Home
Reading
Searching
Subscribe
Sponsors
Statistics
Posting
Contact
Spam
Lists
Links
About
Hosting
Filtering
Features Download
Marketing
Archives
FAQ
Blog
 
Gmane
From: Jasper Neumann <jasper.neumann <at> web.de>
Subject: Re: Quirk in switch lowering
Newsgroups: gmane.comp.compilers.llvm.devel
Date: Saturday 11th January 2014 22:48:23 UTC (over 3 years ago)
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
 
CD: 2ms