Skip to content
Tutorials Center
My learning

Topics

Lesson 35 of 61 ยท Intermediate Code and Optimization

Basic Blocks and Control Flow Graphs

Learn how compilers split three-address code into basic blocks, build a control flow graph, find dominators and loops, with runnable Python code.

Three-address code is a flat list of instructions with jumps in the middle. That is easy to generate, but hard to reason about: to know what can happen after instruction 7, you have to follow jumps by hand. Optimizers need a better picture. They want to ask, "Which pieces of code always run together? Which can run next? Is this piece inside a loop?" The answer is the control flow graph (CFG): a graph whose nodes are chunks of straight-line code and whose edges are the possible jumps between them.

In this lesson you will cut the TAC from the previous lesson into basic blocks, wire them into a CFG, compute dominators, and find the loops. All the code runs here, and the loop example is the same one you generated before.

Basic blocks

A basic block is a maximal sequence of instructions that always executes from first to last: control can enter only at the first instruction, and leave only at the last one. Inside a block there are no jumps in and no jumps out (except possibly at the end), so you can analyze the block as one unit. Many optimizations are easy within a block, because the order of execution is known (see local optimizations).

To find the blocks you only need to find where each block begins. Those instructions are called leaders, and three rules identify them:

  1. The first instruction of the program is a leader.
  2. Any instruction that is the target of a jump (a labelled instruction) is a leader.
  3. Any instruction that follows a jump is a leader.

Each block then runs from one leader up to (but not including) the next one. Rule 2 says control may arrive from elsewhere, so a new block must start there. Rule 3 says that after a jump, whether control falls through or goes elsewhere, we may be in a different situation, so a new block starts.

The control flow graph

The CFG has one node per basic block, and an edge A -> B when control can pass from the end of A to the start of B. Looking at the last instruction of block A decides its outgoing edges:

Last instruction of the block Edges
goto L one edge to the block that starts at L
if cond goto L two edges: to the block at L, and to the next block (fall through)
anything else one edge to the next block
(last block of the program) none, it is an exit

The first block is the entry. Blocks with an edge into a block are its predecessors; blocks it points to are its successors.

Building a CFG in Python

The code below follows the three rules, cuts the program into blocks, and prints each block together with its successors. The program is the loop from the last lesson after tidying (it adds up a few numbers).

Python Leaders, basic blocks and edges

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The 19 lines became nine blocks. B1 is just the label and a jump (the loop test i > 10), because every conditional jump ends a block. B4 is a single test, if i != 7 goto L6, which can fall into B5 or jump to B6. B6 holds only a label: it exists because L6 is a jump target (rule 2). B7 is where the two branches of the if meet again, and its goto L1 is the edge that closes the loop. B8 has no successors, so it is the exit. Here is the same graph as a picture:

flowchart TB
    B0["B0: i = 1, total = 0"] --> B1
    B1["B1: if i > 10"] -->|"jump"| B8["B8: print total"]
    B1 --> B2["B2: if total > 20"]
    B2 -->|"jump"| B8
    B2 --> B3["B3: t1 = i % 2<br/>if t1 == 0"]
    B3 -->|"jump"| B5["B5: total = total + i"]
    B3 --> B4["B4: if i != 7"]
    B4 -->|"jump"| B6["B6: (empty)"]
    B4 --> B5
    B5 --> B7["B7: i = i + 1<br/>goto L1"]
    B6 --> B7
    B7 --> B1

The loop is visible at a glance: B1 through B7 form a cycle, and B8 is the way out.

Dominators

Edges tell us what can happen next. Dominators tell us what must have happened before. A block D dominates a block N if every path from the entry to N goes through D. Every block dominates itself, and the entry dominates everything.

Dominators are computed by a small fixed-point algorithm:

  • dom(entry) = {entry}.
  • For every other block N: dom(N) = {N} together with the intersection of dom(P) over all predecessors P of N.
  • Repeat until nothing changes. (Start every other block with "dominated by everyone", and the sets shrink to the right answer.)

The intuition: anything that dominates all of N's predecessors also lies on every path to N. Dominance is the basis for SSA construction and for deciding when it is safe to move code, as in loop optimizations.

Finding loops

The CFG shows the loops, but the compiler needs a definition it can compute. A back edge is an edge N -> H where H dominates N: a jump back to a block that is guaranteed to have run before. H is the loop header. The natural loop of the back edge is H plus every block that can reach N without passing through H: you collect them by walking predecessors backwards from N, stopping at H.

The next example does all of it: it computes dominators for the loop program, reports the back edge and its natural loop, and then shows another use of the CFG, finding unreachable code (blocks no path from the entry can reach), which an optimizer can delete.

Python Dominators, back edges, loops and dead blocks

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Look at dom(B5): it is B0, B1, B2, B3, B5. B4 is not in it, because B5 can be reached from B3 directly (when t1 == 0), without going through B4. By contrast dom(B7) contains B3 but neither B4, B5 nor B6: both branches of the if lead to B7, so neither branch is mandatory. The only back edge is B7 -> B1, because B1 dominates B7, and its natural loop is all of B1 to B7. B8 is outside the loop: it is the exit. B1 is the only way into the loop, which is what makes this loop reducible (structured) and easy to optimize.

The second program has code after an unconditional goto. No edge leads to B1, so the reachability walk never visits it, and it is flagged as unreachable. One caveat: dominators as written assumes every block is reachable (an unreachable block has no predecessors, and the intersection would be of nothing), so a real compiler deletes unreachable blocks first.

Compilers that read unstructured code (such as goto-heavy C) can meet loops with several entry points, called irreducible loops. They have no single header and no clean natural-loop form, so many loop optimizations skip them. Structured while and for loops always give reducible CFGs.

What the CFG is used for

The CFG is the backbone of the optimizer. You will use it in the rest of this chapter.

  • Local optimizations work inside one block at a time.
  • Data-flow analysis passes information along the edges until nothing changes (data-flow analysis).
  • SSA construction needs dominators to place phi functions.
  • Loop optimizations need the loops and their headers.
  • Dead code elimination removes unreachable blocks, and branch simplification merges a block with its only successor.
  • Register allocation and instruction scheduling work on blocks and their order.

Real compilers keep, for every block, lists of both predecessors and successors, because analyses run forwards as well as backwards.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Which of these instructions is a leader of a new basic block?

    The three leader rules are: the first instruction, any jump target, and any instruction that follows a jump. A plain assignment in the middle of a run starts nothing new.
  2. 2. A basic block ends with if x < y goto L. How many outgoing edges does it have (assuming L is not the next block)?

    A conditional jump can either jump (edge to the target block) or fall through (edge to the following block).
  3. 3. What does it mean that block D dominates block N?

    Dominance is about all paths from the entry. D must be on every one of them, though not necessarily right before N.
  4. 4. How is a back edge defined?

    A jump back to a block that is guaranteed to have already run means we are going around a loop. H is its header.

Summary

  • A basic block is a straight run of instructions entered only at the top and left only at the bottom; leaders (first instruction, jump targets, instructions after jumps) mark where blocks begin.
  • The control flow graph has blocks as nodes and possible jumps and fall-throughs as edges.
  • Block A dominates B if every path from the entry to B goes through A; dominators come from a simple intersection-until-stable algorithm.
  • A back edge goes to a dominating block; the loop it closes is that header plus everything that can reach the edge's tail without passing the header.
  • The CFG also reveals unreachable code, and it is the structure that data-flow analysis, SSA and loop optimizations work on.

Next: Local Optimizations