[LLVMdev] Array Dependence Analysis
sabre at nondot.org
Wed Mar 19 18:13:43 PDT 2008
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.
>> actually recommend against trying to implement a maximally precise
>> dependence analyzer without a client. With no client, there is no
>> 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
>> client is tested and working there, you can use it to evaluate
>> 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,
> example). This pass is almost finished with some minor FIXMEs for
> cases. If there is an interest I can share/contribute it soon.
> 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
> analysis precision. Comparing output of parallelized programs to the
> original ones would, probably, help to check its correctness.
Makes sense, sounds fun!
More information about the llvm-dev