X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FAnalysis%2FBasicAliasAnalysis.cpp;h=a9efc5a9f7341c438fa5f52a46cc855c47a72336;hb=92602ea18e3d3b1fb6b780a2aa0301004f2c7285;hp=11b33326fb7854e71c8de0b5d1841085fe2d2f16;hpb=adba582bc659f41de59b19b03af760fe93bd283f;p=oota-llvm.git diff --git a/lib/Analysis/BasicAliasAnalysis.cpp b/lib/Analysis/BasicAliasAnalysis.cpp index 11b33326fb7..a9efc5a9f73 100644 --- a/lib/Analysis/BasicAliasAnalysis.cpp +++ b/lib/Analysis/BasicAliasAnalysis.cpp @@ -17,7 +17,7 @@ #include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/SmallVector.h" #include "llvm/Analysis/AliasAnalysis.h" -#include "llvm/Analysis/AssumptionTracker.h" +#include "llvm/Analysis/AssumptionCache.h" #include "llvm/Analysis/CFG.h" #include "llvm/Analysis/CaptureTracking.h" #include "llvm/Analysis/InstructionSimplify.h" @@ -196,8 +196,7 @@ namespace { static Value *GetLinearExpression(Value *V, APInt &Scale, APInt &Offset, ExtensionKind &Extension, const DataLayout &DL, unsigned Depth, - AssumptionTracker *AT, - DominatorTree *DT) { + AssumptionCache *AC, DominatorTree *DT) { assert(V->getType()->isIntegerTy() && "Not an integer value"); // Limit our recursion depth. @@ -207,6 +206,14 @@ static Value *GetLinearExpression(Value *V, APInt &Scale, APInt &Offset, return V; } + if (ConstantInt *Const = dyn_cast(V)) { + // if it's a constant, just convert it to an offset + // and remove the variable. + Offset += Const->getValue(); + assert(Scale == 0 && "Constant values don't have a scale"); + return V; + } + if (BinaryOperator *BOp = dyn_cast(V)) { if (ConstantInt *RHSC = dyn_cast(BOp->getOperand(1))) { switch (BOp->getOpcode()) { @@ -214,24 +221,24 @@ static Value *GetLinearExpression(Value *V, APInt &Scale, APInt &Offset, case Instruction::Or: // X|C == X+C if all the bits in C are unset in X. Otherwise we can't // analyze it. - if (!MaskedValueIsZero(BOp->getOperand(0), RHSC->getValue(), &DL, 0, - AT, BOp, DT)) + if (!MaskedValueIsZero(BOp->getOperand(0), RHSC->getValue(), &DL, 0, AC, + BOp, DT)) break; // FALL THROUGH. case Instruction::Add: V = GetLinearExpression(BOp->getOperand(0), Scale, Offset, Extension, - DL, Depth+1, AT, DT); + DL, Depth + 1, AC, DT); Offset += RHSC->getValue(); return V; case Instruction::Mul: V = GetLinearExpression(BOp->getOperand(0), Scale, Offset, Extension, - DL, Depth+1, AT, DT); + DL, Depth + 1, AC, DT); Offset *= RHSC->getValue(); Scale *= RHSC->getValue(); return V; case Instruction::Shl: V = GetLinearExpression(BOp->getOperand(0), Scale, Offset, Extension, - DL, Depth+1, AT, DT); + DL, Depth + 1, AC, DT); Offset <<= RHSC->getValue().getLimitedValue(); Scale <<= RHSC->getValue().getLimitedValue(); return V; @@ -251,10 +258,13 @@ static Value *GetLinearExpression(Value *V, APInt &Scale, APInt &Offset, Offset = Offset.trunc(SmallWidth); Extension = isa(V) ? EK_SignExt : EK_ZeroExt; - Value *Result = GetLinearExpression(CastOp, Scale, Offset, Extension, - DL, Depth+1, AT, DT); + Value *Result = GetLinearExpression(CastOp, Scale, Offset, Extension, DL, + Depth + 1, AC, DT); Scale = Scale.zext(OldWidth); - Offset = Offset.zext(OldWidth); + + // We have to sign-extend even if Extension == EK_ZeroExt as we can't + // decompose a sign extension (i.e. zext(x - 1) != zext(x) - zext(-1)). + Offset = Offset.sext(OldWidth); return Result; } @@ -283,7 +293,7 @@ static const Value * DecomposeGEPExpression(const Value *V, int64_t &BaseOffs, SmallVectorImpl &VarIndices, bool &MaxLookupReached, const DataLayout *DL, - AssumptionTracker *AT, DominatorTree *DT) { + AssumptionCache *AC, DominatorTree *DT) { // Limit recursion depth to limit compile time in crazy cases. unsigned MaxLookup = MaxLookupSearchDepth; MaxLookupReached = false; @@ -314,7 +324,7 @@ DecomposeGEPExpression(const Value *V, int64_t &BaseOffs, // If it's not a GEP, hand it off to SimplifyInstruction to see if it // can come up with something. This matches what GetUnderlyingObject does. if (const Instruction *I = dyn_cast(V)) - // TODO: Get a DominatorTree and AssumptionTracker and use them here + // TODO: Get a DominatorTree and AssumptionCache and use them here // (these are both now available in this function, but this should be // updated when GetUnderlyingObject is updated). TLI should be // provided also. @@ -376,7 +386,7 @@ DecomposeGEPExpression(const Value *V, int64_t &BaseOffs, // Use GetLinearExpression to decompose the index into a C1*V+C2 form. APInt IndexScale(Width, 0), IndexOffset(Width, 0); Index = GetLinearExpression(Index, IndexScale, IndexOffset, Extension, - *DL, 0, AT, DT); + *DL, 0, AC, DT); // 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. @@ -457,7 +467,7 @@ namespace { void getAnalysisUsage(AnalysisUsage &AU) const override { AU.addRequired(); - AU.addRequired(); + AU.addRequired(); AU.addRequired(); } @@ -580,7 +590,7 @@ char BasicAliasAnalysis::ID = 0; INITIALIZE_AG_PASS_BEGIN(BasicAliasAnalysis, AliasAnalysis, "basicaa", "Basic Alias Analysis (stateless AA impl)", false, true, false) -INITIALIZE_PASS_DEPENDENCY(AssumptionTracker) +INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker) INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfo) INITIALIZE_AG_PASS_END(BasicAliasAnalysis, AliasAnalysis, "basicaa", "Basic Alias Analysis (stateless AA impl)", @@ -603,7 +613,7 @@ BasicAliasAnalysis::pointsToConstantMemory(const Location &Loc, bool OrLocal) { Worklist.push_back(Loc.Ptr); do { const Value *V = GetUnderlyingObject(Worklist.pop_back_val(), DL); - if (!Visited.insert(V)) { + if (!Visited.insert(V).second) { Visited.clear(); return AliasAnalysis::pointsToConstantMemory(Loc, OrLocal); } @@ -894,7 +904,22 @@ BasicAliasAnalysis::aliasGEP(const GEPOperator *GEP1, uint64_t V1Size, bool GEP1MaxLookupReached; SmallVector GEP1VariableIndices; - AssumptionTracker *AT = &getAnalysis(); + // We have to get two AssumptionCaches here because GEP1 and V2 may be from + // different functions. + // FIXME: This really doesn't make any sense. We get a dominator tree below + // that can only refer to a single function. But this function (aliasGEP) is + // a method on an immutable pass that can be called when there *isn't* + // a single function. The old pass management layer makes this "work", but + // this isn't really a clean solution. + AssumptionCacheTracker &ACT = getAnalysis(); + AssumptionCache *AC1 = nullptr, *AC2 = nullptr; + if (auto *GEP1I = dyn_cast(GEP1)) + AC1 = &ACT.getAssumptionCache( + const_cast(*GEP1I->getParent()->getParent())); + if (auto *I2 = dyn_cast(V2)) + AC2 = &ACT.getAssumptionCache( + const_cast(*I2->getParent()->getParent())); + DominatorTreeWrapperPass *DTWP = getAnalysisIfAvailable(); DominatorTree *DT = DTWP ? &DTWP->getDomTree() : nullptr; @@ -921,11 +946,11 @@ BasicAliasAnalysis::aliasGEP(const GEPOperator *GEP1, uint64_t V1Size, bool GEP2MaxLookupReached; SmallVector GEP2VariableIndices; const Value *GEP2BasePtr = - DecomposeGEPExpression(GEP2, GEP2BaseOffset, GEP2VariableIndices, - GEP2MaxLookupReached, DL, AT, DT); + DecomposeGEPExpression(GEP2, GEP2BaseOffset, GEP2VariableIndices, + GEP2MaxLookupReached, DL, AC2, DT); const Value *GEP1BasePtr = - DecomposeGEPExpression(GEP1, GEP1BaseOffset, GEP1VariableIndices, - GEP1MaxLookupReached, DL, AT, DT); + DecomposeGEPExpression(GEP1, GEP1BaseOffset, GEP1VariableIndices, + GEP1MaxLookupReached, DL, AC1, DT); // DecomposeGEPExpression and GetUnderlyingObject should return the // same result except when DecomposeGEPExpression has no DataLayout. if (GEP1BasePtr != UnderlyingV1 || GEP2BasePtr != UnderlyingV2) { @@ -953,15 +978,15 @@ BasicAliasAnalysis::aliasGEP(const GEPOperator *GEP1, uint64_t V1Size, // 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, AT, DT); + DecomposeGEPExpression(GEP1, GEP1BaseOffset, GEP1VariableIndices, + GEP1MaxLookupReached, DL, AC1, DT); int64_t GEP2BaseOffset; bool GEP2MaxLookupReached; SmallVector GEP2VariableIndices; const Value *GEP2BasePtr = - DecomposeGEPExpression(GEP2, GEP2BaseOffset, GEP2VariableIndices, - GEP2MaxLookupReached, DL, AT, DT); + DecomposeGEPExpression(GEP2, GEP2BaseOffset, GEP2VariableIndices, + GEP2MaxLookupReached, DL, AC2, DT); // DecomposeGEPExpression and GetUnderlyingObject should return the // same result except when DecomposeGEPExpression has no DataLayout. @@ -999,8 +1024,8 @@ BasicAliasAnalysis::aliasGEP(const GEPOperator *GEP1, uint64_t V1Size, return R; const Value *GEP1BasePtr = - DecomposeGEPExpression(GEP1, GEP1BaseOffset, GEP1VariableIndices, - GEP1MaxLookupReached, DL, AT, DT); + DecomposeGEPExpression(GEP1, GEP1BaseOffset, GEP1VariableIndices, + GEP1MaxLookupReached, DL, AC1, DT); // DecomposeGEPExpression and GetUnderlyingObject should return the // same result except when DecomposeGEPExpression has no DataLayout. @@ -1051,12 +1076,43 @@ BasicAliasAnalysis::aliasGEP(const GEPOperator *GEP1, uint64_t V1Size, } } - // Try to distinguish something like &A[i][1] against &A[42][0]. - // Grab the least significant bit set in any of the scales. if (!GEP1VariableIndices.empty()) { uint64_t Modulo = 0; - for (unsigned i = 0, e = GEP1VariableIndices.size(); i != e; ++i) - Modulo |= (uint64_t)GEP1VariableIndices[i].Scale; + bool AllPositive = true; + for (unsigned i = 0, e = GEP1VariableIndices.size(); i != e; ++i) { + + // Try to distinguish something like &A[i][1] against &A[42][0]. + // Grab the least significant bit set in any of the scales. We + // don't need std::abs here (even if the scale's negative) as we'll + // be ^'ing Modulo with itself later. + Modulo |= (uint64_t) GEP1VariableIndices[i].Scale; + + if (AllPositive) { + // If the Value could change between cycles, then any reasoning about + // the Value this cycle may not hold in the next cycle. We'll just + // give up if we can't determine conditions that hold for every cycle: + const Value *V = GEP1VariableIndices[i].V; + + bool SignKnownZero, SignKnownOne; + ComputeSignBit(const_cast(V), SignKnownZero, SignKnownOne, DL, + 0, AC1, nullptr, DT); + + // Zero-extension widens the variable, and so forces the sign + // bit to zero. + bool IsZExt = GEP1VariableIndices[i].Extension == EK_ZeroExt; + SignKnownZero |= IsZExt; + SignKnownOne &= !IsZExt; + + // If the variable begins with a zero then we know it's + // positive, regardless of whether the value is signed or + // unsigned. + int64_t Scale = GEP1VariableIndices[i].Scale; + AllPositive = + (SignKnownZero && Scale >= 0) || + (SignKnownOne && Scale < 0); + } + } + Modulo = Modulo ^ (Modulo & (Modulo - 1)); // We can compute the difference between the two addresses @@ -1066,6 +1122,12 @@ BasicAliasAnalysis::aliasGEP(const GEPOperator *GEP1, uint64_t V1Size, if (V1Size != UnknownSize && V2Size != UnknownSize && ModOffset >= V2Size && V1Size <= Modulo - ModOffset) return NoAlias; + + // If we know all the variables are positive, then GEP1 >= GEP1BasePtr. + // If GEP1BasePtr > V2 (GEP1BaseOffset > 0) then we know the pointers + // don't alias if V2Size can fit in the gap between V2 and GEP1BasePtr. + if (AllPositive && GEP1BaseOffset > 0 && V2Size <= (uint64_t) GEP1BaseOffset) + return NoAlias; } // Statically, we can see that the base objects are the same, but the @@ -1185,7 +1247,7 @@ BasicAliasAnalysis::aliasPHI(const PHINode *PN, uint64_t PNSize, // sides are PHI nodes. In which case, this is O(m x n) time where 'm' // and 'n' are the number of PHI sources. return MayAlias; - if (UniqueSrc.insert(PV1)) + if (UniqueSrc.insert(PV1).second) V1Srcs.push_back(PV1); }