ON THE REMOVAL OF ANTI-DEPENDENCES AND OUTPUT-DEPENDENCES

In this paper we build upon results of Padua and Wolfe,((1)) who intro duced two graph transformations to break dependence paths including an ti- and output-dependences. We first formalize these two transformatio ns. Then, given a loop nest, we aim at determining which statements sh ould be transformed so as to break artificial dependence paths involvi ng anti-or output-dependences. The problem of finding the minimum numb er of statements to be transformed is shown to be NP-complete, and we propose two efficient heuristics.