Integer set coalescing for polyhedral compilation

Polyhedral compilation is widely used in high-level synthesis tools and in production compilers such as gcc, LLVM and IBM/XL. It is based on the polyhedral model, a powerful abstraction for analyzing and transforming (parts of) programs that are ``sufficiently regular''. The key feature of this model is that it is instance based, allowing for a representation and treatment of individual dynamic executions of a statement inside a loop nest and/or individual array elements. These individual elements are represented by tuples of integers which are collected in sets and relations described by affine constraints. Polyhedral compilation then mainly consists of an analysis and transformation of these sets and relations. There are typically many ways to describe the same set of integer tuples using affine constraints. Most operations that can be performed on these sets do not depend on which particular representation is used, in the sense that only the time required for the computation is affected by this choice but not the value of the result. There are however some operations where this choice can have a significant impact, notably the computation of (overapproximations of) transitive closures and the construction of an AST for visiting each point in a set. Assuming a representation in disjunctive normal form, it is in all cases important to keep the number of disjuncts as small as possible. Excess disjuncts may result from operations such as subtraction, lexicographic optimization and integer projection. Set coalescing tries to combine several disjuncts into a single disjunct without affecting the elements in the set. We describe several cases where coalescing can be applied.status: publishe