程序代写代做代考 assembler computer architecture compiler Java mips Compilers and computer architecture: A realistic compiler to MIPS

Compilers and computer architecture: A realistic compiler to MIPS
Martin Berger
November 2015

Recall the function of compilers

Recall the structure of compilers
Source program
Lexical analysis
Intermediate code generation
Optimisation
Syntax analysis
Semantic analysis, e.g. type checking
Code generation
Translated program

Introduction
Now we look at more realistic code generation. In the previous two lectures we investigated key issues in compilation for more realistic source and target languages, such as procedures and memory alignment. We also introduced the MIPS architecture, which has an especially clean instruction set architecture, is widely used (embedded systems, PS2, PSP), and has deeply influenced other CPU architectures (e.g. ARM).

Source language
The language we translate to MIPS is a simple imperative language with integers as sole data type and recursive procedures with arguments. Here’s it’s grammar.
P →D;P|D
D → defID(A)=E
A →Ane|ε
Ane → ID,Ane|ID
E → INT|ID|ifE=EthenEelseE
| E+E|E−E|ID(EA) EA → ε|EAne
EAne → E|E,EAne
Here ID ranges over identifiers, and INT over integers. The first declared procedure is the entry point (i.e. will be executed when the program is run) and must take 0 arguments. Procedure names must be distinct.

Source language as AST data type in pseudo code
class Program ( decls : List [ Declaration ] ) {

Source language as AST data type in pseudo code
class Program ( decls : List [ Declaration ] ) {
class Declaration ( id : String,
args : List [ String ],
body : Exp )

Source language as AST data type in pseudo code
abstract class Exp
class IntLiteral ( n : Int ) extends Exp
class Variable ( x : String ) extends Exp
class If ( l : Exp,
r : Exp,
thenBody : Exp,
elseBody : Exp ) extends Exp
class Add ( l : Exp, r : Exp ) extends Exp
class Sub ( l : Exp, r : Exp ) extends Exp
class Call ( f : String,
args : List [ Exp ] ) extends Exp

Example program
def myFirstProg () = fib ( 3 );
def fib ( n ) =
if n = 0 then
0
else if n = 1 then
1 else
fib ( n-1 ) + fib ( n-2 )

Generating code for the language
We use MIPS as an accumulator machine. So we are using only a tiny fraction of MIPS’s power. This is to keep the compiler easy.

Generating code for the language
We use MIPS as an accumulator machine. So we are using only a tiny fraction of MIPS’s power. This is to keep the compiler easy.
Recall that in an accumulator machine all operations:
􏹩 thefirstargumentisassumedtobeintheaccumulator;
􏹩 allremainingargumentssitonthe(topofthe)stack;
􏹩 theresultoftheoperationisstoredintheaccumulator;
􏹩 afterfinishingtheoperation,allargumentsareremoved from the stack.
The code generator we will be presenting guarantees that all these assumptions always hold.

Generating code for the language
To use MIPS as an accumulator machine we need to decide what registers to use as stack pointer and accumulator.
We make the following assumptions (which are in line with the assumptions the MIPS community makes, see previous lecture slides).
􏹩 Weusethegeneralpurposeregister$a0asaccumulator. 􏹩 Weusethegeneralpurposeregister$spasstackpointer.

Generating code for the language
To use MIPS as an accumulator machine we need to decide what registers to use as stack pointer and accumulator.
We make the following assumptions (which are in line with the assumptions the MIPS community makes, see previous lecture slides).
􏹩 Weusethegeneralpurposeregister$a0asaccumulator.
􏹩 Weusethegeneralpurposeregister$spasstackpointer.
􏹩 Thestackpointeralwayspointstothefirstfreebyteabove the stack.

Generating code for the language
To use MIPS as an accumulator machine we need to decide what registers to use as stack pointer and accumulator.
We make the following assumptions (which are in line with the assumptions the MIPS community makes, see previous lecture slides).
􏹩 Weusethegeneralpurposeregister$a0asaccumulator.
􏹩 Weusethegeneralpurposeregister$spasstackpointer.
􏹩 Thestackpointeralwayspointstothefirstfreebyteabove the stack.
􏹩 Thestackgrowsdownwards.

Generating code for the language
To use MIPS as an accumulator machine we need to decide what registers to use as stack pointer and accumulator.
We make the following assumptions (which are in line with the assumptions the MIPS community makes, see previous lecture slides).
􏹩 Weusethegeneralpurposeregister$a0asaccumulator.
􏹩 Weusethegeneralpurposeregister$spasstackpointer.
􏹩 Thestackpointeralwayspointstothefirstfreebyteabove the stack.
􏹩 Thestackgrowsdownwards. We could have made other choices.

Assumption about data types
Our source language has integers.

Assumption about data types
Our source language has integers.
We will translate them to the built-in 32 bit MIPS data-type.

Assumption about data types
Our source language has integers.
We will translate them to the built-in 32 bit MIPS data-type.
Other choices are possible (e.g. 64 bits, infinite precision, 16 bit etc). This one is by far the simplest.

Code generation
Let’s start easy and generate code expressions.

Code generation
Let’s start easy and generate code expressions.
For simplicity we’ll ignore some issues like placing alignment commands.

Code generation
Let’s start easy and generate code expressions.
For simplicity we’ll ignore some issues like placing alignment commands.
As with the translation to an idealised accumulator machine a few weeks ago, we compile expressions by recursively walking the AST. We want to write the following:
def genExp ( e : Exp ) =
if e is of form
IntLiteral ( n ) then …
Variable ( x ) then …
If ( cond , thenBody, elseBody ) then …
Add ( l, r ) then …
Sub ( l, r ) then …
Call ( f, args ) then … } }

Code generation: integer literals
Let’s start with the simplest case.
def genExp ( e : Exp ) =
if e is of form
IntLiteral ( n ) then
li $a0 n

Code generation: integer literals
Let’s start with the simplest case.
def genExp ( e : Exp ) =
if e is of form
IntLiteral ( n ) then
li $a0 n
Convention: code in red is MIPS code to be executed at run-time. Code in black is executed at compile-time. We are also going to be a bit sloppy about the datatype MIPS_I of MIPS instructions.
This preserves all invariants to do with the stack and the accumulator as required. Recall that li is a pseudo instruction and will be expanded by the assembler into several real MIPS instructions.

Code generation: addition
def genExp ( e : Exp ) =
if e is of form
Add ( l, r ) then
genExp ( l )
sw $a0 0($sp)
addiu $sp $sp -4
genExp ( r )
lw $t1 4($sp)
add $a0 $t1 $a0
addiu $sp $sp 4
Note that this evaluates from left to right! Recall also that the stack grows downwards and that the stack pointer points to the first free memory cell above the stack.

Code generation: minus
We want to translate e − e′. We need new MIPS command: sub reg1 reg2 reg3
It subtracts the content of reg3 from the content of reg2 and stores the result in reg1. I.e. reg1 := reg2 – reg3.

Code generation: minus
def genExp ( e : Exp ) =
if e is of form
Minus ( l, r ) then
genExp ( l )
sw $a0 0 $sp
addiu $sp $sp -4
genExp ( r )
lw $t1 4($sp)
sub $a0 $t1 $a0
addiu $sp $sp 4
Note that sub $a0 $t1 $a0 deducts $a0 from $t1.

Code generation: conditional
We want to translate if e1 = e2 then e else e′. We need two new MIPS commands:
beq reg1 reg2 label
b label
beq branches to label if the content of reg1 is identical to the content of reg2. Otherwise it does nothing and moves on to the next command.

Code generation: conditional
def genExp ( e : Exp ) =
if e is of form
If ( l, r, thenBody, elseBody ) then
val elseBranch = newLabel () // not needed
val thenBranch = newLabel ()
val exitLabel = newLabel ()
genExp ( l )
sw $a0 0($sp)
addiu $sp $sp -4
genExp ( r )
lw $t1 4($sp)
addiu $sp $sp 4
beq $a0 $t1 thenBranch
elseBranch + “:”
genExp ( elseBody )
b exitLabel
thenBranch + “:”
genExp ( thenBody )
exitLabel + “:” }

Code generation: procedure calls/declarations
The code a compiler emits for procedure calls and declarations depends on the layout of the activation record (AR).

Code generation: procedure calls/declarations
The code a compiler emits for procedure calls and declarations depends on the layout of the activation record (AR).
The AR stores all the data that’s needed to execute an invocation of a procedure.

Code generation: procedure calls/declarations
main
Main’s AR
f( 3 )
Result Argument: 3 Return address
Result Argument: 2 Return address
f( 2 )
The code a compiler emits for procedure calls and declarations depends on the layout of the activation record (AR).
The AR stores all the data that’s needed to execute an invocation of a procedure.
ARs are held on the stack, because procedure entries and exits are adhere to a bracketing discipline.
Note that invocation result and (some) procedure arguments are often passed in register not in AR (for efficiency)

Code generation: procedure calls/declarations
For our simple language, we can make do with a simple AR layout:

Code generation: procedure calls/declarations
For our simple language, we can make do with a simple AR layout:
The result is always in the accumulator, so no need for to store the result in the AR.

Code generation: procedure calls/declarations
For our simple language, we can make do with a simple AR layout:
The result is always in the accumulator, so no need for to store the result in the AR.
The only variables in the language are procedure parameters. We hold them in AR: for the procedure call f(e1 , …, en ) just push the result of evaluating e1, …, en onto the stack.
The AR needs to store the return address.
The stack calling discipline ensures that on procedure exit $sp is the same as on procedure entry.
Also: no registers need to be preserved in accumulator machines. Why?

Code generation: procedure calls/declarations
So ARs for a procedure with n arguments look like this:
caller’s FP
argument n
…
argument 1
return address
A pointer to the top of current AR (i.e. where the return address sits) is useful (though not necessary) see later. This pointer is called frame pointer and lives in register $fp. We need to restore the caller’s FP on procedure exit, so we store it in the AR upon procedure entry. The FP makes accessing variables easier (see later).

Code generation: procedure calls/declarations
Let’s look at an example: assume we call f (7, 100, 33)
FP
Caller’s AR
Caller’s AR
Caller’s FP
Third argument: 33 Second argument: 100 First argument: 7
Caller’s FP
Third argument: 33 Second argument: 100 First argument: 7
FP Return address SP
Caller’s responsibility
Callee’s responsibility
SP
Jump

Code generation: procedure calls/declarations
To be able to get the return addess for a procedure call easily, we need a new MIPS instruction:
jal label
Note that jal stands for jump and link. This instruction does
the following:
Jumps unconditionally to label, stores the address of next
instruction (syntactically following jal label) in register $ra.
On many other architectures, the return address is automatically placed on the stack by a call instruction.

Code generation: procedure calls/declarations
To be able to get the return addess for a procedure call easily, we need a new MIPS instruction:
jal label
Note that jal stands for jump and link. This instruction does
the following:
Jumps unconditionally to label, stores the address of next
instruction (syntactically following jal label) in register $ra. On many other architectures, the return address is
automatically placed on the stack by a call instruction.
On MIPS we must push the return address on stack explicitly. This can only be done by callee, because address is available only after jal has executed.

Code generation: procedure calls
Example of procedure call with 3 arguments. General case is similar.

Code generation: procedure calls
Example of procedure call with 3 arguments. General case is similar.
case Call ( f, List ( e1, e2, e3 ) ) then
sw $fp 0($sp) // save FP on stack
addiu $sp $sp -4
genExp ( e3 ) // we choose right-to-left ev. order
sw $a0 0($sp) // save 3rd argument on stack
addiu $sp $sp -4
genExp ( e2 )
sw $a0 0($sp) // save 2nd argument on stack
addiu $sp $sp -4
genExp ( e1 )
sw $a0 0($sp) // save 1st argument on stack
addiu $sp $sp -4
jal ( f + “_entry” ) // jump to f, save return
// addr in $ra

Code generation: procedure calls
Several things are worth noting.

Code generation: procedure calls
Several things are worth noting. 􏹩 ThecallerfirstsavestheFP.

Code generation: procedure calls
Several things are worth noting.
􏹩 ThecallerfirstsavestheFP.
􏹩 Thenthecallersavesprocedureparametersinreverse order (right-to-left).

Code generation: procedure calls
Several things are worth noting.
􏹩 ThecallerfirstsavestheFP.
􏹩 Thenthecallersavesprocedureparametersinreverse order (right-to-left).
􏹩 Implicitlythecallersavesthereturnaddressin$raby executing jal. The return address is still not on the stack. That’s the callee’s responsibility.
􏹩 ForaprocedurewithnargumentstheAR(withoutreturn address) is 4 + 4 ∗ n = 4(n + 1) bytes long. This is know at compile time and is important for the compilation of procedure bodies.

Code generation: procedure calls
So far we perfectly adhere to the lhs of this picture (except 33, 100, 7).
FP
Caller’s AR
Caller’s AR
Caller’s FP
Third argument: 33 Second argument: 100 First argument: 7
Caller’s FP
Third argument: 33 Second argument: 100 First argument: 7
FP Return address SP
Caller’s responsibility
Callee’s responsibility
SP
Jump

Code generation: procedure calls, callee’s side
We use a procedure for compiling declarations like so:
def genDecl ( d : Declaration ) = …

Code generation: procedure calls, callee’s side

Code generation: procedure calls, callee’s side
We need two new MIPS instructions:
jr reg
move reg reg’

Code generation: procedure calls, callee’s side
We need two new MIPS instructions:
jr reg
move reg reg’
The former (jr reg) jumps to the address stored in register reg.

Code generation: procedure calls, callee’s side
We need two new MIPS instructions:
jr reg
move reg reg’
The former (jr reg) jumps to the address stored in register reg.
The latter (move reg reg’) moves the content of register reg’ into the register reg.

Code generation: procedure calls, callee’s side
def genDecl ( d : Declaration ) =
val sizeAR = ( 2 + d.args.size ) * 4
// each procedure argument takes 4 bytes,
// in addition the AR stores the return
// address and old FP
d.id + “_entry:” // label to jump to
move $fp $sp // FP points to (future) top of AR
sw $ra 0($sp) // put return address on stack
addiu $sp $sp -4 // now AR is fully created
genExp ( d.body )
lw $ra 4($sp) // load return address into $ra
// could also use $fp
addiu $sp $sp sizeAR // pop AR off stack in one go
lw $fp 0($sp) // restore old FP
jr $ra // hand back control to caller

Code generation: procedure calls, callee’s side
Before call On entry On exit
Caller’s AR Caller’s AR Caller’s AR FPFP FP
After call
Caller’s AR
SP
Caller’s FP
Third argument: 33 Second argument: 100 First argument: 7
Caller’s FP SP Third argument: 33
Second argument: 100
First argument: 7
FP Return address SP
SP

Code generation: frame pointer
Variables are just the procedure parameters in this language.

Code generation: frame pointer
Variables are just the procedure parameters in this language.
They are all on the stack in the AR, pushed by the caller. How do we access them? The obvious solution (use the SP with appropriate offset) does not work (at least not easily).
Problem: The stack grows and shrinks when intermediate results are computed (in the accumulator machine approach), so the variables are not on a fixed offset from $sp. For example in
def f ( x, y, z ) = x + ( ( x * z ) + ( y – y ) )

Code generation: variable use
Assume we compile the variable x which is the i-th (starting to count from 1) formal parameter of the ambient procedure declaration.
case Variable ( x ) then
val offset = 4*i
lw $a0 offset($fp)
Putting the arguments in reverse order on the stack makes the offseting calculation val offset = 4*i a tiny bit easier.
Key insight: access at fixed offset relative to a dynamically changing pointer. Offset and pointer location are known at compile time.
This idea is pervasive in compilation.

Code generation: variable use
Caller’s AR
Caller’s FP
Third argument: 33 Second argument: 100 First argument: 7 Return address
FP
In the declaration def f (x, y, z) = …, we have:
􏹩 x isataddress$fp + 4 􏹩 y isataddress$fp + 8 􏹩 z isataddress$fp + 12
Note that this work because indexing begins at 1 in this case, and arguments are pushed on stack from right to left.

Translation of variable assignment
Given that we know now that reading a variable is translated as
case Variable ( x ) then
val offset = 4*i
lw $a0 offset($fp)
How would you translate an assignment
x := e
Assume that the variable x is the i-th (starting to count from 1) formal parameter of the ambient procedure declaration.

Code generation: summary remarks
The code of variable access, procedure calls and declarations depends totally on the layout of the AR, so the AR must be designed together with the code generator, and all parts of the code generator must agree on AR conventions. It’s just as important to be clear about the nature of the stack (grows upwards or downwards), frame pointer etc.
Access at fixed offset relative to dynamically changing pointer. Offset and pointer location are known at compile time.
Code and layout also depends on CPU.
Code generation happens by recursive AST walk. Industrial strength compilers are more complicated:

Code generation: summary remarks
The code of variable access, procedure calls and declarations depends totally on the layout of the AR, so the AR must be designed together with the code generator, and all parts of the code generator must agree on AR conventions. It’s just as important to be clear about the nature of the stack (grows upwards or downwards), frame pointer etc.
Access at fixed offset relative to dynamically changing pointer. Offset and pointer location are known at compile time.
Code and layout also depends on CPU.
Code generation happens by recursive AST walk.
Industrial strength compilers are more complicated:
􏹩 Trytokeepvaluesinregisters,especiallythecurrentstack frame. E.g. compilers for MIPS usually pass first four procedure arguments in registers $a0 – $a3.

Code generation: summary remarks
The code of variable access, procedure calls and declarations depends totally on the layout of the AR, so the AR must be designed together with the code generator, and all parts of the code generator must agree on AR conventions. It’s just as important to be clear about the nature of the stack (grows upwards or downwards), frame pointer etc.
Access at fixed offset relative to dynamically changing pointer. Offset and pointer location are known at compile time.
Code and layout also depends on CPU.
Code generation happens by recursive AST walk.
Industrial strength compilers are more complicated:
􏹩 Trytokeepvaluesinregisters,especiallythecurrentstack frame. E.g. compilers for MIPS usually pass first four procedure arguments in registers $a0 – $a3.
􏹩 Intermediatevalues,localvariablesareheldinregisters, not on the stack.

Non-integer procedure arguments
What we have not covered is procedures taking non integer arguments.

Non-integer procedure arguments
What we have not covered is procedures taking non integer arguments.
This is easy: the only difference from a code generation perspective between integer types and other types as procedure arguments is the size of the data. But that size is known at compile-time (at least for languages that are statically typed). For example the type double is often 64 bits. So we reserve 8 bytes for arguments of that type in the procedure’s AR layout. We may have to use two calls to lw and sw to load and store such arguments, but otherwise code generation is unchanged.

Non-integer procedure arguments
Consider a procedure with the following signature:
int f ( int x,
double y,
int z ) = { … }
(Not valid in our mini-language). Assuming that double is stored as 64 bits, then the AR would look like on the right.
How does the code generator know what size the variables have?
1632 Caller’s FP 1636 int x
1640
Double y 1644
1648 int z
1652
return address

Non-integer procedure arguments
Consider a procedure with the following signature:
int f ( int x,
double y,
int z ) = { … }
(Not valid in our mini-language). Assuming that double is stored as 64 bits, then the AR would look like on the right.
How does the code generator know what size the variables have?
Using the information stored in the symbol table, which was created by the type checker and passed to the code-generator.
1632 Caller’s FP 1636 int x
1640
Double y 1644
1648 int z
1652
return address

Non-integer procedure arguments
Due to the simplistic accumulator machine approach, cannot do the same with the return value, e.g.
double f ( int x, double y, int z ) = …

Non-integer procedure arguments
Due to the simplistic accumulator machine approach, cannot do the same with the return value, e.g.
double f ( int x, double y, int z ) = …
This is because the accumulator holds the return value of procedure calls, and the accumulator is fixed at 32 bits.
In this case we’d have to move to an approach that holds the return value also in the AR (either for all arguments, or only for arguments that don’t fit in a register – we know at compile time which is which).

Example def sumto(n) = if n=0 then 0 else n+sumto(n-1)
sumto_entry:
move $fp $sp
sw $ra 0($sp)
addiu $sp $sp
lw $a0 4($fp)
sw $a0 0($sp)
addiu $sp $sp
li $a0 0
-4
-4
addiu $sp $sp -4
li $a0 1
lw $t1 4($sp)
sub $a0 $t1 $a0
addiu $sp $sp 4
sw $a0 0($sp)
addiu $sp $sp -4
jal sumto_entry
lw $t1 4($sp)
add $a0 $t1 $a0
addiu $sp $sp 4
b exit2
then1:
li $a0 0
exit2:
lw $ra 4($sp)
addiu $sp $sp 12
lw $fp 0($sp)
jr $ra
lw $t1 4($sp)
addiu $sp $sp
beq $a0 $t1 then1
else0:
lw $a0 4($fp)
sw $a0 0($sp)
addiu $sp $sp
sw $fp 0($sp)
addiu $sp $sp
lw $a0 4($fp)
sw $a0 0($sp)
-4 -4
4

Interesting observations
Several points are worth thinking about.

Interesting observations
Several points are worth thinking about.
Stack allocated memory is much faster than heap allocation, because (1) acquiring stack memory is just a constant-time push operation, and (2) the whole AR can be ’deleted’ (= popped off the stack) in a single, constant-time operation. We will soon learn about heap-allocation (section on garbage-collection), which is much more expensive. This is why low-level language (C, C++, Rust) don’t have garbage collection (by default).

Another interesting observation: inefficiency of the
translation
As already pointed out at the beginning of this course, stack- and accumulator machines are inefficient.

Another interesting observation: inefficiency of the
translation
As already pointed out at the beginning of this course, stack- and accumulator machines are inefficient. Consider this from the previous slide (compilation of parts of n = 0 in sumto):
lw $a0 4($fp)
sw $a0 0($sp)
addiu $sp $sp -4
li $a0 0
lw $t1 4($sp)
// first we load n into the
// accumulator from the stack
// then we push n back onto
// the stack
// now we load n back from
// the stack into a temporary

Compiling whole programs
So far we have only compiled expressions and single declarations, but a program is a sequence of declarations, and it is called from, and returns to the OS. To compile a whole program we do the following:
􏹩 Generatecodeforeachdeclaration.
􏹩 EmitcodeenablingtheOStocallthefirstprocedure(like Java’s main – other languages might have different conventions) ’to get the ball rolling’. This essentially involves
1. Creating (the caller’s side of) an activation record.
2. Jump-and-link’ing to the first procedure.
3. Code that hands back control gracefully to the OS after
program termination. Termination means doing a return to the place after (2). This part is highly OS specific.

Compiling whole programs
Say we had a program declaring 4 procedures f1, f2, f3, and f4 in this order. Then a fully formed compiler would typically generate code as follows.
preamble:
…// e.g. alignment commands if needed
entry_point: // this is where the OS jumps to
// at startup
… // create AR for initial call to f1
jal f1_entry // jump to f1
… // cleanup, hand back control to OS
f1_entry:
… // f1 body code
f2_entry:
… // f2 body code
f3_entry:
… // f3 body code
f4_entry:
… // f4 body code

Related Posts