This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: [RFC][VRP] Improve intersect_ranges


On Wed, Oct 12, 2016 at 8:35 AM, kugan
<kugan.vivekanandarajah@linaro.org> wrote:
> Hi Richard,
>
>
> On 12/10/16 00:14, Richard Biener wrote:
>>
>> On Tue, Oct 11, 2016 at 2:57 AM, kugan
>> <kugan.vivekanandarajah@linaro.org> wrote:
>>>
>>> Hi Richard,
>>> Hi Richard,
>>>
>>> On 10/10/16 20:13, Richard Biener wrote:
>>>>
>>>>
>>>> On Sat, Oct 8, 2016 at 9:38 PM, kugan
>>>> <kugan.vivekanandarajah@linaro.org>
>>>> wrote:
>>>>>
>>>>>
>>>>> Hi Richard,
>>>>>
>>>>> Thanks for the review.
>>>>> On 07/10/16 20:11, Richard Biener wrote:
>>>>>>
>>>>>>
>>>>>>
>>>>>> On Fri, Oct 7, 2016 at 12:00 AM, kugan
>>>>>> <kugan.vivekanandarajah@linaro.org> wrote:
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>> Hi,
>>>>>>>
>>>>>>> In vrp intersect_ranges, Richard recently changed it to create
>>>>>>> integer
>>>>>>> value
>>>>>>> ranges when it is integer singleton.
>>>>>>>
>>>>>>> Maybe we should do the same when the other range is a complex ranges
>>>>>>> with
>>>>>>> SSA_NAME (like [x+2, +INF])?
>>>>>>>
>>>>>>> Attached patch tries to do this. There are cases where it will be
>>>>>>> beneficial
>>>>>>> as the  testcase in the patch. (For this testcase to work with Early
>>>>>>> VRP,
>>>>>>> we
>>>>>>> need the patch posted at
>>>>>>> https://gcc.gnu.org/ml/gcc-patches/2016-10/msg00413.html)
>>>>>>>
>>>>>>> Bootstrapped and regression tested on x86_64-linux-gnu with no new
>>>>>>> regressions.
>>>>>>
>>>>>>
>>>>>>
>>>>>>
>>>>>> This is not clearly a win, in fact it can completely lose an
>>>>>> ASSERT_EXPR
>>>>>> because there is no way to add its effect back as an equivalence.  The
>>>>>> current choice of always using the "left" keeps the ASSERT_EXPR range
>>>>>> and is able to record the other range via an equivalence.
>>>>>
>>>>>
>>>>>
>>>>>
>>>>> How about changing the order in Early VRP when we are dealing with the
>>>>> same
>>>>> SSA_NAME in inner and outer scope. Here is a patch that does this. Is
>>>>> this
>>>>> OK if no new regressions?
>>>>
>>>>
>>>>
>>>> I'm not sure if this is a good way forward.  The failure with the
>>>> testcase
>>>> is
>>>> that we don't extract a range for k from if (j < k) which I believe
>>>> another
>>>> patch from you addresses?
>>>
>>>
>>>
>>> Yes,  I have committed that. I am trying to add test cases for this and
>>> thats when I stumbled on this:
>>>
>>> For:
>>> foo (int k, int j)
>>> {
>>>    <bb 2>:
>>>    if (j_1(D) > 9)
>>>      goto <bb 3>;
>>>    else
>>>      goto <bb 6>;
>>>
>>>    <bb 3>:
>>>    if (j_1(D) < k_2(D))
>>>      goto <bb 4>;
>>>    else
>>>      goto <bb 6>;
>>>
>>>    <bb 4>:
>>>    k_3 = k_2(D) + 1;
>>>    if (k_2(D) <= 8)
>>>      goto <bb 5>;
>>>    else
>>>      goto <bb 6>;
>>>
>>>    <bb 5>:
>>>    abort ();
>>>
>>>    <bb 6>:
>>>    return j_1(D);
>>>
>>> }
>>>
>>> Before we look at - if (j_1(D) < k_2(D))
>>> j_1 (D) has [10, +INF]  EQUIVALENCES: { j_1(D) } (1 elements)
>>>
>>> When we look at  if (j_1(D) < k_2(D))
>>> The range is [-INF, k_2(D) + -1]  EQUIVALENCES: { j_1(D) } (1 elements)
>>>
>>> We intersect:
>>> [-INF, k_2(D) + -1]  EQUIVALENCES: { j_1(D) } (1 elements)
>>> and
>>> [10, +INF]  EQUIVALENCES: { j_1(D) } (1 elements)
>>>
>>> to
>>> [-INF, k_2(D) + -1]  EQUIVALENCES: { j_1(D) } (1 elements)
>>>
>>> Due to this, in if (j_1(D) < k_2(D)) , we get pessimistic value range for
>>> k_2(D)
>>
>>
>> Ah, but that is because when generating the range for k from j < k we
>> use the updated range for j.  That obviously doens't make too much sense.
>>
>> @@ -10650,7 +10661,7 @@ public:
>>    virtual void after_dom_children (basic_block);
>>    void push_value_range (const_tree var, value_range *vr);
>>    value_range *pop_value_range (const_tree var);
>> -  void try_add_new_range (tree op, tree_code code, tree limit);
>> +  value_range *try_add_new_range (tree op, tree_code code, tree limit);
>>
>>    /* Cond_stack holds the old VR.  */
>>    auto_vec<std::pair <const_tree, value_range*> > stack;
>> @@ -10661,7 +10672,7 @@ public:
>>
>>  /*  Add new range to OP such that (OP CODE LIMIT) is true.  */
>>
>> -void
>> +value_range *
>>  evrp_dom_walker::try_add_new_range (tree op, tree_code code, tree limit)
>>  {
>>    value_range vr = VR_INITIALIZER;
>> @@ -10678,8 +10689,9 @@ evrp_dom_walker::try_add_new_range (tree
>>      {
>>        value_range *new_vr = vrp_value_range_pool.allocate ();
>>        *new_vr = vr;
>> -      push_value_range (op, new_vr);
>> +      return new_vr;
>>      }
>> +  return NULL;
>>  }
>>
>>  /* See if there is any new scope is entered with new VR and set that VR
>> to
>> @@ -10715,7 +10727,7 @@ evrp_dom_walker::before_dom_children (ba
>>             code = invert_tree_comparison (gimple_cond_code (stmt),
>>                                            HONOR_NANS (op0));
>>           /* Add VR when (OP0 CODE OP1) condition is true.  */
>> -         try_add_new_range (op0, code, op1);
>> +         value_range *op0_range = try_add_new_range (op0, code, op1);
>>
>>           /* Register ranges for y in x < y where
>>              y might have ranges that are useful.  */
>> @@ -10728,8 +10740,13 @@ evrp_dom_walker::before_dom_children (ba
>>                                                           &new_code,
>> &limit))
>>             {
>>               /* Add VR when (OP1 NEW_CODE LIMIT) condition is true.  */
>> -             try_add_new_range (op1, new_code, limit);
>> +             value_range *op1_range = try_add_new_range (op1, new_code,
>> limit);
>> +             if (op1_range)
>> +               push_value_range (op1, op1_range);
>>             }
>> +
>> +         if (op0_range)
>> +           push_value_range (op0, op0_range);
>>         }
>>      }
>>
>>
>>
>> seems to fix that and the issue.
>>
>
> Here is your patch with slight name change and ChangeLog. Bootstrapped and
> regression tested on x86_64-linux-gnu with no regressions. Is this OK for
> trunk?

Ok.

Richard.

> Thanks,
> Kugan
>
>
> gcc/ChangeLog:
>
> 2016-10-12  Richard Biener  <rguenther@suse.de>
>
>         * tree-vrp.c (evrp_dom_walker::try_find_new_range): Renamed from
>         try_add_new_range and made to return new range.
>         (evrp_dom_walker::before_dom_children): Push op1 value range before
>         pushing op0 value range.
>
>
> gcc/testsuite/ChangeLog:
>
> 2016-10-12  Kugan Vivekanandarajah  <kuganv@linaro.org>
>
>
>         * gcc.dg/tree-ssa/evrp6.c: New test.
>
>>> Thanks,
>>> Kugan
>>>
>>>
>>>
>>>> As said the issue is with the equivalence / value-range representation
>>>> so
>>>> you can't do sth like
>>>>
>>>>           /* Discover VR when condition is true.  */
>>>>           extract_range_for_var_from_comparison_expr (op0, code, op0,
>>>> op1,
>>>> &vr);
>>>>           if (old_vr->type == VR_RANGE || old_vr->type == VR_ANTI_RANGE)
>>>>             vrp_intersect_ranges (&vr, old_vr);
>>>>
>>>>           /* If we found any usable VR, set the VR to ssa_name and
>>>> create
>>>> a
>>>>              PUSH old value in the stack with the old VR.  */
>>>>           if (vr.type == VR_RANGE || vr.type == VR_ANTI_RANGE)
>>>>             {
>>>>               new_vr = vrp_value_range_pool.allocate ();
>>>>               *new_vr = vr;
>>>>               push_value_range (op0, new_vr);
>>>>   ->>>  add equivalence to old_vr for new_vr.
>>>>
>>>> because old_vr and new_vr are the 'same' (they are associated with SSA
>>>> name op0)
>>>>
>>>> Richard.
>>>>
>>>>> Thanks,
>>>>> Kugan
>>>>>
>>>>>
>>>>>
>>>>>
>>>>>
>>>>>> My thought on this was that we need to separate "ranges" and
>>>>>> associated
>>>>>> SSA names so we can introduce new ranges w/o the need for an SSA name
>>>>>> (and thus we can create an equivalence to the ASSERT_EXPR range).
>>>>>> IIRC I started on this at some point but never finished it ...
>>>>>>
>>>>>> Richard.
>>>>>>
>>>>>>> Thanks,
>>>>>>> Kugan
>>>>>>>
>>>>>>>
>>>>>>> gcc/testsuite/ChangeLog:
>>>>>>>
>>>>>>> 2016-10-07  Kugan Vivekanandarajah  <kuganv@linaro.org>
>>>>>>>
>>>>>>>         * gcc.dg/tree-ssa/evrp6.c: New test.
>>>>>>>
>>>>>>> gcc/ChangeLog:
>>>>>>>
>>>>>>> 2016-10-07  Kugan Vivekanandarajah  <kuganv@linaro.org>
>>>>>>>
>>>>>>>         * tree-vrp.c (intersect_ranges): If we failed to handle
>>>>>>>         the intersection and the other range involves computation
>>>>>>> with
>>>>>>>         symbolic values, choose integer range if available.
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>
>>>
>


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]