switch statement generation

dgaudet@undergrad.math.uwaterloo.ca (Dean Gaudet)
Wed, 6 Apr 1994 14:18:10 GMT

          From comp.compilers

Related articles
switch statement generation dgaudet@undergrad.math.uwaterloo.ca (1994-04-06)
Re: switch statement generation mps@dent.uchicago.edu (1994-04-07)
switch statement generation dgaudet@undergrad.math.uwaterloo.ca (1994-04-07)
Re: switch generation and exceptions nandu@cs.clemson.edu (1994-04-09)
Re: switch statement generation henry@zoo.toronto.edu (1994-04-10)
Re: switch statement generation ch+@cs.cmu.edu (1994-04-11)
Re: switch statement generation ok@cs.rmit.oz.au (1994-04-13)
[2 later articles]
| List of all articles for this month |

Newsgroups: comp.compilers
From: dgaudet@undergrad.math.uwaterloo.ca (Dean Gaudet)
Keywords: code, optimize
Organization: University of Waterloo
Date: Wed, 6 Apr 1994 14:18:10 GMT

A few years back I came up with a method of encoding switch statements
using binary search that doesn't involve many branches. There is a branch
for equality, but no branch for above and below comparisons. It's based
on Knuth _Art of Programming_ V3, 6.2.1, problem 24. I originally did it
for the 386, but I'm sure it can be adapted to other processors.

The raw cycle counts on a 386 seemed to favour it over full inline binary
searches, but since my method is table driven there are cache issues to
worry about. It can also be adapted to a roughly 24-byte loop to do
binary search, comparable to the 18-byte loop required for a linear search
through a table.

Since I don't seem to be finding the time/effort to do anything with it, I
figured I'd toss it out to the net.community. If you're interested send
me email. (I haven't even looked around to see if anyone else has already
used this technique :)


Post a followup to this message

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