|
 ABSTRACT
We present practical approximation methods for computing interprocedural aliases and side effects for a program written in a language that includes pointers, reference parameters and recursion. We present the following results: 1) An algorithm for flow-sensitive interprocedural alias analysis which is more precise and efficient than the best interprocedural method known. 2) An extension of traditional flow-insensitive alias analysis which accommodates pointers and provides a framework for a family of algorithms which trade off precision for efficiency. 3) An algorithm which correctly computes side effects in the presence of pointers. Pointers cannot be correctly handled by conventional methods for side effect analysis. 4) An alias naming technique which handles dynamically allocated objects and guarantees the correctness of data-flow analysis. 5) A compact representation based on transitive reduction which does not result in a loss of precision and improves precision in some case. 6) A method for intraprocedural alias analysis which is based on a sparse representation.
REFERENCES
Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.
| |
1
|
A. V. Aho, M. R. Garey, and J. D. Ullman. The transitive reduction of a directed graph. SIAM journal on Computing, 1(2):131-137, 1972.
|
| |
2
|
Alfred V. Aho , Ravi Sethi , Jeffrey D. Ullman, Compilers: principles, techniques, and tools, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
|
| |
3
|
|
 |
4
|
|
| |
5
|
|
| |
6
|
|
| |
7
|
|
| |
8
|
Jong-Deok Choi , Ron Cytron , Jeanne Ferrante, Automatic construction of sparse data flow evaluation graphs, Proceedings of the 18th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.55-66, January 21-23, 1991, Orlando, Florida, United States
[doi> 10.1145/99583.99594]
|
| |
9
|
|
| |
10
|
|
| |
11
|
|
| |
12
|
|
| |
13
|
S. Horwitz , P. Pfeiffer , T. Reps, Dependence analysis for pointer variables, Proceedings of the ACM SIGPLAN 1989 Conference on Programming language design and implementation, p.28-40, June 19-23, 1989, Portland, Oregon, United States
|
| |
14
|
|
| |
15
|
|
| |
16
|
|
| |
17
|
|
| |
18
|
|
| |
19
|
|
| |
20
|
|
| |
21
|
|
| |
22
|
|
CITED BY 109
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Gary M. Zoppetti , Gagan Agrawal , Lori Pollock , Jose Nelson Amaral , Xinan Tang , Guang Gao, Automatic compiler techniques for thread coarsening for multithreaded architectures, Proceedings of the 14th international conference on Supercomputing, p.306-315, May 08-11, 2000, Santa Fe, New Mexico, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Esther Salamí , Jesús Corbal , Carlos Álvarez , Mateo Valero, Cost effective memory disambiguation for multimedia codes, Proceedings of the 2002 international conference on Compilers, architecture, and synthesis for embedded systems, October 08-11, 2002, Grenoble, France
|
|
|
|
|
|
|
|
|
|
|
|
Markus Mock , Manuvir Das , Craig Chambers , Susan J. Eggers, Dynamic points-to sets: a comparison with static analyses and potential applications in program understanding and optimization, Proceedings of the 2001 ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering, p.66-72, June 2001, Snowbird, Utah, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Jongwook Woo , Jehak Woo , Isabelle Attali , Denis Caromel , Jean-Luc Gaudiot , Andrew L Wendelborn, Alias analysis for exceptions in Java, Australian Computer Science Communications, v.24 n.1, p.321-329, January-February 2002
|
|
|
Ramkrishna Chatterjee , Barbara G. Ryder , William A. Landi, Relevant context inference, Proceedings of the 26th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.133-146, January 20-22, 1999, San Antonio, Texas, United States
|
|
|
Peng Wu , Paul Feautrier , David Padua , Zehra Sura, Instance-wise points-to analysis for loop-based dependence testing, Proceedings of the 16th international conference on Supercomputing, June 22-26, 2002, New York, New York, USA
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Mooly Sagiv , Thomas Reps , Reinhard Wilhelm, Solving shape-analysis problems in languages with destructive updating, Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.16-31, January 21-24, 1996, St. Petersburg Beach, Florida, United States
|
|
|
Jyh-shiarn Yur , Barbara G. Ryder , William A. Landi, An incremental flow- and context-sensitive pointer aliasing analysis, Proceedings of the 21st international conference on Software engineering, p.442-451, May 16-22, 1999, Los Angeles, California, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Saumya Debray , Robert Muth , Matthew Weippert, Alias analysis of executable code, Proceedings of the 25th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.12-24, January 19-21, 1998, San Diego, California, United States
|
|
|
Rakesh Ghiya , Laurie J. Hendren, Is it a tree, a DAG, or a cyclic graph? A shape analysis for heap-directed pointers in C, Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.1-15, January 21-24, 1996, St. Petersburg Beach, Florida, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Dzintars Avots , Michael Dalton , V. Benjamin Livshits , Monica S. Lam, Improving software security with a C pointer analysis, Proceedings of the 27th international conference on Software engineering, May 15-21, 2005, St. Louis, MO, USA
|
|
|
|
|
|
|
|
|
|
|
|
Michael Gorbovitski , Tom Rothamel , Yanhong A. Liu , Scott D. Stoller, Implementing incrementalization across object abstraction, Companion to the 20th annual ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, October 16-20, 2005, San Diego, CA, USA
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Stephen Fink , Eran Yahav , Nurit Dor , G. Ramalingam , Emmanuel Geay, Effective typestate verification in the presence of aliasing, Proceedings of the 2006 international symposium on Software testing and analysis, July 17-20, 2006, Portland, Maine, USA
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Thomas J. Marlowe , William G. Landi , Barbara G. Ryder , Jong-Deok Choi , Michael G. Burke , Paul Carini, Pointer-induced aliasing: a clarification, ACM SIGPLAN Notices, v.28 n.9, p.67-70, Sept. 1993
|
|
|
|
|
|
|
|
|
Marcio Buss , Daniel Brand , Vugranam Sreedhar , Stephen A. Edwards, Flexible pointer analysis using assign-fetch graphs, Proceedings of the 2008 ACM symposium on Applied computing, March 16-20, 2008, Fortaleza, Ceara, Brazil
|
|
|
|
|
|
Shay Artzi , Adam Kiezun , David Glasser , Michael D. Ernst, Combined static and dynamic mutability analysis, Proceedings of the twenty-second IEEE/ACM international conference on Automated software engineering, November 05-09, 2007, Atlanta, Georgia, USA
|
|
|
|
|
|
|
|
|
Shay Artzi , Adam Kieżun , Jaime Quinonez , Michael D. Ernst, Parameter reference immutability: formal definition, inference tool, and comparison, Automated Software Engineering, v.16 n.1, p.145-192, March 2009
|
|
|
|
|
Adobe Acrobat
QuickTime
Windows Media Player
Real Player
Pdf
D.3