isa<IntegerType>(MemsetType->getParamType(2)))
return true;
}
-
return false;
}
if (F->onlyAccessesArgMemory())
Min = FunctionModRefBehavior(Min & FMRB_OnlyAccessesArgumentPointees);
- if (isMemsetPattern16(F, TLI))
- Min = FMRB_OnlyAccessesArgumentPointees;
-
// Otherwise be conservative.
return FunctionModRefBehavior(AAResultBase::getModRefBehavior(F) & Min);
}
-ModRefInfo BasicAAResult::getArgModRefInfo(ImmutableCallSite CS,
- unsigned ArgIdx) {
+/// Returns true if this is a writeonly (i.e Mod only) parameter. Currently,
+/// we don't have a writeonly attribute, so this only knows about builtin
+/// intrinsics and target library functions. We could consider adding a
+/// writeonly attribute in the future and moving all of these facts to either
+/// Intrinsics.td or InferFunctionAttr.cpp
+static bool isWriteOnlyParam(ImmutableCallSite CS, unsigned ArgIdx,
+ const TargetLibraryInfo &TLI) {
if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(CS.getInstruction()))
switch (II->getIntrinsicID()) {
default:
case Intrinsic::memset:
case Intrinsic::memcpy:
case Intrinsic::memmove:
- assert((ArgIdx == 0 || ArgIdx == 1) &&
- "Invalid argument index for memory intrinsic");
- return ArgIdx ? MRI_Ref : MRI_Mod;
+ // We don't currently have a writeonly attribute. All other properties
+ // of these intrinsics are nicely described via attributes in
+ // Intrinsics.td and handled generically.
+ if (ArgIdx == 0)
+ return true;
}
// We can bound the aliasing properties of memset_pattern16 just as we can
// for memcpy/memset. This is particularly important because the
// LoopIdiomRecognizer likes to turn loops into calls to memset_pattern16
- // whenever possible.
- if (CS.getCalledFunction() &&
- isMemsetPattern16(CS.getCalledFunction(), TLI)) {
- assert((ArgIdx == 0 || ArgIdx == 1) &&
- "Invalid argument index for memset_pattern16");
- return ArgIdx ? MRI_Ref : MRI_Mod;
- }
- // FIXME: Handle memset_pattern4 and memset_pattern8 also.
+ // whenever possible. Note that all but the missing writeonly attribute are
+ // handled via InferFunctionAttr.
+ if (CS.getCalledFunction() && isMemsetPattern16(CS.getCalledFunction(), TLI))
+ if (ArgIdx == 0)
+ return true;
+
+ // TODO: memset_pattern4, memset_pattern8
+ // TODO: _chk variants
+ // TODO: strcmp, strcpy
+
+ return false;
+}
+
+ModRefInfo BasicAAResult::getArgModRefInfo(ImmutableCallSite CS,
+ unsigned ArgIdx) {
+
+ // Emulate the missing writeonly attribute by checking for known builtin
+ // intrinsics and target library functions.
+ if (isWriteOnlyParam(CS, ArgIdx, TLI))
+ return MRI_Mod;
+
+ if (CS.paramHasAttr(ArgIdx + 1, Attribute::ReadOnly))
+ return MRI_Ref;
+
+ if (CS.paramHasAttr(ArgIdx + 1, Attribute::ReadNone))
+ return MRI_NoModRef;
return AAResultBase::getArgModRefInfo(CS, ArgIdx);
}
static bool isAssumeIntrinsic(ImmutableCallSite CS) {
const IntrinsicInst *II = dyn_cast<IntrinsicInst>(CS.getInstruction());
- if (II && II->getIntrinsicID() == Intrinsic::assume)
- return true;
+ return II && II->getIntrinsicID() == Intrinsic::assume;
+}
- return false;
+#ifndef NDEBUG
+static const Function *getParent(const Value *V) {
+ if (const Instruction *inst = dyn_cast<Instruction>(V))
+ return inst->getParent()->getParent();
+
+ if (const Argument *arg = dyn_cast<Argument>(V))
+ return arg->getParent();
+
+ return nullptr;
+}
+
+static bool notDifferentParent(const Value *O1, const Value *O2) {
+
+ const Function *F1 = getParent(O1);
+ const Function *F2 = getParent(O2);
+
+ return !F1 || !F2 || F1 == F2;
+}
+#endif
+
+AliasResult BasicAAResult::alias(const MemoryLocation &LocA,
+ const MemoryLocation &LocB) {
+ assert(notDifferentParent(LocA.Ptr, LocB.Ptr) &&
+ "BasicAliasAnalysis doesn't support interprocedural queries.");
+
+ // If we have a directly cached entry for these locations, we have recursed
+ // through this once, so just return the cached results. Notably, when this
+ // happens, we don't clear the cache.
+ auto CacheIt = AliasCache.find(LocPair(LocA, LocB));
+ if (CacheIt != AliasCache.end())
+ return CacheIt->second;
+
+ AliasResult Alias = aliasCheck(LocA.Ptr, LocA.Size, LocA.AATags, LocB.Ptr,
+ LocB.Size, LocB.AATags);
+ // AliasCache rarely has more than 1 or 2 elements, always use
+ // shrink_and_clear so it quickly returns to the inline capacity of the
+ // SmallDenseMap if it ever grows larger.
+ // FIXME: This should really be shrink_to_inline_capacity_and_clear().
+ AliasCache.shrink_and_clear();
+ VisitedPhiBBs.clear();
+ return Alias;
}
/// Checks to see if the specified callsite can clobber the specified memory
ConstantInt *C2 =
dyn_cast<ConstantInt>(GEP2->getOperand(GEP2->getNumOperands() - 1));
- // If the last (struct) indices aren't constants, we can't say anything.
- // If they're identical, the other indices might be also be dynamically
- // equal, so the GEPs can alias.
- if (!C1 || !C2 || C1 == C2)
+ // If the last (struct) indices are constants and are equal, the other indices
+ // might be also be dynamically equal, so the GEPs can alias.
+ if (C1 && C2 && C1 == C2)
return MayAlias;
// Find the last-indexed type of the GEP, i.e., the type you'd get if
IntermediateIndices.push_back(GEP1->getOperand(i + 1));
}
- StructType *LastIndexedStruct =
- dyn_cast<StructType>(GetElementPtrInst::getIndexedType(
- GEP1->getSourceElementType(), IntermediateIndices));
+ auto *Ty = GetElementPtrInst::getIndexedType(
+ GEP1->getSourceElementType(), IntermediateIndices);
+ StructType *LastIndexedStruct = dyn_cast<StructType>(Ty);
- if (!LastIndexedStruct)
+ if (isa<SequentialType>(Ty)) {
+ // We know that:
+ // - both GEPs begin indexing from the exact same pointer;
+ // - the last indices in both GEPs are constants, indexing into a sequential
+ // type (array or pointer);
+ // - both GEPs only index through arrays prior to that.
+ //
+ // Because array indices greater than the number of elements are valid in
+ // GEPs, unless we know the intermediate indices are identical between
+ // GEP1 and GEP2 we cannot guarantee that the last indexed arrays don't
+ // partially overlap. We also need to check that the loaded size matches
+ // the element size, otherwise we could still have overlap.
+ const uint64_t ElementSize =
+ DL.getTypeStoreSize(cast<SequentialType>(Ty)->getElementType());
+ if (V1Size != ElementSize || V2Size != ElementSize)
+ return MayAlias;
+
+ for (unsigned i = 0, e = GEP1->getNumIndices() - 1; i != e; ++i)
+ if (GEP1->getOperand(i + 1) != GEP2->getOperand(i + 1))
+ return MayAlias;
+
+ // Now we know that the array/pointer that GEP1 indexes into and that
+ // that GEP2 indexes into must either precisely overlap or be disjoint.
+ // Because they cannot partially overlap and because fields in an array
+ // cannot overlap, if we can prove the final indices are different between
+ // GEP1 and GEP2, we can conclude GEP1 and GEP2 don't alias.
+
+ // If the last indices are constants, we've already checked they don't
+ // equal each other so we can exit early.
+ if (C1 && C2)
+ return NoAlias;
+ if (isKnownNonEqual(GEP1->getOperand(GEP1->getNumOperands() - 1),
+ GEP2->getOperand(GEP2->getNumOperands() - 1),
+ DL))
+ return NoAlias;
return MayAlias;
+ } else if (!LastIndexedStruct || !C1 || !C2) {
+ return MayAlias;
+ }
// We know that:
// - both GEPs begin indexing from the exact same pointer;
return Alias;
}
-/// Provideis a bunch of ad-hoc rules to disambiguate in common cases, such as
+/// Provides a bunch of ad-hoc rules to disambiguate in common cases, such as
/// array references.
AliasResult BasicAAResult::aliasCheck(const Value *V1, uint64_t V1Size,
AAMDNodes V1AAInfo, const Value *V2,
// 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->begin(), Inst, DT, LI))
+ if (isPotentiallyReachable(&P->front(), Inst, DT, LI))
return false;
return true;
// If we've been sext'ed then zext'd the maximum difference between Var0 and
// Var1 is possible to calculate, but we're just interested in the absolute
- // minumum difference between the two. The minimum distance may occur due to
+ // 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 = APInt::getMaxValue(Width) - MinDiff + APInt(Width, 1);
+ APInt MinDiff = V0Offset - V1Offset, Wrapped = -MinDiff;
MinDiff = APIntOps::umin(MinDiff, Wrapped);
uint64_t MinDiffBytes = MinDiff.getZExtValue() * std::abs(Var0.Scale);
AM->getCachedResult<LoopAnalysis>(F));
}
+BasicAAWrapperPass::BasicAAWrapperPass() : FunctionPass(ID) {
+ initializeBasicAAWrapperPassPass(*PassRegistry::getPassRegistry());
+}
+
char BasicAAWrapperPass::ID = 0;
void BasicAAWrapperPass::anchor() {}
projects / oota-llvm.git / blobdiff