[LLVMdev] Using DependenceAnalysis::depends

[Snehasish Kumar]

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>