On Tue, Sep 8, 2026 at 9:45 PM Andrew Pinski <[email protected]> wrote:
>
> On Tue, Sep 8, 2026 at 12:32 PM Dominic P <[email protected]> wrote:
> >
> > 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.
>
>
> Why not in general?
>
> > (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)
Note even when the RHS is an integer constant it might be out-of-bounds, but
you can check that here.
> > + 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);
>
> And then just use `abs(a) % precision` for non power of 2 cases?
> Note you might need to take care when dealing with small precision rhs
> of the shift if it is signed. An example
> is signed precision of 4 . which can only represent up to 15.
Cheaper than % might be using MAX (ABSU (count), precision-1). Both
are somewhat arbitrary of course (but it's UB, so ...). That said, I didn't
check the code we generate for 'x % small-constant', it might be
cheaper than max (absu (), ...) (instead of absu you could also simply
cast to unsigned).
>
>
> > + 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
> >
