Code Generation

CS143
Lecture 12

Instructor: Fredrik Kjolstad

Slide design by Prof. Alex Aiken, with modifications
1
Lecture Outline

• Topic 1: Basic Code Generation

– The MIPS assembly language
– A simple source language
– Stack-machine implementation of the simple language

• Topic 2: Code Generation for Objects

2
From Stack Machines to MIPS

• The compiler generates code for a stack machine

with accumulator

• We want to run the resulting code on the MIPS

processor (or simulator)

• We simulate stack machine instructions using

MIPS instructions and registers

3
Simulating a Stack Machine…

• The accumulator is kept in MIPS register $a0

• The stack is kept in memory

– The stack grows towards lower addresses
– Standard convention on the MIPS architecture

• The address of the next location on the stack is

kept in MIPS register $sp
– The top of the stack is at address $sp + 4

4
MIPS Assembly

MIPS architecture
– Prototypical Reduced Instruction Set Computer (RISC)
architecture
– Arithmetic operations use registers for operands and
results
– Must use load and store instructions to use operands
and results in memory
– 32 general purpose registers (32 bits each)
• We will use $sp, $a0 and $t1 (a temporary register)

• Read the SPIM documentation for details

5
A Sample of MIPS Instructions

– lw reg1 offset(reg2)
• Load 32-bit word from address reg2 + offset into reg1
– add reg1 reg2 reg3
• reg1 ← reg2 + reg3
– sw reg1 offset(reg2)
• Store 32-bit word in reg1 at address reg2 + offset
– addiu reg1 reg2 imm
• reg1 ← reg2 + imm
• “u” means overflow is not checked
– li reg imm
• reg ← imm

6
MIPS Assembly. Example.

• The stack-machine code for 7 + 5 in MIPS:

acc ← 7 li $a0 7
push acc sw $a0 0($sp)
addiu $sp $sp -4
acc ← 5 li $a0 5
acc ← acc + top_of_stack lw $t1 4($sp)
add $a0 $a0 $t1
pop addiu $sp $sp 4

• We now generalize this to a simple language…

7
A Small Language

• A language with integers and integer operations

P → D; P | D
D → def id(ARGS) = E;
ARGS → id, ARGS | id
E → int | id | if E1 = E2 then E3 else E4
| E1 + E2 | E1 – E2 | id(E1,…,En)

8
A Small Language (Cont.)

• The first function definition f is the “main” routine

• Running the program on input i means computing
f(i)
• Program for computing the Fibonacci numbers:
def fib(x) = if x = 1 then 0 else
if x = 2 then 1 else
fib(x - 1) + fib(x – 2)

9
Code Generation Strategy

• For each expression e we generate MIPS code

that:
– Computes the value of e in $a0
– Preserves $sp and the contents of the stack

• We define a code generation function cgen(e)

whose result is the code generated for e

10
Code Generation for Constants

• The code to evaluate a constant simply copies it

into the accumulator:
cgen(i) = li $a0 i

• This preserves the stack, as required

• Color key:
– RED: compile time
– BLUE: run time

11
Code Generation for Add

cgen(e1 + e2) = cgen(e1 + e2) =

cgen(e1) cgen(e1)
sw $a0 0($sp) print “sw $a0 0($sp)”
addiu $sp $sp -4 print “addiu $sp $sp -4”
cgen(e2) cgen(e2)
lw $t1 4($sp) print “lw $t1 4($sp)”
add $a0 $t1 $a0 print “add $a0 $t1 $a0”
addiu $sp $sp 4 print “addiu $sp $sp 4”

12
Code Generation for Add. Wrong!

• Optimization: Put the result of e1 directly in $t1?

cgen(e1 + e2) =
cgen(e1)
move $t1 $a0
cgen(e2)
add $a0 $t1 $a0

• Try to generate code for : 3 + (7 + 5)

13
Code Generation Notes

• The code for + is a template with “holes” for code

for evaluating e1 and e2

• Stack machine code generation is recursive

– Code for e1 + e2 is code for e1 and e2 glued together

• Code generation can be written as a recursive-

descent of the AST
– At least for expressions

14
Code Generation for Sub and Constants

• New instruction: sub reg1 reg2 reg3

– Implements reg1 ← reg2 - reg3
cgen(e1 - e2) =
cgen(e1)
sw $a0 0($sp)
addiu $sp $sp -4
cgen(e2)
lw $t1 4($sp)
sub $a0 $t1 $a0
addiu $sp $sp 4

15
Code Generation for Conditional

• We need flow control instructions

• New instruction: beq reg1 reg2 label

– Branch to label if reg1 = reg2

• New instruction: b label

– Unconditional jump to label

16
Code Generation for If (Cont.)

cgen(if e1 = e2 then e3 else e4) =

cgen(e1)
false_branch:
sw $a0 0($sp)
cgen(e4)
addiu $sp $sp -4
b end_if
cgen(e2)
true_branch:
lw $t1 4($sp)
cgen(e3)
addiu $sp $sp 4
beq $a0 $t1 true_branch end_if:

17
The Activation Record

• Code for function calls and function definitions

depends on the layout of the AR

• A very simple AR suffices for this language:

– The result is always in the accumulator
• No need to store the result in the AR
– The activation record holds actual parameters
• For f(x1,…,xn) push xn,…,x1 on the stack
• These are the only variables in this language

18
The Activation Record (Cont.)

• The stack discipline guarantees that on function

exit $sp is the same as it was on function entry

• We need the return address

• A pointer to the current activation is useful

–This pointer lives in register $fp (frame pointer)
–Reason for frame pointer will be clear shortly

19
The Activation Record

• Summary: For this language, an AR with the

caller’s frame pointer, the actual parameters, and
the return address suffices
• Picture: Consider a call to f(x,y), the AR is:

old fp
y
AR of f
x
FP return
SP 20
Code Generation for Function Call

• The calling sequence is the instructions (of both

caller and callee) to set up a function invocation

• New instruction: jal label

– Jump to label, save address of next instruction in $ra
– On other architectures the return address is stored on
the stack by the “call” instruction

21
Code Generation for Function Call (Cont.)

cgen(f(e1,…,en)) = • The caller saves its value

sw $fp 0($sp) of the frame pointer
addiu $sp $sp -4 • Then it saves the actual
cgen(en) parameters in reverse
sw $a0 0($sp) order
addiu $sp $sp -4
• The caller saves the return
…
address in register $ra
cgen(e1)
• The AR so far is 4*n+4
sw $a0 0($sp)
bytes long
addiu $sp $sp -4
jal f_entry

22
Code Generation for Function Definition

• New instruction: jr reg

– Jump to address in register reg

cgen(def f(x1,…,xn) = e) = • Note: The frame pointer

move $fp $sp points to the top, not bottom
of the frame
sw $ra 0($sp)
• The callee pops the return
addiu $sp $sp -4 address, the actual
cgen(e) arguments and the saved
lw $ra 4($sp) value of the frame pointer
addiu $sp $sp z • z = 4*n + 8
lw $fp 0($sp)
jr $ra
23
Calling Sequence: Example for f(x,y)

Before call On entry Before exit After call

FP FP FP

SP old fp old fp SP
y y
x x
SP FP return
SP

24
Code Generation for Variables

• Variable references are the last construct

• The “variables” of a function are just its

parameters
– They are all in the AR
– Pushed by the caller

• Problem: Because the stack grows when

intermediate results are saved, the variables are
not at a fixed offset from $sp
25
Code Generation for Variables (Cont.)

• Solution: use a frame pointer

– Always points to the return address on the stack
– Since it does not move it can be used to find the
variables
• Let xi be the ith (i = 1,…,n) formal parameter of the
function for which code is being generated

cgen(xi) = lw $a0 z($fp) ( z = 4*i )

26
Code Generation for Variables (Cont.)

• Example: For a function def f(x,y) = e the

activation and frame pointer are set up as follows:

old fp
y • X is at fp + 4
x • Y is at fp + 8
FP return

SP
27
Summary

• The activation record must be designed together

with the code generator

• Code generation can be done by recursive

traversal of the AST

• We recommend you use a stack machine for your

Cool compiler (it’s simple)

28
Summary

• Production compilers do different things

– Emphasis is on keeping values (esp. current stack
frame) in registers
– Intermediate results are laid out in the AR, not pushed
and popped from the stack

29
An Improvement

• Idea: Keep temporaries in the AR

• The code generator must assign a location in the

AR for each temporary

30
Example

def fib(x) = if x = 1 then 0 else

if x = 2 then 1 else
fib(x - 1) + fib(x – 2)

• What intermediate values are placed on the

stack?

• How many slots are needed in the AR to hold

these values?

31
How Many Temporaries?

• Let NT(e) = # of temps needed to evaluate e

• NT(e1 + e2)
– Needs at least as many temporaries as NT(e1)
– Needs at least as many temporaries as NT(e2) + 1

• Space used for temporaries in e1 can be reused for

temporaries in e2

32
The Equations

NT(e1 + e2) = max(NT(e1), 1 + NT(e2))

NT(e1 - e2) = max(NT(e1), 1 + NT(e2))
NT(if e1 = e2 then e3 else e4) = max(NT(e1),1 + NT(e2), NT(e3), NT(e4))
NT(id(e1,…,en) = max(NT(e1),…,NT(en))
NT(int) = 0
NT(id) = 0

Is this bottom-up or top-down?

What is NT(…code for fib…)?

33
The Revised AR

• For a function definition f(x1,…,xn) = e the AR has

2 + n + NT(e) elements
– Return address
– Frame pointer
– n arguments
– NT(e) locations for intermediate results

34
Picture

Old FP
xn
...
x1
FP Return Addr.
Temp NT(e)
...
Temp 1

35
Revised Code Generation

• Code generation must know how many

temporaries are in use at each point

• Add a new argument to code generation: the

position of the next available temporary

36
Code Generation for + (original)

cgen(e1 + e2) =
cgen(e1)
sw $a0 0($sp)
addiu $sp $sp -4
cgen(e2)
lw $t1 4($sp)
add $a0 $t1 $a0
addiu $sp $sp 4

37
Code Generation for + (revised)

cgen(e1 + e2, nt) =

cgen(e1, nt)
sw $a0 nt($fp)

cgen(e2, nt + 4)
lw $t1 nt($fp)
add $a0 $t1 $a0

38
Notes

• The temporary area is used like a small, fixed-

size stack

• Exercise: Write out cgen for other constructs

39
Code Generation for OO Languages

Topic II

40
Object Layout

• OO implementation = Stuff from last part + more

stuff

• OO Slogan: If B is a subclass of A, then an object

of class B can be used wherever an object of
class A is expected

• This means that code in class A works unmodified

for an object of class B

41
Two Issues

• How are objects represented in memory?

• How is dynamic dispatch implemented?

42
Object Layout Example

Class A {
a: Int;
d: Int;
f(): Int { a ← a + d };
};

Class B inherits A { Class C inherits A {

b: Int; c: Int;
f(): Int { a }; h(): Int { a ← a + c };
g(): Int { a ← a + b }; };
};

43
Object Layout (Cont.)

• Attributes a and d are inherited by classes B and

C

• All methods in all classes refer to a

• For A methods to work correctly in A, B, and C

objects, attribute a must be in the same “place” in
each object

44
Object Layout (Cont.)

An object is like a struct in C. The reference

foo.attribute
is an index into a foo struct at an offset
corresponding to attribute

Objects in Cool are implemented similarly

– Objects are laid out in contiguous memory
– Each attribute stored at a fixed offset in object
– When a method is invoked, the object is self

45
Cool Object Layout

• The first 3 words of Cool objects contain header

information:
Offset

Class Tag 0
Object Size 4
Dispatch Ptr 8
Attribute 1 12
Attribute 2 16
...

46
Cool Object Layout (Cont.)

• Class tag is an integer

– Identifies class of the object
• Object size is an integer
– Size of the object in words
• Dispatch ptr is a pointer to a table of methods
– More later
• Attributes in subsequent slots

• Lay out in contiguous memory

47
Subclasses

Observation: Given a layout for class A, a layout for

subclass B can be defined by extending the
layout of A with additional slots for the additional
attributes of B

Leaves the layout of A unchanged

(B is an extension)

48
Layout Picture

Offset 0 4 8 12 16 20
Class

A Atag 5 * a d

B Btag 6 * a d b

C Ctag 6 * a d c

49
Subclasses (Cont.)

• The offset for an attribute is the same in a class

and all of its subclasses
– Any method for an A1 can be used on a subclass A2
• Consider layout for An < … < A3 < A2 < A1

Header A1 object

A1 attrs. A2 object

A2 attrs A3 object

A3 attrs
...
50
Object Layout Example (Repeat)

Class A {
a: Int;
d: Int;
f(): Int { a ← a + d };
};

Class B inherits A { Class C inherits A {

b: Int; c: Int;
f(): Int { a }; h(): Int { a ← a + c };
g(): Int { a ← a + b }; };
};

51
Dynamic Dispatch Example

• e.g()
– g refers to method in B if e is a B
• e.f()
– f refers to method in A if e is an A or C
(inherited in the case of C)
– f refers to method in B if e is a B

• The implementation of methods and dynamic

dispatch strongly resembles the implementation
of attributes

52
Dispatch Tables

• Every class has a fixed set of methods

(including inherited methods)

• A dispatch table indexes these methods

– An array of method entry points
– A method f lives at a fixed offset in the dispatch table
for a class and all of its subclasses

53
Dispatch Table Example

Offset 0 4 • The dispatch table for

Class class A has only 1 method
• The tables for B and C
A fA extend the table for A to
the right
B fB g
• Because methods can be
overridden, the method for
f is not the same in every
C fA h class, but is always at the
same offset

54
Using Dispatch Tables

• The dispatch pointer in an object of class X points

to the dispatch table for class X

• Every method f of class X is assigned an offset Of

in the dispatch table at compile time

55
Using Dispatch Tables (Cont.)

• To implement a dynamic dispatch e.f() we

– Evaluate e, giving an object x
– Call D[Of]
• D is the dispatch table for x
• In the call, self is bound to x

56