llvm dev - Aug 2017 - Dependence analysis - missing loop-carried dependencies?

Hi,

I'm trying to do some (loop-carried) dependence analysis using LLVM, but
I'm confused by the results I'm getting. For example, consider this
simple
C program:
int main(){
  for (int i = 0; i < 10; ++i) {
  }
  return 0;
}
I would expect that the loop comparison depends on the loop initialisation
and the loop update, however I only see a dependence to the loop
initialisation.
    %3 = load i32, i32* %i, align 4   --->   store i32 0, i32* %i, align 4
I don't see a dependence to `store i32 %8, i32* %i, align 4` as I would
have expected. Am I misunderstanding the dependence analysis or doing
something wrong?

Here's the IR, the code I'm using to find the dependencies, the command
I'm
running it with, and the full output:

; Function Attrs: noinline nounwind uwtable
define i32 @main() #0 {
  %1 = alloca i32, align 4
  %i = alloca i32, align 4
  store i32 0, i32* %1, align 4
  store i32 0, i32* %i, align 4
  br label %2

; <label>:2:                                      ; preds = %6, %0
  %3 = load i32, i32* %i, align 4
  %4 = icmp slt i32 %3, 10
  br i1 %4, label %5, label %9

; <label>:5:                                      ; preds = %2
  br label %6

; <label>:6:                                      ; preds = %5
  %7 = load i32, i32* %i, align 4
  %8 = add nsw i32 %7, 1
  store i32 %8, i32* %i, align 4
  br label %2

; <label>:9:                                      ; preds = %2
  ret i32 0
}

  bool runOnFunction(Function &F) override {
    DependenceInfo *depinfo        
&getAnalysis<DependenceAnalysisWrapperPass>().getDI();
    // check dependencies between each pair of instructions
    for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; I++) {
      for (inst_iterator J = I; J != E; J++) {
        std::unique_ptr<Dependence> infoPtr;
        infoPtr = depinfo->depends(&*I, &*J, true);
        Dependence *dep = infoPtr.get();
        if (dep != NULL && !dep->isInput()) {
          if (!dep->isLoopIndependent()) errs() << "[L]";
          if (dep->isConfused()) errs() << "[C]";
          dep->getDst()->print(errs(), false);
          errs() << "   ---> ";
          dep->getSrc()->print(errs(), false);
          errs() << "\n";
        }
      }
    }
    return false;
  }

  void getAnalysisUsage(AnalysisUsage &AU) const override {
    AU.addRequired<DependenceAnalysisWrapperPass>();
  }

$ clang -fno-inline -emit-llvm loop.c -c -o loop.bcr
$ opt -load ~/dev/llvm_install/lib/LLVMSimpleDG.so \
    -disable-inlining -loop-simplify -simpledg \
    < loop.bcr > loop.bc

    %3 = load i32, i32* %i, align 4   --->   store i32 0, i32* %i, align 4
    %7 = load i32, i32* %i, align 4   --->   store i32 0, i32* %i, align 4
    store i32 %8, i32* %i, align 4   --->   store i32 0, i32* %i, align 4
    store i32 %8, i32* %i, align 4   --->   %3 = load i32, i32* %i, align 4
    store i32 %8, i32* %i, align 4   --->   %7 = load i32, i32* %i, align 4
[L] store i32 %8, i32* %i, align 4   --->   store i32 %8, i32* %i, align 4

Thank you for your help,

Shaun

On 3 August 2017 at 15:57, Shaun Steenkamp <shauncs.s at gmail.com>
wrote:
> I'm trying to do some (loop-carried) dependence analysis using LLVM,
but
> I'm confused by the results I'm getting. For example, consider this
simple
> C program:
> int main(){
>   for (int i = 0; i < 10; ++i) {
>   }
>   return 0;
> }
> I would expect that the loop comparison depends on the loop initialisation
> and the loop update, however I only see a dependence to the loop
> initialisation.
>     %3 = load i32, i32* %i, align 4   --->   store i32 0, i32* %i, align
4
> I don't see a dependence to `store i32 %8, i32* %i, align 4` as I would
> have expected. Am I misunderstanding the dependence analysis or doing
> something wrong?
For the archives (in case someone stumbles upon this via google):

I was getting confusing results because I foolishly was forgetting to
run a lot of basic/essential LLVM passes.

Running with
  opt -disable-inlining -mem2reg -loop-simplify -loop-rotate
-simplifycfg -instcombine -indvars
gave good results for a loop like this:
  int A[11];
  for (int i = 0; i < 10; ++i) {
    A[i+1] = A[i];
  }

I have since found that Polly [1] is much more suitable for my needs,
so I'm now using that instead.

Shaun

[1]: https://polly.llvm.org/

On Wed, Aug 9, 2017, at 14:33, Shaun Steenkamp via llvm-dev
wrote:
> On 3 August 2017 at 15:57, Shaun Steenkamp <shauncs.s at gmail.com>
wrote:
> > I'm trying to do some (loop-carried) dependence analysis using
LLVM, but
> > I'm confused by the results I'm getting. For example, consider
this simple
> > C program:
> > int main(){
> >   for (int i = 0; i < 10; ++i) {
> >   }
> >   return 0;
> > }
> > I would expect that the loop comparison depends on the loop
initialisation
> > and the loop update, however I only see a dependence to the loop
> > initialisation.
> >     %3 = load i32, i32* %i, align 4   --->   store i32 0, i32* %i,
align 4
> > I don't see a dependence to `store i32 %8, i32* %i, align 4` as I
would
> > have expected. Am I misunderstanding the dependence analysis or doing
> > something wrong?
> 
> For the archives (in case someone stumbles upon this via google):
> 
> I was getting confusing results because I foolishly was forgetting to
> run a lot of basic/essential LLVM passes.
> 
> Running with
>   opt -disable-inlining -mem2reg -loop-simplify -loop-rotate
> -simplifycfg -instcombine -indvars
> gave good results for a loop like this:
>   int A[11];
>   for (int i = 0; i < 10; ++i) {
>     A[i+1] = A[i];
>   }
> 
> I have since found that Polly [1] is much more suitable for my needs,
> so I'm now using that instead.
Nice to hear!

Best,
Tobias