44 #include "llvm/Config/llvm-config.h"
97 #define DEBUG_TYPE "sroa"
99 STATISTIC(NumAllocasAnalyzed,
"Number of allocas analyzed for replacement");
100 STATISTIC(NumAllocaPartitions,
"Number of alloca partitions formed");
101 STATISTIC(MaxPartitionsPerAlloca,
"Maximum number of partitions per alloca");
102 STATISTIC(NumAllocaPartitionUses,
"Number of alloca partition uses rewritten");
103 STATISTIC(MaxUsesPerAllocaPartition,
"Maximum number of uses of a partition");
104 STATISTIC(NumNewAllocas,
"Number of new, smaller allocas introduced");
105 STATISTIC(NumPromoted,
"Number of allocas promoted to SSA values");
106 STATISTIC(NumLoadsSpeculated,
"Number of loads speculated to allow promotion");
107 STATISTIC(NumDeleted,
"Number of instructions deleted");
108 STATISTIC(NumVectorized,
"Number of vectorized aggregates");
160 : BeginOffset(BeginOffset), EndOffset(EndOffset),
161 UseAndIsSplittable(U, IsSplittable) {}
163 uint64_t beginOffset()
const {
return BeginOffset; }
164 uint64_t endOffset()
const {
return EndOffset; }
166 bool isSplittable()
const {
return UseAndIsSplittable.
getInt(); }
167 void makeUnsplittable() { UseAndIsSplittable.
setInt(
false); }
169 Use *getUse()
const {
return UseAndIsSplittable.
getPointer(); }
171 bool isDead()
const {
return getUse() ==
nullptr; }
172 void kill() { UseAndIsSplittable.
setPointer(
nullptr); }
181 if (beginOffset() <
RHS.beginOffset())
183 if (beginOffset() >
RHS.beginOffset())
185 if (isSplittable() !=
RHS.isSplittable())
186 return !isSplittable();
187 if (endOffset() >
RHS.endOffset())
195 return LHS.beginOffset() < RHSOffset;
199 return LHSOffset <
RHS.beginOffset();
203 return isSplittable() ==
RHS.isSplittable() &&
204 beginOffset() ==
RHS.beginOffset() && endOffset() ==
RHS.endOffset();
253 int OldSize = Slices.size();
255 auto SliceI = Slices.begin() + OldSize;
257 std::inplace_merge(Slices.begin(), SliceI, Slices.end());
262 class partition_iterator;
270 return DeadUseIfPromotable;
281 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
293 template <
typename DerivedT,
typename RetT =
void>
class BuilderBase;
298 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
359 uint64_t BeginOffset = 0, EndOffset = 0;
386 assert(BeginOffset < EndOffset &&
"Partitions must span some bytes!");
387 return EndOffset - BeginOffset;
404 iterator
end()
const {
return SJ; }
438 uint64_t MaxSplitSliceEndOffset = 0;
454 assert((
P.SI != SE || !
P.SplitTails.empty()) &&
455 "Cannot advance past the end of the slices!");
458 if (!
P.SplitTails.empty()) {
459 if (
P.EndOffset >= MaxSplitSliceEndOffset) {
461 P.SplitTails.clear();
462 MaxSplitSliceEndOffset = 0;
468 [&](Slice *
S) { return S->endOffset() <= P.EndOffset; });
471 return S->endOffset() == MaxSplitSliceEndOffset;
473 "Could not find the current max split slice offset!");
476 return S->endOffset() <= MaxSplitSliceEndOffset;
478 "Max split slice end offset is not actually the max!");
485 assert(
P.SplitTails.empty() &&
"Failed to clear the split slices!");
495 if (
S.isSplittable() &&
S.endOffset() >
P.EndOffset) {
496 P.SplitTails.push_back(&
S);
497 MaxSplitSliceEndOffset =
498 std::max(
S.endOffset(), MaxSplitSliceEndOffset);
506 P.BeginOffset =
P.EndOffset;
507 P.EndOffset = MaxSplitSliceEndOffset;
514 if (!
P.SplitTails.empty() &&
P.SI->beginOffset() !=
P.EndOffset &&
515 !
P.SI->isSplittable()) {
516 P.BeginOffset =
P.EndOffset;
517 P.EndOffset =
P.SI->beginOffset();
527 P.BeginOffset =
P.SplitTails.empty() ?
P.SI->beginOffset() :
P.EndOffset;
528 P.EndOffset =
P.SI->endOffset();
533 if (!
P.SI->isSplittable()) {
536 assert(
P.BeginOffset ==
P.SI->beginOffset());
540 while (
P.SJ != SE &&
P.SJ->beginOffset() <
P.EndOffset) {
541 if (!
P.SJ->isSplittable())
542 P.EndOffset =
std::max(
P.EndOffset,
P.SJ->endOffset());
554 assert(
P.SI->isSplittable() &&
"Forming a splittable partition!");
557 while (
P.SJ != SE &&
P.SJ->beginOffset() <
P.EndOffset &&
558 P.SJ->isSplittable()) {
559 P.EndOffset =
std::max(
P.EndOffset,
P.SJ->endOffset());
566 if (
P.SJ != SE &&
P.SJ->beginOffset() <
P.EndOffset) {
568 P.EndOffset =
P.SJ->beginOffset();
575 "End iterators don't match between compared partition iterators!");
582 if (
P.SI ==
RHS.P.SI &&
P.SplitTails.empty() ==
RHS.P.SplitTails.empty()) {
584 "Same set of slices formed two different sized partitions!");
585 assert(
P.SplitTails.size() ==
RHS.P.SplitTails.size() &&
586 "Same slice position with differently sized non-empty split "
610 partition_iterator(
end(),
end()));
617 if (
ConstantInt *CI = dyn_cast<ConstantInt>(
SI.getCondition()))
618 return SI.getOperand(1 + CI->isZero());
619 if (
SI.getOperand(1) ==
SI.getOperand(2))
620 return SI.getOperand(1);
627 if (
PHINode *PN = dyn_cast<PHINode>(&
I)) {
629 return PN->hasConstantValue();
656 AllocSize(
DL.getTypeAllocSize(AI.getAllocatedType()).getFixedSize()),
661 if (VisitedDeadInsts.
insert(&
I).second)
662 AS.DeadUsers.push_back(&
I);
666 bool IsSplittable =
false) {
672 <<
" which has zero size or starts outside of the "
673 << AllocSize <<
" byte alloca:\n"
674 <<
" alloca: " << AS.AI <<
"\n"
675 <<
" use: " <<
I <<
"\n");
676 return markAsDead(
I);
688 assert(AllocSize >= BeginOffset);
689 if (
Size > AllocSize - BeginOffset) {
691 <<
Offset <<
" to remain within the " << AllocSize
693 <<
" alloca: " << AS.AI <<
"\n"
694 <<
" use: " <<
I <<
"\n");
695 EndOffset = AllocSize;
698 AS.Slices.push_back(Slice(BeginOffset, EndOffset, U, IsSplittable));
703 return markAsDead(BC);
705 return Base::visitBitCastInst(BC);
710 return markAsDead(ASC);
712 return Base::visitAddrSpaceCastInst(ASC);
717 return markAsDead(GEPI);
732 ConstantInt *OpC = dyn_cast<ConstantInt>(GTI.getOperand());
737 if (
StructType *STy = GTI.getStructTypeOrNull()) {
749 DL.getTypeAllocSize(GTI.getIndexedType()).getFixedSize());
755 if (GEPOffset.
ugt(AllocSize))
756 return markAsDead(GEPI);
760 return Base::visitGetElementPtrInst(GEPI);
776 "All simple FCA loads should have been pre-split");
779 return PI.setAborted(&LI);
783 return PI.setAborted(&LI);
785 if (isa<ScalableVectorType>(LI.
getType()))
786 return PI.setAborted(&LI);
793 Value *ValOp =
SI.getValueOperand();
795 return PI.setEscapedAndAborted(&
SI);
797 return PI.setAborted(&
SI);
799 if (
SI.isVolatile() &&
800 SI.getPointerAddressSpace() !=
DL.getAllocaAddrSpace())
801 return PI.setAborted(&
SI);
803 if (isa<ScalableVectorType>(ValOp->
getType()))
804 return PI.setAborted(&
SI);
817 <<
Offset <<
" which extends past the end of the "
818 << AllocSize <<
" byte alloca:\n"
819 <<
" alloca: " << AS.AI <<
"\n"
820 <<
" use: " <<
SI <<
"\n");
821 return markAsDead(
SI);
825 "All simple FCA stores should have been pre-split");
832 if ((Length && Length->
getValue() == 0) ||
833 (IsOffsetKnown &&
Offset.uge(AllocSize)))
835 return markAsDead(II);
838 return PI.setAborted(&II);
843 return PI.setAborted(&II);
846 : AllocSize -
Offset.getLimitedValue(),
852 if (Length && Length->
getValue() == 0)
854 return markAsDead(II);
858 if (VisitedDeadInsts.
count(&II))
862 return PI.setAborted(&II);
869 return PI.setAborted(&II);
876 if (
Offset.uge(AllocSize)) {
878 MemTransferSliceMap.
find(&II);
879 if (MTPI != MemTransferSliceMap.
end())
880 AS.Slices[MTPI->second].kill();
881 return markAsDead(II);
892 return markAsDead(II);
901 std::tie(MTPI, Inserted) =
902 MemTransferSliceMap.
insert(std::make_pair(&II, AS.Slices.size()));
903 unsigned PrevIdx = MTPI->second;
905 Slice &PrevP = AS.Slices[PrevIdx];
909 if (!II.
isVolatile() && PrevP.beginOffset() == RawOffset) {
911 return markAsDead(II);
916 PrevP.makeUnsplittable();
920 insertUse(II,
Offset,
Size, Inserted && Length);
923 assert(AS.Slices[PrevIdx].getUse()->getUser() == &II &&
924 "Map index doesn't point back to a slice with this user.");
933 AS.DeadUseIfPromotable.push_back(U);
938 return PI.setAborted(&II);
953 Base::visitIntrinsicInst(II);
964 Uses.push_back(std::make_pair(cast<Instruction>(*U), Root));
971 std::tie(UsedI,
I) =
Uses.pop_back_val();
973 if (
LoadInst *LI = dyn_cast<LoadInst>(
I)) {
975 DL.getTypeStoreSize(LI->
getType()).getFixedSize());
983 DL.getTypeStoreSize(
Op->getType()).getFixedSize());
988 if (!
GEP->hasAllZeroIndices())
990 }
else if (!isa<BitCastInst>(
I) && !isa<PHINode>(
I) &&
991 !isa<SelectInst>(
I) && !isa<AddrSpaceCastInst>(
I)) {
995 for (
User *U :
I->users())
996 if (Visited.
insert(cast<Instruction>(U)).second)
997 Uses.push_back(std::make_pair(
I, cast<Instruction>(U)));
998 }
while (!
Uses.empty());
1004 assert(isa<PHINode>(
I) || isa<SelectInst>(
I));
1006 return markAsDead(
I);
1011 if (isa<PHINode>(
I) &&
1012 I.getParent()->getFirstInsertionPt() ==
I.getParent()->end())
1013 return PI.setAborted(&
I);
1031 AS.DeadOperands.push_back(U);
1037 return PI.setAborted(&
I);
1044 return PI.setAborted(UnsafeI);
1053 if (
Offset.uge(AllocSize)) {
1054 AS.DeadOperands.push_back(U);
1061 void visitPHINode(
PHINode &PN) { visitPHINodeOrSelectInst(PN); }
1063 void visitSelectInst(
SelectInst &
SI) { visitPHINodeOrSelectInst(
SI); }
1066 void visitInstruction(
Instruction &
I) { PI.setAborted(&
I); }
1071 #
if !defined(
NDEBUG) || defined(LLVM_ENABLE_DUMP)
1074 PointerEscapingInstr(nullptr) {
1076 SliceBuilder::PtrInfo PtrI =
PB.visitPtr(AI);
1077 if (PtrI.isEscaped() || PtrI.isAborted()) {
1080 PointerEscapingInstr = PtrI.getEscapingInst() ? PtrI.getEscapingInst()
1081 : PtrI.getAbortingInst();
1082 assert(PointerEscapingInstr &&
"Did not track a bad instruction");
1093 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1097 printSlice(OS,
I, Indent);
1099 printUse(OS,
I, Indent);
1102 void AllocaSlices::printSlice(
raw_ostream &OS, const_iterator
I,
1104 OS << Indent <<
"[" <<
I->beginOffset() <<
"," <<
I->endOffset() <<
")"
1105 <<
" slice #" << (
I -
begin())
1106 << (
I->isSplittable() ?
" (splittable)" :
"");
1109 void AllocaSlices::printUse(
raw_ostream &OS, const_iterator
I,
1111 OS << Indent <<
" used by: " << *
I->getUse()->getUser() <<
"\n";
1115 if (PointerEscapingInstr) {
1116 OS <<
"Can't analyze slices for alloca: " << AI <<
"\n"
1117 <<
" A pointer to this alloca escaped by:\n"
1118 <<
" " << *PointerEscapingInstr <<
"\n";
1122 OS <<
"Slices of alloca: " << AI <<
"\n";
1132 #endif // !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1136 static std::pair<Type *, IntegerType *>
1140 bool TyIsCommon =
true;
1145 for (AllocaSlices::const_iterator
I =
B;
I !=
E; ++
I) {
1146 Use *U =
I->getUse();
1147 if (isa<IntrinsicInst>(*U->getUser()))
1149 if (
I->beginOffset() !=
B->beginOffset() ||
I->endOffset() != EndOffset)
1152 Type *UserTy =
nullptr;
1153 if (
LoadInst *LI = dyn_cast<LoadInst>(U->getUser())) {
1155 }
else if (
StoreInst *
SI = dyn_cast<StoreInst>(U->getUser())) {
1156 UserTy =
SI->getValueOperand()->getType();
1159 if (
IntegerType *UserITy = dyn_cast_or_null<IntegerType>(UserTy)) {
1164 if (UserITy->getBitWidth() % 8 != 0 ||
1165 UserITy->getBitWidth() / 8 > (EndOffset -
B->beginOffset()))
1170 if (!ITy || ITy->
getBitWidth() < UserITy->getBitWidth())
1176 if (!UserTy || (Ty && Ty != UserTy))
1182 return {TyIsCommon ? Ty :
nullptr, ITy};
1213 APInt MaxSize(APWidth, 0);
1214 bool HaveLoad =
false;
1216 LoadInst *LI = dyn_cast<LoadInst>(U);
1229 if (BBI->mayWriteToMemory())
1276 IRB.SetInsertPoint(&PN);
1278 PN.
getName() +
".sroa.speculated");
1308 IRB.SetInsertPoint(TI);
1311 LoadTy, InVal, Alignment,
1313 ++NumLoadsSpeculated;
1315 Load->setAAMetadata(AATags);
1317 InjectedLoads[Pred] =
Load;
1339 Value *TValue =
SI.getTrueValue();
1340 Value *FValue =
SI.getFalseValue();
1343 for (
User *U :
SI.users()) {
1349 LI = dyn_cast<LoadInst>(U);
1371 IRB.SetInsertPoint(&
SI);
1372 Value *TV =
SI.getTrueValue();
1373 Value *FV =
SI.getFalseValue();
1375 while (!
SI.use_empty()) {
1382 LI = cast<LoadInst>(
SI.user_back());
1387 IRB.SetInsertPoint(LI);
1389 BC ? IRB.CreateBitCast(TV, BC->
getType(), TV->
getName() +
".sroa.cast")
1392 BC ? IRB.CreateBitCast(FV, BC->
getType(), FV->
getName() +
".sroa.cast")
1395 LI->
getName() +
".sroa.speculate.load.true");
1397 LI->
getName() +
".sroa.speculate.load.false");
1398 NumLoadsSpeculated += 2;
1410 Value *V = IRB.CreateSelect(
SI.getCondition(), TL, FL,
1411 LI->
getName() +
".sroa.speculated");
1419 SI.eraseFromParent();
1428 const Twine &NamePrefix) {
1429 if (Indices.empty())
1434 if (Indices.size() == 1 && cast<ConstantInt>(Indices.back())->isZero())
1438 return IRB.CreateInBoundsGEP(
1439 BasePtr->getType()->getNonOpaquePointerElementType(), BasePtr, Indices,
1440 NamePrefix +
"sroa_idx");
1455 const Twine &NamePrefix) {
1457 return buildGEP(IRB, BasePtr, Indices, NamePrefix);
1460 unsigned OffsetSize =
DL.getIndexTypeSizeInBits(BasePtr->getType());
1464 unsigned NumLayers = 0;
1465 Type *ElementTy = Ty;
1470 if (
ArrayType *ArrayTy = dyn_cast<ArrayType>(ElementTy)) {
1471 ElementTy = ArrayTy->getElementType();
1472 Indices.push_back(IRB.getIntN(OffsetSize, 0));
1473 }
else if (
VectorType *VectorTy = dyn_cast<VectorType>(ElementTy)) {
1474 ElementTy = VectorTy->getElementType();
1475 Indices.push_back(IRB.getInt32(0));
1476 }
else if (
StructType *STy = dyn_cast<StructType>(ElementTy)) {
1477 if (STy->element_begin() == STy->element_end())
1479 ElementTy = *STy->element_begin();
1480 Indices.push_back(IRB.getInt32(0));
1485 }
while (ElementTy != TargetTy);
1486 if (ElementTy != TargetTy)
1487 Indices.
erase(Indices.end() - NumLayers, Indices.end());
1489 return buildGEP(IRB, BasePtr, Indices, NamePrefix);
1505 const Twine &NamePrefix) {
1522 Indices.push_back(IRB.getInt(
Index));
1544 const Twine &NamePrefix) {
1548 Ptr = IRB.CreateInBoundsGEP(IRB.getInt8Ty(), Ptr, IRB.getInt(
Offset),
1549 NamePrefix +
"sroa_idx");
1550 return IRB.CreatePointerBitCastOrAddrSpaceCast(Ptr,
PointerTy,
1551 NamePrefix +
"sroa_cast");
1563 Value *OffsetPtr =
nullptr;
1564 Value *OffsetBasePtr;
1568 Value *Int8Ptr =
nullptr;
1577 auto AS = cast<PointerType>(Ptr->
getType())->getAddressSpace();
1584 if (!
GEP->accumulateConstantOffset(
DL, GEPOffset))
1587 Ptr =
GEP->getPointerOperand();
1588 if (!Visited.
insert(Ptr).second)
1595 Indices, NamePrefix)) {
1599 if (OffsetPtr && OffsetPtr != OffsetBasePtr)
1600 if (
Instruction *
I = dyn_cast<Instruction>(OffsetPtr)) {
1601 assert(
I->use_empty() &&
"Built a GEP with uses some how!");
1602 I->eraseFromParent();
1605 OffsetBasePtr = Ptr;
1619 Ptr = cast<Operator>(Ptr)->getOperand(0);
1620 }
else if (
GlobalAlias *GA = dyn_cast<GlobalAlias>(Ptr)) {
1621 if (GA->isInterposable())
1623 Ptr = GA->getAliasee();
1628 }
while (Visited.
insert(Ptr).second);
1632 Int8Ptr = IRB.CreateBitCast(
1633 Ptr, IRB.getInt8PtrTy(
PointerTy->getPointerAddressSpace()),
1634 NamePrefix +
"sroa_raw_cast");
1638 OffsetPtr = Int8PtrOffset == 0
1640 : IRB.CreateInBoundsGEP(IRB.getInt8Ty(), Int8Ptr,
1641 IRB.getInt(Int8PtrOffset),
1642 NamePrefix +
"sroa_raw_idx");
1647 if (cast<PointerType>(Ptr->
getType()) != TargetPtrTy) {
1648 Ptr = IRB.CreatePointerBitCastOrAddrSpaceCast(Ptr,
1650 NamePrefix +
"sroa_cast");
1674 if (isa<IntegerType>(OldTy) && isa<IntegerType>(NewTy)) {
1677 "We can't have the same bitwidth for different int types");
1681 if (
DL.getTypeSizeInBits(NewTy).getFixedSize() !=
1682 DL.getTypeSizeInBits(OldTy).getFixedSize())
1698 return OldAS == NewAS ||
1699 (!
DL.isNonIntegralAddressSpace(OldAS) &&
1700 !
DL.isNonIntegralAddressSpace(NewAS) &&
1701 DL.getPointerSize(OldAS) ==
DL.getPointerSize(NewAS));
1707 return !
DL.isNonIntegralPointerType(NewTy);
1711 if (!
DL.isNonIntegralPointerType(OldTy))
1734 assert(!(isa<IntegerType>(OldTy) && isa<IntegerType>(NewTy)) &&
1735 "Integer types must be the exact same to convert.");
1743 return IRB.CreateIntToPtr(IRB.CreateBitCast(V,
DL.getIntPtrType(NewTy)),
1753 return IRB.CreateBitCast(IRB.CreatePtrToInt(V,
DL.getIntPtrType(OldTy)),
1766 if (OldAS != NewAS) {
1767 assert(
DL.getPointerSize(OldAS) ==
DL.getPointerSize(NewAS));
1768 return IRB.CreateIntToPtr(IRB.CreatePtrToInt(V,
DL.getIntPtrType(OldTy)),
1773 return IRB.CreateBitCast(V, NewTy);
1786 std::max(
S.beginOffset(),
P.beginOffset()) -
P.beginOffset();
1787 uint64_t BeginIndex = BeginOffset / ElementSize;
1788 if (BeginIndex * ElementSize != BeginOffset ||
1789 BeginIndex >= cast<FixedVectorType>(Ty)->getNumElements())
1792 std::min(
S.endOffset(),
P.endOffset()) -
P.beginOffset();
1793 uint64_t EndIndex = EndOffset / ElementSize;
1794 if (EndIndex * ElementSize != EndOffset ||
1795 EndIndex > cast<FixedVectorType>(Ty)->getNumElements())
1798 assert(EndIndex > BeginIndex &&
"Empty vector!");
1799 uint64_t NumElements = EndIndex - BeginIndex;
1800 Type *SliceTy = (NumElements == 1)
1805 Type::getIntNTy(Ty->
getContext(), NumElements * ElementSize * 8);
1807 Use *U =
S.getUse();
1810 if (
MI->isVolatile())
1812 if (!
S.isSplittable())
1814 }
else if (
IntrinsicInst *II = dyn_cast<IntrinsicInst>(U->getUser())) {
1817 }
else if (
LoadInst *LI = dyn_cast<LoadInst>(U->getUser())) {
1824 if (
P.beginOffset() >
S.beginOffset() ||
P.endOffset() <
S.endOffset()) {
1830 }
else if (
StoreInst *
SI = dyn_cast<StoreInst>(U->getUser())) {
1831 if (
SI->isVolatile())
1833 Type *STy =
SI->getValueOperand()->getType();
1837 if (
P.beginOffset() >
S.beginOffset() ||
P.endOffset() <
S.endOffset()) {
1863 Type *CommonEltTy =
nullptr;
1864 bool HaveCommonEltTy =
true;
1865 auto CheckCandidateType = [&](
Type *Ty) {
1866 if (
auto *VTy = dyn_cast<VectorType>(Ty)) {
1868 if (!CandidateTys.empty()) {
1870 if (
DL.getTypeSizeInBits(VTy).getFixedSize() !=
1871 DL.getTypeSizeInBits(V).getFixedSize()) {
1872 CandidateTys.
clear();
1876 CandidateTys.push_back(VTy);
1878 CommonEltTy = VTy->getElementType();
1879 else if (CommonEltTy != VTy->getElementType())
1880 HaveCommonEltTy =
false;
1884 for (
const Slice &
S :
P)
1885 if (
S.beginOffset() ==
P.beginOffset() &&
1886 S.endOffset() ==
P.endOffset()) {
1887 if (
auto *LI = dyn_cast<LoadInst>(
S.getUse()->getUser()))
1888 CheckCandidateType(LI->
getType());
1889 else if (
auto *
SI = dyn_cast<StoreInst>(
S.getUse()->getUser()))
1890 CheckCandidateType(
SI->getValueOperand()->getType());
1894 if (CandidateTys.empty())
1901 if (!HaveCommonEltTy) {
1907 if (CandidateTys.empty())
1914 assert(
DL.getTypeSizeInBits(RHSTy).getFixedSize() ==
1915 DL.getTypeSizeInBits(LHSTy).getFixedSize() &&
1916 "Cannot have vector types of different sizes!");
1918 "All non-integer types eliminated!");
1919 assert(LHSTy->getElementType()->isIntegerTy() &&
1920 "All non-integer types eliminated!");
1921 return cast<FixedVectorType>(RHSTy)->getNumElements() <
1922 cast<FixedVectorType>(LHSTy)->getNumElements();
1926 std::unique(CandidateTys.begin(), CandidateTys.end(), RankVectorTypes),
1927 CandidateTys.end());
1933 assert(VTy->getElementType() == CommonEltTy &&
1934 "Unaccounted for element type!");
1935 assert(VTy == CandidateTys[0] &&
1936 "Different vector types with the same element type!");
1939 CandidateTys.resize(1);
1943 auto CheckVectorTypeForPromotion = [&](
VectorType *VTy) {
1945 DL.getTypeSizeInBits(VTy->getElementType()).getFixedSize();
1949 if (ElementSize % 8)
1951 assert((
DL.getTypeSizeInBits(VTy).getFixedSize() % 8) == 0 &&
1952 "vector size not a multiple of element size?");
1955 for (
const Slice &
S :
P)
1959 for (
const Slice *
S :
P.splitSliceTails())
1966 if (CheckVectorTypeForPromotion(VTy))
1980 bool &WholeAllocaOp) {
1983 uint64_t RelBegin =
S.beginOffset() - AllocBeginOffset;
1984 uint64_t RelEnd =
S.endOffset() - AllocBeginOffset;
1986 Use *U =
S.getUse();
1992 if (
IntrinsicInst *II = dyn_cast<IntrinsicInst>(U->getUser())) {
2002 if (
LoadInst *LI = dyn_cast<LoadInst>(U->getUser())) {
2006 if (
DL.getTypeStoreSize(LI->
getType()).getFixedSize() >
Size)
2010 if (
S.beginOffset() < AllocBeginOffset)
2015 if (!isa<VectorType>(LI->
getType()) && RelBegin == 0 && RelEnd ==
Size)
2016 WholeAllocaOp =
true;
2018 if (ITy->getBitWidth() <
DL.getTypeStoreSizeInBits(ITy).getFixedSize())
2020 }
else if (RelBegin != 0 || RelEnd !=
Size ||
2026 }
else if (
StoreInst *
SI = dyn_cast<StoreInst>(U->getUser())) {
2027 Type *ValueTy =
SI->getValueOperand()->getType();
2028 if (
SI->isVolatile())
2031 if (
DL.getTypeStoreSize(ValueTy).getFixedSize() >
Size)
2035 if (
S.beginOffset() < AllocBeginOffset)
2040 if (!isa<VectorType>(ValueTy) && RelBegin == 0 && RelEnd ==
Size)
2041 WholeAllocaOp =
true;
2042 if (
IntegerType *ITy = dyn_cast<IntegerType>(ValueTy)) {
2043 if (ITy->getBitWidth() <
DL.getTypeStoreSizeInBits(ITy).getFixedSize())
2045 }
else if (RelBegin != 0 || RelEnd !=
Size ||
2051 }
else if (
MemIntrinsic *
MI = dyn_cast<MemIntrinsic>(U->getUser())) {
2052 if (
MI->isVolatile() || !isa<Constant>(
MI->getLength()))
2054 if (!
S.isSplittable())
2071 uint64_t SizeInBits =
DL.getTypeSizeInBits(AllocaTy).getFixedSize();
2073 if (SizeInBits > IntegerType::MAX_INT_BITS)
2077 if (SizeInBits !=
DL.getTypeStoreSizeInBits(AllocaTy).getFixedSize())
2083 Type *IntTy = Type::getIntNTy(AllocaTy->
getContext(), SizeInBits);
2095 bool WholeAllocaOp =
P.empty() &&
DL.isLegalInteger(SizeInBits);
2097 for (
const Slice &
S :
P)
2102 for (
const Slice *
S :
P.splitSliceTails())
2107 return WholeAllocaOp;
2116 DL.getTypeStoreSize(IntTy).getFixedSize() &&
2117 "Element extends past full value");
2119 if (
DL.isBigEndian())
2120 ShAmt = 8 * (
DL.getTypeStoreSize(IntTy).getFixedSize() -
2121 DL.getTypeStoreSize(Ty).getFixedSize() -
Offset);
2123 V = IRB.CreateLShr(V, ShAmt,
Name +
".shift");
2127 "Cannot extract to a larger integer!");
2129 V = IRB.CreateTrunc(V, Ty,
Name +
".trunc");
2140 "Cannot insert a larger integer!");
2143 V = IRB.CreateZExt(V, IntTy,
Name +
".ext");
2147 DL.getTypeStoreSize(IntTy).getFixedSize() &&
2148 "Element store outside of alloca store");
2150 if (
DL.isBigEndian())
2151 ShAmt = 8 * (
DL.getTypeStoreSize(IntTy).getFixedSize() -
2152 DL.getTypeStoreSize(Ty).getFixedSize() -
Offset);
2154 V = IRB.CreateShl(V, ShAmt,
Name +
".shift");
2160 Old = IRB.CreateAnd(Old,
Mask,
Name +
".mask");
2162 V = IRB.CreateOr(Old, V,
Name +
".insert");
2170 auto *VecTy = cast<FixedVectorType>(V->
getType());
2171 unsigned NumElements = EndIndex - BeginIndex;
2172 assert(NumElements <= VecTy->getNumElements() &&
"Too many elements!");
2174 if (NumElements == VecTy->getNumElements())
2177 if (NumElements == 1) {
2178 V = IRB.CreateExtractElement(V, IRB.getInt32(BeginIndex),
2184 auto Mask = llvm::to_vector<8>(llvm::seq<int>(BeginIndex, EndIndex));
2185 V = IRB.CreateShuffleVector(V,
Mask,
Name +
".extract");
2191 unsigned BeginIndex,
const Twine &
Name) {
2193 assert(VecTy &&
"Can only insert a vector into a vector");
2198 V = IRB.CreateInsertElement(Old, V, IRB.getInt32(BeginIndex),
2204 assert(cast<FixedVectorType>(Ty)->getNumElements() <=
2205 cast<FixedVectorType>(VecTy)->getNumElements() &&
2206 "Too many elements!");
2207 if (cast<FixedVectorType>(Ty)->getNumElements() ==
2208 cast<FixedVectorType>(VecTy)->getNumElements()) {
2212 unsigned EndIndex = BeginIndex + cast<FixedVectorType>(Ty)->getNumElements();
2219 Mask.reserve(cast<FixedVectorType>(VecTy)->getNumElements());
2220 for (
unsigned i = 0;
i != cast<FixedVectorType>(VecTy)->getNumElements(); ++
i)
2221 if (
i >= BeginIndex &&
i < EndIndex)
2222 Mask.push_back(
i - BeginIndex);
2225 V = IRB.CreateShuffleVector(V,
Mask,
Name +
".expand");
2229 Mask2.
reserve(cast<FixedVectorType>(VecTy)->getNumElements());
2230 for (
unsigned i = 0;
i != cast<FixedVectorType>(VecTy)->getNumElements(); ++
i)
2231 Mask2.push_back(IRB.getInt1(
i >= BeginIndex &&
i < EndIndex));
2256 const uint64_t NewAllocaBeginOffset, NewAllocaEndOffset;
2285 uint64_t NewBeginOffset = 0, NewEndOffset = 0;
2288 bool IsSplittable =
false;
2289 bool IsSplit =
false;
2290 Use *OldUse =
nullptr;
2305 uint64_t NewAllocaEndOffset,
bool IsIntegerPromotable,
2309 :
DL(
DL), AS(AS),
Pass(
Pass), OldAI(OldAI), NewAI(NewAI),
2310 NewAllocaBeginOffset(NewAllocaBeginOffset),
2311 NewAllocaEndOffset(NewAllocaEndOffset),
2312 NewAllocaTy(NewAI.getAllocatedType()),
2315 ?
Type::getIntNTy(NewAI.getContext(),
2316 DL.getTypeSizeInBits(NewAI.getAllocatedType())
2319 VecTy(PromotableVecTy),
2320 ElementTy(VecTy ? VecTy->getElementType() : nullptr),
2321 ElementSize(VecTy ?
DL.getTypeSizeInBits(ElementTy).getFixedSize() / 8
2323 PHIUsers(PHIUsers), SelectUsers(SelectUsers),
2326 assert((
DL.getTypeSizeInBits(ElementTy).getFixedSize() % 8) == 0 &&
2327 "Only multiple-of-8 sized vector elements are viable");
2330 assert((!IntTy && !VecTy) || (IntTy && !VecTy) || (!IntTy && VecTy));
2334 bool CanSROA =
true;
2335 BeginOffset =
I->beginOffset();
2336 EndOffset =
I->endOffset();
2337 IsSplittable =
I->isSplittable();
2339 BeginOffset < NewAllocaBeginOffset || EndOffset > NewAllocaEndOffset;
2340 LLVM_DEBUG(
dbgs() <<
" rewriting " << (IsSplit ?
"split " :
""));
2345 assert(BeginOffset < NewAllocaEndOffset);
2346 assert(EndOffset > NewAllocaBeginOffset);
2347 NewBeginOffset =
std::max(BeginOffset, NewAllocaBeginOffset);
2348 NewEndOffset =
std::min(EndOffset, NewAllocaEndOffset);
2350 SliceSize = NewEndOffset - NewBeginOffset;
2352 OldUse =
I->getUse();
2353 OldPtr = cast<Instruction>(OldUse->get());
2355 Instruction *OldUserI = cast<Instruction>(OldUse->getUser());
2356 IRB.SetInsertPoint(OldUserI);
2357 IRB.SetCurrentDebugLocation(OldUserI->
getDebugLoc());
2358 IRB.getInserter().SetNamePrefix(
2361 CanSROA &= visit(cast<Instruction>(OldUse->getUser()));
2380 assert(IsSplit || BeginOffset == NewBeginOffset);
2386 size_t LastSROAPrefix = OldName.
rfind(
".sroa.");
2387 if (LastSROAPrefix != StringRef::npos) {
2388 OldName = OldName.
substr(LastSROAPrefix + strlen(
".sroa."));
2391 if (IndexEnd != StringRef::npos && OldName[IndexEnd] ==
'.') {
2393 OldName = OldName.
substr(IndexEnd + 1);
2395 if (OffsetEnd != StringRef::npos && OldName[OffsetEnd] ==
'.')
2397 OldName = OldName.
substr(OffsetEnd + 1);
2401 OldName = OldName.
substr(0, OldName.
find(
".sroa_"));
2408 Twine(OldName) +
"."
2420 Align getSliceAlign() {
2422 NewBeginOffset - NewAllocaBeginOffset);
2426 assert(VecTy &&
"Can only call getIndex when rewriting a vector");
2428 assert(RelOffset / ElementSize < UINT32_MAX &&
"Index out of bounds");
2434 void deleteIfTriviallyDead(
Value *V) {
2437 Pass.DeadInsts.push_back(
I);
2441 unsigned BeginIndex = getIndex(NewBeginOffset);
2442 unsigned EndIndex = getIndex(NewEndOffset);
2443 assert(EndIndex > BeginIndex &&
"Empty vector!");
2448 Load->copyMetadata(LI, {LLVMContext::MD_mem_parallel_loop_access,
2449 LLVMContext::MD_access_group});
2454 assert(IntTy &&
"We cannot insert an integer to the alloca");
2459 assert(NewBeginOffset >= NewAllocaBeginOffset &&
"Out of bounds offset");
2461 if (
Offset > 0 || NewEndOffset < NewAllocaEndOffset) {
2470 assert(cast<IntegerType>(LI.
getType())->getBitWidth() >= SliceSize * 8 &&
2471 "Can only handle an extract for an overly wide load");
2472 if (cast<IntegerType>(LI.
getType())->getBitWidth() > SliceSize * 8)
2473 V = IRB.CreateZExt(V, LI.
getType());
2486 Type *TargetTy = IsSplit ? Type::getIntNTy(LI.
getContext(), SliceSize * 8)
2488 const bool IsLoadPastEnd =
2489 DL.getTypeStoreSize(TargetTy).getFixedSize() > SliceSize;
2490 bool IsPtrAdjusted =
false;
2493 V = rewriteVectorizedLoadInst(LI);
2495 V = rewriteIntegerLoad(LI);
2496 }
else if (NewBeginOffset == NewAllocaBeginOffset &&
2497 NewEndOffset == NewAllocaEndOffset &&
2530 if (
auto *AITy = dyn_cast<IntegerType>(NewAllocaTy))
2531 if (
auto *TITy = dyn_cast<IntegerType>(TargetTy))
2532 if (AITy->getBitWidth() < TITy->getBitWidth()) {
2533 V = IRB.CreateZExt(V, TITy,
"load.ext");
2534 if (
DL.isBigEndian())
2535 V = IRB.CreateShl(V, TITy->getBitWidth() - AITy->getBitWidth(),
2541 IRB.CreateAlignedLoad(TargetTy, getNewAllocaSlicePtr(IRB, LTy),
2547 NewLI->
copyMetadata(LI, {LLVMContext::MD_mem_parallel_loop_access,
2548 LLVMContext::MD_access_group});
2551 IsPtrAdjusted =
true;
2558 "Only integer type loads and stores are split");
2559 assert(SliceSize <
DL.getTypeStoreSize(LI.
getType()).getFixedSize() &&
2560 "Split load isn't smaller than original load");
2562 "Non-byte-multiple bit width");
2572 V =
insertInteger(
DL, IRB, Placeholder, V, NewBeginOffset - BeginOffset,
2575 Placeholder->replaceAllUsesWith(&LI);
2576 Placeholder->deleteValue();
2581 Pass.DeadInsts.push_back(&LI);
2582 deleteIfTriviallyDead(OldOp);
2590 unsigned BeginIndex = getIndex(NewBeginOffset);
2591 unsigned EndIndex = getIndex(NewEndOffset);
2592 assert(EndIndex > BeginIndex &&
"Empty vector!");
2593 unsigned NumElements = EndIndex - BeginIndex;
2594 assert(NumElements <= cast<FixedVectorType>(VecTy)->getNumElements() &&
2595 "Too many elements!");
2596 Type *SliceTy = (NumElements == 1)
2608 Store->copyMetadata(
SI, {LLVMContext::MD_mem_parallel_loop_access,
2609 LLVMContext::MD_access_group});
2611 Store->setAAMetadata(AATags.
shift(NewBeginOffset - BeginOffset));
2612 Pass.DeadInsts.push_back(&
SI);
2619 assert(IntTy &&
"We cannot extract an integer from the alloca");
2621 if (
DL.getTypeSizeInBits(V->
getType()).getFixedSize() !=
2626 assert(BeginOffset >= NewAllocaBeginOffset &&
"Out of bounds offset");
2632 Store->copyMetadata(
SI, {LLVMContext::MD_mem_parallel_loop_access,
2633 LLVMContext::MD_access_group});
2635 Store->setAAMetadata(AATags.
shift(NewBeginOffset - BeginOffset));
2636 Pass.DeadInsts.push_back(&
SI);
2643 Value *OldOp =
SI.getOperand(1);
2647 Value *V =
SI.getValueOperand();
2653 Pass.PostPromotionWorklist.insert(AI);
2655 if (SliceSize <
DL.getTypeStoreSize(V->
getType()).getFixedSize()) {
2658 "Only integer type loads and stores are split");
2660 "Non-byte-multiple bit width");
2661 IntegerType *NarrowTy = Type::getIntNTy(
SI.getContext(), SliceSize * 8);
2667 return rewriteVectorizedStoreInst(V,
SI, OldOp, AATags);
2669 return rewriteIntegerStore(V,
SI, AATags);
2671 const bool IsStorePastEnd =
2672 DL.getTypeStoreSize(V->
getType()).getFixedSize() > SliceSize;
2674 if (NewBeginOffset == NewAllocaBeginOffset &&
2675 NewEndOffset == NewAllocaEndOffset &&
2682 if (
auto *VITy = dyn_cast<IntegerType>(V->
getType()))
2683 if (
auto *AITy = dyn_cast<IntegerType>(NewAllocaTy))
2684 if (VITy->getBitWidth() > AITy->getBitWidth()) {
2685 if (
DL.isBigEndian())
2686 V = IRB.CreateLShr(V, VITy->getBitWidth() - AITy->getBitWidth(),
2688 V = IRB.CreateTrunc(V, AITy,
"load.trunc");
2693 IRB.CreateAlignedStore(V, &NewAI, NewAI.
getAlign(),
SI.isVolatile());
2695 unsigned AS =
SI.getPointerAddressSpace();
2698 IRB.CreateAlignedStore(V, NewPtr, getSliceAlign(),
SI.isVolatile());
2700 NewSI->
copyMetadata(
SI, {LLVMContext::MD_mem_parallel_loop_access,
2701 LLVMContext::MD_access_group});
2704 if (
SI.isVolatile())
2708 Pass.DeadInsts.push_back(&
SI);
2709 deleteIfTriviallyDead(OldOp);
2727 assert(
Size > 0 &&
"Expected a positive number of bytes.");
2735 IRB.CreateZExt(V, SplatIntTy,
"zext"),
2736 ConstantExpr::getUDiv(
2737 Constant::getAllOnesValue(SplatIntTy),
2738 ConstantExpr::getZExt(Constant::getAllOnesValue(V->
getType()),
2746 V = IRB.CreateVectorSplat(NumElements, V,
"vsplat");
2759 if (!isa<ConstantInt>(II.
getLength())) {
2761 assert(NewBeginOffset == BeginOffset);
2765 deleteIfTriviallyDead(OldPtr);
2770 Pass.DeadInsts.push_back(&II);
2775 const bool CanContinue = [&]() {
2778 if (BeginOffset > NewAllocaBeginOffset ||
2779 EndOffset < NewAllocaEndOffset)
2783 const uint64_t Len =
C->getLimitedValue();
2786 auto *Int8Ty = IntegerType::getInt8Ty(NewAI.
getContext());
2789 DL.isLegalInteger(
DL.getTypeSizeInBits(ScalarTy).getFixedSize());
2801 New->setAAMetadata(AATags.
shift(NewBeginOffset - BeginOffset));
2815 assert(ElementTy == ScalarTy);
2817 unsigned BeginIndex = getIndex(NewBeginOffset);
2818 unsigned EndIndex = getIndex(NewEndOffset);
2819 assert(EndIndex > BeginIndex &&
"Empty vector!");
2820 unsigned NumElements = EndIndex - BeginIndex;
2821 assert(NumElements <= cast<FixedVectorType>(VecTy)->getNumElements() &&
2822 "Too many elements!");
2824 Value *Splat = getIntegerSplat(
2825 II.
getValue(),
DL.getTypeSizeInBits(ElementTy).getFixedSize() / 8);
2827 if (NumElements > 1)
2841 if (IntTy && (BeginOffset != NewAllocaBeginOffset ||
2842 EndOffset != NewAllocaBeginOffset)) {
2850 "Wrong type for an alloca wide integer!");
2855 assert(NewBeginOffset == NewAllocaBeginOffset);
2856 assert(NewEndOffset == NewAllocaEndOffset);
2859 DL.getTypeSizeInBits(ScalarTy).getFixedSize() / 8);
2860 if (
VectorType *AllocaVecTy = dyn_cast<VectorType>(AllocaTy))
2862 V, cast<FixedVectorType>(AllocaVecTy)->getNumElements());
2869 New->copyMetadata(II, {LLVMContext::MD_mem_parallel_loop_access,
2870 LLVMContext::MD_access_group});
2872 New->setAAMetadata(AATags.
shift(NewBeginOffset - BeginOffset));
2898 if (!IsSplittable) {
2899 Value *AdjustedPtr = getNewAllocaSlicePtr(IRB, OldPtr->
getType());
2910 deleteIfTriviallyDead(OldPtr);
2923 (BeginOffset > NewAllocaBeginOffset || EndOffset < NewAllocaEndOffset ||
2931 if (EmitMemCpy && &OldAI == &NewAI) {
2933 assert(NewBeginOffset == BeginOffset);
2936 if (NewEndOffset != EndOffset)
2938 NewEndOffset - NewBeginOffset));
2942 Pass.DeadInsts.push_back(&II);
2949 assert(AI != &OldAI && AI != &NewAI &&
2950 "Splittable transfers cannot reach the same alloca on both ends.");
2951 Pass.Worklist.insert(AI);
2958 unsigned OffsetWidth =
DL.getIndexSizeInBits(OtherAS);
2959 APInt OtherOffset(OffsetWidth, NewBeginOffset - BeginOffset);
2963 commonAlignment(OtherAlign, OtherOffset.zextOrTrunc(64).getZExtValue());
2971 Value *OurPtr = getNewAllocaSlicePtr(IRB, OldPtr->
getType());
2975 Value *DestPtr, *SrcPtr;
2980 DestAlign = SliceAlign;
2982 SrcAlign = OtherAlign;
2985 DestAlign = OtherAlign;
2987 SrcAlign = SliceAlign;
2989 CallInst *
New = IRB.CreateMemCpy(DestPtr, DestAlign, SrcPtr, SrcAlign,
2992 New->setAAMetadata(AATags.
shift(NewBeginOffset - BeginOffset));
2997 bool IsWholeAlloca = NewBeginOffset == NewAllocaBeginOffset &&
2998 NewEndOffset == NewAllocaEndOffset;
3000 unsigned BeginIndex = VecTy ? getIndex(NewBeginOffset) : 0;
3001 unsigned EndIndex = VecTy ? getIndex(NewEndOffset) : 0;
3002 unsigned NumElements = EndIndex - BeginIndex;
3004 IntTy ? Type::getIntNTy(IntTy->
getContext(),
Size * 8) : nullptr;
3009 if (VecTy && !IsWholeAlloca) {
3010 if (NumElements == 1)
3014 }
else if (IntTy && !IsWholeAlloca) {
3017 OtherTy = NewAllocaTy;
3024 Value *DstPtr = &NewAI;
3032 if (VecTy && !IsWholeAlloca && !IsDest) {
3036 }
else if (IntTy && !IsWholeAlloca && !IsDest) {
3043 LoadInst *
Load = IRB.CreateAlignedLoad(OtherTy, SrcPtr, SrcAlign,
3045 Load->copyMetadata(II, {LLVMContext::MD_mem_parallel_loop_access,
3046 LLVMContext::MD_access_group});
3048 Load->setAAMetadata(AATags.
shift(NewBeginOffset - BeginOffset));
3052 if (VecTy && !IsWholeAlloca && IsDest) {
3056 }
else if (IntTy && !IsWholeAlloca && IsDest) {
3066 IRB.CreateAlignedStore(Src, DstPtr, DstAlign, II.
isVolatile()));
3067 Store->copyMetadata(II, {LLVMContext::MD_mem_parallel_loop_access,
3068 LLVMContext::MD_access_group});
3070 Store->setAAMetadata(AATags.
shift(NewBeginOffset - BeginOffset));
3077 "Unexpected intrinsic!");
3081 Pass.DeadInsts.push_back(&II);
3098 if (NewBeginOffset != NewAllocaBeginOffset ||
3099 NewEndOffset != NewAllocaEndOffset)
3104 NewEndOffset - NewBeginOffset);
3111 New = IRB.CreateLifetimeStart(Ptr,
Size);
3113 New = IRB.CreateLifetimeEnd(Ptr,
Size);
3128 Uses.push_back(&Root);
3132 if (
LoadInst *LI = dyn_cast<LoadInst>(
I)) {
3137 SI->setAlignment(
std::min(
SI->getAlign(), getSliceAlign()));
3141 assert(isa<BitCastInst>(
I) || isa<AddrSpaceCastInst>(
I) ||
3142 isa<PHINode>(
I) || isa<SelectInst>(
I) ||
3143 isa<GetElementPtrInst>(
I));
3144 for (
User *U :
I->users())
3145 if (Visited.
insert(cast<Instruction>(U)).second)
3146 Uses.push_back(cast<Instruction>(U));
3147 }
while (!
Uses.empty());
3150 bool visitPHINode(
PHINode &PN) {
3152 assert(BeginOffset >= NewAllocaBeginOffset &&
"PHIs are unsplittable");
3153 assert(EndOffset <= NewAllocaEndOffset &&
"PHIs are unsplittable");
3160 if (isa<PHINode>(OldPtr))
3163 IRB.SetInsertPoint(OldPtr);
3164 IRB.SetCurrentDebugLocation(OldPtr->
getDebugLoc());
3166 Value *NewPtr = getNewAllocaSlicePtr(IRB, OldPtr->
getType());
3171 deleteIfTriviallyDead(OldPtr);
3174 fixLoadStoreAlign(PN);
3185 assert((
SI.getTrueValue() == OldPtr ||
SI.getFalseValue() == OldPtr) &&
3186 "Pointer isn't an operand!");
3187 assert(BeginOffset >= NewAllocaBeginOffset &&
"Selects are unsplittable");
3188 assert(EndOffset <= NewAllocaEndOffset &&
"Selects are unsplittable");
3190 Value *NewPtr = getNewAllocaSlicePtr(IRB, OldPtr->
getType());
3192 if (
SI.getOperand(1) == OldPtr)
3193 SI.setOperand(1, NewPtr);
3194 if (
SI.getOperand(2) == OldPtr)
3195 SI.setOperand(2, NewPtr);
3198 deleteIfTriviallyDead(OldPtr);
3201 fixLoadStoreAlign(
SI);
3218 class AggLoadStoreRewriter :
public InstVisitor<AggLoadStoreRewriter, bool> {
3220 friend class InstVisitor<AggLoadStoreRewriter, bool>;
3238 AggLoadStoreRewriter(
const DataLayout &
DL, IRBuilderTy &IRB)
3239 :
DL(
DL), IRB(IRB) {}
3246 bool Changed =
false;
3247 while (!
Queue.empty()) {
3248 U =
Queue.pop_back_val();
3249 Changed |= visit(cast<Instruction>(U->getUser()));
3258 for (
Use &U :
I.uses())
3260 Queue.push_back(&U);
3264 bool visitInstruction(
Instruction &
I) {
return false; }
3267 template <
typename Derived>
class OpSplitter {
3298 : IRB(IRB), GEPIndices(1, IRB.getInt32(0)), Ptr(Ptr), BaseTy(BaseTy),
3299 BaseAlign(BaseAlign),
DL(
DL) {
3300 IRB.SetInsertPoint(InsertionPoint);
3319 unsigned Offset =
DL.getIndexedOffsetInType(BaseTy, GEPIndices);
3320 return static_cast<Derived *
>(
this)->emitFunc(
3324 if (
ArrayType *ATy = dyn_cast<ArrayType>(Ty)) {
3325 unsigned OldSize = Indices.size();
3327 for (
unsigned Idx = 0, Size = ATy->getNumElements(); Idx !=
Size;
3329 assert(Indices.size() == OldSize &&
"Did not return to the old size");
3330 Indices.push_back(Idx);
3331 GEPIndices.push_back(IRB.getInt32(Idx));
3332 emitSplitOps(ATy->getElementType(), Agg,
Name +
"." +
Twine(Idx));
3333 GEPIndices.pop_back();
3339 if (
StructType *STy = dyn_cast<StructType>(Ty)) {
3340 unsigned OldSize = Indices.size();
3342 for (
unsigned Idx = 0, Size = STy->getNumElements(); Idx !=
Size;
3344 assert(Indices.size() == OldSize &&
"Did not return to the old size");
3345 Indices.push_back(Idx);
3346 GEPIndices.push_back(IRB.getInt32(Idx));
3347 emitSplitOps(STy->getElementType(Idx), Agg,
Name +
"." +
Twine(Idx));
3348 GEPIndices.pop_back();
3358 struct LoadOpSplitter :
public OpSplitter<LoadOpSplitter> {
3364 : OpSplitter<LoadOpSplitter>(InsertionPoint, Ptr, BaseTy, BaseAlign,
DL,
3374 IRB.CreateInBoundsGEP(BaseTy, Ptr, GEPIndices,
Name +
".gep");
3376 IRB.CreateAlignedLoad(Ty,
GEP, Alignment,
Name +
".load");
3381 GEPOperator::accumulateConstantOffset(BaseTy, GEPIndices,
DL, Offset))
3384 Agg = IRB.CreateInsertValue(Agg,
Load, Indices,
Name +
".insert");
3406 struct StoreOpSplitter :
public OpSplitter<StoreOpSplitter> {
3410 : OpSplitter<StoreOpSplitter>(InsertionPoint, Ptr, BaseTy, BaseAlign,
3422 Value *ExtractValue =
3423 IRB.CreateExtractValue(Agg, Indices,
Name +
".extract");
3424 Value *InBoundsGEP =
3425 IRB.CreateInBoundsGEP(BaseTy, Ptr, GEPIndices,
Name +
".gep");
3427 IRB.CreateAlignedStore(ExtractValue, InBoundsGEP, Alignment);
3432 GEPOperator::accumulateConstantOffset(BaseTy, GEPIndices,
DL, Offset))
3440 if (!
SI.isSimple() ||
SI.getPointerOperand() != *U)
3442 Value *V =
SI.getValueOperand();
3448 StoreOpSplitter Splitter(&
SI, *U, V->
getType(),
SI.getAAMetadata(),
3452 SI.eraseFromParent();
3474 <<
"\n original: " << *Sel
3477 IRB.SetInsertPoint(&GEPI);
3483 Value *NTrue = IRB.CreateGEP(Ty, True, Index, True->
getName() +
".sroa.gep",
3488 Value *NFalse = IRB.CreateGEP(Ty, False, Index,
3489 False->
getName() +
".sroa.gep", IsInBounds);
3492 Sel->
getName() +
".sroa.sel");
3493 Visited.
erase(&GEPI);
3498 enqueueUsers(*NSelI);
3502 <<
"\n " << *NSel <<
'\n');
3515 { Instruction *I = dyn_cast<Instruction>(In);
3516 return !I || isa<GetElementPtrInst>(I) || isa<PHINode>(I) ||
3517 succ_empty(I->getParent()) ||
3518 !I->getParent()->isLegalToHoistInto();
3523 <<
"\n original: " << *PHI
3531 PHI->
getName() +
".sroa.phi");
3534 Value *NewVal =
nullptr;
3541 IRB.SetInsertPoint(
In->getParent(), std::next(
In->getIterator()));
3543 NewVal = IRB.CreateGEP(Ty,
In, Index,
In->getName() +
".sroa.gep",
3549 Visited.
erase(&GEPI);
3553 enqueueUsers(*NewPN);
3557 dbgs() <<
"\n " << *NewPN <<
'\n');
3564 foldGEPSelect(GEPI))
3575 bool visitPHINode(
PHINode &PN) {
3597 uint64_t AllocSize =
DL.getTypeAllocSize(Ty).getFixedSize();
3601 if (
ArrayType *ArrTy = dyn_cast<ArrayType>(Ty)) {
3602 InnerTy = ArrTy->getElementType();
3603 }
else if (
StructType *STy = dyn_cast<StructType>(Ty)) {
3606 InnerTy = STy->getElementType(Index);
3611 if (AllocSize >
DL.getTypeAllocSize(InnerTy).getFixedSize() ||
3612 TypeSize >
DL.getTypeSizeInBits(InnerTy).getFixedSize())
3633 if (Offset == 0 &&
DL.getTypeAllocSize(Ty).getFixedSize() == Size)
3635 if (Offset >
DL.getTypeAllocSize(Ty).getFixedSize() ||
3636 (
DL.getTypeAllocSize(Ty).getFixedSize() - Offset) < Size)
3639 if (isa<ArrayType>(Ty) || isa<VectorType>(Ty)) {
3642 if (
auto *AT = dyn_cast<ArrayType>(Ty)) {
3643 ElementTy = AT->getElementType();
3644 TyNumElements = AT->getNumElements();
3648 auto *VT = cast<FixedVectorType>(Ty);
3649 ElementTy = VT->getElementType();
3650 TyNumElements = VT->getNumElements();
3652 uint64_t ElementSize =
DL.getTypeAllocSize(ElementTy).getFixedSize();
3653 uint64_t NumSkippedElements = Offset / ElementSize;
3654 if (NumSkippedElements >= TyNumElements)
3656 Offset -= NumSkippedElements * ElementSize;
3659 if (Offset > 0 || Size < ElementSize) {
3661 if ((Offset + Size) > ElementSize)
3668 if (Size == ElementSize)
3670 assert(Size > ElementSize);
3671 uint64_t NumElements = Size / ElementSize;
3672 if (NumElements * ElementSize != Size)
3684 uint64_t EndOffset = Offset + Size;
3692 uint64_t ElementSize =
DL.getTypeAllocSize(ElementTy).getFixedSize();
3693 if (Offset >= ElementSize)
3697 if (Offset > 0 || Size < ElementSize) {
3698 if ((Offset + Size) > ElementSize)
3704 if (Size == ElementSize)
3711 if (Index == EndIndex)
3721 assert(Index < EndIndex);
3779 struct SplitOffsets {
3781 std::vector<uint64_t> Splits;
3798 LLVM_DEBUG(
dbgs() <<
" Searching for candidate loads and stores\n");
3800 for (Slice &
S :
P) {
3802 if (!
S.isSplittable() ||
S.endOffset() <=
P.endOffset()) {
3806 if (
auto *LI = dyn_cast<LoadInst>(
I))
3807 UnsplittableLoads.
insert(LI);
3808 else if (
auto *
SI = dyn_cast<StoreInst>(
I))
3809 if (
auto *LI = dyn_cast<LoadInst>(
SI->getValueOperand()))
3810 UnsplittableLoads.
insert(LI);
3813 assert(
P.endOffset() >
S.beginOffset() &&
3814 "Empty or backwards partition!");
3817 if (
auto *LI = dyn_cast<LoadInst>(
I)) {
3823 auto IsLoadSimplyStored = [](
LoadInst *LI) {
3825 auto *
SI = dyn_cast<StoreInst>(LU);
3826 if (!
SI || !
SI->isSimple())
3831 if (!IsLoadSimplyStored(LI)) {
3832 UnsplittableLoads.
insert(LI);
3836 Loads.push_back(LI);
3837 }
else if (
auto *
SI = dyn_cast<StoreInst>(
I)) {
3838 if (
S.getUse() != &
SI->getOperandUse(
SI->getPointerOperandIndex()))
3841 auto *StoredLoad = dyn_cast<LoadInst>(
SI->getValueOperand());
3842 if (!StoredLoad || !StoredLoad->isSimple())
3844 assert(!
SI->isVolatile() &&
"Cannot split volatile stores!");
3846 Stores.push_back(
SI);
3854 auto &
Offsets = SplitOffsetsMap[
I];
3856 "Should not have splits the first time we see an instruction!");
3858 Offsets.Splits.push_back(
P.endOffset() -
S.beginOffset());
3863 for (Slice *
S :
P.splitSliceTails()) {
3864 auto SplitOffsetsMapI =
3865 SplitOffsetsMap.
find(cast<Instruction>(
S->getUse()->getUser()));
3866 if (SplitOffsetsMapI == SplitOffsetsMap.
end())
3868 auto &
Offsets = SplitOffsetsMapI->second;
3872 "Cannot have an empty set of splits on the second partition!");
3874 P.beginOffset() -
Offsets.S->beginOffset() &&
3875 "Previous split does not end where this one begins!");
3879 if (
S->endOffset() >
P.endOffset())
3891 auto *LI = cast<LoadInst>(
SI->getValueOperand());
3894 if (UnsplittableLoads.
count(LI))
3897 auto LoadOffsetsI = SplitOffsetsMap.
find(LI);
3898 if (LoadOffsetsI == SplitOffsetsMap.
end())
3900 auto &LoadOffsets = LoadOffsetsI->second;
3903 auto &StoreOffsets = SplitOffsetsMap[
SI];
3908 if (LoadOffsets.Splits == StoreOffsets.Splits)
3912 <<
" " << *LI <<
"\n"
3913 <<
" " << *
SI <<
"\n");
3919 UnsplittableLoads.
insert(LI);
3927 auto *LI = cast<LoadInst>(
SI->getValueOperand());
3928 return UnsplittableLoads.
count(LI);
3933 return UnsplittableLoads.
count(LI);
3938 if (Loads.empty() && Stores.empty())
3943 IRBuilderTy IRB(&AI);
3961 std::vector<LoadInst *> SplitLoads;
3966 auto &
Offsets = SplitOffsetsMap[LI];
3967 unsigned SliceSize =
Offsets.S->endOffset() -
Offsets.S->beginOffset();
3969 "Load must have type size equal to store size");
3971 "Load must be >= slice size");
3974 assert(BaseOffset + SliceSize > BaseOffset &&
3975 "Cannot represent alloca access size using 64-bit integers!");
3978 IRB.SetInsertPoint(LI);
3985 auto *PartTy = Type::getIntNTy(LI->
getContext(), PartSize * 8);
3987 auto *PartPtrTy = PartTy->getPointerTo(AS);
3988 LoadInst *PLoad = IRB.CreateAlignedLoad(
3991 APInt(
DL.getIndexSizeInBits(AS), PartOffset),
3992 PartPtrTy,
BasePtr->getName() +
"."),
3995 PLoad->
copyMetadata(*LI, {LLVMContext::MD_mem_parallel_loop_access,
3996 LLVMContext::MD_access_group});
4000 SplitLoads.push_back(PLoad);
4003 NewSlices.push_back(
4004 Slice(BaseOffset + PartOffset, BaseOffset + PartOffset + PartSize,
4007 LLVM_DEBUG(
dbgs() <<
" new slice [" << NewSlices.back().beginOffset()
4008 <<
", " << NewSlices.back().endOffset()
4009 <<
"): " << *PLoad <<
"\n");
4016 PartOffset =
Offsets.Splits[Idx];
4018 PartSize = (Idx <
Size ?
Offsets.Splits[Idx] : SliceSize) - PartOffset;
4024 bool DeferredStores =
false;
4027 if (!Stores.empty() && SplitOffsetsMap.
count(
SI)) {
4028 DeferredStores =
true;
4034 Value *StoreBasePtr =
SI->getPointerOperand();
4035 IRB.SetInsertPoint(
SI);
4039 for (
int Idx = 0, Size = SplitLoads.size(); Idx < Size; ++Idx) {
4045 auto AS =
SI->getPointerAddressSpace();
4046 StoreInst *PStore = IRB.CreateAlignedStore(
4049 APInt(
DL.getIndexSizeInBits(AS), PartOffset),
4050 PartPtrTy, StoreBasePtr->
getName() +
"."),
4053 PStore->
copyMetadata(*
SI, {LLVMContext::MD_mem_parallel_loop_access,
4054 LLVMContext::MD_access_group});
4055 LLVM_DEBUG(
dbgs() <<
" +" << PartOffset <<
":" << *PStore <<
"\n");
4062 if (
AllocaInst *OtherAI = dyn_cast<AllocaInst>(StoreBasePtr)) {
4063 ResplitPromotableAllocas.
insert(OtherAI);
4064 Worklist.insert(OtherAI);
4065 }
else if (
AllocaInst *OtherAI = dyn_cast<AllocaInst>(
4067 Worklist.insert(OtherAI);
4071 DeadInsts.push_back(
SI);
4079 DeadInsts.push_back(LI);
4089 auto *LI = cast<LoadInst>(
SI->getValueOperand());
4093 assert(StoreSize > 0 &&
"Cannot have a zero-sized integer store!");
4097 "Slice size should always match load size exactly!");
4099 assert(BaseOffset + StoreSize > BaseOffset &&
4100 "Cannot represent alloca access size using 64-bit integers!");
4103 Instruction *StoreBasePtr = cast<Instruction>(
SI->getPointerOperand());
4108 auto SplitLoadsMapI = SplitLoadsMap.
find(LI);
4109 std::vector<LoadInst *> *SplitLoads =
nullptr;
4110 if (SplitLoadsMapI != SplitLoadsMap.
end()) {
4111 SplitLoads = &SplitLoadsMapI->second;
4113 "Too few split loads for the number of splits in the store!");
4121 auto *PartTy = Type::getIntNTy(Ty->
getContext(), PartSize * 8);
4123 auto *StorePartPtrTy = PartTy->getPointerTo(
SI->getPointerAddressSpace());
4128 PLoad = (*SplitLoads)[Idx];
4130 IRB.SetInsertPoint(LI);
4132 PLoad = IRB.CreateAlignedLoad(
4135 APInt(
DL.getIndexSizeInBits(AS), PartOffset),
4136 LoadPartPtrTy, LoadBasePtr->
getName() +
"."),
4139 PLoad->
copyMetadata(*LI, {LLVMContext::MD_mem_parallel_loop_access,
4140 LLVMContext::MD_access_group});
4144 IRB.SetInsertPoint(
SI);
4145 auto AS =
SI->getPointerAddressSpace();
4146 StoreInst *PStore = IRB.CreateAlignedStore(
4149 APInt(
DL.getIndexSizeInBits(AS), PartOffset),
4150 StorePartPtrTy, StoreBasePtr->
getName() +
"."),
4153 PStore->
copyMetadata(*
SI, {LLVMContext::MD_mem_parallel_loop_access,
4154 LLVMContext::MD_access_group});
4157 NewSlices.push_back(
4158 Slice(BaseOffset + PartOffset, BaseOffset + PartOffset + PartSize,
4161 LLVM_DEBUG(
dbgs() <<
" new slice [" << NewSlices.back().beginOffset()
4162 <<
", " << NewSlices.back().endOffset()
4163 <<
"): " << *PStore <<
"\n");
4173 PartOffset =
Offsets.Splits[Idx];
4175 PartSize = (Idx <
Size ?
Offsets.Splits[Idx] : StoreSize) - PartOffset;
4184 if (
AllocaInst *OtherAI = dyn_cast<AllocaInst>(LoadBasePtr)) {
4185 assert(OtherAI != &AI &&
"We can't re-split our own alloca!");
4186 ResplitPromotableAllocas.
insert(OtherAI);
4187 Worklist.insert(OtherAI);
4188 }
else if (
AllocaInst *OtherAI = dyn_cast<AllocaInst>(
4190 assert(OtherAI != &AI &&
"We can't re-split our own alloca!");
4191 Worklist.insert(OtherAI);
4206 DeadInsts.push_back(LI);
4208 DeadInsts.push_back(
SI);
4228 return ResplitPromotableAllocas.
count(AI);
4249 Type *SliceTy =
nullptr;
4251 std::pair<Type *, IntegerType *> CommonUseTy =
4254 if (CommonUseTy.first)
4255 if (
DL.getTypeAllocSize(CommonUseTy.first).getFixedSize() >=
P.size())
4256 SliceTy = CommonUseTy.first;
4260 P.beginOffset(),
P.size()))
4261 SliceTy = TypePartitionTy;
4263 if (!SliceTy && CommonUseTy.second)
4264 if (
DL.getTypeAllocSize(CommonUseTy.second).getFixedSize() >=
P.size())
4265 SliceTy = CommonUseTy.second;
4266 if ((!SliceTy || (SliceTy->
isArrayTy() &&
4268 DL.isLegalInteger(
P.size() * 8))
4269 SliceTy = Type::getIntNTy(*
C,
P.size() * 8);
4272 assert(
DL.getTypeAllocSize(SliceTy).getFixedSize() >=
P.size());
4298 const bool IsUnconstrained =
Alignment <=
DL.getABITypeAlign(SliceTy);
4301 IsUnconstrained ?
DL.getPrefTypeAlign(SliceTy) : Alignment,
4309 <<
"[" <<
P.beginOffset() <<
"," <<
P.endOffset()
4310 <<
") to: " << *NewAI <<
"\n");
4315 unsigned PPWOldSize = PostPromotionWorklist.size();
4316 unsigned NumUses = 0;
4321 P.endOffset(), IsIntegerPromotable, VecTy,
4322 PHIUsers, SelectUsers);
4323 bool Promotable =
true;
4324 for (Slice *
S :
P.splitSliceTails()) {
4328 for (Slice &
S :
P) {
4333 NumAllocaPartitionUses += NumUses;
4334 MaxUsesPerAllocaPartition.updateMax(NumUses);
4342 SelectUsers.
clear();
4350 SelectUsers.clear();
4356 auto *OldInst = dyn_cast<Instruction>(U->get());
4357 Value::dropDroppableUse(*U);
4360 DeadInsts.push_back(OldInst);
4362 if (PHIUsers.empty() && SelectUsers.empty()) {
4364 PromotableAllocas.push_back(NewAI);
4369 for (
PHINode *PHIUser : PHIUsers)
4370 SpeculatablePHIs.insert(PHIUser);
4372 SpeculatableSelects.insert(SelectUser);
4373 Worklist.insert(NewAI);
4377 while (PostPromotionWorklist.size() > PPWOldSize)
4378 PostPromotionWorklist.pop_back();
4388 Worklist.insert(NewAI);
4400 unsigned NumPartitions = 0;
4401 bool Changed =
false;
4405 Changed |= presplitLoadsAndStores(AI, AS);
4413 bool IsSorted =
true;
4417 const uint64_t MaxBitVectorSize = 1024;
4418 if (AllocaSize <= MaxBitVectorSize) {
4423 for (
unsigned O =
S.beginOffset() + 1;
4424 O <
S.endOffset() &&
O < AllocaSize;
O++)
4425 SplittableOffset.reset(
O);
4427 for (Slice &
S : AS) {
4428 if (!
S.isSplittable())
4431 if ((
S.beginOffset() > AllocaSize || SplittableOffset[
S.beginOffset()]) &&
4432 (
S.endOffset() > AllocaSize || SplittableOffset[
S.endOffset()]))
4435 if (isa<LoadInst>(
S.getUse()->getUser()) ||
4436 isa<StoreInst>(
S.getUse()->getUser())) {
4437 S.makeUnsplittable();
4445 for (Slice &
S : AS) {
4446 if (!
S.isSplittable())
4449 if (
S.beginOffset() == 0 &&
S.endOffset() >= AllocaSize)
4452 if (isa<LoadInst>(
S.getUse()->getUser()) ||
4453 isa<StoreInst>(
S.getUse()->getUser())) {
4454 S.makeUnsplittable();
4475 for (
auto &
P : AS.partitions()) {
4476 if (
AllocaInst *NewAI = rewritePartition(AI, AS,
P)) {
4484 Fragments.push_back(
Fragment(NewAI,
P.beginOffset() * SizeOfByte, Size));
4490 NumAllocaPartitions += NumPartitions;
4491 MaxPartitionsPerAlloca.updateMax(NumPartitions);
4497 auto *Expr = DbgDeclare->getExpression();
4501 for (
auto Fragment : Fragments) {
4504 auto *FragmentExpr = Expr;
4505 if (
Fragment.Size < AllocaSize || Expr->isFragment()) {
4508 auto ExprFragment = Expr->getFragmentInfo();
4514 ExprFragment->OffsetInBits + ExprFragment->SizeInBits;
4515 if (Start >= AbsEnd)
4521 if (
auto OrigFragment = FragmentExpr->getFragmentInfo()) {
4522 assert(Start >= OrigFragment->OffsetInBits &&
4523 "new fragment is outside of original fragment");
4524 Start -= OrigFragment->OffsetInBits;
4528 auto VarSize = DbgDeclare->getVariable()->getSizeInBits();
4530 if (Size > *VarSize)
4532 if (Size == 0 || Start + Size > *VarSize)
4537 if (!VarSize || *VarSize != Size) {
4539 DIExpression::createFragmentExpression(Expr, Start, Size))
4551 return LHS->getVariable() ==
RHS->getVariable() &&
4552 LHS->getDebugLoc()->getInlinedAt() ==
4553 RHS->getDebugLoc()->getInlinedAt();
4555 if (SameVariableFragment(OldDII, DbgDeclare))
4556 OldDII->eraseFromParent();
4559 DIB.insertDeclare(
Fragment.Alloca, DbgDeclare->getVariable(), FragmentExpr,
4560 DbgDeclare->getDebugLoc(), &AI);
4567 void SROAPass::clobberUse(
Use &U) {
4575 if (
Instruction *OldI = dyn_cast<Instruction>(OldV))
4577 DeadInsts.push_back(OldI);
4588 ++NumAllocasAnalyzed;
4600 DL.getTypeAllocSize(AT).getFixedSize() == 0)
4603 bool Changed =
false;
4607 IRBuilderTy IRB(&AI);
4608 AggLoadStoreRewriter AggRewriter(
DL, IRB);
4609 Changed |= AggRewriter.rewrite(AI);
4620 for (
Use &DeadOp : DeadUser->operands())
4627 DeadInsts.push_back(DeadUser);
4630 for (
Use *DeadOp : AS.getDeadOperands()) {
4631 clobberUse(*DeadOp);
4636 if (AS.begin() == AS.end())
4639 Changed |= splitAlloca(AI, AS);
4642 while (!SpeculatablePHIs.empty())
4646 while (!SpeculatableSelects.empty())
4661 bool SROAPass::deleteDeadInstructions(
4663 bool Changed =
false;
4664 while (!DeadInsts.empty()) {
4665 Instruction *
I = dyn_cast_or_null<Instruction>(DeadInsts.pop_back_val());
4673 DeletedAllocas.
insert(AI);
4675 OldDII->eraseFromParent();
4680 for (
Use &Operand :
I->operands())
4681 if (
Instruction *U = dyn_cast<Instruction>(Operand)) {
4685 DeadInsts.push_back(U);
4689 I->eraseFromParent();
4700 bool SROAPass::promoteAllocas(
Function &
F) {
4701 if (PromotableAllocas.empty())
4704 NumPromoted += PromotableAllocas.size();
4708 PromotableAllocas.clear();
4715 C = &
F.getContext();
4725 PromotableAllocas.push_back(AI);
4727 Worklist.insert(AI);
4732 bool Changed =
false;
4738 while (!Worklist.empty()) {
4739 Changed |= runOnAlloca(*Worklist.pop_back_val());
4740 Changed |= deleteDeadInstructions(DeletedAllocas);
4744 if (!DeletedAllocas.
empty()) {
4745 auto IsInSet = [&](
AllocaInst *AI) {
return DeletedAllocas.
count(AI); };
4746 Worklist.remove_if(IsInSet);
4747 PostPromotionWorklist.remove_if(IsInSet);
4749 DeletedAllocas.
clear();
4753 Changed |= promoteAllocas(
F);
4755 Worklist = PostPromotionWorklist;
4756 PostPromotionWorklist.clear();
4757 }
while (!Worklist.empty());
4788 if (skipFunction(
F))
4791 auto PA = Impl.runImpl(
4792 F, getAnalysis<DominatorTreeWrapperPass>().getDomTree(),
4793 getAnalysis<AssumptionCacheTracker>().getAssumptionCache(
F));
4812 "Scalar Replacement Of Aggregates",
false,
false)