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) {
1434 InsertedCast = cast<CastInst>(CI->
clone());
1439 TheUse = InsertedCast;
1463 if (
auto *ASC = dyn_cast<AddrSpaceCastInst>(CI)) {
1465 ASC->getDestAddressSpace()))
1505 match(IVInc, m_ExtractValue<0>(m_Intrinsic<Intrinsic::uadd_with_overflow>(
1509 match(IVInc, m_ExtractValue<0>(m_Intrinsic<Intrinsic::usub_with_overflow>(
1520static std::optional<std::pair<Instruction *, Constant *>>
1523 if (!L || L->getHeader() != PN->
getParent() || !L->getLoopLatch())
1524 return std::nullopt;
1527 if (!IVInc || LI->
getLoopFor(IVInc->getParent()) != L)
1528 return std::nullopt;
1532 return std::make_pair(IVInc, Step);
1533 return std::nullopt;
1537 auto *
I = dyn_cast<Instruction>(V);
1544 if (
auto *PN = dyn_cast<PHINode>(
LHS))
1546 return IVInc->first ==
I;
1550bool CodeGenPrepare::replaceMathCmpWithIntrinsic(
BinaryOperator *BO,
1558 assert(L &&
"L should not be null after isIVIncrement()");
1560 if (LI->getLoopFor(
Cmp->getParent()) != L)
1575 if (BO->
getParent() !=
Cmp->getParent() && !IsReplacableIVIncrement(BO)) {
1598 if (BO->
getOpcode() == Instruction::Add &&
1599 IID == Intrinsic::usub_with_overflow) {
1600 assert(isa<Constant>(Arg1) &&
"Unexpected input for usubo");
1609 if ((BO->
getOpcode() != Instruction::Xor && &Iter == BO) || &Iter == Cmp) {
1614 assert(InsertPt !=
nullptr &&
"Parent block did not contain cmp or binop");
1617 Value *MathOV = Builder.CreateBinaryIntrinsic(IID, Arg0, Arg1);
1618 if (BO->
getOpcode() != Instruction::Xor) {
1619 Value *Math = Builder.CreateExtractValue(MathOV, 0,
"math");
1623 "Patterns with XOr should use the BO only in the compare");
1624 Value *OV = Builder.CreateExtractValue(MathOV, 1,
"ov");
1626 Cmp->eraseFromParent();
1636 Value *
A = Cmp->getOperand(0), *
B = Cmp->getOperand(1);
1639 if (isa<Constant>(
A))
1644 B = ConstantInt::get(
B->getType(), 1);
1646 B = ConstantInt::get(
B->getType(), -1);
1652 for (
User *U :
A->users()) {
1654 Add = cast<BinaryOperator>(U);
1663bool CodeGenPrepare::combineToUAddWithOverflow(
CmpInst *Cmp,
1664 ModifyDT &ModifiedDT) {
1665 bool EdgeCase =
false;
1672 A =
Add->getOperand(0);
1673 B =
Add->getOperand(1);
1679 Add->hasNUsesOrMore(EdgeCase ? 1 : 2)))
1685 if (
Add->getParent() !=
Cmp->getParent() && !
Add->hasOneUse())
1688 if (!replaceMathCmpWithIntrinsic(
Add,
A,
B, Cmp,
1689 Intrinsic::uadd_with_overflow))
1693 ModifiedDT = ModifyDT::ModifyInstDT;
1697bool CodeGenPrepare::combineToUSubWithOverflow(
CmpInst *Cmp,
1698 ModifyDT &ModifiedDT) {
1701 if (isa<Constant>(
A) && isa<Constant>(
B))
1712 B = ConstantInt::get(
B->getType(), 1);
1726 Value *CmpVariableOperand = isa<Constant>(
A) ?
B :
A;
1728 for (
User *U : CmpVariableOperand->
users()) {
1731 Sub = cast<BinaryOperator>(U);
1736 const APInt *CmpC, *AddC;
1739 Sub = cast<BinaryOperator>(U);
1752 Cmp, Intrinsic::usub_with_overflow))
1756 ModifiedDT = ModifyDT::ModifyInstDT;
1777 bool MadeChange =
false;
1780 Use &TheUse = UI.getUse();
1787 if (isa<PHINode>(
User))
1795 if (UserBB == DefBB)
1799 CmpInst *&InsertedCmp = InsertedCmps[UserBB];
1805 Cmp->getOperand(0), Cmp->getOperand(1),
"");
1812 TheUse = InsertedCmp;
1818 if (Cmp->use_empty()) {
1819 Cmp->eraseFromParent();
1856 for (
User *U : Cmp->users()) {
1857 if (isa<BranchInst>(U))
1859 if (isa<SelectInst>(U) && cast<SelectInst>(U)->getCondition() == Cmp)
1878 if (CmpBB != FalseBB)
1881 Value *CmpOp0 = Cmp->getOperand(0), *CmpOp1 = Cmp->getOperand(1);
1895 for (
User *U : Cmp->users()) {
1896 if (
auto *BI = dyn_cast<BranchInst>(U)) {
1901 if (
auto *SI = dyn_cast<SelectInst>(U)) {
1904 SI->swapProfMetadata();
1916 Value *Op0 = Cmp->getOperand(0);
1917 Value *Op1 = Cmp->getOperand(1);
1919 isa<Constant>(Op1) || Op0 == Op1)
1926 unsigned NumInspected = 0;
1929 if (++NumInspected > 128)
1937 if (GoodToSwap > 0) {
1938 Cmp->swapOperands();
1946 FCmpInst *FCmp = dyn_cast<FCmpInst>(Cmp);
1958 auto ShouldReverseTransform = [](
FPClassTest ClassTest) {
1961 auto [ClassVal, ClassTest] =
1967 if (!ShouldReverseTransform(ClassTest) && !ShouldReverseTransform(~ClassTest))
1972 Cmp->replaceAllUsesWith(IsFPClass);
1977bool CodeGenPrepare::optimizeCmp(
CmpInst *Cmp, ModifyDT &ModifiedDT) {
1981 if (combineToUAddWithOverflow(Cmp, ModifiedDT))
1984 if (combineToUSubWithOverflow(Cmp, ModifiedDT))
2005 SetOfInstrs &InsertedInsts) {
2008 assert(!InsertedInsts.count(AndI) &&
2009 "Attempting to optimize already optimized and instruction");
2010 (void)InsertedInsts;
2019 if (!isa<ConstantInt>(AndI->
getOperand(0)) &&
2024 for (
auto *U : AndI->
users()) {
2028 if (!isa<ICmpInst>(
User))
2032 if (!CmpC || !CmpC->
isZero())
2047 Use &TheUse = UI.getUse();
2065 TheUse = InsertedAnd;
2081 if (!isa<TruncInst>(
User)) {
2082 if (
User->getOpcode() != Instruction::And ||
2088 if ((Cimm & (Cimm + 1)).getBoolValue())
2101 auto *TruncI = cast<TruncInst>(
User);
2102 bool MadeChange =
false;
2105 TruncE = TruncI->user_end();
2106 TruncUI != TruncE;) {
2108 Use &TruncTheUse = TruncUI.getUse();
2109 Instruction *TruncUser = cast<Instruction>(*TruncUI);
2128 if (isa<PHINode>(TruncUser))
2133 if (UserBB == TruncUserBB)
2137 CastInst *&InsertedTrunc = InsertedTruncs[TruncUserBB];
2139 if (!InsertedShift && !InsertedTrunc) {
2143 if (ShiftI->
getOpcode() == Instruction::AShr)
2145 BinaryOperator::CreateAShr(ShiftI->
getOperand(0), CI,
"");
2148 BinaryOperator::CreateLShr(ShiftI->
getOperand(0), CI,
"");
2156 TruncInsertPt.setHeadBit(
true);
2157 assert(TruncInsertPt != TruncUserBB->
end());
2161 InsertedTrunc->
insertBefore(*TruncUserBB, TruncInsertPt);
2162 InsertedTrunc->
setDebugLoc(TruncI->getDebugLoc());
2166 TruncTheUse = InsertedTrunc;
2199 bool MadeChange =
false;
2202 Use &TheUse = UI.getUse();
2208 if (isa<PHINode>(
User))
2216 if (UserBB == DefBB) {
2231 if (isa<TruncInst>(
User) &&
2244 if (!InsertedShift) {
2248 if (ShiftI->
getOpcode() == Instruction::AShr)
2250 BinaryOperator::CreateAShr(ShiftI->
getOperand(0), CI,
"");
2253 BinaryOperator::CreateLShr(ShiftI->
getOperand(0), CI,
"");
2261 TheUse = InsertedShift;
2310 if (Ty->
isVectorTy() || SizeInBits >
DL->getLargestLegalIntTypeSizeInBits())
2322 FreshBBs.
insert(CallBlock);
2329 SplitPt.setHeadBit(
true);
2332 FreshBBs.
insert(EndBlock);
2337 L->addBasicBlockToLoop(CallBlock, LI);
2338 L->addBasicBlockToLoop(EndBlock, LI);
2369 ModifiedDT = ModifyDT::ModifyBBDT;
2373bool CodeGenPrepare::optimizeCallInst(
CallInst *CI, ModifyDT &ModifiedDT) {
2382 CurInstIterator = BB->
begin();
2389 if (optimizeInlineAsmInst(CI))
2398 for (
auto &Arg : CI->
args()) {
2403 if (!Arg->getType()->isPointerTy())
2406 cast<PointerType>(Arg->getType())->getAddressSpace()),
2413 if ((AI = dyn_cast<AllocaInst>(Val)) && AI->
getAlign() < PrefAlign &&
2432 if (!MIDestAlign || DestAlign > *MIDestAlign)
2433 MI->setDestAlignment(DestAlign);
2435 MaybeAlign MTISrcAlign = MTI->getSourceAlign();
2437 if (!MTISrcAlign || SrcAlign > *MTISrcAlign)
2438 MTI->setSourceAlignment(SrcAlign);
2446 if (CI->
hasFnAttr(Attribute::Cold) && !OptSize &&
2448 for (
auto &Arg : CI->
args()) {
2449 if (!Arg->getType()->isPointerTy())
2451 unsigned AS = Arg->getType()->getPointerAddressSpace();
2452 if (optimizeMemoryInst(CI, Arg, Arg->getType(), AS))
2461 case Intrinsic::assume:
2463 case Intrinsic::allow_runtime_check:
2464 case Intrinsic::allow_ubsan_check:
2465 case Intrinsic::experimental_widenable_condition: {
2474 resetIteratorIfInvalidatedWhileCalling(BB, [&]() {
2479 case Intrinsic::objectsize:
2481 case Intrinsic::is_constant:
2483 case Intrinsic::aarch64_stlxr:
2484 case Intrinsic::aarch64_stxr: {
2493 InsertedInsts.insert(ExtVal);
2497 case Intrinsic::launder_invariant_group:
2498 case Intrinsic::strip_invariant_group: {
2500 auto it = LargeOffsetGEPMap.
find(II);
2501 if (it != LargeOffsetGEPMap.
end()) {
2505 auto GEPs = std::move(it->second);
2506 LargeOffsetGEPMap[ArgVal].append(GEPs.begin(), GEPs.end());
2507 LargeOffsetGEPMap.
erase(II);
2514 case Intrinsic::cttz:
2515 case Intrinsic::ctlz:
2519 case Intrinsic::fshl:
2520 case Intrinsic::fshr:
2521 return optimizeFunnelShift(II);
2522 case Intrinsic::dbg_assign:
2523 case Intrinsic::dbg_value:
2524 return fixupDbgValue(II);
2525 case Intrinsic::masked_gather:
2527 case Intrinsic::masked_scatter:
2534 while (!PtrOps.
empty()) {
2537 if (optimizeMemoryInst(II, PtrVal, AccessTy, AS))
2552 if (
Value *V = Simplifier.optimizeCall(CI, Builder)) {
2565 if (
const auto *II = dyn_cast<IntrinsicInst>(CI))
2567 case Intrinsic::memset:
2568 case Intrinsic::memcpy:
2569 case Intrinsic::memmove:
2577 if (Callee && TLInfo && TLInfo->
getLibFunc(*Callee, LF))
2579 case LibFunc_strcpy:
2580 case LibFunc_strncpy:
2581 case LibFunc_strcat:
2582 case LibFunc_strncat:
2623bool CodeGenPrepare::dupRetToEnableTailCallOpts(
BasicBlock *BB,
2624 ModifyDT &ModifiedDT) {
2632 assert(LI->getLoopFor(BB) ==
nullptr &&
"A return block cannot be in a loop");
2639 BCI = dyn_cast<BitCastInst>(V);
2643 EVI = dyn_cast<ExtractValueInst>(V);
2650 PN = dyn_cast<PHINode>(V);
2656 auto isLifetimeEndOrBitCastFor = [](
const Instruction *Inst) {
2657 const BitCastInst *BC = dyn_cast<BitCastInst>(Inst);
2661 if (
const IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst))
2670 while (isa<DbgInfoIntrinsic>(BI) || BI == BCI || BI == EVI ||
2671 isa<PseudoProbeInst>(BI) || isLifetimeEndOrBitCastFor(BI))
2684 CallInst *CI = dyn_cast<CallInst>(IncomingVal);
2703 CI = dyn_cast_or_null<CallInst>(
2717 if (!VisitedBBs.
insert(Pred).second)
2719 if (
Instruction *
I = Pred->rbegin()->getPrevNonDebugInstruction(
true)) {
2725 if (!V || isa<UndefValue>(V) ||
2735 bool Changed =
false;
2736 for (
auto const &TailCallBB : TailCallBBs) {
2739 BranchInst *BI = dyn_cast<BranchInst>(TailCallBB->getTerminator());
2746 BFI->getBlockFreq(BB) >=
BFI->getBlockFreq(TailCallBB));
2747 BFI->setBlockFreq(BB,
2748 (
BFI->getBlockFreq(BB) -
BFI->getBlockFreq(TailCallBB)));
2749 ModifiedDT = ModifyDT::ModifyBBDT;
2772 Value *OriginalValue =
nullptr;
2773 bool InBounds =
true;
2777 BaseRegField = 0x01,
2779 BaseOffsField = 0x04,
2780 ScaledRegField = 0x08,
2782 MultipleFields = 0xff
2795 return MultipleFields;
2796 if (BaseGV && other.BaseGV && BaseGV->getType() != other.BaseGV->getType())
2797 return MultipleFields;
2800 return MultipleFields;
2803 if (InBounds != other.InBounds)
2804 return MultipleFields;
2807 unsigned Result = NoField;
2810 if (BaseGV != other.BaseGV)
2812 if (BaseOffs != other.BaseOffs)
2815 Result |= ScaledRegField;
2822 return MultipleFields;
2824 return static_cast<FieldName
>(
Result);
2845 case ScaledRegField:
2848 return ConstantInt::get(IntPtrTy, BaseOffs);
2852 void SetCombinedField(FieldName
Field,
Value *V,
2858 case ExtAddrMode::BaseRegField:
2861 case ExtAddrMode::BaseGVField:
2868 case ExtAddrMode::ScaledRegField:
2879 case ExtAddrMode::BaseOffsField:
2898#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
2900 bool NeedPlus =
false;
2906 BaseGV->printAsOperand(
OS,
false);
2911 OS << (NeedPlus ?
" + " :
"") << BaseOffs;
2916 OS << (NeedPlus ?
" + " :
"") <<
"Base:";
2921 OS << (NeedPlus ?
" + " :
"") <<
Scale <<
"*";
2944class TypePromotionTransaction {
2948 class TypePromotionAction {
2956 TypePromotionAction(
Instruction *Inst) : Inst(Inst) {}
2958 virtual ~TypePromotionAction() =
default;
2965 virtual void undo() = 0;
2970 virtual void commit() {
2976 class InsertionHandler {
2985 std::optional<DbgRecord::self_iterator> BeforeDbgRecord = std::nullopt;
2988 bool HasPrevInstruction;
3001 if (HasPrevInstruction) {
3002 Point.PrevInst = &*std::prev(Inst->
getIterator());
3010 if (HasPrevInstruction) {
3027 class InstructionMoveBefore :
public TypePromotionAction {
3029 InsertionHandler Position;
3034 : TypePromotionAction(Inst), Position(Inst) {
3041 void undo()
override {
3043 Position.insert(Inst);
3048 class OperandSetter :
public TypePromotionAction {
3058 : TypePromotionAction(Inst),
Idx(
Idx) {
3060 <<
"for:" << *Inst <<
"\n"
3061 <<
"with:" << *NewVal <<
"\n");
3067 void undo()
override {
3069 <<
"for: " << *Inst <<
"\n"
3070 <<
"with: " << *Origin <<
"\n");
3077 class OperandsHider :
public TypePromotionAction {
3083 OperandsHider(
Instruction *Inst) : TypePromotionAction(Inst) {
3086 OriginalValues.
reserve(NumOpnds);
3087 for (
unsigned It = 0; It < NumOpnds; ++It) {
3099 void undo()
override {
3101 for (
unsigned It = 0, EndIt = OriginalValues.
size(); It != EndIt; ++It)
3107 class TruncBuilder :
public TypePromotionAction {
3114 TruncBuilder(
Instruction *Opnd,
Type *Ty) : TypePromotionAction(Opnd) {
3116 Builder.SetCurrentDebugLocation(
DebugLoc());
3117 Val = Builder.CreateTrunc(Opnd, Ty,
"promoted");
3122 Value *getBuiltValue() {
return Val; }
3125 void undo()
override {
3127 if (
Instruction *IVal = dyn_cast<Instruction>(Val))
3128 IVal->eraseFromParent();
3133 class SExtBuilder :
public TypePromotionAction {
3141 : TypePromotionAction(InsertPt) {
3143 Val = Builder.CreateSExt(Opnd, Ty,
"promoted");
3148 Value *getBuiltValue() {
return Val; }
3151 void undo()
override {
3153 if (
Instruction *IVal = dyn_cast<Instruction>(Val))
3154 IVal->eraseFromParent();
3159 class ZExtBuilder :
public TypePromotionAction {
3167 : TypePromotionAction(InsertPt) {
3169 Builder.SetCurrentDebugLocation(
DebugLoc());
3170 Val = Builder.CreateZExt(Opnd, Ty,
"promoted");
3175 Value *getBuiltValue() {
return Val; }
3178 void undo()
override {
3180 if (
Instruction *IVal = dyn_cast<Instruction>(Val))
3181 IVal->eraseFromParent();
3186 class TypeMutator :
public TypePromotionAction {
3193 : TypePromotionAction(Inst), OrigTy(Inst->
getType()) {
3194 LLVM_DEBUG(
dbgs() <<
"Do: MutateType: " << *Inst <<
" with " << *NewTy
3200 void undo()
override {
3201 LLVM_DEBUG(
dbgs() <<
"Undo: MutateType: " << *Inst <<
" with " << *OrigTy
3208 class UsesReplacer :
public TypePromotionAction {
3210 struct InstructionAndIdx {
3218 : Inst(Inst),
Idx(
Idx) {}
3237 : TypePromotionAction(Inst),
New(
New) {
3238 LLVM_DEBUG(
dbgs() <<
"Do: UsersReplacer: " << *Inst <<
" with " << *New
3243 OriginalUses.
push_back(InstructionAndIdx(UserI,
U.getOperandNo()));
3254 void undo()
override {
3256 for (InstructionAndIdx &
Use : OriginalUses)
3257 Use.Inst->setOperand(
Use.Idx, Inst);
3262 for (
auto *DVI : DbgValues)
3263 DVI->replaceVariableLocationOp(New, Inst);
3267 DVR->replaceVariableLocationOp(New, Inst);
3272 class InstructionRemover :
public TypePromotionAction {
3274 InsertionHandler Inserter;
3278 OperandsHider Hider;
3281 UsesReplacer *Replacer =
nullptr;
3284 SetOfInstrs &RemovedInsts;
3291 InstructionRemover(
Instruction *Inst, SetOfInstrs &RemovedInsts,
3292 Value *New =
nullptr)
3293 : TypePromotionAction(Inst), Inserter(Inst), Hider(Inst),
3294 RemovedInsts(RemovedInsts) {
3296 Replacer =
new UsesReplacer(Inst, New);
3297 LLVM_DEBUG(
dbgs() <<
"Do: InstructionRemover: " << *Inst <<
"\n");
3298 RemovedInsts.insert(Inst);
3305 ~InstructionRemover()
override {
delete Replacer; }
3307 InstructionRemover &operator=(
const InstructionRemover &other) =
delete;
3308 InstructionRemover(
const InstructionRemover &other) =
delete;
3312 void undo()
override {
3313 LLVM_DEBUG(
dbgs() <<
"Undo: InstructionRemover: " << *Inst <<
"\n");
3314 Inserter.insert(Inst);
3318 RemovedInsts.erase(Inst);
3326 using ConstRestorationPt =
const TypePromotionAction *;
3328 TypePromotionTransaction(SetOfInstrs &RemovedInsts)
3329 : RemovedInsts(RemovedInsts) {}
3336 void rollback(ConstRestorationPt Point);
3339 ConstRestorationPt getRestorationPoint()
const;
3371 SetOfInstrs &RemovedInsts;
3376void TypePromotionTransaction::setOperand(
Instruction *Inst,
unsigned Idx,
3378 Actions.
push_back(std::make_unique<TypePromotionTransaction::OperandSetter>(
3379 Inst,
Idx, NewVal));
3382void TypePromotionTransaction::eraseInstruction(
Instruction *Inst,
3385 std::make_unique<TypePromotionTransaction::InstructionRemover>(
3386 Inst, RemovedInsts, NewVal));
3389void TypePromotionTransaction::replaceAllUsesWith(
Instruction *Inst,
3392 std::make_unique<TypePromotionTransaction::UsesReplacer>(Inst, New));
3395void TypePromotionTransaction::mutateType(
Instruction *Inst,
Type *NewTy) {
3397 std::make_unique<TypePromotionTransaction::TypeMutator>(Inst, NewTy));
3401 std::unique_ptr<TruncBuilder>
Ptr(
new TruncBuilder(Opnd, Ty));
3403 Actions.push_back(std::move(
Ptr));
3409 std::unique_ptr<SExtBuilder>
Ptr(
new SExtBuilder(Inst, Opnd, Ty));
3411 Actions.push_back(std::move(
Ptr));
3417 std::unique_ptr<ZExtBuilder>
Ptr(
new ZExtBuilder(Inst, Opnd, Ty));
3419 Actions.push_back(std::move(
Ptr));
3423TypePromotionTransaction::ConstRestorationPt
3424TypePromotionTransaction::getRestorationPoint()
const {
3425 return !Actions.empty() ? Actions.back().get() :
nullptr;
3428bool TypePromotionTransaction::commit() {
3429 for (std::unique_ptr<TypePromotionAction> &Action : Actions)
3436void TypePromotionTransaction::rollback(
3437 TypePromotionTransaction::ConstRestorationPt Point) {
3438 while (!Actions.empty() && Point != Actions.back().get()) {
3439 std::unique_ptr<TypePromotionAction> Curr = Actions.pop_back_val();
3449class AddressingModeMatcher {
3468 const SetOfInstrs &InsertedInsts;
3471 InstrToOrigTy &PromotedInsts;
3474 TypePromotionTransaction &TPT;
3477 std::pair<AssertingVH<GetElementPtrInst>, int64_t> &LargeOffsetGEP;
3481 bool IgnoreProfitability;
3484 bool OptSize =
false;
3489 AddressingModeMatcher(
3494 const SetOfInstrs &InsertedInsts, InstrToOrigTy &PromotedInsts,
3495 TypePromotionTransaction &TPT,
3498 : AddrModeInsts(AMI), TLI(TLI),
TRI(
TRI),
3499 DL(
MI->getModule()->getDataLayout()), LI(LI), getDTFn(getDTFn),
3500 AccessTy(AT), AddrSpace(AS), MemoryInst(
MI),
AddrMode(AM),
3501 InsertedInsts(InsertedInsts), PromotedInsts(PromotedInsts), TPT(TPT),
3502 LargeOffsetGEP(LargeOffsetGEP), OptSize(OptSize), PSI(PSI),
BFI(
BFI) {
3503 IgnoreProfitability =
false;
3520 InstrToOrigTy &PromotedInsts, TypePromotionTransaction &TPT,
3525 bool Success = AddressingModeMatcher(AddrModeInsts, TLI,
TRI, LI, getDTFn,
3526 AccessTy, AS, MemoryInst, Result,
3527 InsertedInsts, PromotedInsts, TPT,
3528 LargeOffsetGEP, OptSize, PSI, BFI)
3536 bool matchScaledValue(
Value *ScaleReg, int64_t Scale,
unsigned Depth);
3538 bool matchOperationAddr(
User *AddrInst,
unsigned Opcode,
unsigned Depth,
3539 bool *MovedAway =
nullptr);
3540 bool isProfitableToFoldIntoAddressingMode(
Instruction *
I,
3543 bool valueAlreadyLiveAtInst(
Value *Val,
Value *KnownLive1,
Value *KnownLive2);
3544 bool isPromotionProfitable(
unsigned NewCost,
unsigned OldCost,
3545 Value *PromotedOperand)
const;
3551class PhiNodeSetIterator {
3552 PhiNodeSet *
const Set;
3553 size_t CurrentIndex = 0;
3558 PhiNodeSetIterator(PhiNodeSet *
const Set,
size_t Start);
3560 PhiNodeSetIterator &operator++();
3576 friend class PhiNodeSetIterator;
3579 using iterator = PhiNodeSetIterator;
3594 size_t FirstValidElement = 0;
3601 if (NodeMap.insert(std::make_pair(
Ptr,
NodeList.size())).second) {
3612 if (NodeMap.erase(
Ptr)) {
3613 SkipRemovedElements(FirstValidElement);
3623 FirstValidElement = 0;
3629 if (FirstValidElement == 0)
3630 SkipRemovedElements(FirstValidElement);
3631 return PhiNodeSetIterator(
this, FirstValidElement);
3635 iterator
end() {
return PhiNodeSetIterator(
this,
NodeList.size()); }
3638 size_t size()
const {
return NodeMap.size(); }
3649 void SkipRemovedElements(
size_t &CurrentIndex) {
3650 while (CurrentIndex <
NodeList.size()) {
3651 auto it = NodeMap.find(
NodeList[CurrentIndex]);
3654 if (it != NodeMap.end() && it->second == CurrentIndex)
3661PhiNodeSetIterator::PhiNodeSetIterator(PhiNodeSet *
const Set,
size_t Start)
3662 : Set(Set), CurrentIndex(Start) {}
3664PHINode *PhiNodeSetIterator::operator*()
const {
3666 "PhiNodeSet access out of range");
3667 return Set->NodeList[CurrentIndex];
3670PhiNodeSetIterator &PhiNodeSetIterator::operator++() {
3672 "PhiNodeSet access out of range");
3674 Set->SkipRemovedElements(CurrentIndex);
3678bool PhiNodeSetIterator::operator==(
const PhiNodeSetIterator &RHS)
const {
3679 return CurrentIndex ==
RHS.CurrentIndex;
3682bool PhiNodeSetIterator::operator!=(
const PhiNodeSetIterator &RHS)
const {
3683 return !((*this) ==
RHS);
3689class SimplificationTracker {
3694 PhiNodeSet AllPhiNodes;
3703 auto SV = Storage.
find(V);
3704 if (SV == Storage.
end())
3714 while (!WorkList.
empty()) {
3716 if (!Visited.
insert(
P).second)
3718 if (
auto *PI = dyn_cast<Instruction>(
P))
3720 for (
auto *U : PI->users())
3723 PI->replaceAllUsesWith(V);
3724 if (
auto *
PHI = dyn_cast<PHINode>(PI))
3725 AllPhiNodes.erase(
PHI);
3726 if (
auto *
Select = dyn_cast<SelectInst>(PI))
3728 PI->eraseFromParent();
3738 while (OldReplacement !=
From) {
3740 To = dyn_cast<PHINode>(OldReplacement);
3741 OldReplacement = Get(
From);
3743 assert(To && Get(To) == To &&
"Replacement PHI node is already replaced.");
3745 From->replaceAllUsesWith(To);
3746 AllPhiNodes.erase(
From);
3747 From->eraseFromParent();
3750 PhiNodeSet &newPhiNodes() {
return AllPhiNodes; }
3752 void insertNewPhi(
PHINode *PN) { AllPhiNodes.insert(PN); }
3756 unsigned countNewPhiNodes()
const {
return AllPhiNodes.size(); }
3758 unsigned countNewSelectNodes()
const {
return AllSelectNodes.
size(); }
3760 void destroyNewNodes(
Type *CommonType) {
3763 for (
auto *
I : AllPhiNodes) {
3764 I->replaceAllUsesWith(Dummy);
3765 I->eraseFromParent();
3767 AllPhiNodes.clear();
3768 for (
auto *
I : AllSelectNodes) {
3769 I->replaceAllUsesWith(Dummy);
3770 I->eraseFromParent();
3772 AllSelectNodes.clear();
3777class AddressingModeCombiner {
3779 typedef std::pair<PHINode *, PHINode *> PHIPair;
3786 ExtAddrMode::FieldName DifferentField = ExtAddrMode::NoField;
3789 bool AllAddrModesTrivial =
true;
3792 Type *CommonType =
nullptr;
3801 Value *CommonValue =
nullptr;
3805 : SQ(_SQ), Original(OriginalValue) {}
3807 ~AddressingModeCombiner() { eraseCommonValueIfDead(); }
3819 AllAddrModesTrivial = AllAddrModesTrivial && NewAddrMode.isTrivial();
3822 if (AddrModes.
empty()) {
3830 ExtAddrMode::FieldName ThisDifferentField =
3831 AddrModes[0].compare(NewAddrMode);
3832 if (DifferentField == ExtAddrMode::NoField)
3833 DifferentField = ThisDifferentField;
3834 else if (DifferentField != ThisDifferentField)
3835 DifferentField = ExtAddrMode::MultipleFields;
3838 bool CanHandle = DifferentField != ExtAddrMode::MultipleFields;
3841 CanHandle = CanHandle && DifferentField != ExtAddrMode::ScaleField;
3846 CanHandle = CanHandle && (DifferentField != ExtAddrMode::BaseOffsField ||
3851 CanHandle = CanHandle && (DifferentField != ExtAddrMode::BaseGVField ||
3852 !NewAddrMode.HasBaseReg);
3869 bool combineAddrModes() {
3871 if (AddrModes.
size() == 0)
3875 if (AddrModes.
size() == 1 || DifferentField == ExtAddrMode::NoField)
3880 if (AllAddrModesTrivial)
3883 if (!addrModeCombiningAllowed())
3889 FoldAddrToValueMapping
Map;
3890 if (!initializeMap(Map))
3893 CommonValue = findCommon(Map);
3895 AddrModes[0].SetCombinedField(DifferentField, CommonValue, AddrModes);
3896 return CommonValue !=
nullptr;
3902 void eraseCommonValueIfDead() {
3903 if (CommonValue && CommonValue->
getNumUses() == 0)
3904 if (
Instruction *CommonInst = dyn_cast<Instruction>(CommonValue))
3905 CommonInst->eraseFromParent();
3913 bool initializeMap(FoldAddrToValueMapping &Map) {
3918 for (
auto &AM : AddrModes) {
3919 Value *DV = AM.GetFieldAsValue(DifferentField, IntPtrTy);
3922 if (CommonType && CommonType !=
Type)
3925 Map[AM.OriginalValue] = DV;
3930 assert(CommonType &&
"At least one non-null value must be!");
3931 for (
auto *V : NullValue)
3959 Value *findCommon(FoldAddrToValueMapping &Map) {
3967 SimplificationTracker
ST(SQ);
3972 InsertPlaceholders(Map, TraverseOrder, ST);
3975 FillPlaceholders(Map, TraverseOrder, ST);
3978 ST.destroyNewNodes(CommonType);
3983 unsigned PhiNotMatchedCount = 0;
3985 ST.destroyNewNodes(CommonType);
3989 auto *
Result =
ST.Get(
Map.find(Original)->second);
3991 NumMemoryInstsPhiCreated +=
ST.countNewPhiNodes() + PhiNotMatchedCount;
3992 NumMemoryInstsSelectCreated +=
ST.countNewSelectNodes();
4001 PhiNodeSet &PhiNodesToMatch) {
4008 while (!WorkList.
empty()) {
4010 if (!Visited.
insert(Item).second)
4017 for (
auto *
B : Item.first->blocks()) {
4018 Value *FirstValue = Item.first->getIncomingValueForBlock(
B);
4019 Value *SecondValue = Item.second->getIncomingValueForBlock(
B);
4020 if (FirstValue == SecondValue)
4023 PHINode *FirstPhi = dyn_cast<PHINode>(FirstValue);
4024 PHINode *SecondPhi = dyn_cast<PHINode>(SecondValue);
4030 if (!FirstPhi || !SecondPhi || !PhiNodesToMatch.count(FirstPhi) ||
4035 if (Matcher.
count({FirstPhi, SecondPhi}))
4040 if (MatchedPHIs.
insert(FirstPhi).second)
4041 Matcher.
insert({FirstPhi, SecondPhi});
4043 WorkList.
push_back({FirstPhi, SecondPhi});
4052 bool MatchPhiSet(SimplificationTracker &ST,
bool AllowNewPhiNodes,
4053 unsigned &PhiNotMatchedCount) {
4059 PhiNodeSet &PhiNodesToMatch =
ST.newPhiNodes();
4060 while (PhiNodesToMatch.size()) {
4064 WillNotMatch.
clear();
4068 bool IsMatched =
false;
4069 for (
auto &
P :
PHI->getParent()->phis()) {
4071 if (PhiNodesToMatch.count(&
P))
4073 if ((IsMatched = MatchPhiNode(
PHI, &
P, Matched, PhiNodesToMatch)))
4078 for (
auto M : Matched)
4084 for (
auto MV : Matched)
4085 ST.ReplacePhi(MV.first, MV.second);
4090 if (!AllowNewPhiNodes)
4093 PhiNotMatchedCount += WillNotMatch.
size();
4094 for (
auto *
P : WillNotMatch)
4095 PhiNodesToMatch.erase(
P);
4100 void FillPlaceholders(FoldAddrToValueMapping &Map,
4102 SimplificationTracker &ST) {
4103 while (!TraverseOrder.
empty()) {
4105 assert(
Map.contains(Current) &&
"No node to fill!!!");
4110 auto *CurrentSelect = cast<SelectInst>(Current);
4111 auto *TrueValue = CurrentSelect->getTrueValue();
4112 assert(
Map.contains(TrueValue) &&
"No True Value!");
4113 Select->setTrueValue(
ST.Get(Map[TrueValue]));
4114 auto *FalseValue = CurrentSelect->getFalseValue();
4115 assert(
Map.contains(FalseValue) &&
"No False Value!");
4116 Select->setFalseValue(
ST.Get(Map[FalseValue]));
4119 auto *
PHI = cast<PHINode>(V);
4122 Value *PV = cast<PHINode>(Current)->getIncomingValueForBlock(
B);
4123 assert(
Map.contains(PV) &&
"No predecessor Value!");
4124 PHI->addIncoming(
ST.Get(Map[PV]),
B);
4127 Map[Current] =
ST.Simplify(V);
4136 void InsertPlaceholders(FoldAddrToValueMapping &Map,
4138 SimplificationTracker &ST) {
4140 assert((isa<PHINode>(Original) || isa<SelectInst>(Original)) &&
4141 "Address must be a Phi or Select node");
4144 while (!Worklist.
empty()) {
4147 if (
Map.contains(Current))
4153 if (
SelectInst *CurrentSelect = dyn_cast<SelectInst>(Current)) {
4158 CurrentSelect->getName(),
4159 CurrentSelect->getIterator(), CurrentSelect);
4163 Worklist.
push_back(CurrentSelect->getTrueValue());
4164 Worklist.
push_back(CurrentSelect->getFalseValue());
4167 PHINode *CurrentPhi = cast<PHINode>(Current);
4172 ST.insertNewPhi(
PHI);
4178 bool addrModeCombiningAllowed() {
4181 switch (DifferentField) {
4184 case ExtAddrMode::BaseRegField:
4186 case ExtAddrMode::BaseGVField:
4188 case ExtAddrMode::BaseOffsField:
4190 case ExtAddrMode::ScaledRegField:
4200bool AddressingModeMatcher::matchScaledValue(
Value *ScaleReg, int64_t Scale,
4205 return matchAddr(ScaleReg,
Depth);
4220 TestAddrMode.
Scale += Scale;
4235 Value *AddLHS =
nullptr;
4236 if (isa<Instruction>(ScaleReg) &&
4239 TestAddrMode.InBounds =
false;
4246 AddrModeInsts.
push_back(cast<Instruction>(ScaleReg));
4256 auto GetConstantStep =
4257 [
this](
const Value *
V) -> std::optional<std::pair<Instruction *, APInt>> {
4258 auto *PN = dyn_cast<PHINode>(V);
4260 return std::nullopt;
4263 return std::nullopt;
4270 if (
auto *OIVInc = dyn_cast<OverflowingBinaryOperator>(IVInc->first))
4271 if (OIVInc->hasNoSignedWrap() || OIVInc->hasNoUnsignedWrap())
4272 return std::nullopt;
4273 if (
auto *ConstantStep = dyn_cast<ConstantInt>(IVInc->second))
4274 return std::make_pair(IVInc->first, ConstantStep->getValue());
4275 return std::nullopt;
4290 if (
auto IVStep = GetConstantStep(ScaleReg)) {
4297 APInt Step = IVStep->second;
4299 if (
Offset.isSignedIntN(64)) {
4300 TestAddrMode.InBounds =
false;
4302 TestAddrMode.BaseOffs -=
Offset.getLimitedValue();
4307 getDTFn().
dominates(IVInc, MemoryInst)) {
4308 AddrModeInsts.
push_back(cast<Instruction>(IVInc));
4327 switch (
I->getOpcode()) {
4328 case Instruction::BitCast:
4329 case Instruction::AddrSpaceCast:
4331 if (
I->getType() ==
I->getOperand(0)->getType())
4333 return I->getType()->isIntOrPtrTy();
4334 case Instruction::PtrToInt:
4337 case Instruction::IntToPtr:
4340 case Instruction::Add:
4342 case Instruction::Mul:
4343 case Instruction::Shl:
4345 return isa<ConstantInt>(
I->getOperand(1));
4346 case Instruction::GetElementPtr:
4359 Instruction *PromotedInst = dyn_cast<Instruction>(Val);
4374class TypePromotionHelper {
4377 static void addPromotedInst(InstrToOrigTy &PromotedInsts,
4379 ExtType ExtTy = IsSExt ? SignExtension : ZeroExtension;
4380 InstrToOrigTy::iterator It = PromotedInsts.find(ExtOpnd);
4381 if (It != PromotedInsts.end()) {
4384 if (It->second.getInt() == ExtTy)
4390 ExtTy = BothExtension;
4392 PromotedInsts[ExtOpnd] = TypeIsSExt(ExtOpnd->
getType(), ExtTy);
4399 static const Type *getOrigType(
const InstrToOrigTy &PromotedInsts,
4401 ExtType ExtTy = IsSExt ? SignExtension : ZeroExtension;
4402 InstrToOrigTy::const_iterator It = PromotedInsts.find(Opnd);
4403 if (It != PromotedInsts.end() && It->second.getInt() == ExtTy)
4404 return It->second.getPointer();
4419 static bool canGetThrough(
const Instruction *Inst,
Type *ConsideredExtType,
4420 const InstrToOrigTy &PromotedInsts,
bool IsSExt);
4424 static bool shouldExtOperand(
const Instruction *Inst,
int OpIdx) {
4425 return !(isa<SelectInst>(Inst) && OpIdx == 0);
4437 static Value *promoteOperandForTruncAndAnyExt(
4439 InstrToOrigTy &PromotedInsts,
unsigned &CreatedInstsCost,
4453 TypePromotionTransaction &TPT,
4454 InstrToOrigTy &PromotedInsts,
4455 unsigned &CreatedInstsCost,
4461 static Value *signExtendOperandForOther(
4463 InstrToOrigTy &PromotedInsts,
unsigned &CreatedInstsCost,
4466 return promoteOperandForOther(Ext, TPT, PromotedInsts, CreatedInstsCost,
4467 Exts, Truncs, TLI,
true);
4471 static Value *zeroExtendOperandForOther(
4473 InstrToOrigTy &PromotedInsts,
unsigned &CreatedInstsCost,
4476 return promoteOperandForOther(Ext, TPT, PromotedInsts, CreatedInstsCost,
4477 Exts, Truncs, TLI,
false);
4483 InstrToOrigTy &PromotedInsts,
4484 unsigned &CreatedInstsCost,
4500 const InstrToOrigTy &PromotedInsts);
4505bool TypePromotionHelper::canGetThrough(
const Instruction *Inst,
4506 Type *ConsideredExtType,
4507 const InstrToOrigTy &PromotedInsts,
4516 if (isa<ZExtInst>(Inst))
4520 if (IsSExt && isa<SExtInst>(Inst))
4525 if (
const auto *BinOp = dyn_cast<BinaryOperator>(Inst))
4526 if (isa<OverflowingBinaryOperator>(BinOp) &&
4527 ((!IsSExt && BinOp->hasNoUnsignedWrap()) ||
4528 (IsSExt && BinOp->hasNoSignedWrap())))
4532 if ((Inst->
getOpcode() == Instruction::And ||
4537 if (Inst->
getOpcode() == Instruction::Xor) {
4539 if (
const auto *Cst = dyn_cast<ConstantInt>(Inst->
getOperand(1)))
4540 if (!Cst->getValue().isAllOnes())
4549 if (Inst->
getOpcode() == Instruction::LShr && !IsSExt)
4558 const auto *ExtInst = cast<const Instruction>(*Inst->
user_begin());
4559 if (ExtInst->hasOneUse()) {
4560 const auto *AndInst = dyn_cast<const Instruction>(*ExtInst->user_begin());
4561 if (AndInst && AndInst->getOpcode() == Instruction::And) {
4562 const auto *Cst = dyn_cast<ConstantInt>(AndInst->getOperand(1));
4572 if (!isa<TruncInst>(Inst))
4586 Instruction *Opnd = dyn_cast<Instruction>(OpndVal);
4594 const Type *OpndType = getOrigType(PromotedInsts, Opnd, IsSExt);
4597 else if ((IsSExt && isa<SExtInst>(Opnd)) || (!IsSExt && isa<ZExtInst>(Opnd)))
4607TypePromotionHelper::Action TypePromotionHelper::getAction(
4608 Instruction *Ext,
const SetOfInstrs &InsertedInsts,
4610 assert((isa<SExtInst>(Ext) || isa<ZExtInst>(Ext)) &&
4611 "Unexpected instruction type");
4612 Instruction *ExtOpnd = dyn_cast<Instruction>(
Ext->getOperand(0));
4614 bool IsSExt = isa<SExtInst>(Ext);
4618 if (!ExtOpnd || !canGetThrough(ExtOpnd, ExtTy, PromotedInsts, IsSExt))
4624 if (isa<TruncInst>(ExtOpnd) && InsertedInsts.count(ExtOpnd))
4629 if (isa<SExtInst>(ExtOpnd) || isa<TruncInst>(ExtOpnd) ||
4630 isa<ZExtInst>(ExtOpnd))
4631 return promoteOperandForTruncAndAnyExt;
4637 return IsSExt ? signExtendOperandForOther : zeroExtendOperandForOther;
4640Value *TypePromotionHelper::promoteOperandForTruncAndAnyExt(
4642 InstrToOrigTy &PromotedInsts,
unsigned &CreatedInstsCost,
4648 Value *ExtVal = SExt;
4649 bool HasMergedNonFreeExt =
false;
4650 if (isa<ZExtInst>(SExtOpnd)) {
4653 HasMergedNonFreeExt = !TLI.
isExtFree(SExtOpnd);
4657 TPT.eraseInstruction(SExt);
4662 TPT.setOperand(SExt, 0, SExtOpnd->
getOperand(0));
4664 CreatedInstsCost = 0;
4668 TPT.eraseInstruction(SExtOpnd);
4671 Instruction *ExtInst = dyn_cast<Instruction>(ExtVal);
4676 CreatedInstsCost = !TLI.
isExtFree(ExtInst) && !HasMergedNonFreeExt;
4684 TPT.eraseInstruction(ExtInst, NextVal);
4688Value *TypePromotionHelper::promoteOperandForOther(
4690 InstrToOrigTy &PromotedInsts,
unsigned &CreatedInstsCost,
4697 CreatedInstsCost = 0;
4703 Value *Trunc = TPT.createTrunc(Ext, ExtOpnd->
getType());
4704 if (
Instruction *ITrunc = dyn_cast<Instruction>(Trunc)) {
4706 ITrunc->moveAfter(ExtOpnd);
4711 TPT.replaceAllUsesWith(ExtOpnd, Trunc);
4714 TPT.setOperand(Ext, 0, ExtOpnd);
4724 addPromotedInst(PromotedInsts, ExtOpnd, IsSExt);
4726 TPT.mutateType(ExtOpnd,
Ext->getType());
4728 TPT.replaceAllUsesWith(Ext, ExtOpnd);
4731 for (
int OpIdx = 0, EndOpIdx = ExtOpnd->
getNumOperands(); OpIdx != EndOpIdx;
4735 !shouldExtOperand(ExtOpnd, OpIdx)) {
4741 if (
const ConstantInt *Cst = dyn_cast<ConstantInt>(Opnd)) {
4743 unsigned BitWidth =
Ext->getType()->getIntegerBitWidth();
4746 TPT.setOperand(ExtOpnd, OpIdx, ConstantInt::get(
Ext->getType(), CstVal));
4750 if (isa<UndefValue>(Opnd)) {
4757 Value *ValForExtOpnd = IsSExt
4758 ? TPT.createSExt(ExtOpnd, Opnd,
Ext->getType())
4759 : TPT.createZExt(ExtOpnd, Opnd,
Ext->getType());
4760 TPT.setOperand(ExtOpnd, OpIdx, ValForExtOpnd);
4761 Instruction *InstForExtOpnd = dyn_cast<Instruction>(ValForExtOpnd);
4762 if (!InstForExtOpnd)
4768 CreatedInstsCost += !TLI.
isExtFree(InstForExtOpnd);
4771 TPT.eraseInstruction(Ext);
4783bool AddressingModeMatcher::isPromotionProfitable(
4784 unsigned NewCost,
unsigned OldCost,
Value *PromotedOperand)
const {
4785 LLVM_DEBUG(
dbgs() <<
"OldCost: " << OldCost <<
"\tNewCost: " << NewCost
4790 if (NewCost > OldCost)
4792 if (NewCost < OldCost)
4811bool AddressingModeMatcher::matchOperationAddr(
User *AddrInst,
unsigned Opcode,
4823 case Instruction::PtrToInt:
4826 case Instruction::IntToPtr: {
4834 case Instruction::BitCast:
4844 case Instruction::AddrSpaceCast: {
4852 case Instruction::Add: {
4856 unsigned OldSize = AddrModeInsts.
size();
4861 TypePromotionTransaction::ConstRestorationPt LastKnownGood =
4862 TPT.getRestorationPoint();
4866 int First = 0, Second = 1;
4868 && !isa<ConstantInt>(AddrInst->
getOperand(Second)))
4877 AddrModeInsts.
resize(OldSize);
4878 TPT.rollback(LastKnownGood);
4888 AddrModeInsts.
resize(OldSize);
4889 TPT.rollback(LastKnownGood);
4895 case Instruction::Mul:
4896 case Instruction::Shl: {
4900 if (!RHS ||
RHS->getBitWidth() > 64)
4902 int64_t Scale = Opcode == Instruction::Shl
4903 ? 1LL <<
RHS->getLimitedValue(
RHS->getBitWidth() - 1)
4904 :
RHS->getSExtValue();
4908 case Instruction::GetElementPtr: {
4911 int VariableOperand = -1;
4912 unsigned VariableScale = 0;
4914 int64_t ConstantOffset = 0;
4916 for (
unsigned i = 1, e = AddrInst->
getNumOperands(); i != e; ++i, ++GTI) {
4920 cast<ConstantInt>(AddrInst->
getOperand(i))->getZExtValue();
4930 dyn_cast<ConstantInt>(AddrInst->
getOperand(i))) {
4938 if (VariableOperand != -1)
4942 VariableOperand = i;
4950 if (VariableOperand == -1) {
4951 AddrMode.BaseOffs += ConstantOffset;
4953 if (!cast<GEPOperator>(AddrInst)->isInBounds())
4957 AddrMode.BaseOffs -= ConstantOffset;
4961 ConstantOffset > 0) {
4967 auto *BaseI = dyn_cast<Instruction>(
Base);
4968 auto *
GEP = cast<GetElementPtrInst>(AddrInst);
4969 if (isa<Argument>(
Base) || isa<GlobalValue>(
Base) ||
4970 (BaseI && !isa<CastInst>(BaseI) &&
4971 !isa<GetElementPtrInst>(BaseI))) {
4975 : &
GEP->getFunction()->getEntryBlock();
4977 LargeOffsetGEP = std::make_pair(
GEP, ConstantOffset);
4986 unsigned OldSize = AddrModeInsts.
size();
4989 AddrMode.BaseOffs += ConstantOffset;
4990 if (!cast<GEPOperator>(AddrInst)->isInBounds())
4998 AddrModeInsts.
resize(OldSize);
5006 if (!matchScaledValue(AddrInst->
getOperand(VariableOperand), VariableScale,
5011 AddrModeInsts.
resize(OldSize);
5016 AddrMode.BaseOffs += ConstantOffset;
5017 if (!matchScaledValue(AddrInst->
getOperand(VariableOperand),
5018 VariableScale,
Depth)) {
5021 AddrModeInsts.
resize(OldSize);
5028 case Instruction::SExt:
5029 case Instruction::ZExt: {
5036 TypePromotionHelper::Action TPH =
5037 TypePromotionHelper::getAction(Ext, InsertedInsts, TLI, PromotedInsts);
5041 TypePromotionTransaction::ConstRestorationPt LastKnownGood =
5042 TPT.getRestorationPoint();
5043 unsigned CreatedInstsCost = 0;
5045 Value *PromotedOperand =
5046 TPH(Ext, TPT, PromotedInsts, CreatedInstsCost,
nullptr,
nullptr, TLI);
5061 assert(PromotedOperand &&
5062 "TypePromotionHelper should have filtered out those cases");
5065 unsigned OldSize = AddrModeInsts.
size();
5067 if (!matchAddr(PromotedOperand,
Depth) ||
5072 !isPromotionProfitable(CreatedInstsCost,
5073 ExtCost + (AddrModeInsts.
size() - OldSize),
5076 AddrModeInsts.
resize(OldSize);
5077 LLVM_DEBUG(
dbgs() <<
"Sign extension does not pay off: rollback\n");
5078 TPT.rollback(LastKnownGood);
5083 case Instruction::Call:
5084 if (
IntrinsicInst *II = dyn_cast<IntrinsicInst>(AddrInst)) {
5101bool AddressingModeMatcher::matchAddr(
Value *
Addr,
unsigned Depth) {
5104 TypePromotionTransaction::ConstRestorationPt LastKnownGood =
5105 TPT.getRestorationPoint();
5124 unsigned OldSize = AddrModeInsts.
size();
5127 bool MovedAway =
false;
5128 if (matchOperationAddr(
I,
I->getOpcode(),
Depth, &MovedAway)) {
5136 if (
I->hasOneUse() ||
5137 isProfitableToFoldIntoAddressingMode(
I, BackupAddrMode,
AddrMode)) {
5144 AddrModeInsts.
resize(OldSize);
5145 TPT.rollback(LastKnownGood);
5148 if (matchOperationAddr(CE,
CE->getOpcode(),
Depth))
5150 TPT.rollback(LastKnownGood);
5151 }
else if (isa<ConstantPointerNull>(
Addr)) {
5177 TPT.rollback(LastKnownGood);
5196 if (OpInfo.CallOperandVal == OpVal &&
5198 !OpInfo.isIndirect))
5214 if (!ConsideredInsts.
insert(
I).second)
5222 for (
Use &U :
I->uses()) {
5228 Instruction *UserI = cast<Instruction>(U.getUser());
5229 if (
LoadInst *LI = dyn_cast<LoadInst>(UserI)) {
5230 MemoryUses.push_back({&U, LI->getType()});
5234 if (
StoreInst *SI = dyn_cast<StoreInst>(UserI)) {
5237 MemoryUses.push_back({&U, SI->getValueOperand()->
getType()});
5244 MemoryUses.push_back({&U, RMW->getValOperand()->
getType()});
5251 MemoryUses.push_back({&U, CmpX->getCompareOperand()->
getType()});
5255 if (
CallInst *CI = dyn_cast<CallInst>(UserI)) {
5256 if (CI->hasFnAttr(Attribute::Cold)) {
5265 InlineAsm *IA = dyn_cast<InlineAsm>(CI->getCalledOperand());
5276 PSI, BFI, SeenInsts))
5287 unsigned SeenInsts = 0;
5290 PSI, BFI, SeenInsts);
5298bool AddressingModeMatcher::valueAlreadyLiveAtInst(
Value *Val,
5300 Value *KnownLive2) {
5302 if (Val ==
nullptr || Val == KnownLive1 || Val == KnownLive2)
5306 if (!isa<Instruction>(Val) && !isa<Argument>(Val))
5312 if (
AllocaInst *AI = dyn_cast<AllocaInst>(Val))
5343bool AddressingModeMatcher::isProfitableToFoldIntoAddressingMode(
5345 if (IgnoreProfitability)
5363 if (valueAlreadyLiveAtInst(ScaledReg, AMBefore.
BaseReg, AMBefore.
ScaledReg))
5364 ScaledReg =
nullptr;
5368 if (!BaseReg && !ScaledReg)
5389 for (
const std::pair<Use *, Type *> &Pair : MemoryUses) {
5391 Instruction *UserI = cast<Instruction>(Pair.first->getUser());
5392 Type *AddressAccessTy = Pair.second;
5393 unsigned AS =
Address->getType()->getPointerAddressSpace();
5399 std::pair<AssertingVH<GetElementPtrInst>, int64_t> LargeOffsetGEP(
nullptr,
5401 TypePromotionTransaction::ConstRestorationPt LastKnownGood =
5402 TPT.getRestorationPoint();
5403 AddressingModeMatcher Matcher(MatchedAddrModeInsts, TLI,
TRI, LI, getDTFn,
5404 AddressAccessTy, AS, UserI, Result,
5405 InsertedInsts, PromotedInsts, TPT,
5406 LargeOffsetGEP, OptSize, PSI, BFI);
5407 Matcher.IgnoreProfitability =
true;
5408 bool Success = Matcher.matchAddr(Address, 0);
5415 TPT.rollback(LastKnownGood);
5421 MatchedAddrModeInsts.
clear();
5431 return I->getParent() != BB;
5455 Type *AccessTy,
unsigned AddrSpace) {
5467 bool PhiOrSelectSeen =
false;
5470 AddressingModeCombiner AddrModes(SQ,
Addr);
5471 TypePromotionTransaction TPT(RemovedInsts);
5472 TypePromotionTransaction::ConstRestorationPt LastKnownGood =
5473 TPT.getRestorationPoint();
5474 while (!worklist.
empty()) {
5486 if (!Visited.
insert(V).second)
5490 if (
PHINode *
P = dyn_cast<PHINode>(V)) {
5492 PhiOrSelectSeen =
true;
5496 if (
SelectInst *SI = dyn_cast<SelectInst>(V)) {
5499 PhiOrSelectSeen =
true;
5506 AddrModeInsts.
clear();
5507 std::pair<AssertingVH<GetElementPtrInst>, int64_t> LargeOffsetGEP(
nullptr,
5512 auto getDTFn = [MemoryInst,
this]() ->
const DominatorTree & {
5514 return this->getDT(*
F);
5516 ExtAddrMode NewAddrMode = AddressingModeMatcher::Match(
5517 V, AccessTy, AddrSpace, MemoryInst, AddrModeInsts, *TLI, *LI, getDTFn,
5518 *
TRI, InsertedInsts, PromotedInsts, TPT, LargeOffsetGEP, OptSize, PSI,
5526 LargeOffsetGEPMap[
GEP->getPointerOperand()].push_back(LargeOffsetGEP);
5527 LargeOffsetGEPID.
insert(std::make_pair(
GEP, LargeOffsetGEPID.
size()));
5530 NewAddrMode.OriginalValue =
V;
5531 if (!AddrModes.addNewAddrMode(NewAddrMode))
5538 if (!AddrModes.combineAddrModes()) {
5539 TPT.rollback(LastKnownGood);
5551 if (!PhiOrSelectSeen &&
none_of(AddrModeInsts, [&](
Value *V) {
5573 Type *IntPtrTy =
DL->getIntPtrType(
Addr->getType());
5576 <<
" for " << *MemoryInst <<
"\n");
5579 Addr->getType()->getPointerAddressSpace() &&
5580 !
DL->isNonIntegralPointerType(
Addr->getType())) {
5586 SunkAddr = Builder.CreatePtrToInt(SunkAddr, IntPtrTy,
"sunkaddr");
5588 Builder.CreateIntToPtr(SunkAddr,
Addr->getType(),
"sunkaddr");
5590 SunkAddr = Builder.CreatePointerCast(SunkAddr,
Addr->getType());
5597 <<
" for " << *MemoryInst <<
"\n");
5598 Value *ResultPtr =
nullptr, *ResultIndex =
nullptr;
5609 if (ResultPtr ||
AddrMode.Scale != 1)
5631 if (BaseGV !=
nullptr) {
5636 ResultPtr = Builder.CreateThreadLocalAddress(BaseGV);
5645 if (!
DL->isNonIntegralPointerType(
Addr->getType())) {
5646 if (!ResultPtr &&
AddrMode.BaseReg) {
5647 ResultPtr = Builder.CreateIntToPtr(
AddrMode.BaseReg,
Addr->getType(),
5650 }
else if (!ResultPtr &&
AddrMode.Scale == 1) {
5651 ResultPtr = Builder.CreateIntToPtr(
AddrMode.ScaledReg,
Addr->getType(),
5660 }
else if (!ResultPtr) {
5664 Builder.getPtrTy(
Addr->getType()->getPointerAddressSpace());
5673 if (
V->getType() != IntPtrTy)
5674 V = Builder.CreateIntCast(V, IntPtrTy,
true,
"sunkaddr");
5682 if (
V->getType() == IntPtrTy) {
5686 cast<IntegerType>(
V->getType())->getBitWidth() &&
5687 "We can't transform if ScaledReg is too narrow");
5688 V = Builder.CreateTrunc(V, IntPtrTy,
"sunkaddr");
5692 V = Builder.CreateMul(V, ConstantInt::get(IntPtrTy,
AddrMode.Scale),
5695 ResultIndex = Builder.CreateAdd(ResultIndex, V,
"sunkaddr");
5706 if (ResultPtr->
getType() != I8PtrTy)
5707 ResultPtr = Builder.CreatePointerCast(ResultPtr, I8PtrTy);
5708 ResultPtr = Builder.CreatePtrAdd(ResultPtr, ResultIndex,
"sunkaddr",
5716 SunkAddr = ResultPtr;
5718 if (ResultPtr->
getType() != I8PtrTy)
5719 ResultPtr = Builder.CreatePointerCast(ResultPtr, I8PtrTy);
5720 SunkAddr = Builder.CreatePtrAdd(ResultPtr, ResultIndex,
"sunkaddr",
5726 Addr->getType()->getPointerAddressSpace() &&
5727 !
DL->isNonIntegralPointerType(
Addr->getType())) {
5733 SunkAddr = Builder.CreatePtrToInt(SunkAddr, IntPtrTy,
"sunkaddr");
5735 Builder.CreateIntToPtr(SunkAddr,
Addr->getType(),
"sunkaddr");
5737 SunkAddr = Builder.CreatePointerCast(SunkAddr,
Addr->getType());
5746 PointerType *ScalePtrTy = dyn_cast_or_null<PointerType>(ScaleTy);
5747 if (
DL->isNonIntegralPointerType(
Addr->getType()) ||
5748 (BasePtrTy &&
DL->isNonIntegralPointerType(BasePtrTy)) ||
5749 (ScalePtrTy &&
DL->isNonIntegralPointerType(ScalePtrTy)) ||
5751 DL->isNonIntegralPointerType(
AddrMode.BaseGV->getType())))
5755 <<
" for " << *MemoryInst <<
"\n");
5756 Type *IntPtrTy =
DL->getIntPtrType(
Addr->getType());
5766 if (
V->getType()->isPointerTy())
5767 V = Builder.CreatePtrToInt(V, IntPtrTy,
"sunkaddr");
5768 if (
V->getType() != IntPtrTy)
5769 V = Builder.CreateIntCast(V, IntPtrTy,
true,
"sunkaddr");
5776 if (
V->getType() == IntPtrTy) {
5778 }
else if (
V->getType()->isPointerTy()) {
5779 V = Builder.CreatePtrToInt(V, IntPtrTy,
"sunkaddr");
5780 }
else if (cast<IntegerType>(IntPtrTy)->
getBitWidth() <
5781 cast<IntegerType>(
V->getType())->getBitWidth()) {
5782 V = Builder.CreateTrunc(V, IntPtrTy,
"sunkaddr");
5789 Instruction *
I = dyn_cast_or_null<Instruction>(Result);
5791 I->eraseFromParent();
5795 V = Builder.CreateMul(V, ConstantInt::get(IntPtrTy,
AddrMode.Scale),
5798 Result = Builder.CreateAdd(Result, V,
"sunkaddr");
5805 if (BaseGV !=
nullptr) {
5808 BaseGVPtr = Builder.CreateThreadLocalAddress(BaseGV);
5812 Value *
V = Builder.CreatePtrToInt(BaseGVPtr, IntPtrTy,
"sunkaddr");
5814 Result = Builder.CreateAdd(Result, V,
"sunkaddr");
5823 Result = Builder.CreateAdd(Result, V,
"sunkaddr");
5831 SunkAddr = Builder.CreateIntToPtr(Result,
Addr->getType(),
"sunkaddr");
5842 resetIteratorIfInvalidatedWhileCalling(CurInstIterator->getParent(), [&]() {
5843 RecursivelyDeleteTriviallyDeadInstructions(
5844 Repl, TLInfo, nullptr,
5845 [&](Value *V) { removeAllAssertingVHReferences(V); });
5869bool CodeGenPrepare::optimizeGatherScatterInst(
Instruction *MemoryInst,
5873 if (
const auto *
GEP = dyn_cast<GetElementPtrInst>(
Ptr)) {
5875 if (!
GEP->hasIndices())
5885 bool RewriteGEP =
false;
5887 if (Ops[0]->
getType()->isVectorTy()) {
5894 unsigned FinalIndex = Ops.size() - 1;
5899 for (
unsigned i = 1; i < FinalIndex; ++i) {
5900 auto *
C = dyn_cast<Constant>(Ops[i]);
5903 if (isa<VectorType>(
C->getType()))
5904 C =
C->getSplatValue();
5905 auto *CI = dyn_cast_or_null<ConstantInt>(
C);
5906 if (!CI || !CI->
isZero())
5913 if (Ops[FinalIndex]->
getType()->isVectorTy()) {
5915 auto *
C = dyn_cast<ConstantInt>(V);
5917 if (!
C || !
C->isZero()) {
5918 Ops[FinalIndex] =
V;
5926 if (!RewriteGEP && Ops.size() == 2)
5929 auto NumElts = cast<VectorType>(
Ptr->getType())->getElementCount();
5933 Type *SourceTy =
GEP->getSourceElementType();
5934 Type *ScalarIndexTy =
DL->getIndexType(Ops[0]->
getType()->getScalarType());
5938 if (!Ops[FinalIndex]->
getType()->isVectorTy()) {
5939 NewAddr = Builder.CreateGEP(SourceTy, Ops[0],
ArrayRef(Ops).drop_front());
5940 auto *IndexTy = VectorType::get(ScalarIndexTy, NumElts);
5942 SourceTy,
ArrayRef(Ops).drop_front());
5950 if (Ops.size() != 2) {
5956 SourceTy,
ArrayRef(Ops).drop_front());
5960 NewAddr = Builder.CreateGEP(SourceTy,
Base,
Index);
5962 }
else if (!isa<Constant>(
Ptr)) {
5969 auto NumElts = cast<VectorType>(
Ptr->getType())->getElementCount();
5974 Type *ScalarIndexTy =
DL->getIndexType(
V->getType()->getScalarType());
5975 auto *IndexTy = VectorType::get(ScalarIndexTy, NumElts);
5978 Intrinsic::masked_gather) {
5982 Intrinsic::masked_scatter);
5995 if (
Ptr->use_empty())
5997 Ptr, TLInfo,
nullptr,
5998 [&](
Value *V) { removeAllAssertingVHReferences(V); });
6005bool CodeGenPrepare::optimizeInlineAsmInst(
CallInst *CS) {
6006 bool MadeChange =
false;
6009 TM->getSubtargetImpl(*CS->
getFunction())->getRegisterInfo();
6019 OpInfo.isIndirect) {
6021 MadeChange |= optimizeMemoryInst(CS, OpVal, OpVal->
getType(), ~0u);
6034 bool IsSExt = isa<SExtInst>(FirstUser);
6038 if ((IsSExt && !isa<SExtInst>(UI)) || (!IsSExt && !isa<ZExtInst>(UI)))
6084bool CodeGenPrepare::tryToPromoteExts(
6087 unsigned CreatedInstsCost) {
6088 bool Promoted =
false;
6091 for (
auto *
I : Exts) {
6093 if (isa<LoadInst>(
I->getOperand(0))) {
6106 TypePromotionHelper::Action TPH =
6107 TypePromotionHelper::getAction(
I, InsertedInsts, *TLI, PromotedInsts);
6116 TypePromotionTransaction::ConstRestorationPt LastKnownGood =
6117 TPT.getRestorationPoint();
6119 unsigned NewCreatedInstsCost = 0;
6122 Value *PromotedVal = TPH(
I, TPT, PromotedInsts, NewCreatedInstsCost,
6123 &NewExts,
nullptr, *TLI);
6125 "TypePromotionHelper should have filtered out those cases");
6135 long long TotalCreatedInstsCost = CreatedInstsCost + NewCreatedInstsCost;
6138 TotalCreatedInstsCost =
6139 std::max((
long long)0, (TotalCreatedInstsCost - ExtCost));
6141 (TotalCreatedInstsCost > 1 ||
6143 (ExtCost == 0 && NewExts.
size() > 1))) {
6147 TPT.rollback(LastKnownGood);
6153 (void)tryToPromoteExts(TPT, NewExts, NewlyMovedExts, TotalCreatedInstsCost);
6154 bool NewPromoted =
false;
6155 for (
auto *ExtInst : NewlyMovedExts) {
6156 Instruction *MovedExt = cast<Instruction>(ExtInst);
6160 if (isa<LoadInst>(ExtOperand) &&
6165 ProfitablyMovedExts.
push_back(MovedExt);
6172 TPT.rollback(LastKnownGood);
6183bool CodeGenPrepare::mergeSExts(
Function &
F) {
6184 bool Changed =
false;
6185 for (
auto &Entry : ValToSExtendedUses) {
6186 SExts &Insts = Entry.second;
6189 if (RemovedInsts.count(Inst) || !isa<SExtInst>(Inst) ||
6192 bool inserted =
false;
6193 for (
auto &Pt : CurPts) {
6196 RemovedInsts.insert(Pt);
6197 Pt->removeFromParent();
6208 RemovedInsts.insert(Inst);
6215 CurPts.push_back(Inst);
6257bool CodeGenPrepare::splitLargeGEPOffsets() {
6258 bool Changed =
false;
6259 for (
auto &Entry : LargeOffsetGEPMap) {
6260 Value *OldBase = Entry.first;
6262 &LargeOffsetGEPs = Entry.second;
6263 auto compareGEPOffset =
6264 [&](
const std::pair<GetElementPtrInst *, int64_t> &
LHS,
6265 const std::pair<GetElementPtrInst *, int64_t> &
RHS) {
6266 if (
LHS.first ==
RHS.first)
6268 if (
LHS.second !=
RHS.second)
6269 return LHS.second <
RHS.second;
6270 return LargeOffsetGEPID[
LHS.first] < LargeOffsetGEPID[
RHS.first];
6273 llvm::sort(LargeOffsetGEPs, compareGEPOffset);
6274 LargeOffsetGEPs.
erase(
6275 std::unique(LargeOffsetGEPs.
begin(), LargeOffsetGEPs.
end()),
6276 LargeOffsetGEPs.
end());
6278 if (LargeOffsetGEPs.
front().second == LargeOffsetGEPs.
back().second)
6281 int64_t BaseOffset = LargeOffsetGEPs.
begin()->second;
6282 Value *NewBaseGEP =
nullptr;
6284 auto createNewBase = [&](int64_t BaseOffset,
Value *OldBase,
6287 Type *PtrIdxTy =
DL->getIndexType(
GEP->getType());
6289 PointerType::get(Ctx,
GEP->getType()->getPointerAddressSpace());
6293 if (
auto *BaseI = dyn_cast<Instruction>(OldBase)) {
6297 if (isa<PHINode>(BaseI))
6299 else if (
InvokeInst *Invoke = dyn_cast<InvokeInst>(BaseI)) {
6301 SplitEdge(NewBaseInsertBB, Invoke->getNormalDest(), DT.get(), LI);
6304 NewBaseInsertPt = std::next(BaseI->getIterator());
6311 IRBuilder<> NewBaseBuilder(NewBaseInsertBB, NewBaseInsertPt);
6313 Value *BaseIndex = ConstantInt::get(PtrIdxTy, BaseOffset);
6314 NewBaseGEP = OldBase;
6315 if (NewBaseGEP->
getType() != I8PtrTy)
6316 NewBaseGEP = NewBaseBuilder.CreatePointerCast(NewBaseGEP, I8PtrTy);
6318 NewBaseBuilder.CreatePtrAdd(NewBaseGEP, BaseIndex,
"splitgep");
6319 NewGEPBases.
insert(NewBaseGEP);
6325 LargeOffsetGEPs.
front().second, LargeOffsetGEPs.
back().second)) {
6326 BaseOffset = PreferBase;
6329 createNewBase(BaseOffset, OldBase, BaseGEP);
6332 auto *LargeOffsetGEP = LargeOffsetGEPs.
begin();
6333 while (LargeOffsetGEP != LargeOffsetGEPs.
end()) {
6335 int64_t
Offset = LargeOffsetGEP->second;
6336 if (
Offset != BaseOffset) {
6343 GEP->getResultElementType(),
6344 GEP->getAddressSpace())) {
6350 NewBaseGEP =
nullptr;
6355 Type *PtrIdxTy =
DL->getIndexType(
GEP->getType());
6360 createNewBase(BaseOffset, OldBase,
GEP);
6364 Value *NewGEP = NewBaseGEP;
6365 if (
Offset != BaseOffset) {
6368 NewGEP = Builder.CreatePtrAdd(NewBaseGEP,
Index);
6372 LargeOffsetGEP = LargeOffsetGEPs.
erase(LargeOffsetGEP);
6373 GEP->eraseFromParent();
6380bool CodeGenPrepare::optimizePhiType(
6387 Type *PhiTy =
I->getType();
6388 Type *ConvertTy =
nullptr;
6390 (!
I->getType()->isIntegerTy() && !
I->getType()->isFloatingPointTy()))
6406 bool AnyAnchored =
false;
6408 while (!Worklist.
empty()) {
6411 if (
auto *Phi = dyn_cast<PHINode>(II)) {
6413 for (
Value *V :
Phi->incoming_values()) {
6414 if (
auto *OpPhi = dyn_cast<PHINode>(V)) {
6415 if (!PhiNodes.
count(OpPhi)) {
6416 if (!Visited.
insert(OpPhi).second)
6421 }
else if (
auto *OpLoad = dyn_cast<LoadInst>(V)) {
6422 if (!OpLoad->isSimple())
6424 if (Defs.
insert(OpLoad).second)
6426 }
else if (
auto *OpEx = dyn_cast<ExtractElementInst>(V)) {
6427 if (Defs.
insert(OpEx).second)
6429 }
else if (
auto *OpBC = dyn_cast<BitCastInst>(V)) {
6431 ConvertTy = OpBC->getOperand(0)->getType();
6432 if (OpBC->getOperand(0)->getType() != ConvertTy)
6434 if (Defs.
insert(OpBC).second) {
6436 AnyAnchored |= !isa<LoadInst>(OpBC->getOperand(0)) &&
6437 !isa<ExtractElementInst>(OpBC->getOperand(0));
6439 }
else if (
auto *OpC = dyn_cast<ConstantData>(V))
6448 if (
auto *OpPhi = dyn_cast<PHINode>(V)) {
6449 if (!PhiNodes.
count(OpPhi)) {
6450 if (Visited.
count(OpPhi))
6456 }
else if (
auto *OpStore = dyn_cast<StoreInst>(V)) {
6457 if (!OpStore->isSimple() || OpStore->getOperand(0) != II)
6459 Uses.insert(OpStore);
6460 }
else if (
auto *OpBC = dyn_cast<BitCastInst>(V)) {
6462 ConvertTy = OpBC->getType();
6463 if (OpBC->getType() != ConvertTy)
6467 any_of(OpBC->users(), [](
User *U) { return !isa<StoreInst>(U); });
6474 if (!ConvertTy || !AnyAnchored ||
6478 LLVM_DEBUG(
dbgs() <<
"Converting " << *
I <<
"\n and connected nodes to "
6479 << *ConvertTy <<
"\n");
6487 if (isa<BitCastInst>(
D)) {
6488 ValMap[
D] =
D->getOperand(0);
6492 ValMap[
D] =
new BitCastInst(
D, ConvertTy,
D->getName() +
".bc", insertPt);
6497 Phi->getName() +
".tc",
Phi->getIterator());
6499 for (
PHINode *Phi : PhiNodes) {
6500 PHINode *NewPhi = cast<PHINode>(ValMap[Phi]);
6501 for (
int i = 0, e =
Phi->getNumIncomingValues(); i < e; i++)
6503 Phi->getIncomingBlock(i));
6508 if (isa<BitCastInst>(U)) {
6512 U->setOperand(0,
new BitCastInst(ValMap[
U->getOperand(0)], PhiTy,
"bc",
6519 DeletedInstrs.
insert(Phi);
6523bool CodeGenPrepare::optimizePhiTypes(
Function &
F) {
6527 bool Changed =
false;
6533 for (
auto &Phi : BB.
phis())
6534 Changed |= optimizePhiType(&Phi, Visited, DeletedInstrs);
6537 for (
auto *
I : DeletedInstrs) {
6539 I->eraseFromParent();
6547bool CodeGenPrepare::canFormExtLd(
6550 for (
auto *MovedExtInst : MovedExts) {
6551 if (isa<LoadInst>(MovedExtInst->getOperand(0))) {
6552 LI = cast<LoadInst>(MovedExtInst->getOperand(0));
6553 Inst = MovedExtInst;
6605bool CodeGenPrepare::optimizeExt(
Instruction *&Inst) {
6606 bool AllowPromotionWithoutCommonHeader =
false;
6611 *Inst, AllowPromotionWithoutCommonHeader);
6612 TypePromotionTransaction TPT(RemovedInsts);
6613 TypePromotionTransaction::ConstRestorationPt LastKnownGood =
6614 TPT.getRestorationPoint();
6619 bool HasPromoted = tryToPromoteExts(TPT, Exts, SpeculativelyMovedExts);
6627 if (canFormExtLd(SpeculativelyMovedExts, LI, ExtFedByLoad, HasPromoted)) {
6628 assert(LI && ExtFedByLoad &&
"Expect a valid load and extension");
6633 Inst = ExtFedByLoad;
6638 if (ATPConsiderable &&
6639 performAddressTypePromotion(Inst, AllowPromotionWithoutCommonHeader,
6640 HasPromoted, TPT, SpeculativelyMovedExts))
6643 TPT.rollback(LastKnownGood);
6652bool CodeGenPrepare::performAddressTypePromotion(
6653 Instruction *&Inst,
bool AllowPromotionWithoutCommonHeader,
6654 bool HasPromoted, TypePromotionTransaction &TPT,
6656 bool Promoted =
false;
6658 bool AllSeenFirst =
true;
6659 for (
auto *
I : SpeculativelyMovedExts) {
6660 Value *HeadOfChain =
I->getOperand(0);
6662 SeenChainsForSExt.
find(HeadOfChain);
6665 if (AlreadySeen != SeenChainsForSExt.
end()) {
6666 if (AlreadySeen->second !=
nullptr)
6667 UnhandledExts.
insert(AlreadySeen->second);
6668 AllSeenFirst =
false;
6672 if (!AllSeenFirst || (AllowPromotionWithoutCommonHeader &&
6673 SpeculativelyMovedExts.size() == 1)) {
6677 for (
auto *
I : SpeculativelyMovedExts) {
6678 Value *HeadOfChain =
I->getOperand(0);
6679 SeenChainsForSExt[HeadOfChain] =
nullptr;
6680 ValToSExtendedUses[HeadOfChain].push_back(
I);
6683 Inst = SpeculativelyMovedExts.pop_back_val();
6688 for (
auto *
I : SpeculativelyMovedExts) {
6689 Value *HeadOfChain =
I->getOperand(0);
6690 SeenChainsForSExt[HeadOfChain] = Inst;
6695 if (!AllSeenFirst && !UnhandledExts.
empty())
6696 for (
auto *VisitedSExt : UnhandledExts) {
6697 if (RemovedInsts.count(VisitedSExt))
6699 TypePromotionTransaction TPT(RemovedInsts);
6703 bool HasPromoted = tryToPromoteExts(TPT, Exts, Chains);
6707 for (
auto *
I : Chains) {
6708 Value *HeadOfChain =
I->getOperand(0);
6710 SeenChainsForSExt[HeadOfChain] =
nullptr;
6711 ValToSExtendedUses[HeadOfChain].push_back(
I);
6722 Value *Src =
I->getOperand(0);
6723 if (Src->hasOneUse())
6732 if (!isa<Instruction>(Src) || DefBB != cast<Instruction>(Src)->
getParent())
6735 bool DefIsLiveOut =
false;
6736 for (
User *U :
I->users()) {
6741 if (UserBB == DefBB)
6743 DefIsLiveOut =
true;
6750 for (
User *U : Src->users()) {
6753 if (UserBB == DefBB)
6757 if (isa<PHINode>(UI) || isa<LoadInst>(UI) || isa<StoreInst>(UI))
6764 bool MadeChange =
false;
6765 for (
Use &U : Src->uses()) {
6770 if (UserBB == DefBB)
6774 Instruction *&InsertedTrunc = InsertedTruncs[UserBB];
6776 if (!InsertedTrunc) {
6779 InsertedTrunc =
new TruncInst(
I, Src->getType(),
"");
6781 InsertedInsts.insert(InsertedTrunc);
6844bool CodeGenPrepare::optimizeLoadExt(
LoadInst *Load) {
6845 if (!
Load->isSimple() || !
Load->getType()->isIntOrPtrTy())
6849 if (
Load->hasOneUse() &&
6850 InsertedInsts.count(cast<Instruction>(*
Load->user_begin())))
6858 for (
auto *U :
Load->users())
6859 WorkList.
push_back(cast<Instruction>(U));
6870 while (!WorkList.
empty()) {
6874 if (!Visited.
insert(
I).second)
6878 if (
auto *Phi = dyn_cast<PHINode>(
I)) {
6879 for (
auto *U :
Phi->users())
6880 WorkList.
push_back(cast<Instruction>(U));
6884 switch (
I->getOpcode()) {
6885 case Instruction::And: {
6886 auto *AndC = dyn_cast<ConstantInt>(
I->getOperand(1));
6889 APInt AndBits = AndC->getValue();
6890 DemandBits |= AndBits;
6892 if (AndBits.
ugt(WidestAndBits))
6893 WidestAndBits = AndBits;
6894 if (AndBits == WidestAndBits &&
I->getOperand(0) == Load)
6899 case Instruction::Shl: {
6900 auto *ShlC = dyn_cast<ConstantInt>(
I->getOperand(1));
6904 DemandBits.setLowBits(
BitWidth - ShiftAmt);
6908 case Instruction::Trunc: {
6911 DemandBits.setLowBits(TruncBitWidth);
6920 uint32_t ActiveBits = DemandBits.getActiveBits();
6932 if (ActiveBits <= 1 || !DemandBits.isMask(ActiveBits) ||
6933 WidestAndBits != DemandBits)
6946 auto *NewAnd = cast<Instruction>(
6947 Builder.CreateAnd(Load, ConstantInt::get(Ctx, DemandBits)));
6950 InsertedInsts.insert(NewAnd);
6955 NewAnd->setOperand(0, Load);
6958 for (
auto *
And : AndsToMaybeRemove)
6961 if (cast<ConstantInt>(
And->getOperand(1))->getValue() == DemandBits) {
6963 if (&*CurInstIterator ==
And)
6964 CurInstIterator = std::next(
And->getIterator());
6965 And->eraseFromParent();
6976 auto *
I = dyn_cast<Instruction>(V);
6998 uint64_t Max = std::max(TrueWeight, FalseWeight);
6999 uint64_t Sum = TrueWeight + FalseWeight;
7007 CmpInst *Cmp = dyn_cast<CmpInst>(SI->getCondition());
7012 if (!Cmp || !Cmp->hasOneUse())
7033 for (
SelectInst *DefSI = SI; DefSI !=
nullptr && Selects.
count(DefSI);
7034 DefSI = dyn_cast<SelectInst>(V)) {
7035 assert(DefSI->getCondition() == SI->getCondition() &&
7036 "The condition of DefSI does not match with SI");
7037 V = (isTrue ? DefSI->getTrueValue() : DefSI->getFalseValue());
7040 assert(V &&
"Failed to get select true/false value");
7069 Value *NewTVal = Builder.CreateBinOp(Opcode, Shift->
getOperand(0), TVal);
7070 Value *NewFVal = Builder.CreateBinOp(Opcode, Shift->
getOperand(0), FVal);
7071 Value *NewSel = Builder.CreateSelect(
Cond, NewTVal, NewFVal);
7077bool CodeGenPrepare::optimizeFunnelShift(
IntrinsicInst *Fsh) {
7079 assert((Opcode == Intrinsic::fshl || Opcode == Intrinsic::fshr) &&
7080 "Expected a funnel shift");
7104 Value *NewTVal = Builder.CreateIntrinsic(Opcode, Ty, {
X,
Y, TVal});
7105 Value *NewFVal = Builder.CreateIntrinsic(Opcode, Ty, {
X,
Y, FVal});
7106 Value *NewSel = Builder.CreateSelect(
Cond, NewTVal, NewFVal);
7114bool CodeGenPrepare::optimizeSelectInst(
SelectInst *SI) {
7126 It !=
SI->getParent()->
end(); ++It) {
7128 if (
I &&
SI->getCondition() ==
I->getCondition()) {
7138 CurInstIterator = std::next(LastSI->
getIterator());
7143 fixupDbgVariableRecordsOnInst(*SI);
7145 bool VectorCond = !
SI->getCondition()->getType()->isIntegerTy(1);
7148 if (VectorCond ||
SI->getMetadata(LLVMContext::MD_unpredictable))
7152 if (
SI->getType()->isVectorTy())
7153 SelectKind = TargetLowering::ScalarCondVectorVal;
7155 SelectKind = TargetLowering::ScalarValSelect;
7198 TrueInstrs.
push_back(cast<Instruction>(V));
7200 FalseInstrs.
push_back(cast<Instruction>(V));
7208 SplitPt.setHeadBit(
true);
7211 auto *CondFr =
IB.CreateFreeze(
SI->getCondition(),
SI->getName() +
".frozen");
7218 if (TrueInstrs.
size() == 0) {
7220 CondFr, SplitPt,
false,
nullptr,
nullptr, LI));
7222 EndBlock = cast<BasicBlock>(FalseBranch->
getOperand(0));
7223 }
else if (FalseInstrs.
size() == 0) {
7225 CondFr, SplitPt,
false,
nullptr,
nullptr, LI));
7227 EndBlock = cast<BasicBlock>(TrueBranch->
getOperand(0));
7232 nullptr,
nullptr, LI);
7233 TrueBranch = cast<BranchInst>(ThenTerm);
7234 FalseBranch = cast<BranchInst>(ElseTerm);
7237 EndBlock = cast<BasicBlock>(TrueBranch->
getOperand(0));
7240 EndBlock->
setName(
"select.end");
7242 TrueBlock->
setName(
"select.true.sink");
7244 FalseBlock->
setName(FalseInstrs.
size() == 0 ?
"select.false"
7245 :
"select.false.sink");
7249 FreshBBs.
insert(TrueBlock);
7251 FreshBBs.
insert(FalseBlock);
7252 FreshBBs.
insert(EndBlock);
7255 BFI->setBlockFreq(EndBlock,
BFI->getBlockFreq(StartBlock));
7257 static const unsigned MD[] = {
7258 LLVMContext::MD_prof, LLVMContext::MD_unpredictable,
7259 LLVMContext::MD_make_implicit, LLVMContext::MD_dbg};
7265 I->moveBefore(TrueBranch);
7267 I->moveBefore(FalseBranch);
7273 if (TrueBlock ==
nullptr)
7274 TrueBlock = StartBlock;
7275 else if (FalseBlock ==
nullptr)
7276 FalseBlock = StartBlock;
7279 INS.
insert(ASI.begin(), ASI.end());
7293 SI->eraseFromParent();
7295 ++NumSelectsExpanded;
7299 CurInstIterator = StartBlock->
end();
7315 auto *SVIVecType = cast<FixedVectorType>(SVI->
getType());
7318 "Expected a type of the same size!");
7324 Builder.SetInsertPoint(SVI);
7325 Value *BC1 = Builder.CreateBitCast(
7326 cast<Instruction>(SVI->
getOperand(0))->getOperand(1), NewType);
7327 Value *Shuffle = Builder.CreateVectorSplat(NewVecType->getNumElements(), BC1);
7328 Value *BC2 = Builder.CreateBitCast(Shuffle, SVIVecType);
7332 SVI, TLInfo,
nullptr,
7333 [&](
Value *V) { removeAllAssertingVHReferences(V); });
7337 if (
auto *BCI = dyn_cast<Instruction>(BC1))
7338 if (
auto *
Op = dyn_cast<Instruction>(BCI->
getOperand(0)))
7339 if (BCI->
getParent() !=
Op->getParent() && !isa<PHINode>(
Op) &&
7340 !
Op->isTerminator() && !
Op->isEHPad())
7346bool CodeGenPrepare::tryToSinkFreeOperands(
Instruction *
I) {
7358 bool Changed =
false;
7362 unsigned long InstNumber = 0;
7363 for (
const auto &
I : *TargetBB)
7364 InstOrdering[&
I] = InstNumber++;
7367 auto *UI = cast<Instruction>(
U->get());
7368 if (isa<PHINode>(UI))
7371 if (InstOrdering[UI] < InstOrdering[InsertPoint])
7380 for (
Use *U : ToReplace) {
7381 auto *UI = cast<Instruction>(
U->get());
7388 auto *OpDef = dyn_cast<Instruction>(NI->
getOperand(
I));
7391 FreshBBs.
insert(OpDef->getParent());
7395 NewInstructions[UI] = NI;
7400 InsertedInsts.insert(NI);
7406 if (NewInstructions.
count(OldI))
7407 NewInstructions[OldI]->setOperand(
U->getOperandNo(), NI);
7414 for (
auto *
I : MaybeDead) {
7415 if (!
I->hasNUsesOrMore(1)) {
7417 I->eraseFromParent();
7424bool CodeGenPrepare::optimizeSwitchType(
SwitchInst *SI) {
7432 if (RegWidth <= cast<IntegerType>(OldType)->
getBitWidth())
7450 ExtType = Instruction::SExt;
7452 if (
auto *Arg = dyn_cast<Argument>(
Cond)) {
7453 if (Arg->hasSExtAttr())
7454 ExtType = Instruction::SExt;
7455 if (Arg->hasZExtAttr())
7456 ExtType = Instruction::ZExt;
7462 SI->setCondition(ExtInst);
7463 for (
auto Case :
SI->cases()) {
7464 const APInt &NarrowConst = Case.getCaseValue()->getValue();
7465 APInt WideConst = (ExtType == Instruction::ZExt)
7466 ? NarrowConst.
zext(RegWidth)
7467 : NarrowConst.
sext(RegWidth);
7468 Case.setValue(ConstantInt::get(Context, WideConst));
7474bool CodeGenPrepare::optimizeSwitchPhiConstants(
SwitchInst *SI) {
7481 Value *Condition =
SI->getCondition();
7483 if (isa<ConstantInt>(*Condition))
7486 bool Changed =
false;
7492 BasicBlock *CaseBB = Case.getCaseSuccessor();
7495 bool CheckedForSinglePred =
false;
7497 Type *PHIType =
PHI.getType();
7505 if (PHIType == ConditionType || TryZExt) {
7507 bool SkipCase =
false;
7508 Value *Replacement =
nullptr;
7509 for (
unsigned I = 0, E =
PHI.getNumIncomingValues();
I != E;
I++) {
7510 Value *PHIValue =
PHI.getIncomingValue(
I);
7511 if (PHIValue != CaseValue) {
7514 ConstantInt *PHIValueInt = dyn_cast<ConstantInt>(PHIValue);
7520 if (
PHI.getIncomingBlock(
I) != SwitchBB)
7525 if (!CheckedForSinglePred) {
7526 CheckedForSinglePred =
true;
7527 if (
SI->findCaseDest(CaseBB) ==
nullptr) {
7533 if (Replacement ==
nullptr) {
7534 if (PHIValue == CaseValue) {
7535 Replacement = Condition;
7538 Replacement = Builder.CreateZExt(Condition, PHIType);
7541 PHI.setIncomingValue(
I, Replacement);
7552bool CodeGenPrepare::optimizeSwitchInst(
SwitchInst *SI) {
7553 bool Changed = optimizeSwitchType(SI);
7554 Changed |= optimizeSwitchPhiConstants(SI);
7575class VectorPromoteHelper {
7592 unsigned StoreExtractCombineCost;
7601 if (InstsToBePromoted.
empty())
7603 return InstsToBePromoted.
back();
7609 unsigned getTransitionOriginalValueIdx()
const {
7610 assert(isa<ExtractElementInst>(Transition) &&
7611 "Other kind of transitions are not supported yet");
7618 unsigned getTransitionIdx()
const {
7619 assert(isa<ExtractElementInst>(Transition) &&
7620 "Other kind of transitions are not supported yet");
7628 Type *getTransitionType()
const {
7643 bool isProfitableToPromote() {
7644 Value *ValIdx = Transition->
getOperand(getTransitionOriginalValueIdx());
7645 unsigned Index = isa<ConstantInt>(ValIdx)
7646 ? cast<ConstantInt>(ValIdx)->getZExtValue()
7648 Type *PromotedType = getTransitionType();
7651 unsigned AS =
ST->getPointerAddressSpace();
7669 for (
const auto &Inst : InstsToBePromoted) {
7675 bool IsArg0Constant = isa<UndefValue>(Arg0) || isa<ConstantInt>(Arg0) ||
7676 isa<ConstantFP>(Arg0);
7689 dbgs() <<
"Estimated cost of computation to be promoted:\nScalar: "
7690 << ScalarCost <<
"\nVector: " << VectorCost <<
'\n');
7691 return ScalarCost > VectorCost;
7703 unsigned ExtractIdx = std::numeric_limits<unsigned>::max();
7708 if (
ConstantInt *CstVal = dyn_cast<ConstantInt>(ValExtractIdx))
7714 ElementCount EC = cast<VectorType>(getTransitionType())->getElementCount();
7718 if (!
EC.isScalable()) {
7721 for (
unsigned Idx = 0;
Idx !=
EC.getKnownMinValue(); ++
Idx) {
7722 if (
Idx == ExtractIdx)
7730 "Generate scalable vector for non-splat is unimplemented");
7736 unsigned OperandIdx) {
7739 if (OperandIdx != 1)
7741 switch (
Use->getOpcode()) {
7744 case Instruction::SDiv:
7745 case Instruction::UDiv:
7746 case Instruction::SRem:
7747 case Instruction::URem:
7749 case Instruction::FDiv:
7750 case Instruction::FRem:
7751 return !
Use->hasNoNaNs();
7759 unsigned CombineCost)
7760 :
DL(
DL), TLI(TLI),
TTI(
TTI), Transition(Transition),
7761 StoreExtractCombineCost(CombineCost) {
7762 assert(Transition &&
"Do not know how to promote null");
7766 bool canPromote(
const Instruction *ToBePromoted)
const {
7768 return isa<BinaryOperator>(ToBePromoted);
7773 bool shouldPromote(
const Instruction *ToBePromoted)
const {
7777 const Value *Val =
U.get();
7778 if (Val == getEndOfTransition()) {
7782 if (canCauseUndefinedBehavior(ToBePromoted,
U.getOperandNo()))
7786 if (!isa<ConstantInt>(Val) && !isa<UndefValue>(Val) &&
7787 !isa<ConstantFP>(Val))
7796 ISDOpcode, TLI.
getValueType(DL, getTransitionType(),
true));
7805 void enqueueForPromotion(
Instruction *ToBePromoted) {
7806 InstsToBePromoted.push_back(ToBePromoted);
7810 void recordCombineInstruction(
Instruction *ToBeCombined) {
7812 CombineInst = ToBeCombined;
7822 if (InstsToBePromoted.empty() || !CombineInst)
7830 for (
auto &ToBePromoted : InstsToBePromoted)
7831 promoteImpl(ToBePromoted);
7832 InstsToBePromoted.clear();
7839void VectorPromoteHelper::promoteImpl(
Instruction *ToBePromoted) {
7849 "The type of the result of the transition does not match "
7854 Type *TransitionTy = getTransitionType();
7861 Value *NewVal =
nullptr;
7862 if (Val == Transition)
7863 NewVal = Transition->
getOperand(getTransitionOriginalValueIdx());
7864 else if (isa<UndefValue>(Val) || isa<ConstantInt>(Val) ||
7865 isa<ConstantFP>(Val)) {
7868 cast<Constant>(Val),
7869 isa<UndefValue>(Val) ||
7870 canCauseUndefinedBehavior(ToBePromoted,
U.getOperandNo()));
7874 ToBePromoted->
setOperand(
U.getOperandNo(), NewVal);
7877 Transition->
setOperand(getTransitionOriginalValueIdx(), ToBePromoted);
7883bool CodeGenPrepare::optimizeExtractElementInst(
Instruction *Inst) {
7884 unsigned CombineCost = std::numeric_limits<unsigned>::max();
7899 LLVM_DEBUG(
dbgs() <<
"Found an interesting transition: " << *Inst <<
'\n');
7900 VectorPromoteHelper VPH(*
DL, *TLI, *
TTI, Inst, CombineCost);
7907 if (ToBePromoted->
getParent() != Parent) {
7908 LLVM_DEBUG(
dbgs() <<
"Instruction to promote is in a different block ("
7910 <<
") than the transition (" << Parent->
getName()
7915 if (VPH.canCombine(ToBePromoted)) {
7917 <<
"will be combined with: " << *ToBePromoted <<
'\n');
7918 VPH.recordCombineInstruction(ToBePromoted);
7919 bool Changed = VPH.promote();
7920 NumStoreExtractExposed += Changed;
7925 if (!VPH.canPromote(ToBePromoted) || !VPH.shouldPromote(ToBePromoted))
7928 LLVM_DEBUG(
dbgs() <<
"Promoting is possible... Enqueue for promotion!\n");
7930 VPH.enqueueForPromotion(ToBePromoted);
7931 Inst = ToBePromoted;
7971 Type *StoreType = SI.getValueOperand()->getType();
7980 if (!
DL.typeSizeEqualsStoreSize(StoreType) ||
7981 DL.getTypeSizeInBits(StoreType) == 0)
7984 unsigned HalfValBitSize =
DL.getTypeSizeInBits(StoreType) / 2;
7986 if (!
DL.typeSizeEqualsStoreSize(SplitStoreType))
7990 if (SI.isVolatile())
8002 if (!
match(SI.getValueOperand(),
8009 if (!
LValue->getType()->isIntegerTy() ||
8010 DL.getTypeSizeInBits(
LValue->getType()) > HalfValBitSize ||
8012 DL.getTypeSizeInBits(HValue->
getType()) > HalfValBitSize)
8017 auto *LBC = dyn_cast<BitCastInst>(
LValue);
8018 auto *HBC = dyn_cast<BitCastInst>(HValue);
8032 if (LBC && LBC->getParent() != SI.getParent())
8034 if (HBC && HBC->getParent() != SI.getParent())
8035 HValue = Builder.
CreateBitCast(HBC->getOperand(0), HBC->getType());
8037 bool IsLE = SI.getModule()->getDataLayout().isLittleEndian();
8038 auto CreateSplitStore = [&](
Value *V,
bool Upper) {
8041 Align Alignment = SI.getAlign();
8042 const bool IsOffsetStore = (IsLE &&
Upper) || (!IsLE && !
Upper);
8043 if (IsOffsetStore) {
8045 SplitStoreType,
Addr,
8056 CreateSplitStore(
LValue,
false);
8057 CreateSplitStore(HValue,
true);
8060 SI.eraseFromParent();
8068 return GEP->getNumOperands() == 2 &&
I.isSequential() &&
8069 isa<ConstantInt>(
GEP->getOperand(1));
8147 if (!isa<Instruction>(GEPIOp))
8149 auto *GEPIOpI = cast<Instruction>(GEPIOp);
8150 if (GEPIOpI->getParent() != SrcBlock)
8155 if (auto *I = dyn_cast<Instruction>(Usr)) {
8156 if (I->getParent() != SrcBlock) {
8164 std::vector<GetElementPtrInst *> UGEPIs;
8171 if (!isa<Instruction>(Usr))
8173 auto *UI = cast<Instruction>(Usr);
8178 if (!isa<GetElementPtrInst>(Usr))
8180 auto *UGEPI = cast<GetElementPtrInst>(Usr);
8186 if (UGEPI->getOperand(0) != GEPIOp)
8188 if (UGEPI->getSourceElementType() != GEPI->getSourceElementType())
8190 if (GEPIIdx->getType() !=
8191 cast<ConstantInt>(UGEPI->getOperand(1))->getType())
8193 ConstantInt *UGEPIIdx = cast<ConstantInt>(UGEPI->getOperand(1));
8198 UGEPIs.push_back(UGEPI);
8200 if (UGEPIs.size() == 0)
8204 ConstantInt *UGEPIIdx = cast<ConstantInt>(UGEPI->getOperand(1));
8213 UGEPI->setOperand(0, GEPI);
8214 ConstantInt *UGEPIIdx = cast<ConstantInt>(UGEPI->getOperand(1));
8215 Constant *NewUGEPIIdx = ConstantInt::get(
8216 GEPIIdx->getType(), UGEPIIdx->
getValue() - GEPIIdx->getValue());
8217 UGEPI->setOperand(1, NewUGEPIIdx);
8220 if (!GEPI->isInBounds()) {
8221 UGEPI->setIsInBounds(
false);
8228 return cast<Instruction>(Usr)->getParent() != SrcBlock;
8230 "GEPIOp is used outside SrcBlock");
8250 ICmpInst *Cmp = dyn_cast<ICmpInst>(Branch->getCondition());
8251 if (!Cmp || !isa<ConstantInt>(Cmp->getOperand(1)) || !Cmp->hasOneUse())
8254 Value *
X = Cmp->getOperand(0);
8255 APInt CmpC = cast<ConstantInt>(Cmp->getOperand(1))->getValue();
8257 for (
auto *U :
X->users()) {
8261 (UI->
getParent() != Branch->getParent() &&
8262 UI->
getParent() != Branch->getSuccessor(0) &&
8263 UI->
getParent() != Branch->getSuccessor(1)) ||
8264 (UI->
getParent() != Branch->getParent() &&
8268 if (CmpC.
isPowerOf2() && Cmp->getPredicate() == ICmpInst::ICMP_ULT &&
8271 if (UI->
getParent() != Branch->getParent())
8274 ConstantInt::get(UI->
getType(), 0));
8276 LLVM_DEBUG(
dbgs() <<
" to compare on zero: " << *NewCmp <<
"\n");
8280 if (Cmp->isEquality() &&
8284 if (UI->
getParent() != Branch->getParent())
8287 ConstantInt::get(UI->
getType(), 0));
8289 LLVM_DEBUG(
dbgs() <<
" to compare on zero: " << *NewCmp <<
"\n");
8297bool CodeGenPrepare::optimizeInst(
Instruction *
I, ModifyDT &ModifiedDT) {
8298 bool AnyChange =
false;
8299 AnyChange = fixupDbgVariableRecordsOnInst(*
I);
8303 if (InsertedInsts.count(
I))
8307 if (
PHINode *
P = dyn_cast<PHINode>(
I)) {
8312 LargeOffsetGEPMap.erase(
P);
8314 P->eraseFromParent();
8321 if (
CastInst *CI = dyn_cast<CastInst>(
I)) {
8334 if ((isa<UIToFPInst>(
I) || isa<FPToUIInst>(
I) || isa<TruncInst>(
I)) &&
8336 I, LI->getLoopFor(
I->getParent()), *
TTI))
8339 if (isa<ZExtInst>(
I) || isa<SExtInst>(
I)) {
8344 TargetLowering::TypeExpandInteger) {
8348 I, LI->getLoopFor(
I->getParent()), *
TTI))
8351 bool MadeChange = optimizeExt(
I);
8352 return MadeChange | optimizeExtUses(
I);
8358 if (
auto *Cmp = dyn_cast<CmpInst>(
I))
8359 if (optimizeCmp(Cmp, ModifiedDT))
8362 if (
LoadInst *LI = dyn_cast<LoadInst>(
I)) {
8363 LI->
setMetadata(LLVMContext::MD_invariant_group,
nullptr);
8364 bool Modified = optimizeLoadExt(LI);
8370 if (
StoreInst *SI = dyn_cast<StoreInst>(
I)) {
8373 SI->setMetadata(LLVMContext::MD_invariant_group,
nullptr);
8374 unsigned AS =
SI->getPointerAddressSpace();
8375 return optimizeMemoryInst(
I,
SI->getOperand(1),
8376 SI->getOperand(0)->getType(), AS);
8380 unsigned AS = RMW->getPointerAddressSpace();
8381 return optimizeMemoryInst(
I, RMW->getPointerOperand(), RMW->getType(), AS);
8385 unsigned AS = CmpX->getPointerAddressSpace();
8386 return optimizeMemoryInst(
I, CmpX->getPointerOperand(),
8387 CmpX->getCompareOperand()->getType(), AS);
8397 if (BinOp && (BinOp->
getOpcode() == Instruction::AShr ||
8398 BinOp->
getOpcode() == Instruction::LShr)) {
8406 if (GEPI->hasAllZeroIndices()) {
8409 GEPI->getName(), GEPI->getIterator());
8410 NC->setDebugLoc(GEPI->getDebugLoc());
8413 GEPI, TLInfo,
nullptr,
8414 [&](
Value *V) { removeAllAssertingVHReferences(V); });
8416 optimizeInst(
NC, ModifiedDT);
8428 if (
ICmpInst *II = dyn_cast<ICmpInst>(FI->getOperand(0)))
8430 else if (
FCmpInst *
F = dyn_cast<FCmpInst>(FI->getOperand(0)))
8431 CmpI =
F->getFastMathFlags().none() ?
F :
nullptr;
8435 bool Const0 = isa<ConstantInt>(Op0) || isa<ConstantFP>(Op0) ||
8436 isa<ConstantPointerNull>(Op0);
8437 bool Const1 = isa<ConstantInt>(Op1) || isa<ConstantFP>(Op1) ||
8438 isa<ConstantPointerNull>(Op1);
8439 if (Const0 || Const1) {
8440 if (!Const0 || !Const1) {
8446 FI->eraseFromParent();
8453 if (tryToSinkFreeOperands(
I))
8456 switch (
I->getOpcode()) {
8457 case Instruction::Shl:
8458 case Instruction::LShr:
8459 case Instruction::AShr:
8460 return optimizeShiftInst(cast<BinaryOperator>(
I));
8461 case Instruction::Call:
8463 case Instruction::Select:
8464 return optimizeSelectInst(cast<SelectInst>(
I));
8465 case Instruction::ShuffleVector:
8466 return optimizeShuffleVectorInst(cast<ShuffleVectorInst>(
I));
8467 case Instruction::Switch:
8468 return optimizeSwitchInst(cast<SwitchInst>(
I));
8469 case Instruction::ExtractElement:
8470 return optimizeExtractElementInst(cast<ExtractElementInst>(
I));
8471 case Instruction::Br:
8472 return optimizeBranch(cast<BranchInst>(
I), *TLI, FreshBBs, IsHugeFunc);
8481 if (!
I.getType()->isIntegerTy() ||
8492 &
I, TLInfo,
nullptr,
8493 [&](
Value *V) { removeAllAssertingVHReferences(V); });
8500bool CodeGenPrepare::optimizeBlock(
BasicBlock &BB, ModifyDT &ModifiedDT) {
8502 bool MadeChange =
false;
8505 CurInstIterator = BB.
begin();
8506 ModifiedDT = ModifyDT::NotModifyDT;
8507 while (CurInstIterator != BB.
end()) {
8508 MadeChange |= optimizeInst(&*CurInstIterator++, ModifiedDT);
8509 if (ModifiedDT != ModifyDT::NotModifyDT) {
8522 }
while (ModifiedDT == ModifyDT::ModifyInstDT);
8524 bool MadeBitReverse =
true;
8525 while (MadeBitReverse) {
8526 MadeBitReverse =
false;
8528 if (makeBitReverse(
I)) {
8529 MadeBitReverse = MadeChange =
true;
8534 MadeChange |= dupRetToEnableTailCallOpts(&BB, ModifiedDT);
8546 bool AnyChange =
false;
8549 for (
Value *Location : LocationOps) {
8565bool CodeGenPrepare::fixupDbgVariableRecordsOnInst(
Instruction &
I) {
8566 bool AnyChange =
false;
8568 AnyChange |= fixupDbgVariableRecord(DVR);
8575 if (DVR.
Type != DbgVariableRecord::LocationType::Value &&
8576 DVR.
Type != DbgVariableRecord::LocationType::Assign)
8580 bool AnyChange =
false;
8583 for (
Value *Location : LocationOps) {
8601 if (isa<PHINode>(VI))
8602 DVI->
insertBefore(&*VI->getParent()->getFirstInsertionPt());
8610 if (isa<PHINode>(VI))
8621bool CodeGenPrepare::placeDbgValues(
Function &
F) {
8622 bool MadeChange =
false;
8625 auto DbgProcessor = [&](
auto *DbgItem,
Instruction *Position) {
8627 for (
Value *V : DbgItem->location_ops())
8628 if (
Instruction *VI = dyn_cast_or_null<Instruction>(V))
8636 if (
VI->isTerminator())
8641 if (isa<PHINode>(VI) &&
VI->getParent()->getTerminator()->isEHPad())
8652 if (VIs.size() > 1) {
8655 <<
"Unable to find valid location for Debug Value, undefing:\n"
8657 DbgItem->setKillLocation();
8662 << *DbgItem <<
' ' << *VI);
8674 DbgProcessor(DVI, DVI);
8682 if (DVR.
Type != DbgVariableRecord::LocationType::Value)
8684 DbgProcessor(&DVR, &
Insn);
8695bool CodeGenPrepare::placePseudoProbes(
Function &
F) {
8696 bool MadeChange =
false;
8699 auto FirstInst =
Block.getFirstInsertionPt();
8700 while (FirstInst !=
Block.end() && FirstInst->isDebugOrPseudoInst())
8704 while (
I !=
Block.end()) {
8705 if (
auto *II = dyn_cast<PseudoProbeInst>(
I++)) {
8716 uint64_t NewMax = (NewTrue > NewFalse) ? NewTrue : NewFalse;
8717 uint32_t Scale = (NewMax / std::numeric_limits<uint32_t>::max()) + 1;
8718 NewTrue = NewTrue / Scale;
8719 NewFalse = NewFalse / Scale;
8744bool CodeGenPrepare::splitBranchCondition(
Function &
F, ModifyDT &ModifiedDT) {
8748 bool MadeChange =
false;
8749 for (
auto &BB :
F) {
8762 if (Br1->getMetadata(LLVMContext::MD_unpredictable))
8770 Value *Cond1, *Cond2;
8773 Opc = Instruction::And;
8776 Opc = Instruction::Or;
8786 if (!IsGoodCond(Cond1) || !IsGoodCond(Cond2))
8800 Br1->setCondition(Cond1);
8805 if (Opc == Instruction::And)
8806 Br1->setSuccessor(0, TmpBB);
8808 Br1->setSuccessor(1, TmpBB);
8812 if (
auto *
I = dyn_cast<Instruction>(Cond2)) {
8813 I->removeFromParent();
8814 I->insertBefore(Br2);
8826 if (Opc == Instruction::Or)
8840 if (Opc == Instruction::Or) {
8862 uint64_t NewTrueWeight = TrueWeight;
8863 uint64_t NewFalseWeight = TrueWeight + 2 * FalseWeight;
8865 Br1->setMetadata(LLVMContext::MD_prof,
8869 NewTrueWeight = TrueWeight;
8870 NewFalseWeight = 2 * FalseWeight;
8872 Br2->setMetadata(LLVMContext::MD_prof,
8897 uint64_t NewTrueWeight = 2 * TrueWeight + FalseWeight;
8898 uint64_t NewFalseWeight = FalseWeight;
8900 Br1->setMetadata(LLVMContext::MD_prof,
8904 NewTrueWeight = 2 * TrueWeight;
8905 NewFalseWeight = FalseWeight;
8907 Br2->setMetadata(LLVMContext::MD_prof,
8913 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.
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.