CS 380C: Advanced Compiler Techniques

      Instructor: Keshav Pingali
      email: pingali@cs.utexas.edu
      Phone: 232-6567
      Class Hours: Tuesday & Thursday 9:30-11:00, RAS 312
      Office Hours: 1:00-2:00PM, Tuesday, ACES 4.126A

      TA: Suriya  Subramanian
      email: suriya@cs.utexas.edu
      Office Hours: Wednesdays  3:00PM-4:00PM  in  ENS  31 NQ Desk 1

      Administrative Assistant Aubrey Hooser
      email: aubrey@ices.utexas.edu
      phone: 232 7460
      office: ACES 4.126

    Course materials

      Lecture Schedule and Notes

      Assignments
      Clarifications (Please look here to see if your question has already been answered)
      Errata
      Projects

    Description
    This course will focus on compilation techniques for optimizing program execution on uniprocessors and multicore processors.  We will begin with classical topics such as intermediate program representations, interprocedural and intraprocedural dataflow analysis, register allocation, and scheduling for modern uniprocessors. Then we will discuss multicore processors, and study techniques such as dependence analysis, loop transformations, points-to analysis, and shape analysis for optimizing the execution of regular and irregular programs on multicore processors. We conclude with a discussion of current research directions in compilers. 

    Course work
    There will be written assignments as well as programming assignments. Written assignments will test understanding of concepts while programming projects will provide experience with implementation issues and allow students to evaluate the impact of individual techniques. A final project gives students experience with systems research. 

    Prerequisites
    An undergraduate compiler course and architecture course, or permission of instructor. Programming experience in the context of a larger system is helpful. This page gives a more detailed list of concepts you should be familiar with.

    Grading

    • 60% - Assignments
    • 40% - Project (proposal, implementation, final report)

    Academic Integrity

    Feel free to discuss homework and labs with other members of the class, myself, or the TA. However, do not look at or copy anyone else's solutions to a homework or lab. I am not concerned with how you come to understand the problem and how to solve it, but once you have the background necessary to solve it, you must provide your own solution.

    The Student Code of Conduct documents your rights and responsibilities as a student.

    Course Materials
    We will be using papers (rather than a synthesizing book) in this class. Some of the course material is presented in these books.

    • Keith D Cooper and Linda Torczon, Engineering a Compiler, Morgan Kaufmann.
    • Steven Muchnick, Advanced Compiler Design Implementation, Morgan Kaufmann.
    • Aho, Sethi and Ullman, Compilers: Principles, Techniques and Tools, Addison-Wesley. (New version with Lam out in August 2006.)
    • Randy Allen & Ken Kennedy, Optimizing Compilers for Modern Architectures, Morgan Kaufmann.

    Topics

    1. Introduction
        compiler structure, architecture and compilation, sources of improvement
    2. Control flow analysis
        basic blocks & loops
    3. Data flow analysis
        lattice theory, iterative frameworks, reaching definitions, liveness
    4. More control flow analysis
        dominators, postdominators, control dependence
    5. Static-single assignment
        static-single assignment, constant propagation.
    6. Global optimizations
        loop invariant code motion, common subexpression elimination, strength reduction.
    7. Interprocedural analysis
        side effects, flow-insensitive, flow-sensitive, constants, inlining.
    8. Register allocation
        coloring, allocation, live range splitting.
    9. Instruction scheduling
        pipelined and VLIW architectures, list scheduling.
    10. Array dependence analysis
        integer linear programming, dependence abstractions.
    11. Loop transformations
        linear loop transformations, loop fusion/fission, enhancing parallelism and locality
    12. Optimistic evaluation of irregular programs
        data parallelism in irregular programs, optimistic parallelization
    13. Optimizing irregular program execution
        points-to analysis, shape analysis
    14. Self-optimizing programs
        empirical search, ATLAS, FFTW