Re: Help needed: Code generation for CASE/SWITCH statements

On 4 Dec 1997 15:04:27 GMT, Jakob <jakob@iar_.se> wrote:
>I would like to know if anybody knows of any references (articles,
>books, online sources) where information can be found about how to
>select implementation strategies for switch statements (case for Ada
>and Pascal).


I worked on exactly this problem at Green Hills last year. The
problem is quite complicated in the general cases, since just
selecting among a set of strategies is not enough. You may need to
combine strategies to get a good solution - for example, a switch
which selects on 3,4,6,7,8,123,653,789,1005,1006,1007,1008 is probably
best implemented with two jump tables and a linear search (i.e. a
sequence of compares) with a binary search to figure out which to use.
Exactly how to split things up can depend on the speed and size of the
instruction sequences involved, as well.


I ended up implementing an N^3 algorithm (where N == # of arms) which
finds an optimal partitioning and algorithm assumptions (given various
assumptions about instruction timing/size), and a statistical order N
algorithm which finds nearly-optimal solutions. Which algorithm was
used depended on number of arms - the N^3 alg was faster for about <64
arms.


Combined with some other improvements (on the code-gen side of
things), this produced a 10-25% improvement in our benchmark: all of
the switch statements extracted from SpecInt95, exercised heavily. Of
course, this benchmark didn't execute much code other than the
switches, but it still made me pretty happy.


Has anyone heard of switch optimization to this extent? I don't have
'Producing Good Code for the Case Statement' so I don't know what that
covers. If not, I may write up a paper on the details.


Seth
--

Return to the comp.compilers page.
Search the comp.compilers archives again.