[LLVMdev] Quirk in switch lowering
jasper.neumann at web.de
Sat Jan 11 14:48:23 PST 2014
>> I'm currently working on switch lowering using hashing which can fully
>> replace the jump table method. It works quite good by now but I will have to
>> prepare a ton of documentation and test stuff. Some of the remaining
>> problems can easily be solved later.
> Is it somehow similar to MRST (multi-way radix search trees) technique?
Well, yes and no. The idea is to catch all switch labels with a single
perfect hash function which transforms the label values into a small
range of numbers. One test follows and thereafter we can dispatch with a
jump table. This is especially effective if the switch labels are
sparse. The normal jump table approach is a special case thereof.
The MRST technique can be seen as an imperfect hashing approach.
Larger ranges ought to be treated later by MRST or a decision tree;
unfortunately I could not yet get this running.
A detailed discussion can be found in
Superoptimizer Analysis of Multiway Branch Code Generation" by Roger
Anthony Sayle, 2008).
More information about the llvm-dev