Re: How to type braces for computed gotos

wclodius@earthlink.net (William Clodius) writes:
>glen herrmannsfeldt <gah@ugcs.caltech.edu> wrote:
>
>> William Clodius <wclodius@earthlink.net> wrote:
>>
>> (snip on labeled variable GOTO, Fortran ASSIGNed GOTO, and such)
>> ...
>> If you consider something like Duff's device, then it isn't so obvious
>> that computed GOTO is so different from C's switch/case. (Well, when
>> the labels are sequential starting at one.)
>>
>> As I noted previously, the Fortran standard now considers SELECT CASE
>> as a replacement for computed GOTO, though the latter hasn't yet been
>> removed from the standard.


SELECT CASE may or may not be closer to switch than Fortran's computed
GOTO, but my claim was that Fortran's computed GOTO is closer to C
switch than to GNU C's labels-as-values (often called "computed goto",
too). You make a good point from the view of usage, but I was
thinking more about implementation:


Fortran's computed goto does a range check, a table lookup and an
indirect branch. And so does C's switch (well, the compiler can also
use other implementations, but that's certainly the classical
implementation, and it is probably used by every compiler for densely
populated cases).


In contrast, GNU C's labels-as-values and Fortran's assigned goto deal
directly with code addresses: The code address of a label is stored in
a variable (or more complex structure), and the corresponding goto
just performs an indirect branch.


>In the case of Anton I think for the applications he is best know for,
>high performance interpreters, the lack of syntactic block is a minor
>advantage in that the
>
>100 SELECT CASE(i)
> CASE(0)
> ...
> GO TO 100
> CASE(1)
> ...
> GO TO 100
> CASE(2)
> ...
>
>can be replaced by
>
> GO TO(10, 11, 12, ...) I
>10 ...
> GO TO(10, 11, 12, ...) I
>11 ...
> GO TO(10, 11, 12, ...) I
>12 ...
>
>Saving an extra step in indirection. The bigger problem is the fall
>through semantics for out of range with its implicit additonal test and
>branch before the goto's implicit branch table.


Actually the shared indirect branch is the bigger problem. The range
check is predictable and costs almost nothing, while the shared
indirect branch has almost 0% prediction accuracy (in contrast to
about 50% accuracy if you have a separate indirect branch at the end
of every routine that implements a virtual machine instruction).


> That can be avoided by a
>modulo operation
>
>GO TO(10, 11, 12, ...) MODULO(I, N) +1
>
>where N is the number of labels appearing in the computed GOTO. If I is
>an 8 bit integer and N is 256 a sufficiently smart compiler should
>recognize the semantics of an unsigned 8 bit integer, fit the jump table
>in a single level 1 cache line, optimize out the MODULO, the addition of
>1, and the test for out of range and give him the efficiency he used to
>get with gcc's "computed goto".


Even if you eliminate the range check and produce separate indirect
branches, the Fortran computed goto (or SELECT CASE) and C switch
still perform the table lookup, which is not needed with GNU C's
labels-as-values or Fortran's assigned GOTO. The performance impact
is not as big as with separate indirect branches, but it's still there
and can be eliminated. The technique is called direct-threaded code.
In Fortran it might look like this:


            ASSIGN 11 TO PROG(0)
            ASSIGN 11 TO PROG(1)
            ASSIGN 10 TO PROG(2)
            IP=0
            GOTO PROG(IP)


10 ... code for virtual machine addition ...
            IP=IP+1
            GOTO PROG(IP)
            GOTO I
11 ... code for virtual machine constant ...
            IP=IP+1
            GOTO PROG(IP)
            GOTO I


Of course in a real interpreter PROG would not be initialized by
hard-coded ASSIGNs, but the ASSIGNs would initialize an instruction
array, and the interpreter front end would fill PROG from there; this
essentially moves the indirection from execution to the interpreter
front-end (one indirection per VM instruction instead of one
indirection per VM instruction execution).


- anton
--
M. Anton Ertl
anton@mips.complang.tuwien.ac.at
http://www.complang.tuwien.ac.at/anton/

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