diff options
| -rw-r--r-- | lib/Analysis/BasicAliasAnalysis.cpp | 32 | ||||
| -rw-r--r-- | lib/Target/README.txt | 2 | ||||
| -rw-r--r-- | test/Analysis/BasicAA/gep-alias.ll | 16 |
3 files changed, 48 insertions, 2 deletions
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 @@ BasicAliasAnalysis::getModRefInfo(CallSite CS1, CallSite CS2) { 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 @@ static const Value *DecomposeGEPExpression(const Value *V, int64_t &BaseOffs, // 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 @@ int i; } } -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 @@ entry: ; 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 +} + + |