Tutorial Week 8 (Solutions)
Task 1. You were asked to translate the following programs into stack machine assembler.
1. a := a + b + c
2. x := (a – b) – c
3. x := a – (b – c)
4. x := a*b + c
5. c := c + a*b
6. x := (a + b)/(c – d)
7. x := a*a / b*b
8. x := a*a – a*a
9. x := maximum ( b, c )
10. x := minimum ( b, c )
11. x := x + 1; y := y – x
12. x := 100; for i = 1 to 50 { x := x-i }
Here are some example solutions. Other answers are possible.
Exercise 1:
PushAbs(c)
PushAbs(b)
Plus()
PushAbs(a)
Plus()
Pop(a)
Exercise 2:
PushAbs(c)
PushAbs(b)
PushAbs(a)
Minus()
Minus()
Pop(x)
Exercise 3:
PushAbs(c)
PushAbs(b)
Minus()
PushAbs(a)
Minus()
Pop(x)
Exercise 4:
PushAbs(c)
PushAbs(b)
PushAbs(a)
Times()
Plus()
Pop(x)
Exercise 5:
PushAbs(b)
PushAbs(a)
Times()
PushAbs(c)
Plus()
Pop(x)
Exercise 6:
PushAbs(d)
PushAbs(c)
Minus()
PushAbs(b)
PushAbs(a)
Plus()
Divide()
Pop(x)
Exercise 7:
PushAbs(b)
PushAbs(b)
Times()
PushAbs(a)
PushAbs(a)
Times()
Divide()
Pop(x)
Exercise 9:
PushAbs b
PushAbs c
CompGreaterThan
JumpTrue greater
PushAbs b
Jump just_pop
greater:
Push c
just_pop:
Pop x
Exercise 11:
PushImm(1)
PushAbs(x)
Plus()
Pop(x)
PushAbs(x)
PushAbs(y)
Minus()
Pop(y)
Exercise 12:
PushImm(100)
Pop(x)
PushImm(1)
Pop(i)
begin_loop:
PushImm(50)
PushAbs(i)
CompGreaterThan()
JumpTrue(end_loop)
PushAbs(i)
PushAbs(x)
Minus()
Pop(x)
PushAbs(i)
PushImm(1)
Plus()
Pop(i)
Jump(begin_loop)
end_loop:
Task 2. Very similar to stack machines and omitted.
Task 3. Very similar to stack machines and omitted.
Task 4. Here is the machine language required in Task 4.
abstract class Instruction
case class I_Nop () extends Instruction
case class I_Pop ( r : Register ) extends Instruction
case class I_Push ( r : Register ) extends Instruction
case class I_Load ( r : Register, x : Variable ) extends Instruction
case class I_LoadImm ( r : Register, n : Int ) extends Instruction
case class I_Store ( r : Register, x : Variable ) extends Instruction
case class I_CompGreaterThan ( r1 : Register, r2 : Register ) extends Instruction
case class I_CompEq ( r1 : Register, r2 : Register ) extends Instruction
case class I_Jump ( l : MemoryLoc ) extends Instruction
case class I_JumpTrue ( r : Register, l : MemoryLoc ) extends Instruction
case class I_JumpFalse ( r : Register, l : MemoryLoc ) extends Instruction
case class I_Plus ( r1 : Register, r2 : Register ) extends Instruction
case class I_Minus ( r1 : Register, r2 : Register ) extends Instruction
case class I_Times ( r1 : Register, r2 : Register ) extends Instruction
case class I_Divide ( r1 : Register, r2 : Register ) extends Instruction
case class I_PlusStack ( r : Register ) extends Instruction
case class I_MinusStack ( r : Register ) extends Instruction
case class I_TimesStack ( r : Register ) extends Instruction
case class I_DivideStack ( r : Register ) extends Instruction
case class I_Negate ( r : Register ) extends Instruction
case class I_DefineLabel ( l : MemoryLoc ) extends Instruction
The meaning of these instructions can be given by way of an interpreter, reproduced below. However, it’s not necessary to be this formal. A hand-written explanation is fine too.
class RegisterMachine ( maxMem : Int, maxRegs : Int ) {
assert ( maxMem > 0 && maxRegs > 0 )
private val mem = Array.fill ( maxMem ) ( 0 )
private val reg = Array.fill ( maxRegs ) ( 0 )
private var pc = 0
private var ir = 0
private var sp = 0
private def incSP () = { sp = ( sp + 1 ) % maxMem }
private def decSP () = { sp = ( sp – 1 ) % maxMem }
private def incPC () = { pc = ( pc + 1 ) % maxMem }
def load ( code : Array [ Int ], startAddress : Int ) : Unit = {
throw new Exception ( “[RegisterMachine::load] not implemented yet” ) }
def run () : Unit = {
while ( true ) {
ir = mem ( pc )
incPC ()
ir match {
case 0 => {} // I_Nop
case 1 => { // I_Pop
val i = mem ( pc )
incPC ()
reg ( i ) = mem ( sp )
decSP () }
case 2 => { // I_Push
val i = mem ( pc )
incPC ()
incSP ()
mem ( sp ) = reg ( i ) }
case 3 => { // I_Load
val i = mem ( pc )
incPC ()
val x = mem ( pc )
incPC ()
reg ( i ) = mem ( x ) }
case 4 => { // I_LoadImm
val i = mem ( pc )
incPC ()
val n = mem ( pc )
incPC ()
reg ( i ) = n }
case 5 => { // I_Store
val i = mem ( pc )
incPC ()
val x = mem ( pc )
incPC ()
mem ( i ) = reg ( x ) }
case 6 => { // I_CompGreaterThan
val i = mem ( pc )
incPC ()
val j = mem ( pc )
incPC ()
if ( reg ( i ) > reg ( j ) ) reg ( i ) = 1 else reg ( i ) = 0 }
case 7 => { // I_CompEq
val i = mem ( pc )
incPC ()
val j = mem ( pc )
incPC ()
if ( reg ( i ) == reg ( j ) ) reg ( i ) = 1 else reg ( i ) = 0 }
case 8 => { // I_Jump
pc = mem ( pc ) }
case 9 => { // I_JumpTrue
val i = mem ( pc )
incPC ()
val adr = mem ( pc )
incPC ()
if ( reg ( i ) != 0 ) pc = adr }
case 10 => { // I_JumpFalse
val i = mem ( pc )
incPC ()
val adr = mem ( pc )
incPC ()
if ( reg ( i ) == 0 ) pc = adr }
case 11 => { // I_Plus
val i = mem ( pc )
incPC ()
val j = mem ( pc )
incPC ()
reg ( i ) = reg ( i ) + reg ( j ) }
case 12 => { // I_Minus
val i = mem ( pc )
incPC ()
val j = mem ( pc )
incPC ()
reg ( i ) = reg ( i ) – reg ( j ) }
case 13 => { // I_Times
val i = mem ( pc )
incPC ()
val j = mem ( pc )
incPC ()
reg ( i ) = reg ( i ) * reg ( j ) }
case 14 => { // I_Divide
val i = mem ( pc )
incPC ()
val j = mem ( pc )
incPC ()
reg ( i ) = reg ( i ) / reg ( j ) }
case 15 => { // I_Negate
val i = mem ( pc )
incPC ()
reg ( i ) = reg ( i ) * ( -1 ) }
case 16 => { // I_PlusStack
val i = mem ( pc )
incPC ()
val arg = mem ( sp )
decSP ()
reg ( i ) = reg ( i ) + arg }
case 17 => { // I_MinusStack
val i = mem ( pc )
incPC ()
val arg = mem ( sp )
decSP ()
reg ( i ) = reg ( i ) – arg }
case 18 => { // I_TimesStack
val i = mem ( pc )
incPC ()
val arg = mem ( sp )
decSP ()
reg ( i ) = reg ( i ) * arg }
case 19 => { // I_DivideStack
val i = mem ( pc )
incPC ()
val arg = mem ( sp )
decSP ()
reg ( i ) = reg ( i ) / arg }
case _ => throw new Exception ( “[RegisterMachine:run] illegal opcode” ) } } } }
The full code generator is given next.
class CodeGen ( maxRegs : Int ) {
def codegenBinop ( op : Op, r1 : Register, r2 : Register ) : List [ Instruction ] = {
op match {
case Plus () => List ( I_Plus ( r1, r2 ) )
case Minus () => List ( I_Minus ( r1, r2 ) )
case Times () => List ( I_Times ( r1, r2 ) )
case Divide () => List ( I_Divide ( r1, r2 ) ) } }
def codegenBinopStack ( op : Op, r : Register ) : List [ Instruction ] = {
op match {
case Plus () => List ( I_PlusStack ( r ) )
case Minus () => List ( I_MinusStack ( r ) )
case Times () => List ( I_TimesStack ( r ) )
case Divide () => List ( I_DivideStack ( r ) ) } }
def codegenUnop ( op : Op, r : Register ) : List [ Instruction ] = {
op match {
case Minus () => List ( I_Negate ( r ) )
case _ => throw new Exception ( “[codegenUnop] Invalide unary command!” ) } }
def codegenExpr ( exp : Expr, target : Register ) : List [ Instruction ] = {
exp match {
case Binop ( lhs, op, rhs ) => {
if ( target < maxRegs-1 ) {
codegenExpr ( rhs, target ) ++
codegenExpr ( lhs, target+1 ) ++
codegenBinop ( op, target, target+1 ) } // arguments from registers
else { // now target == maxRegs-1
codegenExpr ( rhs, target ) ++
List ( I_Push ( target ) ) ++
codegenExpr ( lhs, target ) ++
codegenBinopStack ( op, target ) } } // gets one argument from stack
case Unop ( op, e ) => codegenExpr ( e, target ) ++ codegenUnop ( op, target )
case Ident ( x ) => List ( I_Load ( target, x ) )
case Const ( n ) => List ( I_LoadImm ( target, n ) ) } }
def codegenStatement ( s : Statement, firstFree : Register ) : List [ Instruction ] = {
val r = firstFree
var n = -1
def newLabel () : String = { n += 1; “l_” + n.toString }
s match {
case Assign ( x, e ) => codegenExpr ( e, r ) ++ List ( I_Store ( r, x ) )
case Sequence ( lhs, rhs ) => codegenStatement ( lhs, r ) ++
codegenStatement ( rhs, r )
case For ( loopVar, from, to, body ) => {
val label1 = newLabel ()
val label2 = newLabel ()
codegenExpr ( from, r ) ++
List ( I_Store ( r, loopVar ), I_DefineLabel ( label1 ) ) ++
codegenExpr ( to, r ) ++
List ( I_Load ( r+1, loopVar ),
I_CompGreaterThan ( r, r+1 ),
I_JumpTrue ( r, label2 ) ) ++
codegenStatement ( body, r ) ++
List ( I_Load ( r, loopVar ),
I_LoadImm ( r+1, 1 ),
I_Plus ( r, r+1 ),
I_Store ( r, loopVar ),
I_Jump ( label1 ),
I_DefineLabel ( label2 ) ) }
def codegenProgram ( s : Statement ) : List [ Instruction ] = codegenStatement ( s, 0 )
}