Integer Set Library (ISL) – A Primer
10 days ago
- #polyhedral-model
- #compiler-optimization
- #integer-set-library
- Polyhedral optimization is a tool used in compilers for optimizing loop nests.
- The Integer Set Library (ISL) is an open-source C library implementing core algorithms for polyhedral optimization.
- ISL represents integer points indirectly via quasi-affine formulas, which are systems of equalities and inequalities.
- Polyhedral optimization constructs integer sets corresponding to loop iteration spaces, mapping each loop execution to a point in the set.
- Quasi-affine formulas support operations like addition, multiplication by constants, floor/ceiling division, and modulus.
- Presburger formulas extend quasi-affine expressions with logical operators and quantifiers.
- ISL supports different types of sets and maps, including basic sets, union sets, and relations (maps).
- ISL can generate C code that iterates over points in a Presburger set, with control over iteration order.
- The ISL C API is extensive, with functions for manipulating sets, maps, and relations, including composition and domain extraction.
- MLIR's Fast Presburger Library (FPL) is a partial port of ISL, with an interoperability layer enabling conversion between ISL and FPL representations.