CFGsimplified

Building the CFG

An `if` becomes two blocks and a join. A `while` becomes three blocks and an edge that points backwards. Then there is the edge nobody expects: the one from a two-way branch straight into a merge, which has no safe place to put anything — and which AtlasLang reports rather than guesses at.

The question

How does a compiler turn nested if and while statements into blocks and edges, and what goes wrong?

Source→Lexing→Tokens→Parsing→AST→Semantics→Typed→IR→Optimize→Codegen→Machine code→Link→Execute

What the program is here

The typed AST on the way in, a graph of blocks and edges on the way out, and — during construction — a partially built graph with a "current block" that instructions are appended to. It exists to answer the question the tree could not: from here, where can control go, stated as edges rather than as nesting.

What this phase may assume or do

The construction is correct when every path through the graph corresponds to a possible execution of the source and every possible execution corresponds to a path. Two clauses do most of the work: a loop's condition block must be reached before its body on entry, so a zero-iteration loop executes nothing; and every block must end in exactly one terminator, so no block can fall through into whichever block the emitter happened to place next.

Key points

Construction is a recursive walk over the tree with one piece of state: the block instructions are being appended to.
An if produces a branch, one or two arm blocks and a join; an if with no else sends the false edge straight to the join.
A while produces a condition block, a body block and an exit, and the entry must jump to the *condition* — jumping to the body builds a do/while.
The back edge from the body to the condition is what makes the graph cyclic, which is why dominance must iterate.
Predecessor and successor lists should be recomputed from terminators, never maintained by hand across transformations.
A critical edge runs from a multi-successor block to a multi-predecessor block and has no safe place for edge code; splitting it is the fix.

`if` becomes a diamond

The construction is a recursive walk with one piece of mutable state: the block instructions are currently being appended to. For an if, the walk creates the blocks first — a then-block, an else-block if there is one, and a join block — then lowers the condition into the *current* block and terminates it with a branch to the then-block and the else-block, or to the join if there is no else.

Then it makes the then-block current, lowers the body, and terminates with a jump to the join. Same for the else-block. Then it makes the join current, and returns — so whatever comes next in the source is appended to the join block, which is exactly right, because that is where both arms end up.

The if with no else is worth pausing on, because it is where the interesting case lives. The false edge goes directly from the condition block to the join. So the join has two predecessors, and the condition block has two successors — and that combination is the critical edge this lesson ends on.

`while` becomes a cycle

A while needs three blocks: a condition block, a body block and an exit block. The current block is terminated with an unconditional jump to the condition block — not to the body — because the condition must be evaluated before the first iteration. Then the condition block is made current, the condition is lowered into it, and it is terminated with a branch to the body or the exit.

Then the body is lowered, and terminated with a jump *back* to the condition block. That is the back edge, and it is the single most consequential edge in the whole graph: it is what makes the graph cyclic, which is why dominance must be computed by iteration rather than by a single traversal, and it is what [[natural-loops]] finds in order to recover the loop the lowering destroyed.

The two ways to get this wrong are both plausible-looking. Enter at the body instead of the condition and you have built a do/while: the body executes once even when the condition was false from the start. Point the back edge at the body instead of the condition and the loop never re-tests and never exits. Both compile. Both type-check. Both are wrong for every program that used the construct.

AtlasLang CFG for while (n < 3) { s = s + n; n = n + 1; } — verbatim engine output, with real block ids

b0entryentry
```
store @n, 0
store @s, 0
jump b1
```
Jumps to the condition, not the body. This one edge is the difference between `while` and `do/while`.
b1while.cond↺ loop header
```
%0 = load @n
%1 = bool %0 < 3
branch %1 ? b2 : b3
```
Two predecessors: the entry and the body. That makes it a merge point, and the loop header.

b2while.bodylatch

%2 = load @s
%3 = load @n
%4 = int %2 + %3
store @s, %4
%5 = load @n
%6 = int %5 + 1
store @n, %6
jump b1

Ends with the back edge.

b3while.exit
```
%7 = load @s
print %7
ret
```

Edges

b0→b1
b1→b2true
b1→b3false
b2→b1back edge

Read it asThree blocks and four edges, one of which points backwards. Everything the while meant is in that shape: the loop runs zero times if b1 immediately takes the false edge, and the back edge is what makes "zero or more times" expressible at all. findLoops() in the engine returns exactly { header: b1, latch: b2, body: [b1, b2] } for this function.

Edges must be derived, never maintained by hand

A block has a terminator, which names its successors, and a predecessor list, which is the inverse relation. Keeping both by hand across dozens of transformations is a losing game: any pass that rewrites a terminator and forgets to update the predecessor lists leaves a graph that disagrees with the code, and every analysis downstream computes a correct answer to the wrong question.

AtlasLang solves this by never maintaining them. linkEdges() clears every predecessor and successor list and recomputes both from the terminators, and it is idempotent, so calling it after any change is always safe and never wrong. Lowering calls it, unreachable-block pruning calls it again after filtering.

The same function also handles a case that is easy to miss: a branch whose two targets are the same block should contribute one edge, not two, or the block appears to have two predecessors when it has one — and a phi node placed there would then need two operands for one incoming edge. successorsOf() collapses that case explicitly.

The critical edge

simplifiedAtlasLang detects critical edges and reports them without splitting; LLVM has a BreakCriticalEdges utility that several passes require to have run, and Cranelift sidesteps the problem entirely by using block parameters instead of phi nodes, which places the value on the jump rather than on the edge. Three different answers to the same problem, and only one of them is "handle it carefully".

A critical edge goes from a block with more than one successor to a block with more than one predecessor. The if without an else produces one immediately: the condition block has two successors, the join has two predecessors, and the false edge between them is critical.

Why it matters: several transformations need to place code *on an edge*. Resolving a phi node is the standard example — the phi says "on the edge from b0, my value is 0; on the edge from b1, it is 1", and turning that into copies means placing a copy on each edge. For an ordinary edge there is somewhere to put it: at the end of the predecessor if the predecessor has only that successor, or at the start of the successor if the successor has only that predecessor. For a critical edge there is neither. Put the copy at the end of the predecessor and it also executes on the *other* successor's path; put it at the start of the successor and it also executes for the *other* predecessor's arrivals.

The fix is to split the edge: insert a new empty block in the middle, whose only job is to hold the copies. That block has one predecessor and one successor, so both placements become safe. It is a cheap transformation — an extra jump, usually removed by the backend — and it is a prerequisite for correct phi resolution rather than an optimization.

AtlasLang's outOfSSA does not split edges. What it does instead is *detect* every critical edge it crosses and return it in criticalEdges, alongside the copies it emitted. That is a deliberate design decision and the honest one for a teaching compiler: placing copies across a critical edge is a miscompilation waiting for the right program, and doing it correctly requires a transformation the function does not perform. Reporting means the risk is visible in the interactive rather than silently accepted, and the reader can see exactly which edge would need splitting.

Splitting a critical edge so a copy has somewhere to live

Before

b0: ... branch %1 ? b1 : b2     ; b0 has two successors
b1: ... jump b2
b2: %3 = phi x [0 from b0, 1 from b1]   ; b2 has two predecessors
                                        ; the b0 -> b2 edge is critical

After

b0: ... branch %1 ? b1 : b4
b1: ... %3 = copy 1
    jump b2
b4: %3 = copy 0        ; new block, holds the copy for the b0 edge only
    jump b2
b2: print %3

Legal only when

Inserting an empty block on an edge is always legal: the new block has exactly one predecessor and one successor, executes on precisely the paths the original edge did, and adds no observable behavior. It is a prerequisite for placing edge-specific code, not an optimization, and it is what makes phi resolution correct in the presence of a critical edge.

Illegal when

Placing the copy at the end of b0 without splitting is wrong whenever %3 is read on the b0 -> b1 path, because the copy executes there too and clobbers whatever that path expected. Placing it at the start of b2 is wrong because it executes for arrivals from b1 as well, overwriting the value b1 provided. For the specific program above the first placement happens to be harmless — nothing in b1 reads %3 — which is exactly what makes the bug class so durable: the wrong version passes many tests.

How it works

The steps, in the order the compiler takes them.

Keep a current block; append every instruction lowered from a statement to it.
For an if: create the arm blocks and the join first, lower the condition into the current block, terminate with a branch, lower each arm with that arm's block current and terminate it with a jump to the join, then make the join current.
For a while: create condition, body and exit blocks, terminate the current block with a jump to the condition, lower the condition and terminate with a branch to body or exit, lower the body and terminate with a jump back to the condition, then make the exit current.
Terminate every block exactly once; ignore further terminators for a block already terminated, since code after a return is unreachable.
Recompute predecessor and successor lists from the terminators once the function is complete, collapsing a branch whose targets are equal into a single edge.
Delete blocks the entry cannot reach, because dominance assumes every block has a dominator.
Split any critical edge before placing edge-specific code on it, or detect and report the ones you do not split.

How it breaks

What the engineer observes when it goes wrong — not what goes wrong internally.

A while is lowered entering at the body, and a loop that should not run at all runs once. The symptom is an off-by-one in a result computed elsewhere, with nothing pointing at the loop.
The back edge points at the body instead of the condition, and the program hangs — which is at least easy to notice, unlike the previous case.
A predecessor list is not updated after a terminator is rewritten, and dominance is computed over a graph that no longer matches the code. Every dependent analysis is silently wrong and nothing crashes.
A branch with two identical targets produces two edges, and a phi node in the target is given two operands for one arrival. The out-of-SSA pass emits two copies on one edge and the second overwrites the first.
Copies are placed across an unsplit critical edge, and a value is clobbered on the path that did not need it. The program is correct until a later pass makes that path read the value.
An unreachable block survives lowering, dominance has nothing to give it, and any analysis that consults dominance for that block gets a meaningless answer.

When it helps

Reading a lowering implementation. Every compiler's if and while lowering has this shape, and recognising it makes an unfamiliar frontend readable in minutes.
Debugging a control-flow bug. Comparing the CFG dump against the source construct localises a lowering fault immediately, and lowering faults are otherwise very hard to attribute.
Understanding why phi resolution and edge splitting exist. Both are consequences of the graph shape that construction produces, not arbitrary extra machinery.

When it hurts

When the language has unstructured control flow. goto into the middle of a loop, computed jumps and irreducible graphs all break the tidy recursive construction, and the analyses that assume reducibility need fallbacks.
When the graph must be turned back into structured form, as when targeting WebAssembly. Restructuring an arbitrary CFG into nested blocks and loops needs a real algorithm and sometimes introduces extra branching — [[wasm-model]].

What it costs

Every one of these is paid by something.

Recomputing edges from terminators buys a graph that cannot drift out of sync and pays a linear pass every time, rather than the constant-time incremental update a hand-maintained list would give.
Splitting critical edges buys correct phi resolution everywhere and pays with extra blocks and jumps, most of which the backend removes but all of which every intermediate pass must traverse.
Creating a join block for every if whether or not anything reaches it buys a uniform construction with no special cases, and pays with orphan blocks that a pruning pass then has to remove.
Keeping labels such as while.cond on blocks buys readable dumps and pays with metadata every transformation must decide whether to preserve — and that is silently misleading when a pass does not.

What else you could do

What a different compiler or language does instead, and when that is better.

Build the graph from a flat instruction list by finding leaders, rather than from the tree during lowering. This is what a disassembler or a binary analysis tool must do, since it has no tree — and it is strictly harder, because indirect jump targets must be inferred.
Use block parameters instead of phi nodes, as Cranelift, Swift SIL and MLIR do. The critical-edge problem disappears because the value travels on the jump rather than living on the edge.
Require the IR to have no critical edges as an invariant, splitting them at construction. Phi resolution becomes trivial at the cost of more blocks everywhere, and every pass must maintain the invariant.
Do not build a graph: structured-only representations such as WebAssembly bytecode keep the nesting, which makes some analyses harder and makes validation much easier.

See it for yourself

The flag, dump or tool that shows you this directly.

rustc --emit=mir prints MIR with explicit bb0: blocks and terminators, which is the clearest published example of a lowering's output.
opt -passes=dot-cfg file.ll renders the graph; compare the picture with the source to see exactly which construct produced which blocks.
opt -passes=break-crit-edges -S file.ll runs LLVM's critical-edge splitter and prints the result, so you can diff the before and after and count the inserted blocks.
GOSSAFUNC=Fname go build writes ssa.html showing the Go CFG at every pass, including the early lowering that creates the blocks.
Our CFG viewer at /compilers/cfg builds the AtlasLang graph live and marks the back edge; an if with no else shows the critical edge the out-of-SSA pass reports.

Plausible wrong readings

Stated the way a confident engineer states them.

"The join block exists because the source had a statement after the if." It exists because control has to come back together. AtlasLang creates a join for every if whether or not anything follows, and prunes it later if nothing reaches it.
"A back edge is an edge that goes upward in the listing." It is an edge whose target dominates its source. Block ordering in a listing is a printing convention and can be changed without changing the graph.
"Critical edges are rare." Every if without an else produces one, and so does every short-circuit && or ||. They are among the most common shapes in real code.
"Splitting an edge changes the program." It inserts a block containing a jump, executing on exactly the paths the edge did. It is one of the few transformations that is unconditionally safe.

Misconceptions

The claim, and what is actually true.

The CFG is built once and then stays fixed.

Nearly every optimization changes it. Blocks are merged, split, deleted and created throughout the pipeline, and the edge lists and dominance information are invalidated and recomputed constantly.

A critical edge is a bug in the construction.

It is a normal shape produced by ordinary code. An if without an else produces one every time. The bug is placing edge code on it without splitting.

Zero-iteration loops are an edge case.

They are the reason the entry jumps to the condition rather than the body, and getting that wrong is one of the most common lowering mistakes in a hand-written frontend.

Go deeper

The same idea at increasing depth. Stop wherever it stops being useful.

overview

The compiler walks the tree keeping track of which block it is currently filling. An if makes three blocks — two arms and a place where they rejoin — and a branch between them. A while makes three blocks and an edge that points backwards from the body to the test. After that walk, the if and the while are gone, and only blocks and arrows remain.

practical

Two mistakes account for most hand-written lowering bugs. First, entering the loop at the body rather than the condition, which turns while into do/while and shows up as an off-by-one somewhere else entirely. Second, updating a terminator without updating the edge lists, which leaves dominance computed over a graph that no longer exists. Both are prevented by discipline rather than cleverness: jump to the condition, and recompute the edges from the terminators after any change rather than patching them.

advanced

The critical edge is the clearest example in this domain of a problem created entirely by a representation choice. Phi nodes place a value at a merge, but the value logically belongs to an *edge*, and edges are not places you can put instructions. Every solution follows from where you decide the value lives: split the edge so it becomes a place, use block parameters so the value rides the jump, or forbid critical edges as an IR invariant. LLVM chose the first, Cranelift the second, and various research IRs the third. Once you see phi nodes as an encoding rather than as a primitive, the whole family of phi-related bugs — the swap problem, the critical edge, phi arity — reads as consequences of that one encoding decision.

How much this depends on

Nothing in this domain is true of every compiler. These say how much.

simplifiedAtlasLang has no break, continue, goto or exceptions, so its construction needs no exit-edge bookkeeping. In a real compiler that is most of the work: break is an edge to the exit block from arbitrary nesting depth, continue is an edge to the condition, and an early return or a panic must run pending destructors on the way out. That is why loop lowering in rustc or Clang is hundreds of lines rather than twenty.

typicalThe block-per-construct shape described here is what mainstream frontends produce, though the exact block count varies: some create a join block only when something reaches it, some merge single-successor blocks eagerly, and some emit an explicit exit block per function. The edges are the same in all of them; the block count is not comparable across compilers.

implementationLLVM provides BreakCriticalEdges as a utility pass that other passes declare as a prerequisite, so in an LLVM pipeline critical edges are typically already gone by the time phi resolution runs. Cranelift never has the problem because block parameters put the value on the jump. AtlasLang reports rather than splitting, which is a third answer suited to showing the problem rather than hiding it.

If you were asked this in an interview

Lower a while loop into blocks and edges. Which edge decides whether it is a while or a do/while?
What is a critical edge, and what breaks if you place a copy on one without splitting it?
Why should predecessor lists be recomputed rather than maintained incrementally?

Connections

DSAdirected-graph dfs cycle-detection adjacency-list

Domains that do not exist yet

Programming Languages & Runtime Internals — Destructor and cleanup ordering on abrupt exit paths
The hard part of real CFG construction is the exit edges — break, early return, exception, panic — and what must run on each. The compiler builds the edges; the runtime semantics that decide what belongs on them are owned there.