SUMMARY: Code Generation for Switch Statements

Here is the SUMMARY of responses to my post to comp.compilers about the
Code Generation problem of Case/Switch Statements:


----------------------------------------------------------------------
>From Dave Hanson:


@article{sale81,
author="Arthur Sale",
title="The Implementation of Case Statement in {P}ascal",
journal=SPE,
volume=11, number=9, month=sep, year=1981, pages="929-942"
}
@article{hennessy:mendelsohn:82,
author="John L. Hennessy and Noah Mendelsohn",
title="Compilation of the {P}ascal Case Statement",
journal=SPE,
volume=12, number=9, month=sep, year=1982, pages="879-882"
}
@article{bernstein85,
author="Robert L. Bernstein",
title="Producing Good Code for the Case Statement",
journal=SPE,
volume=15, number=10, month=oct, year=1985, pages="1021-1024"
}


lcc (our ANSI C compiler) implements something similar to what's described
in the bernstein paper. it generates a binary search of dense branch
tables, and the density can be specified.


----------------------------------------------------------------------


>From Jonathan Thornburg:


I have a book at home which describes the innards of the DEC VMS PL/I (and
later C) compiler. It talks a bit about this, basically they just set a
flag which triggers a 2nd scan over the entire source program. They say
they looked around at a bunch of other compilers and found either
(a) backpatching, which they considered "bad software aesthetics", or
(b) jumping around the jump table, which is inefficient.
[Probably Anklam et al., "Engineering a Compiler," Digital Press, 1982,
ISBN 0-932376-19-3.]


----------------------------------------------------------------------
>From Hank Dietz:


About 6-8 years ago, I implemented a little scheme that uses the lowest
execution time cost of several methods. The most sophisticated method
finds cheap nearly perfect hash functions so that an arbitrary switch can
be implemented using a reasonable-size jump table... but this isn't
always best, because using the jump table can take longer than doing just
a few simple comparisons.


There was a paper written then, but it never got published... interest
wasn't high then. ;-) If there's enough interest now, I'd be happy to
clean-up the paper and try again... I suppose I could at least make it
into a Purdue Tech Report.


BTW, the C and Pascal constructs are VERY different -- and I'm not just
talking about the fact that C cases can fall through. Pascal explicitly
states that values not listed cause undefined behavior, whereas C promises
that such values cause all cases to be skipped.
--

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