Which conditions must hold before a compiler hoists a computation out of a loop body?
answer
- same value on every iteration
- preheader runs once, before entry
- the loop might run zero times
- effects and faults block the move
- longer live range, more spill pressure
basics
~20 sThe expression must be invariant — every operand defined outside the loop and unchanged by it — and moving it must not change behaviour. That means it is effect-free and safe to evaluate even when the loop body would have run zero times, or the hoist is guarded.
solid answer
~40 sThree conditions. **Invariance**: every operand is a literal or defined outside the loop, nothing in the body redefines it, and for a memory read nothing in the body may write that location. **Safety**: the expression has no observable effect and cannot fault, because the hoisted copy runs in the preheader — once, before the loop's entry test — so it executes even on a zero-iteration loop, and even on iterations where a conditional inside the body would have skipped it. **Profitability**: the hoisted value is now live across the whole loop, which raises register pressure and can force a spill that costs more than recomputing a cheap operation. When safety cannot be proved, the usual remedy is to guard the preheader with a copy of the loop's entry test.
code
pseudocode · 16 lines// before: the product is recomputed on every iteration
i = 0
while i < n:
limit = base * factor
if rows[i] > limit:
emit(rows[i])
i = i + 1
// after: hoisted into a guarded preheader
i = 0
if i < n: // guard duplicates the loop entry test
limit = base * factor // runs once, and only if the body will run
while i < n:
if rows[i] > limit:
emit(rows[i])
i = i + 1go deeper
Recall the idea: work that produces the same value each time around can be done once before the loop instead.
State all three conditions and explain the preheader, including why a loop that might run zero times forces either a guard or a proof of the trip count.
Demonstrate the failure you have actually seen: a legal hoist that lengthened a live range, forced a spill in a hot loop and made the optimised build slower than the unoptimised one.
Treat it as a cost-model question — when the pipeline should hoist aggressively, how it interacts with later allocation, and how you keep that decision measurable rather than folkloric.
## What invariant actually means An expression is **loop-invariant** when it evaluates to the same value on every iteration. Concretely: each operand is either a literal, or defined outside the loop, or itself invariant by the same rule; nothing inside the body redefines those operands; and if the expression reads memory, nothing inside the body may write the location it reads. That last clause is the one that most often blocks a hoist in real code, because proving no write can touch a location is an aliasing question, and a single opaque call in the body can force the compiler to assume the worst. The transform moves the computation into the **preheader** — a block that executes exactly once, immediately before the loop's first entry test. That is the whole benefit: work proportional to the trip count becomes work done once. ## Why invariance alone is not enough Hoisting changes *how often* and *under what conditions* the expression runs. Two cases make that visible. 1. **The zero-trip loop.** A loop whose entry test is false on arrival never runs its body. Move an expression into the preheader and it runs anyway. If the expression is a harmless multiply, nobody notices. If it can fault — a division whose divisor is zero when the loop is empty, an indexed read past the end of a buffer — the optimised program faults where the original did not. 2. **The conditional inside the body.** An invariant expression sitting inside an `if` within the loop runs only on iterations where the branch is taken. Hoisting makes it unconditional, which has the same consequence: work, or a fault, on paths that never had it. So the safety condition is: the expression is free of observable effects *and* safe to evaluate speculatively, or the compiler has proved the body executes at least once, or the hoist is guarded. ## The guard The standard remedy is to duplicate the loop's entry test in front of the preheader, so the hoisted work happens only when the body would have run. A counted loop with a folded bound often does not need this, because the trip count is known to be positive at compile time — which is one of the ways constant folding earns its keep two passes earlier. | condition | what it rules out | typical remedy | |---|---|---| | operands unchanged in the body | a value that differs per iteration | decline the hoist | | no write in the body may alias a read | a stale value after a store | stronger aliasing facts, or inline the opaque call | | effect-free | duplicating or losing an effect | decline the hoist | | cannot fault when the body runs zero times | a new fault in the optimised build | guard the preheader, or prove the trip count | | result still worth it | a spill worse than recomputing | cost model declines | ## The cost nobody mentions first A hoisted value is live from the preheader to its last use inside the loop — that is, across the entire loop. In the interference graph the allocator builds later, that value now conflicts with everything else live in the loop. On a hot loop that already uses most of the machine's registers, the hoist can be what tips allocation into spilling: the value is stored to the stack frame and reloaded on every iteration, which is a memory access per iteration in place of the arithmetic that was there before. For a cheap operation that is a straight loss, and allocators partly defend against it by rematerialising cheap values at their uses instead of reloading them. This is the clearest example in the whole pipeline of a transform that is locally correct, locally profitable-looking, and globally a regression — which is why motion passes consult a cost model rather than hoisting everything they legally can. ## Reading the result When a hoist is applied, the loop body shrinks and a block appears before it. If the compiler could not prove the trip count, that block sits behind a test that mirrors the loop condition, and the loop itself usually ends up in a form that tests once on entry and again at the bottom. Seeing that shape in generated code is the signature of a guarded hoist rather than an unconditional one.
- Why is an invariant expression inside a conditional within the loop body harder to hoist?Because it currently runs only on iterations where the branch is taken, and hoisting makes it unconditional. That is fine for an effect-free, non-faulting expression, since evaluating it more often changes nothing observable. For anything that can fault or has an effect, the compiler must either prove the branch is always taken or leave the expression where it is.
- How can a legal hoist make a hot loop slower?The hoisted value becomes live across the whole loop, so it interferes with every other value live there. If the loop already uses most of the available registers, the allocator spills it: a store after the preheader and a reload at each use. Replacing a cheap arithmetic operation with a per-iteration memory access is a net loss, which is why motion passes consult a cost model.
- What lets a compiler skip the guard entirely?Proving the body runs at least once. A counted loop whose bounds were folded to literals gives that immediately, and so does a form that tests the condition at the bottom after an entry test the compiler can reason about. Without such a proof, the preheader is guarded by a copy of the entry test.
Hoisting is doing the setup before you check whether the shop is open. Harmless if the setup costs nothing; wasteful, or wrong, if the setup is something you cannot take back.
saying these in an interview costs you the question
- Says invariance alone is sufficient to hoist.
- Forgets the loop may execute zero times.
- Thinks the preheader runs once per iteration.
- Hoists a read while an opaque call in the body may write it.
- Assumes hoisting is always a win, ignoring register pressure.