43#include "llvm/Config/llvm-config.h"
64#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);
474 bool combineToUSubWithOverflow(
CmpInst *Cmp, ModifyDT &ModifiedDT);
475 bool combineToUAddWithOverflow(
CmpInst *Cmp, ModifyDT &ModifiedDT);
505char CodeGenPrepareLegacyPass::ID = 0;
507bool CodeGenPrepareLegacyPass::runOnFunction(
Function &
F) {
511 CodeGenPrepare CGP(
TM);
512 CGP.DL = &
F.getParent()->getDataLayout();
513 CGP.SubtargetInfo =
TM->getSubtargetImpl(
F);
514 CGP.TLI = CGP.SubtargetInfo->getTargetLowering();
515 CGP.TRI = CGP.SubtargetInfo->getRegisterInfo();
516 CGP.TLInfo = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(
F);
517 CGP.TTI = &getAnalysis<TargetTransformInfoWrapperPass>().getTTI(
F);
518 CGP.LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
521 CGP.PSI = &getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI();
523 getAnalysisIfAvailable<BasicBlockSectionsProfileReaderWrapperPass>();
524 CGP.BBSectionsProfileReader = BBSPRWP ? &BBSPRWP->getBBSPR() :
nullptr;
530 "Optimize for code generation",
false,
false)
541 return new CodeGenPrepareLegacyPass();
546 CodeGenPrepare CGP(
TM);
548 bool Changed = CGP.run(
F, AM);
560 DL = &
F.getParent()->getDataLayout();
561 SubtargetInfo =
TM->getSubtargetImpl(
F);
571 BBSectionsProfileReader =
577 bool EverMadeChange =
false;
579 OptSize =
F.hasOptSize();
584 F.setSectionPrefix(
"hot");
589 if (
F.hasFnAttribute(Attribute::Hot) ||
590 PSI->isFunctionHotInCallGraph(&
F, *BFI))
591 F.setSectionPrefix(
"hot");
595 else if (PSI->isFunctionColdInCallGraph(&
F, *BFI) ||
596 F.hasFnAttribute(Attribute::Cold))
597 F.setSectionPrefix(
"unlikely");
599 PSI->isFunctionHotnessUnknown(
F))
600 F.setSectionPrefix(
"unknown");
609 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)) {
785 Value *Operand = Assume->getOperand(0);
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);
1203 for (
auto *ThisRelocate : AllRelocateCalls) {
1204 auto K = std::make_pair(ThisRelocate->getBasePtrIndex(),
1205 ThisRelocate->getDerivedPtrIndex());
1206 RelocateIdxMap.
insert(std::make_pair(K, ThisRelocate));
1208 for (
auto &Item : RelocateIdxMap) {
1209 std::pair<unsigned, unsigned> Key = Item.first;
1210 if (Key.first == Key.second)
1215 auto BaseKey = std::make_pair(Key.first, Key.first);
1218 auto MaybeBase = RelocateIdxMap.
find(BaseKey);
1219 if (MaybeBase == RelocateIdxMap.
end())
1224 RelocateInstMap[MaybeBase->second].push_back(
I);
1232 for (
unsigned i = 1; i <
GEP->getNumOperands(); i++) {
1234 auto *
Op = dyn_cast<ConstantInt>(
GEP->getOperand(i));
1235 if (!
Op ||
Op->getZExtValue() > 20)
1239 for (
unsigned i = 1; i <
GEP->getNumOperands(); i++)
1249 bool MadeChange =
false;
1257 &*R != RelocatedBase; ++R)
1258 if (
auto *RI = dyn_cast<GCRelocateInst>(R))
1268 "Not relocating a derived object of the original base object");
1269 if (ToReplace->getBasePtrIndex() == ToReplace->getDerivedPtrIndex()) {
1283 auto *Derived = dyn_cast<GetElementPtrInst>(ToReplace->getDerivedPtr());
1284 if (!Derived || Derived->getPointerOperand() !=
Base)
1293 "Should always have one since it's not a terminator");
1321 Value *ActualRelocatedBase = RelocatedBase;
1322 if (RelocatedBase->
getType() !=
Base->getType()) {
1323 ActualRelocatedBase =
1326 Value *Replacement =
1327 Builder.
CreateGEP(Derived->getSourceElementType(), ActualRelocatedBase,
1333 Value *ActualReplacement = Replacement;
1334 if (Replacement->
getType() != ToReplace->getType()) {
1339 ToReplace->eraseFromParent();
1364 bool MadeChange =
false;
1366 for (
auto *U :
I.users())
1373 if (AllRelocateCalls.
size() < 2)
1380 if (RelocateInstMap.
empty())
1383 for (
auto &Item : RelocateInstMap)
1397 bool MadeChange =
false;
1400 Use &TheUse = UI.getUse();
1407 UserBB = PN->getIncomingBlock(TheUse);
1415 if (
User->isEHPad())
1425 if (UserBB == DefBB)
1429 CastInst *&InsertedCast = InsertedCasts[UserBB];
1431 if (!InsertedCast) {
1441 TheUse = InsertedCast;
1465 if (
auto *ASC = dyn_cast<AddrSpaceCastInst>(CI)) {
1467 ASC->getDestAddressSpace()))
1507 match(IVInc, m_ExtractValue<0>(m_Intrinsic<Intrinsic::uadd_with_overflow>(
1511 match(IVInc, m_ExtractValue<0>(m_Intrinsic<Intrinsic::usub_with_overflow>(
1522static std::optional<std::pair<Instruction *, Constant *>>
1525 if (!L || L->getHeader() != PN->
getParent() || !L->getLoopLatch())
1526 return std::nullopt;
1529 if (!IVInc || LI->
getLoopFor(IVInc->getParent()) != L)
1530 return std::nullopt;
1534 return std::make_pair(IVInc, Step);
1535 return std::nullopt;
1539 auto *
I = dyn_cast<Instruction>(V);
1546 if (
auto *PN = dyn_cast<PHINode>(
LHS))
1548 return IVInc->first ==
I;
1552bool CodeGenPrepare::replaceMathCmpWithIntrinsic(
BinaryOperator *BO,
1560 assert(L &&
"L should not be null after isIVIncrement()");
1562 if (LI->getLoopFor(
Cmp->getParent()) != L)
1577 if (BO->
getParent() !=
Cmp->getParent() && !IsReplacableIVIncrement(BO)) {
1600 if (BO->
getOpcode() == Instruction::Add &&
1601 IID == Intrinsic::usub_with_overflow) {
1602 assert(isa<Constant>(Arg1) &&
"Unexpected input for usubo");
1611 if ((BO->
getOpcode() != Instruction::Xor && &Iter == BO) || &Iter == Cmp) {
1616 assert(InsertPt !=
nullptr &&
"Parent block did not contain cmp or binop");
1619 Value *MathOV = Builder.CreateBinaryIntrinsic(IID, Arg0, Arg1);
1620 if (BO->
getOpcode() != Instruction::Xor) {
1621 Value *Math = Builder.CreateExtractValue(MathOV, 0,
"math");
1625 "Patterns with XOr should use the BO only in the compare");
1626 Value *OV = Builder.CreateExtractValue(MathOV, 1,
"ov");
1628 Cmp->eraseFromParent();
1638 Value *
A = Cmp->getOperand(0), *
B = Cmp->getOperand(1);
1641 if (isa<Constant>(
A))
1646 B = ConstantInt::get(
B->getType(), 1);
1648 B = ConstantInt::get(
B->getType(), -1);
1654 for (
User *U :
A->users()) {
1656 Add = cast<BinaryOperator>(U);
1665bool CodeGenPrepare::combineToUAddWithOverflow(
CmpInst *Cmp,
1666 ModifyDT &ModifiedDT) {
1667 bool EdgeCase =
false;
1674 A =
Add->getOperand(0);
1675 B =
Add->getOperand(1);
1681 Add->hasNUsesOrMore(EdgeCase ? 1 : 2)))
1687 if (
Add->getParent() !=
Cmp->getParent() && !
Add->hasOneUse())
1690 if (!replaceMathCmpWithIntrinsic(
Add,
A,
B, Cmp,
1691 Intrinsic::uadd_with_overflow))
1695 ModifiedDT = ModifyDT::ModifyInstDT;
1699bool CodeGenPrepare::combineToUSubWithOverflow(
CmpInst *Cmp,
1700 ModifyDT &ModifiedDT) {
1703 if (isa<Constant>(
A) && isa<Constant>(
B))
1714 B = ConstantInt::get(
B->getType(), 1);
1728 Value *CmpVariableOperand = isa<Constant>(
A) ?
B :
A;
1730 for (
User *U : CmpVariableOperand->
users()) {
1733 Sub = cast<BinaryOperator>(U);
1738 const APInt *CmpC, *AddC;
1741 Sub = cast<BinaryOperator>(U);
1754 Cmp, Intrinsic::usub_with_overflow))
1758 ModifiedDT = ModifyDT::ModifyInstDT;
1779 bool MadeChange =
false;
1782 Use &TheUse = UI.getUse();
1789 if (isa<PHINode>(
User))
1797 if (UserBB == DefBB)
1801 CmpInst *&InsertedCmp = InsertedCmps[UserBB];
1807 Cmp->getOperand(0), Cmp->getOperand(1),
"");
1814 TheUse = InsertedCmp;
1820 if (Cmp->use_empty()) {
1821 Cmp->eraseFromParent();
1858 for (
User *U : Cmp->users()) {
1859 if (isa<BranchInst>(U))
1861 if (isa<SelectInst>(U) && cast<SelectInst>(U)->getCondition() == Cmp)
1880 if (CmpBB != FalseBB)
1883 Value *CmpOp0 = Cmp->getOperand(0), *CmpOp1 = Cmp->getOperand(1);
1897 for (
User *U : Cmp->users()) {
1898 if (
auto *BI = dyn_cast<BranchInst>(U)) {
1903 if (
auto *SI = dyn_cast<SelectInst>(U)) {
1906 SI->swapProfMetadata();
1918 Value *Op0 = Cmp->getOperand(0);
1919 Value *Op1 = Cmp->getOperand(1);
1921 isa<Constant>(Op1) || Op0 == Op1)
1928 unsigned NumInspected = 0;
1931 if (++NumInspected > 128)
1939 if (GoodToSwap > 0) {
1940 Cmp->swapOperands();
1948 FCmpInst *FCmp = dyn_cast<FCmpInst>(Cmp);
1960 auto ShouldReverseTransform = [](
FPClassTest ClassTest) {
1963 auto [ClassVal, ClassTest] =
1969 if (!ShouldReverseTransform(ClassTest) && !ShouldReverseTransform(~ClassTest))
1974 Cmp->replaceAllUsesWith(IsFPClass);
1979bool CodeGenPrepare::optimizeCmp(
CmpInst *Cmp, ModifyDT &ModifiedDT) {
1983 if (combineToUAddWithOverflow(Cmp, ModifiedDT))
1986 if (combineToUSubWithOverflow(Cmp, ModifiedDT))
2007 SetOfInstrs &InsertedInsts) {
2010 assert(!InsertedInsts.count(AndI) &&
2011 "Attempting to optimize already optimized and instruction");
2012 (void)InsertedInsts;
2021 if (!isa<ConstantInt>(AndI->
getOperand(0)) &&
2026 for (
auto *U : AndI->
users()) {
2030 if (!isa<ICmpInst>(
User))
2034 if (!CmpC || !CmpC->
isZero())
2049 Use &TheUse = UI.getUse();
2067 TheUse = InsertedAnd;
2083 if (!isa<TruncInst>(
User)) {
2084 if (
User->getOpcode() != Instruction::And ||
2090 if ((Cimm & (Cimm + 1)).getBoolValue())
2103 auto *TruncI = cast<TruncInst>(
User);
2104 bool MadeChange =
false;
2107 TruncE = TruncI->user_end();
2108 TruncUI != TruncE;) {
2110 Use &TruncTheUse = TruncUI.getUse();
2111 Instruction *TruncUser = cast<Instruction>(*TruncUI);
2130 if (isa<PHINode>(TruncUser))
2135 if (UserBB == TruncUserBB)
2139 CastInst *&InsertedTrunc = InsertedTruncs[TruncUserBB];
2141 if (!InsertedShift && !InsertedTrunc) {
2145 if (ShiftI->
getOpcode() == Instruction::AShr)
2147 BinaryOperator::CreateAShr(ShiftI->
getOperand(0), CI,
"");
2150 BinaryOperator::CreateLShr(ShiftI->
getOperand(0), CI,
"");
2158 TruncInsertPt.setHeadBit(
true);
2159 assert(TruncInsertPt != TruncUserBB->
end());
2163 InsertedTrunc->
insertBefore(*TruncUserBB, TruncInsertPt);
2164 InsertedTrunc->
setDebugLoc(TruncI->getDebugLoc());
2168 TruncTheUse = InsertedTrunc;
2201 bool MadeChange =
false;
2204 Use &TheUse = UI.getUse();
2210 if (isa<PHINode>(
User))
2218 if (UserBB == DefBB) {
2233 if (isa<TruncInst>(
User) &&
2246 if (!InsertedShift) {
2250 if (ShiftI->
getOpcode() == Instruction::AShr)
2252 BinaryOperator::CreateAShr(ShiftI->
getOperand(0), CI,
"");
2255 BinaryOperator::CreateLShr(ShiftI->
getOperand(0), CI,
"");
2263 TheUse = InsertedShift;
2312 if (Ty->
isVectorTy() || SizeInBits >
DL->getLargestLegalIntTypeSizeInBits())
2324 FreshBBs.
insert(CallBlock);
2331 SplitPt.setHeadBit(
true);
2334 FreshBBs.
insert(EndBlock);
2339 L->addBasicBlockToLoop(CallBlock, LI);
2340 L->addBasicBlockToLoop(EndBlock, LI);
2371 ModifiedDT = ModifyDT::ModifyBBDT;
2375bool CodeGenPrepare::optimizeCallInst(
CallInst *CI, ModifyDT &ModifiedDT) {
2384 CurInstIterator = BB->
begin();
2391 if (optimizeInlineAsmInst(CI))
2400 for (
auto &Arg : CI->
args()) {
2405 if (!Arg->getType()->isPointerTy())
2408 cast<PointerType>(Arg->getType())->getAddressSpace()),
2415 if ((AI = dyn_cast<AllocaInst>(Val)) && AI->
getAlign() < PrefAlign &&
2434 if (!MIDestAlign || DestAlign > *MIDestAlign)
2435 MI->setDestAlignment(DestAlign);
2437 MaybeAlign MTISrcAlign = MTI->getSourceAlign();
2439 if (!MTISrcAlign || SrcAlign > *MTISrcAlign)
2440 MTI->setSourceAlignment(SrcAlign);
2448 if (CI->
hasFnAttr(Attribute::Cold) && !OptSize &&
2450 for (
auto &Arg : CI->
args()) {
2451 if (!Arg->getType()->isPointerTy())
2453 unsigned AS = Arg->getType()->getPointerAddressSpace();
2454 if (optimizeMemoryInst(CI, Arg, Arg->getType(), AS))
2463 case Intrinsic::assume:
2465 case Intrinsic::allow_runtime_check:
2466 case Intrinsic::allow_ubsan_check:
2467 case Intrinsic::experimental_widenable_condition: {
2476 resetIteratorIfInvalidatedWhileCalling(BB, [&]() {
2481 case Intrinsic::objectsize:
2483 case Intrinsic::is_constant:
2485 case Intrinsic::aarch64_stlxr:
2486 case Intrinsic::aarch64_stxr: {
2495 InsertedInsts.insert(ExtVal);
2499 case Intrinsic::launder_invariant_group:
2500 case Intrinsic::strip_invariant_group: {
2502 auto it = LargeOffsetGEPMap.
find(II);
2503 if (it != LargeOffsetGEPMap.
end()) {
2507 auto GEPs = std::move(it->second);
2508 LargeOffsetGEPMap[ArgVal].append(GEPs.begin(), GEPs.end());
2509 LargeOffsetGEPMap.
erase(II);
2516 case Intrinsic::cttz:
2517 case Intrinsic::ctlz:
2521 case Intrinsic::fshl:
2522 case Intrinsic::fshr:
2523 return optimizeFunnelShift(II);
2524 case Intrinsic::dbg_assign:
2525 case Intrinsic::dbg_value:
2526 return fixupDbgValue(II);
2527 case Intrinsic::masked_gather:
2529 case Intrinsic::masked_scatter:
2536 while (!PtrOps.
empty()) {
2539 if (optimizeMemoryInst(II, PtrVal, AccessTy, AS))
2554 if (
Value *V = Simplifier.optimizeCall(CI, Builder)) {
2567 if (
const auto *II = dyn_cast<IntrinsicInst>(CI))
2569 case Intrinsic::memset:
2570 case Intrinsic::memcpy:
2571 case Intrinsic::memmove:
2579 if (Callee && TLInfo && TLInfo->
getLibFunc(*Callee, LF))
2581 case LibFunc_strcpy:
2582 case LibFunc_strncpy:
2583 case LibFunc_strcat:
2584 case LibFunc_strncat:
2625bool CodeGenPrepare::dupRetToEnableTailCallOpts(
BasicBlock *BB,
2626 ModifyDT &ModifiedDT) {
2634 assert(LI->getLoopFor(BB) ==
nullptr &&
"A return block cannot be in a loop");
2641 BCI = dyn_cast<BitCastInst>(V);
2645 EVI = dyn_cast<ExtractValueInst>(V);
2652 PN = dyn_cast<PHINode>(V);
2658 auto isLifetimeEndOrBitCastFor = [](
const Instruction *Inst) {
2659 const BitCastInst *BC = dyn_cast<BitCastInst>(Inst);
2663 if (
const IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst))
2672 while (isa<DbgInfoIntrinsic>(BI) || BI == BCI || BI == EVI ||
2673 isa<PseudoProbeInst>(BI) || isLifetimeEndOrBitCastFor(BI))
2686 CallInst *CI = dyn_cast<CallInst>(IncomingVal);
2705 CI = dyn_cast_or_null<CallInst>(
2719 if (!VisitedBBs.
insert(Pred).second)
2721 if (
Instruction *
I = Pred->rbegin()->getPrevNonDebugInstruction(
true)) {
2727 if (!V || isa<UndefValue>(V) ||
2737 bool Changed =
false;
2738 for (
auto const &TailCallBB : TailCallBBs) {
2741 BranchInst *BI = dyn_cast<BranchInst>(TailCallBB->getTerminator());
2748 BFI->getBlockFreq(BB) >=
BFI->getBlockFreq(TailCallBB));
2749 BFI->setBlockFreq(BB,
2750 (
BFI->getBlockFreq(BB) -
BFI->getBlockFreq(TailCallBB)));
2751 ModifiedDT = ModifyDT::ModifyBBDT;
2774 Value *OriginalValue =
nullptr;
2775 bool InBounds =
true;
2779 BaseRegField = 0x01,
2781 BaseOffsField = 0x04,
2782 ScaledRegField = 0x08,
2784 MultipleFields = 0xff
2797 return MultipleFields;
2798 if (BaseGV && other.BaseGV && BaseGV->getType() != other.BaseGV->getType())
2799 return MultipleFields;
2802 return MultipleFields;
2805 if (InBounds != other.InBounds)
2806 return MultipleFields;
2809 unsigned Result = NoField;
2812 if (BaseGV != other.BaseGV)
2814 if (BaseOffs != other.BaseOffs)
2817 Result |= ScaledRegField;
2824 return MultipleFields;
2826 return static_cast<FieldName
>(
Result);
2847 case ScaledRegField:
2850 return ConstantInt::get(IntPtrTy, BaseOffs);
2854 void SetCombinedField(FieldName
Field,
Value *V,
2860 case ExtAddrMode::BaseRegField:
2863 case ExtAddrMode::BaseGVField:
2870 case ExtAddrMode::ScaledRegField:
2881 case ExtAddrMode::BaseOffsField:
2900#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
2902 bool NeedPlus =
false;
2908 BaseGV->printAsOperand(
OS,
false);
2913 OS << (NeedPlus ?
" + " :
"") << BaseOffs;
2918 OS << (NeedPlus ?
" + " :
"") <<
"Base:";
2923 OS << (NeedPlus ?
" + " :
"") <<
Scale <<
"*";
2946class TypePromotionTransaction {
2950 class TypePromotionAction {
2958 TypePromotionAction(
Instruction *Inst) : Inst(Inst) {}
2960 virtual ~TypePromotionAction() =
default;
2967 virtual void undo() = 0;
2972 virtual void commit() {
2978 class InsertionHandler {
2987 std::optional<DbgRecord::self_iterator> BeforeDbgRecord = std::nullopt;
2990 bool HasPrevInstruction;
3003 if (HasPrevInstruction) {
3004 Point.PrevInst = &*std::prev(Inst->
getIterator());
3012 if (HasPrevInstruction) {
3029 class InstructionMoveBefore :
public TypePromotionAction {
3031 InsertionHandler Position;
3036 : TypePromotionAction(Inst), Position(Inst) {
3043 void undo()
override {
3045 Position.insert(Inst);
3050 class OperandSetter :
public TypePromotionAction {
3060 : TypePromotionAction(Inst),
Idx(
Idx) {
3062 <<
"for:" << *Inst <<
"\n"
3063 <<
"with:" << *NewVal <<
"\n");
3069 void undo()
override {
3071 <<
"for: " << *Inst <<
"\n"
3072 <<
"with: " << *Origin <<
"\n");
3079 class OperandsHider :
public TypePromotionAction {
3085 OperandsHider(
Instruction *Inst) : TypePromotionAction(Inst) {
3088 OriginalValues.
reserve(NumOpnds);
3089 for (
unsigned It = 0; It < NumOpnds; ++It) {
3101 void undo()
override {
3103 for (
unsigned It = 0, EndIt = OriginalValues.
size(); It != EndIt; ++It)
3109 class TruncBuilder :
public TypePromotionAction {
3116 TruncBuilder(
Instruction *Opnd,
Type *Ty) : TypePromotionAction(Opnd) {
3118 Builder.SetCurrentDebugLocation(
DebugLoc());
3119 Val = Builder.CreateTrunc(Opnd, Ty,
"promoted");
3124 Value *getBuiltValue() {
return Val; }
3127 void undo()
override {
3129 if (
Instruction *IVal = dyn_cast<Instruction>(Val))
3130 IVal->eraseFromParent();
3135 class SExtBuilder :
public TypePromotionAction {
3143 : TypePromotionAction(InsertPt) {
3145 Val = Builder.CreateSExt(Opnd, Ty,
"promoted");
3150 Value *getBuiltValue() {
return Val; }
3153 void undo()
override {
3155 if (
Instruction *IVal = dyn_cast<Instruction>(Val))
3156 IVal->eraseFromParent();
3161 class ZExtBuilder :
public TypePromotionAction {
3169 : TypePromotionAction(InsertPt) {
3171 Builder.SetCurrentDebugLocation(
DebugLoc());
3172 Val = Builder.CreateZExt(Opnd, Ty,
"promoted");
3177 Value *getBuiltValue() {
return Val; }
3180 void undo()
override {
3182 if (
Instruction *IVal = dyn_cast<Instruction>(Val))
3183 IVal->eraseFromParent();
3188 class TypeMutator :
public TypePromotionAction {
3195 : TypePromotionAction(Inst), OrigTy(Inst->
getType()) {
3196 LLVM_DEBUG(
dbgs() <<
"Do: MutateType: " << *Inst <<
" with " << *NewTy
3202 void undo()
override {
3203 LLVM_DEBUG(
dbgs() <<
"Undo: MutateType: " << *Inst <<
" with " << *OrigTy
3210 class UsesReplacer :
public TypePromotionAction {
3212 struct InstructionAndIdx {
3220 : Inst(Inst),
Idx(
Idx) {}
3239 : TypePromotionAction(Inst),
New(
New) {
3240 LLVM_DEBUG(
dbgs() <<
"Do: UsersReplacer: " << *Inst <<
" with " << *New
3245 OriginalUses.
push_back(InstructionAndIdx(UserI,
U.getOperandNo()));
3256 void undo()
override {
3258 for (InstructionAndIdx &
Use : OriginalUses)
3259 Use.Inst->setOperand(
Use.Idx, Inst);
3264 for (
auto *DVI : DbgValues)
3265 DVI->replaceVariableLocationOp(New, Inst);
3269 DVR->replaceVariableLocationOp(New, Inst);
3274 class InstructionRemover :
public TypePromotionAction {
3276 InsertionHandler Inserter;
3280 OperandsHider Hider;
3283 UsesReplacer *Replacer =
nullptr;
3286 SetOfInstrs &RemovedInsts;
3293 InstructionRemover(
Instruction *Inst, SetOfInstrs &RemovedInsts,
3294 Value *New =
nullptr)
3295 : TypePromotionAction(Inst), Inserter(Inst), Hider(Inst),
3296 RemovedInsts(RemovedInsts) {
3298 Replacer =
new UsesReplacer(Inst, New);
3299 LLVM_DEBUG(
dbgs() <<
"Do: InstructionRemover: " << *Inst <<
"\n");
3300 RemovedInsts.insert(Inst);
3307 ~InstructionRemover()
override {
delete Replacer; }
3309 InstructionRemover &operator=(
const InstructionRemover &other) =
delete;
3310 InstructionRemover(
const InstructionRemover &other) =
delete;
3314 void undo()
override {
3315 LLVM_DEBUG(
dbgs() <<
"Undo: InstructionRemover: " << *Inst <<
"\n");
3316 Inserter.insert(Inst);
3320 RemovedInsts.erase(Inst);
3328 using ConstRestorationPt =
const TypePromotionAction *;
3330 TypePromotionTransaction(SetOfInstrs &RemovedInsts)
3331 : RemovedInsts(RemovedInsts) {}
3338 void rollback(ConstRestorationPt Point);
3341 ConstRestorationPt getRestorationPoint()
const;
3373 SetOfInstrs &RemovedInsts;
3378void TypePromotionTransaction::setOperand(
Instruction *Inst,
unsigned Idx,
3380 Actions.
push_back(std::make_unique<TypePromotionTransaction::OperandSetter>(
3381 Inst,
Idx, NewVal));
3384void TypePromotionTransaction::eraseInstruction(
Instruction *Inst,
3387 std::make_unique<TypePromotionTransaction::InstructionRemover>(
3388 Inst, RemovedInsts, NewVal));
3391void TypePromotionTransaction::replaceAllUsesWith(
Instruction *Inst,
3394 std::make_unique<TypePromotionTransaction::UsesReplacer>(Inst, New));
3397void TypePromotionTransaction::mutateType(
Instruction *Inst,
Type *NewTy) {
3399 std::make_unique<TypePromotionTransaction::TypeMutator>(Inst, NewTy));
3403 std::unique_ptr<TruncBuilder>
Ptr(
new TruncBuilder(Opnd, Ty));
3405 Actions.push_back(std::move(
Ptr));
3411 std::unique_ptr<SExtBuilder>
Ptr(
new SExtBuilder(Inst, Opnd, Ty));
3413 Actions.push_back(std::move(
Ptr));
3419 std::unique_ptr<ZExtBuilder>
Ptr(
new ZExtBuilder(Inst, Opnd, Ty));
3421 Actions.push_back(std::move(
Ptr));
3425TypePromotionTransaction::ConstRestorationPt
3426TypePromotionTransaction::getRestorationPoint()
const {
3427 return !Actions.empty() ? Actions.back().get() :
nullptr;
3430bool TypePromotionTransaction::commit() {
3431 for (std::unique_ptr<TypePromotionAction> &Action : Actions)
3438void TypePromotionTransaction::rollback(
3439 TypePromotionTransaction::ConstRestorationPt Point) {
3440 while (!Actions.empty() && Point != Actions.back().get()) {
3441 std::unique_ptr<TypePromotionAction> Curr = Actions.pop_back_val();
3451class AddressingModeMatcher {
3470 const SetOfInstrs &InsertedInsts;
3473 InstrToOrigTy &PromotedInsts;
3476 TypePromotionTransaction &TPT;
3479 std::pair<AssertingVH<GetElementPtrInst>, int64_t> &LargeOffsetGEP;
3483 bool IgnoreProfitability;
3486 bool OptSize =
false;
3491 AddressingModeMatcher(
3496 const SetOfInstrs &InsertedInsts, InstrToOrigTy &PromotedInsts,
3497 TypePromotionTransaction &TPT,
3500 : AddrModeInsts(AMI), TLI(TLI),
TRI(
TRI),
3501 DL(
MI->getModule()->getDataLayout()), LI(LI), getDTFn(getDTFn),
3502 AccessTy(AT), AddrSpace(AS), MemoryInst(
MI),
AddrMode(AM),
3503 InsertedInsts(InsertedInsts), PromotedInsts(PromotedInsts), TPT(TPT),
3504 LargeOffsetGEP(LargeOffsetGEP), OptSize(OptSize), PSI(PSI),
BFI(
BFI) {
3505 IgnoreProfitability =
false;
3522 InstrToOrigTy &PromotedInsts, TypePromotionTransaction &TPT,
3527 bool Success = AddressingModeMatcher(AddrModeInsts, TLI,
TRI, LI, getDTFn,
3528 AccessTy, AS, MemoryInst, Result,
3529 InsertedInsts, PromotedInsts, TPT,
3530 LargeOffsetGEP, OptSize, PSI, BFI)
3538 bool matchScaledValue(
Value *ScaleReg, int64_t Scale,
unsigned Depth);
3540 bool matchOperationAddr(
User *AddrInst,
unsigned Opcode,
unsigned Depth,
3541 bool *MovedAway =
nullptr);
3542 bool isProfitableToFoldIntoAddressingMode(
Instruction *
I,
3545 bool valueAlreadyLiveAtInst(
Value *Val,
Value *KnownLive1,
Value *KnownLive2);
3546 bool isPromotionProfitable(
unsigned NewCost,
unsigned OldCost,
3547 Value *PromotedOperand)
const;
3553class PhiNodeSetIterator {
3554 PhiNodeSet *
const Set;
3555 size_t CurrentIndex = 0;
3560 PhiNodeSetIterator(PhiNodeSet *
const Set,
size_t Start);
3562 PhiNodeSetIterator &operator++();
3578 friend class PhiNodeSetIterator;
3581 using iterator = PhiNodeSetIterator;
3596 size_t FirstValidElement = 0;
3603 if (NodeMap.insert(std::make_pair(
Ptr,
NodeList.size())).second) {
3614 if (NodeMap.erase(
Ptr)) {
3615 SkipRemovedElements(FirstValidElement);
3625 FirstValidElement = 0;
3631 if (FirstValidElement == 0)
3632 SkipRemovedElements(FirstValidElement);
3633 return PhiNodeSetIterator(
this, FirstValidElement);
3637 iterator
end() {
return PhiNodeSetIterator(
this,
NodeList.size()); }
3640 size_t size()
const {
return NodeMap.size(); }
3651 void SkipRemovedElements(
size_t &CurrentIndex) {
3652 while (CurrentIndex <
NodeList.size()) {
3653 auto it = NodeMap.find(
NodeList[CurrentIndex]);
3656 if (it != NodeMap.end() && it->second == CurrentIndex)
3663PhiNodeSetIterator::PhiNodeSetIterator(PhiNodeSet *
const Set,
size_t Start)
3664 : Set(Set), CurrentIndex(Start) {}
3666PHINode *PhiNodeSetIterator::operator*()
const {
3668 "PhiNodeSet access out of range");
3669 return Set->NodeList[CurrentIndex];
3672PhiNodeSetIterator &PhiNodeSetIterator::operator++() {
3674 "PhiNodeSet access out of range");
3676 Set->SkipRemovedElements(CurrentIndex);
3680bool PhiNodeSetIterator::operator==(
const PhiNodeSetIterator &RHS)
const {
3681 return CurrentIndex ==
RHS.CurrentIndex;
3684bool PhiNodeSetIterator::operator!=(
const PhiNodeSetIterator &RHS)
const {
3685 return !((*this) ==
RHS);
3691class SimplificationTracker {
3696 PhiNodeSet AllPhiNodes;
3705 auto SV = Storage.
find(V);
3706 if (SV == Storage.
end())
3716 while (!WorkList.
empty()) {
3718 if (!Visited.
insert(
P).second)
3720 if (
auto *PI = dyn_cast<Instruction>(
P))
3722 for (
auto *U : PI->users())
3725 PI->replaceAllUsesWith(V);
3726 if (
auto *
PHI = dyn_cast<PHINode>(PI))
3727 AllPhiNodes.erase(
PHI);
3728 if (
auto *
Select = dyn_cast<SelectInst>(PI))
3730 PI->eraseFromParent();
3740 while (OldReplacement !=
From) {
3742 To = dyn_cast<PHINode>(OldReplacement);
3743 OldReplacement = Get(
From);
3745 assert(To && Get(To) == To &&
"Replacement PHI node is already replaced.");
3747 From->replaceAllUsesWith(To);
3748 AllPhiNodes.erase(
From);
3749 From->eraseFromParent();
3752 PhiNodeSet &newPhiNodes() {
return AllPhiNodes; }
3754 void insertNewPhi(
PHINode *PN) { AllPhiNodes.insert(PN); }
3758 unsigned countNewPhiNodes()
const {
return AllPhiNodes.size(); }
3760 unsigned countNewSelectNodes()
const {
return AllSelectNodes.
size(); }
3762 void destroyNewNodes(
Type *CommonType) {
3765 for (
auto *
I : AllPhiNodes) {
3766 I->replaceAllUsesWith(Dummy);
3767 I->eraseFromParent();
3769 AllPhiNodes.clear();
3770 for (
auto *
I : AllSelectNodes) {
3771 I->replaceAllUsesWith(Dummy);
3772 I->eraseFromParent();
3774 AllSelectNodes.clear();
3779class AddressingModeCombiner {
3781 typedef std::pair<PHINode *, PHINode *> PHIPair;
3788 ExtAddrMode::FieldName DifferentField = ExtAddrMode::NoField;
3791 bool AllAddrModesTrivial =
true;
3794 Type *CommonType =
nullptr;
3803 Value *CommonValue =
nullptr;
3807 : SQ(_SQ), Original(OriginalValue) {}
3809 ~AddressingModeCombiner() { eraseCommonValueIfDead(); }
3821 AllAddrModesTrivial = AllAddrModesTrivial && NewAddrMode.isTrivial();
3824 if (AddrModes.
empty()) {
3832 ExtAddrMode::FieldName ThisDifferentField =
3833 AddrModes[0].compare(NewAddrMode);
3834 if (DifferentField == ExtAddrMode::NoField)
3835 DifferentField = ThisDifferentField;
3836 else if (DifferentField != ThisDifferentField)
3837 DifferentField = ExtAddrMode::MultipleFields;
3840 bool CanHandle = DifferentField != ExtAddrMode::MultipleFields;
3843 CanHandle = CanHandle && DifferentField != ExtAddrMode::ScaleField;
3848 CanHandle = CanHandle && (DifferentField != ExtAddrMode::BaseOffsField ||
3853 CanHandle = CanHandle && (DifferentField != ExtAddrMode::BaseGVField ||
3854 !NewAddrMode.HasBaseReg);
3871 bool combineAddrModes() {
3873 if (AddrModes.
size() == 0)
3877 if (AddrModes.
size() == 1 || DifferentField == ExtAddrMode::NoField)
3882 if (AllAddrModesTrivial)
3885 if (!addrModeCombiningAllowed())
3891 FoldAddrToValueMapping
Map;
3892 if (!initializeMap(Map))
3895 CommonValue = findCommon(Map);
3897 AddrModes[0].SetCombinedField(DifferentField, CommonValue, AddrModes);
3898 return CommonValue !=
nullptr;
3904 void eraseCommonValueIfDead() {
3905 if (CommonValue && CommonValue->
getNumUses() == 0)
3906 if (
Instruction *CommonInst = dyn_cast<Instruction>(CommonValue))
3907 CommonInst->eraseFromParent();
3915 bool initializeMap(FoldAddrToValueMapping &Map) {
3920 for (
auto &AM : AddrModes) {
3921 Value *DV = AM.GetFieldAsValue(DifferentField, IntPtrTy);
3924 if (CommonType && CommonType !=
Type)
3927 Map[AM.OriginalValue] = DV;
3932 assert(CommonType &&
"At least one non-null value must be!");
3933 for (
auto *V : NullValue)
3961 Value *findCommon(FoldAddrToValueMapping &Map) {
3969 SimplificationTracker
ST(SQ);
3974 InsertPlaceholders(Map, TraverseOrder, ST);
3977 FillPlaceholders(Map, TraverseOrder, ST);
3980 ST.destroyNewNodes(CommonType);
3985 unsigned PhiNotMatchedCount = 0;
3987 ST.destroyNewNodes(CommonType);
3991 auto *
Result =
ST.Get(
Map.find(Original)->second);
3993 NumMemoryInstsPhiCreated +=
ST.countNewPhiNodes() + PhiNotMatchedCount;
3994 NumMemoryInstsSelectCreated +=
ST.countNewSelectNodes();
4003 PhiNodeSet &PhiNodesToMatch) {
4010 while (!WorkList.
empty()) {
4012 if (!Visited.
insert(Item).second)
4019 for (
auto *
B : Item.first->blocks()) {
4020 Value *FirstValue = Item.first->getIncomingValueForBlock(
B);
4021 Value *SecondValue = Item.second->getIncomingValueForBlock(
B);
4022 if (FirstValue == SecondValue)
4025 PHINode *FirstPhi = dyn_cast<PHINode>(FirstValue);
4026 PHINode *SecondPhi = dyn_cast<PHINode>(SecondValue);
4032 if (!FirstPhi || !SecondPhi || !PhiNodesToMatch.count(FirstPhi) ||
4037 if (Matcher.
count({FirstPhi, SecondPhi}))
4042 if (MatchedPHIs.
insert(FirstPhi).second)
4043 Matcher.
insert({FirstPhi, SecondPhi});
4045 WorkList.
push_back({FirstPhi, SecondPhi});
4054 bool MatchPhiSet(SimplificationTracker &ST,
bool AllowNewPhiNodes,
4055 unsigned &PhiNotMatchedCount) {
4061 PhiNodeSet &PhiNodesToMatch =
ST.newPhiNodes();
4062 while (PhiNodesToMatch.size()) {
4066 WillNotMatch.
clear();
4070 bool IsMatched =
false;
4071 for (
auto &
P :
PHI->getParent()->phis()) {
4073 if (PhiNodesToMatch.count(&
P))
4075 if ((IsMatched = MatchPhiNode(
PHI, &
P, Matched, PhiNodesToMatch)))
4080 for (
auto M : Matched)
4086 for (
auto MV : Matched)
4087 ST.ReplacePhi(MV.first, MV.second);
4092 if (!AllowNewPhiNodes)
4095 PhiNotMatchedCount += WillNotMatch.
size();
4096 for (
auto *
P : WillNotMatch)
4097 PhiNodesToMatch.erase(
P);
4102 void FillPlaceholders(FoldAddrToValueMapping &Map,
4104 SimplificationTracker &ST) {
4105 while (!TraverseOrder.
empty()) {
4107 assert(
Map.contains(Current) &&
"No node to fill!!!");
4112 auto *CurrentSelect = cast<SelectInst>(Current);
4113 auto *TrueValue = CurrentSelect->getTrueValue();
4114 assert(
Map.contains(TrueValue) &&
"No True Value!");
4115 Select->setTrueValue(
ST.Get(Map[TrueValue]));
4116 auto *FalseValue = CurrentSelect->getFalseValue();
4117 assert(
Map.contains(FalseValue) &&
"No False Value!");
4118 Select->setFalseValue(
ST.Get(Map[FalseValue]));
4121 auto *
PHI = cast<PHINode>(V);
4124 Value *PV = cast<PHINode>(Current)->getIncomingValueForBlock(
B);
4125 assert(
Map.contains(PV) &&
"No predecessor Value!");
4126 PHI->addIncoming(
ST.Get(Map[PV]),
B);
4129 Map[Current] =
ST.Simplify(V);
4138 void InsertPlaceholders(FoldAddrToValueMapping &Map,
4140 SimplificationTracker &ST) {
4142 assert((isa<PHINode>(Original) || isa<SelectInst>(Original)) &&
4143 "Address must be a Phi or Select node");
4146 while (!Worklist.
empty()) {
4149 if (
Map.contains(Current))
4155 if (
SelectInst *CurrentSelect = dyn_cast<SelectInst>(Current)) {
4160 CurrentSelect->getName(),
4161 CurrentSelect->getIterator(), CurrentSelect);
4165 Worklist.
push_back(CurrentSelect->getTrueValue());
4166 Worklist.
push_back(CurrentSelect->getFalseValue());
4169 PHINode *CurrentPhi = cast<PHINode>(Current);
4174 ST.insertNewPhi(
PHI);
4180 bool addrModeCombiningAllowed() {
4183 switch (DifferentField) {
4186 case ExtAddrMode::BaseRegField:
4188 case ExtAddrMode::BaseGVField:
4190 case ExtAddrMode::BaseOffsField:
4192 case ExtAddrMode::ScaledRegField:
4202bool AddressingModeMatcher::matchScaledValue(
Value *ScaleReg, int64_t Scale,
4207 return matchAddr(ScaleReg,
Depth);
4222 TestAddrMode.
Scale += Scale;
4237 Value *AddLHS =
nullptr;
4238 if (isa<Instruction>(ScaleReg) &&
4241 TestAddrMode.InBounds =
false;
4248 AddrModeInsts.
push_back(cast<Instruction>(ScaleReg));
4258 auto GetConstantStep =
4259 [
this](
const Value *
V) -> std::optional<std::pair<Instruction *, APInt>> {
4260 auto *PN = dyn_cast<PHINode>(V);
4262 return std::nullopt;
4265 return std::nullopt;
4272 if (
auto *OIVInc = dyn_cast<OverflowingBinaryOperator>(IVInc->first))
4273 if (OIVInc->hasNoSignedWrap() || OIVInc->hasNoUnsignedWrap())
4274 return std::nullopt;
4275 if (
auto *ConstantStep = dyn_cast<ConstantInt>(IVInc->second))
4276 return std::make_pair(IVInc->first, ConstantStep->getValue());
4277 return std::nullopt;
4292 if (
auto IVStep = GetConstantStep(ScaleReg)) {
4299 APInt Step = IVStep->second;
4301 if (
Offset.isSignedIntN(64)) {
4302 TestAddrMode.InBounds =
false;
4304 TestAddrMode.BaseOffs -=
Offset.getLimitedValue();
4309 getDTFn().
dominates(IVInc, MemoryInst)) {
4310 AddrModeInsts.
push_back(cast<Instruction>(IVInc));
4329 switch (
I->getOpcode()) {
4330 case Instruction::BitCast:
4331 case Instruction::AddrSpaceCast:
4333 if (
I->getType() ==
I->getOperand(0)->getType())
4335 return I->getType()->isIntOrPtrTy();
4336 case Instruction::PtrToInt:
4339 case Instruction::IntToPtr:
4342 case Instruction::Add:
4344 case Instruction::Mul:
4345 case Instruction::Shl:
4347 return isa<ConstantInt>(
I->getOperand(1));
4348 case Instruction::GetElementPtr:
4361 Instruction *PromotedInst = dyn_cast<Instruction>(Val);
4376class TypePromotionHelper {
4379 static void addPromotedInst(InstrToOrigTy &PromotedInsts,
4381 ExtType ExtTy = IsSExt ? SignExtension : ZeroExtension;
4382 InstrToOrigTy::iterator It = PromotedInsts.find(ExtOpnd);
4383 if (It != PromotedInsts.end()) {
4386 if (It->second.getInt() == ExtTy)
4392 ExtTy = BothExtension;
4394 PromotedInsts[ExtOpnd] = TypeIsSExt(ExtOpnd->
getType(), ExtTy);
4401 static const Type *getOrigType(
const InstrToOrigTy &PromotedInsts,
4403 ExtType ExtTy = IsSExt ? SignExtension : ZeroExtension;
4404 InstrToOrigTy::const_iterator It = PromotedInsts.find(Opnd);
4405 if (It != PromotedInsts.end() && It->second.getInt() == ExtTy)
4406 return It->second.getPointer();
4421 static bool canGetThrough(
const Instruction *Inst,
Type *ConsideredExtType,
4422 const InstrToOrigTy &PromotedInsts,
bool IsSExt);
4426 static bool shouldExtOperand(
const Instruction *Inst,
int OpIdx) {
4427 return !(isa<SelectInst>(Inst) && OpIdx == 0);
4439 static Value *promoteOperandForTruncAndAnyExt(
4441 InstrToOrigTy &PromotedInsts,
unsigned &CreatedInstsCost,
4455 TypePromotionTransaction &TPT,
4456 InstrToOrigTy &PromotedInsts,
4457 unsigned &CreatedInstsCost,
4463 static Value *signExtendOperandForOther(
4465 InstrToOrigTy &PromotedInsts,
unsigned &CreatedInstsCost,
4468 return promoteOperandForOther(Ext, TPT, PromotedInsts, CreatedInstsCost,
4469 Exts, Truncs, TLI,
true);
4473 static Value *zeroExtendOperandForOther(
4475 InstrToOrigTy &PromotedInsts,
unsigned &CreatedInstsCost,
4478 return promoteOperandForOther(Ext, TPT, PromotedInsts, CreatedInstsCost,
4479 Exts, Truncs, TLI,
false);
4485 InstrToOrigTy &PromotedInsts,
4486 unsigned &CreatedInstsCost,
4502 const InstrToOrigTy &PromotedInsts);
4507bool TypePromotionHelper::canGetThrough(
const Instruction *Inst,
4508 Type *ConsideredExtType,
4509 const InstrToOrigTy &PromotedInsts,
4518 if (isa<ZExtInst>(Inst))
4522 if (IsSExt && isa<SExtInst>(Inst))
4527 if (
const auto *BinOp = dyn_cast<BinaryOperator>(Inst))
4528 if (isa<OverflowingBinaryOperator>(BinOp) &&
4529 ((!IsSExt && BinOp->hasNoUnsignedWrap()) ||
4530 (IsSExt && BinOp->hasNoSignedWrap())))
4534 if ((Inst->
getOpcode() == Instruction::And ||
4539 if (Inst->
getOpcode() == Instruction::Xor) {
4541 if (
const auto *Cst = dyn_cast<ConstantInt>(Inst->
getOperand(1)))
4542 if (!Cst->getValue().isAllOnes())
4551 if (Inst->
getOpcode() == Instruction::LShr && !IsSExt)
4560 const auto *ExtInst = cast<const Instruction>(*Inst->
user_begin());
4561 if (ExtInst->hasOneUse()) {
4562 const auto *AndInst = dyn_cast<const Instruction>(*ExtInst->user_begin());
4563 if (AndInst && AndInst->getOpcode() == Instruction::And) {
4564 const auto *Cst = dyn_cast<ConstantInt>(AndInst->getOperand(1));
4574 if (!isa<TruncInst>(Inst))
4588 Instruction *Opnd = dyn_cast<Instruction>(OpndVal);
4596 const Type *OpndType = getOrigType(PromotedInsts, Opnd, IsSExt);
4599 else if ((IsSExt && isa<SExtInst>(Opnd)) || (!IsSExt && isa<ZExtInst>(Opnd)))
4609TypePromotionHelper::Action TypePromotionHelper::getAction(
4610 Instruction *Ext,
const SetOfInstrs &InsertedInsts,
4612 assert((isa<SExtInst>(Ext) || isa<ZExtInst>(Ext)) &&
4613 "Unexpected instruction type");
4614 Instruction *ExtOpnd = dyn_cast<Instruction>(
Ext->getOperand(0));
4616 bool IsSExt = isa<SExtInst>(Ext);
4620 if (!ExtOpnd || !canGetThrough(ExtOpnd, ExtTy, PromotedInsts, IsSExt))
4626 if (isa<TruncInst>(ExtOpnd) && InsertedInsts.count(ExtOpnd))
4631 if (isa<SExtInst>(ExtOpnd) || isa<TruncInst>(ExtOpnd) ||
4632 isa<ZExtInst>(ExtOpnd))
4633 return promoteOperandForTruncAndAnyExt;
4639 return IsSExt ? signExtendOperandForOther : zeroExtendOperandForOther;
4642Value *TypePromotionHelper::promoteOperandForTruncAndAnyExt(
4644 InstrToOrigTy &PromotedInsts,
unsigned &CreatedInstsCost,
4650 Value *ExtVal = SExt;
4651 bool HasMergedNonFreeExt =
false;
4652 if (isa<ZExtInst>(SExtOpnd)) {
4655 HasMergedNonFreeExt = !TLI.
isExtFree(SExtOpnd);
4659 TPT.eraseInstruction(SExt);
4664 TPT.setOperand(SExt, 0, SExtOpnd->
getOperand(0));
4666 CreatedInstsCost = 0;
4670 TPT.eraseInstruction(SExtOpnd);
4673 Instruction *ExtInst = dyn_cast<Instruction>(ExtVal);
4678 CreatedInstsCost = !TLI.
isExtFree(ExtInst) && !HasMergedNonFreeExt;
4686 TPT.eraseInstruction(ExtInst, NextVal);
4690Value *TypePromotionHelper::promoteOperandForOther(
4692 InstrToOrigTy &PromotedInsts,
unsigned &CreatedInstsCost,
4699 CreatedInstsCost = 0;
4705 Value *Trunc = TPT.createTrunc(Ext, ExtOpnd->
getType());
4706 if (
Instruction *ITrunc = dyn_cast<Instruction>(Trunc)) {
4708 ITrunc->moveAfter(ExtOpnd);
4713 TPT.replaceAllUsesWith(ExtOpnd, Trunc);
4716 TPT.setOperand(Ext, 0, ExtOpnd);
4726 addPromotedInst(PromotedInsts, ExtOpnd, IsSExt);
4728 TPT.mutateType(ExtOpnd,
Ext->getType());
4730 TPT.replaceAllUsesWith(Ext, ExtOpnd);
4733 for (
int OpIdx = 0, EndOpIdx = ExtOpnd->
getNumOperands(); OpIdx != EndOpIdx;
4737 !shouldExtOperand(ExtOpnd, OpIdx)) {
4743 if (
const ConstantInt *Cst = dyn_cast<ConstantInt>(Opnd)) {
4745 unsigned BitWidth =
Ext->getType()->getIntegerBitWidth();
4748 TPT.setOperand(ExtOpnd, OpIdx, ConstantInt::get(
Ext->getType(), CstVal));
4752 if (isa<UndefValue>(Opnd)) {
4759 Value *ValForExtOpnd = IsSExt
4760 ? TPT.createSExt(ExtOpnd, Opnd,
Ext->getType())
4761 : TPT.createZExt(ExtOpnd, Opnd,
Ext->getType());
4762 TPT.setOperand(ExtOpnd, OpIdx, ValForExtOpnd);
4763 Instruction *InstForExtOpnd = dyn_cast<Instruction>(ValForExtOpnd);
4764 if (!InstForExtOpnd)
4770 CreatedInstsCost += !TLI.
isExtFree(InstForExtOpnd);
4773 TPT.eraseInstruction(Ext);
4785bool AddressingModeMatcher::isPromotionProfitable(
4786 unsigned NewCost,
unsigned OldCost,
Value *PromotedOperand)
const {
4787 LLVM_DEBUG(
dbgs() <<
"OldCost: " << OldCost <<
"\tNewCost: " << NewCost
4792 if (NewCost > OldCost)
4794 if (NewCost < OldCost)
4813bool AddressingModeMatcher::matchOperationAddr(
User *AddrInst,
unsigned Opcode,
4825 case Instruction::PtrToInt:
4828 case Instruction::IntToPtr: {
4836 case Instruction::BitCast:
4846 case Instruction::AddrSpaceCast: {
4854 case Instruction::Add: {
4858 unsigned OldSize = AddrModeInsts.
size();
4863 TypePromotionTransaction::ConstRestorationPt LastKnownGood =
4864 TPT.getRestorationPoint();
4868 int First = 0, Second = 1;
4870 && !isa<ConstantInt>(AddrInst->
getOperand(Second)))
4879 AddrModeInsts.
resize(OldSize);
4880 TPT.rollback(LastKnownGood);
4890 AddrModeInsts.
resize(OldSize);
4891 TPT.rollback(LastKnownGood);
4897 case Instruction::Mul:
4898 case Instruction::Shl: {
4902 if (!RHS ||
RHS->getBitWidth() > 64)
4904 int64_t Scale = Opcode == Instruction::Shl
4905 ? 1LL <<
RHS->getLimitedValue(
RHS->getBitWidth() - 1)
4906 :
RHS->getSExtValue();
4910 case Instruction::GetElementPtr: {
4913 int VariableOperand = -1;
4914 unsigned VariableScale = 0;
4916 int64_t ConstantOffset = 0;
4918 for (
unsigned i = 1, e = AddrInst->
getNumOperands(); i != e; ++i, ++GTI) {
4922 cast<ConstantInt>(AddrInst->
getOperand(i))->getZExtValue();
4932 dyn_cast<ConstantInt>(AddrInst->
getOperand(i))) {
4940 if (VariableOperand != -1)
4944 VariableOperand = i;
4952 if (VariableOperand == -1) {
4953 AddrMode.BaseOffs += ConstantOffset;
4955 if (!cast<GEPOperator>(AddrInst)->isInBounds())
4959 AddrMode.BaseOffs -= ConstantOffset;
4963 ConstantOffset > 0) {
4969 auto *BaseI = dyn_cast<Instruction>(
Base);
4970 auto *
GEP = cast<GetElementPtrInst>(AddrInst);
4971 if (isa<Argument>(
Base) || isa<GlobalValue>(
Base) ||
4972 (BaseI && !isa<CastInst>(BaseI) &&
4973 !isa<GetElementPtrInst>(BaseI))) {
4977 : &
GEP->getFunction()->getEntryBlock();
4979 LargeOffsetGEP = std::make_pair(
GEP, ConstantOffset);
4988 unsigned OldSize = AddrModeInsts.
size();
4991 AddrMode.BaseOffs += ConstantOffset;
4992 if (!cast<GEPOperator>(AddrInst)->isInBounds())
5000 AddrModeInsts.
resize(OldSize);
5008 if (!matchScaledValue(AddrInst->
getOperand(VariableOperand), VariableScale,
5013 AddrModeInsts.
resize(OldSize);
5018 AddrMode.BaseOffs += ConstantOffset;
5019 if (!matchScaledValue(AddrInst->
getOperand(VariableOperand),
5020 VariableScale,
Depth)) {
5023 AddrModeInsts.
resize(OldSize);
5030 case Instruction::SExt:
5031 case Instruction::ZExt: {
5038 TypePromotionHelper::Action TPH =
5039 TypePromotionHelper::getAction(Ext, InsertedInsts, TLI, PromotedInsts);
5043 TypePromotionTransaction::ConstRestorationPt LastKnownGood =
5044 TPT.getRestorationPoint();
5045 unsigned CreatedInstsCost = 0;
5047 Value *PromotedOperand =
5048 TPH(Ext, TPT, PromotedInsts, CreatedInstsCost,
nullptr,
nullptr, TLI);
5063 assert(PromotedOperand &&
5064 "TypePromotionHelper should have filtered out those cases");
5067 unsigned OldSize = AddrModeInsts.
size();
5069 if (!matchAddr(PromotedOperand,
Depth) ||
5074 !isPromotionProfitable(CreatedInstsCost,
5075 ExtCost + (AddrModeInsts.
size() - OldSize),
5078 AddrModeInsts.
resize(OldSize);
5079 LLVM_DEBUG(
dbgs() <<
"Sign extension does not pay off: rollback\n");
5080 TPT.rollback(LastKnownGood);
5085 case Instruction::Call:
5086 if (
IntrinsicInst *II = dyn_cast<IntrinsicInst>(AddrInst)) {
5103bool AddressingModeMatcher::matchAddr(
Value *
Addr,
unsigned Depth) {
5106 TypePromotionTransaction::ConstRestorationPt LastKnownGood =
5107 TPT.getRestorationPoint();
5126 unsigned OldSize = AddrModeInsts.
size();
5129 bool MovedAway =
false;
5130 if (matchOperationAddr(
I,
I->getOpcode(),
Depth, &MovedAway)) {
5138 if (
I->hasOneUse() ||
5139 isProfitableToFoldIntoAddressingMode(
I, BackupAddrMode,
AddrMode)) {
5146 AddrModeInsts.
resize(OldSize);
5147 TPT.rollback(LastKnownGood);
5150 if (matchOperationAddr(CE,
CE->getOpcode(),
Depth))
5152 TPT.rollback(LastKnownGood);
5153 }
else if (isa<ConstantPointerNull>(
Addr)) {
5179 TPT.rollback(LastKnownGood);
5198 if (OpInfo.CallOperandVal == OpVal &&
5200 !OpInfo.isIndirect))
5216 if (!ConsideredInsts.
insert(
I).second)
5224 for (
Use &U :
I->uses()) {
5230 Instruction *UserI = cast<Instruction>(U.getUser());
5231 if (
LoadInst *LI = dyn_cast<LoadInst>(UserI)) {
5232 MemoryUses.push_back({&U, LI->getType()});
5236 if (
StoreInst *SI = dyn_cast<StoreInst>(UserI)) {
5239 MemoryUses.push_back({&U, SI->getValueOperand()->
getType()});
5246 MemoryUses.push_back({&U, RMW->getValOperand()->
getType()});
5253 MemoryUses.push_back({&U, CmpX->getCompareOperand()->
getType()});
5257 if (
CallInst *CI = dyn_cast<CallInst>(UserI)) {
5258 if (CI->hasFnAttr(Attribute::Cold)) {
5267 InlineAsm *IA = dyn_cast<InlineAsm>(CI->getCalledOperand());
5278 PSI, BFI, SeenInsts))
5289 unsigned SeenInsts = 0;
5292 PSI, BFI, SeenInsts);
5300bool AddressingModeMatcher::valueAlreadyLiveAtInst(
Value *Val,
5302 Value *KnownLive2) {
5304 if (Val ==
nullptr || Val == KnownLive1 || Val == KnownLive2)
5308 if (!isa<Instruction>(Val) && !isa<Argument>(Val))
5314 if (
AllocaInst *AI = dyn_cast<AllocaInst>(Val))
5345bool AddressingModeMatcher::isProfitableToFoldIntoAddressingMode(
5347 if (IgnoreProfitability)
5365 if (valueAlreadyLiveAtInst(ScaledReg, AMBefore.
BaseReg, AMBefore.
ScaledReg))
5366 ScaledReg =
nullptr;
5370 if (!BaseReg && !ScaledReg)
5391 for (
const std::pair<Use *, Type *> &Pair : MemoryUses) {
5393 Instruction *UserI = cast<Instruction>(Pair.first->getUser());
5394 Type *AddressAccessTy = Pair.second;
5395 unsigned AS =
Address->getType()->getPointerAddressSpace();
5401 std::pair<AssertingVH<GetElementPtrInst>, int64_t> LargeOffsetGEP(
nullptr,
5403 TypePromotionTransaction::ConstRestorationPt LastKnownGood =
5404 TPT.getRestorationPoint();
5405 AddressingModeMatcher Matcher(MatchedAddrModeInsts, TLI,
TRI, LI, getDTFn,
5406 AddressAccessTy, AS, UserI, Result,
5407 InsertedInsts, PromotedInsts, TPT,
5408 LargeOffsetGEP, OptSize, PSI, BFI);
5409 Matcher.IgnoreProfitability =
true;
5410 bool Success = Matcher.matchAddr(Address, 0);
5417 TPT.rollback(LastKnownGood);
5423 MatchedAddrModeInsts.
clear();
5433 return I->getParent() != BB;
5457 Type *AccessTy,
unsigned AddrSpace) {
5469 bool PhiOrSelectSeen =
false;
5472 AddressingModeCombiner AddrModes(SQ,
Addr);
5473 TypePromotionTransaction TPT(RemovedInsts);
5474 TypePromotionTransaction::ConstRestorationPt LastKnownGood =
5475 TPT.getRestorationPoint();
5476 while (!worklist.
empty()) {
5488 if (!Visited.
insert(V).second)
5492 if (
PHINode *
P = dyn_cast<PHINode>(V)) {
5494 PhiOrSelectSeen =
true;
5498 if (
SelectInst *SI = dyn_cast<SelectInst>(V)) {
5501 PhiOrSelectSeen =
true;
5508 AddrModeInsts.
clear();
5509 std::pair<AssertingVH<GetElementPtrInst>, int64_t> LargeOffsetGEP(
nullptr,
5514 auto getDTFn = [MemoryInst,
this]() ->
const DominatorTree & {
5516 return this->getDT(*
F);
5518 ExtAddrMode NewAddrMode = AddressingModeMatcher::Match(
5519 V, AccessTy, AddrSpace, MemoryInst, AddrModeInsts, *TLI, *LI, getDTFn,
5520 *
TRI, InsertedInsts, PromotedInsts, TPT, LargeOffsetGEP, OptSize, PSI,
5528 LargeOffsetGEPMap[
GEP->getPointerOperand()].push_back(LargeOffsetGEP);
5529 LargeOffsetGEPID.
insert(std::make_pair(
GEP, LargeOffsetGEPID.
size()));
5532 NewAddrMode.OriginalValue =
V;
5533 if (!AddrModes.addNewAddrMode(NewAddrMode))
5540 if (!AddrModes.combineAddrModes()) {
5541 TPT.rollback(LastKnownGood);
5553 if (!PhiOrSelectSeen &&
none_of(AddrModeInsts, [&](
Value *V) {
5575 Type *IntPtrTy =
DL->getIntPtrType(
Addr->getType());
5578 <<
" for " << *MemoryInst <<
"\n");
5581 Addr->getType()->getPointerAddressSpace() &&
5582 !
DL->isNonIntegralPointerType(
Addr->getType())) {
5588 SunkAddr = Builder.CreatePtrToInt(SunkAddr, IntPtrTy,
"sunkaddr");
5590 Builder.CreateIntToPtr(SunkAddr,
Addr->getType(),
"sunkaddr");
5592 SunkAddr = Builder.CreatePointerCast(SunkAddr,
Addr->getType());
5599 <<
" for " << *MemoryInst <<
"\n");
5600 Value *ResultPtr =
nullptr, *ResultIndex =
nullptr;
5611 if (ResultPtr ||
AddrMode.Scale != 1)
5633 if (BaseGV !=
nullptr) {
5638 ResultPtr = Builder.CreateThreadLocalAddress(BaseGV);
5647 if (!
DL->isNonIntegralPointerType(
Addr->getType())) {
5648 if (!ResultPtr &&
AddrMode.BaseReg) {
5649 ResultPtr = Builder.CreateIntToPtr(
AddrMode.BaseReg,
Addr->getType(),
5652 }
else if (!ResultPtr &&
AddrMode.Scale == 1) {
5653 ResultPtr = Builder.CreateIntToPtr(
AddrMode.ScaledReg,
Addr->getType(),
5662 }
else if (!ResultPtr) {
5666 Builder.getPtrTy(
Addr->getType()->getPointerAddressSpace());
5675 if (
V->getType() != IntPtrTy)
5676 V = Builder.CreateIntCast(V, IntPtrTy,
true,
"sunkaddr");
5684 if (
V->getType() == IntPtrTy) {
5688 cast<IntegerType>(
V->getType())->getBitWidth() &&
5689 "We can't transform if ScaledReg is too narrow");
5690 V = Builder.CreateTrunc(V, IntPtrTy,
"sunkaddr");
5694 V = Builder.CreateMul(V, ConstantInt::get(IntPtrTy,
AddrMode.Scale),
5697 ResultIndex = Builder.CreateAdd(ResultIndex, V,
"sunkaddr");
5708 if (ResultPtr->
getType() != I8PtrTy)
5709 ResultPtr = Builder.CreatePointerCast(ResultPtr, I8PtrTy);
5710 ResultPtr = Builder.CreatePtrAdd(ResultPtr, ResultIndex,
"sunkaddr",
5718 SunkAddr = ResultPtr;
5720 if (ResultPtr->
getType() != I8PtrTy)
5721 ResultPtr = Builder.CreatePointerCast(ResultPtr, I8PtrTy);
5722 SunkAddr = Builder.CreatePtrAdd(ResultPtr, ResultIndex,
"sunkaddr",
5728 Addr->getType()->getPointerAddressSpace() &&
5729 !
DL->isNonIntegralPointerType(
Addr->getType())) {
5735 SunkAddr = Builder.CreatePtrToInt(SunkAddr, IntPtrTy,
"sunkaddr");
5737 Builder.CreateIntToPtr(SunkAddr,
Addr->getType(),
"sunkaddr");
5739 SunkAddr = Builder.CreatePointerCast(SunkAddr,
Addr->getType());
5748 PointerType *ScalePtrTy = dyn_cast_or_null<PointerType>(ScaleTy);
5749 if (
DL->isNonIntegralPointerType(
Addr->getType()) ||
5750 (BasePtrTy &&
DL->isNonIntegralPointerType(BasePtrTy)) ||
5751 (ScalePtrTy &&
DL->isNonIntegralPointerType(ScalePtrTy)) ||
5753 DL->isNonIntegralPointerType(
AddrMode.BaseGV->getType())))
5757 <<
" for " << *MemoryInst <<
"\n");
5758 Type *IntPtrTy =
DL->getIntPtrType(
Addr->getType());
5768 if (
V->getType()->isPointerTy())
5769 V = Builder.CreatePtrToInt(V, IntPtrTy,
"sunkaddr");
5770 if (
V->getType() != IntPtrTy)
5771 V = Builder.CreateIntCast(V, IntPtrTy,
true,
"sunkaddr");
5778 if (
V->getType() == IntPtrTy) {
5780 }
else if (
V->getType()->isPointerTy()) {
5781 V = Builder.CreatePtrToInt(V, IntPtrTy,
"sunkaddr");
5782 }
else if (cast<IntegerType>(IntPtrTy)->
getBitWidth() <
5783 cast<IntegerType>(
V->getType())->getBitWidth()) {
5784 V = Builder.CreateTrunc(V, IntPtrTy,
"sunkaddr");
5791 Instruction *
I = dyn_cast_or_null<Instruction>(Result);
5793 I->eraseFromParent();
5797 V = Builder.CreateMul(V, ConstantInt::get(IntPtrTy,
AddrMode.Scale),
5800 Result = Builder.CreateAdd(Result, V,
"sunkaddr");
5807 if (BaseGV !=
nullptr) {
5810 BaseGVPtr = Builder.CreateThreadLocalAddress(BaseGV);
5814 Value *
V = Builder.CreatePtrToInt(BaseGVPtr, IntPtrTy,
"sunkaddr");
5816 Result = Builder.CreateAdd(Result, V,
"sunkaddr");
5825 Result = Builder.CreateAdd(Result, V,
"sunkaddr");
5833 SunkAddr = Builder.CreateIntToPtr(Result,
Addr->getType(),
"sunkaddr");
5844 resetIteratorIfInvalidatedWhileCalling(CurInstIterator->getParent(), [&]() {
5845 RecursivelyDeleteTriviallyDeadInstructions(
5846 Repl, TLInfo, nullptr,
5847 [&](Value *V) { removeAllAssertingVHReferences(V); });
5871bool CodeGenPrepare::optimizeGatherScatterInst(
Instruction *MemoryInst,
5875 if (
const auto *
GEP = dyn_cast<GetElementPtrInst>(
Ptr)) {
5877 if (!
GEP->hasIndices())
5887 bool RewriteGEP =
false;
5889 if (Ops[0]->
getType()->isVectorTy()) {
5896 unsigned FinalIndex = Ops.size() - 1;
5901 for (
unsigned i = 1; i < FinalIndex; ++i) {
5902 auto *
C = dyn_cast<Constant>(Ops[i]);
5905 if (isa<VectorType>(
C->getType()))
5906 C =
C->getSplatValue();
5907 auto *CI = dyn_cast_or_null<ConstantInt>(
C);
5908 if (!CI || !CI->
isZero())
5915 if (Ops[FinalIndex]->
getType()->isVectorTy()) {
5917 auto *
C = dyn_cast<ConstantInt>(V);
5919 if (!
C || !
C->isZero()) {
5920 Ops[FinalIndex] =
V;
5928 if (!RewriteGEP && Ops.size() == 2)
5931 auto NumElts = cast<VectorType>(
Ptr->getType())->getElementCount();
5935 Type *SourceTy =
GEP->getSourceElementType();
5936 Type *ScalarIndexTy =
DL->getIndexType(Ops[0]->
getType()->getScalarType());
5940 if (!Ops[FinalIndex]->
getType()->isVectorTy()) {
5941 NewAddr = Builder.CreateGEP(SourceTy, Ops[0],
ArrayRef(Ops).drop_front());
5942 auto *IndexTy = VectorType::get(ScalarIndexTy, NumElts);
5944 SourceTy,
ArrayRef(Ops).drop_front());
5952 if (Ops.size() != 2) {
5958 SourceTy,
ArrayRef(Ops).drop_front());
5962 NewAddr = Builder.CreateGEP(SourceTy,
Base,
Index);
5964 }
else if (!isa<Constant>(
Ptr)) {
5971 auto NumElts = cast<VectorType>(
Ptr->getType())->getElementCount();
5976 Type *ScalarIndexTy =
DL->getIndexType(
V->getType()->getScalarType());
5977 auto *IndexTy = VectorType::get(ScalarIndexTy, NumElts);
5980 Intrinsic::masked_gather) {
5984 Intrinsic::masked_scatter);
5997 if (
Ptr->use_empty())
5999 Ptr, TLInfo,
nullptr,
6000 [&](
Value *V) { removeAllAssertingVHReferences(V); });
6007bool CodeGenPrepare::optimizeInlineAsmInst(
CallInst *CS) {
6008 bool MadeChange =
false;
6011 TM->getSubtargetImpl(*CS->
getFunction())->getRegisterInfo();
6021 OpInfo.isIndirect) {
6023 MadeChange |= optimizeMemoryInst(CS, OpVal, OpVal->
getType(), ~0u);
6036 bool IsSExt = isa<SExtInst>(FirstUser);
6040 if ((IsSExt && !isa<SExtInst>(UI)) || (!IsSExt && !isa<ZExtInst>(UI)))
6086bool CodeGenPrepare::tryToPromoteExts(
6089 unsigned CreatedInstsCost) {
6090 bool Promoted =
false;
6093 for (
auto *
I : Exts) {
6095 if (isa<LoadInst>(
I->getOperand(0))) {
6108 TypePromotionHelper::Action TPH =
6109 TypePromotionHelper::getAction(
I, InsertedInsts, *TLI, PromotedInsts);
6118 TypePromotionTransaction::ConstRestorationPt LastKnownGood =
6119 TPT.getRestorationPoint();
6121 unsigned NewCreatedInstsCost = 0;
6124 Value *PromotedVal = TPH(
I, TPT, PromotedInsts, NewCreatedInstsCost,
6125 &NewExts,
nullptr, *TLI);
6127 "TypePromotionHelper should have filtered out those cases");
6137 long long TotalCreatedInstsCost = CreatedInstsCost + NewCreatedInstsCost;
6140 TotalCreatedInstsCost =
6141 std::max((
long long)0, (TotalCreatedInstsCost - ExtCost));
6143 (TotalCreatedInstsCost > 1 ||
6145 (ExtCost == 0 && NewExts.
size() > 1))) {
6149 TPT.rollback(LastKnownGood);
6155 (void)tryToPromoteExts(TPT, NewExts, NewlyMovedExts, TotalCreatedInstsCost);
6156 bool NewPromoted =
false;
6157 for (
auto *ExtInst : NewlyMovedExts) {
6158 Instruction *MovedExt = cast<Instruction>(ExtInst);
6162 if (isa<LoadInst>(ExtOperand) &&
6167 ProfitablyMovedExts.
push_back(MovedExt);
6174 TPT.rollback(LastKnownGood);
6185bool CodeGenPrepare::mergeSExts(
Function &
F) {
6186 bool Changed =
false;
6187 for (
auto &Entry : ValToSExtendedUses) {
6188 SExts &Insts = Entry.second;
6191 if (RemovedInsts.count(Inst) || !isa<SExtInst>(Inst) ||
6194 bool inserted =
false;
6195 for (
auto &Pt : CurPts) {
6198 RemovedInsts.insert(Pt);
6199 Pt->removeFromParent();
6210 RemovedInsts.insert(Inst);
6217 CurPts.push_back(Inst);
6259bool CodeGenPrepare::splitLargeGEPOffsets() {
6260 bool Changed =
false;
6261 for (
auto &Entry : LargeOffsetGEPMap) {
6262 Value *OldBase = Entry.first;
6264 &LargeOffsetGEPs = Entry.second;
6265 auto compareGEPOffset =
6266 [&](
const std::pair<GetElementPtrInst *, int64_t> &
LHS,
6267 const std::pair<GetElementPtrInst *, int64_t> &
RHS) {
6268 if (
LHS.first ==
RHS.first)
6270 if (
LHS.second !=
RHS.second)
6271 return LHS.second <
RHS.second;
6272 return LargeOffsetGEPID[
LHS.first] < LargeOffsetGEPID[
RHS.first];
6275 llvm::sort(LargeOffsetGEPs, compareGEPOffset);
6276 LargeOffsetGEPs.
erase(
6277 std::unique(LargeOffsetGEPs.
begin(), LargeOffsetGEPs.
end()),
6278 LargeOffsetGEPs.
end());
6280 if (LargeOffsetGEPs.
front().second == LargeOffsetGEPs.
back().second)
6283 int64_t BaseOffset = LargeOffsetGEPs.
begin()->second;
6284 Value *NewBaseGEP =
nullptr;
6286 auto createNewBase = [&](int64_t BaseOffset,
Value *OldBase,
6289 Type *PtrIdxTy =
DL->getIndexType(
GEP->getType());
6291 PointerType::get(Ctx,
GEP->getType()->getPointerAddressSpace());
6295 if (
auto *BaseI = dyn_cast<Instruction>(OldBase)) {
6299 if (isa<PHINode>(BaseI))
6301 else if (
InvokeInst *Invoke = dyn_cast<InvokeInst>(BaseI)) {
6303 SplitEdge(NewBaseInsertBB, Invoke->getNormalDest(), DT.get(), LI);
6306 NewBaseInsertPt = std::next(BaseI->getIterator());
6313 IRBuilder<> NewBaseBuilder(NewBaseInsertBB, NewBaseInsertPt);
6315 Value *BaseIndex = ConstantInt::get(PtrIdxTy, BaseOffset);
6316 NewBaseGEP = OldBase;
6317 if (NewBaseGEP->
getType() != I8PtrTy)
6318 NewBaseGEP = NewBaseBuilder.CreatePointerCast(NewBaseGEP, I8PtrTy);
6320 NewBaseBuilder.CreatePtrAdd(NewBaseGEP, BaseIndex,
"splitgep");
6321 NewGEPBases.
insert(NewBaseGEP);
6327 LargeOffsetGEPs.
front().second, LargeOffsetGEPs.
back().second)) {
6328 BaseOffset = PreferBase;
6331 createNewBase(BaseOffset, OldBase, BaseGEP);
6334 auto *LargeOffsetGEP = LargeOffsetGEPs.
begin();
6335 while (LargeOffsetGEP != LargeOffsetGEPs.
end()) {
6337 int64_t
Offset = LargeOffsetGEP->second;
6338 if (
Offset != BaseOffset) {
6345 GEP->getResultElementType(),
6346 GEP->getAddressSpace())) {
6352 NewBaseGEP =
nullptr;
6357 Type *PtrIdxTy =
DL->getIndexType(
GEP->getType());
6362 createNewBase(BaseOffset, OldBase,
GEP);
6366 Value *NewGEP = NewBaseGEP;
6367 if (
Offset != BaseOffset) {
6370 NewGEP = Builder.CreatePtrAdd(NewBaseGEP,
Index);
6374 LargeOffsetGEP = LargeOffsetGEPs.
erase(LargeOffsetGEP);
6375 GEP->eraseFromParent();
6382bool CodeGenPrepare::optimizePhiType(
6389 Type *PhiTy =
I->getType();
6390 Type *ConvertTy =
nullptr;
6392 (!
I->getType()->isIntegerTy() && !
I->getType()->isFloatingPointTy()))
6408 bool AnyAnchored =
false;
6410 while (!Worklist.
empty()) {
6413 if (
auto *Phi = dyn_cast<PHINode>(II)) {
6415 for (
Value *V :
Phi->incoming_values()) {
6416 if (
auto *OpPhi = dyn_cast<PHINode>(V)) {
6417 if (!PhiNodes.
count(OpPhi)) {
6418 if (!Visited.
insert(OpPhi).second)
6423 }
else if (
auto *OpLoad = dyn_cast<LoadInst>(V)) {
6424 if (!OpLoad->isSimple())
6426 if (Defs.
insert(OpLoad).second)
6428 }
else if (
auto *OpEx = dyn_cast<ExtractElementInst>(V)) {
6429 if (Defs.
insert(OpEx).second)
6431 }
else if (
auto *OpBC = dyn_cast<BitCastInst>(V)) {
6433 ConvertTy = OpBC->getOperand(0)->getType();
6434 if (OpBC->getOperand(0)->getType() != ConvertTy)
6436 if (Defs.
insert(OpBC).second) {
6438 AnyAnchored |= !isa<LoadInst>(OpBC->getOperand(0)) &&
6439 !isa<ExtractElementInst>(OpBC->getOperand(0));
6441 }
else if (
auto *OpC = dyn_cast<ConstantData>(V))
6450 if (
auto *OpPhi = dyn_cast<PHINode>(V)) {
6451 if (!PhiNodes.
count(OpPhi)) {
6452 if (Visited.
count(OpPhi))
6458 }
else if (
auto *OpStore = dyn_cast<StoreInst>(V)) {
6459 if (!OpStore->isSimple() || OpStore->getOperand(0) != II)
6461 Uses.insert(OpStore);
6462 }
else if (
auto *OpBC = dyn_cast<BitCastInst>(V)) {
6464 ConvertTy = OpBC->getType();
6465 if (OpBC->getType() != ConvertTy)
6469 any_of(OpBC->users(), [](
User *U) { return !isa<StoreInst>(U); });
6476 if (!ConvertTy || !AnyAnchored ||
6480 LLVM_DEBUG(
dbgs() <<
"Converting " << *
I <<
"\n and connected nodes to "
6481 << *ConvertTy <<
"\n");
6489 if (isa<BitCastInst>(
D)) {
6490 ValMap[
D] =
D->getOperand(0);
6494 ValMap[
D] =
new BitCastInst(
D, ConvertTy,
D->getName() +
".bc", insertPt);
6499 Phi->getName() +
".tc",
Phi->getIterator());
6501 for (
PHINode *Phi : PhiNodes) {
6502 PHINode *NewPhi = cast<PHINode>(ValMap[Phi]);
6503 for (
int i = 0, e =
Phi->getNumIncomingValues(); i < e; i++)
6505 Phi->getIncomingBlock(i));
6510 if (isa<BitCastInst>(U)) {
6514 U->setOperand(0,
new BitCastInst(ValMap[
U->getOperand(0)], PhiTy,
"bc",
6521 DeletedInstrs.
insert(Phi);
6525bool CodeGenPrepare::optimizePhiTypes(
Function &
F) {
6529 bool Changed =
false;
6535 for (
auto &Phi : BB.
phis())
6536 Changed |= optimizePhiType(&Phi, Visited, DeletedInstrs);
6539 for (
auto *
I : DeletedInstrs) {
6541 I->eraseFromParent();
6549bool CodeGenPrepare::canFormExtLd(
6552 for (
auto *MovedExtInst : MovedExts) {
6553 if (isa<LoadInst>(MovedExtInst->getOperand(0))) {
6554 LI = cast<LoadInst>(MovedExtInst->getOperand(0));
6555 Inst = MovedExtInst;
6607bool CodeGenPrepare::optimizeExt(
Instruction *&Inst) {
6608 bool AllowPromotionWithoutCommonHeader =
false;
6613 *Inst, AllowPromotionWithoutCommonHeader);
6614 TypePromotionTransaction TPT(RemovedInsts);
6615 TypePromotionTransaction::ConstRestorationPt LastKnownGood =
6616 TPT.getRestorationPoint();
6621 bool HasPromoted = tryToPromoteExts(TPT, Exts, SpeculativelyMovedExts);
6629 if (canFormExtLd(SpeculativelyMovedExts, LI, ExtFedByLoad, HasPromoted)) {
6630 assert(LI && ExtFedByLoad &&
"Expect a valid load and extension");
6635 Inst = ExtFedByLoad;
6640 if (ATPConsiderable &&
6641 performAddressTypePromotion(Inst, AllowPromotionWithoutCommonHeader,
6642 HasPromoted, TPT, SpeculativelyMovedExts))
6645 TPT.rollback(LastKnownGood);
6654bool CodeGenPrepare::performAddressTypePromotion(
6655 Instruction *&Inst,
bool AllowPromotionWithoutCommonHeader,
6656 bool HasPromoted, TypePromotionTransaction &TPT,
6658 bool Promoted =
false;
6660 bool AllSeenFirst =
true;
6661 for (
auto *
I : SpeculativelyMovedExts) {
6662 Value *HeadOfChain =
I->getOperand(0);
6664 SeenChainsForSExt.
find(HeadOfChain);
6667 if (AlreadySeen != SeenChainsForSExt.
end()) {
6668 if (AlreadySeen->second !=
nullptr)
6669 UnhandledExts.
insert(AlreadySeen->second);
6670 AllSeenFirst =
false;
6674 if (!AllSeenFirst || (AllowPromotionWithoutCommonHeader &&
6675 SpeculativelyMovedExts.size() == 1)) {
6679 for (
auto *
I : SpeculativelyMovedExts) {
6680 Value *HeadOfChain =
I->getOperand(0);
6681 SeenChainsForSExt[HeadOfChain] =
nullptr;
6682 ValToSExtendedUses[HeadOfChain].push_back(
I);
6685 Inst = SpeculativelyMovedExts.pop_back_val();
6690 for (
auto *
I : SpeculativelyMovedExts) {
6691 Value *HeadOfChain =
I->getOperand(0);
6692 SeenChainsForSExt[HeadOfChain] = Inst;
6697 if (!AllSeenFirst && !UnhandledExts.
empty())
6698 for (
auto *VisitedSExt : UnhandledExts) {
6699 if (RemovedInsts.count(VisitedSExt))
6701 TypePromotionTransaction TPT(RemovedInsts);
6705 bool HasPromoted = tryToPromoteExts(TPT, Exts, Chains);
6709 for (
auto *
I : Chains) {
6710 Value *HeadOfChain =
I->getOperand(0);
6712 SeenChainsForSExt[HeadOfChain] =
nullptr;
6713 ValToSExtendedUses[HeadOfChain].push_back(
I);
6724 Value *Src =
I->getOperand(0);
6725 if (Src->hasOneUse())
6734 if (!isa<Instruction>(Src) || DefBB != cast<Instruction>(Src)->
getParent())
6737 bool DefIsLiveOut =
false;
6738 for (
User *U :
I->users()) {
6743 if (UserBB == DefBB)
6745 DefIsLiveOut =
true;
6752 for (
User *U : Src->users()) {
6755 if (UserBB == DefBB)
6759 if (isa<PHINode>(UI) || isa<LoadInst>(UI) || isa<StoreInst>(UI))
6766 bool MadeChange =
false;
6767 for (
Use &U : Src->uses()) {
6772 if (UserBB == DefBB)
6776 Instruction *&InsertedTrunc = InsertedTruncs[UserBB];
6778 if (!InsertedTrunc) {
6781 InsertedTrunc =
new TruncInst(
I, Src->getType(),
"");
6783 InsertedInsts.insert(InsertedTrunc);
6846bool CodeGenPrepare::optimizeLoadExt(
LoadInst *Load) {
6847 if (!
Load->isSimple() || !
Load->getType()->isIntOrPtrTy())
6851 if (
Load->hasOneUse() &&
6852 InsertedInsts.count(cast<Instruction>(*
Load->user_begin())))
6860 for (
auto *U :
Load->users())
6861 WorkList.
push_back(cast<Instruction>(U));
6872 while (!WorkList.
empty()) {
6876 if (!Visited.
insert(
I).second)
6880 if (
auto *Phi = dyn_cast<PHINode>(
I)) {
6881 for (
auto *U :
Phi->users())
6882 WorkList.
push_back(cast<Instruction>(U));
6886 switch (
I->getOpcode()) {
6887 case Instruction::And: {
6888 auto *AndC = dyn_cast<ConstantInt>(
I->getOperand(1));
6891 APInt AndBits = AndC->getValue();
6892 DemandBits |= AndBits;
6894 if (AndBits.
ugt(WidestAndBits))
6895 WidestAndBits = AndBits;
6896 if (AndBits == WidestAndBits &&
I->getOperand(0) == Load)
6901 case Instruction::Shl: {
6902 auto *ShlC = dyn_cast<ConstantInt>(
I->getOperand(1));
6906 DemandBits.setLowBits(
BitWidth - ShiftAmt);
6910 case Instruction::Trunc: {
6913 DemandBits.setLowBits(TruncBitWidth);
6922 uint32_t ActiveBits = DemandBits.getActiveBits();
6934 if (ActiveBits <= 1 || !DemandBits.isMask(ActiveBits) ||
6935 WidestAndBits != DemandBits)
6948 auto *NewAnd = cast<Instruction>(
6949 Builder.CreateAnd(Load, ConstantInt::get(Ctx, DemandBits)));
6952 InsertedInsts.insert(NewAnd);
6957 NewAnd->setOperand(0, Load);
6960 for (
auto *
And : AndsToMaybeRemove)
6963 if (cast<ConstantInt>(
And->getOperand(1))->getValue() == DemandBits) {
6965 if (&*CurInstIterator ==
And)
6966 CurInstIterator = std::next(
And->getIterator());
6967 And->eraseFromParent();
6978 auto *
I = dyn_cast<Instruction>(V);
7000 uint64_t Max = std::max(TrueWeight, FalseWeight);
7001 uint64_t Sum = TrueWeight + FalseWeight;
7009 CmpInst *Cmp = dyn_cast<CmpInst>(SI->getCondition());
7014 if (!Cmp || !Cmp->hasOneUse())
7035 for (
SelectInst *DefSI = SI; DefSI !=
nullptr && Selects.
count(DefSI);
7036 DefSI = dyn_cast<SelectInst>(V)) {
7037 assert(DefSI->getCondition() == SI->getCondition() &&
7038 "The condition of DefSI does not match with SI");
7039 V = (isTrue ? DefSI->getTrueValue() : DefSI->getFalseValue());
7042 assert(V &&
"Failed to get select true/false value");
7071 Value *NewTVal = Builder.CreateBinOp(Opcode, Shift->
getOperand(0), TVal);
7072 Value *NewFVal = Builder.CreateBinOp(Opcode, Shift->
getOperand(0), FVal);
7073 Value *NewSel = Builder.CreateSelect(
Cond, NewTVal, NewFVal);
7079bool CodeGenPrepare::optimizeFunnelShift(
IntrinsicInst *Fsh) {
7081 assert((Opcode == Intrinsic::fshl || Opcode == Intrinsic::fshr) &&
7082 "Expected a funnel shift");
7106 Value *NewTVal = Builder.CreateIntrinsic(Opcode, Ty, {
X,
Y, TVal});
7107 Value *NewFVal = Builder.CreateIntrinsic(Opcode, Ty, {
X,
Y, FVal});
7108 Value *NewSel = Builder.CreateSelect(
Cond, NewTVal, NewFVal);
7116bool CodeGenPrepare::optimizeSelectInst(
SelectInst *SI) {
7128 It !=
SI->getParent()->
end(); ++It) {
7130 if (
I &&
SI->getCondition() ==
I->getCondition()) {
7140 CurInstIterator = std::next(LastSI->
getIterator());
7145 fixupDbgVariableRecordsOnInst(*SI);
7147 bool VectorCond = !
SI->getCondition()->getType()->isIntegerTy(1);
7150 if (VectorCond ||
SI->getMetadata(LLVMContext::MD_unpredictable))
7154 if (
SI->getType()->isVectorTy())
7155 SelectKind = TargetLowering::ScalarCondVectorVal;
7157 SelectKind = TargetLowering::ScalarValSelect;
7200 TrueInstrs.
push_back(cast<Instruction>(V));
7202 FalseInstrs.
push_back(cast<Instruction>(V));
7210 SplitPt.setHeadBit(
true);
7213 auto *CondFr =
IB.CreateFreeze(
SI->getCondition(),
SI->getName() +
".frozen");
7220 if (TrueInstrs.
size() == 0) {
7222 CondFr, SplitPt,
false,
nullptr,
nullptr, LI));
7224 EndBlock = cast<BasicBlock>(FalseBranch->
getOperand(0));
7225 }
else if (FalseInstrs.
size() == 0) {
7227 CondFr, SplitPt,
false,
nullptr,
nullptr, LI));
7229 EndBlock = cast<BasicBlock>(TrueBranch->
getOperand(0));
7234 nullptr,
nullptr, LI);
7235 TrueBranch = cast<BranchInst>(ThenTerm);
7236 FalseBranch = cast<BranchInst>(ElseTerm);
7239 EndBlock = cast<BasicBlock>(TrueBranch->
getOperand(0));
7242 EndBlock->
setName(
"select.end");
7244 TrueBlock->
setName(
"select.true.sink");
7246 FalseBlock->
setName(FalseInstrs.
size() == 0 ?
"select.false"
7247 :
"select.false.sink");
7251 FreshBBs.
insert(TrueBlock);
7253 FreshBBs.
insert(FalseBlock);
7254 FreshBBs.
insert(EndBlock);
7257 BFI->setBlockFreq(EndBlock,
BFI->getBlockFreq(StartBlock));
7259 static const unsigned MD[] = {
7260 LLVMContext::MD_prof, LLVMContext::MD_unpredictable,
7261 LLVMContext::MD_make_implicit, LLVMContext::MD_dbg};
7267 I->moveBefore(TrueBranch);
7269 I->moveBefore(FalseBranch);
7275 if (TrueBlock ==
nullptr)
7276 TrueBlock = StartBlock;
7277 else if (FalseBlock ==
nullptr)
7278 FalseBlock = StartBlock;
7281 INS.
insert(ASI.begin(), ASI.end());
7295 SI->eraseFromParent();
7297 ++NumSelectsExpanded;
7301 CurInstIterator = StartBlock->
end();
7317 auto *SVIVecType = cast<FixedVectorType>(SVI->
getType());
7320 "Expected a type of the same size!");
7326 Builder.SetInsertPoint(SVI);
7327 Value *BC1 = Builder.CreateBitCast(
7328 cast<Instruction>(SVI->
getOperand(0))->getOperand(1), NewType);
7329 Value *Shuffle = Builder.CreateVectorSplat(NewVecType->getNumElements(), BC1);
7330 Value *BC2 = Builder.CreateBitCast(Shuffle, SVIVecType);
7334 SVI, TLInfo,
nullptr,
7335 [&](
Value *V) { removeAllAssertingVHReferences(V); });
7339 if (
auto *BCI = dyn_cast<Instruction>(BC1))
7340 if (
auto *
Op = dyn_cast<Instruction>(BCI->
getOperand(0)))
7341 if (BCI->
getParent() !=
Op->getParent() && !isa<PHINode>(
Op) &&
7342 !
Op->isTerminator() && !
Op->isEHPad())
7348bool CodeGenPrepare::tryToSinkFreeOperands(
Instruction *
I) {
7360 bool Changed =
false;
7364 unsigned long InstNumber = 0;
7365 for (
const auto &
I : *TargetBB)
7366 InstOrdering[&
I] = InstNumber++;
7369 auto *UI = cast<Instruction>(
U->get());
7370 if (isa<PHINode>(UI))
7373 if (InstOrdering[UI] < InstOrdering[InsertPoint])
7382 for (
Use *U : ToReplace) {
7383 auto *UI = cast<Instruction>(
U->get());
7390 auto *OpDef = dyn_cast<Instruction>(NI->
getOperand(
I));
7393 FreshBBs.
insert(OpDef->getParent());
7397 NewInstructions[UI] = NI;
7402 InsertedInsts.insert(NI);
7408 if (NewInstructions.
count(OldI))
7409 NewInstructions[OldI]->setOperand(
U->getOperandNo(), NI);
7416 for (
auto *
I : MaybeDead) {
7417 if (!
I->hasNUsesOrMore(1)) {
7419 I->eraseFromParent();
7426bool CodeGenPrepare::optimizeSwitchType(
SwitchInst *SI) {
7434 if (RegWidth <= cast<IntegerType>(OldType)->
getBitWidth())
7452 ExtType = Instruction::SExt;
7454 if (
auto *Arg = dyn_cast<Argument>(
Cond)) {
7455 if (Arg->hasSExtAttr())
7456 ExtType = Instruction::SExt;
7457 if (Arg->hasZExtAttr())
7458 ExtType = Instruction::ZExt;
7464 SI->setCondition(ExtInst);
7465 for (
auto Case :
SI->cases()) {
7466 const APInt &NarrowConst = Case.getCaseValue()->getValue();
7467 APInt WideConst = (ExtType == Instruction::ZExt)
7468 ? NarrowConst.
zext(RegWidth)
7469 : NarrowConst.
sext(RegWidth);
7470 Case.setValue(ConstantInt::get(Context, WideConst));
7476bool CodeGenPrepare::optimizeSwitchPhiConstants(
SwitchInst *SI) {
7483 Value *Condition =
SI->getCondition();
7485 if (isa<ConstantInt>(*Condition))
7488 bool Changed =
false;
7494 BasicBlock *CaseBB = Case.getCaseSuccessor();
7497 bool CheckedForSinglePred =
false;
7499 Type *PHIType =
PHI.getType();
7507 if (PHIType == ConditionType || TryZExt) {
7509 bool SkipCase =
false;
7510 Value *Replacement =
nullptr;
7511 for (
unsigned I = 0, E =
PHI.getNumIncomingValues();
I != E;
I++) {
7512 Value *PHIValue =
PHI.getIncomingValue(
I);
7513 if (PHIValue != CaseValue) {
7516 ConstantInt *PHIValueInt = dyn_cast<ConstantInt>(PHIValue);
7522 if (
PHI.getIncomingBlock(
I) != SwitchBB)
7527 if (!CheckedForSinglePred) {
7528 CheckedForSinglePred =
true;
7529 if (
SI->findCaseDest(CaseBB) ==
nullptr) {
7535 if (Replacement ==
nullptr) {
7536 if (PHIValue == CaseValue) {
7537 Replacement = Condition;
7540 Replacement = Builder.CreateZExt(Condition, PHIType);
7543 PHI.setIncomingValue(
I, Replacement);
7554bool CodeGenPrepare::optimizeSwitchInst(
SwitchInst *SI) {
7555 bool Changed = optimizeSwitchType(SI);
7556 Changed |= optimizeSwitchPhiConstants(SI);
7577class VectorPromoteHelper {
7594 unsigned StoreExtractCombineCost;
7603 if (InstsToBePromoted.
empty())
7605 return InstsToBePromoted.
back();
7611 unsigned getTransitionOriginalValueIdx()
const {
7612 assert(isa<ExtractElementInst>(Transition) &&
7613 "Other kind of transitions are not supported yet");
7620 unsigned getTransitionIdx()
const {
7621 assert(isa<ExtractElementInst>(Transition) &&
7622 "Other kind of transitions are not supported yet");
7630 Type *getTransitionType()
const {
7645 bool isProfitableToPromote() {
7646 Value *ValIdx = Transition->
getOperand(getTransitionOriginalValueIdx());
7647 unsigned Index = isa<ConstantInt>(ValIdx)
7648 ? cast<ConstantInt>(ValIdx)->getZExtValue()
7650 Type *PromotedType = getTransitionType();
7653 unsigned AS =
ST->getPointerAddressSpace();
7671 for (
const auto &Inst : InstsToBePromoted) {
7677 bool IsArg0Constant = isa<UndefValue>(Arg0) || isa<ConstantInt>(Arg0) ||
7678 isa<ConstantFP>(Arg0);
7691 dbgs() <<
"Estimated cost of computation to be promoted:\nScalar: "
7692 << ScalarCost <<
"\nVector: " << VectorCost <<
'\n');
7693 return ScalarCost > VectorCost;
7705 unsigned ExtractIdx = std::numeric_limits<unsigned>::max();
7710 if (
ConstantInt *CstVal = dyn_cast<ConstantInt>(ValExtractIdx))
7716 ElementCount EC = cast<VectorType>(getTransitionType())->getElementCount();
7720 if (!
EC.isScalable()) {
7723 for (
unsigned Idx = 0;
Idx !=
EC.getKnownMinValue(); ++
Idx) {
7724 if (
Idx == ExtractIdx)
7732 "Generate scalable vector for non-splat is unimplemented");
7738 unsigned OperandIdx) {
7741 if (OperandIdx != 1)
7743 switch (
Use->getOpcode()) {
7746 case Instruction::SDiv:
7747 case Instruction::UDiv:
7748 case Instruction::SRem:
7749 case Instruction::URem:
7751 case Instruction::FDiv:
7752 case Instruction::FRem:
7753 return !
Use->hasNoNaNs();
7761 unsigned CombineCost)
7762 :
DL(
DL), TLI(TLI),
TTI(
TTI), Transition(Transition),
7763 StoreExtractCombineCost(CombineCost) {
7764 assert(Transition &&
"Do not know how to promote null");
7768 bool canPromote(
const Instruction *ToBePromoted)
const {
7770 return isa<BinaryOperator>(ToBePromoted);
7775 bool shouldPromote(
const Instruction *ToBePromoted)
const {
7779 const Value *Val =
U.get();
7780 if (Val == getEndOfTransition()) {
7784 if (canCauseUndefinedBehavior(ToBePromoted,
U.getOperandNo()))
7788 if (!isa<ConstantInt>(Val) && !isa<UndefValue>(Val) &&
7789 !isa<ConstantFP>(Val))
7798 ISDOpcode, TLI.
getValueType(DL, getTransitionType(),
true));
7807 void enqueueForPromotion(
Instruction *ToBePromoted) {
7808 InstsToBePromoted.push_back(ToBePromoted);
7812 void recordCombineInstruction(
Instruction *ToBeCombined) {
7814 CombineInst = ToBeCombined;
7824 if (InstsToBePromoted.empty() || !CombineInst)
7832 for (
auto &ToBePromoted : InstsToBePromoted)
7833 promoteImpl(ToBePromoted);
7834 InstsToBePromoted.clear();
7841void VectorPromoteHelper::promoteImpl(
Instruction *ToBePromoted) {
7851 "The type of the result of the transition does not match "
7856 Type *TransitionTy = getTransitionType();
7863 Value *NewVal =
nullptr;
7864 if (Val == Transition)
7865 NewVal = Transition->
getOperand(getTransitionOriginalValueIdx());
7866 else if (isa<UndefValue>(Val) || isa<ConstantInt>(Val) ||
7867 isa<ConstantFP>(Val)) {
7870 cast<Constant>(Val),
7871 isa<UndefValue>(Val) ||
7872 canCauseUndefinedBehavior(ToBePromoted,
U.getOperandNo()));
7876 ToBePromoted->
setOperand(
U.getOperandNo(), NewVal);
7879 Transition->
setOperand(getTransitionOriginalValueIdx(), ToBePromoted);
7885bool CodeGenPrepare::optimizeExtractElementInst(
Instruction *Inst) {
7886 unsigned CombineCost = std::numeric_limits<unsigned>::max();
7901 LLVM_DEBUG(
dbgs() <<
"Found an interesting transition: " << *Inst <<
'\n');
7902 VectorPromoteHelper VPH(*
DL, *TLI, *
TTI, Inst, CombineCost);
7909 if (ToBePromoted->
getParent() != Parent) {
7910 LLVM_DEBUG(
dbgs() <<
"Instruction to promote is in a different block ("
7912 <<
") than the transition (" << Parent->
getName()
7917 if (VPH.canCombine(ToBePromoted)) {
7919 <<
"will be combined with: " << *ToBePromoted <<
'\n');
7920 VPH.recordCombineInstruction(ToBePromoted);
7921 bool Changed = VPH.promote();
7922 NumStoreExtractExposed += Changed;
7927 if (!VPH.canPromote(ToBePromoted) || !VPH.shouldPromote(ToBePromoted))
7930 LLVM_DEBUG(
dbgs() <<
"Promoting is possible... Enqueue for promotion!\n");
7932 VPH.enqueueForPromotion(ToBePromoted);
7933 Inst = ToBePromoted;
7973 Type *StoreType = SI.getValueOperand()->getType();
7982 if (!
DL.typeSizeEqualsStoreSize(StoreType) ||
7983 DL.getTypeSizeInBits(StoreType) == 0)
7986 unsigned HalfValBitSize =
DL.getTypeSizeInBits(StoreType) / 2;
7988 if (!
DL.typeSizeEqualsStoreSize(SplitStoreType))
7992 if (SI.isVolatile())
8004 if (!
match(SI.getValueOperand(),
8011 if (!
LValue->getType()->isIntegerTy() ||
8012 DL.getTypeSizeInBits(
LValue->getType()) > HalfValBitSize ||
8014 DL.getTypeSizeInBits(HValue->
getType()) > HalfValBitSize)
8019 auto *LBC = dyn_cast<BitCastInst>(
LValue);
8020 auto *HBC = dyn_cast<BitCastInst>(HValue);
8034 if (LBC && LBC->getParent() != SI.getParent())
8036 if (HBC && HBC->getParent() != SI.getParent())
8037 HValue = Builder.
CreateBitCast(HBC->getOperand(0), HBC->getType());
8039 bool IsLE = SI.getModule()->getDataLayout().isLittleEndian();
8040 auto CreateSplitStore = [&](
Value *V,
bool Upper) {
8043 Align Alignment = SI.getAlign();
8044 const bool IsOffsetStore = (IsLE &&
Upper) || (!IsLE && !
Upper);
8045 if (IsOffsetStore) {
8047 SplitStoreType,
Addr,
8058 CreateSplitStore(
LValue,
false);
8059 CreateSplitStore(HValue,
true);
8062 SI.eraseFromParent();
8070 return GEP->getNumOperands() == 2 &&
I.isSequential() &&
8071 isa<ConstantInt>(
GEP->getOperand(1));
8149 if (!isa<Instruction>(GEPIOp))
8151 auto *GEPIOpI = cast<Instruction>(GEPIOp);
8152 if (GEPIOpI->getParent() != SrcBlock)
8157 if (auto *I = dyn_cast<Instruction>(Usr)) {
8158 if (I->getParent() != SrcBlock) {
8166 std::vector<GetElementPtrInst *> UGEPIs;
8173 if (!isa<Instruction>(Usr))
8175 auto *UI = cast<Instruction>(Usr);
8180 if (!isa<GetElementPtrInst>(Usr))
8182 auto *UGEPI = cast<GetElementPtrInst>(Usr);
8188 if (UGEPI->getOperand(0) != GEPIOp)
8190 if (UGEPI->getSourceElementType() != GEPI->getSourceElementType())
8192 if (GEPIIdx->getType() !=
8193 cast<ConstantInt>(UGEPI->getOperand(1))->getType())
8195 ConstantInt *UGEPIIdx = cast<ConstantInt>(UGEPI->getOperand(1));
8200 UGEPIs.push_back(UGEPI);
8202 if (UGEPIs.size() == 0)
8206 ConstantInt *UGEPIIdx = cast<ConstantInt>(UGEPI->getOperand(1));
8215 UGEPI->setOperand(0, GEPI);
8216 ConstantInt *UGEPIIdx = cast<ConstantInt>(UGEPI->getOperand(1));
8217 Constant *NewUGEPIIdx = ConstantInt::get(
8218 GEPIIdx->getType(), UGEPIIdx->
getValue() - GEPIIdx->getValue());
8219 UGEPI->setOperand(1, NewUGEPIIdx);
8222 if (!GEPI->isInBounds()) {
8223 UGEPI->setIsInBounds(
false);
8230 return cast<Instruction>(Usr)->getParent() != SrcBlock;
8232 "GEPIOp is used outside SrcBlock");
8252 ICmpInst *Cmp = dyn_cast<ICmpInst>(Branch->getCondition());
8253 if (!Cmp || !isa<ConstantInt>(Cmp->getOperand(1)) || !Cmp->hasOneUse())
8256 Value *
X = Cmp->getOperand(0);
8257 APInt CmpC = cast<ConstantInt>(Cmp->getOperand(1))->getValue();
8259 for (
auto *U :
X->users()) {
8263 (UI->
getParent() != Branch->getParent() &&
8264 UI->
getParent() != Branch->getSuccessor(0) &&
8265 UI->
getParent() != Branch->getSuccessor(1)) ||
8266 (UI->
getParent() != Branch->getParent() &&
8270 if (CmpC.
isPowerOf2() && Cmp->getPredicate() == ICmpInst::ICMP_ULT &&
8273 if (UI->
getParent() != Branch->getParent())
8276 ConstantInt::get(UI->
getType(), 0));
8278 LLVM_DEBUG(
dbgs() <<
" to compare on zero: " << *NewCmp <<
"\n");
8282 if (Cmp->isEquality() &&
8286 if (UI->
getParent() != Branch->getParent())
8289 ConstantInt::get(UI->
getType(), 0));
8291 LLVM_DEBUG(
dbgs() <<
" to compare on zero: " << *NewCmp <<
"\n");
8299bool CodeGenPrepare::optimizeInst(
Instruction *
I, ModifyDT &ModifiedDT) {
8300 bool AnyChange =
false;
8301 AnyChange = fixupDbgVariableRecordsOnInst(*
I);
8305 if (InsertedInsts.count(
I))
8309 if (
PHINode *
P = dyn_cast<PHINode>(
I)) {
8314 LargeOffsetGEPMap.erase(
P);
8316 P->eraseFromParent();
8323 if (
CastInst *CI = dyn_cast<CastInst>(
I)) {
8336 if ((isa<UIToFPInst>(
I) || isa<FPToUIInst>(
I) || isa<TruncInst>(
I)) &&
8338 I, LI->getLoopFor(
I->getParent()), *
TTI))
8341 if (isa<ZExtInst>(
I) || isa<SExtInst>(
I)) {
8346 TargetLowering::TypeExpandInteger) {
8350 I, LI->getLoopFor(
I->getParent()), *
TTI))
8353 bool MadeChange = optimizeExt(
I);
8354 return MadeChange | optimizeExtUses(
I);
8360 if (
auto *Cmp = dyn_cast<CmpInst>(
I))
8361 if (optimizeCmp(Cmp, ModifiedDT))
8364 if (
LoadInst *LI = dyn_cast<LoadInst>(
I)) {
8365 LI->
setMetadata(LLVMContext::MD_invariant_group,
nullptr);
8366 bool Modified = optimizeLoadExt(LI);
8372 if (
StoreInst *SI = dyn_cast<StoreInst>(
I)) {
8375 SI->setMetadata(LLVMContext::MD_invariant_group,
nullptr);
8376 unsigned AS =
SI->getPointerAddressSpace();
8377 return optimizeMemoryInst(
I,
SI->getOperand(1),
8378 SI->getOperand(0)->getType(), AS);
8382 unsigned AS = RMW->getPointerAddressSpace();
8383 return optimizeMemoryInst(
I, RMW->getPointerOperand(), RMW->getType(), AS);
8387 unsigned AS = CmpX->getPointerAddressSpace();
8388 return optimizeMemoryInst(
I, CmpX->getPointerOperand(),
8389 CmpX->getCompareOperand()->getType(), AS);
8399 if (BinOp && (BinOp->
getOpcode() == Instruction::AShr ||
8400 BinOp->
getOpcode() == Instruction::LShr)) {
8408 if (GEPI->hasAllZeroIndices()) {
8411 GEPI->getName(), GEPI->getIterator());
8412 NC->setDebugLoc(GEPI->getDebugLoc());
8415 GEPI, TLInfo,
nullptr,
8416 [&](
Value *V) { removeAllAssertingVHReferences(V); });
8418 optimizeInst(
NC, ModifiedDT);
8430 if (
ICmpInst *II = dyn_cast<ICmpInst>(FI->getOperand(0)))
8432 else if (
FCmpInst *
F = dyn_cast<FCmpInst>(FI->getOperand(0)))
8433 CmpI =
F->getFastMathFlags().none() ?
F :
nullptr;
8437 bool Const0 = isa<ConstantInt>(Op0) || isa<ConstantFP>(Op0) ||
8438 isa<ConstantPointerNull>(Op0);
8439 bool Const1 = isa<ConstantInt>(Op1) || isa<ConstantFP>(Op1) ||
8440 isa<ConstantPointerNull>(Op1);
8441 if (Const0 || Const1) {
8442 if (!Const0 || !Const1) {
8448 FI->eraseFromParent();
8455 if (tryToSinkFreeOperands(
I))
8458 switch (
I->getOpcode()) {
8459 case Instruction::Shl:
8460 case Instruction::LShr:
8461 case Instruction::AShr:
8462 return optimizeShiftInst(cast<BinaryOperator>(
I));
8463 case Instruction::Call:
8465 case Instruction::Select:
8466 return optimizeSelectInst(cast<SelectInst>(
I));
8467 case Instruction::ShuffleVector:
8468 return optimizeShuffleVectorInst(cast<ShuffleVectorInst>(
I));
8469 case Instruction::Switch:
8470 return optimizeSwitchInst(cast<SwitchInst>(
I));
8471 case Instruction::ExtractElement:
8472 return optimizeExtractElementInst(cast<ExtractElementInst>(
I));
8473 case Instruction::Br:
8474 return optimizeBranch(cast<BranchInst>(
I), *TLI, FreshBBs, IsHugeFunc);
8483 if (!
I.getType()->isIntegerTy() ||
8494 &
I, TLInfo,
nullptr,
8495 [&](
Value *V) { removeAllAssertingVHReferences(V); });
8502bool CodeGenPrepare::optimizeBlock(
BasicBlock &BB, ModifyDT &ModifiedDT) {
8504 bool MadeChange =
false;
8507 CurInstIterator = BB.
begin();
8508 ModifiedDT = ModifyDT::NotModifyDT;
8509 while (CurInstIterator != BB.
end()) {
8510 MadeChange |= optimizeInst(&*CurInstIterator++, ModifiedDT);
8511 if (ModifiedDT != ModifyDT::NotModifyDT) {
8524 }
while (ModifiedDT == ModifyDT::ModifyInstDT);
8526 bool MadeBitReverse =
true;
8527 while (MadeBitReverse) {
8528 MadeBitReverse =
false;
8530 if (makeBitReverse(
I)) {
8531 MadeBitReverse = MadeChange =
true;
8536 MadeChange |= dupRetToEnableTailCallOpts(&BB, ModifiedDT);
8548 bool AnyChange =
false;
8551 for (
Value *Location : LocationOps) {
8567bool CodeGenPrepare::fixupDbgVariableRecordsOnInst(
Instruction &
I) {
8568 bool AnyChange =
false;
8570 AnyChange |= fixupDbgVariableRecord(DVR);
8577 if (DVR.
Type != DbgVariableRecord::LocationType::Value &&
8578 DVR.
Type != DbgVariableRecord::LocationType::Assign)
8582 bool AnyChange =
false;
8585 for (
Value *Location : LocationOps) {
8603 if (isa<PHINode>(VI))
8604 DVI->
insertBefore(&*VI->getParent()->getFirstInsertionPt());
8612 if (isa<PHINode>(VI))
8623bool CodeGenPrepare::placeDbgValues(
Function &
F) {
8624 bool MadeChange =
false;
8627 auto DbgProcessor = [&](
auto *DbgItem,
Instruction *Position) {
8629 for (
Value *V : DbgItem->location_ops())
8630 if (
Instruction *VI = dyn_cast_or_null<Instruction>(V))
8638 if (
VI->isTerminator())
8643 if (isa<PHINode>(VI) &&
VI->getParent()->getTerminator()->isEHPad())
8654 if (VIs.size() > 1) {
8657 <<
"Unable to find valid location for Debug Value, undefing:\n"
8659 DbgItem->setKillLocation();
8664 << *DbgItem <<
' ' << *VI);
8676 DbgProcessor(DVI, DVI);
8684 if (DVR.
Type != DbgVariableRecord::LocationType::Value)
8686 DbgProcessor(&DVR, &
Insn);
8697bool CodeGenPrepare::placePseudoProbes(
Function &
F) {
8698 bool MadeChange =
false;
8701 auto FirstInst =
Block.getFirstInsertionPt();
8702 while (FirstInst !=
Block.end() && FirstInst->isDebugOrPseudoInst())
8706 while (
I !=
Block.end()) {
8707 if (
auto *II = dyn_cast<PseudoProbeInst>(
I++)) {
8718 uint64_t NewMax = (NewTrue > NewFalse) ? NewTrue : NewFalse;
8719 uint32_t Scale = (NewMax / std::numeric_limits<uint32_t>::max()) + 1;
8720 NewTrue = NewTrue / Scale;
8721 NewFalse = NewFalse / Scale;
8746bool CodeGenPrepare::splitBranchCondition(
Function &
F, ModifyDT &ModifiedDT) {
8750 bool MadeChange =
false;
8751 for (
auto &BB :
F) {
8764 if (Br1->getMetadata(LLVMContext::MD_unpredictable))
8772 Value *Cond1, *Cond2;
8775 Opc = Instruction::And;
8778 Opc = Instruction::Or;
8788 if (!IsGoodCond(Cond1) || !IsGoodCond(Cond2))
8802 Br1->setCondition(Cond1);
8807 if (Opc == Instruction::And)
8808 Br1->setSuccessor(0, TmpBB);
8810 Br1->setSuccessor(1, TmpBB);
8814 if (
auto *
I = dyn_cast<Instruction>(Cond2)) {
8815 I->removeFromParent();
8816 I->insertBefore(Br2);
8828 if (Opc == Instruction::Or)
8842 if (Opc == Instruction::Or) {
8864 uint64_t NewTrueWeight = TrueWeight;
8865 uint64_t NewFalseWeight = TrueWeight + 2 * FalseWeight;
8867 Br1->setMetadata(LLVMContext::MD_prof,
8871 NewTrueWeight = TrueWeight;
8872 NewFalseWeight = 2 * FalseWeight;
8874 Br2->setMetadata(LLVMContext::MD_prof,
8899 uint64_t NewTrueWeight = 2 * TrueWeight + FalseWeight;
8900 uint64_t NewFalseWeight = FalseWeight;
8902 Br1->setMetadata(LLVMContext::MD_prof,
8906 NewTrueWeight = 2 * TrueWeight;
8907 NewFalseWeight = FalseWeight;
8909 Br2->setMetadata(LLVMContext::MD_prof,
8915 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
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
amdgpu AMDGPU Register Bank Select
This file implements a class to represent arbitrary precision integral constant values and operations...
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 void computeBaseDerivedRelocateMap(const SmallVectorImpl< GCRelocateInst * > &AllRelocateCalls, DenseMap< GCRelocateInst *, SmallVector< GCRelocateInst *, 2 > > &RelocateInstMap)
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 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."))
bool matchIncrement(const Instruction *IVInc, Instruction *&LHS, Constant *&Step)
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 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 cl::opt< bool > EnableGEPOffsetSplit("cgp-split-large-offset-gep", cl::Hidden, cl::init(true), cl::desc("Enable splitting large offset of GEP."))
static cl::opt< bool > DisableComplexAddrModes("disable-complex-addr-modes", cl::Hidden, cl::init(false), cl::desc("Disables combining addressing modes with different parts " "in optimizeMemoryInst."))
static cl::opt< bool > EnableICMP_EQToICMP_ST("cgp-icmp-eq2icmp-st", cl::Hidden, cl::init(false), cl::desc("Enable ICMP_EQ to ICMP_S(L|G)T conversion."))
static cl::opt< bool > VerifyBFIUpdates("cgp-verify-bfi-updates", cl::Hidden, cl::init(false), cl::desc("Enable BFI update verification for " "CodeGenPrepare."))
static cl::opt< bool > BBSectionsGuidedSectionPrefix("bbsections-guided-section-prefix", cl::Hidden, cl::init(true), cl::desc("Use the basic-block-sections profile to determine the text " "section prefix for hot functions. Functions with " "basic-block-sections profile will be placed in `.text.hot` " "regardless of their FDO profile info. Other functions won't be " "impacted, i.e., their prefixes will be decided by FDO/sampleFDO " "profiles."))
static bool isIVIncrement(const Value *V, const LoopInfo *LI)
static cl::opt< bool > DisableGCOpts("disable-cgp-gc-opts", cl::Hidden, cl::init(false), cl::desc("Disable GC optimizations in CodeGenPrepare"))
static bool GEPSequentialConstIndexed(GetElementPtrInst *GEP)
static bool isPromotedInstructionLegal(const TargetLowering &TLI, const DataLayout &DL, Value *Val)
Check whether or not Val is a legal instruction for TLI.
static cl::opt< uint64_t > FreqRatioToSkipMerge("cgp-freq-ratio-to-skip-merge", cl::Hidden, cl::init(2), cl::desc("Skip merging empty blocks if (frequency of empty block) / " "(frequency of destination block) is greater than this ratio"))
static bool optimizeBranch(BranchInst *Branch, const TargetLowering &TLI, SmallSet< BasicBlock *, 32 > &FreshBBs, bool IsHugeFunc)
static bool IsNonLocalValue(Value *V, BasicBlock *BB)
Return true if the specified values are defined in a different basic block than BB.
static bool despeculateCountZeros(IntrinsicInst *CountZeros, LoopInfo &LI, const TargetLowering *TLI, const DataLayout *DL, ModifyDT &ModifiedDT, SmallSet< BasicBlock *, 32 > &FreshBBs, bool IsHugeFunc)
If counting leading or trailing zeros is an expensive operation and a zero input is defined,...
static bool hasSameExtUse(Value *Val, const TargetLowering &TLI)
Check if all the uses of Val are equivalent (or free) zero or sign extensions.
static cl::opt< bool > StressExtLdPromotion("stress-cgp-ext-ld-promotion", cl::Hidden, cl::init(false), cl::desc("Stress test ext(promotable(ld)) -> promoted(ext(ld)) " "optimization in CodeGenPrepare"))
static bool matchUAddWithOverflowConstantEdgeCases(CmpInst *Cmp, BinaryOperator *&Add)
Match special-case patterns that check for unsigned add overflow.
static cl::opt< bool > DisableSelectToBranch("disable-cgp-select2branch", cl::Hidden, cl::init(false), cl::desc("Disable select to branch conversion."))
static cl::opt< bool > DisableDeletePHIs("disable-cgp-delete-phis", cl::Hidden, cl::init(false), cl::desc("Disable elimination of dead PHI nodes."))
static cl::opt< bool > AddrSinkNewPhis("addr-sink-new-phis", cl::Hidden, cl::init(false), cl::desc("Allow creation of Phis in Address sinking."))
Defines an IR pass for CodeGen Prepare.
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
#define LLVM_ATTRIBUTE_UNUSED
This file contains the declarations for the subclasses of Constant, which represent the different fla...
static void clear(coro::Shape &Shape)
static cl::opt< TargetTransformInfo::TargetCostKind > CostKind("cost-kind", cl::desc("Target cost kind"), cl::init(TargetTransformInfo::TCK_RecipThroughput), cl::values(clEnumValN(TargetTransformInfo::TCK_RecipThroughput, "throughput", "Reciprocal throughput"), clEnumValN(TargetTransformInfo::TCK_Latency, "latency", "Instruction latency"), clEnumValN(TargetTransformInfo::TCK_CodeSize, "code-size", "Code size"), clEnumValN(TargetTransformInfo::TCK_SizeAndLatency, "size-latency", "Code size and latency")))
Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx
This file defines the DenseMap class.
DenseMap< Block *, BlockRelaxAux > Blocks
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
Rewrite Partial Register Uses
static void eraseInstruction(Instruction &I, ICFLoopSafetyInfo &SafetyInfo, MemorySSAUpdater &MSSAU)
unsigned const TargetRegisterInfo * TRI
This file implements a map that provides insertion order iteration.
Module.h This file contains the declarations for the Module class.
static GCMetadataPrinterRegistry::Add< OcamlGCMetadataPrinter > Y("ocaml", "ocaml 3.10-compatible collector")
const char LLVMTargetMachineRef TM
#define INITIALIZE_PASS_DEPENDENCY(depName)
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
This file defines the PointerIntPair class.
This file contains the declarations for profiling metadata utility functions.
const SmallVectorImpl< MachineOperand > MachineBasicBlock * TBB
const SmallVectorImpl< MachineOperand > & Cond
static bool dominates(InstrPosIndexes &PosIndexes, const MachineInstr &A, const MachineInstr &B)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
static bool optimizeCallInst(CallInst *CI, bool &ModifiedDT, const TargetTransformInfo &TTI, const DataLayout &DL, DomTreeUpdater *DTU)
static bool optimizeBlock(BasicBlock &BB, bool &ModifiedDT, const TargetTransformInfo &TTI, const DataLayout &DL, DomTreeUpdater *DTU)
This file defines the SmallPtrSet class.
This file defines the SmallVector class.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
static SymbolRef::Type getType(const Symbol *Sym)
This file describes how to lower LLVM code to machine code.
static cl::opt< bool > DisableSelectOptimize("disable-select-optimize", cl::init(true), cl::Hidden, cl::desc("Disable the select-optimization pass from running"))
Disable the select optimization pass.
Target-Independent Code Generator Pass Configuration Options pass.
This defines the Use class.
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...
void reinsertInstInDbgRecords(Instruction *I, std::optional< DbgRecord::self_iterator > Pos)
In rare circumstances instructions can be speculatively removed from blocks, and then be re-inserted ...
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...
static BinaryOperator * Create(BinaryOps Op, Value *S1, Value *S2, const Twine &Name, BasicBlock::iterator InsertBefore)
Construct a binary instruction, given the opcode and the two operands.
BinaryOps getOpcode() const
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.
Instruction::CastOps getOpcode() const
Return the opcode of this CastInst.
static CastInst * Create(Instruction::CastOps, Value *S, Type *Ty, const Twine &Name, BasicBlock::iterator InsertBefore)
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, BasicBlock::iterator InsertBefore)
Construct a compare instruction, given the opcode, the predicate and the two operands.
Predicate getPredicate() const
Return the predicate for this instruction.
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Base class for constants with no operands.
A constant value that is initialized with an expression using other constant values.
static Constant * getBitCast(Constant *C, Type *Ty, bool OnlyIfReduced=false)
static Constant * getNeg(Constant *C, bool HasNSW=false)
This is the shared class of boolean and integer constants.
static ConstantInt * getTrue(LLVMContext &Context)
bool isZero() const
This is just a convenience method to make client code smaller for a common code.
int64_t getSExtValue() const
Return the constant as a 64-bit integer value after it has been sign extended as appropriate for the ...
const APInt & getValue() const
Return the constant as an APInt value reference.
static Constant * getSplat(ElementCount EC, Constant *Elt)
Return a ConstantVector with the specified constant in each element.
static Constant * get(ArrayRef< Constant * > V)
This is an important base class in LLVM.
static Constant * 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)
Record of a variable value-assignment, aka a non instruction representation of the dbg....
LocationType Type
Classification of the debug-info record that this DbgVariableRecord represents.
void replaceVariableLocationOp(Value *OldValue, Value *NewValue, bool AllowEmpty=false)
iterator_range< location_op_iterator > location_ops() const
Get the locations corresponding to the variable referenced by the debug info intrinsic.
iterator find(const_arg_type_t< KeyT > Val)
bool erase(const KeyT &Val)
size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
bool isReachableFromEntry(const Use &U) const
Provide an overload for a Use.
bool dominates(const BasicBlock *BB, const Use &U) const
Return true if the (end of the) basic block BB dominates the use U.
This instruction compares its operands according to the predicate given to the constructor.
static FixedVectorType * get(Type *ElementType, unsigned NumElts)
This class implements simplifications for calls to fortified library functions (__st*cpy_chk,...
This class represents a freeze function that returns random concrete value if an operand is either a ...
FunctionPass class - This class is used to implement most global optimizations.
virtual bool runOnFunction(Function &F)=0
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass.
const BasicBlock & getEntryBlock() const
const Value * getStatepoint() const
The statepoint with which this gc.relocate is associated.
Represents calls to the gc.relocate intrinsic.
unsigned getBasePtrIndex() const
The index into the associate statepoint's argument list which contains the base pointer of the pointe...
Represents a gc.statepoint intrinsic call.
an instruction for type-safe pointer arithmetic to access elements of arrays and structs
static Type * getIndexedType(Type *Ty, ArrayRef< Value * > IdxList)
Returns the result type of a getelementptr with the given source element type and indexes.
void setAlignment(Align Align)
Sets the alignment attribute of the GlobalObject.
bool canIncreaseAlignment() const
Returns true if the alignment of the value can be unilaterally increased.
bool isThreadLocal() const
If the value is "Thread Local", its value isn't shared by the threads.
Type * getValueType() const
This instruction compares its operands according to the predicate given to the constructor.
Value * CreateZExtOrBitCast(Value *V, Type *DestTy, const Twine &Name="")
ConstantInt * getTrue()
Get the constant value for i1 true.
Value * CreateFreeze(Value *V, const Twine &Name="")
void SetCurrentDebugLocation(DebugLoc L)
Set location information used by debugging information.
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 * CreateGEP(Type *Ty, Value *Ptr, ArrayRef< Value * > IdxList, const Twine &Name="", bool IsInBounds=false)
ConstantInt * getInt(const APInt &AI)
Get a constant integer value.
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Instruction * clone() const
Create a copy of 'this' instruction that is identical in all ways except the following:
void removeFromParent()
This method unlinks 'this' from the containing basic block, but does not delete it.
void insertBefore(Instruction *InsertPos)
Insert an unlinked instruction into a basic block immediately before the specified instruction.
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
const Instruction * getPrevNonDebugInstruction(bool SkipPseudoOp=false) const
Return a pointer to the previous non-debug instruction in the same basic block as 'this',...
void moveAfter(Instruction *MovePos)
Unlink this instruction from its current basic block and insert it into the basic block that MovePos ...
bool isEHPad() const
Return true if the instruction is a variety of EH-block.
const BasicBlock * getParent() const
InstListType::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
Instruction * user_back()
Specialize the methods defined in Value, as we know that an instruction can only be used by other ins...
const Function * getFunction() const
Return the function this instruction belongs to.
void setMetadata(unsigned KindID, MDNode *Node)
Set the metadata of the specified kind to the specified node.
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
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)
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)
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()
static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr, BasicBlock::iterator InsertBefore)
Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...
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 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, BasicBlock::iterator InsertBefore, 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)
erase - If the set contains the specified pointer, remove it and return true, otherwise return false.
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
A SetVector that performs no allocations if smaller than a certain size.
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
size_type count(const T &V) const
count - Return 1 if the element is in the set, 0 otherwise.
bool contains(const T &V) const
Check if the SmallSet contains the given element.
std::pair< const_iterator, bool > insert(const T &V)
insert - Insert an element into the set if it isn't already there.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
reference emplace_back(ArgTypes &&... Args)
void reserve(size_type N)
iterator erase(const_iterator CI)
typename SuperClass::iterator iterator
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
An instruction for storing to memory.
static unsigned getPointerOperandIndex()
StringRef - Represent a constant reference to a string, i.e.
Used to lazily calculate structure layout information for a target machine, based on the DataLayout s...
TypeSize getElementOffset(unsigned Idx) const
Class to represent struct types.
Analysis pass providing the TargetTransformInfo.
Analysis pass providing the TargetLibraryInfo.
Provides information about what library functions are available for the current target.
bool getLibFunc(StringRef funcName, LibFunc &F) const
Searches for a particular function name.
int InstructionOpcodeToISD(unsigned Opcode) const
Get the ISD node that corresponds to the Instruction class opcode.
virtual bool isVectorShiftByScalarCheap(Type *Ty) const
Return true if it's significantly cheaper to shift a vector by a uniform scalar than by an amount whi...
EVT getValueType(const DataLayout &DL, Type *Ty, bool AllowUnknown=false) const
Return the EVT corresponding to this LLVM type.
virtual bool isSelectSupported(SelectSupportKind) const
virtual bool isEqualityCmpFoldedWithSignedCmp() const
Return true if instruction generated for equality comparison is folded with instruction generated for...
virtual bool shouldFormOverflowOp(unsigned Opcode, EVT VT, bool MathUsed) const
Try to convert math with an overflow comparison into the corresponding DAG node operation.
virtual bool isMaskAndCmp0FoldingBeneficial(const Instruction &AndI) const
Return if the target supports combining a chain like:
bool isExtLoad(const LoadInst *Load, const Instruction *Ext, const DataLayout &DL) const
Return true if Load and Ext can form an ExtLoad.
virtual bool isSExtCheaperThanZExt(EVT FromTy, EVT ToTy) const
Return true if sign-extension from FromTy to ToTy is cheaper than zero-extension.
const TargetMachine & getTargetMachine() const
virtual bool isZExtFree(Type *FromTy, Type *ToTy) const
Return true if any actual instruction that defines a value of type FromTy implicitly zero-extends the...
bool enableExtLdPromotion() const
Return true if the target wants to use the optimization that turns ext(promotableInst1(....
virtual bool isCheapToSpeculateCttz(Type *Ty) const
Return true if it is cheap to speculate a call to intrinsic cttz.
bool isJumpExpensive() const
Return true if Flow Control is an expensive operation that should be avoided.
bool hasExtractBitsInsn() const
Return true if the target has BitExtract instructions.
SelectSupportKind
Enum that describes what type of support for selects the target has.
virtual bool allowsMisalignedMemoryAccesses(EVT, unsigned AddrSpace=0, Align Alignment=Align(1), MachineMemOperand::Flags Flags=MachineMemOperand::MONone, unsigned *=nullptr) const
Determine if the target supports unaligned memory accesses.
bool isSlowDivBypassed() const
Returns true if target has indicated at least one type should be bypassed.
virtual bool isTruncateFree(Type *FromTy, Type *ToTy) const
Return true if it's free to truncate a value of type FromTy to type ToTy.
virtual EVT getTypeToTransformTo(LLVMContext &Context, EVT VT) const
For types supported by the target, this is an identity function.
virtual MVT getPreferredSwitchConditionType(LLVMContext &Context, EVT ConditionVT) const
Returns preferred type for switch condition.
bool isCondCodeLegal(ISD::CondCode CC, MVT VT) const
Return true if the specified condition code is legal on this target.
virtual bool canCombineStoreAndExtract(Type *VectorTy, Value *Idx, unsigned &Cost) const
Return true if the target can combine store(extractelement VectorTy, Idx).
bool isTypeLegal(EVT VT) const
Return true if the target has native support for the specified value type.
virtual bool isFreeAddrSpaceCast(unsigned SrcAS, unsigned DestAS) const
Returns true if a cast from SrcAS to DestAS is "cheap", such that e.g.
virtual bool shouldConsiderGEPOffsetSplit() const
bool hasMultipleConditionRegisters() const
Return true if multiple condition registers are available.
bool isExtFree(const Instruction *I) const
Return true if the extension represented by I is free.
virtual bool getAddrModeArguments(IntrinsicInst *, SmallVectorImpl< Value * > &, Type *&) const
CodeGenPrepare sinks address calculations into the same BB as Load/Store instructions reading the add...
bool isOperationLegalOrCustom(unsigned Op, EVT VT, bool LegalOnly=false) const
Return true if the specified operation is legal on this target or can be made legal with custom lower...
bool isPredictableSelectExpensive() const
Return true if selects are only cheaper than branches if the branch is unlikely to be predicted right...
virtual bool isMultiStoresCheaperThanBitsMerge(EVT LTy, EVT HTy) const
Return true if it is cheaper to split the store of a merged int val from a pair of smaller values int...
bool isLoadExtLegal(unsigned ExtType, EVT ValVT, EVT MemVT) const
Return true if the specified load with extension is legal on this target.
const DenseMap< unsigned int, unsigned int > & getBypassSlowDivWidths() const
Returns map of slow types for division or remainder with corresponding fast types.
virtual bool isCheapToSpeculateCtlz(Type *Ty) const
Return true if it is cheap to speculate a call to intrinsic ctlz.
virtual bool useSoftFloat() const
virtual int64_t getPreferredLargeGEPBaseOffset(int64_t MinOffset, int64_t MaxOffset) const
Return the prefered common base offset.
LegalizeTypeAction getTypeAction(LLVMContext &Context, EVT VT) const
Return how we should legalize values of this type, either it is already legal (return 'Legal') or we ...
virtual bool shouldAlignPointerArgs(CallInst *, unsigned &, Align &) const
Return true if the pointer arguments to CI should be aligned by aligning the object whose address is ...
virtual Type * shouldConvertSplatType(ShuffleVectorInst *SVI) const
Given a shuffle vector SVI representing a vector splat, return a new scalar type of size equal to SVI...
virtual bool addressingModeSupportsTLS(const GlobalValue &) const
Returns true if the targets addressing mode can target thread local storage (TLS).
virtual bool shouldConvertPhiType(Type *From, Type *To) const
Given a set in interconnected phis of type 'From' that are loaded/stored or bitcast to type 'To',...
virtual bool isFAbsFree(EVT VT) const
Return true if an fabs operation is free to the point where it is never worthwhile to replace it with...
virtual bool preferZeroCompareBranch() const
Return true if the heuristic to prefer icmp eq zero should be used in code gen prepare.
virtual bool shouldSinkOperands(Instruction *I, SmallVectorImpl< Use * > &Ops) const
Return true if sinking I's operands to the same basic block as I is profitable, e....
virtual bool isLegalAddressingMode(const DataLayout &DL, const AddrMode &AM, Type *Ty, unsigned AddrSpace, Instruction *I=nullptr) const
Return true if the addressing mode represented by AM is legal for this target, for a load/store of th...
virtual bool optimizeExtendOrTruncateConversion(Instruction *I, Loop *L, const TargetTransformInfo &TTI) const
Try to optimize extending or truncating conversion instructions (like zext, trunc,...
This class defines information used to lower LLVM code to legal SelectionDAG operators that the targe...
std::vector< AsmOperandInfo > AsmOperandInfoVector
virtual bool ExpandInlineAsm(CallInst *) const
This hook allows the target to expand an inline asm call to be explicit llvm code if it wants to.
virtual AsmOperandInfoVector ParseConstraints(const DataLayout &DL, const TargetRegisterInfo *TRI, const CallBase &Call) const
Split up the constraint string from the inline assembly value into the specific constraints and their...
virtual void ComputeConstraintToUse(AsmOperandInfo &OpInfo, SDValue Op, SelectionDAG *DAG=nullptr) const
Determines the constraint code and constraint type to use for the specific AsmOperandInfo,...
virtual bool mayBeEmittedAsTailCall(const CallInst *) const
Return true if the target may be able emit the call instruction as a tail call.
Primary interface to the complete machine description for the target machine.
virtual bool isNoopAddrSpaceCast(unsigned SrcAS, unsigned DestAS) const
Returns true if a cast between SrcAS and DestAS is a noop.
Target-Independent Code Generator Pass Configuration Options.
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
TargetSubtargetInfo - Generic base class for all target subtargets.
virtual const TargetRegisterInfo * getRegisterInfo() const
getRegisterInfo - If register information is available, return it.
virtual const TargetLowering * getTargetLowering() const
virtual bool addrSinkUsingGEPs() const
Sink addresses into blocks using GEP instructions rather than pointer casts and arithmetic.
This class represents a truncation of integer types.
The instances of the Type class are immutable: once they are created, they are never changed.
unsigned getIntegerBitWidth() const
bool isVectorTy() const
True if this is an instance of VectorType.
unsigned getPointerAddressSpace() const
Get the address space of this pointer or pointer vector type.
static IntegerType * getIntNTy(LLVMContext &C, unsigned N)
unsigned getScalarSizeInBits() const LLVM_READONLY
If this is a vector type, return the getPrimitiveSizeInBits value for the element type.
bool isScalableTy() const
Return true if this is a type whose size is a known multiple of vscale.
bool isIntOrPtrTy() const
Return true if this is an integer type or a pointer type.
static IntegerType * getInt32Ty(LLVMContext &C)
bool isIntegerTy() const
True if this is an instance of IntegerType.
Type * getScalarType() const
If this is a vector type, return the element type, otherwise return 'this'.
'undef' values are things that do not have specified contents.
static UndefValue * get(Type *T)
Static factory methods - Return an 'undef' object of the specified type.
A Use represents the edge between a Value definition and its users.
bool replaceUsesOfWith(Value *From, Value *To)
Replace uses of one Value with another.
const Use & getOperandUse(unsigned i) const
void setOperand(unsigned i, Value *Val)
Value * getOperand(unsigned i) const
unsigned getNumOperands() const
LLVM Value Representation.
Type * getType() const
All values are typed, get the type of this value.
const Value * stripAndAccumulateInBoundsConstantOffsets(const DataLayout &DL, APInt &Offset) const
This is a wrapper around stripAndAccumulateConstantOffsets with the in-bounds requirement set to fals...
user_iterator user_begin()
void setName(const Twine &Name)
Change the name of the value.
bool hasOneUse() const
Return true if there is exactly one use of this value.
void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
iterator_range< user_iterator > users()
Align getPointerAlignment(const DataLayout &DL) const
Returns an alignment of the pointer value.
bool isUsedInBasicBlock(const BasicBlock *BB) const
Check if this value is used in the specified basic block.
bool hasNUsesOrMore(unsigned N) const
Return true if this value has N uses or more.
const Value * stripPointerCasts() const
Strip off pointer casts, all-zero GEPs and address space casts.
LLVMContext & getContext() const
All values hold a context through their type.
unsigned getNumUses() const
This method computes the number of uses of this Value.
iterator_range< use_iterator > uses()
void mutateType(Type *Ty)
Mutate the type of this Value to be of the specified type.
user_iterator_impl< User > user_iterator
StringRef getName() const
Return a constant reference to the value's name.
void takeName(Value *V)
Transfer the name from V to this value.
void dump() const
Support for debugging, callable in GDB: V->dump()
Value handle that is nullable, but tries to track the Value.
bool pointsToAliveValue() const
This class represents zero extension of integer types.
constexpr ScalarTy getFixedValue() const
constexpr bool isNonZero() const
constexpr bool isScalable() const
Returns whether the quantity is scaled by a runtime quantity (vscale).
StructType * getStructTypeOrNull() const
TypeSize getSequentialElementStride(const DataLayout &DL) const
self_iterator getIterator()
NodeTy * getNextNode()
Get the next node, or nullptr for the list tail.
This class implements an extremely fast bulk output stream that can only output to a stream.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
@ C
The default llvm calling convention, compatible with C.
unsigned getAddrMode(MCInstrInfo const &MCII, MCInst const &MCI)
cst_pred_ty< is_all_ones > m_AllOnes()
Match an integer or vector with all bits set.
BinaryOp_match< LHS, RHS, Instruction::Add > m_Add(const LHS &L, const RHS &R)
class_match< BinaryOperator > m_BinOp()
Match an arbitrary binary operation and ignore it.
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.
class_match< ConstantInt > m_ConstantInt()
Match an arbitrary ConstantInt and ignore it.
cst_pred_ty< is_one > m_One()
Match an integer 1 or a vector with all elements equal to 1.
ThreeOps_match< Cond, LHS, RHS, Instruction::Select > m_Select(const Cond &C, const LHS &L, const RHS &R)
Matches SelectInst.
cst_pred_ty< is_zero_int > m_ZeroInt()
Match an integer 0 or a vector with all elements equal to 0.
CmpClass_match< LHS, RHS, ICmpInst, ICmpInst::Predicate > m_ICmp(ICmpInst::Predicate &Pred, const LHS &L, const RHS &R)
OneUse_match< T > m_OneUse(const T &SubPattern)
auto m_LogicalOr()
Matches L || R where L and R are arbitrary values.
TwoOps_match< V1_t, V2_t, Instruction::ShuffleVector > m_Shuffle(const V1_t &v1, const V2_t &v2)
Matches ShuffleVectorInst independently of mask value.
CastInst_match< OpTy, ZExtInst > m_ZExt(const OpTy &Op)
Matches ZExt.
class_match< CmpInst > m_Cmp()
Matches any compare instruction and ignore it.
brc_match< Cond_t, bind_ty< BasicBlock >, bind_ty< BasicBlock > > m_Br(const Cond_t &C, BasicBlock *&T, BasicBlock *&F)
apint_match m_APInt(const APInt *&Res)
Match a ConstantInt or splatted ConstantVector, binding the specified pointer to the contained APInt.
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
BinaryOp_match< LHS, RHS, Instruction::Shl > m_Shl(const LHS &L, const RHS &R)
UAddWithOverflow_match< LHS_t, RHS_t, Sum_t > m_UAddWithOverflow(const LHS_t &L, const RHS_t &R, const Sum_t &S)
Match an icmp instruction checking for unsigned overflow on addition.
auto m_LogicalAnd()
Matches L && R where L and R are arbitrary values.
auto m_Undef()
Match an arbitrary undef constant.
BinaryOp_match< LHS, RHS, Instruction::Or, true > m_c_Or(const LHS &L, const RHS &R)
Matches an Or with LHS and RHS in either order.
ThreeOps_match< Val_t, Elt_t, Idx_t, Instruction::InsertElement > m_InsertElt(const Val_t &Val, const Elt_t &Elt, const Idx_t &Idx)
Matches InsertElementInst.
BinaryOp_match< LHS, RHS, Instruction::Sub > m_Sub(const LHS &L, const RHS &R)
match_combine_or< LTy, RTy > m_CombineOr(const LTy &L, const RTy &R)
Combine two pattern matchers matching L || R.
int compare(DigitsT LDigits, int16_t LScale, DigitsT RDigits, int16_t RScale)
Compare two scaled numbers.
ManagedStatic< cl::opt< FnT >, OptCreatorT > Action
@ CE
Windows NT (Windows on ARM)
initializer< Ty > init(const Ty &Val)
PointerTypeMap run(const Module &M)
Compute the PointerTypeMap for the module M.
NodeAddr< PhiNode * > Phi
const_iterator begin(StringRef path, Style style=Style::native)
Get begin iterator over path.
const_iterator end(StringRef path)
Get end iterator over path.
This is an optimization pass for GlobalISel generic memory operations.
auto drop_begin(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the first N elements excluded.
pred_iterator pred_end(BasicBlock *BB)
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
bool RemoveRedundantDbgInstrs(BasicBlock *BB)
Try to remove redundant dbg.value instructions from given basic block.
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
int popcount(T Value) noexcept
Count the number of set bits in a value.
auto size(R &&Range, std::enable_if_t< std::is_base_of< std::random_access_iterator_tag, typename std::iterator_traits< decltype(Range.begin())>::iterator_category >::value, void > *=nullptr)
Get the size of a range.
bool RecursivelyDeleteTriviallyDeadInstructions(Value *V, const TargetLibraryInfo *TLI=nullptr, MemorySSAUpdater *MSSAU=nullptr, std::function< void(Value *)> AboutToDeleteCallback=std::function< void(Value *)>())
If the specified value is a trivially dead instruction, delete it.
bool ConstantFoldTerminator(BasicBlock *BB, bool DeleteDeadConditions=false, const TargetLibraryInfo *TLI=nullptr, DomTreeUpdater *DTU=nullptr)
If a terminator instruction is predicated on a constant value, convert it into an unconditional branc...
APInt operator*(APInt a, uint64_t RHS)
bool isAligned(Align Lhs, uint64_t SizeInBytes)
Checks that SizeInBytes is a multiple of the alignment.
void salvageDebugInfo(const MachineRegisterInfo &MRI, MachineInstr &MI)
Assuming the instruction MI is going to be deleted, attempt to salvage debug users of MI by writing t...
auto successors(const MachineBasicBlock *BB)
ReturnInst * FoldReturnIntoUncondBranch(ReturnInst *RI, BasicBlock *BB, BasicBlock *Pred, DomTreeUpdater *DTU=nullptr)
This method duplicates the specified return instruction into a predecessor which ends in an unconditi...
bool operator!=(uint64_t V1, const APInt &V2)
Instruction * SplitBlockAndInsertIfElse(Value *Cond, BasicBlock::iterator SplitBefore, bool Unreachable, MDNode *BranchWeights=nullptr, DomTreeUpdater *DTU=nullptr, LoopInfo *LI=nullptr, BasicBlock *ElseBlock=nullptr)
Similar to SplitBlockAndInsertIfThen, but the inserted block is on the false path of the branch.
void append_range(Container &C, Range &&R)
Wrapper function to append range R to container C.
bool shouldOptimizeForSize(const MachineFunction *MF, ProfileSummaryInfo *PSI, const MachineBlockFrequencyInfo *BFI, PGSOQueryType QueryType=PGSOQueryType::Other)
Returns true if machine function MF is suggested to be size-optimized based on the profile.
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
void DeleteDeadBlock(BasicBlock *BB, DomTreeUpdater *DTU=nullptr, bool KeepOneInputPHIs=false)
Delete the specified block, which must have no predecessors.
Value * getSplatValue(const Value *V)
Get splat value if the input is a splat vector or return nullptr.
void initializeCodeGenPrepareLegacyPassPass(PassRegistry &)
void findDbgValues(SmallVectorImpl< DbgValueInst * > &DbgValues, Value *V, SmallVectorImpl< DbgVariableRecord * > *DbgVariableRecords=nullptr)
Finds the llvm.dbg.value intrinsics describing a value.
bool operator==(const AddressRangeValuePair &LHS, const AddressRangeValuePair &RHS)
bool SplitIndirectBrCriticalEdges(Function &F, bool IgnoreBlocksWithoutPHI, BranchProbabilityInfo *BPI=nullptr, BlockFrequencyInfo *BFI=nullptr)
Printable print(const GCNRegPressure &RP, const GCNSubtarget *ST=nullptr)
Value * simplifyInstruction(Instruction *I, const SimplifyQuery &Q)
See if we can compute a simplified version of this instruction.
Align getKnownAlignment(Value *V, const DataLayout &DL, const Instruction *CxtI=nullptr, AssumptionCache *AC=nullptr, const DominatorTree *DT=nullptr)
Try to infer an alignment for the specified pointer.
void erase(Container &C, ValueType V)
Wrapper function to remove a value from a container:
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
bool isSplatValue(const Value *V, int Index=-1, unsigned Depth=0)
Return true if each element of the vector value V is poisoned or equal to every other non-poisoned el...
pred_iterator pred_begin(BasicBlock *BB)
bool DeleteDeadPHIs(BasicBlock *BB, const TargetLibraryInfo *TLI=nullptr, MemorySSAUpdater *MSSAU=nullptr)
Examine each PHI in the given block and delete it if it is dead.
bool replaceAndRecursivelySimplify(Instruction *I, Value *SimpleV, const TargetLibraryInfo *TLI=nullptr, const DominatorTree *DT=nullptr, AssumptionCache *AC=nullptr, SmallSetVector< Instruction *, 8 > *UnsimplifiedUsers=nullptr)
Replace all uses of 'I' with 'SimpleV' and simplify the uses recursively.
auto reverse(ContainerTy &&C)
bool recognizeBSwapOrBitReverseIdiom(Instruction *I, bool MatchBSwaps, bool MatchBitReversals, SmallVectorImpl< Instruction * > &InsertedInsts)
Try to match a bswap or bitreverse idiom.
void sort(IteratorTy Start, IteratorTy End)
FPClassTest
Floating-point class tests, supported by 'is_fpclass' intrinsic.
void SplitBlockAndInsertIfThenElse(Value *Cond, BasicBlock::iterator SplitBefore, Instruction **ThenTerm, Instruction **ElseTerm, MDNode *BranchWeights=nullptr, DomTreeUpdater *DTU=nullptr, LoopInfo *LI=nullptr)
SplitBlockAndInsertIfThenElse is similar to SplitBlockAndInsertIfThen, but also creates the ElseBlock...
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
bool none_of(R &&Range, UnaryPredicate P)
Provide wrappers to std::none_of which take ranges instead of having to pass begin/end explicitly.
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.
bool isSafeToSpeculativelyExecute(const Instruction *I, const Instruction *CtxI=nullptr, AssumptionCache *AC=nullptr, const DominatorTree *DT=nullptr, const TargetLibraryInfo *TLI=nullptr)
Return true if the instruction does not have any effects besides calculating the result and does not ...
constexpr unsigned BitWidth
bool extractBranchWeights(const MDNode *ProfileData, SmallVectorImpl< uint32_t > &Weights)
Extract branch weights from MD_prof metadata.
bool bypassSlowDivision(BasicBlock *BB, const DenseMap< unsigned int, unsigned int > &BypassWidth)
This optimization identifies DIV instructions in a BB that can be profitably bypassed and carried out...
gep_type_iterator gep_type_begin(const User *GEP)
void erase_if(Container &C, UnaryPredicate P)
Provide a container algorithm similar to C++ Library Fundamentals v2's erase_if which is equivalent t...
std::pair< Value *, FPClassTest > fcmpToClassTest(CmpInst::Predicate Pred, const Function &F, Value *LHS, Value *RHS, bool LookThroughSrc=true)
Returns a pair of values, which if passed to llvm.is.fpclass, returns the same result as an fcmp with...
auto predecessors(const MachineBasicBlock *BB)
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
Align commonAlignment(Align A, uint64_t Offset)
Returns the alignment that satisfies both alignments.
bool pred_empty(const BasicBlock *BB)
Instruction * SplitBlockAndInsertIfThen(Value *Cond, BasicBlock::iterator SplitBefore, bool Unreachable, MDNode *BranchWeights=nullptr, DomTreeUpdater *DTU=nullptr, LoopInfo *LI=nullptr, BasicBlock *ThenBlock=nullptr)
Split the containing block at the specified instruction - everything before SplitBefore stays in the ...
BasicBlock * SplitEdge(BasicBlock *From, BasicBlock *To, DominatorTree *DT=nullptr, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, const Twine &BBName="")
Split the edge connecting the specified blocks, and return the newly created basic block between From...
static auto filterDbgVars(iterator_range< simple_ilist< DbgRecord >::iterator > R)
Filter the DbgRecord range to DbgVariableRecord types only and downcast.
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.