How to analyze large programs efficiently and informatively

Elimination of partial redundancies is a powerful optimization that has been implemented in at least three important production compilers and has inspired several similar optimizations. The global data flow analysis that supports this family of optimizations includes some bidirectional problems. (A bidirectional problem is one in which the global information at each basic block depends on both control flow predecessors and control flow successors.) This paper contributes two ways to simplify and expedite the analysis, especially for large programs. For each global data flow question, we examine only the places in the program where the question might have an answer different from a trivial default answer. In a large program, we may examine only a small fraction of the places conventional algorithms would examine. We reduce the relevant bidirectional problems to simpler unidirectional problems. These bidirectional problems can be solved by applying a quick correction to a unidirectional approximation