This page contains both the PDF format copies of the lecture notes, and
a lecture-by-lecture bibliography for the class.
Some of the reading materials are available by direct link;
others will require
you to visit the ACM Digital Library
or the university's library.
Note: if you visit the ACM Digital Library
from the campus network, you should be able to download the papers under
Rice's subscription.
Finally, you can find most of the papers on
Google Scholar.
Look up the paper by author or title, then check to see if it has a copy of the
actual document.
General Background - see a good undergraduate textbook
Chapter 8, EaC2e
Read the Wikipedia entry on Compiler Optimization
The results on inline substitution in the lecture are taken from
K.D. Cooper, M.W. Hall, and L. Torczon,
"An Experiment with Inline Substitution",
Software--Practice and
Experience 21(6), June 1991, pages 581-601.
(DOI)
P. Briggs, K.D. Cooper, and L.T. Simpson, "Value Numbering,"
Software-Practice and Experience, 27(6), July 1997.
(DOI)
(local copy)
J. Cocke, "Global Common Subexpression Elimination,"
Proceedings of a Symposium on Compiler Construction,
Sigplan Notices 5(7), 1970, pages 20--24.
(DOI)
G. Kildall, "A Unified Approach to Global Optimization",
Proceedings of the 1st POPL, 1973,
(DOI)
Ken Kennedy, "A Survey of Data Flow Analysis Techniques", in
Program Flow Analysis: Theory and Applications
(N.D. Jones and S.S Muchnick, editors), Prentice-Hall, 1981.
(TR version)
J.B. Kam and J.D. Ullman, "Global Data-flow Analysis and
Iterative Algorithms", JACM 23(1), January 1976, pages 158-171.
(DOI)
J.B. Kam and J.D. Ullman, "Monotone Data-flow Analysis Frameworks",
Acta Informatica, 7(3), pages 305-317, 1977.
(URL)
Shift register example is from Cooper's thesis, Rice 1983.
K. Pettis and R.C. Hansen, "Profile Guided Code Positioning,"
Proceedings of the ACM SIGPLAN '90 Conference on Programming
Language Design and Implementation (PLDI),
White Plains, NY, July 1990,
pages 16-27. (Also SIGPLAN Notices 25(6).)
(DOI)
K.D. Cooper, M.W. Hall, and L. Torczon,
"An Experiment with Inline Substitution",
Software--Practice and
Experience 21(6), June 1991, pages 581-601.
(DOI)
J.W. Davidson and A. Holler, "A Study of a C Function Inliner,"
Software--Practice and Experience 19(1), January
1988, pages 79-97.
(DOI)
J.W. Davidson and A. Holler,
"Subprogram Inlining: A Study of Its Effects on Program Execution
Time", IEEE Transactions on
Software Engineering, 18(2) 1992, pages 89-102.
(DOI)
K. Cooper, M. Hall, L. Torczon, "Unexpected Side Effects of Inline
Substitution: A Case Study," ACM Letters on Programming
Languages and Systems (LOPLAS) 1(1).
(DOI)
P. Zhao and J.N. Amaral, "To Inline or Not to Inline? Enhanced
Inlining Decions," Proceedings of the 4th Workshop on Languages
and Compilers for Parallel Computing (LCPC), October 2003, pages
405-419.
(URL)
J.E. Ball, "Predicting the Effects of Optimization on a Procedure
Body,"Proceedings of the 1979 ACM SIGPLAN Symposium on Compiler
Construction (SIGPLAN '79), 1979 pages 214-220.
(DOI)
M. Wegman and F.K. Zadeck, "Constant Propagation with Conditional
Branches", ACM Transactions on Programming Languages and Systems
(TOPLAS) 13(2), pages 181-210.
(DOI)
K. Cooper, T. Harvey, and T. Waterman, "An Adaptive Strategy
for Inline Substitution", Proceedings of CC 2008, pages
69-84
(URL)
"Improved Optimization of Fortran Object Programs,"
R.G. Scarborough and H.G. Kolsky,
IBM Journal of Research and Development, pages 660-676,
November, 1980.
(local copy)
M. Auslander and M. Hopkins, "An Overview of the PL.8 Compiler,",
Proceedings of the 1982 ACM SIGPLAN Symposium on Compiler
Construction, Boston, MA, USA, June 1982. (Also, SIGPLAN
Notices 17(6))
(DOI)
J. Cocke and P. Markstein, "Measurement of Program Improvement
Algorithms," Proceedings of the 1980 IFIP Congress,
North Holland Publishers, 1980.
(local copy)
(Also, IBM RC 8111, 1980)
F.E. Allen and J. Cocke, "A Catalogue of Optimizing Transformations,"
in Design and Optimization of Compilers, R. Rustin, ed.,
Prentice-Hall, Englewood Cliffs, NJ, 1972, pages 1-30.
(local copy)
D.R. Perkins and R.L. Sites, "Machine-independent PASCAL Code
Optimization," Proceedings of the 1979 SIGPLAN Symposium on
Compiler Construction, 1979, pages 201-207.
(DOI)
Compiler-Based Code Improvement Techniques, an unpublished
paper by K.D. Cooper, K.S. McKinley, and L. Torczon
(local copy)
K.D. Cooper, T.J. Harvey, and K. Kennedy, "A Simple, Fast
Dominator Algorithm," Rice CS TR 06-38870, January 2006.
(local copy)
(see also Section 9.5.2 in EaC2e)
M. Wegman and F.K. Zadeck, "Constant Propagation with Conditional
Branches", ACM Transactions on Programming Languages and Systems
(TOPLAS) 13(2), pages 181-210.
(DOI)
"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.
(DOI)
"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. (on readings page)
(DOI)
R.M. Shapiro and H. Saint, "The Representation of Algorithms,"
RADC-TR-69-313, Voulume II, September 1969.
(URL)
This report is often referenced but almost never seen.
I had not seen a copy until I obtained this one in 2012.
M. Wegman and F.K. Zadeck, "Constant Propagation with Conditional
Branches", ACM Transactions on Programming Languages and Systems
(TOPLAS) 13(2), pages 181-210.
(DOI)
Section 9.3.6 in EaC2e (SSCP)
Section 10.7.1 in EaC2e (SCCP)
See also: C. Click and K.D. Cooper, "Combining Analyses, Combining
Optimizataions,"
ACM Transactions on Programming Languages and Systems (TOPLAS),
17(2), pages 181-196.
(DOI)
J. Knoop, O. Ruthing, and B. Steffen,
"Lazy Code Motion",
Proceedings of ACM SIGPLAN '92 Conference on Programming Language
Design and Implementation (PLDI), June 199,
(DOI)
K-H. Drechsler and M.P. Stadel,
"A variation of Knoop, Ruthing, and Steffen's Lazy Code Motion",
ACM SIGPLAN Notices, 28(5), May 1993
(DOI)
Section 10.3.1 of EaC2e
L. T. Simpson, "Value-Driven Redundancy Elimination," Ph.D. Thesis,
Rice University Department of Computer Science, April 1996. (Also
Rice CS TR 96-308)
R. Kennedy, S. Chan, S.M. Liu, R. Lo, P. Tu, and F.Chow,
“Partial Redundancy Elimination in SSA Form”,
ACM Transactions on Programming Languages and Systems,
21(3), May 1999, pages 627-676.
DOI
The slides include citations to many papers on prior art.
Benoit Boissinot, Alain Darte, Benoit Dupont de Dinechin, Christophe
Guillon, and Fabrice Rastello, "Revisiting Out-of-SSA Translation for
Correctness, Code Quality, and Efficiency", CGO 2009, March 2009.
(DOI)
"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. (on readings page)
(DOI)
R.E. Tarjan, "Depth-first search and linear graph algorithms,"
SIAM Journal of Computing1(2), 1972, pages 146-160.
(DOI)
See also
Proceedings of the 12th Annual Symposium on Switching and
Automata Theory, IEEE, 1971, pages 114-121.
(DOI)
See also the chapter, "Reduction of Operator Strength" by F.E. Allen,
J. Cocke, and K. Kennedy in Program Flow Analysis, N.D. Jones and
S.S. Muchnick, editors. (copy in Fondren Library)
K.D. Cooper, L.T. Simpson, and C.A. Vick, "Operator Strength Reduction",
ACM TOPLAS, 23(5), September 2001, pages 603-625.
(DOI)
This algorithm relies heavily on Tarjan's paper on Depth-First Search
(citation above)
(DOI)
If you are interested in the data-flow school of strength reduction,
see:
J. Issac and D.M. Dhamdhere, "A Composite Algorithm for Strength
Reduction and Code Movement", International Journal of Computer
and Information Sciences, 9(3), 1980, pages 243-273.
(DOI)
J. Knoop, O. Ruthing, and B. Steffen, "Lazy Strength Reduction,"
Journal of Programming Languages, 1(1), 1993, pages 71-91.
(CiteSeer or local copy))
P. Briggs and K.D. Cooper, "Effective Partial Redundancy Elimination,"
Proceedings of PLDI 94, June 1994, pages 159-170.
(DOI)
R.W. Floyd, "An Algorithm for Coding Efficient Arithmetic Operations,"
Communications of the ACM, 4(1), January 1961, pages 42-51.
(DOI)
D. Frailey, "Expression Optimization Using Unary Complement Operators,"
Proceedings of a Symposium on Compiler Optimization,
1970, pages 67--85.
(DOI)
This lecture refers to the Alpern-Wegman-Zadeck algorithm (AWZ) for
discovering congruent expressions. We haven't covered that material,
but for the interested student ...
B. Alpern, M.N. Wegman, and F.K. Zadeck, "Detecting Equality of
Variables in Programs," Proceedings of the 15th ACM SIGPLAN-SIGACT
Symposium on Principles of Programming Languages (POPL 88),
pages 1-11.
(DOI)
Advice on the Lab, or "What would I do at this point
in the semester?"
K. Cooper, J. Eckhardt, and K. Kennedy, "Redundancy Elimination
Revisited," Proceedings of the 17th Internation Conference on Parallel
Architectures and Compilation Tools (PACT 08), 2008, pages 12-21
(DOI)
P. Briggs, K.D. Cooper, L. Torczon, "Improvements to Graph Coloring
Register Allocation,", ACM Transactions on Programming Languages
and Systems (TOPLAS), 16(3), May 1994, pages 428-455.
(DOI)
G.J. Chaitin, M.A. Auslander, A.K. Chandra, J. Cocke, M.E. Hopkins,
and P.W. Markstein, "Register Allocation Via Coloring,", Computer
Languages, 6(1), January 1981, pages 47--57.
(DOI)
G.J. Chaitin, "Register Allocation and Spilling Via Graph Coloring,"
Proceedings of the ACM SIGPLAN Symposium on Compiler Construction,
SIGNPLAN NOTICES 17(6), June 1982, pages 98--105.
(DOI)
G.J. Chaitin, "Register Allocation and Spilling Via Graph Coloring,"
United States Patent 4,571,678, February 1986.
S.S. Lavrov, "Store Economy in Closed Operator Scheme", Journal
of Computational Mathematics and Mathematical Physics I, 4, 1961,
pages 687-701. (Published in English translation in USSR
Computational Mathematics and Mathematical Physics 1(3), 1962.
pages 810--828.)
A.P. Ershov, "Reduction of the Problem of Memory Allocation in
Programming to the Problem of Coloring the Vertices of Graphs",
Doklady Akademii Naux SSSR 142(4), pages 785-787.
(Published in English translation in Soviet Mathematics 3(1),
January 1962, pages 163-165.)
K.D. Cooper, T.J. Harvey, and L. Torczon, "How to Build an Interference
Graph", Software--Practice and Experience. 28(4), April 1998.
(DOI)
R. Gupta, M.L. Soffa, and T. Steele, "Register Allocation via
Clique Separators," Proceedings of the ACM SIGPLAN 1989 Conference
on Programming Language Design and Implementation (PLDI '89),
July 1989, pages 264-274. (Also, SIGPLAN Notices 24(7))
(DOI)
L. George and A. Appel, "Iterated Register Coalescing,", ACM
TOPLAS, 18(3), May 1996, pages 300-324.
(DOI)
M. Hailperin, "Comparing Conservative Coalescing Criteria,"
ACM TOPLAS 27(3), May 2005, pages 571-582.
(DOI)
C. Fu, and K. Wilken, "A Faster Optimal Register Allocator,",
Proceedings of the 35th Annual ACM/IEEE International Symposium
on Microarchitecture (MICRO 35), pages 245-256.
(DOI)
D.J. Scales, K.H. Randall, S. Ghemawat, and J. Dean,
"The Swift Java Compiler: Design and Implementation",
Compaq Western Research Laboratory (WRL) Research Report 2000/2,
April 2000.
full paper from HP Labs
P. Deutsch and A.M Schiffman, "Efficient Implementation of the
Smalltalk-80 System," ACM Symposium on Principles of Programming
Languages (POPL), 1984.
(DOI)
(Background Reading) A. Kay, "A Personal Computer for
Children of All Ages,", Proceedings of the ACM National
Conference, Boston, MA, Aug. 1972
(DOI)
(Background Reading) J. Lees, "The World in Your Own Notebook," The
Best of Creative Computing, 3, 1980.
(URL)
V. Bala, E. Duesterwald, and S. Banerjia, "Dynamo: A Transparent
Dynamic Optimization System," Proceedings of the ACM SIGPLAN
2000 Conference on Programming Language Design and Implementation,
(PLDI 2000), June 2000, pages 1-12.
(DOI)
This site is maintained by Keith D. Cooper.
He is a terrible e-mail correspondent.
