IT603(A) • Compiler Design • Unit V

Code Optimization and Generation

Complete RGPV exam-oriented notes covering optimizer organization, basic blocks, control-flow graphs, DAG representation, loops, peephole optimization and local block optimization.

Start Unit 5 Notes
Home › Compiler Design › Unit 5

1. Code Optimization 14 Marks

Code optimization is the compiler phase that transforms intermediate code into an equivalent form that executes faster, uses less memory or consumes fewer resources without changing the program's meaning.

Basic Principle

An optimization must preserve the observable behavior of the source program. The optimized program should produce the same result for every valid input.

Position in Compiler

Intermediate Code | v +------------------+ | Code Optimizer | +------------------+ | Optimized Intermediate Code | v Target Code Generator

Main Objectives

  • Reduce execution time.
  • Reduce code size.
  • Reduce memory accesses.
  • Improve register utilization.
  • Remove unnecessary computations.
  • Reduce power and processor-resource usage.

Characteristics of a Good Optimizer

  • Preserves program meaning.
  • Produces measurable improvement.
  • Does not excessively increase compilation time.
  • Works for a broad class of programs.
  • Uses safe and predictable transformations.

Example

Before: t1 = 2 * 3 t2 = a + 0 t3 = t1 + t2 After: t3 = 6 + a

Constant folding and algebraic simplification remove unnecessary instructions.

Types of Optimization

  • Machine-independent optimization
  • Machine-dependent optimization
  • Local optimization
  • Global optimization
  • Loop optimization
  • Peephole optimization
Conclusion: Code optimization improves program efficiency while preserving correctness and is a major responsibility of the compiler back end.

2. Organization of Code Optimizer 14 Marks

The organization of a code optimizer describes how optimization analyses and transformations are arranged between intermediate-code generation and target-code generation.

General Organization

Source Program | Front End | Intermediate Code | +-------------------------------+ | Machine-Independent Optimizer | +-------------------------------+ | Optimized Intermediate Code | Code Generator | +-----------------------------+ | Machine-Dependent Optimizer | +-----------------------------+ | Target Program

Machine-Independent Optimization

These transformations do not depend on target-machine instructions.

  • Constant folding
  • Common subexpression elimination
  • Dead-code elimination
  • Copy propagation
  • Loop-invariant code motion
  • Strength reduction

Machine-Dependent Optimization

These transformations use details of the target architecture.

  • Register allocation
  • Instruction selection
  • Instruction scheduling
  • Use of special machine instructions
  • Peephole improvement of target code

Optimizer Components

  • Control-flow analyzer: constructs basic blocks and flow graphs.
  • Data-flow analyzer: computes reaching definitions, liveness and available expressions.
  • Transformation engine: applies safe optimizations.
  • Cost estimator: estimates whether transformation is beneficial.

Optimization Levels

LevelAreaExample
LocalOne basic blockConstant folding
GlobalMultiple blocks in one procedureGlobal common subexpression elimination
LoopLoop body and controlLoop-invariant code motion
InterproceduralMultiple proceduresInlining

3. Optimization Criteria and Safety 14 Marks

Correctness Requirement

The optimizer must not change program semantics. It must preserve values, control flow, side effects and exception behavior where required by the language.

Profitability

A valid transformation is not always profitable. The compiler estimates whether it reduces execution cost or code size.

Cost Measures

  • Number of instructions
  • Number of memory accesses
  • Loop execution frequency
  • Branch cost
  • Register pressure
  • Code-size increase

Conservative Optimization

If the compiler cannot prove that a transformation is safe, it should normally avoid that transformation.

Important: Optimization should improve efficiency without changing the output, input behavior or required side effects of the program.

4. Principal Sources of Optimization 14 Marks

1. Common Subexpression Elimination

Before: t1 = a * b t2 = a * b + c After: t1 = a * b t2 = t1 + c

2. Constant Folding

Before: x = 4 * 5 After: x = 20

3. Constant Propagation

Before: a = 10 b = a + 5 After: a = 10 b = 15

4. Copy Propagation

Before: x = y z = x + 1 After: x = y z = y + 1

5. Dead-Code Elimination

x = 5 x = 8 The first assignment is dead if x is not used between them.

6. Algebraic Simplification

x + 0 → x x * 1 → x x * 0 → 0 x - x → 0

7. Strength Reduction

x * 2 → x + x i * 4 inside loop → incremental address update

8. Code Motion

A computation whose result does not change within a loop can be moved outside the loop.

5. Basic Blocks 14 Marks

A basic block is a maximal sequence of consecutive instructions with one entry point and one exit point.

Properties

  • Control enters only at the first instruction.
  • Control leaves only at the last instruction.
  • There is no branch into the middle.
  • There is no branch out except at the end.
  • All instructions execute sequentially once the block is entered.

Example

1. t1 = a + b 2. t2 = t1 * c 3. if t2 > d goto 6 4. x = t2 - d 5. goto 7 6. x = d - t2 7. y = x + 1

Possible basic blocks:

B1: Instructions 1, 2, 3 B2: Instructions 4, 5 B3: Instruction 6 B4: Instruction 7

Importance

  • Foundation for local optimization.
  • Nodes of a control-flow graph.
  • Useful for liveness analysis.
  • Useful for instruction scheduling.
  • Defines regions of straight-line code.

6. Identifying Leaders and Constructing Basic Blocks 14 Marks

A leader is the first instruction of a basic block.

Rules for Identifying Leaders

  1. The first instruction is a leader.
  2. The target of a conditional or unconditional jump is a leader.
  3. The instruction immediately following a jump is a leader.

Construction Algorithm

  1. Mark all leaders using the above rules.
  2. For each leader, form a block containing that leader and all following instructions up to, but not including, the next leader.
  3. The last block continues to the end of the program.

Example

1. i = 1 2. sum = 0 3. if i > 10 goto 8 4. t1 = 4 * i 5. sum = sum + t1 6. i = i + 1 7. goto 3 8. result = sum

Leaders

  • Instruction 1: first instruction
  • Instruction 3: jump target of instruction 7
  • Instruction 4: follows conditional jump at instruction 3
  • Instruction 8: jump target and follows instruction 7
B1: 1, 2 B2: 3 B3: 4, 5, 6, 7 B4: 8

7. Flow Graphs 14 Marks

A flow graph is a directed graph in which nodes represent basic blocks and edges represent possible transfers of control.

Edge Rules

An edge B1 → B2 exists if:

  • There is a jump from the last instruction of B1 to the first instruction of B2.
  • B2 immediately follows B1 and B1 does not end with an unconditional jump.

Example Flow Graph

+------+ | B1 | +------+ | v +------+ +----| B2 |----+ | +------+ | false | true | | v | | +------+ | | | B3 |----+ | +------+ | | +-------v +------+ | B4 | +------+

Predecessor and Successor

  • Successor: a block that may execute immediately after the current block.
  • Predecessor: a block that may execute immediately before the current block.

Uses

  • Detect loops.
  • Perform global data-flow analysis.
  • Find unreachable code.
  • Determine execution paths.
  • Support global optimization.

8. DAG Representation of Basic Blocks 14 Marks

A directed acyclic graph for a basic block represents computations and dependencies while allowing identical subexpressions to share nodes.

DAG Nodes

  • Leaves represent initial values of identifiers and constants.
  • Interior nodes represent operators.
  • Labels on nodes represent variables holding the computed value.

Example

1. t1 = a + b 2. t2 = a + b 3. x = t1 * c 4. y = t2 * c

DAG representation shares both common computations:

* / \ + c / \ a b Labels: + node → t1, t2 * node → x, y

Uses of DAG

  • Find common subexpressions.
  • Detect dead assignments.
  • Determine value dependencies.
  • Reorder independent computations.
  • Generate efficient code for a basic block.

Advantages

  • Compact representation.
  • Natural local optimization structure.
  • Avoids repeated computation.
  • Supports algebraic transformations.

9. Construction of DAG for a Basic Block 14 Marks

Algorithm

  1. Create a leaf for every initial identifier or constant.
  2. For instruction x = y op z, locate nodes for y and z.
  3. If an existing node has the same operator and children, reuse it.
  4. Otherwise create a new operator node.
  5. Attach x as a label to the result node.
  6. Remove x from any previously labeled node.

Unary and Copy Statements

x = op y Create or reuse unary node op(y). x = y Attach label x to the node representing y.

Dead-Code Detection

If a root node's value is not live at the end of the block and has no required side effect, the corresponding computation may be eliminated.

Example

a = b + c d = b + c e = a + d

The DAG uses one node for b+c, labeled a and d. The final addition uses the same node twice.

10. Local Optimization 14 Marks

Local optimization applies transformations within a single basic block.

Local Techniques

  • Local common subexpression elimination
  • Constant folding
  • Constant propagation
  • Copy propagation
  • Dead-code elimination
  • Algebraic simplification
  • Strength reduction

Example

Before: t1 = a + b t2 = a + b t3 = t2 * 1 x = t3 + 0 After: t1 = a + b x = t1

Advantages

  • Simple and fast analysis.
  • No complex global information required.
  • Effective for straight-line code.
  • Easy to combine with DAG representation.

Limitation

Local optimization cannot exploit information across basic-block boundaries.

11. Loops in Flow Graph 14 Marks

A loop in a flow graph is a set of basic blocks that may execute repeatedly and normally has a distinguished entry block called the loop header.

Dominators

A node d dominates node n if every path from the entry node to n passes through d.

Back Edge

An edge n → d is a back edge if d dominates n.

Natural Loop

The natural loop of a back edge n → d contains d, n and all nodes that can reach n without passing through d.

Example

B1 | v B2 <---------+ | | v | B3 | | | v | B4 ----------+ Back edge: B4 → B2 Loop header: B2 Natural loop: {B2, B3, B4}

Why Loops Are Important

  • Loop bodies execute many times.
  • Small improvements give large runtime benefits.
  • Most execution time is often spent in loops.

12. Loop Optimization 14 Marks

1. Loop-Invariant Code Motion

Move computations outside the loop if their operands do not change inside the loop.

Before: for (...) { t = a * b; x[i] = t + i; } After: t = a * b; for (...) { x[i] = t + i; }

2. Strength Reduction

Replace expensive operations with cheaper operations.

Before: address = base + i * 4 After: address = address + 4 per iteration

3. Induction Variable Elimination

Remove redundant variables that change by a fixed amount each iteration.

4. Loop Unrolling

Duplicate loop body to reduce branch overhead.

Before: for(i=0; i<4; i++) a[i] = 0; Unrolled: a[0]=0; a[1]=0; a[2]=0; a[3]=0;

5. Loop Fusion

Combine adjacent loops having compatible ranges.

6. Loop Interchange

Exchange nested-loop order to improve memory locality.

Safety Conditions

  • Preserve data dependencies.
  • Preserve side effects.
  • Do not move computations that may cause exceptions incorrectly.

13. Peephole Optimization 14 Marks

Peephole optimization examines a small sliding window of consecutive target or intermediate instructions and replaces inefficient patterns with better ones.

Working

Instruction Sequence | Small Window (Peephole) | Pattern Matching | Equivalent Better Sequence

Common Peephole Transformations

1. Redundant Instruction Elimination

MOV R1, R1 → remove

2. Flow-of-Control Optimization

JMP L1 L1: JMP L2 Replace with: JMP L2

3. Algebraic Simplification

ADD R1, 0 → remove MUL R1, 1 → remove

4. Strength Reduction

MUL R1, 2 may become SHIFT_LEFT R1, 1

5. Use of Machine Idioms

x = x + 1 may become INC x

6. Unreachable Code Elimination

Instructions after an unconditional jump and before the next reachable label may be removed.

Advantages

  • Simple implementation.
  • Low analysis cost.
  • Improves target code.
  • Can use machine-specific instruction patterns.

Limitations

  • Limited to a small instruction window.
  • Cannot perform broad global transformations.
  • Repeated passes may be needed.

14. Basic Block Optimization 14 Marks

Basic block optimization improves straight-line code within a basic block using local analysis and transformation.

Steps

  1. Construct the basic block.
  2. Build a DAG or value representation.
  3. Identify common subexpressions.
  4. Propagate constants and copies.
  5. Remove dead assignments.
  6. Apply algebraic simplification.
  7. Generate an efficient instruction order.

Example

Original: a = b + c d = b + c e = d * 2 f = e + 0 a = 10 Optimized: d = b + c e = d + d f = e a = 10

Transformations

  • Common subexpression elimination
  • Dead-code elimination
  • Reordering independent statements
  • Use of cheaper operators
  • Temporary-variable reduction

Benefits

  • Fewer instructions.
  • Reduced temporary storage.
  • Better register use.
  • Faster execution.

15. Basic Data-Flow Concepts 14 Marks

Data-flow analysis collects information about how values and definitions move through a control-flow graph.

Reaching Definitions

A definition reaches a point if there is a path from the definition to that point without another definition of the same variable.

Live Variable

A variable is live at a point if its current value may be used along some path before being redefined.

Available Expression

An expression is available at a point if it has already been computed on every path and none of its operands have changed.

Uses

AnalysisMain Use
Reaching definitionsConstant propagation and use-definition chains
Live variablesRegister allocation and dead-code elimination
Available expressionsCommon subexpression elimination
Very busy expressionsCode motion

IN and OUT Sets

Data-flow equations commonly compute information entering and leaving each basic block.

IN[B] = information entering block B OUT[B] = information leaving block B

16. Basics of Code Generation 14 Marks

Code generation is the compiler phase that converts intermediate code into target assembly or machine instructions.

Inputs

  • Intermediate representation
  • Symbol-table information
  • Target-machine description

Main Issues

  • Instruction selection
  • Register allocation and assignment
  • Order of evaluation
  • Use of addressing modes
  • Storage management
  • Instruction scheduling

Simple Example

Three-address code: t1 = a + b x = t1 Possible target code: MOV R0, a ADD R0, b MOV x, R0

Register Allocation

Register allocation decides which values should remain in limited processor registers. Register assignment chooses the actual register.

Desirable Properties

  • Correct target code
  • Efficient instruction sequence
  • Good register use
  • Fast code-generation process

17. Important Comparisons 14 Marks

Local vs Global Optimization

FeatureLocalGlobal
ScopeOne basic blockMultiple basic blocks
Analysis costLowHigher
Information requiredLocal statementsControl and data flow
ExampleConstant foldingGlobal dead-code elimination

Machine-Independent vs Machine-Dependent Optimization

FeatureMachine IndependentMachine Dependent
Target detailsNot requiredRequired
Applied toIntermediate codeTarget code or low-level IR
ExamplesCommon subexpression eliminationRegister allocation, instruction scheduling

Basic Block vs Flow Graph

Basic BlockFlow Graph
Straight-line instruction sequenceGraph of basic blocks
One entry and one exitRepresents possible control transfers
Used for local optimizationUsed for global optimization

Unit 5 Quick Revision

  • Optimization improves code without changing meaning.
  • Machine-independent optimization works on intermediate code.
  • A basic block has one entry and one exit.
  • Leaders identify starting instructions of basic blocks.
  • A flow graph represents control flow among blocks.
  • A DAG shares common expressions inside a block.
  • Back edges help identify natural loops.
  • Loop optimization gives major performance benefits.
  • Peephole optimization examines a small instruction window.
  • Data-flow analysis supports global optimization.
  • Code generation performs instruction selection and register allocation.

Important RGPV Exam Questions

Long Answer Questions

  1. Define code optimization and explain its objectives and classifications.
  2. Explain the organization of a code optimizer with a neat diagram.
  3. Discuss principal sources of code optimization with examples.
  4. Define a basic block and explain the algorithm for constructing basic blocks.
  5. Explain flow graphs with a suitable example.
  6. Explain DAG representation of a basic block.
  7. Construct a DAG for a given basic block and explain its uses.
  8. Explain local optimization techniques.
  9. Define dominators, back edges and natural loops.
  10. Explain loop optimization techniques with examples.
  11. Explain peephole optimization and its transformations.
  12. Explain basic block optimization using DAG.
  13. Explain reaching definitions, live variables and available expressions.
  14. Explain the basic issues in code generation.
  15. Compare machine-independent and machine-dependent optimization.

Short Answer Questions

  1. What is code optimization?
  2. Define basic block.
  3. What is a leader?
  4. Define control-flow graph.
  5. What is a DAG?
  6. Define common subexpression.
  7. What is dead code?
  8. Define loop-invariant computation.
  9. What is peephole optimization?
  10. Define live variable.
Exam Strategy: For basic-block questions, first mark leaders, form blocks and then draw the flow graph. For optimization questions, always show before-and-after code.

Download Study Resources

Unit 5 PDF

Printable detailed notes will be uploaded soon.

Coming Soon

Optimization Problems

Basic block and DAG practice will be available soon.

Coming Soon

PYQ Analysis

Repeated Unit 5 questions will be added soon.

Coming Soon

Frequently Asked Questions

Its purpose is to improve execution speed, memory usage or code size without changing program behavior.
It is a maximal straight-line sequence of instructions having one entry and one exit.
A DAG identifies common subexpressions, dependencies and dead computations and supports efficient local optimization.
An edge n to d is a back edge when d dominates n. Back edges are used to identify natural loops.
It is a local method that examines a small sequence of instructions and replaces inefficient patterns with equivalent better ones.