Hi Richard,

Thanks for the review.

On 28/07/16 21:34, Richard Biener wrote:
> 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 ;)
>


Here is an updated patch which addresses the earlier review comments.

Just to see the effectiveness of this, I did a simple test.

That is, I built gcc with --enable-languages=c,c++ --disable-bootstrap 
--disable-multilib and added -fdump-ipa-cp to the compiler flag and 
grepped for number of times ipa-vrp (with the ipa-vrp patch) is setting 
the value range for argument. I also did the same with tree-vrp used in 
place of tree-evrp as an early vrp. tree-evrp is setting 186 times 
compared to tree-vrp which is setting 207 times. I didn't see the actual 
value ranges which can also make lots of difference.

In future we might want to iterate on dom based vrp till fixed point is 
reached if there is a need.

Thanks,
Kugan