[LLVMdev] Array Dependence Analysis

[Wojciech Matyjewicz]

Hi,

> Cool!  I think the most critical part of this is to get a good  
> interface for dependence analysis.  There are lots of interesting  
> implementations that have various time/space tradeoffs.
> 
> For example, it would be great if Omega was available as an option,  
> even if the compiler didn't use it by default.  This argues for making  
> dependence analysis implementations pluggable like alias analyses.

Yes, I also thought about it that way. I think we may look at the
dependence analysis in LLVM at three levels (from the lowest to the
highest one):

1) Testing for dependence given two sequences of GEP indices assuming
that base pointers are the same. The indices could have a SCEV form or
even be preprocessed to something simpler (affine expressions for example).

2) Testing for dependence of two instructions (that access memory). It
would use alias analysis to answer some queries immediately, or to check
whether two GEP base pointers equal. If the latter is the case, 1) would
be used to check for dependences.

3) Complex queries (for example: does the given loop carry dependence?).
It would use 2) and summarize its results.

Only the first level could be pluggable allowing to interchange or chain
core dependency testing techniques. I think there will be no use in
making pluggable the higher ones (please, correct me if I am wrong).
This approach would require to divide the analysis structure into two
parts, say; DependenceAnalysis and IndexingTester.

That said, I must admit I haven't made it that way in my prototype. I
have it in mind, but I'm currently trying to keep things simple and just
to check whether the precision of my implementation is worth anything.

> Sounds good.  If you have the interface nailed down, it would be good  
> to post what the query interface looks like.  Vikram and others have a  
> lot of experience with dependence analysis and know what sorts of  
> queries various clients are interested in.  They can help give  
> feedback on the direction you're pursuing independent of the  
> implementation.

Ok. I'll post it when it crystallizes (what should happen soon).

> I'd suggest looking at:
> 
> Using the chains of recurrences algebra for data dependence testing  
> and induction variable substitution
> MS Thesis, Johnie Birch
> 
> Array Data Dependence Testing with the Chains of Recurrences Algebra
> http://citeseer.ist.psu.edu/vanengelen04array.html
> 
> An empirical evaluation of chains of recurrences for array dependence  
> testing
> http://doi.acm.org/10.1145/1152154.1152198

I've read the second one, but am not sure if it's easy to implement if
overflow and unknown signedness are taken into account. For now, I will
stick to the classical Banerjee test. If time allows I'll return to the
article.

>>> From my experience I can say it's essential to use a precise alias
>> analysis as the base for the array dependence analysis. Fortunately,
>> using Data Structure or Andersen's AA for the whole program can  
>> provide
>> really good results.
> 
> Yep, but any particular dep analysis implementation should just  
> require AliasAnalysis instead of a specific implementation.  This lets  
> the client (e.g. llvm-gcc) decide what passes to plug together.

You're right. From the implementation point of view the choice of alias
analysis doesn't matter at all.

Wojtek