90using namespace PatternMatch;
92#define DEBUG_TYPE "dse"
94STATISTIC(NumRemainingStores,
"Number of stores remaining after DSE");
95STATISTIC(NumRedundantStores,
"Number of redundant stores deleted");
96STATISTIC(NumFastStores,
"Number of stores deleted");
97STATISTIC(NumFastOther,
"Number of other instrs removed");
98STATISTIC(NumCompletePartials,
"Number of stores dead by later partials");
99STATISTIC(NumModifiedStores,
"Number of stores modified");
104 "Number of times a valid candidate is returned from getDomMemoryDef");
106 "Number iterations check for reads in getDomMemoryDef");
109 "Controls which MemoryDefs are eliminated.");
114 cl::desc(
"Enable partial-overwrite tracking in DSE"));
119 cl::desc(
"Enable partial store merging in DSE"));
123 cl::desc(
"The number of memory instructions to scan for "
124 "dead store elimination (default = 150)"));
127 cl::desc(
"The maximum number of steps while walking upwards to find "
128 "MemoryDefs that may be killed (default = 90)"));
132 cl::desc(
"The maximum number candidates that only partially overwrite the "
133 "killing MemoryDef to consider"
138 cl::desc(
"The number of MemoryDefs we consider as candidates to eliminated "
139 "other stores per basic block (default = 5000)"));
144 "The cost of a step in the same basic block as the killing MemoryDef"
150 cl::desc(
"The cost of a step in a different basic "
151 "block than the killing MemoryDef"
156 cl::desc(
"The maximum number of blocks to check when trying to prove that "
157 "all paths to an exit go through a killing block (default = 50)"));
167 cl::desc(
"Allow DSE to optimize memory accesses."));
179 if (isa<StoreInst>(
I))
183 switch (II->getIntrinsicID()) {
184 default:
return false;
185 case Intrinsic::memset:
186 case Intrinsic::memcpy:
187 case Intrinsic::memcpy_element_unordered_atomic:
188 case Intrinsic::memset_element_unordered_atomic:
205 return isa<AnyMemSetInst>(
I);
222enum OverwriteResult {
226 OW_PartialEarlierWithFullLater,
240 const auto *KillingII = dyn_cast<IntrinsicInst>(KillingI);
241 const auto *DeadII = dyn_cast<IntrinsicInst>(DeadI);
242 if (KillingII ==
nullptr || DeadII ==
nullptr)
244 if (KillingII->getIntrinsicID() != DeadII->getIntrinsicID())
246 if (KillingII->getIntrinsicID() == Intrinsic::masked_store) {
249 cast<VectorType>(KillingII->getArgOperand(0)->getType());
250 VectorType *DeadTy = cast<VectorType>(DeadII->getArgOperand(0)->getType());
251 if (KillingTy->getScalarSizeInBits() != DeadTy->getScalarSizeInBits())
254 if (KillingTy->getElementCount() != DeadTy->getElementCount())
259 if (KillingPtr != DeadPtr && !AA.
isMustAlias(KillingPtr, DeadPtr))
263 if (KillingII->getArgOperand(3) != DeadII->getArgOperand(3))
282 int64_t KillingOff, int64_t DeadOff,
293 KillingOff < int64_t(DeadOff + DeadSize) &&
294 int64_t(KillingOff + KillingSize) >= DeadOff) {
297 auto &IM = IOL[DeadI];
298 LLVM_DEBUG(
dbgs() <<
"DSE: Partial overwrite: DeadLoc [" << DeadOff <<
", "
299 << int64_t(DeadOff + DeadSize) <<
") KillingLoc ["
300 << KillingOff <<
", " << int64_t(KillingOff + KillingSize)
307 int64_t KillingIntStart = KillingOff;
308 int64_t KillingIntEnd = KillingOff + KillingSize;
312 auto ILI = IM.lower_bound(KillingIntStart);
313 if (ILI != IM.end() && ILI->second <= KillingIntEnd) {
317 KillingIntStart = std::min(KillingIntStart, ILI->second);
318 KillingIntEnd = std::max(KillingIntEnd, ILI->first);
327 while (ILI != IM.end() && ILI->second <= KillingIntEnd) {
328 assert(ILI->second > KillingIntStart &&
"Unexpected interval");
329 KillingIntEnd = std::max(KillingIntEnd, ILI->first);
334 IM[KillingIntEnd] = KillingIntStart;
337 if (ILI->second <= DeadOff && ILI->first >= int64_t(DeadOff + DeadSize)) {
338 LLVM_DEBUG(
dbgs() <<
"DSE: Full overwrite from partials: DeadLoc ["
339 << DeadOff <<
", " << int64_t(DeadOff + DeadSize)
340 <<
") Composite KillingLoc [" << ILI->second <<
", "
341 << ILI->first <<
")\n");
342 ++NumCompletePartials;
350 int64_t(DeadOff + DeadSize) > KillingOff &&
351 uint64_t(KillingOff - DeadOff) + KillingSize <= DeadSize) {
352 LLVM_DEBUG(
dbgs() <<
"DSE: Partial overwrite a dead load [" << DeadOff
353 <<
", " << int64_t(DeadOff + DeadSize)
354 <<
") by a killing store [" << KillingOff <<
", "
355 << int64_t(KillingOff + KillingSize) <<
")\n");
357 return OW_PartialEarlierWithFullLater;
370 (KillingOff > DeadOff && KillingOff < int64_t(DeadOff + DeadSize) &&
371 int64_t(KillingOff + KillingSize) >= int64_t(DeadOff + DeadSize)))
384 (KillingOff <= DeadOff && int64_t(KillingOff + KillingSize) > DeadOff)) {
385 assert(int64_t(KillingOff + KillingSize) < int64_t(DeadOff + DeadSize) &&
386 "Expect to be handled as OW_Complete");
406 using BlockAddressPair = std::pair<BasicBlock *, PHITransAddr>;
418 if (
auto *MemSet = dyn_cast<MemSetInst>(SecondI))
423 auto *MemLocPtr =
const_cast<Value *
>(MemLoc.
Ptr);
428 bool isFirstBlock =
true;
431 while (!WorkList.
empty()) {
443 assert(
B == SecondBB &&
"first block is not the store block");
445 isFirstBlock =
false;
451 for (; BI != EI; ++BI) {
453 if (
I->mayWriteToMemory() &&
I != SecondI)
459 "Should not hit the entry block because SI must be dominated by LI");
469 auto Inserted = Visited.
insert(std::make_pair(Pred, TranslatedPtr));
470 if (!Inserted.second) {
473 if (TranslatedPtr != Inserted.first->second)
478 WorkList.
push_back(std::make_pair(Pred, PredAddr));
487 uint64_t NewSizeInBits,
bool IsOverwriteEnd) {
489 uint64_t DeadSliceSizeInBits = OldSizeInBits - NewSizeInBits;
491 OldOffsetInBits + (IsOverwriteEnd ? NewSizeInBits : 0);
496 uint64_t RelativeOffset = DeadFragment.OffsetInBits -
502 DAI->
getExpression(), RelativeOffset, DeadFragment.SizeInBits)) {
509 DIExpression::get(DAI->
getContext(), std::nullopt),
510 DeadFragment.OffsetInBits, DeadFragment.SizeInBits);
519 auto GetDeadLink = [&Ctx, &LinkToNothing]() {
522 return LinkToNothing;
532 for (
auto *DAI : Linked) {
533 std::optional<DIExpression::FragmentInfo> NewFragment;
535 DeadSliceSizeInBits, DAI,
545 if (NewFragment->SizeInBits == 0)
549 auto *NewAssign = cast<DbgAssignIntrinsic>(DAI->
clone());
550 NewAssign->insertAfter(DAI);
551 NewAssign->setAssignId(GetDeadLink());
553 SetDeadFragExpr(NewAssign, *NewFragment);
554 NewAssign->setKillAddress();
559 uint64_t &DeadSize, int64_t KillingStart,
560 uint64_t KillingSize,
bool IsOverwriteEnd) {
561 auto *DeadIntrinsic = cast<AnyMemIntrinsic>(DeadI);
562 Align PrefAlign = DeadIntrinsic->getDestAlign().valueOrOne();
578 int64_t ToRemoveStart = 0;
582 if (IsOverwriteEnd) {
587 ToRemoveStart = KillingStart + Off;
588 if (DeadSize <=
uint64_t(ToRemoveStart - DeadStart))
590 ToRemoveSize = DeadSize -
uint64_t(ToRemoveStart - DeadStart);
592 ToRemoveStart = DeadStart;
594 "Not overlapping accesses?");
595 ToRemoveSize = KillingSize -
uint64_t(DeadStart - KillingStart);
600 if (ToRemoveSize <= (PrefAlign.
value() - Off))
602 ToRemoveSize -= PrefAlign.
value() - Off;
605 "Should preserve selected alignment");
608 assert(ToRemoveSize > 0 &&
"Shouldn't reach here if nothing to remove");
609 assert(DeadSize > ToRemoveSize &&
"Can't remove more than original size");
611 uint64_t NewSize = DeadSize - ToRemoveSize;
612 if (
auto *AMI = dyn_cast<AtomicMemIntrinsic>(DeadI)) {
615 const uint32_t ElementSize = AMI->getElementSizeInBytes();
616 if (0 != NewSize % ElementSize)
621 << (IsOverwriteEnd ?
"END" :
"BEGIN") <<
": " << *DeadI
622 <<
"\n KILLER [" << ToRemoveStart <<
", "
623 << int64_t(ToRemoveStart + ToRemoveSize) <<
")\n");
625 Value *DeadWriteLength = DeadIntrinsic->getLength();
627 DeadIntrinsic->setLength(TrimmedLength);
628 DeadIntrinsic->setDestAlignment(PrefAlign);
630 Value *OrigDest = DeadIntrinsic->getRawDest();
631 if (!IsOverwriteEnd) {
635 Value *Dest = OrigDest;
636 if (OrigDest->
getType() != Int8PtrTy)
638 Value *Indices[1] = {
641 Type::getInt8Ty(DeadIntrinsic->getContext()), Dest, Indices,
"", DeadI);
642 NewDestGEP->
setDebugLoc(DeadIntrinsic->getDebugLoc());
646 DeadIntrinsic->setDest(NewDestGEP);
655 DeadStart += ToRemoveSize;
662 int64_t &DeadStart,
uint64_t &DeadSize) {
667 int64_t KillingStart = OII->second;
668 uint64_t KillingSize = OII->first - KillingStart;
670 assert(OII->first - KillingStart >= 0 &&
"Size expected to be positive");
672 if (KillingStart > DeadStart &&
675 (
uint64_t)(KillingStart - DeadStart) < DeadSize &&
678 KillingSize >= DeadSize - (
uint64_t)(KillingStart - DeadStart)) {
679 if (
tryToShorten(DeadI, DeadStart, DeadSize, KillingStart, KillingSize,
690 int64_t &DeadStart,
uint64_t &DeadSize) {
695 int64_t KillingStart = OII->second;
696 uint64_t KillingSize = OII->first - KillingStart;
698 assert(OII->first - KillingStart >= 0 &&
"Size expected to be positive");
700 if (KillingStart <= DeadStart &&
703 KillingSize > (
uint64_t)(DeadStart - KillingStart)) {
706 assert(KillingSize - (
uint64_t)(DeadStart - KillingStart) < DeadSize &&
707 "Should have been handled as OW_Complete");
708 if (
tryToShorten(DeadI, DeadStart, DeadSize, KillingStart, KillingSize,
719 int64_t KillingOffset, int64_t DeadOffset,
746 unsigned BitOffsetDiff = (KillingOffset - DeadOffset) * 8;
747 unsigned LShiftAmount =
748 DL.isBigEndian() ? DeadValue.
getBitWidth() - BitOffsetDiff - KillingBits
751 LShiftAmount + KillingBits);
754 APInt Merged = (DeadValue & ~Mask) | (KillingValue << LShiftAmount);
756 <<
"\n Killing: " << *KillingI
757 <<
"\n Merged Value: " << Merged <<
'\n');
767 switch (II->getIntrinsicID()) {
768 case Intrinsic::lifetime_start:
769 case Intrinsic::lifetime_end:
770 case Intrinsic::invariant_end:
771 case Intrinsic::launder_invariant_group:
772 case Intrinsic::assume:
774 case Intrinsic::dbg_declare:
775 case Intrinsic::dbg_label:
776 case Intrinsic::dbg_value:
786bool canSkipDef(
MemoryDef *
D,
bool DefVisibleToCaller) {
790 if (
auto *CB = dyn_cast<CallBase>(DI))
791 if (CB->onlyAccessesInaccessibleMemory())
796 if (DI->
mayThrow() && !DefVisibleToCaller)
804 if (isa<FenceInst>(DI))
808 if (isNoopIntrinsic(DI))
837 bool ContainsIrreducibleLoops;
863 bool AnyUnreachableExit;
868 bool ShouldIterateEndOfFunctionDSE;
871 DSEState(
const DSEState &) =
delete;
872 DSEState &operator=(
const DSEState &) =
delete;
877 :
F(
F), AA(AA), EI(DT, LI, EphValues), BatchAA(AA, &EI), MSSA(MSSA),
878 DT(DT), PDT(PDT), TLI(TLI),
DL(
F.
getParent()->getDataLayout()), LI(LI) {
883 PostOrderNumbers[BB] = PO++;
886 if (
I.mayThrow() && !MA)
887 ThrowingBlocks.
insert(
I.getParent());
889 auto *MD = dyn_cast_or_null<MemoryDef>(MA);
891 (getLocForWrite(&
I) || isMemTerminatorInst(&
I)))
899 if (AI.hasPassPointeeByValueCopyAttr())
900 InvisibleToCallerAfterRet.
insert({&AI,
true});
906 return isa<UnreachableInst>(E->getTerminator());
914 if (
auto *CB = dyn_cast<CallBase>(
I)) {
917 (F == LibFunc_memset_chk || F == LibFunc_memcpy_chk)) {
926 if (
const auto *Len = dyn_cast<ConstantInt>(CB->getArgOperand(2)))
941 OverwriteResult isOverwrite(
const Instruction *KillingI,
945 int64_t &KillingOff, int64_t &DeadOff) {
949 if (!isGuaranteedLoopIndependent(DeadI, KillingI, DeadLoc))
953 strengthenLocationSize(KillingI, KillingLoc.
Size);
961 if (DeadUndObj == KillingUndObj && KillingLocSize.
isPrecise()) {
964 KillingUndObjSize == KillingLocSize.
getValue())
973 const auto *KillingMemI = dyn_cast<MemIntrinsic>(KillingI);
974 const auto *DeadMemI = dyn_cast<MemIntrinsic>(DeadI);
975 if (KillingMemI && DeadMemI) {
976 const Value *KillingV = KillingMemI->getLength();
977 const Value *DeadV = DeadMemI->getLength();
978 if (KillingV == DeadV && BatchAA.
isMustAlias(DeadLoc, KillingLoc))
997 if (KillingSize >= DeadSize)
1004 if (Off >= 0 && (
uint64_t)Off + DeadSize <= KillingSize)
1010 if (DeadUndObj != KillingUndObj) {
1026 const Value *DeadBasePtr =
1028 const Value *KillingBasePtr =
1033 if (DeadBasePtr != KillingBasePtr)
1051 if (DeadOff >= KillingOff) {
1054 if (
uint64_t(DeadOff - KillingOff) + DeadSize <= KillingSize)
1058 else if ((
uint64_t)(DeadOff - KillingOff) < KillingSize)
1059 return OW_MaybePartial;
1063 else if ((
uint64_t)(KillingOff - DeadOff) < DeadSize) {
1064 return OW_MaybePartial;
1071 bool isInvisibleToCallerAfterRet(
const Value *V) {
1072 if (isa<AllocaInst>(V))
1074 auto I = InvisibleToCallerAfterRet.
insert({
V,
false});
1076 if (!isInvisibleToCallerOnUnwind(V)) {
1077 I.first->second =
false;
1082 return I.first->second;
1085 bool isInvisibleToCallerOnUnwind(
const Value *V) {
1086 bool RequiresNoCaptureBeforeUnwind;
1089 if (!RequiresNoCaptureBeforeUnwind)
1092 auto I = CapturedBeforeReturn.
insert({
V,
true});
1099 return !
I.first->second;
1102 std::optional<MemoryLocation> getLocForWrite(
Instruction *
I)
const {
1103 if (!
I->mayWriteToMemory())
1104 return std::nullopt;
1106 if (
auto *CB = dyn_cast<CallBase>(
I))
1115 assert(getLocForWrite(
I) &&
"Must have analyzable write");
1119 return SI->isUnordered();
1121 if (
auto *CB = dyn_cast<CallBase>(
I)) {
1123 if (
auto *
MI = dyn_cast<MemIntrinsic>(CB))
1124 return !
MI->isVolatile();
1128 if (CB->isLifetimeStartOrEnd())
1131 return CB->use_empty() && CB->willReturn() && CB->doesNotThrow() &&
1132 !CB->isTerminator();
1148 if (
auto *CB = dyn_cast<CallBase>(UseInst))
1149 if (CB->onlyAccessesInaccessibleMemory())
1152 int64_t InstWriteOffset, DepWriteOffset;
1153 if (
auto CC = getLocForWrite(UseInst))
1154 return isOverwrite(UseInst, DefInst, *
CC, DefLoc, InstWriteOffset,
1155 DepWriteOffset) == OW_Complete;
1160 bool isWriteAtEndOfFunction(
MemoryDef *Def) {
1162 << *
Def->getMemoryInst()
1163 <<
") is at the end the function \n");
1165 auto MaybeLoc = getLocForWrite(
Def->getMemoryInst());
1167 LLVM_DEBUG(
dbgs() <<
" ... could not get location for write.\n");
1173 auto PushMemUses = [&WorkList, &Visited](
MemoryAccess *Acc) {
1174 if (!Visited.
insert(Acc).second)
1177 WorkList.
push_back(cast<MemoryAccess>(
U.getUser()));
1180 for (
unsigned I = 0;
I < WorkList.
size();
I++) {
1187 if (isa<MemoryPhi>(UseAccess)) {
1191 if (!isGuaranteedLoopInvariant(MaybeLoc->Ptr))
1194 PushMemUses(cast<MemoryPhi>(UseAccess));
1199 Instruction *UseInst = cast<MemoryUseOrDef>(UseAccess)->getMemoryInst();
1200 if (isReadClobber(*MaybeLoc, UseInst)) {
1201 LLVM_DEBUG(
dbgs() <<
" ... hit read clobber " << *UseInst <<
".\n");
1205 if (
MemoryDef *UseDef = dyn_cast<MemoryDef>(UseAccess))
1206 PushMemUses(UseDef);
1214 std::optional<std::pair<MemoryLocation, bool>>
1222 if (
auto *CB = dyn_cast<CallBase>(
I)) {
1227 return std::nullopt;
1233 auto *CB = dyn_cast<CallBase>(
I);
1234 return CB && (CB->getIntrinsicID() == Intrinsic::lifetime_end ||
1242 std::optional<std::pair<MemoryLocation, bool>> MaybeTermLoc =
1243 getLocForTerminator(MaybeTerm);
1254 auto TermLoc = MaybeTermLoc->first;
1255 if (MaybeTermLoc->second) {
1259 int64_t InstWriteOffset = 0;
1260 int64_t DepWriteOffset = 0;
1261 return isOverwrite(MaybeTerm, AccessI, TermLoc, Loc, InstWriteOffset,
1262 DepWriteOffset) == OW_Complete;
1267 if (isNoopIntrinsic(UseInst))
1272 if (
auto SI = dyn_cast<StoreInst>(UseInst))
1278 if (
auto *CB = dyn_cast<CallBase>(UseInst))
1279 if (CB->onlyAccessesInaccessibleMemory())
1290 bool isGuaranteedLoopIndependent(
const Instruction *Current,
1300 if (!ContainsIrreducibleLoops && CurrentLI &&
1304 return isGuaranteedLoopInvariant(CurrentLoc.
Ptr);
1310 bool isGuaranteedLoopInvariant(
const Value *
Ptr) {
1311 Ptr =
Ptr->stripPointerCasts();
1312 if (
auto *
GEP = dyn_cast<GEPOperator>(
Ptr))
1313 if (
GEP->hasAllConstantIndices())
1314 Ptr =
GEP->getPointerOperand()->stripPointerCasts();
1316 if (
auto *
I = dyn_cast<Instruction>(
Ptr)) {
1317 return I->getParent()->isEntryBlock() ||
1318 (!ContainsIrreducibleLoops && !LI.
getLoopFor(
I->getParent()));
1329 std::optional<MemoryAccess *>
1332 unsigned &ScanLimit,
unsigned &WalkerStepLimit,
1333 bool IsMemTerm,
unsigned &PartialLimit) {
1334 if (ScanLimit == 0 || WalkerStepLimit == 0) {
1336 return std::nullopt;
1353 std::optional<MemoryLocation> CurrentLoc;
1354 for (;; Current = cast<MemoryDef>(Current)->getDefiningAccess()) {
1356 dbgs() <<
" visiting " << *Current;
1358 dbgs() <<
" (" << *cast<MemoryUseOrDef>(Current)->getMemoryInst()
1369 return std::nullopt;
1377 if (WalkerStepLimit <= StepCost) {
1379 return std::nullopt;
1381 WalkerStepLimit -= StepCost;
1385 if (isa<MemoryPhi>(Current)) {
1392 MemoryDef *CurrentDef = cast<MemoryDef>(Current);
1395 if (canSkipDef(CurrentDef, !isInvisibleToCallerOnUnwind(KillingUndObj))) {
1396 CanOptimize =
false;
1402 if (mayThrowBetween(KillingI, CurrentI, KillingUndObj)) {
1404 return std::nullopt;
1409 if (isDSEBarrier(KillingUndObj, CurrentI)) {
1411 return std::nullopt;
1418 if (!isa<IntrinsicInst>(CurrentI) && isReadClobber(KillingLoc, CurrentI))
1419 return std::nullopt;
1422 if (
any_of(Current->
uses(), [
this, &KillingLoc, StartAccess](
Use &U) {
1423 if (auto *UseOrDef = dyn_cast<MemoryUseOrDef>(U.getUser()))
1424 return !MSSA.dominates(StartAccess, UseOrDef) &&
1425 isReadClobber(KillingLoc, UseOrDef->getMemoryInst());
1429 return std::nullopt;
1434 CurrentLoc = getLocForWrite(CurrentI);
1435 if (!CurrentLoc || !isRemovable(CurrentI)) {
1436 CanOptimize =
false;
1443 if (!isGuaranteedLoopIndependent(CurrentI, KillingI, *CurrentLoc)) {
1445 CanOptimize =
false;
1453 if (!isMemTerminator(*CurrentLoc, CurrentI, KillingI)) {
1454 CanOptimize =
false;
1458 int64_t KillingOffset = 0;
1459 int64_t DeadOffset = 0;
1460 auto OR = isOverwrite(KillingI, CurrentI, KillingLoc, *CurrentLoc,
1461 KillingOffset, DeadOffset);
1467 (OR == OW_Complete || OR == OW_MaybePartial))
1473 CanOptimize =
false;
1478 if (OR == OW_Unknown || OR == OW_None)
1480 else if (OR == OW_MaybePartial) {
1485 if (PartialLimit <= 1) {
1486 WalkerStepLimit -= 1;
1487 LLVM_DEBUG(
dbgs() <<
" ... reached partial limit ... continue with next access\n");
1504 Instruction *MaybeDeadI = cast<MemoryDef>(MaybeDeadAccess)->getMemoryInst();
1505 LLVM_DEBUG(
dbgs() <<
" Checking for reads of " << *MaybeDeadAccess <<
" ("
1506 << *MaybeDeadI <<
")\n");
1511 WorkList.
insert(cast<MemoryAccess>(
U.getUser()));
1513 PushMemUses(MaybeDeadAccess);
1516 for (
unsigned I = 0;
I < WorkList.
size();
I++) {
1521 if (ScanLimit < (WorkList.
size() -
I)) {
1523 return std::nullopt;
1526 NumDomMemDefChecks++;
1528 if (isa<MemoryPhi>(UseAccess)) {
1533 LLVM_DEBUG(
dbgs() <<
" ... skipping, dominated by killing block\n");
1537 PushMemUses(UseAccess);
1541 Instruction *UseInst = cast<MemoryUseOrDef>(UseAccess)->getMemoryInst();
1547 LLVM_DEBUG(
dbgs() <<
" ... skipping, dominated by killing def\n");
1553 if (isMemTerminator(MaybeDeadLoc, MaybeDeadI, UseInst)) {
1556 <<
" ... skipping, memterminator invalidates following accesses\n");
1560 if (isNoopIntrinsic(cast<MemoryUseOrDef>(UseAccess)->getMemoryInst())) {
1562 PushMemUses(UseAccess);
1566 if (UseInst->
mayThrow() && !isInvisibleToCallerOnUnwind(KillingUndObj)) {
1568 return std::nullopt;
1573 if (isReadClobber(MaybeDeadLoc, UseInst)) {
1575 return std::nullopt;
1581 if (MaybeDeadAccess == UseAccess &&
1582 !isGuaranteedLoopInvariant(MaybeDeadLoc.
Ptr)) {
1583 LLVM_DEBUG(
dbgs() <<
" ... found not loop invariant self access\n");
1584 return std::nullopt;
1590 if (KillingDef == UseAccess || MaybeDeadAccess == UseAccess) {
1605 if (
MemoryDef *UseDef = dyn_cast<MemoryDef>(UseAccess)) {
1606 if (isCompleteOverwrite(MaybeDeadLoc, MaybeDeadI, UseInst)) {
1608 if (PostOrderNumbers.
find(MaybeKillingBlock)->second <
1609 PostOrderNumbers.
find(MaybeDeadAccess->
getBlock())->second) {
1610 if (!isInvisibleToCallerAfterRet(KillingUndObj)) {
1612 <<
" ... found killing def " << *UseInst <<
"\n");
1613 KillingDefs.
insert(UseInst);
1617 <<
" ... found preceeding def " << *UseInst <<
"\n");
1618 return std::nullopt;
1621 PushMemUses(UseDef);
1628 if (!isInvisibleToCallerAfterRet(KillingUndObj)) {
1631 KillingBlocks.
insert(KD->getParent());
1633 "Expected at least a single killing block");
1647 if (!AnyUnreachableExit)
1648 return std::nullopt;
1652 CommonPred =
nullptr;
1656 if (KillingBlocks.
count(CommonPred))
1657 return {MaybeDeadAccess};
1663 WorkList.
insert(CommonPred);
1666 if (!isa<UnreachableInst>(
R->getTerminator()))
1673 for (
unsigned I = 0;
I < WorkList.
size();
I++) {
1676 if (KillingBlocks.
count(Current))
1678 if (Current == MaybeDeadAccess->
getBlock())
1679 return std::nullopt;
1690 return std::nullopt;
1697 return {MaybeDeadAccess};
1707 while (!NowDeadInsts.
empty()) {
1717 if (
MemoryDef *MD = dyn_cast<MemoryDef>(MA)) {
1719 if (
auto *SI = dyn_cast<StoreInst>(MD->getMemoryInst())) {
1720 if (
SI->getValueOperand()->getType()->isPointerTy()) {
1722 if (CapturedBeforeReturn.
erase(UO))
1723 ShouldIterateEndOfFunctionDSE =
true;
1724 InvisibleToCallerAfterRet.
erase(UO);
1729 Updater.removeMemoryAccess(MA);
1733 if (
I != IOLs.
end())
1734 I->second.erase(DeadInst);
1737 if (
Instruction *OpI = dyn_cast<Instruction>(O)) {
1753 const Value *KillingUndObj) {
1757 if (KillingUndObj && isInvisibleToCallerOnUnwind(KillingUndObj))
1762 return !ThrowingBlocks.
empty();
1773 if (DeadI->
mayThrow() && !isInvisibleToCallerOnUnwind(KillingUndObj))
1779 if (
auto *LI = dyn_cast<LoadInst>(DeadI))
1781 if (
auto *SI = dyn_cast<StoreInst>(DeadI))
1783 if (
auto *ARMW = dyn_cast<AtomicRMWInst>(DeadI))
1785 if (
auto *CmpXchg = dyn_cast<AtomicCmpXchgInst>(DeadI))
1795 bool eliminateDeadWritesAtEndOfFunction() {
1796 bool MadeChange =
false;
1799 <<
"Trying to eliminate MemoryDefs at the end of the function\n");
1801 ShouldIterateEndOfFunctionDSE =
false;
1807 auto DefLoc = getLocForWrite(DefI);
1808 if (!DefLoc || !isRemovable(DefI))
1817 if (!isInvisibleToCallerAfterRet(UO))
1820 if (isWriteAtEndOfFunction(Def)) {
1822 LLVM_DEBUG(
dbgs() <<
" ... MemoryDef is not accessed until the end "
1823 "of the function\n");
1829 }
while (ShouldIterateEndOfFunctionDSE);
1837 MemSetInst *MemSet = dyn_cast<MemSetInst>(DefI);
1842 if (!StoredConstant || !StoredConstant->
isNullValue())
1845 if (!isRemovable(DefI))
1849 if (
F.hasFnAttribute(Attribute::SanitizeMemory) ||
1850 F.hasFnAttribute(Attribute::SanitizeAddress) ||
1851 F.hasFnAttribute(Attribute::SanitizeHWAddress) ||
1852 F.getName() ==
"calloc")
1854 auto *
Malloc =
const_cast<CallInst *
>(dyn_cast<CallInst>(DefUO));
1857 auto *InnerCallee =
Malloc->getCalledFunction();
1861 if (!TLI.
getLibFunc(*InnerCallee, Func) || !TLI.
has(Func) ||
1862 Func != LibFunc_malloc)
1868 auto *MallocBB =
Malloc->getParent(),
1869 *MemsetBB = Memset->getParent();
1870 if (MallocBB == MemsetBB)
1872 auto *
Ptr = Memset->getArgOperand(0);
1873 auto *TI = MallocBB->getTerminator();
1879 if (Pred != ICmpInst::ICMP_EQ || MemsetBB != FalseBB)
1886 if (!shouldCreateCalloc(
Malloc, MemSet) ||
1891 Type *SizeTTy =
Malloc->getArgOperand(0)->getType();
1893 Malloc->getArgOperand(0), IRB, TLI);
1898 cast<MemoryDef>(Updater.getMemorySSA()->getMemoryAccess(
Malloc));
1900 Updater.createMemoryAccessAfter(cast<Instruction>(Calloc), LastDef,
1902 auto *NewAccessMD = cast<MemoryDef>(NewAccess);
1903 Updater.insertDef(NewAccessMD,
true);
1904 Updater.removeMemoryAccess(
Malloc);
1905 Malloc->replaceAllUsesWith(Calloc);
1906 Malloc->eraseFromParent();
1915 MemSetInst *MemSet = dyn_cast<MemSetInst>(DefI);
1916 Constant *StoredConstant =
nullptr;
1918 StoredConstant = dyn_cast<Constant>(
Store->getOperand(0));
1920 StoredConstant = dyn_cast<Constant>(MemSet->
getValue());
1924 if (!isRemovable(DefI))
1927 if (StoredConstant) {
1932 if (InitC && InitC == StoredConstant)
1940 if (
auto *LoadI = dyn_cast<LoadInst>(
Store->getOperand(0))) {
1941 if (LoadI->getPointerOperand() ==
Store->getOperand(1)) {
1945 if (LoadAccess ==
Def->getDefiningAccess())
1960 for (
unsigned I = 1;
I < ToCheck.
size(); ++
I) {
1961 Current = ToCheck[
I];
1962 if (
auto PhiAccess = dyn_cast<MemoryPhi>(Current)) {
1964 for (
auto &
Use : PhiAccess->incoming_values())
1965 ToCheck.
insert(cast<MemoryAccess>(&
Use));
1971 assert(isa<MemoryDef>(Current) &&
1972 "Only MemoryDefs should reach here.");
1977 if (LoadAccess != Current)
1988 bool Changed =
false;
1989 for (
auto OI : IOL) {
1992 assert(isRemovable(DeadI) &&
"Expect only removable instruction");
1995 int64_t DeadStart = 0;
2009 bool eliminateRedundantStoresOfExistingValues() {
2010 bool MadeChange =
false;
2011 LLVM_DEBUG(
dbgs() <<
"Trying to eliminate MemoryDefs that write the "
2012 "already existing value\n");
2013 for (
auto *Def : MemDefs) {
2018 auto MaybeDefLoc = getLocForWrite(DefInst);
2019 if (!MaybeDefLoc || !isRemovable(DefInst))
2026 if (
Def->isOptimized())
2027 UpperDef = dyn_cast<MemoryDef>(
Def->getOptimized());
2029 UpperDef = dyn_cast<MemoryDef>(
Def->getDefiningAccess());
2034 auto IsRedundantStore = [&]() {
2037 if (
auto *MemSetI = dyn_cast<MemSetInst>(UpperInst)) {
2038 if (
auto *SI = dyn_cast<StoreInst>(DefInst)) {
2041 int64_t InstWriteOffset = 0;
2042 int64_t DepWriteOffset = 0;
2043 auto OR = isOverwrite(UpperInst, DefInst, UpperLoc, *MaybeDefLoc,
2044 InstWriteOffset, DepWriteOffset);
2046 return StoredByte && StoredByte == MemSetI->getOperand(1) &&
2053 if (!IsRedundantStore() || isReadClobber(*MaybeDefLoc, DefInst))
2055 LLVM_DEBUG(
dbgs() <<
"DSE: Remove No-Op Store:\n DEAD: " << *DefInst
2058 NumRedundantStores++;
2070 bool MadeChange =
false;
2073 DSEState State(
F, AA, MSSA, DT, PDT, AC, TLI, LI);
2075 for (
unsigned I = 0;
I < State.MemDefs.size();
I++) {
2077 if (State.SkipStores.count(KillingDef))
2081 std::optional<MemoryLocation> MaybeKillingLoc;
2082 if (State.isMemTerminatorInst(KillingI)) {
2083 if (
auto KillingLoc = State.getLocForTerminator(KillingI))
2084 MaybeKillingLoc = KillingLoc->first;
2086 MaybeKillingLoc = State.getLocForWrite(KillingI);
2089 if (!MaybeKillingLoc) {
2090 LLVM_DEBUG(
dbgs() <<
"Failed to find analyzable write location for "
2091 << *KillingI <<
"\n");
2095 assert(KillingLoc.
Ptr &&
"KillingLoc should not be null");
2098 << *KillingDef <<
" (" << *KillingI <<
")\n");
2107 bool Shortend =
false;
2108 bool IsMemTerm = State.isMemTerminatorInst(KillingI);
2110 for (
unsigned I = 0;
I < ToCheck.
size();
I++) {
2112 if (State.SkipStores.count(Current))
2115 std::optional<MemoryAccess *> MaybeDeadAccess = State.getDomMemoryDef(
2116 KillingDef, Current, KillingLoc, KillingUndObj, ScanLimit,
2117 WalkerStepLimit, IsMemTerm, PartialLimit);
2119 if (!MaybeDeadAccess) {
2125 LLVM_DEBUG(
dbgs() <<
" Checking if we can kill " << *DeadAccess);
2126 if (isa<MemoryPhi>(DeadAccess)) {
2127 LLVM_DEBUG(
dbgs() <<
"\n ... adding incoming values to worklist\n");
2128 for (
Value *V : cast<MemoryPhi>(DeadAccess)->incoming_values()) {
2136 if (State.PostOrderNumbers[IncomingBlock] >
2137 State.PostOrderNumbers[PhiBlock])
2138 ToCheck.
insert(IncomingAccess);
2142 auto *DeadDefAccess = cast<MemoryDef>(DeadAccess);
2143 Instruction *DeadI = DeadDefAccess->getMemoryInst();
2145 ToCheck.
insert(DeadDefAccess->getDefiningAccess());
2146 NumGetDomMemoryDefPassed++;
2155 if (KillingUndObj != DeadUndObj)
2157 LLVM_DEBUG(
dbgs() <<
"DSE: Remove Dead Store:\n DEAD: " << *DeadI
2158 <<
"\n KILLER: " << *KillingI <<
'\n');
2159 State.deleteDeadInstruction(DeadI);
2164 int64_t KillingOffset = 0;
2165 int64_t DeadOffset = 0;
2166 OverwriteResult
OR = State.isOverwrite(
2167 KillingI, DeadI, KillingLoc, DeadLoc, KillingOffset, DeadOffset);
2168 if (OR == OW_MaybePartial) {
2169 auto Iter = State.IOLs.insert(
2170 std::make_pair<BasicBlock *, InstOverlapIntervalsTy>(
2172 auto &IOL = Iter.first->second;
2174 DeadOffset, DeadI, IOL);
2178 auto *DeadSI = dyn_cast<StoreInst>(DeadI);
2179 auto *KillingSI = dyn_cast<StoreInst>(KillingI);
2183 if (DeadSI && KillingSI && DT.
dominates(DeadSI, KillingSI)) {
2185 KillingSI, DeadSI, KillingOffset, DeadOffset, State.DL,
2186 State.BatchAA, &DT)) {
2189 DeadSI->setOperand(0, Merged);
2190 ++NumModifiedStores;
2196 State.deleteDeadInstruction(KillingSI);
2197 auto I = State.IOLs.find(DeadSI->getParent());
2198 if (
I != State.IOLs.end())
2199 I->second.erase(DeadSI);
2205 if (OR == OW_Complete) {
2206 LLVM_DEBUG(
dbgs() <<
"DSE: Remove Dead Store:\n DEAD: " << *DeadI
2207 <<
"\n KILLER: " << *KillingI <<
'\n');
2208 State.deleteDeadInstruction(DeadI);
2216 if (!Shortend && State.storeIsNoop(KillingDef, KillingUndObj)) {
2217 LLVM_DEBUG(
dbgs() <<
"DSE: Remove No-Op Store:\n DEAD: " << *KillingI
2219 State.deleteDeadInstruction(KillingI);
2220 NumRedundantStores++;
2226 if (!Shortend && State.tryFoldIntoCalloc(KillingDef, KillingUndObj)) {
2227 LLVM_DEBUG(
dbgs() <<
"DSE: Remove memset after forming calloc:\n"
2228 <<
" DEAD: " << *KillingI <<
'\n');
2229 State.deleteDeadInstruction(KillingI);
2236 for (
auto &KV : State.IOLs)
2237 MadeChange |= State.removePartiallyOverlappedStores(KV.second);
2239 MadeChange |= State.eliminateRedundantStoresOfExistingValues();
2240 MadeChange |= State.eliminateDeadWritesAtEndOfFunction();
2257 bool Changed = eliminateDeadStores(
F, AA, MSSA, DT, PDT, AC, TLI, LI);
2259#ifdef LLVM_ENABLE_STATS
2262 NumRemainingStores += isa<StoreInst>(&
I);
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
This file implements a class to represent arbitrary precision integral constant values and operations...
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 uint64_t getPointerSize(const Value *V, const DataLayout &DL, const TargetLibraryInfo &TLI, const Function *F)
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 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.
print must be executed print the must be executed context for all instructions
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.
A function analysis which provides an AssumptionCache.
A cache of @llvm.assume calls within a function.
LLVM Basic Block Representation.
const Function * getParent() const
Return the enclosing method, or null if none.
InstListType::iterator iterator
Instruction iterators...
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.
static CastInst * CreatePointerCast(Value *S, Type *Ty, const Twine &Name, BasicBlock *InsertAtEnd)
Create a BitCast AddrSpaceCast, or a PtrToInt cast instruction.
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
static Constant * get(Type *Ty, uint64_t V, bool IsSigned=false)
If Ty is a vector type, return a Constant with a splat of the given value.
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< FragmentInfo > getFragmentInfo(expr_op_iterator Start, expr_op_iterator End)
Retrieve the details of this fragment expression.
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.
This represents the llvm.dbg.assign instruction.
void setAssignId(DIAssignID *New)
void setKillAddress()
Kill the address component.
void setExpression(DIExpression *NewExpr)
DIExpression * getExpression() const
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)
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()
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="", Instruction *InsertBefore=nullptr)
Create an "inbounds" getelementptr.
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.
Instruction * clone() const
Create a copy of 'this' instruction that is identical in all ways except the following:
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
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.
SymbolTableList< Instruction >::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
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)
uint64_t 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()
MemorySSAWalker * getWalker()
MemoryUseOrDef * getMemoryAccess(const Instruction *I) const
Given a memory Mod/Ref'ing instruction, get the MemorySSA access associated with it.
void ensureOptimizedUses()
By default, uses are not optimized during MemorySSA construction.
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...
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.
The instances of the Type class are immutable: once they are created, they are never changed.
unsigned getPointerAddressSpace() const
Get the address space of this pointer or pointer vector type.
static IntegerType * getInt8Ty(LLVMContext &C)
static PointerType * getInt8PtrTy(LLVMContext &C, unsigned AS=0)
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()
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
bool match(Val *V, const Pattern &P)
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.
CmpClass_match< LHS, RHS, ICmpInst, ICmpInst::Predicate > m_ICmp(ICmpInst::Predicate &Pred, const LHS &L, const RHS &R)
brc_match< Cond_t, bind_ty< BasicBlock >, bind_ty< BasicBlock > > m_Br(const Cond_t &C, BasicBlock *&T, BasicBlock *&F)
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.
bool calculateFragmentIntersect(const DataLayout &DL, const Value *Dest, uint64_t SliceOffsetInBits, uint64_t SliceSizeInBits, const DbgAssignIntrinsic *DAI, 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)
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.
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 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.
static void collectEphemeralValues(const Loop *L, AssumptionCache *AC, SmallPtrSetImpl< const Value * > &EphValues)
Collect a loop's ephemeral values (those used only by an assume or similar intrinsics in the loop).
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.