This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
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.
>>>>>>>
>>>>>>>
>>>>>>>
>>>>>
>>>
>