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_declare:
744 case Intrinsic::dbg_label:
745 case Intrinsic::dbg_value:
755bool canSkipDef(
MemoryDef *
D,
bool DefVisibleToCaller) {
759 if (
auto *CB = dyn_cast<CallBase>(DI))
760 if (CB->onlyAccessesInaccessibleMemory())
765 if (DI->
mayThrow() && !DefVisibleToCaller)
773 if (isa<FenceInst>(DI))
777 if (isNoopIntrinsic(DI))
806 bool ContainsIrreducibleLoops;
832 bool AnyUnreachableExit;
837 bool ShouldIterateEndOfFunctionDSE;
840 DSEState(
const DSEState &) =
delete;
841 DSEState &operator=(
const DSEState &) =
delete;
846 :
F(
F), AA(AA), EI(DT, LI, EphValues), BatchAA(AA, &EI), MSSA(MSSA),
847 DT(DT), PDT(PDT), TLI(TLI),
DL(
F.
getParent()->getDataLayout()), LI(LI) {
852 PostOrderNumbers[BB] = PO++;
855 if (
I.mayThrow() && !MA)
856 ThrowingBlocks.
insert(
I.getParent());
858 auto *MD = dyn_cast_or_null<MemoryDef>(MA);
860 (getLocForWrite(&
I) || isMemTerminatorInst(&
I)))
868 if (AI.hasPassPointeeByValueCopyAttr())
869 InvisibleToCallerAfterRet.
insert({&AI,
true});
875 return isa<UnreachableInst>(E->getTerminator());
883 if (
auto *CB = dyn_cast<CallBase>(
I)) {
886 (F == LibFunc_memset_chk || F == LibFunc_memcpy_chk)) {
895 if (
const auto *Len = dyn_cast<ConstantInt>(CB->getArgOperand(2)))
910 OverwriteResult isOverwrite(
const Instruction *KillingI,
914 int64_t &KillingOff, int64_t &DeadOff) {
918 if (!isGuaranteedLoopIndependent(DeadI, KillingI, DeadLoc))
922 strengthenLocationSize(KillingI, KillingLoc.
Size);
930 if (DeadUndObj == KillingUndObj && KillingLocSize.
isPrecise()) {
933 KillingUndObjSize == KillingLocSize.
getValue())
942 const auto *KillingMemI = dyn_cast<MemIntrinsic>(KillingI);
943 const auto *DeadMemI = dyn_cast<MemIntrinsic>(DeadI);
944 if (KillingMemI && DeadMemI) {
945 const Value *KillingV = KillingMemI->getLength();
946 const Value *DeadV = DeadMemI->getLength();
947 if (KillingV == DeadV && BatchAA.
isMustAlias(DeadLoc, KillingLoc))
966 if (KillingSize >= DeadSize)
973 if (Off >= 0 && (
uint64_t)Off + DeadSize <= KillingSize)
979 if (DeadUndObj != KillingUndObj) {
995 const Value *DeadBasePtr =
997 const Value *KillingBasePtr =
1002 if (DeadBasePtr != KillingBasePtr)
1020 if (DeadOff >= KillingOff) {
1023 if (
uint64_t(DeadOff - KillingOff) + DeadSize <= KillingSize)
1027 else if ((
uint64_t)(DeadOff - KillingOff) < KillingSize)
1028 return OW_MaybePartial;
1032 else if ((
uint64_t)(KillingOff - DeadOff) < DeadSize) {
1033 return OW_MaybePartial;
1040 bool isInvisibleToCallerAfterRet(
const Value *V) {
1041 if (isa<AllocaInst>(V))
1043 auto I = InvisibleToCallerAfterRet.
insert({
V,
false});
1045 if (!isInvisibleToCallerOnUnwind(V)) {
1046 I.first->second =
false;
1051 return I.first->second;
1054 bool isInvisibleToCallerOnUnwind(
const Value *V) {
1055 bool RequiresNoCaptureBeforeUnwind;
1058 if (!RequiresNoCaptureBeforeUnwind)
1061 auto I = CapturedBeforeReturn.
insert({
V,
true});
1068 return !
I.first->second;
1071 std::optional<MemoryLocation> getLocForWrite(
Instruction *
I)
const {
1072 if (!
I->mayWriteToMemory())
1073 return std::nullopt;
1075 if (
auto *CB = dyn_cast<CallBase>(
I))
1084 assert(getLocForWrite(
I) &&
"Must have analyzable write");
1088 return SI->isUnordered();
1090 if (
auto *CB = dyn_cast<CallBase>(
I)) {
1092 if (
auto *
MI = dyn_cast<MemIntrinsic>(CB))
1093 return !
MI->isVolatile();
1097 if (CB->isLifetimeStartOrEnd())
1100 return CB->use_empty() && CB->willReturn() && CB->doesNotThrow() &&
1101 !CB->isTerminator();
1117 if (
auto *CB = dyn_cast<CallBase>(UseInst))
1118 if (CB->onlyAccessesInaccessibleMemory())
1121 int64_t InstWriteOffset, DepWriteOffset;
1122 if (
auto CC = getLocForWrite(UseInst))
1123 return isOverwrite(UseInst, DefInst, *
CC, DefLoc, InstWriteOffset,
1124 DepWriteOffset) == OW_Complete;
1129 bool isWriteAtEndOfFunction(
MemoryDef *Def) {
1131 << *
Def->getMemoryInst()
1132 <<
") is at the end the function \n");
1134 auto MaybeLoc = getLocForWrite(
Def->getMemoryInst());
1136 LLVM_DEBUG(
dbgs() <<
" ... could not get location for write.\n");
1142 auto PushMemUses = [&WorkList, &Visited](
MemoryAccess *Acc) {
1143 if (!Visited.
insert(Acc).second)
1146 WorkList.
push_back(cast<MemoryAccess>(
U.getUser()));
1149 for (
unsigned I = 0;
I < WorkList.
size();
I++) {
1156 if (isa<MemoryPhi>(UseAccess)) {
1160 if (!isGuaranteedLoopInvariant(MaybeLoc->Ptr))
1163 PushMemUses(cast<MemoryPhi>(UseAccess));
1168 Instruction *UseInst = cast<MemoryUseOrDef>(UseAccess)->getMemoryInst();
1169 if (isReadClobber(*MaybeLoc, UseInst)) {
1170 LLVM_DEBUG(
dbgs() <<
" ... hit read clobber " << *UseInst <<
".\n");
1174 if (
MemoryDef *UseDef = dyn_cast<MemoryDef>(UseAccess))
1175 PushMemUses(UseDef);
1183 std::optional<std::pair<MemoryLocation, bool>>
1191 if (
auto *CB = dyn_cast<CallBase>(
I)) {
1196 return std::nullopt;
1202 auto *CB = dyn_cast<CallBase>(
I);
1203 return CB && (CB->getIntrinsicID() == Intrinsic::lifetime_end ||
1211 std::optional<std::pair<MemoryLocation, bool>> MaybeTermLoc =
1212 getLocForTerminator(MaybeTerm);
1223 auto TermLoc = MaybeTermLoc->first;
1224 if (MaybeTermLoc->second) {
1228 int64_t InstWriteOffset = 0;
1229 int64_t DepWriteOffset = 0;
1230 return isOverwrite(MaybeTerm, AccessI, TermLoc, Loc, InstWriteOffset,
1231 DepWriteOffset) == OW_Complete;
1236 if (isNoopIntrinsic(UseInst))
1241 if (
auto SI = dyn_cast<StoreInst>(UseInst))
1247 if (
auto *CB = dyn_cast<CallBase>(UseInst))
1248 if (CB->onlyAccessesInaccessibleMemory())
1259 bool isGuaranteedLoopIndependent(
const Instruction *Current,
1269 if (!ContainsIrreducibleLoops && CurrentLI &&
1273 return isGuaranteedLoopInvariant(CurrentLoc.
Ptr);
1279 bool isGuaranteedLoopInvariant(
const Value *
Ptr) {
1280 Ptr =
Ptr->stripPointerCasts();
1281 if (
auto *
GEP = dyn_cast<GEPOperator>(
Ptr))
1282 if (
GEP->hasAllConstantIndices())
1283 Ptr =
GEP->getPointerOperand()->stripPointerCasts();
1285 if (
auto *
I = dyn_cast<Instruction>(
Ptr)) {
1286 return I->getParent()->isEntryBlock() ||
1287 (!ContainsIrreducibleLoops && !LI.
getLoopFor(
I->getParent()));
1298 std::optional<MemoryAccess *>
1301 unsigned &ScanLimit,
unsigned &WalkerStepLimit,
1302 bool IsMemTerm,
unsigned &PartialLimit) {
1303 if (ScanLimit == 0 || WalkerStepLimit == 0) {
1305 return std::nullopt;
1322 std::optional<MemoryLocation> CurrentLoc;
1323 for (;; Current = cast<MemoryDef>(Current)->getDefiningAccess()) {
1325 dbgs() <<
" visiting " << *Current;
1327 dbgs() <<
" (" << *cast<MemoryUseOrDef>(Current)->getMemoryInst()
1338 return std::nullopt;
1346 if (WalkerStepLimit <= StepCost) {
1348 return std::nullopt;
1350 WalkerStepLimit -= StepCost;
1354 if (isa<MemoryPhi>(Current)) {
1361 MemoryDef *CurrentDef = cast<MemoryDef>(Current);
1364 if (canSkipDef(CurrentDef, !isInvisibleToCallerOnUnwind(KillingUndObj))) {
1365 CanOptimize =
false;
1371 if (mayThrowBetween(KillingI, CurrentI, KillingUndObj)) {
1373 return std::nullopt;
1378 if (isDSEBarrier(KillingUndObj, CurrentI)) {
1380 return std::nullopt;
1387 if (!isa<IntrinsicInst>(CurrentI) && isReadClobber(KillingLoc, CurrentI))
1388 return std::nullopt;
1391 if (
any_of(Current->
uses(), [
this, &KillingLoc, StartAccess](
Use &U) {
1392 if (auto *UseOrDef = dyn_cast<MemoryUseOrDef>(U.getUser()))
1393 return !MSSA.dominates(StartAccess, UseOrDef) &&
1394 isReadClobber(KillingLoc, UseOrDef->getMemoryInst());
1398 return std::nullopt;
1403 CurrentLoc = getLocForWrite(CurrentI);
1404 if (!CurrentLoc || !isRemovable(CurrentI)) {
1405 CanOptimize =
false;
1412 if (!isGuaranteedLoopIndependent(CurrentI, KillingI, *CurrentLoc)) {
1414 CanOptimize =
false;
1422 if (!isMemTerminator(*CurrentLoc, CurrentI, KillingI)) {
1423 CanOptimize =
false;
1427 int64_t KillingOffset = 0;
1428 int64_t DeadOffset = 0;
1429 auto OR = isOverwrite(KillingI, CurrentI, KillingLoc, *CurrentLoc,
1430 KillingOffset, DeadOffset);
1436 (OR == OW_Complete || OR == OW_MaybePartial))
1442 CanOptimize =
false;
1447 if (OR == OW_Unknown || OR == OW_None)
1449 else if (OR == OW_MaybePartial) {
1454 if (PartialLimit <= 1) {
1455 WalkerStepLimit -= 1;
1456 LLVM_DEBUG(
dbgs() <<
" ... reached partial limit ... continue with next access\n");
1473 Instruction *MaybeDeadI = cast<MemoryDef>(MaybeDeadAccess)->getMemoryInst();
1474 LLVM_DEBUG(
dbgs() <<
" Checking for reads of " << *MaybeDeadAccess <<
" ("
1475 << *MaybeDeadI <<
")\n");
1480 WorkList.
insert(cast<MemoryAccess>(
U.getUser()));
1482 PushMemUses(MaybeDeadAccess);
1485 for (
unsigned I = 0;
I < WorkList.
size();
I++) {
1490 if (ScanLimit < (WorkList.
size() -
I)) {
1492 return std::nullopt;
1495 NumDomMemDefChecks++;
1497 if (isa<MemoryPhi>(UseAccess)) {
1502 LLVM_DEBUG(
dbgs() <<
" ... skipping, dominated by killing block\n");
1506 PushMemUses(UseAccess);
1510 Instruction *UseInst = cast<MemoryUseOrDef>(UseAccess)->getMemoryInst();
1516 LLVM_DEBUG(
dbgs() <<
" ... skipping, dominated by killing def\n");
1522 if (isMemTerminator(MaybeDeadLoc, MaybeDeadI, UseInst)) {
1525 <<
" ... skipping, memterminator invalidates following accesses\n");
1529 if (isNoopIntrinsic(cast<MemoryUseOrDef>(UseAccess)->getMemoryInst())) {
1531 PushMemUses(UseAccess);
1535 if (UseInst->
mayThrow() && !isInvisibleToCallerOnUnwind(KillingUndObj)) {
1537 return std::nullopt;
1542 if (isReadClobber(MaybeDeadLoc, UseInst)) {
1544 return std::nullopt;
1550 if (MaybeDeadAccess == UseAccess &&
1551 !isGuaranteedLoopInvariant(MaybeDeadLoc.
Ptr)) {
1552 LLVM_DEBUG(
dbgs() <<
" ... found not loop invariant self access\n");
1553 return std::nullopt;
1559 if (KillingDef == UseAccess || MaybeDeadAccess == UseAccess) {
1574 if (
MemoryDef *UseDef = dyn_cast<MemoryDef>(UseAccess)) {
1575 if (isCompleteOverwrite(MaybeDeadLoc, MaybeDeadI, UseInst)) {
1577 if (PostOrderNumbers.
find(MaybeKillingBlock)->second <
1578 PostOrderNumbers.
find(MaybeDeadAccess->
getBlock())->second) {
1579 if (!isInvisibleToCallerAfterRet(KillingUndObj)) {
1581 <<
" ... found killing def " << *UseInst <<
"\n");
1582 KillingDefs.
insert(UseInst);
1586 <<
" ... found preceeding def " << *UseInst <<
"\n");
1587 return std::nullopt;
1590 PushMemUses(UseDef);
1597 if (!isInvisibleToCallerAfterRet(KillingUndObj)) {
1600 KillingBlocks.
insert(KD->getParent());
1602 "Expected at least a single killing block");
1616 if (!AnyUnreachableExit)
1617 return std::nullopt;
1621 CommonPred =
nullptr;
1625 if (KillingBlocks.
count(CommonPred))
1626 return {MaybeDeadAccess};
1632 WorkList.
insert(CommonPred);
1635 if (!isa<UnreachableInst>(
R->getTerminator()))
1642 for (
unsigned I = 0;
I < WorkList.
size();
I++) {
1645 if (KillingBlocks.
count(Current))
1647 if (Current == MaybeDeadAccess->
getBlock())
1648 return std::nullopt;
1659 return std::nullopt;
1666 return {MaybeDeadAccess};
1676 while (!NowDeadInsts.
empty()) {
1686 if (
MemoryDef *MD = dyn_cast<MemoryDef>(MA)) {
1688 if (
auto *SI = dyn_cast<StoreInst>(MD->getMemoryInst())) {
1689 if (
SI->getValueOperand()->getType()->isPointerTy()) {
1691 if (CapturedBeforeReturn.
erase(UO))
1692 ShouldIterateEndOfFunctionDSE =
true;
1693 InvisibleToCallerAfterRet.
erase(UO);
1698 Updater.removeMemoryAccess(MA);
1702 if (
I != IOLs.
end())
1703 I->second.erase(DeadInst);
1706 if (
Instruction *OpI = dyn_cast<Instruction>(O)) {
1722 const Value *KillingUndObj) {
1726 if (KillingUndObj && isInvisibleToCallerOnUnwind(KillingUndObj))
1731 return !ThrowingBlocks.
empty();
1742 if (DeadI->
mayThrow() && !isInvisibleToCallerOnUnwind(KillingUndObj))
1748 if (
auto *LI = dyn_cast<LoadInst>(DeadI))
1750 if (
auto *SI = dyn_cast<StoreInst>(DeadI))
1752 if (
auto *ARMW = dyn_cast<AtomicRMWInst>(DeadI))
1754 if (
auto *CmpXchg = dyn_cast<AtomicCmpXchgInst>(DeadI))
1764 bool eliminateDeadWritesAtEndOfFunction() {
1765 bool MadeChange =
false;
1768 <<
"Trying to eliminate MemoryDefs at the end of the function\n");
1770 ShouldIterateEndOfFunctionDSE =
false;
1776 auto DefLoc = getLocForWrite(DefI);
1777 if (!DefLoc || !isRemovable(DefI))
1786 if (!isInvisibleToCallerAfterRet(UO))
1789 if (isWriteAtEndOfFunction(Def)) {
1791 LLVM_DEBUG(
dbgs() <<
" ... MemoryDef is not accessed until the end "
1792 "of the function\n");
1798 }
while (ShouldIterateEndOfFunctionDSE);
1806 MemSetInst *MemSet = dyn_cast<MemSetInst>(DefI);
1811 if (!StoredConstant || !StoredConstant->
isNullValue())
1814 if (!isRemovable(DefI))
1818 if (
F.hasFnAttribute(Attribute::SanitizeMemory) ||
1819 F.hasFnAttribute(Attribute::SanitizeAddress) ||
1820 F.hasFnAttribute(Attribute::SanitizeHWAddress) ||
1821 F.getName() ==
"calloc")
1823 auto *
Malloc =
const_cast<CallInst *
>(dyn_cast<CallInst>(DefUO));
1826 auto *InnerCallee =
Malloc->getCalledFunction();
1830 if (!TLI.
getLibFunc(*InnerCallee, Func) || !TLI.
has(Func) ||
1831 Func != LibFunc_malloc)
1837 auto *MallocBB =
Malloc->getParent(),
1838 *MemsetBB = Memset->getParent();
1839 if (MallocBB == MemsetBB)
1841 auto *
Ptr = Memset->getArgOperand(0);
1842 auto *TI = MallocBB->getTerminator();
1848 if (Pred != ICmpInst::ICMP_EQ || MemsetBB != FalseBB)
1855 if (!shouldCreateCalloc(
Malloc, MemSet) ||
1860 Type *SizeTTy =
Malloc->getArgOperand(0)->getType();
1862 Malloc->getArgOperand(0), IRB, TLI);
1867 cast<MemoryDef>(Updater.getMemorySSA()->getMemoryAccess(
Malloc));
1869 Updater.createMemoryAccessAfter(cast<Instruction>(Calloc), LastDef,
1871 auto *NewAccessMD = cast<MemoryDef>(NewAccess);
1872 Updater.insertDef(NewAccessMD,
true);
1873 Updater.removeMemoryAccess(
Malloc);
1874 Malloc->replaceAllUsesWith(Calloc);
1875 Malloc->eraseFromParent();
1884 MemSetInst *MemSet = dyn_cast<MemSetInst>(DefI);
1885 Constant *StoredConstant =
nullptr;
1887 StoredConstant = dyn_cast<Constant>(
Store->getOperand(0));
1889 StoredConstant = dyn_cast<Constant>(MemSet->
getValue());
1893 if (!isRemovable(DefI))
1896 if (StoredConstant) {
1901 if (InitC && InitC == StoredConstant)
1909 if (
auto *LoadI = dyn_cast<LoadInst>(
Store->getOperand(0))) {
1910 if (LoadI->getPointerOperand() ==
Store->getOperand(1)) {
1914 if (LoadAccess ==
Def->getDefiningAccess())
1929 for (
unsigned I = 1;
I < ToCheck.
size(); ++
I) {
1930 Current = ToCheck[
I];
1931 if (
auto PhiAccess = dyn_cast<MemoryPhi>(Current)) {
1933 for (
auto &
Use : PhiAccess->incoming_values())
1934 ToCheck.
insert(cast<MemoryAccess>(&
Use));
1940 assert(isa<MemoryDef>(Current) &&
1941 "Only MemoryDefs should reach here.");
1946 if (LoadAccess != Current)
1957 bool Changed =
false;
1958 for (
auto OI : IOL) {
1961 assert(isRemovable(DeadI) &&
"Expect only removable instruction");
1964 int64_t DeadStart = 0;
1978 bool eliminateRedundantStoresOfExistingValues() {
1979 bool MadeChange =
false;
1980 LLVM_DEBUG(
dbgs() <<
"Trying to eliminate MemoryDefs that write the "
1981 "already existing value\n");
1982 for (
auto *Def : MemDefs) {
1987 auto MaybeDefLoc = getLocForWrite(DefInst);
1988 if (!MaybeDefLoc || !isRemovable(DefInst))
1995 if (
Def->isOptimized())
1996 UpperDef = dyn_cast<MemoryDef>(
Def->getOptimized());
1998 UpperDef = dyn_cast<MemoryDef>(
Def->getDefiningAccess());
2003 auto IsRedundantStore = [&]() {
2006 if (
auto *MemSetI = dyn_cast<MemSetInst>(UpperInst)) {
2007 if (
auto *SI = dyn_cast<StoreInst>(DefInst)) {
2010 int64_t InstWriteOffset = 0;
2011 int64_t DepWriteOffset = 0;
2012 auto OR = isOverwrite(UpperInst, DefInst, UpperLoc, *MaybeDefLoc,
2013 InstWriteOffset, DepWriteOffset);
2015 return StoredByte && StoredByte == MemSetI->getOperand(1) &&
2022 if (!IsRedundantStore() || isReadClobber(*MaybeDefLoc, DefInst))
2024 LLVM_DEBUG(
dbgs() <<
"DSE: Remove No-Op Store:\n DEAD: " << *DefInst
2027 NumRedundantStores++;
2039 bool MadeChange =
false;
2042 DSEState State(
F, AA, MSSA, DT, PDT, AC, TLI, LI);
2044 for (
unsigned I = 0;
I < State.MemDefs.size();
I++) {
2046 if (State.SkipStores.count(KillingDef))
2050 std::optional<MemoryLocation> MaybeKillingLoc;
2051 if (State.isMemTerminatorInst(KillingI)) {
2052 if (
auto KillingLoc = State.getLocForTerminator(KillingI))
2053 MaybeKillingLoc = KillingLoc->first;
2055 MaybeKillingLoc = State.getLocForWrite(KillingI);
2058 if (!MaybeKillingLoc) {
2059 LLVM_DEBUG(
dbgs() <<
"Failed to find analyzable write location for "
2060 << *KillingI <<
"\n");
2064 assert(KillingLoc.
Ptr &&
"KillingLoc should not be null");
2067 << *KillingDef <<
" (" << *KillingI <<
")\n");
2076 bool Shortend =
false;
2077 bool IsMemTerm = State.isMemTerminatorInst(KillingI);
2079 for (
unsigned I = 0;
I < ToCheck.
size();
I++) {
2081 if (State.SkipStores.count(Current))
2084 std::optional<MemoryAccess *> MaybeDeadAccess = State.getDomMemoryDef(
2085 KillingDef, Current, KillingLoc, KillingUndObj, ScanLimit,
2086 WalkerStepLimit, IsMemTerm, PartialLimit);
2088 if (!MaybeDeadAccess) {
2094 LLVM_DEBUG(
dbgs() <<
" Checking if we can kill " << *DeadAccess);
2095 if (isa<MemoryPhi>(DeadAccess)) {
2096 LLVM_DEBUG(
dbgs() <<
"\n ... adding incoming values to worklist\n");
2097 for (
Value *V : cast<MemoryPhi>(DeadAccess)->incoming_values()) {
2105 if (State.PostOrderNumbers[IncomingBlock] >
2106 State.PostOrderNumbers[PhiBlock])
2107 ToCheck.
insert(IncomingAccess);
2111 auto *DeadDefAccess = cast<MemoryDef>(DeadAccess);
2112 Instruction *DeadI = DeadDefAccess->getMemoryInst();
2114 ToCheck.
insert(DeadDefAccess->getDefiningAccess());
2115 NumGetDomMemoryDefPassed++;
2124 if (KillingUndObj != DeadUndObj)
2126 LLVM_DEBUG(
dbgs() <<
"DSE: Remove Dead Store:\n DEAD: " << *DeadI
2127 <<
"\n KILLER: " << *KillingI <<
'\n');
2128 State.deleteDeadInstruction(DeadI);
2133 int64_t KillingOffset = 0;
2134 int64_t DeadOffset = 0;
2135 OverwriteResult
OR = State.isOverwrite(
2136 KillingI, DeadI, KillingLoc, DeadLoc, KillingOffset, DeadOffset);
2137 if (OR == OW_MaybePartial) {
2138 auto Iter = State.IOLs.insert(
2139 std::make_pair<BasicBlock *, InstOverlapIntervalsTy>(
2141 auto &IOL = Iter.first->second;
2143 DeadOffset, DeadI, IOL);
2147 auto *DeadSI = dyn_cast<StoreInst>(DeadI);
2148 auto *KillingSI = dyn_cast<StoreInst>(KillingI);
2152 if (DeadSI && KillingSI && DT.
dominates(DeadSI, KillingSI)) {
2154 KillingSI, DeadSI, KillingOffset, DeadOffset, State.DL,
2155 State.BatchAA, &DT)) {
2158 DeadSI->setOperand(0, Merged);
2159 ++NumModifiedStores;
2165 State.deleteDeadInstruction(KillingSI);
2166 auto I = State.IOLs.find(DeadSI->getParent());
2167 if (
I != State.IOLs.end())
2168 I->second.erase(DeadSI);
2174 if (OR == OW_Complete) {
2175 LLVM_DEBUG(
dbgs() <<
"DSE: Remove Dead Store:\n DEAD: " << *DeadI
2176 <<
"\n KILLER: " << *KillingI <<
'\n');
2177 State.deleteDeadInstruction(DeadI);
2185 if (!Shortend && State.storeIsNoop(KillingDef, KillingUndObj)) {
2186 LLVM_DEBUG(
dbgs() <<
"DSE: Remove No-Op Store:\n DEAD: " << *KillingI
2188 State.deleteDeadInstruction(KillingI);
2189 NumRedundantStores++;
2195 if (!Shortend && State.tryFoldIntoCalloc(KillingDef, KillingUndObj)) {
2196 LLVM_DEBUG(
dbgs() <<
"DSE: Remove memset after forming calloc:\n"
2197 <<
" DEAD: " << *KillingI <<
'\n');
2198 State.deleteDeadInstruction(KillingI);
2205 for (
auto &KV : State.IOLs)
2206 MadeChange |= State.removePartiallyOverlappedStores(KV.second);
2208 MadeChange |= State.eliminateRedundantStoresOfExistingValues();
2209 MadeChange |= State.eliminateDeadWritesAtEndOfFunction();
2226 bool Changed = eliminateDeadStores(
F, AA, MSSA, DT, PDT, AC, TLI, LI);
2228#ifdef LLVM_ENABLE_STATS
2231 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 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.
This is the interface for a simple mod/ref and alias analysis over globals.
static void deleteDeadInstruction(Instruction *I)
This file implements a map that provides insertion order iteration.
This file provides utility analysis objects describing memory locations.
This file exposes an interface to building/using memory SSA to walk memory instructions using a use/d...
Module.h This file contains the declarations for the Module class.
print must be executed print the must be executed context for all instructions
Contains a collection of routines for determining if a given instruction is guaranteed to execute if ...
This header defines various interfaces for pass management in LLVM.
This file builds on the ADT/GraphTraits.h file to build a generic graph post order iterator.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file implements a set that has insertion order iteration characteristics.
This file defines the SmallPtrSet class.
This file defines the SmallVector class.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
A manager for alias analyses.
Class for arbitrary precision integers.
APInt zext(unsigned width) const
Zero extend to a new width.
static APInt getBitsSet(unsigned numBits, unsigned loBit, unsigned hiBit)
Get a value with a block of bits set.
unsigned getBitWidth() const
Return the number of bits in the APInt.
The possible results of an alias query.
@ NoAlias
The two locations do not alias at all.
@ PartialAlias
The two locations alias, but only due to a partial overlap.
@ MustAlias
The two locations precisely alias each other.
constexpr int32_t getOffset() const
constexpr bool hasOffset() const
A container for analyses that lazily runs them and caches their results.
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
This class represents an incoming formal argument to a Function.
A function analysis which provides an AssumptionCache.
A cache of @llvm.assume calls within a function.
LLVM Basic Block Representation.
const Function * getParent() const
Return the enclosing method, or null if none.
InstListType::iterator iterator
Instruction iterators...
This class is a wrapper over an AAResults, and it is intended to be used only when there are no IR ch...
AliasResult alias(const MemoryLocation &LocA, const MemoryLocation &LocB)
bool isMustAlias(const MemoryLocation &LocA, const MemoryLocation &LocB)
ModRefInfo getModRefInfo(const Instruction *I, const std::optional< MemoryLocation > &OptLoc)
Represents analyses that only rely on functions' control flow.
This class represents a function call, abstracting a target machine's calling convention.
static CastInst * CreatePointerCast(Value *S, Type *Ty, const Twine &Name, BasicBlock *InsertAtEnd)
Create a BitCast AddrSpaceCast, or a PtrToInt cast instruction.
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
static Constant * get(Type *Ty, uint64_t V, bool IsSigned=false)
If Ty is a vector type, return a Constant with a splat of the given value.
This is an important base class in LLVM.
bool isNullValue() const
Return true if this is the value that would be returned by getNullValue.
static DIAssignID * getDistinct(LLVMContext &Context)
static 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.
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 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.
Represents a single loop in the control flow graph.
This class implements a map that also provides access to all stored values in a deterministic order.
iterator find(const KeyT &Key)
Value * getLength() const
This class wraps the llvm.memset and llvm.memset.inline intrinsics.
BasicBlock * getBlock() const
Represents a read-write access to memory, whether it is a must-alias, or a may-alias.
void setOptimized(MemoryAccess *MA)
Representation for a specific memory location.
static MemoryLocation get(const LoadInst *LI)
Return a location with information about the memory reference by the given instruction.
LocationSize Size
The maximum size of the location, in address-units, or UnknownSize if the size is not known.
static MemoryLocation getAfter(const Value *Ptr, const AAMDNodes &AATags=AAMDNodes())
Return a location that may access any location after Ptr, while remaining within the underlying objec...
MemoryLocation getWithNewPtr(const Value *NewPtr) const
const Value * Ptr
The address of the start of the location.
static MemoryLocation getForDest(const MemIntrinsic *MI)
Return a location representing the destination of a memory set or transfer.
static std::optional< MemoryLocation > getOrNone(const Instruction *Inst)
An analysis that produces MemorySSA for a function.
MemoryAccess * getClobberingMemoryAccess(const Instruction *I, BatchAAResults &AA)
Given a memory Mod/Ref/ModRef'ing instruction, calling this will give you the nearest dominating Memo...
Encapsulates MemorySSA, including all data associated with memory accesses.
MemorySSAWalker * getSkipSelfWalker()
MemorySSAWalker * getWalker()
MemoryUseOrDef * getMemoryAccess(const Instruction *I) const
Given a memory Mod/Ref'ing instruction, get the MemorySSA access associated with it.
void ensureOptimizedUses()
By default, uses are not optimized during MemorySSA construction.
bool isLiveOnEntryDef(const MemoryAccess *MA) const
Return true if MA represents the live on entry value.
MemoryAccess * getDefiningAccess() const
Get the access that produces the memory state used by this Use.
Instruction * getMemoryInst() const
Get the instruction that this MemoryUse represents.
PHITransAddr - An address value which tracks and handles phi translation.
Value * translateValue(BasicBlock *CurBB, BasicBlock *PredBB, const DominatorTree *DT, bool MustDominate)
translateValue - PHI translate the current address up the CFG from CurBB to Pred, updating our state ...
bool isPotentiallyPHITranslatable() const
isPotentiallyPHITranslatable - If this needs PHI translation, return true if we have some hope of doi...
bool needsPHITranslationFromBlock(BasicBlock *BB) const
needsPHITranslationFromBlock - Return true if moving from the specified BasicBlock to its predecessor...
Analysis pass which computes a PostDominatorTree.
PostDominatorTree Class - Concrete subclass of DominatorTree that is used to compute the post-dominat...
bool dominates(const Instruction *I1, const Instruction *I2) const
Return true if I1 dominates I2.
A set of analyses that are preserved following a run of a transformation pass.
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
void preserveSet()
Mark an analysis set as preserved.
void preserve()
Mark an analysis as preserved.
A vector that has set insertion semantics.
size_type size() const
Determine the number of elements in the SetVector.
bool insert(const value_type &X)
Insert a new element into the SetVector.
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
bool contains(ConstPtrType Ptr) const
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
A SetVector that performs no allocations if smaller than a certain size.
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
An instruction for storing to memory.
Value * getValueOperand()
Analysis pass providing the TargetLibraryInfo.
Provides information about what library functions are available for the current target.
bool has(LibFunc F) const
Tests whether a library function is available.
bool getLibFunc(StringRef funcName, LibFunc &F) const
Searches for a particular function name.
The instances of the Type class are immutable: once they are created, they are never changed.
unsigned getPointerAddressSpace() const
Get the address space of this pointer or pointer vector type.
static IntegerType * getInt8Ty(LLVMContext &C)
static PointerType * getInt8PtrTy(LLVMContext &C, unsigned AS=0)
A Use represents the edge between a Value definition and its users.
LLVM Value Representation.
Type * getType() const
All values are typed, get the type of this value.
const Value * stripPointerCasts() const
Strip off pointer casts, all-zero GEPs and address space casts.
LLVMContext & getContext() const
All values hold a context through their type.
iterator_range< use_iterator > uses()
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
bool match(Val *V, const Pattern &P)
specificval_ty m_Specific(const Value *V)
Match if we have a specific specified value.
class_match< ConstantInt > m_ConstantInt()
Match an arbitrary ConstantInt and ignore it.
CmpClass_match< LHS, RHS, ICmpInst, ICmpInst::Predicate > m_ICmp(ICmpInst::Predicate &Pred, const LHS &L, const RHS &R)
brc_match< Cond_t, bind_ty< BasicBlock >, bind_ty< BasicBlock > > m_Br(const Cond_t &C, BasicBlock *&T, BasicBlock *&F)
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
is_zero m_Zero()
Match any null constant or a vector with all elements equal to 0.
AssignmentMarkerRange getAssignmentMarkers(DIAssignID *ID)
Return a range of dbg.assign intrinsics which use \ID as an operand.
initializer< Ty > init(const Ty &Val)
This is an optimization pass for GlobalISel generic memory operations.
auto drop_begin(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the first N elements excluded.
Constant * getInitialValueOfAllocation(const Value *V, const TargetLibraryInfo *TLI, Type *Ty)
If this is a call to an allocation function that initializes memory to a fixed value,...
bool isStrongerThanMonotonic(AtomicOrdering AO)
bool isAligned(Align Lhs, uint64_t SizeInBytes)
Checks that SizeInBytes is a multiple of the alignment.
void salvageDebugInfo(const MachineRegisterInfo &MRI, MachineInstr &MI)
Assuming the instruction MI is going to be deleted, attempt to salvage debug users of MI by writing t...
Value * emitCalloc(Value *Num, Value *Size, IRBuilderBase &B, const TargetLibraryInfo &TLI)
Emit a call to the calloc function.
Value * GetPointerBaseWithConstantOffset(Value *Ptr, int64_t &Offset, const DataLayout &DL, bool AllowNonInbounds=true)
Analyze the specified pointer to see if it can be expressed as a base pointer plus a constant offset.
const Value * getUnderlyingObject(const Value *V, unsigned MaxLookup=6)
This method strips off any GEP address adjustments and pointer casts from the specified value,...
iterator_range< po_iterator< T > > post_order(const T &G)
bool isNoAliasCall(const Value *V)
Return true if this pointer is returned by a noalias function.
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
bool isInstructionTriviallyDead(Instruction *I, const TargetLibraryInfo *TLI=nullptr)
Return true if the result produced by the instruction is not used, and the instruction will return.
bool getObjectSize(const Value *Ptr, uint64_t &Size, const DataLayout &DL, const TargetLibraryInfo *TLI, ObjectSizeOpts Opts={})
Compute the size of the object pointed by Ptr.
auto reverse(ContainerTy &&C)
bool isModSet(const ModRefInfo MRI)
bool PointerMayBeCaptured(const Value *V, bool ReturnCaptures, bool StoreCaptures, unsigned MaxUsesToExplore=0)
PointerMayBeCaptured - Return true if this pointer value may be captured by the enclosing function (w...
bool NullPointerIsDefined(const Function *F, unsigned AS=0)
Check whether null pointer dereferencing is considered undefined behavior for a given function or an ...
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
bool AreStatisticsEnabled()
Check if statistics are enabled.
bool isNotVisibleOnUnwind(const Value *Object, bool &RequiresNoCaptureBeforeUnwind)
Return true if Object memory is not visible after an unwind, in the sense that program semantics cann...
uint64_t offsetToAlignment(uint64_t Value, Align Alignment)
Returns the offset to the next integer (mod 2**64) that is greater than or equal to Value and is a mu...
bool salvageKnowledge(Instruction *I, AssumptionCache *AC=nullptr, DominatorTree *DT=nullptr)
Calls BuildAssumeFromInst and if the resulting llvm.assume is valid insert if before I.
Value * getFreedOperand(const CallBase *CB, const TargetLibraryInfo *TLI)
If this if a call to a free function, return the freed operand.
Value * isBytewiseValue(Value *V, const DataLayout &DL)
If the specified value can be set by repeating the same byte in memory, return the i8 value that it i...
auto predecessors(const MachineBasicBlock *BB)
bool mayContainIrreducibleControl(const Function &F, const LoopInfo *LI)
bool isStrongerThan(AtomicOrdering AO, AtomicOrdering Other)
Returns true if ao is stronger than other as defined by the AtomicOrdering lattice,...
bool isRefSet(const ModRefInfo MRI)
This struct is a compact representation of a valid (non-zero power of two) alignment.
uint64_t value() const
This is a hole in the type system and should not be abused.
static void collectEphemeralValues(const Loop *L, AssumptionCache *AC, SmallPtrSetImpl< const Value * > &EphValues)
Collect a loop's ephemeral values (those used only by an assume or similar intrinsics in the loop).
Holds the characteristics of one fragment of a larger variable.
Various options to control the behavior of getObjectSize.
bool NullIsUnknownSize
If this is true, null pointers in address space 0 will be treated as though they can't be evaluated.