On 17/07/12 14:57, Steven Bosscher wrote:
> On Tue, Jul 17, 2012 at 1:21 PM, Tom de Vries <tom_devr...@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
>
