Simplifying dependent reductions using duality

Abstract

Programs often contain redundant computations, and frequently the onus is on the developer to detect these repeated computations and remove them. As an alternative to hand optimization, compilers can often be used to automatically optimize program inefficiencies. In this work, we discuss a compiler optimization that can automatically detect and remove certain types of redundant computation. Specifically, this thesis explores the problem of automatically simplifying dependent reductions in the polyhedral model. To simplify dependent reductions, we will use the mathematical concept of duality which allows us to view this problem through the lens of program dependences. Duality greatly simplifies our approach in comparison with prior work, and we will it to augment a preexisting simplifying reductions algorithm.