CD Notes
Complete guide to dead code elimination covering unreachable code, useless computations, liveness analysis, and aggressive dead code elimination techniques in compiler optimization.
What is Dead Code?
Dead code refers to program statements whose results are never used or code that can never be reached during execution. Eliminating dead code reduces program size, improves cache utilization, and can speed up other optimizations. There are two main categories: unreachable code (cannot be executed) and useless code (executes but results are never needed).
Types of Dead Code
1. Unreachable Code (control-flow dead):
if (false) {
x = compute(); // never executes
}
return result;
y = x + 1; // after return, never reached
2. Useless Code (data-flow dead):
x = a + b; // computed but never used
y = c * d; // y is also never read
z = x + y; // only z matters... but if z unused too?
3. Dead stores:
x = 5; // first store
x = 10; // overwrites before any read → first store is dead
4. Redundant operations:
x = x + 0; // no effect
y = y * 1; // no effectAlgorithm: Simple Dead Code Elimination
Algorithm (backward pass)
1. Mark all critical instructions as "live"
(I/O, function calls with side effects, stores to volatiles, returns)
2. For each live instruction I:
Mark all instructions that define operands of I as "live"
3. Repeat until no new instructions marked
4. Remove all unmarked instructions
Example
1: a = read() ← LIVE (I/O side effect)
2: b = a + 1 ← check if used...
3: c = b * 2 ← check if used...
4: d = a - 3 ← check if used...
5: print(c) ← LIVE (I/O side effect)
6: e = d + c ← NOT USED → DEAD
Backward marking from live instructions
print(c) uses c → mark line 3 live
c = b*2 uses b → mark line 2 live
b = a+1 uses a → mark line 1 live (already live)
Line 4 (d = a-3): d used only in line 6, which is dead → line 4 DEAD
Line 6 (e = d+c): e never used → DEAD
After DCE
1: a = read()
2: b = a + 1
3: c = b * 2
5: print(c)
Unreachable Code Elimination
Algorithm
1. Build control flow graph
2. Find all blocks reachable from entry (DFS/BFS)
3. Delete unreachable blocks
Example
┌─────┐
┌───│Entry │───┐
│ └─────┘ │
↓ ↓
┌─────┐ ┌─────┐
│ B1 │ │ B2 │
└──┬──┘ └──┬──┘
│ │
↓ ↓
┌─────┐ ┌─────┐
│ B3 │ │ B4 │ ← no edges lead here!
└──┬──┘ └─────┘ (unreachable)
↓
┌─────┐
│Exit │
└─────┘
After removing unreachable B4 and verifying all paths
B4 deleted, saving code space and analysis time.
Common sources of unreachable code
- Debug code guarded by constant flags
- Template/generic instantiation artifacts
- After constant propagation eliminates branches
- After inlining reveals dead paths
Dead Store Elimination
Aggressive Dead Code Elimination (Aggressive DCE)
DCE and Control Flow
| Before | After DCE: |
| // temp not used after loop | entire loop body is dead! |
| // Actually if i not used either | entire loop is dead! |
Dead Code in Practice
Sources of dead code in real programs
1. Defensive programming:
if (DEBUG) { log_state(); } // DEBUG=false → dead
2. Library code:
#include <algorithm> // includes many unused templates
3. After inlining:
inline int max(int a, int b) { return a>b ? a : b; }
x = max(5, 3); // after inline + fold: x = 5
// the comparison code is dead
4. Partial specialization:
template<bool flag> void process() {
if (flag) { ... } // dead when flag=false
else { ... } // dead when flag=true
}
5. After other optimizations:
Original: x = a + b; y = x * 2; z = y + 1; return z;
After inlining caller only uses return value directly
Intermediate dead assignments may appear and be eliminated.
Implementation Considerations
Interview Questions
- Q: Why can't we simply remove all unused variable assignments?
A: Because the right-hand side may have side effects. A function call might perform I/O, modify global state, or throw exceptions. A memory read might be volatile. The compiler must prove the entire instruction has no observable effect before removing it, not just that the result is unused.
- Q: How does dead code elimination interact with debugging?
A: At -O0, no DCE is performed so debuggers can inspect all variables. With optimization, DCE removes variables and their assignments, making debugging harder — "optimized out" messages. Some compilers emit debug info mapping removed variables to their last known values.
- Q: Can dead code elimination improve other optimizations?
A: Yes! Removing dead code reduces the CFG size, simplifies dataflow analysis, reduces register pressure (fewer live variables), and can expose new optimization opportunities (e.g., a loop becomes empty after DCE and can be removed entirely).
- Q: What is the difference between dead code elimination and unreachable code elimination?
A: DCE removes code that executes but whose results are never used (data-flow dead). Unreachable code elimination removes code that can never execute (control-flow dead). Both reduce code size, but they use different analyses: DCE uses liveness/def-use analysis; unreachable code elimination uses reachability in the CFG.
- Q: How does aggressive DCE differ from standard DCE?
A: Standard DCE scans forward marking results as "used" or "unused." Aggressive DCE works backward from known-essential (critical) instructions, marking only what's needed. Aggressive DCE handles chains of dead code in one pass and naturally handles the case where a long chain of computations feeds into nothing — it simply never marks any of them live.
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for Dead Code Elimination in Compiler Optimization.
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, optimization, dead, elimination
Related Compiler Design Topics