Compiler Design

Basic Blocks & Flow Graphs

PreviousNext

Basic Blocks & Flow Graphs

A Basic Block is a straight-line sequence of code with only one entry point and one exit point. Execution always starts at the first instruction and flows sequentially to the last instruction, with no branches in or out in the middle.

To partition a sequence of three-address code into basic blocks, we first identify Leaders (the first instruction of a block):

  • The FIRST statement of the program is a leader.
  • Any statement that is the TARGET of a goto (conditional or unconditional jump) is a leader.
  • Any statement that IMMEDIATELY FOLLOWS a goto is a leader.

Block Formation: Each leader starts a new basic block which extends up to (but not including) the next leader.

Flow Graphs

A Flow Graph is a directed graph where:

  • Nodes = Basic Blocks
  • Edges = Possible control flow (branches) between blocks. An edge B1 → B2 exists if B2 can immediately follow B1 in execution (either by a fall-through or a jump target).

A flow graph is Reducible if its edges can be cleanly partitioned into two disjoint sets:

  • Forward Edges: These form an acyclic graph where every node is reachable from the entry node.
  • Back Edges: An edge (a, b) where node b DOMINATES node a (meaning b must be executed before a can be reached). Back edges identify natural loops.

Node D dominates Node N (written as D dom N) if EVERY path from the entry node to N must go through D.

  • The Entry node dominates ALL nodes.
  • Dominance is transitive: if D dom X and X dom N, then D dom N.
  • Each node (except entry) has exactly one Immediate Dominator — the closest strict dominator on the path.

A Dominator Tree is a tree where the root is the entry node, and each node's parent is its immediate dominator. It is heavily used in compilers to find natural loops.

Introduction to Code OptimizationLive Variable Analysis