The motivating example for this patch was a change that was submitted
for genattrtab last year, which would have made us generate
switch (type = get_attr_type (insn))
{
... some cases ...
default:
switch (type = get_attr_type (insn)))
{
... some other cases ...
}
}
The idea was to optimize this by merging the code into a single switch.
My expectation was that this was most likely to occur in
machine-generated code, but there are a few instances of this pattern in
the gcc sources themselves. One case is
code = gimple_code (stmt);
switch (code)
{
....
default:
if (is_gimple_omp (code))
{
}
}
where is_gimple_omp expands into another switch. More cases exist in the
compiler as shown by various bootstrap failures along the way; sometimes
these are exposed after other optimizations. One is in the Ada runtime
library somewhere, and another (which currently cannot be transformed by
the patch) is in the Fortran frontend.
In the future we could also look for if statements making another
comparison of the variable in the default branch, that would be a minor
extension.
The motivating example currently can't be transformed because
get_attr_type calls are in the way.
Bootstrapped and tested on x86_64-linux. Ok?
Bernd
* tree-cfgcleanup.c (try_merge_switches): New function.
(cleanup_tree_cfg_bb): Call it.
* c-c++-common/merge-switch-1.c: New test.
* c-c++-common/merge-switch-2.c: New test.
* c-c++-common/merge-switch-3.c: New test.
Index: gcc/tree-cfgcleanup.c
===================================================================
--- gcc/tree-cfgcleanup.c (revision 237797)
+++ gcc/tree-cfgcleanup.c (working copy)
@@ -630,6 +630,242 @@ fixup_noreturn_call (gimple *stmt)
return changed;
}
+/* Look for situations where we have a switch inside the default case of
+ another, and they switch on the same condition. We look for the
+ second switch in BB. If we find such a situation, merge the two
+ switch statements. */
+
+static bool
+try_merge_switches (basic_block bb)
+{
+ if (!single_pred_p (bb))
+ return false;
+ basic_block pred_bb = single_pred (bb);
+
+ /* Look for a structure with two switch statements on the same value. */
+ gimple_stmt_iterator gsi1, gsi2;
+ gsi1 = gsi_last_nondebug_bb (pred_bb);
+ if (gsi_end_p (gsi1))
+ return false;
+ gimple *pred_end = gsi_stmt (gsi1);
+ if (gimple_code (pred_end) != GIMPLE_SWITCH)
+ return false;
+
+ gsi2 = gsi_after_labels (bb);
+ if (gsi_end_p (gsi2))
+ return false;
+
+ gimple *stmt = gsi_stmt (gsi2);
+ while (is_gimple_debug (stmt))
+ {
+ gsi_next (&gsi2);
+ if (gsi_end_p (gsi2))
+ return false;
+ stmt = gsi_stmt (gsi2);
+ }
+
+ if (gimple_code (stmt) != GIMPLE_SWITCH)
+ return false;
+ gswitch *sw1 = as_a <gswitch *> (pred_end);
+ gswitch *sw2 = as_a <gswitch *> (stmt);
+ tree idx1 = gimple_switch_index (sw1);
+ tree idx2 = gimple_switch_index (sw2);
+ if (TREE_CODE (idx1) != SSA_NAME || idx1 != idx2)
+ return false;
+ size_t n1 = gimple_switch_num_labels (sw1);
+ size_t n2 = gimple_switch_num_labels (sw2);
+ if (n1 <= 1 || n2 <= 1)
+ return false;
+ tree sw1_default = gimple_switch_default_label (sw1);
+ if (label_to_block (CASE_LABEL (sw1_default)) != bb)
+ return false;
+
+ /* We know we have the basic structure of what we are looking for. Sort
+ out some special cases regarding phi nodes. */
+ if (!gsi_end_p (gsi_start_phis (bb)))
+ return false;
+
+ edge e;
+ edge_iterator ei;
+ FOR_EACH_EDGE (e, ei, bb->succs)
+ {
+ basic_block dest = e->dest;
+ if (find_edge (pred_bb, dest))
+ {
+ /* If a destination block is reached from both switches, any
+ phi nodes there would become corrupted. */
+ gphi_iterator psi = gsi_start_phis (dest);
+ if (!gsi_end_p (psi))
+ return false;
+ }
+ }
+
+ /* At this point we know we are making the transformation.
+ Clear the CASE_CHAIN values to avoid inconsistencies. */
+ end_recording_case_labels ();
+
+ /* Start at 1 to skip default labels. */
+ size_t i1 = 1;
+ size_t i2 = 1;
+ tree ce1 = gimple_switch_label (sw1, i1);
+ tree ce2 = gimple_switch_label (sw2, i2);
+ auto_vec<tree> new_labels;
+
+ /* Keep track of the blocks that were reachable from the second switch,
+ and whose edges should be redirected to the first. Sometimes we
+ eliminate cases from the second switch entirely since they are
+ unreachable; in such cases, the bit for the destination block
+ remains clear. */
+ bitmap_head redirect_bbs;
+ bitmap_initialize (&redirect_bbs, &bitmap_default_obstack);
+
+ /* Merge case labels from sw2 into those of sw1. */
+ while (i1 < n1 && i2 < n2)
+ {
+ tree min1 = CASE_LOW (ce1);
+ tree min2 = CASE_LOW (ce2);
+ tree max1 = CASE_HIGH (ce1);
+ tree max2 = CASE_HIGH (ce2);
+ if (max1 == NULL_TREE)
+ max1 = min1;
+ if (max2 == NULL_TREE)
+ max2 = min2;
+
+ if (label_to_block (CASE_LABEL (ce1)) == bb)
+ {
+ /* A non-default case that jumps to the second switch. Drop it. */
+ if (++i1 < n1)
+ ce1 = gimple_switch_label (sw1, i1);
+ }
+ else if (tree_int_cst_compare (min1, max2) > 0)
+ {
+ /* CE2 is a range entirely below that of CE1. */
+ basic_block other_bb = label_to_block (CASE_LABEL (ce2));
+ bitmap_set_bit (&redirect_bbs, other_bb->index);
+ new_labels.safe_push (ce2);
+ if (++i2 < n2)
+ ce2 = gimple_switch_label (sw2, i2);
+ }
+ else if (tree_int_cst_compare (min2, max1) > 0)
+ {
+ /* CE1 is a range entirely below that of CE2. */
+ new_labels.safe_push (ce1);
+ if (++i1 < n1)
+ ce1 = gimple_switch_label (sw1, i1);
+ }
+ else if (tree_int_cst_compare (min1, min2) <= 0)
+ {
+ /* The range of CE1 begins at or below the one of CE2. */
+ if (tree_int_cst_compare (max1, max2) >= 0)
+ {
+ /* CE1 ends after CE2. Drop CE2. */
+ if (++i2 < n2)
+ ce2 = gimple_switch_label (sw2, i2);
+ }
+ else
+ {
+ /* We have overlap. Adjust CE2 to being just after CE1. */
+ new_labels.safe_push (ce1);
+ min2 = int_const_binop (PLUS_EXPR, max1, integer_one_node);
+ CASE_LOW (ce2) = min2;
+ if (++i1 < n1)
+ ce1 = gimple_switch_label (sw1, i1);
+ }
+ }
+ else
+ {
+ /* The range of CE1 begins after CE2, and there is overlap.
+ Adjust and add a copy of CE2 to cover the range up to the
+ start of CE1. */
+ max2 = int_const_binop (MINUS_EXPR, max1, integer_one_node);
+ tree split = copy_node (ce2);
+ CASE_HIGH (split) = max2;
+ CASE_LOW (ce2) = min1;
+ new_labels.safe_push (split);
+ basic_block other_bb = label_to_block (CASE_LABEL (ce2));
+ bitmap_set_bit (&redirect_bbs, other_bb->index);
+ }
+ }
+ /* Append trailing elements of either array. This will never append
+ from both. */
+ while (i1 < n1)
+ {
+ new_labels.safe_push (ce1);
+ if (++i1 < n1)
+ ce1 = gimple_switch_label (sw1, i1);
+ }
+ while (i2 < n2)
+ {
+ basic_block other_bb = label_to_block (CASE_LABEL (ce2));
+ bitmap_set_bit (&redirect_bbs, other_bb->index);
+ new_labels.safe_push (ce2);
+ if (++i2 < n2)
+ ce2 = gimple_switch_label (sw2, i2);
+ }
+
+ /* Merge adjacent ranges. */
+ size_t new_count = new_labels.length ();
+ for (i1 = i2 = 1; i1 < new_count; )
+ {
+ ce1 = new_labels[i1++];
+ tree high = CASE_HIGH (ce1);
+ if (high == NULL_TREE)
+ high = CASE_LOW (ce1);
+ while (i1 < new_count)
+ {
+ ce2 = new_labels[i1];
+ if (!integer_onep (int_const_binop (MINUS_EXPR, CASE_LOW (ce2),
+ high))
+ || CASE_LABEL (ce1) != CASE_LABEL (ce2))
+ break;
+
+ CASE_HIGH (ce1) = CASE_HIGH (ce2);
+ i1++;
+ }
+ new_labels[i2++] = ce1;
+ }
+ new_labels.truncate (i2);
+
+ /* Create a replacement switch. */
+ tree sw2_default = gimple_switch_default_label (sw2);
+ basic_block other_bb = label_to_block (CASE_LABEL (sw2_default));
+ bitmap_set_bit (&redirect_bbs, other_bb->index);
+
+ gswitch *new_sw1 = gimple_build_switch (gimple_switch_index (sw1),
+ sw2_default, new_labels);
+ gsi_replace (&gsi1, new_sw1, false);
+
+ /* Redirect edges. */
+
+ for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); )
+ {
+ basic_block dest = e->dest;
+ if (!bitmap_bit_p (&redirect_bbs, dest->index)
+ || find_edge (pred_bb, dest))
+ {
+ ei_next (&ei);
+ continue;
+ }
+ redirect_edge_pred (e, pred_bb);
+ bitmap_set_bit (cfgcleanup_altered_bbs, dest->index);
+ }
+
+ if (dom_info_available_p (CDI_DOMINATORS))
+ {
+ basic_block dombb = get_immediate_dominator (CDI_DOMINATORS, bb);
+ gcc_assert (dombb == pred_bb);
+ vec<basic_block> fix_bbs;
+ fix_bbs = get_all_dominated_blocks (CDI_DOMINATORS, pred_bb);
+ iterate_fix_dominators (CDI_DOMINATORS, fix_bbs, false);
+ fix_bbs.release ();
+ }
+
+ remove_edge_and_dominated_blocks (single_pred_edge (bb));
+ bitmap_clear (&redirect_bbs);
+
+ start_recording_case_labels ();
+ return true;
+}
/* Tries to cleanup cfg in basic block BB. Returns true if anything
changes. */
@@ -641,6 +877,9 @@ cleanup_tree_cfg_bb (basic_block bb)
&& remove_forwarder_block (bb))
return true;
+ if (try_merge_switches (bb))
+ return true;
+
/* Merging the blocks may create new opportunities for folding
conditional branches (due to the elimination of single-valued PHI
nodes). */
Index: gcc/testsuite/c-c++-common/merge-switch-1.c
===================================================================
--- gcc/testsuite/c-c++-common/merge-switch-1.c (revision 0)
+++ gcc/testsuite/c-c++-common/merge-switch-1.c (working copy)
@@ -0,0 +1,30 @@
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+
+__attribute__((noinline,noclone)) int foo (int c)
+{
+ switch (c)
+ {
+ case 1:
+ case 3:
+ case 5:
+ case 7:
+ case 9:
+ case 11:
+ return 5;
+ default:
+ switch (c)
+ {
+ case 0:
+ case 2:
+ case 4:
+ case 6:
+ case 8:
+ case 10:
+ return 5;
+ default:
+ return 0;
+ }
+ }
+}
+/* { dg-final { scan-tree-dump-times "switch" 1 "optimized" } } */
+/* { dg-final { scan-tree-dump-times "case 0 \\.\\.\\. 11" 1 "optimized" } } */
Index: gcc/testsuite/c-c++-common/merge-switch-2.c
===================================================================
--- gcc/testsuite/c-c++-common/merge-switch-2.c (revision 0)
+++ gcc/testsuite/c-c++-common/merge-switch-2.c (working copy)
@@ -0,0 +1,32 @@
+/* { dg-options "-O2 -fdump-tree-dse1" } */
+
+/* We use the dse1 dump since it's before switchconv, but after a cfg
+ cleanup pass which should take care of merging the switches. */
+int foo (int c)
+{
+ switch (c)
+ {
+ case 1:
+ case 3:
+ case 5:
+ case 7:
+ case 9:
+ case 11:
+ return 4;
+ default:
+ switch (c)
+ {
+ case 0:
+ case 2:
+ case 4:
+ case 6:
+ case 8:
+ case 10:
+ return 5;
+ default:
+ return 0;
+ }
+ }
+}
+/* { dg-final { scan-tree-dump-times "switch" 1 "dse1" } } */
+/* { dg-final { scan-tree-dump-not "\\.\\.\\." "dse1" } } */
Index: gcc/testsuite/c-c++-common/merge-switch-3.c
===================================================================
--- gcc/testsuite/c-c++-common/merge-switch-3.c (revision 0)
+++ gcc/testsuite/c-c++-common/merge-switch-3.c (working copy)
@@ -0,0 +1,31 @@
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+/* Sanity check that switch merging doesn't happen when switching on
+ different variables. */
+
+int foo (int c, int d)
+{
+ switch (c)
+ {
+ case 1:
+ case 30:
+ case 51:
+ case 73:
+ case 92:
+ case 115:
+ return 4;
+ default:
+ switch (d)
+ {
+ case 10:
+ case 22:
+ case 42:
+ case 62:
+ case 81:
+ case 101:
+ return 5;
+ default:
+ return 0;
+ }
+ }
+}
+/* { dg-final { scan-tree-dump-times "switch" 2 "optimized" } } */
