| Message ID | CAELXzTNiYLRn0T70mi6K27H7Tt9AQNYyYamJ99di3vWtivLGbw@mail.gmail.com |
|---|---|
| State | New |
| Headers | show |
Ping ? Thanks, Kugan On 23 August 2016 at 12:11, Kugan Vivekanandarajah <kugan.vivekanandarajah@linaro.org> wrote: > Hi, > > On 19 August 2016 at 21:41, Richard Biener <richard.guenther@gmail.com> wrote: >> On Tue, Aug 16, 2016 at 9:45 AM, kugan >> <kugan.vivekanandarajah@linaro.org> wrote: >>> Hi Richard, >>> >>> On 12/08/16 20:43, Richard Biener wrote: >>>> >>>> On Wed, Aug 3, 2016 at 3:17 AM, kugan <kugan.vivekanandarajah@linaro.org> >>>> wrote: >>> >>> >>> [SNIP] >>> >>>> >>>> diff --git a/gcc/common.opt b/gcc/common.opt >>>> index 8a292ed..7028cd4 100644 >>>> --- a/gcc/common.opt >>>> +++ b/gcc/common.opt >>>> @@ -2482,6 +2482,10 @@ ftree-vrp >>>> Common Report Var(flag_tree_vrp) Init(0) Optimization >>>> Perform Value Range Propagation on trees. >>>> >>>> +fdisable-tree-evrp >>>> +Common Report Var(flag_disable_early_vrp) Init(0) Optimization >>>> +Disable Early Value Range Propagation on trees. >>>> + >>>> >>>> no please, this is automatically supported via -fdisable- >>> >>> >>> I am now having -ftree-evrp which is enabled all the time. But This will >>> only be used for disabling the early-vrp. That is, early-vrp will be run >>> when ftree-vrp is enabled and ftree-evrp is not explicitly disabled. Is this >>> OK? >> >> Why would one want to disable early-vrp? I see you do this in the testsuite >> for non-early VRP unit-tests but using -fdisable-tree-evrp1 there >> would be ok as well. > > Removed it altogether. I though that you wanted a way to disable > early-vrp for testing purposes. > >>>> >>>> @@ -1728,11 +1736,12 @@ extract_range_from_assert (value_range *vr_p, tree >>>> expr) >>>> always false. */ >>>> >>>> static void >>>> -extract_range_from_ssa_name (value_range *vr, tree var) >>>> +extract_range_from_ssa_name (value_range *vr, bool dom_p, tree var) >>>> { >>>> value_range *var_vr = get_value_range (var); >>>> >>>> - if (var_vr->type != VR_VARYING) >>>> + if (var_vr->type != VR_VARYING >>>> + && (!dom_p || var_vr->type != VR_UNDEFINED)) >>>> copy_value_range (vr, var_vr); >>>> else >>>> set_value_range (vr, VR_RANGE, var, var, NULL); >>>> >>>> why do you need these changes? I think I already told you you need to >>>> initialize the lattice to sth else than VR_UNDEFINED and that you can't >>>> fully re-use update_value_range. If you don't want to do that then >>>> instead >>>> of doing changes all over the place do it in get_value_range and have a >>>> global flag. >>> >>> >>> I have now added a global early_vrp_p and use this to initialize >>> VR_INITIALIZER and get_value_range default to VR_VARYING. >> >> ICK. Ok, I see that this works, but it is quite ugly, so (see below) >> >>>> >>>> >>>> @@ -3594,7 +3643,8 @@ extract_range_from_cond_expr (value_range *vr, >>>> gassign *stmt) >>>> on the range of its operand and the expression code. */ >>>> >>>> static void >>>> -extract_range_from_comparison (value_range *vr, enum tree_code code, >>>> +extract_range_from_comparison (value_range *vr, >>>> + enum tree_code code, >>>> tree type, tree op0, tree op1) >>>> { >>>> bool sop = false; >>>> >>>> remove these kind of no-op changes. >>> >>> >>> Done. >>> >>> >>>> >>>> +/* Initialize local data structures for VRP. If DOM_P is true, >>>> + we will be calling this from early_vrp where value range propagation >>>> + is done by visiting stmts in dominator tree. ssa_propagate engine >>>> + is not used in this case and that part of the ininitialization will >>>> + be skipped. */ >>>> >>>> static void >>>> -vrp_initialize (void) >>>> +vrp_initialize (bool dom_p) >>>> { >>>> basic_block bb; >>>> >>>> @@ -6949,6 +7010,9 @@ vrp_initialize (void) >>>> vr_phi_edge_counts = XCNEWVEC (int, num_ssa_names); >>>> bitmap_obstack_initialize (&vrp_equiv_obstack); >>>> >>>> + if (dom_p) >>>> + return; >>>> + >>>> >>>> split the function instead. >>>> >>>> @@ -7926,7 +7992,8 @@ vrp_visit_switch_stmt (gswitch *stmt, edge >>>> *taken_edge_p) >>>> If STMT produces a varying value, return SSA_PROP_VARYING. */ >>>> >>>> static enum ssa_prop_result >>>> -vrp_visit_stmt (gimple *stmt, edge *taken_edge_p, tree *output_p) >>>> +vrp_visit_stmt_worker (gimple *stmt, bool dom_p, edge *taken_edge_p, >>>> + tree *output_p) >>>> { >>>> tree def; >>>> ssa_op_iter iter; >>>> @@ -7940,7 +8007,7 @@ vrp_visit_stmt (gimple *stmt, edge >>>> *taken_edge_p, tree *output_p) >>>> if (!stmt_interesting_for_vrp (stmt)) >>>> gcc_assert (stmt_ends_bb_p (stmt)); >>>> else if (is_gimple_assign (stmt) || is_gimple_call (stmt)) >>>> - return vrp_visit_assignment_or_call (stmt, output_p); >>>> + return vrp_visit_assignment_or_call (stmt, dom_p, output_p); >>>> else if (gimple_code (stmt) == GIMPLE_COND) >>>> return vrp_visit_cond_stmt (as_a <gcond *> (stmt), taken_edge_p); >>>> else if (gimple_code (stmt) == GIMPLE_SWITCH) >>>> @@ -7954,6 +8021,12 @@ vrp_visit_stmt (gimple *stmt, edge >>>> *taken_edge_p, tree *output_p) >>>> return SSA_PROP_VARYING; >>>> } >>>> >>>> +static enum ssa_prop_result >>>> +vrp_visit_stmt (gimple *stmt, edge *taken_edge_p, tree *output_p) >>>> +{ >>>> + return vrp_visit_stmt_worker (stmt, false, taken_edge_p, output_p); >>>> +} >>>> >>>> as said the refactoring that would be appreciated is to split out the >>>> update_value_range calls >>>> from the worker functions so you can call the respective functions >>>> from the DOM implementations. >>>> That they are globbed in vrp_visit_stmt currently is due to the API of >>>> the SSA propagator. >>> >>> Sent this as separate patch for easy reviewing and testing. >> >> Thanks. >> >>>> >>>> @@ -8768,6 +8842,12 @@ vrp_visit_phi_node (gphi *phi) >>>> fprintf (dump_file, "\n"); >>>> } >>>> >>>> + if (dom_p && vr_arg.type == VR_UNDEFINED) >>>> + { >>>> + set_value_range_to_varying (&vr_result); >>>> + break; >>>> + } >>>> + >>>> >>>> eh... ok, so another way to attack this is, instead of initializing >>>> the lattice to sth else >>>> than VR_UNDEFINED, make sure to drop the lattice to varying for all PHI >>>> args on >>>> yet unvisited incoming edges (you're not doing optimistic VRP). That's >>>> the only >>>> place you _have_ to do it. >>> >>> >>> Even when it is initialize (as I am doing now), we can still end up with >>> VR_UNDEFINED during the propagation. I have just left the above so that we >>> dont end up with the wrong VR. >> >> How would we end up with wrong VRs? I see >> >> + /* Discover VR when condition is true. */ >> + extract_range_for_var_from_comparison_expr (op0, code, op0, op1, &vr); >> + if (old_vr->type == VR_RANGE || old_vr->type == VR_ANTI_RANGE) >> + vrp_intersect_ranges (&vr, old_vr); >> >> where you already disregard UNDEFINED as old_vr. >> >> What you might be missing is to set all DEFs on !stmt_interesting_for_vrp to >> VARYING. Also >> >> + if (stmt_interesting_for_vrp (stmt)) >> + { >> + tree lhs = gimple_get_lhs (stmt); >> + value_range vr = VR_INITIALIZER; >> + vrp_visit_stmt_worker (stmt, &taken_edge, &output, &vr); >> + update_value_range (lhs, &vr); >> + >> + /* Try folding stmts with the VR discovered. */ >> + if (fold_stmt (&gsi, follow_single_use_edges)) >> + update_stmt (gsi_stmt (gsi)); >> >> folding here can introduce additional stmts and thus unvisited SSA defs >> which would end up with VR_UNINITIALIZED defs - I don't see exactly >> where that would cause issues but I'm not sure it might not. So better >> use fold_stmt_inplace or alternatively if fold_stmt returned true then, >> remembering the previous stmt gsi, iterate over all stmts emitted and >> set their defs to varying (or re-visit them). See for example how >> tree-ssa-forwprop.c does this re-visiting (it revisits all changed stmts). > > I am now setting the results of stmts that are not interesting to vrp > to VR_VARYING. > > Also, before visiting PHI, if any of the arguments are undefined, > result of the PHI is also set varying. > > I have removed all the others. This now bootstraps and passes > regressions (see attached patch). > > >> Note that you want to have a custom valueize function instead of just >> follow_single_use_edges as you want to valueize all SSA names according >> to their lattice value (if it has a single value). You can use vrp_valueize >> for this though that gets you non-single-use edge following as well. >> Eventually it's going to be cleaner to do what the SSA propagator does and >> before folding do >> >> did_replace = replace_uses_in (stmt, vrp_valueize); >> if (fold_stmt (&gsi, follow_single_use_edges) >> || did_replace) >> update_stmt (gsi_stmt (gsi)); >> >> exporting replace_uses_in for this is ok. I guess I prefer this for now. > > I also added the above. I noticed that I need > recompute_tree_invariant_for_addr_expr as in ssa_propagate. My initial > implementation also had gimple_purge_all_dead_eh_edges and > fixup_noreturn_call as in ssa_propagat but I thinj that is not needed > as it would be done at the end of the pass. > > With this I noticed more stmts are folded before vrp1. This required > me to adjust some testcases. > >> >> Overall this now looks good apart from the folding and the VR_INITIALIZER thing. >> >> You can commit the already approved refactoring changes and combine this >> patch with the struct value_range move, this way I can more easily look into >> issues with the UNDEFINED thing if you can come up with a testcase that >> doesn't work. >> > > I have now committed all the dependent patches. > > Attached patch passes regression and bootstrap except pr33738.C. This > is an unrelated issue as discussed in > https://gcc.gnu.org/ml/gcc-patches/2016-08/msg01386.html > > Is this OK? > > Thanks, > Kugan > > >> Thanks, >> Richard. >> >>> I also noticed that g++.dg/warn/pr33738.C testcase is now failing. This is >>> because, with early-vrp setting value range ccp2 is optimizing without >>> issuing a warning. I will look into it. >>> >>> bootstrap and regression testing is in progress. >>> >>> Thanks, >>> Kugan
On Tue, Aug 23, 2016 at 4:11 AM, Kugan Vivekanandarajah <kugan.vivekanandarajah@linaro.org> wrote: > Hi, > > On 19 August 2016 at 21:41, Richard Biener <richard.guenther@gmail.com> wrote: >> On Tue, Aug 16, 2016 at 9:45 AM, kugan >> <kugan.vivekanandarajah@linaro.org> wrote: >>> Hi Richard, >>> >>> On 12/08/16 20:43, Richard Biener wrote: >>>> >>>> On Wed, Aug 3, 2016 at 3:17 AM, kugan <kugan.vivekanandarajah@linaro.org> >>>> wrote: >>> >>> >>> [SNIP] >>> >>>> >>>> diff --git a/gcc/common.opt b/gcc/common.opt >>>> index 8a292ed..7028cd4 100644 >>>> --- a/gcc/common.opt >>>> +++ b/gcc/common.opt >>>> @@ -2482,6 +2482,10 @@ ftree-vrp >>>> Common Report Var(flag_tree_vrp) Init(0) Optimization >>>> Perform Value Range Propagation on trees. >>>> >>>> +fdisable-tree-evrp >>>> +Common Report Var(flag_disable_early_vrp) Init(0) Optimization >>>> +Disable Early Value Range Propagation on trees. >>>> + >>>> >>>> no please, this is automatically supported via -fdisable- >>> >>> >>> I am now having -ftree-evrp which is enabled all the time. But This will >>> only be used for disabling the early-vrp. That is, early-vrp will be run >>> when ftree-vrp is enabled and ftree-evrp is not explicitly disabled. Is this >>> OK? >> >> Why would one want to disable early-vrp? I see you do this in the testsuite >> for non-early VRP unit-tests but using -fdisable-tree-evrp1 there >> would be ok as well. > > Removed it altogether. I though that you wanted a way to disable > early-vrp for testing purposes. But there is via the generic -fdisable-tree-DUMPFILE way. >>>> >>>> @@ -1728,11 +1736,12 @@ extract_range_from_assert (value_range *vr_p, tree >>>> expr) >>>> always false. */ >>>> >>>> static void >>>> -extract_range_from_ssa_name (value_range *vr, tree var) >>>> +extract_range_from_ssa_name (value_range *vr, bool dom_p, tree var) >>>> { >>>> value_range *var_vr = get_value_range (var); >>>> >>>> - if (var_vr->type != VR_VARYING) >>>> + if (var_vr->type != VR_VARYING >>>> + && (!dom_p || var_vr->type != VR_UNDEFINED)) >>>> copy_value_range (vr, var_vr); >>>> else >>>> set_value_range (vr, VR_RANGE, var, var, NULL); >>>> >>>> why do you need these changes? I think I already told you you need to >>>> initialize the lattice to sth else than VR_UNDEFINED and that you can't >>>> fully re-use update_value_range. If you don't want to do that then >>>> instead >>>> of doing changes all over the place do it in get_value_range and have a >>>> global flag. >>> >>> >>> I have now added a global early_vrp_p and use this to initialize >>> VR_INITIALIZER and get_value_range default to VR_VARYING. >> >> ICK. Ok, I see that this works, but it is quite ugly, so (see below) >> >>>> >>>> >>>> @@ -3594,7 +3643,8 @@ extract_range_from_cond_expr (value_range *vr, >>>> gassign *stmt) >>>> on the range of its operand and the expression code. */ >>>> >>>> static void >>>> -extract_range_from_comparison (value_range *vr, enum tree_code code, >>>> +extract_range_from_comparison (value_range *vr, >>>> + enum tree_code code, >>>> tree type, tree op0, tree op1) >>>> { >>>> bool sop = false; >>>> >>>> remove these kind of no-op changes. >>> >>> >>> Done. >>> >>> >>>> >>>> +/* Initialize local data structures for VRP. If DOM_P is true, >>>> + we will be calling this from early_vrp where value range propagation >>>> + is done by visiting stmts in dominator tree. ssa_propagate engine >>>> + is not used in this case and that part of the ininitialization will >>>> + be skipped. */ >>>> >>>> static void >>>> -vrp_initialize (void) >>>> +vrp_initialize (bool dom_p) >>>> { >>>> basic_block bb; >>>> >>>> @@ -6949,6 +7010,9 @@ vrp_initialize (void) >>>> vr_phi_edge_counts = XCNEWVEC (int, num_ssa_names); >>>> bitmap_obstack_initialize (&vrp_equiv_obstack); >>>> >>>> + if (dom_p) >>>> + return; >>>> + >>>> >>>> split the function instead. >>>> >>>> @@ -7926,7 +7992,8 @@ vrp_visit_switch_stmt (gswitch *stmt, edge >>>> *taken_edge_p) >>>> If STMT produces a varying value, return SSA_PROP_VARYING. */ >>>> >>>> static enum ssa_prop_result >>>> -vrp_visit_stmt (gimple *stmt, edge *taken_edge_p, tree *output_p) >>>> +vrp_visit_stmt_worker (gimple *stmt, bool dom_p, edge *taken_edge_p, >>>> + tree *output_p) >>>> { >>>> tree def; >>>> ssa_op_iter iter; >>>> @@ -7940,7 +8007,7 @@ vrp_visit_stmt (gimple *stmt, edge >>>> *taken_edge_p, tree *output_p) >>>> if (!stmt_interesting_for_vrp (stmt)) >>>> gcc_assert (stmt_ends_bb_p (stmt)); >>>> else if (is_gimple_assign (stmt) || is_gimple_call (stmt)) >>>> - return vrp_visit_assignment_or_call (stmt, output_p); >>>> + return vrp_visit_assignment_or_call (stmt, dom_p, output_p); >>>> else if (gimple_code (stmt) == GIMPLE_COND) >>>> return vrp_visit_cond_stmt (as_a <gcond *> (stmt), taken_edge_p); >>>> else if (gimple_code (stmt) == GIMPLE_SWITCH) >>>> @@ -7954,6 +8021,12 @@ vrp_visit_stmt (gimple *stmt, edge >>>> *taken_edge_p, tree *output_p) >>>> return SSA_PROP_VARYING; >>>> } >>>> >>>> +static enum ssa_prop_result >>>> +vrp_visit_stmt (gimple *stmt, edge *taken_edge_p, tree *output_p) >>>> +{ >>>> + return vrp_visit_stmt_worker (stmt, false, taken_edge_p, output_p); >>>> +} >>>> >>>> as said the refactoring that would be appreciated is to split out the >>>> update_value_range calls >>>> from the worker functions so you can call the respective functions >>>> from the DOM implementations. >>>> That they are globbed in vrp_visit_stmt currently is due to the API of >>>> the SSA propagator. >>> >>> Sent this as separate patch for easy reviewing and testing. >> >> Thanks. >> >>>> >>>> @@ -8768,6 +8842,12 @@ vrp_visit_phi_node (gphi *phi) >>>> fprintf (dump_file, "\n"); >>>> } >>>> >>>> + if (dom_p && vr_arg.type == VR_UNDEFINED) >>>> + { >>>> + set_value_range_to_varying (&vr_result); >>>> + break; >>>> + } >>>> + >>>> >>>> eh... ok, so another way to attack this is, instead of initializing >>>> the lattice to sth else >>>> than VR_UNDEFINED, make sure to drop the lattice to varying for all PHI >>>> args on >>>> yet unvisited incoming edges (you're not doing optimistic VRP). That's >>>> the only >>>> place you _have_ to do it. >>> >>> >>> Even when it is initialize (as I am doing now), we can still end up with >>> VR_UNDEFINED during the propagation. I have just left the above so that we >>> dont end up with the wrong VR. >> >> How would we end up with wrong VRs? I see >> >> + /* Discover VR when condition is true. */ >> + extract_range_for_var_from_comparison_expr (op0, code, op0, op1, &vr); >> + if (old_vr->type == VR_RANGE || old_vr->type == VR_ANTI_RANGE) >> + vrp_intersect_ranges (&vr, old_vr); >> >> where you already disregard UNDEFINED as old_vr. >> >> What you might be missing is to set all DEFs on !stmt_interesting_for_vrp to >> VARYING. Also >> >> + if (stmt_interesting_for_vrp (stmt)) >> + { >> + tree lhs = gimple_get_lhs (stmt); >> + value_range vr = VR_INITIALIZER; >> + vrp_visit_stmt_worker (stmt, &taken_edge, &output, &vr); >> + update_value_range (lhs, &vr); >> + >> + /* Try folding stmts with the VR discovered. */ >> + if (fold_stmt (&gsi, follow_single_use_edges)) >> + update_stmt (gsi_stmt (gsi)); >> >> folding here can introduce additional stmts and thus unvisited SSA defs >> which would end up with VR_UNINITIALIZED defs - I don't see exactly >> where that would cause issues but I'm not sure it might not. So better >> use fold_stmt_inplace or alternatively if fold_stmt returned true then, >> remembering the previous stmt gsi, iterate over all stmts emitted and >> set their defs to varying (or re-visit them). See for example how >> tree-ssa-forwprop.c does this re-visiting (it revisits all changed stmts). > > I am now setting the results of stmts that are not interesting to vrp > to VR_VARYING. > > Also, before visiting PHI, if any of the arguments are undefined, > result of the PHI is also set varying. > > I have removed all the others. This now bootstraps and passes > regressions (see attached patch). > > >> Note that you want to have a custom valueize function instead of just >> follow_single_use_edges as you want to valueize all SSA names according >> to their lattice value (if it has a single value). You can use vrp_valueize >> for this though that gets you non-single-use edge following as well. >> Eventually it's going to be cleaner to do what the SSA propagator does and >> before folding do >> >> did_replace = replace_uses_in (stmt, vrp_valueize); >> if (fold_stmt (&gsi, follow_single_use_edges) >> || did_replace) >> update_stmt (gsi_stmt (gsi)); >> >> exporting replace_uses_in for this is ok. I guess I prefer this for now. > > I also added the above. I noticed that I need > recompute_tree_invariant_for_addr_expr as in ssa_propagate. My initial > implementation also had gimple_purge_all_dead_eh_edges and > fixup_noreturn_call as in ssa_propagat but I thinj that is not needed > as it would be done at the end of the pass. I don't see this being done at the end of the pass. So please re-instantiate that parts. > With this I noticed more stmts are folded before vrp1. This required > me to adjust some testcases. > >> >> Overall this now looks good apart from the folding and the VR_INITIALIZER thing. >> >> You can commit the already approved refactoring changes and combine this >> patch with the struct value_range move, this way I can more easily look into >> issues with the UNDEFINED thing if you can come up with a testcase that >> doesn't work. >> > > I have now committed all the dependent patches. > > Attached patch passes regression and bootstrap except pr33738.C. This > is an unrelated issue as discussed in > https://gcc.gnu.org/ml/gcc-patches/2016-08/msg01386.html > > Is this OK? +/* Initialize local data structures for VRP. If DOM_P is true, + we will be calling this from early_vrp where value range propagation + is done by visiting stmts in dominator tree. ssa_propagate engine + is not used in this case and that part of the ininitialization will + be skipped. */ + +static void +vrp_initialize () comment needs updating now. static void -extract_range_from_phi_node (gphi *phi, value_range *vr_result) +extract_range_from_phi_node (gphi *phi, value_range *vr_result, + bool early_vrp_p) { I don't think you need this changes now that you have stmt_visit_phi_node_in_dom_p guarding its call. +static bool +stmt_visit_phi_node_in_dom_p (gphi *phi) +{ + ssa_op_iter iter; + use_operand_p oprnd; + tree op; + value_range *vr; + FOR_EACH_PHI_ARG (oprnd, phi, iter, SSA_OP_USE) + { + op = USE_FROM_PTR (oprnd); + if (TREE_CODE (op) == SSA_NAME) + { + vr = get_value_range (op); + if (vr->type == VR_UNDEFINED) + return false; + } + } I think this is overly conservative in never allowing UNDEFINED on PHI node args (even if the def was actually visited). I think that the most easy way to improve this bit would be to actually track visited blocks. You already set the EDGE_EXECUTABLE flag on edges so you could clear BB_VISITED on all blocks and set it in the before_dom_children hook (at the end). Then the above can be folded into the PHI visiting: bool has_unvisited_pred = false; FOR_EACH_EDGE (e, ei, bb->preds) if (!(e->src->flags & BB_VISITED)) { has_unvisited_preds = true; break; } + /* Visit PHI stmts and discover any new VRs possible. */ + gimple_stmt_iterator gsi; + for (gphi_iterator gpi = gsi_start_phis (bb); + !gsi_end_p (gpi); gsi_next (&gpi)) + { + gphi *phi = gpi.phi (); + tree lhs = PHI_RESULT (phi); + value_range vr_result = VR_INITIALIZER; + if (! has_unvisived_preds && stmt_interesting_for_vrp (phi) + && stmt_visit_phi_node_in_dom_p (phi)) + extract_range_from_phi_node (phi, &vr_result, true); + else + set_value_range_to_varying (&vr_result); + update_value_range (lhs, &vr_result); + } due to a bug in IRA you need to make sure to un-set BB_VISITED after early-vrp is finished again. + /* Try folding stmts with the VR discovered. */ + bool did_replace = replace_uses_in (stmt, evrp_valueize); + if (fold_stmt (&gsi, follow_single_use_edges) + || did_replace) + update_stmt (gsi_stmt (gsi)); you should be able to re-use vrp_valueize here. + def_operand_p def_p = SINGLE_SSA_DEF_OPERAND (stmt, SSA_OP_DEF); + /* Set the SSA with the value range. */ + if (def_p + && TREE_CODE (DEF_FROM_PTR (def_p)) == SSA_NAME + && INTEGRAL_TYPE_P (TREE_TYPE (DEF_FROM_PTR (def_p)))) + { + tree def = DEF_FROM_PTR (def_p); + unsigned ver = SSA_NAME_VERSION (def); + if ((vr_value[ver]->type == VR_RANGE Use get_value_range () please, not direct access to vr_value. + || vr_value[ver]->type == VR_ANTI_RANGE) + && (TREE_CODE (vr_value[ver]->min) == INTEGER_CST) + && (TREE_CODE (vr_value[ver]->max) == INTEGER_CST)) + set_range_info (def, vr_value[ver]->type, vr_value[ver]->min, + vr_value[ver]->max); + } Otherwise the patch looks good now (with a lot of improvement possibilities of course). Thanks and sorry for the delay, Richard. > Thanks, > Kugan > > >> Thanks, >> Richard. >> >>> I also noticed that g++.dg/warn/pr33738.C testcase is now failing. This is >>> because, with early-vrp setting value range ccp2 is optimizing without >>> issuing a warning. I will look into it. >>> >>> bootstrap and regression testing is in progress. >>> >>> Thanks, >>> Kugan
> + /* Visit PHI stmts and discover any new VRs possible. */ > + gimple_stmt_iterator gsi; > + for (gphi_iterator gpi = gsi_start_phis (bb); > + !gsi_end_p (gpi); gsi_next (&gpi)) > + { > + gphi *phi = gpi.phi (); > + tree lhs = PHI_RESULT (phi); > + value_range vr_result = VR_INITIALIZER; > + if (! has_unvisived_preds > && stmt_interesting_for_vrp (phi) > + && stmt_visit_phi_node_in_dom_p (phi)) > + extract_range_from_phi_node (phi, &vr_result, true); > + else > + set_value_range_to_varying (&vr_result); > + update_value_range (lhs, &vr_result); > + } > > due to a bug in IRA you need to make sure to un-set BB_VISITED after > early-vrp is finished again. How IRA bugs affects early passes? Honza
On September 14, 2016 11:36:16 PM GMT+02:00, Jan Hubicka <hubicka@ucw.cz> wrote: >> + /* Visit PHI stmts and discover any new VRs possible. */ >> + gimple_stmt_iterator gsi; >> + for (gphi_iterator gpi = gsi_start_phis (bb); >> + !gsi_end_p (gpi); gsi_next (&gpi)) >> + { >> + gphi *phi = gpi.phi (); >> + tree lhs = PHI_RESULT (phi); >> + value_range vr_result = VR_INITIALIZER; >> + if (! has_unvisived_preds >> && stmt_interesting_for_vrp (phi) >> + && stmt_visit_phi_node_in_dom_p (phi)) >> + extract_range_from_phi_node (phi, &vr_result, true); >> + else >> + set_value_range_to_varying (&vr_result); >> + update_value_range (lhs, &vr_result); >> + } >> >> due to a bug in IRA you need to make sure to un-set BB_VISITED after >> early-vrp is finished again. >How IRA bugs affects early passes? IRA bogously relies on BB_VISITED being cleared at pass start. Richard. >Honza
On 09/14/2016 11:55 PM, Richard Biener wrote: > On September 14, 2016 11:36:16 PM GMT+02:00, Jan Hubicka <hubicka@ucw.cz> wrote: >>> + /* Visit PHI stmts and discover any new VRs possible. */ >>> + gimple_stmt_iterator gsi; >>> + for (gphi_iterator gpi = gsi_start_phis (bb); >>> + !gsi_end_p (gpi); gsi_next (&gpi)) >>> + { >>> + gphi *phi = gpi.phi (); >>> + tree lhs = PHI_RESULT (phi); >>> + value_range vr_result = VR_INITIALIZER; >>> + if (! has_unvisived_preds >>> && stmt_interesting_for_vrp (phi) >>> + && stmt_visit_phi_node_in_dom_p (phi)) >>> + extract_range_from_phi_node (phi, &vr_result, true); >>> + else >>> + set_value_range_to_varying (&vr_result); >>> + update_value_range (lhs, &vr_result); >>> + } >>> >>> due to a bug in IRA you need to make sure to un-set BB_VISITED after >>> early-vrp is finished again. >> How IRA bugs affects early passes? > > IRA bogously relies on BB_VISITED being cleared at pass start. Seems like IRA ought to be fixed to clear BB_VISITED on every block as part of its initialization. Jeff
On Thu, Sep 15, 2016 at 4:45 PM, Jeff Law <law@redhat.com> wrote: > On 09/14/2016 11:55 PM, Richard Biener wrote: >> >> On September 14, 2016 11:36:16 PM GMT+02:00, Jan Hubicka <hubicka@ucw.cz> >> wrote: >>>> >>>> + /* Visit PHI stmts and discover any new VRs possible. */ >>>> + gimple_stmt_iterator gsi; >>>> + for (gphi_iterator gpi = gsi_start_phis (bb); >>>> + !gsi_end_p (gpi); gsi_next (&gpi)) >>>> + { >>>> + gphi *phi = gpi.phi (); >>>> + tree lhs = PHI_RESULT (phi); >>>> + value_range vr_result = VR_INITIALIZER; >>>> + if (! has_unvisived_preds >>>> && stmt_interesting_for_vrp (phi) >>>> + && stmt_visit_phi_node_in_dom_p (phi)) >>>> + extract_range_from_phi_node (phi, &vr_result, true); >>>> + else >>>> + set_value_range_to_varying (&vr_result); >>>> + update_value_range (lhs, &vr_result); >>>> + } >>>> >>>> due to a bug in IRA you need to make sure to un-set BB_VISITED after >>>> early-vrp is finished again. >>> >>> How IRA bugs affects early passes? >> >> >> IRA bogously relies on BB_VISITED being cleared at pass start. > > Seems like IRA ought to be fixed to clear BB_VISITED on every block as part > of its initialization. Agreed but I didn't find the time to track down an appropriate place to do that. Richard. > Jeff >
diff --git a/gcc/doc/invoke.texi b/gcc/doc/invoke.texi index 1f04501..e00688a5 100644 --- a/gcc/doc/invoke.texi +++ b/gcc/doc/invoke.texi @@ -12433,6 +12433,11 @@ is made by appending @file{.slp} to the source file name. Dump each function after Value Range Propagation (VRP). The file name is made by appending @file{.vrp} to the source file name. +@item early vrp +@opindex fdump-tree-evrp +Dump each function after Early Value Range Propagation (EVRP). The file name +is made by appending @file{.evrp} to the source file name. + @item oaccdevlow @opindex fdump-tree-oaccdevlow Dump each function after applying device-specific OpenACC transformations. diff --git a/gcc/passes.def b/gcc/passes.def index 533157d..9759fed 100644 --- a/gcc/passes.def +++ b/gcc/passes.def @@ -89,6 +89,7 @@ along with GCC; see the file COPYING3. If not see execute TODO_rebuild_alias at this point. */ NEXT_PASS (pass_build_ealias); NEXT_PASS (pass_fre); + NEXT_PASS (pass_early_vrp); NEXT_PASS (pass_merge_phi); NEXT_PASS (pass_dse); NEXT_PASS (pass_cd_dce); diff --git a/gcc/testsuite/g++.dg/tree-ssa/pr31146-2.C b/gcc/testsuite/g++.dg/tree-ssa/pr31146-2.C index 5e09583..cf4ed33 100644 --- a/gcc/testsuite/g++.dg/tree-ssa/pr31146-2.C +++ b/gcc/testsuite/g++.dg/tree-ssa/pr31146-2.C @@ -1,5 +1,5 @@ /* { dg-do compile } */ -/* { dg-options "-O -fdump-tree-forwprop1" } */ +/* { dg-options "-O -fno-tree-vrp -fdump-tree-forwprop1" } */ #include <new> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/evrp1.c b/gcc/testsuite/gcc.dg/tree-ssa/evrp1.c index e69de29..8c6e4e6 100644 --- a/gcc/testsuite/gcc.dg/tree-ssa/evrp1.c +++ b/gcc/testsuite/gcc.dg/tree-ssa/evrp1.c @@ -0,0 +1,13 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-evrp" } */ + +int foo (int i); +int bar (int j) +{ + if (j > 2) + return foo (j + 2); + else + return j; +} + +/* { dg-final { scan-tree-dump "\\\[5, \\+INF" "evrp" } } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/evrp2.c b/gcc/testsuite/gcc.dg/tree-ssa/evrp2.c index e69de29..e6d4235 100644 --- a/gcc/testsuite/gcc.dg/tree-ssa/evrp2.c +++ b/gcc/testsuite/gcc.dg/tree-ssa/evrp2.c @@ -0,0 +1,18 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-evrp" } */ + +int foo (int i); +int bar2 (int j) +{ + if (j > 2) + { + if (j < 7) + return foo (j + 1); + else + return foo (j + 2); + } + return j; +} + + +/* { dg-final { scan-tree-dump "\\\[4, 7\\\]" "evrp" } } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/evrp3.c b/gcc/testsuite/gcc.dg/tree-ssa/evrp3.c index e69de29..1a3bbd5 100644 --- a/gcc/testsuite/gcc.dg/tree-ssa/evrp3.c +++ b/gcc/testsuite/gcc.dg/tree-ssa/evrp3.c @@ -0,0 +1,15 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-evrp" } */ + +int foo (int i); +void bar (int j) +{ + unsigned int i; + for (i = 0; i < 10; ++i) + { + bar (i + 1); + } +} + +/* { dg-final { scan-tree-dump "\\\[1, 10\\\]" "evrp" } } */ + diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr20657.c b/gcc/testsuite/gcc.dg/tree-ssa/pr20657.c index 727ca4c..e678231 100644 --- a/gcc/testsuite/gcc.dg/tree-ssa/pr20657.c +++ b/gcc/testsuite/gcc.dg/tree-ssa/pr20657.c @@ -3,7 +3,7 @@ statement, which was needed to eliminate the second "if" statement. */ /* { dg-do compile } */ -/* { dg-options "-O2 -fno-tree-dominator-opts -fno-tree-fre -fdump-tree-vrp1-details" } */ +/* { dg-options "-O2 -fno-tree-dominator-opts -fno-tree-fre -fdump-tree-evrp" } */ int foo (int a) @@ -14,4 +14,4 @@ foo (int a) return 0; } -/* { dg-final { scan-tree-dump-times "Folding predicate" 1 "vrp1"} } */ +/* { dg-final { scan-tree-dump-times "if" 1 "evrp"} } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr22117.c b/gcc/testsuite/gcc.dg/tree-ssa/pr22117.c index 7efdd63..3a433d6 100644 --- a/gcc/testsuite/gcc.dg/tree-ssa/pr22117.c +++ b/gcc/testsuite/gcc.dg/tree-ssa/pr22117.c @@ -3,7 +3,7 @@ known to be zero after entering the first two "if" statements. */ /* { dg-do compile } */ -/* { dg-options "-O2 -fdump-tree-vrp1" } */ +/* { dg-options "-O2 -fdump-tree-vrp1" } */ void link_error (void); @@ -21,4 +21,4 @@ foo (int *p, int q) } } -/* { dg-final { scan-tree-dump-times "Folding predicate r_.* != 0B to 0" 1 "vrp1" } } */ +/* { dg-final { scan-tree-dump-times "link_error" 0 "vrp1" } } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr25382.c b/gcc/testsuite/gcc.dg/tree-ssa/pr25382.c index dcf9148..c4fda8b 100644 --- a/gcc/testsuite/gcc.dg/tree-ssa/pr25382.c +++ b/gcc/testsuite/gcc.dg/tree-ssa/pr25382.c @@ -3,7 +3,7 @@ Check that VRP now gets ranges from BIT_AND_EXPRs. */ /* { dg-do compile } */ -/* { dg-options "-O2 -fno-tree-ccp -fdump-tree-vrp1" } */ +/* { dg-options "-O2 -fno-tree-ccp -fdump-tree-vrp" } */ int foo (int a) diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr37508.c b/gcc/testsuite/gcc.dg/tree-ssa/pr37508.c index 0963cd9..2ba09af 100644 --- a/gcc/testsuite/gcc.dg/tree-ssa/pr37508.c +++ b/gcc/testsuite/gcc.dg/tree-ssa/pr37508.c @@ -46,4 +46,4 @@ int test4 (struct foo2 *x) return 0; } -/* { dg-final { scan-tree-dump-times "Folding" 2 "vrp1" } } */ +/* { dg-final { scan-tree-dump-times "if" 2 "vrp1" } } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr61839_2.c b/gcc/testsuite/gcc.dg/tree-ssa/pr61839_2.c index ffa00a7..e44dc57 100644 --- a/gcc/testsuite/gcc.dg/tree-ssa/pr61839_2.c +++ b/gcc/testsuite/gcc.dg/tree-ssa/pr61839_2.c @@ -1,6 +1,6 @@ /* PR tree-optimization/61839. */ /* { dg-do compile } */ -/* { dg-options "-O2 -fdump-tree-vrp1" } */ +/* { dg-options "-O2 -fdump-tree-evrp" } */ /* { dg-require-effective-target int32plus } */ __attribute__ ((noinline)) @@ -47,8 +47,8 @@ int bar2 () /* Dont optimize 972195717 / 0 in function foo. */ -/* { dg-final { scan-tree-dump-times "972195717 / _" 1 "vrp1" } } */ +/* { dg-final { scan-tree-dump-times "972195717 / _" 1 "evrp" } } */ /* Dont optimize 972195717 % 0 in function bar. */ -/* { dg-final { scan-tree-dump-times "972195717 % _" 1 "vrp1" } } */ +/* { dg-final { scan-tree-dump-times "972195717 % _" 1 "evrp" } } */ /* Optimize in function bar2. */ -/* { dg-final { scan-tree-dump-times "972195715 % _" 0 "vrp1" } } */ +/* { dg-final { scan-tree-dump-times "972195715 % _" 0 "evrp" } } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr64130.c b/gcc/testsuite/gcc.dg/tree-ssa/pr64130.c index 0b25466..f39bd17 100644 --- a/gcc/testsuite/gcc.dg/tree-ssa/pr64130.c +++ b/gcc/testsuite/gcc.dg/tree-ssa/pr64130.c @@ -1,6 +1,6 @@ /* { dg-do compile } */ -/* { dg-options "-O2 -fdump-tree-vrp1" } */ +/* { dg-options "-O2 -fdump-tree-evrp" } */ int funsigned (unsigned a) { @@ -13,6 +13,6 @@ int funsigned2 (unsigned a) return (-1 * 0x1ffffffffL) / a == 0; } -/* { dg-final { scan-tree-dump ": \\\[2, 8589934591\\\]" "vrp1" } } */ -/* { dg-final { scan-tree-dump ": \\\[-8589934591, -2\\\]" "vrp1" } } */ +/* { dg-final { scan-tree-dump ": \\\[2, 8589934591\\\]" "evrp" } } */ +/* { dg-final { scan-tree-dump ": \\\[-8589934591, -2\\\]" "evrp" } } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp04.c b/gcc/testsuite/gcc.dg/tree-ssa/vrp04.c index 61b7a47..67f8f01 100644 --- a/gcc/testsuite/gcc.dg/tree-ssa/vrp04.c +++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp04.c @@ -10,4 +10,4 @@ foo (int a, int b) return a + b; } -/* { dg-final { scan-tree-dump-times "Folding predicate a_.*to 1" 1 "vrp1" } } */ +/* { dg-final { scan-tree-dump-times "if" 1 "vrp1" } } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp06.c b/gcc/testsuite/gcc.dg/tree-ssa/vrp06.c index cdad534..c4ce170 100644 --- a/gcc/testsuite/gcc.dg/tree-ssa/vrp06.c +++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp06.c @@ -28,6 +28,6 @@ foo (int i, int j, int a) return i + a + j; } -/* { dg-final { scan-tree-dump-times "Folding predicate i_\[0-9\]+.*0 to 0" 1 "vrp1" } } */ -/* { dg-final { scan-tree-dump-times "Folding predicate j_\[0-9\]+.*0 to 1" 1 "vrp1" } } */ +/* { dg-final { scan-tree-dump-times "Folding predicate \[i|j\]_\[0-9\]+.*0 to 0" 1 "vrp1" } } */ +/* { dg-final { scan-tree-dump-times "Folding predicate \[i|j\]_\[0-9\]+.*0 to 1" 1 "vrp1" } } */ /* { dg-final { scan-tree-dump-times "Folding predicate i_\[0-9]+.*j_\[0-9\]+.* to 0" 1 "vrp1" } } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp16.c b/gcc/testsuite/gcc.dg/tree-ssa/vrp16.c index 8f5d5c8..d09f3ae 100644 --- a/gcc/testsuite/gcc.dg/tree-ssa/vrp16.c +++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp16.c @@ -1,5 +1,5 @@ /* { dg-do compile } */ -/* { dg-options "-O2 -fno-tree-fre -fdump-tree-vrp1-details" } */ +/* { dg-options "-O2 -fno-tree-fre -fdump-tree-evrp" } */ extern void abort (void) __attribute__ ((__noreturn__)); @@ -19,5 +19,5 @@ nonlocal_mentioned_p (rtx x) abort (); } -/* { dg-final { scan-tree-dump-times "Folding predicate .*to 0" 1 "vrp1" } } */ +/* { dg-final { scan-tree-dump-times "if" 0 "evrp" } } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp25.c b/gcc/testsuite/gcc.dg/tree-ssa/vrp25.c index cbc4ec3..a49f079 100644 --- a/gcc/testsuite/gcc.dg/tree-ssa/vrp25.c +++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp25.c @@ -1,5 +1,5 @@ /* { dg-do compile } */ -/* { dg-options "-O2 -fno-tree-fre -fdump-tree-vrp1-details" } */ +/* { dg-options "-O2 -fno-tree-fre -fdump-tree-vrp1" } */ extern void abort (); extern void arf (); @@ -49,5 +49,5 @@ L9: /* The second test of (code1 != 53) and the test (D18670 <= 2) are both totally subsumed by earlier tests and thus should be folded away using VRP. */ -/* { dg-final { scan-tree-dump-times "Folding predicate" 2 "vrp1" } } */ +/* { dg-final { scan-tree-dump-times "if" 3 "vrp1" } } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp46.c b/gcc/testsuite/gcc.dg/tree-ssa/vrp46.c index d3c9ed1..5b279a1 100644 --- a/gcc/testsuite/gcc.dg/tree-ssa/vrp46.c +++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp46.c @@ -27,6 +27,5 @@ func_18 ( int t ) } } -/* There should be a single if left. */ -/* { dg-final { scan-tree-dump-times "if" 1 "vrp1" } } */ +/* { dg-final { scan-tree-dump-times "if" 0 "vrp1" } } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp67.c b/gcc/testsuite/gcc.dg/tree-ssa/vrp67.c index ef5e8f9..5155f7b 100644 --- a/gcc/testsuite/gcc.dg/tree-ssa/vrp67.c +++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp67.c @@ -36,4 +36,4 @@ unsigned baz (unsigned i) return i; } -/* { dg-final { scan-tree-dump-times "Folding predicate" 3 "vrp1" } } */ +/* { dg-final { scan-tree-dump-times "if" 3 "vrp1" } } */ diff --git a/gcc/timevar.def b/gcc/timevar.def index 5f12118..8837832 100644 --- a/gcc/timevar.def +++ b/gcc/timevar.def @@ -149,6 +149,7 @@ DEFTIMEVAR (TV_TREE_CFG , "tree CFG construction") DEFTIMEVAR (TV_TREE_CLEANUP_CFG , "tree CFG cleanup") DEFTIMEVAR (TV_TREE_TAIL_MERGE , "tree tail merge") DEFTIMEVAR (TV_TREE_VRP , "tree VRP") +DEFTIMEVAR (TV_TREE_EARLY_VRP , "tree Early VRP") DEFTIMEVAR (TV_TREE_COPY_PROP , "tree copy propagation") DEFTIMEVAR (TV_FIND_REFERENCED_VARS , "tree find ref. vars") DEFTIMEVAR (TV_TREE_PTA , "tree PTA") diff --git a/gcc/tree-pass.h b/gcc/tree-pass.h index c0059de..86d797e 100644 --- a/gcc/tree-pass.h +++ b/gcc/tree-pass.h @@ -440,6 +440,7 @@ extern gimple_opt_pass *make_pass_fre (gcc::context *ctxt); extern gimple_opt_pass *make_pass_check_data_deps (gcc::context *ctxt); extern gimple_opt_pass *make_pass_copy_prop (gcc::context *ctxt); extern gimple_opt_pass *make_pass_isolate_erroneous_paths (gcc::context *ctxt); +extern gimple_opt_pass *make_pass_early_vrp (gcc::context *ctxt); extern gimple_opt_pass *make_pass_vrp (gcc::context *ctxt); extern gimple_opt_pass *make_pass_uncprop (gcc::context *ctxt); extern gimple_opt_pass *make_pass_return_slot (gcc::context *ctxt); diff --git a/gcc/tree-ssa-propagate.c b/gcc/tree-ssa-propagate.c index c8cf078..97cfde5 100644 --- a/gcc/tree-ssa-propagate.c +++ b/gcc/tree-ssa-propagate.c @@ -863,7 +863,7 @@ static struct prop_stats_d prop_stats; /* Replace USE references in statement STMT with the values stored in PROP_VALUE. Return true if at least one reference was replaced. */ -static bool +bool replace_uses_in (gimple *stmt, ssa_prop_get_value_fn get_value) { bool replaced = false; diff --git a/gcc/tree-ssa-propagate.h b/gcc/tree-ssa-propagate.h index 30d66a9..1a96976 100644 --- a/gcc/tree-ssa-propagate.h +++ b/gcc/tree-ssa-propagate.h @@ -84,5 +84,6 @@ extern void propagate_value (use_operand_p, tree); extern void replace_exp (use_operand_p, tree); extern void propagate_tree_value (tree *, tree); extern void propagate_tree_value_into_stmt (gimple_stmt_iterator *, tree); +extern bool replace_uses_in (gimple *stmt, ssa_prop_get_value_fn get_value); #endif /* _TREE_SSA_PROPAGATE_H */ diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c index 86f2a8f..e4d789b 100644 --- a/gcc/tree-vrp.c +++ b/gcc/tree-vrp.c @@ -60,6 +60,7 @@ along with GCC; see the file COPYING3. If not see #include "case-cfn-macros.h" #include "params.h" #include "alloc-pool.h" +#include "domwalk.h" #define VR_INITIALIZER { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL } @@ -1455,44 +1456,17 @@ op_with_boolean_value_range_p (tree op) && integer_onep (vr->max)); } -/* Extract value range information from an ASSERT_EXPR EXPR and store - it in *VR_P. */ +/* Extract value range information for VAR when (OP COND_CODE LIMIT) is + true and store it in *VR_P. */ static void -extract_range_from_assert (value_range *vr_p, tree expr) +extract_range_for_var_from_comparison_expr (tree var, enum tree_code cond_code, + tree op, tree limit, + value_range *vr_p) { - tree var, cond, limit, min, max, type; + tree min, max, type; value_range *limit_vr; - enum tree_code cond_code; - - var = ASSERT_EXPR_VAR (expr); - cond = ASSERT_EXPR_COND (expr); - - gcc_assert (COMPARISON_CLASS_P (cond)); - - /* Find VAR in the ASSERT_EXPR conditional. */ - if (var == TREE_OPERAND (cond, 0) - || TREE_CODE (TREE_OPERAND (cond, 0)) == PLUS_EXPR - || TREE_CODE (TREE_OPERAND (cond, 0)) == NOP_EXPR) - { - /* If the predicate is of the form VAR COMP LIMIT, then we just - take LIMIT from the RHS and use the same comparison code. */ - cond_code = TREE_CODE (cond); - limit = TREE_OPERAND (cond, 1); - cond = TREE_OPERAND (cond, 0); - } - else - { - /* If the predicate is of the form LIMIT COMP VAR, then we need - to flip around the comparison code to create the proper range - for VAR. */ - cond_code = swap_tree_comparison (TREE_CODE (cond)); - limit = TREE_OPERAND (cond, 0); - cond = TREE_OPERAND (cond, 1); - } - limit = avoid_overflow_infinity (limit); - type = TREE_TYPE (var); gcc_assert (limit != var); @@ -1538,15 +1512,15 @@ extract_range_from_assert (value_range *vr_p, tree expr) as well build the range [b_4, +INF] for it. One special case we handle is extracting a range from a range test encoded as (unsigned)var + CST <= limit. */ - if (TREE_CODE (cond) == NOP_EXPR - || TREE_CODE (cond) == PLUS_EXPR) + if (TREE_CODE (op) == NOP_EXPR + || TREE_CODE (op) == PLUS_EXPR) { - if (TREE_CODE (cond) == PLUS_EXPR) + if (TREE_CODE (op) == PLUS_EXPR) { - min = fold_build1 (NEGATE_EXPR, TREE_TYPE (TREE_OPERAND (cond, 1)), - TREE_OPERAND (cond, 1)); + min = fold_build1 (NEGATE_EXPR, TREE_TYPE (TREE_OPERAND (op, 1)), + TREE_OPERAND (op, 1)); max = int_const_binop (PLUS_EXPR, limit, min); - cond = TREE_OPERAND (cond, 0); + op = TREE_OPERAND (op, 0); } else { @@ -1730,6 +1704,41 @@ extract_range_from_assert (value_range *vr_p, tree expr) vrp_intersect_ranges (vr_p, get_value_range (var)); } +/* Extract value range information from an ASSERT_EXPR EXPR and store + it in *VR_P. */ + +static void +extract_range_from_assert (value_range *vr_p, tree expr) +{ + tree var = ASSERT_EXPR_VAR (expr); + tree cond = ASSERT_EXPR_COND (expr); + tree limit, op; + enum tree_code cond_code; + gcc_assert (COMPARISON_CLASS_P (cond)); + + /* Find VAR in the ASSERT_EXPR conditional. */ + if (var == TREE_OPERAND (cond, 0) + || TREE_CODE (TREE_OPERAND (cond, 0)) == PLUS_EXPR + || TREE_CODE (TREE_OPERAND (cond, 0)) == NOP_EXPR) + { + /* If the predicate is of the form VAR COMP LIMIT, then we just + take LIMIT from the RHS and use the same comparison code. */ + cond_code = TREE_CODE (cond); + limit = TREE_OPERAND (cond, 1); + op = TREE_OPERAND (cond, 0); + } + else + { + /* If the predicate is of the form LIMIT COMP VAR, then we need + to flip around the comparison code to create the proper range + for VAR. */ + cond_code = swap_tree_comparison (TREE_CODE (cond)); + limit = TREE_OPERAND (cond, 0); + op = TREE_OPERAND (cond, 1); + } + extract_range_for_var_from_comparison_expr (var, cond_code, op, + limit, vr_p); +} /* Extract range information from SSA name VAR and store it in VR. If VAR has an interesting range, use it. Otherwise, create the @@ -6952,19 +6961,28 @@ stmt_interesting_for_vrp (gimple *stmt) return false; } - -/* Initialize local data structures for VRP. */ +/* Initialize VRP lattice. */ static void -vrp_initialize (void) +vrp_initialize_lattice () { - basic_block bb; - values_propagated = false; num_vr_values = num_ssa_names; vr_value = XCNEWVEC (value_range *, num_vr_values); vr_phi_edge_counts = XCNEWVEC (int, num_ssa_names); bitmap_obstack_initialize (&vrp_equiv_obstack); +} + +/* Initialize local data structures for VRP. If DOM_P is true, + we will be calling this from early_vrp where value range propagation + is done by visiting stmts in dominator tree. ssa_propagate engine + is not used in this case and that part of the ininitialization will + be skipped. */ + +static void +vrp_initialize () +{ + basic_block bb; FOR_EACH_BB_FN (bb, cfun) { @@ -8698,7 +8716,8 @@ vrp_meet (value_range *vr0, const value_range *vr1) value ranges, set a new range in VR_RESULT. */ static void -extract_range_from_phi_node (gphi *phi, value_range *vr_result) +extract_range_from_phi_node (gphi *phi, value_range *vr_result, + bool early_vrp_p) { size_t i; tree lhs = PHI_RESULT (phi); @@ -8821,6 +8840,7 @@ extract_range_from_phi_node (gphi *phi, value_range *vr_result) use the updated range and iterate one more time. If we will not simulate this PHI again via the backedge allow us to iterate. */ if (edges > 0 + && !early_vrp_p && gimple_phi_num_args (phi) > 1 && edges == old_edges && lhs_vr->type != VR_UNDEFINED @@ -8888,7 +8908,8 @@ scev_check: scev_check can be reached from two paths, one is a fall through from above "varying" label, the other is direct goto from code block which tries to avoid infinite simulation. */ - if ((l = loop_containing_stmt (phi)) + if (!early_vrp_p + && (l = loop_containing_stmt (phi)) && l->header == gimple_bb (phi)) adjust_range_with_scev (vr_result, l, phi, lhs); @@ -8918,7 +8939,7 @@ vrp_visit_phi_node (gphi *phi) { tree lhs = PHI_RESULT (phi); value_range vr_result = VR_INITIALIZER; - extract_range_from_phi_node (phi, &vr_result); + extract_range_from_phi_node (phi, &vr_result, false); if (update_value_range (lhs, &vr_result)) { if (dump_file && (dump_flags & TDF_DETAILS)) @@ -10505,6 +10526,22 @@ finalize_jump_threads (void) delete equiv_stack; } +/* Free VRP lattice. */ + +static void +vrp_free_lattice () +{ + /* Free allocated memory. */ + free (vr_value); + free (vr_phi_edge_counts); + bitmap_obstack_release (&vrp_equiv_obstack); + vrp_value_range_pool.release (); + + /* So that we can distinguish between VRP data being available + and not available. */ + vr_value = NULL; + vr_phi_edge_counts = NULL; +} /* Traverse all the blocks folding conditionals with known ranges. */ @@ -10551,17 +10588,271 @@ vrp_finalize (bool warn_array_bounds_p) /* We must identify jump threading opportunities before we release the datastructures built by VRP. */ identify_jump_threads (); +} - /* Free allocated memory. */ - free (vr_value); - free (vr_phi_edge_counts); - bitmap_obstack_release (&vrp_equiv_obstack); - vrp_value_range_pool.release (); +/* Check to see if the PHI stmt has any back edges taht is not visited yet + (Circular dependancy). In dominator based VRP, if we have back-edges, + we will have SSA_NAME operands with VR_UNDEFINED value range. */ - /* So that we can distinguish between VRP data being available - and not available. */ - vr_value = NULL; - vr_phi_edge_counts = NULL; +static bool +stmt_visit_phi_node_in_dom_p (gphi *phi) +{ + ssa_op_iter iter; + use_operand_p oprnd; + tree op; + value_range *vr; + FOR_EACH_PHI_ARG (oprnd, phi, iter, SSA_OP_USE) + { + op = USE_FROM_PTR (oprnd); + if (TREE_CODE (op) == SSA_NAME) + { + vr = get_value_range (op); + if (vr->type == VR_UNDEFINED) + return false; + } + } + return true; +} + +/* evrp_dom_walker visits the basic blocks in the dominance order and set + the Value Ranges (VR) for SSA_NAMEs in the scope. Use this VR to + discover more VRs. */ + +class evrp_dom_walker : public dom_walker +{ +public: + evrp_dom_walker () + : dom_walker (CDI_DOMINATORS), stack (10) {} + virtual edge before_dom_children (basic_block); + virtual void after_dom_children (basic_block); + void push_value_range (const_tree var, value_range *vr); + value_range *pop_value_range (const_tree var); + + /* Cond_stack holds the old VR. */ + auto_vec<std::pair <const_tree, value_range*> > stack; +}; + +/* Return the singleton value-range for NAME or NAME. */ + +static inline tree +evrp_valueize (tree name) +{ + if (TREE_CODE (name) == SSA_NAME) + { + value_range *vr = get_value_range (name); + if (vr->type == VR_RANGE + && (range_int_cst_p (vr) + || (TREE_CODE (vr->min) == SSA_NAME)) + && vrp_operand_equal_p (vr->min, vr->max)) + return vr->min; + } + return name; +} + +/* See if there is any new scope is entered with new VR and set that VR to + ssa_name before visiting the statements in the scope. */ + +edge +evrp_dom_walker::before_dom_children (basic_block bb) +{ + value_range *new_vr = NULL; + tree op0 = NULL_TREE; + push_value_range (NULL_TREE, NULL); + if (single_pred_p (bb)) + { + edge e = single_pred_edge (bb); + value_range vr = VR_INITIALIZER; + gimple *stmt = last_stmt (e->src); + if (stmt + && gimple_code (stmt) == GIMPLE_COND + && (op0 = gimple_cond_lhs (stmt)) + && TREE_CODE (op0) == SSA_NAME + && INTEGRAL_TYPE_P (TREE_TYPE (gimple_cond_lhs (stmt)))) + { + /* Entering a new scope. Try to see if we can find a VR + here. */ + tree op1 = gimple_cond_rhs (stmt); + tree_code code = gimple_cond_code (stmt); + value_range *old_vr = get_value_range (op0); + + if (TREE_OVERFLOW_P (op1)) + op1 = drop_tree_overflow (op1); + + /* If condition is false, invert the cond. */ + if (e->flags & EDGE_FALSE_VALUE) + code = invert_tree_comparison (gimple_cond_code (stmt), + HONOR_NANS (op0)); + /* Discover VR when condition is true. */ + extract_range_for_var_from_comparison_expr (op0, code, op0, op1, &vr); + if (old_vr->type == VR_RANGE || old_vr->type == VR_ANTI_RANGE) + vrp_intersect_ranges (&vr, old_vr); + + /* If we found any usable VR, set the VR to ssa_name and create a + PUSH old value in the stack with the old VR. */ + if (vr.type == VR_RANGE || vr.type == VR_ANTI_RANGE) + { + new_vr = vrp_value_range_pool.allocate (); + *new_vr = vr; + push_value_range (op0, new_vr); + } + } + } + + /* Visit PHI stmts and discover any new VRs possible. */ + gimple_stmt_iterator gsi; + for (gphi_iterator gpi = gsi_start_phis (bb); + !gsi_end_p (gpi); gsi_next (&gpi)) + { + gphi *phi = gpi.phi (); + tree lhs = PHI_RESULT (phi); + value_range vr_result = VR_INITIALIZER; + if (stmt_interesting_for_vrp (phi) + && stmt_visit_phi_node_in_dom_p (phi)) + extract_range_from_phi_node (phi, &vr_result, true); + else + set_value_range_to_varying (&vr_result); + update_value_range (lhs, &vr_result); + } + + /* Visit all other stmts and discover any new VRs possible. */ + for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) + { + gimple *stmt = gsi_stmt (gsi); + edge taken_edge; + tree output = NULL_TREE; + /* TODO, if found taken_edge, we should visit (return it) and travel + again to improve VR as done in DOM/SCCVN optimizations. It should + be done carefully as stmts might prematurely leave a BB like + in EH. */ + if (stmt_interesting_for_vrp (stmt)) + { + value_range vr = VR_INITIALIZER; + extract_range_from_stmt (stmt, &taken_edge, &output, &vr); + if (output) + update_value_range (output, &vr); + + /* Try folding stmts with the VR discovered. */ + bool did_replace = replace_uses_in (stmt, evrp_valueize); + if (fold_stmt (&gsi, follow_single_use_edges) + || did_replace) + update_stmt (gsi_stmt (gsi)); + + if (did_replace + && gimple_assign_single_p (stmt)) + { + tree rhs = gimple_assign_rhs1 (stmt); + + if (TREE_CODE (rhs) == ADDR_EXPR) + recompute_tree_invariant_for_addr_expr (rhs); + } + + def_operand_p def_p = SINGLE_SSA_DEF_OPERAND (stmt, SSA_OP_DEF); + /* Set the SSA with the value range. */ + if (def_p + && TREE_CODE (DEF_FROM_PTR (def_p)) == SSA_NAME + && INTEGRAL_TYPE_P (TREE_TYPE (DEF_FROM_PTR (def_p)))) + { + tree def = DEF_FROM_PTR (def_p); + unsigned ver = SSA_NAME_VERSION (def); + if ((vr_value[ver]->type == VR_RANGE + || vr_value[ver]->type == VR_ANTI_RANGE) + && (TREE_CODE (vr_value[ver]->min) == INTEGER_CST) + && (TREE_CODE (vr_value[ver]->max) == INTEGER_CST)) + set_range_info (def, vr_value[ver]->type, vr_value[ver]->min, + vr_value[ver]->max); + } + } + else + { + tree def; + ssa_op_iter iter; + FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF) + set_value_range_to_varying (get_value_range (def)); + } + } + return NULL; +} + +/* Restore/pop VRs valid only for BB when we leave BB. */ + +void +evrp_dom_walker::after_dom_children (basic_block bb ATTRIBUTE_UNUSED) +{ + gcc_checking_assert (!stack.is_empty ()); + while (stack.last ().first != NULL_TREE) + pop_value_range (stack.last ().first); + pop_value_range (stack.last ().first); +} + +/* Push the Value Range of VAR to the stack and update it with new VR. */ + +void +evrp_dom_walker::push_value_range (const_tree var, value_range *vr) +{ + if (vr != NULL) + { + unsigned ver = SSA_NAME_VERSION (var); + gcc_checking_assert (vr_value); + stack.safe_push (std::make_pair (var, vr_value[ver])); + + if (ver < num_vr_values) + vr_value[ver] = vr; + } + else + stack.safe_push (std::make_pair (var, vr)); +} + +/* Pop the Value Range from the vrp_stack and update VAR with it. */ + +value_range * +evrp_dom_walker::pop_value_range (const_tree var) +{ + value_range *vr = stack.last ().second; + if (vr != NULL) + { + unsigned ver = SSA_NAME_VERSION (var); + gcc_checking_assert (var == stack.last ().first); + gcc_checking_assert (vr_value); + + if (ver < num_vr_values) + vr_value[ver] = vr; + } + stack.pop (); + return vr; +} + + +/* Main entry point for the early vrp pass which is a simplified non-iterative + version of VRP where basic blocks are visited in dominance order. Value + ranges discovered in early vrp will also be used by ipa-vrp. */ + +static unsigned int +execute_early_vrp () +{ + edge e; + edge_iterator ei; + basic_block bb; + + calculate_dominance_info (CDI_DOMINATORS); + FOR_EACH_BB_FN (bb, cfun) + { + FOR_EACH_EDGE (e, ei, bb->preds) + e->flags |= EDGE_EXECUTABLE; + } + vrp_initialize_lattice (); + + /* Walk stmts in dominance order and propagate VRP. */ + evrp_dom_walker walker; + walker.walk (ENTRY_BLOCK_PTR_FOR_FN (cfun)); + + if (dump_file) + { + fprintf (dump_file, "\nValue ranges after Early VRP:\n\n"); + dump_all_value_ranges (dump_file); + fprintf (dump_file, "\n"); + } + vrp_free_lattice (); + return 0; } @@ -10632,9 +10923,11 @@ execute_vrp (bool warn_array_bounds_p) /* For visiting PHI nodes we need EDGE_DFS_BACK computed. */ mark_dfs_back_edges (); + vrp_initialize_lattice (); vrp_initialize (); ssa_propagate (vrp_visit_stmt, vrp_visit_phi_node); vrp_finalize (warn_array_bounds_p); + vrp_free_lattice (); free_numbers_of_iterations_estimates (cfun); @@ -10732,3 +11025,44 @@ make_pass_vrp (gcc::context *ctxt) { return new pass_vrp (ctxt); } + +namespace { + +const pass_data pass_data_early_vrp = +{ + GIMPLE_PASS, /* type */ + "evrp", /* name */ + OPTGROUP_NONE, /* optinfo_flags */ + TV_TREE_EARLY_VRP, /* tv_id */ + PROP_ssa, /* properties_required */ + 0, /* properties_provided */ + 0, /* properties_destroyed */ + 0, /* todo_flags_start */ + ( TODO_cleanup_cfg | TODO_update_ssa | TODO_verify_all ), +}; + +class pass_early_vrp : public gimple_opt_pass +{ +public: + pass_early_vrp (gcc::context *ctxt) + : gimple_opt_pass (pass_data_early_vrp, ctxt) + {} + + /* opt_pass methods: */ + opt_pass * clone () { return new pass_early_vrp (m_ctxt); } + virtual bool gate (function *) + { + return flag_tree_vrp != 0; + } + virtual unsigned int execute (function *) + { return execute_early_vrp (); } + +}; // class pass_vrp +} // anon namespace + +gimple_opt_pass * +make_pass_early_vrp (gcc::context *ctxt) +{ + return new pass_early_vrp (ctxt); +} +