Bjarne Steensgaard
ABSTRACT
We present an interprocedural flow-insensitive points-to analysis based on type inference methods with an almost linear time cost complexity To our knowledge, this is the asymptotically fastest non-trivial interprocedural points-to analysis algorithm yet described The algorithm is based on a non-standard type system. The type inferred for any variable represents a set of locations and includes a type which in turn represents a set of locations possibly pointed to by the variable. The type inferred for a function variable represents a set of functions It may point to and includes a type signature for these functions The results are equivalent to those of a flow-insensitive alias analysis (and control flow analysis) that assumes alias relations are reflexive and transitive.This work makes three contributions. The first is a type system for describing a universally valid storage shape graph for a program in linear space. The second is a constraint system which often leads to better results than the "obvious" constraint system for the given type system The third is an almost linear time algorithm for points-to analysis by solving a constraint system.
- ABS94.Todd M Austin, Scott E Breach, and Gurindar S Sohi. Efficient detection of all pointer and array access errors In SIGPLAN'94: Conferet#ce on Programming Languctge Design alzd hnple, zentatlon, pages 290-30t, June 1994. Google Scholar
Digital Library
- And94.Lars Ole Andersen. Program Analysis and Specialization for the C Progranzming Language. PhD thesis, Department of Computer Science, University of Copenhagen, May 1994.Google Scholar
- ASU86.Alfred V. Aho, Ravi Sethi, and Jeffrey D. Ultman. Compilers--Principles, Techniques, and Tools. Addison-Wesley, 1986 Google ScholarDigital Library
- BCCH95.Michael Burke, Paul Carini, Jong-Deok Choi, and Michael Hind Flow-insensitive interprocedurat alias analysis in the presence of pointers In Proceedings from the 7th International Workshop on Languages and Compilers for Parallel Computing, volume 892 of Lecture Notes in Computer Science, pages 234-250. Springer-Verlag, 1995. Extended version published as Research Report RC 19546, IBM T.J. Watson Research Center, September 1994. Google ScholarDigital Library
- CBC93.Jong-Deok Choi, Michael Burke, and Paul Carini. Efficient flow-sensitive interprocedural computation of pointer-induced aliases and side effects. In Proceedings of the Twentieth Annual A CM SIGPLAN-SIGA CT Symposittm on Principles of Progrcunming Languages, pages 232-245, Charleston, South Carolina, January 1993. Google ScholarDigital Library
- CR91.William Clinger and Jonathan Rees (editors). Revised4 report on the algorithmic language Scheme, November t99I.Google Scholar
- CWZ90.David R. Chase, Mark Wegman, and E Kenneth Zadeck Analysis of pointers and structures, in Proceedings of the SIGPLAN '90 Conference on Programruing Language Design and hnplementation, pages 296-310, June 1990. Google ScholarDigital Library
- Deu92.Alain Deutsch A storeless model of aliasing and its abstractions using finite representations of right-regular equivalence relations. In hzternattonal Conference on Conqmter Languages, pages 2-13 IEEE, April 1992.Google Scholar
- Deu94.Alain Deutsch. Interprocedural may-alias analysis for pointers" Beyond /,:-limiting. In SIGPLAN'94: Conference on Programming Language Design and hnplementation, pages 230-241, June 20-24 1994. Google ScholarDigital Library
- EGH94.Maryam Emami, Rakesh Ghiya, and Laurie J. Hendren. Context-sensitive interproceduraI points-to analysis in the presence of function pointers, in SIGPLAN'94: Conference on Programming Language Design and hnl#lemeiztation, pages 242-256, June 20-24 1994. Google ScholarDigital Library
- Gri95.WilliamG Griswold Use ofalgorithm from {Ste95a} in a program restructunng tool. Personal communication at PLDI'95, June 1995.Google Scholar
- Hen91.Fritz Henglein. Efficient type inference for higher-order binding-time analysis. In Functional Programmi#zg and Computer Architecture, pages 448-472, 1991. Google ScholarDigital Library
- KR88.Brian W. Kernighan and Dennis M. Ritchie. The C Programming Language, Second edition. Prentice Hall, 1988. Google ScholarDigital Library
- Lan95.William Landi. Almost linear time points-to analyses. Personal commumcanon at POPL'95, January 1995Google Scholar
- LR92.William Landi and Barbara G. Ryder. A safe approximate algorithm for interprocedural pointer aliasing. In Proceedings of the SIGPLAN '92 Conference on Programming Language Design and hlq#lementation, pages 235-248, June 1992. Google ScholarDigital Library
- LRZ93.William A. Landi, Barbara G. Ryder, and Sean Zhang. Interprocedural modification side effect analysis with pointer aliasing. In Proceedings of the SIGPLAN '93 Conference on Programmmg Language Design and hnplenzentatlon, pages 56-67, June 1993. Google ScholarDigital Library
- Mor95.David Morgenthaler. Poster presentation at PLDI'95, June 1995.Google Scholar
- Ruf95.Erik Ruf. Context-insensitive alias analysis reconsidered In SIGPLAN'95 Conference on Programming Language Design and hnplementation, pages 13-22, June 1995. Google ScholarDigital Library
- Ste95a.Bjarne Steensgaard. Points-to analysis in almost linear time. Technical Report MSR-TR-95-08, Microsoft Research, March t995.Google Scholar
- Ste95b.Bjarne Steensgaard. Sparse functional stores tbr imperative programs. In A CM SIGPLAN Workshop on Intermediate Representations (IR'95), pages 62-70, San Francisco, CA, January 22 1995. Proceedings appear as March 1995 issue of SIGPLAN Notices. Google ScholarDigital Library
- Tar83.Robert E. Tarjan. Data structures and network flow algorithms. In Regional Conference Series in Applied Mathematics, volume CMBS 44 of Regional Conference Series in Applied Mathematics. SIAM, 1983.Google Scholar
- TT94.Mads Tofte and Jean-Pierre Talpin. Implementation of the typed call-by-value A-calculus using a stack of regions. In Proceedings 21st SIGPLAN-SIGA CT Symposium on Principles of Programming Languages, pages t 88-201, January 1994. Google ScholarDigital Library
- WCES94.Daniel Weise, Roger E Crew, Michael Ernst, and Bjarne Steensgaard. Value dependence graphs: Representation without taxation. In Proceedings 21st SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pages 297-310, January 1994. Google ScholarDigital Library
- Wei80.William E. Weihl. Interprocedural data flow analysis in the presence of pointers, procedure variables, and label variables. In Cotference Record of the Seventh Annual A CM Symposium on Principles of Programming Languages, pages 83-94, January t980. Google ScholarDigital Library
- WL95.Robert E Wilson and Monica S. Lain. Efficient contextsensitive pointer analysis for C programs. In SIG- PLAN'95 Conference on Programming Language Design and Inq#lementation, pages 1-12, June 1995. Google ScholarDigital Library
- Zha95.Sean Zhang. Poster presentaUon at PLDI'95, June 1995.Google Scholar
Index Terms
- Points-to analysis in almost linear time
Recommendations
Efficient points-to analysis for whole-program analysis
To function on programs written in languages such as C that make extensive use of pointers, automated software engineering tools require safe alias information. Existing alias-analysis techniques that are sufficiently efficient for analysis on large ...
Efficient points-to analysis for whole-program analysis
ESEC/FSE-7: Proceedings of the 7th European software engineering conference held jointly with the 7th ACM SIGSOFT international symposium on Foundations of software engineeringTo function on programs written in languages such as C that make extensive use of pointers, automated software engineering tools require safe alias information. Existing alias-analysis techniques that are sufficiently efficient for analysis on large ...
On-demand dynamic summary-based points-to analysis
CGO '12: Proceedings of the Tenth International Symposium on Code Generation and OptimizationStatic analyses can be typically accelerated by reducing redundancies. Modern demand-driven points-to or alias analysis techniques rest on the foundation of Context-Free Language (CFL) reachability. These techniques achieve high precision efficiently ...
Comments