[RFC,IPA-VRP] Early VRP Implementation

Hi Riachard,

Thanks for the review. Here is an updated patch with comments below.

> +/* Restore/Pop all the old VRs maintained in the cond_stack.  */
> +
> +void evrp_dom_walker::finalize_dom_walker ()
> +{
> +  while (!cond_stack.is_empty ())
> +    {
> +      tree var = cond_stack.last ().second;
> +      pop_value_range (var);
> +      cond_stack.pop ();
> +    }
>
> why is this necessary at all?  Looks like a waste of time (and the
> stack should be empty here
> anyway).  I think you leak cond_stack as well, I suppose using
> auto_vec might work here,
> you have to check.
Done.

>
>>>
>>> +         /* Discover VR when condition is true.  */
>>> +         if (te == e
>>> +             && !TREE_OVERFLOW_P (op0)
>>> +             && !TREE_OVERFLOW_P (op1))
>>
>>
>> This is mainly to handle gcc.dg/pr38934.c. This would result in ICE from
>> set_value_range otherwise:
>>
>> gcc_assert ((!TREE_OVERFLOW_P (min) || is_overflow_infinity (min))
>>                   && (!TREE_OVERFLOW_P (max) || is_overflow_infinity
>> (max)));
>
> Ok, instead make sure to remove the overflow flag via
>
>   if (TREE_OVERFLOW_P (op0))
>     op0 = drop_tree_overflow (op0);
  ...
Done.

>
> it looks like you want to merge the if ( & EDGE_TRUE_VALUE) and FALSE_VALUE
> cases and only invert the tree comparison for the false edge.
Done.

>
> +             tree cond = build2 (code, boolean_type_node, op0, op1);
> +             extract_range_for_var_from_comparison_expr (&vr, op0, cond);
>
> no wasteful tree building here please.  Instead of cond pass in code,
> op0 and op1
> as separate arguments.
Done.

>
> +         /* If we found any usable VR, set the VR to ssa_name and create a
> +            PUSH old value in the cond_stack with the old VR.  */
> +         if (vr.type == VR_RANGE || vr.type == VR_ANTI_RANGE)
> +           {
> +             value_range *new_vr = vrp_value_range_pool.allocate ();
> +             memset (new_vr, 0, sizeof (*new_vr));
> +             *new_vr = vr;
> +             cond_stack.safe_push (std::make_pair (bb, op0));
>
> the memset looks redundant given you copy-assing from vr anyway.
Done.

>
> You seem to miss the chance to register ranges for x_2 in i_1 < x_2 where
> both i_1 and x_2 might have ranges that are useful.
I will address this once the basic structure is in place if that is OK 
with you.

>
> push and pop_value_range should be methods in the dom walker class
> and vrp_stack and cond_stack should be a single stack.  You can omit
> basic_block if you use a "magic" NULL_TREE var as marker (simply
> push a NULL_TREE, NULL pair at the end of before_dom_children).
>
Done.

>>>
>>> you can use e->flags & EDGE_TRUE_VALUE/EDGE_FALSE_VALUE
>>>
>>> why do you need those TREE_OVERFLOW checks?
>>>
>>> +             tree cond = build2 (code, boolean_type_node, op0, op1);
>>> +             tree a = build2 (ASSERT_EXPR, TREE_TYPE (op0), op0, cond);
>>> +             extract_range_from_assert (&vr, a);
>>>
>>> so I was hoping that the "refactoring" patch in the series would expose a
>>> more
>>> useful interface than extract_range_from_assert ... namely one that can
>>> extract a range from the comparison directly and does not require building
>>> a scratch ASSERT_EXPR.
>>
>>
>> I have split extract_range_from_assert into
>> extract_range_for_var_from_comparison_expr and using it now. Is that better?
>
> See above.
>
>>>
>>>
>>> +         /* If we found any usable VR, set the VR to ssa_name and create
>>> a
>>> +            restore point in the cond_stack with the  old VR. */
>>> +         if (vr.type == VR_RANGE || vr.type == VR_ANTI_RANGE)
>>> +           {
>>> +             value_range *new_vr = XCNEW (value_range);
>>> +             *new_vr = vr;
>>> +             cond_stack.safe_push (std::make_pair (bb,
>>> +                                                   std::make_pair (op0,
>>> +
>>> old_vr)));
>>> +             change_value_range (op0, new_vr);
>>>
>>> I don't like 'change_value_range' as interface, please integrate that into
>>> a push/pop_value_range style interface instead.
>>
>>
>> Tried using push/pop interface.
>>>
>>>
>>> +       vrp_visit_stmt (stmt, &taken_edge_p, &output_p);
>>> +    }
>>> +
>>> +  return NULL;
>>>
>>> you should return taken_edge_p (misnamed as it isn't a pointer) and take
>>> advantage of EDGE_EXECUTABLE.  Again see DOM/SCCVN (might want to
>>> defer this as a followup improvement).
>>
>>
>> I have added a TODO to this effect and will comeback to it.
>>>
>>>
>>> Note that the advantage of a DOM-based VRP is that backtracking is easy
>>> to implement (you don't do that yet).  That is, after DEF got a (better)
>>> value-range you can simply re-visit all the defs of its uses (and
>>> recursively).
>>> I think you have to be careful with stmts that might prematurely leave a
>>> BB
>>> though (like via EH).  So sth for a followup as well.
>>
>>
>> Is this OK now. Bootstrapped and regression tested on x86_64-linux  with no
>> new regressions.
>
> Better, still not perfect.
>
> I'm also arguing on the pass placement now - you put it where it may make sense
> for IPA VRP (but then IPA VRP could simply do this in its analysis phase) but
> not so much where it makes sense during the early pipeline.  I think it makes
> sense after FRE.
>
> Looking at how you finalize I see several issues with simply re-using
> vrp_finalize.
>
> First of all the loop doing the set_range_info will turn up with
> nothing as you've
> popped off all value-ranges from the lattice.  Same for substitute-and-fold (or
> jump-threading).
I am not sure understanding you. I am poping the value ranges for scope 
when we leave them. Other value ranges which lives in all the regions 
will remain.

>
> What you instead need to do with the DOM scheme is at the point you
> call vrp_visit_stmt do sth like
>
>      vrp_visit_stmt (....);
>      if (fold_stmt (&gsi, follow_single_use_edges))
>        update_stmt ();
I have added this. I think this will be good as we would be able to 
optimize with value ranges that is valid within the scope.

>      tree def = SINGLE_SSA_DEF_OPERAND (stmt, SSA_OP_DEF);
>      if (def
>          && INTEGRAL_TYPE_P (TREE_TYPE (def))
>          && (TREE_CODE (vr_value[i]->min) == INTEGER_CST)
>           && (TREE_CODE (vr_value[i]->max) == INTEGER_CST)
>           && (vr_value[i]->type == VR_RANGE
>               || vr_value[i]->type == VR_ANTI_RANGE))
>         set_range_info (name, vr_value[i]->type, vr_value[i]->min,
>                         vr_value[i]->max);
>
I am not sure if this is needed. I dont know if my push/pop value range 
implementation is not what you wanted. If you still prefer, I am happy 
to add this.

> thus please split vrp_finalize into two parts, one of it with the memory
> freeing which is the one you'd call.
>
> Note that EVRP is not enabled by default at any optimization level
> it seems so bootstrap / test of it would be useless (did you only
> test with the full series?  I never looked at the IPA VRP part)
>
I have:

+ftree-evrp
+Common Report Var(flag_tree_early_vrp) Init(1) Optimization
+Perform Early Value Range Propagation on trees.

I would like to run this only for -O2 and above but for now I am using 
this to test.

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

[RFC,IPA-VRP] Early VRP Implementation

Commit Message

Comments

Patch