In this problem, we shall consider a reaching-definitions data-flow analysis that is simpler than that in Example 12.13. Assume that each statement by itself is a block, and initially assume that each statement defines exactly one variable. The EDB predicate pred(I, J) means that statement I is a predecessor of statement J. The EDB predicate defines (I, X) means that the variable defined by statement / is X. We shall use IDB predicates in(I, D) and out(I, D) to mean that definition D reaches the beginning or end of statement /, respectively. Note that a definition is really a statement number. Fig. 12.19 is a data log program that expresses the usual algorithm for computing reaching definitions.
Notice that rule (1) says that a statement kills itself, but rule (2) assures that a statement is in its own "out set" anyway. Rule (3) is the normal transfer function, and rule (4) allows confluence, since I can have several predecessors. Your problem is to modify the rules to handle the common case where a definition is ambiguous, e.g., an assignment through a pointer. In this situation, defines(I,X) may be true for several different X's and one I. A definition is best represented by a pair (D,X), where D is a statement, and X is one of the variables that may be defined at D. As a result, in and out become three argument predicates; e.g., in(I, D,X) means that the (possible) definition of X at statement D reaches the beginning of statement I.
Example 12.13