Re: [gambit-list] Need help on understanding GVM bytecode

-- Meng Zhang Sent with Sparrow (http://www.sparrowmailapp.com/?sig) On Wednesday, December 7, 2011 at 2:53 AM, Marc Feeley wrote: > > On 2011-12-06, at 2:26 AM, Meng Zhang wrote: > > > Hi everyone, > > > > I'm trying to understand the GVM bytecode, while I got some problem on understanding its handling > > of stack frames. > > > > In the paper <A Parallel Virtual Machine for Efficient Scheme Compilation: > > .... JUMP and COND instructions cause the stack pointer to be recalculated, while LABEL > > instructions recalculated the frame pointer... > > > > While I can hardly understand these description, with the ".gvm" I can hardly understand how backend > > should do with given instruction. > > > > I do read the the c backend implementation, it uses one "fp" pointer and calculate stackpointer based > > on that. But the other operations the it uses is too difficult to understand without any documents, so > > I'll be grateful if anyone could give me a concrete example on gambit's stack handling. > > I agree that the description in the paper is not very clear. The basic idea is that the manipulation of the stack is expressed implicitly in GVM. In other words, there are no push and pop operations, and no direct manipulation of a stack pointer. This has the advantage that the back-end has some liberty on how to implement the stack. Among other things, it can grow the stack upward or downward, whichever is most convenient, or faster, or matches the processor's stack handling. > > Let me explain with an example. Here's some Scheme code for the factorial function: > > ------------------------------------------------------------------------------ > (declare > (standard-bindings) > (not safe) > (block) > (not inline) > (not interrupts-enabled) > ) > > (define (fact n) > (if (fx= n 0) > 1 > (fx* n (fact (fx- n 1))))) > ------------------------------------------------------------------------------ > > This can be compiled to a textual representation of the GVM code by adding the flag -gvm to gsc's command-line options. The GVM code for the fact function is: > > ------------------------------------------------------------------------------ > #1 0 entry-point 1 () ; +0=# +1=n > if (##fx= +1 '0) jump 0 #3 else #2 ; +0=# +1=n > > #2 0 ; +0=# +1=n > -1 = +0 ; -1=# +1=n > -2 = +1 ; -1=# -2=n +1=n > +1 = (##fx- +1 '1) ; -1=# -2=n +1=. > +0 = #4 ; -1=# -2=n +0=. +1=. > -3 = . ; -1=# -2=n -3 +0=. +1=. > -4 = . ; -1=# -2=n -3 -4 +0=. +1=. > -5 = . ; -1=# -2=n -3 -4 -5 +0=. +1=. > -6 = . ; -1=# -2=n -3 -4 -5 -6 +0=. +1=. > -7 = . ; -1=# -2=n -3 -4 -5 -6 -7 +0=. +1=. > -8 = . ; -1=# -2=n -3 -4 -5 -6 -7 -8 +0=. +1=. > if (##fx= +1 '0) jump 8 #3 else #2 ; -1=# -2=n -3 -4 -5 -6 -7 -8 +0=. +1=. > > #3 0 ; +0=# > +1 = '1 ; +0=# +1=. > jump 0 +0 ; +1=. > > #4 8 return-point ; -1=# -2=n -3 -4 -5 -6 -7 -8 +1=. > +1 = (##fx* -2 +1) ; -1=# -2 -3 -4 -5 -6 -7 -8 +1=. > jump 0 -1 ; +1=. > ------------------------------------------------------------------------------ > > This GVM code contains 4 basic blocks, labelled #1 to #4. The basic block #1 is the entry point of fact. On the right side, we can see the assignment of variables to the registers and stack slots. On entry, GVM register 0 (i.e. +0) contains the return address (i.e. #), and GVM register 1 (i.e. +1) contains the parameter n. > > The first line of each basic block gives some details on the nature of the basic block (is it a procedure entry-point, a return-point of a call, or a plain basic-block?). It also gives, immediately after the label, the frame size at the beginning of that block. You will notice that this is consistent with the assignment of variables on the right side. For example, block #4 has a frame size of 8, and in that frame only slots 1 and 2 (i.e. the -1 and -2) are live, containing respectively the return address and variable n. Why so much wasted space? Simply to align frames and leave space for linking the frames (needed for implementing first-class continuations, but that is a different story which I won't explain here). > > All basic blocks end with a jump instruction of some kind, in this case either unconditional (i.e. jump <fs> <dest>) or conditional (i.e. if ... jump <fs> #n else #m). The parameter <fs> of these instructions indicates the frame size at the end of the block (when the jump is executed). It accounts for any expansion or contraction of the frame. > > For example block #2 begins with a frame size of 0 and ends with a frame size of 8. That's because 8 slots have been allocated on the stack. In particular, the return address and n have been stored to the stack (the other slots are those reserved for call/cc and alignment). > > Block #4 is the reverse case... beginning with a frame size of 8 and ending with a frame size of 0. That's because 8 slots have been removed from the stack. > > Implementing this efficiently on most machines can be done by updating the value of the stack pointer (SP) at the jump instructions. The adjustment is the difference between the frame size at the end of the block and the frame size at the beginning of the block. All stack accesses within a block can be done relative to the SP: when accessing the stack slot N (the notation -N in the GVM code), you have to access stack[SP+N-fs], where fs is the frame size at the beginning of the block. > > Is that clearer? > > Marc