15-745 Optimizing Compilers, Spring 2005
Papers for In-Class Discussions

• Pointer Analysis
  • Ghiya, Lavery, and Sehr, "On the importance of points-to analysis and other memory disambiguation methods for C programs" PLDI 2001 Primary
  • Nevin Heintze and Olivier Tardieu, "Ultra-fast aliasing analysis using CLA: a million lines of C code in a second" PLDI 2001
  • Rakesh Ghiya and Laurie J. Hendren. ``Putting Pointer Analysis to Work,'' in Proceedings of the 25th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, San Diego, California, pages 121-133, January 1998. p121-ghiya.pdf
  • Rakesh Ghiya and Laurie J. Hendren. ``Is it a Tree, a DAG, or a Cyclic Graph? A Shape Analysis for Heap-Directed Pointers in C,'' in Proceedings of the 23rd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, St. Petersburg, Florida, pages 1-15, January 1996. p1-ghiya.pdf
  • Maryam Emami, Rakesh Ghiya, and Laurie J. Hendren. ``Context-Sensitive Interprocedural Points-to Analysis in the Presence of Function Pointers,'' in Proceedings of the ACM SIGPLAN '94 Conference on Programming Language Design and Implementation, pages 242-256, June 1994. p242-emami.pdf
  • Robert P. Wilson and Monica S. Lam. ``Efficient Context-Sensitive Pointer Analysis for C Programs,'' in Proceedings of the ACM SIGPLAN'95 Conference on Programming Language Design and Implementation, pages 1-12, June 1995. p1-wilson.pdf p131-whaley.pdf

• Eliminating Memory References
  • Rastislav Bodik, Rajiv Gupta and Mary Lou Soffa. ``Load-Reuse Analysis: Design and Evaluation,'' in Proceedings of the ACM SIGPLAN '99 Conference on Programming Language Design and Implementation, pages 64-76. May 1999. p64-bodik.pdf
  • Raymond Lo, Fred Chow, Robert Kennedy, Shin-Ming Liu and Peng Tu. ``Register Promotion by Sparse Partial Redundancy Elimination of Loads and Stores,'', in Proceedings of the ACM SIGPLAN '98 Conference on Programming Language Design and Implementation, pages 26-37, June 1998. p26-lo.pdf

• Profiling Techniques
  • Thomas Ball and James R. Laurus. ``Efficient Path Profiling,'' in Proceedings of the 29th Annual IEEE/ACM International Symposium on Microarchitecture, pages 46-57, December 1996. p46-ball.pdf
  • James R. Larus. ``Whole Program Paths,'' in Proceedings of the ACM SIGPLAN '99 Conference on Programming Language Design and Implementation, pages 259-269, May 1999. p259-larus.pdf
  • Jennifer M. Anderson, Lance M. Berc, Jeffrey Dean, Sanjay Ghemawat, Monika R. Henzinger, Shun-Tak A. Leung, Richard L. Sites, Mark T. Vandevoorde, Carl A. Waldspurger and William E. Weihl. ``Continuous Profiling: Where Have All the Cycles Gone?,'', in Proceedings of the Sixteenth ACM Symposium on Operating Systems Principles, pages 1-14, October 1997. p357-anderson.pdf

• Exploiting Profiling Information in Data Flow Analysis
  • Glenn Ammons and James R. Larus. ``Improving Data-Flow Analysis with Path Profiles,'' in Proceedings of the ACM SIGPLAN '98 Conference on Programming Language Design and Implementation,pages 72-84, June 1998. p72-ammons.pdf
  • Robert Cohn and P. Geoffrey Lowney. ``Hot Cold Optimization of Large Windows/NT Applications,'' in Proceedings of the 29th Annual IEEE/ACM International Symposium on Microarchitecture, pages 80-89, December 1996. p80-cohn.pdf

• Dynamic Optimizations (1)
  • Vasanth Bala, Evelyn Duesterwald and Sanjeev Banerjia. ``Dynamo: a Transparent Dynamic Optimization System,'' in Proceedings of the ACM SIGPLAN '00 Conference on Programming Language Design and Implementation, pages 1-12, June 2000. p1-bala.pdf
  • Brian Grant, Matthai Philipose, Markus Mock, Craig Chambers and Susan J. Eggers. ``An Evaluation of Staged Run-Time Optimizations in DyC,'' in Proceedings of the ACM SIGPLAN '99 Conference on Programming Language Design and Implementation, pages 293-304, May 1999. p656-grant.pdf
  • Matthew Arnold, Stephen Fink, David Grove, Michael Hind and Peter F. Sweeney. ``Adaptive Optimization in the Jalapeno JVM,'' in Proceedings of the Conference on Object-Oriented Programming, Systems, Languages, and Applications, pages 47-65, October 2000. p47-arnold.pdf
  • Alexander Klaiber. ``The Technology Behind Crusoe Processors,'' Transmeta Corporation. paper_aklaiber_19jan00.pdf
  • Matthew C. Merten, Andrew R. Trick, Erik M. Nystrom, Ronald D. Barnes, and Wen-mei W. Hwu. ``A Hardware Mechanism for Dynamic Extraction and Relayout of Program Hot Spots,'' in Proceedings of the 27th International Symposium on Computer Architecture, pages 59-70, June 2000. p59-merten.pdf

• Improving Data Cache Performance
  • T. Chilimbi, "Efficient representations and abstractions for quantifying and exploiting data reference locality" PLDI 2001 Primary
  • Trishul M. Chilimbi, Bob Davidson, and James R. Larus. ``Cache-Conscious Structure Definition,'' in Proceedings of the ACM SIGPLAN '99 Conference on Programming Language Design and Implementation, pages 13-24, May 1999. p13-chilimbi.pdf
  • Trishul M. Chilimbi, Mark D. Hill, and James R. Larus, ``Cache-Conscious Structure Layout,'' in Proceedings of the ACM SIGPLAN '99 Conference on Programming Language Design and Implementation, pages 1-12, May 1999. p1-chilimbi.pdf
  • C. Ding, K. Kennedy, "Improving Cache Performance in Dynamic Applications through Data and Computation Reorganization at Run Time" PLDI 1999

• Code Layout Optimizations
  • N. Gloy, T. Blackwell, M. Smith, and B. Calder. ``Procedure Placement using Temporal Ordering Information,'' in Proceedings of the 30th Annual ACM/IEEE International Symposium on Microarchitecture, pages 303-313, December 1997. p977-gloy.pdf
  • C. Young, D. Johnson, D. Karger, and M. Smith, ``Near-optimal Intraprocedural Branch Alignment,'' in Proceedings of the ACM SIGPLAN 1997 Conference on Programming Language Design and Implementation, pages 183-193, June 1997. p183-young.pdf

• IA-64 from a Compiler Optimization Perspective
  • Rumi Zahir, Jonathan Ross, Dale Morris and Drew Hess. ``OS and Compiler Considerations in the Design of the IA-64 Architecture,'' in Proceedings of the 9th International Conference on Architectural Support for Programming Languages and Operating Systems, pages 212-221, November 2000. p212-zahir.pdf
  • Scott A. Mahlke and Richard E. Hank and James E. McCormick and David I. August and Wen-Mei W. Hwu, A comparison of full and partial predicated execution support for ILP processors, ISCA 1995.
  • Sebastian Winkel, Exploring the Performance Potential of Itanium Processors with ILP-based Scheduling, in CGO 2004 March 2004.

• Debugging Optimized Code
  • Ali-Reza Adl-Tabatabai and Thomas Gross. ``Source-Level Debugging of Scalar Optimized Code,'' in Proceedings of the ACM SIGPLAN '96 Conference on Programming Language Design and Implementation, pages 33-43, May 1996. p33-adl-tabatabai.pdf
  • Le-Chun Wu, Rajiv Mirani, Harish Patil, Bruce Olsen and Wen-mei W. Hwu. ``A New Framework for Debugging Globally Optimized Code,'' in Proceedings of the ACM SIGPLAN '99 Conference on Programming Language Design and Implementation, pages 181-191, May 1999. p181-wu.pdf

• Register Allocation
  • Michael D. Smith, Norman Ramsey, Glenn Holloway. A generalized algorithm for graph-coloring register allocation. June 2004 PLDI.
  • A Appel and L George, Optimal Spilling for CISC Machines with Few Registers, PLDI 2001
  • Guei-Yuan Lueh, Thomas Gross, Call-cost directed register allocation, PLDI 1997
  • Peter Bergner, Peter Dahl, David Engebretsen, Matthew O'Keefe, Spill code minimization via interference region spilling, PLDI 1997

• Software Pipelining
  • Mikhail Smelyanskiy, Scott Mahlke, Edward Davidson, Probabilistic Predicate-Aware Modulo Scheduling in CGO 2004
  • Hongbo Rong, Zhizhong Tang, R. Govindarajan, Alban Douillet, Guang Gao, Single-Dimension Software Pipelining for Multi-Dimensional Loops in CGO 2004
  • Hongbo Rong, Alban Douillet, R. Govindarajan, Guang Gao Code Generation for Single-Dimension Software Pipelining of Multi-Dimensional Loops in CGO 2004

• Exotic architectures
  • Doug Burger et.al., "Scaling to the End of Silicon with EDGE Architectures", IEEE Computer July 2004. (local copy).
  • Jan Hoogerbrugge and Henk Corporaal and Hans Mulder, ``Software pipelining for transport-triggered architectures'', MICRO 24 (1991).
  • Steve Swanson, Ken Michelson, Andrew Schwerin and Mark Oskin. WaveScalar In the 36th Annual International Symposium on Microarchitecture (MICRO-36), December 2003

• Dynamic Optimization - 2
  • Michael D. Smith. "Overcoming the Challenges to Feedback-Directed Optimization," Proc. ACM SIGPLAN Workshop on Dynamic and Adaptive Compilation and Optimization (Dynamo'00), invited lecture, Boston, MA, January 18, 2000.
  • cliff-asplos94.ps
  • Trishul M. Chilimbi and Martin Hirzel, ``Dynamic hot data stream prefetching for general-purpose programs,'' Proceedings of the ACM SIGPLAN 2002 Conference on Programming language design and implementation, pages 199-209, 2002.
  • Markus Mock and Craig Chambers and Susan J. Eggers, Calpa: a tool for automating selective dynamic compilation, MICRO 33: Proceedings of the 33rd annual ACM/IEEE international symposium on Microarchitecture 2000.
  • Steve S.W. Liao, Perry H. Wang, Hong Wang, Gerolf Hoflehner, Daniel Lavery, John P. Shen. Post-pass binary adaptation for software-based speculative precomputation PLDI 2002.