[PATCH 1/3] tree-optimization: hoist shifts by an in-range constant count

movement_possibility_1 restricts shifts and rotates to
MOVE_PRESERVE_EXECUTION so that a count which is out of range is never
speculatively executed.  The test was inverted: wi::ltu_p (count,
precision) is true exactly when the count is in range and the shift is
perfectly well defined, so it was the well-defined shifts that were
pinned, while a constant count >= precision - the undefined case the
comment describes - fell through as MOVE_POSSIBLE.

The restriction was added by r14-4786-gd118738e71cf46 (PR111000), whose
concern is a count that cannot be proven in range - there, hoisting can
introduce an undefined shift on a path that never executed it.  That
case is unaffected here: a non-INTEGER_CST count still takes the
MOVE_PRESERVE_EXECUTION path through the first half of the disjunct, and
gcc.dg/torture/pr111000.c still passes, and compiles to identical code
before and after.

compute_invariantness skips a MOVE_PRESERVE_EXECUTION statement whenever
the block may not execute, and outermost_invariant_loop then returns
NULL for its result, so the entire invariant chain rooted at such a
shift was pinned with it.  In the new testcase the multiply and the
divide then stay in the loop as well.

How much of this reaches the emitted code varies.  It is clearest where
the division survives as a libcall by a constant divisor: on
arm-none-eabi at -Os -mcpu=arm1176jzf-s the bl __aeabi_idiv sits inside
the loop body before this change and above the loop after it, and the
register save list shrinks from eight registers to six.  Where the
division is expanded inline the RTL loop-invariant pass can recover the
motion on its own - at -O2 that same function is byte for byte identical
before and after - and a non-constant divisor stays pinned either way as
possibly trapping.  Hoisting earlier can also cost a little code size
where it raises register pressure: a loop body with several such chains
under one guard grows on Thumb at -Os, because the hoisted values are
live across the loop.  The GIMPLE-level change is what the testcase
checks.

The series was bootstrapped on x86_64-pc-linux-gnu at trunk 7f549ea2b47
with the stage2/stage3 comparison successful, and a full make check shows
no regressions: 227924 gcc and 278399 g++ expected passes, and every one
of the 112 unexpected results also occurs with the series reverted.  With the patch reverted and the test kept, the lim2 dump moves
no statements instead of three.

Assisted-by: Claude Opus 5 (Anthropic)

gcc/ChangeLog:

	PR tree-optimization/111000
	* tree-ssa-loop-im.cc (movement_possibility_1): Require
	MOVE_PRESERVE_EXECUTION for an out-of-range constant shift
	count, not an in-range one.

gcc/testsuite/ChangeLog:

	* gcc.dg/tree-ssa/loop-im-shift-1.c: New test.

Signed-off-by: Dominic P <[email protected]>
---
 .../gcc.dg/tree-ssa/loop-im-shift-1.c         | 23 +++++++++++++++++++
 gcc/tree-ssa-loop-im.cc                       |  2 +-
 2 files changed, 24 insertions(+), 1 deletion(-)
 create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/loop-im-shift-1.c

diff --git a/gcc/testsuite/gcc.dg/tree-ssa/loop-im-shift-1.c b/gcc/testsuite/gcc.dg/tree-ssa/loop-im-shift-1.c
new file mode 100644
index 00000000000..129fa13bf0e
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/loop-im-shift-1.c
@@ -0,0 +1,23 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-lim2-details" } */
+
+/* A shift by an in-range constant is perfectly well defined, so loop-invariant
+   motion may hoist it out of a conditionally executed block just like any other
+   arithmetic.  Only a constant count that is out of range (or a non-constant
+   one, which cannot be proven in range here) has to be restricted to
+   MOVE_PRESERVE_EXECUTION.
+
+   Because the shift's result feeds the rest of the chain, restricting it also
+   pinned everything computed from it, so the multiply and the divide below
+   stayed in the loop as well.  */
+
+void f (int *p, int n, int a, int b, int c, int *q)
+{
+  for (int i = 0; i < n; i++)
+    if (p[i] > c)
+      q[i] = ((a << 3) * b) / 7;
+}
+
+/* The whole invariant chain must move, exactly as it does when the shift is
+   written as a multiply by 8.  */
+/* { dg-final { scan-tree-dump-times "Moving statement" 3 "lim2" } } */
diff --git a/gcc/tree-ssa-loop-im.cc b/gcc/tree-ssa-loop-im.cc
index 41264560009..0dcf5982ec2 100644
--- a/gcc/tree-ssa-loop-im.cc
+++ b/gcc/tree-ssa-loop-im.cc
@@ -425,7 +425,7 @@ movement_possibility_1 (gimple *stmt)
 	   || code == RROTATE_EXPR)
 	  && (TREE_CODE (gimple_assign_rhs2 (stmt)) != INTEGER_CST
 	      /* We cannot use ranges at 'stmt' here.  */
-	      || wi::ltu_p (wi::to_wide (gimple_assign_rhs2 (stmt)),
+	      || wi::geu_p (wi::to_wide (gimple_assign_rhs2 (stmt)),
 			    element_precision (type))))
 	ret = MOVE_PRESERVE_EXECUTION;
     }
-- 
2.55.0