This is the most complex patch. It follows original implementation and
does following improvements that were part of original code:
a) for a node with both children (that don't have children) and only single case
values handled: emit series of 3 compares and jump to default
b) for a node with only one child (that doesn't have a child) and only single
case values handled: emit 2 compares and jump to default
c) for a node of a range without a child, emit if (index - low) <= (high - low))
d) profile emission is precise, taken also from previous implementation
These changes + VRP should move us back to code quality we had in GCC 8.
gcc/ChangeLog:
2018-08-13 Martin Liska
PR tree-optimization/86847
* tree-switch-conversion.c (switch_decision_tree::dump_case_nodes):
Dump also subtree probability.
(switch_decision_tree::do_jump_if_equal): New function.
(switch_decision_tree::emit_case_nodes): Handle special
situations in balanced tree that can be emitted much simpler.
Fix calculation of probabilities that happen in tree expansion.
* tree-switch-conversion.h (struct cluster): Add
is_single_value_p.
(struct simple_cluster): Likewise.
(struct case_tree_node): Add new function has_child.
(do_jump_if_equal): New.
gcc/testsuite/ChangeLog:
2018-08-13 Martin Liska
* gcc.dg/tree-ssa/switch-3.c: New test.
* gcc.dg/tree-ssa/vrp105.c: Remove.
---
gcc/testsuite/gcc.dg/tree-ssa/switch-3.c | 20 ++
gcc/testsuite/gcc.dg/tree-ssa/vrp105.c | 37
gcc/tree-switch-conversion.c | 243 ---
gcc/tree-switch-conversion.h | 24 +++
4 files changed, 256 insertions(+), 68 deletions(-)
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/switch-3.c
delete mode 100644 gcc/testsuite/gcc.dg/tree-ssa/vrp105.c
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/switch-3.c b/gcc/testsuite/gcc.dg/tree-ssa/switch-3.c
new file mode 100644
index 000..44981e1d186
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/switch-3.c
@@ -0,0 +1,20 @@
+/* { dg-options "-O2 -fdump-tree-switchlower1" } */
+
+int cipher_to_alg(int cipher)
+{
+ switch (cipher)
+{
+ case 8: return 2;
+ case 16: return 3;
+ case 32: return 4;
+ case 64: return 6;
+ case 256: return 9;
+ case 512: return 10;
+ case 2048: return 11;
+ case 4096: return 12;
+ case 8192: return 13;
+}
+ return 0;
+}
+
+/* { dg-final { scan-tree-dump-times "if \\(cipher\[^\n ]*" 12 "switchlower1" } } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp105.c b/gcc/testsuite/gcc.dg/tree-ssa/vrp105.c
deleted file mode 100644
index 7cdd4dd8f3a..000
--- a/gcc/testsuite/gcc.dg/tree-ssa/vrp105.c
+++ /dev/null
@@ -1,37 +0,0 @@
-/* PR tree-optimization/18046 */
-/* { dg-options "-O2 -fdump-tree-vrp2-details" } */
-/* { dg-final { scan-tree-dump-times "Threaded jump" 1 "vrp2" } } */
-/* In the 2nd VRP pass (after PRE) we expect to thread the default label of the
- 1st switch straight to that of the 2nd switch. */
-
-extern void foo (void);
-extern void bar (void);
-
-extern int i;
-void
-test (void)
-{
- switch (i)
-{
-case 0:
- foo ();
- break;
-case 1:
- bar ();
- break;
-default:
- break;
-}
-
- switch (i)
-{
-case 0:
- foo ();
- break;
-case 1:
- bar ();
- break;
-default:
- break;
-}
-}
diff --git a/gcc/tree-switch-conversion.c b/gcc/tree-switch-conversion.c
index cd771438214..78914bbe81a 100644
--- a/gcc/tree-switch-conversion.c
+++ b/gcc/tree-switch-conversion.c
@@ -2008,7 +2008,9 @@ switch_decision_tree::dump_case_nodes (FILE *f, case_tree_node *root,
fprintf (f, "%*s", indent_step * indent_level, "");
root->m_c->dump (f);
root->m_c->m_prob.dump (f);
- fputs ("\n", f);
+ fputs (" subtree: ", f);
+ root->m_c->m_subtree_prob.dump (f);
+ fputs (")\n", f);
dump_case_nodes (f, root->m_right, indent_step, indent_level);
}
@@ -2054,6 +2056,33 @@ switch_decision_tree::emit_cmp_and_jump_insns (basic_block bb, tree op0,
return false_edge->dest;
}
+/* Generate code to jump to LABEL if OP0 and OP1 are equal in mode MODE.
+ PROB is the probability of jumping to LABEL_BB. */
+
+basic_block
+switch_decision_tree::do_jump_if_equal (basic_block bb, tree op0, tree op1,
+ basic_block label_bb,
+ profile_probability prob)
+{
+ op1 = fold_convert (TREE_TYPE (op0), op1);
+
+ gcond *cond = gimple_build_cond (EQ_EXPR, op0, op1, NULL_TREE, NULL_TREE);
+ gimple_stmt_iterator gsi = gsi_last_bb (bb);
+ gsi_insert_before (, cond, GSI_SAME_STMT);
+
+ gcc_assert (single_succ_p (bb));
+
+ /* Make a new basic block where false branch will take place. */
+ edge false_edge = split_block (bb, cond);
+ false_edge->flags
