diff mbox series

[07/13] match-sat-alu.pd: Recognize X + MIN (~X, Y) as unsigned saturating addition

Message ID 20260902145254.77832-9-ktkachov@nvidia.com
State New
Headers
Series Saturating arithmetic matching improvements |

Commit Message

Kyrylo Tkachov Sept. 2, 2026, 2:52 p.m. UTC 
  From: Kyrylo Tkachov <ktkachov@nvidia.com>

For unsigned X, ~X is MAX - X.  MIN (~X, Y) limits the addend to the largest
value that cannot overflow.  X + MIN (~X, Y) is therefore saturating addition.

Recognize this form.  Require the MIN to have one use so that the replacement
removes it.

AArch64 -O2:

before:

	mvn	w2, w0
	cmp	w2, w1
	csel	w2, w2, w1, ls
	add	w0, w2, w0

after:

	adds	w0, w0, w1
	csinv	w0, w0, wzr, cc

Four instructions become two.

Bootstrapped and tested on aarch64-none-linux-gnu.

Ok for trunk?

gcc/ChangeLog:

	* match-sat-alu.pd (unsigned_integer_sat_add): Add the
	X + MIN (~X, Y) form.

gcc/testsuite/ChangeLog:

	* gcc.target/aarch64/sat_u_add_min_not-1.c: New test.

Signed-off-by: Kyrylo Tkachov <ktkachov@nvidia.com>
---
 gcc/match-sat-alu.pd                           |  7 +++++++
 .../gcc.target/aarch64/sat_u_add_min_not-1.c   | 18 ++++++++++++++++++
 2 files changed, 25 insertions(+)
 create mode 100644 gcc/testsuite/gcc.target/aarch64/sat_u_add_min_not-1.c

Comments

Andrea Pinski Sept. 3, 2026, 5:29 a.m. UTC | #1 
On Wed, Sep 2, 2026 at 7:59 AM <ktkachov@nvidia.com> wrote:
>
> From: Kyrylo Tkachov <ktkachov@nvidia.com>
>
> For unsigned X, ~X is MAX - X.  MIN (~X, Y) limits the addend to the largest
> value that cannot overflow.  X + MIN (~X, Y) is therefore saturating addition.
>
> Recognize this form.  Require the MIN to have one use so that the replacement
> removes it.
>
> AArch64 -O2:
>
> before:
>
>         mvn     w2, w0
>         cmp     w2, w1
>         csel    w2, w2, w1, ls
>         add     w0, w2, w0
>
> after:
>
>         adds    w0, w0, w1
>         csinv   w0, w0, wzr, cc
>
> Four instructions become two.
>
> Bootstrapped and tested on aarch64-none-linux-gnu.
>
> Ok for trunk?
>
> gcc/ChangeLog:
>
>         * match-sat-alu.pd (unsigned_integer_sat_add): Add the
>         X + MIN (~X, Y) form.
>
> gcc/testsuite/ChangeLog:
>
>         * gcc.target/aarch64/sat_u_add_min_not-1.c: New test.
>
> Signed-off-by: Kyrylo Tkachov <ktkachov@nvidia.com>
> ---
>  gcc/match-sat-alu.pd                           |  7 +++++++
>  .../gcc.target/aarch64/sat_u_add_min_not-1.c   | 18 ++++++++++++++++++
>  2 files changed, 25 insertions(+)
>  create mode 100644 gcc/testsuite/gcc.target/aarch64/sat_u_add_min_not-1.c
>
> diff --git a/gcc/match-sat-alu.pd b/gcc/match-sat-alu.pd
> index 9564366d32f..b01989c3a1c 100644
> --- a/gcc/match-sat-alu.pd
> +++ b/gcc/match-sat-alu.pd
> @@ -68,6 +68,13 @@ along with GCC; see the file COPYING3.  If not see
>       wide_int sum = wi::add (cst_1, cst_2);
>      }
>      (if (wi::eq_p (max, sum))))))
> + (match (unsigned_integer_sat_add @0 @1)
> +  /* SAT_U_ADD = X + MIN (~X, Y).  ~X is MAX - X, so the MIN caps Y at the
> +     largest addend that does not overflow.  The MIN has to be single use:
> +     while it stays live the saturating add is computed beside it instead of
> +     replacing it, which costs an instruction.  */
> +  (plus:c (min:c@2 (bit_not @0) @1) @0)
> +  (if (single_use (@2))))

Does using :cs on min work instead of the single_use?  It might be
useful to add a testcase where the min is used twice.
Otherwise this is ok.
On a follow up maybe you can recognize `~X + MIN(X, Y)` as sat u add for `~X+Y`

>   (match (unsigned_integer_sat_add @0 @1)
>    /* SUM = ADD_OVERFLOW (X, Y)
>       SAT_U_ADD = REALPART (SUM) | -IMAGPART (SUM)   */
> diff --git a/gcc/testsuite/gcc.target/aarch64/sat_u_add_min_not-1.c b/gcc/testsuite/gcc.target/aarch64/sat_u_add_min_not-1.c
> new file mode 100644
> index 00000000000..58ed36897ab
> --- /dev/null
> +++ b/gcc/testsuite/gcc.target/aarch64/sat_u_add_min_not-1.c
> @@ -0,0 +1,18 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -fdump-tree-optimized" } */
> +
> +typedef unsigned char u8;
> +typedef unsigned short u16;
> +typedef unsigned int u32;
> +typedef unsigned long long u64;
> +
> +#define DEF(T)                                         \
> +  T f_##T (T a, T b) { T t = ~a; return a + (b < t ? b : t); } \
> +  T g_##T (T a, T b) { T t = ~a; return (t < b ? t : b) + a; }
> +
> +DEF (u8)
> +DEF (u16)
> +DEF (u32)
> +DEF (u64)
> +
> +/* { dg-final { scan-tree-dump-times "\\.SAT_ADD " 8 "optimized" } } */
> --
> 2.50.1 (Apple Git-155)
>
diff mbox series

Patch

diff --git a/gcc/match-sat-alu.pd b/gcc/match-sat-alu.pd
index 9564366d32f..b01989c3a1c 100644
--- a/gcc/match-sat-alu.pd
+++ b/gcc/match-sat-alu.pd
@@ -68,6 +68,13 @@  along with GCC; see the file COPYING3.  If not see
      wide_int sum = wi::add (cst_1, cst_2);
     }
     (if (wi::eq_p (max, sum))))))
+ (match (unsigned_integer_sat_add @0 @1)
+  /* SAT_U_ADD = X + MIN (~X, Y).  ~X is MAX - X, so the MIN caps Y at the
+     largest addend that does not overflow.  The MIN has to be single use:
+     while it stays live the saturating add is computed beside it instead of
+     replacing it, which costs an instruction.  */
+  (plus:c (min:c@2 (bit_not @0) @1) @0)
+  (if (single_use (@2))))
  (match (unsigned_integer_sat_add @0 @1)
   /* SUM = ADD_OVERFLOW (X, Y)
      SAT_U_ADD = REALPART (SUM) | -IMAGPART (SUM)   */
diff --git a/gcc/testsuite/gcc.target/aarch64/sat_u_add_min_not-1.c b/gcc/testsuite/gcc.target/aarch64/sat_u_add_min_not-1.c
new file mode 100644
index 00000000000..58ed36897ab
--- /dev/null
+++ b/gcc/testsuite/gcc.target/aarch64/sat_u_add_min_not-1.c
@@ -0,0 +1,18 @@ 
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+
+typedef unsigned char u8;
+typedef unsigned short u16;
+typedef unsigned int u32;
+typedef unsigned long long u64;
+
+#define DEF(T)						\
+  T f_##T (T a, T b) { T t = ~a; return a + (b < t ? b : t); }	\
+  T g_##T (T a, T b) { T t = ~a; return (t < b ? t : b) + a; }
+
+DEF (u8)
+DEF (u16)
+DEF (u32)
+DEF (u64)
+
+/* { dg-final { scan-tree-dump-times "\\.SAT_ADD " 8 "optimized" } } */