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

[Richard Biener <richard.guenther@gmail.com>]

On Thu, Jul 28, 2016 at 9:35 AM, kugan
<kugan.vivekanandarajah@linaro.org> wrote:
> 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?

It works if you push the old value before calling vrp_visit_stmt, yes.
But I think
you want to do that only if the value-range changed to avoid too many changes
on the stack.  I guess we can defer further refactoring and
optimization of this case
to the point where we consider looking back very aggressively.

>> +/* 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?

No, why would you need to iterate here?  As said, the key point is to
initialize value-ranges as VARYING rather than UNDEFINED.

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

I never posted it I think, it's structure is similar to yours with lots
of ??? comments ;)

Richard.

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