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

Wed Jan 17 00:22:04 PST 2018

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