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

• by its address
• or by the identifier of a variable associated with this address. if any.

A stack

which is used to perform arithmetic operations.

The instruction are quite limited and fall into three classes:

• arithmetic operations
• stack manipulation
• control flow.

	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.

• The evaluation proceeds by processing the postfix representation from left to right.
• Each operand is pushed onto the stack as it is encountered.
• When a k-ary operator is reached,
  • its leftmost argument is k - 1 positions below the top of the stack and
  • its rightmost argument is at the top of the stack.
• The evaluation applies the operator to its k arguments, pop them and push the result onto the stack.

In our intermediate language,

• all values are integers
• 0 corresponds to false and
• all nonzero integers corresponds to true.

L-VALUES AND R-VALUES. In assignments like

x := a
x := x + 1

• the right side specifies an integer value,
• the left side specifies where the value should be stored

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 expr₁ then action₁ else action₂

looks like

code for expr₁

gofalse else

code for action₁

goto out

label else

code for action₂

label out

Example 4   A boolean disjonction

expr₁ or expr₂

can be viewed as an alternative:

if expr₁ then true else expr₂

Hence, the stack machine code for it looks like

code for expr₁

copy

gotrue out

pop

code for expr₂

label out

• Recall that gotrue and gofalse pop the value on top of the stack in order to simplify code generation for conditional and while statements.
• By copying the value of expr₁, we ensure that the value on top of the stack is true if the gotrue instruction leads to a jump.

A boolean conjonction

expr₁ and expr₂

would be treated similarly as the alternative:

if expr₁ then expr₂ else false