65#define DEBUG_TYPE "memcpyopt"
67STATISTIC(NumMemCpyInstr,
"Number of memcpy instructions deleted");
68STATISTIC(NumMemMoveInstr,
"Number of memmove instructions deleted");
69STATISTIC(NumMemSetInfer,
"Number of memsets inferred");
70STATISTIC(NumMoveToCpy,
"Number of memmoves converted to memcpy");
71STATISTIC(NumCpyToSet,
"Number of memcpys converted to memset");
72STATISTIC(NumCallSlot,
"Number of call slot optimizations performed");
73STATISTIC(NumStackMove,
"Number of stack-move optimizations performed");
102 bool isProfitableToUseMemset(
const DataLayout &
DL)
const;
110bool MemsetRange::isProfitableToUseMemset(
const DataLayout &
DL)
const {
112 if (TheStores.
size() >= 4 ||
End - Start >= 16)
116 if (TheStores.
size() < 2)
121 for (Instruction *SI : TheStores)
127 if (TheStores.size() == 2)
140 unsigned Bytes = unsigned(
End - Start);
141 unsigned MaxIntSize =
DL.getLargestLegalIntTypeSizeInBits() / 8;
144 unsigned NumPointerStores = Bytes / MaxIntSize;
147 unsigned NumByteStores = Bytes % MaxIntSize;
152 return TheStores.size() > NumPointerStores + NumByteStores;
163 const DataLayout &
DL;
166 MemsetRanges(
const DataLayout &
DL) :
DL(
DL) {}
170 const_iterator
begin()
const {
return Ranges.begin(); }
171 const_iterator
end()
const {
return Ranges.end(); }
174 void addInst(int64_t OffsetFromFirst, Instruction *Inst) {
176 addStore(OffsetFromFirst, SI);
181 void addStore(int64_t OffsetFromFirst, StoreInst *SI) {
182 TypeSize StoreSize =
DL.getTypeStoreSize(
SI->getOperand(0)->getType());
185 SI->getPointerOperand(),
SI->getAlign(), SI);
188 void addMemSet(int64_t OffsetFromFirst, MemSetInst *MSI) {
202void MemsetRanges::addRange(int64_t Start, int64_t
Size,
Value *Ptr,
203 MaybeAlign Alignment, Instruction *Inst) {
207 Ranges, [=](
const MemsetRange &O) {
return O.End <
Start; });
213 MemsetRange &
R = *
Ranges.insert(
I, MemsetRange());
218 R.TheStores.push_back(Inst);
223 I->TheStores.push_back(Inst);
227 if (
I->Start <= Start &&
I->End >=
End)
236 if (Start < I->Start) {
247 range_iterator NextI =
I;
248 while (++NextI !=
Ranges.end() &&
End >= NextI->Start) {
250 I->TheStores.append(NextI->TheStores.begin(), NextI->TheStores.end());
251 if (NextI->End >
I->End)
267 assert(Start->getParent() ==
End->getParent() &&
"Must be in same block");
269 if (Start->getFunction()->doesNotThrow())
274 bool RequiresNoCaptureBeforeUnwind;
276 RequiresNoCaptureBeforeUnwind) &&
277 !RequiresNoCaptureBeforeUnwind)
285void MemCpyOptPass::eraseInstruction(Instruction *
I) {
286 MSSAU->removeMemoryAccess(
I);
287 EEA->removeInstruction(
I);
288 I->eraseFromParent();
299 assert(Start->getBlock() ==
End->getBlock() &&
"Only local supported");
305 if (
II &&
II->getIntrinsicID() == Intrinsic::lifetime_start &&
306 SkippedLifetimeStart && !*SkippedLifetimeStart) {
307 *SkippedLifetimeStart =
I;
326 return Start->getBlock() !=
End->getBlock() ||
328 make_range(std::next(Start->getIterator()),
End->getIterator()),
330 if (isa<MemoryUse>(&Acc))
332 Instruction *AccInst =
333 cast<MemoryUseOrDef>(&Acc)->getMemoryInst();
334 return isModSet(AA.getModRefInfo(AccInst, Loc));
348Instruction *MemCpyOptPass::tryMergingIntoMemset(Instruction *StartInst,
355 if (
DL.getTypeStoreSize(
SI->getOperand(0)->getType()).isScalable())
369 MemoryUseOrDef *MemInsertPoint =
nullptr;
370 for (++BI; !BI->isTerminator(); ++BI) {
374 MemInsertPoint = CurrentAcc;
379 if (CB->onlyAccessesInaccessibleMemory())
387 if (BI->mayWriteToMemory() || BI->mayReadFromMemory())
394 if (!NextStore->isSimple())
397 Value *StoredVal = NextStore->getValueOperand();
405 if (
DL.getTypeStoreSize(StoredVal->
getType()).isScalable())
414 if (ByteVal != StoredByte)
418 std::optional<int64_t>
Offset =
419 NextStore->getPointerOperand()->getPointerOffsetFrom(StartPtr,
DL);
427 if (MSI->isVolatile() || ByteVal != MSI->getValue() ||
432 std::optional<int64_t>
Offset =
433 MSI->getDest()->getPointerOffsetFrom(StartPtr,
DL);
449 Ranges.addInst(0, StartInst);
459 for (
const MemsetRange &
Range : Ranges) {
460 if (
Range.TheStores.size() == 1)
464 if (!
Range.isProfitableToUseMemset(
DL))
469 StartPtr =
Range.StartPtr;
471 AMemSet = Builder.CreateMemSet(StartPtr, ByteVal,
Range.End -
Range.Start,
478 dbgs() <<
"With: " << *AMemSet <<
'\n');
479 if (!
Range.TheStores.empty())
484 ? MSSAU->createMemoryAccessBefore(AMemSet,
nullptr, MemInsertPoint)
485 : MSSAU->createMemoryAccessAfter(AMemSet,
nullptr, MemInsertPoint));
486 MSSAU->insertDef(NewDef,
true);
487 MemInsertPoint = NewDef;
490 for (Instruction *SI :
Range.TheStores)
503bool MemCpyOptPass::moveUp(StoreInst *SI, Instruction *
P,
const LoadInst *LI) {
511 DenseSet<Instruction *>
Args;
512 auto AddArg = [&](
Value *Arg) {
514 if (
I &&
I->getParent() ==
SI->getParent()) {
522 if (!AddArg(
SI->getPointerOperand()))
526 SmallVector<Instruction *, 8> ToLift{
SI};
536 for (
auto I = --
SI->getIterator(),
E =
P->getIterator();
I !=
E; --
I) {
544 bool MayAlias =
isModOrRefSet(AA->getModRefInfo(
C, std::nullopt));
546 bool NeedLift =
false;
566 if (
isModSet(AA->getModRefInfo(
C, LoadLoc)))
599 MemoryUseOrDef *MemInsertPoint =
nullptr;
600 if (MemoryUseOrDef *MA = MSSA->getMemoryAccess(
P)) {
606 if (MemoryUseOrDef *MA = MSSA->getMemoryAccess(&
I)) {
616 EEA->insertPotentialCapture(
I);
617 I->moveBefore(
P->getIterator());
618 assert(MemInsertPoint &&
"Must have found insert point");
619 if (MemoryUseOrDef *MA = MSSA->getMemoryAccess(
I)) {
620 MSSAU->moveAfter(MA, MemInsertPoint);
628bool MemCpyOptPass::processStoreOfLoad(StoreInst *SI, LoadInst *LI,
629 const DataLayout &
DL,
634 BatchAAResults BAA(*AA, EEA);
636 if (
T->isAggregateType()) {
646 if (
isModSet(BAA.getModRefInfo(&
I, LoadLoc))) {
656 if (
P == SI || moveUp(SI,
P, LI)) {
661 bool UseMemMove =
false;
662 if (
isModSet(AA->getModRefInfo(SI, LoadLoc)))
667 Builder.CreateTypeSize(Builder.getInt64Ty(),
DL.getTypeStoreSize(
T));
670 M = Builder.CreateMemMove(
SI->getPointerOperand(),
SI->getAlign(),
674 M = Builder.CreateMemCpy(
SI->getPointerOperand(),
SI->getAlign(),
676 M->copyMetadata(*SI, LLVMContext::MD_DIAssignID);
678 LLVM_DEBUG(
dbgs() <<
"Promoting " << *LI <<
" to " << *SI <<
" => " << *M
682 auto *NewAccess = MSSAU->createMemoryAccessAfter(M,
nullptr, LastDef);
690 BBI =
M->getIterator();
698 auto GetCall = [&]() -> CallInst * {
702 MSSA->getWalker()->getClobberingMemoryAccess(LI, BAA)))
707 bool Changed = performCallSlotOptzn(
708 LI, SI,
SI->getPointerOperand()->stripPointerCasts(),
710 DL.getTypeStoreSize(
SI->getOperand(0)->getType()),
711 std::min(
SI->getAlign(), LI->
getAlign()), BAA, GetCall);
722 if (performStackMoveOptzn(LI, SI,
SI->getPointerOperand(),
726 BBI =
SI->getNextNode()->getIterator();
746 if (
SI->getMetadata(LLVMContext::MD_nontemporal))
749 const DataLayout &
DL =
SI->getDataLayout();
751 Value *StoredVal =
SI->getValueOperand();
760 return processStoreOfLoad(SI, LI,
DL, BBI);
774 tryMergingIntoMemset(SI,
SI->getPointerOperand(), ByteVal)) {
775 BBI =
I->getIterator();
782 auto *
T =
V->getType();
783 if (!
T->isAggregateType())
786 TypeSize
Size =
DL.getTypeStoreSize(
T);
787 if (
Size.isScalable())
791 auto *
M = Builder.CreateMemSet(
SI->getPointerOperand(), ByteVal,
Size,
793 M->copyMetadata(*SI, LLVMContext::MD_DIAssignID);
795 LLVM_DEBUG(
dbgs() <<
"Promoting " << *SI <<
" to " << *M <<
"\n");
800 auto *NewAccess = MSSAU->createMemoryAccessBefore(M,
nullptr, StoreDef);
807 BBI =
M->getIterator();
817 BBI =
I->getIterator();
826bool MemCpyOptPass::performCallSlotOptzn(Instruction *cpyLoad,
827 Instruction *cpyStore,
Value *cpyDest,
828 Value *cpySrc, TypeSize cpySize,
831 std::function<CallInst *()> GetC) {
857 std::optional<TypeSize> SrcAllocaSize = srcAlloca->getAllocationSize(
DL);
858 if (!SrcAllocaSize || SrcAllocaSize->isScalable())
860 uint64_t srcSize = SrcAllocaSize->getFixedValue();
862 if (cpySize < srcSize)
865 CallInst *
C = GetC();
871 if (
F->isIntrinsic() &&
F->getIntrinsicID() == Intrinsic::lifetime_start)
874 if (
C->getParent() != cpyStore->
getParent()) {
879 MemoryLocation DestLoc =
882 : MemoryLocation::getForDest(
cast<MemCpyInst>(cpyStore));
888 MSSA->getMemoryAccess(cpyStore), &SkippedLifetimeStart)) {
889 LLVM_DEBUG(dbgs() <<
"Call Slot: Dest pointer modified after call\n");
896 if (SkippedLifetimeStart) {
899 if (LifetimeArg && LifetimeArg->getParent() ==
C->getParent() &&
900 C->comesBefore(LifetimeArg))
906 bool ExplicitlyDereferenceableOnly;
908 ExplicitlyDereferenceableOnly) ||
910 SimplifyQuery(
DL, DT, AC,
C))) {
919 LLVM_DEBUG(
dbgs() <<
"Call Slot: Dest pointer not dereferenceable\n");
939 LLVM_DEBUG(
dbgs() <<
"Call Slot: Dest may be visible through unwinding\n");
944 Align srcAlign = srcAlloca->getAlign();
945 bool isDestSufficientlyAligned = srcAlign <= cpyDestAlign;
949 LLVM_DEBUG(
dbgs() <<
"Call Slot: Dest not sufficiently aligned\n");
958 while (!srcUseList.empty()) {
959 User *
U = srcUseList.pop_back_val();
968 if (U !=
C && U != cpyLoad) {
969 LLVM_DEBUG(
dbgs() <<
"Call slot: Source accessed by " << *U <<
"\n");
976 bool SrcIsCaptured =
any_of(
C->args(), [&](Use &U) {
977 return U->stripPointerCasts() == cpySrc &&
978 !C->doesNotCapture(C->getArgOperandNo(&U));
995 MemoryLocation SrcLoc =
997 for (Instruction &
I :
998 make_range(++
C->getIterator(),
C->getParent()->end())) {
1001 if (
II->getIntrinsicID() == Intrinsic::lifetime_end &&
1002 II->getArgOperand(0) == srcAlloca)
1025 bool NeedMoveGEP =
false;
1026 if (!DT->dominates(cpyDest,
C)) {
1029 if (
GEP &&
GEP->hasAllConstantIndices() &&
1030 DT->dominates(
GEP->getPointerOperand(),
C))
1052 for (
unsigned ArgI = 0; ArgI <
C->arg_size(); ++ArgI)
1053 if (
C->getArgOperand(ArgI)->stripPointerCasts() == cpySrc &&
1054 cpySrc->
getType() !=
C->getArgOperand(ArgI)->getType())
1058 bool changedArgument =
false;
1059 for (
unsigned ArgI = 0; ArgI <
C->arg_size(); ++ArgI)
1060 if (
C->getArgOperand(ArgI)->stripPointerCasts() == cpySrc) {
1061 changedArgument =
true;
1062 C->setArgOperand(ArgI, cpyDest);
1065 if (!changedArgument)
1069 if (!isDestSufficientlyAligned) {
1077 GEP->moveBefore(
C->getIterator());
1080 if (SkippedLifetimeStart) {
1081 SkippedLifetimeStart->
moveBefore(
C->getIterator());
1082 MSSAU->moveBefore(MSSA->getMemoryAccess(SkippedLifetimeStart),
1083 MSSA->getMemoryAccess(
C));
1087 if (cpyLoad != cpyStore)
1096bool MemCpyOptPass::processMemCpyMemCpyDependence(MemCpyInst *M,
1098 BatchAAResults &BAA) {
1112 int64_t MForwardOffset = 0;
1113 const DataLayout &
DL =
M->getDataLayout();
1116 if (
M->getSource() != MDep->
getDest()) {
1117 std::optional<int64_t>
Offset =
1118 M->getSource()->getPointerOffsetFrom(MDep->
getDest(),
DL);
1121 MForwardOffset = *
Offset;
1124 Value *CopyLength =
M->getLength();
1129 if (MForwardOffset != 0 || MDep->
getLength() != CopyLength) {
1135 if (!MDepLen || !MLen)
1137 if (MDepLen->getZExtValue() < MLen->getZExtValue() + MForwardOffset) {
1140 if (MDepLen->getZExtValue() <= (
uint64_t)MForwardOffset)
1144 CopyLength = ConstantInt::get(CopyLength->
getType(),
1145 MDepLen->getZExtValue() - MForwardOffset);
1153 if (NewCopySource && NewCopySource->
use_empty())
1166 MCopyLoc = MCopyLoc.getWithNewSize(
1175 if (MForwardOffset > 0) {
1177 std::optional<int64_t> MDestOffset =
1179 if (MDestOffset == MForwardOffset)
1180 CopySource =
M->getDest();
1182 CopySource = Builder.CreatePtrAddWithSignedOffset(
1187 MCopyLoc = MCopyLoc.getWithNewPtr(CopySource);
1188 if (CopySourceAlign)
1201 if (
writtenBetween(MSSA, BAA, MCopyLoc, MSSA->getMemoryAccess(MDep),
1202 MSSA->getMemoryAccess(M)))
1218 bool UseMemMove =
false;
1223 if (
M->isForceInlined())
1229 LLVM_DEBUG(
dbgs() <<
"MemCpyOptPass: Forwarding memcpy->memcpy src:\n"
1237 NewM = Builder.CreateMemMove(
M->getDest(),
M->getDestAlign(), CopySource,
1238 CopySourceAlign, CopyLength,
M->isVolatile());
1239 else if (
M->isForceInlined())
1243 NewM = Builder.CreateMemCpyInline(
M->getDest(),
M->getDestAlign(),
1244 CopySource, CopySourceAlign, CopyLength,
1247 NewM = Builder.CreateMemCpy(
M->getDest(),
M->getDestAlign(), CopySource,
1248 CopySourceAlign, CopyLength,
M->isVolatile());
1254 auto *NewAccess = MSSAU->createMemoryAccessAfter(NewM,
nullptr, LastDef);
1282bool MemCpyOptPass::processMemSetMemCpyDependence(MemCpyInst *MemCpy,
1284 BatchAAResults &BAA) {
1310 MSSA->getMemoryAccess(MemSet),
1311 MSSA->getMemoryAccess(MemCpy)))
1323 if (DestSize == SrcSize) {
1346 "Preserving debug location based on moving memset within BB.");
1347 Builder.SetCurrentDebugLocation(MemSet->
getDebugLoc());
1351 SrcSize = Builder.CreateZExtOrTrunc(SrcSize, IdxTy);
1352 DestSize = Builder.CreateZExtOrTrunc(DestSize, IdxTy);
1354 Value *Ule = Builder.CreateICmpULE(DestSize, SrcSize);
1355 Value *SizeDiff = Builder.CreateSub(DestSize, SrcSize);
1356 Value *MemsetLen = Builder.CreateSelect(
1357 Ule, ConstantInt::getNullValue(DestSize->
getType()), SizeDiff);
1363 Builder.CreateMemSet(Builder.CreatePtrAdd(Dest, SrcSize),
1364 MemSet->
getOperand(1), MemsetLen, Alignment);
1367 "MemCpy must be a MemoryDef");
1372 MSSAU->createMemoryAccessBefore(NewMemSet,
nullptr, LastDef);
1387 if (
II->getIntrinsicID() == Intrinsic::lifetime_start)
1389 return II->getArgOperand(0) == Alloca;
1422bool MemCpyOptPass::performMemCpyToMemSetOptzn(MemCpyInst *MemCpy,
1424 BatchAAResults &BAA) {
1428 int64_t MOffset = 0;
1433 std::optional<int64_t>
Offset =
1444 if (MOffset != 0 || MemSetSize != CopySize) {
1451 if (!CMemSetSize || !CCopySize || MOffset < 0 ||
1452 CCopySize->getZExtValue() + MOffset > CMemSetSize->getZExtValue()) {
1456 if (CMemSetSize && CCopySize) {
1457 uint64_t MemSetSizeVal = CMemSetSize->getZExtValue();
1458 uint64_t MemCpySizeVal = CCopySize->getZExtValue();
1464 NewSize = MemCpySizeVal <=
Offset ? 0 : MemCpySizeVal -
Offset;
1465 }
else if (MOffset == 0) {
1466 NewSize = MemSetSizeVal;
1469 MemSetSizeVal <= (
uint64_t)MOffset ? 0 : MemSetSizeVal - MOffset;
1471 CopySize = ConstantInt::get(CopySize->
getType(), NewSize);
1483 DestPtr = Builder.CreatePtrAddWithSignedOffset(DestPtr, -MOffset);
1489 Builder.CreateMemSet(DestPtr, MemSet->
getOperand(1), CopySize, Align);
1491 auto *NewAccess = MSSAU->createMemoryAccessAfter(NewM,
nullptr, LastDef);
1509bool MemCpyOptPass::performStackMoveOptzn(Instruction *
Load, Instruction *
Store,
1511 TypeSize
Size, BatchAAResults &BAA) {
1526 if (SrcAlloca == DestAlloca)
1546 if (!SrcOffset || *SrcOffset < *DestOffset || *SrcOffset < 0)
1549 if ((*SrcOffset - *DestOffset) % DestAlloca->
getAlign().
value() != 0)
1553 if (!SrcSize || !DestSize)
1555 if (*SrcSize != *DestSize)
1556 if (!SrcSize->isFixed() || !DestSize->isFixed())
1559 if (
Size != *DestSize || *DestOffset != 0) {
1560 LLVM_DEBUG(
dbgs() <<
"Stack Move: Destination alloca size mismatch\n");
1566 if (
Size.isFixed()) {
1567 if (*SrcOffset +
Size > *SrcSize)
1569 }
else if (*SrcOffset != 0) {
1575 bool MoveSrc = !DT->dominates(SrcAlloca, DestAlloca);
1577 if (!DT->dominates(DestAlloca, SrcAlloca))
1586 SmallVector<Instruction *, 4> LifetimeMarkers;
1587 SmallPtrSet<Instruction *, 4> AAMetadataInstrs;
1589 auto CaptureTrackingWithModRef =
1590 [&](
Instruction *AI, function_ref<bool(Instruction *)> ModRefCallback,
1591 bool &AddressCaptured) ->
bool {
1592 SmallVector<Instruction *, 8> Worklist;
1595 Worklist.
reserve(MaxUsesToExplore);
1596 SmallPtrSet<const Use *, 20> Visited;
1597 while (!Worklist.
empty()) {
1599 for (
const Use &U :
I->uses()) {
1602 if (Visited.
size() >= MaxUsesToExplore) {
1605 <<
"Stack Move: Exceeded max uses to see ModRef, bailing\n");
1608 if (!Visited.
insert(&U).second)
1615 if (UI->mayReadOrWriteMemory()) {
1616 if (UI->isLifetimeStartOrEnd()) {
1625 AAMetadataInstrs.
insert(UI);
1627 if (!ModRefCallback(UI))
1642 ModRefInfo DestModRef = ModRefInfo::NoModRef;
1644 SmallVector<BasicBlock *, 8> ReachabilityWorklist;
1645 auto DestModRefCallback = [&](
Instruction *UI) ->
bool {
1655 if (UI->getParent() ==
Store->getParent()) {
1664 if (UI->comesBefore(
Store))
1674 ReachabilityWorklist.
push_back(UI->getParent());
1680 bool DestAddressCaptured =
false;
1681 if (!CaptureTrackingWithModRef(DestAlloca, DestModRefCallback,
1682 DestAddressCaptured))
1685 if (!ReachabilityWorklist.
empty() &&
1687 nullptr, DT,
nullptr))
1703 auto SrcModRefCallback = [&](
Instruction *UI) ->
bool {
1716 bool SrcAddressCaptured =
false;
1717 if (!CaptureTrackingWithModRef(SrcAlloca, SrcModRefCallback,
1718 SrcAddressCaptured))
1723 if (DestAddressCaptured && SrcAddressCaptured)
1735 if (*SrcSize != *DestSize) {
1738 if (DestSize->getFixedValue() > SrcSize->getFixedValue()) {
1745 Value *NewDestPtr = SrcAlloca;
1746 if (*SrcOffset != *DestOffset) {
1748 NewDestPtr = Builder.CreatePtrAddWithSignedOffset(
1760 if (!LifetimeMarkers.
empty()) {
1761 for (Instruction *
I : LifetimeMarkers)
1770 for (Instruction *
I : AAMetadataInstrs) {
1771 I->setMetadata(LLVMContext::MD_alias_scope,
nullptr);
1772 I->setMetadata(LLVMContext::MD_noalias,
nullptr);
1773 I->setMetadata(LLVMContext::MD_tbaa,
nullptr);
1774 I->setMetadata(LLVMContext::MD_tbaa_struct,
nullptr);
1777 LLVM_DEBUG(
dbgs() <<
"Stack Move: Performed stack-move optimization\n");
1799 if (
M->isVolatile())
1803 if (
M->getSource() ==
M->getDest()) {
1816 MemoryUseOrDef *MA = MSSA->getMemoryAccess(M);
1823 if (GV->isConstant() && GV->hasDefinitiveInitializer())
1825 M->getDataLayout())) {
1828 M->getRawDest(), ByteVal,
M->getLength(),
M->getDestAlign(),
false);
1831 MSSAU->createMemoryAccessAfter(NewM,
nullptr, LastDef);
1839 BatchAAResults BAA(*AA, EEA);
1843 const MemoryAccess *DestClobber =
1844 MSSA->getWalker()->getClobberingMemoryAccess(AnyClobber, DestLoc, BAA);
1852 if (DestClobber->
getBlock() ==
M->getParent())
1853 if (processMemSetMemCpyDependence(M, MDep, BAA))
1856 MemoryAccess *SrcClobber = MSSA->getWalker()->getClobberingMemoryAccess(
1868 if (Instruction *
MI = MD->getMemoryInst()) {
1871 if (performCallSlotOptzn(M, M,
M->getDest(),
M->getSource(),
1873 M->getDestAlign().valueOrOne(), BAA,
1874 [
C]() -> CallInst * { return C; })) {
1876 <<
" call: " << *
C <<
"\n"
1877 <<
" memcpy: " << *M <<
"\n");
1885 if (processMemCpyMemCpyDependence(M, MDep, BAA))
1888 if (performMemCpyToMemSetOptzn(M, MDep, BAA)) {
1911 if (performStackMoveOptzn(M, M,
M->getDest(),
M->getSource(),
1914 BBI =
M->getNextNode()->getIterator();
1925bool MemCpyOptPass::isMemMoveMemSetDependency(MemMoveInst *M) {
1926 const auto &
DL =
M->getDataLayout();
1927 MemoryUseOrDef *MemMoveAccess = MSSA->getMemoryAccess(M);
1933 auto *MemMoveSourceOp =
M->getSource();
1939 LocationSize MemMoveLocSize = SourceLoc.
Size;
1940 if (
Source->getPointerOperand() !=
M->getDest() ||
1947 LocationSize TotalSize =
1949 MemoryLocation CombinedLoc(
M->getDest(), TotalSize);
1953 BatchAAResults BAA(*AA);
1956 MSSA->getWalker()->getClobberingMemoryAccess(FirstDef, CombinedLoc, BAA));
1966 if (!MemSetLength ||
1967 MemSetLength->getZExtValue() <
Offset.getZExtValue() + MemMoveSize)
1984 if (!
M->isVolatile() && isMemMoveMemSetDependency(M)) {
1994 LLVM_DEBUG(
dbgs() <<
"MemCpyOptPass: Optimizing memmove -> memcpy: " << *M
1998 Type *ArgTys[3] = {
M->getRawDest()->getType(),
M->getRawSource()->getType(),
1999 M->getLength()->getType()};
2001 M->getModule(), Intrinsic::memcpy, ArgTys));
2011bool MemCpyOptPass::processByValArgument(CallBase &CB,
unsigned ArgNo) {
2016 TypeSize ByValSize =
DL.getTypeAllocSize(ByValTy);
2018 MemoryUseOrDef *CallAccess = MSSA->getMemoryAccess(&CB);
2021 MemCpyInst *MDep =
nullptr;
2022 BatchAAResults BAA(*AA, EEA);
2023 MemoryAccess *Clobber = MSSA->getWalker()->getClobberingMemoryAccess(
2037 if (!
C1 || !TypeSize::isKnownGE(
2050 if ((!MemDepAlign || *MemDepAlign < *ByValAlign) &&
2066 MSSA->getMemoryAccess(MDep), CallAccess))
2069 LLVM_DEBUG(
dbgs() <<
"MemCpyOptPass: Forwarding memcpy to byval:\n"
2070 <<
" " << *MDep <<
"\n"
2071 <<
" " << CB <<
"\n");
2094bool MemCpyOptPass::processImmutArgument(CallBase &CB,
unsigned ArgNo) {
2095 BatchAAResults BAA(*AA, EEA);
2119 std::optional<TypeSize> AllocaSize = AI->getAllocationSize(
DL);
2122 if (!AllocaSize || AllocaSize->isScalable())
2125 MemoryUseOrDef *CallAccess = MSSA->getMemoryAccess(&CB);
2129 MemCpyInst *MDep =
nullptr;
2130 MemoryAccess *Clobber = MSSA->getWalker()->getClobberingMemoryAccess(
2146 if (!MDepLen || AllocaSize != MDepLen->getValue())
2153 Align AllocaAlign = AI->getAlign();
2154 if (MemDepAlign < AllocaAlign &&
2166 MSSA->getMemoryAccess(MDep), CallAccess))
2173 LLVM_DEBUG(
dbgs() <<
"MemCpyOptPass: Forwarding memcpy to Immut src:\n"
2174 <<
" " << *MDep <<
"\n"
2175 <<
" " << CB <<
"\n");
2185bool MemCpyOptPass::iterateOnFunction(
Function &
F) {
2186 bool MadeChange =
false;
2189 for (BasicBlock &BB :
F) {
2194 if (!DT->isReachableFromEntry(&BB))
2201 bool RepeatInstruction =
false;
2204 MadeChange |= processStore(SI, BI);
2206 RepeatInstruction = processMemSet(M, BI);
2208 RepeatInstruction = processMemCpy(M, BI);
2210 RepeatInstruction = processMemMove(M, BI);
2212 for (
unsigned i = 0, e = CB->
arg_size(); i != e; ++i) {
2214 MadeChange |= processByValArgument(*CB, i);
2216 MadeChange |= processImmutArgument(*CB, i);
2221 if (RepeatInstruction) {
2222 if (BI != BB.
begin())
2240 bool MadeChange =
runImpl(
F, &TLI, AA, AC, DT, PDT, &MSSA->getMSSA());
2254 bool MadeChange =
false;
2267 if (!iterateOnFunction(
F))
const TargetLowering & TLI
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
static GCRegistry::Add< ShadowStackGC > C("shadow-stack", "Very portable GC for uncooperative code generators")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
static bool runImpl(MachineFunction &MF)
This file contains the declarations for the subclasses of Constant, which represent the different fla...
This file defines the DenseSet and SmallDenseSet classes.
This is the interface for a simple mod/ref and alias analysis over globals.
Module.h This file contains the declarations for the Module class.
This header defines various interfaces for pass management in LLVM.
static void eraseInstruction(Instruction &I, const LICMDependencies &Deps)
static bool mayBeVisibleThroughUnwinding(Value *V, Instruction *Start, Instruction *End)
static bool isZeroSize(Value *Size)
static bool hasUndefContents(MemorySSA *MSSA, BatchAAResults &AA, Value *V, MemoryDef *Def)
Determine whether the pointer V had only undefined content (due to Def), either because it was freshl...
static bool accessedBetween(BatchAAResults &AA, MemoryLocation Loc, const MemoryUseOrDef *Start, const MemoryUseOrDef *End, Instruction **SkippedLifetimeStart=nullptr)
static bool overreadUndefContents(MemorySSA *MSSA, MemCpyInst *MemCpy, MemIntrinsic *MemSrc, BatchAAResults &BAA)
static bool writtenBetween(MemorySSA *MSSA, BatchAAResults &AA, MemoryLocation Loc, const MemoryUseOrDef *Start, const MemoryUseOrDef *End)
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...
ConstantRange Range(APInt(BitWidth, Low), APInt(BitWidth, High))
uint64_t IntrinsicInst * II
This file contains the declarations for profiling metadata utility functions.
This file defines the scope_exit class, which executes user-defined cleanup logic at scope exit.
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.
LLVM_ABI bool isStaticAlloca() const
Return true if this alloca is in the entry block of the function and is a constant size.
Align getAlign() const
Return the alignment of the memory that is being allocated by the instruction.
void setAllocatedType(Type *Ty)
for use only in special circumstances that need to generically transform a whole instruction (eg: IR ...
Type * getAllocatedType() const
Return the type that is being allocated by the instruction.
unsigned getAddressSpace() const
Return the address space for the allocation.
LLVM_ABI std::optional< TypeSize > getAllocationSize(const DataLayout &DL) const
Get allocation size in bytes.
void setAlignment(Align Align)
const Value * getArraySize() const
Get the number of elements allocated.
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
A function analysis which provides an AssumptionCache.
A cache of @llvm.assume calls within a function.
iterator begin()
Instruction iterator methods.
LLVM_ABI bool isEntryBlock() const
Return true if this is the entry block of the containing function.
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...
bool isMustAlias(const MemoryLocation &LocA, const MemoryLocation &LocB)
ModRefInfo getModRefInfo(const Instruction *I, const std::optional< MemoryLocation > &OptLoc)
ModRefInfo callCapturesBefore(const Instruction *I, const MemoryLocation &MemLoc, DominatorTree *DT)
Represents analyses that only rely on functions' control flow.
bool doesNotCapture(unsigned OpNo) const
Determine whether this data operand is not captured.
LLVM_ABI bool paramHasAttr(unsigned ArgNo, Attribute::AttrKind Kind) const
Determine whether the argument or parameter has the given attribute.
bool isByValArgument(unsigned ArgNo) const
Determine whether this argument is passed by value.
MaybeAlign getParamAlign(unsigned ArgNo) const
Extract the alignment for a call or parameter (0=unknown).
bool onlyReadsMemory(unsigned OpNo) const
Type * getParamByValType(unsigned ArgNo) const
Extract the byval type for a call or parameter.
Value * getArgOperand(unsigned i) const
void setArgOperand(unsigned i, Value *v)
unsigned arg_size() const
A parsed version of the target data layout string in and methods for querying it.
LLVM_ABI IntegerType * getIndexType(LLVMContext &C, unsigned AddressSpace) const
Returns the type of a GEP index in AddressSpace.
Analysis pass which computes a DominatorTree.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Context-sensitive CaptureAnalysis provider, which computes and caches the earliest common dominator c...
static GEPNoWrapFlags inBounds()
LLVM_ABI void mergeDIAssignID(ArrayRef< const Instruction * > SourceInstructions)
Merge the DIAssignID metadata from this instruction and those attached to instructions in SourceInstr...
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
LLVM_ABI void moveBefore(InstListType::iterator InsertPos)
Unlink this instruction from its current basic block and insert it into the basic block that MovePos ...
LLVM_ABI void dropUnknownNonDebugMetadata(ArrayRef< unsigned > KnownIDs={})
Drop all unknown metadata except for debug locations.
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
LLVM_ABI void copyMetadata(const Instruction &SrcInst, ArrayRef< unsigned > WL=ArrayRef< unsigned >())
Copy metadata from SrcInst to this instruction.
LLVM_ABI const DataLayout & getDataLayout() const
Get the data layout of the module this instruction belongs to.
Value * getPointerOperand()
Align getAlign() const
Return the alignment of the access that is being performed.
static LocationSize precise(uint64_t Value)
TypeSize getValue() const
This class wraps the llvm.memcpy intrinsic.
LLVM_ABI PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Value * getLength() const
Value * getRawDest() const
Value * getDest() const
This is just like getRawDest, but it strips off any cast instructions (including addrspacecast) that ...
MaybeAlign getDestAlign() const
This is the common base class for memset/memcpy/memmove.
Value * getRawSource() const
Return the arguments to the instruction.
MaybeAlign getSourceAlign() const
Value * getSource() const
This is just like getRawSource, but it strips off any cast instructions that feed it,...
BasicBlock * getBlock() const
Represents a read-write access to memory, whether it is a must-alias, or a may-alias.
Representation for a specific memory location.
static LLVM_ABI MemoryLocation get(const LoadInst *LI)
Return a location with information about the memory reference by the given instruction.
static LLVM_ABI MemoryLocation getForSource(const MemTransferInst *MTI)
Return a location representing the source of a memory transfer.
LocationSize Size
The maximum size of the location, in address-units, or UnknownSize if the size is not known.
static MemoryLocation getBeforeOrAfter(const Value *Ptr, const AAMDNodes &AATags=AAMDNodes())
Return a location that may access any location before or after Ptr, while remaining within the underl...
static LLVM_ABI MemoryLocation getForDest(const MemIntrinsic *MI)
Return a location representing the destination of a memory set or transfer.
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.
LLVM_ABI bool dominates(const MemoryAccess *A, const MemoryAccess *B) const
Given two memory accesses in potentially different blocks, determine whether MemoryAccess A dominates...
LLVM_ABI void verifyMemorySSA(VerificationLevel=VerificationLevel::Fast) const
Verify that MemorySSA is self consistent (IE definitions dominate all uses, uses appear in the right ...
LLVM_ABI 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.
Class that has the common methods + fields of memory uses/defs.
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.
Analysis pass which computes a PostDominatorTree.
PostDominatorTree Class - Concrete subclass of DominatorTree that is used to compute the post-dominat...
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.
PreservedAnalyses & preserveSet()
Mark an analysis set as preserved.
PreservedAnalyses & preserve()
Mark an analysis as preserved.
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
void reserve(size_type N)
typename SuperClass::const_iterator const_iterator
void append(ItTy in_start, ItTy in_end)
Add the specified range to the end of the SmallVector.
typename SuperClass::iterator iterator
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Analysis pass providing the TargetLibraryInfo.
Provides information about what library functions are available for the current target.
static constexpr TypeSize getFixed(ScalarTy ExactSize)
Type * getScalarType() const
If this is a vector type, return the element type, otherwise return 'this'.
void setOperand(unsigned i, Value *Val)
Value * getOperand(unsigned i) const
LLVM Value Representation.
Type * getType() const
All values are typed, get the type of this value.
bool hasOneUse() const
Return true if there is exactly one use of this value.
LLVM_ABI void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
LLVM_ABI const Value * stripPointerCasts() const
Strip off pointer casts, all-zero GEPs and address space casts.
LLVM_ABI std::optional< int64_t > getPointerOffsetFrom(const Value *Other, const DataLayout &DL) const
If this ptr is provably equal to Other plus a constant offset, return that offset in bytes.
constexpr ScalarTy getFixedValue() const
constexpr bool isScalable() const
Returns whether the quantity is scaled by a runtime quantity (vscale).
const ParentTy * getParent() const
reverse_self_iterator getReverseIterator()
self_iterator getIterator()
This provides a very simple, boring adaptor for a begin and end iterator into a range type.
Abstract Attribute helper functions.
constexpr char Align[]
Key for Kernel::Arg::Metadata::mAlign.
constexpr char Args[]
Key for Kernel::Metadata::mArgs.
@ BasicBlock
Various leaf nodes.
LLVM_ABI Function * getOrInsertDeclaration(Module *M, ID id, ArrayRef< Type * > OverloadTys={})
Look up the Function declaration of the intrinsic id in the Module M.
@ User
could "use" a pointer
friend class Instruction
Iterator for Instructions in a `BasicBlock.
LLVM_ABI iterator begin() const
This is an optimization pass for GlobalISel generic memory operations.
bool capturesAddress(CaptureComponents CC)
LLVM_ABI Align getOrEnforceKnownAlignment(Value *V, MaybeAlign PrefAlign, const DataLayout &DL, const Instruction *CtxI=nullptr, AssumptionCache *AC=nullptr, const DominatorTree *DT=nullptr)
Try to ensure that the alignment of V is at least PrefAlign bytes.
LLVM_ABI void setExplicitlyUnknownBranchWeightsIfProfiled(Instruction &I, StringRef PassName, const Function *F=nullptr)
Like setExplicitlyUnknownBranchWeights(...), but only sets unknown branch weights in the new instruct...
decltype(auto) dyn_cast(const From &Val)
dyn_cast<X> - Return the argument parameter cast to the specified type.
scope_exit(Callable) -> scope_exit< Callable >
@ Load
The value being inserted comes from a load (InsertElement only).
@ Store
The extracted value is stored (ExtractElement only).
auto partition_point(R &&Range, Predicate P)
Binary search for the first iterator in a range where a predicate is false.
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
void append_range(Container &C, Range &&R)
Wrapper function to append range R to container C.
auto cast_or_null(const Y &Val)
LLVM_ABI unsigned getDefaultMaxUsesToExploreForCaptureTracking()
getDefaultMaxUsesToExploreForCaptureTracking - Return default value of the maximal number of uses to ...
LLVM_ABI bool PointerMayBeCapturedBefore(const Value *V, bool ReturnCaptures, const Instruction *I, const DominatorTree *DT, bool IncludeI=false, unsigned MaxUsesToExplore=0, const LoopInfo *LI=nullptr)
PointerMayBeCapturedBefore - Return true if this pointer value may be captured by the enclosing funct...
RelativeUniformCounterPtr ValuesPtrExpr VTableAddr Value
LLVM_ABI Value * simplifyInstruction(Instruction *I, const SimplifyQuery &Q)
See if we can compute a simplified version of this instruction.
auto dyn_cast_or_null(const Y &Val)
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
auto reverse(ContainerTy &&C)
bool isModSet(const ModRefInfo MRI)
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
IRBuilder(LLVMContext &, FolderTy, InserterTy) -> IRBuilder< FolderTy, InserterTy >
bool isModOrRefSet(const ModRefInfo MRI)
LLVM_ABI 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...
LLVM_ABI bool VerifyMemorySSA
Enables verification of MemorySSA.
class LLVM_GSL_OWNER SmallVector
Forward declaration of SmallVector so that calculateSmallVectorDefaultInlinedElements can reference s...
LLVM_ABI const Value * getUnderlyingObject(const Value *V, unsigned MaxLookup=MaxLookupSearchDepth, bool MustPreserveProvenance=false)
This method strips off any GEP address adjustments, pointer casts or llvm.threadlocal....
bool isa(const From &Val)
isa<X> - Return true if the parameter to the template is an instance of one of the template type argu...
LLVM_ABI bool isKnownNonZero(const Value *V, const SimplifyQuery &Q, unsigned Depth=0)
Return true if the given value is known to be non-zero when defined.
RNSuccIterator< NodeRef, BlockT, RegionT > succ_begin(NodeRef Node)
ModRefInfo
Flags indicating whether a memory access modifies or references memory.
RNSuccIterator< NodeRef, BlockT, RegionT > succ_end(NodeRef Node)
DWARFExpression::Operation Op
LLVM_ABI bool isPotentiallyReachableFromMany(SmallVectorImpl< BasicBlock * > &Worklist, const BasicBlock *StopBB, const SmallPtrSetImpl< BasicBlock * > *ExclusionSet, const DominatorTree *DT=nullptr, const LoopInfo *LI=nullptr, const CycleInfo *CI=nullptr)
Determine whether there is at least one path from a block in 'Worklist' to 'StopBB' without passing t...
LLVM_ABI bool isIdentifiedFunctionLocal(const Value *V)
Return true if V is umabigously identified at the function-level.
LLVM_ABI bool isGuaranteedToTransferExecutionToSuccessor(const Instruction *I)
Return true if this function can prove that the instruction I will always transfer execution to one o...
decltype(auto) cast(const From &Val)
cast<X> - Return the argument parameter cast to the specified type.
LLVM_ABI 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...
Align commonAlignment(Align A, uint64_t Offset)
Returns the alignment that satisfies both alignments.
LLVM_ABI void combineAAMetadata(Instruction *K, const Instruction *J)
Combine metadata of two instructions, where instruction J is a memory access that has been merged int...
bool capturesAnything(CaptureComponents CC)
LLVM_ABI UseCaptureInfo DetermineUseCaptureKind(const Use &U, const Value *Base)
Determine what kind of capture behaviour U may exhibit.
AnalysisManager< Function > FunctionAnalysisManager
Convenience typedef for the Function analysis manager.
LLVM_ABI bool isDereferenceablePointer(const Value *V, Type *Ty, const SimplifyQuery &Q, bool IgnoreFree=false)
Equivalent to isDereferenceableAndAlignedPointer with an alignment of 1.
@ End
Run the machine verifier once, at the end of the pipeline.
AAResults AliasAnalysis
Temporary typedef for legacy code that uses a generic AliasAnalysis pointer or reference.
bool capturesAnyProvenance(CaptureComponents CC)
bool isRefSet(const ModRefInfo MRI)
LLVM_ABI bool isWritableObject(const Value *Object, bool &ExplicitlyDereferenceableOnly)
Return true if the Object is writable, in the sense that any location based on this pointer that can ...
constexpr uint64_t value() const
This is a hole in the type system and should not be abused.
This struct is a compact representation of a valid (power of two) or undefined (0) alignment.
Align valueOrOne() const
For convenience, returns a valid alignment or 1 if undefined.
CaptureComponents UseCC
Components captured by this use.
CaptureComponents ResultCC
Components captured by the return value of the user of this Use.