9. What Compilers Can and Cannot Do

What this lecture covers

This lecture picks up where the earlier LLVM IR and assembly lecture left off, looking at what actually happens inside the compiler between IR generation and final assembly. Instead of the asymptotic analysis of the previous lecture on multithreaded algorithms, this one is about the mechanics of compiler transformation passes: how a compiler mechanically rewrites code to remove waste, and where its reasoning breaks down.

Using a small N-body gravity simulation as a running example, the lecture walks through how the compiler optimizes a single scalar, a struct, a chain of function calls, and a nested loop, then turns to case studies of loops that do or do not vectorize because of pointer aliasing. After watching, you should be able to read a compiler optimization report, reason about why a given piece of code was or wasn't optimized, and use annotations like restrict and const to help the compiler do more.

Key ideas

• Transformation passes: the compiler runs a fixed, empirically-tuned sequence of passes over the IR, each analyzing and rewriting code to improve performance.
• Optimization reports: passing the right flags makes LLVM report what each pass did, but the reports are jargon-heavy, incomplete, and don't cover every pass.
• Register promotion: the compiler's core trick for scalars and struct fields is replacing loads and stores to stack memory with the original values already held in (infinite) IR registers, then deleting the now-dead allocations, stores and loads.
• Function inlining: replacing a call with the callee's body, which then exposes further dead-code elimination; it is blocked by recursion, calls across compilation units, and it can hurt performance by bloating code size.
• Loop invariant code motion (hoisting): computations inside a loop that don't depend on the inner loop variable get moved to the outer loop so they run fewer times.
• Magic-number division: at the assembly stage, constant integer division is replaced by a multiply-and-shift using a precomputed magic constant, since division is much slower than multiplication.
• Alias analysis: to vectorize a loop over two pointers, the compiler must prove the underlying memory doesn't overlap; when it can't prove this statically it may generate both a vectorized and a scalar version of the loop, guarded by a runtime aliasing check.
• What compilers can't do: they don't understand domain semantics (such as physical symmetry in a force calculation), and precise aliasing is undecidable in general, so compilers fall back on heuristics and programmer hints like restrict and const.

Walkthrough

Why study compiler optimizations (4:02)

The lecture opens with reasons to look inside the compiler: it saves you manual optimization work, it helps you write code that the compiler can optimize well, it helps you debug compiler-level surprises and bugs, and understanding it generalizes beyond this course since many languages compile through similar pipelines, often via LLVM itself.

Anatomy of the compiler and its reports (8:03)

The compiler is described as a sequence of transformation passes over LLVM IR, run in a fixed order. You can request reports on what passes did using compiler flags and a regular expression filter, but the reports are long, jargon-filled, and don't cover every pass or tell the whole story.

A tour of what LLVM optimizes (13:09)

Working from a checklist reused from an earlier lecture, the lecture rates which classic optimizations LLVM handles well: constant folding, common subexpression elimination, algebraic simplification, loop hoisting, unrolling, vectorization, tail-call elimination and inlining are strong; sentinels, fast-path creation and coarsening are not things the compiler does for you. It notes the compiler is especially effective at keeping data in registers rather than memory.

Magic-number arithmetic in assembly (18:11)

Comparing IR to final x86 assembly for multiply and divide by constants shows the LEA instruction used for fast multiplies by small constants, and a magic-number multiply-and-shift trick that replaces division by 71 with a multiplication by 2^38 / 71 + 1 followed by a right shift, avoiding the much more expensive divide instruction.

Optimizing scalars, structs and the N-body example (25:15)

Using a vec_scale routine from an N-body simulation, the lecture shows step by step how unoptimized IR that stores a scalar argument to the stack and reloads it gets rewritten to use the register value directly, then how the same pattern applies field by field to a struct, eliminating all the stack allocations, stores and loads once nothing else depends on them.

Inlining function calls (42:33)

A chain of vec_add and vec_scale calls is inlined one call at a time: the callee's body replaces the call instruction, the now-redundant call and return are deleted, and the resulting pack-then-immediately-unpack struct operations are removed as dead code. Repeating this across the whole chain reduces several function calls to straight-line floating-point arithmetic. The lecture then explains why the compiler doesn't inline everything: recursion, cross-compilation-unit calls, and code-size blowup that can hurt instruction-cache performance, plus attributes like always_inline, noinline and link-time optimization for controlling it.

Hoisting loop-invariant code (59:47)

A doubly nested loop that computes forces between N bodies has two address calculations in its innermost loop that only depend on the outer loop variable. The compiler proves they are invariant across inner-loop iterations and hoists them to the outer loop, cutting how often they execute. The lecture also notes what the compiler cannot see: it can't exploit the physical symmetry that the force from body 1 on body 2 is the negative of the force from body 2 on body 1, because it only knows algebra, not physics.

Vectorization and pointer aliasing (1:06:50)

A simple axpy-style loop (Y[i] += A * X[i]) is put to a vote on whether it vectorizes; the answer turns out to be "yes and no." Inspecting the compiled control flow graph reveals three loops: a vectorized version, a scalar version, and a runtime check comparing X, Y and N to detect whether the two arrays overlap in memory, branching to whichever loop is safe. The lecture closes by explaining that precise alias analysis is undecidable in general, so compilers rely on heuristics and metadata, and recommends programmers help by annotating pointers with restrict and const.

Before you watch

• Review lecture 5's coverage of LLVM IR and x86-64 assembly, since this lecture builds directly on that IR-to-assembly pipeline.
• Be comfortable with basic pointer arithmetic in C, needed to follow the aliasing address-calculation example.
• A quick refresher on registers versus memory access costs will help the register-promotion discussion make sense.

Check your understanding

1. Why does eliminating a load from memory require first proving that no other instruction can have changed the stored value?
2. What three reasons does the lecture give for why a compiler won't inline every function call?
3. Explain in your own words what loop invariant code motion does and why it reduces running time.
4. Why did the compiler generate two versions of the axpy-style loop instead of just one?
5. What can restrict and const tell the compiler that it cannot otherwise infer on its own?