expertLegality
I want to move this computation out of the loop. How do I decide whether I am allowed to?
Whether the candidate reasons from observable behavior and preconditions instead of from "it looks the same". The discriminator is whether they name the trap and the exception cases without prompting — those are what separate an optimizer from a miscompiler.
What a strong answer covers
- The question is always the same: does every execution of the transformed program produce the same observable behavior as some legal execution of the original? Observable behavior is defined by the language — typically I/O, volatile accesses, program termination and, in a concurrent language, whatever the memory model makes visible to other threads. Everything else is the compiler's to rearrange under the as-if rule.
- For hoisting out of a loop, that decomposes into concrete preconditions. The expression must be loop-invariant: none of its operands is redefined in the loop, and no store in the loop may alias any memory it reads. It must not have side effects. It must not be able to trap — a division or a load that faults, hoisted above the guard that prevented it from executing, converts a program that ran fine into one that crashes. And the loop must execute at least once, or the hoist must go into a preheader that only runs when the loop is entered, otherwise you have introduced a computation the original never performed.
- The last two are the ones people get wrong, and they are why compilers hoist into a guarded preheader rather than above the loop, and why a faulting operation is hoisted only when it can be proved safe or the target defines the fault away.
- The general shape holds for other transformations. Deleting a computation requires that nothing observable depends on it having run. Reordering two memory operations requires that they do not alias, and in a concurrent program that the memory model permits it. Folding an operation at compile time requires that it cannot trap, which is why a compiler that folds
1/0has turned a runtime fault into a build failure.
✓ Green flags
- Starts from observable behavior and the as-if rule rather than from the transformation.
- Lists preconditions as a checklist: invariance, no side effects, no trap, executes at least once.
- Names the preheader and why it is guarded.
- Raises aliasing as the thing that usually blocks it in real code.
- Notes that concurrency changes what is observable, so a single-threaded argument is not sufficient.
✗ Red flags
- "It computes the same value, so it is fine." Same value is necessary and nowhere near sufficient — a trap or a side effect makes it illegal regardless.
- "The compiler does it automatically, so I do not need to know." It does it when it can prove the preconditions; the interesting cases are precisely the ones where it cannot, and knowing why is how you fix them.
- "Just mark it const." Const in most languages constrains the programmer, not the alias analysis; it is not a promise the optimizer can rely on.
- "Zero-iteration loops are an edge case nobody hits." A hoisted faulting load in a loop that runs zero times is a crash in production and a clean run in test.
Follow-up
The loop body contains a call to a function in another translation unit. What can the compiler still hoist, and what changes if you enable LTO?
Implementation challenge
What to ask them to write or trace on a whiteboard.
Write a loop where hoisting is legal, then change one line so it becomes illegal, for each of three reasons: aliasing, a trap, and zero iterations.