Extend movement_possibility_1 to variable shift counts, following up on
r17-3550. Rather than proving the count in range, hoist the shift and
mask the count where it lands: gimple_needing_rewrite_undefined now
covers a shift or rotate by a non-constant count when the precision is a
power of two, and rewrite_to_defined_unconditional masks that count with
precision - 1. loop-im then needs MOVE_PRESERVE_EXECUTION only for an
out-of-range constant count, a count that cannot be masked, or 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 by a non-constant count that may be out of
range, when the precision is a power of two.
(rewrite_to_defined_unconditional): Mask such a count.
* 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 only for an
out-of-range constant count, a count the rewrite does not mask, or
when optimizing the loop 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.
Signed-off-by: Dominic P <[email protected]>
---
Note on function k in the test: VRP1 exports the guard's [0, 7] as the
global range of s, so PRE folds the mask away again and the hoisted shift
uses the raw count.
Torture corpora at -O2: x86_64 7 files change, net -335 bytes of .text;
arm-none-eabi 10 files, net -16 bytes. At -Os nothing changes on x86_64.
gcc/gimple-fold.cc | 38 +++++++++++-
.../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 | 23 ++++++++
.../gcc.dg/tree-ssa/loop-im-shift-5.c | 13 +++++
gcc/tree-ssa-loop-im.cc | 54 ++++++++++++-----
6 files changed, 215 insertions(+), 15 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
diff --git a/gcc/gimple-fold.cc b/gcc/gimple-fold.cc
index 17b65e0a9e9..2ed9c6ef5b7 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 is not a constant may be out of
+ range; for a power-of-two precision the count can be masked 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)
+ && pow2p_hwi (TYPE_PRECISION (lhs_type))
+ && TREE_CODE (gimple_assign_rhs2 (stmt)) != INTEGER_CST)
+ 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,29 @@ rewrite_to_defined_unconditional (gimple_stmt_iterator
*gsi, gimple *stmt,
}
return stmts;
}
+ /* Mask a non-constant shift or rotate count into range. */
+ enum tree_code code = gimple_assign_rhs_code (stmt);
+ if (code == LSHIFT_EXPR
+ || code == RSHIFT_EXPR
+ || code == LROTATE_EXPR
+ || code == RROTATE_EXPR)
+ {
+ tree count = gimple_assign_rhs2 (stmt);
+ tree mask = build_int_cst (TREE_TYPE (count),
+ TYPE_PRECISION (TREE_TYPE (lhs)) - 1);
+ count = gimple_build (&stmts, BIT_AND_EXPR, TREE_TYPE (count),
+ count, mask);
+ 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..791943fd24e
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/loop-im-shift-4.c
@@ -0,0 +1,23 @@
+/* { dg-do run { target bitint } } */
+/* { dg-options "-O2 -std=c23" } */
+
+/* A non-power-of-two precision cannot be masked; the shift must stay put. */
+
+__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;
+}
+
+int
+main (void)
+{
+ int p[2] = { 1, 9 };
+ _BitInt(24) q[2] = { 0, 0 };
+ f (p, 2, 1, 8u, 4, q);
+ if (q[0] != 0 || q[1] != 256)
+ __builtin_abort ();
+ return 0;
+}
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/tree-ssa-loop-im.cc b/gcc/tree-ssa-loop-im.cc
index 0dcf5982ec2..f61b95475c1 100644
--- a/gcc/tree-ssa-loop-im.cc
+++ b/gcc/tree-ssa-loop-im.cc
@@ -416,18 +416,21 @@ 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. */
- if ((code == LSHIFT_EXPR
- || code == RSHIFT_EXPR
- || code == LROTATE_EXPR
- || code == RROTATE_EXPR)
- && (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))))
- ret = MOVE_PRESERVE_EXECUTION;
+ /* A non-constant count is masked by rewrite_to_defined_unconditional
+ when moved, unless optimizing for size; an out-of-range constant
+ cannot be made well-defined. */
+ if (code == LSHIFT_EXPR
+ || code == RSHIFT_EXPR
+ || code == LROTATE_EXPR
+ || code == RROTATE_EXPR)
+ {
+ tree count = gimple_assign_rhs2 (stmt);
+ if (TREE_CODE (count) == INTEGER_CST
+ ? wi::geu_p (wi::to_wide (count), element_precision (type))
+ : (!gimple_needing_rewrite_undefined (stmt)
+ || optimize_loop_for_size_p (loop_containing_stmt (stmt))))
+ ret = MOVE_PRESERVE_EXECUTION;
+ }
}
/* Non local loads in a transaction cannot be hoisted out. Well,
@@ -780,6 +783,27 @@ 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. */
+
+static bool
+shift_needs_mask_p (gimple *stmt, class loop *loop)
+{
+ if (!is_gimple_assign (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)
+ return false;
+ if (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 +953,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
