teach basicaa that A[i] != A[i+1].
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@89951 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/lib/Analysis/BasicAliasAnalysis.cpp b/lib/Analysis/BasicAliasAnalysis.cpp
index 15ae344..fb6b9df 100644
--- a/lib/Analysis/BasicAliasAnalysis.cpp
+++ b/lib/Analysis/BasicAliasAnalysis.cpp
@@ -378,6 +378,30 @@
return NoAA::getModRefInfo(CS1, CS2);
}
+/// GetLinearExpression - Analyze the specified value as a linear expression:
+/// "A*V + B". Return the scale and offset values as APInts and return V as a
+/// Value*. The incoming Value is known to be a scalar integer.
+static Value *GetLinearExpression(Value *V, APInt &Scale, APInt &Offset) {
+ assert(isa<IntegerType>(V->getType()) && "Not an integer value");
+
+ if (BinaryOperator *BOp = dyn_cast<BinaryOperator>(V)) {
+ if (ConstantInt *RHSC = dyn_cast<ConstantInt>(BOp->getOperand(1))) {
+ switch (BOp->getOpcode()) {
+ default: break;
+ case Instruction::Add:
+ V = GetLinearExpression(BOp->getOperand(0), Scale, Offset);
+ Offset += RHSC->getValue();
+ return V;
+ // TODO: SHL, MUL, OR.
+ }
+ }
+ }
+
+ Scale = 1;
+ Offset = 0;
+ return V;
+}
+
/// DecomposeGEPExpression - If V is a symbolic pointer expression, decompose it
/// into a base pointer with a constant offset and a number of scaled symbolic
/// offsets.
@@ -456,6 +480,14 @@
// TODO: Could handle linear expressions here like A[X+1], also A[X*4|1].
uint64_t Scale = TD->getTypeAllocSize(*GTI);
+ unsigned Width = cast<IntegerType>(Index->getType())->getBitWidth();
+ APInt IndexScale(Width, 0), IndexOffset(Width, 0);
+ Index = GetLinearExpression(Index, IndexScale, IndexOffset);
+
+ Scale *= IndexScale.getZExtValue();
+ BaseOffs += IndexOffset.getZExtValue()*Scale;
+
+
// If we already had an occurrance of this index variable, merge this
// scale into it. For example, we want to handle:
// A[x][x] -> x*16 + x*4 -> x*20
diff --git a/lib/Target/README.txt b/lib/Target/README.txt
index 6d90f05..3096f95 100644
--- a/lib/Target/README.txt
+++ b/lib/Target/README.txt
@@ -458,8 +458,6 @@
}
}
-BasicAA also doesn't do this for add. It needs to know that &A[i+1] != &A[i].
-
//===---------------------------------------------------------------------===//
We should investigate an instruction sinking pass. Consider this silly
diff --git a/test/Analysis/BasicAA/gep-alias.ll b/test/Analysis/BasicAA/gep-alias.ll
index e8f8a8e..0c5f7ac 100644
--- a/test/Analysis/BasicAA/gep-alias.ll
+++ b/test/Analysis/BasicAA/gep-alias.ll
@@ -71,3 +71,19 @@
; CHECK: @test4
; CHECK: ret i32 64
}
+
+; P[i] != p[i+1]
+define i32 @test5(i32* %p, i64 %i) {
+ %pi = getelementptr i32* %p, i64 %i
+ %i.next = add i64 %i, 1
+ %pi.next = getelementptr i32* %p, i64 %i.next
+ %x = load i32* %pi
+ store i32 42, i32* %pi.next
+ %y = load i32* %pi
+ %z = sub i32 %x, %y
+ ret i32 %z
+; CHECK: @test5
+; CHECK: ret i32 0
+}
+
+