* tree-cfgcleanup.c (try_merge_switches): New static function.
(cleanup_tree_cfg_bb): Call it.
* tree-cfg.c (discard_case_labels_for): New function.
* tree-cfg.h (discard_case_labels_for): Declare 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.
===================================================================
@@ -1185,6 +1185,32 @@ end_recording_case_labels (void)
BITMAP_FREE (touched_switch_bbs);
}
+/* Discard edge information for a single switch. */
+void
+discard_case_labels_for (gswitch *t)
+{
+ if (!recording_case_labels_p ())
+ return;
+
+ basic_block bb = gimple_bb (t);
+ edge_iterator ei;
+ edge e;
+ FOR_EACH_EDGE (e, ei, bb->succs)
+ {
+ tree *slot = edge_to_cases->get (e);
+ if (!slot)
+ continue;
+ edge_to_cases->remove (e);
+ tree t, next;
+ for (t = *slot; t; t = next)
+ {
+ next = CASE_CHAIN (t);
+ CASE_CHAIN (t) = NULL;
+ }
+ *slot = NULL;
+ }
+}
+
/* If we are inside a {start,end}_recording_cases block, then return
a chain of CASE_LABEL_EXPRs from T which reference E.
===================================================================
@@ -33,6 +33,7 @@ extern void init_empty_tree_cfg_for_func
extern void init_empty_tree_cfg (void);
extern void start_recording_case_labels (void);
extern void end_recording_case_labels (void);
+extern void discard_case_labels_for (gswitch *);
extern basic_block label_to_block_fn (struct function *, tree);
#define label_to_block(t) (label_to_block_fn (cfun, t))
extern void cleanup_dead_labels (void);
===================================================================
@@ -630,6 +630,233 @@ 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);
+ gimple *pred_end = last_stmt (pred_bb);
+ if (! pred_end || gimple_code (pred_end) != GIMPLE_SWITCH)
+ return false;
+
+ gsi2 = gsi_start_nondebug_after_labels_bb (bb);
+ if (gsi_end_p (gsi2))
+ return false;
+
+ gimple *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. */
+ discard_case_labels_for (sw1);
+ discard_case_labels_for (sw2);
+
+ /* 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);
+
+ return true;
+}
/* Tries to cleanup cfg in basic block BB. Returns true if anything
changes. */
@@ -641,6 +868,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). */
===================================================================
@@ -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" } } */
===================================================================
@@ -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" } } */
===================================================================
@@ -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" } } */