64#define DEBUG_TYPE "basicaa"
78STATISTIC(SearchLimitReached,
"Number of times the limit to "
79 "decompose GEPs is reached");
80STATISTIC(SearchTimes,
"Number of times a GEP is decomposed");
109 bool RoundToAlign =
false) {
124 bool NullIsValidLoc) {
156 std::optional<TypeSize> ObjectSize =
getObjectSize(V,
DL, TLI, NullIsValidLoc,
168 bool NullIsValidLoc) {
173 bool CanBeNull, CanBeFreed;
175 V.getPointerDereferenceableBytes(
DL, CanBeNull, CanBeFreed);
176 DerefBytes = (CanBeNull && NullIsValidLoc) ? 0 : DerefBytes;
187 std::optional<TypeSize> ObjectSize =
189 return ObjectSize && *ObjectSize ==
Size;
213 return Succs.
empty() ||
222 auto Iter = EarliestEscapes.insert({Object,
nullptr});
227 if (EarliestCapture) {
228 auto Ins = Inst2Obj.insert({EarliestCapture, {}});
229 Ins.first->second.push_back(Object);
231 Iter.first->second = EarliestCapture;
235 if (!Iter.first->second)
242 if (
I == Iter.first->second) {
252 auto Iter = Inst2Obj.find(
I);
253 if (Iter != Inst2Obj.end()) {
254 for (
const Value *Obj : Iter->second)
255 EarliestEscapes.erase(Obj);
268 unsigned ZExtBits = 0;
269 unsigned SExtBits = 0;
270 unsigned TruncBits = 0;
272 explicit CastedValue(
const Value *V) : V(V) {}
273 explicit CastedValue(
const Value *V,
unsigned ZExtBits,
unsigned SExtBits,
275 : V(V), ZExtBits(ZExtBits), SExtBits(SExtBits), TruncBits(TruncBits) {}
278 return V->getType()->getPrimitiveSizeInBits() - TruncBits + ZExtBits +
282 CastedValue withValue(
const Value *NewV)
const {
283 return CastedValue(NewV, ZExtBits, SExtBits, TruncBits);
287 CastedValue withZExtOfValue(
const Value *NewV)
const {
288 unsigned ExtendBy =
V->getType()->getPrimitiveSizeInBits() -
290 if (ExtendBy <= TruncBits)
291 return CastedValue(NewV, ZExtBits, SExtBits, TruncBits - ExtendBy);
294 ExtendBy -= TruncBits;
295 return CastedValue(NewV, ZExtBits + SExtBits + ExtendBy, 0, 0);
299 CastedValue withSExtOfValue(
const Value *NewV)
const {
300 unsigned ExtendBy =
V->getType()->getPrimitiveSizeInBits() -
302 if (ExtendBy <= TruncBits)
303 return CastedValue(NewV, ZExtBits, SExtBits, TruncBits - ExtendBy);
306 ExtendBy -= TruncBits;
307 return CastedValue(NewV, ZExtBits, SExtBits + ExtendBy, 0);
311 assert(
N.getBitWidth() ==
V->getType()->getPrimitiveSizeInBits() &&
312 "Incompatible bit width");
313 if (TruncBits)
N =
N.trunc(
N.getBitWidth() - TruncBits);
314 if (SExtBits)
N =
N.sext(
N.getBitWidth() + SExtBits);
315 if (ZExtBits)
N =
N.zext(
N.getBitWidth() + ZExtBits);
320 assert(
N.getBitWidth() ==
V->getType()->getPrimitiveSizeInBits() &&
321 "Incompatible bit width");
322 if (TruncBits)
N =
N.truncate(
N.getBitWidth() - TruncBits);
323 if (SExtBits)
N =
N.signExtend(
N.getBitWidth() + SExtBits);
324 if (ZExtBits)
N =
N.zeroExtend(
N.getBitWidth() + ZExtBits);
328 bool canDistributeOver(
bool NUW,
bool NSW)
const {
332 return (!ZExtBits || NUW) && (!SExtBits || NSW);
335 bool hasSameCastsAs(
const CastedValue &
Other)
const {
336 return ZExtBits ==
Other.ZExtBits && SExtBits ==
Other.SExtBits &&
337 TruncBits ==
Other.TruncBits;
342struct LinearExpression {
350 LinearExpression(
const CastedValue &Val,
const APInt &Scale,
352 : Val(Val), Scale(Scale),
Offset(
Offset), IsNSW(IsNSW) {}
354 LinearExpression(
const CastedValue &Val) : Val(Val), IsNSW(
true) {
355 unsigned BitWidth = Val.getBitWidth();
360 LinearExpression mul(
const APInt &
Other,
bool MulIsNSW)
const {
363 bool NSW = IsNSW && (
Other.isOne() || (MulIsNSW &&
Offset.isZero()));
378 if (
const ConstantInt *Const = dyn_cast<ConstantInt>(Val.V))
379 return LinearExpression(Val,
APInt(Val.getBitWidth(), 0),
380 Val.evaluateWith(Const->getValue()),
true);
382 if (
const BinaryOperator *BOp = dyn_cast<BinaryOperator>(Val.V)) {
383 if (
ConstantInt *RHSC = dyn_cast<ConstantInt>(BOp->getOperand(1))) {
384 APInt RHS = Val.evaluateWith(RHSC->getValue());
387 bool NUW =
true, NSW =
true;
388 if (isa<OverflowingBinaryOperator>(BOp)) {
389 NUW &= BOp->hasNoUnsignedWrap();
390 NSW &= BOp->hasNoSignedWrap();
392 if (!Val.canDistributeOver(NUW, NSW))
400 LinearExpression E(Val);
401 switch (BOp->getOpcode()) {
406 case Instruction::Or:
408 if (!cast<PossiblyDisjointInst>(BOp)->isDisjoint())
412 case Instruction::Add: {
419 case Instruction::Sub: {
426 case Instruction::Mul:
431 case Instruction::Shl:
437 if (
RHS.getLimitedValue() > Val.getBitWidth())
442 E.Offset <<=
RHS.getLimitedValue();
443 E.Scale <<=
RHS.getLimitedValue();
451 if (isa<ZExtInst>(Val.V))
453 Val.withZExtOfValue(cast<CastInst>(Val.V)->getOperand(0)),
456 if (isa<SExtInst>(Val.V))
458 Val.withSExtOfValue(cast<CastInst>(Val.V)->getOperand(0)),
470 assert(IndexSize <=
Offset.getBitWidth() &&
"Invalid IndexSize!");
471 unsigned ShiftBits =
Offset.getBitWidth() - IndexSize;
472 if (ShiftBits != 0) {
474 Offset.ashrInPlace(ShiftBits);
481struct VariableGEPIndex {
496 bool hasNegatedScaleOf(
const VariableGEPIndex &
Other)
const {
497 if (IsNegated ==
Other.IsNegated)
498 return Scale == -
Other.Scale;
499 return Scale ==
Other.Scale;
507 OS <<
"(V=" << Val.V->getName()
508 <<
", zextbits=" << Val.ZExtBits
509 <<
", sextbits=" << Val.SExtBits
510 <<
", truncbits=" << Val.TruncBits
511 <<
", scale=" << Scale
513 <<
", negated=" << IsNegated <<
")";
562 const Instruction *CxtI = dyn_cast<Instruction>(V);
564 unsigned MaxIndexSize =
DL.getMaxIndexSizeInBits();
565 DecomposedGEP Decomposed;
566 Decomposed.Offset =
APInt(MaxIndexSize, 0);
572 if (
const GlobalAlias *GA = dyn_cast<GlobalAlias>(V)) {
573 if (!GA->isInterposable()) {
574 V = GA->getAliasee();
582 if (
Op->getOpcode() == Instruction::BitCast ||
583 Op->getOpcode() == Instruction::AddrSpaceCast) {
584 V =
Op->getOperand(0);
590 if (
const auto *
PHI = dyn_cast<PHINode>(V)) {
592 if (
PHI->getNumIncomingValues() == 1) {
593 V =
PHI->getIncomingValue(0);
596 }
else if (
const auto *Call = dyn_cast<CallBase>(V)) {
618 if (Decomposed.InBounds == std::nullopt)
621 Decomposed.InBounds =
false;
628 unsigned IndexSize =
DL.getIndexSizeInBits(AS);
630 bool GepHasConstantOffset =
true;
632 I != E; ++
I, ++GTI) {
637 unsigned FieldNo = cast<ConstantInt>(
Index)->getZExtValue();
641 Decomposed.Offset +=
DL.getStructLayout(STy)->getElementOffset(FieldNo);
658 CIdx->getValue().sextOrTrunc(MaxIndexSize);
668 GepHasConstantOffset =
false;
672 unsigned Width =
Index->getType()->getIntegerBitWidth();
673 unsigned SExtBits = IndexSize > Width ? IndexSize - Width : 0;
674 unsigned TruncBits = IndexSize < Width ? Width - IndexSize : 0;
676 CastedValue(
Index, 0, SExtBits, TruncBits), DL, 0, AC, DT);
681 Decomposed.Offset +=
LE.Offset.sext(MaxIndexSize);
682 APInt Scale =
LE.Scale.sext(MaxIndexSize);
688 for (
unsigned i = 0, e = Decomposed.VarIndices.size(); i != e; ++i) {
689 if ((Decomposed.VarIndices[i].Val.V ==
LE.Val.V ||
691 Decomposed.VarIndices[i].Val.hasSameCastsAs(
LE.Val)) {
692 Scale += Decomposed.VarIndices[i].Scale;
694 Decomposed.VarIndices.erase(Decomposed.VarIndices.begin() + i);
704 VariableGEPIndex Entry = {
LE.Val, Scale, CxtI,
LE.IsNSW,
706 Decomposed.VarIndices.push_back(Entry);
711 if (GepHasConstantOffset)
716 }
while (--MaxLookup);
720 SearchLimitReached++;
727 assert(Visited.empty() &&
"Visited must be cleared after use!");
730 unsigned MaxLookup = 8;
737 if (!Visited.insert(V).second)
741 if (IgnoreLocals && isa<AllocaInst>(V))
750 if (
const Argument *Arg = dyn_cast<Argument>(V)) {
751 if (Arg->hasNoAliasAttr() && Arg->onlyReadsMemory()) {
762 if (!GV->isConstant())
768 if (
const SelectInst *SI = dyn_cast<SelectInst>(V)) {
776 if (
const PHINode *PN = dyn_cast<PHINode>(V)) {
778 if (PN->getNumIncomingValues() > MaxLookup)
786 }
while (!Worklist.
empty() && --MaxLookup);
789 if (!Worklist.
empty())
803 MemoryEffects Min = Call->getAttributes().getMemoryEffects();
805 if (
const Function *F = dyn_cast<Function>(Call->getCalledOperand())) {
809 if (Call->hasReadingOperandBundles())
811 if (Call->hasClobberingOperandBundles())
822 switch (
F->getIntrinsicID()) {
823 case Intrinsic::experimental_guard:
824 case Intrinsic::experimental_deoptimize:
831 return F->getMemoryEffects();
836 if (Call->paramHasAttr(ArgIdx, Attribute::WriteOnly))
839 if (Call->paramHasAttr(ArgIdx, Attribute::ReadOnly))
842 if (Call->paramHasAttr(ArgIdx, Attribute::ReadNone))
850 if (
const Instruction *inst = dyn_cast<Instruction>(V)) {
851 if (!inst->getParent())
856 if (
const Argument *arg = dyn_cast<Argument>(V))
857 return arg->getParent();
867 return !F1 || !F2 || F1 == F2;
875 "BasicAliasAnalysis doesn't support interprocedural queries.");
876 return aliasCheck(LocA.
Ptr, LocA.
Size, LocB.
Ptr, LocB.
Size, AAQI, CtxI);
889 "AliasAnalysis query involving multiple functions!");
898 if (isa<AllocaInst>(Object))
899 if (
const CallInst *CI = dyn_cast<CallInst>(Call))
900 if (CI->isTailCall() &&
901 !CI->getAttributes().hasAttrSomewhere(Attribute::ByVal))
906 if (
auto *AI = dyn_cast<AllocaInst>(Object))
907 if (!AI->isStaticAlloca() &&
isIntrinsicCall(Call, Intrinsic::stackrestore))
915 if (!isa<Constant>(Object) && Call != Object &&
922 unsigned OperandNo = 0;
923 for (
auto CI = Call->data_operands_begin(), CE = Call->data_operands_end();
924 CI != CE; ++CI, ++OperandNo) {
925 if (!(*CI)->getType()->isPointerTy())
930 if (Call->doesNotAccessMemory(OperandNo))
943 if (Call->onlyReadsMemory(OperandNo)) {
948 if (Call->onlyWritesMemory(OperandNo)) {
1046 return (isa<AllocaInst>(V) || isa<GlobalVariable>(V));
1062 if (!isa<GEPOperator>(V2))
1075 DecomposedGEP DecompGEP1 = DecomposeGEPExpression(GEP1, DL, &AC, DT);
1076 DecomposedGEP DecompGEP2 = DecomposeGEPExpression(V2, DL, &AC, DT);
1079 if (DecompGEP1.Base == GEP1 && DecompGEP2.Base == V2)
1084 subtractDecomposedGEPs(DecompGEP1, DecompGEP2, AAQI);
1090 if (*DecompGEP1.InBounds && DecompGEP1.VarIndices.empty() &&
1092 DecompGEP1.Offset.sge(V2Size.
getValue()) &&
1096 if (isa<GEPOperator>(V2)) {
1098 if (*DecompGEP2.InBounds && DecompGEP1.VarIndices.empty() &&
1100 DecompGEP1.Offset.sle(-V1Size.
getValue()) &&
1107 if (DecompGEP1.Offset == 0 && DecompGEP1.VarIndices.empty())
1128 if (DecompGEP1.VarIndices.empty()) {
1133 const Value *RightPtr = GEP1;
1136 const bool Swapped =
Off.isNegative();
1155 if (
Off.ult(LSize)) {
1160 Off.ule(INT32_MAX) && (Off + VRightSize.
getValue()).ule(LSize)) {
1176 if (!Overflow &&
Off.uge(UpperRange))
1184 if (DecompGEP1.VarIndices.size() == 1 &&
1185 DecompGEP1.VarIndices[0].Val.TruncBits == 0 &&
1186 DecompGEP1.Offset.isZero() &&
1189 const VariableGEPIndex &ScalableVar = DecompGEP1.VarIndices[0];
1191 ScalableVar.IsNegated ? -ScalableVar.Scale : ScalableVar.Scale;
1196 bool Overflows = !DecompGEP1.VarIndices[0].IsNSW;
1222 for (
unsigned i = 0, e = DecompGEP1.VarIndices.size(); i != e; ++i) {
1223 const VariableGEPIndex &
Index = DecompGEP1.VarIndices[i];
1225 APInt ScaleForGCD = Scale;
1231 GCD = ScaleForGCD.
abs();
1236 true, &AC,
Index.CxtI);
1245 "Bit widths are normalized to MaxIndexSize");
1251 if (
Index.IsNegated)
1252 OffsetRange = OffsetRange.
sub(CR);
1254 OffsetRange = OffsetRange.
add(CR);
1263 APInt ModOffset = DecompGEP1.Offset.
srem(GCD);
1267 (GCD - ModOffset).uge(V1Size.
getValue()))
1282 std::optional<APInt> MinAbsVarIndex;
1283 if (DecompGEP1.VarIndices.size() == 1) {
1285 const VariableGEPIndex &Var = DecompGEP1.VarIndices[0];
1286 if (Var.Val.TruncBits == 0 &&
1290 auto MultiplyByScaleNoWrap = [](
const VariableGEPIndex &Var) {
1294 int ValOrigBW = Var.Val.V->getType()->getPrimitiveSizeInBits();
1298 int MaxScaleValueBW = Var.Val.getBitWidth() - ValOrigBW;
1299 if (MaxScaleValueBW <= 0)
1301 return Var.Scale.ule(
1306 if (MultiplyByScaleNoWrap(Var)) {
1308 MinAbsVarIndex = Var.Scale.abs();
1311 }
else if (DecompGEP1.VarIndices.size() == 2) {
1316 const VariableGEPIndex &Var0 = DecompGEP1.VarIndices[0];
1317 const VariableGEPIndex &Var1 = DecompGEP1.VarIndices[1];
1318 if (Var0.hasNegatedScaleOf(Var1) && Var0.Val.TruncBits == 0 &&
1322 MinAbsVarIndex = Var0.Scale.abs();
1325 if (MinAbsVarIndex) {
1327 APInt OffsetLo = DecompGEP1.Offset - *MinAbsVarIndex;
1328 APInt OffsetHi = DecompGEP1.Offset + *MinAbsVarIndex;
1335 if (constantOffsetHeuristic(DecompGEP1, V1Size, V2Size, &AC, DT, AAQI))
1364 if (
const SelectInst *SI2 = dyn_cast<SelectInst>(V2))
1365 if (isValueEqualInPotentialCycles(
SI->getCondition(), SI2->getCondition(),
1401 if (
const PHINode *PN2 = dyn_cast<PHINode>(V2))
1402 if (PN2->getParent() == PN->
getParent()) {
1403 std::optional<AliasResult> Alias;
1424 bool isRecursive =
false;
1425 auto CheckForRecPhi = [&](
Value *PV) {
1436 Value *OnePhi =
nullptr;
1442 if (isa<PHINode>(PV1)) {
1443 if (OnePhi && OnePhi != PV1) {
1454 if (CheckForRecPhi(PV1))
1457 if (UniqueSrc.
insert(PV1).second)
1461 if (OnePhi && UniqueSrc.
size() > 1)
1496 for (
unsigned i = 1, e = V1Srcs.
size(); i != e; ++i) {
1522 V2 =
V2->stripPointerCastsForAliasAnalysis();
1526 if (isa<UndefValue>(V1) || isa<UndefValue>(V2))
1535 if (isValueEqualInPotentialCycles(V1, V2, AAQI))
1575 O2, dyn_cast<Instruction>(O1),
true))
1578 O1, dyn_cast<Instruction>(O2),
true))
1587 TLI, NullIsValidLocation)) ||
1590 TLI, NullIsValidLocation)))
1600 if (OBU.
getTagName() ==
"separate_storage") {
1610 auto ValidAssumeForPtrContext = [&](
const Value *
Ptr) {
1615 if (
const Argument *PtrA = dyn_cast<Argument>(
Ptr)) {
1624 if ((O1 == HintO1 && O2 == HintO2) || (O1 == HintO2 && O2 == HintO1)) {
1630 ValidAssumeForPtrContext(V1) || ValidAssumeForPtrContext(V2)) {
1654 if (AAQI.
Depth >= 512)
1663 const bool Swapped = V1 >
V2;
1669 auto &Entry = Pair.first->second;
1670 if (!Entry.isDefinitive()) {
1672 ++Entry.NumAssumptionUses;
1676 auto Result = Entry.Result;
1684 aliasCheckRecursive(V1, V1Size, V2, V2Size, AAQI, O1, O2);
1688 auto &Entry = It->second;
1691 bool AssumptionDisproven =
1693 if (AssumptionDisproven)
1700 Entry.Result.swap(Swapped);
1701 Entry.NumAssumptionUses = -1;
1706 if (AssumptionDisproven)
1722 if (
const GEPOperator *GV1 = dyn_cast<GEPOperator>(V1)) {
1726 }
else if (
const GEPOperator *GV2 = dyn_cast<GEPOperator>(V2)) {
1733 if (
const PHINode *PN = dyn_cast<PHINode>(V1)) {
1737 }
else if (
const PHINode *PN = dyn_cast<PHINode>(V2)) {
1748 }
else if (
const SelectInst *S2 = dyn_cast<SelectInst>(V2)) {
1774bool BasicAAResult::isValueEqualInPotentialCycles(
const Value *V,
1785 const Instruction *Inst = dyn_cast<Instruction>(V);
1793void BasicAAResult::subtractDecomposedGEPs(DecomposedGEP &DestGEP,
1794 const DecomposedGEP &SrcGEP,
1796 DestGEP.Offset -= SrcGEP.Offset;
1797 for (
const VariableGEPIndex &Src : SrcGEP.VarIndices) {
1801 for (
auto I :
enumerate(DestGEP.VarIndices)) {
1802 VariableGEPIndex &Dest =
I.value();
1803 if ((!isValueEqualInPotentialCycles(Dest.Val.V, Src.Val.V, AAQI) &&
1805 !Dest.Val.hasSameCastsAs(Src.Val))
1809 if (Dest.IsNegated) {
1810 Dest.Scale = -Dest.Scale;
1811 Dest.IsNegated =
false;
1817 if (Dest.Scale != Src.Scale) {
1818 Dest.Scale -= Src.Scale;
1821 DestGEP.VarIndices.erase(DestGEP.VarIndices.begin() +
I.index());
1829 VariableGEPIndex Entry = {Src.Val, Src.Scale, Src.CxtI, Src.IsNSW,
1831 DestGEP.VarIndices.push_back(Entry);
1836bool BasicAAResult::constantOffsetHeuristic(
const DecomposedGEP &
GEP,
1842 if (
GEP.VarIndices.size() != 2 || !MaybeV1Size.
hasValue() ||
1849 const VariableGEPIndex &Var0 =
GEP.VarIndices[0], &Var1 =
GEP.VarIndices[1];
1851 if (Var0.Val.TruncBits != 0 || !Var0.Val.hasSameCastsAs(Var1.Val) ||
1852 !Var0.hasNegatedScaleOf(Var1) ||
1853 Var0.Val.V->getType() != Var1.Val.V->getType())
1860 LinearExpression E0 =
1862 LinearExpression E1 =
1864 if (E0.Scale != E1.Scale || !E0.Val.hasSameCastsAs(E1.Val) ||
1865 !isValueEqualInPotentialCycles(E0.Val.V, E1.Val.V, AAQI))
1875 APInt MinDiff = E0.Offset - E1.Offset, Wrapped = -MinDiff;
1877 APInt MinDiffBytes =
1878 MinDiff.
zextOrTrunc(Var0.Scale.getBitWidth()) * Var0.Scale.
abs();
1884 return MinDiffBytes.
uge(V1Size +
GEP.Offset.abs()) &&
1885 MinDiffBytes.
uge(V2Size +
GEP.Offset.abs());
1907void BasicAAWrapperPass::anchor() {}
1910 "Basic Alias Analysis (stateless AA impl)",
true,
true)
1922 auto &ACT = getAnalysis<AssumptionCacheTracker>();
1923 auto &TLIWP = getAnalysis<TargetLibraryInfoWrapperPass>();
1924 auto &DTWP = getAnalysis<DominatorTreeWrapperPass>();
1927 TLIWP.getTLI(
F), ACT.getAssumptionCache(
F),
1928 &DTWP.getDomTree()));
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
This file implements a class to represent arbitrary precision integral constant values and operations...
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 cl::opt< bool > EnableRecPhiAnalysis("basic-aa-recphi", cl::Hidden, cl::init(true))
Enable analysis of recursive PHI nodes.
static const Function * getParent(const Value *V)
static bool isObjectSmallerThan(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 is smaller than Size.
static bool isBaseOfObject(const Value *V)
Return true if we know V to the base address of the corresponding memory object.
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 cl::opt< bool > EnableSeparateStorageAnalysis("basic-aa-separate-storage", cl::Hidden, cl::init(true))
static bool notDifferentParent(const Value *O1, const Value *O2)
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)
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 void adjustToIndexSize(APInt &Offset, unsigned IndexSize)
To ensure a pointer offset fits in an integer of size IndexSize (in bits) when that size is smaller t...
static bool isIntrinsicCall(const CallBase *Call, Intrinsic::ID IID)
static const unsigned MaxLookupSearchDepth
This is the interface for LLVM's primary stateless and local alias analysis.
block Block Frequency Analysis
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
This file contains the declarations for the subclasses of Constant, which represent the different fla...
std::optional< std::vector< StOtherPiece > > Other
This file provides utility analysis objects describing memory locations.
#define INITIALIZE_PASS_DEPENDENCY(depName)
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
place backedge safepoints impl
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file provides utility classes that use RAII to save and restore values.
This file defines the make_scope_exit function, which executes user-defined cleanup logic at scope ex...
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.
AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB)
The main low level interface to the alias analysis implementation.
MemoryEffects getMemoryEffects(const CallBase *Call)
Return the behavior of the given call site.
Class for arbitrary precision integers.
APInt umul_ov(const APInt &RHS, bool &Overflow) const
APInt zext(unsigned width) const
Zero extend to a new width.
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 isNegative() const
Determine sign of this APInt.
unsigned countr_zero() const
Count the number of trailing zero bits.
APInt srem(const APInt &RHS) const
Function for signed remainder operation.
APInt smul_ov(const APInt &RHS, bool &Overflow) const
bool isNonNegative() const
Determine if this APInt Value is non-negative (>= 0)
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)
API to communicate dependencies between analyses during invalidation.
bool invalidate(IRUnitT &IR, const PreservedAnalyses &PA)
Trigger the invalidation of some other analysis pass if not already handled and return whether it was...
A container for analyses that lazily runs them and caches their results.
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.
This represents the llvm.assume intrinsic.
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.
MutableArrayRef< ResultElem > assumptionsFor(const Value *V)
Access the list of assumptions which affect this value.
This is the AA result object for the basic, local, and stateless alias analysis.
ModRefInfo getModRefInfo(const CallBase *Call, const MemoryLocation &Loc, AAQueryInfo &AAQI)
Checks to see if the specified callsite can clobber the specified memory object.
ModRefInfo getArgModRefInfo(const CallBase *Call, unsigned ArgIdx)
Get the location associated with a pointer argument of a callsite.
MemoryEffects getMemoryEffects(const CallBase *Call, AAQueryInfo &AAQI)
Returns the behavior when calling the given call site.
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.
bool invalidate(Function &Fn, const PreservedAnalyses &PA, FunctionAnalysisManager::Invalidator &Inv)
Handle invalidation events in the new pass manager.
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...
BasicAAResult run(Function &F, FunctionAnalysisManager &AM)
LLVM Basic Block Representation.
iterator begin()
Instruction iterator methods.
bool isEntryBlock() const
Return true if this is the entry block of the containing function.
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...
OperandBundleUse getOperandBundleAt(unsigned Index) const
Return the operand bundle at a specific index.
This class represents a function call, abstracting a target machine's calling convention.
This is the shared class of boolean and integer constants.
A constant pointer value that points to null.
This class represents a range of values.
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 ConstantRange fromKnownBits(const KnownBits &Known, bool IsSigned)
Initialize a range based on a known bits constraint.
ConstantRange smul_fast(const ConstantRange &Other) const
Return range of possible values for a signed multiplication of this and Other.
bool isEmptySet() const
Return true if this set contains no members.
ConstantRange smul_sat(const ConstantRange &Other) const
Perform a signed saturating multiplication of two constant ranges.
APInt getUnsignedMax() const
Return the largest unsigned value contained in the ConstantRange.
ConstantRange intersectWith(const ConstantRange &CR, PreferredRangeType Type=Smallest) const
Return the range that results from the intersection of this range with another range.
APInt getSignedMax() const
Return the largest signed value contained in the ConstantRange.
uint32_t getBitWidth() const
Get the bit width of this ConstantRange.
ConstantRange sub(const ConstantRange &Other) const
Return a new range representing the possible values resulting from a subtraction of a value in this r...
ConstantRange sextOrTrunc(uint32_t BitWidth) const
Make this range have the bit width given by BitWidth.
This class represents an Operation in the Expression.
A parsed version of the target data layout string in and methods for querying it.
iterator find(const_arg_type_t< KeyT > Val)
std::pair< iterator, bool > try_emplace(KeyT &&Key, Ts &&... Args)
bool erase(const KeyT &Val)
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.
bool isNotCapturedBefore(const Value *Object, const Instruction *I, bool OrAt) override
Check whether Object is not captured before instruction I.
void removeInstruction(Instruction *I)
FunctionPass class - This class is used to implement most global optimizations.
bool isInBounds() const
Test whether this is an inbounds GEP, as defined by LangRef.html.
Type * getSourceElementType() const
unsigned getPointerAddressSpace() const
Method to return the address space of the pointer operand.
Module * getParent()
Get the module that this global value is contained inside of...
const BasicBlock * getParent() const
A wrapper class for inspecting calls to intrinsic functions.
Intrinsic::ID getIntrinsicID() const
Return the intrinsic ID of this intrinsic.
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()
Create MemoryEffectsBase that can read any memory.
static MemoryEffectsBase inaccessibleMemOnly(ModRefInfo MR=ModRefInfo::ModRef)
Create MemoryEffectsBase that can only access inaccessible memory.
static MemoryEffectsBase writeOnly()
Create MemoryEffectsBase that can write any memory.
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.
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.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
A set of analyses that are preserved following a run of a transformation pass.
This class represents the LLVM 'select' instruction.
bool isNotCapturedBefore(const Value *Object, const Instruction *I, bool OrAt) override
Check whether Object is not captured before instruction I.
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
void push_back(const T &Elt)
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(SmallPtrSetImpl< Type * > *Visited=nullptr) const
Return true if it makes sense to take the size of this type.
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.
Value * getOperand(unsigned i) const
LLVM Value Representation.
Type * getType() const
All values are typed, get the type of this value.
StringRef getName() const
Return a constant reference to the value's name.
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
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.
APInt GreatestCommonDivisor(APInt A, APInt B)
Compute GCD of two unsigned APInt values.
bool match(Val *V, const Pattern &P)
VScaleVal_match m_VScale()
initializer< Ty > init(const Ty &Val)
This is an optimization pass for GlobalISel generic memory operations.
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
bool isValidAssumeForContext(const Instruction *I, const Instruction *CxtI, const DominatorTree *DT=nullptr, bool AllowEphemerals=false)
Return true if it is valid to use the assumptions provided by an assume intrinsic,...
detail::scope_exit< std::decay_t< Callable > > make_scope_exit(Callable &&F)
const Value * getArgumentAliasingToReturnedPointer(const CallBase *Call, bool MustPreserveNullness)
This function returns call pointer argument that is considered the same by aliasing rules.
auto enumerate(FirstRange &&First, RestRanges &&...Rest)
Given two or more input ranges, returns a new range whose values are are tuples (A,...
bool isPotentiallyReachableFromMany(SmallVectorImpl< BasicBlock * > &Worklist, const BasicBlock *StopBB, const SmallPtrSetImpl< BasicBlock * > *ExclusionSet, const DominatorTree *DT=nullptr, const LoopInfo *LI=nullptr)
Determine whether there is at least one path from a block in 'Worklist' to 'StopBB' without passing t...
auto successors(const MachineBasicBlock *BB)
void append_range(Container &C, Range &&R)
Wrapper function to append range R to container C.
const Value * getUnderlyingObject(const Value *V, unsigned MaxLookup=6)
This method strips off any GEP address adjustments, pointer casts or llvm.threadlocal....
bool isNonEscapingLocalObject(const Value *V, SmallDenseMap< const Value *, bool, 8 > *IsCapturedCache=nullptr)
Returns true if the pointer is to a function-local object that never escapes from the function.
ConstantRange computeConstantRange(const Value *V, bool ForSigned, bool UseInstrInfo=true, AssumptionCache *AC=nullptr, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, unsigned Depth=0)
Determine the possible constant range of an integer or vector of integer value.
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 isModSet(const ModRefInfo MRI)
bool NullPointerIsDefined(const Function *F, unsigned AS=0)
Check whether null pointer dereferencing is considered undefined behavior for a given function or an ...
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
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...
FunctionPass * createBasicAAWrapperPass()
bool isMallocOrCallocLikeFn(const Value *V, const TargetLibraryInfo *TLI)
Tests if a value is a call or invoke to a library function that allocates memory similar to malloc or...
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.
Instruction * FindEarliestCapture(const Value *V, Function &F, bool ReturnCaptures, bool StoreCaptures, const DominatorTree &DT, unsigned MaxUsesToExplore=0)
bool isKnownNonEqual(const Value *V1, const Value *V2, const DataLayout &DL, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true)
Return true if the given values are known to be non-equal when defined.
void initializeBasicAAWrapperPassPass(PassRegistry &)
void computeKnownBits(const Value *V, KnownBits &Known, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true)
Determine which bits of V are known to be either zero or one and return them in the KnownZero/KnownOn...
bool isModAndRefSet(const ModRefInfo MRI)
bool isIdentifiedFunctionLocal(const Value *V)
Return true if V is umabigously identified at the function-level.
constexpr unsigned BitWidth
bool isEscapeSource(const Value *V)
Returns true if the pointer is one which would have been considered an escape by isNonEscapingLocalOb...
gep_type_iterator gep_type_begin(const User *GEP)
bool isIdentifiedObject(const Value *V)
Return true if this pointer refers to a distinct and identifiable object.
bool isPotentiallyReachable(const Instruction *From, const Instruction *To, const SmallPtrSetImpl< BasicBlock * > *ExclusionSet=nullptr, const DominatorTree *DT=nullptr, const LoopInfo *LI=nullptr)
Determine whether instruction 'To' is reachable from 'From', without passing through any blocks in Ex...
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
std::optional< bool > InBounds
SmallVector< VariableGEPIndex, 4 > VarIndices
void print(raw_ostream &OS) const
A special type used by analysis passes to provide an address that identifies that particular analysis...
virtual bool isNotCapturedBefore(const Value *Object, const Instruction *I, bool OrAt)=0
Check whether Object is not captured before instruction I.
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.
A lightweight accessor for an operand bundle meant to be passed around by value.
StringRef getTagName() const
Return the tag of this operand bundle as a string.
A utility class that uses RAII to save and restore the value of a variable.