Code Generation and Optimization

Code Generation and Optimization

Code Generation produces target code from intermediate representation.

Code Generation

Code Generator: Converts intermediate code to target code.

Tasks:

• Instruction selection
• Register allocation
• Instruction scheduling

Register Allocation

Purpose: Assign variables to registers.

Problem: Limited registers, many variables.

Strategies:

• Simple Strategy: Keep variables in memory
• Register Allocation: Assign to registers
• Spilling: Move to memory when needed

Graph Coloring:

• Variables as nodes
• Interference graph
• Color with minimum registers

Code Optimization

Purpose: Improve code efficiency.

Local Optimization

Within basic blocks:

• Constant folding
• Common subexpression elimination
• Dead code elimination

Global Optimization

Across basic blocks:

• Loop optimization
• Constant propagation
• Copy propagation

Loop Optimization

Techniques:

• Loop Invariant Code Motion: Move invariant code outside loop
• Induction Variable Elimination: Simplify loop variables
• Loop Unrolling: Reduce loop overhead

Basic Blocks

Basic Block: Sequence of statements with single entry and exit.

Properties:

• No branches except at end
• No labels except at start

Leader: First statement of basic block.

Partitioning:

• Start of program
• Target of jump
• Statement after jump

Control Flow Graph

CFG: Graph representation of control flow.

Nodes: Basic blocks

Edges: Control flow

Use: Global optimization

GATE CS Important Points

1. Code Generation: Three-address to target code
2. Register Allocation: Graph coloring
3. Optimization: Local and global
4. Basic Blocks: Identification
5. Loop Optimization: Techniques

Practice Tips

1. Code Generation: Generate code for expressions
2. Register Allocation: Assign registers
3. Optimization: Apply optimization techniques
4. Basic Blocks: Identify and partition
5. Previous Year Questions: Solve GATE code generation questions