Valid Transformations: A New Class of Loop Transformations

In this paper we present a new class of loop optimizing transformations called valid transformations. This class of transformations are different from existing ones in that valid transformations can be illegal and can result in incorrect non-pipelined designs. Nevertheless, valid transformations have feasible pipeline schedules which is important for scheduling loops. We present an example valid transformation called loop expansion which can help explore a larger design space and helps in producing cost-performance efficient designs. Several examples are used to demonstrate the efficacy of the proposed transformations.