On Tue, Aug 11, 2026 at 11:21 AM Eikansh Gupta
<[email protected]> wrote:
>
> 'switch (D + C)' with an integer constant C is equivalent to 'switch (D)'
> with every case label decreased by C. Fold the offset into the labels so
> the addition is removed and the bare index is exposed to later passes; e.g.
> 'switch (v + 20)' now tests v against 150..157 instead of v + 20 against
> 170..177.
>
> Trapping (-ftrapv) and sanitized (-fsanitize=signed-integer-overflow) types
> are left alone, since removing the addition would drop the trap or diagnostic
> that must still happen when D + C overflows.
>
> PR tree-optimization/121460
>
> gcc/ChangeLog:
>
> * tree-ssa-forwprop.cc (simplify_gimple_switch_offset): New function.
> (simplify_gimple_switch): Call simplify_gimple_switch_offset.
>
> gcc/testsuite/ChangeLog:
>
> * gcc.dg/tree-ssa/switch-addfold-1.c: New test.
> * gcc.dg/tree-ssa/switch-addfold-2.c: New test.
> * gcc.dg/tree-ssa/switch-addfold-3.c: New test.
>
> Signed-off-by: Eikansh Gupta <[email protected]>
> ---
> .../gcc.dg/tree-ssa/switch-addfold-1.c | 61 +++++++++++++++++
> .../gcc.dg/tree-ssa/switch-addfold-2.c | 27 ++++++++
> .../gcc.dg/tree-ssa/switch-addfold-3.c | 34 ++++++++++
> gcc/tree-ssa-forwprop.cc | 66 +++++++++++++++++++
> 4 files changed, 188 insertions(+)
> create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/switch-addfold-1.c
> create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/switch-addfold-2.c
> create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/switch-addfold-3.c
>
> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/switch-addfold-1.c
> b/gcc/testsuite/gcc.dg/tree-ssa/switch-addfold-1.c
> new file mode 100644
> index 00000000000..ee7d9938ac0
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/switch-addfold-1.c
> @@ -0,0 +1,61 @@
> +/* PR tree-optimization/121460 */
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -fdump-tree-forwprop1" } */
> +
> +/* Verify that a constant offset on a switch index is folded into the
> + case labels, so the addition/subtraction is removed and the switch
> + dispatches on the bare index. */
> +void foo (int, int);
> +
> +void add (unsigned char v, int w)
> +{
> + int i, j;
> + switch (v + 20)
> + {
> + case 170: i = 1; j = w; break;
> + case 171: i = 2; j = v; break;
> + case 172: i = 3; j = -19; break;
> + case 173: i = 4; j = -w; break;
> + case 174: i = 5; j = 55; break;
> + case 175: i = 6; j = w; break;
> + case 176: i = 7; j = 55; break;
> + case 177: i = 8; j = 55; break;
> + default: __builtin_unreachable ();
> + }
> + foo (i, j);
> +}
> +
> +void sub (int v)
> +{
> + int i;
> + switch (v - 5)
> + {
> + case 10: i = 1; break;
> + case 11: i = 2; break;
> + case 12: i = 3; break;
> + default: i = 0; break;
> + }
> + foo (i, v);
> +}
> +
> +void range (int v)
> +{
> + int i;
> + switch (v + 100)
> + {
> + case 110 ... 115: i = 1; break;
> + case 120: i = 2; break;
> + default: i = 0; break;
> + }
> + foo (i, v);
> +}
> +
> +/* The additive offset should be gone from the switch index. */
> +/* { dg-final { scan-tree-dump-not "\\+ 20" "forwprop1" } } */
> +/* { dg-final { scan-tree-dump-not "\\+ -5;" "forwprop1" } } */
> +/* { dg-final { scan-tree-dump-not "\\+ 100" "forwprop1" } } */
> +
> +/* Labels should be shifted down accordingly. */
> +/* { dg-final { scan-tree-dump "case 150:" "forwprop1" } } */
> +/* { dg-final { scan-tree-dump "case 15:" "forwprop1" } } */
> +/* { dg-final { scan-tree-dump "case 10 ... 15:" "forwprop1" } } */
> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/switch-addfold-2.c
> b/gcc/testsuite/gcc.dg/tree-ssa/switch-addfold-2.c
> new file mode 100644
> index 00000000000..91a31f32414
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/switch-addfold-2.c
> @@ -0,0 +1,27 @@
> +/* PR tree-optimization/121460 */
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -fdump-tree-forwprop1" } */
> +
> +void foo (int);
> +
> +/* GIMPLE canonicalizes 'un - 10' into 'un + (-10)', i.e. 'un + 4294967286',
> + so the fold sees a large wrapped constant. Subtracting it from each label
> + wraps back to the intended value (10 - 4294967286 == 20 and
> + 20 - 4294967286 == 30, modulo 2**32), which is correct. A plain overflow
> + check would wrongly bail here (the subtraction underflows); the fold
> instead
> + only requires the shifted labels to stay sorted (20 <= 30), so it still
> + applies. */
> +void usub (unsigned un)
> +{
> + switch (un - 10)
> + {
> + case 10: foo (1); break; /* un == 20 */
> + case 20: foo (2); break; /* un == 30 */
> + default: foo (0); break;
> + }
> +}
> +
> +/* { dg-final { scan-tree-dump "switch \\(un" "forwprop1" } } */
> +/* { dg-final { scan-tree-dump "case 20:" "forwprop1" } } */
> +/* { dg-final { scan-tree-dump "case 30:" "forwprop1" } } */
> +/* { dg-final { scan-tree-dump-not "4294967286" "forwprop1" } } */
> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/switch-addfold-3.c
> b/gcc/testsuite/gcc.dg/tree-ssa/switch-addfold-3.c
> new file mode 100644
> index 00000000000..fbc8f2fa690
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/switch-addfold-3.c
> @@ -0,0 +1,34 @@
> +/* PR tree-optimization/121460 */
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -fdump-tree-forwprop1" } */
> +
> +void foo (int);
> +
> +/* u + 1: labels would become UINT_MAX and 1 (reordered) -> bail. */
> +void wrap (unsigned u)
> +{
> + switch (u + 1)
> + {
> + case 0: foo (1); break;
> + case 2: foo (2); break;
> + default: foo (0); break;
> + }
> +}
> +
> +/* Same, but the case range would itself wrap. */
> +void wrap_range (unsigned u)
> +{
> + switch (u + 1)
> + {
> + case 0 ... 2: foo (1); break;
> + case 10: foo (2); break;
> + default: foo (0); break;
> + }
> +}
> +
> +/* Additions survive and labels stay unchanged; the wrapped value is absent.
> */
> +/* { dg-final { scan-tree-dump-times " \\+ 1;" 2 "forwprop1" } } */
> +/* { dg-final { scan-tree-dump "case 0:" "forwprop1" } } */
> +/* { dg-final { scan-tree-dump "case 0 ... 2:" "forwprop1" } } */
> +/* { dg-final { scan-tree-dump "case 10:" "forwprop1" } } */
> +/* { dg-final { scan-tree-dump-not "4294967295" "forwprop1" } } */
> diff --git a/gcc/tree-ssa-forwprop.cc b/gcc/tree-ssa-forwprop.cc
> index 75f06c6ba41..580c99ecb59 100644
> --- a/gcc/tree-ssa-forwprop.cc
> +++ b/gcc/tree-ssa-forwprop.cc
> @@ -1035,6 +1035,66 @@ simplify_gimple_switch_label_vec (gswitch *stmt, tree
> index_type,
> }
> }
>
> +/* Helper for simplify_gimple_switch. Try to fold a constant offset on the
> + index of switch STMT into its case labels: 'switch (D + C)' is equivalent
> + to 'switch (D)' with every case label decreased by C. Return true
> + if the rewrite was performed. */
> +static bool
> +simplify_gimple_switch_offset (gswitch *stmt, tree cond, gimple *def_stmt,
> + bitmap simple_dce_worklist)
> +{
> + if (!is_gimple_assign (def_stmt)
> + || gimple_assign_rhs_code (def_stmt) != PLUS_EXPR)
> + return false;
> +
> + tree op0 = gimple_assign_rhs1 (def_stmt);
> + tree op1 = gimple_assign_rhs2 (def_stmt);
> + tree type = TREE_TYPE (cond);
> + unsigned num_labels = gimple_switch_num_labels (stmt);
> +
> + if (TREE_CODE (op0) != SSA_NAME
> + || TREE_CODE (op1) != INTEGER_CST
> + || integer_zerop (op1)
> + || !INTEGRAL_TYPE_P (type)
> + /* Removing the addition would drop a trap or sanitizer check for the
> + inputs where D + C overflows, so leave those modes alone. */
> + || TYPE_OVERFLOW_TRAPS (type)
> + || TYPE_OVERFLOW_SANITIZED (type))
I think you want to guard against a large unsigned constant with MSB set
so that the effective values become only smaller? In fact, would it make
sense to canonicalize the minimum CASE_LOW to zero? Or is the point
of the patch to elide the shift of the switch value? Because for a casei
tablejump we'll shift the values again. But smaller case values are
cheaper to materialize in case of a decision tree expansion.
> + return false;
> +
> + if (num_labels < 2)
> + return false;
> +
> + signop sgn = TYPE_SIGN (type);
> + wide_int c = wi::to_wide (op1);
> + tree last = gimple_switch_label (stmt, num_labels - 1);
> + tree min = CASE_LOW (gimple_switch_label (stmt, 1));
> + tree max = CASE_HIGH (last) ? CASE_HIGH (last) : CASE_LOW (last);
> +
> + /* Check if the shifted extremes stay in order. This will ensure that all
> + the labels are in order after shifting them. */
> + if (!wi::le_p (wi::sub (wi::to_wide (min), c),
> + wi::sub (wi::to_wide (max), c), sgn))
> + return false;
> +
> + /* Shift every label in place and switch to the bare index. */
> + for (unsigned i = 1; i < num_labels; i++)
> + {
> + tree label = gimple_switch_label (stmt, i);
> + CASE_LOW (label)
> + = wide_int_to_tree (type, wi::sub (wi::to_wide (CASE_LOW (label)),
> c));
> + if (CASE_HIGH (label))
> + CASE_HIGH (label)
> + = wide_int_to_tree (type,
> + wi::sub (wi::to_wide (CASE_HIGH (label)), c));
> + }
> +
> + bitmap_set_bit (simple_dce_worklist, SSA_NAME_VERSION (cond));
> + gimple_switch_set_index (stmt, op0);
> + update_stmt (stmt);
> + return true;
> +}
> +
> /* STMT is a SWITCH_EXPR for which we attempt to find equivalent forms of
> the condition which we may be able to optimize better. */
>
> @@ -1086,6 +1146,12 @@ simplify_gimple_switch (gswitch *stmt,
> }
> }
> }
> +
> + /* Otherwise try to fold a constant additive offset on the index
> + into the case labels. */
> + if (simplify_gimple_switch_offset (stmt, cond, def_stmt,
> + simple_dce_worklist))
> + return true;
> }
>
> return false;
> --
> 2.34.1
>
