Patchwork [1/2] if-to-switch conversion pass

login
register
mail settings
Submitter Tom de Vries
Date Jan. 24, 2013, 6:09 p.m.
Message ID <510178C1.60704@mentor.com>
Download mbox | patch
Permalink /patch/215464/
State New
Headers show

Comments

Tom de Vries - Jan. 24, 2013, 6:09 p.m.
Steven,

On 19/07/12 16:43, Steven Bosscher wrote:
> On Thu, Jul 19, 2012 at 3:43 PM, Tom de Vries <Tom_deVries@mentor.com> wrote:
>>> I think you should compare your method to the one described in the
>>> paper, and at least reference the paper if it's somehow similar --
>>
>> Interesting, thanks. Will do.
> 

Done.

> BTW, I have the value profiling bits for this in my implementation of
> this pass. Your pass is more complete than mine, so I'm going to port
> my value-profiling bits to your pass once your pass is on the trunk.
> 
> 
>>> This transformation should *not* be enabled by default at -O2. Users
>>> may have sorted the branches deliberately in a certain order, and if
>>> switch expansion results in a different order, your transformation is
>>> not an optimization.
>>>
>>
>> Right, thanks for pointing that out.  We don't tag case labels with
>> probabilities,
> 
> With my value-profiling patch, we will do that :-)
> 
> 
>> so once we convert an if-chain to a switch and expand the switch
>> back to an if-chain, there's no information to recreate the original (or then
>> optimal) order.
> 
> Right. What I think we should do, is use the analysis result of your
> pass to do either the if-to-switch conversion *or* an if-to-if
> conversion as described in that paper.
> 
> 
>> If we convert to a shift-and-bit-test however, and we collapse all the jumps
>> into one, we increase the likelihood of the remaining jump at the cost of a more
>> complex jump condition computation.
>>
>> In the motivating example of the pass, the first jump of the if-chain has a
>> probability of 0.5. After converting the if-chain to a shift-and-bit-test the
>> probability of the remaining jump is 0.9.
>>
>> I expect that on architectures with a high branch mispredict penalty the cost of
>> the additional computation will be more that compensated by the reduced mispredicts.
>>
>> So how about this heuristic:
>> - -Os: always convert if-chains into switches
> 
> That makes sense if your ranges are dense. For a sparse if-chain you
> may increase code size if the switch expands to a tablejump (because
> the tablejump gaps have to be filled). But there is a heuristic in
> expand_switch_as_decision_tree_p for the -Os case that seems to work
> quite well (see PR11823 and
> http://gcc.gnu.org/ml/gcc-patches/2003-08/msg02054.html) so I think
> it's always a win to convert an if-chain to a switch with -Os.
> 

I've played around with this on x86_64, but I've haven't yet been able to define
a sensible size heuristic (which is one of the reasons why it took me so long to
reply, sorry about that). So this particular version of the patch is only active
when optimizing for speed.

> There was one counter-example some time ago, see
> http://gcc.gnu.org/ml/gcc-patches/2007-06/msg01648.html, perhaps you
> can have a look and see what happens with the "if"-version of the code
> in that mail with your patch.
> 
> 

The patch doesn't do anything with it, since the if-version of that code is not
an if-chain.

>> - -O2+: convert an if-chain only if:
>>         - the resulting switch will be converted into a bit-test and
>>         - there is a mispredict_cost >= n where:
>>           - mispredict_cost == BRANCH_COST (1, 0) - BRANCH_COST (1, 1) and
>>           - n is a pass parameter
> 
> That seems reasonable (but please if you use bool args to
> BRANCH_COST).

I've implemented this, apart from the pass parameter, I'm currently simply using
mispredict_cost > 0.

> You can also use predictable_edge_p and
> edge->probability to help decide whether or not to transform (without
> profile info, the branch probability is guessed using heuristics that
> do a reasonable job).
> 

Ported to trunk, bootstrapped and reg-tested on x86_64.

OK for stage1 trunk? Any further comments?

Thanks,
- Tom

> Ciao!
> Steven
> 

2012-01-24  Tom de Vries  <tom@codesourcery.com>

	* tree-if-switch-conversion.c: New pass.
	* tree-pass.h (pass_if_to_switch): Declare.
	* common.opt (ftree-if-to-switch-conversion): New switch.
	* opts.c (default_options_table): Set flag_tree_if_to_switch_conversion
	at -O2 and higher.
	* passes.c (init_optimization_passes): Use new pass.
	* doc/invoke.texi (-ftree-if-to-switch-conversion): New item.
	(Optimization Options, option -O2): Add -ftree-if-to-switch-conversion.
	* Makefile.in (OBJS): Add tree-if-switch-conversion.o.
	(tree-if-switch-conversion.o): New rule.
	* tree.h (expand_switch_using_bit_tests_p): Declare as extern.
	* tree-switch-conversion.c (expand_switch_using_bit_tests_p): Remove
	static from definition.

	* gcc.dg/if-to-switch.c: New test.
	* gcc.dg/if-to-switch.c-2: Same.
	* gcc.dg/if-to-switch.c-3: Same.
	* gcc.dg/tree-ssa/vrp33.c: Run with -fno-tree-if-to-switch-conversion.
	* gcc.dg/tree-ssa/vrp63.c: Same.
	* gcc.dg/tree-ssa/vrp64.c: Same.
	* gcc.dg/pr21643.c: Same.

Patch

Index: gcc/tree.h
===================================================================
--- gcc/tree.h	(revision 194077)
+++ gcc/tree.h	(working copy)
@@ -5616,6 +5616,10 @@ 
 extern void expand_stack_restore (tree);
 extern void expand_return (tree);
 
+/* In tree-switch-conversion.c  */
+
+extern bool expand_switch_using_bit_tests_p (tree, unsigned int, unsigned int);
+
 /* In tree-eh.c */
 extern void using_eh_for_cleanups (void);
 
Index: gcc/tree-pass.h
===================================================================
--- gcc/tree-pass.h	(revision 194077)
+++ gcc/tree-pass.h	(working copy)
@@ -489,6 +489,7 @@ 
 extern struct gimple_opt_pass pass_inline_parameters;
 extern struct gimple_opt_pass pass_update_address_taken;
 extern struct gimple_opt_pass pass_convert_switch;
+extern struct gimple_opt_pass pass_if_to_switch;
 
 /* The root of the compilation pass tree, once constructed.  */
 extern struct opt_pass *all_passes, *all_small_ipa_passes, *all_lowering_passes,
Index: gcc/tree-if-switch-conversion.c
===================================================================
--- gcc/tree-if-switch-conversion.c	(revision 0)
+++ gcc/tree-if-switch-conversion.c	(revision 0)
@@ -0,0 +1,1369 @@ 
+/* Convert a chain of if statements into a switch statement.
+   Copyright (C) 2010, 2011, 2012 Free Software Foundation, Inc.
+   Contributed by Tom de Vries <tom@codesourcery.com>
+
+This file is part of GCC.
+
+GCC is free software; you can redistribute it and/or modify it
+under the terms of the GNU General Public License as published by the
+Free Software Foundation; either version 3, or (at your option) any
+later version.
+
+GCC is distributed in the hope that it will be useful, but WITHOUT
+ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+for more details.
+
+You should have received a copy of the GNU General Public License
+along with GCC; see the file COPYING3.  If not see
+<http://www.gnu.org/licenses/>.  */
+
+/* The following pass converts a chain of ifs into a switch.
+
+   The if-chain has the following properties:
+   - all bbs end in a GIMPLE_COND.
+   - all but the first bb are empty, apart from the GIMPLE_COND.
+   - the GIMPLE_CONDs compare the same variable against integer constants.
+   - the true gotos all target the same bb.
+   - the false gotos target the next in the if-chain.
+
+   F.i., consider the following if-chain:
+   ...
+   <bb 4>:
+   ...
+   if (D.1993_3 == 32)
+     goto <bb 3>;
+   else
+     goto <bb 5>;
+
+   <bb 5>:
+   if (D.1993_3 == 13)
+     goto <bb 3>;
+   else
+     goto <bb 6>;
+
+   <bb 6>:
+   if (D.1993_3 == 10)
+     goto <bb 3>;
+   else
+     goto <bb 7>;
+
+   <bb 7>:
+   if (D.1993_3 == 9)
+     goto <bb 3>;
+   else
+     goto <bb 8>;
+   ...
+
+   The pass will report this if-chain like this:
+   ...
+   var: D.1993_3
+   first: <bb 4>
+   true: <bb 3>
+   last: <bb 7>
+   constants: 9 10 13 32
+   ...
+
+   and then convert the if-chain into a switch:
+   ...
+   <bb 4>:
+   ...
+   switch (D.1993_3) <default: <L8>,
+		      case 9: <L7>,
+		      case 10: <L7>,
+		      case 13: <L7>,
+		      case 32: <L7>>
+   ...
+
+   The pass will try to construct a chain for each bb, unless the bb it is
+   already contained in a chain.  This ensures that all chains will be found,
+   and that no chain will be constructed twice.
+
+   The pass detect range-checks in analyze_bb as well, and handles them.
+   Simple ones, like 'c <= 5', and more complex ones, like
+   '(unsigned char) c + 247 <= 1', which is generated by the C front-end from
+   code like '(c == 9 || c == 10)' or '(9 <= c && c <= 10)'.
+
+   The if-chain is conceptually similar to a 'reorderable sequence of range
+   conditions' as described in "Efficient and effective branch reordering using
+   profile data" (Yang et. al., 2002).
+   The difference is that for an if-chain the true gotos all target the same bb,
+   such that it is eligible for conversion into a single bit test.
+
+   A few known limitations of the pass:
+   - it does not analyze switch statements as part of an if-chain
+   - it does not analyze if-trees
+   - it does not create larger if-chains by moving a side-effects from a block
+     to it's successor blocks (See 'Making sequences reorderable' in the paper
+     mentioned above).  */
+
+#include "config.h"
+#include "system.h"
+#include "coretypes.h"
+
+#include "gimple.h"
+#include "gimple-pretty-print.h"
+#include "tree-flow.h"
+#include "tree-pass.h"
+#include "expr.h"
+
+/* Struct to describe a range [low, high].  */
+
+struct range_def
+{
+  tree high;
+  tree low;
+};
+typedef struct range_def *range;
+
+static struct obstack range_obstack;
+
+static range
+range_alloc (tree high, tree low)
+{
+  size_t obsize = sizeof (struct range_def);
+  range r = (range)obstack_alloc (&range_obstack, obsize);
+  r->high = high;
+  r->low = low;
+  return r;
+}
+
+/* Information we collect about a single bb.  */
+
+struct ifsc_info_def
+{
+  /* Variable that is tested to determine the control-flow.  */
+  tree var;
+  /* Ranges of constants the variable is compared to.  */
+  vec<range, va_gc> *ranges;
+  /* Successor edge of the bb if the comparison is successful.  */
+  edge true_edge;
+  /* Successor edge of the bb if the comparison is not successful.  */
+  edge false_edge;
+  /* Set if the all the operations in the bb are only used to determine the
+     control-flow.  */
+  bool empty;
+  /* Set if the bb is part of a chain.  */
+  bool chained;
+};
+typedef struct ifsc_info_def *ifsc_info;
+
+/* Macros to access the fields of struct ifsc_info.  */
+
+#define BB_IFSC_VAR(bb) (((ifsc_info)bb->aux)->var)
+#define BB_IFSC_RANGES(bb) (((ifsc_info)bb->aux)->ranges)
+#define BB_IFSC_TRUE_EDGE(bb) (((ifsc_info)bb->aux)->true_edge)
+#define BB_IFSC_FALSE_EDGE(bb) (((ifsc_info)bb->aux)->false_edge)
+#define BB_IFSC_EMPTY(bb) (((ifsc_info)bb->aux)->empty)
+#define BB_IFSC_CHAINED(bb) (((ifsc_info)bb->aux)->chained)
+
+/* Data-type describing an if-chain.  */
+
+struct if_chain_def
+{
+  /* First bb in the chain.  */
+  basic_block first;
+  /* Last bb in the chain.  */
+  basic_block last;
+  /* Variable that all bbs in the chain test to determine control-flow.  */
+  tree var;
+  /* Ranges of constants the variable is compared to.  */
+  vec<range, va_gc> *ranges;
+  /* Same as previous, but sorted and with duplicates removed.  */
+  vec<range, va_gc> *sorted_ranges;
+};
+typedef struct if_chain_def *if_chain;
+
+static struct obstack chain_obstack;
+
+/* Return allocated if_chain.  */
+
+static if_chain
+chain_alloc (void)
+{
+  size_t obsize = sizeof (struct if_chain_def);
+  if_chain chain = (if_chain)obstack_alloc (&range_obstack, obsize);
+  vec_alloc (chain->ranges, 8);
+  vec_alloc (chain->sorted_ranges, 8);
+  return chain;
+}
+
+/* Forward declarations.  */
+
+static void
+refine_ranges (basic_block, tree *, vec<range, va_gc> **, bool *,
+	       unsigned int *);
+
+/* Print RS to F.  */
+
+static void
+print_range_vector (FILE *f, vec<range, va_gc> *rs)
+{
+  unsigned int ix;
+  range r;
+
+  FOR_EACH_VEC_ELT (*rs, ix, r)
+    {
+      if (ix != 0)
+	fprintf (f, " ");
+      print_generic_expr (f, r->low, 0);
+      if (r->high)
+	{
+	  fprintf (f, "-");
+	  print_generic_expr (f, r->high, 0);
+	}
+    }
+  fprintf (f, "\n");
+}
+
+/* Add a range of [LOW, HIGH] to RS.  */
+
+static void
+push_range (vec<range, va_gc> **rs, tree high, tree low)
+{
+  range r = range_alloc (high, low);
+  vec_safe_push (*rs, r);
+}
+
+/* Helper function for sort_ranges.  */
+
+static int
+compare_ranges (const void *p1, const void *p2)
+{
+  const range r1 = *(const range *const)p1;
+  const range r2 = *(const range *const)p2;
+  bool r1_before_r2, r2_before_r1;
+  tree r1_high, r1_low, r2_high, r2_low;
+
+  r1_low = r1->low;
+  r2_low = r2->low;
+  r1_high = r1->high != NULL_TREE ? r1->high : r1_low;
+  r2_high = r2->high != NULL_TREE ? r2->high : r2_low;
+
+  r1_before_r2 = tree_int_cst_compare (r1_high, r2_low) < 0;
+  if (r1_before_r2)
+    return -1;
+
+  r2_before_r1 = tree_int_cst_compare (r2_high, r1_low) < 0;
+  if (r2_before_r1)
+    return 1;
+
+  return tree_int_cst_compare (r1_low, r2_low);
+}
+
+/* Return true if ranges R1 and R2 overlap.  */
+
+static bool
+range_overlap (range r1, range r2)
+{
+  tree r1_high, r1_low, r2_high, r2_low;
+  tree f;
+
+  r1_low = r1->low;
+  r2_low = r2->low;
+  r1_high = r1->high != NULL_TREE ? r1->high : r1_low;
+  r2_high = r2->high != NULL_TREE ? r2->high : r2_low;
+
+  /* r1 before r2.  */
+  f = fold_binary (LT_EXPR, boolean_type_node, r1_high, r2_low);
+  if (tree_int_cst_equal (f, integer_one_node))
+    return false;
+
+  /* r2 before r1.  */
+  f = fold_binary (LT_EXPR, boolean_type_node, r2_high, r1_low);
+  if (tree_int_cst_equal (f, integer_one_node))
+    return false;
+
+  return true;
+}
+
+/* Return true if R1 and R2 are adjacent ranges.  */
+
+static bool
+range_adjacent (range r1, range r2)
+{
+  tree r1_high, r1_low, r2_high, r2_low;
+  tree r1_high_plus_1, r2_high_plus_1;
+  tree type = TREE_TYPE (r1->low);
+
+  r1_low = r1->low;
+  r2_low = r2->low;
+  r1_high = r1->high != NULL_TREE ? r1->high : r1_low;
+  r2_high = r2->high != NULL_TREE ? r2->high : r2_low;
+
+  if (!tree_int_cst_equal (r1_high, TYPE_MAXVAL (type)))
+    {
+      r1_high_plus_1 = fold_binary (PLUS_EXPR, type, r1_high, integer_one_node);
+      if (tree_int_cst_equal (r1_high_plus_1, r2_low))
+	return true;
+    }
+
+  if (!tree_int_cst_equal (r2_high, TYPE_MAXVAL (type)))
+    {
+      r2_high_plus_1 = fold_binary (PLUS_EXPR, type, r2_high, integer_one_node);
+      if (tree_int_cst_equal (r2_high_plus_1, r1_low))
+	return true;
+    }
+
+  return false;
+}
+
+/* Return combined range if R1 and R2 overlap, otherwise return NULL.  */
+
+static range
+combine_ranges (range r1, range r2)
+{
+  tree low, high;
+  tree r1_high, r1_low, r2_high, r2_low;
+
+  if (!r1 || !r2
+      || (!range_overlap (r1, r2)
+	  && !range_adjacent (r1, r2)))
+    return NULL;
+
+  r1_low = r1->low;
+  r2_low = r2->low;
+  r1_high = r1->high != NULL_TREE ? r1->high : r1_low;
+  r2_high = r2->high != NULL_TREE ? r2->high : r2_low;
+
+  low = fold_binary (MIN_EXPR, TREE_TYPE (r1_low), r1_low, r2_low);
+  high = fold_binary (MAX_EXPR, TREE_TYPE (r1_high), r1_high, r2_high);
+
+  if (tree_int_cst_equal (low, high))
+    high = NULL_TREE;
+
+  return range_alloc (high, low);
+}
+
+/* Sort ranges in RANGES and copy to sorted_ranges, while combining overlapping
+   ranges.  */
+
+static void
+sort_ranges (vec<range, va_gc> *ranges, vec<range, va_gc> **sorted_ranges)
+{
+  unsigned int ix;
+  range prev = NULL, r;
+
+  /* Sort ranges.  */
+  ranges->qsort (compare_ranges);
+
+  FOR_EACH_VEC_ELT (*ranges, ix, r)
+    {
+      range m = combine_ranges (prev, r);
+      if (m)
+	{
+	  prev = m;
+	  continue;
+	}
+      if (prev)
+	vec_safe_push (*sorted_ranges, prev);
+      prev = r;
+    }
+  if (prev)
+    vec_safe_push (*sorted_ranges, prev);
+}
+
+/* Find the true and false edge of a GIMPLE_COND bb BB and return them in
+   TRUE_EDGE and FALSE_EDGE.  */
+
+static void
+get_edges (basic_block bb, edge *true_edge, edge *false_edge)
+{
+  edge e0, e1;
+  int e0_true;
+
+  e0 = EDGE_SUCC (bb, 0);
+  e1 = EDGE_SUCC (bb, 1);
+
+  e0_true = e0->flags & EDGE_TRUE_VALUE;
+
+  *true_edge = e0_true ? e0 : e1;
+  *false_edge = e0_true ? e1 : e0;
+}
+
+/* Attempt to express the comparison of VAR against range [LOW, HIGH] in terms
+   of another var, if the defining stmt of VAR is a cast, and return true
+   if successful.  Increment NR_STMTS with the number of stmts in BB that were
+   used to implement the comparison.  */
+
+static bool
+refine_range_cast (tree *var, tree high, tree low, unsigned int *nr_stmts)
+{
+  tree op1;
+  tree f1, f2;
+  gimple stmt = SSA_NAME_DEF_STMT (*var);
+
+  if (!is_gimple_assign (stmt)
+      || gimple_assign_rhs_code (stmt) != NOP_EXPR)
+    return false;
+
+  /* Gimple stmt is a signed to unsigned cast.  */
+  op1 = gimple_assign_rhs1 (stmt);
+  if (TREE_TYPE (*var) != unsigned_type_for (TREE_TYPE (op1)))
+    return false;
+
+  /* Test if the low-high range is representable in the signed type.  */
+  f1 = fold_binary (GE_EXPR, boolean_type_node, low, integer_zero_node);
+  if (!tree_int_cst_equal (f1, integer_one_node))
+    return false;
+  f2 = fold_binary (LE_EXPR, boolean_type_node, high ? high : low,
+		    TYPE_MAXVAL (TREE_TYPE (op1)));
+  if (!tree_int_cst_equal (f2, integer_one_node))
+    return false;
+
+  *var = op1;
+  (*nr_stmts)++;
+  return true;
+}
+
+/* Attempt to express the comparison of VAR against range [LOW, HIGH] in terms
+   of another var, if the defining stmt of VAR is a PLUS_EXPR, and return true
+   if successful.  Increment NR_STMTS with the number of stmts in BB that were
+   used to implement the comparison.  */
+
+static bool
+refine_range_plus (tree *var, tree *high, tree *low,
+		   unsigned int *nr_stmts)
+{
+  tree op1, op2, offset;
+  tree new_low, new_high, new_var, cmp;
+  gimple stmt = SSA_NAME_DEF_STMT (*var);
+
+  if (!stmt
+      || !is_gimple_assign (stmt)
+      || gimple_assign_rhs_code (stmt) != PLUS_EXPR
+      || !TYPE_OVERFLOW_WRAPS (TREE_TYPE (*var)))
+    return false;
+
+  op1 = gimple_assign_rhs1 (stmt);
+  op2 = gimple_assign_rhs2 (stmt);
+
+  if (!TREE_CONSTANT (op1)
+      && !TREE_CONSTANT (op2))
+    return false;
+
+  new_var = TREE_CONSTANT (op1) ? op2 : op1;
+  offset = TREE_CONSTANT (op1) ? op1 : op2;
+
+  /* Need integral switch var.  */
+  if (TREE_CODE (new_var) != SSA_NAME || !INTEGRAL_TYPE_P (TREE_TYPE (new_var)))
+    return false;
+
+
+  new_low = fold_binary (MINUS_EXPR, TREE_TYPE (new_var), *low, offset);
+  new_high = (*high == NULL_TREE
+	      ? NULL_TREE
+	      : fold_binary (MINUS_EXPR, TREE_TYPE (new_var), *high, offset));
+
+  cmp = fold_binary (LE_EXPR, TREE_TYPE (new_var), new_low, new_high);
+
+  if (!tree_int_cst_equal (cmp, integer_one_node))
+    {
+      /* Todo: Represent this as 2 ranges.  */
+      return false;
+    }
+
+  *high = new_high;
+  *low = new_low;
+  *var = new_var;
+
+  (*nr_stmts)++;
+  return true;
+}
+
+/* Analyze comparison STMT, and if successful, return true.  Returns in VAR the
+   comparison var, and in [LOW, HIGH] the comparison range.  Increment NR_STMTS
+   with the number of stmts in BB that were used to implement the
+   comparison.  */
+
+static bool
+get_constant_comparison (gimple stmt, tree *var, tree *high, tree *low,
+			 unsigned int *nr_stmts)
+{
+  tree op1, op2;
+  enum tree_code code;
+
+  if (!stmt || !is_gimple_assign (stmt))
+    return false;
+
+  code = gimple_assign_rhs_code (stmt);
+  switch (code)
+    {
+    case EQ_EXPR:
+    case LE_EXPR:
+    case GE_EXPR:
+      break;
+    case LT_EXPR:
+    case GT_EXPR:
+      /* Todo.  */
+      return false;
+    default:
+      return false;
+    }
+
+  *var = NULL_TREE;
+  *high = NULL_TREE;
+  *low = NULL_TREE;
+
+  op1 = gimple_assign_rhs1 (stmt);
+  op2 = gimple_assign_rhs2 (stmt);
+
+  if (!TREE_CONSTANT (op1)
+      && !TREE_CONSTANT (op2))
+    return false;
+
+  /* Normalize comparison into (var code constant).  */
+  *var = TREE_CONSTANT (op1) ? op2 : op1;
+  *low = TREE_CONSTANT (op1) ? op1 : op2;
+  code = TREE_CONSTANT (op1) ? swap_tree_comparison (code) : code;
+
+  /* Need integral switch var.  */
+  if (TREE_CODE (*var) != SSA_NAME || !INTEGRAL_TYPE_P (TREE_TYPE (*var)))
+    return false;
+
+  if (code == GE_EXPR)
+    *high = TYPE_MAXVAL (TREE_TYPE (*var));
+  else if (code == LE_EXPR)
+    {
+      *high = *low;
+      *low = TYPE_MINVAL (TREE_TYPE (*var));
+    }
+
+  (*nr_stmts)++;
+  return true;
+}
+
+/* Attempt to express the comparison of VAR against RANGES in terms of another
+   var, if the defining stmt of VAR is and BIT_IOR_EXPR, and return true if
+   successful.  Increment NR_STMTS with the number of stmts in BB that were used
+   to implement the comparison.  */
+
+static bool
+refine_range_bit_ior (tree *var, vec<range, va_gc> **ranges,
+		      unsigned int *nr_stmts)
+{
+  tree op1, op2;
+  tree op1_var, op2_var, op_const_high, op_const_low;
+  gimple op_def;
+  gimple stmt = SSA_NAME_DEF_STMT (*var);
+  basic_block bb;
+  vec<range, va_gc> *op_ranges1;
+  vec<range, va_gc> *op_ranges2;
+
+  if (!stmt
+      || !is_gimple_assign (stmt)
+      || gimple_assign_rhs_code (stmt) != BIT_IOR_EXPR)
+    return false;
+
+  bb = gimple_bb (stmt);
+
+  op1 = gimple_assign_rhs1 (stmt);
+  op2 = gimple_assign_rhs2 (stmt);
+
+  if (TREE_CODE (op1) != SSA_NAME
+      || TREE_CODE (op2) != SSA_NAME)
+    return false;
+
+  if (!has_single_use (op1) || !has_single_use (op2))
+    return false;
+
+  vec_alloc (op_ranges1, 1);
+  op_def = SSA_NAME_DEF_STMT (op1);
+  if (gimple_bb (stmt) == gimple_bb (op_def)
+      && get_constant_comparison (op_def, &op1_var, &op_const_high,
+				  &op_const_low, nr_stmts))
+    {
+      push_range (&op_ranges1, op_const_high, op_const_low);
+      refine_ranges (bb, &op1_var, &op_ranges1, NULL, nr_stmts);
+    }
+  else
+    return false;
+
+  vec_alloc (op_ranges2, 1);
+  op_def = SSA_NAME_DEF_STMT (op2);
+  if (gimple_bb (stmt) == gimple_bb (op_def)
+      && get_constant_comparison (op_def, &op2_var, &op_const_high,
+				  &op_const_low,nr_stmts))
+    {
+      push_range (&op_ranges2, op_const_high, op_const_low);
+      refine_ranges (bb, &op2_var, &op_ranges2, NULL, nr_stmts);
+      if (op1_var != op2_var)
+	return false;
+    }
+  else
+    return false;
+
+  *var = op1_var;
+  vec_safe_truncate (*ranges, 0);
+  vec_safe_splice (*ranges, op_ranges1);
+  vec_safe_splice (*ranges, op_ranges2);
+
+  (*nr_stmts)++;
+  return true;
+}
+
+/* Attempt to express the comparison of VAR against RANGES in terms of another
+   var, if the defining stmt of VAR is and BIT_AND_EXPR, and return true if
+   successful.  Increment NR_STMTS with the number of stmts in BB that were used
+   to implement the comparison.  */
+
+static bool
+refine_range_bit_and (tree *var, vec<range, va_gc> **ranges,
+		      unsigned int *nr_stmts)
+{
+  gimple stmt = SSA_NAME_DEF_STMT (*var);
+  tree new_var, cst;
+  tree op1, op2;
+  range r;
+  tree cst2, inv_mask;
+  unsigned int zero_bits;
+
+  if (!stmt
+      || !is_gimple_assign (stmt)
+      || gimple_assign_rhs_code (stmt) != BIT_AND_EXPR)
+    return false;
+
+  op1 = gimple_assign_rhs1 (stmt);
+  op2 = gimple_assign_rhs2 (stmt);
+
+  if (!TREE_CONSTANT (op1)
+      && !TREE_CONSTANT (op2))
+    return false;
+
+  new_var = TREE_CONSTANT (op1) ? op2 : op1;
+  cst = TREE_CONSTANT (op1) ? op1 : op2;
+
+  /* Need integral switch var.  */
+  if (TREE_CODE (new_var) != SSA_NAME || !INTEGRAL_TYPE_P (TREE_TYPE (new_var)))
+    return false;
+
+  zero_bits
+    = HOST_BITS_PER_DOUBLE_INT - tree_to_double_int (cst).popcount ();
+
+  if (zero_bits != 1)
+    return false;
+
+  if ((*ranges)->length ()  != 1)
+    return false;
+
+  r = (**ranges)[0];
+  if (r->high != NULL_TREE)
+    return false;
+
+  inv_mask = fold_unary (BIT_NOT_EXPR, TREE_TYPE (cst), cst);
+  cst2 = fold_binary (BIT_IOR_EXPR, TREE_TYPE (cst), r->low, inv_mask);
+
+  push_range (ranges, NULL_TREE, cst2);
+
+  *var = new_var;
+
+  (*nr_stmts)++;
+  return true;
+}
+
+/* Attempt to express the comparison of VAR against RANGES in BB
+   in terms of another var.  Invert swap_edges if that means reverting the
+   logic of the comparison, and increment NR_STMTS with the number of stmts in
+   BB that were used to implement the comparison.  */
+
+static void
+refine_ranges (basic_block bb, tree *var, vec<range, va_gc> **ranges,
+	       bool *swap_edges, unsigned int *nr_stmts)
+{
+  range r = NULL;
+  gimple stmt = SSA_NAME_DEF_STMT (*var);
+
+  if (!stmt || gimple_bb (stmt) != bb)
+    return;
+
+  if (!has_single_use (*var))
+    return;
+
+  if ((*ranges)->length ()  == 1)
+    {
+      r = (**ranges)[0];
+
+      if (refine_range_cast (var, r->high, r->low, nr_stmts))
+	{
+	  refine_ranges (bb, var, ranges, NULL, nr_stmts);
+	  return;
+	}
+
+      if (refine_range_plus (var, &r->high, &r->low, nr_stmts))
+	{
+	  refine_ranges (bb, var, ranges, NULL, nr_stmts);
+	  return;
+	}
+
+      if (r->high != NULL_TREE)
+	return;
+
+      if (tree_int_cst_equal (r->low, integer_zero_node)
+	  && refine_range_bit_ior (var, ranges, nr_stmts))
+	{
+	  *swap_edges = !*swap_edges;
+	  refine_ranges (bb, var, ranges, NULL, nr_stmts);
+	  return;
+	}
+
+      if (refine_range_bit_and (var, ranges, nr_stmts))
+	{
+	  refine_ranges (bb, var, ranges, NULL, nr_stmts);
+	  return;
+	}
+    }
+
+}
+
+/* Convert all trees in RANGES to TYPE.  */
+
+static bool
+convert_ranges (tree type, vec<range, va_gc> *ranges)
+{
+  unsigned int ix;
+  range r;
+
+  FOR_EACH_VEC_ELT (*ranges, ix, r)
+    {
+      r->low = fold_convert (type, r->low);
+      if (TREE_TYPE (r->low) != type)
+	return false;
+
+      if (r->high == NULL_TREE)
+	continue;
+
+      r->high = fold_convert (type, r->high);
+      if (TREE_TYPE (r->high) != type)
+	return false;
+    }
+
+  return true;
+}
+
+/* Return true if the amount of nondebug statements in BB is EXPECTED_NR.  */
+
+static bool
+nr_nondebug_stmts_equal_to (basic_block bb, unsigned int expected_nr)
+{
+  gimple_stmt_iterator gsi;
+  unsigned int nr = 0;
+
+  for (gsi = gsi_start_nondebug_bb (bb);
+       !gsi_end_p (gsi); gsi_next_nondebug (&gsi))
+    {
+      nr++;
+      if (nr > expected_nr)
+	return false;
+    }
+
+  return nr == expected_nr;
+}
+
+/* Analyze BB and store results in ifsc_info_def struct.  */
+
+static void
+analyze_bb (basic_block bb)
+{
+  gimple stmt = last_stmt (bb);
+  tree lhs, rhs, var, constant;
+  edge true_edge, false_edge;
+  enum tree_code cond_code;
+  vec<range, va_gc> *ranges;
+  unsigned int nr_stmts = 0;
+  bool swap_edges = false;
+  tree low, high;
+
+  /* We currently only handle bbs with GIMPLE_COND.  */
+  if (!stmt || gimple_code (stmt) != GIMPLE_COND)
+    return;
+
+  cond_code = gimple_cond_code (stmt);
+  switch (cond_code)
+    {
+    case EQ_EXPR:
+    case NE_EXPR:
+    case LE_EXPR:
+    case GE_EXPR:
+      break;
+    case LT_EXPR:
+    case GT_EXPR:
+      /* Todo.  */
+      return;
+    default:
+      return;
+    }
+
+  lhs = gimple_cond_lhs (stmt);
+  rhs = gimple_cond_rhs (stmt);
+
+  /* The comparison needs to be against a constant.  */
+  if (!TREE_CONSTANT (lhs)
+      && !TREE_CONSTANT (rhs))
+    return;
+
+  /* Normalize comparison into (var cond_code constant).  */
+  var = TREE_CONSTANT (lhs) ? rhs : lhs;
+  constant = TREE_CONSTANT (lhs) ? lhs : rhs;
+  cond_code = (TREE_CONSTANT (lhs)
+	       ? swap_tree_comparison (cond_code)
+	       : cond_code);
+
+  if (cond_code == NE_EXPR)
+    {
+      cond_code = EQ_EXPR;
+      swap_edges = true;
+    }
+
+  /* The switch var needs to be integral.  */
+  if (TREE_CODE (var) != SSA_NAME || !INTEGRAL_TYPE_P(TREE_TYPE (var)))
+    return;
+
+  switch (cond_code)
+    {
+    case GE_EXPR:
+      low = constant;
+      high = TYPE_MAXVAL (TREE_TYPE (var));
+      break;
+    case LE_EXPR:
+      low = TYPE_MINVAL (TREE_TYPE (var));
+      high = constant;
+      break;
+    case EQ_EXPR:
+      low = constant;
+      high = NULL_TREE;
+      break;
+    default:
+      gcc_unreachable ();
+    }
+
+  vec_alloc (ranges, 8);
+  push_range (&ranges, high, low);
+  refine_ranges (bb, &var, &ranges, &swap_edges, &nr_stmts);
+
+  /* Store analysis in ifsc_info_def struct.  */
+  BB_IFSC_VAR (bb) = var;
+  BB_IFSC_RANGES (bb) = ranges;
+  BB_IFSC_EMPTY (bb) = nr_nondebug_stmts_equal_to (bb, nr_stmts + 1);
+
+  get_edges (bb, &true_edge, &false_edge);
+  BB_IFSC_TRUE_EDGE (bb) = swap_edges ? false_edge : true_edge;
+  BB_IFSC_FALSE_EDGE (bb) = swap_edges ? true_edge: false_edge;
+
+  /* Bail out if verify_gimple_switch would fail.  */
+  if (!convert_ranges (TREE_TYPE (var), ranges))
+    BB_IFSC_VAR (bb) = NULL_TREE;
+}
+
+/* Return true if all the phis in the dest block of edges E1 and E2 have the
+   same values for the two edges.  */
+
+static bool
+same_phi_nodes_values (edge e1, edge e2)
+{
+  gimple_stmt_iterator gsi;
+  gcc_assert (e1->dest == e2->dest);
+
+  for (gsi = gsi_start_phis (e1->dest);
+       !gsi_end_p (gsi); gsi_next (&gsi))
+    {
+      gimple phi = gsi_stmt (gsi);
+      tree val1 = PHI_ARG_DEF_FROM_EDGE (phi, e1);
+      tree val2 = PHI_ARG_DEF_FROM_EDGE (phi, e2);
+      if (!operand_equal_for_phi_arg_p (val1, val2))
+	return false;
+    }
+  return true;
+}
+
+/* Returns true if BB cannot be chained to other bbs.  */
+
+static bool
+cannot_be_chained (basic_block bb)
+{
+  return (BB_IFSC_VAR (bb) == NULL_TREE
+	  || BB_IFSC_CHAINED (bb));
+}
+
+/* Returns true if BB can be a part of CHAIN.  */
+
+static bool
+bb_fits_in_chain (basic_block bb, if_chain chain)
+{
+  edge chain_true_edge = BB_IFSC_TRUE_EDGE (chain->first);
+  edge bb_true_edge = BB_IFSC_TRUE_EDGE (bb);
+
+  return (BB_IFSC_VAR (bb) == chain->var
+	  && bb_true_edge->dest == chain_true_edge->dest
+	  && same_phi_nodes_values (bb_true_edge, chain_true_edge));
+}
+
+/* Grow CHAIN forward.  */
+
+static void
+grow_if_chain_forward (if_chain chain)
+{
+  basic_block next_bb;
+
+  while (1)
+    {
+      next_bb = BB_IFSC_FALSE_EDGE (chain->last)->dest;
+
+      if (cannot_be_chained (next_bb))
+	break;
+
+      /* Each bb in the chain needs to be the only predecessor.  */
+      if (!single_pred_p (next_bb))
+	break;
+
+      if (!bb_fits_in_chain (next_bb, chain))
+	break;
+
+      /* We can only add empty bbs at the end of the chain.  */
+      if (!BB_IFSC_EMPTY (next_bb))
+	break;
+
+      /* Add next_bb at end of chain.  */
+      vec_safe_splice (chain->ranges, BB_IFSC_RANGES (next_bb));
+      BB_IFSC_CHAINED (next_bb) = true;
+      chain->last = next_bb;
+    }
+}
+
+/* Grow CHAIN backward.  */
+
+static void
+grow_if_chain_backward (if_chain chain)
+{
+  basic_block prev_bb;
+
+  while (1)
+    {
+      /* First bb is not empty, cannot grow backwards.  */
+      if (!BB_IFSC_EMPTY (chain->first))
+	break;
+
+      /* First bb has no single predecessor, cannot grow backwards.  */
+      if (!single_pred_p (chain->first))
+	break;
+
+      prev_bb = single_pred (chain->first);
+      if (cannot_be_chained (prev_bb)
+	  || !bb_fits_in_chain (prev_bb, chain))
+	break;
+
+      /* Add prev_bb at beginning of chain.  */
+      vec_safe_splice (chain->ranges, BB_IFSC_RANGES (prev_bb));
+      BB_IFSC_CHAINED (prev_bb) = true;
+      chain->first = prev_bb;
+    }
+}
+
+/* Seed chain with BB, try to grow it forward and backward and return it.  */
+
+static if_chain
+grow_if_chain (basic_block bb)
+{
+  if_chain chain = chain_alloc ();
+
+  /* Set bb as initial part of the chain.  */
+  vec_safe_splice (chain->ranges,  BB_IFSC_RANGES (bb));
+  chain->first = chain->last = bb;
+  chain->var = BB_IFSC_VAR (bb);
+
+  /* bb is part of a chain now.  */
+  BB_IFSC_CHAINED (bb) = true;
+
+  /* Grow chain to its maximum size.  */
+  grow_if_chain_forward (chain);
+  grow_if_chain_backward (chain);
+
+  /* Sort ranges and skip duplicates.  */
+  sort_ranges (chain->ranges, &chain->sorted_ranges);
+  return chain;
+}
+
+/* Dump CHAIN to dump_file.  */
+
+static void
+dump_if_chain (if_chain chain)
+{
+  edge true_edge = BB_IFSC_TRUE_EDGE (chain->first);
+
+  fprintf (dump_file, "var: ");
+  print_generic_expr (dump_file, chain->var, 0);
+  fprintf (dump_file, "\n");
+  fprintf (dump_file, "first: <bb %d>\n", chain->first->index);
+  fprintf (dump_file, "true: <bb %d>\n", true_edge->dest->index);
+  fprintf (dump_file, "last: <bb %d>\n",chain->last->index);
+
+  fprintf (dump_file, "ranges: ");
+  print_range_vector (dump_file, chain->ranges);
+
+  if (chain->sorted_ranges->length ()
+      != chain->ranges->length ())
+    {
+      fprintf (dump_file, "sorted_ranges: ");
+      print_range_vector (dump_file, chain->sorted_ranges);
+    }
+}
+
+/* Remove redundant bbs and edges after turning CHAIN into a switch statement.
+   Accumulate the probabilities on the path following the false edges in
+   FALSE_PROB.  */
+
+static void
+remove_redundant_bbs_and_edges (if_chain chain, int *false_prob)
+{
+  basic_block bb, next;
+  edge true_edge, false_edge;
+
+  for (bb = chain->first;; bb = next)
+    {
+      true_edge = BB_IFSC_TRUE_EDGE (bb);
+      false_edge = BB_IFSC_FALSE_EDGE (bb);
+
+      /* Determine next, before we delete false_edge.  */
+      next = false_edge->dest;
+
+      /* Accumulate probability.  */
+      *false_prob = (*false_prob * false_edge->probability) / REG_BR_PROB_BASE;
+
+      /* Don't remove the new true_edge.  */
+      if (bb != chain->first)
+	remove_edge (true_edge);
+
+      /* Don't remove the new false_edge.  */
+      if (bb != chain->last)
+	remove_edge (false_edge);
+
+      /* Don't remove the first bb.  */
+      if (bb != chain->first)
+	delete_basic_block (bb);
+
+      /* Stop after last.  */
+      if (bb == chain->last)
+	break;
+    }
+}
+
+/* Update the control flow graph after turning CHAIN into a switch
+   statement.  */
+
+static void
+update_cfg (if_chain chain)
+{
+  edge true_edge, false_edge;
+  int false_prob;
+  int flags_mask = ~(EDGE_FALLTHRU|EDGE_TRUE_VALUE|EDGE_FALSE_VALUE);
+
+  /* We keep these 2 edges, and remove the rest.  We need this specific
+     false_edge, because a phi in chain->last->dest might reference (the index
+     of) this edge.  For true_edge, we could pick any of them.  */
+  true_edge = BB_IFSC_TRUE_EDGE (chain->first);
+  false_edge = BB_IFSC_FALSE_EDGE (chain->last);
+
+  /* Update true edge.  */
+  true_edge->flags &= flags_mask;
+
+  /* Update false edge.  */
+  redirect_edge_pred (false_edge, chain->first);
+  false_edge->flags &= flags_mask;
+
+  false_prob = REG_BR_PROB_BASE;
+  remove_redundant_bbs_and_edges (chain, &false_prob);
+
+  /* Repair probabilities.  */
+  true_edge->probability = REG_BR_PROB_BASE - false_prob;
+  false_edge->probability = false_prob;
+}
+
+/* Create switch statement corresponding to CHAIN.  Borrows from
+   gimplify_switch_expr.  */
+
+static void
+convert_if_chain_to_switch (if_chain chain)
+{
+  tree label_decl_true, label_decl_false;
+  gimple label_true, label_false, gimple_switch;
+  gimple_stmt_iterator gsi;
+  tree default_case, other_case;
+  unsigned int ix;
+  vec<tree> labels;
+  range r;
+  edge true_edge = BB_IFSC_TRUE_EDGE (chain->first);
+
+  /* Create and insert true jump label.  */
+  label_decl_true = create_artificial_label (UNKNOWN_LOCATION);
+  label_true = gimple_build_label (label_decl_true);
+  gsi = gsi_start_bb (true_edge->dest);
+  gsi_insert_before (&gsi, label_true, GSI_SAME_STMT);
+
+  /* Create and insert false jump label.  */
+  label_decl_false = create_artificial_label (UNKNOWN_LOCATION);
+  label_false = gimple_build_label (label_decl_false);
+  gsi = gsi_start_bb (BB_IFSC_FALSE_EDGE (chain->last)->dest);
+  gsi_insert_before (&gsi, label_false, GSI_SAME_STMT);
+
+  /* Create default case label.  */
+  default_case = build4 (CASE_LABEL_EXPR, void_type_node,
+			 NULL_TREE, NULL_TREE,
+			 label_decl_false, NULL_TREE);
+
+  /* Create case labels.  */
+  labels.create (chain->sorted_ranges->length ());
+  FOR_EACH_VEC_ELT (*chain->sorted_ranges, ix, r)
+    {
+      other_case = build4 (CASE_LABEL_EXPR, void_type_node, r->low, r->high,
+			   label_decl_true, NULL_TREE);
+      labels.safe_push (other_case);
+    }
+
+  /* Create and insert switch.  */
+  gimple_switch = gimple_build_switch (chain->var, default_case, labels);
+  gsi = gsi_for_stmt (last_stmt (chain->first));
+  gsi_insert_before (&gsi, gimple_switch, GSI_SAME_STMT);
+
+  /* Remove now obsolete if.  */
+  gsi_remove (&gsi, true);
+
+  labels.release ();
+}
+
+/* Convert every if-chain in CHAINS into a switch statement.  */
+
+static void
+convert_chains (vec<if_chain> chains)
+{
+  unsigned int ix;
+  if_chain chain;
+
+  if (chains.is_empty ())
+    return;
+
+  FOR_EACH_VEC_ELT (chains, ix, chain)
+    {
+      if (dump_file)
+	dump_if_chain (chain);
+
+      convert_if_chain_to_switch (chain);
+
+      update_cfg (chain);
+    }
+
+  /* Force recalculation of dominance info.  */
+  free_dominance_info (CDI_DOMINATORS);
+  free_dominance_info (CDI_POST_DOMINATORS);
+}
+
+/* Allocate memory used by the pass.  */
+
+static void
+init_pass (void)
+{
+  size_t aux_size = sizeof (struct ifsc_info_def);
+  alloc_aux_for_blocks (aux_size);
+  gcc_obstack_init (&range_obstack);
+  gcc_obstack_init (&chain_obstack);
+}
+
+/* Deallocate memory used by the pass.  */
+
+static void
+finish_pass (void)
+{
+  free_aux_for_blocks ();
+  obstack_free (&range_obstack, NULL);
+  obstack_free (&chain_obstack, NULL);
+}
+
+/* For CHAIN, return in:
+   - RANGE the difference between highest and lowest case.
+   - UNIQ the number of unique case node targets, not counting the default case.
+   - COUNT the number of comparisons needed, not counting the default case.  */
+
+static void
+chain_get_switch_parameters (if_chain chain, tree *tree_range,
+			     unsigned int *uniq, unsigned int *count)
+{
+  range f = (*chain->sorted_ranges)[0];
+  range l = chain->sorted_ranges->last ();
+  tree high, low;
+  unsigned int i;
+  range r;
+
+  low = f->low;
+  high = l->high;
+  if (high == NULL_TREE)
+    high = l->low;
+
+  *tree_range = fold_binary (MINUS_EXPR, TREE_TYPE (low), high, low);
+
+  /* An if-chain has only 1 target.  */
+  *uniq = 1;
+
+  *count = 0;
+  FOR_EACH_VEC_ELT_REVERSE (*chain->sorted_ranges, i, r)
+    {
+      tree low, high;
+
+      low = r->low;
+      gcc_assert (low);
+      high = r->high;
+      gcc_assert (! high || tree_int_cst_lt (low, high));
+
+      /* Count the elements.
+	 A range counts double, since it requires two compares.  */
+      /* Todo: A range [type_min, a] or [b, type_max] should maybe count as
+	 one.  */
+      *count += 1;
+      if (high)
+	*count += 1;
+    }
+}
+
+/* Return the relative cost of mispredicting a branch.  */
+
+static int
+branch_mispredict_penalty (void)
+{
+  int well_predicted_branch_cost = BRANCH_COST (true, true);
+  int branch_cost = BRANCH_COST (true, false);
+  return branch_cost - well_predicted_branch_cost;
+}
+
+/* Return true if CHAIN should be converted into a switch statement.  If
+   CAN_EXPAND_AS_BIT_TEST, we can expand switches as bit test.  */
+
+static bool
+convert_if_chain_p (if_chain chain, bool can_expand_as_bit_test)
+{
+  tree tree_range;
+  unsigned int uniq;
+  unsigned int count;
+  bool expand_as_bit_test;
+  int bmp = branch_mispredict_penalty ();
+  int bmp_threshold = 1;
+
+  /* Avoid converting really small chains.  */
+  if (chain->first == chain->last
+      || chain->sorted_ranges->length () == 1)
+    return false;
+
+  chain_get_switch_parameters (chain, &tree_range, &uniq, &count);
+
+  expand_as_bit_test
+    = (can_expand_as_bit_test
+       ? expand_switch_using_bit_tests_p (tree_range, uniq, count)
+       : false);
+
+  if (optimize_function_for_speed_p (cfun))
+    {
+      if (expand_as_bit_test)
+	{
+	  /* We are limited here in our decision making by the absence of
+	     accurate profile info.  If we expand_as_bit_test it means
+	     we're before pass_convert_switch, which is before
+	     pass_ipa_tree_profile.  */
+
+	  if (bmp < bmp_threshold)
+	    {
+	      /* Converting the if-chain to a bit-test might slow the first jump
+		 of the chain down because the condition testing is more
+		 expensive.  So we only do this if we expect a benificial effect
+		 from an increased likelihood of the collapsed jump, in other
+		 words there's significant branch mispredict penalty.  */
+	      return false;
+	    }
+
+	  return true;
+	}
+
+      /* By converting an if-chain into a switch, and later into a decision
+	 tree, we effectively reorder the branches.  We shouldn't reorder
+	 without using profile info.
+	 And if we don't convert into a decision tree it'll be a table jump
+	 which is generally slow, so we take the conservative choice here.  */
+      return false;
+    }
+
+  /* We're not optimizing, bail out.  */
+  return false;
+}
+
+/* Find if-chains and convert them to switch statements.  If
+   CAN_EXPAND_AS_BIT_TEST, we can expand switches as bit test.  */
+
+static unsigned int
+find_and_convert_if_chains (bool can_expand_as_bit_test)
+{
+  basic_block bb;
+  if_chain chain;
+  vec<if_chain> chains;
+
+  chains.create (0);
+  init_pass ();
+
+  FOR_EACH_BB (bb)
+    analyze_bb (bb);
+
+  FOR_EACH_BB (bb)
+    {
+      if (cannot_be_chained (bb))
+	continue;
+
+      chain = grow_if_chain (bb);
+
+      if (!convert_if_chain_p (chain, can_expand_as_bit_test))
+	continue;
+
+      chains.safe_push (chain);
+    }
+
+  convert_chains (chains);
+
+  finish_pass ();
+  chains.release ();
+
+  return 0;
+}
+
+/* Find if-chains and convert them to switch statements, which may be
+   transformed into bit tests.  */
+
+static unsigned int
+if_to_switch (void)
+{
+  /* The argument should correspond to the location of the pass relative to
+     pass_convert_switch.  */
+  return find_and_convert_if_chains (true);
+}
+
+/* Returns true if the pass should be run.  */
+
+static bool
+if_to_switch_gate (void)
+{
+  return (flag_tree_if_to_switch_conversion
+	  && !profile_flag);
+}
+
+struct gimple_opt_pass pass_if_to_switch =
+{
+ {
+  GIMPLE_PASS,
+  "iftoswitch",                         /* name */
+  OPTGROUP_NONE,                        /* optinfo_flags */
+  if_to_switch_gate,                    /* gate */
+  if_to_switch,                         /* execute */
+  NULL,                                 /* sub */
+  NULL,                                 /* next */
+  0,                                    /* static_pass_number */
+  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_ggc_collect    /* todo_flags_finish */
+  | TODO_verify_ssa
+ }
+};
Index: gcc/opts.c
===================================================================
--- gcc/opts.c	(revision 194077)
+++ gcc/opts.c	(working copy)
@@ -473,6 +473,7 @@ 
     { OPT_LEVELS_2_PLUS, OPT_fstrict_overflow, NULL, 1 },
     { OPT_LEVELS_2_PLUS, OPT_freorder_blocks, NULL, 1 },
     { OPT_LEVELS_2_PLUS, OPT_freorder_functions, NULL, 1 },
+    { OPT_LEVELS_2_PLUS, OPT_ftree_if_to_switch_conversion, NULL, 1 },
     { OPT_LEVELS_2_PLUS, OPT_ftree_vrp, NULL, 1 },
     { OPT_LEVELS_2_PLUS, OPT_ftree_builtin_call_dce, NULL, 1 },
     { OPT_LEVELS_2_PLUS, OPT_ftree_pre, NULL, 1 },
Index: gcc/common.opt
===================================================================
--- gcc/common.opt	(revision 194077)
+++ gcc/common.opt	(working copy)
@@ -2023,6 +2023,10 @@ 
 Common Report Var(flag_tree_switch_conversion) Optimization
 Perform conversions of switch initializations.
 
+ftree-if-to-switch-conversion
+Common Report Var(flag_tree_if_to_switch_conversion) Optimization
+Perform conversions of chains of ifs into switches.
+
 ftree-dce
 Common Report Var(flag_tree_dce) Optimization
 Enable SSA dead code elimination optimization on trees
Index: gcc/Makefile.in
===================================================================
--- gcc/Makefile.in	(revision 194077)
+++ gcc/Makefile.in	(working copy)
@@ -1395,6 +1395,7 @@ 
 	tree-profile.o \
 	tree-scalar-evolution.o \
 	tree-sra.o \
+	tree-if-switch-conversion.o \
 	tree-switch-conversion.o \
 	tree-ssa-address.o \
 	tree-ssa-alias.o \
@@ -3029,6 +3030,9 @@ 
    $(IPA_PROP_H) $(DIAGNOSTIC_H) statistics.h \
    $(PARAMS_H) $(TARGET_H) $(FLAGS_H) \
    $(DBGCNT_H) $(TREE_INLINE_H) $(GIMPLE_PRETTY_PRINT_H)
+tree-if-switch-conversion.o : tree-if-switch-conversion.c $(CONFIG_H) \
+   $(SYSTEM_H) coretypes.h \
+   $(GIMPLE_H) $(GIMPLE_PRETTY_PRINT_H) $(TREE_FLOW_H) $(TREE_PASS_H)
 tree-switch-conversion.o : tree-switch-conversion.c $(CONFIG_H) $(SYSTEM_H) \
     $(TREE_H) $(TM_P_H) $(TREE_FLOW_H) $(DIAGNOSTIC_H) $(TREE_INLINE_H) \
     $(TM_H) coretypes.h $(GIMPLE_H) \
Index: gcc/tree-switch-conversion.c
===================================================================
--- gcc/tree-switch-conversion.c	(revision 194077)
+++ gcc/tree-switch-conversion.c	(working copy)
@@ -149,7 +149,7 @@ 
    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
+bool
 expand_switch_using_bit_tests_p (tree range,
 				 unsigned int uniq,
 				 unsigned int count)
Index: gcc/passes.c
===================================================================
--- gcc/passes.c	(revision 194077)
+++ gcc/passes.c	(working copy)
@@ -1336,6 +1336,7 @@ 
 	  NEXT_PASS (pass_cd_dce);
 	  NEXT_PASS (pass_early_ipa_sra);
 	  NEXT_PASS (pass_tail_recursion);
+	  NEXT_PASS (pass_if_to_switch);
 	  NEXT_PASS (pass_convert_switch);
           NEXT_PASS (pass_cleanup_eh);
           NEXT_PASS (pass_profile);
Index: gcc/doc/invoke.texi
===================================================================
--- gcc/doc/invoke.texi	(revision 194077)
+++ gcc/doc/invoke.texi	(working copy)
@@ -414,8 +414,8 @@ 
 -ftree-builtin-call-dce -ftree-ccp -ftree-ch @gol
 -ftree-coalesce-inline-vars -ftree-coalesce-vars -ftree-copy-prop @gol
 -ftree-copyrename -ftree-dce -ftree-dominator-opts -ftree-dse @gol
--ftree-forwprop -ftree-fre -ftree-loop-if-convert @gol
--ftree-loop-if-convert-stores -ftree-loop-im @gol
+-ftree-forwprop -ftree-fre -ftree-if-to-switch-conversion @gol
+-ftree-loop-if-convert -ftree-loop-if-convert-stores -ftree-loop-im @gol
 -ftree-phiprop -ftree-loop-distribution -ftree-loop-distribute-patterns @gol
 -ftree-loop-ivcanon -ftree-loop-linear -ftree-loop-optimize @gol
 -ftree-parallelize-loops=@var{n} -ftree-pre -ftree-partial-pre -ftree-pta @gol
@@ -6543,6 +6543,7 @@ 
 -fsched-interblock  -fsched-spec @gol
 -fschedule-insns  -fschedule-insns2 @gol
 -fstrict-aliasing -fstrict-overflow @gol
+-ftree-if-to-switch-conversion @gol
 -ftree-switch-conversion -ftree-tail-merge @gol
 -ftree-pre @gol
 -ftree-vrp}
@@ -7494,6 +7495,10 @@ 
 be limited using @option{max-tail-merge-comparisons} parameter and
 @option{max-tail-merge-iterations} parameter.
 
+@item -ftree-if-to-switch-conversion
+Perform conversion of chains of ifs into switches.  This flag is enabled by
+default at @option{-O2} and higher.
+
 @item -ftree-dce
 @opindex ftree-dce
 Perform dead code elimination (DCE) on trees.  This flag is enabled by
Index: gcc/testsuite/gcc.dg/if-to-switch-2.c
===================================================================
--- gcc/testsuite/gcc.dg/if-to-switch-2.c	(revision 0)
+++ gcc/testsuite/gcc.dg/if-to-switch-2.c	(revision 0)
@@ -0,0 +1,17 @@ 
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-iftoswitch" } */
+
+/* Example with (*src >= 9 && *src <= 10).  The front-end turns this into
+   (((unsigned char) *src) + 247) <= 1.  */
+
+const char *
+f (const char *src)
+{
+  while (*src == 13 || (*src >= 9 && *src <= 10) || *src == 32)
+    ++src;
+  return src;
+}
+
+/* { dg-final { scan-tree-dump-times "if \\(" 0 "iftoswitch"} } */
+/* { dg-final { scan-tree-dump-times "switch \\(" 1 "iftoswitch"} } */
+/* { dg-final { cleanup-tree-dump "iftoswitch" } } */
Index: gcc/testsuite/gcc.dg/if-to-switch-3.c
===================================================================
--- gcc/testsuite/gcc.dg/if-to-switch-3.c	(revision 0)
+++ gcc/testsuite/gcc.dg/if-to-switch-3.c	(revision 0)
@@ -0,0 +1,16 @@ 
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-iftoswitch" } */
+
+/* Contains duplicate test for 9.  */
+
+const char *
+f (const char *src)
+{
+  while (*src == 13 || (*src >= 9 && *src <= 10) || *src == 32 || *src == 9)
+    ++src;
+  return src;
+}
+
+/* { dg-final { scan-tree-dump-times "if \\(" 0 "iftoswitch"} } */
+/* { dg-final { scan-tree-dump-times "switch \\(" 1 "iftoswitch"} } */
+/* { dg-final { cleanup-tree-dump "iftoswitch" } } */
Index: gcc/testsuite/gcc.dg/if-to-switch.c
===================================================================
--- gcc/testsuite/gcc.dg/if-to-switch.c	(revision 0)
+++ gcc/testsuite/gcc.dg/if-to-switch.c	(revision 0)
@@ -0,0 +1,14 @@ 
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-iftoswitch" } */
+
+const char *
+f (const char *src)
+{
+  while (*src == 13 || *src == 9 || *src == 10 || *src == 32)
+    ++src;
+  return src;
+}
+
+/* { dg-final { scan-tree-dump-times "if \\(" 0 "iftoswitch"} } */
+/* { dg-final { scan-tree-dump-times "switch \\(" 1 "iftoswitch"} } */
+/* { dg-final { cleanup-tree-dump "iftoswitch" } } */
Index: gcc/testsuite/gcc.dg/tree-ssa/vrp63.c
===================================================================
--- gcc/testsuite/gcc.dg/tree-ssa/vrp63.c	(revision 194077)
+++ gcc/testsuite/gcc.dg/tree-ssa/vrp63.c	(working copy)
@@ -1,6 +1,6 @@ 
 /* PR tree-optimization/51721 */
 /* { dg-do link } */
-/* { dg-options "-O2" } */
+/* { dg-options "-O2 -fno-tree-if-to-switch-conversion" } */
 
 extern void link_error (void);
 
Index: gcc/testsuite/gcc.dg/tree-ssa/vrp64.c
===================================================================
--- gcc/testsuite/gcc.dg/tree-ssa/vrp64.c	(revision 194077)
+++ gcc/testsuite/gcc.dg/tree-ssa/vrp64.c	(working copy)
@@ -1,6 +1,6 @@ 
 /* PR tree-optimization/51721 */
 /* { dg-do link } */
-/* { dg-options "-O2" } */
+/* { dg-options "-O2 -fno-tree-if-to-switch-conversion" } */
 
 extern void link_error (void);
 
Index: gcc/testsuite/gcc.dg/tree-ssa/vrp33.c
===================================================================
--- gcc/testsuite/gcc.dg/tree-ssa/vrp33.c	(revision 194077)
+++ gcc/testsuite/gcc.dg/tree-ssa/vrp33.c	(working copy)
@@ -1,5 +1,5 @@ 
 /* { dg-do compile } */
-/* { dg-options "-O2 -fdump-tree-vrp1" } */
+/* { dg-options "-O2 -fdump-tree-vrp1 -fno-tree-if-to-switch-conversion" } */
 
 /* This is from PR14052.  */
 
Index: gcc/testsuite/gcc.dg/pr21643.c
===================================================================
--- gcc/testsuite/gcc.dg/pr21643.c	(revision 194077)
+++ gcc/testsuite/gcc.dg/pr21643.c	(working copy)
@@ -1,6 +1,6 @@ 
 /* PR tree-optimization/21643 */
 /* { dg-do compile } */
-/* { dg-options "-O2 -fdump-tree-reassoc1-details" } */
+/* { dg-options "-O2 -fdump-tree-reassoc1-details -fno-tree-if-to-switch-conversion" } */
 
 int
 f1 (unsigned char c)