On Sat, Sep 12, 2026 at 11:24 PM Dominic P <[email protected]> wrote: > > The rules that fold x & (x >> (PREC - 1)) to MIN <x, 0> and its siblings > stop one step short of the idiom they come from, which adds the masked > difference back: > > int t = (a - b) & ((a - b) >> 31); a -= t; b += t; > > leaving MIN <a - b, 0> added to b and subtracted from a. Fold the four > combinations: > > 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)
Please also see https://gcc.gnu.org/pipermail/gcc-patches/2026-September/731051.html . I was going to try to add a signed version of this but I need a better overflow_free_p at this point to avoid the problem of introducing an overflow that was not there before. Maybe the special version for canceling out one of the terms is ok to be added. I see you missed: `MIN(X+Y, Y) - Y` -> `MIN(X, 0)` Y + MIN (X - Y, 0) -> MIN (X, Y) can be done for unsigned types too. `MIN(x, 0)` Will not show up. For signed wrapping types, it can be done safely if we know that `x - y` + `y` does not overflow. We should do `a - MIN(b, c)` as `a + MAX(-b,-c)` if b and c are easily negatable and don't introduce any undefined behaviors. see negate_expr_p usage in match.pd. This should be a seperate patch. Then you can remove your `X - MIN (X - Y, 0)` pattern and only need the Y+MINMAX pattern (and the MINMAX - Y pattern). > > Both read the sign of X - Y, so they hold only where the difference cannot > wrap: at the minimum of a wrapping type it turns positive and the > branchless form selects the other operand. The overflow guard excludes > -fwrapv and unsigned types. No !TYPE_OVERFLOW_SANITIZED guard is needed: > under -fsanitize=signed-integer-overflow the arithmetic is .UBSAN_CHECK_SUB > and .UBSAN_CHECK_ADD, the pattern does not match, and the dumps are > identical with and without the patch. > > The difference is not required to be single use: in the idiom above one > masked difference feeds both a subtraction and an addition, both fold, and > the difference dies. Where a further use does not fold the difference > stays and the fold adds a compare, five instructions to six on aarch64 at > -O2. > > The rule sits in the #if GIMPLE block of the rules it completes and is > INTEGRAL_TYPE_P like them; the producers are scalar, so no vector spelling > reaches it. > > x264 writes its median-of-three motion vector predictor this way > (common/base.h:232), three times per call. On aarch64 the function goes > from ten instructions to seven excluding the return, one fewer than the > same median written with conditional expressions, because the canonical > form lets the back end share a compare. Executed instructions for 12.3 > million calls, counted under qemu with one instruction per translation > block, fall from 147,752,451 to 123,192,835 (16.6%). The object holding > it shrinks by 20 bytes: the win is per call, not per byte. > > Bootstrapped and regression tested on x86_64-pc-linux-gnu; aarch64.exp, > vect.exp and tree-ssa.exp under qemu on aarch64-none-linux-gnu: no PASS > lost, no new FAIL. > > Assisted-by: Claude Opus 5 (Anthropic) > > gcc/ChangeLog: > > * match.pd (Y + MIN (X - Y, 0), X - MIN (X - Y, 0), Y + MAX (X - Y, > 0), > X - MAX (X - Y, 0)): Fold to MIN_EXPR and MAX_EXPR of X and Y. > > 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. > > Signed-off-by: Dominic P <[email protected]> > --- > gcc/match.pd | 18 ++++++ > gcc/testsuite/gcc.dg/torture/minmax-swar-1.c | 60 +++++++++++++++++++ > gcc/testsuite/gcc.dg/tree-ssa/minmax-swar-1.c | 57 ++++++++++++++++++ > gcc/testsuite/gcc.dg/tree-ssa/minmax-swar-2.c | 25 ++++++++ > 4 files changed, 160 insertions(+) > create mode 100644 gcc/testsuite/gcc.dg/torture/minmax-swar-1.c > create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/minmax-swar-1.c > create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/minmax-swar-2.c > > diff --git a/gcc/match.pd b/gcc/match.pd > index 8278cf1fd6d..b2e17b97866 100644 > --- a/gcc/match.pd > +++ b/gcc/match.pd > @@ -5554,6 +5554,24 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT) > && !TYPE_UNSIGNED (type) > && wi::eq_p (wi::to_wide (@1), TYPE_PRECISION (type) - 1)) > (rresult @0 { build_int_cst (type, bitop == BIT_IOR_EXPR ? -1 : 0); })))) > + > +/* Complete the branchless min/max the rules above leave half folded: > + > + 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) > + > + Both identities read the sign of X - Y, so they hold only where that > + difference cannot wrap. */ > +(for op (min max) > + opp (max min) > + (simplify > + (plus:c (op (minus @0 @1) integer_zerop) @1) > + (if (INTEGRAL_TYPE_P (type) && TYPE_OVERFLOW_UNDEFINED (type)) > + (op @0 @1))) > + (simplify > + (minus @0 (op (minus @0 @1) integer_zerop)) > + (if (INTEGRAL_TYPE_P (type) && TYPE_OVERFLOW_UNDEFINED (type)) > + (opp @0 @1)))) For these this should be ANY_INTEGRAL_TYPE_P and add a few vector testcases. > #endif > > /* Fold `1 >> a` into `a == 0` for scalar integral types. */ > 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 00000000000..09bdd650788 > --- /dev/null > +++ b/gcc/testsuite/gcc.dg/torture/minmax-swar-1.c > @@ -0,0 +1,60 @@ > +/* { 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)) > +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[] = { -536870912, -65536, -257, -1, 0, 1, 257, 65536, > + 536870911 }; > + 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 (); > + 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 00000000000..53bf1242cb8 > --- /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 00000000000..b600d69207e > --- /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" } } */ > -- > 2.55.0 >
