Ping.
diff --git a/gcc/gimple-match-head.c b/gcc/gimple-match-head.c index 2beadbc..d66fcb1 100644 --- a/gcc/gimple-match-head.c +++ b/gcc/gimple-match-head.c @@ -39,6 +39,7 @@ along with GCC; see the file COPYING3. If not see #include "internal-fn.h" #include "case-cfn-macros.h" #include "gimplify.h" +#include "tree-vrp.h" /* Forward declarations of the private auto-generated matchers. diff --git a/gcc/match.pd b/gcc/match.pd index b24bfb4..f54b734 100644 --- a/gcc/match.pd +++ b/gcc/match.pd @@ -1119,6 +1119,113 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT) (minus @0 (minus @0 @1)) @1) + /* ((T)(A +- CST)) +- CST -> (T)(A) +- CST) */ +#if GIMPLE + (for outer_op (plus minus) + (for inner_op (plus minus) + (simplify + (outer_op (convert (inner_op@3 @0 INTEGER_CST@1)) INTEGER_CST@2) + (with + { + /* If the inner operation is wrapped inside a conversion, we have to + check it overflows/underflows and can only then perform the + simplification, i.e. add the second constant to the first + (wrapped) and convert afterwards. This fixes + https://gcc.gnu.org/bugzilla/show_bug.cgi?id=69526 */ + bool inner_ovf = false; + + bool combine_ovf = true; + tree cst = NULL_TREE; + bool combine_constants = false; + bool types_ok = false; + + tree inner_type = TREE_TYPE (@3); + /* Check overflow in wrapped binop? */ + bool check_inner_ovf = !TYPE_OVERFLOW_UNDEFINED (inner_type); + /* Check overflow when combining constants? */ + bool check_combine_ovf = TYPE_OVERFLOW_UNDEFINED (type); + + signop s1 = TYPE_SIGN (type); + + if (TYPE_PRECISION (type) >= TYPE_PRECISION (inner_type)) + { + types_ok = true; + + /* Check if the inner binop does not overflow i.e. we have VRP + information and can prove prove it. */ + if (check_inner_ovf) + inner_ovf = binop_overflow (inner_op, @0, @1, inner_type); + else + inner_ovf = false; + + wide_int w1 = @1; + wide_int w2 = @2; + + wide_int combined_cst; + + /* Convert to TYPE keeping possible signedness even when + dealing with unsigned types. */ + wide_int v1; + v1 = v1.from (w1, w2.get_precision(), tree_int_cst_sign_bit + (@1) ? SIGNED : UNSIGNED); + + if (inner_op == MINUS_EXPR) + w1 = wi::neg (w1); + + if (outer_op == MINUS_EXPR) + w2 = wi::neg (w2); + + /* Combine in outer, larger type */ + combined_cst = wi::add (v1, w2, TYPE_SIGN (type), &combine_ovf); + + /* The combined constant is ok if its type does not exhibit + undefined overflow or there was no overflow when + combining. */ + bool combined_cst_ok = !check_combine_ovf || !combine_ovf; + if (!inner_ovf && combined_cst_ok) + { + /* convert to tree of outer type */ + cst = wide_int_to_tree (type, combined_cst); + combine_constants = true; + } + } + } + (if (types_ok && combine_constants && cst) + (outer_op (convert { @0; }) { cst; })) + )))) +#endif + + /* ((T)(A)) +- CST -> (T)(A +- CST) */ +#if GIMPLE + (for outer_op (plus minus) + (simplify + (outer_op (convert @0) INTEGER_CST@2) + /* Perform binary operation inside the cast if the constant fits + and there is no overflow. */ + (with + { + bool simplify = false; + + wide_int cst = @2; + tree inner_type = TREE_TYPE (@0); + tree cst_inner = wide_int_to_tree (inner_type, cst); + bool inner_ovf = true; + + if (TYPE_PRECISION (inner_type) >= TYPE_PRECISION (type) + || TREE_CODE (inner_type) != INTEGER_TYPE) + simplify = false; + else + { + inner_ovf = binop_overflow (outer_op, @0, cst_inner, inner_type); + if (!inner_ovf) + simplify = true; + } + } + (if (simplify && @0) + (convert (outer_op @0 (convert { @2; })))) + ))) +#endif + /* (A +- CST) +- CST -> A + CST */ (for outer_op (plus minus) (for inner_op (plus minus) @@ -1132,6 +1239,7 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT) (if (cst && !TREE_OVERFLOW (cst)) (inner_op @0 { cst; } )))))) + /* (CST - A) +- CST -> CST - A */ (for outer_op (plus minus) (simplify diff --git a/gcc/testsuite/gcc.dg/wrapped-binop-simplify-signed-1.c b/gcc/testsuite/gcc.dg/wrapped-binop-simplify-signed-1.c new file mode 100644 index 0000000..0afe99a --- /dev/null +++ b/gcc/testsuite/gcc.dg/wrapped-binop-simplify-signed-1.c @@ -0,0 +1,76 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-forwprop1-details" } */ +/* { dg-final { scan-tree-dump-times "gimple_simplified to" 11 "forwprop1" } } */ + +#include <limits.h> + +// should simplify, ignore possible signed overflow in (a - 2) and combine +// constants +long foo(int a) +{ + return (long)(a - 2) + 1; +} + +// should simplify +long bar(int a) +{ + return (long)(a + 3) - 1; +} + +// should simplify with combined constant in outer type +long baz(int a) +{ + return (long)(a - 1) + 2; +} + +// should simplify +long baf(int a) +{ + return (long)(a + 1) - 2; +} + +// should simplify (same as above) +long bak(int a) +{ + return (long)(a + 1) + 3; +} + +// should simplify (same) +long bal(int a) +{ + return (long)(a - 7) - 4; +} + +// should simplify with combined constant in inner type, no overflow in +// combined constant in inner type (1 - INT_MAX) although it looks like it :) +long bam(int a) +{ + return (long)(a - 1) - INT_MAX; +} + +// should simplify with combined constant in outer type, overflow in +// combined constant in inner type +long bam2(int a) +{ + return (long)(a + 1) + INT_MAX; +} + +// should simplify with combined constant in outer type, overflow in +// combined constant in inner type +long ban(int a) +{ + return (long)(a - 1) + INT_MIN; +} + +// should simplify with combined constant in outer type, overflow in +// combined constant in inner type +long ban2(int a) +{ + return (long)(a + 1) - INT_MIN; +} + +// should simplify, assumes no inner overflow +unsigned long baq(int a) +{ + return (unsigned long)(a + 1) - 1; +} diff --git a/gcc/testsuite/gcc.dg/wrapped-binop-simplify-signed-2.c b/gcc/testsuite/gcc.dg/wrapped-binop-simplify-signed-2.c new file mode 100644 index 0000000..9b166f6 --- /dev/null +++ b/gcc/testsuite/gcc.dg/wrapped-binop-simplify-signed-2.c @@ -0,0 +1,26 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-forwprop1-details -fdump-tree-vrp1-details" } */ +/* { dg-final { scan-tree-dump-times "gimple_simplified to" 0 "forwprop1" } } */ +/* { dg-final { scan-tree-dump-times "gimple_simplified to" 0 "vrp1" } } */ + +#include <limits.h> +#include <assert.h> + +// should not simplify, 2 + LONG_MAX overflows +long bao(int a) +{ + return (long)(a + 2) + LONG_MAX; +} + +// should not simplify +long bar(int a) +{ + return (long)(a - 2) - LONG_MAX; +} + +// should not simplify although at first looks like (long)(a - 1) + 1 on +// tree level, but a is promoted to long +long bas(int a) +{ + return (long)(a + UINT_MAX) + 1; +} diff --git a/gcc/testsuite/gcc.dg/wrapped-binop-simplify-unsigned-1.c b/gcc/testsuite/gcc.dg/wrapped-binop-simplify-unsigned-1.c new file mode 100644 index 0000000..fb0463d --- /dev/null +++ b/gcc/testsuite/gcc.dg/wrapped-binop-simplify-unsigned-1.c @@ -0,0 +1,48 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-forwprop1-details -fdump-tree-vrp1-details" } */ +/* { dg-final { scan-tree-dump-times "gimple_simplified to" 1 "forwprop1" } } */ +/* { dg-final { scan-tree-dump-times "gimple_simplified to" 5 "vrp1" } } */ + +#include <limits.h> + +// should simplify (same as above with VRP) +unsigned long oof2(unsigned int a) +{ + if (a > 3 && a < INT_MAX - 100) + return (unsigned long)(a - 1) + 1; +} + +// same +unsigned long bap(unsigned int a) +{ + if (a > 3 && a < INT_MAX - 100) + return (unsigned long)(a + 1) + ULONG_MAX; +} + +// should simplify +unsigned long bar3(unsigned int a) +{ + if (a > 3 && a < INT_MAX - 100) + return (unsigned long)(a + 1) - 5; +} + +// should simplify in outer type as we cannot prove non-overflow +unsigned long bar4(unsigned int a) +{ + if (a > 3 && a < INT_MAX - 100) + return (unsigned long)(a + 1) - 6; +} + +// should simplify +unsigned long baq(int a) +{ + return (unsigned long)(a - 2) + 1; +} + +// should simplify +long baq3(unsigned int a) +{ + if (a > 3 && a < INT_MAX - 100) + return (long)(a - 1) + 1; +} + diff --git a/gcc/testsuite/gcc.dg/wrapped-binop-simplify-unsigned-2.c b/gcc/testsuite/gcc.dg/wrapped-binop-simplify-unsigned-2.c new file mode 100644 index 0000000..3843b6d --- /dev/null +++ b/gcc/testsuite/gcc.dg/wrapped-binop-simplify-unsigned-2.c @@ -0,0 +1,29 @@ +/* { dg-do run } */ +/* { dg-options "-O2" } */ + +#include <assert.h> +#include <limits.h> + +unsigned int a = 3; +unsigned int aa = UINT_MAX; + +int main() +{ + volatile unsigned long b = (unsigned long)(aa + 1) - 1; + assert (b == 18446744073709551615ul); + + volatile unsigned long c = (unsigned long)(a - 4) + 1; + assert (c == 4294967296); + + volatile unsigned long d = (unsigned long)(a + UINT_MAX - 4) + 2; + assert (d == 4294967296); + + volatile unsigned long e = (unsigned long)(a - UINT_MAX) + UINT_MAX; + assert (e == 4294967299); + + volatile unsigned long f = (unsigned long)(a + UINT_MAX) - UINT_MAX; + assert (f == 18446744069414584323ul); + + volatile long g = (long)(a - 4) + 1; + assert (g == 4294967296); +} diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c index 4333d60..f9bf2d4 100644 --- a/gcc/tree-vrp.c +++ b/gcc/tree-vrp.c @@ -3231,6 +3231,109 @@ extract_range_from_binary_expr (value_range *vr, } } +/* Check if the binary operation overflows. */ +bool binop_overflow (enum tree_code op, tree t1, tree t2, tree type) +{ + if (t1 == NULL_TREE || t2 == NULL_TREE || type == NULL_TREE) + return true; + + if (TREE_CODE (type) != INTEGER_TYPE) + return true; + + if (TREE_CODE (t1) != SSA_NAME) + return true; + + if (op != PLUS_EXPR && op != MINUS_EXPR) + return true; + + wide_int min1; + wide_int max1; + signop st1 = TYPE_SIGN (TREE_TYPE (t1)); + + if (TREE_CODE (t1) != INTEGER_CST) + { + enum value_range_type vrtype1 = get_range_info (t1, &min1, &max1); + + if (!vrtype1 || (vrtype1 != VR_RANGE && vrtype1 != VR_ANTI_RANGE)) + return true; + + if (vrtype1 == VR_ANTI_RANGE) + { + bool ovf; + wide_int tmpmin = wi::add (min1, 1, st1, &ovf); + if (st1 == SIGNED && ovf) + return true; + wide_int tmpmax = wi::sub (max1, 1, st1, &ovf); + if (st1 == SIGNED && ovf) + return true; + min1 = tmpmin; + max1 = tmpmax; + } + } + else + { + min1 = t1; + max1 = t1; + } + + wide_int min2; + wide_int max2; + signop st2 = TYPE_SIGN (TREE_TYPE (t2)); + + if (TREE_CODE (t2) != INTEGER_CST) + { + enum value_range_type vrtype2 = get_range_info (t2, &min2, &max2); + + if (!vrtype2 || (vrtype2 != VR_RANGE && vrtype2 != VR_ANTI_RANGE)) + return true; + + if (vrtype2 == VR_ANTI_RANGE) + { + bool ovf; + wide_int tmpmin = wi::add (min2, 1, st2, &ovf); + if (st2 == SIGNED && ovf) + return true; + wide_int tmpmax = wi::sub (max2, 1, st2, &ovf); + if (st2 == SIGNED && ovf) + return true; + min2 = tmpmin; + max2 = tmpmax; + } + } + else + { + min2 = t2; + max2 = t2; + } + + wide_int wmin, wmax; + + bool ovf; + signop sgn = TYPE_SIGN (TREE_TYPE (t1)) == SIGNED + || TYPE_SIGN (TREE_TYPE (t2)) == SIGNED ? SIGNED : UNSIGNED; + if (op == MINUS_EXPR) + { + wmin = wi::sub (min1, min2, sgn, &ovf); + if (sgn == SIGNED && (ovf || wi::gt_p (wmin, min1, sgn))) + return true; + wmax = wi::sub (max1, max2, sgn, &ovf); + if (sgn == SIGNED && (ovf || wi::gt_p (wmax, max1, sgn))) + return true; + } + else + { + wmin = wi::add (min1, min2, sgn, &ovf); + if (sgn == SIGNED && (ovf || wi::lt_p (wmin, min1, sgn))) + return true; + wmax = wi::add (max1, max2, sgn, &ovf); + if (sgn == SIGNED && (ovf || wi::lt_p (wmax, max1, sgn))) + return true; + } + + return wi::gt_p (wmin, wmax, TYPE_SIGN (TREE_TYPE (t1))); +} + + /* Extract range information from a unary operation CODE based on the range of its operand *VR0 with type OP0_TYPE with resulting type TYPE. The resulting range is stored in *VR. */ @@ -8906,6 +9009,37 @@ simplify_truth_ops_using_ranges (gimple_stmt_iterator *gsi, gimple *stmt) return true; } +/* Simplify ((type) (b +- CST1)) + CST2 to (type) b + (CST1 + CST2) + if (b +- CST1) does not underflow. */ + +static bool +simplify_plus_or_minus_using_ranges (gimple_stmt_iterator *gsi, gimple *stmt) +{ + enum tree_code code = gimple_assign_rhs_code (stmt); + tree op0 = gimple_assign_rhs1 (stmt); + tree op1 = gimple_assign_rhs2 (stmt); + + if ((code == PLUS_EXPR || code == MINUS_EXPR) && + op0 != NULL && op1 != NULL) + { + gimple *stmt1 = SSA_NAME_DEF_STMT (op0); + if (gassign *def = dyn_cast <gassign *> (stmt1)) + { + if (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def)) + && TREE_CODE (op1) == INTEGER_CST) + { + /* Only mark the stmt as updated here, so fold_stmt in + tree-ssa-propagate will call the matching pattern in + match.pd. */ + update_stmt (gsi_stmt (*gsi)); + return true; + } + } + } + + return false; +} + /* Simplify a division or modulo operator to a right shift or bitwise and if the first operand is unsigned or is greater than zero and the second operand is an exact power of two. @@ -9905,6 +10039,12 @@ simplify_stmt_using_ranges (gimple_stmt_iterator *gsi) return simplify_min_or_max_using_ranges (stmt); break; + case MINUS_EXPR: + case PLUS_EXPR: + if (TREE_CODE (rhs1) == SSA_NAME) + return simplify_plus_or_minus_using_ranges (gsi, stmt); + break; + default: break; } diff --git a/gcc/tree-vrp.h b/gcc/tree-vrp.h new file mode 100644 index 0000000..5a867bc --- /dev/null +++ b/gcc/tree-vrp.h @@ -0,0 +1,2 @@ +extern bool +binop_overflow (enum tree_code op, tree t1, tree t2, tree type);