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