Index: include/llvm/Analysis/BasicAliasAnalysis.h =================================================================== --- include/llvm/Analysis/BasicAliasAnalysis.h +++ include/llvm/Analysis/BasicAliasAnalysis.h @@ -139,11 +139,11 @@ const DataLayout &DL, unsigned Depth, AssumptionCache *AC, DominatorTree *DT, bool &NSW, bool &NUW); - static const Value * - DecomposeGEPExpression(const Value *V, int64_t &BaseOffs, - SmallVectorImpl &VarIndices, - bool &MaxLookupReached, const DataLayout &DL, - AssumptionCache *AC, DominatorTree *DT); + static const Value *DecomposeGEPExpression( + const Value *V, int64_t &BaseStructOffs, int64_t &BaseNonStructOffs, + SmallVectorImpl &VarIndices, bool &MaxLookupReached, + const DataLayout &DL, AssumptionCache *AC, DominatorTree *DT); + /// \brief A Heuristic for aliasGEP that searches for a constant offset /// between the variables. /// Index: lib/Analysis/BasicAliasAnalysis.cpp =================================================================== --- lib/Analysis/BasicAliasAnalysis.cpp +++ lib/Analysis/BasicAliasAnalysis.cpp @@ -343,8 +343,8 @@ /// GetUnderlyingObject and DecomposeGEPExpression must use the same search /// depth (MaxLookupSearchDepth). When DataLayout not is around, it just looks /// through pointer casts. -/*static*/ const Value *BasicAAResult::DecomposeGEPExpression( - const Value *V, int64_t &BaseOffs, +const Value *BasicAAResult::DecomposeGEPExpression( + const Value *V, int64_t &BaseStructOffs, int64_t &BaseNonStructOffs, SmallVectorImpl &VarIndices, bool &MaxLookupReached, const DataLayout &DL, AssumptionCache *AC, DominatorTree *DT) { // Limit recursion depth to limit compile time in crazy cases. @@ -352,7 +352,8 @@ MaxLookupReached = false; SearchTimes++; - BaseOffs = 0; + BaseStructOffs = 0; + BaseNonStructOffs = 0; do { // See if this is a bitcast or GEP. const Operator *Op = dyn_cast(V); @@ -409,7 +410,7 @@ if (FieldNo == 0) continue; - BaseOffs += DL.getStructLayout(STy)->getElementOffset(FieldNo); + BaseStructOffs += DL.getStructLayout(STy)->getElementOffset(FieldNo); continue; } @@ -417,7 +418,7 @@ if (const ConstantInt *CIdx = dyn_cast(Index)) { if (CIdx->isZero()) continue; - BaseOffs += DL.getTypeAllocSize(*GTI) * CIdx->getSExtValue(); + BaseNonStructOffs += DL.getTypeAllocSize(*GTI) * CIdx->getSExtValue(); continue; } @@ -438,7 +439,7 @@ // The GEP index scale ("Scale") scales C1*V+C2, yielding (C1*V+C2)*Scale. // This gives us an aggregate computation of (C1*Scale)*V + C2*Scale. - BaseOffs += IndexOffset.getSExtValue() * Scale; + BaseNonStructOffs += IndexOffset.getSExtValue() * Scale; Scale *= IndexScale.getSExtValue(); // If we already had an occurrence of this index variable, merge this @@ -466,7 +467,8 @@ } // Take care of wrap-arounds - BaseOffs = adjustToPointerSize(BaseOffs, PointerSize); + BaseStructOffs = adjustToPointerSize(BaseStructOffs, PointerSize); + BaseNonStructOffs = adjustToPointerSize(BaseNonStructOffs, PointerSize); // Analyze the base pointer next. V = GEPOp->getOperand(0); @@ -949,6 +951,41 @@ return MayAlias; } +// If a we have (a) a GEP and (b) a pointer based on an alloca, and the +// beginning of the object the GEP points would have a negative offset with +// repsect to the alloca, that means the GEP can not alias pointer (b). +// Note that the pointer based on the alloca may not be a GEP. For +// example, it may be the alloca itself. +static bool +isGEPBaseAtNegativeOffset(int64_t GEPStructOffset, int64_t GEPNonStructOffset, + int64_t AllocaBaseOffset, bool GEPHasVariableIndices, + bool AllocaHasVariableIndices, + bool GEPMaxLookupReached, bool AllocaMaxLookupReached, + const Value *AllocaBasePtr, uint64_t AllocaAccessSize, + const GEPOperator *GEPOp) { + + // If the alloca access size is unknown, or the GEP isn't inbounds, bail. + if (GEPMaxLookupReached || AllocaMaxLookupReached || + AllocaAccessSize == MemoryLocation::UnknownSize || !GEPOp->isInBounds()) + return false; + + // We need an alloca, and want to know the offset of the pointer + // from the alloca precisely, so no variable indices are allowed. + if (!isa(AllocaBasePtr) || AllocaHasVariableIndices) + return false; + + // If the GEP has no variable indices, we know the precise offset + // from the base, then use it. If the GEP has variable indices, we're in + // a bit more trouble: we can't count on the constant offsets that come + // from non-struct sources, since these can be "rewound" by a negative + // variable offset. So use only offsets that came from structs. + int64_t GEPBaseOffset = GEPStructOffset; + if (!GEPHasVariableIndices) + GEPBaseOffset += GEPNonStructOffset; + + return (GEPBaseOffset >= AllocaBaseOffset + (int64_t)AllocaAccessSize); +} + /// Provides a bunch of ad-hoc rules to disambiguate a GEP instruction against /// another pointer. /// @@ -960,14 +997,47 @@ uint64_t V2Size, const AAMDNodes &V2AAInfo, const Value *UnderlyingV1, const Value *UnderlyingV2) { - int64_t GEP1BaseOffset; - bool GEP1MaxLookupReached; - SmallVector GEP1VariableIndices; + int64_t GEP1StructOffset, GEP2StructOffset, GEP1NonStructOffset, + GEP2NonStructOffset; + bool GEP1MaxLookupReached, GEP2MaxLookupReached; + SmallVector GEP1VariableIndices, GEP2VariableIndices; + + const Value *GEP1BasePtr = DecomposeGEPExpression( + GEP1, GEP1StructOffset, GEP1NonStructOffset, GEP1VariableIndices, + GEP1MaxLookupReached, DL, &AC, DT); + const Value *GEP2BasePtr = DecomposeGEPExpression( + V2, GEP2StructOffset, GEP2NonStructOffset, GEP2VariableIndices, + GEP2MaxLookupReached, DL, &AC, DT); + int64_t GEP1BaseOffset = GEP1StructOffset + GEP1NonStructOffset; + int64_t GEP2BaseOffset = GEP2StructOffset + GEP2NonStructOffset; + + assert(GEP1BasePtr == UnderlyingV1 && GEP2BasePtr == UnderlyingV2 && + "DecomposeGEPExpression returned a result different from " + "GetUnderlyingObject"); + + // If the GEP's offset relative to its base is such that the base would + // fall below the start of the object underlying V2, then the GEP and V2 + // cannot alias. + if (isGEPBaseAtNegativeOffset(GEP1StructOffset, GEP1NonStructOffset, + GEP2BaseOffset, !GEP1VariableIndices.empty(), + !GEP2VariableIndices.empty(), + GEP1MaxLookupReached, GEP2MaxLookupReached, + GEP2BasePtr, V2Size, GEP1)) + return NoAlias; // If we have two gep instructions with must-alias or not-alias'ing base // pointers, figure out if the indexes to the GEP tell us anything about the // derived pointer. if (const GEPOperator *GEP2 = dyn_cast(V2)) { + // Check for the GEP base being at a negative offset, this time in the other + // direction. + if (isGEPBaseAtNegativeOffset(GEP2StructOffset, GEP2NonStructOffset, + GEP1BaseOffset, !GEP2VariableIndices.empty(), + !GEP1VariableIndices.empty(), + GEP2MaxLookupReached, GEP1MaxLookupReached, + GEP1BasePtr, V1Size, GEP2)) + return NoAlias; + // Do the base pointers alias? AliasResult BaseAlias = aliasCheck(UnderlyingV1, MemoryLocation::UnknownSize, AAMDNodes(), @@ -982,22 +1052,6 @@ if (PreciseBaseAlias == NoAlias) { // See if the computed offset from the common pointer tells us about the // relation of the resulting pointer. - int64_t GEP2BaseOffset; - bool GEP2MaxLookupReached; - SmallVector GEP2VariableIndices; - const Value *GEP2BasePtr = - DecomposeGEPExpression(GEP2, GEP2BaseOffset, GEP2VariableIndices, - GEP2MaxLookupReached, DL, &AC, DT); - const Value *GEP1BasePtr = - DecomposeGEPExpression(GEP1, GEP1BaseOffset, GEP1VariableIndices, - GEP1MaxLookupReached, DL, &AC, DT); - // DecomposeGEPExpression and GetUnderlyingObject should return the - // same result except when DecomposeGEPExpression has no DataLayout. - // FIXME: They always have a DataLayout, so this should become an - // assert. - if (GEP1BasePtr != UnderlyingV1 || GEP2BasePtr != UnderlyingV2) { - return MayAlias; - } // If the max search depth is reached the result is undefined if (GEP2MaxLookupReached || GEP1MaxLookupReached) return MayAlias; @@ -1006,7 +1060,6 @@ if (GEP1BaseOffset == GEP2BaseOffset && GEP1VariableIndices == GEP2VariableIndices) return NoAlias; - GEP1VariableIndices.clear(); } } @@ -1018,24 +1071,6 @@ // Otherwise, we have a MustAlias. Since the base pointers alias each other // exactly, see if the computed offset from the common pointer tells us // about the relation of the resulting pointer. - const Value *GEP1BasePtr = - DecomposeGEPExpression(GEP1, GEP1BaseOffset, GEP1VariableIndices, - GEP1MaxLookupReached, DL, &AC, DT); - - int64_t GEP2BaseOffset; - bool GEP2MaxLookupReached; - SmallVector GEP2VariableIndices; - const Value *GEP2BasePtr = - DecomposeGEPExpression(GEP2, GEP2BaseOffset, GEP2VariableIndices, - GEP2MaxLookupReached, DL, &AC, DT); - - // DecomposeGEPExpression and GetUnderlyingObject should return the - // same result except when DecomposeGEPExpression has no DataLayout. - // FIXME: They always have a DataLayout, so this should become an assert. - if (GEP1BasePtr != UnderlyingV1 || GEP2BasePtr != UnderlyingV2) { - return MayAlias; - } - // If we know the two GEPs are based off of the exact same pointer (and not // just the same underlying object), see if that tells us anything about // the resulting pointers. @@ -1075,16 +1110,6 @@ // with the first operand of the getelementptr". return R; - const Value *GEP1BasePtr = - DecomposeGEPExpression(GEP1, GEP1BaseOffset, GEP1VariableIndices, - GEP1MaxLookupReached, DL, &AC, DT); - - // DecomposeGEPExpression and GetUnderlyingObject should return the - // same result except when DecomposeGEPExpression has no DataLayout. - // FIXME: They always have a DataLayout, so this should become an assert. - if (GEP1BasePtr != UnderlyingV1) { - return MayAlias; - } // If the max search depth is reached the result is undefined if (GEP1MaxLookupReached) return MayAlias; Index: test/Analysis/BasicAA/negoffset.ll =================================================================== --- test/Analysis/BasicAA/negoffset.ll +++ test/Analysis/BasicAA/negoffset.ll @@ -0,0 +1,68 @@ +; RUN: opt < %s -basicaa -aa-eval -print-all-alias-modref-info -disable-output 2>&1 | FileCheck %s + +target datalayout = "e-m:e-p:32:32-f64:32:64-f80:32-n8:16:32-S128" +target triple = "i386-unknown-linux-gnu" + +declare i32* @random.i32(i32* %ptr) + +; CHECK-LABEL: Function: arr: +; CHECK-DAG: MayAlias: i32* %alloca, i32* %p0 +; CHECK-DAG: NoAlias: i32* %alloca, i32* %p1 +define void @arr() { + %alloca = alloca i32, i32 4 + %random = call i32* @random.i32(i32* %alloca) + %p0 = getelementptr inbounds i32, i32* %random, i32 0 + %p1 = getelementptr inbounds i32, i32* %random, i32 1 + ret void +} + +; CHECK-LABEL: Function: arg: +; CHECK-DAG: MayAlias: i32* %arg, i32* %p0 +; CHECK-DAG: MayAlias: i32* %arg, i32* %p1 +define void @arg(i32* %arg) { + %random = call i32* @random.i32(i32* %arg) + %p0 = getelementptr inbounds i32, i32* %random, i32 0 + %p1 = getelementptr inbounds i32, i32* %random, i32 1 + ret void +} + +; CHECK-LABEL: Function: struct: +; CHECK-DAG: MayAlias: i32* %f0, i32* %p0 +; CHECK-DAG: MayAlias: i32* %f1, i32* %p0 +; CHECK-DAG: NoAlias: i32* %f0, i32* %p1 +; CHECK-DAG: MayAlias: i32* %f1, i32* %p1 +%struct = type { i32, i32, i32 } +define void @struct() { + %alloca = alloca %struct + %alloca.i32 = bitcast %struct* %alloca to i32* + %random = call i32* @random.i32(i32* %alloca.i32) + %f0 = getelementptr inbounds %struct, %struct* %alloca, i32 0, i32 0 + %f1 = getelementptr inbounds %struct, %struct* %alloca, i32 0, i32 1 + %p0 = getelementptr inbounds i32, i32* %random, i32 0 + %p1 = getelementptr inbounds i32, i32* %random, i32 1 + ret void +} + +; CHECK-LABEL: Function: complex: +; CHECK-DAG: MayAlias: i32* %a2.0, i32* %r2.0 +; CHECK-DAG: NoAlias: i32* %a2.0, i32* %r2.1 +; CHECK-DAG: MayAlias: i32* %a2.0, i32* %r2.i +; CHECK-DAG: MayAlias: i32* %a2.0, i32* %r2.1i +; CHECK-DAG: NoAlias: i32* %a1, i32* %r2.0 +; CHECK-DAG: NoAlias: i32* %a1, i32* %r2.1 +; CHECK-DAG: NoAlias: i32* %a1, i32* %r2.i +; CHECK-DAG: NoAlias: i32* %a1, i32* %r2.1i +%complex = type { i32, i32, [4 x i32] } +define void @complex(i32 %i) { + %alloca = alloca %complex + %alloca.i32 = bitcast %complex* %alloca to i32* + %r.i32 = call i32* @random.i32(i32* %alloca.i32) + %random = bitcast i32* %r.i32 to %complex* + %a1 = getelementptr inbounds %complex, %complex* %alloca, i32 0, i32 1 + %a2.0 = getelementptr inbounds %complex, %complex* %alloca, i32 0, i32 2, i32 0 + %r2.0 = getelementptr inbounds %complex, %complex* %random, i32 0, i32 2, i32 0 + %r2.1 = getelementptr inbounds %complex, %complex* %random, i32 0, i32 2, i32 1 + %r2.i = getelementptr inbounds %complex, %complex* %random, i32 0, i32 2, i32 %i + %r2.1i = getelementptr inbounds i32, i32* %r2.1, i32 %i + ret void +}