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

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