public inbox for gcc-patches@gcc.gnu.org
 help / color / mirror / Atom feed
* [PATCH 1/2] if-to-switch conversion pass
@ 2012-07-17 11:21 Tom de Vries
  2012-07-17 11:25 ` [PATCH 2/2] if-to-switch conversion pass -- infrastructure Tom de Vries
                   ` (2 more replies)
  0 siblings, 3 replies; 14+ messages in thread
From: Tom de Vries @ 2012-07-17 11:21 UTC (permalink / raw)
  To: Richard Guenther; +Cc: gcc-patches, Jakub Jelinek, Steven Bosscher, Jan Hubicka

[-- Attachment #1: Type: text/plain, Size: 4063 bytes --]

Richard,

attached patch implements an if-to-switch conversion tree pass
pass_if_to_switch. I will follow up this email with an infrastructure patch that
provides double_int_popcount and popcount_hwi.

The pass detects chains of ifs like this:
...
   <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>;
...

and converts them into a switch statement:
...
   <bb 4>:
   ...
   switch (D.1993_3) <default: <L8>,
                      case 9: <L7>,
                      case 10: <L7>,
                      case 13: <L7>,
                      case 32: <L7>>
...

There are 2 motivations to convert chains of ifs to switches (as discussed in
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=46935 ):
- to reduce the control flow graph
- to take advantage of the efficient shift-and-bit-test implementations of
  switches

This pass takes the first approach as optimization measure, so it doesn't test
if the resulting switch can be converted into a shift-and-bit-test implementation.

pass_if_to_switch is on by default at O2 and higher, and controlled by
-ftree-if-to-switch-conversion.

The pass works as follows:
- it analyzes all bbs
- it forms if-chains out of bbs
- it transforms if-chains into switches

The pass is run twice, once before pass_convert_switch, and once after pass_pre.

By running it before pass_convert_switch, we take advantage of the
shift-and-bit-test implementation of switches (the conversion has recently been
moved from pass_expand to pass_convert_switch).

By running it after pass_pre, we take advantage of blocks collapsed by tail
merging, creating opportunities for if-to-switch conversion. Test-case
if-to-switch-5.c (the example from PR14799) is transformed into a switch by the
second run of the pass, not the first.

Perhaps instead of the second run of pass_if_to_switch, we could run tail-merge
(maybe without using gvn?) before the first run of pass_if_to_switch.  That
would also allow if-to-switch-5.c to be converted to a shift-and-bit-test.

For all the new test-cases, the if-chain is transformed into a switch by the
pass. For test-cases if-to-switch.c, if-to-switch-2.c and if-to-switch-4.c the
if-chains are subsequently transformed into shift-and-bit-tests.

The if-chain from the test-case if-to-switch-3.c (the example from PR46935) is
transformed into the following switch:
...
  switch (cD.1707_2(D))
  <default: <L9>,
   case 0 ... 32: <L8>, case 34: <L8>, case 39: <L8>, case 44: <L8>,
   case 46: <L8>, case 58: <L8>, case 59 ... 60: <L8>, case 62: <L8>,
   case 92: <L8>>
...
This switch is currently not transformed into a shift-and-bit-test since the
resulting range is too large, but the divide-and-conquer approach mentioned in
http://gcc.gnu.org/ml/gcc-patches/2012-06/msg01960.html could split off the
0..32 test and implement the rest as shift-and-bit-test.


Bootstrapped and reg-tested (Ada inclusive) on x86_64.

OK for trunk?

Thanks,
- Tom

2012-07-17  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.
	
	* 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/if-to-switch.c-4: Same.
	* gcc.dg/if-to-switch.c-5: 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.


[-- Attachment #2: tree-if-to-switch-conversion.patch --]
[-- Type: text/x-patch, Size: 42880 bytes --]

Index: gcc/tree-pass.h
===================================================================
--- gcc/tree-pass.h (revision 189508)
+++ gcc/tree-pass.h (working copy)
@@ -577,6 +577,7 @@ extern struct gimple_opt_pass pass_early
 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
===================================================================
--- /dev/null (new file)
+++ gcc/tree-if-switch-conversion.c (revision 0)
@@ -0,0 +1,1218 @@
+/* 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)'.  */
+
+#include "config.h"
+#include "system.h"
+#include "coretypes.h"
+#include "tm.h"
+
+#include "params.h"
+#include "flags.h"
+#include "tree.h"
+#include "basic-block.h"
+#include "tree-flow.h"
+#include "tree-flow-inline.h"
+#include "tree-ssa-operands.h"
+#include "diagnostic.h"
+#include "tree-pass.h"
+#include "tree-dump.h"
+#include "timevar.h"
+#include "tree-pretty-print.h"
+
+/* Struct to describe a range [low, high].  */
+
+struct range_def
+{
+  tree high;
+  tree low;
+};
+typedef struct range_def *range;
+
+DEF_VEC_P (range);
+DEF_VEC_ALLOC_P (range, gc);
+
+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, 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, gc) *ranges;
+  /* Same as previous, but sorted and with duplicates removed.  */
+  VEC (range, gc) *sorted_ranges;
+};
+typedef struct if_chain_def *if_chain;
+
+DEF_VEC_P (if_chain);
+DEF_VEC_ALLOC_P (if_chain, gc);
+
+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);
+  chain->ranges = VEC_alloc (range, gc, 8);
+  chain->sorted_ranges = VEC_alloc (range, gc, 8);
+  return chain;
+}
+
+/* Forward declarations.  */
+
+static void
+refine_ranges (basic_block, tree *, VEC (range, gc) **, bool *,
+	       unsigned int *);
+
+
+/* Dump RS to dump_file.  */
+
+static void
+dump_range_vector (VEC (range, gc) *rs)
+{
+  unsigned int ix;
+  range r;
+
+  for (ix = 0; VEC_iterate (range, rs, ix, r); ix++)
+    {
+      if (ix != 0)
+	fprintf (dump_file, " ");
+      print_generic_expr (dump_file, r->low, 0);
+      if (r->high)
+	{
+	  fprintf (dump_file, "-");
+	  print_generic_expr (dump_file, r->high, 0);
+	}
+    }
+  fprintf (dump_file, "\n");
+}
+
+/* Add a range of [LOW, HIGH] to RS.  */
+
+static void
+push_range (VEC (range, gc) **rs, tree high, tree low)
+{
+  range r = range_alloc (high, low);
+  VEC_safe_push (range, gc, *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 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))
+    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, gc) *ranges, VEC (range, gc) **sorted_ranges)
+{
+  size_t len = VEC_length (range, ranges);
+  unsigned int ix;
+  range prev = NULL, r;
+
+  /* Sort ranges.  */
+  qsort (VEC_address (range, ranges), len, sizeof (range),
+	 compare_ranges);
+
+  for (ix = 0; VEC_iterate (range, ranges, ix, r); ix++)
+    {
+      range m = combine_ranges (prev, r);
+      if (m)
+	{
+	  prev = m;
+	  continue;
+	}
+      if (prev)
+	VEC_safe_push (range, gc, *sorted_ranges, prev);
+      prev = r;
+    }
+  if (prev)
+    VEC_safe_push (range, gc, *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;
+  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));
+
+  *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, 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, gc) *op_ranges1 = NULL;
+  VEC (range, gc) *op_ranges2 = NULL;
+
+  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;
+
+  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;
+
+  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_truncate (range, *ranges, 0);
+  VEC_safe_splice (range, gc, *ranges, op_ranges1);
+  VEC_safe_splice (range, gc, *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, 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 - double_int_popcount (tree_to_double_int (cst));
+
+  if (zero_bits != 1)
+    return false;
+
+  if (VEC_length (range, *ranges)  != 1)
+    return false;
+
+  r = VEC_index (range, *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, 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 (VEC_length (range, *ranges)  == 1)
+    {
+      r = VEC_index (range, *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, gc) *ranges)
+{
+  unsigned int ix;
+  range r;
+
+  for (ix = 0; VEC_iterate (range, ranges, ix, r); ix++)
+    {
+      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->low) != type)
+	return false;
+    }
+
+  return true;
+}
+
+/* Return true if the amount of nondebug statments 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, gc) *ranges = NULL;
+  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 ();
+    }
+
+  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 (range, gc, 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 (range, gc, 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 (range, gc, 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: ");
+  dump_range_vector (chain->ranges);
+
+  if (VEC_length (range, chain->sorted_ranges)
+      != VEC_length (range, chain->ranges))
+    {
+      fprintf (dump_file, "sorted_ranges: ");
+      dump_range_vector (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, heap) *labels;
+  range r;
+  edge true_edge = BB_IFSC_TRUE_EDGE (chain->first);
+
+  labels = VEC_alloc (tree, heap, 8);
+
+  /* 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.  */
+  for (ix = 0; VEC_iterate (range, chain->sorted_ranges, ix, r); ix++)
+    {
+      other_case = build4 (CASE_LABEL_EXPR, void_type_node, r->low, r->high,
+			   label_decl_true, NULL_TREE);
+      VEC_safe_push (tree, heap, labels, other_case);
+    }
+
+  /* Create and insert switch.  */
+  gimple_switch = gimple_build_switch_vec (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);
+
+  VEC_free (tree, heap, labels);
+}
+
+/* Convert every if-chain in CHAINS into a switch statement.  */
+
+static void
+convert_chains (VEC (if_chain, gc) *chains)
+{
+  unsigned int ix;
+  if_chain chain;
+
+  if (VEC_empty (if_chain, chains))
+    return;
+
+  for (ix = 0; VEC_iterate (if_chain, chains, ix, chain); ix++)
+    {
+      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);
+}
+
+/* Return true if CHAIN should be transformed into a switch statement.  */
+
+static bool
+transform_if_chain_p (if_chain chain)
+{
+  /* Don't transform if the cfg doesn't get reduced.  */
+  if (chain->first == chain->last)
+    return false;
+
+  /* It should be possible to represent a single range by an if statement.  */
+  if (VEC_length (range, chain->sorted_ranges) == 1)
+    return false;
+
+  return true;
+}
+
+/* Find if-chains and convert them to switch statements.  */
+
+static unsigned int
+do_if_to_switch (void)
+{
+  basic_block bb;
+  if_chain chain;
+  VEC (if_chain, gc) *chains = NULL;
+
+  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 (!transform_if_chain_p (chain))
+	continue;
+
+      VEC_safe_push (if_chain, gc, chains, chain);
+    }
+
+  convert_chains (chains);
+
+  finish_pass ();
+
+  return 0;
+}
+
+/* Returns true if the pass should be run.  */
+
+static bool
+if_to_switch_gate (void)
+{
+  return flag_tree_if_to_switch_conversion;
+}
+
+/* The pass definition.  */
+
+struct gimple_opt_pass pass_if_to_switch =
+{
+ {
+  GIMPLE_PASS,
+  "iftoswitch",                         /* name */
+  if_to_switch_gate,                    /* gate */
+  do_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_verify_ssa  /* todo_flags_finish */
+ }
+};
Index: gcc/opts.c
===================================================================
--- gcc/opts.c (revision 189508)
+++ gcc/opts.c (working copy)
@@ -476,6 +476,7 @@ static const struct default_options defa
     { 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 189508)
+++ gcc/common.opt (working copy)
@@ -1996,6 +1996,10 @@ ftree-switch-conversion
 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 189508)
+++ gcc/Makefile.in (working copy)
@@ -1391,6 +1391,7 @@ OBJS = \
 	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 \
@@ -3013,7 +3014,12 @@ tree-sra.o : tree-sra.c $(CONFIG_H) $(SY
    $(IPA_PROP_H) $(DIAGNOSTIC_H) statistics.h $(TREE_DUMP_H) $(TIMEVAR_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) $(TREE_H) $(TM_P_H) $(TREE_FLOW_H) $(DIAGNOSTIC_H) \
+    $(TREE_INLINE_H) $(TIMEVAR_H) $(TM_H) coretypes.h $(TREE_DUMP_H) \
+    $(GIMPLE_H) $(TREE_PASS_H) $(FLAGS_H) $(EXPR_H) $(BASIC_BLOCK_H) output.h \
+    $(GGC_H) $(OBSTACK_H) $(PARAMS_H) $(CPPLIB_H) $(PARAMS_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) \
     $(TIMEVAR_H) $(TM_H) coretypes.h $(TREE_DUMP_H) $(GIMPLE_H) \
 /* Compute the absolute value of X.  */
Index: gcc/passes.c
===================================================================
--- gcc/passes.c (revision 189508)
+++ gcc/passes.c (working copy)
@@ -1312,6 +1312,7 @@ init_optimization_passes (void)
 	  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);
@@ -1421,6 +1422,7 @@ init_optimization_passes (void)
       NEXT_PASS (pass_optimize_bswap);
       NEXT_PASS (pass_split_crit_edges);
       NEXT_PASS (pass_pre);
+      NEXT_PASS (pass_if_to_switch);
       NEXT_PASS (pass_sink_code);
       NEXT_PASS (pass_tree_loop);
 	{
Index: gcc/doc/invoke.texi
===================================================================
--- gcc/doc/invoke.texi (revision 189508)
+++ gcc/doc/invoke.texi (working copy)
@@ -408,8 +408,8 @@ Objective-C and Objective-C++ Dialects}.
 -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
@@ -6298,6 +6298,7 @@ also turns on the following optimization
 -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}
@@ -7224,6 +7225,10 @@ in this pass can
 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
===================================================================
--- /dev/null (new file)
+++ gcc/testsuite/gcc.dg/if-to-switch-2.c (revision 0)
@@ -0,0 +1,17 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-iftoswitch1" } */
+
+/* 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 "iftoswitch1"} } */
+/* { dg-final { scan-tree-dump-times "switch \\(" 1 "iftoswitch1"} } */
+/* { dg-final { cleanup-tree-dump "iftoswitch1" } } */
Index: gcc/testsuite/gcc.dg/if-to-switch-3.c
===================================================================
--- /dev/null (new file)
+++ gcc/testsuite/gcc.dg/if-to-switch-3.c (revision 0)
@@ -0,0 +1,16 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-iftoswitch1" } */
+
+/* Example from PR 46935.  */
+
+int crud (unsigned char c)
+{
+  return (((((((((((int) c <= 32 || (int) c == 46) || (int) c == 44)
+         || (int) c == 58) || (int) c == 59) || (int) c == 60)
+          || (int) c == 62) || (int) c == 34) || (int) c == 92)
+       || (int) c == 39) != 0);
+}
+
+/* { dg-final { scan-tree-dump-times "if \\(" 0 "iftoswitch1"} } */
+/* { dg-final { scan-tree-dump-times "switch \\(" 1 "iftoswitch1"} } */
+/* { dg-final { cleanup-tree-dump "iftoswitch1" } } */
Index: gcc/testsuite/gcc.dg/if-to-switch-4.c
===================================================================
--- /dev/null (new file)
+++ gcc/testsuite/gcc.dg/if-to-switch-4.c (revision 0)
@@ -0,0 +1,16 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-iftoswitch1" } */
+
+/* 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 "iftoswitch1"} } */
+/* { dg-final { scan-tree-dump-times "switch \\(" 1 "iftoswitch1"} } */
+/* { dg-final { cleanup-tree-dump "iftoswitch1" } } */
Index: gcc/testsuite/gcc.dg/if-to-switch-5.c
===================================================================
--- /dev/null (new file)
+++ gcc/testsuite/gcc.dg/if-to-switch-5.c (revision 0)
@@ -0,0 +1,25 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-iftoswitch2" } */
+
+/* This is the example from PR14799.  This example is handled by the second
+   if-to-switch pass.  Only after pre are the different blocks with the call to
+   bar collapsed, and then if-to-switch conversion can do it's work.  */
+
+void bar (void);
+
+void
+foo (int a)
+{
+  if (a == 30)
+    bar ();
+  else if (a == 31)
+    bar ();
+  else if (a == 53)
+    bar ();
+  else if (a == 23)
+    bar ();
+}
+
+/* { dg-final { scan-tree-dump-times "if \\(" 0 "iftoswitch2"} } */
+/* { dg-final { scan-tree-dump-times "switch \\(" 1 "iftoswitch2"} } */
+/* { dg-final { cleanup-tree-dump "iftoswitch2" } } */
Index: gcc/testsuite/gcc.dg/if-to-switch.c
===================================================================
--- /dev/null (new file)
+++ gcc/testsuite/gcc.dg/if-to-switch.c (revision 0)
@@ -0,0 +1,14 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-iftoswitch1" } */
+
+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 "iftoswitch1"} } */
+/* { dg-final { scan-tree-dump-times "switch \\(" 1 "iftoswitch1"} } */
+/* { dg-final { cleanup-tree-dump "iftoswitch1" } } */
Index: gcc/testsuite/gcc.dg/tree-ssa/vrp63.c
===================================================================
--- gcc/testsuite/gcc.dg/tree-ssa/vrp63.c (revision 189508)
+++ 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 189508)
+++ 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 189508)
+++ 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.  */
 

^ permalink raw reply	[flat|nested] 14+ messages in thread
end of thread, other threads:[~2013-01-24 18:10 UTC | newest]

Thread overview: 14+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2012-07-17 11:21 [PATCH 1/2] if-to-switch conversion pass Tom de Vries
2012-07-17 11:25 ` [PATCH 2/2] if-to-switch conversion pass -- infrastructure Tom de Vries
2012-07-17 11:30   ` Richard Guenther
2012-07-17 13:55     ` Tom de Vries
2012-07-17 12:58 ` [PATCH 1/2] if-to-switch conversion pass Steven Bosscher
2012-07-19 13:43   ` Tom de Vries
2012-07-19 14:43     ` Steven Bosscher
2013-01-24 18:10       ` Tom de Vries
2012-07-18 17:32 ` Bernhard Reutner-Fischer
2012-07-18 21:30   ` Tom de Vries
2012-07-18 21:47     ` Steven Bosscher
2012-07-19 12:43       ` Tom de Vries
2012-07-19 19:40       ` Tom Tromey
2012-07-19 22:58         ` Joseph S. Myers

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).