Due: Wen. Feb. 15 11:59pm for control flow and Mon. Feb. 20 11:59pm for local value numbering
In this project you are asked to implement value numbering in the URCC compiler.
* Prepare your project directory and copy the two seed files. Replace [255_repos] with your directory name.
cd [255_repos]/assignments/3_vn
mkdir [your_user_id]
cp base/{urcc,vn.rb} [your_user_id]
* Update the environment variables so your urcccompiler can be invoked outside its directory and it can access the urccimplementation in [255_repos]/urcc. If you are using C Shell, you can do so by adding the following lines into your .cshrc file
setenv PATH "$PATH":"[255_repos]/assignments/3_vn/[your_user_id]/" setenv RUBYLIB "$RUBYLIB":"[255_repos]/urcc"
* See if you can run URCC, just type urcc following with your GIMPLE file name, e.g. urcc [255_repos]/urcc/test/odd.c.004t.gimple. By default, the generated c file is odd_urcc.c, and the binary file is odd. You can run oddand it should be able to proclaim that (the number) 255 is odd.
See RochesterCCompiler for the class hierarchy of the URCC intermediate form. If this is your first time to write code in Ruby, you may also have a look at Programming Ruby by Thomas and Hunt (free on-line access for 1st edition).
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).
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 public test programs use only 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. Your compiler will be evaluated in hidden test cases, and an incorrectly optimized program would count against you more so than a failure in compilation.
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). This pass should work same as cs255 pass in project 2. A code skeleton of the pass is given in assignments/3_vn/base/inst_count.rb.
Test your value-numbering URCC compiler on all programs in [255_repos]/assignments/gimple_code/. You may adapt the script assignments/2_pass/base/test.rbfor this purpose.
Count the number of dynamic instructions for each original test program and for its generated version via your URCC compiler. 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.
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.