llvm dev - Jan 2018 - RFC: Import of Integer Set Library into LLVM source tree

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

On Wed, Jan 17, 2018, at 09:14, Tobias Grosser via llvm-dev
wrote:
> 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.
Also, one more data-point. We currently ship isl + Polly with the standard LLVM
releases, as well as the debian + ubuntu package builds. Hence, this path is
well tested.

Best,
Tobias
> 
> Best,
> Tobias
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

> On Jan 17, 2018, at 12:14 AM, Tobias Grosser <tobias.grosser at
inf.ethz.ch> wrote:
>> 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.
Great, I think that that would be a fine approach: you can have the cmake logic
detect which version of isl is installed and fail if it is the wrong version. 
This would address my concern.
>> What other options have you considered?  
> 
> There are no other license compatible alternatives for the full set of
functionalities we are using.
I’m not familiar with this technology or how much of it you’re using, but… how
much code is this really?  Have you considered designing a from scratch
implementation in the LLVM style?  This would presumably be much more efficient,
it would be something you could control, and you’d be able to focus it on a
specific requirement.
>> 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.
Right, but I understand that you’re interested in getting polly integrated with
LLVM (something I don’t yet fully understand the implications of).  That is a
very different situation than including ISL in Polly when Polly is out of tree.

The motivation explained in the original email seemed to hinge around the fact
that Polly’s unit tests depend on accidental details of ISL that change across
releases.  If you can fix that, then it seems more plausible to unbundle it.

If you can’t fix that, and can’t replace ISL, then the best approach seems to
have CMake detect and reject incompatible versions.

-Chris

2018-01-18 6:40 GMT+01:00 Chris Lattner <clattner at
nondot.org>:
> Great, I think that that would be a fine approach: you can have the cmake
logic detect which version of isl is installed and fail if it is the wrong
version.  This would address my concern.
> The motivation explained in the original email seemed to hinge around the
fact that Polly’s unit tests depend on accidental details of ISL that change
across releases.  If you can fix that, then it seems more plausible to unbundle
it.
>
> If you can’t fix that, and can’t replace ISL, then the best approach seems
to have CMake detect and reject incompatible versions.
This would require buildbot admins to regularly install new versions of isl.

Isl implements the main loop optimization algorithms, so any change in
isl may potentially change Polly's output. This is not accidental but
intended, to profit from improvements in isl's loop optimization
algorithms. With the side-effect of input/output pairs (unit tests) to
be version-locked to a specific version of isl.

Isl currently has 177052 lines in source files. We thought about
writing a C++ implementation of it, but then again it would take
years, introduce new bugs and split the isl community.

Michael