Questions: Basic Block Analysis

Question 1

A three-address code sequence contains a conditional branch to label L7, followed by another instruction. According to basic block analysis, which of the following is correct?

• A. Only the instruction at L7 starts a new basic block; the instruction after the branch stays in the current block
• B. The conditional branch itself becomes its own single-instruction basic block
• C. Both the instruction at L7 and the instruction immediately following the branch are leaders that start new basic blocks
• D. The branch ends the current block; no new block begins until the next unconditional jump

Answer: (C)

A branch creates two potential successors: the branch target (L7) and the fall-through (the instruction immediately after). Both are leaders because: L7 is a jump target, and the instruction after the branch immediately follows a branch instruction. These are two of the three leader conditions. The current block ends at the branch (its last instruction). This ensures every basic block has exactly one entry point and exits only at its final instruction — the defining property of a basic block.

Question 2

A compiler wants to propagate constants across an entire function (not just within single blocks). What infrastructure is required beyond basic block identification?

• A. No additional infrastructure — constant propagation is purely local and works block-by-block
• B. A control-flow graph built from the basic blocks, then a dataflow analysis (reaching definitions) across block boundaries
• C. Splitting basic blocks into smaller single-instruction units so constants propagate more easily
• D. Exception handler elimination, since exception targets are the only obstacle to global propagation

Answer: (B)

Local constant folding works within a single basic block. But to propagate a constant computed in block A into block B (which follows A), the compiler needs to know which blocks can reach which — that is, it needs the control-flow graph. Then it runs a dataflow analysis (like reaching definitions) that tracks what values are guaranteed to be constant at each point across the CFG. This is the distinction between local optimizations (within a block) and global optimizations (across the CFG). Basic block identification is the prerequisite for building the CFG.

Question 3

Any two instructions within the same basic block can be freely reordered, since a basic block guarantees sequential execution with no branches.

• T. True
• F. False

Answer: False

Sequential control flow guarantees that all instructions in a basic block execute in order when any of them executes — but it does NOT mean they can be arbitrarily reordered. Reordering is only safe when there are no data dependencies: if instruction B reads a value written by instruction A, B must come after A regardless of the block structure. A basic block eliminates control-flow hazards but not data-dependence hazards. Local optimization within a block still requires dependence analysis before reordering instructions.

Question 4

A basic block has exactly one entry point (its first instruction) and all control flow exits through its last instruction, with no jumps into or out of the middle of the block.

• T. True
• F. False

Answer: True

This single-entry, single-exit property is the defining characteristic of a basic block and the reason it is so useful for optimization. It means that if the first instruction of a block executes, every instruction in the block executes. This guarantee allows local optimizations (common subexpression elimination, constant folding) to reason about a block's contents as a straight-line sequence without worrying about control flow. The CFG edges then capture how blocks relate to each other.

Question 5

What is a 'leader' in basic block analysis, and what three conditions make an instruction a leader? Why does identifying leaders fully determine the basic block partition?

Model answer: A leader is an instruction that begins a new basic block. The three conditions are: (1) the first instruction in the program is always a leader; (2) any instruction that is the target of a branch or jump is a leader; (3) any instruction that immediately follows a branch or jump is a leader. Once all leaders are identified, each basic block consists of a leader plus all subsequent instructions up to (but not including) the next leader. This completely partitions the instruction sequence into non-overlapping basic blocks with no ambiguity.

The leader-based algorithm is elegant because it requires only a single pass to identify leaders and a second pass to assign instructions to blocks. Every instruction belongs to exactly one basic block: the one begun by the most recent leader at or before it. The algorithm handles all control flow structures — conditionals, loops, switches — uniformly, because they all ultimately reduce to branch instructions whose targets and fall-throughs are leaders.