Purpose

  The target generation module constructs the parse tree of the transformed source program. It takes the index spaces, schedule and allocation to build transformation matrices for every statement in the source program. Since the generated parse tree does not contain any synchronization or communication statements this module should be called ``raw target generator''.

This process takes place in three steps. First, all required information is loaded. Second, the source statements are transformed individually. In order to achieve that, the transformation matrices are computed, the target index spaces are constructed, strides and offsets are calculated, and finally all expressions in every statement are re-indexed according to its transformed coordinates. Third, the transformed statements in their respective index spaces (parts) are merged to a single target program. Aside from the two options of synchronous or asynchronous code, three merging strategies are available (see [Wet95] for details):

1. The parts are simply combined with a parallel operator, i.e., there are several separate loop nests which are assumed to be executed in parallel.  
2. All index spaces of the parts are merged to one index space to construct a perfect loop nest. The statements inside the body are guarded by ifs to determine at run time whether or not they are to be executed. This is the run time solution.  
3. To avoid ifs at run time, one determines at compile time precisely in which regions which statements must be executed, and enumerates these regions successively. This is only implemented for the outermost dimension, the others are merged by the run time method. Problem: for n parameters in the loop bounds, an O(n!) case distinction in the target program is necessary to determine their relative order.