Re: [PATCH 3/3] Compute predicates for phi node results in ipa-inline-analysis.c
On Mon, Sep 3, 2012 at 5:52 PM, Jan Hubicka hubi...@ucw.cz wrote: On Fri, Aug 31, 2012 at 7:24 PM, Martin Jambor mjam...@suse.cz wrote: Hi, On Thu, Aug 30, 2012 at 05:11:35PM +0200, Martin Jambor wrote: this is a new version of the patch which makes ipa analysis produce predicates for PHI node results, at least at the bottom of the simplest diamond and semi-diamond CFG subgraphs. This time I also analyze the conditions again rather than extracting information from CFG edges, which means I can reason about substantially more PHI nodes. This patch makes us produce loop bounds hint for the pr48636.f90 testcase. Bootstrapped and tested on x86_64-linux. OK for trunk? Thanks, Martin 2012-08-29 Martin Jambor mjam...@suse.cz * ipa-inline-analysis.c (phi_result_unknown_predicate): New function. (predicate_for_phi_result): Likewise. (estimate_function_body_sizes): Use the above two functions. This patch, on top of the one doing loop calculations almost always, introduces a number of testsuite failures which somehow I had not caught during my testing. The problem is that either calculate_dominance_info or loop_optimizer_init introduce new SSA names for which there is no index in nonconstant_names which is allocated before the dominance and loop computations. I'm currently bootstrapping and testing the following fix which simply allocates the vector after doing the two computations. If it passes I will commit it straight away so that the regression is fixed before I leave for the weekend, I hope it's obvious enough for that. On the other hand, it would really be better if we did not change function bodies during IPA summary generation phase... Um ... we shouldn't do this. Can you track down where it happens? I suppose it might come from CFG manipulations loop_optimizer_init performs when not passing AVOID_CFG_MODIFICATIONS. I bet it come from loop noromalization :) (i.e. loop closed form or preheader construction both needs new SSA names.) I think it would be best to make pass manager to handle this and make loop normalization to happen once before all SSA IPA analysis And compute loops as well. Richard. Honza
Re: [PATCH 3/3] Compute predicates for phi node results in ipa-inline-analysis.c
On Tue, Sep 04, 2012 at 11:27:47AM +0200, Richard Guenther wrote: On Mon, Sep 3, 2012 at 5:52 PM, Jan Hubicka hubi...@ucw.cz wrote: On Fri, Aug 31, 2012 at 7:24 PM, Martin Jambor mjam...@suse.cz wrote: Hi, On Thu, Aug 30, 2012 at 05:11:35PM +0200, Martin Jambor wrote: this is a new version of the patch which makes ipa analysis produce predicates for PHI node results, at least at the bottom of the simplest diamond and semi-diamond CFG subgraphs. This time I also analyze the conditions again rather than extracting information from CFG edges, which means I can reason about substantially more PHI nodes. This patch makes us produce loop bounds hint for the pr48636.f90 testcase. Bootstrapped and tested on x86_64-linux. OK for trunk? Thanks, Martin 2012-08-29 Martin Jambor mjam...@suse.cz * ipa-inline-analysis.c (phi_result_unknown_predicate): New function. (predicate_for_phi_result): Likewise. (estimate_function_body_sizes): Use the above two functions. This patch, on top of the one doing loop calculations almost always, introduces a number of testsuite failures which somehow I had not caught during my testing. The problem is that either calculate_dominance_info or loop_optimizer_init introduce new SSA names for which there is no index in nonconstant_names which is allocated before the dominance and loop computations. I'm currently bootstrapping and testing the following fix which simply allocates the vector after doing the two computations. If it passes I will commit it straight away so that the regression is fixed before I leave for the weekend, I hope it's obvious enough for that. On the other hand, it would really be better if we did not change function bodies during IPA summary generation phase... Um ... we shouldn't do this. Can you track down where it happens? I suppose it might come from CFG manipulations loop_optimizer_init performs when not passing AVOID_CFG_MODIFICATIONS. I bet it come from loop noromalization :) (i.e. loop closed form or preheader construction both needs new SSA names.) I think it would be best to make pass manager to handle this and make loop normalization to happen once before all SSA IPA analysis And compute loops as well. OK, this is now PR 54477 so that we don't forget. Thanks, Martin
Re: [PATCH 3/3] Compute predicates for phi node results in ipa-inline-analysis.c
On Fri, Aug 31, 2012 at 7:24 PM, Martin Jambor mjam...@suse.cz wrote: Hi, On Thu, Aug 30, 2012 at 05:11:35PM +0200, Martin Jambor wrote: this is a new version of the patch which makes ipa analysis produce predicates for PHI node results, at least at the bottom of the simplest diamond and semi-diamond CFG subgraphs. This time I also analyze the conditions again rather than extracting information from CFG edges, which means I can reason about substantially more PHI nodes. This patch makes us produce loop bounds hint for the pr48636.f90 testcase. Bootstrapped and tested on x86_64-linux. OK for trunk? Thanks, Martin 2012-08-29 Martin Jambor mjam...@suse.cz * ipa-inline-analysis.c (phi_result_unknown_predicate): New function. (predicate_for_phi_result): Likewise. (estimate_function_body_sizes): Use the above two functions. This patch, on top of the one doing loop calculations almost always, introduces a number of testsuite failures which somehow I had not caught during my testing. The problem is that either calculate_dominance_info or loop_optimizer_init introduce new SSA names for which there is no index in nonconstant_names which is allocated before the dominance and loop computations. I'm currently bootstrapping and testing the following fix which simply allocates the vector after doing the two computations. If it passes I will commit it straight away so that the regression is fixed before I leave for the weekend, I hope it's obvious enough for that. On the other hand, it would really be better if we did not change function bodies during IPA summary generation phase... Um ... we shouldn't do this. Can you track down where it happens? I suppose it might come from CFG manipulations loop_optimizer_init performs when not passing AVOID_CFG_MODIFICATIONS. Richard. Sorry for the breakage, Martin 2012-08-31 Martin Jambor mjam...@suse.cz * ipa-inline-analysis.c (estimate_function_body_sizes): Allocate nonconstant_names after calculate_dominance_info and loop_optimizer_init. Index: src/gcc/ipa-inline-analysis.c === --- src.orig/gcc/ipa-inline-analysis.c +++ src/gcc/ipa-inline-analysis.c @@ -2185,13 +2185,6 @@ estimate_function_body_sizes (struct cgr struct ipa_node_params *parms_info = NULL; VEC (predicate_t, heap) *nonconstant_names = NULL; - if (ipa_node_params_vector !early optimize) -{ - parms_info = IPA_NODE_REF (node); - VEC_safe_grow_cleared (predicate_t, heap, nonconstant_names, -VEC_length (tree, SSANAMES (my_function))); -} - info-conds = 0; info-entry = 0; @@ -2199,6 +2192,13 @@ estimate_function_body_sizes (struct cgr { calculate_dominance_info (CDI_DOMINATORS); loop_optimizer_init (LOOPS_NORMAL | LOOPS_HAVE_RECORDED_EXITS); + + if (ipa_node_params_vector) + { + parms_info = IPA_NODE_REF (node); + VEC_safe_grow_cleared (predicate_t, heap, nonconstant_names, +VEC_length (tree, SSANAMES (my_function))); + } } if (dump_file)
Re: [PATCH 3/3] Compute predicates for phi node results in ipa-inline-analysis.c
On Fri, Aug 31, 2012 at 7:24 PM, Martin Jambor mjam...@suse.cz wrote: Hi, On Thu, Aug 30, 2012 at 05:11:35PM +0200, Martin Jambor wrote: this is a new version of the patch which makes ipa analysis produce predicates for PHI node results, at least at the bottom of the simplest diamond and semi-diamond CFG subgraphs. This time I also analyze the conditions again rather than extracting information from CFG edges, which means I can reason about substantially more PHI nodes. This patch makes us produce loop bounds hint for the pr48636.f90 testcase. Bootstrapped and tested on x86_64-linux. OK for trunk? Thanks, Martin 2012-08-29 Martin Jambor mjam...@suse.cz * ipa-inline-analysis.c (phi_result_unknown_predicate): New function. (predicate_for_phi_result): Likewise. (estimate_function_body_sizes): Use the above two functions. This patch, on top of the one doing loop calculations almost always, introduces a number of testsuite failures which somehow I had not caught during my testing. The problem is that either calculate_dominance_info or loop_optimizer_init introduce new SSA names for which there is no index in nonconstant_names which is allocated before the dominance and loop computations. I'm currently bootstrapping and testing the following fix which simply allocates the vector after doing the two computations. If it passes I will commit it straight away so that the regression is fixed before I leave for the weekend, I hope it's obvious enough for that. On the other hand, it would really be better if we did not change function bodies during IPA summary generation phase... Um ... we shouldn't do this. Can you track down where it happens? I suppose it might come from CFG manipulations loop_optimizer_init performs when not passing AVOID_CFG_MODIFICATIONS. I bet it come from loop noromalization :) (i.e. loop closed form or preheader construction both needs new SSA names.) I think it would be best to make pass manager to handle this and make loop normalization to happen once before all SSA IPA analysis Honza
Re: [PATCH 3/3] Compute predicates for phi node results in ipa-inline-analysis.c
Hi, this is a new version of the patch which makes ipa analysis produce predicates for PHI node results, at least at the bottom of the simplest diamond and semi-diamond CFG subgraphs. This time I also analyze the conditions again rather than extracting information from CFG edges, which means I can reason about substantially more PHI nodes. This patch makes us produce loop bounds hint for the pr48636.f90 testcase. Bootstrapped and tested on x86_64-linux. OK for trunk? OK, thanks! Do you think you can add testcase? I plan to reorg the analysis to work in dominator order (now we compute dominators anyway for lop analysis) that will make this also bit more strong across non-trivial CFGs. (originally I did not care much since inliner cares only about simple functions with simple CFG, but with inline hints and other stuff we need to be more careful to not throw away useful info. Honza
Re: [PATCH 3/3] Compute predicates for phi node results in ipa-inline-analysis.c
Hi, On Fri, Aug 31, 2012 at 10:52:28AM +0200, Jan Hubicka wrote: Hi, this is a new version of the patch which makes ipa analysis produce predicates for PHI node results, at least at the bottom of the simplest diamond and semi-diamond CFG subgraphs. This time I also analyze the conditions again rather than extracting information from CFG edges, which means I can reason about substantially more PHI nodes. This patch makes us produce loop bounds hint for the pr48636.f90 testcase. Bootstrapped and tested on x86_64-linux. OK for trunk? OK, thanks! Do you think you can add testcase? Thanks, I forgot to include the testcase in the email somehow, I have committed the changes to pr48636.f90 below along with the patch. I plan to reorg the analysis to work in dominator order (now we compute dominators anyway for lop analysis) that will make this also bit more strong across non-trivial CFGs. (originally I did not care much since inliner cares only about simple functions with simple CFG, but with inline hints and other stuff we need to be more careful to not throw away useful info. Well, evaluating the GIMPLE_COND rather than disecting the predicates in an e-aux also makes for much nicer code. However, processing in dominator order is certainly a good idea. Martin Index: src/gcc/testsuite/gfortran.dg/pr48636.f90 === --- src.orig/gcc/testsuite/gfortran.dg/pr48636.f90 +++ src/gcc/testsuite/gfortran.dg/pr48636.f90 @@ -1,5 +1,5 @@ ! { dg-do compile } -! { dg-options -O3 -fdump-ipa-inline } +! { dg-options -O3 -fdump-ipa-inline-details } module foo implicit none @@ -34,4 +34,6 @@ program main end program main ! { dg-final { scan-ipa-dump bar\[^\\n\]*inline copy in MAIN inline } } +! { dg-final { scan-ipa-dump-times phi predicate: 5 inline } } +! { dg-final { scan-ipa-dump inline hints: loop_iterations inline } } ! { dg-final { cleanup-ipa-dump inline } }
Re: [PATCH 3/3] Compute predicates for phi node results in ipa-inline-analysis.c
Hi, On Thu, Aug 30, 2012 at 05:11:35PM +0200, Martin Jambor wrote: this is a new version of the patch which makes ipa analysis produce predicates for PHI node results, at least at the bottom of the simplest diamond and semi-diamond CFG subgraphs. This time I also analyze the conditions again rather than extracting information from CFG edges, which means I can reason about substantially more PHI nodes. This patch makes us produce loop bounds hint for the pr48636.f90 testcase. Bootstrapped and tested on x86_64-linux. OK for trunk? Thanks, Martin 2012-08-29 Martin Jambor mjam...@suse.cz * ipa-inline-analysis.c (phi_result_unknown_predicate): New function. (predicate_for_phi_result): Likewise. (estimate_function_body_sizes): Use the above two functions. This patch, on top of the one doing loop calculations almost always, introduces a number of testsuite failures which somehow I had not caught during my testing. The problem is that either calculate_dominance_info or loop_optimizer_init introduce new SSA names for which there is no index in nonconstant_names which is allocated before the dominance and loop computations. I'm currently bootstrapping and testing the following fix which simply allocates the vector after doing the two computations. If it passes I will commit it straight away so that the regression is fixed before I leave for the weekend, I hope it's obvious enough for that. On the other hand, it would really be better if we did not change function bodies during IPA summary generation phase... Sorry for the breakage, Martin 2012-08-31 Martin Jambor mjam...@suse.cz * ipa-inline-analysis.c (estimate_function_body_sizes): Allocate nonconstant_names after calculate_dominance_info and loop_optimizer_init. Index: src/gcc/ipa-inline-analysis.c === --- src.orig/gcc/ipa-inline-analysis.c +++ src/gcc/ipa-inline-analysis.c @@ -2185,13 +2185,6 @@ estimate_function_body_sizes (struct cgr struct ipa_node_params *parms_info = NULL; VEC (predicate_t, heap) *nonconstant_names = NULL; - if (ipa_node_params_vector !early optimize) -{ - parms_info = IPA_NODE_REF (node); - VEC_safe_grow_cleared (predicate_t, heap, nonconstant_names, -VEC_length (tree, SSANAMES (my_function))); -} - info-conds = 0; info-entry = 0; @@ -2199,6 +2192,13 @@ estimate_function_body_sizes (struct cgr { calculate_dominance_info (CDI_DOMINATORS); loop_optimizer_init (LOOPS_NORMAL | LOOPS_HAVE_RECORDED_EXITS); + + if (ipa_node_params_vector) + { + parms_info = IPA_NODE_REF (node); + VEC_safe_grow_cleared (predicate_t, heap, nonconstant_names, +VEC_length (tree, SSANAMES (my_function))); + } } if (dump_file)
[PATCH 3/3] Compute predicates for phi node results in ipa-inline-analysis.c
Hi, this is a new version of the patch which makes ipa analysis produce predicates for PHI node results, at least at the bottom of the simplest diamond and semi-diamond CFG subgraphs. This time I also analyze the conditions again rather than extracting information from CFG edges, which means I can reason about substantially more PHI nodes. This patch makes us produce loop bounds hint for the pr48636.f90 testcase. Bootstrapped and tested on x86_64-linux. OK for trunk? Thanks, Martin 2012-08-29 Martin Jambor mjam...@suse.cz * ipa-inline-analysis.c (phi_result_unknown_predicate): New function. (predicate_for_phi_result): Likewise. (estimate_function_body_sizes): Use the above two functions. Index: src/gcc/ipa-inline-analysis.c === --- src.orig/gcc/ipa-inline-analysis.c +++ src/gcc/ipa-inline-analysis.c @@ -2070,6 +2070,99 @@ param_change_prob (gimple stmt, int i) return REG_BR_PROB_BASE; } +/* Find whether a basic block BB is the final block of a (half) diamond CFG + sub-graph and if the predicate the condition depends on is known. If so, + return true and store the pointer the predicate in *P. */ + +static bool +phi_result_unknown_predicate (struct ipa_node_params *info, + struct inline_summary *summary, basic_block bb, + struct predicate *p, + VEC (predicate_t, heap) *nonconstant_names) +{ + edge e; + edge_iterator ei; + basic_block first_bb = NULL; + gimple stmt; + + if (single_pred_p (bb)) +{ + *p = false_predicate (); + return true; +} + + FOR_EACH_EDGE (e, ei, bb-preds) +{ + if (single_succ_p (e-src)) + { + if (!single_pred_p (e-src)) + return false; + if (!first_bb) + first_bb = single_pred (e-src); + else if (single_pred (e-src) != first_bb) + return false; + } + else + { + if (!first_bb) + first_bb = e-src; + else if (e-src != first_bb) + return false; + } +} + + if (!first_bb) +return false; + + stmt = last_stmt (first_bb); + if (!stmt + || gimple_code (stmt) != GIMPLE_COND + || !is_gimple_ip_invariant (gimple_cond_rhs (stmt))) +return false; + + *p = will_be_nonconstant_expr_predicate (info, summary, + gimple_cond_lhs (stmt), + nonconstant_names); + if (true_predicate_p (p)) +return false; + else +return true; +} + +/* Given a PHI statement in a function described by inline properties SUMMARY + and *P being the predicate describing whether the selected PHI argument is + known, store a predicate for the result of the PHI statement into + NONCONSTANT_NAMES, if possible. */ + +static void +predicate_for_phi_result (struct inline_summary *summary, gimple phi, + struct predicate *p, + VEC (predicate_t, heap) *nonconstant_names) +{ + unsigned i; + + for (i = 0; i gimple_phi_num_args (phi); i++) +{ + tree arg = gimple_phi_arg (phi, i)-def; + if (!is_gimple_min_invariant (arg)) + { + gcc_assert (TREE_CODE (arg) == SSA_NAME); + *p = or_predicates (summary-conds, p, + VEC_index (predicate_t, nonconstant_names, + SSA_NAME_VERSION (arg))); + if (true_predicate_p (p)) + return; + } +} + + if (dump_file (dump_flags TDF_DETAILS)) +{ + fprintf (dump_file, \t\tphi predicate: ); + dump_predicate (dump_file, summary-conds, p); +} + VEC_replace (predicate_t, nonconstant_names, + SSA_NAME_VERSION (gimple_phi_result (phi)), *p); +} /* Compute function body size parameters for NODE. When EARLY is true, we compute only simple summaries without @@ -2143,7 +2236,30 @@ estimate_function_body_sizes (struct cgr fprintf (dump_file, \n BB %i predicate:, bb-index); dump_predicate (dump_file, info-conds, bb_predicate); } - + + if (parms_info nonconstant_names) + { + struct predicate phi_predicate; + bool first_phi = true; + + for (bsi = gsi_start_phis (bb); !gsi_end_p (bsi); gsi_next (bsi)) + { + if (first_phi + !phi_result_unknown_predicate (parms_info, info, bb, + phi_predicate, + nonconstant_names)) + break; + first_phi = false; + if (dump_file (dump_flags TDF_DETAILS)) + { + fprintf (dump_file, ); + print_gimple_stmt (dump_file, gsi_stmt (bsi), 0, 0); + } + predicate_for_phi_result (info, gsi_stmt (bsi), phi_predicate, +
Re: [PATCH 3/3] Compute predicates for phi node results in ipa-inline-analysis.c
Hi, this third patch is basically a proof-of-concept aiming at alleviating the following code found in Fortran functions when they look at the contents of array descriptors: bb 2: stride.156_7 = strain_tensor_6(D)-dim[0].stride; if (stride.156_7 != 0) goto bb 3; else goto bb 4; bb 3: bb 4: # stride.156_4 = PHI stride.156_7(3), 1(2) and stride.156_4 is then used for other computations. Currently we compute a predicate for SSA name stride.156_7 but the PHI node stops us from having one for stride.156_4 and those computed from it. This patch looks at phi nodes, and if its pairs of predecessors have the same nearest common dominator, and the condition there is known to be described by a predicate (computed either by set_cond_stmt_execution_predicate or, set_switch_stmt_execution_predicate, we depend on knowing how exactly they behave), we use the parameter and offset from the predicate condition and create one for the PHI node result, provided the arguments of a phi node allow that, of course. Consider: b==0? T/ \F /\ / \ a==0? a==0? T/ \F T/ \F ... \ / ... \ / PHI In this case vale of PHI is determined by a==0, but the condition in common dominator would be b==0. We can work this out from control dependency relation or handle it by propagation engine, but perhaps it is overkill. What about special casing (half) diamond CFG to start with? Path is OK with that change. Honza
[PATCH 3/3] Compute predicates for phi node results in ipa-inline-analysis.c
Hi, this third patch is basically a proof-of-concept aiming at alleviating the following code found in Fortran functions when they look at the contents of array descriptors: bb 2: stride.156_7 = strain_tensor_6(D)-dim[0].stride; if (stride.156_7 != 0) goto bb 3; else goto bb 4; bb 3: bb 4: # stride.156_4 = PHI stride.156_7(3), 1(2) and stride.156_4 is then used for other computations. Currently we compute a predicate for SSA name stride.156_7 but the PHI node stops us from having one for stride.156_4 and those computed from it. This patch looks at phi nodes, and if its pairs of predecessors have the same nearest common dominator, and the condition there is known to be described by a predicate (computed either by set_cond_stmt_execution_predicate or, set_switch_stmt_execution_predicate, we depend on knowing how exactly they behave), we use the parameter and offset from the predicate condition and create one for the PHI node result, provided the arguments of a phi node allow that, of course. I hacked this together one evening a some timw ago and I expect to talk with Honza about how we can perhaps access information abut edges properly, nevertheless the patch passes bootstrap and testing on x86_64. On current trunk, I need to pass -finline-limit=204 to cut down execution time of fatigue2 polyhedron benchmark from 155 seconds to 91 seconds. With the patch, I only need -finline-limit=166. So there's still quite some way to go but something along these lines can be part of it. Thanks for all comments and suggestions, Martin 2012-05-30 Martin Jambor mjam...@suse.cz * ipa-inline-analysis.c (known_phi_condition_for_bb): New function. (predicate_for_phi_result): Likewise. (estimate_function_body_sizes): Use the above two functions. (inline_analyze_function): Calculate and free dominance info. Index: src/gcc/ipa-inline-analysis.c === --- src.orig/gcc/ipa-inline-analysis.c +++ src/gcc/ipa-inline-analysis.c @@ -1954,6 +1954,96 @@ param_change_prob (gimple stmt, int i) return REG_BR_PROB_BASE; } +/* For basic block BB, find if all pairs of its predecesors have a common + dominator and if that dominator ends with a simple condition. If so, return + TRUE and stor pointer to *C. */ + +static bool +known_phi_condition_for_bb (struct inline_summary *info, basic_block bb, + struct condition **c) +{ + edge_iterator ei; + edge e; + basic_block computed_dom = NULL; + basic_block prev = NULL; + + FOR_EACH_EDGE (e, ei, bb-preds) +{ + if (prev) + { + basic_block dom = nearest_common_dominator (CDI_DOMINATORS, prev, + e-src); + if (!computed_dom) + computed_dom = dom; + else if (dom != computed_dom) + return false; + + } + prev = e-src; +} + + if (!computed_dom) +return false; + + FOR_EACH_EDGE (e, ei, computed_dom-succs) +if (e-aux) + { + struct predicate *p; + int i; + p = (struct predicate *) e-aux; + + if (p-clause[0] == 0 || p-clause[1] != 0) + return false; + for (i = 0 ; i NUM_CONDITIONS; i++) + if (((1 i) p-clause[0]) == p-clause[0]) + break; + if (i == NUM_CONDITIONS || i predicate_first_dynamic_condition) + return false; + + *c = VEC_index (condition, info-conds, + i - predicate_first_dynamic_condition); + return true; + } + return false; +} + +/* Given a PHI statement STMT in a function described by inline properties INFO + and in a basic lock whose predecesors in CFG is selected according to a + parameter (and potentially offset) stored in condition *C, store a predicate + for the result of the PHI statement into NONCONSTANT_NAMES, if possible. */ + +static void +predicate_for_phi_result (struct inline_summary *info, gimple stmt, + struct condition *c, + VEC (predicate_t, heap) *nonconstant_names) +{ + struct predicate p; + unsigned i; + + for (i = 0; i gimple_phi_num_args (stmt); i++) +{ + tree arg = gimple_phi_arg (stmt, i)-def; + if (!is_gimple_min_invariant (arg)) + { + gcc_assert (TREE_CODE (arg) == SSA_NAME); + if (true_predicate_p (VEC_index (predicate_t, nonconstant_names, + SSA_NAME_VERSION (arg + return; + } +} + + p = add_condition (info, c-operand_num, c-agg_contents, c-offset, +CHANGED, NULL); + if (dump_file (dump_flags TDF_DETAILS)) +{ + fprintf (dump_file, ); + print_gimple_stmt (dump_file, stmt, 0, 0); + fprintf (dump_file, \t\tphi predicate: ); + dump_predicate (dump_file, info-conds, p); +} + VEC_replace (predicate_t, nonconstant_names, +