Introduction
The ACM SIGPLAN Conference on
Programming Language Design and Implementation (PLDI) and its
predecessor, the Symposium on Compiler Construction, are a forum where
researchers have presented original work on practical issues in the
design, development, implementation, and use of programming languages.
At the appointment of ACM SIGPLAN, our committee compiled a selection
of what we found to be the 50 most influential papers published in
PLDI from 1979 through 1999 into a special SIGPLAN proceedings.
We began by soliciting nominations from the committee and
community at large. At least three committee members carefully
reviewed all the papers in each year. We received 351 nominations
from the community and the committee, resulting in 174 distinct papers
nominations. Each committee member then voted for 60 of these 175.
Excluding the top 29 papers, we voted again with 15 votes among the
additional 45 papers that had garnered at least one vote in the
previous round. We held a conference call to discuss the final
selection of papers. We discussed conflict papers towards the end of
the selection process, and the person with a conflict hung up and
called back upon email notification. Of the 50 papers, 16 papers
include one or more committee members as authors. Our primary
criterion were impact and technical excellence.
The final issue will contain retrospectives from the authors, and we
are in the process of notifying the authors and requesting
retrospectives.
We hope this project will have many positive effects. The collection
will highlight and honor papers that made a large impact on the field.
We hope academics and practitioners will use it as a reading list for
training and that beginning graduate students will use it to study for
area exams. We hope our selection will serve to reemphasize early
papers that may no longer be getting the attention (and citations!)
they deserve. With the retrospectives, authors will discuss how the
history of the work, and how the paper influenced their own and other
subsequent people's work.
I would like to thank the committee for their outstanding efforts to
assemble the best possible selection by reading through the old
proceedings and thoughtfully examining the works of their colleagues.
I would especially like to thank Guy Steele and Keith Cooper, both of
whom examined all of the proceedings and thus providing two complete
sets of nominations from the entire collection. I would also like to
thank Jim Burrill who helped me assemble web pages and scripts and
helped me make this process go smoothly as possible.
Sincerely,
Selected Papers by Year
1979
1979
1979
1982
1982
1982
1982
1984
1984
1984
1984
1986
1986
1986
1986
1986
1988
1988
1988
1988
1988
1988
1989
1989
1989
1990
1990
1990
1990
1990
1990
1991
1991
1991
1992
1992
1993
1993
1993
1994
1996
1996
1998
1998
1998
1998
1999
1999
1999
Kathryn S. McKinley
Editor
Organizing Committee
Kathryn S. McKinley
The University of Texas at Austin
Program Committee
Keith D. Cooper,
Rice University
Jack W. Davidson,
The University of Virginia
Susan Eggers,
The University of Washington, Seattle
Charles N. Fischer,
The University of Wisconsin, Madison
Ken Kennedy,
Rice University
Jim Larus,
Microsoft Research
Peter Lee,
Carnegie Mellon University
Barbara Ryder,
Rutgers University
Michael D. Smith,
Harvard University
Mary Lou Soffa,
The University of Pittsburgh
Guy Steele, Sun Microsystems
Philip Wadler,
Avaya Labs
Mark Wegman,
IBM Research
Code Generation in a Machine-Independent Compiler
by Roderic G. G. Cattell, Joseph M. Newcomer, and Bruce W. Leverett
Efficient Computation of LALR(1) Look-Ahead Sets
by Frank DeRemer and Thomas J. Pennello
Automatic Storage Optimization
by Janet Fabri
An Overview of the PL.8 Compiler
by Marc Auslander and Martin Hopkins
gprof: A Call Graph Execution Profiler
by Susan L. Graham, Peter B. Kessler, and Marshall K. Mckusick
Optimization of Range Checking
by Victoria Markestein, John Cocke, and Peter Markstein
Register Allocation and Spilling via Graph Coloring
by Gregory J. Chaitin
Automatic Loop Interchange
by John R. Allen and Ken Kennedy
Register Allocation by Priority-based Coloring
by Frederick Chow and John Hennesey
Automatic Generation of Peephole Optimizations
by Jack W. Davidson and Christopher W. Fraser
Parallel Processing: A Smart Compiler and a Dumb Machine
by Joseph A. Fisher, John R. Ellis, John C. Ruttenburg, and Alexandru Nicolau
Interprocedural Dependence Analysis and Parallelization
by Michael Burke and Ron Cytron
Interprocedural Constant Propagation
by David Callahan, Keith D. Cooper, Ken Kennedy, and Linda
Torczon
Efficient Instruction Scheduling for a Pipelined Architecture
by Philip B. Gibbons and Steven S. Muchnick
ORBIT: An Optimizing Compiler for Scheme
by David Kranz, Richard Kelsey, Jonathan Rees, Paul Hudak,
James Philbin, and Norman Adams
Global Register Allocation at Link Time
by David W. Wall
Real-time Concurrent Collection on Stock Multiprocessors
by Andrew W. Appel, John R. Ellis, and Kai Li
Interprocedural Side-Effect Analysis in Linear Time
by Keith D. Cooper and Ken Kennedy
Interprocedural Slicing Using Dependence Graphs
by Susan Horwitz, Thomas Reps, and David Binkley
Software Pipelining: An Effective Scheduling Technique for VLIW Machines
by Monica Lam
Control Flow Analysis in Scheme
by Olin Shivers
Register Windows vs. Register Allocation
by David W. Wall
Coloring Heuristics for Register Allocation
by Preston Briggs, Keith D. Cooper, Ken Kennedy, and Linda Torczon
Customization: Optimizing Compiler Technology for SELF, A Dynamically-Typed Object-Oriented Programming Language
by Craig Chambers and David Ungar
On-The-Fly Detection of Access Anomalies
by Edith Schonberg
Improving Register Allocation for Subscripted Variables
by David Callahan, Steve Carr, and Ken Kennedy
Analysis of Pointers and Structures
by David R. Chase, Mark Wegman, and F. Kenneth Zadeck
How to Read Floating-Point Numbers Accurately
by William D. Clinger
How to Print Floating-Point Numbers Accurately
by Guy L. Steele Jr., and Jon L. White
Fast Breakpoints: Design and Implementation
by Peter B. Kessler
Profile Guided Code Positioning
by Karl Pettis and Robert C. Hansen
Soft Typing
by Robert Cartwright and Mike Fagan
Predicting Program Behavior Using Real or Estimated Profiles
by David W. Wall
A Data Locality Optimizing Algorithm
by Michael E. Wolf and Monica Lam
Lazy Code Motion
by Jens Knoop, Oliver Ruthing, and Bernhard Steffen
A Safe Approximate Algorithm for Interprocedural Pointer Aliasing
by William Landi and Barbara G. Ryder
Space Efficient Conservative Garbage Collection
by Hans-Juergen Boehm
The Essence of Compiling with Continuations
by Cormac Flanagan, Amr Sabry, Bruce F. Duba, and Matthias Felleisen
Balanced Scheduling: Instruction Scheduling When Memory Latency is Uncertain
by Daniel R. Kerns and Susan J. Eggers
ATOM: A System for Building Customized Program Analysis Tools
by Amitabh Srivastava and Alan Eustace
Optimizing ML with Run-Time Code Generation
by Peter Lee and Mark Leone
TIL: A Type-Directed Optimizing Compiler for ML
by David Tarditi, Greg Morrisett, Perry Cheng, Chris Stone,
Robert Harper, and Peter Lee
Improving Data-flow Analysis with Path Profiling
by Glenn Ammons and James R. Larus
Thin Locks: Featherweight Synchronization for Java
by David F. Bacon, Ravi Konuru, Chet Murthy, and Mauricio
Serrano
Complete Removal of Redundant Computations
by Rastislav Bodik, Rajiv Gupta, and Mary Lou Soffa
The Design and Implementation of a Certifying Compiler
by George C. Necula, and Peter Lee
On Bounding Time and Space for Multiprocessor Garbage Collection
by Guy E. Blelloch and Perry Cheng
A Fast Fourier Transform Compiler
by Matteo Frigo
An Evaluation of Staged Run-Time Optimizations in DyC
by Brian Grant, Matthai Philipose, Markus Mock, Craig
Chambers, and Susan J. Eggers