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.
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
The following code is provided as a starting point for your
project. The files listed below live on the ilab cluster in
~uli/cs415/projects/proj3 . Please copy the
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.
You can generate an executable called codegen by
typing make . The executable codegen expects the input on
In order to allow for testing and comparisons, codegen can be called two different
- 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.
- symtab.h and symtab.c: Only offset of variables is interesting for
- Scanner: scan.l (flex); do not modify; simplified over project 2.
- Parser: parse.y (bison); do not modify; simplified over project 2.
- Makefile; do not modify; added valnum.h and valnum.c
- instrutil.h and instrutil.c: definition of emit needs to be
extended for the optimization case
- valnum.h an valnum.c : this is where you implement the signature
- There are a few test programs in subdirectory "testcases";
we may post a sample solution later
- ./codegen < demo : this invokes the unoptimizing compiler which is
provided to you
- ./codegen -O < demo : this invokes your cse optimizing
compiler. This version will use your "optimized" version of emit.
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.
Please see sakai.
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