Path: csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!usenet.blueworldhosting.com!feeder01.blueworldhosting.com!border2.nntp.dca1.giganews.com!nntp.giganews.com!news.iecc.com!.POSTED!nerds-end From: anton@mips.complang.tuwien.ac.at (Anton Ertl) Newsgroups: comp.compilers Subject: Re: How to type braces for computed gotos Date: Fri, 25 Jul 2014 22:38:09 -0400 (EDT) Organization: Institut fuer Computersprachen, Technische Universitaet Wien Lines: 112 Sender: news@iecc.com Approved: comp.compilers@iecc.com Message-ID: <14-07-059@comp.compilers> References: <14-05-013@comp.compilers> <14-07-033@comp.compilers> <14-07-048@comp.compilers> <14-07-054@comp.compilers> <14-07-056@comp.compilers> <14-07-058@comp.compilers> NNTP-Posting-Host: news.iecc.com X-Trace: miucha.iecc.com 1406342289 34308 2001:470:1f07:1126:0:676f:7373:6970 (26 Jul 2014 02:38:09 GMT) X-Complaints-To: abuse@iecc.com NNTP-Posting-Date: Sat, 26 Jul 2014 02:38:09 +0000 (UTC) Keywords: C, Fortran, syntax Posted-Date: 25 Jul 2014 22:38:09 EDT X-submission-address: compilers@iecc.com X-moderator-address: compilers-request@iecc.com X-FAQ-and-archives: http://compilers.iecc.com Xref: csiph.com comp.compilers:1349 wclodius@earthlink.net (William Clodius) writes: >glen herrmannsfeldt wrote: > >> William Clodius 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/