Project 1B: Basic Blocks (Part B)

Project 1B: Basic Blocks

Due Date: 02/09/07

Programs should be submitted using the turnin program on csnet.cs.tamu.edu by the announced time. Submissions should be in the form of a single file named project1B_UIN.tar.gz file (where UIN is your UIN number) containing the relevant source code and a README file explaining your approach (see Creating .tar.gz File below on how to create and submit this file.)

Introduction

This project is intended to be an introduction to the internal structures used by the MiniPolaris compiler, specifically the Statement, StmtList, ProgramUnit, and Program types.

This project will collect information about the basic blocks in a FORTRAN program, comment the FORTRAN code to show where the basic blocks begin, and print a summary of the basic blocks for each program unit. See Rules to Define Basic Block Boundaries below for hints.

Input and Output

Input

The input to your program will be a FORTRAN 77 program. This will be specified on the command line when running your copy of MiniPolaris, e.g.

mini_polaris -f sw test.f > test.list

In this example, test.f is a FORTRAN program which you want to compile.

We save the output to the file test.list which may be examined for correctness. The file sw contains your own copy of the switchfile in your work directory. (see Switches.)

Output

The output that MiniPolaris produces goes to stdout (error messages to stderr) and is a listing containing information produced by the compiler during each pass of the compiler. Converting this list file to an actual FORTRAN file is done as follows :

list2src < test.list > test.P.f

The .P.f ending indicates the file potentially contains parallelization directives, which is not relevant for this assignment, but which is important to the purpose of the Polaris compiler.

The output FORTRAN program produced by this project should include comments before the first statement in each basic block identifying that basic block (see comment example.) Additionally, you should provide a method to summarize the basic blocks for each program unit (see summary example.) A summary should contain the number of basic blocks, and for each basic block, what is the first statement and last statement, and the successor(s) and predecessor(s) (which will be other basic blocks.) And finally, you should provide the option of printing out the current subprogram just after you have found the basic blocks, either in normal FORTRAN or a detailed listing of the abstract syntax tree (see AST exmple.)

Program Design

Switches

All the routines for finding and summarizing basic blocks should be controlled by switches (such as the file sw used in the above example.) For the basic block pass you will use the following switches :

basic_blocks

1 Find the basic blocks

bb_mark

1 Annotate basic blocks

p_bbsummary

1 Print a summary of basic blocks for each program unit

p_bblocks

2 print after basic blocks pass (1 == Fortran form, 2 == all fields)

These values are the default as specified in the file switches in your work directory (do not remove this file since it is a symbolic link to the default switchfile -- copy it to another file and specify that filename with the -f option when running mini_polaris.)

So, if you use a different switchfile which has p_bbsummary set to 0, then the summary routine will not be called. If you set basic_blocks to 0, then none of the routines will be called (it doesn't make sense to print the summary if you have not found the basic blocks.)

Basic Block Pass

The basic block pass should be implemented in the cvdl/bblock directory. You should have a directory and some source files already after running setup. The file bblock.h shows the prototypes of the two functions called from the driver program

List<BasicBlock>   * find_basic_blocks(ProgramUnit & pgm);
void                summarize_basic_blocks(ProgramUnit &pgm,
                                           List<BasicBlock> * bbl,
                                           ostream &o);

Note that this requires you use the class BasicBlock and that it is derived from type Listable, in order to be able to use it as part of a List. Several hints are provided for this assignment to get you started. The function find_basic_blocks() should return NULL if the type of program unit represented by pgm is not a program, subroutine, or function. (Hint : look at cvdl/base/ProgramUnit.h for the various types allowed and how to find out what type pgm is.)

You will probably need to use the class WorkStack to accomplish the function find_basic_blocks(). (see WorkStack example.)

Or on linux, the file cvdl/bblock/Makefile includes the lines :

CPPSRCS = bblock.cc # add your other .cc files here

CPPHDRS = bblock.h BasicBlock.h # add your other .h files here

If you create other source files, you should add them to these two lines so they will be compiled and linked into the final program.

It is highly recommended that you implement these functions one step at a time, compiling and testing your latest addition to verify that your additions are correct. Be sure to follow the hints on print format and naming of basic blocks so that your output is identical to the examples (see Examples.)

Compiling

You can re-compile your files from within the bblock directory as long as you have compiled mini_polaris for once. In another word, there is already a mini_polaris generated.

If you have not compiled out mini_polaris yet, change to your work directory and run make, i.e.

cd ~/minipolaris

make

If you make some changes and want to recompile, just type make at the bblock directory. Or, if you want to do it from the top-level makefile, you should do (suppose you are at the bblock directory)

rm libbblock_pkg.so.1

cd ~/minipolaris

make

Examples

Sample FORTRAN programs are provided in the samples. The first example for this project is explained here. You should examine the files themselves in the samples to see how the complete files look.

Creating .tar.gz File

The files necessary for submission should be all source code (.cc and .h) and the Makefiles in the directory cvdl/bblock in your personal work directory. To create the file project1B_UIN.tar.gz (where uin is your UIN number), first clean out all non-relevant files from the bblock directory, including any objects or libraries (i.e., any .o files.) Then change to your cvdl directory and then tar and compress the files as in the following example :

cd ~/minipolaris/cvdl/bblock

rm *.o libbblock_pkg.so.1

cd ..

tar cf - bblock | gzip > project1B_UIN.tar.gz

gzcat proj-bblock.tar.gz | tar tvf -       # this will list the files for verification

Rules to Define Basic Blocks Boundaries

The FORTRAN code can be splited into its basic blocks using ` following rules:

The very first line is the START of a BB.
Any GOTO is the END of a basic block and the next line is the START of a new basic block.
Any target of a GOTO is the START of a BB.
IFs:

 
         IF (Exp) THEN 
            Stat 
         ENDIF

      
         IF (!E) GOTO 001
            Stat
            IMPLIED GOTO 001
    001  CONTINUE

DO Loops:

        DO I=1,10
           Stat
        ENDDO

        I=1
   001  IF (I .GT. 10) GOTO 002
        Stat
        I=I+1
        GOTO 001
   002  CONTINUE

When the function find_basic_blocks() is called, Polaris will have already scanned the input program and represented it as an AST. So, it is unnecessary to examine the type of statement because the successors and predecessors by statement are already available. You can also find out the next and previous statement lexicographically (i.e. the line before and the line after in the original program.) This makes it very easy to determine if a statement jumps to any other statement except the next line (one of the requirements for the end of a basic block) or if it has more than one possible successor/predecessor statement.

Department of Computer Science and Engineering | Dwight Look College of Engineering | Texas A&M University
Privacy statement: Computer Science and Engineering Engineering TAMU