[LLVMdev] Loop carried dependence analysis?

[Preston Briggs]

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
>     {...}
> }
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20121109/d6a68dc6/attachment.html>