Dan Grove
ABSTRACT
An implementation of interprocedural constant propagation must model the transmission of values through each procedure. In the framework proposed by Callahan, Cooper, Kennedy, and Torczon in 1986, this intraprocedural propagation is modeled with a jump function. While Callahan et al. propose several kinds of jump functions, they give no data to help choose between them. This paper reports on a comparative study of jump function implementations. It shows that different jump functions produce different numbers of useful constants; it suggests a particular function, called the pass-through parameter jump function, as the most cost-effective in practice.
- 1.Bowen Alpern, Mark N. Wegman, and F. Kenneth Zadeck. Detecting equality of variables in programs. In Conference Record of the Fifteenth Annual A CM Symposium on Principles of Programming Languages, pages 1-11, January 1988. Google Scholar
Digital Library
- 2.Robert A. Ballance, Arthur B. Maccabe, and Karl J. Ottenstein. The program dependence web: A representation supporting control, data, and demand-driven interpretation of imperative languages. $IGPLAN Notices, 25(6):257-271, June 1990. Proceedings of the A CM SIGPLAN '90 Conference on Programming Language Design and Implementation. Google ScholarDigital Library
- 3.Michael Burke and Ron Cytron. Interprocedural dependence analysis and parallelization. SIC- PLAN Notices, 21(7):162-175, July 1986. Proceedings of the A CM $IGPLAN '86 Symposium on Compiler Construction. Google ScholarDigital Library
- 4.David Callahan, Keith D. Cooper, Ken Kennedy, and Linda Torczon. Interprocedural constant propagation. $IGPLAN Notices, 21(7):152-161, July 1986. Proceedings of the A CM $IGPLAN '86 Symposium on Compiler Construction. Google ScholarDigital Library
- 5.Keith D. Cooper, Mary W. Hall, Robert T. Hood, Ken Kennedy, Kathryn McKinley, John Mellor-Crummey, Linda Torczon, and Scott K. Warren. The ParaScope parallel programming environment. Proceedings of the IEEE, February 1993. (to appear).Google ScholarCross Ref
- 6.Keith D. Cooper, Mary W. Hall, and Ken Kennedy. Procedure cloning. In Proceedings of the IEEE Computer Society 1992 International Conference on Computer Languages, pages 96- 105, April 1992.Google ScholarCross Ref
- 7.Keith D. Cooper and Ken Kennedy. Interprocedural side-effect analysis in linear time. SIC- PLAN Notices, 23(7):57-66, July 1988. Proceedings of the A CM $iGPLAN '88 Conference on Programming Language Design and Implementation. Google ScholarDigital Library
- 8.Ron Cytron, Jeanne Ferrante, Barry K. Rosen, Mark N. Wegman, and F. Kenneth Zadeck. Efficiently computing static single assignment form and the control dependence graph. A CM Transactions on Programming Languages and Systems, 13(4):451-490, October 1991. Google ScholarDigital Library
- 9.Rudolf Eigenmann and William Blume. An effectiveness study of parallelizing compiler techniques. In Proceedings of the 1991 International Conference on Parallel Processing, St. Charles, IL, August 1991.Google Scholar
- 10.Paul Havlak. Interprocedural Symbolic Analysis. PhD thesis, Rice University, expected May, 1993. Google ScholarDigital Library
- 11.Matthew S. Hecht. Flow Analysis of Computer Programs. Programming Languages Series. Elsevier North-Holland, Inc., 52 Vanderbilt Avenue, New York, NY 10017, 1977. Google ScholarDigital Library
- 12.Gary A. Kildall. A unified approach to global program optimization. In Conference Record of the A CM Symposium on Principles of Programming Languages, pages 194-206, October 1973. Google ScholarDigital Library
- 13.Robert Metzger and Sean Stroud. Interprocedural constant propagation: An empirical study. (To appear in A CM Letters on Programming Languages and Systems). Google ScholarDigital Library
- 14.Zhiyu Shen, Zhiyuan Li, and Pen-Chung Yew. An empirical study of FORTRAN programs for parallelizing compilers. IEEE Transactions on Parallel and Distributed Systems, 1(3):356-364, July 1990. Google ScholarDigital Library
- 15.Jaswinder P. Singh and John Hennessy. An empirical investigation of the effectiveness of and limitations of automatic parallelization. In Proceedings of the International Symposium on Shared Memory Multiprocessors, Tokyo, japan, April 1991.Google Scholar
- 16.Mark N. Wegman and F. Kenneth Zadeck. Constant propagation with conditional branches. A CM Transactions on Programming Languages and Systems, 13(2):181-210, April 1991. Google ScholarDigital Library
Index Terms
- Interprocedural constant propagation: a study of jump function implementation
Recommendations
Interprocedural constant propagation: a study of jump function implementation
An implementation of interprocedural constant propagation must model the transmission of values through each procedure. In the framework proposed by Callahan, Cooper, Kennedy, and Torczon in 1986, this intraprocedural propagation is modeled with a jump ...
Interprocedural constant propagation: an empirical study
Constant propagation is an optimization that substitutes values for names. Interprocedural constant propagation performs this substitution throughout an entire program, propagating constant values across procedure boundaries. CONVEX Computer Corporation ...
Comments