Using DependenceAnalysis::depends

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

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

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

Errata:

C1 (false) : WAW - S3->S1

should read

C1 (false) : RAW - S3->S1

My apologies.

Snehasish

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

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

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

Hello Preston,

can you elaborate what exactly is the problem with DependenceAnalysis
or point me to a thread/bug report discussing it? Do you think that
this will require a large effort? I would like to put some time on
this and also on the graph dep. builder.

César.

Here’s a thread that talk about the basic problems: http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20130701/179665.html
I think it’s a pretty big effort to fix it all, but I haven’t been able to put in any time on it, so I may be overly pessimistic.

Sebastian Pop wrote a delinearizer, so at least that part is done.
See [llvm] r194527 - delinearization of arrays

Preston