Go, change the world
RV College of
Engineering
Compiler Design(16CS62)
Code Generation
Unit V
1
RV College of
Engineering Outline Go, change the world
•Code Generation Issues
•Target language Issues
•Basic Blocks and Flow Graphs
•Optimizations of Basic Blocks
•Addresses in Target Code
•A Simple Code Generator
•Peephole optimization
2
RV College of
Engineering Introduction Go, change the world
The final phase of a compiler is code generator
It receives an intermediate representation (IR) with supplementary
information in symbol table
Produces a semantically equivalent target program
Code generator main tasks:
Instruction selection
Register allocation and assignment
Instruction ordering
Code
Front end Code optimizer
Generator
3
RV College of
Engineering Issues in Code Generator Go, change the world
• Input to the code generator
• The target program
• Instruction Selection
• Register allocation
• Evaluation Order
4
Input to the code generator
•IR + Symbol table
•IR
1) Three address code representations Quadruples, Triples,
Indirect triples
2) Virtual Machine Representations Byte codes
3) Graphical Representations Syntax Trees and DAGs
•Syntactic and semantic errors have been already detected
5
The target program
Common target architectures are:
RISC (Reduced Instruction Set Computer)
CISC (Complex Instruction Set Computer)
Stack based machines
6
Instruction Selection
Mapping IR to code sequence is determined by 3 factors
• Level of the IR
• Nature of the instruction-set architecture
• Desired quality of the generated code
a=b+c
x=y+z d=a+e
LD R0, b
LD R0, y
ADD R0, R0, c
ADD R0, R0, z
ST a, R0
ST x, R0
LD R0, a
ADD R0, R0, e 7
STd, R0
Register allocation
• Two subproblems
❖Register allocation: selecting the set of variables that will reside in registers at each
point in the program
❖Resister assignment: selecting specific register that a variable reside in
• Complications imposed by the hardware architecture
Example: register pairs for multiplication(even/odd) and division(dividend-Even-odd
register pair)
•(Shift right double arithmetic)
L R0, a
t=a+b L R1, a A R0, b
t=t*c A R1, b t=a+b
M R0, c
T=t/d M R0, c t=t+c
SRDA R0, 32
D R0, d T=t/d
D R0, d
ST R1, t ST R1, t 8
Evaluation Order
• Order in which computations are performed
• Registers to be allocated to store intermediate results
9
RV College of
Engineering The target Language Go, change the world
•A Simple Target Machine Model
•Program and Instruction costs
10
A simple target machine model
❖ Three address machine
❖ Byte Addressable with n GPRs R0 to Rn-1
❖ Assume operands as integers
• Load operations: LD dst,addr LD r,x and LD r1, r2
• Store operations: ST addr, src ST x,r
• Computation operations: OP dst, src1, src2
• Unconditional jumps: BR L
• Conditional jumps: Bcond r, L like BLTZ r, L
11
Addressing Modes
• variable name: x
• indexed address: a(r) like LD R1, a(R2) means R1=contents(a+contents(R2))
• integer indexed by a register : like LD R1, 100(R2) R1=contents (100+contents(R2))
• Indirect addressing mode: *r and *100(R2) R1=contents(contents(100+contents(R2))
• immediate constant addressing mode: like LD R1, #100
12
Examples
x=y-z x=y-z
LD R1,y SUB R1, x, y
LD R2,z ST x, R1
SUB R1,R1,R2
ST x,R1
13
b = a [i]
LD R1, i //R1 = i
MUL R1, R1, 8 //R1 = Rl * 8
LD R2, a(R1) //R2=contents(a+contents(R1))
ST b, R2 //b = R2
14
a[j] = c
LD R1, c //R1 = c
LD R2, j // R2 = j
MUL R2, R2, 8 //R2 = R2 * 8
ST a(R2), R1 //contents(a+contents(R2))=R1
15
x=*p
LD R1, p //R1 = p
LD R2, 0(R1) // R2 = contents(0+contents(R1))
ST x, R2 // x=R2
16
*p=y
LD R1, p //R1 = p
LD R2, y // R2=y
ST 0(R1), R2 // contents(0+contents(R1))=R2
17
Conditional-jump three-address instruction
if x<y goto L
LD R1, x // R1 = x
LD R2, y // R2 = y
SUB R1, R1, R2 // R1 = R1 – R2
BLTZ R1, M // i f R1 < 0 jump to M
18
RV College of
Engineering Program and Instruction Cost Go, change the world
Common cost measures
Compilation time
Size of the program
Running time
Power Consumption
19
Costs associated with the addressing modes
LD R0, R1 cost = 1
LD R0, M cost = 2
LD R1, *100(R2) cost = 3
20
Examples
Determine the cost of the following instruction sequences
LD R0, R1 cost = 1
LD R0, M cost = 2
LD R1, *100(R2) cost = 3
21
RV College of
Engineering Examples Go, change the world
22
RV College of
Engineering Basic blocks and flow graphs Go, change the world
•Graph representation of intermediate code
•Partition the intermediate code into basic blocks
❖The flow of control can only enter the basic block through the first instruction in the
block. That is, there are no jumps into the middle of the block.
❖Control will leave the block without halting or branching, except possibly at the last
instruction in the block.
•The basic blocks become the nodes of a flow graph, edges indicate which block follows
which other block
23
Go, change the world
RV College of
Engineering Constructing Basic Blocks
1) Determine a set of leaders, the first instruction of blocks
2) A basic block consists of a leader and all the following instructions until the
next leader
24
RV College of
Engineering Constructing Basic Blocks Go, change the world
1. Elect Leader
First three-address instn in the intermediate code is a leader
Any instn that is a target of a conditional or unconditional jump is a leader
Any instn that immediately follows a conditional or unconditional jump is a
leader
2. For each leader its basic blocks consists of itself and all instn up to but not
including the next leader or end of intermediate program
25
RV College of
Engineering Constructing Basic Blocks Go, change the world
Where,
B = Base address
I = Row subscript of element whose address is to be found
J = Column subscript of element whose address is to be found
W = Storage Size of one element stored in the array (in byte)
Lr = Lower limit of row/start row index of matrix, if not given assume
0 (zero)
Lc = Lower limit of column/start column index of matrix, if not given
assume 0 (zero)
M = Number of row of the given matrix
N = Number of column of the given matrix
Address of A [ I ][ J ] = B + W * [ N * ( I – Lr ) + ( J – Lc ) ]
T3=(N*I+J)*W ( N*-Lr-Lc)*W=-88
Address of A [ I ] = B + W * ( I – LB
26
)
RV College of
Engineering Identify leaders Go, change the world
First three-address instn in the intermediate code
is a leader
Any instn that is a target of a conditional or
unconditional jump is a leader
Any instn that immediately follows a conditional
or unconditional jump is a leader
27
RV College of
Engineering Flow Graph Go, change the world
Once an intermediate-code program is partitioned into basic blocks, we
represent the flow of control between them by a flow graph.
28
1. There is a conditional or unconditional jump from the
Constructing the end of B to the beginning of C
Flow Graph
There is an edge from block B to
block C iff it is possible for the first
instruction in block C to immediately
follow the last instruction in block B
29
2. C immediately follows B in the original order of the
Constructing the three-address instructions, and B does not end in an
Flow Graph unconditional jump
There is an edge from block B to
block C iff it is possible for the first
instruction in block C to immediately
follow the last instruction in block B
30
1. There is an edge from the entry to the first executable
Constructing the node.
Flow Graph
Often we add two nodes, called the
entry and exit.
31
2. There is an edge to the exit from any basic block that
Constructing the contains an instruction that could bet eh last executed
Flow Graph instruction of the program
Often we add two nodes, called the
entry and exit.
32
33
goto B
1. There is a node in L called the loop entry with the property
Loops that no other node in L has a predecessor outside L. That is
, every path from the entry of the entire flow graph to any
node in L goes through the loop entry.
{B2,B3,B4}, has B2 as its loop entry, among 3 nodes on B2 has
predecessor B1 not in L
We say that a set of nodes L in a flow
graph is a loop if
34
2. Every node in L has a nonempty path, completely within
Loops L, to the entry of L.{B2 B3 B4 B2}
We say that a set of nodes L in a flow
graph is a loop if
35
RV College of
Engineering Outline Go, change the world
• Code Generation Issues
• Target language Issues
• Basic Blocks and Flow Graphs
• Optimizations of Basic Blocks
• Addresses in Target Code
• Peephole optimization
• A Simple Code Generator
36
RV College of
Engineering Optimization of basic blocks Go, change the world
DAG Representation of basic block eliminates
Eliminates Local common subexpressions
Eliminates Dead Code
Reorder statement
Apply algebraic laws to reorder operands to simplify computation
37
RV College of
Engineering Elimination of common sub expression Go, change the world
Rewritten as
a=b+c
d=a-d
c=d+c {c=a-d+c}
Assuming b is not live outside basic block
If i assign a value to x, if j has x as an operand and control can flow from i to j
without any intervening assignments to x then we say x is live at i 38
RV College of
Engineering Elimination of Dead Code Go, change the world
39
RV College of
Engineering Reorder Statements Go, change the world
a= b-c a= b-c
z= x+y d= a-k
m= p-q z= x+y
t= v-l m= p-q
d= a-k t= v-l
40
RV College of
Engineering Apply Algebraic Laws Go, change the world
Apply arithmetic identities
Replace expensive operator by cheaper one
Use constant folding (evaluated during compile time)
2 * 3.1 4 as 6.28
Use associativity and commutativity
41
RV College of
Engineering Representation of Array references Go, change the world
An assignment from an array, like x = a [i], is represented by creating a node with
operator =[] and two children representing the initial value of the array, a0 in this
case, and the index i. Variable x becomes a label of this new node.
An assignment to an array, like a [j] = y, is represented by a new node with operator
[]= and three children representing a0, j and y. There is no variable labeling this
node.
42
RV College of
Engineering Representation of Array references Go, change the world
43
RV College of
Engineering Addresses in Target Code Go, change the world
• How names in IR can be converted into addresses
A statically determined area Code (Size determined at Compile time)
A statically determined data area Static (Global Constant determined at CT)
A dynamically managed area Heap ( Allocation done in execution -Heap)
A dynamically managed area Stack (Holding Activation Records-Procedure Calls)
44
RV College of
Engineering Static Allocation Go, change the world
• call callee
• Return
• Halt
• Action(Placeholder for other three address instructions)
45
RV College of
Engineering Static Allocation Go, change the world
• First location in activation holds the return address
Target machine instruction for call callee
ST [Link], #here+20 //Stores return address in AR
BR [Link]
Target machine instruction for return callee
BR *[Link] //Transfers control to the address saved at the beginning of AR for
callee
46
RV College of
Engineering Sample Program Go, change the world
47
RV College of
Engineering Stack Allocation Go, change the world
The position of an activation record for a procedure will not known until run time
These positions are stored in a register, so words in AR can be accessed as offset from
value in register
Branch to called procedure
Return to caller
in Callee: BR *0(SP)
in caller:SUB SP, SP, #[Link]
48
RV College of
Engineering Stack Allocation Go, change the world
49
RV College of
Engineering Runtime addresses for names Go, change the world
X=0
Static[12]=0
LD 112, #0
50
RV College of
Engineering Peephole Optimization Go, change the world
Effective technique for locally improving the target code done by examining a sliding
window of target instructions (called the peephole) and replacing instruction sequences
within the peephole by a shorter or a faster sequence
51
RV College of
Engineering Characteristics of peephole optimization Go, change the world
52
RV College of
Engineering Redundant instruction Elimination Go, change the world
Elimination of redundant loads and stores
Eliminating unreachable code(code
next to uncond jump)
53
RV College of
Engineering Flow of control optimization Go, change the world
54
RV College of
Engineering Algebraic Simplifications Go, change the world
X=X+0
X=X*1
Three address code can be eliminated
55
RV College of
Engineering Use of Machine Idioms Go, change the world
Auto-increment Addressing mode
Auto-Decrement Addressing mode
56
RV College of
Engineering Cost of Instructions Go, change the world
Determine the cost of the following
instruction sequences
LD R0, R1 cost = 1
LD R0, M cost = 2
LD R1, *100(R2) cost = 3
57
RV College of
Engineering Outline Go, change the world
• Code Generation Issues
• Target language Issues
• Basic Blocks and Flow Graphs
• Optimizations of Basic Blocks
• Addresses in Target Code
• Peephole optimization
• A Simple Code Generator
58
RV College of
Engineering A Simple Code Generator Go, change the world
Uses of registers
In most machine architectures, some or all of the operands of an operation must be in
registers in order to perform the operation.
Registers make good temporaries - places to hold the result of a sub-expression while a
larger expression is being evaluated, or more generally, a place to hold a variable that is
used only within a single basic block.
Registers are often used to help with run-time storage management, for example, to
manage the run-time stack, including the maintenance of stack pointers and possibly the
top elements of the stack itself.
59
RV College of
Engineering A Simple Code Generator Go, change the world
Descriptors for data structure(Register and Variable)
For each available register, a register descriptor keeps track of the variable names
whose current value is in that register. Since we shall use only those registers that
are available for local use within a basic block, we assume that initially, all register
descriptors are empty. As the code generation progresses, each register will hold the
value of zero or more names.
For each program variable, an address descriptor keeps track of the location or
locations where the current value of that variable can be found. The location might
be a register, a memory address, a stack location, or some set of more than one of
these. The information can be stored in the symbol-table entry for that variable
name.
60
RV College of
Engineering A Simple Code Generator Go, change the world
Machine Instructions for Operations
• Use getReg(x = y + z) to select registers for x, y, and z. Call these Rx, Ry and Rz.
• If y is not in Ry (according to the register descriptor for Ry), then issue an
instruction LD Ry, y', where y' is one of the memory locations for y (according to
the address descriptor for y).
• Similarly, if z is not in Rz, issue and instruction LD Rz, z', where z' is a location for Z
• Issue the instruction ADD Rx , Ry, Rz.
61
RV College of
Engineering A Simple Code Generator Go, change the world
Machine Instructions for Copy Statement
• x=y
• LD Ry, y,
• Register descriptor Ry, includes x as one of the value found
62
RV College of
Engineering A Simple Code Generator Go, change the world
Ending the Basic Block
• Local to basic block-Lose its scope after block ends
• If variable is LIVE on exit?? ST x,R
main(){
int a,c=2;
{
int b=20;
b=30;
a=40;
}
a=a+c;
}
63
RV College of
Engineering A Simple Code Generator Go, change the world
Rules for updating the register and address descriptors
For the instruction LD R, x
Change the register descriptor for register R so it holds only x.
Change the address descriptor for x by adding register R as an additional location.
For the instruction ST x, R, change the address descriptor for x to include its own memory
location
For an operation such as ADD Rx, Ry, Rz implementing a three-address instruction x = y + z
Change the register descriptor for Rx so that it holds only x.
Change the address descriptor for x so that its only location is Rx. Note that the memory
location for x is not now in the address descriptor for x.
Remove Rx from the address descriptor of any variable other than x.
When we process a copy statement x = y, after generating the load for y into register R y, if
needed, and after managing descriptors as for all load statements (per rule I):
Add x to the register descriptor for Ry.
Change the address descriptor for x so that its only location is Ry .
64
RV College of
Engineering A Simple Code Generator Go, change the world
Instructions generated and the changes in the register and address descriptors
65
RV College of
Engineering A Simple Code Generator Go, change the world
Design of the function getReg()-Rules for picking register Ry for y
If y is currently in a register, pick a register already containing y as Ry. Do not
issue a machine instruction to load this register, as none is needed.
If y is not in a register, but there is a register that is currently empty, pick one
such register as Ry.
The difficult case occurs when y is not in a register, and there is no register that
is currently empty. We need to pick one of the allowable registers anyway, and
we need to make it safe to reuse.
66
RV College of
Engineering A Simple Code Generator Go, change the world
Possibilities for value of R
If the address descriptor for v says that v is somewhere besides R, then we are OK
If v is x, the value being computed by instruction I, and x is not also one of the other
operands of instruction I (z in this example), then we are OK. The reason is that in
this case, we know this value of x is never again going to be used, so we are free to
ignore it.
Otherwise, if v is not used later (that is, after the instruction I, there are no further
uses of v, and if v is live on exit from the block, then v is recomputed within the
block), then we are OK.
If we are not OK by one of the first two cases, then we need to generate the store
instruction ST v, R to place a copy of v in its own memory location. This operation is
called a spill.
67
RV College of
Engineering A Simple Code Generator Go, change the world
Selection of the register Rx
1. Since a new value of x is being computed, a register that holds only x is always an
acceptable choice for Rx.
2. If y is not used after instruction I, and Ry holds only y after being loaded, Ry can
also be used as Rx. A similar option holds regarding z and Rx.
68
RV College of
Engineering Examples-Flowgraphs Go, change the world
69
RV College of
Engineering Examples-Flowgraphs Go, change the world
L1
L2 L4
L3 L5
L6
70
RV College of
Engineering Examples-Flowgraphs Go, change the world
71
RV College of
Engineering Examples-Flowgraphs Go, change the world
72
RV College of
Engineering Examples-Flowgraphs Go, change the world
0: i=0
1:if(i>=N) goto L1
2. if(i>=j) goto L5
3:if(a[i]>=a[j]) goto L3
4:tmp = a[j]
5: a[j] = a[i]
6: a[i] = tmp
7. Goto L2
8.L3:if(a[i]!=a[j]) goto L4
[Link] L2
11.L4 gotoL5
12.L2:j=j+1
13.L5:i=i+1
14.L1:
73
RV College of
Engineering
Go, change the world
Questions??
74