create new tag
view all tags

Project 2. Value Numbering

20%, Individual Project, Due: Mon. Feb. 7 11:59pm for control flow and Mon. Feb. 14 11:59pm for local value numbering


In this project you need to implement value numbering in the URCC compiler.

Step #1: set up URCC compiler

* Prepare your project directory and copy the two seed files.

 cd [255_repos]/projects/2_vn
 mkdir [your_user_id]
 cp base/{urcc,vn.rb} [your_user_id]

* Update the environment variables so your urcc compiler can be invoked outside its directory and it can access the urcc implementation 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]/projects/2_vn/[your_user_id]/"
  setenv RUBYLIB "$RUBYLIB":"[255_repos]/urcc"

* Configure URCC to use GCC 4.2.x. Change urcc/ast/urcc file (the 4th line) to specify your own GCC 4.2.2 directory. For example, if the gcc you built last time is under /localdisk/gcc/gcc-build/bin/gcc, then change that line to:

  Yourgcc = "/localdisk/gcc/gcc-build/bin/gcc"

* See if you can run URCC, just type urcc following with your file name, e.g. urcc [255_repos]/urcc/test/odd.c. By default, it will generate an odd.c.*.gimple file in your current directory. The generated c file is odd_urcc.c, and the binary file is odd. You can run odd and it should be able to proclaim that (the number) 255 is odd.

See CS255Spring09ProjectRubyTrack for more information about URCC compiler and 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).

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, Chapter 9, Fig. 9.1 on page 439.

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 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.

Step #4: test and report

Test your value-numbering URCC compiler on all programs in [255_repos]/projects/test_cases/. You may adapt the script projects/1_gcc/base/test.rb for this purpose.

To measure the effect, use your GCC compiler from Project 1 to 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.

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.

Edit | Attach | Watch | Print version | History: r2 < r1 | Backlinks | Raw View | Raw edit | More topic actions
Topic revision: r2 - 2011-01-24 - ChenDing
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2020 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding URCS? Send feedback