diff options
Diffstat (limited to 'llvm/lib/Analysis/BasicAliasAnalysis.cpp')
| -rw-r--r-- | llvm/lib/Analysis/BasicAliasAnalysis.cpp | 866 |
1 files changed, 411 insertions, 455 deletions
diff --git a/llvm/lib/Analysis/BasicAliasAnalysis.cpp b/llvm/lib/Analysis/BasicAliasAnalysis.cpp index 97d0cb63ef99..357772c9c4f2 100644 --- a/llvm/lib/Analysis/BasicAliasAnalysis.cpp +++ b/llvm/lib/Analysis/BasicAliasAnalysis.cpp @@ -23,7 +23,6 @@ #include "llvm/Analysis/CFG.h" #include "llvm/Analysis/CaptureTracking.h" #include "llvm/Analysis/InstructionSimplify.h" -#include "llvm/Analysis/LoopInfo.h" #include "llvm/Analysis/MemoryBuiltins.h" #include "llvm/Analysis/MemoryLocation.h" #include "llvm/Analysis/PhiValues.h" @@ -104,7 +103,6 @@ bool BasicAAResult::invalidate(Function &Fn, const PreservedAnalyses &PA, // depend on them. if (Inv.invalidate<AssumptionAnalysis>(Fn, PA) || (DT && Inv.invalidate<DominatorTreeAnalysis>(Fn, PA)) || - (LI && Inv.invalidate<LoopAnalysis>(Fn, PA)) || (PV && Inv.invalidate<PhiValuesAnalysis>(Fn, PA))) return true; @@ -131,6 +129,14 @@ static bool isEscapeSource(const Value *V) { if (isa<LoadInst>(V)) return true; + // The inttoptr case works because isNonEscapingLocalObject considers all + // means of converting or equating a pointer to an int (ptrtoint, ptr store + // which could be followed by an integer load, ptr<->int compare) as + // escaping, and objects located at well-known addresses via platform-specific + // means cannot be considered non-escaping local objects. + if (isa<IntToPtrInst>(V)) + return true; + return false; } @@ -201,9 +207,11 @@ static uint64_t getMinimalExtentFrom(const Value &V, // If we have dereferenceability information we know a lower bound for the // extent as accesses for a lower offset would be valid. We need to exclude // the "or null" part if null is a valid pointer. - bool CanBeNull; - uint64_t DerefBytes = V.getPointerDereferenceableBytes(DL, CanBeNull); + bool CanBeNull, CanBeFreed; + uint64_t DerefBytes = + V.getPointerDereferenceableBytes(DL, CanBeNull, CanBeFreed); DerefBytes = (CanBeNull && NullIsValidLoc) ? 0 : DerefBytes; + DerefBytes = CanBeFreed ? 0 : DerefBytes; // If queried with a precise location size, we assume that location size to be // accessed, thus valid. if (LocSize.isPrecise()) @@ -222,167 +230,168 @@ static bool isObjectSize(const Value *V, uint64_t Size, const DataLayout &DL, // GetElementPtr Instruction Decomposition and Analysis //===----------------------------------------------------------------------===// -/// Analyzes the specified value as a linear expression: "A*V + B", where A and -/// B are constant integers. -/// -/// Returns the scale and offset values as APInts and return V as a Value*, and -/// return whether we looked through any sign or zero extends. The incoming -/// Value is known to have IntegerType, and it may already be sign or zero -/// extended. -/// -/// Note that this looks through extends, so the high bits may not be -/// represented in the result. -/*static*/ const Value *BasicAAResult::GetLinearExpression( - const Value *V, APInt &Scale, APInt &Offset, unsigned &ZExtBits, - unsigned &SExtBits, const DataLayout &DL, unsigned Depth, - AssumptionCache *AC, DominatorTree *DT, bool &NSW, bool &NUW) { - assert(V->getType()->isIntegerTy() && "Not an integer value"); +namespace { +/// Represents zext(sext(V)). +struct ExtendedValue { + const Value *V; + unsigned ZExtBits; + unsigned SExtBits; - // Limit our recursion depth. - if (Depth == 6) { - Scale = 1; - Offset = 0; - return V; + explicit ExtendedValue(const Value *V, unsigned ZExtBits = 0, + unsigned SExtBits = 0) + : V(V), ZExtBits(ZExtBits), SExtBits(SExtBits) {} + + unsigned getBitWidth() const { + return V->getType()->getPrimitiveSizeInBits() + ZExtBits + SExtBits; + } + + ExtendedValue withValue(const Value *NewV) const { + return ExtendedValue(NewV, ZExtBits, SExtBits); + } + + ExtendedValue withZExtOfValue(const Value *NewV) const { + unsigned ExtendBy = V->getType()->getPrimitiveSizeInBits() - + NewV->getType()->getPrimitiveSizeInBits(); + // zext(sext(zext(NewV))) == zext(zext(zext(NewV))) + return ExtendedValue(NewV, ZExtBits + SExtBits + ExtendBy, 0); + } + + ExtendedValue withSExtOfValue(const Value *NewV) const { + unsigned ExtendBy = V->getType()->getPrimitiveSizeInBits() - + NewV->getType()->getPrimitiveSizeInBits(); + // zext(sext(sext(NewV))) + return ExtendedValue(NewV, ZExtBits, SExtBits + ExtendBy); + } + + APInt evaluateWith(APInt N) const { + assert(N.getBitWidth() == V->getType()->getPrimitiveSizeInBits() && + "Incompatible bit width"); + if (SExtBits) N = N.sext(N.getBitWidth() + SExtBits); + if (ZExtBits) N = N.zext(N.getBitWidth() + ZExtBits); + return N; + } + + bool canDistributeOver(bool NUW, bool NSW) const { + // zext(x op<nuw> y) == zext(x) op<nuw> zext(y) + // sext(x op<nsw> y) == sext(x) op<nsw> sext(y) + return (!ZExtBits || NUW) && (!SExtBits || NSW); } +}; + +/// Represents zext(sext(V)) * Scale + Offset. +struct LinearExpression { + ExtendedValue Val; + APInt Scale; + APInt Offset; - if (const ConstantInt *Const = dyn_cast<ConstantInt>(V)) { - // If it's a constant, just convert it to an offset and remove the variable. - // If we've been called recursively, the Offset bit width will be greater - // than the constant's (the Offset's always as wide as the outermost call), - // so we'll zext here and process any extension in the isa<SExtInst> & - // isa<ZExtInst> cases below. - Offset += Const->getValue().zextOrSelf(Offset.getBitWidth()); - assert(Scale == 0 && "Constant values don't have a scale"); - return V; + /// True if all operations in this expression are NSW. + bool IsNSW; + + LinearExpression(const ExtendedValue &Val, const APInt &Scale, + const APInt &Offset, bool IsNSW) + : Val(Val), Scale(Scale), Offset(Offset), IsNSW(IsNSW) {} + + LinearExpression(const ExtendedValue &Val) : Val(Val), IsNSW(true) { + unsigned BitWidth = Val.getBitWidth(); + Scale = APInt(BitWidth, 1); + Offset = APInt(BitWidth, 0); } +}; +} - if (const BinaryOperator *BOp = dyn_cast<BinaryOperator>(V)) { +/// Analyzes the specified value as a linear expression: "A*V + B", where A and +/// B are constant integers. +static LinearExpression GetLinearExpression( + const ExtendedValue &Val, const DataLayout &DL, unsigned Depth, + AssumptionCache *AC, DominatorTree *DT) { + // Limit our recursion depth. + if (Depth == 6) + return Val; + + if (const ConstantInt *Const = dyn_cast<ConstantInt>(Val.V)) + return LinearExpression(Val, APInt(Val.getBitWidth(), 0), + Val.evaluateWith(Const->getValue()), true); + + if (const BinaryOperator *BOp = dyn_cast<BinaryOperator>(Val.V)) { if (ConstantInt *RHSC = dyn_cast<ConstantInt>(BOp->getOperand(1))) { - // If we've been called recursively, then Offset and Scale will be wider - // than the BOp operands. We'll always zext it here as we'll process sign - // extensions below (see the isa<SExtInst> / isa<ZExtInst> cases). - APInt RHS = RHSC->getValue().zextOrSelf(Offset.getBitWidth()); + APInt RHS = Val.evaluateWith(RHSC->getValue()); + // The only non-OBO case we deal with is or, and only limited to the + // case where it is both nuw and nsw. + bool NUW = true, NSW = true; + if (isa<OverflowingBinaryOperator>(BOp)) { + NUW &= BOp->hasNoUnsignedWrap(); + NSW &= BOp->hasNoSignedWrap(); + } + if (!Val.canDistributeOver(NUW, NSW)) + return Val; + LinearExpression E(Val); switch (BOp->getOpcode()) { default: // We don't understand this instruction, so we can't decompose it any // further. - Scale = 1; - Offset = 0; - return V; + return Val; 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, AC, - BOp, DT)) { - Scale = 1; - Offset = 0; - return V; - } + BOp, DT)) + return Val; + LLVM_FALLTHROUGH; - case Instruction::Add: - V = GetLinearExpression(BOp->getOperand(0), Scale, Offset, ZExtBits, - SExtBits, DL, Depth + 1, AC, DT, NSW, NUW); - Offset += RHS; + case Instruction::Add: { + E = GetLinearExpression(Val.withValue(BOp->getOperand(0)), DL, + Depth + 1, AC, DT); + E.Offset += RHS; + E.IsNSW &= NSW; break; - case Instruction::Sub: - V = GetLinearExpression(BOp->getOperand(0), Scale, Offset, ZExtBits, - SExtBits, DL, Depth + 1, AC, DT, NSW, NUW); - Offset -= RHS; + } + case Instruction::Sub: { + E = GetLinearExpression(Val.withValue(BOp->getOperand(0)), DL, + Depth + 1, AC, DT); + E.Offset -= RHS; + E.IsNSW &= NSW; break; - case Instruction::Mul: - V = GetLinearExpression(BOp->getOperand(0), Scale, Offset, ZExtBits, - SExtBits, DL, Depth + 1, AC, DT, NSW, NUW); - Offset *= RHS; - Scale *= RHS; + } + case Instruction::Mul: { + E = GetLinearExpression(Val.withValue(BOp->getOperand(0)), DL, + Depth + 1, AC, DT); + E.Offset *= RHS; + E.Scale *= RHS; + E.IsNSW &= NSW; break; + } case Instruction::Shl: - V = GetLinearExpression(BOp->getOperand(0), Scale, Offset, ZExtBits, - SExtBits, DL, Depth + 1, AC, DT, NSW, NUW); - // We're trying to linearize an expression of the kind: // shl i8 -128, 36 // where the shift count exceeds the bitwidth of the type. // We can't decompose this further (the expression would return // a poison value). - if (Offset.getBitWidth() < RHS.getLimitedValue() || - Scale.getBitWidth() < RHS.getLimitedValue()) { - Scale = 1; - Offset = 0; - return V; - } - - Offset <<= RHS.getLimitedValue(); - Scale <<= RHS.getLimitedValue(); - // the semantics of nsw and nuw for left shifts don't match those of - // multiplications, so we won't propagate them. - NSW = NUW = false; - return V; - } - - if (isa<OverflowingBinaryOperator>(BOp)) { - NUW &= BOp->hasNoUnsignedWrap(); - NSW &= BOp->hasNoSignedWrap(); + if (RHS.getLimitedValue() > Val.getBitWidth()) + return Val; + + E = GetLinearExpression(Val.withValue(BOp->getOperand(0)), DL, + Depth + 1, AC, DT); + E.Offset <<= RHS.getLimitedValue(); + E.Scale <<= RHS.getLimitedValue(); + E.IsNSW &= NSW; + break; } - return V; + return E; } } - // Since GEP indices are sign extended anyway, we don't care about the high - // bits of a sign or zero extended value - just scales and offsets. The - // extensions have to be consistent though. - if (isa<SExtInst>(V) || isa<ZExtInst>(V)) { - Value *CastOp = cast<CastInst>(V)->getOperand(0); - unsigned NewWidth = V->getType()->getPrimitiveSizeInBits(); - unsigned SmallWidth = CastOp->getType()->getPrimitiveSizeInBits(); - unsigned OldZExtBits = ZExtBits, OldSExtBits = SExtBits; - const Value *Result = - GetLinearExpression(CastOp, Scale, Offset, ZExtBits, SExtBits, DL, - Depth + 1, AC, DT, NSW, NUW); - - // zext(zext(%x)) == zext(%x), and similarly for sext; we'll handle this - // by just incrementing the number of bits we've extended by. - unsigned ExtendedBy = NewWidth - SmallWidth; - - if (isa<SExtInst>(V) && ZExtBits == 0) { - // sext(sext(%x, a), b) == sext(%x, a + b) - - if (NSW) { - // We haven't sign-wrapped, so it's valid to decompose sext(%x + c) - // into sext(%x) + sext(c). We'll sext the Offset ourselves: - unsigned OldWidth = Offset.getBitWidth(); - Offset = Offset.trunc(SmallWidth).sext(NewWidth).zextOrSelf(OldWidth); - } else { - // We may have signed-wrapped, so don't decompose sext(%x + c) into - // sext(%x) + sext(c) - Scale = 1; - Offset = 0; - Result = CastOp; - ZExtBits = OldZExtBits; - SExtBits = OldSExtBits; - } - SExtBits += ExtendedBy; - } else { - // sext(zext(%x, a), b) = zext(zext(%x, a), b) = zext(%x, a + b) - - if (!NUW) { - // We may have unsigned-wrapped, so don't decompose zext(%x + c) into - // zext(%x) + zext(c) - Scale = 1; - Offset = 0; - Result = CastOp; - ZExtBits = OldZExtBits; - SExtBits = OldSExtBits; - } - ZExtBits += ExtendedBy; - } + if (isa<ZExtInst>(Val.V)) + return GetLinearExpression( + Val.withZExtOfValue(cast<CastInst>(Val.V)->getOperand(0)), + DL, Depth + 1, AC, DT); - return Result; - } + if (isa<SExtInst>(Val.V)) + return GetLinearExpression( + Val.withSExtOfValue(cast<CastInst>(Val.V)->getOperand(0)), + DL, Depth + 1, AC, DT); - Scale = 1; - Offset = 0; - return V; + return Val; } /// To ensure a pointer offset fits in an integer of size PointerSize @@ -477,6 +486,13 @@ BasicAAResult::DecomposeGEPExpression(const Value *V, const DataLayout &DL, return Decomposed; } + // Track whether we've seen at least one in bounds gep, and if so, whether + // all geps parsed were in bounds. + if (Decomposed.InBounds == None) + Decomposed.InBounds = GEPOp->isInBounds(); + else if (!GEPOp->isInBounds()) + Decomposed.InBounds = false; + // Don't attempt to analyze GEPs over unsized objects. if (!GEPOp->getSourceElementType()->isSized()) { Decomposed.Base = V; @@ -525,20 +541,12 @@ BasicAAResult::DecomposeGEPExpression(const Value *V, const DataLayout &DL, APInt Scale(MaxPointerSize, DL.getTypeAllocSize(GTI.getIndexedType()).getFixedSize()); - unsigned ZExtBits = 0, SExtBits = 0; - // If the integer type is smaller than the pointer size, it is implicitly // sign extended to pointer size. unsigned Width = Index->getType()->getIntegerBitWidth(); - if (PointerSize > Width) - SExtBits += PointerSize - Width; - - // Use GetLinearExpression to decompose the index into a C1*V+C2 form. - APInt IndexScale(Width, 0), IndexOffset(Width, 0); - bool NSW = true, NUW = true; - const Value *OrigIndex = Index; - Index = GetLinearExpression(Index, IndexScale, IndexOffset, ZExtBits, - SExtBits, DL, 0, AC, DT, NSW, NUW); + unsigned SExtBits = PointerSize > Width ? PointerSize - Width : 0; + LinearExpression LE = GetLinearExpression( + ExtendedValue(Index, 0, SExtBits), 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. @@ -551,19 +559,13 @@ BasicAAResult::DecomposeGEPExpression(const Value *V, const DataLayout &DL, // (C1*Scale)*V+C2*Scale can also overflow. We should check for this // possibility. bool Overflow; - APInt ScaledOffset = IndexOffset.sextOrTrunc(MaxPointerSize) + APInt ScaledOffset = LE.Offset.sextOrTrunc(MaxPointerSize) .smul_ov(Scale, Overflow); if (Overflow) { - Index = OrigIndex; - IndexScale = 1; - IndexOffset = 0; - - ZExtBits = SExtBits = 0; - if (PointerSize > Width) - SExtBits += PointerSize - Width; + LE = LinearExpression(ExtendedValue(Index, 0, SExtBits)); } else { Decomposed.Offset += ScaledOffset; - Scale *= IndexScale.sextOrTrunc(MaxPointerSize); + Scale *= LE.Scale.sextOrTrunc(MaxPointerSize); } // If we already had an occurrence of this index variable, merge this @@ -571,9 +573,9 @@ BasicAAResult::DecomposeGEPExpression(const Value *V, const DataLayout &DL, // A[x][x] -> x*16 + x*4 -> x*20 // This also ensures that 'x' only appears in the index list once. for (unsigned i = 0, e = Decomposed.VarIndices.size(); i != e; ++i) { - if (Decomposed.VarIndices[i].V == Index && - Decomposed.VarIndices[i].ZExtBits == ZExtBits && - Decomposed.VarIndices[i].SExtBits == SExtBits) { + if (Decomposed.VarIndices[i].V == LE.Val.V && + Decomposed.VarIndices[i].ZExtBits == LE.Val.ZExtBits && + Decomposed.VarIndices[i].SExtBits == LE.Val.SExtBits) { Scale += Decomposed.VarIndices[i].Scale; Decomposed.VarIndices.erase(Decomposed.VarIndices.begin() + i); break; @@ -585,7 +587,8 @@ BasicAAResult::DecomposeGEPExpression(const Value *V, const DataLayout &DL, Scale = adjustToPointerSize(Scale, PointerSize); if (!!Scale) { - VariableGEPIndex Entry = {Index, ZExtBits, SExtBits, Scale, CxtI}; + VariableGEPIndex Entry = { + LE.Val.V, LE.Val.ZExtBits, LE.Val.SExtBits, Scale, CxtI, LE.IsNSW}; Decomposed.VarIndices.push_back(Entry); } } @@ -665,6 +668,11 @@ bool BasicAAResult::pointsToConstantMemory(const MemoryLocation &Loc, return Worklist.empty(); } +static bool isIntrinsicCall(const CallBase *Call, Intrinsic::ID IID) { + const IntrinsicInst *II = dyn_cast<IntrinsicInst>(Call); + return II && II->getIntrinsicID() == IID; +} + /// Returns the behavior when calling the given call site. FunctionModRefBehavior BasicAAResult::getModRefBehavior(const CallBase *Call) { if (Call->doesNotAccessMemory()) @@ -764,11 +772,6 @@ ModRefInfo BasicAAResult::getArgModRefInfo(const CallBase *Call, return AAResultBase::getArgModRefInfo(Call, ArgIdx); } -static bool isIntrinsicCall(const CallBase *Call, Intrinsic::ID IID) { - const IntrinsicInst *II = dyn_cast<IntrinsicInst>(Call); - return II && II->getIntrinsicID() == IID; -} - #ifndef NDEBUG static const Function *getParent(const Value *V) { if (const Instruction *inst = dyn_cast<Instruction>(V)) { @@ -797,8 +800,7 @@ AliasResult BasicAAResult::alias(const MemoryLocation &LocA, AAQueryInfo &AAQI) { assert(notDifferentParent(LocA.Ptr, LocB.Ptr) && "BasicAliasAnalysis doesn't support interprocedural queries."); - return aliasCheck(LocA.Ptr, LocA.Size, LocA.AATags, LocB.Ptr, LocB.Size, - LocB.AATags, AAQI); + return aliasCheck(LocA.Ptr, LocA.Size, LocB.Ptr, LocB.Size, AAQI); } /// Checks to see if the specified callsite can clobber the specified memory @@ -865,10 +867,10 @@ ModRefInfo BasicAAResult::getModRefInfo(const CallBase *Call, AliasResult AR = getBestAAResults().alias( MemoryLocation::getBeforeOrAfter(*CI), MemoryLocation::getBeforeOrAfter(Object), AAQI); - if (AR != MustAlias) + if (AR != AliasResult::MustAlias) IsMustAlias = false; // Operand doesn't alias 'Object', continue looking for other aliases - if (AR == NoAlias) + if (AR == AliasResult::NoAlias) continue; // Operand aliases 'Object', but call doesn't modify it. Strengthen // initial assumption and keep looking in case if there are more aliases. @@ -910,8 +912,8 @@ ModRefInfo BasicAAResult::getModRefInfo(const CallBase *Call, if (isMallocOrCallocLikeFn(Call, &TLI)) { // Be conservative if the accessed pointer may alias the allocation - // fallback to the generic handling below. - if (getBestAAResults().alias(MemoryLocation::getBeforeOrAfter(Call), - Loc, AAQI) == NoAlias) + if (getBestAAResults().alias(MemoryLocation::getBeforeOrAfter(Call), Loc, + AAQI) == AliasResult::NoAlias) return ModRefInfo::NoModRef; } @@ -925,22 +927,16 @@ ModRefInfo BasicAAResult::getModRefInfo(const CallBase *Call, getBestAAResults().alias(MemoryLocation::getForDest(Inst), Loc, AAQI); // It's also possible for Loc to alias both src and dest, or neither. ModRefInfo rv = ModRefInfo::NoModRef; - if (SrcAA != NoAlias) + if (SrcAA != AliasResult::NoAlias) rv = setRef(rv); - if (DestAA != NoAlias) + if (DestAA != AliasResult::NoAlias) rv = setMod(rv); return rv; } - // While the assume intrinsic is marked as arbitrarily writing so that - // proper control dependencies will be maintained, it never aliases any - // particular memory location. - if (isIntrinsicCall(Call, Intrinsic::assume)) - return ModRefInfo::NoModRef; - - // Like assumes, guard intrinsics are also marked as arbitrarily writing so - // that proper control dependencies are maintained but they never mods any - // particular memory location. + // Guard intrinsics are marked as arbitrarily writing so that proper control + // dependencies are maintained but they never mods any particular memory + // location. // // *Unlike* assumes, guard intrinsics are modeled as reading memory since the // heap state at the point the guard is issued needs to be consistent in case @@ -984,16 +980,9 @@ ModRefInfo BasicAAResult::getModRefInfo(const CallBase *Call, ModRefInfo BasicAAResult::getModRefInfo(const CallBase *Call1, const CallBase *Call2, AAQueryInfo &AAQI) { - // While the assume intrinsic is marked as arbitrarily writing so that - // proper control dependencies will be maintained, it never aliases any - // particular memory location. - if (isIntrinsicCall(Call1, Intrinsic::assume) || - isIntrinsicCall(Call2, Intrinsic::assume)) - return ModRefInfo::NoModRef; - - // Like assumes, guard intrinsics are also marked as arbitrarily writing so - // that proper control dependencies are maintained but they never mod any - // particular memory location. + // Guard intrinsics are marked as arbitrarily writing so that proper control + // dependencies are maintained but they never mods any particular memory + // location. // // *Unlike* assumes, guard intrinsics are modeled as reading memory since the // heap state at the point the guard is issued needs to be consistent in case @@ -1016,62 +1005,17 @@ ModRefInfo BasicAAResult::getModRefInfo(const CallBase *Call1, return AAResultBase::getModRefInfo(Call1, Call2, AAQI); } -// 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. -// The same applies if (b) is based on a GlobalVariable. Note that just being -// based on isIdentifiedObject() is not enough - we need an identified object -// that does not permit access to negative offsets. For example, a negative -// offset from a noalias argument or call can be inbounds w.r.t the actual -// underlying object. -// -// For example, consider: -// -// struct { int f0, int f1, ...} foo; -// foo alloca; -// foo* random = bar(alloca); -// int *f0 = &alloca.f0 -// int *f1 = &random->f1; -// -// Which is lowered, approximately, to: -// -// %alloca = alloca %struct.foo -// %random = call %struct.foo* @random(%struct.foo* %alloca) -// %f0 = getelementptr inbounds %struct, %struct.foo* %alloca, i32 0, i32 0 -// %f1 = getelementptr inbounds %struct, %struct.foo* %random, i32 0, i32 1 -// -// Assume %f1 and %f0 alias. Then %f1 would point into the object allocated -// by %alloca. Since the %f1 GEP is inbounds, that means %random must also -// point into the same object. But since %f0 points to the beginning of %alloca, -// the highest %f1 can be is (%alloca + 3). This means %random can not be higher -// than (%alloca - 1), and so is not inbounds, a contradiction. -bool BasicAAResult::isGEPBaseAtNegativeOffset(const GEPOperator *GEPOp, - const DecomposedGEP &DecompGEP, const DecomposedGEP &DecompObject, - LocationSize MaybeObjectAccessSize) { - // If the object access size is unknown, or the GEP isn't inbounds, bail. - if (!MaybeObjectAccessSize.hasValue() || !GEPOp->isInBounds()) - return false; - - const uint64_t ObjectAccessSize = MaybeObjectAccessSize.getValue(); - - // We need the object to be an alloca or a globalvariable, and want to know - // the offset of the pointer from the object precisely, so no variable - // indices are allowed. - if (!(isa<AllocaInst>(DecompObject.Base) || - isa<GlobalVariable>(DecompObject.Base)) || - !DecompObject.VarIndices.empty()) - 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 can't get exact GEP offset to identify pointer alias. So return - // false in that case. - if (!DecompGEP.VarIndices.empty()) - return false; - - return DecompGEP.Offset.sge(DecompObject.Offset + (int64_t)ObjectAccessSize); +/// Return true if we know V to the base address of the corresponding memory +/// object. This implies that any address less than V must be out of bounds +/// for the underlying object. Note that just being isIdentifiedObject() is +/// not enough - For example, a negative offset from a noalias argument or call +/// can be inbounds w.r.t the actual underlying object. +static bool isBaseOfObject(const Value *V) { + // TODO: We can handle other cases here + // 1) For GC languages, arguments to functions are often required to be + // base pointers. + // 2) Result of allocation routines are often base pointers. Leverage TLI. + return (isa<AllocaInst>(V) || isa<GlobalVariable>(V)); } /// Provides a bunch of ad-hoc rules to disambiguate a GEP instruction against @@ -1081,9 +1025,24 @@ bool BasicAAResult::isGEPBaseAtNegativeOffset(const GEPOperator *GEPOp, /// UnderlyingV1 is getUnderlyingObject(GEP1), UnderlyingV2 is the same for /// V2. AliasResult BasicAAResult::aliasGEP( - const GEPOperator *GEP1, LocationSize V1Size, const AAMDNodes &V1AAInfo, - const Value *V2, LocationSize V2Size, const AAMDNodes &V2AAInfo, + const GEPOperator *GEP1, LocationSize V1Size, + const Value *V2, LocationSize V2Size, const Value *UnderlyingV1, const Value *UnderlyingV2, AAQueryInfo &AAQI) { + if (!V1Size.hasValue() && !V2Size.hasValue()) { + // TODO: This limitation exists for compile-time reasons. Relax it if we + // can avoid exponential pathological cases. + if (!isa<GEPOperator>(V2)) + return AliasResult::MayAlias; + + // If both accesses have unknown size, we can only check whether the base + // objects don't alias. + AliasResult BaseAlias = getBestAAResults().alias( + MemoryLocation::getBeforeOrAfter(UnderlyingV1), + MemoryLocation::getBeforeOrAfter(UnderlyingV2), AAQI); + return BaseAlias == AliasResult::NoAlias ? AliasResult::NoAlias + : AliasResult::MayAlias; + } + DecomposedGEP DecompGEP1 = DecomposeGEPExpression(GEP1, DL, &AC, DT); DecomposedGEP DecompGEP2 = DecomposeGEPExpression(V2, DL, &AC, DT); @@ -1091,108 +1050,95 @@ AliasResult BasicAAResult::aliasGEP( // compile-time constant. if (!DecompGEP1.HasCompileTimeConstantScale || !DecompGEP2.HasCompileTimeConstantScale) - return MayAlias; + return AliasResult::MayAlias; assert(DecompGEP1.Base == UnderlyingV1 && DecompGEP2.Base == 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(GEP1, DecompGEP1, DecompGEP2, V2Size)) - 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<GEPOperator>(V2)) { - // Check for the GEP base being at a negative offset, this time in the other - // direction. - if (isGEPBaseAtNegativeOffset(GEP2, DecompGEP2, DecompGEP1, V1Size)) - return NoAlias; - // Do the base pointers alias? - AliasResult BaseAlias = getBestAAResults().alias( - MemoryLocation::getBeforeOrAfter(UnderlyingV1), - MemoryLocation::getBeforeOrAfter(UnderlyingV2), AAQI); - - // For GEPs with identical offsets, we can preserve the size and AAInfo - // when performing the alias check on the underlying objects. - if (BaseAlias == MayAlias && DecompGEP1.Offset == DecompGEP2.Offset && - DecompGEP1.VarIndices == DecompGEP2.VarIndices) { - AliasResult PreciseBaseAlias = getBestAAResults().alias( - MemoryLocation(UnderlyingV1, V1Size, V1AAInfo), - MemoryLocation(UnderlyingV2, V2Size, V2AAInfo), AAQI); - if (PreciseBaseAlias == NoAlias) - return NoAlias; - } - - // If we get a No or May, then return it immediately, no amount of analysis - // will improve this situation. - if (BaseAlias != MustAlias) { - assert(BaseAlias == NoAlias || BaseAlias == MayAlias); - return BaseAlias; - } - - // Subtract the GEP2 pointer from the GEP1 pointer to find out their - // symbolic difference. - DecompGEP1.Offset -= DecompGEP2.Offset; - GetIndexDifference(DecompGEP1.VarIndices, DecompGEP2.VarIndices); - - } else { - // Check to see if these two pointers are related by the getelementptr - // instruction. If one pointer is a GEP with a non-zero index of the other - // pointer, we know they cannot alias. - - // If both accesses are unknown size, we can't do anything useful here. - if (!V1Size.hasValue() && !V2Size.hasValue()) - return MayAlias; - - AliasResult R = getBestAAResults().alias( - MemoryLocation::getBeforeOrAfter(UnderlyingV1), - MemoryLocation(V2, V2Size, V2AAInfo), AAQI); - if (R != MustAlias) { - // If V2 may alias GEP base pointer, conservatively returns MayAlias. - // If V2 is known not to alias GEP base pointer, then the two values - // cannot alias per GEP semantics: "Any memory access must be done through - // a pointer value associated with an address range of the memory access, - // otherwise the behavior is undefined.". - assert(R == NoAlias || R == MayAlias); - return R; - } + // Subtract the GEP2 pointer from the GEP1 pointer to find out their + // symbolic difference. + DecompGEP1.Offset -= DecompGEP2.Offset; + GetIndexDifference(DecompGEP1.VarIndices, DecompGEP2.VarIndices); + + // If an inbounds GEP would have to start from an out of bounds address + // for the two to alias, then we can assume noalias. + if (*DecompGEP1.InBounds && DecompGEP1.VarIndices.empty() && + V2Size.hasValue() && DecompGEP1.Offset.sge(V2Size.getValue()) && + isBaseOfObject(DecompGEP2.Base)) + return AliasResult::NoAlias; + + if (isa<GEPOperator>(V2)) { + // Symmetric case to above. + if (*DecompGEP2.InBounds && DecompGEP1.VarIndices.empty() && + V1Size.hasValue() && DecompGEP1.Offset.sle(-V1Size.getValue()) && + isBaseOfObject(DecompGEP1.Base)) + return AliasResult::NoAlias; } - // In the two GEP Case, if there is no difference in the offsets of the - // computed pointers, the resultant pointers are a must alias. This - // happens when we have two lexically identical GEP's (for example). - // - // In the other case, if we have getelementptr <ptr>, 0, 0, 0, 0, ... and V2 - // must aliases the GEP, the end result is a must alias also. + // For GEPs with identical offsets, we can preserve the size and AAInfo + // when performing the alias check on the underlying objects. if (DecompGEP1.Offset == 0 && DecompGEP1.VarIndices.empty()) - return MustAlias; + return getBestAAResults().alias( + MemoryLocation(UnderlyingV1, V1Size), + MemoryLocation(UnderlyingV2, V2Size), AAQI); + + // Do the base pointers alias? + AliasResult BaseAlias = getBestAAResults().alias( + MemoryLocation::getBeforeOrAfter(UnderlyingV1), + MemoryLocation::getBeforeOrAfter(UnderlyingV2), AAQI); + + // If we get a No or May, then return it immediately, no amount of analysis + // will improve this situation. + if (BaseAlias != AliasResult::MustAlias) { + assert(BaseAlias == AliasResult::NoAlias || + BaseAlias == AliasResult::MayAlias); + return BaseAlias; + } // If there is a constant difference between the pointers, but the difference // is less than the size of the associated memory object, then we know // that the objects are partially overlapping. If the difference is // greater, we know they do not overlap. if (DecompGEP1.Offset != 0 && DecompGEP1.VarIndices.empty()) { - if (DecompGEP1.Offset.sge(0)) { - if (V2Size.hasValue()) { - if (DecompGEP1.Offset.ult(V2Size.getValue())) - return PartialAlias; - return NoAlias; - } - } else { - // We have the situation where: + APInt &Off = DecompGEP1.Offset; + + // Initialize for Off >= 0 (V2 <= GEP1) case. + const Value *LeftPtr = V2; + const Value *RightPtr = GEP1; + LocationSize VLeftSize = V2Size; + LocationSize VRightSize = V1Size; + const bool Swapped = Off.isNegative(); + + if (Swapped) { + // Swap if we have the situation where: // + + // | BaseOffset | // ---------------->| // |-->V1Size |-------> V2Size // GEP1 V2 - if (V1Size.hasValue()) { - if ((-DecompGEP1.Offset).ult(V1Size.getValue())) - return PartialAlias; - return NoAlias; + std::swap(LeftPtr, RightPtr); + std::swap(VLeftSize, VRightSize); + Off = -Off; + } + + if (VLeftSize.hasValue()) { + const uint64_t LSize = VLeftSize.getValue(); + if (Off.ult(LSize)) { + // Conservatively drop processing if a phi was visited and/or offset is + // too big. + AliasResult AR = AliasResult::PartialAlias; + if (VRightSize.hasValue() && Off.ule(INT32_MAX) && + (Off + VRightSize.getValue()).ule(LSize)) { + // Memory referenced by right pointer is nested. Save the offset in + // cache. Note that originally offset estimated as GEP1-V2, but + // AliasResult contains the shift that represents GEP1+Offset=V2. + AR.setOffset(-Off.getSExtValue()); + AR.swap(Swapped); + } + return AR; } + return AliasResult::NoAlias; } } @@ -1201,11 +1147,16 @@ AliasResult BasicAAResult::aliasGEP( bool AllNonNegative = DecompGEP1.Offset.isNonNegative(); bool AllNonPositive = DecompGEP1.Offset.isNonPositive(); for (unsigned i = 0, e = DecompGEP1.VarIndices.size(); i != e; ++i) { - const APInt &Scale = DecompGEP1.VarIndices[i].Scale; + APInt Scale = DecompGEP1.VarIndices[i].Scale; + APInt ScaleForGCD = DecompGEP1.VarIndices[i].Scale; + if (!DecompGEP1.VarIndices[i].IsNSW) + ScaleForGCD = APInt::getOneBitSet(Scale.getBitWidth(), + Scale.countTrailingZeros()); + if (i == 0) - GCD = Scale.abs(); + GCD = ScaleForGCD.abs(); else - GCD = APIntOps::GreatestCommonDivisor(GCD, Scale.abs()); + GCD = APIntOps::GreatestCommonDivisor(GCD, ScaleForGCD.abs()); if (AllNonNegative || AllNonPositive) { // If the Value could change between cycles, then any reasoning about @@ -1243,7 +1194,7 @@ AliasResult BasicAAResult::aliasGEP( if (V1Size.hasValue() && V2Size.hasValue() && ModOffset.uge(V2Size.getValue()) && (GCD - ModOffset).uge(V1Size.getValue())) - return NoAlias; + return AliasResult::NoAlias; // If we know all the variables are non-negative, then the total offset is // also non-negative and >= DecompGEP1.Offset. We have the following layout: @@ -1251,14 +1202,14 @@ AliasResult BasicAAResult::aliasGEP( // If DecompGEP1.Offset >= V2Size, the accesses don't alias. if (AllNonNegative && V2Size.hasValue() && DecompGEP1.Offset.uge(V2Size.getValue())) - return NoAlias; + return AliasResult::NoAlias; // Similarly, if the variables are non-positive, then the total offset is // also non-positive and <= DecompGEP1.Offset. We have the following layout: // [TotalOffset, TotalOffset+V1Size) ... [0, V2Size) // If -DecompGEP1.Offset >= V1Size, the accesses don't alias. if (AllNonPositive && V1Size.hasValue() && (-DecompGEP1.Offset).uge(V1Size.getValue())) - return NoAlias; + return AliasResult::NoAlias; if (V1Size.hasValue() && V2Size.hasValue()) { // Try to determine whether abs(VarIndex) > 0. @@ -1289,19 +1240,19 @@ AliasResult BasicAAResult::aliasGEP( // or higher both do not alias. if (OffsetLo.isNegative() && (-OffsetLo).uge(V1Size.getValue()) && OffsetHi.isNonNegative() && OffsetHi.uge(V2Size.getValue())) - return NoAlias; + return AliasResult::NoAlias; } } if (constantOffsetHeuristic(DecompGEP1.VarIndices, V1Size, V2Size, DecompGEP1.Offset, &AC, DT)) - return NoAlias; + return AliasResult::NoAlias; } // Statically, we can see that the base objects are the same, but the // pointers have dynamic offsets which we can't resolve. And none of our // little tricks above worked. - return MayAlias; + return AliasResult::MayAlias; } static AliasResult MergeAliasResults(AliasResult A, AliasResult B) { @@ -1309,56 +1260,55 @@ static AliasResult MergeAliasResults(AliasResult A, AliasResult B) { if (A == B) return A; // A mix of PartialAlias and MustAlias is PartialAlias. - if ((A == PartialAlias && B == MustAlias) || - (B == PartialAlias && A == MustAlias)) - return PartialAlias; + if ((A == AliasResult::PartialAlias && B == AliasResult::MustAlias) || + (B == AliasResult::PartialAlias && A == AliasResult::MustAlias)) + return AliasResult::PartialAlias; // Otherwise, we don't know anything. - return MayAlias; + return AliasResult::MayAlias; } /// Provides a bunch of ad-hoc rules to disambiguate a Select instruction /// against another. AliasResult BasicAAResult::aliasSelect(const SelectInst *SI, LocationSize SISize, - const AAMDNodes &SIAAInfo, const Value *V2, - LocationSize V2Size, const AAMDNodes &V2AAInfo, + const Value *V2, LocationSize V2Size, AAQueryInfo &AAQI) { // If the values are Selects with the same condition, we can do a more precise // check: just check for aliases between the values on corresponding arms. if (const SelectInst *SI2 = dyn_cast<SelectInst>(V2)) if (SI->getCondition() == SI2->getCondition()) { AliasResult Alias = getBestAAResults().alias( - MemoryLocation(SI->getTrueValue(), SISize, SIAAInfo), - MemoryLocation(SI2->getTrueValue(), V2Size, V2AAInfo), AAQI); - if (Alias == MayAlias) - return MayAlias; + MemoryLocation(SI->getTrueValue(), SISize), + MemoryLocation(SI2->getTrueValue(), V2Size), AAQI); + if (Alias == AliasResult::MayAlias) + return AliasResult::MayAlias; AliasResult ThisAlias = getBestAAResults().alias( - MemoryLocation(SI->getFalseValue(), SISize, SIAAInfo), - MemoryLocation(SI2->getFalseValue(), V2Size, V2AAInfo), AAQI); + MemoryLocation(SI->getFalseValue(), SISize), + MemoryLocation(SI2->getFalseValue(), V2Size), AAQI); return MergeAliasResults(ThisAlias, Alias); } // If both arms of the Select node NoAlias or MustAlias V2, then returns // NoAlias / MustAlias. Otherwise, returns MayAlias. AliasResult Alias = getBestAAResults().alias( - MemoryLocation(V2, V2Size, V2AAInfo), - MemoryLocation(SI->getTrueValue(), SISize, SIAAInfo), AAQI); - if (Alias == MayAlias) - return MayAlias; + MemoryLocation(V2, V2Size), + MemoryLocation(SI->getTrueValue(), SISize), AAQI); + if (Alias == AliasResult::MayAlias) + return AliasResult::MayAlias; AliasResult ThisAlias = getBestAAResults().alias( - MemoryLocation(V2, V2Size, V2AAInfo), - MemoryLocation(SI->getFalseValue(), SISize, SIAAInfo), AAQI); + MemoryLocation(V2, V2Size), + MemoryLocation(SI->getFalseValue(), SISize), AAQI); return MergeAliasResults(ThisAlias, Alias); } /// Provide a bunch of ad-hoc rules to disambiguate a PHI instruction against /// another. AliasResult BasicAAResult::aliasPHI(const PHINode *PN, LocationSize PNSize, - const AAMDNodes &PNAAInfo, const Value *V2, - LocationSize V2Size, - const AAMDNodes &V2AAInfo, + const Value *V2, LocationSize V2Size, AAQueryInfo &AAQI) { + if (!PN->getNumIncomingValues()) + return AliasResult::NoAlias; // If the values are PHIs in the same block, we can do a more precise // as well as efficient check: just check for aliases between the values // on corresponding edges. @@ -1367,16 +1317,15 @@ AliasResult BasicAAResult::aliasPHI(const PHINode *PN, LocationSize PNSize, Optional<AliasResult> Alias; for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { AliasResult ThisAlias = getBestAAResults().alias( - MemoryLocation(PN->getIncomingValue(i), PNSize, PNAAInfo), + MemoryLocation(PN->getIncomingValue(i), PNSize), MemoryLocation( - PN2->getIncomingValueForBlock(PN->getIncomingBlock(i)), V2Size, - V2AAInfo), + PN2->getIncomingValueForBlock(PN->getIncomingBlock(i)), V2Size), AAQI); if (Alias) *Alias = MergeAliasResults(*Alias, ThisAlias); else Alias = ThisAlias; - if (*Alias == MayAlias) + if (*Alias == AliasResult::MayAlias) break; } return *Alias; @@ -1405,7 +1354,7 @@ AliasResult BasicAAResult::aliasPHI(const PHINode *PN, LocationSize PNSize, // is if both sides are PHI nodes. In which case, this is O(m x n) time // where 'm' and 'n' are the number of PHI sources. if (PhiValueSet.size() > MaxLookupSearchDepth) - return MayAlias; + return AliasResult::MayAlias; // Add the values to V1Srcs for (Value *PV1 : PhiValueSet) { if (CheckForRecPhi(PV1)) @@ -1416,13 +1365,19 @@ AliasResult BasicAAResult::aliasPHI(const PHINode *PN, LocationSize PNSize, // If we don't have PhiInfo then just look at the operands of the phi itself // FIXME: Remove this once we can guarantee that we have PhiInfo always SmallPtrSet<Value *, 4> UniqueSrc; + Value *OnePhi = nullptr; for (Value *PV1 : PN->incoming_values()) { - if (isa<PHINode>(PV1)) - // If any of the source itself is a PHI, return MayAlias conservatively - // to avoid compile time explosion. The worst possible case is if both - // 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 (isa<PHINode>(PV1)) { + if (OnePhi && OnePhi != PV1) { + // To control potential compile time explosion, we choose to be + // conserviate when we have more than one Phi input. It is important + // that we handle the single phi case as that lets us handle LCSSA + // phi nodes and (combined with the recursive phi handling) simple + // pointer induction variable patterns. + return AliasResult::MayAlias; + } + OnePhi = PV1; + } if (CheckForRecPhi(PV1)) continue; @@ -1430,13 +1385,18 @@ AliasResult BasicAAResult::aliasPHI(const PHINode *PN, LocationSize PNSize, if (UniqueSrc.insert(PV1).second) V1Srcs.push_back(PV1); } + + if (OnePhi && UniqueSrc.size() > 1) + // Out of an abundance of caution, allow only the trivial lcssa and + // recursive phi cases. + return AliasResult::MayAlias; } // If V1Srcs is empty then that means that the phi has no underlying non-phi // value. This should only be possible in blocks unreachable from the entry // block, but return MayAlias just in case. if (V1Srcs.empty()) - return MayAlias; + return AliasResult::MayAlias; // If this PHI node is recursive, indicate that the pointer may be moved // across iterations. We can only prove NoAlias if different underlying @@ -1456,21 +1416,21 @@ AliasResult BasicAAResult::aliasPHI(const PHINode *PN, LocationSize PNSize, // If we inserted a block into VisitedPhiBBs, alias analysis results that // have been cached earlier may no longer be valid. Perform recursive queries // with a new AAQueryInfo. - AAQueryInfo NewAAQI; + AAQueryInfo NewAAQI = AAQI.withEmptyCache(); AAQueryInfo *UseAAQI = BlockInserted ? &NewAAQI : &AAQI; AliasResult Alias = getBestAAResults().alias( - MemoryLocation(V2, V2Size, V2AAInfo), - MemoryLocation(V1Srcs[0], PNSize, PNAAInfo), *UseAAQI); + MemoryLocation(V2, V2Size), + MemoryLocation(V1Srcs[0], PNSize), *UseAAQI); // Early exit if the check of the first PHI source against V2 is MayAlias. // Other results are not possible. - if (Alias == MayAlias) - return MayAlias; + if (Alias == AliasResult::MayAlias) + return AliasResult::MayAlias; // With recursive phis we cannot guarantee that MustAlias/PartialAlias will // remain valid to all elements and needs to conservatively return MayAlias. - if (isRecursive && Alias != NoAlias) - return MayAlias; + if (isRecursive && Alias != AliasResult::NoAlias) + return AliasResult::MayAlias; // If all sources of the PHI node NoAlias or MustAlias V2, then returns // NoAlias / MustAlias. Otherwise, returns MayAlias. @@ -1478,10 +1438,9 @@ AliasResult BasicAAResult::aliasPHI(const PHINode *PN, LocationSize PNSize, Value *V = V1Srcs[i]; AliasResult ThisAlias = getBestAAResults().alias( - MemoryLocation(V2, V2Size, V2AAInfo), - MemoryLocation(V, PNSize, PNAAInfo), *UseAAQI); + MemoryLocation(V2, V2Size), MemoryLocation(V, PNSize), *UseAAQI); Alias = MergeAliasResults(ThisAlias, Alias); - if (Alias == MayAlias) + if (Alias == AliasResult::MayAlias) break; } @@ -1491,23 +1450,21 @@ AliasResult BasicAAResult::aliasPHI(const PHINode *PN, LocationSize PNSize, /// Provides a bunch of ad-hoc rules to disambiguate in common cases, such as /// array references. AliasResult BasicAAResult::aliasCheck(const Value *V1, LocationSize V1Size, - const AAMDNodes &V1AAInfo, const Value *V2, LocationSize V2Size, - const AAMDNodes &V2AAInfo, AAQueryInfo &AAQI) { // If either of the memory references is empty, it doesn't matter what the // pointer values are. if (V1Size.isZero() || V2Size.isZero()) - return NoAlias; + return AliasResult::NoAlias; // Strip off any casts if they exist. - V1 = V1->stripPointerCastsAndInvariantGroups(); - V2 = V2->stripPointerCastsAndInvariantGroups(); + V1 = V1->stripPointerCastsForAliasAnalysis(); + V2 = V2->stripPointerCastsForAliasAnalysis(); // If V1 or V2 is undef, the result is NoAlias because we can always pick a // value for undef that aliases nothing in the program. if (isa<UndefValue>(V1) || isa<UndefValue>(V2)) - return NoAlias; + return AliasResult::NoAlias; // Are we checking for alias of the same value? // Because we look 'through' phi nodes, we could look at "Value" pointers from @@ -1516,10 +1473,10 @@ AliasResult BasicAAResult::aliasCheck(const Value *V1, LocationSize V1Size, // happen by looking at the visited phi nodes and making sure they cannot // reach the value. if (isValueEqualInPotentialCycles(V1, V2)) - return MustAlias; + return AliasResult::MustAlias; if (!V1->getType()->isPointerTy() || !V2->getType()->isPointerTy()) - return NoAlias; // Scalars cannot alias each other + return AliasResult::NoAlias; // Scalars cannot alias each other // Figure out what objects these things are pointing to if we can. const Value *O1 = getUnderlyingObject(V1, MaxLookupSearchDepth); @@ -1529,26 +1486,26 @@ AliasResult BasicAAResult::aliasCheck(const Value *V1, LocationSize V1Size, // don't alias any other pointer. if (const ConstantPointerNull *CPN = dyn_cast<ConstantPointerNull>(O1)) if (!NullPointerIsDefined(&F, CPN->getType()->getAddressSpace())) - return NoAlias; + return AliasResult::NoAlias; if (const ConstantPointerNull *CPN = dyn_cast<ConstantPointerNull>(O2)) if (!NullPointerIsDefined(&F, CPN->getType()->getAddressSpace())) - return NoAlias; + return AliasResult::NoAlias; if (O1 != O2) { // If V1/V2 point to two different objects, we know that we have no alias. if (isIdentifiedObject(O1) && isIdentifiedObject(O2)) - return NoAlias; + return AliasResult::NoAlias; // Constant pointers can't alias with non-const isIdentifiedObject objects. if ((isa<Constant>(O1) && isIdentifiedObject(O2) && !isa<Constant>(O2)) || (isa<Constant>(O2) && isIdentifiedObject(O1) && !isa<Constant>(O1))) - return NoAlias; + return AliasResult::NoAlias; // Function arguments can't alias with things that are known to be // unambigously identified at the function level. if ((isa<Argument>(O1) && isIdentifiedFunctionLocal(O2)) || (isa<Argument>(O2) && isIdentifiedFunctionLocal(O1))) - return NoAlias; + return AliasResult::NoAlias; // If one pointer is the result of a call/invoke or load and the other is a // non-escaping local object within the same function, then we know the @@ -1561,10 +1518,10 @@ AliasResult BasicAAResult::aliasCheck(const Value *V1, LocationSize V1Size, // nocapture value to other functions as long as they don't capture it. if (isEscapeSource(O1) && isNonEscapingLocalObject(O2, &AAQI.IsCapturedCache)) - return NoAlias; + return AliasResult::NoAlias; if (isEscapeSource(O2) && isNonEscapingLocalObject(O1, &AAQI.IsCapturedCache)) - return NoAlias; + return AliasResult::NoAlias; } // If the size of one access is larger than the entire object on the other @@ -1576,7 +1533,7 @@ AliasResult BasicAAResult::aliasCheck(const Value *V1, LocationSize V1Size, (isObjectSmallerThan( O1, getMinimalExtentFrom(*V2, V2Size, DL, NullIsValidLocation), DL, TLI, NullIsValidLocation))) - return NoAlias; + return AliasResult::NoAlias; // If one the accesses may be before the accessed pointer, canonicalize this // by using unknown after-pointer sizes for both accesses. This is @@ -1590,14 +1547,21 @@ AliasResult BasicAAResult::aliasCheck(const Value *V1, LocationSize V1Size, V2Size = LocationSize::afterPointer(); } + // FIXME: If this depth limit is hit, then we may cache sub-optimal results + // for recursive queries. For this reason, this limit is chosen to be large + // enough to be very rarely hit, while still being small enough to avoid + // stack overflows. + if (AAQI.Depth >= 512) + return AliasResult::MayAlias; + // Check the cache before climbing up use-def chains. This also terminates // otherwise infinitely recursive queries. - AAQueryInfo::LocPair Locs(MemoryLocation(V1, V1Size, V1AAInfo), - MemoryLocation(V2, V2Size, V2AAInfo)); - if (V1 > V2) + AAQueryInfo::LocPair Locs({V1, V1Size}, {V2, V2Size}); + const bool Swapped = V1 > V2; + if (Swapped) std::swap(Locs.first, Locs.second); const auto &Pair = AAQI.AliasCache.try_emplace( - Locs, AAQueryInfo::CacheEntry{NoAlias, 0}); + Locs, AAQueryInfo::CacheEntry{AliasResult::NoAlias, 0}); if (!Pair.second) { auto &Entry = Pair.first->second; if (!Entry.isDefinitive()) { @@ -1605,26 +1569,32 @@ AliasResult BasicAAResult::aliasCheck(const Value *V1, LocationSize V1Size, ++Entry.NumAssumptionUses; ++AAQI.NumAssumptionUses; } - return Entry.Result; + // Cache contains sorted {V1,V2} pairs but we should return original order. + auto Result = Entry.Result; + Result.swap(Swapped); + return Result; } int OrigNumAssumptionUses = AAQI.NumAssumptionUses; unsigned OrigNumAssumptionBasedResults = AAQI.AssumptionBasedResults.size(); - AliasResult Result = aliasCheckRecursive(V1, V1Size, V1AAInfo, V2, V2Size, - V2AAInfo, AAQI, O1, O2); + AliasResult Result = + aliasCheckRecursive(V1, V1Size, V2, V2Size, AAQI, O1, O2); auto It = AAQI.AliasCache.find(Locs); assert(It != AAQI.AliasCache.end() && "Must be in cache"); auto &Entry = It->second; // Check whether a NoAlias assumption has been used, but disproven. - bool AssumptionDisproven = Entry.NumAssumptionUses > 0 && Result != NoAlias; + bool AssumptionDisproven = + Entry.NumAssumptionUses > 0 && Result != AliasResult::NoAlias; if (AssumptionDisproven) - Result = MayAlias; + Result = AliasResult::MayAlias; // This is a definitive result now, when considered as a root query. AAQI.NumAssumptionUses -= Entry.NumAssumptionUses; Entry.Result = Result; + // Cache contains sorted {V1,V2} pairs. + Entry.Result.swap(Swapped); Entry.NumAssumptionUses = -1; // If the assumption has been disproven, remove any results that may have @@ -1636,48 +1606,43 @@ AliasResult BasicAAResult::aliasCheck(const Value *V1, LocationSize V1Size, // The result may still be based on assumptions higher up in the chain. // Remember it, so it can be purged from the cache later. - if (OrigNumAssumptionUses != AAQI.NumAssumptionUses && Result != MayAlias) + if (OrigNumAssumptionUses != AAQI.NumAssumptionUses && + Result != AliasResult::MayAlias) AAQI.AssumptionBasedResults.push_back(Locs); return Result; } AliasResult BasicAAResult::aliasCheckRecursive( - const Value *V1, LocationSize V1Size, const AAMDNodes &V1AAInfo, - const Value *V2, LocationSize V2Size, const AAMDNodes &V2AAInfo, + const Value *V1, LocationSize V1Size, + const Value *V2, LocationSize V2Size, AAQueryInfo &AAQI, const Value *O1, const Value *O2) { if (const GEPOperator *GV1 = dyn_cast<GEPOperator>(V1)) { - AliasResult Result = - aliasGEP(GV1, V1Size, V1AAInfo, V2, V2Size, V2AAInfo, O1, O2, AAQI); - if (Result != MayAlias) + AliasResult Result = aliasGEP(GV1, V1Size, V2, V2Size, O1, O2, AAQI); + if (Result != AliasResult::MayAlias) return Result; } else if (const GEPOperator *GV2 = dyn_cast<GEPOperator>(V2)) { - AliasResult Result = - aliasGEP(GV2, V2Size, V2AAInfo, V1, V1Size, V1AAInfo, O2, O1, AAQI); - if (Result != MayAlias) + AliasResult Result = aliasGEP(GV2, V2Size, V1, V1Size, O2, O1, AAQI); + if (Result != AliasResult::MayAlias) return Result; } if (const PHINode *PN = dyn_cast<PHINode>(V1)) { - AliasResult Result = - aliasPHI(PN, V1Size, V1AAInfo, V2, V2Size, V2AAInfo, AAQI); - if (Result != MayAlias) + AliasResult Result = aliasPHI(PN, V1Size, V2, V2Size, AAQI); + if (Result != AliasResult::MayAlias) return Result; } else if (const PHINode *PN = dyn_cast<PHINode>(V2)) { - AliasResult Result = - aliasPHI(PN, V2Size, V2AAInfo, V1, V1Size, V1AAInfo, AAQI); - if (Result != MayAlias) + AliasResult Result = aliasPHI(PN, V2Size, V1, V1Size, AAQI); + if (Result != AliasResult::MayAlias) return Result; } if (const SelectInst *S1 = dyn_cast<SelectInst>(V1)) { - AliasResult Result = - aliasSelect(S1, V1Size, V1AAInfo, V2, V2Size, V2AAInfo, AAQI); - if (Result != MayAlias) + AliasResult Result = aliasSelect(S1, V1Size, V2, V2Size, AAQI); + if (Result != AliasResult::MayAlias) return Result; } else if (const SelectInst *S2 = dyn_cast<SelectInst>(V2)) { - AliasResult Result = - aliasSelect(S2, V2Size, V2AAInfo, V1, V1Size, V1AAInfo, AAQI); - if (Result != MayAlias) + AliasResult Result = aliasSelect(S2, V2Size, V1, V1Size, AAQI); + if (Result != AliasResult::MayAlias) return Result; } @@ -1688,10 +1653,10 @@ AliasResult BasicAAResult::aliasCheckRecursive( if (V1Size.isPrecise() && V2Size.isPrecise() && (isObjectSize(O1, V1Size.getValue(), DL, TLI, NullIsValidLocation) || isObjectSize(O2, V2Size.getValue(), DL, TLI, NullIsValidLocation))) - return PartialAlias; + return AliasResult::PartialAlias; } - return MayAlias; + return AliasResult::MayAlias; } /// Check whether two Values can be considered equivalent. @@ -1720,7 +1685,7 @@ bool BasicAAResult::isValueEqualInPotentialCycles(const Value *V, // the Values cannot come from different iterations of a potential cycle the // phi nodes could be involved in. for (auto *P : VisitedPhiBBs) - if (isPotentiallyReachable(&P->front(), Inst, nullptr, DT, LI)) + if (isPotentiallyReachable(&P->front(), Inst, nullptr, DT)) return false; return true; @@ -1750,9 +1715,10 @@ void BasicAAResult::GetIndexDifference( // If we found it, subtract off Scale V's from the entry in Dest. If it // goes to zero, remove the entry. - if (Dest[j].Scale != Scale) + if (Dest[j].Scale != Scale) { Dest[j].Scale -= Scale; - else + Dest[j].IsNSW = false; + } else Dest.erase(Dest.begin() + j); Scale = 0; break; @@ -1760,7 +1726,8 @@ void BasicAAResult::GetIndexDifference( // If we didn't consume this entry, add it to the end of the Dest list. if (!!Scale) { - VariableGEPIndex Entry = {V, ZExtBits, SExtBits, -Scale, Src[i].CxtI}; + VariableGEPIndex Entry = {V, ZExtBits, SExtBits, + -Scale, Src[i].CxtI, Src[i].IsNSW}; Dest.push_back(Entry); } } @@ -1780,28 +1747,20 @@ bool BasicAAResult::constantOffsetHeuristic( const VariableGEPIndex &Var0 = VarIndices[0], &Var1 = VarIndices[1]; if (Var0.ZExtBits != Var1.ZExtBits || Var0.SExtBits != Var1.SExtBits || - Var0.Scale != -Var1.Scale) + Var0.Scale != -Var1.Scale || Var0.V->getType() != Var1.V->getType()) return false; - unsigned Width = Var1.V->getType()->getIntegerBitWidth(); - // We'll strip off the Extensions of Var0 and Var1 and do another round // of GetLinearExpression decomposition. In the example above, if Var0 // is zext(%x + 1) we should get V1 == %x and V1Offset == 1. - APInt V0Scale(Width, 0), V0Offset(Width, 0), V1Scale(Width, 0), - V1Offset(Width, 0); - bool NSW = true, NUW = true; - unsigned V0ZExtBits = 0, V0SExtBits = 0, V1ZExtBits = 0, V1SExtBits = 0; - const Value *V0 = GetLinearExpression(Var0.V, V0Scale, V0Offset, V0ZExtBits, - V0SExtBits, DL, 0, AC, DT, NSW, NUW); - NSW = true; - NUW = true; - const Value *V1 = GetLinearExpression(Var1.V, V1Scale, V1Offset, V1ZExtBits, - V1SExtBits, DL, 0, AC, DT, NSW, NUW); - - if (V0Scale != V1Scale || V0ZExtBits != V1ZExtBits || - V0SExtBits != V1SExtBits || !isValueEqualInPotentialCycles(V0, V1)) + LinearExpression E0 = + GetLinearExpression(ExtendedValue(Var0.V), DL, 0, AC, DT); + LinearExpression E1 = + GetLinearExpression(ExtendedValue(Var1.V), DL, 0, AC, DT); + if (E0.Scale != E1.Scale || E0.Val.ZExtBits != E1.Val.ZExtBits || + E0.Val.SExtBits != E1.Val.SExtBits || + !isValueEqualInPotentialCycles(E0.Val.V, E1.Val.V)) return false; // We have a hit - Var0 and Var1 only differ by a constant offset! @@ -1811,7 +1770,7 @@ bool BasicAAResult::constantOffsetHeuristic( // minimum difference between the two. The minimum distance may occur due to // wrapping; consider "add i3 %i, 5": if %i == 7 then 7 + 5 mod 8 == 4, and so // the minimum distance between %i and %i + 5 is 3. - APInt MinDiff = V0Offset - V1Offset, Wrapped = -MinDiff; + APInt MinDiff = E0.Offset - E1.Offset, Wrapped = -MinDiff; MinDiff = APIntOps::umin(MinDiff, Wrapped); APInt MinDiffBytes = MinDiff.zextOrTrunc(Var0.Scale.getBitWidth()) * Var0.Scale.abs(); @@ -1834,9 +1793,8 @@ BasicAAResult BasicAA::run(Function &F, FunctionAnalysisManager &AM) { auto &TLI = AM.getResult<TargetLibraryAnalysis>(F); auto &AC = AM.getResult<AssumptionAnalysis>(F); auto *DT = &AM.getResult<DominatorTreeAnalysis>(F); - auto *LI = AM.getCachedResult<LoopAnalysis>(F); auto *PV = AM.getCachedResult<PhiValuesAnalysis>(F); - return BasicAAResult(F.getParent()->getDataLayout(), F, TLI, AC, DT, LI, PV); + return BasicAAResult(F.getParent()->getDataLayout(), F, TLI, AC, DT, PV); } BasicAAWrapperPass::BasicAAWrapperPass() : FunctionPass(ID) { @@ -1864,13 +1822,11 @@ bool BasicAAWrapperPass::runOnFunction(Function &F) { auto &ACT = getAnalysis<AssumptionCacheTracker>(); auto &TLIWP = getAnalysis<TargetLibraryInfoWrapperPass>(); auto &DTWP = getAnalysis<DominatorTreeWrapperPass>(); - auto *LIWP = getAnalysisIfAvailable<LoopInfoWrapperPass>(); auto *PVWP = getAnalysisIfAvailable<PhiValuesWrapperPass>(); Result.reset(new BasicAAResult(F.getParent()->getDataLayout(), F, TLIWP.getTLI(F), ACT.getAssumptionCache(F), &DTWP.getDomTree(), - LIWP ? &LIWP->getLoopInfo() : nullptr, PVWP ? &PVWP->getResult() : nullptr)); return false; |