|
 ABSTRACT
This paper proposes an efficient technique for context-sensitive pointer analysis that is applicable to real C programs. For efficiency, we summarize the effects of procedures using partial transfer functions. A partial transfer function (PTF) describes the behavior of a procedure assuming that certain alias relationships hold when it is called. We can reuse a PTF in many calling contexts as long as the aliases among the inputs to the procedure are the same. Our empirical results demonstrate that this technique is successful—a single PTF per procedure is usually sufficient to obtain completely context-sensitive results. Because many C programs use features such as type casts and pointer arithmetic to circumvent the high-level type system, our algorithm is based on a low-level representation of memory locations that safely handles all the features of C. We have implemented our algorithm in the SUIF compiler system and we show that it runs efficiently for a set of C benchmarks.
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
|
|
| |
2
|
|
| |
3
|
R. Cytron , J. Ferrante , B. K. Rosen , M. N. Wegman , F. K. Zadeck, An efficient method of computing static single assignment form, Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.25-35, January 11-13, 1989, Austin, Texas, United States
[doi> 10.1145/75277.75280]
|
| |
4
|
|
| |
5
|
M. Emami. A Practical interprocedural Alias Analysis for an Optimizing/Parallelizing C Compiler. Master's thesis, School of Computer Science, McGill University, Aug. 1993.
|
| |
6
|
Maryam Emami , Rakesh Ghiya , Laurie J. Hendren, Context-sensitive interprocedural points-to analysis in the presence of function pointers, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.242-256, June 20-24, 1994, Orlando, Florida, United States
|
| |
7
|
|
| |
8
|
W. L. Harrison III. The Interprocedural Analysis and Automatic Parallelization of Scheme Programs. Lisp and Symbolic Computation, 2(3): 176-396, Oct. 1989.
|
| |
9
|
|
| |
10
|
|
| |
11
|
N. Jones and S. Muchnick. Flow Analysis and Optimization of Lisp-like Structures. In S. Muchnick and N. Jones, editors, Program Flow Analysis: Theory and Applications, pages 102-131. Prentice Hall, 1979.
|
| |
12
|
|
| |
13
|
|
| |
14
|
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
[doi> 10.1145/165364.165387]
|
| |
15
|
E. Ruf. Personal communication, Oct. 1994.
|
| |
16
|
Robert P. Wilson , Robert S. French , Christopher S. Wilson , Saman P. Amarasinghe , Jennifer M. Anderson , Steve W. K. Tjiang , Shih-Wei Liao , Chau-Wen Tseng , Mary W. Hall , Monica S. Lam , John L. Hennessy, SUIF: an infrastructure for research on parallelizing and optimizing compilers, ACM SIGPLAN Notices, v.29 n.12, p.31-37, Dec. 1994
[doi> 10.1145/193209.193217]
|
CITED BY 168
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
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
|
|
|
Junpei Niwa , Takashi Matsumoto , Kei Hiraki, Comparative study of page-based and segment-based software DSM through compiler optimization, Proceedings of the 14th international conference on Supercomputing, p.284-295, May 08-11, 2000, Santa Fe, New Mexico, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
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
|
|
|
|
|
|
|
|
|
|
|
|
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
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Pedro V. Artigas , Manish Gupta , Samuel P. Midkiff , José E. Moreira, Automatic loop transformations and parallelization for Java, Proceedings of the 14th international conference on Supercomputing, p.1-10, May 08-11, 2000, Santa Fe, New Mexico, United States
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
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
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
T. Kuhn , T. Oppold , C. Schulz-Key , M. Winterholer , W. Rosenstiel , M. Edwards , Y. Kashai, Object oriented hardware synthesis and verification, Proceedings of the 14th international symposium on Systems synthesis, September 30-October 03, 2001, Montréal, P.Q., Canada
|
|
|
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
|
|
|
|
|
|
|
|
|
Markus Mock , Darren C. Atkinson , Craig Chambers , Susan J. Eggers, Improving program slicing with dynamic points-to data, Proceedings of the 10th ACM SIGSOFT symposium on Foundations of software engineering, November 18-22, 2002, Charleston, South Carolina, USA
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
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
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Saman P. Amarasinghe , Jennifer M. Anderson , Christopher S. Wilson , Shih-Wei Liao , Brian R. Murphy , Robert S. French , Monica S. Lam , Mary W. Hall, Multiprocessors from a Software Perspective, IEEE Micro, v.16 n.3, p.52-61, June 1996
|
|
|
|
|
|
Jin Lin , Tong Chen , Wei-Chung Hsu , Pen-Chung Yew , Roy Dz-Ching Ju , Tin-Fook Ngai , Sun Chan, A compiler framework for speculative analysis and optimizations, ACM SIGPLAN Notices, v.38 n.5, May 2003
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Luc Séméria , Koichi Sato , Giovanni De Micheli, Resolution of dynamic memory allocation and pointers for the behavioral synthesis form C, Proceedings of the conference on Design, automation and test in Europe, p.312-319, March 27-30, 2000, Paris, France
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Partha Biswas , Vinay Choudhary , Kubilay Atasu , Laura Pozzi , Paolo Ienne , Nikil Dutt, Introduction of local memory elements in instruction set extensions, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Jin Lin , Tong Chen , Wei-Chung Hsu , Pen-Chung Yew , Roy Dz-Ching Ju , Tin-Fook Ngai , Sun Chan, A compiler framework for speculative optimizations, ACM Transactions on Architecture and Code Optimization (TACO), v.1 n.3, p.247-271, September 2004
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
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
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Monica S. Lam , John Whaley , V. Benjamin Livshits , Michael C. Martin , Dzintars Avots , Michael Carbin , Christopher Unkel, Context-sensitive program analysis as database queries, Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 13-15, 2005, Baltimore, Maryland
|
|
|
|
|
|
|
|
|
|
|
|
Girish Venkataramani , Tiberiu Chelcea , Seth Copen Goldstein , Tobias Bjerregaard, SOMA: a tool for synthesizing and optimizing memory accesses in ASICs, Proceedings of the 3rd IEEE/ACM/IFIP international conference on Hardware/software codesign and system synthesis, September 19-21, 2005, Jersey City, NJ, USA
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Antonia Zhai , Christopher B. Colohan , J. Gregory Steffan , Todd C. Mowry, Compiler Optimization of Memory-Resident Value Communication Between Speculative Threads, Proceedings of the international symposium on Code generation and optimization: feedback-directed and runtime optimization, p.39, March 20-24, 2004, Palo Alto, California
|
|
|
|
|
|
Neil Vachharajani , Matthew J. Bridges , Jonathan Chang , Ram Rangan , Guilherme Ottoni , Jason A. Blome , George A. Reis , Manish Vachharajani , David I. August, RIFLE: An Architectural Framework for User-Centric Information-Flow Security, Proceedings of the 37th annual IEEE/ACM International Symposium on Microarchitecture, p.243-254, December 04-08, 2004, Portland, Oregon
|
|
|
|
|
|
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
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Angeles Navarro , Francisco Corbera , Adrian Tineo , Rafael Asenjo , Emilio L. Zapata, Detecting loop-carried dependences in programs with dynamic data structures, Journal of Parallel and Distributed Computing, v.67 n.1, p.47-62, January, 2007
|
|
|
|
|
|
Mark Marron , Darko Stefanovic , Manuel Hermenegildo , Deepak Kapur, Heap analysis in the presence of collection libraries, Proceedings of the 7th ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering, p.31-36, June 13-14, 2007, San Diego, California, USA
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Bolei Guo , Matthew J. Bridges , Spyridon Triantafyllis , Guilherme Ottoni , Easwaran Raman , David I. August, Practical and Accurate Low-Level Pointer Analysis, Proceedings of the international symposium on Code generation and optimization, p.291-302, March 20-23, 2005
|
|
|
|
|
|
|
|
|
|
|
|
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
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Adobe Acrobat
QuickTime
Windows Media Player
Real Player
Pdf
D.3