67#define DEBUG_TYPE "basicaa"
74STATISTIC(SearchLimitReached,
"Number of times the limit to "
75 "decompose GEPs is reached");
76STATISTIC(SearchTimes,
"Number of times a GEP is decomposed");
84 FunctionAnalysisManager::Invalidator &Inv) {
107 bool RoundToAlign =
false) {
113 if (
Size->isScalable())
126 bool NullIsValidLoc) {
133 V.getPointerDereferenceableBytes(
DL, CanBeNull,
nullptr);
134 DerefBytes = (CanBeNull && NullIsValidLoc) ? 0 : DerefBytes;
148 bool NullIsValidLoc) {
186 std::optional<TypeSize> ObjectSize =
188 return ObjectSize && *ObjectSize ==
Size;
208 auto [CacheIt, Inserted] = IsCapturedCache.try_emplace(Object);
214 return ReturnCaptures ? CacheIt->second.WithRet : CacheIt->second.WithoutRet;
224 return Succs.
empty() ||
231 : DT(DT), LI(LI), CI(CI),
239 auto Iter = EarliestEscapes.try_emplace(Object);
244 Inst2Obj[EarliestInst].push_back(Object);
245 Iter.first->second = {EarliestInst, Res};
248 if (ReturnCaptures) {
249 assert(!
I &&
"Context instruction not supported if ReturnCaptures");
250 return Iter.first->second.second.WithRet;
253 auto IsNotCapturedBefore = [&]() {
255 Instruction *CaptureInst = Iter.first->second.first;
263 if (
I == CaptureInst) {
274 "Blocks were renumbered while EarliestEscapeAnalysis was alive");
275 auto [It, Inserted] = IsReachableCache.try_emplace(
286 return !callsReturnsTwiceFn();
288 if (IsNotCapturedBefore())
290 return Iter.first->second.second.WithoutRet;
293bool EarliestEscapeAnalysis::callsReturnsTwiceFn() {
294 if (!CallsReturnsTwiceFn)
295 CallsReturnsTwiceFn =
297 return *CallsReturnsTwiceFn;
301 auto Iter = Inst2Obj.find(
I);
302 if (Iter != Inst2Obj.end()) {
303 for (
const Value *Obj : Iter->second)
304 EarliestEscapes.erase(Obj);
310 for (
const Use &U :
I->operands()) {
311 if (!U->getType()->isPointerTy())
316 EarliestEscapes.clear();
331 unsigned ZExtBits = 0;
332 unsigned SExtBits = 0;
333 unsigned TruncBits = 0;
335 bool IsNonNegative =
false;
337 explicit CastedValue(
const Value *V) : V(V) {}
338 explicit CastedValue(
const Value *
V,
unsigned ZExtBits,
unsigned SExtBits,
339 unsigned TruncBits,
bool IsNonNegative)
340 :
V(
V), ZExtBits(ZExtBits), SExtBits(SExtBits), TruncBits(TruncBits),
341 IsNonNegative(IsNonNegative) {}
344 return V->getType()->getPrimitiveSizeInBits() - TruncBits + ZExtBits +
348 CastedValue withValue(
const Value *NewV,
bool PreserveNonNeg)
const {
349 return CastedValue(NewV, ZExtBits, SExtBits, TruncBits,
350 IsNonNegative && PreserveNonNeg);
354 CastedValue withZExtOfValue(
const Value *NewV,
bool ZExtNonNegative)
const {
355 unsigned ExtendBy =
V->getType()->getPrimitiveSizeInBits() -
357 if (ExtendBy <= TruncBits)
360 return CastedValue(NewV, ZExtBits, SExtBits, TruncBits - ExtendBy,
364 ExtendBy -= TruncBits;
369 return CastedValue(NewV, ZExtBits + SExtBits + ExtendBy, 0, 0,
374 CastedValue withSExtOfValue(
const Value *NewV)
const {
375 unsigned ExtendBy =
V->getType()->getPrimitiveSizeInBits() -
377 if (ExtendBy <= TruncBits)
380 return CastedValue(NewV, ZExtBits, SExtBits, TruncBits - ExtendBy,
384 ExtendBy -= TruncBits;
387 return CastedValue(NewV, ZExtBits, SExtBits + ExtendBy, 0, IsNonNegative);
390 APInt evaluateWith(APInt
N)
const {
391 assert(
N.getBitWidth() ==
V->getType()->getPrimitiveSizeInBits() &&
392 "Incompatible bit width");
393 if (TruncBits)
N =
N.trunc(
N.getBitWidth() - TruncBits);
394 if (SExtBits)
N =
N.sext(
N.getBitWidth() + SExtBits);
395 if (ZExtBits)
N =
N.zext(
N.getBitWidth() + ZExtBits);
399 ConstantRange evaluateWith(ConstantRange
N)
const {
400 assert(
N.getBitWidth() ==
V->getType()->getPrimitiveSizeInBits() &&
401 "Incompatible bit width");
402 if (TruncBits)
N =
N.truncate(
N.getBitWidth() - TruncBits);
403 if (IsNonNegative && !
N.isAllNonNegative())
407 if (SExtBits)
N =
N.signExtend(
N.getBitWidth() + SExtBits);
408 if (ZExtBits)
N =
N.zeroExtend(
N.getBitWidth() + ZExtBits);
412 KnownBits evaluateWith(KnownBits K)
const {
413 assert(
K.getBitWidth() ==
V->getType()->getPrimitiveSizeInBits() &&
414 "Incompatible bit width");
416 K =
K.trunc(
K.getBitWidth() - TruncBits);
418 K =
K.sext(
K.getBitWidth() + SExtBits);
420 K =
K.zext(
K.getBitWidth() + ZExtBits);
424 bool canDistributeOver(
bool NUW,
bool NSW)
const {
428 return (!ZExtBits || NUW) && (!SExtBits || NSW);
431 bool hasSameCastsAs(
const CastedValue &
Other)
const {
432 if (
V->getType() !=
Other.V->getType())
435 if (ZExtBits ==
Other.ZExtBits && SExtBits ==
Other.SExtBits &&
436 TruncBits ==
Other.TruncBits)
440 if (IsNonNegative ||
Other.IsNonNegative)
441 return (ZExtBits + SExtBits ==
Other.ZExtBits +
Other.SExtBits &&
442 TruncBits ==
Other.TruncBits);
459 const APInt &
Offset,
bool IsNUW,
bool IsNSW)
463 : Val(Val), IsNUW(
true), IsNSW(
true) {
464 unsigned BitWidth = Val.getBitWidth();
472 bool NSW = IsNSW && (
Other.isOne() || (MulIsNSW &&
Offset.isZero()));
473 bool NUW = IsNUW && (
Other.isOne() || MulIsNUW);
479 APInt NewScale =
Scale.smul_ov(
Other, ScaleOverflow);
480 NSW &= !ScaleOverflow;
497 Val.evaluateWith(Const->getValue()),
true,
true);
501 APInt RHS = Val.evaluateWith(RHSC->getValue());
504 bool NUW =
true, NSW =
true;
506 NUW &= BOp->hasNoUnsignedWrap();
507 NSW &= BOp->hasNoSignedWrap();
509 if (!Val.canDistributeOver(NUW, NSW))
518 switch (BOp->getOpcode()) {
523 case Instruction::Or:
529 case Instruction::Add: {
534 E.Offset =
E.Offset.sadd_ov(
RHS, Overflow);
536 E.IsNSW &= NSW && !Overflow;
539 case Instruction::Sub: {
543 E.Offset =
E.Offset.ssub_ov(
RHS, Overflow);
545 E.IsNSW &= NSW && !Overflow;
548 case Instruction::Mul:
553 case Instruction::Shl: {
559 if (
RHS.getLimitedValue() > Val.getBitWidth())
567 unsigned BitWidth = Val.getBitWidth();
568 unsigned ShAmt =
RHS.getLimitedValue();
582 Val.withZExtOfValue(ZExt->getOperand(0), ZExt->hasNonNeg()),
DL,
596struct VariableGEPIndex {
611 bool hasNegatedScaleOf(
const VariableGEPIndex &
Other)
const {
612 if (IsNegated ==
Other.IsNegated)
613 return Scale == -
Other.Scale;
614 return Scale ==
Other.Scale;
621 void print(raw_ostream &OS)
const {
622 OS <<
"(V=" << Val.V->
getName()
623 <<
", zextbits=" << Val.ZExtBits
624 <<
", sextbits=" << Val.SExtBits
625 <<
", truncbits=" << Val.TruncBits
626 <<
", scale=" << Scale
628 <<
", negated=" << IsNegated <<
")";
650 OS <<
", inbounds=" << (
NWFlags.isInBounds() ?
"1" :
"0")
651 <<
", nuw=" << (
NWFlags.hasNoUnsignedWrap() ?
"1" :
"0")
652 <<
"(DecomposedGEP Base=" <<
Base->getName() <<
", Offset=" <<
Offset
654 for (
size_t i = 0; i <
VarIndices.size(); i++) {
678BasicAAResult::DecomposeGEPExpression(
const Value *V,
const DataLayout &DL,
685 unsigned IndexSize = DL.getIndexTypeSizeInBits(V->getType());
694 if (!GA->isInterposable()) {
695 V = GA->getAliasee();
703 if (
Op->getOpcode() == Instruction::BitCast ||
704 Op->getOpcode() == Instruction::AddrSpaceCast) {
705 Value *NewV =
Op->getOperand(0);
706 auto *NewVTy = NewV->
getType();
710 DL.getIndexTypeSizeInBits(NewVTy) != IndexSize) {
722 if (
PHI->getNumIncomingValues() == 1) {
723 V =
PHI->getIncomingValue(0);
758 I != E; ++
I, ++GTI) {
767 Decomposed.
Offset += DL.getStructLayout(STy)->getElementOffset(FieldNo);
784 CIdx->getValue().sextOrTrunc(IndexSize);
798 bool NonNeg = NUSW && NUW;
799 unsigned Width = Index->getType()->getIntegerBitWidth();
800 unsigned SExtBits = IndexSize > Width ? IndexSize - Width : 0;
801 unsigned TruncBits = IndexSize < Width ? Width - IndexSize : 0;
803 CastedValue(Index, 0, SExtBits, TruncBits, NonNeg), DL, 0, AC, DT);
809 Decomposed.
Offset += LE.Offset;
810 APInt Scale = LE.Scale;
818 for (
unsigned i = 0, e = Decomposed.
VarIndices.
size(); i != e; ++i) {
819 if ((Decomposed.
VarIndices[i].Val.V == LE.Val.V ||
821 Decomposed.
VarIndices[i].Val.hasSameCastsAs(LE.Val)) {
824 LE.IsNSW = LE.IsNUW =
false;
831 VariableGEPIndex Entry = {LE.Val, Scale, CtxI, LE.IsNSW,
839 }
while (--MaxLookup);
843 SearchLimitReached++;
850 assert(Visited.empty() &&
"Visited must be cleared after use!");
853 unsigned MaxLookup = 8;
860 if (!Visited.insert(V).second)
874 if (Arg->hasNoAliasAttr() && Arg->onlyReadsMemory()) {
885 if (!GV->isConstant())
901 if (PN->getNumIncomingValues() > MaxLookup)
909 }
while (!Worklist.
empty() && --MaxLookup);
912 if (!Worklist.
empty())
920 return II &&
II->getIntrinsicID() == IID;
932 if (
Call->hasReadingOperandBundles())
934 if (
Call->hasClobberingOperandBundles())
936 if (
Call->isVolatile()) {
949 return F->getMemoryEffects();
954 if (
Call->doesNotAccessMemory(ArgIdx))
957 if (
Call->onlyWritesMemory(ArgIdx))
960 if (
Call->onlyReadsMemory(ArgIdx))
969 if (!inst->getParent())
971 return inst->getParent()->getParent();
985 return !F1 || !F2 || F1 == F2;
993 "BasicAliasAnalysis doesn't support interprocedural queries.");
994 return aliasCheck(LocA.
Ptr, LocA.
Size, LocB.
Ptr, LocB.
Size, AAQI, CtxI);
1007 "AliasAnalysis query involving multiple functions!");
1018 if (CI->isTailCall() &&
1019 !CI->getAttributes().hasAttrSomewhere(Attribute::ByVal))
1032 if (ME.doesNotAccessMemory())
1047 Call->isInlineAsm()) {
1064 Object,
Call,
false,
false);
1074 if ((ArgMR | OtherMR) != OtherMR) {
1076 for (
const Use &U :
Call->data_ops()) {
1077 const Value *Arg = U;
1080 unsigned ArgIdx =
Call->getDataOperandNo(&U);
1082 Call->isArgOperand(&U)
1090 if (NewArgMR == ArgMR)
1096 ModRefInfo Result = ArgMR | OtherMR | SyncMR;
1099 if ((ErrnoMR | Result) != Result) {
1177 auto BaseObjectsAlias = [&]() {
1197 return BaseObjectsAlias();
1202 DominatorTree *DT = getDT(AAQI);
1203 DecomposedGEP DecompGEP1 = DecomposeGEPExpression(GEP1, DL, &AC, DT);
1204 DecomposedGEP DecompGEP2 = DecomposeGEPExpression(V2, DL, &AC, DT);
1207 if (DecompGEP1.Base == GEP1 && DecompGEP2.Base == V2)
1211 if (DecompGEP1.Offset.getBitWidth() != DecompGEP2.Offset.getBitWidth())
1212 return BaseObjectsAlias();
1215 if (DecompGEP1.VarIndices.size() < DecompGEP2.VarIndices.size()) {
1223 subtractDecomposedGEPs(DecompGEP1, DecompGEP2, AAQI);
1229 if (DecompGEP1.NWFlags.isInBounds() && DecompGEP1.VarIndices.empty() &&
1231 DecompGEP1.Offset.sge(V2Size.
getValue()) &&
1236 if (DecompGEP2.NWFlags.isInBounds() && DecompGEP1.VarIndices.empty() &&
1238 DecompGEP1.Offset.sle(-V1Size.
getValue()) &&
1244 if (DecompGEP1.Offset == 0 && DecompGEP1.VarIndices.empty())
1245 return AAQI.
AAR.
alias(MemoryLocation(DecompGEP1.Base, V1Size),
1246 MemoryLocation(DecompGEP2.Base, V2Size), AAQI);
1249 AliasResult BaseAlias =
1265 if (DecompGEP1.VarIndices.empty()) {
1266 APInt &
Off = DecompGEP1.Offset;
1269 LocationSize VLeftSize = V2Size;
1270 LocationSize VRightSize = V1Size;
1271 const bool Swapped =
Off.isNegative();
1287 const TypeSize LSize = VLeftSize.
getValue();
1289 if (
Off.ult(LSize)) {
1294 Off.ule(INT32_MAX) && (
Off + VRightSize.
getValue()).ule(LSize)) {
1311 if (!Overflow &&
Off.uge(UpperRange))
1318 if (DecompGEP1.VarIndices.size() == 1 &&
1319 DecompGEP1.VarIndices[0].Val.TruncBits == 0 &&
1320 DecompGEP1.Offset.isZero() &&
1323 const VariableGEPIndex &ScalableVar = DecompGEP1.VarIndices[0];
1325 ScalableVar.IsNegated ? -ScalableVar.Scale : ScalableVar.Scale;
1326 LocationSize VLeftSize = Scale.
isNegative() ? V1Size : V2Size;
1330 bool Overflows = !DecompGEP1.VarIndices[0].IsNSW;
1355 if (!DecompGEP1.VarIndices.empty() &&
1356 DecompGEP1.NWFlags.hasNoUnsignedWrap() && V2Size.
hasValue() &&
1366 unsigned BW = DecompGEP1.Offset.getBitWidth();
1374 auto [GCD, OffsetRange, VIKnownBits] = analyzeVariableOffsets(DecompGEP1, DT);
1382 APInt ModOffset = DecompGEP1.Offset.srem(GCD);
1386 (GCD - ModOffset).uge(V1Size.
getValue()))
1391 ConstantRange Range1 = OffsetRange.add(
1392 ConstantRange(APInt(BW, 0), APInt(BW, V1Size.
getValue())));
1393 ConstantRange Range2 =
1394 ConstantRange(APInt(BW, 0), APInt(BW, V2Size.
getValue()));
1400 if (
auto MinAbsVarIndex =
1401 computeMinAbsVarOffset(DecompGEP1, VIKnownBits, DT, AAQI)) {
1403 APInt OffsetLo = DecompGEP1.Offset - *MinAbsVarIndex;
1404 APInt OffsetHi = DecompGEP1.Offset + *MinAbsVarIndex;
1413 if (computeConstantOffsetHeuristic(DecompGEP1, V1Size, V2Size, &AC, DT, AAQI))
1443 if (isValueEqualInPotentialCycles(
SI->getCondition(), SI2->getCondition(),
1446 AAQI.
AAR.
alias(MemoryLocation(
SI->getTrueValue(), SISize),
1447 MemoryLocation(SI2->getTrueValue(), V2Size), AAQI);
1450 AliasResult ThisAlias =
1451 AAQI.
AAR.
alias(MemoryLocation(
SI->getFalseValue(), SISize),
1452 MemoryLocation(SI2->getFalseValue(), V2Size), AAQI);
1458 AliasResult Alias = AAQI.
AAR.
alias(MemoryLocation(
SI->getTrueValue(), SISize),
1459 MemoryLocation(V2, V2Size), AAQI);
1463 AliasResult ThisAlias =
1464 AAQI.
AAR.
alias(MemoryLocation(
SI->getFalseValue(), SISize),
1465 MemoryLocation(V2, V2Size), AAQI);
1482 std::optional<AliasResult> Alias;
1484 AliasResult ThisAlias = AAQI.
AAR.
alias(
1499 SmallVector<Value *, 4> V1Srcs;
1503 bool isRecursive =
false;
1504 auto CheckForRecPhi = [&](
Value *PV) {
1505 if (!Opts.basic_aa_recphi)
1514 SmallPtrSet<Value *, 4> UniqueSrc;
1520 if (CheckForRecPhi(PV1))
1523 if (UniqueSrc.
insert(PV1).second)
1549 AliasResult Alias = AAQI.
AAR.
alias(MemoryLocation(V1Srcs[0], PNSize),
1550 MemoryLocation(V2, V2Size), AAQI);
1563 for (
unsigned i = 1, e = V1Srcs.
size(); i != e; ++i) {
1566 AliasResult ThisAlias = AAQI.
AAR.
alias(
1567 MemoryLocation(
V, PNSize), MemoryLocation(V2, V2Size), AAQI);
1598 V1 =
V1->stripPointerCastsForAliasAnalysis();
1612 if (isValueEqualInPotentialCycles(
V1, V2, AAQI))
1665 if (Opts.basic_aa_separate_storage) {
1666 for (AssumptionCache::ResultElem &Elem : AC.assumptionsFor(
O1)) {
1671 OperandBundleUse OBU =
Assume->getOperandBundleAt(Elem.Index);
1681 DominatorTree *DT = getDT(AAQI);
1682 auto ValidAssumeForPtrContext = [&](
const Value *Ptr) {
1689 &*PtrA->getParent()->getEntryBlock().begin();
1696 if ((
O1 == HintO1 &&
O2 == HintO2) || (
O1 == HintO2 &&
O2 == HintO1)) {
1703 ValidAssumeForPtrContext(V2)))) {
1706 if (!isValueEqualInPotentialCycles(
O1,
O1, AAQI) ||
1707 !isValueEqualInPotentialCycles(
O2,
O2, AAQI))
1739 if (AAQI.
Depth >= 512)
1748 const bool Swapped =
V1 > V2;
1754 auto &
Entry = Pair.first->second;
1755 if (!
Entry.isDefinitive()) {
1760 if (
Entry.isAssumption())
1761 ++
Entry.NumAssumptionUses;
1772 aliasCheckRecursive(
V1, V1Size, V2, V2Size, AAQI,
O1,
O2);
1776 auto &
Entry = It->second;
1779 bool AssumptionDisproven =
1781 if (AssumptionDisproven)
1788 Entry.Result.swap(Swapped);
1793 if (AssumptionDisproven)
1809 if (AAQI.
Depth == 1) {
1828 AliasResult
Result = aliasGEP(GV1, V1Size, V2, V2Size,
O1,
O2, AAQI);
1832 AliasResult
Result = aliasGEP(GV2, V2Size,
V1, V1Size,
O2,
O1, AAQI);
1839 AliasResult
Result = aliasPHI(PN, V1Size, V2, V2Size, AAQI);
1843 AliasResult
Result = aliasPHI(PN, V2Size,
V1, V1Size, AAQI);
1850 AliasResult
Result = aliasSelect(
S1, V1Size, V2, V2Size, AAQI);
1854 AliasResult
Result = aliasSelect(S2, V2Size,
V1, V1Size, AAQI);
1885 if (
Loc.Size.hasValue() &&
1886 Loc.Size.getValue().getKnownMinValue() * 8 > TLI.getIntSize())
1895 if (GV->hasLocalLinkage())
1900 if (TLI.isErrnoFunctionCall())
1913bool BasicAAResult::isValueEqualInPotentialCycles(
const Value *V,
1925 if (!Inst || Inst->
getParent()->isEntryBlock())
1928 return isNotInCycle(Inst, getDT(AAQI),
nullptr,
nullptr);
1932void BasicAAResult::subtractDecomposedGEPs(DecomposedGEP &DestGEP,
1933 const DecomposedGEP &SrcGEP,
1937 if (DestGEP.Offset.ult(SrcGEP.Offset))
1938 DestGEP.NWFlags = DestGEP.NWFlags.withoutNoUnsignedWrap();
1940 DestGEP.Offset -= SrcGEP.Offset;
1941 for (
const VariableGEPIndex &Src : SrcGEP.VarIndices) {
1945 for (
auto I :
enumerate(DestGEP.VarIndices)) {
1946 VariableGEPIndex &Dest =
I.value();
1947 if ((!isValueEqualInPotentialCycles(Dest.Val.V, Src.Val.V, AAQI) &&
1949 !Dest.Val.hasSameCastsAs(Src.Val))
1953 if (Dest.IsNegated) {
1954 Dest.Scale = -Dest.Scale;
1955 Dest.IsNegated =
false;
1961 if (Dest.Scale != Src.Scale) {
1964 if (Dest.Scale.
ult(Src.Scale))
1965 DestGEP.NWFlags = DestGEP.NWFlags.withoutNoUnsignedWrap();
1967 Dest.Scale -= Src.Scale;
1970 DestGEP.VarIndices.erase(DestGEP.VarIndices.begin() +
I.index());
1978 VariableGEPIndex
Entry = {Src.Val, Src.Scale, Src.CtxI, Src.IsNSW,
1980 DestGEP.VarIndices.push_back(Entry);
1983 DestGEP.NWFlags = DestGEP.NWFlags.withoutNoUnsignedWrap();
1989BasicAAResult::analyzeVariableOffsets(
const DecomposedGEP &
GEP,
1992 ConstantRange OffsetRange(
GEP.Offset);
1994 VarIndexKnownBits.
reserve(
GEP.VarIndices.size());
1996 for (
unsigned I = 0,
E =
GEP.VarIndices.size();
I !=
E; ++
I) {
1997 const VariableGEPIndex &
Index =
GEP.VarIndices[
I];
1998 const APInt &Scale =
Index.Scale;
2000 SimplifyQuery SQ(DL, DT, &AC,
Index.CtxI,
true);
2004 APInt ScaleForGCD = Scale;
2013 unsigned VarTZ =
Known.countMinTrailingZeros();
2017 ScaleForGCD <<= std::min(VarTZ, MaxShift);
2021 GCD = ScaleForGCD.
abs();
2030 CR =
Index.Val.evaluateWith(CR).sextOrTrunc(OffsetRange.getBitWidth());
2033 "Bit widths are normalized to MaxIndexSize");
2035 CR = CR.
smul_sat(ConstantRange(Scale));
2037 CR = CR.
smul_fast(ConstantRange(Scale));
2039 if (
Index.IsNegated)
2040 OffsetRange = OffsetRange.
sub(CR);
2042 OffsetRange = OffsetRange.
add(CR);
2045 return {GCD, OffsetRange, std::move(VarIndexKnownBits)};
2058 int MaxScaleValueBW = Var.Val.getBitWidth() - ValOrigBW;
2059 if (MaxScaleValueBW <= 0)
2061 return Var.Scale.
ule(
2065std::optional<APInt> BasicAAResult::computeMinAbsVarOffset(
2068 const auto &VarIndices =
GEP.VarIndices;
2069 if (VarIndices.size() == 1) {
2071 const VariableGEPIndex &Var = VarIndices[0];
2072 if (Var.Val.TruncBits == 0 &&
2073 isKnownNonZero(Var.Val.V, SimplifyQuery(DL, DT, &AC, Var.CtxI))) {
2078 return Var.Scale.
abs();
2081 return std::nullopt;
2084 if (VarIndices.size() == 2) {
2089 const VariableGEPIndex &Var0 = VarIndices[0];
2090 const VariableGEPIndex &Var1 = VarIndices[1];
2091 bool Preconditions =
2092 Var0.Val.TruncBits == 0 && Var0.Val.hasSameCastsAs(Var1.Val) &&
2097 return std::nullopt;
2099 if (Var0.hasNegatedScaleOf(Var1)) {
2101 SimplifyQuery(DL, DT, &AC, Var0.CtxI
2104 return Var0.Scale.
abs();
2107 return std::nullopt;
2118 bool EffectiveNeg0 = Var0.IsNegated ^ Var0.Scale.
isNegative();
2119 bool EffectiveNeg1 = Var1.IsNegated ^ Var1.Scale.
isNegative();
2120 if (EffectiveNeg0 != EffectiveNeg1) {
2121 APInt AbsScale0 = Var0.Scale.
abs();
2122 APInt AbsScale1 = Var1.Scale.
abs();
2124 APInt
C0 = AbsScale0.
udiv(ScaleGCD);
2125 APInt
C1 = AbsScale1.
udiv(ScaleGCD);
2129 auto Known0 =
KnownBits::mul(Var0.Val.evaluateWith(VIKnownBits[0]),
2132 auto Known1 =
KnownBits::mul(Var1.Val.evaluateWith(VIKnownBits[1]),
2140 return std::nullopt;
2143bool BasicAAResult::computeConstantOffsetHeuristic(
const DecomposedGEP &
GEP,
2149 if (
GEP.VarIndices.size() != 2 || !MaybeV1Size.
hasValue() ||
2156 const VariableGEPIndex &Var0 =
GEP.VarIndices[0], &Var1 =
GEP.VarIndices[1];
2160 if (Var0.Val.TruncBits != 0 || !Var0.Val.hasSameCastsAs(Var1.Val) ||
2161 !Var0.hasNegatedScaleOf(Var1) ||
2175 LinearExpression
E0 =
2177 LinearExpression E1 =
2179 if (
E0.Scale != E1.
Scale || !
E0.Val.hasSameCastsAs(E1.Val) ||
2180 !isValueEqualInPotentialCycles(
E0.Val.V, E1.Val.V, AAQI))
2190 APInt MinDiff =
E0.Offset - E1.
Offset, Wrapped = -MinDiff;
2192 APInt MinDiffBytes =
2199 return MinDiffBytes.
uge(V1Size +
GEP.Offset.abs()) &&
2200 MinDiffBytes.
uge(V2Size +
GEP.Offset.abs());
2220void BasicAAWrapperPass::anchor() {}
2223 "Basic Alias Analysis (stateless AA impl)",
true,
true)
2228 "Basic Alias Analysis (stateless AA impl)",
true,
true)
2240 TLIWP.getTLI(
F), ACT.getAssumptionCache(
F),
2241 &DTWP.getDomTree()));
const TargetLowering & TLI
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
This file implements a class to represent arbitrary precision integral constant values and operations...
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)
This file contains the simple types necessary to represent the attributes associated with functions a...
static const Function * getParent(const Value *V)
static bool isObjectSize(const Value *V, TypeSize Size, const DataLayout &DL, const TargetLibraryInfo &TLI, bool NullIsValidLoc)
Returns true if we can prove that the object specified by V has size Size.
static bool isArgumentOrArgumentLike(const Value *V)
static bool notDifferentParent(const Value *O1, const Value *O2)
static bool multiplyByScaleNoWrap(const VariableGEPIndex &Var)
Check whether V*Scale cannot wrap for any value of V, so that abs(V*Scale) >= abs(Scale) holds in the...
static LinearExpression GetLinearExpression(const CastedValue &Val, const DataLayout &DL, unsigned Depth, AssumptionCache *AC, DominatorTree *DT)
Analyzes the specified value as a linear expression: "A*V + B", where A and B are constant integers.
static bool isNotInCycle(const Instruction *I, const DominatorTree *DT, const LoopInfo *LI, const CycleInfo *CI)
static bool areBothVScale(const Value *V1, const Value *V2)
Return true if both V1 and V2 are VScale.
static TypeSize getMinimalExtentFrom(const Value &V, const LocationSize &LocSize, const DataLayout &DL, bool NullIsValidLoc)
Return the minimal extent from V to the end of the underlying object, assuming the result is used in ...
static AliasResult MergeAliasResults(AliasResult A, AliasResult B)
static bool isIntrinsicCall(const CallBase *Call, Intrinsic::ID IID)
static bool isObjectSmallerThan(const Value *V, const Value &OtherV, LocationSize OtherSize, const DataLayout &DL, const TargetLibraryInfo &TLI, bool NullIsValidLoc)
Returns true if we can prove that the object specified by V is smaller than the minimal extent access...
This is the interface for LLVM's primary stateless and local alias analysis.
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
This file contains the declarations for the subclasses of Constant, which represent the different fla...
This file declares the LLVM IR specialization of the GenericCycle templates.
static DeltaTreeNode * getRoot(void *Root)
This file provides utility analysis objects describing memory locations.
uint64_t IntrinsicInst * II
#define INITIALIZE_PASS_DEPENDENCY(depName)
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
This file provides utility classes that use RAII to save and restore values.
This file defines the scope_exit class, which executes user-defined cleanup logic at scope exit.
This file defines the SmallPtrSet class.
This file defines the SmallVector class.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
static unsigned getBitWidth(Type *Ty, const DataLayout &DL)
Returns the bitwidth of the given scalar or pointer type.
This class stores info we want to provide to or retain within an alias query.
SmallVector< AAQueryInfo::LocPair, 4 > AssumptionBasedResults
Location pairs for which an assumption based result is currently stored.
unsigned Depth
Query depth used to distinguish recursive queries.
int NumAssumptionUses
How many active NoAlias assumption uses there are.
std::pair< AACacheLoc, AACacheLoc > LocPair
bool MayBeCrossIteration
Tracks whether the accesses may be on different cycle iterations.
bool AllowEphemerals
Whether ephemeral values should be allowed when checking assumes.
LLVM_ABI AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB)
The main low level interface to the alias analysis implementation.
LLVM_ABI AliasResult aliasErrno(const MemoryLocation &Loc, const Instruction *CtxI)
LLVM_ABI MemoryEffects getMemoryEffects(const CallBase *Call)
Return the behavior of the given call site.
LLVM_ABI ModRefInfo getArgModRefInfo(const CallBase *Call, unsigned ArgIdx)
Get the ModRef info associated with a pointer argument of a call.
Class for arbitrary precision integers.
LLVM_ABI APInt umul_ov(const APInt &RHS, bool &Overflow) const
LLVM_ABI APInt udiv(const APInt &RHS) const
Unsigned division operation.
LLVM_ABI APInt zextOrTrunc(unsigned width) const
Zero extend or truncate to width.
static APInt getMaxValue(unsigned numBits)
Gets maximum unsigned value of APInt for specific bit width.
APInt abs() const
Get the absolute value.
unsigned getBitWidth() const
Return the number of bits in the APInt.
bool ult(const APInt &RHS) const
Unsigned less than comparison.
bool isNegative() const
Determine sign of this APInt.
unsigned countr_zero() const
Count the number of trailing zero bits.
static APInt getSignedMinValue(unsigned numBits)
Gets minimum signed value of APInt for a specific bit width.
unsigned getSignificantBits() const
Get the minimum bit size for this signed APInt.
LLVM_ABI APInt smul_ov(const APInt &RHS, bool &Overflow) const
bool isNonNegative() const
Determine if this APInt Value is non-negative (>= 0)
bool ule(const APInt &RHS) const
Unsigned less or equal comparison.
static APInt getZero(unsigned numBits)
Get the '0' value for the specified bit-width.
static APInt getOneBitSet(unsigned numBits, unsigned BitNo)
Return an APInt with exactly one bit set in the result.
bool uge(const APInt &RHS) const
Unsigned greater or equal comparison.
The possible results of an alias query.
void swap(bool DoSwap=true)
Helper for processing AliasResult for swapped memory location pairs.
@ MayAlias
The two locations may or may not alias.
@ NoAlias
The two locations do not alias at all.
@ PartialAlias
The two locations alias, but only due to a partial overlap.
@ MustAlias
The two locations precisely alias each other.
void setOffset(int32_t NewOffset)
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Represent the analysis usage information of a pass.
void setPreservesAll()
Set by analyses that do not transform their input at all.
AnalysisUsage & addRequiredTransitive()
This class represents an incoming formal argument to a Function.
Represent a constant reference to an array (0 or more elements consecutively in memory),...
A function analysis which provides an AssumptionCache.
An immutable pass that tracks lazily created AssumptionCache objects.
A cache of @llvm.assume calls within a function.
This is the AA result object for the basic, local, and stateless alias analysis.
LLVM_ABI ModRefInfo getModRefInfo(const CallBase *Call, const MemoryLocation &Loc, AAQueryInfo &AAQI)
Checks to see if the specified callsite can clobber the specified memory object.
LLVM_ABI ModRefInfo getArgModRefInfo(const CallBase *Call, unsigned ArgIdx)
Get the location associated with a pointer argument of a callsite.
LLVM_ABI BasicAAResult(const DataLayout &DL, const Function &F, const TargetLibraryInfo &TLI, AssumptionCache &AC, DominatorTree *DT=nullptr)
LLVM_ABI MemoryEffects getMemoryEffects(const CallBase *Call, AAQueryInfo &AAQI)
Returns the behavior when calling the given call site.
LLVM_ABI AliasResult aliasErrno(const MemoryLocation &Loc, const Instruction *CtxI)
LLVM_ABI ModRefInfo getModRefInfoMask(const MemoryLocation &Loc, AAQueryInfo &AAQI, bool IgnoreLocals=false)
Returns a bitmask that should be unconditionally applied to the ModRef info of a memory location.
LLVM_ABI bool invalidate(Function &Fn, const PreservedAnalyses &PA, FunctionAnalysisManager::Invalidator &Inv)
Handle invalidation events in the new pass manager.
LLVM_ABI AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB, AAQueryInfo &AAQI, const Instruction *CtxI)
Legacy wrapper pass to provide the BasicAAResult object.
bool runOnFunction(Function &F) override
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass.
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
LLVM_ABI BasicAAResult run(Function &F, FunctionAnalysisManager &AM)
LLVM Basic Block Representation.
unsigned getNumber() const
const Function * getParent() const
Return the enclosing method, or null if none.
Base class for all callable instructions (InvokeInst and CallInst) Holds everything related to callin...
This class represents a function call, abstracting a target machine's calling convention.
This is the shared class of boolean and integer constants.
This class represents a range of values.
LLVM_ABI ConstantRange add(const ConstantRange &Other) const
Return a new range representing the possible values resulting from an addition of a value in this ran...
static LLVM_ABI ConstantRange fromKnownBits(const KnownBits &Known, bool IsSigned)
Initialize a range based on a known bits constraint.
LLVM_ABI ConstantRange smul_fast(const ConstantRange &Other) const
Return range of possible values for a signed multiplication of this and Other.
LLVM_ABI bool isEmptySet() const
Return true if this set contains no members.
LLVM_ABI ConstantRange smul_sat(const ConstantRange &Other) const
Perform a signed saturating multiplication of two constant ranges.
LLVM_ABI APInt getUnsignedMax() const
Return the largest unsigned value contained in the ConstantRange.
LLVM_ABI ConstantRange intersectWith(const ConstantRange &CR, PreferredRangeType Type=Smallest) const
Return the range that results from the intersection of this range with another range.
LLVM_ABI APInt getSignedMax() const
Return the largest signed value contained in the ConstantRange.
LLVM_ABI ConstantRange sub(const ConstantRange &Other) const
Return a new range representing the possible values resulting from a subtraction of a value in this r...
A parsed version of the target data layout string in and methods for querying it.
iterator find(const_arg_type_t< KeyT > Val)
bool erase(const KeyT &Val)
std::pair< iterator, bool > try_emplace(KeyT &&Key, Ts &&...Args)
Analysis pass which computes a DominatorTree.
Legacy analysis pass which computes a DominatorTree.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
void removeInstruction(Instruction *I)
CaptureComponents getCapturesBefore(const Value *Object, const Instruction *I, bool OrAt, bool ReturnCaptures) override
Return how Object may be captured before instruction I, considering only provenance captures.
void insertPotentialCapture(const Instruction *I)
Notify the analysis that I is about to be inserted or moved.
EarliestEscapeAnalysis(DominatorTree &DT, const LoopInfo *LI=nullptr, const CycleInfo *CI=nullptr)
FunctionPass class - This class is used to implement most global optimizations.
unsigned getBlockNumberEpoch() const
Return the "epoch" of current block numbers.
bool callsFunctionThatReturnsTwice() const
callsFunctionThatReturnsTwice - Return true if the function has a call to setjmp or other function th...
bool hasFnAttribute(Attribute::AttrKind Kind) const
Return true if the function has the attribute.
Represents flags for the getelementptr instruction/expression.
static GEPNoWrapFlags all()
GEPNoWrapFlags withoutNoUnsignedWrap() const
bool hasNoUnsignedSignedWrap() const
bool hasNoUnsignedWrap() const
LLVM_ABI Type * getSourceElementType() const
GEPNoWrapFlags getNoWrapFlags() const
CycleRef getCycle(const BlockT *Block) const
Find the innermost cycle containing Block.
Module * getParent()
Get the module that this global value is contained inside of...
LLVM_ABI const Function * getFunction() const
Return the function this instruction belongs to.
LLVM_ABI bool comesBefore(const Instruction *Other) const
Given an instruction Other in the same basic block as this instruction, return true if this instructi...
A wrapper class for inspecting calls to intrinsic functions.
bool mayBeBeforePointer() const
Whether accesses before the base pointer are possible.
static constexpr LocationSize beforeOrAfterPointer()
Any location before or after the base pointer (but still within the underlying object).
TypeSize getValue() const
static constexpr LocationSize afterPointer()
Any location after the base pointer (but still within the underlying object).
static MemoryEffectsBase readOnly()
MemoryEffectsBase getWithoutLoc(Location Loc) const
Get new MemoryEffectsBase with NoModRef on the given Loc.
static MemoryEffectsBase inaccessibleMemOnly(ModRefInfo MR=ModRefInfo::ModRef)
static MemoryEffectsBase writeOnly()
Representation for a specific memory location.
LocationSize Size
The maximum size of the location, in address-units, or UnknownSize if the size is not known.
static MemoryLocation getBeforeOrAfter(const Value *Ptr, const AAMDNodes &AATags=AAMDNodes())
Return a location that may access any location before or after Ptr, while remaining within the underl...
const Value * Ptr
The address of the start of the location.
static LLVM_ABI MemoryLocation getForArgument(const CallBase *Call, unsigned ArgIdx, const TargetLibraryInfo *TLI)
Return a location representing a particular argument of a call.
This is a utility class that provides an abstraction for the common functionality between Instruction...
op_range incoming_values()
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
unsigned getNumIncomingValues() const
Return the number of incoming edges.
AnalysisType & getAnalysis() const
getAnalysis<AnalysisType>() - This function is used by subclasses to get to the analysis information ...
A set of analyses that are preserved following a run of a transformation pass.
This class represents the LLVM 'select' instruction.
CaptureComponents getCapturesBefore(const Value *Object, const Instruction *I, bool OrAt, bool ReturnCaptures) override
Return how Object may be captured before instruction I, considering only provenance captures.
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
reference emplace_back(ArgTypes &&... Args)
void reserve(size_type N)
iterator erase(const_iterator CI)
void push_back(const T &Elt)
LLVM_NO_SANITIZE_CFI_UNRELATED_CAST iterator begin()
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Class to represent struct types.
Analysis pass providing the TargetLibraryInfo.
Provides information about what library functions are available for the current target.
static constexpr TypeSize getFixed(ScalarTy ExactSize)
bool isPointerTy() const
True if this is an instance of PointerType.
bool isSized() const
Return true if it makes sense to take the size of this type.
LLVM_ABI TypeSize getPrimitiveSizeInBits() const LLVM_READONLY
Return the basic size of this type if it is a primitive type.
A Use represents the edge between a Value definition and its users.
const Use * const_op_iterator
Value * getOperand(unsigned i) const
LLVM Value Representation.
Type * getType() const
All values are typed, get the type of this value.
LLVM_ABI StringRef getName() const
Return a constant reference to the value's name.
LLVM_ABI const Value * stripPointerCastsForAliasAnalysis() const
Strip off pointer casts, all-zero GEPs, single-argument phi nodes and invariant group info.
constexpr ScalarTy getFixedValue() const
static constexpr bool isKnownLT(const FixedOrScalableQuantity &LHS, const FixedOrScalableQuantity &RHS)
constexpr bool isScalable() const
Returns whether the quantity is scaled by a runtime quantity (vscale).
constexpr ScalarTy getKnownMinValue() const
Returns the minimum value this quantity can represent.
StructType * getStructTypeOrNull() const
TypeSize getSequentialElementStride(const DataLayout &DL) const
const ParentTy * getParent() const
This class implements an extremely fast bulk output stream that can only output to a stream.
const APInt & umin(const APInt &A, const APInt &B)
Determine the smaller of two APInts considered to be unsigned.
LLVM_ABI APInt GreatestCommonDivisor(APInt A, APInt B, bool IsSigned=false)
Compute GCD of two APInt values.
bool match(Val *V, const Pattern &P)
auto m_VScale()
Matches a call to llvm.vscale().
friend class Instruction
Iterator for Instructions in a `BasicBlock.
This is an optimization pass for GlobalISel generic memory operations.
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
bool capturesReadProvenanceOnly(CaptureComponents CC)
SaveAndRestore(T &) -> SaveAndRestore< T >
BundleAttr getBundleAttrFromOBU(OperandBundleUse OBU)
@ Known
Known to have no common set bits.
auto enumerate(FirstRange &&First, RestRanges &&...Rest)
Given two or more input ranges, returns a new range whose values are tuples (A, B,...
decltype(auto) dyn_cast(const From &Val)
dyn_cast<X> - Return the argument parameter cast to the specified type.
auto successors(const MachineBasicBlock *BB)
LLVM_ABI bool isBaseOfObject(const Value *V)
Return true if we know V to the base address of the corresponding memory object.
LLVM_ABI const Value * getArgumentAliasingToReturnedPointer(const CallBase *Call, bool MustPreserveOffset, bool MustPreserveProvenance=false)
This function returns call pointer argument that is considered the same by aliasing rules.
void append_range(Container &C, Range &&R)
Wrapper function to append range R to container C.
constexpr bool isUIntN(unsigned N, uint64_t x)
Checks if an unsigned integer fits into the given (dynamic) bit width.
LLVM_ABI void computeKnownBits(const Value *V, KnownBits &Known, const DataLayout &DL, AssumptionCache *AC=nullptr, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true, unsigned Depth=0)
Determine which bits of V are known to be either zero or one and return them in the KnownZero/KnownOn...
@ O1
Optimize quickly without destroying debuggability.
@ O2
Optimize for fast execution as much as possible without triggering significant incremental compile ti...
MemoryEffectsBase< IRMemLocation > MemoryEffects
Summary of how a function affects memory in the program.
LLVM_ABI std::optional< TypeSize > getBaseObjectSize(const Value *Ptr, const DataLayout &DL, const TargetLibraryInfo *TLI, ObjectSizeOpts Opts={})
Like getObjectSize(), but only returns the size of base objects (like allocas, global variables and a...
RelativeUniformCounterPtr ValuesPtrExpr VTableAddr Value
LLVM_ABI bool isValidAssumeForContext(const Instruction *I, const Instruction *CtxI, const DominatorTree *DT=nullptr, bool AllowEphemerals=false)
Return true if it is valid to use the assumptions provided by an assume intrinsic,...
const AnalysisOptions & getAnalysisOptions(const LLVMContext &C)
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
LLVM_ABI bool getObjectSize(const Value *Ptr, uint64_t &Size, const DataLayout &DL, const TargetLibraryInfo *TLI, ObjectSizeOpts Opts={})
Compute the size of the object pointed by Ptr.
bool capturesFullProvenance(CaptureComponents CC)
LLVM_ABI ModRefInfo getSyncEffects(AAResults *AA, const MemoryLocation &Loc, AAQueryInfo &AAQI)
Get ModRefInfo for a synchronizing operation, such as a fence or stronger than monotonic atomic load/...
bool isModSet(const ModRefInfo MRI)
LLVM_ABI bool NullPointerIsDefined(const Function *F, unsigned AS=0)
Check whether null pointer dereferencing is considered undefined behavior for a given function or an ...
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
generic_gep_type_iterator<> gep_type_iterator
bool isModOrRefSet(const ModRefInfo MRI)
constexpr unsigned MaxLookupSearchDepth
The max limit of the search depth in DecomposeGEPExpression() and getUnderlyingObject().
LLVM_ABI ConstantRange getVScaleRange(const Function *F, unsigned BitWidth)
Determine the possible constant range of vscale with the given bit width, based on the vscale_range f...
LLVM_ABI FunctionPass * createBasicAAWrapperPass()
CaptureComponents
Components of the pointer that may be captured.
class LLVM_GSL_OWNER SmallVector
Forward declaration of SmallVector so that calculateSmallVectorDefaultInlinedElements can reference s...
LLVM_ABI const Value * getUnderlyingObject(const Value *V, unsigned MaxLookup=MaxLookupSearchDepth, bool MustPreserveProvenance=false)
This method strips off any GEP address adjustments, pointer casts or llvm.threadlocal....
bool isa(const From &Val)
isa<X> - Return true if the parameter to the template is an instance of one of the template type argu...
LLVM_ABI bool isKnownNonZero(const Value *V, const SimplifyQuery &Q, unsigned Depth=0)
Return true if the given value is known to be non-zero when defined.
ModRefInfo
Flags indicating whether a memory access modifies or references memory.
@ Ref
The access may reference the value stored in memory.
@ ModRef
The access may reference and may modify the value stored in memory.
@ Mod
The access may modify the value stored in memory.
@ NoModRef
The access neither references nor modifies the value stored in memory.
@ ArgMem
Access to memory via argument pointers.
@ InaccessibleMem
Memory that is inaccessible via LLVM IR.
LLVM_ABI bool isPotentiallyReachable(const Instruction *From, const Instruction *To, const SmallPtrSetImpl< BasicBlock * > *ExclusionSet=nullptr, const DominatorTree *DT=nullptr, const LoopInfo *LI=nullptr, const CycleInfo *CI=nullptr)
Determine whether instruction 'To' is reachable from 'From', without passing through any blocks in Ex...
LLVM_ABI bool isKnownNonEqual(const Value *V1, const Value *V2, const SimplifyQuery &SQ, unsigned Depth=0)
Return true if the given values are known to be non-equal when defined.
DWARFExpression::Operation Op
LLVM_ABI bool PointerMayBeCaptured(const Value *V, bool ReturnCaptures, unsigned MaxUsesToExplore=0)
PointerMayBeCaptured - Return true if this pointer value may be captured by the enclosing function (w...
LLVM_ABI bool isPotentiallyReachableFromMany(SmallVectorImpl< BasicBlock * > &Worklist, const BasicBlock *StopBB, const SmallPtrSetImpl< BasicBlock * > *ExclusionSet, const DominatorTree *DT=nullptr, const LoopInfo *LI=nullptr, const CycleInfo *CI=nullptr)
Determine whether there is at least one path from a block in 'Worklist' to 'StopBB' without passing t...
LLVM_ABI std::pair< Instruction *, CaptureResult > FindEarliestCapture(const Value *V, Function &F, const DominatorTree &DT, CaptureComponents Mask, unsigned MaxUsesToExplore=0)
bool isModAndRefSet(const ModRefInfo MRI)
LLVM_ABI bool isIdentifiedFunctionLocal(const Value *V)
Return true if V is umabigously identified at the function-level.
constexpr unsigned BitWidth
LLVM_ABI bool isEscapeSource(const Value *V)
Returns true if the pointer is one which would have been considered an escape by isNotCapturedBefore.
decltype(auto) cast(const From &Val)
cast<X> - Return the argument parameter cast to the specified type.
gep_type_iterator gep_type_begin(const User *GEP)
LLVM_ABI UseCaptureInfo DetermineUseCaptureKind(const Use &U, const Value *Base)
Determine what kind of capture behaviour U may exhibit.
AnalysisManager< Function > FunctionAnalysisManager
Convenience typedef for the Function analysis manager.
bool capturesNothing(CaptureComponents CC)
LLVM_ABI bool isIdentifiedObject(const Value *V)
Return true if this pointer refers to a distinct and identifiable object.
bool capturesAnyProvenance(CaptureComponents CC)
constexpr detail::IsaCheckPredicate< Types... > IsaPred
Function object wrapper for the llvm::isa type check.
LLVM_ABI ConstantRange computeConstantRange(const Value *V, bool ForSigned, const SimplifyQuery &SQ, unsigned Depth=0)
Determine the possible constant range of an integer or vector of integer value.
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
SmallVector< VariableGEPIndex, 4 > VarIndices
void print(raw_ostream &OS) const
ConstantRange OffsetRange
SmallVector< KnownBits, 4 > VarIndexKnownBits
static constexpr int Definitive
Cache entry is neither an assumption nor does it use a (non-definitive) assumption.
static constexpr int AssumptionBased
Cache entry is not an assumption itself, but may be using an assumption from higher up the stack.
A special type used by analysis passes to provide an address that identifies that particular analysis...
virtual CaptureComponents getCapturesBefore(const Value *Object, const Instruction *I, bool OrAt, bool ReturnCaptures)=0
Return how Object may be captured before instruction I, considering only provenance captures.
virtual ~CaptureAnalysis()=0
static KnownBits makeConstant(const APInt &C)
Create known bits from a known constant.
static LLVM_ABI std::optional< bool > ne(const KnownBits &LHS, const KnownBits &RHS)
Determine if these known bits always give the same ICMP_NE result.
static LLVM_ABI KnownBits mul(const KnownBits &LHS, const KnownBits &RHS, bool NoUndefSelfMultiply=false)
Compute known bits resulting from multiplying LHS and RHS.
Linear expression BasePtr + Index * Scale + Offset.
LinearExpression(Value *BasePtr, unsigned BitWidth)
Various options to control the behavior of getObjectSize.
bool NullIsUnknownSize
If this is true, null pointers in address space 0 will be treated as though they can't be evaluated.
bool RoundToAlign
Whether to round the result up to the alignment of allocas, byval arguments, and global variables.