On the complexity of partially-flow-sensitive alias analysis

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On the complexity of partially-flow-sensitive alias analysis

Full text

Pdf (575 KB)

Source

ACM Transactions on Programming Languages and Systems (TOPLAS) archive
Volume 30 , Issue 3 (May 2008) table of contents

Article No. 13

Year of Publication: 2008

ISSN:0164-0925

Authors

N. Rinetzky	Tel Aviv University, Tel Aviv, Israel
G. Ramalingam	Microsoft Research India, Bangalore, India
M. Sagiv	Tel Aviv University, Tel Aviv, Israel
E. Yahav	IBM T. J. Watson Research Center, Yorktown Heights, NY

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 9, Downloads (12 Months): 80, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1353445.1353447 What is a DOI?

ABSTRACT

We introduce the notion of a partially-flow-sensitive analysis based on the number of read and write operations that are guaranteed to be analyzed in a sequential manner. We study the complexity of partially-flow-sensitive alias analysis and show that precise alias analysis with a very limited flow-sensitivity is as hard as precise flow-sensitive alias analysis, both when dynamic memory allocation is allowed, as well as in the absence of dynamic memory allocation.

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. dissertation, DIKU, Univ. of Copenhagen. (DIKU report 94/19).
	2	Venkatesan T. Chakaravarthy, New results on the computability and complexity of points--to analysis, Proceedings of the 30th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.115-125, January 15-17, 2003, New Orleans, Louisiana, USA
	3	Susan Horwitz, Precise flow-insensitive may-alias analysis is NP-hard, ACM Transactions on Programming Languages and Systems (TOPLAS), v.19 n.1, p.1-6, Jan. 1997 [doi>10.1145/239912.239913]
	4	Brian W. Kernighan , Dennis M. Ritchie, The C programming language, Prentice Hall Press, Upper Saddle River, NJ, 1989
	5	William Alexander Landi, Interprocedural aliasing in the presence of pointers, Rutgers University, New Brunswick, NJ, 1992
	6	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]
	7	Robert Milne , C. Strachey, A Theory of Programming Language Semantics, Halsted Press, New York, NY, 1977
	8	Robert Muth , Saumya Debray, On the complexity of flow-sensitive dataflow analyses, Proceedings of the 27th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.67-80, January 19-21, 2000, Boston, MA, USA [doi>10.1145/325694.325704]
	9	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]
	10	John C. Reynolds, Separation Logic: A Logic for Shared Mutable Data Structures, Proceedings of the 17th Annual IEEE Symposium on Logic in Computer Science, p.55-74, July 22-25, 2002
	11	Strachey, C. 1966. Towards a formal semantics. In Formal Language Description Languages for Computer Programming, T. B. Steel, Ed. North Holland, Amsterdam, The Netherlands, 198--220.