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

sethml@ugcs.caltech.edu (Seth LaForge)
7 Dec 1997 22:05:31 -0500

          From comp.compilers

Related articles
[4 earlier articles]
Re: Help needed: Code generation for CASE/SWITCH statements dlmoore@ix.netcom.com (David L Moore) (1997-12-05)
Re: Help needed: Code generation for CASE/SWITCH statements drh@microsoft.com (Dave Hanson) (1997-12-05)
Re: Help needed: Code generation for CASE/SWITCH statements wilson@marker.cs.utah.edu (Wilson C Hsieh) (1997-12-05)
Re: Help needed: Code generation for CASE/SWITCH statements conway@mundook.cs.mu.OZ.AU (1997-12-05)
Re: Help needed: Code generation for CASE/SWITCH statements gclind01@spd.louisville.edu (1997-12-07)
Re: Help needed: Code generation for CASE/SWITCH statements wi534@victoria.tc.ca (William A. Barath) (1997-12-07)
Re: Help needed: Code generation for CASE/SWITCH statements sethml@ugcs.caltech.edu (1997-12-07)
Re: Help needed: Code generation for CASE/SWITCH statements henry@zoo.toronto.edu (Henry Spencer) (1997-12-10)
Re: Help needed: Code generation for CASE/SWITCH statements a_s_t_o_r@guardian.no (Alexander Kjeldaas) (1997-12-10)
Re: Help needed: Code generation for CASE/SWITCH statements vonbrand@inf.utfsm.cl (Horst von Brand) (1997-12-12)
Re: Help needed: Code generation for CASE/SWITCH statements wi534@victoria.tc.canada (William A. Barath) (1997-12-12)
Re: Help needed: Code generation for CASE/SWITCH statements henry@zoo.toronto.edu (Henry Spencer) (1997-12-15)
Re: Help needed: Code generation for CASE/SWITCH statements dietz@interaccess.com (Paul Dietz) (1997-12-16)
[3 later articles]
| List of all articles for this month |

From: sethml@ugcs.caltech.edu (Seth LaForge)
Newsgroups: comp.compilers,comp.lang.c.moderated
Date: 7 Dec 1997 22:05:31 -0500
Organization: California Institute of Technology, Pasadena
References: <clcm-19971204-0012@plethora.net>
Keywords: code, optimize

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
--


Post a followup to this message

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