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

[Tom de Vries]

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.

-------------- next part --------------
A non-text attachment was scrubbed...
Name: tree-if-to-switch-conversion.patch
Type: text/x-patch
Size: 42880 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/gcc-patches/attachments/20120717/8bf28bed/attachment.bin>