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

As Example 4 shows, each node may have more than one pointer to it. We can represent a DAG internally by a process known as value-numbering . Each node is numbered and this number is entered whenever this node is reused. This is shown in Example 5.

 EXAMPLE 5 Value-numbering
 
 	Node	   Left Child	    Right Child
 	1. X1
 	2. a
 	3. bb
 	4. 12
 	5. * 		(3)		(4)
 	6. +		(2)		(5)
 	8.y :=		(1)		(6)
 	8. X2
 	9. 2
 	10. /		(2)		(9)
 	11. +		(10)		(5)
 	12. :=		(8)		(11)