[LLVMdev] DependenceAnalysis and PR14241

[Chandler Carruth]

Hey Preston,

I wanted to let you know that we found a really serious problem with
DependenceAnalysis in PR14241. In summary, DA seems to have a baked-in
assumption that the base pointer of the GEPs it inspects are loop
invariant. It appears to only do analysis on the subscripts.

This is especially important for LLVM because C++ code (compiled
through Clang) very frequently expresses loops as pointer loops rather
than indexed loops, and thus I would expect a large number of the
interesting dependence queries to actually require the subscript
analysis your pass currently does to additionally analyze any loop
variant base pointers. Such base pointers can essentially factor the
subscripts across two separate GEPs, so that may also be a bit tricky
to model correctly.

In trying to give you a nice, short test case, I also noticed that the
DA testing infrastructure has a deeply surprising limitation: it can
only handle dependence queries for stores in a loop which are
*followed* by a load. The PR in question (and I would imagine many
other common scenarios) actually take the form of a load followed by a
store. or some other more complex interaction of loads and stores.

I think it might make more sense to make your testing print routine
look at the full set of load/store pairs, regardless of sequencing.


Just to give you the flavor right away of the types of loop that led
to PR14241, and the utility of the testing strategy I mentioned, I
made a quick local patch to my tree. Then I have:

% cat PR14241.ll
; ModuleID = 'PR14241.ll'
target datalayout =
"e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128"
target triple = "x86_64-unknown-linux-gnu"

define void @f(i32* %s, i64 %size) {
entry:
  %end.idx = add i64 %size, -1
  %end.ptr = getelementptr inbounds i32* %s, i64 %end.idx
  br label %while.body

while.body:
  %phi.ptr = phi i32* [ %s, %entry ], [ %next.ptr, %while.body ]
  %src.ptr = getelementptr inbounds i32* %phi.ptr, i64 1
  %val = load i32* %src.ptr, align 4
  %dst.ptr = getelementptr inbounds i32* %phi.ptr, i64 0
  store i32 %val, i32* %dst.ptr, align 4
  %next.ptr = getelementptr inbounds i32* %phi.ptr, i64 1
  %cmp = icmp eq i32* %next.ptr, %end.ptr
  br i1 %cmp, label %exit, label %while.body

exit:
  ret void
}


With the old DependenceAnalysis testing I get:
% ./bin/opt -S -o - PR14241.ll -analyze -basicaa -da
Printing analysis 'Basic Alias Analysis (stateless AA impl)':
Pass::print not implemented for pass: 'Basic Alias Analysis (stateless
AA impl)'!
Printing analysis 'Dependence Analysis' for function 'f':

With my patch to the testing output:
% ./bin/opt -S -o - PR14241.ll -analyze -basicaa -da
Printing analysis 'Basic Alias Analysis (stateless AA impl)':
Pass::print not implemented for pass: 'Basic Alias Analysis (stateless
AA impl)'!
Printing analysis 'Dependence Analysis' for function 'f':
da analyze - none!


Note the "none" conclusion. There most certainly is a dependence
between the load and the store though. ;]


Let me know if I can help with fixing this, I'm really excited about
having proper dependence analysis in LLVM!
-Chandler