Project 3 for CSC 255/455, Spring 2014

Project 3: Value Numbering in URCC

Due: Fri. March 28 11:59pm for control flow and Fri. April 4 11:59pm for local value numbering


In this project you are asked to implement value numbering in the URCC compiler, a mini compiler written in Ruby.

Step #1: set up URCC compiler

* Check out the source code (all files can be found under [255_repos]/urcc/). Read RochesterCCompiler for the class hierarchy of the URCC intermediate form.

* Prepare your project directory and copy [255_repos]/assignments/3_vn/base/{urcc, inst_count} to your own working directory. Don't forget to switch back to your branch before you start your work.

* See if you can run URCC directly, just type ./urcc with a C file name, e.g., input.c. The compiler will parse the corresponding LLVM intermediate file (input.c.ll) and generate two C files in current working directory: input_urcc.orig.c is the un-optimized source code dumped from the original AST; input_urcc.c dumped from your optimized AST (if there is any optimization). Also, a binary file, input_urcc.bin will be generated.

* See if you can run inst_count. Read its source code to learn how to add a pass to urcc. Note that there could be a chain of passes. Handle the ordering among them carefully.

Step #2: build control flow gragh

Before value numbering, you need to build control flow graph of the input program. Follow the algorithm in the Cooper & Torczon book, Figure 5.6 on page 241 (Figure 9.1 in the first edition). Design data structures and implement your CFG pass.

Step #3: implement value numbering

Value numbering can be carried out in different scopes: basic block, extended basic block, or dominator block. In this assignment, you are required to implement basic-block value numbering. Optimizing at a larger scope is encouraged and will be given extra credits.

The test programs (under assignments/test_cases) mainly use basic arithmetic and logical operations. Your compiler is required only to correctly optimize these programs. It does not need to support pointer operations except to allow the taking-address operation in scanf. The absence of dynamic data allocation and pointer dereference removes most of the aliasing concerns and gives you more room for optimization. In addition, if you are taking CS255 instead of CS455, your compiler does not need to support or optimize array operations.

Your compiler may fail if a program contains operations it does not support. It should fail gracefully: it should check for cases it does not support, and when it finds such cases, output a descriptive error and exit. Documenting what your compiler checks in the README file is a good idea. Under no circumstances it may generate incorrect code. An incorrectly optimized program would count against you more so than a failure in compilation.

Your value numbering pass should be able to run as an individual command, just like urcc or inst_count.

Step #4: finish the inst_count pass to count the run-time operations

To measure the effect of value numbering, another URCC pass is required to count and output the number of run-time statements (AssignStat and GotoStat). A code skeleton of the pass is already given in assignments/3_vn/base/inst_count.

Step #5: test and report

Test your value-numbering URCC compiler on all programs in [255_repos]/assignments/test_cases/. You may use the script assignments/3_vn/base/test.rb to do this automatically. For example, the command "./test.rb all ./inst_count" will invoke inst_count pass on all test cases and save the test reuslt in your current working directory.

Count the number of dynamic instructions for each original test program (inst_count pass) and for its optimizied version (your VN pass + inss_count pass). Report these two numbers as before and after results.

You are required to submit the program files for value numbering and a report file outlining your design and listing the before and after instruction count for all test programs. The report file may be in plain text or pdf.

Result sharing

You are encouraged to check in your early results into the repository so you can see each other's numbers while working on the project.