93using namespace PatternMatch;
95#define DEBUG_TYPE "dse"
97STATISTIC(NumRemainingStores,
"Number of stores remaining after DSE");
98STATISTIC(NumRedundantStores,
"Number of redundant stores deleted");
99STATISTIC(NumFastStores,
"Number of stores deleted");
100STATISTIC(NumFastOther,
"Number of other instrs removed");
101STATISTIC(NumCompletePartials,
"Number of stores dead by later partials");
102STATISTIC(NumModifiedStores,
"Number of stores modified");
107 "Number of times a valid candidate is returned from getDomMemoryDef");
109 "Number iterations check for reads in getDomMemoryDef");
112 "Controls which MemoryDefs are eliminated.");
117 cl::desc(
"Enable partial-overwrite tracking in DSE"));
122 cl::desc(
"Enable partial store merging in DSE"));
126 cl::desc(
"The number of memory instructions to scan for "
127 "dead store elimination (default = 150)"));
130 cl::desc(
"The maximum number of steps while walking upwards to find "
131 "MemoryDefs that may be killed (default = 90)"));
135 cl::desc(
"The maximum number candidates that only partially overwrite the "
136 "killing MemoryDef to consider"
141 cl::desc(
"The number of MemoryDefs we consider as candidates to eliminated "
142 "other stores per basic block (default = 5000)"));
147 "The cost of a step in the same basic block as the killing MemoryDef"
153 cl::desc(
"The cost of a step in a different basic "
154 "block than the killing MemoryDef"
159 cl::desc(
"The maximum number of blocks to check when trying to prove that "
160 "all paths to an exit go through a killing block (default = 50)"));
170 cl::desc(
"Allow DSE to optimize memory accesses."));
182 if (isa<StoreInst>(
I))
186 switch (II->getIntrinsicID()) {
187 default:
return false;
188 case Intrinsic::memset:
189 case Intrinsic::memcpy:
190 case Intrinsic::memcpy_element_unordered_atomic:
191 case Intrinsic::memset_element_unordered_atomic:
208 return isa<AnyMemSetInst>(
I);
225enum OverwriteResult {
229 OW_PartialEarlierWithFullLater,
243 const auto *KillingII = dyn_cast<IntrinsicInst>(KillingI);
244 const auto *DeadII = dyn_cast<IntrinsicInst>(DeadI);
245 if (KillingII ==
nullptr || DeadII ==
nullptr)
247 if (KillingII->getIntrinsicID() != DeadII->getIntrinsicID())
249 if (KillingII->getIntrinsicID() == Intrinsic::masked_store) {
252 cast<VectorType>(KillingII->getArgOperand(0)->getType());
253 VectorType *DeadTy = cast<VectorType>(DeadII->getArgOperand(0)->getType());
254 if (KillingTy->getScalarSizeInBits() != DeadTy->getScalarSizeInBits())
257 if (KillingTy->getElementCount() != DeadTy->getElementCount())
262 if (KillingPtr != DeadPtr && !AA.
isMustAlias(KillingPtr, DeadPtr))
266 if (KillingII->getArgOperand(3) != DeadII->getArgOperand(3))
285 int64_t KillingOff, int64_t DeadOff,
296 KillingOff < int64_t(DeadOff + DeadSize) &&
297 int64_t(KillingOff + KillingSize) >= DeadOff) {
300 auto &IM = IOL[DeadI];
301 LLVM_DEBUG(
dbgs() <<
"DSE: Partial overwrite: DeadLoc [" << DeadOff <<
", "
302 << int64_t(DeadOff + DeadSize) <<
") KillingLoc ["
303 << KillingOff <<
", " << int64_t(KillingOff + KillingSize)
310 int64_t KillingIntStart = KillingOff;
311 int64_t KillingIntEnd = KillingOff + KillingSize;
315 auto ILI = IM.lower_bound(KillingIntStart);
316 if (ILI != IM.end() && ILI->second <= KillingIntEnd) {
320 KillingIntStart = std::min(KillingIntStart, ILI->second);
321 KillingIntEnd = std::max(KillingIntEnd, ILI->first);
330 while (ILI != IM.end() && ILI->second <= KillingIntEnd) {
331 assert(ILI->second > KillingIntStart &&
"Unexpected interval");
332 KillingIntEnd = std::max(KillingIntEnd, ILI->first);
337 IM[KillingIntEnd] = KillingIntStart;
340 if (ILI->second <= DeadOff && ILI->first >= int64_t(DeadOff + DeadSize)) {
341 LLVM_DEBUG(
dbgs() <<
"DSE: Full overwrite from partials: DeadLoc ["
342 << DeadOff <<
", " << int64_t(DeadOff + DeadSize)
343 <<
") Composite KillingLoc [" << ILI->second <<
", "
344 << ILI->first <<
")\n");
345 ++NumCompletePartials;
353 int64_t(DeadOff + DeadSize) > KillingOff &&
354 uint64_t(KillingOff - DeadOff) + KillingSize <= DeadSize) {
355 LLVM_DEBUG(
dbgs() <<
"DSE: Partial overwrite a dead load [" << DeadOff
356 <<
", " << int64_t(DeadOff + DeadSize)
357 <<
") by a killing store [" << KillingOff <<
", "
358 << int64_t(KillingOff + KillingSize) <<
")\n");
360 return OW_PartialEarlierWithFullLater;
373 (KillingOff > DeadOff && KillingOff < int64_t(DeadOff + DeadSize) &&
374 int64_t(KillingOff + KillingSize) >= int64_t(DeadOff + DeadSize)))
387 (KillingOff <= DeadOff && int64_t(KillingOff + KillingSize) > DeadOff)) {
388 assert(int64_t(KillingOff + KillingSize) < int64_t(DeadOff + DeadSize) &&
389 "Expect to be handled as OW_Complete");
409 using BlockAddressPair = std::pair<BasicBlock *, PHITransAddr>;
421 if (
auto *MemSet = dyn_cast<MemSetInst>(SecondI))
426 auto *MemLocPtr =
const_cast<Value *
>(MemLoc.
Ptr);
431 bool isFirstBlock =
true;
434 while (!WorkList.
empty()) {
446 assert(
B == SecondBB &&
"first block is not the store block");
448 isFirstBlock =
false;
454 for (; BI != EI; ++BI) {
456 if (
I->mayWriteToMemory() &&
I != SecondI)
462 "Should not hit the entry block because SI must be dominated by LI");
472 auto Inserted = Visited.
insert(std::make_pair(Pred, TranslatedPtr));
473 if (!Inserted.second) {
476 if (TranslatedPtr != Inserted.first->second)
481 WorkList.
push_back(std::make_pair(Pred, PredAddr));
490 bool IsOverwriteEnd) {
492 DeadFragment.
SizeInBits = OldSizeInBits - NewSizeInBits;
494 OldOffsetInBits + (IsOverwriteEnd ? NewSizeInBits : 0);
496 auto CreateDeadFragExpr = [Inst, DeadFragment]() {
500 DIExpression::get(Inst->
getContext(), std::nullopt),
511 if (
auto FragInfo = DAI->getExpression()->getFragmentInfo()) {
517 auto *NewAssign = cast<DbgAssignIntrinsic>(DAI->clone());
518 NewAssign->insertAfter(DAI);
521 NewAssign->setAssignId(LinkToNothing);
522 NewAssign->setExpression(CreateDeadFragExpr());
523 NewAssign->setKillAddress();
528 uint64_t &DeadSize, int64_t KillingStart,
529 uint64_t KillingSize,
bool IsOverwriteEnd) {
530 auto *DeadIntrinsic = cast<AnyMemIntrinsic>(DeadI);
531 Align PrefAlign = DeadIntrinsic->getDestAlign().valueOrOne();
547 int64_t ToRemoveStart = 0;
551 if (IsOverwriteEnd) {
556 ToRemoveStart = KillingStart + Off;
557 if (DeadSize <=
uint64_t(ToRemoveStart - DeadStart))
559 ToRemoveSize = DeadSize -
uint64_t(ToRemoveStart - DeadStart);
561 ToRemoveStart = DeadStart;
563 "Not overlapping accesses?");
564 ToRemoveSize = KillingSize -
uint64_t(DeadStart - KillingStart);
569 if (ToRemoveSize <= (PrefAlign.
value() - Off))
571 ToRemoveSize -= PrefAlign.
value() - Off;
574 "Should preserve selected alignment");
577 assert(ToRemoveSize > 0 &&
"Shouldn't reach here if nothing to remove");
578 assert(DeadSize > ToRemoveSize &&
"Can't remove more than original size");
580 uint64_t NewSize = DeadSize - ToRemoveSize;
581 if (
auto *AMI = dyn_cast<AtomicMemIntrinsic>(DeadI)) {
584 const uint32_t ElementSize = AMI->getElementSizeInBytes();
585 if (0 != NewSize % ElementSize)
590 << (IsOverwriteEnd ?
"END" :
"BEGIN") <<
": " << *DeadI
591 <<
"\n KILLER [" << ToRemoveStart <<
", "
592 << int64_t(ToRemoveStart + ToRemoveSize) <<
")\n");
594 Value *DeadWriteLength = DeadIntrinsic->getLength();
596 DeadIntrinsic->setLength(TrimmedLength);
597 DeadIntrinsic->setDestAlignment(PrefAlign);
599 if (!IsOverwriteEnd) {
600 Value *OrigDest = DeadIntrinsic->getRawDest();
604 Value *Dest = OrigDest;
605 if (OrigDest->
getType() != Int8PtrTy)
607 Value *Indices[1] = {
610 Type::getInt8Ty(DeadIntrinsic->getContext()), Dest, Indices,
"", DeadI);
611 NewDestGEP->
setDebugLoc(DeadIntrinsic->getDebugLoc());
615 DeadIntrinsic->setDest(NewDestGEP);
624 DeadStart += ToRemoveSize;
631 int64_t &DeadStart,
uint64_t &DeadSize) {
636 int64_t KillingStart = OII->second;
637 uint64_t KillingSize = OII->first - KillingStart;
639 assert(OII->first - KillingStart >= 0 &&
"Size expected to be positive");
641 if (KillingStart > DeadStart &&
644 (
uint64_t)(KillingStart - DeadStart) < DeadSize &&
647 KillingSize >= DeadSize - (
uint64_t)(KillingStart - DeadStart)) {
648 if (
tryToShorten(DeadI, DeadStart, DeadSize, KillingStart, KillingSize,
659 int64_t &DeadStart,
uint64_t &DeadSize) {
664 int64_t KillingStart = OII->second;
665 uint64_t KillingSize = OII->first - KillingStart;
667 assert(OII->first - KillingStart >= 0 &&
"Size expected to be positive");
669 if (KillingStart <= DeadStart &&
672 KillingSize > (
uint64_t)(DeadStart - KillingStart)) {
675 assert(KillingSize - (
uint64_t)(DeadStart - KillingStart) < DeadSize &&
676 "Should have been handled as OW_Complete");
677 if (
tryToShorten(DeadI, DeadStart, DeadSize, KillingStart, KillingSize,
688 int64_t KillingOffset, int64_t DeadOffset,
715 unsigned BitOffsetDiff = (KillingOffset - DeadOffset) * 8;
716 unsigned LShiftAmount =
717 DL.isBigEndian() ? DeadValue.
getBitWidth() - BitOffsetDiff - KillingBits
720 LShiftAmount + KillingBits);
723 APInt Merged = (DeadValue & ~Mask) | (KillingValue << LShiftAmount);
725 <<
"\n Killing: " << *KillingI
726 <<
"\n Merged Value: " << Merged <<
'\n');
736 switch (II->getIntrinsicID()) {
737 case Intrinsic::lifetime_start:
738 case Intrinsic::lifetime_end:
739 case Intrinsic::invariant_end:
740 case Intrinsic::launder_invariant_group:
741 case Intrinsic::assume:
743 case Intrinsic::dbg_addr:
744 case Intrinsic::dbg_declare:
745 case Intrinsic::dbg_label:
746 case Intrinsic::dbg_value:
756bool canSkipDef(
MemoryDef *
D,
bool DefVisibleToCaller) {
760 if (
auto *CB = dyn_cast<CallBase>(DI))
761 if (CB->onlyAccessesInaccessibleMemory())
766 if (DI->
mayThrow() && !DefVisibleToCaller)
774 if (isa<FenceInst>(DI))
778 if (isNoopIntrinsic(DI))
807 bool ContainsIrreducibleLoops;
833 bool AnyUnreachableExit;
838 bool ShouldIterateEndOfFunctionDSE;
841 DSEState(
const DSEState &) =
delete;
842 DSEState &operator=(
const DSEState &) =
delete;
847 :
F(
F), AA(AA), EI(DT, LI, EphValues), BatchAA(AA, &EI), MSSA(MSSA),
848 DT(DT), PDT(PDT), TLI(TLI),
DL(
F.
getParent()->getDataLayout()), LI(LI) {
853 PostOrderNumbers[BB] = PO++;
856 if (
I.mayThrow() && !MA)
857 ThrowingBlocks.
insert(
I.getParent());
859 auto *MD = dyn_cast_or_null<MemoryDef>(MA);
861 (getLocForWrite(&
I) || isMemTerminatorInst(&
I)))
869 if (AI.hasPassPointeeByValueCopyAttr())
870 InvisibleToCallerAfterRet.
insert({&AI,
true});
876 return isa<UnreachableInst>(E->getTerminator());
884 if (
auto *CB = dyn_cast<CallBase>(
I)) {
887 (F == LibFunc_memset_chk || F == LibFunc_memcpy_chk)) {
896 if (
const auto *Len = dyn_cast<ConstantInt>(CB->getArgOperand(2)))
911 OverwriteResult isOverwrite(
const Instruction *KillingI,
915 int64_t &KillingOff, int64_t &DeadOff) {
919 if (!isGuaranteedLoopIndependent(DeadI, KillingI, DeadLoc))
923 strengthenLocationSize(KillingI, KillingLoc.
Size);
931 if (DeadUndObj == KillingUndObj && KillingLocSize.
isPrecise()) {
934 KillingUndObjSize == KillingLocSize.
getValue())
943 const auto *KillingMemI = dyn_cast<MemIntrinsic>(KillingI);
944 const auto *DeadMemI = dyn_cast<MemIntrinsic>(DeadI);
945 if (KillingMemI && DeadMemI) {
946 const Value *KillingV = KillingMemI->getLength();
947 const Value *DeadV = DeadMemI->getLength();
948 if (KillingV == DeadV && BatchAA.
isMustAlias(DeadLoc, KillingLoc))
967 if (KillingSize >= DeadSize)
974 if (Off >= 0 && (
uint64_t)Off + DeadSize <= KillingSize)
980 if (DeadUndObj != KillingUndObj) {
996 const Value *DeadBasePtr =
998 const Value *KillingBasePtr =
1003 if (DeadBasePtr != KillingBasePtr)
1021 if (DeadOff >= KillingOff) {
1024 if (
uint64_t(DeadOff - KillingOff) + DeadSize <= KillingSize)
1028 else if ((
uint64_t)(DeadOff - KillingOff) < KillingSize)
1029 return OW_MaybePartial;
1033 else if ((
uint64_t)(KillingOff - DeadOff) < DeadSize) {
1034 return OW_MaybePartial;
1041 bool isInvisibleToCallerAfterRet(
const Value *V) {
1042 if (isa<AllocaInst>(V))
1044 auto I = InvisibleToCallerAfterRet.
insert({V,
false});
1046 if (!isInvisibleToCallerOnUnwind(V)) {
1047 I.first->second =
false;
1052 return I.first->second;
1055 bool isInvisibleToCallerOnUnwind(
const Value *V) {
1056 bool RequiresNoCaptureBeforeUnwind;
1059 if (!RequiresNoCaptureBeforeUnwind)
1062 auto I = CapturedBeforeReturn.
insert({V,
true});
1069 return !
I.first->second;
1072 std::optional<MemoryLocation> getLocForWrite(
Instruction *
I)
const {
1073 if (!
I->mayWriteToMemory())
1074 return std::nullopt;
1076 if (
auto *CB = dyn_cast<CallBase>(
I))
1085 assert(getLocForWrite(
I) &&
"Must have analyzable write");
1089 return SI->isUnordered();
1091 if (
auto *CB = dyn_cast<CallBase>(
I)) {
1093 if (
auto *
MI = dyn_cast<MemIntrinsic>(CB))
1094 return !
MI->isVolatile();
1098 if (CB->isLifetimeStartOrEnd())
1101 return CB->use_empty() && CB->willReturn() && CB->doesNotThrow() &&
1102 !CB->isTerminator();
1118 if (
auto *CB = dyn_cast<CallBase>(UseInst))
1119 if (CB->onlyAccessesInaccessibleMemory())
1122 int64_t InstWriteOffset, DepWriteOffset;
1123 if (
auto CC = getLocForWrite(UseInst))
1124 return isOverwrite(UseInst, DefInst, *
CC, DefLoc, InstWriteOffset,
1125 DepWriteOffset) == OW_Complete;
1130 bool isWriteAtEndOfFunction(
MemoryDef *Def) {
1132 << *
Def->getMemoryInst()
1133 <<
") is at the end the function \n");
1135 auto MaybeLoc = getLocForWrite(
Def->getMemoryInst());
1137 LLVM_DEBUG(
dbgs() <<
" ... could not get location for write.\n");
1143 auto PushMemUses = [&WorkList, &Visited](
MemoryAccess *Acc) {
1144 if (!Visited.
insert(Acc).second)
1147 WorkList.
push_back(cast<MemoryAccess>(U.getUser()));
1150 for (
unsigned I = 0;
I < WorkList.
size();
I++) {
1157 if (isa<MemoryPhi>(UseAccess)) {
1161 if (!isGuaranteedLoopInvariant(MaybeLoc->Ptr))
1164 PushMemUses(cast<MemoryPhi>(UseAccess));
1169 Instruction *UseInst = cast<MemoryUseOrDef>(UseAccess)->getMemoryInst();
1170 if (isReadClobber(*MaybeLoc, UseInst)) {
1171 LLVM_DEBUG(
dbgs() <<
" ... hit read clobber " << *UseInst <<
".\n");
1175 if (
MemoryDef *UseDef = dyn_cast<MemoryDef>(UseAccess))
1176 PushMemUses(UseDef);
1184 std::optional<std::pair<MemoryLocation, bool>>
1192 if (
auto *CB = dyn_cast<CallBase>(
I)) {
1197 return std::nullopt;
1203 auto *CB = dyn_cast<CallBase>(
I);
1204 return CB && (CB->getIntrinsicID() == Intrinsic::lifetime_end ||
1212 std::optional<std::pair<MemoryLocation, bool>> MaybeTermLoc =
1213 getLocForTerminator(MaybeTerm);
1224 auto TermLoc = MaybeTermLoc->first;
1225 if (MaybeTermLoc->second) {
1229 int64_t InstWriteOffset = 0;
1230 int64_t DepWriteOffset = 0;
1231 return isOverwrite(MaybeTerm, AccessI, TermLoc, Loc, InstWriteOffset,
1232 DepWriteOffset) == OW_Complete;
1237 if (isNoopIntrinsic(UseInst))
1242 if (
auto SI = dyn_cast<StoreInst>(UseInst))
1248 if (
auto *CB = dyn_cast<CallBase>(UseInst))
1249 if (CB->onlyAccessesInaccessibleMemory())
1260 bool isGuaranteedLoopIndependent(
const Instruction *Current,
1270 if (!ContainsIrreducibleLoops && CurrentLI &&
1274 return isGuaranteedLoopInvariant(CurrentLoc.
Ptr);
1280 bool isGuaranteedLoopInvariant(
const Value *
Ptr) {
1281 Ptr =
Ptr->stripPointerCasts();
1282 if (
auto *
GEP = dyn_cast<GEPOperator>(
Ptr))
1283 if (
GEP->hasAllConstantIndices())
1284 Ptr =
GEP->getPointerOperand()->stripPointerCasts();
1286 if (
auto *
I = dyn_cast<Instruction>(
Ptr)) {
1287 return I->getParent()->isEntryBlock() ||
1288 (!ContainsIrreducibleLoops && !LI.
getLoopFor(
I->getParent()));
1299 std::optional<MemoryAccess *>
1302 unsigned &ScanLimit,
unsigned &WalkerStepLimit,
1303 bool IsMemTerm,
unsigned &PartialLimit) {
1304 if (ScanLimit == 0 || WalkerStepLimit == 0) {
1306 return std::nullopt;
1323 std::optional<MemoryLocation> CurrentLoc;
1324 for (;; Current = cast<MemoryDef>(Current)->getDefiningAccess()) {
1326 dbgs() <<
" visiting " << *Current;
1328 dbgs() <<
" (" << *cast<MemoryUseOrDef>(Current)->getMemoryInst()
1339 return std::nullopt;
1347 if (WalkerStepLimit <= StepCost) {
1349 return std::nullopt;
1351 WalkerStepLimit -= StepCost;
1355 if (isa<MemoryPhi>(Current)) {
1362 MemoryDef *CurrentDef = cast<MemoryDef>(Current);
1365 if (canSkipDef(CurrentDef, !isInvisibleToCallerOnUnwind(KillingUndObj))) {
1366 CanOptimize =
false;
1372 if (mayThrowBetween(KillingI, CurrentI, KillingUndObj)) {
1374 return std::nullopt;
1379 if (isDSEBarrier(KillingUndObj, CurrentI)) {
1381 return std::nullopt;
1388 if (!isa<IntrinsicInst>(CurrentI) && isReadClobber(KillingLoc, CurrentI))
1389 return std::nullopt;
1392 if (
any_of(Current->
uses(), [
this, &KillingLoc, StartAccess](
Use &U) {
1393 if (auto *UseOrDef = dyn_cast<MemoryUseOrDef>(U.getUser()))
1394 return !MSSA.dominates(StartAccess, UseOrDef) &&
1395 isReadClobber(KillingLoc, UseOrDef->getMemoryInst());
1399 return std::nullopt;
1404 CurrentLoc = getLocForWrite(CurrentI);
1405 if (!CurrentLoc || !isRemovable(CurrentI)) {
1406 CanOptimize =
false;
1413 if (!isGuaranteedLoopIndependent(CurrentI, KillingI, *CurrentLoc)) {
1415 CanOptimize =
false;
1423 if (!isMemTerminator(*CurrentLoc, CurrentI, KillingI)) {
1424 CanOptimize =
false;
1428 int64_t KillingOffset = 0;
1429 int64_t DeadOffset = 0;
1430 auto OR = isOverwrite(KillingI, CurrentI, KillingLoc, *CurrentLoc,
1431 KillingOffset, DeadOffset);
1437 (OR == OW_Complete || OR == OW_MaybePartial))
1443 CanOptimize =
false;
1448 if (OR == OW_Unknown || OR == OW_None)
1450 else if (OR == OW_MaybePartial) {
1455 if (PartialLimit <= 1) {
1456 WalkerStepLimit -= 1;
1457 LLVM_DEBUG(
dbgs() <<
" ... reached partial limit ... continue with next access\n");
1474 Instruction *MaybeDeadI = cast<MemoryDef>(MaybeDeadAccess)->getMemoryInst();
1475 LLVM_DEBUG(
dbgs() <<
" Checking for reads of " << *MaybeDeadAccess <<
" ("
1476 << *MaybeDeadI <<
")\n");
1483 PushMemUses(MaybeDeadAccess);
1486 for (
unsigned I = 0;
I < WorkList.
size();
I++) {
1491 if (ScanLimit < (WorkList.
size() -
I)) {
1493 return std::nullopt;
1496 NumDomMemDefChecks++;
1498 if (isa<MemoryPhi>(UseAccess)) {
1503 LLVM_DEBUG(
dbgs() <<
" ... skipping, dominated by killing block\n");
1507 PushMemUses(UseAccess);
1511 Instruction *UseInst = cast<MemoryUseOrDef>(UseAccess)->getMemoryInst();
1517 LLVM_DEBUG(
dbgs() <<
" ... skipping, dominated by killing def\n");
1523 if (isMemTerminator(MaybeDeadLoc, MaybeDeadI, UseInst)) {
1526 <<
" ... skipping, memterminator invalidates following accesses\n");
1530 if (isNoopIntrinsic(cast<MemoryUseOrDef>(UseAccess)->getMemoryInst())) {
1532 PushMemUses(UseAccess);
1536 if (UseInst->
mayThrow() && !isInvisibleToCallerOnUnwind(KillingUndObj)) {
1538 return std::nullopt;
1543 if (isReadClobber(MaybeDeadLoc, UseInst)) {
1545 return std::nullopt;
1551 if (MaybeDeadAccess == UseAccess &&
1552 !isGuaranteedLoopInvariant(MaybeDeadLoc.
Ptr)) {
1553 LLVM_DEBUG(
dbgs() <<
" ... found not loop invariant self access\n");
1554 return std::nullopt;
1560 if (KillingDef == UseAccess || MaybeDeadAccess == UseAccess) {
1575 if (
MemoryDef *UseDef = dyn_cast<MemoryDef>(UseAccess)) {
1576 if (isCompleteOverwrite(MaybeDeadLoc, MaybeDeadI, UseInst)) {
1578 if (PostOrderNumbers.
find(MaybeKillingBlock)->second <
1579 PostOrderNumbers.
find(MaybeDeadAccess->
getBlock())->second) {
1580 if (!isInvisibleToCallerAfterRet(KillingUndObj)) {
1582 <<
" ... found killing def " << *UseInst <<
"\n");
1583 KillingDefs.
insert(UseInst);
1587 <<
" ... found preceeding def " << *UseInst <<
"\n");
1588 return std::nullopt;
1591 PushMemUses(UseDef);
1598 if (!isInvisibleToCallerAfterRet(KillingUndObj)) {
1601 KillingBlocks.
insert(KD->getParent());
1603 "Expected at least a single killing block");
1617 if (!AnyUnreachableExit)
1618 return std::nullopt;
1622 CommonPred =
nullptr;
1626 if (KillingBlocks.
count(CommonPred))
1627 return {MaybeDeadAccess};
1633 WorkList.
insert(CommonPred);
1636 if (!isa<UnreachableInst>(
R->getTerminator()))
1643 for (
unsigned I = 0;
I < WorkList.
size();
I++) {
1646 if (KillingBlocks.
count(Current))
1648 if (Current == MaybeDeadAccess->
getBlock())
1649 return std::nullopt;
1660 return std::nullopt;
1667 return {MaybeDeadAccess};
1677 while (!NowDeadInsts.
empty()) {
1687 if (
MemoryDef *MD = dyn_cast<MemoryDef>(MA)) {
1689 if (
auto *SI = dyn_cast<StoreInst>(MD->getMemoryInst())) {
1690 if (
SI->getValueOperand()->getType()->isPointerTy()) {
1692 if (CapturedBeforeReturn.
erase(UO))
1693 ShouldIterateEndOfFunctionDSE =
true;
1694 InvisibleToCallerAfterRet.
erase(UO);
1699 Updater.removeMemoryAccess(MA);
1703 if (
I != IOLs.
end())
1704 I->second.erase(DeadInst);
1707 if (
Instruction *OpI = dyn_cast<Instruction>(O)) {
1723 const Value *KillingUndObj) {
1727 if (KillingUndObj && isInvisibleToCallerOnUnwind(KillingUndObj))
1732 return !ThrowingBlocks.
empty();
1743 if (DeadI->
mayThrow() && !isInvisibleToCallerOnUnwind(KillingUndObj))
1749 if (
auto *LI = dyn_cast<LoadInst>(DeadI))
1751 if (
auto *SI = dyn_cast<StoreInst>(DeadI))
1753 if (
auto *ARMW = dyn_cast<AtomicRMWInst>(DeadI))
1755 if (
auto *CmpXchg = dyn_cast<AtomicCmpXchgInst>(DeadI))
1765 bool eliminateDeadWritesAtEndOfFunction() {
1766 bool MadeChange =
false;
1769 <<
"Trying to eliminate MemoryDefs at the end of the function\n");
1771 ShouldIterateEndOfFunctionDSE =
false;
1777 auto DefLoc = getLocForWrite(DefI);
1778 if (!DefLoc || !isRemovable(DefI))
1787 if (!isInvisibleToCallerAfterRet(UO))
1790 if (isWriteAtEndOfFunction(Def)) {
1792 LLVM_DEBUG(
dbgs() <<
" ... MemoryDef is not accessed until the end "
1793 "of the function\n");
1799 }
while (ShouldIterateEndOfFunctionDSE);
1807 MemSetInst *MemSet = dyn_cast<MemSetInst>(DefI);
1812 if (!StoredConstant || !StoredConstant->
isNullValue())
1815 if (!isRemovable(DefI))
1819 if (
F.hasFnAttribute(Attribute::SanitizeMemory) ||
1820 F.hasFnAttribute(Attribute::SanitizeAddress) ||
1821 F.hasFnAttribute(Attribute::SanitizeHWAddress) ||
1822 F.getName() ==
"calloc")
1824 auto *
Malloc =
const_cast<CallInst *
>(dyn_cast<CallInst>(DefUO));
1827 auto *InnerCallee =
Malloc->getCalledFunction();
1831 if (!TLI.
getLibFunc(*InnerCallee, Func) || !TLI.
has(Func) ||
1832 Func != LibFunc_malloc)
1838 auto *MallocBB =
Malloc->getParent(),
1839 *MemsetBB = Memset->getParent();
1840 if (MallocBB == MemsetBB)
1842 auto *
Ptr = Memset->getArgOperand(0);
1843 auto *TI = MallocBB->getTerminator();
1849 if (Pred != ICmpInst::ICMP_EQ || MemsetBB != FalseBB)
1856 if (!shouldCreateCalloc(
Malloc, MemSet) ||
1861 Type *SizeTTy =
Malloc->getArgOperand(0)->getType();
1863 Malloc->getArgOperand(0), IRB, TLI);
1868 cast<MemoryDef>(Updater.getMemorySSA()->getMemoryAccess(
Malloc));
1870 Updater.createMemoryAccessAfter(cast<Instruction>(Calloc), LastDef,
1872 auto *NewAccessMD = cast<MemoryDef>(NewAccess);
1873 Updater.insertDef(NewAccessMD,
true);
1874 Updater.removeMemoryAccess(
Malloc);
1875 Malloc->replaceAllUsesWith(Calloc);
1876 Malloc->eraseFromParent();
1885 MemSetInst *MemSet = dyn_cast<MemSetInst>(DefI);
1886 Constant *StoredConstant =
nullptr;
1888 StoredConstant = dyn_cast<Constant>(
Store->getOperand(0));
1890 StoredConstant = dyn_cast<Constant>(MemSet->
getValue());
1894 if (!isRemovable(DefI))
1897 if (StoredConstant) {
1902 if (InitC && InitC == StoredConstant)
1910 if (
auto *LoadI = dyn_cast<LoadInst>(
Store->getOperand(0))) {
1911 if (LoadI->getPointerOperand() ==
Store->getOperand(1)) {
1915 if (LoadAccess ==
Def->getDefiningAccess())
1930 for (
unsigned I = 1;
I < ToCheck.
size(); ++
I) {
1931 Current = ToCheck[
I];
1932 if (
auto PhiAccess = dyn_cast<MemoryPhi>(Current)) {
1934 for (
auto &
Use : PhiAccess->incoming_values())
1935 ToCheck.
insert(cast<MemoryAccess>(&
Use));
1941 assert(isa<MemoryDef>(Current) &&
1942 "Only MemoryDefs should reach here.");
1947 if (LoadAccess != Current)
1958 bool Changed =
false;
1959 for (
auto OI : IOL) {
1962 assert(isRemovable(DeadI) &&
"Expect only removable instruction");
1965 int64_t DeadStart = 0;
1979 bool eliminateRedundantStoresOfExistingValues() {
1980 bool MadeChange =
false;
1981 LLVM_DEBUG(
dbgs() <<
"Trying to eliminate MemoryDefs that write the "
1982 "already existing value\n");
1983 for (
auto *Def : MemDefs) {
1988 auto MaybeDefLoc = getLocForWrite(DefInst);
1989 if (!MaybeDefLoc || !isRemovable(DefInst))
1996 if (
Def->isOptimized())
1997 UpperDef = dyn_cast<MemoryDef>(
Def->getOptimized());
1999 UpperDef = dyn_cast<MemoryDef>(
Def->getDefiningAccess());
2004 auto IsRedundantStore = [&]() {
2007 if (
auto *MemSetI = dyn_cast<MemSetInst>(UpperInst)) {
2008 if (
auto *SI = dyn_cast<StoreInst>(DefInst)) {
2011 int64_t InstWriteOffset = 0;
2012 int64_t DepWriteOffset = 0;
2013 auto OR = isOverwrite(UpperInst, DefInst, UpperLoc, *MaybeDefLoc,
2014 InstWriteOffset, DepWriteOffset);
2016 return StoredByte && StoredByte == MemSetI->getOperand(1) &&
2023 if (!IsRedundantStore() || isReadClobber(*MaybeDefLoc, DefInst))
2025 LLVM_DEBUG(
dbgs() <<
"DSE: Remove No-Op Store:\n DEAD: " << *DefInst
2028 NumRedundantStores++;
2040 bool MadeChange =
false;
2043 DSEState State(
F, AA, MSSA, DT, PDT, AC, TLI, LI);
2045 for (
unsigned I = 0;
I < State.MemDefs.size();
I++) {
2047 if (State.SkipStores.count(KillingDef))
2051 std::optional<MemoryLocation> MaybeKillingLoc;
2052 if (State.isMemTerminatorInst(KillingI)) {
2053 if (
auto KillingLoc = State.getLocForTerminator(KillingI))
2054 MaybeKillingLoc = KillingLoc->first;
2056 MaybeKillingLoc = State.getLocForWrite(KillingI);
2059 if (!MaybeKillingLoc) {
2060 LLVM_DEBUG(
dbgs() <<
"Failed to find analyzable write location for "
2061 << *KillingI <<
"\n");
2065 assert(KillingLoc.
Ptr &&
"KillingLoc should not be null");
2068 << *KillingDef <<
" (" << *KillingI <<
")\n");
2077 bool Shortend =
false;
2078 bool IsMemTerm = State.isMemTerminatorInst(KillingI);
2080 for (
unsigned I = 0;
I < ToCheck.
size();
I++) {
2082 if (State.SkipStores.count(Current))
2085 std::optional<MemoryAccess *> MaybeDeadAccess = State.getDomMemoryDef(
2086 KillingDef, Current, KillingLoc, KillingUndObj, ScanLimit,
2087 WalkerStepLimit, IsMemTerm, PartialLimit);
2089 if (!MaybeDeadAccess) {
2095 LLVM_DEBUG(
dbgs() <<
" Checking if we can kill " << *DeadAccess);
2096 if (isa<MemoryPhi>(DeadAccess)) {
2097 LLVM_DEBUG(
dbgs() <<
"\n ... adding incoming values to worklist\n");
2098 for (
Value *V : cast<MemoryPhi>(DeadAccess)->incoming_values()) {
2106 if (State.PostOrderNumbers[IncomingBlock] >
2107 State.PostOrderNumbers[PhiBlock])
2108 ToCheck.
insert(IncomingAccess);
2112 auto *DeadDefAccess = cast<MemoryDef>(DeadAccess);
2113 Instruction *DeadI = DeadDefAccess->getMemoryInst();
2115 ToCheck.
insert(DeadDefAccess->getDefiningAccess());
2116 NumGetDomMemoryDefPassed++;
2125 if (KillingUndObj != DeadUndObj)
2127 LLVM_DEBUG(
dbgs() <<
"DSE: Remove Dead Store:\n DEAD: " << *DeadI
2128 <<
"\n KILLER: " << *KillingI <<
'\n');
2129 State.deleteDeadInstruction(DeadI);
2134 int64_t KillingOffset = 0;
2135 int64_t DeadOffset = 0;
2136 OverwriteResult
OR = State.isOverwrite(
2137 KillingI, DeadI, KillingLoc, DeadLoc, KillingOffset, DeadOffset);
2138 if (OR == OW_MaybePartial) {
2139 auto Iter = State.IOLs.insert(
2140 std::make_pair<BasicBlock *, InstOverlapIntervalsTy>(
2142 auto &IOL = Iter.first->second;
2144 DeadOffset, DeadI, IOL);
2148 auto *DeadSI = dyn_cast<StoreInst>(DeadI);
2149 auto *KillingSI = dyn_cast<StoreInst>(KillingI);
2153 if (DeadSI && KillingSI && DT.
dominates(DeadSI, KillingSI)) {
2155 KillingSI, DeadSI, KillingOffset, DeadOffset, State.DL,
2156 State.BatchAA, &DT)) {
2159 DeadSI->setOperand(0, Merged);
2160 ++NumModifiedStores;
2166 State.deleteDeadInstruction(KillingSI);
2167 auto I = State.IOLs.find(DeadSI->getParent());
2168 if (
I != State.IOLs.end())
2169 I->second.erase(DeadSI);
2175 if (OR == OW_Complete) {
2176 LLVM_DEBUG(
dbgs() <<
"DSE: Remove Dead Store:\n DEAD: " << *DeadI
2177 <<
"\n KILLER: " << *KillingI <<
'\n');
2178 State.deleteDeadInstruction(DeadI);
2186 if (!Shortend && State.storeIsNoop(KillingDef, KillingUndObj)) {
2187 LLVM_DEBUG(
dbgs() <<
"DSE: Remove No-Op Store:\n DEAD: " << *KillingI
2189 State.deleteDeadInstruction(KillingI);
2190 NumRedundantStores++;
2196 if (!Shortend && State.tryFoldIntoCalloc(KillingDef, KillingUndObj)) {
2197 LLVM_DEBUG(
dbgs() <<
"DSE: Remove memset after forming calloc:\n"
2198 <<
" DEAD: " << *KillingI <<
'\n');
2199 State.deleteDeadInstruction(KillingI);
2206 for (
auto &KV : State.IOLs)
2207 MadeChange |= State.removePartiallyOverlappedStores(KV.second);
2209 MadeChange |= State.eliminateRedundantStoresOfExistingValues();
2210 MadeChange |= State.eliminateDeadWritesAtEndOfFunction();
2227 bool Changed = eliminateDeadStores(
F, AA, MSSA, DT, PDT, AC, TLI, LI);
2229#ifdef LLVM_ENABLE_STATS
2232 NumRemainingStores += isa<StoreInst>(&
I);
2257 if (skipFunction(
F))
2260 AliasAnalysis &AA = getAnalysis<AAResultsWrapperPass>().getAAResults();
2261 DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
2263 getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(
F);
2264 MemorySSA &MSSA = getAnalysis<MemorySSAWrapperPass>().getMSSA();
2266 getAnalysis<PostDominatorTreeWrapperPass>().getPostDomTree();
2268 getAnalysis<AssumptionCacheTracker>().getAssumptionCache(
F);
2269 LoopInfo &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
2271 bool Changed = eliminateDeadStores(
F, AA, MSSA, DT, PDT, AC, TLI, LI);
2273#ifdef LLVM_ENABLE_STATS
2276 NumRemainingStores += isa<StoreInst>(&
I);
2301char DSELegacyPass::ID = 0;
2318 return new DSELegacyPass();
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 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 void shortenAssignment(Instruction *Inst, uint64_t OldOffsetInBits, uint64_t OldSizeInBits, uint64_t NewSizeInBits, bool IsOverwriteEnd)
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.
static bool runOnFunction(Function &F, bool PostInlining)
This is the interface for a simple mod/ref and alias analysis over globals.
static void deleteDeadInstruction(Instruction *I)
Machine Common Subexpression Elimination
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.
#define INITIALIZE_PASS_DEPENDENCY(depName)
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
This file 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.
A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object.
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.
Represent the analysis usage information of a pass.
AnalysisUsage & addRequired()
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
void setPreservesCFG()
This function should be called by the pass, iff they do not:
This class represents an incoming formal argument to a Function.
A function analysis which provides an AssumptionCache.
An immutable pass that tracks lazily created AssumptionCache objects.
A cache of @llvm.assume calls within a function.
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 bool fragmentsOverlap(const FragmentInfo &A, const FragmentInfo &B)
Check if fragments overlap between a pair of FragmentInfos.
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)
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.
Legacy analysis pass which computes a DominatorTree.
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)
FunctionPass class - This class is used to implement most global optimizations.
const BasicBlock & getEntryBlock() const
static GetElementPtrInst * CreateInBounds(Type *PointeeType, Value *Ptr, ArrayRef< Value * > IdxList, const Twine &NameStr="", Instruction *InsertBefore=nullptr)
Create an "inbounds" getelementptr.
Legacy wrapper pass to provide the GlobalsAAResult object.
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
bool mayWriteToMemory() const LLVM_READONLY
Return true if this instruction may modify memory.
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 mayThrow() const LLVM_READONLY
Return true if this instruction may throw an exception.
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.
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.
The legacy pass manager's analysis pass to compute loop information.
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)
A wrapper analysis pass for the legacy pass manager that exposes a MemoryDepnedenceResults instance.
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...
Legacy analysis pass which computes MemorySSA.
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.
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 PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
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.
User * getUser() const
Returns the User that contains this Use.
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.
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
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.
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.
FunctionPass * createDeadStoreEliminationPass()
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...
void initializeDSELegacyPassPass(PassRegistry &)
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...
void 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.