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

Dear community,

for our goal to make polyhedral optimization available in the main
LLVM source, we will need the Integer Set Library (isl)[1]. It is the
main dependency of Polly, but would be required even if we do not
directly import Polly.

I already prepared a patch [2], unfortunately without feedback on the
general approach. As Philip suggested in the review, I am reaching out
with an RFC with a wider audience on llvm-dev.

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.

An alternative would be to only store the git sha1 and a CMake script
would download that version when building. However, it would also be
more difficult to both sources in-sync in the checkout (think of git
bisect).

I suppose these were also the reasons why Polly imported the isl
source in commit r228193 instead of requiring users to call
utils/checkout_isl.sh manually.


The other design decisions and rationales are mentioned in the review
summary [2]. I repeat them here so they can be referred to in replies.

* The library is named LLVMISL and contained in the lib/ISL folder to
work best with LLVM's component system. The component's name
"ISL" was
chosen over "isl" as it matches the capitalization of other
two/three-letter-acronym components.

* Isl's headers are installed into $PREFIX/include/llvm/ISL/isl. This
is to not conflict with potentially user/system-installed isl headers.
Please note that this means that MIT-licensed headers land on the
target system.

* The source of isl itself is added to the contrib/isl directory. This
is to keep the source in one directory rather than spreading it into
the lib and include directories, facilitating integration of upstream
changes. There is a script "isl-merge.py" that automates this. It
currently requires LLVM being checked out using git. The new subfolder
"contrib" should make it clear that this is downstream code and maybe
one shouldn't run clang-format over it which would make the next merge
difficult.

* There is an additional "GIT_HEAD_ID" file containing the
upstream's
revision. It is used by isl-merge.py to determine the common ancestor
and CMakeLists.txt to determine the version. Normally isl's make dist
would generate this file, it is done manually here to not requiring a
configure/make/make dist cycle when merging the latest isl. Due to
different Autotools versions being installed on the different systems,
this might lead to spurious conflicts with the generated configure
etc. files. However, due to the need of an isl-noexeceptions.h, I may
need to include such a cycle in isl-merge.py anyway.

* Isl has its own unittest "isl_test.c". It is put into bin/ (but not
installed) and run by llvm-lit on llvm-check. This was just the
simplest to do since it doesn't require any additional lit.site.cfg in
order to find the isl_test in a different directory.


Looking forward for your feedback.

Michael


[1] http://isl.gforge.inria.fr/
[2] https://reviews.llvm.org/D40122

On 01/15/2018 10:52 AM, Michael Kruse via llvm-dev
wrote:
> Dear community,
>
> for our goal to make polyhedral optimization available in the main
> LLVM source, we will need the Integer Set Library (isl)[1]. It is the
> main dependency of Polly, but would be required even if we do not
> directly import Polly.
>
> I already prepared a patch [2], unfortunately without feedback on the
> general approach. As Philip suggested in the review, I am reaching out
> with an RFC with a wider audience on llvm-dev.
If this is ready to be reviewed, I recommend removing the "[WIP]" from
the title. Normally I interpret "[WIP]" (which I presume stands for
"work in progress") as meaning "I'm looking for early
feedback on this
approach, perhaps primarily from a limited audience, but the patch
itself is not really ready for review (e.g., still known not to build,
to crash, miscompile, and so on).

What you have below sounds generally good to me (a couple of questions
below).
>
> 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.
>
> An alternative would be to only store the git sha1 and a CMake script
> would download that version when building. However, it would also be
> more difficult to both sources in-sync in the checkout (think of git
> bisect).
>
> I suppose these were also the reasons why Polly imported the isl
> source in commit r228193 instead of requiring users to call
> utils/checkout_isl.sh manually.
>
>
> The other design decisions and rationales are mentioned in the review
> summary [2]. I repeat them here so they can be referred to in replies.
>
> * The library is named LLVMISL and contained in the lib/ISL folder to
> work best with LLVM's component system. The component's name
"ISL" was
> chosen over "isl" as it matches the capitalization of other
> two/three-letter-acronym components.
>
> * Isl's headers are installed into $PREFIX/include/llvm/ISL/isl. This
> is to not conflict with potentially user/system-installed isl headers.
> Please note that this means that MIT-licensed headers land on the
> target system.
>
> * The source of isl itself is added to the contrib/isl directory. This
> is to keep the source in one directory rather than spreading it into
> the lib and include directories, facilitating integration of upstream
> changes.
>  There is a script "isl-merge.py" that automates this. It
> currently requires LLVM being checked out using git. The new subfolder
> "contrib" should make it clear that this is downstream code and
maybe
> one shouldn't run clang-format over it which would make the next merge
> difficult.
>
> * There is an additional "GIT_HEAD_ID" file containing the
upstream's
> revision. It is used by isl-merge.py to determine the common ancestor
> and CMakeLists.txt to determine the version. Normally isl's make dist
> would generate this file, it is done manually here to not requiring a
> configure/make/make dist cycle when merging the latest isl. Due to
> different Autotools versions being installed on the different systems,
> this might lead to spurious conflicts with the generated configure
> etc. files. However, due to the need of an isl-noexeceptions.h, I may
> need to include such a cycle in isl-merge.py anyway.
Can you clarify when/if autotools are required and under what circumstances.
>
> * Isl has its own unittest "isl_test.c". It is put into bin/ (but
not
> installed) and run by llvm-lit on llvm-check. This was just the
> simplest to do since it doesn't require any additional lit.site.cfg in
> order to find the isl_test in a different directory.
Can it end up in the unittests subdirectory with the other unit tests?

Thanks again,
Hal
>
>
> Looking forward for your feedback.
>
> Michael
>
>
> [1] http://isl.gforge.inria.fr/
> [2] https://reviews.llvm.org/D40122
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
-- 
Hal Finkel
Lead, Compiler Technology and Programming Languages
Leadership Computing Facility
Argonne National Laboratory

Thank you for the feedback.

2018-01-15 18:21 GMT+01:00 Hal Finkel <hfinkel at
anl.gov>:
> If this is ready to be reviewed, I recommend removing the "[WIP]"
from
> the title. Normally I interpret "[WIP]" (which I presume stands
for
> "work in progress") as meaning "I'm looking for early
feedback on this
> approach, perhaps primarily from a limited audience, but the patch
> itself is not really ready for review (e.g., still known not to build,
> to crash, miscompile, and so on).
Thanks for the hint, I did not think of this. The intention to keep
the flag was that I do not intend to commit it right away, but rather
to discuss the approach. Committing is only becomes necessary when
implementing something requiring it.

>> * There is an additional "GIT_HEAD_ID" file containing the
upstream's
>> revision. It is used by isl-merge.py to determine the common ancestor
>> and CMakeLists.txt to determine the version. Normally isl's make
dist
>> would generate this file, it is done manually here to not requiring a
>> configure/make/make dist cycle when merging the latest isl. Due to
>> different Autotools versions being installed on the different systems,
>> this might lead to spurious conflicts with the generated configure
>> etc. files. However, due to the need of an isl-noexeceptions.h, I may
>> need to include such a cycle in isl-merge.py anyway.
>
> Can you clarify when/if autotools are required and under what
circumstances.
Polly's update_isl.py runs it to generate the files GIT_HEAD_ID,
isl_config.h and isl-noexeceptions.h where only the GIT_HEAD_ID is
actually used.

GIT_HEAD_ID:
Polly) Use the one generated by autotools, run by update_isl.py
D40122) Generated by isl-merge.py

isl_config.h:
Polly) Generated by CMakeLists.txt
D40122) Generated by CMakeLists.txt

isl-noexeceptions.h:
Polly) Added manually to the repository. When an update is necessary,
the user has to configure/build isl and copy the generated
isl-noexeceptions.h into the repository
D40122) There is no isl-noexeceptions.h

Since sometime we will need isl-noexeceptions.h, here are the approaches:

using autotools) Like update_isl.py, run autotools by isl-merge.py and
copy the file generated into the repository.
without autotools) Run the commands that the autotools' build would
run by isl-merge.py

The latter might require maintenance if the way isl's build system
creates isl-noexeceptions.h changes.

autotools are required only in the former solution and only when
someone wants to merge a newer version of isl by running isl-merge.py.

>> * Isl has its own unittest "isl_test.c". It is put into bin/
(but not
>> installed) and run by llvm-lit on llvm-check. This was just the
>> simplest to do since it doesn't require any additional lit.site.cfg
in
>> order to find the isl_test in a different directory.
>
> Can it end up in the unittests subdirectory with the other unit tests?
The lit.cfg in test\Unit directory assumes that all tests are using
gtest. This is not the case for isl_test.

The unittests subdirectory only contains the sources of the unittests,
isl_test's sources are in contrib/isl/isl_test.c for the
external-source separating reason.

We could move the CMakeLists.txt to build isl_test into the unittest
dir, but for compiling, it requires some definitions from
lib/ISL/CMakeLists.txt (e.g. include paths) which are not available in
sibling build directories. One could move these definitions further up
into the root CMakeLists.txt or duplicate in unittests/ISL. IMHO, both
have more downsides than the advantage of having a unittest/ISL
directory.


Michael

Hi Micheal,

thanks for moving this forward!

2018-01-15 17:52 GMT+01:00 Michael Kruse via llvm-dev <
llvm-dev at lists.llvm.org>:
> Dear community,
>
> for our goal to make polyhedral optimization available in the main
> LLVM source, we will need the Integer Set Library (isl)[1]. It is the
> main dependency of Polly, but would be required even if we do not
> directly import Polly.
>
> I already prepared a patch [2], unfortunately without feedback on the
> general approach. As Philip suggested in the review, I am reaching out
> with an RFC with a wider audience on llvm-dev.
>
> 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.
>
> An alternative would be to only store the git sha1 and a CMake script
> would download that version when building. However, it would also be
> more difficult to both sources in-sync in the checkout (think of git
> bisect).
>
> I suppose these were also the reasons why Polly imported the isl
> source in commit r228193 instead of requiring users to call
> utils/checkout_isl.sh manually.
>
>
> The other design decisions and rationales are mentioned in the review
> summary [2]. I repeat them here so they can be referred to in replies.
>
> * The library is named LLVMISL and contained in the lib/ISL folder to
> work best with LLVM's component system. The component's name
"ISL" was
> chosen over "isl" as it matches the capitalization of other
> two/three-letter-acronym components.
>
> * Isl's headers are installed into $PREFIX/include/llvm/ISL/isl. This
> is to not conflict with potentially user/system-installed isl headers.
> Please note that this means that MIT-licensed headers land on the
> target system.
>
I think this needs to be emphasized. This means we effectively ship another
version of isl to our users, independent of whether they have one already.
Is this really what we want?

Cheers,
Philip

> * The source of isl itself is added to the contrib/isl directory. This
> is to keep the source in one directory rather than spreading it into
> the lib and include directories, facilitating integration of upstream
> changes. There is a script "isl-merge.py" that automates this. It
> currently requires LLVM being checked out using git. The new subfolder
> "contrib" should make it clear that this is downstream code and
maybe
> one shouldn't run clang-format over it which would make the next merge
> difficult.
>
> * There is an additional "GIT_HEAD_ID" file containing the
upstream's
> revision. It is used by isl-merge.py to determine the common ancestor
> and CMakeLists.txt to determine the version. Normally isl's make dist
> would generate this file, it is done manually here to not requiring a
> configure/make/make dist cycle when merging the latest isl. Due to
> different Autotools versions being installed on the different systems,
> this might lead to spurious conflicts with the generated configure
> etc. files. However, due to the need of an isl-noexeceptions.h, I may
> need to include such a cycle in isl-merge.py anyway.
>
> * Isl has its own unittest "isl_test.c". It is put into bin/ (but
not
> installed) and run by llvm-lit on llvm-check. This was just the
> simplest to do since it doesn't require any additional lit.site.cfg in
> order to find the isl_test in a different directory.
>
>
> Looking forward for your feedback.
>
> Michael
>
>
> [1] http://isl.gforge.inria.fr/
> [2] https://reviews.llvm.org/D40122
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20180115/e0b57145/attachment.html>

On Mon, Jan 15, 2018, at 22:10, Philip Pfaffe via llvm-dev
wrote:
> Hi Micheal,
> 
> thanks for moving this forward!
> 
> 2018-01-15 17:52 GMT+01:00 Michael Kruse via llvm-dev <
> llvm-dev at lists.llvm.org>:
> 
> > Dear community,
> >
> > for our goal to make polyhedral optimization available in the main
> > LLVM source, we will need the Integer Set Library (isl)[1]. It is the
> > main dependency of Polly, but would be required even if we do not
> > directly import Polly.
> >
> > I already prepared a patch [2], unfortunately without feedback on the
> > general approach. As Philip suggested in the review, I am reaching out
> > with an RFC with a wider audience on llvm-dev.
> >
> > 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.
> >
> > An alternative would be to only store the git sha1 and a CMake script
> > would download that version when building. However, it would also be
> > more difficult to both sources in-sync in the checkout (think of git
> > bisect).
> >
> > I suppose these were also the reasons why Polly imported the isl
> > source in commit r228193 instead of requiring users to call
> > utils/checkout_isl.sh manually.
> >
> >
> > The other design decisions and rationales are mentioned in the review
> > summary [2]. I repeat them here so they can be referred to in replies.
> >
> > * The library is named LLVMISL and contained in the lib/ISL folder to
> > work best with LLVM's component system. The component's name
"ISL" was
> > chosen over "isl" as it matches the capitalization of other
> > two/three-letter-acronym components.
> >
> > * Isl's headers are installed into $PREFIX/include/llvm/ISL/isl.
This
> > is to not conflict with potentially user/system-installed isl headers.
> > Please note that this means that MIT-licensed headers land on the
> > target system.
> >
> 
> I think this needs to be emphasized. This means we effectively ship another
> version of isl to our users, independent of whether they have one already.
> Is this really what we want?
Yes, I feel this is important for predicability and reproducability of test
cases. Even minor differences in isl version might result in differences in how
code is compiled. Without using a fixed version of isl for a given SVN id, it
will be more difficult to reproduce bug reports.

Do you see any drawback with this approach?

Best,
Tobias
> 
> Cheers,
> Philip
> 
> 
> > * The source of isl itself is added to the contrib/isl directory. This
> > is to keep the source in one directory rather than spreading it into
> > the lib and include directories, facilitating integration of upstream
> > changes. There is a script "isl-merge.py" that automates
this. It
> > currently requires LLVM being checked out using git. The new subfolder
> > "contrib" should make it clear that this is downstream code
and maybe
> > one shouldn't run clang-format over it which would make the next
merge
> > difficult.
> >
> > * There is an additional "GIT_HEAD_ID" file containing the
upstream's
> > revision. It is used by isl-merge.py to determine the common ancestor
> > and CMakeLists.txt to determine the version. Normally isl's make
dist
> > would generate this file, it is done manually here to not requiring a
> > configure/make/make dist cycle when merging the latest isl. Due to
> > different Autotools versions being installed on the different systems,
> > this might lead to spurious conflicts with the generated configure
> > etc. files. However, due to the need of an isl-noexeceptions.h, I may
> > need to include such a cycle in isl-merge.py anyway.
> >
> > * Isl has its own unittest "isl_test.c". It is put into bin/
(but not
> > installed) and run by llvm-lit on llvm-check. This was just the
> > simplest to do since it doesn't require any additional
lit.site.cfg in
> > order to find the isl_test in a different directory.
> >
> >
> > Looking forward for your feedback.
> >
> > Michael
> >
> >
> > [1] http://isl.gforge.inria.fr/
> > [2] https://reviews.llvm.org/D40122
> > _______________________________________________
> > LLVM Developers mailing list
> > llvm-dev at lists.llvm.org
> > http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
> >
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

On 01/15/2018 08:52 AM, Michael Kruse via llvm-dev
wrote:
> Dear community,
>
> for our goal to make polyhedral optimization available in the main
> LLVM source, we will need the Integer Set Library (isl)[1]. It is the
> main dependency of Polly, but would be required even if we do not
> directly import Polly.
>
> I already prepared a patch [2], unfortunately without feedback on the
> general approach. As Philip suggested in the review, I am reaching out
> with an RFC with a wider audience on llvm-dev.
>
> 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.
>
> An alternative would be to only store the git sha1 and a CMake script
> would download that version when building. However, it would also be
> more difficult to both sources in-sync in the checkout (think of git
> bisect).
>
> I suppose these were also the reasons why Polly imported the isl
> source in commit r228193 instead of requiring users to call
> utils/checkout_isl.sh manually.
>
>
> The other design decisions and rationales are mentioned in the review
> summary [2]. I repeat them here so they can be referred to in replies.
>
> * The library is named LLVMISL and contained in the lib/ISL folder to
> work best with LLVM's component system. The component's name
"ISL" was
> chosen over "isl" as it matches the capitalization of other
> two/three-letter-acronym components.
>
> * Isl's headers are installed into $PREFIX/include/llvm/ISL/isl. This
> is to not conflict with potentially user/system-installed isl headers.
> Please note that this means that MIT-licensed headers land on the
> target system.
This comment caught my eye.  Looking at ISL, it appears to offer a MIT 
license only.  How does this interact with LLVM's licensing? There does 
appear to be some precedent for third party libraries under different 
licenses, but this needs careful discussion and review by a 
knowledgeable party.  (I am not one.)
>
> * The source of isl itself is added to the contrib/isl directory. This
> is to keep the source in one directory rather than spreading it into
> the lib and include directories, facilitating integration of upstream
> changes. There is a script "isl-merge.py" that automates this. It
> currently requires LLVM being checked out using git. The new subfolder
> "contrib" should make it clear that this is downstream code and
maybe
> one shouldn't run clang-format over it which would make the next merge
> difficult.
>
> * There is an additional "GIT_HEAD_ID" file containing the
upstream's
> revision. It is used by isl-merge.py to determine the common ancestor
> and CMakeLists.txt to determine the version. Normally isl's make dist
> would generate this file, it is done manually here to not requiring a
> configure/make/make dist cycle when merging the latest isl. Due to
> different Autotools versions being installed on the different systems,
> this might lead to spurious conflicts with the generated configure
> etc. files. However, due to the need of an isl-noexeceptions.h, I may
> need to include such a cycle in isl-merge.py anyway.
>
> * Isl has its own unittest "isl_test.c". It is put into bin/ (but
not
> installed) and run by llvm-lit on llvm-check. This was just the
> simplest to do since it doesn't require any additional lit.site.cfg in
> order to find the isl_test in a different directory.
>
>
> Looking forward for your feedback.
>
> Michael
>
>
> [1] http://isl.gforge.inria.fr/
> [2] https://reviews.llvm.org/D40122
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

> 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,

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’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.  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.

How much of ISL are you using?  What other options have you considered?  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?

-Chris

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 01:41, Philip Reames via llvm-dev
wrote:
> 
> 
> On 01/15/2018 08:52 AM, Michael Kruse via llvm-dev wrote:
> > Dear community,
> >
> > for our goal to make polyhedral optimization available in the main
> > LLVM source, we will need the Integer Set Library (isl)[1]. It is the
> > main dependency of Polly, but would be required even if we do not
> > directly import Polly.
> >
> > I already prepared a patch [2], unfortunately without feedback on the
> > general approach. As Philip suggested in the review, I am reaching out
> > with an RFC with a wider audience on llvm-dev.
> >
> > 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.
> >
> > An alternative would be to only store the git sha1 and a CMake script
> > would download that version when building. However, it would also be
> > more difficult to both sources in-sync in the checkout (think of git
> > bisect).
> >
> > I suppose these were also the reasons why Polly imported the isl
> > source in commit r228193 instead of requiring users to call
> > utils/checkout_isl.sh manually.
> >
> >
> > The other design decisions and rationales are mentioned in the review
> > summary [2]. I repeat them here so they can be referred to in replies.
> >
> > * The library is named LLVMISL and contained in the lib/ISL folder to
> > work best with LLVM's component system. The component's name
"ISL" was
> > chosen over "isl" as it matches the capitalization of other
> > two/three-letter-acronym components.
> >
> > * Isl's headers are installed into $PREFIX/include/llvm/ISL/isl.
This
> > is to not conflict with potentially user/system-installed isl headers.
> > Please note that this means that MIT-licensed headers land on the
> > target system.
> This comment caught my eye.  Looking at ISL, it appears to offer a MIT 
> license only.  How does this interact with LLVM's licensing? There does
> appear to be some precedent for third party libraries under different 
> licenses, but this needs careful discussion and review by a 
> knowledgeable party.  (I am not one.)
We changed the license of isl to MIT following the recommendation of Chris
Lattner. a while ago. Hal Finkel recently re-checked the license situation. It
seems to be fine for now. If at some point this is becoming a blocker, we could
theoretically consider re-licensing once more (or alternatively rewrite parts of
isl with the knowledge we gained from using it).

Best,
Tobias

Hi Chris,

thanks for your feedback. I have some additions to what Tobias already
mentioned.

2018-01-17 7:22 GMT+01:00 Chris Lattner <clattner at
nondot.org>:
> 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’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.
isl has three arbitrary-length integer backends: gmp, imath
(https://github.com/creachadair/imath, MIT licensed), imath32 (32 bit
integer, falls back to imath on overflow).

The imath support has been added because of the licensing issue when
included into Polly.
> 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.
The imath32 backend was written because of this. We are constantly
improving the performance.
> Why should this be included with every LLVM distribution instead of being
conditionally compiled?
The patch https://reviews.llvm.org/D40122 compiles isl conditionally
(LLVM_INCLUDE_ISL, off by default).
>  If the major issue is the polly regression tests, why not fix the tests?
The regression tests verify that the LLVM IR is correctly represented
in isl (affine expressions, iteration domains, dependencies, etc),
which in turn depends on isl's string output. The only way I see to
avoid this issue is to not check those at all. Only (input IR ->
generated IR) tests remain. It is like testing ScalarEvolution without
being able to dump an llvm::SCEV.


Michael

On Mon, Jan 15, 2018 at 05:52:02PM +0100, Michael Kruse via llvm-dev
wrote:
> * The library is named LLVMISL and contained in the lib/ISL folder to
> work best with LLVM's component system. The component's name
"ISL" was
> chosen over "isl" as it matches the capitalization of other
> two/three-letter-acronym components.
Are the ISL sources themselve put into a namespace under llvm? That's my
primary concern: a program wanting to use a random ISL version and LLVM
at the same time.

Joerg

2018-01-19 15:56 GMT+01:00 Joerg Sonnenberger via llvm-dev <
llvm-dev at lists.llvm.org>:
> On Mon, Jan 15, 2018 at 05:52:02PM +0100, Michael Kruse via llvm-dev wrote:
> > * The library is named LLVMISL and contained in the lib/ISL folder to
> > work best with LLVM's component system. The component's name
"ISL" was
> > chosen over "isl" as it matches the capitalization of other
> > two/three-letter-acronym components.
>
> Are the ISL sources themselve put into a namespace under llvm? That's
my
> primary concern: a program wanting to use a random ISL version and LLVM
> at the same time.
>
This is my primary concern as well, and the point I tried to raise in my
email before. They currently are not. If we did import isl into an llvm
namespace, that'd mean we'd have to modify the isl source upon every
update
(which is certainly scriptable, but still tedious and likely hard to
maintain, I believe).

Cheers,
Philip

>
> Joerg
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20180119/0e7e0651/attachment.html>

2018-01-19 15:56 GMT+01:00 Joerg Sonnenberger via llvm-dev
<llvm-dev at lists.llvm.org>:
> On Mon, Jan 15, 2018 at 05:52:02PM +0100, Michael Kruse via llvm-dev wrote:
>> * The library is named LLVMISL and contained in the lib/ISL folder to
>> work best with LLVM's component system. The component's name
"ISL" was
>> chosen over "isl" as it matches the capitalization of other
>> two/three-letter-acronym components.
>
> Are the ISL sources themselve put into a namespace under llvm? That's
my
> primary concern: a program wanting to use a random ISL version and LLVM
> at the same time.
No, isl and its headers are written in plain C and we do not modify
its sources to put symbols into namespaces (and compile as C++
sources).

We actually had this occurring with Draggonegg: isl would be used by
both LLVM/Polly and GCC/Graphite and loaded into the same address
space. We solved this by hiding the isl symbols with
-fvisibility=hidden. We do not do this anymore because it makes
BUILD_SHARED_LIBS=ON/OFF behave differently, and Draggenegg being
de-facto deprecated.

Since isl includes imath, it uses a different approach: The file
"wrap.h" #defines every imath symbol with an "isl_" prefix,
e.g.
#define impq_cmp isl_impq_cmp

We could modify the source and append/prepend namespaces around the
C-sources. The isl-merge.py script would merge them into upstream
sources and only conflict when the start/end of the file is changed
upstream, and then easy to resolve. Or one compiles such as
isl_ctx.cpp:

namspace llvm {
#include "isl_ctx.c"
}

The isl source are currently not C++-friendly because of implicit
casts from void*, but this can be upstreamed to isl. We might even try
upstream a preprocessor definition to optional use namespaces:

#ifdef ISL_NAMESSPACE
namespace ISL_NAMESSPACE {
#endif

What I want to say, if this should be a major issue, there are solutions for it.

Michael

> On Jan 19, 2018, at 6:56 AM, Joerg Sonnenberger via llvm-dev <llvm-dev
at lists.llvm.org> wrote:
> 
> On Mon, Jan 15, 2018 at 05:52:02PM +0100, Michael Kruse via llvm-dev wrote:
>> * The library is named LLVMISL and contained in the lib/ISL folder to
>> work best with LLVM's component system. The component's name
"ISL" was
>> chosen over "isl" as it matches the capitalization of other
>> two/three-letter-acronym components.
> 
> Are the ISL sources themselve put into a namespace under llvm? That's
my
> primary concern: a program wanting to use a random ISL version and LLVM
> at the same time.
Yes, this can be a very significant problem.  Many highly layered software
systems (e.g. TensorFlow) end up with LLVM as a dependency (e.g. through XLA). 
Making ISL a non-encapsulated dependency that LLVM is version locked with will
be a significant problem if any of the other layers need to use ISL, because
they will be version locked to the same revision even if they themselves don’t
depend on LLVM...

-Chris