Re: [RFC][IPA-VRP] Early VRP Implementation

[kugan <kugan.vivekanandarajah@linaro.org>]

Hi Richard,

Thanks for the review.
>
> It seems that in your pop_value_range you assume you only pop one
> range per BB - while that's likely true at the moment it will be a limitation
> in the future.  You want to pop ranges until you hit the NULL marker
> in after_dom_children and unconditionally push a NULL marker.
>
I understand. Right now, I am adding only one assert based on the 
condition. But in future, we will be adding more so this is needed. I 
will do that.

> For example to match current VRPs behavior on say
>
>    i_2 = (int) j_3;
>    if (i_2 < 0)
>      ...
>
> which can register an assert for j_3 when i_2 < 0 is true we'd do that
> by re-simulating DEFs of uses we figured out new ranges of (and all
> their uses).  All those ranges would be temporary as well, thus they'd
> need to be pushed/popped.  In my quick prototype this was done
> using a worklist seeded by the names we can derive a range from from
> conditionals and "SSA propagating" from it.  Note that for this
> the generic vrp_visit_stmt cannot be re-used as it doesn't push/pop,
> factoring out the lattice update is what is needed here.
>

I dont think I understand this part. vrp_visit_stmt is going to add 
value ranges for the variables defined in the if-block (in the example 
below it is for t). If we push the value range for i_2 and j_3 when we 
enter if-block, vrp_visit_stmt should compute "t" correctly. When we 
leave the if-block, we will pop i_2 and j_3.

     i_2 = (int) j_3;
     if (i_2 < 0)
     {
       t = j_2 * 2;	
     }
Am I missing something here?

> +/* Visit 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.  Restore the
> +   old VR once the scope is exited.  */
> +
> +static bool
> +evrp_visit_phi_node_local (gphi *phi)
> +{
> +  size_t i;
> +  tree lhs = PHI_RESULT (phi);
> +  value_range vr_result = VR_INITIALIZER;
> +  bool first = true;
> +  int edges;
> +
> +  edges = 0;
> +  for (i = 0; i < gimple_phi_num_args (phi); i++)
> +    {
> +      edge e = gimple_phi_arg_edge (phi, i);
> +      tree arg = PHI_ARG_DEF (phi, i);
> +      value_range vr_arg = VR_INITIALIZER;
> +      ++edges;
> +
> +      /* If there is a back-edge, set the result to VARYING.  */
> +      if (e->flags & (EDGE_DFS_BACK | EDGE_COMPLEX))
> +       {
> +         set_value_range_to_varying (&vr_result);
> +         break;
> +       }
> ...
> +      /* If any of the RHS value is VARYING, set the result to VARYING.  */
> +      if ((vr_arg.type != VR_RANGE)
> +         && (vr_arg.type != VR_ANTI_RANGE))
> +       {
> +         set_value_range_to_varying (&vr_result);
> +         break;
> +       }
>
> this shows that you need to start conservative for a DOM based VRP,
> thus with all lattice values initialized to VARYING (but undefined SSA
> names of course still can be UNDEFINED) rather than UNDEFINED.
>
> +      if (TREE_CODE (arg) == SSA_NAME)
> +       vr_arg = *(get_value_range (arg));
> +      else
> +       set_value_range_to_varying (&vr_arg);
>
> err - what about constants?  When you initialize the lattice properly
> you should be able to re-use vrp_visit_phi_node (maybe split out
> its head to avoid using SCEV or the iteration limitation).

I also like re-using vrp_visit_phi_node but the issue is, we will have 
to keep a work-list of nodes to be re-evaluated till the lattice reach a 
fixpoint. Is that OK with you?

If we are to do this, we should be able to reuse the callbacks 
vrp_visit_phi_node and vrp_visit_stmt as it is.

Do you have a reference to your DOM based prototype?

Thanks,
Kugan

> Btw, you don't want to call vrp_initialize in evrp either, this is setting
> SSA propagator state which you do not want to do.  Please factor
> out lattice allocation/deallocation instead.  I see that might require
> really factoring vrp_visit_stmt into a function that omits updating
> the lattice and just returns a range for the single DEF.
>
> That said, a good refactoring is to split the SSA propagator callback
> implementations (vrp_visit_stmt and vrp_visit_phi_node) into workers
> returning a value range and the callback that does the update_value_range
> call plus returing a SSA propgator state.  You can then re-use the worker.
>
> Thanks,
> Richard.
>
>> I  have tested the last set of patch separately.
>>
>> I will do more testing on this patch based on your feedback. Does this look
>> better?
>>
>> Thanks,
>> Kugan
>>
>>