Compiler Syllabus Summary

In December, I solicited reading lists of graduate compiler classes in
order to come up with a syllabus for a reading group at MIT for this past
spring. Several people were interested in the syllabus I came up with, so
I am posting it. I waited until the end of the semester so the posting
would benefit from our experience.


I have also attached a preliminary table of contents for Peter Lee's book,
_Topics in Advanced Language Implementation_, which Prof. Lee sent me in
response to my query.


Ellen Spertus
ellens@ai.mit.edu
----------------


Summary:
Register Allocation (2 days)
Dataflow Analysis (1 day)
Instruction Scheduling (2 days)
Code generation (2 days)
Alias Analysis (1 day)
Debugging Optimized Code (1 day)
Dependence Analysis and Parallelism (3 days)




Register Allocation (1/2)


      G. J. Chaitin, M. A. Auslander, A. K. Chandra, J. Cocke, M. E.
      Hopkins, and P. W. Markstein, Register Allocation via Coloring,
      _Computer Languages_, 6(1):47-57 (1981).


      G. J. Chaitin, Register Allocation and Spilling via Graph Coloring.
      _Proceedings of the SIGPLAN '82 Symposium on Compiler
      Construction_, pages 98-105 (June 1982).


      David W. Wall, Register Windows vs. Register Allocation,
      _Proceedings of the SIGPLAN '88 Conference on Programming Language
      Design and Implementation_, volume II, pages 67-78 (June 1988).




Register Allocation (2/2)


      Fred C. Chow and John Hennessy, The Priority-Based Coloring Approach
      to Register Allocation, _ACM Transactions on Programming Languages
      and Systems_ 12(4):501-536 (October 1990).


      Fred C. Chow, Minimizing Register Usage Penalty at Procedure Calls,
      _Proceedings of the SIGPLAN '88 Conference on Programming Language
      Design and Implementation_, pages 85-94 (June 1988).




February 19: Dataflow Analysis


      R. Cytron, J. Ferrante, B. K. Rosen, M. N. Wegman, and F. K.
      Zadeck, Efficiently Computing Static Single Assignment Form and
      the Control Dependence Graph, _ACM Transactions on Programming
      Languages and Systems_ 13(4):451-490 (October 1991).


      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).


Supplementary reading on dataflow analysis, not for discussion:


      M. Sharir, Structural Analysis: a New Approach to Flow Analysis in
      Optimizing Compilers, _Computer Languages_ 5(3/4):141-153 (1980).


      J. T. Schwartz and M. Sharir, Tarjan's Fast Interval Finding
      Algorithm, _Setl Newsletter_, Courant, number 302 (March 1978).




Instruction Scheduling (1/2)


        John Hennessy and Thomas Gross, Postpass Code Optimization of
        Pipeline Constraints, _ACM Transactions on Programming Languages
        and Systems_ 5(3):422-448 (July 1983).


        P. B. Gibbons and S. S. Muchnick, Efficient Instruction Scheduling
        for a Pipelined Architecture, _Proceedings of the SIGPLAN '86
        Conference on Compiler Construction_, pages 11-16 (June 1986).




Instruction Scheduling (2/2)


        J. Fisher, Trace Scheduling: A Technique for Global Microcode
        Compaction, _IEEE Transactions on Computers_, C-30(7):478-490
        (July 1981).


        M. Lam. Software Pipelining: An Effective Scheduling Technique
        for VLIW Machines, _Proceedings of the SIGPLAN '88 Symposium on
        Programming Language Design and Implementation_, pages 318-328
        (June 1988).




Code Generation (1/2)


        R. Sethi and J. D. Ullman, The Generation of Optimal Code for
        Arithmetic Expressions, _Journal of the ACM_, 17(4):715-728
        (October 1970).


        B. W. Leverett, R. G. G. Cattell, S. O. Hobbs, J. M. Newcomer,
        A. H. Reiner, B. R. Schatz, and W. A. Wulf, An Overview of the
        Production-Quality Compiler-Compiler Project, _Computer_
        13(8):38-49 (August 1980).


        Jack W. Davidson, A Retargetable Instruction Reorganizer,
        _Proceedings of the SIGPLAN '86 Symposium on Compiler
        Construction_, pages 234-241 (June 1986).




Code Generation (2/2)


        R. S. Glanville and S. L. Graham, A New Method for Compiler Code
        Generation, _Conference Record of the Fifth Symposium on Principles
        of Programming Languages_, pages 231-240 (January 1978).


        R. Nigel Horspool, An Alternative to the Graham-Glanville Code-
        Generation Method. _IEEE Software_ 4(3):33-39 (May 1987).




Alias Analysis


      J. P. Banning, An Efficient Way to Find the Side Effects of
      Procedure Calls and the Aliases of Variables, _Conference Record of
      the 6th Annual ACM Symposium on the Principles of Programming
      Languages_, pages 29-41 (January 1979).


        Keith D. Cooper, Analyzing Aliases of Reference Formal Parameters,
        _Conference Record of the Twelfth ACM Symposium on the Principles
        of Programming Languages_, pages 281-290 (January 1985).


        S. Horwitz, P. Pfeiffer, and T. Reps, Dependence Analysis for
        Pointer Variables, _Proceedings of the SIGPLAN '89 Conference
        on Programming Language Design and Implementation_, pages 28-40
        (June 1989).




Debugging Optimized Code


        J. Hennessy, Symbolic Debugging of Optimized Code, _ACM Transactions
        on Programming Languages and Systems_ 4(3):323-344 (July 1982).


        P. T. Zellweger, An Interactive High-Level Debugging for Control-Flow
        Optimized Programs, _ACM SIGSOFT/SIGPLAN Software Engineering
        Symposium on High-Level Debugging_, pages 159-171, 1983.


        P. Fritzson, "A Systematic Approach to Advanced Debugging through
        Incremental Compilation", _ACM SIGSOFT/SIGPLAN Software Engineering
        Symposium on High-level Debugging_, pages 130-139, 1983.




Dependence Analysis and Parallelism (1/4)


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


        Ron Cytron, Doacross: Beyond Vectorization for Multiprocessors.
        _Proceedings of the 1986 International Conference on Parallel
        Processing_, pages 836-844 (August 1986).




Dependence Analysis and Parallelism (2/4)


        Jeanne Ferrante, Karl J. Ottenstein, and J. D. Warren, The Program
        Dependence Graph and its Use in Optimization, _ACM Transactions
        on Programming Languages and Systems_, 9(3):319-349 (July 1987).


        Michael Burke and Ron Cytron, Interprocedural Dependence Analysis
        and Parallelism, _Proceedings of the SIGPLAN '86 Conference on
        Compiler Construction_, pages 167-175 (June 1986).




Dependence Analysis and Parallelism (3/4)


        Geoffrey Fox, et al. Fortran D Language Specification. Rice COMP
        TR90-141, December, 1990.


        Kathleen Knobe, Joan Lukas, and Guy L. Steele, Data Optimization:
        Allocation of Arrays to Reduce Communication on SIMD MAchines.
        _Journal of Parallel and Distributed Computing, 8:102-118 (1990).




Dependence Analysis and Parallelism (4/4)


        R. Allen, D. Callahan, and K. Kennedy, Automatic Decomposition of
        Scientific Programs for Parallel Execution, _Conference Record of
        the Fourteenth ACM Symposium on Principles of Programming
        Languages_, pages 63-76 (June 1987).


        Remi Triolet, Francois Irigoin, and Paul Feautrier, Direct
        Parallelization of Call Statements, _Proceedings of the SIGPLAN '86
        Symposium on Compiler Construction_, pages 176-185 (June 1986).


        Constantine D. Polychronopoulos et al, _Paraphrase-2: An
        Environment for Parallelizing, Partitioning, Synchronizing, and
        Scheduling Programs on Multiprocessors, _Proceedings of the 1989
        International Conference on Parallel Processing_, volume II, pages
        836-844 (August 1986).


----------------


Preliminary table of contents for:


TOPICS IN ADVANCED LANGUAGE IMPLEMENTATION
Peter Lee, Editor


Contributing Authors:


Andrew W. Appel
Joseph L. Bates
David L. Detlefs
Conal Elliott
Scott E. Fahlman
Alessandro Forin
Maurice P. Herlihy
Philip J. Koopman, Jr.
Kevin J. Lang
Peter Lee
Barak A. Pearlmutter
Frank Pfenning
Uwe F. Pleban
Eugene J. Rollins
Olin Shivers
Peter A. Steenkiste
Skef Wholey
Jeannette M. Wing




CHAPTER 1: Editor's Introduction
by Peter Lee


*** PART ONE: ADVANCED IMPLEMENTATION TECHNIQUES ***


CHAPTER 2: The Implementation of Tags and Run-time Type Checking
by Peter A. Steenkiste


CHAPTER 3: Advanced Register Allocation
by Peter A. Steenkiste


CHAPTER 4: Flow Analysis and Type Recovery for Scheme
by Olin Shivers


CHAPTER 5: Garbage Collection
by Andrew W. Appel


CHAPTER 6: Concurrent Garbage Collection for C++
by David L. Detlefs




*** PART TWO: PRACTICE AND EXPERIENCE WITH ADVANCED IMPLEMENTATIONS ***


CHAPTER 7: Design Considerations for CMU Common Lisp
by Scott E. Fahlman


CHAPTER 8: Compilation Issues in the Screme Implementation for the 88000
by Uwe F. Pleban


CHAPTER 9: The Implementation of Oaklisp
by Kevin J. Lang and Barak A. Pearlmutter




*** PART THREE: PARALLEL AND DISTRIBUTED LANGUAGES ***


CHAPTER 10: Futures
by Alessandro Forin


CHAPTER 11: An Experimental Implementation of Connection Machine Lisp
by Skef Wholey


CHAPTER 12: Inheritance of Synchronization and Recovery Properties in
Avalon/C++
by David L. Detlefs, Maurice P. Herlihy, and Jeannette M. Wing




*** PART FOUR: NEW AND UNCONVENTIONAL LANGUAGES AND TECHNIQUES


CHAPTER 13: A Semi-functional Implementation of Higher-order Logic Programming
by Conal Elliott and Frank Pfenning


CHAPTER 14: The Architecture of the PRL Mathematics Environment
by Joseph L. Bates


CHAPTER 15: A Simple Implementation of Object Storage for Common Lisp
by Eugene J. Rollins


CHAPTER 16: Architectural Considerations for Combinator Graph Reduction
by Philip J. Koopman, Jr. and Peter Lee
--

Return to the comp.compilers page.
Search the comp.compilers archives again.