diff mbox series

[13/13] match.pd: Narrow promoted saturating addition and subtraction

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

Commit Message

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

Integer promotions can leave a narrow saturating operation as extensions, a
wide operation, a clamp, and a truncation.  Simplify these forms:

  (type) MAX ((wide_type) A - (wide_type) B, 0)
    -> A - MIN (A, B)
  (type) MIN ((wide_type) A + (wide_type) B, MAX)
    -> A + MIN (~A, B)

Require an intermediate type in which the operation cannot overflow.
Subtraction needs a wider signed type.  Addition needs one extra value bit and
a further sign bit for a signed intermediate.  Also require the exact maximum
of the narrow type.

The result exposes narrow saturating forms.

AArch64 -O3, vector body:

before:

	ldr	q30, [x1, x4]
	ldr	q29, [x2, x4]
	usubl	v28.8h, v30.8b, v29.8b
	usubl2	v29.8h, v30.16b, v29.16b
	smax	v28.8h, v28.8h, v31.8h
	smax	v29.8h, v29.8h, v31.8h
	uzp1	v29.16b, v28.16b, v29.16b
	str	q29, [x0, x4]

after:

	ldr	q31, [x1, x4]
	ldr	q30, [x2, x4]
	uqsub	v30.16b, v31.16b, v30.16b
	str	q30, [x0, x4]

The five computing instructions become one.  Targets without a saturating
instruction still use fewer operations.

Scalar byte and halfword forms on AArch64 can cost one extra instruction
because the backend uses SIMD registers.  The direct narrow form has the same
cost.

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

Ok for trunk?

gcc/ChangeLog:

	* match.pd ((type) MAX ((wide_type) a - (wide_type) b, 0)): New
	simplification.
	((type) MIN ((wide_type) a + (wide_type) b, MAX)): Likewise.

gcc/testsuite/ChangeLog:

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

Signed-off-by: Kyrylo Tkachov <ktkachov@nvidia.com>
---
 gcc/match.pd                                  | 37 +++++++++++++++++++
 .../gcc.target/aarch64/sat_u_promoted-1.c     | 29 +++++++++++++++
 .../gcc.target/aarch64/sat_u_promoted-2.c     | 32 ++++++++++++++++
 3 files changed, 98 insertions(+)
 create mode 100644 gcc/testsuite/gcc.target/aarch64/sat_u_promoted-1.c
 create mode 100644 gcc/testsuite/gcc.target/aarch64/sat_u_promoted-2.c

Comments

Andrea Pinski Sept. 3, 2026, 5:37 a.m. UTC | #1 
On Wed, Sep 2, 2026 at 7:56 AM <ktkachov@nvidia.com> wrote:
>
> From: Kyrylo Tkachov <ktkachov@nvidia.com>
>
> Integer promotions can leave a narrow saturating operation as extensions, a
> wide operation, a clamp, and a truncation.  Simplify these forms:
>
>   (type) MAX ((wide_type) A - (wide_type) B, 0)
>     -> A - MIN (A, B)
>   (type) MIN ((wide_type) A + (wide_type) B, MAX)
>     -> A + MIN (~A, B)
>
> Require an intermediate type in which the operation cannot overflow.
> Subtraction needs a wider signed type.  Addition needs one extra value bit and
> a further sign bit for a signed intermediate.  Also require the exact maximum
> of the narrow type.
>
> The result exposes narrow saturating forms.
>
> AArch64 -O3, vector body:
>
> before:
>
>         ldr     q30, [x1, x4]
>         ldr     q29, [x2, x4]
>         usubl   v28.8h, v30.8b, v29.8b
>         usubl2  v29.8h, v30.16b, v29.16b
>         smax    v28.8h, v28.8h, v31.8h
>         smax    v29.8h, v29.8h, v31.8h
>         uzp1    v29.16b, v28.16b, v29.16b
>         str     q29, [x0, x4]
>
> after:
>
>         ldr     q31, [x1, x4]
>         ldr     q30, [x2, x4]
>         uqsub   v30.16b, v31.16b, v30.16b
>         str     q30, [x0, x4]
>
> The five computing instructions become one.  Targets without a saturating
> instruction still use fewer operations.
>
> Scalar byte and halfword forms on AArch64 can cost one extra instruction
> because the backend uses SIMD registers.  The direct narrow form has the same
> cost.
>
> Bootstrapped and tested on aarch64-none-linux-gnu.
>
> Ok for trunk?
>
> gcc/ChangeLog:
>
>         * match.pd ((type) MAX ((wide_type) a - (wide_type) b, 0)): New
>         simplification.
>         ((type) MIN ((wide_type) a + (wide_type) b, MAX)): Likewise.
>
> gcc/testsuite/ChangeLog:
>
>         * gcc.target/aarch64/sat_u_promoted-1.c: New test.
>         * gcc.target/aarch64/sat_u_promoted-2.c: New test.
>
> Signed-off-by: Kyrylo Tkachov <ktkachov@nvidia.com>
> ---
>  gcc/match.pd                                  | 37 +++++++++++++++++++
>  .../gcc.target/aarch64/sat_u_promoted-1.c     | 29 +++++++++++++++
>  .../gcc.target/aarch64/sat_u_promoted-2.c     | 32 ++++++++++++++++
>  3 files changed, 98 insertions(+)
>  create mode 100644 gcc/testsuite/gcc.target/aarch64/sat_u_promoted-1.c
>  create mode 100644 gcc/testsuite/gcc.target/aarch64/sat_u_promoted-2.c
>
> diff --git a/gcc/match.pd b/gcc/match.pd
> index 54cad1cd2bc..8afdb4105f6 100644
> --- a/gcc/match.pd
> +++ b/gcc/match.pd
> @@ -4839,6 +4839,43 @@ DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
>      @0
>      @2)))
>
> +/* Narrow a saturating add or subtract that the integer promotions widened.
> +   For an unsigned type,
> +     (type) MAX ((wide_type) a - (wide_type) b, 0) -> a - MIN (a, b)
> +     (type) MIN ((wide_type) a + (wide_type) b, MAX) -> a + MIN (~a, b)
> +   Both results are exact in the narrow type: the difference is clamped at
> +   zero and the sum at MAX, so the truncation never loses a bit.  The widening
> +   sequence of five operations collapses to two or three narrow ones.  */
> +(simplify
> + (convert (max@4 (minus@2 (convert @0) (convert @1)) integer_zerop))
> + (if (INTEGRAL_TYPE_P (type)
> +      && TYPE_UNSIGNED (type)
> +      && types_match (type, @0, @1)
> +      && single_use (@4)
> +      && !TYPE_UNSIGNED (TREE_TYPE (@2))
> +      && TYPE_PRECISION (TREE_TYPE (@2)) > TYPE_PRECISION (type))
> +  (minus @0 (min @0 @1))))

I think you should :s on the max instead of single_use here.
Does it make sense to extend this one to a vector types too? So use
element_precision and ANY_INTEGRAL_TYPE_P?
Though you might need to check to see if min/minus is supported for
that vector type.

> +
> +(simplify
> + (convert (min@4 (plus@2 (convert @0) (convert @1)) INTEGER_CST@3))
> + (if (INTEGRAL_TYPE_P (type)
> +      && TYPE_UNSIGNED (type)
> +      && types_match (type, @0, @1)
> +      && single_use (@4))

:s on the min instead of single_use.

> +  (with
> +   {
> +    unsigned precision = TYPE_PRECISION (type);
> +    tree wide_type = TREE_TYPE (@2);
> +    unsigned wide_precision = TYPE_PRECISION (wide_type);
> +    /* The widened sum reaches 2 * (2^precision - 1), which needs one bit
> +       more than the narrow type, and one further bit for a sign.  */
> +    unsigned needed = precision + (TYPE_UNSIGNED (wide_type) ? 1 : 2);
> +   }
> +   (if (wide_precision >= needed
> +       && wi::eq_p (wi::to_wide (@3),
> +                    wi::mask (precision, false, wide_precision)))
> +    (plus @0 (min @1 (bit_not @0)))))))

Same question about vector types?  Though INTEGER_CST becomes
uniform_integer_cst instead.

Also for the !single use case, adding a testcase for that would be useful.


> +
>  /* MIN (MAX (X, Y + CST), Y) -> Y for a positive CST, and the dual
>     MAX (MIN (X, Y + CST), Y) -> Y for a negative one.  The inner select is
>     at least Y + CST, which the absence of wrapping puts strictly beyond Y,
> diff --git a/gcc/testsuite/gcc.target/aarch64/sat_u_promoted-1.c b/gcc/testsuite/gcc.target/aarch64/sat_u_promoted-1.c
> new file mode 100644
> index 00000000000..424d2df3fba
> --- /dev/null
> +++ b/gcc/testsuite/gcc.target/aarch64/sat_u_promoted-1.c
> @@ -0,0 +1,29 @@
> +/* { 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;
> +
> +/* The integer promotions turn a narrow saturating add or subtract written
> +   as a clamp into a widened operation feeding a MIN or a MAX.  */
> +
> +u8 sub8 (u8 a, u8 b) { int t = a - b; return t < 0 ? 0 : t; }
> +u8 sub8_swapped (u8 a, u8 b) { int t = a - b; return t > 0 ? t : 0; }
> +u16 sub16 (u16 a, u16 b) { int t = a - b; return t < 0 ? 0 : t; }
> +u32 sub32 (u32 a, u32 b) { long long t = (long long) a - b; return t < 0 ? 0 : t; }
> +
> +u8 add8 (u8 a, u8 b) { int t = a + b; return t > 255 ? 255 : t; }
> +u16 add16 (u16 a, u16 b) { int t = a + b; return t > 65535 ? 65535 : t; }
> +u32 add32 (u32 a, u32 b) { u64 t = (u64) a + b; return t > 0xffffffffu ? 0xffffffffu : t; }
> +
> +u8 add8_shared (u8 a, u8 b, int *p)
> +{
> +  int t = a + b;
> +  *p = t;
> +  return t > 255 ? 255 : t;
> +}
> +
> +/* { dg-final { scan-tree-dump-times "\\.SAT_SUB " 4 "optimized" } } */
> +/* { dg-final { scan-tree-dump-times "\\.SAT_ADD " 4 "optimized" } } */
> diff --git a/gcc/testsuite/gcc.target/aarch64/sat_u_promoted-2.c b/gcc/testsuite/gcc.target/aarch64/sat_u_promoted-2.c
> new file mode 100644
> index 00000000000..3370ab0706a
> --- /dev/null
> +++ b/gcc/testsuite/gcc.target/aarch64/sat_u_promoted-2.c
> @@ -0,0 +1,32 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O3 -fdump-tree-optimized" } */
> +
> +typedef unsigned char u8;
> +
> +/* Without the recognition these loops widen, clamp and pack again, five
> +   vector operations where one saturating operation does the job.  */
> +
> +void
> +sub_loop (u8 *__restrict d, u8 *__restrict a, u8 *__restrict b, int n)
> +{
> +  for (int i = 0; i < n; i++)
> +    {
> +      int t = a[i] - b[i];
> +      d[i] = t < 0 ? 0 : t;
> +    }
> +}
> +
> +void
> +add_loop (u8 *__restrict d, u8 *__restrict a, u8 *__restrict b, int n)
> +{
> +  for (int i = 0; i < n; i++)
> +    {
> +      int t = a[i] + b[i];
> +      d[i] = t > 255 ? 255 : t;
> +    }
> +}
> +
> +/* { dg-final { scan-tree-dump "\\.SAT_SUB " "optimized" } } */
> +/* { dg-final { scan-tree-dump "\\.SAT_ADD " "optimized" } } */
> +/* { dg-final { scan-assembler "uqsub\tv\[0-9\]+\.16b" } } */
> +/* { dg-final { scan-assembler "uqadd\tv\[0-9\]+\.16b" } } */
> --
> 2.50.1 (Apple Git-155)
>
diff mbox series

Patch

diff --git a/gcc/match.pd b/gcc/match.pd
index 54cad1cd2bc..8afdb4105f6 100644
--- a/gcc/match.pd
+++ b/gcc/match.pd
@@ -4839,6 +4839,43 @@  DEFINE_INT_AND_FLOAT_ROUND_FN (RINT)
     @0
     @2)))
 
+/* Narrow a saturating add or subtract that the integer promotions widened.
+   For an unsigned type,
+     (type) MAX ((wide_type) a - (wide_type) b, 0) -> a - MIN (a, b)
+     (type) MIN ((wide_type) a + (wide_type) b, MAX) -> a + MIN (~a, b)
+   Both results are exact in the narrow type: the difference is clamped at
+   zero and the sum at MAX, so the truncation never loses a bit.  The widening
+   sequence of five operations collapses to two or three narrow ones.  */
+(simplify
+ (convert (max@4 (minus@2 (convert @0) (convert @1)) integer_zerop))
+ (if (INTEGRAL_TYPE_P (type)
+      && TYPE_UNSIGNED (type)
+      && types_match (type, @0, @1)
+      && single_use (@4)
+      && !TYPE_UNSIGNED (TREE_TYPE (@2))
+      && TYPE_PRECISION (TREE_TYPE (@2)) > TYPE_PRECISION (type))
+  (minus @0 (min @0 @1))))
+
+(simplify
+ (convert (min@4 (plus@2 (convert @0) (convert @1)) INTEGER_CST@3))
+ (if (INTEGRAL_TYPE_P (type)
+      && TYPE_UNSIGNED (type)
+      && types_match (type, @0, @1)
+      && single_use (@4))
+  (with
+   {
+    unsigned precision = TYPE_PRECISION (type);
+    tree wide_type = TREE_TYPE (@2);
+    unsigned wide_precision = TYPE_PRECISION (wide_type);
+    /* The widened sum reaches 2 * (2^precision - 1), which needs one bit
+       more than the narrow type, and one further bit for a sign.  */
+    unsigned needed = precision + (TYPE_UNSIGNED (wide_type) ? 1 : 2);
+   }
+   (if (wide_precision >= needed
+	&& wi::eq_p (wi::to_wide (@3),
+		     wi::mask (precision, false, wide_precision)))
+    (plus @0 (min @1 (bit_not @0)))))))
+
 /* MIN (MAX (X, Y + CST), Y) -> Y for a positive CST, and the dual
    MAX (MIN (X, Y + CST), Y) -> Y for a negative one.  The inner select is
    at least Y + CST, which the absence of wrapping puts strictly beyond Y,
diff --git a/gcc/testsuite/gcc.target/aarch64/sat_u_promoted-1.c b/gcc/testsuite/gcc.target/aarch64/sat_u_promoted-1.c
new file mode 100644
index 00000000000..424d2df3fba
--- /dev/null
+++ b/gcc/testsuite/gcc.target/aarch64/sat_u_promoted-1.c
@@ -0,0 +1,29 @@ 
+/* { 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;
+
+/* The integer promotions turn a narrow saturating add or subtract written
+   as a clamp into a widened operation feeding a MIN or a MAX.  */
+
+u8 sub8 (u8 a, u8 b) { int t = a - b; return t < 0 ? 0 : t; }
+u8 sub8_swapped (u8 a, u8 b) { int t = a - b; return t > 0 ? t : 0; }
+u16 sub16 (u16 a, u16 b) { int t = a - b; return t < 0 ? 0 : t; }
+u32 sub32 (u32 a, u32 b) { long long t = (long long) a - b; return t < 0 ? 0 : t; }
+
+u8 add8 (u8 a, u8 b) { int t = a + b; return t > 255 ? 255 : t; }
+u16 add16 (u16 a, u16 b) { int t = a + b; return t > 65535 ? 65535 : t; }
+u32 add32 (u32 a, u32 b) { u64 t = (u64) a + b; return t > 0xffffffffu ? 0xffffffffu : t; }
+
+u8 add8_shared (u8 a, u8 b, int *p)
+{
+  int t = a + b;
+  *p = t;
+  return t > 255 ? 255 : t;
+}
+
+/* { dg-final { scan-tree-dump-times "\\.SAT_SUB " 4 "optimized" } } */
+/* { dg-final { scan-tree-dump-times "\\.SAT_ADD " 4 "optimized" } } */
diff --git a/gcc/testsuite/gcc.target/aarch64/sat_u_promoted-2.c b/gcc/testsuite/gcc.target/aarch64/sat_u_promoted-2.c
new file mode 100644
index 00000000000..3370ab0706a
--- /dev/null
+++ b/gcc/testsuite/gcc.target/aarch64/sat_u_promoted-2.c
@@ -0,0 +1,32 @@ 
+/* { dg-do compile } */
+/* { dg-options "-O3 -fdump-tree-optimized" } */
+
+typedef unsigned char u8;
+
+/* Without the recognition these loops widen, clamp and pack again, five
+   vector operations where one saturating operation does the job.  */
+
+void
+sub_loop (u8 *__restrict d, u8 *__restrict a, u8 *__restrict b, int n)
+{
+  for (int i = 0; i < n; i++)
+    {
+      int t = a[i] - b[i];
+      d[i] = t < 0 ? 0 : t;
+    }
+}
+
+void
+add_loop (u8 *__restrict d, u8 *__restrict a, u8 *__restrict b, int n)
+{
+  for (int i = 0; i < n; i++)
+    {
+      int t = a[i] + b[i];
+      d[i] = t > 255 ? 255 : t;
+    }
+}
+
+/* { dg-final { scan-tree-dump "\\.SAT_SUB " "optimized" } } */
+/* { dg-final { scan-tree-dump "\\.SAT_ADD " "optimized" } } */
+/* { dg-final { scan-assembler "uqsub\tv\[0-9\]+\.16b" } } */
+/* { dg-final { scan-assembler "uqadd\tv\[0-9\]+\.16b" } } */