Introduction

To show the working of the MFP algorithm, in the following an example of the Reaching Definitions Analysis will be discussed step-by-step. In this analysis one wants to know for each program point which definitions might reach this point. Here, a definition of a variable x is an assignment x := E, and program points are represented by (the numbers of) nodes in the control flow graph. A definition of x at a program point i reaches program point j, if there is a path in the control flow graph from i to j which contains no other definition of x (except possibly at its two end points). The specification of the Reaching Definitions Analysis can be seen from the PAG/WWW web pages.

The Reaching Definitions Analysis will be demonstrated at the example program listed in Figure 1. Note that this is not the "Reaching Definitions example" from the PAG/WWW web pages, but contains an additional statement (the assignment in Line 11).

Figure 1: Example program

PAG/WWW returns the analysis results as presented in Figure 2. In the program, labels are introduced which correspond to the numbers of the nodes in the control flow graph. For each node, the figure lists the entry information, which reaches the node from its predecessors, and the exit information, which is passed to its successors. The definitions that reach a node are represented as pairs (x,i) of a variable x and a program point i where the assignment to this variable happened. In the beginning of the program, all variables are assumed to be defined at an unknown program point "?" somewhere before the beginning of the program. Alternatively, (x,?) may be interpreted as an indication for the fact that variable x exists, but has not been initialised.

Figure 2: The analysis results

In the next paragraph, the single steps of the MFP algorithm are explained which lead to the solution shown in Figure 2. The steps are numbered in the same way as PAG/WWW numbers them. To get further information on how to interpret the analysis results and to use the result window, see Interpreting Analysis Results.

The Analysis Steps

When looking at the pictures, it is useful to think of the various pieces of information as attached to the edges (as it is suggested by the layout of the pictures). The information at an edge is the exit information of the source node of the edge and contributes to the entry information of the destination of the edge (which is not explicitly shown).

At the end of every step, the actual worklist is shown as it will be when the step has been completed. The nodes in the worklist are ordered in the way they have to be visited by the MFP algorithm. (This ordering can be determined by the author of the analysis.) Thus the next step always selects the node standing first in the worklist, removes it from the worklist, and may insert some new nodes. In each picture, the node that has just been selected is colored red, the remaining nodes from the worklist are colored blue, and all other nodes in the control flow graph are shown green.

The initial worklist is {0}, where 0 is the start node.

	Step 1: The initial information is the same in every node, namely the least element of the lattice of analysis results. It stands for "not yet visited". The node actually visited in this step is the red node 0, the starting point of the analysis. The step to be performed now takes node 0 out of the worklist and recalculates the information for all outgoing edges. In the picture, this has not yet been done, so that the information at the outgoing edge of 0 is still . The new information at this edge can be seen in Step 2. All nodes whose input is changed by the computation of the information at the outgoing edges of the red node are inserted into the worklist. In our case, the only node to be inserted is node 1. (New) Worklist: {1}
Step 2: Now, the exit information of node 0, which is also the entry information of node 1, is visible at the edge from 0 to 1. It consists of the pairs (x,?) and (y,?) where "?" refers to an unknown position. The only node in the worklist is node 1 and so it is selected and removed from the worklist. Node 0 is now colored green because it is no longer contained in the worklist. Because of the statement in node 1, which is a definition for x, the pair (x,1) is put into the exit information of node 1 (to be seen in Step 3). This pair overwrites and replaces the previously contained pair (x,?). Indeed, the only definition of x that reaches node 2 is that in node 1. Since the information at the edge from 1 to 2 changes from to {(y,?), (x,1)}, node 2 is inserted into the worklist. Worklist: {2}
	Step 3: Node 2 is selected from the worklist and therefore colored red. Node 2 contains a definition of y and so (y,2) is inserted into the set of definitions leaving the node, overwriting (y,?). Hence, the information at the edge leading to node 3 is changed, and therefore, node 3 is inserted into the worklist. Worklist: {3}
Step 4: Node 3 has got two predecessors, so its entry information results from the two incoming sets of definitions by the combine function. In the Reaching Definitions Analysis, the combine function is , which is union for two sets, and ignores . Thus, the entry information at node 3 is the set at the edge from 2 to 3. The node selected from the worklist is node 3 (red). Since it does not contain any assignment, its entry information is passed unchanged towards its two successors, 4 and 6. Because the information at the edges towards 4 and 6 changes, both nodes are inserted into the worklist. Worklist: {4,6}
	Step 5: For the first time there are two nodes in the worklist. In the Reaching Definitions Analysis, loops are handled before the code after the loop. Hence node 4 becomes the actual node and is colored red. Node 6 remains in the worklist, which is indicated by the blue color. The statement in node 4 is a definition for y, and so (y,4) is inserted in the set of definitions, overwriting (y,2). Thus the information leaving node 4 is {(x,1),(y,4)}. Since the information at the edge from 4 to 5 changes, node 5 is inserted into the worklist. Worklist: {5,6}
Step 6: Node 5 is selected. It contains a definition for x, so the outgoing information is {(x,5),(y,4)}. Since the information at the edge from 5 to 3 changes, node 3 is inserted in the worklist (again). Worklist: {3,6}
	Step 7: Once again the MFP algorithm reaches node 3 and takes it out of the worklist. This time, both predecessors of node 3 (nodes 2 and 5) contribute a set of definitions. The entry information of node 3 is the union of these two sets, i.e. {(x,5), (x,1), (y,4), (y,2)}. Here, no overwriting occurs since the two definitions come from different control paths, and the Reaching Definitions Analysis records all definitions that may reach a program point. The exit information of node 3 is the same as its entry information (to be seen in Step 8). Thus, the information at the two edges leaving node 3 changes, and its successors, nodes 4 and 6, have to be inserted into the worklist (node 6 was already there). Worklist: {4,6}
Step 8: Again, node 4 is visited first. It contains a definition of y which overwrites the two definitions of y in the entry information of the node. Thus, the exit information of node 4 is {(x,5), (x,1), (y,4)}. The previous exit information (still to be seen in the red box) was {(x,1), (y,4)}. Since the exit information changes, the successor node 5 is inserted into the worklist. Worklist: {5,6}
	Step 9: Node 5 is selected from the worklist. It contains a definition of x which overwrites the two definitions of x in the entry information. Hence, the exit information is {(x,5), (y,4)} - the same as the old exit information (still to be seen in the red box). Therefore, the succesor node 3 is not inserted into the worklist again. Worklist: {6}
Step 10: Now node 6 is selected, the only node left in the worklist. The definitions of y from the entry information are overwritten by the new definition of y in this node. The information at the outgoing edge changes. So node 7 is inserted into the worklist. Worklist: {7}
	Step 11: The program end node 7 is now selected. Since there are no edges leaving this node, there is no successor to be inserted into the worklist. Worklist: { } The worklist is now empty, and the algorithm terminates.

Search