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