CD Notes

Introduction to Code Generation in Compiler Design

Comprehensive introduction to the code generation phase of compilation covering objectives, challenges, target code forms, and the interface between intermediate representation and machine code.

What is Code Generation?

Code generation is the final phase of a compiler that transforms the intermediate representation (IR) into target machine code. This phase bridges the gap between the platform-independent optimized IR and the specific instruction set of the target processor. It is arguably the most complex phase because it must produce correct, efficient code that fully utilizes the target machine's capabilities.

Position in Compiler Pipeline

Example

Source → Lexer → Parser → Semantic → IR Gen → Optimizer → Code Gen → Target Code Analysis Code Front End Middle End Back End (language-dependent) (independent) (machine-dependent) Code Generator receives: - Optimized intermediate code (three-address code, SSA, etc.) - Symbol table information - Target machine specification Code Generator produces: - Assembly language, or - Relocatable machine code, or - Absolute machine code

Objectives of Code Generation

Correctness: Generated code must preserve the meaning of the source program
Efficiency: Use minimal instructions, registers, and memory
Speed: Code generation itself should be fast (compilation time)
Register utilization: Maximize use of fast registers over slow memory

Target Code Forms

Form 1	Absolute Machine Code
Example	0x89 0x45 0xFC (mov [ebp-4], eax)
Form 2	Relocatable Machine Code
Example	MOV [_counter], EAX (address of _counter TBD)
Form 3	Assembly Language
Example	mov eax, [ebp+8]

Issues in Code Generation

Instruction Selection

Choosing the right instructions for each IR operation:

Example

Three-address code: x = y + z Possible translations (x86): Option 1 (memory-to-memory): MOV eax, [y] ADD eax, [z] MOV [x], eax Option 2 (if y already in register R1): ADD R1, [z] MOV [x], R1 Option 3 (if x = x + 1, use increment): INC [x] The code generator must pick the most efficient option.

Register Allocation

Problem	IR assumes unlimited temporaries, but CPUs have limited registers.
After t1 = a+b	t1 is live
After t2 = c+d	t1, t2 are live
After t3 = t1*t2	t1, t3 are live (t2 dead)
After t4 = t1-t2	Wait - t2 needed again? No, t1 used for t4
Actually	t1 live from def to last use (line 3,4)
Max simultaneous live	t1, t2, t3 = 3 registers needed

Instruction Ordering

Example

Reordering can improve pipeline utilization: Original order: Reordered: LOAD R1, [a] LOAD R1, [a] ADD R1, R1, [b] ← stall LOAD R2, [c] ← no stall LOAD R2, [c] ADD R1, R1, [b] ← data ready ADD R2, R2, [d] ← stall ADD R2, R2, [d] ← data ready MUL R3, R1, R2 MUL R3, R1, R2 Pipeline stalls eliminated by interleaving independent operations.

Simple Code Generation Algorithm

Algorithm	For each three-address instruction x = y op z:
Register Descriptor	tracks what each register currently holds
Address Descriptor	tracks where each variable's value is (register/memory/both)
Code	t1 = a - b
Step 1	t1 = a - b
Register	{R0: t1}
Address	{t1: R0}
Step 2	t2 = a + c
Register	{R0: t1, R1: t2}
Address	{t1: R0, t2: R1}
Step 3	t3 = t1 * t2
Register	{R0: t3, R1: t2}
Address	{t3: R0}

Basic Blocks and Flow Graphs

Basic Block	maximal sequence of instructions with:
L	┐
[B1] ──true──	[B2]
└──false──	[B3]

Code Generation from DAGs

Example

DAG for: a = b + c; d = a - e; f = a + e; [=f] [=d] | | [+] [-] / \ / \ [=a] [e] [=a] [e] | | [+] [+] ← Same node (common subexpression) / \ / \ [b] [c] [b] [c] Optimized DAG (shared): [=f] [=d] | | [+] [-] / \ / \ [=a] [e] | [+] / \ [b] [c] Code from DAG: R0 = b + c ; compute [=a] store a, R0 R1 = R0 - e ; compute [=d] store d, R1 R1 = R0 + e ; compute [=f], reuse R0 for a store f, R1

Peephole Optimization in Code Generation

Example

After initial code generation, a peephole pass improves local patterns: Before: After: MOV R0, R1 (eliminated - redundant) MOV R1, R0 MOV R0, [x] MOV R0, [x] MOV [x], R0 (second instruction eliminated) ADD R0, 0 (eliminated - no effect) MUL R0, 2 SHL R0, 1 (shift is faster) JMP L1 JMP L2 (jump chain simplified) L1: JMP L2

Code Generator Architecture

┌─────────────────────────────────────────────────────────┐ │ Code Generator │ │ │ │ ┌──────────┐ ┌──────────┐ ┌──────────┐ ┌────────┐│ │ │Instruction│ │ Register │ │Instruction│ │Peephole││ │ │ Selection │→│Allocation│→│ Scheduling│→│ Opt. ││ │ └──────────┘ └──────────┘ └──────────┘ └────────┘│ │ ↑ │ │ │ │ Target Machine Description ↓ │ │ ┌─────────┐ ┌─────────┐ │ │ │ IR │ │ Target │ │ │ │ Input │ │ Code │ │ │ └─────────┘ └─────────┘ │ └─────────────────────────────────────────────────────────┘

Interview Questions

Q: What is the difference between code generation and code optimization?

A: Code optimization transforms IR to better IR (platform-independent improvements like CSE, dead code elimination). Code generation translates IR to target machine code (platform-specific decisions like instruction selection, register allocation). Optimization precedes generation, though some optimizations (peephole) happen during/after generation.

Q: Why is register allocation NP-complete?

A: Optimal register allocation reduces to graph coloring — assign k colors (registers) to nodes (variables) such that no two simultaneously live variables share a color. Graph k-coloring is NP-complete for k ≥ 3. Compilers use heuristics (linear scan, graph coloring with spilling) for practical solutions.

Q: What information does a code generator need from earlier phases?

A: The symbol table (variable types, sizes, scopes, offsets), the IR (three-address code or SSA form), type information (for selecting appropriate machine instructions — integer vs floating-point), and liveness information (which variables are live at each point, for register allocation).

Q: How does a code generator handle function calls?

A: It follows the target platform's calling convention: push arguments (registers or stack per ABI), save caller-saved registers, emit CALL instruction, handle return value (usually in specific register like EAX/R0), restore registers. The activation record layout determines stack frame setup.

Q: What is the advantage of generating assembly vs machine code directly?

A: Assembly is human-readable and debuggable, allows use of assembler features (macros, pseudo-ops), handles instruction encoding details, and supports relocatable output. Direct machine code generation is faster (no assembler pass) and used in JIT compilers where compilation speed is critical.

Exam Focus

Revise definitions, diagrams, examples, and short-answer points for Introduction to Code Generation in Compiler Design.

Interview Use

Prepare one clear explanation, one practical example, and one common mistake for this Compiler Design topic.

Search Terms

compiler-design, compiler design, compiler, design, code, generation, introduction, introduction to code generation in compiler design

Continue learning this concept

Code GenerationCode Generator Design in Compiler ConstructionDetailed exploration of code generator design principles including target machine models, instruction costs, addressing modes, and the systematic approach to building effective code generators.Code GenerationInstruction Selection in Code GenerationDetailed guide to instruction selection techniques including tree pattern matching, dynamic programming, BURS, and practical approaches to choosing optimal machine instructions for intermediate code.Code GenerationMachine Code Generation in CompilersGuide to machine code generation covering binary encoding, instruction formats, addressing mode encoding, relocation, and the final translation from assembly to executable machine code.Code GenerationRegister Allocation in Compiler DesignComplete guide to register allocation covering liveness analysis, interference graphs, graph coloring, linear scan allocation, spilling strategies, and practical implementation approaches.Code GenerationRegister Assignment Strategies in Code GenerationDetailed exploration of register assignment techniques including local and global assignment, usage counts, register pairs, and hardware-specific constraints in compiler code generation.Code GenerationTarget Machine Architecture for Code GenerationUnderstanding target machine architectures for compiler code generation including RISC vs CISC, instruction sets, memory hierarchy, pipelining, and how architecture features influence code generation.

PreviousStorage Organization: Memory Sections and Layout NextCode Generator Design in Compiler Construction

CD Notes

Introduction to Code Generation in Compiler Design

Comprehensive introduction to the code generation phase of compilation covering objectives, challenges, target code forms, and the interface between intermediate representation and machine code.

What is Code Generation?

Position in Compiler Pipeline

Example

Objectives of Code Generation

Correctness: Generated code must preserve the meaning of the source program
Efficiency: Use minimal instructions, registers, and memory
Speed: Code generation itself should be fast (compilation time)
Register utilization: Maximize use of fast registers over slow memory

Target Code Forms

Form 1	Absolute Machine Code
Example	0x89 0x45 0xFC (mov [ebp-4], eax)
Form 2	Relocatable Machine Code
Example	MOV [_counter], EAX (address of _counter TBD)
Form 3	Assembly Language
Example	mov eax, [ebp+8]

Issues in Code Generation

Instruction Selection

Choosing the right instructions for each IR operation:

Example

Register Allocation

Problem	IR assumes unlimited temporaries, but CPUs have limited registers.
After t1 = a+b	t1 is live
After t2 = c+d	t1, t2 are live
After t3 = t1*t2	t1, t3 are live (t2 dead)
After t4 = t1-t2	Wait - t2 needed again? No, t1 used for t4
Actually	t1 live from def to last use (line 3,4)
Max simultaneous live	t1, t2, t3 = 3 registers needed

Instruction Ordering

Example

Simple Code Generation Algorithm

Algorithm	For each three-address instruction x = y op z:
Register Descriptor	tracks what each register currently holds
Address Descriptor	tracks where each variable's value is (register/memory/both)
Code	t1 = a - b
Step 1	t1 = a - b
Register	{R0: t1}
Address	{t1: R0}
Step 2	t2 = a + c
Register	{R0: t1, R1: t2}
Address	{t1: R0, t2: R1}
Step 3	t3 = t1 * t2
Register	{R0: t3, R1: t2}
Address	{t3: R0}

Basic Blocks and Flow Graphs

Basic Block	maximal sequence of instructions with:
L	┐
[B1] ──true──	[B2]
└──false──	[B3]

Code Generation from DAGs

Example

Peephole Optimization in Code Generation

Example

Code Generator Architecture

Interview Questions

Q: What is the difference between code generation and code optimization?

Q: Why is register allocation NP-complete?

Q: What information does a code generator need from earlier phases?

Q: How does a code generator handle function calls?

Q: What is the advantage of generating assembly vs machine code directly?

Exam Focus

Revise definitions, diagrams, examples, and short-answer points for Introduction to Code Generation in Compiler Design.

Interview Use

Prepare one clear explanation, one practical example, and one common mistake for this Compiler Design topic.

Search Terms

compiler-design, compiler design, compiler, design, code, generation, introduction, introduction to code generation in compiler design

Continue learning this concept

PreviousStorage Organization: Memory Sections and Layout NextCode Generator Design in Compiler Construction