Re: Switch statement code generation

Joshua Cranmer <Pidgeot18@verizon.invalid> wrote:
> I'm trying to put together a list of various methods to do code generate
> for switch statements.


> This is what I have so far:
> * Successive if/else branches
> * Jump tables
> * branch tables with linear and binary scans
> * Clustering tables (e.g., if you have cases 0-100 and 300-400).


The two I have seen done on S/370 are an indexed branch to a table of
branch instructions, and indexed load of an address to a register, and
then BR to that address. I presume those are two of the above. (IBM
programs commonly have return codes that are multiples of four,
presumably to make the indexing easier.)


> Are there any other methods worth mentioning?


VAX has the CASE instruction, most likely a microcode implementation
of one of the above. When VAX was new, there were stories that many
of the special instructions (such as POLY and INDEX) were slower than
doing the same operation using separate instructions.


I believe that JVM also has a special instruction for this
operation, as the above likely don't work there.


> [I think I've seen hashing into branch tables. -John]


Sounds better than branching into hash tables.


-- glen
[On machines with condition codes, I've seen binary searches expanded
into code with compare and branch instructions; after the comparison
you can do a three way branch on less, equal, or greater. -John]

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