CS461 -- Compilers
Instructor: Micah Beck --- Fall, 2012
TAs: Yanjun Yao and Chuanjun He
Book: Engineering a Compiler, 2nd Ed. by Cooper & Torczon
CS461 Information
The final exam will be held on Dec 13 at 12:30pm-2:30pm in the classroom.
Lectures and syllabus
I am starting the semester using
these slides from a course taught by the book authors at Rice University in Fall 2010.
I may or may not decide to use these slides throughout the semester.
The syllabus will initially follow the schedule laid out by these slides,
but there may be changes later in the semester.
Supplemental Lectures
There will be some supplemental lectures given by one of the TAs,
particularly covering topics in automated Front End implementation.
These lectures will be given at 2:10pm on Tuesdays in Room 522 in the Dougherty Engineering Building
(next door to Min Kao on the left when walking up the hill towards Ferris).
These supplemental lectures will be announced in class and posted on this page.
No supplemental lectures are currently scheduled.
Exams and Final Grade
There will be a midterm and a final exam. The final is cummulative
(ie any material from throughout the semester may be covered) but will
focus on material from the later part of the semester.
The weighting that will make up the final grade will be
- 20% for the midterm exam
- 30% for the final exam
- 25% for homeworks
- 25% for the course project
The midterm exam will be held on Oct 4 in class. It will cover material through bottom up parsing, but not including intermediate representations.
Homework Assignments
- Assignment 1, Due 9/11/2012 in class: C&T Chap 2, Probs 1-6
- Assignment 2, Due 9/18/2012 in class: C&T Chap 3, Probs 1-5
- Assignment 3, Due 9/25/2012 in class: C&T Chap 3, Probs 7, 8, 11a
- Assignment 4, Due 11/8/2012 in class: C&T Chap 5, Probs 1-3, 5, 7, 9; Chap 6, Probs 1, 2
- Assignment 5, Due 11/27/2012 in class: C&T Cap 7, Probs 1-3, 10-11; Chap 8, Probs 2, 4, 6
Course Project
Part 1, Due 11/13/2012 Read in straight line code in the form of three address code, perform the local value numbering algorithm (p 422 in C&T) and write the three address code back out without redundancies. You should preserve variable names from the original three address code as much as possible.
The three address code
v1 <- v2 op v3
should be represented as a line
v1 v2 op v3
where a variable name can be any legal C variable name and op can be one of the keywords PLUS, MINUS, TIMES or DIV.
Signed integer constants are represented as in C.
Part 2, Due 12/13/2012 Part 2 extends part 1 by requiring that you enhance your redudancy elimination program in part 1 to also handle algebraic identities, constant folding and redudant assignment elimination. There is also an extra credit assignment (worth 20% of your grade in this assignment) to implement local dead code elimination.
- Algebraic identities. Take account of the following agebraic identities in your value numbering:
- x + y = y + x
- x * y = y * x
- x + 0 = 0 + x = x
- x - 0 = x
- x * 1 = 1 * x = x
- x / 1 = x
For example, this code:
x <- w TIMES 1
z <- x PLUS y
w <- w PLUS y
should be replaced by:
x <- w TIMES 1
z <- x PLUS y
w <- z
- Constant folding. Whenever a variable reference is known to be a constant due to a previous constant assignment of the form v <- c,
for exmpale:
x <- 3
z <- x PLUS y
the varaible reference should be replaced by the constant, in this example:
x <- 3
z <- 3 PLUS y
In addition, any operation whose operands are both constant should be replaced by simple assignment of the result, for example:
w <- 3 PLUS 5
should be replaced by
w <- 8
These two constants should be combined, as in this example:
q <- 3
r <- 5
s <- r TIMES q
should be replaced by:
q <- 3
r <- 5
s <- 15
In cases where the operation requires division by zero the code should be left unchanged and an appropriate error warning should be printed starting with the exclamation point character "!".
Note that any two expressions that evaluate to the same constant expression sho
uld be considered to have the same value number. Thus this code:
x <- 2 PLUS 3
y <- 4 PLUS 1
z <- x PLUS 1
w <- y PLUS 1
Should be replaced by:
x <- 5
y <- 5
z <- 6
w <- 6
- Redundant assignment elimination When there is an assignment of a value to a variable which already carries the same value number, the assignment should be eliminated. For example:
c <- a PLUS b
d <- a PLUS b
c <- d
Should be replaced by
c <- a PLUS b
d <- c
Note that redudant assignment elimination should be performed using algebraic identities and after constant folding, so that this code:
x <- 3
y <- 1
z <- x PLUS y
w <- z MINUS 3
w <- w TIMES w
Should be replaced by:
x <- 3
y <- 1
z <- x PLUS y
w <- 1
- Extra Credit: Local Dead Code Elimination. Any assignment to a variable that is killed before it is used should be eliminated. For example:
x <- 3
y <- 1
z <- x PLUS y
z <- x MINUS y
should be replaced by:
x <- 3
y <- 1
z <- 2
Local Dead Code Elimination does not require an iterative algorithm, and can be implementated in a single pass analysis pass over the code followed by elimination of dead assignments.
Note that Local Dead Code Elimination should be performed after the constant folding and redundant assignment elimination.