diff mbox

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

Message ID 50054A9C.4030404@mentor.com
State New
Headers show

Commit Message

Tom de Vries July 17, 2012, 11:21 a.m. UTC 
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.

Comments

Steven Bosscher July 17, 2012, 12:57 p.m. UTC | #1 
On Tue, Jul 17, 2012 at 1:21 PM, Tom de Vries <Tom_deVries@mentor.com> wrote:
> Richard,
>
> attached patch implements an if-to-switch conversion tree pass
> pass_if_to_switch.

Nice. I've been working on something similar, using the paper
"Efficient and Effective Branch Reordering Using Profile Data" (Mingui
Yang et. al., see www.cs.fsu.edu/~whalley/papers/acmtoplas02.ps and
also mentioned in tree-switch-conversion.c). The if-to-switch
conversion falls out naturally from the algorithm proposed in that
paper. It also proposes basic block duplication to form longer chains
of if-chains to convert.

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 --
once upon a time it was a stated goal of tree-ssa to use algorithms
close to "literature algorithms". Your approach looks very similar:
smarter in some respects (the bit ranges stuff) and less sophisticated
in others (no block duplication).

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.

If the transformation is enabled with -fprofile-use, profile
information gets lost with this transformation, because you don't have
unique edges per condition anymore. This always hurts for the default
case, and may also hurt "normal" cases. The Yang paper describes a
value profiling method to record per-condition profile data, and I was
planning to implement that as well (and also the PGO switch lowering
that Freescale proposed at the GCC Summit 2006, see
http://gcc.gnu.org/ml/gcc-patches/2008-04/msg02120.html).

Perhaps you can have a look and see if there are some handles in the
above that you can work with :-)

Ciao!
Steven
Bernhard Reutner-Fischer July 18, 2012, 5:32 p.m. UTC | #2 
On Tue, Jul 17, 2012 at 01:21:00PM +0200, Tom de Vries wrote:

> /* 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)

>+/* 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)

low, not high? This is not immediately obvious to me, please explain?

>+	return false;
>+    }
>+
>+  return true;
>+}

>+/* 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;

missing space

[]
>+/* 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++)

shouldn't this be FOR_EACH_VEC_ELT nowadays? Everywhere.
>+    {
>+      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);
>+}

>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)

I think this list needs updating.

Nice to see if improvements, finally! :)
TIA && cheers,
Tom de Vries July 18, 2012, 9:30 p.m. UTC | #3 
Bernhard,

thanks for the review.

On 18/07/12 19:32, Bernhard Reutner-Fischer wrote:
> On Tue, Jul 17, 2012 at 01:21:00PM +0200, Tom de Vries wrote:
> 
>> /* 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)
> 
>> +/* 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)
> 
> low, not high? This is not immediately obvious to me, please explain?
> 

It's not obvious because it wrong, thanks for spotting that. This will be fixed
in the next submission.

>> +	return false;
>> +    }
>> +
>> +  return true;
>> +}
> 
>> +/* 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;
> 
> missing space
> 
> []

This will be fixed in the next submission.

>> +/* 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++)
> 
> shouldn't this be FOR_EACH_VEC_ELT nowadays? Everywhere.

Same.

>> +    {
>> +      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);
>> +}
> 
>> 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)
> 
> I think this list needs updating.
> 

I went over the list just now and all the elements appear in other makerules as
well, so I don't see any obvious ones that should be removed. I think the
PARAMS_H is not necessary. Do you have concerns about anything else?

Thanks,
- Tom

> Nice to see if improvements, finally! :)
> TIA && cheers,
>
Steven Bosscher July 18, 2012, 9:47 p.m. UTC | #4 
On Wed, Jul 18, 2012 at 11:30 PM, Tom de Vries <Tom_deVries@mentor.com> wrote:
>>> +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)
>>
>> I think this list needs updating.
>>
>
> I went over the list just now and all the elements appear in other makerules as
> well, so I don't see any obvious ones that should be removed. I think the
> PARAMS_H is not necessary. Do you have concerns about anything else?

Why would the other make rules matter? You're adding new make rules
for your new file. Make it depend only on what your new file needs.

Makefile.in is a mess. One of these days, someone (hi, Tromey) will
hopefully get annoyed enough with this again to finish some tool to
auto-generate the dependences list. Until that time, let's try to
avoid proliferating the messy rules from old files to new ones.

> +#include "config.h"
> +#include "system.h"
> +#include "coretypes.h"
> +#include "tm.h"

Dearohdearohdear. You're going to look at target macros in this pass?
Surely not. So, let's drop this header,

> +
> +#include "params.h"

-ENONEEDFORTHIS


> +#include "flags.h"

You get flags.h for free from tree.h, but...

> +#include "tree.h"
> +#include "basic-block.h"
> +#include "tree-ssa-operands.h"

You get these if you be a nice GIMPLE pass and include gimple.h
instead of these three headers.

> +#include "tree-flow.h"
> +#include "tree-flow-inline.h"

You don't need tree-flow-inline.h. tree-flow.h includes it already for you.


> +#include "diagnostic.h"

I don't think you're emitting diagnostics.
Except maybe: "warning: trying to out-smart developer if I do this
without profile info" :-)


> +#include "tree-pass.h"
> +#include "tree-dump.h"

You don't need tree-dump.h


> +#include "timevar.h"

You don't need timevar.h, either.


> +#include "tree-pretty-print.h"

You want gimple-pretty-print.h in a GIMPLE pass.

So you're left with:

+#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"

and

+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)

Looks a lot nicer to me.

Please do feel free to join my headless header-hunt and help clean up
all those other files that have needlessly complex #includes and
correspondingly silly Makefile.in rules!

Ciao!
Steven
Tom de Vries July 19, 2012, 12:42 p.m. UTC | #5 
On 18/07/12 23:47, Steven Bosscher wrote:
> On Wed, Jul 18, 2012 at 11:30 PM, Tom de Vries <Tom_deVries@mentor.com> wrote:
>>>> +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)
>>>
>>> I think this list needs updating.
>>>
>>
>> I went over the list just now and all the elements appear in other makerules as
>> well, so I don't see any obvious ones that should be removed. I think the
>> PARAMS_H is not necessary. Do you have concerns about anything else?
> 
> Why would the other make rules matter?

Steven,

Some header files are grouped into a macros like f.i. TREE_H. Something I saw
happening before was that a header file moved into such a macro, and my rule in
the patch was the only rule left using that header directly. I was referring to
this scenario.

> You're adding new make rules
> for your new file. Make it depend only on what your new file needs.
> 
> Makefile.in is a mess. One of these days, someone (hi, Tromey) will
> hopefully get annoyed enough with this again to finish some tool to
> auto-generate the dependences list. Until that time, let's try to
> avoid proliferating the messy rules from old files to new ones.
> 
>> +#include "config.h"
>> +#include "system.h"
>> +#include "coretypes.h"
>> +#include "tm.h"
> 
> Dearohdearohdear. You're going to look at target macros in this pass?
> Surely not. So, let's drop this header,
> 
>> +
>> +#include "params.h"
> 
> -ENONEEDFORTHIS
> 
> 
>> +#include "flags.h"
> 
> You get flags.h for free from tree.h, but...
> 
>> +#include "tree.h"
>> +#include "basic-block.h"
>> +#include "tree-ssa-operands.h"
> 
> You get these if you be a nice GIMPLE pass and include gimple.h
> instead of these three headers.
> 
>> +#include "tree-flow.h"
>> +#include "tree-flow-inline.h"
> 
> You don't need tree-flow-inline.h. tree-flow.h includes it already for you.
> 
> 
>> +#include "diagnostic.h"
> 
> I don't think you're emitting diagnostics.
> Except maybe: "warning: trying to out-smart developer if I do this
> without profile info" :-)
> 
> 
>> +#include "tree-pass.h"
>> +#include "tree-dump.h"
> 
> You don't need tree-dump.h
> 
> 
>> +#include "timevar.h"
> 
> You don't need timevar.h, either.
> 
> 
>> +#include "tree-pretty-print.h"
> 
> You want gimple-pretty-print.h in a GIMPLE pass.
> 
> So you're left with:
> 
> +#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"
> 
> and
> 
> +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)
> 
> Looks a lot nicer to me.
> 

Indeed :) , thanks a lot.

I'll clean this up for the next submission.

Thanks,
- Tom

> Please do feel free to join my headless header-hunt and help clean up
> all those other files that have needlessly complex #includes and
> correspondingly silly Makefile.in rules!
> 
> Ciao!
> Steven
>
Tom de Vries July 19, 2012, 1:43 p.m. UTC | #6 
On 17/07/12 14:57, Steven Bosscher wrote:
> On Tue, Jul 17, 2012 at 1:21 PM, Tom de Vries <Tom_deVries@mentor.com> wrote:
>> Richard,
>>
>> attached patch implements an if-to-switch conversion tree pass
>> pass_if_to_switch.
> 
> Nice. I've been working on something similar, using the paper
> "Efficient and Effective Branch Reordering Using Profile Data" (Mingui
> Yang et. al., see www.cs.fsu.edu/~whalley/papers/acmtoplas02.ps and
> also mentioned in tree-switch-conversion.c). The if-to-switch
> conversion falls out naturally from the algorithm proposed in that
> paper. It also proposes basic block duplication to form longer chains
> of if-chains to convert.
> 
> 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.

> once upon a time it was a stated goal of tree-ssa to use algorithms
> close to "literature algorithms". Your approach looks very similar:
> smarter in some respects (the bit ranges stuff) and less sophisticated
> in others (no block duplication).
> 
> 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, 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.

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
- -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
?

> If the transformation is enabled with -fprofile-use, profile
> information gets lost with this transformation, because you don't have
> unique edges per condition anymore. This always hurts for the default
> case, and may also hurt "normal" cases. The Yang paper describes a
> value profiling method to record per-condition profile data, and I was
> planning to implement that as well (and also the PGO switch lowering
> that Freescale proposed at the GCC Summit 2006, see
> http://gcc.gnu.org/ml/gcc-patches/2008-04/msg02120.html).
> 
> Perhaps you can have a look and see if there are some handles in the
> above that you can work with :-)
> 

Those are very useful pointers, thanks.

- Tom

> Ciao!
> Steven
>
Steven Bosscher July 19, 2012, 2:43 p.m. UTC | #7 
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.

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.

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.


> - -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). 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).

Ciao!
Steven
Tom Tromey July 19, 2012, 7:39 p.m. UTC | #8 
>>>>> "Steven" == Steven Bosscher <stevenb.gcc@gmail.com> writes:

Steven> Makefile.in is a mess. One of these days, someone (hi, Tromey) will
Steven> hopefully get annoyed enough with this again to finish some tool to
Steven> auto-generate the dependences list. Until that time, let's try to
Steven> avoid proliferating the messy rules from old files to new ones.

I'm hoping to talk Dodji into it ;-)

Seriously, I think the real problem is convincing oneself that the bug
in GNU make has been fixed.

Tom
Joseph Myers July 19, 2012, 10:58 p.m. UTC | #9 
On Thu, 19 Jul 2012, Tom Tromey wrote:

> >>>>> "Steven" == Steven Bosscher <stevenb.gcc@gmail.com> writes:
> 
> Steven> Makefile.in is a mess. One of these days, someone (hi, Tromey) will
> Steven> hopefully get annoyed enough with this again to finish some tool to
> Steven> auto-generate the dependences list. Until that time, let's try to
> Steven> avoid proliferating the messy rules from old files to new ones.
> 
> I'm hoping to talk Dodji into it ;-)
> 
> Seriously, I think the real problem is convincing oneself that the bug
> in GNU make has been fixed.

And I think we have no evidence that the bug was unavoidable by the patch 
in the first place - the patch made no changes relating to the GNU make 
feature supposedly required for the bug - see what I said in 
<http://gcc.gnu.org/ml/gcc-patches/2011-05/msg01925.html> about how to 
approach the change more incrementally, at least get the benefits of 
whatever changes don't trigger the bug, and if the bug does reappear then 
understand properly what is required to make it appear.
diff mbox

Patch

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.  */