Questions: Control Flow Graphs

Question 1

Which of the following best defines a basic block in a control flow graph?

• A. Any single three-address instruction in the intermediate representation.
• B. A maximal sequence of consecutive instructions with exactly one entry point (no jumps into the middle) and one exit point (execution falls through or branches only at the end).
• C. Any loop body identified by a back edge in the CFG.
• D. A set of instructions that all access the same variable.

Answer: (B)

A basic block is defined by the absence of internal control flow: once execution enters the first instruction, every subsequent instruction in the block is guaranteed to execute before any branch. 'Maximal' means we extend the block as far as possible before hitting a branch or a branch target. This guarantee — that the whole block runs or none of it does — is exactly what enables optimizations like local dead-code elimination and constant folding within a block.

Question 2

In a CFG, a conditional branch instruction (such as an if-else) always produces exactly two outgoing edges from the basic block that contains it.

• T. True
• F. False

Answer: True

A conditional branch has two possible successor states: the taken branch (true branch) and the fall-through (false branch). Both must be represented as outgoing edges so the CFG accurately models all possible execution paths. An unconditional jump produces one outgoing edge, and a return instruction typically connects to a special EXIT node or has no outgoing edge (depending on the CFG model).

Question 3

A naive approach to optimization would operate instruction-by-instruction across the whole program. Why do compiler writers instead build a CFG and work with basic blocks as the unit of analysis?

Model answer: Within a basic block, control flow is linear and predictable: every instruction executes in sequence whenever any instruction in the block executes. This lets optimizations like constant propagation, common subexpression elimination, and liveness analysis make guarantees that would require tracking branching for individual instructions. The CFG then lifts these per-block results to the whole program, connecting blocks via edges so inter-block (global) analyses like reaching definitions and dominator trees can be computed with standard graph algorithms.

Basic blocks partition the program into chunks where local reasoning is safe, and the CFG provides the graph structure for global reasoning. This two-level decomposition — local optimization within blocks, global analysis on the CFG — is the core architecture of almost every optimizing compiler, from GCC to LLVM. The alternative (working instruction-by-instruction across arbitrary control flow) would require re-analyzing every possible execution path at every step.