程序代写代做代考 computer architecture compiler scheme Compilers and computer architecture Code-generation (3): accumulator-machines

Compilers and computer architecture Code-generation (3): accumulator-machines
Martin Berger
November 2015

Recall the function of compilers

The accumulator machine

The accumulator machine
This machine has a stack, and just one register, the accumulator. The stack is used for intermediate values as in the stack machine, but arithmetic etc. instructions are always of the form:
Acc := Acc + Store[SP]
SP := SP+1
(Similar for other operations like *, – …)

Commands for accumulator machines

Commands for accumulator machines
As with the stack machine, we have PC, SP, IR. In addition we have the “accumulator” (accu).
Nop Pop
Push Load x
LoadImm n Store x
CompGreaterThan
Does nothing
removes the top of the stack and stores it
in the accumulator
Pushes the content of the accumulator on stack
Loads the content of memory location x into accumulator
Loads integer n into accumulator
Stores the content of accumulator in memory location x
Compares the accumulator with the top of the stack, stores 1 in accumulator if former
is bigger than latter otherwise stores 0, cleans up stack

Commands for accumulator machines
CompEq Jump l JumpTrue l …
Plus …
…
Jumps to l
Jumps to address/label l if accumulator is not 0
Adds the content of the accu with the top of stack storing result in accu, cleans up stack

Commands for accumulator machines
CompEq Jump l JumpTrue l …
Plus
…
Jumps to l
Jumps to address/label l if accumulator is not 0
Adds the content of the accu with the top of stack storing result in accu, cleans up stack
…
Code generator for statements is like that for the stack machine.

Semantics of accumulator machine (brief)

Semantics of accumulator machine (brief)
Add does
accu := accu + mem (SP); SP:=SP+1

Semantics of accumulator machine (brief)
Add does
accu := accu + mem (SP); SP:=SP+1
Push does
SP := SP-1; mem ( SP ) := accu

Semantics of accumulator machine (brief)
Add does
accu := accu + mem (SP); SP:=SP+1
Push does
SP := SP-1; mem ( SP ) := accu
Pop does
accu := mem ( SP ); SP := SP+1

Semantics of accumulator machine (brief)
Add does
accu := accu + mem (SP); SP:=SP+1
Push does
SP := SP-1; mem ( SP ) := accu
Pop does
accu := mem ( SP ); SP := SP+1
Load x does
accu := mem ( x )

Semantics of accumulator machine (brief)
Add does
accu := accu + mem (SP); SP:=SP+1
Push does
SP := SP-1; mem ( SP ) := accu
Pop does
accu := mem ( SP ); SP := SP+1
Load x does
accu := mem ( x )
Store x does
mem ( x ) := accu

Code generation for the accumulator machine (brief)

Code generation for the accumulator machine (brief)
Like for the stack machine, but values of expressions are left in the accumulator.
def codegenExpr ( exp : Expr ) =
if exp is of form
Binop ( lhs, op, rhs ) => {
codegenExpr ( rhs ) ++
List ( I_Push ) ++
codegenExpr ( lhs ) ++
codegenBinop ( op ) }
Ident ( x ) => List ( I_Load ( x ) )
Const ( n ) => List ( I_LoadImm ( n ) )
def codegenBinop ( op : Op ) =
if op is of form
Plus () => List ( I_Plus () )
…

Two-strategy translation
Now we do what we promised earlier.

Two-strategy translation
Now we do what we promised earlier.
􏹩 Whilefreeregistersremain,usetheregistermachine strategy for compilation.

Two-strategy translation
Now we do what we promised earlier.
􏹩 Whilefreeregistersremain,usetheregistermachine strategy for compilation.
􏹩 Whenthelimitisreached(ie.whenthereisoneregister left), revert to the accumulator strategy, using the last register as the accumulator.
For this to be workable, we need a register machine with one register that can act as the accumulator. On most modern CPUs, any of the general purpose registers (i.e. not SP, PC) can serve as accumulator.

Code generator with limited registers

Code generator with limited registers
def codegenExp( e : Expr, target : Register ) =
if e is of form
Ident( x ) => List ( I_Load ( target, x ) )
Const( n ) => List ( I_LoadImm ( target, n ) )
Binop( lhs, op, rhs ) =>
if ( target < maxRegs-1 ) // we have regs left codegenExp ( rhs, target ) ++ codegenExp ( lhs, target+1 ) ++ codegenBinop ( op, target, target+1 ) else // one registers left, use as accumulator codegenExp ( rhs, target ) ++ List ( I_Push ( target ) ) ++ codegenExp ( lhs, target ) ++ codegenBinopStack ( op, target ) ... Here maxRegs is the number of registers. Code generator with limited register Code generator with limited register def codegenBinop( op : Op, r1 : Register, r2 : Register if match is of form Plus () => List ( I_Plus ( r1, r2 ) )
Minus () => List ( I_Minus ( r1, r2 ) )
…
def codegenBinopStack( op : Op, r : Register ) =
if match is of form
Plus () => List ( I_PlusStack ( r ) )
Minus () => List ( I_MinusStack ( r ) )
…
Note that this ’merges’ the machine language of the register machine (e.g. I_Plus) with the language of the accumulator machine (e.g. I_PlusStack). In the tutorials, you will be asked to make this precise.

Semantics of the new commands (example)

Semantics of the new commands (example)
For example the new command
PlusStack r
simply does
r := r + mem ( SP );
SP := ( SP + 1 )
For simplicity we are ignoring under/overflowing the stack.

Summary

Summary
We saw a simple code generator for a simple language of statements and expressions, targeting a simple stack machine. This week we looked at ways of improving code for expressions. This involved register machines and accumulator machines, and other addressing modes.
Using just one register (accumulator) much reduces memory reference.
With a large number of registers, the situation gets even better.
If you run out out of registers, we can revert to the accumulator scheme.

The material in the textbooks

The material in the textbooks
Sorry, but the material I’ve presented is not discussed in the form I have used here in the textbooks. Of course all textbooks discuss code generation.

Related Posts