UNIMODULAR TRANSFORMATIONS OF NON-PERFECTLY NESTED LOOPS

A framework is described in which a class of imperfectly nested loops can be restructured using unimodular transformations. In this framewor k, an imperfect loop nest is converted to a perfect loop nest using Ab u-Sufah's Non-Basic-to-Basic-Loop transformation. Conditions for the l egality of this transformation and techniques for their verification a re discussed. An iteration space, which extends the usual concept so a s to represent explicitly the executions of individual statements, is proposed to model the converted loop nest. Since the converted loop ne st is a perfect loop nest, data dependences can be extracted and optim al transformations can be selected for parallelism and/or locality in the normal manner. To generate the restructured code for a unimodular transformation, a code generation method is provided that produces the restructured code that is free of if statements by construction.