A framework for enhancing data reuse via associative reordering

The freedom to reorder computations involving associative operators has been widely recognized and exploited in designing parallel algo-rithms and to a more limited extent in optimizing compilers. In this paper, we develop a novel framework utilizing the associa-tivity and commutativity of operations in regular loop computations to enhance register reuse. Stencils represent a particular class of im-portant computations where the optimization framework can be ap-plied to enhance performance. We show how stencil operations can be implemented to better exploit register reuse and reduce load/stores. We develop a multi-dimensional retiming formalism to characterize the space of valid implementations in conjunction with other program transformations. Experimental results demonstrate the effectiveness of the framework on a collection of high-order stencils. 1