[RFC,IPA-VRP] Early VRP Implementation

Hi Richard,

Thanks for the review.

On 14/09/16 22:04, Richard Biener wrote:
> 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,

>>>> 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.

OK. I didnt know about that.

>>> 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.

I have copied these part as well.

>> 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.
>
Done.

>
>  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.

OK removed it. That also mean I had to put scev_* in the early_vrp.

> +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;
>          }
>
OK done.

I also had to check for uninitialized variables that will have 
VR_UNDEFINED as range. We do not visit GIMPLE_NOP.

> +  /* 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.
OK. Done.

>
> +         /* 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.
This issue is vrp_valueize accepts ranges such as [VAR + CST, VAR + CST] 
which we can not set.

>
> +         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.
>
Done.

> +                  || 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).
I will work on the improvement after this goes in.

Bootstrapped and regression tested on x86_64-linux-gnu. Does this looks OK?

Thanks,
Kugan

>
> 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

[RFC,IPA-VRP] Early VRP Implementation

Commit Message

Patch