Data Flow Analysis for Procedural Languages

Abstract

Global analysis and optimization techniques presuppose local data flow information about the effects of program statements on the values associated wRh names For procedure calls this information is not immediately available but can presumably be obtained through flow analysis of procedure bodies Accurate mformatlon proves to be surprisingly difficult to obtain This paper includes a language independent formulation of the problem, an interprocedural data flow algorithm, and a proof that the algorithm is correct Symbohc data flow analysis is introduced in the course of optimizing the algorithm We move much of the work outside of a loop by manipulating partially evaluated symbolic expressions for the data within the loop Foundational difficulties are revealed when the theory of data flow analysis is extended to support extensive optimization of procedural language programs Several widespread assumptions become false or ambiguous A few of the problems are resolved here Inductive arguments are facilitated by a simple path tree representation of control flow that allows for both recurslon and side effects. © 1979, ACM. All rights reserved.