COMP 512: Advanced Compiler Construction Professor Keith D. Cooper Department of Computer Science Rice University Houston, Texas, USA Spring 2008: Room 105, Keck Hall, Monday, Wednesday, Friday, 10am

Reading Material Available Online

1. Improved Optimization of FORTRAN Object Programs
   R.G. Scarborough and H.G. Kolsky IBM Journal of Research and Development24(6), November 1980.
   
   
2. Compiler-based Code Improvement Techniques,
   K.D. Cooper, K.S. McKinley, and L. Torczon
   Draft survey paper on scalar optimization; it is the source for many parts of 512, including the taxonomy (see Section 6)
   
   
3. Compiler Transformations for High Performance Computing,
   David F. Bacon, Susan L. Graham, and Oliver J. Sharp
   From ACM Computing Surveys, 26(4).
   If you want someone else's viewpoint in a survey, here it is.
   
   
4. The Swift Java Compiler: Design and Implementation,
   Daniel J. Scales, Keith H. Randall, Sanjay Ghemawat, and Jeff Dean
   This paper ia a Compaq Research Technical Report. I particularly like the table that shows the contribution of each transformation to overall code quality.
   
   
5. Efficiently Computing Static Single Assignment Form And The Control Dependence Graph,
   Ron Cytron, Jeanne Ferrante, Barry K. Rosen, Mark N. Wegman, and F. Kenneth Zadeck, ACM Transactions on Programming Languages and Systems (TOPLAS), 13(4), October 1991, pages 451--490.
   
   
6. Operator Strength Reduction,
   Keith D. Cooper, L. Taylor Simpson, and Christopher A. Vick
   ACM Transactions on Programming Languages and Systems (TOPLAS) 23(5), September 2001, pages 603-625
   
   
7. Live-range splitting in a graph-coloring register allocator,
   Keith D. Cooper and L. Taylor Simpson
   Proceedings of the 1998 International Compiler Construction Conference (CC98), Lisbon, PT, March/April 1998.
   
   
8. The Reference Implementation of CLEAN,
   Rob Shillner and John Lu, 1994.
   
   
9. A Simple, Fast Dominance Algorithm (in preparation),
   Keith D. Cooper, Timothy J. Harvey, and Ken Kennedy.
   
   
10. Code Motion of Control Structures in High Level Languages, Ron Cytron, Andy Lowry, and Kenneth Zadeck, Proceedings of the 13th ACM SIGPLAN SIGACT Symposium on Principles of Programming Languages, January 1986, pages 70--84.
    
    
11. Dynamo: A Transparent Dynamic Optimization System, Vasanth Bala, Evelyn Duesterwald, and Sanjeev Banerjia, Proceedings of the 2000 ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI 2000), Vancouver, BC, Canada, June 2000, pages 1--12. (SIGPLAN Notices 35(5), May 2000)
    
    
12. An experiment with inline substitution, K.D. Cooper, M.W. Hall, and L. Torczon, Software--Practice and Experience, 21(6), June 1991.
    
    
13. Value Numbering, P. Briggs, K.D. Cooper, L.T. Simpson, Software--Practice and Experience, 27(6), June 1997.
    
    
14. Global Common Subexpression Elimination, J. Cocke, Proceedings of a Symposium on Compiler Construction, SIGPLAN Notices, 5(7), pages 20-24, July 1970.
    
    
15. Global Data Flow Analysis and Iterative Algorithms, J.B. Kam and J.D. Ullman, Journal of the ACM, 23(1), January 1976, pages 158-171.
    
    
16. Automatic synthesis of optimal invariant assertions, P. Cousot and R. Cousot, Proceedings of the 1977 Symposium on Artificial Intelligence and Programming Languages, ACM SIGART, 1977, pages 1-12.
    
    
17. A Survey of Data-flow Analysis Techniques, K. Kennedy, in Program Flow Analysis: Theory and Applications (N.D. Jones and S.S. Muchnick, editors), Prentice-Hall, 1981.
    
    A Survey of Data-flow Analysis Techniques, scanned from the original technical report. (This version has only the bibliographic entries from Ken's Chapter, rather than the entire book's bibliography. It may be a more accurate bibliography.)
    
    
18. 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.
    
    
19. Constant Propagation with Conditional Branches, M.N. Wegman and F.K. Zadeck, ACM Transactions on Programming Languages and Systems (TOPLAS), 13(2), April 1991, pages 181--210.
    
    
20. Lazy Code Motion, J. Knoop, O. Ruthing, and B. Steffen, Proceedings of the ACM SIGPLAN '92 Conference on Programming Language Design and Implementation (PLDI), SIGPLAN Notices 27(7), July 1992.
    
    
21. A variation of Knoop, Ruthing, and Steffen's `Lazy Code Motion', K.H. Drechsler and M.P. Stadel, SIGPLAN Notices 28(5), May 1993.
    
    
22. Effective Partial Redundancy Elimination, P. Briggs and K.D. Cooper, Proceedings of the ACM SIGPLAN '94 Conference on Programming Language Design and Implementation (PLDI), SIGPLAN Notices 29(6), June 1994.
    
    
23. Analyzing and Compressing Assembly Code, C.W. Fraser, E. Myers, A.L. Wendt, Proceedings of the 1984 SIGPLAN symposium on Compiler construction.
    
    
24. Enhanced Code Compression for Embedded RISC Processors, K.D. Cooper and N. McIntosh, Proceedings of the ACM SIGPLAN '99 Conference on Programming Language Design and Implementation (PLDI).
    
    
25. Superoptimizer: A Look at the Smallest Program, H. Massalin, Proceedings of the Second International Conference on Architectural Support for Programming Languages and Systems, (ASPLOS II), Palo Alto, CA, USA, 1987, pages 122-126.
    
    
26. A Catalogue of Optimizing Transformations, F. Allen and J. Cocke, in Design and Optimization of Compilers, Prentice-Hall, 1972, pages 1-30.
    
    
27. Non-local Instruction Scheduling with Limited Growth, K.D. Cooper and P.J. Schielke, Proceedings of the 1998 ACM Workshop on Languages, Compilers, and Tools for Embedded Systems, Montreal, CA, June 1998.
    See also "An Experimental Evaluation of List Scheduling", K.D. Cooper, P.J. Schielke, and D. Subramanian, Rice University, Department of Computer Science Technical Report 98-326, 1998.
    
    
28. Optimizing for Reduced Code Space using Genetic Algorithms, K.D. Cooper, P.J. Schielke, and D. Subramanian, Proceedings of the 1999 ACM Workshop on Languages, Compilers, and Tools for Embedded Systems, Atlanta, GA, USA, May 1999.
    
    
29. Optimization of Range Checking, V. Markstein, J. Cocke, P. Markstein, Proceedings of the 1982 SIGPLAN symposium on Compiler construction.
    
    
30. Optimizing Array Bound Checks Using Flow Analysis, R. Gupta, ACM Letters on Programming Languages and Systems (LOPLAS), 2(1-4), March 1983.
    
    
31. Detecting Equality of Variables in Programs, B. Alpern, M.N. Wegman, and F.K. Zadeck, Proceedings of the 15th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, (POPL), January 1988, pages 1--11.
    
    
32. Register Promotion in C Programs, K.D. Cooper and J. Lu, Proceedings of the ACM SIGPLAN '97 Conference on Programming Language Design and Implementation (PLDI), SIGPLAN Notices 32(6), June 1997.
    
    
33. Register Promotion by Sparse Partial Redundancy Elimination of Loads and Stores, R. Lo, F. Chow, R. Kennedy, S. Liu, P. Tu, Proceedings of the ACM SIGPLAN '98 Conference on Programming Language Design and Implementation (PLDI).
    
    
34. Investigating Adaptive Compilation Using the MIPSpro Compiler, K.D. Cooper and T. Waterman, LACSI Symposium 2003.
    
    
35. Profile Guided Code Positioning, K. Pettis and R.C. Hansen, Proceedings of the ACM SIGPLAN '90 Conference on Programming Language Design and Implementation (PLDI), SIGPLAN Notices 25(6), June 1990.
    
    
36. The Superblock: An Effective Technique for VLIW and Superscalar Compilation, Wen-Mei W. Hwu, Scott A. Mahlke, William Y. Chen, Pohua P. Chang, Nancy J. Warter, Roger A Bringmann, Ronald G. Ouellette, Richard E. Hank, John G. Holm, and Daniel M. Lavery, Journal of Supercomputing -- Special Issue on Instruction Level Parallelism, 7(1), pages 229-248, May 1993.
    
    
37. Trace Scheduling: A Technique For Global Microcode Compaction, J. Fisher, IEEE Transactions on Computers, C-30(7), pages 478-490, July 1981.
    
    
38. Software Pipelining: An Effective Scheduling Technique for VLIW Machines, M. Lam, Proceedings of the ACM SIGPLAN '88 Conference on Programming Language Design and Implementation (PLDI), June 1988.
    
    
39. Interprocedural Analysis and Optimization, K. D. Cooper, M. W. Hall, K. Kennedy, and L. Torczon, Communications on Pure and Applied Mathematics, 48, 1995 (pages 947-1003).
    
    
40. An Interval-based Approach to Exhaustive and Incremental Interprocedural Analysis, M. Burke, ACM Transactions on Programming Languages and Systems (TOPLAS), 12(3), July 1990.
    
    
41. Efficient Call Graph Analysis, M. Hall and K. Kennedy, ACM Letters on Programming Languages and Systems (LOPLAS), 1(3), September, 1992.
    
    
42. A Scheme for Interprocedural Modification Side Effect Analysis with Pointer Aliasing, B. G. Ryder, W. Landi, P.A. Stocks, S. Zhang, and R. Altucher, ACM Transactions on Programming Languages and Systems (TOPLAS), 23(2), March 2001.
    
    
43. Unification-based Pointer Analysis with Directional Assignments, M. Das, Proceedings of the ACM SIGPLAN 2000 Conference on Programming Language Design and Implementation (PLDI), May 2000.
    
    
44. Minimizing Register Usage Penalty at Procedure Calls, F. Chow, Proceedings of the ACM SIGPLAN '88 Conference on Programming Language Design and Implementation (PLDI).
    
    
45. Register Windows versus Register Allocation, D. Wall, Proceedings of the ACM SIGPLAN '88 Conference on Programming Language Design and Implementation (PLDI).
    
    
46. Interprocedural Constant Propagation: A Study of Jump Function Implementations, D. Grove and L. Torczon, Proceedings of the ACM SIGPLAN '93 Conference on Programming Language Design and Implementation (PLDI).
    
    
47. Interprocedural Constant Propagation: An Empirical Study, R. Metzger and S. Stroud, ACM Letters on Programming Languages and Systems (LOPLAS), 2(1-4).
    
    
48. An Analysis of Inline Substitution For a Structured Programming Language, R. Scheifler, Communications of the ACM, 20(9), September, 1977, pages 647-654.
    
    
49. Subprogram Inlining: A Study of Its Effects on Program Execution Time, J.W. Davidson and A. Holler, IEEE Transactions on Software Engineering, 18(2) 1992, pages 89-102.
    
    
50. Constructing the Procedure Call Multigraph, D. Callahan, A. Carle, M.W. Hall and K. Kennedy, IEEE Transactions on Software Engineering, 16(4) 1990.
    
    
51. A Study of a C Function Inliner, J.W. Davidson and A. Holler, Software--Practice and Experience, 18(1), 1988.
    
    
52. Constructing the Call Graph of a Program, B. Ryder, IEEE Transactions on Software Engineering, 1979.
    
    
53. "A Program Data Flow Analysis Procedure," F.E. Allen and J. Cocke, Communications of the ACM, 19(3), March 1976, pages 137-147.
    
    
54. "An Interval-based Approach to Exhaustive and Incremental Interprocedural Data-Flow Analysis," M. Burke, ACM Transactions on Programming Languages and Systems, 12(3), July 1990, pages 341-395.
    
    
55. "An Incremental Algorithm for Software Analysis," B.G. Ryder and M.D. Carroll, Proceedings of the Second ACM SIGSOFT/SIGPLAN Software Engineering Symposium on Practical Software Development Environments , Palo Alto, CA, USA, 1987, pages 171-179. (Also, ACM SIGPLAN Notices, 22(1), January 1987, pages 171-179)
    
    
56. "A Simple Algorithm for Global Data Flow Analysis Problems", M.S. Hecht and J.D. Ullman, SIAM Journal of Computing, 4(4), December 1975, pages 519-532.
    
    
57. "Elimination Algorithms for Data Flow Analysis," B.G. Ryder and M.C. Paull, ACM Computing Surveys, 18(3), September 1986, pages 277-316.
    
    
58. "Incremental Data-Flow Analysis Algorithms," B.G. Ryder and M.C. Paull, ACM Transactions on Programming Languages and Systems 10(1), January 1988, pages 1-50.
    
    
59. "An Overview of the PL.8 Compiler", M. Auslander and M. Hopkins, Proceedings of the 1982 ACM SIGPLAN Symposium on Compiler Construction, June, 1982. (Also, SIGPLAN Notices, 17(6))
    
    
60. "Measurement of Program Improvement Algorithms", J. Cocke and P. Markstein, Information Processing 80, Proceedings of IFIP Congress 80, Tokyo, Japan, October, 1980 (North-Holland/IFIP).
    
    
61. "A Unified Approach to Global Program Optimization", G. Kildall, Proceedings of the First ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages (POPL), Boston, MA, USA, 1973, pages 194-206.
    
    
62. "A Sparse Algorithm for Predicated Global Value Numbering", Karthik Gargi, Proceedings of the ACM SIGPLAN 2002 Symposiumon Programming Language Design and Implementations (PLDI), Berlin, pages 45-56.
    
    
63. "SCC-Based Value Numbering", K.D. Cooper and L. Taylor Simpson, Technical Report CRPC-TR956363-S, Center for Research on Parallel Computation, Rice University, Houston, TX, USA, October 1995. [Algorithm also described in Muchnick's book]