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

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

Hi Johannes,

Hi Johannes,

> 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 :wink:

Hi Johannes,

This is interesting. I will include a block diagram in the proposal. Thanks a lot.

In the design the LLVM passes always directly communicate with PolyhedralInfo, this requires Polly tightly integrate in to LLVM.

If we do not want a tight integration, we can do the following:

  1. Introduce an abstract memory dependency query interface, like AliasAnalysis
  2. I remember LLVM had already have dependency analysis, this can be the default implementation of the memory dependency query interface. Or the default implementation can be a “may depend” analysis.
  3. PolyhedralInfo is yet another implementation of memory dependency analysis.

That is:

LLVM Passes → DependencyAnalysis —> Default implementation

-—> Implementation in LLVM

----> Polyhedral dependency analysis in Polly

Hi ether,

Your suggestion is appropriate with respect to LLVM framework.

However, I am not aware of such a common interface for Dependence Analysis as there is one for AliasAnalysis.

The current plan is to provide the new Dependence Analysis interface that can be used when the other analysis engines fail to provide a concrete result. I do not want to overestimate things by proposing such a common framework for Dependence analysis in LLVM.

The integration will not be tight as we can return empty analysis result if Polly is not compiled with LLVM tools.

Hi Utpal,

Yes, we do not need to drive ourself crazy and do everything in this GSoC. We can build a tight integration in GSoC and improve later when necessary.

Thanks
Hongbin