Project 2. Value Numbering

5%, 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. As you know, 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 #1: set up URCC compiler

* Use the code you checked out in part 1 and change to your working directory, for example /localdisk/gcc/urcc. There is a How_To_Install file which provides instructions for installation. Basically, in order to use urcc from directories other than urcc, you need to add the bin directory into your environment variable PATH, and add the ast directory into your RUBYLIB, which the Ruby interpreter uses to search for needed modules. For instance, you have the top directory, urcc, under /localdisk/gcc/urcc. If you are using C Shell, you can do so by adding the following lines into your .cshrc file

       setenv PATH "$PATH":"$HOME/urcc/bin"
       setenv RUBYLIB "$HOME/urcc/ast"

* Change urcc/ast/driver.rb file (the 22nd line) to specify your own GCC 4.2.2 directory (what you built in Project Part 1). 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"

* Run URCC, just type urcc following with your file name, e.g. urcc ab.c. By default, it will generate a ab.c.*.gimple file, the c file generated by urcc ab_urcc.c, and the binary file ab.

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

* In order to recognize loops, you may have to build control flow graph of the parsed program first. Just follow the algorithm given in the Cooper & Torczon book.

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