Branches determine which instructions execute and which definitions can reach later uses.
By the end: Read a control-flow graph, explain dominance, and separate a graph of possible paths from one execution trace.
A basic block has one entry and executes straight through until its terminator, such as a branch or return. A control-flow graph connects blocks by possible transfers. A loop appears as a path that can return to an earlier block, not as a magical instruction that repeats everything above it.
The loop experiment initializes i and sum, tests i against a bound, updates the two values in the body, and returns when the test fails. The graph shows every possible edge for this program. Highlighting shows one execution, with a fixed small bound, rather than changing the graph itself.
A control-flow graph records possible transfers between basic blocks. It is not a timeline and does not place blocks at memory addresses. To construct the counting-loop graph, first identify its decisions. Initialization sets i and sum to zero. A test compares i with the bound. A successful test transfers to a body that adds i to sum and increments i. The body returns to the test, while a failed test transfers to the return. The graph needs separate blocks where these transfers can choose different continuations.
The entry block has one outgoing edge to the test. The test has two outgoing edges, labeled true and false. The body has one outgoing back edge to the test, and the exit returns rather than choosing another block in this fragment. Calling an edge a back edge describes its role in this loop, not an instruction to reverse execution. The updated state travels forward through another visit to the test. The body has already completed its addition and increment before that visit begins.
Basic-block boundaries describe control, not an arbitrary fixed number of source lines. The two updates can occupy one body block because execution proceeds through both without an intervening branch in this model. If a language operation could transfer to an exception handler, an IR that models those exceptional transfers may need additional edges or block boundaries. Our loop model has no such operations. Its four blocks are appropriate for its specified arithmetic and control, rather than a universal template for every source-level while loop.
Changing the bound does not require changing these four blocks or their possible edges. Bound zero makes the first comparison false, while bound five allows several trips through the same body and test. A graph edge can exist without being taken in a particular run. This is why counting four drawn blocks does not predict how many block executions the model records. The static structure stays small while dynamic visits repeat, and a graph can represent many traces without drawing a fresh copy of the body for each iteration.
Before starting the page's loop player, choose the preset that skips the body and predict the completed blocks. They are entry, test, and exit. Both variables remain zero throughout, because neither body update executes. The test-to-body edge is still present in the picture, but it is unused in this scenario. Compare that prediction with the complete block trace, not only the final return. A return value of zero alone would not distinguish this path from a run that adds zero during one body visit.
| Scenario | Completed blocks | Body state / returned value |
|---|---|---|
| Bound 0 preset | Entry, test, exit | No body state / return 0 |
| Bound 1, paper comparison | Entry, test, body, test, exit | After body: i = 1, sum = 0 / return 0 |
Next choose the three-iteration preset, which resets the trace rather than continuing the previous run. Predict the first completed body state before advancing. The body adds the old i, which is zero, to sum, then increments i to one. Its recorded state is therefore i equal to one and sum equal to zero. Reading the highlighted body as a promise about the next operation would give the wrong interpretation. The player records the block that has completed, so its values include all updates in that block.
A block dominates another when every path from the entry to the latter passes through the former. This helps explain where a definition is available and where a computation can safely be placed. An observed trace is insufficient to prove dominance because it may visit only one of several paths.
Data-flow analyses propagate facts across graph edges, often until reaching a fixed point. Loops can require repeated propagation. Facts may be conservative: an analysis can say a value might be live or a branch might be reachable even when a more powerful analysis could rule it out. Such caution can prevent an unsafe transformation.
Dominance asks a question about every path through a graph. A block D dominates a block B when every path from the entry to B passes through D. Consider separate conditional pseudocode whose entry defines a = 4 and then chooses a left or right block. The left defines u = a + 1, the right defines v = a + 2, and both lead to a join. Entry dominates the join because either route begins there. Left does not dominate the join because the right route avoids it.
This distinction explains a common invalid value use. Returning u directly at the join would work on the left route but lack a definition on the right route. The fact that the graph prints the left assignment above the join is irrelevant. A valid merge could define r = phi(left: u, right: v) at the join and return r. That selects five after the left path and six after the right. The phi uses each value on the incoming edge where its definition is available.
For ordinary SSA uses outside phi inputs, a definition must dominate its uses, with an earlier definition preceding a later use inside the same block. Phi inputs have the edge-specific interpretation just described. This is a representation rule that makes value availability checkable without executing every input. It does not assert that all source languages use SSA, nor that dominance alone proves an optimization safe. Effects, memory changes, and exceptions still require their own reasoning even when all value definitions reach their uses correctly.
You can compute dominance sets by repeated intersections. Give entry the set containing entry alone. Initially give each other reachable block the set of all blocks. For a non-entry block, intersect the sets of its predecessors and then add the block itself. In the diamond, left eventually has entry and left, while right has entry and right. Their intersection contains only entry, so the join's final set contains entry and join. The calculation encodes the requirement that a dominator occur on every incoming route.
Loops explain why the calculation may require repetition. A header can have an entry predecessor and a back-edge predecessor whose facts depend on the header itself. Updating one set may change a successor's set, which then affects another update. For a finite graph, this particular process only removes candidates from the initial finite sets, so it eventually stops when no set changes. That stable result is a fixed point. Reaching it is a static analysis computation, not evidence that executing the modeled program terminates.
| Block | Predecessors | Final dominators |
|---|---|---|
| Entry | None in this fragment | {Entry} |
| Left | Entry | {Entry, Left} |
| Right | Entry | {Entry, Right} |
| Join | Left and Right | {Entry, Join} |
Try the diamond by drawing the path entry, right, join and crossing out every block it avoids. That single path disproves the claim that left dominates join. To prove entry dominates join, however, one selected path is insufficient. Inspect both incoming routes and the graph's defined entry. Then add a new edge directly from entry to join on paper. A phi at join now needs an input for that predecessor too. A control-flow edit can invalidate value-selection structure even when every old instruction remains unchanged.
Changing the bound replaces and resets the trace. The graph retains every possible edge; the highlighted block is the last completed block.
After entry: i = 0, sum = 0. Initialize i and sum to zero.
| Block | i | sum | Effect or decision |
|---|---|---|---|
| entry | 0 | 0 | Initialize i and sum to zero. |
| test | 0 | 0 | 0 < 3 is true. |
| body | 1 | 0 | Add 0, increment i, then return to the test. |
| test | 1 | 0 | 1 < 3 is true. |
| body | 2 | 1 | Add 1, increment i, then return to the test. |
| test | 2 | 1 | 2 < 3 is true. |
| body | 3 | 3 | Add 2, increment i, then return to the test. |
| test | 3 | 3 | 3 < 3 is false. |
| exit | 3 | 3 | Return 3. |
| Bound | Body visits | Returned sum |
|---|---|---|
| 0 | 0 | 0 |
| 3 | 3 | 0 + 1 + 2 = 3 |
| 5 | 5 | 0 + 1 + 2 + 3 + 4 = 10 |
For bound three, begin after entry with i equal to zero and sum equal to zero. The first test succeeds because zero is smaller than three. After the first body, i is one and sum remains zero. The second test succeeds, and the next body adds one before setting i to two. The third test also succeeds, so the final body adds two and sets i to three. At this point sum is three, but execution has not yet checked the condition that permits leaving the loop.
The fourth test compares three with three and fails. Only then does the exit return three. The ordered completed-block sequence is entry, test, body, test, body, test, body, test, exit. It contains nine recorded states, including the initial entry state. The player has eight transitions between these states, so a final playback step labeled eight is consistent with nine rows in the complete trace. State count and transition count differ by one here because the first state exists before the player advances at all.
| State number | Completed block | i | sum | Decision or update |
|---|---|---|---|---|
| 0 | Entry | 0 | 0 | Initialize |
| 1 | Test | 0 | 0 | 0 < 3 is true |
| 2 | Body | 1 | 0 | Add 0, then increment |
| 3 | Test | 1 | 0 | 1 < 3 is true |
| 4 | Body | 2 | 1 | Add 1, then increment |
| 5 | Test | 2 | 1 | 2 < 3 is true |
| 6 | Body | 3 | 3 | Add 2, then increment |
| 7 | Test | 3 | 3 | 3 < 3 is false |
| 8 | Exit | 3 | 3 | Return 3 |
For a nonnegative bound n in this model, the body executes n times and the test executes n plus one times. Entry and exit each execute once. Adding these counts gives two times n plus three block visits. The model accepts integer bounds zero through five, so these formulas describe its accepted scenarios without making claims about arbitrary source programs. Bound five gives five body visits, six tests, thirteen recorded states, and twelve transitions. Its sum is ten because the body adds zero, one, two, three, and four.
An invariant explains why the sum matches those traces. Whenever the test begins with i equal to k, sum contains the integers starting at zero and ending just before k. The entry establishes this for k equal to zero through an empty sum. If a test succeeds, the body adds k and increments i, so the same statement holds for the next test with k increased by one. At the failed test, k equals the bound. The return therefore contains exactly the terms for successful iterations.
Use the invariant to compare bound zero with a paper-only bound-one case. Both return zero, but the first has no body visits and the second has one body visit that adds zero. Their total block visits are three and five respectively. This is a counterexample to inferring an execution path from the returned value alone. It also explains why a wrong loop might accidentally pass a test that checks only zero. Intermediate i values and test outcomes discriminate behaviors that the final arithmetic result cannot distinguish.
| Bound | Static blocks | Body visits | Test visits | All visits | Return |
|---|---|---|---|---|---|
| 0 | 4 | 0 | 1 | 3 | 0 |
| 1, paper case | 4 | 1 | 2 | 5 | 0 |
| 3 | 4 | 3 | 4 | 9 | 3 |
| 5 | 4 | 5 | 6 | 13 | 10 |
Inspect the complete trace for the five-iteration preset and predict each row before uncovering it. The completed body states should be one and zero, two and one, three and three, four and six, then five and ten, listing i before sum. Check the next test after every body. A missing final test or a body state with the old i indicates a different recording convention or an error. These are exact checks on the teaching trace, not measurements of machine instruction counts, processor cycles, or elapsed runtime.
Moving a computation before a conditional can make it execute on paths where it previously did not. That may introduce an exception, a memory access, or an observable effect. The arithmetic expression lab has no such effects, but the restriction matters in richer languages.
Loop optimizations also need proof about bounds, dependencies, and effects. A value that appears unchanged in the source text may change through an alias or a call. A control-flow graph exposes paths; it does not automatically solve every semantic question about the operations on those paths.
A control-flow graph helps state a transformation's proof obligations. Suppose separate pseudocode tests d != 0, computes q = 12 / d only on the true branch, and returns zero on the false branch. Assume integer division by zero raises an observable error. Moving the division before the test makes it execute even when d is zero. The original path returns zero without dividing, while the transformed path raises an error. The graph has exposed a change in which operations execute, regardless of whether the arithmetic is correct for nonzero d.
Contrast that operation with an unused local computation of 12 + 1 under wrapping integer rules, with no effects or failure. Executing that addition before the branch need not introduce the division example's error. Yet moving it does not automatically make the program faster. The false path now performs an extra addition, and a target might already implement the original branch differently. Semantic permission answers whether behavior remains allowed. A cost argument asks whether a particular representation and execution workload benefit.
Loop-invariant code motion applies related reasoning to repeated paths. An expression is invariant if the relevant inputs have the same values on each iteration where it executes. Consider a body that computes scale * 2 without assigning scale. If scale is a stable local integer and multiplication has wrapping, effect-free semantics, repeated evaluations have the same result. A compiler might compute the result outside the loop. If the body can execute zero times, the moved operation now also executes on a path where the original never computed it.
That newly introduced execution matters when an apparently invariant operation can fail. A division by an unchanged divisor might still trap before a zero-iteration loop if moved without a guard. A memory read may also cease to be invariant if the body writes the same storage through another reference. The source spelling of the pointer can remain unchanged while the referenced contents change. A safe analysis must account for those possible writes, including relevant calls. The graph records paths, but operation semantics and alias information determine which movements preserve behavior.
For a paper experiment, add a hypothetical print of i immediately before the loop body increment. Bound three now prints zero, one, two. Moving the print to the test block before its comparison would also print three on the final failing test. Both versions still return three, so comparing final sums misses the changed output trace. Moving the print after the body increment instead prints one, two, three. The block location and the order within that block both affect observable behavior under this assumed print semantics.
| Print location | Output for bound 3 | Returned sum |
|---|---|---|
| Body, before increment | 0, 1, 2 | 3 |
| Body, after increment | 1, 2, 3 | 3 |
| Test, before comparison | 0, 1, 2, 3 | 3 |
Return to the actual loop player and separate what it demonstrates from those paper transformations. It executes the fixed update order and lets presets change the bound; it does not move instructions, model division, or analyze aliases. Use its completed-block states to justify the exact sums and visit counts. Use the separate counterexamples to explain why a compiler needs more than a plausible graph rewrite. An optimization claim should identify the permitted inputs, the preserved observations, and the target-dependent cost evidence before drawing a conclusion about real performance.
For bound three, how many times does the loop body run, how many times is the test evaluated, and what is returned?
The failing final test is still a test execution.
| Operation | Dynamic visits |
|---|---|
| Entry | 1 |
| Test | 4 |
| Body | 3 |
| Exit | 1 |
The body runs three times, for i = 0, 1, and 2. The test runs four times, including i = 3 when it fails. The return value is 0 + 1 + 2 = 3. Counting blocks in the graph would not give these execution counts.
A division occurs only inside a branch whose condition ensures the divisor is nonzero. Is moving the division before the branch automatically safe?
Ask which new executions the movement creates.
| Location | When division occurs |
|---|---|
| Inside guarded branch | Only when the guard permits it |
| Before the branch | Also on paths that skip the branch |
No. The moved operation may execute with zero on a path where the original did not divide. Whether that traps, raises an exception, or has another specified effect depends on the language. A valid transformation must preserve the relevant behavior and prove its preconditions, not only simplify the graph.
The explanations, examples, and worked answers are complete without these optional links. The sources describe specific implementations and language contracts, not one universal compiler pipeline. SmallExpr and the later pseudocode models are constructed teaching examples. Source notes identify the selected material reviewed; this is not an exhaustive compiler survey, production conformance test, or independent specialist review.
Selected material on IR structure, SSA, phi semantics, integer operations, and semantic constraints. A production IR reference, not a specification of SmallExpr or a claim that every compiler uses LLVM.
Selected overview and register-allocation material describing instruction selection, target constraints, liveness, and native-code generation. The storage lab is not an implementation of LLVM’s allocator. The reviewed register-allocation example has inconsistent def/use prose; the lesson follows explicit assignment direction instead.