A bug in DependenceAnalysis?

Hello llvm-dev,

I’m running a pass that uses the result of llvm::DependenceAnalysisWrapperPass to compute the dependencies between all instructions of a loop. I have the following two examples of code I wish to analyse:

example A:


void move_one(int *A, unsigned n) {
for (unsigned i = 0; i < n-1; ++i) {
A[i] = A[i + 1];
}
}

and example B:


void move_one_alt(int *A, unsigned n) {
int *B = A + 1;
for (unsigned i = 0; i < n-1; ++i) {
A[i] = B[i];
}
}

I would expect that I get the same result for both A and B, namely a loop carried anti (WAR) dependence from the generated load instruction to the generated store instruction. This should be the case, because on iteration i+1 the loop is writing to the element that has been read in the previous iteration - iteration i.

However, in example A I get a loop carried flow (RAW) dependence from the store instruction to the load instruction, while in example B I don’t get any dependence at all.

Am I missing something, or is the result wrong?

Thanks,

  • Stan

Hi Stan,

in both cases I get a consistent anti result. Can you show us the command lines you’re using? Which version of llvm is this?

Best,
Philip

Hi Philip,

Thanks for checking!

I’m running my own Foo pass that registers DependenceAnalysisWrapperPass as a prerequisite and then I run it like so:

opt -load libfoo.so -foo example.bc

This is LLVM 3.9.

Cheers,

  • Stan

Hi Stan,

can you share your example.bc? Can you reproduce your issue with llvm 4.0 or, better even, trunk?

Cheers,
Philip

Hi Philip,

I forgot to mention that I was ignoring loop-independent dependences. If I don’t I get an inconsistent, ordered, anti, loop-independent dependence and an inconsistent, ordered, flow, loop-carried dependence for example A. At the same time I get just a consistent, ordered, anti, loop-independent dependence for example B.

Here’s the .ll code for example A:

; Function Attrs: nounwind uwtable
define void @_Z8move_onePij(i32*, i32) #3 {
br label %3

; :3: ; preds = %13, %2
%.0 = phi i32 [ 0, %2 ], [ %14, %13 ]
%4 = sub i32 %1, 1
%5 = icmp ult i32 %.0, %4
br i1 %5, label %6, label %15

; :6: ; preds = %3
%7 = add i32 %.0, 1
%8 = zext i32 %7 to i64
%9 = getelementptr inbounds i32, i32* %0, i64 %8
%10 = load i32, i32* %9, align 4
%11 = zext i32 %.0 to i64
%12 = getelementptr inbounds i32, i32* %0, i64 %11
store i32 %10, i32* %12, align 4
br label %13

; :13: ; preds = %6
%14 = add i32 %.0, 1
br label %3

; :15: ; preds = %3
ret void
}

Here’s the .ll code for example B:

; Function Attrs: nounwind uwtable
define void @_Z12move_one_altPij(i32*, i32) #3 {
%3 = getelementptr inbounds i32, i32* %0, i64 1
br label %4

; :4: ; preds = %13, %2
%.0 = phi i32 [ 0, %2 ], [ %14, %13 ]
%5 = sub i32 %1, 1
%6 = icmp ult i32 %.0, %5
br i1 %6, label %7, label %15

; :7: ; preds = %4
%8 = zext i32 %.0 to i64
%9 = getelementptr inbounds i32, i32* %3, i64 %8
%10 = load i32, i32* %9, align 4
%11 = zext i32 %.0 to i64
%12 = getelementptr inbounds i32, i32* %0, i64 %11
store i32 %10, i32* %12, align 4
br label %13

; :13: ; preds = %7
%14 = add i32 %.0, 1
br label %4

; :15: ; preds = %4
ret void
}

Can you please check whether the anti dependeces that you get are loop-carried or loop-independent?

Thanks,

  • Stan

Hi Stan,

in the first example, I get an “anti [*|<]” result. DA doesn’t look through zext expressions, so it needs to overapproximate.

In the second example I get a “consistent anti [0|<]” result, which is wrong. The cause of this bug is that DA falsely ignores the base pointer, and only looks at the indices.

Please file a bug report for this, including a reproducing example, and put me on CC.

Cheers,
Philip

Hi Philip,

Done. See https://bugs.llvm.org/show_bug.cgi?id=33567.

Cheers,

  • Stan