#include "llvm/Analysis/LoopPass.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/Instructions.h"
+#include "llvm/Support/Debug.h"
using namespace llvm;
LoopPass *llvm::createLoopDependenceAnalysisPass() {
memrefs.push_back(i);
}
+static bool IsLoadOrStoreInst(Value *I) {
+ return isa<LoadInst>(I) || isa<StoreInst>(I);
+}
+
+static Value *GetPointerOperand(Value *I) {
+ if (LoadInst *i = dyn_cast<LoadInst>(I))
+ return i->getPointerOperand();
+ if (StoreInst *i = dyn_cast<StoreInst>(I))
+ return i->getPointerOperand();
+ assert(0 && "Value is no load or store instruction!");
+ // Never reached.
+ return 0;
+}
+
//===----------------------------------------------------------------------===//
// Dependence Testing
//===----------------------------------------------------------------------===//
bool LoopDependenceAnalysis::depends(Value *src, Value *dst) {
assert(isDependencePair(src, dst) && "Values form no dependence pair!");
+ DOUT << "== LDA test ==\n" << *src << *dst;
+
+ // We only analyse loads and stores; for possible memory accesses by e.g.
+ // free, call, or invoke instructions we conservatively assume dependence.
+ if (!IsLoadOrStoreInst(src) || !IsLoadOrStoreInst(dst))
+ return true;
+
+ Value *srcPtr = GetPointerOperand(src);
+ Value *dstPtr = GetPointerOperand(dst);
+ const Value *srcObj = srcPtr->getUnderlyingObject();
+ const Value *dstObj = dstPtr->getUnderlyingObject();
+ const Type *srcTy = srcObj->getType();
+ const Type *dstTy = dstObj->getType();
+
+ // For now, we only work on (pointers to) global or stack-allocated array
+ // values, as we know that their underlying memory areas will not overlap.
+ // MAYBE: relax this and test for aliasing?
+ if (!((isa<GlobalVariable>(srcObj) || isa<AllocaInst>(srcObj)) &&
+ (isa<GlobalVariable>(dstObj) || isa<AllocaInst>(dstObj)) &&
+ isa<PointerType>(srcTy) &&
+ isa<PointerType>(dstTy) &&
+ isa<ArrayType>(cast<PointerType>(srcTy)->getElementType()) &&
+ isa<ArrayType>(cast<PointerType>(dstTy)->getElementType())))
+ return true;
+
+ // If the arrays are different, the underlying memory areas do not overlap
+ // and the memory accesses are therefore independent.
+ if (srcObj != dstObj)
+ return false;
+
+ // We couldn't establish a more precise result, so we have to conservatively
+ // assume full dependence.
return true;
}
--- /dev/null
+; RUN: llvm-as < %s | opt -disable-output -analyze -lda > %t
+; RUN: grep {instructions: 2} %t | count 1
+; RUN: grep {0,1: dependent} %t | count 1
+
+; x[5] = x[6] // with x being an array on the stack
+
+define void @foo(...) nounwind {
+entry:
+ %xptr = alloca [256 x i32], align 4
+ %x.ld.addr = getelementptr [256 x i32]* %xptr, i64 0, i64 6
+ %x.st.addr = getelementptr [256 x i32]* %xptr, i64 0, i64 5
+ br label %for.body
+
+for.body:
+ %i = phi i64 [ 0, %entry ], [ %i.next, %for.body ]
+ %x = load i32* %x.ld.addr
+ store i32 %x, i32* %x.st.addr
+ %i.next = add i64 %i, 1
+ %exitcond = icmp eq i64 %i.next, 256
+ br i1 %exitcond, label %for.end, label %for.body
+
+for.end:
+ ret void
+}
--- /dev/null
+; RUN: llvm-as < %s | opt -disable-output -analyze -lda > %t
+; RUN: grep {instructions: 2} %t | count 1
+; RUN: grep {0,1: dependent} %t | count 1
+
+; x[5] = x[6] // with x being a pointer passed as argument
+
+define void @foo(i32* nocapture %xptr) nounwind {
+entry:
+ %x.ld.addr = getelementptr i32* %xptr, i64 6
+ %x.st.addr = getelementptr i32* %xptr, i64 5
+ br label %for.body
+
+for.body:
+ %i = phi i64 [ 0, %entry ], [ %i.next, %for.body ]
+ %x = load i32* %x.ld.addr
+ store i32 %x, i32* %x.st.addr
+ %i.next = add i64 %i, 1
+ %exitcond = icmp eq i64 %i.next, 256
+ br i1 %exitcond, label %for.end, label %for.body
+
+for.end:
+ ret void
+}
; RUN: llvm-as < %s | opt -disable-output -analyze -lda > %t
; RUN: grep {instructions: 3} %t | count 1
; RUN: grep {0,2: dependent} %t | count 1
-; RUN: grep {1,2: dependent} %t | count 1
+; RUN: grep {1,2: independent} %t | count 1
; for (i = 0; i < 256; i++)
; x[i] = x[i] + y[i]
; RUN: llvm-as < %s | opt -disable-output -analyze -lda > %t
; RUN: grep {instructions: 3} %t | count 1
; RUN: grep {0,2: dependent} %t | count 1
-; RUN: grep {1,2: dependent} %t | count 1
+; RUN: grep {1,2: independent} %t | count 1
; for (i = 0; i < 256; i++)
; x[i+1] = x[i] + y[i]