Build a Control Flow Graph (CFG) from Your IR

Topic Overview

CFGs Model Execution Paths

A control flow graph has basic blocks as nodes and jumps as edges. LLVM's BasicBlock, GCC's edge lists, and every dataflow analysis start here. Building the CFG from IR means partitioning instructions at leaders and wiring fall-through and branch targets.

Constructing the CFG

Leaders: first instruction, targets of jumps, instructions after branches. Each leader starts a basic block. Successors: fall-through to next block, branch targets. Predecessors are the inverse edges.

cCopy
Loading…

• Entry block has no predecessors
• Exit blocks end in return or unreachable
• Critical edges may need splitting for SSA
• CFG is the input to dominance and loop analysis

Connecting to real compilers

Production compilers embed this step inside a longer pipeline. GCC flows through cpp, cc1, assembly, and ld; Clang uses the driver, Sema, LLVM IR passes, and a target backend. LLVM bitcode, JVM bytecode, and WASM are other familiar IRs at the same layer. The exercise isolates one pass so you can test it alone before chaining it to the next stage.

Why for this exercise

You will build a control flow graph from your IR. This exercise requires identifying basic block boundaries, creating block nodes, and linking predecessors and successors for each branch and fall-through.

Your Task

Partition three-address code into basic blocks and connect them into a control-flow graph: the structure every optimisation in the next subtracks works on.

Input

TAC in the format of Design a Simple 3-Address Code IR (copies, binary operations, NAME: labels, goto L, if a goto L, ifFalse a goto L, print a), plus return a. Instructions are numbered from 0 in input order, labels included; blank lines are ignored.

Building the graph

1. Leaders: instruction 0; every label; every instruction immediately after a goto, if, ifFalse or return.

2. A basic block runs from a leader up to (not including) the next leader. Number blocks B0, B1, … in program order.

3. Successors of a block, from its last instruction:

   • goto L → the block starting with label L
   • if / ifFalse ... goto L → the block of L (taken) then the next block (fall-through)
   • return → EXIT
   • anything else → the next block

   "The next block" after the last block is EXIT. If both successors are the same block, list it once.

4. Predecessors are the reverse edges (EXIT has none listed).

5. A block is unreachable if no path leads to it from B0.

Output

For each block:

cCopy
Loading…

Then unreachable: BX BY (or unreachable: none) and edges=E, counting every successor entry including those to EXIT.

Example

Input:

cCopy
Loading…

Output:

cCopy
Loading…

Requirements

1. A BasicBlock struct (first/last instruction, successor and predecessor lists) built from a leader bitmap.
2. Map label names to blocks once, then derive edges from each block's last instruction.

Hidden tests cover code after an unconditional goto (unreachable), a conditional jump to the very next block, several returns, and a loop whose exit falls off the end of the program.