8.5.6 Data Structure for a DAG

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)