Michael Burke
Ron Cytron
Abstract
We present a method that combines a deep analysis of program dependences with a broad analysis of the interaction among procedures. The method is more efficient than existing methods: we reduce many tests, performed separately by existing methods, to a single test. The method is more precise than existing methods with respect to references to multi-dimensional arrays and dependence information hidden by procedure calls. The method is more general than existing methods: we accommodate potentially aliased variables and structures of differing shapes that share storage. We accomplish the above through a unified approach that integrates subscript analysis with aliasing and interprocedural information.
- 1 John R. Allen, "Dependence Analysis for Subscript Variables and Its Application to Program Transformations", Rice Ph.D. Thesis, April 1983. Google Scholar
Digital Library
- 2 Utpal Banerjee, "Data Dependence in Ordinary Programs", M,S. Thesis, University of Illinois at Urbana-Champaign, DCS Report No. UIUCDCS-R-76-837, November 1976.Google Scholar
- 3 Utpal Banerjee, "Speedup of Ordinary Programs", Ph.D. Thesis, University of Illinois at Urbana- Champaign, DCS Report No. UIUCDCS-R-79-989, October 1979. Google ScholarDigital Library
- 4 John Banning, "An Efficient Way to Find the Side Effects of Procedure Calls and the Aliases of Variables", Conf. Rec. Seventh ACM Symposium on Principles of Programming Languages, January 1980. Google ScholarDigital Library
- 5 Michael Burke, "An Interval Analysis Approach Toward Interprocedural Data Flow", IBM Research Report RC 10640, July 1984.Google Scholar
- 6 Michael Burke and Ron Cytron, "Interprocedural Dependence Analysis and Parallelization", IBM Research Report RCI 1794, April, 1986.Google Scholar
- 7 Keith Cooper, "Interprocedural Data Flow Analysis in a Programming Environment", Rice Ph.D. Thesis, April 1983. Google ScholarDigital Library
- 8 Keith Cooper, "Analyzing Aliases of Reference Formal Parameters", Conf. Rec. Twelfth ACM Symposium on Principles of Programming Languages, 281-290, January 1985. Google ScholarDigital Library
- 9 Keith Cooper and Ken Kennedy, "Efficient Computation of Flow Insensitive Interproeedurai Summary Information", Proceedings of the SIGPLAN 84 Symposiumon Compiler Construction, June 1984. Google ScholarDigital Library
- 10 Ron Cytron, "Compile-time Scheduling and Optimization for Asynchronous Machines", Ph.D. Thesis, University of Illinois at Urbana- Champaign, August, 1982.Google Scholar
- 11 Christopher A. Huson, "An In-Line Subroutine Expander for Parafrase", M.S. Thesis, University of Illinois at Urbana-Champaign, 1982.Google Scholar
- 12 G. KildaU, "A Unified Approach to Program Optimization", Conf, Rec. First A CM Symposium on Principles of Programming Languages, 194-206, October 1973. Google ScholarDigital Library
- 13 David J. Kuck, The Structure of Computers and Computations, Volume 1, John Wiley and Sons, New York, 1978. Google ScholarDigital Library
- 14 Bruce R. Leasure, "Compiling Serial Languages for Parallel Machines", M.S. Thesis, University of Illinois at Urbana-Champaign, 1976.Google Scholar
- 15 J.H. Reif and H.R. Lewis, "Symbolic Evaluation and the Global Value Graph", Conf. Rec. Fourth ACM Symposium on Principles of Programming Languages, January 1977. Google ScholarDigital Library
- 16 Robert Shostak, "Deciding Linear Inequalities by Computing Loop Residues", Journal of the Association for Computing Machinery, Vol. 28, No. 4, October 1981. Google ScholarDigital Library
- 17 Remi J. Triolet, "Contribution a la Parellisation Automatique de Programmes Fortran Comportant des Appels de Procedure", Ph.D. Thesis, L'Universite Pierre et Marie Curie (Paris VI), December 1984.Google Scholar
- 18 Mark Wegman and Ken Zadeck, "Constant Propagation with Conditional Branches", Conf. Rec. Twelfth ACM Symposium on Principles of Programming Languages, 291-299, January 1985. Google ScholarDigital Library
- 19 Michael J. Wolfe, "Optimizing Supercompilers for Supercomputers", Ph.D. Thesis, University of Illinois at Urbana-Champaign, 1982. Google ScholarDigital Library
Index Terms
- Interprocedural dependence analysis and parallelization
Recommendations
Interprocedural dependence analysis and parallelization
20 Years of the ACM SIGPLAN Conference on Programming Language Design and Implementation 1979-1999: A SelectionThe area of dependence analysis has served as grounds for fruitful research as well as practical implementation. Compilers and tools that utilize dependence information can generate code that takes advantage of parallel resources and storage hierarchies ...
Interprocedural dependence analysis and parallelization
SIGPLAN '86: Proceedings of the 1986 SIGPLAN symposium on Compiler constructionWe present a method that combines a deep analysis of program dependences with a broad analysis of the interaction among procedures. The method is more efficient than existing methods: we reduce many tests, performed separately by existing methods, to a ...
Interprocedural pointer alias analysis
We present practical approximation methods for computing and representing interprocedural aliases for a program written in a language that includes pointers, reference parameters, and recursion. We present the following contributions: (1) a framework ...
Comments