Dependence analysis - missing loop-carried dependencies?

Project Infrastructure LLVM Dev List Archives
1

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

2

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/

3

Nice to hear!

Best,
Tobias