Interprocedural Analysis and Optimization (2 lectures)
Ten Hardware Features That Affect Optimization
The Last Lecture
Lecture by Lecture Bibliography
Here is a breakdown, by lecture, of relevant reading material.
I am certain that you can gain all of the requisite knowledge
by attending lecture, asking clever questions, and reading the sources
mentioned in the slides.
Still, some of you may want more material...
Lecture 1 (Introduction)
General Background - see a good undergraduate textbook
Results on inline substitution: "An experiment with
inline substitution", K.D. Cooper, M.W. Hall, and L. Torczon,
Software--Practice and Experience 21(6), June 1991.
Lecture 2 (Experience paper on Fortran H)
"Improved Optimization of Fortran Object Programs,"
R.G. Scarborough and H.G. Kolsky,
IBM Journal of Research and Development, pages 660-676,
November, 1980.
Lecture 3 (Local Value Numbering)
Chapter 8 of Engineering a Compiler
Original algorithm was described in Cocke and Schwartz's famous
unpublished work, "Programming Langauges and Their Compilers".
Lecture 4
Chapter 8 of Engineering a Compiler
"Value Numbering," P. Briggs, K.D. Cooper, and L.T. Simpson,
Software--Practice and Experience, 27(6), June 1997
"Global Common Subexpression Elimination", J. Cocke,
Proceedings of a Symposium on Compiler Construction,
SIGPLAN Notices 5(7), pages 20-24, July 1970.
Lecture 5
Chapter 8 of Engineering a Compiler
"Global Common Subexpression Elimination", J. Cocke,
Proceedings of a Symposium on Compiler Construction,
SIGPLAN Notices 5(7), pages 20-24, July 1970.
Lecture 6
"Global Data Flow Analysis and Iterative Algorithms", J.B. Kam
and J.D. Ullman, Journal of the ACM 23(1), January 1976,
pages 158-171.
"Automatic Synthesis of Invariant Assertions", P. Cousot and
R. Cousot, Proceedings of the 1977 Symposium on Artificial
Intelligence and Programming Languages, ACM SIGART, 1977,
pages 1-12.
Lectures 7 & 8
Chapter 9 of Engineering a Compiler
"A Survey of Data-flow Analysis Techniques," Ken kennedy,
in Program Flow Analysis: Theory and Applications
(N.D. Jones and S.S. Muchnick, editors), Prentice-Hall, 1981.
Lecture 9
Chapter 9 of Engineering a Compiler
"Efficiently Computing Static Single Assignment Form and the
Control Dependence Graph", R. Cytron, J. Ferrante, B.K. Rosen, M.N.
Wegman, and F.K. Zadeck, ACM TOPLAS 13(4), October 1991, pages
451--490.
"Practical Improvements to the Construction and Destruction of
Static Single Assignment Form", P. Briggs, K.D. Cooper, T.J. Harvey,
and L.T. Simpson, Software--Practice and Experience 28(8)
July 1998, pages 859--891.
Lecture 10
The dead code elimination algorithm is from the original SSA paper,
Cytron et al. listed under Lecture 9, with corrections from Rob
Shillner (the use of reverse dominance frontiers and postdominators to
reconnect branches).
Chapter 10 of Engineering a Compiler presents both algorithms.
The constant propagation algorithm is from "Constant Propagation
with Conditional Branches," M.N. Wegman and F.K. Zadeck, ACM Transactions
on Programming Languages and Systems, 13(2), April 1991, pages 181--210.
Lecture 11
The unpublished survey paper, particularly Section 6 (on readings page)
Section 10.2 of Engineering a Compiler
Lecture 12
"Lazy Code Motion," J. Knoop, O. Ruthing, and B. Steffen,
Proceedings of the ACM SIGPLAN '92 Conference on Programming Language
Design and Implementation (PLDI), SIGPLAN Notices 27(7), pages 224-234,
July 1992.
"A variation of Knoop, Ruthing, and Steffen's `Lazy Code Motion',"
K.H. Drechsler and M.P. Stadel, SIGPLAN Notices 28(5), pages 29-3,
May 1993.
Section 10.3.2 of Engineering a Compiler
Lecture 13
Section 10.3.1 of Engineering a Compiler
The "web" of the original CLEAN implementation (on the Readings page)
Lecture 14
"Effective Partial Redundancy Elimination," P. Briggs and K.D. Cooper,
Proceedings of the ACM SIGPLAN '94 Conference on Programming Language
Design and Implementation (PLDI), SIGPLAN Notices 29(6), June 1994,
pages 159-170.
Lecture 16
"Operator Strength Reduction," K.D. Cooper, L.T. Simpson and C.A. Vick,
ACM Transactions on Programming Languages and Systems (TOPLAS), 23(5),
September 2001, pages 603--625.
Lecture 17
Hoisting: See Fischer & LeBlanc's book Crafting a Compiler or
Chapter 10 of Engineering A Compiler
Cross-jumping: See Wulf et al's book on the Bliss compiler
Procedure Abstraction: Fraser, Myers, and Wendt in PLDI 1984 and
Cooper and McIntosh in PLDI 1998
Superoptimizer" "Superoptimizer -- A Look at the Smallest Program",
H. Massalin, Proceedings of the Second International Conference
on Architectural Support for Programming Languages and Systems
(ASPLOS II), Palo Alto, CA, USA, 1987, pages 122-126.
Linearization: "A Catalogue of Program Optimizations", F. Allen and J.
Cocke, in Design and Optimization of Compilers, Prentice-Hall,
1972, pages 1-30.
List Scheduling:
"Non-local Instruction Scheduling with Limited Growth,
K.D. Cooper and P.J. Schielke,
Proceedigns of the 1998 ACM Workshop
on Languages, Compilers, and Tools for Embedded Systems (LCTES),
Montreal, CA, June 1998, pages 193--207.
Adaptive Compilation (for code size):
"Optimizing for Reduced Code Space usinng Genetic Algorithms",
K.D. Cooper, P.J. Schielke, and D. Subramanian,
Proceedigns of the 1999 ACM Workshop
on Languages, Compilers, and Tools for Embedded Systems (LCTES),
Atlanta, GA, USA, May 1999, pages 1--9.
Lecture 18
"Optimization of Range Checking," V. Markstein, J. Cocke, P. Markstein,
Proceedings of the 1982 ACM SIGPLAN Conference on Compiler
Construction, SIGPLAN Notices, 17(6), June 1982), pages 114-119.
"Optimizing Array Bound Checks Using Flow Analysis," R. Gupta,
ACM Letters on Programming Languages and Systems (LOPLAS),
2(1-4), March 1983, pages 135-150.
Lecture 19
"Detecting Equality of Variables in Programs," B. Alpern, M.N. Wegman,
and F.K. Zadeck, Proceedings of the 15th ACM SIGPLAN-SIGACT Symposium
on Principles of Programming Languages (POPL),
January 1988, pages 1--11.
Lecture 20
List in development, see Survey paper (# 2 on Readings page) if in a hurry
Lecture 21 (Code Motion for Control Structures)
"Code Motion of Control Structures in High-level Languages,"
R. Cytron, A. Lowry, and F.K. Zadeck, Proceedings of the 13th
ACM SIGPLAN SIGACT Symposium on Principles of Programming Languages,
January, 1986, pages 70--84.
Lecture 22 (Loop Transformations)
A variety of sources; for starters see the Loop Transformations
section of the survey paper (Cooper, McKinley and Torczon on the Readings page)
and the survey by Bacon, Graham, and Sharp.
The register promotion work is from
"Register Promotion in C Programs," Keith D. Cooper and John Lu,
Proceedings of the 1997 SIGPLAN Conference on Programming Language
Design and Implementation SIGPLAN Notices 32(6), June, 1997, pages 308-319.
See also the papers by Sastry & Ju and by Chow et al. in the 1998 PLDI
Proceedings.
Lecture 23
Todd's paper in the LACSI 2003 Proceedings, to be posted ...
Lecture 24 (Profile Guided Code Positioning)
"Profile Guided Code Positioning," K. Pettis and R.C. Hansen,
Proceedings of the 1990 ACM SIGPLAN Conference on Programming
Language Design and Implementation (PLDI), SIGPLAN Notices 25(6),
June 1990, pages 16--27. (White Plains, NY, USA)
Lecture 25 (Register Allocation)
See bibliography on last slide of the lecture ...
Lecture 30 (Dynamo)
"Dynamo: A Transparent Dynamic Optimization System,", Vasanth
Bala, Evelyn Deuesterwald, and Sanjeev Banerjia, Proceedings
of the 2000 ACM SIGPLAN Conference on Prorgamming Langauge
Design and Implementation (PLDI) , SIGPLAN Notices, 35(5),
May 2000, pages 1-12.
Lecture 31 (Scheduling, part 1)
Chapter 12, Engineering a Compiler
"Non-local instruction scheduling with limited code growth," Keith
D. Cooper and Philip J. Schielke, Proceedings of the 1998 ACM
SIGPLAN Workshop on Languages, Compilers, and Tools for Embedded
Systems (LCTES), Montreal, Quebec, CA, June 1988, pages 193--207.
"The Superblock; An Effective Technique for VLIW and Superscalar
Compilation,"
Wen-Mei W. Hwu, Scott A. Mahlke, William Y. Chen, Pohua P. Chang,
Nancy J. Warter, Roger A Bringmann, Ronald G. Ouellette, Richard E.
Hank, John G. Holm, and Daniel M. Lavery, Journal of Supercomputing --
Special Issue on Instruction Level Parallelism, 7(1), pages 229-248,
May 1993.
"Trace Scheduling: A Technique For Global Micorcode Compaction",
Joseph A. Fisher, IEEE Transactions on ComputersC-30(7),
pages 478-490, July 1981.
Lecture 32 (Scheduling, part 2)
"Software Pipelining: An Effective Scheduling Technique for
VLIW Machines," Monica Lam, Proceedings of the 1988 ACM
SIGPLAN Conference on Programming Language Design and Implementation
(PLDI), June 1988, pages 318-328.
"Improved Software Pipelining for Superscalar Architectures,"
Edmar Wienskoski, Ph.D. Thesis, Department of Computer Science,
Rice University, April 1998.
Lecture 33 (Interprocedural Analysis & Optimization, 2 lectures)
Several papers cited in the slides are listed for earlier
lectures.
This list could be longer; instead, it is representative.
Inline substitution:
"An Experiment with Inline Substitution", Keith D. Cooper,
Mary W. Hall, and Linda Torczon Software--Practice and
Experience 21(6), June 1991, pages 581-601.
"A Study of a C Function Inliner," Jack W. Davidson and Anne
Holler, Software--Practice and Experience 19(1), January
1988, pages 79-97.
"Subprogram Inlining: A Study of Its Effects on Program Execution
Time", Jack W. Davidson and Anne Holler, IEEE Transactions on
Software Engineering, 18(2) 1992, pages 89-102.
Classic interprocedural problems:
See "Interprocedural Analysis and Optimization," Keith D.
Cooper, Mary W. Hall, Ken Kennedy, & Torczon, Communications
on Pure and Applied Mathematics 48, 1995 (pages 947-1003).
The bibliography of this paper list myriad relevant papers.
Call Graph Construction:
"Constructing the Call Graph of a Program," Barbara Ryder,
IEEE Transactions on Software Engineering, May 1979.
"Constructing the Procedure Call Multigraph,", David Callahan,
Alan Carle, Mary W. Hall and Ken Kennedy, IEEE Transactions on
Software Engineering, 16(4), Apr 1990.
"An Interval-based Approach to Exhaustive and Incremental
Interprocedural Analysis," Michael Burke, ACM TOPLAS
12(3), July 1990.
"Efficient Call Graph Analysis", Mary W. Hall and Ken Kennedy,
ACM LOPLAS 1(3), September 1992.
Pointer Analysis:
"A Scheme for Interprocedural Modiciation Side Effect Analysis with
Pointer Aliasing," Barbara G. Ryder, William Landi, Philip A Stocks,
Sean Zhang, and Rita Altucher, ACM TOPLAS 23(2), March 2001.
"Unification-based Pointer Analysis with Directional Assignments,"
Manuvir Das, Proceedings of the ACM SIGPLAN 2000 Conference
on Programming Language Design and Implementation (PLDI),
SIGPLAN Notices, 35(5), May 2000, pages 35-46.
Interprocedural register allocation:
"Minimizing Register Usage Penalty at Procedure Calls,"
Fred C. Chow, Proceedings of the ACM SIGPLAN 1988 Confernce
on Programming Language Design and Implementation (PLDI),
June 1988, pages 85-94.
"Register Windows versus Register Allocation,",
David W. Wall, Proceedings of the ACM SIGPLAN 1988 Confernce
on Programming Language Design and Implementation (PLDI),
June 1988, pages 67--78.
Impact:
"Interprocedural Constant Propgation: A Study of Jump Function
Implementations," Daniel Grove and Linda Torczon,
Proceedings of the ACM SIGPLAN 1993 Conference on Programming
Language Design and Implementation, (PLDI)
ACM SIGPLAN Notices 28(6), June 1993, pages 90-99.
"Interprocedural Constant Propagation: An Empirical Study,"
Robert Metzger and Sean Stroud, ACM LOPLAS, 2(1-4),
1993, pages 213-232.
"An Analysis of Inline Substitution For a Structured Programming
Language," Robert Scheifler, Communications of the ACM, 20(9),
September, 1977, pages 647-654.
Access to online copies of the papers can be had through a number of
sources.
TOPLAS, SIGPLAN Notices, ACM Conferences -- ACM Digital Library
This site is maintained by Keith D. Cooper.
He is a terrible e-mail correspondent.
