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) > + 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. > + 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 >
