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.

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:

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

Thus, as long as your final grade is higher than your midterm grade, the midterm grade will not affect your total course grade.

Reading Assignments

Homework Assignments


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.
  1. Algebraic identities. Take account of the following agebraic identities in your value numbering: 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

  2. 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

  3. 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

  4. 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.