<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
</head>
<body text="#000000" bgcolor="#FFFFFF">
<p>Hi, Nadav, Chris, et al.,</p>
<p>If you've not already seen it, we had a long discussion about
incorporating Polly into LLVM on llvm-dev,
<a class="moz-txt-link-freetext" href="http://lists.llvm.org/pipermail/llvm-dev/2017-September/117063.html">http://lists.llvm.org/pipermail/llvm-dev/2017-September/117063.html</a>
(with a continuation in October:
<a class="moz-txt-link-freetext" href="http://lists.llvm.org/pipermail/llvm-dev/2017-October/118125.html">http://lists.llvm.org/pipermail/llvm-dev/2017-October/118125.html</a>)
with a lot of detailed information.<br>
</p>
<p>I think it is important, first, that we agree on the goals of
this effort. While Polly is currently used as an isolated
analysis-and-transformation engine, it won't stay that way. The
goal is to split, refactor, and rewrite (as needed) the current
components so that we have four things:</p>
<p> 1. A dependence analysis driven by state-of-the-art polyhedral
analysis.<br>
</p>
<p> 2. A framework for easily constructing loop transformations on
LLVM IR.</p>
<p> 3. Loop transformations built on these capabilities. These might
be canonicalization transformations in addition to
cost-model-driven optimization transformations.</p>
<p> 4. A generic (e.g., ILP-driven) scheduling capability for a wide
class of transformations.</p>
<p>Especially as we leave the realm of inner loops, we need a better
dependence analysis than what we have currently in
LoopAccessAnalysis and DependenceAnalysis. Moreover, this
dependence analysis needs the ability to interact with a
capability for generating dynamic legality predicates (for
multiversioning; something that Polly can do). Dependence analysis
using polyhedral modeling is appealing for several reasons. It
provides a robust solution that seems likely easier to maintain
than an every-expanding set of special tests. Moreover, it
isolates the mathematical reasoning behind a well-defined
interface allowing for proper separation of concerns.<br>
</p>
<p>Working with loops in LLVM currently is unnecessarily difficult.
Just last week I was writing a transformation which split a loop
into several consecutive loops (where each of the p loops had ~n/p
iterations). This seems like a simple task, but even using (what I
believe to be) our best utilities from SCEV, LoopUtils, etc., by
the time I dealt with multiple induction variables, reductions,
and more, plus keeping needed analyses up to date, this
transformation took hundreds of lines of code. We need a better
way of doing this. One of the capabilities within Polly is,
essentially, an infrastructure for rewriting loop nests. Our plan
includes refactoring this capability into a generic loop-rewriting
utility that can be used to implement a variety of different loop
transformations. This should make of our loop transformations,
current and future, easier to write, more robust, and easier to
maintain.</p>
<p>One thing we can do immediately with this infrastructure, even in
its current form, is provide a user-driven (i.e.,
metadata-directed) set of transformations encompassing nearly all
common loop-nest transforms (interchange, fission/fusion, skewing,
tiling). Importantly, we can do this, not only where the user
assert safety, but using polyhedral analysis, also where we
generate legality predicates. This would be a significant step
toward making LLVM-based compilers in the top tier of HPC
compilers, but having such capabilities only conditionally
supported in the backend would be an unfortunate complication for
our users.</p>
<p>The automated loop-nest rewriting (using an ILP-solver to pick
some optimal schedule), which is what many people might think of
as the primary usage modality of polyhedral loop optimizations,
and thus Polly, is only a part of this overall program for
improving LLVM's infrastructure for handling loops. This is an
important capability, but among many other factors, depends on
good cost modeling (an area in which Polly currently needs work).
If at some point the cost modeling, etc. improves to the point
where we could have something like this in the default
optimization pipeline, that would be great (from my perspective),
but that's only a small potential benefit from this integration.</p>
<p>In addition to these technical aspects, there are community
considerations, but with respect to Polly, and with respect to the
isl library on which it depends. Obviously there are different
ways we can develop these capabilities in LLVM, but I prefer a way
that takes as much of the existing Polly community as possible and
merges it into the LLVM community. This requires preserving
Polly's current capabilities during this development process, and
ideally, not partitioning between the "old" separate-repository
code base and the "new" in-tree code base. The tricky part here is
what to do with isl. To be clear, isl has already been relicensed
once with the specific goal of better LLVM integration, the
dependency on GMP has been removed, and further changes along
these lines are not unthinkable. isl has its own developer
community, but many of the core Polly developers are also
significant isl contributors, and so there's significant overlap.
The remainder of the isl community is a significant resource, and
whether or not we wish to separate it from our development in this
area is something we should specifically consider. I personally
suspect that we'll end up rewriting a lot of what's in isl
eventually, but we'd need to figure out what to do in the mean
time. isl is a moving target, like LLVM itself, and given the
developer overlap between Polly and isl, I don't think it makes
sense to think of isl as some kind of truly external dependency.
We'd likely need to version lock anyway, so the benefit of having
isl in a separate repository on separate servers seems like a
system providing all of the disadvantages of an external
dependency with few/none of the benefits. This is why Polly
currently has the needed version of isl in its repository, and in
order to move Polly into LLVM itself, moving isl seems like the
first step.<br>
</p>
<p>Finally, LLVM is a major dependency of many external projects,
and binary side is certainly a concern. In general, we need a
better way to enable not compiling transformations not needed by a
particular project. Polyhedral, or any other, loop transformations
are no different from CFL alias analysis, sanitizer
instrumentation passes, or any number of other things in this
regard. We should have a better infrastructure for partial builds
but we shouldn't hold up any particular contribution because of
deficiencies in this area. Also, I believe that the infrastructure
added will be useful for transformations important to many
different frontends (e.g., bounds-check removal and canonicalizing
transformations).<br>
</p>
Thanks again,<br>
Hal<br>
<br>
<div class="moz-cite-prefix">On 01/20/2018 12:47 PM, Nadav Rotem via
llvm-dev wrote:<br>
</div>
<blockquote type="cite"
cite="mid:99fd096a-5848-43f2-a079-9e15d997f9ff@me.com">
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<div><br>
</div>
<div>
<div style="color: #000000; font-family: SFNSText, 'Helvetica
Neue', Helvetica, Arial, sans-serif; font-size: 15px;
font-style: normal; font-variant-ligatures: normal;
font-variant-caps: normal; font-weight: 300; letter-spacing:
normal; orphans: 2; text-align: start; text-indent: 0px;
text-transform: none; white-space: normal; widows: 2;
word-spacing: 0px; -webkit-text-stroke-width: 0px;
text-decoration-style: initial; text-decoration-color:
initial;" data-mce-style="color: #000000; font-family:
SFNSText, 'Helvetica Neue', Helvetica, Arial, sans-serif;
font-size: 15px; font-style: normal; font-variant-ligatures:
normal; font-variant-caps: normal; font-weight: 300;
letter-spacing: normal; orphans: 2; text-align: start;
text-indent: 0px; text-transform: none; white-space: normal;
widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px;
text-decoration-style: initial; text-decoration-color:
initial;">Hi Tobi, </div>
<div style="color: #000000; font-family: SFNSText, 'Helvetica
Neue', Helvetica, Arial, sans-serif; font-size: 15px;
font-style: normal; font-variant-ligatures: normal;
font-variant-caps: normal; font-weight: 300; letter-spacing:
normal; orphans: 2; text-align: start; text-indent: 0px;
text-transform: none; white-space: normal; widows: 2;
word-spacing: 0px; -webkit-text-stroke-width: 0px;
text-decoration-style: initial; text-decoration-color:
initial;" data-mce-style="color: #000000; font-family:
SFNSText, 'Helvetica Neue', Helvetica, Arial, sans-serif;
font-size: 15px; font-style: normal; font-variant-ligatures:
normal; font-variant-caps: normal; font-weight: 300;
letter-spacing: normal; orphans: 2; text-align: start;
text-indent: 0px; text-transform: none; white-space: normal;
widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px;
text-decoration-style: initial; text-decoration-color:
initial;"><br data-mce-bogus="1">
</div>
<div style="color: #000000; font-family: SFNSText, 'Helvetica
Neue', Helvetica, Arial, sans-serif; font-size: 15px;
font-style: normal; font-variant-ligatures: normal;
font-variant-caps: normal; font-weight: 300; letter-spacing:
normal; orphans: 2; text-align: start; text-indent: 0px;
text-transform: none; white-space: normal; widows: 2;
word-spacing: 0px; -webkit-text-stroke-width: 0px;
text-decoration-style: initial; text-decoration-color:
initial;" data-mce-style="color: #000000; font-family:
SFNSText, 'Helvetica Neue', Helvetica, Arial, sans-serif;
font-size: 15px; font-style: normal; font-variant-ligatures:
normal; font-variant-caps: normal; font-weight: 300;
letter-spacing: normal; orphans: 2; text-align: start;
text-indent: 0px; text-transform: none; white-space: normal;
widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px;
text-decoration-style: initial; text-decoration-color:
initial;">I have some concerns about adding Polly into LLVM
proper. I think that it's great that Polly is a part of the
LLVM umbrella of projects, like Clang and LLDB. However, I am
not convinced that Polly belongs in the LLVM compiler
library. LLVM is a major dependency for so many external
projects. Rust, Swift, GPU drivers by different vendors, and
JIT compilers all rely on LLVM. Projects that depend on LLVM <span
data-mce-style="color: #000000; font-family: SFNSText,
'Helvetica Neue', Helvetica, Arial, sans-serif; font-size:
15px; font-style: normal; font-variant-ligatures: normal;
font-variant-caps: normal; font-weight: 300; letter-spacing:
normal; orphans: 2; text-align: start; text-indent: 0px;
text-transform: none; white-space: normal; widows: 2;
word-spacing: 0px; -webkit-text-stroke-width: 0px;
background-color: #ffffff; text-decoration-style: initial;
text-decoration-color: initial; display: inline !important;
float: none;" style="color: rgb(0, 0, 0); font-family:
SFNSText, "Helvetica Neue", Helvetica, Arial,
sans-serif; font-size: 15px; font-style: normal;
font-variant-ligatures: normal; font-variant-caps: normal;
font-weight: 300; letter-spacing: normal; orphans: 2;
text-align: start; text-indent: 0px; text-transform: none;
white-space: normal; widows: 2; word-spacing: 0px;
-webkit-text-stroke-width: 0px; background-color: rgb(255,
255, 255); text-decoration-style: initial;
text-decoration-color: initial; float: none; display: inline
!important;">are going to pay the cost of adding Polly into
the LLVM library. </span>These projects operate under a
different set of constraints and optimize different metrics.
One of my main concerns is binary size. The size of the LLVM
compiler library matters, especially on mobile, especially for
JIT compilers. Growing the size of the LLVM binary increases
the app load time (because the shared object needs to be read
from disk). Moreover, the current size of the LLVM library
prevents people from bundling a copy of LLVM with mobile apps
because app stores limit the size of apps. Yes, I know that
it's possible to disable Polly in production scenarios, but
this looks like an unnecessary hurdle. </div>
<div style="color: #000000; font-family: SFNSText, 'Helvetica
Neue', Helvetica, Arial, sans-serif; font-size: 15px;
font-style: normal; font-variant-ligatures: normal;
font-variant-caps: normal; font-weight: 300; letter-spacing:
normal; orphans: 2; text-align: start; text-indent: 0px;
text-transform: none; white-space: normal; widows: 2;
word-spacing: 0px; -webkit-text-stroke-width: 0px;
text-decoration-style: initial; text-decoration-color:
initial;" data-mce-style="color: #000000; font-family:
SFNSText, 'Helvetica Neue', Helvetica, Arial, sans-serif;
font-size: 15px; font-style: normal; font-variant-ligatures:
normal; font-variant-caps: normal; font-weight: 300;
letter-spacing: normal; orphans: 2; text-align: start;
text-indent: 0px; text-transform: none; white-space: normal;
widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px;
text-decoration-style: initial; text-decoration-color:
initial;"> <br>
</div>
<div style="color: #000000; font-family: SFNSText, 'Helvetica
Neue', Helvetica, Arial, sans-serif; font-size: 15px;
font-style: normal; font-variant-ligatures: normal;
font-variant-caps: normal; font-weight: 300; letter-spacing:
normal; orphans: 2; text-align: start; text-indent: 0px;
text-transform: none; white-space: normal; widows: 2;
word-spacing: 0px; -webkit-text-stroke-width: 0px;
text-decoration-style: initial; text-decoration-color:
initial;" data-mce-style="color: #000000; font-family:
SFNSText, 'Helvetica Neue', Helvetica, Arial, sans-serif;
font-size: 15px; font-style: normal; font-variant-ligatures:
normal; font-variant-caps: normal; font-weight: 300;
letter-spacing: normal; orphans: 2; text-align: start;
text-indent: 0px; text-transform: none; white-space: normal;
widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px;
text-decoration-style: initial; text-decoration-color:
initial;">Would it be possible to use the LLVM plugin
mechanism to load Polly dynamically into the clang pass
manager instead of integrating it into the LLVM tree? </div>
<div style="color: #000000; font-family: SFNSText, 'Helvetica
Neue', Helvetica, Arial, sans-serif; font-size: 15px;
font-style: normal; font-variant-ligatures: normal;
font-variant-caps: normal; font-weight: 300; letter-spacing:
normal; orphans: 2; text-align: start; text-indent: 0px;
text-transform: none; white-space: normal; widows: 2;
word-spacing: 0px; -webkit-text-stroke-width: 0px;
text-decoration-style: initial; text-decoration-color:
initial;" data-mce-style="color: #000000; font-family:
SFNSText, 'Helvetica Neue', Helvetica, Arial, sans-serif;
font-size: 15px; font-style: normal; font-variant-ligatures:
normal; font-variant-caps: normal; font-weight: 300;
letter-spacing: normal; orphans: 2; text-align: start;
text-indent: 0px; text-transform: none; white-space: normal;
widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px;
text-decoration-style: initial; text-decoration-color:
initial;"><br data-mce-bogus="1">
</div>
<div style="color: #000000; font-family: SFNSText, 'Helvetica
Neue', Helvetica, Arial, sans-serif; font-size: 15px;
font-style: normal; font-variant-ligatures: normal;
font-variant-caps: normal; font-weight: 300; letter-spacing:
normal; orphans: 2; text-align: start; text-indent: 0px;
text-transform: none; white-space: normal; widows: 2;
word-spacing: 0px; -webkit-text-stroke-width: 0px;
text-decoration-style: initial; text-decoration-color:
initial;" data-mce-style="color: #000000; font-family:
SFNSText, 'Helvetica Neue', Helvetica, Arial, sans-serif;
font-size: 15px; font-style: normal; font-variant-ligatures:
normal; font-variant-caps: normal; font-weight: 300;
letter-spacing: normal; orphans: 2; text-align: start;
text-indent: 0px; text-transform: none; white-space: normal;
widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px;
text-decoration-style: initial; text-decoration-color:
initial;">Thanks,</div>
<div style="color: #000000; font-family: SFNSText, 'Helvetica
Neue', Helvetica, Arial, sans-serif; font-size: 15px;
font-style: normal; font-variant-ligatures: normal;
font-variant-caps: normal; font-weight: 300; letter-spacing:
normal; orphans: 2; text-align: start; text-indent: 0px;
text-transform: none; white-space: normal; widows: 2;
word-spacing: 0px; -webkit-text-stroke-width: 0px;
text-decoration-style: initial; text-decoration-color:
initial;" data-mce-style="color: #000000; font-family:
SFNSText, 'Helvetica Neue', Helvetica, Arial, sans-serif;
font-size: 15px; font-style: normal; font-variant-ligatures:
normal; font-variant-caps: normal; font-weight: 300;
letter-spacing: normal; orphans: 2; text-align: start;
text-indent: 0px; text-transform: none; white-space: normal;
widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px;
text-decoration-style: initial; text-decoration-color:
initial;">Nadav <br>
</div>
<div style="color: #000000; font-family: SFNSText, 'Helvetica
Neue', Helvetica, Arial, sans-serif; font-size: 15px;
font-style: normal; font-variant-ligatures: normal;
font-variant-caps: normal; font-weight: 300; letter-spacing:
normal; orphans: 2; text-align: start; text-indent: 0px;
text-transform: none; white-space: normal; widows: 2;
word-spacing: 0px; -webkit-text-stroke-width: 0px;
text-decoration-style: initial; text-decoration-color:
initial;" data-mce-style="color: #000000; font-family:
SFNSText, 'Helvetica Neue', Helvetica, Arial, sans-serif;
font-size: 15px; font-style: normal; font-variant-ligatures:
normal; font-variant-caps: normal; font-weight: 300;
letter-spacing: normal; orphans: 2; text-align: start;
text-indent: 0px; text-transform: none; white-space: normal;
widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px;
text-decoration-style: initial; text-decoration-color:
initial;"><br data-mce-bogus="1">
</div>
<br>
On Jan 15, 2018, at 01:33 PM, Tobias Grosser via llvm-dev
<a class="moz-txt-link-rfc2396E" href="mailto:llvm-dev@lists.llvm.org"><llvm-dev@lists.llvm.org></a> wrote:<br>
<br>
</div>
<div>
<blockquote type="cite">
<div class="msg-quote">
<div class="_stretch"><span class="body-text-content">Dear
LLVM community,<br>
<br>
hope all of you had a good start into 2018 and a quiet
branching of LLVM 6.0.<br>
<br>
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.<br>
<br>
Short summary:<br>
<br>
* Today Polly is already part of each LLVM release (and
will be shipping with LLVM 6.0) for everybody to try,
with conservative defaults.<br>
* We proposed to include Polly and isl into LLVM to
provide modern high-level loop optimizations into LLVM<br>
* 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.<br>
<br>
Let me briefly summarize the current status:<br>
<br>
* Michael sent out an official email to discuss how to
best include isl into LLVM<br>
(<a
href="http://lists.llvm.org/pipermail/llvm-dev/2018-January/120408.html"
data-mce-href="http://lists.llvm.org/pipermail/llvm-dev/2018-January/120408.html"
moz-do-not-send="true">http://lists.llvm.org/pipermail/llvm-dev/2018-January/120408.html</a>)<br>
* We sent out the LLVM developers meeting notes (<a
href="_http://lists.llvm.org/pipermail/llvm-dev/2018-January/120419.html_"
data-mce-href="_http://lists.llvm.org/pipermail/llvm-dev/2018-January/120419.html_"
moz-do-not-send="true">_http://lists.llvm.org/pipermail/llvm-dev/2018-January/120419.html_</a>)<br>
* Philip Pfaffe prepared a preliminary patch set for
integrating Polly closer into LLVM:<br>
<a
href="_https://github.com/pfaffe/llvm-project-20170507/commits/merge-polly-into-upstream_"
data-mce-href="_https://github.com/pfaffe/llvm-project-20170507/commits/merge-polly-into-upstream_"
moz-do-not-send="true">_https://github.com/pfaffe/llvm-project-20170507/commits/merge-polly-into-upstream_</a><br>
(further cleanup needed)<br>
* 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. <a
href="_https://reviews.llvm.org/D38585_"
data-mce-href="_https://reviews.llvm.org/D38585_"
moz-do-not-send="true">_https://reviews.llvm.org/D38585_</a><br>
* Oleksandr, Sven and Manasij Mukherjee started to look
into spatial locality<br>
* We worked on expanding the isl C++ bindings (<a
href="_http://repo.or.cz/isl.git/shortlog_"
data-mce-href="_http://repo.or.cz/isl.git/shortlog_"
moz-do-not-send="true">_http://repo.or.cz/isl.git/shortlog_</a>).
While a first set of patches is already open, further
patches will follow over the next couple of weeks.<br>
<br>
Let me briefly summarize the LLVM developer meeting
comments on our proposal (subjective summary)<br>
<br>
* Most people were interested in having polyhedral loop
optimizations being part of LLVM.<br>
* 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.<br>
* 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?)<br>
* How stable/fast/… is Polly today<br>
* We build all of AOSP with rather restrictive
compile-time limits<br>
* Bootstrapping time of clang is regressed by 6% (at
most)<br>
* Removal of scalar dependences is today very generic
and must be sped up in the future<br>
* 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)<br>
* 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.<br>
<br>
The precise inclusion agenda has been presented here:<br>
<br>
<a
href="http://lists.llvm.org/pipermail/llvm-dev/2017-September/117698.html"
data-mce-href="http://lists.llvm.org/pipermail/llvm-dev/2017-September/117698.html"
moz-do-not-send="true">http://lists.llvm.org/pipermail/llvm-dev/2017-September/117698.html</a><br>
<br>
After having merged communities, I suggest to form a
loop optimization working group which jointly discusses
how LLVM’s loop optimizations should evolve.<br>
<br>
I would like to invite comments regarding this proposal.<br>
Are there any specific concerns we should address before
requesting the initial svn move?<br>
<br>
Best,<br>
Tobias<br>
<br>
<br>
_______________________________________________<br>
LLVM Developers mailing list<br>
<a href="mailto:llvm-dev@lists.llvm.org"
data-mce-href="mailto:llvm-dev@lists.llvm.org"
moz-do-not-send="true">llvm-dev@lists.llvm.org</a><br>
<a
href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev"
data-mce-href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev"
moz-do-not-send="true">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a><br>
</span></div>
</div>
</blockquote>
</div>
<br>
<fieldset class="mimeAttachmentHeader"></fieldset>
<br>
<pre wrap="">_______________________________________________
LLVM Developers mailing list
<a class="moz-txt-link-abbreviated" href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a>
<a class="moz-txt-link-freetext" href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev">http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev</a>
</pre>
</blockquote>
<br>
<pre class="moz-signature" cols="72">--
Hal Finkel
Lead, Compiler Technology and Programming Languages
Leadership Computing Facility
Argonne National Laboratory</pre>
</body>
</html>