USING AFFINE CLOSURE TO FIND LEGAL REORDERING TRANSFORMATIONS

We present a unified framework for applying iteration reordering trans formations. This framework is able to represent traditional transforma tions such as loop interchange, loop skewing and loop distribution as well as compositions of these transformations. Using a unified framewo rk rather than a sequence of ad-hoc transformations makes it, easier t o analyze and predict the effects of these transformations. Our framew ork is based on the idea that all reordering transformations can be re presented as a mapping from the original iteration space to a new iter ation space. An optimizing compiler would use our framework by finding a mapping that both corresponds to a legal transformation and produce s 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. As part of this process we use a new operation called affine closure.