[LLVMdev] Loop carried dependence analysis?

[erkan diken]

Hi Preston,

I am trying to use DA as well. I used your example and commands that you
wrote in order to get DA information.

However, it does not report any dependence info.

I am wondering whether your local copy differs from the one on the
repository ?

Thanks.
Erkan.



On Fri, Nov 9, 2012 at 2:40 PM, Preston Briggs <preston.briggs at gmail.com>wrote:

> Hi,
>
> The DependenceAnalysis pass will find loop-carried dependences. However,
> it is a conservative analysis and will sometimes suggest there may be more
> dependences than actually exist. In your example, I expect the analysis is
> confused for some reason and is returning the default confused response.
> You could test it using the isConfused() method. Note that the DVEntry::ALL
> direction is always valid. A distance of NULL is similarly valid; it merely
> indicates that the analysis couldn't figure out a fixed distance (or
> perhaps one doesn't exit).
>
> In your example, there's certainly a dependence from the load to the
> store. I'd expect it to report a consistent, loop-carried anti dependence
> with distance -1, and it does for me. Here's the test program I used:
>
> void zip(double *arr) {
>   for (int i = 1; i < 100; i++) {
>     arr[i] = arr[i-1];
>   }
> }
>
>
> and here's how I compiled things:
>
> clang -c -emit-llvm zip.c -o zip.bc
> opt -basicaa -mem2reg -simplifycfg -loop-simplify -loop-rotate
> -simplifycfg -instcombine -indvars -da -analyze zip.bc
>
>
> Some of the passes may not be necessary, but they're what I use by
> default. In this case, -analyze tests 3 pairs of memory references, the
> load against itself, the load versus the store, and the store against
> itself. It reports:
>
> da analyze - consistent input [0|<]!
> da analyze - consistent anti [-1]!
> da analyze - consistent output [0|<]!
>
>
> Hope this helps,
> Preston
>
>
>
> Hello everyone,
>>
>> I intend to build a pass to profile some benchmarks for loop carried
>> dependencies.  At first I tried looking at LoopDependenceAnalysis.{h,cpp}
>> but the files were removed for some reason.  So I continued with the
>> DependenceAnalysis pass.  But the flow, anti dependence, etc methods are
>> only reporting sequential and not loop carried dependencies.  Does LLVM
>> support loop carried dependency analysis?
>>
>> In addition, the distance and direction for dependent instructions always
>> have invalid values; Dependence::getDirection() returns DVEntry::ALL which
>> is the default value and Dependence::getDistance always returns null.
>>
>> E.g, for this input loop:
>> for (int i = 1; i < 100; i++)
>> {
>>     arr[i] = arr[i-1];
>> }
>>
>> This dependence is reported:
>> %1 = load i32* %arrayidx.i, align 4  --->   store i32 %1, i32*
>> %arrayidx2.i, align 4
>>
>> And the following is the code to output distance and directions.
>> nestingLevel is the innermost loop depth, 1 in this case.
>>
>> Dependence* dependence = dependenceAnalysis->depends(instructions[src],
>> instructions[dst], true);
>> if (dependence)
>> {
>>     unsigned direction = dependence->getDirection(nestingLevel); //
>> Returns DVEntry::ALL
>>     if (const SCEV* scev = dependence->getDistance(nestingLevel))  //
>> Returns null
>>     {...}
>> }
>>
>>
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>
>


-- 
Best Regards,
Erkan Diken
------------------
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20121112/f3ab545e/attachment.html>