CS461 -- Compilers
Instructor: Micah Beck --- Fall, 2013
Book: Engineering a Compiler, 2nd Ed. by Cooper & Torczon
CS461 Information
Lectures and syllabus
I will be using
these slides from a course taught by the book authors at Rice University in Fall 2010.
- Overview (Ch 1)
- Scanning (Ch 2)
- Parsing (Ch 3)
- Context Sensitive Analysis (Ch 4)
- Intermediate Representation (Ch 5)
- Inner Workings of Compiled Code (Ch 6, 7)
- Introduction to Optimization (Ch 8)
- Code Selection (Ch 11)
- Instruction Scheduling (Ch 12)
- Register Allcoation (Ch 13)
- More Optimization(time permitting)
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 total course grade is:
- 30% for the midterm exam
- 40% for the final exam
- 30% for the course project
However, the midterm exam grade is calculated as the maximum of the midterm exam grade and the final exam grade. Thus the total course grade is
[MAX(midterm, final) * 30] + [final * 40] + [project*30]
Thus, as long as your final grade is higher than your midterm grade, the midterm grade will not affect your total course grade.
Note: the homeworks are not included in the total course grade!
Reading Assignments
- Week of 9/3: Chapter 2, Sections 2.1 - 2.4
- For 9/10: Chapter 3, Sections 3.1 - 3.3
- For 9/12: Chapter 3, Sections 3.4 - 3.5
- For 9/17: Chapter 4, Sections 4.1 - 4.2
- For 9/26: Chapter 5, Sections 5.1 - 5.2
- For 10/1: Chapter 5, Section 5.3
- For 10/3: Chapter 5, Section 5.4 - 5.5
- For 10/10: Chapter 6, Section 6.1 - 6.3,
- For 10/15: Chapter 8, Section 7.1 - 7.9
- For 10/22: Chapter 8, Section 8.1 - 8.4
- For 10/29: Chapter 8, Section 8.5 - 8.6
- For 10/31: Chapter 9, Section 9.1 - 9.2, 9.4
- For 11/5: Chapter 10, Section 10.1 - 10.3
- For 11/7: Chapter 11, Section 11.1 - 11.3
- For 11/14: Chapter 11, Section 11.4 - 11.5
- For 11/19: Chapter 13, Section 13.1 - 13.3
- For 11/21: Chapter 13, Section 13.4
Homework Assignments
- Assignment 1, C&T Chap 2, Probs 1-6
- Assignment 2, C&T Chap 3, Probs 1-5
- Assignment 3, C&T Chap 3, Probs 7, 8, 11a
- Assignment 4, C&T Chap 5, Probs 1-3, 5, 7, 9;
- Assignment 5 C&T Chap 6, Probs 1, 2
- Assignment 6, C&T Cap 7, Probs 1-3, 10-11
- Assignment 7, C&T Chap 8, Probs 2, 4, 6
- Assignment 8, C&T Chap 9, Probs 2, 3; Chap 10, Probs 1-3; Chap 11, Probs 3, 6; Chap 13, Probs 1, 2, 4
Course Project
Part 1, Due 10/15/2013 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 theRto be keywords PLUS, MINUS, TIMES or DIV.
Signed integer constants are represented as in C.
new Part 2, Due 12/3/2013 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
- 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.