Splitting Polyhedra to Generate More Efficient Code: Efficient Code Generation in the Polyhedral Model is Harder Than We Thought

International audienceCode generation in the polyhedral model takes as inputa union of Z-polyhedra and produces code scanning all ofthem. Modern code generation tools are heavily relying onpolyhedral operations to perform this task. However, theseoperations are typically provided by general-purpose poly-hedral libraries that are not specifically designed to addressthe code generation problem. In particular, (unions of) poly-hedra may be represented in various mathematically equiv-alent ways which may have different properties with respectto code generation. In this paper, we investigate this prob-lem and try to find the best representation of polyhedra togenerate efficient code.We present two contributions. First we demonstrate thatthis problem has been largely under-estimated, showing sig-nificant control overhead deviations when using differentrepresentations of the same polyhedra. Second, we proposean improvement to the main algorithm of the state-of-the-artcode generation tool CLooG. It generates code with fewertests in the inner loops, and aims to reduce control overheadand to simplify vectorization for the compiler, at the cost ofa larger code size. It is based on a smart splitting of theunion of polyhedra while recursing on the dimensions. Weimplemented our algorithm in CLooG/PolyLib, and com-pared the performance and size of the generated code to theCLooG/isl version