Publications Ordered by Subject

Notice:

This page contains a complete listing of publications for Keith D. Cooper. Where the paper can be re-created using current technology, a PDF version of the paper is supplied. In the cases where no PDF version is available, the text was written using tools that have changed enough to make them reproducible.

These versions may differ in formatting detail from the published papers. The published source should be considered the definitive version.

    Interprocedural Data-Flow Analysis (Algorithms)

    In the 1980s, the compiler group at Rice explored a range of problems in interprocedural data-flow analysis. The design and implementation of the Rn Programming Environment (and its successor, ParaScope) served as a focus for this work. Many of these papers report results developed as part of these efforts. These algorithms and results have found practical application in both research and commercial systems.
  1. "Efficient Computation of Flow Insensitive Interprocedural Summary Information" (with K. Kennedy), Proceedings of the SIGPLAN 84 Symposium on Compiler Construction, SIGPLAN Notices 19(6), June, 1984, pages 247-258.

    This paper shows how to map the interprocedure MOD and USE computations onto Tarjan's balanced-tree, path compression scheme for solving data-flow problems. The result is an algorithm that runs much faster than previous techniques. The formulation in the paper has a couple of flaws. These are addressed in a correction (number 7 below).

  2. "Analyzing Aliases of Reference Formal Parameters," Conference Record of the Twelfth Annual ACM SIGACT/SIGPLAN Symposium on Principles of Programming Languages (POPL), January 1985, pages 281-290.

    This paper reformulates the aliasing problem that arises from interactions of call-by-reference parameters and global variables. The problem is cast into an iterative data-flow framework, leading to a simple algorithm. Several optimizations to the algorithm are included.

  3. "The Impact of Interprocedural Analysis and Optimization on the Design of a Software Development Environment" (with K. Kennedy and L. Torczon), Proceedings of the SIGPLAN 85 Symposium on Language Issues in Programming Environments, SIGPLAN Notices 20(7), July, 1985, pages 107-116.

    This paper lays out, for the first time, the challenges and opportunities that arise from embedding an interprocedural analysis and optimization system in a programming environment. It describes the Rn scheme for distributing the work of analysis across multiple tools in the environment. It describes the recompilation problems introduced by interprocedural analysis and optimization. An expanded version of this work appeared in ACM TOPLAS in 1986 (see 6 below).

  4. "Interprocedural Constant Propagation" (with D. Callahan, K. Kennedy and L. Torczon), Proceedings of the SIGPLAN 86 Symposium on Compiler Construction, SIGPLAN Notices 21(7), July, 1986, pages 152-161.

    This paper describes the techniques for interprocedural constant propagation developed for Rn. The underlying algorithms are from Torczon's thesis. Callahan did the first implementation of the ideas as part of the PFC automatic parallelization system.

  5. "Interprocedural Optimization: Eliminating Unnecessary Recompilation" (with K. Kennedy and L. Torczon), Proceedings of the SIGPLAN 86 Symposium on Compiler Construction, SIGPLAN Notices 21(7), July, 1986, pages 58-67.

    This paper describes the recompilation analysis framework developed for Rn. The original work is from Torczon's thesis. Here, it is reformulated to present a more standard framework. A subsequent ACM TOPLAS paper by Michael Burke and Linda Torczon expands on these ideas.

  6. "The Impact of Interprocedural Analysis and Optimization in the Rn Programming Environment" (with K. Kennedy and L. Torczon), ACM Transactions on Programming Languages and Systems (TOPLAS), October, 1986, pages 491-523.

    The definitive paper on the Rn experience with interprocedural analysis and optimization. This paper summarizes algorithms, issues, and solutions. It grew out of the ACM SIGPLAN 85 paper (see 3 above).

  7. "Efficient Computation of Flow-Insensitive Interprocedural Summary Information - A Correction" (with K. Kennedy), SIGPLAN Notices 23(4), April, 1988, pages 35-42.

    This paper corrects errors in the ACM SIGPLAN 84 paper (see 1 above).

  8. "Interprocedural Side-Effect Analysis in Linear Time" (with K. Kennedy), Proceedings of the SIGPLAN 88 Conference on Programming Language Design and Implementation (PLDI), SIGPLAN Notices 23(7), July, 1988, pages 57-66.

    This paper introduces a new way of looking at the interprocedural side-effect problem--using a graph that shows parameter binding relationships. Using this new graph with the decomposition presented in the correction (see 7 above) leads to a simple, fast algorithm for the summary problems. The underlying philosophy--that interprocedural problems can be analyzed easily if we discover the right graph on which to perform the analysis--became a theme for work at Rice for several years. (See, for example, Callahan's work on the Program Summary Graph in the same conference.)

  9. "Fast Interprocedural Alias Analysis" (with K. Kennedy), Conference Record of the Sixteenth Annual ACM SIGACT/SIGPLAN Symposium on Principles of Programming Languages (POPL), January, 1989, pages 49-59.

    This paper takes the insights behind the binding-graph algorithms for summary problems and applies them to the aliasing problems that arise from interactions of call-by-reference parameters and global variables. It introduces an analog of the binding graph, shows how to perform alias analysis over the graph, and gives an efficient technique for incorporating the alias information into summary sets produced by the ACM SIGPLAN 88 PLDI paper.

  10. "Interprocedural Analysis and Optimization" (with M. Hall, K. Kennedy, and L. Torczon) Communications on Pure and Applied Mathematics, Volume 48, 1995, pages 947-1003.

    This paper provides an overview of the Rice work on interprocedural analysis. It includes algorithms for the classic problems (call-graph construction, summary problems, aliasing, & constant propagation), as well as new work on interprocedural live and kill analysis.

  11. "Recompilation Algorithms for an Optimizing Compiler Based in the Rn Programming Environment" (with K. Kennedy and L. Torczon), Computer Science Technical Report 84-7, Rice University, November 1984.

    A preliminary version of the ACM SIGPLAN 86 paper (see 5 above). The formulation at this stage is quite different from that in the final paper.

  12. "Advanced Techniques in Interprocedural Analysis" (with D. Callahan, K. Kennedy, and L. Torczon), Computer Science Technical Report 87-48, Rice University, June 1987.

    A technical report that lays out the (then) future research directions of the interprocedural analysis group at Rice. It includes preliminary discussions of regular-section side-effect analysis, range propagation, and approximation methods for problems that are inherently flow-sensitive. It describes ideas on quick recompilation and whole-program planning and optimization.

    Interprocedural Optimization

    The Rn Programming Environment was not intended just to analyze programs. The goal was to use the results of interprocedural analysis (or "whole program analysis") to improve the code generated by a compiler. These papers address the issues that arise in compiling and optimizing whole programs.
  13. "Optimization of Compiled Code in the Rn Programming Environment" (with K. Kennedy and L. Torczon), Proceedings of the 19th Annual Hawaii International Conference on Systems Sciences, January, 1986, pages 492-502.

  14. "Editing and Compiling Whole Programs" (with K. Kennedy, L. Torczon, A. Weingarten, and M. Wolcott), Proceedings of the Second ACM SIGPLAN/SIGSOFT Symposium on Practical Software Development Environments (PSDE), December, 1986, pages 92-101.

  15. "An Experiment with Inline Substitution" (with M.W. Hall and L. Torczon), Software-Practice and Experience 21(6), June, 1991, pp 581-601.

    This paper examines the effectiveness of five commercial compilers on code that results from extensive inline substitution. We took a set of benchmark programs and inlined away most of the dynamically executed procedure calls. We took the original source and the transformed source to five different compilers and ran it. The results were completely inconsistent. None of the compilers was consistently able to capitalize on the opportunities that should arise from removing procedure calls. (The shortfalls that we observed in this study motivated some of our work on classical optimization.)

  16. "Procedure Cloning" (with M. Hall and K. Kennedy), Proceedings of the IEEE Computer Society 1992 International Conference on Computer Languages (ICCL), April, 1992, pp 96-105.

  17. "Unexpected Side Effects of Inline Substitution: A Case Study" (with M.W. Hall and L. Torczon), ACM Letters on Programming Languages and Systems (LOPLAS) 1(1), March 1992, pp. 22-32.

    A case study of a single code, the LINPACKD benchmark, on a single machine, the MIPS R2000. Inline substitution of the most heavily executed procedure calls produced a slowdown in the code, because it made some references that look unambiguous in the original code appear ambiguous in the transformed code. As a result, the MIPS compiler inserted NOPs to let a critical store complete before executing the immediately following load.

    The paper was intended to make the point that subtle and unintended consequences can dramatically affect the results of interprocedural experiments. (After all, getting rid of lots of procedure calls should make the code faster, not slower.)

  18. "A Methodology for Procedure Cloning" (with M.W. Hall and K. Kennedy) Computer Languages, 19(2), April 1993, pp. 105-118.

  19. "Goal-directed Interprocedural Optimization", (with P. Briggs, M.W. Hall, and L. Torczon), Computer Science Technical Report 90-147, November 1990.

    Programming Environments

  20. "Parallel Programming Support in ParaScope" (with D. Callahan, R.T. Hood, K. Kennedy, L. Torczon, and S.K. Warren), Proceedings of the 1987 DFVLR-Conference on Parallel Processing in Science and Engineering, Koln, Germany, June, 1987.

    Also published as Parallel Computing in Science and Engineering (R. Dierstein, D. Muller-Wichards, and H. Wacker, editors), Lecture Notes in Computer Science 295, Springer-Verlag, Berlin, June 1987, pages 91-106.

  21. "A Practical Environment for Scientific Programming" (with A. Carle, R.T. Hood, K. Kennedy, L. Torczon, and S.K. Warren), IEEE Computer, 20(11), November, 1987, pages 75-89.

  22. "ParaScope: a Parallel Programming Environment" (with D. Callahan, K. Kennedy, R.T. Hood, and L. Torczon), The International Journal of Supercomputer Applications, 2(4), December, 1988, pages 84-99.

  23. "The ParaScope Parallel Programming Environment" (with M.W. Hall, R.T. Hood, K. Kennedy, K. McKinley, J. Mellor-Crummey, L. Torczon, and S.K. Warren) Proceedings of the IEEE, 81(2), February 1993, pp. 244-263.

  24. "The Rn Environment: A Capsule Description" (with R.T. Hood, K. Kennedy, and L. Torczon), Computer Science Technical Report 87-46, Rice University, June 1987.

    Register Allocation

  25. "Coloring Heuristics for Register Allocation" (with P. Briggs, K. Kennedy, and L. Torczon), Proceedings of the SIGPLAN 89 Conference on Programming Language Design and Implementation (PLDI), SIGPLAN Notices 24(7), July, 1989, pages 275-284.

  26. "Coloring Register Pairs" (with P. Briggs and L. Torczon), ACM Letters on Programming Languages and Systems, (LOPLAS) 1(1), March 1992, pp. 3-13.

  27. "Rematerialization" (with P. Briggs and L. Torczon), Proceedings of the SIGPLAN 92 Conference on Programming Language Design and Implementation (PLDI), SIGPLAN Notices 27(7), July, 1992, pp. 311-321.

  28. "Improvements to Graph Coloring Register Allocation", (with P. Briggs and L. Torczon), ACM Transactions on Programming Languages and Systems (TOPLAS) 16(3), May 1994, pp. 428-456.

  29. "How to build an interference graph" (with T.J. Harvey and L. Torczon). Software-Practice and Experience, 28(4), April, 1998, pages. 425-444.

  30. "Live-range splitting in a graph coloring register allocator", (with L.T. Simpson), Proceedings of the 1998 International Conference on Compiler Construction, (Lecture Notes in Computer Science, 1383, Springer), March/April 1998, Lisbon, Portugal, pp. 174-187.

  31. Patent: Digital Computer Register Allocation and Code Spilling Using Interference Graph Coloring (with P. Briggs, K. Kennedy, and L. Torczon), Patent number 5,249,295.

  32. "Aggressive Live Range Splitting" (with P. Briggs and L. Torczon), Code 91 - Concepts, Tools, and Techniques, Schloss Dagstuhl, Germany, May, 1991.

    Classical Optimization

  33. "Using Compiler Technology to Drive Advanced Microprocessors" Proceedings of the DARPA Software Technology Conference, Los Angeles, CA, April 28-30, 1992, pp. 42-49.

  34. "Effective Partial Redundancy Elimination" (with P. Briggs), Proceedings of the SIGPLAN 94 Conference on Programming Language Design and Implementation, SIGPLAN Notices 29(6) June 1994, pp.159-170.

  35. "Combining Analyses, Combining Optimizations" (with C. Click), ACM Transactions on Programming Languages and Systems (TOPLAS), 17(2), March 1995, pp. 181-196.

  36. "Cross-loop Reuse Analysis and its Application to Cache Optimizations" (with K. Kennedy and N. McIntosh), Proceedings of Languages and Compilers for Parallel Computers (LCPC), August 1996.

  37. "Value Numbering", (with P. Briggs and L. Taylor Simpson), Software--Practice and Experience 27(6), June 1997, pp. 710-724.

  38. "Register promotion in C programs", (with J. Lu) Proceedings of the SIGPLAN 97 Conference on Programming Language Design and Implementation (PLDI), SIGPLAN Notices 32(6), June 1997, pages 308-319.

  39. "Practical Improvements to the Construction and Destruction of Static Single Assignment Form" (with P. Briggs, T.J. Harvey, and L. Taylor Simpson). Software-Practice and Experience 28(8), July, 1998, pp. 859-881.

  40. "Operator Strength Reduction" (with L.T. Simpson and C. Vick). ACM Transactions on Programming Languages and Systems (TOPLAS), ( to appear).

  41. "Value-Numbering" (with P. Briggs and L.T. Simpson). Center for Research on Parallel Computation Technical Report TR94527, November 1994

  42. "An Empirical Study of Inter-loop Reuse in the NAS Benchmarks" (with K. Kennedy and N. McIntosh) Center for Research on Parallel Computation Technical Report TR95519, March 1995.

  43. "Using Conditional Branches to Improve Constant Propagation" (with P. Briggs and L. Torczon), Center for Research on Parallel Computation Technical Report TR95533, April 1995.

  44. "Operator Strength Reduction" (with L.T. Simpson and C. Vick), Center for Research on Parallel Computation Technical Report TR95635, October 1995.

  45. "SCC-Based Value Numbering" (with L.T. Simpson), Center for Research on Parallel Computation Technical Report TR95636, October 1995.

  46. "Value-Driven Code Motion" (with L.T. Simpson), Center for Research on Parallel Computation Technical Report TR95637 (available online), October 1995.

  47. "Compiler Techniques for Software Prefetching of Cache-Coherent Shared-Memory Multiprocessors," (with N. McIntosh, K. Fletcher, and K. Kennedy), Center for Research on Parallel Computation Technical Report TR96675, October 1996.

  48. "An Experimental Evaluation of List Scheduling," (with P. Schielke and D. Subramanian), Rice University Department of Computer Science Technical Report 98-326, September 1998.

  49. "Compilers, Microprocessors, and Memory Systems" (with P. Briggs), NSF Workshop on High Performance Memory Systems, Charlottesville, Virginia, April, 1993.

    Embedded Systems Work

  50. "Compiler-controlled memory" (with T.J. Harvey). Proceedings of the Eighth International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS), San Jose, CA, October 1998, pp. 2-11.

    (Also: ACM SIGPLAN Notices, 33(11), November 1998; ACM SIGOPS Operating Systems Review, 32(5), December 1998; and ACM SIGARCH Computer Architecture News, 26(Special Issue), October 1998.)

  51. "Enhanced Code Compression for Embedded RISC Processors" (with N. McIntosh), Proceedings of the SIGPLAN 99 Conference on Programming Language Design and Implementation (PLDI), SIGPLAN Notices 34(?), pages 139-149.

  52. "Non-local instruction scheduling with limited code growth" (with P.J. Schielke). 1998 ACM SIGPLAN Workshop on Languages, Compilers, and Tools for Embedded Systems (LCTES), Montreal, CA, June 1998. (Lecture Notes in Computer Science, 1474, F. Mueller and A. Bestavros, (editors), Springer), June 1998, pp. 193-207.

  53. "Optimizing for Reduced Code Space using Genetic Algorithms" (with P. Schielke and D. Subramanian), 1999 ACM SIGPLAN Workshop on Languages, Compilers, and Tools for Embedded Systems (LCTES), Atlanta, GA, May 1999. (Proceedings will appear as an issue of SIGPLAN Notices)

    Building Monograph

  54. "Outram's Building at Rice: Icons, Images, and Themes", published by Rice University, October 1996; 20 pages.