Hi I want to analyse the memory dependencies which exist in a loop at an intra iteration as well as inter iteration (loop carried dependencies). I looked at the DependenceAnalysis implementation which returns a lot of the information I require (based on a prior AliasAnalysis pass), however I need to pass the Src and Dst instructions in program order. I was wondering how I can collect all the memory access pairs from the basic blocks within the CFG of the loop body which would allow me to know which pairs are RAW/WAR/WAW. It seems related to the approach outlined here : https://sites.google.com/site/parallelizationforllvm/building-the-dependence-graph Is there any existing implementation I can take a look at? It seems that the only the DependenceAnalysis::depends is only called in the dumpExampleDependence() function (checked using cscope). Is there no other module which uses this class? Thanks, Snehasish -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20131227/fb9a96a4/attachment.html>
Hi, There's no implementation yet of the dependence graph builder. You can use DependenceAnalysis to get the info you want by expensively testing all pairs of memory references. What you call "intra iteration" are "loop-independent" dependences, and are tested at the same time as the loop-carried dependences. (In the old days, people tried to say "inter" and "intra", but it was too confusing during talks. It was much clearer to say loop independent and loop carried.) I know of no other check-in code that uses DependenceAnalysis. Which is appropriate; it's not ready for use (that is, it's incorrect). I misunderstood how GEPs work, so it will sometimes miss existing dependences. Preston On Fri, Dec 27, 2013 at 8:46 AM, Snehasish Kumar <ska124 at sfu.ca> wrote:> Hi > > I want to analyse the memory dependencies which exist in a loop at an > intra iteration as well as inter iteration (loop carried dependencies). I > looked at the DependenceAnalysis implementation which returns a lot of the > information I require (based on a prior AliasAnalysis pass), however I need > to pass the Src and Dst instructions in program order. > > I was wondering how I can collect all the memory access pairs from the > basic blocks within the CFG of the loop body which would allow me to know > which pairs are RAW/WAR/WAW. It seems related to the approach outlined here > : > https://sites.google.com/site/parallelizationforllvm/building-the-dependence-graph > > Is there any existing implementation I can take a look at? > It seems that the only the DependenceAnalysis::depends is only called in > the dumpExampleDependence() function (checked using cscope). Is there no > other module which uses this class? > > Thanks, > Snehasish >-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20131227/5b7d503f/attachment.html>
Hi Preston, Thank you for the prompt response. You can use DependenceAnalysis to get the info you want by expensively> testing all pairs of memory references.Isn't all pairs testing incorrect in the sense that a pair may only exist for a certain path? Consider the following example. A[i] = 42; // S1 if( condition ) // C1 { A[i] = 20; // S2 } B[i] = A[i]; // S3 Testing for all pairs would indicate that there exists a WAR between S2 and S3 but it is only correct if C1 evaluates to true. Similarly, there may or may not be a WAW between S1 and S2. Thus to clearly indicate the possible paths I would like to generate something like: C1 (true) : WAW - S2->S1 , RAW - S3->S2 C1 (false) : WAW - S3->S1 So then it seems to me that building the dependence graph is essential. Are there no other Analysis/Transforms which require this type of information? I looked at AESOP (http://aesop.ece.umd.edu/doc/aesop-white-paper.pdf) which implements an autoparallelization framework and it seems they would need to do similar checks, the page hosting the code is currently offline. Thanks, Snehasish On Fri, Dec 27, 2013 at 12:24 PM, Preston Briggs <preston.briggs at gmail.com>wrote:> Hi, > > There's no implementation yet of the dependence graph builder. > > You can use DependenceAnalysis to get the info you want by expensively > testing all pairs of memory references. > > What you call "intra iteration" are "loop-independent" dependences, and > are tested at the same time as the loop-carried dependences. > > (In the old days, people tried to say "inter" and "intra", but it was too > confusing during talks. It was much clearer to say loop independent and > loop carried.) > > I know of no other check-in code that uses DependenceAnalysis. Which is > appropriate; it's not ready for use (that is, it's incorrect). I > misunderstood how GEPs work, so it will sometimes miss existing dependences. > > Preston > > > > > On Fri, Dec 27, 2013 at 8:46 AM, Snehasish Kumar <ska124 at sfu.ca> wrote: > >> Hi >> >> I want to analyse the memory dependencies which exist in a loop at an >> intra iteration as well as inter iteration (loop carried dependencies). I >> looked at the DependenceAnalysis implementation which returns a lot of the >> information I require (based on a prior AliasAnalysis pass), however I need >> to pass the Src and Dst instructions in program order. >> >> I was wondering how I can collect all the memory access pairs from the >> basic blocks within the CFG of the loop body which would allow me to know >> which pairs are RAW/WAR/WAW. It seems related to the approach outlined here >> : >> https://sites.google.com/site/parallelizationforllvm/building-the-dependence-graph >> >> Is there any existing implementation I can take a look at? >> It seems that the only the DependenceAnalysis::depends is only called in >> the dumpExampleDependence() function (checked using cscope). Is there no >> other module which uses this class? >> >> Thanks, >> Snehasish >> > >-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20131227/bedb7e09/attachment.html>
Hello Preston, can you elaborate what exactly is the problem with DependenceAnalysis or point me to a thread/bug report discussing it? Do you think that this will require a large effort? I would like to put some time on this and also on the graph dep. builder. César. 2013/12/27 Preston Briggs <preston.briggs at gmail.com>:> Hi, > > There's no implementation yet of the dependence graph builder. > > You can use DependenceAnalysis to get the info you want by expensively > testing all pairs of memory references. > > What you call "intra iteration" are "loop-independent" dependences, and are > tested at the same time as the loop-carried dependences. > > (In the old days, people tried to say "inter" and "intra", but it was too > confusing during talks. It was much clearer to say loop independent and loop > carried.) > > I know of no other check-in code that uses DependenceAnalysis. Which is > appropriate; it's not ready for use (that is, it's incorrect). I > misunderstood how GEPs work, so it will sometimes miss existing dependences. > > Preston > > > > > On Fri, Dec 27, 2013 at 8:46 AM, Snehasish Kumar <ska124 at sfu.ca> wrote: >> >> Hi >> >> I want to analyse the memory dependencies which exist in a loop at an >> intra iteration as well as inter iteration (loop carried dependencies). I >> looked at the DependenceAnalysis implementation which returns a lot of the >> information I require (based on a prior AliasAnalysis pass), however I need >> to pass the Src and Dst instructions in program order. >> >> I was wondering how I can collect all the memory access pairs from the >> basic blocks within the CFG of the loop body which would allow me to know >> which pairs are RAW/WAR/WAW. It seems related to the approach outlined here >> : >> https://sites.google.com/site/parallelizationforllvm/building-the-dependence-graph >> >> Is there any existing implementation I can take a look at? >> It seems that the only the DependenceAnalysis::depends is only called in >> the dumpExampleDependence() function (checked using cscope). Is there no >> other module which uses this class? >> >> Thanks, >> Snehasish > > > > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev >