diff mbox series

[06/13] match-sat-alu.pd: Recognize complement tests for unsigned saturating addition

Message ID 20260902145254.77832-8-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 an unsigned type, MAX - Y is ~Y.  An overflow test can therefore use

  X > ~Y ? MAX : X + Y

Recognize strict and non-strict comparisons with either operand or result arm
order.  Equality is safe because both arms produce MAX.  Also recognize
ADD_OVERFLOW forms that select a separate X + Y expression.

AArch64 -O3, vector body:

before:

	add	v29.4s, v31.4s, v30.4s
	not	v30.16b, v30.16b
	cmhs	v30.4s, v30.4s, v31.4s
	orn	v30.16b, v29.16b, v30.16b

after:

	uqadd	v30.4s, v31.4s, v30.4s

Four vector operations become one.

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

Ok for trunk?

gcc/ChangeLog:

	* match-sat-alu.pd (unsigned_integer_sat_add): Recognise comparisons
	against the complement of an operand.  Also recognise ADD_OVERFLOW with
	a separate addition.

gcc/testsuite/ChangeLog:

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

Signed-off-by: Kyrylo Tkachov <ktkachov@nvidia.com>
---
 gcc/match-sat-alu.pd                          | 32 +++++++++++++++++++
 .../gcc.target/aarch64/sat_u_add_not_cmp-1.c  | 30 +++++++++++++++++
 .../gcc.target/aarch64/sat_u_add_not_cmp-2.c  | 17 ++++++++++
 3 files changed, 79 insertions(+)
 create mode 100644 gcc/testsuite/gcc.target/aarch64/sat_u_add_not_cmp-1.c
 create mode 100644 gcc/testsuite/gcc.target/aarch64/sat_u_add_not_cmp-2.c

Comments

Andrea Pinski Sept. 3, 2026, 6:07 a.m. UTC | #1 
On Wed, Sep 2, 2026 at 7:59 AM <ktkachov@nvidia.com> wrote:
>
> From: Kyrylo Tkachov <ktkachov@nvidia.com>
>
> For an unsigned type, MAX - Y is ~Y.  An overflow test can therefore use
>
>   X > ~Y ? MAX : X + Y
>
> Recognize strict and non-strict comparisons with either operand or result arm
> order.  Equality is safe because both arms produce MAX.  Also recognize
> ADD_OVERFLOW forms that select a separate X + Y expression.
>
> AArch64 -O3, vector body:
>
> before:
>
>         add     v29.4s, v31.4s, v30.4s
>         not     v30.16b, v30.16b
>         cmhs    v30.4s, v30.4s, v31.4s
>         orn     v30.16b, v29.16b, v30.16b
>
> after:
>
>         uqadd   v30.4s, v31.4s, v30.4s
>
> Four vector operations become one.
>
> Bootstrapped and tested on aarch64-none-linux-gnu.
>
> Ok for trunk?
>
> gcc/ChangeLog:
>
>         * match-sat-alu.pd (unsigned_integer_sat_add): Recognise comparisons
>         against the complement of an operand.  Also recognise ADD_OVERFLOW with
>         a separate addition.
>
> gcc/testsuite/ChangeLog:
>
>         * gcc.target/aarch64/sat_u_add_not_cmp-1.c: New test.
>         * gcc.target/aarch64/sat_u_add_not_cmp-2.c: New test.
>
> Signed-off-by: Kyrylo Tkachov <ktkachov@nvidia.com>
> ---
>  gcc/match-sat-alu.pd                          | 32 +++++++++++++++++++
>  .../gcc.target/aarch64/sat_u_add_not_cmp-1.c  | 30 +++++++++++++++++
>  .../gcc.target/aarch64/sat_u_add_not_cmp-2.c  | 17 ++++++++++
>  3 files changed, 79 insertions(+)
>  create mode 100644 gcc/testsuite/gcc.target/aarch64/sat_u_add_not_cmp-1.c
>  create mode 100644 gcc/testsuite/gcc.target/aarch64/sat_u_add_not_cmp-2.c
>
> diff --git a/gcc/match-sat-alu.pd b/gcc/match-sat-alu.pd
> index b3dd8db0d27..9564366d32f 100644
> --- a/gcc/match-sat-alu.pd
> +++ b/gcc/match-sat-alu.pd
> @@ -97,6 +97,38 @@ along with GCC; see the file COPYING3.  If not see
>    (cond^ (ne (imagpart (IFN_ADD_OVERFLOW@2 @0 INTEGER_CST@1)) integer_zerop)
>          integer_minus_onep (realpart @2))
>    (if (types_match (type, @0) && int_fits_type_p (@1, type))))
> + (match (unsigned_integer_sat_add @0 @1)
> +  /* SUM = ADD_OVERFLOW (X, Y)
> +     SAT_U_ADD = IMAGPART (SUM) == 0 ? X + Y : -1.  */
> +  (cond^ (eq (imagpart (IFN_ADD_OVERFLOW @0 @1)) integer_zerop)
> +        (plus:c @0 @1) integer_minus_onep)
> +  (if (types_match (type, @0, @1))))

The types will match in this case so you don't need types_match here.
The reason is the use of plus here.
I am not 100% sure you need `:c` here since the order should be the
same for IFN_ADD_OVERFLOW too.


> + (match (unsigned_integer_sat_add @0 @1)
> +  /* SUM = ADD_OVERFLOW (X, Y)
> +     SAT_U_ADD = IMAGPART (SUM) != 0 ? -1 : X + Y.  */
> +  (cond^ (ne (imagpart (IFN_ADD_OVERFLOW @0 @1)) integer_zerop)
> +        integer_minus_onep (plus:c @0 @1))
> +  (if (types_match (type, @0, @1))))

Same comments as above.

> + /* A source that tests for overflow against the complement of an operand,
> +    such as a > MAX - b ? MAX : a + b, reaches the recognisers as a compare
> +    with ~Y, since ~Y is MAX - Y.  The strict and non-strict forms are both
> +    exact because at X == ~Y the sum is MAX and the two arms agree.  */
> + (match (unsigned_integer_sat_add @0 @1)
> +  (cond^ (ge (bit_not @1) @0) (plus:c @0 @1) integer_minus_onep))
> + (match (unsigned_integer_sat_add @0 @1)
> +  (cond^ (gt (bit_not @1) @0) (plus:c @0 @1) integer_minus_onep))
> + (match (unsigned_integer_sat_add @0 @1)
> +  (cond^ (le @0 (bit_not @1)) (plus:c @0 @1) integer_minus_onep))
> + (match (unsigned_integer_sat_add @0 @1)
> +  (cond^ (lt @0 (bit_not @1)) (plus:c @0 @1) integer_minus_onep))

(for cmp (ge gt)
 (match (unsigned_integer_sat_add @0 @1)
 (cond^ (cmp:c (bit_not @1) @0) (plus:c @0 @1) integer_minus_onep))

> + (match (unsigned_integer_sat_add @0 @1)
> +  (cond^ (lt (bit_not @1) @0) integer_minus_onep (plus:c @0 @1)))
> + (match (unsigned_integer_sat_add @0 @1)
> +  (cond^ (le (bit_not @1) @0) integer_minus_onep (plus:c @0 @1)))
> + (match (unsigned_integer_sat_add @0 @1)
> +  (cond^ (gt @0 (bit_not @1)) integer_minus_onep (plus:c @0 @1)))
> + (match (unsigned_integer_sat_add @0 @1)
> +  (cond^ (ge @0 (bit_not @1)) integer_minus_onep (plus:c @0 @1)))

(for cmp (lt le)
 (match (unsigned_integer_sat_add @0 @1)
 (cond^ (cmp:c (bit_not @1) @0) integer_minus_onep (plus:c @0 @1) ))

That is use a for loop and :c on the cmp.

>   (match (unsigned_integer_sat_add @0 @1)
>    /* WIDEN_SUM = (WT)X + (WT)Y
>       SAT_U_ADD = WIDEN_SUM > MAX ? MAX : (NT)WIDEN_SUM  */
> diff --git a/gcc/testsuite/gcc.target/aarch64/sat_u_add_not_cmp-1.c b/gcc/testsuite/gcc.target/aarch64/sat_u_add_not_cmp-1.c
> new file mode 100644
> index 00000000000..88041f53f61
> --- /dev/null
> +++ b/gcc/testsuite/gcc.target/aarch64/sat_u_add_not_cmp-1.c
> @@ -0,0 +1,30 @@
> +/* { 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;
> +
> +/* Every one of these tests for overflow against MAX - b, which reaches the
> +   middle end as a comparison with ~b.  The strict and the non-strict form
> +   agree, because at a == MAX - b the sum is MAX and so is the other arm.  */
> +
> +#define DEF(N, T, MX)                                          \
> +  T f1_##N (T a, T b) { return a > (T) (MX - b) ? MX : a + b; }        \
> +  T f2_##N (T a, T b) { return a >= (T) (MX - b) ? MX : a + b; } \
> +  T f3_##N (T a, T b) { return b > (T) ~a ? MX : a + b; }      \
> +  T f4_##N (T a, T b) { return b >= (T) ~a ? MX : a + b; }     \
> +  T f5_##N (T a, T b) { return a <= (T) (MX - b) ? a + b : MX; } \
> +  T f6_##N (T a, T b) { return a < (T) (MX - b) ? a + b : MX; }        \
> +  T f7_##N (T a, T b) { return (T) (MX - a) < b ? MX : a + b; }        \
> +  T f8_##N (T a, T b) { return (T) (MX - a) <= b ? MX : a + b; } \
> +  T f9_##N (T a, T b) { return (T) ~b >= a ? a + b : MX; }     \
> +  T f10_##N (T a, T b) { return (T) ~b > a ? a + b : MX; }
> +
> +DEF (8, u8, 255)
> +DEF (16, u16, 65535)
> +DEF (32, u32, 0xffffffffu)
> +DEF (64, u64, ~0ull)
> +
> +/* { dg-final { scan-tree-dump-times "\\.SAT_ADD " 40 "optimized" } } */
> diff --git a/gcc/testsuite/gcc.target/aarch64/sat_u_add_not_cmp-2.c b/gcc/testsuite/gcc.target/aarch64/sat_u_add_not_cmp-2.c
> new file mode 100644
> index 00000000000..bf93656885f
> --- /dev/null
> +++ b/gcc/testsuite/gcc.target/aarch64/sat_u_add_not_cmp-2.c
> @@ -0,0 +1,17 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O3 -fdump-tree-optimized" } */
> +
> +typedef unsigned int u32;
> +
> +/* Unrecognised, this vectorises as an add, a complement, a compare and a
> +   select instead of one uqadd.  */
> +
> +void
> +f (u32 *__restrict d, u32 *__restrict a, u32 *__restrict b, int n)
> +{
> +  for (int i = 0; i < n; i++)
> +    d[i] = a[i] > 0xffffffffu - b[i] ? 0xffffffffu : a[i] + b[i];
> +}
> +
> +/* { dg-final { scan-tree-dump "\\.SAT_ADD " "optimized" } } */
> +/* { dg-final { scan-assembler "uqadd\tv\[0-9\]+\.4s" } } */
> --
> 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 b3dd8db0d27..9564366d32f 100644
--- a/gcc/match-sat-alu.pd
+++ b/gcc/match-sat-alu.pd
@@ -97,6 +97,38 @@  along with GCC; see the file COPYING3.  If not see
   (cond^ (ne (imagpart (IFN_ADD_OVERFLOW@2 @0 INTEGER_CST@1)) integer_zerop)
 	 integer_minus_onep (realpart @2))
   (if (types_match (type, @0) && int_fits_type_p (@1, type))))
+ (match (unsigned_integer_sat_add @0 @1)
+  /* SUM = ADD_OVERFLOW (X, Y)
+     SAT_U_ADD = IMAGPART (SUM) == 0 ? X + Y : -1.  */
+  (cond^ (eq (imagpart (IFN_ADD_OVERFLOW @0 @1)) integer_zerop)
+	 (plus:c @0 @1) integer_minus_onep)
+  (if (types_match (type, @0, @1))))
+ (match (unsigned_integer_sat_add @0 @1)
+  /* SUM = ADD_OVERFLOW (X, Y)
+     SAT_U_ADD = IMAGPART (SUM) != 0 ? -1 : X + Y.  */
+  (cond^ (ne (imagpart (IFN_ADD_OVERFLOW @0 @1)) integer_zerop)
+	 integer_minus_onep (plus:c @0 @1))
+  (if (types_match (type, @0, @1))))
+ /* A source that tests for overflow against the complement of an operand,
+    such as a > MAX - b ? MAX : a + b, reaches the recognisers as a compare
+    with ~Y, since ~Y is MAX - Y.  The strict and non-strict forms are both
+    exact because at X == ~Y the sum is MAX and the two arms agree.  */
+ (match (unsigned_integer_sat_add @0 @1)
+  (cond^ (ge (bit_not @1) @0) (plus:c @0 @1) integer_minus_onep))
+ (match (unsigned_integer_sat_add @0 @1)
+  (cond^ (gt (bit_not @1) @0) (plus:c @0 @1) integer_minus_onep))
+ (match (unsigned_integer_sat_add @0 @1)
+  (cond^ (le @0 (bit_not @1)) (plus:c @0 @1) integer_minus_onep))
+ (match (unsigned_integer_sat_add @0 @1)
+  (cond^ (lt @0 (bit_not @1)) (plus:c @0 @1) integer_minus_onep))
+ (match (unsigned_integer_sat_add @0 @1)
+  (cond^ (lt (bit_not @1) @0) integer_minus_onep (plus:c @0 @1)))
+ (match (unsigned_integer_sat_add @0 @1)
+  (cond^ (le (bit_not @1) @0) integer_minus_onep (plus:c @0 @1)))
+ (match (unsigned_integer_sat_add @0 @1)
+  (cond^ (gt @0 (bit_not @1)) integer_minus_onep (plus:c @0 @1)))
+ (match (unsigned_integer_sat_add @0 @1)
+  (cond^ (ge @0 (bit_not @1)) integer_minus_onep (plus:c @0 @1)))
  (match (unsigned_integer_sat_add @0 @1)
   /* WIDEN_SUM = (WT)X + (WT)Y
      SAT_U_ADD = WIDEN_SUM > MAX ? MAX : (NT)WIDEN_SUM  */
diff --git a/gcc/testsuite/gcc.target/aarch64/sat_u_add_not_cmp-1.c b/gcc/testsuite/gcc.target/aarch64/sat_u_add_not_cmp-1.c
new file mode 100644
index 00000000000..88041f53f61
--- /dev/null
+++ b/gcc/testsuite/gcc.target/aarch64/sat_u_add_not_cmp-1.c
@@ -0,0 +1,30 @@ 
+/* { 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;
+
+/* Every one of these tests for overflow against MAX - b, which reaches the
+   middle end as a comparison with ~b.  The strict and the non-strict form
+   agree, because at a == MAX - b the sum is MAX and so is the other arm.  */
+
+#define DEF(N, T, MX)						\
+  T f1_##N (T a, T b) { return a > (T) (MX - b) ? MX : a + b; }	\
+  T f2_##N (T a, T b) { return a >= (T) (MX - b) ? MX : a + b; } \
+  T f3_##N (T a, T b) { return b > (T) ~a ? MX : a + b; }	\
+  T f4_##N (T a, T b) { return b >= (T) ~a ? MX : a + b; }	\
+  T f5_##N (T a, T b) { return a <= (T) (MX - b) ? a + b : MX; } \
+  T f6_##N (T a, T b) { return a < (T) (MX - b) ? a + b : MX; }	\
+  T f7_##N (T a, T b) { return (T) (MX - a) < b ? MX : a + b; }	\
+  T f8_##N (T a, T b) { return (T) (MX - a) <= b ? MX : a + b; } \
+  T f9_##N (T a, T b) { return (T) ~b >= a ? a + b : MX; }	\
+  T f10_##N (T a, T b) { return (T) ~b > a ? a + b : MX; }
+
+DEF (8, u8, 255)
+DEF (16, u16, 65535)
+DEF (32, u32, 0xffffffffu)
+DEF (64, u64, ~0ull)
+
+/* { dg-final { scan-tree-dump-times "\\.SAT_ADD " 40 "optimized" } } */
diff --git a/gcc/testsuite/gcc.target/aarch64/sat_u_add_not_cmp-2.c b/gcc/testsuite/gcc.target/aarch64/sat_u_add_not_cmp-2.c
new file mode 100644
index 00000000000..bf93656885f
--- /dev/null
+++ b/gcc/testsuite/gcc.target/aarch64/sat_u_add_not_cmp-2.c
@@ -0,0 +1,17 @@ 
+/* { dg-do compile } */
+/* { dg-options "-O3 -fdump-tree-optimized" } */
+
+typedef unsigned int u32;
+
+/* Unrecognised, this vectorises as an add, a complement, a compare and a
+   select instead of one uqadd.  */
+
+void
+f (u32 *__restrict d, u32 *__restrict a, u32 *__restrict b, int n)
+{
+  for (int i = 0; i < n; i++)
+    d[i] = a[i] > 0xffffffffu - b[i] ? 0xffffffffu : a[i] + b[i];
+}
+
+/* { dg-final { scan-tree-dump "\\.SAT_ADD " "optimized" } } */
+/* { dg-final { scan-assembler "uqadd\tv\[0-9\]+\.4s" } } */