Title: Integer set coalescing for polyhedral compilation
Authors: Verdoolaege, Sven # ×
Issue Date: 21-Oct-2014
Conference: Mini-workshop on polyhedral compilation and domain-specific computing date:21 October 2014
Abstract: 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.
Publication status: published
KU Leuven publication type: IMa
Appears in Collections:Informatics Section
× corresponding author
# (joint) last author

Files in This Item:
File Description Status SizeFormat
slides.pdf Published 576KbAdobe PDFView/Open


All items in Lirias are protected by copyright, with all rights reserved.