https://gcc.gnu.org/g:9d734bb468e714099fd56ee31676f9d88a5f7154
commit r17-4210-g9d734bb468e714099fd56ee31676f9d88a5f7154 Author: Dominic P <[email protected]> Date: Sun Sep 13 15:50:01 2026 -0600 [PATCH v2 2/2] match.pd: complete the branchless min and max folds The x & (x >> (PREC - 1)) -> MIN (x, 0) rules leave the branchless min/max idiom t = (a - b) & ((a - b) >> 31); a -= t; b += t; half folded. Add Y + MIN (X - Y, 0) -> MIN (X, Y) X - MIN (X - Y, 0) -> MAX (X, Y) MIN (X + Y, Y) - Y -> MIN (X, 0) and the MAX forms. Each needs the inner operation not to overflow, which gimple_match_no_overflow_p takes from the type or, on GIMPLE, from ranges. There is no :s because the idiom uses the masked value twice and both uses fold. x264's median-of-three predictor (common/base.h) goes from 20 to 11 instructions on x86_64 at -O2. Bootstrapped and regression tested on x86_64-pc-linux-gnu. --- Thanks for the review. v2 splits it as you suggested. 1/2 is A - MIN (B, C) -> A + MAX (-B, -C). It needs TYPE_OVERFLOW_UNDEFINED as well as negate_expr_p. 2/2 keeps X - MIN (X - Y, 0), because 1/2 cannot reach it: X - Y is only negatable when the type wraps. Without that rule x264's median is 18 instructions on x86_64 at -O2, against 11 with it. MIN (X + Y, Y) - Y is added, unsigned and -fwrapv use the range check from your 731051, and both patches are ANY_INTEGRAL_TYPE_P with vector tests. Assisted-by: Claude Opus 5 (Anthropic) gcc/ChangeLog: * generic-match-head.cc (gimple_match_no_overflow_p): New. * gimple-match-head.cc (gimple_match_no_overflow_p): New. * match.pd (Y + MIN (X - Y, 0), X - MIN (X - Y, 0), Y + MAX (X - Y, 0), X - MAX (X - Y, 0), MIN (X + Y, Y) - Y, MAX (X + Y, Y) - Y): New patterns. gcc/testsuite/ChangeLog: * gcc.dg/torture/minmax-swar-1.c: New test. * gcc.dg/tree-ssa/minmax-swar-1.c: New test. * gcc.dg/tree-ssa/minmax-swar-2.c: New test. * gcc.dg/tree-ssa/minmax-swar-3.c: New test. * gcc.dg/tree-ssa/minmax-swar-4.c: New test. * gcc.dg/tree-ssa/minmax-swar-5.c: New test. * gcc.dg/tree-ssa/minmax-swar-6.c: New test. * gcc.dg/tree-ssa/minmax-swar-7.c: New test. Signed-off-by: Dominic P <[email protected]> Diff: --- gcc/generic-match-head.cc | 9 +++ gcc/gimple-match-head.cc | 17 ++++++ gcc/match.pd | 24 ++++++++ gcc/testsuite/gcc.dg/torture/minmax-swar-1.c | 81 +++++++++++++++++++++++++++ gcc/testsuite/gcc.dg/tree-ssa/minmax-swar-1.c | 57 +++++++++++++++++++ gcc/testsuite/gcc.dg/tree-ssa/minmax-swar-2.c | 25 +++++++++ gcc/testsuite/gcc.dg/tree-ssa/minmax-swar-3.c | 39 +++++++++++++ gcc/testsuite/gcc.dg/tree-ssa/minmax-swar-4.c | 54 ++++++++++++++++++ gcc/testsuite/gcc.dg/tree-ssa/minmax-swar-5.c | 70 +++++++++++++++++++++++ gcc/testsuite/gcc.dg/tree-ssa/minmax-swar-6.c | 53 ++++++++++++++++++ gcc/testsuite/gcc.dg/tree-ssa/minmax-swar-7.c | 32 +++++++++++ 11 files changed, 461 insertions(+) diff --git a/gcc/generic-match-head.cc b/gcc/generic-match-head.cc index 9e7097a038d1..5f66965c84f1 100644 --- a/gcc/generic-match-head.cc +++ b/gcc/generic-match-head.cc @@ -209,3 +209,12 @@ gimple_match_ctx (tree) { return NULL; } + +/* Return true if CODE applied to OP0 and OP1 in TYPE cannot overflow. + On GENERIC there is no range query, so only TYPE can say so. */ + +static inline bool +gimple_match_no_overflow_p (tree_code, tree type, tree, tree, tree) +{ + return TYPE_OVERFLOW_UNDEFINED (type); +} diff --git a/gcc/gimple-match-head.cc b/gcc/gimple-match-head.cc index 757e324cb21a..b2f26c71fc9c 100644 --- a/gcc/gimple-match-head.cc +++ b/gcc/gimple-match-head.cc @@ -535,3 +535,20 @@ gimple_match_range_of_expr (vrange &r, tree op, tree ctx = NULL_TREE) return false; return !r.undefined_p (); } + +/* Return true if CODE applied to OP0 and OP1 in TYPE cannot overflow, + either because TYPE says so or because their ranges prove it. CTX is + a capture passed on to gimple_match_range_of_expr. */ + +static inline bool +gimple_match_no_overflow_p (tree_code code, tree type, tree op0, tree op1, + tree ctx) +{ + if (TYPE_OVERFLOW_UNDEFINED (type)) + return true; + + int_range_max vr0, vr1; + return (gimple_match_range_of_expr (vr0, op0, ctx) + && gimple_match_range_of_expr (vr1, op1, ctx) + && range_op_handler (code).overflow_free_p (vr0, vr1)); +} diff --git a/gcc/match.pd b/gcc/match.pd index 6728fc68fc13..0d2312c17f7a 100644 --- a/gcc/match.pd +++ b/gcc/match.pd @@ -5624,6 +5624,30 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT) (rresult @0 { build_int_cst (type, bitop == BIT_IOR_EXPR ? -1 : 0); })))) #endif +/* Complete the branchless min and max the rules above leave half folded, + and the same identity with the addition inside the select: + + Y + MIN (X - Y, 0) -> MIN (X, Y) X - MIN (X - Y, 0) -> MAX (X, Y) + Y + MAX (X - Y, 0) -> MAX (X, Y) X - MAX (X - Y, 0) -> MIN (X, Y) + MIN (X + Y, Y) - Y -> MIN (X, 0) MAX (X + Y, Y) - Y -> MAX (X, 0) */ +(for minmax (min max) + maxmin (max min) + (simplify + (plus:c (minmax (minus@3 @0 @1) integer_zerop) @1) + (if (ANY_INTEGRAL_TYPE_P (type) + && gimple_match_no_overflow_p (MINUS_EXPR, type, @0, @1, @3)) + (minmax @0 @1))) + (simplify + (minus @0 (minmax (minus@3 @0 @1) integer_zerop)) + (if (ANY_INTEGRAL_TYPE_P (type) + && gimple_match_no_overflow_p (MINUS_EXPR, type, @0, @1, @3)) + (maxmin @0 @1))) + (simplify + (minus (minmax:c (plus:c@3 @0 @1) @1) @1) + (if (ANY_INTEGRAL_TYPE_P (type) + && gimple_match_no_overflow_p (PLUS_EXPR, type, @0, @1, @3)) + (minmax @0 { build_zero_cst (type); })))) + /* Fold `1 >> a` into `a == 0` for scalar integral types. */ (simplify (rshift integer_onep @2) diff --git a/gcc/testsuite/gcc.dg/torture/minmax-swar-1.c b/gcc/testsuite/gcc.dg/torture/minmax-swar-1.c new file mode 100644 index 000000000000..005a485c13ee --- /dev/null +++ b/gcc/testsuite/gcc.dg/torture/minmax-swar-1.c @@ -0,0 +1,81 @@ +/* { dg-do run } */ +/* { dg-require-effective-target int32 } */ + +/* The canonicalization must not change any value. Every difference formed + below stays inside the type, so the test is also valid under -ftrapv (where + the fold itself is disabled, the branchless form being the one that traps). */ + +static int __attribute__ ((noipa)) +swar_min (int a, int b) +{ + int t = a - b; + return b + (t & (t >> 31)); +} + +static int __attribute__ ((noipa)) +swar_max (int a, int b) +{ + int t = a - b; + return a - (t & (t >> 31)); +} + +static int __attribute__ ((noipa)) +swar_median (int a, int b, int c) +{ + int t = (a - b) & ((a - b) >> 31); + a -= t; + b += t; + b -= (b - c) & ((b - c) >> 31); + b += (a - b) & ((a - b) >> 31); + return b; +} + +static int __attribute__ ((noipa)) +clamp_lo (int x, int y) +{ + int s = x + y; + return (s < y ? s : y) - y; +} + +static int __attribute__ ((noipa)) +clamp_hi (int x, int y) +{ + int s = x + y; + return (s > y ? s : y) - y; +} + +static int __attribute__ ((noipa)) +ref_median (int a, int b, int c) +{ + int lo = a < b ? (a < c ? a : c) : (b < c ? b : c); + int hi = a > b ? (a > c ? a : c) : (b > c ? b : c); + return a + b + c - lo - hi; +} + +int +main (void) +{ + static const int vs[] = { -268435456, -65536, -257, -1, 0, 1, 257, 65536, + 268435455 }; + unsigned n = sizeof (vs) / sizeof (vs[0]); + for (unsigned i = 0; i < n; i++) + for (unsigned j = 0; j < n; j++) + { + int a = vs[i], b = vs[j]; + if (swar_min (a, b) != (a < b ? a : b)) + __builtin_abort (); + if (swar_max (a, b) != (a > b ? a : b)) + __builtin_abort (); + if (a < 268435456 && a > -268435456 && b < 268435456 && b > -268435456) + { + if (clamp_lo (a, b) != (a < 0 ? a : 0)) + __builtin_abort (); + if (clamp_hi (a, b) != (a > 0 ? a : 0)) + __builtin_abort (); + } + for (unsigned k = 0; k < n; k++) + if (swar_median (a, b, vs[k]) != ref_median (a, b, vs[k])) + __builtin_abort (); + } + return 0; +} diff --git a/gcc/testsuite/gcc.dg/tree-ssa/minmax-swar-1.c b/gcc/testsuite/gcc.dg/tree-ssa/minmax-swar-1.c new file mode 100644 index 000000000000..53bf1242cb8b --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/minmax-swar-1.c @@ -0,0 +1,57 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-forwprop1 -fdump-tree-optimized" } */ +/* { dg-require-effective-target int32 } */ + +/* The branchless min and max that x264's x264_median writes. The existing + rule turns x & (x >> 31) into MIN <x, 0>; these have to finish the job. */ + +int +swar_min (int a, int b) +{ + int t = a - b; + return b + (t & (t >> 31)); +} + +int +swar_max (int a, int b) +{ + int t = a - b; + return a - (t & (t >> 31)); +} + +int +swar_min_not (int a, int b) +{ + int t = a - b; + return a - (t & ~(t >> 31)); +} + +int +swar_max_not (int a, int b) +{ + int t = a - b; + return b + (t & ~(t >> 31)); +} + +/* Both uses of the one difference have to fold. */ +int +swar_median (int a, int b, int c) +{ + int t = (a - b) & ((a - b) >> 31); + a -= t; + b += t; + b -= (b - c) & ((b - c) >> 31); + b += (a - b) & ((a - b) >> 31); + return b; +} + +/* The existing rule leaves MIN <x, 0> and MAX <x, 0> behind, so the counts + alone do not say whether this patch fired; what says it is that none of the + clamps against zero survive. The four simple functions fold in forwprop1, + the median needs one more pass because its uses are chained. */ +/* { dg-final { scan-tree-dump-not "MIN_EXPR <\[^,\]*, 0>" "forwprop1" } } */ +/* { dg-final { scan-tree-dump-not "MAX_EXPR <\[^,\]*, 0>" "forwprop1" } } */ +/* { dg-final { scan-tree-dump-not "MIN_EXPR <\[^,\]*, 0>" "optimized" } } */ +/* { dg-final { scan-tree-dump-not "MAX_EXPR <\[^,\]*, 0>" "optimized" } } */ +/* { dg-final { scan-tree-dump-times "MIN_EXPR" 4 "optimized" } } */ +/* { dg-final { scan-tree-dump-times "MAX_EXPR" 4 "optimized" } } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/minmax-swar-2.c b/gcc/testsuite/gcc.dg/tree-ssa/minmax-swar-2.c new file mode 100644 index 000000000000..b600d69207e9 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/minmax-swar-2.c @@ -0,0 +1,25 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fwrapv -fdump-tree-optimized" } */ +/* { dg-require-effective-target int32 } */ + +/* With a wrapping difference the identity fails: for a = INT_MIN, b = 1 the + difference wraps positive and the branchless form returns b. The inner + MIN <a - b, 0> is still formed, but neither function may become a plain + MIN or MAX of a and b. */ + +int +swar_min (int a, int b) +{ + int t = a - b; + return b + (t & (t >> 31)); +} + +int +swar_max (int a, int b) +{ + int t = a - b; + return a - (t & (t >> 31)); +} + +/* { dg-final { scan-tree-dump-times "MIN_EXPR <\[^,\]*, 0>" 2 "optimized" } } */ +/* { dg-final { scan-tree-dump-not "MAX_EXPR" "optimized" } } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/minmax-swar-3.c b/gcc/testsuite/gcc.dg/tree-ssa/minmax-swar-3.c new file mode 100644 index 000000000000..5061683d04cb --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/minmax-swar-3.c @@ -0,0 +1,39 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-forwprop1-raw -fdump-tree-optimized-raw" } */ + +/* MIN (X + Y, Y) - Y -> MIN (X, 0) and MAX (X + Y, Y) - Y -> MAX (X, 0). */ + +int +clamp_lo (int x, int y) +{ + int s = x + y; + return (s < y ? s : y) - y; +} + +int +clamp_hi (int x, int y) +{ + int s = x + y; + return (s > y ? s : y) - y; +} + +int +clamp_lo_long (int x, int y) +{ + int s = x + y; + int m; + if (s < y) + m = s; + else + m = y; + return m - y; +} + +/* The two written with ?: fold in forwprop1; the one written with if and else + needs phiopt to make the select first. */ +/* { dg-final { scan-tree-dump-times "<min_expr," 1 "forwprop1" } } */ +/* { dg-final { scan-tree-dump-times "<max_expr," 1 "forwprop1" } } */ +/* { dg-final { scan-tree-dump-not "<plus_expr," "optimized" } } */ +/* { dg-final { scan-tree-dump-not "<minus_expr," "optimized" } } */ +/* { dg-final { scan-tree-dump-times "<min_expr," 2 "optimized" } } */ +/* { dg-final { scan-tree-dump-times "<max_expr," 1 "optimized" } } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/minmax-swar-4.c b/gcc/testsuite/gcc.dg/tree-ssa/minmax-swar-4.c new file mode 100644 index 000000000000..96675c1a6a9f --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/minmax-swar-4.c @@ -0,0 +1,54 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fwrapv -fdump-tree-optimized-raw" } */ + +/* Under -fwrapv the identities still hold where the range of the operands + rules the wrap out. */ + +int +swar_min_ranged (int a, int b) +{ + if (a < -1000 || a > 1000) + __builtin_unreachable (); + if (b < -1000 || b > 1000) + __builtin_unreachable (); + int t = a - b; + return b + (t < 0 ? t : 0); +} + +int +swar_max_ranged (int a, int b) +{ + if (a < -1000 || a > 1000) + __builtin_unreachable (); + if (b < -1000 || b > 1000) + __builtin_unreachable (); + int t = a - b; + return a - (t < 0 ? t : 0); +} + +int +clamp_lo_ranged (int x, int y) +{ + if (x < -1000 || x > 1000) + __builtin_unreachable (); + if (y < -1000 || y > 1000) + __builtin_unreachable (); + int s = x + y; + return (s < y ? s : y) - y; +} + +int +clamp_hi_ranged (int x, int y) +{ + if (x < -1000 || x > 1000) + __builtin_unreachable (); + if (y < -1000 || y > 1000) + __builtin_unreachable (); + int s = x + y; + return (s > y ? s : y) - y; +} + +/* { dg-final { scan-tree-dump-not "<plus_expr," "optimized" } } */ +/* { dg-final { scan-tree-dump-not "<minus_expr," "optimized" } } */ +/* { dg-final { scan-tree-dump-times "<min_expr," 2 "optimized" } } */ +/* { dg-final { scan-tree-dump-times "<max_expr," 2 "optimized" } } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/minmax-swar-5.c b/gcc/testsuite/gcc.dg/tree-ssa/minmax-swar-5.c new file mode 100644 index 000000000000..931d5a0d7419 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/minmax-swar-5.c @@ -0,0 +1,70 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -Wno-psabi -fdump-tree-forwprop1-raw" } */ + +/* All six rules on a vector type. The selects against zero are spelled with + >, not <: a vector x < 0 is canonicalised to the sign mask x >> 31, and the + rule that turns x & (x >> 31) into MIN <x, 0> is scalar, so that spelling + forms no vector MIN_EXPR at all. The scan is on forwprop1, which runs + before the vector lowering that would split a MAX_EXPR the target cannot + do. */ + +typedef int v4si __attribute__ ((vector_size (16))); + +/* Y + MIN (X - Y, 0) -> MIN (X, Y). */ +v4si +add_min_vec (v4si a, v4si b) +{ + v4si t = a - b, z = { 0, 0, 0, 0 }; + v4si m = t > z; + return b + ((z & m) | (t & ~m)); +} + +/* Y + MAX (X - Y, 0) -> MAX (X, Y). */ +v4si +add_max_vec (v4si a, v4si b) +{ + v4si t = a - b, z = { 0, 0, 0, 0 }; + v4si m = t > z; + return b + ((t & m) | (z & ~m)); +} + +/* X - MIN (X - Y, 0) -> MAX (X, Y). */ +v4si +sub_min_vec (v4si a, v4si b) +{ + v4si t = a - b, z = { 0, 0, 0, 0 }; + v4si m = t > z; + return a - ((z & m) | (t & ~m)); +} + +/* X - MAX (X - Y, 0) -> MIN (X, Y). */ +v4si +sub_max_vec (v4si a, v4si b) +{ + v4si t = a - b, z = { 0, 0, 0, 0 }; + v4si m = t > z; + return a - ((t & m) | (z & ~m)); +} + +/* MIN (X + Y, Y) - Y -> MIN (X, 0). */ +v4si +clamp_lo_vec (v4si x, v4si y) +{ + v4si s = x + y; + v4si m = s < y; + return ((s & m) | (y & ~m)) - y; +} + +/* MAX (X + Y, Y) - Y -> MAX (X, 0). */ +v4si +clamp_hi_vec (v4si x, v4si y) +{ + v4si s = x + y; + v4si m = s > y; + return ((s & m) | (y & ~m)) - y; +} + +/* { dg-final { scan-tree-dump-not "<plus_expr," "forwprop1" } } */ +/* { dg-final { scan-tree-dump-not "<minus_expr," "forwprop1" } } */ +/* { dg-final { scan-tree-dump-times "<min_expr," 3 "forwprop1" } } */ +/* { dg-final { scan-tree-dump-times "<max_expr," 3 "forwprop1" } } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/minmax-swar-6.c b/gcc/testsuite/gcc.dg/tree-ssa/minmax-swar-6.c new file mode 100644 index 000000000000..4f096a002296 --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/minmax-swar-6.c @@ -0,0 +1,53 @@ +/* { dg-do compile } */ +/* { dg-require-effective-target vect_int } */ +/* { dg-options "-O3 -fdump-tree-optimized" } */ +/* { dg-additional-options "-msse2" { target ia32 } } */ + +/* The two difference pairs reaching vector code through the loop vectorizer: + the fold is on the scalar loop body, so what is left to vectorize is a + vector MIN or MAX of the two loads, with no vector add or subtract. */ + +void +add_min (int *r, int *a, int *b, int n) +{ + for (int i = 0; i < n; i++) + { + int t = a[i] - b[i]; + r[i] = b[i] + (t < 0 ? t : 0); + } +} + +void +add_max (int *r, int *a, int *b, int n) +{ + for (int i = 0; i < n; i++) + { + int t = a[i] - b[i]; + r[i] = b[i] + (t > 0 ? t : 0); + } +} + +void +sub_min (int *r, int *a, int *b, int n) +{ + for (int i = 0; i < n; i++) + { + int t = a[i] - b[i]; + r[i] = a[i] - (t < 0 ? t : 0); + } +} + +void +sub_max (int *r, int *a, int *b, int n) +{ + for (int i = 0; i < n; i++) + { + int t = a[i] - b[i]; + r[i] = a[i] - (t > 0 ? t : 0); + } +} + +/* { dg-final { scan-tree-dump-not "= vect_\[^;\]* - vect_" "optimized" } } */ +/* { dg-final { scan-tree-dump-not "= vect_\[^;\]* \\+ vect_" "optimized" } } */ +/* { dg-final { scan-tree-dump "MIN_EXPR <vect_\[^,\]*, vect_" "optimized" { target { ! vect_no_int_min_max } } } } */ +/* { dg-final { scan-tree-dump "MAX_EXPR <vect_\[^,\]*, vect_" "optimized" { target { ! vect_no_int_min_max } } } } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/minmax-swar-7.c b/gcc/testsuite/gcc.dg/tree-ssa/minmax-swar-7.c new file mode 100644 index 000000000000..125fcb3016cc --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/minmax-swar-7.c @@ -0,0 +1,32 @@ +/* { dg-do compile } */ +/* { dg-require-effective-target vect_int } */ +/* { dg-options "-O3 -fdump-tree-optimized" } */ +/* { dg-additional-options "-msse2" { target ia32 } } */ + +/* MINMAX (X + Y, Y) - Y through the loop vectorizer: the vector add and the + vector subtract both go, leaving the clamp against zero. */ + +void +clamp_lo (int *r, int *x, int *y, int n) +{ + for (int i = 0; i < n; i++) + { + int s = x[i] + y[i]; + r[i] = (s < y[i] ? s : y[i]) - y[i]; + } +} + +void +clamp_hi (int *r, int *x, int *y, int n) +{ + for (int i = 0; i < n; i++) + { + int s = x[i] + y[i]; + r[i] = (s > y[i] ? s : y[i]) - y[i]; + } +} + +/* { dg-final { scan-tree-dump-not "= vect_\[^;\]* - vect_" "optimized" } } */ +/* { dg-final { scan-tree-dump-not "= vect_\[^;\]* \\+ vect_" "optimized" } } */ +/* { dg-final { scan-tree-dump "MIN_EXPR <vect_\[^,\]*, \{ 0" "optimized" { target { ! vect_no_int_min_max } } } } */ +/* { dg-final { scan-tree-dump "MAX_EXPR <vect_\[^,\]*, \{ 0" "optimized" { target { ! vect_no_int_min_max } } } } */
