Instructor: David MacQueen Ryerson 250 By appointment Lecture: TR 10:30-11:50 Ryerson 276 Mailing list: cmsc22620 'at' mailman 'dot' cs 'dot' uchicago 'dot' edu mailman.cs.uchicago.edu/mailman/listinfo/cmsc22620
This course is a continuation of CMSC 22610 and deals with the optimization and code-generation phases of a compiler. We will cover intermediate representations and basic optimizations, dataflow analysis, instruction selection, and register allocation. There will be light homework and a mid-term exam, but main body of required work will be the course project. The source language we will be compiling is MinML, the same subset of SML that was used in CMSC22610 in Winter quarter 2011.
Another more advance textbook by Appel is also relevant:
Title: Modern Compiler Implementation in ML Author: Andrew Appel Publisher: Cambridge University Press, 1998 Errata: www.cs.princeton.edu/~appel/modern/ml/errata.html
The programming assignments will be written using the SML programming language. The following book is one of the better introductions to SML programming.
Title: Compiling with Continuations Author: Andrew Appel Publisher: Cambridge University Press, 1992
The following reference may also be useful:
Title: ML for the Working Programmer (2nd Edition) Authors: L.C. Paulson Publisher: Cambridge University Press, 1996
Title: The Standard ML Library Editors: Emden Gansner and John Reppy Publisher: Cambridge University Press, 2004
Grading for the course will be based on:
Percentage Component 20% Homework assignments 20% Midterm Exam (11/18) 50% Projects 10% Class participation
Assignment Due date Homework 1 April 14 Homework 2 May 5
https://phoenixforge.cs.uchicago.eduThe student svn repositories are accessible at URLs of the form
https://phoenixforge.cs.uchicago.edu/svn/name-icl2where name is replaced by the student CnetID (the user name used to log in to phoenixforge). There is also a common repository for use by everyone at the URL:
https://phoenixforge.cs.uchicago.edu/svn/common-icl2Currently this common repository contains a copy of the compiler from CMSC22610 from last quarter. To check out a working copy of that compiler, which I am calling comp1, run the following svn command:
svn co https://phoenixforge.cs.uchicago.edu/svn/common-icl2/comp1/trunk comp1Phoenixforge and Subversion (Notes from CMSC 22610) provides basic instructions on the use of Phoenixforge and SVN. [Tentative] The project will be divided into five milestones with the following tentative due dates:
April 8: Project 1 --- translation to LambdaIR April 29: Project 2 --- basic code generation May 10: Project 3 --- GC support May 20: Project 4 --- value numbering June 3: Project 5 --- register allocation
MinML Concrete Syntax Project-1 description (for LangF!) Project-2 description x86-64 instructions and ABI Implementing non-local control flow Project-3 description Project-4 description
The Essence of Compiling With Continuations, by Flanagan, Sabry, Duba, and Felleisen. This paper introduced the idea of ANF (Administrative Normal Form). This paper is also available as a pdf download from the ACM Digital Library (available free from the UofC network). <\li> - Representing control: as study of the CPS transformation by Olivier Danvy and Andrzej Filinski. This is an important treatment of the Continuation-Passing-Style (CPS) transform, introducing a variant that handles tail-calls properly.
- Tree Pattern Matching for ML by Marianne Baudinet and David MacQueen. This is the first paper on the problem of compiling optimal pattern matching for an ordered sequence of patterns over algebraic datatypes.
- A Term Pattern-Match Compiler Inspired by Finite Automata Theory by Mikael Pettersson. Another algorithm for compiling merged pattern matching.
- Shrinking Lambda Expressions in Linear Time by Andrew Appel and Trevor Jim. This describes a number of contraction optimizations, that is, reduction rules that will shrink the program.
- Efficient and Safe-for-Space Closure Conversion by Zhong Shao and Andrew Appel. This describes an approach to efficient construction of function closure environments.
- x86-64 Machine-Level Programming by Randal Bryant and David O'Hallaron of CMU. A guide to the programming interface of the x86-64 architecture. See also Gentle Introduction to x86-64 Assembly at www.x86-64.org (an AMD site).
[The following is due to Stuart Kurtz]
The University of Chicago is a scholarly academic community. You need to both understand and internalize the ethics of our community. A good place to start is with the Cadet's Honor Code of the US Military Academy: "A Cadet will not lie, cheat, or steal, or tolerate those who do." It is important to understand that the notion of property that matters most to academics is ideas, and that to pass someone else's ideas off as your own is to lie, cheat, and steal.
The University has a formal policy on Academic Honesty, which is somewhat more verbose than West Point's. Even so, you should read and understand it.
We believe that student interactions are an important and useful means to mastery of the material. We recommend that you discuss the material in this class with other students, and that includes the homework assignments. So what is the boundary between acceptable collaboration and academic misconduct? First, while it is acceptable to discuss homework, it is not acceptable to turn in someone else's work as your own. When the time comes to write down your answer, you should write it down yourself from your own memory. Moreover, you should cite any material discussions, or written sources, e.g.,
Note: I discussed this exercise with Jane Smith.
The University's policy, for its relative length, says less than it should regarding the culpability of those who know of misconduct by others, but do not report it. An all too common case has been where one student has decided to "help" another student by giving them a copy of their assignment, only to have that other student copy it and turn it in. In such cases, we view both students as culpable and pursue disciplinary sanctions against both.
For the student collaborations, it can be a slippery slope that leads from sanctioned collaboration to outright misconduct. But for all the slipperyness, there is a clear line: present only your ideas as yours and attribute all others.
If you have any questions about what is or is not proper academic conduct, please ask your instructors.