next up previous
Next: Three-Address Code Up: Compiler Theory: Intermediate Code Generation Previous: Intermediate Languages

Abstract Stack Machines

One popular form of intermediate representation is code for an abstract stack machine.


ABSTRACT STACK MACHINE. This machine has three memory zones.

The instruction memory
which holds the instruction of the program being executed.
The data memory
which store values. Each value can be accessed
A stack
which is used to perform arithmetic operations.
The instruction are quite limited and fall into three classes:

  Instruction     Stack Data value and address
1 push 5     16 0 1
2 rvalue 2   top $ \rightarrow$ 7 11 2
3 +       7 3
4 rvalue 3       ... 4
5 * $ \leftarrow$ pc        
6 ...          


ARITHMETIC OPERATIONS. The abstract stack machine code for an arithmetic expression E simulates the evaluation of a postfix representation of E using a stack.

In our intermediate language,


L-VALUES AND R-VALUES. In assignments like

x := a
x := x + 1
The terms L-values and R-values refer to values that are appropriate on the left and rigth sides of an assignment, respectively.



STACK MANIPULATION. We have the following instructions.

push v
which pushes v onto the stack.
rvalue $ \ell$
which pushes the content of data location $ \ell$.
lvalue $ \ell$
which pushes the address of data location $ \ell$.
pop
which throws away the value on top of the stack.
:=
which places the R-value on top in the L-value below it, and both are popped.
copy
which pushes a copy of the top value on the stack.


Example 2   The translation of the PASCAL-like statement
x := (a + b) * (c mod 5)
in our abstract stack machine is
lvalue x
rvalue a 
rvalue b
+ 
rvalue c
push 5
mod
*
:=


CONTROL FLOW. The stack machine executes instructions in numerical order unless told to do otherwise by a conditional or unconditional jump statement. We assume that our machine supports symolic labels, that is we can decorate any instruction with a name, its label. Then the control-flow instructions for our abstract stack machine are

label $ \ell$
the current statement receives the label $ \ell$,
goto $ \ell$
the next instruction is taken from statement with label $ \ell$,
gofalse $ \ell$
pop the top value, say v, and jump to label $ \ell$ if v = 0,
gotrue $ \ell$
pop the top value, say v, and jump to label $ \ell$ if v $ \neq$ 0.
label
stop the execution.

Example 3   The stack machine code for an alternative
if expr1 then action1 else action2
looks like
code for expr1
gofalse else
code for action1
goto out
label else
code for action2
label out

Example 4   A boolean disjonction
expr1 or expr2
can be viewed as an alternative:
if expr1 then true else expr2
Hence, the stack machine code for it looks like
code for expr1
copy
gotrue out
pop
code for expr2
label out
A boolean conjonction
expr1 and expr2
would be treated similarly as the alternative:
if expr1 then expr2 else false


next up previous
Next: Three-Address Code Up: Compiler Theory: Intermediate Code Generation Previous: Intermediate Languages
Marc Moreno Maza
2004-12-02