From patchwork Tue Jun 20 12:13:49 2017 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: =?utf-8?q?Martin_Li=C5=A1ka?= X-Patchwork-Id: 778244 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from sourceware.org (server1.sourceware.org [209.132.180.131]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 3wsRbM6hyTz9s4s for ; Tue, 20 Jun 2017 22:14:07 +1000 (AEST) Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.b="EXA7YAaE"; dkim-atps=neutral DomainKey-Signature: a=rsa-sha1; c=nofws; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender :subject:to:cc:references:from:message-id:date:mime-version :in-reply-to:content-type; q=dns; s=default; b=MhxYdlJT5cuesygtD X6FirXpcbCUqSGy6mYHG/Z2bP6tH3LHDQ38xoWAmRL5sOg885C7QQ9V/5iLsdWgF qbZZEuJH/jeB9RDsbQVvgDHn5xMdoY7I8RFCQQD+8jRAj3+e/AQxytJ36VGBqAdv 9hAFOEyeTsS+7qpLVyFPOLc4pc= DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=gcc.gnu.org; h=list-id :list-unsubscribe:list-archive:list-post:list-help:sender :subject:to:cc:references:from:message-id:date:mime-version :in-reply-to:content-type; s=default; bh=9AFndoi6CGtKcF0ZkOZfnvi C2nQ=; b=EXA7YAaEVya1c+JQbkgvCcLetsZuZk7o6WoTzPKIVufMPRrscd+eFJz 95/55B23Vd91Pd85cHvomF5k+wdJmDDhuas30IhUcjQ5UUkf/gK2OXOVoFIKZvz2 oRC1ngQ/BCtyeS1S4M/4k+joXqd1zkfYs2OhkSklaQouecHju0gU= Received: (qmail 130058 invoked by alias); 20 Jun 2017 12:13:58 -0000 Mailing-List: contact gcc-patches-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Id: List-Unsubscribe: List-Archive: List-Post: List-Help: Sender: gcc-patches-owner@gcc.gnu.org Delivered-To: mailing list gcc-patches@gcc.gnu.org Received: (qmail 130041 invoked by uid 89); 20 Jun 2017 12:13:56 -0000 Authentication-Results: sourceware.org; auth=none X-Virus-Found: No X-Spam-SWARE-Status: No, score=-26.9 required=5.0 tests=BAYES_00, GIT_PATCH_0, GIT_PATCH_1, GIT_PATCH_2, GIT_PATCH_3, SPF_PASS autolearn=ham version=3.3.2 spammy=growth, retire X-HELO: mx1.suse.de Received: from mx2.suse.de (HELO mx1.suse.de) (195.135.220.15) by sourceware.org (qpsmtpd/0.93/v0.84-503-g423c35a) with ESMTP; Tue, 20 Jun 2017 12:13:52 +0000 Received: from relay2.suse.de (charybdis-ext.suse.de [195.135.220.254]) by mx1.suse.de (Postfix) with ESMTP id 19172AAB9; Tue, 20 Jun 2017 12:13:50 +0000 (UTC) Subject: Re: [PATCH 2/3] Make early return predictor more precise. To: Jan Hubicka Cc: gcc-patches@gcc.gnu.org References: <20170609140804.GI53583@kam.mff.cuni.cz> <20170619111135.GC72026@kam.mff.cuni.cz> From: =?UTF-8?Q?Martin_Li=c5=a1ka?= Message-ID: <62ae8f2a-0e53-5177-afa4-4314f118c3cc@suse.cz> Date: Tue, 20 Jun 2017 14:13:49 +0200 User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:52.0) Gecko/20100101 Thunderbird/52.1.1 MIME-Version: 1.0 In-Reply-To: <20170619111135.GC72026@kam.mff.cuni.cz> X-IsSubscribed: yes On 06/19/2017 01:11 PM, Jan Hubicka wrote: >> Ok, you're right that we can preserve the predictor. However, let's consider following test-case: >> >> static >> int baz(int a) >> { >> if (a == 1) >> return 1; >> >> return 0; >> } >> >> >> static >> int bar(int a) >> { >> if (a == 1) >> return baz(a); >> >> return 0; >> } >> >> static >> int foo(int a) >> { >> if (a == 1) >> return bar(a); >> >> return 12; >> } >> >> int main(int argc, char **argv) >> { >> return foo(argc); >> } >> >> There after einline we have: >> >> main (int argc, char * * argv) >> { >> int D.1832; >> int _3; >> int _4; >> >> [100.00%]: >> if (argc_2(D) == 1) >> goto ; [37.13%] >> else >> goto ; [62.87%] >> >> [37.13%]: >> // predicted unlikely by early return (on trees) predictor. >> // predicted unlikely by early return (on trees) predictor. >> // predicted unlikely by early return (on trees) predictor. >> >> [100.00%]: >> # _3 = PHI <12(2), 1(3)> >> _5 = _3; >> _4 = _5; >> return _4; >> >> } >> >> I'm thinking what's the best place to merge all the predictor >> statements? > > I wonder if we need to - predictors are relatively short lived. > In fact they do not need to hit IPA passes but they do as at a time > I was implementing them I was worrying about introducing yet another > global IPA pass to remove them (we can't do during early inlining > because we want to reuse them after inlining). Ok, so I fixed that in the described way. There's one remaining fallout of: gcc/testsuite/gcc.dg/tree-ssa/ipa-split-5.c Where a fnsplit is properly done, but then it's again inlined: Considering split_me.part.0/5 with 23 size to be inlined into test/2 in unknown:0 Estimated badness is -0.000001, frequency 0.33. Inlined split_me.part.0 into test which now has time 50.300000 and size 44, net change of +17. Considering split_me.part.0/5 with 23 size to be inlined into test/2 in unknown:0 Estimated badness is -0.000001, frequency 0.33. Inlined split_me.part.0 into test which now has time 70.760000 and size 61, net change of +17. Considering split_me.part.0/5 with 23 size to be inlined into test/2 in unknown:0 Estimated badness is -0.000001, frequency 0.33. Inlined split_me.part.0 into test which now has time 91.220000 and size 78, net change of +17. Considering split_me.part.0/5 with 23 size to be inlined into test/2 in unknown:0 Estimated badness is -0.000001, frequency 0.33. Inlined split_me.part.0 into test which now has time 111.680000 and size 95, net change of +17. Unit growth for small function inlining: 61->129 (111%) ... Any hint how to block the IPA inlining? Sending new version of patch. Martin > > I would just move pass_strip_predict_hints pre-IPA and not worry about > them chaining. > > There is problem that after inlining the prediction may expand its scope > and predict branch that it outside of the original function body, > but I do not see very easy solution for that besides not re-doing > prediction (we could also copy probabilities from the inlined function > when they exists and honnor them in the outer function. I am not sure > that is going to improve prediction quality though - extra context > is probably useful) > > Thanks, > Honza >> >> Thanks, >> Martin >> >>> >>> Where did you found this case? >>> Honza >>>> >>>> /* Create a new deep copy of the statement. */ >>>> copy = gimple_copy (stmt); >>>> -- >>>> 2.13.0 >>>> From 84625a782add6ae2ed29630815b61b34a052770a Mon Sep 17 00:00:00 2001 From: marxin Date: Tue, 6 Jun 2017 10:55:18 +0200 Subject: [PATCH 1/2] Make early return predictor more precise. gcc/ChangeLog: 2017-05-26 Martin Liska PR tree-optimization/79489 * gimplify.c (maybe_add_early_return_predict_stmt): New function. (gimplify_return_expr): Call the function. * predict.c (tree_estimate_probability_bb): Remove handling of early return. * predict.def: Update comment about early return predictor. * gimple-predict.h (is_gimple_predict): New function. * predict.def: Change default value of early return to 66. * tree-tailcall.c (find_tail_calls): Skip GIMPLE_PREDICT statements. * passes.def: Put pass_strip_predict_hints to the beginning of IPA passes. --- gcc/gimple-low.c | 2 ++ gcc/gimple-predict.h | 8 ++++++++ gcc/gimplify.c | 16 ++++++++++++++++ gcc/passes.def | 1 + gcc/predict.c | 41 ----------------------------------------- gcc/predict.def | 15 +++------------ gcc/tree-tailcall.c | 2 ++ 7 files changed, 32 insertions(+), 53 deletions(-) diff --git a/gcc/gimple-low.c b/gcc/gimple-low.c index 619b9d7bfb1..4ea6c3532f3 100644 --- a/gcc/gimple-low.c +++ b/gcc/gimple-low.c @@ -30,6 +30,8 @@ along with GCC; see the file COPYING3. If not see #include "calls.h" #include "gimple-iterator.h" #include "gimple-low.h" +#include "predict.h" +#include "gimple-predict.h" /* The differences between High GIMPLE and Low GIMPLE are the following: diff --git a/gcc/gimple-predict.h b/gcc/gimple-predict.h index ba58e12e9e9..0e6c2e1ea01 100644 --- a/gcc/gimple-predict.h +++ b/gcc/gimple-predict.h @@ -80,4 +80,12 @@ gimple_build_predict (enum br_predictor predictor, enum prediction outcome) return p; } +/* Return true if GS is a GIMPLE_PREDICT statement. */ + +static inline bool +is_gimple_predict (const gimple *gs) +{ + return gimple_code (gs) == GIMPLE_PREDICT; +} + #endif /* GCC_GIMPLE_PREDICT_H */ diff --git a/gcc/gimplify.c b/gcc/gimplify.c index 9af95a28704..1c6e1591953 100644 --- a/gcc/gimplify.c +++ b/gcc/gimplify.c @@ -1428,6 +1428,20 @@ gimplify_bind_expr (tree *expr_p, gimple_seq *pre_p) return GS_ALL_DONE; } +/* Maybe add early return predict statement to PRE_P sequence. */ + +static void +maybe_add_early_return_predict_stmt (gimple_seq *pre_p) +{ + /* If we are not in a conditional context, add PREDICT statement. */ + if (gimple_conditional_context ()) + { + gimple *predict = gimple_build_predict (PRED_TREE_EARLY_RETURN, + NOT_TAKEN); + gimplify_seq_add_stmt (pre_p, predict); + } +} + /* Gimplify a RETURN_EXPR. If the expression to be returned is not a GIMPLE value, it is assigned to a new temporary and the statement is re-written to return the temporary. @@ -1458,6 +1472,7 @@ gimplify_return_expr (tree stmt, gimple_seq *pre_p) || TREE_CODE (ret_expr) == RESULT_DECL || ret_expr == error_mark_node) { + maybe_add_early_return_predict_stmt (pre_p); greturn *ret = gimple_build_return (ret_expr); gimple_set_no_warning (ret, TREE_NO_WARNING (stmt)); gimplify_seq_add_stmt (pre_p, ret); @@ -1525,6 +1540,7 @@ gimplify_return_expr (tree stmt, gimple_seq *pre_p) gimplify_and_add (TREE_OPERAND (stmt, 0), pre_p); + maybe_add_early_return_predict_stmt (pre_p); ret = gimple_build_return (result); gimple_set_no_warning (ret, TREE_NO_WARNING (stmt)); gimplify_seq_add_stmt (pre_p, ret); diff --git a/gcc/passes.def b/gcc/passes.def index c14f6b9f63c..316e19d12e3 100644 --- a/gcc/passes.def +++ b/gcc/passes.def @@ -107,6 +107,7 @@ along with GCC; see the file COPYING3. If not see early optimizations again. It is thus good idea to do this late. */ NEXT_PASS (pass_split_functions); + NEXT_PASS (pass_strip_predict_hints); POP_INSERT_PASSES () NEXT_PASS (pass_release_ssa_names); NEXT_PASS (pass_rebuild_cgraph_edges); diff --git a/gcc/predict.c b/gcc/predict.c index 60d1a094d10..790be9fbf16 100644 --- a/gcc/predict.c +++ b/gcc/predict.c @@ -2739,7 +2739,6 @@ tree_estimate_probability_bb (basic_block bb, bool local_only) { edge e; edge_iterator ei; - gimple *last; FOR_EACH_EDGE (e, ei, bb->succs) { @@ -2766,46 +2765,6 @@ tree_estimate_probability_bb (basic_block bb, bool local_only) } } - /* Predict early returns to be probable, as we've already taken - care for error returns and other cases are often used for - fast paths through function. - - Since we've already removed the return statements, we are - looking for CFG like: - - if (conditional) - { - .. - goto return_block - } - some other blocks - return_block: - return_stmt. */ - if (e->dest != bb->next_bb - && e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun) - && single_succ_p (e->dest) - && single_succ_edge (e->dest)->dest == EXIT_BLOCK_PTR_FOR_FN (cfun) - && (last = last_stmt (e->dest)) != NULL - && gimple_code (last) == GIMPLE_RETURN) - { - edge e1; - edge_iterator ei1; - - if (single_succ_p (bb)) - { - FOR_EACH_EDGE (e1, ei1, bb->preds) - if (!predicted_by_p (e1->src, PRED_NULL_RETURN) - && !predicted_by_p (e1->src, PRED_CONST_RETURN) - && !predicted_by_p (e1->src, PRED_NEGATIVE_RETURN)) - predict_edge_def (e1, PRED_TREE_EARLY_RETURN, NOT_TAKEN); - } - else - if (!predicted_by_p (e->src, PRED_NULL_RETURN) - && !predicted_by_p (e->src, PRED_CONST_RETURN) - && !predicted_by_p (e->src, PRED_NEGATIVE_RETURN)) - predict_edge_def (e, PRED_TREE_EARLY_RETURN, NOT_TAKEN); - } - /* Look for block we are guarding (ie we dominate it, but it doesn't postdominate us). */ if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun) && e->dest != bb diff --git a/gcc/predict.def b/gcc/predict.def index fcda6c48f11..f7b2bf7738c 100644 --- a/gcc/predict.def +++ b/gcc/predict.def @@ -128,18 +128,9 @@ DEF_PREDICTOR (PRED_POLYMORPHIC_CALL, "polymorphic call", HITRATE (59), 0) indefinitely. */ DEF_PREDICTOR (PRED_RECURSIVE_CALL, "recursive call", HITRATE (75), 0) -/* Branch causing function to terminate is probably not taken. - FIXME: early return currently predicts code: - int foo (int a) - { - if (a) - bar(); - else - bar2(); - } - even though there is no return statement involved. We probably want to track - this from FE or retire the predictor. */ -DEF_PREDICTOR (PRED_TREE_EARLY_RETURN, "early return (on trees)", HITRATE (54), 0) +/* Branch causing function to terminate is probably not taken. */ +DEF_PREDICTOR (PRED_TREE_EARLY_RETURN, "early return (on trees)", HITRATE (66), + 0) /* Branch containing goto is probably not taken. FIXME: Currently not used. */ diff --git a/gcc/tree-tailcall.c b/gcc/tree-tailcall.c index b7053387e91..6aa9a56462e 100644 --- a/gcc/tree-tailcall.c +++ b/gcc/tree-tailcall.c @@ -421,6 +421,7 @@ find_tail_calls (basic_block bb, struct tailcall **ret) if (gimple_code (stmt) == GIMPLE_LABEL || gimple_code (stmt) == GIMPLE_RETURN || gimple_code (stmt) == GIMPLE_NOP + || gimple_code (stmt) == GIMPLE_PREDICT || gimple_clobber_p (stmt) || is_gimple_debug (stmt)) continue; @@ -555,6 +556,7 @@ find_tail_calls (basic_block bb, struct tailcall **ret) if (gimple_code (stmt) == GIMPLE_LABEL || gimple_code (stmt) == GIMPLE_NOP + || gimple_code (stmt) == GIMPLE_PREDICT || gimple_clobber_p (stmt) || is_gimple_debug (stmt)) continue; -- 2.13.1