42#include "llvm/Config/llvm-config.h"
63#include "llvm/IR/IntrinsicsAArch64.h"
108#define DEBUG_TYPE "codegenprepare"
111STATISTIC(NumPHIsElim,
"Number of trivial PHIs eliminated");
112STATISTIC(NumGEPsElim,
"Number of GEPs converted to casts");
113STATISTIC(NumCmpUses,
"Number of uses of Cmp expressions replaced with uses of "
115STATISTIC(NumCastUses,
"Number of uses of Cast expressions replaced with uses "
117STATISTIC(NumMemoryInsts,
"Number of memory instructions whose address "
118 "computations were sunk");
120 "Number of phis created when address "
121 "computations were sunk to memory instructions");
123 "Number of select created when address "
124 "computations were sunk to memory instructions");
125STATISTIC(NumExtsMoved,
"Number of [s|z]ext instructions combined with loads");
126STATISTIC(NumExtUses,
"Number of uses of [s|z]ext instructions optimized");
128 "Number of and mask instructions added to form ext loads");
129STATISTIC(NumAndUses,
"Number of uses of and mask instructions optimized");
130STATISTIC(NumRetsDup,
"Number of return instructions duplicated");
131STATISTIC(NumDbgValueMoved,
"Number of debug value instructions moved");
132STATISTIC(NumSelectsExpanded,
"Number of selects turned into branches");
133STATISTIC(NumStoreExtractExposed,
"Number of store(extractelement) exposed");
137 cl::desc(
"Disable branch optimizations in CodeGenPrepare"));
141 cl::desc(
"Disable GC optimizations in CodeGenPrepare"));
146 cl::desc(
"Disable select to branch conversion."));
150 cl::desc(
"Address sinking in CGP using GEPs."));
154 cl::desc(
"Enable sinkinig and/cmp into branches."));
158 cl::desc(
"Disable store(extract) optimizations in CodeGenPrepare"));
162 cl::desc(
"Stress test store(extract) optimizations in CodeGenPrepare"));
166 cl::desc(
"Disable ext(promotable(ld)) -> promoted(ext(ld)) optimization in "
171 cl::desc(
"Stress test ext(promotable(ld)) -> promoted(ext(ld)) "
172 "optimization in CodeGenPrepare"));
176 cl::desc(
"Disable protection against removing loop preheaders"));
180 cl::desc(
"Use profile info to add section prefix for hot/cold functions"));
183 "profile-unknown-in-special-section",
cl::Hidden,
184 cl::desc(
"In profiling mode like sampleFDO, if a function doesn't have "
185 "profile, we cannot tell the function is cold for sure because "
186 "it may be a function newly added without ever being sampled. "
187 "With the flag enabled, compiler can put such profile unknown "
188 "functions into a special section, so runtime system can choose "
189 "to handle it in a different way than .text section, to save "
190 "RAM for example. "));
194 cl::desc(
"Use the basic-block-sections profile to determine the text "
195 "section prefix for hot functions. Functions with "
196 "basic-block-sections profile will be placed in `.text.hot` "
197 "regardless of their FDO profile info. Other functions won't be "
198 "impacted, i.e., their prefixes will be decided by FDO/sampleFDO "
203 cl::desc(
"Skip merging empty blocks if (frequency of empty block) / "
204 "(frequency of destination block) is greater than this ratio"));
208 cl::desc(
"Force store splitting no matter what the target query says."));
212 cl::desc(
"Enable merging of redundant sexts when one is dominating"
218 cl::desc(
"Disables combining addressing modes with different parts "
219 "in optimizeMemoryInst."));
223 cl::desc(
"Allow creation of Phis in Address sinking."));
227 cl::desc(
"Allow creation of selects in Address sinking."));
231 cl::desc(
"Allow combining of BaseReg field in Address sinking."));
235 cl::desc(
"Allow combining of BaseGV field in Address sinking."));
239 cl::desc(
"Allow combining of BaseOffs field in Address sinking."));
243 cl::desc(
"Allow combining of ScaledReg field in Address sinking."));
248 cl::desc(
"Enable splitting large offset of GEP."));
252 cl::desc(
"Enable ICMP_EQ to ICMP_S(L|G)T conversion."));
256 cl::desc(
"Enable BFI update verification for "
261 cl::desc(
"Enable converting phi types in CodeGenPrepare"));
265 cl::desc(
"Least BB number of huge function."));
270 cl::desc(
"Max number of address users to look at"));
274 cl::desc(
"Disable elimination of dead PHI nodes."));
302class TypePromotionTransaction;
313 std::unique_ptr<BlockFrequencyInfo>
BFI;
314 std::unique_ptr<BranchProbabilityInfo> BPI;
329 SetOfInstrs InsertedInsts;
333 InstrToOrigTy PromotedInsts;
336 SetOfInstrs RemovedInsts;
355 ValueToSExts ValToSExtendedUses;
365 std::unique_ptr<DominatorTree> DT;
369 bool IsHugeFunc =
false;
387 InsertedInsts.clear();
388 PromotedInsts.clear();
407 template <
typename F>
408 void resetIteratorIfInvalidatedWhileCalling(
BasicBlock *BB,
F f) {
412 Value *CurValue = &*CurInstIterator;
419 if (IterHandle != CurValue) {
420 CurInstIterator = BB->
begin();
428 DT = std::make_unique<DominatorTree>(
F);
432 void removeAllAssertingVHReferences(
Value *V);
435 bool eliminateMostlyEmptyBlocks(
Function &
F);
438 void eliminateMostlyEmptyBlock(
BasicBlock *BB);
443 bool optimizeInst(
Instruction *
I, ModifyDT &ModifiedDT);
447 bool optimizeInlineAsmInst(
CallInst *CS);
451 bool optimizeLoadExt(
LoadInst *Load);
457 bool optimizeSwitchPhiConstants(
SwitchInst *SI);
459 bool optimizeExtractElementInst(
Instruction *Inst);
460 bool dupRetToEnableTailCallOpts(
BasicBlock *BB, ModifyDT &ModifiedDT);
466 bool tryToPromoteExts(TypePromotionTransaction &TPT,
469 unsigned CreatedInstsCost = 0);
471 bool splitLargeGEPOffsets();
475 bool performAddressTypePromotion(
476 Instruction *&Inst,
bool AllowPromotionWithoutCommonHeader,
477 bool HasPromoted, TypePromotionTransaction &TPT,
479 bool splitBranchCondition(
Function &
F, ModifyDT &ModifiedDT);
485 bool optimizeCmp(
CmpInst *Cmp, ModifyDT &ModifiedDT);
486 bool combineToUSubWithOverflow(
CmpInst *Cmp, ModifyDT &ModifiedDT);
487 bool combineToUAddWithOverflow(
CmpInst *Cmp, ModifyDT &ModifiedDT);
493char CodeGenPrepare::ID = 0;
496 "Optimize for code generation",
false,
false)
508bool CodeGenPrepare::runOnFunction(
Function &
F) {
512 DL = &
F.getParent()->getDataLayout();
514 bool EverMadeChange =
false;
517 SubtargetInfo =
TM->getSubtargetImpl(
F);
518 TLI = SubtargetInfo->getTargetLowering();
519 TRI = SubtargetInfo->getRegisterInfo();
520 TLInfo = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(
F);
521 TTI = &getAnalysis<TargetTransformInfoWrapperPass>().getTTI(
F);
522 LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
525 PSI = &getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI();
526 BBSectionsProfileReader =
527 getAnalysisIfAvailable<BasicBlockSectionsProfileReader>();
528 OptSize =
F.hasOptSize();
533 F.setSectionPrefix(
"hot");
538 if (
F.hasFnAttribute(Attribute::Hot) ||
540 F.setSectionPrefix(
"hot");
545 F.hasFnAttribute(Attribute::Cold))
546 F.setSectionPrefix(
"unlikely");
549 F.setSectionPrefix(
"unknown");
558 while (BB !=
nullptr) {
572 EverMadeChange |= eliminateAssumptions(
F);
576 EverMadeChange |= eliminateMostlyEmptyBlocks(
F);
578 ModifyDT ModifiedDT = ModifyDT::NotModifyDT;
580 EverMadeChange |= splitBranchCondition(
F, ModifiedDT);
596 bool MadeChange =
true;
597 bool FuncIterated =
false;
602 if (FuncIterated && !FreshBBs.
contains(&BB))
605 ModifyDT ModifiedDTOnIteration = ModifyDT::NotModifyDT;
608 if (ModifiedDTOnIteration == ModifyDT::ModifyBBDT)
611 MadeChange |= Changed;
624 else if (FuncIterated)
629 if (ModifiedDTOnIteration != ModifyDT::NotModifyDT)
634 FuncIterated = IsHugeFunc;
637 MadeChange |= mergeSExts(
F);
638 if (!LargeOffsetGEPMap.
empty())
639 MadeChange |= splitLargeGEPOffsets();
640 MadeChange |= optimizePhiTypes(
F);
643 eliminateFallThrough(
F, DT.get());
654 EverMadeChange |= MadeChange;
655 SeenChainsForSExt.
clear();
656 ValToSExtendedUses.clear();
657 RemovedInsts.clear();
658 LargeOffsetGEPMap.
clear();
659 LargeOffsetGEPID.
clear();
683 MadeChange |= !WorkList.
empty();
684 while (!WorkList.
empty()) {
697 if (EverMadeChange || MadeChange)
698 MadeChange |= eliminateFallThrough(
F);
700 EverMadeChange |= MadeChange;
707 if (
auto *SP = dyn_cast<GCStatepointInst>(&
I))
709 for (
auto &
I : Statepoints)
710 EverMadeChange |= simplifyOffsetableRelocate(*
I);
715 EverMadeChange |= placeDbgValues(
F);
716 EverMadeChange |= placePseudoProbes(
F);
723 return EverMadeChange;
726bool CodeGenPrepare::eliminateAssumptions(
Function &
F) {
727 bool MadeChange =
false;
729 CurInstIterator = BB.begin();
730 while (CurInstIterator != BB.end()) {
732 if (
auto *Assume = dyn_cast<AssumeInst>(
I)) {
734 Value *Operand = Assume->getOperand(0);
735 Assume->eraseFromParent();
737 resetIteratorIfInvalidatedWhileCalling(&BB, [&]() {
748void CodeGenPrepare::removeAllAssertingVHReferences(
Value *V) {
749 LargeOffsetGEPMap.
erase(V);
750 NewGEPBases.
erase(V);
752 auto GEP = dyn_cast<GetElementPtrInst>(V);
758 auto VecI = LargeOffsetGEPMap.
find(
GEP->getPointerOperand());
759 if (VecI == LargeOffsetGEPMap.
end())
762 auto &GEPVector = VecI->second;
765 if (GEPVector.empty())
766 LargeOffsetGEPMap.
erase(VecI);
775 NewBFI.verifyMatch(*BFI);
782 bool Changed =
false;
792 auto *BB = cast_or_null<BasicBlock>(
Block);
800 if (!SinglePred || SinglePred == BB || BB->hasAddressTaken())
808 if (Term && !
Term->isConditional()) {
820 FreshBBs.
insert(SinglePred);
828 for (
const auto &Pred : Preds)
829 if (
auto *BB = cast_or_null<BasicBlock>(Pred))
845 if (BBI != BB->
begin()) {
847 while (isa<DbgInfoIntrinsic>(BBI)) {
848 if (BBI == BB->
begin())
852 if (!isa<DbgInfoIntrinsic>(BBI) && !isa<PHINode>(BBI))
861 if (!canMergeBlocks(BB, DestBB))
871bool CodeGenPrepare::eliminateMostlyEmptyBlocks(
Function &
F) {
874 while (!LoopList.empty()) {
875 Loop *
L = LoopList.pop_back_val();
878 Preheaders.
insert(Preheader);
881 bool MadeChange =
false;
897 BasicBlock *DestBB = findDestBlockOfMergeableEmptyBlock(BB);
899 !isMergingEmptyBlockProfitable(BB, DestBB, Preheaders.
count(BB)))
902 eliminateMostlyEmptyBlock(BB);
908bool CodeGenPrepare::isMergingEmptyBlockProfitable(
BasicBlock *BB,
924 if (
auto *CBI = dyn_cast<CallBrInst>((Pred)->getTerminator()))
925 for (
unsigned i = 0, e = CBI->getNumSuccessors(); i != e; ++i)
926 if (DestBB == CBI->getSuccessor(i))
957 if (!isa<PHINode>(DestBB->
begin()))
965 if (DestBBPred == BB)
969 return DestPN.getIncomingValueForBlock(BB) ==
970 DestPN.getIncomingValueForBlock(DestBBPred);
972 SameIncomingValueBBs.
insert(DestBBPred);
978 if (SameIncomingValueBBs.
count(Pred))
984 for (
auto *SameValueBB : SameIncomingValueBBs)
985 if (SameValueBB->getUniquePredecessor() == Pred &&
986 DestBB == findDestBlockOfMergeableEmptyBlock(SameValueBB))
987 BBFreq +=
BFI->getBlockFreq(SameValueBB);
990 return !Limit || PredFreq <= *Limit;
996bool CodeGenPrepare::canMergeBlocks(
const BasicBlock *BB,
1004 if (UI->
getParent() != DestBB || !isa<PHINode>(UI))
1010 if (
const PHINode *UPN = dyn_cast<PHINode>(UI))
1011 for (
unsigned I = 0,
E = UPN->getNumIncomingValues();
I !=
E; ++
I) {
1013 if (
Insn &&
Insn->getParent() == BB &&
1014 Insn->getParent() != UPN->getIncomingBlock(
I))
1024 const PHINode *DestBBPN = dyn_cast<PHINode>(DestBB->
begin());
1030 if (
const PHINode *BBPN = dyn_cast<PHINode>(BB->
begin())) {
1032 for (
unsigned i = 0, e = BBPN->getNumIncomingValues(); i != e; ++i)
1033 BBPreds.
insert(BBPN->getIncomingBlock(i));
1041 if (BBPreds.
count(Pred)) {
1043 const Value *V1 = PN.getIncomingValueForBlock(Pred);
1044 const Value *
V2 = PN.getIncomingValueForBlock(BB);
1047 if (
const PHINode *V2PN = dyn_cast<PHINode>(V2))
1048 if (V2PN->getParent() == BB)
1049 V2 = V2PN->getIncomingValueForBlock(Pred);
1065 auto *OldI = dyn_cast<Instruction>(Old);
1079void CodeGenPrepare::eliminateMostlyEmptyBlock(
BasicBlock *BB) {
1089 if (SinglePred != DestBB) {
1090 assert(SinglePred == BB &&
1091 "Single predecessor not the same as predecessor");
1100 FreshBBs.
insert(SinglePred);
1101 FreshBBs.
erase(DestBB);
1111 Value *InVal = PN.removeIncomingValue(BB,
false);
1115 PHINode *InValPhi = dyn_cast<PHINode>(InVal);
1116 if (InValPhi && InValPhi->
getParent() == BB) {
1125 for (
unsigned i = 0, e = BBPN->getNumIncomingValues(); i != e; ++i)
1126 PN.addIncoming(InVal, BBPN->getIncomingBlock(i));
1129 PN.addIncoming(InVal, Pred);
1153 for (
auto *ThisRelocate : AllRelocateCalls) {
1154 auto K = std::make_pair(ThisRelocate->getBasePtrIndex(),
1155 ThisRelocate->getDerivedPtrIndex());
1156 RelocateIdxMap.
insert(std::make_pair(K, ThisRelocate));
1158 for (
auto &Item : RelocateIdxMap) {
1159 std::pair<unsigned, unsigned> Key = Item.first;
1160 if (Key.first == Key.second)
1165 auto BaseKey = std::make_pair(Key.first, Key.first);
1168 auto MaybeBase = RelocateIdxMap.
find(BaseKey);
1169 if (MaybeBase == RelocateIdxMap.
end())
1174 RelocateInstMap[MaybeBase->second].push_back(
I);
1182 for (
unsigned i = 1; i <
GEP->getNumOperands(); i++) {
1184 auto *
Op = dyn_cast<ConstantInt>(
GEP->getOperand(i));
1185 if (!
Op ||
Op->getZExtValue() > 20)
1189 for (
unsigned i = 1; i <
GEP->getNumOperands(); i++)
1199 bool MadeChange =
false;
1207 &*R != RelocatedBase; ++R)
1208 if (
auto *RI = dyn_cast<GCRelocateInst>(R))
1218 "Not relocating a derived object of the original base object");
1219 if (ToReplace->getBasePtrIndex() == ToReplace->getDerivedPtrIndex()) {
1233 auto *Derived = dyn_cast<GetElementPtrInst>(ToReplace->getDerivedPtr());
1234 if (!Derived || Derived->getPointerOperand() !=
Base)
1243 "Should always have one since it's not a terminator");
1247 Builder.SetCurrentDebugLocation(ToReplace->getDebugLoc());
1271 Value *ActualRelocatedBase = RelocatedBase;
1272 if (RelocatedBase->
getType() !=
Base->getType()) {
1273 ActualRelocatedBase =
1274 Builder.CreateBitCast(RelocatedBase,
Base->getType());
1276 Value *Replacement =
1277 Builder.CreateGEP(Derived->getSourceElementType(), ActualRelocatedBase,
1283 Value *ActualReplacement = Replacement;
1284 if (Replacement->
getType() != ToReplace->getType()) {
1288 ToReplace->replaceAllUsesWith(ActualReplacement);
1289 ToReplace->eraseFromParent();
1314 bool MadeChange =
false;
1316 for (
auto *U :
I.users())
1323 if (AllRelocateCalls.
size() < 2)
1330 if (RelocateInstMap.
empty())
1333 for (
auto &Item : RelocateInstMap)
1347 bool MadeChange =
false;
1350 Use &TheUse = UI.getUse();
1357 UserBB = PN->getIncomingBlock(TheUse);
1365 if (
User->isEHPad())
1375 if (UserBB == DefBB)
1379 CastInst *&InsertedCast = InsertedCasts[UserBB];
1381 if (!InsertedCast) {
1385 CI->
getType(),
"", &*InsertPt);
1390 TheUse = InsertedCast;
1414 if (
auto *ASC = dyn_cast<AddrSpaceCastInst>(CI)) {
1416 ASC->getDestAddressSpace()))
1437 TargetLowering::TypePromoteInteger)
1440 TargetLowering::TypePromoteInteger)
1456 match(IVInc, m_ExtractValue<0>(m_Intrinsic<Intrinsic::uadd_with_overflow>(
1460 match(IVInc, m_ExtractValue<0>(m_Intrinsic<Intrinsic::usub_with_overflow>(
1471static std::optional<std::pair<Instruction *, Constant *>>
1474 if (!L || L->getHeader() != PN->
getParent() || !L->getLoopLatch())
1475 return std::nullopt;
1478 if (!IVInc || LI->
getLoopFor(IVInc->getParent()) != L)
1479 return std::nullopt;
1483 return std::make_pair(IVInc, Step);
1484 return std::nullopt;
1488 auto *
I = dyn_cast<Instruction>(V);
1495 if (
auto *PN = dyn_cast<PHINode>(
LHS))
1497 return IVInc->first ==
I;
1501bool CodeGenPrepare::replaceMathCmpWithIntrinsic(
BinaryOperator *BO,
1509 assert(L &&
"L should not be null after isIVIncrement()");
1526 if (BO->
getParent() !=
Cmp->getParent() && !IsReplacableIVIncrement(BO)) {
1549 if (BO->
getOpcode() == Instruction::Add &&
1550 IID == Intrinsic::usub_with_overflow) {
1551 assert(isa<Constant>(Arg1) &&
"Unexpected input for usubo");
1560 if ((BO->
getOpcode() != Instruction::Xor && &Iter == BO) || &Iter == Cmp) {
1565 assert(InsertPt !=
nullptr &&
"Parent block did not contain cmp or binop");
1568 Value *MathOV =
Builder.CreateBinaryIntrinsic(IID, Arg0, Arg1);
1569 if (BO->
getOpcode() != Instruction::Xor) {
1570 Value *Math =
Builder.CreateExtractValue(MathOV, 0,
"math");
1574 "Patterns with XOr should use the BO only in the compare");
1575 Value *OV =
Builder.CreateExtractValue(MathOV, 1,
"ov");
1577 Cmp->eraseFromParent();
1587 Value *
A = Cmp->getOperand(0), *
B = Cmp->getOperand(1);
1590 if (isa<Constant>(
A))
1603 for (
User *U :
A->users()) {
1605 Add = cast<BinaryOperator>(U);
1614bool CodeGenPrepare::combineToUAddWithOverflow(
CmpInst *Cmp,
1615 ModifyDT &ModifiedDT) {
1616 bool EdgeCase =
false;
1623 A =
Add->getOperand(0);
1624 B =
Add->getOperand(1);
1630 Add->hasNUsesOrMore(EdgeCase ? 1 : 2)))
1636 if (
Add->getParent() !=
Cmp->getParent() && !
Add->hasOneUse())
1639 if (!replaceMathCmpWithIntrinsic(
Add,
A,
B, Cmp,
1640 Intrinsic::uadd_with_overflow))
1644 ModifiedDT = ModifyDT::ModifyInstDT;
1648bool CodeGenPrepare::combineToUSubWithOverflow(
CmpInst *Cmp,
1649 ModifyDT &ModifiedDT) {
1652 if (isa<Constant>(
A) && isa<Constant>(
B))
1657 if (Pred == ICmpInst::ICMP_UGT) {
1659 Pred = ICmpInst::ICMP_ULT;
1664 Pred = ICmpInst::ICMP_ULT;
1669 Pred = ICmpInst::ICMP_ULT;
1671 if (Pred != ICmpInst::ICMP_ULT)
1677 Value *CmpVariableOperand = isa<Constant>(
A) ?
B :
A;
1679 for (
User *U : CmpVariableOperand->
users()) {
1682 Sub = cast<BinaryOperator>(U);
1687 const APInt *CmpC, *AddC;
1690 Sub = cast<BinaryOperator>(U);
1703 Cmp, Intrinsic::usub_with_overflow))
1707 ModifiedDT = ModifyDT::ModifyInstDT;
1728 bool MadeChange =
false;
1731 Use &TheUse = UI.getUse();
1738 if (isa<PHINode>(
User))
1746 if (UserBB == DefBB)
1750 CmpInst *&InsertedCmp = InsertedCmps[UserBB];
1756 Cmp->getOperand(0), Cmp->getOperand(1),
"",
1763 TheUse = InsertedCmp;
1769 if (Cmp->use_empty()) {
1770 Cmp->eraseFromParent();
1802 if (Pred != ICmpInst::ICMP_EQ)
1807 for (
User *U : Cmp->users()) {
1808 if (isa<BranchInst>(U))
1810 if (isa<SelectInst>(U) && cast<SelectInst>(U)->getCondition() == Cmp)
1829 if (CmpBB != FalseBB)
1832 Value *CmpOp0 = Cmp->getOperand(0), *CmpOp1 = Cmp->getOperand(1);
1836 if (DomPred != ICmpInst::ICMP_SGT && DomPred != ICmpInst::ICMP_SLT)
1846 for (
User *U : Cmp->users()) {
1847 if (
auto *BI = dyn_cast<BranchInst>(U)) {
1852 if (
auto *SI = dyn_cast<SelectInst>(U)) {
1855 SI->swapProfMetadata();
1867 Value *Op0 = Cmp->getOperand(0);
1868 Value *Op1 = Cmp->getOperand(1);
1870 isa<Constant>(Op1) || Op0 == Op1)
1877 unsigned NumInspected = 0;
1880 if (++NumInspected > 128)
1888 if (GoodToSwap > 0) {
1889 Cmp->swapOperands();
1895bool CodeGenPrepare::optimizeCmp(
CmpInst *Cmp, ModifyDT &ModifiedDT) {
1899 if (combineToUAddWithOverflow(Cmp, ModifiedDT))
1902 if (combineToUSubWithOverflow(Cmp, ModifiedDT))
1920 SetOfInstrs &InsertedInsts) {
1923 assert(!InsertedInsts.count(AndI) &&
1924 "Attempting to optimize already optimized and instruction");
1925 (void)InsertedInsts;
1934 if (!isa<ConstantInt>(AndI->
getOperand(0)) &&
1939 for (
auto *U : AndI->
users()) {
1943 if (!isa<ICmpInst>(
User))
1947 if (!CmpC || !CmpC->
isZero())
1962 Use &TheUse = UI.getUse();
1980 TheUse = InsertedAnd;
1996 if (!isa<TruncInst>(
User)) {
1997 if (
User->getOpcode() != Instruction::And ||
2003 if ((Cimm & (Cimm + 1)).getBoolValue())
2016 auto *TruncI = cast<TruncInst>(
User);
2017 bool MadeChange =
false;
2020 TruncE = TruncI->user_end();
2021 TruncUI != TruncE;) {
2023 Use &TruncTheUse = TruncUI.getUse();
2024 Instruction *TruncUser = cast<Instruction>(*TruncUI);
2043 if (isa<PHINode>(TruncUser))
2048 if (UserBB == TruncUserBB)
2052 CastInst *&InsertedTrunc = InsertedTruncs[TruncUserBB];
2054 if (!InsertedShift && !InsertedTrunc) {
2058 if (ShiftI->
getOpcode() == Instruction::AShr)
2059 InsertedShift = BinaryOperator::CreateAShr(ShiftI->
getOperand(0), CI,
2062 InsertedShift = BinaryOperator::CreateLShr(ShiftI->
getOperand(0), CI,
2069 assert(TruncInsertPt != TruncUserBB->
end());
2072 TruncI->
getType(),
"", &*TruncInsertPt);
2073 InsertedTrunc->
setDebugLoc(TruncI->getDebugLoc());
2077 TruncTheUse = InsertedTrunc;
2110 bool MadeChange =
false;
2113 Use &TheUse = UI.getUse();
2119 if (isa<PHINode>(
User))
2127 if (UserBB == DefBB) {
2142 if (isa<TruncInst>(
User) &&
2155 if (!InsertedShift) {
2159 if (ShiftI->
getOpcode() == Instruction::AShr)
2160 InsertedShift = BinaryOperator::CreateAShr(ShiftI->
getOperand(0), CI,
2163 InsertedShift = BinaryOperator::CreateLShr(ShiftI->
getOperand(0), CI,
2171 TheUse = InsertedShift;
2220 if (Ty->
isVectorTy() || SizeInBits >
DL->getLargestLegalIntTypeSizeInBits())
2232 FreshBBs.
insert(CallBlock);
2240 FreshBBs.
insert(EndBlock);
2245 L->addBasicBlockToLoop(CallBlock, LI);
2246 L->addBasicBlockToLoop(EndBlock, LI);
2261 Builder.CreateCondBr(Cmp, EndBlock, CallBlock);
2277 ModifiedDT = ModifyDT::ModifyBBDT;
2281bool CodeGenPrepare::optimizeCallInst(
CallInst *CI, ModifyDT &ModifiedDT) {
2290 CurInstIterator = BB->
begin();
2297 if (optimizeInlineAsmInst(CI))
2306 for (
auto &Arg : CI->
args()) {
2311 if (!Arg->getType()->isPointerTy())
2314 cast<PointerType>(Arg->getType())->getAddressSpace()),
2321 if ((AI = dyn_cast<AllocaInst>(Val)) && AI->
getAlign() < PrefAlign &&
2340 if (!MIDestAlign || DestAlign > *MIDestAlign)
2341 MI->setDestAlignment(DestAlign);
2343 MaybeAlign MTISrcAlign = MTI->getSourceAlign();
2345 if (!MTISrcAlign || SrcAlign > *MTISrcAlign)
2346 MTI->setSourceAlignment(SrcAlign);
2354 if (CI->
hasFnAttr(Attribute::Cold) && !OptSize &&
2356 for (
auto &Arg : CI->
args()) {
2357 if (!Arg->getType()->isPointerTy())
2359 unsigned AS = Arg->getType()->getPointerAddressSpace();
2360 if (optimizeMemoryInst(CI, Arg, Arg->getType(), AS))
2369 case Intrinsic::assume:
2371 case Intrinsic::experimental_widenable_condition: {
2380 resetIteratorIfInvalidatedWhileCalling(BB, [&]() {
2385 case Intrinsic::objectsize:
2387 case Intrinsic::is_constant:
2389 case Intrinsic::aarch64_stlxr:
2390 case Intrinsic::aarch64_stxr: {
2399 InsertedInsts.insert(ExtVal);
2403 case Intrinsic::launder_invariant_group:
2404 case Intrinsic::strip_invariant_group: {
2406 auto it = LargeOffsetGEPMap.
find(II);
2407 if (it != LargeOffsetGEPMap.
end()) {
2411 auto GEPs = std::move(it->second);
2412 LargeOffsetGEPMap[ArgVal].append(GEPs.begin(), GEPs.end());
2413 LargeOffsetGEPMap.
erase(II);
2420 case Intrinsic::cttz:
2421 case Intrinsic::ctlz:
2425 case Intrinsic::fshl:
2426 case Intrinsic::fshr:
2427 return optimizeFunnelShift(II);
2428 case Intrinsic::dbg_assign:
2429 case Intrinsic::dbg_value:
2430 return fixupDbgValue(II);
2431 case Intrinsic::masked_gather:
2433 case Intrinsic::masked_scatter:
2440 while (!PtrOps.
empty()) {
2443 if (optimizeMemoryInst(II, PtrVal, AccessTy, AS))
2458 if (
Value *V = Simplifier.optimizeCall(CI, Builder)) {
2497bool CodeGenPrepare::dupRetToEnableTailCallOpts(
BasicBlock *BB,
2498 ModifyDT &ModifiedDT) {
2506 assert(LI->
getLoopFor(BB) ==
nullptr &&
"A return block cannot be in a loop");
2513 BCI = dyn_cast<BitCastInst>(V);
2517 EVI = dyn_cast<ExtractValueInst>(V);
2524 PN = dyn_cast<PHINode>(V);
2532 auto isLifetimeEndOrBitCastFor = [](
const Instruction *Inst) {
2533 const BitCastInst *BC = dyn_cast<BitCastInst>(Inst);
2537 if (
const IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst))
2546 while (isa<DbgInfoIntrinsic>(BI) || BI == BCI || BI == EVI ||
2547 isa<PseudoProbeInst>(BI) || isLifetimeEndOrBitCastFor(BI))
2560 CallInst *CI = dyn_cast<CallInst>(IncomingVal);
2571 if (!VisitedBBs.
insert(Pred).second)
2573 if (
Instruction *
I = Pred->rbegin()->getPrevNonDebugInstruction(
true)) {
2582 bool Changed =
false;
2583 for (
auto const &TailCallBB : TailCallBBs) {
2586 BranchInst *BI = dyn_cast<BranchInst>(TailCallBB->getTerminator());
2593 BFI->getBlockFreq(BB) >=
BFI->getBlockFreq(TailCallBB));
2596 (
BFI->getBlockFreq(BB) -
BFI->getBlockFreq(TailCallBB)).getFrequency());
2597 ModifiedDT = ModifyDT::ModifyBBDT;
2620 Value *OriginalValue =
nullptr;
2621 bool InBounds =
true;
2625 BaseRegField = 0x01,
2627 BaseOffsField = 0x04,
2628 ScaledRegField = 0x08,
2630 MultipleFields = 0xff
2643 return MultipleFields;
2644 if (BaseGV && other.BaseGV && BaseGV->getType() != other.BaseGV->getType())
2645 return MultipleFields;
2648 return MultipleFields;
2651 if (InBounds != other.InBounds)
2652 return MultipleFields;
2655 unsigned Result = NoField;
2658 if (BaseGV != other.BaseGV)
2660 if (BaseOffs != other.BaseOffs)
2663 Result |= ScaledRegField;
2670 return MultipleFields;
2672 return static_cast<FieldName
>(
Result);
2693 case ScaledRegField:
2700 void SetCombinedField(FieldName
Field,
Value *V,
2706 case ExtAddrMode::BaseRegField:
2709 case ExtAddrMode::BaseGVField:
2716 case ExtAddrMode::ScaledRegField:
2727 case ExtAddrMode::BaseOffsField:
2746#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
2748 bool NeedPlus =
false;
2754 BaseGV->printAsOperand(
OS,
false);
2759 OS << (NeedPlus ?
" + " :
"") << BaseOffs;
2764 OS << (NeedPlus ?
" + " :
"") <<
"Base:";
2769 OS << (NeedPlus ?
" + " :
"") <<
Scale <<
"*";
2792class TypePromotionTransaction {
2796 class TypePromotionAction {
2804 TypePromotionAction(
Instruction *Inst) : Inst(Inst) {}
2806 virtual ~TypePromotionAction() =
default;
2813 virtual void undo() = 0;
2818 virtual void commit() {
2824 class InsertionHandler {
2835 bool HasPrevInstruction;
2842 if (HasPrevInstruction)
2843 Point.PrevInst = &*--It;
2850 if (HasPrevInstruction) {
2855 Instruction *Position = &*Point.BB->getFirstInsertionPt();
2865 class InstructionMoveBefore :
public TypePromotionAction {
2867 InsertionHandler Position;
2872 : TypePromotionAction(Inst), Position(Inst) {
2879 void undo()
override {
2881 Position.insert(Inst);
2886 class OperandSetter :
public TypePromotionAction {
2896 : TypePromotionAction(Inst),
Idx(
Idx) {
2898 <<
"for:" << *Inst <<
"\n"
2899 <<
"with:" << *NewVal <<
"\n");
2905 void undo()
override {
2907 <<
"for: " << *Inst <<
"\n"
2908 <<
"with: " << *Origin <<
"\n");
2915 class OperandsHider :
public TypePromotionAction {
2921 OperandsHider(
Instruction *Inst) : TypePromotionAction(Inst) {
2924 OriginalValues.
reserve(NumOpnds);
2925 for (
unsigned It = 0; It < NumOpnds; ++It) {
2937 void undo()
override {
2939 for (
unsigned It = 0, EndIt = OriginalValues.
size(); It != EndIt; ++It)
2945 class TruncBuilder :
public TypePromotionAction {
2952 TruncBuilder(
Instruction *Opnd,
Type *Ty) : TypePromotionAction(Opnd) {
2955 Val =
Builder.CreateTrunc(Opnd, Ty,
"promoted");
2960 Value *getBuiltValue() {
return Val; }
2963 void undo()
override {
2965 if (
Instruction *IVal = dyn_cast<Instruction>(Val))
2966 IVal->eraseFromParent();
2971 class SExtBuilder :
public TypePromotionAction {
2979 : TypePromotionAction(InsertPt) {
2981 Val =
Builder.CreateSExt(Opnd, Ty,
"promoted");
2986 Value *getBuiltValue() {
return Val; }
2989 void undo()
override {
2991 if (
Instruction *IVal = dyn_cast<Instruction>(Val))
2992 IVal->eraseFromParent();
2997 class ZExtBuilder :
public TypePromotionAction {
3005 : TypePromotionAction(InsertPt) {
3008 Val =
Builder.CreateZExt(Opnd, Ty,
"promoted");
3013 Value *getBuiltValue() {
return Val; }
3016 void undo()
override {
3018 if (
Instruction *IVal = dyn_cast<Instruction>(Val))
3019 IVal->eraseFromParent();
3024 class TypeMutator :
public TypePromotionAction {
3031 : TypePromotionAction(Inst), OrigTy(Inst->
getType()) {
3032 LLVM_DEBUG(
dbgs() <<
"Do: MutateType: " << *Inst <<
" with " << *NewTy
3038 void undo()
override {
3039 LLVM_DEBUG(
dbgs() <<
"Undo: MutateType: " << *Inst <<
" with " << *OrigTy
3046 class UsesReplacer :
public TypePromotionAction {
3048 struct InstructionAndIdx {
3056 : Inst(Inst),
Idx(
Idx) {}
3073 : TypePromotionAction(Inst),
New(
New) {
3074 LLVM_DEBUG(
dbgs() <<
"Do: UsersReplacer: " << *Inst <<
" with " << *New
3079 OriginalUses.
push_back(InstructionAndIdx(UserI,
U.getOperandNo()));
3090 void undo()
override {
3092 for (InstructionAndIdx &
Use : OriginalUses)
3093 Use.Inst->setOperand(
Use.Idx, Inst);
3098 for (
auto *DVI : DbgValues)
3099 DVI->replaceVariableLocationOp(New, Inst);
3104 class InstructionRemover :
public TypePromotionAction {
3106 InsertionHandler Inserter;
3110 OperandsHider Hider;
3113 UsesReplacer *Replacer =
nullptr;
3116 SetOfInstrs &RemovedInsts;
3123 InstructionRemover(
Instruction *Inst, SetOfInstrs &RemovedInsts,
3124 Value *New =
nullptr)
3125 : TypePromotionAction(Inst), Inserter(Inst), Hider(Inst),
3126 RemovedInsts(RemovedInsts) {
3128 Replacer =
new UsesReplacer(Inst, New);
3129 LLVM_DEBUG(
dbgs() <<
"Do: InstructionRemover: " << *Inst <<
"\n");
3130 RemovedInsts.insert(Inst);
3137 ~InstructionRemover()
override {
delete Replacer; }
3139 InstructionRemover &operator=(
const InstructionRemover &other) =
delete;
3140 InstructionRemover(
const InstructionRemover &other) =
delete;
3144 void undo()
override {
3145 LLVM_DEBUG(
dbgs() <<
"Undo: InstructionRemover: " << *Inst <<
"\n");
3146 Inserter.insert(Inst);
3150 RemovedInsts.erase(Inst);
3158 using ConstRestorationPt =
const TypePromotionAction *;
3160 TypePromotionTransaction(SetOfInstrs &RemovedInsts)
3161 : RemovedInsts(RemovedInsts) {}
3168 void rollback(ConstRestorationPt Point);
3171 ConstRestorationPt getRestorationPoint()
const;
3207 SetOfInstrs &RemovedInsts;
3212void TypePromotionTransaction::setOperand(
Instruction *Inst,
unsigned Idx,
3214 Actions.
push_back(std::make_unique<TypePromotionTransaction::OperandSetter>(
3215 Inst,
Idx, NewVal));
3218void TypePromotionTransaction::eraseInstruction(
Instruction *Inst,
3221 std::make_unique<TypePromotionTransaction::InstructionRemover>(
3222 Inst, RemovedInsts, NewVal));
3225void TypePromotionTransaction::replaceAllUsesWith(
Instruction *Inst,
3228 std::make_unique<TypePromotionTransaction::UsesReplacer>(Inst, New));
3231void TypePromotionTransaction::mutateType(
Instruction *Inst,
Type *NewTy) {
3233 std::make_unique<TypePromotionTransaction::TypeMutator>(Inst, NewTy));
3237 std::unique_ptr<TruncBuilder>
Ptr(
new TruncBuilder(Opnd, Ty));
3239 Actions.push_back(std::move(
Ptr));
3245 std::unique_ptr<SExtBuilder>
Ptr(
new SExtBuilder(Inst, Opnd, Ty));
3247 Actions.push_back(std::move(
Ptr));
3253 std::unique_ptr<ZExtBuilder>
Ptr(
new ZExtBuilder(Inst, Opnd, Ty));
3255 Actions.push_back(std::move(
Ptr));
3259void TypePromotionTransaction::moveBefore(
Instruction *Inst,
3262 std::make_unique<TypePromotionTransaction::InstructionMoveBefore>(
3266TypePromotionTransaction::ConstRestorationPt
3267TypePromotionTransaction::getRestorationPoint()
const {
3268 return !Actions.empty() ? Actions.back().get() :
nullptr;
3271bool TypePromotionTransaction::commit() {
3272 for (std::unique_ptr<TypePromotionAction> &Action : Actions)
3279void TypePromotionTransaction::rollback(
3280 TypePromotionTransaction::ConstRestorationPt Point) {
3281 while (!Actions.empty() && Point != Actions.back().get()) {
3282 std::unique_ptr<TypePromotionAction> Curr = Actions.pop_back_val();
3292class AddressingModeMatcher {
3311 const SetOfInstrs &InsertedInsts;
3314 InstrToOrigTy &PromotedInsts;
3317 TypePromotionTransaction &TPT;
3320 std::pair<AssertingVH<GetElementPtrInst>, int64_t> &LargeOffsetGEP;
3324 bool IgnoreProfitability;
3327 bool OptSize =
false;
3332 AddressingModeMatcher(
3337 const SetOfInstrs &InsertedInsts, InstrToOrigTy &PromotedInsts,
3338 TypePromotionTransaction &TPT,
3341 : AddrModeInsts(AMI), TLI(TLI),
TRI(
TRI),
3342 DL(
MI->getModule()->getDataLayout()), LI(LI), getDTFn(getDTFn),
3343 AccessTy(AT), AddrSpace(AS), MemoryInst(
MI),
AddrMode(AM),
3344 InsertedInsts(InsertedInsts), PromotedInsts(PromotedInsts), TPT(TPT),
3345 LargeOffsetGEP(LargeOffsetGEP), OptSize(OptSize), PSI(PSI),
BFI(
BFI) {
3346 IgnoreProfitability =
false;
3363 InstrToOrigTy &PromotedInsts, TypePromotionTransaction &TPT,
3368 bool Success = AddressingModeMatcher(AddrModeInsts, TLI,
TRI, LI, getDTFn,
3369 AccessTy, AS, MemoryInst, Result,
3370 InsertedInsts, PromotedInsts, TPT,
3371 LargeOffsetGEP, OptSize, PSI, BFI)
3379 bool matchScaledValue(
Value *ScaleReg, int64_t Scale,
unsigned Depth);
3381 bool matchOperationAddr(
User *AddrInst,
unsigned Opcode,
unsigned Depth,
3382 bool *MovedAway =
nullptr);
3383 bool isProfitableToFoldIntoAddressingMode(
Instruction *
I,
3386 bool valueAlreadyLiveAtInst(
Value *Val,
Value *KnownLive1,
Value *KnownLive2);
3387 bool isPromotionProfitable(
unsigned NewCost,
unsigned OldCost,
3388 Value *PromotedOperand)
const;
3394class PhiNodeSetIterator {
3395 PhiNodeSet *
const Set;
3396 size_t CurrentIndex = 0;
3401 PhiNodeSetIterator(PhiNodeSet *
const Set,
size_t Start);
3403 PhiNodeSetIterator &operator++();
3419 friend class PhiNodeSetIterator;
3422 using iterator = PhiNodeSetIterator;
3437 size_t FirstValidElement = 0;
3444 if (NodeMap.insert(std::make_pair(
Ptr,
NodeList.size())).second) {
3455 if (NodeMap.erase(
Ptr)) {
3456 SkipRemovedElements(FirstValidElement);
3466 FirstValidElement = 0;
3472 if (FirstValidElement == 0)
3473 SkipRemovedElements(FirstValidElement);
3474 return PhiNodeSetIterator(
this, FirstValidElement);
3478 iterator
end() {
return PhiNodeSetIterator(
this,
NodeList.size()); }
3481 size_t size()
const {
return NodeMap.size(); }
3492 void SkipRemovedElements(
size_t &CurrentIndex) {
3493 while (CurrentIndex <
NodeList.size()) {
3494 auto it = NodeMap.find(
NodeList[CurrentIndex]);
3497 if (it != NodeMap.end() && it->second == CurrentIndex)
3504PhiNodeSetIterator::PhiNodeSetIterator(PhiNodeSet *
const Set,
size_t Start)
3505 : Set(Set), CurrentIndex(Start) {}
3507PHINode *PhiNodeSetIterator::operator*()
const {
3509 "PhiNodeSet access out of range");
3510 return Set->NodeList[CurrentIndex];
3513PhiNodeSetIterator &PhiNodeSetIterator::operator++() {
3515 "PhiNodeSet access out of range");
3517 Set->SkipRemovedElements(CurrentIndex);
3521bool PhiNodeSetIterator::operator==(
const PhiNodeSetIterator &RHS)
const {
3522 return CurrentIndex ==
RHS.CurrentIndex;
3525bool PhiNodeSetIterator::operator!=(
const PhiNodeSetIterator &RHS)
const {
3526 return !((*this) ==
RHS);
3532class SimplificationTracker {
3537 PhiNodeSet AllPhiNodes;
3546 auto SV = Storage.
find(V);
3547 if (SV == Storage.
end())
3557 while (!WorkList.
empty()) {
3559 if (!Visited.
insert(
P).second)
3561 if (
auto *PI = dyn_cast<Instruction>(
P))
3563 for (
auto *U : PI->users())
3566 PI->replaceAllUsesWith(V);
3567 if (
auto *
PHI = dyn_cast<PHINode>(PI))
3568 AllPhiNodes.erase(
PHI);
3569 if (
auto *
Select = dyn_cast<SelectInst>(PI))
3571 PI->eraseFromParent();
3581 while (OldReplacement !=
From) {
3583 To = dyn_cast<PHINode>(OldReplacement);
3584 OldReplacement = Get(
From);
3586 assert(To && Get(To) == To &&
"Replacement PHI node is already replaced.");
3588 From->replaceAllUsesWith(To);
3589 AllPhiNodes.erase(
From);
3590 From->eraseFromParent();
3593 PhiNodeSet &newPhiNodes() {
return AllPhiNodes; }
3595 void insertNewPhi(
PHINode *PN) { AllPhiNodes.insert(PN); }
3599 unsigned countNewPhiNodes()
const {
return AllPhiNodes.size(); }
3601 unsigned countNewSelectNodes()
const {
return AllSelectNodes.
size(); }
3603 void destroyNewNodes(
Type *CommonType) {
3606 for (
auto *
I : AllPhiNodes) {
3607 I->replaceAllUsesWith(Dummy);
3608 I->eraseFromParent();
3610 AllPhiNodes.clear();
3611 for (
auto *
I : AllSelectNodes) {
3612 I->replaceAllUsesWith(Dummy);
3613 I->eraseFromParent();
3615 AllSelectNodes.clear();
3620class AddressingModeCombiner {
3622 typedef std::pair<PHINode *, PHINode *> PHIPair;
3629 ExtAddrMode::FieldName DifferentField = ExtAddrMode::NoField;
3632 bool AllAddrModesTrivial =
true;
3635 Type *CommonType =
nullptr;
3644 Value *CommonValue =
nullptr;
3648 : SQ(_SQ), Original(OriginalValue) {}
3650 ~AddressingModeCombiner() { eraseCommonValueIfDead(); }
3662 AllAddrModesTrivial = AllAddrModesTrivial && NewAddrMode.isTrivial();
3665 if (AddrModes.
empty()) {
3673 ExtAddrMode::FieldName ThisDifferentField =
3674 AddrModes[0].compare(NewAddrMode);
3675 if (DifferentField == ExtAddrMode::NoField)
3676 DifferentField = ThisDifferentField;
3677 else if (DifferentField != ThisDifferentField)
3678 DifferentField = ExtAddrMode::MultipleFields;
3681 bool CanHandle = DifferentField != ExtAddrMode::MultipleFields;
3684 CanHandle = CanHandle && DifferentField != ExtAddrMode::ScaleField;
3689 CanHandle = CanHandle && (DifferentField != ExtAddrMode::BaseOffsField ||
3694 CanHandle = CanHandle && (DifferentField != ExtAddrMode::BaseGVField ||
3695 !NewAddrMode.HasBaseReg);
3712 bool combineAddrModes() {
3714 if (AddrModes.
size() == 0)
3718 if (AddrModes.
size() == 1 || DifferentField == ExtAddrMode::NoField)
3723 if (AllAddrModesTrivial)
3726 if (!addrModeCombiningAllowed())
3732 FoldAddrToValueMapping
Map;
3733 if (!initializeMap(Map))
3736 CommonValue = findCommon(Map);
3738 AddrModes[0].SetCombinedField(DifferentField, CommonValue, AddrModes);
3739 return CommonValue !=
nullptr;
3745 void eraseCommonValueIfDead() {
3746 if (CommonValue && CommonValue->
getNumUses() == 0)
3747 if (
Instruction *CommonInst = dyn_cast<Instruction>(CommonValue))
3748 CommonInst->eraseFromParent();
3756 bool initializeMap(FoldAddrToValueMapping &Map) {
3761 for (
auto &AM : AddrModes) {
3762 Value *DV = AM.GetFieldAsValue(DifferentField, IntPtrTy);
3765 if (CommonType && CommonType !=
Type)
3768 Map[AM.OriginalValue] = DV;
3773 assert(CommonType &&
"At least one non-null value must be!");
3774 for (
auto *V : NullValue)
3802 Value *findCommon(FoldAddrToValueMapping &Map) {
3810 SimplificationTracker
ST(SQ);
3815 InsertPlaceholders(Map, TraverseOrder, ST);
3818 FillPlaceholders(Map, TraverseOrder, ST);
3821 ST.destroyNewNodes(CommonType);
3826 unsigned PhiNotMatchedCount = 0;
3828 ST.destroyNewNodes(CommonType);
3832 auto *
Result =
ST.Get(
Map.find(Original)->second);
3834 NumMemoryInstsPhiCreated +=
ST.countNewPhiNodes() + PhiNotMatchedCount;
3835 NumMemoryInstsSelectCreated +=
ST.countNewSelectNodes();
3844 PhiNodeSet &PhiNodesToMatch) {
3851 while (!WorkList.
empty()) {
3853 if (!Visited.
insert(Item).second)
3860 for (
auto *
B : Item.first->blocks()) {
3861 Value *FirstValue = Item.first->getIncomingValueForBlock(
B);
3862 Value *SecondValue = Item.second->getIncomingValueForBlock(
B);
3863 if (FirstValue == SecondValue)
3866 PHINode *FirstPhi = dyn_cast<PHINode>(FirstValue);
3867 PHINode *SecondPhi = dyn_cast<PHINode>(SecondValue);
3873 if (!FirstPhi || !SecondPhi || !PhiNodesToMatch.count(FirstPhi) ||
3878 if (Matcher.
count({FirstPhi, SecondPhi}))
3883 if (MatchedPHIs.
insert(FirstPhi).second)
3884 Matcher.
insert({FirstPhi, SecondPhi});
3886 WorkList.
push_back({FirstPhi, SecondPhi});
3895 bool MatchPhiSet(SimplificationTracker &ST,
bool AllowNewPhiNodes,
3896 unsigned &PhiNotMatchedCount) {
3902 PhiNodeSet &PhiNodesToMatch =
ST.newPhiNodes();
3903 while (PhiNodesToMatch.size()) {
3907 WillNotMatch.
clear();
3911 bool IsMatched =
false;
3912 for (
auto &
P :
PHI->getParent()->phis()) {
3914 if (PhiNodesToMatch.count(&
P))
3916 if ((IsMatched = MatchPhiNode(
PHI, &
P, Matched, PhiNodesToMatch)))
3921 for (
auto M : Matched)
3927 for (
auto MV : Matched)
3928 ST.ReplacePhi(MV.first, MV.second);
3933 if (!AllowNewPhiNodes)
3936 PhiNotMatchedCount += WillNotMatch.
size();
3937 for (
auto *
P : WillNotMatch)
3938 PhiNodesToMatch.erase(
P);
3943 void FillPlaceholders(FoldAddrToValueMapping &Map,
3945 SimplificationTracker &ST) {
3946 while (!TraverseOrder.
empty()) {
3948 assert(
Map.contains(Current) &&
"No node to fill!!!");
3953 auto *CurrentSelect = cast<SelectInst>(Current);
3954 auto *TrueValue = CurrentSelect->getTrueValue();
3955 assert(
Map.contains(TrueValue) &&
"No True Value!");
3956 Select->setTrueValue(
ST.Get(Map[TrueValue]));
3957 auto *FalseValue = CurrentSelect->getFalseValue();
3958 assert(
Map.contains(FalseValue) &&
"No False Value!");
3959 Select->setFalseValue(
ST.Get(Map[FalseValue]));
3962 auto *
PHI = cast<PHINode>(V);
3965 Value *PV = cast<PHINode>(Current)->getIncomingValueForBlock(
B);
3966 assert(
Map.contains(PV) &&
"No predecessor Value!");
3967 PHI->addIncoming(
ST.Get(Map[PV]),
B);
3970 Map[Current] =
ST.Simplify(V);
3979 void InsertPlaceholders(FoldAddrToValueMapping &Map,
3981 SimplificationTracker &ST) {
3983 assert((isa<PHINode>(Original) || isa<SelectInst>(Original)) &&
3984 "Address must be a Phi or Select node");
3987 while (!Worklist.
empty()) {
3990 if (
Map.contains(Current))
3996 if (
SelectInst *CurrentSelect = dyn_cast<SelectInst>(Current)) {
4000 CurrentSelect->getCondition(), Dummy, Dummy,
4001 CurrentSelect->getName(), CurrentSelect, CurrentSelect);
4005 Worklist.
push_back(CurrentSelect->getTrueValue());
4006 Worklist.
push_back(CurrentSelect->getFalseValue());
4009 PHINode *CurrentPhi = cast<PHINode>(Current);
4014 ST.insertNewPhi(
PHI);
4020 bool addrModeCombiningAllowed() {
4023 switch (DifferentField) {
4026 case ExtAddrMode::BaseRegField:
4028 case ExtAddrMode::BaseGVField:
4030 case ExtAddrMode::BaseOffsField:
4032 case ExtAddrMode::ScaledRegField:
4042bool AddressingModeMatcher::matchScaledValue(
Value *ScaleReg, int64_t Scale,
4047 return matchAddr(ScaleReg,
Depth);
4062 TestAddrMode.
Scale += Scale;
4077 Value *AddLHS =
nullptr;
4078 if (isa<Instruction>(ScaleReg) &&
4081 TestAddrMode.InBounds =
false;
4088 AddrModeInsts.
push_back(cast<Instruction>(ScaleReg));
4098 auto GetConstantStep =
4099 [
this](
const Value *
V) -> std::optional<std::pair<Instruction *, APInt>> {
4100 auto *PN = dyn_cast<PHINode>(V);
4102 return std::nullopt;
4105 return std::nullopt;
4112 if (
auto *OIVInc = dyn_cast<OverflowingBinaryOperator>(IVInc->first))
4113 if (OIVInc->hasNoSignedWrap() || OIVInc->hasNoUnsignedWrap())
4114 return std::nullopt;
4115 if (
auto *ConstantStep = dyn_cast<ConstantInt>(IVInc->second))
4116 return std::make_pair(IVInc->first, ConstantStep->getValue());
4117 return std::nullopt;
4132 if (
auto IVStep = GetConstantStep(ScaleReg)) {
4139 APInt Step = IVStep->second;
4141 if (
Offset.isSignedIntN(64)) {
4142 TestAddrMode.InBounds =
false;
4144 TestAddrMode.BaseOffs -=
Offset.getLimitedValue();
4149 getDTFn().
dominates(IVInc, MemoryInst)) {
4150 AddrModeInsts.
push_back(cast<Instruction>(IVInc));
4169 switch (
I->getOpcode()) {
4170 case Instruction::BitCast:
4171 case Instruction::AddrSpaceCast:
4173 if (
I->getType() ==
I->getOperand(0)->getType())
4175 return I->getType()->isIntOrPtrTy();
4176 case Instruction::PtrToInt:
4179 case Instruction::IntToPtr:
4182 case Instruction::Add:
4184 case Instruction::Mul:
4185 case Instruction::Shl:
4187 return isa<ConstantInt>(
I->getOperand(1));
4188 case Instruction::GetElementPtr:
4201 Instruction *PromotedInst = dyn_cast<Instruction>(Val);
4216class TypePromotionHelper {
4219 static void addPromotedInst(InstrToOrigTy &PromotedInsts,
4221 ExtType ExtTy = IsSExt ? SignExtension : ZeroExtension;
4222 InstrToOrigTy::iterator It = PromotedInsts.find(ExtOpnd);
4223 if (It != PromotedInsts.end()) {
4226 if (It->second.getInt() == ExtTy)
4232 ExtTy = BothExtension;
4234 PromotedInsts[ExtOpnd] = TypeIsSExt(ExtOpnd->
getType(), ExtTy);
4241 static const Type *getOrigType(
const InstrToOrigTy &PromotedInsts,
4243 ExtType ExtTy = IsSExt ? SignExtension : ZeroExtension;
4244 InstrToOrigTy::const_iterator It = PromotedInsts.find(Opnd);
4245 if (It != PromotedInsts.end() && It->second.getInt() == ExtTy)
4246 return It->second.getPointer();
4261 static bool canGetThrough(
const Instruction *Inst,
Type *ConsideredExtType,
4262 const InstrToOrigTy &PromotedInsts,
bool IsSExt);
4266 static bool shouldExtOperand(
const Instruction *Inst,
int OpIdx) {
4267 return !(isa<SelectInst>(Inst) && OpIdx == 0);
4279 static Value *promoteOperandForTruncAndAnyExt(
4281 InstrToOrigTy &PromotedInsts,
unsigned &CreatedInstsCost,
4295 TypePromotionTransaction &TPT,
4296 InstrToOrigTy &PromotedInsts,
4297 unsigned &CreatedInstsCost,
4303 static Value *signExtendOperandForOther(
4305 InstrToOrigTy &PromotedInsts,
unsigned &CreatedInstsCost,
4308 return promoteOperandForOther(Ext, TPT, PromotedInsts, CreatedInstsCost,
4309 Exts, Truncs, TLI,
true);
4313 static Value *zeroExtendOperandForOther(
4315 InstrToOrigTy &PromotedInsts,
unsigned &CreatedInstsCost,
4318 return promoteOperandForOther(Ext, TPT, PromotedInsts, CreatedInstsCost,
4319 Exts, Truncs, TLI,
false);
4325 InstrToOrigTy &PromotedInsts,
4326 unsigned &CreatedInstsCost,
4342 const InstrToOrigTy &PromotedInsts);
4347bool TypePromotionHelper::canGetThrough(
const Instruction *Inst,
4348 Type *ConsideredExtType,
4349 const InstrToOrigTy &PromotedInsts,
4358 if (isa<ZExtInst>(Inst))
4362 if (IsSExt && isa<SExtInst>(Inst))
4367 if (
const auto *BinOp = dyn_cast<BinaryOperator>(Inst))
4368 if (isa<OverflowingBinaryOperator>(BinOp) &&
4369 ((!IsSExt && BinOp->hasNoUnsignedWrap()) ||
4370 (IsSExt && BinOp->hasNoSignedWrap())))
4374 if ((Inst->
getOpcode() == Instruction::And ||
4379 if (Inst->
getOpcode() == Instruction::Xor) {
4381 if (
const auto *Cst = dyn_cast<ConstantInt>(Inst->
getOperand(1)))
4382 if (!Cst->getValue().isAllOnes())
4391 if (Inst->
getOpcode() == Instruction::LShr && !IsSExt)
4400 const auto *ExtInst = cast<const Instruction>(*Inst->
user_begin());
4401 if (ExtInst->hasOneUse()) {
4402 const auto *AndInst = dyn_cast<const Instruction>(*ExtInst->user_begin());
4403 if (AndInst && AndInst->getOpcode() == Instruction::And) {
4404 const auto *Cst = dyn_cast<ConstantInt>(AndInst->getOperand(1));
4414 if (!isa<TruncInst>(Inst))
4428 Instruction *Opnd = dyn_cast<Instruction>(OpndVal);
4436 const Type *OpndType = getOrigType(PromotedInsts, Opnd, IsSExt);
4439 else if ((IsSExt && isa<SExtInst>(Opnd)) || (!IsSExt && isa<ZExtInst>(Opnd)))
4449TypePromotionHelper::Action TypePromotionHelper::getAction(
4450 Instruction *Ext,
const SetOfInstrs &InsertedInsts,
4452 assert((isa<SExtInst>(Ext) || isa<ZExtInst>(Ext)) &&
4453 "Unexpected instruction type");
4454 Instruction *ExtOpnd = dyn_cast<Instruction>(
Ext->getOperand(0));
4456 bool IsSExt = isa<SExtInst>(Ext);
4460 if (!ExtOpnd || !canGetThrough(ExtOpnd, ExtTy, PromotedInsts, IsSExt))
4466 if (isa<TruncInst>(ExtOpnd) && InsertedInsts.count(ExtOpnd))
4471 if (isa<SExtInst>(ExtOpnd) || isa<TruncInst>(ExtOpnd) ||
4472 isa<ZExtInst>(ExtOpnd))
4473 return promoteOperandForTruncAndAnyExt;
4479 return IsSExt ? signExtendOperandForOther : zeroExtendOperandForOther;
4482Value *TypePromotionHelper::promoteOperandForTruncAndAnyExt(
4484 InstrToOrigTy &PromotedInsts,
unsigned &CreatedInstsCost,
4490 Value *ExtVal = SExt;
4491 bool HasMergedNonFreeExt =
false;
4492 if (isa<ZExtInst>(SExtOpnd)) {
4495 HasMergedNonFreeExt = !TLI.
isExtFree(SExtOpnd);
4499 TPT.eraseInstruction(SExt);
4504 TPT.setOperand(SExt, 0, SExtOpnd->
getOperand(0));
4506 CreatedInstsCost = 0;
4510 TPT.eraseInstruction(SExtOpnd);
4513 Instruction *ExtInst = dyn_cast<Instruction>(ExtVal);
4518 CreatedInstsCost = !TLI.
isExtFree(ExtInst) && !HasMergedNonFreeExt;
4526 TPT.eraseInstruction(ExtInst, NextVal);
4530Value *TypePromotionHelper::promoteOperandForOther(
4532 InstrToOrigTy &PromotedInsts,
unsigned &CreatedInstsCost,
4539 CreatedInstsCost = 0;
4545 Value *Trunc = TPT.createTrunc(Ext, ExtOpnd->
getType());
4546 if (
Instruction *ITrunc = dyn_cast<Instruction>(Trunc)) {
4548 ITrunc->moveAfter(ExtOpnd);
4553 TPT.replaceAllUsesWith(ExtOpnd, Trunc);
4556 TPT.setOperand(Ext, 0, ExtOpnd);
4566 addPromotedInst(PromotedInsts, ExtOpnd, IsSExt);
4568 TPT.mutateType(ExtOpnd,
Ext->getType());
4570 TPT.replaceAllUsesWith(Ext, ExtOpnd);
4575 for (
int OpIdx = 0, EndOpIdx = ExtOpnd->
getNumOperands(); OpIdx != EndOpIdx;
4579 !shouldExtOperand(ExtOpnd, OpIdx)) {
4585 if (
const ConstantInt *Cst = dyn_cast<ConstantInt>(Opnd)) {
4587 unsigned BitWidth =
Ext->getType()->getIntegerBitWidth();
4594 if (isa<UndefValue>(Opnd)) {
4605 Value *ValForExtOpnd = IsSExt ? TPT.createSExt(Ext, Opnd,
Ext->getType())
4606 : TPT.createZExt(Ext, Opnd,
Ext->getType());
4607 if (!isa<Instruction>(ValForExtOpnd)) {
4608 TPT.setOperand(ExtOpnd, OpIdx, ValForExtOpnd);
4611 ExtForOpnd = cast<Instruction>(ValForExtOpnd);
4615 TPT.setOperand(ExtForOpnd, 0, Opnd);
4618 TPT.moveBefore(ExtForOpnd, ExtOpnd);
4619 TPT.setOperand(ExtOpnd, OpIdx, ExtForOpnd);
4620 CreatedInstsCost += !TLI.
isExtFree(ExtForOpnd);
4622 ExtForOpnd =
nullptr;
4624 if (ExtForOpnd == Ext) {
4626 TPT.eraseInstruction(Ext);
4639bool AddressingModeMatcher::isPromotionProfitable(
4640 unsigned NewCost,
unsigned OldCost,
Value *PromotedOperand)
const {
4641 LLVM_DEBUG(
dbgs() <<
"OldCost: " << OldCost <<
"\tNewCost: " << NewCost
4646 if (NewCost > OldCost)
4648 if (NewCost < OldCost)
4667bool AddressingModeMatcher::matchOperationAddr(
User *AddrInst,
unsigned Opcode,
4679 case Instruction::PtrToInt:
4682 case Instruction::IntToPtr: {
4690 case Instruction::BitCast:
4700 case Instruction::AddrSpaceCast: {
4708 case Instruction::Add: {
4712 unsigned OldSize = AddrModeInsts.
size();
4717 TypePromotionTransaction::ConstRestorationPt LastKnownGood =
4718 TPT.getRestorationPoint();
4722 int First = 0, Second = 1;
4724 && !isa<ConstantInt>(AddrInst->
getOperand(Second)))
4733 AddrModeInsts.
resize(OldSize);
4734 TPT.rollback(LastKnownGood);
4744 AddrModeInsts.
resize(OldSize);
4745 TPT.rollback(LastKnownGood);
4751 case Instruction::Mul:
4752 case Instruction::Shl: {
4756 if (!RHS ||
RHS->getBitWidth() > 64)
4758 int64_t Scale = Opcode == Instruction::Shl
4759 ? 1LL <<
RHS->getLimitedValue(
RHS->getBitWidth() - 1)
4760 :
RHS->getSExtValue();
4764 case Instruction::GetElementPtr: {
4767 int VariableOperand = -1;
4768 unsigned VariableScale = 0;
4770 int64_t ConstantOffset = 0;
4772 for (
unsigned i = 1, e = AddrInst->
getNumOperands(); i != e; ++i, ++GTI) {
4776 cast<ConstantInt>(AddrInst->
getOperand(i))->getZExtValue();
4786 dyn_cast<ConstantInt>(AddrInst->
getOperand(i))) {
4794 if (VariableOperand != -1)
4798 VariableOperand = i;
4806 if (VariableOperand == -1) {
4807 AddrMode.BaseOffs += ConstantOffset;
4809 if (!cast<GEPOperator>(AddrInst)->isInBounds())
4813 AddrMode.BaseOffs -= ConstantOffset;
4817 ConstantOffset > 0) {
4823 auto *BaseI = dyn_cast<Instruction>(
Base);
4824 auto *
GEP = cast<GetElementPtrInst>(AddrInst);
4825 if (isa<Argument>(
Base) || isa<GlobalValue>(
Base) ||
4826 (BaseI && !isa<CastInst>(BaseI) &&
4827 !isa<GetElementPtrInst>(BaseI))) {
4831 : &
GEP->getFunction()->getEntryBlock();
4833 LargeOffsetGEP = std::make_pair(
GEP, ConstantOffset);
4842 unsigned OldSize = AddrModeInsts.
size();
4845 AddrMode.BaseOffs += ConstantOffset;
4846 if (!cast<GEPOperator>(AddrInst)->isInBounds())
4854 AddrModeInsts.
resize(OldSize);
4862 if (!matchScaledValue(AddrInst->
getOperand(VariableOperand), VariableScale,
4867 AddrModeInsts.
resize(OldSize);
4872 AddrMode.BaseOffs += ConstantOffset;
4873 if (!matchScaledValue(AddrInst->
getOperand(VariableOperand),
4874 VariableScale,
Depth)) {
4877 AddrModeInsts.
resize(OldSize);
4884 case Instruction::SExt:
4885 case Instruction::ZExt: {
4892 TypePromotionHelper::Action TPH =
4893 TypePromotionHelper::getAction(Ext, InsertedInsts, TLI, PromotedInsts);
4897 TypePromotionTransaction::ConstRestorationPt LastKnownGood =
4898 TPT.getRestorationPoint();
4899 unsigned CreatedInstsCost = 0;
4901 Value *PromotedOperand =
4902 TPH(Ext, TPT, PromotedInsts, CreatedInstsCost,
nullptr,
nullptr, TLI);
4917 assert(PromotedOperand &&
4918 "TypePromotionHelper should have filtered out those cases");
4921 unsigned OldSize = AddrModeInsts.
size();
4923 if (!matchAddr(PromotedOperand,
Depth) ||
4928 !isPromotionProfitable(CreatedInstsCost,
4929 ExtCost + (AddrModeInsts.
size() - OldSize),
4932 AddrModeInsts.
resize(OldSize);
4933 LLVM_DEBUG(
dbgs() <<
"Sign extension does not pay off: rollback\n");
4934 TPT.rollback(LastKnownGood);
4948bool AddressingModeMatcher::matchAddr(
Value *
Addr,
unsigned Depth) {
4951 TypePromotionTransaction::ConstRestorationPt LastKnownGood =
4952 TPT.getRestorationPoint();
4971 unsigned OldSize = AddrModeInsts.
size();
4974 bool MovedAway =
false;
4975 if (matchOperationAddr(
I,
I->getOpcode(),
Depth, &MovedAway)) {
4983 if (
I->hasOneUse() ||
4984 isProfitableToFoldIntoAddressingMode(
I, BackupAddrMode,
AddrMode)) {
4991 AddrModeInsts.
resize(OldSize);
4992 TPT.rollback(LastKnownGood);
4995 if (matchOperationAddr(CE,
CE->getOpcode(),
Depth))
4997 TPT.rollback(LastKnownGood);
4998 }
else if (isa<ConstantPointerNull>(
Addr)) {
5024 TPT.rollback(LastKnownGood);
5043 if (OpInfo.CallOperandVal == OpVal &&
5045 !OpInfo.isIndirect))
5061 if (!ConsideredInsts.
insert(
I).second)
5069 for (
Use &U :
I->uses()) {
5075 Instruction *UserI = cast<Instruction>(U.getUser());
5076 if (
LoadInst *LI = dyn_cast<LoadInst>(UserI)) {
5077 MemoryUses.push_back({&U, LI->getType()});
5081 if (
StoreInst *SI = dyn_cast<StoreInst>(UserI)) {
5084 MemoryUses.push_back({&U, SI->getValueOperand()->
getType()});
5091 MemoryUses.push_back({&U, RMW->getValOperand()->
getType()});
5098 MemoryUses.push_back({&U, CmpX->getCompareOperand()->
getType()});
5102 if (
CallInst *CI = dyn_cast<CallInst>(UserI)) {
5103 if (CI->hasFnAttr(Attribute::Cold)) {
5112 InlineAsm *IA = dyn_cast<InlineAsm>(CI->getCalledOperand());
5123 PSI, BFI, SeenInsts))
5134 unsigned SeenInsts = 0;
5137 PSI, BFI, SeenInsts);
5145bool AddressingModeMatcher::valueAlreadyLiveAtInst(
Value *Val,
5147 Value *KnownLive2) {