CFGtypical

Basic Blocks

A maximal run of instructions with one way in and one way out. If the first instruction executes, all of them do — and that single guarantee is what makes the block, rather than the instruction, the unit every analysis is written against.

The question

What exactly makes a group of instructions a basic block, and why is that the unit compilers analyse?

Source→Lexing→Tokens→Parsing→AST→Semantics→Typed→IR→Optimize→Codegen→Machine code→Link→Execute
What the program is here

A maximal sequence of instructions such that control enters only at the first and leaves only after the last. The block is the unit at which "did this execute" has a single answer for every instruction inside it, which is what it exists to provide: an analysis can summarise the whole block as one transfer function and reason about the graph instead of the instruction list.

What this phase may assume or do

Treating a sequence as one block is valid only if nothing in the middle can be jumped to and nothing in the middle can transfer control elsewhere. The second clause is the one that catches people: a call that cannot return — because it throws, aborts or diverges — ends a block, and in a language with exceptions any call at all may end one, because a handler edge leaves from the middle of what looked like straight-line code.

Key points

  • A basic block is a maximal instruction sequence entered only at the first instruction and left only after the last.
  • If the first instruction runs, every instruction in the block runs — that single guarantee is the reason the block is the unit of analysis.
  • Blocks end at branches and jumps, before labels, and at any call that may not return to the following instruction.
  • Inside a block dataflow facts flow straight through with no merging, so the whole block collapses to one transfer function and the fixed-point problem shrinks to the block graph.
  • In a language with exceptions, a call that may throw is a terminator, not an ordinary instruction — which is why LLVM has both call and invoke.

One entry, one exit, all or nothing

The defining property is a guarantee about execution: if the first instruction of a block runs, every instruction in that block runs, in order, exactly once, before control leaves. Nothing can jump into the middle, because block boundaries are placed at every jump target. Nothing can leave from the middle, because block boundaries are placed after every instruction from which control can go somewhere other than the next one.

A block ends at three kinds of thing. It ends at a branch or jump, because control diverges. It ends before a label — an instruction that is the target of some jump — because control can arrive there without having come through the instruction above. And it ends at a call that cannot return: a call to a diverging function, a call that throws in a language with exceptions, an abort. The last case is the one most often forgotten, and forgetting it produces a block whose "all or nothing" guarantee is false.

"Maximal" matters too. Any sequence with one entry and one exit is *a* block; the basic block is the largest such sequence at that point. Splitting a block unnecessarily costs nothing semantically and costs analysis efficiency — more nodes, more edges, more meet operations at every fixed-point iteration.

Four blocks, and why each boundary is where it is
  1. b0entryentry
    store @x, 0
store @c, 7
%0 = load @c
%1 = bool %0 > 3
branch %1 ? b1 : b2
    Ends at the branch: control diverges here, so nothing after it belongs to this block.
  2. b1if.then
    store @x, 1
jump b2
    Starts here because `b0` can jump here — it is a label, and control can arrive without passing through the instruction above it in the listing.
  3. b2if.join
    %2 = load @x
print %2
ret
    Two predecessors, so it must be its own block. Both `b0` and `b1` can arrive here, and neither can be assumed.
Edges
  • b0→b1true
  • b0→b2false
  • b1→b2

Read it asThis is AtlasLang's real output for let x = 0; let c = 7; if (c > 3) { x = 1; } print(x);. Note that the if with no else still produces a join block with two predecessors — the false edge goes straight there. That two-predecessor block is the reason [[dominance-frontier]] has anything to say about this program.

Why the block and not the instruction

Every dataflow analysis could in principle work instruction by instruction. It does not, and the reason is that inside a block there is no choice to make. Facts flow straight through: the fact after instruction *n* is a function of the fact before it, with no merging, no branching, no uncertainty. A whole block can therefore be summarised as one composed transfer function, computed once, and the iterative part of the analysis runs over blocks rather than instructions.

That reduces the size of the fixed-point problem by roughly the average block length — often five to fifteen instructions in real code — which is the difference between an analysis that is practical on a large function and one that is not. [[data-flow-framework]] is written in exactly these terms: a transfer function per block and a meet operator at every point with more than one predecessor.

The other reason is that merge points are where the interesting things happen, and merge points are block boundaries by construction. A block with two predecessors is where two values may arrive, which is where a phi node goes; a block with two successors is where a value may be needed on one path and not the other. Making blocks the nodes puts every one of those decisions on a node boundary rather than in the middle of a sequence.

The call that ends a block

implementationLLVM distinguishes call (an ordinary instruction) from invoke (a terminator with normal and unwind successors), so C++ code compiled with exceptions enabled has substantially more blocks than the same code with -fno-exceptions. GCC represents the same thing differently, with exception regions attached to statements rather than by splitting blocks in the same way. The concept — a call that can leave a block early is a block boundary — holds in both; the representation does not transfer.

In a language without exceptions, a call is an ordinary instruction: control goes away and comes back, and the instructions after it run. In a language with exceptions, that is false for every call whose callee might throw — control may leave from that point and never return to the next instruction. So the block ends there, and there is an edge to the handler.

This is why the same function compiled as C and as C++ can have very different block counts, and why LLVM has two call instructions: call, which is an ordinary instruction inside a block, and invoke, which is a *terminator* with two successors — the normal continuation and the exception landing pad. The difference is not a detail of exception handling; it is the difference between an instruction and a block boundary, and every analysis sees it.

The same logic applies to any instruction from which control might not continue: a call to a noreturn function, an explicit trap, an infinite loop the compiler can prove diverges. Getting this wrong means an optimizer believes code after the call is reachable, and it may hoist work into a place that never executes — usually harmless, occasionally not, and always confusing when it appears in a profile.

How it works

The steps, in the order the compiler takes them.

  • Scan the instruction list and mark every leader: the first instruction, every jump or branch target, and every instruction immediately after a terminator.
  • Each block runs from one leader up to and including the instruction before the next leader.
  • Treat any call that may not return normally as a terminator, adding an edge to its handler or none at all if control cannot continue.
  • Record the block's successors from its terminator; derive predecessors by inverting.
  • Merge a block with its single predecessor when that predecessor has exactly one successor, since the split buys nothing and costs an edge.

How it breaks

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

  • A block boundary is missed at a jump target, so control can arrive in the middle of a block. Analyses conclude that earlier instructions in the block have run when they have not, and a value is read before anything wrote it on that path.
  • A call that can throw is treated as an ordinary instruction, and an optimizer moves a store past it. On the exception path the handler observes state that could not exist in the source program — and every test that does not throw passes.
  • Blocks are split more finely than necessary, and compile time on large functions rises noticeably because every dataflow iteration now has many more nodes to visit.
  • A block is merged with its predecessor when the predecessor had another successor, silently placing instructions on a path that should not execute them.

When it helps

  • Reading a dump: the block boundaries tell you where the control-flow decisions are, so scanning terminators first gives the shape of the function in seconds.
  • Reasoning about instruction scheduling and peephole optimization, both of which are typically block-local because the "all or nothing" guarantee is what makes local reasoning sound.
  • Understanding why a transformation stopped at a boundary. Most local optimizations are block-scoped by construction, and "it did not fire because there was a branch in the middle" is a common and correct answer.

When it hurts

  • When the optimization you want spans blocks. Block-local reasoning is sound and limited, and everything global — code motion, global value numbering, register allocation — needs the graph and the dataflow machinery on top of it.
  • In code with very short blocks. Heavily branchy code has blocks of one or two instructions, at which point the analysis-efficiency argument for blocks largely evaporates and the overhead per block starts to dominate.

What it costs

Every one of these is paid by something.

  • Blocks buy a smaller fixed-point problem and a place to put merge decisions, and pay with a second structure to maintain: block boundaries must be recomputed or repaired after any transformation that changes a terminator.
  • Maximal blocks buy analysis efficiency and pay in transformation freedom, because splitting a block is sometimes exactly what a later pass needs — which is why edge splitting is a routine transformation rather than a violation.
  • Treating throwing calls as terminators buys correctness on exception paths and pays with a substantially larger graph: the same C++ function has far more blocks with exceptions enabled than without.

What else you could do

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

  • Extended basic blocks — a tree of blocks with a single entry but several exits — give some of the analysis benefit over a larger region, and are used for scheduling in some backends where a longer straight-line window is worth the complication.
  • Traces or superblocks, which are hot paths through several blocks with side exits, used in trace-based JITs and in some scheduling work. They buy a longer optimization window on the common path and pay with duplicated code on the cold ones.
  • Instruction-level analysis with no blocks at all, which is what sea-of-nodes does: there is nothing to enter or leave until the scheduler builds blocks at the end — [[ir-design-tradeoffs]].
  • No blocks because no CFG: an AST interpreter never forms them, and correspondingly never gets any analysis that depends on them.

See it for yourself

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

  • rustc --emit=mir labels every block bb0:, bb1: and prints its terminator on the last line, which makes leaders and boundaries explicit.
  • clang -S -emit-llvm -o - shows LLVM basic blocks as labelled regions; compile the same file with and without -fno-exceptions and count blocks to see the invoke effect.
  • opt -passes=dot-cfg-only file.ll renders the block graph with the instructions stripped, which is the fastest way to see the shape alone.
  • objdump -d --visualize-jumps on a compiled binary draws jump targets in the disassembly, which is block structure surviving into machine code.

Plausible wrong readings

Stated the way a confident engineer states them.

  • "A basic block is a source statement." A statement with a short-circuit operator or a conditional expression spans several blocks, and a run of simple statements is one block. There is no correspondence.
  • "A block always ends at a call." Only when the call may not return to the next instruction. In a language without exceptions, an ordinary call sits comfortably in the middle of a block.
  • "Fewer blocks is faster code." Block count is a property of the compiler's representation. Splitting a block emits no instructions and changes nothing about what runs.
  • "Blocks are the same thing as scopes." Scopes are lexical and nest; blocks are execution regions and form a graph. A single scope routinely contains dozens of blocks — [[lexical-scope]].

Misconceptions

The claim, and what is actually true.

A block with one instruction is a mistake.
It is common and correct. A loop header that only branches, or an edge-splitting block inserted to solve the critical-edge problem, is legitimately one instruction long.
Instructions in a block execute atomically.
They execute in order with nothing jumping in or out, which is a control-flow guarantee, not an atomicity one. Another thread can observe intermediate states, and a signal can arrive mid-block — [[data-races]] in Concurrency is where that story lives.

Go deeper

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

overview

A basic block is a run of instructions with no way in except at the top and no way out except at the bottom. If the first one runs, they all run. Compilers analyse blocks rather than individual instructions because that guarantee means there are no decisions to make inside a block — all the decisions are at the boundaries.

practical

When you read an IR dump, the block headers and the last line of each block are the whole story. The instructions in between are straight-line code you can read later. If a transformation you expected did not happen, check whether it was block-local: a great many peephole and scheduling transformations simply do not cross a boundary, and a branch in the middle of what you thought was straight-line code is the usual explanation.

advanced

The block abstraction leaks in exactly one place that matters, and it is worth internalising: the "all or nothing" guarantee is about control flow, not about observability. Another thread or a signal handler can observe the middle of a block, which is why a compiler may not introduce a store that the source did not have, even inside a block where it appears unobservable. This is the compiler-side of what the language memory model forbids, and it is the reason a seemingly local optimization can be illegal for reasons that live entirely outside the function — [[memory-model]] in Concurrency owns the other half.

How much this depends on

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

typicalThe leader-based construction described here is what LLVM, GCC, Go and rustc all do, with variations in whether a single-successor block is eagerly merged with its predecessor. Compilers targeting structured control flow, such as those emitting WebAssembly, must additionally restructure the resulting graph back into nested regions.
implementationWhether a call ends a block depends on the language and the build configuration, not on the compiler alone. The same C++ source compiled with -fno-exceptions produces ordinary call instructions inside blocks and with exceptions enabled produces invoke terminators that end them.

If you were asked this in an interview

  • Define a basic block, then tell me three things that end one.
  • Why is the block rather than the instruction the unit of dataflow analysis?
  • Why does LLVM have both call and invoke?

Connections

DSAdirected-graphadjacency-list
Computer Architecturebranch-predictioninstruction-cache
Concurrencymemory-modeldata-races
Domains that do not exist yet
  • Programming Languages & Runtime Internals — What a running thread can observe between two instructions
    The block guarantee is about control flow only. What another thread or a signal handler can see mid-block is a runtime and memory-model question, and it constrains what the compiler may legally do inside a block.