CS 415: Compilers
Project 3: Local Common Subexpression Elimination
Due date: Wednesday, May 8


Clarifications and Modifications

Subset of Language used in Project 2

The language used for this project is a strict subset of the language used in project 2. The language for project 3 supports only integer types, has only scalar variables, limits the form variable declarations, and supports only assignment and print statements. In other words, every program in this language is a basic block. There is also a limited set of ILOC instructions the compiler can generate: ADD, SUB, MULT, LOADI, LOADAI, STOREAI, OUTPUTAI.

Project Description

You are asked to implement local (basic block) common subexpression elimination using virtual register numbers as value numbers. Using the algorithm discussed in class, you will build signatures and hash them in order to detect whether particular ILOC instructions are redundant or not. The common subexpression detection is done as part of the emit function. If an ILOC instruction is redundant, the generation of the instruction is surpressed, and the virtual register number (i.e., value number) of the register that contains the already computed value is used instead. You will need to implement a signature hash function and supporting infrastructure in files valnum.h and valnum.c.

The project is designed to be a stand-alone project, i.e., you don't need a solution of project 2 to work on project 3. However, the basic structure of the two projects is the same, so you could integrate the two projects. In also should make understanding the overall infrastructure easier.


Getting Started

The following code is provided as a starting point for your project. The files listed below live on the ilab cluster in subdirectory ~uli/cs415/projects/proj3 . Please copy the files into your subdirectory of choice using the command
cp -r ~uli/cs415/projects/proj3 myProjectSubdirectory . You may modify files for your project according to the following guideline.
  1. attr.h and attr.c: Not really needed for this project, but still there to be consistent with project 2. There is no type checking in project 3.
  2. symtab.h and symtab.c: Only offset of variables is interesting for this project.
  3. Scanner: scan.l (flex); do not modify; simplified over project 2.
  4. Parser: parse.y (bison); do not modify; simplified over project 2.
  5. Makefile; do not modify; added valnum.h and valnum.c
  6. instrutil.h and instrutil.c: definition of emit needs to be extended for the optimization case
  7. valnum.h an valnum.c : this is where you implement the signature hash function
  8. There are a few test programs in subdirectory "testcases"; we may post a sample solution later
You can generate an executable called codegen by typing make . The executable codegen expects the input on stdin. In order to allow for testing and comparisons, codegen can be called two different ways:


Due Date

The project is due at 11:59 pm on Wednesday May 8, 2019--that is, one minute before midnight.

If you have specific, overriding, personal reasons why these dates are unreasonable, you should discuss them directly with the instructor before the deadline.

There may only be a limited late submission possible. If late submission is possible, our standard policly of 20% penalty per starting 24 hours applies.


Submission Procedure

Please see sakai.


Grading Criteria

All test cases will be syntactically and semantically correct. The project will be mainly graded on functionality. You will receive no credit for the entire project if your code does not compile and run on the ilab cluster .