llvm dev - Sep 2017 - [RFC] Polly Status and Integration

Hi Sebastian,

thanks for the comments!

On 09/27, Sebastian Pop wrote:
> On Tue, Sep 26, 2017 at 2:00 AM, Tobias Grosser via llvm-dev
> <llvm-dev at lists.llvm.org> wrote:
> > On Tue, Sep 26, 2017, at 00:03, Johannes Doerfert wrote:
> >> It depends on what you want. If you want a polyhedral scheduler
right
> >> away, integration is the way to go.
> 
> I think this is the topic of the thread as the folks who started
> this discussion stated that they want to see Polly integrated
> in LLVM.
> 
> >> However, I don't think reuse of
> >> Polly for other purposes is that simple and the changes I argue
for are
> >> (in this context) quite complicated (see below).
> 
> You are just saying that there are difficult to write polyhedral
> passes that do not fully rely on the infrastructure that Polly
> provides, which in my opinion, is perfectly fine.
> 
> Polly's integration will bring to LLVM more than the loop
> transforms that Polly implements with isl's schedulers:
> there are a set of issues that Polly had to solve and that will
> be of use by the other polyhedral analyses and optimizations
> that you are mentioning.
> Here are a few examples of the more general infrastructure
> that Polly enables: license of isl compatible with LLVM, isl's
> compute-out, imath, native int computations instead of MP, etc.
Do we need to integrate Polly to get these benefits?
> >> I do think that changing all the parts I mentioned will require a
major
> >> rewrite and that it will be more complicated than writing the
components
> >> "from scratch".
> 
> Nobody tries to stop you writing those things from scratch.
I never got this impression, if it did look that way than by accident.
> However if you want to make those passes useful to the
> existing code, for example in value range propagation,
> or in some of the redundant code elimination passes,
> or in Polly, you would have to deal with the complexities
> of transitioning the existing code to the new analysis interfaces.
Actually, I started to copy parts of the ScalarEvolution interface in
order to integrate the analysis passes this way into LLVM
transformations. While it is obviously hard (and probably not useful) to
provide "exactly" the same interface as ScalarEvolution, I can look at
the use cases e.g., LoopDeletion, and try to come up with a general way
to convey the needed information, e.g. "bool mayBeInfinite(Loop *L)".

My point is that I can easily use the modular analysis design to do only
what is needed to answer a query without any worrying about side effects
that are of no concern.

Let me elaborate on this example. If you want to know if a loop might be
infinite you only need to check the iteration domain (and the soundness
of the modeling of that domain). What you explicitly not need to look at
are accesses (in order to safe time and increases applicability). To use
Polly for this query you would need to modify multiple code locations.
That means even more code paths just to prevent the analysis of accesses
but allow only the domains to be represented. I do not say it is
impossible but I try to argue that Polly is just not designed for such a
use case and we should not pretend otherwise.
> >> The reason is simple, new components can be developed
> >> one by one without the need to worry about the implications for
later
> >> passes. We can design them for the uses cases at hand while
keeping
> >> their use in a future polyhedral scheduling pipeline in mind. In
Polly,
> >> the things I want to change have implicit and explicit ties to
various
> >> parts in the pipeline. Consequently, it is extremely challenging
to
> >> change them only in parts of the pipeline e.g., the modeling, at
least
> >> if we want to keep the original functionality intact all the time.
> 
> This is normal operation: work in the compiler is incremental,
> it happens by evolution and rarely by revolution.
My point exactly.
> I will give you an example from another part of the compiler that
> we try to extend while keeping the existing pass work at all time:
> jump-threading.
> The original jump-thread pass was contributed more than
> 10 years ago, and it does pretty well to optimize the code.
> However it still cannot jump-thread across multiple basic blocks
> and across loop back-edges: there were several attempts in
> extending the existing pass without much traction.
> An easy way would be to start from scratch and just implement
> a new pass. However that would require to implement more
> than half of the analysis and code generation with code that
> would mostly look the same. I see no good reason to throw
> away that code when we could very well improve over the
> existing code in incremental steps:
> maintaining the dominators, improve the way we operate on
> the CFG, maintaining loops across several jump-threads, etc.,
> the sum of which gets us closer to what we want to achieve
> while improving the existing code.
First, I never argued to throw anything away. Second, I do not know the
details of the jump-threading evolution. Third, we also do reimplement
things from scratch from time to time while we keep on using the
original code.
> > For some of the changes you propose -- e.g. extracting parts of Polly
to
> > build a polyhedral value analysis -- extracting it out individually is
> > clearly the right approach.
> 
> I agree: making the infrastructure more general and used in
> more code than in isl's polyhedral schedulers can happen
> as incremental changes as new functionality is built.
> If the current way Polly does things stands in the way,
> it should be fixed in incremental steps.
I tried that. One reason I had to give up is that it is simply much
harder. You cannot always get rid of fundamental design choices
incrementally. At least not if you do not want to disturb the rest of
the pipeline while you do it. And while this is not (yet) a mission
critical component I do think people would like to keep the scheduling
capabilities of Polly working all the time.


Cheers,
  Johannes

-- 

Johannes Doerfert
Researcher / PhD Student

Compiler Design Lab (Prof. Hack)
Saarland Informatics Campus, Germany
Building E1.3, Room 4.31

Tel. +49 (0)681 302-57521 : doerfert at cs.uni-saarland.de
Fax. +49 (0)681 302-3065  : http://www.cdl.uni-saarland.de/people/doerfert
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 228 bytes
Desc: Digital signature
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170929/e8df06d9/attachment.sig>

Hi,

On Thu, Sep 28, 2017 at 6:15 PM, Johannes Doerfert via llvm-dev <
llvm-dev at lists.llvm.org> wrote:
>
> Actually, I started to copy parts of the ScalarEvolution interface in
> order to integrate the analysis passes this way into LLVM
> transformations. While it is obviously hard (and probably not useful) to
> provide "exactly" the same interface as ScalarEvolution, I can
look at
> the use cases e.g., LoopDeletion, and try to come up with a general way
> to convey the needed information, e.g. "bool mayBeInfinite(Loop
*L)".
>
> My point is that I can easily use the modular analysis design to do only
> what is needed to answer a query without any worrying about side effects
> that are of no concern.

Great! We do some wonderful stuff with ScalarEvolution and I was waiting
for something like that to exploit some of that polyhedral magic. I think
that this is a promising approach. However, because having Polyhedral
Analysis is an orthogonal approach to Polly (which is more like a
Polyhedral IR), it is not really correlated with the true goal of this
discussion: integrating Polly or not into LLVM (except that it would mean
isl is already a dependency).

I am okay with having those two approaches in LLVM itself.

Polly is oriented towards providing a full blown polyhedral compiler
pipeline, this is great in the sense that it allows to do all the high
level transformations we can dream of, but this is also difficult to
compose with current LLVM passes, we lose debug information, and it is
relatively hard to control what happen. As such, it might be fine in its
own folder, I don't see much interest in "not compiling Polly"
except if to
not have the isl library as a dependency.

Polyhedral Analysis is oriented towards providing new tools for any LLVM
analysis or transformation passes. There is a wide range of applicability
to this (it can at least be used almost everywhere ScalarEvolution can),
and because it can represent set and relations (instead of only functions
like SCEV) I suspect it can be used in an even wider range of applications
and a lot of them are outside the polyhedral realm (aka. will hardly ever
fit into Polly's pipeline).

As for the isl as a dependency, I don't really mind. isl is a relatively
small library with a rather stable interface, and its compilation time is
quite short. Including the whole source code (like Polly), or requesting it
as an external dependency is probably fine. I would suggest however that we
don't diverge from upstream isl if we continue the route of including the
source code (we might want to upstream a CMake build?).

-- 
*Alexandre Isoard*
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170928/7cb3b4e9/attachment.html>

Hi Alexandre,

great to get more people involved! (That also includes Sebastian who
wrote the last mail).

On 09/28, Alexandre Isoard wrote:
> Hi,
> 
> On Thu, Sep 28, 2017 at 6:15 PM, Johannes Doerfert via llvm-dev <
> llvm-dev at lists.llvm.org> wrote:
> >
> > Actually, I started to copy parts of the ScalarEvolution interface in
> > order to integrate the analysis passes this way into LLVM
> > transformations. While it is obviously hard (and probably not useful)
to
> > provide "exactly" the same interface as ScalarEvolution, I
can look at
> > the use cases e.g., LoopDeletion, and try to come up with a general
way
> > to convey the needed information, e.g. "bool mayBeInfinite(Loop
*L)".
> >
> > My point is that I can easily use the modular analysis design to do
only
> > what is needed to answer a query without any worrying about side
effects
> > that are of no concern.
> 
> 
> Great! We do some wonderful stuff with ScalarEvolution and I was waiting
> for something like that to exploit some of that polyhedral magic. I think
> that this is a promising approach. However, because having Polyhedral
> Analysis is an orthogonal approach to Polly (which is more like a
> Polyhedral IR), it is not really correlated with the true goal of this
> discussion: integrating Polly or not into LLVM (except that it would mean
> isl is already a dependency).
> 
> I am okay with having those two approaches in LLVM itself.
I do not object to this statement, nor to the reasoning below. I
mentioned before that Polly is the (only) way to get a full blown
polyhedral compiler pipeline, at least for the foreseeable future. My
main arguments targeted the use of parts of it as stand-alone analyses
and you summarized that well.

Thanks!

--
  Johannes
> Polly is oriented towards providing a full blown polyhedral compiler
> pipeline, this is great in the sense that it allows to do all the high
> level transformations we can dream of, but this is also difficult to
> compose with current LLVM passes, we lose debug information, and it is
> relatively hard to control what happen. As such, it might be fine in its
> own folder, I don't see much interest in "not compiling
Polly" except if to
> not have the isl library as a dependency.
> 
> Polyhedral Analysis is oriented towards providing new tools for any LLVM
> analysis or transformation passes. There is a wide range of applicability
> to this (it can at least be used almost everywhere ScalarEvolution can),
> and because it can represent set and relations (instead of only functions
> like SCEV) I suspect it can be used in an even wider range of applications
> and a lot of them are outside the polyhedral realm (aka. will hardly ever
> fit into Polly's pipeline).
> 
> As for the isl as a dependency, I don't really mind. isl is a
relatively
> small library with a rather stable interface, and its compilation time is
> quite short. Including the whole source code (like Polly), or requesting it
> as an external dependency is probably fine. I would suggest however that we
> don't diverge from upstream isl if we continue the route of including
the
> source code (we might want to upstream a CMake build?).
> 
> -- 
> *Alexandre Isoard*
-- 

Johannes Doerfert
Researcher / PhD Student

Compiler Design Lab (Prof. Hack)
Saarland Informatics Campus, Germany
Building E1.3, Room 4.31

Tel. +49 (0)681 302-57521 : doerfert at cs.uni-saarland.de
Fax. +49 (0)681 302-3065  : http://www.cdl.uni-saarland.de/people/doerfert
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 228 bytes
Desc: Digital signature
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170929/a4f7fe7d/attachment.sig>