llvm dev - Jan 2018 - Inclusion of Polly and isl into core LLVM

[add subject]

Dear LLVM community,

hope all of you had a good start into 2018 and a quiet branching of LLVM 6.0.

With the latest LLVM release out of the way and a longer development phase
starting, we would like to restart the process of including Polly and isl into
core LLVM to bring changes in early on before the next LLVM release.

Short summary:

 * Today Polly is already part of each LLVM release (and will be shipping with
LLVM 6.0) for everybody to try, with conservative defaults.
 * We proposed to include Polly and isl into LLVM to provide modern high-level
loop optimizations into LLVM
 * We suggested to develop Polly and isl as part of core LLVM to make
interactions with the core LLVM community easier and to allow us to better
integrate Polly with the new pass manager.

Let me briefly summarize the current status:

 * Michael sent out an official email to discuss how to best include isl into
LLVM
(http://lists.llvm.org/pipermail/llvm-dev/2018-January/120408.html)
 * We sent out the LLVM developers meeting notes
(_http://lists.llvm.org/pipermail/llvm-dev/2018-January/120419.html_)
 * Philip Pfaffe prepared a preliminary patch set for integrating Polly closer
into LLVM:
   
_https://github.com/pfaffe/llvm-project-20170507/commits/merge-polly-into-upstream_
  (further cleanup needed)
 * We are working further with ARM (Florian Hahn and Francesco) to upstream the
inliner changes needed for the end-to-end optimization of SPEC 2006
libquantum.   _https://reviews.llvm.org/D38585_
 * Oleksandr, Sven and Manasij Mukherjee started to look into spatial locality
 * We worked on expanding the isl C++ bindings
(_http://repo.or.cz/isl.git/shortlog_). While a first set of patches is already
open, further patches will follow over the next couple of weeks.

Let me briefly summarize the LLVM developer meeting comments on our proposal
(subjective summary)

 * Most people were interested in having polyhedral loop optimizations being
part of LLVM.
 * Ideas of uses of isl beyond polyhedral loop scheduling were raised (e.g., for
polyhedral value analysis, dependence analysis, or broader assumption tracking).
Others were interested in the use of polyhedral loop optimization with “learned”
scheduling strategies.
 * Specific concerns were raised that an integration of Polly into LLVM may be
an implicit choice of LLVMs loop optimization future. This is not the case.
While Polly is today the only end-to-end high-level loop optimization, other
approaches can and should explored (e.g., can there be synergies with the region
vectorizer?)
 * How stable/fast/… is Polly today
   * We build all of AOSP with rather restrictive compile-time limits
   * Bootstrapping time of clang is regressed by 6% (at most)
   * Removal of scalar dependences is today very generic and must be sped up in
the future
   * Polly still shows up at the top of the middle-end, but larger compile time
regressions are often due to increased code size (and the LLVM backend)
   * We see non-trivial speedups for hmmer, libquantum, and various
linear-algebra kernels (we use gemm-specific optimizations). The first two
require additional flags to be enabled.

The precise inclusion agenda has been presented here:

http://lists.llvm.org/pipermail/llvm-dev/2017-September/117698.html

After having merged communities, I suggest to form a loop optimization working
group which jointly discusses how LLVM’s loop optimizations should evolve.

I would like to invite comments regarding this proposal.
Are there any specific concerns we should address before requesting the initial
svn move?

Best,
Tobias

> On Jan 15, 2018, at 1:44 PM, Tobias Grosser via llvm-dev <llvm-dev at
lists.llvm.org> wrote:
> Short summary:
> 
> * Today Polly is already part of each LLVM release (and will be shipping
with LLVM 6.0) for everybody to try, with conservative defaults.
> * We proposed to include Polly and isl into LLVM to provide modern
high-level loop optimizations into LLVM
> * We suggested to develop Polly and isl as part of core LLVM to make
interactions with the core LLVM community easier and to allow us to better
integrate Polly with the new pass manager.
I’m definitely in favor of moving polly to a more normal structure as an LLVM
subproject.

If I understand correctly, you are proposing several different things:
1) Moving the polly mailing lists to more conventional structured llvm mailing
lists.
2) Putting a copy of ISL into LLVM.
3) Moving Polly out of its own subproject into the main llvm repo.
4) Turning on polly by default.

Here is my opinion about these steps:

1) This would be great IMO, I’m not sure why Polly was on google groups in the
first place.  That said, I don’t see a strong advantage to having polly
discussion on llvm-dev, rather than just move polly-dev to the llvm list-serv.

2) This is complicated and unconventional for several reasons, but we can lead
that to the other thread.  It also doesn’t seem required by the other goals you
have.

3) I do not understand the motivation of this at all.  Polly in its own
subproject seems perfectly logical to me, just like clang is in its own
subproject.  In the context of the git migration, we’re talking about going to
an uber tree.  In that scenario, I can see how integrating polly makes sense,
but in the absence of that, I don’t understand the motivation.  The LLVM svn
repo is already too monolithic in the SVN design, making it larger isn’t a
feature.

4) I know this isn’t a strong goal immediately, but it has to be a goal to
justify the other steps.  I’d like to know more about this: what is the path
towards this, what are the thresholds and criteria that you think make sense,
how likely are those to happen, and why should we move polly into the tree
before these criteria are established and met?

> Let me briefly summarize the LLVM developer meeting comments on our
proposal (subjective summary)
> 
> * Most people were interested in having polyhedral loop optimizations being
part of LLVM.
Right, but Polly is already part of LLVM.

What is your pitch for why Polly’s status should change?  Why is it good for the
LLVM project?  What code benefits from it?  If you want it integrated as part of
(e.g.) Clang builds, why does it need to move into the LLVM repo?  What is your
path to getting it on by default?  What codes (out side of
already-known-hackable SPEC benchmarks and BLAS kernels) does polly benefit?

Here is another way of asking the question: Clang is the default compiler for
several large OS’s, including (e.g.) FreeBSD.  What programs does Polly show a
measurable benefit for?

-Chris

On Mon, 15 Jan 2018 22:44:45 +0100, Tobias Grosser via llvm-dev wrote:

<snip>
>  * How stable/fast/… is Polly today
>    * We build all of AOSP with rather restrictive compile-time limits
>    * Bootstrapping time of clang is regressed by 6% (at most)
>    * Removal of scalar dependences is today very generic and must be
>      sped up in the future
>    * Polly still shows up at the top of the middle-end, but larger
>      compile time regressions are often due to increased code size (and
>      the LLVM backend)
>    * We see non-trivial speedups for hmmer, libquantum, and various
>      linear-algebra kernels (we use gemm-specific optimizations). The
>      first two require additional flags to be enabled.
On the topic of performance, this paper might be of interest:

Fast Polyhedral Abstract Domain
Gagandeep Singh, Markus Püschel, Martin Vechev
http://www.srl.inf.ethz.ch/papers/POPL17-Polyhedra.pdf
> Our experimental results demonstrate massive gains in both space and
> time: we show end-to-end speedups of two to five orders of magnitude
> compared to state-of-the-art  Polyhedra implementations as well as
> significant memory gains, on all larger benchmarks. In fact, in many
> cases our analysis terminates in seconds where prior code runs out of
> memory or times out after 4 hours.
They compared against PPL and ELISA.

On Tue, 23 Jan 2018 01:23:51 +0000, Alex Elsayed via llvm-dev wrote:
> On Mon, 15 Jan 2018 22:44:45 +0100, Tobias Grosser via llvm-dev wrote:
> 
> <snip>
> 
>>  * How stable/fast/… is Polly today
>>    * We build all of AOSP with rather restrictive compile-time limits *
>>    Bootstrapping time of clang is regressed by 6% (at most)
>>    * Removal of scalar dependences is today very generic and must be
>>      sped up in the future
>>    * Polly still shows up at the top of the middle-end, but larger
>>      compile time regressions are often due to increased code size (and
>>      the LLVM backend)
>>    * We see non-trivial speedups for hmmer, libquantum, and various
>>      linear-algebra kernels (we use gemm-specific optimizations). The
>>      first two require additional flags to be enabled.
> 
> On the topic of performance, this paper might be of interest:
> 
> Fast Polyhedral Abstract Domain
> Gagandeep Singh, Markus Püschel, Martin Vechev
> http://www.srl.inf.ethz.ch/papers/POPL17-Polyhedra.pdf
> 
>> Our experimental results demonstrate massive gains in both space and
>> time: we show end-to-end speedups of two to five orders of magnitude
>> compared to state-of-the-art  Polyhedra implementations as well as
>> significant memory gains, on all larger benchmarks. In fact, in many
>> cases our analysis terminates in seconds where prior code runs out of
>> memory or times out after 4 hours.
> 
> They compared against PPL and ELISA.
Gah, my mistake - they compared against NewPolka and PPL, and _their_ 
work was ELINA.