Interprocedural modification side effect analysis with pointer aliasing
Published 1 June 1993Open access
William Landi, Barbara G. Ryder, Sean X. Zhang
Citations153
SJR quartileQ1
SJR score1.61
SNIP1.17
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 present a new interprocedural modification side effects algorithm for C programs, that can discern side effects through general-purpose pointer usage. Ours is the first complete design and implementation of such an algorithm. Preliminary performance findings support the practicality of the technique, which is based on our previous approximation algorithm for pointer aliases [LR92]. Each indirect store through a pointer variable is found, on average, to correspond to a store into 1.2 locations. This indicates that our program-point-specific pointer aliasing information is quite precise when used to determine the effects of these stores.
Keywords
Computer Science
Compilers: Principles, Techniques, and Tools
8,137 Citations1986Alfred V. Aho, Ravi Sethi +1 more
This book discusses the design of a Code Generator, the role of the Lexical Analyzer, and other topics related to code generation and optimization.
IEEE Transactions on Software EngineeringProgram Slicing
3,175 Citations1984Mark Weiser
In particular, finding statement-minimal slices is in general unsolvable, but using data flow analysis is sufficient to find approximate slices.
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.
ACM SIGPLAN NoticesThe program dependence graph in a software development environment
643 Citations1984Karl J. Ottenstein, Linda M. Ottenstein
Kluwer international series in engineering and computer scienceDependence Analysis for Supercomputing
599 Citations1988Utpal Banerjee
This chapter discusses one-Dimensional Arrays, Single Loops, and Dependence Tests, which are tests of the theory of Dependence on Vectors and its application to Systems of Equations.
ACM SIGPLAN NoticesInterprocedural slicing using dependence graphs
376 Citations2004Susan Horwitz, Thomas Reps +1 more
Efficient flow-sensitive interprocedural computation of pointer-induced aliases and side effects
351 Citations1993Jong-Deok Choi, Michael Burke +1 more
An algorithm for flow-sensitive interprocedural alias analysis which is more precise and efficient than the best interProcedural method known and an extension of traditional flow-insensitive aliases analysis which accommodates pointers and provides a framework for a family of algorithms which trade off precision for efficiency.
A safe approximate algorithm for interprocedural aliasing
335 Citations1992William Landi, Barbara G. Ryder
ACM SIGPLAN NoticesA safe approximate algorithm for interprocedural pointer aliasing
279 Citations2004William Landi, Barbara G. Ryder
The program dependence graph in a software development environment
270 Citations1984Karl J. Ottenstein, Linda M. Ottenstein
The program dependence graph (PDG) may be a suitable internal form that is amenable to incremental data flow analysis, improving response time to the user in an interactive environment and facilitating debugging through data flow anomaly detection.
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 flexible approach to interprocedural data flow analysis and programs with recursive data structures
211 Citations1982Neil D. Jones, Steven S. Muchnick
A new approach to data flow analysis of procedural programs and programs with recursive data structures is described, which depends on simulation of the interpreter for the subject programming language using a retrieval function to approximate a program's data structures.
Pointer-induced aliasing: a problem taxonomy
205 Citations1991William Landi, Barbara G. Ryder
The problem classification, an overview of the proof that finding interprocedural aliases in the presence of single level pointers is in 7, and a represent proof for the NP-hard problems are presented.
Internet Archive (Internet Archive)Data flow analysis techniques for test data selection
199 Citations2011S. Rapps, Elaine J. Weyuker
This paper examines a family of program test data selection criteria derived from data flow analysis techniques similar to those used in compiler optimization, arguing that currently used path selection criteria which examine only the control flow of a program are inadequate.
The semantic approach to program slicing
182 Citations1991G. A. Venkatesh
This paper identifies and categorizes different notions of a program slice available in the literature as well as several new notions formalized in a denotational framework.
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 Transactions on Programming Languages and SystemsAn interval-based approach to exhaustive and incremental interprocedural data-flow analysis
130 Citations1990Michael Burke
ACM SIGPLAN NoticesThe program summary graph and flow-sensitive interprocedual data flow analysis
125 Citations1988David Callahan
Lifetime analysis of dynamically allocated objects
114 Citations1988Cristina Ruggieri, ThomasP. Murtagh
This paper shows that compile-time lifetime analysis can be applied to programs written in languages with static type systems and dynamically allocated objects, to provide earlier storage binding time for objects, while maintaining all the advantages of dynamic allocation.
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.
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.
The program summary graph and flow-sensitive interprocedual data flow analysis
65 Citations1988D. Callahan
A method for interprocedural data flow analysis which is powerful enough to express flowsensitive problems but fast enough to apply to very large programs is discussed.
Data flow-based test adequacy analysis for languages with pointers
60 Citations1991Thomas J. Ostrand, Elaine J. Weyuker
The data f70w adequacy criteria, originally proposed for a simple language and Pascal, have been substantially modified to provide more thorough analysis for code exfensive use of pointers and complex control sirucfures, such as code frequently writ fen in the C language.
Interprocedural Def-Use associations in C programs
38 Citations1991Hemant D. Pande, William Landi
This work presents the first high-precision algorithm for obtaining Def-Use Associations in C programs with single level pointers that uses program-point-specific pointer-induced aliases to obtain good approximations to the set of definitions reaching a program point.
ISMM: the incremental software maintenance manager
22 Citations2003Barbara G. Ryder
The incremental software maintenance manager (ISMM) is a prototype software maintenance tool which uses incremental static analysis to assess the scope of proposed source code changes and validates their usefulness, especially for large systems.