In a control-flow graph, a back edge runs from node L to node H. What structural condition on H and L makes this a natural loop back edge?
AL must dominate H — control must always flow through L before H
BH must dominate L — control must always flow through H before L
CH and L must be in the same strongly connected component with no other entries
DL must be the only predecessor of H in the CFG
A back edge is defined as an edge from L to H where H dominates L — meaning every path from the CFG entry to L passes through H. H is the loop header: it is the single required entry point. The dominance requirement is what makes it a 'natural' loop; without it, the loop would be irreducible (multiple entries). Option A has the relationship reversed: it is H that dominates L, not the other way around.
Question 2 Multiple Choice
A nested loop has an outer loop running 100 iterations and an inner loop running 10 iterations per outer iteration. Which loop should be the primary target for optimization, and why?
AThe outer loop, because it controls when the inner loop executes
BThe inner loop, because a single operation moved out of it saves 1,000 executions, not just 100
DNeither — compilers optimize loops based only on instruction count, not iteration count
The inner loop executes 100 × 10 = 1,000 times total, while the outer loop header executes only 100 times. Moving a loop-invariant computation out of the inner loop saves 999 redundant executions; moving it out of only the outer loop saves 99. This is why compilers prioritize innermost loops: they represent the highest iteration density, and any savings there multiplies across all outer iterations. Nesting depth is a proxy, but iteration count and operation cost are the real drivers.
Question 3 True / False
Nearly every loop in a well-formed program has exactly one entry point (header), making most loops natural loops.
TTrue
FFalse
Answer: False
Irreducible loops, which arise from unstructured control flow such as 'goto' statements or certain hand-written assembly patterns, have multiple entry points. Control can reach the loop body through more than one block, so no single header dominates all loop nodes. These are not natural loops. Compilers handle irreducible loops by either transforming them via node splitting or conservatively skipping optimizations on them.
Question 4 True / False
Loop-invariant code motion — moving computations whose operands don't change within a loop to just before the loop — can only be safely applied after loop detection has identified the loop's header and body.
TTrue
FFalse
Answer: True
To hoist an expression out of a loop, the compiler must know (1) what constitutes the loop body, (2) that the expression is computed on every execution path through the body, and (3) that it is safe to execute it earlier. All three require knowing the loop structure: its header, back edges, and body nodes. Without loop detection, the compiler cannot identify which code is 'inside' the loop or where to place the hoisted computation.
Question 5 Short Answer
What makes an irreducible loop challenging for compiler optimization, and how do compilers typically handle it?
Think about your answer, then reveal below.
Model answer: An irreducible loop has multiple entry points — no single header dominates all nodes in the loop. This breaks the assumption underlying most loop analyses: that there is one place to check loop-invariant properties and one 'pre-header' where hoisted code can be placed. Without a unique entry, induction variable detection, invariant code motion, and vectorization all become unsafe or ambiguous. Compilers typically respond either by converting the irreducible loop into a reducible one via node splitting (duplicating a shared node to give each entry path its own copy) or by skipping loop-specific optimizations on those regions entirely.
Irreducibility is rare in code generated from structured high-level languages, which is why most programmers never encounter it directly. But it matters at the compiler level because even a single irreducible region can block optimization of surrounding code.