ACM Portal
  Subscribe (Full Service)    Register (Limited Service, Free)    Login
  Search:   The ACM Digital Library   The Guide
  
ACM Home Page
Please provide us with feedback. Feedback
Precise flow-insensitive may-alias analysis is NP-hard
Full text PdfPdf (128 KB)
Source ACM Transactions on Programming Languages and Systems (TOPLAS) archive
Volume 19 ,  Issue 1  (January 1997) table of contents
Pages: 1 - 6  
Year of Publication: 1997
ISSN:0164-0925
Author
Susan Horwitz  Univ. of Wisconsin–Madison, Madison
Publisher
ACM  New York, NY, USA
Bibliometrics
Downloads (6 Weeks): 9,   Downloads (12 Months): 65,   Citation Count: 15
Additional Information:

abstract   references   cited by   index terms   review   collaborative colleagues  

Tools and Actions: Request Permissions Request Permissions    Review this Article  
DOI Bookmark: Use this link to bookmark this Article: http://doi.acm.org/10.1145/239912.239913
What is a DOI?

ABSTRACT

Determining aliases is one of the foundamental static analysis problems, in part because the precision with which this problem is solved can affect the precision of other analyses such as live variables, available expressions, and constant propagation. Previous work has investigated the complexity of flow-sensitive alias analysis. In this article we show that precise flow-insensitive may-alias analysis is NP-hard given arbitrary levels of pointers and arbitrary pointer dereferencing.


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
ANDERSEN, L. O. 1994. Program analysis and specialization for the C programming language. Ph.D. thesis, DIKU Rep. 94/19, DIKU, Univ. of Copenhagen, Denmark.
 
2
Michael G. Burke , Paul R. Carini , Jong-Deok Choi , Michael Hind, Flow-Insensitive Interprocedural Alias Analysis in the Presence of Pointers, Proceedings of the 7th International Workshop on Languages and Compilers for Parallel Computing, p.234-250, August 08-10, 1994
 
3
Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
4
William Landi, Undecidability of static analysis, ACM Letters on Programming Languages and Systems (LOPLAS), v.1 n.4, p.323-337, Dec. 1992  [doi>10.1145/161494.161501]
5
William Landi , Barbara G. Ryder, Pointer-induced aliasing: a problem taxonomy, Proceedings of the 18th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.93-103, January 21-23, 1991, Orlando, Florida, United States  [doi>10.1145/99583.99599]
6
G. Ramalingam, The undecidability of aliasing, ACM Transactions on Programming Languages and Systems (TOPLAS), v.16 n.5, p.1467-1471, Sept. 1994  [doi>10.1145/186025.186041]
7
Bjarne Steensgaard, Points-to analysis in almost linear time, Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.32-41, January 21-24, 1996, St. Petersburg Beach, Florida, United States  [doi>10.1145/237721.237727]

CITED BY  15
Michael Hind, Pointer analysis: haven't we solved this problem yet?, Proceedings of the 2001 ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering, p.54-61, June 2001, Snowbird, Utah, United States
Michael Hind , Michael Burke , Paul Carini , Jong-Deok Choi, Interprocedural pointer alias analysis, ACM Transactions on Programming Languages and Systems (TOPLAS), v.21 n.4, p.848-894, July 1999
Christian S. Collberg , Clark Thomborson, Watermarking, tamper-proffing, and obfuscation: tools for software protection, IEEE Transactions on Software Engineering, v.28 n.8, p.735-746, August 2002
Venkatesan T. Chakaravarthy, New results on the computability and complexity of points--to analysis, ACM SIGPLAN Notices, v.38 n.1, p.115-125, January 2003
Glenn Bruns , Satish Chandra, Searching for points-to analysis, Proceedings of the 10th ACM SIGSOFT symposium on Foundations of software engineering, November 18-22, 2002, Charleston, South Carolina, USA
Alessandro Orso , Saurabh Sinha , Mary Jean Harrold, Classifying data dependences in the presence of pointers for program comprehension, testing, and debugging, ACM Transactions on Software Engineering and Methodology (TOSEM), v.13 n.2, p.199-239, April 2004
David J. Pearce , Paul H. J. Kelly , Chris Hankin, Efficient field-sensitive pointer analysis for C, Proceedings of the ACM-SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering, June 07-08, 2004, Washington DC, USA
Glenn Bruns , Satish Chandra, Searching for points-to analysis, ACM SIGSOFT Software Engineering Notes, v.27 n.6, November 2002
Anirban Majumdar , Clark Thomborson, Manufacturing opaque predicates in distributed systems for code obfuscation, Proceedings of the 29th Australasian Computer Science Conference, p.187-196, January 16-19, 2006, Hobart, Australia
Rebecca Hasti , Susan Horwitz, Using static single assignment form to improve flow-insensitive pointer analysis, ACM SIGPLAN Notices, v.33 n.5, p.97-105, May 1998
V. Krishna Nandivada , Suresh Jagannathan, Dynamic state restoration using versioning exceptions, Higher-Order and Symbolic Computation, v.19 n.1, p.101-124, March 2006
David J. Pearce , Paul H. J. Kelly , Chris Hankin, Online Cycle Detection and Difference Propagation: Applications to Pointer Analysis, Software Quality Control, v.12 n.4, p.311-337, December 2004
David Binkley, Source Code Analysis: A Road Map, 2007 Future of Software Engineering, p.104-119, May 23-25, 2007
N. Rinetzky , G. Ramalingam , M. Sagiv , E. Yahav, On the complexity of partially-flow-sensitive alias analysis, ACM Transactions on Programming Languages and Systems (TOPLAS), v.30 n.3, p.1-28, May 2008
Fernando Magno Quintao Pereira , Daniel Berlin, Wave Propagation and Deep Propagation for Pointer Analysis, Proceedings of the 2009 International Symposium on Code Generation and Optimization, p.126-135, March 22-25, 2009

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization

  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.3 Formal Languages
          Subjects: Decision problems


General Terms:
Languages, Theory


Keywords:
alias analysis, dataflow analysis, pointer analysis, static analysis


REVIEW

"Max Hailperin : Reviewer"

Horwitz show a problem to be NP-hard that several researchers have recently attacked with polynomial-time algorithms for generating imprecise solutions. Imprecise solutions here mean those that may err, but only in a conservative d  more...

Collaborative Colleagues:
Susan Horwitz: colleagues

The ACM Portal is published by the Association for Computing Machinery. Copyright © 2009 ACM, Inc.
Terms of Usage   Privacy Policy   Code of Ethics   Contact Us

Useful downloads: Adobe Acrobat    QuickTime    Windows Media Player    Real Player