| Message ID | 20260902145254.77832-4-ktkachov@nvidia.com |
|---|---|
| State | New |
| Headers | show |
| Series | Saturating arithmetic matching improvements | expand |
On Wed, Sep 2, 2026 at 7:54 AM <ktkachov@nvidia.com> wrote: > > From: Kyrylo Tkachov <ktkachov@nvidia.com> > > X - MIN (X, Y) is unsigned saturating subtraction, but subtraction > statements were not checked for this form. > > Recognize the form and check MINUS_EXPR statements for saturation. Require > the MIN to have one use so that the replacement removes it. If a replacement > changes the current statement, do not try to widen that statement. > > AArch64 -O2: > > before: > > cmp w1, w0 > csel w1, w1, w0, ls > sub w0, w0, w1 > > after: > > subs w0, w0, w1 > csel w0, w0, wzr, cs > > The vector form becomes one UQSUB instead of a comparison, a select, and a > subtraction. > > Bootstrapped and tested on aarch64-none-linux-gnu. > > Ok for trunk? > > gcc/ChangeLog: > > * match-sat-alu.pd (unsigned_integer_sat_sub): Add the > X - MIN (X, Y) form. > * tree-ssa-math-opts.cc > (math_opts_dom_walker::before_dom_children): Call > match_unsigned_saturation_sub for MINUS_EXPR as well, and > only widen while the statement is unchanged. > > gcc/testsuite/ChangeLog: > > * gcc.target/aarch64/sat_u_sub_minmax-1.c: New test. > * gcc.target/aarch64/sat_u_sub_minmax-2.c: New test. > * gcc.target/aarch64/sat_u_sub_minmax-3.c: New test. > > Signed-off-by: Kyrylo Tkachov <ktkachov@nvidia.com> > --- > gcc/match-sat-alu.pd | 6 ++++ > .../gcc.target/aarch64/sat_u_sub_minmax-1.c | 18 +++++++++++ > .../gcc.target/aarch64/sat_u_sub_minmax-2.c | 32 +++++++++++++++++++ > .../gcc.target/aarch64/sat_u_sub_minmax-3.c | 27 ++++++++++++++++ > gcc/tree-ssa-math-opts.cc | 5 +-- > 5 files changed, 86 insertions(+), 2 deletions(-) > create mode 100644 gcc/testsuite/gcc.target/aarch64/sat_u_sub_minmax-1.c > create mode 100644 gcc/testsuite/gcc.target/aarch64/sat_u_sub_minmax-2.c > create mode 100644 gcc/testsuite/gcc.target/aarch64/sat_u_sub_minmax-3.c > > diff --git a/gcc/match-sat-alu.pd b/gcc/match-sat-alu.pd > index 7156529f589..1b35b35cff8 100644 > --- a/gcc/match-sat-alu.pd > +++ b/gcc/match-sat-alu.pd > @@ -131,6 +131,12 @@ along with GCC; see the file COPYING3. If not see > /* SAT_U_SUB = (X - Y) * (X >= Y) */ > (mult:c (minus @0 @1) (convert (ge @0 @1))) > (if (types_match (type, @0, @1)))) > + (match (unsigned_integer_sat_sub @0 @1) > + /* SAT_U_SUB = X - MIN (X, Y). The MIN has to be single use: while it > + stays live the saturating subtract is computed beside it instead of > + replacing it, which costs an instruction. */ > + (minus @0 (min:c@2 @0 @1)) > + (if (single_use (@2)))) :s on the min. So `(minus @0 (min:cs @0 @1))` > (match (unsigned_integer_sat_sub @0 @1) > /* DIFF = SUB_OVERFLOW (X, Y) > SAT_U_SUB = REALPART (DIFF) | (IMAGPART (DIFF) + (-1)) */ > diff --git a/gcc/testsuite/gcc.target/aarch64/sat_u_sub_minmax-1.c b/gcc/testsuite/gcc.target/aarch64/sat_u_sub_minmax-1.c > new file mode 100644 > index 00000000000..aa1d7b6f031 > --- /dev/null > +++ b/gcc/testsuite/gcc.target/aarch64/sat_u_sub_minmax-1.c > @@ -0,0 +1,18 @@ > +/* { dg-do compile } */ > +/* { dg-options "-O2 -fdump-tree-optimized" } */ > + > +#define DEF_MIN(T) \ > + T min_##T (T a, T b) { return a - (a < b ? a : b); } \ > + T nim_##T (T a, T b) { return a - (b < a ? b : a); } > + > +typedef unsigned char u8; > +typedef unsigned short u16; > +typedef unsigned int u32; > +typedef unsigned long long u64; > + > +DEF_MIN (u8) > +DEF_MIN (u16) > +DEF_MIN (u32) > +DEF_MIN (u64) > + > +/* { dg-final { scan-tree-dump-times "\\.SAT_SUB " 8 "optimized" } } */ > diff --git a/gcc/testsuite/gcc.target/aarch64/sat_u_sub_minmax-2.c b/gcc/testsuite/gcc.target/aarch64/sat_u_sub_minmax-2.c > new file mode 100644 > index 00000000000..dcf8ab46309 > --- /dev/null > +++ b/gcc/testsuite/gcc.target/aarch64/sat_u_sub_minmax-2.c > @@ -0,0 +1,32 @@ > +/* { dg-do compile } */ > +/* { dg-options "-O3 -fdump-tree-optimized" } */ > + > +typedef unsigned char u8; > +typedef unsigned int u32; > + > +/* The recognition must reach the vectoriser, so that the loop becomes a > + single uqsub rather than a compare, a select and a subtraction. */ > + > +void > +min_loop (u8 *__restrict d, u8 *__restrict a, u8 *__restrict b, int n) > +{ > + for (int i = 0; i < n; i++) > + { > + u8 x = a[i], y = b[i]; > + d[i] = x - (x < y ? x : y); > + } > +} > + > +void > +min_loop32 (u32 *__restrict d, u32 *__restrict a, u32 *__restrict b, int n) > +{ > + for (int i = 0; i < n; i++) > + { > + u32 x = a[i], y = b[i]; > + d[i] = x - (y < x ? y : x); > + } > +} > + > +/* { dg-final { scan-tree-dump "\\.SAT_SUB " "optimized" } } */ > +/* { dg-final { scan-assembler "uqsub\tv\[0-9\]+\\.16b" } } */ > +/* { dg-final { scan-assembler "uqsub\tv\[0-9\]+\\.4s" } } */ > diff --git a/gcc/testsuite/gcc.target/aarch64/sat_u_sub_minmax-3.c b/gcc/testsuite/gcc.target/aarch64/sat_u_sub_minmax-3.c > new file mode 100644 > index 00000000000..029c136b7d0 > --- /dev/null > +++ b/gcc/testsuite/gcc.target/aarch64/sat_u_sub_minmax-3.c > @@ -0,0 +1,27 @@ > +/* { dg-do compile } */ > +/* { dg-options "-O2 -fdump-tree-optimized" } */ > + > +typedef unsigned int u32; > + > +/* While the MIN stays live the saturating subtract would be computed beside > + it rather than instead of it, so the rules do not fire. */ > + > +u32 > +min_live (u32 a, u32 b, u32 *o) > +{ > + u32 m = a < b ? a : b; > + *o = m; > + return a - m; > +} > + > +u32 > +add_min_live (u32 a, u32 b, u32 *o) > +{ > + u32 t = ~a; > + u32 m = b < t ? b : t; > + *o = m; > + return a + m; > +} > + > +/* { dg-final { scan-tree-dump-not "\\.SAT_SUB " "optimized" } } */ > +/* { dg-final { scan-tree-dump-not "\\.SAT_ADD " "optimized" } } */ > diff --git a/gcc/tree-ssa-math-opts.cc b/gcc/tree-ssa-math-opts.cc > index b371b5b7cff..ed3abb7d5c4 100644 > --- a/gcc/tree-ssa-math-opts.cc > +++ b/gcc/tree-ssa-math-opts.cc > @@ -7332,10 +7332,11 @@ math_opts_dom_walker::after_dom_children (basic_block bb) > > case PLUS_EXPR: > match_saturation_add_with_assign (&gsi, as_a<gassign *> (stmt)); > - match_unsigned_saturation_sub (&gsi, as_a<gassign *> (stmt)); > /* fall-through */ > case MINUS_EXPR: > - if (!convert_plusminus_to_widen (&gsi, stmt, code)) > + match_unsigned_saturation_sub (&gsi, as_a<gassign *> (stmt)); > + if (gsi_stmt (gsi) == stmt > + && !convert_plusminus_to_widen (&gsi, stmt, code)) Instead of `gsi_stmt (gsi) == stmt` instead return true from match_unsigned_saturation_sub if something was done. And do: if (!match_unsigned_saturation_sub (&gsi, as_a<gassign *> (stmt)) && !convert_plusminus_to_widen (&gsi, stmt, code)) { ... > { > match_arith_overflow (&gsi, stmt, code, m_cfg_changed_p); > if (gsi_stmt (gsi) == stmt) > -- > 2.50.1 (Apple Git-155) >
> On 3 Sep 2026, at 08:00, Andrea Pinski <andrew.pinski@oss.qualcomm.com> wrote: > > On Wed, Sep 2, 2026 at 7:54 AM <ktkachov@nvidia.com> wrote: >> >> From: Kyrylo Tkachov <ktkachov@nvidia.com> >> >> X - MIN (X, Y) is unsigned saturating subtraction, but subtraction >> statements were not checked for this form. >> >> Recognize the form and check MINUS_EXPR statements for saturation. Require >> the MIN to have one use so that the replacement removes it. If a replacement >> changes the current statement, do not try to widen that statement. >> >> AArch64 -O2: >> >> before: >> >> cmp w1, w0 >> csel w1, w1, w0, ls >> sub w0, w0, w1 >> >> after: >> >> subs w0, w0, w1 >> csel w0, w0, wzr, cs >> >> The vector form becomes one UQSUB instead of a comparison, a select, and a >> subtraction. >> >> Bootstrapped and tested on aarch64-none-linux-gnu. >> >> Ok for trunk? >> >> gcc/ChangeLog: >> >> * match-sat-alu.pd (unsigned_integer_sat_sub): Add the >> X - MIN (X, Y) form. >> * tree-ssa-math-opts.cc >> (math_opts_dom_walker::before_dom_children): Call >> match_unsigned_saturation_sub for MINUS_EXPR as well, and >> only widen while the statement is unchanged. >> >> gcc/testsuite/ChangeLog: >> >> * gcc.target/aarch64/sat_u_sub_minmax-1.c: New test. >> * gcc.target/aarch64/sat_u_sub_minmax-2.c: New test. >> * gcc.target/aarch64/sat_u_sub_minmax-3.c: New test. >> >> Signed-off-by: Kyrylo Tkachov <ktkachov@nvidia.com> >> --- >> gcc/match-sat-alu.pd | 6 ++++ >> .../gcc.target/aarch64/sat_u_sub_minmax-1.c | 18 +++++++++++ >> .../gcc.target/aarch64/sat_u_sub_minmax-2.c | 32 +++++++++++++++++++ >> .../gcc.target/aarch64/sat_u_sub_minmax-3.c | 27 ++++++++++++++++ >> gcc/tree-ssa-math-opts.cc | 5 +-- >> 5 files changed, 86 insertions(+), 2 deletions(-) >> create mode 100644 gcc/testsuite/gcc.target/aarch64/sat_u_sub_minmax-1.c >> create mode 100644 gcc/testsuite/gcc.target/aarch64/sat_u_sub_minmax-2.c >> create mode 100644 gcc/testsuite/gcc.target/aarch64/sat_u_sub_minmax-3.c >> >> diff --git a/gcc/match-sat-alu.pd b/gcc/match-sat-alu.pd >> index 7156529f589..1b35b35cff8 100644 >> --- a/gcc/match-sat-alu.pd >> +++ b/gcc/match-sat-alu.pd >> @@ -131,6 +131,12 @@ along with GCC; see the file COPYING3. If not see >> /* SAT_U_SUB = (X - Y) * (X >= Y) */ >> (mult:c (minus @0 @1) (convert (ge @0 @1))) >> (if (types_match (type, @0, @1)))) >> + (match (unsigned_integer_sat_sub @0 @1) >> + /* SAT_U_SUB = X - MIN (X, Y). The MIN has to be single use: while it >> + stays live the saturating subtract is computed beside it instead of >> + replacing it, which costs an instruction. */ >> + (minus @0 (min:c@2 @0 @1)) >> + (if (single_use (@2)))) > > :s on the min. > So `(minus @0 (min:cs @0 @1))` The :s does not enforce single_use in a named predicate matcher. I haven’t looked into whether that’s by design or an oversight though. Is that something that’s implementable? > >> (match (unsigned_integer_sat_sub @0 @1) >> /* DIFF = SUB_OVERFLOW (X, Y) >> SAT_U_SUB = REALPART (DIFF) | (IMAGPART (DIFF) + (-1)) */ >> diff --git a/gcc/testsuite/gcc.target/aarch64/sat_u_sub_minmax-1.c b/gcc/testsuite/gcc.target/aarch64/sat_u_sub_minmax-1.c >> new file mode 100644 >> index 00000000000..aa1d7b6f031 >> --- /dev/null >> +++ b/gcc/testsuite/gcc.target/aarch64/sat_u_sub_minmax-1.c >> @@ -0,0 +1,18 @@ >> +/* { dg-do compile } */ >> +/* { dg-options "-O2 -fdump-tree-optimized" } */ >> + >> +#define DEF_MIN(T) \ >> + T min_##T (T a, T b) { return a - (a < b ? a : b); } \ >> + T nim_##T (T a, T b) { return a - (b < a ? b : a); } >> + >> +typedef unsigned char u8; >> +typedef unsigned short u16; >> +typedef unsigned int u32; >> +typedef unsigned long long u64; >> + >> +DEF_MIN (u8) >> +DEF_MIN (u16) >> +DEF_MIN (u32) >> +DEF_MIN (u64) >> + >> +/* { dg-final { scan-tree-dump-times "\\.SAT_SUB " 8 "optimized" } } */ >> diff --git a/gcc/testsuite/gcc.target/aarch64/sat_u_sub_minmax-2.c b/gcc/testsuite/gcc.target/aarch64/sat_u_sub_minmax-2.c >> new file mode 100644 >> index 00000000000..dcf8ab46309 >> --- /dev/null >> +++ b/gcc/testsuite/gcc.target/aarch64/sat_u_sub_minmax-2.c >> @@ -0,0 +1,32 @@ >> +/* { dg-do compile } */ >> +/* { dg-options "-O3 -fdump-tree-optimized" } */ >> + >> +typedef unsigned char u8; >> +typedef unsigned int u32; >> + >> +/* The recognition must reach the vectoriser, so that the loop becomes a >> + single uqsub rather than a compare, a select and a subtraction. */ >> + >> +void >> +min_loop (u8 *__restrict d, u8 *__restrict a, u8 *__restrict b, int n) >> +{ >> + for (int i = 0; i < n; i++) >> + { >> + u8 x = a[i], y = b[i]; >> + d[i] = x - (x < y ? x : y); >> + } >> +} >> + >> +void >> +min_loop32 (u32 *__restrict d, u32 *__restrict a, u32 *__restrict b, int n) >> +{ >> + for (int i = 0; i < n; i++) >> + { >> + u32 x = a[i], y = b[i]; >> + d[i] = x - (y < x ? y : x); >> + } >> +} >> + >> +/* { dg-final { scan-tree-dump "\\.SAT_SUB " "optimized" } } */ >> +/* { dg-final { scan-assembler "uqsub\tv\[0-9\]+\\.16b" } } */ >> +/* { dg-final { scan-assembler "uqsub\tv\[0-9\]+\\.4s" } } */ >> diff --git a/gcc/testsuite/gcc.target/aarch64/sat_u_sub_minmax-3.c b/gcc/testsuite/gcc.target/aarch64/sat_u_sub_minmax-3.c >> new file mode 100644 >> index 00000000000..029c136b7d0 >> --- /dev/null >> +++ b/gcc/testsuite/gcc.target/aarch64/sat_u_sub_minmax-3.c >> @@ -0,0 +1,27 @@ >> +/* { dg-do compile } */ >> +/* { dg-options "-O2 -fdump-tree-optimized" } */ >> + >> +typedef unsigned int u32; >> + >> +/* While the MIN stays live the saturating subtract would be computed beside >> + it rather than instead of it, so the rules do not fire. */ >> + >> +u32 >> +min_live (u32 a, u32 b, u32 *o) >> +{ >> + u32 m = a < b ? a : b; >> + *o = m; >> + return a - m; >> +} >> + >> +u32 >> +add_min_live (u32 a, u32 b, u32 *o) >> +{ >> + u32 t = ~a; >> + u32 m = b < t ? b : t; >> + *o = m; >> + return a + m; >> +} >> + >> +/* { dg-final { scan-tree-dump-not "\\.SAT_SUB " "optimized" } } */ >> +/* { dg-final { scan-tree-dump-not "\\.SAT_ADD " "optimized" } } */ >> diff --git a/gcc/tree-ssa-math-opts.cc b/gcc/tree-ssa-math-opts.cc >> index b371b5b7cff..ed3abb7d5c4 100644 >> --- a/gcc/tree-ssa-math-opts.cc >> +++ b/gcc/tree-ssa-math-opts.cc >> @@ -7332,10 +7332,11 @@ math_opts_dom_walker::after_dom_children (basic_block bb) >> >> case PLUS_EXPR: >> match_saturation_add_with_assign (&gsi, as_a<gassign *> (stmt)); >> - match_unsigned_saturation_sub (&gsi, as_a<gassign *> (stmt)); >> /* fall-through */ >> case MINUS_EXPR: >> - if (!convert_plusminus_to_widen (&gsi, stmt, code)) >> + match_unsigned_saturation_sub (&gsi, as_a<gassign *> (stmt)); >> + if (gsi_stmt (gsi) == stmt >> + && !convert_plusminus_to_widen (&gsi, stmt, code)) > > Instead of `gsi_stmt (gsi) == stmt` instead return true from > match_unsigned_saturation_sub if something was done. > And do: > if (!match_unsigned_saturation_sub (&gsi, as_a<gassign *> (stmt)) > && !convert_plusminus_to_widen (&gsi, stmt, code)) > { > ... Thanks, I’ll do that in the v2. Kyrill > >> { >> match_arith_overflow (&gsi, stmt, code, m_cfg_changed_p); >> if (gsi_stmt (gsi) == stmt) >> -- >> 2.50.1 (Apple Git-155)
diff --git a/gcc/match-sat-alu.pd b/gcc/match-sat-alu.pd index 7156529f589..1b35b35cff8 100644 --- a/gcc/match-sat-alu.pd +++ b/gcc/match-sat-alu.pd @@ -131,6 +131,12 @@ along with GCC; see the file COPYING3. If not see /* SAT_U_SUB = (X - Y) * (X >= Y) */ (mult:c (minus @0 @1) (convert (ge @0 @1))) (if (types_match (type, @0, @1)))) + (match (unsigned_integer_sat_sub @0 @1) + /* SAT_U_SUB = X - MIN (X, Y). The MIN has to be single use: while it + stays live the saturating subtract is computed beside it instead of + replacing it, which costs an instruction. */ + (minus @0 (min:c@2 @0 @1)) + (if (single_use (@2)))) (match (unsigned_integer_sat_sub @0 @1) /* DIFF = SUB_OVERFLOW (X, Y) SAT_U_SUB = REALPART (DIFF) | (IMAGPART (DIFF) + (-1)) */ diff --git a/gcc/testsuite/gcc.target/aarch64/sat_u_sub_minmax-1.c b/gcc/testsuite/gcc.target/aarch64/sat_u_sub_minmax-1.c new file mode 100644 index 00000000000..aa1d7b6f031 --- /dev/null +++ b/gcc/testsuite/gcc.target/aarch64/sat_u_sub_minmax-1.c @@ -0,0 +1,18 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-optimized" } */ + +#define DEF_MIN(T) \ + T min_##T (T a, T b) { return a - (a < b ? a : b); } \ + T nim_##T (T a, T b) { return a - (b < a ? b : a); } + +typedef unsigned char u8; +typedef unsigned short u16; +typedef unsigned int u32; +typedef unsigned long long u64; + +DEF_MIN (u8) +DEF_MIN (u16) +DEF_MIN (u32) +DEF_MIN (u64) + +/* { dg-final { scan-tree-dump-times "\\.SAT_SUB " 8 "optimized" } } */ diff --git a/gcc/testsuite/gcc.target/aarch64/sat_u_sub_minmax-2.c b/gcc/testsuite/gcc.target/aarch64/sat_u_sub_minmax-2.c new file mode 100644 index 00000000000..dcf8ab46309 --- /dev/null +++ b/gcc/testsuite/gcc.target/aarch64/sat_u_sub_minmax-2.c @@ -0,0 +1,32 @@ +/* { dg-do compile } */ +/* { dg-options "-O3 -fdump-tree-optimized" } */ + +typedef unsigned char u8; +typedef unsigned int u32; + +/* The recognition must reach the vectoriser, so that the loop becomes a + single uqsub rather than a compare, a select and a subtraction. */ + +void +min_loop (u8 *__restrict d, u8 *__restrict a, u8 *__restrict b, int n) +{ + for (int i = 0; i < n; i++) + { + u8 x = a[i], y = b[i]; + d[i] = x - (x < y ? x : y); + } +} + +void +min_loop32 (u32 *__restrict d, u32 *__restrict a, u32 *__restrict b, int n) +{ + for (int i = 0; i < n; i++) + { + u32 x = a[i], y = b[i]; + d[i] = x - (y < x ? y : x); + } +} + +/* { dg-final { scan-tree-dump "\\.SAT_SUB " "optimized" } } */ +/* { dg-final { scan-assembler "uqsub\tv\[0-9\]+\\.16b" } } */ +/* { dg-final { scan-assembler "uqsub\tv\[0-9\]+\\.4s" } } */ diff --git a/gcc/testsuite/gcc.target/aarch64/sat_u_sub_minmax-3.c b/gcc/testsuite/gcc.target/aarch64/sat_u_sub_minmax-3.c new file mode 100644 index 00000000000..029c136b7d0 --- /dev/null +++ b/gcc/testsuite/gcc.target/aarch64/sat_u_sub_minmax-3.c @@ -0,0 +1,27 @@ +/* { dg-do compile } */ +/* { dg-options "-O2 -fdump-tree-optimized" } */ + +typedef unsigned int u32; + +/* While the MIN stays live the saturating subtract would be computed beside + it rather than instead of it, so the rules do not fire. */ + +u32 +min_live (u32 a, u32 b, u32 *o) +{ + u32 m = a < b ? a : b; + *o = m; + return a - m; +} + +u32 +add_min_live (u32 a, u32 b, u32 *o) +{ + u32 t = ~a; + u32 m = b < t ? b : t; + *o = m; + return a + m; +} + +/* { dg-final { scan-tree-dump-not "\\.SAT_SUB " "optimized" } } */ +/* { dg-final { scan-tree-dump-not "\\.SAT_ADD " "optimized" } } */ diff --git a/gcc/tree-ssa-math-opts.cc b/gcc/tree-ssa-math-opts.cc index b371b5b7cff..ed3abb7d5c4 100644 --- a/gcc/tree-ssa-math-opts.cc +++ b/gcc/tree-ssa-math-opts.cc @@ -7332,10 +7332,11 @@ math_opts_dom_walker::after_dom_children (basic_block bb) case PLUS_EXPR: match_saturation_add_with_assign (&gsi, as_a<gassign *> (stmt)); - match_unsigned_saturation_sub (&gsi, as_a<gassign *> (stmt)); /* fall-through */ case MINUS_EXPR: - if (!convert_plusminus_to_widen (&gsi, stmt, code)) + match_unsigned_saturation_sub (&gsi, as_a<gassign *> (stmt)); + if (gsi_stmt (gsi) == stmt + && !convert_plusminus_to_widen (&gsi, stmt, code)) { match_arith_overflow (&gsi, stmt, code, m_cfg_changed_p); if (gsi_stmt (gsi) == stmt)