Polynomial approximations in the polytope model: Bringing the power of quasi-polynomials to the masses

This paper addresses one issue in the polyhedral model of loop nests that limits its practical applicability. We present methods for avoiding the use of quasi-polynomials when enumerating integer points in polyhedra, by computing polynomial approximations of the quasi-polynomials and also polynomial upper and lower bounds of the quasi-polynomial. We propose two methods and different variants thereof. An evaluation on a set of systems of linear equalities generated by several compiler analyses shows that the accuracy of our more advanced method is similar to or better than the accuracy of existing techniques, while the computation is faster on difficult problems.status: publishe