[RFC,IPA-VRP] Early VRP Implementation

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

[RFC,IPA-VRP] Early VRP Implementation

Commit Message

Comments

Patch