<div dir="ltr">All-pairs testing is correct, in that it is conservative; it never fails to report an existing dependence.<div><br></div><div>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.</div>
<div><br></div><div>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.</div><div><br></div><div>Preston</div><div><br></div>
</div><div class="gmail_extra"><br><br><div class="gmail_quote">On Fri, Dec 27, 2013 at 10:38 AM, Snehasish Kumar <span dir="ltr"><<a href="mailto:ska124@sfu.ca" target="_blank">ska124@sfu.ca</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div dir="ltr"><div>Hi Preston,</div><div><br></div>Thank you for the prompt response.<div class="im"><div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
<span style="font-family:arial,sans-serif;font-size:13px">You can use DependenceAnalysis to get the info you want by expensively testing all pairs of memory references.</span></blockquote><div><br></div></div><div>Isn't all pairs testing incorrect in the sense that a pair may only exist for a certain path? Consider the following example.</div>
<div><br></div><div>A[i] = 42; // S1</div><div>if( condition ) // C1</div><div>{</div><div> A[i] = 20; // S2</div><div>}</div><div>B[i] = A[i]; // S3</div><div><br></div><div>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.</div>
<div>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:</div><div><br></div><div>C1 (true) : WAW - S2->S1 , RAW - S3->S2</div>
<div>C1 (false) : WAW - S3->S1</div><div><br></div><div>So then it seems to me that building the dependence graph is essential.</div><div><br></div><div>Are there no other Analysis/Transforms which require this type of information? </div>
<div>I looked at AESOP (<a href="http://aesop.ece.umd.edu/doc/aesop-white-paper.pdf" target="_blank">http://aesop.ece.umd.edu/doc/aesop-white-paper.pdf</a>) which implements an autoparallelization framework and it seems they would need to do similar checks, the page hosting the code is currently offline.</div>
<div><br></div><div>Thanks,</div><div>Snehasish</div></div><div class="HOEnZb"><div class="h5"><div class="gmail_extra"><br><br><div class="gmail_quote">On Fri, Dec 27, 2013 at 12:24 PM, Preston Briggs <span dir="ltr"><<a href="mailto:preston.briggs@gmail.com" target="_blank">preston.briggs@gmail.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">Hi,<div><br></div><div>There's no implementation yet of the dependence graph builder.</div><div><br>
</div><div>You can use DependenceAnalysis to get the info you want by expensively testing all pairs of memory references.</div>
<div><br></div><div>What you call "intra iteration" are "loop-independent" dependences, and are tested at the same time as the loop-carried dependences.</div><div><br></div><div>(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.)</div>
<div><br></div><div>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.</div>
<span><font color="#888888">
<div><br></div><div>Preston</div><div><br></div><div><br></div></font></span></div><div><div><div class="gmail_extra"><br><br><div class="gmail_quote">On Fri, Dec 27, 2013 at 8:46 AM, Snehasish Kumar <span dir="ltr"><<a href="mailto:ska124@sfu.ca" target="_blank">ska124@sfu.ca</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">Hi <div><br></div><div>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. </div>
<div><br></div><div>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 : <a href="https://sites.google.com/site/parallelizationforllvm/building-the-dependence-graph" target="_blank">https://sites.google.com/site/parallelizationforllvm/building-the-dependence-graph</a></div>
<div><br></div><div>Is there any existing implementation I can take a look at? </div><div>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?</div>
<div><br></div><div>Thanks,</div><div>Snehasish</div></div>
</blockquote></div><br></div>
</div></div></blockquote></div><br></div>
</div></div></blockquote></div><br></div>