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 Tue, Oct 11, 2016 at 2:57 AM, kugan
<kugan.vivekanandarajah@linaro.org> wrote:
> 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.
> 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.
>>>>>
>>>>>
>>>>>
>>>
>