[LLVMdev] Quirk in switch lowering

[Jasper Neumann]

Hello Anton,

>> 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 
http://ols.fedoraproject.org/GCC/Reprints-2008/sayle-reprint.pdf ("A 
Superoptimizer Analysis of Multiway Branch Code Generation" by Roger 
Anthony Sayle, 2008).

Best regards
Jasper Neumann