* [RFA][PR tree-optimization/79095] [PATCH 1/4] Improve ranges for MINUS_EXPR and EXACT_DIV_EXPR V2
@ 2017-02-07 18:31 Jeff Law
2017-02-08 12:45 ` Richard Biener
2017-02-12 8:08 ` Marc Glisse
0 siblings, 2 replies; 10+ messages in thread
From: Jeff Law @ 2017-02-07 18:31 UTC (permalink / raw)
To: gcc-patches
[-- Attachment #1: Type: text/plain, Size: 586 bytes --]
This patch addresses issues Richi raised from V1. Specifically it moves
EXACT_DIV_EXPR handling into extract_range_from_binary_expr_1 and less
aggressively uses ~[0,0] when intersecting ranges -- only doing so when
vr1's range is > 65536 elements. That number is highly arbitrary. I'm
certainly open to other values, not sure if a PARAM makes sense or not,
but can certainly do that if folks think it would be useful. There were
other minor nits Richi pointed out that were fixed too.
Bootstrapped and regression tested as part of the full patch series.
OK for the trunk?
[-- Attachment #2: P1 --]
[-- Type: text/plain, Size: 3306 bytes --]
* tree-vrp.c (extract_range_from_binary_expr_1): For EXACT_DIV_EXPR,
if the numerator has the range ~[0,0] make the resultant range ~[0,0].
(extract_range_from_binary_expr): For MINUS_EXPR with no derived range,
if the operands are known to be not equal, then the resulting range
is ~[0,0].
(difference_larger_than): New function.
(intersect_ranges): If the new range is ~[0,0] and the old range is
wide, then prefer ~[0,0].
diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
index b429217..ad8173c 100644
--- a/gcc/tree-vrp.c
+++ b/gcc/tree-vrp.c
@@ -2264,6 +2264,19 @@ extract_range_from_binary_expr_1 (value_range *vr,
if (vr0.type == VR_ANTI_RANGE
&& ranges_from_anti_range (&vr0, &vrtem0, &vrtem1))
{
+ /* We get imprecise results from ranges_from_anti_range when
+ code is EXACT_DIV_EXPR. We could mask out bits in the resulting
+ range, but then we also need to hack up vrp_meet. It's just
+ easier to special case when vr0 is ~[0,0] for EXACT_DIV_EXPR. */
+ if (code == EXACT_DIV_EXPR
+ && vr0.type == VR_ANTI_RANGE
+ && vr0.min == vr0.max
+ && integer_zerop (vr0.min))
+ {
+ set_value_range_to_nonnull (vr, expr_type);
+ return;
+ }
+
extract_range_from_binary_expr_1 (vr, code, expr_type, &vrtem0, vr1_);
if (vrtem1.type != VR_UNDEFINED)
{
@@ -3298,6 +3311,21 @@ extract_range_from_binary_expr (value_range *vr,
extract_range_from_binary_expr_1 (vr, code, expr_type, &n_vr0, &vr1);
}
+
+ /* If we didn't derive a range for MINUS_EXPR, and
+ op1's range is ~[op0,op0] or vice-versa, then we
+ can derive a non-null range. This happens often for
+ pointer subtraction. */
+ if (vr->type == VR_VARYING
+ && code == MINUS_EXPR
+ && TREE_CODE (op0) == SSA_NAME
+ && ((vr0.type == VR_ANTI_RANGE
+ && symbolic_range_based_on_p (&vr0, op1)
+ && vr0.min == vr0.max)
+ || (vr1.type == VR_ANTI_RANGE
+ && symbolic_range_based_on_p (&vr1, op0)
+ && vr1.min == vr1.max)))
+ set_value_range_to_nonnull (vr, TREE_TYPE (op0));
}
/* Extract range information from a unary operation CODE based on
@@ -8448,6 +8476,17 @@ give_up:
*vr0max = NULL_TREE;
}
+/* Return TRUE if MAX - MIN (both trees) is larger than LIMIT (HOST_WIDE_INT)
+ or overflows, FALSE otherwise. */
+
+static bool
+difference_larger_than (tree max, tree min, HOST_WIDE_INT limit)
+{
+ bool overflow;
+ wide_int res = wi::sub (max, min, SIGNED, &overflow);
+ return wi::gt_p (res, limit, UNSIGNED) || overflow;
+}
+
/* Intersect the two value-ranges { *VR0TYPE, *VR0MIN, *VR0MAX } and
{ VR1TYPE, VR0MIN, VR0MAX } and store the result
in { *VR0TYPE, *VR0MIN, *VR0MAX }. This may not be the smallest
@@ -8620,6 +8659,15 @@ intersect_ranges (enum value_range_type *vr0type,
else if (vrp_val_is_min (vr1min)
&& vrp_val_is_max (vr1max))
;
+ /* Choose the anti-range if it is ~[0,0], that range is special
+ enough to special case when vr1's range is relatively wide. */
+ else if (*vr0type == VR_ANTI_RANGE
+ && *vr0min == *vr0max
+ && integer_zerop (*vr0min)
+ && TREE_CODE (vr1max) == INTEGER_CST
+ && TREE_CODE (vr1min) == INTEGER_CST
+ && difference_larger_than (vr1max, vr1min, 65536))
+ ;
/* Else choose the range. */
else
{
^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [RFA][PR tree-optimization/79095] [PATCH 1/4] Improve ranges for MINUS_EXPR and EXACT_DIV_EXPR V2
2017-02-07 18:31 [RFA][PR tree-optimization/79095] [PATCH 1/4] Improve ranges for MINUS_EXPR and EXACT_DIV_EXPR V2 Jeff Law
@ 2017-02-08 12:45 ` Richard Biener
2017-02-10 3:08 ` Jeff Law
2017-02-12 8:08 ` Marc Glisse
1 sibling, 1 reply; 10+ messages in thread
From: Richard Biener @ 2017-02-08 12:45 UTC (permalink / raw)
To: Jeff Law; +Cc: gcc-patches
On Tue, Feb 7, 2017 at 7:31 PM, Jeff Law <law@redhat.com> wrote:
>
> This patch addresses issues Richi raised from V1. Specifically it moves
> EXACT_DIV_EXPR handling into extract_range_from_binary_expr_1 and less
> aggressively uses ~[0,0] when intersecting ranges -- only doing so when
> vr1's range is > 65536 elements. That number is highly arbitrary. I'm
> certainly open to other values, not sure if a PARAM makes sense or not, but
> can certainly do that if folks think it would be useful. There were other
> minor nits Richi pointed out that were fixed too.
>
> Bootstrapped and regression tested as part of the full patch series.
>
> OK for the trunk?
>
>
> * tree-vrp.c (extract_range_from_binary_expr_1): For EXACT_DIV_EXPR,
> if the numerator has the range ~[0,0] make the resultant range
> ~[0,0].
> (extract_range_from_binary_expr): For MINUS_EXPR with no derived
> range,
> if the operands are known to be not equal, then the resulting range
> is ~[0,0].
> (difference_larger_than): New function.
> (intersect_ranges): If the new range is ~[0,0] and the old range is
> wide, then prefer ~[0,0].
>
> diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
> index b429217..ad8173c 100644
> --- a/gcc/tree-vrp.c
> +++ b/gcc/tree-vrp.c
> @@ -2264,6 +2264,19 @@ extract_range_from_binary_expr_1 (value_range *vr,
> if (vr0.type == VR_ANTI_RANGE
> && ranges_from_anti_range (&vr0, &vrtem0, &vrtem1))
> {
> + /* We get imprecise results from ranges_from_anti_range when
> + code is EXACT_DIV_EXPR. We could mask out bits in the resulting
> + range, but then we also need to hack up vrp_meet. It's just
> + easier to special case when vr0 is ~[0,0] for EXACT_DIV_EXPR. */
> + if (code == EXACT_DIV_EXPR
> + && vr0.type == VR_ANTI_RANGE
> + && vr0.min == vr0.max
> + && integer_zerop (vr0.min))
> + {
> + set_value_range_to_nonnull (vr, expr_type);
> + return;
> + }
> +
Please move this before the surrounding if.
> extract_range_from_binary_expr_1 (vr, code, expr_type, &vrtem0,
> vr1_);
> if (vrtem1.type != VR_UNDEFINED)
> {
> @@ -3298,6 +3311,21 @@ extract_range_from_binary_expr (value_range *vr,
>
> extract_range_from_binary_expr_1 (vr, code, expr_type, &n_vr0, &vr1);
> }
> +
> + /* If we didn't derive a range for MINUS_EXPR, and
> + op1's range is ~[op0,op0] or vice-versa, then we
> + can derive a non-null range. This happens often for
> + pointer subtraction. */
> + if (vr->type == VR_VARYING
> + && code == MINUS_EXPR
> + && TREE_CODE (op0) == SSA_NAME
> + && ((vr0.type == VR_ANTI_RANGE
> + && symbolic_range_based_on_p (&vr0, op1)
Just seeing this again this also covers ~[op1 - 1, op1 - 1] and you are
just lucky because of the vr0.min == vr0.max equality compare and
both op1 - 1 hopefully not tree-shared (I'm not confident in that...).
So I think it would be better written as simply
&& vr0.min == op1
together with vr0.min == vr0.max you'd get what you are after.
> + && vr0.min == vr0.max)
> + || (vr1.type == VR_ANTI_RANGE
> + && symbolic_range_based_on_p (&vr1, op0)
Likewise of course.
> + && vr1.min == vr1.max)))
> + set_value_range_to_nonnull (vr, TREE_TYPE (op0));
> }
>
> /* Extract range information from a unary operation CODE based on
> @@ -8448,6 +8476,17 @@ give_up:
> *vr0max = NULL_TREE;
> }
>
> +/* Return TRUE if MAX - MIN (both trees) is larger than LIMIT
> (HOST_WIDE_INT)
> + or overflows, FALSE otherwise. */
> +
> +static bool
> +difference_larger_than (tree max, tree min, HOST_WIDE_INT limit)
> +{
> + bool overflow;
> + wide_int res = wi::sub (max, min, SIGNED, &overflow);
> + return wi::gt_p (res, limit, UNSIGNED) || overflow;
> +}
> +
> /* Intersect the two value-ranges { *VR0TYPE, *VR0MIN, *VR0MAX } and
> { VR1TYPE, VR0MIN, VR0MAX } and store the result
> in { *VR0TYPE, *VR0MIN, *VR0MAX }. This may not be the smallest
> @@ -8620,6 +8659,15 @@ intersect_ranges (enum value_range_type *vr0type,
> else if (vrp_val_is_min (vr1min)
> && vrp_val_is_max (vr1max))
> ;
> + /* Choose the anti-range if it is ~[0,0], that range is special
> + enough to special case when vr1's range is relatively wide. */
> + else if (*vr0type == VR_ANTI_RANGE
That's already known to be true here.
> + && *vr0min == *vr0max
> + && integer_zerop (*vr0min)
> + && TREE_CODE (vr1max) == INTEGER_CST
> + && TREE_CODE (vr1min) == INTEGER_CST
> + && difference_larger_than (vr1max, vr1min, 65536))
> + ;
in the case that interests us for the PR what is vr1?
> /* Else choose the range. */
> else
> {
>
^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [RFA][PR tree-optimization/79095] [PATCH 1/4] Improve ranges for MINUS_EXPR and EXACT_DIV_EXPR V2
2017-02-08 12:45 ` Richard Biener
@ 2017-02-10 3:08 ` Jeff Law
2017-02-10 8:14 ` Richard Biener
2017-02-10 23:53 ` Jeff Law
0 siblings, 2 replies; 10+ messages in thread
From: Jeff Law @ 2017-02-10 3:08 UTC (permalink / raw)
To: Richard Biener; +Cc: gcc-patches
On 02/08/2017 05:45 AM, Richard Biener wrote:
> On Tue, Feb 7, 2017 at 7:31 PM, Jeff Law <law@redhat.com> wrote:
>>
>> This patch addresses issues Richi raised from V1. Specifically it moves
>> EXACT_DIV_EXPR handling into extract_range_from_binary_expr_1 and less
>> aggressively uses ~[0,0] when intersecting ranges -- only doing so when
>> vr1's range is > 65536 elements. That number is highly arbitrary. I'm
>> certainly open to other values, not sure if a PARAM makes sense or not, but
>> can certainly do that if folks think it would be useful. There were other
>> minor nits Richi pointed out that were fixed too.
>>
>> Bootstrapped and regression tested as part of the full patch series.
>>
>> OK for the trunk?
>>
>>
>> * tree-vrp.c (extract_range_from_binary_expr_1): For EXACT_DIV_EXPR,
>> if the numerator has the range ~[0,0] make the resultant range
>> ~[0,0].
>> (extract_range_from_binary_expr): For MINUS_EXPR with no derived
>> range,
>> if the operands are known to be not equal, then the resulting range
>> is ~[0,0].
>> (difference_larger_than): New function.
>> (intersect_ranges): If the new range is ~[0,0] and the old range is
>> wide, then prefer ~[0,0].
>>
>> diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
>> index b429217..ad8173c 100644
>> --- a/gcc/tree-vrp.c
>> +++ b/gcc/tree-vrp.c
>> @@ -2264,6 +2264,19 @@ extract_range_from_binary_expr_1 (value_range *vr,
>> if (vr0.type == VR_ANTI_RANGE
>> && ranges_from_anti_range (&vr0, &vrtem0, &vrtem1))
>> {
>> + /* We get imprecise results from ranges_from_anti_range when
>> + code is EXACT_DIV_EXPR. We could mask out bits in the resulting
>> + range, but then we also need to hack up vrp_meet. It's just
>> + easier to special case when vr0 is ~[0,0] for EXACT_DIV_EXPR. */
>> + if (code == EXACT_DIV_EXPR
>> + && vr0.type == VR_ANTI_RANGE
>> + && vr0.min == vr0.max
>> + && integer_zerop (vr0.min))
>> + {
>> + set_value_range_to_nonnull (vr, expr_type);
>> + return;
>> + }
>> +
>
> Please move this before the surrounding if.
Yea. I wasn't sure about best location. Before the surrounding IF
works for me.
>
>> extract_range_from_binary_expr_1 (vr, code, expr_type, &vrtem0,
>> vr1_);
>> if (vrtem1.type != VR_UNDEFINED)
>> {
>> @@ -3298,6 +3311,21 @@ extract_range_from_binary_expr (value_range *vr,
>>
>> extract_range_from_binary_expr_1 (vr, code, expr_type, &n_vr0, &vr1);
>> }
>> +
>> + /* If we didn't derive a range for MINUS_EXPR, and
>> + op1's range is ~[op0,op0] or vice-versa, then we
>> + can derive a non-null range. This happens often for
>> + pointer subtraction. */
>> + if (vr->type == VR_VARYING
>> + && code == MINUS_EXPR
>> + && TREE_CODE (op0) == SSA_NAME
>> + && ((vr0.type == VR_ANTI_RANGE
>> + && symbolic_range_based_on_p (&vr0, op1)
>
> Just seeing this again this also covers ~[op1 - 1, op1 - 1] and you are
> just lucky because of the vr0.min == vr0.max equality compare and
> both op1 - 1 hopefully not tree-shared (I'm not confident in that...).
>
> So I think it would be better written as simply
>
> && vr0.min == op1
>
> together with vr0.min == vr0.max you'd get what you are after.
You're right. Fixed.
>
>> + && vr0.min == vr0.max)
>> + || (vr1.type == VR_ANTI_RANGE
>> + && symbolic_range_based_on_p (&vr1, op0)
>
> Likewise of course.
Likewise.
>
>> + && vr1.min == vr1.max)))
>> + set_value_range_to_nonnull (vr, TREE_TYPE (op0));
>> }
>>
>> /* Extract range information from a unary operation CODE based on
>> @@ -8448,6 +8476,17 @@ give_up:
>> *vr0max = NULL_TREE;
>> }
>>
>> +/* Return TRUE if MAX - MIN (both trees) is larger than LIMIT
>> (HOST_WIDE_INT)
>> + or overflows, FALSE otherwise. */
>> +
>> +static bool
>> +difference_larger_than (tree max, tree min, HOST_WIDE_INT limit)
>> +{
>> + bool overflow;
>> + wide_int res = wi::sub (max, min, SIGNED, &overflow);
>> + return wi::gt_p (res, limit, UNSIGNED) || overflow;
>> +}
>> +
>> /* Intersect the two value-ranges { *VR0TYPE, *VR0MIN, *VR0MAX } and
>> { VR1TYPE, VR0MIN, VR0MAX } and store the result
>> in { *VR0TYPE, *VR0MIN, *VR0MAX }. This may not be the smallest
>> @@ -8620,6 +8659,15 @@ intersect_ranges (enum value_range_type *vr0type,
>> else if (vrp_val_is_min (vr1min)
>> && vrp_val_is_max (vr1max))
>> ;
>> + /* Choose the anti-range if it is ~[0,0], that range is special
>> + enough to special case when vr1's range is relatively wide. */
>> + else if (*vr0type == VR_ANTI_RANGE
>
> That's already known to be true here.
Yes. Removed.
>
>> + && *vr0min == *vr0max
>> + && integer_zerop (*vr0min)
>> + && TREE_CODE (vr1max) == INTEGER_CST
>> + && TREE_CODE (vr1min) == INTEGER_CST
>> + && difference_larger_than (vr1max, vr1min, 65536))
>> + ;
>
> in the case that interests us for the PR what is vr1?
[-2305843009213693952, 2305843009213693951]
Jeff
^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [RFA][PR tree-optimization/79095] [PATCH 1/4] Improve ranges for MINUS_EXPR and EXACT_DIV_EXPR V2
2017-02-10 3:08 ` Jeff Law
@ 2017-02-10 8:14 ` Richard Biener
2017-02-10 23:53 ` Jeff Law
1 sibling, 0 replies; 10+ messages in thread
From: Richard Biener @ 2017-02-10 8:14 UTC (permalink / raw)
To: Jeff Law; +Cc: gcc-patches
On Fri, Feb 10, 2017 at 4:06 AM, Jeff Law <law@redhat.com> wrote:
> On 02/08/2017 05:45 AM, Richard Biener wrote:
>>
>> On Tue, Feb 7, 2017 at 7:31 PM, Jeff Law <law@redhat.com> wrote:
>>>
>>>
>>> This patch addresses issues Richi raised from V1. Specifically it moves
>>> EXACT_DIV_EXPR handling into extract_range_from_binary_expr_1 and less
>>> aggressively uses ~[0,0] when intersecting ranges -- only doing so when
>>> vr1's range is > 65536 elements. That number is highly arbitrary. I'm
>>> certainly open to other values, not sure if a PARAM makes sense or not,
>>> but
>>> can certainly do that if folks think it would be useful. There were
>>> other
>>> minor nits Richi pointed out that were fixed too.
>>>
>>> Bootstrapped and regression tested as part of the full patch series.
>>>
>>> OK for the trunk?
>>>
>>>
>>> * tree-vrp.c (extract_range_from_binary_expr_1): For
>>> EXACT_DIV_EXPR,
>>> if the numerator has the range ~[0,0] make the resultant range
>>> ~[0,0].
>>> (extract_range_from_binary_expr): For MINUS_EXPR with no derived
>>> range,
>>> if the operands are known to be not equal, then the resulting
>>> range
>>> is ~[0,0].
>>> (difference_larger_than): New function.
>>> (intersect_ranges): If the new range is ~[0,0] and the old range
>>> is
>>> wide, then prefer ~[0,0].
>>>
>>> diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
>>> index b429217..ad8173c 100644
>>> --- a/gcc/tree-vrp.c
>>> +++ b/gcc/tree-vrp.c
>>> @@ -2264,6 +2264,19 @@ extract_range_from_binary_expr_1 (value_range *vr,
>>> if (vr0.type == VR_ANTI_RANGE
>>> && ranges_from_anti_range (&vr0, &vrtem0, &vrtem1))
>>> {
>>> + /* We get imprecise results from ranges_from_anti_range when
>>> + code is EXACT_DIV_EXPR. We could mask out bits in the resulting
>>> + range, but then we also need to hack up vrp_meet. It's just
>>> + easier to special case when vr0 is ~[0,0] for EXACT_DIV_EXPR.
>>> */
>>> + if (code == EXACT_DIV_EXPR
>>> + && vr0.type == VR_ANTI_RANGE
>>> + && vr0.min == vr0.max
>>> + && integer_zerop (vr0.min))
>>> + {
>>> + set_value_range_to_nonnull (vr, expr_type);
>>> + return;
>>> + }
>>> +
>>
>>
>> Please move this before the surrounding if.
>
> Yea. I wasn't sure about best location. Before the surrounding IF works
> for me.
>
>>
>>> extract_range_from_binary_expr_1 (vr, code, expr_type, &vrtem0,
>>> vr1_);
>>> if (vrtem1.type != VR_UNDEFINED)
>>> {
>>> @@ -3298,6 +3311,21 @@ extract_range_from_binary_expr (value_range *vr,
>>>
>>> extract_range_from_binary_expr_1 (vr, code, expr_type, &n_vr0,
>>> &vr1);
>>> }
>>> +
>>> + /* If we didn't derive a range for MINUS_EXPR, and
>>> + op1's range is ~[op0,op0] or vice-versa, then we
>>> + can derive a non-null range. This happens often for
>>> + pointer subtraction. */
>>> + if (vr->type == VR_VARYING
>>> + && code == MINUS_EXPR
>>> + && TREE_CODE (op0) == SSA_NAME
>>> + && ((vr0.type == VR_ANTI_RANGE
>>> + && symbolic_range_based_on_p (&vr0, op1)
>>
>>
>> Just seeing this again this also covers ~[op1 - 1, op1 - 1] and you are
>> just lucky because of the vr0.min == vr0.max equality compare and
>> both op1 - 1 hopefully not tree-shared (I'm not confident in that...).
>>
>> So I think it would be better written as simply
>>
>> && vr0.min == op1
>>
>> together with vr0.min == vr0.max you'd get what you are after.
>
> You're right. Fixed.
>
>>
>>> + && vr0.min == vr0.max)
>>> + || (vr1.type == VR_ANTI_RANGE
>>> + && symbolic_range_based_on_p (&vr1, op0)
>>
>>
>> Likewise of course.
>
> Likewise.
>
>
>>
>>> + && vr1.min == vr1.max)))
>>> + set_value_range_to_nonnull (vr, TREE_TYPE (op0));
>>> }
>>>
>>> /* Extract range information from a unary operation CODE based on
>>> @@ -8448,6 +8476,17 @@ give_up:
>>> *vr0max = NULL_TREE;
>>> }
>>>
>>> +/* Return TRUE if MAX - MIN (both trees) is larger than LIMIT
>>> (HOST_WIDE_INT)
>>> + or overflows, FALSE otherwise. */
>>> +
>>> +static bool
>>> +difference_larger_than (tree max, tree min, HOST_WIDE_INT limit)
>>> +{
>>> + bool overflow;
>>> + wide_int res = wi::sub (max, min, SIGNED, &overflow);
>>> + return wi::gt_p (res, limit, UNSIGNED) || overflow;
>>> +}
>>> +
>>> /* Intersect the two value-ranges { *VR0TYPE, *VR0MIN, *VR0MAX } and
>>> { VR1TYPE, VR0MIN, VR0MAX } and store the result
>>> in { *VR0TYPE, *VR0MIN, *VR0MAX }. This may not be the smallest
>>> @@ -8620,6 +8659,15 @@ intersect_ranges (enum value_range_type *vr0type,
>>> else if (vrp_val_is_min (vr1min)
>>> && vrp_val_is_max (vr1max))
>>> ;
>>> + /* Choose the anti-range if it is ~[0,0], that range is special
>>> + enough to special case when vr1's range is relatively wide.
>>> */
>>> + else if (*vr0type == VR_ANTI_RANGE
>>
>>
>> That's already known to be true here.
>
> Yes. Removed.
>
>
>>
>>> + && *vr0min == *vr0max
>>> + && integer_zerop (*vr0min)
>>> + && TREE_CODE (vr1max) == INTEGER_CST
>>> + && TREE_CODE (vr1min) == INTEGER_CST
>>> + && difference_larger_than (vr1max, vr1min, 65536))
>>> + ;
>>
>>
>> in the case that interests us for the PR what is vr1?
>
> [-2305843009213693952, 2305843009213693951]
Ok, so let's do
/* Choose the anti-range if it is ~[0,0], that range is special
for pointer-like operations at least if the vr1's range is
relatively wide. This helps catching the fact when
pointer subtraction results in a known non-zero value. */
else if (*vr0min == *vr0max
&& integer_zerop (*vr0min)
&& TYPE_PRECISION (TREE_TYPE (*vr0min)) ==
TYPE_PRECISION (ptr_type_node)
&& TREE_CODE (vr1max) == INTEGER_CST
&& TREE_CODE (vr1min) == INTEGER_CST
&& wi::clz (wi::sub (vr1max, vr1min)) <
TYPE_PRECISION (TREE_TYPE (*vr0min)) / 2)
;
I'm still not 100% convinced this is the correct place to fix this (I
wonder if for the testcase
a carefully crafted match.pd pattern would be enough to simplify the
final != 0 comparison).
But let's defer more work on this to GCC 8 (where we hopefully get a
less stupid range representation
in VRP as well).
Thanks,
Richard.
>
> Jeff
^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [RFA][PR tree-optimization/79095] [PATCH 1/4] Improve ranges for MINUS_EXPR and EXACT_DIV_EXPR V2
2017-02-10 3:08 ` Jeff Law
2017-02-10 8:14 ` Richard Biener
@ 2017-02-10 23:53 ` Jeff Law
1 sibling, 0 replies; 10+ messages in thread
From: Jeff Law @ 2017-02-10 23:53 UTC (permalink / raw)
To: Richard Biener; +Cc: gcc-patches
On 02/09/2017 08:06 PM, Jeff Law wrote:
>
>
>>
>>> + && *vr0min == *vr0max
>>> + && integer_zerop (*vr0min)
>>> + && TREE_CODE (vr1max) == INTEGER_CST
>>> + && TREE_CODE (vr1min) == INTEGER_CST
>>> + && difference_larger_than (vr1max, vr1min, 65536))
>>> + ;
>>
>> in the case that interests us for the PR what is vr1?
> [-2305843009213693952, 2305843009213693951]
And just for completeness, I instrumented the compiler to dump the range
every time this code triggered to see what kind of ranges we'd be
changing into ~[0,0].
It triggers 1260 times during a bootstrap. 20 most common:
20 [-1073741824,1073741823]
20 [-65535,65535]
22 [-2147483647,2147483646]
23 [-1152921504606846976,1152921504606846975]
24 [-2147483648,39]
24 [-72057594037927936,72057594037927935]
24 [-8388608,8388607]
27 [-536870912,536870911]
28 [-2305843009213693952,2305843009213693951]
28 [-536870910,536870910]
32 [-2147483648,113]
41 [-2147483648,32767]
48 [-1,2147483646]
48 [-2147483647,2147483647]
48 [-2147483648,63]
48 [-9223372036854775807,9223372036854775807]
53 [-214748364,214748364]
70 [-2147483648,1]
160 [-2147483648,2147483647]
162 [-2147483648,2147483646]
Obviously it's harder to know how many of those ultimately lead to
optimizing something better.
With your heuristic we get 378 triggers with the most common being:
17 [-2147483648,113]
17 [-9223372036854775808,9223372036854775806]
18 [-1,2147483646]
18 [-2147483648,32767]
23 [-1152921504606846976,1152921504606846975]
24 [-72057594037927936,72057594037927935]
27 [-536870912,536870911]
28 [-2305843009213693952,2305843009213693951]
45 [-2147483648,2147483646]
48 [-9223372036854775807,9223372036854775807]
Anyway, I'll do the usual testing with your version.
jeff
^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [RFA][PR tree-optimization/79095] [PATCH 1/4] Improve ranges for MINUS_EXPR and EXACT_DIV_EXPR V2
2017-02-07 18:31 [RFA][PR tree-optimization/79095] [PATCH 1/4] Improve ranges for MINUS_EXPR and EXACT_DIV_EXPR V2 Jeff Law
2017-02-08 12:45 ` Richard Biener
@ 2017-02-12 8:08 ` Marc Glisse
2017-02-13 16:16 ` Jeff Law
1 sibling, 1 reply; 10+ messages in thread
From: Marc Glisse @ 2017-02-12 8:08 UTC (permalink / raw)
To: Jeff Law; +Cc: gcc-patches
On Tue, 7 Feb 2017, Jeff Law wrote:
> * tree-vrp.c (extract_range_from_binary_expr_1): For EXACT_DIV_EXPR,
> if the numerator has the range ~[0,0] make the resultant range ~[0,0].
If I understand correctly, for x /[ex] 4 with x!=0, we currently split
~[0,0] into [INT_MIN,-1] and [1,INT_MAX], then apply EXACT_DIV_EXPR which
gives [INT_MIN/4,-1] and [1,INT_MAX/4], and finally compute the union of
those, which prefers [INT_MIN/4,INT_MAX/4] over ~[0,0]. We could change
the union function, but this patch prefers changing the code elsewhere so
that the new behavior is restricted to the EXACT_DIV_EXPR case (and
supposedly the patch will be reverted if we get a new non-contiguous
version of ranges, where union would already work). Is that it?
--
Marc Glisse
^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [RFA][PR tree-optimization/79095] [PATCH 1/4] Improve ranges for MINUS_EXPR and EXACT_DIV_EXPR V2
2017-02-12 8:08 ` Marc Glisse
@ 2017-02-13 16:16 ` Jeff Law
2017-02-13 16:38 ` Marc Glisse
0 siblings, 1 reply; 10+ messages in thread
From: Jeff Law @ 2017-02-13 16:16 UTC (permalink / raw)
To: gcc-patches
On 02/12/2017 12:13 AM, Marc Glisse wrote:
> On Tue, 7 Feb 2017, Jeff Law wrote:
>
>> * tree-vrp.c (extract_range_from_binary_expr_1): For EXACT_DIV_EXPR,
>> if the numerator has the range ~[0,0] make the resultant range ~[0,0].
>
> If I understand correctly, for x /[ex] 4 with x!=0, we currently split
> ~[0,0] into [INT_MIN,-1] and [1,INT_MAX], then apply EXACT_DIV_EXPR
> which gives [INT_MIN/4,-1] and [1,INT_MAX/4], and finally compute the
> union of those, which prefers [INT_MIN/4,INT_MAX/4] over ~[0,0]. We
> could change the union function, but this patch prefers changing the
> code elsewhere so that the new behavior is restricted to the
> EXACT_DIV_EXPR case (and supposedly the patch will be reverted if we get
> a new non-contiguous version of ranges, where union would already work).
> Is that it?
That was one of alternate approaches I suggested.
Part of the problem is the conversion of ~[0,0] is imprecise when it's
going to be used in EXACT_DIV_EXPR, which I outlined elsewhere in the
thread. As a result of that imprecision, the ranges we get are
[INT_MIN/4,0] U [0,INT_MAX/4].
If we fix that imprecision so that the conversion yields [INT_MIN,-4] U
[4, INT_MAX] then apply EXACT_DIV_EXPR we get [INT_MIN/4,-1] U
[1,INT_MAX/4], which union_ranges turns into [INT_MIN/4,INT_MAX/4]. We
still end up needing a hack in union_ranges that will look a hell of a
lot like the one we're contemplating for intersect_ranges.
Jeff
^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [RFA][PR tree-optimization/79095] [PATCH 1/4] Improve ranges for MINUS_EXPR and EXACT_DIV_EXPR V2
2017-02-13 16:16 ` Jeff Law
@ 2017-02-13 16:38 ` Marc Glisse
2017-02-13 16:58 ` Jeff Law
0 siblings, 1 reply; 10+ messages in thread
From: Marc Glisse @ 2017-02-13 16:38 UTC (permalink / raw)
To: Jeff Law; +Cc: gcc-patches
On Mon, 13 Feb 2017, Jeff Law wrote:
> On 02/12/2017 12:13 AM, Marc Glisse wrote:
>> On Tue, 7 Feb 2017, Jeff Law wrote:
>>
>>> * tree-vrp.c (extract_range_from_binary_expr_1): For EXACT_DIV_EXPR,
>>> if the numerator has the range ~[0,0] make the resultant range ~[0,0].
>>
>> If I understand correctly, for x /[ex] 4 with x!=0, we currently split
>> ~[0,0] into [INT_MIN,-1] and [1,INT_MAX], then apply EXACT_DIV_EXPR
>> which gives [INT_MIN/4,-1] and [1,INT_MAX/4], and finally compute the
>> union of those, which prefers [INT_MIN/4,INT_MAX/4] over ~[0,0]. We
>> could change the union function, but this patch prefers changing the
>> code elsewhere so that the new behavior is restricted to the
>> EXACT_DIV_EXPR case (and supposedly the patch will be reverted if we get
>> a new non-contiguous version of ranges, where union would already work).
>> Is that it?
> That was one of alternate approaches I suggested.
>
> Part of the problem is the conversion of ~[0,0] is imprecise when it's going
> to be used in EXACT_DIV_EXPR, which I outlined elsewhere in the thread. As a
> result of that imprecision, the ranges we get are [INT_MIN/4,0] U
> [0,INT_MAX/4].
If VRP for [1, INT_MAX] /[ex] 4 produces [0, INT_MAX/4] instead of [1,
INT_MAX/4], that's a bug that should be fixed in any case. You shouldn't
need [4, INT_MAX] for that.
> If we fix that imprecision so that the conversion yields [INT_MIN,-4] U [4,
> INT_MAX] then apply EXACT_DIV_EXPR we get [INT_MIN/4,-1] U [1,INT_MAX/4],
> which union_ranges turns into [INT_MIN/4,INT_MAX/4]. We still end up needing
> a hack in union_ranges that will look a hell of a lot like the one we're
> contemplating for intersect_ranges.
That was the point of my question. Do we want to put that "hack" (prefer
an anti-range in some cases) in a central place where it would apply any
time we try to replace [a,b]U[c,d] (b+1<c) with a single range (and where
it would naturally disappear when we start allowing multiple ranges), or
do we prefer to put it in the few odd places where we have reason to
believe that it will help, while the usual strategy (produce [a,d])
remains preferable in general? From your patch it seems to be the later
case, which makes sense.
--
Marc Glisse
^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [RFA][PR tree-optimization/79095] [PATCH 1/4] Improve ranges for MINUS_EXPR and EXACT_DIV_EXPR V2
2017-02-13 16:38 ` Marc Glisse
@ 2017-02-13 16:58 ` Jeff Law
2017-02-14 11:09 ` Marc Glisse
0 siblings, 1 reply; 10+ messages in thread
From: Jeff Law @ 2017-02-13 16:58 UTC (permalink / raw)
To: gcc-patches
On 02/13/2017 09:15 AM, Marc Glisse wrote:
> On Mon, 13 Feb 2017, Jeff Law wrote:
>
>> On 02/12/2017 12:13 AM, Marc Glisse wrote:
>>> On Tue, 7 Feb 2017, Jeff Law wrote:
>>>
>>>> * tree-vrp.c (extract_range_from_binary_expr_1): For EXACT_DIV_EXPR,
>>>> if the numerator has the range ~[0,0] make the resultant range ~[0,0].
>>>
>>> If I understand correctly, for x /[ex] 4 with x!=0, we currently split
>>> ~[0,0] into [INT_MIN,-1] and [1,INT_MAX], then apply EXACT_DIV_EXPR
>>> which gives [INT_MIN/4,-1] and [1,INT_MAX/4], and finally compute the
>>> union of those, which prefers [INT_MIN/4,INT_MAX/4] over ~[0,0]. We
>>> could change the union function, but this patch prefers changing the
>>> code elsewhere so that the new behavior is restricted to the
>>> EXACT_DIV_EXPR case (and supposedly the patch will be reverted if we get
>>> a new non-contiguous version of ranges, where union would already work).
>>> Is that it?
>> That was one of alternate approaches I suggested.
>>
>> Part of the problem is the conversion of ~[0,0] is imprecise when it's
>> going to be used in EXACT_DIV_EXPR, which I outlined elsewhere in the
>> thread. As a result of that imprecision, the ranges we get are
>> [INT_MIN/4,0] U [0,INT_MAX/4].
>
> If VRP for [1, INT_MAX] /[ex] 4 produces [0, INT_MAX/4] instead of [1,
> INT_MAX/4], that's a bug that should be fixed in any case. You shouldn't
> need [4, INT_MAX] for that.
Agreed. But given it doesn't actually make anything around 79095
easier, I'd just assume defer to gcc-8.
I suspect that we'll see nicely refined anti-ranges, but rarely see
improvements in the generated code.
>
>> If we fix that imprecision so that the conversion yields [INT_MIN,-4]
>> U [4, INT_MAX] then apply EXACT_DIV_EXPR we get [INT_MIN/4,-1] U
>> [1,INT_MAX/4], which union_ranges turns into [INT_MIN/4,INT_MAX/4].
>> We still end up needing a hack in union_ranges that will look a hell
>> of a lot like the one we're contemplating for intersect_ranges.
>
> That was the point of my question. Do we want to put that "hack" (prefer
> an anti-range in some cases) in a central place where it would apply any
> time we try to replace [a,b]U[c,d] (b+1<c) with a single range (and
> where it would naturally disappear when we start allowing multiple
> ranges), or do we prefer to put it in the few odd places where we have
> reason to believe that it will help, while the usual strategy (produce
> [a,d]) remains preferable in general? From your patch it seems to be the
> later case, which makes sense.
I suspect we'll still need both. The code to prefer ~[0,0] when
intersecting ranges likely needs to stay regardless of other
improvements we make to EXACT_DIV_EXPR.
This is because we have to produce a wide range, including zero during
vrp1 and it's only during vrp2 that we can exclude zero. Thus no matter
what we do, we end up in intersect_ranges and have to make a guess about
whether to prefer the wide range of anti-singleton range of ~[0,0].
Jeff
^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [RFA][PR tree-optimization/79095] [PATCH 1/4] Improve ranges for MINUS_EXPR and EXACT_DIV_EXPR V2
2017-02-13 16:58 ` Jeff Law
@ 2017-02-14 11:09 ` Marc Glisse
0 siblings, 0 replies; 10+ messages in thread
From: Marc Glisse @ 2017-02-14 11:09 UTC (permalink / raw)
To: Jeff Law; +Cc: gcc-patches
On Mon, 13 Feb 2017, Jeff Law wrote:
> On 02/13/2017 09:15 AM, Marc Glisse wrote:
>> On Mon, 13 Feb 2017, Jeff Law wrote:
>>
>>> On 02/12/2017 12:13 AM, Marc Glisse wrote:
>>>> On Tue, 7 Feb 2017, Jeff Law wrote:
>>>>
>>>>> * tree-vrp.c (extract_range_from_binary_expr_1): For EXACT_DIV_EXPR,
>>>>> if the numerator has the range ~[0,0] make the resultant range ~[0,0].
>>>>
>>>> If I understand correctly, for x /[ex] 4 with x!=0, we currently split
>>>> ~[0,0] into [INT_MIN,-1] and [1,INT_MAX], then apply EXACT_DIV_EXPR
>>>> which gives [INT_MIN/4,-1] and [1,INT_MAX/4], and finally compute the
>>>> union of those, which prefers [INT_MIN/4,INT_MAX/4] over ~[0,0]. We
>>>> could change the union function, but this patch prefers changing the
>>>> code elsewhere so that the new behavior is restricted to the
>>>> EXACT_DIV_EXPR case (and supposedly the patch will be reverted if we get
>>>> a new non-contiguous version of ranges, where union would already work).
>>>> Is that it?
>>> That was one of alternate approaches I suggested.
>>>
>>> Part of the problem is the conversion of ~[0,0] is imprecise when it's
>>> going to be used in EXACT_DIV_EXPR, which I outlined elsewhere in the
>>> thread. As a result of that imprecision, the ranges we get are
>>> [INT_MIN/4,0] U [0,INT_MAX/4].
>>
>> If VRP for [1, INT_MAX] /[ex] 4 produces [0, INT_MAX/4] instead of [1,
>> INT_MAX/4], that's a bug that should be fixed in any case. You shouldn't
>> need [4, INT_MAX] for that.
> Agreed. But given it doesn't actually make anything around 79095 easier, I'd
> just assume defer to gcc-8.
That all depends how you handle the intersection/union thing.
> I suspect that we'll see nicely refined anti-ranges, but rarely see
> improvements in the generated code.
>
>>
>>> If we fix that imprecision so that the conversion yields [INT_MIN,-4]
>>> U [4, INT_MAX] then apply EXACT_DIV_EXPR we get [INT_MIN/4,-1] U
>>> [1,INT_MAX/4], which union_ranges turns into [INT_MIN/4,INT_MAX/4].
>>> We still end up needing a hack in union_ranges that will look a hell
>>> of a lot like the one we're contemplating for intersect_ranges.
>>
>> That was the point of my question. Do we want to put that "hack" (prefer
>> an anti-range in some cases) in a central place where it would apply any
>> time we try to replace [a,b]U[c,d] (b+1<c) with a single range (and
>> where it would naturally disappear when we start allowing multiple
>> ranges), or do we prefer to put it in the few odd places where we have
>> reason to believe that it will help, while the usual strategy (produce
>> [a,d]) remains preferable in general? From your patch it seems to be the
>> later case, which makes sense.
> I suspect we'll still need both. The code to prefer ~[0,0] when intersecting
> ranges likely needs to stay regardless of other improvements we make to
> EXACT_DIV_EXPR.
>
> This is because we have to produce a wide range, including zero during vrp1
> and it's only during vrp2 that we can exclude zero. Thus no matter what we
> do, we end up in intersect_ranges and have to make a guess about whether to
> prefer the wide range of anti-singleton range of ~[0,0].
In the cases where intersect_ranges (with at least one anti-range) ends up
with a union [a,b]U[c,d] with b+1<c, it could call union_ranges (or they
could both call the same helper), and we would have all the logic in a
single place to decide whether we want [a,d] or ~[b+1,c-1]. When we move
to multiple range components, an interesting place will be the heuristics
to go down from n components to 3 (or whatever number we pick), trying to
preserve the largest holes, the hole containing 0 if there is one, the
holes with numbers of small magnitude, etc.
In my opinion, having the logic in a non-central place like
extract_range_from_binary_expr_1 makes sense if we want a different
heuristic for this case than the general case. If the heuristic is
duplicated in a central place like vrp_intersect, that's probably not the
case, so I'd favor having the logic in exactly one place.
(I am not asking you to change anything, just discussing some
possibilities)
--
Marc Glisse
^ permalink raw reply [flat|nested] 10+ messages in thread
end of thread, other threads:[~2017-02-14 10:58 UTC | newest]
Thread overview: 10+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2017-02-07 18:31 [RFA][PR tree-optimization/79095] [PATCH 1/4] Improve ranges for MINUS_EXPR and EXACT_DIV_EXPR V2 Jeff Law
2017-02-08 12:45 ` Richard Biener
2017-02-10 3:08 ` Jeff Law
2017-02-10 8:14 ` Richard Biener
2017-02-10 23:53 ` Jeff Law
2017-02-12 8:08 ` Marc Glisse
2017-02-13 16:16 ` Jeff Law
2017-02-13 16:38 ` Marc Glisse
2017-02-13 16:58 ` Jeff Law
2017-02-14 11:09 ` Marc Glisse
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).