Interprocedural data-flow analysis that supports recursion while only

Abstract

A computer implemented method performs flow-sensitive interprocedural data flow analysis without iteration for a class of interprocedural problems. The accuracy of the solution can approach the iterative result without the compile time cost. For interprocedural constant propagation (ICP), this method is more effective than existing methods and costs about the same compilation time. For flow-sensitive ICP over a program call graph (PCG), the method supports recursion while only performing one flow-sensitive analysis of each routine. If the PCG has cycles, a flow-insensitive solution is precomputed for constant propagation. During the flow-sensitive computation, the flow-insensitive result is used for a back edge. This permits a flow-sensitive solution to be obtained in one forward traversal of the PCG. This method can also be used to compute returned constants with one reverse traversal of the PCG. For flow-sensitive USE over a program call graph (PCG), the method supports recursion while only performing one flow-sensitive analysis of each routine. If the PCG has cycles, a flow-insensitive solution for a reference set (REF) is precomputed. During the flow-sensitive USE computation, the flow-insensitive REF solution is used for a back edge. This permits a flow-sensitive USE solution to be obtained in one reverse traversal of the PCG.