An integer set library for program analysis

Many program analysis techniques are based on manipulations of sets of integers bounded by linear constraints. These integers typically represent iterations of a loop nest or elements of an array. Double description based libraries are sometimes used for representing such sets, but these libraries usually have little or no explicit support for parameters and existentially quantified variables, which are essential for some program analysis tasks, and focus on rationals instead of integers. Furthermore, in our applications, the number of constraints describing a set is usually fairly small, while a vertex based description could be very large. We present a new library exclusively based on constraints and geared towards the manipulation of integer sets. The library supports some operations not typically available in other libraries, such as parametric integer linear programming and the computation of the integer affine hull, and produces significantly improved results in some applications.status: publishe