Project 2 for CSC 255/455, Spring 2012

Project 2: Adding a pass in GCC/LLVM

Due: Mon. Feb. 6 11:59pm

Introduction

For a taste of the most widely used compilers, you will implement a simple pass inside GCC or LLVM to count and output the number of executed statements when the program executes. If you follow the instructions below, the project should not take more than four hours. The purpose is to learn the process more than to learn the compiler. You will use a different compiler in later projects but the basic three-phase structure --- a front-end, a set of optimization passes, and a back-end ---is the same.

You can choose either GCC or LLVM as your baseline compiler. But a GCC writer should pair with an LLVM writer for the last part which is to compile a list of pros and cons comparing the two compilers. Please refer to the following GCC/LLVM sections to build your own compiler.


 

GCC

Install GCC

Here we use GCC-4.2.2. It is not the most recent GCC, but should be sufficient for our project. Check out the code from GCC read-only repository, following the commands below. For more information about GCC debugging and data structure, check out the instructions, pointers, and discussions from 2009 project page.

**step #1 Check out gcc source code. It will over 700MB disk space, let's not to store it in your home directory in your CS account. Use either your personal machine or the local disk on one of the public use machines in the CS department. The local disk in these machines can be accessed at /localdisk. Create your own directory first. The local disk is not shared. You have to log into the machine to access its local disk. If you use your personal machine, please note that for testing purpose, you will need to have your compiler and the class repository accessible from your machine, and the machine should be able to run Unix commands and Ruby scripts.

    cd  /localdisk/your_dir
    svn co svn://gcc.gnu.org/svn/gcc/tags/gcc_4_2_2_release gcc-4.2.2

**step #2 Apply the cs255 patch file and copy in cs255.c. They are in the class repository under assignments/2_pass/base/gcc/.

   cd gcc-4.2.2
   cd gcc
   patch -i [class_repos]/assignments/2_pass/base/gcc/cs255.patch
   cp [class_repos]/assignments/2_pass/base/gcc/cs255.c .
   cd ../..

**step #3 Install GCC

    mkdir obj
    cd obj
    ../gcc-4.2.2/configure --prefix=$INSTALL_DIR 
        // $INSTALL_DIR is the directory you want to install your compiler, such as $HOME/gcc-build
        // If you encounter the error "error: Building GCC requires GMP 4.1+ and MPFR 2.3.0+", 
        // please download gmp or mpfr from ftp://gcc.gnu.org/pub/gcc/infrastructure 
        // and put the extracted directory under $HOME/gcc/gcc-4.2.2/
    make
    make install

* If you are not familiar with subversion, take a look at the VersionStuff page.

* Gnu's wiki page on the generic installation procedure for GCC.
 

Add the cs255 pass

In the cs255.patch, you are provided with a file cs255.c, which has code to first add a call init()at the beginning of the main function, which has a global counter initialized to 0; then add a call before each (gimple---GCC intermediate form) statement, which increments the counter; and finally add a call at the exit, which reports the run-time instruction counts. The three functions are provided in 2_pass/base/gcc/cs255-lib.[ch].

  • Put your own code into gcc-4.2.2/gcc/cs255.c
  • Initialization: you'll need to add it at the entry of the mainfunction
  • Increment: to be added before each real gimple statements (all except for labels)
  • Report: to be added at all possible exits of the program
  • Remember to add #include "cs255-lib.h"in your testing programs.
  • Invoke your pass: use gcc -O2 -fcs255 your_test_prog cs255-lib.c

This part should take at most tens of lines of code and no more than a day (including half an hour compiling the compiler for the first time). The purpose is to get you familiar with GCC and the basic GCC functions that you'll need for adding your optimization passes. Reading the relevant, existing code (in gcc-4.2.2/gcc/cs255.c) is the best way to help you implementing the required pass. For instance, the code for counting the number of basic blocks and statements statically is already in the file. The code for getting the dynamic count of the basic blocks is also given.

For testing, we use the test cases in directory assignments/test_cases. You may use the results from them to check your code with your classmates. And they are very useful in following parts.
 


 

LLVM

Install Clang + LLVM

LLVM (http://www.llvm.org) is a modern compiler infrastructure widely used in both academia and industry.  CLang is a LLVM front end. Here we use Clang+LLVM 3.0.

**step #1 Check out source code. It will over 70MB disk space, let's not to store it in your home directory in your CS account. Use either your personal machine or the local disk on one of the public use machines in the CS department. The local disk in these machines can be accessed at /localdisk. Create your own directory first. The local disk is not shared. You have to log into the machine to access its local disk. If you use your personal machine, please note that for testing purpose, you will need to have your compiler and the class repository accessible from your machine, and the machine should be able to run Unix commands and Ruby scripts.
Checkout LLVM:

    cd  /localdisk/your_dir
    svn co http://llvm.org/svn/llvm-project/llvm/tags/RELEASE_30/final/ llvm

Checkout Clang:

    cd llvm/tools
    svn co http://llvm.org/svn/llvm-project/cfe/tags/RELEASE_30/final/ clang

**step #2 Apply the cs255 patch file and copy in cs255.c. They are in the class repository under .

    cd ..
    patch -p1 < [class_repos]/assignments/2_pass/base/llvm/cs255.patch
    touch lib/Transforms/Cs255/Cs255.exports

**step #3 Build LLVM and Clang.

    cd .. (back to where you started)
    mkdir build (for building without polluting the source dir)
    cd build
    ../llvm/configure --disable-optimized
    make

When the building procedure is over, Clang, opt and llc are in /localdisk/your_dir/build/Debug/bin. Cs255.so is in /localdisk/your_dir/build/Debug/lib.
 

Add the cs255 pass

In this part, you will add a pass that will insert code into a program to count and output the number of LLVM-IR when the program executes. You need to first add a call at the beginning of the main function, which has a global counter initialized to 0; then add a call before each LLVM-IR statement, which increments the counter; and finally add a call at the exit, which reports the run-time instruction counts. The three functions are provided in cs255-lib.cand cs255-lib.h. These two files are already included in assignments/test_casesdirectory when you check out padding files.

  • Put your own code into $LLVM_SRC/lib/Transforms/Cs255/Cs255.cpp
  • Initialization: you'll need to add it at the entry of the main function
  • Increment: to be added before each real LLVM-IR statements (all except for ALLOCA statments)
  • Report: to be added at all possible exits of the program
  • Invoke your pass: use opt -load $BUILD/Debug/lib/Cs255.so -cs255 your_bitcode_files

This part should take at most tens of lines of code and no more than a day (including half an hour compiling the compiler for the first time). The purpose is to get you familiar with LLVM and the basic LLVM functions that you'll need for adding your optimization passes. Reading the relevant, existing code (in $LLVM_SRC/lib/Transforms/Cs255/Cs255.cpp) is the best way to help you writing your new code in an existing system. For instance, the code for getting the dynamic count of the basic blocks is given. For testing, there are some test case in directory test_cases. You may use the results from them to check your code with your classmates. And they are very useful in following parts.

Useful tips

  • Use the front end--- clang to do the transformation from C code to LLVM-IR in bitcode format
  • Use the middle end--- opt to call our project optimization on bitcode
  • Use the bitcode linker--- llvm-link to merge all related bitcode into a single bitcode file
  • Use the virtual machine---  lli to run bitcode, or use the static compiler--- llc to compile bitcode into the native binary code
  • Use llvm-dis to generate bitcode in textual format for debugging

For more build and information, please read http://clang.llvm.org/get_started.html.
 


 

Automated testing

You are provided with a testing harness at assignments/2_pass/base/test.rb. Suppose your current working directory is assignments/2_pass/paul, you can use

../base/test.rb ab.c /usr/bin/gcc or ../base/test.rb ab.c /usr/bin/clang

to test the default copmiler on the test ab.c(or any other file in test_cases), or you can use

../base/test.rb all /user/bin/gcc or ../base/test.rb all /usr/bin/clang

to test all C programs in the test directory. Some of the programs require inputs. The test harness provides the default inputs. You can test your cs255 compiler similarly by modifying test.rb, in particular, uncommenting the two lines marked in the file. In addition, supply your compiler (path to your own gccor clangcommand) in place of /user/bin/gcc as the second argument when running test.rb.

 


 

Submit your project

Create a directory in the repository as assignments/2_pass/your_cs_user_id. Submit the source code (only the modified cs255.c if you use GCC, or Cs255.cpp if you use LLVM), along with a report document, either in text or pdf, describing the design and implementation.

Your report should contain the instruction counts generated by your compiler for all test programs with the standard inputs. Use the test scripting test.rb, which generates a summary of results when it is run with "all" as the second parameter. You should include the summary in the report.

You will submit your own comparison (can be the same as the partner's) in the report.  Other than the technical discussion, the rest, compiler pass and report, should be individual work.  The project will be graded individually.

* assignments/2_pass/basecontains base code for your work, but you are not supposed to modify any file under it in your submission. Please keep all your files under assignments/2_pass/your_cs_user_id.