GATE CS - COMPILER DESIGN:Code Generation and Optimization
Mastering code generation and optimization concepts and implementation.
Code Generation and Optimization for GATE CS
GATE rarely asks you to emit x86. It asks for three-address code, basic-block ideas, and whether an optimization is safe / local.
From IR to code
Input: three-address statements or quadruples. Output: machine-ish instructions with registers. Issues: instruction selection, register allocation, ordering.
Basic blocks and flow graph
A basic block is a maximal straight-line sequence: one entry, one exit (no internal jumps). Partition IR at leaders (first statement, jump targets, fall-through after jumps). Connect blocks into a flow graph.
Local optimizations GATE names
| Opt | Idea |
|---|---|
| Constant folding | \(2+3 \to 5\) at compile time |
| Constant propagation | Replace uses of a known constant |
| Copy propagation | \(x=y\) then use \(y\) |
| Dead code elimination | Remove unused computations |
| Common subexpression elimination | Reuse prior \(t = a+b\) |
| Strength reduction | \(x*2 \to x<<1\) when valid |
Algebraic identities and machine-dependent opts appear as one-liners in options.
Register allocation (exam level)
More temporaries than registers ⇒ spill to memory. Graph coloring is the classic model; GATE may only ask “spill” vocabulary.