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

On Fri, Oct 13, 2017 at 5:13 PM, Michael Kruse via llvm-dev <
llvm-dev at lists.llvm.org> wrote:
> 2017-10-14 1:29 GMT+02:00 Saito, Hideki via llvm-dev <
> llvm-dev at lists.llvm.org>:
> > I'm also sorry that I'm not commenting on the main part of
your RFC in
> this reply. I just want to focus on
> > one thing here.
> >
> >                       Proposed Loop Optimization Framework
> >                       ------------------------------------
> >                       Only the architecture is outlined here. The
> reasons for them can be
> >                       found in the "rationales" section
below.
> >
> >                       A) Preprocessing
> >                       Make a copy of the entire function to allow
> transformations only for
> >                       the sake of analysis.
> >
> > Before we started our journey into VPlan-based vectorization approach,
> we explicitly asked about modifying the IR for
> > the sake of vectorization analysis ----- general consensus in LLVM-DEV
> was "that's a bad idea". We thought so, too.
> > That's the reason VPlan has its own local data structure that it
can
> play with.
> >
> > Making a copy of the entire function is far worse than copying a loop
> (nest). Unless the community mindset has dramatically
> > changed since ~2yrs ago, it's unlikely that you'll get
overwhelming
> support on "copy the entire function" before the decision
> > to transform is taken. So, if this part is optional, you may want to
> state that.
> >
> > Having said that, in https://reviews.llvm.org/D38676, we are
> introducing concepts like VPValue, VPUser, and VPInstruction,
> > in order to manipulate and interact with things that didn't come
from
> the IR of the original loop (nest). As such, I can see
> > why you think "a playground copy of IR" is beneficial. Even
before
> reading your RFC, I was actually thinking that someone
> > else may also benefit from VPValue/VPUser/VPInstruction-like concept
> for the analysis part of some heavy-weight transformations.
> > Ideally, what we wanted to do was to use LLVM's Value class
hierarchy if
> we could generate/manipulate "abstract Instructions"
> > w/o making them parts of the IR state, instead of creating our own
> light-weight VPValue/VPUser/VPInstruction classes.
> > If anyone has better ideas in this area, we'd like to listen to.
Please
> reply either to this thread or through the code review
> > mentioned above.
>
> Thank you for bringing in results from previous discussions. The only
> resource I was aware of was the EuroLLVM talk where I got the
> impression this was done for performance reasons. Do you recall the
> arguments why it was considered a bad idea?
>
> I understand that modifying the IR speculatively might not the best
> thing to do. However, I also think that another meta-layer
> representing instructions increases complexity and duplicates
> algorithms when we could just reuse the data structures and algorithms
> that already exist and have matured.
>
I have a feeling that the LLVM LoopInfo/Loop datastructure, which only
focus on the CFG, is not sufficient.
And we build extra layer upon the LLVM LoopInfo/Loop, e.g. Scop in Polly
and  the Hierarchical CFG in VPlan (right?).

Maybe we can have layers between the existing LoopInfo/Loop and VPlan/SCoP:

1. LoopInfo/Loop
2. LoopInfo/Loop + Hierarchical CFG
3. LoopInfo/Loop + Hierarchical CFG + Memory Accesses description
4. VPlan/Scop

I think layer 2 and 3 will be very useful even outside of Polly and VPlan

Hongbin

>
> Michael
> _______________________________________________
> 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/20171014/ce29c4a3/attachment.html>

2017-10-14 22:30 GMT+02:00 Hongbin Zheng <etherzhhb at
gmail.com>:
> I have a feeling that the LLVM LoopInfo/Loop datastructure, which only
focus
> on the CFG, is not sufficient.
> And we build extra layer upon the LLVM LoopInfo/Loop, e.g. Scop in Polly
and
> the Hierarchical CFG in VPlan (right?).
>
> Maybe we can have layers between the existing LoopInfo/Loop and VPlan/SCoP:
>
> 1. LoopInfo/Loop
> 2. LoopInfo/Loop + Hierarchical CFG
> 3. LoopInfo/Loop + Hierarchical CFG + Memory Accesses description
> 4. VPlan/Scop
>
> I think layer 2 and 3 will be very useful even outside of Polly and VPlan
The idea is also that the new hierarchy can be modified iteratively
and IR only generated at the end when all transform decisions have
been made, and analysis/layers be shared between transformations, eg..
a polyhedral dependency analysis, when available, can be used by the
vectorizer without additional programming because the dependency data
structure is the same. PolyhedralInfo currently is very different from
LoopAccessAnalysis.

Michael

2017-10-14 22:30 GMT+02:00 Hongbin Zheng <etherzhhb at
gmail.com>:
> I have a feeling that the LLVM LoopInfo/Loop datastructure, which only
focus
> on the CFG, is not sufficient.
> And we build extra layer upon the LLVM LoopInfo/Loop, e.g. Scop in Polly
and
> the Hierarchical CFG in VPlan (right?).
>
> Maybe we can have layers between the existing LoopInfo/Loop and VPlan/SCoP:
>
> 1. LoopInfo/Loop
> 2. LoopInfo/Loop + Hierarchical CFG
> 3. LoopInfo/Loop + Hierarchical CFG + Memory Accesses description
> 4. VPlan/Scop
>
> I think layer 2 and 3 will be very useful even outside of Polly and VPlan
The idea is also that the new hierarchy can be modified iteratively
and IR only generated at the end when all transform decisions have
been made, and analysis/layers be shared between transformations, eg..
a polyhedral dependency analysis, when available, can be used by the
vectorizer without additional programming because the dependency data
structure is the same. PolyhedralInfo currently is very different from
LoopAccessAnalysis.

Michael

On Sat, Oct 14, 2017 at 3:00 PM, Michael Kruse <llvmdev at meinersbur.de>
wrote:
> 2017-10-14 22:30 GMT+02:00 Hongbin Zheng <etherzhhb at gmail.com>:
> > I have a feeling that the LLVM LoopInfo/Loop datastructure, which only
> focus
> > on the CFG, is not sufficient.
> > And we build extra layer upon the LLVM LoopInfo/Loop, e.g. Scop in
Polly
> and
> > the Hierarchical CFG in VPlan (right?).
> >
> > Maybe we can have layers between the existing LoopInfo/Loop and
> VPlan/SCoP:
> >
> > 1. LoopInfo/Loop
> > 2. LoopInfo/Loop + Hierarchical CFG
> > 3. LoopInfo/Loop + Hierarchical CFG + Memory Accesses description
> > 4. VPlan/Scop
> >
> > I think layer 2 and 3 will be very useful even outside of Polly and
VPlan
>
> The idea is also that the new hierarchy can be modified iteratively
> and IR only generated at the end
In general 1-4 are different representations to the same program, or a set
of equivalent programs (at different levels of abstraction), and eventually
we need to properly connect different representations together such that we
can materialize the changes from one representation to another.
Maybe we could have a common infrastructure builtin to the Value class
hierarchy to allow us to easily connect LLVM IR to different
representations (e.g. SCoP or VPlan) and propagate the changes back?


> when all transform decisions have
> been made, and analysis/layers be shared between transformations, eg..
> a polyhedral dependency analysis, when available, can be used by the
> vectorizer without additional programming because the dependency data
> structure is the same
One way to achieve this is to design an interface like Alias Analsyis, to
hide different implementations behind a "common" interface.


> . PolyhedralInfo currently is very different from
> LoopAccessAnalysis.
>
> Michael
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20171016/af31b51f/attachment.html>