44#include "llvm/Config/llvm-config.h"
65#include "llvm/IR/IntrinsicsAArch64.h"
109#define DEBUG_TYPE "codegenprepare"
112STATISTIC(NumPHIsElim,
"Number of trivial PHIs eliminated");
113STATISTIC(NumGEPsElim,
"Number of GEPs converted to casts");
114STATISTIC(NumCmpUses,
"Number of uses of Cmp expressions replaced with uses of "
116STATISTIC(NumCastUses,
"Number of uses of Cast expressions replaced with uses "
118STATISTIC(NumMemoryInsts,
"Number of memory instructions whose address "
119 "computations were sunk");
121 "Number of phis created when address "
122 "computations were sunk to memory instructions");
124 "Number of select created when address "
125 "computations were sunk to memory instructions");
126STATISTIC(NumExtsMoved,
"Number of [s|z]ext instructions combined with loads");
127STATISTIC(NumExtUses,
"Number of uses of [s|z]ext instructions optimized");
129 "Number of and mask instructions added to form ext loads");
130STATISTIC(NumAndUses,
"Number of uses of and mask instructions optimized");
131STATISTIC(NumRetsDup,
"Number of return instructions duplicated");
132STATISTIC(NumDbgValueMoved,
"Number of debug value instructions moved");
133STATISTIC(NumSelectsExpanded,
"Number of selects turned into branches");
134STATISTIC(NumStoreExtractExposed,
"Number of store(extractelement) exposed");
138 cl::desc(
"Disable branch optimizations in CodeGenPrepare"));
142 cl::desc(
"Disable GC optimizations in CodeGenPrepare"));
147 cl::desc(
"Disable select to branch conversion."));
151 cl::desc(
"Address sinking in CGP using GEPs."));
155 cl::desc(
"Enable sinking and/cmp into branches."));
159 cl::desc(
"Disable store(extract) optimizations in CodeGenPrepare"));
163 cl::desc(
"Stress test store(extract) optimizations in CodeGenPrepare"));
167 cl::desc(
"Disable ext(promotable(ld)) -> promoted(ext(ld)) optimization in "
172 cl::desc(
"Stress test ext(promotable(ld)) -> promoted(ext(ld)) "
173 "optimization in CodeGenPrepare"));
177 cl::desc(
"Disable protection against removing loop preheaders"));
181 cl::desc(
"Use profile info to add section prefix for hot/cold functions"));
184 "profile-unknown-in-special-section",
cl::Hidden,
185 cl::desc(
"In profiling mode like sampleFDO, if a function doesn't have "
186 "profile, we cannot tell the function is cold for sure because "
187 "it may be a function newly added without ever being sampled. "
188 "With the flag enabled, compiler can put such profile unknown "
189 "functions into a special section, so runtime system can choose "
190 "to handle it in a different way than .text section, to save "
191 "RAM for example. "));
195 cl::desc(
"Use the basic-block-sections profile to determine the text "
196 "section prefix for hot functions. Functions with "
197 "basic-block-sections profile will be placed in `.text.hot` "
198 "regardless of their FDO profile info. Other functions won't be "
199 "impacted, i.e., their prefixes will be decided by FDO/sampleFDO "
204 cl::desc(
"Skip merging empty blocks if (frequency of empty block) / "
205 "(frequency of destination block) is greater than this ratio"));
209 cl::desc(
"Force store splitting no matter what the target query says."));
213 cl::desc(
"Enable merging of redundant sexts when one is dominating"
219 cl::desc(
"Disables combining addressing modes with different parts "
220 "in optimizeMemoryInst."));
224 cl::desc(
"Allow creation of Phis in Address sinking."));
228 cl::desc(
"Allow creation of selects in Address sinking."));
232 cl::desc(
"Allow combining of BaseReg field in Address sinking."));
236 cl::desc(
"Allow combining of BaseGV field in Address sinking."));
240 cl::desc(
"Allow combining of BaseOffs field in Address sinking."));
244 cl::desc(
"Allow combining of ScaledReg field in Address sinking."));
249 cl::desc(
"Enable splitting large offset of GEP."));
253 cl::desc(
"Enable ICMP_EQ to ICMP_S(L|G)T conversion."));
257 cl::desc(
"Enable BFI update verification for "
262 cl::desc(
"Enable converting phi types in CodeGenPrepare"));
266 cl::desc(
"Least BB number of huge function."));
271 cl::desc(
"Max number of address users to look at"));
275 cl::desc(
"Disable elimination of dead PHI nodes."));
303class TypePromotionTransaction;
305class CodeGenPrepare {
306 friend class CodeGenPrepareLegacyPass;
315 std::unique_ptr<BlockFrequencyInfo>
BFI;
316 std::unique_ptr<BranchProbabilityInfo> BPI;
331 SetOfInstrs InsertedInsts;
335 InstrToOrigTy PromotedInsts;
338 SetOfInstrs RemovedInsts;
357 ValueToSExts ValToSExtendedUses;
367 std::unique_ptr<DominatorTree> DT;
373 bool IsHugeFunc =
false;
381 void releaseMemory() {
383 InsertedInsts.
clear();
384 PromotedInsts.clear();
393 template <
typename F>
394 void resetIteratorIfInvalidatedWhileCalling(
BasicBlock *BB,
F f) {
398 Value *CurValue = &*CurInstIterator;
405 if (IterHandle != CurValue) {
406 CurInstIterator = BB->
begin();
414 DT = std::make_unique<DominatorTree>(
F);
418 void removeAllAssertingVHReferences(
Value *V);
421 bool eliminateMostlyEmptyBlocks(
Function &
F);
424 void eliminateMostlyEmptyBlock(
BasicBlock *BB);
429 bool optimizeInst(
Instruction *
I, ModifyDT &ModifiedDT);
433 bool optimizeInlineAsmInst(
CallInst *CS);
437 bool optimizeLoadExt(
LoadInst *Load);
443 bool optimizeSwitchPhiConstants(
SwitchInst *SI);
445 bool optimizeExtractElementInst(
Instruction *Inst);
446 bool dupRetToEnableTailCallOpts(
BasicBlock *BB, ModifyDT &ModifiedDT);
454 bool tryToPromoteExts(TypePromotionTransaction &TPT,
457 unsigned CreatedInstsCost = 0);
459 bool splitLargeGEPOffsets();
463 bool performAddressTypePromotion(
464 Instruction *&Inst,
bool AllowPromotionWithoutCommonHeader,
465 bool HasPromoted, TypePromotionTransaction &TPT,
467 bool splitBranchCondition(
Function &
F, ModifyDT &ModifiedDT);
473 bool optimizeCmp(
CmpInst *Cmp, ModifyDT &ModifiedDT);
475 bool combineToUSubWithOverflow(
CmpInst *Cmp, ModifyDT &ModifiedDT);
476 bool combineToUAddWithOverflow(
CmpInst *Cmp, ModifyDT &ModifiedDT);
506char CodeGenPrepareLegacyPass::ID = 0;
508bool CodeGenPrepareLegacyPass::runOnFunction(
Function &
F) {
512 CodeGenPrepare CGP(TM);
513 CGP.DL = &
F.getDataLayout();
514 CGP.SubtargetInfo =
TM->getSubtargetImpl(
F);
515 CGP.TLI = CGP.SubtargetInfo->getTargetLowering();
516 CGP.TRI = CGP.SubtargetInfo->getRegisterInfo();
517 CGP.TLInfo = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(
F);
518 CGP.TTI = &getAnalysis<TargetTransformInfoWrapperPass>().getTTI(
F);
519 CGP.LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
522 CGP.PSI = &getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI();
524 getAnalysisIfAvailable<BasicBlockSectionsProfileReaderWrapperPass>();
525 CGP.BBSectionsProfileReader = BBSPRWP ? &BBSPRWP->getBBSPR() :
nullptr;
531 "Optimize for code generation",
false,
false)
542 return new CodeGenPrepareLegacyPass();
547 CodeGenPrepare CGP(TM);
549 bool Changed = CGP.run(
F, AM);
561 DL = &
F.getDataLayout();
562 SubtargetInfo = TM->getSubtargetImpl(
F);
572 BBSectionsProfileReader =
578 bool EverMadeChange =
false;
580 OptSize =
F.hasOptSize();
585 F.setSectionPrefix(
"hot");
590 if (
F.hasFnAttribute(Attribute::Hot) ||
591 PSI->isFunctionHotInCallGraph(&
F, *BFI))
592 F.setSectionPrefix(
"hot");
596 else if (PSI->isFunctionColdInCallGraph(&
F, *BFI) ||
597 F.hasFnAttribute(Attribute::Cold))
598 F.setSectionPrefix(
"unlikely");
600 PSI->isFunctionHotnessUnknown(
F))
601 F.setSectionPrefix(
"unknown");
610 while (BB !=
nullptr) {
623 EverMadeChange |= eliminateAssumptions(
F);
627 EverMadeChange |= eliminateMostlyEmptyBlocks(
F);
629 ModifyDT ModifiedDT = ModifyDT::NotModifyDT;
631 EverMadeChange |= splitBranchCondition(
F, ModifiedDT);
645 LI->analyze(getDT(
F));
647 bool MadeChange =
true;
648 bool FuncIterated =
false;
653 if (FuncIterated && !FreshBBs.
contains(&BB))
656 ModifyDT ModifiedDTOnIteration = ModifyDT::NotModifyDT;
659 if (ModifiedDTOnIteration == ModifyDT::ModifyBBDT)
662 MadeChange |= Changed;
675 else if (FuncIterated)
680 if (ModifiedDTOnIteration != ModifyDT::NotModifyDT)
685 FuncIterated = IsHugeFunc;
688 MadeChange |= mergeSExts(
F);
689 if (!LargeOffsetGEPMap.
empty())
690 MadeChange |= splitLargeGEPOffsets();
691 MadeChange |= optimizePhiTypes(
F);
694 eliminateFallThrough(
F, DT.get());
698 LI->verify(getDT(
F));
705 EverMadeChange |= MadeChange;
706 SeenChainsForSExt.
clear();
707 ValToSExtendedUses.clear();
708 RemovedInsts.clear();
709 LargeOffsetGEPMap.
clear();
710 LargeOffsetGEPID.
clear();
734 MadeChange |= !WorkList.
empty();
735 while (!WorkList.
empty()) {
748 if (EverMadeChange || MadeChange)
749 MadeChange |= eliminateFallThrough(
F);
751 EverMadeChange |= MadeChange;
758 if (
auto *SP = dyn_cast<GCStatepointInst>(&
I))
760 for (
auto &
I : Statepoints)
761 EverMadeChange |= simplifyOffsetableRelocate(*
I);
766 EverMadeChange |= placeDbgValues(
F);
767 EverMadeChange |= placePseudoProbes(
F);
774 return EverMadeChange;
777bool CodeGenPrepare::eliminateAssumptions(
Function &
F) {
778 bool MadeChange =
false;
780 CurInstIterator = BB.begin();
781 while (CurInstIterator != BB.end()) {
783 if (
auto *Assume = dyn_cast<AssumeInst>(
I)) {
786 Assume->eraseFromParent();
788 resetIteratorIfInvalidatedWhileCalling(&BB, [&]() {
799void CodeGenPrepare::removeAllAssertingVHReferences(
Value *V) {
800 LargeOffsetGEPMap.
erase(V);
801 NewGEPBases.
erase(V);
803 auto GEP = dyn_cast<GetElementPtrInst>(V);
809 auto VecI = LargeOffsetGEPMap.
find(
GEP->getPointerOperand());
810 if (VecI == LargeOffsetGEPMap.
end())
813 auto &GEPVector = VecI->second;
816 if (GEPVector.empty())
817 LargeOffsetGEPMap.
erase(VecI);
826 NewBFI.verifyMatch(*BFI);
833 bool Changed =
false;
843 auto *BB = cast_or_null<BasicBlock>(
Block);
851 if (!SinglePred || SinglePred == BB || BB->hasAddressTaken())
859 if (Term && !
Term->isConditional()) {
871 FreshBBs.
insert(SinglePred);
879 for (
const auto &Pred : Preds)
880 if (
auto *BB = cast_or_null<BasicBlock>(Pred))
896 if (BBI != BB->
begin()) {
898 while (isa<DbgInfoIntrinsic>(BBI)) {
899 if (BBI == BB->
begin())
903 if (!isa<DbgInfoIntrinsic>(BBI) && !isa<PHINode>(BBI))
912 if (!canMergeBlocks(BB, DestBB))
922bool CodeGenPrepare::eliminateMostlyEmptyBlocks(
Function &
F) {
925 while (!LoopList.empty()) {
926 Loop *
L = LoopList.pop_back_val();
929 Preheaders.
insert(Preheader);
932 bool MadeChange =
false;
948 BasicBlock *DestBB = findDestBlockOfMergeableEmptyBlock(BB);
950 !isMergingEmptyBlockProfitable(BB, DestBB, Preheaders.
count(BB)))
953 eliminateMostlyEmptyBlock(BB);
959bool CodeGenPrepare::isMergingEmptyBlockProfitable(
BasicBlock *BB,
975 if (isa<CallBrInst>(Pred->getTerminator()) &&
1007 if (!isa<PHINode>(DestBB->
begin()))
1015 if (DestBBPred == BB)
1019 return DestPN.getIncomingValueForBlock(BB) ==
1020 DestPN.getIncomingValueForBlock(DestBBPred);
1022 SameIncomingValueBBs.
insert(DestBBPred);
1028 if (SameIncomingValueBBs.
count(Pred))
1034 for (
auto *SameValueBB : SameIncomingValueBBs)
1035 if (SameValueBB->getUniquePredecessor() == Pred &&
1036 DestBB == findDestBlockOfMergeableEmptyBlock(SameValueBB))
1037 BBFreq +=
BFI->getBlockFreq(SameValueBB);
1040 return !Limit || PredFreq <= *Limit;
1046bool CodeGenPrepare::canMergeBlocks(
const BasicBlock *BB,
1054 if (UI->
getParent() != DestBB || !isa<PHINode>(UI))
1060 if (
const PHINode *UPN = dyn_cast<PHINode>(UI))
1061 for (
unsigned I = 0, E = UPN->getNumIncomingValues();
I != E; ++
I) {
1063 if (
Insn &&
Insn->getParent() == BB &&
1064 Insn->getParent() != UPN->getIncomingBlock(
I))
1074 const PHINode *DestBBPN = dyn_cast<PHINode>(DestBB->
begin());
1080 if (
const PHINode *BBPN = dyn_cast<PHINode>(BB->
begin())) {
1082 for (
unsigned i = 0, e = BBPN->getNumIncomingValues(); i != e; ++i)
1083 BBPreds.
insert(BBPN->getIncomingBlock(i));
1091 if (BBPreds.
count(Pred)) {
1093 const Value *V1 = PN.getIncomingValueForBlock(Pred);
1094 const Value *
V2 = PN.getIncomingValueForBlock(BB);
1097 if (
const PHINode *V2PN = dyn_cast<PHINode>(V2))
1098 if (V2PN->getParent() == BB)
1099 V2 = V2PN->getIncomingValueForBlock(Pred);
1115 auto *OldI = dyn_cast<Instruction>(Old);
1129void CodeGenPrepare::eliminateMostlyEmptyBlock(
BasicBlock *BB) {
1139 if (SinglePred != DestBB) {
1140 assert(SinglePred == BB &&
1141 "Single predecessor not the same as predecessor");
1150 FreshBBs.
insert(SinglePred);
1151 FreshBBs.
erase(DestBB);
1161 Value *InVal = PN.removeIncomingValue(BB,
false);
1165 PHINode *InValPhi = dyn_cast<PHINode>(InVal);
1166 if (InValPhi && InValPhi->
getParent() == BB) {
1175 for (
unsigned i = 0, e = BBPN->getNumIncomingValues(); i != e; ++i)
1176 PN.addIncoming(InVal, BBPN->getIncomingBlock(i));
1179 PN.addIncoming(InVal, Pred);
1209 for (
auto *ThisRelocate : AllRelocateCalls) {
1210 auto K = std::make_pair(ThisRelocate->getBasePtrIndex(),
1211 ThisRelocate->getDerivedPtrIndex());
1212 RelocateIdxMap.
insert(std::make_pair(K, ThisRelocate));
1214 for (
auto &Item : RelocateIdxMap) {
1215 std::pair<unsigned, unsigned> Key = Item.first;
1216 if (Key.first == Key.second)
1221 auto BaseKey = std::make_pair(Key.first, Key.first);
1224 auto MaybeBase = RelocateIdxMap.
find(BaseKey);
1225 if (MaybeBase == RelocateIdxMap.
end())
1230 RelocateInstMap[MaybeBase->second].push_back(
I);
1238 for (
unsigned i = 1; i <
GEP->getNumOperands(); i++) {
1240 auto *
Op = dyn_cast<ConstantInt>(
GEP->getOperand(i));
1241 if (!
Op ||
Op->getZExtValue() > 20)
1245 for (
unsigned i = 1; i <
GEP->getNumOperands(); i++)
1255 bool MadeChange =
false;
1262 for (
auto R = RelocatedBase->
getParent()->getFirstInsertionPt();
1263 &*R != RelocatedBase; ++R)
1264 if (
auto *RI = dyn_cast<GCRelocateInst>(R))
1267 RelocatedBase->
moveBefore(RI->getIterator());
1274 "Not relocating a derived object of the original base object");
1275 if (ToReplace->getBasePtrIndex() == ToReplace->getDerivedPtrIndex()) {
1280 if (RelocatedBase->
getParent() != ToReplace->getParent()) {
1289 auto *Derived = dyn_cast<GetElementPtrInst>(ToReplace->getDerivedPtr());
1290 if (!Derived || Derived->getPointerOperand() !=
Base)
1299 "Should always have one since it's not a terminator");
1327 Value *ActualRelocatedBase = RelocatedBase;
1328 if (RelocatedBase->
getType() !=
Base->getType()) {
1329 ActualRelocatedBase =
1332 Value *Replacement =
1333 Builder.
CreateGEP(Derived->getSourceElementType(), ActualRelocatedBase,
1339 Value *ActualReplacement = Replacement;
1340 if (Replacement->
getType() != ToReplace->getType()) {
1345 ToReplace->eraseFromParent();
1370 bool MadeChange =
false;
1372 for (
auto *U :
I.users())
1379 if (AllRelocateCalls.
size() < 2)
1386 if (RelocateInstMap.
empty())
1389 for (
auto &Item : RelocateInstMap)
1403 bool MadeChange =
false;
1406 Use &TheUse = UI.getUse();
1413 UserBB = PN->getIncomingBlock(TheUse);
1421 if (
User->isEHPad())
1431 if (UserBB == DefBB)
1435 CastInst *&InsertedCast = InsertedCasts[UserBB];
1437 if (!InsertedCast) {
1440 InsertedCast = cast<CastInst>(CI->
clone());
1445 TheUse = InsertedCast;
1469 if (
auto *ASC = dyn_cast<AddrSpaceCastInst>(CI)) {
1471 ASC->getDestAddressSpace()))
1511 match(IVInc, m_ExtractValue<0>(m_Intrinsic<Intrinsic::uadd_with_overflow>(
1515 match(IVInc, m_ExtractValue<0>(m_Intrinsic<Intrinsic::usub_with_overflow>(
1526static std::optional<std::pair<Instruction *, Constant *>>
1529 if (!L || L->getHeader() != PN->
getParent() || !L->getLoopLatch())
1530 return std::nullopt;
1533 if (!IVInc || LI->
getLoopFor(IVInc->getParent()) != L)
1534 return std::nullopt;
1538 return std::make_pair(IVInc, Step);
1539 return std::nullopt;
1543 auto *
I = dyn_cast<Instruction>(V);
1550 if (
auto *PN = dyn_cast<PHINode>(
LHS))
1552 return IVInc->first ==
I;
1556bool CodeGenPrepare::replaceMathCmpWithIntrinsic(
BinaryOperator *BO,
1564 assert(L &&
"L should not be null after isIVIncrement()");
1566 if (LI->getLoopFor(
Cmp->getParent()) != L)
1572 auto &DT = getDT(*BO->
getParent()->getParent());
1581 if (BO->
getParent() !=
Cmp->getParent() && !IsReplacableIVIncrement(BO)) {
1604 if (BO->
getOpcode() == Instruction::Add &&
1605 IID == Intrinsic::usub_with_overflow) {
1606 assert(isa<Constant>(Arg1) &&
"Unexpected input for usubo");
1615 if ((BO->
getOpcode() != Instruction::Xor && &Iter == BO) || &Iter == Cmp) {
1620 assert(InsertPt !=
nullptr &&
"Parent block did not contain cmp or binop");
1623 Value *MathOV = Builder.CreateBinaryIntrinsic(IID, Arg0, Arg1);
1624 if (BO->
getOpcode() != Instruction::Xor) {
1625 Value *Math = Builder.CreateExtractValue(MathOV, 0,
"math");
1629 "Patterns with XOr should use the BO only in the compare");
1630 Value *OV = Builder.CreateExtractValue(MathOV, 1,
"ov");
1632 Cmp->eraseFromParent();
1642 Value *
A = Cmp->getOperand(0), *
B = Cmp->getOperand(1);
1645 if (isa<Constant>(
A))
1650 B = ConstantInt::get(
B->getType(), 1);
1658 for (
User *U :
A->users()) {
1660 Add = cast<BinaryOperator>(U);
1669bool CodeGenPrepare::combineToUAddWithOverflow(
CmpInst *Cmp,
1670 ModifyDT &ModifiedDT) {
1671 bool EdgeCase =
false;
1678 A =
Add->getOperand(0);
1679 B =
Add->getOperand(1);
1685 Add->hasNUsesOrMore(EdgeCase ? 1 : 2)))
1691 if (
Add->getParent() !=
Cmp->getParent() && !
Add->hasOneUse())
1694 if (!replaceMathCmpWithIntrinsic(
Add,
A,
B, Cmp,
1695 Intrinsic::uadd_with_overflow))
1699 ModifiedDT = ModifyDT::ModifyInstDT;
1703bool CodeGenPrepare::combineToUSubWithOverflow(
CmpInst *Cmp,
1704 ModifyDT &ModifiedDT) {
1707 if (isa<Constant>(
A) && isa<Constant>(
B))
1718 B = ConstantInt::get(
B->getType(), 1);
1732 Value *CmpVariableOperand = isa<Constant>(
A) ?
B :
A;
1734 for (
User *U : CmpVariableOperand->
users()) {
1737 Sub = cast<BinaryOperator>(U);
1742 const APInt *CmpC, *AddC;
1745 Sub = cast<BinaryOperator>(U);
1758 Cmp, Intrinsic::usub_with_overflow))
1762 ModifiedDT = ModifyDT::ModifyInstDT;
1783 bool MadeChange =
false;
1786 Use &TheUse = UI.getUse();
1793 if (isa<PHINode>(
User))
1801 if (UserBB == DefBB)
1805 CmpInst *&InsertedCmp = InsertedCmps[UserBB];
1811 Cmp->getOperand(0), Cmp->getOperand(1),
"");
1818 TheUse = InsertedCmp;
1824 if (Cmp->use_empty()) {
1825 Cmp->eraseFromParent();
1862 for (
User *U : Cmp->users()) {
1863 if (isa<BranchInst>(U))
1865 if (isa<SelectInst>(U) && cast<SelectInst>(U)->getCondition() == Cmp)
1884 if (CmpBB != FalseBB)
1887 Value *CmpOp0 = Cmp->getOperand(0), *CmpOp1 = Cmp->getOperand(1);
1901 for (
User *U : Cmp->users()) {
1902 if (
auto *BI = dyn_cast<BranchInst>(U)) {
1907 if (
auto *SI = dyn_cast<SelectInst>(U)) {
1910 SI->swapProfMetadata();
1922 Value *Op0 = Cmp->getOperand(0);
1923 Value *Op1 = Cmp->getOperand(1);
1925 isa<Constant>(Op1) || Op0 == Op1)
1932 unsigned NumInspected = 0;
1935 if (++NumInspected > 128)
1943 if (GoodToSwap > 0) {
1944 Cmp->swapOperands();
1952 FCmpInst *FCmp = dyn_cast<FCmpInst>(Cmp);
1964 auto ShouldReverseTransform = [](
FPClassTest ClassTest) {
1967 auto [ClassVal, ClassTest] =
1973 if (!ShouldReverseTransform(ClassTest) && !ShouldReverseTransform(~ClassTest))
1978 Cmp->replaceAllUsesWith(IsFPClass);
1986 Value *Incr, *RemAmt;
1991 Value *AddInst, *AddOffset;
1993 auto *PN = dyn_cast<PHINode>(Incr);
1994 if (PN !=
nullptr) {
1996 AddOffset =
nullptr;
2004 PN = dyn_cast<PHINode>(V0);
2005 if (PN !=
nullptr) {
2008 PN = dyn_cast<PHINode>(V1);
2018 if (PN->getNumIncomingValues() != 2)
2023 if (!L || !L->getLoopPreheader() || !L->getLoopLatch())
2027 if (!L->contains(Rem))
2031 if (!L->isLoopInvariant(RemAmt))
2052 AddInstOut = AddInst;
2053 AddOffsetOut = AddOffset;
2072 Value *AddOffset, *RemAmt, *AddInst;
2075 AddOffset, LoopIncrPN))
2100 assert(AddOffset &&
"We found an add but missing values");
2130 NewRem->
addIncoming(Start, L->getLoopPreheader());
2135 FreshBBs.
insert(L->getLoopLatch());
2142 cast<Instruction>(AddInst)->eraseFromParent();
2146bool CodeGenPrepare::optimizeURem(
Instruction *Rem) {
2163 auto *
II = cast<IntrinsicInst>(Cmp->getOperand(0));
2167 Cmp->setOperand(1, ConstantInt::get(
II->getType(), 2));
2177bool CodeGenPrepare::optimizeCmp(
CmpInst *Cmp, ModifyDT &ModifiedDT) {
2181 if (combineToUAddWithOverflow(Cmp, ModifiedDT))
2184 if (combineToUSubWithOverflow(Cmp, ModifiedDT))
2208 SetOfInstrs &InsertedInsts) {
2211 assert(!InsertedInsts.count(AndI) &&
2212 "Attempting to optimize already optimized and instruction");
2213 (void)InsertedInsts;
2222 if (!isa<ConstantInt>(AndI->
getOperand(0)) &&
2227 for (
auto *U : AndI->
users()) {
2231 if (!isa<ICmpInst>(
User))
2235 if (!CmpC || !CmpC->
isZero())
2250 Use &TheUse = UI.getUse();
2268 TheUse = InsertedAnd;
2284 if (!isa<TruncInst>(
User)) {
2285 if (
User->getOpcode() != Instruction::And ||
2291 if ((Cimm & (Cimm + 1)).getBoolValue())
2304 auto *TruncI = cast<TruncInst>(
User);
2305 bool MadeChange =
false;
2308 TruncE = TruncI->user_end();
2309 TruncUI != TruncE;) {
2311 Use &TruncTheUse = TruncUI.getUse();
2312 Instruction *TruncUser = cast<Instruction>(*TruncUI);
2331 if (isa<PHINode>(TruncUser))
2336 if (UserBB == TruncUserBB)
2340 CastInst *&InsertedTrunc = InsertedTruncs[TruncUserBB];
2342 if (!InsertedShift && !InsertedTrunc) {
2346 if (ShiftI->
getOpcode() == Instruction::AShr)
2348 BinaryOperator::CreateAShr(ShiftI->
getOperand(0), CI,
"");
2351 BinaryOperator::CreateLShr(ShiftI->
getOperand(0), CI,
"");
2359 TruncInsertPt.setHeadBit(
true);
2360 assert(TruncInsertPt != TruncUserBB->
end());
2364 InsertedTrunc->
insertBefore(*TruncUserBB, TruncInsertPt);
2365 InsertedTrunc->
setDebugLoc(TruncI->getDebugLoc());
2369 TruncTheUse = InsertedTrunc;
2402 bool MadeChange =
false;
2405 Use &TheUse = UI.getUse();
2411 if (isa<PHINode>(
User))
2419 if (UserBB == DefBB) {
2434 if (isa<TruncInst>(
User) &&
2447 if (!InsertedShift) {
2451 if (ShiftI->
getOpcode() == Instruction::AShr)
2453 BinaryOperator::CreateAShr(ShiftI->
getOperand(0), CI,
"");
2456 BinaryOperator::CreateLShr(ShiftI->
getOperand(0), CI,
"");
2464 TheUse = InsertedShift;
2513 if (Ty->
isVectorTy() || SizeInBits >
DL->getLargestLegalIntTypeSizeInBits())
2525 FreshBBs.
insert(CallBlock);
2532 SplitPt.setHeadBit(
true);
2535 FreshBBs.
insert(EndBlock);
2540 L->addBasicBlockToLoop(CallBlock, LI);
2541 L->addBasicBlockToLoop(EndBlock, LI);
2572 ModifiedDT = ModifyDT::ModifyBBDT;
2576bool CodeGenPrepare::optimizeCallInst(
CallInst *CI, ModifyDT &ModifiedDT) {
2585 CurInstIterator = BB->
begin();
2592 if (optimizeInlineAsmInst(CI))
2601 for (
auto &Arg : CI->
args()) {
2606 if (!Arg->getType()->isPointerTy())
2609 cast<PointerType>(Arg->getType())->getAddressSpace()),
2616 if ((AI = dyn_cast<AllocaInst>(Val)) && AI->
getAlign() < PrefAlign &&
2635 if (!MIDestAlign || DestAlign > *MIDestAlign)
2636 MI->setDestAlignment(DestAlign);
2638 MaybeAlign MTISrcAlign = MTI->getSourceAlign();
2640 if (!MTISrcAlign || SrcAlign > *MTISrcAlign)
2641 MTI->setSourceAlignment(SrcAlign);
2651 for (
auto &Arg : CI->
args()) {
2652 if (!Arg->getType()->isPointerTy())
2654 unsigned AS = Arg->getType()->getPointerAddressSpace();
2655 if (optimizeMemoryInst(CI, Arg, Arg->getType(), AS))
2661 switch (
II->getIntrinsicID()) {
2664 case Intrinsic::assume:
2666 case Intrinsic::allow_runtime_check:
2667 case Intrinsic::allow_ubsan_check:
2668 case Intrinsic::experimental_widenable_condition: {
2672 if (
II->use_empty()) {
2673 II->eraseFromParent();
2677 resetIteratorIfInvalidatedWhileCalling(BB, [&]() {
2682 case Intrinsic::objectsize:
2684 case Intrinsic::is_constant:
2686 case Intrinsic::aarch64_stlxr:
2687 case Intrinsic::aarch64_stxr: {
2696 InsertedInsts.insert(ExtVal);
2700 case Intrinsic::launder_invariant_group:
2701 case Intrinsic::strip_invariant_group: {
2702 Value *ArgVal =
II->getArgOperand(0);
2703 auto it = LargeOffsetGEPMap.
find(
II);
2704 if (it != LargeOffsetGEPMap.
end()) {
2708 auto GEPs = std::move(it->second);
2709 LargeOffsetGEPMap[ArgVal].append(GEPs.begin(), GEPs.end());
2714 II->eraseFromParent();
2717 case Intrinsic::cttz:
2718 case Intrinsic::ctlz:
2722 case Intrinsic::fshl:
2723 case Intrinsic::fshr:
2724 return optimizeFunnelShift(
II);
2725 case Intrinsic::dbg_assign:
2726 case Intrinsic::dbg_value:
2727 return fixupDbgValue(
II);
2728 case Intrinsic::masked_gather:
2729 return optimizeGatherScatterInst(
II,
II->getArgOperand(0));
2730 case Intrinsic::masked_scatter:
2731 return optimizeGatherScatterInst(
II,
II->getArgOperand(1));
2737 while (!PtrOps.
empty()) {
2740 if (optimizeMemoryInst(
II, PtrVal, AccessTy, AS))
2756 if (
Value *V = Simplifier.optimizeCall(CI, Builder)) {
2767 if (!
F->getReturnType()->isPointerTy())
2771 for (
auto &BB : *
F) {
2773 if (
auto *V = dyn_cast<GlobalVariable>(RI->getReturnValue())) {
2776 else if (V != UniformValue)
2784 return UniformValue;
2787 if (
Callee->hasExactDefinition()) {
2789 bool MadeChange =
false;
2791 auto *
I = dyn_cast<Instruction>(
U.getUser());
2814 if (
const auto *
II = dyn_cast<IntrinsicInst>(CI))
2815 switch (
II->getIntrinsicID()) {
2816 case Intrinsic::memset:
2817 case Intrinsic::memcpy:
2818 case Intrinsic::memmove:
2826 if (Callee && TLInfo && TLInfo->
getLibFunc(*Callee, LF))
2828 case LibFunc_strcpy:
2829 case LibFunc_strncpy:
2830 case LibFunc_strcat:
2831 case LibFunc_strncat:
2872bool CodeGenPrepare::dupRetToEnableTailCallOpts(
BasicBlock *BB,
2873 ModifyDT &ModifiedDT) {
2881 assert(LI->getLoopFor(BB) ==
nullptr &&
"A return block cannot be in a loop");
2888 BCI = dyn_cast<BitCastInst>(V);
2892 EVI = dyn_cast<ExtractValueInst>(V);
2899 PN = dyn_cast<PHINode>(V);
2905 auto isLifetimeEndOrBitCastFor = [](
const Instruction *Inst) {
2906 const BitCastInst *BC = dyn_cast<BitCastInst>(Inst);
2911 return II->getIntrinsicID() == Intrinsic::lifetime_end;
2917 auto isFakeUse = [&FakeUses](
const Instruction *Inst) {
2918 if (
auto *
II = dyn_cast<IntrinsicInst>(Inst);
2919 II &&
II->getIntrinsicID() == Intrinsic::fake_use) {
2927 if (!isa<PHINode>(
II->getOperand(0))) {
2940 while (isa<DbgInfoIntrinsic>(BI) || &*BI == BCI || &*BI == EVI ||
2941 isa<PseudoProbeInst>(BI) || isLifetimeEndOrBitCastFor(&*BI) ||
2958 CallInst *CI = dyn_cast<CallInst>(IncomingVal);
2978 CI = dyn_cast_or_null<CallInst>(
2994 if (!VisitedBBs.
insert(Pred).second)
2996 if (
Instruction *
I = Pred->rbegin()->getPrevNonDebugInstruction(
true)) {
3002 if (!V || isa<UndefValue>(V) ||
3013 bool Changed =
false;
3014 for (
auto const &TailCallBB : TailCallBBs) {
3017 BranchInst *BI = dyn_cast<BranchInst>(TailCallBB->getTerminator());
3024 BFI->getBlockFreq(BB) >=
BFI->getBlockFreq(TailCallBB));
3025 BFI->setBlockFreq(BB,
3026 (
BFI->getBlockFreq(BB) -
BFI->getBlockFreq(TailCallBB)));
3027 ModifiedDT = ModifyDT::ModifyBBDT;
3036 for (
auto *CI : CallInsts) {
3037 for (
auto const *FakeUse : FakeUses) {
3038 auto *ClonedInst = FakeUse->clone();
3059 Value *OriginalValue =
nullptr;
3060 bool InBounds =
true;
3064 BaseRegField = 0x01,
3066 BaseOffsField = 0x04,
3067 ScaledRegField = 0x08,
3069 MultipleFields = 0xff
3090 return MultipleFields;
3091 if (BaseGV && other.BaseGV && BaseGV->getType() != other.BaseGV->getType())
3092 return MultipleFields;
3095 return MultipleFields;
3098 if (InBounds != other.InBounds)
3099 return MultipleFields;
3102 unsigned Result = NoField;
3105 if (BaseGV != other.BaseGV)
3107 if (BaseOffs != other.BaseOffs)
3110 Result |= ScaledRegField;
3117 return MultipleFields;
3119 return static_cast<FieldName
>(
Result);
3140 case ScaledRegField:
3143 return ConstantInt::get(IntPtrTy, BaseOffs);
3147 void SetCombinedField(FieldName
Field,
Value *V,
3153 case ExtAddrMode::BaseRegField:
3156 case ExtAddrMode::BaseGVField:
3163 case ExtAddrMode::ScaledRegField:
3174 case ExtAddrMode::BaseOffsField:
3193#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
3195 bool NeedPlus =
false;
3201 BaseGV->printAsOperand(
OS,
false);
3206 OS << (NeedPlus ?
" + " :
"") << BaseOffs;
3211 OS << (NeedPlus ?
" + " :
"") <<
"Base:";
3216 OS << (NeedPlus ?
" + " :
"") <<
Scale <<
"*";
3239class TypePromotionTransaction {
3243 class TypePromotionAction {
3251 TypePromotionAction(
Instruction *Inst) : Inst(Inst) {}
3253 virtual ~TypePromotionAction() =
default;
3260 virtual void undo() = 0;
3265 virtual void commit() {
3271 class InsertionHandler {
3280 std::optional<DbgRecord::self_iterator> BeforeDbgRecord = std::nullopt;
3283 bool HasPrevInstruction;
3288 HasPrevInstruction = (Inst != &*(Inst->
getParent()->begin()));
3296 if (HasPrevInstruction) {
3305 if (HasPrevInstruction) {
3317 Inst->
getParent()->reinsertInstInDbgRecords(Inst, BeforeDbgRecord);
3322 class InstructionMoveBefore :
public TypePromotionAction {
3324 InsertionHandler Position;
3329 : TypePromotionAction(Inst), Position(Inst) {
3336 void undo()
override {
3338 Position.insert(Inst);
3343 class OperandSetter :
public TypePromotionAction {
3353 : TypePromotionAction(Inst),
Idx(
Idx) {
3355 <<
"for:" << *Inst <<
"\n"
3356 <<
"with:" << *NewVal <<
"\n");
3362 void undo()
override {
3364 <<
"for: " << *Inst <<
"\n"
3365 <<
"with: " << *Origin <<
"\n");
3372 class OperandsHider :
public TypePromotionAction {
3378 OperandsHider(
Instruction *Inst) : TypePromotionAction(Inst) {
3381 OriginalValues.
reserve(NumOpnds);
3382 for (
unsigned It = 0; It < NumOpnds; ++It) {
3394 void undo()
override {
3396 for (
unsigned It = 0, EndIt = OriginalValues.
size(); It != EndIt; ++It)
3402 class TruncBuilder :
public TypePromotionAction {
3409 TruncBuilder(
Instruction *Opnd,
Type *Ty) : TypePromotionAction(Opnd) {
3411 Builder.SetCurrentDebugLocation(
DebugLoc());
3412 Val = Builder.CreateTrunc(Opnd, Ty,
"promoted");
3417 Value *getBuiltValue() {
return Val; }
3420 void undo()
override {
3422 if (
Instruction *IVal = dyn_cast<Instruction>(Val))
3423 IVal->eraseFromParent();
3428 class SExtBuilder :
public TypePromotionAction {
3436 : TypePromotionAction(InsertPt) {
3438 Val = Builder.CreateSExt(Opnd, Ty,
"promoted");
3443 Value *getBuiltValue() {
return Val; }
3446 void undo()
override {
3448 if (
Instruction *IVal = dyn_cast<Instruction>(Val))
3449 IVal->eraseFromParent();
3454 class ZExtBuilder :
public TypePromotionAction {
3462 : TypePromotionAction(InsertPt) {
3464 Builder.SetCurrentDebugLocation(
DebugLoc());
3465 Val = Builder.CreateZExt(Opnd, Ty,
"promoted");
3470 Value *getBuiltValue() {
return Val; }
3473 void undo()
override {
3475 if (
Instruction *IVal = dyn_cast<Instruction>(Val))
3476 IVal->eraseFromParent();
3481 class TypeMutator :
public TypePromotionAction {
3488 : TypePromotionAction(Inst), OrigTy(Inst->
getType()) {
3489 LLVM_DEBUG(
dbgs() <<
"Do: MutateType: " << *Inst <<
" with " << *NewTy
3495 void undo()
override {
3496 LLVM_DEBUG(
dbgs() <<
"Undo: MutateType: " << *Inst <<
" with " << *OrigTy
3503 class UsesReplacer :
public TypePromotionAction {
3505 struct InstructionAndIdx {
3513 : Inst(Inst),
Idx(
Idx) {}
3532 : TypePromotionAction(Inst),
New(
New) {
3533 LLVM_DEBUG(
dbgs() <<
"Do: UsersReplacer: " << *Inst <<
" with " << *New
3538 OriginalUses.
push_back(InstructionAndIdx(UserI,
U.getOperandNo()));
3549 void undo()
override {
3551 for (InstructionAndIdx &
Use : OriginalUses)
3552 Use.Inst->setOperand(
Use.Idx, Inst);
3557 for (
auto *DVI : DbgValues)
3558 DVI->replaceVariableLocationOp(New, Inst);
3562 DVR->replaceVariableLocationOp(New, Inst);
3567 class InstructionRemover :
public TypePromotionAction {
3569 InsertionHandler Inserter;
3573 OperandsHider Hider;
3576 UsesReplacer *Replacer =
nullptr;
3579 SetOfInstrs &RemovedInsts;
3586 InstructionRemover(
Instruction *Inst, SetOfInstrs &RemovedInsts,
3587 Value *New =
nullptr)
3588 : TypePromotionAction(Inst), Inserter(Inst), Hider(Inst),
3589 RemovedInsts(RemovedInsts) {
3591 Replacer =
new UsesReplacer(Inst, New);
3592 LLVM_DEBUG(
dbgs() <<
"Do: InstructionRemover: " << *Inst <<
"\n");
3593 RemovedInsts.insert(Inst);
3600 ~InstructionRemover()
override {
delete Replacer; }
3602 InstructionRemover &operator=(
const InstructionRemover &other) =
delete;
3603 InstructionRemover(
const InstructionRemover &other) =
delete;
3607 void undo()
override {
3608 LLVM_DEBUG(
dbgs() <<
"Undo: InstructionRemover: " << *Inst <<
"\n");
3609 Inserter.insert(Inst);
3613 RemovedInsts.erase(Inst);
3621 using ConstRestorationPt =
const TypePromotionAction *;
3623 TypePromotionTransaction(SetOfInstrs &RemovedInsts)
3624 : RemovedInsts(RemovedInsts) {}
3631 void rollback(ConstRestorationPt Point);
3634 ConstRestorationPt getRestorationPoint()
const;
3666 SetOfInstrs &RemovedInsts;
3671void TypePromotionTransaction::setOperand(
Instruction *Inst,
unsigned Idx,
3673 Actions.
push_back(std::make_unique<TypePromotionTransaction::OperandSetter>(
3674 Inst,
Idx, NewVal));
3677void TypePromotionTransaction::eraseInstruction(
Instruction *Inst,
3680 std::make_unique<TypePromotionTransaction::InstructionRemover>(
3681 Inst, RemovedInsts, NewVal));
3684void TypePromotionTransaction::replaceAllUsesWith(
Instruction *Inst,
3687 std::make_unique<TypePromotionTransaction::UsesReplacer>(Inst, New));
3690void TypePromotionTransaction::mutateType(
Instruction *Inst,
Type *NewTy) {
3692 std::make_unique<TypePromotionTransaction::TypeMutator>(Inst, NewTy));
3696 std::unique_ptr<TruncBuilder>
Ptr(
new TruncBuilder(Opnd, Ty));
3698 Actions.push_back(std::move(
Ptr));
3704 std::unique_ptr<SExtBuilder>
Ptr(
new SExtBuilder(Inst, Opnd, Ty));
3706 Actions.push_back(std::move(
Ptr));
3712 std::unique_ptr<ZExtBuilder>
Ptr(
new ZExtBuilder(Inst, Opnd, Ty));
3714 Actions.push_back(std::move(
Ptr));
3718TypePromotionTransaction::ConstRestorationPt
3719TypePromotionTransaction::getRestorationPoint()
const {
3720 return !Actions.empty() ? Actions.back().get() :
nullptr;
3723bool TypePromotionTransaction::commit() {
3724 for (std::unique_ptr<TypePromotionAction> &Action : Actions)
3731void TypePromotionTransaction::rollback(
3732 TypePromotionTransaction::ConstRestorationPt Point) {
3733 while (!Actions.empty() && Point != Actions.back().get()) {
3734 std::unique_ptr<TypePromotionAction> Curr = Actions.pop_back_val();
3744class AddressingModeMatcher {
3763 const SetOfInstrs &InsertedInsts;
3766 InstrToOrigTy &PromotedInsts;
3769 TypePromotionTransaction &TPT;
3772 std::pair<AssertingVH<GetElementPtrInst>, int64_t> &LargeOffsetGEP;
3776 bool IgnoreProfitability;
3779 bool OptSize =
false;
3784 AddressingModeMatcher(
3789 const SetOfInstrs &InsertedInsts, InstrToOrigTy &PromotedInsts,
3790 TypePromotionTransaction &TPT,
3793 : AddrModeInsts(AMI), TLI(TLI),
TRI(
TRI),
3794 DL(
MI->getDataLayout()), LI(LI), getDTFn(getDTFn),
3795 AccessTy(AT), AddrSpace(AS), MemoryInst(
MI),
AddrMode(AM),
3796 InsertedInsts(InsertedInsts), PromotedInsts(PromotedInsts), TPT(TPT),
3797 LargeOffsetGEP(LargeOffsetGEP), OptSize(OptSize), PSI(PSI),
BFI(
BFI) {
3798 IgnoreProfitability =
false;
3815 InstrToOrigTy &PromotedInsts, TypePromotionTransaction &TPT,
3820 bool Success = AddressingModeMatcher(AddrModeInsts, TLI,
TRI, LI, getDTFn,
3821 AccessTy, AS, MemoryInst, Result,
3822 InsertedInsts, PromotedInsts, TPT,
3823 LargeOffsetGEP, OptSize, PSI, BFI)
3831 bool matchScaledValue(
Value *ScaleReg, int64_t Scale,
unsigned Depth);
3833 bool matchOperationAddr(
User *AddrInst,
unsigned Opcode,
unsigned Depth,
3834 bool *MovedAway =
nullptr);
3835 bool isProfitableToFoldIntoAddressingMode(
Instruction *
I,
3838 bool valueAlreadyLiveAtInst(
Value *Val,
Value *KnownLive1,
Value *KnownLive2);
3839 bool isPromotionProfitable(
unsigned NewCost,
unsigned OldCost,
3840 Value *PromotedOperand)
const;
3846class PhiNodeSetIterator {
3847 PhiNodeSet *
const Set;
3848 size_t CurrentIndex = 0;
3853 PhiNodeSetIterator(PhiNodeSet *
const Set,
size_t Start);
3855 PhiNodeSetIterator &operator++();
3871 friend class PhiNodeSetIterator;
3874 using iterator = PhiNodeSetIterator;
3889 size_t FirstValidElement = 0;
3896 if (NodeMap.insert(std::make_pair(
Ptr,
NodeList.size())).second) {
3907 if (NodeMap.erase(
Ptr)) {
3908 SkipRemovedElements(FirstValidElement);
3918 FirstValidElement = 0;
3924 if (FirstValidElement == 0)
3925 SkipRemovedElements(FirstValidElement);
3926 return PhiNodeSetIterator(
this, FirstValidElement);
3930 iterator
end() {
return PhiNodeSetIterator(
this,
NodeList.size()); }
3933 size_t size()
const {
return NodeMap.size(); }
3944 void SkipRemovedElements(
size_t &CurrentIndex) {
3945 while (CurrentIndex <
NodeList.size()) {
3946 auto it = NodeMap.find(
NodeList[CurrentIndex]);
3949 if (it != NodeMap.end() && it->second == CurrentIndex)
3956PhiNodeSetIterator::PhiNodeSetIterator(PhiNodeSet *
const Set,
size_t Start)
3957 :
Set(
Set), CurrentIndex(Start) {}
3959PHINode *PhiNodeSetIterator::operator*()
const {
3961 "PhiNodeSet access out of range");
3962 return Set->NodeList[CurrentIndex];
3965PhiNodeSetIterator &PhiNodeSetIterator::operator++() {
3967 "PhiNodeSet access out of range");
3969 Set->SkipRemovedElements(CurrentIndex);
3973bool PhiNodeSetIterator::operator==(
const PhiNodeSetIterator &RHS)
const {
3974 return CurrentIndex ==
RHS.CurrentIndex;
3977bool PhiNodeSetIterator::operator!=(
const PhiNodeSetIterator &RHS)
const {
3978 return !((*this) ==
RHS);
3984class SimplificationTracker {
3989 PhiNodeSet AllPhiNodes;
3998 auto SV = Storage.
find(V);
3999 if (SV == Storage.
end())
4009 while (!WorkList.
empty()) {
4011 if (!Visited.
insert(
P).second)
4013 if (
auto *PI = dyn_cast<Instruction>(
P))
4015 for (
auto *U : PI->users())
4018 PI->replaceAllUsesWith(V);
4019 if (
auto *
PHI = dyn_cast<PHINode>(PI))
4020 AllPhiNodes.erase(
PHI);
4021 if (
auto *
Select = dyn_cast<SelectInst>(PI))
4023 PI->eraseFromParent();
4033 while (OldReplacement !=
From) {
4035 To = dyn_cast<PHINode>(OldReplacement);
4036 OldReplacement = Get(
From);
4038 assert(To && Get(To) == To &&
"Replacement PHI node is already replaced.");
4040 From->replaceAllUsesWith(To);
4041 AllPhiNodes.erase(
From);
4042 From->eraseFromParent();
4045 PhiNodeSet &newPhiNodes() {
return AllPhiNodes; }
4047 void insertNewPhi(
PHINode *PN) { AllPhiNodes.insert(PN); }
4051 unsigned countNewPhiNodes()
const {
return AllPhiNodes.size(); }
4053 unsigned countNewSelectNodes()
const {
return AllSelectNodes.
size(); }
4055 void destroyNewNodes(
Type *CommonType) {
4058 for (
auto *
I : AllPhiNodes) {
4059 I->replaceAllUsesWith(Dummy);
4060 I->eraseFromParent();
4062 AllPhiNodes.clear();
4063 for (
auto *
I : AllSelectNodes) {
4064 I->replaceAllUsesWith(Dummy);
4065 I->eraseFromParent();
4067 AllSelectNodes.clear();
4072class AddressingModeCombiner {
4074 typedef std::pair<PHINode *, PHINode *> PHIPair;
4081 ExtAddrMode::FieldName DifferentField = ExtAddrMode::NoField;
4084 bool AllAddrModesTrivial =
true;
4087 Type *CommonType =
nullptr;
4096 Value *CommonValue =
nullptr;
4100 : SQ(_SQ), Original(OriginalValue) {}
4102 ~AddressingModeCombiner() { eraseCommonValueIfDead(); }
4114 AllAddrModesTrivial = AllAddrModesTrivial && NewAddrMode.isTrivial();
4117 if (AddrModes.
empty()) {
4125 ExtAddrMode::FieldName ThisDifferentField =
4126 AddrModes[0].compare(NewAddrMode);
4127 if (DifferentField == ExtAddrMode::NoField)
4128 DifferentField = ThisDifferentField;
4129 else if (DifferentField != ThisDifferentField)
4130 DifferentField = ExtAddrMode::MultipleFields;
4133 bool CanHandle = DifferentField != ExtAddrMode::MultipleFields;
4136 CanHandle = CanHandle && DifferentField != ExtAddrMode::ScaleField;
4141 CanHandle = CanHandle && (DifferentField != ExtAddrMode::BaseOffsField ||
4146 CanHandle = CanHandle && (DifferentField != ExtAddrMode::BaseGVField ||
4147 !NewAddrMode.HasBaseReg);
4164 bool combineAddrModes() {
4166 if (AddrModes.
size() == 0)
4170 if (AddrModes.
size() == 1 || DifferentField == ExtAddrMode::NoField)
4175 if (AllAddrModesTrivial)
4178 if (!addrModeCombiningAllowed())
4184 FoldAddrToValueMapping
Map;
4185 if (!initializeMap(Map))
4188 CommonValue = findCommon(Map);
4190 AddrModes[0].SetCombinedField(DifferentField, CommonValue, AddrModes);
4191 return CommonValue !=
nullptr;
4197 void eraseCommonValueIfDead() {
4198 if (CommonValue && CommonValue->
getNumUses() == 0)
4199 if (
Instruction *CommonInst = dyn_cast<Instruction>(CommonValue))
4200 CommonInst->eraseFromParent();
4208 bool initializeMap(FoldAddrToValueMapping &Map) {
4213 for (
auto &AM : AddrModes) {
4214 Value *DV = AM.GetFieldAsValue(DifferentField, IntPtrTy);
4217 if (CommonType && CommonType !=
Type)
4220 Map[AM.OriginalValue] = DV;
4225 assert(CommonType &&
"At least one non-null value must be!");
4226 for (
auto *V : NullValue)
4254 Value *findCommon(FoldAddrToValueMapping &Map) {
4262 SimplificationTracker
ST(SQ);
4267 InsertPlaceholders(Map, TraverseOrder, ST);
4270 FillPlaceholders(Map, TraverseOrder, ST);
4273 ST.destroyNewNodes(CommonType);
4278 unsigned PhiNotMatchedCount = 0;
4280 ST.destroyNewNodes(CommonType);
4284 auto *
Result =
ST.Get(
Map.find(Original)->second);
4286 NumMemoryInstsPhiCreated +=
ST.countNewPhiNodes() + PhiNotMatchedCount;
4287 NumMemoryInstsSelectCreated +=
ST.countNewSelectNodes();
4296 PhiNodeSet &PhiNodesToMatch) {
4303 while (!WorkList.
empty()) {
4305 if (!Visited.
insert(Item).second)
4312 for (
auto *
B : Item.first->blocks()) {
4313 Value *FirstValue = Item.first->getIncomingValueForBlock(
B);
4314 Value *SecondValue = Item.second->getIncomingValueForBlock(
B);
4315 if (FirstValue == SecondValue)
4318 PHINode *FirstPhi = dyn_cast<PHINode>(FirstValue);
4319 PHINode *SecondPhi = dyn_cast<PHINode>(SecondValue);
4325 if (!FirstPhi || !SecondPhi || !PhiNodesToMatch.count(FirstPhi) ||
4330 if (Matcher.
count({FirstPhi, SecondPhi}))
4335 if (MatchedPHIs.
insert(FirstPhi).second)
4336 Matcher.
insert({FirstPhi, SecondPhi});
4338 WorkList.
push_back({FirstPhi, SecondPhi});
4347 bool MatchPhiSet(SimplificationTracker &ST,
bool AllowNewPhiNodes,
4348 unsigned &PhiNotMatchedCount) {
4354 PhiNodeSet &PhiNodesToMatch =
ST.newPhiNodes();
4355 while (PhiNodesToMatch.size()) {
4359 WillNotMatch.
clear();
4363 bool IsMatched =
false;
4364 for (
auto &
P :
PHI->getParent()->phis()) {
4366 if (PhiNodesToMatch.count(&
P))
4368 if ((IsMatched = MatchPhiNode(
PHI, &
P, Matched, PhiNodesToMatch)))
4373 for (
auto M : Matched)
4379 for (
auto MV : Matched)
4380 ST.ReplacePhi(MV.first, MV.second);
4385 if (!AllowNewPhiNodes)
4388 PhiNotMatchedCount += WillNotMatch.
size();
4389 for (
auto *
P : WillNotMatch)
4390 PhiNodesToMatch.erase(
P);
4395 void FillPlaceholders(FoldAddrToValueMapping &Map,
4397 SimplificationTracker &ST) {
4398 while (!TraverseOrder.
empty()) {
4400 assert(
Map.contains(Current) &&
"No node to fill!!!");
4405 auto *CurrentSelect = cast<SelectInst>(Current);
4406 auto *TrueValue = CurrentSelect->getTrueValue();
4407 assert(
Map.contains(TrueValue) &&
"No True Value!");
4408 Select->setTrueValue(
ST.Get(Map[TrueValue]));
4409 auto *FalseValue = CurrentSelect->getFalseValue();
4410 assert(
Map.contains(FalseValue) &&
"No False Value!");
4411 Select->setFalseValue(
ST.Get(Map[FalseValue]));
4414 auto *
PHI = cast<PHINode>(V);
4417 Value *PV = cast<PHINode>(Current)->getIncomingValueForBlock(
B);
4418 assert(
Map.contains(PV) &&
"No predecessor Value!");
4419 PHI->addIncoming(
ST.Get(Map[PV]),
B);
4422 Map[Current] =
ST.Simplify(V);
4431 void InsertPlaceholders(FoldAddrToValueMapping &Map,
4433 SimplificationTracker &ST) {
4435 assert((isa<PHINode>(Original) || isa<SelectInst>(Original)) &&
4436 "Address must be a Phi or Select node");
4439 while (!Worklist.
empty()) {
4442 if (
Map.contains(Current))
4448 if (
SelectInst *CurrentSelect = dyn_cast<SelectInst>(Current)) {
4453 CurrentSelect->getName(),
4454 CurrentSelect->getIterator(), CurrentSelect);
4458 Worklist.
push_back(CurrentSelect->getTrueValue());
4459 Worklist.
push_back(CurrentSelect->getFalseValue());
4462 PHINode *CurrentPhi = cast<PHINode>(Current);
4467 ST.insertNewPhi(
PHI);
4473 bool addrModeCombiningAllowed() {
4476 switch (DifferentField) {
4479 case ExtAddrMode::BaseRegField:
4481 case ExtAddrMode::BaseGVField:
4483 case ExtAddrMode::BaseOffsField:
4485 case ExtAddrMode::ScaledRegField:
4495bool AddressingModeMatcher::matchScaledValue(
Value *ScaleReg, int64_t Scale,
4500 return matchAddr(ScaleReg,
Depth);
4515 TestAddrMode.
Scale += Scale;
4530 Value *AddLHS =
nullptr;
4531 if (isa<Instruction>(ScaleReg) &&
4534 TestAddrMode.InBounds =
false;
4541 AddrModeInsts.
push_back(cast<Instruction>(ScaleReg));
4551 auto GetConstantStep =
4552 [
this](
const Value *
V) -> std::optional<std::pair<Instruction *, APInt>> {
4553 auto *PN = dyn_cast<PHINode>(V);
4555 return std::nullopt;
4558 return std::nullopt;
4565 if (
auto *OIVInc = dyn_cast<OverflowingBinaryOperator>(IVInc->first))
4566 if (OIVInc->hasNoSignedWrap() || OIVInc->hasNoUnsignedWrap())
4567 return std::nullopt;
4568 if (
auto *ConstantStep = dyn_cast<ConstantInt>(IVInc->second))
4569 return std::make_pair(IVInc->first, ConstantStep->getValue());
4570 return std::nullopt;
4585 if (
auto IVStep = GetConstantStep(ScaleReg)) {
4592 APInt Step = IVStep->second;
4594 if (
Offset.isSignedIntN(64)) {
4595 TestAddrMode.InBounds =
false;
4597 TestAddrMode.BaseOffs -=
Offset.getLimitedValue();
4602 getDTFn().
dominates(IVInc, MemoryInst)) {
4603 AddrModeInsts.
push_back(cast<Instruction>(IVInc));
4622 switch (
I->getOpcode()) {
4623 case Instruction::BitCast:
4624 case Instruction::AddrSpaceCast:
4626 if (
I->getType() ==
I->getOperand(0)->getType())
4628 return I->getType()->isIntOrPtrTy();
4629 case Instruction::PtrToInt:
4632 case Instruction::IntToPtr:
4635 case Instruction::Add:
4637 case Instruction::Mul:
4638 case Instruction::Shl:
4640 return isa<ConstantInt>(
I->getOperand(1));
4641 case Instruction::GetElementPtr:
4654 Instruction *PromotedInst = dyn_cast<Instruction>(Val);
4669class TypePromotionHelper {
4672 static void addPromotedInst(InstrToOrigTy &PromotedInsts,
4674 ExtType ExtTy = IsSExt ? SignExtension : ZeroExtension;
4675 InstrToOrigTy::iterator It = PromotedInsts.find(ExtOpnd);
4676 if (It != PromotedInsts.end()) {
4679 if (It->second.getInt() == ExtTy)
4685 ExtTy = BothExtension;
4687 PromotedInsts[ExtOpnd] = TypeIsSExt(ExtOpnd->
getType(), ExtTy);
4694 static const Type *getOrigType(
const InstrToOrigTy &PromotedInsts,
4696 ExtType ExtTy = IsSExt ? SignExtension : ZeroExtension;
4697 InstrToOrigTy::const_iterator It = PromotedInsts.find(Opnd);
4698 if (It != PromotedInsts.end() && It->second.getInt() == ExtTy)
4699 return It->second.getPointer();
4714 static bool canGetThrough(
const Instruction *Inst,
Type *ConsideredExtType,
4715 const InstrToOrigTy &PromotedInsts,
bool IsSExt);
4719 static bool shouldExtOperand(
const Instruction *Inst,
int OpIdx) {
4720 return !(isa<SelectInst>(Inst) && OpIdx == 0);
4732 static Value *promoteOperandForTruncAndAnyExt(
4734 InstrToOrigTy &PromotedInsts,
unsigned &CreatedInstsCost,
4748 TypePromotionTransaction &TPT,
4749 InstrToOrigTy &PromotedInsts,
4750 unsigned &CreatedInstsCost,
4756 static Value *signExtendOperandForOther(
4758 InstrToOrigTy &PromotedInsts,
unsigned &CreatedInstsCost,
4761 return promoteOperandForOther(Ext, TPT, PromotedInsts, CreatedInstsCost,
4762 Exts, Truncs, TLI,
true);
4766 static Value *zeroExtendOperandForOther(
4768 InstrToOrigTy &PromotedInsts,
unsigned &CreatedInstsCost,
4771 return promoteOperandForOther(Ext, TPT, PromotedInsts, CreatedInstsCost,
4772 Exts, Truncs, TLI,
false);
4778 InstrToOrigTy &PromotedInsts,
4779 unsigned &CreatedInstsCost,
4793 static Action getAction(
Instruction *Ext,
const SetOfInstrs &InsertedInsts,
4795 const InstrToOrigTy &PromotedInsts);
4800bool TypePromotionHelper::canGetThrough(
const Instruction *Inst,
4801 Type *ConsideredExtType,
4802 const InstrToOrigTy &PromotedInsts,
4811 if (isa<ZExtInst>(Inst))
4815 if (IsSExt && isa<SExtInst>(Inst))
4820 if (
const auto *BinOp = dyn_cast<BinaryOperator>(Inst))
4821 if (isa<OverflowingBinaryOperator>(BinOp) &&
4822 ((!IsSExt && BinOp->hasNoUnsignedWrap()) ||
4823 (IsSExt && BinOp->hasNoSignedWrap())))
4827 if ((Inst->
getOpcode() == Instruction::And ||
4832 if (Inst->
getOpcode() == Instruction::Xor) {
4834 if (
const auto *Cst = dyn_cast<ConstantInt>(Inst->
getOperand(1)))
4835 if (!Cst->getValue().isAllOnes())
4844 if (Inst->
getOpcode() == Instruction::LShr && !IsSExt)
4853 const auto *ExtInst = cast<const Instruction>(*Inst->
user_begin());
4854 if (ExtInst->hasOneUse()) {
4855 const auto *AndInst = dyn_cast<const Instruction>(*ExtInst->user_begin());
4856 if (AndInst && AndInst->getOpcode() == Instruction::And) {
4857 const auto *Cst = dyn_cast<ConstantInt>(AndInst->getOperand(1));
4867 if (!isa<TruncInst>(Inst))
4881 Instruction *Opnd = dyn_cast<Instruction>(OpndVal);
4889 const Type *OpndType = getOrigType(PromotedInsts, Opnd, IsSExt);
4892 else if ((IsSExt && isa<SExtInst>(Opnd)) || (!IsSExt && isa<ZExtInst>(Opnd)))
4902TypePromotionHelper::Action TypePromotionHelper::getAction(
4903 Instruction *Ext,
const SetOfInstrs &InsertedInsts,
4905 assert((isa<SExtInst>(Ext) || isa<ZExtInst>(Ext)) &&
4906 "Unexpected instruction type");
4907 Instruction *ExtOpnd = dyn_cast<Instruction>(
Ext->getOperand(0));
4909 bool IsSExt = isa<SExtInst>(Ext);
4913 if (!ExtOpnd || !canGetThrough(ExtOpnd, ExtTy, PromotedInsts, IsSExt))
4919 if (isa<TruncInst>(ExtOpnd) && InsertedInsts.count(ExtOpnd))
4924 if (isa<SExtInst>(ExtOpnd) || isa<TruncInst>(ExtOpnd) ||
4925 isa<ZExtInst>(ExtOpnd))
4926 return promoteOperandForTruncAndAnyExt;
4932 return IsSExt ? signExtendOperandForOther : zeroExtendOperandForOther;
4935Value *TypePromotionHelper::promoteOperandForTruncAndAnyExt(
4937 InstrToOrigTy &PromotedInsts,
unsigned &CreatedInstsCost,
4943 Value *ExtVal = SExt;
4944 bool HasMergedNonFreeExt =
false;
4945 if (isa<ZExtInst>(SExtOpnd)) {
4948 HasMergedNonFreeExt = !TLI.
isExtFree(SExtOpnd);
4952 TPT.eraseInstruction(SExt);
4957 TPT.setOperand(SExt, 0, SExtOpnd->
getOperand(0));
4959 CreatedInstsCost = 0;
4963 TPT.eraseInstruction(SExtOpnd);
4966 Instruction *ExtInst = dyn_cast<Instruction>(ExtVal);
4971 CreatedInstsCost = !TLI.
isExtFree(ExtInst) && !HasMergedNonFreeExt;
4979 TPT.eraseInstruction(ExtInst, NextVal);
4983Value *TypePromotionHelper::promoteOperandForOther(
4985 InstrToOrigTy &PromotedInsts,
unsigned &CreatedInstsCost,
4992 CreatedInstsCost = 0;
4998 Value *Trunc = TPT.createTrunc(Ext, ExtOpnd->
getType());
4999 if (
Instruction *ITrunc = dyn_cast<Instruction>(Trunc)) {
5001 ITrunc->moveAfter(ExtOpnd);
5006 TPT.replaceAllUsesWith(ExtOpnd, Trunc);
5009 TPT.setOperand(Ext, 0, ExtOpnd);
5019 addPromotedInst(PromotedInsts, ExtOpnd, IsSExt);
5021 TPT.mutateType(ExtOpnd,
Ext->getType());
5023 TPT.replaceAllUsesWith(Ext, ExtOpnd);
5026 for (
int OpIdx = 0, EndOpIdx = ExtOpnd->
getNumOperands(); OpIdx != EndOpIdx;
5030 !shouldExtOperand(ExtOpnd, OpIdx)) {
5036 if (
const ConstantInt *Cst = dyn_cast<ConstantInt>(Opnd)) {
5038 unsigned BitWidth =
Ext->getType()->getIntegerBitWidth();
5041 TPT.setOperand(ExtOpnd, OpIdx, ConstantInt::get(
Ext->getType(), CstVal));
5045 if (isa<UndefValue>(Opnd)) {
5052 Value *ValForExtOpnd = IsSExt
5053 ? TPT.createSExt(ExtOpnd, Opnd,
Ext->getType())
5054 : TPT.createZExt(ExtOpnd, Opnd,
Ext->getType());
5055 TPT.setOperand(ExtOpnd, OpIdx, ValForExtOpnd);
5056 Instruction *InstForExtOpnd = dyn_cast<Instruction>(ValForExtOpnd);
5057 if (!InstForExtOpnd)
5063 CreatedInstsCost += !TLI.
isExtFree(InstForExtOpnd);
5066 TPT.eraseInstruction(Ext);
5078bool AddressingModeMatcher::isPromotionProfitable(
5079 unsigned NewCost,
unsigned OldCost,
Value *PromotedOperand)
const {
5080 LLVM_DEBUG(
dbgs() <<
"OldCost: " << OldCost <<
"\tNewCost: " << NewCost
5085 if (NewCost > OldCost)
5087 if (NewCost < OldCost)
5106bool AddressingModeMatcher::matchOperationAddr(
User *AddrInst,
unsigned Opcode,
5118 case Instruction::PtrToInt:
5121 case Instruction::IntToPtr: {
5129 case Instruction::BitCast:
5139 case Instruction::AddrSpaceCast: {
5147 case Instruction::Add: {
5151 unsigned OldSize = AddrModeInsts.
size();
5156 TypePromotionTransaction::ConstRestorationPt LastKnownGood =
5157 TPT.getRestorationPoint();
5161 int First = 0, Second = 1;
5163 && !isa<ConstantInt>(AddrInst->
getOperand(Second)))
5172 AddrModeInsts.
resize(OldSize);
5173 TPT.rollback(LastKnownGood);
5183 AddrModeInsts.
resize(OldSize);
5184 TPT.rollback(LastKnownGood);
5190 case Instruction::Mul:
5191 case Instruction::Shl: {
5195 if (!RHS ||
RHS->getBitWidth() > 64)
5197 int64_t Scale = Opcode == Instruction::Shl
5198 ? 1LL <<
RHS->getLimitedValue(
RHS->getBitWidth() - 1)
5199 :
RHS->getSExtValue();
5203 case Instruction::GetElementPtr: {
5206 int VariableOperand = -1;
5207 unsigned VariableScale = 0;
5209 int64_t ConstantOffset = 0;
5211 for (
unsigned i = 1, e = AddrInst->
getNumOperands(); i != e; ++i, ++GTI) {
5215 cast<ConstantInt>(AddrInst->
getOperand(i))->getZExtValue();
5225 dyn_cast<ConstantInt>(AddrInst->
getOperand(i))) {
5233 if (VariableOperand != -1)
5237 VariableOperand = i;
5245 if (VariableOperand == -1) {
5246 AddrMode.BaseOffs += ConstantOffset;
5248 if (!cast<GEPOperator>(AddrInst)->isInBounds())
5252 AddrMode.BaseOffs -= ConstantOffset;
5256 ConstantOffset > 0) {
5262 auto *BaseI = dyn_cast<Instruction>(
Base);
5263 auto *
GEP = cast<GetElementPtrInst>(AddrInst);
5264 if (isa<Argument>(
Base) || isa<GlobalValue>(
Base) ||
5265 (BaseI && !isa<CastInst>(BaseI) &&
5266 !isa<GetElementPtrInst>(BaseI))) {
5270 : &
GEP->getFunction()->getEntryBlock();
5272 LargeOffsetGEP = std::make_pair(
GEP, ConstantOffset);
5281 unsigned OldSize = AddrModeInsts.
size();
5284 AddrMode.BaseOffs += ConstantOffset;
5285 if (!cast<GEPOperator>(AddrInst)->isInBounds())
5293 AddrModeInsts.
resize(OldSize);
5301 if (!matchScaledValue(AddrInst->
getOperand(VariableOperand), VariableScale,
5306 AddrModeInsts.
resize(OldSize);
5311 AddrMode.BaseOffs += ConstantOffset;
5312 if (!matchScaledValue(AddrInst->
getOperand(VariableOperand),
5313 VariableScale,
Depth)) {
5316 AddrModeInsts.
resize(OldSize);
5323 case Instruction::SExt:
5324 case Instruction::ZExt: {
5331 TypePromotionHelper::Action TPH =
5332 TypePromotionHelper::getAction(Ext, InsertedInsts, TLI, PromotedInsts);
5336 TypePromotionTransaction::ConstRestorationPt LastKnownGood =
5337 TPT.getRestorationPoint();
5338 unsigned CreatedInstsCost = 0;
5340 Value *PromotedOperand =
5341 TPH(Ext, TPT, PromotedInsts, CreatedInstsCost,
nullptr,
nullptr, TLI);
5356 assert(PromotedOperand &&
5357 "TypePromotionHelper should have filtered out those cases");
5360 unsigned OldSize = AddrModeInsts.
size();
5362 if (!matchAddr(PromotedOperand,
Depth) ||
5367 !isPromotionProfitable(CreatedInstsCost,
5368 ExtCost + (AddrModeInsts.
size() - OldSize),
5371 AddrModeInsts.
resize(OldSize);
5372 LLVM_DEBUG(
dbgs() <<
"Sign extension does not pay off: rollback\n");
5373 TPT.rollback(LastKnownGood);
5378 AddrMode.replaceWith(Ext, PromotedOperand);
5381 case Instruction::Call:
5383 if (
II->getIntrinsicID() == Intrinsic::threadlocal_address) {
5399bool AddressingModeMatcher::matchAddr(
Value *
Addr,
unsigned Depth) {
5402 TypePromotionTransaction::ConstRestorationPt LastKnownGood =
5403 TPT.getRestorationPoint();
5422 unsigned OldSize = AddrModeInsts.
size();
5425 bool MovedAway =
false;
5426 if (matchOperationAddr(
I,
I->getOpcode(),
Depth, &MovedAway)) {
5434 if (
I->hasOneUse() ||
5435 isProfitableToFoldIntoAddressingMode(
I, BackupAddrMode,
AddrMode)) {
5442 AddrModeInsts.
resize(OldSize);
5443 TPT.rollback(LastKnownGood);
5446 if (matchOperationAddr(CE,
CE->getOpcode(),
Depth))
5448 TPT.rollback(LastKnownGood);
5449 }
else if (isa<ConstantPointerNull>(
Addr)) {
5475 TPT.rollback(LastKnownGood);
5494 if (OpInfo.CallOperandVal == OpVal &&
5496 !OpInfo.isIndirect))
5512 if (!ConsideredInsts.
insert(
I).second)
5520 for (
Use &U :
I->uses()) {
5526 Instruction *UserI = cast<Instruction>(U.getUser());
5527 if (
LoadInst *LI = dyn_cast<LoadInst>(UserI)) {
5528 MemoryUses.push_back({&U, LI->getType()});
5532 if (
StoreInst *SI = dyn_cast<StoreInst>(UserI)) {
5535 MemoryUses.push_back({&U, SI->getValueOperand()->
getType()});
5542 MemoryUses.push_back({&U, RMW->getValOperand()->
getType()});
5549 MemoryUses.push_back({&U, CmpX->getCompareOperand()->
getType()});
5553 if (
CallInst *CI = dyn_cast<CallInst>(UserI)) {
5554 if (CI->hasFnAttr(Attribute::Cold)) {
5561 InlineAsm *IA = dyn_cast<InlineAsm>(CI->getCalledOperand());
5572 PSI, BFI, SeenInsts))
5583 unsigned SeenInsts = 0;
5586 PSI, BFI, SeenInsts);
5594bool AddressingModeMatcher::valueAlreadyLiveAtInst(
Value *Val,
5596 Value *KnownLive2) {
5598 if (Val ==
nullptr || Val == KnownLive1 || Val == KnownLive2)
5602 if (!isa<Instruction>(Val) && !isa<Argument>(Val))
5608 if (
AllocaInst *AI = dyn_cast<AllocaInst>(Val))
5639bool AddressingModeMatcher::isProfitableToFoldIntoAddressingMode(
5641 if (IgnoreProfitability)
5659 if (valueAlreadyLiveAtInst(ScaledReg, AMBefore.
BaseReg, AMBefore.
ScaledReg))
5660 ScaledReg =
nullptr;
5664 if (!BaseReg && !ScaledReg)
5685 for (
const std::pair<Use *, Type *> &Pair : MemoryUses) {
5687 Instruction *UserI = cast<Instruction>(Pair.first->getUser());
5688 Type *AddressAccessTy = Pair.second;
5689 unsigned AS =
Address->getType()->getPointerAddressSpace();
5695 std::pair<AssertingVH<GetElementPtrInst>, int64_t> LargeOffsetGEP(
nullptr,
5697 TypePromotionTransaction::ConstRestorationPt LastKnownGood =
5698 TPT.getRestorationPoint();
5699 AddressingModeMatcher Matcher(MatchedAddrModeInsts, TLI,
TRI, LI, getDTFn,
5700 AddressAccessTy, AS, UserI, Result,
5701 InsertedInsts, PromotedInsts, TPT,
5702 LargeOffsetGEP, OptSize, PSI, BFI);
5703 Matcher.IgnoreProfitability =
true;
5704 bool Success = Matcher.matchAddr(Address, 0);
5711 TPT.rollback(LastKnownGood);
5717 MatchedAddrModeInsts.
clear();
5727 return I->getParent() != BB;
5751 Type *AccessTy,
unsigned AddrSpace) {
5763 bool PhiOrSelectSeen =
false;
5766 AddressingModeCombiner AddrModes(SQ,
Addr);
5767 TypePromotionTransaction TPT(RemovedInsts);
5768 TypePromotionTransaction::ConstRestorationPt LastKnownGood =
5769 TPT.getRestorationPoint();
5770 while (!worklist.
empty()) {
5782 if (!Visited.
insert(V).second)
5786 if (
PHINode *
P = dyn_cast<PHINode>(V)) {
5788 PhiOrSelectSeen =
true;
5792 if (
SelectInst *SI = dyn_cast<SelectInst>(V)) {
5795 PhiOrSelectSeen =
true;
5802 AddrModeInsts.
clear();
5803 std::pair<AssertingVH<GetElementPtrInst>, int64_t> LargeOffsetGEP(
nullptr,
5808 auto getDTFn = [MemoryInst,
this]() ->
const DominatorTree & {
5810 return this->getDT(*
F);
5812 ExtAddrMode NewAddrMode = AddressingModeMatcher::Match(
5813 V, AccessTy, AddrSpace, MemoryInst, AddrModeInsts, *TLI, *LI, getDTFn,
5814 *
TRI, InsertedInsts, PromotedInsts, TPT, LargeOffsetGEP, OptSize, PSI,
5822 LargeOffsetGEPMap[
GEP->getPointerOperand()].push_back(LargeOffsetGEP);
5823 LargeOffsetGEPID.
insert(std::make_pair(
GEP, LargeOffsetGEPID.
size()));
5826 NewAddrMode.OriginalValue =
V;
5827 if (!AddrModes.addNewAddrMode(NewAddrMode))
5834 if (!AddrModes.combineAddrModes()) {
5835 TPT.rollback(LastKnownGood);
5847 if (!PhiOrSelectSeen &&
none_of(AddrModeInsts, [&](
Value *V) {
5869 Type *IntPtrTy =
DL->getIntPtrType(
Addr->getType());
5872 <<
" for " << *MemoryInst <<
"\n");
5875 Addr->getType()->getPointerAddressSpace() &&
5876 !
DL->isNonIntegralPointerType(
Addr->getType())) {
5882 SunkAddr = Builder.CreatePtrToInt(SunkAddr, IntPtrTy,
"sunkaddr");
5884 Builder.CreateIntToPtr(SunkAddr,
Addr->getType(),
"sunkaddr");
5886 SunkAddr = Builder.CreatePointerCast(SunkAddr,
Addr->getType());
5893 <<
" for " << *MemoryInst <<
"\n");
5894 Value *ResultPtr =
nullptr, *ResultIndex =
nullptr;
5905 if (ResultPtr ||
AddrMode.Scale != 1)
5927 if (BaseGV !=
nullptr) {
5932 ResultPtr = Builder.CreateThreadLocalAddress(BaseGV);
5941 if (!
DL->isNonIntegralPointerType(
Addr->getType())) {
5942 if (!ResultPtr &&
AddrMode.BaseReg) {
5943 ResultPtr = Builder.CreateIntToPtr(
AddrMode.BaseReg,
Addr->getType(),
5946 }
else if (!ResultPtr &&
AddrMode.Scale == 1) {
5947 ResultPtr = Builder.CreateIntToPtr(
AddrMode.ScaledReg,
Addr->getType(),
5956 }
else if (!ResultPtr) {
5960 Builder.getPtrTy(
Addr->getType()->getPointerAddressSpace());
5969 if (
V->getType() != IntPtrTy)
5970 V = Builder.CreateIntCast(V, IntPtrTy,
true,
"sunkaddr");
5978 if (
V->getType() == IntPtrTy) {
5982 cast<IntegerType>(
V->getType())->getBitWidth() &&
5983 "We can't transform if ScaledReg is too narrow");
5984 V = Builder.CreateTrunc(V, IntPtrTy,
"sunkaddr");
5988 V = Builder.CreateMul(V, ConstantInt::get(IntPtrTy,
AddrMode.Scale),
5991 ResultIndex = Builder.CreateAdd(ResultIndex, V,
"sunkaddr");
6002 if (ResultPtr->
getType() != I8PtrTy)
6003 ResultPtr = Builder.CreatePointerCast(ResultPtr, I8PtrTy);
6004 ResultPtr = Builder.CreatePtrAdd(ResultPtr, ResultIndex,
"sunkaddr",
6012 SunkAddr = ResultPtr;
6014 if (ResultPtr->
getType() != I8PtrTy)
6015 ResultPtr = Builder.CreatePointerCast(ResultPtr, I8PtrTy);
6016 SunkAddr = Builder.CreatePtrAdd(ResultPtr, ResultIndex,
"sunkaddr",
6022 Addr->getType()->getPointerAddressSpace() &&
6023 !
DL->isNonIntegralPointerType(
Addr->getType())) {
6029 SunkAddr = Builder.CreatePtrToInt(SunkAddr, IntPtrTy,
"sunkaddr");
6031 Builder.CreateIntToPtr(SunkAddr,
Addr->getType(),
"sunkaddr");
6033 SunkAddr = Builder.CreatePointerCast(SunkAddr,
Addr->getType());
6042 PointerType *ScalePtrTy = dyn_cast_or_null<PointerType>(ScaleTy);
6043 if (
DL->isNonIntegralPointerType(
Addr->getType()) ||
6044 (BasePtrTy &&
DL->isNonIntegralPointerType(BasePtrTy)) ||
6045 (ScalePtrTy &&
DL->isNonIntegralPointerType(ScalePtrTy)) ||
6047 DL->isNonIntegralPointerType(
AddrMode.BaseGV->getType())))
6051 <<
" for " << *MemoryInst <<
"\n");
6052 Type *IntPtrTy =
DL->getIntPtrType(
Addr->getType());
6062 if (
V->getType()->isPointerTy())
6063 V = Builder.CreatePtrToInt(V, IntPtrTy,
"sunkaddr");
6064 if (
V->getType() != IntPtrTy)
6065 V = Builder.CreateIntCast(V, IntPtrTy,
true,
"sunkaddr");
6072 if (
V->getType() == IntPtrTy) {
6074 }
else if (
V->getType()->isPointerTy()) {
6075 V = Builder.CreatePtrToInt(V, IntPtrTy,
"sunkaddr");
6076 }
else if (cast<IntegerType>(IntPtrTy)->
getBitWidth() <
6077 cast<IntegerType>(
V->getType())->getBitWidth()) {
6078 V = Builder.CreateTrunc(V, IntPtrTy,
"sunkaddr");
6085 Instruction *
I = dyn_cast_or_null<Instruction>(Result);
6087 I->eraseFromParent();
6091 V = Builder.CreateMul(V, ConstantInt::get(IntPtrTy,
AddrMode.Scale),
6094 Result = Builder.CreateAdd(Result, V,
"sunkaddr");
6101 if (BaseGV !=
nullptr) {
6104 BaseGVPtr = Builder.CreateThreadLocalAddress(BaseGV);
6108 Value *
V = Builder.CreatePtrToInt(BaseGVPtr, IntPtrTy,
"sunkaddr");
6110 Result = Builder.CreateAdd(Result, V,
"sunkaddr");
6119 Result = Builder.CreateAdd(Result, V,
"sunkaddr");
6127 SunkAddr = Builder.CreateIntToPtr(Result,
Addr->getType(),
"sunkaddr");
6138 resetIteratorIfInvalidatedWhileCalling(CurInstIterator->getParent(), [&]() {
6139 RecursivelyDeleteTriviallyDeadInstructions(
6140 Repl, TLInfo, nullptr,
6141 [&](Value *V) { removeAllAssertingVHReferences(V); });
6165bool CodeGenPrepare::optimizeGatherScatterInst(
Instruction *MemoryInst,
6169 if (
const auto *
GEP = dyn_cast<GetElementPtrInst>(
Ptr)) {
6171 if (!
GEP->hasIndices())
6181 bool RewriteGEP =
false;
6183 if (Ops[0]->
getType()->isVectorTy()) {
6190 unsigned FinalIndex = Ops.size() - 1;
6195 for (
unsigned i = 1; i < FinalIndex; ++i) {
6196 auto *
C = dyn_cast<Constant>(Ops[i]);
6199 if (isa<VectorType>(
C->getType()))
6200 C =
C->getSplatValue();
6201 auto *CI = dyn_cast_or_null<ConstantInt>(
C);
6202 if (!CI || !CI->
isZero())
6209 if (Ops[FinalIndex]->
getType()->isVectorTy()) {
6211 auto *
C = dyn_cast<ConstantInt>(V);
6213 if (!
C || !
C->isZero()) {
6214 Ops[FinalIndex] =
V;
6222 if (!RewriteGEP && Ops.size() == 2)
6225 auto NumElts = cast<VectorType>(
Ptr->getType())->getElementCount();
6229 Type *SourceTy =
GEP->getSourceElementType();
6230 Type *ScalarIndexTy =
DL->getIndexType(Ops[0]->
getType()->getScalarType());
6234 if (!Ops[FinalIndex]->
getType()->isVectorTy()) {
6235 NewAddr = Builder.CreateGEP(SourceTy, Ops[0],
ArrayRef(Ops).drop_front());
6236 auto *IndexTy = VectorType::get(ScalarIndexTy, NumElts);
6238 SourceTy,
ArrayRef(Ops).drop_front());
6246 if (Ops.size() != 2) {
6252 SourceTy,
ArrayRef(Ops).drop_front());
6256 NewAddr = Builder.CreateGEP(SourceTy,
Base, Index);
6258 }
else if (!isa<Constant>(
Ptr)) {
6265 auto NumElts = cast<VectorType>(
Ptr->getType())->getElementCount();
6270 Type *ScalarIndexTy =
DL->getIndexType(
V->getType()->getScalarType());
6271 auto *IndexTy = VectorType::get(ScalarIndexTy, NumElts);
6274 Intrinsic::masked_gather) {
6278 Intrinsic::masked_scatter);
6291 if (
Ptr->use_empty())
6293 Ptr, TLInfo,
nullptr,
6294 [&](
Value *V) { removeAllAssertingVHReferences(V); });
6301bool CodeGenPrepare::optimizeInlineAsmInst(
CallInst *CS) {
6302 bool MadeChange =
false;
6305 TM->getSubtargetImpl(*CS->
getFunction())->getRegisterInfo();
6315 OpInfo.isIndirect) {
6317 MadeChange |= optimizeMemoryInst(CS, OpVal, OpVal->
getType(), ~0u);
6330 bool IsSExt = isa<SExtInst>(FirstUser);
6334 if ((IsSExt && !isa<SExtInst>(UI)) || (!IsSExt && !isa<ZExtInst>(UI)))
6380bool CodeGenPrepare::tryToPromoteExts(
6383 unsigned CreatedInstsCost) {
6384 bool Promoted =
false;
6387 for (
auto *
I : Exts) {
6389 if (isa<LoadInst>(
I->getOperand(0))) {
6402 TypePromotionHelper::Action TPH =
6403 TypePromotionHelper::getAction(
I, InsertedInsts, *TLI, PromotedInsts);
6412 TypePromotionTransaction::ConstRestorationPt LastKnownGood =
6413 TPT.getRestorationPoint();
6415 unsigned NewCreatedInstsCost = 0;
6418 Value *PromotedVal = TPH(
I, TPT, PromotedInsts, NewCreatedInstsCost,
6419 &NewExts,
nullptr, *TLI);
6421 "TypePromotionHelper should have filtered out those cases");
6431 long long TotalCreatedInstsCost = CreatedInstsCost + NewCreatedInstsCost;
6434 TotalCreatedInstsCost =
6435 std::max((
long long)0, (TotalCreatedInstsCost - ExtCost));
6437 (TotalCreatedInstsCost > 1 ||
6439 (ExtCost == 0 && NewExts.
size() > 1))) {
6443 TPT.rollback(LastKnownGood);
6449 (void)tryToPromoteExts(TPT, NewExts, NewlyMovedExts, TotalCreatedInstsCost);
6450 bool NewPromoted =
false;
6451 for (
auto *ExtInst : NewlyMovedExts) {
6452 Instruction *MovedExt = cast<Instruction>(ExtInst);
6456 if (isa<LoadInst>(ExtOperand) &&
6461 ProfitablyMovedExts.
push_back(MovedExt);
6468 TPT.rollback(LastKnownGood);
6479bool CodeGenPrepare::mergeSExts(
Function &
F) {
6480 bool Changed =
false;
6481 for (
auto &Entry : ValToSExtendedUses) {
6482 SExts &Insts =
Entry.second;
6485 if (RemovedInsts.count(Inst) || !isa<SExtInst>(Inst) ||
6488 bool inserted =
false;
6489 for (
auto &Pt : CurPts) {
6492 RemovedInsts.insert(Pt);
6493 Pt->removeFromParent();
6504 RemovedInsts.insert(Inst);
6511 CurPts.push_back(Inst);
6553bool CodeGenPrepare::splitLargeGEPOffsets() {
6554 bool Changed =
false;
6555 for (
auto &Entry : LargeOffsetGEPMap) {
6558 &LargeOffsetGEPs =
Entry.second;
6559 auto compareGEPOffset =
6560 [&](
const std::pair<GetElementPtrInst *, int64_t> &
LHS,
6561 const std::pair<GetElementPtrInst *, int64_t> &
RHS) {
6562 if (
LHS.first ==
RHS.first)
6564 if (
LHS.second !=
RHS.second)
6565 return LHS.second <
RHS.second;
6566 return LargeOffsetGEPID[
LHS.first] < LargeOffsetGEPID[
RHS.first];
6569 llvm::sort(LargeOffsetGEPs, compareGEPOffset);
6572 if (LargeOffsetGEPs.
front().second == LargeOffsetGEPs.
back().second)
6575 int64_t BaseOffset = LargeOffsetGEPs.
begin()->second;
6576 Value *NewBaseGEP =
nullptr;
6578 auto createNewBase = [&](int64_t BaseOffset,
Value *OldBase,
6581 Type *PtrIdxTy =
DL->getIndexType(
GEP->getType());
6583 PointerType::get(Ctx,
GEP->getType()->getPointerAddressSpace());
6587 if (
auto *BaseI = dyn_cast<Instruction>(OldBase)) {
6591 if (isa<PHINode>(BaseI))
6593 else if (
InvokeInst *Invoke = dyn_cast<InvokeInst>(BaseI)) {
6595 SplitEdge(NewBaseInsertBB, Invoke->getNormalDest(), DT.get(), LI);
6598 NewBaseInsertPt = std::next(BaseI->getIterator());
6605 IRBuilder<> NewBaseBuilder(NewBaseInsertBB, NewBaseInsertPt);
6607 Value *BaseIndex = ConstantInt::get(PtrIdxTy, BaseOffset);
6608 NewBaseGEP = OldBase;
6609 if (NewBaseGEP->
getType() != I8PtrTy)
6610 NewBaseGEP = NewBaseBuilder.CreatePointerCast(NewBaseGEP, I8PtrTy);
6612 NewBaseBuilder.CreatePtrAdd(NewBaseGEP, BaseIndex,
"splitgep");
6613 NewGEPBases.
insert(NewBaseGEP);
6619 LargeOffsetGEPs.
front().second, LargeOffsetGEPs.
back().second)) {
6620 BaseOffset = PreferBase;
6623 createNewBase(BaseOffset, OldBase, BaseGEP);
6626 auto *LargeOffsetGEP = LargeOffsetGEPs.
begin();
6627 while (LargeOffsetGEP != LargeOffsetGEPs.
end()) {
6629 int64_t
Offset = LargeOffsetGEP->second;
6630 if (
Offset != BaseOffset) {
6637 GEP->getResultElementType(),
6638 GEP->getAddressSpace())) {
6644 NewBaseGEP =
nullptr;
6649 Type *PtrIdxTy =
DL->getIndexType(
GEP->getType());
6654 createNewBase(BaseOffset, OldBase,
GEP);
6658 Value *NewGEP = NewBaseGEP;
6659 if (
Offset != BaseOffset) {
6662 NewGEP = Builder.CreatePtrAdd(NewBaseGEP, Index);
6666 LargeOffsetGEP = LargeOffsetGEPs.
erase(LargeOffsetGEP);
6667 GEP->eraseFromParent();
6674bool CodeGenPrepare::optimizePhiType(
6681 Type *PhiTy =
I->getType();
6682 Type *ConvertTy =
nullptr;
6684 (!
I->getType()->isIntegerTy() && !
I->getType()->isFloatingPointTy()))
6700 bool AnyAnchored =
false;
6702 while (!Worklist.
empty()) {
6705 if (
auto *Phi = dyn_cast<PHINode>(
II)) {
6707 for (
Value *V :
Phi->incoming_values()) {
6708 if (
auto *OpPhi = dyn_cast<PHINode>(V)) {
6709 if (!PhiNodes.
count(OpPhi)) {
6710 if (!Visited.
insert(OpPhi).second)
6715 }
else if (
auto *OpLoad = dyn_cast<LoadInst>(V)) {
6716 if (!OpLoad->isSimple())
6718 if (Defs.
insert(OpLoad).second)
6720 }
else if (
auto *OpEx = dyn_cast<ExtractElementInst>(V)) {
6721 if (Defs.
insert(OpEx).second)
6723 }
else if (
auto *OpBC = dyn_cast<BitCastInst>(V)) {
6725 ConvertTy = OpBC->getOperand(0)->getType();
6726 if (OpBC->getOperand(0)->getType() != ConvertTy)
6728 if (Defs.
insert(OpBC).second) {
6730 AnyAnchored |= !isa<LoadInst>(OpBC->getOperand(0)) &&
6731 !isa<ExtractElementInst>(OpBC->getOperand(0));
6733 }
else if (
auto *OpC = dyn_cast<ConstantData>(V))
6741 for (
User *V :
II->users()) {
6742 if (
auto *OpPhi = dyn_cast<PHINode>(V)) {
6743 if (!PhiNodes.
count(OpPhi)) {
6744 if (Visited.
count(OpPhi))
6750 }
else if (
auto *OpStore = dyn_cast<StoreInst>(V)) {
6751 if (!OpStore->isSimple() || OpStore->getOperand(0) !=
II)
6753 Uses.insert(OpStore);
6754 }
else if (
auto *OpBC = dyn_cast<BitCastInst>(V)) {
6756 ConvertTy = OpBC->getType();
6757 if (OpBC->getType() != ConvertTy)
6761 any_of(OpBC->users(), [](
User *U) { return !isa<StoreInst>(U); });
6768 if (!ConvertTy || !AnyAnchored ||
6772 LLVM_DEBUG(
dbgs() <<
"Converting " << *
I <<
"\n and connected nodes to "
6773 << *ConvertTy <<
"\n");
6781 if (isa<BitCastInst>(
D)) {
6782 ValMap[
D] =
D->getOperand(0);
6786 ValMap[
D] =
new BitCastInst(
D, ConvertTy,
D->getName() +
".bc", insertPt);
6791 Phi->getName() +
".tc",
Phi->getIterator());
6793 for (
PHINode *Phi : PhiNodes) {
6794 PHINode *NewPhi = cast<PHINode>(ValMap[Phi]);
6795 for (
int i = 0, e =
Phi->getNumIncomingValues(); i < e; i++)
6797 Phi->getIncomingBlock(i));
6802 if (isa<BitCastInst>(U)) {
6806 U->setOperand(0,
new BitCastInst(ValMap[
U->getOperand(0)], PhiTy,
"bc",
6813 DeletedInstrs.
insert(Phi);
6817bool CodeGenPrepare::optimizePhiTypes(
Function &
F) {
6821 bool Changed =
false;
6827 for (
auto &Phi : BB.
phis())
6828 Changed |= optimizePhiType(&Phi, Visited, DeletedInstrs);
6831 for (
auto *
I : DeletedInstrs) {
6833 I->eraseFromParent();
6841bool CodeGenPrepare::canFormExtLd(
6844 for (
auto *MovedExtInst : MovedExts) {
6845 if (isa<LoadInst>(MovedExtInst->getOperand(0))) {
6846 LI = cast<LoadInst>(MovedExtInst->getOperand(0));
6847 Inst = MovedExtInst;
6899bool CodeGenPrepare::optimizeExt(
Instruction *&Inst) {
6900 bool AllowPromotionWithoutCommonHeader =
false;
6905 *Inst, AllowPromotionWithoutCommonHeader);
6906 TypePromotionTransaction TPT(RemovedInsts);
6907 TypePromotionTransaction::ConstRestorationPt LastKnownGood =
6908 TPT.getRestorationPoint();
6913 bool HasPromoted = tryToPromoteExts(TPT, Exts, SpeculativelyMovedExts);
6921 if (canFormExtLd(SpeculativelyMovedExts, LI, ExtFedByLoad, HasPromoted)) {
6922 assert(LI && ExtFedByLoad &&
"Expect a valid load and extension");
6927 Inst = ExtFedByLoad;
6932 if (ATPConsiderable &&
6933 performAddressTypePromotion(Inst, AllowPromotionWithoutCommonHeader,
6934 HasPromoted, TPT, SpeculativelyMovedExts))
6937 TPT.rollback(LastKnownGood);
6946bool CodeGenPrepare::performAddressTypePromotion(
6947 Instruction *&Inst,
bool AllowPromotionWithoutCommonHeader,
6948 bool HasPromoted, TypePromotionTransaction &TPT,
6950 bool Promoted =
false;
6952 bool AllSeenFirst =
true;
6953 for (
auto *
I : SpeculativelyMovedExts) {
6954 Value *HeadOfChain =
I->getOperand(0);
6956 SeenChainsForSExt.
find(HeadOfChain);
6959 if (AlreadySeen != SeenChainsForSExt.
end()) {
6960 if (AlreadySeen->second !=
nullptr)
6961 UnhandledExts.
insert(AlreadySeen->second);
6962 AllSeenFirst =
false;
6966 if (!AllSeenFirst || (AllowPromotionWithoutCommonHeader &&
6967 SpeculativelyMovedExts.size() == 1)) {
6971 for (
auto *
I : SpeculativelyMovedExts) {
6972 Value *HeadOfChain =
I->getOperand(0);
6973 SeenChainsForSExt[HeadOfChain] =
nullptr;
6974 ValToSExtendedUses[HeadOfChain].push_back(
I);
6977 Inst = SpeculativelyMovedExts.pop_back_val();
6982 for (
auto *
I : SpeculativelyMovedExts) {
6983 Value *HeadOfChain =
I->getOperand(0);
6984 SeenChainsForSExt[HeadOfChain] = Inst;
6989 if (!AllSeenFirst && !UnhandledExts.
empty())
6990 for (
auto *VisitedSExt : UnhandledExts) {
6991 if (RemovedInsts.count(VisitedSExt))
6993 TypePromotionTransaction TPT(RemovedInsts);
6997 bool HasPromoted = tryToPromoteExts(TPT, Exts, Chains);
7001 for (
auto *
I : Chains) {
7002 Value *HeadOfChain =
I->getOperand(0);
7004 SeenChainsForSExt[HeadOfChain] =
nullptr;
7005 ValToSExtendedUses[HeadOfChain].push_back(
I);
7016 Value *Src =
I->getOperand(0);
7017 if (Src->hasOneUse())
7026 if (!isa<Instruction>(Src) || DefBB != cast<Instruction>(Src)->
getParent())
7029 bool DefIsLiveOut =
false;
7030 for (
User *U :
I->users()) {
7035 if (UserBB == DefBB)
7037 DefIsLiveOut =
true;
7044 for (
User *U : Src->users()) {
7047 if (UserBB == DefBB)
7051 if (isa<PHINode>(UI) || isa<LoadInst>(UI) || isa<StoreInst>(UI))
7058 bool MadeChange =
false;
7059 for (
Use &U : Src->uses()) {
7064 if (UserBB == DefBB)
7068 Instruction *&InsertedTrunc = InsertedTruncs[UserBB];
7070 if (!InsertedTrunc) {
7073 InsertedTrunc =
new TruncInst(
I, Src->getType(),
"");
7075 InsertedInsts.insert(InsertedTrunc);
7138bool CodeGenPrepare::optimizeLoadExt(
LoadInst *Load) {
7139 if (!
Load->isSimple() || !
Load->getType()->isIntOrPtrTy())
7143 if (
Load->hasOneUse() &&
7144 InsertedInsts.count(cast<Instruction>(*
Load->user_begin())))
7153 for (
auto *U :
Load->users())
7154 WorkList.
push_back(cast<Instruction>(U));
7165 while (!WorkList.
empty()) {
7169 if (!Visited.
insert(
I).second)
7173 if (
auto *Phi = dyn_cast<PHINode>(
I)) {
7174 for (
auto *U :
Phi->users())
7175 WorkList.
push_back(cast<Instruction>(U));
7179 switch (
I->getOpcode()) {
7180 case Instruction::And: {
7181 auto *AndC = dyn_cast<ConstantInt>(
I->getOperand(1));
7184 APInt AndBits = AndC->getValue();
7185 DemandBits |= AndBits;
7187 if (AndBits.
ugt(WidestAndBits))
7188 WidestAndBits = AndBits;
7189 if (AndBits == WidestAndBits &&
I->getOperand(0) == Load)
7194 case Instruction::Shl: {
7195 auto *ShlC = dyn_cast<ConstantInt>(
I->getOperand(1));
7199 DemandBits.setLowBits(
BitWidth - ShiftAmt);
7204 case Instruction::Trunc: {
7207 DemandBits.setLowBits(TruncBitWidth);
7217 uint32_t ActiveBits = DemandBits.getActiveBits();
7229 if (ActiveBits <= 1 || !DemandBits.isMask(ActiveBits) ||
7230 WidestAndBits != DemandBits)
7243 auto *NewAnd = cast<Instruction>(
7244 Builder.CreateAnd(Load, ConstantInt::get(Ctx, DemandBits)));
7247 InsertedInsts.insert(NewAnd);
7252 NewAnd->setOperand(0, Load);
7255 for (
auto *
And : AndsToMaybeRemove)
7258 if (cast<ConstantInt>(
And->getOperand(1))->getValue() == DemandBits) {
7260 if (&*CurInstIterator ==
And)
7261 CurInstIterator = std::next(
And->getIterator());
7262 And->eraseFromParent();
7267 for (
auto *Inst : DropFlags)
7277 auto *
I = dyn_cast<Instruction>(V);
7299 uint64_t Max = std::max(TrueWeight, FalseWeight);
7300 uint64_t Sum = TrueWeight + FalseWeight;
7308 CmpInst *Cmp = dyn_cast<CmpInst>(SI->getCondition());
7313 if (!Cmp || !Cmp->hasOneUse())
7334 for (
SelectInst *DefSI = SI; DefSI !=
nullptr && Selects.
count(DefSI);
7335 DefSI = dyn_cast<SelectInst>(V)) {
7336 assert(DefSI->getCondition() == SI->getCondition() &&
7337 "The condition of DefSI does not match with SI");
7338 V = (isTrue ? DefSI->getTrueValue() : DefSI->getFalseValue());
7341 assert(V &&
"Failed to get select true/false value");
7370 Value *NewTVal = Builder.CreateBinOp(Opcode, Shift->
getOperand(0), TVal);
7371 Value *NewFVal = Builder.CreateBinOp(Opcode, Shift->
getOperand(0), FVal);
7372 Value *NewSel = Builder.CreateSelect(
Cond, NewTVal, NewFVal);
7378bool CodeGenPrepare::optimizeFunnelShift(
IntrinsicInst *Fsh) {
7380 assert((Opcode == Intrinsic::fshl || Opcode == Intrinsic::fshr) &&
7381 "Expected a funnel shift");
7405 Value *NewTVal = Builder.CreateIntrinsic(Opcode, Ty, {
X,
Y, TVal});
7406 Value *NewFVal = Builder.CreateIntrinsic(Opcode, Ty, {
X,
Y, FVal});
7407 Value *NewSel = Builder.CreateSelect(
Cond, NewTVal, NewFVal);
7415bool CodeGenPrepare::optimizeSelectInst(
SelectInst *SI) {
7427 It !=
SI->getParent()->
end(); ++It) {
7429 if (
I &&
SI->getCondition() ==
I->getCondition()) {
7439 CurInstIterator = std::next(LastSI->
getIterator());
7444 fixupDbgVariableRecordsOnInst(*SI);
7446 bool VectorCond = !
SI->getCondition()->getType()->isIntegerTy(1);
7449 if (VectorCond ||
SI->getMetadata(LLVMContext::MD_unpredictable))
7453 if (
SI->getType()->isVectorTy())
7454 SelectKind = TargetLowering::ScalarCondVectorVal;
7456 SelectKind = TargetLowering::ScalarValSelect;
7499 TrueInstrs.
push_back(cast<Instruction>(V));
7501 FalseInstrs.
push_back(cast<Instruction>(V));
7509 SplitPt.setHeadBit(
true);
7512 auto *CondFr =
IB.CreateFreeze(
SI->getCondition(),
SI->getName() +
".frozen");
7519 if (TrueInstrs.
size() == 0) {
7521 CondFr, SplitPt,
false,
nullptr,
nullptr, LI));
7523 EndBlock = cast<BasicBlock>(FalseBranch->
getOperand(0));
7524 }
else if (FalseInstrs.
size() == 0) {
7526 CondFr, SplitPt,
false,
nullptr,
nullptr, LI));
7528 EndBlock = cast<BasicBlock>(TrueBranch->
getOperand(0));
7533 nullptr,
nullptr, LI);
7534 TrueBranch = cast<BranchInst>(ThenTerm);
7535 FalseBranch = cast<BranchInst>(ElseTerm);
7538 EndBlock = cast<BasicBlock>(TrueBranch->
getOperand(0));
7541 EndBlock->
setName(
"select.end");
7543 TrueBlock->
setName(
"select.true.sink");
7545 FalseBlock->
setName(FalseInstrs.
size() == 0 ?
"select.false"
7546 :
"select.false.sink");
7550 FreshBBs.
insert(TrueBlock);
7552 FreshBBs.
insert(FalseBlock);
7553 FreshBBs.
insert(EndBlock);
7556 BFI->setBlockFreq(EndBlock,
BFI->getBlockFreq(StartBlock));
7558 static const unsigned MD[] = {
7559 LLVMContext::MD_prof, LLVMContext::MD_unpredictable,
7560 LLVMContext::MD_make_implicit, LLVMContext::MD_dbg};
7574 if (TrueBlock ==
nullptr)
7575 TrueBlock = StartBlock;
7576 else if (FalseBlock ==
nullptr)
7577 FalseBlock = StartBlock;
7580 INS.
insert(ASI.begin(), ASI.end());
7594 SI->eraseFromParent();
7596 ++NumSelectsExpanded;
7600 CurInstIterator = StartBlock->
end();
7616 auto *SVIVecType = cast<FixedVectorType>(SVI->
getType());
7619 "Expected a type of the same size!");
7625 Builder.SetInsertPoint(SVI);
7626 Value *BC1 = Builder.CreateBitCast(
7627 cast<Instruction>(SVI->
getOperand(0))->getOperand(1), NewType);
7628 Value *Shuffle = Builder.CreateVectorSplat(NewVecType->getNumElements(), BC1);
7629 Value *BC2 = Builder.CreateBitCast(Shuffle, SVIVecType);
7633 SVI, TLInfo,
nullptr,
7634 [&](
Value *V) { removeAllAssertingVHReferences(V); });
7638 if (
auto *BCI = dyn_cast<Instruction>(BC1))
7639 if (
auto *
Op = dyn_cast<Instruction>(BCI->
getOperand(0)))
7640 if (BCI->
getParent() !=
Op->getParent() && !isa<PHINode>(
Op) &&
7641 !
Op->isTerminator() && !
Op->isEHPad())
7647bool CodeGenPrepare::tryToSinkFreeOperands(
Instruction *
I) {
7659 bool Changed =
false;
7663 unsigned long InstNumber = 0;
7664 for (
const auto &
I : *TargetBB)
7665 InstOrdering[&
I] = InstNumber++;
7668 auto *UI = cast<Instruction>(
U->get());
7669 if (isa<PHINode>(UI))
7672 if (InstOrdering[UI] < InstOrdering[InsertPoint])
7681 for (
Use *U : ToReplace) {
7682 auto *UI = cast<Instruction>(
U->get());
7689 if (
auto *OpDef = dyn_cast<Instruction>(
Op))
7690 FreshBBs.
insert(OpDef->getParent());
7693 NewInstructions[UI] = NI;
7698 InsertedInsts.insert(NI);
7704 if (
auto It = NewInstructions.
find(OldI); It != NewInstructions.
end())
7705 It->second->setOperand(
U->getOperandNo(), NI);
7712 for (
auto *
I : MaybeDead) {
7713 if (!
I->hasNUsesOrMore(1)) {
7715 I->eraseFromParent();
7722bool CodeGenPrepare::optimizeSwitchType(
SwitchInst *SI) {
7730 if (RegWidth <= cast<IntegerType>(OldType)->
getBitWidth())
7748 ExtType = Instruction::SExt;
7750 if (
auto *Arg = dyn_cast<Argument>(
Cond)) {
7751 if (Arg->hasSExtAttr())
7752 ExtType = Instruction::SExt;
7753 if (Arg->hasZExtAttr())
7754 ExtType = Instruction::ZExt;
7760 SI->setCondition(ExtInst);
7761 for (
auto Case :
SI->cases()) {
7762 const APInt &NarrowConst = Case.getCaseValue()->getValue();
7763 APInt WideConst = (ExtType == Instruction::ZExt)
7764 ? NarrowConst.
zext(RegWidth)
7765 : NarrowConst.
sext(RegWidth);
7766 Case.setValue(ConstantInt::get(Context, WideConst));
7772bool CodeGenPrepare::optimizeSwitchPhiConstants(
SwitchInst *SI) {
7779 Value *Condition =
SI->getCondition();
7781 if (isa<ConstantInt>(*Condition))
7784 bool Changed =
false;
7790 BasicBlock *CaseBB = Case.getCaseSuccessor();
7793 bool CheckedForSinglePred =
false;
7795 Type *PHIType =
PHI.getType();
7803 if (PHIType == ConditionType || TryZExt) {
7805 bool SkipCase =
false;
7806 Value *Replacement =
nullptr;
7807 for (
unsigned I = 0, E =
PHI.getNumIncomingValues();
I != E;
I++) {
7808 Value *PHIValue =
PHI.getIncomingValue(
I);
7809 if (PHIValue != CaseValue) {
7812 ConstantInt *PHIValueInt = dyn_cast<ConstantInt>(PHIValue);
7818 if (
PHI.getIncomingBlock(
I) != SwitchBB)
7823 if (!CheckedForSinglePred) {
7824 CheckedForSinglePred =
true;
7825 if (
SI->findCaseDest(CaseBB) ==
nullptr) {
7831 if (Replacement ==
nullptr) {
7832 if (PHIValue == CaseValue) {
7833 Replacement = Condition;
7836 Replacement = Builder.CreateZExt(Condition, PHIType);
7839 PHI.setIncomingValue(
I, Replacement);
7850bool CodeGenPrepare::optimizeSwitchInst(
SwitchInst *SI) {
7851 bool Changed = optimizeSwitchType(SI);
7852 Changed |= optimizeSwitchPhiConstants(SI);
7873class VectorPromoteHelper {
7890 unsigned StoreExtractCombineCost;
7899 if (InstsToBePromoted.
empty())
7901 return InstsToBePromoted.
back();
7907 unsigned getTransitionOriginalValueIdx()
const {
7908 assert(isa<ExtractElementInst>(Transition) &&
7909 "Other kind of transitions are not supported yet");
7916 unsigned getTransitionIdx()
const {
7917 assert(isa<ExtractElementInst>(Transition) &&
7918 "Other kind of transitions are not supported yet");
7926 Type *getTransitionType()
const {
7941 bool isProfitableToPromote() {
7942 Value *ValIdx = Transition->
getOperand(getTransitionOriginalValueIdx());
7943 unsigned Index = isa<ConstantInt>(ValIdx)
7944 ? cast<ConstantInt>(ValIdx)->getZExtValue()
7946 Type *PromotedType = getTransitionType();
7949 unsigned AS =
ST->getPointerAddressSpace();
7967 for (
const auto &Inst : InstsToBePromoted) {
7973 bool IsArg0Constant = isa<UndefValue>(Arg0) || isa<ConstantInt>(Arg0) ||
7974 isa<ConstantFP>(Arg0);
7987 dbgs() <<
"Estimated cost of computation to be promoted:\nScalar: "
7988 << ScalarCost <<
"\nVector: " << VectorCost <<
'\n');
7989 return ScalarCost > VectorCost;
8001 unsigned ExtractIdx = std::numeric_limits<unsigned>::max();
8006 if (
ConstantInt *CstVal = dyn_cast<ConstantInt>(ValExtractIdx))
8012 ElementCount EC = cast<VectorType>(getTransitionType())->getElementCount();
8016 if (!
EC.isScalable()) {
8019 for (
unsigned Idx = 0;
Idx !=
EC.getKnownMinValue(); ++
Idx) {
8020 if (
Idx == ExtractIdx)
8028 "Generate scalable vector for non-splat is unimplemented");
8034 unsigned OperandIdx) {
8037 if (OperandIdx != 1)
8039 switch (
Use->getOpcode()) {
8042 case Instruction::SDiv:
8043 case Instruction::UDiv:
8044 case Instruction::SRem:
8045 case Instruction::URem:
8047 case Instruction::FDiv:
8048 case Instruction::FRem:
8049 return !
Use->hasNoNaNs();
8057 unsigned CombineCost)
8058 :
DL(
DL), TLI(TLI),
TTI(
TTI), Transition(Transition),
8059 StoreExtractCombineCost(CombineCost) {
8060 assert(Transition &&
"Do not know how to promote null");
8064 bool canPromote(
const Instruction *ToBePromoted)
const {
8066 return isa<BinaryOperator>(ToBePromoted);
8071 bool shouldPromote(
const Instruction *ToBePromoted)
const {
8075 const Value *Val =
U.get();
8076 if (Val == getEndOfTransition()) {
8080 if (canCauseUndefinedBehavior(ToBePromoted,
U.getOperandNo()))
8084 if (!isa<ConstantInt>(Val) && !isa<UndefValue>(Val) &&
8085 !isa<ConstantFP>(Val))
8094 ISDOpcode, TLI.
getValueType(DL, getTransitionType(),
true));
8103 void enqueueForPromotion(
Instruction *ToBePromoted) {
8104 InstsToBePromoted.push_back(ToBePromoted);
8108 void recordCombineInstruction(
Instruction *ToBeCombined) {
8110 CombineInst = ToBeCombined;
8120 if (InstsToBePromoted.empty() || !CombineInst)
8128 for (
auto &ToBePromoted : InstsToBePromoted)
8129 promoteImpl(ToBePromoted);
8130 InstsToBePromoted.clear();
8137void VectorPromoteHelper::promoteImpl(
Instruction *ToBePromoted) {
8147 "The type of the result of the transition does not match "
8152 Type *TransitionTy = getTransitionType();
8159 Value *NewVal =
nullptr;
8160 if (Val == Transition)
8161 NewVal = Transition->
getOperand(getTransitionOriginalValueIdx());
8162 else if (isa<UndefValue>(Val) || isa<ConstantInt>(Val) ||
8163 isa<ConstantFP>(Val)) {
8166 cast<Constant>(Val),
8167 isa<UndefValue>(Val) ||
8168 canCauseUndefinedBehavior(ToBePromoted,
U.getOperandNo()));
8172 ToBePromoted->
setOperand(
U.getOperandNo(), NewVal);
8175 Transition->
setOperand(getTransitionOriginalValueIdx(), ToBePromoted);
8181bool CodeGenPrepare::optimizeExtractElementInst(
Instruction *Inst) {
8182 unsigned CombineCost = std::numeric_limits<unsigned>::max();
8197 LLVM_DEBUG(
dbgs() <<
"Found an interesting transition: " << *Inst <<
'\n');
8198 VectorPromoteHelper VPH(*
DL, *TLI, *
TTI, Inst, CombineCost);
8205 if (ToBePromoted->
getParent() != Parent) {
8206 LLVM_DEBUG(
dbgs() <<
"Instruction to promote is in a different block ("
8208 <<
") than the transition (" << Parent->
getName()
8213 if (VPH.canCombine(ToBePromoted)) {
8215 <<
"will be combined with: " << *ToBePromoted <<
'\n');
8216 VPH.recordCombineInstruction(ToBePromoted);
8217 bool Changed = VPH.promote();
8218 NumStoreExtractExposed += Changed;
8223 if (!VPH.canPromote(ToBePromoted) || !VPH.shouldPromote(ToBePromoted))
8226 LLVM_DEBUG(
dbgs() <<
"Promoting is possible... Enqueue for promotion!\n");
8228 VPH.enqueueForPromotion(ToBePromoted);
8229 Inst = ToBePromoted;
8269 Type *StoreType = SI.getValueOperand()->getType();
8278 if (!
DL.typeSizeEqualsStoreSize(StoreType) ||
8279 DL.getTypeSizeInBits(StoreType) == 0)
8282 unsigned HalfValBitSize =
DL.getTypeSizeInBits(StoreType) / 2;
8284 if (!
DL.typeSizeEqualsStoreSize(SplitStoreType))
8288 if (SI.isVolatile())
8300 if (!
match(SI.getValueOperand(),
8307 if (!
LValue->getType()->isIntegerTy() ||
8308 DL.getTypeSizeInBits(
LValue->getType()) > HalfValBitSize ||
8310 DL.getTypeSizeInBits(HValue->
getType()) > HalfValBitSize)
8315 auto *LBC = dyn_cast<BitCastInst>(
LValue);
8316 auto *HBC = dyn_cast<BitCastInst>(HValue);
8330 if (LBC && LBC->getParent() != SI.getParent())
8332 if (HBC && HBC->getParent() != SI.getParent())
8333 HValue = Builder.
CreateBitCast(HBC->getOperand(0), HBC->getType());
8335 bool IsLE = SI.getDataLayout().isLittleEndian();
8336 auto CreateSplitStore = [&](
Value *V,
bool Upper) {
8339 Align Alignment = SI.getAlign();
8340 const bool IsOffsetStore = (IsLE &&
Upper) || (!IsLE && !
Upper);
8341 if (IsOffsetStore) {
8343 SplitStoreType,
Addr,
8354 CreateSplitStore(
LValue,
false);
8355 CreateSplitStore(HValue,
true);
8358 SI.eraseFromParent();
8366 return GEP->getNumOperands() == 2 &&
I.isSequential() &&
8367 isa<ConstantInt>(
GEP->getOperand(1));
8445 if (!isa<Instruction>(GEPIOp))
8447 auto *GEPIOpI = cast<Instruction>(GEPIOp);
8448 if (GEPIOpI->getParent() != SrcBlock)
8453 if (auto *I = dyn_cast<Instruction>(Usr)) {
8454 if (I->getParent() != SrcBlock) {
8462 std::vector<GetElementPtrInst *> UGEPIs;
8469 if (!isa<Instruction>(Usr))
8471 auto *UI = cast<Instruction>(Usr);
8476 if (!isa<GetElementPtrInst>(Usr))
8478 auto *UGEPI = cast<GetElementPtrInst>(Usr);
8484 if (UGEPI->getOperand(0) != GEPIOp)
8486 if (UGEPI->getSourceElementType() != GEPI->getSourceElementType())
8488 if (GEPIIdx->getType() !=
8489 cast<ConstantInt>(UGEPI->getOperand(1))->getType())
8491 ConstantInt *UGEPIIdx = cast<ConstantInt>(UGEPI->getOperand(1));
8496 UGEPIs.push_back(UGEPI);
8498 if (UGEPIs.size() == 0)
8502 ConstantInt *UGEPIIdx = cast<ConstantInt>(UGEPI->getOperand(1));
8511 UGEPI->setOperand(0, GEPI);
8512 ConstantInt *UGEPIIdx = cast<ConstantInt>(UGEPI->getOperand(1));
8513 Constant *NewUGEPIIdx = ConstantInt::get(
8514 GEPIIdx->getType(), UGEPIIdx->
getValue() - GEPIIdx->getValue());
8515 UGEPI->setOperand(1, NewUGEPIIdx);
8518 if (!GEPI->isInBounds()) {
8519 UGEPI->setIsInBounds(
false);
8526 return cast<Instruction>(Usr)->getParent() != SrcBlock;
8528 "GEPIOp is used outside SrcBlock");
8548 ICmpInst *Cmp = dyn_cast<ICmpInst>(Branch->getCondition());
8549 if (!Cmp || !isa<ConstantInt>(Cmp->getOperand(1)) || !Cmp->hasOneUse())
8552 Value *
X = Cmp->getOperand(0);
8553 APInt CmpC = cast<ConstantInt>(Cmp->getOperand(1))->getValue();
8555 for (
auto *U :
X->users()) {
8559 (UI->
getParent() != Branch->getParent() &&
8560 UI->
getParent() != Branch->getSuccessor(0) &&
8561 UI->
getParent() != Branch->getSuccessor(1)) ||
8562 (UI->
getParent() != Branch->getParent() &&
8563 !UI->
getParent()->getSinglePredecessor()))
8566 if (CmpC.
isPowerOf2() && Cmp->getPredicate() == ICmpInst::ICMP_ULT &&
8569 if (UI->
getParent() != Branch->getParent())
8573 ConstantInt::get(UI->
getType(), 0));
8575 LLVM_DEBUG(
dbgs() <<
" to compare on zero: " << *NewCmp <<
"\n");
8579 if (Cmp->isEquality() &&
8583 if (UI->
getParent() != Branch->getParent())
8587 ConstantInt::get(UI->
getType(), 0));
8589 LLVM_DEBUG(
dbgs() <<
" to compare on zero: " << *NewCmp <<
"\n");
8597bool CodeGenPrepare::optimizeInst(
Instruction *
I, ModifyDT &ModifiedDT) {
8598 bool AnyChange =
false;
8599 AnyChange = fixupDbgVariableRecordsOnInst(*
I);
8603 if (InsertedInsts.count(
I))
8607 if (
PHINode *
P = dyn_cast<PHINode>(
I)) {
8612 LargeOffsetGEPMap.erase(
P);
8614 P->eraseFromParent();
8621 if (
CastInst *CI = dyn_cast<CastInst>(
I)) {
8634 if ((isa<UIToFPInst>(
I) || isa<SIToFPInst>(
I) || isa<FPToUIInst>(
I) ||
8635 isa<TruncInst>(
I)) &&
8637 I, LI->getLoopFor(
I->getParent()), *
TTI))
8640 if (isa<ZExtInst>(
I) || isa<SExtInst>(
I)) {
8645 TargetLowering::TypeExpandInteger) {
8649 I, LI->getLoopFor(
I->getParent()), *
TTI))
8652 bool MadeChange = optimizeExt(
I);
8653 return MadeChange | optimizeExtUses(
I);
8659 if (
auto *Cmp = dyn_cast<CmpInst>(
I))
8660 if (optimizeCmp(Cmp, ModifiedDT))
8664 if (optimizeURem(
I))
8667 if (
LoadInst *LI = dyn_cast<LoadInst>(
I)) {
8668 LI->
setMetadata(LLVMContext::MD_invariant_group,
nullptr);
8669 bool Modified = optimizeLoadExt(LI);
8675 if (
StoreInst *SI = dyn_cast<StoreInst>(
I)) {
8678 SI->setMetadata(LLVMContext::MD_invariant_group,
nullptr);
8679 unsigned AS =
SI->getPointerAddressSpace();
8680 return optimizeMemoryInst(
I,
SI->getOperand(1),
8681 SI->getOperand(0)->getType(), AS);
8685 unsigned AS = RMW->getPointerAddressSpace();
8686 return optimizeMemoryInst(
I, RMW->getPointerOperand(), RMW->getType(), AS);
8690 unsigned AS = CmpX->getPointerAddressSpace();
8691 return optimizeMemoryInst(
I, CmpX->getPointerOperand(),
8692 CmpX->getCompareOperand()->getType(), AS);
8702 if (BinOp && (BinOp->
getOpcode() == Instruction::AShr ||
8703 BinOp->
getOpcode() == Instruction::LShr)) {
8711 if (GEPI->hasAllZeroIndices()) {
8714 GEPI->getName(), GEPI->getIterator());
8715 NC->setDebugLoc(GEPI->getDebugLoc());
8718 GEPI, TLInfo,
nullptr,
8719 [&](
Value *V) { removeAllAssertingVHReferences(V); });
8721 optimizeInst(
NC, ModifiedDT);
8733 if (
ICmpInst *
II = dyn_cast<ICmpInst>(FI->getOperand(0)))
8735 else if (
FCmpInst *
F = dyn_cast<FCmpInst>(FI->getOperand(0)))
8736 CmpI =
F->getFastMathFlags().none() ?
F :
nullptr;
8740 bool Const0 = isa<ConstantInt>(Op0) || isa<ConstantFP>(Op0) ||
8741 isa<ConstantPointerNull>(Op0);
8742 bool Const1 = isa<ConstantInt>(Op1) || isa<ConstantFP>(Op1) ||
8743 isa<ConstantPointerNull>(Op1);
8744 if (Const0 || Const1) {
8745 if (!Const0 || !Const1) {
8751 FI->eraseFromParent();
8758 if (tryToSinkFreeOperands(
I))
8761 switch (
I->getOpcode()) {
8762 case Instruction::Shl:
8763 case Instruction::LShr:
8764 case Instruction::AShr:
8765 return optimizeShiftInst(cast<BinaryOperator>(
I));
8766 case Instruction::Call:
8768 case Instruction::Select:
8769 return optimizeSelectInst(cast<SelectInst>(
I));
8770 case Instruction::ShuffleVector:
8771 return optimizeShuffleVectorInst(cast<ShuffleVectorInst>(
I));
8772 case Instruction::Switch:
8773 return optimizeSwitchInst(cast<SwitchInst>(
I));
8774 case Instruction::ExtractElement:
8775 return optimizeExtractElementInst(cast<ExtractElementInst>(
I));
8776 case Instruction::Br:
8777 return optimizeBranch(cast<BranchInst>(
I), *TLI, FreshBBs, IsHugeFunc);
8786 if (!
I.getType()->isIntegerTy() ||
8797 &
I, TLInfo,
nullptr,
8798 [&](
Value *V) { removeAllAssertingVHReferences(V); });
8805bool CodeGenPrepare::optimizeBlock(
BasicBlock &BB, ModifyDT &ModifiedDT) {
8807 bool MadeChange =
false;
8810 CurInstIterator = BB.
begin();
8811 ModifiedDT = ModifyDT::NotModifyDT;
8812 while (CurInstIterator != BB.
end()) {
8813 MadeChange |= optimizeInst(&*CurInstIterator++, ModifiedDT);
8814 if (ModifiedDT != ModifyDT::NotModifyDT) {
8827 }
while (ModifiedDT == ModifyDT::ModifyInstDT);
8829 bool MadeBitReverse =
true;
8830 while (MadeBitReverse) {
8831 MadeBitReverse =
false;
8833 if (makeBitReverse(
I)) {
8834 MadeBitReverse = MadeChange =
true;
8839 MadeChange |= dupRetToEnableTailCallOpts(&BB, ModifiedDT);
8851 bool AnyChange =
false;
8854 for (
Value *Location : LocationOps) {
8870bool CodeGenPrepare::fixupDbgVariableRecordsOnInst(
Instruction &
I) {
8871 bool AnyChange =
false;
8873 AnyChange |= fixupDbgVariableRecord(DVR);
8880 if (DVR.
Type != DbgVariableRecord::LocationType::Value &&
8881 DVR.
Type != DbgVariableRecord::LocationType::Assign)
8885 bool AnyChange =
false;
8888 for (
Value *Location : LocationOps) {
8906 if (isa<PHINode>(VI))
8907 DVI->
insertBefore(VI->getParent()->getFirstInsertionPt());
8915 if (isa<PHINode>(VI))
8926bool CodeGenPrepare::placeDbgValues(
Function &
F) {
8927 bool MadeChange =
false;
8930 auto DbgProcessor = [&](
auto *DbgItem,
Instruction *Position) {
8932 for (
Value *V : DbgItem->location_ops())
8933 if (
Instruction *VI = dyn_cast_or_null<Instruction>(V))
8941 if (
VI->isTerminator())
8946 if (isa<PHINode>(VI) &&
VI->getParent()->getTerminator()->isEHPad())
8957 if (VIs.size() > 1) {
8960 <<
"Unable to find valid location for Debug Value, undefing:\n"
8962 DbgItem->setKillLocation();
8967 << *DbgItem <<
' ' << *VI);
8979 DbgProcessor(DVI, DVI);
8987 if (DVR.
Type != DbgVariableRecord::LocationType::Value)
8989 DbgProcessor(&DVR, &
Insn);
9000bool CodeGenPrepare::placePseudoProbes(
Function &
F) {
9001 bool MadeChange =
false;
9004 auto FirstInst =
Block.getFirstInsertionPt();
9005 while (FirstInst !=
Block.end() && FirstInst->isDebugOrPseudoInst())
9009 while (
I !=
Block.end()) {
9010 if (
auto *
II = dyn_cast<PseudoProbeInst>(
I++)) {
9011 II->moveBefore(FirstInst);
9021 uint64_t NewMax = (NewTrue > NewFalse) ? NewTrue : NewFalse;
9022 uint32_t Scale = (NewMax / std::numeric_limits<uint32_t>::max()) + 1;
9023 NewTrue = NewTrue / Scale;
9024 NewFalse = NewFalse / Scale;
9049bool CodeGenPrepare::splitBranchCondition(
Function &
F, ModifyDT &ModifiedDT) {
9053 bool MadeChange =
false;
9054 for (
auto &BB :
F) {
9067 if (Br1->getMetadata(LLVMContext::MD_unpredictable))
9075 Value *Cond1, *Cond2;
9078 Opc = Instruction::And;
9081 Opc = Instruction::Or;
9091 if (!IsGoodCond(Cond1) || !IsGoodCond(Cond2))
9105 Br1->setCondition(Cond1);
9110 if (Opc == Instruction::And)
9111 Br1->setSuccessor(0, TmpBB);
9113 Br1->setSuccessor(1, TmpBB);
9117 if (
auto *
I = dyn_cast<Instruction>(Cond2)) {
9118 I->removeFromParent();
9119 I->insertBefore(Br2->getIterator());
9131 if (Opc == Instruction::Or)
9145 if (Opc == Instruction::Or) {
9167 uint64_t NewTrueWeight = TrueWeight;
9168 uint64_t NewFalseWeight = TrueWeight + 2 * FalseWeight;
9170 Br1->setMetadata(LLVMContext::MD_prof,
9175 NewTrueWeight = TrueWeight;
9176 NewFalseWeight = 2 * FalseWeight;
9178 Br2->setMetadata(LLVMContext::MD_prof,
9203 uint64_t NewTrueWeight = 2 * TrueWeight + FalseWeight;
9204 uint64_t NewFalseWeight = FalseWeight;
9206 Br1->setMetadata(LLVMContext::MD_prof,
9210 NewTrueWeight = 2 * TrueWeight;
9211 NewFalseWeight = FalseWeight;
9213 Br2->setMetadata(LLVMContext::MD_prof,
9219 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 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 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, BasicBlock::iterator 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 bool adjustIsPower2Test(CmpInst *Cmp, const TargetLowering &TLI, const TargetTransformInfo &TTI, const DataLayout &DL)
Some targets have better codegen for ctpop(X) u< 2 than ctpop(X) == 1.
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 isRemOfLoopIncrementWithLoopInvariant(Instruction *Rem, const LoopInfo *LI, Value *&RemAmtOut, Value *&AddInstOut, Value *&AddOffsetOut, PHINode *&LoopIncrPNOut)
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 cl::opt< bool > EnableAndCmpSinking("enable-andcmp-sinking", cl::Hidden, cl::init(true), cl::desc("Enable sinking and/cmp into branches."))
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 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")
Module.h This file contains the declarations for the Module class.
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.
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)
Remove Loads Into Fake Uses
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
static bool optimizeBlock(BasicBlock &BB, bool &ModifiedDT, const TargetTransformInfo &TTI, const DataLayout &DL, bool HasBranchDivergence, DomTreeUpdater *DTU)
static bool optimizeCallInst(CallInst *CI, bool &ModifiedDT, const TargetTransformInfo &TTI, const DataLayout &DL, bool HasBranchDivergence, 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,...
InstListType::const_iterator getFirstNonPHIIt() const
Returns an iterator to the first instruction in this block that is not a PHINode instruction.
void insertDbgRecordBefore(DbgRecord *DR, InstListType::iterator Here)
Insert a DbgRecord into a block at the position given by Here.
InstListType::const_iterator const_iterator
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
InstListType::const_iterator getFirstNonPHIOrDbg(bool SkipPseudoOp=true) const
Returns a pointer to the first instruction in this block that is not a PHINode or a debug intrinsic,...
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.
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.
An abstraction over a floating-point predicate, and a pack of an integer predicate with samesign info...
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)
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.
bool isEquality() const
Return true if this predicate is either EQ or NE.
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 setHasNoSignedWrap(bool b=true)
Set or clear the nsw flag on this instruction, which must be an operator which supports this flag.
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 hasMetadata() const
Return true if this instruction has any metadata attached to it.
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.
bool comesBefore(const Instruction *Other) const
Given an instruction Other in the same basic block as this instruction, return true if this instructi...
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.
In order to facilitate speculative execution, many instructions do not invoke immediate undefined beh...
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.
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 for a comparison of the specified types on this ...
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.
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...
virtual bool getAddrModeArguments(const IntrinsicInst *, SmallVectorImpl< Value * > &, Type *&) const
CodeGenPrepare sinks address calculations into the same BB as Load/Store instructions reading the add...
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 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(SmallPtrSetImpl< const Type * > &Visited) 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'.
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.
int getNumOccurrences() const
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.
OverflowingBinaryOp_match< LHS, RHS, Instruction::Add, OverflowingBinaryOperator::NoUnsignedWrap > m_NUWAdd(const LHS &L, const RHS &R)
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.
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.
OverflowingBinaryOp_match< LHS, RHS, Instruction::Add, OverflowingBinaryOperator::NoSignedWrap > m_NSWAdd(const LHS &L, const RHS &R)
CmpClass_match< LHS, RHS, ICmpInst > m_ICmp(CmpPredicate &Pred, const LHS &L, const RHS &R)
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.
@ CE
Windows NT (Windows on ARM)
initializer< Ty > init(const Ty &Val)
PointerTypeMap run(const Module &M)
Compute the PointerTypeMap for the module M.
@ Assume
Do not drop type tests (default).
NodeAddr< PhiNode * > Phi
const_iterator begin(StringRef path LLVM_LIFETIME_BOUND, Style style=Style::native)
Get begin iterator over path.
const_iterator end(StringRef path LLVM_LIFETIME_BOUND)
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.
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...
auto pred_end(const MachineBasicBlock *BB)
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.
Value * simplifyAddInst(Value *LHS, Value *RHS, bool IsNSW, bool IsNUW, const SimplifyQuery &Q)
Given operands for an Add, fold the result or return null.
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...
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.
auto pred_begin(const MachineBasicBlock *BB)
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.