Basic Block Analysis

Topic Overview

Analyzing Block Structure

Basic blocks are straight-line code with single entry and exit. Analyses partition the CFG into blocks, then compute properties per block: predecessors, successors, dominators, loop membership. LLVM's LoopInfo and GCC's loop passes depend on this foundation.

Block-Level Facts

For each block: list of instructions, predecessor and successor sets, whether it is a loop header, whether it dominates its successors' join nodes.

cCopy
Loading…

• Leaders define block boundaries
• Critical edge: pred has multiple succs and succ has multiple preds
• Loop header: block with back edge from descendant
• Block frequency estimates guide code layout

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 implement basic block analysis on your CFG. This exercise requires identifying blocks, computing predecessor and successor lists, and preparing data structures for loop and dominance analyses.

Your Task

Go beyond splitting code into basic blocks: compute global liveness over the control-flow graph, which variables are live on entry to and exit from every block, with the classic iterative data-flow algorithm. This is the analysis register allocators and dead-store elimination run on real, branching code.

Input

TAC with labels and jumps: x = a, x = a OP b, L:, goto L, if a goto L, ifFalse a goto L, print a, return a. Operands are names or integer literals.

Steps

1. Blocks and edges exactly as in Build a Control Flow Graph (CFG) from Your IR: leaders are the first instruction, every label, and every instruction after a jump or return; a conditional jump has two successors, goto one, return none; otherwise control falls through to the next block. Blocks are B0, B1, ….
2. Local sets per block, scanning its instructions top to bottom:
   • use(B): variables read before any write to them in B
   • def(B): variables written in B
3. Iterate until nothing changes: in each pass, visit blocks from the last to the first and set out(B) = ⋃ in(S) over successors S, then in(B) = use(B) ∪ (out(B) − def(B)). All sets start empty. Count passes, including the final one that changes nothing.

Output

cCopy
Loading…

Variables inside a set are listed in order of first appearance in the program (reading each instruction left to right), separated by single spaces.

Example

Input:

cCopy
Loading…

Output:

cCopy
Loading…

Requirements

1. Bit sets (or boolean arrays indexed by variable) for use, def, in and out.
2. Compute the local sets once; the iteration only combines them.

Hidden tests cover nested loops, a variable that is never live, and an unreachable block (liveness still flows backward into it from its successor).