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

[Tom de Vries]

Steven,

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

Done.

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

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

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

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

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

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

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

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

OK for stage1 trunk? Any further comments?

Thanks,
- Tom

> Ciao!
> Steven
> 

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

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

	* gcc.dg/if-to-switch.c: New test.
	* gcc.dg/if-to-switch.c-2: Same.
	* gcc.dg/if-to-switch.c-3: Same.
	* gcc.dg/tree-ssa/vrp33.c: Run with -fno-tree-if-to-switch-conversion.
	* gcc.dg/tree-ssa/vrp63.c: Same.
	* gcc.dg/tree-ssa/vrp64.c: Same.
	* gcc.dg/pr21643.c: Same.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: tree-if-to-switch-conversion-simple-heuristic.patch
Type: text/x-patch
Size: 46460 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/gcc-patches/attachments/20130124/9f748c31/attachment.bin>