Data Structures for Building Control Flow Graphs

8.5.1 Basic Blocks

A basic block is a sequence of intermediate representation constructs (quadruples, abstract syntax trees, whatever) which allow no flow of control in or out of the block except at the top or bottom. Figure 3 shows the structure of a basic block.

We will use the term statement for the intermediate representation and show it in quadruple form because quadruples are easier to read than IR in tree form.

Leaders

A basic block consists of a leader and all code before the next leader. We define a leader to be (1) the first statement in the program (or procedure), (2) the target of a branch, identified most easily because it has a label, and (3) the statement after a "diverging flow " : the statement after a conditional or unconditional branch. Figure 4 shows this pictorially:

Basic blocks can be built during parsing if it is assumed that all labels are referenced or after parsing without that assumption. Example 2 shows the outline of a FOR-Loop and its basic blocks.

Since a basic block consists of straight-line code, it computes a set of expressions. Many optimizations are really transformations applied to basic blocks and to sequences of basic blocks.

Although this program might be translated in different ways, the discussion here is still valid.

One we have computed basic blocks, we can create the control flow graph.