<div dir="ltr"><div><span style="font-family:arial,sans-serif;font-size:13px">Errata:</span></div><div><span style="font-family:arial,sans-serif;font-size:13px"><br></span></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">C1 (false) : WAW - S3->S1</span></blockquote><div><br></div><div>should read</div><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">C1 (false) : RAW - S3->S1</span> </blockquote><div><br></div><div>My apologies.</div><div><br></div><div>Snehasish </div></div><div class="gmail_extra"><br><br>
<div class="gmail_quote">On Fri, Dec 27, 2013 at 1:38 PM, 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>