Compiler Design (MCA554) – Unit 5: Code Generation and Code Optimization

 
Based on MCA Semester III Syllabus 

---
Introduction to Code Generation
Code Generation is the final phase of a compiler.
Its purpose is to convert intermediate code into target machine code.
Compiler Flow:
Source Program
      ↓
Lexical Analysis
      ↓
Syntax Analysis
      ↓
Semantic Analysis
      ↓
Intermediate Code
      ↓
Code Generation
      ↓
Machine Code

---
Objectives of Code Generation
A good code generator should:
Produce correct code
Produce efficient code
Use memory efficiently
Reduce execution time


---
Inputs to Code Generator
The code generator receives:
Intermediate Code
Symbol Table
Runtime Information

Example:
t1 = a + b
t2 = t1 * c

---
Outputs of Code Generator
The output is machine code or assembly code.
Example:
MOV R1, a
ADD R1, b
MUL R1, c

---
Machine Dependent Code Generation
Machine-dependent code generation considers:
CPU architecture
Number of registers
Memory organization
Instruction set

Different processors generate different machine code.
Example:
Intel Processor
ARM Processor
RISC Processor

---
Object Code Forms
Object code can be generated in different forms.
Absolute Machine Code
Memory locations fixed.
Example:
1000: MOV A,B
1001: ADD A,C

---
Relocatable Machine Code
Addresses can be adjusted during loading.
Advantages:
Flexible
Easier linking


---
Assembly Language Code
Human-readable machine instructions.
Example:
MOV AX, BX
ADD AX, CX

---
Target Machine
Target Machine is the system on which generated code executes.
Examples:
Intel x86
ARM
MIPS

The compiler must understand the target machine architecture.

---
Simple Code Generator
Consider:
a = b + c
Intermediate Code:
t1 = b + c
a = t1
Generated Code:
MOV R1, b
ADD R1, c
MOV a, R1

---
Register Allocation
Registers are very fast memory locations inside CPU.
Example:
R1
R2
R3
Compiler must decide:
Which variable gets which register
When registers are reused


---
Importance of Register Allocation
Good register allocation:
Improves performance
Reduces memory access
Produces faster programs


---
Register Assignment
Assigning variables to available registers.
Example:
a → R1
b → R2
c → R3

---
Register Allocation Strategies
Local Allocation
Inside a basic block.

---
Global Allocation
Across the entire program.

---
Peephole Optimization
A simple optimization technique.
Compiler examines a small set of consecutive instructions and replaces inefficient code with efficient code.

---
Example 1: Redundant Instructions
Before:
MOV R1, A
MOV A, R1
After:
MOV R1, A

---
Example 2: Constant Folding
Before:
a = 10 + 20
After:
a = 30

---
Example 3: Strength Reduction
Before:
x = y * 2
After:
x = y + y

---
Advantages of Peephole Optimization
Faster execution
Smaller code size
Better efficiency


---
Code Optimization
Code Optimization improves program performance without changing output.
Objectives:
Reduce execution time
Reduce memory usage
Improve efficiency


---
Sources of Optimization
Common Subexpression Elimination
Before:
a = b + c
d = b + c
After:
t = b + c
a = t
d = t

---
Dead Code Elimination
Remove statements that never affect output.
Before:
x = 10
x = 20
print(x)
After:
x = 20
print(x)

---
Constant Folding
Before:
a = 5 * 4
After:
a = 20

---
Constant Propagation
Before:
x = 10
y = x + 5
After:
x = 10
y = 15

---
Basic Blocks
A Basic Block is a sequence of instructions with:
One entry point
One exit point

No jumps inside the block.
Example:
a = b + c
d = a + e
f = d + g
This forms one basic block.

---
Properties of Basic Blocks
Executed sequentially
No branching inside
Important for optimization


---
Flow Graph
A graphical representation of control flow between basic blocks.
Example:
B1
     / \
    ↓ ↓
   B2 B3
     \ /
      ↓
      B4
Where:
B1, B2, B3, B4
are Basic Blocks.

---
Advantages of Flow Graph
Visualizes program flow
Helps optimization
Helps data flow analysis


---
Directed Acyclic Graph (DAG)
A DAG is used to represent computations inside a basic block.
Properties:
No cycles
Eliminates redundant computations
Supports optimization


---
Example of DAG
Expression:
a = b + c
d = b + c
DAG:
+
     / \
    b c
   / \
  a d
Only one computation of:
b + c
is required.

---
Advantages of DAG
Removes duplicate computations
Saves memory
Improves execution speed


---
Global Data Flow Analysis
Studies how data moves through a program.
Purpose:
Optimization
Dead code elimination
Register allocation


---
Applications of Data Flow Analysis
Constant propagation
Reaching definitions
Live variable analysis
Dead code detection


---
Organization of Code Optimizer
Intermediate Code
       ↓
Code Optimizer
       ↓
Optimized Code
       ↓
Code Generator
       ↓
Target Code

---
Important Exam Questions
Short Questions
1. Define Code Generation.

2. What is Register Allocation?

3. Define Peephole Optimization.

4. What is a Basic Block?

5. What is a Flow Graph?

6. Define DAG.

7. What is Constant Folding?

8. What is Dead Code Elimination?



---
Long Questions
1. Explain Code Generation with examples.

2. Discuss Register Allocation and Assignment.

3. Explain Peephole Optimization techniques.

4. What are Basic Blocks? Explain with examples.

5. Explain Flow Graphs and their applications.

6. Discuss DAG representation of Basic Blocks.

7. Explain various Code Optimization techniques.



---
Quick Revision Notes
Code Generation = Intermediate Code → Machine Code
Register Allocation = Assign variables to CPU registers
Register Assignment = Map variables to registers
Peephole Optimization = Small code improvements
Constant Folding = Compute constants at compile time
Dead Code Elimination = Remove useless code
Basic Block = Single-entry, single-exit instruction sequence
Flow Graph = Graph of basic blocks
DAG = Removes redundant computations
Data Flow Analysis = Tracks data movement for optimization


---
Compiler Design (MCA554) Complete ✅
Units Covered
1. Introduction to Compiler & Lexical Analysis

2. Parsing and Syntax Analysis

3. Syntax Directed Translation & Intermediate Code

4. Type Checking & Runtime Environment

5. Code Generation & Code Optimization



x