An interval-based approach to exhaustive and incremental interprocedural data-flow analysis
ACM Transactions on Programming Languages and SystemsPublished 1 July 1990Open access
Michael Burke
Citations130
SJR quartileQ2
SJR score0.56
SNIP1.52
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
Abstract
We reformulate interval analysis so that it can he applied to any monotone data-flow problem, including the nonfast problems of flow-insensitive interprocedural analysis. We then develop an incremental interval analysis technique that can be applied to the same class of problems. When applied to flow-insensitive interprocedural data-flow problems, the resulting algorithms are simple, practical, and efficient. With a single update, the incremental algorithm can accommodate any sequence of program changes that does not alter the structure of the program call graph. It can also accommodate a large class of structural changes. For alias analysis, we develop an incremental algorithm that obtains the exact solution as computed by an exhaustive algorithm. Finally, we develop a transitive closure algorithm that is particularly well suited to the very sparse matrices associated with the problems we address.
Keywords
Computer Science
SIAM Journal on ComputingDepth-First Search and Linear Graph Algorithms
6,021 Citations1972Robert E. Tarjan
The value of depth-first search or “backtracking” as a technique for solving problems is illustrated by two examples of an improved version of an algorithm for finding the strongly connected components of a directed graph.
Journal of the ACMA Theorem on Boolean Matrices
1,657 Citations1962Stephen Warshall
It is proved the validity of an algorithm whose running time goes up slightly faster than the square of d, the running times of which increase-other things being equal-as the cube of d.
A unified approach to global program optimization
893 Citations1973Gary A. Kildall
A technique is presented for global analysis of program structure in order to perform compile time optimization of object code generated for expressions that includes constant propagation, common subexpression elimination, elimination of redundant register load operations, and live expression analysis.
Optimizing supercompilers for supercomputers
837 Citations2020Michael Wolfe
This work will focus a great deal on the importance of compilers in supercomputing, and compare and contrast the advantages and impacts of compiler solutions to the "Performance + Portability + Productivity" problem with language and runtime solutions.
Dependence graphs and compiler optimizations
652 Citations1981David J. Kuck, Robert H. Kuhn +3 more
This paper defines such graphs and discusses two kinds of transformations, simple rewriting transformations that remove dependence arcs and abstraction transformations that deal more globally with a dependence graph.
Communications of the ACMA program data flow analysis procedure
410 Citations1976Frances Allen, John Cocke
The global data relationships in a program can be exposed and codified by the static analysis methods described in this paper.
Acta InformaticaMonotone data flow analysis frameworks
380 Citations1977John B. Kam, Jeffrey D. Ullman
This work shows the nonexistence of an algorithm to compute the meet over all paths solution for monotone frameworks, and shows that the maximal fixed point solution exists for every instance of everymonotone framework, and that it can be obtained by Kildall's algorithm.
Journal of the ACMGlobal Data Flow Analysis and Iterative Algorithms
303 Citations1976John B. Kam, Jeffrey D. Ullman
Conditions under which the bound on the number of iterations required for propagation algorithms when the data is represented by bit vectors and depth-first ordering of the flow graph is used are considered are considered.
Journal of the ACMFast Algorithms for Solving Path Problems
282 Citations1981Robert E. Tarjan
A method to compute path expressions by dividing G into components, computing path expressions on the components by Gaussian elimination, and combining the solutions is described, which requires O(m $\alpha$(m,n) time on a reducible flow graph.
IEEE Transactions on ComputersHigh-Speed Multiprocessors and Compilation Techniques
269 Citations1980Padua, Kuck +1 more
The purpose of this paper is to present some ideas on multiprocessor design and on automatic translation of sequential programs into parallel programs for multip rocessors.
Journal of the ACMA Unified Approach to Path Problems
249 Citations1981Robert E. Tarjan
The results provide a general-purpose algorithm for solving any path problem, and show that the problem of constructing path expressions is in some sense the most general path problem.
An efficient way to find the side effects of procedure calls and the aliases of variables
242 Citations1979John Banning
ACM SIGPLAN NoticesInterprocedural dependence analysis and parallelization
219 Citations2004Michael Burke, Ron K. Cytron
A method is presented that combines a deep analysis of program dependences with a broad analysis of the interaction among procedures, and a unified approach that integrates subscript analysis with aliasing and interprocedural information is presented.
A precise inter-procedural data flow algorithm
210 Citations1981Eugene M. Myers
The avail, live, and must-summary data flow problems are shown to be NP-complete in the presence of aliasing and it is argued that in practice SET is small and on the order of the number of variables of the program.
Journal of Computer and System SciencesTesting flow graph reducibility
187 Citations1974Robert E. Tarjan
Journal of the ACMA Fast and Usually Linear Algorithm for Global Flow Analysis
187 Citations1976Susan L. Graham, Mark N. Wegman
A new algorithm for global flow analysis on reducible graphs which has a worst-case time bound of O(e log e) function operations and a restriction to one-entry one-exit control structures guarantees linearity.
An overview of the PTRAN analysis system for multiprocessing
184 Citations2014Frances Allen, Michael Burke +3 more
SIAM Journal on ComputingFlow Graph Reducibility
172 Citations1972Matthew S. Hecht, Jeffrey D. Ullman
Rice University's digital scholarship archive (Rice University)Dependence analysis for subscripted variables and its application to program transformations
170 Citations1983John R. Allen
The order in which the statements of a program are executed can affect the execution time of the program, and this fact has made use of this fact by reordering code to improve its performance on a machine.
Journal of the ACMCharacterizations of Reducible Flow Graphs
168 Citations1974Matthew S. Hecht, Jeffrey D. Ullman
The backward edges of a reducible flow graph are unique and it is shown that there is a “natural” single-entry loop associated with each backward edge of a reducing flow graph.
Communications of the ACMA practical interprocedural data flow analysis algorithm
153 Citations1978Jeffrey M. Barth
A new interprocedural data flow analysis algorithm is presented and analyzed which associates with each procedure in a program information about which variables may be modified, which may be used, and which are possibly preserved by a call on the procedure, and all of its subcalls.
ACM SIGPLAN NoticesInterprocedural side-effect analysis in linear time
149 Citations2004Keith D. Cooper, Ken Kennedy
Automatic decomposition of scientific programs for parallel execution
145 Citations1987Randy Allen, David Callahan +1 more
An algorithm for transforming sequential programs into equivalent parallel programs is presented and the problem of generating optimal code when loop interchange is employed is shown to be intractable.
SIAM Journal on ComputingA Simple Algorithm for Global Data Flow Analysis Problems
135 Citations1975Matthew S. Hecht, Jeffrey D. Ullman
A simple, iterative bit propagation algorithm for solving global data flow analysis problems such as “available expressions” and “live variables” is presented and shown to be quite comparable in speed to the corresponding interval analysis algorithm.
Journal of Parallel and Distributed ComputingAn overview of the PTRAN analysis system for multiprocessing
135 Citations1988Frances Allen, Michael Burke +3 more
PTRAN-A: the currently operational analysis phase of PTRAN, which is both broad and deep, incorporating interprocedural information into dependence analysis.
ACM SIGPLAN NoticesThe program summary graph and flow-sensitive interprocedual data flow analysis
125 Citations1988David Callahan
ACM Computing SurveysElimination algorithms for data flow analysis
120 Citations1986Barbara G. Ryder, Marvin C. Paull
A unified model of a family of data flow algorithms, called elimination methods, is presented, which provides implementation-independent descriptions of the algorithms to facilitate comparisons among them and illustrate the sources of improvement in worst case complexity bounds.
Fast interprocedual alias analysis
115 Citations1989Keith D. Cooper, Ken Kennedy
A new algorithm for computing interprocedural aliases due to passing parameters by reference is presented and, when combined with algorithms for alias-free, flow-insensitive data-flow problems, yields algorithms for solution of the general flow- insensitive problems.
Efficient computation of flow insensitive interprocedural summary information
106 Citations1984Keith D. Cooper, Ken Kennedy
This paper describes a method for annotating each statement s in a program with a set MOD(s) conraining those variables whose values can be changed as a result of executing s.
Incremental data flow analysis in a structured program editor
106 Citations1984F. Kenneth Zadeck
A new algorithm for solving some GDFAPs is presented here and it is expected that this algorithm will run slower in the batch compiling environment, but there are conditions under which this algorithm can be expected to be superior to those in the bit vector class.
ACM Transactions on Programming Languages and SystemsThe impact of interprocedural analysis and optimization in the R <sup>n</sup> programming environment
104 Citations1986Keith D. Cooper, Ken Kennedy +1 more
An overview of the methods used by the environment to accomplish interprocedural analysis and optimization is presented and the impact of these methods on the various environment components are discussed.
Acta InformaticaFast algorithms for the elimination of common subexpressions
99 Citations1973Jeffrey D. Ullman
Two algorithms for computing the set of available expressions at entrance to the nodes of a flow graph are given and one of them works only for reducible flow graphs and requires O(n log n) extended steps.
ACM Transactions on Programming Languages and SystemsIncremental data-flow analysis algorithms
95 Citations1988Barbara G. Ryder, Marvin C. Paull
This work identifies a priori the nodes in its flow graph whose corresponding data-flow equations may be affected by the changes of ACINCF and ACINCB, and can be refined to characterize the reduced equations possibly affected if structured loop exit mechanisms are used.
IEEE Transactions on Software EngineeringProperty extraction in well-founded property sets
93 Citations1975Ben Wegbreit
Techniques are presented for property computation in iterative and recursive programs and application to a variety of property sets is discussed.
Analyzing aliases of reference formal parameters
86 Citations1985Keith D. Cooper
This paper presents a set of techniques for analyzing aliasing patterns, divided into detecting the introduction of aliases and tracking their propagation, and a data flow analysis framework is given for the propagation problem.
Incremental data flow analysis via dominator and attribute update
83 Citations1988Martin D. Carroll, Barbara G. Ryder
This work reduces a monotone data flow problem formulated for solution using Graham-Wegman elimination to the problem of constructing and decorating an attributed tree structurally isomorphic to the dominator tree of the program flow graph, and extends Reps' attributed tree update techniques to update attribute values in response to changes in this structure.
Communications of the ACMHigh-level data flow analysis
72 Citations1977Barry K. Rosen
A simple general method of high-level data flow analysis that allows free use of escape and jump statements, avoids large graphs when compiling large programs, facilitates updating of data flow information to reflect program changes, and derives new global information helpful in solving many familiar global flow analysis problems is proposed.
Journal of the ACMData Flow Analysis for Procedural Languages
70 Citations1979Barry K. Rosen
A language independent formulation of the problem, an interprocedural data flow algorithm, and a proof that the algorithm is correct are included, and several widespread assumptions become false or ambiguous.
ACM SIGPLAN NoticesInterprocedural dependence analysis and parallelization
69 Citations1986Michael Burke, Ron K. Cytron
Incremental data flow analysis
67 Citations1983Barbara G. Ryder
This paper presents ACINCF and ACINCB, incremental update algorithms for forward and backward data flow problems, which are based on a linear equations model of Allen/Cocke interval analysis, and studies their performance on a robust structured programming language L.
Acta InformaticaOn computing the transitive closure of a relation
65 Citations1977J. Eve, Reino Kurki-Suonio
An algorithm is presented for computing the transitive closure of an arbitrary relation which is based upon Tarjan's algorithm for finding the strongly connected components of a directed graph, and combines the advantages of Warshall's algorithm, namely, succinctness, a single traversal of the directed graph and ability to exploit the availability of Boolean vector operations.
ACM Transactions on Programming Languages and SystemsExperience with the SETL Optimizer
61 Citations1983Stefan M. Freudenberger, Jacob T. Schwartz +1 more
The structure of an existing optimizer for the very high-level, set theoretically oriented programming language SETL is described, and its capabilities are illustrated.
International Journal of Computer MathematicsA global flow analysis algorithm
61 Citations1972Ken Kennedy
A global algorithm which uses interval analysis techniques to recognize live variables is presented and it is shown that this algorithm can be used to solve the challenge of recognizing live variables in discrete time.
IBM Journal of Research and DevelopmentThe Experimental Compiling System
55 Citations1980Frances Allen, J. L. Carter +5 more
The Experimental Compiling System (ECS) described here represents a new compiler construction methodology that uses a compiler base which can be augmenttd to create a compiler for any one of a wide class of source languages.
IEEE Transactions on Software EngineeringA critical analysis of incremental iterative data flow analysis algorithms
40 Citations1990Michael Burke, Barbara G. Ryder
A model of data flow analysis and fixed point iteration solution procedures is presented and the faulty incremental iterative algorithm is introduced.
An interprocedural data flow analysis algorithm
40 Citations1977Jeffrey M. Barth
A lower bound for the computational complexity of gathering interprocedural data flow information is derived and the algorithm is shown to be asymptotically optimal.
Software Practice and ExperienceInterprocedural optimization: Experimental results
38 Citations1989Stephen Richardson, Mahadevan Ganapathi
An algorithm for interprocedural data flow analysis has been implemented that produces three flow‐insensitive summary sets: MOD, USE and ALIASES and the utility of the resulting information was investigated using an optimizing Pascal compiler.
ACM SIGPLAN NoticesAn incremental algorithm for software analysis
32 Citations1987Martin D. Carroll, Barbara G. Ryder
Rice University's digital scholarship archive (Rice University)Interprocedural data flow analysis in a programming environment
31 Citations1983Keith D. Cooper
This thesis examines three problems arising in the construction of an ambitious optimizing compiler based in a programming environment, the analysis of aliasing patterns, computation of summary data flow information, and assignment of linkage styles to call sites.
Science of Computer ProgrammingConditions for incremental iteration: Examples and counterexamples
27 Citations1988Barbara G. Ryder, Thomas J. Marlowe +1 more
The results show that this incremental update procedure is not in general correct, and sufficient conditions for correctness are given, and counterexamples in Boolean algebra and data flow analysis showing that difficulties with the proposed algorithms can occur in practice.
Data-flow analysis and incremental iteration
20 Citations1989Thomas J. Marlowe, Barbara G. Ryder
This work examines first data flow frameworks and then incremental algorithms in detail, and determines precise conditions responsible for the inefficiency of existing incremental iterative data flow algorithms, and proposes a class of algorithms, which are called hybrid algorithms, based on the strong component decomposition of the flow graph and a corresponding factorization of the lattice.
SIAM Journal on ComputingA Comparison of Two Algorithms for Global Data Flow Analysis
20 Citations1976Ken Kennedy
The problem of determining the points in a program at which variables are “live” (will be used again) is introduced and discussed and two solutions, one which uses a simple iterative algorithm and an algorithm based on “Cocke–Allen interval” analysis are presented and analyzed.
Linear cost is sometimes quadratic
17 Citations1981Barry K. Rosen
Demand-driven algorithms capable of updating without extensive reanalysls are studied: accurate where accuracy is demanded, but not burdened by the cost of providing much more than is demanded.
STARS (University of Central Florida)Incremental analysis of programs
16 Citations1983Vida Ghodssi
These algorithms update the solution from a previous analysis to reflect changes in the program to ensure extensive reanalysis of programs after each program modification can be avoided.
Incremental data flow analysis based on a unified model of elimination algorithms
13 Citations1982Barbara G. Ryder
It is shown that given a data flow problem defined on a digraph, the effects of a set of localized program changes can be determined without full re-analysis by some global data flow algorithm.
SIAM Journal on ComputingA Lubricant for Data Flow Analysis
6 Citations1982Barry K. Rosen
The main result relates the problem of finding a flow cover to that of finding regular expressions to describe certain sets of paths in the graph so that one can be ready to solve any problem with that scheme by interpreting the expressions in light of the remaining portions of the problem.