88using namespace PatternMatch;
90#define DEBUG_TYPE "dse"
92STATISTIC(NumRemainingStores,
"Number of stores remaining after DSE");
93STATISTIC(NumRedundantStores,
"Number of redundant stores deleted");
94STATISTIC(NumFastStores,
"Number of stores deleted");
95STATISTIC(NumFastOther,
"Number of other instrs removed");
96STATISTIC(NumCompletePartials,
"Number of stores dead by later partials");
97STATISTIC(NumModifiedStores,
"Number of stores modified");
98STATISTIC(NumCFGChecks,
"Number of stores modified");
102 "Number of times a valid candidate is returned from getDomMemoryDef");
104 "Number iterations check for reads in getDomMemoryDef");
107 "Controls which MemoryDefs are eliminated.");
112 cl::desc(
"Enable partial-overwrite tracking in DSE"));
117 cl::desc(
"Enable partial store merging in DSE"));
121 cl::desc(
"The number of memory instructions to scan for "
122 "dead store elimination (default = 150)"));
125 cl::desc(
"The maximum number of steps while walking upwards to find "
126 "MemoryDefs that may be killed (default = 90)"));
130 cl::desc(
"The maximum number candidates that only partially overwrite the "
131 "killing MemoryDef to consider"
136 cl::desc(
"The number of MemoryDefs we consider as candidates to eliminated "
137 "other stores per basic block (default = 5000)"));
142 "The cost of a step in the same basic block as the killing MemoryDef"
148 cl::desc(
"The cost of a step in a different basic "
149 "block than the killing MemoryDef"
154 cl::desc(
"The maximum number of blocks to check when trying to prove that "
155 "all paths to an exit go through a killing block (default = 50)"));
165 cl::desc(
"Allow DSE to optimize memory accesses."));
177 if (isa<StoreInst>(
I))
181 switch (II->getIntrinsicID()) {
182 default:
return false;
183 case Intrinsic::memset:
184 case Intrinsic::memcpy:
185 case Intrinsic::memcpy_element_unordered_atomic:
186 case Intrinsic::memset_element_unordered_atomic:
203 return isa<AnyMemSetInst>(
I);
221enum OverwriteResult {
225 OW_PartialEarlierWithFullLater,
239 const auto *KillingII = dyn_cast<IntrinsicInst>(KillingI);
240 const auto *DeadII = dyn_cast<IntrinsicInst>(DeadI);
241 if (KillingII ==
nullptr || DeadII ==
nullptr)
243 if (KillingII->getIntrinsicID() != DeadII->getIntrinsicID())
245 if (KillingII->getIntrinsicID() == Intrinsic::masked_store) {
248 cast<VectorType>(KillingII->getArgOperand(0)->getType());
249 VectorType *DeadTy = cast<VectorType>(DeadII->getArgOperand(0)->getType());
250 if (KillingTy->getScalarSizeInBits() != DeadTy->getScalarSizeInBits())
253 if (KillingTy->getElementCount() != DeadTy->getElementCount())
258 if (KillingPtr != DeadPtr && !AA.
isMustAlias(KillingPtr, DeadPtr))
262 if (KillingII->getArgOperand(3) != DeadII->getArgOperand(3))
281 int64_t KillingOff, int64_t DeadOff,
292 KillingOff < int64_t(DeadOff + DeadSize) &&
293 int64_t(KillingOff + KillingSize) >= DeadOff) {
296 auto &IM = IOL[DeadI];
297 LLVM_DEBUG(
dbgs() <<
"DSE: Partial overwrite: DeadLoc [" << DeadOff <<
", "
298 << int64_t(DeadOff + DeadSize) <<
") KillingLoc ["
299 << KillingOff <<
", " << int64_t(KillingOff + KillingSize)
306 int64_t KillingIntStart = KillingOff;
307 int64_t KillingIntEnd = KillingOff + KillingSize;
311 auto ILI = IM.lower_bound(KillingIntStart);
312 if (ILI != IM.end() && ILI->second <= KillingIntEnd) {
316 KillingIntStart = std::min(KillingIntStart, ILI->second);
317 KillingIntEnd = std::max(KillingIntEnd, ILI->first);
326 while (ILI != IM.end() && ILI->second <= KillingIntEnd) {
327 assert(ILI->second > KillingIntStart &&
"Unexpected interval");
328 KillingIntEnd = std::max(KillingIntEnd, ILI->first);
333 IM[KillingIntEnd] = KillingIntStart;
336 if (ILI->second <= DeadOff && ILI->first >= int64_t(DeadOff + DeadSize)) {
337 LLVM_DEBUG(
dbgs() <<
"DSE: Full overwrite from partials: DeadLoc ["
338 << DeadOff <<
", " << int64_t(DeadOff + DeadSize)
339 <<
") Composite KillingLoc [" << ILI->second <<
", "
340 << ILI->first <<
")\n");
341 ++NumCompletePartials;
349 int64_t(DeadOff + DeadSize) > KillingOff &&
350 uint64_t(KillingOff - DeadOff) + KillingSize <= DeadSize) {
351 LLVM_DEBUG(
dbgs() <<
"DSE: Partial overwrite a dead load [" << DeadOff
352 <<
", " << int64_t(DeadOff + DeadSize)
353 <<
") by a killing store [" << KillingOff <<
", "
354 << int64_t(KillingOff + KillingSize) <<
")\n");
356 return OW_PartialEarlierWithFullLater;
369 (KillingOff > DeadOff && KillingOff < int64_t(DeadOff + DeadSize) &&
370 int64_t(KillingOff + KillingSize) >= int64_t(DeadOff + DeadSize)))
383 (KillingOff <= DeadOff && int64_t(KillingOff + KillingSize) > DeadOff)) {
384 assert(int64_t(KillingOff + KillingSize) < int64_t(DeadOff + DeadSize) &&
385 "Expect to be handled as OW_Complete");
405 using BlockAddressPair = std::pair<BasicBlock *, PHITransAddr>;
417 if (
auto *MemSet = dyn_cast<MemSetInst>(SecondI))
422 auto *MemLocPtr =
const_cast<Value *
>(MemLoc.
Ptr);
427 bool isFirstBlock =
true;
430 while (!WorkList.
empty()) {
442 assert(
B == SecondBB &&
"first block is not the store block");
444 isFirstBlock =
false;
450 for (; BI != EI; ++BI) {
452 if (
I->mayWriteToMemory() &&
I != SecondI)
458 "Should not hit the entry block because SI must be dominated by LI");
468 auto Inserted = Visited.
insert(std::make_pair(Pred, TranslatedPtr));
469 if (!Inserted.second) {
472 if (TranslatedPtr != Inserted.first->second)
477 WorkList.
push_back(std::make_pair(Pred, PredAddr));
486 uint64_t NewSizeInBits,
bool IsOverwriteEnd) {
488 uint64_t DeadSliceSizeInBits = OldSizeInBits - NewSizeInBits;
490 OldOffsetInBits + (IsOverwriteEnd ? NewSizeInBits : 0);
491 auto SetDeadFragExpr = [](
auto *Assign,
495 uint64_t RelativeOffset = DeadFragment.OffsetInBits -
496 Assign->getExpression()
501 Assign->getExpression(), RelativeOffset, DeadFragment.SizeInBits)) {
502 Assign->setExpression(*
NewExpr);
508 DIExpression::get(Assign->getContext(), std::nullopt),
509 DeadFragment.OffsetInBits, DeadFragment.SizeInBits);
510 Assign->setExpression(Expr);
511 Assign->setKillLocation();
518 auto GetDeadLink = [&Ctx, &LinkToNothing]() {
521 return LinkToNothing;
532 auto InsertAssignForOverlap = [&](
auto *Assign) {
533 std::optional<DIExpression::FragmentInfo> NewFragment;
535 DeadSliceSizeInBits, Assign,
540 Assign->setKillAddress();
541 Assign->setAssignId(GetDeadLink());
545 if (NewFragment->SizeInBits == 0)
549 auto *NewAssign =
static_cast<decltype(Assign)
>(Assign->clone());
550 NewAssign->insertAfter(Assign);
551 NewAssign->setAssignId(GetDeadLink());
553 SetDeadFragExpr(NewAssign, *NewFragment);
554 NewAssign->setKillAddress();
556 for_each(Linked, InsertAssignForOverlap);
557 for_each(LinkedDPVAssigns, InsertAssignForOverlap);
561 uint64_t &DeadSize, int64_t KillingStart,
562 uint64_t KillingSize,
bool IsOverwriteEnd) {
563 auto *DeadIntrinsic = cast<AnyMemIntrinsic>(DeadI);
564 Align PrefAlign = DeadIntrinsic->getDestAlign().valueOrOne();
580 int64_t ToRemoveStart = 0;
584 if (IsOverwriteEnd) {
589 ToRemoveStart = KillingStart + Off;
590 if (DeadSize <=
uint64_t(ToRemoveStart - DeadStart))
592 ToRemoveSize = DeadSize -
uint64_t(ToRemoveStart - DeadStart);
594 ToRemoveStart = DeadStart;
596 "Not overlapping accesses?");
597 ToRemoveSize = KillingSize -
uint64_t(DeadStart - KillingStart);
602 if (ToRemoveSize <= (PrefAlign.
value() - Off))
604 ToRemoveSize -= PrefAlign.
value() - Off;
607 "Should preserve selected alignment");
610 assert(ToRemoveSize > 0 &&
"Shouldn't reach here if nothing to remove");
611 assert(DeadSize > ToRemoveSize &&
"Can't remove more than original size");
613 uint64_t NewSize = DeadSize - ToRemoveSize;
614 if (
auto *AMI = dyn_cast<AtomicMemIntrinsic>(DeadI)) {
617 const uint32_t ElementSize = AMI->getElementSizeInBytes();
618 if (0 != NewSize % ElementSize)
623 << (IsOverwriteEnd ?
"END" :
"BEGIN") <<
": " << *DeadI
624 <<
"\n KILLER [" << ToRemoveStart <<
", "
625 << int64_t(ToRemoveStart + ToRemoveSize) <<
")\n");
627 Value *DeadWriteLength = DeadIntrinsic->getLength();
628 Value *TrimmedLength = ConstantInt::get(DeadWriteLength->
getType(), NewSize);
629 DeadIntrinsic->setLength(TrimmedLength);
630 DeadIntrinsic->setDestAlignment(PrefAlign);
632 Value *OrigDest = DeadIntrinsic->getRawDest();
633 if (!IsOverwriteEnd) {
634 Value *Indices[1] = {
635 ConstantInt::get(DeadWriteLength->
getType(), ToRemoveSize)};
639 NewDestGEP->
setDebugLoc(DeadIntrinsic->getDebugLoc());
640 DeadIntrinsic->setDest(NewDestGEP);
649 DeadStart += ToRemoveSize;
656 int64_t &DeadStart,
uint64_t &DeadSize) {
661 int64_t KillingStart = OII->second;
662 uint64_t KillingSize = OII->first - KillingStart;
664 assert(OII->first - KillingStart >= 0 &&
"Size expected to be positive");
666 if (KillingStart > DeadStart &&
669 (
uint64_t)(KillingStart - DeadStart) < DeadSize &&
672 KillingSize >= DeadSize - (
uint64_t)(KillingStart - DeadStart)) {
673 if (
tryToShorten(DeadI, DeadStart, DeadSize, KillingStart, KillingSize,
684 int64_t &DeadStart,
uint64_t &DeadSize) {
689 int64_t KillingStart = OII->second;
690 uint64_t KillingSize = OII->first - KillingStart;
692 assert(OII->first - KillingStart >= 0 &&
"Size expected to be positive");
694 if (KillingStart <= DeadStart &&
697 KillingSize > (
uint64_t)(DeadStart - KillingStart)) {
700 assert(KillingSize - (
uint64_t)(DeadStart - KillingStart) < DeadSize &&
701 "Should have been handled as OW_Complete");
702 if (
tryToShorten(DeadI, DeadStart, DeadSize, KillingStart, KillingSize,
713 int64_t KillingOffset, int64_t DeadOffset,
740 unsigned BitOffsetDiff = (KillingOffset - DeadOffset) * 8;
741 unsigned LShiftAmount =
742 DL.isBigEndian() ? DeadValue.
getBitWidth() - BitOffsetDiff - KillingBits
745 LShiftAmount + KillingBits);
748 APInt Merged = (DeadValue & ~Mask) | (KillingValue << LShiftAmount);
750 <<
"\n Killing: " << *KillingI
751 <<
"\n Merged Value: " << Merged <<
'\n');
761 switch (II->getIntrinsicID()) {
762 case Intrinsic::lifetime_start:
763 case Intrinsic::lifetime_end:
764 case Intrinsic::invariant_end:
765 case Intrinsic::launder_invariant_group:
766 case Intrinsic::assume:
768 case Intrinsic::dbg_declare:
769 case Intrinsic::dbg_label:
770 case Intrinsic::dbg_value:
780bool canSkipDef(
MemoryDef *
D,
bool DefVisibleToCaller) {
784 if (
auto *CB = dyn_cast<CallBase>(DI))
785 if (CB->onlyAccessesInaccessibleMemory())
790 if (DI->
mayThrow() && !DefVisibleToCaller)
798 if (isa<FenceInst>(DI))
802 if (isNoopIntrinsic(DI))
831 bool ContainsIrreducibleLoops;
854 bool AnyUnreachableExit;
859 bool ShouldIterateEndOfFunctionDSE;
865 DSEState(
const DSEState &) =
delete;
866 DSEState &operator=(
const DSEState &) =
delete;
871 :
F(
F), AA(AA), EI(DT, &LI), BatchAA(AA, &EI), MSSA(MSSA), DT(DT),
872 PDT(PDT), TLI(TLI),
DL(
F.
getParent()->getDataLayout()), LI(LI) {
877 PostOrderNumbers[BB] = PO++;
880 if (
I.mayThrow() && !MA)
881 ThrowingBlocks.
insert(
I.getParent());
883 auto *MD = dyn_cast_or_null<MemoryDef>(MA);
885 (getLocForWrite(&
I) || isMemTerminatorInst(&
I)))
893 if (AI.hasPassPointeeByValueCopyAttr())
894 InvisibleToCallerAfterRet.
insert({&AI,
true});
900 return isa<UnreachableInst>(E->getTerminator());
906 if (
auto *CB = dyn_cast<CallBase>(
I)) {
909 (F == LibFunc_memset_chk || F == LibFunc_memcpy_chk)) {
918 if (
const auto *Len = dyn_cast<ConstantInt>(CB->getArgOperand(2)))
933 OverwriteResult isOverwrite(
const Instruction *KillingI,
937 int64_t &KillingOff, int64_t &DeadOff) {
941 if (!isGuaranteedLoopIndependent(DeadI, KillingI, DeadLoc))
945 strengthenLocationSize(KillingI, KillingLoc.
Size);
953 if (DeadUndObj == KillingUndObj && KillingLocSize.
isPrecise() &&
955 std::optional<TypeSize> KillingUndObjSize =
957 if (KillingUndObjSize && *KillingUndObjSize == KillingLocSize.
getValue())
966 const auto *KillingMemI = dyn_cast<MemIntrinsic>(KillingI);
967 const auto *DeadMemI = dyn_cast<MemIntrinsic>(DeadI);
968 if (KillingMemI && DeadMemI) {
969 const Value *KillingV = KillingMemI->getLength();
970 const Value *DeadV = DeadMemI->getLength();
971 if (KillingV == DeadV && BatchAA.
isMustAlias(DeadLoc, KillingLoc))
984 const bool AnyScalable =
996 if (KillingSize >= DeadSize)
1003 if (Off >= 0 && (
uint64_t)Off + DeadSize <= KillingSize)
1009 if (DeadUndObj != KillingUndObj) {
1025 const Value *DeadBasePtr =
1027 const Value *KillingBasePtr =
1032 if (DeadBasePtr != KillingBasePtr)
1050 if (DeadOff >= KillingOff) {
1053 if (
uint64_t(DeadOff - KillingOff) + DeadSize <= KillingSize)
1057 else if ((
uint64_t)(DeadOff - KillingOff) < KillingSize)
1058 return OW_MaybePartial;
1062 else if ((
uint64_t)(KillingOff - DeadOff) < DeadSize) {
1063 return OW_MaybePartial;
1070 bool isInvisibleToCallerAfterRet(
const Value *V) {
1071 if (isa<AllocaInst>(V))
1073 auto I = InvisibleToCallerAfterRet.
insert({
V,
false});
1075 if (!isInvisibleToCallerOnUnwind(V)) {
1076 I.first->second =
false;
1081 return I.first->second;
1084 bool isInvisibleToCallerOnUnwind(
const Value *V) {
1085 bool RequiresNoCaptureBeforeUnwind;
1088 if (!RequiresNoCaptureBeforeUnwind)
1091 auto I = CapturedBeforeReturn.
insert({
V,
true});
1098 return !
I.first->second;
1101 std::optional<MemoryLocation> getLocForWrite(
Instruction *
I)
const {
1102 if (!
I->mayWriteToMemory())
1103 return std::nullopt;
1105 if (
auto *CB = dyn_cast<CallBase>(
I))
1114 assert(getLocForWrite(
I) &&
"Must have analyzable write");
1118 return SI->isUnordered();
1120 if (
auto *CB = dyn_cast<CallBase>(
I)) {
1122 if (
auto *
MI = dyn_cast<MemIntrinsic>(CB))
1123 return !
MI->isVolatile();
1127 if (CB->isLifetimeStartOrEnd())
1130 return CB->use_empty() && CB->willReturn() && CB->doesNotThrow() &&
1131 !CB->isTerminator();
1147 if (
auto *CB = dyn_cast<CallBase>(UseInst))
1148 if (CB->onlyAccessesInaccessibleMemory())
1151 int64_t InstWriteOffset, DepWriteOffset;
1152 if (
auto CC = getLocForWrite(UseInst))
1153 return isOverwrite(UseInst, DefInst, *
CC, DefLoc, InstWriteOffset,
1154 DepWriteOffset) == OW_Complete;
1159 bool isWriteAtEndOfFunction(
MemoryDef *Def) {
1161 << *
Def->getMemoryInst()
1162 <<
") is at the end the function \n");
1164 auto MaybeLoc = getLocForWrite(
Def->getMemoryInst());
1166 LLVM_DEBUG(
dbgs() <<
" ... could not get location for write.\n");
1172 auto PushMemUses = [&WorkList, &Visited](
MemoryAccess *Acc) {
1173 if (!Visited.
insert(Acc).second)
1176 WorkList.
push_back(cast<MemoryAccess>(
U.getUser()));
1179 for (
unsigned I = 0;
I < WorkList.
size();
I++) {
1186 if (isa<MemoryPhi>(UseAccess)) {
1190 if (!isGuaranteedLoopInvariant(MaybeLoc->Ptr))
1193 PushMemUses(cast<MemoryPhi>(UseAccess));
1198 Instruction *UseInst = cast<MemoryUseOrDef>(UseAccess)->getMemoryInst();
1199 if (isReadClobber(*MaybeLoc, UseInst)) {
1200 LLVM_DEBUG(
dbgs() <<
" ... hit read clobber " << *UseInst <<
".\n");
1204 if (
MemoryDef *UseDef = dyn_cast<MemoryDef>(UseAccess))
1205 PushMemUses(UseDef);
1213 std::optional<std::pair<MemoryLocation, bool>>
1221 if (
auto *CB = dyn_cast<CallBase>(
I)) {
1226 return std::nullopt;
1232 auto *CB = dyn_cast<CallBase>(
I);
1233 return CB && (CB->getIntrinsicID() == Intrinsic::lifetime_end ||
1241 std::optional<std::pair<MemoryLocation, bool>> MaybeTermLoc =
1242 getLocForTerminator(MaybeTerm);
1253 auto TermLoc = MaybeTermLoc->first;
1254 if (MaybeTermLoc->second) {
1258 int64_t InstWriteOffset = 0;
1259 int64_t DepWriteOffset = 0;
1260 return isOverwrite(MaybeTerm, AccessI, TermLoc, Loc, InstWriteOffset,
1261 DepWriteOffset) == OW_Complete;
1266 if (isNoopIntrinsic(UseInst))
1271 if (
auto SI = dyn_cast<StoreInst>(UseInst))
1277 if (
auto *CB = dyn_cast<CallBase>(UseInst))
1278 if (CB->onlyAccessesInaccessibleMemory())
1289 bool isGuaranteedLoopIndependent(
const Instruction *Current,
1299 if (!ContainsIrreducibleLoops && CurrentLI &&
1303 return isGuaranteedLoopInvariant(CurrentLoc.
Ptr);
1309 bool isGuaranteedLoopInvariant(
const Value *
Ptr) {
1310 Ptr =
Ptr->stripPointerCasts();
1311 if (
auto *
GEP = dyn_cast<GEPOperator>(
Ptr))
1312 if (
GEP->hasAllConstantIndices())
1313 Ptr =
GEP->getPointerOperand()->stripPointerCasts();
1315 if (
auto *
I = dyn_cast<Instruction>(
Ptr)) {
1316 return I->getParent()->isEntryBlock() ||
1317 (!ContainsIrreducibleLoops && !LI.
getLoopFor(
I->getParent()));
1328 std::optional<MemoryAccess *>
1331 unsigned &ScanLimit,
unsigned &WalkerStepLimit,
1332 bool IsMemTerm,
unsigned &PartialLimit) {
1333 if (ScanLimit == 0 || WalkerStepLimit == 0) {
1335 return std::nullopt;
1352 std::optional<MemoryLocation> CurrentLoc;
1353 for (;; Current = cast<MemoryDef>(Current)->getDefiningAccess()) {
1355 dbgs() <<
" visiting " << *Current;
1357 dbgs() <<
" (" << *cast<MemoryUseOrDef>(Current)->getMemoryInst()
1368 return std::nullopt;
1376 if (WalkerStepLimit <= StepCost) {
1378 return std::nullopt;
1380 WalkerStepLimit -= StepCost;
1384 if (isa<MemoryPhi>(Current)) {
1391 MemoryDef *CurrentDef = cast<MemoryDef>(Current);
1394 if (canSkipDef(CurrentDef, !isInvisibleToCallerOnUnwind(KillingUndObj))) {
1395 CanOptimize =
false;
1401 if (mayThrowBetween(KillingI, CurrentI, KillingUndObj)) {
1403 return std::nullopt;
1408 if (isDSEBarrier(KillingUndObj, CurrentI)) {
1410 return std::nullopt;
1417 if (!isa<IntrinsicInst>(CurrentI) && isReadClobber(KillingLoc, CurrentI))
1418 return std::nullopt;
1421 if (
any_of(Current->
uses(), [
this, &KillingLoc, StartAccess](
Use &U) {
1422 if (auto *UseOrDef = dyn_cast<MemoryUseOrDef>(U.getUser()))
1423 return !MSSA.dominates(StartAccess, UseOrDef) &&
1424 isReadClobber(KillingLoc, UseOrDef->getMemoryInst());
1428 return std::nullopt;
1433 CurrentLoc = getLocForWrite(CurrentI);
1434 if (!CurrentLoc || !isRemovable(CurrentI)) {
1435 CanOptimize =
false;
1442 if (!isGuaranteedLoopIndependent(CurrentI, KillingI, *CurrentLoc)) {
1444 CanOptimize =
false;
1452 if (!isMemTerminator(*CurrentLoc, CurrentI, KillingI)) {
1453 CanOptimize =
false;
1457 int64_t KillingOffset = 0;
1458 int64_t DeadOffset = 0;
1459 auto OR = isOverwrite(KillingI, CurrentI, KillingLoc, *CurrentLoc,
1460 KillingOffset, DeadOffset);
1466 (OR == OW_Complete || OR == OW_MaybePartial))
1472 CanOptimize =
false;
1477 if (OR == OW_Unknown || OR == OW_None)
1479 else if (OR == OW_MaybePartial) {
1484 if (PartialLimit <= 1) {
1485 WalkerStepLimit -= 1;
1486 LLVM_DEBUG(
dbgs() <<
" ... reached partial limit ... continue with next access\n");
1503 Instruction *MaybeDeadI = cast<MemoryDef>(MaybeDeadAccess)->getMemoryInst();
1504 LLVM_DEBUG(
dbgs() <<
" Checking for reads of " << *MaybeDeadAccess <<
" ("
1505 << *MaybeDeadI <<
")\n");
1510 WorkList.
insert(cast<MemoryAccess>(
U.getUser()));
1512 PushMemUses(MaybeDeadAccess);
1515 for (
unsigned I = 0;
I < WorkList.
size();
I++) {
1520 if (ScanLimit < (WorkList.
size() -
I)) {
1522 return std::nullopt;
1525 NumDomMemDefChecks++;
1527 if (isa<MemoryPhi>(UseAccess)) {
1532 LLVM_DEBUG(
dbgs() <<
" ... skipping, dominated by killing block\n");
1536 PushMemUses(UseAccess);
1540 Instruction *UseInst = cast<MemoryUseOrDef>(UseAccess)->getMemoryInst();
1546 LLVM_DEBUG(
dbgs() <<
" ... skipping, dominated by killing def\n");
1552 if (isMemTerminator(MaybeDeadLoc, MaybeDeadI, UseInst)) {
1555 <<
" ... skipping, memterminator invalidates following accesses\n");
1559 if (isNoopIntrinsic(cast<MemoryUseOrDef>(UseAccess)->getMemoryInst())) {
1561 PushMemUses(UseAccess);
1565 if (UseInst->
mayThrow() && !isInvisibleToCallerOnUnwind(KillingUndObj)) {
1567 return std::nullopt;
1572 if (isReadClobber(MaybeDeadLoc, UseInst)) {
1574 return std::nullopt;
1580 if (MaybeDeadAccess == UseAccess &&
1581 !isGuaranteedLoopInvariant(MaybeDeadLoc.
Ptr)) {
1582 LLVM_DEBUG(
dbgs() <<
" ... found not loop invariant self access\n");
1583 return std::nullopt;
1589 if (KillingDef == UseAccess || MaybeDeadAccess == UseAccess) {
1604 if (
MemoryDef *UseDef = dyn_cast<MemoryDef>(UseAccess)) {
1605 if (isCompleteOverwrite(MaybeDeadLoc, MaybeDeadI, UseInst)) {
1607 if (PostOrderNumbers.
find(MaybeKillingBlock)->second <
1608 PostOrderNumbers.
find(MaybeDeadAccess->
getBlock())->second) {
1609 if (!isInvisibleToCallerAfterRet(KillingUndObj)) {
1611 <<
" ... found killing def " << *UseInst <<
"\n");
1612 KillingDefs.
insert(UseInst);
1616 <<
" ... found preceeding def " << *UseInst <<
"\n");
1617 return std::nullopt;
1620 PushMemUses(UseDef);
1627 if (!isInvisibleToCallerAfterRet(KillingUndObj)) {
1630 KillingBlocks.
insert(KD->getParent());
1632 "Expected at least a single killing block");
1646 if (!AnyUnreachableExit)
1647 return std::nullopt;
1651 CommonPred =
nullptr;
1655 if (KillingBlocks.
count(CommonPred))
1656 return {MaybeDeadAccess};
1662 WorkList.
insert(CommonPred);
1665 if (!isa<UnreachableInst>(
R->getTerminator()))
1672 for (
unsigned I = 0;
I < WorkList.
size();
I++) {
1675 if (KillingBlocks.
count(Current))
1677 if (Current == MaybeDeadAccess->
getBlock())
1678 return std::nullopt;
1689 return std::nullopt;
1696 return {MaybeDeadAccess};
1707 while (!NowDeadInsts.
empty()) {
1717 bool IsMemDef = MA && isa<MemoryDef>(MA);
1720 auto *MD = cast<MemoryDef>(MA);
1722 if (
auto *SI = dyn_cast<StoreInst>(MD->getMemoryInst())) {
1723 if (
SI->getValueOperand()->getType()->isPointerTy()) {
1725 if (CapturedBeforeReturn.
erase(UO))
1726 ShouldIterateEndOfFunctionDSE =
true;
1727 InvisibleToCallerAfterRet.
erase(UO);
1732 Updater.removeMemoryAccess(MA);
1736 if (
I != IOLs.
end())
1737 I->second.erase(DeadInst);
1740 if (
Instruction *OpI = dyn_cast<Instruction>(O)) {
1764 const Value *KillingUndObj) {
1768 if (KillingUndObj && isInvisibleToCallerOnUnwind(KillingUndObj))
1773 return !ThrowingBlocks.
empty();
1784 if (DeadI->
mayThrow() && !isInvisibleToCallerOnUnwind(KillingUndObj))
1790 if (
auto *LI = dyn_cast<LoadInst>(DeadI))
1792 if (
auto *SI = dyn_cast<StoreInst>(DeadI))
1794 if (
auto *ARMW = dyn_cast<AtomicRMWInst>(DeadI))
1796 if (
auto *CmpXchg = dyn_cast<AtomicCmpXchgInst>(DeadI))
1806 bool eliminateDeadWritesAtEndOfFunction() {
1807 bool MadeChange =
false;
1810 <<
"Trying to eliminate MemoryDefs at the end of the function\n");
1812 ShouldIterateEndOfFunctionDSE =
false;
1818 auto DefLoc = getLocForWrite(DefI);
1819 if (!DefLoc || !isRemovable(DefI))
1828 if (!isInvisibleToCallerAfterRet(UO))
1831 if (isWriteAtEndOfFunction(Def)) {
1833 LLVM_DEBUG(
dbgs() <<
" ... MemoryDef is not accessed until the end "
1834 "of the function\n");
1840 }
while (ShouldIterateEndOfFunctionDSE);
1848 MemSetInst *MemSet = dyn_cast<MemSetInst>(DefI);
1853 if (!StoredConstant || !StoredConstant->
isNullValue())
1856 if (!isRemovable(DefI))
1860 if (
F.hasFnAttribute(Attribute::SanitizeMemory) ||
1861 F.hasFnAttribute(Attribute::SanitizeAddress) ||
1862 F.hasFnAttribute(Attribute::SanitizeHWAddress) ||
1863 F.getName() ==
"calloc")
1865 auto *
Malloc =
const_cast<CallInst *
>(dyn_cast<CallInst>(DefUO));
1868 auto *InnerCallee =
Malloc->getCalledFunction();
1872 if (!TLI.
getLibFunc(*InnerCallee, Func) || !TLI.
has(Func) ||
1873 Func != LibFunc_malloc)
1883 auto *MallocBB =
Malloc->getParent(),
1884 *MemsetBB = Memset->getParent();
1885 if (MallocBB == MemsetBB)
1887 auto *
Ptr = Memset->getArgOperand(0);
1888 auto *TI = MallocBB->getTerminator();
1894 if (Pred != ICmpInst::ICMP_EQ || MemsetBB != FalseBB)
1901 if (!shouldCreateCalloc(
Malloc, MemSet) ||
1906 Type *SizeTTy =
Malloc->getArgOperand(0)->getType();
1907 auto *Calloc =
emitCalloc(ConstantInt::get(SizeTTy, 1),
1908 Malloc->getArgOperand(0), IRB, TLI);
1914 Updater.createMemoryAccessAfter(cast<Instruction>(Calloc),
nullptr,
1916 auto *NewAccessMD = cast<MemoryDef>(NewAccess);
1917 Updater.insertDef(NewAccessMD,
true);
1918 Malloc->replaceAllUsesWith(Calloc);
1925 bool dominatingConditionImpliesValue(
MemoryDef *Def) {
1926 auto *StoreI = cast<StoreInst>(
Def->getMemoryInst());
1928 Value *StorePtr = StoreI->getPointerOperand();
1929 Value *StoreVal = StoreI->getValueOperand();
1936 if (!BI || !BI->isConditional())
1942 if (BI->getSuccessor(0) == BI->getSuccessor(1))
1947 if (!
match(BI->getCondition(),
1957 if (Pred == ICmpInst::ICMP_EQ &&
1962 if (Pred == ICmpInst::ICMP_NE &&
1971 return MSSA.
dominates(ClobAcc, LoadAcc);
1979 MemSetInst *MemSet = dyn_cast<MemSetInst>(DefI);
1980 Constant *StoredConstant =
nullptr;
1982 StoredConstant = dyn_cast<Constant>(
Store->getOperand(0));
1984 StoredConstant = dyn_cast<Constant>(MemSet->
getValue());
1988 if (!isRemovable(DefI))
1991 if (StoredConstant) {
1996 if (InitC && InitC == StoredConstant)
2004 if (dominatingConditionImpliesValue(Def))
2007 if (
auto *LoadI = dyn_cast<LoadInst>(
Store->getOperand(0))) {
2008 if (LoadI->getPointerOperand() ==
Store->getOperand(1)) {
2012 if (LoadAccess ==
Def->getDefiningAccess())
2027 for (
unsigned I = 1;
I < ToCheck.
size(); ++
I) {
2028 Current = ToCheck[
I];
2029 if (
auto PhiAccess = dyn_cast<MemoryPhi>(Current)) {
2031 for (
auto &
Use : PhiAccess->incoming_values())
2032 ToCheck.
insert(cast<MemoryAccess>(&
Use));
2038 assert(isa<MemoryDef>(Current) &&
2039 "Only MemoryDefs should reach here.");
2044 if (LoadAccess != Current)
2055 bool Changed =
false;
2056 for (
auto OI : IOL) {
2059 assert(isRemovable(DeadI) &&
"Expect only removable instruction");
2062 int64_t DeadStart = 0;
2076 bool eliminateRedundantStoresOfExistingValues() {
2077 bool MadeChange =
false;
2078 LLVM_DEBUG(
dbgs() <<
"Trying to eliminate MemoryDefs that write the "
2079 "already existing value\n");
2080 for (
auto *Def : MemDefs) {
2085 auto MaybeDefLoc = getLocForWrite(DefInst);
2086 if (!MaybeDefLoc || !isRemovable(DefInst))
2093 if (
Def->isOptimized())
2094 UpperDef = dyn_cast<MemoryDef>(
Def->getOptimized());
2096 UpperDef = dyn_cast<MemoryDef>(
Def->getDefiningAccess());
2101 auto IsRedundantStore = [&]() {
2104 if (
auto *MemSetI = dyn_cast<MemSetInst>(UpperInst)) {
2105 if (
auto *SI = dyn_cast<StoreInst>(DefInst)) {
2108 int64_t InstWriteOffset = 0;
2109 int64_t DepWriteOffset = 0;
2110 auto OR = isOverwrite(UpperInst, DefInst, UpperLoc, *MaybeDefLoc,
2111 InstWriteOffset, DepWriteOffset);
2113 return StoredByte && StoredByte == MemSetI->getOperand(1) &&
2120 if (!IsRedundantStore() || isReadClobber(*MaybeDefLoc, DefInst))
2122 LLVM_DEBUG(
dbgs() <<
"DSE: Remove No-Op Store:\n DEAD: " << *DefInst
2125 NumRedundantStores++;
2136 bool MadeChange =
false;
2138 DSEState State(
F, AA, MSSA, DT, PDT, TLI, LI);
2140 for (
unsigned I = 0;
I < State.MemDefs.size();
I++) {
2142 if (State.SkipStores.count(KillingDef))
2146 std::optional<MemoryLocation> MaybeKillingLoc;
2147 if (State.isMemTerminatorInst(KillingI)) {
2148 if (
auto KillingLoc = State.getLocForTerminator(KillingI))
2149 MaybeKillingLoc = KillingLoc->first;
2151 MaybeKillingLoc = State.getLocForWrite(KillingI);
2154 if (!MaybeKillingLoc) {
2155 LLVM_DEBUG(
dbgs() <<
"Failed to find analyzable write location for "
2156 << *KillingI <<
"\n");
2160 assert(KillingLoc.
Ptr &&
"KillingLoc should not be null");
2163 << *KillingDef <<
" (" << *KillingI <<
")\n");
2172 bool Shortend =
false;
2173 bool IsMemTerm = State.isMemTerminatorInst(KillingI);
2175 for (
unsigned I = 0;
I < ToCheck.
size();
I++) {
2177 if (State.SkipStores.count(Current))
2180 std::optional<MemoryAccess *> MaybeDeadAccess = State.getDomMemoryDef(
2181 KillingDef, Current, KillingLoc, KillingUndObj, ScanLimit,
2182 WalkerStepLimit, IsMemTerm, PartialLimit);
2184 if (!MaybeDeadAccess) {
2190 LLVM_DEBUG(
dbgs() <<
" Checking if we can kill " << *DeadAccess);
2191 if (isa<MemoryPhi>(DeadAccess)) {
2192 LLVM_DEBUG(
dbgs() <<
"\n ... adding incoming values to worklist\n");
2193 for (
Value *V : cast<MemoryPhi>(DeadAccess)->incoming_values()) {
2201 if (State.PostOrderNumbers[IncomingBlock] >
2202 State.PostOrderNumbers[PhiBlock])
2203 ToCheck.
insert(IncomingAccess);
2207 auto *DeadDefAccess = cast<MemoryDef>(DeadAccess);
2208 Instruction *DeadI = DeadDefAccess->getMemoryInst();
2210 ToCheck.
insert(DeadDefAccess->getDefiningAccess());
2211 NumGetDomMemoryDefPassed++;
2220 if (KillingUndObj != DeadUndObj)
2222 LLVM_DEBUG(
dbgs() <<
"DSE: Remove Dead Store:\n DEAD: " << *DeadI
2223 <<
"\n KILLER: " << *KillingI <<
'\n');
2224 State.deleteDeadInstruction(DeadI);
2229 int64_t KillingOffset = 0;
2230 int64_t DeadOffset = 0;
2231 OverwriteResult
OR = State.isOverwrite(
2232 KillingI, DeadI, KillingLoc, DeadLoc, KillingOffset, DeadOffset);
2233 if (OR == OW_MaybePartial) {
2234 auto Iter = State.IOLs.insert(
2235 std::make_pair<BasicBlock *, InstOverlapIntervalsTy>(
2237 auto &IOL = Iter.first->second;
2239 DeadOffset, DeadI, IOL);
2243 auto *DeadSI = dyn_cast<StoreInst>(DeadI);
2244 auto *KillingSI = dyn_cast<StoreInst>(KillingI);
2248 if (DeadSI && KillingSI && DT.
dominates(DeadSI, KillingSI)) {
2250 KillingSI, DeadSI, KillingOffset, DeadOffset, State.DL,
2251 State.BatchAA, &DT)) {
2254 DeadSI->setOperand(0, Merged);
2255 ++NumModifiedStores;
2261 State.deleteDeadInstruction(KillingSI);
2262 auto I = State.IOLs.find(DeadSI->getParent());
2263 if (
I != State.IOLs.end())
2264 I->second.erase(DeadSI);
2270 if (OR == OW_Complete) {
2271 LLVM_DEBUG(
dbgs() <<
"DSE: Remove Dead Store:\n DEAD: " << *DeadI
2272 <<
"\n KILLER: " << *KillingI <<
'\n');
2273 State.deleteDeadInstruction(DeadI);
2281 if (!Shortend && State.storeIsNoop(KillingDef, KillingUndObj)) {
2282 LLVM_DEBUG(
dbgs() <<
"DSE: Remove No-Op Store:\n DEAD: " << *KillingI
2284 State.deleteDeadInstruction(KillingI);
2285 NumRedundantStores++;
2291 if (!Shortend && State.tryFoldIntoCalloc(KillingDef, KillingUndObj)) {
2292 LLVM_DEBUG(
dbgs() <<
"DSE: Remove memset after forming calloc:\n"
2293 <<
" DEAD: " << *KillingI <<
'\n');
2294 State.deleteDeadInstruction(KillingI);
2301 for (
auto &KV : State.IOLs)
2302 MadeChange |= State.removePartiallyOverlappedStores(KV.second);
2304 MadeChange |= State.eliminateRedundantStoresOfExistingValues();
2305 MadeChange |= State.eliminateDeadWritesAtEndOfFunction();
2307 while (!State.ToRemove.empty()) {
2308 Instruction *DeadInst = State.ToRemove.pop_back_val();
2327 bool Changed = eliminateDeadStores(
F, AA, MSSA, DT, PDT, TLI, LI);
2329#ifdef LLVM_ENABLE_STATS
2332 NumRemainingStores += isa<StoreInst>(&
I);
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
This file implements a class to represent arbitrary precision integral constant values and operations...
ReachingDefAnalysis InstSet & ToRemove
Expand Atomic instructions
static const Function * getParent(const Value *V)
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
This file contains the declarations for the subclasses of Constant, which represent the different fla...
static void shortenAssignment(Instruction *Inst, Value *OriginalDest, uint64_t OldOffsetInBits, uint64_t OldSizeInBits, uint64_t NewSizeInBits, bool IsOverwriteEnd)
static bool isShortenableAtTheEnd(Instruction *I)
Returns true if the end of this instruction can be safely shortened in length.
static cl::opt< bool > EnablePartialStoreMerging("enable-dse-partial-store-merging", cl::init(true), cl::Hidden, cl::desc("Enable partial store merging in DSE"))
static bool tryToShortenBegin(Instruction *DeadI, OverlapIntervalsTy &IntervalMap, int64_t &DeadStart, uint64_t &DeadSize)
std::map< int64_t, int64_t > OverlapIntervalsTy
static bool isShortenableAtTheBeginning(Instruction *I)
Returns true if the beginning of this instruction can be safely shortened in length.
static cl::opt< unsigned > MemorySSADefsPerBlockLimit("dse-memoryssa-defs-per-block-limit", cl::init(5000), cl::Hidden, cl::desc("The number of MemoryDefs we consider as candidates to eliminated " "other stores per basic block (default = 5000)"))
static Constant * tryToMergePartialOverlappingStores(StoreInst *KillingI, StoreInst *DeadI, int64_t KillingOffset, int64_t DeadOffset, const DataLayout &DL, BatchAAResults &AA, DominatorTree *DT)
static bool memoryIsNotModifiedBetween(Instruction *FirstI, Instruction *SecondI, BatchAAResults &AA, const DataLayout &DL, DominatorTree *DT)
Returns true if the memory which is accessed by the second instruction is not modified between the fi...
static OverwriteResult isMaskedStoreOverwrite(const Instruction *KillingI, const Instruction *DeadI, BatchAAResults &AA)
Check if two instruction are masked stores that completely overwrite one another.
static cl::opt< unsigned > MemorySSAOtherBBStepCost("dse-memoryssa-otherbb-cost", cl::init(5), cl::Hidden, cl::desc("The cost of a step in a different basic " "block than the killing MemoryDef" "(default = 5)"))
static bool tryToShorten(Instruction *DeadI, int64_t &DeadStart, uint64_t &DeadSize, int64_t KillingStart, uint64_t KillingSize, bool IsOverwriteEnd)
static cl::opt< unsigned > MemorySSAScanLimit("dse-memoryssa-scanlimit", cl::init(150), cl::Hidden, cl::desc("The number of memory instructions to scan for " "dead store elimination (default = 150)"))
static cl::opt< unsigned > MemorySSASameBBStepCost("dse-memoryssa-samebb-cost", cl::init(1), cl::Hidden, cl::desc("The cost of a step in the same basic block as the killing MemoryDef" "(default = 1)"))
static cl::opt< bool > EnablePartialOverwriteTracking("enable-dse-partial-overwrite-tracking", cl::init(true), cl::Hidden, cl::desc("Enable partial-overwrite tracking in DSE"))
static OverwriteResult isPartialOverwrite(const MemoryLocation &KillingLoc, const MemoryLocation &DeadLoc, int64_t KillingOff, int64_t DeadOff, Instruction *DeadI, InstOverlapIntervalsTy &IOL)
Return 'OW_Complete' if a store to the 'KillingLoc' location completely overwrites a store to the 'De...
static cl::opt< unsigned > MemorySSAPartialStoreLimit("dse-memoryssa-partial-store-limit", cl::init(5), cl::Hidden, cl::desc("The maximum number candidates that only partially overwrite the " "killing MemoryDef to consider" " (default = 5)"))
static std::optional< TypeSize > getPointerSize(const Value *V, const DataLayout &DL, const TargetLibraryInfo &TLI, const Function *F)
static bool tryToShortenEnd(Instruction *DeadI, OverlapIntervalsTy &IntervalMap, int64_t &DeadStart, uint64_t &DeadSize)
static cl::opt< unsigned > MemorySSAUpwardsStepLimit("dse-memoryssa-walklimit", cl::init(90), cl::Hidden, cl::desc("The maximum number of steps while walking upwards to find " "MemoryDefs that may be killed (default = 90)"))
static cl::opt< bool > OptimizeMemorySSA("dse-optimize-memoryssa", cl::init(true), cl::Hidden, cl::desc("Allow DSE to optimize memory accesses."))
static cl::opt< unsigned > MemorySSAPathCheckLimit("dse-memoryssa-path-check-limit", cl::init(50), cl::Hidden, cl::desc("The maximum number of blocks to check when trying to prove that " "all paths to an exit go through a killing block (default = 50)"))
This file provides an implementation of debug counters.
#define DEBUG_COUNTER(VARNAME, COUNTERNAME, DESC)
This file defines the DenseMap class.
This is the interface for a simple mod/ref and alias analysis over globals.
static void deleteDeadInstruction(Instruction *I)
This file implements a map that provides insertion order iteration.
This file provides utility analysis objects describing memory locations.
This file exposes an interface to building/using memory SSA to walk memory instructions using a use/d...
Module.h This file contains the declarations for the Module class.
Contains a collection of routines for determining if a given instruction is guaranteed to execute if ...
This header defines various interfaces for pass management in LLVM.
This file builds on the ADT/GraphTraits.h file to build a generic graph post order iterator.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file implements a set that has insertion order iteration characteristics.
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)
A manager for alias analyses.
Class for arbitrary precision integers.
APInt zext(unsigned width) const
Zero extend to a new width.
static APInt getBitsSet(unsigned numBits, unsigned loBit, unsigned hiBit)
Get a value with a block of bits set.
unsigned getBitWidth() const
Return the number of bits in the APInt.
The possible results of an alias query.
@ 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.
constexpr int32_t getOffset() const
constexpr bool hasOffset() const
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.
This class represents an incoming formal argument to a Function.
LLVM Basic Block Representation.
const Function * getParent() const
Return the enclosing method, or null if none.
InstListType::iterator iterator
Instruction iterators...
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
This class is a wrapper over an AAResults, and it is intended to be used only when there are no IR ch...
AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB)
bool isMustAlias(const MemoryLocation &LocA, const MemoryLocation &LocB)
ModRefInfo getModRefInfo(const Instruction *I, const std::optional< MemoryLocation > &OptLoc)
Represents analyses that only rely on functions' control flow.
This class represents a function call, abstracting a target machine's calling convention.
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
This is an important base class in LLVM.
bool isNullValue() const
Return true if this is the value that would be returned by getNullValue.
static DIAssignID * getDistinct(LLVMContext &Context)
static std::optional< DIExpression * > createFragmentExpression(const DIExpression *Expr, unsigned OffsetInBits, unsigned SizeInBits)
Create a DIExpression to describe one part of an aggregate variable that is fragmented across multipl...
PreservedAnalyses run(Function &F, FunctionAnalysisManager &FAM)
A parsed version of the target data layout string in and methods for querying it.
static bool shouldExecute(unsigned CounterName)
iterator find(const_arg_type_t< KeyT > Val)
bool erase(const KeyT &Val)
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
DomTreeNodeBase * getIDom() const
Analysis pass which computes a DominatorTree.
NodeT * findNearestCommonDominator(NodeT *A, NodeT *B) const
Find nearest common dominator basic block for basic block A and B.
iterator_range< root_iterator > roots()
DomTreeNodeBase< NodeT > * getNode(const NodeT *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
bool properlyDominates(const DomTreeNodeBase< NodeT > *A, const DomTreeNodeBase< NodeT > *B) const
properlyDominates - Returns true iff A dominates B and A != B.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
bool isReachableFromEntry(const Use &U) const
Provide an overload for a Use.
bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
Context-sensitive CaptureInfo provider, which computes and caches the earliest common dominator closu...
void removeInstruction(Instruction *I)
const BasicBlock & getEntryBlock() const
static GetElementPtrInst * CreateInBounds(Type *PointeeType, Value *Ptr, ArrayRef< Value * > IdxList, const Twine &NameStr, BasicBlock::iterator InsertBefore)
Create an "inbounds" getelementptr.
bool isEquality() const
Return true if this predicate is either EQ or NE.
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
bool mayThrow(bool IncludePhaseOneUnwind=false) const LLVM_READONLY
Return true if this instruction may throw an exception.
bool mayWriteToMemory() const LLVM_READONLY
Return true if this instruction may modify memory.
const Module * getModule() const
Return the module owning the function this instruction belongs to or nullptr it the function does not...
bool isAtomic() const LLVM_READONLY
Return true if this instruction has an AtomicOrdering of unordered or higher.
const BasicBlock * getParent() const
InstListType::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
bool mayReadFromMemory() const LLVM_READONLY
Return true if this instruction may read memory.
bool isIdenticalTo(const Instruction *I) const LLVM_READONLY
Return true if the specified instruction is exactly identical to the current one.
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
const_iterator begin() const
bool empty() const
empty - Return true when no intervals are mapped.
const_iterator end() const
A wrapper class for inspecting calls to intrinsic functions.
This is an important class for using LLVM in a threaded context.
static LocationSize precise(uint64_t Value)
TypeSize getValue() const
Analysis pass that exposes the LoopInfo for a function.
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
Represents a single loop in the control flow graph.
This class implements a map that also provides access to all stored values in a deterministic order.
iterator find(const KeyT &Key)
Value * getLength() const
This class wraps the llvm.memset and llvm.memset.inline intrinsics.
BasicBlock * getBlock() const
Represents a read-write access to memory, whether it is a must-alias, or a may-alias.
void setOptimized(MemoryAccess *MA)
Representation for a specific memory location.
static MemoryLocation get(const LoadInst *LI)
Return a location with information about the memory reference by the given instruction.
LocationSize Size
The maximum size of the location, in address-units, or UnknownSize if the size is not known.
static MemoryLocation getAfter(const Value *Ptr, const AAMDNodes &AATags=AAMDNodes())
Return a location that may access any location after Ptr, while remaining within the underlying objec...
MemoryLocation getWithNewPtr(const Value *NewPtr) const
const Value * Ptr
The address of the start of the location.
static MemoryLocation getForDest(const MemIntrinsic *MI)
Return a location representing the destination of a memory set or transfer.
static std::optional< MemoryLocation > getOrNone(const Instruction *Inst)
An analysis that produces MemorySSA for a function.
MemoryAccess * getClobberingMemoryAccess(const Instruction *I, BatchAAResults &AA)
Given a memory Mod/Ref/ModRef'ing instruction, calling this will give you the nearest dominating Memo...
Encapsulates MemorySSA, including all data associated with memory accesses.
MemorySSAWalker * getSkipSelfWalker()
bool dominates(const MemoryAccess *A, const MemoryAccess *B) const
Given two memory accesses in potentially different blocks, determine whether MemoryAccess A dominates...
MemorySSAWalker * getWalker()
MemoryUseOrDef * getMemoryAccess(const Instruction *I) const
Given a memory Mod/Ref'ing instruction, get the MemorySSA access associated with it.
bool isLiveOnEntryDef(const MemoryAccess *MA) const
Return true if MA represents the live on entry value.
MemoryAccess * getDefiningAccess() const
Get the access that produces the memory state used by this Use.
Instruction * getMemoryInst() const
Get the instruction that this MemoryUse represents.
const DataLayout & getDataLayout() const
Get the data layout for the module's target platform.
PHITransAddr - An address value which tracks and handles phi translation.
Value * translateValue(BasicBlock *CurBB, BasicBlock *PredBB, const DominatorTree *DT, bool MustDominate)
translateValue - PHI translate the current address up the CFG from CurBB to Pred, updating our state ...
bool isPotentiallyPHITranslatable() const
isPotentiallyPHITranslatable - If this needs PHI translation, return true if we have some hope of doi...
bool needsPHITranslationFromBlock(BasicBlock *BB) const
needsPHITranslationFromBlock - Return true if moving from the specified BasicBlock to its predecessor...
static PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
Analysis pass which computes a PostDominatorTree.
PostDominatorTree Class - Concrete subclass of DominatorTree that is used to compute the post-dominat...
bool dominates(const Instruction *I1, const Instruction *I2) const
Return true if I1 dominates I2.
A set of analyses that are preserved following a run of a transformation pass.
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
void preserveSet()
Mark an analysis set as preserved.
void preserve()
Mark an analysis as preserved.
A vector that has set insertion semantics.
size_type size() const
Determine the number of elements in the SetVector.
bool insert(const value_type &X)
Insert a new element into the SetVector.
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
bool contains(ConstPtrType Ptr) const
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
A SetVector that performs no allocations if smaller than a certain size.
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
An instruction for storing to memory.
Value * getValueOperand()
Analysis pass providing the TargetLibraryInfo.
Provides information about what library functions are available for the current target.
bool has(LibFunc F) const
Tests whether a library function is available.
bool getLibFunc(StringRef funcName, LibFunc &F) const
Searches for a particular function name.
static constexpr TypeSize getFixed(ScalarTy ExactSize)
The instances of the Type class are immutable: once they are created, they are never changed.
static IntegerType * getInt8Ty(LLVMContext &C)
bool isVoidTy() const
Return true if this is 'void'.
A Use represents the edge between a Value definition and its users.
LLVM Value Representation.
Type * getType() const
All values are typed, get the type of this value.
const Value * stripPointerCasts() const
Strip off pointer casts, all-zero GEPs and address space casts.
LLVMContext & getContext() const
All values hold a context through their type.
iterator_range< use_iterator > uses()
constexpr bool isScalable() const
Returns whether the quantity is scaled by a runtime quantity (vscale).
self_iterator getIterator()
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
bool match(Val *V, const Pattern &P)
bind_ty< Instruction > m_Instruction(Instruction *&I)
Match an instruction, capturing it if we match.
specificval_ty m_Specific(const Value *V)
Match if we have a specific specified value.
class_match< ConstantInt > m_ConstantInt()
Match an arbitrary ConstantInt and ignore it.
match_combine_and< LTy, RTy > m_CombineAnd(const LTy &L, const RTy &R)
Combine two pattern matchers matching L && R.
CmpClass_match< LHS, RHS, ICmpInst, ICmpInst::Predicate > m_ICmp(ICmpInst::Predicate &Pred, const LHS &L, const RHS &R)
OneOps_match< OpTy, Instruction::Load > m_Load(const OpTy &Op)
Matches LoadInst.
brc_match< Cond_t, bind_ty< BasicBlock >, bind_ty< BasicBlock > > m_Br(const Cond_t &C, BasicBlock *&T, BasicBlock *&F)
CmpClass_match< LHS, RHS, ICmpInst, ICmpInst::Predicate, true > m_c_ICmp(ICmpInst::Predicate &Pred, const LHS &L, const RHS &R)
Matches an ICmp with a predicate over LHS and RHS in either order.
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
is_zero m_Zero()
Match any null constant or a vector with all elements equal to 0.
AssignmentMarkerRange getAssignmentMarkers(DIAssignID *ID)
Return a range of dbg.assign intrinsics which use \ID as an operand.
SmallVector< DPValue * > getDPVAssignmentMarkers(const Instruction *Inst)
bool calculateFragmentIntersect(const DataLayout &DL, const Value *Dest, uint64_t SliceOffsetInBits, uint64_t SliceSizeInBits, const DbgAssignIntrinsic *DbgAssign, std::optional< DIExpression::FragmentInfo > &Result)
Calculate the fragment of the variable in DAI covered from (Dest + SliceOffsetInBits) to to (Dest + S...
initializer< Ty > init(const Ty &Val)
NodeAddr< DefNode * > Def
NodeAddr< FuncNode * > Func
This is an optimization pass for GlobalISel generic memory operations.
auto drop_begin(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the first N elements excluded.
UnaryFunction for_each(R &&Range, UnaryFunction F)
Provide wrappers to std::for_each which take ranges instead of having to pass begin/end explicitly.
Constant * getInitialValueOfAllocation(const Value *V, const TargetLibraryInfo *TLI, Type *Ty)
If this is a call to an allocation function that initializes memory to a fixed value,...
bool isStrongerThanMonotonic(AtomicOrdering AO)
bool isAligned(Align Lhs, uint64_t SizeInBytes)
Checks that SizeInBytes is a multiple of the alignment.
void salvageDebugInfo(const MachineRegisterInfo &MRI, MachineInstr &MI)
Assuming the instruction MI is going to be deleted, attempt to salvage debug users of MI by writing t...
Value * emitCalloc(Value *Num, Value *Size, IRBuilderBase &B, const TargetLibraryInfo &TLI)
Emit a call to the calloc function.
Value * GetPointerBaseWithConstantOffset(Value *Ptr, int64_t &Offset, const DataLayout &DL, bool AllowNonInbounds=true)
Analyze the specified pointer to see if it can be expressed as a base pointer plus a constant offset.
const Value * getUnderlyingObject(const Value *V, unsigned MaxLookup=6)
This method strips off any GEP address adjustments and pointer casts from the specified value,...
iterator_range< po_iterator< T > > post_order(const T &G)
bool isNoAliasCall(const Value *V)
Return true if this pointer is returned by a noalias function.
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
bool isInstructionTriviallyDead(Instruction *I, const TargetLibraryInfo *TLI=nullptr)
Return true if the result produced by the instruction is not used, and the instruction will return.
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.
auto reverse(ContainerTy &&C)
bool isModSet(const ModRefInfo MRI)
bool PointerMayBeCaptured(const Value *V, bool ReturnCaptures, bool StoreCaptures, unsigned MaxUsesToExplore=0)
PointerMayBeCaptured - Return true if this pointer value may be captured by the enclosing function (w...
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.
bool AreStatisticsEnabled()
Check if statistics are enabled.
bool isNotVisibleOnUnwind(const Value *Object, bool &RequiresNoCaptureBeforeUnwind)
Return true if Object memory is not visible after an unwind, in the sense that program semantics cann...
uint64_t offsetToAlignment(uint64_t Value, Align Alignment)
Returns the offset to the next integer (mod 2**64) that is greater than or equal to Value and is a mu...
bool salvageKnowledge(Instruction *I, AssumptionCache *AC=nullptr, DominatorTree *DT=nullptr)
Calls BuildAssumeFromInst and if the resulting llvm.assume is valid insert if before I.
Value * getFreedOperand(const CallBase *CB, const TargetLibraryInfo *TLI)
If this if a call to a free function, return the freed operand.
Value * isBytewiseValue(Value *V, const DataLayout &DL)
If the specified value can be set by repeating the same byte in memory, return the i8 value that it i...
auto predecessors(const MachineBasicBlock *BB)
bool mayContainIrreducibleControl(const Function &F, const LoopInfo *LI)
bool isIdentifiedObject(const Value *V)
Return true if this pointer refers to a distinct and identifiable object.
bool isStrongerThan(AtomicOrdering AO, AtomicOrdering Other)
Returns true if ao is stronger than other as defined by the AtomicOrdering lattice,...
bool isRefSet(const ModRefInfo MRI)
This struct is a compact representation of a valid (non-zero power of two) alignment.
uint64_t value() const
This is a hole in the type system and should not be abused.
Holds the characteristics of one fragment of a larger variable.
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.