[LLVMdev] Array Dependence Analysis

[Wojciech Matyjewicz]

Chris Lattner wrote:
> I'm fine with starting simple and generalizing it out from there.  I'd  
> actually recommend against trying to implement a maximally precise  
> dependence analyzer without a client.  With no client, there is no way  
> to test that you're getting correct results and whether the  
> improvements in precision are actually useful.
> 
> I'd suggest starting out with a simple checker, e.g. that handles  
> simple affine cases, and some client (a loop xform?).  This should be  
> enough to get the transformation working on simple loops, and when the  
> client is tested and working there, you can use it to evaluate whether  
> the precision improvements are worthwhile.

In fact, I've a client to test dependence analysis. It's a simple loop
parallelization pass. Basically, it tries to divide the set of
iterations into smaller sets and execute them in separate threads. The
loop is parallelized if it has appropriate shape (i.e. is rotated, has
canonical indvar), has known iteration count (at runtime) and doesn't
carry any dependence. The new dependence analysis is used to check if
there are no memory dependences. Register dependences are simpler to
detect as they are introduced only by the loop header PHI nodes. Some
register dependences can be eliminated (in case of scalar reduction, for
example). This pass is almost finished with some minor FIXMEs for corner
cases. If there is an interest I can share/contribute it soon. However,
I wouldn't expect much from it and would rather treat it as a toy.

After your advice, I am going to prepare (locally) custom tests for
llvm-test testsuite. The number of loops not carrying memory
dependences, or parallelizable ones can be a good measure of dependence
analysis precision. Comparing output of parallelized programs to the
original ones would, probably, help to check its correctness.

> If you're looking for a simple client, I'd suggest something like loop  
> reversal.

I think it would exercise dependence analysis in the same way as the
above pass. Off course, it's still worthy to implement it.
Unfortunately, I am not sure if I'll have time for it in the nearest
future. Maybe someone else is interested?:)

> Another transform that needs dependence analysis which would be even  
> more useful (but still very simple) is a "loops to memset/memcpy"  
> pass.  This optimization would speed up the 'viterbi' program in the  
> test suite a *lot* for the various 'history' loops.

Ok, but, unfortunately, as above...

Wojtek