This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[RFC] optimize x - y cmp 0 with undefined overflow
- From: Eric Botcazou <ebotcazou at adacore dot com>
- To: gcc-patches at gcc dot gnu dot org
- Date: Mon, 26 May 2014 12:22:01 +0200
- Subject: [RFC] optimize x - y cmp 0 with undefined overflow
- Authentication-results: sourceware.org; auth=none
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 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 "
"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;/* { 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" } } *//* { 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" } */
}/* { 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" } } */-- { 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" } }