[LLVMdev] Array Dependence Analysis

[Chris Lattner]

>> As part of the advanced compilers course semester project (at  
>> UIUC), we
>> are starting to implement array dependence analysis for LLVM.

Great!  This is something we've needed for a long time.

> I'm currently working on a similar project and hoping to finish it in
> about two weeks.

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.

> As for now, I'm focusing on the dependency analysis engine and publish
> only a simplistic interface (it only allows to check whether a loop
> carries a memory dependence). However, the engine is quite
> self-contained and should be easy to attach to a different interface.
> For instance, the engine will be able to find dependence direction
> vectors for an instruction pair.

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.

>> Any suggestion on features, tests and/or interface are welcome.

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

etc.

>> 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.

-Chris