[LLVMdev] Array Dependence Analysis

[Chris Lattner]

On Mar 19, 2008, at 5:35 PM, Wojciech Matyjewicz wrote:

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

Makes sense, sounds fun!

-Chris