Switch other switch expansion methods into classes.

2018-06-20  Martin Liska  <mliska@suse.cz>

	* tree-switch-conversion.c (switch_conversion::collect):
        Record m_uniq property.
	(switch_conversion::expand): Bail out for special conditions.
	(group_cluster::~group_cluster): New.
	(group_cluster::group_cluster): Likewise.
	(group_cluster::dump): Likewise.
	(jump_table_cluster::emit): New.
	(switch_decision_tree::fix_phi_operands_for_edges): New.
	(struct case_node): Remove struct.
	(jump_table_cluster::can_be_handled): New.
	(case_values_threshold): Moved to header.
	(reset_out_edges_aux): Likewise.
	(jump_table_cluster::is_beneficial): New.
	(bit_test_cluster::can_be_handled): Likewise.
	(add_case_node): Remove.
	(bit_test_cluster::is_beneficial): New.
	(case_bit_test::cmp): New.
	(bit_test_cluster::emit): New.
	(expand_switch_as_decision_tree_p): Remove.
	(bit_test_cluster::hoist_edge_and_branch_if_true): New.
	(fix_phi_operands_for_edge): Likewise.
	(switch_decision_tree::analyze_switch_statement): New.
	(compute_cases_per_edge): Move ...
	(switch_decision_tree::compute_cases_per_edge): ... here.
	(try_switch_expansion): Likewise.
	(switch_decision_tree::try_switch_expansion): Likewise.
	(record_phi_operand_mapping): Likewise.
	(switch_decision_tree::record_phi_operand_mapping): Likewise.
	(emit_case_decision_tree): Likewise.
	(switch_decision_tree::emit): Likewise.
	(balance_case_nodes): Likewise.
	(switch_decision_tree::balance_case_nodes): Likewise.
	(dump_case_nodes): Likewise.
	(switch_decision_tree::dump_case_nodes): Likewise.
	(emit_jump): Likewise.
	(switch_decision_tree::emit_jump): Likewise.
	(emit_cmp_and_jump_insns): Likewise.
	(switch_decision_tree::emit_cmp_and_jump_insns): Likewise.
	(emit_case_nodes): Likewise.
	(switch_decision_tree::emit_case_nodes): Likewise.
	(conditional_probability): Remove.
	* tree-switch-conversion.h (enum cluster_type): New.
	(PRINT_CASE): New.
	(struct cluster): Likewise.
	(cluster::cluster): Likewise.
	(struct simple_cluster): Likewise.
	(simple_cluster::simple_cluster): Likewise.
	(struct group_cluster): Likewise.
	(struct jump_table_cluster): Likewise.
	(struct bit_test_cluster): Likewise.
	(struct min_cluster_item): Likewise.
	(struct case_tree_node): Likewise.
	(case_tree_node::case_tree_node): Likewise.
	(jump_table_cluster::case_values_threshold): Likewise.
	(struct case_bit_test): Likewise.
	(struct switch_decision_tree): Likewise.
	(struct switch_conversion): Likewise.
	(switch_decision_tree::reset_out_edges_aux): Likewise.
2018-06-20  Martin Liska  <mliska@suse.cz>

	* gcc.dg/tree-ssa/vrp104.c: Grep just for GIMPLE IL.

From-SVN: r261793

1 files changed, 848 insertions, 528 deletions

diff --git a/gcc/tree-switch-conversion.c b/gcc/tree-switch-conversion.c
index e8b44bdd2d8..1260ba2e145 100644
--- a/gcc/tree-switch-conversion.c
+++ b/gcc/tree-switch-conversion.c
@@ -179,6 +179,11 @@ switch_conversion::collect (gswitch *swtch)
 	  && ! tree_int_cst_equal (CASE_LOW (elt), CASE_HIGH (elt)))
 	m_count++;
     }
+
+  /* Get the number of unique non-default targets out of the GIMPLE_SWITCH
+     block.  Assume a CFG cleanup would have already removed degenerate
+     switch statements, this allows us to just use EDGE_COUNT.  */
+  m_uniq = EDGE_COUNT (gimple_bb (swtch)->succs) - 1;
 }
 
 /* Checks whether the range given by individual case statements of the switch
@@ -935,6 +940,22 @@ switch_conversion::expand (gswitch *swtch)
   /* A switch on a constant should have been optimized in tree-cfg-cleanup.  */
   gcc_checking_assert (!TREE_CONSTANT (m_index_expr));
 
+  /* Prefer bit test if possible.  */
+  if (tree_fits_uhwi_p (m_range_size)
+      && bit_test_cluster::can_be_handled (tree_to_uhwi (m_range_size), m_uniq)
+      && bit_test_cluster::is_beneficial (m_count, m_uniq))
+    {
+      m_reason = "expanding as bit test is preferable";
+      return;
+    }
+
+  if (m_uniq <= 2)
+    {
+      /* This will be expanded as a decision tree .  */
+      m_reason = "expanding as jumps is preferable";
+      return;
+    }
+
   /* If there is no common successor, we cannot do the transformation.  */
   if (!m_final_bb)
     {
@@ -985,157 +1006,443 @@ switch_conversion::~switch_conversion ()
   XDELETEVEC (m_default_values);
 }
 
-/* The main function of the pass scans statements for switches and invokes
-   process_switch on them.  */
+/* Constructor.  */
 
-namespace {
+group_cluster::group_cluster (vec<cluster *> &clusters,
+			      unsigned start, unsigned end)
+{
+  gcc_checking_assert (end - start + 1 >= 1);
+  m_prob = profile_probability::never ();
+  m_cases.create (end - start + 1);
+  for (unsigned i = start; i <= end; i++)
+    {
+      m_cases.quick_push (static_cast<simple_cluster *> (clusters[i]));
+      m_prob += clusters[i]->m_prob;
+    }
+  m_subtree_prob = m_prob;
+}
 
-const pass_data pass_data_convert_switch =
+/* Destructor.  */
+
+group_cluster::~group_cluster ()
 {
-  GIMPLE_PASS, /* type */
-  "switchconv", /* name */
-  OPTGROUP_NONE, /* optinfo_flags */
-  TV_TREE_SWITCH_CONVERSION, /* tv_id */
-  ( PROP_cfg | PROP_ssa ), /* properties_required */
-  0, /* properties_provided */
-  0, /* properties_destroyed */
-  0, /* todo_flags_start */
-  TODO_update_ssa, /* todo_flags_finish */
-};
+  for (unsigned i = 0; i < m_cases.length (); i++)
+    delete m_cases[i];
 
-class pass_convert_switch : public gimple_opt_pass
+  m_cases.release ();
+}
+
+/* Dump content of a cluster.  */
+
+void
+group_cluster::dump (FILE *f, bool details)
 {
-public:
-  pass_convert_switch (gcc::context *ctxt)
-    : gimple_opt_pass (pass_data_convert_switch, ctxt)
-  {}
+  unsigned total_values = 0;
+  for (unsigned i = 0; i < m_cases.length (); i++)
+    total_values += m_cases[i]->get_range (m_cases[i]->get_low (),
+					   m_cases[i]->get_high ());
 
-  /* opt_pass methods: */
-  virtual bool gate (function *) { return flag_tree_switch_conversion != 0; }
-  virtual unsigned int execute (function *);
+  unsigned comparison_count = 0;
+  for (unsigned i = 0; i < m_cases.length (); i++)
+    {
+      simple_cluster *sc = static_cast<simple_cluster *> (m_cases[i]);
+      comparison_count += sc->m_range_p ? 2 : 1;
+    }
 
-}; // class pass_convert_switch
+  unsigned HOST_WIDE_INT range = get_range (get_low (), get_high ());
+  fprintf (f, "%s", get_type () == JUMP_TABLE ? "JT" : "BT");
 
-unsigned int
-pass_convert_switch::execute (function *fun)
+  if (details)
+    fprintf (f, "(values:%d comparisons:%d range:" HOST_WIDE_INT_PRINT_DEC
+	     " density: %.2f%%)", total_values, comparison_count, range,
+	     100.0f * comparison_count / range);
+
+  fprintf (f, ":");
+  PRINT_CASE (f, get_low ());
+  fprintf (f, "-");
+  PRINT_CASE (f, get_high ());
+  fprintf (f, " ");
+}
+
+/* Emit GIMPLE code to handle the cluster.  */
+
+void
+jump_table_cluster::emit (tree index_expr, tree,
+			  tree default_label_expr, basic_block default_bb)
 {
-  basic_block bb;
-  bool cfg_altered = false;
+  /* For jump table we just emit a new gswitch statement that will
+     be latter lowered to jump table.  */
+  auto_vec <tree> labels;
+  labels.create (m_cases.length ());
 
-  FOR_EACH_BB_FN (bb, fun)
-  {
-    gimple *stmt = last_stmt (bb);
-    if (stmt && gimple_code (stmt) == GIMPLE_SWITCH)
-      {
-	if (dump_file)
-	  {
-	    expanded_location loc = expand_location (gimple_location (stmt));
+  make_edge (m_case_bb, default_bb, 0);
+  for (unsigned i = 0; i < m_cases.length (); i++)
+    {
+      labels.quick_push (unshare_expr (m_cases[i]->m_case_label_expr));
+      make_edge (m_case_bb, m_cases[i]->m_case_bb, 0);
+    }
 
-	    fprintf (dump_file, "beginning to process the following "
-		     "SWITCH statement (%s:%d) : ------- \n",
-		     loc.file, loc.line);
-	    print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
-	    putc ('\n', dump_file);
-	  }
+  gswitch *s = gimple_build_switch (index_expr,
+				    unshare_expr (default_label_expr), labels);
+  gimple_stmt_iterator gsi = gsi_start_bb (m_case_bb);
+  gsi_insert_after (&gsi, s, GSI_NEW_STMT);
+}
 
-	switch_conversion sconv;
-	sconv.expand (as_a <gswitch *> (stmt));
-	cfg_altered |= sconv.m_cfg_altered;
-	if (!sconv.m_reason)
-	  {
-	    if (dump_file)
-	      {
-		fputs ("Switch converted\n", dump_file);
-		fputs ("--------------------------------\n", dump_file);
-	      }
+/* Return true when cluster starting at START and ending at END (inclusive)
+   can build a jump-table.  */
 
-	    /* Make no effort to update the post-dominator tree.
-	       It is actually not that hard for the transformations
-	       we have performed, but it is not supported
-	       by iterate_fix_dominators.  */
-	    free_dominance_info (CDI_POST_DOMINATORS);
-	  }
-	else
-	  {
-	    if (dump_file)
-	      {
-		fputs ("Bailing out - ", dump_file);
-		fputs (sconv.m_reason, dump_file);
-		fputs ("\n--------------------------------\n", dump_file);
-	      }
-	  }
-      }
-  }
+bool
+jump_table_cluster::can_be_handled (const vec<cluster *> &clusters,
+				    unsigned start, unsigned end)
+{
+  /* If the switch is relatively small such that the cost of one
+     indirect jump on the target are higher than the cost of a
+     decision tree, go with the decision tree.
 
-  return cfg_altered ? TODO_cleanup_cfg : 0;;
+     If range of values is much bigger than number of values,
+     or if it is too large to represent in a HOST_WIDE_INT,
+     make a sequence of conditional branches instead of a dispatch.
+
+     The definition of "much bigger" depends on whether we are
+     optimizing for size or for speed.  If the former, the maximum
+     ratio range/count = 3, because this was found to be the optimal
+     ratio for size on i686-pc-linux-gnu, see PR11823.  The ratio
+     10 is much older, and was probably selected after an extensive
+     benchmarking investigation on numerous platforms.  Or maybe it
+     just made sense to someone at some point in the history of GCC,
+     who knows...  */
+  if (!flag_jump_tables)
+    return false;
+
+  unsigned HOST_WIDE_INT max_ratio = optimize_insn_for_size_p () ? 3 : 10;
+
+  unsigned HOST_WIDE_INT range = get_range (clusters[start]->get_low (),
+					    clusters[end]->get_high ());
+  /* Check overflow.  */
+  if (range == 0)
+    return false;
+
+  unsigned HOST_WIDE_INT comparison_count = 0;
+  for (unsigned i = start; i <= end; i++)
+    {
+      simple_cluster *sc = static_cast<simple_cluster *> (clusters[i]);
+      comparison_count += sc->m_range_p ? 2 : 1;
+    }
+
+  return range <= max_ratio * comparison_count;
 }
 
-} // anon namespace
+/* Return true if cluster starting at START and ending at END (inclusive)
+   is profitable transformation.  */
 
-gimple_opt_pass *
-make_pass_convert_switch (gcc::context *ctxt)
+bool
+jump_table_cluster::is_beneficial (const vec<cluster *> &,
+				   unsigned start, unsigned end)
 {
-  return new pass_convert_switch (ctxt);
+  return end - start + 1 >= case_values_threshold ();
 }
 
-struct case_node
+/* Return true when RANGE of case values with UNIQ labels
+   can build a bit test.  */
+
+bool
+bit_test_cluster::can_be_handled (unsigned HOST_WIDE_INT range,
+				  unsigned int uniq)
 {
-  case_node		*left;	/* Left son in binary tree.  */
-  case_node		*right;	/* Right son in binary tree;
-				   also node chain.  */
-  case_node		*parent; /* Parent of node in binary tree.  */
-  tree			low;	/* Lowest index value for this label.  */
-  tree			high;	/* Highest index value for this label.  */
-  basic_block		case_bb; /* Label to jump to when node matches.  */
-  tree			case_label; /* Label to jump to when node matches.  */
-  profile_probability   prob; /* Probability of taking this case.  */
-  profile_probability   subtree_prob;  /* Probability of reaching subtree
-					  rooted at this node.  */
-};
+  /* Check overflow.  */
+  if (range == 0)
+    return 0;
 
-typedef case_node *case_node_ptr;
+  if (range >= GET_MODE_BITSIZE (word_mode))
+    return false;
 
-static basic_block emit_case_nodes (basic_block, tree, case_node_ptr,
-				    basic_block, tree, profile_probability,
-				    tree, hash_map<tree, tree> *);
+  return uniq <= 3;
+}
 
-/* Return the smallest number of different values for which it is best to use a
-   jump-table instead of a tree of conditional branches.  */
+/* Return true when cluster starting at START and ending at END (inclusive)
+   can build a bit test.  */
 
-static unsigned int
-case_values_threshold (void)
+bool
+bit_test_cluster::can_be_handled (const vec<cluster *> &clusters,
+				  unsigned start, unsigned end)
 {
-  unsigned int threshold = PARAM_VALUE (PARAM_CASE_VALUES_THRESHOLD);
+  unsigned HOST_WIDE_INT range = get_range (clusters[start]->get_low (),
+					    clusters[end]->get_high ());
+  auto_bitmap dest_bbs;
 
-  if (threshold == 0)
-    threshold = targetm.case_values_threshold ();
+  for (unsigned i = start; i <= end; i++)
+    {
+      simple_cluster *sc = static_cast<simple_cluster *> (clusters[i]);
+      bitmap_set_bit (dest_bbs, sc->m_case_bb->index);
+    }
 
-  return threshold;
+  return can_be_handled (range, bitmap_count_bits (dest_bbs));
 }
 
-/* Reset the aux field of all outgoing edges of basic block BB.  */
+/* Return true when COUNT of cases of UNIQ labels is beneficial for bit test
+   transformation.  */
 
-static inline void
-reset_out_edges_aux (basic_block bb)
+bool
+bit_test_cluster::is_beneficial (unsigned count, unsigned uniq)
 {
-  edge e;
-  edge_iterator ei;
-  FOR_EACH_EDGE (e, ei, bb->succs)
-    e->aux = (void *) 0;
+  return (((uniq == 1 && count >= 3)
+	   || (uniq == 2 && count >= 5)
+	   || (uniq == 3 && count >= 6)));
+}
+
+/* Return true if cluster starting at START and ending at END (inclusive)
+   is profitable transformation.  */
+
+bool
+bit_test_cluster::is_beneficial (const vec<cluster *> &clusters,
+				 unsigned start, unsigned end)
+{
+  auto_bitmap dest_bbs;
+
+  for (unsigned i = start; i <= end; i++)
+    {
+      simple_cluster *sc = static_cast<simple_cluster *> (clusters[i]);
+      bitmap_set_bit (dest_bbs, sc->m_case_bb->index);
+    }
+
+  unsigned uniq = bitmap_count_bits (dest_bbs);
+  unsigned count = end - start + 1;
+  return is_beneficial (count, uniq);
+}
+
+/* Comparison function for qsort to order bit tests by decreasing
+   probability of execution.  */
+
+int
+case_bit_test::cmp (const void *p1, const void *p2)
+{
+  const struct case_bit_test *const d1 = (const struct case_bit_test *) p1;
+  const struct case_bit_test *const d2 = (const struct case_bit_test *) p2;
+
+  if (d2->bits != d1->bits)
+    return d2->bits - d1->bits;
+
+  /* Stabilize the sort.  */
+  return (LABEL_DECL_UID (CASE_LABEL (d2->label))
+	  - LABEL_DECL_UID (CASE_LABEL (d1->label)));
+}
+
+/*  Expand a switch statement by a short sequence of bit-wise
+    comparisons.  "switch(x)" is effectively converted into
+    "if ((1 << (x-MINVAL)) & CST)" where CST and MINVAL are
+    integer constants.
+
+    INDEX_EXPR is the value being switched on.
+
+    MINVAL is the lowest case value of in the case nodes,
+    and RANGE is highest value minus MINVAL.  MINVAL and RANGE
+    are not guaranteed to be of the same type as INDEX_EXPR
+    (the gimplifier doesn't change the type of case label values,
+    and MINVAL and RANGE are derived from those values).
+    MAXVAL is MINVAL + RANGE.
+
+    There *MUST* be max_case_bit_tests or less unique case
+    node targets.  */
+
+void
+bit_test_cluster::emit (tree index_expr, tree index_type,
+			tree, basic_block default_bb)
+{
+  struct case_bit_test test[m_max_case_bit_tests] = { {} };
+  unsigned int i, j, k;
+  unsigned int count;
+
+  tree unsigned_index_type = unsigned_type_for (index_type);
+
+  gimple_stmt_iterator gsi;
+  gassign *shift_stmt;
+
+  tree idx, tmp, csui;
+  tree word_type_node = lang_hooks.types.type_for_mode (word_mode, 1);
+  tree word_mode_zero = fold_convert (word_type_node, integer_zero_node);
+  tree word_mode_one = fold_convert (word_type_node, integer_one_node);
+  int prec = TYPE_PRECISION (word_type_node);
+  wide_int wone = wi::one (prec);
+
+  tree minval = get_low ();
+  tree maxval = get_high ();
+  tree range = int_const_binop (MINUS_EXPR, maxval, minval);
+
+  /* Go through all case labels, and collect the case labels, profile
+     counts, and other information we need to build the branch tests.  */
+  count = 0;
+  for (i = 0; i < m_cases.length (); i++)
+    {
+      unsigned int lo, hi;
+      simple_cluster *n = static_cast<simple_cluster *> (m_cases[i]);
+      for (k = 0; k < count; k++)
+	if (n->m_case_bb == test[k].target_bb)
+	  break;
+
+      if (k == count)
+	{
+	  gcc_checking_assert (count < m_max_case_bit_tests);
+	  test[k].mask = wi::zero (prec);
+	  test[k].target_bb = n->m_case_bb;
+	  test[k].label = n->m_case_label_expr;
+	  test[k].bits = 1;
+	  count++;
+	}
+      else
+	test[k].bits++;
+
+      lo = tree_to_uhwi (int_const_binop (MINUS_EXPR, n->get_low (), minval));
+      if (n->get_high () == NULL_TREE)
+	hi = lo;
+      else
+	hi = tree_to_uhwi (int_const_binop (MINUS_EXPR, n->get_high (),
+					    minval));
+
+      for (j = lo; j <= hi; j++)
+	test[k].mask |= wi::lshift (wone, j);
+    }
+
+  qsort (test, count, sizeof (*test), case_bit_test::cmp);
+
+  /* If all values are in the 0 .. BITS_PER_WORD-1 range, we can get rid of
+     the minval subtractions, but it might make the mask constants more
+     expensive.  So, compare the costs.  */
+  if (compare_tree_int (minval, 0) > 0
+      && compare_tree_int (maxval, GET_MODE_BITSIZE (word_mode)) < 0)
+    {
+      int cost_diff;
+      HOST_WIDE_INT m = tree_to_uhwi (minval);
+      rtx reg = gen_raw_REG (word_mode, 10000);
+      bool speed_p = optimize_insn_for_speed_p ();
+      cost_diff = set_rtx_cost (gen_rtx_PLUS (word_mode, reg,
+					      GEN_INT (-m)), speed_p);
+      for (i = 0; i < count; i++)
+	{
+	  rtx r = immed_wide_int_const (test[i].mask, word_mode);
+	  cost_diff += set_src_cost (gen_rtx_AND (word_mode, reg, r),
+				     word_mode, speed_p);
+	  r = immed_wide_int_const (wi::lshift (test[i].mask, m), word_mode);
+	  cost_diff -= set_src_cost (gen_rtx_AND (word_mode, reg, r),
+				     word_mode, speed_p);
+	}
+      if (cost_diff > 0)
+	{
+	  for (i = 0; i < count; i++)
+	    test[i].mask = wi::lshift (test[i].mask, m);
+	  minval = build_zero_cst (TREE_TYPE (minval));
+	  range = maxval;
+	}
+    }
+
+  /* Now build the test-and-branch code.  */
+
+  gsi = gsi_last_bb (m_case_bb);
+
+  /* idx = (unsigned)x - minval.  */
+  idx = fold_convert (unsigned_index_type, index_expr);
+  idx = fold_build2 (MINUS_EXPR, unsigned_index_type, idx,
+		     fold_convert (unsigned_index_type, minval));
+  idx = force_gimple_operand_gsi (&gsi, idx,
+				  /*simple=*/true, NULL_TREE,
+				  /*before=*/true, GSI_SAME_STMT);
+
+  /* if (idx > range) goto default */
+  range = force_gimple_operand_gsi (&gsi,
+				    fold_convert (unsigned_index_type, range),
+				    /*simple=*/true, NULL_TREE,
+				    /*before=*/true, GSI_SAME_STMT);
+  tmp = fold_build2 (GT_EXPR, boolean_type_node, idx, range);
+  basic_block new_bb = hoist_edge_and_branch_if_true (&gsi, tmp, default_bb);
+  gsi = gsi_last_bb (new_bb);
+
+  /* csui = (1 << (word_mode) idx) */
+  csui = make_ssa_name (word_type_node);
+  tmp = fold_build2 (LSHIFT_EXPR, word_type_node, word_mode_one,
+		     fold_convert (word_type_node, idx));
+  tmp = force_gimple_operand_gsi (&gsi, tmp,
+				  /*simple=*/false, NULL_TREE,
+				  /*before=*/true, GSI_SAME_STMT);
+  shift_stmt = gimple_build_assign (csui, tmp);
+  gsi_insert_before (&gsi, shift_stmt, GSI_SAME_STMT);
+  update_stmt (shift_stmt);
+
+  /* for each unique set of cases:
+       if (const & csui) goto target  */
+  for (k = 0; k < count; k++)
+    {
+      tmp = wide_int_to_tree (word_type_node, test[k].mask);
+      tmp = fold_build2 (BIT_AND_EXPR, word_type_node, csui, tmp);
+      tmp = force_gimple_operand_gsi (&gsi, tmp,
+				      /*simple=*/true, NULL_TREE,
+				      /*before=*/true, GSI_SAME_STMT);
+      tmp = fold_build2 (NE_EXPR, boolean_type_node, tmp, word_mode_zero);
+      new_bb = hoist_edge_and_branch_if_true (&gsi, tmp, test[k].target_bb);
+      gsi = gsi_last_bb (new_bb);
+    }
+
+  /* We should have removed all edges now.  */
+  gcc_assert (EDGE_COUNT (gsi_bb (gsi)->succs) == 0);
+
+  /* If nothing matched, go to the default label.  */
+  make_edge (gsi_bb (gsi), default_bb, EDGE_FALLTHRU);
+}
+
+/* Split the basic block at the statement pointed to by GSIP, and insert
+   a branch to the target basic block of E_TRUE conditional on tree
+   expression COND.
+
+   It is assumed that there is already an edge from the to-be-split
+   basic block to E_TRUE->dest block.  This edge is removed, and the
+   profile information on the edge is re-used for the new conditional
+   jump.
+
+   The CFG is updated.  The dominator tree will not be valid after
+   this transformation, but the immediate dominators are updated if
+   UPDATE_DOMINATORS is true.
+
+   Returns the newly created basic block.  */
+
+basic_block
+bit_test_cluster::hoist_edge_and_branch_if_true (gimple_stmt_iterator *gsip,
+						 tree cond, basic_block case_bb)
+{
+  tree tmp;
+  gcond *cond_stmt;
+  edge e_false;
+  basic_block new_bb, split_bb = gsi_bb (*gsip);
+
+  edge e_true = make_edge (split_bb, case_bb, EDGE_TRUE_VALUE);
+  gcc_assert (e_true->src == split_bb);
+
+  tmp = force_gimple_operand_gsi (gsip, cond, /*simple=*/true, NULL,
+				  /*before=*/true, GSI_SAME_STMT);
+  cond_stmt = gimple_build_cond_from_tree (tmp, NULL_TREE, NULL_TREE);
+  gsi_insert_before (gsip, cond_stmt, GSI_SAME_STMT);
+
+  e_false = split_block (split_bb, cond_stmt);
+  new_bb = e_false->dest;
+  redirect_edge_pred (e_true, split_bb);
+
+  e_false->flags &= ~EDGE_FALLTHRU;
+  e_false->flags |= EDGE_FALSE_VALUE;
+  e_false->probability = e_true->probability.invert ();
+  new_bb->count = e_false->count ();
+
+  return new_bb;
 }
 
 /* Compute the number of case labels that correspond to each outgoing edge of
-   STMT.  Record this information in the aux field of the edge.  */
+   switch statement.  Record this information in the aux field of the edge.  */
 
-static inline void
-compute_cases_per_edge (gswitch *stmt)
+void
+switch_decision_tree::compute_cases_per_edge ()
 {
-  basic_block bb = gimple_bb (stmt);
-  reset_out_edges_aux (bb);
-  int ncases = gimple_switch_num_labels (stmt);
+  basic_block bb = gimple_bb (m_switch);
+  reset_out_edges_aux ();
+  int ncases = gimple_switch_num_labels (m_switch);
   for (int i = ncases - 1; i >= 1; --i)
     {
-      tree elt = gimple_switch_label (stmt, i);
+      tree elt = gimple_switch_label (m_switch, i);
       tree lab = CASE_LABEL (elt);
       basic_block case_bb = label_to_block_fn (cfun, lab);
       edge case_edge = find_edge (bb, case_bb);
@@ -1143,61 +1450,242 @@ compute_cases_per_edge (gswitch *stmt)
     }
 }
 
-/* Do the insertion of a case label into case_list.  The labels are
-   fed to us in descending order from the sorted vector of case labels used
-   in the tree part of the middle end.  So the list we construct is
-   sorted in ascending order.
+/* Analyze switch statement and return true when the statement is expanded
+   as decision tree.  */
+
+bool
+switch_decision_tree::analyze_switch_statement ()
+{
+  unsigned l = gimple_switch_num_labels (m_switch);
+  basic_block bb = gimple_bb (m_switch);
+  auto_vec<cluster *> clusters;
+  clusters.create (l - 1);
+
+  tree default_label = CASE_LABEL (gimple_switch_default_label (m_switch));
+  basic_block default_bb = label_to_block_fn (cfun, default_label);
+  m_case_bbs.reserve (l);
+  m_case_bbs.quick_push (default_bb);
+
+  compute_cases_per_edge ();
+
+  for (unsigned i = 1; i < l; i++)
+    {
+      tree elt = gimple_switch_label (m_switch, i);
+      tree lab = CASE_LABEL (elt);
+      basic_block case_bb = label_to_block_fn (cfun, lab);
+      edge case_edge = find_edge (bb, case_bb);
+      tree low = CASE_LOW (elt);
+      tree high = CASE_HIGH (elt);
+
+      profile_probability p
+	= case_edge->probability.apply_scale (1, (intptr_t) (case_edge->aux));
+      clusters.quick_push (new simple_cluster (low, high, elt, case_bb, p));
+      m_case_bbs.quick_push (case_bb);
+    }
+
+  reset_out_edges_aux ();
+
+  vec<cluster *> output;
+  output.create (1);
+
+  /* Find whether the switch statement can be expanded with a method
+     different from decision tree.  */
+  unsigned end = clusters.length () - 1;
+  if (jump_table_cluster::can_be_handled (clusters, 0, end)
+      && jump_table_cluster::is_beneficial (clusters, 0, end))
+    output.safe_push (new jump_table_cluster (clusters, 0, end));
+  else if (bit_test_cluster::can_be_handled (clusters, 0, end)
+	   && bit_test_cluster::is_beneficial (clusters, 0, end))
+    output.safe_push (new bit_test_cluster (clusters, 0, end));
+  else
+    output = clusters;
+
+  if (dump_file)
+    {
+      fprintf (dump_file, ";; GIMPLE switch case clusters: ");
+      for (unsigned i = 0; i < output.length (); i++)
+	output[i]->dump (dump_file, dump_flags & TDF_DETAILS);
+      fprintf (dump_file, "\n");
+    }
 
-   LABEL is the case label to be inserted.  LOW and HIGH are the bounds
-   against which the index is compared to jump to LABEL and PROB is the
-   estimated probability LABEL is reached from the switch statement.  */
+  bool expanded = try_switch_expansion (output);
 
-static case_node *
-add_case_node (case_node *head, tree low, tree high, basic_block case_bb,
-	       tree case_label, profile_probability prob,
-	       object_allocator<case_node> &case_node_pool)
+  for (unsigned i = 0; i < output.length (); i++)
+    delete output[i];
+
+  return expanded;
+}
+
+/* Attempt to expand CLUSTERS as a decision tree.  Return true when
+   expanded.  */
+
+bool
+switch_decision_tree::try_switch_expansion (vec<cluster *> &clusters)
 {
-  case_node *r;
-
-  gcc_checking_assert (low);
-  gcc_checking_assert (high && (TREE_TYPE (low) == TREE_TYPE (high)));
-
-  /* Add this label to the chain.  */
-  r = case_node_pool.allocate ();
-  r->low = low;
-  r->high = high;
-  r->case_bb = case_bb;
-  r->case_label = case_label;
-  r->parent = r->left = NULL;
-  r->prob = prob;
-  r->subtree_prob = prob;
-  r->right = head;
-  return r;
+  tree index_expr = gimple_switch_index (m_switch);
+  tree index_type = TREE_TYPE (index_expr);
+  basic_block bb = gimple_bb (m_switch);
+
+  if (gimple_switch_num_labels (m_switch) == 1)
+    return false;
+
+  /* Find the default case target label.  */
+  tree default_label_expr = CASE_LABEL (gimple_switch_default_label (m_switch));
+  m_default_bb = label_to_block_fn (cfun, default_label_expr);
+  edge default_edge = find_edge (bb, m_default_bb);
+
+  /* Do the insertion of a case label into m_case_list.  The labels are
+     fed to us in descending order from the sorted vector of case labels used
+     in the tree part of the middle end.  So the list we construct is
+     sorted in ascending order.  */
+
+  for (int i = clusters.length () - 1; i >= 0; i--)
+    {
+      case_tree_node *r = m_case_list;
+      m_case_list = m_case_node_pool.allocate ();
+      m_case_list->m_right = r;
+      m_case_list->m_c = clusters[i];
+    }
+
+  record_phi_operand_mapping ();
+
+  /* Split basic block that contains the gswitch statement.  */
+  gimple_stmt_iterator gsi = gsi_last_bb (bb);
+  edge e;
+  if (gsi_end_p (gsi))
+    e = split_block_after_labels (bb);
+  else
+    {
+      gsi_prev (&gsi);
+      e = split_block (bb, gsi_stmt (gsi));
+    }
+  bb = split_edge (e);
+
+  /* Create new basic blocks for non-case clusters where specific expansion
+     needs to happen.  */
+  for (unsigned i = 0; i < clusters.length (); i++)
+    if (clusters[i]->get_type () != SIMPLE_CASE)
+      {
+	clusters[i]->m_case_bb = create_empty_bb (bb);
+	clusters[i]->m_case_bb->loop_father = bb->loop_father;
+      }
+
+  /* Do not do an extra work for a single cluster.  */
+  if (clusters.length () == 1
+      && clusters[0]->get_type () != SIMPLE_CASE)
+    clusters[0]->emit (index_expr, index_type,
+		       gimple_switch_default_label (m_switch), m_default_bb);
+  else
+    {
+      emit (bb, index_expr, default_edge->probability, index_type);
+
+      /* Emit cluster-specific switch handling.  */
+      for (unsigned i = 0; i < clusters.length (); i++)
+	if (clusters[i]->get_type () != SIMPLE_CASE)
+	  clusters[i]->emit (index_expr, index_type,
+			     gimple_switch_default_label (m_switch),
+			     m_default_bb);
+    }
+
+  fix_phi_operands_for_edges ();
+
+  return true;
 }
 
-/* Dump ROOT, a list or tree of case nodes, to file.  */
+/* Before switch transformation, record all SSA_NAMEs defined in switch BB
+   and used in a label basic block.  */
 
-static void
-dump_case_nodes (FILE *f, case_node *root, int indent_step, int indent_level)
+void
+switch_decision_tree::record_phi_operand_mapping ()
 {
-  if (root == 0)
-    return;
-  indent_level++;
+  basic_block switch_bb = gimple_bb (m_switch);
+  /* Record all PHI nodes that have to be fixed after conversion.  */
+  for (unsigned i = 0; i < m_case_bbs.length (); i++)
+    {
+      gphi_iterator gsi;
+      basic_block bb = m_case_bbs[i];
+      for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
+	{
+	  gphi *phi = gsi.phi ();
 
-  dump_case_nodes (f, root->left, indent_step, indent_level);
+	  for (unsigned i = 0; i < gimple_phi_num_args (phi); i++)
+	    {
+	      basic_block phi_src_bb = gimple_phi_arg_edge (phi, i)->src;
+	      if (phi_src_bb == switch_bb)
+		{
+		  tree def = gimple_phi_arg_def (phi, i);
+		  tree result = gimple_phi_result (phi);
+		  m_phi_mapping.put (result, def);
+		  break;
+		}
+	    }
+	}
+    }
+}
 
-  fputs (";; ", f);
-  fprintf (f, "%*s", indent_step * indent_level, "");
-  print_dec (wi::to_wide (root->low), f, TYPE_SIGN (TREE_TYPE (root->low)));
-  if (!tree_int_cst_equal (root->low, root->high))
+/* Append new operands to PHI statements that were introduced due to
+   addition of new edges to case labels.  */
+
+void
+switch_decision_tree::fix_phi_operands_for_edges ()
+{
+  gphi_iterator gsi;
+
+  for (unsigned i = 0; i < m_case_bbs.length (); i++)
     {
-      fprintf (f, " ... ");
-      print_dec (wi::to_wide (root->high), f,
-		 TYPE_SIGN (TREE_TYPE (root->high)));
+      basic_block bb = m_case_bbs[i];
+      for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
+	{
+	  gphi *phi = gsi.phi ();
+	  for (unsigned j = 0; j < gimple_phi_num_args (phi); j++)
+	    {
+	      tree def = gimple_phi_arg_def (phi, j);
+	      if (def == NULL_TREE)
+		{
+		  edge e = gimple_phi_arg_edge (phi, j);
+		  tree *definition
+		    = m_phi_mapping.get (gimple_phi_result (phi));
+		  gcc_assert (definition);
+		  add_phi_arg (phi, *definition, e, UNKNOWN_LOCATION);
+		}
+	    }
+	}
+    }
+}
+
+/* Generate a decision tree, switching on INDEX_EXPR and jumping to
+   one of the labels in CASE_LIST or to the DEFAULT_LABEL.
+
+   We generate a binary decision tree to select the appropriate target
+   code.  */
+
+void
+switch_decision_tree::emit (basic_block bb, tree index_expr,
+			    profile_probability default_prob, tree index_type)
+{
+  balance_case_nodes (&m_case_list, NULL);
+
+  if (dump_file)
+    dump_function_to_file (current_function_decl, dump_file, dump_flags);
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    {
+      int indent_step = ceil_log2 (TYPE_PRECISION (index_type)) + 2;
+      fprintf (dump_file, ";; Expanding GIMPLE switch as decision tree:\n");
+      gcc_assert (m_case_list != NULL);
+      dump_case_nodes (dump_file, m_case_list, indent_step, 0);
     }
-  fputs ("\n", f);
 
-  dump_case_nodes (f, root->right, indent_step, indent_level);
+  bb = emit_case_nodes (bb, index_expr, m_case_list, default_prob, index_type);
+
+  if (bb)
+    emit_jump (bb, m_default_bb);
+
+  /* Remove all edges and do just an edge that will reach default_bb.  */
+  bb = gimple_bb (m_switch);
+  gimple_stmt_iterator gsi = gsi_last_bb (bb);
+  gsi_remove (&gsi, true);
+
+  delete_basic_block (bb);
 }
 
 /* Take an ordered list of case nodes
@@ -1210,28 +1698,29 @@ dump_case_nodes (FILE *f, case_node *root, int indent_step, int indent_level)
    then attached to the pivot as left and right branches.  Each
    branch is then transformed recursively.  */
 
-static void
-balance_case_nodes (case_node_ptr *head, case_node_ptr parent)
+void
+switch_decision_tree::balance_case_nodes (case_tree_node **head,
+					  case_tree_node *parent)
 {
-  case_node_ptr np;
+  case_tree_node *np;
 
   np = *head;
   if (np)
     {
       int i = 0;
       int ranges = 0;
-      case_node_ptr *npp;
-      case_node_ptr left;
+      case_tree_node **npp;
+      case_tree_node *left;
 
       /* Count the number of entries on branch.  Also count the ranges.  */
 
       while (np)
 	{
-	  if (!tree_int_cst_equal (np->low, np->high))
+	  if (!tree_int_cst_equal (np->m_c->get_low (), np->m_c->get_high ()))
 	    ranges++;
 
 	  i++;
-	  np = np->right;
+	  np = np->m_right;
 	}
 
       if (i > 2)
@@ -1242,7 +1731,7 @@ balance_case_nodes (case_node_ptr *head, case_node_ptr parent)
 
 	  /* If there are just three nodes, split at the middle one.  */
 	  if (i == 3)
-	    npp = &(*npp)->right;
+	    npp = &(*npp)->m_right;
 	  else
 	    {
 	      /* Find the place in the list that bisects the list's total cost,
@@ -1252,320 +1741,247 @@ balance_case_nodes (case_node_ptr *head, case_node_ptr parent)
 	      while (1)
 		{
 		  /* Skip nodes while their cost does not reach that amount.  */
-		  if (!tree_int_cst_equal ((*npp)->low, (*npp)->high))
+		  if (!tree_int_cst_equal ((*npp)->m_c->get_low (),
+					   (*npp)->m_c->get_high ()))
 		    i--;
 		  i--;
 		  if (i <= 0)
 		    break;
-		  npp = &(*npp)->right;
+		  npp = &(*npp)->m_right;
 		}
 	    }
 	  *head = np = *npp;
 	  *npp = 0;
-	  np->parent = parent;
-	  np->left = left;
+	  np->m_parent = parent;
+	  np->m_left = left;
 
 	  /* Optimize each of the two split parts.  */
-	  balance_case_nodes (&np->left, np);
-	  balance_case_nodes (&np->right, np);
-	  np->subtree_prob = np->prob;
-	  np->subtree_prob += np->left->subtree_prob;
-	  np->subtree_prob += np->right->subtree_prob;
+	  balance_case_nodes (&np->m_left, np);
+	  balance_case_nodes (&np->m_right, np);
+	  np->m_c->m_subtree_prob = np->m_c->m_prob;
+	  np->m_c->m_subtree_prob += np->m_left->m_c->m_subtree_prob;
+	  np->m_c->m_subtree_prob += np->m_right->m_c->m_subtree_prob;
 	}
       else
 	{
 	  /* Else leave this branch as one level,
 	     but fill in `parent' fields.  */
 	  np = *head;
-	  np->parent = parent;
-	  np->subtree_prob = np->prob;
-	  for (; np->right; np = np->right)
+	  np->m_parent = parent;
+	  np->m_c->m_subtree_prob = np->m_c->m_prob;
+	  for (; np->m_right; np = np->m_right)
 	    {
-	      np->right->parent = np;
-	      (*head)->subtree_prob += np->right->subtree_prob;
+	      np->m_right->m_parent = np;
+	      (*head)->m_c->m_subtree_prob += np->m_right->m_c->m_subtree_prob;
 	    }
 	}
     }
 }
 
-/* Return true if a switch should be expanded as a decision tree.
-   RANGE is the difference between highest and lowest case.
-   UNIQ is number of unique case node targets, not counting the default case.
-   COUNT is the number of comparisons needed, not counting the default case.  */
+/* Dump ROOT, a list or tree of case nodes, to file.  */
 
-static bool
-expand_switch_as_decision_tree_p (tree range,
-				  unsigned int uniq ATTRIBUTE_UNUSED,
-				  unsigned int count)
+void
+switch_decision_tree::dump_case_nodes (FILE *f, case_tree_node *root,
+				       int indent_step, int indent_level)
 {
-  int max_ratio;
-
-  /* If neither casesi or tablejump is available, or flag_jump_tables
-     over-ruled us, we really have no choice.  */
-  if (!targetm.have_casesi () && !targetm.have_tablejump ())
-    return true;
-  if (!flag_jump_tables)
-    return true;
-#ifndef ASM_OUTPUT_ADDR_DIFF_ELT
-  if (flag_pic)
-    return true;
-#endif
-
-  /* If the switch is relatively small such that the cost of one
-     indirect jump on the target are higher than the cost of a
-     decision tree, go with the decision tree.
-
-     If range of values is much bigger than number of values,
-     or if it is too large to represent in a HOST_WIDE_INT,
-     make a sequence of conditional branches instead of a dispatch.
-
-     The definition of "much bigger" depends on whether we are
-     optimizing for size or for speed.  If the former, the maximum
-     ratio range/count = 3, because this was found to be the optimal
-     ratio for size on i686-pc-linux-gnu, see PR11823.  The ratio
-     10 is much older, and was probably selected after an extensive
-     benchmarking investigation on numerous platforms.  Or maybe it
-     just made sense to someone at some point in the history of GCC,
-     who knows...  */
-  max_ratio = optimize_insn_for_size_p () ? 3 : 10;
-  if (count < case_values_threshold () || !tree_fits_uhwi_p (range)
-      || compare_tree_int (range, max_ratio * count) > 0)
-    return true;
+  if (root == 0)
+    return;
+  indent_level++;
 
-  return false;
-}
+  dump_case_nodes (f, root->m_left, indent_step, indent_level);
 
-static void
-fix_phi_operands_for_edge (edge e, hash_map<tree, tree> *phi_mapping)
-{
-  basic_block bb = e->dest;
-  gphi_iterator gsi;
-  for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
-    {
-      gphi *phi = gsi.phi ();
+  fputs (";; ", f);
+  fprintf (f, "%*s", indent_step * indent_level, "");
+  root->m_c->dump (f);
+  root->m_c->m_prob.dump (f);
+  fputs ("\n", f);
 
-      tree *definition = phi_mapping->get (gimple_phi_result (phi));
-      if (definition)
-	add_phi_arg (phi, *definition, e, UNKNOWN_LOCATION);
-    }
+  dump_case_nodes (f, root->m_right, indent_step, indent_level);
 }
 
 
 /* Add an unconditional jump to CASE_BB that happens in basic block BB.  */
 
-static void
-emit_jump (basic_block bb, basic_block case_bb,
-	   hash_map<tree, tree> *phi_mapping)
+void
+switch_decision_tree::emit_jump (basic_block bb, basic_block case_bb)
 {
   edge e = single_succ_edge (bb);
   redirect_edge_succ (e, case_bb);
-  fix_phi_operands_for_edge (e, phi_mapping);
 }
 
-/* Generate a decision tree, switching on INDEX_EXPR and jumping to
-   one of the labels in CASE_LIST or to the DEFAULT_LABEL.
-   DEFAULT_PROB is the estimated probability that it jumps to
-   DEFAULT_LABEL.
-
-   We generate a binary decision tree to select the appropriate target
-   code.  */
+/* Generate code to compare OP0 with OP1 so that the condition codes are
+   set and to jump to LABEL_BB if the condition is true.
+   COMPARISON is the GIMPLE comparison (EQ, NE, GT, etc.).
+   PROB is the probability of jumping to LABEL_BB.  */
 
-static void
-emit_case_decision_tree (gswitch *s, tree index_expr, tree index_type,
-			 case_node_ptr case_list, basic_block default_bb,
-			 tree default_label, profile_probability default_prob,
-			 hash_map<tree, tree> *phi_mapping)
+basic_block
+switch_decision_tree::emit_cmp_and_jump_insns (basic_block bb, tree op0,
+					       tree op1, tree_code comparison,
+					       basic_block label_bb,
+					       profile_probability prob)
 {
-  balance_case_nodes (&case_list, NULL);
-
-  if (dump_file)
-    dump_function_to_file (current_function_decl, dump_file, dump_flags);
-  if (dump_file && (dump_flags & TDF_DETAILS))
-    {
-      int indent_step = ceil_log2 (TYPE_PRECISION (index_type)) + 2;
-      fprintf (dump_file, ";; Expanding GIMPLE switch as decision tree:\n");
-      dump_case_nodes (dump_file, case_list, indent_step, 0);
-    }
+  // TODO: it's once called with lhs != index.
+  op1 = fold_convert (TREE_TYPE (op0), op1);
 
-  basic_block bb = gimple_bb (s);
+  gcond *cond = gimple_build_cond (comparison, op0, op1, NULL_TREE, NULL_TREE);
   gimple_stmt_iterator gsi = gsi_last_bb (bb);
-  edge e;
-  if (gsi_end_p (gsi))
-    e = split_block_after_labels (bb);
-  else
-    {
-      gsi_prev (&gsi);
-      e = split_block (bb, gsi_stmt (gsi));
-    }
-  bb = split_edge (e);
+  gsi_insert_after (&gsi, cond, GSI_NEW_STMT);
 
-  bb = emit_case_nodes (bb, index_expr, case_list, default_bb, default_label,
-			default_prob, index_type, phi_mapping);
+  gcc_assert (single_succ_p (bb));
 
-  if (bb)
-    emit_jump (bb, default_bb, phi_mapping);
+  /* 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 ();
 
-  /* Remove all edges and do just an edge that will reach default_bb.  */
-  gsi = gsi_last_bb (gimple_bb (s));
-  gsi_remove (&gsi, true);
+  edge true_edge = make_edge (bb, label_bb, EDGE_TRUE_VALUE);
+  true_edge->probability = prob;
+
+  return false_edge->dest;
 }
 
-static void
-record_phi_operand_mapping (const vec<basic_block> bbs, basic_block switch_bb,
-			    hash_map <tree, tree> *map)
+/* 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.
+   DEFAULT_PROB is probability of cases leading to default BB.
+   INDEX_TYPE is the type of the index of the switch.  */
+
+basic_block
+switch_decision_tree::emit_case_nodes (basic_block bb, tree index,
+				       case_tree_node *node,
+				       profile_probability default_prob,
+				       tree index_type)
 {
-  /* Record all PHI nodes that have to be fixed after conversion.  */
-  for (unsigned i = 0; i < bbs.length (); i++)
-    {
-      basic_block bb = bbs[i];
+  /* If node is null, we are done.  */
+  if (node == NULL)
+    return bb;
 
-      gphi_iterator gsi;
-      for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
-	{
-	  gphi *phi = gsi.phi ();
+  /* 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);
 
-	  for (unsigned i = 0; i < gimple_phi_num_args (phi); i++)
-	    {
-	      basic_block phi_src_bb = gimple_phi_arg_edge (phi, i)->src;
-	      if (phi_src_bb == switch_bb)
-		{
-		  tree def = gimple_phi_arg_def (phi, i);
-		  tree result = gimple_phi_result (phi);
-		  map->put (result, def);
-		  break;
-		}
-	    }
-	}
-    }
-}
+  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);
 
-/* Attempt to expand gimple switch STMT to a decision tree.  */
+  /* 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);
 
-static bool
-try_switch_expansion (gswitch *stmt)
-{
-  tree minval = NULL_TREE, maxval = NULL_TREE, range = NULL_TREE;
-  basic_block default_bb;
-  unsigned int count, uniq;
-  int i;
-  int ncases = gimple_switch_num_labels (stmt);
-  tree index_expr = gimple_switch_index (stmt);
-  tree index_type = TREE_TYPE (index_expr);
-  tree elt;
-  basic_block bb = gimple_bb (stmt);
+  /* Handle the left-hand subtree.  */
+  bb = emit_case_nodes (bb, index, node->m_left,
+			default_prob, index_type);
 
-  hash_map<tree, tree> phi_mapping;
-  auto_vec<basic_block> case_bbs;
+  /* 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);
 
-  /* A list of case labels; it is first built as a list and it may then
-     be rearranged into a nearly balanced binary tree.  */
-  case_node *case_list = 0;
+  bb = emit_case_nodes (test_bb, index, node->m_right,
+			default_prob, index_type);
 
-  /* A pool for case nodes.  */
-  object_allocator<case_node> case_node_pool ("struct case_node pool");
+  return bb;
+}
 
-  /* cleanup_tree_cfg removes all SWITCH_EXPR with their index
-     expressions being INTEGER_CST.  */
-  gcc_assert (TREE_CODE (index_expr) != INTEGER_CST);
+/* The main function of the pass scans statements for switches and invokes
+   process_switch on them.  */
 
-  if (ncases == 1)
-    return false;
+namespace {
 
-  /* Find the default case target label.  */
-  tree default_label = CASE_LABEL (gimple_switch_default_label (stmt));
-  default_bb = label_to_block_fn (cfun, default_label);
-  edge default_edge = find_edge (bb, default_bb);
-  profile_probability default_prob = default_edge->probability;
-  case_bbs.safe_push (default_bb);
-
-  /* Get upper and lower bounds of case values.  */
-  elt = gimple_switch_label (stmt, 1);
-  minval = fold_convert (index_type, CASE_LOW (elt));
-  elt = gimple_switch_label (stmt, ncases - 1);
-  if (CASE_HIGH (elt))
-    maxval = fold_convert (index_type, CASE_HIGH (elt));
-  else
-    maxval = fold_convert (index_type, CASE_LOW (elt));
+const pass_data pass_data_convert_switch =
+{
+  GIMPLE_PASS, /* type */
+  "switchconv", /* name */
+  OPTGROUP_NONE, /* optinfo_flags */
+  TV_TREE_SWITCH_CONVERSION, /* tv_id */
+  ( PROP_cfg | PROP_ssa ), /* properties_required */
+  0, /* properties_provided */
+  0, /* properties_destroyed */
+  0, /* todo_flags_start */
+  TODO_update_ssa, /* todo_flags_finish */
+};
 
-  /* Compute span of values.  */
-  range = fold_build2 (MINUS_EXPR, index_type, maxval, minval);
+class pass_convert_switch : public gimple_opt_pass
+{
+public:
+  pass_convert_switch (gcc::context *ctxt)
+    : gimple_opt_pass (pass_data_convert_switch, ctxt)
+  {}
 
-  /* Listify the labels queue and gather some numbers to decide
-     how to expand this switch.  */
-  uniq = 0;
-  count = 0;
-  hash_set<tree> seen_labels;
-  compute_cases_per_edge (stmt);
+  /* opt_pass methods: */
+  virtual bool gate (function *) { return flag_tree_switch_conversion != 0; }
+  virtual unsigned int execute (function *);
 
-  for (i = ncases - 1; i >= 1; --i)
-    {
-      elt = gimple_switch_label (stmt, i);
-      tree low = CASE_LOW (elt);
-      gcc_assert (low);
-      tree high = CASE_HIGH (elt);
-      gcc_assert (!high || tree_int_cst_lt (low, high));
-      tree lab = CASE_LABEL (elt);
+}; // class pass_convert_switch
 
-      /* Count the elements.
-	 A range counts double, since it requires two compares.  */
-      count++;
-      if (high)
-	count++;
-
-      /* If we have not seen this label yet, then increase the
-	 number of unique case node targets seen.  */
-      if (!seen_labels.add (lab))
-	uniq++;
-
-      /* The bounds on the case range, LOW and HIGH, have to be converted
-	 to case's index type TYPE.  Note that the original type of the
-	 case index in the source code is usually "lost" during
-	 gimplification due to type promotion, but the case labels retain the
-	 original type.  Make sure to drop overflow flags.  */
-      low = fold_convert (index_type, low);
-      if (TREE_OVERFLOW (low))
-	low = wide_int_to_tree (index_type, wi::to_wide (low));
-
-      /* The canonical from of a case label in GIMPLE is that a simple case
-	 has an empty CASE_HIGH.  For the casesi and tablejump expanders,
-	 the back ends want simple cases to have high == low.  */
-      if (!high)
-	high = low;
-      high = fold_convert (index_type, high);
-      if (TREE_OVERFLOW (high))
-	high = wide_int_to_tree (index_type, wi::to_wide (high));
+unsigned int
+pass_convert_switch::execute (function *fun)
+{
+  basic_block bb;
+  bool cfg_altered = false;
 
-      basic_block case_bb = label_to_block_fn (cfun, lab);
-      edge case_edge = find_edge (bb, case_bb);
-      case_list = add_case_node (
-	case_list, low, high, case_bb, lab,
-	case_edge->probability.apply_scale (1, (intptr_t) (case_edge->aux)),
-	case_node_pool);
+  FOR_EACH_BB_FN (bb, fun)
+  {
+    gimple *stmt = last_stmt (bb);
+    if (stmt && gimple_code (stmt) == GIMPLE_SWITCH)
+      {
+	if (dump_file)
+	  {
+	    expanded_location loc = expand_location (gimple_location (stmt));
 
-      case_bbs.safe_push (case_bb);
-    }
-  reset_out_edges_aux (bb);
-  record_phi_operand_mapping (case_bbs, bb, &phi_mapping);
+	    fprintf (dump_file, "beginning to process the following "
+		     "SWITCH statement (%s:%d) : ------- \n",
+		     loc.file, loc.line);
+	    print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
+	    putc ('\n', dump_file);
+	  }
 
-  /* cleanup_tree_cfg removes all SWITCH_EXPR with a single
-     destination, such as one with a default case only.
-     It also removes cases that are out of range for the switch
-     type, so we should never get a zero here.  */
-  gcc_assert (count > 0);
+	switch_conversion sconv;
+	sconv.expand (as_a <gswitch *> (stmt));
+	cfg_altered |= sconv.m_cfg_altered;
+	if (!sconv.m_reason)
+	  {
+	    if (dump_file)
+	      {
+		fputs ("Switch converted\n", dump_file);
+		fputs ("--------------------------------\n", dump_file);
+	      }
 
-  /* Decide how to expand this switch.
-     The two options at this point are a dispatch table (casesi or
-     tablejump) or a decision tree.  */
+	    /* Make no effort to update the post-dominator tree.
+	       It is actually not that hard for the transformations
+	       we have performed, but it is not supported
+	       by iterate_fix_dominators.  */
+	    free_dominance_info (CDI_POST_DOMINATORS);
+	  }
+	else
+	  {
+	    if (dump_file)
+	      {
+		fputs ("Bailing out - ", dump_file);
+		fputs (sconv.m_reason, dump_file);
+		fputs ("\n--------------------------------\n", dump_file);
+	      }
+	  }
+      }
+  }
 
-  if (expand_switch_as_decision_tree_p (range, uniq, count))
-    {
-      emit_case_decision_tree (stmt, index_expr, index_type, case_list,
-			       default_bb, default_label, default_prob,
-			       &phi_mapping);
-      return true;
-    }
+  return cfg_altered ? TODO_cleanup_cfg : 0;;
+}
 
-  return false;
+} // anon namespace
+
+gimple_opt_pass *
+make_pass_convert_switch (gcc::context *ctxt)
+{
+  return new pass_convert_switch (ctxt);
 }
 
 /* The main function of the pass scans statements for switches and invokes
@@ -1614,23 +2030,35 @@ pass_lower_switch<O0>::execute (function *fun)
   basic_block bb;
   bool expanded = false;
 
+  auto_vec<gimple *> switch_statements;
+  switch_statements.create (1);
+
   FOR_EACH_BB_FN (bb, fun)
     {
       gimple *stmt = last_stmt (bb);
       if (stmt && gimple_code (stmt) == GIMPLE_SWITCH)
+	switch_statements.safe_push (stmt);
+    }
+
+  for (unsigned i = 0; i < switch_statements.length (); i++)
+    {
+      gimple *stmt = switch_statements[i];
+      if (dump_file)
 	{
-	  if (dump_file)
-	    {
-	      expanded_location loc = expand_location (gimple_location (stmt));
+	  expanded_location loc = expand_location (gimple_location (stmt));
 
-	      fprintf (dump_file, "beginning to process the following "
-				  "SWITCH statement (%s:%d) : ------- \n",
-		       loc.file, loc.line);
-	      print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
-	      putc ('\n', dump_file);
-	    }
+	  fprintf (dump_file, "beginning to process the following "
+		   "SWITCH statement (%s:%d) : ------- \n",
+		   loc.file, loc.line);
+	  print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
+	  putc ('\n', dump_file);
+	}
 
-	  expanded |= try_switch_expansion (as_a<gswitch *> (stmt));
+      gswitch *swtch = dyn_cast<gswitch *> (stmt);
+      if (swtch)
+	{
+	  switch_decision_tree dt (swtch);
+	  expanded |= dt.analyze_switch_statement ();
 	}
     }
 
@@ -1657,112 +2085,4 @@ make_pass_lower_switch (gcc::context *ctxt)
   return new pass_lower_switch<false> (ctxt);
 }
 
-/* Generate code to compare X with Y so that the condition codes are
-   set and to jump to LABEL if the condition is true.  If X is a
-   constant and Y is not a constant, then the comparison is swapped to
-   ensure that the comparison RTL has the canonical form.
-
-   UNSIGNEDP nonzero says that X and Y are unsigned; this matters if they
-   need to be widened.  UNSIGNEDP is also used to select the proper
-   branch condition code.
-
-   If X and Y have mode BLKmode, then SIZE specifies the size of both X and Y.
-
-   MODE is the mode of the inputs (in case they are const_int).
-
-   COMPARISON is the rtl operator to compare with (EQ, NE, GT, etc.).
-   It will be potentially converted into an unsigned variant based on
-   UNSIGNEDP to select a proper jump instruction.
-
-   PROB is the probability of jumping to LABEL.  */
-
-static basic_block
-emit_cmp_and_jump_insns (basic_block bb, tree op0, tree op1,
-			 tree_code comparison, basic_block label_bb,
-			 profile_probability prob,
-			 hash_map<tree, tree> *phi_mapping)
-{
-  gcond *cond = gimple_build_cond (comparison, op0, op1, NULL_TREE, NULL_TREE);
-  gimple_stmt_iterator gsi = gsi_last_bb (bb);
-  gsi_insert_after (&gsi, cond, GSI_NEW_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);
-  fix_phi_operands_for_edge (true_edge, phi_mapping);
-  true_edge->probability = prob;
-
-  return false_edge->dest;
-}
-
-/* Computes the conditional probability of jumping to a target if the branch
-   instruction is executed.
-   TARGET_PROB is the estimated probability of jumping to a target relative
-   to some basic block BB.
-   BASE_PROB is the probability of reaching the branch instruction relative
-   to the same basic block BB.  */
-
-static inline profile_probability
-conditional_probability (profile_probability target_prob,
-			 profile_probability base_prob)
-{
-  return target_prob / base_prob;
-}
-
-/* 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.
-   INDEX_TYPE is the type of the index of the switch.  */
-
-static basic_block
-emit_case_nodes (basic_block bb, tree index, case_node_ptr node,
-		 basic_block default_bb, tree default_label,
-		 profile_probability default_prob, tree index_type,
-		 hash_map<tree, tree> *phi_mapping)
-{
-  /* 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->right ? node->right->subtree_prob : profile_probability::never ();
-  probability
-    = conditional_probability (probability + default_prob.apply_scale (1, 2),
-			       node->subtree_prob + default_prob);
-  bb = emit_cmp_and_jump_insns (bb, index, node->high, GT_EXPR,
-				test_bb, probability, phi_mapping);
-  default_prob = default_prob.apply_scale (1, 2);
-
-  /* Value belongs to this node or to the left-hand subtree.  */
-  probability
-    = conditional_probability (node->prob, node->subtree_prob + default_prob);
-  bb = emit_cmp_and_jump_insns (bb, index, node->low, GE_EXPR,
-				node->case_bb, probability,
-				phi_mapping);
-
-  /* Handle the left-hand subtree.  */
-  bb = emit_case_nodes (bb, index, node->left, default_bb,
-			default_label, default_prob, index_type,
-			phi_mapping);
-
-  /* If the left-hand subtree fell through,
-     don't let it fall into the right-hand subtree.  */
-  if (default_bb)
-    emit_jump (bb, default_bb, phi_mapping);
-
-  bb = emit_case_nodes (test_bb, index, node->right, default_bb,
-			default_label, default_prob, index_type,
-			phi_mapping);
-
-  return bb;
-}