Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!seismo!rochester!pt.cs.cmu.edu!cadre!pitt!darth!gary
From: gary@darth.UUCP (Gary Wisniewski)
Newsgroups: net.lang.c
Subject: Re: Generating code for the switch statement
Message-ID: <141@darth.UUCP>
Date: Thu, 21-Aug-86 00:49:15 EDT
Article-I.D.: darth.141
Posted: Thu Aug 21 00:49:15 1986
Date-Received: Mon, 25-Aug-86 21:45:37 EDT
References: <15093@ucbvax.BERKELEY.EDU> <2765@brl-smoke.ARPA> <610@hropus.UUCP> <840@edison.UUCP>
Reply-To: gary@darth.UUCP (Gary Wisniewski)
Organization: Darth Software, Allison Park, Pa. 15101
Lines: 65
Summary: A plethora of options

In article <840@edison.UUCP> jso@edison.UUCP (John Owens) writes:
>In article <610@hropus.UUCP>, ka@hropus.UUCP (Kenneth Almquist) writes:
>> If the cases are not consecutive, the branch table must be filled with
>> entries for the "missing" cases, making the table larger.  [....]  If
>> the cases are mostly consecutive with a few outliers, a branch table
>> could be augmented with a few specific tests for the outliers, but I
>> don't know of any compiler that does this.
>
>The Microsoft Pascal/Fortran compilers, at least some of the old
>ones (3.04 and 3.11) do this.  I haven't tried it to see if their
>wonderful new code generators do.

Lattice C (for IBM PC/XT/AT) actually generates three possible code sequences
for switch statements:

	1.  For a small number of cases, individual comparisons
	    are generated.
	2.  For a large number of cases, a branch table is generated, with
	    default branches for the missing cases.
	3.  For cases which compromise space (in 2) or speed (in 1), the
	    final approach builds a compact branch table and scans it
	    sequentially.

This is true for versions 2.14/2.15 of Lattice C (which were the same
as the Microsoft C Compiler before version 3.)  Lattice no longer supplies
the Microsoft compiler, but has continued the traditional switch statement
code generation trio at Lattice version 3.00.

It is certainly not clear whether or not it is worth the trouble.
Especially since the Lattice code generator does not take advantage of
some of the fast compare/increment/repeat instructions for the 8086/88 when
implementing option (3).  Instead, they generate a loop which takes several
times the speed and space possible with a better technique.

Another interesting note about Lattice's handling of switch statements.
Lattice reduces the following:

	switch (i)
	  {
	    case '0':
	    case '1':
	    case '2':
	    case '3':
	      break;
	  }

to:

	if (i >= '0' || i <= '3')
	  ;

However, it will not perform the same optimization if other cases, not
serial with the rest, are included in the switch statement.  I hope that
this is a side effect, since this particular situation would occur
seldom, if ever, in real C code.

In any case, they seem to have spent some time trying to generate
interesting, if not useful, code for switch statements.  (I do
wish they had recognized the above example as useless and removed it
completely, however.)

Gary Wisniewski
Pittsburgh, PA
(412) 363-4685
uucp:	{allegra,bellcore,cadre}!pitt!darth!gary