[net.lang.c] the C switch

hkr4627@acf4.UUCP (Hedley K. J. Rainnie) (03/02/85)

Do any C compilers perform switch optimization? I.e. tradeoff cascaded if
for table lookup. Clearly this is an optimization since a table would be
very wasteful for:

    switch(x){
     case 0: a();break;
     case 65535: b();
    }

Just wondering. 

Hedley.

gwyn@brl-tgr.ARPA (Doug Gwyn <gwyn>) (03/03/85)

> Do any C compilers perform switch optimization? I.e. tradeoff cascaded if
> for table lookup.

All the C compilers I am familiar with have about three different ways
of generating code for a switch statement, in an attempt to optimize
the size of the code vs. its speed.

guy@rlgvax.UUCP (Guy Harris) (03/03/85)

> > Do any C compilers perform switch optimization? I.e. tradeoff cascaded if
> > for table lookup.
> 
> All the C compilers I am familiar with have about three different ways
> of generating code for a switch statement, in an attempt to optimize
> the size of the code vs. its speed.

Specifically, for a dense switch the VAX PCC generates a "casel" (indexed
branch) instruction.  For a sparse switch with a small number of cases, it
generates a cascaded "if".  For stuff in between, it either generates a linear
or hashed table search.  I believe the Ritchie PDP-11 C compiler generates
similar code; many other PCC implementations do also.

	Guy Harris
	{seismo,ihnp4,allegra}!rlgvax!guy
-- 
	Guy Harris
	{seismo,ihnp4,allegra}!rlgvax!guy

henry@utzoo.UUCP (Henry Spencer) (03/04/85)

> Do any C compilers perform switch optimization? I.e. tradeoff cascaded if
> for table lookup. Clearly this is an optimization since a table would be
> very wasteful for [a very sparse switch].

Most if not all C compilers do.  It's necessary, really.
-- 
				Henry Spencer @ U of Toronto Zoology
				{allegra,ihnp4,linus,decvax}!utzoo!henry

thomson@uthub.UUCP (Brian Thomson) (03/07/85)

One of the schemes used by the Version 6 Ritchie compiler had the
unfortunate characteristic of being non-reentrant; it was de-conceived
in V7.
-- 
		    Brian Thomson,	    CSRI Univ. of Toronto
		    {linus,ihnp4,uw-beaver,floyd,utzoo}!utcsrgv!uthub!thomson

dave@lsuc.UUCP (David Sherman) (03/11/85)

> Do any C compilers perform switch optimization? I.e. tradeoff cascaded if
> for table lookup.

The code generation algorithms (three of them) are described
in an article by LeRoy Fundingsland, "Code Generation for the
``Switch'' By the Version 7 C Compiler" which appears in UNIX Review,
Feb-March 1984 (vol. 2 #1), pp. 94-100 and 123.  I found it very
instructive.

Dave Sherman
Toronto
-- 
{utzoo pesnta nrcaero utcs hcr}!lsuc!dave
{allegra decvax ihnp4 linus}!utcsri!lsuc!dave