From: Kyrylo Tkachov <ktkachov@nvidia.com>
Signed saturating addition and subtraction can use a wider intermediate that
is clamped to the result type bounds:
(T) MIN (MAX ((WT) X + (WT) Y, T_MIN), T_MAX)
-> .SAT_ADD (X, Y)
Recognize addition and subtraction in both clamp nesting orders. Require a
signed intermediate that is strictly wider than the result type. This keeps
the arithmetic exact before the clamp. Require the outer clamp to have one
use so that the replacement removes it.
Check signed saturation subtraction when the clamp is rooted at a conversion.
AArch64 -O2:
before:
sxtw x1, w1
add x0, x1, w0, sxtw
mov x1, -2147483648
cmp x0, x1
csel x0, x0, x1, ge
mov w1, 2147483647
cmp x0, x1
csel x0, x0, x1, le
after:
fmov s31, w0
fmov s30, w1
sqadd s31, s31, s30
fmov w0, s31
The other clamp forms have the same reduction.
Bootstrapped and tested on aarch64-none-linux-gnu.
Ok for trunk?
gcc/ChangeLog:
* match-sat-alu.pd (signed_integer_sat_add): Add the two sided
clamp on a wider intermediate, in both nesting orders.
(signed_integer_sat_sub): Likewise.
* tree-ssa-math-opts.cc (match_unsigned_saturation_sub): Rename
to ...
(match_saturation_sub_with_assign): ... this, and ask the signed
predicate as well.
(math_opts_dom_walker::before_dom_children): Update the callers,
and call it for NOP_EXPR.
gcc/testsuite/ChangeLog:
* gcc.target/aarch64/sat_s_clamp-1.c: New test.
* gcc.target/aarch64/sat_s_clamp-2.c: New test.
Signed-off-by: Kyrylo Tkachov <ktkachov@nvidia.com>
---
gcc/match-sat-alu.pd | 87 ++++++++++++++++++-
.../gcc.target/aarch64/sat_s_clamp-1.c | 78 +++++++++++++++++
.../gcc.target/aarch64/sat_s_clamp-2.c | 43 +++++++++
gcc/tree-ssa-math-opts.cc | 14 +--
4 files changed, 214 insertions(+), 8 deletions(-)
create mode 100644 gcc/testsuite/gcc.target/aarch64/sat_s_clamp-1.c
create mode 100644 gcc/testsuite/gcc.target/aarch64/sat_s_clamp-2.c
@@ -395,7 +395,52 @@ along with GCC; see the file COPYING3. If not see
integer_zerop)
(signed_integer_sat_val @0)
@2)
- (if (wi::eq_p (wi::to_wide (@1), wi::to_wide (@3))))))
+ (if (wi::eq_p (wi::to_wide (@1), wi::to_wide (@3)))))
+
+ /* A signed saturating add written as a two sided clamp on a wider
+ intermediate, which is a common source form and what the integer
+ promotions leave for a narrow type. Both nesting orders occur:
+ an if followed by an if or an else if gives MAX then MIN, while
+ max (min (t, HI), LO) gives MIN then MAX. */
+ (match (signed_integer_sat_add @0 @1)
+ /* WT SUM = (WT)X + (WT)Y
+ SAT_S_ADD = (T)MIN (MAX (SUM, T_MIN), T_MAX) */
+ (convert (min@4 (max (plus (convert @0) (convert @1)) INTEGER_CST@2)
+ INTEGER_CST@3))
+ (if (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);
+ wide_int lo = wide_int::from (wi::min_value (precision, SIGNED),
+ wide_precision, SIGNED);
+ wide_int hi = wide_int::from (wi::max_value (precision, SIGNED),
+ wide_precision, SIGNED);
+ }
+ /* One extra bit is enough for a sum of two values of the narrow type,
+ and at equal precision the clamp is not a saturating add at all. */
+ (if (wide_precision > precision && !TYPE_UNSIGNED (wide_type)
+ && wi::eq_p (wi::to_wide (@2), lo)
+ && wi::eq_p (wi::to_wide (@3), hi))))))
+ (match (signed_integer_sat_add @0 @1)
+ /* SAT_S_ADD = (T)MAX (MIN (SUM, T_MAX), T_MIN) */
+ (convert (max@4 (min (plus (convert @0) (convert @1)) INTEGER_CST@3)
+ INTEGER_CST@2))
+ (if (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);
+ wide_int lo = wide_int::from (wi::min_value (precision, SIGNED),
+ wide_precision, SIGNED);
+ wide_int hi = wide_int::from (wi::max_value (precision, SIGNED),
+ wide_precision, SIGNED);
+ }
+ (if (wide_precision > precision && !TYPE_UNSIGNED (wide_type)
+ && wi::eq_p (wi::to_wide (@2), lo)
+ && wi::eq_p (wi::to_wide (@3), hi)))))))
/* Saturation sub for signed integer. */
(if (INTEGRAL_TYPE_P (type) && !TYPE_UNSIGNED (type))
@@ -432,7 +477,45 @@ along with GCC; see the file COPYING3. If not see
(cond^ (ne (imagpart (IFN_SUB_OVERFLOW@2 @0 @1)) integer_zerop)
(signed_integer_sat_val @0)
(realpart @2))
- (if (types_match (type, @0, @1)))))
+ (if (types_match (type, @0, @1))))
+ /* The same two sided clamp on a wider intermediate, for a subtraction. */
+ (match (signed_integer_sat_sub @0 @1)
+ /* WT DIFF = (WT)X - (WT)Y
+ SAT_S_SUB = (T)MIN (MAX (DIFF, T_MIN), T_MAX) */
+ (convert (min@4 (max (minus (convert @0) (convert @1)) INTEGER_CST@2)
+ INTEGER_CST@3))
+ (if (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);
+ wide_int lo = wide_int::from (wi::min_value (precision, SIGNED),
+ wide_precision, SIGNED);
+ wide_int hi = wide_int::from (wi::max_value (precision, SIGNED),
+ wide_precision, SIGNED);
+ }
+ (if (wide_precision > precision && !TYPE_UNSIGNED (wide_type)
+ && wi::eq_p (wi::to_wide (@2), lo)
+ && wi::eq_p (wi::to_wide (@3), hi))))))
+ (match (signed_integer_sat_sub @0 @1)
+ /* SAT_S_SUB = (T)MAX (MIN (DIFF, T_MAX), T_MIN) */
+ (convert (max@4 (min (minus (convert @0) (convert @1)) INTEGER_CST@3)
+ INTEGER_CST@2))
+ (if (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);
+ wide_int lo = wide_int::from (wi::min_value (precision, SIGNED),
+ wide_precision, SIGNED);
+ wide_int hi = wide_int::from (wi::max_value (precision, SIGNED),
+ wide_precision, SIGNED);
+ }
+ (if (wide_precision > precision && !TYPE_UNSIGNED (wide_type)
+ && wi::eq_p (wi::to_wide (@2), lo)
+ && wi::eq_p (wi::to_wide (@3), hi)))))))
/* Saturation truncate for signed integer. */
(if (INTEGRAL_TYPE_P (type) && !TYPE_UNSIGNED (type))
new file mode 100644
@@ -0,0 +1,78 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+
+#include <limits.h>
+
+static inline int imin (int a, int b) { return a < b ? a : b; }
+static inline int imax (int a, int b) { return a > b ? a : b; }
+
+/* A signed saturating add or subtract written as a two sided clamp on a
+ wider intermediate. Both nesting orders appear, and the narrow types
+ reach this shape through the integer promotions. */
+
+int
+add_ll (int x, int y)
+{
+ long long t = (long long) x + y;
+ if (t > INT_MAX) t = INT_MAX;
+ if (t < INT_MIN) t = INT_MIN;
+ return (int) t;
+}
+
+int
+add_ll_else (int x, int y)
+{
+ long long t = (long long) x + y;
+ if (t > INT_MAX) t = INT_MAX;
+ else if (t < INT_MIN) t = INT_MIN;
+ return (int) t;
+}
+
+int
+sub_ll (int x, int y)
+{
+ long long t = (long long) x - y;
+ if (t > INT_MAX) t = INT_MAX;
+ if (t < INT_MIN) t = INT_MIN;
+ return (int) t;
+}
+
+short
+add_hi (short x, short y)
+{
+ int t = x + y;
+ return (short) imax (imin (t, 32767), -32768);
+}
+
+short
+sub_hi (short x, short y)
+{
+ int t = x - y;
+ return (short) imin (imax (t, -32768), 32767);
+}
+
+signed char
+add_qi (signed char x, signed char y)
+{
+ int t = x + y;
+ return (signed char) imax (imin (t, 127), -128);
+}
+
+signed char
+sub_qi (signed char x, signed char y)
+{
+ int t = x - y;
+ return (signed char) imin (imax (t, -128), 127);
+}
+
+signed char
+add_qi_shared (signed char x, signed char y, int *p)
+{
+ int t = x + y;
+ int lo = imax (t, -128);
+ *p = lo;
+ return (signed char) imin (lo, 127);
+}
+
+/* { dg-final { scan-tree-dump-times "\\.SAT_ADD " 5 "optimized" } } */
+/* { dg-final { scan-tree-dump-times "\\.SAT_SUB " 3 "optimized" } } */
new file mode 100644
@@ -0,0 +1,43 @@
+/* { dg-do compile } */
+/* { dg-options "-O3 -fdump-tree-optimized" } */
+
+#include <limits.h>
+
+static inline int imin (int a, int b) { return a < b ? a : b; }
+static inline int imax (int a, int b) { return a > b ? a : b; }
+
+void
+add_loop (short *__restrict d, short *__restrict a, short *__restrict b, int n)
+{
+ for (int i = 0; i < n; i++)
+ {
+ int t = a[i] + b[i];
+ d[i] = (short) imax (imin (t, 32767), -32768);
+ }
+}
+
+void
+sat_loop (int *__restrict d, int *__restrict a, int *__restrict b, int n)
+{
+ for (int i = 0; i < n; i++)
+ {
+ long long t = (long long) a[i] + b[i];
+ if (t > INT_MAX) t = INT_MAX;
+ if (t < INT_MIN) t = INT_MIN;
+ d[i] = (int) t;
+ }
+}
+
+/* The clamp of an equal precision sum is not a saturating add: the
+ comparisons are dead and the whole thing is a plain addition. */
+
+int
+not_saturating (int x, int y)
+{
+ int t = x + y;
+ return t > INT_MAX ? INT_MAX : t < INT_MIN ? INT_MIN : t;
+}
+
+/* { dg-final { scan-tree-dump "\\.SAT_ADD " "optimized" } } */
+/* { dg-final { scan-assembler "sqadd\tv\[0-9\]+\.8h" } } */
+/* { dg-final { scan-assembler "sqadd\tv\[0-9\]+\.4s" } } */
@@ -4252,7 +4252,7 @@ match_saturation_add (gimple_stmt_iterator *gsi, gphi *phi)
}
/*
- * Try to match saturation unsigned sub.
+ * Try to match saturation sub with assign.
* _1 = _4 >= _5;
* _3 = _4 - _5;
* _6 = _1 ? _3 : 0;
@@ -4260,12 +4260,13 @@ match_saturation_add (gimple_stmt_iterator *gsi, gphi *phi)
* _6 = .SAT_SUB (_4, _5); */
static void
-match_unsigned_saturation_sub (gimple_stmt_iterator *gsi, gassign *stmt)
+match_saturation_sub_with_assign (gimple_stmt_iterator *gsi, gassign *stmt)
{
tree ops[2];
tree lhs = gimple_assign_lhs (stmt);
- if (gimple_unsigned_integer_sat_sub (lhs, ops, NULL))
+ if (gimple_unsigned_integer_sat_sub (lhs, ops, NULL)
+ || gimple_signed_integer_sat_sub (lhs, ops, NULL))
build_saturation_binary_arith_call_and_replace (gsi, IFN_SAT_SUB, lhs,
ops[0], ops[1]);
}
@@ -7327,14 +7328,14 @@ math_opts_dom_walker::after_dom_children (basic_block bb)
continue;
}
match_arith_overflow (&gsi, stmt, code, m_cfg_changed_p);
- match_unsigned_saturation_sub (&gsi, as_a<gassign *> (stmt));
+ match_saturation_sub_with_assign (&gsi, as_a<gassign *> (stmt));
break;
case PLUS_EXPR:
match_saturation_add_with_assign (&gsi, as_a<gassign *> (stmt));
/* fall-through */
case MINUS_EXPR:
- match_unsigned_saturation_sub (&gsi, as_a<gassign *> (stmt));
+ match_saturation_sub_with_assign (&gsi, as_a<gassign *> (stmt));
if (gsi_stmt (gsi) == stmt
&& !convert_plusminus_to_widen (&gsi, stmt, code))
{
@@ -7375,13 +7376,14 @@ math_opts_dom_walker::after_dom_children (basic_block bb)
case COND_EXPR:
case BIT_AND_EXPR:
- match_unsigned_saturation_sub (&gsi, as_a<gassign *> (stmt));
+ match_saturation_sub_with_assign (&gsi, as_a<gassign *> (stmt));
break;
case NOP_EXPR:
match_unsigned_saturation_mul (&gsi, as_a<gassign *> (stmt));
match_unsigned_saturation_trunc (&gsi, as_a<gassign *> (stmt));
match_saturation_add_with_assign (&gsi, as_a<gassign *> (stmt));
+ match_saturation_sub_with_assign (&gsi, as_a<gassign *> (stmt));
/* fall-through */
case CONVERT_EXPR:
/* The long-multiply recognizer's high-part emit ends in an