Optimisation of C-code (runtime and compiled) ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ - Placing of STG registers in machine registers - Optimisation of interpreter loop (tail calls) /* TODO: flags */ -OC flag to ghc causes optimisation ANSI C ~~~~~~ For functions with no args we declare them as foo( STG_NO_ARGS ) rather than foo(), because you can tell ANSI C a little more by making STG_NO_ARGS expand to void. Maybe something to do with forward declarations? Optimisation with GCC ~~~~~~~~~~~~~~~~~~~~~ We are concentrating most optimisation with gcc which allows suitable global register declarations. REGISTERS: See StgOpt.h for a description of register usage Note that all modules that reference the STG registers must be compiled the same way so they look at the registers and not the global variables. TAIL CALLS: Seperate modules for tail call optimisations are required. Requitre to partition runtime system code. .hc: Modules with tail call routines (most runtime and all compiled) are labeled .hc (literate = .lhc). These are compiled to assember with tail call optimisation on and then post processed with sed (Yuk!) All routines which return a continuation (STGJUMP) must be compiled this way. (The only exeption to this is continuations which exit/abort which may live in .c files) .c: These modules are not compiled with the tail call optimisation and don't have sed processing. Sed processing would destroy the code! All routines which are not continuations (called and return conventionally) must be compiled this way. This includes various parts of the runtime system. See Also ~sansom/work/gcstats/OBSERVATIONS Info Recieved from Eliot Miranda: Received: from dcs.glasgow.ac.uk (tutuila) by vanuata.dcs.glasgow.ac.uk; Thu, 4 Jul 91 09:40:34 BST Message-Id: <15456.9107040841@dcs.glasgow.ac.uk> X-Comment1: ############################################################# X-Comment2: # uk.ac.glasgow.cs has changed to uk.ac.glasgow.dcs # X-Comment3: # If this address does not work please ask your mail # X-Comment4: # administrator to update your NRS & mailer tables. # X-Comment5: ############################################################# To: simonpj Cc: sansom Subject: Miranda's original msg Date: Thu, 04 Jul 91 09:41:19 +0100 From: Simon L Peyton Jones >From eliot@.cs.qmw.ac.uk Mon Apr 1 11:16:06 1991 From: eliot@.cs.qmw.ac.uk (Eliot Miranda) Newsgroups: comp.compilers Subject: Portable Fast Direct Threaded Code Keywords: interpreter, design Date: 28 Mar 91 12:20:06 GMT Reply-To: Eliot Miranda Organization: Computer Science Dept, QMW, University of London, UK. Various people have asked me for details on how I do threaded code in my dynamic translation Smalltalk-80 VM. So here's the gory details as well as the first published benchmarks for the system. How to do "Machine-Independent" Fast Direct Threaded Code: First off, use C (although other flexible machine-oriented imperative languages would probably work too). Global registers: If you can use GCC >v1.33 you can use global register variables to hold the threaded code machine's registers. If you have various forms of stupid C compiler then you can get global register variables by declaring your globals as register variables in every function, and later editing the assembler generated by the C compiler to remove global register saves & restores (details in [Miranda]). Threaded Code: Threaded code instructions (TCIs) are written as C procedures. They are compiled to assembler by the C compiler. Subsequently a simple editor script is run on the assembler to remove the prologues and epilogues from the threaded code procedures, and possibly to insert direct threaded code jumps. How to Identify Threaded Code Instructions: The method I prefer is to segregate TCIs from other procedures & functions in the machine by placing related groups of TCIs in separate source files. I give my threaded code source files the .tc extension and they have a rule in the makefile that will run the editor script on the assembler. An alternative is to identify each threaded code procedure with a special prefix which is spotted by the editor script. This is probably more error prone & doesn't fit well with leaf-routine optimization (see below). How to Write Threaded Code Instructions: Each TCI is writen an a void function of no arguments. It is wise to start and end each TCI with two special macros to replace '{' and '}'. So, using GCC on the SPARC, given some declarations: typedef void (*TCODE)(); /* a TCODE is a pointer to a function */ typedef ???? ObjectPointer; . . . register TCODE *tcip asm("%g7"); /*threaded code instruction pointer*/ register ObjectPointer *stackPointer asm("%g5"); e.g. popStack would be written: void popStack() TBEGIN stackPointer--; TEND With GCC TBEGIN is #define TBEGIN { With stupid C compilers it can be defined to be the list of global register variables. Further, if you want to build a debuger for your threaded code machine you could compile the system with #define TBEGIN { int frig = checkForBreakPoint(); and ignore lots of warnings about variable frig being unused :-). TEND has to do a direct threaded code jump. In my system I want an indirect post-increment jump on tcip; i.e. jump to *tcip++. On the SPARC with tcip in %g7 the jump is ld [%g7],%o0 ! get *tcip jmpl %o0,%g0 ! jump to it add %g7,4,%g7 ! increment tcip in the jump's delay slot On the 68k with tcip in a5 the jump is movl a5@+,a0 jmp a0@ With GCC this is implemented by the JUMPNEXT macro. On the SPARC: #define JUMPNEXT do{ \ asm("ld [%g7],%o0; jmpl %o0,%g0; add %g7,4,%g7");\ return;}while(0) Note the return, it tells the compiler that control does not pass this point. On the 68k: /* SBD = Silent But Deadly = Stack Bug Dummy. gcc has a bug with no-defer-pop. it always depers the pop of the last function call in a routine. SBD is a dummy call to ensure no other previous call gets its pop deferred. */ extern void SBD P((void)); #define JUMPNEXT do{ \ asm("movl a5@+,a0; jmp a0@");\ SBD();return;}while(0) SBD is then removed by the editor script. So TEND is defined to be #define TEND JUMPNEXT; } On the SPARC popStack is expanded to void popStack() { stackPointer--; do{asm("ld [%g7],%o0; jmpl %o0,%g0; add %g7,4,%g7");return;}while(0); } Its compiled to: _popStack: !#PROLOGUE# 0 save %sp,-80,%sp !#PROLOGUE# 1 add %g5,-4,%g5 ld [%g7],%o0; jmpl %o0,%g0; add %g7,4,%g7 ret restore The editor script then reduces this to:` _popStack: ! [gotcher] add %g5,-4,%g5 ld [%g7],%o0; jmpl %o0,%g0; add %g7,4,%g7 On the 68k you end up with: .globl _popStack _popStack: subqw #4,a3 movl a5@+,a0; jmp a0@ Global Register Variables and Stupid C Compilers: Some C compilers are stupid enough to provide straight-forward global registers. A C compiler on a nat-semi based system I used just allocated registers in the order they were declared. The assembler syntax was very simple to edit. Global register variables could thus be obtained easily. Some C compilers are stupid but think they're clever. Sun's SUN3 compiler is a case in point. It also allocates registers in the order declared. However, it tries to be clever by removing 'dead assignments' (assignments to subsequently unused register variables). These compilers are easy to fool. Simply arrange that the register variables are always used before leaving a function. I do this by always writing RETURN or RETURNV(e) instead of return and return e. On systems with such stupid C compilers RETURN(e) is defined thus: #define RETURNV(e) do{DummyUseRegs(GR1,GR2,GR3); return e;}while(1) The call on DummyUseRegs fools the compiler into thinking the registers are live & hence saves assignments to them. The editor scripts can then remove calls on DumyUseRegs. Of course on systems with marginally clever C compilers (SUN4 HP-UX etc) you're stuffed. However, in clever C compilers like GCC and Acorn's C compiler you can declare global registers & everything is clean & wholesome :-). Conditional TCODE Jumps: Say we wanted a conditional tcode jump. This might be writen: void skipIfTrue() TBEGIN if (*stackPointer-- == TrueObject) { tcip += 1; JUMPNEXT; } TEND How this All Works: With the above scheme, each threaded code procedure runs in the same C stack frame, and jumps directly to the next procedure, eliminating an unnecessary , pair. Once we establish a stack frame and call the first function away we go. Assuming that you've produced your first threaded code method (a sequence of pointers to threaded code procedures), and that tcip points at the start, then StartTCMachine might be defined as follows: volatile void StartTCMachine() { char *enoughSpaceForAllTCIStackFrames; enoughSpaceForAllTCIStackFrames = alloca(1024); while(1) { (*tcip++)(); } } The alloca allocates space on the stack. After the first (*tcip++)() control goes off into threaded code land and never returns. Leaf Routine Optimization: The threaded code machine will make calls on support routines e.g. graphics, garbage collector etc. Any group of routines that dont access the global registers and don't directly or indirectly call routines that need to access the global registers can be optimized. These routines should be compiled without declaring the global registers. These routines will then use as many registers as the compiler will give them and will save & restore any registers they use, preserving the values of the global register variables. Details of my Smalltalk Threaded Code Machine: I use a pair of words for each TCI, a pointer to the procedure followed by an optional operand. This avoids going out of line to access arguments. e.g. pushLiteral is: void pushLit() TBEGIN *++stackPointer = (OOP)*tcip++; TEND where OOP is an ordinary object pointer. So on entry to push lit we have: tcip-> and popStack must therefore be written void popStack() TBEGIN stackPointer--; tcip++; TEND I dynamically compile Smalltalk-80 bytecodes to threaded code. I use 128k bytes of memory to hold all threaded code. This 'tspace' is periodically scavenged to reclaim space. The architecture is similar to [DeutschSchiffman]. Using an eighth of the space used by the Deutch Schifman machine I get around 75% of the performance on the non-graphics benchmarks. Here are the Smalltalk macro benchmarks for BrouHaHa Smalltalk-80 v2.3.2t running on a monochrome SUN3/60 (20MHz 68020): BitBLT 76.7308 TextScanning 222.857 ClassOrganizer 80.6667 PrintDefinition 59.0278 PrintHierachy 142.857 AllCallsOn 112.5 AllImplementors 130.0 Inspect 116.667 Compiler 86.4341 Decompiler 101.639 KeyboardLookAhead 212.5 KeyboardSingle 302.778 TextDisplay 148.837 TextFormatting 273.81 TextEditing 180.342 Performance Rating 134.198 and on the same machine under the same conditions are the timings for ParcPlace Smalltalk-80 V2.3: BitBLT 99.75 TextScanning 390.0 ClassOrganizer 155.128 PrintDefinition 137.097 PrintHierachy 192.308 AllCallsOn 120.0 AllImplementors 108.333 Inspect 146.774 Compiler 118.617 Decompiler 129.167 KeyboardLookAhead 303.571 KeyboardSingle 473.913 TextDisplay 172.973 TextFormatting 442.308 TextEditing 285.135 Performance Rating 189.504 134.198/189.504 = 0.708154 WARNING!! These systems ARE different, these benchmarks are included only to give a feeling for ball-park performance. Example differences: BrouHaHa ParcPlace closures blue-book BlockContexts immediates: characters, smallints, fixedpoints immediate smallintegers 5844 compiled methods 5136 compiled methods (5026 ordinary methods) (4798 ordinary methods) (818 quick methods) (338 quick methods) More Portable File Organization: To keep the code as clean looking as possible all machine-dependencies are isolated in separate files. e.g. tcode.h gives machine independent definitions for TCODE. It includes machine dependencies from another file: /* for debugging purposes; single step breakpoint at start of each tcode */ #define DEBUG_FETCH_BREAK int frig = fetchBrk(); #ifdef FAST # include "fasttcode.h" #else TCODE *tcip; /* the tcode ip points at TCODEs */ # define JUMPNEXT return # ifdef BIDebug # define TBEGIN { DEBUG_FETCH_BREAK # else # define TBEGIN { # endif # define TEND } #endif GCC/SPARC/fasttcode.h: /* tcodeip in g7 */ register TCODE *tcip asm("%g7"); #define JUMPNEXT do{asm("ld [%g7],%o0; jmpl %o0,%g0; add %g7,4,%g7");return;}while(0) #ifdef BIDebug # define TBEGIN { DEBUG_FETCH_BREAK #else # define TBEGIN { #endif #define TEND JUMPNEXT; } I also don't want to include the necessary definitions for the global registers in every file. So for those non-leaf routines that must avoid using the global registers there's a fastglobal.h file that gives dummy definitions for these registers. e.g. GCC/SPARC/fastglobal.h: /* machine specific FAST defines. Gnu C 1.33 systems can use nice compiler provided global registers. */ #define BEGIN { #define END } #define RETURN(e) return e #define RETURNV return register char *GlobRegDummy1 asm("a5"); register char *GlobRegDummy2 asm("a4"); register char *GlobRegDummy3 asm("a3"); register char *GlobRegDummy4 asm("d6"); #ifdef MASKREGISTER register char *GlobRegDummy5 asm("d7"); #endif I use symbolic links to set up the machine dependent include files. This has the advantage that if you add a new machine you don't have to remake all the others. The Tedious Bit: The only tedious bit is writing the sed-scripts. For the SPARC this took 1 day. Here are the sed scripts I use for SUN 3, MAC2AUX (using GAS) and SUN4, all using GCC (v1.33 upwards). There's a problem on the SPARC in that the ABI does not seem to define the status of the global registers. Some math and library routines stomp on the global registers (beware getwd!), so I've included GCC/SUN4/sed.globreg.bugfix as an example of how to spot the offending math routines: SUN3/GCC/lib/sed.tcode.opt: # script to strip prolog & epilog from threaded code under gcc. # WARNING the script may strip a push of a register argument if a call is the # first statement of a function!! # /^_.*:$/{n N N s/ link a6,#[^\n]*\n// / fmovem #[^\n]*,sp@-/{ N s/ fmovem #[^\n]*,sp@-\n// } s/ moveml .*,sp@-\n// s/ movel [ad][0-7],sp@-\n// } / moveml a6@(-[1-9][0-9]*),#/{N s/ moveml a6@(-[1-9][0-9]*),#[^\n]*\n unlk a6// } / movel a6@(-[1-9][0-9]*),[ad][0-7]/{N s/ movel a6@(-[1-9][0-9]*),[ad][0-7]\n unlk a6// } / movel sp@+,/d / moveml sp@+,#/d / unlk a6/d / rts/d / jbsr _SBD/d MAC2AUX/GCC/lib.gas/sed.tcode.opt: /COMMENT/{ i\ script to strip prolog & epilog from threaded code under gcc. WARNING \ the script may strip a push of a register argument if a call is the\ first statement of a function!! } /^gcc_compiled:/d /^.[^%].*:$/{ n / link %a6/{ N N s/ link %a6,#[x0-9-]*\n// / fmovem #[^\n]*,%sp@-/{ N s/ fmovem #[^\n]*,%sp@-\n// } s/ moveml #[x0-9a-f]*,%sp@-\n// s/ movel %[ad][0-7],%sp@-\n// n } } / moveml -[1-9][0-9]*%a6@,#/{ N s/ moveml -[1-9][0-9]*%a6@,#[x0-9a-f-]*\n unlk %a6// } / movel -[1-9][0-9]*%a6@,%[ad][0-7]/{ N s/ movel -[1-9][0-9]*%a6@,%[ad][0-7]\n unlk %a6// } / movel %sp@+,%/d / moveml %sp@+,#/d / movel %d0,%a0/{ N s/ movel %d0,%a0\n unlk %a6// / movem*l %a6/{ N s/ movel %d0,%a0\n movem*l %a6.*\n unlk %a6// / fmovem %a6/{ N s/ movel %d0,%a0\n movem*l %a6.*\n fmovem %a6.*\n unlk %a6// } } } / unlk %a6/d / rts/d / jbsr SBD/d SUN4/GCC/lib/sed.tcode.opt: # script to strip prolog & epilog from threaded code under gcc. # /^_.*:$/{n N N s/ !#PROLOGUE# 0\n save %sp,[-0-9]*,%sp\n !#PROLOGUE# 1/ ! [gotcher]/ } / ret/d / restore/d SUN4/GCC/lib/sed.globreg.bugfix: # Some of the libc builtin routines (.rem .urem .div & .udiv so far known) # stamp on %g3 which is the maskReg (it contains 0x7FFFFF). # This script reassigns the value of maskReg after each of these routines # has been called. /call[ ]\.div,[0-9]/{n n i\ sethi %hi(0x7FFFFF),%g3 ![globregfix]\ or %lo(0x7FFFFF),%g3,%g3 } /call[ ]\.udiv,[0-9]/{n n i\ sethi %hi(0x7FFFFF),%g3 ![globregfix]\ or %lo(0x7FFFFF),%g3,%g3 } /call[ ]\.rem,[0-9]/{n n i\ sethi %hi(0x7FFFFF),%g3 ![globregfix]\ or %lo(0x7FFFFF),%g3,%g3 } /call[ ]\.urem,[0-9]/{n n i\ sethi %hi(0x7FFFFF),%g3 ![globregfix]\ or %lo(0x7FFFFF),%g3,%g3 } You can now see why I put "Machine-Independent" in quotes. Here's the count of machine dependent code for the SPARC: 25 99 786 fastcache.h 68 262 1882 fastglobal.h 31 112 906 fasttcode.h 28 80 595 ../tcsrc/SUN4/GCC/lib/sed.globreg.bugfix 5 34 222 ../tcsrc/SUN4/GCC/lib/sed.peep.opt 9 30 173 ../tcsrc/SUN4/GCC/lib/sed.tcode.opt 166 617 4564 total Of these 166 lines 51 lines are banner headers. 100 odd lines are machine dependent. A whole VM is around the 20k lines mark. So machine dependencies are down in the 0.5% range. Use this stuff as part of what ever you like. If you try & assert ownership I'll fight & batter you over the head with the GPL ('bout time we had some serious steel in that thar GPL). Share And Enjoy! P.S. The BrouHaHa machine is available to educational institutions with a valid ParcPlace Smalltalk-80 licence, subject to a strict non-disclosure agreement. email me if you want it. I am slow to answer requests! -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request. >From crowl@cs.rochester.edu Tue Apr 2 10:34:53 1991 From: crowl@cs.rochester.edu (Lawrence Crowl) Newsgroups: comp.compilers Subject: Re: Portable Fast Direct Threaded Code Keywords: interpreter, design Date: 31 Mar 91 18:06:35 GMT Reply-To: crowl@cs.rochester.edu (Lawrence Crowl) Organization: Computer Science Department University of Rochester In article <3035@redstar.cs.qmw.ac.uk> Eliot Miranda writes: >The threaded code machine will make calls on support routines, e.g. graphics, >garbage collector etc. Any group of routines that don't access the global >registers and don't directly or indirectly call routines that need to access >the global registers can be optimized. These routines should be compiled >without declaring the global registers. These routines will then use as many >registers as the compiler will give them and will save & restore any >registers they use, preserving the values of the global register variables. This scheme assumes that procedure calls use a "callee saves" register convention, and does not work if you allocate the global register variables out of the "caller saves" set of registers. The problem is that the caller does not save the register (because it is global) and the callee writes over the register (because the caller saved it). In this situation, the programmer must insert explicit saves and restores of the global register variables. The obvious solution to this problem is to allocate all global register variables out of the "callee saves" set of registers. However, the Alliant has _no_ callee saves registers. Library routines on the Alliant will trash every register you have. In addition, implicit library calls to routines like bcopy will also trash your registers. (I learned this the hard way.) The lesson is that calling library routines with global register variables in caller saves registers requires special handling. It is not automagic. -- Lawrence Crowl 716-275-9499 University of Rochester crowl@cs.rochester.edu Computer Science Department ...!rutgers!rochester!crowl Rochester, New York, 14627-0226 -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request. >From Tom.Lane@G.GP.CS.CMU.EDU Wed Apr 3 10:38:09 1991 From: Tom.Lane@G.GP.CS.CMU.EDU Newsgroups: comp.compilers Subject: Re: Portable Fast Direct Threaded Code Keywords: interpreter, design Date: 1 Apr 91 15:21:14 GMT Reply-To: Tom.Lane@G.GP.CS.CMU.EDU Organization: Compilers Central Lawrence Crowl points out one important problem with Eliot Miranda's scheme for global register use in C. There's an even more fundamental problem, though: there is *no guarantee whatever* that the compiler will assign the same registers to the global variables in every routine. Compilers that do intelligent allocation of variables to registers may refuse to honor the "register" declarations at all if the global variables are not heavily used in a given routine, and in any case the globals need not be assigned to the same registers every time. Miranda's scheme thus relies heavily on the assumption of a dumb register allocator (or else a compiler that supports global register variable declarations). This scheme may be "fast" direct threaded code, but it's hardly "portable". -- tom lane Internet: tgl@cs.cmu.edu BITNET: tgl%cs.cmu.edu@cmuccvma [GCC lets you specify what register to use for global register variables, but that is of course both machine and compiler specific. -John] -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request. >From pardo@cs.washington.edu Thu Apr 4 17:34:39 1991 From: pardo@cs.washington.edu (David Keppel) Newsgroups: comp.compilers Subject: Re: Portable Fast Direct Threaded Code Keywords: interpreter, design, bibliography Date: 2 Apr 91 19:21:25 GMT Reply-To: pardo@cs.washington.edu (David Keppel) Organization: Computer Science & Engineering, U. of Washington, Seattle metzger@watson.ibm.com (Perry E. Metzger) writes: >[I'd like a reference on threaded code interpreters.] 3 citations follow: %A James R. Bell %T Threaded Code %J Communications of the ACM (CACM) %V 16 %N 2 %D June 1973 %P 370-372 %X Describes the basic idea of threaded code. Compares to hard code (subroutine calls) and interpreters. %A Richard H. Eckhouse Jr. %A L. Robert Morris %T Minicomputer Systems Organization, Programming, and Applications (PDP-11). 2nd Ed. %I Prentice-Hall, Inc. %P 290-298 %X Describes threaded code and ``knotted code''. I (pardo) think that this is a very clear introduction to threaded code. %A Peter M. Kogge %T An Architectural Trail to Threaded Code Systems %J IEEE Computer %P 22-33 %D March 1982 %W rrh (original) %W Pardo (copy) %X Describes how to build a threaded code interpeter/compiler from scratch. * Direct threaded/indirect threaded. * Less than 2:1 performance hit of threading compared to full compilation. * Note about bad compilers contributing to relative OK-ness of threaded code. * Ease of rewriting stuff. * Ease of tuning. My favorite of the three is Eckhouse & Morris; however I don't know where to get it. The pages that I have are photocopies graciously sent to me by a friend. As the title implies, this book is several years old and undoubtedly out-of-print. ;-D on ( Following this thread of the discussion... ) Pardo -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request. >From simonpj Fri Apr 5 09:52:33 1991 Received: from tutuila.dcs.glasgow.ac.uk by vanuata.cs.glasgow.ac.uk; Fri, 5 Apr 91 09:52:27 BST Message-Id: <2763.9104050851@tutuila.dcs.glasgow.ac.uk> X-Comment1: ############################################################# X-Comment2: # uk.ac.glasgow.cs has changed to uk.ac.glasgow.dcs # X-Comment3: # If this address does not work please ask your mail # X-Comment4: # administrator to update your NRS & mailer tables. # X-Comment5: ############################################################# From: Simon L Peyton Jones To: eliot@cs.qmw.ac.uk Cc: simonpj, partain Subject: Threaded code Date: Fri, 05 Apr 91 09:51:48 +0100 Eliot I saw your article about threaded code. Like you and others, we are using C as an assembler, only for a pure functional language, Haskell. I have some brief questions. 1. By telling GCC not to use a frame pointer, one can eliminate the prolog entirely, can't one? So why edit it out? I guess the answer is going to be local variables, allocated once for all by the StartTCMachine routine. Still, it seems quite a pain. I guess one could sacrifice some (perhaps slight) speed by using a bunch of globals instead. 2. You edit out the epilogue for tidiness only, I take it. It doesn't cause any problems if you leave it in, does it? 3. Why do you use no-defer-pop (with the associated bug)? 4. Why does JUMPNEXT have a loop? Surely the jump leaves the loop right away. Presumably you are tricking the compiler somehow. Thanks Simon L Peyton Jones Glasgow University Simon ============================= Address change ======================= My email address is now officially: simonpj@dcs.glasgow.ac.uk This may fail if your local site has out-of-date mail tables. The old address (simonpj@cs.glasgow.ac.uk) will work for quite a long while, so stay with the old one if the new one fails. ==================================================================== >From eliot@cs.qmw.ac.uk Fri Apr 5 12:18:18 1991 Via: uk.ac.qmw.cs; Fri, 5 Apr 91 12:18:06 BST Received: from aux47 by redstar.cs.qmw.ac.uk id aa26828; 5 Apr 91 12:17 BST Reply-To: eliot@cs.qmw.ac.uk In-Reply-To: Simon L Peyton Jones's mail message <2763.9104050851@tutuila.dcs.glasgow.ac.uk> Message-Id: <9104051217.aa26828@uk.ac.qmw.cs.redstar> From: Eliot Miranda To: simonpj Cc: partain Subject: re: Threaded code Date: Fri, 5 Apr 91 10:54:25 BST > >Eliot > >I saw your article about threaded code. Like you and others, we are >using C as an assembler, only for a pure functional language, Haskell. >I have some brief questions. > >1. By telling GCC not to use a frame pointer, one can eliminate >the prolog entirely, can't one? So why edit it out? No, registers local to the procedure will still be saved & stack space allocated for automatic variables. This IS a problem since the threaded-code jump at the end of the procedure will miss the register restores before the epilogue. Consequently the stack will grow unless these register saves & stack-space allocations are removed. > >I guess the answer is going to be local variables, allocated once for >all by the StartTCMachine routine. Still, it seems quite a pain. I guess >one could sacrifice some (perhaps slight) speed by using a bunch of >globals instead. For certain routines, not using register variables will be expensive (e.g. a simple integer arithmetic primitive). > >2. You edit out the epilogue for tidiness only, I take it. It doesn't >cause any problems if you leave it in, does it? No, but given that the prologue has to be removed & removing the epilogue is as easy (& given finite memory :-) one might as well remove it. > >3. Why do you use no-defer-pop (with the associated bug)? OK. This is again to avoid stack growth. On conventional stack architectures gcc will try & combine the argument popping code of a sequence of procedure calls. e.g. extern long a, b, c; void doit() { foo(a); bar(b); baz(c); } with -O -no-defer-pop one might expect gcc to generate link %a6,#0 movel a,%sp@- jbsr foo addqw #4,%sp movel b,%sp@- jbsr bar addqw #4,%sp movel c,%sp@- jbsr baz addqw #4,%sp unlk %a6 rts but because gcc knows that the unlk instruction will roll back the stack in fact gcc generates: link %a6,#0 movel a,%sp@- jbsr foo addqw #4,%sp movel b,%sp@- jbsr bar addqw #4,%sp movel c,%sp@- jbsr baz unlk %a6 rts With -O -fdefer-pop gcc optimizes out the pops completely & generates: link %a6,#0 movel a,%sp@- jbsr foo movel b,%sp@- jbsr bar movel c,%sp@- jbsr baz unlk %a6 rts with -O -fomit-frame-pointer -fdefer-pop gcc generates: movel a,%sp@- jbsr foo movel b,%sp@- jbsr bar movel c,%sp@- jbsr baz addw #12,%sp rts & with -O -fomit-frame-pointer -fno-defer-pop gcc generates: movel a,%sp@- jbsr foo addqw #4,%sp movel b,%sp@- jbsr bar addqw #4,%sp movel c,%sp@- jbsr baz addqw #4,%sp rts All the above cases are as one would wish. The elimination of all defered pops in the unlk instruction is especially clever. However, in the presence of the threaded-code jump the waters darken! Consider what gcc generates for: register void (**tcip)() asm("%a5"); #define JUMPNEXT do{asm("movl %a5@+,%a0; jmp %a0@");return;}while(0) extern long a, b; void doit() { foo(a); bar(b); JUMPNEXT; } with -O -fdefer-pop gcc generates doit: link %a6,#0 movel a,%sp@- jbsr foo movel b,%sp@- jbsr bar #APP movl %a5@+,%a0; jmp %a0@ #NO_APP unlk %a6 rts This is clearly no good because the arguments to both foo & bar will never be popped. Every time doit() is executed the stack will grow by 8 bytes. Soon your program will dump core with a very large stack segment! with -O -fno-defer-pop gcc generates: link %a6,#0 movel a,%sp@- jbsr foo addqw #4,%sp movel b,%sp@- jbsr bar #APP movl %a5@+,%a0; jmp %a0@ #NO_APP unlk %a6 rts Again useless because bar's pop has been folded into the unlk which won't be executed. with -O -fdefer-pop -fomit-frame-pointer gcc generates movel a,%sp@- jbsr foo movel b,%sp@- jbsr bar addqw #8,%sp #APP movl %a5@+,%a0; jmp %a0@ #NO_APP rts This is great. However, not all functions are susceptible to the omit-frame-pointer optimization (i.e. functions with local variables). E.g. the code generated for: register void (**tcip)() asm("%a5"); #define JUMPNEXT do{asm("movl %a5@+,%a0; jmp %a0@");return;}while(0) extern long a, b; void doit() { char large[1024]; foo(a,large); bar(b); JUMPNEXT; } with -O -fomit-frame-pointer -fdefer-pop is: link %a6,#-1024 pea %a6@(-1024) movel a,%sp@- jbsr foo movel b,%sp@- jbsr bar #APP movl %a5@+,%a0; jmp %a0@ #NO_APP unlk %a6 rts so in general one can't rely on -fomit-frame-pointer. For the above example both -O -fomit-frame-pointer -fno-defer-pop and -O -fno-defer-pop generate: doit: link %a6,#-1024 pea %a6@(-1024) movel a,%sp@- jbsr foo addqw #8,%sp movel b,%sp@- jbsr bar #APP movl %a5@+,%a0; jmp %a0@ #NO_APP unlk %a6 rts This is also useless because bar's argument pop has been folded away. The problem is that gcc will always fold away the last call's argument pop if the function has a frame pointer, and -fomit-frame-pointer can't allways get rid of the frame pointer. In fact, in the presence of variable sized automatic variables or calls on alloca it would be very hard (impossible for recursive functions?) to do. The eatest solution I've come up with is to use -fno-defer-pop and a dummy function call between the threaded-code jump and the return: register void (**tcip)() asm("%a5"); #define JUMPNEXT do{asm("movl %a5@+,%a0; jmp %a0@");SBD();return;}while(0) extern long a, b; void doit() { foo(a); bar(b); JUMPNEXT; } with -O -fno-defer-pop gcc generates: link %a6,#0 movel a,%sp@- jbsr foo addqw #4,%sp movel b,%sp@- jbsr bar addqw #4,%sp #APP movl %a5@+,%a0; jmp %a0@ #NO_APP jbsr SBD unlk %a6 rts Now bar's argument pop is not folded because its no longer the last call in the routine, SBD is. So the call to SBD a) prevents gcc's 'last call argument pop fold into unlk' optimization which prevents uncontrolled stack growth. b) doesn't get executed because of the jump c) is trivial to remove from the assembler with a sed-script >4. Why does JUMPNEXT have a loop? Surely the jump leaves the loop right >away. Presumably you are tricking the compiler somehow. > This is old C lore. The problem is 'How do you write a macro that is a sequence of statements that can be used wherever a single statement can?' take the following definition of JUMPNEXT: #define JUMPNEXT asm("movl %a5@+,%a0; jmp %a0@");return; Now invoke it here: if (its_time_to_jump) JUMPNEXT; do_something_else(); This expands to: if (its_time_to_jump) asm("movl %a5@+,%a0; jmp %a0@"); return; do_something_else(); Not at all whats intended! There are two tricks I know of (the first I saw in Berkely Smalltalk, the second in Richard Stallman's gcc manual. I expect they're both quite old). The first is to surround your statements with if (TRUE){statements}else i.e. #define JUMPNEXT if(1){asm("movl %a5@+,%a0; jmp %a0@");return;}else So now we get: if (its_time_to_jump) if (1){ asm("movl %a5@+,%a0; jmp %a0@"); return; else; do_something_else(); which works because C binds elses innermost first. However, some compilers will whine about dangling elses. The second scheme is more elegant (-: Surround your statements with do{statements}while(FALSE); which will execute statements precisely once (its NOT a loop). i.e. #define JUMPNEXT do{asm("movl %a5@+,%a0; jmp %a0@");SBD();return;}while(0) expands to if (its_time_to_jump) do { asm("movl %a5@+,%a0; jmp %a0@"); return; while(0); do_something_else(); which does what's wanted and doesn't incur compiler whines. >Thanks > >Simon L Peyton Jones >Glasgow University Eliot Miranda email: eliot@cs.qmw.ac.uk Dept of Computer Science Tel: 071 975 5229 (+44 71 975 5229) Queen Mary Westfield College ARPA: eliot%cs.qmw.ac.uk@nsf.ac.uk Mile End Road UUCP: eliot@qmw-cs.uucp LONDON E1 4NS >From vestal@SRC.Honeywell.COM Fri Apr 5 12:26:11 1991 From: vestal@SRC.Honeywell.COM (Steve Vestal) Newsgroups: comp.compilers Subject: Re: Portable Fast Direct Threaded Code Keywords: interpreter, performance, design Date: 3 Apr 91 18:23:34 GMT Reply-To: vestal@SRC.Honeywell.COM (Steve Vestal) Organization: Honeywell Systems & Research Center In-Reply-To: pardo@cs.washington.edu's message of 2 Apr 91 19:21:25 GMT In article <1991Apr2.192125.7464@beaver.cs.washington.edu> pardo@cs.washington.edu (David Keppel) writes: [references about threaded code, much stuff deleted] David> %X Describes how to build a threaded code interpeter/compiler from David> scratch. David> * Less than 2:1 performance hit of threading compared to full David> compilation. I have a question about this. Numbers like this are often cited for threaded-type code, but in Bell's paper this was for the PDP-11 (whose addressing modes made it a natural for threaded code). Paul Klint's "Interpretation Techniques" paper (Software P&E, v11, 1981) cites a significant difference for interpreter fetch/decode times on different architectures. He cited numbers around 2:1 for the PDP-11, but something more like 9:1 for a Cyber. I did a Q&D evaluation of this for a RISC, and the ratio I guestemated was closer to that Klint gave for the Cyber than for the PDP-11 (not unexpectedly). How architecturally dependent is the performance of these techniques (relative to compiling to native code)? Steve Vestal Mail: Honeywell S&RC MN65-2100, 3660 Technology Drive, Minneapolis MN 55418 Phone: (612) 782-7049 Internet: vestal@src.honeywell.com -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request. >From E.Ireland@massey.ac.nz Fri Apr 5 12:29:20 1991 From: E.Ireland@massey.ac.nz (Evan Ireland) Newsgroups: comp.lang.functional Subject: Three address code Date: 4 Apr 91 21:49:21 GMT Reply-To: E.Ireland@massey.ac.nz Organization: Information Sciences, Massey University, New Zealand I've had no luck with mail, so this is for csdw at Rhodes University. > >In an attempt to optimize a functional language, I would like to >turn the stack based intermediate code into three address code. > >Has anyone done similar conversions? Any references would be >greatly appreciated. I do not have any references, but I thought that one aspect of my FAM implementation might be of interest. A number of interpreters and compilers that I have seen implement a stack pointer in a register or global variable. Then to implement various stack operations, they use auto-increment or auto-decrement operations on the stack pointer register. Since I generate portable C, and thus cannot assume I have DATA *f (register DATA *fp) { .... } Thus I pass to each function the current pointer to top of stack, from which it can index downwards to find its arguments. Within the function, I use indexing operations on fp, e.g. fp[3] = fp[1], to manipulate values on the stack, so I am not continually manipulating the stack pointer. If "f" calls another function, it will pass the address of the current top of stack, e.g. g (&f[5]). The advantage to me is that I have a register for a stack pointer even though I am generating portable C code. Now the relationship to three-address code. If you adopt such a scheme, and your three address instructions allow some indexing, you can sometimes generate ADD fp[3],f[4],fp[3] I hope this helps. _______________________________________________________________________________ E.Ireland@massey.ac.nz Evan Ireland, School of Information Sciences, +64 63 69099 x8541 Massey University, Palmerston North, New Zealand. >From pardo@cs.washington.edu Sat Apr 6 14:32:24 1991 From: pardo@cs.washington.edu (David Keppel) Newsgroups: comp.compilers Subject: Re: Portable Fast Direct Threaded Code Keywords: interpreter, performance, design Date: 4 Apr 91 17:10:55 GMT Reply-To: pardo@cs.washington.edu (David Keppel) Organization: Computer Science & Engineering, U. of Washington, Seattle >>>[Threaded code vs. compilation] >pardo@cs.washington.edu (David Keppel) writes: >>[Less than 2:1 performance hit of threading vs. full compilation.] Note also that the reference that claimed 2:1 (Peter M. Kogge, IEEE Computer pp 22-33 March 1982) also attributed part of that ratio to the poor state of compiler optimization. vestal@SRC.Honeywell.COM (Steve Vestal) writes: >[Klint says 2:1 for PDP-11 v. 9:1 for Cyber. > How architecturally dependent are these techniques?] Suppose that the statically-compiled code fragments that are threaded together are called `primitives'. When the execution time of a primitive is large, then the overhead for the interpreter can be large and still have a small effect on performance. The performance of the interpreted code is dominated by the time in a primitive vs. the overhead of moving between primitives. When the execution time of the primitives is small, then the overhead for moving between primitives can be a large fraction of the total execution time. Overhead comes from at least two sources: * Control flow: the address of the the next primitive is loaded from data memory and the processor executes an indirect jump. * Register allocation: a primitive is essentially a function with a fast calling convention (no stack adjustment). Thus, all the traditional problems with interprocedural register allocation. Examples of `large primitives' are ``draw circle'' and ``interpolate spline''. Examplees of small primitives are ``push'', ``add'', etc. * Architectural dependency of control flow Examples: Direct jumps in full compilation: op1 op2 br next // direct jump Indirect jumps for threading for a CISC: op1 op2 br *(r0)+ // load, increment, jump Indirect jumps for threading for a RISC: ld *r0, r1 // scheduled load op1 op2 br *r1 // jump add r1, #4, r1 // delay slot increment Direct jumps in full compilation can frequently use one instruction (a ``near branch'') both to find the address of the next code fragment and perform the control transfer. On a CISC, branches are typically two or three bytes. On a RISC, branches are typically four bytes. The threaded indirect (load, increment, jump) is typically three bytes on a CISC and twelve bytes (three instructions) on a RISC. Direct jumps in full compilation take typically one instruction time. Indirect jumps take at least the following operations: load, increment, jump indirect. On a CISC, the three operations can typically be `folded' in to one instruction. There may be a load penalty of one instruction time but the increment is overlapped, so the total time is three machine units (one `unit' is about one register->register operation). On a RISC, the total penalty is three machine units. Direct jumps take one (I-cache) cycle to fetch both the branch instruction and the address of the branch target. Indirect jumps take a D-cache cycle to fetch the address of the branch target and an I-cache cycle to fetch the branch instruction. Direct jumps can take advantage of instruction prefetching since the address of the next instruction is known at the time that the instruction prefetch reads the direct jump. Threaded indirects require an indirect branch off of a register. Current RISC and CISC machines are about equivalent in that they do little prefetching. Some machines being designed do more prefetching so the threading overhead for them will be greater. * Architectural dependency of register allocation In a machine with a small number of registers, many of the registers are in-use in each primitive and the best possible register allocation will contain many loads and stores. In a machine with a large number of registers, the full-compilation implementation can make much better use of registers than the threaded primitives implementation (again, for small primitives). The savings from full compilation are exactly analagous to the improvements in register allocation from doing inlining of small procedures. * Other points to ponder In some cases the threaded code implementation is substantially smaller than the full-compilation implementation. For large functions or a machine with small caches, the loss of performance from threading might be overwhelmed by the gain in cache performance. On RISC machines, procedure call/return is about twice the cost of other control flow, except for the overhead of register management. Thus, call-dense RISC code from full compilation may behave about the same as threaded code. -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request. >From airs!ian@uunet.UU.NET Sat Apr 6 14:32:56 1991 From: airs!ian@uunet.UU.NET (Ian Lance Taylor) Newsgroups: comp.compilers Subject: Threaded code Keywords: books, interpreter, design Date: 4 Apr 91 07:19:41 GMT Reply-To: airs!ian@uunet.UU.NET (Ian Lance Taylor) Organization: Compilers Central The book ``Threaded Interpretive Languages'' has a quite complete implementation of a threaded version of Forth in Z80 assembler. It's a very complete description of why threaded implementations exist and how to implement them easily. It's by R. G. Loeliger and was published by Byte Books (ISBN 0-07-038360-X). It was published in 1981, though, and I'm sure it's long out of print. Ian Taylor airs!ian@uunet.uu.net uunet!airs!ian -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request. >From firth@sei.cmu.edu Sun Apr 7 14:33:13 1991 From: firth@sei.cmu.edu (Robert Firth) Newsgroups: comp.compilers Subject: Re: Portable Fast Direct Threaded Code Keywords: interpreter, performance, design Date: 4 Apr 91 13:27:21 GMT Reply-To: firth@sei.cmu.edu (Robert Firth) Organization: Software Engineering Institute, Pittsburgh, PA In article <1991Apr3.182334.16164@src.honeywell.com> vestal@SRC.Honeywell.COM (Steve Vestal) writes: >How architecturally dependent is the performance of these techniques >(relative to compiling to native code)? [cost of threaded code on PDP-11, RISC &c] We might have a misunderstanding here, because what I think of as threaded code doesn't have a decoding and interpretation step. But I'll talk of what I know. A program in threaded code is just an array of addresses, possibly interspersed with operands. So the fragment c := a + b becomes something like address of 'load' address of 'a' address of 'load' address of 'b' address of '+' address of 'store' address of 'c' This implies a very simple virtual stack machine - you can get more clever by implementing a virtual register machine. The basic execution thread then does this. We point a global register at the table of addresses, and each primitive has the form treg := treg + address'size ... jump (treg) As you can see, this is great on the PDP-11, since that reduces to one instruction MOV (treg)+,PC ; NOTE TO MAINTAINER: FASTER THAN JMP - DON'T TOUCH! On a typical RISC machine, it's two cycles, since you can put almost anything in the delay slot(s) after the jump. Now, the load instruction, for instance, would say load: treg := treg + address'size load (treg) into tempreg treg := treg + address'size push (tempreg) onto simulated stack jump (treg) On the PDP-11, that's MOV @(treg)+, -(SP) MOV (treg)+, PC On a RISC, it's much more like L R0, 4(treg) ; get operand address L R0, 0(R0) ; dereference to get operand SUBI SP, #4 ; decrement simulated SP S R0, 0(SP) ; push operand on stack ADDI treg, #8 ; step over two addresses (mine & operands) JR (treg) ; over to you, Moriarty! [to fill delay slots, shuffle the above to 132564] Well, if you have one load delay slot and one branch delay slot, you can fill all three of them, so that's 6 cycles. Given that a typical load is only 1.1 cycles in direct code (90% of the delays filled), this is certainly a lot more than a 2:1 overhead! When you add the cost of a simulated stack (lots of needless loads and stores), I can well believe 10:1 time expansion for simple code. In fact, it was more than that on the PDP-11, if you compared threaded code with direct code from a decent compiler. The big win in the Fortran compiler came from (a) very compact threaded code, and (b) the floating point operations were implemented in software, so the overhead of threaded code was swamped by the cost of floating addition, subtraction &c. Here's the full code of the above example, so you can see for yourself Direct: MOV a, R0 ADD b, R0 MOV R0, c Threaded: MOV @(treg)+, -(SP) MOV (treg)+, PC * MOV @(treg)+, -(SP) * MOV (treg)+, PC * ADD (SP)+,(SP) MOV (treg)+, PC MOV (SP)+, @(treg)+ MOV (treg)+, PC Note that, if you implement a one-address add, you save two instructions, since the *** bit reduces to ADD @(treg)+, (SP) But even then, it's coming out at over 4:1. What architectural features make threaded code more efficient? The fundamental one is main memory that is fast (or not too slow) relative to registers, since you're doing a lot more fetching. Another is a set of address modes with double indirection, since you're accessing most operands one level of indirection further back. And good old autoincrement helps a little, too. Alas, none of that says 'risc', and much of it says '1960s'. Incidentally, if I were to do this again today, I'd definitely simulate a general-register machine and use a subset of the real machine's registers. If you take 8 of them, you then have 8 loads and stores, one for each register, but if you make an absolute rule that nobody even thinks about touching one of those 8 that doesn't belong to him, then all the good tricks about register allocation, slaving &c will still work. If you then implement the operations as one-address general-register, you have again 8 versions (add into R0, add into R1, ...) and lo! you're programming a very familiar old friend. "But that was in another country, and besides, the machine is dead..." Robert Firth -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request. >From bpendlet@bambam.es.com Tue Apr 9 20:35:22 1991 From: bpendlet@bambam.es.com (Bob Pendleton) Newsgroups: comp.compilers Subject: Re: Portable Fast Direct Threaded Code Keywords: interpreter, design Date: 8 Apr 91 19:48:00 GMT Reply-To: bpendlet@bambam.es.com (Bob Pendleton) Organization: Compilers Central In article <23613@as0c.sei.cmu.edu> you write: > A program in threaded code is just an array of addresses, possibly > interspersed with operands. So the fragment > > c := a + b > > becomes something like > > address of 'load' > address of 'a' > address of 'load' > address of 'b' > address of '+' > address of 'store' > address of 'c' > > This implies a very simple virtual stack machine - you can get more clever > by implementing a virtual register machine. About 10 years ago I was working on a lisp compler that compiled to threaded code. I was trying to get small code and still have some performance. (Since I wanted to run the code on a Z80 or 8080 small was important. My how things change :-) I found that the 3 most common operations in threaded code were load, store, and execute. So I put those operations with the operands. This made the operands look rather like classes with load, store, and execute as virtual functions. If you let the evaluate operation subsume the load and execute operations the threaded code for c := a + b; becomes address of 'a.evaluate()' address of 'b.evaluate()' address of '+' address of 'c.store()' and g := F(x, y); becomes address of 'x.evaluate()' address of 'y.evaluate()' address of 'F.evaluate()' address of 'g.store()' Which is much smaller than the original version of threaded code. Later, while working on a homebrew version of FORTH I gave up on threaded code completely. I found, like most who have expolored it, that symbolic execution of RPN code is a nice way to generated machine code. Machine code that runs much faster than threaded code, and that the machine code, even on an 8080, was only about 25% bigger than threaded code. -- Bob Pendleton bpendlet@dsd.es.com or decwrl!esunix!bpendlet or utah-cs!esunix!bpendlet [The DEC PDP-11 Fortran compiler did something similar, writing load routines for commonly used variables. -John] -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request. >From pardo@june.cs.washington.edu Wed Apr 24 09:26:32 1991 From: pardo@june.cs.washington.edu (David Keppel) Newsgroups: comp.compilers Subject: Re: Fast Interpreted Code Keywords: interpreter, threaded code Date: 23 Apr 91 02:06:21 GMT Reply-To: pardo@june.cs.washington.edu (David Keppel) Organization: Computer Science & Engineering, U. of Washington, Seattle ssinghani@viewlogic.com (Sunder Singhani) writes: >[Our threaded code isn't fast enough. What's faster?] As far as I know, threaded code gives the fastest primitives/second dispatch rate on a variety of architectures. The general techniques for making things faster (that I know of!) are to change things so that the dispatch rate can go down without changing the work that gets done (or use hardware, but we'll ignore that for the moment.) * Use a different v-machine instruction set The overhead of interpreting is almost nothing in generic PostScript imaging code because all the time is spent in non-interpretded primitives. If you can characterize your key operations (perhaps info in [Davidson & Fraser ??, Fraser, Myers & Wendt 84] can help you analyze for common operations instead of the more normal time in routines) then you can re-code your virtual instruction set to have as primintives oeprations that are performed frequently. * Dynamic compilation to native machine code This is what is done in ParcPlace System's Smalltalk-80 implementation, [Deutsch & Schiffman 84] also Insignia Solution's 8086 interpreter. Dynamic compilation suffers from the need to do compilation at runtime: a compiler that produces better code will take longer to run and the compile time contributes to the overall program runtime. Also, program text isn't shared, even if multiple instances are running simultaneously. * Native-coding key routines If you believe that your program spends 80% of its time in a few key routines, then compiling just these routines -- statically, adding them to the primitive set, statically adding them as library routines, or dynamically -- can improve performance substantially [Pittman 87]. 5 Citations follow: %A Robert Bedichek %T Some Efficient Architecture Simulation Techniques %J Winter '90 USENIX Conference %D 26 October, 1989 %W Robert Bedichek. %W Pardo has a copy. %X Describes a simulator that uses threaded-code techniques to emulate a Motorola 88000. Each 88k instruction is executed in about 20 host (68020) instructions. Discusses techniques used to get the simulation down from several thousand host instructions in many other simulators. %A Jack W. Davidson %A Chris W. Fraser %T Eliminating Redundant Object Code %J POPL9 %P 128-132 %A Peter Deutsch %A Alan M. Schiffman %T Efficient Implementation of the Smalltalk-80 System %J 11th Annual Symposium on Principles of Programming Languages (POPL 11) %D January 1984 %P 297-302 %X Dynamic translatin of p-code to n-code (native code). Resons for not using straight p-code or straight n-code: * p-code is smaller than n-code (<= 5X). * The debugger can debug p-code, improving portability. * Native code is faster (<= 2X). Reasons include special fetch/decode/dispatch hardware; p-machine and n-machine may be very different, e.g., stack machine vs. register-oriented. * Threaded code does reduce the cost of p-code fetch/decode. Does not help with operand decoding. Does not allow optimizations to span more than one instruction. [pardo: that's not technically true, but each optimized instruction must exist in addition to the unoptimized version. That leads to exponential blowup of the p-code. Example: delayed branch and non-delayed branch versions of Robert Bedichek's 88k simulator.] The system characteristics: * The time to translate to n-code via macro expansion is about the same as the execute time to interpret the p-code. * (pg 300:) Self-modifying code (SMC) is deprecated but used in a ``well-confined'' way. Could indirect at more cost. Use SMC on the machines where it works, indirection where SMC. doesn't. * Performance is compared to a ``straightforward'' interpreter. What's that? %A Christopher W. Fraser %A Eugene W. Myers %A Alan L. Wendt %T Analyzing and Compressing Assembly Code %J CCC84 %P 117-121 %A Thomas Pittman %T Two-Level Hybrid Interpreter/Native Code Execution for Combined Space-Time Program Efficiency %D 1987 %J ACM SIGPLAN %P 150-152 %X Talks about native code execution vs. various kinds of interpreting and encoding of key routines in assembly. Hope this helps! ;-D on ( This is all open to interpretation ) Pardo -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request. >From eliot@cs.qmw.ac.uk Tue Apr 30 15:55:17 1991 From: eliot@cs.qmw.ac.uk (Eliot Miranda) Newsgroups: comp.compilers,gnu.gcc.bug,alt.sources Subject: re: Threaded Code Keywords: design, interpreter Date: 5 Apr 91 11:43:51 GMT Reply-To: Eliot Miranda Followup-To: comp.compilers Organization: Computer Science Dept, QMW, University of London, UK. I recently posted articles to comp.compilers & alt.sources on how to write threaded code machines in C. I received the following questions from Simon Peyton Jones at Glasgow. They are specific to GCC. Since they have non-obvious answers & since the answers suggest augmentation of the GCC compiler I'm posting my response to Simon. >From: Simon L Peyton Jones > >I saw your article about threaded code. Like you and others, we are >using C as an assembler, only for a pure functional language, Haskell. >I have some brief questions. > >1. By telling GCC not to use a frame pointer, one can eliminate >the prolog entirely, can't one? So why edit it out? No, registers local to the procedure will still be saved & stack space allocated for automatic variables. This IS a problem since the threaded-code jump at the end of the procedure will miss the register restores before the epilogue. Consequently the stack will grow unless these register saves & stack-space allocations are removed. Also GCC can not always eliminate the frame pointer. >I guess the answer is going to be local variables, allocated once for >all by the StartTCMachine routine. Still, it seems quite a pain. I guess >one could sacrifice some (perhaps slight) speed by using a bunch of >globals instead. For certain routines, not using register variables will be expensive (e.g. a simple integer arithmetic primitive). >2. You edit out the epilogue for tidiness only, I take it. It doesn't >cause any problems if you leave it in, does it? No, but given that the prologue has to be removed & removing the epilogue is as easy (& given finite memory :-) one might as well remove it. > >3. Why do you use no-defer-pop (with the associated bug)? OK. This is again to avoid stack growth. On conventional stack architectures gcc will try & combine the argument popping code of a sequence of procedure calls. e.g. extern long a, b, c; void doit() { foo(a); bar(b); baz(c); } with -O -no-defer-pop one might expect gcc to generate link %a6,#0 movel a,%sp@- jbsr foo addqw #4,%sp movel b,%sp@- jbsr bar addqw #4,%sp movel c,%sp@- jbsr baz addqw #4,%sp unlk %a6 rts but because gcc knows that the unlk instruction will roll back the stack in fact gcc generates: link %a6,#0 movel a,%sp@- jbsr foo addqw #4,%sp movel b,%sp@- jbsr bar addqw #4,%sp movel c,%sp@- jbsr baz unlk %a6 rts With -O -fdefer-pop gcc optimizes out the pops completely & generates: link %a6,#0 movel a,%sp@- jbsr foo movel b,%sp@- jbsr bar movel c,%sp@- jbsr baz unlk %a6 rts with -O -fomit-frame-pointer -fdefer-pop gcc generates: movel a,%sp@- jbsr foo movel b,%sp@- jbsr bar movel c,%sp@- jbsr baz addw #12,%sp rts & with -O -fomit-frame-pointer -fno-defer-pop gcc generates: movel a,%sp@- jbsr foo addqw #4,%sp movel b,%sp@- jbsr bar addqw #4,%sp movel c,%sp@- jbsr baz addqw #4,%sp rts All the above cases are as one would wish. The elimination of all defered pops in the unlk instruction is especially clever. However, in the presence of the threaded-code jump the waters darken! Consider what gcc generates for: register void (**tcip)() asm("%a5"); #define JUMPNEXT do{asm("movl %a5@+,%a0; jmp %a0@");return;}while(0) extern long a, b; void doit() { foo(a); bar(b); JUMPNEXT; } with -O -fdefer-pop gcc generates doit: link %a6,#0 movel a,%sp@- jbsr foo movel b,%sp@- jbsr bar #APP movl %a5@+,%a0; jmp %a0@ #NO_APP unlk %a6 rts This is clearly no good because the arguments to both foo & bar will never be popped. Every time doit() is executed the stack will grow by 8 bytes. Soon your program will dump core with a very large stack segment! with -O -fno-defer-pop gcc generates: link %a6,#0 movel a,%sp@- jbsr foo addqw #4,%sp movel b,%sp@- jbsr bar #APP movl %a5@+,%a0; jmp %a0@ #NO_APP unlk %a6 rts Again useless because bar's pop has been folded into the unlk which won't be executed. with -O -fdefer-pop -fomit-frame-pointer gcc generates movel a,%sp@- jbsr foo movel b,%sp@- jbsr bar addqw #8,%sp #APP movl %a5@+,%a0; jmp %a0@ #NO_APP rts This is great. However, not all functions are susceptible to the omit-frame-pointer optimization (i.e. functions with local variables). E.g. the code generated for: register void (**tcip)() asm("%a5"); #define JUMPNEXT do{asm("movl %a5@+,%a0; jmp %a0@");return;}while(0) extern long a, b; void doit() { char large[1024]; foo(a,large); bar(b); JUMPNEXT; } with -O -fomit-frame-pointer -fdefer-pop is: link %a6,#-1024 pea %a6@(-1024) movel a,%sp@- jbsr foo movel b,%sp@- jbsr bar #APP movl %a5@+,%a0; jmp %a0@ #NO_APP unlk %a6 rts so in general one can't rely on -fomit-frame-pointer. For the above example both -O -fomit-frame-pointer -fno-defer-pop and -O -fno-defer-pop generate: doit: link %a6,#-1024 pea %a6@(-1024) movel a,%sp@- jbsr foo addqw #8,%sp movel b,%sp@- jbsr bar #APP movl %a5@+,%a0; jmp %a0@ #NO_APP unlk %a6 rts This is also useless because bar's argument pop has been folded away. The problem is that gcc will always fold away the last call's argument pop if the function has a frame pointer, and -fomit-frame-pointer can't allways get rid of the frame pointer. In fact, in the presence of variable sized automatic variables or calls on alloca it would be very hard (impossible for recursive functions?) to do. The neatest solution I've come up with is to use -fno-defer-pop and a dummy function call between the threaded-code jump and the return: register void (**tcip)() asm("%a5"); #define JUMPNEXT do{asm("movl %a5@+,%a0; jmp %a0@");SBD();return;}while(0) extern long a, b; void doit() { foo(a); bar(b); JUMPNEXT; } with -O -fno-defer-pop gcc generates: link %a6,#0 movel a,%sp@- jbsr foo addqw #4,%sp movel b,%sp@- jbsr bar addqw #4,%sp #APP movl %a5@+,%a0; jmp %a0@ #NO_APP jbsr SBD unlk %a6 rts Now bar's argument pop is not folded because its no longer the last call in the routine, SBD is. So the call to SBD a) prevents gcc's 'last call argument pop fold into unlk' optimization which prevents uncontrolled stack growth. b) doesn't get executed because of the jump c) is trivial to remove from the assembler with a sed-script One an try to use -fcaller-saves, but this surrounds calls with unnecessary register saves & restores that for the code to be optimal have to be edited out. >4. Why does JUMPNEXT have a loop? Surely the jump leaves the loop right >away. Presumably you are tricking the compiler somehow. This is old C lore. The problem is 'How do you write a macro that is a sequence of statements that can be used wherever a single statement can?' take the following definition of JUMPNEXT: #define JUMPNEXT asm("movl %a5@+,%a0; jmp %a0@");return; Now invoke it here: if (its_time_to_jump) JUMPNEXT; do_something_else(); This expands to: if (its_time_to_jump) asm("movl %a5@+,%a0; jmp %a0@"); return; do_something_else(); Not at all whats intended! There are two tricks I know of (the first I saw in Berkely Smalltalk, the second in Richard Stallman's gcc manual. I expect they're both quite old). The first is to surround your statements with if (TRUE){statements}else i.e. #define JUMPNEXT if(1){asm("movl %a5@+,%a0; jmp %a0@");return;}else So now we get: if (its_time_to_jump) if (1){ asm("movl %a5@+,%a0; jmp %a0@"); return; else; do_something_else(); which works because C binds elses innermost first. However, some compilers will whine about dangling elses. The second scheme is more elegant (-: Surround your statements with do{statements}while(FALSE); which will execute statements precisely once (its NOT a loop). i.e. #define JUMPNEXT do{asm("movl %a5@+,%a0; jmp %a0@");SBD();return;}while(0) expands to if (its_time_to_jump) do { asm("movl %a5@+,%a0; jmp %a0@"); return; while(0); do_something_else(); which does what's wanted and doesn't incur compiler whines. >Thanks > >Simon L Peyton Jones, Glasgow University More and more people are taking the 'use C as an assembler' route, and more and more people are using GCC to do it (because its code quality is good, it had global register variables, and it has an excellent asm facility). The threaded-code in C idea is also becomming more popular. But as the code above demonstrates, one does have to side-step optimizations and develop system-specific assembler editing scripts. I'd like to ask Richard Stallman & the GCC development team for -fno-prolog -fno-epilog flags that instruct gcc to generate a) no register saves or restores b) no automatic variable allocation c) no procedure linkage/frame creation Then the optimal 'Threaded-Code Machine in GCC C' can be compiled without any assembler editing scripts at all. Also nice would be a way of telling GCC that an asm statement changed the flow of control so GCC could a) warn about not-reached code b) eliminate unnecessary code (do more code folding) -- Eliot Miranda email: eliot@cs.qmw.ac.uk Dept of Computer Science Tel: 071 975 5229 (+44 71 975 5229) Queen Mary Westfield College ARPA: eliot%cs.qmw.ac.uk@nsf.ac.uk Mile End Road UUCP: eliot@qmw-cs.uucp LONDON E1 4NS -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request. >From brennan@bcsaic.boeing.com Sat May 4 11:28:41 1991 From: brennan@bcsaic.boeing.com (Michael D Brennan) Newsgroups: comp.compilers Subject: re: Threaded code Keywords: interpreter, design Date: 2 May 91 19:50:23 GMT Reply-To: brennan@bcsaic.boeing.com (Michael D Brennan) Organization: Boeing Aerospace & Electronics, Seattle WA Another method for obtaining threaded byte code for an interpreter is to edit the assembler output of a big switch rather than editing the prologue and epilogue off functions calls. You don't need gcc, global vars in registers, works with smart and dumb compilers, and all optimization can be turned on. For example: This C routine executes (unthreaded) byte code for an interpreter that can add, subtract and print. #define HALT 0 #define PUSH 1 #define ADD 2 #define SUB 3 #define PRINT 4 static int stack[32] ; void execute(code_ptr) register int *code_ptr ; { register int *stack_ptr = stack - 1 ; while ( 1 ) { switch( *code_ptr++ ) { case HALT : return ; case PUSH : * ++ stack_ptr = *code_ptr++ ; break ; case ADD : stack_ptr-- ; *stack_ptr += stack_ptr[1] ; break ; case SUB : stack_ptr-- ; *stack_ptr -= stack_ptr[1] ; break ; case PRINT : printf("%d\n", *stack_ptr--); break ; } } } ------------------------------------------------------- to interpret 2 + (3 - 4) the front end "compiles" in int code[] PUSH, 2, PUSH, 3, PUSH, 4, SUB, ADD, PRINT, HALT and calls execute(code). ------------------------------------------------------ The difference between this and the threaded code discussed over the last few weeks is the switch gets compiled as jmp TABLE[ *code_ptr++ ] where TABLE is the jump table generated by the compiler which holds the addresses of the case labels. With threading, the transitions between functions become jmp *code_ptr++ but this is easy to get by editing the assembler output to export the case label and recode the switch. -------------------------------------------------- For example on a SPARC: code_ptr is %o0 stack_ptr is %i5 ..... ! case PUSH L77004: ld [%i0],%o1 inc 4,%i5 inc 4,%i0 b L77008 st %o1,[%i5] ..... ! the switch, doesn't change structure ! as you add new op codes L77008: mov %i0,%i4 ld [%i4],%i4 inc 4,%i0 cmp %i4,4 bgu L77008 sll %i4,2,%i4 sethi %hi(L2000000),%o1 or %o1,%lo(L2000000),%o1 ! [internal] ld [%i4+%o1],%o0 jmp %o0 nop L2000000: ! the jump TABLE .word L77003 ! HALT etc .word L77004 .word L77005 .word L77006 .word L77007 ------------------------------------------- modify by adding global labels and edit the switch ..... ! case PUSH _push : L77004: ld [%i0],%o1 inc 4,%i5 inc 4,%i0 b L77008 st %o1,[%i5] ..... ! the edited switch L77008: mov %i0,%i4 ld [%i4],%i4 inc 4,%i0 jmp %i4 nop ! remove TABLE ------------------------------------------- For another example on an Intel 8088 stack_ptr is si code_ptr is di ; while ( 1 ) ; { ; switch( *code_ptr++ ) ; @1@50: mov bx,di inc di inc di mov bx,word ptr [bx] cmp bx,3 ja short @1@50 shl bx,1 jmp word ptr cs:@1@C738[bx] @1@122: ; ; case PUSH : ; * ++ stack_ptr = *code_ptr++ ; ; inc si inc si mov ax,word ptr [di] mov word ptr [si],ax inc di inc di ; ; break ; ; jmp short @1@50 ; .... @1@C738 label word ; jump TABLE dw @1@194 ; HALT dw @1@122 ; PUSH etc dw @1@146 .... ------------------------------------------------ edited the jump can be computed inline ; while ( 1 ) ; { ; switch( *code_ptr++ ) ; @1@50: ; switch code is replaced by code only executed once inc di inc di jmp [di-2] ..... _push : @1@122: ; ; case PUSH : ; * ++ stack_ptr = *code_ptr++ ; ; inc si inc si mov ax,word ptr [di] mov word ptr [si],ax inc di inc di ; ; break ; ; inc di ; jmp to *code_ptr++ inline inc di jmp [di-2] ; .... ---------------------------------------------- the "front end" has defines typedef void (*TCODE)() ; extern void halt(), push(), add(), sub(), print() ; TCODE code[CODESIZE] ; in the array code[], the front end compiles push, 2, push, 3, push, 4, sub, add, print, halt and calls execute(code). -- Mike Brennan brennan@bcsaic.boeing.com -- Send compilers articles to compilers@iecc.cambridge.ma.us or {ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request.