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>
Errata: C1 (false) : WAW - S3->S1 should read C1 (false) : RAW - S3->S1 My apologies. Snehasish On Fri, Dec 27, 2013 at 1:38 PM, Snehasish Kumar <ska124 at sfu.ca> wrote:> 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/b4ca2ff3/attachment.html>
All-pairs testing is correct, in that it is conservative; it never fails to report an existing dependence. Your complaint is, essentially, that all-pair dependence testing reports too many dependences, 'cause it doesn't take control flow into account. True! Hence the motivation for guiding analysis using SSA. It's also faster to avoid testing all O(n^2) pairs. There are certainly other analysis and xform passes that would benefit from good dependence analysis, but I don't think anyone is using it yet. Preston On Fri, Dec 27, 2013 at 10:38 AM, Snehasish Kumar <ska124 at sfu.ca> wrote:> 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/14673583/attachment.html>
On 12/27/2013 07:38 PM, Snehasish Kumar wrote:> 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.Hi Snehasish, you may want to look at polly.llvm.org. It has a very detailed dependence analysis that also takes into accounts control flow conditions. (Such kind of analysis are important e.g. when generating GPU code, but also for other more complex loop transformations). Cheers, Tobias
On 01/02/2014 03:47 PM, Tobias Grosser wrote:> On 12/27/2013 07:38 PM, Snehasish Kumar wrote: >> 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. > > Hi Snehasish, > > you may want to look at polly.llvm.org. It has a very detailed > dependence analysis that also takes into accounts control flow > conditions. (Such kind of analysis are important e.g. when generating > GPU code, but also for other more complex loop transformations).I just realized you tried to do so and there are some open questions that most likely have blocked you. Sorry for not replying to those previously. I will look into the WAR problems later tonight. Please ping me directly if you are blocked by any problems. Cheers, Tobias