CS 415: Compilers
Project 3: Local Dead Code Elimination
Due date: Wednesday, May 4

Clarifications and Modifications

Project Description

You are asked to implement local (basic block) dead code elimination pass for ILOC programs. You may assume that values have unique register names, i.e., that the ILOC code follows the register-register model where register numbers are not reassigned.

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, you may choose to use your own infrastructure of project 1 to implement project 3 since both projects take ILOC instructions as input and generate ILOC instructions as output. Your optimizer needs to support the following ILOC instructions in the input code:

  1. loadI, loadAI
  2. storeAI
  3. add, sub, mult
  4. outputAI
Please note that the code provided to you supports more than these instructions, but your dead code elimination pass is only expected to be able to handle the above instructions. All test cases will be limited the above instructions.

Local dead code elimination identifies ILOC instructions that are executed in the basic block but do not contribute to the output of the program. A dead code elimination pass is often used in optimizing compilers as a "clean-up" optimization after other optimizations.

Dead Code Elimination Algorithm

The ILOC instruction sequence of the single basic block is read from a file into an internal representation. The provided code uses a doubly-linked list to represent the sequence of ILOC instructions of the basic block. Each instruction should have a "critical" flag. To start, all output instructions are flagged as critical. All instructions that contribute to the computation of the values of critical instructions are themselves marked critical. You may think of this process as chasing the true dependencies backwards through the basic block. Dependencies can either go through registers or through memory locations.

Dead code elimination does not change the relative order of instructions. Once the marking process reaches a fixed-point, i.e., no instruction needs to be added as critical any more, the optimized code can be generated. In sequential order, print out the instructions that are marked critical, ignoring those that are not marked.

Getting Started

C code is provided as a starting point for your project. You can use this code, but you may also choose to use your own programming infrastructure as in project 1. Remember that this infrastructure has to be available on the ilab cluster.

Please copy the files into your subdirectory of choice using the command
cp -r ~uli/cs415/projects/proj3/students myProjectSubdirectory . You may modify the files for your project as you see fit. However, your dead code eliminator has to take an ILOC program as input on stdin and produce ILOC code as output on stdout:
./deadcode < input.iloc > output.iloc
This is important since we will use an automatic grader.

You can generate an executable called deadcode by typing make . There are a few test programs in subdirectory "testcases". Please should design your own test cases as well.

Due Date

The project is due at 11:59 pm on Wednesday May 4, 2021--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 use canvas to submit your project.

Grading Criteria

All test cases will be syntactically and semantically correct. The project will be graded on effectiveness. You will receive no credit for the entire project if your code does not compile and run on the ilab cluster . If you choose to use your own programming infrastructure, you must include a ReadMe file to let the grader know how to execute your dead code optimization pass.