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) {
632 Value *Indices[1] = {
635 Type::getInt8Ty(DeadIntrinsic->getContext()), OrigDest, Indices,
"", DeadI);
636 NewDestGEP->
setDebugLoc(DeadIntrinsic->getDebugLoc());
637 DeadIntrinsic->setDest(NewDestGEP);
646 DeadStart += ToRemoveSize;
653 int64_t &DeadStart,
uint64_t &DeadSize) {
658 int64_t KillingStart = OII->second;
659 uint64_t KillingSize = OII->first - KillingStart;
661 assert(OII->first - KillingStart >= 0 &&
"Size expected to be positive");
663 if (KillingStart > DeadStart &&
666 (
uint64_t)(KillingStart - DeadStart) < DeadSize &&
669 KillingSize >= DeadSize - (
uint64_t)(KillingStart - DeadStart)) {
670 if (
tryToShorten(DeadI, DeadStart, DeadSize, KillingStart, KillingSize,
681 int64_t &DeadStart,
uint64_t &DeadSize) {
686 int64_t KillingStart = OII->second;
687 uint64_t KillingSize = OII->first - KillingStart;
689 assert(OII->first - KillingStart >= 0 &&
"Size expected to be positive");
691 if (KillingStart <= DeadStart &&
694 KillingSize > (
uint64_t)(DeadStart - KillingStart)) {
697 assert(KillingSize - (
uint64_t)(DeadStart - KillingStart) < DeadSize &&
698 "Should have been handled as OW_Complete");
699 if (
tryToShorten(DeadI, DeadStart, DeadSize, KillingStart, KillingSize,
710 int64_t KillingOffset, int64_t DeadOffset,
737 unsigned BitOffsetDiff = (KillingOffset - DeadOffset) * 8;
738 unsigned LShiftAmount =
739 DL.isBigEndian() ? DeadValue.
getBitWidth() - BitOffsetDiff - KillingBits
742 LShiftAmount + KillingBits);
745 APInt Merged = (DeadValue & ~Mask) | (KillingValue << LShiftAmount);
747 <<
"\n Killing: " << *KillingI
748 <<
"\n Merged Value: " << Merged <<
'\n');
758 switch (II->getIntrinsicID()) {
759 case Intrinsic::lifetime_start:
760 case Intrinsic::lifetime_end:
761 case Intrinsic::invariant_end:
762 case Intrinsic::launder_invariant_group:
763 case Intrinsic::assume:
765 case Intrinsic::dbg_declare:
766 case Intrinsic::dbg_label:
767 case Intrinsic::dbg_value:
777bool canSkipDef(
MemoryDef *
D,
bool DefVisibleToCaller) {
781 if (
auto *CB = dyn_cast<CallBase>(DI))
782 if (CB->onlyAccessesInaccessibleMemory())
787 if (DI->
mayThrow() && !DefVisibleToCaller)
795 if (isa<FenceInst>(DI))
799 if (isNoopIntrinsic(DI))
828 bool ContainsIrreducibleLoops;
854 bool AnyUnreachableExit;
859 bool ShouldIterateEndOfFunctionDSE;
862 DSEState(
const DSEState &) =
delete;
863 DSEState &operator=(
const DSEState &) =
delete;
868 :
F(
F), AA(AA), EI(DT, LI, EphValues), BatchAA(AA, &EI), MSSA(MSSA),
869 DT(DT), PDT(PDT), TLI(TLI),
DL(
F.
getParent()->getDataLayout()), LI(LI) {
874 PostOrderNumbers[BB] = PO++;
877 if (
I.mayThrow() && !MA)
878 ThrowingBlocks.
insert(
I.getParent());
880 auto *MD = dyn_cast_or_null<MemoryDef>(MA);
882 (getLocForWrite(&
I) || isMemTerminatorInst(&
I)))
890 if (AI.hasPassPointeeByValueCopyAttr())
891 InvisibleToCallerAfterRet.
insert({&AI,
true});
897 return isa<UnreachableInst>(E->getTerminator());
905 if (
auto *CB = dyn_cast<CallBase>(
I)) {
908 (F == LibFunc_memset_chk || F == LibFunc_memcpy_chk)) {
917 if (
const auto *Len = dyn_cast<ConstantInt>(CB->getArgOperand(2)))
932 OverwriteResult isOverwrite(
const Instruction *KillingI,
936 int64_t &KillingOff, int64_t &DeadOff) {
940 if (!isGuaranteedLoopIndependent(DeadI, KillingI, DeadLoc))
944 strengthenLocationSize(KillingI, KillingLoc.
Size);
952 if (DeadUndObj == KillingUndObj && KillingLocSize.
isPrecise() &&
956 KillingUndObjSize == KillingLocSize.
getValue())
965 const auto *KillingMemI = dyn_cast<MemIntrinsic>(KillingI);
966 const auto *DeadMemI = dyn_cast<MemIntrinsic>(DeadI);
967 if (KillingMemI && DeadMemI) {
968 const Value *KillingV = KillingMemI->getLength();
969 const Value *DeadV = DeadMemI->getLength();
970 if (KillingV == DeadV && BatchAA.
isMustAlias(DeadLoc, KillingLoc))
989 if (KillingSize >= DeadSize)
996 if (Off >= 0 && (
uint64_t)Off + DeadSize <= KillingSize)
1002 if (DeadUndObj != KillingUndObj) {
1018 const Value *DeadBasePtr =
1020 const Value *KillingBasePtr =
1025 if (DeadBasePtr != KillingBasePtr)
1043 if (DeadOff >= KillingOff) {
1046 if (
uint64_t(DeadOff - KillingOff) + DeadSize <= KillingSize)
1050 else if ((
uint64_t)(DeadOff - KillingOff) < KillingSize)
1051 return OW_MaybePartial;
1055 else if ((
uint64_t)(KillingOff - DeadOff) < DeadSize) {
1056 return OW_MaybePartial;
1063 bool isInvisibleToCallerAfterRet(
const Value *V) {
1064 if (isa<AllocaInst>(V))
1066 auto I = InvisibleToCallerAfterRet.
insert({
V,
false});
1068 if (!isInvisibleToCallerOnUnwind(V)) {
1069 I.first->second =
false;
1074 return I.first->second;
1077 bool isInvisibleToCallerOnUnwind(
const Value *V) {
1078 bool RequiresNoCaptureBeforeUnwind;
1081 if (!RequiresNoCaptureBeforeUnwind)
1084 auto I = CapturedBeforeReturn.
insert({
V,
true});
1091 return !
I.first->second;
1094 std::optional<MemoryLocation> getLocForWrite(
Instruction *
I)
const {
1095 if (!
I->mayWriteToMemory())
1096 return std::nullopt;
1098 if (
auto *CB = dyn_cast<CallBase>(
I))
1107 assert(getLocForWrite(
I) &&
"Must have analyzable write");
1111 return SI->isUnordered();
1113 if (
auto *CB = dyn_cast<CallBase>(
I)) {
1115 if (
auto *
MI = dyn_cast<MemIntrinsic>(CB))
1116 return !
MI->isVolatile();
1120 if (CB->isLifetimeStartOrEnd())
1123 return CB->use_empty() && CB->willReturn() && CB->doesNotThrow() &&
1124 !CB->isTerminator();
1140 if (
auto *CB = dyn_cast<CallBase>(UseInst))
1141 if (CB->onlyAccessesInaccessibleMemory())
1144 int64_t InstWriteOffset, DepWriteOffset;
1145 if (
auto CC = getLocForWrite(UseInst))
1146 return isOverwrite(UseInst, DefInst, *
CC, DefLoc, InstWriteOffset,
1147 DepWriteOffset) == OW_Complete;
1152 bool isWriteAtEndOfFunction(
MemoryDef *Def) {
1154 << *
Def->getMemoryInst()
1155 <<
") is at the end the function \n");
1157 auto MaybeLoc = getLocForWrite(
Def->getMemoryInst());
1159 LLVM_DEBUG(
dbgs() <<
" ... could not get location for write.\n");
1165 auto PushMemUses = [&WorkList, &Visited](
MemoryAccess *Acc) {
1166 if (!Visited.
insert(Acc).second)
1169 WorkList.
push_back(cast<MemoryAccess>(
U.getUser()));
1172 for (
unsigned I = 0;
I < WorkList.
size();
I++) {
1179 if (isa<MemoryPhi>(UseAccess)) {
1183 if (!isGuaranteedLoopInvariant(MaybeLoc->Ptr))
1186 PushMemUses(cast<MemoryPhi>(UseAccess));
1191 Instruction *UseInst = cast<MemoryUseOrDef>(UseAccess)->getMemoryInst();
1192 if (isReadClobber(*MaybeLoc, UseInst)) {
1193 LLVM_DEBUG(
dbgs() <<
" ... hit read clobber " << *UseInst <<
".\n");
1197 if (
MemoryDef *UseDef = dyn_cast<MemoryDef>(UseAccess))
1198 PushMemUses(UseDef);
1206 std::optional<std::pair<MemoryLocation, bool>>
1214 if (
auto *CB = dyn_cast<CallBase>(
I)) {
1219 return std::nullopt;
1225 auto *CB = dyn_cast<CallBase>(
I);
1226 return CB && (CB->getIntrinsicID() == Intrinsic::lifetime_end ||
1234 std::optional<std::pair<MemoryLocation, bool>> MaybeTermLoc =
1235 getLocForTerminator(MaybeTerm);
1246 auto TermLoc = MaybeTermLoc->first;
1247 if (MaybeTermLoc->second) {
1251 int64_t InstWriteOffset = 0;
1252 int64_t DepWriteOffset = 0;
1253 return isOverwrite(MaybeTerm, AccessI, TermLoc, Loc, InstWriteOffset,
1254 DepWriteOffset) == OW_Complete;
1259 if (isNoopIntrinsic(UseInst))
1264 if (
auto SI = dyn_cast<StoreInst>(UseInst))
1270 if (
auto *CB = dyn_cast<CallBase>(UseInst))
1271 if (CB->onlyAccessesInaccessibleMemory())
1282 bool isGuaranteedLoopIndependent(
const Instruction *Current,
1292 if (!ContainsIrreducibleLoops && CurrentLI &&
1296 return isGuaranteedLoopInvariant(CurrentLoc.
Ptr);
1302 bool isGuaranteedLoopInvariant(
const Value *
Ptr) {
1303 Ptr =
Ptr->stripPointerCasts();
1304 if (
auto *
GEP = dyn_cast<GEPOperator>(
Ptr))
1305 if (
GEP->hasAllConstantIndices())
1306 Ptr =
GEP->getPointerOperand()->stripPointerCasts();
1308 if (
auto *
I = dyn_cast<Instruction>(
Ptr)) {
1309 return I->getParent()->isEntryBlock() ||
1310 (!ContainsIrreducibleLoops && !LI.
getLoopFor(
I->getParent()));
1321 std::optional<MemoryAccess *>
1324 unsigned &ScanLimit,
unsigned &WalkerStepLimit,
1325 bool IsMemTerm,
unsigned &PartialLimit) {
1326 if (ScanLimit == 0 || WalkerStepLimit == 0) {
1328 return std::nullopt;
1345 std::optional<MemoryLocation> CurrentLoc;
1346 for (;; Current = cast<MemoryDef>(Current)->getDefiningAccess()) {
1348 dbgs() <<
" visiting " << *Current;
1350 dbgs() <<
" (" << *cast<MemoryUseOrDef>(Current)->getMemoryInst()
1361 return std::nullopt;
1369 if (WalkerStepLimit <= StepCost) {
1371 return std::nullopt;
1373 WalkerStepLimit -= StepCost;
1377 if (isa<MemoryPhi>(Current)) {
1384 MemoryDef *CurrentDef = cast<MemoryDef>(Current);
1387 if (canSkipDef(CurrentDef, !isInvisibleToCallerOnUnwind(KillingUndObj))) {
1388 CanOptimize =
false;
1394 if (mayThrowBetween(KillingI, CurrentI, KillingUndObj)) {
1396 return std::nullopt;
1401 if (isDSEBarrier(KillingUndObj, CurrentI)) {
1403 return std::nullopt;
1410 if (!isa<IntrinsicInst>(CurrentI) && isReadClobber(KillingLoc, CurrentI))
1411 return std::nullopt;
1414 if (
any_of(Current->
uses(), [
this, &KillingLoc, StartAccess](
Use &U) {
1415 if (auto *UseOrDef = dyn_cast<MemoryUseOrDef>(U.getUser()))
1416 return !MSSA.dominates(StartAccess, UseOrDef) &&
1417 isReadClobber(KillingLoc, UseOrDef->getMemoryInst());
1421 return std::nullopt;
1426 CurrentLoc = getLocForWrite(CurrentI);
1427 if (!CurrentLoc || !isRemovable(CurrentI)) {
1428 CanOptimize =
false;
1435 if (!isGuaranteedLoopIndependent(CurrentI, KillingI, *CurrentLoc)) {
1437 CanOptimize =
false;
1445 if (!isMemTerminator(*CurrentLoc, CurrentI, KillingI)) {
1446 CanOptimize =
false;
1450 int64_t KillingOffset = 0;
1451 int64_t DeadOffset = 0;
1452 auto OR = isOverwrite(KillingI, CurrentI, KillingLoc, *CurrentLoc,
1453 KillingOffset, DeadOffset);
1459 (OR == OW_Complete || OR == OW_MaybePartial))
1465 CanOptimize =
false;
1470 if (OR == OW_Unknown || OR == OW_None)
1472 else if (OR == OW_MaybePartial) {
1477 if (PartialLimit <= 1) {
1478 WalkerStepLimit -= 1;
1479 LLVM_DEBUG(
dbgs() <<
" ... reached partial limit ... continue with next access\n");
1496 Instruction *MaybeDeadI = cast<MemoryDef>(MaybeDeadAccess)->getMemoryInst();
1497 LLVM_DEBUG(
dbgs() <<
" Checking for reads of " << *MaybeDeadAccess <<
" ("
1498 << *MaybeDeadI <<
")\n");
1503 WorkList.
insert(cast<MemoryAccess>(
U.getUser()));
1505 PushMemUses(MaybeDeadAccess);
1508 for (
unsigned I = 0;
I < WorkList.
size();
I++) {
1513 if (ScanLimit < (WorkList.
size() -
I)) {
1515 return std::nullopt;
1518 NumDomMemDefChecks++;
1520 if (isa<MemoryPhi>(UseAccess)) {
1525 LLVM_DEBUG(
dbgs() <<
" ... skipping, dominated by killing block\n");
1529 PushMemUses(UseAccess);
1533 Instruction *UseInst = cast<MemoryUseOrDef>(UseAccess)->getMemoryInst();
1539 LLVM_DEBUG(
dbgs() <<
" ... skipping, dominated by killing def\n");
1545 if (isMemTerminator(MaybeDeadLoc, MaybeDeadI, UseInst)) {
1548 <<
" ... skipping, memterminator invalidates following accesses\n");
1552 if (isNoopIntrinsic(cast<MemoryUseOrDef>(UseAccess)->getMemoryInst())) {
1554 PushMemUses(UseAccess);
1558 if (UseInst->
mayThrow() && !isInvisibleToCallerOnUnwind(KillingUndObj)) {
1560 return std::nullopt;
1565 if (isReadClobber(MaybeDeadLoc, UseInst)) {
1567 return std::nullopt;
1573 if (MaybeDeadAccess == UseAccess &&
1574 !isGuaranteedLoopInvariant(MaybeDeadLoc.
Ptr)) {
1575 LLVM_DEBUG(
dbgs() <<
" ... found not loop invariant self access\n");
1576 return std::nullopt;
1582 if (KillingDef == UseAccess || MaybeDeadAccess == UseAccess) {
1597 if (
MemoryDef *UseDef = dyn_cast<MemoryDef>(UseAccess)) {
1598 if (isCompleteOverwrite(MaybeDeadLoc, MaybeDeadI, UseInst)) {
1600 if (PostOrderNumbers.
find(MaybeKillingBlock)->second <
1601 PostOrderNumbers.
find(MaybeDeadAccess->
getBlock())->second) {
1602 if (!isInvisibleToCallerAfterRet(KillingUndObj)) {
1604 <<
" ... found killing def " << *UseInst <<
"\n");
1605 KillingDefs.
insert(UseInst);
1609 <<
" ... found preceeding def " << *UseInst <<
"\n");
1610 return std::nullopt;
1613 PushMemUses(UseDef);
1620 if (!isInvisibleToCallerAfterRet(KillingUndObj)) {
1623 KillingBlocks.
insert(KD->getParent());
1625 "Expected at least a single killing block");
1639 if (!AnyUnreachableExit)
1640 return std::nullopt;
1644 CommonPred =
nullptr;
1648 if (KillingBlocks.
count(CommonPred))
1649 return {MaybeDeadAccess};
1655 WorkList.
insert(CommonPred);
1658 if (!isa<UnreachableInst>(
R->getTerminator()))
1665 for (
unsigned I = 0;
I < WorkList.
size();
I++) {
1668 if (KillingBlocks.
count(Current))
1670 if (Current == MaybeDeadAccess->
getBlock())
1671 return std::nullopt;
1682 return std::nullopt;
1689 return {MaybeDeadAccess};
1699 while (!NowDeadInsts.
empty()) {
1709 if (
MemoryDef *MD = dyn_cast<MemoryDef>(MA)) {
1711 if (
auto *SI = dyn_cast<StoreInst>(MD->getMemoryInst())) {
1712 if (
SI->getValueOperand()->getType()->isPointerTy()) {
1714 if (CapturedBeforeReturn.
erase(UO))
1715 ShouldIterateEndOfFunctionDSE =
true;
1716 InvisibleToCallerAfterRet.
erase(UO);
1721 Updater.removeMemoryAccess(MA);
1725 if (
I != IOLs.
end())
1726 I->second.erase(DeadInst);
1729 if (
Instruction *OpI = dyn_cast<Instruction>(O)) {
1745 const Value *KillingUndObj) {
1749 if (KillingUndObj && isInvisibleToCallerOnUnwind(KillingUndObj))
1754 return !ThrowingBlocks.
empty();
1765 if (DeadI->
mayThrow() && !isInvisibleToCallerOnUnwind(KillingUndObj))
1771 if (
auto *LI = dyn_cast<LoadInst>(DeadI))
1773 if (
auto *SI = dyn_cast<StoreInst>(DeadI))
1775 if (
auto *ARMW = dyn_cast<AtomicRMWInst>(DeadI))
1777 if (
auto *CmpXchg = dyn_cast<AtomicCmpXchgInst>(DeadI))
1787 bool eliminateDeadWritesAtEndOfFunction() {
1788 bool MadeChange =
false;
1791 <<
"Trying to eliminate MemoryDefs at the end of the function\n");
1793 ShouldIterateEndOfFunctionDSE =
false;
1799 auto DefLoc = getLocForWrite(DefI);
1800 if (!DefLoc || !isRemovable(DefI))
1809 if (!isInvisibleToCallerAfterRet(UO))
1812 if (isWriteAtEndOfFunction(Def)) {
1814 LLVM_DEBUG(
dbgs() <<
" ... MemoryDef is not accessed until the end "
1815 "of the function\n");
1821 }
while (ShouldIterateEndOfFunctionDSE);
1829 MemSetInst *MemSet = dyn_cast<MemSetInst>(DefI);
1834 if (!StoredConstant || !StoredConstant->
isNullValue())
1837 if (!isRemovable(DefI))
1841 if (
F.hasFnAttribute(Attribute::SanitizeMemory) ||
1842 F.hasFnAttribute(Attribute::SanitizeAddress) ||
1843 F.hasFnAttribute(Attribute::SanitizeHWAddress) ||
1844 F.getName() ==
"calloc")
1846 auto *
Malloc =
const_cast<CallInst *
>(dyn_cast<CallInst>(DefUO));
1849 auto *InnerCallee =
Malloc->getCalledFunction();
1853 if (!TLI.
getLibFunc(*InnerCallee, Func) || !TLI.
has(Func) ||
1854 Func != LibFunc_malloc)
1864 auto *MallocBB =
Malloc->getParent(),
1865 *MemsetBB = Memset->getParent();
1866 if (MallocBB == MemsetBB)
1868 auto *
Ptr = Memset->getArgOperand(0);
1869 auto *TI = MallocBB->getTerminator();
1875 if (Pred != ICmpInst::ICMP_EQ || MemsetBB != FalseBB)
1882 if (!shouldCreateCalloc(
Malloc, MemSet) ||
1887 Type *SizeTTy =
Malloc->getArgOperand(0)->getType();
1889 Malloc->getArgOperand(0), IRB, TLI);
1894 Updater.createMemoryAccessAfter(cast<Instruction>(Calloc),
nullptr,
1896 auto *NewAccessMD = cast<MemoryDef>(NewAccess);
1897 Updater.insertDef(NewAccessMD,
true);
1898 Updater.removeMemoryAccess(
Malloc);
1899 Malloc->replaceAllUsesWith(Calloc);
1900 Malloc->eraseFromParent();
1909 MemSetInst *MemSet = dyn_cast<MemSetInst>(DefI);
1910 Constant *StoredConstant =
nullptr;
1912 StoredConstant = dyn_cast<Constant>(
Store->getOperand(0));
1914 StoredConstant = dyn_cast<Constant>(MemSet->
getValue());
1918 if (!isRemovable(DefI))
1921 if (StoredConstant) {
1926 if (InitC && InitC == StoredConstant)
1934 if (
auto *LoadI = dyn_cast<LoadInst>(
Store->getOperand(0))) {
1935 if (LoadI->getPointerOperand() ==
Store->getOperand(1)) {
1939 if (LoadAccess ==
Def->getDefiningAccess())
1954 for (
unsigned I = 1;
I < ToCheck.
size(); ++
I) {
1955 Current = ToCheck[
I];
1956 if (
auto PhiAccess = dyn_cast<MemoryPhi>(Current)) {
1958 for (
auto &
Use : PhiAccess->incoming_values())
1959 ToCheck.
insert(cast<MemoryAccess>(&
Use));
1965 assert(isa<MemoryDef>(Current) &&
1966 "Only MemoryDefs should reach here.");
1971 if (LoadAccess != Current)
1982 bool Changed =
false;
1983 for (
auto OI : IOL) {
1986 assert(isRemovable(DeadI) &&
"Expect only removable instruction");
1989 int64_t DeadStart = 0;
2003 bool eliminateRedundantStoresOfExistingValues() {
2004 bool MadeChange =
false;
2005 LLVM_DEBUG(
dbgs() <<
"Trying to eliminate MemoryDefs that write the "
2006 "already existing value\n");
2007 for (
auto *Def : MemDefs) {
2012 auto MaybeDefLoc = getLocForWrite(DefInst);
2013 if (!MaybeDefLoc || !isRemovable(DefInst))
2020 if (
Def->isOptimized())
2021 UpperDef = dyn_cast<MemoryDef>(
Def->getOptimized());
2023 UpperDef = dyn_cast<MemoryDef>(
Def->getDefiningAccess());
2028 auto IsRedundantStore = [&]() {
2031 if (
auto *MemSetI = dyn_cast<MemSetInst>(UpperInst)) {
2032 if (
auto *SI = dyn_cast<StoreInst>(DefInst)) {
2035 int64_t InstWriteOffset = 0;
2036 int64_t DepWriteOffset = 0;
2037 auto OR = isOverwrite(UpperInst, DefInst, UpperLoc, *MaybeDefLoc,
2038 InstWriteOffset, DepWriteOffset);
2040 return StoredByte && StoredByte == MemSetI->getOperand(1) &&
2047 if (!IsRedundantStore() || isReadClobber(*MaybeDefLoc, DefInst))
2049 LLVM_DEBUG(
dbgs() <<
"DSE: Remove No-Op Store:\n DEAD: " << *DefInst
2052 NumRedundantStores++;
2064 bool MadeChange =
false;
2066 DSEState State(
F, AA, MSSA, DT, PDT, AC, TLI, LI);
2068 for (
unsigned I = 0;
I < State.MemDefs.size();
I++) {
2070 if (State.SkipStores.count(KillingDef))
2074 std::optional<MemoryLocation> MaybeKillingLoc;
2075 if (State.isMemTerminatorInst(KillingI)) {
2076 if (
auto KillingLoc = State.getLocForTerminator(KillingI))
2077 MaybeKillingLoc = KillingLoc->first;
2079 MaybeKillingLoc = State.getLocForWrite(KillingI);
2082 if (!MaybeKillingLoc) {
2083 LLVM_DEBUG(
dbgs() <<
"Failed to find analyzable write location for "
2084 << *KillingI <<
"\n");
2088 assert(KillingLoc.
Ptr &&
"KillingLoc should not be null");
2091 << *KillingDef <<
" (" << *KillingI <<
")\n");
2100 bool Shortend =
false;
2101 bool IsMemTerm = State.isMemTerminatorInst(KillingI);
2103 for (
unsigned I = 0;
I < ToCheck.
size();
I++) {
2105 if (State.SkipStores.count(Current))
2108 std::optional<MemoryAccess *> MaybeDeadAccess = State.getDomMemoryDef(
2109 KillingDef, Current, KillingLoc, KillingUndObj, ScanLimit,
2110 WalkerStepLimit, IsMemTerm, PartialLimit);
2112 if (!MaybeDeadAccess) {
2118 LLVM_DEBUG(
dbgs() <<
" Checking if we can kill " << *DeadAccess);
2119 if (isa<MemoryPhi>(DeadAccess)) {
2120 LLVM_DEBUG(
dbgs() <<
"\n ... adding incoming values to worklist\n");
2121 for (
Value *V : cast<MemoryPhi>(DeadAccess)->incoming_values()) {
2129 if (State.PostOrderNumbers[IncomingBlock] >
2130 State.PostOrderNumbers[PhiBlock])
2131 ToCheck.
insert(IncomingAccess);
2135 auto *DeadDefAccess = cast<MemoryDef>(DeadAccess);
2136 Instruction *DeadI = DeadDefAccess->getMemoryInst();
2138 ToCheck.
insert(DeadDefAccess->getDefiningAccess());
2139 NumGetDomMemoryDefPassed++;
2148 if (KillingUndObj != DeadUndObj)
2150 LLVM_DEBUG(
dbgs() <<
"DSE: Remove Dead Store:\n DEAD: " << *DeadI
2151 <<
"\n KILLER: " << *KillingI <<
'\n');
2152 State.deleteDeadInstruction(DeadI);
2157 int64_t KillingOffset = 0;
2158 int64_t DeadOffset = 0;
2159 OverwriteResult
OR = State.isOverwrite(
2160 KillingI, DeadI, KillingLoc, DeadLoc, KillingOffset, DeadOffset);
2161 if (OR == OW_MaybePartial) {
2162 auto Iter = State.IOLs.insert(
2163 std::make_pair<BasicBlock *, InstOverlapIntervalsTy>(
2165 auto &IOL = Iter.first->second;
2167 DeadOffset, DeadI, IOL);
2171 auto *DeadSI = dyn_cast<StoreInst>(DeadI);
2172 auto *KillingSI = dyn_cast<StoreInst>(KillingI);
2176 if (DeadSI && KillingSI && DT.
dominates(DeadSI, KillingSI)) {
2178 KillingSI, DeadSI, KillingOffset, DeadOffset, State.DL,
2179 State.BatchAA, &DT)) {
2182 DeadSI->setOperand(0, Merged);
2183 ++NumModifiedStores;
2189 State.deleteDeadInstruction(KillingSI);
2190 auto I = State.IOLs.find(DeadSI->getParent());
2191 if (
I != State.IOLs.end())
2192 I->second.erase(DeadSI);
2198 if (OR == OW_Complete) {
2199 LLVM_DEBUG(
dbgs() <<
"DSE: Remove Dead Store:\n DEAD: " << *DeadI
2200 <<
"\n KILLER: " << *KillingI <<
'\n');
2201 State.deleteDeadInstruction(DeadI);
2209 if (!Shortend && State.storeIsNoop(KillingDef, KillingUndObj)) {
2210 LLVM_DEBUG(
dbgs() <<
"DSE: Remove No-Op Store:\n DEAD: " << *KillingI
2212 State.deleteDeadInstruction(KillingI);
2213 NumRedundantStores++;
2219 if (!Shortend && State.tryFoldIntoCalloc(KillingDef, KillingUndObj)) {
2220 LLVM_DEBUG(
dbgs() <<
"DSE: Remove memset after forming calloc:\n"
2221 <<
" DEAD: " << *KillingI <<
'\n');
2222 State.deleteDeadInstruction(KillingI);
2229 for (
auto &KV : State.IOLs)
2230 MadeChange |= State.removePartiallyOverlappedStores(KV.second);
2232 MadeChange |= State.eliminateRedundantStoresOfExistingValues();
2233 MadeChange |= State.eliminateDeadWritesAtEndOfFunction();
2250 bool Changed = eliminateDeadStores(
F, AA, MSSA, DT, PDT, AC, TLI, LI);
2252#ifdef LLVM_ENABLE_STATS
2255 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.
Select target instructions out of generic instructions
static void deleteDeadInstruction(Instruction *I)
This file implements a map that provides insertion order iteration.
This file provides utility analysis objects describing memory locations.
This file exposes an interface to building/using memory SSA to walk memory instructions using a use/d...
Module.h This file contains the declarations for the Module class.
Contains a collection of routines for determining if a given instruction is guaranteed to execute if ...
This header defines various interfaces for pass management in LLVM.
This file builds on the ADT/GraphTraits.h file to build a generic graph post order iterator.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file implements a set that has insertion order iteration characteristics.
This file defines the SmallPtrSet class.
This file defines the SmallVector class.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
A manager for alias analyses.
Class for arbitrary precision integers.
APInt zext(unsigned width) const
Zero extend to a new width.
static APInt getBitsSet(unsigned numBits, unsigned loBit, unsigned hiBit)
Get a value with a block of bits set.
unsigned getBitWidth() const
Return the number of bits in the APInt.
The possible results of an alias query.
@ NoAlias
The two locations do not alias at all.
@ PartialAlias
The two locations alias, but only due to a partial overlap.
@ MustAlias
The two locations precisely alias each other.
constexpr int32_t getOffset() const
constexpr bool hasOffset() const
A container for analyses that lazily runs them and caches their results.
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
This class represents an incoming formal argument to a Function.
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.
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.
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.
static IntegerType * getInt8Ty(LLVMContext &C)
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)
NodeAddr< DefNode * > Def
NodeAddr< FuncNode * > Func
This is an optimization pass for GlobalISel generic memory operations.
auto drop_begin(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the first N elements excluded.
Constant * getInitialValueOfAllocation(const Value *V, const TargetLibraryInfo *TLI, Type *Ty)
If this is a call to an allocation function that initializes memory to a fixed value,...
bool isStrongerThanMonotonic(AtomicOrdering AO)
bool isAligned(Align Lhs, uint64_t SizeInBytes)
Checks that SizeInBytes is a multiple of the alignment.
void salvageDebugInfo(const MachineRegisterInfo &MRI, MachineInstr &MI)
Assuming the instruction MI is going to be deleted, attempt to salvage debug users of MI by writing t...
Value * emitCalloc(Value *Num, Value *Size, IRBuilderBase &B, const TargetLibraryInfo &TLI)
Emit a call to the calloc function.
Value * GetPointerBaseWithConstantOffset(Value *Ptr, int64_t &Offset, const DataLayout &DL, bool AllowNonInbounds=true)
Analyze the specified pointer to see if it can be expressed as a base pointer plus a constant offset.
const Value * getUnderlyingObject(const Value *V, unsigned MaxLookup=6)
This method strips off any GEP address adjustments and pointer casts from the specified value,...
iterator_range< po_iterator< T > > post_order(const T &G)
bool isNoAliasCall(const Value *V)
Return true if this pointer is returned by a noalias function.
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
bool isInstructionTriviallyDead(Instruction *I, const TargetLibraryInfo *TLI=nullptr)
Return true if the result produced by the instruction is not used, and the instruction will return.
bool getObjectSize(const Value *Ptr, uint64_t &Size, const DataLayout &DL, const TargetLibraryInfo *TLI, ObjectSizeOpts Opts={})
Compute the size of the object pointed by Ptr.
auto reverse(ContainerTy &&C)
bool isModSet(const ModRefInfo MRI)
bool PointerMayBeCaptured(const Value *V, bool ReturnCaptures, bool StoreCaptures, unsigned MaxUsesToExplore=0)
PointerMayBeCaptured - Return true if this pointer value may be captured by the enclosing function (w...
bool NullPointerIsDefined(const Function *F, unsigned AS=0)
Check whether null pointer dereferencing is considered undefined behavior for a given function or an ...
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
bool AreStatisticsEnabled()
Check if statistics are enabled.
bool isNotVisibleOnUnwind(const Value *Object, bool &RequiresNoCaptureBeforeUnwind)
Return true if Object memory is not visible after an unwind, in the sense that program semantics cann...
uint64_t offsetToAlignment(uint64_t Value, Align Alignment)
Returns the offset to the next integer (mod 2**64) that is greater than or equal to Value and is a mu...
bool salvageKnowledge(Instruction *I, AssumptionCache *AC=nullptr, DominatorTree *DT=nullptr)
Calls BuildAssumeFromInst and if the resulting llvm.assume is valid insert if before I.
Value * getFreedOperand(const CallBase *CB, const TargetLibraryInfo *TLI)
If this if a call to a free function, return the freed operand.
Value * isBytewiseValue(Value *V, const DataLayout &DL)
If the specified value can be set by repeating the same byte in memory, return the i8 value that it i...
auto predecessors(const MachineBasicBlock *BB)
bool mayContainIrreducibleControl(const Function &F, const LoopInfo *LI)
bool isIdentifiedObject(const Value *V)
Return true if this pointer refers to a distinct and identifiable object.
bool isStrongerThan(AtomicOrdering AO, AtomicOrdering Other)
Returns true if ao is stronger than other as defined by the AtomicOrdering lattice,...
bool isRefSet(const ModRefInfo MRI)
This struct is a compact representation of a valid (non-zero power of two) alignment.
uint64_t value() const
This is a hole in the type system and should not be abused.
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.