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 sinkinig 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))
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();
3039 ClonedInst->insertBefore(CI);
3059 Value *OriginalValue =
nullptr;
3060 bool InBounds =
true;
3064 BaseRegField = 0x01,
3066 BaseOffsField = 0x04,
3067 ScaledRegField = 0x08,
3069 MultipleFields = 0xff
3082 return MultipleFields;
3083 if (BaseGV && other.BaseGV && BaseGV->getType() != other.BaseGV->getType())
3084 return MultipleFields;
3087 return MultipleFields;
3090 if (InBounds != other.InBounds)
3091 return MultipleFields;
3094 unsigned Result = NoField;
3097 if (BaseGV != other.BaseGV)
3099 if (BaseOffs != other.BaseOffs)
3102 Result |= ScaledRegField;
3109 return MultipleFields;
3111 return static_cast<FieldName
>(
Result);
3132 case ScaledRegField:
3135 return ConstantInt::get(IntPtrTy, BaseOffs);
3139 void SetCombinedField(FieldName
Field,
Value *V,
3145 case ExtAddrMode::BaseRegField:
3148 case ExtAddrMode::BaseGVField:
3155 case ExtAddrMode::ScaledRegField:
3166 case ExtAddrMode::BaseOffsField:
3185#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
3187 bool NeedPlus =
false;
3193 BaseGV->printAsOperand(
OS,
false);
3198 OS << (NeedPlus ?
" + " :
"") << BaseOffs;
3203 OS << (NeedPlus ?
" + " :
"") <<
"Base:";
3208 OS << (NeedPlus ?
" + " :
"") <<
Scale <<
"*";
3231class TypePromotionTransaction {
3235 class TypePromotionAction {
3243 TypePromotionAction(
Instruction *Inst) : Inst(Inst) {}
3245 virtual ~TypePromotionAction() =
default;
3252 virtual void undo() = 0;
3257 virtual void commit() {
3263 class InsertionHandler {
3272 std::optional<DbgRecord::self_iterator> BeforeDbgRecord = std::nullopt;
3275 bool HasPrevInstruction;
3280 HasPrevInstruction = (Inst != &*(Inst->
getParent()->begin()));
3288 if (HasPrevInstruction) {
3289 Point.PrevInst = &*std::prev(Inst->
getIterator());
3297 if (HasPrevInstruction) {
3309 Inst->
getParent()->reinsertInstInDbgRecords(Inst, BeforeDbgRecord);
3314 class InstructionMoveBefore :
public TypePromotionAction {
3316 InsertionHandler Position;
3321 : TypePromotionAction(Inst), Position(Inst) {
3328 void undo()
override {
3330 Position.insert(Inst);
3335 class OperandSetter :
public TypePromotionAction {
3345 : TypePromotionAction(Inst),
Idx(
Idx) {
3347 <<
"for:" << *Inst <<
"\n"
3348 <<
"with:" << *NewVal <<
"\n");
3354 void undo()
override {
3356 <<
"for: " << *Inst <<
"\n"
3357 <<
"with: " << *Origin <<
"\n");
3364 class OperandsHider :
public TypePromotionAction {
3370 OperandsHider(
Instruction *Inst) : TypePromotionAction(Inst) {
3373 OriginalValues.
reserve(NumOpnds);
3374 for (
unsigned It = 0; It < NumOpnds; ++It) {
3386 void undo()
override {
3388 for (
unsigned It = 0, EndIt = OriginalValues.
size(); It != EndIt; ++It)
3394 class TruncBuilder :
public TypePromotionAction {
3401 TruncBuilder(
Instruction *Opnd,
Type *Ty) : TypePromotionAction(Opnd) {
3403 Builder.SetCurrentDebugLocation(
DebugLoc());
3404 Val = Builder.CreateTrunc(Opnd, Ty,
"promoted");
3409 Value *getBuiltValue() {
return Val; }
3412 void undo()
override {
3414 if (
Instruction *IVal = dyn_cast<Instruction>(Val))
3415 IVal->eraseFromParent();
3420 class SExtBuilder :
public TypePromotionAction {
3428 : TypePromotionAction(InsertPt) {
3430 Val = Builder.CreateSExt(Opnd, Ty,
"promoted");
3435 Value *getBuiltValue() {
return Val; }
3438 void undo()
override {
3440 if (
Instruction *IVal = dyn_cast<Instruction>(Val))
3441 IVal->eraseFromParent();
3446 class ZExtBuilder :
public TypePromotionAction {
3454 : TypePromotionAction(InsertPt) {
3456 Builder.SetCurrentDebugLocation(
DebugLoc());
3457 Val = Builder.CreateZExt(Opnd, Ty,
"promoted");
3462 Value *getBuiltValue() {
return Val; }
3465 void undo()
override {
3467 if (
Instruction *IVal = dyn_cast<Instruction>(Val))
3468 IVal->eraseFromParent();
3473 class TypeMutator :
public TypePromotionAction {
3480 : TypePromotionAction(Inst), OrigTy(Inst->
getType()) {
3481 LLVM_DEBUG(
dbgs() <<
"Do: MutateType: " << *Inst <<
" with " << *NewTy
3487 void undo()
override {
3488 LLVM_DEBUG(
dbgs() <<
"Undo: MutateType: " << *Inst <<
" with " << *OrigTy
3495 class UsesReplacer :
public TypePromotionAction {
3497 struct InstructionAndIdx {
3505 : Inst(Inst),
Idx(
Idx) {}
3524 : TypePromotionAction(Inst),
New(
New) {
3525 LLVM_DEBUG(
dbgs() <<
"Do: UsersReplacer: " << *Inst <<
" with " << *New
3530 OriginalUses.
push_back(InstructionAndIdx(UserI,
U.getOperandNo()));
3541 void undo()
override {
3543 for (InstructionAndIdx &
Use : OriginalUses)
3544 Use.Inst->setOperand(
Use.Idx, Inst);
3549 for (
auto *DVI : DbgValues)
3550 DVI->replaceVariableLocationOp(New, Inst);
3554 DVR->replaceVariableLocationOp(New, Inst);
3559 class InstructionRemover :
public TypePromotionAction {
3561 InsertionHandler Inserter;
3565 OperandsHider Hider;
3568 UsesReplacer *Replacer =
nullptr;
3571 SetOfInstrs &RemovedInsts;
3578 InstructionRemover(
Instruction *Inst, SetOfInstrs &RemovedInsts,
3579 Value *New =
nullptr)
3580 : TypePromotionAction(Inst), Inserter(Inst), Hider(Inst),
3581 RemovedInsts(RemovedInsts) {
3583 Replacer =
new UsesReplacer(Inst, New);
3584 LLVM_DEBUG(
dbgs() <<
"Do: InstructionRemover: " << *Inst <<
"\n");
3585 RemovedInsts.insert(Inst);
3592 ~InstructionRemover()
override {
delete Replacer; }
3594 InstructionRemover &operator=(
const InstructionRemover &other) =
delete;
3595 InstructionRemover(
const InstructionRemover &other) =
delete;
3599 void undo()
override {
3600 LLVM_DEBUG(
dbgs() <<
"Undo: InstructionRemover: " << *Inst <<
"\n");
3601 Inserter.insert(Inst);
3605 RemovedInsts.erase(Inst);
3613 using ConstRestorationPt =
const TypePromotionAction *;
3615 TypePromotionTransaction(SetOfInstrs &RemovedInsts)
3616 : RemovedInsts(RemovedInsts) {}
3623 void rollback(ConstRestorationPt Point);
3626 ConstRestorationPt getRestorationPoint()
const;
3658 SetOfInstrs &RemovedInsts;
3663void TypePromotionTransaction::setOperand(
Instruction *Inst,
unsigned Idx,
3665 Actions.
push_back(std::make_unique<TypePromotionTransaction::OperandSetter>(
3666 Inst,
Idx, NewVal));
3669void TypePromotionTransaction::eraseInstruction(
Instruction *Inst,
3672 std::make_unique<TypePromotionTransaction::InstructionRemover>(
3673 Inst, RemovedInsts, NewVal));
3676void TypePromotionTransaction::replaceAllUsesWith(
Instruction *Inst,
3679 std::make_unique<TypePromotionTransaction::UsesReplacer>(Inst, New));
3682void TypePromotionTransaction::mutateType(
Instruction *Inst,
Type *NewTy) {
3684 std::make_unique<TypePromotionTransaction::TypeMutator>(Inst, NewTy));
3688 std::unique_ptr<TruncBuilder>
Ptr(
new TruncBuilder(Opnd, Ty));
3690 Actions.push_back(std::move(
Ptr));
3696 std::unique_ptr<SExtBuilder>
Ptr(
new SExtBuilder(Inst, Opnd, Ty));
3698 Actions.push_back(std::move(
Ptr));
3704 std::unique_ptr<ZExtBuilder>
Ptr(
new ZExtBuilder(Inst, Opnd, Ty));
3706 Actions.push_back(std::move(
Ptr));
3710TypePromotionTransaction::ConstRestorationPt
3711TypePromotionTransaction::getRestorationPoint()
const {
3712 return !Actions.empty() ? Actions.back().get() :
nullptr;
3715bool TypePromotionTransaction::commit() {
3716 for (std::unique_ptr<TypePromotionAction> &Action : Actions)
3723void TypePromotionTransaction::rollback(
3724 TypePromotionTransaction::ConstRestorationPt Point) {
3725 while (!Actions.empty() && Point != Actions.back().get()) {
3726 std::unique_ptr<TypePromotionAction> Curr = Actions.pop_back_val();
3736class AddressingModeMatcher {
3755 const SetOfInstrs &InsertedInsts;
3758 InstrToOrigTy &PromotedInsts;
3761 TypePromotionTransaction &TPT;
3764 std::pair<AssertingVH<GetElementPtrInst>, int64_t> &LargeOffsetGEP;
3768 bool IgnoreProfitability;
3771 bool OptSize =
false;
3776 AddressingModeMatcher(
3781 const SetOfInstrs &InsertedInsts, InstrToOrigTy &PromotedInsts,
3782 TypePromotionTransaction &TPT,
3785 : AddrModeInsts(AMI), TLI(TLI),
TRI(
TRI),
3786 DL(
MI->getDataLayout()), LI(LI), getDTFn(getDTFn),
3787 AccessTy(AT), AddrSpace(AS), MemoryInst(
MI),
AddrMode(AM),
3788 InsertedInsts(InsertedInsts), PromotedInsts(PromotedInsts), TPT(TPT),
3789 LargeOffsetGEP(LargeOffsetGEP), OptSize(OptSize), PSI(PSI),
BFI(
BFI) {
3790 IgnoreProfitability =
false;
3807 InstrToOrigTy &PromotedInsts, TypePromotionTransaction &TPT,
3812 bool Success = AddressingModeMatcher(AddrModeInsts, TLI,
TRI, LI, getDTFn,
3813 AccessTy, AS, MemoryInst, Result,
3814 InsertedInsts, PromotedInsts, TPT,
3815 LargeOffsetGEP, OptSize, PSI, BFI)
3823 bool matchScaledValue(
Value *ScaleReg, int64_t Scale,
unsigned Depth);
3825 bool matchOperationAddr(
User *AddrInst,
unsigned Opcode,
unsigned Depth,
3826 bool *MovedAway =
nullptr);
3827 bool isProfitableToFoldIntoAddressingMode(
Instruction *
I,
3830 bool valueAlreadyLiveAtInst(
Value *Val,
Value *KnownLive1,
Value *KnownLive2);
3831 bool isPromotionProfitable(
unsigned NewCost,
unsigned OldCost,
3832 Value *PromotedOperand)
const;
3838class PhiNodeSetIterator {
3839 PhiNodeSet *
const Set;
3840 size_t CurrentIndex = 0;
3845 PhiNodeSetIterator(PhiNodeSet *
const Set,
size_t Start);
3847 PhiNodeSetIterator &operator++();
3863 friend class PhiNodeSetIterator;
3866 using iterator = PhiNodeSetIterator;
3881 size_t FirstValidElement = 0;
3888 if (NodeMap.insert(std::make_pair(
Ptr,
NodeList.size())).second) {
3899 if (NodeMap.erase(
Ptr)) {
3900 SkipRemovedElements(FirstValidElement);
3910 FirstValidElement = 0;
3916 if (FirstValidElement == 0)
3917 SkipRemovedElements(FirstValidElement);
3918 return PhiNodeSetIterator(
this, FirstValidElement);
3922 iterator
end() {
return PhiNodeSetIterator(
this,
NodeList.size()); }
3925 size_t size()
const {
return NodeMap.size(); }
3936 void SkipRemovedElements(
size_t &CurrentIndex) {
3937 while (CurrentIndex <
NodeList.size()) {
3938 auto it = NodeMap.find(
NodeList[CurrentIndex]);
3941 if (it != NodeMap.end() && it->second == CurrentIndex)
3948PhiNodeSetIterator::PhiNodeSetIterator(PhiNodeSet *
const Set,
size_t Start)
3949 :
Set(
Set), CurrentIndex(Start) {}
3951PHINode *PhiNodeSetIterator::operator*()
const {
3953 "PhiNodeSet access out of range");
3954 return Set->NodeList[CurrentIndex];
3957PhiNodeSetIterator &PhiNodeSetIterator::operator++() {
3959 "PhiNodeSet access out of range");
3961 Set->SkipRemovedElements(CurrentIndex);
3965bool PhiNodeSetIterator::operator==(
const PhiNodeSetIterator &RHS)
const {
3966 return CurrentIndex ==
RHS.CurrentIndex;
3969bool PhiNodeSetIterator::operator!=(
const PhiNodeSetIterator &RHS)
const {
3970 return !((*this) ==
RHS);
3976class SimplificationTracker {
3981 PhiNodeSet AllPhiNodes;
3990 auto SV = Storage.
find(V);
3991 if (SV == Storage.
end())
4001 while (!WorkList.
empty()) {
4003 if (!Visited.
insert(
P).second)
4005 if (
auto *PI = dyn_cast<Instruction>(
P))
4007 for (
auto *U : PI->users())
4010 PI->replaceAllUsesWith(V);
4011 if (
auto *
PHI = dyn_cast<PHINode>(PI))
4012 AllPhiNodes.erase(
PHI);
4013 if (
auto *
Select = dyn_cast<SelectInst>(PI))
4015 PI->eraseFromParent();
4025 while (OldReplacement !=
From) {
4027 To = dyn_cast<PHINode>(OldReplacement);
4028 OldReplacement = Get(
From);
4030 assert(To && Get(To) == To &&
"Replacement PHI node is already replaced.");
4032 From->replaceAllUsesWith(To);
4033 AllPhiNodes.erase(
From);
4034 From->eraseFromParent();
4037 PhiNodeSet &newPhiNodes() {
return AllPhiNodes; }
4039 void insertNewPhi(
PHINode *PN) { AllPhiNodes.insert(PN); }
4043 unsigned countNewPhiNodes()
const {
return AllPhiNodes.size(); }
4045 unsigned countNewSelectNodes()
const {
return AllSelectNodes.
size(); }
4047 void destroyNewNodes(
Type *CommonType) {
4050 for (
auto *
I : AllPhiNodes) {
4051 I->replaceAllUsesWith(Dummy);
4052 I->eraseFromParent();
4054 AllPhiNodes.clear();
4055 for (
auto *
I : AllSelectNodes) {
4056 I->replaceAllUsesWith(Dummy);
4057 I->eraseFromParent();
4059 AllSelectNodes.clear();
4064class AddressingModeCombiner {
4066 typedef std::pair<PHINode *, PHINode *> PHIPair;
4073 ExtAddrMode::FieldName DifferentField = ExtAddrMode::NoField;
4076 bool AllAddrModesTrivial =
true;
4079 Type *CommonType =
nullptr;
4088 Value *CommonValue =
nullptr;
4092 : SQ(_SQ), Original(OriginalValue) {}
4094 ~AddressingModeCombiner() { eraseCommonValueIfDead(); }
4106 AllAddrModesTrivial = AllAddrModesTrivial && NewAddrMode.isTrivial();
4109 if (AddrModes.
empty()) {
4117 ExtAddrMode::FieldName ThisDifferentField =
4118 AddrModes[0].compare(NewAddrMode);
4119 if (DifferentField == ExtAddrMode::NoField)
4120 DifferentField = ThisDifferentField;
4121 else if (DifferentField != ThisDifferentField)
4122 DifferentField = ExtAddrMode::MultipleFields;
4125 bool CanHandle = DifferentField != ExtAddrMode::MultipleFields;
4128 CanHandle = CanHandle && DifferentField != ExtAddrMode::ScaleField;
4133 CanHandle = CanHandle && (DifferentField != ExtAddrMode::BaseOffsField ||
4138 CanHandle = CanHandle && (DifferentField != ExtAddrMode::BaseGVField ||
4139 !NewAddrMode.HasBaseReg);
4156 bool combineAddrModes() {
4158 if (AddrModes.
size() == 0)
4162 if (AddrModes.
size() == 1 || DifferentField == ExtAddrMode::NoField)
4167 if (AllAddrModesTrivial)
4170 if (!addrModeCombiningAllowed())
4176 FoldAddrToValueMapping
Map;
4177 if (!initializeMap(Map))
4180 CommonValue = findCommon(Map);
4182 AddrModes[0].SetCombinedField(DifferentField, CommonValue, AddrModes);
4183 return CommonValue !=
nullptr;
4189 void eraseCommonValueIfDead() {
4190 if (CommonValue && CommonValue->
getNumUses() == 0)
4191 if (
Instruction *CommonInst = dyn_cast<Instruction>(CommonValue))
4192 CommonInst->eraseFromParent();
4200 bool initializeMap(FoldAddrToValueMapping &Map) {
4205 for (
auto &AM : AddrModes) {
4206 Value *DV = AM.GetFieldAsValue(DifferentField, IntPtrTy);
4209 if (CommonType && CommonType !=
Type)
4212 Map[AM.OriginalValue] = DV;
4217 assert(CommonType &&
"At least one non-null value must be!");
4218 for (
auto *V : NullValue)
4246 Value *findCommon(FoldAddrToValueMapping &Map) {
4254 SimplificationTracker
ST(SQ);
4259 InsertPlaceholders(Map, TraverseOrder, ST);
4262 FillPlaceholders(Map, TraverseOrder, ST);
4265 ST.destroyNewNodes(CommonType);
4270 unsigned PhiNotMatchedCount = 0;
4272 ST.destroyNewNodes(CommonType);
4276 auto *
Result =
ST.Get(
Map.find(Original)->second);
4278 NumMemoryInstsPhiCreated +=
ST.countNewPhiNodes() + PhiNotMatchedCount;
4279 NumMemoryInstsSelectCreated +=
ST.countNewSelectNodes();
4288 PhiNodeSet &PhiNodesToMatch) {
4295 while (!WorkList.
empty()) {
4297 if (!Visited.
insert(Item).second)
4304 for (
auto *
B : Item.first->blocks()) {
4305 Value *FirstValue = Item.first->getIncomingValueForBlock(
B);
4306 Value *SecondValue = Item.second->getIncomingValueForBlock(
B);
4307 if (FirstValue == SecondValue)
4310 PHINode *FirstPhi = dyn_cast<PHINode>(FirstValue);
4311 PHINode *SecondPhi = dyn_cast<PHINode>(SecondValue);
4317 if (!FirstPhi || !SecondPhi || !PhiNodesToMatch.count(FirstPhi) ||
4322 if (Matcher.
count({FirstPhi, SecondPhi}))
4327 if (MatchedPHIs.
insert(FirstPhi).second)
4328 Matcher.
insert({FirstPhi, SecondPhi});
4330 WorkList.
push_back({FirstPhi, SecondPhi});
4339 bool MatchPhiSet(SimplificationTracker &ST,
bool AllowNewPhiNodes,
4340 unsigned &PhiNotMatchedCount) {
4346 PhiNodeSet &PhiNodesToMatch =
ST.newPhiNodes();
4347 while (PhiNodesToMatch.size()) {
4351 WillNotMatch.
clear();
4355 bool IsMatched =
false;
4356 for (
auto &
P :
PHI->getParent()->phis()) {
4358 if (PhiNodesToMatch.count(&
P))
4360 if ((IsMatched = MatchPhiNode(
PHI, &
P, Matched, PhiNodesToMatch)))
4365 for (
auto M : Matched)
4371 for (
auto MV : Matched)
4372 ST.ReplacePhi(MV.first, MV.second);
4377 if (!AllowNewPhiNodes)
4380 PhiNotMatchedCount += WillNotMatch.
size();
4381 for (
auto *
P : WillNotMatch)
4382 PhiNodesToMatch.erase(
P);
4387 void FillPlaceholders(FoldAddrToValueMapping &Map,
4389 SimplificationTracker &ST) {
4390 while (!TraverseOrder.
empty()) {
4392 assert(
Map.contains(Current) &&
"No node to fill!!!");
4397 auto *CurrentSelect = cast<SelectInst>(Current);
4398 auto *TrueValue = CurrentSelect->getTrueValue();
4399 assert(
Map.contains(TrueValue) &&
"No True Value!");
4400 Select->setTrueValue(
ST.Get(Map[TrueValue]));
4401 auto *FalseValue = CurrentSelect->getFalseValue();
4402 assert(
Map.contains(FalseValue) &&
"No False Value!");
4403 Select->setFalseValue(
ST.Get(Map[FalseValue]));
4406 auto *
PHI = cast<PHINode>(V);
4409 Value *PV = cast<PHINode>(Current)->getIncomingValueForBlock(
B);
4410 assert(
Map.contains(PV) &&
"No predecessor Value!");
4411 PHI->addIncoming(
ST.Get(Map[PV]),
B);
4414 Map[Current] =
ST.Simplify(V);
4423 void InsertPlaceholders(FoldAddrToValueMapping &Map,
4425 SimplificationTracker &ST) {
4427 assert((isa<PHINode>(Original) || isa<SelectInst>(Original)) &&
4428 "Address must be a Phi or Select node");
4431 while (!Worklist.
empty()) {
4434 if (
Map.contains(Current))
4440 if (
SelectInst *CurrentSelect = dyn_cast<SelectInst>(Current)) {
4445 CurrentSelect->getName(),
4446 CurrentSelect->getIterator(), CurrentSelect);
4450 Worklist.
push_back(CurrentSelect->getTrueValue());
4451 Worklist.
push_back(CurrentSelect->getFalseValue());
4454 PHINode *CurrentPhi = cast<PHINode>(Current);
4459 ST.insertNewPhi(
PHI);
4465 bool addrModeCombiningAllowed() {
4468 switch (DifferentField) {
4471 case ExtAddrMode::BaseRegField:
4473 case ExtAddrMode::BaseGVField:
4475 case ExtAddrMode::BaseOffsField:
4477 case ExtAddrMode::ScaledRegField:
4487bool AddressingModeMatcher::matchScaledValue(
Value *ScaleReg, int64_t Scale,
4492 return matchAddr(ScaleReg,
Depth);
4507 TestAddrMode.
Scale += Scale;
4522 Value *AddLHS =
nullptr;
4523 if (isa<Instruction>(ScaleReg) &&
4526 TestAddrMode.InBounds =
false;
4533 AddrModeInsts.
push_back(cast<Instruction>(ScaleReg));
4543 auto GetConstantStep =
4544 [
this](
const Value *
V) -> std::optional<std::pair<Instruction *, APInt>> {
4545 auto *PN = dyn_cast<PHINode>(V);
4547 return std::nullopt;
4550 return std::nullopt;
4557 if (
auto *OIVInc = dyn_cast<OverflowingBinaryOperator>(IVInc->first))
4558 if (OIVInc->hasNoSignedWrap() || OIVInc->hasNoUnsignedWrap())
4559 return std::nullopt;
4560 if (
auto *ConstantStep = dyn_cast<ConstantInt>(IVInc->second))
4561 return std::make_pair(IVInc->first, ConstantStep->getValue());
4562 return std::nullopt;
4577 if (
auto IVStep = GetConstantStep(ScaleReg)) {
4584 APInt Step = IVStep->second;
4586 if (
Offset.isSignedIntN(64)) {
4587 TestAddrMode.InBounds =
false;
4589 TestAddrMode.BaseOffs -=
Offset.getLimitedValue();
4594 getDTFn().
dominates(IVInc, MemoryInst)) {
4595 AddrModeInsts.
push_back(cast<Instruction>(IVInc));
4614 switch (
I->getOpcode()) {
4615 case Instruction::BitCast:
4616 case Instruction::AddrSpaceCast:
4618 if (
I->getType() ==
I->getOperand(0)->getType())
4620 return I->getType()->isIntOrPtrTy();
4621 case Instruction::PtrToInt:
4624 case Instruction::IntToPtr:
4627 case Instruction::Add:
4629 case Instruction::Mul:
4630 case Instruction::Shl:
4632 return isa<ConstantInt>(
I->getOperand(1));
4633 case Instruction::GetElementPtr:
4646 Instruction *PromotedInst = dyn_cast<Instruction>(Val);
4661class TypePromotionHelper {
4664 static void addPromotedInst(InstrToOrigTy &PromotedInsts,
4666 ExtType ExtTy = IsSExt ? SignExtension : ZeroExtension;
4667 InstrToOrigTy::iterator It = PromotedInsts.find(ExtOpnd);
4668 if (It != PromotedInsts.end()) {
4671 if (It->second.getInt() == ExtTy)
4677 ExtTy = BothExtension;
4679 PromotedInsts[ExtOpnd] = TypeIsSExt(ExtOpnd->
getType(), ExtTy);
4686 static const Type *getOrigType(
const InstrToOrigTy &PromotedInsts,
4688 ExtType ExtTy = IsSExt ? SignExtension : ZeroExtension;
4689 InstrToOrigTy::const_iterator It = PromotedInsts.find(Opnd);
4690 if (It != PromotedInsts.end() && It->second.getInt() == ExtTy)
4691 return It->second.getPointer();
4706 static bool canGetThrough(
const Instruction *Inst,
Type *ConsideredExtType,
4707 const InstrToOrigTy &PromotedInsts,
bool IsSExt);
4711 static bool shouldExtOperand(
const Instruction *Inst,
int OpIdx) {
4712 return !(isa<SelectInst>(Inst) && OpIdx == 0);
4724 static Value *promoteOperandForTruncAndAnyExt(
4726 InstrToOrigTy &PromotedInsts,
unsigned &CreatedInstsCost,
4740 TypePromotionTransaction &TPT,
4741 InstrToOrigTy &PromotedInsts,
4742 unsigned &CreatedInstsCost,
4748 static Value *signExtendOperandForOther(
4750 InstrToOrigTy &PromotedInsts,
unsigned &CreatedInstsCost,
4753 return promoteOperandForOther(Ext, TPT, PromotedInsts, CreatedInstsCost,
4754 Exts, Truncs, TLI,
true);
4758 static Value *zeroExtendOperandForOther(
4760 InstrToOrigTy &PromotedInsts,
unsigned &CreatedInstsCost,
4763 return promoteOperandForOther(Ext, TPT, PromotedInsts, CreatedInstsCost,
4764 Exts, Truncs, TLI,
false);
4770 InstrToOrigTy &PromotedInsts,
4771 unsigned &CreatedInstsCost,
4785 static Action getAction(
Instruction *Ext,
const SetOfInstrs &InsertedInsts,
4787 const InstrToOrigTy &PromotedInsts);
4792bool TypePromotionHelper::canGetThrough(
const Instruction *Inst,
4793 Type *ConsideredExtType,
4794 const InstrToOrigTy &PromotedInsts,
4803 if (isa<ZExtInst>(Inst))
4807 if (IsSExt && isa<SExtInst>(Inst))
4812 if (
const auto *BinOp = dyn_cast<BinaryOperator>(Inst))
4813 if (isa<OverflowingBinaryOperator>(BinOp) &&
4814 ((!IsSExt && BinOp->hasNoUnsignedWrap()) ||
4815 (IsSExt && BinOp->hasNoSignedWrap())))
4819 if ((Inst->
getOpcode() == Instruction::And ||
4824 if (Inst->
getOpcode() == Instruction::Xor) {
4826 if (
const auto *Cst = dyn_cast<ConstantInt>(Inst->
getOperand(1)))
4827 if (!Cst->getValue().isAllOnes())
4836 if (Inst->
getOpcode() == Instruction::LShr && !IsSExt)
4845 const auto *ExtInst = cast<const Instruction>(*Inst->
user_begin());
4846 if (ExtInst->hasOneUse()) {
4847 const auto *AndInst = dyn_cast<const Instruction>(*ExtInst->user_begin());
4848 if (AndInst && AndInst->getOpcode() == Instruction::And) {
4849 const auto *Cst = dyn_cast<ConstantInt>(AndInst->getOperand(1));
4859 if (!isa<TruncInst>(Inst))
4873 Instruction *Opnd = dyn_cast<Instruction>(OpndVal);
4881 const Type *OpndType = getOrigType(PromotedInsts, Opnd, IsSExt);
4884 else if ((IsSExt && isa<SExtInst>(Opnd)) || (!IsSExt && isa<ZExtInst>(Opnd)))
4894TypePromotionHelper::Action TypePromotionHelper::getAction(
4895 Instruction *Ext,
const SetOfInstrs &InsertedInsts,
4897 assert((isa<SExtInst>(Ext) || isa<ZExtInst>(Ext)) &&
4898 "Unexpected instruction type");
4899 Instruction *ExtOpnd = dyn_cast<Instruction>(
Ext->getOperand(0));
4901 bool IsSExt = isa<SExtInst>(Ext);
4905 if (!ExtOpnd || !canGetThrough(ExtOpnd, ExtTy, PromotedInsts, IsSExt))
4911 if (isa<TruncInst>(ExtOpnd) && InsertedInsts.count(ExtOpnd))
4916 if (isa<SExtInst>(ExtOpnd) || isa<TruncInst>(ExtOpnd) ||
4917 isa<ZExtInst>(ExtOpnd))
4918 return promoteOperandForTruncAndAnyExt;
4924 return IsSExt ? signExtendOperandForOther : zeroExtendOperandForOther;
4927Value *TypePromotionHelper::promoteOperandForTruncAndAnyExt(
4929 InstrToOrigTy &PromotedInsts,
unsigned &CreatedInstsCost,
4935 Value *ExtVal = SExt;
4936 bool HasMergedNonFreeExt =
false;
4937 if (isa<ZExtInst>(SExtOpnd)) {
4940 HasMergedNonFreeExt = !TLI.
isExtFree(SExtOpnd);
4944 TPT.eraseInstruction(SExt);
4949 TPT.setOperand(SExt, 0, SExtOpnd->
getOperand(0));
4951 CreatedInstsCost = 0;
4955 TPT.eraseInstruction(SExtOpnd);
4958 Instruction *ExtInst = dyn_cast<Instruction>(ExtVal);
4963 CreatedInstsCost = !TLI.
isExtFree(ExtInst) && !HasMergedNonFreeExt;
4971 TPT.eraseInstruction(ExtInst, NextVal);
4975Value *TypePromotionHelper::promoteOperandForOther(
4977 InstrToOrigTy &PromotedInsts,
unsigned &CreatedInstsCost,
4984 CreatedInstsCost = 0;
4990 Value *Trunc = TPT.createTrunc(Ext, ExtOpnd->
getType());
4991 if (
Instruction *ITrunc = dyn_cast<Instruction>(Trunc)) {
4993 ITrunc->moveAfter(ExtOpnd);
4998 TPT.replaceAllUsesWith(ExtOpnd, Trunc);
5001 TPT.setOperand(Ext, 0, ExtOpnd);
5011 addPromotedInst(PromotedInsts, ExtOpnd, IsSExt);
5013 TPT.mutateType(ExtOpnd,
Ext->getType());
5015 TPT.replaceAllUsesWith(Ext, ExtOpnd);
5018 for (
int OpIdx = 0, EndOpIdx = ExtOpnd->
getNumOperands(); OpIdx != EndOpIdx;
5022 !shouldExtOperand(ExtOpnd, OpIdx)) {
5028 if (
const ConstantInt *Cst = dyn_cast<ConstantInt>(Opnd)) {
5030 unsigned BitWidth =
Ext->getType()->getIntegerBitWidth();
5033 TPT.setOperand(ExtOpnd, OpIdx, ConstantInt::get(
Ext->getType(), CstVal));
5037 if (isa<UndefValue>(Opnd)) {
5044 Value *ValForExtOpnd = IsSExt
5045 ? TPT.createSExt(ExtOpnd, Opnd,
Ext->getType())
5046 : TPT.createZExt(ExtOpnd, Opnd,
Ext->getType());
5047 TPT.setOperand(ExtOpnd, OpIdx, ValForExtOpnd);
5048 Instruction *InstForExtOpnd = dyn_cast<Instruction>(ValForExtOpnd);
5049 if (!InstForExtOpnd)
5055 CreatedInstsCost += !TLI.
isExtFree(InstForExtOpnd);
5058 TPT.eraseInstruction(Ext);
5070bool AddressingModeMatcher::isPromotionProfitable(
5071 unsigned NewCost,
unsigned OldCost,
Value *PromotedOperand)
const {
5072 LLVM_DEBUG(
dbgs() <<
"OldCost: " << OldCost <<
"\tNewCost: " << NewCost
5077 if (NewCost > OldCost)
5079 if (NewCost < OldCost)
5098bool AddressingModeMatcher::matchOperationAddr(
User *AddrInst,
unsigned Opcode,
5110 case Instruction::PtrToInt:
5113 case Instruction::IntToPtr: {
5121 case Instruction::BitCast:
5131 case Instruction::AddrSpaceCast: {
5139 case Instruction::Add: {
5143 unsigned OldSize = AddrModeInsts.
size();
5148 TypePromotionTransaction::ConstRestorationPt LastKnownGood =
5149 TPT.getRestorationPoint();
5153 int First = 0, Second = 1;
5155 && !isa<ConstantInt>(AddrInst->
getOperand(Second)))
5164 AddrModeInsts.
resize(OldSize);
5165 TPT.rollback(LastKnownGood);
5175 AddrModeInsts.
resize(OldSize);
5176 TPT.rollback(LastKnownGood);
5182 case Instruction::Mul:
5183 case Instruction::Shl: {
5187 if (!RHS ||
RHS->getBitWidth() > 64)
5189 int64_t Scale = Opcode == Instruction::Shl
5190 ? 1LL <<
RHS->getLimitedValue(
RHS->getBitWidth() - 1)
5191 :
RHS->getSExtValue();
5195 case Instruction::GetElementPtr: {
5198 int VariableOperand = -1;
5199 unsigned VariableScale = 0;
5201 int64_t ConstantOffset = 0;
5203 for (
unsigned i = 1, e = AddrInst->
getNumOperands(); i != e; ++i, ++GTI) {
5207 cast<ConstantInt>(AddrInst->
getOperand(i))->getZExtValue();
5217 dyn_cast<ConstantInt>(AddrInst->
getOperand(i))) {
5225 if (VariableOperand != -1)
5229 VariableOperand = i;
5237 if (VariableOperand == -1) {
5238 AddrMode.BaseOffs += ConstantOffset;
5240 if (!cast<GEPOperator>(AddrInst)->isInBounds())
5244 AddrMode.BaseOffs -= ConstantOffset;
5248 ConstantOffset > 0) {
5254 auto *BaseI = dyn_cast<Instruction>(
Base);
5255 auto *
GEP = cast<GetElementPtrInst>(AddrInst);
5256 if (isa<Argument>(
Base) || isa<GlobalValue>(
Base) ||
5257 (BaseI && !isa<CastInst>(BaseI) &&
5258 !isa<GetElementPtrInst>(BaseI))) {
5262 : &
GEP->getFunction()->getEntryBlock();
5264 LargeOffsetGEP = std::make_pair(
GEP, ConstantOffset);
5273 unsigned OldSize = AddrModeInsts.
size();
5276 AddrMode.BaseOffs += ConstantOffset;
5277 if (!cast<GEPOperator>(AddrInst)->isInBounds())
5285 AddrModeInsts.
resize(OldSize);
5293 if (!matchScaledValue(AddrInst->
getOperand(VariableOperand), VariableScale,
5298 AddrModeInsts.
resize(OldSize);
5303 AddrMode.BaseOffs += ConstantOffset;
5304 if (!matchScaledValue(AddrInst->
getOperand(VariableOperand),
5305 VariableScale,
Depth)) {
5308 AddrModeInsts.
resize(OldSize);
5315 case Instruction::SExt:
5316 case Instruction::ZExt: {
5323 TypePromotionHelper::Action TPH =
5324 TypePromotionHelper::getAction(Ext, InsertedInsts, TLI, PromotedInsts);
5328 TypePromotionTransaction::ConstRestorationPt LastKnownGood =
5329 TPT.getRestorationPoint();
5330 unsigned CreatedInstsCost = 0;
5332 Value *PromotedOperand =
5333 TPH(Ext, TPT, PromotedInsts, CreatedInstsCost,
nullptr,
nullptr, TLI);
5348 assert(PromotedOperand &&
5349 "TypePromotionHelper should have filtered out those cases");
5352 unsigned OldSize = AddrModeInsts.
size();
5354 if (!matchAddr(PromotedOperand,
Depth) ||
5359 !isPromotionProfitable(CreatedInstsCost,
5360 ExtCost + (AddrModeInsts.
size() - OldSize),
5363 AddrModeInsts.
resize(OldSize);
5364 LLVM_DEBUG(
dbgs() <<
"Sign extension does not pay off: rollback\n");
5365 TPT.rollback(LastKnownGood);
5370 case Instruction::Call:
5372 if (
II->getIntrinsicID() == Intrinsic::threadlocal_address) {
5388bool AddressingModeMatcher::matchAddr(
Value *
Addr,
unsigned Depth) {
5391 TypePromotionTransaction::ConstRestorationPt LastKnownGood =
5392 TPT.getRestorationPoint();
5411 unsigned OldSize = AddrModeInsts.
size();
5414 bool MovedAway =
false;
5415 if (matchOperationAddr(
I,
I->getOpcode(),
Depth, &MovedAway)) {
5423 if (
I->hasOneUse() ||
5424 isProfitableToFoldIntoAddressingMode(
I, BackupAddrMode,
AddrMode)) {
5431 AddrModeInsts.
resize(OldSize);
5432 TPT.rollback(LastKnownGood);
5435 if (matchOperationAddr(CE,
CE->getOpcode(),
Depth))
5437 TPT.rollback(LastKnownGood);
5438 }
else if (isa<ConstantPointerNull>(
Addr)) {
5464 TPT.rollback(LastKnownGood);
5483 if (OpInfo.CallOperandVal == OpVal &&
5485 !OpInfo.isIndirect))
5501 if (!ConsideredInsts.
insert(
I).second)
5509 for (
Use &U :
I->uses()) {
5515 Instruction *UserI = cast<Instruction>(U.getUser());
5516 if (
LoadInst *LI = dyn_cast<LoadInst>(UserI)) {
5517 MemoryUses.push_back({&U, LI->getType()});
5521 if (
StoreInst *SI = dyn_cast<StoreInst>(UserI)) {
5524 MemoryUses.push_back({&U, SI->getValueOperand()->
getType()});
5531 MemoryUses.push_back({&U, RMW->getValOperand()->
getType()});
5538 MemoryUses.push_back({&U, CmpX->getCompareOperand()->
getType()});
5542 if (
CallInst *CI = dyn_cast<CallInst>(UserI)) {
5543 if (CI->hasFnAttr(Attribute::Cold)) {
5550 InlineAsm *IA = dyn_cast<InlineAsm>(CI->getCalledOperand());
5561 PSI, BFI, SeenInsts))
5572 unsigned SeenInsts = 0;
5575 PSI, BFI, SeenInsts);
5583bool AddressingModeMatcher::valueAlreadyLiveAtInst(
Value *Val,
5585 Value *KnownLive2) {
5587 if (Val ==
nullptr || Val == KnownLive1 || Val == KnownLive2)
5591 if (!isa<Instruction>(Val) && !isa<Argument>(Val))
5597 if (
AllocaInst *AI = dyn_cast<AllocaInst>(Val))
5628bool AddressingModeMatcher::isProfitableToFoldIntoAddressingMode(
5630 if (IgnoreProfitability)
5648 if (valueAlreadyLiveAtInst(ScaledReg, AMBefore.
BaseReg, AMBefore.
ScaledReg))
5649 ScaledReg =
nullptr;
5653 if (!BaseReg && !ScaledReg)
5674 for (
const std::pair<Use *, Type *> &Pair : MemoryUses) {
5676 Instruction *UserI = cast<Instruction>(Pair.first->getUser());
5677 Type *AddressAccessTy = Pair.second;
5678 unsigned AS =
Address->getType()->getPointerAddressSpace();
5684 std::pair<AssertingVH<GetElementPtrInst>, int64_t> LargeOffsetGEP(
nullptr,
5686 TypePromotionTransaction::ConstRestorationPt LastKnownGood =
5687 TPT.getRestorationPoint();
5688 AddressingModeMatcher Matcher(MatchedAddrModeInsts, TLI,
TRI, LI, getDTFn,
5689 AddressAccessTy, AS, UserI, Result,
5690 InsertedInsts, PromotedInsts, TPT,
5691 LargeOffsetGEP, OptSize, PSI, BFI);
5692 Matcher.IgnoreProfitability =
true;
5693 bool Success = Matcher.matchAddr(Address, 0);
5700 TPT.rollback(LastKnownGood);
5706 MatchedAddrModeInsts.
clear();
5716 return I->getParent() != BB;
5740 Type *AccessTy,
unsigned AddrSpace) {
5752 bool PhiOrSelectSeen =
false;
5755 AddressingModeCombiner AddrModes(SQ,
Addr);
5756 TypePromotionTransaction TPT(RemovedInsts);
5757 TypePromotionTransaction::ConstRestorationPt LastKnownGood =
5758 TPT.getRestorationPoint();
5759 while (!worklist.
empty()) {
5771 if (!Visited.
insert(V).second)
5775 if (
PHINode *
P = dyn_cast<PHINode>(V)) {
5777 PhiOrSelectSeen =
true;
5781 if (
SelectInst *SI = dyn_cast<SelectInst>(V)) {
5784 PhiOrSelectSeen =
true;
5791 AddrModeInsts.
clear();
5792 std::pair<AssertingVH<GetElementPtrInst>, int64_t> LargeOffsetGEP(
nullptr,
5797 auto getDTFn = [MemoryInst,
this]() ->
const DominatorTree & {
5799 return this->getDT(*
F);
5801 ExtAddrMode NewAddrMode = AddressingModeMatcher::Match(
5802 V, AccessTy, AddrSpace, MemoryInst, AddrModeInsts, *TLI, *LI, getDTFn,
5803 *
TRI, InsertedInsts, PromotedInsts, TPT, LargeOffsetGEP, OptSize, PSI,
5811 LargeOffsetGEPMap[
GEP->getPointerOperand()].push_back(LargeOffsetGEP);
5812 LargeOffsetGEPID.
insert(std::make_pair(
GEP, LargeOffsetGEPID.
size()));
5815 NewAddrMode.OriginalValue =
V;
5816 if (!AddrModes.addNewAddrMode(NewAddrMode))
5823 if (!AddrModes.combineAddrModes()) {
5824 TPT.rollback(LastKnownGood);
5836 if (!PhiOrSelectSeen &&
none_of(AddrModeInsts, [&](
Value *V) {
5858 Type *IntPtrTy =
DL->getIntPtrType(
Addr->getType());
5861 <<
" for " << *MemoryInst <<
"\n");
5864 Addr->getType()->getPointerAddressSpace() &&
5865 !
DL->isNonIntegralPointerType(
Addr->getType())) {
5871 SunkAddr = Builder.CreatePtrToInt(SunkAddr, IntPtrTy,
"sunkaddr");
5873 Builder.CreateIntToPtr(SunkAddr,
Addr->getType(),
"sunkaddr");
5875 SunkAddr = Builder.CreatePointerCast(SunkAddr,
Addr->getType());
5882 <<
" for " << *MemoryInst <<
"\n");
5883 Value *ResultPtr =
nullptr, *ResultIndex =
nullptr;
5894 if (ResultPtr ||
AddrMode.Scale != 1)
5916 if (BaseGV !=
nullptr) {
5921 ResultPtr = Builder.CreateThreadLocalAddress(BaseGV);
5930 if (!
DL->isNonIntegralPointerType(
Addr->getType())) {
5931 if (!ResultPtr &&
AddrMode.BaseReg) {
5932 ResultPtr = Builder.CreateIntToPtr(
AddrMode.BaseReg,
Addr->getType(),
5935 }
else if (!ResultPtr &&
AddrMode.Scale == 1) {
5936 ResultPtr = Builder.CreateIntToPtr(
AddrMode.ScaledReg,
Addr->getType(),
5945 }
else if (!ResultPtr) {
5949 Builder.getPtrTy(
Addr->getType()->getPointerAddressSpace());
5958 if (
V->getType() != IntPtrTy)
5959 V = Builder.CreateIntCast(V, IntPtrTy,
true,
"sunkaddr");
5967 if (
V->getType() == IntPtrTy) {
5971 cast<IntegerType>(
V->getType())->getBitWidth() &&
5972 "We can't transform if ScaledReg is too narrow");
5973 V = Builder.CreateTrunc(V, IntPtrTy,
"sunkaddr");
5977 V = Builder.CreateMul(V, ConstantInt::get(IntPtrTy,
AddrMode.Scale),
5980 ResultIndex = Builder.CreateAdd(ResultIndex, V,
"sunkaddr");
5991 if (ResultPtr->
getType() != I8PtrTy)
5992 ResultPtr = Builder.CreatePointerCast(ResultPtr, I8PtrTy);
5993 ResultPtr = Builder.CreatePtrAdd(ResultPtr, ResultIndex,
"sunkaddr",
6001 SunkAddr = ResultPtr;
6003 if (ResultPtr->
getType() != I8PtrTy)
6004 ResultPtr = Builder.CreatePointerCast(ResultPtr, I8PtrTy);
6005 SunkAddr = Builder.CreatePtrAdd(ResultPtr, ResultIndex,
"sunkaddr",
6011 Addr->getType()->getPointerAddressSpace() &&
6012 !
DL->isNonIntegralPointerType(
Addr->getType())) {
6018 SunkAddr = Builder.CreatePtrToInt(SunkAddr, IntPtrTy,
"sunkaddr");
6020 Builder.CreateIntToPtr(SunkAddr,
Addr->getType(),
"sunkaddr");
6022 SunkAddr = Builder.CreatePointerCast(SunkAddr,
Addr->getType());
6031 PointerType *ScalePtrTy = dyn_cast_or_null<PointerType>(ScaleTy);
6032 if (
DL->isNonIntegralPointerType(
Addr->getType()) ||
6033 (BasePtrTy &&
DL->isNonIntegralPointerType(BasePtrTy)) ||
6034 (ScalePtrTy &&
DL->isNonIntegralPointerType(ScalePtrTy)) ||
6036 DL->isNonIntegralPointerType(
AddrMode.BaseGV->getType())))
6040 <<
" for " << *MemoryInst <<
"\n");
6041 Type *IntPtrTy =
DL->getIntPtrType(
Addr->getType());
6051 if (
V->getType()->isPointerTy())
6052 V = Builder.CreatePtrToInt(V, IntPtrTy,
"sunkaddr");
6053 if (
V->getType() != IntPtrTy)
6054 V = Builder.CreateIntCast(V, IntPtrTy,
true,
"sunkaddr");
6061 if (
V->getType() == IntPtrTy) {
6063 }
else if (
V->getType()->isPointerTy()) {
6064 V = Builder.CreatePtrToInt(V, IntPtrTy,
"sunkaddr");
6065 }
else if (cast<IntegerType>(IntPtrTy)->
getBitWidth() <
6066 cast<IntegerType>(
V->getType())->getBitWidth()) {
6067 V = Builder.CreateTrunc(V, IntPtrTy,
"sunkaddr");
6074 Instruction *
I = dyn_cast_or_null<Instruction>(Result);
6076 I->eraseFromParent();
6080 V = Builder.CreateMul(V, ConstantInt::get(IntPtrTy,
AddrMode.Scale),
6083 Result = Builder.CreateAdd(Result, V,
"sunkaddr");
6090 if (BaseGV !=
nullptr) {
6093 BaseGVPtr = Builder.CreateThreadLocalAddress(BaseGV);
6097 Value *
V = Builder.CreatePtrToInt(BaseGVPtr, IntPtrTy,
"sunkaddr");
6099 Result = Builder.CreateAdd(Result, V,
"sunkaddr");
6108 Result = Builder.CreateAdd(Result, V,
"sunkaddr");
6116 SunkAddr = Builder.CreateIntToPtr(Result,
Addr->getType(),
"sunkaddr");
6127 resetIteratorIfInvalidatedWhileCalling(CurInstIterator->getParent(), [&]() {
6128 RecursivelyDeleteTriviallyDeadInstructions(
6129 Repl, TLInfo, nullptr,
6130 [&](Value *V) { removeAllAssertingVHReferences(V); });
6154bool CodeGenPrepare::optimizeGatherScatterInst(
Instruction *MemoryInst,
6158 if (
const auto *
GEP = dyn_cast<GetElementPtrInst>(
Ptr)) {
6160 if (!
GEP->hasIndices())
6170 bool RewriteGEP =
false;
6172 if (Ops[0]->
getType()->isVectorTy()) {
6179 unsigned FinalIndex = Ops.size() - 1;
6184 for (
unsigned i = 1; i < FinalIndex; ++i) {
6185 auto *
C = dyn_cast<Constant>(Ops[i]);
6188 if (isa<VectorType>(
C->getType()))
6189 C =
C->getSplatValue();
6190 auto *CI = dyn_cast_or_null<ConstantInt>(
C);
6191 if (!CI || !CI->
isZero())
6198 if (Ops[FinalIndex]->
getType()->isVectorTy()) {
6200 auto *
C = dyn_cast<ConstantInt>(V);
6202 if (!
C || !
C->isZero()) {
6203 Ops[FinalIndex] =
V;
6211 if (!RewriteGEP && Ops.size() == 2)
6214 auto NumElts = cast<VectorType>(
Ptr->getType())->getElementCount();
6218 Type *SourceTy =
GEP->getSourceElementType();
6219 Type *ScalarIndexTy =
DL->getIndexType(Ops[0]->
getType()->getScalarType());
6223 if (!Ops[FinalIndex]->
getType()->isVectorTy()) {
6224 NewAddr = Builder.CreateGEP(SourceTy, Ops[0],
ArrayRef(Ops).drop_front());
6225 auto *IndexTy = VectorType::get(ScalarIndexTy, NumElts);
6227 SourceTy,
ArrayRef(Ops).drop_front());
6235 if (Ops.size() != 2) {
6241 SourceTy,
ArrayRef(Ops).drop_front());
6245 NewAddr = Builder.CreateGEP(SourceTy,
Base, Index);
6247 }
else if (!isa<Constant>(
Ptr)) {
6254 auto NumElts = cast<VectorType>(
Ptr->getType())->getElementCount();
6259 Type *ScalarIndexTy =
DL->getIndexType(
V->getType()->getScalarType());
6260 auto *IndexTy = VectorType::get(ScalarIndexTy, NumElts);
6263 Intrinsic::masked_gather) {
6267 Intrinsic::masked_scatter);
6280 if (
Ptr->use_empty())
6282 Ptr, TLInfo,
nullptr,
6283 [&](
Value *V) { removeAllAssertingVHReferences(V); });
6290bool CodeGenPrepare::optimizeInlineAsmInst(
CallInst *CS) {
6291 bool MadeChange =
false;
6294 TM->getSubtargetImpl(*CS->
getFunction())->getRegisterInfo();
6304 OpInfo.isIndirect) {
6306 MadeChange |= optimizeMemoryInst(CS, OpVal, OpVal->
getType(), ~0u);
6319 bool IsSExt = isa<SExtInst>(FirstUser);
6323 if ((IsSExt && !isa<SExtInst>(UI)) || (!IsSExt && !isa<ZExtInst>(UI)))
6369bool CodeGenPrepare::tryToPromoteExts(
6372 unsigned CreatedInstsCost) {
6373 bool Promoted =
false;
6376 for (
auto *
I : Exts) {
6378 if (isa<LoadInst>(
I->getOperand(0))) {
6391 TypePromotionHelper::Action TPH =
6392 TypePromotionHelper::getAction(
I, InsertedInsts, *TLI, PromotedInsts);
6401 TypePromotionTransaction::ConstRestorationPt LastKnownGood =
6402 TPT.getRestorationPoint();
6404 unsigned NewCreatedInstsCost = 0;
6407 Value *PromotedVal = TPH(
I, TPT, PromotedInsts, NewCreatedInstsCost,
6408 &NewExts,
nullptr, *TLI);
6410 "TypePromotionHelper should have filtered out those cases");
6420 long long TotalCreatedInstsCost = CreatedInstsCost + NewCreatedInstsCost;
6423 TotalCreatedInstsCost =
6424 std::max((
long long)0, (TotalCreatedInstsCost - ExtCost));
6426 (TotalCreatedInstsCost > 1 ||
6428 (ExtCost == 0 && NewExts.
size() > 1))) {
6432 TPT.rollback(LastKnownGood);
6438 (void)tryToPromoteExts(TPT, NewExts, NewlyMovedExts, TotalCreatedInstsCost);
6439 bool NewPromoted =
false;
6440 for (
auto *ExtInst : NewlyMovedExts) {
6441 Instruction *MovedExt = cast<Instruction>(ExtInst);
6445 if (isa<LoadInst>(ExtOperand) &&
6450 ProfitablyMovedExts.
push_back(MovedExt);
6457 TPT.rollback(LastKnownGood);
6468bool CodeGenPrepare::mergeSExts(
Function &
F) {
6469 bool Changed =
false;
6470 for (
auto &Entry : ValToSExtendedUses) {
6471 SExts &Insts =
Entry.second;
6474 if (RemovedInsts.count(Inst) || !isa<SExtInst>(Inst) ||
6477 bool inserted =
false;
6478 for (
auto &Pt : CurPts) {
6481 RemovedInsts.insert(Pt);
6482 Pt->removeFromParent();
6493 RemovedInsts.insert(Inst);
6500 CurPts.push_back(Inst);
6542bool CodeGenPrepare::splitLargeGEPOffsets() {
6543 bool Changed =
false;
6544 for (
auto &Entry : LargeOffsetGEPMap) {
6547 &LargeOffsetGEPs =
Entry.second;
6548 auto compareGEPOffset =
6549 [&](
const std::pair<GetElementPtrInst *, int64_t> &
LHS,
6550 const std::pair<GetElementPtrInst *, int64_t> &
RHS) {
6551 if (
LHS.first ==
RHS.first)
6553 if (
LHS.second !=
RHS.second)
6554 return LHS.second <
RHS.second;
6555 return LargeOffsetGEPID[
LHS.first] < LargeOffsetGEPID[
RHS.first];
6558 llvm::sort(LargeOffsetGEPs, compareGEPOffset);
6561 if (LargeOffsetGEPs.
front().second == LargeOffsetGEPs.
back().second)
6564 int64_t BaseOffset = LargeOffsetGEPs.
begin()->second;
6565 Value *NewBaseGEP =
nullptr;
6567 auto createNewBase = [&](int64_t BaseOffset,
Value *OldBase,
6570 Type *PtrIdxTy =
DL->getIndexType(
GEP->getType());
6572 PointerType::get(Ctx,
GEP->getType()->getPointerAddressSpace());
6576 if (
auto *BaseI = dyn_cast<Instruction>(OldBase)) {
6580 if (isa<PHINode>(BaseI))
6582 else if (
InvokeInst *Invoke = dyn_cast<InvokeInst>(BaseI)) {
6584 SplitEdge(NewBaseInsertBB, Invoke->getNormalDest(), DT.get(), LI);
6587 NewBaseInsertPt = std::next(BaseI->getIterator());
6594 IRBuilder<> NewBaseBuilder(NewBaseInsertBB, NewBaseInsertPt);
6596 Value *BaseIndex = ConstantInt::get(PtrIdxTy, BaseOffset);
6597 NewBaseGEP = OldBase;
6598 if (NewBaseGEP->
getType() != I8PtrTy)
6599 NewBaseGEP = NewBaseBuilder.CreatePointerCast(NewBaseGEP, I8PtrTy);
6601 NewBaseBuilder.CreatePtrAdd(NewBaseGEP, BaseIndex,
"splitgep");
6602 NewGEPBases.
insert(NewBaseGEP);
6608 LargeOffsetGEPs.
front().second, LargeOffsetGEPs.
back().second)) {
6609 BaseOffset = PreferBase;
6612 createNewBase(BaseOffset, OldBase, BaseGEP);
6615 auto *LargeOffsetGEP = LargeOffsetGEPs.
begin();
6616 while (LargeOffsetGEP != LargeOffsetGEPs.
end()) {
6618 int64_t
Offset = LargeOffsetGEP->second;
6619 if (
Offset != BaseOffset) {
6626 GEP->getResultElementType(),
6627 GEP->getAddressSpace())) {
6633 NewBaseGEP =
nullptr;
6638 Type *PtrIdxTy =
DL->getIndexType(
GEP->getType());
6643 createNewBase(BaseOffset, OldBase,
GEP);
6647 Value *NewGEP = NewBaseGEP;
6648 if (
Offset != BaseOffset) {
6651 NewGEP = Builder.CreatePtrAdd(NewBaseGEP, Index);
6655 LargeOffsetGEP = LargeOffsetGEPs.
erase(LargeOffsetGEP);
6656 GEP->eraseFromParent();
6663bool CodeGenPrepare::optimizePhiType(
6670 Type *PhiTy =
I->getType();
6671 Type *ConvertTy =
nullptr;
6673 (!
I->getType()->isIntegerTy() && !
I->getType()->isFloatingPointTy()))
6689 bool AnyAnchored =
false;
6691 while (!Worklist.
empty()) {
6694 if (
auto *Phi = dyn_cast<PHINode>(
II)) {
6696 for (
Value *V :
Phi->incoming_values()) {
6697 if (
auto *OpPhi = dyn_cast<PHINode>(V)) {
6698 if (!PhiNodes.
count(OpPhi)) {
6699 if (!Visited.
insert(OpPhi).second)
6704 }
else if (
auto *OpLoad = dyn_cast<LoadInst>(V)) {
6705 if (!OpLoad->isSimple())
6707 if (Defs.
insert(OpLoad).second)
6709 }
else if (
auto *OpEx = dyn_cast<ExtractElementInst>(V)) {
6710 if (Defs.
insert(OpEx).second)
6712 }
else if (
auto *OpBC = dyn_cast<BitCastInst>(V)) {
6714 ConvertTy = OpBC->getOperand(0)->getType();
6715 if (OpBC->getOperand(0)->getType() != ConvertTy)
6717 if (Defs.
insert(OpBC).second) {
6719 AnyAnchored |= !isa<LoadInst>(OpBC->getOperand(0)) &&
6720 !isa<ExtractElementInst>(OpBC->getOperand(0));
6722 }
else if (
auto *OpC = dyn_cast<ConstantData>(V))
6730 for (
User *V :
II->users()) {
6731 if (
auto *OpPhi = dyn_cast<PHINode>(V)) {
6732 if (!PhiNodes.
count(OpPhi)) {
6733 if (Visited.
count(OpPhi))
6739 }
else if (
auto *OpStore = dyn_cast<StoreInst>(V)) {
6740 if (!OpStore->isSimple() || OpStore->getOperand(0) !=
II)
6742 Uses.insert(OpStore);
6743 }
else if (
auto *OpBC = dyn_cast<BitCastInst>(V)) {
6745 ConvertTy = OpBC->getType();
6746 if (OpBC->getType() != ConvertTy)
6750 any_of(OpBC->users(), [](
User *U) { return !isa<StoreInst>(U); });
6757 if (!ConvertTy || !AnyAnchored ||
6761 LLVM_DEBUG(
dbgs() <<
"Converting " << *
I <<
"\n and connected nodes to "
6762 << *ConvertTy <<
"\n");
6770 if (isa<BitCastInst>(
D)) {
6771 ValMap[
D] =
D->getOperand(0);
6775 ValMap[
D] =
new BitCastInst(
D, ConvertTy,
D->getName() +
".bc", insertPt);
6780 Phi->getName() +
".tc",
Phi->getIterator());
6782 for (
PHINode *Phi : PhiNodes) {
6783 PHINode *NewPhi = cast<PHINode>(ValMap[Phi]);
6784 for (
int i = 0, e =
Phi->getNumIncomingValues(); i < e; i++)
6786 Phi->getIncomingBlock(i));
6791 if (isa<BitCastInst>(U)) {
6795 U->setOperand(0,
new BitCastInst(ValMap[
U->getOperand(0)], PhiTy,
"bc",
6802 DeletedInstrs.
insert(Phi);
6806bool CodeGenPrepare::optimizePhiTypes(
Function &
F) {
6810 bool Changed =
false;
6816 for (
auto &Phi : BB.
phis())
6817 Changed |= optimizePhiType(&Phi, Visited, DeletedInstrs);
6820 for (
auto *
I : DeletedInstrs) {
6822 I->eraseFromParent();
6830bool CodeGenPrepare::canFormExtLd(
6833 for (
auto *MovedExtInst : MovedExts) {
6834 if (isa<LoadInst>(MovedExtInst->getOperand(0))) {
6835 LI = cast<LoadInst>(MovedExtInst->getOperand(0));
6836 Inst = MovedExtInst;
6888bool CodeGenPrepare::optimizeExt(
Instruction *&Inst) {
6889 bool AllowPromotionWithoutCommonHeader =
false;
6894 *Inst, AllowPromotionWithoutCommonHeader);
6895 TypePromotionTransaction TPT(RemovedInsts);
6896 TypePromotionTransaction::ConstRestorationPt LastKnownGood =
6897 TPT.getRestorationPoint();
6902 bool HasPromoted = tryToPromoteExts(TPT, Exts, SpeculativelyMovedExts);
6910 if (canFormExtLd(SpeculativelyMovedExts, LI, ExtFedByLoad, HasPromoted)) {
6911 assert(LI && ExtFedByLoad &&
"Expect a valid load and extension");
6916 Inst = ExtFedByLoad;
6921 if (ATPConsiderable &&
6922 performAddressTypePromotion(Inst, AllowPromotionWithoutCommonHeader,
6923 HasPromoted, TPT, SpeculativelyMovedExts))
6926 TPT.rollback(LastKnownGood);
6935bool CodeGenPrepare::performAddressTypePromotion(
6936 Instruction *&Inst,
bool AllowPromotionWithoutCommonHeader,
6937 bool HasPromoted, TypePromotionTransaction &TPT,
6939 bool Promoted =
false;
6941 bool AllSeenFirst =
true;
6942 for (
auto *
I : SpeculativelyMovedExts) {
6943 Value *HeadOfChain =
I->getOperand(0);
6945 SeenChainsForSExt.
find(HeadOfChain);
6948 if (AlreadySeen != SeenChainsForSExt.
end()) {
6949 if (AlreadySeen->second !=
nullptr)
6950 UnhandledExts.
insert(AlreadySeen->second);
6951 AllSeenFirst =
false;
6955 if (!AllSeenFirst || (AllowPromotionWithoutCommonHeader &&
6956 SpeculativelyMovedExts.size() == 1)) {
6960 for (
auto *
I : SpeculativelyMovedExts) {
6961 Value *HeadOfChain =
I->getOperand(0);
6962 SeenChainsForSExt[HeadOfChain] =
nullptr;
6963 ValToSExtendedUses[HeadOfChain].push_back(
I);
6966 Inst = SpeculativelyMovedExts.pop_back_val();
6971 for (
auto *
I : SpeculativelyMovedExts) {
6972 Value *HeadOfChain =
I->getOperand(0);
6973 SeenChainsForSExt[HeadOfChain] = Inst;
6978 if (!AllSeenFirst && !UnhandledExts.
empty())
6979 for (
auto *VisitedSExt : UnhandledExts) {
6980 if (RemovedInsts.count(VisitedSExt))
6982 TypePromotionTransaction TPT(RemovedInsts);
6986 bool HasPromoted = tryToPromoteExts(TPT, Exts, Chains);
6990 for (
auto *
I : Chains) {
6991 Value *HeadOfChain =
I->getOperand(0);
6993 SeenChainsForSExt[HeadOfChain] =
nullptr;
6994 ValToSExtendedUses[HeadOfChain].push_back(
I);
7005 Value *Src =
I->getOperand(0);
7006 if (Src->hasOneUse())
7015 if (!isa<Instruction>(Src) || DefBB != cast<Instruction>(Src)->
getParent())
7018 bool DefIsLiveOut =
false;
7019 for (
User *U :
I->users()) {
7024 if (UserBB == DefBB)
7026 DefIsLiveOut =
true;
7033 for (
User *U : Src->users()) {
7036 if (UserBB == DefBB)
7040 if (isa<PHINode>(UI) || isa<LoadInst>(UI) || isa<StoreInst>(UI))
7047 bool MadeChange =
false;
7048 for (
Use &U : Src->uses()) {
7053 if (UserBB == DefBB)
7057 Instruction *&InsertedTrunc = InsertedTruncs[UserBB];
7059 if (!InsertedTrunc) {
7062 InsertedTrunc =
new TruncInst(
I, Src->getType(),
"");
7064 InsertedInsts.insert(InsertedTrunc);
7127bool CodeGenPrepare::optimizeLoadExt(
LoadInst *Load) {
7128 if (!
Load->isSimple() || !
Load->getType()->isIntOrPtrTy())
7132 if (
Load->hasOneUse() &&
7133 InsertedInsts.count(cast<Instruction>(*
Load->user_begin())))
7142 for (
auto *U :
Load->users())
7143 WorkList.
push_back(cast<Instruction>(U));
7154 while (!WorkList.
empty()) {
7158 if (!Visited.
insert(
I).second)
7162 if (
auto *Phi = dyn_cast<PHINode>(
I)) {
7163 for (
auto *U :
Phi->users())
7164 WorkList.
push_back(cast<Instruction>(U));
7168 switch (
I->getOpcode()) {
7169 case Instruction::And: {
7170 auto *AndC = dyn_cast<ConstantInt>(
I->getOperand(1));
7173 APInt AndBits = AndC->getValue();
7174 DemandBits |= AndBits;
7176 if (AndBits.
ugt(WidestAndBits))
7177 WidestAndBits = AndBits;
7178 if (AndBits == WidestAndBits &&
I->getOperand(0) == Load)
7183 case Instruction::Shl: {
7184 auto *ShlC = dyn_cast<ConstantInt>(
I->getOperand(1));
7188 DemandBits.setLowBits(
BitWidth - ShiftAmt);
7193 case Instruction::Trunc: {
7196 DemandBits.setLowBits(TruncBitWidth);
7206 uint32_t ActiveBits = DemandBits.getActiveBits();
7218 if (ActiveBits <= 1 || !DemandBits.isMask(ActiveBits) ||
7219 WidestAndBits != DemandBits)
7232 auto *NewAnd = cast<Instruction>(
7233 Builder.CreateAnd(Load, ConstantInt::get(Ctx, DemandBits)));
7236 InsertedInsts.insert(NewAnd);
7241 NewAnd->setOperand(0, Load);
7244 for (
auto *
And : AndsToMaybeRemove)
7247 if (cast<ConstantInt>(
And->getOperand(1))->getValue() == DemandBits) {
7249 if (&*CurInstIterator ==
And)
7250 CurInstIterator = std::next(
And->getIterator());
7251 And->eraseFromParent();
7256 for (
auto *Inst : DropFlags)
7266 auto *
I = dyn_cast<Instruction>(V);
7288 uint64_t Max = std::max(TrueWeight, FalseWeight);
7289 uint64_t Sum = TrueWeight + FalseWeight;
7297 CmpInst *Cmp = dyn_cast<CmpInst>(SI->getCondition());
7302 if (!Cmp || !Cmp->hasOneUse())
7323 for (
SelectInst *DefSI = SI; DefSI !=
nullptr && Selects.
count(DefSI);
7324 DefSI = dyn_cast<SelectInst>(V)) {
7325 assert(DefSI->getCondition() == SI->getCondition() &&
7326 "The condition of DefSI does not match with SI");
7327 V = (isTrue ? DefSI->getTrueValue() : DefSI->getFalseValue());
7330 assert(V &&
"Failed to get select true/false value");
7359 Value *NewTVal = Builder.CreateBinOp(Opcode, Shift->
getOperand(0), TVal);
7360 Value *NewFVal = Builder.CreateBinOp(Opcode, Shift->
getOperand(0), FVal);
7361 Value *NewSel = Builder.CreateSelect(
Cond, NewTVal, NewFVal);
7367bool CodeGenPrepare::optimizeFunnelShift(
IntrinsicInst *Fsh) {
7369 assert((Opcode == Intrinsic::fshl || Opcode == Intrinsic::fshr) &&
7370 "Expected a funnel shift");
7394 Value *NewTVal = Builder.CreateIntrinsic(Opcode, Ty, {
X,
Y, TVal});
7395 Value *NewFVal = Builder.CreateIntrinsic(Opcode, Ty, {
X,
Y, FVal});
7396 Value *NewSel = Builder.CreateSelect(
Cond, NewTVal, NewFVal);
7404bool CodeGenPrepare::optimizeSelectInst(
SelectInst *SI) {
7416 It !=
SI->getParent()->
end(); ++It) {
7418 if (
I &&
SI->getCondition() ==
I->getCondition()) {
7428 CurInstIterator = std::next(LastSI->
getIterator());
7433 fixupDbgVariableRecordsOnInst(*SI);
7435 bool VectorCond = !
SI->getCondition()->getType()->isIntegerTy(1);
7438 if (VectorCond ||
SI->getMetadata(LLVMContext::MD_unpredictable))
7442 if (
SI->getType()->isVectorTy())
7443 SelectKind = TargetLowering::ScalarCondVectorVal;
7445 SelectKind = TargetLowering::ScalarValSelect;
7488 TrueInstrs.
push_back(cast<Instruction>(V));
7490 FalseInstrs.
push_back(cast<Instruction>(V));
7498 SplitPt.setHeadBit(
true);
7501 auto *CondFr =
IB.CreateFreeze(
SI->getCondition(),
SI->getName() +
".frozen");
7508 if (TrueInstrs.
size() == 0) {
7510 CondFr, SplitPt,
false,
nullptr,
nullptr, LI));
7512 EndBlock = cast<BasicBlock>(FalseBranch->
getOperand(0));
7513 }
else if (FalseInstrs.
size() == 0) {
7515 CondFr, SplitPt,
false,
nullptr,
nullptr, LI));
7517 EndBlock = cast<BasicBlock>(TrueBranch->
getOperand(0));
7522 nullptr,
nullptr, LI);
7523 TrueBranch = cast<BranchInst>(ThenTerm);
7524 FalseBranch = cast<BranchInst>(ElseTerm);
7527 EndBlock = cast<BasicBlock>(TrueBranch->
getOperand(0));
7530 EndBlock->
setName(
"select.end");
7532 TrueBlock->
setName(
"select.true.sink");
7534 FalseBlock->
setName(FalseInstrs.
size() == 0 ?
"select.false"
7535 :
"select.false.sink");
7539 FreshBBs.
insert(TrueBlock);
7541 FreshBBs.
insert(FalseBlock);
7542 FreshBBs.
insert(EndBlock);
7545 BFI->setBlockFreq(EndBlock,
BFI->getBlockFreq(StartBlock));
7547 static const unsigned MD[] = {
7548 LLVMContext::MD_prof, LLVMContext::MD_unpredictable,
7549 LLVMContext::MD_make_implicit, LLVMContext::MD_dbg};
7555 I->moveBefore(TrueBranch);
7557 I->moveBefore(FalseBranch);
7563 if (TrueBlock ==
nullptr)
7564 TrueBlock = StartBlock;
7565 else if (FalseBlock ==
nullptr)
7566 FalseBlock = StartBlock;
7569 INS.
insert(ASI.begin(), ASI.end());
7583 SI->eraseFromParent();
7585 ++NumSelectsExpanded;
7589 CurInstIterator = StartBlock->
end();
7605 auto *SVIVecType = cast<FixedVectorType>(SVI->
getType());
7608 "Expected a type of the same size!");
7614 Builder.SetInsertPoint(SVI);
7615 Value *BC1 = Builder.CreateBitCast(
7616 cast<Instruction>(SVI->
getOperand(0))->getOperand(1), NewType);
7617 Value *Shuffle = Builder.CreateVectorSplat(NewVecType->getNumElements(), BC1);
7618 Value *BC2 = Builder.CreateBitCast(Shuffle, SVIVecType);
7622 SVI, TLInfo,
nullptr,
7623 [&](
Value *V) { removeAllAssertingVHReferences(V); });
7627 if (
auto *BCI = dyn_cast<Instruction>(BC1))
7628 if (
auto *
Op = dyn_cast<Instruction>(BCI->
getOperand(0)))
7629 if (BCI->
getParent() !=
Op->getParent() && !isa<PHINode>(
Op) &&
7630 !
Op->isTerminator() && !
Op->isEHPad())
7636bool CodeGenPrepare::tryToSinkFreeOperands(
Instruction *
I) {
7648 bool Changed =
false;
7652 unsigned long InstNumber = 0;
7653 for (
const auto &
I : *TargetBB)
7654 InstOrdering[&
I] = InstNumber++;
7657 auto *UI = cast<Instruction>(
U->get());
7658 if (isa<PHINode>(UI))
7661 if (InstOrdering[UI] < InstOrdering[InsertPoint])
7670 for (
Use *U : ToReplace) {
7671 auto *UI = cast<Instruction>(
U->get());
7678 if (
auto *OpDef = dyn_cast<Instruction>(
Op))
7679 FreshBBs.
insert(OpDef->getParent());
7682 NewInstructions[UI] = NI;
7687 InsertedInsts.insert(NI);
7693 if (NewInstructions.
count(OldI))
7694 NewInstructions[OldI]->setOperand(
U->getOperandNo(), NI);
7701 for (
auto *
I : MaybeDead) {
7702 if (!
I->hasNUsesOrMore(1)) {
7704 I->eraseFromParent();
7711bool CodeGenPrepare::optimizeSwitchType(
SwitchInst *SI) {
7719 if (RegWidth <= cast<IntegerType>(OldType)->
getBitWidth())
7737 ExtType = Instruction::SExt;
7739 if (
auto *Arg = dyn_cast<Argument>(
Cond)) {
7740 if (Arg->hasSExtAttr())
7741 ExtType = Instruction::SExt;
7742 if (Arg->hasZExtAttr())
7743 ExtType = Instruction::ZExt;
7749 SI->setCondition(ExtInst);
7750 for (
auto Case :
SI->cases()) {
7751 const APInt &NarrowConst = Case.getCaseValue()->getValue();
7752 APInt WideConst = (ExtType == Instruction::ZExt)
7753 ? NarrowConst.
zext(RegWidth)
7754 : NarrowConst.
sext(RegWidth);
7755 Case.setValue(ConstantInt::get(Context, WideConst));
7761bool CodeGenPrepare::optimizeSwitchPhiConstants(
SwitchInst *SI) {
7768 Value *Condition =
SI->getCondition();
7770 if (isa<ConstantInt>(*Condition))
7773 bool Changed =
false;
7779 BasicBlock *CaseBB = Case.getCaseSuccessor();
7782 bool CheckedForSinglePred =
false;
7784 Type *PHIType =
PHI.getType();
7792 if (PHIType == ConditionType || TryZExt) {
7794 bool SkipCase =
false;
7795 Value *Replacement =
nullptr;
7796 for (
unsigned I = 0, E =
PHI.getNumIncomingValues();
I != E;
I++) {
7797 Value *PHIValue =
PHI.getIncomingValue(
I);
7798 if (PHIValue != CaseValue) {
7801 ConstantInt *PHIValueInt = dyn_cast<ConstantInt>(PHIValue);
7807 if (
PHI.getIncomingBlock(
I) != SwitchBB)
7812 if (!CheckedForSinglePred) {
7813 CheckedForSinglePred =
true;
7814 if (
SI->findCaseDest(CaseBB) ==
nullptr) {
7820 if (Replacement ==
nullptr) {
7821 if (PHIValue == CaseValue) {
7822 Replacement = Condition;
7825 Replacement = Builder.CreateZExt(Condition, PHIType);
7828 PHI.setIncomingValue(
I, Replacement);
7839bool CodeGenPrepare::optimizeSwitchInst(
SwitchInst *SI) {
7840 bool Changed = optimizeSwitchType(SI);
7841 Changed |= optimizeSwitchPhiConstants(SI);
7862class VectorPromoteHelper {
7879 unsigned StoreExtractCombineCost;
7888 if (InstsToBePromoted.
empty())
7890 return InstsToBePromoted.
back();
7896 unsigned getTransitionOriginalValueIdx()
const {
7897 assert(isa<ExtractElementInst>(Transition) &&
7898 "Other kind of transitions are not supported yet");
7905 unsigned getTransitionIdx()
const {
7906 assert(isa<ExtractElementInst>(Transition) &&
7907 "Other kind of transitions are not supported yet");
7915 Type *getTransitionType()
const {
7930 bool isProfitableToPromote() {
7931 Value *ValIdx = Transition->
getOperand(getTransitionOriginalValueIdx());
7932 unsigned Index = isa<ConstantInt>(ValIdx)
7933 ? cast<ConstantInt>(ValIdx)->getZExtValue()
7935 Type *PromotedType = getTransitionType();
7938 unsigned AS =
ST->getPointerAddressSpace();
7956 for (
const auto &Inst : InstsToBePromoted) {
7962 bool IsArg0Constant = isa<UndefValue>(Arg0) || isa<ConstantInt>(Arg0) ||
7963 isa<ConstantFP>(Arg0);
7976 dbgs() <<
"Estimated cost of computation to be promoted:\nScalar: "
7977 << ScalarCost <<
"\nVector: " << VectorCost <<
'\n');
7978 return ScalarCost > VectorCost;
7990 unsigned ExtractIdx = std::numeric_limits<unsigned>::max();
7995 if (
ConstantInt *CstVal = dyn_cast<ConstantInt>(ValExtractIdx))
8001 ElementCount EC = cast<VectorType>(getTransitionType())->getElementCount();
8005 if (!
EC.isScalable()) {
8008 for (
unsigned Idx = 0;
Idx !=
EC.getKnownMinValue(); ++
Idx) {
8009 if (
Idx == ExtractIdx)
8017 "Generate scalable vector for non-splat is unimplemented");
8023 unsigned OperandIdx) {
8026 if (OperandIdx != 1)
8028 switch (
Use->getOpcode()) {
8031 case Instruction::SDiv:
8032 case Instruction::UDiv:
8033 case Instruction::SRem:
8034 case Instruction::URem:
8036 case Instruction::FDiv:
8037 case Instruction::FRem:
8038 return !
Use->hasNoNaNs();
8046 unsigned CombineCost)
8047 :
DL(
DL), TLI(TLI),
TTI(
TTI), Transition(Transition),
8048 StoreExtractCombineCost(CombineCost) {
8049 assert(Transition &&
"Do not know how to promote null");
8053 bool canPromote(
const Instruction *ToBePromoted)
const {
8055 return isa<BinaryOperator>(ToBePromoted);
8060 bool shouldPromote(
const Instruction *ToBePromoted)
const {
8064 const Value *Val =
U.get();
8065 if (Val == getEndOfTransition()) {
8069 if (canCauseUndefinedBehavior(ToBePromoted,
U.getOperandNo()))
8073 if (!isa<ConstantInt>(Val) && !isa<UndefValue>(Val) &&
8074 !isa<ConstantFP>(Val))
8083 ISDOpcode, TLI.
getValueType(DL, getTransitionType(),
true));
8092 void enqueueForPromotion(
Instruction *ToBePromoted) {
8093 InstsToBePromoted.push_back(ToBePromoted);
8097 void recordCombineInstruction(
Instruction *ToBeCombined) {
8099 CombineInst = ToBeCombined;
8109 if (InstsToBePromoted.empty() || !CombineInst)
8117 for (
auto &ToBePromoted : InstsToBePromoted)
8118 promoteImpl(ToBePromoted);
8119 InstsToBePromoted.clear();
8126void VectorPromoteHelper::promoteImpl(
Instruction *ToBePromoted) {
8136 "The type of the result of the transition does not match "
8141 Type *TransitionTy = getTransitionType();
8148 Value *NewVal =
nullptr;
8149 if (Val == Transition)
8150 NewVal = Transition->
getOperand(getTransitionOriginalValueIdx());
8151 else if (isa<UndefValue>(Val) || isa<ConstantInt>(Val) ||
8152 isa<ConstantFP>(Val)) {
8155 cast<Constant>(Val),
8156 isa<UndefValue>(Val) ||
8157 canCauseUndefinedBehavior(ToBePromoted,
U.getOperandNo()));
8161 ToBePromoted->
setOperand(
U.getOperandNo(), NewVal);
8164 Transition->
setOperand(getTransitionOriginalValueIdx(), ToBePromoted);
8170bool CodeGenPrepare::optimizeExtractElementInst(
Instruction *Inst) {
8171 unsigned CombineCost = std::numeric_limits<unsigned>::max();
8186 LLVM_DEBUG(
dbgs() <<
"Found an interesting transition: " << *Inst <<
'\n');
8187 VectorPromoteHelper VPH(*
DL, *TLI, *
TTI, Inst, CombineCost);
8194 if (ToBePromoted->
getParent() != Parent) {
8195 LLVM_DEBUG(
dbgs() <<
"Instruction to promote is in a different block ("
8197 <<
") than the transition (" << Parent->
getName()
8202 if (VPH.canCombine(ToBePromoted)) {
8204 <<
"will be combined with: " << *ToBePromoted <<
'\n');
8205 VPH.recordCombineInstruction(ToBePromoted);
8206 bool Changed = VPH.promote();
8207 NumStoreExtractExposed += Changed;
8212 if (!VPH.canPromote(ToBePromoted) || !VPH.shouldPromote(ToBePromoted))
8215 LLVM_DEBUG(
dbgs() <<
"Promoting is possible... Enqueue for promotion!\n");
8217 VPH.enqueueForPromotion(ToBePromoted);
8218 Inst = ToBePromoted;
8258 Type *StoreType = SI.getValueOperand()->getType();
8267 if (!
DL.typeSizeEqualsStoreSize(StoreType) ||
8268 DL.getTypeSizeInBits(StoreType) == 0)
8271 unsigned HalfValBitSize =
DL.getTypeSizeInBits(StoreType) / 2;
8273 if (!
DL.typeSizeEqualsStoreSize(SplitStoreType))
8277 if (SI.isVolatile())
8289 if (!
match(SI.getValueOperand(),
8296 if (!
LValue->getType()->isIntegerTy() ||
8297 DL.getTypeSizeInBits(
LValue->getType()) > HalfValBitSize ||
8299 DL.getTypeSizeInBits(HValue->
getType()) > HalfValBitSize)
8304 auto *LBC = dyn_cast<BitCastInst>(
LValue);
8305 auto *HBC = dyn_cast<BitCastInst>(HValue);
8319 if (LBC && LBC->getParent() != SI.getParent())
8321 if (HBC && HBC->getParent() != SI.getParent())
8322 HValue = Builder.
CreateBitCast(HBC->getOperand(0), HBC->getType());
8324 bool IsLE = SI.getDataLayout().isLittleEndian();
8325 auto CreateSplitStore = [&](
Value *V,
bool Upper) {
8328 Align Alignment = SI.getAlign();
8329 const bool IsOffsetStore = (IsLE &&
Upper) || (!IsLE && !
Upper);
8330 if (IsOffsetStore) {
8332 SplitStoreType,
Addr,
8343 CreateSplitStore(
LValue,
false);
8344 CreateSplitStore(HValue,
true);
8347 SI.eraseFromParent();
8355 return GEP->getNumOperands() == 2 &&
I.isSequential() &&
8356 isa<ConstantInt>(
GEP->getOperand(1));
8434 if (!isa<Instruction>(GEPIOp))
8436 auto *GEPIOpI = cast<Instruction>(GEPIOp);
8437 if (GEPIOpI->getParent() != SrcBlock)
8442 if (auto *I = dyn_cast<Instruction>(Usr)) {
8443 if (I->getParent() != SrcBlock) {
8451 std::vector<GetElementPtrInst *> UGEPIs;
8458 if (!isa<Instruction>(Usr))
8460 auto *UI = cast<Instruction>(Usr);
8465 if (!isa<GetElementPtrInst>(Usr))
8467 auto *UGEPI = cast<GetElementPtrInst>(Usr);
8473 if (UGEPI->getOperand(0) != GEPIOp)
8475 if (UGEPI->getSourceElementType() != GEPI->getSourceElementType())
8477 if (GEPIIdx->getType() !=
8478 cast<ConstantInt>(UGEPI->getOperand(1))->getType())
8480 ConstantInt *UGEPIIdx = cast<ConstantInt>(UGEPI->getOperand(1));
8485 UGEPIs.push_back(UGEPI);
8487 if (UGEPIs.size() == 0)
8491 ConstantInt *UGEPIIdx = cast<ConstantInt>(UGEPI->getOperand(1));
8500 UGEPI->setOperand(0, GEPI);
8501 ConstantInt *UGEPIIdx = cast<ConstantInt>(UGEPI->getOperand(1));
8502 Constant *NewUGEPIIdx = ConstantInt::get(
8503 GEPIIdx->getType(), UGEPIIdx->
getValue() - GEPIIdx->getValue());
8504 UGEPI->setOperand(1, NewUGEPIIdx);
8507 if (!GEPI->isInBounds()) {
8508 UGEPI->setIsInBounds(
false);
8515 return cast<Instruction>(Usr)->getParent() != SrcBlock;
8517 "GEPIOp is used outside SrcBlock");
8537 ICmpInst *Cmp = dyn_cast<ICmpInst>(Branch->getCondition());
8538 if (!Cmp || !isa<ConstantInt>(Cmp->getOperand(1)) || !Cmp->hasOneUse())
8541 Value *
X = Cmp->getOperand(0);
8542 APInt CmpC = cast<ConstantInt>(Cmp->getOperand(1))->getValue();
8544 for (
auto *U :
X->users()) {
8548 (UI->
getParent() != Branch->getParent() &&
8549 UI->
getParent() != Branch->getSuccessor(0) &&
8550 UI->
getParent() != Branch->getSuccessor(1)) ||
8551 (UI->
getParent() != Branch->getParent() &&
8552 !UI->
getParent()->getSinglePredecessor()))
8555 if (CmpC.
isPowerOf2() && Cmp->getPredicate() == ICmpInst::ICMP_ULT &&
8558 if (UI->
getParent() != Branch->getParent())
8562 ConstantInt::get(UI->
getType(), 0));
8564 LLVM_DEBUG(
dbgs() <<
" to compare on zero: " << *NewCmp <<
"\n");
8568 if (Cmp->isEquality() &&
8572 if (UI->
getParent() != Branch->getParent())
8576 ConstantInt::get(UI->
getType(), 0));
8578 LLVM_DEBUG(
dbgs() <<
" to compare on zero: " << *NewCmp <<
"\n");
8586bool CodeGenPrepare::optimizeInst(
Instruction *
I, ModifyDT &ModifiedDT) {
8587 bool AnyChange =
false;
8588 AnyChange = fixupDbgVariableRecordsOnInst(*
I);
8592 if (InsertedInsts.count(
I))
8596 if (
PHINode *
P = dyn_cast<PHINode>(
I)) {
8601 LargeOffsetGEPMap.erase(
P);
8603 P->eraseFromParent();
8610 if (
CastInst *CI = dyn_cast<CastInst>(
I)) {
8623 if ((isa<UIToFPInst>(
I) || isa<SIToFPInst>(
I) || isa<FPToUIInst>(
I) ||
8624 isa<TruncInst>(
I)) &&
8626 I, LI->getLoopFor(
I->getParent()), *
TTI))
8629 if (isa<ZExtInst>(
I) || isa<SExtInst>(
I)) {
8634 TargetLowering::TypeExpandInteger) {
8638 I, LI->getLoopFor(
I->getParent()), *
TTI))
8641 bool MadeChange = optimizeExt(
I);
8642 return MadeChange | optimizeExtUses(
I);
8648 if (
auto *Cmp = dyn_cast<CmpInst>(
I))
8649 if (optimizeCmp(Cmp, ModifiedDT))
8653 if (optimizeURem(
I))
8656 if (
LoadInst *LI = dyn_cast<LoadInst>(
I)) {
8657 LI->
setMetadata(LLVMContext::MD_invariant_group,
nullptr);
8658 bool Modified = optimizeLoadExt(LI);
8664 if (
StoreInst *SI = dyn_cast<StoreInst>(
I)) {
8667 SI->setMetadata(LLVMContext::MD_invariant_group,
nullptr);
8668 unsigned AS =
SI->getPointerAddressSpace();
8669 return optimizeMemoryInst(
I,
SI->getOperand(1),
8670 SI->getOperand(0)->getType(), AS);
8674 unsigned AS = RMW->getPointerAddressSpace();
8675 return optimizeMemoryInst(
I, RMW->getPointerOperand(), RMW->getType(), AS);
8679 unsigned AS = CmpX->getPointerAddressSpace();
8680 return optimizeMemoryInst(
I, CmpX->getPointerOperand(),
8681 CmpX->getCompareOperand()->getType(), AS);
8691 if (BinOp && (BinOp->
getOpcode() == Instruction::AShr ||
8692 BinOp->
getOpcode() == Instruction::LShr)) {
8700 if (GEPI->hasAllZeroIndices()) {
8703 GEPI->getName(), GEPI->getIterator());
8704 NC->setDebugLoc(GEPI->getDebugLoc());
8707 GEPI, TLInfo,
nullptr,
8708 [&](
Value *V) { removeAllAssertingVHReferences(V); });
8710 optimizeInst(
NC, ModifiedDT);
8722 if (
ICmpInst *
II = dyn_cast<ICmpInst>(FI->getOperand(0)))
8724 else if (
FCmpInst *
F = dyn_cast<FCmpInst>(FI->getOperand(0)))
8725 CmpI =
F->getFastMathFlags().none() ?
F :
nullptr;
8729 bool Const0 = isa<ConstantInt>(Op0) || isa<ConstantFP>(Op0) ||
8730 isa<ConstantPointerNull>(Op0);
8731 bool Const1 = isa<ConstantInt>(Op1) || isa<ConstantFP>(Op1) ||
8732 isa<ConstantPointerNull>(Op1);
8733 if (Const0 || Const1) {
8734 if (!Const0 || !Const1) {
8740 FI->eraseFromParent();
8747 if (tryToSinkFreeOperands(
I))
8750 switch (
I->getOpcode()) {
8751 case Instruction::Shl:
8752 case Instruction::LShr:
8753 case Instruction::AShr:
8754 return optimizeShiftInst(cast<BinaryOperator>(
I));
8755 case Instruction::Call:
8757 case Instruction::Select:
8758 return optimizeSelectInst(cast<SelectInst>(
I));
8759 case Instruction::ShuffleVector:
8760 return optimizeShuffleVectorInst(cast<ShuffleVectorInst>(
I));
8761 case Instruction::Switch:
8762 return optimizeSwitchInst(cast<SwitchInst>(
I));
8763 case Instruction::ExtractElement:
8764 return optimizeExtractElementInst(cast<ExtractElementInst>(
I));
8765 case Instruction::Br:
8766 return optimizeBranch(cast<BranchInst>(
I), *TLI, FreshBBs, IsHugeFunc);
8775 if (!
I.getType()->isIntegerTy() ||
8786 &
I, TLInfo,
nullptr,
8787 [&](
Value *V) { removeAllAssertingVHReferences(V); });
8794bool CodeGenPrepare::optimizeBlock(
BasicBlock &BB, ModifyDT &ModifiedDT) {
8796 bool MadeChange =
false;
8799 CurInstIterator = BB.
begin();
8800 ModifiedDT = ModifyDT::NotModifyDT;
8801 while (CurInstIterator != BB.
end()) {
8802 MadeChange |= optimizeInst(&*CurInstIterator++, ModifiedDT);
8803 if (ModifiedDT != ModifyDT::NotModifyDT) {
8816 }
while (ModifiedDT == ModifyDT::ModifyInstDT);
8818 bool MadeBitReverse =
true;
8819 while (MadeBitReverse) {
8820 MadeBitReverse =
false;
8822 if (makeBitReverse(
I)) {
8823 MadeBitReverse = MadeChange =
true;
8828 MadeChange |= dupRetToEnableTailCallOpts(&BB, ModifiedDT);
8840 bool AnyChange =
false;
8843 for (
Value *Location : LocationOps) {
8859bool CodeGenPrepare::fixupDbgVariableRecordsOnInst(
Instruction &
I) {
8860 bool AnyChange =
false;
8862 AnyChange |= fixupDbgVariableRecord(DVR);
8869 if (DVR.
Type != DbgVariableRecord::LocationType::Value &&
8870 DVR.
Type != DbgVariableRecord::LocationType::Assign)
8874 bool AnyChange =
false;
8877 for (
Value *Location : LocationOps) {
8895 if (isa<PHINode>(VI))
8896 DVI->
insertBefore(&*VI->getParent()->getFirstInsertionPt());
8904 if (isa<PHINode>(VI))
8915bool CodeGenPrepare::placeDbgValues(
Function &
F) {
8916 bool MadeChange =
false;
8919 auto DbgProcessor = [&](
auto *DbgItem,
Instruction *Position) {
8921 for (
Value *V : DbgItem->location_ops())
8922 if (
Instruction *VI = dyn_cast_or_null<Instruction>(V))
8930 if (
VI->isTerminator())
8935 if (isa<PHINode>(VI) &&
VI->getParent()->getTerminator()->isEHPad())
8946 if (VIs.size() > 1) {
8949 <<
"Unable to find valid location for Debug Value, undefing:\n"
8951 DbgItem->setKillLocation();
8956 << *DbgItem <<
' ' << *VI);
8968 DbgProcessor(DVI, DVI);
8976 if (DVR.
Type != DbgVariableRecord::LocationType::Value)
8978 DbgProcessor(&DVR, &
Insn);
8989bool CodeGenPrepare::placePseudoProbes(
Function &
F) {
8990 bool MadeChange =
false;
8993 auto FirstInst =
Block.getFirstInsertionPt();
8994 while (FirstInst !=
Block.end() && FirstInst->isDebugOrPseudoInst())
8998 while (
I !=
Block.end()) {
8999 if (
auto *
II = dyn_cast<PseudoProbeInst>(
I++)) {
9000 II->moveBefore(&*FirstInst);
9010 uint64_t NewMax = (NewTrue > NewFalse) ? NewTrue : NewFalse;
9011 uint32_t Scale = (NewMax / std::numeric_limits<uint32_t>::max()) + 1;
9012 NewTrue = NewTrue / Scale;
9013 NewFalse = NewFalse / Scale;
9038bool CodeGenPrepare::splitBranchCondition(
Function &
F, ModifyDT &ModifiedDT) {
9042 bool MadeChange =
false;
9043 for (
auto &BB :
F) {
9056 if (Br1->getMetadata(LLVMContext::MD_unpredictable))
9064 Value *Cond1, *Cond2;
9067 Opc = Instruction::And;
9070 Opc = Instruction::Or;
9080 if (!IsGoodCond(Cond1) || !IsGoodCond(Cond2))
9094 Br1->setCondition(Cond1);
9099 if (Opc == Instruction::And)
9100 Br1->setSuccessor(0, TmpBB);
9102 Br1->setSuccessor(1, TmpBB);
9106 if (
auto *
I = dyn_cast<Instruction>(Cond2)) {
9107 I->removeFromParent();
9108 I->insertBefore(Br2);
9120 if (Opc == Instruction::Or)
9134 if (Opc == Instruction::Or) {
9156 uint64_t NewTrueWeight = TrueWeight;
9157 uint64_t NewFalseWeight = TrueWeight + 2 * FalseWeight;
9159 Br1->setMetadata(LLVMContext::MD_prof,
9164 NewTrueWeight = TrueWeight;
9165 NewFalseWeight = 2 * FalseWeight;
9167 Br2->setMetadata(LLVMContext::MD_prof,
9192 uint64_t NewTrueWeight = 2 * TrueWeight + FalseWeight;
9193 uint64_t NewFalseWeight = FalseWeight;
9195 Br1->setMetadata(LLVMContext::MD_prof,
9199 NewTrueWeight = 2 * TrueWeight;
9200 NewFalseWeight = FalseWeight;
9202 Br2->setMetadata(LLVMContext::MD_prof,
9208 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, Instruction *VI)
static cl::opt< bool > DisableBranchOpts("disable-cgp-branch-opts", cl::Hidden, cl::init(false), cl::desc("Disable branch optimizations in CodeGenPrepare"))
static cl::opt< bool > EnableTypePromotionMerge("cgp-type-promotion-merge", cl::Hidden, cl::desc("Enable merging of redundant sexts when one is dominating" " the other."), cl::init(true))
static 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 > EnableAndCmpSinking("enable-andcmp-sinking", cl::Hidden, cl::init(true), cl::desc("Enable sinkinig and/cmp into branches."))
static cl::opt< bool > ProfileGuidedSectionPrefix("profile-guided-section-prefix", cl::Hidden, cl::init(true), cl::desc("Use profile info to add section prefix for hot/cold functions"))
static cl::opt< unsigned > HugeFuncThresholdInCGPP("cgpp-huge-func", cl::init(10000), cl::Hidden, cl::desc("Least BB number of huge function."))
static cl::opt< bool > AddrSinkNewSelects("addr-sink-new-select", cl::Hidden, cl::init(true), cl::desc("Allow creation of selects in Address sinking."))
static bool tryUnmergingGEPsAcrossIndirectBr(GetElementPtrInst *GEPI, const TargetTransformInfo *TTI)
static bool IsOperandAMemoryOperand(CallInst *CI, InlineAsm *IA, Value *OpVal, const TargetLowering &TLI, const TargetRegisterInfo &TRI)
Check to see if all uses of OpVal by the specified inline asm call are due to memory operands.
static bool isIntrinsicOrLFToBeTailCalled(const TargetLibraryInfo *TLInfo, const CallInst *CI)
static cl::opt< bool > ForceSplitStore("force-split-store", cl::Hidden, cl::init(false), cl::desc("Force store splitting no matter what the target query says."))
static void computeBaseDerivedRelocateMap(const SmallVectorImpl< GCRelocateInst * > &AllRelocateCalls, MapVector< GCRelocateInst *, SmallVector< GCRelocateInst *, 0 > > &RelocateInstMap)
static bool simplifyRelocatesOffABase(GCRelocateInst *RelocatedBase, const SmallVectorImpl< GCRelocateInst * > &Targets)
static cl::opt< bool > AddrSinkCombineScaledReg("addr-sink-combine-scaled-reg", cl::Hidden, cl::init(true), cl::desc("Allow combining of ScaledReg field in Address sinking."))
static bool foldICmpWithDominatingICmp(CmpInst *Cmp, const TargetLowering &TLI)
For pattern like:
static bool MightBeFoldableInst(Instruction *I)
This is a little filter, which returns true if an addressing computation involving I might be folded ...
static bool matchIncrement(const Instruction *IVInc, Instruction *&LHS, Constant *&Step)
static cl::opt< bool > EnableGEPOffsetSplit("cgp-split-large-offset-gep", cl::Hidden, cl::init(true), cl::desc("Enable splitting large offset of GEP."))
static cl::opt< bool > DisableComplexAddrModes("disable-complex-addr-modes", cl::Hidden, cl::init(false), cl::desc("Disables combining addressing modes with different parts " "in optimizeMemoryInst."))
static cl::opt< bool > EnableICMP_EQToICMP_ST("cgp-icmp-eq2icmp-st", cl::Hidden, cl::init(false), cl::desc("Enable ICMP_EQ to ICMP_S(L|G)T conversion."))
static cl::opt< bool > VerifyBFIUpdates("cgp-verify-bfi-updates", cl::Hidden, cl::init(false), cl::desc("Enable BFI update verification for " "CodeGenPrepare."))
static cl::opt< bool > BBSectionsGuidedSectionPrefix("bbsections-guided-section-prefix", cl::Hidden, cl::init(true), cl::desc("Use the basic-block-sections profile to determine the text " "section prefix for hot functions. Functions with " "basic-block-sections profile will be placed in `.text.hot` " "regardless of their FDO profile info. Other functions won't be " "impacted, i.e., their prefixes will be decided by FDO/sampleFDO " "profiles."))
static bool 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 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,...
void insertDbgRecordBefore(DbgRecord *DR, InstListType::iterator Here)
Insert a DbgRecord into a block at the position given by Here.
const Instruction * getFirstNonPHI() const
Returns a pointer to the first instruction in this block that is not a PHINode instruction.
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
BasicBlock * splitBasicBlock(iterator I, const Twine &BBName="", bool Before=false)
Split the basic block into two basic blocks at the specified instruction.
const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
const BasicBlock * getUniquePredecessor() const
Return the predecessor of this block if it has a unique predecessor block.
const BasicBlock * getSingleSuccessor() const
Return the successor of this block if it has a single successor.
const Function * getParent() const
Return the enclosing method, or null if none.
SymbolTableList< BasicBlock >::iterator eraseFromParent()
Unlink 'this' from the containing function and delete it.
void insertDbgRecordAfter(DbgRecord *DR, Instruction *I)
Insert a DbgRecord into a block at the position given by I.
const Instruction * getFirstNonPHIOrDbg(bool SkipPseudoOp=true) const
Returns a pointer to the first instruction in this block that is not a PHINode or a debug intrinsic,...
InstListType::iterator iterator
Instruction iterators...
LLVMContext & getContext() const
Get the context in which this basic block lives.
bool IsNewDbgInfoFormat
Flag recording whether or not this block stores debug-info in the form of intrinsic instructions (fal...
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
BinaryOps getOpcode() const
static BinaryOperator * Create(BinaryOps Op, Value *S1, Value *S2, const Twine &Name=Twine(), InsertPosition InsertBefore=nullptr)
Construct a binary instruction, given the opcode and the two operands.
This class represents a no-op cast from one type to another.
BlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate IR basic block frequen...
Conditional or Unconditional Branch instruction.
void swapSuccessors()
Swap the successors of this branch instruction.
bool isConditional() const
BasicBlock * getSuccessor(unsigned i) const
bool isUnconditional() const
Analysis providing branch probability information.
static BranchProbability getBranchProbability(uint64_t Numerator, uint64_t Denominator)
bool isInlineAsm() const
Check if this call is an inline asm statement.
Function * getCalledFunction() const
Returns the function called, or null if this is an indirect function invocation or the function signa...
bool hasFnAttr(Attribute::AttrKind Kind) const
Determine whether this call has the given attribute.
Value * getArgOperand(unsigned i) const
void setArgOperand(unsigned i, Value *v)
iterator_range< User::op_iterator > args()
Iteration adapter for range-for loops.
This class represents a function call, abstracting a target machine's calling convention.
This is the base class for all instructions that perform data casts.
static CastInst * Create(Instruction::CastOps, Value *S, Type *Ty, const Twine &Name="", InsertPosition InsertBefore=nullptr)
Provides a way to construct any of the CastInst subclasses using an opcode instead of the subclass's ...
This class is the base class for the comparison instructions.
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
@ ICMP_SLT
signed less than
@ ICMP_UGT
unsigned greater than
@ ICMP_SGT
signed greater than
@ ICMP_ULT
unsigned less than
Predicate getSwappedPredicate() const
For example, EQ->EQ, SLE->SGE, ULT->UGT, OEQ->OEQ, ULE->UGE, OLT->OGT, etc.
static CmpInst * Create(OtherOps Op, Predicate Pred, Value *S1, Value *S2, const Twine &Name="", InsertPosition InsertBefore=nullptr)
Construct a compare instruction, given the opcode, the predicate and the two operands.
Predicate getPredicate() const
Return the predicate for this instruction.
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)
size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
bool isReachableFromEntry(const Use &U) const
Provide an overload for a Use.
bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
This instruction compares its operands according to the predicate given to the constructor.
static FixedVectorType * get(Type *ElementType, unsigned NumElts)
This class implements simplifications for calls to fortified library functions (__st*cpy_chk,...
This class represents a freeze function that returns random concrete value if an operand is either a ...
FunctionPass class - This class is used to implement most global optimizations.
virtual bool runOnFunction(Function &F)=0
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass.
const BasicBlock & getEntryBlock() const
const Value * getStatepoint() const
The statepoint with which this gc.relocate is associated.
Represents calls to the gc.relocate intrinsic.
unsigned getBasePtrIndex() const
The index into the associate statepoint's argument list which contains the base pointer of the pointe...
Represents a gc.statepoint intrinsic call.
an instruction for type-safe pointer arithmetic to access elements of arrays and structs
static Type * getIndexedType(Type *Ty, ArrayRef< Value * > IdxList)
Returns the result type of a getelementptr with the given source element type and indexes.
void setAlignment(Align Align)
Sets the alignment attribute of the GlobalObject.
bool canIncreaseAlignment() const
Returns true if the alignment of the value can be unilaterally increased.
bool isThreadLocal() const
If the value is "Thread Local", its value isn't shared by the threads.
Type * getValueType() const
This instruction compares its operands according to the predicate given to the constructor.
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.
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.
virtual bool getAddrModeArguments(IntrinsicInst *, SmallVectorImpl< Value * > &, Type *&) const
CodeGenPrepare sinks address calculations into the same BB as Load/Store instructions reading the add...
bool isOperationLegalOrCustom(unsigned Op, EVT VT, bool LegalOnly=false) const
Return true if the specified operation is legal on this target or can be made legal with custom lower...
bool isPredictableSelectExpensive() const
Return true if selects are only cheaper than branches if the branch is unlikely to be predicted right...
virtual bool isMultiStoresCheaperThanBitsMerge(EVT LTy, EVT HTy) const
Return true if it is cheaper to split the store of a merged int val from a pair of smaller values int...
bool isLoadExtLegal(unsigned ExtType, EVT ValVT, EVT MemVT) const
Return true if the specified load with extension is legal on this target.
const DenseMap< unsigned int, unsigned int > & getBypassSlowDivWidths() const
Returns map of slow types for division or remainder with corresponding fast types.
virtual bool isCheapToSpeculateCtlz(Type *Ty) const
Return true if it is cheap to speculate a call to intrinsic ctlz.
virtual bool useSoftFloat() const
virtual int64_t getPreferredLargeGEPBaseOffset(int64_t MinOffset, int64_t MaxOffset) const
Return the prefered common base offset.
LegalizeTypeAction getTypeAction(LLVMContext &Context, EVT VT) const
Return how we should legalize values of this type, either it is already legal (return 'Legal') or we ...
virtual bool shouldAlignPointerArgs(CallInst *, unsigned &, Align &) const
Return true if the pointer arguments to CI should be aligned by aligning the object whose address is ...
virtual Type * shouldConvertSplatType(ShuffleVectorInst *SVI) const
Given a shuffle vector SVI representing a vector splat, return a new scalar type of size equal to SVI...
virtual bool addressingModeSupportsTLS(const GlobalValue &) const
Returns true if the targets addressing mode can target thread local storage (TLS).
virtual bool shouldConvertPhiType(Type *From, Type *To) const
Given a set in interconnected phis of type 'From' that are loaded/stored or bitcast to type 'To',...
virtual bool isFAbsFree(EVT VT) const
Return true if an fabs operation is free to the point where it is never worthwhile to replace it with...
virtual bool preferZeroCompareBranch() const
Return true if the heuristic to prefer icmp eq zero should be used in code gen prepare.
virtual bool 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'.
'undef' values are things that do not have specified contents.
static UndefValue * get(Type *T)
Static factory methods - Return an 'undef' object of the specified type.
A Use represents the edge between a Value definition and its users.
bool replaceUsesOfWith(Value *From, Value *To)
Replace uses of one Value with another.
const Use & getOperandUse(unsigned i) const
void setOperand(unsigned i, Value *Val)
Value * getOperand(unsigned i) const
unsigned getNumOperands() const
LLVM Value Representation.
Type * getType() const
All values are typed, get the type of this value.
const Value * stripAndAccumulateInBoundsConstantOffsets(const DataLayout &DL, APInt &Offset) const
This is a wrapper around stripAndAccumulateConstantOffsets with the in-bounds requirement set to fals...
user_iterator user_begin()
void setName(const Twine &Name)
Change the name of the value.
bool hasOneUse() const
Return true if there is exactly one use of this value.
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
iterator_range< user_iterator > users()
Align getPointerAlignment(const DataLayout &DL) const
Returns an alignment of the pointer value.
bool isUsedInBasicBlock(const BasicBlock *BB) const
Check if this value is used in the specified basic block.
bool hasNUsesOrMore(unsigned N) const
Return true if this value has N uses or more.
const Value * stripPointerCasts() const
Strip off pointer casts, all-zero GEPs and address space casts.
LLVMContext & getContext() const
All values hold a context through their type.
unsigned getNumUses() const
This method computes the number of uses of this Value.
iterator_range< use_iterator > uses()
void mutateType(Type *Ty)
Mutate the type of this Value to be of the specified type.
user_iterator_impl< User > user_iterator
StringRef getName() const
Return a constant reference to the value's name.
void takeName(Value *V)
Transfer the name from V to this value.
void dump() const
Support for debugging, callable in GDB: V->dump()
Value handle that is nullable, but tries to track the Value.
bool pointsToAliveValue() const
This class represents zero extension of integer types.
constexpr ScalarTy getFixedValue() const
constexpr bool isNonZero() const
constexpr bool isScalable() const
Returns whether the quantity is scaled by a runtime quantity (vscale).
StructType * getStructTypeOrNull() const
TypeSize getSequentialElementStride(const DataLayout &DL) const
const ParentTy * getParent() const
self_iterator getIterator()
NodeTy * getNextNode()
Get the next node, or nullptr for the list tail.
This class implements an extremely fast bulk output stream that can only output to a stream.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
@ C
The default llvm calling convention, compatible with C.
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
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, Style style=Style::native)
Get begin iterator over path.
const_iterator end(StringRef path)
Get end iterator over path.
This is an optimization pass for GlobalISel generic memory operations.
auto drop_begin(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the first N elements excluded.
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.