Infrastructure Enhancements

The Polairs compiler supports the majority of analyses needed to implement our transformations. However, in some cases we found it useful to extend or enhance some of the Polaris infrastructure. For example, the internal representation of a program in Polaris is flat; we found it convenient to add a hierarchical representation of statements. Similarly, Polaris represents only dependence direction, we added distance representation.

Dependence Distance Representation

The internal representation of dependence information in Polaris is currently restricted to dependence directions only. In order to support enhancements such as a library of unimodular transformations, it was necessary to introduce dependence distance information. This was achieved by modifying the internal representation of the Polaris arc_type data structure. This data structure is illustrated in the figure below, with the changes highlighted in red. The new fields for each dependence vector element allow the representation of distances in the range of [-127..127].

The Hierarchical Program Graph

Polaris uses a flat representation of the statements in source programs, where each statement has links to its textual predecessor and textual successor. When analyzing source code to identify and transform structures such as nested loops, a hierarchical program representation is often more convenient. The hierarchical program graph is an enhancement to the Polaris infrastructure which enables representation and traversal of structured constructs such as loops, conditional statements, and subroutine invocations. An example program graph is shown in the figure below.

Unimodular Transformations Library

The unimodular loop transformations of permutation, reversal, and skewing (shown below) may be combined together to form arbitrary compound transformations. A support library for unimodular transformations has been developed as an enhancement to the Polaris infrastructure to enable the representation of compound transformations. This library accepts as input a matrix representation of the desired compound transformation, a pointer to the loop nest to be transformed, and the set of dependence vectors for the loop nest. The library verifies the legality of the transformation using the set of dependence vectors, and if the transformation is legal, proceeds to transform both the dependence vectors and the code.