https://gcc.gnu.org/g:56c81c325cccf432954ddea4c73069e2fa047922
commit r17-4207-g56c81c325cccf432954ddea4c73069e2fa047922 Author: Dominic P <[email protected]> Date: Sun Sep 13 13:34:45 2026 -0600 [PATCH] match.pd: Fold ((X + C1) | (C2 - X)) < 0 to an unsigned range test The sign bit of (X + C1) | (C2 - X) is the disjunction of the two sign bits, so the test is X < -C1 || X > C2, that is (unsigned) (X + C1) > C1 + C2. With U for X + C1 and D for C1 + C2 the second operand is D - U, and for 0 <= D < 2 ** (prec - 1) the disjunction is negative exactly when U > D unsigned; D non-negative in the type is the only guard, and no no-overflow assumption is involved. D is tested with wi::ge_p (..., SIGNED), not tree_int_cst_sgn: after over_widening the constants have an unsigned type, for which tree_int_cst_sgn is 1 whatever the bit pattern. Matched in every spelling that reaches match.pd: the comparison, the comparison of a same-precision conversion of it (what narrow types and unsigned data reduce to), the sign-bit extraction x264 uses in encoder/cavlc.c, and the C1 == 0 and C2 == 0 forms, where the addition is absent and the subtraction is a negate. Those need matchers of their own: genmatch cannot make a binary operand optional, and negate does not fit a (for) with minus. The disjunction needs single_use, or both operands stay live and the fold only adds a compare (7 -> 9 x86_64). ABS_EXPR <X> > C and <= C are the same range test, and so is the ABSU_EXPR pair; ABSU_EXPR needs no assumption about the minimum value, ABS_EXPR needs TYPE_OVERFLOW_UNDEFINED. C == TYPE_MAX is left to the existing fold to a constant; == and != are not range tests and are untouched. The addition is built in the unsigned type, so the fold does not invent a signed overflow for the sanitizer to report. All of it is GIMPLE-only, as single_use is always true on GENERIC, and declines under -fsanitize=signed-integer-overflow, where the operand it drops carries a check. The nearest pattern, "Optimize (a | b) < 0 to a < 0 if b is non-negative", does not fire as neither operand is known non-negative. Not matched: ((X + C1) | ~X) < 0, spelled with a BIT_NOT_EXPR rather than a minus, and the arithmetic-shift 0/-1 mask spelling, which is also how vectors reach match.pd. aarch64 -O2: the x264 site 6 -> 4 insns, the range test 6 -> 4, abs > C 5 -> 4; x86_64 6 -> 5, 6 -> 5, 7 -> 5. Checked against a bit-exact model over every 16-bit X for 26 constant pairs in all four spellings, both ABS forms and ABSU_EXPR, and over 32-bit edge and random values. Bootstrapped and regression tested on x86_64-pc-linux-gnu. Assisted-by: Claude Opus 5 (Anthropic) gcc/ChangeLog: * match.pd (ior_range_test, ior_range_test_1, ior_range_test_0): New matchers. (((X + C1) | (C2 - X)) < 0): New simplification. ((unsigned) ((X + C1) | (C2 - X)) >> (prec - 1)): Likewise. (ABS_EXPR <X> > C): Likewise. gcc/testsuite/ChangeLog: * gcc.dg/torture/abs-gt-1.c: New test. * gcc.dg/torture/ior-range-test-1.c: New test. * gcc.dg/tree-ssa/ior-range-test-1.c: New test. * gcc.dg/tree-ssa/ior-range-test-2.c: New test. * gcc.dg/tree-ssa/ior-range-test-3.c: New test. Signed-off-by: Dominic P <[email protected]> Diff: --- gcc/match.pd | 76 ++++++++++++++++++++ gcc/testsuite/gcc.dg/torture/abs-gt-1.c | 38 ++++++++++ gcc/testsuite/gcc.dg/torture/ior-range-test-1.c | 57 +++++++++++++++ gcc/testsuite/gcc.dg/tree-ssa/ior-range-test-1.c | 29 ++++++++ gcc/testsuite/gcc.dg/tree-ssa/ior-range-test-2.c | 91 ++++++++++++++++++++++++ gcc/testsuite/gcc.dg/tree-ssa/ior-range-test-3.c | 17 +++++ 6 files changed, 308 insertions(+) diff --git a/gcc/match.pd b/gcc/match.pd index 3d7091e81b79..213b118da06a 100644 --- a/gcc/match.pd +++ b/gcc/match.pd @@ -5099,6 +5099,65 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT) (cmp (op:c @0 tree_expr_nonnegative_p@1) integer_zerop@2) (cmp @0 @2)))) +#if GIMPLE +/* ((X + C1) | (C2 - X)) < 0 -> (unsigned) (X + C1) > C1 + C2, also spelled + (X | (C2 - X)) < 0, ((X + C1) | -X) < 0 and (X | -X) < 0, and with the + sign bit extracted by a shift rather than compared. */ +(match (ior_range_test @0 @1 @2) + (bit_ior:c@3 (plus@0 @4 INTEGER_CST@1) (minus INTEGER_CST@2 @4)) + (if (single_use (@3) + && !TYPE_OVERFLOW_SANITIZED (TREE_TYPE (@0)) + && wi::ge_p (wi::to_wide (@1) + wi::to_wide (@2), 0, SIGNED)))) +(match (ior_range_test_1 @0 @1) + (bit_ior:c@2 @0 (minus INTEGER_CST@1 @0)) + (if (single_use (@2) + && !TYPE_OVERFLOW_SANITIZED (TREE_TYPE (@0)) + && wi::ge_p (wi::to_wide (@1), 0, SIGNED)))) +(match (ior_range_test_1 @0 @1) + (bit_ior:c@2 (plus@0 @3 INTEGER_CST@1) (negate @3)) + (if (single_use (@2) + && !TYPE_OVERFLOW_SANITIZED (TREE_TYPE (@0)) + && wi::ge_p (wi::to_wide (@1), 0, SIGNED)))) +(match (ior_range_test_0 @0) + (bit_ior:c@1 @0 (negate @0)) + (if (single_use (@1) + && !TYPE_OVERFLOW_SANITIZED (TREE_TYPE (@0))))) +(for cmp (lt ge) + out (gt le) + (simplify + (cmp (nop_convert?@5 (ior_range_test @0 @1 @2)) integer_zerop) + (if (!TYPE_UNSIGNED (TREE_TYPE (@5))) + (with { tree utype = unsigned_type_for (TREE_TYPE (@0)); } + (out (convert:utype @0) + { wide_int_to_tree (utype, wi::to_wide (@1) + wi::to_wide (@2)); })))) + (simplify + (cmp (nop_convert?@3 (ior_range_test_1 @0 @1)) integer_zerop) + (if (!TYPE_UNSIGNED (TREE_TYPE (@3))) + (with { tree utype = unsigned_type_for (TREE_TYPE (@0)); } + (out (convert:utype @0) (convert:utype @1))))) + (simplify + (cmp (nop_convert?@2 (ior_range_test_0 @0)) integer_zerop@3) + (if (!TYPE_UNSIGNED (TREE_TYPE (@2))) + (with { tree utype = unsigned_type_for (TREE_TYPE (@0)); } + (out (convert:utype @0) (convert:utype @3)))))) +(simplify + (rshift (nop_convert? (ior_range_test @0 @1 @2)) INTEGER_CST@5) + (if (TYPE_UNSIGNED (type) + && wi::to_wide (@5) == element_precision (type) - 1) + (convert (gt (convert:type @0) + { wide_int_to_tree (type, wi::to_wide (@1) + wi::to_wide (@2)); })))) +(simplify + (rshift (nop_convert? (ior_range_test_1 @0 @1)) INTEGER_CST@2) + (if (TYPE_UNSIGNED (type) + && wi::to_wide (@2) == element_precision (type) - 1) + (convert (gt (convert:type @0) (convert:type @1))))) +(simplify + (rshift (nop_convert? (ior_range_test_0 @0)) INTEGER_CST@1) + (if (TYPE_UNSIGNED (type) + && wi::to_wide (@1) == element_precision (type) - 1) + (convert (ne @0 { build_zero_cst (TREE_TYPE (@0)); })))) +#endif + /* Undo fancy ways of writing max/min or other ?: expressions, like a - ((a - b) & -(a < b)) and a - (a - b) * (a < b) into (a < b) ? b : a. People normally use ?: and that is what we actually try to optimize. */ @@ -8599,6 +8658,23 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT) (eqne (op @0) zerop@1) (eqne @0 { build_zero_cst (TREE_TYPE (@0)); })))) +#if GIMPLE +/* ABS_EXPR <X> > C -> (unsigned) (X + C) > 2 * C, and the same for <= and + for ABSU_EXPR. */ +(for op (abs absu) + (for cmp (gt le) + (simplify + (cmp (op@2 @0) INTEGER_CST@1) + (if ((op == ABSU_EXPR || TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (@0))) + && !TYPE_OVERFLOW_SANITIZED (TREE_TYPE (@0)) + && single_use (@2) + && wi::ge_p (wi::to_wide (@1), 0, SIGNED) + && !tree_int_cst_equal (@1, TYPE_MAX_VALUE (TREE_TYPE (@0)))) + (with { tree utype = unsigned_type_for (TREE_TYPE (@0)); } + (cmp (plus (convert:utype @0) (convert:utype @1)) + { wide_int_to_tree (utype, wi::to_wide (@1) * 2); })))))) +#endif + /* From fold_sign_changed_comparison and fold_widened_comparison. FIXME: the lack of symmetry is disturbing. */ (for cmp (simple_comparison) diff --git a/gcc/testsuite/gcc.dg/torture/abs-gt-1.c b/gcc/testsuite/gcc.dg/torture/abs-gt-1.c new file mode 100644 index 000000000000..41118ebb7ba7 --- /dev/null +++ b/gcc/testsuite/gcc.dg/torture/abs-gt-1.c @@ -0,0 +1,38 @@ +/* { dg-do run } */ +/* { dg-require-effective-target int32 } */ + +extern void abort (void); + +static int __attribute__((noipa)) +ref (int x, int c) +{ + long long l = x; + return (l < 0 ? -l : l) > c; +} + +static int __attribute__((noipa)) a1 (int x) { return __builtin_abs (x) > 5; } +static int __attribute__((noipa)) a2 (int x) { return __builtin_abs (x) >= 6; } +static int __attribute__((noipa)) a3 (int x) { return __builtin_abs (x) > 0; } +static int __attribute__((noipa)) a4 (int x) { return __builtin_abs (x) > 0x3fffffff; } +static int __attribute__((noipa)) a5 (int x) { return __builtin_abs (x) <= 5; } +static int __attribute__((noipa)) a6 (int x) { return __builtin_abs (x) < 6; } + +int +main (void) +{ + static const int v[] = { 0, 1, -1, 5, -5, 6, -6, 1000, -1000, + 0x3fffffff, -0x3fffffff, 0x40000000, -0x40000000, + 2147483647, -2147483647 }; + unsigned int i; + + for (i = 0; i < sizeof (v) / sizeof (v[0]); i++) + { + int x = v[i]; + + if (a1 (x) != ref (x, 5) || a2 (x) != ref (x, 5) + || a3 (x) != ref (x, 0) || a4 (x) != ref (x, 0x3fffffff) + || a5 (x) == ref (x, 5) || a6 (x) == ref (x, 5)) + abort (); + } + return 0; +} diff --git a/gcc/testsuite/gcc.dg/torture/ior-range-test-1.c b/gcc/testsuite/gcc.dg/torture/ior-range-test-1.c new file mode 100644 index 000000000000..b9002e3f25d9 --- /dev/null +++ b/gcc/testsuite/gcc.dg/torture/ior-range-test-1.c @@ -0,0 +1,57 @@ +/* { dg-do run } */ +/* { dg-additional-options "-fwrapv" } */ +/* { dg-require-effective-target int32 } */ + +extern void abort (void); + +static int __attribute__((noipa)) +ref32 (int x, int c1, int c2) +{ + unsigned int u = (unsigned int) x + (unsigned int) c1; + unsigned int v = (unsigned int) c2 - (unsigned int) x; + return (u | v) >> 31; +} + +static int __attribute__((noipa)) +ref16 (int x, int c1, int c2) +{ + unsigned short u = (unsigned short) (x + c1); + unsigned short v = (unsigned short) (c2 - x); + return ((u | v) >> 15) & 1; +} + +static int __attribute__((noipa)) t1 (int x) { return ((x + 1) | (1 - x)) < 0; } +static int __attribute__((noipa)) t2 (int x) { return ((x + 5) | (5 - x)) >= 0; } +static int __attribute__((noipa)) t3 (int x) { return (((x + 1) | (1 - x)) >> 31) & 1; } +static int __attribute__((noipa)) t4 (int x) { return ((x - 3) | (9 - x)) < 0; } +static int __attribute__((noipa)) t5 (unsigned int x) { return (int) ((x - 3) | (9 - x)) < 0; } +static int __attribute__((noipa)) t6 (short x) { return (short) ((x - 3) | (9 - x)) < 0; } + +int +main (void) +{ + static const int v[] = { 0, 1, -1, 2, -2, 3, -3, 5, -5, 6, -6, 9, 10, -10, + 1000, -1000, 32766, 32767, -32767, -32768, + 2147483647, -2147483647 - 1, 2147483646, + -2147483647 }; + unsigned int i; + + for (i = 0; i < sizeof (v) / sizeof (v[0]); i++) + { + int x = v[i]; + + if (t1 (x) != ref32 (x, 1, 1)) + abort (); + if (t2 (x) == ref32 (x, 5, 5)) + abort (); + if (t3 (x) != ref32 (x, 1, 1)) + abort (); + if (t4 (x) != ref32 (x, -3, 9)) + abort (); + if (t5 ((unsigned int) x) != ref32 (x, -3, 9)) + abort (); + if (t6 ((short) x) != ref16 ((short) x, -3, 9)) + abort (); + } + return 0; +} diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ior-range-test-1.c b/gcc/testsuite/gcc.dg/tree-ssa/ior-range-test-1.c new file mode 100644 index 000000000000..9d1e338bd37c --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/ior-range-test-1.c @@ -0,0 +1,29 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-optimized" } */ +/* { dg-require-effective-target int32 } */ + +int f1 (int x) { return ((x + 1) | (1 - x)) < 0; } +int f2 (int x) { return ((x + 5) | (5 - x)) >= 0; } +int f3 (int x) { return (((x + 1) | (1 - x)) >> 31) & 1; } +int f4 (int x) { return ((x - 3) | (9 - x)) < 0; } +int f5 (int c) { return ((c - 'a') | ('z' - c)) < 0; } +int f6 (unsigned int x) { return (int) ((x - 3) | (9 - x)) < 0; } +int f7 (short x) { return (short) ((x - 3) | (9 - x)) < 0; } +/* C1 == 0 and C2 == 0 are spelled without the addition and as a negate. */ +int f8 (int x) { return (x | (6 - x)) < 0; } +int f9 (int x) { return ((x + 6) | -x) < 0; } +int f10 (int x) { return (x | -x) < 0; } +int f11 (int x) { return (unsigned) (x | -x) >> 31; } +int f12 (int x) { return __builtin_abs (x) > 5; } +int f13 (int x) { return __builtin_abs (x) >= 6; } +int f14 (int x) { return __builtin_abs (x) <= 5; } +int f15 (int x) { return __builtin_abs (x) < 6; } + +/* { dg-final { scan-tree-dump-not " \\| " "optimized" } } */ +/* { dg-final { scan-tree-dump-not "ABS_EXPR" "optimized" } } */ +/* { dg-final { scan-tree-dump-times " > 2;" 2 "optimized" } } */ +/* { dg-final { scan-tree-dump-times " > 6;" 5 "optimized" } } */ +/* { dg-final { scan-tree-dump-times " > 10;" 2 "optimized" } } */ +/* { dg-final { scan-tree-dump-times " <= 10;" 3 "optimized" } } */ +/* { dg-final { scan-tree-dump-times " > 25;" 1 "optimized" } } */ +/* { dg-final { scan-tree-dump-times " != 0;" 2 "optimized" } } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ior-range-test-2.c b/gcc/testsuite/gcc.dg/tree-ssa/ior-range-test-2.c new file mode 100644 index 000000000000..ed6a171b9e0b --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/ior-range-test-2.c @@ -0,0 +1,91 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-forwprop1" } */ +/* { dg-require-effective-target int32 } */ + +int +g1 (int x) +{ + int a = x + 5; + int b = 5 - x; + int c = a | b; + if (c < 0) + return 1; + return 0; +} + +unsigned int +g2 (int x) +{ + int a = x + 5; + int b = 5 - x; + unsigned int c = (unsigned int) (a | b); + return c >> 31; +} + +int +g3 (int c) +{ + int a = c - 'a'; + int b = 'z' - c; + int d = a | b; + if (d < 0) + return 0; + return 1; +} + +int +g4 (int x) +{ + int a = __builtin_abs (x); + if (a > 5) + return 1; + return 0; +} + +int +g5 (int x) +{ + int a = 6 - x; + int b = x | a; + if (b < 0) + return 1; + return 0; +} + +int +g6 (int x) +{ + int a = x + 6; + int b = -x; + int c = a | b; + if (c < 0) + return 1; + return 0; +} + +int +g7 (int x) +{ + int a = -x; + int b = x | a; + if (b < 0) + return 1; + return 0; +} + +int +g8 (int x) +{ + int a = __builtin_abs (x); + if (a <= 5) + return 1; + return 0; +} + +/* { dg-final { scan-tree-dump-not " \\| " "forwprop1" } } */ +/* { dg-final { scan-tree-dump-not "ABS_EXPR" "forwprop1" } } */ +/* { dg-final { scan-tree-dump-times { > 10[;)]} 3 "forwprop1" } } */ +/* { dg-final { scan-tree-dump-times { <= 10[;)]} 1 "forwprop1" } } */ +/* { dg-final { scan-tree-dump-times { > 25[;)]} 1 "forwprop1" } } */ +/* { dg-final { scan-tree-dump-times { > 6[;)]} 2 "forwprop1" } } */ +/* { dg-final { scan-tree-dump-times { != 0[;)]} 1 "forwprop1" } } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ior-range-test-3.c b/gcc/testsuite/gcc.dg/tree-ssa/ior-range-test-3.c new file mode 100644 index 000000000000..b8da406cb351 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/ior-range-test-3.c @@ -0,0 +1,17 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-optimized" } */ +/* { dg-require-effective-target int32 } */ + +int sink; + +/* C1 + C2 reaches the sign bit. */ +int m1 (int x) { return ((x + 0x40000000) | (0x40000000 - x)) < 0; } +/* C1 + C2 is negative. */ +int m2 (int x) { return ((x + -5) | (-5 - x)) < 0; } +/* The disjunction has a second use. */ +int m3 (int x) { int t = (x + 5) | (5 - x); sink = t; return t < 0; } +/* The ABS_EXPR has a second use. */ +int m4 (int x) { int t = __builtin_abs (x); sink = t; return t > 5; } + +/* { dg-final { scan-tree-dump-times " \\| " 3 "optimized" } } */ +/* { dg-final { scan-tree-dump-times "ABS_EXPR" 1 "optimized" } } */
