llvm dev - Mar 2016 - Polly as an Analysis pass in LLVM

Hey Utpal,

First of, I think you made nice process here and have some very good
ideas of what we could do in the future.

[NOTE: I CC'ed some people that have shown interest in this topic but I
might have forgotten some, therefor I also added the llvm-dev list.]

For the upcoming GSoC proposal we should slow down a little bit and
reevaluate our goals. After talking to a couple of LLVM and Polly folks
at EuroLLVM last week, I hope to have a fairly good idea of how to
proceed. To this end, I will give you my personal road map that might be
a good start for the proposal too, though it is not the only way we
could do this:

  1) Make ScopInfo & DependenceInfo function passes to avoid the
     RegionPassManager for these Polly analysis parts. [This doesn't
     need to be the first step but it should be done at some point.]
  2) Create a secondary ScopDetection & ScopInfo that is restricted to
     analyze a single loop. We might just create a dummy region for this
     loop and use the original ScopDetection & ScopInfo. The goal is to
     make (this secondary) ScopDetection & ScopInfo demand driven and
     non-dependent on the RegionInfo analysis. [Same as before, this
     does not need to happen right away.]
  3) Scan the LLVM source code for uses of ScalarEvolution or reasoning
     about the execution of basic blocks [this includes thing like loop
     trip count queries]. These are possible candidates that might
     profit from the knowledge contained in a "Scop" object.
  4) Start an API that translates (simple) queries from the LLVM passes
     to lookups in a Scop. The LLVM pass should never "see" the Scop
     object or anything related for that matter. It will only require a
     "PolyhedralInfo" pass and query it.
  5) Use the above API to augment the information available at the
     points identified in 3), but only if the available information is
     not sufficient to apply the intended transformation.
  6) Evaluate the impact on compile and runtime for each pass that was
     augmented. Check how often (and for which kind of codes) the
     polyhedral information was queried and how often it allowed a
     transformation.
  7) Go back to 3 but now look for passes/opportunities that would need
     dependence information, thus the DependenceInfo pass. Then proceed
     with 4), 5) and 6) for dependences.

Note that not all points are ironed out and it is possibly to much for
one GSoC (or maybe to little, who knows). In any case, I think this
would be a good way to proceed with this work.

I am looking forward to comments or questions from you but also others in
the LLVM or Polly community.

Cheers,
  Johannes
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 213 bytes
Desc: Digital signature
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160321/81c2976a/attachment.sig>

On Mon, Mar 21, 2016 at 4:05 PM, Johannes Doerfert <
doerfert at cs.uni-saarland.de> wrote:
> Hey Utpal,
>
> First of, I think you made nice process here and have some very good
> ideas of what we could do in the future.
>
> [NOTE: I CC'ed some people that have shown interest in this topic but I
> might have forgotten some, therefor I also added the llvm-dev list.]
>
Thank you! I would like to have some comments from LLVM developers on how
we can extend Loop Vectorizer using a better dependence analysis. Please
feel free to share your views.

> For the upcoming GSoC proposal we should slow down a little bit and
> reevaluate our goals. After talking to a couple of LLVM and Polly folks
> at EuroLLVM last week, I hope to have a fairly good idea of how to
> proceed. To this end, I will give you my personal road map that might be
> a good start for the proposal too, though it is not the only way we
> could do this:
>
Thats nice of you, Thank you.

>   1) Make ScopInfo & DependenceInfo function passes to avoid the
>      RegionPassManager for these Polly analysis parts. [This doesn't
>      need to be the first step but it should be done at some point.]
>
I also think this is the most important step for this project.

>   2) Create a secondary ScopDetection & ScopInfo that is restricted to
>      analyze a single loop. We might just create a dummy region for this
>      loop and use the original ScopDetection & ScopInfo. The goal is to
>      make (this secondary) ScopDetection & ScopInfo demand driven and
>      non-dependent on the RegionInfo analysis. [Same as before, this
>      does not need to happen right away.]
>
 Ok.

  3) Scan the LLVM source code for uses of ScalarEvolution or
reasoning
>      about the execution of basic blocks [this includes thing like loop
>      trip count queries]. These are possible candidates that might
>      profit from the knowledge contained in a "Scop" object.
>
Are you suggesting that such pattern could be a possible client for Polly
as an Analysis pass?
I have not thought about them right now, but yes we can include them in the
proposal as well.

  4) Start an API that translates (simple) queries from the LLVM
passes
>      to lookups in a Scop. The LLVM pass should never "see" the
Scop
>      object or anything related for that matter. It will only require a
>      "PolyhedralInfo" pass and query it.
>
I do agree with you here. We need to separate out the interface(API) from
LLVM.

>   5) Use the above API to augment the information available at the
>      points identified in 3), but only if the available information is
>      not sufficient to apply the intended transformation.
>
That makes sense. We can fall-back to Polly only when needed.

>   6) Evaluate the impact on compile and runtime for each pass that was
>      augmented. Check how often (and for which kind of codes) the
>      polyhedral information was queried and how often it allowed a
>      transformation.
>
I think this will be one of the criteria for a successful implementation of
the proposal.

>   7) Go back to 3 but now look for passes/opportunities that would need
>      dependence information, thus the DependenceInfo pass. Then proceed
>      with 4), 5) and 6) for dependences.
>
Yes, possible clients are Loop Vectorizer, Loop Versioning, LNO, etc

> Note that not all points are ironed out and it is possibly to much for
> one GSoC (or maybe to little, who knows). In any case, I think this
> would be a good way to proceed with this work.
>
> I am looking forward to comments or questions from you but also others in
> the LLVM or Polly community.
>
>
> Cheers,
>   Johannes
>
> Thank you for your suggestions. Looking forward for more comments from the
LLVM and Polly community.

Regards,
Utpal Bora
> --
> You received this message because you are subscribed to the Google Groups
> "Polly Development" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to polly-dev+unsubscribe at googlegroups.com.
> For more options, visit https://groups.google.com/d/optout.
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160321/d8842a5c/attachment.html>

Hi Johannes,

On Mon, Mar 21, 2016 at 6:35 PM, Johannes Doerfert <
doerfert at cs.uni-saarland.de> wrote:
> Hey Utpal,
>
> First of, I think you made nice process here and have some very good
> ideas of what we could do in the future.
>
> [NOTE: I CC'ed some people that have shown interest in this topic but I
> might have forgotten some, therefor I also added the llvm-dev list.]
>
> For the upcoming GSoC proposal we should slow down a little bit and
> reevaluate our goals. After talking to a couple of LLVM and Polly folks
> at EuroLLVM last week, I hope to have a fairly good idea of how to
> proceed. To this end, I will give you my personal road map that might be
> a good start for the proposal too, though it is not the only way we
> could do this:
>
>   1) Make ScopInfo & DependenceInfo function passes to avoid the
>      RegionPassManager for these Polly analysis parts. [This doesn't
>      need to be the first step but it should be done at some point.]
>   2) Create a secondary ScopDetection & ScopInfo that is restricted to
>      analyze a single loop. We might just create a dummy region for this
>      loop and use the original ScopDetection & ScopInfo. The goal is to
>      make (this secondary) ScopDetection & ScopInfo demand driven and
>      non-dependent on the RegionInfo analysis. [Same as before, this
>      does not need to happen right away.]
>
I really like this direction. In general, we may want to decouple the
ScopDetection/ScopInfo construction logic from the pass logic, such that we
can run the logic ScopDetection and ScopInfo construction in a function
pass, call graph scc pass, or even a loop pass.

For 1), can we always construct a whole function Scop (excluding the entry
block which contains allocas)?

Thanks
Hongbin


>   3) Scan the LLVM source code for uses of ScalarEvolution or reasoning
>      about the execution of basic blocks [this includes thing like loop
>      trip count queries]. These are possible candidates that might
>      profit from the knowledge contained in a "Scop" object.
>   4) Start an API that translates (simple) queries from the LLVM passes
>      to lookups in a Scop. The LLVM pass should never "see" the
Scop
>      object or anything related for that matter. It will only require a
>      "PolyhedralInfo" pass and query it.
>   5) Use the above API to augment the information available at the
>      points identified in 3), but only if the available information is
>      not sufficient to apply the intended transformation.
>   6) Evaluate the impact on compile and runtime for each pass that was
>      augmented. Check how often (and for which kind of codes) the
>      polyhedral information was queried and how often it allowed a
>      transformation.
>   7) Go back to 3 but now look for passes/opportunities that would need
>      dependence information, thus the DependenceInfo pass. Then proceed
>      with 4), 5) and 6) for dependences.
>
> Note that not all points are ironed out and it is possibly to much for
> one GSoC (or maybe to little, who knows). In any case, I think this
> would be a good way to proceed with this work.
>
> I am looking forward to comments or questions from you but also others in
> the LLVM or Polly community.
>
> Cheers,
>   Johannes
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160323/acd04f3e/attachment-0001.html>

On 03/23, Hongbin Zheng wrote:
> Hi Johannes,
> 
> On Mon, Mar 21, 2016 at 6:35 PM, Johannes Doerfert <
> doerfert at cs.uni-saarland.de> wrote:
> 
> > Hey Utpal,
> >
> > First of, I think you made nice process here and have some very good
> > ideas of what we could do in the future.
> >
> > [NOTE: I CC'ed some people that have shown interest in this topic
but I
> > might have forgotten some, therefor I also added the llvm-dev list.]
> >
> > For the upcoming GSoC proposal we should slow down a little bit and
> > reevaluate our goals. After talking to a couple of LLVM and Polly
folks
> > at EuroLLVM last week, I hope to have a fairly good idea of how to
> > proceed. To this end, I will give you my personal road map that might
be
> > a good start for the proposal too, though it is not the only way we
> > could do this:
> >
> >   1) Make ScopInfo & DependenceInfo function passes to avoid the
> >      RegionPassManager for these Polly analysis parts. [This
doesn't
> >      need to be the first step but it should be done at some point.]
> >   2) Create a secondary ScopDetection & ScopInfo that is
restricted to
> >      analyze a single loop. We might just create a dummy region for
this
> >      loop and use the original ScopDetection & ScopInfo. The goal
is to
> >      make (this secondary) ScopDetection & ScopInfo demand driven
and
> >      non-dependent on the RegionInfo analysis. [Same as before, this
> >      does not need to happen right away.]
> >
> I really like this direction. In general, we may want to decouple the
> ScopDetection/ScopInfo construction logic from the pass logic, such that we
> can run the logic ScopDetection and ScopInfo construction in a function
> pass, call graph scc pass, or even a loop pass.
Totally agreed. Some kind of ScopBuilder interface that can be queried
would be perfect. Additionally a DependenceBuilder.

I would imagine something along the lines of:


   Passes:   ScopInfo <-----------[depends]----------- DependenceInfo
                 |                                              |
             [queries]                                      [queries]
                 |                                              |
                 V                                              V
Interface:  ScopBuilder                          ------ DependenceBuilder
              A  |                               |              |       A
              |  |                               |          [creates]   |
              |  |                               |              |       |
              |  |                               |              V       |
  Objects:    |  |--[creates]--> Scop <--[uses]--|         Dependences  |
              |                    |                            |       |
              |-----[queries]--|   |-----[uses]--| |---[uses]---|       |
                               |                 V V                    |
New Pass/Interface:            |----------- PolyhedralInfo --[queries]--|
                                                  A
                                                  |
                                                  |
                                      [non-polyhedral queries]
                                                  |
                                                  |
                                           **LLVM Passes**
> For 1), can we always construct a whole function Scop (excluding the entry
> block which contains allocas)?
We could even with allocas ;)
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 213 bytes
Desc: Digital signature
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160324/72ccf5ef/attachment.sig>