On 07/19/2016 01:18 PM, Richard Biener wrote:
On Tue, Jul 19, 2016 at 1:07 PM, Bernd Schmidt <bschm...@redhat.com> wrote:
On 07/19/2016 12:35 PM, Richard Biener wrote:
I think that start/end_recording_case_labels also merged adjacent labels
via group_case_labels_stmt. Not sure why you need to stop recording
case labels during the transform. Is this because you are building a new
switch stmt?
It's because the cached mapping gets invalidated. Look in tree-cfg, it has a
edge_to_cases map which I think cannot be maintained if you modify the
structure. I certainly got lots of internal errors until I added that pair
of calls.
Yeah, I see that. OTOH cfgcleanup relies on this cache to be efficient and
you (repeatedly) clear it. Clearing parts of it should be sufficient and if you
used redirect_edge_and_branch instead of redirect_edge_pred it would have
maintained the cache as far as I can see,
I don't think that would work, since we're modifying and/or discarding
case labels as well and they can't remain part of the cache.
or you can make sure to maintain
it yourself or just clear the info associated with the edges you redirect from
one switch to another.
How's this? Tested as before.
Bernd
* 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.
Index: gcc/tree-cfg.c
===================================================================
--- gcc/tree-cfg.c (revision 237797)
+++ gcc/tree-cfg.c (working copy)
@@ -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.
Index: gcc/tree-cfg.h
===================================================================
--- gcc/tree-cfg.h (revision 237797)
+++ gcc/tree-cfg.h (working copy)
@@ -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);
Index: gcc/tree-cfgcleanup.c
===================================================================
--- gcc/tree-cfgcleanup.c (revision 237797)
+++ gcc/tree-cfgcleanup.c (working copy)
@@ -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). */
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" } } */
