Unit-V Subject: Compiler Design

UNIT-V
Code Generation: Issues in the Design of a Code Generator, The Target Language,
addresses in the Target Code, Basic Blocks and Flow graphs, Optimization of Basic Blocks,
Peephole Optimization, Register Allocation and Assignment.
Machine-Independent Optimizations: The Principal Sources of Optimizations,
Introduction to Data-Flow Analysis.

CODE GENERATION:
The final phase of a compiler is code generator. Code generation is the process of
creating machine language
It receives an intermediate representation (IR) from front end of compiler along with
supplementary information in symbol table and produces a semantically equivalent
target program/object code.

Properties desired by an object code generation phase:

• Correctness
• High Quality
• Efficient use of resource of target machine
• Quick code generation
Output of code generation phase is machine code/object code

Forms of object code

• Absolute Code: Machine code that contains references to actual addresses
within programs address space. It can be placed directly in the memory and
execution starts immediately.
o Examples: WATFIV and PL/C produces Absolute code
• Relocatable machine code: It allows subprograms to be compiled separately.
Allows linking and loading of already compiled subroutines.
• Assembler code: It makes code generation process somewhat easier. Slower
(because, assembling, linking, and loading is required)

ISSUES IN THE DESIGN OF A CODE GENERATOR:

The most important criterion for the target code is

Correct code: The target program must preserve the semantic meaning of the
source program and be of high quality
• Correctness
• High-quality
• Efficient use of resources of target code

Dept. of CSE, MEC 2021-2022

Unit-V Subject: Compiler Design

• Quick code generation

Input to the code generator
• IR + Symbol table
We assume front end produces low-level IR, i.e., values of names in it can be
directly manipulated by the machine instructions. Syntactic and semantic errors
have been already detected.
The target programs
Common target architectures are RISC, CISC and Stack based machines. We use a
very simple RISC-like computer with addition of some CISC-like addressing modes
Code generator main tasks:
• Instruction selection
The code generator must map the IR program into a code sequence that can
be executed by the target machine. The complexity of performing this
mapping is determined by factors such as
o The level of the IR
o The nature of the instruction-set architecture.
o The desired quality of the generated code.
Selection of instruction depends on the instruction set of target machine.
Speed of instruction and machine idioms are two important factors in
selection of instruction.
The quality of the generated code is usually determined by its speed and size.
Example:
x=y +z LD R0, b
a=b+c ADD R0, R0, c
LD R0, y
ADD R0, R0, z d=a+e ST a, R0
Useless
ST x, R0 LD R0, a
ADD R0, R0, e
ST d, R0
• Register allocation and assignment
A key problem in code generation is deciding what values to hold in what
registers. Registers are the fastest computational unit on the target machine,
but we usually do not have enough of them to hold all values.

Two subproblems are:

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 resides in.

Complications imposed by the hardware architecture.

Example:
o register pairs for multiplication and division
The product occupies the entire even/odd register pair.
After division, the even register holds the remainder and the odd register the
quotient.

Dept. of CSE, MEC 2021-2022

Unit-V Subject: Compiler Design

• Instruction ordering
Evaluation order is an important factor in generating an efficient target code.
Some orders require a smaller number of registers to hold intermediate results
than the other orders.
• Picking up the best order is difficult.
• Picking a best order is another NP- Complete
• Mostly, the order in which the three-address code is generated, same order is
followed.

THE TARGET LANGUAGE:

Prior knowledge about the target machine and its instruction set is a prerequisite for
designing a good code generator. We use a simple target language assembly code for
a simple computer.

A Simple Target Machine Model

• Load operations: The instruction LD dst, addr loads the value in location addr
into location dst.
o LD r, x (location x into register) and LD r1, r2 (register-to-register)
• Store operations: ST x, r (stores the value in register r into the location x).
• Computation operations: OP dst, src1, src2
o where OP is an operator like ADD, SUB, MOV and dst, src1, and src2 are
locations. ex: SUB r1, r2, r3 <=> r1 = r2 - r3.
• Unconditional jumps: BR L
o BR stands for branch. BR L causes the control to move to label L
• Conditional jumps: Bcond r, L like BLTZ r, L
o Where ‘r’ is a register, L is a label, and cond stands for any of the common
tests on values in the register r.

ADDRESSES IN THE TARGET CODE:

Target machine has a variety of addressing modes.

Addressing Form Address Example Added
Modes Cost

Absolute M M MOV R1, 1

(location) M

Register R R 0

Indexed address a(R) contents(a + contents(R)) LD R1, 1

(a is a variable) a(R2)

Integer Indexed 100(R) contents(100+contents(R)) LD R1, 1

(100 is a memory location) 100(R2)

Dept. of CSE, MEC 2021-2022

Unit-V Subject: Compiler Design

Indirect Register *R contents(R) 0

Indirect Indexed *100(R) contents(contents(100+contnets(R))) LD R1, 1

*100(R2)

Constant/Literal #100 100 MOV #5, 1

R0

Various Address used for three address code are

• Static Allocation
– A statically determined area Code that holds the executable target code.
The size of the target code can be determined at compile time.
– A statically determined data area Static for holding global constants
and other data generated by the compiler. The size of the global
constants and compiler data can also be determined at compile time.
• Stack Allocation
– A dynamically managed area Stack for holding activation records as
they are created and destroyed during procedure calls and returns
• Dynamic Allocation
– A dynamically managed area Heap for holding data objects that are
allocated and freed during program execution
Some of the examples of three address codes for statements:

Dept. of CSE, MEC 2021-2022

Unit-V Subject: Compiler Design

BASIC BLOCKS AND FLOW GRAPHS:

Basic block is a sequence of consecutive statements in which flow of control enters

at the beginning of the block and leaves at the end without halt or possibility of
branching.

The characteristics of basic blocks are-

• They do not contain any kind of jump statements in them.
• There is no possibility of branching or getting halt in the middle.
• All the statements execute in the same order they appear.
• They do not lose the flow control of the program.

Example: t1 = a * 5
t2 = t1 + 7
t3 = t2 – 5
t4 = t1+ t3
t5 = t2 + b
So, the intermediate code is portioned into basic blocks. Each basic blocks become
the nodes of a flow graph.

Partitioning Algorithm:
Any given program can be partitioned into blocks using the following two steps

Step-1: First determine the leader statements

Rules for finding leaders
• The first three-address instruction in the intermediate code is a leader.

Dept. of CSE, MEC 2021-2022

Unit-V Subject: Compiler Design

• Any instruction that is the target of a conditional or unconditional jump (goto)

is a leader.
• Any instruction that immediately follows a conditional or unconditional
jump(goto) is a leader.

Step-2: Basic block is formed starting at the leader and ends just before the next
leader statement.
Example:

• Intermediate code to set a 10*10 matrix to an identity matrix.

As per partition algorithm

• 1 is a leader by default.
• 9, 11, and 17 are jump statements, their targets are 3, 2, 13. so 3, 2, 13 are
leaders.
• 10, 12 are statements that follow jumps.
Leaders: 1, 2, 3, 10, 12, and 13.

Dept. of CSE, MEC 2021-2022

Unit-V Subject: Compiler Design

Blocks: Each block contains statements from the leader to just before the next leader.
• Usually, we add Entry and Exit blocks also.
Block1: 1st statement
Block2: 2nd statement
Block3: statements from 3 to 9
Block4: statements 10, 11
Block5: 12th statement
Block6: 13th statement

Dept. of CSE, MEC 2021-2022

Unit-V Subject: Compiler Design

FLOW GRAPH:
Once an intermediate-code program is partitioned into basic blocks, we represent
the flow of control between them by a flow graph.
• A flow graph is a directed graph in which the flow control information is added
to the basic blocks.
• The nodes of the flow graph are the basic blocks.
There is an edge from block B to block C if the first instruction in block C immediately
follow the last instruction in block B.
Example for Glow Graph:

Compute the basic blocks for the given three address statements and draw flow
graph
(1) PROD = 0
(2) I = 1
(3) T2 = addr(A) – 4
(4) T4 = addr(B) – 4
(5) T1 = 4 x I
(6) T3 = T2[T1]
(7) T5 = T4[T1]
(8) T6 = T3 x T5
(9) PROD = PROD + T6
(10) I = I + 1
(11) IF I <=20 GOTO (5)

Solution-
● PROD = 0 is a leader since first statement of the code is a leader.
● T1 = 4 x I is a leader since target of the conditional goto statement is a leader.

OPTIMIZATION OF BASIC BLOCKS:

There are generally two phases of optimization:

Global Optimization: Transformations are applied to large program segments that
includes functions, procedures, and loops.
• Machine independent optimization is called as global optimization

Local Optimization: Transformations are applied to small blocks of statements. The

local optimization is done prior to global optimization.
• Peephole optimization is the best example for local optimization.
Peephole Optimization: Optimizing the target code of a block.
A simple but effective technique for locally improving the target code is peephole

Dept. of CSE, MEC 2021-2022

Unit-V Subject: Compiler Design

optimization, which is done by examining a sliding window of target instructions

(called the peephole).
Characteristic of peephole optimizations
• Redundant-instruction elimination
o Eliminating Redundant Loads and Stores
o Eliminating Unreachable Code
• Flow-of-control optimizations
o unnecessary jumps can be eliminated

goto L1

...

Ll: goto L2

Can be replaced by:

goto L2

...

Ll: goto L2
o
• Algebraic simplifications and reduction in strength
o x = x + 0, x = x * 1, x2 <=> x * x,
• Use of machine idioms
o Autoincrement and Autodecrement

REGISTER ALLOCATION AND ASSIGNMENT:

Efficient allocation of register is important for generating good code. There are four
strategies for deciding what values in a program should reside in a register and
which register each value should reside.
1. Global Register Allocation
2. Usage Counts
3. Register Assignment for Outer Loops
4. Register Allocation by Graph Coloring
1. Global Register Allocation:
Simple code generation algorithm does local (block based) register allocation. This
resulted that all live variables be stored at the end of block. To save some of these
stores and their corresponding loads, we might arrange to assign registers to
frequently used variables and keep these registers consistent across block boundaries
(globally)
• Frequently used variables are stored in fixed registers.
• So, assign some fixed registers to hold most active variables in each inner
loop.

Dept. of CSE, MEC 2021-2022

Unit-V Subject: Compiler Design

• Some options are:

– Keep values of variables used in loops inside registers
– Use graph coloring approach for more globally allocation
2. Usage Counts:
We can save some cost by keeping a variable x in register for the duration of loop L
For the loops we can approximate the saving by register allocation as:
• Sum over all blocks (B) in a loop (L)
• For each use of x before any definition in the block we add one unit of saving
• If x is live on exit from B and is assigned a value in B, then we add 2 units of
saving
Usage cost of x:
∑ blocks B in L use(x, B) + 2 * live(z, B)
use(x,B): number of time x is used in B prior to any definition of x in B.
live(x,B): equals to 1, if x is live on exit of B and assigned a value.
Otherwise equals to 0.

3. Register Allocation for Outer Loops:

If an outer loop L1 contains an inner loop L2, the names allocated registers in L2
need not be allocated registers in L1 - L2.

if we choose to allocate x a register in L2 but not L1, we must load x on entrance to

L2 and store x on exit from L2.
4. Register allocation by Graph Coloring:
If all the registers are occupied/in use, if we want a register to store a new variable,
one of the register content is to be stored into memory location (spilling). Register
allocation by Graph coloring is a simple and systematic technique for register
allocation and management.
It is a two-pass method:
1st pass: Target machine instructions are selected with an assumption that there
are infinite number of symbolic registers are available
• Names used in three address code become names of symbolic registers
• Three address instructions become machine language instructions
• Once the instruction is selected, 2nd pass assigns physical registers to
symbolic registers
2 pass: For each procedure, a register-inference graph is constructed, in which
nd

nodes are symbolic registers, and an edge connects two nodes if one is live at the
point where the second is defined.

MACHINE-INDEPENDENT OPTIMIZATIONS:

Code Optimization is an approach to enhance the performance of the code. The code
optimization in the synthesis phase is a program transformation technique, which tries
to improve the intermediate code by making it consume fewer resources (i.e., CPU,
Memory, registers) so that faster-running machine code is generated. Code optimizing
process should meet the following objectives :

Dept. of CSE, MEC 2021-2022

Unit-V Subject: Compiler Design

• The optimization must be correct, it must not, in any way, change the
meaning of the program.
• Optimization should increase the speed and performance of the program.
• The compilation time must be kept reasonable.
• The optimization process should not delay the overall compiling process.

The process of code optimization involves-

• Eliminating the unwanted code lines
• Rearranging the statements of the code
Advantages-
The optimized code has the following advantages-
• Optimized code has faster execution speed.
• Optimized code utilizes the memory efficiently.
• Optimized code gives better performance.

THE PRINCIPAL SOURCES OF OPTIMIZATIONS:

1. Compile Time Evaluation
2. Common sub-expression elimination
3. Dead Code Elimination
4. Code Movement
5. Strength Reduction

1. Compile Time Evaluation-

Two techniques that falls under compile time evaluation are-

A) Constant Folding-
It involves folding the constants.
The expressions that contain the operands having constant values at compile time
are evaluated. Those expressions are then replaced with their respective results.
Example-
Circumference of Circle = (22/7) x Diameter
Here,
• This technique evaluates the expression 22/7 at compile time.
• The expression is then replaced with its result 3.14.
• This saves the time at run time.

B) Constant Propagation-
In this technique,

Dept. of CSE, MEC 2021-2022

Unit-V Subject: Compiler Design

• If some variable has been assigned some constant value, then it replaces that
variable with its constant value in the further program during compilation.
• The condition is that the value of variable must not get alter in between.
Example-
pi = 3.14
radius = 10
Area of circle = pi x radius x radius
Here,

• This technique substitutes the value of variables ‘pi’ and ‘radius’ at compile
time.
• It then evaluates the expression 3.14 x 10 x 10.
• The expression is then replaced with its result 314.
• This saves the time at run time.
2. Common Sub-Expression Elimination-

The expression that has been already computed before and appears again in the
code for computation is called as Common Sub-Expression.
1. It involves eliminating the common sub expressions.
2. The redundant expressions are eliminated to avoid their re-computation.
3. The already computed result is used in the further program when required.
Example-
Code Before Optimization Code After Optimization
S1 = 4 x i S1 = 4 x i
S2 = a[S1] S2 = a[S1]
S3 = 4 x j S3 = 4 x j
S4 = 4 x i // Redundant Expression S5 = n
S5 = n S6 = b[S1] + S5
S6 = b[S4] + S5

3. Code Movement-
It involves movement of the code.
• The code present inside the loop is moved out if it does not matter whether it
is present inside or outside.
• Such a code unnecessarily gets execute again and again with each iteration of
the loop.
• This leads to the wastage of time at run time.
Example-
Code Before Optimization Code After Optimization
for ( int j = 0 ; j < n ; j ++) x=y+z;
{ for ( int j = 0 ; j < n ; j ++)
x=y+z; {
a[j] = 6 x j; a[j] = 6 x j;
} }

Dept. of CSE, MEC 2021-2022

Unit-V Subject: Compiler Design

4. Dead Code Elimination-

It involves eliminating the dead code.
• The statements of the code which either never executes or are unreachable or
their output is never used are eliminated.
Example-
Code Before Optimization Code After Optimization
i=0; i=0;
if (i == 1)
{
a=x+5;
}

5. Strength Reduction-
It involves reducing the strength of expressions.
• This technique replaces the expensive and costly operators with the simple
and cheaper ones.
Example-
Code Before Optimization Code After Optimization
B=Ax2 B=A+A

Here,
• The expression “A x 2” is replaced with the expression “A + A”.
• This is because the cost of multiplication operator is higher than that of
addition operator.

INTRODUCTION TO DATA-FLOW ANALYSIS

Data flow analysis refers to a body of techniques that derive information about the
flow of data along program execution paths.

Analysis that determines the information regarding definition and use of data in
program. It is useful in global optimization of code.

Each execution of an intermediate-code statement transforms an input state to a new

output state. The input state is associated with the program point before the
statement and the output state is associated with the program point after the
statement.

Basic Terminology:
• Definition Point: place/line in which a variable is defined.
• Reference Point: place/line in which a variable is referred.
• Evaluation Point: place/line in which operations (arithmetic) is performed.

Dept. of CSE, MEC 2021-2022

Unit-V Subject: Compiler Design

Data Flow Properties:

Available Expression: An expression ‘a+b’ is said to be available at a program point
‘x’, if none of its operands gets modified before their use.
• It is used to eliminate common sub expressions.
Ex:
B1 L1 = 4 ∗ 𝑖

B2 y=x+L
1
p = L1 * 3 B3

Here 4 * i is available in B2 and B3

Reaching Definition: A definition D is reaching to a point x if D is not killed or

redefined before that point.
• It is used in constant/variable propagation.
Ex:

D1:x = 4 D2: x = 𝑥 ∗ 2 D3: y = 𝑥 + 2

B1 B2 B3

D1 is a reaching definition to B2 not for B3

D2 is a reaching definition to B3

Dept. of CSE, MEC 2021-2022