Basic Blocks

Building a Flow Graph

Techniques for Building Flow Graphs

Data Structures for Building Control Flow Graphs

DAGs

Data Structures for a DAG

Benefits of DAGs

Building a control flow graph involves finding predecessors and successors.

Consider the first situation of Figure 6 where basic block A has been built and a leader is identified for the beginning of basic block B. We cannot build the tail of the arrow to basic block B until we find the diverging flow that leads here. Backpatching: returning and filling in the tail information, will define the source of this arc.

The second picture represents the opposite situation. In the second picture in Figure 6, we know we have an arc, but haven't found the leader to which the arc should point; the tail of the arc is known, but its head is not. Here, we can allocate a data structure for a basic block and then backpatch when it is found.