COMPILER DESIGN

Code Optimization & Code Generation

Part 1: CODE OPTIMIZATION

1. Organization of Code Optimizer

A code optimizer sits between the intermediate code generator and the final code generator. Its role is
to improve the intermediate code so that faster or smaller target code results.

Structure of Code Optimizer

The code optimizer is organized into several phases, each responsible for a specific kind of
improvement:

Phase Name Purpose

1 Control Flow Analysis Determines flow of control between basic
blocks
2 Data Flow Analysis Collects information about data values
computed at each point
3 Transformation Uses analysis info to improve code (eliminate
redundancies)
4 Peephole Optimization Local, window-based micro-optimizations on
final code

📝 Key Point: Machine-independent optimizations operate on intermediate code; machine-

dependent optimizations work on target code.

2. Basic Blocks and Flow Graphs

What is a Basic Block?

A basic block is a maximal sequence of consecutive three-address statements with no jumps into or out
of the middle of the block.
 • Execution always starts at the first statement (entry)
• Execution always ends at the last statement (exit) without halting or branching except at end
• Control enters at the beginning and leaves at the end

Algorithm: Identifying Basic Blocks

Step 1 — Find all leaders (first statements of basic blocks):
◦ The first statement of the program is a leader
◦ Any statement that is a target of a conditional or unconditional GOTO is a leader
◦ Any statement immediately following a GOTO or conditional GOTO is a leader

Step 2 — Each basic block consists of a leader and all statements up to, but not including, the next
leader.

✏️ Example — Identifying Basic Blocks:

1: t1 = a * a
2: t2 = a * b
3: t3 = 2 * t2
4: t4 = t1 + t3
5: t5 = b * b
6: t6 = t4 + t5
7: if t6 > 100 goto 10
8: x = 0
9: goto 11
10: x = 1
11: return x

Leaders: 1 (first stmt), 10 (target of goto 10), 8 (follows conditional),

11 (target of goto 11)
Block B1: statements 1-7
Block B2: statements 8-9
Block B3: statement 10
Block B4: statement 11

Flow Graph
A flow graph is a directed graph where:
• Nodes = basic blocks
• Edges = flow of control between blocks
• An edge B1 → B2 exists if B2 can follow B1 (via GOTO or fall-through)
• A special ENTRY node has an edge to the first block
• A special EXIT node receives edges from all blocks that end with return

📝 Key Point: Flow graphs form the foundation for all global optimizations and data flow
analysis.
3. Optimization of Basic Blocks
Several transformations can be applied locally within a single basic block:

a) Common Subexpression Elimination (CSE)

If the same expression is computed more than once, and operands haven't changed in between,
eliminate the redundant computation.

✏️ Example — Common Subexpression Elimination:

BEFORE: AFTER:
t1 = a + b t1 = a + b
t2 = a + b (redundant!) t2 = t1 (reuse t1)
t3 = t1 * t2 t3 = t1 * t1

b) Dead Code Elimination

Remove code that computes values that are never used. A variable is 'dead' if it is not used after its
definition.

✏️ Example — Dead Code Elimination:

BEFORE: AFTER:
x = 5 x = 5
y = x + 2 (y never used) (line removed — y is dead)
return x return x

c) Constant Folding
Evaluate constant expressions at compile time rather than runtime.

✏️ Example — Constant Folding:

BEFORE: AFTER:
x = 3 * 4 x = 12 (computed at compile time)
y = x + 2 y = 14

d) Copy Propagation
After an assignment x = y, replace uses of x with y where possible, allowing dead code elimination.

✏️ Example — Copy Propagation:

BEFORE: AFTER:
x = y x = y
z = x + 1 z = y + 1 (x replaced by y)
e) Algebraic Simplification
Simplify algebraic expressions using mathematical identities.

✏️ Example — Algebraic Simplification:

x = y + 0 → x = y
x = y * 1 → x = y
x = y * 0 → x = 0
x = y ** 2 → x = y * y (avoid expensive power function)

f) Strength Reduction
Replace expensive operations with cheaper equivalents.

✏️ Example — Strength Reduction:

x = y * 2 → x = y + y (or left shift: x = y << 1)
x = y * 8 → x = y << 3 (multiply replaced by shift)
x = y / 2 → x = y >> 1 (divide replaced by shift)

4. Principal Sources of Optimization

Opportunities for optimization arise from several key sources:

a) Loop Optimizations
Loops are critical because they execute repeatedly. Main techniques:

• Code Motion (Loop Invariant Removal)

◦ Move computations that don't change inside the loop to outside
◦ Condition: the expression must be loop-invariant (operands not modified in loop)

✏️ Example — Code Motion:

BEFORE: AFTER (Hoisted):
for i = 1 to n { t = limit - 2 ← moved OUT of loop
x = i + limit - 2 } for i = 1 to n {
x = i + t }

limit-2 is loop-invariant, so it is computed only once!

 • Induction Variable Elimination
◦ Detect induction variables (variables that change by constant amounts in each iteration)
◦ Replace expensive multiplications with simpler additions

✏️ Example — Induction Variable Elimination:

BEFORE: AFTER:
for i = 0 to n { t4 = 4 * 0 (initial)
t1 = 4 * i for i = 0 to n {
t2 = a[t1] } t2 = a[t4]
t4 = t4 + 4 ← add 4 instead of multiply
}

t4 is an induction variable; 4*i is replaced by t4+4 (cheaper)

• Loop Unrolling
◦ Replicate loop body multiple times to reduce loop overhead
◦ Reduces number of loop condition checks and branch instructions

b) Global Common Subexpression Elimination

Extends CSE beyond single basic blocks. If an expression is computed in one block and not modified
before reaching another block, the result can be reused.

✏️ Example — Global CSE:

Block B1: t1 = a + b
Block B2: t2 = a + b ← a and b not changed between B1 and B2

Optimization: In B2, replace t2 = a + b with t2 = t1

c) Copy Propagation (Global)

Propagate copy assignments (x=y) across block boundaries. Enables further dead code elimination.

d) Constant Propagation (Global)

If a variable is always a constant when it reaches a certain point, replace uses with the constant value.

5. DAG Representation of Basic Blocks

A Directed Acyclic Graph (DAG) is a compact representation of a basic block that reveals opportunities
for optimization.
Rules for Constructing DAG
• Each variable or constant that first appears as an operand gets a leaf node
• Each three-address statement creates an interior node labeled with the operator
• Children of an interior node are the operands
• If the same computation already exists as a node, reuse it (this detects common
subexpressions)
• Each node carries the list of variable names that currently hold that value

✏️ Example — DAG Construction:

Given basic block: DAG Construction:
t1 = a + b Node N1: leaf(a), Node N2: leaf(b)
t2 = a - c Node N3: +(N1, N2) → t1
t3 = t1 + t2 Node N4: leaf(c)
t4 = a + b (same as t1!) Node N5: -(N1, N4) → t2
Node N6: +(N3, N5) → t3

t4 = a+b is ALREADY computed as N3! So t4 gets attached to N3.

No new node is created → Common Subexpression detected!

Advantages of DAG
• Automatically detects common subexpressions
• Identifies dead code (nodes with no labels are results that aren't used)
• Enables efficient code regeneration by listing nodes in topological order
• Determines which variables are live (used) at exit of the block

📝 Key Point: DAG is the primary tool for local (basic block level) optimizations in a
compiler.

6. Global Data Flow Analysis

Global data flow analysis collects information about the flow of data through the entire program (across
all basic blocks). This is essential for global optimizations.

a) Reaching Definitions
Definition An assignment such as d: x = y + z is a definition of variable x at point
d.

Reaches Definition d reaches point p if there is a path from d to p and x is NOT

redefined along any path.
Data Flow Equations:

OUT[B] = GEN[B] ∪ (IN[B] - KILL[B])

GEN[B] = definitions generated in block B (not subsequently killed in B)

KILL[B] = all definitions of x in other blocks if B contains a definition of x
IN[B] = ∪ OUT[P] for all predecessors P of B

✏️ Example — Reaching Definitions:

Block B1: d1: x = 5
Block B2: d2: x = 10 (kills d1)
Block B3: uses x

Only d2 reaches B3 because d1 is killed by d2 in B2.

So at B3, x is always 10 — enables Constant Propagation!

b) Live Variable Analysis

Live Variable A variable x is live at point p if there is a path from p to a use of x, and
x is not redefined along that path.

Data Flow Equations (backward analysis):

IN[B] = USE[B] ∪ (OUT[B] - DEF[B])

USE[B] = variables used in B before any definition in B

DEF[B] = variables defined in B (before any use in B)
OUT[B] = ∪ IN[S] for all successors S of B

📝 Key Point: Live variable analysis helps identify dead code — if a variable is not live after
its definition, the definition can be removed.

c) Available Expressions
Available Expression x+y is available at point p if every path from ENTRY to p
evaluates x+y and neither x nor y is redefined after the evaluation.

Data Flow Equations (forward analysis):

OUT[B] = AVAIL_GEN[B] ∪ (IN[B] - AVAIL_KILL[B])

AVAIL_GEN[B] = expressions computed in B whose operands aren't redefined in B

AVAIL_KILL[B] = expressions that use any variable defined in B
IN[B] = ∩ OUT[P] for all predecessors P of B (intersection, not union!)

Analysis Type Direction

Reaching Definitions Forward (Entry → Exit)
Live Variables Backward (Exit → Entry)
Available Expressions Forward (Entry → Exit)
Very Busy Expressions Backward (Exit → Entry)
Part 2: CODE GENERATION

7. Machine Dependent Code Generation

Machine-dependent code generation is the phase that translates intermediate code (three-address
code) into machine code (or assembly) for the target architecture.

Key Challenges
• Efficient register allocation — deciding which values to keep in registers
• Instruction selection — mapping intermediate operations to target machine instructions
• Instruction ordering — choosing the order of instructions for best performance
• Handling memory hierarchy — registers, cache, main memory

8. Object Code Forms

A code generator can produce several forms of object code:

Form Description Use Case

Absolute Machine Code Ready to run at fixed memory Small embedded systems
addresses
Relocatable Machine Code Code with relocation info; loaded Most compiled programs
at any address by linker
Assembly Language Human-readable mnemonic form; Debugging, porting
needs assembler
Intermediate (Bytecode) Abstract machine instructions Interpreted or JIT-compiled
(e.g., JVM bytecode)

9. The Target Machine

The target machine model defines the architecture for which code is generated. A typical model (used
in textbooks) includes:

Register Architecture
• n general-purpose registers: R0, R1, ..., Rn-1
• Special registers: Program Counter (PC), Stack Pointer (SP)
• Operations: Load, Store, Arithmetic, Logical, Conditional Jump
Addressing Modes
Mode Notation Meaning
Immediate #c Constant c
Register Ri Value in register Ri
Direct (Absolute) M Contents of memory location M
Register Indirect *Ri Memory location whose address is in Ri
Indexed c(Ri) Memory at address c + value of Ri

Instruction Costs
Each instruction has an associated cost. Typically:
• Cost of instruction = 1 + cost of each operand
• Register operand cost = 0 (no extra memory access)
• Memory operand cost = 1 (extra memory fetch)
• Constant operand cost = 1

✏️ Example — Instruction Cost:

MOV R0, R1 → cost = 1 + 0 + 0 = 1 (reg to reg)
MOV R0, M → cost = 1 + 0 + 1 = 2 (memory to reg)
MOV R0, *R1 → cost = 1 + 0 + 1 = 2 (indirect)
ADD R0, #5 → cost = 1 + 0 + 1 = 2 (immediate)

10. A Simple Code Generator

A simple code generator translates three-address instructions one by one, making decisions about
register allocation on-the-fly.

Key Data Structures

• Register Descriptor — tracks what variable(s) each register currently holds
• Address Descriptor — tracks all locations (registers + memory) where each variable's current
value can be found

getreg() Function
The getreg() function decides which register to use for a given instruction. Strategy:
◦ Use a register already holding the needed value
◦ Use an empty register
◦ Spill (store to memory) the least useful register and reuse it
Code Generation for Three-Address Statements
For each statement of the form x = y op z:

1. Call getreg() to get register Ry for y

(If y is in a register already, use that register)

2. If y is not in Ry, emit: MOV Ry, y'

(where y' is a memory location for y)

3. If op is binary (x = y op z):
- Get register Rz for z (or use memory location of z)
- Emit: OP Ry, z' (result goes into Ry)

4. Update register descriptor: Ry now holds x

5. Update address descriptor: x is now in Ry
6. If y or z have no other uses after this point, free their registers

✏️ Example — Code Generation for d = (a-b) + (a-c):

Three-address code: Generated Assembly:

t1 = a - b MOV R0, a
t2 = a - c SUB R0, b ; R0 = a - b (= t1)
t3 = t1 + t2 MOV R1, a
d = t3 SUB R1, c ; R1 = a - c (= t2)
ADD R0, R1 ; R0 = t1 + t2 (= t3)
MOV d, R0 ; store result to d

Total instructions: 5 | Registers used: R0, R1

11. Peephole Optimization

Peephole optimization examines a small sliding window (the 'peephole') of generated code and
replaces instruction sequences with shorter or faster equivalents.

📝 Key Point: Peephole optimization is machine-dependent and applied to the final

generated code. It is simple but highly effective.

Common Peephole Transformations

a) Redundant Load/Store Elimination

If a value is stored to memory and then immediately loaded back, the load is redundant.
 ✏️ Example:
BEFORE: AFTER:
MOV R0, x MOV R0, x
MOV x, R0 ← redundant! (eliminated — R0 already has x's value)

b) Unreachable Code Elimination

Code that follows an unconditional jump and has no label is unreachable and can be deleted.

✏️ Example:
BEFORE: AFTER:
GOTO L GOTO L
x = 5 ← unreachable! (eliminated)
L: ... L: ...

c) Flow of Control Optimizations

Simplify unnecessary jumps:

✏️ Example — Jump to Jump:

BEFORE: AFTER:
GOTO L1 GOTO L2 (direct jump)
...
L1: GOTO L2

✏️ Example — Conditional Jump to Unconditional Jump:

BEFORE: AFTER:
IF t GOTO L1 IF NOT t GOTO L2
GOTO L2 L1: ...
L1: ...

d) Algebraic Simplification (Peephole)

Remove instructions that are mathematically trivial:

✏️ Example:
ADD R0, #0 → (removed — adding 0 does nothing)
MUL R0, #1 → (removed — multiplying by 1 does nothing)
MUL R0, #2 → SHL R0, #1 (shift left is faster than multiply)

e) Use of Machine Idioms

Replace general instruction sequences with special machine instructions:

✏️ Example:
BEFORE: AFTER:
MOV R0, 0 CLR R0 (dedicated clear instruction, faster)
ADD R0, #1 INC R0 (dedicated increment instruction)

f) Strength Reduction in Peephole

✏️ Example:
MUL R0, #4 → SHL R0, #2 (shift 2 = multiply by 4, much faster)
MUL R0, #8 → SHL R0, #3 (shift 3 = multiply by 8)
DIV R0, #2 → SHR R0, #1 (right shift = divide by 2)

Quick Summary Table — All Topics

Topic Key Concept Main Benefit

Code Optimizer Organization Analysis + Transformation Structured improvement pipeline
phases
Basic Blocks Leader-based maximal Unit of local analysis
sequences

Flow Graphs Directed graph of blocks Foundation for global analysis

CSE Elimination Reuse already-computed values Fewer computations

Dead Code Elim Remove unused computations Smaller, faster code

Constant Folding Evaluate constants at compile Eliminates runtime arithmetic

time

Loop Optimization Hoist invariants, use induction Huge speedup in loops

vars

DAG Graph of basic block Detects CSE, dead code locally

computations
Reaching Definitions Forward data flow analysis Constant/copy propagation

Live Variables Backward data flow analysis Dead code elimination

Available Exprs Forward + intersection Global CSE

Target Machine Register + addressing model Guides code generation

Object Code Forms Absolute/relocatable/assembly Flexibility of output

Simple Code Generator Reg/addr descriptors + getreg() Efficient register use

Peephole Optimization Window-based local replacement Final code cleanup

— END OF NOTES —