Re: [RFC] optimize x - y cmp 0 with undefined overflow
> Yeah, that sounds good to me.
Here's what I have at last commited after testing on x86-64/Linux.
2014-09-29 Eric Botcazou
* tree-vrp.c (get_single_symbol): New function.
(build_symbolic_expr): Likewise.
(symbolic_range_based_on_p): New predicate.
(extract_range_from_binary_expr_1): Deal with single-symbolic ranges
for PLUS and MINUS. Do not drop symbolic ranges at the end.
(extract_range_from_binary_expr): Try harder for PLUS and MINUS if
operand is symbolic and based on the other operand.
2014-09-29 Eric Botcazou
* gcc.dg/tree-ssa/vrp94.c: New test.
* gnat.dg/opt40.adb: Likewise.
--
Eric BotcazouIndex: tree-vrp.c
===
--- tree-vrp.c (revision 215656)
+++ tree-vrp.c (working copy)
@@ -916,6 +916,98 @@ symbolic_range_p (value_range_t *vr)
|| !is_gimple_min_invariant (vr->max));
}
+/* Return the single symbol (an SSA_NAME) contained in T if any, or NULL_TREE
+ otherwise. We only handle additive operations and set NEG to true if the
+ symbol is negated and INV to the invariant part, if any. */
+
+static tree
+get_single_symbol (tree t, bool *neg, tree *inv)
+{
+ bool neg_;
+ tree inv_;
+
+ if (TREE_CODE (t) == PLUS_EXPR
+ || TREE_CODE (t) == POINTER_PLUS_EXPR
+ || TREE_CODE (t) == MINUS_EXPR)
+{
+ if (is_gimple_min_invariant (TREE_OPERAND (t, 0)))
+ {
+ neg_ = (TREE_CODE (t) == MINUS_EXPR);
+ inv_ = TREE_OPERAND (t, 0);
+ t = TREE_OPERAND (t, 1);
+ }
+ else if (is_gimple_min_invariant (TREE_OPERAND (t, 1)))
+ {
+ neg_ = false;
+ inv_ = TREE_OPERAND (t, 1);
+ t = TREE_OPERAND (t, 0);
+ }
+ else
+return NULL_TREE;
+}
+ else
+{
+ neg_ = false;
+ inv_ = NULL_TREE;
+}
+
+ if (TREE_CODE (t) == NEGATE_EXPR)
+{
+ t = TREE_OPERAND (t, 0);
+ neg_ = !neg_;
+}
+
+ if (TREE_CODE (t) != SSA_NAME)
+return NULL_TREE;
+
+ *neg = neg_;
+ *inv = inv_;
+ return t;
+}
+
+/* The reverse operation: build a symbolic expression with TYPE
+ from symbol SYM, negated according to NEG, and invariant INV. */
+
+static tree
+build_symbolic_expr (tree type, tree sym, bool neg, tree inv)
+{
+ const bool pointer_p = POINTER_TYPE_P (type);
+ tree t = sym;
+
+ if (neg)
+t = build1 (NEGATE_EXPR, type, t);
+
+ if (integer_zerop (inv))
+return t;
+
+ return build2 (pointer_p ? POINTER_PLUS_EXPR : PLUS_EXPR, type, t, inv);
+}
+
+/* Return true if value range VR involves exactly one symbol SYM. */
+
+static bool
+symbolic_range_based_on_p (value_range_t *vr, const_tree sym)
+{
+ bool neg, min_has_symbol, max_has_symbol;
+ tree inv;
+
+ if (is_gimple_min_invariant (vr->min))
+min_has_symbol = false;
+ else if (get_single_symbol (vr->min, &neg, &inv) == sym)
+min_has_symbol = true;
+ else
+return false;
+
+ if (is_gimple_min_invariant (vr->max))
+max_has_symbol = false;
+ else if (get_single_symbol (vr->max, &neg, &inv) == sym)
+max_has_symbol = true;
+ else
+return false;
+
+ return (min_has_symbol || max_has_symbol);
+}
+
/* Return true if value range VR uses an overflow infinity. */
static inline bool
@@ -1199,25 +1291,30 @@ compare_values_warnv (tree val1, tree va
both integers. */
gcc_assert (POINTER_TYPE_P (TREE_TYPE (val1))
== POINTER_TYPE_P (TREE_TYPE (val2)));
+
/* Convert the two values into the same type. This is needed because
sizetype causes sign extension even for unsigned types. */
val2 = fold_convert (TREE_TYPE (val1), val2);
STRIP_USELESS_TYPE_CONVERSION (val2);
if ((TREE_CODE (val1) == SSA_NAME
+ || (TREE_CODE (val1) == NEGATE_EXPR
+ && TREE_CODE (TREE_OPERAND (val1, 0)) == SSA_NAME)
|| TREE_CODE (val1) == PLUS_EXPR
|| TREE_CODE (val1) == MINUS_EXPR)
&& (TREE_CODE (val2) == SSA_NAME
+ || (TREE_CODE (val2) == NEGATE_EXPR
+ && TREE_CODE (TREE_OPERAND (val2, 0)) == SSA_NAME)
|| TREE_CODE (val2) == PLUS_EXPR
|| TREE_CODE (val2) == MINUS_EXPR))
{
tree n1, c1, n2, c2;
enum tree_code code1, code2;
- /* If VAL1 and VAL2 are of the form 'NAME [+-] CST' or 'NAME',
+ /* If VAL1 and VAL2 are of the form '[-]NAME [+-] CST' or 'NAME',
return -1 or +1 accordingly. If VAL1 and VAL2 don't use the
same name, return -2. */
- if (TREE_CODE (val1) == SSA_NAME)
+ if (TREE_CODE (val1) == SSA_NAME || TREE_CODE (val1) == NEGATE_EXPR)
{
code1 = SSA_NAME;
n1 = val1;
@@ -1239,7 +1336,7 @@ compare_values_warnv (tree val1, tree va
}
}
- if (TREE_CODE (val2) == SSA_NAME)
+ if (TREE_CODE (val2) == SSA_NAME || TREE_CODE (val2) == NEGATE_EXPR)
{
code2 = SSA_NAME;
n2 = val2;
@@ -1262,11 +1359,15 @@ compare_values_warnv (tree val1, tree va
}
/* Both values must use the same name. */
+ if (TREE_CODE (n1) == NEGATE_EXPR && TREE_CODE (n2) == NEGATE_EXPR)
+
Re: [RFC] optimize x - y cmp 0 with undefined overflow
On Fri, Jun 20, 2014 at 11:33 AM, Eric Botcazou wrote: > [I'm at last back to this...] > >> > With [1, -x + INF] as the resulting range? But it can be bogus if x is >> > itself equal to +INF (unlike the input range [x + 1, +INF] which is >> > always correct) >> >> Hmm, indeed. >> >> > so this doesn't look valid to me. I don't see how we can get away >> > without a +INF(OVF) here, but I can compute it in >> > extract_range_from_binary_expr_1 if you prefer and try only [op0,op0] >> > and [op1,op1]. >> >> Yeah, I'd prefer that. > > To recap, the range of y is [x + 1, +INF] and we're trying to evaluate the > range of y - x, in particular we want to prove that y - x > 0. > > We compute the range of y - x as [1, -x + INF] by combining [x + 1, +INF] with > [x, x] and we want to massage it because compare_values will rightly choke. > > If overflow is undefined, we can simply change it to [1, +INF (OVF)] and be > done with that. But if overflow is defined, we need to prove that -x + INF > cannot wrap around (which is true if the type is unsigned) and the simplest > way to do that in the general case is to recursively invoke the machinery > of extract_range_from_binary_expr_1 on range_of(-x) + INF and analyze the > result. This looks much more complicated implementation-wise (and would very > likely buy us nothing in practice) than my scheme, where we just approximate > range_of(-x) by [-INF,+INF] and don't need to implement the recursion at all. Hmm, indeed. Put the above into a comment so it's clear why we don't do it that way. > However I can change extract_range_from_binary_expr so that only one range > among [-INF,x], [x,+INF] and [x,x] is tried instead of the 3 ranges in a row. > I initially didn't want to do that because this breaks the separation between > extract_range_from_binary_expr_1 and extract_range_from_binary_expr but, given > their names, this is very likely acceptable. What do you think? Yeah, that sounds good to me. Thanks, Richard. > -- > Eric Botcazou
Re: [RFC] optimize x - y cmp 0 with undefined overflow
[I'm at last back to this...] > > With [1, -x + INF] as the resulting range? But it can be bogus if x is > > itself equal to +INF (unlike the input range [x + 1, +INF] which is > > always correct) > > Hmm, indeed. > > > so this doesn't look valid to me. I don't see how we can get away > > without a +INF(OVF) here, but I can compute it in > > extract_range_from_binary_expr_1 if you prefer and try only [op0,op0] > > and [op1,op1]. > > Yeah, I'd prefer that. To recap, the range of y is [x + 1, +INF] and we're trying to evaluate the range of y - x, in particular we want to prove that y - x > 0. We compute the range of y - x as [1, -x + INF] by combining [x + 1, +INF] with [x, x] and we want to massage it because compare_values will rightly choke. If overflow is undefined, we can simply change it to [1, +INF (OVF)] and be done with that. But if overflow is defined, we need to prove that -x + INF cannot wrap around (which is true if the type is unsigned) and the simplest way to do that in the general case is to recursively invoke the machinery of extract_range_from_binary_expr_1 on range_of(-x) + INF and analyze the result. This looks much more complicated implementation-wise (and would very likely buy us nothing in practice) than my scheme, where we just approximate range_of(-x) by [-INF,+INF] and don't need to implement the recursion at all. However I can change extract_range_from_binary_expr so that only one range among [-INF,x], [x,+INF] and [x,x] is tried instead of the 3 ranges in a row. I initially didn't want to do that because this breaks the separation between extract_range_from_binary_expr_1 and extract_range_from_binary_expr but, given their names, this is very likely acceptable. What do you think? -- Eric Botcazou
Re: [RFC] optimize x - y cmp 0 with undefined overflow
On Fri, Jun 6, 2014 at 12:52 PM, Eric Botcazou wrote:
>> So when computing a range for z in
>>
>> z = y - x;
>>
>> with x = [-INF, y - 1] and y = [x + 1, +INF] (deduced from !(x >= y)) we
>> fail to do sth sensible with [y, y] - [-INF, y - 1] or [x + 1, +INF] - [x,
>> x] but we do sth with [x + 1, +INF] - [-INF, x]? That seems odd to me.
>>
>> With the patch we compute z to [1, +INF(OVF)]
>
> Right, and note the overflow.
>
>> Going the [x + 1, +INF] - [x,x] path first we obtain
>>
>> [1, -x + INF]
>>
>> which fails the sanity checking
>>
>> cmp = compare_values (min, max);
>> if (cmp == -2 || cmp == 1)
>> {
>> /* If the new range has its limits swapped around (MIN > MAX),
>> then the operation caused one of them to wrap around, mark
>> the new range VARYING. */
>> set_value_range_to_varying (vr);
>> }
>> else
>> set_value_range (vr, type, min, max, NULL);
>>
>> but clearly the same reasoning you can apply that makes trying
>> with [-INF, x] valid (it's just enlarging the range) can be applied
>> here, too, when computing +INF - x for the upper bound. We can
>> safely increase that to +INF making the range valid for the above
>> test.
>
> I don't think we can enlarge to +INF because -x + INF can overflow, we can
> only enlarge to +INF(OVF).
>
>> But I wonder what code path in the routine still relies on that sanity
>> checking to produce a valid result (so I'd rather try removing it, or
>> taking uncomparable bounds as a valid range).
>>
>> Simplest would be to simply do
>>
>> set_value_range (vr, type, min, max, NULL);
>> return;
>>
>> and be done with that in the plus/minus handling. With that the
>> testcase optimizes ok for me.
>
> With [1, -x + INF] as the resulting range? But it can be bogus if x is itself
> equal to +INF (unlike the input range [x + 1, +INF] which is always correct)
Hmm, indeed.
> so this doesn't look valid to me. I don't see how we can get away without a
> +INF(OVF) here, but I can compute it in extract_range_from_binary_expr_1 if
> you prefer and try only [op0,op0] and [op1,op1].
Yeah, I'd prefer that.
Thanks,
Richard.
> --
> Eric Botcazou
Re: [RFC] optimize x - y cmp 0 with undefined overflow
> So when computing a range for z in
>
> z = y - x;
>
> with x = [-INF, y - 1] and y = [x + 1, +INF] (deduced from !(x >= y)) we
> fail to do sth sensible with [y, y] - [-INF, y - 1] or [x + 1, +INF] - [x,
> x] but we do sth with [x + 1, +INF] - [-INF, x]? That seems odd to me.
>
> With the patch we compute z to [1, +INF(OVF)]
Right, and note the overflow.
> Going the [x + 1, +INF] - [x,x] path first we obtain
>
> [1, -x + INF]
>
> which fails the sanity checking
>
> cmp = compare_values (min, max);
> if (cmp == -2 || cmp == 1)
> {
> /* If the new range has its limits swapped around (MIN > MAX),
> then the operation caused one of them to wrap around, mark
> the new range VARYING. */
> set_value_range_to_varying (vr);
> }
> else
> set_value_range (vr, type, min, max, NULL);
>
> but clearly the same reasoning you can apply that makes trying
> with [-INF, x] valid (it's just enlarging the range) can be applied
> here, too, when computing +INF - x for the upper bound. We can
> safely increase that to +INF making the range valid for the above
> test.
I don't think we can enlarge to +INF because -x + INF can overflow, we can
only enlarge to +INF(OVF).
> But I wonder what code path in the routine still relies on that sanity
> checking to produce a valid result (so I'd rather try removing it, or
> taking uncomparable bounds as a valid range).
>
> Simplest would be to simply do
>
> set_value_range (vr, type, min, max, NULL);
> return;
>
> and be done with that in the plus/minus handling. With that the
> testcase optimizes ok for me.
With [1, -x + INF] as the resulting range? But it can be bogus if x is itself
equal to +INF (unlike the input range [x + 1, +INF] which is always correct)
so this doesn't look valid to me. I don't see how we can get away without a
+INF(OVF) here, but I can compute it in extract_range_from_binary_expr_1 if
you prefer and try only [op0,op0] and [op1,op1].
--
Eric Botcazou
Re: [RFC] optimize x - y cmp 0 with undefined overflow
On Tue, Jun 3, 2014 at 10:11 AM, Eric Botcazou wrote:
>> Looks mostly ok. Any reason why you are not re-creating
>> MINUS_EXPR in build_symbolic_expr? That is, build
>> inv - t (for non-pointers, of course)?
>
> It's more uniform and compare_values expects an INTEGER_CST on the RHS,
> although the patch was lacking a small tweak to the function:
>
> @@ -1205,19 +1292,23 @@ compare_values_warnv (tree val1, tree va
>STRIP_USELESS_TYPE_CONVERSION (val2);
>
>if ((TREE_CODE (val1) == SSA_NAME
> + || (TREE_CODE (val1) == NEGATE_EXPR
> + && TREE_CODE (TREE_OPERAND (val1, 0)) == SSA_NAME)
> || TREE_CODE (val1) == PLUS_EXPR
> || TREE_CODE (val1) == MINUS_EXPR)
>&& (TREE_CODE (val2) == SSA_NAME
> + || (TREE_CODE (val2) == NEGATE_EXPR
> + && TREE_CODE (TREE_OPERAND (val2, 0)) == SSA_NAME)
> || TREE_CODE (val2) == PLUS_EXPR
> || TREE_CODE (val2) == MINUS_EXPR))
> {
>tree n1, c1, n2, c2;
>enum tree_code code1, code2;
>
> - /* If VAL1 and VAL2 are of the form 'NAME [+-] CST' or 'NAME',
> + /* If VAL1 and VAL2 are of the form '[-]NAME [+-] CST' or 'NAME',
> return -1 or +1 accordingly. If VAL1 and VAL2 don't use the
> same name, return -2. */
> - if (TREE_CODE (val1) == SSA_NAME)
> + if (TREE_CODE (val1) == SSA_NAME || TREE_CODE (val1) == NEGATE_EXPR)
> {
> code1 = SSA_NAME;
> n1 = val1;
> @@ -1239,7 +1330,7 @@ compare_values_warnv (tree val1, tree va
> }
> }
>
> - if (TREE_CODE (val2) == SSA_NAME)
> + if (TREE_CODE (val2) == SSA_NAME || TREE_CODE (val2) == NEGATE_EXPR)
> {
> code2 = SSA_NAME;
> n2 = val2;
> @@ -1262,6 +1353,11 @@ compare_values_warnv (tree val1, tree va
> }
>
>/* Both values must use the same name. */
> + if (TREE_CODE (n1) == NEGATE_EXPR && TREE_CODE (n2) == NEGATE_EXPR)
> + {
> + n1 = TREE_OPERAND (n1, 0);
> + n2 = TREE_OPERAND (n2, 0);
> + }
>if (n1 != n2)
> return -2;
Ah, ok - makes sense.
>> Otherwise if a range becomes -t + inv that will no longer match
>> get_single_symbol for further propagation?
>
> Yes, it will, NEGATE_EXPR is handled by get_single_symbol.
Now spotted.
>> Then I'm not sure if
>>
>> + /* Try with VR0 and [-INF, OP1]. */
>> + set_value_range (&new_vr1, VR_RANGE, vrp_val_min (expr_type), op1,
>> NULL); + extract_range_from_binary_expr_1 (vr, code, expr_type, &vr0,
>> &new_vr1); + if (vr->type != VR_VARYING)
>> + return;
>> +
>> + /* Try with VR0 and [OP1, +INF]. */
>> + set_value_range (&new_vr1, VR_RANGE, op1, vrp_val_max (expr_type),
>> NULL); + extract_range_from_binary_expr_1 (vr, code, expr_type, &vr0,
>> &new_vr1); + if (vr->type != VR_VARYING)
>> + return;
>>
>> is a safe thing to do. If it does make a difference to try [-INF, OP1],
>> [OP1, +INF] instead of just [OP1, OP1] then at least it's very suspicious ;)
>> (or an "easy" missed optimization).
>
> Yes, it makes a difference and is required to eliminate half-symbolic ranges
> (the ones deduced from x >= y). Otherwise extract_range_from_binary_expr_1
> will reject the resulting range because it cannot compare the bounds.
>
> As discussed, extract_range_from_binary_expr_1 doesn't do any fiddling with
> the input ranges, it just computes the resulting range and see whether it can
> interpret it. Half-symbolic ranges cannot be interpreted and probably should
> not, in the general case at least, because I think it can be very delicate, so
> extract_range_from_binary_expr will just try all the possible combinations for
> PLUS and MINUS.
So when computing a range for z in
z = y - x;
with x = [-INF, y - 1] and y = [x + 1, +INF] (deduced from !(x >= y)) we fail to
do sth sensible with [y, y] - [-INF, y - 1] or [x + 1, +INF] - [x, x] but we do
sth with [x + 1, +INF] - [-INF, x]? That seems odd to me.
With the patch we compute z to [1, +INF(OVF)]
Going the [x + 1, +INF] - [x,x] path first we obtain
[1, -x + INF]
which fails the sanity checking
cmp = compare_values (min, max);
if (cmp == -2 || cmp == 1)
{
/* If the new range has its limits swapped around (MIN > MAX),
then the operation caused one of them to wrap around, mark
the new range VARYING. */
set_value_range_to_varying (vr);
}
else
set_value_range (vr, type, min, max, NULL);
but clearly the same reasoning you can apply that makes trying
with [-INF, x] valid (it's just enlarging the range) can be applied
here, too, when computing +INF - x for the upper bound. We can
safely increase that to +INF making the range valid for the above
test.
But I wonder what code path in the routine still relies on that sanity
checking to produce a valid result (so I'd rather try removing it, or
taking uncomparable bounds as a valid range).
Simplest would be to simply do
Re: [RFC] optimize x - y cmp 0 with undefined overflow
> Looks mostly ok. Any reason why you are not re-creating
> MINUS_EXPR in build_symbolic_expr? That is, build
> inv - t (for non-pointers, of course)?
It's more uniform and compare_values expects an INTEGER_CST on the RHS,
although the patch was lacking a small tweak to the function:
@@ -1205,19 +1292,23 @@ compare_values_warnv (tree val1, tree va
STRIP_USELESS_TYPE_CONVERSION (val2);
if ((TREE_CODE (val1) == SSA_NAME
+ || (TREE_CODE (val1) == NEGATE_EXPR
+ && TREE_CODE (TREE_OPERAND (val1, 0)) == SSA_NAME)
|| TREE_CODE (val1) == PLUS_EXPR
|| TREE_CODE (val1) == MINUS_EXPR)
&& (TREE_CODE (val2) == SSA_NAME
+ || (TREE_CODE (val2) == NEGATE_EXPR
+ && TREE_CODE (TREE_OPERAND (val2, 0)) == SSA_NAME)
|| TREE_CODE (val2) == PLUS_EXPR
|| TREE_CODE (val2) == MINUS_EXPR))
{
tree n1, c1, n2, c2;
enum tree_code code1, code2;
- /* If VAL1 and VAL2 are of the form 'NAME [+-] CST' or 'NAME',
+ /* If VAL1 and VAL2 are of the form '[-]NAME [+-] CST' or 'NAME',
return -1 or +1 accordingly. If VAL1 and VAL2 don't use the
same name, return -2. */
- if (TREE_CODE (val1) == SSA_NAME)
+ if (TREE_CODE (val1) == SSA_NAME || TREE_CODE (val1) == NEGATE_EXPR)
{
code1 = SSA_NAME;
n1 = val1;
@@ -1239,7 +1330,7 @@ compare_values_warnv (tree val1, tree va
}
}
- if (TREE_CODE (val2) == SSA_NAME)
+ if (TREE_CODE (val2) == SSA_NAME || TREE_CODE (val2) == NEGATE_EXPR)
{
code2 = SSA_NAME;
n2 = val2;
@@ -1262,6 +1353,11 @@ compare_values_warnv (tree val1, tree va
}
/* Both values must use the same name. */
+ if (TREE_CODE (n1) == NEGATE_EXPR && TREE_CODE (n2) == NEGATE_EXPR)
+ {
+ n1 = TREE_OPERAND (n1, 0);
+ n2 = TREE_OPERAND (n2, 0);
+ }
if (n1 != n2)
return -2;
> Otherwise if a range becomes -t + inv that will no longer match
> get_single_symbol for further propagation?
Yes, it will, NEGATE_EXPR is handled by get_single_symbol.
> Then I'm not sure if
>
> + /* Try with VR0 and [-INF, OP1]. */
> + set_value_range (&new_vr1, VR_RANGE, vrp_val_min (expr_type), op1,
> NULL); + extract_range_from_binary_expr_1 (vr, code, expr_type, &vr0,
> &new_vr1); + if (vr->type != VR_VARYING)
> + return;
> +
> + /* Try with VR0 and [OP1, +INF]. */
> + set_value_range (&new_vr1, VR_RANGE, op1, vrp_val_max (expr_type),
> NULL); + extract_range_from_binary_expr_1 (vr, code, expr_type, &vr0,
> &new_vr1); + if (vr->type != VR_VARYING)
> + return;
>
> is a safe thing to do. If it does make a difference to try [-INF, OP1],
> [OP1, +INF] instead of just [OP1, OP1] then at least it's very suspicious ;)
> (or an "easy" missed optimization).
Yes, it makes a difference and is required to eliminate half-symbolic ranges
(the ones deduced from x >= y). Otherwise extract_range_from_binary_expr_1
will reject the resulting range because it cannot compare the bounds.
As discussed, extract_range_from_binary_expr_1 doesn't do any fiddling with
the input ranges, it just computes the resulting range and see whether it can
interpret it. Half-symbolic ranges cannot be interpreted and probably should
not, in the general case at least, because I think it can be very delicate, so
extract_range_from_binary_expr will just try all the possible combinations for
PLUS and MINUS.
The testcases were attached to the first message in the thread, but I presume
that decent mail programs are a thing of the past. :-) Attached again.
--
Eric Botcazou-- { dg-do compile }
-- { dg-options "-O2 -fdump-tree-optimized" }
function Opt38 (X : Integer; Y : Integer ) return Positive is
Z : Integer;
begin
if X >= Y then
return 1;
end if;
Z := Y - X;
return Z;
end;
-- { dg-final { scan-tree-dump-not "gnat_rcheck" "optimized" } }
-- { dg-final { cleanup-tree-dump "optimized" } }/* { dg-do compile } */
/* { dg-options "-O2 -fdump-tree-optimized" } */
extern void abort (void);
int foo1 (int x, int y)
{
int z;
if (x >= y)
return 1;
z = y - x;
if (z <= 0)
abort ();
return z;
}
unsigned int foo2 (unsigned int x, unsigned int y)
{
unsigned int z;
if (x >= y)
return 1;
z = y - x;
if (z == 0)
abort ();
return z;
}
/* { dg-final { scan-tree-dump-not "abort" "optimized" } } */
/* { dg-final { cleanup-tree-dump "optimized" } } */
Re: [RFC] optimize x - y cmp 0 with undefined overflow
On Mon, Jun 2, 2014 at 12:36 PM, Richard Biener wrote: > On Fri, May 30, 2014 at 10:48 AM, Eric Botcazou wrote: >>> I'd say we still handle "basic" symbolic range ops in >>> extract_range_from_binary_1 >>> but in extract_range_from_binary_expr for a symbolic op0 we try to simplify >>> it with both [op1, op1] and with the value-range of op1 until we get a >>> non-varying range as result. Not sure if it's worth restricting that >>> to the case >>> where op0s value-range refers to op1 or vice versa, and eventually only >>> use op1 symbolically then. >> >> Patch along these lines attached. A bit heavy as expected, but it's VRP... >> It deals with my pet problem, you might want to check it does so with yours. >> >> Tested on x86_64-suse-linux with no regressions. > > Looks mostly ok. Any reason why you are not re-creating > MINUS_EXPR in build_symbolic_expr? That is, build > inv - t (for non-pointers, of course)? Otherwise if a range > becomes -t + inv that will no longer match get_single_symbol > for further propagation? > > Then I'm not sure if > > + /* Try with VR0 and [-INF, OP1]. */ > + set_value_range (&new_vr1, VR_RANGE, vrp_val_min (expr_type), op1, > NULL); > + extract_range_from_binary_expr_1 (vr, code, expr_type, &vr0, &new_vr1); > + if (vr->type != VR_VARYING) > + return; > + > + /* Try with VR0 and [OP1, +INF]. */ > + set_value_range (&new_vr1, VR_RANGE, op1, vrp_val_max (expr_type), > NULL); > + extract_range_from_binary_expr_1 (vr, code, expr_type, &vr0, &new_vr1); > + if (vr->type != VR_VARYING) > + return; > > is a safe thing to do. If it does make a difference to try [-INF, OP1], > [OP1, +INF] instead of just [OP1, OP1] then at least it's very suspicious ;) > (or an "easy" missed optimization). > > So - can you fix the negate thing and drop the four cases trying > the +-INF based ranges? Btw, the testcases are missing in the patch so I can't have a look myself. Richard. > Thanks, > Richard. > >> >> 2014-05-30 Eric Botcazou >> >> * tree-vrp.c (get_single_symbol): New function. >> (build_symbolic_expr): Likewise. >> (symbolic_range_based_on_p): New predicate. >> (extract_range_from_binary_expr_1): Deal with single-symbolic ranges >> for PLUS and MINUS. Do not drop symbolic ranges at the end. >> (extract_range_from_binary_expr): Try harder for PLUS and MINUS if >> operand is symbolic and based on the other operand. >> >> >> 2014-05-30 Eric Botcazou >> >> * gcc.dg/tree-ssa/vrp93.c: New test. >> * gnat.dg/opt38.adb: Likewise. >> >> >> -- >> Eric Botcazou
Re: [RFC] optimize x - y cmp 0 with undefined overflow
On Fri, May 30, 2014 at 10:48 AM, Eric Botcazou wrote: >> I'd say we still handle "basic" symbolic range ops in >> extract_range_from_binary_1 >> but in extract_range_from_binary_expr for a symbolic op0 we try to simplify >> it with both [op1, op1] and with the value-range of op1 until we get a >> non-varying range as result. Not sure if it's worth restricting that >> to the case >> where op0s value-range refers to op1 or vice versa, and eventually only >> use op1 symbolically then. > > Patch along these lines attached. A bit heavy as expected, but it's VRP... > It deals with my pet problem, you might want to check it does so with yours. > > Tested on x86_64-suse-linux with no regressions. Looks mostly ok. Any reason why you are not re-creating MINUS_EXPR in build_symbolic_expr? That is, build inv - t (for non-pointers, of course)? Otherwise if a range becomes -t + inv that will no longer match get_single_symbol for further propagation? Then I'm not sure if + /* Try with VR0 and [-INF, OP1]. */ + set_value_range (&new_vr1, VR_RANGE, vrp_val_min (expr_type), op1, NULL); + extract_range_from_binary_expr_1 (vr, code, expr_type, &vr0, &new_vr1); + if (vr->type != VR_VARYING) + return; + + /* Try with VR0 and [OP1, +INF]. */ + set_value_range (&new_vr1, VR_RANGE, op1, vrp_val_max (expr_type), NULL); + extract_range_from_binary_expr_1 (vr, code, expr_type, &vr0, &new_vr1); + if (vr->type != VR_VARYING) + return; is a safe thing to do. If it does make a difference to try [-INF, OP1], [OP1, +INF] instead of just [OP1, OP1] then at least it's very suspicious ;) (or an "easy" missed optimization). So - can you fix the negate thing and drop the four cases trying the +-INF based ranges? Thanks, Richard. > > 2014-05-30 Eric Botcazou > > * tree-vrp.c (get_single_symbol): New function. > (build_symbolic_expr): Likewise. > (symbolic_range_based_on_p): New predicate. > (extract_range_from_binary_expr_1): Deal with single-symbolic ranges > for PLUS and MINUS. Do not drop symbolic ranges at the end. > (extract_range_from_binary_expr): Try harder for PLUS and MINUS if > operand is symbolic and based on the other operand. > > > 2014-05-30 Eric Botcazou > > * gcc.dg/tree-ssa/vrp93.c: New test. > * gnat.dg/opt38.adb: Likewise. > > > -- > Eric Botcazou
Re: [RFC] optimize x - y cmp 0 with undefined overflow
> I'd say we still handle "basic" symbolic range ops in
> extract_range_from_binary_1
> but in extract_range_from_binary_expr for a symbolic op0 we try to simplify
> it with both [op1, op1] and with the value-range of op1 until we get a
> non-varying range as result. Not sure if it's worth restricting that
> to the case
> where op0s value-range refers to op1 or vice versa, and eventually only
> use op1 symbolically then.
Patch along these lines attached. A bit heavy as expected, but it's VRP...
It deals with my pet problem, you might want to check it does so with yours.
Tested on x86_64-suse-linux with no regressions.
2014-05-30 Eric Botcazou
* tree-vrp.c (get_single_symbol): New function.
(build_symbolic_expr): Likewise.
(symbolic_range_based_on_p): New predicate.
(extract_range_from_binary_expr_1): Deal with single-symbolic ranges
for PLUS and MINUS. Do not drop symbolic ranges at the end.
(extract_range_from_binary_expr): Try harder for PLUS and MINUS if
operand is symbolic and based on the other operand.
2014-05-30 Eric Botcazou
* gcc.dg/tree-ssa/vrp93.c: New test.
* gnat.dg/opt38.adb: Likewise.
--
Eric BotcazouIndex: tree-vrp.c
===
--- tree-vrp.c (revision 211019)
+++ tree-vrp.c (working copy)
@@ -916,6 +916,93 @@ symbolic_range_p (value_range_t *vr)
|| !is_gimple_min_invariant (vr->max));
}
+/* Return the single symbol (an SSA_NAME) contained in T if any, or NULL_TREE
+ otherwise. We only handle additive operations and set NEG to true if the
+ symbol is negated and INV to the invariant part, if any. */
+
+static tree
+get_single_symbol (tree t, bool *neg, tree *inv)
+{
+ if (TREE_CODE (t) == PLUS_EXPR
+ || TREE_CODE (t) == POINTER_PLUS_EXPR
+ || TREE_CODE (t) == MINUS_EXPR)
+{
+ if (is_gimple_min_invariant (TREE_OPERAND (t, 0)))
+ {
+ *inv = TREE_OPERAND (t, 0);
+ *neg = (TREE_CODE (t) == MINUS_EXPR);
+ t = TREE_OPERAND (t, 1);
+ }
+ else if (is_gimple_min_invariant (TREE_OPERAND (t, 1)))
+ {
+ *inv = TREE_OPERAND (t, 1);
+ *neg = false;
+ t = TREE_OPERAND (t, 0);
+ }
+ else
+return NULL_TREE;
+}
+ else
+{
+ *inv = NULL_TREE;
+ *neg = false;
+}
+
+ if (TREE_CODE (t) == NEGATE_EXPR)
+{
+ t = TREE_OPERAND (t, 0);
+ *neg = true;
+}
+
+ if (TREE_CODE (t) != SSA_NAME)
+return NULL_TREE;
+
+ return t;
+}
+
+/* The reverse operation: build a symbolic expression with TYPE
+ from symbol SYM, negated according to NEG, and invariant INV. */
+
+static tree
+build_symbolic_expr (tree type, tree sym, bool neg, tree inv)
+{
+ const bool pointer_p = POINTER_TYPE_P (type);
+ tree t = sym;
+
+ if (neg)
+t = build1 (NEGATE_EXPR, type, t);
+
+ if (integer_zerop (inv))
+return t;
+
+ return build2 (pointer_p ? POINTER_PLUS_EXPR : PLUS_EXPR, type, t, inv);
+}
+
+/* Return true if value range VR involves exactly one symbol SYM. */
+
+static bool
+symbolic_range_based_on_p (value_range_t *vr, const_tree sym)
+{
+ bool neg, min_has_symbol, max_has_symbol;
+ tree inv;
+
+ if (is_gimple_min_invariant (vr->min))
+min_has_symbol = false;
+ else if (get_single_symbol (vr->min, &neg, &inv) == sym)
+min_has_symbol = true;
+ else
+return false;
+
+ if (is_gimple_min_invariant (vr->max))
+max_has_symbol = false;
+ else if (get_single_symbol (vr->max, &neg, &inv) == sym)
+max_has_symbol = true;
+ else
+return false;
+
+ return (min_has_symbol || max_has_symbol);
+}
+
/* Return true if value range VR uses an overflow infinity. */
static inline bool
@@ -2209,7 +2296,7 @@ extract_range_from_multiplicative_op_1 (
}
/* Extract range information from a binary operation CODE based on
- the ranges of each of its operands, *VR0 and *VR1 with resulting
+ the ranges of each of its operands *VR0 and *VR1 with resulting
type EXPR_TYPE. The resulting range is stored in *VR. */
static void
@@ -2303,11 +2390,12 @@ extract_range_from_binary_expr_1 (value_
type = vr0.type;
/* Refuse to operate on VARYING ranges, ranges of different kinds
- and symbolic ranges. As an exception, we allow BIT_AND_EXPR
+ and symbolic ranges. As an exception, we allow BIT_{AND,IOR}
because we may be able to derive a useful range even if one of
the operands is VR_VARYING or symbolic range. Similarly for
- divisions. TODO, we may be able to derive anti-ranges in
- some cases. */
+ divisions, MIN/MAX and PLUS/MINUS.
+
+ TODO, we may be able to derive anti-ranges in some cases. */
if (code != BIT_AND_EXPR
&& code != BIT_IOR_EXPR
&& code != TRUNC_DIV_EXPR
@@ -2318,6 +2406,8 @@ extract_range_from_binary_expr_1 (value_
&& code != TRUNC_MOD_EXPR
&& code != MIN_EXPR
&& code != MAX_EXPR
+ && code != PLUS_EXPR
+ && code != MINUS_EXPR
&& (vr0.
Re: [RFC] optimize x - y cmp 0 with undefined overflow
On May 27, 2014 6:12:58 PM CEST, Eric Botcazou wrote: >> I'm asking to merge them (move them to fold_comparison). > >Done (in the end the patch removes more lines than it adds :-). That's what I like! >Tested on x86_64-suse-linux with no regressions. OK. Thanks, Richard. > >2014-05-27 Eric Botcazou > > * fold-const.c (fold_comparison): Clean up and extend X +- C1 CMP C2 > to X CMP C2 -+ C1 transformation to EQ_EXPR/NE_EXPR. > Add X - Y CMP 0 to X CMP Y transformation. > (fold_binary_loc) : Remove same transformations. > > >2014-05-27 Eric Botcazou > >* gcc.dg/fold-compare-8.c: New test. >* gcc.dg/Wstrict-overflow-25.c: Likewise.
Re: [RFC] optimize x - y cmp 0 with undefined overflow
> I'm asking to merge them (move them to fold_comparison).
Done (in the end the patch removes more lines than it adds :-).
Tested on x86_64-suse-linux with no regressions.
2014-05-27 Eric Botcazou
* fold-const.c (fold_comparison): Clean up and extend X +- C1 CMP C2
to X CMP C2 -+ C1 transformation to EQ_EXPR/NE_EXPR.
Add X - Y CMP 0 to X CMP Y transformation.
(fold_binary_loc) : Remove same transformations.
2014-05-27 Eric Botcazou
* gcc.dg/fold-compare-8.c: New test.
* gcc.dg/Wstrict-overflow-25.c: Likewise.
--
Eric BotcazouIndex: fold-const.c
===
--- fold-const.c (revision 210911)
+++ fold-const.c (working copy)
@@ -8904,6 +8904,7 @@ static tree
fold_comparison (location_t loc, enum tree_code code, tree type,
tree op0, tree op1)
{
+ const bool equality_code = (code == EQ_EXPR || code == NE_EXPR);
tree arg0, arg1, tem;
arg0 = op0;
@@ -8920,28 +8921,24 @@ fold_comparison (location_t loc, enum tr
if (tree_swap_operands_p (arg0, arg1, true))
return fold_build2_loc (loc, swap_tree_comparison (code), type, op1, op0);
- /* Transform comparisons of the form X +- C1 CMP C2 to X CMP C2 +- C1. */
+ /* Transform comparisons of the form X +- C1 CMP C2 to X CMP C2 -+ C1. */
if ((TREE_CODE (arg0) == PLUS_EXPR || TREE_CODE (arg0) == MINUS_EXPR)
- && (TREE_CODE (TREE_OPERAND (arg0, 1)) == INTEGER_CST
- && !TREE_OVERFLOW (TREE_OPERAND (arg0, 1))
- && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (arg1)))
- && (TREE_CODE (arg1) == INTEGER_CST
- && !TREE_OVERFLOW (arg1)))
+ && (equality_code || TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (arg0)))
+ && TREE_CODE (TREE_OPERAND (arg0, 1)) == INTEGER_CST
+ && !TREE_OVERFLOW (TREE_OPERAND (arg0, 1))
+ && TREE_CODE (arg1) == INTEGER_CST
+ && !TREE_OVERFLOW (arg1))
{
+ const enum tree_code
+ reverse_op = TREE_CODE (arg0) == PLUS_EXPR ? MINUS_EXPR : PLUS_EXPR;
tree const1 = TREE_OPERAND (arg0, 1);
- tree const2 = arg1;
+ tree const2 = fold_convert_loc (loc, TREE_TYPE (const1), arg1);
tree variable = TREE_OPERAND (arg0, 0);
- tree lhs;
- int lhs_add;
- lhs_add = TREE_CODE (arg0) != PLUS_EXPR;
-
- lhs = fold_build2_loc (loc, lhs_add ? PLUS_EXPR : MINUS_EXPR,
- TREE_TYPE (arg1), const2, const1);
+ tree new_const = int_const_binop (reverse_op, const2, const1);
/* If the constant operation overflowed this can be
simplified as a comparison against INT_MAX/INT_MIN. */
- if (TREE_CODE (lhs) == INTEGER_CST
- && TREE_OVERFLOW (lhs))
+ if (TREE_OVERFLOW (new_const))
{
int const1_sgn = tree_int_cst_sgn (const1);
enum tree_code code2 = code;
@@ -8961,29 +8958,48 @@ fold_comparison (location_t loc, enum tr
/* We now can look at the canonicalized case
VARIABLE + 1 CODE2 INT_MIN
and decide on the result. */
- if (code2 == LT_EXPR
- || code2 == LE_EXPR
- || code2 == EQ_EXPR)
- return omit_one_operand_loc (loc, type, boolean_false_node, variable);
- else if (code2 == NE_EXPR
- || code2 == GE_EXPR
- || code2 == GT_EXPR)
- return omit_one_operand_loc (loc, type, boolean_true_node, variable);
- }
+ switch (code2)
+ {
+ case EQ_EXPR:
+ case LT_EXPR:
+ case LE_EXPR:
+ return
+ omit_one_operand_loc (loc, type, boolean_false_node, variable);
+
+ case NE_EXPR:
+ case GE_EXPR:
+ case GT_EXPR:
+ return
+ omit_one_operand_loc (loc, type, boolean_true_node, variable);
- if (TREE_CODE (lhs) == TREE_CODE (arg1)
- && (TREE_CODE (lhs) != INTEGER_CST
- || !TREE_OVERFLOW (lhs)))
+ default:
+ gcc_unreachable ();
+ }
+ }
+ else
{
- if (code != EQ_EXPR && code != NE_EXPR)
+ if (!equality_code)
fold_overflow_warning ("assuming signed overflow does not occur "
"when changing X +- C1 cmp C2 to "
- "X cmp C1 +- C2",
+ "X cmp C2 -+ C1",
WARN_STRICT_OVERFLOW_COMPARISON);
- return fold_build2_loc (loc, code, type, variable, lhs);
+ return fold_build2_loc (loc, code, type, variable, new_const);
}
}
+ /* Transform comparisons of the form X - Y CMP 0 to X CMP Y. */
+ if (TREE_CODE (arg0) == MINUS_EXPR
+ && (equality_code || TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (arg0)))
+ && integer_zerop (arg1))
+{
+ if (!equality_code)
+ fold_overflow_warning ("assuming signed overflow does not occur "
+ "when changing X - Y cmp 0 to X cmp Y",
+ WARN_STRICT_OVERFLOW_COMPARISON);
+ return fold_build2_loc (loc, code, type, TREE_OPERAND (arg0, 0),
+ TREE_OPERAND (arg0, 1));
+}
+
/* For comparisons of pointers we can decompose it to a compile time
comparison of the base objects and the offsets into the object.
This requires at least one operand being an ADDR_EXPR or a
@@ -9111,8 +9127,7 @@ fold_comparison (location_t loc, en
Re: [RFC] optimize x - y cmp 0 with undefined overflow
On Tue, May 27, 2014 at 11:59 AM, Eric Botcazou wrote: >> I'm asking to merge them (move them to fold_comparison). > > OK, I'll repost a first patch doing only the fold-const.c massaging. > >> Yeah, it would be nice to see some support. The most interesting cases >> will be symbolic-singleton +- CST where the offset shrinks a constant offset >> in a symbolic A +- CST (thus we don't get into any overflow issues). Thus >> handling >> >> [a + 1, a + 1] - [1, 1] -> [a, a] >> >> for example. We get the offsetted singleton symbolic ranges from >> conditional asserts a lot. > > For the case at hand, you have [x + 1, INF] for y and you want to evaluate the > range of y - x, so you really don't want to use the range of x... Ok. That's similar to the issue I try to address with the VRP snipped I posted yesterday. I'd say we still handle "basic" symbolic range ops in extract_range_from_binary_1 but in extract_range_from_binary_expr for a symbolic op0 we try to simplify it with both [op1, op1] and with the value-range of op1 until we get a non-varying range as result. Not sure if it's worth restricting that to the case where op0s value-range refers to op1 or vice versa, and eventually only use op1 symbolically then. Richard. > -- > Eric Botcazou
Re: [RFC] optimize x - y cmp 0 with undefined overflow
> I'm asking to merge them (move them to fold_comparison). OK, I'll repost a first patch doing only the fold-const.c massaging. > Yeah, it would be nice to see some support. The most interesting cases > will be symbolic-singleton +- CST where the offset shrinks a constant offset > in a symbolic A +- CST (thus we don't get into any overflow issues). Thus > handling > > [a + 1, a + 1] - [1, 1] -> [a, a] > > for example. We get the offsetted singleton symbolic ranges from > conditional asserts a lot. For the case at hand, you have [x + 1, INF] for y and you want to evaluate the range of y - x, so you really don't want to use the range of x... -- Eric Botcazou
Re: [RFC] optimize x - y cmp 0 with undefined overflow
On Tue, May 27, 2014 at 11:25 AM, Eric Botcazou wrote: >> + tree new_const >> + = fold_build2_loc (loc, reverse_op, TREE_TYPE (arg1), const2, >> const1); >> >>/* If the constant operation overflowed this can be >> simplified as a comparison against INT_MAX/INT_MIN. */ >> - if (TREE_CODE (lhs) == INTEGER_CST >> - && TREE_OVERFLOW (lhs)) >> + if (TREE_OVERFLOW (new_const)) >> >> well, either use int_const_binop above or retain the check (or use >> TREE_OVERFLOW_P). Bonus points for using wide-ints here >> and not relying on TREE_OVERFLOW. > > The check is useless (you get either NULL_TREE or INTEGER_CST here) but I'll > use int_const_binop. > >> + /* Transform comparisons of the form X - Y CMP 0 to X CMP Y. */ >> + if (TREE_CODE (arg0) == MINUS_EXPR >> + && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (arg1)) >> >> any good reason for using TYPE_OVERFLOW_UNDEFINED on the >> type of arg1 instead on the type of the MINUS (yes, they should >> match, but it really looks odd ... the overflow of the minus has to be >> undefined). > > For the sake of consistency with the X +- C1 CMP C2 case just above, but I can > change both. > >> Also for EQ_EXPR and NE_EXPR the transform is >> fine even when !TYPE_OVERFLOW_UNDEFINED (and we seem >> to perform it already somewhere). Please look where and try to >> add the undefined overflow case to it. > > Yes, but it's the same for the X +- C1 CMP C2 case, i.e. there are specific > cases for X +- C1 EQ/NE C2 and X - Y EQ/NE 0 in fold_binary, so I'm not sure > what you're asking. I'm asking to merge them (move them to fold_comparison). >> As for the VRP pieces I don't understand what is missing here >> (well, compare_range_with_value and/or compare_values might >> not handle this case? then better fix that to improve symbolic >> range handling in general?). Also I have a longstanding patch >> in my tree that does > > Yes, there is an explicit non-handling of symbolic ranges for PLUS_EXPR and > MINUS_EXPR in VRP (extract_range_from_binary_expr_1) and the patch works > around it by propagating the code instead of the ranges, which is far easier > and sufficient here. If you think that the way to go is to handle symbolic > ranges for PLUS_EXPR and MINUS_EXPR instead, fine with me, I can try. Yeah, it would be nice to see some support. The most interesting cases will be symbolic-singleton +- CST where the offset shrinks a constant offset in a symbolic A +- CST (thus we don't get into any overflow issues). Thus handling [a + 1, a + 1] - [1, 1] -> [a, a] for example. We get the offsetted singleton symbolic ranges from conditional asserts a lot. Thanks, Richard. > -- > Eric Botcazou
Re: [RFC] optimize x - y cmp 0 with undefined overflow
> + tree new_const > + = fold_build2_loc (loc, reverse_op, TREE_TYPE (arg1), const2, > const1); > >/* If the constant operation overflowed this can be > simplified as a comparison against INT_MAX/INT_MIN. */ > - if (TREE_CODE (lhs) == INTEGER_CST > - && TREE_OVERFLOW (lhs)) > + if (TREE_OVERFLOW (new_const)) > > well, either use int_const_binop above or retain the check (or use > TREE_OVERFLOW_P). Bonus points for using wide-ints here > and not relying on TREE_OVERFLOW. The check is useless (you get either NULL_TREE or INTEGER_CST here) but I'll use int_const_binop. > + /* Transform comparisons of the form X - Y CMP 0 to X CMP Y. */ > + if (TREE_CODE (arg0) == MINUS_EXPR > + && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (arg1)) > > any good reason for using TYPE_OVERFLOW_UNDEFINED on the > type of arg1 instead on the type of the MINUS (yes, they should > match, but it really looks odd ... the overflow of the minus has to be > undefined). For the sake of consistency with the X +- C1 CMP C2 case just above, but I can change both. > Also for EQ_EXPR and NE_EXPR the transform is > fine even when !TYPE_OVERFLOW_UNDEFINED (and we seem > to perform it already somewhere). Please look where and try to > add the undefined overflow case to it. Yes, but it's the same for the X +- C1 CMP C2 case, i.e. there are specific cases for X +- C1 EQ/NE C2 and X - Y EQ/NE 0 in fold_binary, so I'm not sure what you're asking. > As for the VRP pieces I don't understand what is missing here > (well, compare_range_with_value and/or compare_values might > not handle this case? then better fix that to improve symbolic > range handling in general?). Also I have a longstanding patch > in my tree that does Yes, there is an explicit non-handling of symbolic ranges for PLUS_EXPR and MINUS_EXPR in VRP (extract_range_from_binary_expr_1) and the patch works around it by propagating the code instead of the ranges, which is far easier and sufficient here. If you think that the way to go is to handle symbolic ranges for PLUS_EXPR and MINUS_EXPR instead, fine with me, I can try. -- Eric Botcazou
Re: [RFC] optimize x - y cmp 0 with undefined overflow
On Mon, May 26, 2014 at 12:22 PM, Eric Botcazou wrote:
> Hi,
>
> the motivation of this work is to get rid of the range check on Z in:
>
> function F (X : Integer; Y : Integer ) return Positive is
>Z : Integer;
> begin
>if X >= Y then
> return 1;
>end if;
>Z := Y - X;
>return Z;
> end;
>
> An equivalent C testcase is:
>
> extern void abort (void);
>
> int foo (int x, int y)
> {
> int z;
>
> if (x >= y)
> return 1;
>
> z = y - x;
> if (z <= 0)
> abort ();
>
> return z;
> }
>
> for which the call to abort is not optimized at -O2.
>
>
> fold_comparison knows how to optimize X +- C1 CMP C2 to X CMP C2 -+ C1 with
> undefined overflow so optimizing X - Y CMP 0 to X CMP Y is a generalization.
>
> Once this is done, forwprop will immediately optimize:
>
> extern void abort (void);
>
> int foo (int x, int y)
> {
> int z;
>
> if (x >= y)
> return 1;
>
> z = y - x;
> if (z <= 0)
> abort ();
>
> return 0;
> }
>
> because 'z' has a single use, but the original testcase won't be optimized.
>
>
> The attached patch implements the missing bits in vrp_evaluate_conditional by
> manual propagating the operands of a defining PLUS_EXPR or MINUS_EXPR for an
> SSA name in a condition; an other possibility could be DOM instead of VRP.
>
> This comes with 4 testcases: the original Ada testcase, the C equivalent, a
> testcase for the folding and another one for the -Wstrict-overflow warning.
>
> Tested on x86_64-suse-linux with no regressions.
+ tree new_const
+ = fold_build2_loc (loc, reverse_op, TREE_TYPE (arg1), const2, const1);
/* If the constant operation overflowed this can be
simplified as a comparison against INT_MAX/INT_MIN. */
- if (TREE_CODE (lhs) == INTEGER_CST
- && TREE_OVERFLOW (lhs))
+ if (TREE_OVERFLOW (new_const))
well, either use int_const_binop above or retain the check (or use
TREE_OVERFLOW_P). Bonus points for using wide-ints here
and not relying on TREE_OVERFLOW.
+ /* Transform comparisons of the form X - Y CMP 0 to X CMP Y. */
+ if (TREE_CODE (arg0) == MINUS_EXPR
+ && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (arg1))
any good reason for using TYPE_OVERFLOW_UNDEFINED on the
type of arg1 instead on the type of the MINUS (yes, they should
match, but it really looks odd ... the overflow of the minus has to be
undefined). Also for EQ_EXPR and NE_EXPR the transform is
fine even when !TYPE_OVERFLOW_UNDEFINED (and we seem
to perform it already somewhere). Please look where and try to
add the undefined overflow case to it.
As for the VRP pieces I don't understand what is missing here
(well, compare_range_with_value and/or compare_values might
not handle this case? then better fix that to improve symbolic
range handling in general?). Also I have a longstanding patch
in my tree that does
Index: gcc/tree-vrp.c
===
--- gcc/tree-vrp.c (revision 210931)
+++ gcc/tree-vrp.c (working copy)
@@ -6919,14 +6919,15 @@ vrp_evaluate_conditional_warnv_with_ops_
vr0 = (TREE_CODE (op0) == SSA_NAME) ? get_value_range (op0) : NULL;
vr1 = (TREE_CODE (op1) == SSA_NAME) ? get_value_range (op1) : NULL;
+ tree res = NULL_TREE;
if (vr0 && vr1)
-return compare_ranges (code, vr0, vr1, strict_overflow_p);
- else if (vr0 && vr1 == NULL)
-return compare_range_with_value (code, vr0, op1, strict_overflow_p);
- else if (vr0 == NULL && vr1)
-return (compare_range_with_value
+res = compare_ranges (code, vr0, vr1, strict_overflow_p);
+ if (!res && vr0)
+res = compare_range_with_value (code, vr0, op1, strict_overflow_p);
+ if (!res && vr1)
+res = (compare_range_with_value
(swap_tree_comparison (code), vr1, op0, strict_overflow_p));
- return NULL;
+ return res;
}
/* Helper function for vrp_evaluate_conditional_warnv. */
maybe that helps as well.
Thanks,
Richard.
>
> 2014-05-26 Eric Botcazou
>
> * fold-const.c (fold_comparison): Clean up and simplify X +- C1 CMP C2
> to X CMP C2 -+ C1 transformation, add X - Y CMP 0 to X CMP Y.
> * tree-vrp.c (vrp_evaluate_conditional_warnv_with_fold): New function.
> (vrp_evaluate_conditional): Call it on SSA names with defining
> PLUS_EXPR
> or MINUS_EXPR if the evaluation of the condition yielded nothing.
>
>
> 2014-05-26 Eric Botcazou
>
> * gcc.dg/fold-compare-8.c: New test.
> * gcc.dg/Wstrict-overflow-25.c: Likewise.
> * gcc.dg/tree-ssa/vrp92.c: Likewise.
> * gnat.dg/opt38.adb: Likewise.
>
>
> --
> Eric Botcazou
[RFC] optimize x - y cmp 0 with undefined overflow
Hi,
the motivation of this work is to get rid of the range check on Z in:
function F (X : Integer; Y : Integer ) return Positive is
Z : Integer;
begin
if X >= Y then
return 1;
end if;
Z := Y - X;
return Z;
end;
An equivalent C testcase is:
extern void abort (void);
int foo (int x, int y)
{
int z;
if (x >= y)
return 1;
z = y - x;
if (z <= 0)
abort ();
return z;
}
for which the call to abort is not optimized at -O2.
fold_comparison knows how to optimize X +- C1 CMP C2 to X CMP C2 -+ C1 with
undefined overflow so optimizing X - Y CMP 0 to X CMP Y is a generalization.
Once this is done, forwprop will immediately optimize:
extern void abort (void);
int foo (int x, int y)
{
int z;
if (x >= y)
return 1;
z = y - x;
if (z <= 0)
abort ();
return 0;
}
because 'z' has a single use, but the original testcase won't be optimized.
The attached patch implements the missing bits in vrp_evaluate_conditional by
manual propagating the operands of a defining PLUS_EXPR or MINUS_EXPR for an
SSA name in a condition; an other possibility could be DOM instead of VRP.
This comes with 4 testcases: the original Ada testcase, the C equivalent, a
testcase for the folding and another one for the -Wstrict-overflow warning.
Tested on x86_64-suse-linux with no regressions.
2014-05-26 Eric Botcazou
* fold-const.c (fold_comparison): Clean up and simplify X +- C1 CMP C2
to X CMP C2 -+ C1 transformation, add X - Y CMP 0 to X CMP Y.
* tree-vrp.c (vrp_evaluate_conditional_warnv_with_fold): New function.
(vrp_evaluate_conditional): Call it on SSA names with defining PLUS_EXPR
or MINUS_EXPR if the evaluation of the condition yielded nothing.
2014-05-26 Eric Botcazou
* gcc.dg/fold-compare-8.c: New test.
* gcc.dg/Wstrict-overflow-25.c: Likewise.
* gcc.dg/tree-ssa/vrp92.c: Likewise.
* gnat.dg/opt38.adb: Likewise.
--
Eric BotcazouIndex: fold-const.c
===
--- fold-const.c (revision 210911)
+++ fold-const.c (working copy)
@@ -8920,28 +8920,25 @@ fold_comparison (location_t loc, enum tr
if (tree_swap_operands_p (arg0, arg1, true))
return fold_build2_loc (loc, swap_tree_comparison (code), type, op1, op0);
- /* Transform comparisons of the form X +- C1 CMP C2 to X CMP C2 +- C1. */
+ /* Transform comparisons of the form X +- C1 CMP C2 to X CMP C2 -+ C1. */
if ((TREE_CODE (arg0) == PLUS_EXPR || TREE_CODE (arg0) == MINUS_EXPR)
- && (TREE_CODE (TREE_OPERAND (arg0, 1)) == INTEGER_CST
- && !TREE_OVERFLOW (TREE_OPERAND (arg0, 1))
- && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (arg1)))
- && (TREE_CODE (arg1) == INTEGER_CST
- && !TREE_OVERFLOW (arg1)))
+ && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (arg1))
+ && TREE_CODE (TREE_OPERAND (arg0, 1)) == INTEGER_CST
+ && !TREE_OVERFLOW (TREE_OPERAND (arg0, 1))
+ && TREE_CODE (arg1) == INTEGER_CST
+ && !TREE_OVERFLOW (arg1))
{
+ const enum tree_code
+ reverse_op = TREE_CODE (arg0) == PLUS_EXPR ? MINUS_EXPR : PLUS_EXPR;
tree const1 = TREE_OPERAND (arg0, 1);
tree const2 = arg1;
tree variable = TREE_OPERAND (arg0, 0);
- tree lhs;
- int lhs_add;
- lhs_add = TREE_CODE (arg0) != PLUS_EXPR;
-
- lhs = fold_build2_loc (loc, lhs_add ? PLUS_EXPR : MINUS_EXPR,
- TREE_TYPE (arg1), const2, const1);
+ tree new_const
+ = fold_build2_loc (loc, reverse_op, TREE_TYPE (arg1), const2, const1);
/* If the constant operation overflowed this can be
simplified as a comparison against INT_MAX/INT_MIN. */
- if (TREE_CODE (lhs) == INTEGER_CST
- && TREE_OVERFLOW (lhs))
+ if (TREE_OVERFLOW (new_const))
{
int const1_sgn = tree_int_cst_sgn (const1);
enum tree_code code2 = code;
@@ -8961,29 +8958,48 @@ fold_comparison (location_t loc, enum tr
/* We now can look at the canonicalized case
VARIABLE + 1 CODE2 INT_MIN
and decide on the result. */
- if (code2 == LT_EXPR
- || code2 == LE_EXPR
- || code2 == EQ_EXPR)
- return omit_one_operand_loc (loc, type, boolean_false_node, variable);
- else if (code2 == NE_EXPR
- || code2 == GE_EXPR
- || code2 == GT_EXPR)
- return omit_one_operand_loc (loc, type, boolean_true_node, variable);
+ switch (code2)
+ {
+ case EQ_EXPR:
+ case LT_EXPR:
+ case LE_EXPR:
+ return
+ omit_one_operand_loc (loc, type, boolean_false_node, variable);
+
+ case NE_EXPR:
+ case GE_EXPR:
+ case GT_EXPR:
+ return
+ omit_one_operand_loc (loc, type, boolean_true_node, variable);
+
+ default:
+ gcc_unreachable ();
+ }
}
-
- if (TREE_CODE (lhs) == TREE_CODE (arg1)
- && (TREE_CODE (lhs) != INTEGER_CST
- || !TREE_OVERFLOW (lhs)))
+ else
{
if (code != EQ_EXPR && code != NE_EXPR)
fold_overflow_warning ("assuming signed overflow does not occur "
