A Hierarchical Basis for Reordering Transformations

Abstract

In this paper, we propose a new dependence baaed program representation.This representation is the union of two previously separate concepts: loop carried dependence and hierarchical abstraction.The resulting form has the property that all information necessary to reorder the set of all executions of the statements contained in a given loop exists in the representation of that loop.Thus, this representation provides an ideal basis for reordering transformations such as vectorisation and loop fusion.As evidence of this, we give efficient algorithms for these two transformations based on this representation.