Advanced Compiler Theory

Underneath specific named optimizations lies a body of general theory — control-flow and data-flow analysis — that determines what a compiler can even prove about a program, and therefore what transformations it can safely apply at all.

Advanced compiler theory covers the general analytical techniques compilers use to figure out facts about a program well enough to safely optimize it — like which variable definitions can reach which uses, which values are still needed later, and which parts of the program can even be reached at all.

A compiler can only safely apply an optimization if it can prove that optimization doesn't change the program's observable behavior — these underlying analyses are precisely how a compiler gathers enough certainty about a program's structure and behavior to make that guarantee, rather than just guessing.

Every optimization discussed in the previous section relies on one or more of these underlying analyses — dead-code elimination needs to know a value is truly unused (liveness analysis), constant propagation needs to know which definition of a variable reaches a given use (data-flow/reaching-definitions analysis), and so on.

Think of a building inspector checking whether a wall can be safely removed during a renovation. The inspector can't just guess — they need to trace exactly which parts of the building's structure depend on that wall (a kind of "reachability" and "dependency" analysis) before certifying it's safe to remove. A compiler's data-flow analyses play exactly that safety-certifying role before it removes or rearranges any code.

Liveness analysis, tracing backward from each use of x, determines that the initial x = 5 is never read before x is reassigned to 10 — its value is never "live" at any point it's actually used, so a compiler can safely eliminate that first, dead assignment entirely.

A Control Flow Graph (CFG), introduced in the Intermediate Representation section, is the foundation nearly every analysis here builds on — nodes are basic blocks, edges represent possible jumps between them, and questions like "can control ever reach this point" or "what are all the possible predecessors of this block" are answered by examining the CFG's structure.

Data-flow analysis is a general family of techniques that compute facts that hold true at each point in a program by propagating information along the CFG's edges — reaching-definitions (which assignments could still be "in effect" at a given point) and liveness (which values might still be read later) are two of the most fundamental and widely used data-flow analyses.

A dominator relationship captures which basic blocks must always execute before another — block A "dominates" block B if every possible path from the program's entry to B passes through A. Dominator information is essential for correctly placing SSA form's phi functions (from the Intermediate Representation section) and for many loop-related optimizations, since a loop's "header" block is defined in terms of dominance.

Escape analysis determines whether a value (like an object allocated inside a function) can ever be accessed from outside that function's scope — if it provably cannot "escape," a compiler may allocate it on the stack (cheap, automatically reclaimed) instead of the heap (more expensive, and in garbage-collected languages, adding pressure on the collector), even in a language that would otherwise default to heap allocation for that value.

Assuming compiler optimizations are based on vague heuristics or guesswork — the mainstream optimizations covered in the previous section are almost always grounded in one of these formally defined, provably sound analyses, specifically so the compiler can guarantee it isn't changing the program's observable behavior.

Underestimating how much of a compiler's engineering effort goes into these underlying analyses rather than the named optimizations themselves — a correct, efficient data-flow analysis framework is what makes dozens of specific optimizations possible to implement safely and consistently.

Confusing dominance (a static property of the CFG's structure, always true regardless of runtime input) with something dynamic or input-dependent — dominance is a fixed structural fact about the compiled program's control-flow graph, not something that varies at runtime.

Recognizing that if a compiler can't prove a fact about your code (for example, because two pointers might alias, discussed further below), it must conservatively assume the worst case and skip an optimization it otherwise could have applied — which is exactly why restructuring code to make facts more provable (using more precise types, avoiding unnecessary aliasing) can sometimes measurably improve generated code quality.

Understanding escape analysis as one concrete reason a garbage-collected language can still sometimes stack-allocate short-lived objects efficiently, rather than assuming "garbage collected" always implies heap allocation with associated collector overhead for every single object.

Appreciating why some optimizations only become possible with more information available (like at link time, across the whole program, discussed in the previous section's LTO point) — a single-file analysis is fundamentally more limited in what it can safely prove than one with visibility into the entire program at once.

Alias analysis and its practical impact Alias analysis tries to determine whether two different pointers or references could ever refer to the same memory location — a genuinely hard problem in languages like C and C++ where pointers can be freely manipulated. When a compiler can't prove two pointers don't alias, it must conservatively assume they might, which can block optimizations like reordering memory accesses or keeping a value cached in a register instead of re-reading it from memory — this is precisely the motivation behind C's restrict keyword, which lets a programmer explicitly promise the compiler that a given pointer doesn't alias others, unlocking optimizations that would otherwise be unsafe to apply.

Interprocedural vs. intraprocedural analysis Intraprocedural analysis examines one function in isolation; interprocedural analysis reasons across function-call boundaries (for example, determining what a called function might do to its arguments, or whether a value could escape through a function call). Interprocedural analysis is significantly more powerful — enabling optimizations ordinary single-function analysis cannot — but also significantly more expensive to compute correctly and efficiently across a large program, which is one of the core trade-offs whole-program and link-time optimization systems have to manage.

SSA construction relies directly on dominance Correctly placing the minimal necessary set of phi functions when converting a program into SSA form (from the Intermediate Representation section) is a direct, well-studied application of dominance information — specifically, phi functions are needed exactly at each variable's "dominance frontier," the precise set of points where control-flow paths carrying different definitions of that variable first merge back together.

What is a dominator, in the context of a control flow graph?

Block A dominates block B if every possible execution path from the program's entry point to B must pass through A first. This is a static, structural property of the control-flow graph, used for things like correctly placing SSA phi functions and reasoning about loops.

What is liveness analysis used for?

Determining, at each point in a program, which values might still be read later along some execution path — used directly for dead-code elimination (removing assignments whose value is never live/used) and for register allocation (a register can be reused once the value in it is no longer live).

What does escape analysis let a compiler do?

Determine whether an allocated value can ever be accessed from outside its allocating function's scope. If it provably cannot escape, the compiler may allocate it on the stack instead of the heap, avoiding heap allocation and, in garbage-collected languages, reducing collector overhead.

Why is pointer aliasing a problem for optimization in C and C++?

Because when a compiler cannot prove two pointers never refer to the same memory, it must conservatively assume they might, blocking optimizations like reordering memory operations or caching a value in a register — which is why C's restrict keyword exists, letting the programmer assert non-aliasing explicitly.

int compute() {
    int x = 5;
    x = 10;      // is the first assignment (x = 5) ever used?
    return x;
}