Project - Transforming Gotos

Project 1A - Transforming Gotos

Due Date: 02/03/09

Programs should be submitted using the turnin system on CSNET by the time announced. Submissions should be in the form of a single file named project1A_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 inteded to extend your introduction to the internal structures used by the MiniPolaris compiler. Not only will you use the Statement class to identify the types of statements which need to be transformed, but you will also learn how to modify existing StmtList, how to create new statements, how to get Expression type objects from Statement type objects, and how to create new Expression type objects.

This project will locate Arithmetic Ifs and Computed Gotots in a FORTRAN program and transform these into equivalent statements containing only If-Then-Elseif-Else-Endif constructs, and Goto type statments. See Rules to Transform Gotos 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 contain all the statements of the original, with the exception of the transformed Gotos (see Gotos example.) You should alsoprovide 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.

Program Design

Switches

All the routines for transforming gotos should be controlled by switches (such as the file sw used in the above example.) For the gotos pass you will use the following switches :

convert_gotos 1 Convert arithmetic ifs and computed gotos to simple gotos
p_congoto     2 print after convert gotos 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 the default switchfile -- copy it to another file and specify that filename with the -f option when running mypolaris.)

So, if you use a different switchfile which has p_congoto set to 0, then the summary routine will not be called. If you set convert_gotos to 0, then none of the routines will be called (it doesn't make sense to print the program if you have not performed the gotos pass.)

Transform Gotos Pass

Interface

The transform gotos pass should be implemented in the cvdl/gotos directory. You should have a directory and some source files already after running setup. The file gotos.h shows the prototype of the function called from the driver program

void convert_gotos(ProgramUnit & pgm);

NOTE : The original source files provided by setup neglected to make the parameter a reference type (i.e. the & was left out.) This causes the program unit to be duplicated, and any changes you make would be lost upon exiting convert_gotos().

This is a simple pass which takes one program unit as input, transforms any relevant statements inside, and completes, returning nothing.

On linux, the file cvdl/gotos/Makefile includes the lines :

CPPSRCS = gotos.cc # add your other .cc files here
CPPHDRS   = gotos.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.

Algorithm Design

convert_gotos() is given a Program Unit on which to work. It need not output any information (though you will find it useful to do so for the purposes of learning the AST representation of the two statement types as well as debugging your code.)

Outermost Loop

The outermost loop of the pass should simply iterate over every statement of type ARITHMETIC_IF_STMT or COMPUTED_GOTO_STMT. You may either iterate over every Statment and perform the transformation when the type matches either of the two aforementioned types, or you may create an iterator to examine only those type statements, e.g.

Iterator<Statement> stmt_it = stmt_list.stmts_of_type(ARITHMETIC_IF_STMT,
                                                      COMPUTED_GOTO_STMT);

`A`voiding Side-effects

Comparing the original FORTRAN statements to the transformed code, you should note that the controlling expression must be evaluated more than once (for non-trivial instances.) If the statement to be transformed is

      IF (f(x)) 10,20,30

then transforming it to

      IF (f(x) .LT. 0) THEN
        GOTO 10
      ELSEIF (f(x) .EQ. 0) THEN
        GOTO 20
      ELSE
        GOTO 30
      ENDIF

will potentially cause a problem if the function f has any side-effects (e.g. parameter modified or common (global) variable modified.) The solution is to replace the expression with a precalculated value. Fortunately, Polaris provides such a function get_precalc() which is described in cvdl/base/utilities/precalc_util.h . Include "utilities/precalc_util.h" to access this file. An example of its use would be as follows :

        if (! stmt.expr().is_side_effect_free())
        {
            stmt.expr(get_precalc(stmt.expr().clone(), pgm, stmt,
                      PRECALC_ALWAYS, "TEMP")) ;
        }

This first tests to see if precalculation is necessary, and if so, it replaces the expression for stmt (type Statement &) with the precalculation variable as well as inserting an assignment to the precalculation variable just before the current statement. If the above code were applied to

      IF (f(x)) 10, 20, 30

it would then look like

      temp = f(x)
      IF (temp) 10, 20, 30

which avoids side-effects. Also, the variable temp is automatically inserted in the symbol table of the current program unit, so it will be declared. Finally, argument 5 to get_precalc() indicates the suggested name to use. If more than one expression is precalculated, the function will automatically create unique names for successive instances, always with the prefix TEMP.

Creating New Statements

You will need to create new statements to replace the old. In Polaris, most of the statement types provide a method for creation. For example, to create a new Goto statement, you only need to provide a pointer to the target statement (type Statement *) and a new statement tag (the tag simply provides a unique identifier to any statement.) This could look like

GotoStmt * mygoto = new GotoStmt(pgm.stmts().new_tag(),
                                 & somestmt);

Note that simply creating this statement does not insert it into the statement list. You must do so yourself with the ins_after(), ins_before(), or related member functions of StmtList.

However, the If-Then-Else-Endif construct involves multiple statements, which must have consistent references to one another. If you try to insert only an IfStmt Polaris will stop and report an inconsistency. Thus, StmtList provides some functions such as ins_IF_ELSE_after() and ins_ELSEIF_after(). You should carefully examine the description of the parameters. An example of their use is provided in StmtList_test.cc. (Note : many of the techniques used to create expressions are unnecessarily low-level, as there are macros and functions to do much of this work.)

Don't forget that once you have created all the new statements and inserted them in the proper locations that you must delete the old (single) statement.

Creating New Expressions

For any IF or ELSEIF statement, you must provide an Expression, which is the condition. For this project, all conditions will be binary expressions (type BinaryExpr) since you will be comparing the original expression to zero (Arithmetic If) or some index (Computed Goto.)

You must remember that whenever you create a new expression from an old one, that you need to clone the old one to maintain ownership consistency. An example of creating a condition which tests if a previously defined expression is less than zero woud be as follows :

        Expression * lt_id = oldexpr.clone();
        Expression * lt_zero = constant(0);
        BinaryExpr * lte = new BinaryExpr(LT_OP,
                             expr_type(LT_OP,
                                       lt_id->type(),
                                       lt_zero->type()),
                             lt_id,
                             lt_zero);

In this example, oldexpr is of type Expression &. Once you have created lte, you may insert it into an IF statement, for example.

It is highly recommended that you implement this function one step at a time, compiling and testing your latest addition to verify that your additions are correct (see Examples.)

Compiling

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

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

cd ~/minipolaris

make

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

rm libgotos_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/gotos in your personal work directory. To create the file project1A_UIN.tar.gz (where UIN is your UIN number), first clean out all non-relevant files from the gotos 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/gotos

rm *.o libgotos_pkg.so.1

cd ..

tar cf - gotos | gzip > project1A_UIN.tar.gz

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

You need to log on csnet.cs.tamu.edu and turn in proj-gotos.tar.gz.

Rules to Transform Gotos

Arithmetic If Statement

Form :

      IF (expr) label1, label2, label3

Example :

      IF (i) 10,20,30

Transformation :

      IF (expr .LT. 0) THEN
          GOTO label1
      ELSEIF (expr .EQ. 0) THEN
          GOTO label2
      ELSE
          GOTO label3
      ENDIF

This is assuming that the precalculation transformation was performed before, and if necessary, expr represents the precalculation variable.

Computed Goto Statement