Coursify

Basic Blocks and Control-Flow Graphs (CFGs) from Three-Address Code

Basic Blocks and Control-Flow Graphs (CFGs) from Three-Address Code

Verified Sources
Nov 4, 2026

In compiler design, a Basic Block is the fundamental unit used to build a Control-Flow Graph (CFG) for analysis and optimization. From a Three-Address Code (TAC) program (typically containing labels and conditional/unconditional jumps), we construct basic blocks by determining leaders, then connect those blocks via jump “targets” and fall-through edges to form the CFG.2

Mermaid view of the idea:

Key terms you will use repeatedly:

  • Leader
  • Successor
  • Predecessor
  • Fall-through

Footnotes

  1. Dragon Book (Compilers: Principles, Techniques, and Tools) basic blocks and CFG via leaders—CFG/data-flow foundations (Wikipedia page referencing the book). https://en.wikipedia.org/wiki/Dragon_book - Provides authoritative context for basic block and CFG concepts used in compiler optimization. ↩

  2. Basic block (compiler) overview and CFG terminology such as leaders, successors/predecessors. https://en.wikipedia.org/wiki/Basic_block - Defines basic blocks and relates them to CFG construction and control-flow structure. ↩

Basic Blocks and Control Flow Graphs (CFGs) Tutorial

Three-address code example (with labels)

Consider the following TAC fragment (labels are explicit control-flow anchors):

P0P_0:

  1. t1 := a < 0
  2. if t1 goto L1
  3. goto L2
  4. L1:
  5. t2 := b * 2
  6. goto L3
  7. L2:
  8. t2 := b + 1
  9. L3:
  10. t3 := t2 + c

This code has:

  • a conditional branch to L1,
  • an unconditional branch to L2,
  • and a join point at L3 where control converges.

The construction goal is:

  1. partition the TAC into basic blocks, and
  2. build a CFG whose nodes are those blocks and edges represent possible runtime transfers.2

Footnotes

  1. Dragon Book (Compilers: Principles, Techniques, and Tools) basic blocks and CFG via leaders—CFG/data-flow foundations (Wikipedia page referencing the book). https://en.wikipedia.org/wiki/Dragon_book - Provides authoritative context for basic block and CFG concepts used in compiler optimization. ↩

  2. Basic block (compiler) overview and CFG terminology such as leaders, successors/predecessors. https://en.wikipedia.org/wiki/Basic_block - Defines basic blocks and relates them to CFG construction and control-flow structure. ↩

Construct basic blocks using the leader rule

  1. 1
    Step 1

    Mark the first TAC statement as a leader. Also mark any statement that is the target of a jump (e.g., a label named by a goto or if ... goto). Finally, mark the statement immediately following any jump as a leader (the fall-through path after a jump).

  2. 2
    Step 2

    For each leader, extend its basic block forward until (but not including) the next leader. The result is a maximal straight-line sequence with no internal jumps that would enter from outside.

  3. 3
    Step 3

    Verify that every basic block has exactly one entry point (the leader) and that control cannot jump into the middle of a block from some other place in the TAC.

  4. 4
    Step 4

    For CFG edges, note that blocks are typically terminated by a conditional branch (if ... goto) or unconditional branch (goto). If a block reaches the end of the TAC or ends with no jump, it terminates by fall-through.

  5. 5
    Step 5

    Treat the leader containing the first statement as the CFG start block.

Apply leader rule to the example

We number statements 1–10 and identify jump targets/next-instruction leaders:

  • The first statement (1) is a leader.
  • if t1 goto L1 makes the statement at label L1: (statement 4) a leader.
  • goto L2 makes label L2: (statement 7) a leader.
  • goto L3 makes label L3: (statement 9) a leader.
  • Also, the statements immediately following jumps become leaders:
    • after statement 2 (if t1 goto L1), the next instruction (3) is a leader (fall-through to statement 3).
    • after statement 3 (goto L2), the next instruction (4) is already a leader (it is the fall-through position, though goto means it won’t execute, but the rule marks it anyway as a potential boundary).

Thus leaders are at statements: 1, 3, 4, 7, 9.

Now form maximal sequences until the next leader:

  • B0 (leader 1): statements 1–2
    • 1: t1 := a < 0
    • 2: if t1 goto L1
  • B1 (leader 3): statements 3
    • 3: goto L2
  • B2 (leader 4): statements 4–6
    • 4: L1:
    • 5: t2 := b * 2
    • 6: goto L3
  • B3 (leader 7): statements 7–8
    • 7: L2:
    • 8: t2 := b + 1
  • B4 (leader 9): statements 9–10
    • 9: L3:
    • 10: t3 := t2 + c

This partition yields basic blocks where control flows only at boundaries (leaders), not in the middle of blocks.2

Footnotes

  1. Dragon Book (Compilers: Principles, Techniques, and Tools) basic blocks and CFG via leaders—CFG/data-flow foundations (Wikipedia page referencing the book). https://en.wikipedia.org/wiki/Dragon_book - Provides authoritative context for basic block and CFG concepts used in compiler optimization. ↩

  2. Basic block (compiler) overview and CFG terminology such as leaders, successors/predecessors. https://en.wikipedia.org/wiki/Basic_block - Defines basic blocks and relates them to CFG construction and control-flow structure. ↩

CFG construction: edges via successors

Once basic blocks are identified, build the CFG:

  • If a block ends with a conditional jump if cond goto Lx, then it has:
    • one edge to the target block beginning at label Lx,
    • and one edge to the fall-through block (the block that starts at the next leader after the conditional).
  • If a block ends with an unconditional jump goto Lx, it has:
    • a single edge to the target block.
  • If a block ends without a jump, it falls through to the next block in program order.2

Footnotes

  1. Dragon Book (Compilers: Principles, Techniques, and Tools) basic blocks and CFG via leaders—CFG/data-flow foundations (Wikipedia page referencing the book). https://en.wikipedia.org/wiki/Dragon_book - Provides authoritative context for basic block and CFG concepts used in compiler optimization. ↩

  2. Basic block (compiler) overview and CFG terminology such as leaders, successors/predecessors. https://en.wikipedia.org/wiki/Basic_block - Defines basic blocks and relates them to CFG construction and control-flow structure. ↩

Build CFG edges for the example

  1. 1
    Step 1

    B0 ends at statement 2: if t1 goto L1. So add edges B0 -> B2 (target L1) and B0 -> B1 (fall-through to statement 3, leader of B1).

  2. 2
    Step 2

    B1 ends at statement 3: goto L2. Add edge B1 -> B3.

  3. 3
    Step 3

    B2 ends at statement 6: goto L3. Add edge B2 -> B4.

  4. 4
    Step 4

    B3 ends at statement 8 and the next labeled block is L3: at statement 9. Add edge B3 -> B4 via fall-through.

  5. 5
    Step 5

    B4 ends at statement 10 with no outgoing jump. If modeling program termination explicitly, it may have an implicit exit node; otherwise it has no successors.

CFG diagram (text + Mermaid)

Block mapping recap:

  • B0: statements 1–2
  • B1: statement 3
  • B2: statements 4–6
  • B3: statements 7–8
  • B4: statements 9–10

Edges:

  • B0 -> B2 (if branch taken)
  • B0 -> B1 (fall-through)
  • B1 -> B3 (goto L2)
  • B2 -> B4 (goto L3)
  • B3 -> B4 (fall-through)

Mermaid CFG:

This is the CFG representation used by classic analyses such as liveness analysis, data-flow frameworks, and many optimizations.2

Footnotes

  1. Dragon Book (Compilers: Principles, Techniques, and Tools) basic blocks and CFG via leaders—CFG/data-flow foundations (Wikipedia page referencing the book). https://en.wikipedia.org/wiki/Dragon_book - Provides authoritative context for basic block and CFG concepts used in compiler optimization. ↩

  2. Basic block (compiler) overview and CFG terminology such as leaders, successors/predecessors. https://en.wikipedia.org/wiki/Basic_block - Defines basic blocks and relates them to CFG construction and control-flow structure. ↩

Pro Tip: Think in terms of “entry”

A basic block is maximal straight-line code with a single entry point. When you apply the leader rule correctly, internal control transfers disappear from block interiors—making data-flow analysis well-defined.

Common pitfall: forgetting fall-through leaders after conditionals

For a conditional jump, the next instruction (fall-through) is a leader even if the jump target is labeled elsewhere. Missing this creates blocks that incorrectly mix two distinct control paths.

Basic blocks in the example (statement ranges)

Each bar shows how many TAC statements are included in a basic block.

From TAC to CFG (typical workflow)

Identify control constructs

1) Start with TAC

Locate labels and conditional/unconditional jumps."

Mark block boundaries

2) Find leaders

First statement, jump targets, and fall-through after jumps."

Partition into maximal straight-line regions

3) Form basic blocks

Grow each block from a leader until the next leader."

Connect via successors

4) Add CFG edges

Conditional: target + fall-through; Unconditional: target only."

Concept checks and edge cases

Basic Blocks & CFG Flashcards

1 / 4
Question · Term

Leader rule (core idea)?

Click to reveal
Answer · Definition

Mark first instruction, jump targets (labels), and the instruction after any jump as leaders; blocks run from leader to before next leader.

Knowledge Check

Question 1 of 4
Q1Single choice

In the leader rule for basic blocks, which statements must be marked as leaders?

Explore Related Topics

1

Designing a Simple Hypothetical CPU: Instruction Set, Datapath, and Control

2

Introduction to Compiler Design and Architecture

The course introduces the fundamental structure and operation of modern compilers, describing how source code is transformed through front‑end analysis, intermediate representation, and back‑end generation.

  • Front‑end performs lexical, syntax, and semantic analysis, building a symbol table and an AST independent of the target.
  • An intermediate representation (IR) like three‑address code lets language‑independent optimizations run before back‑end register and instruction selection.
  • Optimization passes (e.g., dead‑code elimination, loop unrolling) on the IR consume about 50 % of compilation CPU time.
  • Top‑down parsers fail on left‑recursive grammars; they are fixed by rewriting A → Aα | β as A → β A' and A' → α A' | ε.
3

Constructing a DAG for a Basic Block with Variable Redefinitions

Browse all research articles