Module – 5

Q.1. What are the properties of code generation phase? Also explain the
Design Issues of this phase.

Solution

The code generation phase (final compiler phase) translates intermediate

representation into target code (machine/assembly) while ensuring
semantic equivalence and efficiency. Key properties include correctness,
high-quality code generation (speed/size), and efficient register/memory
management. Key design issues are instruction selection, register
allocation/assignment, evaluation order, and memory management.

Properties of Code Generation Phase

 Correctness: The primary goal is that the generated code must
accurately represent the source program's logic and behavior.
 Efficiency: The code must be optimized for speed and size to
maximize execution performance on the target architecture.
 Target-Dependence: The phase is highly dependent on the target
machine's architecture, including instruction set, register count, and
addressing modes.
 Register Management: It maintains both address descriptors
(location of values) and register descriptors (contents of registers) to
minimize memory traffic.
 Input Handling: Operates on intermediate representations (three-
address code, syntax trees) and symbol tables.

Design Issues in Code Generation

 Instruction Selection: Choosing appropriate target machine
instructions to implement intermediate representation statements,
balancing speed and size.
 Register Allocation and Assignment: Deciding which variables reside
in fast CPU registers versus memory to reduce memory access.
 Evaluation Order: Determining the order of calculation for
expressions, which affects the efficiency of register usage.
 Memory Management: Mapping source program names (variables)
to memory addresses (e.g., stack or static).
 Target Program Format: Deciding whether to generate absolute
machine code (fast execution), relocatable code (for linking), or
assembly code.

The code generator should take the following things into consideration to
generate the code:
 Target language : The code generator has to be aware of the nature
of the target language for which the code is to be transformed. That
language may facilitate some machine-specific instructions to help
the compiler generate the code in a more convenient way. The target
machine can have either CISC or RISC processor architecture.
  IR Type : Intermediate representation has various forms. It can be in
Abstract Syntax Tree (AST) structure, Reverse Polish Notation, or 3-
address code.

 Selection of instruction : The code generator takes Intermediate

Representation as input and converts (maps) it into target machines
instruction set. One representation can have many ways
(instructions) to convert it, so it becomes the responsibility of the
code generator to choose the appropriate instructions wisely.

 Register allocation : A program has a number of values to be

maintained during the execution. The target machines architecture
may not allow all of the values to be kept in the CPU memory or
registers. Code generator decides what values to keep in the registers.
Also, it decides the registers to be used to keep these values.

 Ordering of instructions : At last, the code generator decides the

order in which the instruction will be executed. It creates schedules
for instructions to execute them.

Q.2. What are basic blocks? Write the algorithm for partitioning into
Blocks.

Solution

Basic blocks are maximal sequences of consecutive three-address code

instructions where control enters only at the beginning and leaves only at
the end without halts or branching. They act as nodes in a flow graph,
ensuring code executes sequentially. Partitioning involves identifying
"leaders" (start instructions) and grouping statements.

Algorithm for Partitioning into Basic Blocks

 Input: A sequence of three-address statements.
 Output: A list of basic blocks.

Method:
 Identify Leaders: Determine the set of leader statements based on the
following rules:
Rule 1: The first statement is a leader.
Rule 2: Any statement that is the target of a conditional or
unconditional goto is a leader.
Rule 3: Any statement that immediately follows a goto
statement is a leader.
 Construct Blocks: For each leader, construct a basic block that
consists of the leader statement and all subsequent statements up to,
but not including, the next leader or the end of the program.
Example:
1: x = 0 (Leader - Rule 1)
2: y = 1
3: if x < 10 goto 6 (Leader - Rule 2)
4: z = 5 (Leader - Rule 3, follows 3)
5: goto 3
6: print y (Leader - Rule 2, target of 3)
Blocks: B1: (1-2), B2: (3), B3: (4-5), B4: (6)

3. Write a short note on:

a. Flow graph (with example)
b. Dominators
c. Natural loops
d. Inner loops
e. Reducible flow graphs

Solution

a. Flow Graph
A flow graph is a directed graph where nodes represent basic blocks
(maximal sequences of instructions with one entry and one exit) and edges
represent the possible flow of control between them. It is used during code
generation and optimization to visualize program structure.

Example:
Consider the following three-address code:
i=1
if i <= 10 goto (4)
goto (6)
print i
i=i+1
exit
Blocks:
B1: Statements 1, 2
B2: Statement 3
B3: Statements 4, 5
B4: Statement 6
Graph Edges:
B1 → B3 (if condition is true)
B1 → B2 (if condition is false)
B3 → B1 (back to loop check)
B2 → B4 (exit)

A node dominates a node 𝑛 (written 𝑑 dom 𝑛) if every path from the

b. Dominators

initial entry node of the flow graph to 𝑛 must go through 𝑑 .

 Initial Node: Dominates every node in the graph.
 Reflexivity: Every node dominates itself.
  Dominator Tree: A tree where each node's parent is its immediate
dominator (the last dominator on the path from the entry node).

c. Natural Loops
A Natural Loop is a set of nodes in a flow graph that has a single entry

 Back Edge: An edge 𝑛→𝑑 where the head dominates the tail 𝑛.
point and at least one "back edge".

 Header: The node in the back edge 𝑛→𝑑 is the unique entry to the
loop.
 Structure: It consists of the header and all nodes that can reach the
tail without passing through the header.

d. Inner Loops
An Inner Loop is a natural loop that contains no other natural loops within
it.
 Nesting: Natural loops are either disjoint or nested. If one loop is
entirely contained in another, the smaller one is considered "inner".
 Importance: Compilers prioritize optimizing inner loops because
they often account for the majority of a program's execution time

e. Reducible Flow Graphs

A flow graph is reducible if its edges can be partitioned into two disjoint
sets: forward edges (forming an acyclic graph) and back edges (where the
head dominates the tail).
 Property: In a reducible graph, there are no jumps into the middle of
a loop from outside; all loops are entered only through their headers.
 Context: Programs written using structured control statements (like
if-then-else or while) always produce reducible flow graphs.

Q.4. Consider the following program code:

Prod=0;
I=1;
Do{
Prod=prod+a[i]*b[i];
I=i+1;
}while (i<=10);
a. Partition in into blocks
b. Construct the flow graph

Solution

The program is partitioned into three basic blocks: initialization (𝐵1), the

where 𝐵1 flows into 𝐵2 , 𝐵2 loops back to itself, and 𝐵2 flows

loop body (𝐵2), and exit (𝐵3). The flow graph consists of these blocks,

to 𝐵3 when the condition is false.

a. Partition into Basic Blocks

To partition the code into basic blocks, we first identify the leaders (first
statement of a block):
1. First statement is a leader.
2. Target of a goto is a leader.
3. Statement immediately following a goto is a leader.

 (1) 𝑳𝟏: 𝑷𝒓𝒐𝒅=𝟎 (Leader)

Three-Address Code with Leaders:

 (2) 𝐼=1
 (3) 𝑳𝟐 : 𝑻𝟏 =𝒂 [𝒊] (Leader: Loop header)
 (4) 𝑇2 =𝑏 [𝑖]
 (5) 𝑇3 =𝑇1 *𝑇2
 (6) 𝑇4 =𝑃𝑟𝑜𝑑 +𝑇3
 (7) 𝑃𝑟𝑜𝑑 =𝑇4
 (8) 𝐼 =𝑖 +1
 (9) If 𝒊 ≤𝟏𝟎 goto 𝑳𝟐
 (10) 𝑳 : ... (Leader: Loop exit)

𝑩𝟏 (Initial):
Basic Blocks:

Prod = 0

 𝑩𝟐 (Loop Body):
I=1

T1 = a[i]
T2 = b[i]
T3 = T1 * T2
Prod = T4
I=i+1

 𝑩𝟑
If i <= 10 goto B2

(Exit): (Exit statement)

b. Flow Graph

 𝑩𝟏→𝑩 : Initial control flow.

The flow graph connects the basic blocks based on the program flow.

 𝑩𝟐→𝑩 : Loop back (if 𝑖 ≤10 ).

 𝑩𝟐→𝑩 : Loop exit (if 𝑖 >10).

graph TD
B1[B1: Initial] --> B2[B2: Loop Body]
B2 -->|If i <= 10 | B2
B2 -->|If i > 10 | B3[B3: Exit]

[Link] is code optimization? Explain machine dependent and

independent code optimization.

Solution
Code optimization is a compiler design phase that enhances intermediate or
target code to make software faster, smaller, or more resource-efficient
without altering its original functionality. It is broadly divided into
machine-independent optimization (improving algorithm efficiency
regardless of hardware) and machine-dependent optimization (exploiting
specific CPU/hardware features).

1. Machine-Independent Code Optimization

This phase improves intermediate code to produce more efficient target
code without considering the specific CPU architecture. It focus on high-
level logical improvements.

 Target: Intermediate Code.

 Features: Portable, applies to any machine.
 Techniques:
o Constant Folding/Propagation: Evaluating expressions with
constant operands at compile-time (e.g., x = 2 * 3 becomes x =
6).
o Loop Optimization: Moving code outside loops that doesn't
change (Code Motion) or reducing strength of operators inside
loops.
o Dead Code Elimination: Removing code that is never executed
or has no effect on the program result.

2. Machine-Dependent Code Optimization

This phase is applied to the generated target code (machine code) to take
advantage of specific hardware features to maximize performance.

 Target: Object/Assembly Code.

 Features: Non-portable, tailored for specific hardware (e.g., x86,
ARM).
 Techniques:
o Register Allocation: Deciding which variables or expressions
should live in high-speed CPU registers to minimize slow
memory access.
o Instruction Scheduling: Reordering instructions to avoid
pipeline stalls or to take advantage of specialized instructions
(e.g., using LEA vs ADD on Intel).
o Address Optimization: Using absolute memory references or
specialized addressing modes to speed up memory access.

Differences

Feature Machine Independent Machine Dependent

Applied to Intermediate Code Object/Target Code

Hardware Independent (Portable) Specific Architecture

Focus Algorithm/Logical structure Register/Memory usage

Complexity Easier to implement Complex,hardware-pecific

Q.6. What is common sub-expression and how to eliminate it? Explain with
example.

Solution

Common sub-expression elimination (CSE) is a compiler optimization

technique that identifies identical expressions that evaluate to the same
value and replaces them with a single variable holding that computed
value.
By calculating the expression only once, the program avoids redundant
computations, leading to faster execution and more efficient use of CPU
and memory resources.

How to Eliminate Common Sub-expressions

Elimination follows a straightforward principle of reuse:

1. Identification: The compiler (or programmer) searches for instances

2. Analysis: It verifies that the operands involved (e.g., variables 𝑎

where the exact same mathematical or logical operation is repeated.

and 𝑏) have not changed between the first and subsequent

occurrences.
3. Transformation: The value of the first instance is assigned to a
temporary variable. All later instances of the same expression are
then replaced by that variable.

Example
Consider the following original code snippet where the expression b * c is
computed twice:

Original Code:
a=b*c+g
d=b*c*e

After Common Sub-expression Elimination: Instead of calculating b *

c twice, we store it in a temporary variable (tmp) and reuse it
tmp = b * c
a = tmp + g
d = tmp * e

Types of Common Sub-expression Elimination (CSE)

 Local CSE: Occurs within a single "basic block" (a sequence of code
without any jumps or branches).
  Global CSE: Performed across an entire procedure or multiple
blocks, which requires more complex "data-flow analysis" to ensure
the values of operands remain constant across different execution
paths.

Key Benefits and Trade-offs

 Improved Performance: Decreases execution time by reducing the
number of instructions the CPU must process.
 Resource Conservation: Conserves CPU cycles and can simplify the
code structure.
 Potential Drawback: Creating too many temporary variables can
increase "register pressure," potentially forcing the compiler to store
values in slower memory (RAM) instead of fast CPU registers.

Q.7. Write a short note with example to optimize the code:

a. Dead code elimination
b. Variable elimination
c. Code motion
d. Reduction in strength

Solution

Code optimization improves efficiency by reducing resource usage (CPU,

memory) without changing the program's output. Here is a breakdown of
common techniques:

a. Dead Code Elimination

This removes code that is either unreachable or does not affect the
program's final results. It keeps the executable lean and prevents
unnecessary processing.

Example:
# Before
def calculate(x):
result = x * 2
return result
print("Done") # This is dead code (unreachable)

# After
def calculate(x):
return x * 2

b. Variable Elimination

This reduces overhead by removing unnecessary or redundant variables,

often by replacing a variable with the expression it represents (copy
propagation) or combining intermediate steps.
Example:
 # Before
temp = a + b
final_score = temp + c

# After
final_score = a + b + c

c. Code Motion

Also known as "Loop-Invariant Code Motion," this involves moving

calculations that produce the same result regardless of how many times a
loop runs to a position outside the loop.
Example:
# Before
for i in range(len(list)):
x = [Link](144) # Stays the same every loop
print(list[i] * x)

# After
x = 12.0
for i in range(len(list)):
print(list[i] * x)

d. Reduction in Strength

This replaces expensive operations (like multiplication or division) with

cheaper ones (like addition or bit-shifting) to speed up execution time.
Example:
# Before (Expensive multiplication in a loop)
for i in range(10):
val = i * 2

# After (Cheaper addition)

val = 0
for i in range(10):
# val is incremented by 2 each time
val += 2

Q. 8. What is control and data flow analysis? Explain with example.

Solution

Control and data flow analysis are static analysis techniques used in
compiler design to optimize code and verify program behavior. Control
Flow Analysis (CFA) determines the order of statement execution (e.g.,
loops, branches), while Data Flow Analysis (DFA) tracks how variables are
defined, used, and modified across that flow, enabling optimizations like
dead code elimination.
 1. Control Flow Analysis (CFA)

CFA examines the structure of a program to build a Control Flow Graph

(CFG), showing how program execution jumps between blocks, loops, and
conditional branches.
 Purpose: Identify unreachable code, detect loops, and structure
program paths.
 Example: In an if-else statement, CFA identifies two distinct paths
originating from the condition check.

// Code
if (x > 0) {
y = 1; // Path 1
} else {
y = 2; // Path 2
}
print(y); // Merge point

CFA Result: A graph with nodes [if x>0] → [y=1] and [if x>0] → [y=2],
both merging at [print(y)].

2. Data Flow Analysis (DFA)

DFA gathers information about the possible set of values calculated at
various points in a program. It populates the CFG with information about
variables.
 Purpose: Register allocation, constant propagation, and eliminating
common sub expressions.
 Example: Reaching Definitions. Tracking where a variable's value
was last assigned.

1: x = 5;
2: y = x + 2;
3: x = 10;
4: z = x + y;

DFA Result:
 Before line 2, definition x=5 (line 1) is reaching.
 Before line 4, definition x=10 (line 3) is reaching (killing the
definition from line 1).