Scribd
Upload
9 views2 pages

Code Generation in Compiler Design

The document outlines the process of code generation in compiler design, detailing the translation of intermediate code into target machine code while addressing challenges like instruction selection and register allocation. It discusses the importance of the target language design, optimization techniques for basic blocks, and the typical code generation pipeline. Additionally, it provides practical tips for efficient instruction selection and optimization strategies.

Uploaded by

poppy.harshwal
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
9 views2 pages

Code Generation in Compiler Design

The document outlines the process of code generation in compiler design, detailing the translation of intermediate code into target machine code while addressing challenges like instruction selection and register allocation. It discusses the importance of the target language design, optimization techniques for basic blocks, and the typical code generation pipeline. Additionally, it provides practical tips for efficient instruction selection and optimization strategies.

Uploaded by

poppy.harshwal
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

CODE GENERATION – Compiler Design Notes

1. Overview – What a Code Generator Does

A code generator translates intermediate code (IR) into target machine code (assembly or
machine instructions). Its main goals are correctness, efficiency, and reasonable
compilation time. Challenges include instruction selection, register allocation, instruction
scheduling, and memory management.

2. The Target Language

Design of the target machine (RISC vs CISC) affects code generation. Important aspects
include instruction set, number of registers, addressing modes, and calling conventions.

3. Addresses in the Target Code

Addresses in target code can be absolute, relative, or computed using base and offset.
Local variables use stack-relative addresses, while globals may use absolute or
PC-relative addressing.

4. Basic Blocks and Flow Graphs

A Basic Block (BB) is a straight-line sequence of code with single entry and exit. A Control
Flow Graph (CFG) represents BBs as nodes and possible control transfers as edges.

5. Optimization of Basic Blocks

Local optimizations include constant folding, strength reduction, common subexpression


elimination, copy propagation, and dead code elimination.

6. A Simple Code Generator

A simple generator converts IR to machine code block-by-block, selecting instructions and


allocating registers. It emits the translated instructions after mapping temporaries to
machine registers.

7. Peephole Optimization

Peephole optimization scans small instruction windows to remove redundancies or replace


sequences with shorter ones. Examples: removing redundant LOAD/STORE pairs or
combining consecutive arithmetic operations.

8. Register Allocation and Assignment

Register allocation maps variables to machine registers. Techniques include graph


coloring (Chaitin's algorithm) and linear scan allocation. Spilling occurs when registers are
insufficient, storing values temporarily in memory.

9. Dynamic Programming Code Generation


Dynamic programming (DP) is used for optimal instruction selection on expression trees.
The Sethi–Ullman algorithm helps minimize register use during expression evaluation. DP
ensures minimal-cost instruction sequences by combining subproblem solutions.

10. Typical Code Generation Pipeline

1. Lower IR to simpler form


2. Build basic blocks and CFG
3. Perform local optimizations
4. Instruction selection
5. Register allocation
6. Spill/reload insertion
7. Peephole optimization
8. Assembly emission

11. Example: a = b + c * d

Intermediate representation: t1 = c * d; t2 = b + t1; a = t2.


Sethi–Ullman algorithm orders evaluation to minimize register usage, possibly computing
c*d first, then adding b.

12. Practical Tips

• Tree-based DP is effective for instruction selection.


• Use peephole optimizations last.
• Combine selection and allocation when possible.
• Use linear scan for fast compilation, graph coloring for optimized builds.

You might also like