Read an Excerpt
From Chapter 10: Code Optimization
...Meet-Over-Paths Solutions to Data-Flow Problems
Let us imagine that a flow graph has associated with each of its nodes a transfer function, one of the functions in the set F. For each block B, let fB be the transfer function for B.
Consider any path P = B0 => B1 => . . . => Bk from the initial node B0 to some block Bk. We can define the transfer function for P to be the composition of fB0, fBk-1. Note that fBk is not part of the composition, reflecting the point of view that this path is taken to reach the beginning of block Bk, not its end.
We have assumed that the values in V represent information about data used by the program, and that the confluence operator tells how that information is combined when paths converge. It also makes sense to see the top element as representing "no information," since a path carrying the top element yields to any other paths. Thus, if B is a block in the flow graph, the information entering B should be computable by considering every possible path from the initial node to B and seeing what happens along the path, starting out with no information.
Inprinciple, this meet could be over an infinite number of different values, since there are an infinite number of different paths. In practice, it is often adequate to consider only acyclic paths, and even when it is not, as for the constant computation framework discussed above, there are usually other reasons we can find to make this infinite meet by finite meetbe finite for any particular flow graph.
The mop solution to a flow graph makes sense when we realize that as far as information reaching block B is concerned, the flow graph may as well be the one suggested in Fig. 10.61, where the transfer function associated with each of the (possibly infinite number of) paths P1, P2, . . . , in the original flow graph has been given an entirely separate path to B. In Fig. 10.61, the information reaching B is given by the meet over all paths.
Conservativbe Solutions to Flow Problems
When we try to solve the data-flow equations that come from an arbitrary framework, we may or may not be able to obtain the mop solution easily. Fortunately, as with the concrete examples of data-flow frameworks in Sections 10.5 and 10.6, there is a safe direction in which to err, and the iterative data-flow algorithm we discussed in those sections turns out always to provide us with a safe solution. We say a solution in[B] is a safe solution if in[B] is less than or equal to mop(B) for all blocks B.
Despite what the reader might imagine, we did not pull this definition out of thin air. Recall that in any flow graph, the set of apparent paths to a node (those that are paths in the flow graph) can be a proper subset of the real paths, those that are taken on some execution of the program corresponding to this flow graph. In order that the result of the data-flow analysis be usable for whatever purpose we intend it, the data must still be safe if we modify the flow graph by deleting some paths, since we cannot in general distinguish real paths from apparent paths that are not real.
While we may prefer the "true" solution to the data-flow problem, we shall almost surely have no efficient way to tell exactly which paths are real and which are not, so we are forced to accept the mop solution as the closest feasible solution. Thus, whatever use we make of the data-flow information must be consistent with the possibility that the solution we obtain is less than or equal to the true solution. Once we accept that, we should also be able to accept a solution that is less than or equal to the mop for those frameworks that are monotone but not distributive. For distributive frameworks, like those of Section 10.6, the simple iterative algorithm computes the mop solution...
