[llvm-dev] RFC: Import of Integer Set Library into LLVM source tree

[Tobias Grosser via llvm-dev]

On Wed, Jan 17, 2018, at 07:22, Chris Lattner via llvm-dev wrote:
> > On Jan 15, 2018, at 8:52 AM, Michael Kruse via llvm-dev <llvm-dev at lists.llvm.org> wrote:
> > As for the main motivation on why to import the entire source of isl at all:
> > Polly interacts relative tightly with isl which provide the main
> > optimization algorithms. For instance, Polly's regression tests
> > compare the string output of set representation, which unfortunately
> > can change between versions. For instance, if a newer version
> > implements a simpler string description of the same set. That means
> > that tests would fail if a different version is installed on the host
> > system. This is significant for buildbots that would need regular
> > manual action to install a newer version of isl on the system.
> 
> Hi Michael,

Hi Chris,

thank you for your feedback and especially for raising these concerns. We talked with different members of the community and share parts of your concerns.

> I have significant concerns about including ISL into LLVM.  LLVM 
> intentionally takes a very conservative approach to bundling third party 
> code with itself: we prefer instead of have them be external 
> dependencies that are conditionally configured in on demand.

I understand. If needed we can make the compilation of isl optional.

However, as pointed out earlier in this thread it seems preferable to lock LLVM with a very specific version of isl to make sure version differences don't cause spurious bugs. This at least has shown to be very useful in Polly.

> I’m not an expert in ISL in particular, but it looks like it is 
> something of an odd dependency to include: it isn’t structured at all 
> like LLVM, and it (apparently, I could definitely be wrong) depends on 
> the GMP library which is LGPL. 

It can optionally be compiled with GMP, however especially for the use in LLVM we added together with Qualcomm an MIT licensed imath backend (and tuned its performance).

> Beyond licensing, it has an old-school 
> C-style API which appears to be extremely inefficient compared to things 
> like APInt that avoid allocations for 64-bit integers and less.

Over the last year we developed C++ bindings for isl which make its use a lot easier:

https://github.com/llvm-mirror/polly/blob/master/lib/External/isl/include/isl/isl-noexceptions.h

While this does not reduce heap allocations, it will make it easier to replace performance critical parts of isl over time. While we don't have concrete plans to rewrite core parts of isl, I expect over time more and more of isl-style functionality to be incorporated natively in LLVM.

I expect that we could likely reduce heap allocations further, but some of the low-hanging fruits have already been picked. We avoid allocations of GMP/imath data structures all together for cases where integers are smaller than 32 bit. Most critical performance improvements today come from algorithmic improvements. 

Having an implementation that serves as baseline when considering to replacing parts of isl seems to be a good idea.

> How much of ISL are you using?

We currently use the (parameteric) integer programming solver,  the integer constraint library, the constraint to AST code generator, the ILP based scheduler, ...

> What other options have you considered?  

There are no other license compatible alternatives for the full set of functionalities we are using.

Alternatives for the constraint library part are PPL (which does not provide integer constraints), as well as omega (which served as inspiration for isl, but is today mostly unmaintained). Omega is to my knowledge used in compilers such as icc.

Alternatives for the code generation part are ClooG and codegen+. Both are older, provide less functionality, have license issues, and are C based.

Alternatives for the scheduler are Pluto(+) (which is license incompatible).

There are many alternatives for the LP solver. I did not do an extensive search here.

> Why should this be included with every LLVM distribution instead of 
> being conditionally compiled?  If the major issue is the polly 
> regression tests, why not fix the tests?

We currently don't have any issue. isl is today shipped as part of the Polly repository.

As Polly matured over time, all license issues have been resolved, we want to better integrate Polly also with the new pass manager, and alternative uses of parts of isl arose, we propose (see other thread) to move Polly into the LLVM core repository. This would allow also for a  closer integration of polyhedral operations with parts of LLVM. This patch focuses on where/how to integrate isl.

Best,
Tobias