gimple ssa: Teach switch conversion to optimize powers of 2 switches

Sometimes a switch has case numbers that are powers of 2.  Switch
conversion usually isn't able to optimize these switches.  This patch
adds "exponential index transformation" to switch conversion.  After
switch conversion applies this transformation on the switch the index
variable of the switch becomes the exponent instead of the whole value.
For example:

switch (i)
  {
    case (1 << 0): return 0;
    case (1 << 1): return 1;
    case (1 << 2): return 2;
    ...
    case (1 << 30): return 30;
    default: return 31;
  }

gets transformed roughly into

switch (log2(i))
  {
    case 0: return 0;
    case 1: return 1;
    case 2: return 2;
    ...
    case 30: return 30;
    default: return 31;
  }

This enables switch conversion to further optimize the switch.

This patch only enables this transformation if there are optabs for FFS
so that the base 2 logarithm can be computed efficiently at runtime.

gcc/ChangeLog:

	* tree-switch-conversion.cc (can_log2): New static function to
	check if gen_log2 can be used on current target.
	(gen_log2): New static function to generate efficient GIMPLE
	code for taking an exact base 2 log.
	(gen_pow2p): New static function to generate efficient GIMPLE
	code for checking if a value is a power of 2.
	(switch_conversion::switch_conversion): Track if the
	transformation happened.
	(switch_conversion::is_exp_index_transform_viable): New function
	to decide whether the transformation should be applied.
	(switch_conversion::exp_index_transform): New function to
	execute the transformation.
	(switch_conversion::gen_inbound_check): Don't remove the default
	BB if the transformation happened.
	(switch_conversion::expand): Execute the transform if it is
	viable.  Skip the "sufficiently small case range" test if the
	transformation is going to be executed.
	* tree-switch-conversion.h: Add is_exp_index_transform_viable
	and exp_index_transform.

gcc/testsuite/ChangeLog:

	* gcc.dg/tree-ssa/switch-3.c: Disable switch conversion.
	* gcc.target/i386/switch-exp-transform-1.c: New test.
	* gcc.target/i386/switch-exp-transform-2.c: New test.
	* gcc.target/i386/switch-exp-transform-3.c: New test.

Signed-off-by: Filip Kastl <fkastl@suse.cz>

0 files changed, 0 insertions, 0 deletions