* [RFC] optimize x - y cmp 0 with undefined overflow
@ 2014-05-26 10:24 Eric Botcazou
2014-05-26 12:55 ` Richard Biener
0 siblings, 1 reply; 18+ messages in thread
From: Eric Botcazou @ 2014-05-26 10:24 UTC (permalink / raw)
To: gcc-patches
[-- Attachment #1: Type: text/plain, Size: 1967 bytes --]
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 <ebotcazou@adacore.com>
* 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 <ebotcazou@adacore.com>
* 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
[-- Attachment #2: p1.diff --]
[-- Type: text/x-patch, Size: 7233 bytes --]
Index: 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 "
"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
+ && TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (arg1))
+ && integer_zerop (arg1))
+ {
+ if (code != EQ_EXPR && code != NE_EXPR)
+ 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
Index: tree-vrp.c
===================================================================
--- tree-vrp.c (revision 210911)
+++ tree-vrp.c (working copy)
@@ -6966,6 +6966,46 @@ vrp_evaluate_conditional_warnv_with_ops
return NULL_TREE;
}
+/* Helper function for vrp_evaluate_conditional_warnv. */
+
+static tree
+vrp_evaluate_conditional_warnv_with_fold (gimple stmt, enum tree_code code,
+ tree op0, tree op1,
+ bool use_equiv_p,
+ bool *strict_overflow_p,
+ bool *only_ranges)
+{
+ const location_t loc = gimple_location (stmt);
+
+ fold_defer_overflow_warnings ();
+
+ tree t = fold_binary_loc (loc, code, boolean_type_node, op0, op1);
+ if (!t
+ || !COMPARISON_CLASS_P (t)
+ || !is_gimple_val (TREE_OPERAND (t, 0))
+ || !is_gimple_val (TREE_OPERAND (t, 1)))
+ {
+ fold_undefer_overflow_warnings (false, NULL, 0);
+ return NULL_TREE;
+ }
+
+ tree ret = vrp_evaluate_conditional_warnv_with_ops (TREE_CODE (t),
+ TREE_OPERAND (t, 0),
+ TREE_OPERAND (t, 1),
+ use_equiv_p,
+ strict_overflow_p,
+ only_ranges);
+ if (!ret)
+ {
+ fold_undefer_overflow_warnings (false, NULL, 0);
+ return NULL_TREE;
+ }
+
+ fold_undefer_overflow_warnings (!gimple_no_warning_p (stmt), stmt, 0);
+
+ return ret;
+}
+
/* Given (CODE OP0 OP1) within STMT, try to simplify it based on value range
information. Return NULL if the conditional can not be evaluated.
The ranges of all the names equivalent with the operands in COND
@@ -6992,6 +7032,47 @@ vrp_evaluate_conditional (enum tree_code
ret = vrp_evaluate_conditional_warnv_with_ops (code, op0, op1, true, &sop,
&only_ranges);
+ /* The propagation machinery doesn't handle symbolic ranges in conjunction
+ with PLUS_EXPR or MINUS_EXPR so we try to jump over them by propagating
+ their operands instead. */
+ if (!ret
+ && TREE_CODE (op0) == SSA_NAME
+ && is_gimple_assign (SSA_NAME_DEF_STMT (op0)))
+ {
+ gimple def_stmt = SSA_NAME_DEF_STMT (op0);
+ enum tree_code def_code = gimple_assign_rhs_code (def_stmt);
+ if (def_code == PLUS_EXPR || def_code == MINUS_EXPR)
+ {
+ tree new_op0 = fold_build2_loc (gimple_location (def_stmt),
+ def_code, TREE_TYPE (op0),
+ gimple_assign_rhs1 (def_stmt),
+ gimple_assign_rhs2 (def_stmt));
+ ret = vrp_evaluate_conditional_warnv_with_fold (stmt, code,
+ new_op0, op1,
+ true, &sop,
+ &only_ranges);
+ }
+ }
+
+ if (!ret
+ && TREE_CODE (op1) == SSA_NAME
+ && is_gimple_assign (SSA_NAME_DEF_STMT (op1)))
+ {
+ gimple def_stmt = SSA_NAME_DEF_STMT (op1);
+ enum tree_code def_code = gimple_assign_rhs_code (def_stmt);
+ if (def_code == PLUS_EXPR || def_code == MINUS_EXPR)
+ {
+ tree new_op1 = fold_build2_loc (gimple_location (def_stmt),
+ def_code, TREE_TYPE (op1),
+ gimple_assign_rhs1 (def_stmt),
+ gimple_assign_rhs2 (def_stmt));
+ ret = vrp_evaluate_conditional_warnv_with_fold (stmt, code,
+ op0, new_op1,
+ true, &sop,
+ &only_ranges);
+ }
+ }
+
if (ret && sop)
{
enum warn_strict_overflow_code wc;
[-- Attachment #3: fold-compare-8.c --]
[-- Type: text/x-csrc, Size: 229 bytes --]
/* { dg-do compile } */
/* { dg-options "-O2 -fdump-tree-original" } */
int
foo (int x, int y)
{
return x - y < 0;
}
/* { dg-final { scan-tree-dump "x < y" "original" } } */
/* { dg-final { cleanup-tree-dump "original" } } */
[-- Attachment #4: Wstrict-overflow-25.c --]
[-- Type: text/x-csrc, Size: 303 bytes --]
/* { dg-do compile } */
/* { dg-options "-fstrict-overflow -O2 -Wstrict-overflow=3" } */
/* We can only simplify the conditional when using strict overflow
semantics. */
int
foo (int x, int y)
{
return x - y < 0; /* { dg-warning "assuming signed overflow does not occur" "correct warning" } */
}
[-- Attachment #5: vrp92.c --]
[-- Type: text/x-csrc, Size: 336 bytes --]
/* { dg-do compile } */
/* { dg-options "-O2 -fdump-tree-optimized" } */
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;
}
/* { dg-final { scan-tree-dump-not "abort" "optimized" } } */
/* { dg-final { cleanup-tree-dump "optimized" } } */
[-- Attachment #6: opt38.adb --]
[-- Type: text/x-adasrc, Size: 347 bytes --]
-- { 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" } }
^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: [RFC] optimize x - y cmp 0 with undefined overflow
2014-05-26 10:24 [RFC] optimize x - y cmp 0 with undefined overflow Eric Botcazou
@ 2014-05-26 12:55 ` Richard Biener
2014-05-27 9:26 ` Eric Botcazou
0 siblings, 1 reply; 18+ messages in thread
From: Richard Biener @ 2014-05-26 12:55 UTC (permalink / raw)
To: Eric Botcazou; +Cc: GCC Patches
On Mon, May 26, 2014 at 12:22 PM, Eric Botcazou <ebotcazou@adacore.com> 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 <ebotcazou@adacore.com>
>
> * 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 <ebotcazou@adacore.com>
>
> * 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
^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: [RFC] optimize x - y cmp 0 with undefined overflow
2014-05-26 12:55 ` Richard Biener
@ 2014-05-27 9:26 ` Eric Botcazou
2014-05-27 9:42 ` Richard Biener
0 siblings, 1 reply; 18+ messages in thread
From: Eric Botcazou @ 2014-05-27 9:26 UTC (permalink / raw)
To: Richard Biener; +Cc: gcc-patches
> + 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
^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: [RFC] optimize x - y cmp 0 with undefined overflow
2014-05-27 9:26 ` Eric Botcazou
@ 2014-05-27 9:42 ` Richard Biener
2014-05-27 10:00 ` Eric Botcazou
2014-05-27 16:14 ` Eric Botcazou
0 siblings, 2 replies; 18+ messages in thread
From: Richard Biener @ 2014-05-27 9:42 UTC (permalink / raw)
To: Eric Botcazou; +Cc: GCC Patches
On Tue, May 27, 2014 at 11:25 AM, Eric Botcazou <ebotcazou@adacore.com> 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
^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: [RFC] optimize x - y cmp 0 with undefined overflow
2014-05-27 9:42 ` Richard Biener
@ 2014-05-27 10:00 ` Eric Botcazou
2014-05-27 10:12 ` Richard Biener
2014-05-27 16:14 ` Eric Botcazou
1 sibling, 1 reply; 18+ messages in thread
From: Eric Botcazou @ 2014-05-27 10:00 UTC (permalink / raw)
To: Richard Biener; +Cc: gcc-patches
> 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
^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: [RFC] optimize x - y cmp 0 with undefined overflow
2014-05-27 10:00 ` Eric Botcazou
@ 2014-05-27 10:12 ` Richard Biener
2014-05-30 8:49 ` Eric Botcazou
0 siblings, 1 reply; 18+ messages in thread
From: Richard Biener @ 2014-05-27 10:12 UTC (permalink / raw)
To: Eric Botcazou; +Cc: GCC Patches
On Tue, May 27, 2014 at 11:59 AM, Eric Botcazou <ebotcazou@adacore.com> 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
^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: [RFC] optimize x - y cmp 0 with undefined overflow
2014-05-27 9:42 ` Richard Biener
2014-05-27 10:00 ` Eric Botcazou
@ 2014-05-27 16:14 ` Eric Botcazou
2014-05-27 16:19 ` Richard Biener
1 sibling, 1 reply; 18+ messages in thread
From: Eric Botcazou @ 2014-05-27 16:14 UTC (permalink / raw)
To: Richard Biener; +Cc: gcc-patches
[-- Attachment #1: Type: text/plain, Size: 631 bytes --]
> 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 <ebotcazou@adacore.com>
* 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) <EQ_EXPR/NE_EXPR>: Remove same transformations.
2014-05-27 Eric Botcazou <ebotcazou@adacore.com>
* gcc.dg/fold-compare-8.c: New test.
* gcc.dg/Wstrict-overflow-25.c: Likewise.
--
Eric Botcazou
[-- Attachment #2: p.diff --]
[-- Type: text/x-patch, Size: 6975 bytes --]
Index: 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, enum tr
|| POINTER_TYPE_OVERFLOW_UNDEFINED))
{
- if (code != EQ_EXPR
- && code != NE_EXPR
+ if (!equality_code
&& bitpos0 != bitpos1
&& (pointer_may_wrap_p (base0, offset0, bitpos0)
|| pointer_may_wrap_p (base1, offset1, bitpos1)))
@@ -9146,7 +9161,7 @@ fold_comparison (location_t loc, enum tr
object and overflow on pointer differences is undefined as of
6.5.6/8 and /9 with respect to the signed ptrdiff_t. */
else if (bitpos0 == bitpos1
- && ((code == EQ_EXPR || code == NE_EXPR)
+ && (equality_code
|| (indirect_base0 && DECL_P (base0))
|| POINTER_TYPE_OVERFLOW_UNDEFINED))
{
@@ -9164,8 +9179,7 @@ fold_comparison (location_t loc, enum tr
else
offset1 = fold_convert_loc (loc, ssizetype, offset1);
- if (code != EQ_EXPR
- && code != NE_EXPR
+ if (!equality_code
&& (pointer_may_wrap_p (base0, offset0, bitpos0)
|| pointer_may_wrap_p (base1, offset1, bitpos1)))
fold_overflow_warning (("assuming pointer wraparound does not "
@@ -12888,21 +12902,6 @@ fold_binary_loc (location_t loc,
type);
}
- /* If this is an EQ or NE comparison of a constant with a PLUS_EXPR or
- a MINUS_EXPR of a constant, we can convert it into a comparison with
- a revised constant as long as no overflow occurs. */
- if (TREE_CODE (arg1) == INTEGER_CST
- && (TREE_CODE (arg0) == PLUS_EXPR
- || TREE_CODE (arg0) == MINUS_EXPR)
- && TREE_CODE (TREE_OPERAND (arg0, 1)) == INTEGER_CST
- && 0 != (tem = const_binop (TREE_CODE (arg0) == PLUS_EXPR
- ? MINUS_EXPR : PLUS_EXPR,
- fold_convert_loc (loc, TREE_TYPE (arg0),
- arg1),
- TREE_OPERAND (arg0, 1)))
- && !TREE_OVERFLOW (tem))
- return fold_build2_loc (loc, code, type, TREE_OPERAND (arg0, 0), tem);
-
/* Similarly for a NEGATE_EXPR. */
if (TREE_CODE (arg0) == NEGATE_EXPR
&& TREE_CODE (arg1) == INTEGER_CST
@@ -12956,13 +12955,6 @@ fold_binary_loc (location_t loc,
TREE_OPERAND (arg0, 1), arg1);
}
- /* If we have X - Y == 0, we can convert that to X == Y and similarly
- for !=. Don't do this for ordered comparisons due to overflow. */
- if (TREE_CODE (arg0) == MINUS_EXPR
- && integer_zerop (arg1))
- return fold_build2_loc (loc, code, type,
- TREE_OPERAND (arg0, 0), TREE_OPERAND (arg0, 1));
-
/* Convert ABS_EXPR<x> == 0 or ABS_EXPR<x> != 0 to x == 0 or x != 0. */
if (TREE_CODE (arg0) == ABS_EXPR
&& (integer_zerop (arg1) || real_zerop (arg1)))
^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: [RFC] optimize x - y cmp 0 with undefined overflow
2014-05-27 16:14 ` Eric Botcazou
@ 2014-05-27 16:19 ` Richard Biener
0 siblings, 0 replies; 18+ messages in thread
From: Richard Biener @ 2014-05-27 16:19 UTC (permalink / raw)
To: Eric Botcazou; +Cc: gcc-patches
On May 27, 2014 6:12:58 PM CEST, Eric Botcazou <ebotcazou@adacore.com> 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 <ebotcazou@adacore.com>
>
> * 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) <EQ_EXPR/NE_EXPR>: Remove same transformations.
>
>
>2014-05-27 Eric Botcazou <ebotcazou@adacore.com>
>
> * gcc.dg/fold-compare-8.c: New test.
> * gcc.dg/Wstrict-overflow-25.c: Likewise.
^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: [RFC] optimize x - y cmp 0 with undefined overflow
2014-05-27 10:12 ` Richard Biener
@ 2014-05-30 8:49 ` Eric Botcazou
2014-06-02 10:36 ` Richard Biener
0 siblings, 1 reply; 18+ messages in thread
From: Eric Botcazou @ 2014-05-30 8:49 UTC (permalink / raw)
To: Richard Biener; +Cc: gcc-patches
[-- Attachment #1: Type: text/plain, Size: 1208 bytes --]
> 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 <ebotcazou@adacore.com>
* 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 <ebotcazou@adacore.com>
* gcc.dg/tree-ssa/vrp93.c: New test.
* gnat.dg/opt38.adb: Likewise.
--
Eric Botcazou
[-- Attachment #2: vrp_symbolic.diff --]
[-- Type: text/x-patch, Size: 14750 bytes --]
Index: 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.type == VR_VARYING
|| vr1.type == VR_VARYING
|| vr0.type != vr1.type
@@ -2376,50 +2466,115 @@ extract_range_from_binary_expr_1 (value_
range and see what we end up with. */
if (code == PLUS_EXPR || code == MINUS_EXPR)
{
- /* If we have a PLUS_EXPR with two VR_RANGE integer constant
- ranges compute the precise range for such case if possible. */
- if (range_int_cst_p (&vr0)
- && range_int_cst_p (&vr1))
- {
- signop sgn = TYPE_SIGN (expr_type);
- unsigned int prec = TYPE_PRECISION (expr_type);
- wide_int type_min = wi::min_value (TYPE_PRECISION (expr_type), sgn);
- wide_int type_max = wi::max_value (TYPE_PRECISION (expr_type), sgn);
- wide_int wmin, wmax;
+ const bool minus_p = (code == MINUS_EXPR);
+ tree min_op0 = vr0.min;
+ tree min_op1 = minus_p ? vr1.max : vr1.min;
+ tree max_op0 = vr0.max;
+ tree max_op1 = minus_p ? vr1.min : vr1.max;
+ tree sym_min_op0 = NULL_TREE;
+ tree sym_min_op1 = NULL_TREE;
+ tree sym_max_op0 = NULL_TREE;
+ tree sym_max_op1 = NULL_TREE;
+ bool neg_min_op0, neg_min_op1, neg_max_op0, neg_max_op1;
+
+ /* If we have a PLUS or MINUS with two VR_RANGEs, either constant or
+ single-symbolic ranges, try to compute the precise resulting range,
+ but only if we know that this resulting range will also be constant
+ or single-symbolic. */
+ if (vr0.type == VR_RANGE && vr1.type == VR_RANGE
+ && (TREE_CODE (min_op0) == INTEGER_CST
+ || (sym_min_op0
+ = get_single_symbol (min_op0, &neg_min_op0, &min_op0)))
+ && (TREE_CODE (min_op1) == INTEGER_CST
+ || (sym_min_op1
+ = get_single_symbol (min_op1, &neg_min_op1, &min_op1)))
+ && (!(sym_min_op0 && sym_min_op1)
+ || (sym_min_op0 == sym_min_op1
+ && neg_min_op0 == (minus_p ? neg_min_op1 : !neg_min_op1)))
+ && (TREE_CODE (max_op0) == INTEGER_CST
+ || (sym_max_op0
+ = get_single_symbol (max_op0, &neg_max_op0, &max_op0)))
+ && (TREE_CODE (max_op1) == INTEGER_CST
+ || (sym_max_op1
+ = get_single_symbol (max_op1, &neg_max_op1, &max_op1)))
+ && (!(sym_max_op0 && sym_max_op1)
+ || (sym_max_op0 == sym_max_op1
+ && neg_max_op0 == (minus_p ? neg_max_op1 : !neg_max_op1))))
+ {
+ const signop sgn = TYPE_SIGN (expr_type);
+ const unsigned int prec = TYPE_PRECISION (expr_type);
+ wide_int type_min, type_max, wmin, wmax;
int min_ovf = 0;
int max_ovf = 0;
- if (code == PLUS_EXPR)
+ /* Get the lower and upper bounds of the type. */
+ if (TYPE_OVERFLOW_WRAPS (expr_type))
{
- wmin = wi::add (vr0.min, vr1.min);
- wmax = wi::add (vr0.max, vr1.max);
-
- /* Check for overflow. */
- if (wi::cmp (vr1.min, 0, sgn) != wi::cmp (wmin, vr0.min, sgn))
- min_ovf = wi::cmp (vr0.min, wmin, sgn);
- if (wi::cmp (vr1.max, 0, sgn) != wi::cmp (wmax, vr0.max, sgn))
- max_ovf = wi::cmp (vr0.max, wmax, sgn);
+ type_min = wi::min_value (prec, sgn);
+ type_max = wi::max_value (prec, sgn);
}
- else /* if (code == MINUS_EXPR) */
+ else
{
- wmin = wi::sub (vr0.min, vr1.max);
- wmax = wi::sub (vr0.max, vr1.min);
+ type_min = vrp_val_min (expr_type);
+ type_max = vrp_val_max (expr_type);
+ }
- if (wi::cmp (0, vr1.max, sgn) != wi::cmp (wmin, vr0.min, sgn))
- min_ovf = wi::cmp (vr0.min, vr1.max, sgn);
- if (wi::cmp (0, vr1.min, sgn) != wi::cmp (wmax, vr0.max, sgn))
- max_ovf = wi::cmp (vr0.max, vr1.min, sgn);
+ /* Combine the lower bounds, if any. */
+ if (min_op0 && min_op1)
+ {
+ if (minus_p)
+ {
+ wmin = wi::sub (min_op0, min_op1);
+
+ /* Check for overflow. */
+ if (wi::cmp (0, min_op1, sgn)
+ != wi::cmp (wmin, min_op0, sgn))
+ min_ovf = wi::cmp (min_op0, min_op1, sgn);
+ }
+ else
+ {
+ wmin = wi::add (min_op0, min_op1);
+
+ /* Check for overflow. */
+ if (wi::cmp (min_op1, 0, sgn)
+ != wi::cmp (wmin, min_op0, sgn))
+ min_ovf = wi::cmp (min_op0, wmin, sgn);
+ }
}
+ else if (min_op0)
+ wmin = min_op0;
+ else if (min_op1)
+ wmin = minus_p ? wi::neg (min_op1) : min_op1;
+ else
+ wmin = wi::shwi (0, prec);
- /* For non-wrapping arithmetic look at possibly smaller
- value-ranges of the type. */
- if (!TYPE_OVERFLOW_WRAPS (expr_type))
+ /* Combine the upper bounds, if any. */
+ if (max_op0 && max_op1)
{
- if (vrp_val_min (expr_type))
- type_min = vrp_val_min (expr_type);
- if (vrp_val_max (expr_type))
- type_max = vrp_val_max (expr_type);
+ if (minus_p)
+ {
+ wmax = wi::sub (max_op0, max_op1);
+
+ /* Check for overflow. */
+ if (wi::cmp (0, max_op1, sgn)
+ != wi::cmp (wmax, max_op0, sgn))
+ max_ovf = wi::cmp (max_op0, max_op1, sgn);
+ }
+ else
+ {
+ wmax = wi::add (max_op0, max_op1);
+
+ if (wi::cmp (max_op1, 0, sgn)
+ != wi::cmp (wmax, max_op0, sgn))
+ max_ovf = wi::cmp (max_op0, wmax, sgn);
+ }
}
+ else if (max_op0)
+ wmax = max_op0;
+ else if (max_op1)
+ wmax = minus_p ? wi::neg (max_op1) : max_op1;
+ else
+ wmax = wi::shwi (0, prec);
/* Check for type overflow. */
if (min_ovf == 0)
@@ -2437,6 +2592,15 @@ extract_range_from_binary_expr_1 (value_
max_ovf = 1;
}
+ /* If we have overflow for the constant part and the resulting
+ range will be symbolic, drop to VR_VARYING. */
+ if ((min_ovf && sym_min_op0 != sym_min_op1)
+ || (max_ovf && sym_max_op0 != sym_max_op1))
+ {
+ set_value_range_to_varying (vr);
+ return;
+ }
+
if (TYPE_OVERFLOW_WRAPS (expr_type))
{
/* If overflow wraps, truncate the values and adjust the
@@ -2450,8 +2614,7 @@ extract_range_from_binary_expr_1 (value_
min = wide_int_to_tree (expr_type, tmin);
max = wide_int_to_tree (expr_type, tmax);
}
- else if (min_ovf == -1
- && max_ovf == 1)
+ else if (min_ovf == -1 && max_ovf == 1)
{
/* Underflow and overflow, drop to VR_VARYING. */
set_value_range_to_varying (vr);
@@ -2526,20 +2689,44 @@ extract_range_from_binary_expr_1 (value_
else
max = wide_int_to_tree (expr_type, wmax);
}
+
if (needs_overflow_infinity (expr_type)
&& supports_overflow_infinity (expr_type))
{
- if (is_negative_overflow_infinity (vr0.min)
- || (code == PLUS_EXPR
- ? is_negative_overflow_infinity (vr1.min)
- : is_positive_overflow_infinity (vr1.max)))
+ if ((min_op0 && is_negative_overflow_infinity (min_op0))
+ || (min_op1
+ && (minus_p
+ ? is_positive_overflow_infinity (min_op1)
+ : is_negative_overflow_infinity (min_op1))))
min = negative_overflow_infinity (expr_type);
- if (is_positive_overflow_infinity (vr0.max)
- || (code == PLUS_EXPR
- ? is_positive_overflow_infinity (vr1.max)
- : is_negative_overflow_infinity (vr1.min)))
+ if ((max_op0 && is_positive_overflow_infinity (max_op0))
+ || (max_op1
+ && (minus_p
+ ? is_negative_overflow_infinity (max_op1)
+ : is_positive_overflow_infinity (max_op1))))
max = positive_overflow_infinity (expr_type);
}
+
+ /* If the result lower bound is constant, we're done;
+ otherwise, build the symbolic lower bound. */
+ if (sym_min_op0 == sym_min_op1)
+ ;
+ else if (sym_min_op0)
+ min = build_symbolic_expr (expr_type, sym_min_op0,
+ neg_min_op0, min);
+ else if (sym_min_op1)
+ min = build_symbolic_expr (expr_type, sym_min_op1,
+ neg_min_op1 ^ minus_p, min);
+
+ /* Likewise for the upper bound. */
+ if (sym_max_op0 == sym_max_op1)
+ ;
+ else if (sym_max_op0)
+ max = build_symbolic_expr (expr_type, sym_max_op0,
+ neg_max_op0, max);
+ else if (sym_max_op1)
+ max = build_symbolic_expr (expr_type, sym_max_op1,
+ neg_max_op1 ^ minus_p, max);
}
else
{
@@ -3024,14 +3211,11 @@ extract_range_from_binary_expr_1 (value_
gcc_unreachable ();
/* If either MIN or MAX overflowed, then set the resulting range to
- VARYING. But we do accept an overflow infinity
- representation. */
+ VARYING. But we do accept an overflow infinity representation. */
if (min == NULL_TREE
- || !is_gimple_min_invariant (min)
- || (TREE_OVERFLOW (min) && !is_overflow_infinity (min))
+ || (TREE_OVERFLOW_P (min) && !is_overflow_infinity (min))
|| max == NULL_TREE
- || !is_gimple_min_invariant (max)
- || (TREE_OVERFLOW (max) && !is_overflow_infinity (max)))
+ || (TREE_OVERFLOW_P (max) && !is_overflow_infinity (max)))
{
set_value_range_to_varying (vr);
return;
@@ -3093,6 +3277,58 @@ extract_range_from_binary_expr (value_ra
set_value_range_to_varying (&vr1);
extract_range_from_binary_expr_1 (vr, code, expr_type, &vr0, &vr1);
+
+ /* Try harder for PLUS and MINUS if the range of one operand is symbolic
+ and based on the other operand. */
+ if (vr->type == VR_VARYING
+ && (code == PLUS_EXPR || code == MINUS_EXPR)
+ && TREE_CODE (op1) == SSA_NAME
+ && vr0.type == VR_RANGE
+ && symbolic_range_based_on_p (&vr0, op1))
+ {
+ value_range_t new_vr1 = VR_INITIALIZER;
+
+ /* 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;
+
+ /* Try with VR0 and [OP1, OP1]. */
+ set_value_range (&new_vr1, VR_RANGE, op1, op1, NULL);
+ extract_range_from_binary_expr_1 (vr, code, expr_type, &vr0, &new_vr1);
+ }
+
+ if (vr->type == VR_VARYING
+ && (code == PLUS_EXPR || code == MINUS_EXPR)
+ && TREE_CODE (op0) == SSA_NAME
+ && vr1.type == VR_RANGE
+ && symbolic_range_based_on_p (&vr1, op0))
+ {
+ value_range_t new_vr0 = VR_INITIALIZER;
+
+ /* Try with [-INF, OP0] and VR1. */
+ set_value_range (&new_vr0, VR_RANGE, vrp_val_min (expr_type), op0, NULL);
+ extract_range_from_binary_expr_1 (vr, code, expr_type, &new_vr0, &vr1);
+ if (vr->type != VR_VARYING)
+ return;
+
+ /* Try with [OP0, +INF] and VR1. */
+ set_value_range (&new_vr0, VR_RANGE, op0, vrp_val_max (expr_type), NULL);
+ extract_range_from_binary_expr_1 (vr, code, expr_type, &new_vr0, &vr1);
+ if (vr->type != VR_VARYING)
+ return;
+
+ /* Try with [OP0, OP0] and VR1. */
+ set_value_range (&new_vr0, VR_RANGE, op0, op0, NULL);
+ extract_range_from_binary_expr_1 (vr, code, expr_type, &new_vr0, &vr1);
+ }
}
/* Extract range information from a unary operation CODE based on
^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: [RFC] optimize x - y cmp 0 with undefined overflow
2014-05-30 8:49 ` Eric Botcazou
@ 2014-06-02 10:36 ` Richard Biener
2014-06-02 10:37 ` Richard Biener
2014-06-03 8:13 ` Eric Botcazou
0 siblings, 2 replies; 18+ messages in thread
From: Richard Biener @ 2014-06-02 10:36 UTC (permalink / raw)
To: Eric Botcazou; +Cc: GCC Patches
On Fri, May 30, 2014 at 10:48 AM, Eric Botcazou <ebotcazou@adacore.com> 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 <ebotcazou@adacore.com>
>
> * 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 <ebotcazou@adacore.com>
>
> * gcc.dg/tree-ssa/vrp93.c: New test.
> * gnat.dg/opt38.adb: Likewise.
>
>
> --
> Eric Botcazou
^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: [RFC] optimize x - y cmp 0 with undefined overflow
2014-06-02 10:36 ` Richard Biener
@ 2014-06-02 10:37 ` Richard Biener
2014-06-03 8:13 ` Eric Botcazou
1 sibling, 0 replies; 18+ messages in thread
From: Richard Biener @ 2014-06-02 10:37 UTC (permalink / raw)
To: Eric Botcazou; +Cc: GCC Patches
On Mon, Jun 2, 2014 at 12:36 PM, Richard Biener
<richard.guenther@gmail.com> wrote:
> On Fri, May 30, 2014 at 10:48 AM, Eric Botcazou <ebotcazou@adacore.com> 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 <ebotcazou@adacore.com>
>>
>> * 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 <ebotcazou@adacore.com>
>>
>> * gcc.dg/tree-ssa/vrp93.c: New test.
>> * gnat.dg/opt38.adb: Likewise.
>>
>>
>> --
>> Eric Botcazou
^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: [RFC] optimize x - y cmp 0 with undefined overflow
2014-06-02 10:36 ` Richard Biener
2014-06-02 10:37 ` Richard Biener
@ 2014-06-03 8:13 ` Eric Botcazou
2014-06-03 11:00 ` Richard Biener
1 sibling, 1 reply; 18+ messages in thread
From: Eric Botcazou @ 2014-06-03 8:13 UTC (permalink / raw)
To: Richard Biener; +Cc: gcc-patches
[-- Attachment #1: Type: text/plain, Size: 3699 bytes --]
> 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
[-- Attachment #2: opt38.adb --]
[-- Type: text/x-adasrc, Size: 345 bytes --]
-- { 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" } }
[-- Attachment #3: vrp93.c --]
[-- Type: text/x-csrc, Size: 495 bytes --]
/* { 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" } } */
^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: [RFC] optimize x - y cmp 0 with undefined overflow
2014-06-03 8:13 ` Eric Botcazou
@ 2014-06-03 11:00 ` Richard Biener
2014-06-06 10:54 ` Eric Botcazou
0 siblings, 1 reply; 18+ messages in thread
From: Richard Biener @ 2014-06-03 11:00 UTC (permalink / raw)
To: Eric Botcazou; +Cc: GCC Patches
On Tue, Jun 3, 2014 at 10:11 AM, Eric Botcazou <ebotcazou@adacore.com> 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
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.
I'd say ok with that change and only trying [op0,op0] and [op1,op1].
Thanks,
Richard.
>
> 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.
Heh ;)
> --
> Eric Botcazou
^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: [RFC] optimize x - y cmp 0 with undefined overflow
2014-06-03 11:00 ` Richard Biener
@ 2014-06-06 10:54 ` Eric Botcazou
2014-06-06 15:45 ` Richard Biener
0 siblings, 1 reply; 18+ messages in thread
From: Eric Botcazou @ 2014-06-06 10:54 UTC (permalink / raw)
To: Richard Biener; +Cc: gcc-patches
> 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
^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: [RFC] optimize x - y cmp 0 with undefined overflow
2014-06-06 10:54 ` Eric Botcazou
@ 2014-06-06 15:45 ` Richard Biener
2014-06-20 9:40 ` Eric Botcazou
0 siblings, 1 reply; 18+ messages in thread
From: Richard Biener @ 2014-06-06 15:45 UTC (permalink / raw)
To: Eric Botcazou; +Cc: GCC Patches
On Fri, Jun 6, 2014 at 12:52 PM, Eric Botcazou <ebotcazou@adacore.com> 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
^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: [RFC] optimize x - y cmp 0 with undefined overflow
2014-06-06 15:45 ` Richard Biener
@ 2014-06-20 9:40 ` Eric Botcazou
2014-06-24 10:34 ` Richard Biener
0 siblings, 1 reply; 18+ messages in thread
From: Eric Botcazou @ 2014-06-20 9:40 UTC (permalink / raw)
To: Richard Biener; +Cc: gcc-patches
[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
^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: [RFC] optimize x - y cmp 0 with undefined overflow
2014-06-20 9:40 ` Eric Botcazou
@ 2014-06-24 10:34 ` Richard Biener
2014-09-29 23:01 ` Eric Botcazou
0 siblings, 1 reply; 18+ messages in thread
From: Richard Biener @ 2014-06-24 10:34 UTC (permalink / raw)
To: Eric Botcazou; +Cc: GCC Patches
On Fri, Jun 20, 2014 at 11:33 AM, Eric Botcazou <ebotcazou@adacore.com> 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
^ permalink raw reply [flat|nested] 18+ messages in thread
* Re: [RFC] optimize x - y cmp 0 with undefined overflow
2014-06-24 10:34 ` Richard Biener
@ 2014-09-29 23:01 ` Eric Botcazou
0 siblings, 0 replies; 18+ messages in thread
From: Eric Botcazou @ 2014-09-29 23:01 UTC (permalink / raw)
To: Richard Biener; +Cc: gcc-patches
[-- Attachment #1: Type: text/plain, Size: 741 bytes --]
> 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 <ebotcazou@adacore.com>
* 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 <ebotcazou@adacore.com>
* gcc.dg/tree-ssa/vrp94.c: New test.
* gnat.dg/opt40.adb: Likewise.
--
Eric Botcazou
[-- Attachment #2: vrp_symbolic-2.diff --]
[-- Type: text/x-patch, Size: 16928 bytes --]
Index: 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)
+ {
+ n1 = TREE_OPERAND (n1, 0);
+ n2 = TREE_OPERAND (n2, 0);
+ }
if (n1 != n2)
return -2;
- if (code1 == SSA_NAME
- && code2 == SSA_NAME)
+ if (code1 == SSA_NAME && code2 == SSA_NAME)
/* NAME == NAME */
return 0;
@@ -2209,7 +2310,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 +2404,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 +2420,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.type == VR_VARYING
|| vr1.type == VR_VARYING
|| vr0.type != vr1.type
@@ -2376,50 +2480,115 @@ extract_range_from_binary_expr_1 (value_
range and see what we end up with. */
if (code == PLUS_EXPR || code == MINUS_EXPR)
{
- /* If we have a PLUS_EXPR with two VR_RANGE integer constant
- ranges compute the precise range for such case if possible. */
- if (range_int_cst_p (&vr0)
- && range_int_cst_p (&vr1))
- {
- signop sgn = TYPE_SIGN (expr_type);
- unsigned int prec = TYPE_PRECISION (expr_type);
- wide_int type_min = wi::min_value (TYPE_PRECISION (expr_type), sgn);
- wide_int type_max = wi::max_value (TYPE_PRECISION (expr_type), sgn);
- wide_int wmin, wmax;
+ const bool minus_p = (code == MINUS_EXPR);
+ tree min_op0 = vr0.min;
+ tree min_op1 = minus_p ? vr1.max : vr1.min;
+ tree max_op0 = vr0.max;
+ tree max_op1 = minus_p ? vr1.min : vr1.max;
+ tree sym_min_op0 = NULL_TREE;
+ tree sym_min_op1 = NULL_TREE;
+ tree sym_max_op0 = NULL_TREE;
+ tree sym_max_op1 = NULL_TREE;
+ bool neg_min_op0, neg_min_op1, neg_max_op0, neg_max_op1;
+
+ /* If we have a PLUS or MINUS with two VR_RANGEs, either constant or
+ single-symbolic ranges, try to compute the precise resulting range,
+ but only if we know that this resulting range will also be constant
+ or single-symbolic. */
+ if (vr0.type == VR_RANGE && vr1.type == VR_RANGE
+ && (TREE_CODE (min_op0) == INTEGER_CST
+ || (sym_min_op0
+ = get_single_symbol (min_op0, &neg_min_op0, &min_op0)))
+ && (TREE_CODE (min_op1) == INTEGER_CST
+ || (sym_min_op1
+ = get_single_symbol (min_op1, &neg_min_op1, &min_op1)))
+ && (!(sym_min_op0 && sym_min_op1)
+ || (sym_min_op0 == sym_min_op1
+ && neg_min_op0 == (minus_p ? neg_min_op1 : !neg_min_op1)))
+ && (TREE_CODE (max_op0) == INTEGER_CST
+ || (sym_max_op0
+ = get_single_symbol (max_op0, &neg_max_op0, &max_op0)))
+ && (TREE_CODE (max_op1) == INTEGER_CST
+ || (sym_max_op1
+ = get_single_symbol (max_op1, &neg_max_op1, &max_op1)))
+ && (!(sym_max_op0 && sym_max_op1)
+ || (sym_max_op0 == sym_max_op1
+ && neg_max_op0 == (minus_p ? neg_max_op1 : !neg_max_op1))))
+ {
+ const signop sgn = TYPE_SIGN (expr_type);
+ const unsigned int prec = TYPE_PRECISION (expr_type);
+ wide_int type_min, type_max, wmin, wmax;
int min_ovf = 0;
int max_ovf = 0;
- if (code == PLUS_EXPR)
+ /* Get the lower and upper bounds of the type. */
+ if (TYPE_OVERFLOW_WRAPS (expr_type))
{
- wmin = wi::add (vr0.min, vr1.min);
- wmax = wi::add (vr0.max, vr1.max);
-
- /* Check for overflow. */
- if (wi::cmp (vr1.min, 0, sgn) != wi::cmp (wmin, vr0.min, sgn))
- min_ovf = wi::cmp (vr0.min, wmin, sgn);
- if (wi::cmp (vr1.max, 0, sgn) != wi::cmp (wmax, vr0.max, sgn))
- max_ovf = wi::cmp (vr0.max, wmax, sgn);
+ type_min = wi::min_value (prec, sgn);
+ type_max = wi::max_value (prec, sgn);
}
- else /* if (code == MINUS_EXPR) */
+ else
{
- wmin = wi::sub (vr0.min, vr1.max);
- wmax = wi::sub (vr0.max, vr1.min);
+ type_min = vrp_val_min (expr_type);
+ type_max = vrp_val_max (expr_type);
+ }
- if (wi::cmp (0, vr1.max, sgn) != wi::cmp (wmin, vr0.min, sgn))
- min_ovf = wi::cmp (vr0.min, vr1.max, sgn);
- if (wi::cmp (0, vr1.min, sgn) != wi::cmp (wmax, vr0.max, sgn))
- max_ovf = wi::cmp (vr0.max, vr1.min, sgn);
+ /* Combine the lower bounds, if any. */
+ if (min_op0 && min_op1)
+ {
+ if (minus_p)
+ {
+ wmin = wi::sub (min_op0, min_op1);
+
+ /* Check for overflow. */
+ if (wi::cmp (0, min_op1, sgn)
+ != wi::cmp (wmin, min_op0, sgn))
+ min_ovf = wi::cmp (min_op0, min_op1, sgn);
+ }
+ else
+ {
+ wmin = wi::add (min_op0, min_op1);
+
+ /* Check for overflow. */
+ if (wi::cmp (min_op1, 0, sgn)
+ != wi::cmp (wmin, min_op0, sgn))
+ min_ovf = wi::cmp (min_op0, wmin, sgn);
+ }
}
+ else if (min_op0)
+ wmin = min_op0;
+ else if (min_op1)
+ wmin = minus_p ? wi::neg (min_op1) : min_op1;
+ else
+ wmin = wi::shwi (0, prec);
- /* For non-wrapping arithmetic look at possibly smaller
- value-ranges of the type. */
- if (!TYPE_OVERFLOW_WRAPS (expr_type))
+ /* Combine the upper bounds, if any. */
+ if (max_op0 && max_op1)
{
- if (vrp_val_min (expr_type))
- type_min = vrp_val_min (expr_type);
- if (vrp_val_max (expr_type))
- type_max = vrp_val_max (expr_type);
+ if (minus_p)
+ {
+ wmax = wi::sub (max_op0, max_op1);
+
+ /* Check for overflow. */
+ if (wi::cmp (0, max_op1, sgn)
+ != wi::cmp (wmax, max_op0, sgn))
+ max_ovf = wi::cmp (max_op0, max_op1, sgn);
+ }
+ else
+ {
+ wmax = wi::add (max_op0, max_op1);
+
+ if (wi::cmp (max_op1, 0, sgn)
+ != wi::cmp (wmax, max_op0, sgn))
+ max_ovf = wi::cmp (max_op0, wmax, sgn);
+ }
}
+ else if (max_op0)
+ wmax = max_op0;
+ else if (max_op1)
+ wmax = minus_p ? wi::neg (max_op1) : max_op1;
+ else
+ wmax = wi::shwi (0, prec);
/* Check for type overflow. */
if (min_ovf == 0)
@@ -2437,6 +2606,15 @@ extract_range_from_binary_expr_1 (value_
max_ovf = 1;
}
+ /* If we have overflow for the constant part and the resulting
+ range will be symbolic, drop to VR_VARYING. */
+ if ((min_ovf && sym_min_op0 != sym_min_op1)
+ || (max_ovf && sym_max_op0 != sym_max_op1))
+ {
+ set_value_range_to_varying (vr);
+ return;
+ }
+
if (TYPE_OVERFLOW_WRAPS (expr_type))
{
/* If overflow wraps, truncate the values and adjust the
@@ -2450,8 +2628,7 @@ extract_range_from_binary_expr_1 (value_
min = wide_int_to_tree (expr_type, tmin);
max = wide_int_to_tree (expr_type, tmax);
}
- else if (min_ovf == -1
- && max_ovf == 1)
+ else if (min_ovf == -1 && max_ovf == 1)
{
/* Underflow and overflow, drop to VR_VARYING. */
set_value_range_to_varying (vr);
@@ -2526,20 +2703,44 @@ extract_range_from_binary_expr_1 (value_
else
max = wide_int_to_tree (expr_type, wmax);
}
+
if (needs_overflow_infinity (expr_type)
&& supports_overflow_infinity (expr_type))
{
- if (is_negative_overflow_infinity (vr0.min)
- || (code == PLUS_EXPR
- ? is_negative_overflow_infinity (vr1.min)
- : is_positive_overflow_infinity (vr1.max)))
+ if ((min_op0 && is_negative_overflow_infinity (min_op0))
+ || (min_op1
+ && (minus_p
+ ? is_positive_overflow_infinity (min_op1)
+ : is_negative_overflow_infinity (min_op1))))
min = negative_overflow_infinity (expr_type);
- if (is_positive_overflow_infinity (vr0.max)
- || (code == PLUS_EXPR
- ? is_positive_overflow_infinity (vr1.max)
- : is_negative_overflow_infinity (vr1.min)))
+ if ((max_op0 && is_positive_overflow_infinity (max_op0))
+ || (max_op1
+ && (minus_p
+ ? is_negative_overflow_infinity (max_op1)
+ : is_positive_overflow_infinity (max_op1))))
max = positive_overflow_infinity (expr_type);
}
+
+ /* If the result lower bound is constant, we're done;
+ otherwise, build the symbolic lower bound. */
+ if (sym_min_op0 == sym_min_op1)
+ ;
+ else if (sym_min_op0)
+ min = build_symbolic_expr (expr_type, sym_min_op0,
+ neg_min_op0, min);
+ else if (sym_min_op1)
+ min = build_symbolic_expr (expr_type, sym_min_op1,
+ neg_min_op1 ^ minus_p, min);
+
+ /* Likewise for the upper bound. */
+ if (sym_max_op0 == sym_max_op1)
+ ;
+ else if (sym_max_op0)
+ max = build_symbolic_expr (expr_type, sym_max_op0,
+ neg_max_op0, max);
+ else if (sym_max_op1)
+ max = build_symbolic_expr (expr_type, sym_max_op1,
+ neg_max_op1 ^ minus_p, max);
}
else
{
@@ -3024,14 +3225,11 @@ extract_range_from_binary_expr_1 (value_
gcc_unreachable ();
/* If either MIN or MAX overflowed, then set the resulting range to
- VARYING. But we do accept an overflow infinity
- representation. */
+ VARYING. But we do accept an overflow infinity representation. */
if (min == NULL_TREE
- || !is_gimple_min_invariant (min)
- || (TREE_OVERFLOW (min) && !is_overflow_infinity (min))
+ || (TREE_OVERFLOW_P (min) && !is_overflow_infinity (min))
|| max == NULL_TREE
- || !is_gimple_min_invariant (max)
- || (TREE_OVERFLOW (max) && !is_overflow_infinity (max)))
+ || (TREE_OVERFLOW_P (max) && !is_overflow_infinity (max)))
{
set_value_range_to_varying (vr);
return;
@@ -3093,6 +3291,59 @@ extract_range_from_binary_expr (value_ra
set_value_range_to_varying (&vr1);
extract_range_from_binary_expr_1 (vr, code, expr_type, &vr0, &vr1);
+
+ /* Try harder for PLUS and MINUS if the range of one operand is symbolic
+ and based on the other operand, for example if it was deduced from a
+ symbolic comparison. When a bound of the range of the first operand
+ is invariant, we set the corresponding bound of the new range to INF
+ in order to avoid recursing on the range of the second operand. */
+ if (vr->type == VR_VARYING
+ && (code == PLUS_EXPR || code == MINUS_EXPR)
+ && TREE_CODE (op1) == SSA_NAME
+ && vr0.type == VR_RANGE
+ && symbolic_range_based_on_p (&vr0, op1))
+ {
+ const bool minus_p = (code == MINUS_EXPR);
+ value_range_t n_vr1 = VR_INITIALIZER;
+
+ /* Try with VR0 and [-INF, OP1]. */
+ if (is_gimple_min_invariant (minus_p ? vr0.max : vr0.min))
+ set_value_range (&n_vr1, VR_RANGE, vrp_val_min (expr_type), op1, NULL);
+
+ /* Try with VR0 and [OP1, +INF]. */
+ else if (is_gimple_min_invariant (minus_p ? vr0.min : vr0.max))
+ set_value_range (&n_vr1, VR_RANGE, op1, vrp_val_max (expr_type), NULL);
+
+ /* Try with VR0 and [OP1, OP1]. */
+ else
+ set_value_range (&n_vr1, VR_RANGE, op1, op1, NULL);
+
+ extract_range_from_binary_expr_1 (vr, code, expr_type, &vr0, &n_vr1);
+ }
+
+ if (vr->type == VR_VARYING
+ && (code == PLUS_EXPR || code == MINUS_EXPR)
+ && TREE_CODE (op0) == SSA_NAME
+ && vr1.type == VR_RANGE
+ && symbolic_range_based_on_p (&vr1, op0))
+ {
+ const bool minus_p = (code == MINUS_EXPR);
+ value_range_t n_vr0 = VR_INITIALIZER;
+
+ /* Try with [-INF, OP0] and VR1. */
+ if (is_gimple_min_invariant (minus_p ? vr1.max : vr1.min))
+ set_value_range (&n_vr0, VR_RANGE, vrp_val_min (expr_type), op0, NULL);
+
+ /* Try with [OP0, +INF] and VR1. */
+ else if (is_gimple_min_invariant (minus_p ? vr1.min : vr1.max))
+ set_value_range (&n_vr0, VR_RANGE, op0, vrp_val_max (expr_type), NULL);
+
+ /* Try with [OP0, OP0] and VR1. */
+ else
+ set_value_range (&n_vr0, VR_RANGE, op0, op0, NULL);
+
+ extract_range_from_binary_expr_1 (vr, code, expr_type, &n_vr0, &vr1);
+ }
}
/* Extract range information from a unary operation CODE based on
[-- Attachment #3: vrp94.c --]
[-- Type: text/x-csrc, Size: 496 bytes --]
/* { 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" } } */
[-- Attachment #4: opt40.adb --]
[-- Type: text/x-adasrc, Size: 380 bytes --]
-- { dg-do compile }
-- { dg-options "-O2 -fdump-tree-optimized" }
pragma Suppress (Overflow_Check);
function Opt40 (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" } }
^ permalink raw reply [flat|nested] 18+ messages in thread
end of thread, other threads:[~2014-09-29 23:01 UTC | newest]
Thread overview: 18+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2014-05-26 10:24 [RFC] optimize x - y cmp 0 with undefined overflow Eric Botcazou
2014-05-26 12:55 ` Richard Biener
2014-05-27 9:26 ` Eric Botcazou
2014-05-27 9:42 ` Richard Biener
2014-05-27 10:00 ` Eric Botcazou
2014-05-27 10:12 ` Richard Biener
2014-05-30 8:49 ` Eric Botcazou
2014-06-02 10:36 ` Richard Biener
2014-06-02 10:37 ` Richard Biener
2014-06-03 8:13 ` Eric Botcazou
2014-06-03 11:00 ` Richard Biener
2014-06-06 10:54 ` Eric Botcazou
2014-06-06 15:45 ` Richard Biener
2014-06-20 9:40 ` Eric Botcazou
2014-06-24 10:34 ` Richard Biener
2014-09-29 23:01 ` Eric Botcazou
2014-05-27 16:14 ` Eric Botcazou
2014-05-27 16:19 ` Richard Biener
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).