The Assembly Code

The compiler produces assembly code for a very simple computer.
It has three registers: a stack pointer (SP) a frame pointer 
(FP) and a program counter (PC). The program counter contains 
the address of the next instruction to be executed. The stack 
grows from low addresses into high addresses as things are 
pushed. All calculations are done on the stack. Ints and floats 
occupy four bytes. All instructions have either one operand or
none at all. In the following description:

  mem[n]    represents the contents of the four bytes of 
                      memory starting at location n. 
  Push(x)   is an abbreviation for    mem[SP]=x; SP=SP+1
  x=Pop()   is an abbreviation for    SP=SP-1; x=mem[SP]

  opd represents any operand; operands may be:
      a number (fixed or floating point)
      a label, representing a memory address
      FP+n, representing the memory address n bytes 
                                above the Frame Pointer
      @opd, representing the address of operand opd.

LOAD  opd   Push(mem[opd])      push memory content onto stack
STOR  opd   mem[opd]=mem[SP-1]  store value from top of stack in memory.
                                 not popped
LOADN opd   Push(opd)           push (integer) constant onto stack
LOADF opd   Push(opd)           push (floating point) constant onto stack
POP         Pop()                   remove something from the stack and ignore it
STI         b=Pop(); a=Pop(); mem[a]=b; Push(b)   “Store indirect”
LDI         a=Pop(); b=mem[a]; Push(b)            “Load indirect”
DUP         a=mem[SP-1]; Push(a)            duplicate value on top of stack
ADD         b=Pop(); a=Pop(); Push(a+b)     pop two ints, add them, push the result
ADDF        b=Pop(); a=Pop(); Push(a+b)     same as above, but floating point,
SUB         b=Pop(); a=Pop(); Push(a-b)     pop two ints, subtract them, push the result
SUBF        b=Pop(); a=Pop(); Push(a-b)     same as above, but floating point,
MUL         b=Pop(); a=Pop(); Push(a*b)     pop two ints, multiply them, push the result
MULF        b=Pop(); a=Pop(); Push(a*b)     same as above, but floating point,
DIV         b=Pop(); a=Pop(); Push(a/b)     pop two ints, divide them, push the result
DIVF        b=Pop(); a=Pop(); Push(a/b)     same as above, but floating point,
MOD         b=Pop(); a=Pop(); Push(a%b)     pop two ints, divide them, push the remainder
FLOAT       i=Pop(); f=(float)i; Push(f)    pop a integer, convert to a float, and push it back
FIX         f=Pop(); i=(int)f; Push(i)      pop a float, convert to an int, and push it back
NOT         a=Pop(); if (a==0) Push(1) otherwise Push(0)
AND         b=Pop(); a=Pop(); if a and b are both 1 Push(1) otherwise Push(0)
OR          b=Pop(); a=Pop(); if either a or b are 1 Push(1) otherwise Push(0)
EQL         b=Pop(); a=Pop(); if (a==b) Push(1) otherwise Push(0)
EQLF            same as above, but floating point
NEQ         b=Pop(); a=Pop(); if (a==b) Push(0) otherwise Push(1)
NEQF            same as above, but floating point
LSS         b=Pop(); a=Pop(); if (a<b) Push(1) otherwise Push(0)
LSSF            same as above, but floating point
GTR         b=Pop(); a=Pop(); if (a>b) Push(1) otherwise Push(0)
GTRF            same as above, but floating point
LEQ         b=Pop(); a=Pop(); if (a>b) Push(0) otherwise Push(1)
LEQF            same as above, but floating point
GEQ         b=Pop(); a=Pop(); if (a<b) Push(0) otherwise Push(1)
GEQF            same as above, but floating point
INCSP opd   SP=SP+opd     increment the stack pointer
DECSP opd   SP=SP-opd     decrement the stack pointer
INCFP opd   FP=FP+opd     increment the frame pointer
DECFP opd   FP=FP-opd     decrement the frame pointer
JUMP  opd   PC=opd        unconditional jump to label
PJZ   opd   x=Pop(); if (x==0) PC=opd pop an integer; if it is zero jump to label
POPJMP      PC=Pop()      pop an address from the stack and jump there
POPFP       FP=Pop()      pop new value for the frame pointer from the stack
LDFP        Push(FP)      push the frame pointer onto the stack
INIT        FP=k; SP=k    stack pointer and frame pointer both initialised to
                          address of the base of the stack.

So, for example, if cat, bat, and hat are global/static integer variables, 
then cat=1+bat*3+hat*5 could be translated into
    LOADN 1
    LOAD  bat
    LOADN 3
    MUL
    ADD
    LOAD  hat
    LOADN 5
    MUL
    ADD
    STOR  cat
    POP
On the other hand, if variables are local, living in the current stack 
frame, they will be accessed relative to the frame pointer, so  
{ int a,b; a=7; b=a*2; a=a+a*b; }  could be translated as follows 
(the first operation is to increase SP to “reserve” space for the 
two variables; the last operation puts SP back again to “release”
that space, we assume that SP is initially 4 more than FP):
    INCSP 8
    LOADN 7
    STOR  FP+4
    POP
    LOAD  FP+4
    LOADN 2
    MUL
    STOR  FP+8
    POP
    LOAD  FP+4
    LOAD  FP+4
    LOAD  FP+8
    MUL
    ADD
    STOR  FP+4
    POP
    DECSP 8

The assembly code provides only the minimum set of instructions 
required to make everything possible. It has no special 
instructions for handling functions, those operations have to 
be made from simpler parts. To call the function f with two 
parameters, 3 and x*2, we must construct a stack frame for f 
by hand. First the current frame pointer is saved, then the return 
address is pushed (we have to use a label to get this address),
then the parameters are evaluated and pushed onto the stack. The 
new stack frame will start at the location containing the return
address, so the parameters are being put in their correct places in 
the new frame. Once the parameter values are in place in the new
frame, the FP is moved up to point to the beginning of the 
new frame.

f(3,x*2) becomes
    LDFP       -- push current frame pointer for safe keeping
    LOAD  @L1  -- save return address. This will be the base of the new frame
    LOADN 3    -- put value 3 in the right place in the new frame (recall that the
    LOAD  x    -- first parameter is the first local variable, so it goes in
    LOADN 2    -- the first position
    MUL        -- put x*2 in place in the new frame, the second position
    INCFP 16   -- assuming there are 16 bytes in the current stack frame
    JUMP  f
L1: POPFP
    LOAD  RESULT

The called function is responsible for removing its local 
variables and parameters from the stack; it must also save
its result in a global variable called RESULT, pop its own
return address from the stack, and jump back to it. After
doing all of that, the whole of the new stack frame will
have been dismantled, leaving only the old frame pointer
that we saved right at the beginning, so recovering the
old FP and pushing the result on the stack is all that is
required to complete the function call.

The called function must make its own space for local variables
when it is called, and before exitting it must reduce the stack 
pointer to deallocate all local variables and parameters, then
finally pop the return address and jump to it.

int f(int a, int b)      
{ int x;       
   x=a*a+b*b;    
   return (x+1); }
becomes
      F:  INCSP 4     -- make space for new local
          LOAD  FP+4  -- a is first thing in the stack frame
          LOAD  FP+4  -- and again
          MUL         -- that makes a squared
          LOAD  FP+8  -- b is the second thing in the stack frame
          LOAD  FP+8
          MUL
          ADD
          STOR  FP+12 -- x is the third thing in the stack frame
          POP
          LOAD  FP+12
          LOADN 1
          ADD
          STOR  RESULT
          POP
          DECSP 12    -- remove locals and parameters
          POPJMP      -- pop return address and jump there

Conditionals are easy, I’ll illustrate one with a while loop,
this time we’ll assume that all the variables are globals, so
    fac=1; while (n>=0) { fac=fac*n;  n=n-1; }
calculating the factorial of n, looks like this:

    LOADN 1
    STOR  FAC
L5: LOAD  N   -- label for going round again
    LOADN 0
    GTR
    PJZ   L6  -- pop the result of (n>=0) and jump if its zero
    LOAD  FAC
    LOAD  N
    MUL
    STOR  FAC
    POP
    LOAD  N
    LOADN 1
    SUB
    STOR  N
    POP
    JUMP  L5
L6:          -- all finished