44#include "llvm/Config/llvm-config.h"
65#include "llvm/IR/IntrinsicsAArch64.h"
110#define DEBUG_TYPE "codegenprepare"
113STATISTIC(NumPHIsElim,
"Number of trivial PHIs eliminated");
114STATISTIC(NumGEPsElim,
"Number of GEPs converted to casts");
115STATISTIC(NumCmpUses,
"Number of uses of Cmp expressions replaced with uses of "
117STATISTIC(NumCastUses,
"Number of uses of Cast expressions replaced with uses "
119STATISTIC(NumMemoryInsts,
"Number of memory instructions whose address "
120 "computations were sunk");
122 "Number of phis created when address "
123 "computations were sunk to memory instructions");
125 "Number of select created when address "
126 "computations were sunk to memory instructions");
127STATISTIC(NumExtsMoved,
"Number of [s|z]ext instructions combined with loads");
128STATISTIC(NumExtUses,
"Number of uses of [s|z]ext instructions optimized");
130 "Number of and mask instructions added to form ext loads");
131STATISTIC(NumAndUses,
"Number of uses of and mask instructions optimized");
132STATISTIC(NumRetsDup,
"Number of return instructions duplicated");
133STATISTIC(NumDbgValueMoved,
"Number of debug value instructions moved");
134STATISTIC(NumSelectsExpanded,
"Number of selects turned into branches");
135STATISTIC(NumStoreExtractExposed,
"Number of store(extractelement) exposed");
139 cl::desc(
"Disable branch optimizations in CodeGenPrepare"));
143 cl::desc(
"Disable GC optimizations in CodeGenPrepare"));
148 cl::desc(
"Disable select to branch conversion."));
152 cl::desc(
"Address sinking in CGP using GEPs."));
156 cl::desc(
"Enable sinkinig and/cmp into branches."));
160 cl::desc(
"Disable store(extract) optimizations in CodeGenPrepare"));
164 cl::desc(
"Stress test store(extract) optimizations in CodeGenPrepare"));
168 cl::desc(
"Disable ext(promotable(ld)) -> promoted(ext(ld)) optimization in "
173 cl::desc(
"Stress test ext(promotable(ld)) -> promoted(ext(ld)) "
174 "optimization in CodeGenPrepare"));
178 cl::desc(
"Disable protection against removing loop preheaders"));
182 cl::desc(
"Use profile info to add section prefix for hot/cold functions"));
185 "profile-unknown-in-special-section",
cl::Hidden,
186 cl::desc(
"In profiling mode like sampleFDO, if a function doesn't have "
187 "profile, we cannot tell the function is cold for sure because "
188 "it may be a function newly added without ever being sampled. "
189 "With the flag enabled, compiler can put such profile unknown "
190 "functions into a special section, so runtime system can choose "
191 "to handle it in a different way than .text section, to save "
192 "RAM for example. "));
196 cl::desc(
"Use the basic-block-sections profile to determine the text "
197 "section prefix for hot functions. Functions with "
198 "basic-block-sections profile will be placed in `.text.hot` "
199 "regardless of their FDO profile info. Other functions won't be "
200 "impacted, i.e., their prefixes will be decided by FDO/sampleFDO "
205 cl::desc(
"Skip merging empty blocks if (frequency of empty block) / "
206 "(frequency of destination block) is greater than this ratio"));
210 cl::desc(
"Force store splitting no matter what the target query says."));
214 cl::desc(
"Enable merging of redundant sexts when one is dominating"
220 cl::desc(
"Disables combining addressing modes with different parts "
221 "in optimizeMemoryInst."));
225 cl::desc(
"Allow creation of Phis in Address sinking."));
229 cl::desc(
"Allow creation of selects in Address sinking."));
233 cl::desc(
"Allow combining of BaseReg field in Address sinking."));
237 cl::desc(
"Allow combining of BaseGV field in Address sinking."));
241 cl::desc(
"Allow combining of BaseOffs field in Address sinking."));
245 cl::desc(
"Allow combining of ScaledReg field in Address sinking."));
250 cl::desc(
"Enable splitting large offset of GEP."));
254 cl::desc(
"Enable ICMP_EQ to ICMP_S(L|G)T conversion."));
258 cl::desc(
"Enable BFI update verification for "
263 cl::desc(
"Enable converting phi types in CodeGenPrepare"));
267 cl::desc(
"Least BB number of huge function."));
272 cl::desc(
"Max number of address users to look at"));
276 cl::desc(
"Disable elimination of dead PHI nodes."));
304class TypePromotionTransaction;
306class CodeGenPrepare {
307 friend class CodeGenPrepareLegacyPass;
316 std::unique_ptr<BlockFrequencyInfo>
BFI;
317 std::unique_ptr<BranchProbabilityInfo> BPI;
332 SetOfInstrs InsertedInsts;
336 InstrToOrigTy PromotedInsts;
339 SetOfInstrs RemovedInsts;
358 ValueToSExts ValToSExtendedUses;
368 std::unique_ptr<DominatorTree> DT;
374 bool IsHugeFunc =
false;
382 void releaseMemory() {
384 InsertedInsts.
clear();
385 PromotedInsts.clear();
394 template <
typename F>
395 void resetIteratorIfInvalidatedWhileCalling(
BasicBlock *BB,
F f) {
399 Value *CurValue = &*CurInstIterator;
406 if (IterHandle != CurValue) {
407 CurInstIterator = BB->
begin();
415 DT = std::make_unique<DominatorTree>(
F);
419 void removeAllAssertingVHReferences(
Value *V);
422 bool eliminateMostlyEmptyBlocks(
Function &
F);
425 void eliminateMostlyEmptyBlock(
BasicBlock *BB);
430 bool optimizeInst(
Instruction *
I, ModifyDT &ModifiedDT);
434 bool optimizeInlineAsmInst(
CallInst *CS);
438 bool optimizeLoadExt(
LoadInst *Load);
444 bool optimizeSwitchPhiConstants(
SwitchInst *SI);
446 bool optimizeExtractElementInst(
Instruction *Inst);
447 bool dupRetToEnableTailCallOpts(
BasicBlock *BB, ModifyDT &ModifiedDT);
455 bool tryToPromoteExts(TypePromotionTransaction &TPT,
458 unsigned CreatedInstsCost = 0);
460 bool splitLargeGEPOffsets();
464 bool performAddressTypePromotion(
465 Instruction *&Inst,
bool AllowPromotionWithoutCommonHeader,
466 bool HasPromoted, TypePromotionTransaction &TPT,
468 bool splitBranchCondition(
Function &
F, ModifyDT &ModifiedDT);
474 bool optimizeCmp(
CmpInst *Cmp, ModifyDT &ModifiedDT);
476 bool combineToUSubWithOverflow(
CmpInst *Cmp, ModifyDT &ModifiedDT);
477 bool combineToUAddWithOverflow(
CmpInst *Cmp, ModifyDT &ModifiedDT);
507char CodeGenPrepareLegacyPass::ID = 0;
509bool CodeGenPrepareLegacyPass::runOnFunction(
Function &
F) {
513 CodeGenPrepare CGP(TM);
514 CGP.DL = &
F.getDataLayout();
515 CGP.SubtargetInfo =
TM->getSubtargetImpl(
F);
516 CGP.TLI = CGP.SubtargetInfo->getTargetLowering();
517 CGP.TRI = CGP.SubtargetInfo->getRegisterInfo();
518 CGP.TLInfo = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(
F);
519 CGP.TTI = &getAnalysis<TargetTransformInfoWrapperPass>().getTTI(
F);
520 CGP.LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
523 CGP.PSI = &getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI();
525 getAnalysisIfAvailable<BasicBlockSectionsProfileReaderWrapperPass>();
526 CGP.BBSectionsProfileReader = BBSPRWP ? &BBSPRWP->getBBSPR() :
nullptr;
532 "Optimize for code generation",
false,
false)
543 return new CodeGenPrepareLegacyPass();
548 CodeGenPrepare CGP(TM);
550 bool Changed = CGP.run(
F, AM);
562 DL = &
F.getDataLayout();
563 SubtargetInfo = TM->getSubtargetImpl(
F);
573 BBSectionsProfileReader =
579 bool EverMadeChange =
false;
581 OptSize =
F.hasOptSize();
586 F.setSectionPrefix(
"hot");
591 if (
F.hasFnAttribute(Attribute::Hot) ||
592 PSI->isFunctionHotInCallGraph(&
F, *BFI))
593 F.setSectionPrefix(
"hot");
597 else if (PSI->isFunctionColdInCallGraph(&
F, *BFI) ||
598 F.hasFnAttribute(Attribute::Cold))
599 F.setSectionPrefix(
"unlikely");
601 PSI->isFunctionHotnessUnknown(
F))
602 F.setSectionPrefix(
"unknown");
611 while (BB !=
nullptr) {
625 EverMadeChange |= eliminateAssumptions(
F);
629 EverMadeChange |= eliminateMostlyEmptyBlocks(
F);
631 ModifyDT ModifiedDT = ModifyDT::NotModifyDT;
633 EverMadeChange |= splitBranchCondition(
F, ModifiedDT);
647 LI->analyze(getDT(
F));
649 bool MadeChange =
true;
650 bool FuncIterated =
false;
655 if (FuncIterated && !FreshBBs.
contains(&BB))
658 ModifyDT ModifiedDTOnIteration = ModifyDT::NotModifyDT;
661 if (ModifiedDTOnIteration == ModifyDT::ModifyBBDT)
664 MadeChange |= Changed;
677 else if (FuncIterated)
682 if (ModifiedDTOnIteration != ModifyDT::NotModifyDT)
687 FuncIterated = IsHugeFunc;
690 MadeChange |= mergeSExts(
F);
691 if (!LargeOffsetGEPMap.
empty())
692 MadeChange |= splitLargeGEPOffsets();
693 MadeChange |= optimizePhiTypes(
F);
696 eliminateFallThrough(
F, DT.get());
700 LI->verify(getDT(
F));
707 EverMadeChange |= MadeChange;
708 SeenChainsForSExt.
clear();
709 ValToSExtendedUses.clear();
710 RemovedInsts.clear();
711 LargeOffsetGEPMap.
clear();
712 LargeOffsetGEPID.
clear();
736 MadeChange |= !WorkList.
empty();
737 while (!WorkList.
empty()) {
750 if (EverMadeChange || MadeChange)
751 MadeChange |= eliminateFallThrough(
F);
753 EverMadeChange |= MadeChange;
760 if (
auto *SP = dyn_cast<GCStatepointInst>(&
I))
762 for (
auto &
I : Statepoints)
763 EverMadeChange |= simplifyOffsetableRelocate(*
I);
768 EverMadeChange |= placeDbgValues(
F);
769 EverMadeChange |= placePseudoProbes(
F);
776 return EverMadeChange;
779bool CodeGenPrepare::eliminateAssumptions(
Function &
F) {
780 bool MadeChange =
false;
782 CurInstIterator = BB.begin();
783 while (CurInstIterator != BB.end()) {
785 if (
auto *Assume = dyn_cast<AssumeInst>(
I)) {
787 Value *Operand = Assume->getOperand(0);
788 Assume->eraseFromParent();
790 resetIteratorIfInvalidatedWhileCalling(&BB, [&]() {
801void CodeGenPrepare::removeAllAssertingVHReferences(
Value *V) {
802 LargeOffsetGEPMap.
erase(V);
803 NewGEPBases.
erase(V);
805 auto GEP = dyn_cast<GetElementPtrInst>(V);
811 auto VecI = LargeOffsetGEPMap.
find(
GEP->getPointerOperand());
812 if (VecI == LargeOffsetGEPMap.
end())
815 auto &GEPVector = VecI->second;
818 if (GEPVector.empty())
819 LargeOffsetGEPMap.
erase(VecI);
828 NewBFI.verifyMatch(*BFI);
835 bool Changed =
false;
845 auto *BB = cast_or_null<BasicBlock>(
Block);
853 if (!SinglePred || SinglePred == BB || BB->hasAddressTaken())
861 if (Term && !
Term->isConditional()) {
873 FreshBBs.
insert(SinglePred);
881 for (
const auto &Pred : Preds)
882 if (
auto *BB = cast_or_null<BasicBlock>(Pred))
898 if (BBI != BB->
begin()) {
900 while (isa<DbgInfoIntrinsic>(BBI)) {
901 if (BBI == BB->
begin())
905 if (!isa<DbgInfoIntrinsic>(BBI) && !isa<PHINode>(BBI))
914 if (!canMergeBlocks(BB, DestBB))
924bool CodeGenPrepare::eliminateMostlyEmptyBlocks(
Function &
F) {
927 while (!LoopList.empty()) {
928 Loop *
L = LoopList.pop_back_val();
931 Preheaders.
insert(Preheader);
934 bool MadeChange =
false;
950 BasicBlock *DestBB = findDestBlockOfMergeableEmptyBlock(BB);
952 !isMergingEmptyBlockProfitable(BB, DestBB, Preheaders.
count(BB)))
955 eliminateMostlyEmptyBlock(BB);
961bool CodeGenPrepare::isMergingEmptyBlockProfitable(
BasicBlock *BB,
977 if (isa<CallBrInst>(Pred->getTerminator()) &&
1009 if (!isa<PHINode>(DestBB->
begin()))
1017 if (DestBBPred == BB)
1021 return DestPN.getIncomingValueForBlock(BB) ==
1022 DestPN.getIncomingValueForBlock(DestBBPred);
1024 SameIncomingValueBBs.
insert(DestBBPred);
1030 if (SameIncomingValueBBs.
count(Pred))
1036 for (
auto *SameValueBB : SameIncomingValueBBs)
1037 if (SameValueBB->getUniquePredecessor() == Pred &&
1038 DestBB == findDestBlockOfMergeableEmptyBlock(SameValueBB))
1039 BBFreq +=
BFI->getBlockFreq(SameValueBB);
1042 return !Limit || PredFreq <= *Limit;
1048bool CodeGenPrepare::canMergeBlocks(
const BasicBlock *BB,
1056 if (UI->
getParent() != DestBB || !isa<PHINode>(UI))
1062 if (
const PHINode *UPN = dyn_cast<PHINode>(UI))
1063 for (
unsigned I = 0, E = UPN->getNumIncomingValues();
I != E; ++
I) {
1065 if (
Insn &&
Insn->getParent() == BB &&
1066 Insn->getParent() != UPN->getIncomingBlock(
I))
1076 const PHINode *DestBBPN = dyn_cast<PHINode>(DestBB->
begin());
1082 if (
const PHINode *BBPN = dyn_cast<PHINode>(BB->
begin())) {
1084 for (
unsigned i = 0, e = BBPN->getNumIncomingValues(); i != e; ++i)
1085 BBPreds.
insert(BBPN->getIncomingBlock(i));
1093 if (BBPreds.
count(Pred)) {
1095 const Value *V1 = PN.getIncomingValueForBlock(Pred);
1096 const Value *
V2 = PN.getIncomingValueForBlock(BB);
1099 if (
const PHINode *V2PN = dyn_cast<PHINode>(V2))
1100 if (V2PN->getParent() == BB)
1101 V2 = V2PN->getIncomingValueForBlock(Pred);
1117 auto *OldI = dyn_cast<Instruction>(Old);
1131void CodeGenPrepare::eliminateMostlyEmptyBlock(
BasicBlock *BB) {
1141 if (SinglePred != DestBB) {
1142 assert(SinglePred == BB &&
1143 "Single predecessor not the same as predecessor");
1152 FreshBBs.
insert(SinglePred);
1153 FreshBBs.
erase(DestBB);
1163 Value *InVal = PN.removeIncomingValue(BB,
false);
1167 PHINode *InValPhi = dyn_cast<PHINode>(InVal);
1168 if (InValPhi && InValPhi->
getParent() == BB) {
1177 for (
unsigned i = 0, e = BBPN->getNumIncomingValues(); i != e; ++i)
1178 PN.addIncoming(InVal, BBPN->getIncomingBlock(i));
1181 PN.addIncoming(InVal, Pred);
1205 for (
auto *ThisRelocate : AllRelocateCalls) {
1206 auto K = std::make_pair(ThisRelocate->getBasePtrIndex(),
1207 ThisRelocate->getDerivedPtrIndex());
1208 RelocateIdxMap.
insert(std::make_pair(K, ThisRelocate));
1210 for (
auto &Item : RelocateIdxMap) {
1211 std::pair<unsigned, unsigned> Key = Item.first;
1212 if (Key.first == Key.second)
1217 auto BaseKey = std::make_pair(Key.first, Key.first);
1220 auto MaybeBase = RelocateIdxMap.
find(BaseKey);
1221 if (MaybeBase == RelocateIdxMap.
end())
1226 RelocateInstMap[MaybeBase->second].push_back(
I);
1234 for (
unsigned i = 1; i <
GEP->getNumOperands(); i++) {
1236 auto *
Op = dyn_cast<ConstantInt>(
GEP->getOperand(i));
1237 if (!
Op ||
Op->getZExtValue() > 20)
1241 for (
unsigned i = 1; i <
GEP->getNumOperands(); i++)
1251 bool MadeChange =
false;
1258 for (
auto R = RelocatedBase->
getParent()->getFirstInsertionPt();
1259 &*R != RelocatedBase; ++R)
1260 if (
auto *RI = dyn_cast<GCRelocateInst>(R))
1270 "Not relocating a derived object of the original base object");
1271 if (ToReplace->getBasePtrIndex() == ToReplace->getDerivedPtrIndex()) {
1276 if (RelocatedBase->
getParent() != ToReplace->getParent()) {
1285 auto *Derived = dyn_cast<GetElementPtrInst>(ToReplace->getDerivedPtr());
1286 if (!Derived || Derived->getPointerOperand() !=
Base)
1295 "Should always have one since it's not a terminator");
1323 Value *ActualRelocatedBase = RelocatedBase;
1324 if (RelocatedBase->
getType() !=
Base->getType()) {
1325 ActualRelocatedBase =
1328 Value *Replacement =
1329 Builder.
CreateGEP(Derived->getSourceElementType(), ActualRelocatedBase,
1335 Value *ActualReplacement = Replacement;
1336 if (Replacement->
getType() != ToReplace->getType()) {
1341 ToReplace->eraseFromParent();
1366 bool MadeChange =
false;
1368 for (
auto *U :
I.users())
1375 if (AllRelocateCalls.
size() < 2)
1382 if (RelocateInstMap.
empty())
1385 for (
auto &Item : RelocateInstMap)
1399 bool MadeChange =
false;
1402 Use &TheUse = UI.getUse();
1409 UserBB = PN->getIncomingBlock(TheUse);
1417 if (
User->isEHPad())
1427 if (UserBB == DefBB)
1431 CastInst *&InsertedCast = InsertedCasts[UserBB];
1433 if (!InsertedCast) {
1436 InsertedCast = cast<CastInst>(CI->
clone());
1441 TheUse = InsertedCast;
1465 if (
auto *ASC = dyn_cast<AddrSpaceCastInst>(CI)) {
1467 ASC->getDestAddressSpace()))
1507 match(IVInc, m_ExtractValue<0>(m_Intrinsic<Intrinsic::uadd_with_overflow>(
1511 match(IVInc, m_ExtractValue<0>(m_Intrinsic<Intrinsic::usub_with_overflow>(
1522static std::optional<std::pair<Instruction *, Constant *>>
1525 if (!L || L->getHeader() != PN->
getParent() || !L->getLoopLatch())
1526 return std::nullopt;
1529 if (!IVInc || LI->
getLoopFor(IVInc->getParent()) != L)
1530 return std::nullopt;
1534 return std::make_pair(IVInc, Step);
1535 return std::nullopt;
1539 auto *
I = dyn_cast<Instruction>(V);
1546 if (
auto *PN = dyn_cast<PHINode>(
LHS))
1548 return IVInc->first ==
I;
1552bool CodeGenPrepare::replaceMathCmpWithIntrinsic(
BinaryOperator *BO,
1560 assert(L &&
"L should not be null after isIVIncrement()");
1562 if (LI->getLoopFor(
Cmp->getParent()) != L)
1568 auto &DT = getDT(*BO->
getParent()->getParent());
1577 if (BO->
getParent() !=
Cmp->getParent() && !IsReplacableIVIncrement(BO)) {
1600 if (BO->
getOpcode() == Instruction::Add &&
1601 IID == Intrinsic::usub_with_overflow) {
1602 assert(isa<Constant>(Arg1) &&
"Unexpected input for usubo");
1611 if ((BO->
getOpcode() != Instruction::Xor && &Iter == BO) || &Iter == Cmp) {
1616 assert(InsertPt !=
nullptr &&
"Parent block did not contain cmp or binop");
1619 Value *MathOV = Builder.CreateBinaryIntrinsic(IID, Arg0, Arg1);
1620 if (BO->
getOpcode() != Instruction::Xor) {
1621 Value *Math = Builder.CreateExtractValue(MathOV, 0,
"math");
1625 "Patterns with XOr should use the BO only in the compare");
1626 Value *OV = Builder.CreateExtractValue(MathOV, 1,
"ov");
1628 Cmp->eraseFromParent();
1638 Value *
A = Cmp->getOperand(0), *
B = Cmp->getOperand(1);
1641 if (isa<Constant>(
A))
1646 B = ConstantInt::get(
B->getType(), 1);
1654 for (
User *U :
A->users()) {
1656 Add = cast<BinaryOperator>(U);
1665bool CodeGenPrepare::combineToUAddWithOverflow(
CmpInst *Cmp,
1666 ModifyDT &ModifiedDT) {
1667 bool EdgeCase =
false;
1674 A =
Add->getOperand(0);
1675 B =
Add->getOperand(1);
1681 Add->hasNUsesOrMore(EdgeCase ? 1 : 2)))
1687 if (
Add->getParent() !=
Cmp->getParent() && !
Add->hasOneUse())
1690 if (!replaceMathCmpWithIntrinsic(
Add,
A,
B, Cmp,
1691 Intrinsic::uadd_with_overflow))
1695 ModifiedDT = ModifyDT::ModifyInstDT;
1699bool CodeGenPrepare::combineToUSubWithOverflow(
CmpInst *Cmp,
1700 ModifyDT &ModifiedDT) {
1703 if (isa<Constant>(
A) && isa<Constant>(
B))
1714 B = ConstantInt::get(
B->getType(), 1);
1728 Value *CmpVariableOperand = isa<Constant>(
A) ?
B :
A;
1730 for (
User *U : CmpVariableOperand->
users()) {
1733 Sub = cast<BinaryOperator>(U);
1738 const APInt *CmpC, *AddC;
1741 Sub = cast<BinaryOperator>(U);
1754 Cmp, Intrinsic::usub_with_overflow))
1758 ModifiedDT = ModifyDT::ModifyInstDT;
1779 bool MadeChange =
false;
1782 Use &TheUse = UI.getUse();
1789 if (isa<PHINode>(
User))
1797 if (UserBB == DefBB)
1801 CmpInst *&InsertedCmp = InsertedCmps[UserBB];
1807 Cmp->getOperand(0), Cmp->getOperand(1),
"");
1814 TheUse = InsertedCmp;
1820 if (Cmp->use_empty()) {
1821 Cmp->eraseFromParent();
1858 for (
User *U : Cmp->users()) {
1859 if (isa<BranchInst>(U))
1861 if (isa<SelectInst>(U) && cast<SelectInst>(U)->getCondition() == Cmp)
1880 if (CmpBB != FalseBB)
1883 Value *CmpOp0 = Cmp->getOperand(0), *CmpOp1 = Cmp->getOperand(1);
1897 for (
User *U : Cmp->users()) {
1898 if (
auto *BI = dyn_cast<BranchInst>(U)) {
1903 if (
auto *SI = dyn_cast<SelectInst>(U)) {
1906 SI->swapProfMetadata();
1918 Value *Op0 = Cmp->getOperand(0);
1919 Value *Op1 = Cmp->getOperand(1);
1921 isa<Constant>(Op1) || Op0 == Op1)
1928 unsigned NumInspected = 0;
1931 if (++NumInspected > 128)
1939 if (GoodToSwap > 0) {
1940 Cmp->swapOperands();
1948 FCmpInst *FCmp = dyn_cast<FCmpInst>(Cmp);
1960 auto ShouldReverseTransform = [](
FPClassTest ClassTest) {
1963 auto [ClassVal, ClassTest] =
1969 if (!ShouldReverseTransform(ClassTest) && !ShouldReverseTransform(~ClassTest))
1974 Cmp->replaceAllUsesWith(IsFPClass);
1983 Value *Incr, *RemAmt;
1989 auto *PN = dyn_cast<PHINode>(Incr);
1995 if (PN->getNumIncomingValues() != 2)
2000 if (!L || !L->getLoopPreheader() || !L->getLoopLatch())
2004 if (!L->contains(Rem))
2008 if (!L->isLoopInvariant(RemAmt))
2089 NewRem->
addIncoming(Start, L->getLoopPreheader());
2094 FreshBBs.
insert(L->getLoopLatch());
2102bool CodeGenPrepare::optimizeURem(
Instruction *Rem) {
2108bool CodeGenPrepare::optimizeCmp(
CmpInst *Cmp, ModifyDT &ModifiedDT) {
2112 if (combineToUAddWithOverflow(Cmp, ModifiedDT))
2115 if (combineToUSubWithOverflow(Cmp, ModifiedDT))
2136 SetOfInstrs &InsertedInsts) {
2139 assert(!InsertedInsts.count(AndI) &&
2140 "Attempting to optimize already optimized and instruction");
2141 (void)InsertedInsts;
2150 if (!isa<ConstantInt>(AndI->
getOperand(0)) &&
2155 for (
auto *U : AndI->
users()) {
2159 if (!isa<ICmpInst>(
User))
2163 if (!CmpC || !CmpC->
isZero())
2178 Use &TheUse = UI.getUse();
2196 TheUse = InsertedAnd;
2212 if (!isa<TruncInst>(
User)) {
2213 if (
User->getOpcode() != Instruction::And ||
2219 if ((Cimm & (Cimm + 1)).getBoolValue())
2232 auto *TruncI = cast<TruncInst>(
User);
2233 bool MadeChange =
false;
2236 TruncE = TruncI->user_end();
2237 TruncUI != TruncE;) {
2239 Use &TruncTheUse = TruncUI.getUse();
2240 Instruction *TruncUser = cast<Instruction>(*TruncUI);
2259 if (isa<PHINode>(TruncUser))
2264 if (UserBB == TruncUserBB)
2268 CastInst *&InsertedTrunc = InsertedTruncs[TruncUserBB];
2270 if (!InsertedShift && !InsertedTrunc) {
2274 if (ShiftI->
getOpcode() == Instruction::AShr)
2276 BinaryOperator::CreateAShr(ShiftI->
getOperand(0), CI,
"");
2279 BinaryOperator::CreateLShr(ShiftI->
getOperand(0), CI,
"");
2287 TruncInsertPt.setHeadBit(
true);
2288 assert(TruncInsertPt != TruncUserBB->
end());
2292 InsertedTrunc->
insertBefore(*TruncUserBB, TruncInsertPt);
2293 InsertedTrunc->
setDebugLoc(TruncI->getDebugLoc());
2297 TruncTheUse = InsertedTrunc;
2330 bool MadeChange =
false;
2333 Use &TheUse = UI.getUse();
2339 if (isa<PHINode>(
User))
2347 if (UserBB == DefBB) {
2362 if (isa<TruncInst>(
User) &&
2375 if (!InsertedShift) {
2379 if (ShiftI->
getOpcode() == Instruction::AShr)
2381 BinaryOperator::CreateAShr(ShiftI->
getOperand(0), CI,
"");
2384 BinaryOperator::CreateLShr(ShiftI->
getOperand(0), CI,
"");
2392 TheUse = InsertedShift;
2441 if (Ty->
isVectorTy() || SizeInBits >
DL->getLargestLegalIntTypeSizeInBits())
2453 FreshBBs.
insert(CallBlock);
2460 SplitPt.setHeadBit(
true);
2463 FreshBBs.
insert(EndBlock);
2468 L->addBasicBlockToLoop(CallBlock, LI);
2469 L->addBasicBlockToLoop(EndBlock, LI);
2500 ModifiedDT = ModifyDT::ModifyBBDT;
2504bool CodeGenPrepare::optimizeCallInst(
CallInst *CI, ModifyDT &ModifiedDT) {
2513 CurInstIterator = BB->
begin();
2520 if (optimizeInlineAsmInst(CI))
2529 for (
auto &Arg : CI->
args()) {
2534 if (!Arg->getType()->isPointerTy())
2537 cast<PointerType>(Arg->getType())->getAddressSpace()),
2544 if ((AI = dyn_cast<AllocaInst>(Val)) && AI->
getAlign() < PrefAlign &&
2563 if (!MIDestAlign || DestAlign > *MIDestAlign)
2564 MI->setDestAlignment(DestAlign);
2566 MaybeAlign MTISrcAlign = MTI->getSourceAlign();
2568 if (!MTISrcAlign || SrcAlign > *MTISrcAlign)
2569 MTI->setSourceAlignment(SrcAlign);
2577 if (CI->
hasFnAttr(Attribute::Cold) && !OptSize &&
2579 for (
auto &Arg : CI->
args()) {
2580 if (!Arg->getType()->isPointerTy())
2582 unsigned AS = Arg->getType()->getPointerAddressSpace();
2583 if (optimizeMemoryInst(CI, Arg, Arg->getType(), AS))
2589 switch (
II->getIntrinsicID()) {
2592 case Intrinsic::assume:
2594 case Intrinsic::allow_runtime_check:
2595 case Intrinsic::allow_ubsan_check:
2596 case Intrinsic::experimental_widenable_condition: {
2600 if (
II->use_empty()) {
2601 II->eraseFromParent();
2605 resetIteratorIfInvalidatedWhileCalling(BB, [&]() {
2610 case Intrinsic::objectsize:
2612 case Intrinsic::is_constant:
2614 case Intrinsic::aarch64_stlxr:
2615 case Intrinsic::aarch64_stxr: {
2624 InsertedInsts.insert(ExtVal);
2628 case Intrinsic::launder_invariant_group:
2629 case Intrinsic::strip_invariant_group: {
2630 Value *ArgVal =
II->getArgOperand(0);
2631 auto it = LargeOffsetGEPMap.
find(
II);
2632 if (it != LargeOffsetGEPMap.
end()) {
2636 auto GEPs = std::move(it->second);
2637 LargeOffsetGEPMap[ArgVal].append(GEPs.begin(), GEPs.end());
2642 II->eraseFromParent();
2645 case Intrinsic::cttz:
2646 case Intrinsic::ctlz:
2650 case Intrinsic::fshl:
2651 case Intrinsic::fshr:
2652 return optimizeFunnelShift(
II);
2653 case Intrinsic::dbg_assign:
2654 case Intrinsic::dbg_value:
2655 return fixupDbgValue(
II);
2656 case Intrinsic::masked_gather:
2657 return optimizeGatherScatterInst(
II,
II->getArgOperand(0));
2658 case Intrinsic::masked_scatter:
2659 return optimizeGatherScatterInst(
II,
II->getArgOperand(1));
2665 while (!PtrOps.
empty()) {
2668 if (optimizeMemoryInst(
II, PtrVal, AccessTy, AS))
2683 if (
Value *V = Simplifier.optimizeCall(CI, Builder)) {
2696 if (
const auto *
II = dyn_cast<IntrinsicInst>(CI))
2697 switch (
II->getIntrinsicID()) {
2698 case Intrinsic::memset:
2699 case Intrinsic::memcpy:
2700 case Intrinsic::memmove:
2708 if (Callee && TLInfo && TLInfo->
getLibFunc(*Callee, LF))
2710 case LibFunc_strcpy:
2711 case LibFunc_strncpy:
2712 case LibFunc_strcat:
2713 case LibFunc_strncat:
2754bool CodeGenPrepare::dupRetToEnableTailCallOpts(
BasicBlock *BB,
2755 ModifyDT &ModifiedDT) {
2763 assert(LI->getLoopFor(BB) ==
nullptr &&
"A return block cannot be in a loop");
2770 BCI = dyn_cast<BitCastInst>(V);
2774 EVI = dyn_cast<ExtractValueInst>(V);
2781 PN = dyn_cast<PHINode>(V);
2787 auto isLifetimeEndOrBitCastFor = [](
const Instruction *Inst) {
2788 const BitCastInst *BC = dyn_cast<BitCastInst>(Inst);
2793 return II->getIntrinsicID() == Intrinsic::lifetime_end;
2801 while (isa<DbgInfoIntrinsic>(BI) || BI == BCI || BI == EVI ||
2802 isa<PseudoProbeInst>(BI) || isLifetimeEndOrBitCastFor(BI))
2815 CallInst *CI = dyn_cast<CallInst>(IncomingVal);
2834 CI = dyn_cast_or_null<CallInst>(
2848 if (!VisitedBBs.
insert(Pred).second)
2850 if (
Instruction *
I = Pred->rbegin()->getPrevNonDebugInstruction(
true)) {
2856 if (!V || isa<UndefValue>(V) ||
2866 bool Changed =
false;
2867 for (
auto const &TailCallBB : TailCallBBs) {
2870 BranchInst *BI = dyn_cast<BranchInst>(TailCallBB->getTerminator());
2877 BFI->getBlockFreq(BB) >=
BFI->getBlockFreq(TailCallBB));
2878 BFI->setBlockFreq(BB,
2879 (
BFI->getBlockFreq(BB) -
BFI->getBlockFreq(TailCallBB)));
2880 ModifiedDT = ModifyDT::ModifyBBDT;
2903 Value *OriginalValue =
nullptr;
2904 bool InBounds =
true;
2908 BaseRegField = 0x01,
2910 BaseOffsField = 0x04,
2911 ScaledRegField = 0x08,
2913 MultipleFields = 0xff
2926 return MultipleFields;
2927 if (BaseGV && other.BaseGV && BaseGV->getType() != other.BaseGV->getType())
2928 return MultipleFields;
2931 return MultipleFields;
2934 if (InBounds != other.InBounds)
2935 return MultipleFields;
2938 unsigned Result = NoField;
2941 if (BaseGV != other.BaseGV)
2943 if (BaseOffs != other.BaseOffs)
2946 Result |= ScaledRegField;
2953 return MultipleFields;
2955 return static_cast<FieldName
>(
Result);
2976 case ScaledRegField:
2979 return ConstantInt::get(IntPtrTy, BaseOffs);
2983 void SetCombinedField(FieldName
Field,
Value *V,
2989 case ExtAddrMode::BaseRegField:
2992 case ExtAddrMode::BaseGVField:
2999 case ExtAddrMode::ScaledRegField:
3010 case ExtAddrMode::BaseOffsField:
3029#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
3031 bool NeedPlus =
false;
3037 BaseGV->printAsOperand(
OS,
false);
3042 OS << (NeedPlus ?
" + " :
"") << BaseOffs;
3047 OS << (NeedPlus ?
" + " :
"") <<
"Base:";
3052 OS << (NeedPlus ?
" + " :
"") <<
Scale <<
"*";
3075class TypePromotionTransaction {
3079 class TypePromotionAction {
3087 TypePromotionAction(
Instruction *Inst) : Inst(Inst) {}
3089 virtual ~TypePromotionAction() =
default;
3096 virtual void undo() = 0;
3101 virtual void commit() {
3107 class InsertionHandler {
3116 std::optional<DbgRecord::self_iterator> BeforeDbgRecord = std::nullopt;
3119 bool HasPrevInstruction;
3124 HasPrevInstruction = (Inst != &*(Inst->
getParent()->begin()));
3132 if (HasPrevInstruction) {
3133 Point.PrevInst = &*std::prev(Inst->
getIterator());
3141 if (HasPrevInstruction) {
3153 Inst->
getParent()->reinsertInstInDbgRecords(Inst, BeforeDbgRecord);
3158 class InstructionMoveBefore :
public TypePromotionAction {
3160 InsertionHandler Position;
3165 : TypePromotionAction(Inst), Position(Inst) {
3172 void undo()
override {
3174 Position.insert(Inst);
3179 class OperandSetter :
public TypePromotionAction {
3189 : TypePromotionAction(Inst),
Idx(
Idx) {
3191 <<
"for:" << *Inst <<
"\n"
3192 <<
"with:" << *NewVal <<
"\n");
3198 void undo()
override {
3200 <<
"for: " << *Inst <<
"\n"
3201 <<
"with: " << *Origin <<
"\n");
3208 class OperandsHider :
public TypePromotionAction {
3214 OperandsHider(
Instruction *Inst) : TypePromotionAction(Inst) {
3217 OriginalValues.
reserve(NumOpnds);
3218 for (
unsigned It = 0; It < NumOpnds; ++It) {
3230 void undo()
override {
3232 for (
unsigned It = 0, EndIt = OriginalValues.
size(); It != EndIt; ++It)
3238 class TruncBuilder :
public TypePromotionAction {
3245 TruncBuilder(
Instruction *Opnd,
Type *Ty) : TypePromotionAction(Opnd) {
3247 Builder.SetCurrentDebugLocation(
DebugLoc());
3248 Val = Builder.CreateTrunc(Opnd, Ty,
"promoted");
3253 Value *getBuiltValue() {
return Val; }
3256 void undo()
override {
3258 if (
Instruction *IVal = dyn_cast<Instruction>(Val))
3259 IVal->eraseFromParent();
3264 class SExtBuilder :
public TypePromotionAction {
3272 : TypePromotionAction(InsertPt) {
3274 Val = Builder.CreateSExt(Opnd, Ty,
"promoted");
3279 Value *getBuiltValue() {
return Val; }
3282 void undo()
override {
3284 if (
Instruction *IVal = dyn_cast<Instruction>(Val))
3285 IVal->eraseFromParent();
3290 class ZExtBuilder :
public TypePromotionAction {
3298 : TypePromotionAction(InsertPt) {
3300 Builder.SetCurrentDebugLocation(
DebugLoc());
3301 Val = Builder.CreateZExt(Opnd, Ty,
"promoted");
3306 Value *getBuiltValue() {
return Val; }
3309 void undo()
override {
3311 if (
Instruction *IVal = dyn_cast<Instruction>(Val))
3312 IVal->eraseFromParent();
3317 class TypeMutator :
public TypePromotionAction {
3324 : TypePromotionAction(Inst), OrigTy(Inst->
getType()) {
3325 LLVM_DEBUG(
dbgs() <<
"Do: MutateType: " << *Inst <<
" with " << *NewTy
3331 void undo()
override {
3332 LLVM_DEBUG(
dbgs() <<
"Undo: MutateType: " << *Inst <<
" with " << *OrigTy
3339 class UsesReplacer :
public TypePromotionAction {
3341 struct InstructionAndIdx {
3349 : Inst(Inst),
Idx(
Idx) {}
3368 : TypePromotionAction(Inst),
New(
New) {
3369 LLVM_DEBUG(
dbgs() <<
"Do: UsersReplacer: " << *Inst <<
" with " << *New
3374 OriginalUses.
push_back(InstructionAndIdx(UserI,
U.getOperandNo()));
3385 void undo()
override {
3387 for (InstructionAndIdx &
Use : OriginalUses)
3388 Use.Inst->setOperand(
Use.Idx, Inst);
3393 for (
auto *DVI : DbgValues)
3394 DVI->replaceVariableLocationOp(New, Inst);
3398 DVR->replaceVariableLocationOp(New, Inst);
3403 class InstructionRemover :
public TypePromotionAction {
3405 InsertionHandler Inserter;
3409 OperandsHider Hider;
3412 UsesReplacer *Replacer =
nullptr;
3415 SetOfInstrs &RemovedInsts;
3422 InstructionRemover(
Instruction *Inst, SetOfInstrs &RemovedInsts,
3423 Value *New =
nullptr)
3424 : TypePromotionAction(Inst), Inserter(Inst), Hider(Inst),
3425 RemovedInsts(RemovedInsts) {
3427 Replacer =
new UsesReplacer(Inst, New);
3428 LLVM_DEBUG(
dbgs() <<
"Do: InstructionRemover: " << *Inst <<
"\n");
3429 RemovedInsts.insert(Inst);
3436 ~InstructionRemover()
override {
delete Replacer; }
3438 InstructionRemover &operator=(
const InstructionRemover &other) =
delete;
3439 InstructionRemover(
const InstructionRemover &other) =
delete;
3443 void undo()
override {
3444 LLVM_DEBUG(
dbgs() <<
"Undo: InstructionRemover: " << *Inst <<
"\n");
3445 Inserter.insert(Inst);
3449 RemovedInsts.erase(Inst);
3457 using ConstRestorationPt =
const TypePromotionAction *;
3459 TypePromotionTransaction(SetOfInstrs &RemovedInsts)
3460 : RemovedInsts(RemovedInsts) {}
3467 void rollback(ConstRestorationPt Point);
3470 ConstRestorationPt getRestorationPoint()
const;
3502 SetOfInstrs &RemovedInsts;
3507void TypePromotionTransaction::setOperand(
Instruction *Inst,
unsigned Idx,
3509 Actions.
push_back(std::make_unique<TypePromotionTransaction::OperandSetter>(
3510 Inst,
Idx, NewVal));
3513void TypePromotionTransaction::eraseInstruction(
Instruction *Inst,
3516 std::make_unique<TypePromotionTransaction::InstructionRemover>(
3517 Inst, RemovedInsts, NewVal));
3520void TypePromotionTransaction::replaceAllUsesWith(
Instruction *Inst,
3523 std::make_unique<TypePromotionTransaction::UsesReplacer>(Inst, New));
3526void TypePromotionTransaction::mutateType(
Instruction *Inst,
Type *NewTy) {
3528 std::make_unique<TypePromotionTransaction::TypeMutator>(Inst, NewTy));
3532 std::unique_ptr<TruncBuilder>
Ptr(
new TruncBuilder(Opnd, Ty));
3534 Actions.push_back(std::move(
Ptr));
3540 std::unique_ptr<SExtBuilder>
Ptr(
new SExtBuilder(Inst, Opnd, Ty));
3542 Actions.push_back(std::move(
Ptr));
3548 std::unique_ptr<ZExtBuilder>
Ptr(
new ZExtBuilder(Inst, Opnd, Ty));
3550 Actions.push_back(std::move(
Ptr));
3554TypePromotionTransaction::ConstRestorationPt
3555TypePromotionTransaction::getRestorationPoint()
const {
3556 return !Actions.empty() ? Actions.back().get() :
nullptr;
3559bool TypePromotionTransaction::commit() {
3560 for (std::unique_ptr<TypePromotionAction> &Action : Actions)
3567void TypePromotionTransaction::rollback(
3568 TypePromotionTransaction::ConstRestorationPt Point) {
3569 while (!Actions.empty() && Point != Actions.back().get()) {
3570 std::unique_ptr<TypePromotionAction> Curr = Actions.pop_back_val();
3580class AddressingModeMatcher {
3599 const SetOfInstrs &InsertedInsts;
3602 InstrToOrigTy &PromotedInsts;
3605 TypePromotionTransaction &TPT;
3608 std::pair<AssertingVH<GetElementPtrInst>, int64_t> &LargeOffsetGEP;
3612 bool IgnoreProfitability;
3615 bool OptSize =
false;
3620 AddressingModeMatcher(
3625 const SetOfInstrs &InsertedInsts, InstrToOrigTy &PromotedInsts,
3626 TypePromotionTransaction &TPT,
3629 : AddrModeInsts(AMI), TLI(TLI),
TRI(
TRI),
3630 DL(
MI->getDataLayout()), LI(LI), getDTFn(getDTFn),
3631 AccessTy(AT), AddrSpace(AS), MemoryInst(
MI),
AddrMode(AM),
3632 InsertedInsts(InsertedInsts), PromotedInsts(PromotedInsts), TPT(TPT),
3633 LargeOffsetGEP(LargeOffsetGEP), OptSize(OptSize), PSI(PSI),
BFI(
BFI) {
3634 IgnoreProfitability =
false;
3651 InstrToOrigTy &PromotedInsts, TypePromotionTransaction &TPT,
3656 bool Success = AddressingModeMatcher(AddrModeInsts, TLI,
TRI, LI, getDTFn,
3657 AccessTy, AS, MemoryInst, Result,
3658 InsertedInsts, PromotedInsts, TPT,
3659 LargeOffsetGEP, OptSize, PSI, BFI)
3667 bool matchScaledValue(
Value *ScaleReg, int64_t Scale,
unsigned Depth);
3669 bool matchOperationAddr(
User *AddrInst,
unsigned Opcode,
unsigned Depth,
3670 bool *MovedAway =
nullptr);
3671 bool isProfitableToFoldIntoAddressingMode(
Instruction *
I,
3674 bool valueAlreadyLiveAtInst(
Value *Val,
Value *KnownLive1,
Value *KnownLive2);
3675 bool isPromotionProfitable(
unsigned NewCost,
unsigned OldCost,
3676 Value *PromotedOperand)
const;
3682class PhiNodeSetIterator {
3683 PhiNodeSet *
const Set;
3684 size_t CurrentIndex = 0;
3689 PhiNodeSetIterator(PhiNodeSet *
const Set,
size_t Start);
3691 PhiNodeSetIterator &operator++();
3707 friend class PhiNodeSetIterator;
3710 using iterator = PhiNodeSetIterator;
3725 size_t FirstValidElement = 0;
3732 if (NodeMap.insert(std::make_pair(
Ptr,
NodeList.size())).second) {
3743 if (NodeMap.erase(
Ptr)) {
3744 SkipRemovedElements(FirstValidElement);
3754 FirstValidElement = 0;
3760 if (FirstValidElement == 0)
3761 SkipRemovedElements(FirstValidElement);
3762 return PhiNodeSetIterator(
this, FirstValidElement);
3766 iterator
end() {
return PhiNodeSetIterator(
this,
NodeList.size()); }
3769 size_t size()
const {
return NodeMap.size(); }
3780 void SkipRemovedElements(
size_t &CurrentIndex) {
3781 while (CurrentIndex <
NodeList.size()) {
3782 auto it = NodeMap.find(
NodeList[CurrentIndex]);
3785 if (it != NodeMap.end() && it->second == CurrentIndex)
3792PhiNodeSetIterator::PhiNodeSetIterator(PhiNodeSet *
const Set,
size_t Start)
3793 :
Set(
Set), CurrentIndex(Start) {}
3795PHINode *PhiNodeSetIterator::operator*()
const {
3797 "PhiNodeSet access out of range");
3798 return Set->NodeList[CurrentIndex];
3801PhiNodeSetIterator &PhiNodeSetIterator::operator++() {
3803 "PhiNodeSet access out of range");
3805 Set->SkipRemovedElements(CurrentIndex);
3809bool PhiNodeSetIterator::operator==(
const PhiNodeSetIterator &RHS)
const {
3810 return CurrentIndex ==
RHS.CurrentIndex;
3813bool PhiNodeSetIterator::operator!=(
const PhiNodeSetIterator &RHS)
const {
3814 return !((*this) ==
RHS);
3820class SimplificationTracker {
3825 PhiNodeSet AllPhiNodes;
3834 auto SV = Storage.
find(V);
3835 if (SV == Storage.
end())
3845 while (!WorkList.
empty()) {
3847 if (!Visited.
insert(
P).second)
3849 if (
auto *PI = dyn_cast<Instruction>(
P))
3851 for (
auto *U : PI->users())
3854 PI->replaceAllUsesWith(V);
3855 if (
auto *
PHI = dyn_cast<PHINode>(PI))
3856 AllPhiNodes.erase(
PHI);
3857 if (
auto *
Select = dyn_cast<SelectInst>(PI))
3859 PI->eraseFromParent();
3869 while (OldReplacement !=
From) {
3871 To = dyn_cast<PHINode>(OldReplacement);
3872 OldReplacement = Get(
From);
3874 assert(To && Get(To) == To &&
"Replacement PHI node is already replaced.");
3876 From->replaceAllUsesWith(To);
3877 AllPhiNodes.erase(
From);
3878 From->eraseFromParent();
3881 PhiNodeSet &newPhiNodes() {
return AllPhiNodes; }
3883 void insertNewPhi(
PHINode *PN) { AllPhiNodes.insert(PN); }
3887 unsigned countNewPhiNodes()
const {
return AllPhiNodes.size(); }
3889 unsigned countNewSelectNodes()
const {
return AllSelectNodes.
size(); }
3891 void destroyNewNodes(
Type *CommonType) {
3894 for (
auto *
I : AllPhiNodes) {
3895 I->replaceAllUsesWith(Dummy);
3896 I->eraseFromParent();
3898 AllPhiNodes.clear();
3899 for (
auto *
I : AllSelectNodes) {
3900 I->replaceAllUsesWith(Dummy);
3901 I->eraseFromParent();
3903 AllSelectNodes.clear();
3908class AddressingModeCombiner {
3910 typedef std::pair<PHINode *, PHINode *> PHIPair;
3917 ExtAddrMode::FieldName DifferentField = ExtAddrMode::NoField;
3920 bool AllAddrModesTrivial =
true;
3923 Type *CommonType =
nullptr;
3932 Value *CommonValue =
nullptr;
3936 : SQ(_SQ), Original(OriginalValue) {}
3938 ~AddressingModeCombiner() { eraseCommonValueIfDead(); }
3950 AllAddrModesTrivial = AllAddrModesTrivial && NewAddrMode.isTrivial();
3953 if (AddrModes.
empty()) {
3961 ExtAddrMode::FieldName ThisDifferentField =
3962 AddrModes[0].compare(NewAddrMode);
3963 if (DifferentField == ExtAddrMode::NoField)
3964 DifferentField = ThisDifferentField;
3965 else if (DifferentField != ThisDifferentField)
3966 DifferentField = ExtAddrMode::MultipleFields;
3969 bool CanHandle = DifferentField != ExtAddrMode::MultipleFields;
3972 CanHandle = CanHandle && DifferentField != ExtAddrMode::ScaleField;
3977 CanHandle = CanHandle && (DifferentField != ExtAddrMode::BaseOffsField ||
3982 CanHandle = CanHandle && (DifferentField != ExtAddrMode::BaseGVField ||
3983 !NewAddrMode.HasBaseReg);
4000 bool combineAddrModes() {
4002 if (AddrModes.
size() == 0)
4006 if (AddrModes.
size() == 1 || DifferentField == ExtAddrMode::NoField)
4011 if (AllAddrModesTrivial)
4014 if (!addrModeCombiningAllowed())
4020 FoldAddrToValueMapping
Map;
4021 if (!initializeMap(Map))
4024 CommonValue = findCommon(Map);
4026 AddrModes[0].SetCombinedField(DifferentField, CommonValue, AddrModes);
4027 return CommonValue !=
nullptr;
4033 void eraseCommonValueIfDead() {
4034 if (CommonValue && CommonValue->
getNumUses() == 0)
4035 if (
Instruction *CommonInst = dyn_cast<Instruction>(CommonValue))
4036 CommonInst->eraseFromParent();
4044 bool initializeMap(FoldAddrToValueMapping &Map) {
4049 for (
auto &AM : AddrModes) {
4050 Value *DV = AM.GetFieldAsValue(DifferentField, IntPtrTy);
4053 if (CommonType && CommonType !=
Type)
4056 Map[AM.OriginalValue] = DV;
4061 assert(CommonType &&
"At least one non-null value must be!");
4062 for (
auto *V : NullValue)
4090 Value *findCommon(FoldAddrToValueMapping &Map) {
4098 SimplificationTracker
ST(SQ);
4103 InsertPlaceholders(Map, TraverseOrder, ST);
4106 FillPlaceholders(Map, TraverseOrder, ST);
4109 ST.destroyNewNodes(CommonType);
4114 unsigned PhiNotMatchedCount = 0;
4116 ST.destroyNewNodes(CommonType);
4120 auto *
Result =
ST.Get(
Map.find(Original)->second);
4122 NumMemoryInstsPhiCreated +=
ST.countNewPhiNodes() + PhiNotMatchedCount;
4123 NumMemoryInstsSelectCreated +=
ST.countNewSelectNodes();
4132 PhiNodeSet &PhiNodesToMatch) {
4139 while (!WorkList.
empty()) {
4141 if (!Visited.
insert(Item).second)
4148 for (
auto *
B : Item.first->blocks()) {
4149 Value *FirstValue = Item.first->getIncomingValueForBlock(
B);
4150 Value *SecondValue = Item.second->getIncomingValueForBlock(
B);
4151 if (FirstValue == SecondValue)
4154 PHINode *FirstPhi = dyn_cast<PHINode>(FirstValue);
4155 PHINode *SecondPhi = dyn_cast<PHINode>(SecondValue);
4161 if (!FirstPhi || !SecondPhi || !PhiNodesToMatch.count(FirstPhi) ||
4166 if (Matcher.
count({FirstPhi, SecondPhi}))
4171 if (MatchedPHIs.
insert(FirstPhi).second)
4172 Matcher.
insert({FirstPhi, SecondPhi});
4174 WorkList.
push_back({FirstPhi, SecondPhi});
4183 bool MatchPhiSet(SimplificationTracker &ST,
bool AllowNewPhiNodes,
4184 unsigned &PhiNotMatchedCount) {
4190 PhiNodeSet &PhiNodesToMatch =
ST.newPhiNodes();
4191 while (PhiNodesToMatch.size()) {
4195 WillNotMatch.
clear();
4199 bool IsMatched =
false;
4200 for (
auto &
P :
PHI->getParent()->phis()) {
4202 if (PhiNodesToMatch.count(&
P))
4204 if ((IsMatched = MatchPhiNode(
PHI, &
P, Matched, PhiNodesToMatch)))
4209 for (
auto M : Matched)
4215 for (
auto MV : Matched)
4216 ST.ReplacePhi(MV.first, MV.second);
4221 if (!AllowNewPhiNodes)
4224 PhiNotMatchedCount += WillNotMatch.
size();
4225 for (
auto *
P : WillNotMatch)
4226 PhiNodesToMatch.erase(
P);
4231 void FillPlaceholders(FoldAddrToValueMapping &Map,
4233 SimplificationTracker &ST) {
4234 while (!TraverseOrder.
empty()) {
4236 assert(
Map.contains(Current) &&
"No node to fill!!!");
4241 auto *CurrentSelect = cast<SelectInst>(Current);
4242 auto *TrueValue = CurrentSelect->getTrueValue();
4243 assert(
Map.contains(TrueValue) &&
"No True Value!");
4244 Select->setTrueValue(
ST.Get(Map[TrueValue]));
4245 auto *FalseValue = CurrentSelect->getFalseValue();
4246 assert(
Map.contains(FalseValue) &&
"No False Value!");
4247 Select->setFalseValue(
ST.Get(Map[FalseValue]));
4250 auto *
PHI = cast<PHINode>(V);
4253 Value *PV = cast<PHINode>(Current)->getIncomingValueForBlock(
B);
4254 assert(
Map.contains(PV) &&
"No predecessor Value!");
4255 PHI->addIncoming(
ST.Get(Map[PV]),
B);
4258 Map[Current] =
ST.Simplify(V);
4267 void InsertPlaceholders(FoldAddrToValueMapping &Map,
4269 SimplificationTracker &ST) {
4271 assert((isa<PHINode>(Original) || isa<SelectInst>(Original)) &&
4272 "Address must be a Phi or Select node");
4275 while (!Worklist.
empty()) {
4278 if (
Map.contains(Current))
4284 if (
SelectInst *CurrentSelect = dyn_cast<SelectInst>(Current)) {
4289 CurrentSelect->getName(),
4290 CurrentSelect->getIterator(), CurrentSelect);
4294 Worklist.
push_back(CurrentSelect->getTrueValue());
4295 Worklist.
push_back(CurrentSelect->getFalseValue());
4298 PHINode *CurrentPhi = cast<PHINode>(Current);
4303 ST.insertNewPhi(
PHI);
4309 bool addrModeCombiningAllowed() {
4312 switch (DifferentField) {
4315 case ExtAddrMode::BaseRegField:
4317 case ExtAddrMode::BaseGVField:
4319 case ExtAddrMode::BaseOffsField:
4321 case ExtAddrMode::ScaledRegField:
4331bool AddressingModeMatcher::matchScaledValue(
Value *ScaleReg, int64_t Scale,
4336 return matchAddr(ScaleReg,
Depth);
4351 TestAddrMode.
Scale += Scale;
4366 Value *AddLHS =
nullptr;
4367 if (isa<Instruction>(ScaleReg) &&
4370 TestAddrMode.InBounds =
false;
4377 AddrModeInsts.
push_back(cast<Instruction>(ScaleReg));
4387 auto GetConstantStep =
4388 [
this](
const Value *
V) -> std::optional<std::pair<Instruction *, APInt>> {
4389 auto *PN = dyn_cast<PHINode>(V);
4391 return std::nullopt;
4394 return std::nullopt;
4401 if (
auto *OIVInc = dyn_cast<OverflowingBinaryOperator>(IVInc->first))
4402 if (OIVInc->hasNoSignedWrap() || OIVInc->hasNoUnsignedWrap())
4403 return std::nullopt;
4404 if (
auto *ConstantStep = dyn_cast<ConstantInt>(IVInc->second))
4405 return std::make_pair(IVInc->first, ConstantStep->getValue());
4406 return std::nullopt;
4421 if (
auto IVStep = GetConstantStep(ScaleReg)) {
4428 APInt Step = IVStep->second;
4430 if (
Offset.isSignedIntN(64)) {
4431 TestAddrMode.InBounds =
false;
4433 TestAddrMode.BaseOffs -=
Offset.getLimitedValue();
4438 getDTFn().
dominates(IVInc, MemoryInst)) {
4439 AddrModeInsts.
push_back(cast<Instruction>(IVInc));
4458 switch (
I->getOpcode()) {
4459 case Instruction::BitCast:
4460 case Instruction::AddrSpaceCast:
4462 if (
I->getType() ==
I->getOperand(0)->getType())
4464 return I->getType()->isIntOrPtrTy();
4465 case Instruction::PtrToInt:
4468 case Instruction::IntToPtr:
4471 case Instruction::Add:
4473 case Instruction::Mul:
4474 case Instruction::Shl:
4476 return isa<ConstantInt>(
I->getOperand(1));
4477 case Instruction::GetElementPtr:
4490 Instruction *PromotedInst = dyn_cast<Instruction>(Val);
4505class TypePromotionHelper {
4508 static void addPromotedInst(InstrToOrigTy &PromotedInsts,
4510 ExtType ExtTy = IsSExt ? SignExtension : ZeroExtension;
4511 InstrToOrigTy::iterator It = PromotedInsts.find(ExtOpnd);
4512 if (It != PromotedInsts.end()) {
4515 if (It->second.getInt() == ExtTy)
4521 ExtTy = BothExtension;
4523 PromotedInsts[ExtOpnd] = TypeIsSExt(ExtOpnd->
getType(), ExtTy);
4530 static const Type *getOrigType(
const InstrToOrigTy &PromotedInsts,
4532 ExtType ExtTy = IsSExt ? SignExtension : ZeroExtension;
4533 InstrToOrigTy::const_iterator It = PromotedInsts.find(Opnd);
4534 if (It != PromotedInsts.end() && It->second.getInt() == ExtTy)
4535 return It->second.getPointer();
4550 static bool canGetThrough(
const Instruction *Inst,
Type *ConsideredExtType,
4551 const InstrToOrigTy &PromotedInsts,
bool IsSExt);
4555 static bool shouldExtOperand(
const Instruction *Inst,
int OpIdx) {
4556 return !(isa<SelectInst>(Inst) && OpIdx == 0);
4568 static Value *promoteOperandForTruncAndAnyExt(
4570 InstrToOrigTy &PromotedInsts,
unsigned &CreatedInstsCost,
4584 TypePromotionTransaction &TPT,
4585 InstrToOrigTy &PromotedInsts,
4586 unsigned &CreatedInstsCost,
4592 static Value *signExtendOperandForOther(
4594 InstrToOrigTy &PromotedInsts,
unsigned &CreatedInstsCost,
4597 return promoteOperandForOther(Ext, TPT, PromotedInsts, CreatedInstsCost,
4598 Exts, Truncs, TLI,
true);
4602 static Value *zeroExtendOperandForOther(
4604 InstrToOrigTy &PromotedInsts,
unsigned &CreatedInstsCost,
4607 return promoteOperandForOther(Ext, TPT, PromotedInsts, CreatedInstsCost,
4608 Exts, Truncs, TLI,
false);
4614 InstrToOrigTy &PromotedInsts,
4615 unsigned &CreatedInstsCost,
4631 const InstrToOrigTy &PromotedInsts);
4636bool TypePromotionHelper::canGetThrough(
const Instruction *Inst,
4637 Type *ConsideredExtType,
4638 const InstrToOrigTy &PromotedInsts,
4647 if (isa<ZExtInst>(Inst))
4651 if (IsSExt && isa<SExtInst>(Inst))
4656 if (
const auto *BinOp = dyn_cast<BinaryOperator>(Inst))
4657 if (isa<OverflowingBinaryOperator>(BinOp) &&
4658 ((!IsSExt && BinOp->hasNoUnsignedWrap()) ||
4659 (IsSExt && BinOp->hasNoSignedWrap())))
4663 if ((Inst->
getOpcode() == Instruction::And ||
4668 if (Inst->
getOpcode() == Instruction::Xor) {
4670 if (
const auto *Cst = dyn_cast<ConstantInt>(Inst->
getOperand(1)))
4671 if (!Cst->getValue().isAllOnes())
4680 if (Inst->
getOpcode() == Instruction::LShr && !IsSExt)
4689 const auto *ExtInst = cast<const Instruction>(*Inst->
user_begin());
4690 if (ExtInst->hasOneUse()) {
4691 const auto *AndInst = dyn_cast<const Instruction>(*ExtInst->user_begin());
4692 if (AndInst && AndInst->getOpcode() == Instruction::And) {
4693 const auto *Cst = dyn_cast<ConstantInt>(AndInst->getOperand(1));
4703 if (!isa<TruncInst>(Inst))
4717 Instruction *Opnd = dyn_cast<Instruction>(OpndVal);
4725 const Type *OpndType = getOrigType(PromotedInsts, Opnd, IsSExt);
4728 else if ((IsSExt && isa<SExtInst>(Opnd)) || (!IsSExt && isa<ZExtInst>(Opnd)))
4738TypePromotionHelper::Action TypePromotionHelper::getAction(
4739 Instruction *Ext,
const SetOfInstrs &InsertedInsts,
4741 assert((isa<SExtInst>(Ext) || isa<ZExtInst>(Ext)) &&
4742 "Unexpected instruction type");
4743 Instruction *ExtOpnd = dyn_cast<Instruction>(
Ext->getOperand(0));
4745 bool IsSExt = isa<SExtInst>(Ext);
4749 if (!ExtOpnd || !canGetThrough(ExtOpnd, ExtTy, PromotedInsts, IsSExt))
4755 if (isa<TruncInst>(ExtOpnd) && InsertedInsts.count(ExtOpnd))
4760 if (isa<SExtInst>(ExtOpnd) || isa<TruncInst>(ExtOpnd) ||
4761 isa<ZExtInst>(ExtOpnd))
4762 return promoteOperandForTruncAndAnyExt;
4768 return IsSExt ? signExtendOperandForOther : zeroExtendOperandForOther;
4771Value *TypePromotionHelper::promoteOperandForTruncAndAnyExt(
4773 InstrToOrigTy &PromotedInsts,
unsigned &CreatedInstsCost,
4779 Value *ExtVal = SExt;
4780 bool HasMergedNonFreeExt =
false;
4781 if (isa<ZExtInst>(SExtOpnd)) {
4784 HasMergedNonFreeExt = !TLI.
isExtFree(SExtOpnd);
4788 TPT.eraseInstruction(SExt);
4793 TPT.setOperand(SExt, 0, SExtOpnd->
getOperand(0));
4795 CreatedInstsCost = 0;
4799 TPT.eraseInstruction(SExtOpnd);
4802 Instruction *ExtInst = dyn_cast<Instruction>(ExtVal);
4807 CreatedInstsCost = !TLI.
isExtFree(ExtInst) && !HasMergedNonFreeExt;
4815 TPT.eraseInstruction(ExtInst, NextVal);
4819Value *TypePromotionHelper::promoteOperandForOther(
4821 InstrToOrigTy &PromotedInsts,
unsigned &CreatedInstsCost,
4828 CreatedInstsCost = 0;
4834 Value *Trunc = TPT.createTrunc(Ext, ExtOpnd->
getType());
4835 if (
Instruction *ITrunc = dyn_cast<Instruction>(Trunc)) {
4837 ITrunc->moveAfter(ExtOpnd);
4842 TPT.replaceAllUsesWith(ExtOpnd, Trunc);
4845 TPT.setOperand(Ext, 0, ExtOpnd);
4855 addPromotedInst(PromotedInsts, ExtOpnd, IsSExt);
4857 TPT.mutateType(ExtOpnd,
Ext->getType());
4859 TPT.replaceAllUsesWith(Ext, ExtOpnd);
4862 for (
int OpIdx = 0, EndOpIdx = ExtOpnd->
getNumOperands(); OpIdx != EndOpIdx;
4866 !shouldExtOperand(ExtOpnd, OpIdx)) {
4872 if (
const ConstantInt *Cst = dyn_cast<ConstantInt>(Opnd)) {
4874 unsigned BitWidth =
Ext->getType()->getIntegerBitWidth();
4877 TPT.setOperand(ExtOpnd, OpIdx, ConstantInt::get(
Ext->getType(), CstVal));
4881 if (isa<UndefValue>(Opnd)) {
4888 Value *ValForExtOpnd = IsSExt
4889 ? TPT.createSExt(ExtOpnd, Opnd,
Ext->getType())
4890 : TPT.createZExt(ExtOpnd, Opnd,
Ext->getType());
4891 TPT.setOperand(ExtOpnd, OpIdx, ValForExtOpnd);
4892 Instruction *InstForExtOpnd = dyn_cast<Instruction>(ValForExtOpnd);
4893 if (!InstForExtOpnd)
4899 CreatedInstsCost += !TLI.
isExtFree(InstForExtOpnd);
4902 TPT.eraseInstruction(Ext);
4914bool AddressingModeMatcher::isPromotionProfitable(
4915 unsigned NewCost,
unsigned OldCost,
Value *PromotedOperand)
const {
4916 LLVM_DEBUG(
dbgs() <<
"OldCost: " << OldCost <<
"\tNewCost: " << NewCost
4921 if (NewCost > OldCost)
4923 if (NewCost < OldCost)
4942bool AddressingModeMatcher::matchOperationAddr(
User *AddrInst,
unsigned Opcode,
4954 case Instruction::PtrToInt:
4957 case Instruction::IntToPtr: {
4965 case Instruction::BitCast:
4975 case Instruction::AddrSpaceCast: {
4983 case Instruction::Add: {
4987 unsigned OldSize = AddrModeInsts.
size();
4992 TypePromotionTransaction::ConstRestorationPt LastKnownGood =
4993 TPT.getRestorationPoint();
4997 int First = 0, Second = 1;
4999 && !isa<ConstantInt>(AddrInst->
getOperand(Second)))
5008 AddrModeInsts.
resize(OldSize);
5009 TPT.rollback(LastKnownGood);
5019 AddrModeInsts.
resize(OldSize);
5020 TPT.rollback(LastKnownGood);
5026 case Instruction::Mul:
5027 case Instruction::Shl: {
5031 if (!RHS ||
RHS->getBitWidth() > 64)
5033 int64_t Scale = Opcode == Instruction::Shl
5034 ? 1LL <<
RHS->getLimitedValue(
RHS->getBitWidth() - 1)
5035 :
RHS->getSExtValue();
5039 case Instruction::GetElementPtr: {
5042 int VariableOperand = -1;
5043 unsigned VariableScale = 0;
5045 int64_t ConstantOffset = 0;
5047 for (
unsigned i = 1, e = AddrInst->
getNumOperands(); i != e; ++i, ++GTI) {
5051 cast<ConstantInt>(AddrInst->
getOperand(i))->getZExtValue();
5061 dyn_cast<ConstantInt>(AddrInst->
getOperand(i))) {
5069 if (VariableOperand != -1)
5073 VariableOperand = i;
5081 if (VariableOperand == -1) {
5082 AddrMode.BaseOffs += ConstantOffset;
5084 if (!cast<GEPOperator>(AddrInst)->isInBounds())
5088 AddrMode.BaseOffs -= ConstantOffset;
5092 ConstantOffset > 0) {
5098 auto *BaseI = dyn_cast<Instruction>(
Base);
5099 auto *
GEP = cast<GetElementPtrInst>(AddrInst);
5100 if (isa<Argument>(
Base) || isa<GlobalValue>(
Base) ||
5101 (BaseI && !isa<CastInst>(BaseI) &&
5102 !isa<GetElementPtrInst>(BaseI))) {
5106 : &
GEP->getFunction()->getEntryBlock();
5108 LargeOffsetGEP = std::make_pair(
GEP, ConstantOffset);
5117 unsigned OldSize = AddrModeInsts.
size();
5120 AddrMode.BaseOffs += ConstantOffset;
5121 if (!cast<GEPOperator>(AddrInst)->isInBounds())
5129 AddrModeInsts.
resize(OldSize);
5137 if (!matchScaledValue(AddrInst->
getOperand(VariableOperand), VariableScale,
5142 AddrModeInsts.
resize(OldSize);
5147 AddrMode.BaseOffs += ConstantOffset;
5148 if (!matchScaledValue(AddrInst->
getOperand(VariableOperand),
5149 VariableScale,
Depth)) {
5152 AddrModeInsts.
resize(OldSize);
5159 case Instruction::SExt:
5160 case Instruction::ZExt: {
5167 TypePromotionHelper::Action TPH =
5168 TypePromotionHelper::getAction(Ext, InsertedInsts, TLI, PromotedInsts);
5172 TypePromotionTransaction::ConstRestorationPt LastKnownGood =
5173 TPT.getRestorationPoint();
5174 unsigned CreatedInstsCost = 0;
5176 Value *PromotedOperand =
5177 TPH(Ext, TPT, PromotedInsts, CreatedInstsCost,
nullptr,
nullptr, TLI);
5192 assert(PromotedOperand &&
5193 "TypePromotionHelper should have filtered out those cases");
5196 unsigned OldSize = AddrModeInsts.
size();
5198 if (!matchAddr(PromotedOperand,
Depth) ||
5203 !isPromotionProfitable(CreatedInstsCost,
5204 ExtCost + (AddrModeInsts.
size() - OldSize),
5207 AddrModeInsts.
resize(OldSize);
5208 LLVM_DEBUG(
dbgs() <<
"Sign extension does not pay off: rollback\n");
5209 TPT.rollback(LastKnownGood);
5214 case Instruction::Call:
5216 if (
II->getIntrinsicID() == Intrinsic::threadlocal_address) {
5232bool AddressingModeMatcher::matchAddr(
Value *
Addr,
unsigned Depth) {
5235 TypePromotionTransaction::ConstRestorationPt LastKnownGood =
5236 TPT.getRestorationPoint();
5255 unsigned OldSize = AddrModeInsts.
size();
5258 bool MovedAway =
false;
5259 if (matchOperationAddr(
I,
I->getOpcode(),
Depth, &MovedAway)) {
5267 if (
I->hasOneUse() ||
5268 isProfitableToFoldIntoAddressingMode(
I, BackupAddrMode,
AddrMode)) {
5275 AddrModeInsts.
resize(OldSize);
5276 TPT.rollback(LastKnownGood);
5279 if (matchOperationAddr(CE,
CE->getOpcode(),
Depth))
5281 TPT.rollback(LastKnownGood);
5282 }
else if (isa<ConstantPointerNull>(
Addr)) {
5308 TPT.rollback(LastKnownGood);
5327 if (OpInfo.CallOperandVal == OpVal &&
5329 !OpInfo.isIndirect))
5345 if (!ConsideredInsts.
insert(
I).second)
5353 for (
Use &U :
I->uses()) {
5359 Instruction *UserI = cast<Instruction>(U.getUser());
5360 if (
LoadInst *LI = dyn_cast<LoadInst>(UserI)) {
5361 MemoryUses.push_back({&U, LI->getType()});
5365 if (
StoreInst *SI = dyn_cast<StoreInst>(UserI)) {
5368 MemoryUses.push_back({&U, SI->getValueOperand()->
getType()});
5375 MemoryUses.push_back({&U, RMW->getValOperand()->
getType()});
5382 MemoryUses.push_back({&U, CmpX->getCompareOperand()->
getType()});
5386 if (
CallInst *CI = dyn_cast<CallInst>(UserI)) {
5387 if (CI->hasFnAttr(Attribute::Cold)) {
5396 InlineAsm *IA = dyn_cast<InlineAsm>(CI->getCalledOperand());
5407 PSI, BFI, SeenInsts))
5418 unsigned SeenInsts = 0;
5421 PSI, BFI, SeenInsts);
5429bool AddressingModeMatcher::valueAlreadyLiveAtInst(
Value *Val,
5431 Value *KnownLive2) {
5433 if (Val ==
nullptr || Val == KnownLive1 || Val == KnownLive2)
5437 if (!isa<Instruction>(Val) && !isa<Argument>(Val))
5443 if (
AllocaInst *AI = dyn_cast<AllocaInst>(Val))
5474bool AddressingModeMatcher::isProfitableToFoldIntoAddressingMode(
5476 if (IgnoreProfitability)
5494 if (valueAlreadyLiveAtInst(ScaledReg, AMBefore.
BaseReg, AMBefore.
ScaledReg))
5495 ScaledReg =
nullptr;
5499 if (!BaseReg && !ScaledReg)
5520 for (
const std::pair<Use *, Type *> &Pair : MemoryUses) {
5522 Instruction *UserI = cast<Instruction>(Pair.first->getUser());
5523 Type *AddressAccessTy = Pair.second;
5524 unsigned AS =
Address->getType()->getPointerAddressSpace();
5530 std::pair<AssertingVH<GetElementPtrInst>, int64_t> LargeOffsetGEP(
nullptr,
5532 TypePromotionTransaction::ConstRestorationPt LastKnownGood =
5533 TPT.getRestorationPoint();
5534 AddressingModeMatcher Matcher(MatchedAddrModeInsts, TLI,
TRI, LI, getDTFn,
5535 AddressAccessTy, AS, UserI, Result,
5536 InsertedInsts, PromotedInsts, TPT,
5537 LargeOffsetGEP, OptSize, PSI, BFI);
5538 Matcher.IgnoreProfitability =
true;
5539 bool Success = Matcher.matchAddr(Address, 0);
5546 TPT.rollback(LastKnownGood);
5552 MatchedAddrModeInsts.
clear();
5562 return I->getParent() != BB;
5586 Type *AccessTy,
unsigned AddrSpace) {
5598 bool PhiOrSelectSeen =
false;
5601 AddressingModeCombiner AddrModes(SQ,
Addr);
5602 TypePromotionTransaction TPT(RemovedInsts);
5603 TypePromotionTransaction::ConstRestorationPt LastKnownGood =
5604 TPT.getRestorationPoint();
5605 while (!worklist.
empty()) {
5617 if (!Visited.
insert(V).second)
5621 if (
PHINode *
P = dyn_cast<PHINode>(V)) {
5623 PhiOrSelectSeen =
true;
5627 if (
SelectInst *SI = dyn_cast<SelectInst>(V)) {
5630 PhiOrSelectSeen =
true;
5637 AddrModeInsts.
clear();
5638 std::pair<AssertingVH<GetElementPtrInst>, int64_t> LargeOffsetGEP(
nullptr,
5643 auto getDTFn = [MemoryInst,
this]() ->
const DominatorTree & {
5645 return this->getDT(*
F);
5647 ExtAddrMode NewAddrMode = AddressingModeMatcher::Match(
5648 V, AccessTy, AddrSpace, MemoryInst, AddrModeInsts, *TLI, *LI, getDTFn,
5649 *
TRI, InsertedInsts, PromotedInsts, TPT, LargeOffsetGEP, OptSize, PSI,
5657 LargeOffsetGEPMap[
GEP->getPointerOperand()].push_back(LargeOffsetGEP);
5658 LargeOffsetGEPID.
insert(std::make_pair(
GEP, LargeOffsetGEPID.
size()));
5661 NewAddrMode.OriginalValue =
V;
5662 if (!AddrModes.addNewAddrMode(NewAddrMode))
5669 if (!AddrModes.combineAddrModes()) {
5670 TPT.rollback(LastKnownGood);
5682 if (!PhiOrSelectSeen &&
none_of(AddrModeInsts, [&](
Value *V) {
5704 Type *IntPtrTy =
DL->getIntPtrType(
Addr->getType());
5707 <<
" for " << *MemoryInst <<
"\n");
5710 Addr->getType()->getPointerAddressSpace() &&
5711 !
DL->isNonIntegralPointerType(
Addr->getType())) {
5717 SunkAddr = Builder.CreatePtrToInt(SunkAddr, IntPtrTy,
"sunkaddr");
5719 Builder.CreateIntToPtr(SunkAddr,
Addr->getType(),
"sunkaddr");
5721 SunkAddr = Builder.CreatePointerCast(SunkAddr,
Addr->getType());
5728 <<
" for " << *MemoryInst <<
"\n");
5729 Value *ResultPtr =
nullptr, *ResultIndex =
nullptr;
5740 if (ResultPtr ||
AddrMode.Scale != 1)
5762 if (BaseGV !=
nullptr) {
5767 ResultPtr = Builder.CreateThreadLocalAddress(BaseGV);
5776 if (!
DL->isNonIntegralPointerType(
Addr->getType())) {
5777 if (!ResultPtr &&
AddrMode.BaseReg) {
5778 ResultPtr = Builder.CreateIntToPtr(
AddrMode.BaseReg,
Addr->getType(),
5781 }
else if (!ResultPtr &&
AddrMode.Scale == 1) {
5782 ResultPtr = Builder.CreateIntToPtr(
AddrMode.ScaledReg,
Addr->getType(),
5791 }
else if (!ResultPtr) {
5795 Builder.getPtrTy(
Addr->getType()->getPointerAddressSpace());
5804 if (
V->getType() != IntPtrTy)
5805 V = Builder.CreateIntCast(V, IntPtrTy,
true,
"sunkaddr");
5813 if (
V->getType() == IntPtrTy) {
5817 cast<IntegerType>(
V->getType())->getBitWidth() &&
5818 "We can't transform if ScaledReg is too narrow");
5819 V = Builder.CreateTrunc(V, IntPtrTy,
"sunkaddr");
5823 V = Builder.CreateMul(V, ConstantInt::get(IntPtrTy,
AddrMode.Scale),
5826 ResultIndex = Builder.CreateAdd(ResultIndex, V,
"sunkaddr");
5837 if (ResultPtr->
getType() != I8PtrTy)
5838 ResultPtr = Builder.CreatePointerCast(ResultPtr, I8PtrTy);
5839 ResultPtr = Builder.CreatePtrAdd(ResultPtr, ResultIndex,
"sunkaddr",
5847 SunkAddr = ResultPtr;
5849 if (ResultPtr->
getType() != I8PtrTy)
5850 ResultPtr = Builder.CreatePointerCast(ResultPtr, I8PtrTy);
5851 SunkAddr = Builder.CreatePtrAdd(ResultPtr, ResultIndex,
"sunkaddr",
5857 Addr->getType()->getPointerAddressSpace() &&
5858 !
DL->isNonIntegralPointerType(
Addr->getType())) {
5864 SunkAddr = Builder.CreatePtrToInt(SunkAddr, IntPtrTy,
"sunkaddr");
5866 Builder.CreateIntToPtr(SunkAddr,
Addr->getType(),
"sunkaddr");
5868 SunkAddr = Builder.CreatePointerCast(SunkAddr,
Addr->getType());
5877 PointerType *ScalePtrTy = dyn_cast_or_null<PointerType>(ScaleTy);
5878 if (
DL->isNonIntegralPointerType(
Addr->getType()) ||
5879 (BasePtrTy &&
DL->isNonIntegralPointerType(BasePtrTy)) ||
5880 (ScalePtrTy &&
DL->isNonIntegralPointerType(ScalePtrTy)) ||
5882 DL->isNonIntegralPointerType(
AddrMode.BaseGV->getType())))
5886 <<
" for " << *MemoryInst <<
"\n");
5887 Type *IntPtrTy =
DL->getIntPtrType(
Addr->getType());
5897 if (
V->getType()->isPointerTy())
5898 V = Builder.CreatePtrToInt(V, IntPtrTy,
"sunkaddr");
5899 if (
V->getType() != IntPtrTy)
5900 V = Builder.CreateIntCast(V, IntPtrTy,
true,
"sunkaddr");
5907 if (
V->getType() == IntPtrTy) {
5909 }
else if (
V->getType()->isPointerTy()) {
5910 V = Builder.CreatePtrToInt(V, IntPtrTy,
"sunkaddr");
5911 }
else if (cast<IntegerType>(IntPtrTy)->
getBitWidth() <
5912 cast<IntegerType>(
V->getType())->getBitWidth()) {
5913 V = Builder.CreateTrunc(V, IntPtrTy,
"sunkaddr");
5920 Instruction *
I = dyn_cast_or_null<Instruction>(Result);
5922 I->eraseFromParent();
5926 V = Builder.CreateMul(V, ConstantInt::get(IntPtrTy,
AddrMode.Scale),
5929 Result = Builder.CreateAdd(Result, V,
"sunkaddr");
5936 if (BaseGV !=
nullptr) {
5939 BaseGVPtr = Builder.CreateThreadLocalAddress(BaseGV);
5943 Value *
V = Builder.CreatePtrToInt(BaseGVPtr, IntPtrTy,
"sunkaddr");
5945 Result = Builder.CreateAdd(Result, V,
"sunkaddr");
5954 Result = Builder.CreateAdd(Result, V,
"sunkaddr");
5962 SunkAddr = Builder.CreateIntToPtr(Result,
Addr->getType(),
"sunkaddr");
5973 resetIteratorIfInvalidatedWhileCalling(CurInstIterator->getParent(), [&]() {
5974 RecursivelyDeleteTriviallyDeadInstructions(
5975 Repl, TLInfo, nullptr,
5976 [&](Value *V) { removeAllAssertingVHReferences(V); });
6000bool CodeGenPrepare::optimizeGatherScatterInst(
Instruction *MemoryInst,
6004 if (
const auto *
GEP = dyn_cast<GetElementPtrInst>(
Ptr)) {
6006 if (!
GEP->hasIndices())
6016 bool RewriteGEP =
false;
6018 if (Ops[0]->
getType()->isVectorTy()) {
6025 unsigned FinalIndex = Ops.size() - 1;
6030 for (
unsigned i = 1; i < FinalIndex; ++i) {
6031 auto *
C = dyn_cast<Constant>(Ops[i]);
6034 if (isa<VectorType>(
C->getType()))
6035 C =
C->getSplatValue();
6036 auto *CI = dyn_cast_or_null<ConstantInt>(
C);
6037 if (!CI || !CI->
isZero())
6044 if (Ops[FinalIndex]->
getType()->isVectorTy()) {
6046 auto *
C = dyn_cast<ConstantInt>(V);
6048 if (!
C || !
C->isZero()) {
6049 Ops[FinalIndex] =
V;
6057 if (!RewriteGEP && Ops.size() == 2)
6060 auto NumElts = cast<VectorType>(
Ptr->getType())->getElementCount();
6064 Type *SourceTy =
GEP->getSourceElementType();
6065 Type *ScalarIndexTy =
DL->getIndexType(Ops[0]->
getType()->getScalarType());
6069 if (!Ops[FinalIndex]->
getType()->isVectorTy()) {
6070 NewAddr = Builder.CreateGEP(SourceTy, Ops[0],
ArrayRef(Ops).drop_front());
6071 auto *IndexTy = VectorType::get(ScalarIndexTy, NumElts);
6073 SourceTy,
ArrayRef(Ops).drop_front());
6081 if (Ops.size() != 2) {
6087 SourceTy,
ArrayRef(Ops).drop_front());
6091 NewAddr = Builder.CreateGEP(SourceTy,
Base,
Index);
6093 }
else if (!isa<Constant>(
Ptr)) {
6100 auto NumElts = cast<VectorType>(
Ptr->getType())->getElementCount();
6105 Type *ScalarIndexTy =
DL->getIndexType(
V->getType()->getScalarType());
6106 auto *IndexTy = VectorType::get(ScalarIndexTy, NumElts);
6109 Intrinsic::masked_gather) {
6113 Intrinsic::masked_scatter);
6126 if (
Ptr->use_empty())
6128 Ptr, TLInfo,
nullptr,
6129 [&](
Value *V) { removeAllAssertingVHReferences(V); });
6136bool CodeGenPrepare::optimizeInlineAsmInst(
CallInst *CS) {
6137 bool MadeChange =
false;
6140 TM->getSubtargetImpl(*CS->
getFunction())->getRegisterInfo();
6150 OpInfo.isIndirect) {
6152 MadeChange |= optimizeMemoryInst(CS, OpVal, OpVal->
getType(), ~0u);
6165 bool IsSExt = isa<SExtInst>(FirstUser);
6169 if ((IsSExt && !isa<SExtInst>(UI)) || (!IsSExt && !isa<ZExtInst>(UI)))
6215bool CodeGenPrepare::tryToPromoteExts(
6218 unsigned CreatedInstsCost) {
6219 bool Promoted =
false;
6222 for (
auto *
I : Exts) {
6224 if (isa<LoadInst>(
I->getOperand(0))) {
6237 TypePromotionHelper::Action TPH =
6238 TypePromotionHelper::getAction(
I, InsertedInsts, *TLI, PromotedInsts);
6247 TypePromotionTransaction::ConstRestorationPt LastKnownGood =
6248 TPT.getRestorationPoint();
6250 unsigned NewCreatedInstsCost = 0;
6253 Value *PromotedVal = TPH(
I, TPT, PromotedInsts, NewCreatedInstsCost,
6254 &NewExts,
nullptr, *TLI);
6256 "TypePromotionHelper should have filtered out those cases");
6266 long long TotalCreatedInstsCost = CreatedInstsCost + NewCreatedInstsCost;
6269 TotalCreatedInstsCost =
6270 std::max((
long long)0, (TotalCreatedInstsCost - ExtCost));
6272 (TotalCreatedInstsCost > 1 ||
6274 (ExtCost == 0 && NewExts.
size() > 1))) {
6278 TPT.rollback(LastKnownGood);
6284 (void)tryToPromoteExts(TPT, NewExts, NewlyMovedExts, TotalCreatedInstsCost);
6285 bool NewPromoted =
false;
6286 for (
auto *ExtInst : NewlyMovedExts) {
6287 Instruction *MovedExt = cast<Instruction>(ExtInst);
6291 if (isa<LoadInst>(ExtOperand) &&
6296 ProfitablyMovedExts.
push_back(MovedExt);
6303 TPT.rollback(LastKnownGood);
6314bool CodeGenPrepare::mergeSExts(
Function &
F) {
6315 bool Changed =
false;
6316 for (
auto &Entry : ValToSExtendedUses) {
6317 SExts &Insts =
Entry.second;
6320 if (RemovedInsts.count(Inst) || !isa<SExtInst>(Inst) ||
6323 bool inserted =
false;
6324 for (
auto &Pt : CurPts) {
6327 RemovedInsts.insert(Pt);
6328 Pt->removeFromParent();
6339 RemovedInsts.insert(Inst);
6346 CurPts.push_back(Inst);
6388bool CodeGenPrepare::splitLargeGEPOffsets() {
6389 bool Changed =
false;
6390 for (
auto &Entry : LargeOffsetGEPMap) {
6393 &LargeOffsetGEPs =
Entry.second;
6394 auto compareGEPOffset =
6395 [&](
const std::pair<GetElementPtrInst *, int64_t> &
LHS,
6396 const std::pair<GetElementPtrInst *, int64_t> &
RHS) {
6397 if (
LHS.first ==
RHS.first)
6399 if (
LHS.second !=
RHS.second)
6400 return LHS.second <
RHS.second;
6401 return LargeOffsetGEPID[
LHS.first] < LargeOffsetGEPID[
RHS.first];
6404 llvm::sort(LargeOffsetGEPs, compareGEPOffset);
6407 if (LargeOffsetGEPs.
front().second == LargeOffsetGEPs.
back().second)
6410 int64_t BaseOffset = LargeOffsetGEPs.
begin()->second;
6411 Value *NewBaseGEP =
nullptr;
6413 auto createNewBase = [&](int64_t BaseOffset,
Value *OldBase,
6416 Type *PtrIdxTy =
DL->getIndexType(
GEP->getType());
6418 PointerType::get(Ctx,
GEP->getType()->getPointerAddressSpace());
6422 if (
auto *BaseI = dyn_cast<Instruction>(OldBase)) {
6426 if (isa<PHINode>(BaseI))
6428 else if (
InvokeInst *Invoke = dyn_cast<InvokeInst>(BaseI)) {
6430 SplitEdge(NewBaseInsertBB, Invoke->getNormalDest(), DT.get(), LI);
6433 NewBaseInsertPt = std::next(BaseI->getIterator());
6440 IRBuilder<> NewBaseBuilder(NewBaseInsertBB, NewBaseInsertPt);
6442 Value *BaseIndex = ConstantInt::get(PtrIdxTy, BaseOffset);
6443 NewBaseGEP = OldBase;
6444 if (NewBaseGEP->
getType() != I8PtrTy)
6445 NewBaseGEP = NewBaseBuilder.CreatePointerCast(NewBaseGEP, I8PtrTy);
6447 NewBaseBuilder.CreatePtrAdd(NewBaseGEP, BaseIndex,
"splitgep");
6448 NewGEPBases.
insert(NewBaseGEP);
6454 LargeOffsetGEPs.
front().second, LargeOffsetGEPs.
back().second)) {
6455 BaseOffset = PreferBase;
6458 createNewBase(BaseOffset, OldBase, BaseGEP);
6461 auto *LargeOffsetGEP = LargeOffsetGEPs.
begin();
6462 while (LargeOffsetGEP != LargeOffsetGEPs.
end()) {
6464 int64_t
Offset = LargeOffsetGEP->second;
6465 if (
Offset != BaseOffset) {
6472 GEP->getResultElementType(),
6473 GEP->getAddressSpace())) {
6479 NewBaseGEP =
nullptr;
6484 Type *PtrIdxTy =
DL->getIndexType(
GEP->getType());
6489 createNewBase(BaseOffset, OldBase,
GEP);
6493 Value *NewGEP = NewBaseGEP;
6494 if (
Offset != BaseOffset) {
6497 NewGEP = Builder.CreatePtrAdd(NewBaseGEP,
Index);
6501 LargeOffsetGEP = LargeOffsetGEPs.
erase(LargeOffsetGEP);
6502 GEP->eraseFromParent();
6509bool CodeGenPrepare::optimizePhiType(
6516 Type *PhiTy =
I->getType();
6517 Type *ConvertTy =
nullptr;
6519 (!
I->getType()->isIntegerTy() && !
I->getType()->isFloatingPointTy()))
6535 bool AnyAnchored =
false;
6537 while (!Worklist.
empty()) {
6540 if (
auto *Phi = dyn_cast<PHINode>(
II)) {
6542 for (
Value *V :
Phi->incoming_values()) {
6543 if (
auto *OpPhi = dyn_cast<PHINode>(V)) {
6544 if (!PhiNodes.
count(OpPhi)) {
6545 if (!Visited.
insert(OpPhi).second)
6550 }
else if (
auto *OpLoad = dyn_cast<LoadInst>(V)) {
6551 if (!OpLoad->isSimple())
6553 if (Defs.
insert(OpLoad).second)
6555 }
else if (
auto *OpEx = dyn_cast<ExtractElementInst>(V)) {
6556 if (Defs.
insert(OpEx).second)
6558 }
else if (
auto *OpBC = dyn_cast<BitCastInst>(V)) {
6560 ConvertTy = OpBC->getOperand(0)->getType();
6561 if (OpBC->getOperand(0)->getType() != ConvertTy)
6563 if (Defs.
insert(OpBC).second) {
6565 AnyAnchored |= !isa<LoadInst>(OpBC->getOperand(0)) &&
6566 !isa<ExtractElementInst>(OpBC->getOperand(0));
6568 }
else if (
auto *OpC = dyn_cast<ConstantData>(V))
6576 for (
User *V :
II->users()) {
6577 if (
auto *OpPhi = dyn_cast<PHINode>(V)) {
6578 if (!PhiNodes.
count(OpPhi)) {
6579 if (Visited.
count(OpPhi))
6585 }
else if (
auto *OpStore = dyn_cast<StoreInst>(V)) {
6586 if (!OpStore->isSimple() || OpStore->getOperand(0) !=
II)
6588 Uses.insert(OpStore);
6589 }
else if (
auto *OpBC = dyn_cast<BitCastInst>(V)) {
6591 ConvertTy = OpBC->getType();
6592 if (OpBC->getType() != ConvertTy)
6596 any_of(OpBC->users(), [](
User *U) { return !isa<StoreInst>(U); });
6603 if (!ConvertTy || !AnyAnchored ||
6607 LLVM_DEBUG(
dbgs() <<
"Converting " << *
I <<
"\n and connected nodes to "
6608 << *ConvertTy <<
"\n");
6616 if (isa<BitCastInst>(
D)) {
6617 ValMap[
D] =
D->getOperand(0);
6621 ValMap[
D] =
new BitCastInst(
D, ConvertTy,
D->getName() +
".bc", insertPt);
6626 Phi->getName() +
".tc",
Phi->getIterator());
6628 for (
PHINode *Phi : PhiNodes) {
6629 PHINode *NewPhi = cast<PHINode>(ValMap[Phi]);
6630 for (
int i = 0, e =
Phi->getNumIncomingValues(); i < e; i++)
6632 Phi->getIncomingBlock(i));
6637 if (isa<BitCastInst>(U)) {
6641 U->setOperand(0,
new BitCastInst(ValMap[
U->getOperand(0)], PhiTy,
"bc",
6648 DeletedInstrs.
insert(Phi);
6652bool CodeGenPrepare::optimizePhiTypes(
Function &
F) {
6656 bool Changed =
false;
6662 for (
auto &Phi : BB.
phis())
6663 Changed |= optimizePhiType(&Phi, Visited, DeletedInstrs);
6666 for (
auto *
I : DeletedInstrs) {
6668 I->eraseFromParent();
6676bool CodeGenPrepare::canFormExtLd(
6679 for (
auto *MovedExtInst : MovedExts) {
6680 if (isa<LoadInst>(MovedExtInst->getOperand(0))) {
6681 LI = cast<LoadInst>(MovedExtInst->getOperand(0));
6682 Inst = MovedExtInst;
6734bool CodeGenPrepare::optimizeExt(
Instruction *&Inst) {
6735 bool AllowPromotionWithoutCommonHeader =
false;
6740 *Inst, AllowPromotionWithoutCommonHeader);
6741 TypePromotionTransaction TPT(RemovedInsts);
6742 TypePromotionTransaction::ConstRestorationPt LastKnownGood =
6743 TPT.getRestorationPoint();
6748 bool HasPromoted = tryToPromoteExts(TPT, Exts, SpeculativelyMovedExts);
6756 if (canFormExtLd(SpeculativelyMovedExts, LI, ExtFedByLoad, HasPromoted)) {
6757 assert(LI && ExtFedByLoad &&
"Expect a valid load and extension");
6762 Inst = ExtFedByLoad;
6767 if (ATPConsiderable &&
6768 performAddressTypePromotion(Inst, AllowPromotionWithoutCommonHeader,
6769 HasPromoted, TPT, SpeculativelyMovedExts))
6772 TPT.rollback(LastKnownGood);
6781bool CodeGenPrepare::performAddressTypePromotion(
6782 Instruction *&Inst,
bool AllowPromotionWithoutCommonHeader,
6783 bool HasPromoted, TypePromotionTransaction &TPT,
6785 bool Promoted =
false;
6787 bool AllSeenFirst =
true;
6788 for (
auto *
I : SpeculativelyMovedExts) {
6789 Value *HeadOfChain =
I->getOperand(0);
6791 SeenChainsForSExt.
find(HeadOfChain);
6794 if (AlreadySeen != SeenChainsForSExt.
end()) {
6795 if (AlreadySeen->second !=
nullptr)
6796 UnhandledExts.
insert(AlreadySeen->second);
6797 AllSeenFirst =
false;
6801 if (!AllSeenFirst || (AllowPromotionWithoutCommonHeader &&
6802 SpeculativelyMovedExts.size() == 1)) {
6806 for (
auto *
I : SpeculativelyMovedExts) {
6807 Value *HeadOfChain =
I->getOperand(0);
6808 SeenChainsForSExt[HeadOfChain] =
nullptr;
6809 ValToSExtendedUses[HeadOfChain].push_back(
I);
6812 Inst = SpeculativelyMovedExts.pop_back_val();
6817 for (
auto *
I : SpeculativelyMovedExts) {
6818 Value *HeadOfChain =
I->getOperand(0);
6819 SeenChainsForSExt[HeadOfChain] = Inst;
6824 if (!AllSeenFirst && !UnhandledExts.
empty())
6825 for (
auto *VisitedSExt : UnhandledExts) {
6826 if (RemovedInsts.count(VisitedSExt))
6828 TypePromotionTransaction TPT(RemovedInsts);
6832 bool HasPromoted = tryToPromoteExts(TPT, Exts, Chains);
6836 for (
auto *
I : Chains) {
6837 Value *HeadOfChain =
I->getOperand(0);
6839 SeenChainsForSExt[HeadOfChain] =
nullptr;
6840 ValToSExtendedUses[HeadOfChain].push_back(
I);
6851 Value *Src =
I->getOperand(0);
6852 if (Src->hasOneUse())
6861 if (!isa<Instruction>(Src) || DefBB != cast<Instruction>(Src)->
getParent())
6864 bool DefIsLiveOut =
false;
6865 for (
User *U :
I->users()) {
6870 if (UserBB == DefBB)
6872 DefIsLiveOut =
true;
6879 for (
User *U : Src->users()) {
6882 if (UserBB == DefBB)
6886 if (isa<PHINode>(UI) || isa<LoadInst>(UI) || isa<StoreInst>(UI))
6893 bool MadeChange =
false;
6894 for (
Use &U : Src->uses()) {
6899 if (UserBB == DefBB)
6903 Instruction *&InsertedTrunc = InsertedTruncs[UserBB];
6905 if (!InsertedTrunc) {
6908 InsertedTrunc =
new TruncInst(
I, Src->getType(),
"");
6910 InsertedInsts.insert(InsertedTrunc);
6973bool CodeGenPrepare::optimizeLoadExt(
LoadInst *Load) {
6974 if (!
Load->isSimple() || !
Load->getType()->isIntOrPtrTy())
6978 if (
Load->hasOneUse() &&
6979 InsertedInsts.count(cast<Instruction>(*
Load->user_begin())))
6987 for (
auto *U :
Load->users())
6988 WorkList.
push_back(cast<Instruction>(U));
6999 while (!WorkList.
empty()) {
7003 if (!Visited.
insert(
I).second)
7007 if (
auto *Phi = dyn_cast<PHINode>(
I)) {
7008 for (
auto *U :
Phi->users())
7009 WorkList.
push_back(cast<Instruction>(U));
7013 switch (
I->getOpcode()) {
7014 case Instruction::And: {
7015 auto *AndC = dyn_cast<ConstantInt>(
I->getOperand(1));
7018 APInt AndBits = AndC->getValue();
7019 DemandBits |= AndBits;
7021 if (AndBits.
ugt(WidestAndBits))
7022 WidestAndBits = AndBits;
7023 if (AndBits == WidestAndBits &&
I->getOperand(0) == Load)
7028 case Instruction::Shl: {
7029 auto *ShlC = dyn_cast<ConstantInt>(
I->getOperand(1));
7033 DemandBits.setLowBits(
BitWidth - ShiftAmt);
7037 case Instruction::Trunc: {
7040 DemandBits.setLowBits(TruncBitWidth);
7049 uint32_t ActiveBits = DemandBits.getActiveBits();
7061 if (ActiveBits <= 1 || !DemandBits.isMask(ActiveBits) ||
7062 WidestAndBits != DemandBits)
7075 auto *NewAnd = cast<Instruction>(
7076 Builder.CreateAnd(Load, ConstantInt::get(Ctx, DemandBits)));
7079 InsertedInsts.insert(NewAnd);
7084 NewAnd->setOperand(0, Load);
7087 for (
auto *
And : AndsToMaybeRemove)
7090 if (cast<ConstantInt>(
And->getOperand(1))->getValue() == DemandBits) {
7092 if (&*CurInstIterator ==
And)
7093 CurInstIterator = std::next(
And->getIterator());
7094 And->eraseFromParent();
7105 auto *
I = dyn_cast<Instruction>(V);
7127 uint64_t Max = std::max(TrueWeight, FalseWeight);
7128 uint64_t Sum = TrueWeight + FalseWeight;
7136 CmpInst *Cmp = dyn_cast<CmpInst>(SI->getCondition());
7141 if (!Cmp || !Cmp->hasOneUse())
7162 for (
SelectInst *DefSI = SI; DefSI !=
nullptr && Selects.
count(DefSI);
7163 DefSI = dyn_cast<SelectInst>(V)) {
7164 assert(DefSI->getCondition() == SI->getCondition() &&
7165 "The condition of DefSI does not match with SI");
7166 V = (isTrue ? DefSI->getTrueValue() : DefSI->getFalseValue());
7169 assert(V &&
"Failed to get select true/false value");
7198 Value *NewTVal = Builder.CreateBinOp(Opcode, Shift->
getOperand(0), TVal);
7199 Value *NewFVal = Builder.CreateBinOp(Opcode, Shift->
getOperand(0), FVal);
7200 Value *NewSel = Builder.CreateSelect(
Cond, NewTVal, NewFVal);
7206bool CodeGenPrepare::optimizeFunnelShift(
IntrinsicInst *Fsh) {
7208 assert((Opcode == Intrinsic::fshl || Opcode == Intrinsic::fshr) &&
7209 "Expected a funnel shift");
7233 Value *NewTVal = Builder.CreateIntrinsic(Opcode, Ty, {
X,
Y, TVal});
7234 Value *NewFVal = Builder.CreateIntrinsic(Opcode, Ty, {
X,
Y, FVal});
7235 Value *NewSel = Builder.CreateSelect(
Cond, NewTVal, NewFVal);
7243bool CodeGenPrepare::optimizeSelectInst(
SelectInst *SI) {
7255 It !=
SI->getParent()->
end(); ++It) {
7257 if (
I &&
SI->getCondition() ==
I->getCondition()) {
7267 CurInstIterator = std::next(LastSI->
getIterator());
7272 fixupDbgVariableRecordsOnInst(*SI);
7274 bool VectorCond = !
SI->getCondition()->getType()->isIntegerTy(1);
7277 if (VectorCond ||
SI->getMetadata(LLVMContext::MD_unpredictable))
7281 if (
SI->getType()->isVectorTy())
7282 SelectKind = TargetLowering::ScalarCondVectorVal;
7284 SelectKind = TargetLowering::ScalarValSelect;
7327 TrueInstrs.
push_back(cast<Instruction>(V));
7329 FalseInstrs.
push_back(cast<Instruction>(V));
7337 SplitPt.setHeadBit(
true);
7340 auto *CondFr =
IB.CreateFreeze(
SI->getCondition(),
SI->getName() +
".frozen");
7347 if (TrueInstrs.
size() == 0) {
7349 CondFr, SplitPt,
false,
nullptr,
nullptr, LI));
7351 EndBlock = cast<BasicBlock>(FalseBranch->
getOperand(0));
7352 }
else if (FalseInstrs.
size() == 0) {
7354 CondFr, SplitPt,
false,
nullptr,
nullptr, LI));
7356 EndBlock = cast<BasicBlock>(TrueBranch->
getOperand(0));
7361 nullptr,
nullptr, LI);
7362 TrueBranch = cast<BranchInst>(ThenTerm);
7363 FalseBranch = cast<BranchInst>(ElseTerm);
7366 EndBlock = cast<BasicBlock>(TrueBranch->
getOperand(0));
7369 EndBlock->
setName(
"select.end");
7371 TrueBlock->
setName(
"select.true.sink");
7373 FalseBlock->
setName(FalseInstrs.
size() == 0 ?
"select.false"
7374 :
"select.false.sink");
7378 FreshBBs.
insert(TrueBlock);
7380 FreshBBs.
insert(FalseBlock);
7381 FreshBBs.
insert(EndBlock);
7384 BFI->setBlockFreq(EndBlock,
BFI->getBlockFreq(StartBlock));
7386 static const unsigned MD[] = {
7387 LLVMContext::MD_prof, LLVMContext::MD_unpredictable,
7388 LLVMContext::MD_make_implicit, LLVMContext::MD_dbg};
7394 I->moveBefore(TrueBranch);
7396 I->moveBefore(FalseBranch);
7402 if (TrueBlock ==
nullptr)
7403 TrueBlock = StartBlock;
7404 else if (FalseBlock ==
nullptr)
7405 FalseBlock = StartBlock;
7408 INS.
insert(ASI.begin(), ASI.end());
7422 SI->eraseFromParent();
7424 ++NumSelectsExpanded;
7428 CurInstIterator = StartBlock->
end();
7444 auto *SVIVecType = cast<FixedVectorType>(SVI->
getType());
7447 "Expected a type of the same size!");
7453 Builder.SetInsertPoint(SVI);
7454 Value *BC1 = Builder.CreateBitCast(
7455 cast<Instruction>(SVI->
getOperand(0))->getOperand(1), NewType);
7456 Value *Shuffle = Builder.CreateVectorSplat(NewVecType->getNumElements(), BC1);
7457 Value *BC2 = Builder.CreateBitCast(Shuffle, SVIVecType);
7461 SVI, TLInfo,
nullptr,
7462 [&](
Value *V) { removeAllAssertingVHReferences(V); });
7466 if (
auto *BCI = dyn_cast<Instruction>(BC1))
7467 if (
auto *
Op = dyn_cast<Instruction>(BCI->
getOperand(0)))
7468 if (BCI->
getParent() !=
Op->getParent() && !isa<PHINode>(
Op) &&
7469 !
Op->isTerminator() && !
Op->isEHPad())
7475bool CodeGenPrepare::tryToSinkFreeOperands(
Instruction *
I) {
7487 bool Changed =
false;
7491 unsigned long InstNumber = 0;
7492 for (
const auto &
I : *TargetBB)
7493 InstOrdering[&
I] = InstNumber++;
7496 auto *UI = cast<Instruction>(
U->get());
7497 if (isa<PHINode>(UI))
7500 if (InstOrdering[UI] < InstOrdering[InsertPoint])
7509 for (
Use *U : ToReplace) {
7510 auto *UI = cast<Instruction>(
U->get());
7517 if (
auto *OpDef = dyn_cast<Instruction>(
Op))
7518 FreshBBs.
insert(OpDef->getParent());
7521 NewInstructions[UI] = NI;
7526 InsertedInsts.insert(NI);
7532 if (NewInstructions.
count(OldI))
7533 NewInstructions[OldI]->setOperand(
U->getOperandNo(), NI);
7540 for (
auto *
I : MaybeDead) {
7541 if (!
I->hasNUsesOrMore(1)) {
7543 I->eraseFromParent();
7550bool CodeGenPrepare::optimizeSwitchType(
SwitchInst *SI) {
7558 if (RegWidth <= cast<IntegerType>(OldType)->
getBitWidth())
7576 ExtType = Instruction::SExt;
7578 if (
auto *Arg = dyn_cast<Argument>(
Cond)) {
7579 if (Arg->hasSExtAttr())
7580 ExtType = Instruction::SExt;
7581 if (Arg->hasZExtAttr())
7582 ExtType = Instruction::ZExt;
7588 SI->setCondition(ExtInst);
7589 for (
auto Case :
SI->cases()) {
7590 const APInt &NarrowConst = Case.getCaseValue()->getValue();
7591 APInt WideConst = (ExtType == Instruction::ZExt)
7592 ? NarrowConst.
zext(RegWidth)
7593 : NarrowConst.
sext(RegWidth);
7594 Case.setValue(ConstantInt::get(Context, WideConst));
7600bool CodeGenPrepare::optimizeSwitchPhiConstants(
SwitchInst *SI) {
7607 Value *Condition =
SI->getCondition();
7609 if (isa<ConstantInt>(*Condition))
7612 bool Changed =
false;
7618 BasicBlock *CaseBB = Case.getCaseSuccessor();
7621 bool CheckedForSinglePred =
false;
7623 Type *PHIType =
PHI.getType();
7631 if (PHIType == ConditionType || TryZExt) {
7633 bool SkipCase =
false;
7634 Value *Replacement =
nullptr;
7635 for (
unsigned I = 0, E =
PHI.getNumIncomingValues();
I != E;
I++) {
7636 Value *PHIValue =
PHI.getIncomingValue(
I);
7637 if (PHIValue != CaseValue) {
7640 ConstantInt *PHIValueInt = dyn_cast<ConstantInt>(PHIValue);
7646 if (
PHI.getIncomingBlock(
I) != SwitchBB)
7651 if (!CheckedForSinglePred) {
7652 CheckedForSinglePred =
true;
7653 if (
SI->findCaseDest(CaseBB) ==
nullptr) {
7659 if (Replacement ==
nullptr) {
7660 if (PHIValue == CaseValue) {
7661 Replacement = Condition;
7664 Replacement = Builder.CreateZExt(Condition, PHIType);
7667 PHI.setIncomingValue(
I, Replacement);
7678bool CodeGenPrepare::optimizeSwitchInst(
SwitchInst *SI) {
7679 bool Changed = optimizeSwitchType(SI);
7680 Changed |= optimizeSwitchPhiConstants(SI);
7701class VectorPromoteHelper {
7718 unsigned StoreExtractCombineCost;
7727 if (InstsToBePromoted.
empty())
7729 return InstsToBePromoted.
back();
7735 unsigned getTransitionOriginalValueIdx()
const {
7736 assert(isa<ExtractElementInst>(Transition) &&
7737 "Other kind of transitions are not supported yet");
7744 unsigned getTransitionIdx()
const {
7745 assert(isa<ExtractElementInst>(Transition) &&
7746 "Other kind of transitions are not supported yet");
7754 Type *getTransitionType()
const {
7769 bool isProfitableToPromote() {
7770 Value *ValIdx = Transition->
getOperand(getTransitionOriginalValueIdx());
7771 unsigned Index = isa<ConstantInt>(ValIdx)
7772 ? cast<ConstantInt>(ValIdx)->getZExtValue()
7774 Type *PromotedType = getTransitionType();
7777 unsigned AS =
ST->getPointerAddressSpace();
7795 for (
const auto &Inst : InstsToBePromoted) {
7801 bool IsArg0Constant = isa<UndefValue>(Arg0) || isa<ConstantInt>(Arg0) ||
7802 isa<ConstantFP>(Arg0);
7815 dbgs() <<
"Estimated cost of computation to be promoted:\nScalar: "
7816 << ScalarCost <<
"\nVector: " << VectorCost <<
'\n');
7817 return ScalarCost > VectorCost;
7829 unsigned ExtractIdx = std::numeric_limits<unsigned>::max();
7834 if (
ConstantInt *CstVal = dyn_cast<ConstantInt>(ValExtractIdx))
7840 ElementCount EC = cast<VectorType>(getTransitionType())->getElementCount();
7844 if (!
EC.isScalable()) {
7847 for (
unsigned Idx = 0;
Idx !=
EC.getKnownMinValue(); ++
Idx) {
7848 if (
Idx == ExtractIdx)
7856 "Generate scalable vector for non-splat is unimplemented");
7862 unsigned OperandIdx) {
7865 if (OperandIdx != 1)
7867 switch (
Use->getOpcode()) {
7870 case Instruction::SDiv:
7871 case Instruction::UDiv:
7872 case Instruction::SRem:
7873 case Instruction::URem:
7875 case Instruction::FDiv:
7876 case Instruction::FRem:
7877 return !
Use->hasNoNaNs();
7885 unsigned CombineCost)
7886 :
DL(
DL), TLI(TLI),
TTI(
TTI), Transition(Transition),
7887 StoreExtractCombineCost(CombineCost) {
7888 assert(Transition &&
"Do not know how to promote null");
7892 bool canPromote(
const Instruction *ToBePromoted)
const {
7894 return isa<BinaryOperator>(ToBePromoted);
7899 bool shouldPromote(
const Instruction *ToBePromoted)
const {
7903 const Value *Val =
U.get();
7904 if (Val == getEndOfTransition()) {
7908 if (canCauseUndefinedBehavior(ToBePromoted,
U.getOperandNo()))
7912 if (!isa<ConstantInt>(Val) && !isa<UndefValue>(Val) &&
7913 !isa<ConstantFP>(Val))
7922 ISDOpcode, TLI.
getValueType(DL, getTransitionType(),
true));
7931 void enqueueForPromotion(
Instruction *ToBePromoted) {
7932 InstsToBePromoted.push_back(ToBePromoted);
7936 void recordCombineInstruction(
Instruction *ToBeCombined) {
7938 CombineInst = ToBeCombined;
7948 if (InstsToBePromoted.empty() || !CombineInst)
7956 for (
auto &ToBePromoted : InstsToBePromoted)
7957 promoteImpl(ToBePromoted);
7958 InstsToBePromoted.clear();
7965void VectorPromoteHelper::promoteImpl(
Instruction *ToBePromoted) {
7975 "The type of the result of the transition does not match "
7980 Type *TransitionTy = getTransitionType();
7987 Value *NewVal =
nullptr;
7988 if (Val == Transition)
7989 NewVal = Transition->
getOperand(getTransitionOriginalValueIdx());
7990 else if (isa<UndefValue>(Val) || isa<ConstantInt>(Val) ||
7991 isa<ConstantFP>(Val)) {
7994 cast<Constant>(Val),
7995 isa<UndefValue>(Val) ||
7996 canCauseUndefinedBehavior(ToBePromoted,
U.getOperandNo()));
8000 ToBePromoted->
setOperand(
U.getOperandNo(), NewVal);
8003 Transition->
setOperand(getTransitionOriginalValueIdx(), ToBePromoted);
8009bool CodeGenPrepare::optimizeExtractElementInst(
Instruction *Inst) {
8010 unsigned CombineCost = std::numeric_limits<unsigned>::max();
8025 LLVM_DEBUG(
dbgs() <<
"Found an interesting transition: " << *Inst <<
'\n');
8026 VectorPromoteHelper VPH(*
DL, *TLI, *
TTI, Inst, CombineCost);
8033 if (ToBePromoted->
getParent() != Parent) {
8034 LLVM_DEBUG(
dbgs() <<
"Instruction to promote is in a different block ("
8036 <<
") than the transition (" << Parent->
getName()
8041 if (VPH.canCombine(ToBePromoted)) {
8043 <<
"will be combined with: " << *ToBePromoted <<
'\n');
8044 VPH.recordCombineInstruction(ToBePromoted);
8045 bool Changed = VPH.promote();
8046 NumStoreExtractExposed += Changed;
8051 if (!VPH.canPromote(ToBePromoted) || !VPH.shouldPromote(ToBePromoted))
8054 LLVM_DEBUG(
dbgs() <<
"Promoting is possible... Enqueue for promotion!\n");
8056 VPH.enqueueForPromotion(ToBePromoted);
8057 Inst = ToBePromoted;
8097 Type *StoreType = SI.getValueOperand()->getType();
8106 if (!
DL.typeSizeEqualsStoreSize(StoreType) ||
8107 DL.getTypeSizeInBits(StoreType) == 0)
8110 unsigned HalfValBitSize =
DL.getTypeSizeInBits(StoreType) / 2;
8112 if (!
DL.typeSizeEqualsStoreSize(SplitStoreType))
8116 if (SI.isVolatile())
8128 if (!
match(SI.getValueOperand(),
8135 if (!
LValue->getType()->isIntegerTy() ||
8136 DL.getTypeSizeInBits(
LValue->getType()) > HalfValBitSize ||
8138 DL.getTypeSizeInBits(HValue->
getType()) > HalfValBitSize)
8143 auto *LBC = dyn_cast<BitCastInst>(
LValue);
8144 auto *HBC = dyn_cast<BitCastInst>(HValue);
8158 if (LBC && LBC->getParent() != SI.getParent())
8160 if (HBC && HBC->getParent() != SI.getParent())
8161 HValue = Builder.
CreateBitCast(HBC->getOperand(0), HBC->getType());
8163 bool IsLE = SI.getDataLayout().isLittleEndian();
8164 auto CreateSplitStore = [&](
Value *V,
bool Upper) {
8167 Align Alignment = SI.getAlign();
8168 const bool IsOffsetStore = (IsLE &&
Upper) || (!IsLE && !
Upper);
8169 if (IsOffsetStore) {
8171 SplitStoreType,
Addr,
8182 CreateSplitStore(
LValue,
false);
8183 CreateSplitStore(HValue,
true);
8186 SI.eraseFromParent();
8194 return GEP->getNumOperands() == 2 &&
I.isSequential() &&
8195 isa<ConstantInt>(
GEP->getOperand(1));
8273 if (!isa<Instruction>(GEPIOp))
8275 auto *GEPIOpI = cast<Instruction>(GEPIOp);
8276 if (GEPIOpI->getParent() != SrcBlock)
8281 if (auto *I = dyn_cast<Instruction>(Usr)) {
8282 if (I->getParent() != SrcBlock) {
8290 std::vector<GetElementPtrInst *> UGEPIs;
8297 if (!isa<Instruction>(Usr))
8299 auto *UI = cast<Instruction>(Usr);
8304 if (!isa<GetElementPtrInst>(Usr))
8306 auto *UGEPI = cast<GetElementPtrInst>(Usr);
8312 if (UGEPI->getOperand(0) != GEPIOp)
8314 if (UGEPI->getSourceElementType() != GEPI->getSourceElementType())
8316 if (GEPIIdx->getType() !=
8317 cast<ConstantInt>(UGEPI->getOperand(1))->getType())
8319 ConstantInt *UGEPIIdx = cast<ConstantInt>(UGEPI->getOperand(1));
8324 UGEPIs.push_back(UGEPI);
8326 if (UGEPIs.size() == 0)
8330 ConstantInt *UGEPIIdx = cast<ConstantInt>(UGEPI->getOperand(1));
8339 UGEPI->setOperand(0, GEPI);
8340 ConstantInt *UGEPIIdx = cast<ConstantInt>(UGEPI->getOperand(1));
8341 Constant *NewUGEPIIdx = ConstantInt::get(
8342 GEPIIdx->getType(), UGEPIIdx->
getValue() - GEPIIdx->getValue());
8343 UGEPI->setOperand(1, NewUGEPIIdx);
8346 if (!GEPI->isInBounds()) {
8347 UGEPI->setIsInBounds(
false);
8354 return cast<Instruction>(Usr)->getParent() != SrcBlock;
8356 "GEPIOp is used outside SrcBlock");
8376 ICmpInst *Cmp = dyn_cast<ICmpInst>(Branch->getCondition());
8377 if (!Cmp || !isa<ConstantInt>(Cmp->getOperand(1)) || !Cmp->hasOneUse())
8380 Value *
X = Cmp->getOperand(0);
8381 APInt CmpC = cast<ConstantInt>(Cmp->getOperand(1))->getValue();
8383 for (
auto *U :
X->users()) {
8387 (UI->
getParent() != Branch->getParent() &&
8388 UI->
getParent() != Branch->getSuccessor(0) &&
8389 UI->
getParent() != Branch->getSuccessor(1)) ||
8390 (UI->
getParent() != Branch->getParent() &&
8391 !UI->
getParent()->getSinglePredecessor()))
8394 if (CmpC.
isPowerOf2() && Cmp->getPredicate() == ICmpInst::ICMP_ULT &&
8397 if (UI->
getParent() != Branch->getParent())
8401 ConstantInt::get(UI->
getType(), 0));
8403 LLVM_DEBUG(
dbgs() <<
" to compare on zero: " << *NewCmp <<
"\n");
8407 if (Cmp->isEquality() &&
8411 if (UI->
getParent() != Branch->getParent())
8415 ConstantInt::get(UI->
getType(), 0));
8417 LLVM_DEBUG(
dbgs() <<
" to compare on zero: " << *NewCmp <<
"\n");
8425bool CodeGenPrepare::optimizeInst(
Instruction *
I, ModifyDT &ModifiedDT) {
8426 bool AnyChange =
false;
8427 AnyChange = fixupDbgVariableRecordsOnInst(*
I);
8431 if (InsertedInsts.count(
I))
8435 if (
PHINode *
P = dyn_cast<PHINode>(
I)) {
8440 LargeOffsetGEPMap.erase(
P);
8442 P->eraseFromParent();
8449 if (
CastInst *CI = dyn_cast<CastInst>(
I)) {
8462 if ((isa<UIToFPInst>(
I) || isa<SIToFPInst>(
I) || isa<FPToUIInst>(
I) ||
8463 isa<TruncInst>(
I)) &&
8465 I, LI->getLoopFor(
I->getParent()), *
TTI))
8468 if (isa<ZExtInst>(
I) || isa<SExtInst>(
I)) {
8473 TargetLowering::TypeExpandInteger) {
8477 I, LI->getLoopFor(
I->getParent()), *
TTI))
8480 bool MadeChange = optimizeExt(
I);
8481 return MadeChange | optimizeExtUses(
I);
8487 if (
auto *Cmp = dyn_cast<CmpInst>(
I))
8488 if (optimizeCmp(Cmp, ModifiedDT))
8492 if (optimizeURem(
I))
8495 if (
LoadInst *LI = dyn_cast<LoadInst>(
I)) {
8496 LI->
setMetadata(LLVMContext::MD_invariant_group,
nullptr);
8497 bool Modified = optimizeLoadExt(LI);
8503 if (
StoreInst *SI = dyn_cast<StoreInst>(
I)) {
8506 SI->setMetadata(LLVMContext::MD_invariant_group,
nullptr);
8507 unsigned AS =
SI->getPointerAddressSpace();
8508 return optimizeMemoryInst(
I,
SI->getOperand(1),
8509 SI->getOperand(0)->getType(), AS);
8513 unsigned AS = RMW->getPointerAddressSpace();
8514 return optimizeMemoryInst(
I, RMW->getPointerOperand(), RMW->getType(), AS);
8518 unsigned AS = CmpX->getPointerAddressSpace();
8519 return optimizeMemoryInst(
I, CmpX->getPointerOperand(),
8520 CmpX->getCompareOperand()->getType(), AS);
8530 if (BinOp && (BinOp->
getOpcode() == Instruction::AShr ||
8531 BinOp->
getOpcode() == Instruction::LShr)) {
8539 if (GEPI->hasAllZeroIndices()) {
8542 GEPI->getName(), GEPI->getIterator());
8543 NC->setDebugLoc(GEPI->getDebugLoc());
8546 GEPI, TLInfo,
nullptr,
8547 [&](
Value *V) { removeAllAssertingVHReferences(V); });
8549 optimizeInst(
NC, ModifiedDT);
8561 if (
ICmpInst *
II = dyn_cast<ICmpInst>(FI->getOperand(0)))
8563 else if (
FCmpInst *
F = dyn_cast<FCmpInst>(FI->getOperand(0)))
8564 CmpI =
F->getFastMathFlags().none() ?
F :
nullptr;
8568 bool Const0 = isa<ConstantInt>(Op0) || isa<ConstantFP>(Op0) ||
8569 isa<ConstantPointerNull>(Op0);
8570 bool Const1 = isa<ConstantInt>(Op1) || isa<ConstantFP>(Op1) ||
8571 isa<ConstantPointerNull>(Op1);
8572 if (Const0 || Const1) {
8573 if (!Const0 || !Const1) {
8579 FI->eraseFromParent();
8586 if (tryToSinkFreeOperands(
I))
8589 switch (
I->getOpcode()) {
8590 case Instruction::Shl:
8591 case Instruction::LShr:
8592 case Instruction::AShr:
8593 return optimizeShiftInst(cast<BinaryOperator>(
I));
8594 case Instruction::Call:
8596 case Instruction::Select:
8597 return optimizeSelectInst(cast<SelectInst>(
I));
8598 case Instruction::ShuffleVector:
8599 return optimizeShuffleVectorInst(cast<ShuffleVectorInst>(
I));
8600 case Instruction::Switch:
8601 return optimizeSwitchInst(cast<SwitchInst>(
I));
8602 case Instruction::ExtractElement:
8603 return optimizeExtractElementInst(cast<ExtractElementInst>(
I));
8604 case Instruction::Br:
8605 return optimizeBranch(cast<BranchInst>(
I), *TLI, FreshBBs, IsHugeFunc);
8614 if (!
I.getType()->isIntegerTy() ||
8625 &
I, TLInfo,
nullptr,
8626 [&](
Value *V) { removeAllAssertingVHReferences(V); });
8633bool CodeGenPrepare::optimizeBlock(
BasicBlock &BB, ModifyDT &ModifiedDT) {
8635 bool MadeChange =
false;
8638 CurInstIterator = BB.
begin();
8639 ModifiedDT = ModifyDT::NotModifyDT;
8640 while (CurInstIterator != BB.
end()) {
8641 MadeChange |= optimizeInst(&*CurInstIterator++, ModifiedDT);
8642 if (ModifiedDT != ModifyDT::NotModifyDT) {
8655 }
while (ModifiedDT == ModifyDT::ModifyInstDT);
8657 bool MadeBitReverse =
true;
8658 while (MadeBitReverse) {
8659 MadeBitReverse =
false;
8661 if (makeBitReverse(
I)) {
8662 MadeBitReverse = MadeChange =
true;
8667 MadeChange |= dupRetToEnableTailCallOpts(&BB, ModifiedDT);
8679 bool AnyChange =
false;
8682 for (
Value *Location : LocationOps) {
8698bool CodeGenPrepare::fixupDbgVariableRecordsOnInst(
Instruction &
I) {
8699 bool AnyChange =
false;
8701 AnyChange |= fixupDbgVariableRecord(DVR);
8708 if (DVR.
Type != DbgVariableRecord::LocationType::Value &&
8709 DVR.
Type != DbgVariableRecord::LocationType::Assign)
8713 bool AnyChange =
false;
8716 for (
Value *Location : LocationOps) {
8734 if (isa<PHINode>(VI))
8735 DVI->
insertBefore(&*VI->getParent()->getFirstInsertionPt());
8743 if (isa<PHINode>(VI))
8754bool CodeGenPrepare::placeDbgValues(
Function &
F) {
8755 bool MadeChange =
false;
8758 auto DbgProcessor = [&](
auto *DbgItem,
Instruction *Position) {
8760 for (
Value *V : DbgItem->location_ops())
8761 if (
Instruction *VI = dyn_cast_or_null<Instruction>(V))
8769 if (
VI->isTerminator())
8774 if (isa<PHINode>(VI) &&
VI->getParent()->getTerminator()->isEHPad())
8785 if (VIs.size() > 1) {
8788 <<
"Unable to find valid location for Debug Value, undefing:\n"
8790 DbgItem->setKillLocation();
8795 << *DbgItem <<
' ' << *VI);
8807 DbgProcessor(DVI, DVI);
8815 if (DVR.
Type != DbgVariableRecord::LocationType::Value)
8817 DbgProcessor(&DVR, &
Insn);
8828bool CodeGenPrepare::placePseudoProbes(
Function &
F) {
8829 bool MadeChange =
false;
8832 auto FirstInst =
Block.getFirstInsertionPt();
8833 while (FirstInst !=
Block.end() && FirstInst->isDebugOrPseudoInst())
8837 while (
I !=
Block.end()) {
8838 if (
auto *
II = dyn_cast<PseudoProbeInst>(
I++)) {
8839 II->moveBefore(&*FirstInst);
8849 uint64_t NewMax = (NewTrue > NewFalse) ? NewTrue : NewFalse;
8850 uint32_t Scale = (NewMax / std::numeric_limits<uint32_t>::max()) + 1;
8851 NewTrue = NewTrue / Scale;
8852 NewFalse = NewFalse / Scale;
8877bool CodeGenPrepare::splitBranchCondition(
Function &
F, ModifyDT &ModifiedDT) {
8881 bool MadeChange =
false;
8882 for (
auto &BB :
F) {
8895 if (Br1->getMetadata(LLVMContext::MD_unpredictable))
8903 Value *Cond1, *Cond2;
8906 Opc = Instruction::And;
8909 Opc = Instruction::Or;
8919 if (!IsGoodCond(Cond1) || !IsGoodCond(Cond2))
8933 Br1->setCondition(Cond1);
8938 if (Opc == Instruction::And)
8939 Br1->setSuccessor(0, TmpBB);
8941 Br1->setSuccessor(1, TmpBB);
8945 if (
auto *
I = dyn_cast<Instruction>(Cond2)) {
8946 I->removeFromParent();
8947 I->insertBefore(Br2);
8959 if (Opc == Instruction::Or)
8973 if (Opc == Instruction::Or) {
8995 uint64_t NewTrueWeight = TrueWeight;
8996 uint64_t NewFalseWeight = TrueWeight + 2 * FalseWeight;
8998 Br1->setMetadata(LLVMContext::MD_prof,
9003 NewTrueWeight = TrueWeight;
9004 NewFalseWeight = 2 * FalseWeight;
9006 Br2->setMetadata(LLVMContext::MD_prof,
9031 uint64_t NewTrueWeight = 2 * TrueWeight + FalseWeight;
9032 uint64_t NewFalseWeight = FalseWeight;
9034 Br1->setMetadata(LLVMContext::MD_prof,
9038 NewTrueWeight = 2 * TrueWeight;
9039 NewFalseWeight = FalseWeight;
9041 Br2->setMetadata(LLVMContext::MD_prof,
9047 ModifiedDT = ModifyDT::ModifyBBDT;
for(const MachineOperand &MO :llvm::drop_begin(OldMI.operands(), Desc.getNumOperands()))
static unsigned getIntrinsicID(const SDNode *N)
static bool canCombine(MachineBasicBlock &MBB, MachineOperand &MO, unsigned CombineOpc, unsigned ZeroReg=0, bool CheckZeroReg=false)
SmallVector< AArch64_IMM::ImmInsnModel, 4 > Insn
amdgpu AMDGPU Register Bank Select
This file implements a class to represent arbitrary precision integral constant values and operations...
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
This file contains the simple types necessary to represent the attributes associated with functions a...
static const Function * getParent(const Value *V)
BlockVerifier::State From
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
static bool sinkAndCmp0Expression(Instruction *AndI, const TargetLowering &TLI, SetOfInstrs &InsertedInsts)
Duplicate and sink the given 'and' instruction into user blocks where it is used in a compare to allo...
static bool SinkShiftAndTruncate(BinaryOperator *ShiftI, Instruction *User, ConstantInt *CI, DenseMap< BasicBlock *, BinaryOperator * > &InsertedShifts, const TargetLowering &TLI, const DataLayout &DL)
Sink both shift and truncate instruction to the use of truncate's BB.
static bool getGEPSmallConstantIntOffsetV(GetElementPtrInst *GEP, SmallVectorImpl< Value * > &OffsetV)
Optimize for code generation
static bool sinkSelectOperand(const TargetTransformInfo *TTI, Value *V)
Check if V (an operand of a select instruction) is an expensive instruction that is only used once.
static void replaceAllUsesWith(Value *Old, Value *New, SmallSet< BasicBlock *, 32 > &FreshBBs, bool IsHuge)
Replace all old uses with new ones, and push the updated BBs into FreshBBs.
static bool isExtractBitsCandidateUse(Instruction *User)
Check if the candidates could be combined with a shift instruction, which includes:
static cl::opt< unsigned > MaxAddressUsersToScan("cgp-max-address-users-to-scan", cl::init(100), cl::Hidden, cl::desc("Max number of address users to look at"))
static cl::opt< bool > OptimizePhiTypes("cgp-optimize-phi-types", cl::Hidden, cl::init(true), cl::desc("Enable converting phi types in CodeGenPrepare"))
static cl::opt< bool > DisableStoreExtract("disable-cgp-store-extract", cl::Hidden, cl::init(false), cl::desc("Disable store(extract) optimizations in CodeGenPrepare"))
static bool foldFCmpToFPClassTest(CmpInst *Cmp, const TargetLowering &TLI, const DataLayout &DL)
static bool sinkCmpExpression(CmpInst *Cmp, const TargetLowering &TLI)
Sink the given CmpInst into user blocks to reduce the number of virtual registers that must be create...
static void scaleWeights(uint64_t &NewTrue, uint64_t &NewFalse)
Scale down both weights to fit into uint32_t.
static cl::opt< bool > ProfileUnknownInSpecialSection("profile-unknown-in-special-section", cl::Hidden, cl::desc("In profiling mode like sampleFDO, if a function doesn't have " "profile, we cannot tell the function is cold for sure because " "it may be a function newly added without ever being sampled. " "With the flag enabled, compiler can put such profile unknown " "functions into a special section, so runtime system can choose " "to handle it in a different way than .text section, to save " "RAM for example. "))
static bool OptimizeExtractBits(BinaryOperator *ShiftI, ConstantInt *CI, const TargetLowering &TLI, const DataLayout &DL)
Sink the shift right instruction into user blocks if the uses could potentially be combined with this...
static cl::opt< bool > DisableExtLdPromotion("disable-cgp-ext-ld-promotion", cl::Hidden, cl::init(false), cl::desc("Disable ext(promotable(ld)) -> promoted(ext(ld)) optimization in " "CodeGenPrepare"))
static cl::opt< bool > DisablePreheaderProtect("disable-preheader-prot", cl::Hidden, cl::init(false), cl::desc("Disable protection against removing loop preheaders"))
static cl::opt< bool > AddrSinkCombineBaseOffs("addr-sink-combine-base-offs", cl::Hidden, cl::init(true), cl::desc("Allow combining of BaseOffs field in Address sinking."))
static bool OptimizeNoopCopyExpression(CastInst *CI, const TargetLowering &TLI, const DataLayout &DL)
If the specified cast instruction is a noop copy (e.g.
static bool splitMergedValStore(StoreInst &SI, const DataLayout &DL, const TargetLowering &TLI)
For the instruction sequence of store below, F and I values are bundled together as an i64 value befo...
static bool SinkCast(CastInst *CI)
Sink the specified cast instruction into its user blocks.
static bool swapICmpOperandsToExposeCSEOpportunities(CmpInst *Cmp)
Many architectures use the same instruction for both subtract and cmp.
static cl::opt< bool > AddrSinkCombineBaseReg("addr-sink-combine-base-reg", cl::Hidden, cl::init(true), cl::desc("Allow combining of BaseReg field in Address sinking."))
static bool FindAllMemoryUses(Instruction *I, SmallVectorImpl< std::pair< Use *, Type * > > &MemoryUses, SmallPtrSetImpl< Instruction * > &ConsideredInsts, const TargetLowering &TLI, const TargetRegisterInfo &TRI, bool OptSize, ProfileSummaryInfo *PSI, BlockFrequencyInfo *BFI, unsigned &SeenInsts)
Recursively walk all the uses of I until we find a memory use.
static cl::opt< bool > StressStoreExtract("stress-cgp-store-extract", cl::Hidden, cl::init(false), cl::desc("Stress test store(extract) optimizations in CodeGenPrepare"))
static bool isFormingBranchFromSelectProfitable(const TargetTransformInfo *TTI, const TargetLowering *TLI, SelectInst *SI)
Returns true if a SelectInst should be turned into an explicit branch.
static std::optional< std::pair< Instruction *, Constant * > > getIVIncrement(const PHINode *PN, const LoopInfo *LI)
If given PN is an inductive variable with value IVInc coming from the backedge, and on each iteration...
static cl::opt< bool > AddrSinkCombineBaseGV("addr-sink-combine-base-gv", cl::Hidden, cl::init(true), cl::desc("Allow combining of BaseGV field in Address sinking."))
static cl::opt< bool > AddrSinkUsingGEPs("addr-sink-using-gep", cl::Hidden, cl::init(true), cl::desc("Address sinking in CGP using GEPs."))
static bool isRemOfLoopIncrementWithLoopInvariant(Instruction *Rem, const LoopInfo *LI, Value *&RemAmtOut, PHINode *&LoopIncrPNOut)
static Value * getTrueOrFalseValue(SelectInst *SI, bool isTrue, const SmallPtrSet< const Instruction *, 2 > &Selects)
If isTrue is true, return the true value of SI, otherwise return false value of SI.
static void DbgInserterHelper(DbgValueInst *DVI, Instruction *VI)
static cl::opt< bool > DisableBranchOpts("disable-cgp-branch-opts", cl::Hidden, cl::init(false), cl::desc("Disable branch optimizations in CodeGenPrepare"))
static cl::opt< bool > EnableTypePromotionMerge("cgp-type-promotion-merge", cl::Hidden, cl::desc("Enable merging of redundant sexts when one is dominating" " the other."), cl::init(true))
static cl::opt< bool > EnableAndCmpSinking("enable-andcmp-sinking", cl::Hidden, cl::init(true), cl::desc("Enable sinkinig and/cmp into branches."))
static cl::opt< bool > ProfileGuidedSectionPrefix("profile-guided-section-prefix", cl::Hidden, cl::init(true), cl::desc("Use profile info to add section prefix for hot/cold functions"))
static cl::opt< unsigned > HugeFuncThresholdInCGPP("cgpp-huge-func", cl::init(10000), cl::Hidden, cl::desc("Least BB number of huge function."))
static cl::opt< bool > AddrSinkNewSelects("addr-sink-new-select", cl::Hidden, cl::init(true), cl::desc("Allow creation of selects in Address sinking."))
static bool tryUnmergingGEPsAcrossIndirectBr(GetElementPtrInst *GEPI, const TargetTransformInfo *TTI)
static bool IsOperandAMemoryOperand(CallInst *CI, InlineAsm *IA, Value *OpVal, const TargetLowering &TLI, const TargetRegisterInfo &TRI)
Check to see if all uses of OpVal by the specified inline asm call are due to memory operands.
static bool isIntrinsicOrLFToBeTailCalled(const TargetLibraryInfo *TLInfo, const CallInst *CI)
static cl::opt< bool > ForceSplitStore("force-split-store", cl::Hidden, cl::init(false), cl::desc("Force store splitting no matter what the target query says."))
static void computeBaseDerivedRelocateMap(const SmallVectorImpl< GCRelocateInst * > &AllRelocateCalls, MapVector< GCRelocateInst *, SmallVector< GCRelocateInst *, 0 > > &RelocateInstMap)
static bool simplifyRelocatesOffABase(GCRelocateInst *RelocatedBase, const SmallVectorImpl< GCRelocateInst * > &Targets)
static cl::opt< bool > AddrSinkCombineScaledReg("addr-sink-combine-scaled-reg", cl::Hidden, cl::init(true), cl::desc("Allow combining of ScaledReg field in Address sinking."))
static bool foldICmpWithDominatingICmp(CmpInst *Cmp, const TargetLowering &TLI)
For pattern like:
static bool MightBeFoldableInst(Instruction *I)
This is a little filter, which returns true if an addressing computation involving I might be folded ...
static bool matchIncrement(const Instruction *IVInc, Instruction *&LHS, Constant *&Step)
static cl::opt< bool > EnableGEPOffsetSplit("cgp-split-large-offset-gep", cl::Hidden, cl::init(true), cl::desc("Enable splitting large offset of GEP."))
static cl::opt< bool > DisableComplexAddrModes("disable-complex-addr-modes", cl::Hidden, cl::init(false), cl::desc("Disables combining addressing modes with different parts " "in optimizeMemoryInst."))
static cl::opt< bool > EnableICMP_EQToICMP_ST("cgp-icmp-eq2icmp-st", cl::Hidden, cl::init(false), cl::desc("Enable ICMP_EQ to ICMP_S(L|G)T conversion."))
static cl::opt< bool > VerifyBFIUpdates("cgp-verify-bfi-updates", cl::Hidden, cl::init(false), cl::desc("Enable BFI update verification for " "CodeGenPrepare."))
static cl::opt< bool > BBSectionsGuidedSectionPrefix("bbsections-guided-section-prefix", cl::Hidden, cl::init(true), cl::desc("Use the basic-block-sections profile to determine the text " "section prefix for hot functions. Functions with " "basic-block-sections profile will be placed in `.text.hot` " "regardless of their FDO profile info. Other functions won't be " "impacted, i.e., their prefixes will be decided by FDO/sampleFDO " "profiles."))
static bool isIVIncrement(const Value *V, const LoopInfo *LI)
static cl::opt< bool > DisableGCOpts("disable-cgp-gc-opts", cl::Hidden, cl::init(false), cl::desc("Disable GC optimizations in CodeGenPrepare"))
static bool GEPSequentialConstIndexed(GetElementPtrInst *GEP)
static bool isPromotedInstructionLegal(const TargetLowering &TLI, const DataLayout &DL, Value *Val)
Check whether or not Val is a legal instruction for TLI.
static cl::opt< uint64_t > FreqRatioToSkipMerge("cgp-freq-ratio-to-skip-merge", cl::Hidden, cl::init(2), cl::desc("Skip merging empty blocks if (frequency of empty block) / " "(frequency of destination block) is greater than this ratio"))
static bool optimizeBranch(BranchInst *Branch, const TargetLowering &TLI, SmallSet< BasicBlock *, 32 > &FreshBBs, bool IsHugeFunc)
static bool IsNonLocalValue(Value *V, BasicBlock *BB)
Return true if the specified values are defined in a different basic block than BB.
static bool despeculateCountZeros(IntrinsicInst *CountZeros, LoopInfo &LI, const TargetLowering *TLI, const DataLayout *DL, ModifyDT &ModifiedDT, SmallSet< BasicBlock *, 32 > &FreshBBs, bool IsHugeFunc)
If counting leading or trailing zeros is an expensive operation and a zero input is defined,...
static bool hasSameExtUse(Value *Val, const TargetLowering &TLI)
Check if all the uses of Val are equivalent (or free) zero or sign extensions.
static cl::opt< bool > StressExtLdPromotion("stress-cgp-ext-ld-promotion", cl::Hidden, cl::init(false), cl::desc("Stress test ext(promotable(ld)) -> promoted(ext(ld)) " "optimization in CodeGenPrepare"))
static bool matchUAddWithOverflowConstantEdgeCases(CmpInst *Cmp, BinaryOperator *&Add)
Match special-case patterns that check for unsigned add overflow.
static cl::opt< bool > DisableSelectToBranch("disable-cgp-select2branch", cl::Hidden, cl::init(false), cl::desc("Disable select to branch conversion."))
static cl::opt< bool > DisableDeletePHIs("disable-cgp-delete-phis", cl::Hidden, cl::init(false), cl::desc("Disable elimination of dead PHI nodes."))
static bool foldURemOfLoopIncrement(Instruction *Rem, const DataLayout *DL, const LoopInfo *LI, SmallSet< BasicBlock *, 32 > &FreshBBs, bool IsHuge)
static cl::opt< bool > AddrSinkNewPhis("addr-sink-new-phis", cl::Hidden, cl::init(false), cl::desc("Allow creation of Phis in Address sinking."))
Defines an IR pass for CodeGen Prepare.
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
#define LLVM_ATTRIBUTE_UNUSED
This file contains the declarations for the subclasses of Constant, which represent the different fla...
static void clear(coro::Shape &Shape)
static cl::opt< TargetTransformInfo::TargetCostKind > CostKind("cost-kind", cl::desc("Target cost kind"), cl::init(TargetTransformInfo::TCK_RecipThroughput), cl::values(clEnumValN(TargetTransformInfo::TCK_RecipThroughput, "throughput", "Reciprocal throughput"), clEnumValN(TargetTransformInfo::TCK_Latency, "latency", "Instruction latency"), clEnumValN(TargetTransformInfo::TCK_CodeSize, "code-size", "Code size"), clEnumValN(TargetTransformInfo::TCK_SizeAndLatency, "size-latency", "Code size and latency")))
Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx
This file defines the DenseMap class.
DenseMap< Block *, BlockRelaxAux > Blocks
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
Rewrite Partial Register Uses
This defines the Use class.
static void eraseInstruction(Instruction &I, ICFLoopSafetyInfo &SafetyInfo, MemorySSAUpdater &MSSAU)
unsigned const TargetRegisterInfo * TRI
This file implements a map that provides insertion order iteration.
Module.h This file contains the declarations for the Module class.
uint64_t IntrinsicInst * II
static GCMetadataPrinterRegistry::Add< OcamlGCMetadataPrinter > Y("ocaml", "ocaml 3.10-compatible collector")
#define INITIALIZE_PASS_DEPENDENCY(depName)
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
This file defines the PointerIntPair class.
This file contains the declarations for profiling metadata utility functions.
const SmallVectorImpl< MachineOperand > MachineBasicBlock * TBB
const SmallVectorImpl< MachineOperand > & Cond
static bool dominates(InstrPosIndexes &PosIndexes, const MachineInstr &A, const MachineInstr &B)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
static bool optimizeCallInst(CallInst *CI, bool &ModifiedDT, const TargetTransformInfo &TTI, const DataLayout &DL, DomTreeUpdater *DTU)
static bool optimizeBlock(BasicBlock &BB, bool &ModifiedDT, const TargetTransformInfo &TTI, const DataLayout &DL, DomTreeUpdater *DTU)
This file defines the SmallPtrSet class.
This file defines the SmallVector class.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
static SymbolRef::Type getType(const Symbol *Sym)
This file describes how to lower LLVM code to machine code.
static cl::opt< bool > DisableSelectOptimize("disable-select-optimize", cl::init(true), cl::Hidden, cl::desc("Disable the select-optimization pass from running"))
Disable the select optimization pass.
Target-Independent Code Generator Pass Configuration Options pass.
static unsigned getBitWidth(Type *Ty, const DataLayout &DL)
Returns the bitwidth of the given scalar or pointer type.
static Constant * getConstantVector(MVT VT, ArrayRef< APInt > Bits, const APInt &Undefs, LLVMContext &C)
Class for arbitrary precision integers.
APInt zext(unsigned width) const
Zero extend to a new width.
bool ugt(const APInt &RHS) const
Unsigned greater than comparison.
bool isZero() const
Determine if this value is zero, i.e. all bits are clear.
bool isSignedIntN(unsigned N) const
Check if this APInt has an N-bits signed integer value.
unsigned getSignificantBits() const
Get the minimum bit size for this signed APInt.
unsigned logBase2() const
APInt sext(unsigned width) const
Sign extend to a new width.
bool isPowerOf2() const
Check if this APInt's value is a power of two greater than zero.
int64_t getSExtValue() const
Get sign extended value.
an instruction to allocate memory on the stack
bool isStaticAlloca() const
Return true if this alloca is in the entry block of the function and is a constant size.
Align getAlign() const
Return the alignment of the memory that is being allocated by the instruction.
Type * getAllocatedType() const
Return the type that is being allocated by the instruction.
void setAlignment(Align Align)
A container for analyses that lazily runs them and caches their results.
PassT::Result * getCachedResult(IRUnitT &IR) const
Get the cached result of an analysis pass for a given IR unit.
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Represent the analysis usage information of a pass.
AnalysisUsage & addUsedIfAvailable()
Add the specified Pass class to the set of analyses used by this pass.
AnalysisUsage & addRequired()
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Value handle that asserts if the Value is deleted.
An instruction that atomically checks whether a specified value is in a memory location,...
static unsigned getPointerOperandIndex()
an instruction that atomically reads a memory location, combines it with another value,...
static unsigned getPointerOperandIndex()
Analysis pass providing the BasicBlockSectionsProfileReader.
bool isFunctionHot(StringRef FuncName) const
LLVM Basic Block Representation.
iterator begin()
Instruction iterator methods.
iterator_range< const_phi_iterator > phis() const
Returns a range that iterates over the phis in the basic block.
const_iterator getFirstInsertionPt() const
Returns an iterator to the first instruction in this block that is suitable for inserting a non-PHI i...
bool hasAddressTaken() const
Returns true if there are any uses of this basic block other than direct branches,...
void insertDbgRecordBefore(DbgRecord *DR, InstListType::iterator Here)
Insert a DbgRecord into a block at the position given by Here.
const Instruction * getFirstNonPHI() const
Returns a pointer to the first instruction in this block that is not a PHINode instruction.
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
BasicBlock * splitBasicBlock(iterator I, const Twine &BBName="", bool Before=false)
Split the basic block into two basic blocks at the specified instruction.
const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
const BasicBlock * getUniquePredecessor() const
Return the predecessor of this block if it has a unique predecessor block.
const BasicBlock * getSingleSuccessor() const
Return the successor of this block if it has a single successor.
const Function * getParent() const
Return the enclosing method, or null if none.
SymbolTableList< BasicBlock >::iterator eraseFromParent()
Unlink 'this' from the containing function and delete it.
void insertDbgRecordAfter(DbgRecord *DR, Instruction *I)
Insert a DbgRecord into a block at the position given by I.
const Instruction * getFirstNonPHIOrDbg(bool SkipPseudoOp=true) const
Returns a pointer to the first instruction in this block that is not a PHINode or a debug intrinsic,...
InstListType::iterator iterator
Instruction iterators...
LLVMContext & getContext() const
Get the context in which this basic block lives.
bool IsNewDbgInfoFormat
Flag recording whether or not this block stores debug-info in the form of intrinsic instructions (fal...
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
BinaryOps getOpcode() const
static BinaryOperator * Create(BinaryOps Op, Value *S1, Value *S2, const Twine &Name=Twine(), InsertPosition InsertBefore=nullptr)
Construct a binary instruction, given the opcode and the two operands.
This class represents a no-op cast from one type to another.
BlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate IR basic block frequen...
Conditional or Unconditional Branch instruction.
void swapSuccessors()
Swap the successors of this branch instruction.
bool isConditional() const
BasicBlock * getSuccessor(unsigned i) const
bool isUnconditional() const
Analysis providing branch probability information.
static BranchProbability getBranchProbability(uint64_t Numerator, uint64_t Denominator)
bool isInlineAsm() const
Check if this call is an inline asm statement.
Function * getCalledFunction() const
Returns the function called, or null if this is an indirect function invocation or the function signa...
bool hasFnAttr(Attribute::AttrKind Kind) const
Determine whether this call has the given attribute.
Value * getArgOperand(unsigned i) const
void setArgOperand(unsigned i, Value *v)
iterator_range< User::op_iterator > args()
Iteration adapter for range-for loops.
This class represents a function call, abstracting a target machine's calling convention.
This is the base class for all instructions that perform data casts.
static CastInst * Create(Instruction::CastOps, Value *S, Type *Ty, const Twine &Name="", InsertPosition InsertBefore=nullptr)
Provides a way to construct any of the CastInst subclasses using an opcode instead of the subclass's ...
This class is the base class for the comparison instructions.
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
@ ICMP_SLT
signed less than
@ ICMP_UGT
unsigned greater than
@ ICMP_SGT
signed greater than
@ ICMP_ULT
unsigned less than
Predicate getSwappedPredicate() const
For example, EQ->EQ, SLE->SGE, ULT->UGT, OEQ->OEQ, ULE->UGE, OLT->OGT, etc.
static CmpInst * Create(OtherOps Op, Predicate Pred, Value *S1, Value *S2, const Twine &Name="", InsertPosition InsertBefore=nullptr)
Construct a compare instruction, given the opcode, the predicate and the two operands.
Predicate getPredicate() const
Return the predicate for this instruction.
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Base class for constants with no operands.
A constant value that is initialized with an expression using other constant values.
static Constant * getBitCast(Constant *C, Type *Ty, bool OnlyIfReduced=false)
static Constant * getNeg(Constant *C, bool HasNSW=false)
This is the shared class of boolean and integer constants.
static ConstantInt * getTrue(LLVMContext &Context)
bool isZero() const
This is just a convenience method to make client code smaller for a common code.
int64_t getSExtValue() const
Return the constant as a 64-bit integer value after it has been sign extended as appropriate for the ...
const APInt & getValue() const
Return the constant as an APInt value reference.
static Constant * getSplat(ElementCount EC, Constant *Elt)
Return a ConstantVector with the specified constant in each element.
static Constant * get(ArrayRef< Constant * > V)
This is an important base class in LLVM.
static Constant * getAllOnesValue(Type *Ty)
static Constant * getNullValue(Type *Ty)
Constructor to create a '0' constant of arbitrary type.
This class represents an Operation in the Expression.
A parsed version of the target data layout string in and methods for querying it.
IntegerType * getIntPtrType(LLVMContext &C, unsigned AddressSpace=0) const
Returns an integer type with size at least as big as that of a pointer in the given address space.
This represents the llvm.dbg.value instruction.
iterator_range< location_op_iterator > location_ops() const
Get the locations corresponding to the variable referenced by the debug info intrinsic.
void replaceVariableLocationOp(Value *OldValue, Value *NewValue, bool AllowEmpty=false)
Record of a variable value-assignment, aka a non instruction representation of the dbg....
LocationType Type
Classification of the debug-info record that this DbgVariableRecord represents.
void replaceVariableLocationOp(Value *OldValue, Value *NewValue, bool AllowEmpty=false)
iterator_range< location_op_iterator > location_ops() const
Get the locations corresponding to the variable referenced by the debug info intrinsic.
iterator find(const_arg_type_t< KeyT > Val)
bool erase(const KeyT &Val)
size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
bool isReachableFromEntry(const Use &U) const
Provide an overload for a Use.
bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
This instruction compares its operands according to the predicate given to the constructor.
static FixedVectorType * get(Type *ElementType, unsigned NumElts)
This class implements simplifications for calls to fortified library functions (__st*cpy_chk,...
This class represents a freeze function that returns random concrete value if an operand is either a ...
FunctionPass class - This class is used to implement most global optimizations.
virtual bool runOnFunction(Function &F)=0
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass.
const BasicBlock & getEntryBlock() const
const Value * getStatepoint() const
The statepoint with which this gc.relocate is associated.
Represents calls to the gc.relocate intrinsic.
unsigned getBasePtrIndex() const
The index into the associate statepoint's argument list which contains the base pointer of the pointe...
Represents a gc.statepoint intrinsic call.
an instruction for type-safe pointer arithmetic to access elements of arrays and structs
static Type * getIndexedType(Type *Ty, ArrayRef< Value * > IdxList)
Returns the result type of a getelementptr with the given source element type and indexes.
void setAlignment(Align Align)
Sets the alignment attribute of the GlobalObject.
bool canIncreaseAlignment() const
Returns true if the alignment of the value can be unilaterally increased.
bool isThreadLocal() const
If the value is "Thread Local", its value isn't shared by the threads.
Type * getValueType() const
This instruction compares its operands according to the predicate given to the constructor.
Value * CreateZExtOrBitCast(Value *V, Type *DestTy, const Twine &Name="")
ConstantInt * getTrue()
Get the constant value for i1 true.
Value * CreateSelect(Value *C, Value *True, Value *False, const Twine &Name="", Instruction *MDFrom=nullptr)
Value * CreateFreeze(Value *V, const Twine &Name="")
void SetCurrentDebugLocation(DebugLoc L)
Set location information used by debugging information.
Value * CreateNUWAdd(Value *LHS, Value *RHS, const Twine &Name="")
Value * CreateGEP(Type *Ty, Value *Ptr, ArrayRef< Value * > IdxList, const Twine &Name="", GEPNoWrapFlags NW=GEPNoWrapFlags::none())
Value * createIsFPClass(Value *FPNum, unsigned Test)
Value * CreateCmp(CmpInst::Predicate Pred, Value *LHS, Value *RHS, const Twine &Name="", MDNode *FPMathTag=nullptr)
PHINode * CreatePHI(Type *Ty, unsigned NumReservedValues, const Twine &Name="")
Value * CreateICmpEQ(Value *LHS, Value *RHS, const Twine &Name="")
Value * CreateBitCast(Value *V, Type *DestTy, const Twine &Name="")
BranchInst * CreateCondBr(Value *Cond, BasicBlock *True, BasicBlock *False, MDNode *BranchWeights=nullptr, MDNode *Unpredictable=nullptr)
Create a conditional 'br Cond, TrueDest, FalseDest' instruction.
void SetInsertPoint(BasicBlock *TheBB)
This specifies that created instructions should be appended to the end of the specified block.
StoreInst * CreateAlignedStore(Value *Val, Value *Ptr, MaybeAlign Align, bool isVolatile=false)
Value * CreateICmp(CmpInst::Predicate P, Value *LHS, Value *RHS, const Twine &Name="")
ConstantInt * getInt(const APInt &AI)
Get a constant integer value.
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Instruction * clone() const
Create a copy of 'this' instruction that is identical in all ways except the following:
void removeFromParent()
This method unlinks 'this' from the containing basic block, but does not delete it.
void insertBefore(Instruction *InsertPos)
Insert an unlinked instruction into a basic block immediately before the specified instruction.
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
const Instruction * getPrevNonDebugInstruction(bool SkipPseudoOp=false) const
Return a pointer to the previous non-debug instruction in the same basic block as 'this',...
void moveAfter(Instruction *MovePos)
Unlink this instruction from its current basic block and insert it into the basic block that MovePos ...
bool isEHPad() const
Return true if the instruction is a variety of EH-block.
InstListType::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
Instruction * user_back()
Specialize the methods defined in Value, as we know that an instruction can only be used by other ins...
const Function * getFunction() const
Return the function this instruction belongs to.
void setMetadata(unsigned KindID, MDNode *Node)
Set the metadata of the specified kind to the specified node.
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
void dropPoisonGeneratingFlags()
Drops flags that may cause this instruction to evaluate to poison despite having non-poison inputs.
std::optional< simple_ilist< DbgRecord >::iterator > getDbgReinsertionPosition()
Return an iterator to the position of the "Next" DbgRecord after this instruction,...
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
void copyMetadata(const Instruction &SrcInst, ArrayRef< unsigned > WL=ArrayRef< unsigned >())
Copy metadata from SrcInst to this instruction.
void insertAfter(Instruction *InsertPos)
Insert an unlinked instruction into a basic block immediately after the specified instruction.
void moveBefore(Instruction *MovePos)
Unlink this instruction from its current basic block and insert it into the basic block that MovePos ...
A wrapper class for inspecting calls to intrinsic functions.
Intrinsic::ID getIntrinsicID() const
Return the intrinsic ID of this intrinsic.
This is an important class for using LLVM in a threaded context.
An instruction for reading from memory.
unsigned getPointerAddressSpace() const
Returns the address space of the pointer operand.
Analysis pass that exposes the LoopInfo for a function.
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
The legacy pass manager's analysis pass to compute loop information.
Represents a single loop in the control flow graph.
MDNode * createBranchWeights(uint32_t TrueWeight, uint32_t FalseWeight, bool IsExpected=false)
Return metadata containing two branch weights.
TypeSize getSizeInBits() const
Returns the size of the specified MVT in bits.
static MVT getIntegerVT(unsigned BitWidth)
void replacePhiUsesWith(MachineBasicBlock *Old, MachineBasicBlock *New)
Update all phi nodes in this basic block to refer to basic block New instead of basic block Old.
This class implements a map that also provides access to all stored values in a deterministic order.
VectorType::iterator erase(typename VectorType::iterator Iterator)
Remove the element given by Iterator.
iterator find(const KeyT &Key)
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
This is the common base class for memset/memcpy/memmove.
This class wraps the llvm.memcpy/memmove intrinsics.
An analysis over an "inner" IR unit that provides access to an analysis manager over a "outer" IR uni...
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
op_range incoming_values()
Value * getIncomingValueForBlock(const BasicBlock *BB) const
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
unsigned getNumIncomingValues() const
Return the number of incoming edges.
static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr="", InsertPosition InsertBefore=nullptr)
Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
virtual void getAnalysisUsage(AnalysisUsage &) const
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
virtual StringRef getPassName() const
getPassName - Return a nice clean name for a pass.
PointerIntPair - This class implements a pair of a pointer and small integer.
static PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
A set of analyses that are preserved following a run of a transformation pass.
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
void preserve()
Mark an analysis as preserved.
An analysis pass based on the new PM to deliver ProfileSummaryInfo.
An analysis pass based on legacy pass manager to deliver ProfileSummaryInfo.
Analysis providing profile information.
Return a value (possibly void), from a function.
Value * getReturnValue() const
Convenience accessor. Returns null if there is no return value.
Unlike LLVM values, Selection DAG nodes may return multiple values as the result of a computation.
This class represents the LLVM 'select' instruction.
static SelectInst * Create(Value *C, Value *S1, Value *S2, const Twine &NameStr="", InsertPosition InsertBefore=nullptr, Instruction *MDFrom=nullptr)
A vector that has set insertion semantics.
size_type count(const key_type &key) const
Count the number of elements of a given key in the SetVector.
bool empty() const
Determine if the SetVector is empty or not.
bool insert(const value_type &X)
Insert a new element into the SetVector.
value_type pop_back_val()
This instruction constructs a fixed permutation of two input vectors.
VectorType * getType() const
Overload to return most specific vector type.
Implements a dense probed hash-table based set with some number of buckets stored inline.
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
bool erase(PtrType Ptr)
Remove pointer from the set.
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
A SetVector that performs no allocations if smaller than a certain size.
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
size_type count(const T &V) const
count - Return 1 if the element is in the set, 0 otherwise.
bool contains(const T &V) const
Check if the SmallSet contains the given element.
std::pair< const_iterator, bool > insert(const T &V)
insert - Insert an element into the set if it isn't already there.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
reference emplace_back(ArgTypes &&... Args)
void reserve(size_type N)
iterator erase(const_iterator CI)
typename SuperClass::iterator iterator
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
An instruction for storing to memory.
static unsigned getPointerOperandIndex()
StringRef - Represent a constant reference to a string, i.e.
Used to lazily calculate structure layout information for a target machine, based on the DataLayout s...
TypeSize getElementOffset(unsigned Idx) const
Class to represent struct types.
Analysis pass providing the TargetTransformInfo.
Analysis pass providing the TargetLibraryInfo.
Provides information about what library functions are available for the current target.
bool getLibFunc(StringRef funcName, LibFunc &F) const
Searches for a particular function name.
int InstructionOpcodeToISD(unsigned Opcode) const
Get the ISD node that corresponds to the Instruction class opcode.
virtual bool isVectorShiftByScalarCheap(Type *Ty) const
Return true if it's significantly cheaper to shift a vector by a uniform scalar than by an amount whi...
EVT getValueType(const DataLayout &DL, Type *Ty, bool AllowUnknown=false) const
Return the EVT corresponding to this LLVM type.
virtual bool isSelectSupported(SelectSupportKind) const
virtual bool isEqualityCmpFoldedWithSignedCmp() const
Return true if instruction generated for equality comparison is folded with instruction generated for...
virtual bool shouldFormOverflowOp(unsigned Opcode, EVT VT, bool MathUsed) const
Try to convert math with an overflow comparison into the corresponding DAG node operation.
virtual bool isMaskAndCmp0FoldingBeneficial(const Instruction &AndI) const
Return if the target supports combining a chain like:
bool isExtLoad(const LoadInst *Load, const Instruction *Ext, const DataLayout &DL) const
Return true if Load and Ext can form an ExtLoad.
virtual bool isSExtCheaperThanZExt(EVT FromTy, EVT ToTy) const
Return true if sign-extension from FromTy to ToTy is cheaper than zero-extension.
const TargetMachine & getTargetMachine() const
virtual bool isZExtFree(Type *FromTy, Type *ToTy) const
Return true if any actual instruction that defines a value of type FromTy implicitly zero-extends the...
bool enableExtLdPromotion() const
Return true if the target wants to use the optimization that turns ext(promotableInst1(....
virtual bool isCheapToSpeculateCttz(Type *Ty) const
Return true if it is cheap to speculate a call to intrinsic cttz.
bool isJumpExpensive() const
Return true if Flow Control is an expensive operation that should be avoided.
bool hasExtractBitsInsn() const
Return true if the target has BitExtract instructions.
SelectSupportKind
Enum that describes what type of support for selects the target has.
virtual bool allowsMisalignedMemoryAccesses(EVT, unsigned AddrSpace=0, Align Alignment=Align(1), MachineMemOperand::Flags Flags=MachineMemOperand::MONone, unsigned *=nullptr) const
Determine if the target supports unaligned memory accesses.
bool isSlowDivBypassed() const
Returns true if target has indicated at least one type should be bypassed.
virtual bool isTruncateFree(Type *FromTy, Type *ToTy) const
Return true if it's free to truncate a value of type FromTy to type ToTy.
virtual EVT getTypeToTransformTo(LLVMContext &Context, EVT VT) const
For types supported by the target, this is an identity function.
virtual MVT getPreferredSwitchConditionType(LLVMContext &Context, EVT ConditionVT) const
Returns preferred type for switch condition.
bool isCondCodeLegal(ISD::CondCode CC, MVT VT) const
Return true if the specified condition code is legal on this target.
virtual bool canCombineStoreAndExtract(Type *VectorTy, Value *Idx, unsigned &Cost) const
Return true if the target can combine store(extractelement VectorTy, Idx).
bool isTypeLegal(EVT VT) const
Return true if the target has native support for the specified value type.
virtual bool isFreeAddrSpaceCast(unsigned SrcAS, unsigned DestAS) const
Returns true if a cast from SrcAS to DestAS is "cheap", such that e.g.
virtual bool shouldConsiderGEPOffsetSplit() const
bool hasMultipleConditionRegisters() const
Return true if multiple condition registers are available.
bool isExtFree(const Instruction *I) const
Return true if the extension represented by I is free.
virtual bool getAddrModeArguments(IntrinsicInst *, SmallVectorImpl< Value * > &, Type *&) const
CodeGenPrepare sinks address calculations into the same BB as Load/Store instructions reading the add...
bool isOperationLegalOrCustom(unsigned Op, EVT VT, bool LegalOnly=false) const
Return true if the specified operation is legal on this target or can be made legal with custom lower...
bool isPredictableSelectExpensive() const
Return true if selects are only cheaper than branches if the branch is unlikely to be predicted right...
virtual bool isMultiStoresCheaperThanBitsMerge(EVT LTy, EVT HTy) const
Return true if it is cheaper to split the store of a merged int val from a pair of smaller values int...
bool isLoadExtLegal(unsigned ExtType, EVT ValVT, EVT MemVT) const
Return true if the specified load with extension is legal on this target.
const DenseMap< unsigned int, unsigned int > & getBypassSlowDivWidths() const
Returns map of slow types for division or remainder with corresponding fast types.
virtual bool isCheapToSpeculateCtlz(Type *Ty) const
Return true if it is cheap to speculate a call to intrinsic ctlz.
virtual bool useSoftFloat() const
virtual int64_t getPreferredLargeGEPBaseOffset(int64_t MinOffset, int64_t MaxOffset) const
Return the prefered common base offset.
LegalizeTypeAction getTypeAction(LLVMContext &Context, EVT VT) const
Return how we should legalize values of this type, either it is already legal (return 'Legal') or we ...
virtual bool shouldAlignPointerArgs(CallInst *, unsigned &, Align &) const
Return true if the pointer arguments to CI should be aligned by aligning the object whose address is ...
virtual Type * shouldConvertSplatType(ShuffleVectorInst *SVI) const
Given a shuffle vector SVI representing a vector splat, return a new scalar type of size equal to SVI...
virtual bool addressingModeSupportsTLS(const GlobalValue &) const
Returns true if the targets addressing mode can target thread local storage (TLS).
virtual bool shouldConvertPhiType(Type *From, Type *To) const
Given a set in interconnected phis of type 'From' that are loaded/stored or bitcast to type 'To',...
virtual bool isFAbsFree(EVT VT) const
Return true if an fabs operation is free to the point where it is never worthwhile to replace it with...
virtual bool preferZeroCompareBranch() const
Return true if the heuristic to prefer icmp eq zero should be used in code gen prepare.
virtual bool shouldSinkOperands(Instruction *I, SmallVectorImpl< Use * > &Ops) const
Return true if sinking I's operands to the same basic block as I is profitable, e....
virtual bool isLegalAddressingMode(const DataLayout &DL, const AddrMode &AM, Type *Ty, unsigned AddrSpace, Instruction *I=nullptr) const
Return true if the addressing mode represented by AM is legal for this target, for a load/store of th...
virtual bool optimizeExtendOrTruncateConversion(Instruction *I, Loop *L, const TargetTransformInfo &TTI) const
Try to optimize extending or truncating conversion instructions (like zext, trunc,...
This class defines information used to lower LLVM code to legal SelectionDAG operators that the targe...
std::vector< AsmOperandInfo > AsmOperandInfoVector
virtual bool ExpandInlineAsm(CallInst *) const
This hook allows the target to expand an inline asm call to be explicit llvm code if it wants to.
virtual AsmOperandInfoVector ParseConstraints(const DataLayout &DL, const TargetRegisterInfo *TRI, const CallBase &Call) const
Split up the constraint string from the inline assembly value into the specific constraints and their...
virtual void ComputeConstraintToUse(AsmOperandInfo &OpInfo, SDValue Op, SelectionDAG *DAG=nullptr) const
Determines the constraint code and constraint type to use for the specific AsmOperandInfo,...
virtual bool mayBeEmittedAsTailCall(const CallInst *) const
Return true if the target may be able emit the call instruction as a tail call.
Primary interface to the complete machine description for the target machine.
virtual bool isNoopAddrSpaceCast(unsigned SrcAS, unsigned DestAS) const
Returns true if a cast between SrcAS and DestAS is a noop.
Target-Independent Code Generator Pass Configuration Options.
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
TargetSubtargetInfo - Generic base class for all target subtargets.
virtual const TargetRegisterInfo * getRegisterInfo() const
getRegisterInfo - If register information is available, return it.
virtual const TargetLowering * getTargetLowering() const
virtual bool addrSinkUsingGEPs() const
Sink addresses into blocks using GEP instructions rather than pointer casts and arithmetic.
This class represents a truncation of integer types.
The instances of the Type class are immutable: once they are created, they are never changed.
unsigned getIntegerBitWidth() const
bool isVectorTy() const
True if this is an instance of VectorType.
unsigned getPointerAddressSpace() const
Get the address space of this pointer or pointer vector type.
static IntegerType * getIntNTy(LLVMContext &C, unsigned N)
unsigned getScalarSizeInBits() const LLVM_READONLY
If this is a vector type, return the getPrimitiveSizeInBits value for the element type.
bool isScalableTy() const
Return true if this is a type whose size is a known multiple of vscale.
bool isIntOrPtrTy() const
Return true if this is an integer type or a pointer type.
static IntegerType * getInt32Ty(LLVMContext &C)
bool isIntegerTy() const
True if this is an instance of IntegerType.
Type * getScalarType() const
If this is a vector type, return the element type, otherwise return 'this'.
'undef' values are things that do not have specified contents.
static UndefValue * get(Type *T)
Static factory methods - Return an 'undef' object of the specified type.
A Use represents the edge between a Value definition and its users.
bool replaceUsesOfWith(Value *From, Value *To)
Replace uses of one Value with another.
const Use & getOperandUse(unsigned i) const
void setOperand(unsigned i, Value *Val)
Value * getOperand(unsigned i) const
unsigned getNumOperands() const
LLVM Value Representation.
Type * getType() const
All values are typed, get the type of this value.
const Value * stripAndAccumulateInBoundsConstantOffsets(const DataLayout &DL, APInt &Offset) const
This is a wrapper around stripAndAccumulateConstantOffsets with the in-bounds requirement set to fals...
user_iterator user_begin()
void setName(const Twine &Name)
Change the name of the value.
bool hasOneUse() const
Return true if there is exactly one use of this value.
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
iterator_range< user_iterator > users()
Align getPointerAlignment(const DataLayout &DL) const
Returns an alignment of the pointer value.
bool isUsedInBasicBlock(const BasicBlock *BB) const
Check if this value is used in the specified basic block.
bool hasNUsesOrMore(unsigned N) const
Return true if this value has N uses or more.
const Value * stripPointerCasts() const
Strip off pointer casts, all-zero GEPs and address space casts.
LLVMContext & getContext() const
All values hold a context through their type.
unsigned getNumUses() const
This method computes the number of uses of this Value.
iterator_range< use_iterator > uses()
void mutateType(Type *Ty)
Mutate the type of this Value to be of the specified type.
user_iterator_impl< User > user_iterator
StringRef getName() const
Return a constant reference to the value's name.
void takeName(Value *V)
Transfer the name from V to this value.
void dump() const
Support for debugging, callable in GDB: V->dump()
Value handle that is nullable, but tries to track the Value.
bool pointsToAliveValue() const
This class represents zero extension of integer types.
constexpr ScalarTy getFixedValue() const
constexpr bool isNonZero() const
constexpr bool isScalable() const
Returns whether the quantity is scaled by a runtime quantity (vscale).
StructType * getStructTypeOrNull() const
TypeSize getSequentialElementStride(const DataLayout &DL) const
const ParentTy * getParent() const
self_iterator getIterator()
NodeTy * getNextNode()
Get the next node, or nullptr for the list tail.
This class implements an extremely fast bulk output stream that can only output to a stream.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
@ C
The default llvm calling convention, compatible with C.
unsigned getAddrMode(MCInstrInfo const &MCII, MCInst const &MCI)
cst_pred_ty< is_all_ones > m_AllOnes()
Match an integer or vector with all bits set.
BinaryOp_match< LHS, RHS, Instruction::Add > m_Add(const LHS &L, const RHS &R)
class_match< BinaryOperator > m_BinOp()
Match an arbitrary binary operation and ignore it.
BinaryOp_match< LHS, RHS, Instruction::URem > m_URem(const LHS &L, const RHS &R)
class_match< Constant > m_Constant()
Match an arbitrary Constant and ignore it.
specific_intval< false > m_SpecificInt(const APInt &V)
Match a specific integer value or vector with all elements equal to the value.
bool match(Val *V, const Pattern &P)
bind_ty< Instruction > m_Instruction(Instruction *&I)
Match an instruction, capturing it if we match.
specificval_ty m_Specific(const Value *V)
Match if we have a specific specified value.
BinOpPred_match< LHS, RHS, is_right_shift_op > m_Shr(const LHS &L, const RHS &R)
Matches logical shift operations.
OverflowingBinaryOp_match< LHS, RHS, Instruction::Add, OverflowingBinaryOperator::NoUnsignedWrap, true > m_c_NUWAdd(const LHS &L, const RHS &R)
class_match< ConstantInt > m_ConstantInt()
Match an arbitrary ConstantInt and ignore it.
cst_pred_ty< is_one > m_One()
Match an integer 1 or a vector with all elements equal to 1.
ThreeOps_match< Cond, LHS, RHS, Instruction::Select > m_Select(const Cond &C, const LHS &L, const RHS &R)
Matches SelectInst.
cst_pred_ty< is_zero_int > m_ZeroInt()
Match an integer 0 or a vector with all elements equal to 0.
CmpClass_match< LHS, RHS, ICmpInst, ICmpInst::Predicate > m_ICmp(ICmpInst::Predicate &Pred, const LHS &L, const RHS &R)
OneUse_match< T > m_OneUse(const T &SubPattern)
auto m_LogicalOr()
Matches L || R where L and R are arbitrary values.
TwoOps_match< V1_t, V2_t, Instruction::ShuffleVector > m_Shuffle(const V1_t &v1, const V2_t &v2)
Matches ShuffleVectorInst independently of mask value.
match_combine_and< class_match< Constant >, match_unless< constantexpr_match > > m_ImmConstant()
Match an arbitrary immediate Constant and ignore it.
CastInst_match< OpTy, ZExtInst > m_ZExt(const OpTy &Op)
Matches ZExt.
class_match< CmpInst > m_Cmp()
Matches any compare instruction and ignore it.
brc_match< Cond_t, bind_ty< BasicBlock >, bind_ty< BasicBlock > > m_Br(const Cond_t &C, BasicBlock *&T, BasicBlock *&F)
apint_match m_APInt(const APInt *&Res)
Match a ConstantInt or splatted ConstantVector, binding the specified pointer to the contained APInt.
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
BinaryOp_match< LHS, RHS, Instruction::Shl > m_Shl(const LHS &L, const RHS &R)
UAddWithOverflow_match< LHS_t, RHS_t, Sum_t > m_UAddWithOverflow(const LHS_t &L, const RHS_t &R, const Sum_t &S)
Match an icmp instruction checking for unsigned overflow on addition.
auto m_LogicalAnd()
Matches L && R where L and R are arbitrary values.
auto m_Undef()
Match an arbitrary undef constant.
BinaryOp_match< LHS, RHS, Instruction::Or, true > m_c_Or(const LHS &L, const RHS &R)
Matches an Or with LHS and RHS in either order.
ThreeOps_match< Val_t, Elt_t, Idx_t, Instruction::InsertElement > m_InsertElt(const Val_t &Val, const Elt_t &Elt, const Idx_t &Idx)
Matches InsertElementInst.
BinaryOp_match< LHS, RHS, Instruction::Sub > m_Sub(const LHS &L, const RHS &R)
match_combine_or< LTy, RTy > m_CombineOr(const LTy &L, const RTy &R)
Combine two pattern matchers matching L || R.
int compare(DigitsT LDigits, int16_t LScale, DigitsT RDigits, int16_t RScale)
Compare two scaled numbers.
ManagedStatic< cl::opt< FnT >, OptCreatorT > Action
@ CE
Windows NT (Windows on ARM)
initializer< Ty > init(const Ty &Val)
PointerTypeMap run(const Module &M)
Compute the PointerTypeMap for the module M.
NodeAddr< PhiNode * > Phi
const_iterator begin(StringRef path, Style style=Style::native)
Get begin iterator over path.
const_iterator end(StringRef path)
Get end iterator over path.
This is an optimization pass for GlobalISel generic memory operations.
auto drop_begin(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the first N elements excluded.
pred_iterator pred_end(BasicBlock *BB)
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
bool RemoveRedundantDbgInstrs(BasicBlock *BB)
Try to remove redundant dbg.value instructions from given basic block.
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
int popcount(T Value) noexcept
Count the number of set bits in a value.
auto size(R &&Range, std::enable_if_t< std::is_base_of< std::random_access_iterator_tag, typename std::iterator_traits< decltype(Range.begin())>::iterator_category >::value, void > *=nullptr)
Get the size of a range.
bool RecursivelyDeleteTriviallyDeadInstructions(Value *V, const TargetLibraryInfo *TLI=nullptr, MemorySSAUpdater *MSSAU=nullptr, std::function< void(Value *)> AboutToDeleteCallback=std::function< void(Value *)>())
If the specified value is a trivially dead instruction, delete it.
bool ConstantFoldTerminator(BasicBlock *BB, bool DeleteDeadConditions=false, const TargetLibraryInfo *TLI=nullptr, DomTreeUpdater *DTU=nullptr)
If a terminator instruction is predicated on a constant value, convert it into an unconditional branc...
APInt operator*(APInt a, uint64_t RHS)
bool isAligned(Align Lhs, uint64_t SizeInBytes)
Checks that SizeInBytes is a multiple of the alignment.
void salvageDebugInfo(const MachineRegisterInfo &MRI, MachineInstr &MI)
Assuming the instruction MI is going to be deleted, attempt to salvage debug users of MI by writing t...
auto successors(const MachineBasicBlock *BB)
ReturnInst * FoldReturnIntoUncondBranch(ReturnInst *RI, BasicBlock *BB, BasicBlock *Pred, DomTreeUpdater *DTU=nullptr)
This method duplicates the specified return instruction into a predecessor which ends in an unconditi...
bool operator!=(uint64_t V1, const APInt &V2)
Instruction * SplitBlockAndInsertIfElse(Value *Cond, BasicBlock::iterator SplitBefore, bool Unreachable, MDNode *BranchWeights=nullptr, DomTreeUpdater *DTU=nullptr, LoopInfo *LI=nullptr, BasicBlock *ElseBlock=nullptr)
Similar to SplitBlockAndInsertIfThen, but the inserted block is on the false path of the branch.
void append_range(Container &C, Range &&R)
Wrapper function to append range R to container C.
bool shouldOptimizeForSize(const MachineFunction *MF, ProfileSummaryInfo *PSI, const MachineBlockFrequencyInfo *BFI, PGSOQueryType QueryType=PGSOQueryType::Other)
Returns true if machine function MF is suggested to be size-optimized based on the profile.
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
void DeleteDeadBlock(BasicBlock *BB, DomTreeUpdater *DTU=nullptr, bool KeepOneInputPHIs=false)
Delete the specified block, which must have no predecessors.
auto unique(Range &&R, Predicate P)
Value * getSplatValue(const Value *V)
Get splat value if the input is a splat vector or return nullptr.
void initializeCodeGenPrepareLegacyPassPass(PassRegistry &)
bool hasBranchWeightOrigin(const Instruction &I)
Check if Branch Weight Metadata has an "expected" field from an llvm.expect* intrinsic.
void findDbgValues(SmallVectorImpl< DbgValueInst * > &DbgValues, Value *V, SmallVectorImpl< DbgVariableRecord * > *DbgVariableRecords=nullptr)
Finds the llvm.dbg.value intrinsics describing a value.
bool operator==(const AddressRangeValuePair &LHS, const AddressRangeValuePair &RHS)
bool SplitIndirectBrCriticalEdges(Function &F, bool IgnoreBlocksWithoutPHI, BranchProbabilityInfo *BPI=nullptr, BlockFrequencyInfo *BFI=nullptr)
Printable print(const GCNRegPressure &RP, const GCNSubtarget *ST=nullptr)
Value * simplifyInstruction(Instruction *I, const SimplifyQuery &Q)
See if we can compute a simplified version of this instruction.
Align getKnownAlignment(Value *V, const DataLayout &DL, const Instruction *CxtI=nullptr, AssumptionCache *AC=nullptr, const DominatorTree *DT=nullptr)
Try to infer an alignment for the specified pointer.
void erase(Container &C, ValueType V)
Wrapper function to remove a value from a container:
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
bool isSplatValue(const Value *V, int Index=-1, unsigned Depth=0)
Return true if each element of the vector value V is poisoned or equal to every other non-poisoned el...
pred_iterator pred_begin(BasicBlock *BB)
bool DeleteDeadPHIs(BasicBlock *BB, const TargetLibraryInfo *TLI=nullptr, MemorySSAUpdater *MSSAU=nullptr)
Examine each PHI in the given block and delete it if it is dead.
bool replaceAndRecursivelySimplify(Instruction *I, Value *SimpleV, const TargetLibraryInfo *TLI=nullptr, const DominatorTree *DT=nullptr, AssumptionCache *AC=nullptr, SmallSetVector< Instruction *, 8 > *UnsimplifiedUsers=nullptr)
Replace all uses of 'I' with 'SimpleV' and simplify the uses recursively.
auto reverse(ContainerTy &&C)
bool recognizeBSwapOrBitReverseIdiom(Instruction *I, bool MatchBSwaps, bool MatchBitReversals, SmallVectorImpl< Instruction * > &InsertedInsts)
Try to match a bswap or bitreverse idiom.
void sort(IteratorTy Start, IteratorTy End)
FPClassTest
Floating-point class tests, supported by 'is_fpclass' intrinsic.
void SplitBlockAndInsertIfThenElse(Value *Cond, BasicBlock::iterator SplitBefore, Instruction **ThenTerm, Instruction **ElseTerm, MDNode *BranchWeights=nullptr, DomTreeUpdater *DTU=nullptr, LoopInfo *LI=nullptr)
SplitBlockAndInsertIfThenElse is similar to SplitBlockAndInsertIfThen, but also creates the ElseBlock...
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
bool none_of(R &&Range, UnaryPredicate P)
Provide wrappers to std::none_of which take ranges instead of having to pass begin/end explicitly.
bool isSafeToSpeculativelyExecute(const Instruction *I, const Instruction *CtxI=nullptr, AssumptionCache *AC=nullptr, const DominatorTree *DT=nullptr, const TargetLibraryInfo *TLI=nullptr, bool UseVariableInfo=true)
Return true if the instruction does not have any effects besides calculating the result and does not ...
FunctionPass * createCodeGenPrepareLegacyPass()
createCodeGenPrepareLegacyPass - Transform the code to expose more pattern matching during instructio...
ISD::CondCode getFCmpCondCode(FCmpInst::Predicate Pred)
getFCmpCondCode - Return the ISD condition code corresponding to the given LLVM IR floating-point con...
bool VerifyLoopInfo
Enable verification of loop info.
bool isKnownNonZero(const Value *V, const SimplifyQuery &Q, unsigned Depth=0)
Return true if the given value is known to be non-zero when defined.
@ First
Helpers to iterate all locations in the MemoryEffectsBase class.
bool attributesPermitTailCall(const Function *F, const Instruction *I, const ReturnInst *Ret, const TargetLoweringBase &TLI, bool *AllowDifferingSizes=nullptr)
Test if given that the input instruction is in the tail call position, if there is an attribute misma...
bool MergeBlockIntoPredecessor(BasicBlock *BB, DomTreeUpdater *DTU=nullptr, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, MemoryDependenceResults *MemDep=nullptr, bool PredecessorWithTwoSuccessors=false, DominatorTree *DT=nullptr)
Attempts to merge a block into its predecessor, if possible.
@ And
Bitwise or logical AND of integers.
auto count(R &&Range, const E &Element)
Wrapper function around std::count to count the number of times an element Element occurs in the give...
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
bool isGuaranteedNotToBeUndefOrPoison(const Value *V, AssumptionCache *AC=nullptr, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, unsigned Depth=0)
Return true if this function can prove that V does not have undef bits and is never poison.
constexpr unsigned BitWidth
bool extractBranchWeights(const MDNode *ProfileData, SmallVectorImpl< uint32_t > &Weights)
Extract branch weights from MD_prof metadata.
bool bypassSlowDivision(BasicBlock *BB, const DenseMap< unsigned int, unsigned int > &BypassWidth)
This optimization identifies DIV instructions in a BB that can be profitably bypassed and carried out...
gep_type_iterator gep_type_begin(const User *GEP)
void erase_if(Container &C, UnaryPredicate P)
Provide a container algorithm similar to C++ Library Fundamentals v2's erase_if which is equivalent t...
std::pair< Value *, FPClassTest > fcmpToClassTest(CmpInst::Predicate Pred, const Function &F, Value *LHS, Value *RHS, bool LookThroughSrc=true)
Returns a pair of values, which if passed to llvm.is.fpclass, returns the same result as an fcmp with...
auto predecessors(const MachineBasicBlock *BB)
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
Align commonAlignment(Align A, uint64_t Offset)
Returns the alignment that satisfies both alignments.
bool pred_empty(const BasicBlock *BB)
Instruction * SplitBlockAndInsertIfThen(Value *Cond, BasicBlock::iterator SplitBefore, bool Unreachable, MDNode *BranchWeights=nullptr, DomTreeUpdater *DTU=nullptr, LoopInfo *LI=nullptr, BasicBlock *ThenBlock=nullptr)
Split the containing block at the specified instruction - everything before SplitBefore stays in the ...
BasicBlock * SplitEdge(BasicBlock *From, BasicBlock *To, DominatorTree *DT=nullptr, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, const Twine &BBName="")
Split the edge connecting the specified blocks, and return the newly created basic block between From...
static auto filterDbgVars(iterator_range< simple_ilist< DbgRecord >::iterator > R)
Filter the DbgRecord range to DbgVariableRecord types only and downcast.
Value * simplifyURemInst(Value *LHS, Value *RHS, const SimplifyQuery &Q)
Given operands for a URem, fold the result or return null.
CGPassBuilderOption getCGPassBuilderOption()
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
This struct is a compact representation of a valid (non-zero power of two) alignment.
bool bitsGT(EVT VT) const
Return true if this has more bits than VT.
bool bitsLT(EVT VT) const
Return true if this has less bits than VT.
TypeSize getSizeInBits() const
Return the size of the specified value type in bits.
static EVT getEVT(Type *Ty, bool HandleUnknown=false)
Return the value type corresponding to the specified type.
MVT getSimpleVT() const
Return the SimpleValueType held in the specified simple EVT.
bool isRound() const
Return true if the size is a power-of-two number of bytes.
bool isInteger() const
Return true if this is an integer or a vector integer type.
Used to describe addressing mode similar to ExtAddrMode in CodeGenPrepare.
This struct is a compact representation of a valid (power of two) or undefined (0) alignment.
This represents an addressing mode of: BaseGV + BaseOffs + BaseReg + Scale*ScaleReg + ScalableOffset*...
This contains information for each constraint that we are lowering.