Finding Legal Reordering Transformations using Mappings
Finding Legal Reordering Transformations using Mappings
Files
Publication or External Link
Date
1998-10-15
Authors
Kelly, Wayne
Pugh, William
Advisor
Citation
DRUM DOI
Abstract
Traditionally, optimizing compilers attempt to improve the performance of
programs by applying source to source transformations, such as loop
interchange, loop skewing and loop distribution. Each of these
transformations has its own special legality checks and transformation rules
which make it hard to analyze or predict the effects of compositions of
these transformations. To overcome these problems we have developed a
framework for unifying iteration reordering transformations. The framework
is based on the idea that all reordering transformation can be represented
as a mapping from the original iteration space to a new iteration space.
The framework is designed to provide a uniform way to represent and reason
about transformations. 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 an implicit
search tree.
(Also cross-referenced as UMIACS-TR-94-71)