Difference: CS255Spring11P2 (1 vs. 2)

Revision 22011-01-24 - ChenDing

Line: 1 to 1
 
META TOPICPARENT name="CS255Spring11ProjectHome"
Added:
>
>
 

Project 2. Value Numbering

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

Introduction

Changed:
<
<
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.
>
>
In this project you need to implement value numbering in the URCC compiler.

Step #1: set up URCC compiler

 
Changed:
<
<
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.
>
>
* 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"
 
Changed:
<
<
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

>
>
* 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.
 
Changed:
<
<
* 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"
>
>
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).
 
Changed:
<
<
* 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.
>
>

Step #2: build control flow gragh

 
Changed:
<
<
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).
>
>
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.

 
Changed:
<
<
Step #2: build control flow gragh
>
>
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

 
Deleted:
<
<
* 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.
 \ No newline at end of file
Added:
>
>
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.

Revision 12011-01-19 - ChenDing

Line: 1 to 1
Added:
>
>
META TOPICPARENT name="CS255Spring11ProjectHome"

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

Introduction

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.

 
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