This project develops compile time techniques and a software tool (called the Reduction Simplification Engine, RSE) for optimization of equational programs with reductions (associative, and usually commutative, operations applied to collections of data). By using these techniques and tools it is possible to generate programs with lower asymptotic complexity than the original specification. Such complexity reduction is an ambitious, almost unheard of, goal in compilation: most compilers seek constant factor gains, usually a few percentage points. The techniques developed in this project build on more than twenty years of research by the PI on a formalism called the "polyhedral model." The main novelty of the current effort is that in addition to polyhedral techniques, algebraic properties such as idempotency and distributivity are also used to augment the analyses performed.
