On Thu, Jul 19, 2012 at 3:43 PM, Tom de Vries <tom_devr...@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
