[LLVMdev] DependenceAnalysis and PR14241

[Dan Gohman]

I hadn't reviewed this closely before, but it's actually overkill to use
DependenceAnalysis in LoopIdiomRecognize. LoopIdiomRecognize needs to do
the work to recognize a memmove pattern either way, and while it's nice to
use memcpy instead of memmove, (a) that's something that's nice to do in
general, not just in memmove calls recognized by LoopIdiomRecognizer, and
(b) Converting memcpy to memmove requires simple alias analysis, not
generalized loop dependence analysis.

It happens that LLVM's current AliasAnalysis API isn't quite flexible
enough for this; it doesn't handle dynamic sizes. However, one can manually
perform the alias analysis with the kind of SCEV code being discussed on
this thread.

Dan

On Fri, Nov 2, 2012 at 1:52 AM, Chandler Carruth <chandlerc at google.com>wrote:

> 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
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20121102/b080a5dc/attachment.html>