Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!iuvax!purdue!haven!mimsy!chris
From: chris@mimsy.UUCP (Chris Torek)
Newsgroups: comp.lang.c
Subject: one pass switch code (was forward references in typedefs)
Message-ID: <18735@mimsy.UUCP>
Date: 25 Jul 89 21:03:58 GMT
References: <55480@tut.cis.ohio-state.edu> <1989Jul20.152935.14872@utzoo.uucp> <686@ftp.COM>
Organization: U of Maryland, Dept. of Computer Science, Coll. Pk., MD 20742
Lines: 49

>>In article <24CB9E07.9547@marob.masa.com> cowan@marob.masa.com (John Cowan)
wrote:
>>>Ufcawss, if you talk to the people who wrote VMS C, they'll tell you that
>>>all one-pass implementations of C are unacceptable!  (This has something to
>>>do with generating good code for the 'switch' statement.)

>In article <18729@mimsy.UUCP> I (Chris Torek) answered:
>>They are both right and wrong.  One-pass code generation means there
>>are few opportunities for optimsiation; but generating good switches
>>is easy.  Simply emit a branch at the top of the switch, code at each
>>of the labels, a branch at the bottom, and then generate the code
>>that actually implements the switch.  E.g., given
>>
>> [Clever example deleted]

Now in article <686@ftp.COM> wjr@ftp.COM (Bill Rust) writes:
>... two ways to implement switches: jump tables and compare and execute
>when equal.  Jump tables (ie jmp switch_list[ix] where ix is some easy
>transformation of the switch variable) are much more efficient when
>the range of values that the switch variable can assume is limited (ie
>switch variable in range of 1 to 20 and it assumes 75% of values). The
>only way to tell if a jump table is better than compare and jump is to
>see what the range of the switch variable is and how many values it
>actually assumes.

So far so good.

>This is very difficult to do in a one pass compiler.

Competely wrong.  See text above and example in <18729@mimsy.UUCP>,
and see below.

>The previous correspondent completely ignored this in his response.

False.

``Simply emit a branch at the top of the switch, code at each of the
  labels, a branch at the bottom, and then generate the code that
  actually implements the switch.''

Since the code that implements the switch is not generated until after
all the cases are known, the compiler can select one of the various
alternatives.  (Incidentally, heap switches are better for sparse
tables above a moderate number of comparisons.  PCC has used all three
of these forms---direct, heap, and jump table switches---for years, and
PCC is a one-pass compiler.)
-- 
In-Real-Life: Chris Torek, Univ of MD Comp Sci Dept (+1 301 454 7163)
Domain:	chris@mimsy.umd.edu	Path:	uunet!mimsy!chris