Inter - a stack machine

The target machine for your compiler is a simple stack machine. The machine is organized so code and data are in separate address spaces. The address space for data is further subdivided into a stack and an area for global data. The stack grows toward higher addresses. Instructions that access memory (e.g., rvalue) has access to the entire data address space, so memory locations on the stack can be accessed independently of the stack pointer.

The stack machine has been realized as an interpreter called inter. The interpreter has the following properties:

All instruction names are written in lower case.
Function names can contain lower and upper case letters, but the interpreter is case sensitive: It distinguishes between lower and upper case, so FOO and foo are not the same name.
Max. code size is 4096 instructions.
Max. data size (number of registers) is 1024 (addresses 0--1023).
Max. stack size is 4096 elements (addresses 1024--5119).
The stack pointer is 1024 when the interpreter starts.

The inter memory model

Instruction set

Boolean values are represented by integers, as in C: The value 0 is interpreted as false, and all other values are interpreted as true. The machine uses strings as labels identifying procedures (represented as L in the table below). It also uses integers (represented as c and i).

Everything from two minus signs (--) to the end of the line is considered a comment. Comments can be used to add explanation or debugging information to generated code.

The instruction set is as follows:

Instruction	Explanation
`label` L	Label. Names a location in the program; has no other meaning
`goto` L	Continue executing from label L.
`gofalse` L	Pop one value off the stack. If the value is false, continue executing from label L.
`call` L	Push current program counter onto the stack and continue executing from label L.
`ret`	Return from a routine. Pop a program address from the stack and continue executing from there.
`end`	This instruction marks the end of the code. The interpreter will ignore all code after `end`.

Instruction	Explanation
`push` c	Push the constant integer c onto the stack.
`pop`	Remove the value on the top of the stack.
`lvalue` i	Push the address i onto the stack. (Same as `push` i.)
`rvalue` i	Fetch the value at location i and push it onto the stack.
`rvaltop`	Pop the top value off the stack, consider the value an address (like i in the `rvalue` instruction) and push the value stored in that location onto the stack. This instruction enables indirection (e.g., `*p` in Pascal).
`pushsp`	Push the current value of the stack pointer (i.e., the address to the top of the stack) onto the stack. The interpreter first looks at the stack pointer and then pushes it; thus, the address pushed is the value of the stack pointer before the `pushsp` instruction.
`swap`	Swap the stack's top two values.
`:=`	Pop two values off the stack: first an value, then an address. Copy the value to the memory location at the address.

Instruction	Explanation
`write`	Pop a value off of the stack and print it.
`read`	Read a value and push it onto the stack.

Instruction	Explanation
`cmp`	Pop two values off the stack. If they are equal, push "true"; otherwise, push "false."
`cmpl`	Compare less. Pop two values. If the second value is smaller than the first, push "true"; otherwise, push "false."
`cmple`	Compare less or equal. Pop two values. If the second value is smaller or equal the first, push "true"; otherwise, push "false."

Instruction	Explanation
`not`	Pop a value, then push its logical inverse.
`odd`	Pop a value; if it is an odd number, push "true"; otherwise, push "false."
`+`	Pop two values, then push their sum.
`uminus`	Unary minus. Pop a value. Then, push -a, where a is the value popped.
`-`	Pop two values, then push the result of subtracting the first value from the second.
`*`	Pop two values, then push their product.
`/`	Integer division. Pop two values, then push the second divided by the first.

Example

-- a := 0
push 1
push 0
:=

label again

-- Compare a to 10
rvalue 1
push 10
cmpl
gofalse done

-- a := a + 1
rvalue 1
push 1
+
push 1
swap
:=

-- print a
rvalue 1
write

goto again

label done
end

Running the interpreter

Data

On the csil machines, you can find a binary of the interpreter at ~cs162/inter/inter. (The same directory contains the source code, and you're free to grab it and compile it for your home machine, but it can be a little tricky.)

Suppose an inter program (such as the one in the example above) is in the file count.inter. You can then run the interpreter as follows:

csil:~$ ~cs162/inter/inter count.inter 
Using count.inter as input.
Inter stack machine interpreter
===============================

The machine has the following static limits:
Stack size 2048
Code size  4096
Data size  1024

Page length is set to 2000000000
The stack pointer starts at 1024
Parsing input...
Assembling input...
Executing...
1
2
3
4
5
6
7
8
9
10
csil:~$

The interpreter has a few debugging options; run it with the argument -h to see what these are.

An example with a function call

To better understand how to generate Inter code for an Epsilon program with function calls, we work out an example in full detail. There are many possible layouts for the activation records, but for this example, we assume the following layout:

Return value
Arguments
Return address
Old base pointer
Local variables

Note that the return address is pushed automatically by the call instruction, so the return value and arguments must be pushed by the caller. The old base pointer and the local variables must be pushed by the callee. The ret instruction expects the return address to be on top of the stack, so the callee must pop the local variables and old base pointer before it gets to the ret.

Here is an example Epsilon program:

function foo(a, b);
var c;
begin
  c := a + b;
  c := c + b;
  return c
end;

var k, l;
begin
  k := 1;
  read l;
  write foo(k, l);
end.

First, we look at pseudo code for the Inter code:

k := 2
read l
push return value
push k             -- copy in
push l		   -- copy in
call foo
l := argument 2    -- copy out
pop argument 2
k := argument 1    -- copy out
pop argument 1
-- the return value is not on the top of the stack
write              -- write and pop the return value
goto theend

label foo
push bp                     -- save old bp in the activation record
bp := sp - 2 - #params = sp - 4     -- set new bp
push c
-- the body of the function starts here
push a
push b
+
assign to c
push c
push b
+
assign to c
retval := c
pop c        -- pop the local variable
bp := old bp -- restore the bp
pop bp
ret

label theend
end

Note that the base pointer (which we will store in memory location 0) should point to the beginning of the activation record of the currently executing function. Before starting, the callee must save the old base pointer and set the new base pointer. The stack pointer points to the old base pointer, so the base pointer can be computed from the current stack pointer by subtracting the space taken by the return address, and parameters (in this case 4 words).

Here is the complete Inter code:

-- k := 2
push 1            -- 1 is the (absolute) address of k
push 2
:=
-- read l
push 2            -- 2 is the (absolute) address of l
read
:=
-- push return value
push 42      -- can push anything just to claim the space
-- push k and l
rvalue 1     -- 1 is the (absolute) address of k
rvalue 2     -- 2 is the (absolute) address of l
-- We can finally call the function.
call foo
-- Now copy out.
-- Copy top of stack to absolute address 2.
push 2            
swap
:=
-- Copy top of stack to absolute address 1.
push 1
swap
:=             
-- Pop the return value and write it.
write
goto theend

label foo
-- Save the current (soon to be old) base pointer.
rvalue 0
-- Set the base pointer.
pushsp
push 4
-
push 0       -- absolute address of base pointer
swap
:=
-- Push c.  (Anything, just to claim the space.)
push 23
-- The body of the function starts here.
-- Statement c := a + b starts here.
-- Push address of c (because c is used as an lvalue).
rvalue 0     -- Value of base pointer.
push 5       -- Relative address of c.
+            -- Compute absolute address of c.
-- Push value of a.
rvalue 0     -- Value of base pointer.
push 1       -- Relative address of a.
+            -- Compute absolute address of a.
rvaltop      -- Fetch the value of a.
-- Push value of b.
rvalue 0
push 2       -- Relative address of b.
+
rvaltop
-- Add them.
+
-- Assign to c.
:=
-- Statement c := c + b starts here.
-- Address of c.
rvalue 0
push 5
+
-- Value of c.
rvalue 0
push 5
+
rvaltop
-- Value of b.
rvalue 0
push 2
+
rvaltop
-- Add them.
+
-- Assign to c.
:=
-- Statement return c starts here.
-- Address of return value is just the base pointer.
rvalue 0
-- Value of c.
rvalue 0
push 5
+
rvaltop
-- Assign to the return value.
:=
-- Done with the function body.
-- Remove the local variable c from the stack.
pop
-- Restore the old base pointer.
push 0        -- Store it at address 0
swap
:=
ret

label theend
end