43#include "llvm/Config/llvm-config.h"
64#include "llvm/IR/IntrinsicsAArch64.h"
109#define DEBUG_TYPE "codegenprepare"
112STATISTIC(NumPHIsElim,
"Number of trivial PHIs eliminated");
113STATISTIC(NumGEPsElim,
"Number of GEPs converted to casts");
114STATISTIC(NumCmpUses,
"Number of uses of Cmp expressions replaced with uses of "
116STATISTIC(NumCastUses,
"Number of uses of Cast expressions replaced with uses "
118STATISTIC(NumMemoryInsts,
"Number of memory instructions whose address "
119 "computations were sunk");
121 "Number of phis created when address "
122 "computations were sunk to memory instructions");
124 "Number of select created when address "
125 "computations were sunk to memory instructions");
126STATISTIC(NumExtsMoved,
"Number of [s|z]ext instructions combined with loads");
127STATISTIC(NumExtUses,
"Number of uses of [s|z]ext instructions optimized");
129 "Number of and mask instructions added to form ext loads");
130STATISTIC(NumAndUses,
"Number of uses of and mask instructions optimized");
131STATISTIC(NumRetsDup,
"Number of return instructions duplicated");
132STATISTIC(NumDbgValueMoved,
"Number of debug value instructions moved");
133STATISTIC(NumSelectsExpanded,
"Number of selects turned into branches");
134STATISTIC(NumStoreExtractExposed,
"Number of store(extractelement) exposed");
138 cl::desc(
"Disable branch optimizations in CodeGenPrepare"));
142 cl::desc(
"Disable GC optimizations in CodeGenPrepare"));
147 cl::desc(
"Disable select to branch conversion."));
151 cl::desc(
"Address sinking in CGP using GEPs."));
155 cl::desc(
"Enable sinkinig and/cmp into branches."));
159 cl::desc(
"Disable store(extract) optimizations in CodeGenPrepare"));
163 cl::desc(
"Stress test store(extract) optimizations in CodeGenPrepare"));
167 cl::desc(
"Disable ext(promotable(ld)) -> promoted(ext(ld)) optimization in "
172 cl::desc(
"Stress test ext(promotable(ld)) -> promoted(ext(ld)) "
173 "optimization in CodeGenPrepare"));
177 cl::desc(
"Disable protection against removing loop preheaders"));
181 cl::desc(
"Use profile info to add section prefix for hot/cold functions"));
184 "profile-unknown-in-special-section",
cl::Hidden,
185 cl::desc(
"In profiling mode like sampleFDO, if a function doesn't have "
186 "profile, we cannot tell the function is cold for sure because "
187 "it may be a function newly added without ever being sampled. "
188 "With the flag enabled, compiler can put such profile unknown "
189 "functions into a special section, so runtime system can choose "
190 "to handle it in a different way than .text section, to save "
191 "RAM for example. "));
195 cl::desc(
"Use the basic-block-sections profile to determine the text "
196 "section prefix for hot functions. Functions with "
197 "basic-block-sections profile will be placed in `.text.hot` "
198 "regardless of their FDO profile info. Other functions won't be "
199 "impacted, i.e., their prefixes will be decided by FDO/sampleFDO "
204 cl::desc(
"Skip merging empty blocks if (frequency of empty block) / "
205 "(frequency of destination block) is greater than this ratio"));
209 cl::desc(
"Force store splitting no matter what the target query says."));
213 cl::desc(
"Enable merging of redundant sexts when one is dominating"
219 cl::desc(
"Disables combining addressing modes with different parts "
220 "in optimizeMemoryInst."));
224 cl::desc(
"Allow creation of Phis in Address sinking."));
228 cl::desc(
"Allow creation of selects in Address sinking."));
232 cl::desc(
"Allow combining of BaseReg field in Address sinking."));
236 cl::desc(
"Allow combining of BaseGV field in Address sinking."));
240 cl::desc(
"Allow combining of BaseOffs field in Address sinking."));
244 cl::desc(
"Allow combining of ScaledReg field in Address sinking."));
249 cl::desc(
"Enable splitting large offset of GEP."));
253 cl::desc(
"Enable ICMP_EQ to ICMP_S(L|G)T conversion."));
257 cl::desc(
"Enable BFI update verification for "
262 cl::desc(
"Enable converting phi types in CodeGenPrepare"));
266 cl::desc(
"Least BB number of huge function."));
271 cl::desc(
"Max number of address users to look at"));
275 cl::desc(
"Disable elimination of dead PHI nodes."));
303class TypePromotionTransaction;
305class CodeGenPrepare {
306 friend class CodeGenPrepareLegacyPass;
315 std::unique_ptr<BlockFrequencyInfo>
BFI;
316 std::unique_ptr<BranchProbabilityInfo> BPI;
331 SetOfInstrs InsertedInsts;
335 InstrToOrigTy PromotedInsts;
338 SetOfInstrs RemovedInsts;
357 ValueToSExts ValToSExtendedUses;
367 std::unique_ptr<DominatorTree> DT;
373 bool IsHugeFunc =
false;
381 void releaseMemory() {
383 InsertedInsts.
clear();
384 PromotedInsts.clear();
393 template <
typename F>
394 void resetIteratorIfInvalidatedWhileCalling(
BasicBlock *BB,
F f) {
398 Value *CurValue = &*CurInstIterator;
405 if (IterHandle != CurValue) {
406 CurInstIterator = BB->
begin();
414 DT = std::make_unique<DominatorTree>(
F);
418 void removeAllAssertingVHReferences(
Value *V);
421 bool eliminateMostlyEmptyBlocks(
Function &
F);
424 void eliminateMostlyEmptyBlock(
BasicBlock *BB);
429 bool optimizeInst(
Instruction *
I, ModifyDT &ModifiedDT);
433 bool optimizeInlineAsmInst(
CallInst *CS);
437 bool optimizeLoadExt(
LoadInst *Load);
443 bool optimizeSwitchPhiConstants(
SwitchInst *SI);
445 bool optimizeExtractElementInst(
Instruction *Inst);
446 bool dupRetToEnableTailCallOpts(
BasicBlock *BB, ModifyDT &ModifiedDT);
454 bool tryToPromoteExts(TypePromotionTransaction &TPT,
457 unsigned CreatedInstsCost = 0);
459 bool splitLargeGEPOffsets();
463 bool performAddressTypePromotion(
464 Instruction *&Inst,
bool AllowPromotionWithoutCommonHeader,
465 bool HasPromoted, TypePromotionTransaction &TPT,
467 bool splitBranchCondition(
Function &
F, ModifyDT &ModifiedDT);
473 bool optimizeCmp(
CmpInst *Cmp, ModifyDT &ModifiedDT);
474 bool combineToUSubWithOverflow(
CmpInst *Cmp, ModifyDT &ModifiedDT);
475 bool combineToUAddWithOverflow(
CmpInst *Cmp, ModifyDT &ModifiedDT);
505char CodeGenPrepareLegacyPass::ID = 0;
507bool CodeGenPrepareLegacyPass::runOnFunction(
Function &
F) {
511 CodeGenPrepare CGP(
TM);
512 CGP.DL = &
F.getParent()->getDataLayout();
513 CGP.SubtargetInfo =
TM->getSubtargetImpl(
F);
514 CGP.TLI = CGP.SubtargetInfo->getTargetLowering();
515 CGP.TRI = CGP.SubtargetInfo->getRegisterInfo();
516 CGP.TLInfo = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(
F);
517 CGP.TTI = &getAnalysis<TargetTransformInfoWrapperPass>().getTTI(
F);
518 CGP.LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
521 CGP.PSI = &getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI();
523 getAnalysisIfAvailable<BasicBlockSectionsProfileReaderWrapperPass>();
524 CGP.BBSectionsProfileReader = BBSPRWP ? &BBSPRWP->getBBSPR() :
nullptr;
530 "Optimize for code generation",
false,
false)
541 return new CodeGenPrepareLegacyPass();
546 CodeGenPrepare CGP(
TM);
548 bool Changed = CGP.run(
F, AM);
560 DL = &
F.getParent()->getDataLayout();
561 SubtargetInfo =
TM->getSubtargetImpl(
F);
571 BBSectionsProfileReader =
577 bool EverMadeChange =
false;
579 OptSize =
F.hasOptSize();
584 F.setSectionPrefix(
"hot");
589 if (
F.hasFnAttribute(Attribute::Hot) ||
590 PSI->isFunctionHotInCallGraph(&
F, *BFI))
591 F.setSectionPrefix(
"hot");
595 else if (PSI->isFunctionColdInCallGraph(&
F, *BFI) ||
596 F.hasFnAttribute(Attribute::Cold))
597 F.setSectionPrefix(
"unlikely");
599 PSI->isFunctionHotnessUnknown(
F))
600 F.setSectionPrefix(
"unknown");
609 while (BB !=
nullptr) {
623 EverMadeChange |= eliminateAssumptions(
F);
627 EverMadeChange |= eliminateMostlyEmptyBlocks(
F);
629 ModifyDT ModifiedDT = ModifyDT::NotModifyDT;
631 EverMadeChange |= splitBranchCondition(
F, ModifiedDT);
645 LI->analyze(getDT(
F));
647 bool MadeChange =
true;
648 bool FuncIterated =
false;
653 if (FuncIterated && !FreshBBs.
contains(&BB))
656 ModifyDT ModifiedDTOnIteration = ModifyDT::NotModifyDT;
659 if (ModifiedDTOnIteration == ModifyDT::ModifyBBDT)
662 MadeChange |= Changed;
675 else if (FuncIterated)
680 if (ModifiedDTOnIteration != ModifyDT::NotModifyDT)
685 FuncIterated = IsHugeFunc;
688 MadeChange |= mergeSExts(
F);
689 if (!LargeOffsetGEPMap.
empty())
690 MadeChange |= splitLargeGEPOffsets();
691 MadeChange |= optimizePhiTypes(
F);
694 eliminateFallThrough(
F, DT.get());
698 LI->verify(getDT(
F));
705 EverMadeChange |= MadeChange;
706 SeenChainsForSExt.
clear();
707 ValToSExtendedUses.clear();
708 RemovedInsts.clear();
709 LargeOffsetGEPMap.
clear();
710 LargeOffsetGEPID.
clear();
734 MadeChange |= !WorkList.
empty();
735 while (!WorkList.
empty()) {
748 if (EverMadeChange || MadeChange)
749 MadeChange |= eliminateFallThrough(
F);
751 EverMadeChange |= MadeChange;
758 if (
auto *SP = dyn_cast<GCStatepointInst>(&
I))
760 for (
auto &
I : Statepoints)
761 EverMadeChange |= simplifyOffsetableRelocate(*
I);
766 EverMadeChange |= placeDbgValues(
F);
767 EverMadeChange |= placePseudoProbes(
F);
774 return EverMadeChange;
777bool CodeGenPrepare::eliminateAssumptions(
Function &
F) {
778 bool MadeChange =
false;
780 CurInstIterator = BB.begin();
781 while (CurInstIterator != BB.end()) {
783 if (
auto *Assume = dyn_cast<AssumeInst>(
I)) {
785 Value *Operand = Assume->getOperand(0);
786 Assume->eraseFromParent();
788 resetIteratorIfInvalidatedWhileCalling(&BB, [&]() {
799void CodeGenPrepare::removeAllAssertingVHReferences(
Value *V) {
800 LargeOffsetGEPMap.
erase(V);
801 NewGEPBases.
erase(V);
803 auto GEP = dyn_cast<GetElementPtrInst>(V);
809 auto VecI = LargeOffsetGEPMap.
find(
GEP->getPointerOperand());
810 if (VecI == LargeOffsetGEPMap.
end())
813 auto &GEPVector = VecI->second;
816 if (GEPVector.empty())
817 LargeOffsetGEPMap.
erase(VecI);
826 NewBFI.verifyMatch(*BFI);
833 bool Changed =
false;
843 auto *BB = cast_or_null<BasicBlock>(
Block);
851 if (!SinglePred || SinglePred == BB || BB->hasAddressTaken())
859 if (Term && !
Term->isConditional()) {
871 FreshBBs.
insert(SinglePred);
879 for (
const auto &Pred : Preds)
880 if (
auto *BB = cast_or_null<BasicBlock>(Pred))
896 if (BBI != BB->
begin()) {
898 while (isa<DbgInfoIntrinsic>(BBI)) {
899 if (BBI == BB->
begin())
903 if (!isa<DbgInfoIntrinsic>(BBI) && !isa<PHINode>(BBI))
912 if (!canMergeBlocks(BB, DestBB))
922bool CodeGenPrepare::eliminateMostlyEmptyBlocks(
Function &
F) {
925 while (!LoopList.empty()) {
926 Loop *
L = LoopList.pop_back_val();
929 Preheaders.
insert(Preheader);
932 bool MadeChange =
false;
948 BasicBlock *DestBB = findDestBlockOfMergeableEmptyBlock(BB);
950 !isMergingEmptyBlockProfitable(BB, DestBB, Preheaders.
count(BB)))
953 eliminateMostlyEmptyBlock(BB);
959bool CodeGenPrepare::isMergingEmptyBlockProfitable(
BasicBlock *BB,
975 if (isa<CallBrInst>(Pred->getTerminator()) &&
1007 if (!isa<PHINode>(DestBB->
begin()))
1015 if (DestBBPred == BB)
1019 return DestPN.getIncomingValueForBlock(BB) ==
1020 DestPN.getIncomingValueForBlock(DestBBPred);
1022 SameIncomingValueBBs.
insert(DestBBPred);
1028 if (SameIncomingValueBBs.
count(Pred))
1034 for (
auto *SameValueBB : SameIncomingValueBBs)
1035 if (SameValueBB->getUniquePredecessor() == Pred &&
1036 DestBB == findDestBlockOfMergeableEmptyBlock(SameValueBB))
1037 BBFreq +=
BFI->getBlockFreq(SameValueBB);
1040 return !Limit || PredFreq <= *Limit;
1046bool CodeGenPrepare::canMergeBlocks(
const BasicBlock *BB,
1054 if (UI->
getParent() != DestBB || !isa<PHINode>(UI))
1060 if (
const PHINode *UPN = dyn_cast<PHINode>(UI))
1061 for (
unsigned I = 0,
E = UPN->getNumIncomingValues();
I !=
E; ++
I) {
1063 if (
Insn &&
Insn->getParent() == BB &&
1064 Insn->getParent() != UPN->getIncomingBlock(
I))
1074 const PHINode *DestBBPN = dyn_cast<PHINode>(DestBB->
begin());
1080 if (
const PHINode *BBPN = dyn_cast<PHINode>(BB->
begin())) {
1082 for (
unsigned i = 0, e = BBPN->getNumIncomingValues(); i != e; ++i)
1083 BBPreds.
insert(BBPN->getIncomingBlock(i));
1091 if (BBPreds.
count(Pred)) {
1093 const Value *V1 = PN.getIncomingValueForBlock(Pred);
1094 const Value *
V2 = PN.getIncomingValueForBlock(BB);
1097 if (
const PHINode *V2PN = dyn_cast<PHINode>(V2))
1098 if (V2PN->getParent() == BB)
1099 V2 = V2PN->getIncomingValueForBlock(Pred);
1115 auto *OldI = dyn_cast<Instruction>(Old);
1129void CodeGenPrepare::eliminateMostlyEmptyBlock(
BasicBlock *BB) {
1139 if (SinglePred != DestBB) {
1140 assert(SinglePred == BB &&
1141 "Single predecessor not the same as predecessor");
1150 FreshBBs.
insert(SinglePred);
1151 FreshBBs.
erase(DestBB);
1161 Value *InVal = PN.removeIncomingValue(BB,
false);
1165 PHINode *InValPhi = dyn_cast<PHINode>(InVal);
1166 if (InValPhi && InValPhi->
getParent() == BB) {
1175 for (
unsigned i = 0, e = BBPN->getNumIncomingValues(); i != e; ++i)
1176 PN.addIncoming(InVal, BBPN->getIncomingBlock(i));
1179 PN.addIncoming(InVal, Pred);
1203 for (
auto *ThisRelocate : AllRelocateCalls) {
1204 auto K = std::make_pair(ThisRelocate->getBasePtrIndex(),
1205 ThisRelocate->getDerivedPtrIndex());
1206 RelocateIdxMap.
insert(std::make_pair(K, ThisRelocate));
1208 for (
auto &Item : RelocateIdxMap) {
1209 std::pair<unsigned, unsigned> Key = Item.first;
1210 if (Key.first == Key.second)
1215 auto BaseKey = std::make_pair(Key.first, Key.first);
1218 auto MaybeBase = RelocateIdxMap.
find(BaseKey);
1219 if (MaybeBase == RelocateIdxMap.
end())
1224 RelocateInstMap[MaybeBase->second].push_back(
I);
1232 for (
unsigned i = 1; i <
GEP->getNumOperands(); i++) {
1234 auto *
Op = dyn_cast<ConstantInt>(
GEP->getOperand(i));
1235 if (!
Op ||
Op->getZExtValue() > 20)
1239 for (
unsigned i = 1; i <
GEP->getNumOperands(); i++)
1249 bool MadeChange =
false;
1257 &*R != RelocatedBase; ++R)
1258 if (
auto *RI = dyn_cast<GCRelocateInst>(R))
1268 "Not relocating a derived object of the original base object");
1269 if (ToReplace->getBasePtrIndex() == ToReplace->getDerivedPtrIndex()) {
1283 auto *Derived = dyn_cast<GetElementPtrInst>(ToReplace->getDerivedPtr());
1284 if (!Derived || Derived->getPointerOperand() !=
Base)
1293 "Should always have one since it's not a terminator");
1321 Value *ActualRelocatedBase = RelocatedBase;
1322 if (RelocatedBase->
getType() !=
Base->getType()) {
1323 ActualRelocatedBase =
1326 Value *Replacement =
1327 Builder.
CreateGEP(Derived->getSourceElementType(), ActualRelocatedBase,
1333 Value *ActualReplacement = Replacement;
1334 if (Replacement->
getType() != ToReplace->getType()) {
1339 ToReplace->eraseFromParent();
1364 bool MadeChange =
false;
1366 for (
auto *U :
I.users())
1373 if (AllRelocateCalls.
size() < 2)
1380 if (RelocateInstMap.
empty())
1383 for (
auto &Item : RelocateInstMap)
1397 bool MadeChange =
false;
1400 Use &TheUse = UI.getUse();
1407 UserBB = PN->getIncomingBlock(TheUse);
1415 if (
User->isEHPad())
1425 if (UserBB == DefBB)
1429 CastInst *&InsertedCast = InsertedCasts[UserBB];
1431 if (!InsertedCast) {
1441 TheUse = InsertedCast;
1465 if (
auto *ASC = dyn_cast<AddrSpaceCastInst>(CI)) {
1467 ASC->getDestAddressSpace()))
1507 match(IVInc, m_ExtractValue<0>(m_Intrinsic<Intrinsic::uadd_with_overflow>(
1511 match(IVInc, m_ExtractValue<0>(m_Intrinsic<Intrinsic::usub_with_overflow>(
1522static std::optional<std::pair<Instruction *, Constant *>>
1525 if (!L || L->getHeader() != PN->
getParent() || !L->getLoopLatch())
1526 return std::nullopt;
1529 if (!IVInc || LI->
getLoopFor(IVInc->getParent()) != L)
1530 return std::nullopt;
1534 return std::make_pair(IVInc, Step);
1535 return std::nullopt;
1539 auto *
I = dyn_cast<Instruction>(V);
1546 if (
auto *PN = dyn_cast<PHINode>(
LHS))
1548 return IVInc->first ==
I;
1552bool CodeGenPrepare::replaceMathCmpWithIntrinsic(
BinaryOperator *BO,
1560 assert(L &&
"L should not be null after isIVIncrement()");
1562 if (LI->getLoopFor(
Cmp->getParent()) != L)
1577 if (BO->
getParent() !=
Cmp->getParent() && !IsReplacableIVIncrement(BO)) {
1600 if (BO->
getOpcode() == Instruction::Add &&
1601 IID == Intrinsic::usub_with_overflow) {
1602 assert(isa<Constant>(Arg1) &&
"Unexpected input for usubo");
1611 if ((BO->
getOpcode() != Instruction::Xor && &Iter == BO) || &Iter == Cmp) {
1616 assert(InsertPt !=
nullptr &&
"Parent block did not contain cmp or binop");
1619 Value *MathOV = Builder.CreateBinaryIntrinsic(IID, Arg0, Arg1);
1620 if (BO->
getOpcode() != Instruction::Xor) {
1621 Value *Math = Builder.CreateExtractValue(MathOV, 0,
"math");
1625 "Patterns with XOr should use the BO only in the compare");
1626 Value *OV = Builder.CreateExtractValue(MathOV, 1,
"ov");
1628 Cmp->eraseFromParent();
1638 Value *
A = Cmp->getOperand(0), *
B = Cmp->getOperand(1);
1641 if (isa<Constant>(
A))
1646 B = ConstantInt::get(
B->getType(), 1);
1648 B = ConstantInt::get(
B->getType(), -1);
1654 for (
User *U :
A->users()) {
1656 Add = cast<BinaryOperator>(U);
1665bool CodeGenPrepare::combineToUAddWithOverflow(
CmpInst *Cmp,
1666 ModifyDT &ModifiedDT) {
1667 bool EdgeCase =
false;
1674 A =
Add->getOperand(0);
1675 B =
Add->getOperand(1);
1681 Add->hasNUsesOrMore(EdgeCase ? 1 : 2)))
1687 if (
Add->getParent() !=
Cmp->getParent() && !
Add->hasOneUse())
1690 if (!replaceMathCmpWithIntrinsic(
Add,
A,
B, Cmp,
1691 Intrinsic::uadd_with_overflow))
1695 ModifiedDT = ModifyDT::ModifyInstDT;
1699bool CodeGenPrepare::combineToUSubWithOverflow(
CmpInst *Cmp,
1700 ModifyDT &ModifiedDT) {
1703 if (isa<Constant>(
A) && isa<Constant>(
B))
1714 B = ConstantInt::get(
B->getType(), 1);
1728 Value *CmpVariableOperand = isa<Constant>(
A) ?
B :
A;
1730 for (
User *U : CmpVariableOperand->
users()) {
1733 Sub = cast<BinaryOperator>(U);
1738 const APInt *CmpC, *AddC;
1741 Sub = cast<BinaryOperator>(U);
1754 Cmp, Intrinsic::usub_with_overflow))
1758 ModifiedDT = ModifyDT::ModifyInstDT;
1779 bool MadeChange =
false;
1782 Use &TheUse = UI.getUse();
1789 if (isa<PHINode>(
User))
1797 if (UserBB == DefBB)
1801 CmpInst *&InsertedCmp = InsertedCmps[UserBB];
1807 Cmp->getOperand(0), Cmp->getOperand(1),
"");
1814 TheUse = InsertedCmp;
1820 if (Cmp->use_empty()) {
1821 Cmp->eraseFromParent();
1858 for (
User *U : Cmp->users()) {
1859 if (isa<BranchInst>(U))
1861 if (isa<SelectInst>(U) && cast<SelectInst>(U)->getCondition() == Cmp)
1880 if (CmpBB != FalseBB)
1883 Value *CmpOp0 = Cmp->getOperand(0), *CmpOp1 = Cmp->getOperand(1);
1897 for (
User *U : Cmp->users()) {
1898 if (
auto *BI = dyn_cast<BranchInst>(U)) {
1903 if (
auto *SI = dyn_cast<SelectInst>(U)) {
1906 SI->swapProfMetadata();
1918 Value *Op0 = Cmp->getOperand(0);
1919 Value *Op1 = Cmp->getOperand(1);
1921 isa<Constant>(Op1) || Op0 == Op1)
1928 unsigned NumInspected = 0;
1931 if (++NumInspected > 128)
1939 if (GoodToSwap > 0) {
1940 Cmp->swapOperands();
1946bool CodeGenPrepare::optimizeCmp(
CmpInst *Cmp, ModifyDT &ModifiedDT) {
1950 if (combineToUAddWithOverflow(Cmp, ModifiedDT))
1953 if (combineToUSubWithOverflow(Cmp, ModifiedDT))
1971 SetOfInstrs &InsertedInsts) {
1974 assert(!InsertedInsts.count(AndI) &&
1975 "Attempting to optimize already optimized and instruction");
1976 (void)InsertedInsts;
1985 if (!isa<ConstantInt>(AndI->
getOperand(0)) &&
1990 for (
auto *U : AndI->
users()) {
1994 if (!isa<ICmpInst>(
User))
1998 if (!CmpC || !CmpC->
isZero())
2013 Use &TheUse = UI.getUse();
2031 TheUse = InsertedAnd;
2047 if (!isa<TruncInst>(
User)) {
2048 if (
User->getOpcode() != Instruction::And ||
2054 if ((Cimm & (Cimm + 1)).getBoolValue())
2067 auto *TruncI = cast<TruncInst>(
User);
2068 bool MadeChange =
false;
2071 TruncE = TruncI->user_end();
2072 TruncUI != TruncE;) {
2074 Use &TruncTheUse = TruncUI.getUse();
2075 Instruction *TruncUser = cast<Instruction>(*TruncUI);
2094 if (isa<PHINode>(TruncUser))
2099 if (UserBB == TruncUserBB)
2103 CastInst *&InsertedTrunc = InsertedTruncs[TruncUserBB];
2105 if (!InsertedShift && !InsertedTrunc) {
2109 if (ShiftI->
getOpcode() == Instruction::AShr)
2111 BinaryOperator::CreateAShr(ShiftI->
getOperand(0), CI,
"");
2114 BinaryOperator::CreateLShr(ShiftI->
getOperand(0), CI,
"");
2122 TruncInsertPt.setHeadBit(
true);
2123 assert(TruncInsertPt != TruncUserBB->
end());
2127 InsertedTrunc->
insertBefore(*TruncUserBB, TruncInsertPt);
2128 InsertedTrunc->
setDebugLoc(TruncI->getDebugLoc());
2132 TruncTheUse = InsertedTrunc;
2165 bool MadeChange =
false;
2168 Use &TheUse = UI.getUse();
2174 if (isa<PHINode>(
User))
2182 if (UserBB == DefBB) {
2197 if (isa<TruncInst>(
User) &&
2210 if (!InsertedShift) {
2214 if (ShiftI->
getOpcode() == Instruction::AShr)
2216 BinaryOperator::CreateAShr(ShiftI->
getOperand(0), CI,
"");
2219 BinaryOperator::CreateLShr(ShiftI->
getOperand(0), CI,
"");
2227 TheUse = InsertedShift;
2276 if (Ty->
isVectorTy() || SizeInBits >
DL->getLargestLegalIntTypeSizeInBits())
2288 FreshBBs.
insert(CallBlock);
2295 SplitPt.setHeadBit(
true);
2298 FreshBBs.
insert(EndBlock);
2303 L->addBasicBlockToLoop(CallBlock, LI);
2304 L->addBasicBlockToLoop(EndBlock, LI);
2335 ModifiedDT = ModifyDT::ModifyBBDT;
2339bool CodeGenPrepare::optimizeCallInst(
CallInst *CI, ModifyDT &ModifiedDT) {
2348 CurInstIterator = BB->
begin();
2355 if (optimizeInlineAsmInst(CI))
2364 for (
auto &Arg : CI->
args()) {
2369 if (!Arg->getType()->isPointerTy())
2372 cast<PointerType>(Arg->getType())->getAddressSpace()),
2379 if ((AI = dyn_cast<AllocaInst>(Val)) && AI->
getAlign() < PrefAlign &&
2398 if (!MIDestAlign || DestAlign > *MIDestAlign)
2399 MI->setDestAlignment(DestAlign);
2401 MaybeAlign MTISrcAlign = MTI->getSourceAlign();
2403 if (!MTISrcAlign || SrcAlign > *MTISrcAlign)
2404 MTI->setSourceAlignment(SrcAlign);
2412 if (CI->
hasFnAttr(Attribute::Cold) && !OptSize &&
2414 for (
auto &Arg : CI->
args()) {
2415 if (!Arg->getType()->isPointerTy())
2417 unsigned AS = Arg->getType()->getPointerAddressSpace();
2418 if (optimizeMemoryInst(CI, Arg, Arg->getType(), AS))
2427 case Intrinsic::assume:
2429 case Intrinsic::experimental_widenable_condition: {
2438 resetIteratorIfInvalidatedWhileCalling(BB, [&]() {
2443 case Intrinsic::objectsize:
2445 case Intrinsic::is_constant:
2447 case Intrinsic::aarch64_stlxr:
2448 case Intrinsic::aarch64_stxr: {
2457 InsertedInsts.insert(ExtVal);
2461 case Intrinsic::launder_invariant_group:
2462 case Intrinsic::strip_invariant_group: {
2464 auto it = LargeOffsetGEPMap.
find(II);
2465 if (it != LargeOffsetGEPMap.
end()) {
2469 auto GEPs = std::move(it->second);
2470 LargeOffsetGEPMap[ArgVal].append(GEPs.begin(), GEPs.end());
2471 LargeOffsetGEPMap.
erase(II);
2478 case Intrinsic::cttz:
2479 case Intrinsic::ctlz:
2483 case Intrinsic::fshl:
2484 case Intrinsic::fshr:
2485 return optimizeFunnelShift(II);
2486 case Intrinsic::dbg_assign:
2487 case Intrinsic::dbg_value:
2488 return fixupDbgValue(II);
2489 case Intrinsic::masked_gather:
2491 case Intrinsic::masked_scatter:
2498 while (!PtrOps.
empty()) {
2501 if (optimizeMemoryInst(II, PtrVal, AccessTy, AS))
2516 if (
Value *V = Simplifier.optimizeCall(CI, Builder)) {
2529 if (
const auto *II = dyn_cast<IntrinsicInst>(CI))
2531 case Intrinsic::memset:
2532 case Intrinsic::memcpy:
2533 case Intrinsic::memmove:
2541 if (Callee && TLInfo && TLInfo->
getLibFunc(*Callee, LF))
2543 case LibFunc_strcpy:
2544 case LibFunc_strncpy:
2545 case LibFunc_strcat:
2546 case LibFunc_strncat:
2587bool CodeGenPrepare::dupRetToEnableTailCallOpts(
BasicBlock *BB,
2588 ModifyDT &ModifiedDT) {
2596 assert(LI->getLoopFor(BB) ==
nullptr &&
"A return block cannot be in a loop");
2603 BCI = dyn_cast<BitCastInst>(V);
2607 EVI = dyn_cast<ExtractValueInst>(V);
2614 PN = dyn_cast<PHINode>(V);
2620 auto isLifetimeEndOrBitCastFor = [](
const Instruction *Inst) {
2621 const BitCastInst *BC = dyn_cast<BitCastInst>(Inst);
2625 if (
const IntrinsicInst *II = dyn_cast<IntrinsicInst>(Inst))
2634 while (isa<DbgInfoIntrinsic>(BI) || BI == BCI || BI == EVI ||
2635 isa<PseudoProbeInst>(BI) || isLifetimeEndOrBitCastFor(BI))
2648 CallInst *CI = dyn_cast<CallInst>(IncomingVal);
2667 CI = dyn_cast_or_null<CallInst>(
2681 if (!VisitedBBs.
insert(Pred).second)
2683 if (
Instruction *
I = Pred->rbegin()->getPrevNonDebugInstruction(
true)) {
2689 if (!V || isa<UndefValue>(V) ||
2699 bool Changed =
false;
2700 for (
auto const &TailCallBB : TailCallBBs) {
2703 BranchInst *BI = dyn_cast<BranchInst>(TailCallBB->getTerminator());
2710 BFI->getBlockFreq(BB) >=
BFI->getBlockFreq(TailCallBB));
2711 BFI->setBlockFreq(BB,
2712 (
BFI->getBlockFreq(BB) -
BFI->getBlockFreq(TailCallBB)));
2713 ModifiedDT = ModifyDT::ModifyBBDT;
2736 Value *OriginalValue =
nullptr;
2737 bool InBounds =
true;
2741 BaseRegField = 0x01,
2743 BaseOffsField = 0x04,
2744 ScaledRegField = 0x08,
2746 MultipleFields = 0xff
2759 return MultipleFields;
2760 if (BaseGV && other.BaseGV && BaseGV->getType() != other.BaseGV->getType())
2761 return MultipleFields;
2764 return MultipleFields;
2767 if (InBounds != other.InBounds)
2768 return MultipleFields;
2771 unsigned Result = NoField;
2774 if (BaseGV != other.BaseGV)
2776 if (BaseOffs != other.BaseOffs)
2779 Result |= ScaledRegField;
2786 return MultipleFields;
2788 return static_cast<FieldName
>(
Result);
2809 case ScaledRegField:
2812 return ConstantInt::get(IntPtrTy, BaseOffs);
2816 void SetCombinedField(FieldName
Field,
Value *V,
2822 case ExtAddrMode::BaseRegField:
2825 case ExtAddrMode::BaseGVField:
2832 case ExtAddrMode::ScaledRegField:
2843 case ExtAddrMode::BaseOffsField:
2862#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
2864 bool NeedPlus =
false;
2870 BaseGV->printAsOperand(
OS,
false);
2875 OS << (NeedPlus ?
" + " :
"") << BaseOffs;
2880 OS << (NeedPlus ?
" + " :
"") <<
"Base:";
2885 OS << (NeedPlus ?
" + " :
"") <<
Scale <<
"*";
2908class TypePromotionTransaction {
2912 class TypePromotionAction {
2920 TypePromotionAction(
Instruction *Inst) : Inst(Inst) {}
2922 virtual ~TypePromotionAction() =
default;
2929 virtual void undo() = 0;
2934 virtual void commit() {
2940 class InsertionHandler {
2949 std::optional<DbgRecord::self_iterator> BeforeDbgRecord = std::nullopt;
2952 bool HasPrevInstruction;
2965 if (HasPrevInstruction) {
2966 Point.PrevInst = &*std::prev(Inst->
getIterator());
2974 if (HasPrevInstruction) {
2991 class InstructionMoveBefore :
public TypePromotionAction {
2993 InsertionHandler Position;
2998 : TypePromotionAction(Inst), Position(Inst) {
3005 void undo()
override {
3007 Position.insert(Inst);
3012 class OperandSetter :
public TypePromotionAction {
3022 : TypePromotionAction(Inst),
Idx(
Idx) {
3024 <<
"for:" << *Inst <<
"\n"
3025 <<
"with:" << *NewVal <<
"\n");
3031 void undo()
override {
3033 <<
"for: " << *Inst <<
"\n"
3034 <<
"with: " << *Origin <<
"\n");
3041 class OperandsHider :
public TypePromotionAction {
3047 OperandsHider(
Instruction *Inst) : TypePromotionAction(Inst) {
3050 OriginalValues.
reserve(NumOpnds);
3051 for (
unsigned It = 0; It < NumOpnds; ++It) {
3063 void undo()
override {
3065 for (
unsigned It = 0, EndIt = OriginalValues.
size(); It != EndIt; ++It)
3071 class TruncBuilder :
public TypePromotionAction {
3078 TruncBuilder(
Instruction *Opnd,
Type *Ty) : TypePromotionAction(Opnd) {
3080 Builder.SetCurrentDebugLocation(
DebugLoc());
3081 Val = Builder.CreateTrunc(Opnd, Ty,
"promoted");
3086 Value *getBuiltValue() {
return Val; }
3089 void undo()
override {
3091 if (
Instruction *IVal = dyn_cast<Instruction>(Val))
3092 IVal->eraseFromParent();
3097 class SExtBuilder :
public TypePromotionAction {
3105 : TypePromotionAction(InsertPt) {
3107 Val = Builder.CreateSExt(Opnd, Ty,
"promoted");
3112 Value *getBuiltValue() {
return Val; }
3115 void undo()
override {
3117 if (
Instruction *IVal = dyn_cast<Instruction>(Val))
3118 IVal->eraseFromParent();
3123 class ZExtBuilder :
public TypePromotionAction {
3131 : TypePromotionAction(InsertPt) {
3133 Builder.SetCurrentDebugLocation(
DebugLoc());
3134 Val = Builder.CreateZExt(Opnd, Ty,
"promoted");
3139 Value *getBuiltValue() {
return Val; }
3142 void undo()
override {
3144 if (
Instruction *IVal = dyn_cast<Instruction>(Val))
3145 IVal->eraseFromParent();
3150 class TypeMutator :
public TypePromotionAction {
3157 : TypePromotionAction(Inst), OrigTy(Inst->
getType()) {
3158 LLVM_DEBUG(
dbgs() <<
"Do: MutateType: " << *Inst <<
" with " << *NewTy
3164 void undo()
override {
3165 LLVM_DEBUG(
dbgs() <<
"Undo: MutateType: " << *Inst <<
" with " << *OrigTy
3172 class UsesReplacer :
public TypePromotionAction {
3174 struct InstructionAndIdx {
3182 : Inst(Inst),
Idx(
Idx) {}
3201 : TypePromotionAction(Inst),
New(
New) {
3202 LLVM_DEBUG(
dbgs() <<
"Do: UsersReplacer: " << *Inst <<
" with " << *New
3207 OriginalUses.
push_back(InstructionAndIdx(UserI,
U.getOperandNo()));
3218 void undo()
override {
3220 for (InstructionAndIdx &
Use : OriginalUses)
3221 Use.Inst->setOperand(
Use.Idx, Inst);
3226 for (
auto *DVI : DbgValues)
3227 DVI->replaceVariableLocationOp(New, Inst);
3231 DPV->replaceVariableLocationOp(New, Inst);
3236 class InstructionRemover :
public TypePromotionAction {
3238 InsertionHandler Inserter;
3242 OperandsHider Hider;
3245 UsesReplacer *Replacer =
nullptr;
3248 SetOfInstrs &RemovedInsts;
3255 InstructionRemover(
Instruction *Inst, SetOfInstrs &RemovedInsts,
3256 Value *New =
nullptr)
3257 : TypePromotionAction(Inst), Inserter(Inst), Hider(Inst),
3258 RemovedInsts(RemovedInsts) {
3260 Replacer =
new UsesReplacer(Inst, New);
3261 LLVM_DEBUG(
dbgs() <<
"Do: InstructionRemover: " << *Inst <<
"\n");
3262 RemovedInsts.insert(Inst);
3269 ~InstructionRemover()
override {
delete Replacer; }
3271 InstructionRemover &operator=(
const InstructionRemover &other) =
delete;
3272 InstructionRemover(
const InstructionRemover &other) =
delete;
3276 void undo()
override {
3277 LLVM_DEBUG(
dbgs() <<
"Undo: InstructionRemover: " << *Inst <<
"\n");
3278 Inserter.insert(Inst);
3282 RemovedInsts.erase(Inst);
3290 using ConstRestorationPt =
const TypePromotionAction *;
3292 TypePromotionTransaction(SetOfInstrs &RemovedInsts)
3293 : RemovedInsts(RemovedInsts) {}
3300 void rollback(ConstRestorationPt Point);
3303 ConstRestorationPt getRestorationPoint()
const;
3335 SetOfInstrs &RemovedInsts;
3340void TypePromotionTransaction::setOperand(
Instruction *Inst,
unsigned Idx,
3342 Actions.
push_back(std::make_unique<TypePromotionTransaction::OperandSetter>(
3343 Inst,
Idx, NewVal));
3346void TypePromotionTransaction::eraseInstruction(
Instruction *Inst,
3349 std::make_unique<TypePromotionTransaction::InstructionRemover>(
3350 Inst, RemovedInsts, NewVal));
3353void TypePromotionTransaction::replaceAllUsesWith(
Instruction *Inst,
3356 std::make_unique<TypePromotionTransaction::UsesReplacer>(Inst, New));
3359void TypePromotionTransaction::mutateType(
Instruction *Inst,
Type *NewTy) {
3361 std::make_unique<TypePromotionTransaction::TypeMutator>(Inst, NewTy));
3365 std::unique_ptr<TruncBuilder>
Ptr(
new TruncBuilder(Opnd, Ty));
3367 Actions.push_back(std::move(
Ptr));
3373 std::unique_ptr<SExtBuilder>
Ptr(
new SExtBuilder(Inst, Opnd, Ty));
3375 Actions.push_back(std::move(
Ptr));
3381 std::unique_ptr<ZExtBuilder>
Ptr(
new ZExtBuilder(Inst, Opnd, Ty));
3383 Actions.push_back(std::move(
Ptr));
3387TypePromotionTransaction::ConstRestorationPt
3388TypePromotionTransaction::getRestorationPoint()
const {
3389 return !Actions.empty() ? Actions.back().get() :
nullptr;
3392bool TypePromotionTransaction::commit() {
3393 for (std::unique_ptr<TypePromotionAction> &Action : Actions)
3400void TypePromotionTransaction::rollback(
3401 TypePromotionTransaction::ConstRestorationPt Point) {
3402 while (!Actions.empty() && Point != Actions.back().get()) {
3403 std::unique_ptr<TypePromotionAction> Curr = Actions.pop_back_val();
3413class AddressingModeMatcher {
3432 const SetOfInstrs &InsertedInsts;
3435 InstrToOrigTy &PromotedInsts;
3438 TypePromotionTransaction &TPT;
3441 std::pair<AssertingVH<GetElementPtrInst>, int64_t> &LargeOffsetGEP;
3445 bool IgnoreProfitability;
3448 bool OptSize =
false;
3453 AddressingModeMatcher(
3458 const SetOfInstrs &InsertedInsts, InstrToOrigTy &PromotedInsts,
3459 TypePromotionTransaction &TPT,
3462 : AddrModeInsts(AMI), TLI(TLI),
TRI(
TRI),
3463 DL(
MI->getModule()->getDataLayout()), LI(LI), getDTFn(getDTFn),
3464 AccessTy(AT), AddrSpace(AS), MemoryInst(
MI),
AddrMode(AM),
3465 InsertedInsts(InsertedInsts), PromotedInsts(PromotedInsts), TPT(TPT),
3466 LargeOffsetGEP(LargeOffsetGEP), OptSize(OptSize), PSI(PSI),
BFI(
BFI) {
3467 IgnoreProfitability =
false;
3484 InstrToOrigTy &PromotedInsts, TypePromotionTransaction &TPT,
3489 bool Success = AddressingModeMatcher(AddrModeInsts, TLI,
TRI, LI, getDTFn,
3490 AccessTy, AS, MemoryInst, Result,
3491 InsertedInsts, PromotedInsts, TPT,
3492 LargeOffsetGEP, OptSize, PSI, BFI)
3500 bool matchScaledValue(
Value *ScaleReg, int64_t Scale,
unsigned Depth);
3502 bool matchOperationAddr(
User *AddrInst,
unsigned Opcode,
unsigned Depth,
3503 bool *MovedAway =
nullptr);
3504 bool isProfitableToFoldIntoAddressingMode(
Instruction *
I,
3507 bool valueAlreadyLiveAtInst(
Value *Val,
Value *KnownLive1,
Value *KnownLive2);
3508 bool isPromotionProfitable(
unsigned NewCost,
unsigned OldCost,
3509 Value *PromotedOperand)
const;
3515class PhiNodeSetIterator {
3516 PhiNodeSet *
const Set;
3517 size_t CurrentIndex = 0;
3522 PhiNodeSetIterator(PhiNodeSet *
const Set,
size_t Start);
3524 PhiNodeSetIterator &operator++();
3540 friend class PhiNodeSetIterator;
3543 using iterator = PhiNodeSetIterator;
3558 size_t FirstValidElement = 0;
3565 if (NodeMap.insert(std::make_pair(
Ptr,
NodeList.size())).second) {
3576 if (NodeMap.erase(
Ptr)) {
3577 SkipRemovedElements(FirstValidElement);
3587 FirstValidElement = 0;
3593 if (FirstValidElement == 0)
3594 SkipRemovedElements(FirstValidElement);
3595 return PhiNodeSetIterator(
this, FirstValidElement);
3599 iterator
end() {
return PhiNodeSetIterator(
this,
NodeList.size()); }
3602 size_t size()
const {
return NodeMap.size(); }
3613 void SkipRemovedElements(
size_t &CurrentIndex) {
3614 while (CurrentIndex <
NodeList.size()) {
3615 auto it = NodeMap.find(
NodeList[CurrentIndex]);
3618 if (it != NodeMap.end() && it->second == CurrentIndex)
3625PhiNodeSetIterator::PhiNodeSetIterator(PhiNodeSet *
const Set,
size_t Start)
3626 : Set(Set), CurrentIndex(Start) {}
3628PHINode *PhiNodeSetIterator::operator*()
const {
3630 "PhiNodeSet access out of range");
3631 return Set->NodeList[CurrentIndex];
3634PhiNodeSetIterator &PhiNodeSetIterator::operator++() {
3636 "PhiNodeSet access out of range");
3638 Set->SkipRemovedElements(CurrentIndex);
3642bool PhiNodeSetIterator::operator==(
const PhiNodeSetIterator &RHS)
const {
3643 return CurrentIndex ==
RHS.CurrentIndex;
3646bool PhiNodeSetIterator::operator!=(
const PhiNodeSetIterator &RHS)
const {
3647 return !((*this) ==
RHS);
3653class SimplificationTracker {
3658 PhiNodeSet AllPhiNodes;
3667 auto SV = Storage.
find(V);
3668 if (SV == Storage.
end())
3678 while (!WorkList.
empty()) {
3680 if (!Visited.
insert(
P).second)
3682 if (
auto *PI = dyn_cast<Instruction>(
P))
3684 for (
auto *U : PI->users())
3687 PI->replaceAllUsesWith(V);
3688 if (
auto *
PHI = dyn_cast<PHINode>(PI))
3689 AllPhiNodes.erase(
PHI);
3690 if (
auto *
Select = dyn_cast<SelectInst>(PI))
3692 PI->eraseFromParent();
3702 while (OldReplacement !=
From) {
3704 To = dyn_cast<PHINode>(OldReplacement);
3705 OldReplacement = Get(
From);
3707 assert(To && Get(To) == To &&
"Replacement PHI node is already replaced.");
3709 From->replaceAllUsesWith(To);
3710 AllPhiNodes.erase(
From);
3711 From->eraseFromParent();
3714 PhiNodeSet &newPhiNodes() {
return AllPhiNodes; }
3716 void insertNewPhi(
PHINode *PN) { AllPhiNodes.insert(PN); }
3720 unsigned countNewPhiNodes()
const {
return AllPhiNodes.size(); }
3722 unsigned countNewSelectNodes()
const {
return AllSelectNodes.
size(); }
3724 void destroyNewNodes(
Type *CommonType) {
3727 for (
auto *
I : AllPhiNodes) {
3728 I->replaceAllUsesWith(Dummy);
3729 I->eraseFromParent();
3731 AllPhiNodes.clear();
3732 for (
auto *
I : AllSelectNodes) {
3733 I->replaceAllUsesWith(Dummy);
3734 I->eraseFromParent();
3736 AllSelectNodes.clear();
3741class AddressingModeCombiner {
3743 typedef std::pair<PHINode *, PHINode *> PHIPair;
3750 ExtAddrMode::FieldName DifferentField = ExtAddrMode::NoField;
3753 bool AllAddrModesTrivial =
true;
3756 Type *CommonType =
nullptr;
3765 Value *CommonValue =
nullptr;
3769 : SQ(_SQ), Original(OriginalValue) {}
3771 ~AddressingModeCombiner() { eraseCommonValueIfDead(); }
3783 AllAddrModesTrivial = AllAddrModesTrivial && NewAddrMode.isTrivial();
3786 if (AddrModes.
empty()) {
3794 ExtAddrMode::FieldName ThisDifferentField =
3795 AddrModes[0].compare(NewAddrMode);
3796 if (DifferentField == ExtAddrMode::NoField)
3797 DifferentField = ThisDifferentField;
3798 else if (DifferentField != ThisDifferentField)
3799 DifferentField = ExtAddrMode::MultipleFields;
3802 bool CanHandle = DifferentField != ExtAddrMode::MultipleFields;
3805 CanHandle = CanHandle && DifferentField != ExtAddrMode::ScaleField;
3810 CanHandle = CanHandle && (DifferentField != ExtAddrMode::BaseOffsField ||
3815 CanHandle = CanHandle && (DifferentField != ExtAddrMode::BaseGVField ||
3816 !NewAddrMode.HasBaseReg);
3833 bool combineAddrModes() {
3835 if (AddrModes.
size() == 0)
3839 if (AddrModes.
size() == 1 || DifferentField == ExtAddrMode::NoField)
3844 if (AllAddrModesTrivial)
3847 if (!addrModeCombiningAllowed())
3853 FoldAddrToValueMapping
Map;
3854 if (!initializeMap(Map))
3857 CommonValue = findCommon(Map);
3859 AddrModes[0].SetCombinedField(DifferentField, CommonValue, AddrModes);
3860 return CommonValue !=
nullptr;
3866 void eraseCommonValueIfDead() {
3867 if (CommonValue && CommonValue->
getNumUses() == 0)
3868 if (
Instruction *CommonInst = dyn_cast<Instruction>(CommonValue))
3869 CommonInst->eraseFromParent();
3877 bool initializeMap(FoldAddrToValueMapping &Map) {
3882 for (
auto &AM : AddrModes) {
3883 Value *DV = AM.GetFieldAsValue(DifferentField, IntPtrTy);
3886 if (CommonType && CommonType !=
Type)
3889 Map[AM.OriginalValue] = DV;
3894 assert(CommonType &&
"At least one non-null value must be!");
3895 for (
auto *V : NullValue)
3923 Value *findCommon(FoldAddrToValueMapping &Map) {
3931 SimplificationTracker
ST(SQ);
3936 InsertPlaceholders(Map, TraverseOrder, ST);
3939 FillPlaceholders(Map, TraverseOrder, ST);
3942 ST.destroyNewNodes(CommonType);
3947 unsigned PhiNotMatchedCount = 0;
3949 ST.destroyNewNodes(CommonType);
3953 auto *
Result =
ST.Get(
Map.find(Original)->second);
3955 NumMemoryInstsPhiCreated +=
ST.countNewPhiNodes() + PhiNotMatchedCount;
3956 NumMemoryInstsSelectCreated +=
ST.countNewSelectNodes();
3965 PhiNodeSet &PhiNodesToMatch) {
3972 while (!WorkList.
empty()) {
3974 if (!Visited.
insert(Item).second)
3981 for (
auto *
B : Item.first->blocks()) {
3982 Value *FirstValue = Item.first->getIncomingValueForBlock(
B);
3983 Value *SecondValue = Item.second->getIncomingValueForBlock(
B);
3984 if (FirstValue == SecondValue)
3987 PHINode *FirstPhi = dyn_cast<PHINode>(FirstValue);
3988 PHINode *SecondPhi = dyn_cast<PHINode>(SecondValue);
3994 if (!FirstPhi || !SecondPhi || !PhiNodesToMatch.count(FirstPhi) ||
3999 if (Matcher.
count({FirstPhi, SecondPhi}))
4004 if (MatchedPHIs.
insert(FirstPhi).second)
4005 Matcher.
insert({FirstPhi, SecondPhi});
4007 WorkList.
push_back({FirstPhi, SecondPhi});
4016 bool MatchPhiSet(SimplificationTracker &ST,
bool AllowNewPhiNodes,
4017 unsigned &PhiNotMatchedCount) {
4023 PhiNodeSet &PhiNodesToMatch =
ST.newPhiNodes();
4024 while (PhiNodesToMatch.size()) {
4028 WillNotMatch.
clear();
4032 bool IsMatched =
false;
4033 for (
auto &
P :
PHI->getParent()->phis()) {
4035 if (PhiNodesToMatch.count(&
P))
4037 if ((IsMatched = MatchPhiNode(
PHI, &
P, Matched, PhiNodesToMatch)))
4042 for (
auto M : Matched)
4048 for (
auto MV : Matched)
4049 ST.ReplacePhi(MV.first, MV.second);
4054 if (!AllowNewPhiNodes)
4057 PhiNotMatchedCount += WillNotMatch.
size();
4058 for (
auto *
P : WillNotMatch)
4059 PhiNodesToMatch.erase(
P);
4064 void FillPlaceholders(FoldAddrToValueMapping &Map,
4066 SimplificationTracker &ST) {
4067 while (!TraverseOrder.
empty()) {
4069 assert(
Map.contains(Current) &&
"No node to fill!!!");
4074 auto *CurrentSelect = cast<SelectInst>(Current);
4075 auto *TrueValue = CurrentSelect->getTrueValue();
4076 assert(
Map.contains(TrueValue) &&
"No True Value!");
4077 Select->setTrueValue(
ST.Get(Map[TrueValue]));
4078 auto *FalseValue = CurrentSelect->getFalseValue();
4079 assert(
Map.contains(FalseValue) &&
"No False Value!");
4080 Select->setFalseValue(
ST.Get(Map[FalseValue]));
4083 auto *
PHI = cast<PHINode>(V);
4086 Value *PV = cast<PHINode>(Current)->getIncomingValueForBlock(
B);
4087 assert(
Map.contains(PV) &&
"No predecessor Value!");
4088 PHI->addIncoming(
ST.Get(Map[PV]),
B);
4091 Map[Current] =
ST.Simplify(V);
4100 void InsertPlaceholders(FoldAddrToValueMapping &Map,
4102 SimplificationTracker &ST) {
4104 assert((isa<PHINode>(Original) || isa<SelectInst>(Original)) &&
4105 "Address must be a Phi or Select node");
4108 while (!Worklist.
empty()) {
4111 if (
Map.contains(Current))
4117 if (
SelectInst *CurrentSelect = dyn_cast<SelectInst>(Current)) {
4121 CurrentSelect->getCondition(), Dummy, Dummy,
4122 CurrentSelect->getName(), CurrentSelect, CurrentSelect);
4126 Worklist.
push_back(CurrentSelect->getTrueValue());
4127 Worklist.
push_back(CurrentSelect->getFalseValue());
4130 PHINode *CurrentPhi = cast<PHINode>(Current);
4135 ST.insertNewPhi(
PHI);
4141 bool addrModeCombiningAllowed() {
4144 switch (DifferentField) {
4147 case ExtAddrMode::BaseRegField:
4149 case ExtAddrMode::BaseGVField:
4151 case ExtAddrMode::BaseOffsField:
4153 case ExtAddrMode::ScaledRegField:
4163bool AddressingModeMatcher::matchScaledValue(
Value *ScaleReg, int64_t Scale,
4168 return matchAddr(ScaleReg,
Depth);
4183 TestAddrMode.
Scale += Scale;
4198 Value *AddLHS =
nullptr;
4199 if (isa<Instruction>(ScaleReg) &&
4202 TestAddrMode.InBounds =
false;
4209 AddrModeInsts.
push_back(cast<Instruction>(ScaleReg));
4219 auto GetConstantStep =
4220 [
this](
const Value *
V) -> std::optional<std::pair<Instruction *, APInt>> {
4221 auto *PN = dyn_cast<PHINode>(V);
4223 return std::nullopt;
4226 return std::nullopt;
4233 if (
auto *OIVInc = dyn_cast<OverflowingBinaryOperator>(IVInc->first))
4234 if (OIVInc->hasNoSignedWrap() || OIVInc->hasNoUnsignedWrap())
4235 return std::nullopt;
4236 if (
auto *ConstantStep = dyn_cast<ConstantInt>(IVInc->second))
4237 return std::make_pair(IVInc->first, ConstantStep->getValue());
4238 return std::nullopt;
4253 if (
auto IVStep = GetConstantStep(ScaleReg)) {
4260 APInt Step = IVStep->second;
4262 if (
Offset.isSignedIntN(64)) {
4263 TestAddrMode.InBounds =
false;
4265 TestAddrMode.BaseOffs -=
Offset.getLimitedValue();
4270 getDTFn().
dominates(IVInc, MemoryInst)) {
4271 AddrModeInsts.
push_back(cast<Instruction>(IVInc));
4290 switch (
I->getOpcode()) {
4291 case Instruction::BitCast:
4292 case Instruction::AddrSpaceCast:
4294 if (
I->getType() ==
I->getOperand(0)->getType())
4296 return I->getType()->isIntOrPtrTy();
4297 case Instruction::PtrToInt:
4300 case Instruction::IntToPtr:
4303 case Instruction::Add:
4305 case Instruction::Mul:
4306 case Instruction::Shl:
4308 return isa<ConstantInt>(
I->getOperand(1));
4309 case Instruction::GetElementPtr:
4322 Instruction *PromotedInst = dyn_cast<Instruction>(Val);
4337class TypePromotionHelper {
4340 static void addPromotedInst(InstrToOrigTy &PromotedInsts,
4342 ExtType ExtTy = IsSExt ? SignExtension : ZeroExtension;
4343 InstrToOrigTy::iterator It = PromotedInsts.find(ExtOpnd);
4344 if (It != PromotedInsts.end()) {
4347 if (It->second.getInt() == ExtTy)
4353 ExtTy = BothExtension;
4355 PromotedInsts[ExtOpnd] = TypeIsSExt(ExtOpnd->
getType(), ExtTy);
4362 static const Type *getOrigType(
const InstrToOrigTy &PromotedInsts,
4364 ExtType ExtTy = IsSExt ? SignExtension : ZeroExtension;
4365 InstrToOrigTy::const_iterator It = PromotedInsts.find(Opnd);
4366 if (It != PromotedInsts.end() && It->second.getInt() == ExtTy)
4367 return It->second.getPointer();
4382 static bool canGetThrough(
const Instruction *Inst,
Type *ConsideredExtType,
4383 const InstrToOrigTy &PromotedInsts,
bool IsSExt);
4387 static bool shouldExtOperand(
const Instruction *Inst,
int OpIdx) {
4388 return !(isa<SelectInst>(Inst) && OpIdx == 0);
4400 static Value *promoteOperandForTruncAndAnyExt(
4402 InstrToOrigTy &PromotedInsts,
unsigned &CreatedInstsCost,
4416 TypePromotionTransaction &TPT,
4417 InstrToOrigTy &PromotedInsts,
4418 unsigned &CreatedInstsCost,
4424 static Value *signExtendOperandForOther(
4426 InstrToOrigTy &PromotedInsts,
unsigned &CreatedInstsCost,
4429 return promoteOperandForOther(Ext, TPT, PromotedInsts, CreatedInstsCost,
4430 Exts, Truncs, TLI,
true);
4434 static Value *zeroExtendOperandForOther(
4436 InstrToOrigTy &PromotedInsts,
unsigned &CreatedInstsCost,
4439 return promoteOperandForOther(Ext, TPT, PromotedInsts, CreatedInstsCost,
4440 Exts, Truncs, TLI,
false);
4446 InstrToOrigTy &PromotedInsts,
4447 unsigned &CreatedInstsCost,
4463 const InstrToOrigTy &PromotedInsts);
4468bool TypePromotionHelper::canGetThrough(
const Instruction *Inst,
4469 Type *ConsideredExtType,
4470 const InstrToOrigTy &PromotedInsts,
4479 if (isa<ZExtInst>(Inst))
4483 if (IsSExt && isa<SExtInst>(Inst))
4488 if (
const auto *BinOp = dyn_cast<BinaryOperator>(Inst))
4489 if (isa<OverflowingBinaryOperator>(BinOp) &&
4490 ((!IsSExt && BinOp->hasNoUnsignedWrap()) ||
4491 (IsSExt && BinOp->hasNoSignedWrap())))
4495 if ((Inst->
getOpcode() == Instruction::And ||
4500 if (Inst->
getOpcode() == Instruction::Xor) {
4502 if (
const auto *Cst = dyn_cast<ConstantInt>(Inst->
getOperand(1)))
4503 if (!Cst->getValue().isAllOnes())
4512 if (Inst->
getOpcode() == Instruction::LShr && !IsSExt)
4521 const auto *ExtInst = cast<const Instruction>(*Inst->
user_begin());
4522 if (ExtInst->hasOneUse()) {
4523 const auto *AndInst = dyn_cast<const Instruction>(*ExtInst->user_begin());
4524 if (AndInst && AndInst->getOpcode() == Instruction::And) {
4525 const auto *Cst = dyn_cast<ConstantInt>(AndInst->getOperand(1));
4535 if (!isa<TruncInst>(Inst))
4549 Instruction *Opnd = dyn_cast<Instruction>(OpndVal);
4557 const Type *OpndType = getOrigType(PromotedInsts, Opnd, IsSExt);
4560 else if ((IsSExt && isa<SExtInst>(Opnd)) || (!IsSExt && isa<ZExtInst>(Opnd)))
4570TypePromotionHelper::Action TypePromotionHelper::getAction(
4571 Instruction *Ext,
const SetOfInstrs &InsertedInsts,
4573 assert((isa<SExtInst>(Ext) || isa<ZExtInst>(Ext)) &&
4574 "Unexpected instruction type");
4575 Instruction *ExtOpnd = dyn_cast<Instruction>(
Ext->getOperand(0));
4577 bool IsSExt = isa<SExtInst>(Ext);
4581 if (!ExtOpnd || !canGetThrough(ExtOpnd, ExtTy, PromotedInsts, IsSExt))
4587 if (isa<TruncInst>(ExtOpnd) && InsertedInsts.count(ExtOpnd))
4592 if (isa<SExtInst>(ExtOpnd) || isa<TruncInst>(ExtOpnd) ||
4593 isa<ZExtInst>(ExtOpnd))
4594 return promoteOperandForTruncAndAnyExt;
4600 return IsSExt ? signExtendOperandForOther : zeroExtendOperandForOther;
4603Value *TypePromotionHelper::promoteOperandForTruncAndAnyExt(
4605 InstrToOrigTy &PromotedInsts,
unsigned &CreatedInstsCost,
4611 Value *ExtVal = SExt;
4612 bool HasMergedNonFreeExt =
false;
4613 if (isa<ZExtInst>(SExtOpnd)) {
4616 HasMergedNonFreeExt = !TLI.
isExtFree(SExtOpnd);
4620 TPT.eraseInstruction(SExt);
4625 TPT.setOperand(SExt, 0, SExtOpnd->
getOperand(0));
4627 CreatedInstsCost = 0;
4631 TPT.eraseInstruction(SExtOpnd);
4634 Instruction *ExtInst = dyn_cast<Instruction>(ExtVal);
4639 CreatedInstsCost = !TLI.
isExtFree(ExtInst) && !HasMergedNonFreeExt;
4647 TPT.eraseInstruction(ExtInst, NextVal);
4651Value *TypePromotionHelper::promoteOperandForOther(
4653 InstrToOrigTy &PromotedInsts,
unsigned &CreatedInstsCost,
4660 CreatedInstsCost = 0;
4666 Value *Trunc = TPT.createTrunc(Ext, ExtOpnd->
getType());
4667 if (
Instruction *ITrunc = dyn_cast<Instruction>(Trunc)) {
4669 ITrunc->moveAfter(ExtOpnd);
4674 TPT.replaceAllUsesWith(ExtOpnd, Trunc);
4677 TPT.setOperand(Ext, 0, ExtOpnd);
4687 addPromotedInst(PromotedInsts, ExtOpnd, IsSExt);
4689 TPT.mutateType(ExtOpnd,
Ext->getType());
4691 TPT.replaceAllUsesWith(Ext, ExtOpnd);
4694 for (
int OpIdx = 0, EndOpIdx = ExtOpnd->
getNumOperands(); OpIdx != EndOpIdx;
4698 !shouldExtOperand(ExtOpnd, OpIdx)) {
4704 if (
const ConstantInt *Cst = dyn_cast<ConstantInt>(Opnd)) {
4706 unsigned BitWidth =
Ext->getType()->getIntegerBitWidth();
4709 TPT.setOperand(ExtOpnd, OpIdx, ConstantInt::get(
Ext->getType(), CstVal));
4713 if (isa<UndefValue>(Opnd)) {
4720 Value *ValForExtOpnd = IsSExt
4721 ? TPT.createSExt(ExtOpnd, Opnd,
Ext->getType())
4722 : TPT.createZExt(ExtOpnd, Opnd,
Ext->getType());
4723 TPT.setOperand(ExtOpnd, OpIdx, ValForExtOpnd);
4724 Instruction *InstForExtOpnd = dyn_cast<Instruction>(ValForExtOpnd);
4725 if (!InstForExtOpnd)
4731 CreatedInstsCost += !TLI.
isExtFree(InstForExtOpnd);
4734 TPT.eraseInstruction(Ext);
4746bool AddressingModeMatcher::isPromotionProfitable(
4747 unsigned NewCost,
unsigned OldCost,
Value *PromotedOperand)
const {
4748 LLVM_DEBUG(
dbgs() <<
"OldCost: " << OldCost <<
"\tNewCost: " << NewCost
4753 if (NewCost > OldCost)
4755 if (NewCost < OldCost)
4774bool AddressingModeMatcher::matchOperationAddr(
User *AddrInst,
unsigned Opcode,
4786 case Instruction::PtrToInt:
4789 case Instruction::IntToPtr: {
4797 case Instruction::BitCast:
4807 case Instruction::AddrSpaceCast: {
4815 case Instruction::Add: {
4819 unsigned OldSize = AddrModeInsts.
size();
4824 TypePromotionTransaction::ConstRestorationPt LastKnownGood =
4825 TPT.getRestorationPoint();
4829 int First = 0, Second = 1;
4831 && !isa<ConstantInt>(AddrInst->
getOperand(Second)))
4840 AddrModeInsts.
resize(OldSize);
4841 TPT.rollback(LastKnownGood);
4851 AddrModeInsts.
resize(OldSize);
4852 TPT.rollback(LastKnownGood);
4858 case Instruction::Mul:
4859 case Instruction::Shl: {
4863 if (!RHS ||
RHS->getBitWidth() > 64)
4865 int64_t Scale = Opcode == Instruction::Shl
4866 ? 1LL <<
RHS->getLimitedValue(
RHS->getBitWidth() - 1)
4867 :
RHS->getSExtValue();
4871 case Instruction::GetElementPtr: {
4874 int VariableOperand = -1;
4875 unsigned VariableScale = 0;
4877 int64_t ConstantOffset = 0;
4879 for (
unsigned i = 1, e = AddrInst->
getNumOperands(); i != e; ++i, ++GTI) {
4883 cast<ConstantInt>(AddrInst->
getOperand(i))->getZExtValue();
4893 dyn_cast<ConstantInt>(AddrInst->
getOperand(i))) {
4901 if (VariableOperand != -1)
4905 VariableOperand = i;
4913 if (VariableOperand == -1) {
4914 AddrMode.BaseOffs += ConstantOffset;
4916 if (!cast<GEPOperator>(AddrInst)->isInBounds())
4920 AddrMode.BaseOffs -= ConstantOffset;
4924 ConstantOffset > 0) {
4930 auto *BaseI = dyn_cast<Instruction>(
Base);
4931 auto *
GEP = cast<GetElementPtrInst>(AddrInst);
4932 if (isa<Argument>(
Base) || isa<GlobalValue>(
Base) ||
4933 (BaseI && !isa<CastInst>(BaseI) &&
4934 !isa<GetElementPtrInst>(BaseI))) {
4938 : &
GEP->getFunction()->getEntryBlock();
4940 LargeOffsetGEP = std::make_pair(
GEP, ConstantOffset);
4949 unsigned OldSize = AddrModeInsts.
size();
4952 AddrMode.BaseOffs += ConstantOffset;
4953 if (!cast<GEPOperator>(AddrInst)->isInBounds())
4961 AddrModeInsts.
resize(OldSize);
4969 if (!matchScaledValue(AddrInst->
getOperand(VariableOperand), VariableScale,
4974 AddrModeInsts.
resize(OldSize);
4979 AddrMode.BaseOffs += ConstantOffset;
4980 if (!matchScaledValue(AddrInst->
getOperand(VariableOperand),
4981 VariableScale,
Depth)) {
4984 AddrModeInsts.
resize(OldSize);
4991 case Instruction::SExt:
4992 case Instruction::ZExt: {
4999 TypePromotionHelper::Action TPH =
5000 TypePromotionHelper::getAction(Ext, InsertedInsts, TLI, PromotedInsts);
5004 TypePromotionTransaction::ConstRestorationPt LastKnownGood =
5005 TPT.getRestorationPoint();
5006 unsigned CreatedInstsCost = 0;
5008 Value *PromotedOperand =
5009 TPH(Ext, TPT, PromotedInsts, CreatedInstsCost,
nullptr,
nullptr, TLI);
5024 assert(PromotedOperand &&
5025 "TypePromotionHelper should have filtered out those cases");
5028 unsigned OldSize = AddrModeInsts.
size();
5030 if (!matchAddr(PromotedOperand,
Depth) ||
5035 !isPromotionProfitable(CreatedInstsCost,
5036 ExtCost + (AddrModeInsts.
size() - OldSize),
5039 AddrModeInsts.
resize(OldSize);
5040 LLVM_DEBUG(
dbgs() <<
"Sign extension does not pay off: rollback\n");
5041 TPT.rollback(LastKnownGood);
5055bool AddressingModeMatcher::matchAddr(
Value *
Addr,
unsigned Depth) {
5058 TypePromotionTransaction::ConstRestorationPt LastKnownGood =
5059 TPT.getRestorationPoint();
5078 unsigned OldSize = AddrModeInsts.
size();
5081 bool MovedAway =
false;
5082 if (matchOperationAddr(
I,
I->getOpcode(),
Depth, &MovedAway)) {
5090 if (
I->hasOneUse() ||
5091 isProfitableToFoldIntoAddressingMode(
I, BackupAddrMode,
AddrMode)) {
5098 AddrModeInsts.
resize(OldSize);
5099 TPT.rollback(LastKnownGood);
5102 if (matchOperationAddr(CE,
CE->getOpcode(),
Depth))
5104 TPT.rollback(LastKnownGood);
5105 }
else if (isa<ConstantPointerNull>(
Addr)) {
5131 TPT.rollback(LastKnownGood);
5150 if (OpInfo.CallOperandVal == OpVal &&
5152 !OpInfo.isIndirect))
5168 if (!ConsideredInsts.
insert(
I).second)
5176 for (
Use &U :
I->uses()) {
5182 Instruction *UserI = cast<Instruction>(U.getUser());
5183 if (
LoadInst *LI = dyn_cast<LoadInst>(UserI)) {
5184 MemoryUses.push_back({&U, LI->getType()});
5188 if (
StoreInst *SI = dyn_cast<StoreInst>(UserI)) {
5191 MemoryUses.push_back({&U, SI->getValueOperand()->
getType()});
5198 MemoryUses.push_back({&U, RMW->getValOperand()->
getType()});
5205 MemoryUses.push_back({&U, CmpX->getCompareOperand()->
getType()});
5209 if (
CallInst *CI = dyn_cast<CallInst>(UserI)) {
5210 if (CI->hasFnAttr(Attribute::Cold)) {
5219 InlineAsm *IA = dyn_cast<InlineAsm>(CI->getCalledOperand());
5230 PSI, BFI, SeenInsts))
5241 unsigned SeenInsts = 0;
5244 PSI, BFI, SeenInsts);
5252bool AddressingModeMatcher::valueAlreadyLiveAtInst(
Value *Val,
5254 Value *KnownLive2) {
5256 if (Val ==
nullptr || Val == KnownLive1 || Val == KnownLive2)
5260 if (!isa<Instruction>(Val) && !isa<Argument>(Val))
5266 if (
AllocaInst *AI = dyn_cast<AllocaInst>(Val))
5297bool AddressingModeMatcher::isProfitableToFoldIntoAddressingMode(
5299 if (IgnoreProfitability)
5317 if (valueAlreadyLiveAtInst(ScaledReg, AMBefore.
BaseReg, AMBefore.
ScaledReg))
5318 ScaledReg =
nullptr;
5322 if (!BaseReg && !ScaledReg)
5343 for (
const std::pair<Use *, Type *> &Pair : MemoryUses) {
5345 Instruction *UserI = cast<Instruction>(Pair.first->getUser());
5346 Type *AddressAccessTy = Pair.second;
5347 unsigned AS =
Address->getType()->getPointerAddressSpace();
5353 std::pair<AssertingVH<GetElementPtrInst>, int64_t> LargeOffsetGEP(
nullptr,
5355 TypePromotionTransaction::ConstRestorationPt LastKnownGood =
5356 TPT.getRestorationPoint();
5357 AddressingModeMatcher Matcher(MatchedAddrModeInsts, TLI,
TRI, LI, getDTFn,
5358 AddressAccessTy, AS, UserI, Result,
5359 InsertedInsts, PromotedInsts, TPT,
5360 LargeOffsetGEP, OptSize, PSI, BFI);
5361 Matcher.IgnoreProfitability =
true;
5362 bool Success = Matcher.matchAddr(Address, 0);
5369 TPT.rollback(LastKnownGood);
5375 MatchedAddrModeInsts.
clear();
5385 return I->getParent() != BB;
5409 Type *AccessTy,
unsigned AddrSpace) {
5421 bool PhiOrSelectSeen =
false;
5424 AddressingModeCombiner AddrModes(SQ,
Addr);
5425 TypePromotionTransaction TPT(RemovedInsts);
5426 TypePromotionTransaction::ConstRestorationPt LastKnownGood =
5427 TPT.getRestorationPoint();
5428 while (!worklist.
empty()) {
5440 if (!Visited.
insert(V).second)
5444 if (
PHINode *
P = dyn_cast<PHINode>(V)) {
5446 PhiOrSelectSeen =
true;
5450 if (
SelectInst *SI = dyn_cast<SelectInst>(V)) {
5453 PhiOrSelectSeen =
true;
5460 AddrModeInsts.
clear();
5461 std::pair<AssertingVH<GetElementPtrInst>, int64_t> LargeOffsetGEP(
nullptr,
5466 auto getDTFn = [MemoryInst,
this]() ->
const DominatorTree & {
5468 return this->getDT(*
F);
5470 ExtAddrMode NewAddrMode = AddressingModeMatcher::Match(
5471 V, AccessTy, AddrSpace, MemoryInst, AddrModeInsts, *TLI, *LI, getDTFn,
5472 *
TRI, InsertedInsts, PromotedInsts, TPT, LargeOffsetGEP, OptSize, PSI,
5480 LargeOffsetGEPMap[
GEP->getPointerOperand()].push_back(LargeOffsetGEP);
5481 LargeOffsetGEPID.
insert(std::make_pair(
GEP, LargeOffsetGEPID.
size()));
5484 NewAddrMode.OriginalValue =
V;
5485 if (!AddrModes.addNewAddrMode(NewAddrMode))
5492 if (!AddrModes.combineAddrModes()) {
5493 TPT.rollback(LastKnownGood);
5505 if (!PhiOrSelectSeen &&
none_of(AddrModeInsts, [&](
Value *V) {
5527 Type *IntPtrTy =
DL->getIntPtrType(
Addr->getType());
5530 <<
" for " << *MemoryInst <<
"\n");
5533 Addr->getType()->getPointerAddressSpace() &&
5534 !
DL->isNonIntegralPointerType(
Addr->getType())) {
5540 SunkAddr = Builder.CreatePtrToInt(SunkAddr, IntPtrTy,
"sunkaddr");
5542 Builder.CreateIntToPtr(SunkAddr,
Addr->getType(),
"sunkaddr");
5544 SunkAddr = Builder.CreatePointerCast(SunkAddr,
Addr->getType());
5551 <<
" for " << *MemoryInst <<
"\n");
5552 Value *ResultPtr =
nullptr, *ResultIndex =
nullptr;
5563 if (ResultPtr ||
AddrMode.Scale != 1)
5594 if (!
DL->isNonIntegralPointerType(
Addr->getType())) {
5595 if (!ResultPtr &&
AddrMode.BaseReg) {
5596 ResultPtr = Builder.CreateIntToPtr(
AddrMode.BaseReg,
Addr->getType(),
5599 }
else if (!ResultPtr &&
AddrMode.Scale == 1) {
5600 ResultPtr = Builder.CreateIntToPtr(
AddrMode.ScaledReg,
Addr->getType(),
5609 }
else if (!ResultPtr) {
5613 Builder.getPtrTy(
Addr->getType()->getPointerAddressSpace());
5622 if (
V->getType() != IntPtrTy)
5623 V = Builder.CreateIntCast(V, IntPtrTy,
true,
"sunkaddr");
5631 if (
V->getType() == IntPtrTy) {
5635 cast<IntegerType>(
V->getType())->getBitWidth() &&
5636 "We can't transform if ScaledReg is too narrow");
5637 V = Builder.CreateTrunc(V, IntPtrTy,
"sunkaddr");
5641 V = Builder.CreateMul(V, ConstantInt::get(IntPtrTy,
AddrMode.Scale),
5644 ResultIndex = Builder.CreateAdd(ResultIndex, V,
"sunkaddr");
5655 if (ResultPtr->
getType() != I8PtrTy)
5656 ResultPtr = Builder.CreatePointerCast(ResultPtr, I8PtrTy);
5657 ResultPtr = Builder.CreatePtrAdd(ResultPtr, ResultIndex,
"sunkaddr",
5665 SunkAddr = ResultPtr;
5667 if (ResultPtr->
getType() != I8PtrTy)
5668 ResultPtr = Builder.CreatePointerCast(ResultPtr, I8PtrTy);
5669 SunkAddr = Builder.CreatePtrAdd(ResultPtr, ResultIndex,
"sunkaddr",
5675 Addr->getType()->getPointerAddressSpace() &&
5676 !
DL->isNonIntegralPointerType(
Addr->getType())) {
5682 SunkAddr = Builder.CreatePtrToInt(SunkAddr, IntPtrTy,
"sunkaddr");
5684 Builder.CreateIntToPtr(SunkAddr,
Addr->getType(),
"sunkaddr");
5686 SunkAddr = Builder.CreatePointerCast(SunkAddr,
Addr->getType());
5695 PointerType *ScalePtrTy = dyn_cast_or_null<PointerType>(ScaleTy);
5696 if (
DL->isNonIntegralPointerType(
Addr->getType()) ||
5697 (BasePtrTy &&
DL->isNonIntegralPointerType(BasePtrTy)) ||
5698 (ScalePtrTy &&
DL->isNonIntegralPointerType(ScalePtrTy)) ||
5700 DL->isNonIntegralPointerType(
AddrMode.BaseGV->getType())))
5704 <<
" for " << *MemoryInst <<
"\n");
5705 Type *IntPtrTy =
DL->getIntPtrType(
Addr->getType());
5715 if (
V->getType()->isPointerTy())
5716 V = Builder.CreatePtrToInt(V, IntPtrTy,
"sunkaddr");
5717 if (
V->getType() != IntPtrTy)
5718 V = Builder.CreateIntCast(V, IntPtrTy,
true,
"sunkaddr");
5725 if (
V->getType() == IntPtrTy) {
5727 }
else if (
V->getType()->isPointerTy()) {
5728 V = Builder.CreatePtrToInt(V, IntPtrTy,
"sunkaddr");
5729 }
else if (cast<IntegerType>(IntPtrTy)->
getBitWidth() <
5730 cast<IntegerType>(
V->getType())->getBitWidth()) {
5731 V = Builder.CreateTrunc(V, IntPtrTy,
"sunkaddr");
5738 Instruction *
I = dyn_cast_or_null<Instruction>(Result);
5740 I->eraseFromParent();
5744 V = Builder.CreateMul(V, ConstantInt::get(IntPtrTy,
AddrMode.Scale),
5747 Result = Builder.CreateAdd(Result, V,
"sunkaddr");
5754 Value *
V = Builder.CreatePtrToInt(
AddrMode.BaseGV, IntPtrTy,
"sunkaddr");
5756 Result = Builder.CreateAdd(Result, V,
"sunkaddr");
5765 Result = Builder.CreateAdd(Result, V,
"sunkaddr");
5773 SunkAddr = Builder.CreateIntToPtr(Result,
Addr->getType(),
"sunkaddr");
5784 resetIteratorIfInvalidatedWhileCalling(CurInstIterator->getParent(), [&]() {
5785 RecursivelyDeleteTriviallyDeadInstructions(
5786 Repl, TLInfo, nullptr,
5787 [&](Value *V) { removeAllAssertingVHReferences(V); });
5811bool CodeGenPrepare::optimizeGatherScatterInst(
Instruction *MemoryInst,
5815 if (
const auto *
GEP = dyn_cast<GetElementPtrInst>(
Ptr)) {
5817 if (!
GEP->hasIndices())
5827 bool RewriteGEP =
false;
5829 if (Ops[0]->
getType()->isVectorTy()) {
5836 unsigned FinalIndex = Ops.size() - 1;
5841 for (
unsigned i = 1; i < FinalIndex; ++i) {
5842 auto *
C = dyn_cast<Constant>(Ops[i]);
5845 if (isa<VectorType>(
C->getType()))
5846 C =
C->getSplatValue();
5847 auto *CI = dyn_cast_or_null<ConstantInt>(
C);
5848 if (!CI || !CI->
isZero())
5855 if (Ops[FinalIndex]->
getType()->isVectorTy()) {
5857 auto *
C = dyn_cast<ConstantInt>(V);
5859 if (!
C || !
C->isZero()) {
5860 Ops[FinalIndex] =
V;
5868 if (!RewriteGEP && Ops.size() == 2)
5871 auto NumElts = cast<VectorType>(
Ptr->getType())->getElementCount();
5875 Type *SourceTy =
GEP->getSourceElementType();
5876 Type *ScalarIndexTy =
DL->getIndexType(Ops[0]->
getType()->getScalarType());
5880 if (!Ops[FinalIndex]->
getType()->isVectorTy()) {
5881 NewAddr = Builder.CreateGEP(SourceTy, Ops[0],
ArrayRef(Ops).drop_front());
5882 auto *IndexTy = VectorType::get(ScalarIndexTy, NumElts);
5884 SourceTy,
ArrayRef(Ops).drop_front());
5892 if (Ops.size() != 2) {
5898 SourceTy,
ArrayRef(Ops).drop_front());
5902 NewAddr = Builder.CreateGEP(SourceTy,
Base,
Index);
5904 }
else if (!isa<Constant>(
Ptr)) {
5911 auto NumElts = cast<VectorType>(
Ptr->getType())->getElementCount();
5916 Type *ScalarIndexTy =
DL->getIndexType(
V->getType()->getScalarType());
5917 auto *IndexTy = VectorType::get(ScalarIndexTy, NumElts);
5920 Intrinsic::masked_gather) {
5924 Intrinsic::masked_scatter);
5937 if (
Ptr->use_empty())
5939 Ptr, TLInfo,
nullptr,
5940 [&](
Value *V) { removeAllAssertingVHReferences(V); });
5947bool CodeGenPrepare::optimizeInlineAsmInst(
CallInst *CS) {
5948 bool MadeChange =
false;
5951 TM->getSubtargetImpl(*CS->
getFunction())->getRegisterInfo();
5961 OpInfo.isIndirect) {
5963 MadeChange |= optimizeMemoryInst(CS, OpVal, OpVal->
getType(), ~0u);
5976 bool IsSExt = isa<SExtInst>(FirstUser);
5980 if ((IsSExt && !isa<SExtInst>(UI)) || (!IsSExt && !isa<ZExtInst>(UI)))
6026bool CodeGenPrepare::tryToPromoteExts(
6029 unsigned CreatedInstsCost) {
6030 bool Promoted =
false;
6033 for (
auto *
I : Exts) {
6035 if (isa<LoadInst>(
I->getOperand(0))) {
6048 TypePromotionHelper::Action TPH =
6049 TypePromotionHelper::getAction(
I, InsertedInsts, *TLI, PromotedInsts);
6058 TypePromotionTransaction::ConstRestorationPt LastKnownGood =
6059 TPT.getRestorationPoint();
6061 unsigned NewCreatedInstsCost = 0;
6064 Value *PromotedVal = TPH(
I, TPT, PromotedInsts, NewCreatedInstsCost,
6065 &NewExts,
nullptr, *TLI);
6067 "TypePromotionHelper should have filtered out those cases");
6077 long long TotalCreatedInstsCost = CreatedInstsCost + NewCreatedInstsCost;
6080 TotalCreatedInstsCost =
6081 std::max((
long long)0, (TotalCreatedInstsCost - ExtCost));
6083 (TotalCreatedInstsCost > 1 ||
6085 (ExtCost == 0 && NewExts.
size() > 1))) {
6089 TPT.rollback(LastKnownGood);
6095 (void)tryToPromoteExts(TPT, NewExts, NewlyMovedExts, TotalCreatedInstsCost);
6096 bool NewPromoted =
false;
6097 for (
auto *ExtInst : NewlyMovedExts) {
6098 Instruction *MovedExt = cast<Instruction>(ExtInst);
6102 if (isa<LoadInst>(ExtOperand) &&
6107 ProfitablyMovedExts.
push_back(MovedExt);
6114 TPT.rollback(LastKnownGood);
6125bool CodeGenPrepare::mergeSExts(
Function &
F) {
6126 bool Changed =
false;
6127 for (
auto &Entry : ValToSExtendedUses) {
6128 SExts &Insts = Entry.second;
6131 if (RemovedInsts.count(Inst) || !isa<SExtInst>(Inst) ||
6134 bool inserted =
false;
6135 for (
auto &Pt : CurPts) {
6138 RemovedInsts.insert(Pt);
6139 Pt->removeFromParent();
6150 RemovedInsts.insert(Inst);
6157 CurPts.push_back(Inst);
6199bool CodeGenPrepare::splitLargeGEPOffsets() {
6200 bool Changed =
false;
6201 for (
auto &Entry : LargeOffsetGEPMap) {
6202 Value *OldBase = Entry.first;
6204 &LargeOffsetGEPs = Entry.second;
6205 auto compareGEPOffset =
6206 [&](
const std::pair<GetElementPtrInst *, int64_t> &
LHS,
6207 const std::pair<GetElementPtrInst *, int64_t> &
RHS) {
6208 if (
LHS.first ==
RHS.first)
6210 if (
LHS.second !=
RHS.second)
6211 return LHS.second <
RHS.second;
6212 return LargeOffsetGEPID[
LHS.first] < LargeOffsetGEPID[
RHS.first];
6215 llvm::sort(LargeOffsetGEPs, compareGEPOffset);
6216 LargeOffsetGEPs.
erase(
6217 std::unique(LargeOffsetGEPs.
begin(), LargeOffsetGEPs.
end()),
6218 LargeOffsetGEPs.
end());
6220 if (LargeOffsetGEPs.
front().second == LargeOffsetGEPs.
back().second)
6223 int64_t BaseOffset = LargeOffsetGEPs.
begin()->second;
6224 Value *NewBaseGEP =
nullptr;
6226 auto createNewBase = [&](int64_t BaseOffset,
Value *OldBase,
6229 Type *PtrIdxTy =
DL->getIndexType(
GEP->getType());
6231 PointerType::get(Ctx,
GEP->getType()->getPointerAddressSpace());
6235 if (
auto *BaseI = dyn_cast<Instruction>(OldBase)) {
6239 if (isa<PHINode>(BaseI))
6241 else if (
InvokeInst *Invoke = dyn_cast<InvokeInst>(BaseI)) {
6243 SplitEdge(NewBaseInsertBB, Invoke->getNormalDest(), DT.get(), LI);
6246 NewBaseInsertPt = std::next(BaseI->getIterator());
6253 IRBuilder<> NewBaseBuilder(NewBaseInsertBB, NewBaseInsertPt);
6255 Value *BaseIndex = ConstantInt::get(PtrIdxTy, BaseOffset);
6256 NewBaseGEP = OldBase;
6257 if (NewBaseGEP->
getType() != I8PtrTy)
6258 NewBaseGEP = NewBaseBuilder.CreatePointerCast(NewBaseGEP, I8PtrTy);
6260 NewBaseBuilder.CreatePtrAdd(NewBaseGEP, BaseIndex,
"splitgep");
6261 NewGEPBases.
insert(NewBaseGEP);
6267 LargeOffsetGEPs.
front().second, LargeOffsetGEPs.
back().second)) {
6268 BaseOffset = PreferBase;
6271 createNewBase(BaseOffset, OldBase, BaseGEP);
6274 auto *LargeOffsetGEP = LargeOffsetGEPs.
begin();
6275 while (LargeOffsetGEP != LargeOffsetGEPs.
end()) {
6277 int64_t
Offset = LargeOffsetGEP->second;
6278 if (
Offset != BaseOffset) {
6285 GEP->getResultElementType(),
6286 GEP->getAddressSpace())) {
6292 NewBaseGEP =
nullptr;
6297 Type *PtrIdxTy =
DL->getIndexType(
GEP->getType());
6302 createNewBase(BaseOffset, OldBase,
GEP);
6306 Value *NewGEP = NewBaseGEP;
6307 if (
Offset != BaseOffset) {
6310 NewGEP = Builder.CreatePtrAdd(NewBaseGEP,
Index);
6314 LargeOffsetGEP = LargeOffsetGEPs.
erase(LargeOffsetGEP);
6315 GEP->eraseFromParent();
6322bool CodeGenPrepare::optimizePhiType(
6329 Type *PhiTy =
I->getType();
6330 Type *ConvertTy =
nullptr;
6332 (!
I->getType()->isIntegerTy() && !
I->getType()->isFloatingPointTy()))
6348 bool AnyAnchored =
false;
6350 while (!Worklist.
empty()) {
6353 if (
auto *Phi = dyn_cast<PHINode>(II)) {
6355 for (
Value *V :
Phi->incoming_values()) {
6356 if (
auto *OpPhi = dyn_cast<PHINode>(V)) {
6357 if (!PhiNodes.
count(OpPhi)) {
6358 if (!Visited.
insert(OpPhi).second)
6363 }
else if (
auto *OpLoad = dyn_cast<LoadInst>(V)) {
6364 if (!OpLoad->isSimple())
6366 if (Defs.
insert(OpLoad).second)
6368 }
else if (
auto *OpEx = dyn_cast<ExtractElementInst>(V)) {
6369 if (Defs.
insert(OpEx).second)
6371 }
else if (
auto *OpBC = dyn_cast<BitCastInst>(V)) {
6373 ConvertTy = OpBC->getOperand(0)->getType();
6374 if (OpBC->getOperand(0)->getType() != ConvertTy)
6376 if (Defs.
insert(OpBC).second) {
6378 AnyAnchored |= !isa<LoadInst>(OpBC->getOperand(0)) &&
6379 !isa<ExtractElementInst>(OpBC->getOperand(0));
6381 }
else if (
auto *OpC = dyn_cast<ConstantData>(V))
6390 if (
auto *OpPhi = dyn_cast<PHINode>(V)) {
6391 if (!PhiNodes.
count(OpPhi)) {
6392 if (Visited.
count(OpPhi))
6398 }
else if (
auto *OpStore = dyn_cast<StoreInst>(V)) {
6399 if (!OpStore->isSimple() || OpStore->getOperand(0) != II)
6401 Uses.insert(OpStore);
6402 }
else if (
auto *OpBC = dyn_cast<BitCastInst>(V)) {
6404 ConvertTy = OpBC->getType();
6405 if (OpBC->getType() != ConvertTy)
6409 any_of(OpBC->users(), [](
User *U) { return !isa<StoreInst>(U); });
6416 if (!ConvertTy || !AnyAnchored ||
6420 LLVM_DEBUG(
dbgs() <<
"Converting " << *
I <<
"\n and connected nodes to "
6421 << *ConvertTy <<
"\n");
6429 if (isa<BitCastInst>(
D)) {
6430 ValMap[
D] =
D->getOperand(0);
6434 new BitCastInst(
D, ConvertTy,
D->getName() +
".bc",
D->getNextNode());
6439 Phi->getName() +
".tc",
Phi->getIterator());
6441 for (
PHINode *Phi : PhiNodes) {
6442 PHINode *NewPhi = cast<PHINode>(ValMap[Phi]);
6443 for (
int i = 0, e =
Phi->getNumIncomingValues(); i < e; i++)
6445 Phi->getIncomingBlock(i));
6450 if (isa<BitCastInst>(U)) {
6455 new BitCastInst(ValMap[
U->getOperand(0)], PhiTy,
"bc", U));
6461 DeletedInstrs.
insert(Phi);
6465bool CodeGenPrepare::optimizePhiTypes(
Function &
F) {
6469 bool Changed =
false;
6475 for (
auto &Phi : BB.
phis())
6476 Changed |= optimizePhiType(&Phi, Visited, DeletedInstrs);
6479 for (
auto *
I : DeletedInstrs) {
6481 I->eraseFromParent();
6489bool CodeGenPrepare::canFormExtLd(
6492 for (
auto *MovedExtInst : MovedExts) {
6493 if (isa<LoadInst>(MovedExtInst->getOperand(0))) {
6494 LI = cast<LoadInst>(MovedExtInst->getOperand(0));
6495 Inst = MovedExtInst;
6547bool CodeGenPrepare::optimizeExt(
Instruction *&Inst) {
6548 bool AllowPromotionWithoutCommonHeader =
false;
6553 *Inst, AllowPromotionWithoutCommonHeader);
6554 TypePromotionTransaction TPT(RemovedInsts);
6555 TypePromotionTransaction::ConstRestorationPt LastKnownGood =
6556 TPT.getRestorationPoint();
6561 bool HasPromoted = tryToPromoteExts(TPT, Exts, SpeculativelyMovedExts);
6569 if (canFormExtLd(SpeculativelyMovedExts, LI, ExtFedByLoad, HasPromoted)) {
6570 assert(LI && ExtFedByLoad &&
"Expect a valid load and extension");
6575 Inst = ExtFedByLoad;
6580 if (ATPConsiderable &&
6581 performAddressTypePromotion(Inst, AllowPromotionWithoutCommonHeader,
6582 HasPromoted, TPT, SpeculativelyMovedExts))
6585 TPT.rollback(LastKnownGood);
6594bool CodeGenPrepare::performAddressTypePromotion(
6595 Instruction *&Inst,
bool AllowPromotionWithoutCommonHeader,
6596 bool HasPromoted, TypePromotionTransaction &TPT,
6598 bool Promoted =
false;
6600 bool AllSeenFirst =
true;
6601 for (
auto *
I : SpeculativelyMovedExts) {
6602 Value *HeadOfChain =
I->getOperand(0);
6604 SeenChainsForSExt.
find(HeadOfChain);
6607 if (AlreadySeen != SeenChainsForSExt.
end()) {
6608 if (AlreadySeen->second !=
nullptr)
6609 UnhandledExts.
insert(AlreadySeen->second);
6610 AllSeenFirst =
false;
6614 if (!AllSeenFirst || (AllowPromotionWithoutCommonHeader &&
6615 SpeculativelyMovedExts.size() == 1)) {
6619 for (
auto *
I : SpeculativelyMovedExts) {
6620 Value *HeadOfChain =
I->getOperand(0);
6621 SeenChainsForSExt[HeadOfChain] =
nullptr;
6622 ValToSExtendedUses[HeadOfChain].push_back(
I);
6625 Inst = SpeculativelyMovedExts.pop_back_val();
6630 for (
auto *
I : SpeculativelyMovedExts) {
6631 Value *HeadOfChain =
I->getOperand(0);
6632 SeenChainsForSExt[HeadOfChain] = Inst;
6637 if (!AllSeenFirst && !UnhandledExts.
empty())
6638 for (
auto *VisitedSExt : UnhandledExts) {
6639 if (RemovedInsts.count(VisitedSExt))
6641 TypePromotionTransaction TPT(RemovedInsts);
6645 bool HasPromoted = tryToPromoteExts(TPT, Exts, Chains);
6649 for (
auto *
I : Chains) {
6650 Value *HeadOfChain =
I->getOperand(0);
6652 SeenChainsForSExt[HeadOfChain] =
nullptr;
6653 ValToSExtendedUses[HeadOfChain].push_back(
I);
6664 Value *Src =
I->getOperand(0);
6665 if (Src->hasOneUse())
6674 if (!isa<Instruction>(Src) || DefBB != cast<Instruction>(Src)->
getParent())
6677 bool DefIsLiveOut =
false;
6678 for (
User *U :
I->users()) {
6683 if (UserBB == DefBB)
6685 DefIsLiveOut =
true;
6692 for (
User *U : Src->users()) {
6695 if (UserBB == DefBB)
6699 if (isa<PHINode>(UI) || isa<LoadInst>(UI) || isa<StoreInst>(UI))
6706 bool MadeChange =
false;
6707 for (
Use &U : Src->uses()) {
6712 if (UserBB == DefBB)
6716 Instruction *&InsertedTrunc = InsertedTruncs[UserBB];
6718 if (!InsertedTrunc) {
6721 InsertedTrunc =
new TruncInst(
I, Src->getType(),
"");
6723 InsertedInsts.insert(InsertedTrunc);
6786bool CodeGenPrepare::optimizeLoadExt(
LoadInst *Load) {
6787 if (!
Load->isSimple() || !
Load->getType()->isIntOrPtrTy())
6791 if (
Load->hasOneUse() &&
6792 InsertedInsts.count(cast<Instruction>(*
Load->user_begin())))
6800 for (
auto *U :
Load->users())
6801 WorkList.
push_back(cast<Instruction>(U));
6812 while (!WorkList.
empty()) {
6816 if (!Visited.
insert(
I).second)
6820 if (
auto *Phi = dyn_cast<PHINode>(
I)) {
6821 for (
auto *U :
Phi->users())
6822 WorkList.
push_back(cast<Instruction>(U));
6826 switch (
I->getOpcode()) {
6827 case Instruction::And: {
6828 auto *AndC = dyn_cast<ConstantInt>(
I->getOperand(1));
6831 APInt AndBits = AndC->getValue();
6832 DemandBits |= AndBits;
6834 if (AndBits.
ugt(WidestAndBits))
6835 WidestAndBits = AndBits;
6836 if (AndBits == WidestAndBits &&
I->getOperand(0) == Load)
6841 case Instruction::Shl: {
6842 auto *ShlC = dyn_cast<ConstantInt>(
I->getOperand(1));
6846 DemandBits.setLowBits(
BitWidth - ShiftAmt);
6850 case Instruction::Trunc: {
6853 DemandBits.setLowBits(TruncBitWidth);
6862 uint32_t ActiveBits = DemandBits.getActiveBits();
6874 if (ActiveBits <= 1 || !DemandBits.isMask(ActiveBits) ||
6875 WidestAndBits != DemandBits)
6888 auto *NewAnd = cast<Instruction>(
6889 Builder.CreateAnd(Load, ConstantInt::get(Ctx, DemandBits)));
6892 InsertedInsts.insert(NewAnd);
6897 NewAnd->setOperand(0, Load);
6900 for (
auto *
And : AndsToMaybeRemove)
6903 if (cast<ConstantInt>(
And->getOperand(1))->getValue() == DemandBits) {
6905 if (&*CurInstIterator ==
And)
6906 CurInstIterator = std::next(
And->getIterator());
6907 And->eraseFromParent();
6918 auto *
I = dyn_cast<Instruction>(V);
6940 uint64_t Max = std::max(TrueWeight, FalseWeight);
6941 uint64_t Sum = TrueWeight + FalseWeight;
6949 CmpInst *Cmp = dyn_cast<CmpInst>(SI->getCondition());
6954 if (!Cmp || !Cmp->hasOneUse())
6975 for (
SelectInst *DefSI = SI; DefSI !=
nullptr && Selects.
count(DefSI);
6976 DefSI = dyn_cast<SelectInst>(V)) {
6977 assert(DefSI->getCondition() == SI->getCondition() &&
6978 "The condition of DefSI does not match with SI");
6979 V = (isTrue ? DefSI->getTrueValue() : DefSI->getFalseValue());
6982 assert(V &&
"Failed to get select true/false value");
7011 Value *NewTVal = Builder.CreateBinOp(Opcode, Shift->
getOperand(0), TVal);
7012 Value *NewFVal = Builder.CreateBinOp(Opcode, Shift->
getOperand(0), FVal);
7013 Value *NewSel = Builder.CreateSelect(
Cond, NewTVal, NewFVal);
7019bool CodeGenPrepare::optimizeFunnelShift(
IntrinsicInst *Fsh) {
7021 assert((Opcode == Intrinsic::fshl || Opcode == Intrinsic::fshr) &&
7022 "Expected a funnel shift");
7046 Value *NewTVal = Builder.CreateIntrinsic(Opcode, Ty, {
X,
Y, TVal});
7047 Value *NewFVal = Builder.CreateIntrinsic(Opcode, Ty, {
X,
Y, FVal});
7048 Value *NewSel = Builder.CreateSelect(
Cond, NewTVal, NewFVal);
7056bool CodeGenPrepare::optimizeSelectInst(
SelectInst *SI) {
7068 It !=
SI->getParent()->
end(); ++It) {
7070 if (
I &&
SI->getCondition() ==
I->getCondition()) {
7080 CurInstIterator = std::next(LastSI->
getIterator());
7085 fixupDPValuesOnInst(*SI);
7087 bool VectorCond = !
SI->getCondition()->getType()->isIntegerTy(1);
7090 if (VectorCond ||
SI->getMetadata(LLVMContext::MD_unpredictable))
7094 if (
SI->getType()->isVectorTy())
7095 SelectKind = TargetLowering::ScalarCondVectorVal;
7097 SelectKind = TargetLowering::ScalarValSelect;
7140 TrueInstrs.
push_back(cast<Instruction>(V));
7142 FalseInstrs.
push_back(cast<Instruction>(V));
7150 SplitPt.setHeadBit(
true);
7153 auto *CondFr =
IB.CreateFreeze(
SI->getCondition(),
SI->getName() +
".frozen");
7160 if (TrueInstrs.
size() == 0) {
7162 CondFr, SplitPt,
false,
nullptr,
nullptr, LI));
7164 EndBlock = cast<BasicBlock>(FalseBranch->
getOperand(0));
7165 }
else if (FalseInstrs.
size() == 0) {
7167 CondFr, SplitPt,
false,
nullptr,
nullptr, LI));
7169 EndBlock = cast<BasicBlock>(TrueBranch->
getOperand(0));
7174 nullptr,
nullptr, LI);
7175 TrueBranch = cast<BranchInst>(ThenTerm);
7176 FalseBranch = cast<BranchInst>(ElseTerm);
7179 EndBlock = cast<BasicBlock>(TrueBranch->
getOperand(0));
7182 EndBlock->
setName(
"select.end");
7184 TrueBlock->
setName(
"select.true.sink");
7186 FalseBlock->
setName(FalseInstrs.
size() == 0 ?
"select.false"
7187 :
"select.false.sink");
7191 FreshBBs.
insert(TrueBlock);
7193 FreshBBs.
insert(FalseBlock);
7194 FreshBBs.
insert(EndBlock);
7197 BFI->setBlockFreq(EndBlock,
BFI->getBlockFreq(StartBlock));
7199 static const unsigned MD[] = {
7200 LLVMContext::MD_prof, LLVMContext::MD_unpredictable,
7201 LLVMContext::MD_make_implicit, LLVMContext::MD_dbg};
7207 I->moveBefore(TrueBranch);
7209 I->moveBefore(FalseBranch);
7215 if (TrueBlock ==
nullptr)
7216 TrueBlock = StartBlock;
7217 else if (FalseBlock ==
nullptr)
7218 FalseBlock = StartBlock;
7221 INS.
insert(ASI.begin(), ASI.end());
7235 SI->eraseFromParent();
7237 ++NumSelectsExpanded;
7241 CurInstIterator = StartBlock->
end();
7257 auto *SVIVecType = cast<FixedVectorType>(SVI->
getType());
7260 "Expected a type of the same size!");
7266 Builder.SetInsertPoint(SVI);
7267 Value *BC1 = Builder.CreateBitCast(
7268 cast<Instruction>(SVI->
getOperand(0))->getOperand(1), NewType);
7269 Value *Shuffle = Builder.CreateVectorSplat(NewVecType->getNumElements(), BC1);
7270 Value *BC2 = Builder.CreateBitCast(Shuffle, SVIVecType);
7274 SVI, TLInfo,
nullptr,
7275 [&](
Value *V) { removeAllAssertingVHReferences(V); });
7279 if (
auto *BCI = dyn_cast<Instruction>(BC1))
7280 if (
auto *
Op = dyn_cast<Instruction>(BCI->
getOperand(0)))
7281 if (BCI->
getParent() !=
Op->getParent() && !isa<PHINode>(
Op) &&
7282 !
Op->isTerminator() && !
Op->isEHPad())
7288bool CodeGenPrepare::tryToSinkFreeOperands(
Instruction *
I) {
7300 bool Changed =
false;
7304 unsigned long InstNumber = 0;
7305 for (
const auto &
I : *TargetBB)
7306 InstOrdering[&
I] = InstNumber++;
7309 auto *UI = cast<Instruction>(
U->get());
7310 if (isa<PHINode>(UI))
7313 if (InstOrdering[UI] < InstOrdering[InsertPoint])
7322 for (
Use *U : ToReplace) {
7323 auto *UI = cast<Instruction>(
U->get());
7330 auto *OpDef = dyn_cast<Instruction>(NI->
getOperand(
I));
7333 FreshBBs.
insert(OpDef->getParent());
7337 NewInstructions[UI] = NI;
7342 InsertedInsts.insert(NI);
7348 if (NewInstructions.
count(OldI))
7349 NewInstructions[OldI]->setOperand(
U->getOperandNo(), NI);
7356 for (
auto *
I : MaybeDead) {
7357 if (!
I->hasNUsesOrMore(1)) {
7359 I->eraseFromParent();
7366bool CodeGenPrepare::optimizeSwitchType(
SwitchInst *SI) {
7374 if (RegWidth <= cast<IntegerType>(OldType)->
getBitWidth())
7392 ExtType = Instruction::SExt;
7394 if (
auto *Arg = dyn_cast<Argument>(
Cond)) {
7395 if (Arg->hasSExtAttr())
7396 ExtType = Instruction::SExt;
7397 if (Arg->hasZExtAttr())
7398 ExtType = Instruction::ZExt;
7404 SI->setCondition(ExtInst);
7405 for (
auto Case :
SI->cases()) {
7406 const APInt &NarrowConst = Case.getCaseValue()->getValue();
7407 APInt WideConst = (ExtType == Instruction::ZExt)
7408 ? NarrowConst.
zext(RegWidth)
7409 : NarrowConst.
sext(RegWidth);
7410 Case.setValue(ConstantInt::get(Context, WideConst));
7416bool CodeGenPrepare::optimizeSwitchPhiConstants(
SwitchInst *SI) {
7423 Value *Condition =
SI->getCondition();
7425 if (isa<ConstantInt>(*Condition))
7428 bool Changed =
false;
7434 BasicBlock *CaseBB = Case.getCaseSuccessor();
7437 bool CheckedForSinglePred =
false;
7439 Type *PHIType =
PHI.getType();
7447 if (PHIType == ConditionType || TryZExt) {
7449 bool SkipCase =
false;
7450 Value *Replacement =
nullptr;
7451 for (
unsigned I = 0,
E =
PHI.getNumIncomingValues();
I !=
E;
I++) {
7452 Value *PHIValue =
PHI.getIncomingValue(
I);
7453 if (PHIValue != CaseValue) {
7456 ConstantInt *PHIValueInt = dyn_cast<ConstantInt>(PHIValue);
7462 if (
PHI.getIncomingBlock(
I) != SwitchBB)
7467 if (!CheckedForSinglePred) {
7468 CheckedForSinglePred =
true;
7469 if (
SI->findCaseDest(CaseBB) ==
nullptr) {
7475 if (Replacement ==
nullptr) {
7476 if (PHIValue == CaseValue) {
7477 Replacement = Condition;
7480 Replacement = Builder.CreateZExt(Condition, PHIType);
7483 PHI.setIncomingValue(
I, Replacement);
7494bool CodeGenPrepare::optimizeSwitchInst(
SwitchInst *SI) {
7495 bool Changed = optimizeSwitchType(SI);
7496 Changed |= optimizeSwitchPhiConstants(SI);
7517class VectorPromoteHelper {
7534 unsigned StoreExtractCombineCost;
7543 if (InstsToBePromoted.
empty())
7545 return InstsToBePromoted.
back();
7551 unsigned getTransitionOriginalValueIdx()
const {
7552 assert(isa<ExtractElementInst>(Transition) &&
7553 "Other kind of transitions are not supported yet");
7560 unsigned getTransitionIdx()
const {
7561 assert(isa<ExtractElementInst>(Transition) &&
7562 "Other kind of transitions are not supported yet");
7570 Type *getTransitionType()
const {
7585 bool isProfitableToPromote() {
7586 Value *ValIdx = Transition->
getOperand(getTransitionOriginalValueIdx());
7587 unsigned Index = isa<ConstantInt>(ValIdx)
7588 ? cast<ConstantInt>(ValIdx)->getZExtValue()
7590 Type *PromotedType = getTransitionType();
7593 unsigned AS =
ST->getPointerAddressSpace();
7611 for (
const auto &Inst : InstsToBePromoted) {
7617 bool IsArg0Constant = isa<UndefValue>(Arg0) || isa<ConstantInt>(Arg0) ||
7618 isa<ConstantFP>(Arg0);
7631 dbgs() <<
"Estimated cost of computation to be promoted:\nScalar: "
7632 << ScalarCost <<
"\nVector: " << VectorCost <<
'\n');
7633 return ScalarCost > VectorCost;
7645 unsigned ExtractIdx = std::numeric_limits<unsigned>::max();
7650 if (
ConstantInt *CstVal = dyn_cast<ConstantInt>(ValExtractIdx))
7656 ElementCount EC = cast<VectorType>(getTransitionType())->getElementCount();
7660 if (!
EC.isScalable()) {
7663 for (
unsigned Idx = 0;
Idx !=
EC.getKnownMinValue(); ++
Idx) {
7664 if (
Idx == ExtractIdx)
7672 "Generate scalable vector for non-splat is unimplemented");
7678 unsigned OperandIdx) {
7681 if (OperandIdx != 1)
7683 switch (
Use->getOpcode()) {
7686 case Instruction::SDiv:
7687 case Instruction::UDiv:
7688 case Instruction::SRem:
7689 case Instruction::URem:
7691 case Instruction::FDiv:
7692 case Instruction::FRem:
7693 return !
Use->hasNoNaNs();
7701 unsigned CombineCost)
7702 :
DL(
DL), TLI(TLI),
TTI(
TTI), Transition(Transition),
7703 StoreExtractCombineCost(CombineCost) {
7704 assert(Transition &&
"Do not know how to promote null");
7708 bool canPromote(
const Instruction *ToBePromoted)
const {
7710 return isa<BinaryOperator>(ToBePromoted);
7715 bool shouldPromote(
const Instruction *ToBePromoted)
const {
7719 const Value *Val =
U.get();
7720 if (Val == getEndOfTransition()) {
7724 if (canCauseUndefinedBehavior(ToBePromoted,
U.getOperandNo()))
7728 if (!isa<ConstantInt>(Val) && !isa<UndefValue>(Val) &&
7729 !isa<ConstantFP>(Val))
7738 ISDOpcode, TLI.
getValueType(DL, getTransitionType(),
true));
7747 void enqueueForPromotion(
Instruction *ToBePromoted) {
7748 InstsToBePromoted.push_back(ToBePromoted);
7752 void recordCombineInstruction(
Instruction *ToBeCombined) {
7754 CombineInst = ToBeCombined;
7764 if (InstsToBePromoted.empty() || !CombineInst)
7772 for (
auto &ToBePromoted : InstsToBePromoted)
7773 promoteImpl(ToBePromoted);
7774 InstsToBePromoted.clear();
7781void VectorPromoteHelper::promoteImpl(
Instruction *ToBePromoted) {
7791 "The type of the result of the transition does not match "
7796 Type *TransitionTy = getTransitionType();
7803 Value *NewVal =
nullptr;
7804 if (Val == Transition)
7805 NewVal = Transition->
getOperand(getTransitionOriginalValueIdx());
7806 else if (isa<UndefValue>(Val) || isa<ConstantInt>(Val) ||
7807 isa<ConstantFP>(Val)) {
7810 cast<Constant>(Val),
7811 isa<UndefValue>(Val) ||
7812 canCauseUndefinedBehavior(ToBePromoted,
U.getOperandNo()));
7816 ToBePromoted->
setOperand(
U.getOperandNo(), NewVal);
7819 Transition->
setOperand(getTransitionOriginalValueIdx(), ToBePromoted);
7825bool CodeGenPrepare::optimizeExtractElementInst(
Instruction *Inst) {
7826 unsigned CombineCost = std::numeric_limits<unsigned>::max();
7841 LLVM_DEBUG(
dbgs() <<
"Found an interesting transition: " << *Inst <<
'\n');
7842 VectorPromoteHelper VPH(*
DL, *TLI, *
TTI, Inst, CombineCost);
7849 if (ToBePromoted->
getParent() != Parent) {
7850 LLVM_DEBUG(
dbgs() <<
"Instruction to promote is in a different block ("
7852 <<
") than the transition (" << Parent->
getName()
7857 if (VPH.canCombine(ToBePromoted)) {
7859 <<
"will be combined with: " << *ToBePromoted <<
'\n');
7860 VPH.recordCombineInstruction(ToBePromoted);
7861 bool Changed = VPH.promote();
7862 NumStoreExtractExposed += Changed;
7867 if (!VPH.canPromote(ToBePromoted) || !VPH.shouldPromote(ToBePromoted))
7870 LLVM_DEBUG(
dbgs() <<
"Promoting is possible... Enqueue for promotion!\n");
7872 VPH.enqueueForPromotion(ToBePromoted);
7873 Inst = ToBePromoted;
7913 Type *StoreType = SI.getValueOperand()->getType();
7922 if (!
DL.typeSizeEqualsStoreSize(StoreType) ||
7923 DL.getTypeSizeInBits(StoreType) == 0)
7926 unsigned HalfValBitSize =
DL.getTypeSizeInBits(StoreType) / 2;
7928 if (!
DL.typeSizeEqualsStoreSize(SplitStoreType))
7932 if (SI.isVolatile())
7944 if (!
match(SI.getValueOperand(),
7951 if (!
LValue->getType()->isIntegerTy() ||
7952 DL.getTypeSizeInBits(
LValue->getType()) > HalfValBitSize ||
7954 DL.getTypeSizeInBits(HValue->
getType()) > HalfValBitSize)
7959 auto *LBC = dyn_cast<BitCastInst>(
LValue);
7960 auto *HBC = dyn_cast<BitCastInst>(HValue);
7974 if (LBC && LBC->getParent() != SI.getParent())
7976 if (HBC && HBC->getParent() != SI.getParent())
7977 HValue = Builder.
CreateBitCast(HBC->getOperand(0), HBC->getType());
7979 bool IsLE = SI.getModule()->getDataLayout().isLittleEndian();
7980 auto CreateSplitStore = [&](
Value *V,
bool Upper) {
7983 Align Alignment = SI.getAlign();
7984 const bool IsOffsetStore = (IsLE &&
Upper) || (!IsLE && !
Upper);
7985 if (IsOffsetStore) {
7987 SplitStoreType,
Addr,
7998 CreateSplitStore(
LValue,
false);
7999 CreateSplitStore(HValue,
true);
8002 SI.eraseFromParent();
8010 return GEP->getNumOperands() == 2 &&
I.isSequential() &&
8011 isa<ConstantInt>(
GEP->getOperand(1));
8089 if (!isa<Instruction>(GEPIOp))
8091 auto *GEPIOpI = cast<Instruction>(GEPIOp);
8092 if (GEPIOpI->getParent() != SrcBlock)
8097 if (auto *I = dyn_cast<Instruction>(Usr)) {
8098 if (I->getParent() != SrcBlock) {
8106 std::vector<GetElementPtrInst *> UGEPIs;
8113 if (!isa<Instruction>(Usr))
8115 auto *UI = cast<Instruction>(Usr);
8120 if (!isa<GetElementPtrInst>(Usr))
8122 auto *UGEPI = cast<GetElementPtrInst>(Usr);
8128 if (UGEPI->getOperand(0) != GEPIOp)
8130 if (UGEPI->getSourceElementType() != GEPI->getSourceElementType())
8132 if (GEPIIdx->getType() !=
8133 cast<ConstantInt>(UGEPI->getOperand(1))->getType())
8135 ConstantInt *UGEPIIdx = cast<ConstantInt>(UGEPI->getOperand(1));
8140 UGEPIs.push_back(UGEPI);
8142 if (UGEPIs.size() == 0)
8146 ConstantInt *UGEPIIdx = cast<ConstantInt>(UGEPI->getOperand(1));
8155 UGEPI->setOperand(0, GEPI);
8156 ConstantInt *UGEPIIdx = cast<ConstantInt>(UGEPI->getOperand(1));
8157 Constant *NewUGEPIIdx = ConstantInt::get(
8158 GEPIIdx->getType(), UGEPIIdx->
getValue() - GEPIIdx->getValue());
8159 UGEPI->setOperand(1, NewUGEPIIdx);
8162 if (!GEPI->isInBounds()) {
8163 UGEPI->setIsInBounds(
false);
8170 return cast<Instruction>(Usr)->getParent() != SrcBlock;
8172 "GEPIOp is used outside SrcBlock");
8192 ICmpInst *Cmp = dyn_cast<ICmpInst>(Branch->getCondition());
8193 if (!Cmp || !isa<ConstantInt>(Cmp->getOperand(1)) || !Cmp->hasOneUse())
8196 Value *
X = Cmp->getOperand(0);
8197 APInt CmpC = cast<ConstantInt>(Cmp->getOperand(1))->getValue();
8199 for (
auto *U :
X->users()) {
8203 (UI->
getParent() != Branch->getParent() &&
8204 UI->
getParent() != Branch->getSuccessor(0) &&
8205 UI->
getParent() != Branch->getSuccessor(1)) ||
8206 (UI->
getParent() != Branch->getParent() &&
8210 if (CmpC.
isPowerOf2() && Cmp->getPredicate() == ICmpInst::ICMP_ULT &&
8213 if (UI->
getParent() != Branch->getParent())
8216 ConstantInt::get(UI->
getType(), 0));
8218 LLVM_DEBUG(
dbgs() <<
" to compare on zero: " << *NewCmp <<
"\n");
8222 if (Cmp->isEquality() &&
8226 if (UI->
getParent() != Branch->getParent())
8229 ConstantInt::get(UI->
getType(), 0));
8231 LLVM_DEBUG(
dbgs() <<
" to compare on zero: " << *NewCmp <<
"\n");
8239bool CodeGenPrepare::optimizeInst(
Instruction *
I, ModifyDT &ModifiedDT) {
8240 bool AnyChange =
false;
8241 AnyChange = fixupDPValuesOnInst(*
I);
8245 if (InsertedInsts.count(
I))
8249 if (
PHINode *
P = dyn_cast<PHINode>(
I)) {
8254 LargeOffsetGEPMap.erase(
P);
8256 P->eraseFromParent();
8263 if (
CastInst *CI = dyn_cast<CastInst>(
I)) {
8276 if ((isa<UIToFPInst>(
I) || isa<FPToUIInst>(
I) || isa<TruncInst>(
I)) &&
8278 I, LI->getLoopFor(
I->getParent()), *
TTI))
8281 if (isa<ZExtInst>(
I) || isa<SExtInst>(
I)) {
8286 TargetLowering::TypeExpandInteger) {
8290 I, LI->getLoopFor(
I->getParent()), *
TTI))
8293 bool MadeChange = optimizeExt(
I);
8294 return MadeChange | optimizeExtUses(
I);
8300 if (
auto *Cmp = dyn_cast<CmpInst>(
I))
8301 if (optimizeCmp(Cmp, ModifiedDT))
8304 if (
LoadInst *LI = dyn_cast<LoadInst>(
I)) {
8305 LI->
setMetadata(LLVMContext::MD_invariant_group,
nullptr);
8306 bool Modified = optimizeLoadExt(LI);
8312 if (
StoreInst *SI = dyn_cast<StoreInst>(
I)) {
8315 SI->setMetadata(LLVMContext::MD_invariant_group,
nullptr);
8316 unsigned AS =
SI->getPointerAddressSpace();
8317 return optimizeMemoryInst(
I,
SI->getOperand(1),
8318 SI->getOperand(0)->getType(), AS);
8322 unsigned AS = RMW->getPointerAddressSpace();
8323 return optimizeMemoryInst(
I, RMW->getPointerOperand(), RMW->getType(), AS);
8327 unsigned AS = CmpX->getPointerAddressSpace();
8328 return optimizeMemoryInst(
I, CmpX->getPointerOperand(),
8329 CmpX->getCompareOperand()->getType(), AS);
8339 if (BinOp && (BinOp->
getOpcode() == Instruction::AShr ||
8340 BinOp->
getOpcode() == Instruction::LShr)) {
8348 if (GEPI->hasAllZeroIndices()) {
8351 GEPI->getName(), GEPI);
8352 NC->setDebugLoc(GEPI->getDebugLoc());
8355 GEPI, TLInfo,
nullptr,
8356 [&](
Value *V) { removeAllAssertingVHReferences(V); });
8358 optimizeInst(
NC, ModifiedDT);
8370 if (
ICmpInst *II = dyn_cast<ICmpInst>(FI->getOperand(0)))
8372 else if (
FCmpInst *
F = dyn_cast<FCmpInst>(FI->getOperand(0)))
8373 CmpI =
F->getFastMathFlags().none() ?
F :
nullptr;
8377 bool Const0 = isa<ConstantInt>(Op0) || isa<ConstantFP>(Op0) ||
8378 isa<ConstantPointerNull>(Op0);
8379 bool Const1 = isa<ConstantInt>(Op1) || isa<ConstantFP>(Op1) ||
8380 isa<ConstantPointerNull>(Op1);
8381 if (Const0 || Const1) {
8382 if (!Const0 || !Const1) {
8383 auto *
F =
new FreezeInst(Const0 ? Op1 : Op0,
"", CmpI);
8388 FI->eraseFromParent();
8395 if (tryToSinkFreeOperands(
I))
8398 switch (
I->getOpcode()) {
8399 case Instruction::Shl:
8400 case Instruction::LShr:
8401 case Instruction::AShr:
8402 return optimizeShiftInst(cast<BinaryOperator>(
I));
8403 case Instruction::Call:
8405 case Instruction::Select:
8406 return optimizeSelectInst(cast<SelectInst>(
I));
8407 case Instruction::ShuffleVector:
8408 return optimizeShuffleVectorInst(cast<ShuffleVectorInst>(
I));
8409 case Instruction::Switch:
8410 return optimizeSwitchInst(cast<SwitchInst>(
I));
8411 case Instruction::ExtractElement:
8412 return optimizeExtractElementInst(cast<ExtractElementInst>(
I));
8413 case Instruction::Br:
8414 return optimizeBranch(cast<BranchInst>(
I), *TLI, FreshBBs, IsHugeFunc);
8423 if (!
I.getType()->isIntegerTy() ||
8434 &
I, TLInfo,
nullptr,
8435 [&](
Value *V) { removeAllAssertingVHReferences(V); });
8442bool CodeGenPrepare::optimizeBlock(
BasicBlock &BB, ModifyDT &ModifiedDT) {
8444 bool MadeChange =
false;
8447 CurInstIterator = BB.
begin();
8448 ModifiedDT = ModifyDT::NotModifyDT;
8449 while (CurInstIterator != BB.
end()) {
8450 MadeChange |= optimizeInst(&*CurInstIterator++, ModifiedDT);
8451 if (ModifiedDT != ModifyDT::NotModifyDT) {
8464 }
while (ModifiedDT == ModifyDT::ModifyInstDT);
8466 bool MadeBitReverse =
true;
8467 while (MadeBitReverse) {
8468 MadeBitReverse =
false;
8470 if (makeBitReverse(
I)) {
8471 MadeBitReverse = MadeChange =
true;
8476 MadeChange |= dupRetToEnableTailCallOpts(&BB, ModifiedDT);
8488 bool AnyChange =
false;
8491 for (
Value *Location : LocationOps) {
8507bool CodeGenPrepare::fixupDPValuesOnInst(
Instruction &
I) {
8508 bool AnyChange =
false;
8510 AnyChange |= fixupDPValue(DPV);
8516bool CodeGenPrepare::fixupDPValue(
DPValue &DPV) {
8517 if (DPV.
Type != DPValue::LocationType::Value &&
8518 DPV.
Type != DPValue::LocationType::Assign)
8522 bool AnyChange =
false;
8525 for (
Value *Location : LocationOps) {
8543 if (isa<PHINode>(VI))
8544 DVI->
insertBefore(&*VI->getParent()->getFirstInsertionPt());
8552 if (isa<PHINode>(VI))
8563bool CodeGenPrepare::placeDbgValues(
Function &
F) {
8564 bool MadeChange =
false;
8567 auto DbgProcessor = [&](
auto *DbgItem,
Instruction *Position) {
8569 for (
Value *V : DbgItem->location_ops())
8570 if (
Instruction *VI = dyn_cast_or_null<Instruction>(V))
8578 if (
VI->isTerminator())
8583 if (isa<PHINode>(VI) &&
VI->getParent()->getTerminator()->isEHPad())
8594 if (VIs.size() > 1) {
8597 <<
"Unable to find valid location for Debug Value, undefing:\n"
8599 DbgItem->setKillLocation();
8604 << *DbgItem <<
' ' << *VI);
8616 DbgProcessor(DVI, DVI);
8624 if (DPV.
Type != DPValue::LocationType::Value)
8626 DbgProcessor(&DPV, &
Insn);
8637bool CodeGenPrepare::placePseudoProbes(
Function &
F) {
8638 bool MadeChange =
false;
8641 auto FirstInst =
Block.getFirstInsertionPt();
8642 while (FirstInst !=
Block.end() && FirstInst->isDebugOrPseudoInst())
8646 while (
I !=
Block.end()) {
8647 if (
auto *II = dyn_cast<PseudoProbeInst>(
I++)) {
8658 uint64_t NewMax = (NewTrue > NewFalse) ? NewTrue : NewFalse;
8659 uint32_t Scale = (NewMax / std::numeric_limits<uint32_t>::max()) + 1;
8660 NewTrue = NewTrue / Scale;
8661 NewFalse = NewFalse / Scale;
8686bool CodeGenPrepare::splitBranchCondition(
Function &
F, ModifyDT &ModifiedDT) {
8690 bool MadeChange =
false;
8691 for (
auto &BB :
F) {
8704 if (Br1->getMetadata(LLVMContext::MD_unpredictable))
8712 Value *Cond1, *Cond2;
8715 Opc = Instruction::And;
8718 Opc = Instruction::Or;
8728 if (!IsGoodCond(Cond1) || !IsGoodCond(Cond2))
8742 Br1->setCondition(Cond1);
8747 if (Opc == Instruction::And)
8748 Br1->setSuccessor(0, TmpBB);
8750 Br1->setSuccessor(1, TmpBB);
8754 if (
auto *
I = dyn_cast<Instruction>(Cond2)) {
8755 I->removeFromParent();
8756 I->insertBefore(Br2);
8768 if (Opc == Instruction::Or)
8782 if (Opc == Instruction::Or) {
8804 uint64_t NewTrueWeight = TrueWeight;
8805 uint64_t NewFalseWeight = TrueWeight + 2 * FalseWeight;
8807 Br1->setMetadata(LLVMContext::MD_prof,
8811 NewTrueWeight = TrueWeight;
8812 NewFalseWeight = 2 * FalseWeight;
8814 Br2->setMetadata(LLVMContext::MD_prof,
8839 uint64_t NewTrueWeight = 2 * TrueWeight + FalseWeight;
8840 uint64_t NewFalseWeight = FalseWeight;
8842 Br1->setMetadata(LLVMContext::MD_prof,
8846 NewTrueWeight = 2 * TrueWeight;
8847 NewFalseWeight = FalseWeight;
8849 Br2->setMetadata(LLVMContext::MD_prof,
8855 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 GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
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 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,...
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.
void insertDbgRecordAfter(DbgRecord *DPV, Instruction *I)
Insert a DbgRecord into a block at the position given by I.
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.
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.
void insertDbgRecordBefore(DbgRecord *DPV, InstListType::iterator Here)
Insert a DbgRecord into a block at the position given by Here.
bool IsNewDbgInfoFormat
Flag recording whether or not this block stores debug-info in the form of intrinsic instructions (fal...
void reinsertInstInDbgRecords(Instruction *I, std::optional< DbgRecord::self_iterator > Pos)
In rare circumstances instructions can be speculatively removed from blocks, and then be re-inserted ...
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
static BinaryOperator * Create(BinaryOps Op, Value *S1, Value *S2, const Twine &Name, BasicBlock::iterator InsertBefore)
Construct a binary instruction, given the opcode and the two operands.
BinaryOps getOpcode() const
This class represents a no-op cast from one type to another.
BlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate IR basic block frequen...
Conditional or Unconditional Branch instruction.
void swapSuccessors()
Swap the successors of this branch instruction.
bool isConditional() const
BasicBlock * getSuccessor(unsigned i) const
bool isUnconditional() const
Analysis providing branch probability information.
static BranchProbability getBranchProbability(uint64_t Numerator, uint64_t Denominator)
bool isInlineAsm() const
Check if this call is an inline asm statement.
Function * getCalledFunction() const
Returns the function called, or null if this is an indirect function invocation or the function signa...
bool hasFnAttr(Attribute::AttrKind Kind) const
Determine whether this call has the given attribute.
Value * getArgOperand(unsigned i) const
void setArgOperand(unsigned i, Value *v)
iterator_range< User::op_iterator > args()
Iteration adapter for range-for loops.
This class represents a function call, abstracting a target machine's calling convention.
This is the base class for all instructions that perform data casts.
Instruction::CastOps getOpcode() const
Return the opcode of this CastInst.
static CastInst * Create(Instruction::CastOps, Value *S, Type *Ty, const Twine &Name, BasicBlock::iterator InsertBefore)
Provides a way to construct any of the CastInst subclasses using an opcode instead of the subclass's ...
This class is the base class for the comparison instructions.
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
@ ICMP_SLT
signed less than
@ ICMP_UGT
unsigned greater than
@ ICMP_SGT
signed greater than
@ ICMP_ULT
unsigned less than
Predicate getSwappedPredicate() const
For example, EQ->EQ, SLE->SGE, ULT->UGT, OEQ->OEQ, ULE->UGE, OLT->OGT, etc.
static CmpInst * Create(OtherOps Op, Predicate predicate, Value *S1, Value *S2, const Twine &Name, BasicBlock::iterator InsertBefore)
Construct a compare instruction, given the opcode, the predicate and the two operands.
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 HasNUW=false, 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.
Record of a variable value-assignment, aka a non instruction representation of the dbg....
LocationType Type
Classification of the debug-info record that this DPValue represents.
iterator_range< location_op_iterator > location_ops() const
Get the locations corresponding to the variable referenced by the debug info intrinsic.
void replaceVariableLocationOp(Value *OldValue, Value *NewValue, bool AllowEmpty=false)
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)
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.
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 * 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.
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 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 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.
specific_intval< false > m_SpecificInt(APInt V)
Match a specific integer value or vector with all elements equal to the value.
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.
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.
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
bool isKnownNonZero(const Value *V, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true)
Return true if the given value is known to be non-zero when defined.
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 &)
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.
Interval::pred_iterator pred_end(Interval *I)
Align getKnownAlignment(Value *V, const DataLayout &DL, const Instruction *CxtI=nullptr, AssumptionCache *AC=nullptr, const DominatorTree *DT=nullptr)
Try to infer an alignment for the specified pointer.
void erase(Container &C, ValueType V)
Wrapper function to remove a value from a container:
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
bool isSplatValue(const Value *V, int Index=-1, unsigned Depth=0)
Return true if each element of the vector value V is poisoned or equal to every other non-poisoned el...
bool DeleteDeadPHIs(BasicBlock *BB, const TargetLibraryInfo *TLI=nullptr, MemorySSAUpdater *MSSAU=nullptr)
Examine each PHI in the given block and delete it if it is dead.
bool replaceAndRecursivelySimplify(Instruction *I, Value *SimpleV, const TargetLibraryInfo *TLI=nullptr, const DominatorTree *DT=nullptr, AssumptionCache *AC=nullptr, SmallSetVector< Instruction *, 8 > *UnsimplifiedUsers=nullptr)
Replace all uses of 'I' with 'SimpleV' and simplify the uses recursively.
auto reverse(ContainerTy &&C)
bool recognizeBSwapOrBitReverseIdiom(Instruction *I, bool MatchBSwaps, bool MatchBitReversals, SmallVectorImpl< Instruction * > &InsertedInsts)
Try to match a bswap or bitreverse idiom.
void sort(IteratorTy Start, IteratorTy End)
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.
Interval::pred_iterator pred_begin(Interval *I)
pred_begin/pred_end - define methods so that Intervals may be used just like BasicBlocks can with the...
FunctionPass * createCodeGenPrepareLegacyPass()
createCodeGenPrepareLegacyPass - Transform the code to expose more pattern matching during instructio...
bool VerifyLoopInfo
Enable verification of loop info.
@ 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.
void findDbgValues(SmallVectorImpl< DbgValueInst * > &DbgValues, Value *V, SmallVectorImpl< DPValue * > *DPValues=nullptr)
Finds the llvm.dbg.value intrinsics describing a value.
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...
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 DPValue 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.
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 If BaseGV is null...
This contains information for each constraint that we are lowering.