Finding Legal Reordering Transformations using Mappings

TitleFinding Legal Reordering Transformations using Mappings
Publication TypeConference Papers
Year of Publication1995
AuthorsPugh W, Kelly W
Conference NameLanguages and compilers for parallel computing: 7th International Workshop, Ithaca, NY, USA, August 8-10, 1994: proceedings
Date Published1995///

We present a unified framework for applying iteration reordering transformations. This framework is able to represent traditional transformations such as loop interchange, loop skewing and loop distribution as well as compositions of these transformations. Using a unified framework rather than a sequence of adhoc transformations makes it easier to analyze and predict the effects of these transformations. Our framework is based on the idea that all reordering transformations can be represented as a mapping from the original iteration space to a new iteration space. An optimizing compiler would use our framework by finding a mapping that both corresponds to a legal transformation and produces efficient code. We present the mapping selection problem as a search problem by decomposing it into a sequence of smaller choices. We then characterize the set of all legal mappings by defining a search tree.