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

8.5.5 DAGs

The previous sections looked at the control flow graph nodes of basic blocks. DAGs, on the other hands, create a useful structure for the intermediate representation within the basic blocks.

A directed graph with no cycles, called a DAG (Directed Acyclic Graph), is used to represent a basic block. Thus, the nodes of a flow graph are themselves graphs!

We can create a DAG instead of an abstract syntax tree by modifying the operations for constructing the nodes. If the node already exists, the operation returns a pointer to the existing node. Example 4 shows this for the two-line assignment statement example.

    In Example 4, there are two references to a and two references to the quantity bb * 12 .