expertLoops
Why does alias analysis limit what an optimizer can do?
Whether the candidate understands that most missed optimizations in real code are memory questions the compiler could not answer, and can name the mechanisms languages provide to answer them.
What a strong answer covers
- Because almost every interesting transformation on memory needs to know whether two pointers can refer to the same location, and in general that question is undecidable. The analysis must be conservative: if it cannot prove two accesses do not alias, it must assume they might, and then a store between two loads blocks reusing the first load, a hoist out of a loop is blocked, vectorization is blocked, and a store cannot be forwarded to a later load.
- This is why the same loop vectorizes with arrays and does not with pointers, why a function that takes two pointer parameters is optimized worse than one that takes one, and why a member load in a loop is reloaded on every iteration when the loop also calls anything opaque. The compiler has not been lazy; it has been unable to prove a negative.
- Languages give you ways to supply the missing fact. C has
restrictand a type-based aliasing rule that says accesses through incompatible types do not alias — the rule that makes type punning through a cast undefined. Fortran gets vectorization more easily because its parameters are non-aliasing by language rule, which is a large part of its numeric reputation. Rust encodes it in the type system: a&mutis unique by construction, so no-alias is a checked property rather than a promise. C++ has__restrictas an extension and relies heavily on inlining to make the analysis local. - Escape analysis is the same family: if a compiler can prove an object never escapes its allocating function, it can stack-allocate it, scalar-replace its fields, or remove the synchronization on it. The proof is what unlocks the optimization, and it is the proof that fails.
✓ Green flags
- States the conservatism direction correctly: unproven means assume aliasing.
- Gives a concrete missed optimization — a reload in a loop, a blocked vectorization.
- Names
restrict, strict aliasing, or Rust's uniqueness rule as ways to supply the fact. - Connects it to escape analysis and stack allocation.
- Knows that an opaque call is an alias barrier and that inlining or LTO is often what fixes it.
✗ Red flags
- "Pointers are slow." The pointer dereference is not the cost; the lost optimization is, and the two have different fixes.
- "Just use restrict everywhere." It is an unchecked promise. Breaking it is undefined behaviour with no diagnostic, and the failure appears only under optimization.
- "Modern compilers solve aliasing." Modern compilers have very good heuristics for local cases and are still defeated by an opaque call.
- "Strict aliasing means you cannot cast pointers." You can cast; you cannot *access* an object through an incompatible type, and the distinction is what makes
memcpythe sanctioned route.
Follow-up
A vectorization report says "possible dependence between loads and stores". What would you look at, and what are your options in order of preference?
Implementation challenge
What to ask them to write or trace on a whiteboard.
Write a two-pointer function where a reload is forced. Then produce three versions where the compiler can prove non-aliasing — one by language rule, one by annotation, one by restructuring — and say which you would ship.