[PATCH 3/3] Improve switch code emission for a balanced tree (PR tree-optimization/86847).

[marxin <mliska at suse dot cz>]

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  <mliska@suse.cz>

        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  <mliska@suse.cz>

	* 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 00000000000..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..00000000000
--- 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 (&gsi, 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 = EDGE_FALSE_VALUE;
+  false_edge->probability = prob.invert ();
+
+  edge true_edge = make_edge (bb, label_bb, EDGE_TRUE_VALUE);
+  true_edge->probability = prob;
+
+  return false_edge->dest;
+}
+
 /* Emit step-by-step code to select a case for the value of INDEX.
    The thus generated decision tree follows the form of the
    case-node binary tree NODE, whose nodes represent test conditions.
@@ -2066,41 +2095,193 @@ switch_decision_tree::emit_case_nodes (basic_block bb, tree index,
 				       profile_probability default_prob,
 				       tree index_type)
 {
+  profile_probability p;
+
   /* If node is null, we are done.  */
   if (node == NULL)
     return bb;
 
-  /* Branch to a label where we will handle it later.  */
-  basic_block test_bb = split_edge (single_succ_edge (bb));
-  redirect_edge_succ (single_pred_edge (test_bb),
-		      single_succ_edge (bb)->dest);
-
-  profile_probability probability
-    = (node->m_right
-       ? node->m_right->m_c->m_subtree_prob : profile_probability::never ());
-  probability = ((probability + default_prob.apply_scale (1, 2))
-		 / (node->m_c->m_subtree_prob + default_prob));
-  bb = emit_cmp_and_jump_insns (bb, index, node->m_c->get_high (), GT_EXPR,
-				test_bb, probability);
-  default_prob = default_prob.apply_scale (1, 2);
-
-  /* Value belongs to this node or to the left-hand subtree.  */
-  probability = node->m_c->m_prob /
-    (node->m_c->m_subtree_prob + default_prob);
-  bb = emit_cmp_and_jump_insns (bb, index, node->m_c->get_low (), GE_EXPR,
-				node->m_c->m_case_bb, probability);
-
-  /* Handle the left-hand subtree.  */
-  bb = emit_case_nodes (bb, index, node->m_left,
-			default_prob, index_type);
-
-  /* If the left-hand subtree fell through,
-     don't let it fall into the right-hand subtree.  */
-  if (m_default_bb)
-    emit_jump (bb, m_default_bb);
+  /* Single value case.  */
+  if (node->m_c->is_single_value_p ())
+    {
+      /* Node is single valued.  First see if the index expression matches
+	 this node and then check our children, if any.  */
+      p = node->m_c->m_prob / (node->m_c->m_subtree_prob + default_prob);
+      bb = do_jump_if_equal (bb, index, node->m_c->get_low (),
+			     node->m_c->m_case_bb, p);
+      /* Since this case is taken at this point, reduce its weight from
+	 subtree_weight.  */
+      node->m_c->m_subtree_prob -= p;
+
+      if (node->m_left != NULL && node->m_right != NULL)
+	{
+	  /* 1) the node has both children
 
-  bb = emit_case_nodes (test_bb, index, node->m_right,
-			default_prob, index_type);
+	     If both children are single-valued cases with no
+	     children, finish up all the work.  This way, we can save
+	     one ordered comparison.  */
+
+	  if (!node->m_left->has_child ()
+	      && node->m_left->m_c->is_single_value_p ()
+	      && !node->m_right->has_child ()
+	      && node->m_right->m_c->is_single_value_p ())
+	    {
+	      p = (node->m_right->m_c->m_prob
+		   / (node->m_c->m_subtree_prob + default_prob));
+	      bb = do_jump_if_equal (bb, index, node->m_right->m_c->get_low (),
+				     node->m_right->m_c->m_case_bb, p);
+
+	      p = (node->m_left->m_c->m_prob
+		   / (node->m_c->m_subtree_prob + default_prob));
+	      bb = do_jump_if_equal (bb, index, node->m_left->m_c->get_low (),
+				     node->m_left->m_c->m_case_bb, p);
+	    }
+	  else
+	    {
+	      /* Branch to a label where we will handle it later.  */
+	      basic_block test_bb = split_edge (single_succ_edge (bb));
+	      redirect_edge_succ (single_pred_edge (test_bb),
+				  single_succ_edge (bb)->dest);
+
+	      p = ((node->m_right->m_c->m_subtree_prob
+		    + default_prob.apply_scale (1, 2))
+		   / (node->m_c->m_subtree_prob + default_prob));
+	      bb = emit_cmp_and_jump_insns (bb, index, node->m_c->get_high (),
+					    GT_EXPR, test_bb, p);
+	      default_prob = default_prob.apply_scale (1, 2);
+
+	      /* Handle the left-hand subtree.  */
+	      bb = emit_case_nodes (bb, index, node->m_left,
+				    default_prob, index_type);
+
+	      /* If the left-hand subtree fell through,
+		 don't let it fall into the right-hand subtree.  */
+	      if (bb && m_default_bb)
+		emit_jump (bb, m_default_bb);
+
+	      bb = emit_case_nodes (test_bb, index, node->m_right,
+				    default_prob, index_type);
+	    }
+	}
+      else if (node->m_left == NULL && node->m_right != NULL)
+	{
+	  /* 2) the node has only right child.  */
+
+	  /* Here we have a right child but no left so we issue a conditional
+	     branch to default and process the right child.
+
+	     Omit the conditional branch to default if the right child
+	     does not have any children and is single valued; it would
+	     cost too much space to save so little time.  */
+
+	  if (node->m_right->has_child ()
+	      || !node->m_right->m_c->is_single_value_p ())
+	    {
+	      p = (default_prob.apply_scale (1, 2)
+		   / (node->m_c->m_subtree_prob + default_prob));
+	      bb = emit_cmp_and_jump_insns (bb, index, node->m_c->get_low (),
+					    LT_EXPR, m_default_bb, p);
+	      default_prob = default_prob.apply_scale (1, 2);
+
+	      bb = emit_case_nodes (bb, index, node->m_right, default_prob,
+				    index_type);
+	    }
+	  else
+	    {
+	      /* We cannot process node->right normally
+		 since we haven't ruled out the numbers less than
+		 this node's value.  So handle node->right explicitly.  */
+	      p = (node->m_right->m_c->m_subtree_prob
+		   / (node->m_c->m_subtree_prob + default_prob));
+	      bb = do_jump_if_equal (bb, index, node->m_right->m_c->get_low (),
+				     node->m_right->m_c->m_case_bb, p);
+	    }
+	}
+      else if (node->m_left != NULL && node->m_right == NULL)
+	{
+	  /* 3) just one subtree, on the left.  Similar case as previous.  */
+
+	  if (node->m_left->has_child ()
+	      || !node->m_left->m_c->is_single_value_p ())
+	    {
+	      p = (default_prob.apply_scale (1, 2)
+		   / (node->m_c->m_subtree_prob + default_prob));
+	      bb = emit_cmp_and_jump_insns (bb, index, node->m_c->get_low (),
+					    LT_EXPR, m_default_bb, p);
+		  default_prob = default_prob.apply_scale (1, 2);
+
+	      bb = emit_case_nodes (bb, index, node->m_left, default_prob,
+				    index_type);
+	    }
+	  else
+	    {
+	      /* We cannot process node->left normally
+		 since we haven't ruled out the numbers less than
+		 this node's value.  So handle node->left explicitly.  */
+	      p = (node->m_left->m_c->m_subtree_prob
+		   / (node->m_c->m_subtree_prob + default_prob));
+	      bb = do_jump_if_equal (bb, index, node->m_left->m_c->get_low (),
+				     node->m_left->m_c->m_case_bb, p);
+	    }
+	}
+    }
+  else
+    {
+      /* Node is a range.  These cases are very similar to those for a single
+	 value, except that we do not start by testing whether this node
+	 is the one to branch to.  */
+      if (node->has_child () || node->m_c->get_type () != SIMPLE_CASE)
+	{
+	  /* Branch to a label where we will handle it later.  */
+	  basic_block test_bb = split_edge (single_succ_edge (bb));
+	  redirect_edge_succ (single_pred_edge (test_bb),
+			      single_succ_edge (bb)->dest);
+
+
+	   profile_probability right_prob = profile_probability::never ();
+	   if (node->m_right)
+	     right_prob = node->m_right->m_c->m_subtree_prob;
+	  p = ((right_prob + default_prob.apply_scale (1, 2))
+	       / (node->m_c->m_subtree_prob + default_prob));
+
+	  bb = emit_cmp_and_jump_insns (bb, index, node->m_c->get_high (),
+					GT_EXPR, test_bb, p);
+	  default_prob = default_prob.apply_scale (1, 2);
+
+	  /* Value belongs to this node or to the left-hand subtree.  */
+	  p = node->m_c->m_prob / (node->m_c->m_subtree_prob + default_prob);
+	  bb = emit_cmp_and_jump_insns (bb, index, node->m_c->get_low (),
+					GE_EXPR, node->m_c->m_case_bb, p);
+
+	  /* Handle the left-hand subtree.  */
+	  bb = emit_case_nodes (bb, index, node->m_left,
+				default_prob, index_type);
+
+	  /* If the left-hand subtree fell through,
+	     don't let it fall into the right-hand subtree.  */
+	  if (bb && m_default_bb)
+	    emit_jump (bb, m_default_bb);
+
+	  bb = emit_case_nodes (test_bb, index, node->m_right,
+				default_prob, index_type);
+	}
+      else
+	{
+	  /* Node has no children so we check low and high bounds to remove
+	     redundant tests.  Only one of the bounds can exist,
+	     since otherwise this node is bounded--a case tested already.  */
+	  tree lhs, rhs;
+	  generate_range_test (bb, index, node->m_c->get_low (),
+			       node->m_c->get_high (), &lhs, &rhs);
+	  p = default_prob / (node->m_c->m_subtree_prob + default_prob);
+
+	  bb = emit_cmp_and_jump_insns (bb, lhs, rhs, GT_EXPR,
+					m_default_bb, p);
+
+	  emit_jump (bb, node->m_c->m_case_bb);
+	  return NULL;
+	}
+    }
 
   return bb;
 }
diff --git a/gcc/tree-switch-conversion.h b/gcc/tree-switch-conversion.h
index 726d54ad912..37ed2193724 100644
--- a/gcc/tree-switch-conversion.h
+++ b/gcc/tree-switch-conversion.h
@@ -72,6 +72,13 @@ struct cluster
   /* Emit GIMPLE code to handle the cluster.  */
   virtual void emit (tree, tree, tree, basic_block) = 0;
 
+  /* Return true if a cluster handles only a single case value and the
+     value is not a range.  */
+  virtual bool is_single_value_p ()
+  {
+    return false;
+  }
+
   /* Return range of a cluster.  If value would overflow in type of LOW,
      then return 0.  */
   static unsigned HOST_WIDE_INT get_range (tree low, tree high)
@@ -161,6 +168,11 @@ struct simple_cluster: public cluster
     gcc_unreachable ();
   }
 
+  bool is_single_value_p ()
+  {
+    return tree_int_cst_equal (get_low (), get_high ());
+  }
+
   /* Low value of the case.  */
   tree m_low;
 
@@ -435,6 +447,12 @@ struct case_tree_node
   /* Empty Constructor.  */
   case_tree_node ();
 
+  /* Return true when it has a child.  */
+  bool has_child ()
+  {
+    return m_left != NULL || m_right != NULL;
+  }
+
   /* Left son in binary tree.  */
   case_tree_node *m_left;
 
@@ -578,6 +596,12 @@ struct switch_decision_tree
 					      basic_block label_bb,
 					      profile_probability prob);
 
+  /* Generate code to jump to LABEL if OP0 and OP1 are equal in mode MODE.
+     PROB is the probability of jumping to LABEL_BB.  */
+  static basic_block do_jump_if_equal (basic_block bb, tree op0, tree op1,
+				       basic_block label_bb,
+				       profile_probability prob);
+
   /* Reset the aux field of all outgoing edges of switch basic block.  */
   static inline void reset_out_edges_aux (gswitch *swtch);