next up previous contents
Next: 6.7 Avoiding copy overhead Up: 6 Creating New Relations Previous: 6.5 Relational functions that

6.6 Generating code from relations

The library provides code generation functions that can produce loop nests for a set of statements, each with its own iteration space. The algorithm allows the union of these iteration spaces to be non-convex, and performs optimizations to reduce the level of overhead caused by iterating over a non-convex region. Since the overhead-reduction process increases code size, the user may specify how much overhead is to be removed. The algorithm is described elsewhere [KPR95].

To use the following functions, include the file code_gen/code_gen.h in your program.

These two functions return a string containing C pseudo-code:

The interface to the function uses several Tuple s, with the first position in each tuple for the first statement, the second position in each for the second statement, and so on. For each statement, you must provide:

The transformation is an affine, 1-1 mapping from points in the statement's original iteration space to the new iteration space. The output arity of the transformation relations is the dimensionality of the resulting iteration space, and all transformations must have the same output arity. The input arity of each transformation must be the same as the number of set variables in the corresponding iteration space. If no transformation is desired, specify the identity relation for the transformation.

If symbolic constants are used in the iteration spaces, you can provide any information you have about their values in the set known . It must have the same number of set variables as the dimensions of the resulting iteration space. This information can allow us to generate simpler code.

The algorithm can use different levels of effort to remove control overhead, at the cost of code duplication. The effort

parameter is an integer that specifies that all avoidable control overhead should be removed from effort + 1 inner loops. By default, overhead is removed from the innermost loop (effort of 0). For a five dimensional iteration space, an effort level of 1 says that there should be no overheads nested inside four loops; an effort level of 2 means no overheads at nesting level 3 or greater; and so on. An effort of -1 means omit all overhead removal.

To specify names for the statements, you should create a class derived from class naming_info , and pass into the code generation routines a Tuple of pointers to that class. The class needs to provide the following functions:

naming_info()
A default constructor.
virtual naming_info& operator=(const naming_info &n2)
The assignment operator.
virtual String name(Relation *current_map)
The function to provide a String representation of a statement, given the current arguments. See below for a full description.
virtual String debug_name()
A String to represent the statement in debugging output.
virtual char * debug_char_name()
A char* to represent the statement in debugging output. (This is necessary because of the lifetime of temporaries in C++; in a statement like printf("%s",(char *) n->name()) , the cast to char* is considered a use of the temporary String , which is then deleted.)
virtual String declaration()
Returns a String representation of the C declarations for the statement, if any are required. This is currently unused.

The Relation *current_map argument to the naming_info::name

function is a mapping from the index variables of the generated loops to the corresponding original index variables. The new index variables have a different iteration space than any of the original statements, called the ``transformed iteration space''; thus the current_map relation maps an iteration in the transformed iteration space to an iteration in the statement's original iteration space. Calling the function Relation::print_outputs_with_subs_to_string() on current_map will return a comma-delimited list of expressions for calculating the original iteration.



next up previous contents
Next: 6.7 Avoiding copy overhead Up: 6 Creating New Relations Previous: 6.5 Relational functions that



omega@cs.umd.edu