Inside a loop, the expression `result = numerator / divisor` appears inside an `if (divisor != 0)` check. Neither `numerator` nor `divisor` is modified in the loop. A compiler identifies this as loop-invariant. Should it hoist the division to the preheader?
AYes — since neither operand changes, the division computes the same value every iteration and is safe to move
BYes — hoisting loop-invariant expressions to the preheader is always a performance improvement with no correctness risk
CNo — hoisting moves the division outside the conditional, causing it to execute even when divisor is zero, which could fault on iterations where the original code would have skipped the division
DNo — division operations are never loop-invariant because they depend on hardware state
This is the safety problem with LICM. The expression is loop-invariant (same operands, same result each iteration), but it only executes when `divisor != 0`. Moving it to the preheader causes it to execute unconditionally before every iteration. If there is any iteration where `divisor == 0` and the conditional would have protected the division, hoisting causes a fault that the original code would not have. The compiler must verify the expression dominates all loop exits — that every path through the loop executes it — before the hoist is safe.
Question 2 Multiple Choice
A compiler wants to hoist `cost = base_rate * multiplier` from inside an `if (apply_rate)` block within a loop. Under what condition is this safe?
AWhen `base_rate` and `multiplier` are global variables visible across the entire program
BWhen the compiler can prove the expression executes on every iteration (dominates all loop exits) and has no observable side effects
CWhen the loop is guaranteed to run more than a fixed threshold number of iterations
DWhen `apply_rate` is set before the loop begins and never changes inside the loop
Domination is the key safety condition. 'Dominates all loop exits' means every possible execution path through the loop passes through this expression — if the loop runs, the expression executes. If `apply_rate` is sometimes false, there are paths through the loop that don't reach the expression, so it doesn't dominate. Knowing `apply_rate` is set before the loop (option D) doesn't help if it might be false — the expression still skips on some iterations. The compiler also checks for side effects: expressions that modify memory or call functions with observable effects cannot be safely hoisted even when invariant.
Question 3 True / False
Any expression inside a loop whose operands are not modified by the loop can generally be safely hoisted to the loop's preheader.
TTrue
FFalse
Answer: False
This is the most important misconception about LICM. Loop-invariance (same value every iteration) is necessary but not sufficient for safe hoisting. The expression must also execute on every iteration — it must dominate all loop exits. If the expression sits inside a conditional branch, moving it to the preheader changes when it executes, which can cause faults (division by zero, null pointer dereference) or incorrect behavior for expressions with side effects. The compiler must perform dominance analysis, not just operand analysis.
Question 4 True / False
LICM can only improve performance on loops that run at least twice; for a loop that always executes exactly once, hoisting an invariant expression to the preheader provides no speedup.
TTrue
FFalse
Answer: True
Correct. The entire benefit of LICM is eliminating repeated computation: instead of computing x*y on every iteration, compute it once before the loop. If the loop body executes exactly once, the expression already computes exactly once, so moving it outside the loop neither increases nor decreases execution count. LICM's value scales with iteration count — the more iterations, the greater the savings from hoisting an invariant expression.
Question 5 Short Answer
Explain why hoisting a loop-invariant expression from inside a conditional branch to the loop's preheader can be unsafe, and what condition the compiler must verify before proceeding.
Think about your answer, then reveal below.
Model answer: If the expression is inside a conditional, it only executes when that condition is true. Moving it to the preheader makes it execute unconditionally before the loop. If the expression can fault (division by zero, null dereference) or has observable side effects, this changes the program's behavior on iterations where the original condition would have been false. The compiler must verify that the expression dominates all loop exits — meaning every execution path through the loop necessarily reaches the expression — before hoisting is safe.
This is why dominance analysis is the core tool for LICM safety, not just operand analysis. The compiler builds a control-flow graph of the loop and checks whether the expression's block dominates the loop exit blocks. If it does, every iteration executes the expression, and hoisting is semantics-preserving. If it does not (the expression is inside any branch that might not execute), the compiler must either prove the expression is side-effect-free and can't fault, or leave it in place.