Extend movement_possibility_1 to shift counts that are not known to be in
range, following up on r17-3550. Rather than proving the count in range,
hoist the shift and reduce the count where it lands:
gimple_needing_rewrite_undefined now covers a shift or rotate whose count is
not a constant, or is a constant at or above the precision, and
rewrite_to_defined_unconditional masks that count with precision - 1, or
clamps it as unsigned to precision - 1 when the precision is not a power of
two. loop-im then needs MOVE_PRESERVE_EXECUTION only for a count the
rewrite does not handle, such as a vector one, or for a loop optimized for
size.
A shift whose count would need the mask costs 1 rather than LIM_EXPENSIVE,
so it moves only with an expensive statement that depends on it.
Bootstrapped on x86_64-pc-linux-gnu; regression tested there with
gcc.dg/dg.exp and gcc.dg/tree-ssa/tree-ssa.exp, with no unexpected results.
Assisted-by: Claude Opus 5 (Anthropic)
gcc/ChangeLog:
* gimple-fold.cc (gimple_needing_rewrite_undefined): Return true
for a shift or rotate whose count may be out of range.
(rewrite_to_defined_unconditional): Reduce such a count into range.
* tree-ssa-loop-im.cc (shift_needs_mask_p): New function.
(determine_max_movement): Cost a shift whose count would need
masking as cheap.
(movement_possibility_1): Require preserved execution for a
possibly out-of-range count only when the rewrite cannot reduce it
or the loop is optimized for size.
gcc/testsuite/ChangeLog:
* gcc.dg/tree-ssa/loop-im-shift-2.c: Expect every chain but a lone
shift's to move; check the masks.
* gcc.dg/tree-ssa/loop-im-shift-3.c: New test.
* gcc.dg/tree-ssa/loop-im-shift-4.c: New test.
* gcc.dg/tree-ssa/loop-im-shift-5.c: New test.
* gcc.dg/tree-ssa/loop-im-shift-6.c: New test.
Signed-off-by: Dominic P <[email protected]>
---
v5 addresses both of Richard's points.
1. Out-of-range integer constants, checked here.
gimple_needing_rewrite_undefined now returns true for a shift or rotate whose
count is an INTEGER_CST at or above the precision, as well as for a
non-constant one, and rewrite_to_defined_unconditional reduces it the same
way; for a constant the reduction folds, so no statement is added and only
rhs2 changes.
That let the INTEGER_CST special cases go from both loop-im sites.
movement_possibility_1 is back to upstream's shape with one added condition,
and shift_needs_mask_p now starts from gimple_needing_rewrite_undefined, which
also gets it the INTEGRAL_TYPE_P test it was missing for vector shifts.
Measured with git diff --numstat against the base for the two source files:
v4 +82/-15, v5 +74/-7; the tree-ssa-loop-im.cc hunk goes 41/13 -> 31/5.
I checked the other callers of the two functions for the constant case: the
in-place rewriters (ifcombine, loop-split, scev, ivopts, phiopt) get an empty
sequence and only rhs2 changes; reassoc's re-uid loop then covers just the
shift; if-conversion only uses the predicate to run predicate_statements, so
no versioning or store-predication decision changes; strength reduction never
builds a shift. The vectorizer sees this only through if-conversion, which
now hands it an in-range count.
2. % vs MIN for a non-power-of-two precision.
Cast to unsigned and MIN, as you suggest, is cheaper everywhere I measured.
Reducing an unsigned count for precision 24, -O2, instructions excluding the
return:
x86_64 x % 24: 8 MIN (x, 23): 3
aarch64 x % 24: 6 MIN (x, 23): 3
arm-none-eabi x % 24: 6 MIN (x, 23): 2
On the _BitInt(24) testcase itself (loop-im-shift-4.c) that is 37 -> 33
instructions for the function on x86_64.
I read "MAX (ABSU (count), precision-1)" as clamping to precision - 1, which
is the minimum, and the cast to unsigned alone gives the negative case
(ABSU would map -1 to 1, an in-range count, rather than clamping), so v5 uses
MIN ((unsigned) count, precision - 1). Power-of-two precisions keep the plain
mask in the count's own type, with no cast unless the type cannot hold
precision - 1, so that SHIFT_COUNT_TRUNCATED targets still fold it away.
Dropping v4's separate signed/narrow handling for the modulo pays for the
one line the constant case costs.
Rejected:
- Using ranges in gimple_needing_rewrite_undefined to skip the reduction for a
count that is provably in range: it has no statement context, which is what
the existing "We cannot use ranges at 'stmt' here" in movement_possibility_1
is about.
- MIN for power-of-two precisions too: it would lose the SHIFT_COUNT_TRUNCATED
fold, and the mask is the cheaper of the two there anyway.
Testing.
loop-im-shift-4.c now also scans for the MIN form. The constant case needed
the GIMPLE front end: ccp1 folds an out-of-range constant shift to 0 long
before loop-im (checked with -fdump-tree-all; the shift is gone in
038t.ccp1), so no C testcase can put one in front of the pass.
loop-im-shift-6.c is a __GIMPLE (ssa, startwith ("lim")) function shifting by
33; the shift is hoisted with the count reduced to 1. Both new scans fail on
a v4 cc1 built from the same tree and pass on v5. All 16 checks over the six
loop-im-shift tests pass.
One thing worth knowing, unchanged from v4: after the rewrite a non-constant
count still answers true to gimple_needing_rewrite_undefined, so a second pass
rewriting the same statement adds a second mask. It folds away, and the
constant case is idempotent, but I did not try to make the predicate exact.
Bootstrapped on x86_64-pc-linux-gnu; regression tested there with gcc.dg/dg.exp
and gcc.dg/tree-ssa/tree-ssa.exp against the same tree without the patch, no
change apart from the new PASSes.
gcc/gimple-fold.cc | 45 +++++++++++++-
.../gcc.dg/tree-ssa/loop-im-shift-2.c | 58 +++++++++++++++++++
.../gcc.dg/tree-ssa/loop-im-shift-3.c | 44 ++++++++++++++
.../gcc.dg/tree-ssa/loop-im-shift-4.c | 28 +++++++++
.../gcc.dg/tree-ssa/loop-im-shift-5.c | 13 +++++
.../gcc.dg/tree-ssa/loop-im-shift-6.c | 48 +++++++++++++++
gcc/tree-ssa-loop-im.cc | 36 ++++++++++--
7 files changed, 265 insertions(+), 7 deletions(-)
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/loop-im-shift-2.c
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/loop-im-shift-3.c
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/loop-im-shift-4.c
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/loop-im-shift-5.c
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/loop-im-shift-6.c
diff --git a/gcc/gimple-fold.cc b/gcc/gimple-fold.cc
index 17b65e0a9e9..ee42c327626 100644
--- a/gcc/gimple-fold.cc
+++ b/gcc/gimple-fold.cc
@@ -10998,10 +10998,21 @@ gimple_needing_rewrite_undefined (gimple *stmt)
&& TYPE_PRECISION (lhs_type)
< TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (rhs, 0))))
return true;
+ /* A shift or rotate by a count that may be out of range; the count can
+ be reduced into range. */
+ enum tree_code code = gimple_assign_rhs_code (stmt);
+ if ((code == LSHIFT_EXPR
+ || code == RSHIFT_EXPR
+ || code == LROTATE_EXPR
+ || code == RROTATE_EXPR)
+ && INTEGRAL_TYPE_P (lhs_type)
+ && (TREE_CODE (gimple_assign_rhs2 (stmt)) != INTEGER_CST
+ || wi::geu_p (wi::to_wide (gimple_assign_rhs2 (stmt)),
+ TYPE_PRECISION (lhs_type))))
+ return true;
if (!TYPE_OVERFLOW_UNDEFINED (lhs_type))
return false;
- if (!arith_code_with_undefined_signed_overflow
- (gimple_assign_rhs_code (stmt)))
+ if (!arith_code_with_undefined_signed_overflow (code))
return false;
return true;
}
@@ -11099,6 +11110,36 @@ rewrite_to_defined_unconditional (gimple_stmt_iterator
*gsi, gimple *stmt,
}
return stmts;
}
+ /* Reduce a shift or rotate count into range. The mask keeps the count's
+ own type where that holds PREC - 1, so that a SHIFT_COUNT_TRUNCATED
+ target folds it away; MIN needs an unsigned count so a negative one
+ clamps. */
+ enum tree_code code = gimple_assign_rhs_code (stmt);
+ if (code == LSHIFT_EXPR
+ || code == RSHIFT_EXPR
+ || code == LROTATE_EXPR
+ || code == RROTATE_EXPR)
+ {
+ unsigned prec = TYPE_PRECISION (TREE_TYPE (lhs));
+ bool pow2 = pow2p_hwi (prec);
+ tree count = gimple_assign_rhs2 (stmt);
+ tree type = TREE_TYPE (count);
+ if (!pow2 || wi::ltu_p (wi::max_value (type), prec - 1))
+ type = unsigned_type_node;
+ count = gimple_convert (&stmts, type, count);
+ count = gimple_build (&stmts, pow2 ? BIT_AND_EXPR : MIN_EXPR, type,
+ count, build_int_cst (type, prec - 1));
+ gimple_assign_set_rhs2 (stmt, count);
+ gimple_set_modified (stmt, true);
+ if (in_place)
+ {
+ gsi_insert_seq_before (gsi, stmts, GSI_SAME_STMT);
+ update_stmt (stmt);
+ return NULL;
+ }
+ gimple_seq_add_stmt (&stmts, stmt);
+ return stmts;
+ }
tree type = unsigned_type_for (TREE_TYPE (lhs));
if (gimple_assign_rhs_code (stmt) == ABS_EXPR)
gimple_assign_set_rhs_code (stmt, ABSU_EXPR);
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/loop-im-shift-2.c
b/gcc/testsuite/gcc.dg/tree-ssa/loop-im-shift-2.c
new file mode 100644
index 00000000000..15c3f7b5e0d
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/loop-im-shift-2.c
@@ -0,0 +1,58 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-lim2-details -fdump-tree-optimized" } */
+
+/* The count is already in range: hoisted without a further mask. */
+
+void f (int *p, int n, int a, unsigned int s, int c, int *q)
+{
+ s &= 7;
+ for (int i = 0; i < n; i++)
+ if (p[i] > c)
+ q[i] = ((a << s) * 5) / 7;
+}
+
+/* An unconstrained count is masked at the hoisted shift. */
+
+void g (int *p, int n, int a, unsigned int s, int c, int *q)
+{
+ for (int i = 0; i < n; i++)
+ if (p[i] > c)
+ q[i] = ((a << s) * 5) / 7;
+}
+
+/* A mask that does not bound the count below the precision is refined. */
+
+void h (int *p, int n, int a, unsigned int s, int c, int *q)
+{
+ s &= 63;
+ for (int i = 0; i < n; i++)
+ if (p[i] > c)
+ q[i] = ((a << s) * 5) / 7;
+}
+
+/* The guard's range is exported as global by VRP, so no mask survives. */
+
+void k (int *p, int n, int a, unsigned int s, int c, int *q)
+{
+ for (int i = 0; i < n; i++)
+ if (p[i] > c)
+ {
+ if (s > 7) __builtin_unreachable ();
+ q[i] = ((a << s) * 5) / 7;
+ }
+}
+
+/* A lone shift that would need a mask is not worth moving by itself. */
+
+void m (int *p, int n, int a, unsigned int s, int c, int *q)
+{
+ for (int i = 0; i < n; i++)
+ if (p[i] > c)
+ q[i] = a << s;
+}
+
+/* Every chain but m's moves: the shift, the multiply and the divide. */
+/* { dg-final { scan-tree-dump-times "Moving statement" 12 "lim2" } } */
+/* { dg-final { scan-tree-dump-times "Moving statement \[^\\r\\n\]*<<" 4
"lim2" } } */
+/* f's count was masked by 7 already; g and h get a mask of 31. */
+/* { dg-final { scan-tree-dump-times " & 31;" 2 "optimized" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/loop-im-shift-3.c
b/gcc/testsuite/gcc.dg/tree-ssa/loop-im-shift-3.c
new file mode 100644
index 00000000000..03250059e58
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/loop-im-shift-3.c
@@ -0,0 +1,44 @@
+/* { dg-do run } */
+/* { dg-options "-O2" } */
+
+/* The shift is hoisted with its count masked; a count out of range on an
+ iteration that never reaches the shift must not affect the result. */
+
+__attribute__ ((noipa)) void
+k (int *p, int n, int a, unsigned int s, int c, int *q)
+{
+ for (int i = 0; i < n; i++)
+ if (p[i] > c)
+ {
+ if (s > 7) __builtin_unreachable ();
+ q[i] = ((a << s) * 5) / 7;
+ }
+}
+
+__attribute__ ((noipa)) void
+g (int *p, int n, int a, unsigned int s, int c, int *q)
+{
+ for (int i = 0; i < n; i++)
+ if (p[i] > c)
+ q[i] = (a << s) * 5;
+}
+
+int
+main (void)
+{
+ int p[4] = { 1, 5, 2, 9 };
+ int q[4] = { -1, -1, -1, -1 };
+ k (p, 4, 3, 40u, 100, q);
+ g (p, 4, 3, 77u, 100, q);
+ for (int i = 0; i < 4; i++)
+ if (q[i] != -1)
+ __builtin_abort ();
+ k (p, 4, 3, 2u, 4, q);
+ if (q[0] != -1 || q[1] != (3 << 2) * 5 / 7 || q[2] != -1
+ || q[3] != (3 << 2) * 5 / 7)
+ __builtin_abort ();
+ g (p, 4, 3, 3u, 4, q);
+ if (q[1] != (3 << 3) * 5 || q[3] != (3 << 3) * 5)
+ __builtin_abort ();
+ return 0;
+}
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/loop-im-shift-4.c
b/gcc/testsuite/gcc.dg/tree-ssa/loop-im-shift-4.c
new file mode 100644
index 00000000000..a580c5a53b6
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/loop-im-shift-4.c
@@ -0,0 +1,28 @@
+/* { dg-do run { target bitint } } */
+/* { dg-options "-O2 -std=c23 -fdump-tree-optimized" } */
+
+/* A non-power-of-two precision clamps the count to the precision - 1. */
+
+__attribute__ ((noipa)) void
+f (int *p, int n, _BitInt(24) a, unsigned int s, int c, _BitInt(24) *q)
+{
+ for (int i = 0; i < n; i++)
+ if (p[i] > c)
+ q[i] = ((a << s) * 5) / 7;
+}
+
+int
+main (void)
+{
+ int p[2] = { 1, 9 };
+ _BitInt(24) q[2] = { 0, 0 };
+ f (p, 2, 1, 40u, 100, q);
+ if (q[0] != 0 || q[1] != 0)
+ __builtin_abort ();
+ f (p, 2, 1, 8u, 4, q);
+ if (q[0] != 0 || q[1] != ((_BitInt(24)) 1 << 8) * 5 / 7)
+ __builtin_abort ();
+ return 0;
+}
+
+/* { dg-final { scan-tree-dump "MIN_EXPR <\[^,\]*, 23>" "optimized" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/loop-im-shift-5.c
b/gcc/testsuite/gcc.dg/tree-ssa/loop-im-shift-5.c
new file mode 100644
index 00000000000..859ff3d3625
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/loop-im-shift-5.c
@@ -0,0 +1,13 @@
+/* { dg-do compile } */
+/* { dg-options "-Os -fdump-tree-lim2-details" } */
+
+/* When optimizing for size a shift that would need a mask stays put. */
+
+void g (int *p, int n, int a, unsigned int s, int c, int *q)
+{
+ for (int i = 0; i < n; i++)
+ if (p[i] > c)
+ q[i] = ((a << s) * 5) / 7;
+}
+
+/* { dg-final { scan-tree-dump-not "Moving statement" "lim2" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/loop-im-shift-6.c
b/gcc/testsuite/gcc.dg/tree-ssa/loop-im-shift-6.c
new file mode 100644
index 00000000000..866c02625c5
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/loop-im-shift-6.c
@@ -0,0 +1,48 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fgimple -fdump-tree-lim2-details" } */
+
+/* An out-of-range constant count is reduced into range where the shift
+ lands, as a non-constant one is. */
+
+int __GIMPLE (ssa, startwith ("lim"))
+f (int x, int n)
+{
+ int i;
+ int r;
+ int _1;
+ int _2;
+
+ __BB(2):
+ goto __BB6;
+
+ __BB(3):
+ _1 = i_5 & 1;
+ if (_1 != 0)
+ goto __BB4;
+ else
+ goto __BB5;
+
+ __BB(4):
+ _2 = x_8(D) << 33;
+ r_9 = _2 / 5;
+ goto __BB5;
+
+ __BB(5):
+ r_3 = __PHI (__BB4: r_9, __BB3: r_4);
+ i_10 = i_5 + 1;
+ goto __BB6;
+
+ __BB(6,loop_header(1)):
+ r_4 = __PHI (__BB2: 1, __BB5: r_3);
+ i_5 = __PHI (__BB2: 0, __BB5: i_10);
+ if (i_5 < n_7(D))
+ goto __BB3;
+ else
+ goto __BB7;
+
+ __BB(7):
+ return r_4;
+}
+
+/* { dg-final { scan-tree-dump-times "Moving statement" 2 "lim2" } } */
+/* { dg-final { scan-tree-dump " << 1;" "lim2" } } */
diff --git a/gcc/tree-ssa-loop-im.cc b/gcc/tree-ssa-loop-im.cc
index 0dcf5982ec2..0af7f82af7e 100644
--- a/gcc/tree-ssa-loop-im.cc
+++ b/gcc/tree-ssa-loop-im.cc
@@ -416,9 +416,9 @@ movement_possibility_1 (gimple *stmt)
{
auto code = gimple_assign_rhs_code (stmt);
tree type = TREE_TYPE (gimple_assign_rhs1 (stmt));
- /* For shifts and rotates and possibly out-of-bound shift operands
- we currently cannot rewrite them into something unconditionally
- well-defined. */
+ /* A shift or rotate by a possibly out-of-bound count moves only where
+ rewrite_to_defined_unconditional can reduce the count, and not at
+ all when optimizing for size. */
if ((code == LSHIFT_EXPR
|| code == RSHIFT_EXPR
|| code == LROTATE_EXPR
@@ -426,7 +426,9 @@ movement_possibility_1 (gimple *stmt)
&& (TREE_CODE (gimple_assign_rhs2 (stmt)) != INTEGER_CST
/* We cannot use ranges at 'stmt' here. */
|| wi::geu_p (wi::to_wide (gimple_assign_rhs2 (stmt)),
- element_precision (type))))
+ element_precision (type)))
+ && (!gimple_needing_rewrite_undefined (stmt)
+ || optimize_loop_for_size_p (loop_containing_stmt (stmt))))
ret = MOVE_PRESERVE_EXECUTION;
}
@@ -780,6 +782,26 @@ extract_true_false_args_from_phi (basic_block dom, gphi
*phi,
return true;
}
+/* Return true if STMT is a shift or rotate whose count would have to be
+ masked when moved out of LOOP, because STMT is not always executed
+ when LOOP is entered. An out-of-range constant count folds instead. */
+
+static bool
+shift_needs_mask_p (gimple *stmt, class loop *loop)
+{
+ if (!gimple_needing_rewrite_undefined (stmt))
+ return false;
+ enum tree_code code = gimple_assign_rhs_code (stmt);
+ if ((code != LSHIFT_EXPR
+ && code != RSHIFT_EXPR
+ && code != LROTATE_EXPR
+ && code != RROTATE_EXPR)
+ || TREE_CODE (gimple_assign_rhs2 (stmt)) == INTEGER_CST)
+ return false;
+ class loop *always = get_lim_data (stmt)->always_executed_in;
+ return !always || !(always == loop || flow_loop_nested_p (always, loop));
+}
+
/* Determine the outermost loop to that it is possible to hoist a statement
STMT and store it to LIM_DATA (STMT)->max_loop. To do this we determine
the outermost loop in that the value computed by STMT is invariant.
@@ -929,7 +951,11 @@ determine_max_movement (gimple *stmt, bool
must_preserve_exec)
return false;
}
- lim_data->cost += stmt_cost (stmt);
+ /* A shift that needs its count masked is not worth moving on its own. */
+ unsigned cost = stmt_cost (stmt);
+ if (cost >= LIM_EXPENSIVE && shift_needs_mask_p (stmt, lim_data->max_loop))
+ cost = 1;
+ lim_data->cost += cost;
return true;
}
--
2.55.0
