COS598C Assignment 2: Hyperblock Formation

Update - March 24: For l-bench to work correctly, glib-devel (version 1.2) package must be installed in addition to the glib package.
Update - March 19:

The getNewCB() method only creates an empty ControlBlock. The method doesn't add the newly created CB to the IR hierarchy. To do that use the getParent() method to get the parent of the original ControlBlock in the IR tree and add the newly created block using addChildBefore() method.
Download compiler.jar file and replace the compiler.jar in the assignment2 directory with this new file. This fixes some bugs which were present in the previous version.

Update - March 8: The emulator framework is now available. Follow these instructions to install and use the emulator:

Download assignment2_new.tar.gz
Untar the file. This will create a directory starting with assignment2
Edit the velocity_env file and set the VELOCITY variable to assignmen2/velocity directory and then source the velocity_env file.
If you have modified the Hyperblock.java and ControlDependence.java files, copy them to assignment2 directory
Follow the steps to build and execute the code. HyperblockMain will now create a < benchmark_name>/program.m4 file in addition to the .hyper file
Run echo <benchmark_name> | l-bench from the assignment2 directory. This will generate a set of C files from the .m4 file, compile them, execute it with required params and take a diff with the expected output. If your code works correctly, there should be no difference in the outputs.

Note: You need an installation of glib package(version 1.2.10 or above) in your system

This assignment involves forming hyperblocks out of the Control Blocks in innermost loops. Hyperblock formation involves the following steps:

Step 1 : Loop detection and back edge coalescing
Step 2 : Selecting certain basic blocks in the loop as candidate blocks for the hyperblock
Step 3 : Tail duplication to ensure there are no side entrances
Step 4 : Finding control dependence information
Step 5 : Finding predicate registers for each basic block in the hyperblock
Step 6 : Predicating the basic block code to get hyperblock

Out of these steps 1 and 6 are provided for your use.

Since the next assignment will be based on this, it is important that you use good heuristics for selecting candidate blocks. In the next assignment, your code will be evaluated for
performance and so a bad selection of candidates will have its impact on the next assignment

Software and installation directions:

Download this file and untar it
Set your CLASSPATH environment variable to:
.:./compiler.jar:./utility.jar:./functor.jar

Compile the files using the command:

javac -source 1.5
HyperblockMain.java

Run using

java HyperblockMain wc

Running the program will produce wc.hyper file. If you fill in the holes in the .java files given to you the resulting .hyper file will have hyperblocks.

Resources:

Documentations for the compiler and the Library packages

Verifying the correctness of your code :

Soon, the files and directions for creating an Lcode emulator for your output file will be posted here. The scripts will run your hyperblock code and verify that it has produced the correct code

Easwaran Raman (eraman at cs)

Last modified: Sat Mar 20