This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: [PATCH][RFC] Make expansion of balanced binary trees of switches on tree level.


On 08/14/2017 10:32 AM, Richard Biener wrote:
> Hmm, but the existing "lowering" part is called from the
> switch-conversion pass.  So
> I'm not sure a new file is good.

Good, I'm not against having that in a single file. So new version of the patch
does that.

Patch can bootstrap on ppc64le-redhat-linux and survives regression tests.

Ready to be installed?
Martin
>From 27f5901b340e73900ef992470aa52b51ccfb86b9 Mon Sep 17 00:00:00 2001
From: marxin <mliska@suse.cz>
Date: Mon, 31 Jul 2017 14:01:53 +0200
Subject: [PATCH] Make expansion of balanced binary trees of switches on tree
 level.

gcc/ChangeLog:

2017-07-31  Martin Liska  <mliska@suse.cz>

	* passes.def: Include pass_lower_switch.
	* stmt.c (dump_case_nodes): Remove and move to
	tree-switch-conversion.
	(case_values_threshold): Likewise.
	(expand_switch_as_decision_tree_p): Likewise.
	(emit_case_decision_tree): Likewise.
	(expand_case): Likewise.
	(balance_case_nodes): Likewise.
	(node_has_low_bound): Likewise.
	(node_has_high_bound): Likewise.
	(node_is_bounded): Likewise.
	(emit_case_nodes): Likewise.
	* timevar.def: Add TV_TREE_SWITCH_LOWERING.
	* tree-pass.h: Add make_pass_lower_switch.

gcc/testsuite/ChangeLog:

2017-07-31  Martin Liska  <mliska@suse.cz>

	* gcc.dg/tree-prof/update-loopch.c: Scan patterns in
	switchlower.
	* gcc.dg/tree-ssa/vrp104.c: Likewise.
---
 gcc/passes.def                                 |    1 +
 gcc/stmt.c                                     |  861 -----------------
 gcc/testsuite/gcc.dg/tree-prof/update-loopch.c |   10 +-
 gcc/testsuite/gcc.dg/tree-ssa/vrp104.c         |    2 +-
 gcc/timevar.def                                |    1 +
 gcc/tree-pass.h                                |    1 +
 gcc/tree-switch-conversion.c                   | 1178 ++++++++++++++++++++++++
 7 files changed, 1187 insertions(+), 867 deletions(-)

diff --git a/gcc/passes.def b/gcc/passes.def
index 316e19d12e3..81b6e62f602 100644
--- a/gcc/passes.def
+++ b/gcc/passes.def
@@ -394,6 +394,7 @@ along with GCC; see the file COPYING3.  If not see
   NEXT_PASS (pass_lower_vaarg);
   NEXT_PASS (pass_lower_vector);
   NEXT_PASS (pass_lower_complex_O0);
+  NEXT_PASS (pass_lower_switch);
   NEXT_PASS (pass_sancov_O0);
   NEXT_PASS (pass_asan_O0);
   NEXT_PASS (pass_tsan_O0);
diff --git a/gcc/stmt.c b/gcc/stmt.c
index 05e24f00707..4c10b1f37d7 100644
--- a/gcc/stmt.c
+++ b/gcc/stmt.c
@@ -104,12 +104,6 @@ extern basic_block label_to_block_fn (struct function *, tree);
 
 static bool check_unique_operand_names (tree, tree, tree);
 static char *resolve_operand_name_1 (char *, tree, tree, tree);
-static void balance_case_nodes (case_node_ptr *, case_node_ptr);
-static int node_has_low_bound (case_node_ptr, tree);
-static int node_has_high_bound (case_node_ptr, tree);
-static int node_is_bounded (case_node_ptr, tree);
-static void emit_case_nodes (rtx, case_node_ptr, rtx_code_label *,
-			     profile_probability, tree);
 
 /* Return the rtx-label that corresponds to a LABEL_DECL,
    creating it if necessary.  */
@@ -742,164 +736,6 @@ add_case_node (struct case_node *head, tree low, tree high,
   return r;
 }
 
-/* Dump ROOT, a list or tree of case nodes, to file.  */
-
-static void
-dump_case_nodes (FILE *f, struct case_node *root,
-		 int indent_step, int indent_level)
-{
-  if (root == 0)
-    return;
-  indent_level++;
-
-  dump_case_nodes (f, root->left, indent_step, indent_level);
-
-  fputs (";; ", f);
-  fprintf (f, "%*s", indent_step * indent_level, "");
-  print_dec (root->low, f, TYPE_SIGN (TREE_TYPE (root->low)));
-  if (!tree_int_cst_equal (root->low, root->high))
-    {
-      fprintf (f, " ... ");
-      print_dec (root->high, f, TYPE_SIGN (TREE_TYPE (root->high)));
-    }
-  fputs ("\n", f);
-
-  dump_case_nodes (f, root->right, indent_step, indent_level);
-}
-
-/* Return the smallest number of different values for which it is best to use a
-   jump-table instead of a tree of conditional branches.  */
-
-static unsigned int
-case_values_threshold (void)
-{
-  unsigned int threshold = PARAM_VALUE (PARAM_CASE_VALUES_THRESHOLD);
-
-  if (threshold == 0)
-    threshold = targetm.case_values_threshold ();
-
-  return threshold;
-}
-
-/* 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.  */
-
-static bool
-expand_switch_as_decision_tree_p (tree range,
-				  unsigned int uniq ATTRIBUTE_UNUSED,
-				  unsigned int count)
-{
-  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;
-
-  return false;
-}
-
-/* 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.  This is done as follows:
-
-     If the index is a short or char that we do not have
-     an insn to handle comparisons directly, convert it to
-     a full integer now, rather than letting each comparison
-     generate the conversion.
-
-     Load the index into a register.
-
-     The list of cases is rearranged into a binary tree,
-     nearly optimal assuming equal probability for each case.
-
-     The tree is transformed into RTL, eliminating redundant
-     test conditions at the same time.
-
-     If program flow could reach the end of the decision tree
-     an unconditional jump to the default code is emitted.
-
-   The above process is unaware of the CFG.  The caller has to fix up
-   the CFG itself.  This is done in cfgexpand.c.  */     
-
-static void
-emit_case_decision_tree (tree index_expr, tree index_type,
-			 case_node_ptr case_list, rtx_code_label *default_label,
-			 profile_probability default_prob)
-{
-  rtx index = expand_normal (index_expr);
-
-  if (GET_MODE_CLASS (GET_MODE (index)) == MODE_INT
-      && ! have_insn_for (COMPARE, GET_MODE (index)))
-    {
-      int unsignedp = TYPE_UNSIGNED (index_type);
-      machine_mode wider_mode;
-      for (wider_mode = GET_MODE (index); wider_mode != VOIDmode;
-	   wider_mode = GET_MODE_WIDER_MODE (wider_mode))
-	if (have_insn_for (COMPARE, wider_mode))
-	  {
-	    index = convert_to_mode (wider_mode, index, unsignedp);
-	    break;
-	  }
-    }
-
-  do_pending_stack_adjust ();
-
-  if (MEM_P (index))
-    {
-      index = copy_to_reg (index);
-      if (TREE_CODE (index_expr) == SSA_NAME)
-	set_reg_attrs_for_decl_rtl (index_expr, index);
-    }
-
-  balance_case_nodes (&case_list, NULL);
-
-  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);
-    }
-
-  emit_case_nodes (index, case_list, default_label, default_prob, index_type);
-  if (default_label)
-    emit_jump (default_label);
-}
-
 /* Return the sum of probabilities of outgoing edges of basic block BB.  */
 
 static profile_probability
@@ -1150,7 +986,6 @@ expand_case (gswitch *stmt)
   default_label = jump_target_rtx
       (CASE_LABEL (gimple_switch_default_label (stmt)));
   edge default_edge = EDGE_SUCC (bb, 0);
-  profile_probability default_prob = default_edge->probability;
 
   /* Get upper and lower bounds of case values.  */
   elt = gimple_switch_label (stmt, 1);
@@ -1230,11 +1065,6 @@ expand_case (gswitch *stmt)
      The two options at this point are a dispatch table (casesi or
      tablejump) or a decision tree.  */
 
-  if (expand_switch_as_decision_tree_p (range, uniq, count))
-    emit_case_decision_tree (index_expr, index_type,
-                             case_list, default_label,
-                             default_prob);
-  else
     {
       /* If the default case is unreachable, then set default_label to NULL
 	 so that we omit the range check when generating the dispatch table.
@@ -1355,694 +1185,3 @@ expand_sjlj_dispatch_table (rtx dispatch_index,
 }
 
 
-/* Take an ordered list of case nodes
-   and transform them into a near optimal binary tree,
-   on the assumption that any target code selection value is as
-   likely as any other.
-
-   The transformation is performed by splitting the ordered
-   list into two equal sections plus a pivot.  The parts are
-   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)
-{
-  case_node_ptr np;
-
-  np = *head;
-  if (np)
-    {
-      int i = 0;
-      int ranges = 0;
-      case_node_ptr *npp;
-      case_node_ptr left;
-
-      /* Count the number of entries on branch.  Also count the ranges.  */
-
-      while (np)
-	{
-	  if (!tree_int_cst_equal (np->low, np->high))
-	    ranges++;
-
-	  i++;
-	  np = np->right;
-	}
-
-      if (i > 2)
-	{
-	  /* Split this list if it is long enough for that to help.  */
-	  npp = head;
-	  left = *npp;
-
-	  /* If there are just three nodes, split at the middle one.  */
-	  if (i == 3)
-	    npp = &(*npp)->right;
-	  else
-	    {
-	      /* Find the place in the list that bisects the list's total cost,
-		 where ranges count as 2.
-		 Here I gets half the total cost.  */
-	      i = (i + ranges + 1) / 2;
-	      while (1)
-		{
-		  /* Skip nodes while their cost does not reach that amount.  */
-		  if (!tree_int_cst_equal ((*npp)->low, (*npp)->high))
-		    i--;
-		  i--;
-		  if (i <= 0)
-		    break;
-		  npp = &(*npp)->right;
-		}
-	    }
-	  *head = np = *npp;
-	  *npp = 0;
-	  np->parent = parent;
-	  np->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;
-	}
-      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->right->parent = np;
-              (*head)->subtree_prob += np->right->subtree_prob;
-            }
-	}
-    }
-}
-
-/* Search the parent sections of the case node tree
-   to see if a test for the lower bound of NODE would be redundant.
-   INDEX_TYPE is the type of the index expression.
-
-   The instructions to generate the case decision tree are
-   output in the same order as nodes are processed so it is
-   known that if a parent node checks the range of the current
-   node minus one that the current node is bounded at its lower
-   span.  Thus the test would be redundant.  */
-
-static int
-node_has_low_bound (case_node_ptr node, tree index_type)
-{
-  tree low_minus_one;
-  case_node_ptr pnode;
-
-  /* If the lower bound of this node is the lowest value in the index type,
-     we need not test it.  */
-
-  if (tree_int_cst_equal (node->low, TYPE_MIN_VALUE (index_type)))
-    return 1;
-
-  /* If this node has a left branch, the value at the left must be less
-     than that at this node, so it cannot be bounded at the bottom and
-     we need not bother testing any further.  */
-
-  if (node->left)
-    return 0;
-
-  low_minus_one = fold_build2 (MINUS_EXPR, TREE_TYPE (node->low),
-			       node->low,
-			       build_int_cst (TREE_TYPE (node->low), 1));
-
-  /* If the subtraction above overflowed, we can't verify anything.
-     Otherwise, look for a parent that tests our value - 1.  */
-
-  if (! tree_int_cst_lt (low_minus_one, node->low))
-    return 0;
-
-  for (pnode = node->parent; pnode; pnode = pnode->parent)
-    if (tree_int_cst_equal (low_minus_one, pnode->high))
-      return 1;
-
-  return 0;
-}
-
-/* Search the parent sections of the case node tree
-   to see if a test for the upper bound of NODE would be redundant.
-   INDEX_TYPE is the type of the index expression.
-
-   The instructions to generate the case decision tree are
-   output in the same order as nodes are processed so it is
-   known that if a parent node checks the range of the current
-   node plus one that the current node is bounded at its upper
-   span.  Thus the test would be redundant.  */
-
-static int
-node_has_high_bound (case_node_ptr node, tree index_type)
-{
-  tree high_plus_one;
-  case_node_ptr pnode;
-
-  /* If there is no upper bound, obviously no test is needed.  */
-
-  if (TYPE_MAX_VALUE (index_type) == NULL)
-    return 1;
-
-  /* If the upper bound of this node is the highest value in the type
-     of the index expression, we need not test against it.  */
-
-  if (tree_int_cst_equal (node->high, TYPE_MAX_VALUE (index_type)))
-    return 1;
-
-  /* If this node has a right branch, the value at the right must be greater
-     than that at this node, so it cannot be bounded at the top and
-     we need not bother testing any further.  */
-
-  if (node->right)
-    return 0;
-
-  high_plus_one = fold_build2 (PLUS_EXPR, TREE_TYPE (node->high),
-			       node->high,
-			       build_int_cst (TREE_TYPE (node->high), 1));
-
-  /* If the addition above overflowed, we can't verify anything.
-     Otherwise, look for a parent that tests our value + 1.  */
-
-  if (! tree_int_cst_lt (node->high, high_plus_one))
-    return 0;
-
-  for (pnode = node->parent; pnode; pnode = pnode->parent)
-    if (tree_int_cst_equal (high_plus_one, pnode->low))
-      return 1;
-
-  return 0;
-}
-
-/* Search the parent sections of the
-   case node tree to see if both tests for the upper and lower
-   bounds of NODE would be redundant.  */
-
-static int
-node_is_bounded (case_node_ptr node, tree index_type)
-{
-  return (node_has_low_bound (node, index_type)
-	  && node_has_high_bound (node, index_type));
-}
-
-
-/* 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.
-
-   Care is taken to prune redundant tests from the decision tree
-   by detecting any boundary conditions already checked by
-   emitted rtx.  (See node_has_high_bound, node_has_low_bound
-   and node_is_bounded, above.)
-
-   Where the test conditions can be shown to be redundant we emit
-   an unconditional jump to the target code.  As a further
-   optimization, the subordinates of a tree node are examined to
-   check for bounded nodes.  In this case conditional and/or
-   unconditional jumps as a result of the boundary check for the
-   current node are arranged to target the subordinates associated
-   code for out of bound conditions on the current node.
-
-   We can assume that when control reaches the code generated here,
-   the index value has already been compared with the parents
-   of this node, and determined to be on the same side of each parent
-   as this node is.  Thus, if this node tests for the value 51,
-   and a parent tested for 52, we don't need to consider
-   the possibility of a value greater than 51.  If another parent
-   tests for the value 50, then this node need not test anything.  */
-
-static void
-emit_case_nodes (rtx index, case_node_ptr node, rtx_code_label *default_label,
-		 profile_probability default_prob, tree index_type)
-{
-  /* If INDEX has an unsigned type, we must make unsigned branches.  */
-  int unsignedp = TYPE_UNSIGNED (index_type);
-  profile_probability probability;
-  profile_probability prob = node->prob, subtree_prob = node->subtree_prob;
-  machine_mode mode = GET_MODE (index);
-  machine_mode imode = TYPE_MODE (index_type);
-
-  /* Handle indices detected as constant during RTL expansion.  */
-  if (mode == VOIDmode)
-    mode = imode;
-
-  /* See if our parents have already tested everything for us.
-     If they have, emit an unconditional jump for this node.  */
-  if (node_is_bounded (node, index_type))
-    emit_jump (label_rtx (node->code_label));
-
-  else if (tree_int_cst_equal (node->low, node->high))
-    {
-      probability = conditional_probability (prob, subtree_prob + default_prob);
-      /* Node is single valued.  First see if the index expression matches
-	 this node and then check our children, if any.  */
-      do_jump_if_equal (mode, index,
-			convert_modes (mode, imode,
-				       expand_normal (node->low),
-				       unsignedp),
-			jump_target_rtx (node->code_label),
-			unsignedp, probability);
-      /* Since this case is taken at this point, reduce its weight from
-         subtree_weight.  */
-      subtree_prob -= prob;
-      if (node->right != 0 && node->left != 0)
-	{
-	  /* This node has children on both sides.
-	     Dispatch to one side or the other
-	     by comparing the index value with this node's value.
-	     If one subtree is bounded, check that one first,
-	     so we can avoid real branches in the tree.  */
-
-	  if (node_is_bounded (node->right, index_type))
-	    {
-              probability = conditional_probability (
-                  node->right->prob,
-                  subtree_prob + default_prob);
-	      emit_cmp_and_jump_insns (index,
-				       convert_modes
-				       (mode, imode,
-					expand_normal (node->high),
-					unsignedp),
-				       GT, NULL_RTX, mode, unsignedp,
-				       label_rtx (node->right->code_label),
-                                       probability);
-	      emit_case_nodes (index, node->left, default_label, default_prob,
-                               index_type);
-	    }
-
-	  else if (node_is_bounded (node->left, index_type))
-	    {
-              probability = conditional_probability (
-                  node->left->prob,
-                  subtree_prob + default_prob);
-	      emit_cmp_and_jump_insns (index,
-				       convert_modes
-				       (mode, imode,
-					expand_normal (node->high),
-					unsignedp),
-				       LT, NULL_RTX, mode, unsignedp,
-				       label_rtx (node->left->code_label),
-                                       probability);
-	      emit_case_nodes (index, node->right, default_label, 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.  */
-	  else if (tree_int_cst_equal (node->right->low, node->right->high)
-		   && node->right->left == 0
-		   && node->right->right == 0
-		   && tree_int_cst_equal (node->left->low, node->left->high)
-		   && node->left->left == 0
-		   && node->left->right == 0)
-	    {
-	      /* Neither node is bounded.  First distinguish the two sides;
-		 then emit the code for one side at a time.  */
-
-	      /* See if the value matches what the right hand side
-		 wants.  */
-              probability = conditional_probability (
-                  node->right->prob,
-                  subtree_prob + default_prob);
-	      do_jump_if_equal (mode, index,
-				convert_modes (mode, imode,
-					       expand_normal (node->right->low),
-					       unsignedp),
-				jump_target_rtx (node->right->code_label),
-				unsignedp, probability);
-
-	      /* See if the value matches what the left hand side
-		 wants.  */
-              probability = conditional_probability (
-                  node->left->prob,
-                  subtree_prob + default_prob);
-	      do_jump_if_equal (mode, index,
-				convert_modes (mode, imode,
-					       expand_normal (node->left->low),
-					       unsignedp),
-				jump_target_rtx (node->left->code_label),
-				unsignedp, probability);
-	    }
-
-	  else
-	    {
-	      /* Neither node is bounded.  First distinguish the two sides;
-		 then emit the code for one side at a time.  */
-
-	      tree test_label
-		= build_decl (curr_insn_location (),
-			      LABEL_DECL, NULL_TREE, void_type_node);
-
-              /* The default label could be reached either through the right
-                 subtree or the left subtree. Divide the probability
-                 equally.  */
-              probability = conditional_probability (
-                  node->right->subtree_prob + default_prob.apply_scale (1, 2),
-                  subtree_prob + default_prob);
-	      /* See if the value is on the right.  */
-	      emit_cmp_and_jump_insns (index,
-				       convert_modes
-				       (mode, imode,
-					expand_normal (node->high),
-					unsignedp),
-				       GT, NULL_RTX, mode, unsignedp,
-				       label_rtx (test_label),
-                                       probability);
-              default_prob = default_prob.apply_scale (1, 2);
-
-	      /* Value must be on the left.
-		 Handle the left-hand subtree.  */
-	      emit_case_nodes (index, node->left, default_label, default_prob, index_type);
-	      /* If left-hand subtree does nothing,
-		 go to default.  */
-	      if (default_label)
-	        emit_jump (default_label);
-
-	      /* Code branches here for the right-hand subtree.  */
-	      expand_label (test_label);
-	      emit_case_nodes (index, node->right, default_label, default_prob, index_type);
-	    }
-	}
-
-      else if (node->right != 0 && node->left == 0)
-	{
-	  /* 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->right->right || node->right->left
-	      || !tree_int_cst_equal (node->right->low, node->right->high))
-	    {
-	      if (!node_has_low_bound (node, index_type))
-		{
-                  probability = conditional_probability (
-                      default_prob.apply_scale (1, 2),
-                      subtree_prob + default_prob);
-		  emit_cmp_and_jump_insns (index,
-					   convert_modes
-					   (mode, imode,
-					    expand_normal (node->high),
-					    unsignedp),
-					   LT, NULL_RTX, mode, unsignedp,
-					   default_label,
-                                           probability);
-                  default_prob = default_prob.apply_scale (1, 2);
-		}
-
-	      emit_case_nodes (index, node->right, default_label, default_prob, index_type);
-	    }
-	  else
-            {
-              probability = conditional_probability (
-                  node->right->subtree_prob,
-                  subtree_prob + default_prob);
-	      /* 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.  */
-	      do_jump_if_equal (mode, index,
-			        convert_modes
-			        (mode, imode,
-			         expand_normal (node->right->low),
-			         unsignedp),
-				jump_target_rtx (node->right->code_label),
-				unsignedp, probability);
-            }
-	  }
-
-      else if (node->right == 0 && node->left != 0)
-	{
-	  /* Just one subtree, on the left.  */
-	  if (node->left->left || node->left->right
-	      || !tree_int_cst_equal (node->left->low, node->left->high))
-	    {
-	      if (!node_has_high_bound (node, index_type))
-		{
-                  probability = conditional_probability (
-                      default_prob.apply_scale (1, 2),
-                      subtree_prob + default_prob);
-		  emit_cmp_and_jump_insns (index,
-					   convert_modes
-					   (mode, imode,
-					    expand_normal (node->high),
-					    unsignedp),
-					   GT, NULL_RTX, mode, unsignedp,
-					   default_label,
-                                           probability);
-                  default_prob = default_prob.apply_scale (1, 2);
-		}
-
-	      emit_case_nodes (index, node->left, default_label,
-                               default_prob, index_type);
-	    }
-	  else
-            {
-              probability = conditional_probability (
-                  node->left->subtree_prob,
-                  subtree_prob + default_prob);
-	      /* 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.  */
-	      do_jump_if_equal (mode, index,
-			        convert_modes
-			        (mode, imode,
-			         expand_normal (node->left->low),
-			         unsignedp),
-				jump_target_rtx (node->left->code_label),
-				unsignedp, probability);
-            }
-	}
-    }
-  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->right != 0 && node->left != 0)
-	{
-	  /* Node has subtrees on both sides.
-	     If the right-hand subtree is bounded,
-	     test for it first, since we can go straight there.
-	     Otherwise, we need to make a branch in the control structure,
-	     then handle the two subtrees.  */
-	  tree test_label = 0;
-
-	  if (node_is_bounded (node->right, index_type))
-            {
-	      /* Right hand node is fully bounded so we can eliminate any
-	         testing and branch directly to the target code.  */
-              probability = conditional_probability (
-                  node->right->subtree_prob,
-                  subtree_prob + default_prob);
-	      emit_cmp_and_jump_insns (index,
-				       convert_modes
-				       (mode, imode,
-				        expand_normal (node->high),
-				        unsignedp),
-				       GT, NULL_RTX, mode, unsignedp,
-				       label_rtx (node->right->code_label),
-                                       probability);
-            }
-	  else
-	    {
-	      /* Right hand node requires testing.
-		 Branch to a label where we will handle it later.  */
-
-	      test_label = build_decl (curr_insn_location (),
-				       LABEL_DECL, NULL_TREE, void_type_node);
-              probability = conditional_probability (
-                  node->right->subtree_prob + default_prob.apply_scale (1, 2),
-                  subtree_prob + default_prob);
-	      emit_cmp_and_jump_insns (index,
-				       convert_modes
-				       (mode, imode,
-					expand_normal (node->high),
-					unsignedp),
-				       GT, NULL_RTX, mode, unsignedp,
-				       label_rtx (test_label),
-                                       probability);
-              default_prob = default_prob.apply_scale (1, 2);
-	    }
-
-	  /* Value belongs to this node or to the left-hand subtree.  */
-
-          probability = conditional_probability (
-              prob,
-              subtree_prob + default_prob);
-	  emit_cmp_and_jump_insns (index,
-				   convert_modes
-				   (mode, imode,
-				    expand_normal (node->low),
-				    unsignedp),
-				   GE, NULL_RTX, mode, unsignedp,
-				   label_rtx (node->code_label),
-                                   probability);
-
-	  /* Handle the left-hand subtree.  */
-	  emit_case_nodes (index, node->left, default_label, default_prob, index_type);
-
-	  /* If right node had to be handled later, do that now.  */
-
-	  if (test_label)
-	    {
-	      /* If the left-hand subtree fell through,
-		 don't let it fall into the right-hand subtree.  */
-	      if (default_label)
-		emit_jump (default_label);
-
-	      expand_label (test_label);
-	      emit_case_nodes (index, node->right, default_label, default_prob, index_type);
-	    }
-	}
-
-      else if (node->right != 0 && node->left == 0)
-	{
-	  /* Deal with values to the left of this node,
-	     if they are possible.  */
-	  if (!node_has_low_bound (node, index_type))
-	    {
-              probability = conditional_probability (
-                  default_prob.apply_scale (1, 2),
-                  subtree_prob + default_prob);
-	      emit_cmp_and_jump_insns (index,
-				       convert_modes
-				       (mode, imode,
-					expand_normal (node->low),
-					unsignedp),
-				       LT, NULL_RTX, mode, unsignedp,
-				       default_label,
-                                       probability);
-              default_prob = default_prob.apply_scale (1, 2);
-	    }
-
-	  /* Value belongs to this node or to the right-hand subtree.  */
-
-          probability = conditional_probability (
-              prob,
-              subtree_prob + default_prob);
-	  emit_cmp_and_jump_insns (index,
-				   convert_modes
-				   (mode, imode,
-				    expand_normal (node->high),
-				    unsignedp),
-				   LE, NULL_RTX, mode, unsignedp,
-				   label_rtx (node->code_label),
-                                   probability);
-
-	  emit_case_nodes (index, node->right, default_label, default_prob, index_type);
-	}
-
-      else if (node->right == 0 && node->left != 0)
-	{
-	  /* Deal with values to the right of this node,
-	     if they are possible.  */
-	  if (!node_has_high_bound (node, index_type))
-	    {
-              probability = conditional_probability (
-                  default_prob.apply_scale (1, 2),
-                  subtree_prob + default_prob);
-	      emit_cmp_and_jump_insns (index,
-				       convert_modes
-				       (mode, imode,
-					expand_normal (node->high),
-					unsignedp),
-				       GT, NULL_RTX, mode, unsignedp,
-				       default_label,
-                                       probability);
-              default_prob = default_prob.apply_scale (1, 2);
-	    }
-
-	  /* Value belongs to this node or to the left-hand subtree.  */
-
-          probability = conditional_probability (
-              prob,
-              subtree_prob + default_prob);
-	  emit_cmp_and_jump_insns (index,
-				   convert_modes
-				   (mode, imode,
-				    expand_normal (node->low),
-				    unsignedp),
-				   GE, NULL_RTX, mode, unsignedp,
-				   label_rtx (node->code_label),
-                                   probability);
-
-	  emit_case_nodes (index, node->left, default_label, 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.  */
-	  int high_bound = node_has_high_bound (node, index_type);
-	  int low_bound = node_has_low_bound (node, index_type);
-
-	  if (!high_bound && low_bound)
-	    {
-              probability = conditional_probability (
-                  default_prob,
-                  subtree_prob + default_prob);
-	      emit_cmp_and_jump_insns (index,
-				       convert_modes
-				       (mode, imode,
-					expand_normal (node->high),
-					unsignedp),
-				       GT, NULL_RTX, mode, unsignedp,
-				       default_label,
-                                       probability);
-	    }
-
-	  else if (!low_bound && high_bound)
-	    {
-              probability = conditional_probability (
-                  default_prob,
-                  subtree_prob + default_prob);
-	      emit_cmp_and_jump_insns (index,
-				       convert_modes
-				       (mode, imode,
-					expand_normal (node->low),
-					unsignedp),
-				       LT, NULL_RTX, mode, unsignedp,
-				       default_label,
-                                       probability);
-	    }
-	  else if (!low_bound && !high_bound)
-	    {
-	      /* Widen LOW and HIGH to the same width as INDEX.  */
-	      tree type = lang_hooks.types.type_for_mode (mode, unsignedp);
-	      tree low = build1 (CONVERT_EXPR, type, node->low);
-	      tree high = build1 (CONVERT_EXPR, type, node->high);
-	      rtx low_rtx, new_index, new_bound;
-
-	      /* Instead of doing two branches, emit one unsigned branch for
-		 (index-low) > (high-low).  */
-	      low_rtx = expand_expr (low, NULL_RTX, mode, EXPAND_NORMAL);
-	      new_index = expand_simple_binop (mode, MINUS, index, low_rtx,
-					       NULL_RTX, unsignedp,
-					       OPTAB_WIDEN);
-	      new_bound = expand_expr (fold_build2 (MINUS_EXPR, type,
-						    high, low),
-				       NULL_RTX, mode, EXPAND_NORMAL);
-
-              probability = conditional_probability (
-                  default_prob,
-                  subtree_prob + default_prob);
-	      emit_cmp_and_jump_insns (new_index, new_bound, GT, NULL_RTX,
-				       mode, 1, default_label, probability);
-	    }
-
-	  emit_jump (jump_target_rtx (node->code_label));
-	}
-    }
-}
diff --git a/gcc/testsuite/gcc.dg/tree-prof/update-loopch.c b/gcc/testsuite/gcc.dg/tree-prof/update-loopch.c
index 242fa524ee6..73efc878ec0 100644
--- a/gcc/testsuite/gcc.dg/tree-prof/update-loopch.c
+++ b/gcc/testsuite/gcc.dg/tree-prof/update-loopch.c
@@ -1,4 +1,4 @@
-/* { dg-options "-O2 -fdump-ipa-profile-blocks-details -fdump-tree-optimized-blocks-details" } */
+/* { dg-options "-O2 -fdump-ipa-profile-blocks-details -fdump-tree-switchlower-blocks-details" } */
 int max = 33333;
 int a[8];
 int
@@ -16,7 +16,7 @@ main ()
    edge.  */
 /* autofdo cannot do that precise counts */
 /* { dg-final-use-not-autofdo { scan-ipa-dump "loop depth 1, count 33334" "profile"} } */
-/* { dg-final-use-not-autofdo { scan-tree-dump "loop depth 1, count 33333" "optimized"} } */
-/* { dg-final-use-not-autofdo { scan-tree-dump-not "loop depth 1, count 33332" "optimized"} } */
-/* { dg-final-use-not-autofdo { scan-tree-dump "Removing basic block" "optimized"} } */
-/* { dg-final-use { scan-tree-dump-not "Invalid sum" "optimized"} } */
+/* { dg-final-use-not-autofdo { scan-tree-dump "loop depth 1, count 33333" "switchlower"} } */
+/* { dg-final-use-not-autofdo { scan-tree-dump-not "loop depth 1, count 33332" "switchlower"} } */
+/* { dg-final-use-not-autofdo { scan-tree-dump "Removing basic block" "switchlower"} } */
+/* { dg-final-use { scan-tree-dump-not "Invalid sum" "switchlower"} } */
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp104.c b/gcc/testsuite/gcc.dg/tree-ssa/vrp104.c
index 2c3db2e1c49..aa3b00a1204 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/vrp104.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp104.c
@@ -1,6 +1,6 @@
 /* PR tree-optimization/18046  */
 /* { dg-options "-O2 -fdump-tree-optimized" }  */
-/* { dg-final { scan-tree-dump-times "switch" 1 "optimized" } }  */
+/* { dg-final { scan-tree-dump-times "switch" 1 "switchlower" } }  */
 
 void foo (void);
 void bar (void);
diff --git a/gcc/timevar.def b/gcc/timevar.def
index e2460585d62..8cec6af80df 100644
--- a/gcc/timevar.def
+++ b/gcc/timevar.def
@@ -208,6 +208,7 @@ DEFTIMEVAR (TV_TREE_COPY_RENAME	     , "tree rename SSA copies")
 DEFTIMEVAR (TV_TREE_SSA_VERIFY       , "tree SSA verifier")
 DEFTIMEVAR (TV_TREE_STMT_VERIFY      , "tree STMT verifier")
 DEFTIMEVAR (TV_TREE_SWITCH_CONVERSION, "tree switch conversion")
+DEFTIMEVAR (TV_TREE_SWITCH_LOWERING,   "tree switch lowering")
 DEFTIMEVAR (TV_TRANS_MEM             , "transactional memory")
 DEFTIMEVAR (TV_TREE_STRLEN           , "tree strlen optimization")
 DEFTIMEVAR (TV_CGRAPH_VERIFY         , "callgraph verifier")
diff --git a/gcc/tree-pass.h b/gcc/tree-pass.h
index 2863f769610..9f76d822abc 100644
--- a/gcc/tree-pass.h
+++ b/gcc/tree-pass.h
@@ -409,6 +409,7 @@ extern gimple_opt_pass *make_pass_profile (gcc::context *ctxt);
 extern gimple_opt_pass *make_pass_strip_predict_hints (gcc::context *ctxt);
 extern gimple_opt_pass *make_pass_lower_complex_O0 (gcc::context *ctxt);
 extern gimple_opt_pass *make_pass_lower_complex (gcc::context *ctxt);
+extern gimple_opt_pass *make_pass_lower_switch (gcc::context *ctxt);
 extern gimple_opt_pass *make_pass_lower_vector (gcc::context *ctxt);
 extern gimple_opt_pass *make_pass_lower_vector_ssa (gcc::context *ctxt);
 extern gimple_opt_pass *make_pass_lower_omp (gcc::context *ctxt);
diff --git a/gcc/tree-switch-conversion.c b/gcc/tree-switch-conversion.c
index e5b5cb9a0be..8e757e57258 100644
--- a/gcc/tree-switch-conversion.c
+++ b/gcc/tree-switch-conversion.c
@@ -46,6 +46,9 @@ Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
 #include "gimplify-me.h"
 #include "tree-cfg.h"
 #include "cfgloop.h"
+#include "alloc-pool.h"
+#include "target.h"
+#include "tree-into-ssa.h"
 
 /* ??? For lang_hooks.types.type_for_mode, but is there a word_mode
    type in the GIMPLE type system that is language-independent?  */
@@ -1662,3 +1665,1178 @@ make_pass_convert_switch (gcc::context *ctxt)
 {
   return new pass_convert_switch (ctxt);
 }
+
+struct case_node
+{
+  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.  */
+};
+
+typedef case_node *case_node_ptr;
+
+static basic_block emit_case_nodes (basic_block, tree, case_node_ptr,
+				    basic_block, tree, profile_probability,
+				    tree, hash_map<tree, tree> *);
+static bool node_has_low_bound (case_node_ptr, tree);
+static bool node_has_high_bound (case_node_ptr, tree);
+static bool node_is_bounded (case_node_ptr, tree);
+
+/* Return the smallest number of different values for which it is best to use a
+   jump-table instead of a tree of conditional branches.  */
+
+static unsigned int
+case_values_threshold (void)
+{
+  unsigned int threshold = PARAM_VALUE (PARAM_CASE_VALUES_THRESHOLD);
+
+  if (threshold == 0)
+    threshold = targetm.case_values_threshold ();
+
+  return threshold;
+}
+
+/* Reset the aux field of all outgoing edges of basic block BB.  */
+
+static inline void
+reset_out_edges_aux (basic_block bb)
+{
+  edge e;
+  edge_iterator ei;
+  FOR_EACH_EDGE (e, ei, bb->succs)
+    e->aux = (void *) 0;
+}
+
+/* Compute the number of case labels that correspond to each outgoing edge of
+   STMT.  Record this information in the aux field of the edge.  */
+
+static inline void
+compute_cases_per_edge (gswitch *stmt)
+{
+  basic_block bb = gimple_bb (stmt);
+  reset_out_edges_aux (bb);
+  int ncases = gimple_switch_num_labels (stmt);
+  for (int i = ncases - 1; i >= 1; --i)
+    {
+      tree elt = gimple_switch_label (stmt, i);
+      tree lab = CASE_LABEL (elt);
+      basic_block case_bb = label_to_block_fn (cfun, lab);
+      edge case_edge = find_edge (bb, case_bb);
+      case_edge->aux = (void *) ((intptr_t) (case_edge->aux) + 1);
+    }
+}
+
+/* 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.
+
+   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.  */
+
+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)
+{
+  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;
+}
+
+/* Dump ROOT, a list or tree of case nodes, to file.  */
+
+static void
+dump_case_nodes (FILE *f, case_node *root, int indent_step, int indent_level)
+{
+  if (root == 0)
+    return;
+  indent_level++;
+
+  dump_case_nodes (f, root->left, indent_step, indent_level);
+
+  fputs (";; ", f);
+  fprintf (f, "%*s", indent_step * indent_level, "");
+  print_dec (root->low, f, TYPE_SIGN (TREE_TYPE (root->low)));
+  if (!tree_int_cst_equal (root->low, root->high))
+    {
+      fprintf (f, " ... ");
+      print_dec (root->high, f, TYPE_SIGN (TREE_TYPE (root->high)));
+    }
+  fputs ("\n", f);
+
+  dump_case_nodes (f, root->right, indent_step, indent_level);
+}
+
+/* Take an ordered list of case nodes
+   and transform them into a near optimal binary tree,
+   on the assumption that any target code selection value is as
+   likely as any other.
+
+   The transformation is performed by splitting the ordered
+   list into two equal sections plus a pivot.  The parts are
+   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)
+{
+  case_node_ptr np;
+
+  np = *head;
+  if (np)
+    {
+      int i = 0;
+      int ranges = 0;
+      case_node_ptr *npp;
+      case_node_ptr left;
+
+      /* Count the number of entries on branch.  Also count the ranges.  */
+
+      while (np)
+	{
+	  if (!tree_int_cst_equal (np->low, np->high))
+	    ranges++;
+
+	  i++;
+	  np = np->right;
+	}
+
+      if (i > 2)
+	{
+	  /* Split this list if it is long enough for that to help.  */
+	  npp = head;
+	  left = *npp;
+
+	  /* If there are just three nodes, split at the middle one.  */
+	  if (i == 3)
+	    npp = &(*npp)->right;
+	  else
+	    {
+	      /* Find the place in the list that bisects the list's total cost,
+		 where ranges count as 2.
+		 Here I gets half the total cost.  */
+	      i = (i + ranges + 1) / 2;
+	      while (1)
+		{
+		  /* Skip nodes while their cost does not reach that amount.  */
+		  if (!tree_int_cst_equal ((*npp)->low, (*npp)->high))
+		    i--;
+		  i--;
+		  if (i <= 0)
+		    break;
+		  npp = &(*npp)->right;
+		}
+	    }
+	  *head = np = *npp;
+	  *npp = 0;
+	  np->parent = parent;
+	  np->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;
+	}
+      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->right->parent = np;
+	      (*head)->subtree_prob += np->right->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.  */
+
+static bool
+expand_switch_as_decision_tree_p (tree range,
+				  unsigned int uniq ATTRIBUTE_UNUSED,
+				  unsigned int count)
+{
+  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;
+
+  return false;
+}
+
+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 ();
+
+      tree *definition = phi_mapping->get (gimple_phi_result (phi));
+      if (definition)
+	add_phi_arg (phi, *definition, e, UNKNOWN_LOCATION);
+    }
+}
+
+
+/* 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)
+{
+  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.  */
+
+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)
+{
+  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);
+    }
+
+  basic_block bb = gimple_bb (s);
+  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);
+
+  bb = emit_case_nodes (bb, index_expr, case_list, default_bb, default_label,
+			default_prob, index_type, phi_mapping);
+
+  if (bb)
+    emit_jump (bb, default_bb, phi_mapping);
+
+  /* Remove all edges and do just an edge that will reach default_bb.  */
+  gsi = gsi_last_bb (gimple_bb (s));
+  gsi_remove (&gsi, true);
+}
+
+static void
+record_phi_operand_mapping (const vec<basic_block> bbs, basic_block switch_bb,
+			    hash_map <tree, tree> *map)
+{
+  /* Record all PHI nodes that have to be fixed after conversion.  */
+  for (unsigned i = 0; i < bbs.length (); i++)
+    {
+      basic_block bb = bbs[i];
+
+      gphi_iterator gsi;
+      for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
+	{
+	  gphi *phi = gsi.phi ();
+
+	  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;
+		}
+	    }
+	}
+    }
+}
+
+/* Attempt to expand gimple switch STMT to a decision tree.  */
+
+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);
+
+  hash_map<tree, tree> phi_mapping;
+  auto_vec<basic_block> case_bbs;
+
+  /* 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;
+
+  /* A pool for case nodes.  */
+  object_allocator<case_node> case_node_pool ("struct case_node pool");
+
+  /* cleanup_tree_cfg removes all SWITCH_EXPR with their index
+     expressions being INTEGER_CST.  */
+  gcc_assert (TREE_CODE (index_expr) != INTEGER_CST);
+
+  /* Optimization of switch statements with only one label has already
+     occurred, so we should never see them at this point.  */
+  gcc_assert (ncases > 1);
+
+  /* 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 = EDGE_SUCC (bb, 0);
+  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));
+
+  /* Compute span of values.  */
+  range = fold_build2 (MINUS_EXPR, index_type, maxval, minval);
+
+  /* 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);
+
+  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);
+
+      /* 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, 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, high);
+
+      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);
+
+      case_bbs.safe_push (case_bb);
+    }
+  reset_out_edges_aux (bb);
+  record_phi_operand_mapping (case_bbs, bb, &phi_mapping);
+
+  /* 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);
+
+  /* Decide how to expand this switch.
+     The two options at this point are a dispatch table (casesi or
+     tablejump) or a decision tree.  */
+
+  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 false;
+}
+
+/* The main function of the pass scans statements for switches and invokes
+   process_switch on them.  */
+
+namespace {
+
+const pass_data pass_data_lower_switch =
+{
+  GIMPLE_PASS, /* type */
+  "switchlower", /* name */
+  OPTGROUP_NONE, /* optinfo_flags */
+  TV_TREE_SWITCH_LOWERING, /* tv_id */
+  ( PROP_cfg | PROP_ssa ), /* properties_required */
+  0, /* properties_provided */
+  0, /* properties_destroyed */
+  0, /* todo_flags_start */
+  TODO_update_ssa | TODO_cleanup_cfg, /* todo_flags_finish */
+};
+
+class pass_lower_switch : public gimple_opt_pass
+{
+public:
+  pass_lower_switch (gcc::context *ctxt)
+    : gimple_opt_pass (pass_data_lower_switch, ctxt)
+  {}
+
+  /* opt_pass methods: */
+  virtual bool gate (function *) { return true; }
+  virtual unsigned int execute (function *);
+
+}; // class pass_lower_switch
+
+unsigned int
+pass_lower_switch::execute (function *fun)
+{
+  basic_block bb;
+  bool expanded = false;
+
+  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));
+
+	      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));
+	}
+    }
+
+  if (expanded)
+    {
+      free_dominance_info (CDI_DOMINATORS);
+      free_dominance_info (CDI_POST_DOMINATORS);
+      mark_virtual_operands_for_renaming (cfun);
+    }
+
+  return 0;
+}
+
+} // anon namespace
+
+gimple_opt_pass *
+make_pass_lower_switch (gcc::context *ctxt)
+{
+  return new pass_lower_switch (ctxt);
+}
+
+/* Generate code to jump to LABEL if OP0 and OP1 are equal in mode MODE.
+   PROB is the probability of jumping to LABEL.  */
+static basic_block
+do_jump_if_equal (basic_block bb, tree op0, tree op1, basic_block label_bb,
+		  profile_probability prob, hash_map<tree, tree> *phi_mapping)
+{
+  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);
+  fix_phi_operands_for_edge (true_edge, phi_mapping);
+  true_edge->probability = prob;
+
+  return false_edge->dest;
+}
+
+/* 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.
+
+   Care is taken to prune redundant tests from the decision tree
+   by detecting any boundary conditions already checked by
+   emitted rtx.  (See node_has_high_bound, node_has_low_bound
+   and node_is_bounded, above.)
+
+   Where the test conditions can be shown to be redundant we emit
+   an unconditional jump to the target code.  As a further
+   optimization, the subordinates of a tree node are examined to
+   check for bounded nodes.  In this case conditional and/or
+   unconditional jumps as a result of the boundary check for the
+   current node are arranged to target the subordinates associated
+   code for out of bound conditions on the current node.
+
+   We can assume that when control reaches the code generated here,
+   the index value has already been compared with the parents
+   of this node, and determined to be on the same side of each parent
+   as this node is.  Thus, if this node tests for the value 51,
+   and a parent tested for 52, we don't need to consider
+   the possibility of a value greater than 51.  If another parent
+   tests for the value 50, then this node need not test anything.  */
+
+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 INDEX has an unsigned type, we must make unsigned branches.  */
+  profile_probability probability;
+  profile_probability prob = node->prob, subtree_prob = node->subtree_prob;
+
+  /* See if our parents have already tested everything for us.
+     If they have, emit an unconditional jump for this node.  */
+  if (node_is_bounded (node, index_type))
+    {
+      emit_jump (bb, node->case_bb, phi_mapping);
+      return NULL;
+    }
+
+  else if (tree_int_cst_equal (node->low, node->high))
+    {
+      probability = conditional_probability (prob, subtree_prob + default_prob);
+      /* Node is single valued.  First see if the index expression matches
+	 this node and then check our children, if any.  */
+      bb = do_jump_if_equal (bb, index, node->low, node->case_bb, probability,
+			     phi_mapping);
+      /* Since this case is taken at this point, reduce its weight from
+	 subtree_weight.  */
+      subtree_prob -= prob;
+      if (node->right != 0 && node->left != 0)
+	{
+	  /* This node has children on both sides.
+	     Dispatch to one side or the other
+	     by comparing the index value with this node's value.
+	     If one subtree is bounded, check that one first,
+	     so we can avoid real branches in the tree.  */
+
+	  if (node_is_bounded (node->right, index_type))
+	    {
+	      probability
+		= conditional_probability (node->right->prob,
+					   subtree_prob + default_prob);
+	      bb = emit_cmp_and_jump_insns (bb, index, node->high, GT_EXPR,
+					    node->right->case_bb, probability,
+					    phi_mapping);
+	      bb = emit_case_nodes (bb, index, node->left, default_bb,
+				    default_label, default_prob, index_type,
+				    phi_mapping);
+	    }
+
+	  else if (node_is_bounded (node->left, index_type))
+	    {
+	      probability
+		= conditional_probability (node->left->prob,
+					   subtree_prob + default_prob);
+	      bb = emit_cmp_and_jump_insns (bb, index, node->high, LT_EXPR,
+					    node->left->case_bb, probability,
+					    phi_mapping);
+	      bb = emit_case_nodes (bb, index, node->right, default_bb,
+				    default_label, default_prob, index_type,
+				    phi_mapping);
+	    }
+
+	  /* If both children are single-valued cases with no
+	     children, finish up all the work.  This way, we can save
+	     one ordered comparison.  */
+	  else if (tree_int_cst_equal (node->right->low, node->right->high)
+		   && node->right->left == 0 && node->right->right == 0
+		   && tree_int_cst_equal (node->left->low, node->left->high)
+		   && node->left->left == 0 && node->left->right == 0)
+	    {
+	      /* Neither node is bounded.  First distinguish the two sides;
+		 then emit the code for one side at a time.  */
+
+	      /* See if the value matches what the right hand side
+		 wants.  */
+	      probability
+		= conditional_probability (node->right->prob,
+					   subtree_prob + default_prob);
+	      bb = do_jump_if_equal (bb, index, node->right->low,
+				     node->right->case_bb, probability,
+				     phi_mapping);
+
+	      /* See if the value matches what the left hand side
+		 wants.  */
+	      probability
+		= conditional_probability (node->left->prob,
+					   subtree_prob + default_prob);
+	      bb = do_jump_if_equal (bb, index, node->left->low,
+				     node->left->case_bb, probability,
+				     phi_mapping);
+	    }
+
+	  else
+	    {
+	      /* Neither node is bounded.  First distinguish the two sides;
+		 then emit the code for one side at a time.  */
+
+	      basic_block test_bb = split_edge (single_succ_edge (bb));
+	      redirect_edge_succ (single_pred_edge (test_bb),
+				  single_succ_edge (bb)->dest);
+
+	      /* The default label could be reached either through the right
+		 subtree or the left subtree.  Divide the probability
+		 equally.  */
+	      probability
+		= conditional_probability (node->right->subtree_prob
+					     + default_prob.apply_scale (1, 2),
+					   subtree_prob + default_prob);
+	      /* See if the value is on the right.  */
+	      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 must be on the left.
+		 Handle the left-hand subtree.  */
+	      bb = emit_case_nodes (bb, index, node->left, default_bb,
+				    default_label, default_prob, index_type,
+				    phi_mapping);
+	      /* If left-hand subtree does nothing,
+		 go to default.  */
+
+	      if (bb && default_bb)
+		emit_jump (bb, default_bb, phi_mapping);
+
+	      /* Code branches here for the right-hand subtree.  */
+	      bb = emit_case_nodes (test_bb, index, node->right, default_bb,
+				    default_label, default_prob, index_type,
+				    phi_mapping);
+	    }
+	}
+      else if (node->right != 0 && node->left == 0)
+	{
+	  /* 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->right->right || node->right->left
+	      || !tree_int_cst_equal (node->right->low, node->right->high))
+	    {
+	      if (!node_has_low_bound (node, index_type))
+		{
+		  probability
+		    = conditional_probability (default_prob.apply_scale (1, 2),
+					       subtree_prob + default_prob);
+		  bb = emit_cmp_and_jump_insns (bb, index, node->high, LT_EXPR,
+						default_bb, probability,
+						phi_mapping);
+		  default_prob = default_prob.apply_scale (1, 2);
+		}
+
+	      bb = emit_case_nodes (bb, index, node->right, default_bb,
+				    default_label, default_prob, index_type,
+				    phi_mapping);
+	    }
+	  else
+	    {
+	      probability
+		= conditional_probability (node->right->subtree_prob,
+					   subtree_prob + default_prob);
+	      /* 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.  */
+	      bb = do_jump_if_equal (bb, index, node->right->low,
+				     node->right->case_bb, probability,
+				     phi_mapping);
+	    }
+	}
+
+      else if (node->right == 0 && node->left != 0)
+	{
+	  /* Just one subtree, on the left.  */
+	  if (node->left->left || node->left->right
+	      || !tree_int_cst_equal (node->left->low, node->left->high))
+	    {
+	      if (!node_has_high_bound (node, index_type))
+		{
+		  probability
+		    = conditional_probability (default_prob.apply_scale (1, 2),
+					       subtree_prob + default_prob);
+		  bb = emit_cmp_and_jump_insns (bb, index, node->high, GT_EXPR,
+						default_bb, probability,
+						phi_mapping);
+		  default_prob = default_prob.apply_scale (1, 2);
+		}
+
+	      bb = emit_case_nodes (bb, index, node->left, default_bb,
+				    default_label, default_prob, index_type,
+				    phi_mapping);
+	    }
+	  else
+	    {
+	      probability
+		= conditional_probability (node->left->subtree_prob,
+					   subtree_prob + default_prob);
+	      /* 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.  */
+	      do_jump_if_equal (bb, index, node->left->low, node->left->case_bb,
+				probability, phi_mapping);
+	    }
+	}
+    }
+  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->right != 0 && node->left != 0)
+	{
+	  /* Node has subtrees on both sides.
+	     If the right-hand subtree is bounded,
+	     test for it first, since we can go straight there.
+	     Otherwise, we need to make a branch in the control structure,
+	     then handle the two subtrees.  */
+	  basic_block test_bb = NULL;
+
+	  if (node_is_bounded (node->right, index_type))
+	    {
+	      /* Right hand node is fully bounded so we can eliminate any
+		 testing and branch directly to the target code.  */
+	      probability
+		= conditional_probability (node->right->subtree_prob,
+					   subtree_prob + default_prob);
+	      bb = emit_cmp_and_jump_insns (bb, index, node->high, GT_EXPR,
+					    node->right->case_bb, probability,
+					    phi_mapping);
+	    }
+	  else
+	    {
+	      /* Right hand node requires testing.
+		 Branch to a label where we will handle it later.  */
+
+	      test_bb = split_edge (single_succ_edge (bb));
+	      redirect_edge_succ (single_pred_edge (test_bb),
+				  single_succ_edge (bb)->dest);
+
+	      probability
+		= conditional_probability (node->right->subtree_prob
+					     + default_prob.apply_scale (1, 2),
+					   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 (prob, 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 right node had to be handled later, do that now.  */
+	  if (test_bb)
+	    {
+	      /* If the left-hand subtree fell through,
+		 don't let it fall into the right-hand subtree.  */
+	      if (bb && 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);
+	    }
+	}
+
+      else if (node->right != 0 && node->left == 0)
+	{
+	  /* Deal with values to the left of this node,
+	     if they are possible.  */
+	  if (!node_has_low_bound (node, index_type))
+	    {
+	      probability
+		= conditional_probability (default_prob.apply_scale (1, 2),
+					   subtree_prob + default_prob);
+	      bb = emit_cmp_and_jump_insns (bb, index, node->low, LT_EXPR,
+					    default_bb, probability,
+					    phi_mapping);
+	      default_prob = default_prob.apply_scale (1, 2);
+	    }
+
+	  /* Value belongs to this node or to the right-hand subtree.  */
+
+	  probability
+	    = conditional_probability (prob, subtree_prob + default_prob);
+	  bb = emit_cmp_and_jump_insns (bb, index, node->high, LE_EXPR,
+					node->case_bb, probability,
+					phi_mapping);
+
+	  bb = emit_case_nodes (bb, index, node->right, default_bb,
+				default_label, default_prob, index_type,
+				phi_mapping);
+	}
+
+      else if (node->right == 0 && node->left != 0)
+	{
+	  /* Deal with values to the right of this node,
+	     if they are possible.  */
+	  if (!node_has_high_bound (node, index_type))
+	    {
+	      probability
+		= conditional_probability (default_prob.apply_scale (1, 2),
+					   subtree_prob + default_prob);
+	      bb = emit_cmp_and_jump_insns (bb, index, node->high, GT_EXPR,
+					    default_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 (prob, subtree_prob + default_prob);
+	  bb = emit_cmp_and_jump_insns (bb, index, node->low, GE_EXPR,
+					node->case_bb, probability,
+					phi_mapping);
+
+	  bb = emit_case_nodes (bb, index, node->left, default_bb,
+				default_label, default_prob, index_type,
+				phi_mapping);
+	}
+
+      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.  */
+	  bool high_bound = node_has_high_bound (node, index_type);
+	  bool low_bound = node_has_low_bound (node, index_type);
+
+	  if (!high_bound && low_bound)
+	    {
+	      probability
+		= conditional_probability (default_prob,
+					   subtree_prob + default_prob);
+	      bb = emit_cmp_and_jump_insns (bb, index, node->high, GT_EXPR,
+					    default_bb, probability,
+					    phi_mapping);
+	    }
+
+	  else if (!low_bound && high_bound)
+	    {
+	      probability
+		= conditional_probability (default_prob,
+					   subtree_prob + default_prob);
+	      bb = emit_cmp_and_jump_insns (bb, index, node->low, LT_EXPR,
+					    default_bb, probability,
+					    phi_mapping);
+	    }
+	  else if (!low_bound && !high_bound)
+	    {
+	      tree type = TREE_TYPE (index);
+	      tree utype = unsigned_type_for (type);
+
+	      tree lhs = make_ssa_name (type);
+	      gassign *sub1
+		= gimple_build_assign (lhs, MINUS_EXPR, index, node->low);
+
+	      tree converted = make_ssa_name (utype);
+	      gassign *a = gimple_build_assign (converted, NOP_EXPR, lhs);
+
+	      tree rhs = fold_build2 (MINUS_EXPR, utype,
+				      fold_convert (type, node->high),
+				      fold_convert (type, node->low));
+	      gimple_stmt_iterator gsi = gsi_last_bb (bb);
+	      gsi_insert_before (&gsi, sub1, GSI_SAME_STMT);
+	      gsi_insert_before (&gsi, a, GSI_SAME_STMT);
+
+	      probability
+		= conditional_probability (default_prob,
+					   subtree_prob + default_prob);
+	      bb = emit_cmp_and_jump_insns (bb, converted, rhs, GT_EXPR,
+					    default_bb, probability,
+					    phi_mapping);
+	    }
+
+	  emit_jump (bb, node->case_bb, phi_mapping);
+	  return NULL;
+	}
+    }
+
+  return bb;
+}
+
+/* Search the parent sections of the case node tree
+   to see if a test for the lower bound of NODE would be redundant.
+   INDEX_TYPE is the type of the index expression.
+
+   The instructions to generate the case decision tree are
+   output in the same order as nodes are processed so it is
+   known that if a parent node checks the range of the current
+   node minus one that the current node is bounded at its lower
+   span.  Thus the test would be redundant.  */
+
+static bool
+node_has_low_bound (case_node_ptr node, tree index_type)
+{
+  tree low_minus_one;
+  case_node_ptr pnode;
+
+  /* If the lower bound of this node is the lowest value in the index type,
+     we need not test it.  */
+
+  if (tree_int_cst_equal (node->low, TYPE_MIN_VALUE (index_type)))
+    return true;
+
+  /* If this node has a left branch, the value at the left must be less
+     than that at this node, so it cannot be bounded at the bottom and
+     we need not bother testing any further.  */
+
+  if (node->left)
+    return false;
+
+  low_minus_one = fold_build2 (MINUS_EXPR, TREE_TYPE (node->low), node->low,
+			       build_int_cst (TREE_TYPE (node->low), 1));
+
+  /* If the subtraction above overflowed, we can't verify anything.
+     Otherwise, look for a parent that tests our value - 1.  */
+
+  if (!tree_int_cst_lt (low_minus_one, node->low))
+    return false;
+
+  for (pnode = node->parent; pnode; pnode = pnode->parent)
+    if (tree_int_cst_equal (low_minus_one, pnode->high))
+      return true;
+
+  return false;
+}
+
+/* Search the parent sections of the case node tree
+   to see if a test for the upper bound of NODE would be redundant.
+   INDEX_TYPE is the type of the index expression.
+
+   The instructions to generate the case decision tree are
+   output in the same order as nodes are processed so it is
+   known that if a parent node checks the range of the current
+   node plus one that the current node is bounded at its upper
+   span.  Thus the test would be redundant.  */
+
+static bool
+node_has_high_bound (case_node_ptr node, tree index_type)
+{
+  tree high_plus_one;
+  case_node_ptr pnode;
+
+  /* If there is no upper bound, obviously no test is needed.  */
+
+  if (TYPE_MAX_VALUE (index_type) == NULL)
+    return true;
+
+  /* If the upper bound of this node is the highest value in the type
+     of the index expression, we need not test against it.  */
+
+  if (tree_int_cst_equal (node->high, TYPE_MAX_VALUE (index_type)))
+    return true;
+
+  /* If this node has a right branch, the value at the right must be greater
+     than that at this node, so it cannot be bounded at the top and
+     we need not bother testing any further.  */
+
+  if (node->right)
+    return false;
+
+  high_plus_one = fold_build2 (PLUS_EXPR, TREE_TYPE (node->high), node->high,
+			       build_int_cst (TREE_TYPE (node->high), 1));
+
+  /* If the addition above overflowed, we can't verify anything.
+     Otherwise, look for a parent that tests our value + 1.  */
+
+  if (!tree_int_cst_lt (node->high, high_plus_one))
+    return false;
+
+  for (pnode = node->parent; pnode; pnode = pnode->parent)
+    if (tree_int_cst_equal (high_plus_one, pnode->low))
+      return true;
+
+  return false;
+}
+
+/* Search the parent sections of the
+   case node tree to see if both tests for the upper and lower
+   bounds of NODE would be redundant.  */
+
+static bool
+node_is_bounded (case_node_ptr node, tree index_type)
+{
+  return (node_has_low_bound (node, index_type)
+	  && node_has_high_bound (node, index_type));
+}
-- 
2.13.3


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]