CS 415 Compilers - Project 3: Local Dead Code Elimination
CS 415: Compilers
Project 3: Local Dead Code Elimination
Due date: Wednesday, May 4 Clarifications and Modifications As project1 and project2, this is not a group project.
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:
loadI, loadAI storeAI add, sub, mult 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.
