[LLVMdev] Using DependenceAnalysis::depends

[Preston Briggs]

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>