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

On 4 Dec 1997 15:04:27 GMT, jakob@iar_.se (Jakob) wrote:


>I have a number of different tactics for implementing a switch (among
>them a simple jump table and a series of conditional branches), and
>would like the compiler to make a semi-intelligent decision as to
>which to use for a particular switch.


The straightforward way goes something like this. There are two
dimensions of interest: the number of cases, and the density of the
case values. Below a certain number of cases you will generate a
series of conditional branches every time - that number might be, say,
three or four. Above that you look at the cases themselves. What I
do is to measure how many of the values between the lowest value and
the highest value are specified, and divide it by the total number of
cases. That gives me a case "density" which I can use to decide among
different table techniques. If the cases are dense enough, then I
generate a table that has all the cases values between low and high,
and binary-search it at runtime. If they aren't dense enough, then I
scan the table front to back, stopping when a value is encountered
that is higher than my selector value. There are other techniques, of
course, but these three provide reasonable efficiency for the usual
programs. Two parameters are required: the conditional- branch
threshhold, and the case density below which the binary table is
abandoned in favor of the scanning table. I put these in a compiler
control file that is read in at the beginning of each compilation,
along with other similar things, so that it can be tweaked, maybe even
by the advanced user.


Hope this helps.


Dwight
--

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