CS 701
Section 1
Fall 2016

Thomas Reps
Office: 6361 Computer Sciences
Office hours: By appointment
Phone: 262-2091
E-mail: reps at cs.wisc.edu
WWW URLs: Home page


News

Watch this space for the latest updates.

The class mailing list is compsci701-1-f16@lists.wisc.edu. An archive of mail sent to the class can be found here.

Abstracts for the final-project presentations posted

The abstracts are available here.

Class-Project Presentations

Please sign up for one of the slots on 12/7, 12/9, 12/12, and 12/14. The link to the sign-up sheet was sent in a recent e-mail message to the class. Consult the mail archive if you need to find the link.

Last updated:

Fri Dec 2 11:12:44 CST 2016

Contents


Lecture Information

Lecture: Classes are scheduled for 9:30 PM - 10:45 PM on Mondays, Wednesdays, and Fridays. Classes will be in CS 1257. On average, we will meet twice a week; however, we will front-load the classes (i.e., meet three times a week) until early November, after which you will have about five uninterrupted weeks to work on a project of your own choosing. See the course schedule for the dates on which classes will be held.

Textbook and Notes

There is no required textbook for the course. Much of the reading material for the course is available on-line; see the course bibliography.

Over the semester, we will accumulate a set of on-line notes in this directory. The notes (will) cover the following topics:

and possibly other topics as time permits. The link for notetaker sign-up is here.

Assignments

Problem Set 1

For Problem Set 1, do problems 2, 3, and 4 from the list of partial-evaluation problems.
Due: Monday, Oct. 3, 2016 by 4:30 PM in the box outside 6361 CS.

Problem Set 2

For Problem Set 2, do problems 1 and 2 from the list of dataflow-analysis problems.
Due: Monday, Nov. 7, 2016 by 4:30 PM in the box outside 6361 CS.

Course Project

For the course project, you can work on a problem with a partner or by yourself. The first step is to write a project proposal (2-3 pages) that describes the following items:
  1. The statement of the problem to be investigated
  2. An explanation of why the problem is interesting
  3. A description of what you propose to do
A list of possible project topics will be circulated by e-mail to the class mailing list. However, you are not required to choose one of the topics from the list; you may propose a topic of your own devising. If you are already doing research in some area of CS, you may wish to exploit your existing domain expertise by exploring some compilation-related issue in that area.

So that you have an idea of the scope of an appropriate project, here are the abstracts of the presentations from the Fall 2015 version of the course: Fall 2015 abstracts.

To help keep you on track, I am imposing five deadlines:

  1. Due date (for proposal): Monday, October 10, 2016 in class

  2. Milestone 1: I am interested in evidence that you are making forward progress. I will leave it up to you as to what makes the most sense to turn in. For some projects, it could be some worked examples and a summary of planned next steps; for others, it could be an implementation plan with completed steps checked off. Please turn in an updated proposal (with changes marked with changebars [\usepackage{changebar} if you are using LaTeX]), and your new material added as ``Appendix A: Milestone 1''.
    Due date (for Milestone 1 document): Monday, October 31, 2016 in class.

  3. Milestone 2: Description of progress, implementation plan with completed steps checked off, and experimentation plan. Please turn in an updated proposal (with changes marked with changebars, and your new material added as ``Appendix B: Milestone 2''.
    Due date (for Milestone 2 document): Monday, November 21, 2016 (5:00 PM) in the box outside 6361 CS.

  4. Presentation: 20-minute oral presentations (plus 5 minutes for questions/discussion) will be given during class at the end of the semester. You will need to e-mail me an abstract (in plaintext) giving the title, project participants, and a two-paragraph to three-paragraph summary of what will be presented.
    Due date (for abstract): Monday, December 5, 2016 (5:00 PM) by plaintext e-mail.
    Due date (for presentation): In class on 12/7, 12/9, 12/12, and 12/14.

  5. Final Writeup: The final writeup should be modeled after a typical conference paper. There is no length requirement or limit, but I would expect it to be somewhere around 6-10 pages in one of the full-page, double-column conference formats.
    Due date: Thursday, December 15, 2016 at 9:00 AM in the box outside 6361 CS.

Grading

The course will be graded on the conventional (A-F) system.

I will be looking for a few volunteers to prepare LaTeX notes for one or more of the term's classes -- more about this topic later in the semester. Students who do such a task may receive extra credit.

Policy on Collaborative Work

A certain amount of discussion of problem sets and programming problems (but not take-home exams) is permitted. You should not ``go to someone'' simply to get an answer; the kind of collaboration intended is a discussion with someone else in which you discover the answer jointly. You are not to make a habit of it over the course of the semester. (Points will be deducted if you do an excessive amount of the course work in collaboration with other people.)

When you do work in collaboration with someone else, make a note of it on the solution set or program you turn in. In all cases, you are to do your own write-up. For the programming assignments, you are to do your own programming; sharing of code is not permitted.

For the end-of-course project, you are encouraged to work in groups of two.


Course Summary

CS 701 is a graduate course on compilation (broadly defined). We will begin by studying partial evaluation. Partial evaluation involves evaluating a program when only part of the program's input has been supplied. A partial evaluator operates on a program p that takes a pair of inputs, s (for ``static'', or ``supplied'') and d (for ``dynamic'', or ``delayed''), of which only s is known at partial-evaluation time. Partial evaluation of p with respect to s produces a residual program ps with the property that ps applied to d produces the same answer as that obtained when p is applied to s and d together. Partial evaluation provides insight into such topics as translation, optimization, and run-time code generation.

The second topic is static analysis, which provides a way to obtain information about the possible states that a program reaches during execution, but without actually running the program on specific inputs. Instead, static-analysis techniques explore a program's behavior for all possible inputs and all possible states that the program can reach. To make this feasible, the program is "run in the aggregate"---i.e., on descriptors that represent collections of many states. In particular, we will cover several varieties of interprocedural dataflow analysis

One of the important issues one faces when trying to get a software system to perform as desired is to understand what it is actually doing. Thus, the third topic is compiling for profiling.

The remaining topics have the commonal feature of involving a search in a huge search space of possible results: superoptimization, program synthesis, and autotuning.


Criteria to Use for Reading/Critiquing Assignments

Please use the following criteria (taken from Ben Liblit's CS706 class) for the critiques that you write for the reading/critiquing assignments:
  1. Stated goals and solution. What problem are the authors trying to solve? What are the bounds on this problem, i.e., what are they not trying to solve? What techniques or tools do the authors offer to solve the problem at hand? How do the authors know they have solved the problem? Do the authors test or validate their approach experimentally? Does the solution meet the stated goals, or does it fall short in some way? Avoid simply quoting the authors' own abstract. Restating in your own words demonstrates your understanding.

  2. Cool or significant ideas. What is new here? What are the main contributions of the paper? What did you find most interesting? Is this whole paper just a one-off clever trick or are there fundamental ideas here which could be reused in other contexts?

  3. Fallacies and blind spots. Did the authors make any assumptions or disregard any issues that make their approach less appealing? Are there any theoretical problems, practical difficulties, implementation complexities, overlooked influences of evolving technology, and so on? Do you expect the technique to be more or less useful in the future? What kind of code or situation would defeat this approach, and are those programs or scenarios important in practice?

    Note: we are not interested in flaws in presentation, such as trivial examples, confusing notation, or spelling errors. However, if you have a great idea on how some concept could be presented or formalized better, mention it.

  4. New ideas and connections to other work. How could the paper be extended? How could some of the flaws of the paper be corrected or avoided? Also, how does this paper relate to others we have read, or even any other research you are familiar with? Are there similarities between this approach and other work, or differences that highlight important facets of both?

Course Schedule

What follows is a tentative schedule of topics:

DATES   TOPIC                                   READINGS
===========================================================================
9/7     Intro to partial evaluation              [Jones et al. 93], Chapter 1
                                                 Notes on partial evaluation (Part 1)
                                                 Notes on partial evaluation (Part 2)
                                                 Partial-evaluation problems

9/9     Futamura projections
----------------------------------------------------------------------------
9/12    No Class

9/14    Partial evaluation                       [Jones et al. 93], Section 3.3.3 and Chapter 4

9/16    Partial evaluation
----------------------------------------------------------------------------
9/19    Generating extensions

9/21    Generating extensions;
        Partial evaluation of a first-order      [Jones et al. 93], Chapter 5
        functional language

9/22    Problem Set 1 assigned

9/23    Partial evaluation of a first-order     
        functional language wrap-up
----------------------------------------------------------------------------
9/26    Static program analysis                  Lecture Notes from 10/6/2015
        Brief intro to abstract interpretation

9/28    Static analysis as a path problem        Lecture Notes from 10/8/2015

9/30    Collecting semantics and abstract        Lecture Notes from 10/13/2015
        semantics as a path problem
----------------------------------------------------------------------------
10/3    Interprocedural dataflow analysis        [Sharir & Pnueli 81]
                                                 Lecture Notes from 10/15/2015

10/3    Problem Set 1 due: 4:30 PM in the box outside 6361 CS

10/5    Interprocedural dataflow analysis        Lecture Notes from 10/20/2015
                                                 [RHS 1995]

10/7    Program analysis via CFL-reachability    [Reps 1998]
                                                 PLDI00 Tutorial Slides
----------------------------------------------------------------------------
10/10   Automatic differentiation                Lecture Notes from 12/01/2015
        and back-propagation                     [Olah 2015]

10/10   Initial Course-Project Proposal Due (in class)

10/12   Ball-Larus & Melski-Reps path profiling  [BL 1996] and [MR 1999]
                                                 (Ancient) PowerPoint Slides for [MR 1999]

10/14   Whole program paths                      [Larus 1999]
        Dataflow frequency analysis              [SM 2002]
            based on whole program paths
----------------------------------------------------------------------------
10/17   Finish "Dataflow frequency analysis ..." Lecture Notes from 11/3/2015

10/19   Probabilistic calling context            [BM 2007]
        Efficient call-trace collection          [WXCZZ 2016], PowerPoint slides for [WXCZZ 2016]
                                                 Lecture Notes from 11/17/2015

10/21   Bottom-up rewrite systems (BURS)         [FHP 1992]
                                                 [AGT 1989]
----------------------------------------------------------------------------
10/24   Finish Bottom-up rewrite systems (BURS)

10/24   Problem Set 2 assigned

10/26   Pointer analysis                         Notes on Pointer Analysis

10/28   No Class
----------------------------------------------------------------------------
10/31   Guest Lecture by Karu Sankaralingam on GPUs and compiling for GPUs

10/31   Course Project Milestone 1 Due (in class)

11/2    TBA    

11/4    TBA
----------------------------------------------------------------------------
11/7    No Class

11/7    Problem Set 2 due: 4:30 PM in the box outside 6361 CS

11/9    No Class

11/11   No Class
----------------------------------------------------------------------------
11/14   No Class

11/16   No Class

11/18   No Class
----------------------------------------------------------------------------
11/21   No Class

11/21   Course Project Milestone 2 Due (5:00 PM, in the box outside 6361 CS)

11/23   No Class

11/24-27 Thanksgiving Recess

11/25   No Class (Thanksgiving)
----------------------------------------------------------------------------
11/28   No Class

11/30   No Class

12/2    No Class

----------------------------------------------------------------------------
12/5    No Class

12/5    FINAL PROJECT ABSTRACTS DUE (5:00 PM, by e-mail in plain text)

12/7    FINAL PROJECT PRESENTATIONS I

12/9    FINAL PROJECT PRESENTATIONS II
----------------------------------------------------------------------------
12/12   FINAL PROJECT PRESENTATIONS III

12/14   FINAL PROJECT PRESENTATIONS IV

12/15   FINAL PROJECT WRITEUPS DUE (9:00 AM)
----------------------------------------------------------------------------

Bibliography

[AGT 1989]
Aho, A.V., Ganapathi, M., Tjiang, S.W.K., Code generation using tree matching and dynamic programming. ACM Trans. Program. Lang. Syst. 11(4): 491-516 (1989). [On-line copy: On-campus access.]
[BL 1996]
Ball, T., and Larus, J.R., Efficient Path Profiling. MICRO, 1996. [On-line copies: On-campus access; Off-campus access.]
[BA 2006]
Bansal, S. and Aiken, A., Automatic generation of peephole superoptimizers, ASPLOS, 2006. [On-line copies: On-campus access; Off-campus access.]
[BM 2007]
Bond, M.D., McKinley, K.S., Probabilistic calling context. OOPSLA, 2007. [On-line copies: On-campus access; Off-campus access.]
[FHP 1992]
Fraser, C.W., Hanson, D.R., Proebsting, T.A., Engineering a simple, efficient code-generator generator. ACM Letters on Programming Languages and Systems (LOPLAS) 1(3): 213-226 (1992) [On-line copy: PDF.]
[Hoos 2012]
Hoos, H.H., Programming by optimization. Commun. ACM 55(2): 70-80 (2012). [On-line copies: On-campus access; Off-campus access.]
[Jones et al. 93]
Jones, N.D., Gomard, C.K., and Sestoft, P., Partial Evaluation and Automatic Program Generation, Prentice-Hall International, Englewood Cliffs, NJ, 1993. [On-line copy: PostScript, PDF.]
[Larus 1999]
Larus, J.R., Whole program paths. PLDI 1999. [On-line copies: On-campus access; Off-campus access.]
[Leroy 2009]
Leroy, X., Formal verification of a realistic compiler. Commun. ACM 52(7): 107-115 (2009) [On-line copy (from campus only): PDF.]
[Massalin 1987]
Massalin, H., Superoptimizer: A look at the smallest program. ASPLOS, 1987. [On-line copies: On-campus access; Off-campus access.]
[MR 1999]
Melski, D. and Reps, T., Interprocedural path profiling. In Proc. Int. Conf. on Compiler Construction (CC), 1999. [pdf]
[ND 2010]
Nickolls, J., and Dally, W.J., The GPU computing era. IEEE Micro 30(2): 56-69 (2010). [On-line copies: On-campus access; Off-campus access.]
[Nielson, Nielson, & Hankin 1999]
Nielson, F., Nielson, H.R., and Hankin, C., Principles of program analysis, Springer, 1999.
[Olah 2015]
Olah, C., Calculus on computational graphs: Backpropagation. Aug. 2015. [Blog post.]
[Reps 1998]
Reps, T., Program analysis via graph reachability. Information and Software Technology 40, 11-12 (November/December 1998), pp. 701-726. [pdf]
[RHS 1995]
Reps, T., Horwitz, S., and Sagiv, M., Precise interprocedural dataflow analysis via graph reachability. POPL 1995. [pdf]
[RTP 2016]
Reps, T., Turetsky, E., and Prabhu, P., Newtonian program analysis via tensor product. POPL 2016. [pdf, slides]
[SM 2002]
Scholz, B., and Mehofer, E., Dataflow frequency analysis based on whole program paths IEEE PACT 2002. [pdf]
[SP 1981]
Sharir, M. and Pnueli, A., Two approaches to interprocedural data flow analysis, Program Flow Analysis: Theory and Applications, Chapter 7, Prentice-Hall, 1981. [On-line copy (from campus only): PDF.]
[Veldhuizen 1999]
Veldhuizen, T.L., C++ templates as partial evaluation. Proc. Partial Evaluation and Semantic-Based Program Manipulation, 1999. [pdf]
[WXCZZ 2016]
Wu, R., Xiao, X., Cheung, S.-C., Zhang, H., and Zhang, C., Casper: An Efficient Approach to Call Trace Collection POPL 2016. [pdf, slides]