The Cetus Compiler Manual

Cetus is a set of intermediate representation (IR) classes and optimization passes. It currently has a built-in C parser written in Antlr, but relies on a separate program to parse C++. Thus, there are three items you need to obtain for full functionality.

The IR and passes are available at http://www.ece.purdue.edu/ParaMount/Cetus/download.html. This part runs on any system supporting a Java run-time environment, and is covered by the above license. It is available now.

Source and binaries for Solaris and Linux will be supplied for the separate parser. The parser is covered by the GNU General Public License. It incorporates some code and ideas from GCC for increased compatibility with SPEC benchmarks. It also includes some code from the libiberty library to provide command-line handling on systems lacking library support for command-line handling. Purdue Solaris is an example of such a system where neither libpopt nor getopt_long are available. (The standard getopt is insufficient for compilers, which have many options and cannot be limited to single-character flags.) Note that there is no linking, not even at run time, between the Cetus IR code, written in Java, and the parser code, written in C++. The parser and IR communicate through an intermediate data file that uses the graphviz format.

From a substantial list of compiler infrastructures, we choose to discuss three open-source projects that most closely match our goals. The goals are to create a source-to-source infrastructure that supports C and is extensible to other languages. The three projects are the GNU, Polaris, and SUIF compilers. We explain our reasons for not using these infrastructures as our basis, and also discuss important features of these compilers that we want to adopt in Cetus.

Cetus' IR contrasts with the Polaris Fortran translator's IR in that it uses a hierarchical statement structure. The Cetus IR directly reflects the block structure of a program. Polaris lists the statements of each procedure in a flat way, with a reference to the outer statement being the only way for determining the block structure. There are also important differences in the representation of expressions, which further reflects the differences between C and Fortran. The Polaris IR includes assignment statements, whereas Cetus represents assignments in the form of expressions. This corresponds to the C language's feature to include assignment side effects in any expression.

The IR is structured such that the original source program can be reproduced, but this is where source-to-source translators face an intrinsic dilemma. Keeping the IR and output similar to the input will make it easy for the user to recognize the transformations applied by the compiler. On the other hand, keeping the IR language independent leads to a simpler compiler architecture, but may make it impossible to reproduce the original source code as output. In Cetus, the concept of statements and expressions are closely related to the syntax of the C language, facilitating easy source-to-source translation. However, the drawback is increased complexity for pass writers (since they must think in terms of C syntax) and limited extensibility of Cetus to additional languages. That problem is mitigated by the provision of several abstract classes, which represent generic control constructs. Generic passes can then be written using the abstract interface, while more language-specific passes can use the derived classes. We feel it is important to work with multiple languages at an early stage, so that our result is not simply a design that is extensible in theory but also in practice. Toward this goal, we have begun adding a C++ front end and generalizing the IR so that we can evaluate these design trade-offs. Other potential front ends are Java and Fortran 90.

Cetus does not contain a code generator. It is a source-to-source compiler, and so it relies on other compilers (such as GCC or the Sun compiler) to compile the source code it outputs. It is possible that in the future a back end could be added to Cetus, but for research purposes other compilers are more suited to back end optimization work.

There are two ways to extend Cetus to run a new pass.

The IRIterator class implements the Java Iterator interface plus some added functionality. The BreadthFirstIterator and DepthFirstIterator iterate over the IR in breadth-first and depth-first order, respectively. The FlatIterator simply iterates over an object's children, and does not perform a "deep" traversal within the children. An IRIterator can be made to skip objects such that it only returns objects of certain types. It can also be made to prune parts of the traversal below objects of certain types.

IRIterators provide several versions of next that are explained in the examples below. The first example shows how to use the standard next:

/* BreadthFirst traversal over everything in a procedure. Assumes proc is a Procedure object. */

BreadthFirstIterator iter = new BreadthFirstIterator(proc);
while (iter.hasNext())
{
  Object o = iter.next();
  // Do something with the object
}

The next example shows how to locate a particular type of object:

/* Look for loops in a procedure.  Assumes proc is a Procedure object. */

BreadthFirstIterator iter = new BreadthFirstIterator(proc);
try {
  while (true)
  {
    Loop loop = (Loop)iter.next(Loop.class);
    // Do something with the loop
  }
} catch (NoSuchElementException e) {
}

Note the exception handling. next must throw an exception if it cannot find an element of the specified class, because the corresponding hasNext method cannot be implemented. The reason is the iterator would have to actually perform the iteration to determine if there was such a next element, and if true, would need to perform the iteration again to actually return the object. The standard hasNext does not have have this problem because it simply checks if it has reached the end of the list. We think it would be very strange for users if we provided a hasNext method that modified the iterator, and it would be awkward for us to write a hasNext that would look ahead and then undo its changes. Furthermore, that version of hasNext would no longer be a Θ(1) call, so we chose not to provide it.

Other versions of next will find an element of a set of classes, or an element that is not of a set of classes.

The next example shows how to use pruning:

/* Look for procedures in a program.  Assumes prog is a Program object. */

BreadthFirstIterator iter = new BreadthFirstIterator(prog);
iter.pruneOn(Procedure.class);

try {
  while (true)
  {
    Procedure proc = (Procedure)iter.next(Procedure.class);
    // Do something with the procedure 
  }
} catch (NoSuchElementException e) {
}

Instead of obtaining one iterator on the Program object to look for TranslationUnits, and then obtaining another iterator on each TranslationUnit to look for Procedures, it is easier to do a breadth first search on the entire Program. However, it does not make much sense to look for Procedures inside other Procedures, since none of the languages supported by Cetus allow nested Procedures. Therefore, pruneOn tells the iterator to skip anything below a Procedure on the IR tree.

The Tools class is a group of static methods for performing common operations, such as printing lists.

The expression simplifier provides a very important service to pass writers. Our experience with the class project showed that source-to-source transformations implemented within GCC often resulted in large, unreadable expressions. GCC does not provide a symbolic expression simplifier and the students determined it would not be easy to add one given the problems we have mentioned with GCC's IR. The Cetus API, however, made it possible to add a powerful expression simplifier with a modest effort. While it is not as powerful as the simplifiers provided by math packages, such as Maple, Matlab, or Mathematica, it does reduce the expressions to a canonical form and has been able to eliminate the redundancy in the expressions we have encountered in our experiments. Expression simplification enhances the readability of the compiler output and enables other optimizations because it transforms the program into a canonical form. For instance, idiom recognition and induction variable substitution benefited most from the expression simplifier. Recognition is easier because there are fewer complicated expressions to analyze and all expressions have a consistent structure. Substitution can create very long expressions that make later passes less effective unless it is immediately followed by simplification.

To use the expression simplifier, you first create a Simplifier object, then you call its run method on an expression. The Simplifier will not modify the original expression, and instead returns a new, simplified expression.

/* The following code prints 13. */

BinaryExpression a = new BinaryExpression(new IntegerLiteral(3), BinaryOperator.ADD, new IntegerLiteral(4));
BinaryExpression bexpr = new BinaryExpression(a, BinaryOperator.ADD, new IntegerLiteral(6));

(new Simplifier()).run(bexpr).print(System.out);

The Simplifier constructor has some parameters that determine how it should simplify the expression. From experience with the class project, we found that some passes require certain forms of simplification that are not appropriate for other passes. For example, some people are reluctant to simplify floating point expressions because they may no longer have the exact value of the original expression.

The different parameters to the Simplifier will be documented here after they are finalized.

A major complaint about early versions of Cetus was that the printing of IR was not flexible enough. To solve this problem, we have made printing completely customizable by the pass writer. Nearly all classes implement a Printable interface, which means they provide a print method for printing themselves as source code. By default, this print method calls a static method of the same class, called defaultPrint. The call is made by invoking a Java Method object, which is similar to a function pointer in C. The Method object can be changed by calling setPrintMethod and passing it a different printing routine. setPrintMethod allows a pass writer to change how one particular object prints itself. If the pass writer notices that they are calling this method frequently for the same type of object, then it may be easier to call setClassPrintMethod, a static method which causes all newly created objects of a particular class to use the provided printing routine.

Compiler functionality for supporting translation of OpenMP falls into two broad categories. The first category deals with the translation of the OpenMP work sharing constructs to the micro-tasking format. This entails the extraction of the work sharing code to separate microtasking subroutines and insertion of the corresponding function calls and synchronization. Cetus provides an API sufficient for these transformations. The second category deals with the translation of the data clauses, which requires support for accessing and modifying symbol table entries. Cetus provides several ways in which the pass writer can access the symbol table to add and delete symbols or change their scope.

There are currently two different OpenMP translators which have been implemented using Cetus. Both of these use the same OpenMP front end. One translator generates code for shared-memory systems using the POSIX threads API. The other translator targets software distributed shared memory systems and was developed as part of a project to extend OpenMP to cluster systems. Although the entire OpenMP 2.0 specification is not supported yet, the translators are powerful enough to handle benchmarks such as 330.art_m and 320.equake_m from the SPEC OMPM2001 suite.