Code generation in Compiler Design

Code Generation & Register
Allocation
Object code forms - register allocation and
assignment, DAG for register allocation,
Generic code generation algorithms.

Register Allocation and Assignment
• Instruction involving only register operands are shorter and faster than
those involving memory operands.
• This approach has the advantage that it simplifies the design of a
compiler.
Disadvantage:
• It uses registers inefficiently;
• Certain registers may go unused over substantial portions of code,
while unnecessary loads and stores are generated.

Some Issues in Register Allocation
• Which values in a program reside in registers?
– register allocation
• In which register?
– register assignment

The Problem
• Global Register Allocation assumes that allocation is done beyond basic
blocks and usually at function level
• Decision problem related to register allocation:
– Given an intermediate language program represented as a control flow
graph and a number k, is there an assignment of registers to program
variables such that no conflicting variables are assigned the same register,
no extra loads or stores are introduced, and at most k registers are used?
• This problem has been shown to be NP-hard.
• Graph colouring is the most popular heuristic used.
• However, there are simpler algorithms as well

Various strategies used in register assignment
• Global Register Allocation
• Usage Counts
• Register Assignment for Outer Loops
• Register Allocation by Graph Coloring

Global Register Allocation
• When generating the code, the registers are used to hold the value for
the duration of single block.
• All the live variables are stored at the end of each block.
• For the variables that are used consistently we can allocate specific
set of registers.
• Hence allocation of variables to specific registers that is consistent
across the block boundaries is called global register allocation.

• The global register allocation has a strategy of storing the most
frequently used variables in fixed registers throughout the loop
• Another strategy is to assign some fixed number of global
registers to hold the most active value in each inner loop.
• In C program, we can use register storage class to demand for
register allocation globally.
Global Register Allocation

Usage Counts
• Allocate registers for variables used within loops
• Requires information about liveness of variables at the entry and
exit of each Basic Block (BB) of a loop
• Once a variable is computed into a register, it stays in that register
until the end of the BB (subject to existence of next-uses)
• Load/Store instructions cost 2 units (because they occupy two
words)

• The usage count gives the idea about how many units of cost can be
saved by selecting a specific variable for global register allocation.
• The approximate formula for usage count for the loop L in some basic
block B can be given as, i.e. Total savings per variable x is
෍
𝑩𝒍𝒐𝒄𝒌 𝑩 𝒊𝒏 𝑳
(𝒖𝒔𝒆 𝒙, 𝑩 + 𝟐 ∗ 𝒍𝒊𝒗𝒆(𝒙, 𝑩))
– Where use (x, B) is number of times x used in block B prior to
any definition of x and
– live (x, B) =1 is live on exit from B; otherwise live(x)=0.
Usage Counts

Global Register Allocation via Usage Counts (for Single
Loops)
use(a, B1)=0, since a is defined before any use.
use + 2 * live

• a is live on exit from B1 and is assigned a value there, but is not
live on exit from B2, B3, or B4.
– 2*live(a , B1)=2.
– use(a, B1)=0, since a is defined before any use.
– use(a, B2)=use(a, B3)=1 and use(a, B4)=0.
Global Register Allocation via Usage Counts
(for Single Loops)

Global Register Allocation via Usage Counts (for
Nested Loops)
• We first assign registers for inner loops and then
consider outer loops. Let L1 nest L2
– If an outer loop L1, contains an inner loop L2,
• For variables assigned registers in L2, but not in L1,
– load these variables on entry to L2 and store
them on exit from L2
• For variables assigned registers in L1, but not in L2,
– store these variables on entry to L2 and load
them on exit from L2
{
int H,A,L;
{
float x,y;
:
:
}
}
L1
L2

Register Allocation by Graph Coloring
• A register is needed for a computation but all available registers are in use, the
contents of one of the used registers must be stored (Spilled) into a memory
location in order to free up register.
– Graph coloring is a simple systematic technique for allocating registers and
managing register spills.
• In this method, two passes are used.
– In the first pass, target-machine instruction are selected as though there
were infinite number of symbolic registers; in effect, names used in the
intermediate code become names of registers and the three-address
statements become machine language statements.
– In the second pass, for each procedure a register-interference graph is
constructed in which the nodes are symbolic registers and an edge connects
two nodes if one is live at a point where the other is defined.
• An attempt is made to color the register-interference graph using k colors,
where k is the number of assignable registers.

• The main idea is to replace temporary variables with some fixed set of
registers
• First: Need to know which variables are live after each instruction
– Two live variables cannot be allocated to the same register
simultaneously

Register allocation
• For every node n in Control Flow Graph, we have out[n]
– Set of temporaries live out of n
• Two variables interfere if
– both initially live (i.e. function args), or
– both appear in out[n] for any n, or
– one is defined and the other is in out[n]
• x = b - c where x is dead & b is live interfere
• How to assign registers to variables?

Interference graph
• Nodes of the graph = variables
• Edges connect variables that interfere with one another
• Nodes will be assigned a color corresponding to the register
assigned to the variable
• Two colors cannot be next to one another in the graph
Instructions Live variables
b = a + 2
c = b * b
b = c + 1
return b * a

Interference graph
b = a + 2
c = b * b
b = c + 1
return b * a b,a

Interference graph
b = a + 2
c = b * b
b = c + 1 a,c
return b * a b,a

Interference graph
b = a + 2
c = b * b b,a
b = c + 1 a,c
return b * a b,a

Interference graph
b = a + 2 a
c = b * b b,a
b = c + 1 a,c
return b * a b,a

Interference graph
a
c
b
ax
bx
color register
b = a + 2 a
c = b * b b,a
b = c + 1 a,c
return b * a b,a

Interference graph
a
c
b
ax
bx
color register
b = a + 2 a
c = b * b a, b
b = c + 1 a, c
return b * a a, b

Graph coloring
• Questions:
– Can we efficiently find a coloring of the graph whenever possible?
– Can we efficiently find the optimum coloring of the graph?
– How do we choose registers to avoid move instructions?
– What do we do when there are not enough colors (registers) to color the graph?
Kempe’s algorithm for finding a K-coloring of a graph
• Assume K=2
• Step 1 (simplify): find a node with at most K-1 edges and cut it out of the
graph. (i.e. remember this node on a stack for later stages.)
• Once a coloring is found for the simpler graph, we can always color the node
we saved on the stack
• Step 2 (color): when the simplified sub-graph has been colored, add back the
node on the top of the stack and assign it a color, which is not taken by one of
the adjacent nodes

Coloring
b
e
d
ax
bx
color register
a
c
stack:

Coloring
b
e
d
a
stack:
c
c
ax
bx
color register

Coloring
b
e
d
a
stack:
e
c
c
ax
bx
color register

Coloring
b
e
d
a
stack:
a
e
c
c
ax
bx
color register

Coloring
b
e
d
a
stack:
b
a
e
c
c
ax
bx
color register

Coloring
b
e
d
a
stack:
d
b
a
e
c
c
ax
bx
color register

Coloring
b
e
d
a
stack:
c
ax
bx
color register

• Register spilling or reloading:
– If there are not enough registers to hold all the variables, some variables may
be moved to and from RAM. This process is called "spilling" the registers
• Coalescing
– In the context of register allocation, coalescing is the act of merging variable-
to-variable move operations by allocating those two variables to the same
location.
– The coalescing operation takes place after the interference graph is built.
Once two nodes have been coalesced, they must get the same color and be
allocated to the same register.

Coalescing
• Allocate source and destination of copy to same register
• To eliminate register-to-register copies
• Combines live ranges
• Examples

Code Generation – Main Issues
• Transformation
– Type of Intermediate Code Representation  Quadruple
– Intermediate code to Machine code (binary or assembly)
– We assume quadruples and CFG to be available
• Selection of instruction  Which instructions to generate?
– For the quadruple A = A+1, we may generate
inc A
or
Load A, R1
Add #1, R1
Store R1, A
– One sequence is faster than the other (cost implication)

• Ordering of Instruction  In which order?
– Some orders may use fewer registers and/or may be faster
• Register allocation  Which registers to use?
– Optimal assignment of registers to variables is difficult to
achieve
• Optimize for memory, time or power?
• Is the code generator easily retargetable to other machines?
– Can the code generator be produced automatically from
specifications of the machine?
Code Generation – Main Issues

Samples of Generated Code
• B = A[i]
Load i, R1 // R1 = i
Mult R1, 4, R1 // R1 = R1*4
// each element of array
// A is 4 bytes long
Load A(R1), R2 // R2=(A+R1)
Store R2, B // B = R2
• X[j] = Y
Load Y, R1 // R1 = Y
Load j, R2 // R2 = j
Mult R2, 4, R2 // R2=R2*4
Store R1, X(R2)// X(R2)=R1
• if X < Y goto L
Load X, R1
Load Y, R2
Cmp R1, R2 // compare words at
memory addresses pointed by
registers R1 and R2
Blt L //jump to L if (R1) is less
than (R2)
Blt – Branch if Less Than

A Simple Code Generator - I
• Treat each quadruple as a ‘macro’
– Example: The quad A = B + C will result in
Load B, R1
Load C, R2
Add R2, R1
Store R1, A
• Results in inefficient code
– Repeated load/store of registers
• Very simple to implement
Load B, R1
Add C, R1
Store R1, A
(OR)

• Track values in registers and reuse them
– If any operand is already in a register, take advantage of it.
• Register descriptors (RD)
– Tracks <register, variable name> pairs
– A single register can contain values of multiple names, if they are all
copies.
• Address descriptors (AD)
– Tracks <variable name, locations> pairs
– A single name may have its value in multiple locations, such as, memory,
register, and stack
A Simple Code Generator - II

• Register descriptor :
– Register descriptor is used to inform the code generator about the availability of
registers.
– Register descriptor keeps track of values stored in each register.
– Whenever a new register is required during code generation, this descriptor is
consulted for register availability.
• Address descriptor :
– Values of the names (identifiers) used in the program might be stored at
different locations while in execution.
– Address descriptors are used to keep track of memory locations where the
values of identifiers are stored.
– These locations may include CPU registers, heaps, stacks, memory or a
combination of the mentioned locations.
Code generator keeps both the descriptor updated in real-time

Example – use of RD & AD
• For a load statement, LD R1, x  the code generator:
– updates the Register Descriptor R1 that has value of x and
– updates the Address Descriptor (x) to show that one instance of x is in R1.

• Keep the computed result in a register as long as possible
• Store only at the end of a basic block or when that register is needed for
another computation
– On exit from a basic block, store only live variables which are not in their
memory locations already (use address descriptors to determine the later)
– If liveness information is not known, assume that all variables are live at all
times

Example
• A = B+C
1. If B and C are in registers R1 and R2, then generate
• ADD R2, R1 (cost = 1, result in R1)
– legal only if B is not live after the statement. Because B is
destroyed. Earlier R1 contains B.
2. If R1 contains B, but C is in memory
i. ADD C, R1 (cost = 2, result in R1) //we need to fetch from memory
location C
or
ii. LOAD C, R2
ADD R2, R1 (cost = 3, result in R1)
– legal only if B is not live after the statement
– attractive if the value of C is subsequently used (it can be taken
from R2). We need not again load C to register R2.

Next Use Information
• Next use info is used in code generation and register allocation
• Next use of A in quad i is j if
Quad i : A = ... (assignment to variable A)
(control flows from i to j with no assignments to A)
Quad j : = A op B (usage of A) //Next use of A in Quad i is in Quad j.
• In computing next use, we assume that on exit from the basic block
– All temporaries are considered non-live
– All programmer defined variables (and non-temps) are live
• Each procedure/function call is assumed to start a basic block
• Next use is computed on a backward scan on the quadruples in a basic
block, starting from the end
• Next use information is stored in the symbol table

Terminologies used
• Next Use Info  usefully to retain those values which are used later in
registers
• nlv - not live
• lv - live
• lu -last use
• nu - next use
• nnu – not next use

• we can compute next use information (nu) using last use information (lu)
Computing Next Use by Backward Scan

Note on Algorithm
• There is only local register allocation
• Location L is obtained by GETREG(). L could be a memory location. But
normally, it is a register.
• Location of B is B’.
– For each variable, Address descriptor tells us where exactly it is located.
• Update descriptors  L contains the result. L contains a value for A.

• Code generator uses getReg function to determine the status of available
registers and the location of name values.
• getReg() works as follows:
– If variable Y is already in register R, it uses that register.
– else if some register R is available, it uses that register.
– else if both the above options are not possible, it chooses a register that
requires minimal number of load and store instructions.
Function getReg()

Example – To understand code generation process
• T,U, and V are temporaries - not live at the end of the block
– If it is not live, we need not store it at the end of the block.
• W is a non-temporary - live at the end of the block
– If it is live, we need to store it at the end of the block
• Assume that there are 2 registers.
• Initially, all the registers are free, when we process 1st instruction in the
basic block.

Example
• Finally, code generation is completed for this basic block.

DAG representation of basic blocks
• DAG is useful data structures for implementing transformations on
basic blocks
• Gives a picture of how value computed by a statement is used in
subsequent statements
• Good way of determining common sub-expressions
• A DAG for a basic block has following labels on the nodes
– leaves are labeled by unique identifiers, either variable names or
constants
– interior nodes are labeled by an operator symbol
– nodes are also optionally given a sequence of identifiers for labels

Rearranging order of the code
• Consider following basic block and its DAG.

• Three address code for the DAG (assuming only two registers are
available)

• Rearranging the code as shown below,
Rearranging order of the code

Reference
• A.V. Aho, M.S. Lam, R. Sethi, J. D. Ullman,
Compilers Principles, Techniques and Tools,
Pearson Edition, 2013.
P. Kuppusamy - Lexical Analyzer

Code generation in Compiler Design

Recommended

More Related Content

What's hot (20)

Similar to Code generation in Compiler Design (20)

More from Kuppusamy P (20)

Recently uploaded (20)

Code generation in Compiler Design