Deriving Formulae to Count Solutions to Parameterized Linear Systems using Ehrhart Polynomials: Applications to the Analysis of Nested-Loop Programs

Optimizing parallel compilers need to be able to analyze nested loop programs with parametric affine loop bounds, in order to derive efficient parallel programs. The iteration spaces of nested loop programs can be modeled by polyhedra and systems of linear constraints. Using this model, important program analyses such as computing the number of flops executed by a loop, computing the number of memory locations or cache lines touched by a loop, and computing the amount of processor to processor communication needed during the execution of a loop -- all reduce to the same mathematical problem: finding the formula for number of integer solutions to a system of parameterized linear constraints, as a function of the parameters. In this paper, we present a method for deriving a closed-form symbolic formula for the number of integer points contained in a polyhedral region in terms of size parameters. If the set of integer points to be counted lies inside a union of rational convex polytopes, ..