Partitioning dataflow analyses using types

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Partitioning dataflow analyses using types

Full text

Pdf (925 KB)

Source

Annual Symposium on Principles of Programming Languages archive
Proceedings of the 24th ACM SIGPLAN-SIGACT symposium on Principles of programming languages table of contents

Paris, France

Pages: 15 - 26

Year of Publication: 1997

ISBN:0-89791-853-3

Author

Erik Ruf

Microsoft Research, One Microsoft Way, Redmond, WA

Sponsors

L'Ecole des Mines de Paris : L'Ecole des Mines de Paris
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
Ctr Natl de la Recherche Sci :
SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 4, Downloads (12 Months): 27, Citation Count: 15

Additional Information:

references cited by 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/263699.263705 What is a DOI?

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.

	CC77	Patrick Cousot , Radhia Cousot, Abstract interpretation: a unified lattice model for static analysis of programs by construction or approximation of fixpoints, Proceedings of the 4th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.238-252, January 17-19, 1977, Los Angeles, California [doi>10.1145/512950.512973]
	CCF91	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]
	CFR+91	Ron Cytron , Jeanne Ferrante , Barry K. Rosen , Mark N. Wegman , F. Kenneth Zadeck, Efficiently computing static single assignment form and the control dependence graph, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.4, p.451-490, Oct. 1991 [doi>10.1145/115372.115320]
	CWZ90	David R. Chase , Mark Wegman , F. Kenneth Zadeck, Analysis of pointers and structures, Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation, p.296-310, June 1990, White Plains, New York, United States
	Deu94	Alain Deutsch, Interprocedural may-alias analysis for pointers: beyond k-limiting, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.230-241, June 20-24, 1994, Orlando, Florida, United States
	DGS94	Evelyn Duesterwald , Rajiv Gupta , Mary Lou Soffa, Reducing the Cost of Data Flow Analysis By Congruence Partitioning, Proceedings of the 5th International Conference on Compiler Construction, p.357-373, April 07-09, 1994
	DRZ92	Dhananjay M. Dhamdhere , Barry K. Rosen , F. Kenneth Zadeck, How to analyze large programs efficiently and informatively, Proceedings of the ACM SIGPLAN 1992 conference on Programming language design and implementation, p.212-223, June 15-19, 1992, San Francisco, California, United States
	Hen91	Fritz Henglein, Efficient type inference for higher-order binding-time analysis, Proceedings of the 5th ACM conference on Functional programming languages and computer architecture, p.448-472, June 1991, Cambridge, Massachusetts, United States
	Hen92	Fritz Henglein, Global tagging optimization by type inference, Proceedings of the 1992 ACM conference on LISP and functional programming, p.205-215, June 22-24, 1992, San Francisco, California, United States
	HH92	Laurie J. Hendren , Joseph Hummell , Alexandru Nicolau, Abstractions for recursive pointer data structures: improving the analysis and transformation of imperative programs, Proceedings of the ACM SIGPLAN 1992 conference on Programming language design and implementation, p.249-260, June 15-19, 1992, San Francisco, California, United States
	JP90	Martin Jourdan , D. Parigot, Techniques for improving grammar flow analysis, Proceedings of the third European symposium on programming on ESOP '90, p.240-255, May 1990, Copenhagen, Denmark
	JPP94	Richard Johnson , David Pearson , Keshav Pingali, The program structure tree: computing control regions in linear time, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, p.171-185, June 20-24, 1994, Orlando, Florida, United States
	LR91	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]
	LR92	William Landi , Barbara G. Ryder, A safe approximate algorithm for interprocedural aliasing, Proceedings of the ACM SIGPLAN 1992 conference on Programming language design and implementation, p.235-248, June 15-19, 1992, San Francisco, California, United States
	LRF94	Y.-f. Lee, B. G. Ryder, and M. E. Fiuczynski. Region analysis: A parallel elimination method for data flow analysis. In International Conference on Computer Languages, pages 31-42. IEEE Computer Society, May 1994.
	OJ95	R. O'Callahan and D. Jackson. Detecting shared representations using type inference. Technical Report CMU-CS-95-202, School of Computer Science, Carnegie-Mellon University, September 1995.
	OJ96	R. O'Callahan and D. Jackson. Practical program understanding with type inference. Technical Report CMU-CS-96-130, School of Computer Science, Carnegie-Mellon University, May 1996.
	RHS95	Thomas Reps , Susan Horwitz , Mooly Sagiv, Precise interprocedural dataflow analysis via graph reachability, Proceedings of the 22nd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.49-61, January 23-25, 1995, San Francisco, California, United States [doi>10.1145/199448.199462]
	Ruf95a	Erik Ruf, Context-insensitive alias analysis reconsidered, Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation, p.13-22, June 18-21, 1995, La Jolla, California, United States
	Ruf95b	Erik Ruf, Optimizing sparse representations for dataflow analysis, Papers from the 1995 ACM SIGPLAN workshop on Intermediate representations, p.50-61, January 23-25, 1995, San Francisco, California, United States
	Ste95	Bjarne Steensgaard, Sparse functional stores for imperative programs, Papers from the 1995 ACM SIGPLAN workshop on Intermediate representations, p.62-70, January 23-25, 1995, San Francisco, California, United States
	Ste96a	Bjarne Steensgaard, Points-to Analysis by Type Inference of Programs with Structures and Unions, Proceedings of the 6th International Conference on Compiler Construction, p.136-150, April 24-26, 1996
	Ste96b	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]
	WCES94	D. Weise, R. F. Crew, M. Ernst, and B. Steensgaard. Value dependence graphs: Representation without taxation. Technical Report MSR-TR-94-03, Microsoft Research, Redmond, WA, April 13, 1994.
	WL95	Robert P. Wilson , Monica S. Lam, Efficient context-sensitive pointer analysis for C programs, Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation, p.1-12, June 18-21, 1995, La Jolla, California, United States
	ZRL96a	Sean Zhang , Barbara G. Ryder , William Landi, Program decomposition for pointer aliasing: a step toward practical analyses, Proceedings of the 4th ACM SIGSOFT symposium on Foundations of software engineering, p.81-92, October 16-18, 1996, San Francisco, California, United States
	ZRL96b	S. Zhang, B. G. Ryder, and W. Landi. Program decomposition for pointer-induced alia.sing analysis. Technical Report LCSR-TR-259, Laboratory for Computer Science, Rutgers University, March 1996.

CITED BY 15

	Philip A. Stocks , Barbara G. Ryder , William A. Landi , Sean Zhang, Comparing flow and context sensitivity on the modification-side-effects problem, ACM SIGSOFT Software Engineering Notes, v.23 n.2, p.21-31, March 1998
	Amer Diwan , Kathryn S. McKinley , J. Eliot B. Moss, Type-based alias analysis, ACM SIGPLAN Notices, v.33 n.5, p.106-117, May 1998
	Karl Crary , Stephanie Weirich , Greg Morrisett, Intensional polymorphism in type-erasure semantics, ACM SIGPLAN Notices, v.34 n.1, p.301-312, Jan. 1999
	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
	Amer Diwan , Kathryn S. McKinley , J. Eliot B. Moss, Using types to analyze and optimize object-oriented programs, ACM Transactions on Programming Languages and Systems (TOPLAS), v.23 n.1, p.30-72, Jan. 2001
	Sean Zhang , Barbara G. Ryder , William A. Landi, Experiments with combined analysis for pointer aliasing, ACM SIGPLAN Notices, v.33 n.7, p.11-18, July 1998
	Greg Morrisett , David Walker , Karl Crary , Neal Glew, From system F to typed assembly language, Proceedings of the 25th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.85-97, January 19-21, 1998, San Diego, California, United States
	Karl Crary , Stephanie Weirich, Flexible type analysis, ACM SIGPLAN Notices, v.34 n.9, p.233-248, Sept. 1999
	Ben-Chung Cheng , Wen-Mei W. Hwu, Modular interprocedural pointer analysis using access paths: design, implementation, and evaluation, ACM SIGPLAN Notices, v.35 n.5, p.57-69, May 2000
	Sanjay Ghemawat , Keith H. Randall , Daniel J. Scales, Field analysis: getting useful and low-cost interprocedural information, ACM SIGPLAN Notices, v.35 n.5, p.334-344, May 2000
	John L. Ross , Mooly Sagiv, Building a bridge between pointer aliases and program dependences, Nordic Journal of Computing, v.5 n.4, p.361-386, Winter 1998
	Barbara G. Ryder , William A. Landi , Philip A. Stocks , Sean Zhang , Rita Altucher, A schema for interprocedural modification side-effect analysis with pointer aliasing, ACM Transactions on Programming Languages and Systems (TOPLAS), v.23 n.2, p.105-186, March 2001
	Kwangkeun Yi , Sukyoung Ryu, A cost-effective estimation of uncaught exceptions in standard ML programs, Theoretical Computer Science, v.277 n.1-2, p.185-217, April 28, 2002
	Karl Crary , Stephanie Weirich , Greg Morrisett, Intensional polymorphism in type-erasure semantics, Journal of Functional Programming, v.12 n.6, p.567-600, November 2002