Johannes Doerfert via llvm-dev
2016-Mar-24 09:05 UTC
[llvm-dev] Polly as an Analysis pass in LLVM
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>
Utpal Bora via llvm-dev
2016-Mar-24 10:51 UTC
[llvm-dev] Polly as an Analysis pass in LLVM
Hi Johannes, This is interesting. I will include a block diagram in the proposal. Thanks a lot. Regards, Utpal Bora Ph.D. Scholar +917032002001 Computer Science & Engineering IIT Hyderabad On Thu, Mar 24, 2016 at 2:35 PM, Johannes Doerfert < doerfert at cs.uni-saarland.de> wrote:> 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 ;) > > -- > 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/20160324/79579447/attachment.html>
Hongbin Zheng via llvm-dev
2016-Mar-25 02:23 UTC
[llvm-dev] Polly as an Analysis pass in LLVM
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 On Thu, Mar 24, 2016 at 5:05 PM, Johannes Doerfert < doerfert at cs.uni-saarland.de> wrote:> 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 -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20160325/18d96106/attachment.html>
Utpal Bora via llvm-dev
2016-Mar-25 08:07 UTC
[llvm-dev] Polly as an Analysis pass in LLVM
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. Regards, Utpal Bora Ph.D. Scholar +917032002001 Computer Science & Engineering IIT Hyderabad On Fri, Mar 25, 2016 at 7:53 AM, Hongbin Zheng <etherzhhb at gmail.com> wrote:> 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 > > > > On Thu, Mar 24, 2016 at 5:05 PM, Johannes Doerfert < > doerfert at cs.uni-saarland.de> wrote: > >> 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 -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20160325/fa8b55b9/attachment.html>