Skip to content

Lab 8.L2 · Basic blocks, the CFG, traversal orders and critical edges

Chapter: 8 · The Design Space of IRs · Lesson: 8.2 · Time: 4–6 hours · Tests: ./course test 8 (labels ch08)

Goal

Turn a three-address listing (the tac format of lab L1) into basic blocks with the leaders algorithm (Algorithm 8.2.3), build its control-flow graph (Definition 8.2.4), compute the DFS preorder, postorder and reverse postorder and the back edges (Algorithm 8.2.8), find the critical edges (Definition 8.2.5), and split them (Algorithm 8.2.6) so that the listing still computes the same value. The TAC reader, printer and interpreter are provided; the analysis and the transformation are yours.

Requirements

  • R1 (leaders). The leaders are instruction 0, every instruction that carries a label named by some jump, and every instruction immediately after a goto, if, ifz or return. Instructions are numbered from 0; labels are not instructions. A label that no jump names does not start a block.
  • R2 (blocks and edges). Blocks are named B0, B1, … in leader order. Block \(k\) spans from its leader to the instruction before the next leader. Its successors, in this order: the block of the jump target (for goto, if, ifz), then the next block if the last instruction can fall through (if, ifz, or a non-jump). A successor listed twice (a branch to its own fall-through) is listed once. return has no successors.
  • R3 (orders). Depth-first search from B0, trying successors in the order of R2. Preorder = order of first visits; postorder = order of completion; RPO = postorder reversed. Blocks not reachable from B0 appear in no order.
  • R4 (back edges). An edge u->v between reachable blocks is a back edge if v is on the DFS stack when the edge is examined (this includes self-loops). List back edges in block order of u, then in successor order.
  • R5 (critical edges). An edge u->v is critical if u has more than one successor and v more than one predecessor. Unreachable blocks count as predecessors. List them in block order of u, then in successor order.
  • R6 (splitting preserves behavior). splitCriticalEdges(L) returns a listing that the provided reader accepts (unique labels, defined targets, last instruction goto or return) and that returns the same value as L.
  • R7 (splitting is exact). Its CFG is L's CFG with each critical edge u->v replaced by u->n->v for a new block n: exactly one new block and one new edge per critical edge, and no critical edge remains. A listing without critical edges is returned unchanged.

The contract

// labs/ch08-cfg/include/cfglab/CFG.h  (provided; do not change)
namespace cfglab {
/// The report of "Output format" for listing L (R1–R5). Every line ends in '\n'.
std::string analyze(const irforms::tac::Listing &L);
/// L with every critical edge split (R6–R7).
irforms::tac::Listing splitCriticalEdges(const irforms::tac::Listing &L);
}

irforms::tac::Listing is a vector of Instr { Kind K; string Dst, Op, A, B, Target; vector<string> Labels; } (labs/ch08-forms/include/irforms/Forms.h): the labels written immediately before an instruction are attached to it. irforms::tac::parse, print and run are provided.

Command line

ch08-cfg [--split] (<file.tac> | -)

Without --split it prints analyze(listing), and with --split it prints splitCriticalEdges(listing) in the tac format. Parse errors: error: <message> on stderr, exit status 1.

Output format

Exactly these lines, in this order, single spaces, (none) for an empty list:

leaders: <instruction numbers, ascending>
B<k> [<first>,<last>] -> <successors in R2 order, or (none)>      # one line per block
preorder: <blocks>
postorder: <blocks>
rpo: <blocks>
back: <u->v edges, or (none)>
critical: <u->v edges, or (none)>

For the running example (inputs/euler1.tac):

leaders: 0 3 5 8 11 13 14 15 16 18
B0 [0,2] -> B1
B1 [3,4] -> B9 B2
B2 [5,7] -> B5 B3
B3 [8,10] -> B5 B4
B4 [11,12] -> B6
B5 [13,13] -> B6
B6 [14,14] -> B8 B7
B7 [15,15] -> B8
B8 [16,17] -> B1
B9 [18,18] -> (none)
preorder: B0 B1 B9 B2 B5 B6 B8 B7 B3 B4
postorder: B9 B8 B7 B6 B5 B4 B3 B2 B1 B0
rpo: B0 B1 B2 B3 B4 B5 B6 B7 B8 B9
back: B8->B1
critical: B2->B5 B3->B5 B6->B8

The placement of the new blocks and the names of new labels in the split listing are up to you (the reference solution appends crit.N: goto L blocks at the end and inserts a goto after a branch whose fall-through edge is critical).

Provided infrastructure

File What it gives you
../ch08-forms/include/irforms/Forms.h tac::Listing, tac::parse, tac::print, tac::run (the reader rejects duplicate labels, undefined targets and a listing that can fall off its end)
tools/CfgMain.cpp the ch08-cfg driver
inputs/*.tac euler1 (running example), gcd, nested, straight (one block), edges (unreferenced label, branch to its own fall-through, self-loop, unreachable block)
src/ yours: Stub.cpp defines the two functions with TODO(ch08)

What the tests check

Test Checks
ch08.CfgAnalyze.MatchesOracle R1–R5: analyze equals the Python oracle's report exactly on inputs/*.tac and on 40 random listings (tests/ch08/Inputs/cfg/rNN.tac, some with an unreferenced label or an unreachable tail that jumps to the entry)
ch08.CfgSplit.NoCriticalEdgesAndSameBehavior R6–R7 on the same 45 listings, with an independent block/edge counter and the provided interpreter
ch08.CfgSplit.IdempotentWithoutCriticalEdges R7's last sentence on gcd.tac
ch08.lit cfg-*.test the CLI on euler1.tac (exact report) and edges.tac, --split followed by re-analysis and ch08-run, and the reader's fall-off error

Regenerate the expected reports with python3 tests/ch08/update_goldens.py only if you change the oracle (tools/course/lib/irforms.py).

Milestones

  1. Leaders and blocks: the leaders: and B<k> lines of ch08-cfg inputs/euler1.tac match the example above.
  2. DFS orders and back edges (iteratively, not recursively: some listings are long).
  3. Critical edges: ctest -R CfgAnalyze.
  4. Splitting: ctest -R CfgSplit, then ch08-cfg --split inputs/edges.tac | ch08-cfg -.

Hints

Hint 1 — where to start

Build a map from label to instruction index first. The three leader rules then need one pass over the instructions, and a block's successors depend only on its last instruction.

Hint 2 — the key idea

For DFS, keep an explicit stack of (block, next successor index) and an "on stack" flag. An edge whose target is on the stack is a back edge. Postorder is the order in which blocks are popped. For splitting, note that only a block ending in if/ifz has two successors, so each critical edge is either its taken edge or its fall-through edge. Handle the two cases differently: retarget the jump, or insert a goto right after the branch.

Hint 3 — a design sketch

struct Blocks { vector<size_t> Leader, Last, BlockOf; vector<vector<size_t>> Succ; } built once; analyze formats from it. For splitting, compute the critical set on the original CFG, copy the listing, then for each branch block: if the taken edge is critical, add a fresh label crit.N on a new goto <old target> appended at the end and point the branch at crit.N; if the fall-through edge is critical, insert goto <label of the next block> after the branch (adding a fresh label to that block if it has none). The bug the tests catch most often: a branch whose target is its own fall-through, which is one edge, not two.

Stretch goals ★

  • Compute the dominator tree of the CFG (Ch 15) and check the reducibility claim of Lesson 8.2's pitfall: for these listings, every back edge's target dominates its source.
  • Split only the critical edges that an out-of-SSA pass would need: those into blocks with block parameters in lab L1's SSA of the same program.