CFGtypical

The Control-Flow Graph

Once the statements are instructions, the `if` is gone. What remains is a directed graph: blocks of straight-line code as nodes, the ways control can pass between them as edges. Every question about "when does this run" becomes a question about paths.

The question

What is a control-flow graph, and what can I ask of it that I could not ask of the source?

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

What the program is here

A directed graph whose nodes are basic blocks — maximal straight-line instruction sequences — and whose edges are the transfers of control a terminator can make. There is one distinguished entry node. It exists to answer questions of the form on which paths does this happen: is this code reachable, does this value reach that use, is this block always executed before that one. Source text can express nesting; it cannot express paths, because two textually distant blocks may be adjacent in the graph and two adjacent lines may be on different paths.

What this phase may assume or do

The graph builder is entitled to assume the IR is structurally well-formed: every block ends in exactly one terminator, every terminator names targets that exist, and every block other than the entry is reachable from the entry. That last assumption is not free — AtlasLang enforces it by dropping unreachable blocks after lowering, because dominance is undefined for a block the entry cannot reach and every analysis downstream would inherit that undefined result.

Key points

A CFG is a directed graph of basic blocks connected by the transfers of control a terminator can make, with one distinguished entry.
It replaces syntactic nesting with connectivity, which turns "when does this run" into a question about paths.
Reachability, definite assignment, liveness and loop detection are all graph questions with no formulation over the source.
Structured loops, goto loops and lowered tail recursion all produce the same graph shape, which is why the analyses are uniform.
The graph is cyclic whenever there is a loop, so analyses over it iterate to a fixed point or work over an acyclic derived structure.

From nesting to paths

Take the simplest branching program: a condition, two arms, and a statement afterwards. In source it is nested — the arms are *inside* the if, and the statement after is a sibling. That nesting is a description of syntax and it says nothing directly about execution.

In the graph it is flat. Four nodes: the block that evaluates the condition and branches, the two arms, and the block they both reach. The nesting has become two outgoing edges from one node and two incoming edges into another, and the whole structure of the program is now visible as connectivity.

The gain is that questions become graph questions with known answers. Reachability is [[dfs]] from the entry. "Does this block always run" is a dominance question. "Is this a loop" is a question about an edge pointing backwards. None of those have a formulation over the syntax tree, which is why every middle-end analysis is written against the graph and not against the source.

AtlasLang CFG for if (c > 0) { print(1); } else { print(2); } print(3); — verbatim engine output

b0entryentry
```
store @c, 1
%0 = load @c
%1 = bool %0 > 0
branch %1 ? b1 : b2
```
One entry, one exit, and the exit is a two-way branch. Everything before the branch is straight-line code that either all runs or none of it does.
b1if.then
```
print 1
jump b3
```
b2if.else
```
print 2
jump b3
```
b3if.join
```
print 3
ret
```
Two predecessors. This is a merge point, and merge points are where every interesting thing in this module happens.

Edges

b0→b1true
b0→b2false
b1→b3
b2→b3

Read it asThe if does not appear anywhere. It has become the branch terminator in b0 and the two edges out of it, and the else has become the second edge rather than a keyword. b3 exists because control has to come back together somewhere, and the two arrows into it are the reason [[phi-functions]] exist at all.

What the graph makes askable

The graph is a data structure this domain shares with DSA, and the algorithms are the ones from there — depth-first search, reachability, cycle detection, topological order on the acyclic parts. What differs is what the nodes mean and therefore which questions are worth asking.

Reachability. A block no path from the entry reaches is dead: its instructions can be deleted whether or not they have side effects, because no execution reaches them. This is the cheapest optimization in any compiler and it falls straight out of a graph traversal.

Path questions. "Is x definitely assigned before this use" is a question about every path from the entry to the use. "Is this value used on any path after this point" is liveness, running backwards. Both are [[data-flow-framework]] instances and both are stated over the graph.

Loops. A back edge — an edge whose target dominates its source — identifies a loop, and the loop body is recovered from the graph rather than from the source construct that produced it. That is [[natural-loops]], and it exists precisely because lowering destroyed the while.

The same question, over the source and over the graphtypical

Question	Over source text	Over the CFG
Is this code reachable?	Approximate, syntactic — "there is no `return` above it"	Exact: is there a path from the entry
Is this variable assigned on every path here?	Not expressible without simulating control flow	A forward dataflow problem with a meet over predecessors
Is this a loop?	Only if the loop keyword survived; a `goto` loop is invisible	An edge whose target dominates its source
Does A always run before B?	Not expressible — textual order is not execution order	Does A dominate B

The graph is not the source, and does not want to be

simplifiedAtlasLang CFGs have one entry and no exception edges, so every edge is an ordinary branch or jump. Real CFGs for languages with exceptions have edges from any instruction that can throw to its handler, which means a "straight-line" block is only straight-line if nothing in it can throw — and that assumption is why C++ CFGs from Clang contain invoke terminators rather than call instructions. Add exceptions and the block count roughly doubles.

A structured while, a for, a goto loop and a tail-recursive function that a compiler turned into a loop all produce the same shape of graph. That is a feature: the analyses work identically on all four, and a language with goto gets the same optimizations as one without.

It is also the cost. Once the graph is built, the compiler cannot say "your for loop never executes" in the author's words unless it kept a link back. AtlasLang keeps the original construct as a *label* on each block — while.cond, if.join, and.rhs — and those labels are read by nothing in the compiler. They exist so the CFG viewer can tell you where a block came from. That is a deliberately minimal substitute for a high-level IR, and it is exactly as much provenance as a teaching compiler needs and much less than a real one keeps.

The other thing the graph is not is a tree. It has cycles the moment there is a loop, which is why every analysis over it must either iterate to a fixed point or work over an acyclic derived structure like the dominator tree. [[fixed-point-iteration]] is the general shape of the first, and [[dominator-tree]] is the second.

How it works

The steps, in the order the compiler takes them.

Walk the instruction sequence and start a new block at every entry point: the function entry, every branch or jump target, and the instruction after every terminator.
End a block at every terminator — a branch, a jump, a return, or any instruction from which control cannot continue to the next one.
Record each block's successors from its terminator, and derive predecessors by inverting that relation rather than maintaining both by hand.
Mark every block reachable from the entry by traversal, and delete the rest, since analyses that assume every block has a dominator break on the ones that do not.
Recompute the edge lists after any transformation that changes a terminator, rather than patching them incrementally.

How it breaks

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

The predecessor lists drift out of sync with the terminators after a transformation, and dominance is computed over a graph that does not match the code. Everything downstream is silently wrong, and nothing crashes.
A block is left without a terminator, and code generation falls through into whatever block was emitted next. The program works until an unrelated change reorders the blocks, at which point it fails in a way that looks unrelated to the change.
An unreachable block survives into the dominance computation, which has no dominator to give it, and every analysis that consults dominance for that block gets a meaningless answer.
An exception edge is missing, and an optimizer moves a store past an instruction that can throw. The state visible in the handler is wrong, and only on the exceptional path — so every non-throwing test passes.

When it helps

Reading any compiler dump above the frontend. Nearly every mid-level IR listing is a CFG in textual form, and reading it as a graph rather than as a listing is the whole skill.
Reasoning about why an optimization did or did not fire. Most answers are "there was a path you did not think about" or "there was an edge the pass could not prove absent".
Understanding coverage tooling, which is a CFG analysis wearing a different hat: branch coverage is edge coverage on this graph.

When it hurts

When the question is about the source rather than about execution. A lint that wants to say something about the for loop the author wrote must run before the graph exists.
For very large functions, where the graph is large enough that quadratic analyses become the compile-time bottleneck — machine-generated code with thousands of blocks is where compilers actually fall over.

What it costs

Every one of these is paid by something.

The graph buys exact path reasoning and pays with the loss of source structure — a for, a while and a goto loop are now indistinguishable, so anything the author's construct would have told a diagnostic is gone.
It buys uniform analyses across every control construct and pays compile time and memory: an explicit block-and-edge structure per function, rebuilt or repaired after every transformation that touches a terminator.
Keeping provenance labels on blocks buys readable dumps and pays with metadata that every transformation must decide whether to preserve, and that is silently wrong when it does not.

What else you could do

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

Structured control flow only — no arbitrary graph, just nested regions. WebAssembly took this route: its control flow is block, loop and if with structured branches, so a compiler targeting it must *restructure* an arbitrary CFG back into nested form, which is a real and sometimes lossy transformation — [[wasm-model]].
A program dependence graph, which combines control and data dependencies into one structure and is the natural representation for slicing and for some parallelisation work, at the cost of being much harder to print and to reason about locally.
Sea-of-nodes, which has no basic blocks at all until a scheduling pass creates them — the maximal version of "the graph is the program" — see [[ir-design-tradeoffs]].
No graph at all: an AST interpreter simply executes the nesting, which is why it needs none of this machinery and gets none of these optimizations — [[tree-walk-interpreter]].

See it for yourself

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

opt -passes=dot-cfg file.ll writes a Graphviz .dot file per function; dot -Tpng renders it. -passes=dot-cfg-only omits the instructions and shows the shape alone.
clang -Xclang -analyze -Xclang -analyzer-checker=debug.ViewCFG file.c prints the Clang frontend's CFG, including the exception edges that the plain IR listing makes easy to miss.
GOSSAFUNC=Fname go build writes ssa.html, which renders the Go CFG at every pass with blocks and edges drawn.
rustc --emit=mir prints MIR, in which each bb0:, bb1: heading is a basic block and each terminator names its successors explicitly.
Our CFG viewer at /compilers/cfg draws the AtlasLang graph for whatever you type, with the real block ids and labels the engine assigns.

Plausible wrong readings

Stated the way a confident engineer states them.

"The CFG shows the order the program runs in." It shows every order the program *could* run in. A single execution is one path through it, and which path depends on data the graph does not contain.
"Blocks correspond to source statements." Blocks correspond to straight-line runs of instructions. One source statement can span several blocks — any statement containing a short-circuit operator does — and one block can hold many statements.
"An edge means the target runs next." It means it may run next. A conditional branch has two edges out and takes exactly one of them per execution.
"The CFG is a DAG." It is a DAG only for a loop-free function. Loops make it cyclic, and that cyclicity is why dominance has to be computed iteratively.

Misconceptions

The claim, and what is actually true.

The CFG is built by the parser.

It is built during or after lowering, from the instruction sequence. The parser produces a tree, and the tree has no blocks in it.

Every function has one exit block.

Only if the representation requires it. A function with several return statements has several blocks ending in ret unless a pass merges them, and some representations require a single exit precisely so backward analyses have one place to start.

More blocks means slower code.

Block count is a property of the representation, not of the generated code. Splitting a block changes nothing about what executes, which is what makes edge splitting a safe fix for the critical-edge problem.

Go deeper

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

overview

After lowering, the program is a set of straight-line instruction sequences connected by arrows showing where control can go next. That is the control-flow graph. The if and the while are gone; what is left is which block can follow which, and almost every question a compiler asks — is this reachable, does this always run, is this a loop — is a question about that shape.

practical

When reading an IR dump, read the block headers and terminators first and ignore the instructions. Four blocks where one predecessor branches two ways and both arms rejoin is an if. A block whose predecessor list includes a block that appears later in the listing is a loop header, and the edge from that later block is the back edge. Getting fluent at seeing the shape through the text is what makes MIR, LLVM IR and Go SSA dumps readable rather than intimidating.

advanced

The subtle property of the CFG is that it is an over-approximation, and every analysis built on it inherits that. An edge means control *may* transfer, not that it will; a branch on a condition the compiler cannot evaluate has both edges even when one is dynamically impossible. This is what makes the analyses sound — they are conservative — and it is also the ceiling on their precision. Removing edges the compiler can prove impossible is where a great deal of optimization payoff lives, which is why constant propagation and CFG simplification are typically run together and repeatedly rather than once each.

How much this depends on

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

typicalOne entry per function and one graph per function is the mainstream arrangement — LLVM, GCC, Go and rustc all do this. Some representations use a single unified exit node, some allow several; interprocedural analyses build a supergraph across functions. The node-and-edge model is stable; the conventions around entry and exit are not.

simplifiedAtlasLang has no exceptions, no goto, no break and no continue, so every block has at most two successors and every edge comes from a branch or a jump. Real graphs have switch terminators with many successors, exception edges from any call, and indirect branches whose target set must itself be computed — [[control-flow-analysis]].

If you were asked this in an interview

Draw the CFG for an if/else followed by a statement, and tell me which block has more than one predecessor and why that matters.
What can you ask of a CFG that you cannot ask of an AST?
A function has an unreachable block. Why does that break dominance rather than merely wasting space?

Connections

DSAdirected-graph dfs adjacency-list cycle-detection

Computer Architecturebranch-prediction

Domains that do not exist yet

Testing & Reliability Engineering — Branch and path coverage as measures of test adequacy
Coverage instrumentation is a CFG transformation — a counter per edge — and the coverage numbers a test suite reports are statements about this graph. The measurement discipline is owned there.