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


[sethml@ugcs.caltech.edu (Seth LaForge)]
| | 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 have never worked on this problem, but maybe it's possible to do a
simple compiler-calculated good hash of the value. Then you would get
one jump-table, and one or more tests in each node. The advantage
would be that the jump-table would be compact and that the tests would
be correctly predicted in almost 100% of the cases. Maybe you would
get code bloat though.


Maybe this was a lucky shot, but your number series with the simple
hash function x = x & 0xf actually hashes the 12 numbers with only one
collision.


On IA-64 it could be interesting to look at the size of the code in
the nodes of the swith statement. If they are short, some of them
could be combined using predication. If some are short and some are
long, some hash-wizard could make a hash that reorders the sections to
facilitate predication on consecutive short code sections. Other
reasons to reorder would be cache-effects.


Speaking of cache effects. Has anybody tried to "inline" the code in
the jump-table? What I mean is that if the total size of the
code-segments in the nodes of the switch is N bytes and there are n
entries in the jump-table, put the entry to each code section N/n
bytes apart and combine "empty" slots using absolute branches. On many
architectures absolute branches are free, especially when they occur
at the end of an "instruction decode unit". The variable used to index
a normal jump-table would have to be multiplied with N/n of
course. The idea is to better exploit the cache-line you already
access when you index the jumptable. I've done this in assembly on a
few occasions. You could to partial inlining and all kinds of
combinations in between.


astor
--
  Alexander Kjeldaas, Guardian Networks AS, Trondheim, Norway
  http://www.guardian.no/
--

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