[13/13] match.pd: Narrow promoted saturating addition and subtraction
Checks
| Context |
Check |
Description |
| linaro-tcwg-bot/tcwg_simplebootstrap_build--master-aarch64-bootstrap |
success
|
Build passed
|
Commit Message
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
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)
>
@@ -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,
new file mode 100644
@@ -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" } } */
new file mode 100644
@@ -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" } } */