CS265 References

This is a list of books and papers for CS265, Spring 2003, taught by Prof. Susan Graham. (Actually, it's gradually morphing from the list from Spring 2000). Some of the listed papers will be assigned readings - they are indicated in red; others are here as supplementary material. As the readings for the semester are chosen, they will be added to this list, along with links to e-versions of some of the papers. The reading assignments are given in Reading Assignments.

Textbooks

ARZ92
F. Allen, B. K. Rosen, and K. Zadeck, editors. Optimization in Compilers. Draft, 1992. Available only to CS265 students.
This is a draft of a book that was never completed, but it has some useful material. It is available for purchase from a local copy center.

Muchnick97
Steven S. Muchnick. Advanced Compiler Design and Implementation . Morgan Kaufmann, 1997.
Get your copy from an online bookseller such as amazon.com
Be sure to see the errata.

ASU86
A. V. Aho, R. Sethi, and J. D. Ullman. Compilers: Principles, Techniques, and Tools. Addison-Wesley, 1986.
(This is the book that's often used as an undergraduate text. Chapters 1-8 are for review. Chapters 9 and 10 cover course material.)

Papers

Code Generation

PG88
Eduardo Pelegri-Llopart and Susan L. Graham. Optimal Code Generation for Expression Trees: An Application of BURS Theory. In Proceedings of the 1988 ACM SIGACT/SIGPLAN Symposium on Principles of Programming Languages , pages 294-308, January 1988.

FHP92
Christopher. W. Fraser, Robert R. Henry, and Todd A. Proebsting. BURG -- Fast Optimal Instruction Selection and Tree Parsing. ACM SIGPLAN Notices 27 , 4:68-76, April 1992.
The BURG distribution is also available.

Pro95
Todd A. Proebsting. BURS Automata Generation. ACM Transactions on Programming Languages and Systems, 17(3):461-486, May 1995

See Also
PW96
Todd A. Proebsting and Benjamin A. Whaley. One-Pass, Optimal Tree Parsing - With Or Without Trees. CC'96 April 1996.

FH91
Christopher W. Fraser and Robert R. Henry. Hard-coding bottom-up code generation tables to save time and space. Software-Practice and Experience 21 , (1):1-12, January 1991

FP99
Christopher W. Fraser and Todd A. Proebsting. Finite-state Code Generation. ACM SIGPLAN'99 Conference on Programming Language Design and Implementation, pages 270-280, May 1999

MSRR00
Maya Madhavan, Priti Shankar, Siddhartha Rai, and U. Ramakrishna. Extending Graham-Glanville Techniques for Optimal Code Generation. ACM Transactions on Programming Languages and Systems, 22(6):973-1001, November 2000

Knu71
Donald Knuth. An Empirical Study of FORTRAN Programs. Software:Practice and Experience , 1(2):105-133, April/June 1971

Hoa73
D.C. Hoaglin. An Analysis of the Loop Optimization Scores in Knuth's `Empirical Study of Fortran Programs'. Software:Practice and Experience , 3(2):161-169, April/June 1973.

Lamb81
David A. Lamb Construction of a Peephole Optimizer. Software:Practice and Experience , 11(6):639-647, June 1981.

DF80
Jack W. Davidson and Christopher W. Fraser. The Design and Application of a Retargetable Peephole Optimizer. ACM Transactions on Programming Languages and Systems, 2(2):191-202, April 1980.

Kes86
Peter B. Kessler. Discovering Machine -Specific Code Improvements. In Proceedings of the 1986 ACM SIGPLAN Symposium on Compiler Construction. ACM SIGPLAN Notices , 21(7):249-254, July 1986.

DF84
Jack W. Davidson and Christopher W. Fraser. Code Selection through Object Code Optimization. ACM Transactions on Programming Languages and Systems, 6(4):505-526, October 1984.

Code Compression

DEMS00
Saumya K. Debray, William Evans, Robert Muth, and Bjorn de Sutter. Compiler Techniques for Code Compaction. ACM Transactions on Programming Languages and Systems, 22(2):378-415, March 2000

Flow Analysis

Ram99
G. Ramalingam Identifying Loops in Almost Linear Time. ACM Transactions on Programming Languages and Systems, 21(2):175-188, March 1999

TH92
Steven W. K. Tjiang and John L. Hennessy. Sharlit - A tool for building optimizers. In Proceedings of the ACM SIGPLAN '92 Conference on Programming Language Design and Implementation, pages 82-93, June 1992.

Optimizing Transformations

BGS94
David F. Bacon, Susan L. Graham, and Oliver J. Sharp. Compiler Transformations for High-Performance Computing. ACM Computing Surveys, 26(4):347-420, December 1994

BGS00
Rastislav Bodik, Rajiv Gupta, and Vivek Sarkar. ABCD: eliminating array bounds checks on demand. In Proceedings of the ACM SIGPLAN 2000 Conference on Programming Language Design and Implementation, pages 321-333, June 2000

Gup93
Rajiv Gupta. Optimizing Array Bound Checks using Flow Analysis ACM Letters on Programming Languages and Systems, 2(1-4):135-150, December 1993

KRS94
Jens Knoop, Oliver Rüthing and Bernhard Steffen. Optimal code motion: theory and practice. ACM Transactions on Programming Languages and Systems, 16(4):1117-1155, July 1994

LGC02
Sorin Lerner, David Grove, and Craig Chambers. Composing Dataflow Analyses and Transformations. In Proceedings of the 2002 ACM SIGACT/SIGPLAN Symposium on Principles of Programming Languages , January 2002.

LIU99
Yanhong A. Liu. Efficient Computation via Incremental Computation. Technical report, Dept. of Computer Science, Univ. Indiana , 1999.

WZ91
Mark N. Wegman and F. Kenneth Zadeck. Constant propagation with conditional branches. ACM Transactions on Programming Languages and Systems, 13(2):181-210, April 1991

Intermediate Forms and Intermediate Languages

LTS02
Christopher League, Valery Trifonov, and Zhong Shao. Type-preserving compilation of Featherweight Java. ACM
Transactions on Programming Languages and Systems (TOPLAS), 24(2):112-152, March 2002.
BOSW98
Gilad Bracha, Martin Odersky, David Stoutamire, and Philip Wadler. Making the future safe for the past: Adding
genericity to the Java programming language. In Craig Chambers, editor, ACM Symposium on Object-Oriented
Programming: Systems, Languages, and Applications (OOPSLA), pages 183-200, Vancouver, British Columbia, 1998.
 
CFRW91
Ron Cytron, Jeanne Ferrante, Barry K. Rosen, and Mark N. Wegman. Efficiently Computing Static Single Assignment Form and the Control Dependence Graph. ACM Transactions on Programming Languages and Systems, 13(4):451-490, October 1991

GLW95
Susan L. Graham, Steven Lucco, and Robert Wahbe. Adaptable Binary Programs. Proceedings of the 1995 USENIX Winter Conference , January 1995.

Runtime Code Generation and Optimization

BDB00
Vasanth Bala, Evelyn Duesterwald and Sanjeev Banerjia. Dynamo: A Transparent Dynamic Optimization System. Proceedings of the ACM SIGPLAN'00 Conference on Programming Language Design and Implementation, pages 1-12, June 2000
MCE00
M. Mock, C. Chambers, and S. J. Eggers. Calpa: A tool for automating selective dynamic compilation.  In 33rd Annual International Symposium on Microarchitecture (Micro-33), pages 291-302, Monterey, California, December 2000.
 
LL96
 
Peter Lee and Mark Leone. Optimizing ML with run-time code generation., Proceedings of the ACM SIGPLAN'96 Conference on Programming Language Design and Implementation, May 1996.

GMPCE97
B. Grant, M. Mock, M. Philipose, C. Chambers, S.J. Eggers, Annotation-Directed Run-Time Specialization in C, Symposium on Partial Evaluation and Semantics-Based Program Manipulation, June 1997.

APCEB96
J. Auslander, M. Philipose, C. Chambers, S.J. Eggers and B.N. Bershad, Fast, Effective Dynamic Compilation, Proceedings of the ACM SIGPLAN'96 Conference on Programming Language Design and Implementation, May 1996.

Interprocedural Analysis

CK88
Keith D. Cooper and Ken Kennedy. Efficient Computation of Flow Insensitive Interprocedural Summary Information -- A Correction. ACM SIGPLAN Notices 23 , 4, April 1988.

Feedback-directed Compilation

CL99
Robert Cohn and P. Geoffrey Lowney. Feedback directed optimization in Compaq's compilation tools for Alpha. ACM Workshop on Feedback-directed Optimization , November 1999

AL98
G. Ammons and J. Larus. Improving Data-flow Analysis with Path Profiles. ACM SIGPLAN'98 Conference on Programming Language Design and Implementation, pages 72-84, June 1998

Loop Analysis

GSW95
Michael P. Gerlek, Eric Stoltz, and Michael Wolfe. Beyond Induction Variables: Detecting and Classifying Sequences Using a Demand-Driven SSA Form. ACM Transactions on Programming Languages and Systems, 17(1):85-122, January 1995

Compilation of Object-oriented Languages

ACLPS98
Ali-Reza Adl-Tabatabai, Michal Cierniak, Guei-Yuan Lueh, Vishesh M. Parikh, and James M. Stichnoth. Fast, Effective Code Generation in a Just-In-Time Java Compiler. Proceedings of the ACM SIGPLAN'98 Conference on Programming Language Design and Implementation, pages 280-290, June 1998

AH96
Gerald Aigner and Urs Holzle. Eliminating Virtual Function Calls in C++ Programs. ECOOP'96 - Tenth European Conference on Object-Oriented Programming. , Lecture Notes in Computer Science, 1098:142-166, Springer Verlag, July 1996.

Dol97
Julian Dolby. Automatic Inline Allocation of Objects. ACM SIGPLAN'97 Conference on Programming Language Design and Implementation, pages 7-17, June 1997

IKYTOSOKN99
Kazuaki Ishizaki, Motohiro Kawahito, Toshiaki Yasue, Mikio Takeuchi, Takeshi Ogasawara, Toshio Suganuma, Tamiya Onodera, Hideaki Komatsu, and Toshio Nakatani. Design, Implementation, and Evaluation of Optimizations in a Just-In-Time Compiler. ACM 1999Java Grande Conference , San Francisco, June 12-14, 1999

FKRST99
Fitzgerald, Robert ; Knoblock, Todd B. ; Ruf, Erik ; Steensgard, Bjarne ; Tarditi, David. Marmot: An Optimizing Compiler for Java. Microsoft Research Report MSR-TR-99-33 June 1999.

UA96
Urs Holzle and Ole Agesen. Dynamic vs. Static Optimization Techniques for Object-Oriented Languages (TAPOS 1996)

Pointer Analysis

YHR99
Suan Hsi Yong, Susan Horwitz and Thomas Reps. Pointer Analysis for Programs with Structures and Casting. In Proceedings of the ACM SIGPLAN '99 Conference on Programming Language Design and Implementation , pages 91-103, May 1999.

Steen96
Bjarne Steensgaard. Points-to Analysis in Almost Linear Time. In Proceedings of the 1996 ACM SIGACT/SIGPLAN Symposium on Principles of Programming Languages , pages 32-41, January 1996.

Das00
Manuvir Das. Unification-based Pointer Analysis with Directional Assignments. In Proceedings of the ACM SIGPLAN 2000 Conference on Programming Language Design and Implementation, June 2000.

Vectorization and Parallelism

LP01
Jaejin Lee and David A. Padua. Hiding Relaxed Memory Consistency with a Compiler. IEEE Transactions on Computers: Special Issue on Parallel Architectures and Compilation Techniques , 50(8):824-833, August 2001

MP90
S. Midkiff and D. Padua. Issues in the Compile-time Optimization of Parallel Programs. Proceedings of the International Conference on Parallel Processing (ICPP90), II:105-113, August 1990

PW86
David A. Padua and Michael J. Wolfe. Advanced Compiler Optimizations for Supercomputers. Communications of the ACM, 29(12):1184-1201, December 1986

AK87
J. Randy Allen and Ken Kennedy. Automatic translation of FORTRAN programs to vector form. ACM Transactions on Programming Languages and Systems, 9(4):491-542, October 1987

VLIW

The Transmeta Crusoe system is described in The Technology Behind Crusoe(TM) Processors, Alexander Klaiber, Transmeta Corporation, January 2000. Some public information about the Merced chip is available. See Background Material , John Crawford's Talk, and his Slides.

Implementation of Functional Programming Languages

MMH96
Yasuhiko Minamide, Greg Morrisett, and Robert Harper. Typed Closure Conversion. In Proceedings of the 1996 ACM SIGACT/SIGPLAN Symposium on Principles of Programming Languages , pages 271-283, January 1996.

MWCG99
Greg Morrisett, David Walker, Karl Crary, and Neal Glew. From System F to Typed Assembly Language. ACM Transactions on Programming Languages and Systems, 21(3):527-568, May 1999

AJ89
Andrew W. Appel and Trevor Jim. Continuation-Passing, Closure-Passing Style. In Proceedings of the 1988 ACM SIGACT/SIGPLAN Symposium on Principles of Programming Languages , pages 293-302, January 1989.

Roz92
Guillermo Juan Rozas. Taming the Y Operator. Proceedings of the 1992 ACM SIGPLAN Conference on Lisp and Functional Programming , San Francisco, June 1992.

Implementation of Embedded Software

AM98
Guido Araujo and Sharad Malik. Code generation for fixed-point DSPs. ACM Transactions on Design Automation of Electronic Systems, 3(2):136-161, April 1998

  HD98
Silvina Hanono and Srinivas Devadas. Instruction Selection, Resource Allocation, and Scheduling in the AVIV Retargetable Code Generator. Proceedings of the 35th Design Automation Conference, pages 510-515, June 1998.
 

  ZTB00
Eckart Zitzler, Jurgn Teich, and Shuvra S Bhattacharya. Evolutionary algorithms for the synthesis of embedded software. IEEE Transactions on Very Large Scale Integration(VLSI) Systems 8(4):452-455, August 2000

Program Slicing

BG96
David Binkley and Keith Brian Gallagher. Program Slicing. Advances in Computers 43 , Marvin Zelkowitz, Editor, Academic Press, 1996.

Debugging Optimized Code

TG00a
Caroline Tice and Susan L. Graham. Key Instructions: Solving the Code Location Problem for Optimized Code. Compaq SRC Research Report 164 , September 2000.

TG00b
Caroline Tice and Susan L. Graham. A Practical Approach for Recovery of Evicted Variables. Compaq SRC Research Report 167 , November 2000.

Cop94
Max Copperman. Debugging optimized code without being misled. ACM Transactions on Programming Languages and Systems, 16(3):387-427, May 1994.

Compiler Correctness

Nec00
George C. Necula. Translation Validation for an Optimizing Compiler. In Proceedings of the ACM SIGPLAN'00 Conference on Programming Language Design and Implementation, pages 83-94, June 2000.

 

graham@cs.berkeley.edu