46#include "llvm/Config/llvm-config.h"
68#include "llvm/IR/IntrinsicsAArch64.h"
112#define DEBUG_TYPE "codegenprepare"
115STATISTIC(NumPHIsElim,
"Number of trivial PHIs eliminated");
116STATISTIC(NumGEPsElim,
"Number of GEPs converted to casts");
117STATISTIC(NumCmpUses,
"Number of uses of Cmp expressions replaced with uses of "
119STATISTIC(NumCastUses,
"Number of uses of Cast expressions replaced with uses "
121STATISTIC(NumMemoryInsts,
"Number of memory instructions whose address "
122 "computations were sunk");
124 "Number of phis created when address "
125 "computations were sunk to memory instructions");
127 "Number of select created when address "
128 "computations were sunk to memory instructions");
129STATISTIC(NumExtsMoved,
"Number of [s|z]ext instructions combined with loads");
130STATISTIC(NumExtUses,
"Number of uses of [s|z]ext instructions optimized");
132 "Number of and mask instructions added to form ext loads");
133STATISTIC(NumAndUses,
"Number of uses of and mask instructions optimized");
134STATISTIC(NumRetsDup,
"Number of return instructions duplicated");
135STATISTIC(NumDbgValueMoved,
"Number of debug value instructions moved");
136STATISTIC(NumSelectsExpanded,
"Number of selects turned into branches");
137STATISTIC(NumStoreExtractExposed,
"Number of store(extractelement) exposed");
141 cl::desc(
"Disable branch optimizations in CodeGenPrepare"));
145 cl::desc(
"Disable GC optimizations in CodeGenPrepare"));
150 cl::desc(
"Disable select to branch conversion."));
154 cl::desc(
"Address sinking in CGP using GEPs."));
158 cl::desc(
"Enable sinking and/cmp into branches."));
162 cl::desc(
"Disable store(extract) optimizations in CodeGenPrepare"));
166 cl::desc(
"Stress test store(extract) optimizations in CodeGenPrepare"));
170 cl::desc(
"Disable ext(promotable(ld)) -> promoted(ext(ld)) optimization in "
175 cl::desc(
"Stress test ext(promotable(ld)) -> promoted(ext(ld)) "
176 "optimization in CodeGenPrepare"));
180 cl::desc(
"Disable protection against removing loop preheaders"));
184 cl::desc(
"Use profile info to add section prefix for hot/cold functions"));
187 "profile-unknown-in-special-section",
cl::Hidden,
188 cl::desc(
"In profiling mode like sampleFDO, if a function doesn't have "
189 "profile, we cannot tell the function is cold for sure because "
190 "it may be a function newly added without ever being sampled. "
191 "With the flag enabled, compiler can put such profile unknown "
192 "functions into a special section, so runtime system can choose "
193 "to handle it in a different way than .text section, to save "
194 "RAM for example. "));
198 cl::desc(
"Use the basic-block-sections profile to determine the text "
199 "section prefix for hot functions. Functions with "
200 "basic-block-sections profile will be placed in `.text.hot` "
201 "regardless of their FDO profile info. Other functions won't be "
202 "impacted, i.e., their prefixes will be decided by FDO/sampleFDO "
207 cl::desc(
"Skip merging empty blocks if (frequency of empty block) / "
208 "(frequency of destination block) is greater than this ratio"));
212 cl::desc(
"Force store splitting no matter what the target query says."));
216 cl::desc(
"Enable merging of redundant sexts when one is dominating"
222 cl::desc(
"Disables combining addressing modes with different parts "
223 "in optimizeMemoryInst."));
227 cl::desc(
"Allow creation of Phis in Address sinking."));
231 cl::desc(
"Allow creation of selects in Address sinking."));
235 cl::desc(
"Allow combining of BaseReg field in Address sinking."));
239 cl::desc(
"Allow combining of BaseGV field in Address sinking."));
243 cl::desc(
"Allow combining of BaseOffs field in Address sinking."));
247 cl::desc(
"Allow combining of ScaledReg field in Address sinking."));
252 cl::desc(
"Enable splitting large offset of GEP."));
256 cl::desc(
"Enable ICMP_EQ to ICMP_S(L|G)T conversion."));
260 cl::desc(
"Enable BFI update verification for "
265 cl::desc(
"Enable converting phi types in CodeGenPrepare"));
269 cl::desc(
"Least BB number of huge function."));
274 cl::desc(
"Max number of address users to look at"));
278 cl::desc(
"Disable elimination of dead PHI nodes."));
306class TypePromotionTransaction;
308class CodeGenPrepare {
309 friend class CodeGenPrepareLegacyPass;
310 const TargetMachine *TM =
nullptr;
311 const TargetSubtargetInfo *SubtargetInfo =
nullptr;
312 const TargetLowering *TLI =
nullptr;
313 const TargetRegisterInfo *TRI =
nullptr;
314 const TargetTransformInfo *TTI =
nullptr;
315 const BasicBlockSectionsProfileReader *BBSectionsProfileReader =
nullptr;
316 const TargetLibraryInfo *TLInfo =
nullptr;
317 DomTreeUpdater *DTU =
nullptr;
318 LoopInfo *LI =
nullptr;
319 BlockFrequencyInfo *BFI;
320 BranchProbabilityInfo *BPI;
321 ProfileSummaryInfo *PSI =
nullptr;
332 ValueMap<Value *, WeakTrackingVH> SunkAddrs;
335 SetOfInstrs InsertedInsts;
339 InstrToOrigTy PromotedInsts;
342 SetOfInstrs RemovedInsts;
345 DenseMap<Value *, Instruction *> SeenChainsForSExt;
350 MapVector<AssertingVH<Value>,
355 SmallSet<AssertingVH<Value>, 2> NewGEPBases;
358 DenseMap<AssertingVH<GetElementPtrInst>,
int> LargeOffsetGEPID;
361 ValueToSExts ValToSExtendedUses;
367 const DataLayout *DL =
nullptr;
370 CodeGenPrepare() =
default;
371 CodeGenPrepare(
const TargetMachine *TM) : TM(TM){};
373 bool IsHugeFunc =
false;
379 SmallPtrSet<BasicBlock *, 32> FreshBBs;
381 void releaseMemory() {
383 InsertedInsts.clear();
384 PromotedInsts.clear();
391 template <
typename F>
392 void resetIteratorIfInvalidatedWhileCalling(BasicBlock *BB,
F f) {
396 Value *CurValue = &*CurInstIterator;
397 WeakTrackingVH IterHandle(CurValue);
403 if (IterHandle != CurValue) {
404 CurInstIterator = BB->
begin();
410 DominatorTree &getDT() {
return DTU->getDomTree(); }
412 void removeAllAssertingVHReferences(
Value *V);
413 bool eliminateAssumptions(Function &
F);
414 bool eliminateFallThrough(Function &
F);
415 bool eliminateMostlyEmptyBlocks(Function &
F,
bool &ResetLI);
416 BasicBlock *findDestBlockOfMergeableEmptyBlock(BasicBlock *BB);
417 bool canMergeBlocks(
const BasicBlock *BB,
const BasicBlock *DestBB)
const;
418 bool eliminateMostlyEmptyBlock(BasicBlock *BB);
419 bool isMergingEmptyBlockProfitable(BasicBlock *BB, BasicBlock *DestBB,
421 bool makeBitReverse(Instruction &
I);
423 bool optimizeInst(Instruction *
I, ModifyDT &ModifiedDT);
424 bool optimizeMemoryInst(Instruction *MemoryInst,
Value *Addr,
Type *AccessTy,
426 bool optimizeGatherScatterInst(Instruction *MemoryInst,
Value *Ptr);
427 bool optimizeMulWithOverflow(Instruction *
I,
bool IsSigned,
428 ModifyDT &ModifiedDT);
429 bool optimizeInlineAsmInst(CallInst *CS);
431 bool optimizeExt(Instruction *&
I);
432 bool optimizeExtUses(Instruction *
I);
433 bool optimizeLoadExt(LoadInst *Load);
434 bool optimizeShiftInst(BinaryOperator *BO);
435 bool optimizeFunnelShift(IntrinsicInst *Fsh);
436 bool optimizeSelectInst(SelectInst *SI);
437 bool optimizeShuffleVectorInst(ShuffleVectorInst *SVI);
438 bool optimizeSwitchType(SwitchInst *SI);
439 bool optimizeSwitchPhiConstants(SwitchInst *SI);
440 bool optimizeSwitchInst(SwitchInst *SI);
441 bool optimizeExtractElementInst(Instruction *Inst);
442 bool dupRetToEnableTailCallOpts(BasicBlock *BB, ModifyDT &ModifiedDT);
443 bool fixupDbgVariableRecord(DbgVariableRecord &
I);
444 bool fixupDbgVariableRecordsOnInst(Instruction &
I);
445 bool placeDbgValues(Function &
F);
446 bool placePseudoProbes(Function &
F);
447 bool canFormExtLd(
const SmallVectorImpl<Instruction *> &MovedExts,
448 LoadInst *&LI, Instruction *&Inst,
bool HasPromoted);
449 bool tryToPromoteExts(TypePromotionTransaction &TPT,
450 const SmallVectorImpl<Instruction *> &Exts,
451 SmallVectorImpl<Instruction *> &ProfitablyMovedExts,
452 unsigned CreatedInstsCost = 0);
453 bool mergeSExts(Function &
F);
454 bool splitLargeGEPOffsets();
455 bool optimizePhiType(PHINode *Inst, SmallPtrSetImpl<PHINode *> &Visited,
456 SmallPtrSetImpl<Instruction *> &DeletedInstrs);
457 bool optimizePhiTypes(Function &
F);
458 bool performAddressTypePromotion(
459 Instruction *&Inst,
bool AllowPromotionWithoutCommonHeader,
460 bool HasPromoted, TypePromotionTransaction &TPT,
461 SmallVectorImpl<Instruction *> &SpeculativelyMovedExts);
462 bool splitBranchCondition(Function &
F);
463 bool simplifyOffsetableRelocate(GCStatepointInst &
I);
465 bool tryToSinkFreeOperands(Instruction *
I);
466 bool replaceMathCmpWithIntrinsic(BinaryOperator *BO,
Value *Arg0,
Value *Arg1,
468 bool optimizeCmp(CmpInst *Cmp, ModifyDT &ModifiedDT);
469 bool optimizeURem(Instruction *Rem);
470 bool combineToUSubWithOverflow(CmpInst *Cmp, ModifyDT &ModifiedDT);
471 bool combineToUAddWithOverflow(CmpInst *Cmp, ModifyDT &ModifiedDT);
472 bool unfoldPowerOf2Test(CmpInst *Cmp);
473 void verifyBFIUpdates(Function &
F);
474 bool _run(Function &
F);
481 CodeGenPrepareLegacyPass() : FunctionPass(ID) {}
485 StringRef getPassName()
const override {
return "CodeGen Prepare"; }
487 void getAnalysisUsage(AnalysisUsage &AU)
const override {
495 AU.
addRequired<BranchProbabilityInfoWrapperPass>();
503char CodeGenPrepareLegacyPass::ID = 0;
505bool CodeGenPrepareLegacyPass::runOnFunction(
Function &
F) {
508 auto TM = &getAnalysis<TargetPassConfig>().getTM<TargetMachine>();
509 CodeGenPrepare CGP(TM);
510 CGP.DL = &
F.getDataLayout();
513 CGP.TRI = CGP.SubtargetInfo->getRegisterInfo();
514 CGP.TLInfo = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(
F);
515 CGP.TTI = &getAnalysis<TargetTransformInfoWrapperPass>().getTTI(
F);
516 CGP.LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
517 CGP.BPI = &getAnalysis<BranchProbabilityInfoWrapperPass>().getBPI();
518 CGP.BFI = &getAnalysis<BlockFrequencyInfoWrapperPass>().getBFI();
519 CGP.PSI = &getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI();
521 getAnalysisIfAvailable<BasicBlockSectionsProfileReaderWrapperPass>();
522 CGP.BBSectionsProfileReader = BBSPRWP ? &BBSPRWP->getBBSPR() :
nullptr;
523 DomTreeUpdater DTUpdater(
524 &getAnalysis<DominatorTreeWrapperPass>().
getDomTree(),
525 DomTreeUpdater::UpdateStrategy::Lazy);
526 CGP.DTU = &DTUpdater;
532 "Optimize for code generation",
false,
false)
544 return new CodeGenPrepareLegacyPass();
549 CodeGenPrepare CGP(TM);
562 DL = &
F.getDataLayout();
573 BBSectionsProfileReader =
576 DomTreeUpdater::UpdateStrategy::Lazy);
582 bool EverMadeChange =
false;
584 OptSize =
F.hasOptSize();
589 (void)
F.setSectionPrefix(
"hot");
594 if (
F.hasFnAttribute(Attribute::Hot) ||
596 (void)
F.setSectionPrefix(
"hot");
601 F.hasFnAttribute(Attribute::Cold))
602 (void)
F.setSectionPrefix(
"unlikely");
605 (void)
F.setSectionPrefix(
"unknown");
611 const DenseMap<unsigned int, unsigned int> &BypassWidths =
614 while (BB !=
nullptr) {
627 EverMadeChange |= eliminateAssumptions(
F);
629 auto resetLoopInfo = [
this]() {
636 bool ResetLI =
false;
637 EverMadeChange |= eliminateMostlyEmptyBlocks(
F, ResetLI);
642 EverMadeChange |= splitBranchCondition(
F);
648 EverMadeChange |=
Split;
654 assert(getDT().
verify(DominatorTree::VerificationLevel::Fast) &&
655 "Incorrect DominatorTree updates in CGP");
665 bool MadeChange =
true;
666 bool FuncIterated =
false;
676 if (FuncIterated && !FreshBBs.
contains(&BB))
679 ModifyDT ModifiedDTOnIteration = ModifyDT::NotModifyDT;
695 else if (FuncIterated)
700 if (ModifiedDTOnIteration != ModifyDT::NotModifyDT)
705 FuncIterated = IsHugeFunc;
708 MadeChange |= mergeSExts(
F);
709 if (!LargeOffsetGEPMap.
empty())
710 MadeChange |= splitLargeGEPOffsets();
711 MadeChange |= optimizePhiTypes(
F);
714 eliminateFallThrough(
F);
718 assert(getDT().
verify(DominatorTree::VerificationLevel::Fast) &&
719 "Incorrect DominatorTree updates in CGP");
726 for (Instruction *
I : RemovedInsts)
729 EverMadeChange |= MadeChange;
730 SeenChainsForSExt.
clear();
731 ValToSExtendedUses.clear();
732 RemovedInsts.clear();
733 LargeOffsetGEPMap.
clear();
734 LargeOffsetGEPID.
clear();
748 SmallSetVector<BasicBlock *, 8> WorkList;
749 for (BasicBlock &BB :
F) {
755 for (BasicBlock *Succ : Successors)
761 MadeChange |= !WorkList.
empty();
762 while (!WorkList.
empty()) {
768 for (BasicBlock *Succ : Successors)
778 if (EverMadeChange || MadeChange)
779 MadeChange |= eliminateFallThrough(
F);
781 EverMadeChange |= MadeChange;
786 for (BasicBlock &BB :
F)
787 for (Instruction &
I : BB)
790 for (
auto &
I : Statepoints)
791 EverMadeChange |= simplifyOffsetableRelocate(*
I);
796 EverMadeChange |= placeDbgValues(
F);
797 EverMadeChange |= placePseudoProbes(
F);
804 return EverMadeChange;
807bool CodeGenPrepare::eliminateAssumptions(Function &
F) {
808 bool MadeChange =
false;
809 for (BasicBlock &BB :
F) {
810 CurInstIterator = BB.begin();
811 while (CurInstIterator != BB.end()) {
816 Assume->eraseFromParent();
818 resetIteratorIfInvalidatedWhileCalling(&BB, [&]() {
829void CodeGenPrepare::removeAllAssertingVHReferences(
Value *V) {
830 LargeOffsetGEPMap.
erase(V);
831 NewGEPBases.
erase(V);
839 auto VecI = LargeOffsetGEPMap.
find(
GEP->getPointerOperand());
840 if (VecI == LargeOffsetGEPMap.
end())
843 auto &GEPVector = VecI->second;
846 if (GEPVector.empty())
847 LargeOffsetGEPMap.
erase(VecI);
851[[maybe_unused]]
void CodeGenPrepare::verifyBFIUpdates(Function &
F) {
852 DominatorTree NewDT(
F);
853 LoopInfo NewLI(NewDT);
854 BranchProbabilityInfo NewBPI(
F, NewLI, TLInfo);
855 BlockFrequencyInfo NewBFI(
F, NewBPI, NewLI);
856 NewBFI.verifyMatch(*BFI);
862bool CodeGenPrepare::eliminateFallThrough(Function &
F) {
864 SmallPtrSet<BasicBlock *, 8> Preds;
872 BasicBlock *SinglePred = BB->getSinglePredecessor();
875 if (!SinglePred || SinglePred == BB || BB->hasAddressTaken())
888 FreshBBs.
insert(SinglePred);
896 for (
auto *Pred : Preds)
904BasicBlock *CodeGenPrepare::findDestBlockOfMergeableEmptyBlock(BasicBlock *BB) {
913 if (BBI != BB->
begin()) {
924 if (!canMergeBlocks(BB, DestBB))
934bool CodeGenPrepare::eliminateMostlyEmptyBlocks(Function &
F,
bool &ResetLI) {
935 SmallPtrSet<BasicBlock *, 16> Preheaders;
937 while (!LoopList.empty()) {
938 Loop *
L = LoopList.pop_back_val();
940 if (BasicBlock *Preheader =
L->getLoopPreheader())
941 Preheaders.
insert(Preheader);
945 bool MadeChange =
false;
957 BasicBlock *DestBB = findDestBlockOfMergeableEmptyBlock(BB);
959 !isMergingEmptyBlockProfitable(BB, DestBB, Preheaders.
count(BB)))
962 ResetLI |= eliminateMostlyEmptyBlock(BB);
968bool CodeGenPrepare::isMergingEmptyBlockProfitable(BasicBlock *BB,
1019 SmallPtrSet<BasicBlock *, 16> SameIncomingValueBBs;
1024 if (DestBBPred == BB)
1028 return DestPN.getIncomingValueForBlock(BB) ==
1029 DestPN.getIncomingValueForBlock(DestBBPred);
1031 SameIncomingValueBBs.
insert(DestBBPred);
1037 if (SameIncomingValueBBs.
count(Pred))
1043 for (
auto *SameValueBB : SameIncomingValueBBs)
1044 if (SameValueBB->getUniquePredecessor() == Pred &&
1045 DestBB == findDestBlockOfMergeableEmptyBlock(SameValueBB))
1049 return !Limit || PredFreq <= *Limit;
1055bool CodeGenPrepare::canMergeBlocks(
const BasicBlock *BB,
1056 const BasicBlock *DestBB)
const {
1060 for (
const PHINode &PN : BB->
phis()) {
1061 for (
const User *U : PN.users()) {
1070 for (
unsigned I = 0,
E = UPN->getNumIncomingValues();
I !=
E; ++
I) {
1073 Insn->
getParent() != UPN->getIncomingBlock(
I))
1088 SmallPtrSet<const BasicBlock *, 16> BBPreds;
1091 for (
unsigned i = 0, e = BBPN->getNumIncomingValues(); i != e; ++i)
1092 BBPreds.
insert(BBPN->getIncomingBlock(i));
1100 if (BBPreds.
count(Pred)) {
1101 for (
const PHINode &PN : DestBB->
phis()) {
1102 const Value *V1 = PN.getIncomingValueForBlock(Pred);
1103 const Value *V2 = PN.getIncomingValueForBlock(BB);
1107 if (V2PN->getParent() == BB)
1108 V2 = V2PN->getIncomingValueForBlock(Pred);
1139bool CodeGenPrepare::eliminateMostlyEmptyBlock(BasicBlock *BB) {
1149 if (SinglePred != DestBB) {
1150 assert(SinglePred == BB &&
1151 "Single predecessor not the same as predecessor");
1160 FreshBBs.
insert(SinglePred);
1161 FreshBBs.
erase(DestBB);
1169 for (PHINode &PN : DestBB->
phis()) {
1171 Value *InVal = PN.removeIncomingValue(BB,
false);
1176 if (InValPhi && InValPhi->
getParent() == BB) {
1185 for (
unsigned i = 0, e = BBPN->getNumIncomingValues(); i != e; ++i)
1186 PN.addIncoming(InVal, BBPN->getIncomingBlock(i));
1189 PN.addIncoming(InVal, Pred);
1195 if (BI->hasMetadata(LLVMContext::MD_loop)) {
1203 SmallPtrSet<BasicBlock *, 8> SeenPreds;
1207 if (!PredOfDestBB.contains(Pred)) {
1208 if (SeenPreds.
insert(Pred).second)
1209 DTUpdates.
push_back({DominatorTree::Insert, Pred, DestBB});
1214 if (SeenPreds.
insert(Pred).second)
1215 DTUpdates.
push_back({DominatorTree::Delete, Pred, BB});
1217 DTUpdates.
push_back({DominatorTree::Delete, BB, DestBB});
1237 for (
auto *ThisRelocate : AllRelocateCalls) {
1238 auto K = std::make_pair(ThisRelocate->getBasePtrIndex(),
1239 ThisRelocate->getDerivedPtrIndex());
1240 RelocateIdxMap.
insert(std::make_pair(K, ThisRelocate));
1242 for (
auto &Item : RelocateIdxMap) {
1243 std::pair<unsigned, unsigned>
Key = Item.first;
1244 if (
Key.first ==
Key.second)
1249 auto BaseKey = std::make_pair(
Key.first,
Key.first);
1252 auto MaybeBase = RelocateIdxMap.
find(BaseKey);
1253 if (MaybeBase == RelocateIdxMap.
end())
1258 RelocateInstMap[MaybeBase->second].push_back(
I);
1266 for (
unsigned i = 1; i <
GEP->getNumOperands(); i++) {
1269 if (!
Op ||
Op->getZExtValue() > 20)
1273 for (
unsigned i = 1; i <
GEP->getNumOperands(); i++)
1283 bool MadeChange =
false;
1290 for (
auto R = RelocatedBase->
getParent()->getFirstInsertionPt();
1291 &*R != RelocatedBase; ++R)
1295 RelocatedBase->
moveBefore(RI->getIterator());
1302 "Not relocating a derived object of the original base object");
1303 if (ToReplace->getBasePtrIndex() == ToReplace->getDerivedPtrIndex()) {
1308 if (RelocatedBase->
getParent() != ToReplace->getParent()) {
1318 if (!Derived || Derived->getPointerOperand() !=
Base)
1327 "Should always have one since it's not a terminator");
1331 Builder.SetCurrentDebugLocation(ToReplace->getDebugLoc());
1355 Value *ActualRelocatedBase = RelocatedBase;
1356 if (RelocatedBase->
getType() !=
Base->getType()) {
1357 ActualRelocatedBase =
1358 Builder.CreateBitCast(RelocatedBase,
Base->getType());
1360 Value *Replacement =
1361 Builder.CreateGEP(Derived->getSourceElementType(), ActualRelocatedBase,
1367 Value *ActualReplacement = Replacement;
1368 if (Replacement->
getType() != ToReplace->getType()) {
1370 Builder.CreateBitCast(Replacement, ToReplace->
getType());
1373 ToReplace->eraseFromParent();
1397bool CodeGenPrepare::simplifyOffsetableRelocate(GCStatepointInst &
I) {
1398 bool MadeChange =
false;
1400 for (
auto *U :
I.users())
1407 if (AllRelocateCalls.
size() < 2)
1412 MapVector<GCRelocateInst *, SmallVector<GCRelocateInst *, 0>> RelocateInstMap;
1414 if (RelocateInstMap.
empty())
1417 for (
auto &Item : RelocateInstMap)
1431 bool MadeChange =
false;
1434 Use &TheUse = UI.getUse();
1441 UserBB = PN->getIncomingBlock(TheUse);
1449 if (
User->isEHPad())
1459 if (UserBB == DefBB)
1463 CastInst *&InsertedCast = InsertedCasts[UserBB];
1465 if (!InsertedCast) {
1473 TheUse = InsertedCast;
1499 ASC->getDestAddressSpace()))
1554static std::optional<std::pair<Instruction *, Constant *>>
1557 if (!L || L->getHeader() != PN->
getParent() || !L->getLoopLatch())
1558 return std::nullopt;
1561 if (!IVInc || LI->
getLoopFor(IVInc->getParent()) != L)
1562 return std::nullopt;
1566 return std::make_pair(IVInc, Step);
1567 return std::nullopt;
1580 return IVInc->first ==
I;
1584bool CodeGenPrepare::replaceMathCmpWithIntrinsic(BinaryOperator *BO,
1588 auto IsReplacableIVIncrement = [
this, &
Cmp](BinaryOperator *BO) {
1592 assert(L &&
"L should not be null after isIVIncrement()");
1607 return BO->
hasOneUse() && DT.dominates(
Cmp->getParent(),
L->getLoopLatch());
1609 if (BO->
getParent() !=
Cmp->getParent() && !IsReplacableIVIncrement(BO)) {
1632 if (BO->
getOpcode() == Instruction::Add &&
1633 IID == Intrinsic::usub_with_overflow) {
1640 for (Instruction &Iter : *
Cmp->getParent()) {
1643 if ((BO->
getOpcode() != Instruction::Xor && &Iter == BO) || &Iter == Cmp) {
1648 assert(InsertPt !=
nullptr &&
"Parent block did not contain cmp or binop");
1651 Value *MathOV = Builder.CreateBinaryIntrinsic(IID, Arg0, Arg1);
1652 if (BO->
getOpcode() != Instruction::Xor) {
1653 Value *Math = Builder.CreateExtractValue(MathOV, 0,
"math");
1657 "Patterns with XOr should use the BO only in the compare");
1658 Value *OV = Builder.CreateExtractValue(MathOV, 1,
"ov");
1660 Cmp->eraseFromParent();
1670 Value *
A = Cmp->getOperand(0), *
B = Cmp->getOperand(1);
1678 B = ConstantInt::get(
B->getType(), 1);
1686 for (
User *U :
A->users()) {
1697bool CodeGenPrepare::combineToUAddWithOverflow(CmpInst *Cmp,
1698 ModifyDT &ModifiedDT) {
1699 bool EdgeCase =
false;
1701 BinaryOperator *
Add;
1706 A =
Add->getOperand(0);
1707 B =
Add->getOperand(1);
1713 Add->hasNUsesOrMore(EdgeCase ? 1 : 2)))
1719 if (
Add->getParent() !=
Cmp->getParent() && !
Add->hasOneUse())
1722 if (!replaceMathCmpWithIntrinsic(
Add,
A,
B, Cmp,
1723 Intrinsic::uadd_with_overflow))
1727 ModifiedDT = ModifyDT::ModifyInstDT;
1731bool CodeGenPrepare::combineToUSubWithOverflow(CmpInst *Cmp,
1732 ModifyDT &ModifiedDT) {
1739 ICmpInst::Predicate Pred =
Cmp->getPredicate();
1740 if (Pred == ICmpInst::ICMP_UGT) {
1742 Pred = ICmpInst::ICMP_ULT;
1746 B = ConstantInt::get(
B->getType(), 1);
1747 Pred = ICmpInst::ICMP_ULT;
1752 Pred = ICmpInst::ICMP_ULT;
1754 if (Pred != ICmpInst::ICMP_ULT)
1761 BinaryOperator *
Sub =
nullptr;
1762 for (User *U : CmpVariableOperand->
users()) {
1770 const APInt *CmpC, *AddC;
1782 Sub->hasNUsesOrMore(1)))
1788 if (
Sub->getParent() !=
Cmp->getParent() && !
Sub->hasOneUse())
1791 if (!replaceMathCmpWithIntrinsic(
Sub,
Sub->getOperand(0),
Sub->getOperand(1),
1792 Cmp, Intrinsic::usub_with_overflow))
1796 ModifiedDT = ModifyDT::ModifyInstDT;
1803bool CodeGenPrepare::unfoldPowerOf2Test(CmpInst *Cmp) {
1817 if (!IsStrictlyPowerOf2Test && !IsPowerOf2OrZeroTest)
1823 Type *OpTy =
X->getType();
1831 if (Pred == ICmpInst::ICMP_EQ) {
1832 Cmp->setOperand(1, ConstantInt::get(OpTy, 2));
1833 Cmp->setPredicate(ICmpInst::ICMP_ULT);
1835 Cmp->setPredicate(ICmpInst::ICMP_UGT);
1841 if (IsPowerOf2OrZeroTest ||
1852 NewCmp = Builder.CreateICmp(NewPred,
And, ConstantInt::getNullValue(OpTy));
1861 NewCmp = Builder.CreateICmp(NewPred,
Xor,
Sub);
1864 Cmp->replaceAllUsesWith(NewCmp);
1884 bool UsedInPhiOrCurrentBlock =
any_of(Cmp->users(), [Cmp](
User *U) {
1885 return isa<PHINode>(U) ||
1886 cast<Instruction>(U)->getParent() == Cmp->getParent();
1891 if (UsedInPhiOrCurrentBlock && Cmp->getOperand(0)->getType()->isIntegerTy() &&
1892 Cmp->getOperand(0)->getType()->getScalarSizeInBits() >
1893 DL.getLargestLegalIntTypeSizeInBits())
1899 bool MadeChange =
false;
1902 Use &TheUse = UI.getUse();
1917 if (UserBB == DefBB)
1921 CmpInst *&InsertedCmp = InsertedCmps[UserBB];
1927 Cmp->getOperand(0), Cmp->getOperand(1),
"");
1934 TheUse = InsertedCmp;
1940 if (Cmp->use_empty()) {
1941 Cmp->eraseFromParent();
1978 for (
User *U : Cmp->users()) {
2000 if (CmpBB != FalseBB)
2003 Value *CmpOp0 = Cmp->getOperand(0), *CmpOp1 = Cmp->getOperand(1);
2017 for (
User *U : Cmp->users()) {
2019 BI->swapSuccessors();
2025 SI->swapProfMetadata();
2037 Value *Op0 = Cmp->getOperand(0);
2038 Value *Op1 = Cmp->getOperand(1);
2047 unsigned NumInspected = 0;
2050 if (++NumInspected > 128)
2058 if (GoodToSwap > 0) {
2059 Cmp->swapOperands();
2079 auto ShouldReverseTransform = [](
FPClassTest ClassTest) {
2082 auto [ClassVal, ClassTest] =
2088 if (!ShouldReverseTransform(ClassTest) && !ShouldReverseTransform(~ClassTest))
2092 Value *IsFPClass = Builder.createIsFPClass(ClassVal, ClassTest);
2093 Cmp->replaceAllUsesWith(IsFPClass);
2101 Value *Incr, *RemAmt;
2106 Value *AddInst, *AddOffset;
2109 if (PN !=
nullptr) {
2111 AddOffset =
nullptr;
2120 if (PN !=
nullptr) {
2133 if (PN->getNumIncomingValues() != 2)
2138 if (!L || !L->getLoopPreheader() || !L->getLoopLatch())
2142 if (!L->contains(Rem))
2146 if (!L->isLoopInvariant(RemAmt))
2150 if (AddOffset && !L->isLoopInvariant(AddOffset))
2171 AddInstOut = AddInst;
2172 AddOffsetOut = AddOffset;
2191 Value *AddOffset, *RemAmt, *AddInst;
2194 AddOffset, LoopIncrPN))
2219 assert(AddOffset &&
"We found an add but missing values");
2238 Builder.SetInsertPoint(LoopIncrPN);
2239 PHINode *NewRem = Builder.CreatePHI(Ty, 2);
2244 Value *RemAdd = Builder.CreateNUWAdd(NewRem, ConstantInt::get(Ty, 1));
2249 NewRem->
addIncoming(Start, L->getLoopPreheader());
2254 FreshBBs.
insert(L->getLoopLatch());
2265bool CodeGenPrepare::optimizeURem(Instruction *Rem) {
2271bool CodeGenPrepare::optimizeCmp(CmpInst *Cmp, ModifyDT &ModifiedDT) {
2275 if (combineToUAddWithOverflow(Cmp, ModifiedDT))
2278 if (combineToUSubWithOverflow(Cmp, ModifiedDT))
2281 if (unfoldPowerOf2Test(Cmp))
2302 SetOfInstrs &InsertedInsts) {
2305 assert(!InsertedInsts.count(AndI) &&
2306 "Attempting to optimize already optimized and instruction");
2307 (void)InsertedInsts;
2321 for (
auto *U : AndI->
users()) {
2329 if (!CmpC || !CmpC->
isZero())
2344 Use &TheUse = UI.getUse();
2362 TheUse = InsertedAnd;
2379 if (
User->getOpcode() != Instruction::And ||
2385 if ((Cimm & (Cimm + 1)).getBoolValue())
2399 bool MadeChange =
false;
2402 TruncE = TruncI->user_end();
2403 TruncUI != TruncE;) {
2405 Use &TruncTheUse = TruncUI.getUse();
2430 if (UserBB == TruncUserBB)
2434 CastInst *&InsertedTrunc = InsertedTruncs[TruncUserBB];
2436 if (!InsertedShift && !InsertedTrunc) {
2440 if (ShiftI->
getOpcode() == Instruction::AShr)
2442 BinaryOperator::CreateAShr(ShiftI->
getOperand(0), CI,
"");
2445 BinaryOperator::CreateLShr(ShiftI->
getOperand(0), CI,
"");
2453 TruncInsertPt.setHeadBit(
true);
2454 assert(TruncInsertPt != TruncUserBB->
end());
2458 InsertedTrunc->
insertBefore(*TruncUserBB, TruncInsertPt);
2459 InsertedTrunc->
setDebugLoc(TruncI->getDebugLoc());
2463 TruncTheUse = InsertedTrunc;
2496 bool MadeChange =
false;
2499 Use &TheUse = UI.getUse();
2513 if (UserBB == DefBB) {
2541 if (!InsertedShift) {
2545 if (ShiftI->
getOpcode() == Instruction::AShr)
2547 BinaryOperator::CreateAShr(ShiftI->
getOperand(0), CI,
"");
2550 BinaryOperator::CreateLShr(ShiftI->
getOperand(0), CI,
"");
2558 TheUse = InsertedShift;
2606 unsigned SizeInBits = Ty->getScalarSizeInBits();
2607 if (Ty->isVectorTy())
2618 nullptr,
"cond.false");
2620 FreshBBs.
insert(CallBlock);
2627 SplitPt.setHeadBit(
true);
2629 nullptr,
"cond.end");
2631 FreshBBs.
insert(EndBlock);
2636 Builder.SetCurrentDebugLocation(CountZeros->
getDebugLoc());
2643 Op = Builder.CreateFreeze(
Op,
Op->getName() +
".fr");
2644 Value *Cmp = Builder.CreateICmpEQ(
Op, Zero,
"cmpz");
2645 Builder.CreateCondBr(Cmp, EndBlock, CallBlock);
2651 Builder.SetInsertPoint(EndBlock, EndBlock->
begin());
2652 PHINode *PN = Builder.CreatePHI(Ty, 2,
"ctz");
2662 ModifiedDT = ModifyDT::ModifyBBDT;
2666bool CodeGenPrepare::optimizeCallInst(CallInst *CI, ModifyDT &ModifiedDT) {
2670 if (CI->
isInlineAsm() && optimizeInlineAsmInst(CI))
2678 for (
auto &Arg : CI->
args()) {
2683 if (!Arg->getType()->isPointerTy())
2685 APInt
Offset(
DL->getIndexSizeInBits(
2688 Value *Val = Arg->stripAndAccumulateInBoundsConstantOffsets(*
DL,
Offset);
2689 uint64_t Offset2 =
Offset.getLimitedValue();
2695 if (AllocaSize && AllocaSize->getKnownMinValue() >= MinSize + Offset2)
2713 MaybeAlign MIDestAlign =
MI->getDestAlign();
2714 if (!MIDestAlign || DestAlign > *MIDestAlign)
2715 MI->setDestAlignment(DestAlign);
2717 MaybeAlign MTISrcAlign = MTI->getSourceAlign();
2719 if (!MTISrcAlign || SrcAlign > *MTISrcAlign)
2720 MTI->setSourceAlignment(SrcAlign);
2730 for (
auto &Arg : CI->
args()) {
2731 if (!Arg->getType()->isPointerTy())
2733 unsigned AS = Arg->getType()->getPointerAddressSpace();
2734 if (optimizeMemoryInst(CI, Arg, Arg->getType(), AS))
2740 switch (
II->getIntrinsicID()) {
2743 case Intrinsic::assume:
2745 case Intrinsic::allow_runtime_check:
2746 case Intrinsic::allow_ubsan_check:
2747 case Intrinsic::experimental_widenable_condition: {
2751 if (
II->use_empty()) {
2752 II->eraseFromParent();
2756 resetIteratorIfInvalidatedWhileCalling(BB, [&]() {
2761 case Intrinsic::objectsize:
2763 case Intrinsic::is_constant:
2765 case Intrinsic::aarch64_stlxr:
2766 case Intrinsic::aarch64_stxr: {
2775 InsertedInsts.insert(ExtVal);
2779 case Intrinsic::launder_invariant_group:
2780 case Intrinsic::strip_invariant_group: {
2781 Value *ArgVal =
II->getArgOperand(0);
2782 auto it = LargeOffsetGEPMap.
find(
II);
2783 if (it != LargeOffsetGEPMap.
end()) {
2787 auto GEPs = std::move(it->second);
2788 LargeOffsetGEPMap[ArgVal].append(GEPs.begin(), GEPs.end());
2793 II->eraseFromParent();
2796 case Intrinsic::cttz:
2797 case Intrinsic::ctlz:
2801 case Intrinsic::fshl:
2802 case Intrinsic::fshr:
2803 return optimizeFunnelShift(
II);
2804 case Intrinsic::masked_gather:
2805 return optimizeGatherScatterInst(
II,
II->getArgOperand(0));
2806 case Intrinsic::masked_scatter:
2807 return optimizeGatherScatterInst(
II,
II->getArgOperand(1));
2808 case Intrinsic::masked_load:
2811 if (VT->getNumElements() == 1) {
2812 Value *PtrVal =
II->getArgOperand(0);
2814 if (optimizeMemoryInst(
II, PtrVal, VT->getElementType(), AS))
2819 case Intrinsic::masked_store:
2823 if (VT->getNumElements() == 1) {
2824 Value *PtrVal =
II->getArgOperand(1);
2826 if (optimizeMemoryInst(
II, PtrVal, VT->getElementType(), AS))
2831 case Intrinsic::umul_with_overflow:
2832 return optimizeMulWithOverflow(
II,
false, ModifiedDT);
2833 case Intrinsic::smul_with_overflow:
2834 return optimizeMulWithOverflow(
II,
true, ModifiedDT);
2837 SmallVector<Value *, 2> PtrOps;
2840 while (!PtrOps.
empty()) {
2843 if (optimizeMemoryInst(
II, PtrVal, AccessTy, AS))
2857 FortifiedLibCallSimplifier Simplifier(TLInfo,
true);
2859 if (
Value *V = Simplifier.optimizeCall(CI, Builder)) {
2869 auto GetUniformReturnValue = [](
const Function *
F) -> GlobalVariable * {
2870 if (!
F->getReturnType()->isPointerTy())
2873 GlobalVariable *UniformValue =
nullptr;
2874 for (
auto &BB : *
F) {
2879 else if (V != UniformValue)
2887 return UniformValue;
2890 if (
Callee->hasExactDefinition()) {
2891 if (GlobalVariable *RV = GetUniformReturnValue(Callee)) {
2892 bool MadeChange =
false;
2918 switch (
II->getIntrinsicID()) {
2919 case Intrinsic::memset:
2920 case Intrinsic::memcpy:
2921 case Intrinsic::memmove:
2929 if (Callee && TLInfo && TLInfo->
getLibFunc(*Callee, LF))
2931 case LibFunc_strcpy:
2932 case LibFunc_strncpy:
2933 case LibFunc_strcat:
2934 case LibFunc_strncat:
2975bool CodeGenPrepare::dupRetToEnableTailCallOpts(BasicBlock *BB,
2976 ModifyDT &ModifiedDT) {
2984 assert(LI->
getLoopFor(BB) ==
nullptr &&
"A return block cannot be in a loop");
2986 PHINode *PN =
nullptr;
2987 ExtractValueInst *EVI =
nullptr;
2988 BitCastInst *BCI =
nullptr;
3008 auto isLifetimeEndOrBitCastFor = [](
const Instruction *Inst) {
3014 return II->getIntrinsicID() == Intrinsic::lifetime_end;
3020 auto isFakeUse = [&FakeUses](
const Instruction *Inst) {
3022 II &&
II->getIntrinsicID() == Intrinsic::fake_use) {
3044 isLifetimeEndOrBitCastFor(&*BI) || isFakeUse(&*BI))
3051 auto MayBePermittedAsTailCall = [&](
const auto *CI) {
3068 MayBePermittedAsTailCall(CI)) {
3089 MayBePermittedAsTailCall(CI)) {
3096 SmallPtrSet<BasicBlock *, 4> VisitedBBs;
3098 if (!VisitedBBs.
insert(Pred).second)
3100 if (Instruction *
I = Pred->rbegin()->getPrevNode()) {
3102 if (CI && CI->
use_empty() && MayBePermittedAsTailCall(CI)) {
3117 for (
auto const &TailCallBB : TailCallBBs) {
3130 ModifiedDT = ModifyDT::ModifyBBDT;
3139 for (
auto *CI : CallInsts) {
3140 for (
auto const *FakeUse : FakeUses) {
3141 auto *ClonedInst = FakeUse->clone();
3159struct ExtAddrMode :
public TargetLowering::AddrMode {
3160 Value *BaseReg =
nullptr;
3161 Value *ScaledReg =
nullptr;
3162 Value *OriginalValue =
nullptr;
3163 bool InBounds =
true;
3167 BaseRegField = 0x01,
3169 BaseOffsField = 0x04,
3170 ScaledRegField = 0x08,
3172 MultipleFields = 0xff
3175 ExtAddrMode() =
default;
3177 void print(raw_ostream &OS)
const;
3184 if (ScaledReg == From)
3188 FieldName
compare(
const ExtAddrMode &other) {
3191 if (BaseReg && other.
BaseReg &&
3193 return MultipleFields;
3194 if (BaseGV && other.BaseGV && BaseGV->getType() != other.BaseGV->getType())
3195 return MultipleFields;
3198 return MultipleFields;
3201 if (InBounds != other.InBounds)
3202 return MultipleFields;
3205 unsigned Result = NoField;
3208 if (BaseGV != other.BaseGV)
3210 if (BaseOffs != other.BaseOffs)
3213 Result |= ScaledRegField;
3216 if (Scale && other.
Scale && Scale != other.
Scale)
3220 return MultipleFields;
3222 return static_cast<FieldName
>(
Result);
3232 return !BaseOffs && !Scale && !(BaseGV &&
BaseReg);
3243 case ScaledRegField:
3250 void SetCombinedField(FieldName
Field,
Value *V,
3251 const SmallVectorImpl<ExtAddrMode> &AddrModes) {
3256 case ExtAddrMode::BaseRegField:
3259 case ExtAddrMode::BaseGVField:
3262 assert(BaseReg ==
nullptr);
3266 case ExtAddrMode::ScaledRegField:
3271 for (
const ExtAddrMode &AM : AddrModes)
3277 case ExtAddrMode::BaseOffsField:
3280 assert(ScaledReg ==
nullptr);
3290static inline raw_ostream &
operator<<(raw_ostream &OS,
const ExtAddrMode &AM) {
3296#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
3297void ExtAddrMode::print(raw_ostream &OS)
const {
3298 bool NeedPlus =
false;
3304 BaseGV->printAsOperand(OS,
false);
3309 OS << (NeedPlus ?
" + " :
"") << BaseOffs;
3314 OS << (NeedPlus ?
" + " :
"") <<
"Base:";
3315 BaseReg->printAsOperand(OS,
false);
3319 OS << (NeedPlus ?
" + " :
"") << Scale <<
"*";
3342class TypePromotionTransaction {
3346 class TypePromotionAction {
3354 TypePromotionAction(Instruction *Inst) : Inst(Inst) {}
3356 virtual ~TypePromotionAction() =
default;
3363 virtual void undo() = 0;
3368 virtual void commit() {
3374 class InsertionHandler {
3383 std::optional<DbgRecord::self_iterator> BeforeDbgRecord = std::nullopt;
3386 bool HasPrevInstruction;
3390 InsertionHandler(Instruction *Inst) {
3398 if (HasPrevInstruction) {
3406 void insert(Instruction *Inst) {
3407 if (HasPrevInstruction) {
3419 Inst->
getParent()->reinsertInstInDbgRecords(Inst, BeforeDbgRecord);
3424 class InstructionMoveBefore :
public TypePromotionAction {
3426 InsertionHandler Position;
3431 : TypePromotionAction(Inst), Position(Inst) {
3432 LLVM_DEBUG(
dbgs() <<
"Do: move: " << *Inst <<
"\nbefore: " << *Before
3438 void undo()
override {
3440 Position.insert(Inst);
3445 class OperandSetter :
public TypePromotionAction {
3454 OperandSetter(Instruction *Inst,
unsigned Idx,
Value *NewVal)
3455 : TypePromotionAction(Inst), Idx(Idx) {
3457 <<
"for:" << *Inst <<
"\n"
3458 <<
"with:" << *NewVal <<
"\n");
3464 void undo()
override {
3466 <<
"for: " << *Inst <<
"\n"
3467 <<
"with: " << *Origin <<
"\n");
3474 class OperandsHider :
public TypePromotionAction {
3476 SmallVector<Value *, 4> OriginalValues;
3480 OperandsHider(Instruction *Inst) : TypePromotionAction(Inst) {
3483 OriginalValues.
reserve(NumOpnds);
3484 for (
unsigned It = 0; It < NumOpnds; ++It) {
3496 void undo()
override {
3498 for (
unsigned It = 0, EndIt = OriginalValues.
size(); It != EndIt; ++It)
3504 class TruncBuilder :
public TypePromotionAction {
3511 TruncBuilder(Instruction *Opnd,
Type *Ty) : TypePromotionAction(Opnd) {
3513 Builder.SetCurrentDebugLocation(
DebugLoc());
3514 Val = Builder.CreateTrunc(Opnd, Ty,
"promoted");
3519 Value *getBuiltValue() {
return Val; }
3522 void undo()
override {
3525 IVal->eraseFromParent();
3530 class SExtBuilder :
public TypePromotionAction {
3537 SExtBuilder(Instruction *InsertPt,
Value *Opnd,
Type *Ty)
3538 : TypePromotionAction(InsertPt) {
3540 Val = Builder.CreateSExt(Opnd, Ty,
"promoted");
3545 Value *getBuiltValue() {
return Val; }
3548 void undo()
override {
3551 IVal->eraseFromParent();
3556 class ZExtBuilder :
public TypePromotionAction {
3563 ZExtBuilder(Instruction *InsertPt,
Value *Opnd,
Type *Ty)
3564 : TypePromotionAction(InsertPt) {
3566 Builder.SetCurrentDebugLocation(
DebugLoc());
3567 Val = Builder.CreateZExt(Opnd, Ty,
"promoted");
3572 Value *getBuiltValue() {
return Val; }
3575 void undo()
override {
3578 IVal->eraseFromParent();
3583 class TypeMutator :
public TypePromotionAction {
3589 TypeMutator(Instruction *Inst,
Type *NewTy)
3590 : TypePromotionAction(Inst), OrigTy(Inst->
getType()) {
3591 LLVM_DEBUG(
dbgs() <<
"Do: MutateType: " << *Inst <<
" with " << *NewTy
3597 void undo()
override {
3598 LLVM_DEBUG(
dbgs() <<
"Undo: MutateType: " << *Inst <<
" with " << *OrigTy
3605 class UsesReplacer :
public TypePromotionAction {
3607 struct InstructionAndIdx {
3614 InstructionAndIdx(Instruction *Inst,
unsigned Idx)
3615 : Inst(Inst), Idx(Idx) {}
3621 SmallVector<DbgVariableRecord *, 1> DbgVariableRecords;
3631 UsesReplacer(Instruction *Inst,
Value *New)
3632 : TypePromotionAction(Inst),
New(
New) {
3633 LLVM_DEBUG(
dbgs() <<
"Do: UsersReplacer: " << *Inst <<
" with " << *New
3636 for (Use &U : Inst->
uses()) {
3638 OriginalUses.
push_back(InstructionAndIdx(UserI,
U.getOperandNo()));
3649 void undo()
override {
3651 for (InstructionAndIdx &Use : OriginalUses)
3652 Use.Inst->setOperand(
Use.Idx, Inst);
3657 for (DbgVariableRecord *DVR : DbgVariableRecords)
3658 DVR->replaceVariableLocationOp(New, Inst);
3663 class InstructionRemover :
public TypePromotionAction {
3665 InsertionHandler Inserter;
3669 OperandsHider Hider;
3672 UsesReplacer *Replacer =
nullptr;
3675 SetOfInstrs &RemovedInsts;
3682 InstructionRemover(Instruction *Inst, SetOfInstrs &RemovedInsts,
3683 Value *New =
nullptr)
3684 : TypePromotionAction(Inst), Inserter(Inst), Hider(Inst),
3685 RemovedInsts(RemovedInsts) {
3687 Replacer =
new UsesReplacer(Inst, New);
3688 LLVM_DEBUG(
dbgs() <<
"Do: InstructionRemover: " << *Inst <<
"\n");
3689 RemovedInsts.insert(Inst);
3696 ~InstructionRemover()
override {
delete Replacer; }
3698 InstructionRemover &operator=(
const InstructionRemover &other) =
delete;
3699 InstructionRemover(
const InstructionRemover &other) =
delete;
3703 void undo()
override {
3704 LLVM_DEBUG(
dbgs() <<
"Undo: InstructionRemover: " << *Inst <<
"\n");
3705 Inserter.insert(Inst);
3709 RemovedInsts.erase(Inst);
3717 using ConstRestorationPt =
const TypePromotionAction *;
3719 TypePromotionTransaction(SetOfInstrs &RemovedInsts)
3720 : RemovedInsts(RemovedInsts) {}
3727 void rollback(ConstRestorationPt Point);
3730 ConstRestorationPt getRestorationPoint()
const;
3735 void setOperand(Instruction *Inst,
unsigned Idx,
Value *NewVal);
3744 void mutateType(Instruction *Inst,
Type *NewTy);
3747 Value *createTrunc(Instruction *Opnd,
Type *Ty);
3760 SmallVectorImpl<std::unique_ptr<TypePromotionAction>>::iterator;
3762 SetOfInstrs &RemovedInsts;
3767void TypePromotionTransaction::setOperand(Instruction *Inst,
unsigned Idx,
3769 Actions.push_back(std::make_unique<TypePromotionTransaction::OperandSetter>(
3770 Inst, Idx, NewVal));
3773void TypePromotionTransaction::eraseInstruction(Instruction *Inst,
3776 std::make_unique<TypePromotionTransaction::InstructionRemover>(
3777 Inst, RemovedInsts, NewVal));
3780void TypePromotionTransaction::replaceAllUsesWith(Instruction *Inst,
3783 std::make_unique<TypePromotionTransaction::UsesReplacer>(Inst, New));
3786void TypePromotionTransaction::mutateType(Instruction *Inst,
Type *NewTy) {
3788 std::make_unique<TypePromotionTransaction::TypeMutator>(Inst, NewTy));
3791Value *TypePromotionTransaction::createTrunc(Instruction *Opnd,
Type *Ty) {
3792 std::unique_ptr<TruncBuilder> Ptr(
new TruncBuilder(Opnd, Ty));
3793 Value *Val = Ptr->getBuiltValue();
3794 Actions.push_back(std::move(Ptr));
3798Value *TypePromotionTransaction::createSExt(Instruction *Inst,
Value *Opnd,
3800 std::unique_ptr<SExtBuilder> Ptr(
new SExtBuilder(Inst, Opnd, Ty));
3801 Value *Val = Ptr->getBuiltValue();
3802 Actions.push_back(std::move(Ptr));
3806Value *TypePromotionTransaction::createZExt(Instruction *Inst,
Value *Opnd,
3808 std::unique_ptr<ZExtBuilder> Ptr(
new ZExtBuilder(Inst, Opnd, Ty));
3809 Value *Val = Ptr->getBuiltValue();
3810 Actions.push_back(std::move(Ptr));
3814TypePromotionTransaction::ConstRestorationPt
3815TypePromotionTransaction::getRestorationPoint()
const {
3816 return !Actions.empty() ? Actions.back().get() :
nullptr;
3819bool TypePromotionTransaction::commit() {
3820 for (std::unique_ptr<TypePromotionAction> &Action : Actions)
3827void TypePromotionTransaction::rollback(
3828 TypePromotionTransaction::ConstRestorationPt Point) {
3829 while (!Actions.empty() && Point != Actions.back().get()) {
3830 std::unique_ptr<TypePromotionAction> Curr = Actions.pop_back_val();
3840class AddressingModeMatcher {
3841 SmallVectorImpl<Instruction *> &AddrModeInsts;
3842 const TargetLowering &TLI;
3843 const TargetRegisterInfo &
TRI;
3844 const DataLayout &
DL;
3846 const std::function<
const DominatorTree &()> getDTFn;
3859 const SetOfInstrs &InsertedInsts;
3862 InstrToOrigTy &PromotedInsts;
3865 TypePromotionTransaction &TPT;
3868 std::pair<AssertingVH<GetElementPtrInst>, int64_t> &LargeOffsetGEP;
3872 bool IgnoreProfitability;
3875 bool OptSize =
false;
3877 ProfileSummaryInfo *PSI;
3878 BlockFrequencyInfo *BFI;
3880 AddressingModeMatcher(
3881 SmallVectorImpl<Instruction *> &AMI,
const TargetLowering &TLI,
3882 const TargetRegisterInfo &
TRI,
const LoopInfo &LI,
3883 const std::function<
const DominatorTree &()> getDTFn,
Type *AT,
3884 unsigned AS, Instruction *
MI, ExtAddrMode &AM,
3885 const SetOfInstrs &InsertedInsts, InstrToOrigTy &PromotedInsts,
3886 TypePromotionTransaction &TPT,
3887 std::pair<AssertingVH<GetElementPtrInst>, int64_t> &LargeOffsetGEP,
3888 bool OptSize, ProfileSummaryInfo *PSI, BlockFrequencyInfo *BFI)
3889 : AddrModeInsts(AMI), TLI(TLI),
TRI(
TRI),
3890 DL(
MI->getDataLayout()), LI(LI), getDTFn(getDTFn),
3891 AccessTy(AT), AddrSpace(AS), MemoryInst(
MI),
AddrMode(AM),
3892 InsertedInsts(InsertedInsts), PromotedInsts(PromotedInsts), TPT(TPT),
3893 LargeOffsetGEP(LargeOffsetGEP), OptSize(OptSize), PSI(PSI), BFI(BFI) {
3894 IgnoreProfitability =
false;
3906 Match(
Value *V,
Type *AccessTy,
unsigned AS, Instruction *MemoryInst,
3907 SmallVectorImpl<Instruction *> &AddrModeInsts,
3908 const TargetLowering &TLI,
const LoopInfo &LI,
3909 const std::function<
const DominatorTree &()> getDTFn,
3910 const TargetRegisterInfo &
TRI,
const SetOfInstrs &InsertedInsts,
3911 InstrToOrigTy &PromotedInsts, TypePromotionTransaction &TPT,
3912 std::pair<AssertingVH<GetElementPtrInst>, int64_t> &LargeOffsetGEP,
3913 bool OptSize, ProfileSummaryInfo *PSI, BlockFrequencyInfo *BFI) {
3916 bool Success = AddressingModeMatcher(AddrModeInsts, TLI,
TRI, LI, getDTFn,
3917 AccessTy, AS, MemoryInst, Result,
3918 InsertedInsts, PromotedInsts, TPT,
3919 LargeOffsetGEP, OptSize, PSI, BFI)
3927 bool matchScaledValue(
Value *ScaleReg, int64_t Scale,
unsigned Depth);
3929 bool matchOperationAddr(User *AddrInst,
unsigned Opcode,
unsigned Depth,
3930 bool *MovedAway =
nullptr);
3931 bool isProfitableToFoldIntoAddressingMode(Instruction *
I,
3932 ExtAddrMode &AMBefore,
3933 ExtAddrMode &AMAfter);
3934 bool valueAlreadyLiveAtInst(
Value *Val,
Value *KnownLive1,
Value *KnownLive2);
3935 bool isPromotionProfitable(
unsigned NewCost,
unsigned OldCost,
3936 Value *PromotedOperand)
const;
3942class PhiNodeSetIterator {
3943 PhiNodeSet *
const Set;
3944 size_t CurrentIndex = 0;
3949 PhiNodeSetIterator(PhiNodeSet *
const Set,
size_t Start);
3951 PhiNodeSetIterator &operator++();
3967 friend class PhiNodeSetIterator;
3969 using MapType = SmallDenseMap<PHINode *, size_t, 32>;
3970 using iterator = PhiNodeSetIterator;
3985 size_t FirstValidElement = 0;
3991 bool insert(PHINode *Ptr) {
3992 if (NodeMap.insert(std::make_pair(Ptr,
NodeList.
size())).second) {
4002 bool erase(PHINode *Ptr) {
4003 if (NodeMap.erase(Ptr)) {
4004 SkipRemovedElements(FirstValidElement);
4014 FirstValidElement = 0;
4020 if (FirstValidElement == 0)
4021 SkipRemovedElements(FirstValidElement);
4022 return PhiNodeSetIterator(
this, FirstValidElement);
4029 size_t size()
const {
return NodeMap.size(); }
4032 size_t count(PHINode *Ptr)
const {
return NodeMap.count(Ptr); }
4040 void SkipRemovedElements(
size_t &CurrentIndex) {
4042 auto it = NodeMap.find(NodeList[CurrentIndex]);
4045 if (it != NodeMap.end() && it->second == CurrentIndex)
4052PhiNodeSetIterator::PhiNodeSetIterator(PhiNodeSet *
const Set,
size_t Start)
4055PHINode *PhiNodeSetIterator::operator*()
const {
4057 "PhiNodeSet access out of range");
4058 return Set->NodeList[CurrentIndex];
4061PhiNodeSetIterator &PhiNodeSetIterator::operator++() {
4063 "PhiNodeSet access out of range");
4065 Set->SkipRemovedElements(CurrentIndex);
4069bool PhiNodeSetIterator::operator==(
const PhiNodeSetIterator &
RHS)
const {
4070 return CurrentIndex ==
RHS.CurrentIndex;
4073bool PhiNodeSetIterator::operator!=(
const PhiNodeSetIterator &
RHS)
const {
4074 return !((*this) ==
RHS);
4080class SimplificationTracker {
4081 DenseMap<Value *, Value *> Storage;
4084 PhiNodeSet AllPhiNodes;
4086 SmallPtrSet<SelectInst *, 32> AllSelectNodes;
4091 auto SV = Storage.
find(V);
4092 if (SV == Storage.
end())
4100 void ReplacePhi(PHINode *From, PHINode *To) {
4101 Value *OldReplacement = Get(From);
4102 while (OldReplacement != From) {
4105 OldReplacement = Get(From);
4107 assert(To && Get(To) == To &&
"Replacement PHI node is already replaced.");
4110 AllPhiNodes.erase(From);
4114 PhiNodeSet &newPhiNodes() {
return AllPhiNodes; }
4116 void insertNewPhi(PHINode *PN) { AllPhiNodes.insert(PN); }
4118 void insertNewSelect(SelectInst *SI) { AllSelectNodes.
insert(SI); }
4120 unsigned countNewPhiNodes()
const {
return AllPhiNodes.size(); }
4122 unsigned countNewSelectNodes()
const {
return AllSelectNodes.
size(); }
4124 void destroyNewNodes(
Type *CommonType) {
4127 for (
auto *
I : AllPhiNodes) {
4128 I->replaceAllUsesWith(Dummy);
4129 I->eraseFromParent();
4131 AllPhiNodes.clear();
4132 for (
auto *
I : AllSelectNodes) {
4133 I->replaceAllUsesWith(Dummy);
4134 I->eraseFromParent();
4136 AllSelectNodes.clear();
4141class AddressingModeCombiner {
4142 typedef DenseMap<Value *, Value *> FoldAddrToValueMapping;
4143 typedef std::pair<PHINode *, PHINode *> PHIPair;
4150 ExtAddrMode::FieldName DifferentField = ExtAddrMode::NoField;
4153 bool AllAddrModesTrivial =
true;
4156 Type *CommonType =
nullptr;
4158 const DataLayout &
DL;
4164 Value *CommonValue =
nullptr;
4167 AddressingModeCombiner(
const DataLayout &
DL,
Value *OriginalValue)
4168 :
DL(
DL), Original(OriginalValue) {}
4170 ~AddressingModeCombiner() { eraseCommonValueIfDead(); }
4173 const ExtAddrMode &
getAddrMode()
const {
return AddrModes[0]; }
4178 bool addNewAddrMode(ExtAddrMode &NewAddrMode) {
4182 AllAddrModesTrivial = AllAddrModesTrivial && NewAddrMode.isTrivial();
4185 if (AddrModes.
empty()) {
4193 ExtAddrMode::FieldName ThisDifferentField =
4194 AddrModes[0].compare(NewAddrMode);
4195 if (DifferentField == ExtAddrMode::NoField)
4196 DifferentField = ThisDifferentField;
4197 else if (DifferentField != ThisDifferentField)
4198 DifferentField = ExtAddrMode::MultipleFields;
4201 bool CanHandle = DifferentField != ExtAddrMode::MultipleFields;
4204 CanHandle = CanHandle && DifferentField != ExtAddrMode::ScaleField;
4209 CanHandle = CanHandle && (DifferentField != ExtAddrMode::BaseOffsField ||
4214 CanHandle = CanHandle && (DifferentField != ExtAddrMode::BaseGVField ||
4215 !NewAddrMode.HasBaseReg);
4232 bool combineAddrModes() {
4234 if (AddrModes.
size() == 0)
4238 if (AddrModes.
size() == 1 || DifferentField == ExtAddrMode::NoField)
4243 if (AllAddrModesTrivial)
4246 if (!addrModeCombiningAllowed())
4252 FoldAddrToValueMapping
Map;
4253 if (!initializeMap(Map))
4256 CommonValue = findCommon(Map);
4258 AddrModes[0].SetCombinedField(DifferentField, CommonValue, AddrModes);
4259 return CommonValue !=
nullptr;
4265 void eraseCommonValueIfDead() {
4266 if (CommonValue && CommonValue->
use_empty())
4268 CommonInst->eraseFromParent();
4276 bool initializeMap(FoldAddrToValueMapping &Map) {
4279 SmallVector<Value *, 2> NullValue;
4280 Type *IntPtrTy =
DL.getIntPtrType(AddrModes[0].OriginalValue->
getType());
4281 for (
auto &AM : AddrModes) {
4282 Value *DV = AM.GetFieldAsValue(DifferentField, IntPtrTy);
4285 if (CommonType && CommonType !=
Type)
4288 Map[AM.OriginalValue] = DV;
4293 assert(CommonType &&
"At least one non-null value must be!");
4294 for (
auto *V : NullValue)
4322 Value *findCommon(FoldAddrToValueMapping &Map) {
4330 SimplificationTracker
ST;
4335 InsertPlaceholders(Map, TraverseOrder, ST);
4338 FillPlaceholders(Map, TraverseOrder, ST);
4341 ST.destroyNewNodes(CommonType);
4346 unsigned PhiNotMatchedCount = 0;
4348 ST.destroyNewNodes(CommonType);
4352 auto *
Result =
ST.Get(
Map.find(Original)->second);
4354 NumMemoryInstsPhiCreated +=
ST.countNewPhiNodes() + PhiNotMatchedCount;
4355 NumMemoryInstsSelectCreated +=
ST.countNewSelectNodes();
4362 bool MatchPhiNode(PHINode *
PHI, PHINode *Candidate,
4363 SmallSetVector<PHIPair, 8> &Matcher,
4364 PhiNodeSet &PhiNodesToMatch) {
4367 SmallPtrSet<PHINode *, 8> MatchedPHIs;
4370 SmallSet<PHIPair, 8> Visited;
4371 while (!WorkList.
empty()) {
4373 if (!Visited.
insert(Item).second)
4380 for (
auto *
B : Item.first->blocks()) {
4381 Value *FirstValue = Item.first->getIncomingValueForBlock(
B);
4382 Value *SecondValue = Item.second->getIncomingValueForBlock(
B);
4383 if (FirstValue == SecondValue)
4393 if (!FirstPhi || !SecondPhi || !PhiNodesToMatch.count(FirstPhi) ||
4398 if (Matcher.
count({FirstPhi, SecondPhi}))
4403 if (MatchedPHIs.
insert(FirstPhi).second)
4404 Matcher.
insert({FirstPhi, SecondPhi});
4406 WorkList.
push_back({FirstPhi, SecondPhi});
4415 bool MatchPhiSet(SimplificationTracker &ST,
bool AllowNewPhiNodes,
4416 unsigned &PhiNotMatchedCount) {
4420 SmallSetVector<PHIPair, 8> Matched;
4421 SmallPtrSet<PHINode *, 8> WillNotMatch;
4422 PhiNodeSet &PhiNodesToMatch =
ST.newPhiNodes();
4423 while (PhiNodesToMatch.size()) {
4424 PHINode *
PHI = *PhiNodesToMatch.begin();
4427 WillNotMatch.
clear();
4431 bool IsMatched =
false;
4432 for (
auto &
P :
PHI->getParent()->phis()) {
4434 if (PhiNodesToMatch.count(&
P))
4436 if ((IsMatched = MatchPhiNode(
PHI, &
P, Matched, PhiNodesToMatch)))
4446 for (
auto MV : Matched)
4447 ST.ReplacePhi(MV.first, MV.second);
4452 if (!AllowNewPhiNodes)
4455 PhiNotMatchedCount += WillNotMatch.
size();
4456 for (
auto *
P : WillNotMatch)
4457 PhiNodesToMatch.erase(
P);
4462 void FillPlaceholders(FoldAddrToValueMapping &Map,
4463 SmallVectorImpl<Value *> &TraverseOrder,
4464 SimplificationTracker &ST) {
4465 while (!TraverseOrder.
empty()) {
4467 assert(
Map.contains(Current) &&
"No node to fill!!!");
4473 auto *TrueValue = CurrentSelect->getTrueValue();
4474 assert(
Map.contains(TrueValue) &&
"No True Value!");
4475 Select->setTrueValue(
ST.Get(Map[TrueValue]));
4476 auto *FalseValue = CurrentSelect->getFalseValue();
4477 assert(
Map.contains(FalseValue) &&
"No False Value!");
4478 Select->setFalseValue(
ST.Get(Map[FalseValue]));
4485 assert(
Map.contains(PV) &&
"No predecessor Value!");
4486 PHI->addIncoming(
ST.Get(Map[PV]),
B);
4497 void InsertPlaceholders(FoldAddrToValueMapping &Map,
4498 SmallVectorImpl<Value *> &TraverseOrder,
4499 SimplificationTracker &ST) {
4502 "Address must be a Phi or Select node");
4505 while (!Worklist.
empty()) {
4508 if (
Map.contains(Current))
4519 CurrentSelect->getName(),
4520 CurrentSelect->getIterator(), CurrentSelect);
4524 Worklist.
push_back(CurrentSelect->getTrueValue());
4525 Worklist.
push_back(CurrentSelect->getFalseValue());
4533 ST.insertNewPhi(
PHI);
4539 bool addrModeCombiningAllowed() {
4542 switch (DifferentField) {
4545 case ExtAddrMode::BaseRegField:
4547 case ExtAddrMode::BaseGVField:
4549 case ExtAddrMode::BaseOffsField:
4551 case ExtAddrMode::ScaledRegField:
4561bool AddressingModeMatcher::matchScaledValue(
Value *ScaleReg, int64_t Scale,
4566 return matchAddr(ScaleReg,
Depth);
4577 ExtAddrMode TestAddrMode =
AddrMode;
4581 TestAddrMode.
Scale += Scale;
4595 ConstantInt *CI =
nullptr;
4596 Value *AddLHS =
nullptr;
4600 TestAddrMode.InBounds =
false;
4617 auto GetConstantStep =
4618 [
this](
const Value *
V) -> std::optional<std::pair<Instruction *, APInt>> {
4621 return std::nullopt;
4624 return std::nullopt;
4632 if (OIVInc->hasNoSignedWrap() || OIVInc->hasNoUnsignedWrap())
4633 return std::nullopt;
4635 return std::make_pair(IVInc->first, ConstantStep->getValue());
4636 return std::nullopt;
4651 if (
auto IVStep = GetConstantStep(ScaleReg)) {
4658 APInt Step = IVStep->second;
4660 if (
Offset.isSignedIntN(64)) {
4661 TestAddrMode.InBounds =
false;
4663 TestAddrMode.BaseOffs -=
Offset.getLimitedValue();
4668 getDTFn().
dominates(IVInc, MemoryInst)) {
4688 switch (
I->getOpcode()) {
4689 case Instruction::BitCast:
4690 case Instruction::AddrSpaceCast:
4692 if (
I->getType() ==
I->getOperand(0)->getType())
4694 return I->getType()->isIntOrPtrTy();
4695 case Instruction::PtrToInt:
4698 case Instruction::IntToPtr:
4701 case Instruction::Add:
4703 case Instruction::Mul:
4704 case Instruction::Shl:
4707 case Instruction::GetElementPtr:
4735class TypePromotionHelper {
4738 static void addPromotedInst(InstrToOrigTy &PromotedInsts,
4739 Instruction *ExtOpnd,
bool IsSExt) {
4740 ExtType ExtTy = IsSExt ? SignExtension : ZeroExtension;
4741 auto [It,
Inserted] = PromotedInsts.try_emplace(ExtOpnd);
4745 if (It->second.getInt() == ExtTy)
4751 ExtTy = BothExtension;
4753 It->second = TypeIsSExt(ExtOpnd->
getType(), ExtTy);
4760 static const Type *getOrigType(
const InstrToOrigTy &PromotedInsts,
4761 Instruction *Opnd,
bool IsSExt) {
4762 ExtType ExtTy = IsSExt ? SignExtension : ZeroExtension;
4763 InstrToOrigTy::const_iterator It = PromotedInsts.find(Opnd);
4764 if (It != PromotedInsts.end() && It->second.getInt() == ExtTy)
4765 return It->second.getPointer();
4780 static bool canGetThrough(
const Instruction *Inst,
Type *ConsideredExtType,
4781 const InstrToOrigTy &PromotedInsts,
bool IsSExt);
4785 static bool shouldExtOperand(
const Instruction *Inst,
int OpIdx) {
4798 static Value *promoteOperandForTruncAndAnyExt(
4799 Instruction *Ext, TypePromotionTransaction &TPT,
4800 InstrToOrigTy &PromotedInsts,
unsigned &CreatedInstsCost,
4801 SmallVectorImpl<Instruction *> *Exts,
4802 SmallVectorImpl<Instruction *> *Truncs,
const TargetLowering &TLI);
4813 static Value *promoteOperandForOther(Instruction *Ext,
4814 TypePromotionTransaction &TPT,
4815 InstrToOrigTy &PromotedInsts,
4816 unsigned &CreatedInstsCost,
4817 SmallVectorImpl<Instruction *> *Exts,
4818 SmallVectorImpl<Instruction *> *Truncs,
4819 const TargetLowering &TLI,
bool IsSExt);
4822 static Value *signExtendOperandForOther(
4823 Instruction *Ext, TypePromotionTransaction &TPT,
4824 InstrToOrigTy &PromotedInsts,
unsigned &CreatedInstsCost,
4825 SmallVectorImpl<Instruction *> *Exts,
4826 SmallVectorImpl<Instruction *> *Truncs,
const TargetLowering &TLI) {
4827 return promoteOperandForOther(Ext, TPT, PromotedInsts, CreatedInstsCost,
4828 Exts, Truncs, TLI,
true);
4832 static Value *zeroExtendOperandForOther(
4833 Instruction *Ext, TypePromotionTransaction &TPT,
4834 InstrToOrigTy &PromotedInsts,
unsigned &CreatedInstsCost,
4835 SmallVectorImpl<Instruction *> *Exts,
4836 SmallVectorImpl<Instruction *> *Truncs,
const TargetLowering &TLI) {
4837 return promoteOperandForOther(Ext, TPT, PromotedInsts, CreatedInstsCost,
4838 Exts, Truncs, TLI,
false);
4843 using Action =
Value *(*)(Instruction *Ext, TypePromotionTransaction &TPT,
4844 InstrToOrigTy &PromotedInsts,
4845 unsigned &CreatedInstsCost,
4846 SmallVectorImpl<Instruction *> *Exts,
4847 SmallVectorImpl<Instruction *> *Truncs,
4848 const TargetLowering &TLI);
4859 static Action getAction(Instruction *Ext,
const SetOfInstrs &InsertedInsts,
4860 const TargetLowering &TLI,
4861 const InstrToOrigTy &PromotedInsts);
4866bool TypePromotionHelper::canGetThrough(
const Instruction *Inst,
4867 Type *ConsideredExtType,
4868 const InstrToOrigTy &PromotedInsts,
4888 ((!IsSExt && BinOp->hasNoUnsignedWrap()) ||
4889 (IsSExt && BinOp->hasNoSignedWrap())))
4893 if ((Inst->
getOpcode() == Instruction::And ||
4898 if (Inst->
getOpcode() == Instruction::Xor) {
4901 if (!Cst->getValue().isAllOnes())
4910 if (Inst->
getOpcode() == Instruction::LShr && !IsSExt)
4920 if (ExtInst->hasOneUse()) {
4922 if (AndInst && AndInst->getOpcode() == Instruction::And) {
4955 const Type *OpndType = getOrigType(PromotedInsts, Opnd, IsSExt);
4968TypePromotionHelper::Action TypePromotionHelper::getAction(
4969 Instruction *Ext,
const SetOfInstrs &InsertedInsts,
4970 const TargetLowering &TLI,
const InstrToOrigTy &PromotedInsts) {
4972 "Unexpected instruction type");
4979 if (!ExtOpnd || !canGetThrough(ExtOpnd, ExtTy, PromotedInsts, IsSExt))
4992 return promoteOperandForTruncAndAnyExt;
4998 return IsSExt ? signExtendOperandForOther : zeroExtendOperandForOther;
5001Value *TypePromotionHelper::promoteOperandForTruncAndAnyExt(
5002 Instruction *SExt, TypePromotionTransaction &TPT,
5003 InstrToOrigTy &PromotedInsts,
unsigned &CreatedInstsCost,
5004 SmallVectorImpl<Instruction *> *Exts,
5005 SmallVectorImpl<Instruction *> *Truncs,
const TargetLowering &TLI) {
5009 Value *ExtVal = SExt;
5010 bool HasMergedNonFreeExt =
false;
5014 HasMergedNonFreeExt = !TLI.
isExtFree(SExtOpnd);
5017 TPT.replaceAllUsesWith(SExt, ZExt);
5018 TPT.eraseInstruction(SExt);
5023 TPT.setOperand(SExt, 0, SExtOpnd->
getOperand(0));
5025 CreatedInstsCost = 0;
5029 TPT.eraseInstruction(SExtOpnd);
5037 CreatedInstsCost = !TLI.
isExtFree(ExtInst) && !HasMergedNonFreeExt;
5045 TPT.eraseInstruction(ExtInst, NextVal);
5049Value *TypePromotionHelper::promoteOperandForOther(
5050 Instruction *Ext, TypePromotionTransaction &TPT,
5051 InstrToOrigTy &PromotedInsts,
unsigned &CreatedInstsCost,
5052 SmallVectorImpl<Instruction *> *Exts,
5053 SmallVectorImpl<Instruction *> *Truncs,
const TargetLowering &TLI,
5058 CreatedInstsCost = 0;
5064 Value *Trunc = TPT.createTrunc(Ext, ExtOpnd->
getType());
5067 ITrunc->moveAfter(ExtOpnd);
5072 TPT.replaceAllUsesWith(ExtOpnd, Trunc);
5075 TPT.setOperand(Ext, 0, ExtOpnd);
5085 addPromotedInst(PromotedInsts, ExtOpnd, IsSExt);
5087 TPT.mutateType(ExtOpnd, Ext->
getType());
5089 TPT.replaceAllUsesWith(Ext, ExtOpnd);
5096 !shouldExtOperand(ExtOpnd,
OpIdx)) {
5105 APInt CstVal = IsSExt ? Cst->getValue().sext(
BitWidth)
5107 TPT.setOperand(ExtOpnd,
OpIdx, ConstantInt::get(Ext->
getType(), CstVal));
5118 Value *ValForExtOpnd = IsSExt
5119 ? TPT.createSExt(ExtOpnd, Opnd, Ext->
getType())
5120 : TPT.createZExt(ExtOpnd, Opnd, Ext->
getType());
5121 TPT.setOperand(ExtOpnd,
OpIdx, ValForExtOpnd);
5123 if (!InstForExtOpnd)
5129 CreatedInstsCost += !TLI.
isExtFree(InstForExtOpnd);
5132 TPT.eraseInstruction(Ext);
5144bool AddressingModeMatcher::isPromotionProfitable(
5145 unsigned NewCost,
unsigned OldCost,
Value *PromotedOperand)
const {
5146 LLVM_DEBUG(
dbgs() <<
"OldCost: " << OldCost <<
"\tNewCost: " << NewCost
5151 if (NewCost > OldCost)
5153 if (NewCost < OldCost)
5172bool AddressingModeMatcher::matchOperationAddr(User *AddrInst,
unsigned Opcode,
5184 case Instruction::PtrToInt:
5187 case Instruction::IntToPtr: {
5195 case Instruction::BitCast:
5205 case Instruction::AddrSpaceCast: {
5213 case Instruction::Add: {
5216 ExtAddrMode BackupAddrMode =
AddrMode;
5217 unsigned OldSize = AddrModeInsts.
size();
5222 TypePromotionTransaction::ConstRestorationPt LastKnownGood =
5223 TPT.getRestorationPoint();
5227 int First = 0, Second = 1;
5238 AddrModeInsts.
resize(OldSize);
5239 TPT.rollback(LastKnownGood);
5249 AddrModeInsts.
resize(OldSize);
5250 TPT.rollback(LastKnownGood);
5256 case Instruction::Mul:
5257 case Instruction::Shl: {
5261 if (!
RHS ||
RHS->getBitWidth() > 64)
5263 int64_t Scale = Opcode == Instruction::Shl
5264 ? 1LL <<
RHS->getLimitedValue(
RHS->getBitWidth() - 1)
5265 :
RHS->getSExtValue();
5269 case Instruction::GetElementPtr: {
5272 int VariableOperand = -1;
5273 unsigned VariableScale = 0;
5275 int64_t ConstantOffset = 0;
5277 for (
unsigned i = 1, e = AddrInst->
getNumOperands(); i != e; ++i, ++GTI) {
5279 const StructLayout *SL =
DL.getStructLayout(STy);
5290 if (ConstantInt *CI =
5292 const APInt &CVal = CI->
getValue();
5299 if (VariableOperand != -1)
5303 VariableOperand = i;
5304 VariableScale = TypeSize;
5311 if (VariableOperand == -1) {
5312 AddrMode.BaseOffs += ConstantOffset;
5318 AddrMode.BaseOffs -= ConstantOffset;
5322 ConstantOffset > 0) {
5335 BasicBlock *Parent = BaseI ? BaseI->getParent()
5336 : &
GEP->getFunction()->getEntryBlock();
5338 LargeOffsetGEP = std::make_pair(
GEP, ConstantOffset);
5346 ExtAddrMode BackupAddrMode =
AddrMode;
5347 unsigned OldSize = AddrModeInsts.
size();
5350 AddrMode.BaseOffs += ConstantOffset;
5359 AddrModeInsts.
resize(OldSize);
5367 if (!matchScaledValue(AddrInst->
getOperand(VariableOperand), VariableScale,
5372 AddrModeInsts.
resize(OldSize);
5377 AddrMode.BaseOffs += ConstantOffset;
5378 if (!matchScaledValue(AddrInst->
getOperand(VariableOperand),
5379 VariableScale,
Depth)) {
5382 AddrModeInsts.
resize(OldSize);
5389 case Instruction::SExt:
5390 case Instruction::ZExt: {
5397 TypePromotionHelper::Action TPH =
5398 TypePromotionHelper::getAction(Ext, InsertedInsts, TLI, PromotedInsts);
5402 TypePromotionTransaction::ConstRestorationPt LastKnownGood =
5403 TPT.getRestorationPoint();
5404 unsigned CreatedInstsCost = 0;
5406 Value *PromotedOperand =
5407 TPH(Ext, TPT, PromotedInsts, CreatedInstsCost,
nullptr,
nullptr, TLI);
5422 assert(PromotedOperand &&
5423 "TypePromotionHelper should have filtered out those cases");
5425 ExtAddrMode BackupAddrMode =
AddrMode;
5426 unsigned OldSize = AddrModeInsts.
size();
5428 if (!matchAddr(PromotedOperand,
Depth) ||
5433 !isPromotionProfitable(CreatedInstsCost,
5434 ExtCost + (AddrModeInsts.
size() - OldSize),
5437 AddrModeInsts.
resize(OldSize);
5438 LLVM_DEBUG(
dbgs() <<
"Sign extension does not pay off: rollback\n");
5439 TPT.rollback(LastKnownGood);
5444 AddrMode.replaceWith(Ext, PromotedOperand);
5447 case Instruction::Call:
5449 if (
II->getIntrinsicID() == Intrinsic::threadlocal_address) {
5465bool AddressingModeMatcher::matchAddr(
Value *Addr,
unsigned Depth) {
5468 TypePromotionTransaction::ConstRestorationPt LastKnownGood =
5469 TPT.getRestorationPoint();
5493 ExtAddrMode BackupAddrMode =
AddrMode;
5494 unsigned OldSize = AddrModeInsts.
size();
5497 bool MovedAway =
false;
5498 if (matchOperationAddr(
I,
I->getOpcode(),
Depth, &MovedAway)) {
5506 if (
I->hasOneUse() ||
5507 isProfitableToFoldIntoAddressingMode(
I, BackupAddrMode,
AddrMode)) {
5514 AddrModeInsts.
resize(OldSize);
5515 TPT.rollback(LastKnownGood);
5518 if (matchOperationAddr(CE,
CE->getOpcode(),
Depth))
5520 TPT.rollback(LastKnownGood);
5547 TPT.rollback(LastKnownGood);
5566 if (OpInfo.CallOperandVal == OpVal &&
5568 !OpInfo.isIndirect))
5584 if (!ConsideredInsts.
insert(
I).second)
5592 for (
Use &U :
I->uses()) {
5600 MemoryUses.push_back({&U, LI->getType()});
5607 MemoryUses.push_back({&U,
SI->getValueOperand()->getType()});
5614 MemoryUses.push_back({&U, RMW->getValOperand()->getType()});
5621 MemoryUses.push_back({&U, CmpX->getCompareOperand()->getType()});
5631 if (!
find(PtrOps, U.get()))
5634 MemoryUses.push_back({&U, AccessTy});
5639 if (CI->hasFnAttr(Attribute::Cold)) {
5657 PSI, BFI, SeenInsts))
5668 unsigned SeenInsts = 0;
5671 PSI, BFI, SeenInsts);
5679bool AddressingModeMatcher::valueAlreadyLiveAtInst(
Value *Val,
5681 Value *KnownLive2) {
5683 if (Val ==
nullptr || Val == KnownLive1 || Val == KnownLive2)
5724bool AddressingModeMatcher::isProfitableToFoldIntoAddressingMode(
5725 Instruction *
I, ExtAddrMode &AMBefore, ExtAddrMode &AMAfter) {
5726 if (IgnoreProfitability)
5744 if (valueAlreadyLiveAtInst(ScaledReg, AMBefore.
BaseReg, AMBefore.
ScaledReg))
5745 ScaledReg =
nullptr;
5749 if (!BaseReg && !ScaledReg)
5770 for (
const std::pair<Use *, Type *> &Pair : MemoryUses) {
5773 Type *AddressAccessTy = Pair.second;
5774 unsigned AS =
Address->getType()->getPointerAddressSpace();
5780 std::pair<AssertingVH<GetElementPtrInst>, int64_t> LargeOffsetGEP(
nullptr,
5782 TypePromotionTransaction::ConstRestorationPt LastKnownGood =
5783 TPT.getRestorationPoint();
5784 AddressingModeMatcher Matcher(MatchedAddrModeInsts, TLI,
TRI, LI, getDTFn,
5785 AddressAccessTy, AS, UserI, Result,
5786 InsertedInsts, PromotedInsts, TPT,
5787 LargeOffsetGEP, OptSize, PSI, BFI);
5788 Matcher.IgnoreProfitability =
true;
5796 TPT.rollback(LastKnownGood);
5802 MatchedAddrModeInsts.
clear();
5812 return I->getParent() != BB;
5828 return std::next(AddrInst->getIterator());
5839 Earliest = UserInst;
5864bool CodeGenPrepare::optimizeMemoryInst(Instruction *MemoryInst,
Value *Addr,
5865 Type *AccessTy,
unsigned AddrSpace) {
5870 SmallVector<Value *, 8> worklist;
5871 SmallPtrSet<Value *, 16> Visited;
5877 bool PhiOrSelectSeen =
false;
5878 SmallVector<Instruction *, 16> AddrModeInsts;
5879 AddressingModeCombiner AddrModes(*
DL, Addr);
5880 TypePromotionTransaction TPT(RemovedInsts);
5881 TypePromotionTransaction::ConstRestorationPt LastKnownGood =
5882 TPT.getRestorationPoint();
5883 while (!worklist.
empty()) {
5895 if (!Visited.
insert(V).second)
5901 PhiOrSelectSeen =
true;
5908 PhiOrSelectSeen =
true;
5915 AddrModeInsts.
clear();
5916 std::pair<AssertingVH<GetElementPtrInst>, int64_t> LargeOffsetGEP(
nullptr,
5921 auto getDTFn = [
this]() ->
const DominatorTree & {
return getDT(); };
5922 ExtAddrMode NewAddrMode = AddressingModeMatcher::Match(
5923 V, AccessTy, AddrSpace, MemoryInst, AddrModeInsts, *TLI, *LI, getDTFn,
5924 *
TRI, InsertedInsts, PromotedInsts, TPT, LargeOffsetGEP, OptSize, PSI,
5927 GetElementPtrInst *
GEP = LargeOffsetGEP.first;
5932 LargeOffsetGEPMap[
GEP->getPointerOperand()].push_back(LargeOffsetGEP);
5933 LargeOffsetGEPID.
insert(std::make_pair(
GEP, LargeOffsetGEPID.
size()));
5936 NewAddrMode.OriginalValue =
V;
5937 if (!AddrModes.addNewAddrMode(NewAddrMode))
5944 if (!AddrModes.combineAddrModes()) {
5945 TPT.rollback(LastKnownGood);
5951 ExtAddrMode
AddrMode = AddrModes.getAddrMode();
5957 if (!PhiOrSelectSeen &&
none_of(AddrModeInsts, [&](
Value *V) {
5971 WeakTrackingVH SunkAddrVH = SunkAddrs[Addr];
5993 <<
" for " << *MemoryInst <<
"\n");
5997 !
DL->isNonIntegralPointerType(Addr->
getType())) {
6003 SunkAddr = Builder.CreatePtrToInt(SunkAddr, IntPtrTy,
"sunkaddr");
6005 Builder.CreateIntToPtr(SunkAddr, Addr->
getType(),
"sunkaddr");
6007 SunkAddr = Builder.CreatePointerCast(SunkAddr, Addr->
getType());
6014 <<
" for " << *MemoryInst <<
"\n");
6015 Value *ResultPtr =
nullptr, *ResultIndex =
nullptr;
6026 if (ResultPtr ||
AddrMode.Scale != 1)
6047 GlobalValue *BaseGV =
AddrMode.BaseGV;
6048 if (BaseGV !=
nullptr) {
6053 ResultPtr = Builder.CreateThreadLocalAddress(BaseGV);
6062 if (!
DL->isNonIntegralPointerType(Addr->
getType())) {
6063 if (!ResultPtr &&
AddrMode.BaseReg) {
6067 }
else if (!ResultPtr &&
AddrMode.Scale == 1) {
6068 ResultPtr = Builder.CreateIntToPtr(
AddrMode.ScaledReg, Addr->
getType(),
6077 }
else if (!ResultPtr) {
6090 if (
V->getType() != IntPtrTy)
6091 V = Builder.CreateIntCast(V, IntPtrTy,
true,
"sunkaddr");
6099 if (
V->getType() == IntPtrTy) {
6104 "We can't transform if ScaledReg is too narrow");
6105 V = Builder.CreateTrunc(V, IntPtrTy,
"sunkaddr");
6109 V = Builder.CreateMul(
6112 ResultIndex = Builder.CreateAdd(ResultIndex, V,
"sunkaddr");
6123 if (ResultPtr->
getType() != I8PtrTy)
6124 ResultPtr = Builder.CreatePointerCast(ResultPtr, I8PtrTy);
6125 ResultPtr = Builder.CreatePtrAdd(ResultPtr, ResultIndex,
"sunkaddr",
6138 if (PtrInst && PtrInst->getParent() != MemoryInst->
getParent())
6140 SunkAddr = ResultPtr;
6142 if (ResultPtr->
getType() != I8PtrTy)
6143 ResultPtr = Builder.CreatePointerCast(ResultPtr, I8PtrTy);
6144 SunkAddr = Builder.CreatePtrAdd(ResultPtr, ResultIndex,
"sunkaddr",
6151 !
DL->isNonIntegralPointerType(Addr->
getType())) {
6157 SunkAddr = Builder.CreatePtrToInt(SunkAddr, IntPtrTy,
"sunkaddr");
6159 Builder.CreateIntToPtr(SunkAddr, Addr->
getType(),
"sunkaddr");
6161 SunkAddr = Builder.CreatePointerCast(SunkAddr, Addr->
getType());
6171 if (
DL->isNonIntegralPointerType(Addr->
getType()) ||
6172 (BasePtrTy &&
DL->isNonIntegralPointerType(BasePtrTy)) ||
6173 (ScalePtrTy &&
DL->isNonIntegralPointerType(ScalePtrTy)) ||
6175 DL->isNonIntegralPointerType(
AddrMode.BaseGV->getType())))
6179 <<
" for " << *MemoryInst <<
"\n");
6190 if (
V->getType()->isPointerTy())
6191 V = Builder.CreatePtrToInt(V, IntPtrTy,
"sunkaddr");
6192 if (
V->getType() != IntPtrTy)
6193 V = Builder.CreateIntCast(V, IntPtrTy,
true,
"sunkaddr");
6200 if (
V->getType() == IntPtrTy) {
6202 }
else if (
V->getType()->isPointerTy()) {
6203 V = Builder.CreatePtrToInt(V, IntPtrTy,
"sunkaddr");
6206 V = Builder.CreateTrunc(V, IntPtrTy,
"sunkaddr");
6215 I->eraseFromParent();
6219 V = Builder.CreateMul(
6222 Result = Builder.CreateAdd(Result, V,
"sunkaddr");
6228 GlobalValue *BaseGV =
AddrMode.BaseGV;
6229 if (BaseGV !=
nullptr) {
6232 BaseGVPtr = Builder.CreateThreadLocalAddress(BaseGV);
6236 Value *
V = Builder.CreatePtrToInt(BaseGVPtr, IntPtrTy,
"sunkaddr");
6238 Result = Builder.CreateAdd(Result, V,
"sunkaddr");
6247 Result = Builder.CreateAdd(Result, V,
"sunkaddr");
6255 SunkAddr = Builder.CreateIntToPtr(Result, Addr->
getType(),
"sunkaddr");
6261 SunkAddrs[Addr] = WeakTrackingVH(SunkAddr);
6266 resetIteratorIfInvalidatedWhileCalling(CurInstIterator->getParent(), [&]() {
6267 RecursivelyDeleteTriviallyDeadInstructions(
6268 Repl, TLInfo, nullptr,
6269 [&](Value *V) { removeAllAssertingVHReferences(V); });
6293bool CodeGenPrepare::optimizeGatherScatterInst(Instruction *MemoryInst,
6299 if (!
GEP->hasIndices())
6307 SmallVector<Value *, 2>
Ops(
GEP->operands());
6309 bool RewriteGEP =
false;
6318 unsigned FinalIndex =
Ops.size() - 1;
6323 for (
unsigned i = 1; i < FinalIndex; ++i) {
6328 C =
C->getSplatValue();
6330 if (!CI || !CI->
isZero())
6337 if (
Ops[FinalIndex]->
getType()->isVectorTy()) {
6341 if (!
C || !
C->isZero()) {
6342 Ops[FinalIndex] =
V;
6350 if (!RewriteGEP &&
Ops.size() == 2)
6357 Type *SourceTy =
GEP->getSourceElementType();
6358 Type *ScalarIndexTy =
DL->getIndexType(
Ops[0]->
getType()->getScalarType());
6362 if (!
Ops[FinalIndex]->
getType()->isVectorTy()) {
6363 NewAddr = Builder.CreateGEP(SourceTy,
Ops[0],
ArrayRef(
Ops).drop_front());
6364 auto *IndexTy = VectorType::get(ScalarIndexTy, NumElts);
6374 if (
Ops.size() != 2) {
6384 NewAddr = Builder.CreateGEP(SourceTy,
Base, Index);
6398 Type *ScalarIndexTy =
DL->getIndexType(
V->getType()->getScalarType());
6399 auto *IndexTy = VectorType::get(ScalarIndexTy, NumElts);
6402 Intrinsic::masked_gather) {
6406 Intrinsic::masked_scatter);
6421 Ptr, TLInfo,
nullptr,
6422 [&](
Value *V) { removeAllAssertingVHReferences(V); });
6433 if (
I->hasNUsesOrMore(3))
6436 for (
User *U :
I->users()) {
6438 if (!Extract || Extract->getNumIndices() != 1)
6441 unsigned Index = Extract->getIndices()[0];
6443 MulExtract = Extract;
6444 else if (Index == 1)
6445 OverflowExtract = Extract;
6472bool CodeGenPrepare::optimizeMulWithOverflow(Instruction *
I,
bool IsSigned,
6473 ModifyDT &ModifiedDT) {
6480 ExtractValueInst *MulExtract =
nullptr, *OverflowExtract =
nullptr;
6485 InsertedInsts.insert(
I);
6496 OverflowEntryBB->
takeName(
I->getParent());
6502 NoOverflowBB->
moveAfter(OverflowEntryBB);
6510 Value *LoLHS = Builder.CreateTrunc(
LHS, LegalTy,
"lo.lhs");
6511 Value *HiLHS = Builder.CreateLShr(
LHS, VTHalfBitWidth,
"lhs.lsr");
6512 HiLHS = Builder.CreateTrunc(HiLHS, LegalTy,
"hi.lhs");
6515 Value *LoRHS = Builder.CreateTrunc(
RHS, LegalTy,
"lo.rhs");
6516 Value *HiRHS = Builder.CreateLShr(
RHS, VTHalfBitWidth,
"rhs.lsr");
6517 HiRHS = Builder.CreateTrunc(HiRHS, LegalTy,
"hi.rhs");
6519 Value *IsAnyBitTrue;
6522 Builder.CreateAShr(LoLHS, VTHalfBitWidth - 1,
"sign.lo.lhs");
6524 Builder.CreateAShr(LoRHS, VTHalfBitWidth - 1,
"sign.lo.rhs");
6525 Value *XorLHS = Builder.CreateXor(HiLHS, SignLoLHS);
6526 Value *XorRHS = Builder.CreateXor(HiRHS, SignLoRHS);
6527 Value *
Or = Builder.CreateOr(XorLHS, XorRHS,
"or.lhs.rhs");
6528 IsAnyBitTrue = Builder.CreateCmp(ICmpInst::ICMP_NE,
Or,
6529 ConstantInt::getNullValue(
Or->getType()));
6531 Value *CmpLHS = Builder.CreateCmp(ICmpInst::ICMP_NE, HiLHS,
6532 ConstantInt::getNullValue(LegalTy));
6533 Value *CmpRHS = Builder.CreateCmp(ICmpInst::ICMP_NE, HiRHS,
6534 ConstantInt::getNullValue(LegalTy));
6535 IsAnyBitTrue = Builder.CreateOr(CmpLHS, CmpRHS,
"or.lhs.rhs");
6537 Builder.CreateCondBr(IsAnyBitTrue, OverflowBB, NoOverflowBB);
6540 Builder.SetInsertPoint(NoOverflowBB);
6541 Value *ExtLoLHS, *ExtLoRHS;
6543 ExtLoLHS = Builder.CreateSExt(LoLHS, Ty,
"lo.lhs.ext");
6544 ExtLoRHS = Builder.CreateSExt(LoRHS, Ty,
"lo.rhs.ext");
6546 ExtLoLHS = Builder.CreateZExt(LoLHS, Ty,
"lo.lhs.ext");
6547 ExtLoRHS = Builder.CreateZExt(LoRHS, Ty,
"lo.rhs.ext");
6550 Value *
Mul = Builder.CreateMul(ExtLoLHS, ExtLoRHS,
"mul.overflow.no");
6555 OverflowResBB->
setName(
"overflow.res");
6558 Builder.CreateBr(OverflowResBB);
6566 PHINode *OverflowResPHI = Builder.CreatePHI(Ty, 2),
6568 Builder.CreatePHI(IntegerType::getInt1Ty(
I->getContext()), 2);
6580 if (OverflowExtract) {
6581 OverflowExtract->replaceAllUsesWith(OverflowFlagPHI);
6582 OverflowExtract->eraseFromParent();
6587 I->removeFromParent();
6589 I->insertInto(OverflowBB, OverflowBB->
end());
6590 Builder.SetInsertPoint(OverflowBB, OverflowBB->
end());
6592 Value *OverflowFlag = Builder.CreateExtractValue(
I, {1},
"overflow.flag");
6593 Builder.CreateBr(OverflowResBB);
6597 OverflowFlagPHI->addIncoming(OverflowFlag, OverflowBB);
6599 DTU->
applyUpdates({{DominatorTree::Insert, OverflowEntryBB, OverflowBB},
6600 {DominatorTree::Insert, OverflowEntryBB, NoOverflowBB},
6601 {DominatorTree::Insert, NoOverflowBB, OverflowResBB},
6602 {DominatorTree::Delete, OverflowEntryBB, OverflowResBB},
6603 {DominatorTree::Insert, OverflowBB, OverflowResBB}});
6605 ModifiedDT = ModifyDT::ModifyBBDT;
6611bool CodeGenPrepare::optimizeInlineAsmInst(CallInst *CS) {
6612 bool MadeChange =
false;
6614 const TargetRegisterInfo *
TRI =
6619 for (TargetLowering::AsmOperandInfo &OpInfo : TargetConstraints) {
6625 OpInfo.isIndirect) {
6627 MadeChange |= optimizeMemoryInst(CS, OpVal, OpVal->
getType(), ~0u);
6690bool CodeGenPrepare::tryToPromoteExts(
6691 TypePromotionTransaction &TPT,
const SmallVectorImpl<Instruction *> &Exts,
6692 SmallVectorImpl<Instruction *> &ProfitablyMovedExts,
6693 unsigned CreatedInstsCost) {
6694 bool Promoted =
false;
6697 for (
auto *
I : Exts) {
6712 TypePromotionHelper::Action TPH =
6713 TypePromotionHelper::getAction(
I, InsertedInsts, *TLI, PromotedInsts);
6722 TypePromotionTransaction::ConstRestorationPt LastKnownGood =
6723 TPT.getRestorationPoint();
6724 SmallVector<Instruction *, 4> NewExts;
6725 unsigned NewCreatedInstsCost = 0;
6728 Value *PromotedVal = TPH(
I, TPT, PromotedInsts, NewCreatedInstsCost,
6729 &NewExts,
nullptr, *TLI);
6731 "TypePromotionHelper should have filtered out those cases");
6741 long long TotalCreatedInstsCost = CreatedInstsCost + NewCreatedInstsCost;
6744 TotalCreatedInstsCost =
6745 std::max((
long long)0, (TotalCreatedInstsCost - ExtCost));
6747 (TotalCreatedInstsCost > 1 ||
6749 (ExtCost == 0 && NewExts.
size() > 1))) {
6753 TPT.rollback(LastKnownGood);
6758 SmallVector<Instruction *, 2> NewlyMovedExts;
6759 (void)tryToPromoteExts(TPT, NewExts, NewlyMovedExts, TotalCreatedInstsCost);
6760 bool NewPromoted =
false;
6761 for (
auto *ExtInst : NewlyMovedExts) {
6771 ProfitablyMovedExts.
push_back(MovedExt);
6778 TPT.rollback(LastKnownGood);
6789bool CodeGenPrepare::mergeSExts(Function &
F) {
6791 for (
auto &Entry : ValToSExtendedUses) {
6792 SExts &Insts =
Entry.second;
6794 for (Instruction *Inst : Insts) {
6798 bool inserted =
false;
6799 for (
auto &Pt : CurPts) {
6802 RemovedInsts.insert(Pt);
6803 Pt->removeFromParent();
6814 RemovedInsts.insert(Inst);
6821 CurPts.push_back(Inst);
6863bool CodeGenPrepare::splitLargeGEPOffsets() {
6865 for (
auto &Entry : LargeOffsetGEPMap) {
6867 SmallVectorImpl<std::pair<AssertingVH<GetElementPtrInst>, int64_t>>
6868 &LargeOffsetGEPs =
Entry.second;
6869 auto compareGEPOffset =
6870 [&](
const std::pair<GetElementPtrInst *, int64_t> &
LHS,
6871 const std::pair<GetElementPtrInst *, int64_t> &
RHS) {
6872 if (
LHS.first ==
RHS.first)
6874 if (
LHS.second !=
RHS.second)
6875 return LHS.second <
RHS.second;
6876 return LargeOffsetGEPID[
LHS.first] < LargeOffsetGEPID[
RHS.first];
6879 llvm::sort(LargeOffsetGEPs, compareGEPOffset);
6882 if (LargeOffsetGEPs.
front().second == LargeOffsetGEPs.
back().second)
6884 GetElementPtrInst *BaseGEP = LargeOffsetGEPs.
begin()->first;
6885 int64_t BaseOffset = LargeOffsetGEPs.
begin()->second;
6886 Value *NewBaseGEP =
nullptr;
6888 auto createNewBase = [&](int64_t BaseOffset,
Value *OldBase,
6889 GetElementPtrInst *
GEP) {
6890 LLVMContext &Ctx =
GEP->getContext();
6891 Type *PtrIdxTy =
DL->getIndexType(
GEP->getType());
6893 PointerType::get(Ctx,
GEP->getType()->getPointerAddressSpace());
6905 SplitEdge(NewBaseInsertBB, Invoke->getNormalDest(), &getDT(), LI);
6908 NewBaseInsertPt = std::next(BaseI->getIterator());
6915 IRBuilder<> NewBaseBuilder(NewBaseInsertBB, NewBaseInsertPt);
6921 NewBaseGEP = OldBase;
6922 if (NewBaseGEP->
getType() != I8PtrTy)
6923 NewBaseGEP = NewBaseBuilder.CreatePointerCast(NewBaseGEP, I8PtrTy);
6925 NewBaseBuilder.CreatePtrAdd(NewBaseGEP, BaseIndex,
"splitgep");
6926 NewGEPBases.
insert(NewBaseGEP);
6932 LargeOffsetGEPs.
front().second, LargeOffsetGEPs.
back().second)) {
6933 BaseOffset = PreferBase;
6936 createNewBase(BaseOffset, OldBase, BaseGEP);
6939 auto *LargeOffsetGEP = LargeOffsetGEPs.
begin();
6940 while (LargeOffsetGEP != LargeOffsetGEPs.
end()) {
6941 GetElementPtrInst *
GEP = LargeOffsetGEP->first;
6942 int64_t
Offset = LargeOffsetGEP->second;
6943 if (
Offset != BaseOffset) {
6950 GEP->getResultElementType(),
6951 GEP->getAddressSpace())) {
6957 NewBaseGEP =
nullptr;
6962 Type *PtrIdxTy =
DL->getIndexType(
GEP->getType());
6967 createNewBase(BaseOffset, OldBase,
GEP);
6971 Value *NewGEP = NewBaseGEP;
6972 if (
Offset != BaseOffset) {
6975 NewGEP = Builder.CreatePtrAdd(NewBaseGEP, Index);
6979 LargeOffsetGEP = LargeOffsetGEPs.
erase(LargeOffsetGEP);
6980 GEP->eraseFromParent();
6987bool CodeGenPrepare::optimizePhiType(
6988 PHINode *
I, SmallPtrSetImpl<PHINode *> &Visited,
6989 SmallPtrSetImpl<Instruction *> &DeletedInstrs) {
6994 Type *PhiTy =
I->getType();
6995 Type *ConvertTy =
nullptr;
6997 (!
I->getType()->isIntegerTy() && !
I->getType()->isFloatingPointTy()))
7000 SmallVector<Instruction *, 4> Worklist;
7002 SmallPtrSet<PHINode *, 4> PhiNodes;
7003 SmallPtrSet<ConstantData *, 4>
Constants;
7006 SmallPtrSet<Instruction *, 4> Defs;
7007 SmallPtrSet<Instruction *, 4>
Uses;
7013 bool AnyAnchored =
false;
7015 while (!Worklist.
empty()) {
7020 for (
Value *V :
Phi->incoming_values()) {
7022 if (!PhiNodes.
count(OpPhi)) {
7023 if (!Visited.
insert(OpPhi).second)
7029 if (!OpLoad->isSimple())
7031 if (Defs.
insert(OpLoad).second)
7034 if (Defs.
insert(OpEx).second)
7038 ConvertTy = OpBC->getOperand(0)->getType();
7039 if (OpBC->getOperand(0)->getType() != ConvertTy)
7041 if (Defs.
insert(OpBC).second) {
7054 for (User *V :
II->users()) {
7056 if (!PhiNodes.
count(OpPhi)) {
7057 if (Visited.
count(OpPhi))
7064 if (!OpStore->isSimple() || OpStore->getOperand(0) !=
II)
7066 Uses.insert(OpStore);
7069 ConvertTy = OpBC->getType();
7070 if (OpBC->getType() != ConvertTy)
7074 any_of(OpBC->users(), [](User *U) { return !isa<StoreInst>(U); });
7081 if (!ConvertTy || !AnyAnchored || PhiTy == ConvertTy ||
7085 LLVM_DEBUG(
dbgs() <<
"Converting " << *
I <<
"\n and connected nodes to "
7086 << *ConvertTy <<
"\n");
7091 for (ConstantData *
C : Constants)
7093 for (Instruction *
D : Defs) {
7095 ValMap[
D] =
D->getOperand(0);
7099 ValMap[
D] =
new BitCastInst(
D, ConvertTy,
D->getName() +
".bc", insertPt);
7102 for (PHINode *Phi : PhiNodes)
7104 Phi->getName() +
".tc",
Phi->getIterator());
7106 for (PHINode *Phi : PhiNodes) {
7108 for (
int i = 0, e =
Phi->getNumIncomingValues(); i < e; i++)
7110 Phi->getIncomingBlock(i));
7114 for (Instruction *U :
Uses) {
7119 U->setOperand(0,
new BitCastInst(ValMap[
U->getOperand(0)], PhiTy,
"bc",
7129bool CodeGenPrepare::optimizePhiTypes(Function &
F) {
7134 SmallPtrSet<PHINode *, 4> Visited;
7135 SmallPtrSet<Instruction *, 4> DeletedInstrs;
7139 for (
auto &Phi : BB.
phis())
7140 Changed |= optimizePhiType(&Phi, Visited, DeletedInstrs);
7143 for (
auto *
I : DeletedInstrs) {
7145 I->eraseFromParent();
7153bool CodeGenPrepare::canFormExtLd(
7154 const SmallVectorImpl<Instruction *> &MovedExts, LoadInst *&LI,
7155 Instruction *&Inst,
bool HasPromoted) {
7156 for (
auto *MovedExtInst : MovedExts) {
7159 Inst = MovedExtInst;
7211bool CodeGenPrepare::optimizeExt(Instruction *&Inst) {
7212 bool AllowPromotionWithoutCommonHeader =
false;
7217 *Inst, AllowPromotionWithoutCommonHeader);
7218 TypePromotionTransaction TPT(RemovedInsts);
7219 TypePromotionTransaction::ConstRestorationPt LastKnownGood =
7220 TPT.getRestorationPoint();
7222 SmallVector<Instruction *, 2> SpeculativelyMovedExts;
7225 bool HasPromoted = tryToPromoteExts(TPT, Exts, SpeculativelyMovedExts);
7228 LoadInst *LI =
nullptr;
7233 if (canFormExtLd(SpeculativelyMovedExts, LI, ExtFedByLoad, HasPromoted)) {
7234 assert(LI && ExtFedByLoad &&
"Expect a valid load and extension");
7239 Inst = ExtFedByLoad;
7244 if (ATPConsiderable &&
7245 performAddressTypePromotion(Inst, AllowPromotionWithoutCommonHeader,
7246 HasPromoted, TPT, SpeculativelyMovedExts))
7249 TPT.rollback(LastKnownGood);
7258bool CodeGenPrepare::performAddressTypePromotion(
7259 Instruction *&Inst,
bool AllowPromotionWithoutCommonHeader,
7260 bool HasPromoted, TypePromotionTransaction &TPT,
7261 SmallVectorImpl<Instruction *> &SpeculativelyMovedExts) {
7262 bool Promoted =
false;
7263 SmallPtrSet<Instruction *, 1> UnhandledExts;
7264 bool AllSeenFirst =
true;
7265 for (
auto *
I : SpeculativelyMovedExts) {
7266 Value *HeadOfChain =
I->getOperand(0);
7267 DenseMap<Value *, Instruction *>::iterator AlreadySeen =
7268 SeenChainsForSExt.
find(HeadOfChain);
7271 if (AlreadySeen != SeenChainsForSExt.
end()) {
7272 if (AlreadySeen->second !=
nullptr)
7273 UnhandledExts.
insert(AlreadySeen->second);
7274 AllSeenFirst =
false;
7278 if (!AllSeenFirst || (AllowPromotionWithoutCommonHeader &&
7279 SpeculativelyMovedExts.size() == 1)) {
7283 for (
auto *
I : SpeculativelyMovedExts) {
7284 Value *HeadOfChain =
I->getOperand(0);
7285 SeenChainsForSExt[HeadOfChain] =
nullptr;
7286 ValToSExtendedUses[HeadOfChain].push_back(
I);
7289 Inst = SpeculativelyMovedExts.pop_back_val();
7294 for (
auto *
I : SpeculativelyMovedExts) {
7295 Value *HeadOfChain =
I->getOperand(0);
7296 SeenChainsForSExt[HeadOfChain] = Inst;
7301 if (!AllSeenFirst && !UnhandledExts.
empty())
7302 for (
auto *VisitedSExt : UnhandledExts) {
7303 if (RemovedInsts.count(VisitedSExt))
7305 TypePromotionTransaction TPT(RemovedInsts);
7307 SmallVector<Instruction *, 2> Chains;
7309 bool HasPromoted = tryToPromoteExts(TPT, Exts, Chains);
7313 for (
auto *
I : Chains) {
7314 Value *HeadOfChain =
I->getOperand(0);
7316 SeenChainsForSExt[HeadOfChain] =
nullptr;
7317 ValToSExtendedUses[HeadOfChain].push_back(
I);
7323bool CodeGenPrepare::optimizeExtUses(Instruction *
I) {
7328 Value *Src =
I->getOperand(0);
7329 if (Src->hasOneUse())
7341 bool DefIsLiveOut =
false;
7342 for (User *U :
I->users()) {
7347 if (UserBB == DefBB)
7349 DefIsLiveOut =
true;
7356 for (User *U : Src->users()) {
7359 if (UserBB == DefBB)
7368 DenseMap<BasicBlock *, Instruction *> InsertedTruncs;
7370 bool MadeChange =
false;
7371 for (Use &U : Src->uses()) {
7376 if (UserBB == DefBB)
7380 Instruction *&InsertedTrunc = InsertedTruncs[UserBB];
7382 if (!InsertedTrunc) {
7385 InsertedTrunc =
new TruncInst(
I, Src->getType(),
"");
7387 InsertedInsts.insert(InsertedTrunc);
7450bool CodeGenPrepare::optimizeLoadExt(LoadInst *Load) {
7451 if (!
Load->isSimple() || !
Load->getType()->isIntOrPtrTy())
7455 if (
Load->hasOneUse() &&
7461 SmallVector<Instruction *, 8> WorkList;
7462 SmallPtrSet<Instruction *, 16> Visited;
7463 SmallVector<Instruction *, 8> AndsToMaybeRemove;
7464 SmallVector<Instruction *, 8> DropFlags;
7465 for (
auto *U :
Load->users())
7477 while (!WorkList.
empty()) {
7481 if (!Visited.
insert(
I).second)
7486 for (
auto *U :
Phi->users())
7491 switch (
I->getOpcode()) {
7492 case Instruction::And: {
7496 APInt AndBits = AndC->getValue();
7497 DemandBits |= AndBits;
7499 if (AndBits.
ugt(WidestAndBits))
7500 WidestAndBits = AndBits;
7501 if (AndBits == WidestAndBits &&
I->getOperand(0) == Load)
7506 case Instruction::Shl: {
7510 uint64_t ShiftAmt = ShlC->getLimitedValue(
BitWidth - 1);
7511 DemandBits.setLowBits(
BitWidth - ShiftAmt);
7516 case Instruction::Trunc: {
7519 DemandBits.setLowBits(TruncBitWidth);
7529 uint32_t ActiveBits = DemandBits.getActiveBits();
7541 if (ActiveBits <= 1 || !DemandBits.isMask(ActiveBits) ||
7542 WidestAndBits != DemandBits)
7545 LLVMContext &Ctx =
Load->getType()->getContext();
7546 Type *TruncTy = Type::getIntNTy(Ctx, ActiveBits);
7557 Builder.CreateAnd(Load, ConstantInt::get(Ctx, DemandBits)));
7560 InsertedInsts.insert(NewAnd);
7565 NewAnd->setOperand(0, Load);
7568 for (
auto *
And : AndsToMaybeRemove)
7573 if (&*CurInstIterator ==
And)
7574 CurInstIterator = std::next(
And->getIterator());
7575 And->eraseFromParent();
7580 for (
auto *Inst : DropFlags)
7594 TTI->isExpensiveToSpeculativelyExecute(
I);
7612 uint64_t Max = std::max(TrueWeight, FalseWeight);
7613 uint64_t Sum = TrueWeight + FalseWeight;
7616 if (Probability >
TTI->getPredictableBranchThreshold())
7626 if (!Cmp || !Cmp->hasOneUse())
7649 assert(DefSI->getCondition() ==
SI->getCondition() &&
7650 "The condition of DefSI does not match with SI");
7651 V = (isTrue ? DefSI->getTrueValue() : DefSI->getFalseValue());
7654 assert(V &&
"Failed to get select true/false value");
7658bool CodeGenPrepare::optimizeShiftInst(BinaryOperator *Shift) {
7682 BinaryOperator::BinaryOps Opcode = Shift->
getOpcode();
7683 Value *NewTVal = Builder.CreateBinOp(Opcode, Shift->
getOperand(0), TVal);
7684 Value *NewFVal = Builder.CreateBinOp(Opcode, Shift->
getOperand(0), FVal);
7685 Value *NewSel = Builder.CreateSelect(
Cond, NewTVal, NewFVal);
7691bool CodeGenPrepare::optimizeFunnelShift(IntrinsicInst *Fsh) {
7693 assert((Opcode == Intrinsic::fshl || Opcode == Intrinsic::fshr) &&
7694 "Expected a funnel shift");
7718 Value *NewTVal = Builder.CreateIntrinsic(Opcode, Ty, {
X,
Y, TVal});
7719 Value *NewFVal = Builder.CreateIntrinsic(Opcode, Ty, {
X,
Y, FVal});
7720 Value *NewSel = Builder.CreateSelect(
Cond, NewTVal, NewFVal);
7728bool CodeGenPrepare::optimizeSelectInst(SelectInst *SI) {
7740 It !=
SI->getParent()->
end(); ++It) {
7742 if (
I &&
SI->getCondition() ==
I->getCondition()) {
7749 SelectInst *LastSI = ASI.
back();
7752 CurInstIterator = std::next(LastSI->
getIterator());
7756 for (SelectInst *SI :
ArrayRef(ASI).drop_front())
7757 fixupDbgVariableRecordsOnInst(*SI);
7759 bool VectorCond = !
SI->getCondition()->getType()->isIntegerTy(1);
7762 if (VectorCond ||
SI->getMetadata(LLVMContext::MD_unpredictable))
7765 TargetLowering::SelectSupportKind SelectKind;
7766 if (
SI->getType()->isVectorTy())
7767 SelectKind = TargetLowering::ScalarCondVectorVal;
7769 SelectKind = TargetLowering::ScalarValSelect;
7807 for (SelectInst *SI : ASI) {
7819 SplitPt.setHeadBit(
true);
7822 auto *CondFr =
IB.CreateFreeze(
SI->getCondition(),
SI->getName() +
".frozen");
7827 UncondBrInst *TrueBranch =
nullptr;
7828 UncondBrInst *FalseBranch =
nullptr;
7829 if (TrueInstrs.
size() == 0) {
7832 FalseBlock = FalseBranch->getParent();
7834 }
else if (FalseInstrs.
size() == 0) {
7837 TrueBlock = TrueBranch->getParent();
7846 TrueBlock = TrueBranch->getParent();
7847 FalseBlock = FalseBranch->getParent();
7851 EndBlock->
setName(
"select.end");
7853 TrueBlock->
setName(
"select.true.sink");
7855 FalseBlock->
setName(FalseInstrs.
size() == 0 ?
"select.false"
7856 :
"select.false.sink");
7860 FreshBBs.
insert(TrueBlock);
7862 FreshBBs.
insert(FalseBlock);
7863 FreshBBs.
insert(EndBlock);
7868 static const unsigned MD[] = {
7869 LLVMContext::MD_prof, LLVMContext::MD_unpredictable,
7870 LLVMContext::MD_make_implicit, LLVMContext::MD_dbg};
7875 for (Instruction *
I : TrueInstrs)
7876 I->moveBefore(TrueBranch->getIterator());
7877 for (Instruction *
I : FalseInstrs)
7878 I->moveBefore(FalseBranch->getIterator());
7884 if (TrueBlock ==
nullptr)
7885 TrueBlock = StartBlock;
7886 else if (FalseBlock ==
nullptr)
7887 FalseBlock = StartBlock;
7903 SI->eraseFromParent();
7905 ++NumSelectsExpanded;
7909 CurInstIterator = StartBlock->
end();
7916bool CodeGenPrepare::optimizeShuffleVectorInst(ShuffleVectorInst *SVI) {
7928 "Expected a type of the same size!");
7934 Builder.SetInsertPoint(SVI);
7935 Value *BC1 = Builder.CreateBitCast(
7937 Value *Shuffle = Builder.CreateVectorSplat(NewVecType->getNumElements(), BC1);
7938 Value *BC2 = Builder.CreateBitCast(Shuffle, SVIVecType);
7942 SVI, TLInfo,
nullptr,
7943 [&](
Value *V) { removeAllAssertingVHReferences(V); });
7950 !
Op->isTerminator() && !
Op->isEHPad())
7956bool CodeGenPrepare::tryToSinkFreeOperands(Instruction *
I) {
7971 DenseMap<const Instruction *, unsigned long> InstOrdering;
7972 unsigned long InstNumber = 0;
7973 for (
const auto &
I : *TargetBB)
7974 InstOrdering[&
I] = InstNumber++;
7976 for (Use *U :
reverse(OpsToSink)) {
7981 if (InstOrdering[UI] < InstOrdering[InsertPoint])
7988 SetVector<Instruction *> MaybeDead;
7989 DenseMap<Instruction *, Instruction *> NewInstructions;
7990 for (Use *U : ToReplace) {
7999 FreshBBs.
insert(OpDef->getParent());
8002 NewInstructions[UI] = NI;
8007 InsertedInsts.insert(NI);
8013 if (
auto It = NewInstructions.
find(OldI); It != NewInstructions.
end())
8014 It->second->setOperand(
U->getOperandNo(), NI);
8021 for (
auto *
I : MaybeDead) {
8022 if (!
I->hasNUsesOrMore(1)) {
8024 I->eraseFromParent();
8031bool CodeGenPrepare::optimizeSwitchType(SwitchInst *SI) {
8037 unsigned RegWidth =
RegType.getSizeInBits();
8048 auto *NewType = Type::getIntNTy(
Context, RegWidth);
8057 ExtType = Instruction::SExt;
8060 if (Arg->hasSExtAttr())
8061 ExtType = Instruction::SExt;
8062 if (Arg->hasZExtAttr())
8063 ExtType = Instruction::ZExt;
8069 SI->setCondition(ExtInst);
8070 for (
auto Case :
SI->cases()) {
8071 const APInt &NarrowConst = Case.getCaseValue()->getValue();
8072 APInt WideConst = (ExtType == Instruction::ZExt)
8073 ? NarrowConst.
zext(RegWidth)
8074 : NarrowConst.
sext(RegWidth);
8075 Case.setValue(ConstantInt::get(
Context, WideConst));
8081bool CodeGenPrepare::optimizeSwitchPhiConstants(SwitchInst *SI) {
8088 Value *Condition =
SI->getCondition();
8097 for (
const SwitchInst::CaseHandle &Case :
SI->cases()) {
8098 ConstantInt *CaseValue = Case.getCaseValue();
8099 BasicBlock *CaseBB = Case.getCaseSuccessor();
8102 bool CheckedForSinglePred =
false;
8103 for (PHINode &
PHI : CaseBB->
phis()) {
8104 Type *PHIType =
PHI.getType();
8112 if (PHIType == ConditionType || TryZExt) {
8114 bool SkipCase =
false;
8115 Value *Replacement =
nullptr;
8116 for (
unsigned I = 0,
E =
PHI.getNumIncomingValues();
I !=
E;
I++) {
8117 Value *PHIValue =
PHI.getIncomingValue(
I);
8118 if (PHIValue != CaseValue) {
8127 if (
PHI.getIncomingBlock(
I) != SwitchBB)
8132 if (!CheckedForSinglePred) {
8133 CheckedForSinglePred =
true;
8134 if (
SI->findCaseDest(CaseBB) ==
nullptr) {
8140 if (Replacement ==
nullptr) {
8141 if (PHIValue == CaseValue) {
8142 Replacement = Condition;
8145 Replacement = Builder.CreateZExt(Condition, PHIType);
8148 PHI.setIncomingValue(
I, Replacement);
8159bool CodeGenPrepare::optimizeSwitchInst(SwitchInst *SI) {
8160 bool Changed = optimizeSwitchType(SI);
8161 Changed |= optimizeSwitchPhiConstants(SI);
8182class VectorPromoteHelper {
8184 const DataLayout &
DL;
8187 const TargetLowering &TLI;
8190 const TargetTransformInfo &
TTI;
8196 SmallVector<Instruction *, 4> InstsToBePromoted;
8199 unsigned StoreExtractCombineCost;
8208 if (InstsToBePromoted.
empty())
8210 return InstsToBePromoted.
back();
8216 unsigned getTransitionOriginalValueIdx()
const {
8218 "Other kind of transitions are not supported yet");
8225 unsigned getTransitionIdx()
const {
8227 "Other kind of transitions are not supported yet");
8235 Type *getTransitionType()
const {
8246 void promoteImpl(Instruction *ToBePromoted);
8250 bool isProfitableToPromote() {
8251 Value *ValIdx = Transition->
getOperand(getTransitionOriginalValueIdx());
8255 Type *PromotedType = getTransitionType();
8258 unsigned AS =
ST->getPointerAddressSpace();
8276 for (
const auto &Inst : InstsToBePromoted) {
8284 TargetTransformInfo::OperandValueInfo Arg0Info, Arg1Info;
8296 dbgs() <<
"Estimated cost of computation to be promoted:\nScalar: "
8297 << ScalarCost <<
"\nVector: " << VectorCost <<
'\n');
8298 return ScalarCost > VectorCost;
8310 unsigned ExtractIdx = std::numeric_limits<unsigned>::max();
8325 if (!
EC.isScalable()) {
8326 SmallVector<Constant *, 4> ConstVec;
8328 for (
unsigned Idx = 0; Idx !=
EC.getKnownMinValue(); ++Idx) {
8329 if (Idx == ExtractIdx)
8337 "Generate scalable vector for non-splat is unimplemented");
8342 static bool canCauseUndefinedBehavior(
const Instruction *Use,
8343 unsigned OperandIdx) {
8346 if (OperandIdx != 1)
8348 switch (
Use->getOpcode()) {
8351 case Instruction::SDiv:
8352 case Instruction::UDiv:
8353 case Instruction::SRem:
8354 case Instruction::URem:
8356 case Instruction::FDiv:
8357 case Instruction::FRem:
8358 return !
Use->hasNoNaNs();
8364 VectorPromoteHelper(
const DataLayout &
DL,
const TargetLowering &TLI,
8365 const TargetTransformInfo &
TTI, Instruction *Transition,
8366 unsigned CombineCost)
8367 :
DL(
DL), TLI(TLI),
TTI(
TTI), Transition(Transition),
8368 StoreExtractCombineCost(CombineCost) {
8369 assert(Transition &&
"Do not know how to promote null");
8373 bool canPromote(
const Instruction *ToBePromoted)
const {
8380 bool shouldPromote(
const Instruction *ToBePromoted)
const {
8383 for (
const Use &U : ToBePromoted->
operands()) {
8384 const Value *Val =
U.get();
8385 if (Val == getEndOfTransition()) {
8389 if (canCauseUndefinedBehavior(ToBePromoted,
U.getOperandNo()))
8412 void enqueueForPromotion(Instruction *ToBePromoted) {
8413 InstsToBePromoted.push_back(ToBePromoted);
8417 void recordCombineInstruction(Instruction *ToBeCombined) {
8419 CombineInst = ToBeCombined;
8429 if (InstsToBePromoted.empty() || !CombineInst)
8437 for (
auto &ToBePromoted : InstsToBePromoted)
8438 promoteImpl(ToBePromoted);
8439 InstsToBePromoted.clear();
8446void VectorPromoteHelper::promoteImpl(Instruction *ToBePromoted) {
8456 "The type of the result of the transition does not match "
8461 Type *TransitionTy = getTransitionType();
8466 for (Use &U : ToBePromoted->
operands()) {
8468 Value *NewVal =
nullptr;
8469 if (Val == Transition)
8470 NewVal = Transition->
getOperand(getTransitionOriginalValueIdx());
8477 canCauseUndefinedBehavior(ToBePromoted,
U.getOperandNo()));
8481 ToBePromoted->
setOperand(
U.getOperandNo(), NewVal);
8484 Transition->
setOperand(getTransitionOriginalValueIdx(), ToBePromoted);
8490bool CodeGenPrepare::optimizeExtractElementInst(Instruction *Inst) {
8491 unsigned CombineCost = std::numeric_limits<unsigned>::max();
8506 LLVM_DEBUG(
dbgs() <<
"Found an interesting transition: " << *Inst <<
'\n');
8507 VectorPromoteHelper VPH(*
DL, *TLI, *
TTI, Inst, CombineCost);
8514 if (ToBePromoted->
getParent() != Parent) {
8515 LLVM_DEBUG(
dbgs() <<
"Instruction to promote is in a different block ("
8517 <<
") than the transition (" << Parent->
getName()
8522 if (VPH.canCombine(ToBePromoted)) {
8524 <<
"will be combined with: " << *ToBePromoted <<
'\n');
8525 VPH.recordCombineInstruction(ToBePromoted);
8527 NumStoreExtractExposed +=
Changed;
8532 if (!VPH.canPromote(ToBePromoted) || !VPH.shouldPromote(ToBePromoted))
8535 LLVM_DEBUG(
dbgs() <<
"Promoting is possible... Enqueue for promotion!\n");
8537 VPH.enqueueForPromotion(ToBePromoted);
8538 Inst = ToBePromoted;
8578 Type *StoreType =
SI.getValueOperand()->getType();
8587 if (!
DL.typeSizeEqualsStoreSize(StoreType) ||
8588 DL.getTypeSizeInBits(StoreType) == 0)
8591 unsigned HalfValBitSize =
DL.getTypeSizeInBits(StoreType) / 2;
8593 if (!
DL.typeSizeEqualsStoreSize(SplitStoreType))
8597 if (
SI.isVolatile())
8609 if (!
match(
SI.getValueOperand(),
8616 if (!
LValue->getType()->isIntegerTy() ||
8617 DL.getTypeSizeInBits(
LValue->getType()) > HalfValBitSize ||
8619 DL.getTypeSizeInBits(HValue->
getType()) > HalfValBitSize)
8635 Builder.SetInsertPoint(&
SI);
8639 if (LBC && LBC->getParent() !=
SI.getParent())
8640 LValue = Builder.CreateBitCast(LBC->getOperand(0), LBC->getType());
8641 if (HBC && HBC->getParent() !=
SI.getParent())
8642 HValue = Builder.CreateBitCast(HBC->getOperand(0), HBC->getType());
8644 bool IsLE =
SI.getDataLayout().isLittleEndian();
8645 auto CreateSplitStore = [&](
Value *V,
bool Upper) {
8646 V = Builder.CreateZExtOrBitCast(V, SplitStoreType);
8647 Value *Addr =
SI.getPointerOperand();
8648 Align Alignment =
SI.getAlign();
8649 const bool IsOffsetStore = (IsLE &&
Upper) || (!IsLE && !
Upper);
8650 if (IsOffsetStore) {
8651 Addr = Builder.CreateGEP(
8652 SplitStoreType, Addr,
8660 Builder.CreateAlignedStore(V, Addr, Alignment);
8663 CreateSplitStore(
LValue,
false);
8664 CreateSplitStore(HValue,
true);
8667 SI.eraseFromParent();
8675 return GEP->getNumOperands() == 2 &&
I.isSequential() &&
8757 if (GEPIOpI->getParent() != SrcBlock)
8762 if (auto *I = dyn_cast<Instruction>(Usr)) {
8763 if (I->getParent() != SrcBlock) {
8771 std::vector<GetElementPtrInst *> UGEPIs;
8774 for (User *Usr : GEPIOp->
users()) {
8793 if (UGEPI->getOperand(0) != GEPIOp)
8795 if (UGEPI->getSourceElementType() != GEPI->getSourceElementType())
8797 if (GEPIIdx->getType() !=
8805 UGEPIs.push_back(UGEPI);
8807 if (UGEPIs.size() == 0)
8810 for (GetElementPtrInst *UGEPI : UGEPIs) {
8812 APInt NewIdx = UGEPIIdx->
getValue() - GEPIIdx->getValue();
8819 for (GetElementPtrInst *UGEPI : UGEPIs) {
8820 UGEPI->setOperand(0, GEPI);
8822 Constant *NewUGEPIIdx = ConstantInt::get(
8823 GEPIIdx->getType(), UGEPIIdx->
getValue() - GEPIIdx->getValue());
8824 UGEPI->setOperand(1, NewUGEPIIdx);
8827 if (!GEPI->isInBounds()) {
8828 UGEPI->setIsInBounds(
false);
8835 return cast<Instruction>(Usr)->getParent() != SrcBlock;
8837 "GEPIOp is used outside SrcBlock");
8861 Value *
X = Cmp->getOperand(0);
8862 if (!
X->hasUseList())
8867 for (
auto *U :
X->users()) {
8871 (UI->
getParent() != Branch->getParent() &&
8872 UI->
getParent() != Branch->getSuccessor(0) &&
8873 UI->
getParent() != Branch->getSuccessor(1)) ||
8874 (UI->
getParent() != Branch->getParent() &&
8875 !UI->
getParent()->getSinglePredecessor()))
8881 if (UI->
getParent() != Branch->getParent())
8885 ConstantInt::get(UI->
getType(), 0));
8887 LLVM_DEBUG(
dbgs() <<
" to compare on zero: " << *NewCmp <<
"\n");
8891 if (Cmp->isEquality() &&
8896 if (UI->
getParent() != Branch->getParent())
8899 Value *NewCmp = Builder.CreateCmp(Cmp->getPredicate(), UI,
8900 ConstantInt::get(UI->
getType(), 0));
8902 LLVM_DEBUG(
dbgs() <<
" to compare on zero: " << *NewCmp <<
"\n");
8910bool CodeGenPrepare::optimizeInst(Instruction *
I, ModifyDT &ModifiedDT) {
8911 bool AnyChange =
false;
8912 AnyChange = fixupDbgVariableRecordsOnInst(*
I);
8916 if (InsertedInsts.count(
I))
8925 LargeOffsetGEPMap.erase(
P);
8927 P->eraseFromParent();
8950 I, LI->getLoopFor(
I->getParent()), *
TTI))
8958 TargetLowering::TypeExpandInteger) {
8962 I, LI->getLoopFor(
I->getParent()), *
TTI))
8965 bool MadeChange = optimizeExt(
I);
8966 return MadeChange | optimizeExtUses(
I);
8973 if (optimizeCmp(Cmp, ModifiedDT))
8977 if (optimizeURem(
I))
8981 LI->
setMetadata(LLVMContext::MD_invariant_group,
nullptr);
8982 bool Modified = optimizeLoadExt(LI);
8991 SI->setMetadata(LLVMContext::MD_invariant_group,
nullptr);
8992 unsigned AS =
SI->getPointerAddressSpace();
8993 return optimizeMemoryInst(
I,
SI->getOperand(1),
8994 SI->getOperand(0)->getType(), AS);
8998 unsigned AS = RMW->getPointerAddressSpace();
8999 return optimizeMemoryInst(
I, RMW->getPointerOperand(), RMW->getType(), AS);
9003 unsigned AS = CmpX->getPointerAddressSpace();
9004 return optimizeMemoryInst(
I, CmpX->getPointerOperand(),
9005 CmpX->getCompareOperand()->getType(), AS);
9015 if (BinOp && (BinOp->
getOpcode() == Instruction::AShr ||
9016 BinOp->
getOpcode() == Instruction::LShr)) {
9024 if (GEPI->hasAllZeroIndices()) {
9026 Instruction *
NC =
new BitCastInst(GEPI->getOperand(0), GEPI->getType(),
9027 GEPI->getName(), GEPI->getIterator());
9028 NC->setDebugLoc(GEPI->getDebugLoc());
9031 GEPI, TLInfo,
nullptr,
9032 [&](
Value *V) { removeAllAssertingVHReferences(V); });
9034 optimizeInst(
NC, ModifiedDT);
9057 if (Const0 || Const1) {
9058 if (!Const0 || !Const1) {
9059 auto *
F =
new FreezeInst(Const0 ? Op1 : Op0,
"", CmpI->
getIterator());
9064 FI->eraseFromParent();
9071 if (tryToSinkFreeOperands(
I))
9074 switch (
I->getOpcode()) {
9075 case Instruction::Shl:
9076 case Instruction::LShr:
9077 case Instruction::AShr:
9079 case Instruction::Call:
9081 case Instruction::Select:
9083 case Instruction::ShuffleVector:
9085 case Instruction::Switch:
9087 case Instruction::ExtractElement:
9089 case Instruction::CondBr:
9098bool CodeGenPrepare::makeBitReverse(Instruction &
I) {
9099 if (!
I.getType()->isIntegerTy() ||
9104 SmallVector<Instruction *, 4> Insts;
9110 &
I, TLInfo,
nullptr,
9111 [&](
Value *V) { removeAllAssertingVHReferences(V); });
9118bool CodeGenPrepare::optimizeBlock(BasicBlock &BB, ModifyDT &ModifiedDT) {
9120 bool MadeChange =
false;
9123 CurInstIterator = BB.
begin();
9124 ModifiedDT = ModifyDT::NotModifyDT;
9125 while (CurInstIterator != BB.
end()) {
9126 MadeChange |= optimizeInst(&*CurInstIterator++, ModifiedDT);
9127 if (ModifiedDT != ModifyDT::NotModifyDT) {
9136 }
while (ModifiedDT == ModifyDT::ModifyInstDT);
9138 bool MadeBitReverse =
true;
9139 while (MadeBitReverse) {
9140 MadeBitReverse =
false;
9142 if (makeBitReverse(
I)) {
9143 MadeBitReverse = MadeChange =
true;
9148 MadeChange |= dupRetToEnableTailCallOpts(&BB, ModifiedDT);
9153bool CodeGenPrepare::fixupDbgVariableRecordsOnInst(Instruction &
I) {
9154 bool AnyChange =
false;
9155 for (DbgVariableRecord &DVR :
filterDbgVars(
I.getDbgRecordRange()))
9156 AnyChange |= fixupDbgVariableRecord(DVR);
9162bool CodeGenPrepare::fixupDbgVariableRecord(DbgVariableRecord &DVR) {
9163 if (DVR.
Type != DbgVariableRecord::LocationType::Value &&
9164 DVR.
Type != DbgVariableRecord::LocationType::Assign)
9168 bool AnyChange =
false;
9169 SmallDenseSet<Value *> LocationOps(DVR.
location_ops().begin(),
9171 for (
Value *Location : LocationOps) {
9172 WeakTrackingVH SunkAddrVH = SunkAddrs[
Location];
9201bool CodeGenPrepare::placeDbgValues(Function &
F) {
9202 bool MadeChange =
false;
9203 DominatorTree &DT = getDT();
9205 auto DbgProcessor = [&](
auto *DbgItem,
Instruction *Position) {
9206 SmallVector<Instruction *, 4> VIs;
9207 for (
Value *V : DbgItem->location_ops())
9215 for (Instruction *VI : VIs) {
9216 if (
VI->isTerminator())
9221 if (
isa<PHINode>(VI) &&
VI->getParent()->getTerminator()->isEHPad())
9232 if (VIs.size() > 1) {
9235 <<
"Unable to find valid location for Debug Value, undefing:\n"
9237 DbgItem->setKillLocation();
9242 << *DbgItem <<
' ' << *VI);
9249 for (BasicBlock &BB :
F) {
9255 if (DVR.
Type != DbgVariableRecord::LocationType::Value)
9257 DbgProcessor(&DVR, &Insn);
9268bool CodeGenPrepare::placePseudoProbes(Function &
F) {
9269 bool MadeChange =
false;
9272 auto FirstInst =
Block.getFirstInsertionPt();
9273 while (FirstInst !=
Block.end() && FirstInst->isDebugOrPseudoInst())
9277 while (
I !=
Block.end()) {
9279 II->moveBefore(FirstInst);
9289 uint64_t NewMax = (NewTrue > NewFalse) ? NewTrue : NewFalse;
9290 uint32_t Scale = (NewMax / std::numeric_limits<uint32_t>::max()) + 1;
9291 NewTrue = NewTrue / Scale;
9292 NewFalse = NewFalse / Scale;
9317bool CodeGenPrepare::splitBranchCondition(Function &
F) {
9321 bool MadeChange =
false;
9322 for (
auto &BB :
F) {
9335 if (Br1->getMetadata(LLVMContext::MD_unpredictable))
9343 Value *Cond1, *Cond2;
9346 Opc = Instruction::And;
9349 Opc = Instruction::Or;
9359 if (!IsGoodCond(Cond1) || !IsGoodCond(Cond2))
9373 Br1->setCondition(Cond1);
9378 if (
Opc == Instruction::And)
9379 Br1->setSuccessor(0, TmpBB);
9381 Br1->setSuccessor(1, TmpBB);
9386 I->removeFromParent();
9387 I->insertBefore(Br2->getIterator());
9399 if (
Opc == Instruction::Or)
9406 for (PHINode &PN : FBB->
phis()) {
9411 if (Loop *L = LI->getLoopFor(&BB))
9412 L->addBasicBlockToLoop(TmpBB, *LI);
9416 DTU->
applyUpdates({{DominatorTree::Insert, &BB, TmpBB},
9417 {DominatorTree::Insert, TmpBB,
TBB},
9418 {DominatorTree::Insert, TmpBB, FBB},
9419 {DominatorTree::Delete, &BB,
TBB}});
9423 if (
Opc == Instruction::Or) {
9443 uint64_t TrueWeight, FalseWeight;
9445 uint64_t NewTrueWeight = TrueWeight;
9446 uint64_t NewFalseWeight = TrueWeight + 2 * FalseWeight;
9448 Br1->setMetadata(LLVMContext::MD_prof,
9449 MDBuilder(Br1->getContext())
9450 .createBranchWeights(TrueWeight, FalseWeight,
9453 NewTrueWeight = TrueWeight;
9454 NewFalseWeight = 2 * FalseWeight;
9456 Br2->setMetadata(LLVMContext::MD_prof,
9457 MDBuilder(Br2->getContext())
9458 .createBranchWeights(TrueWeight, FalseWeight));
9479 uint64_t TrueWeight, FalseWeight;
9481 uint64_t NewTrueWeight = 2 * TrueWeight + FalseWeight;
9482 uint64_t NewFalseWeight = FalseWeight;
9484 Br1->setMetadata(LLVMContext::MD_prof,
9485 MDBuilder(Br1->getContext())
9486 .createBranchWeights(TrueWeight, FalseWeight));
9488 NewTrueWeight = 2 * TrueWeight;
9489 NewFalseWeight = FalseWeight;
9491 Br2->setMetadata(LLVMContext::MD_prof,
9492 MDBuilder(Br2->getContext())
9493 .createBranchWeights(TrueWeight, FalseWeight));
static unsigned getIntrinsicID(const SDNode *N)
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
AMDGPU Register Bank Select
This file implements a class to represent arbitrary precision integral constant values and operations...
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)
This file contains the simple types necessary to represent the attributes associated with functions a...
static const Function * getParent(const Value *V)
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 GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-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)
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 bool isExtractBitsCandidateUse(Instruction *User)
Check if the candidates could be combined with a shift instruction, which includes:
static cl::opt< unsigned > MaxAddressUsersToScan("cgp-max-address-users-to-scan", cl::init(100), cl::Hidden, cl::desc("Max number of address users to look at"))
static cl::opt< bool > OptimizePhiTypes("cgp-optimize-phi-types", cl::Hidden, cl::init(true), cl::desc("Enable converting phi types in CodeGenPrepare"))
static cl::opt< bool > DisableStoreExtract("disable-cgp-store-extract", cl::Hidden, cl::init(false), cl::desc("Disable store(extract) optimizations in CodeGenPrepare"))
static bool foldFCmpToFPClassTest(CmpInst *Cmp, const TargetLowering &TLI, const DataLayout &DL)
static void scaleWeights(uint64_t &NewTrue, uint64_t &NewFalse)
Scale down both weights to fit into uint32_t.
static cl::opt< bool > ProfileUnknownInSpecialSection("profile-unknown-in-special-section", cl::Hidden, cl::desc("In profiling mode like sampleFDO, if a function doesn't have " "profile, we cannot tell the function is cold for sure because " "it may be a function newly added without ever being sampled. " "With the flag enabled, compiler can put such profile unknown " "functions into a special section, so runtime system can choose " "to handle it in a different way than .text section, to save " "RAM for example. "))
static bool OptimizeExtractBits(BinaryOperator *ShiftI, ConstantInt *CI, const TargetLowering &TLI, const DataLayout &DL)
Sink the shift right instruction into user blocks if the uses could potentially be combined with this...
static cl::opt< bool > DisableExtLdPromotion("disable-cgp-ext-ld-promotion", cl::Hidden, cl::init(false), cl::desc("Disable ext(promotable(ld)) -> promoted(ext(ld)) optimization in " "CodeGenPrepare"))
static cl::opt< bool > DisablePreheaderProtect("disable-preheader-prot", cl::Hidden, cl::init(false), cl::desc("Disable protection against removing loop preheaders"))
static cl::opt< bool > AddrSinkCombineBaseOffs("addr-sink-combine-base-offs", cl::Hidden, cl::init(true), cl::desc("Allow combining of BaseOffs field in Address sinking."))
static bool OptimizeNoopCopyExpression(CastInst *CI, const TargetLowering &TLI, const DataLayout &DL)
If the specified cast instruction is a noop copy (e.g.
static bool splitMergedValStore(StoreInst &SI, const DataLayout &DL, const TargetLowering &TLI)
For the instruction sequence of store below, F and I values are bundled together as an i64 value befo...
static bool SinkCast(CastInst *CI)
Sink the specified cast instruction into its user blocks.
static bool swapICmpOperandsToExposeCSEOpportunities(CmpInst *Cmp)
Many architectures use the same instruction for both subtract and cmp.
static cl::opt< bool > AddrSinkCombineBaseReg("addr-sink-combine-base-reg", cl::Hidden, cl::init(true), cl::desc("Allow combining of BaseReg field in Address sinking."))
static bool FindAllMemoryUses(Instruction *I, SmallVectorImpl< std::pair< Use *, Type * > > &MemoryUses, SmallPtrSetImpl< Instruction * > &ConsideredInsts, const TargetLowering &TLI, const TargetRegisterInfo &TRI, bool OptSize, ProfileSummaryInfo *PSI, BlockFrequencyInfo *BFI, unsigned &SeenInsts)
Recursively walk all the uses of I until we find a memory use.
static cl::opt< bool > StressStoreExtract("stress-cgp-store-extract", cl::Hidden, cl::init(false), cl::desc("Stress test store(extract) optimizations in CodeGenPrepare"))
static bool isFormingBranchFromSelectProfitable(const TargetTransformInfo *TTI, const TargetLowering *TLI, SelectInst *SI)
Returns true if a SelectInst should be turned into an explicit branch.
static std::optional< std::pair< Instruction *, Constant * > > getIVIncrement(const PHINode *PN, const LoopInfo *LI)
If given PN is an inductive variable with value IVInc coming from the backedge, and on each iteration...
static cl::opt< bool > AddrSinkCombineBaseGV("addr-sink-combine-base-gv", cl::Hidden, cl::init(true), cl::desc("Allow combining of BaseGV field in Address sinking."))
static cl::opt< bool > AddrSinkUsingGEPs("addr-sink-using-gep", cl::Hidden, cl::init(true), cl::desc("Address sinking in CGP using GEPs."))
static Value * getTrueOrFalseValue(SelectInst *SI, bool isTrue, const SmallPtrSet< const Instruction *, 2 > &Selects)
If isTrue is true, return the true value of SI, otherwise return false value of SI.
static 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 > ProfileGuidedSectionPrefix("profile-guided-section-prefix", cl::Hidden, cl::init(true), cl::desc("Use profile info to add section prefix for hot/cold functions"))
static cl::opt< unsigned > HugeFuncThresholdInCGPP("cgpp-huge-func", cl::init(10000), cl::Hidden, cl::desc("Least BB number of huge function."))
static cl::opt< bool > AddrSinkNewSelects("addr-sink-new-select", cl::Hidden, cl::init(true), cl::desc("Allow creation of selects in Address sinking."))
static bool foldURemOfLoopIncrement(Instruction *Rem, const DataLayout *DL, const LoopInfo *LI, SmallPtrSet< BasicBlock *, 32 > &FreshBBs, bool IsHuge)
static bool optimizeBranch(CondBrInst *Branch, const TargetLowering &TLI, SmallPtrSet< BasicBlock *, 32 > &FreshBBs, bool IsHugeFunc)
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 void replaceAllUsesWith(Value *Old, Value *New, SmallPtrSet< BasicBlock *, 32 > &FreshBBs, bool IsHuge)
Replace all old uses with new ones, and push the updated BBs into FreshBBs.
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 matchOverflowPattern(Instruction *&I, ExtractValueInst *&MulExtract, ExtractValueInst *&OverflowExtract)
static void computeBaseDerivedRelocateMap(const SmallVectorImpl< GCRelocateInst * > &AllRelocateCalls, MapVector< GCRelocateInst *, SmallVector< GCRelocateInst *, 0 > > &RelocateInstMap)
static bool simplifyRelocatesOffABase(GCRelocateInst *RelocatedBase, const SmallVectorImpl< GCRelocateInst * > &Targets)
static cl::opt< bool > AddrSinkCombineScaledReg("addr-sink-combine-scaled-reg", cl::Hidden, cl::init(true), cl::desc("Allow combining of ScaledReg field in Address sinking."))
static bool foldICmpWithDominatingICmp(CmpInst *Cmp, const TargetLowering &TLI)
For pattern like:
static bool MightBeFoldableInst(Instruction *I)
This is a little filter, which returns true if an addressing computation involving I might be folded ...
static bool matchIncrement(const Instruction *IVInc, Instruction *&LHS, Constant *&Step)
static cl::opt< bool > EnableGEPOffsetSplit("cgp-split-large-offset-gep", cl::Hidden, cl::init(true), cl::desc("Enable splitting large offset of GEP."))
static cl::opt< bool > DisableComplexAddrModes("disable-complex-addr-modes", cl::Hidden, cl::init(false), cl::desc("Disables combining addressing modes with different parts " "in optimizeMemoryInst."))
static cl::opt< bool > EnableICMP_EQToICMP_ST("cgp-icmp-eq2icmp-st", cl::Hidden, cl::init(false), cl::desc("Enable ICMP_EQ to ICMP_S(L|G)T conversion."))
static cl::opt< bool > VerifyBFIUpdates("cgp-verify-bfi-updates", cl::Hidden, cl::init(false), cl::desc("Enable BFI update verification for " "CodeGenPrepare."))
static cl::opt< bool > BBSectionsGuidedSectionPrefix("bbsections-guided-section-prefix", cl::Hidden, cl::init(true), cl::desc("Use the basic-block-sections profile to determine the text " "section prefix for hot functions. Functions with " "basic-block-sections profile will be placed in `.text.hot` " "regardless of their FDO profile info. Other functions won't be " "impacted, i.e., their prefixes will be decided by FDO/sampleFDO " "profiles."))
static bool isRemOfLoopIncrementWithLoopInvariant(Instruction *Rem, const LoopInfo *LI, Value *&RemAmtOut, Value *&AddInstOut, Value *&AddOffsetOut, PHINode *&LoopIncrPNOut)
static bool isIVIncrement(const Value *V, const LoopInfo *LI)
static cl::opt< bool > DisableGCOpts("disable-cgp-gc-opts", cl::Hidden, cl::init(false), cl::desc("Disable GC optimizations in CodeGenPrepare"))
static bool GEPSequentialConstIndexed(GetElementPtrInst *GEP)
static void DbgInserterHelper(DbgVariableRecord *DVR, BasicBlock::iterator VI)
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 BasicBlock::iterator findInsertPos(Value *Addr, Instruction *MemoryInst, Value *SunkAddr)
static bool IsNonLocalValue(Value *V, BasicBlock *BB)
Return true if the specified values are defined in a different basic block than BB.
static cl::opt< bool > EnableAndCmpSinking("enable-andcmp-sinking", cl::Hidden, cl::init(true), cl::desc("Enable sinking and/cmp into branches."))
static bool despeculateCountZeros(IntrinsicInst *CountZeros, DomTreeUpdater *DTU, LoopInfo *LI, const TargetLowering *TLI, const DataLayout *DL, ModifyDT &ModifiedDT, SmallPtrSet< BasicBlock *, 32 > &FreshBBs, bool IsHugeFunc)
If counting leading or trailing zeros is an expensive operation and a zero input is defined,...
static bool sinkCmpExpression(CmpInst *Cmp, const TargetLowering &TLI, const DataLayout &DL)
Sink the given CmpInst into user blocks to reduce the number of virtual registers that must be create...
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.
This file contains the declarations for the subclasses of Constant, which represent the different fla...
static cl::opt< OutputCostKind > CostKind("cost-kind", cl::desc("Target cost kind"), cl::init(OutputCostKind::RecipThroughput), cl::values(clEnumValN(OutputCostKind::RecipThroughput, "throughput", "Reciprocal throughput"), clEnumValN(OutputCostKind::Latency, "latency", "Instruction latency"), clEnumValN(OutputCostKind::CodeSize, "code-size", "Code size"), clEnumValN(OutputCostKind::SizeAndLatency, "size-latency", "Code size and latency"), clEnumValN(OutputCostKind::All, "all", "Print all cost kinds")))
This file defines the DenseMap class.
static bool runOnFunction(Function &F, bool PostInlining)
static Value * getCondition(Instruction *I)
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
Module.h This file contains the declarations for the Module class.
This defines the Use class.
const AbstractManglingParser< Derived, Alloc >::OperatorInfo AbstractManglingParser< Derived, Alloc >::Ops[]
static void eraseInstruction(Instruction &I, ICFLoopSafetyInfo &SafetyInfo, MemorySSAUpdater &MSSAU)
Register const TargetRegisterInfo * TRI
This file implements a map that provides insertion order iteration.
MachineInstr unsigned OpIdx
uint64_t IntrinsicInst * II
OptimizedStructLayoutField Field
#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 DominatorTree getDomTree(Function &F)
static bool dominates(InstrPosIndexes &PosIndexes, const MachineInstr &A, const MachineInstr &B)
Remove Loads Into Fake Uses
static bool optimizeBlock(BasicBlock &BB, bool &ModifiedDT, const TargetTransformInfo &TTI, const DataLayout &DL, bool HasBranchDivergence, DomTreeUpdater *DTU)
static bool optimizeCallInst(CallInst *CI, bool &ModifiedDT, const TargetTransformInfo &TTI, const DataLayout &DL, bool HasBranchDivergence, DomTreeUpdater *DTU)
This file defines the SmallPtrSet class.
This file defines the SmallVector class.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
static TableGen::Emitter::Opt Y("gen-skeleton-entry", EmitSkeleton, "Generate example skeleton entry")
static SymbolRef::Type getType(const Symbol *Sym)
static bool canCombine(MachineBasicBlock &MBB, MachineOperand &MO, unsigned CombineOpc=0)
This file describes how to lower LLVM code to machine code.
static cl::opt< bool > DisableSelectOptimize("disable-select-optimize", cl::init(true), cl::Hidden, cl::desc("Disable the select-optimization pass from running"))
Disable the select optimization pass.
Target-Independent Code Generator Pass Configuration Options pass.
static unsigned getBitWidth(Type *Ty, const DataLayout &DL)
Returns the bitwidth of the given scalar or pointer type.
static Constant * getConstantVector(MVT VT, ArrayRef< APInt > Bits, const APInt &Undefs, LLVMContext &C)
Class for arbitrary precision integers.
LLVM_ABI 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
LLVM_ABI 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.
LLVM_ABI 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.
LLVM_ABI std::optional< TypeSize > getAllocationSize(const DataLayout &DL) const
Get allocation size in bytes.
void setAlignment(Align Align)
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.
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),...
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.
LLVM_ABI const_iterator getFirstInsertionPt() const
Returns an iterator to the first instruction in this block that is suitable for inserting a non-PHI i...
const Function * getParent() const
Return the enclosing method, or null if none.
bool hasAddressTaken() const
Returns true if there are any uses of this basic block other than direct branches,...
LLVM_ABI InstListType::const_iterator getFirstNonPHIIt() const
Returns an iterator to the first instruction in this block that is not a PHINode instruction.
LLVM_ABI void insertDbgRecordBefore(DbgRecord *DR, InstListType::iterator Here)
Insert a DbgRecord into a block at the position given by Here.
InstListType::const_iterator const_iterator
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
LLVM_ABI void moveAfter(BasicBlock *MovePos)
Unlink this basic block from its current function and insert it right after MovePos in the function M...
LLVM_ABI InstListType::const_iterator getFirstNonPHIOrDbg(bool SkipPseudoOp=true) const
Returns a pointer to the first instruction in this block that is not a PHINode or a debug intrinsic,...
LLVM_ABI const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
LLVM_ABI const BasicBlock * getUniquePredecessor() const
Return the predecessor of this block if it has a unique predecessor block.
LLVM_ABI const BasicBlock * getSingleSuccessor() const
Return the successor of this block if it has a single successor.
LLVM_ABI void insertDbgRecordAfter(DbgRecord *DR, Instruction *I)
Insert a DbgRecord into a block at the position given by I.
InstListType::iterator iterator
Instruction iterators...
LLVM_ABI LLVMContext & getContext() const
Get the context in which this basic block lives.
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction; assumes that the block is well-formed.
BinaryOps getOpcode() const
static LLVM_ABI BinaryOperator * Create(BinaryOps Op, Value *S1, Value *S2, const Twine &Name=Twine(), InsertPosition InsertBefore=nullptr)
Construct a binary instruction, given the opcode and the two operands.
Analysis pass which computes BlockFrequencyInfo.
BlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate IR basic block frequen...
LLVM_ABI void setBlockFreq(const BasicBlock *BB, BlockFrequency Freq)
LLVM_ABI BlockFrequency getBlockFreq(const BasicBlock *BB) const
getblockFreq - Return block frequency.
LLVM_ABI std::optional< BlockFrequency > mul(uint64_t Factor) const
Multiplies frequency with Factor. Returns nullopt in case of overflow.
Analysis pass which computes BranchProbabilityInfo.
static LLVM_ABI BranchProbability getBranchProbability(uint64_t Numerator, uint64_t Denominator)
bool isInlineAsm() const
Check if this call is an inline asm statement.
Function * getCalledFunction() const
Returns the function called, or null if this is an indirect function invocation or the function signa...
bool hasFnAttr(Attribute::AttrKind Kind) const
Determine whether this call has the given attribute.
Value * getArgOperand(unsigned i) const
void setArgOperand(unsigned i, Value *v)
iterator_range< User::op_iterator > args()
Iteration adapter for range-for loops.
This class represents a function call, abstracting a target machine's calling convention.
This is the base class for all instructions that perform data casts.
static LLVM_ABI CastInst * Create(Instruction::CastOps, Value *S, Type *Ty, const Twine &Name="", InsertPosition InsertBefore=nullptr)
Provides a way to construct any of the CastInst subclasses using an opcode instead of the subclass's ...
This class is the base class for the comparison instructions.
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
@ ICMP_SLT
signed less than
@ ICMP_UGT
unsigned greater than
@ ICMP_SGT
signed greater than
@ ICMP_ULT
unsigned less than
@ ICMP_ULE
unsigned less or equal
Predicate getSwappedPredicate() const
For example, EQ->EQ, SLE->SGE, ULT->UGT, OEQ->OEQ, ULE->UGE, OLT->OGT, etc.
static LLVM_ABI CmpInst * Create(OtherOps Op, Predicate Pred, Value *S1, Value *S2, const Twine &Name="", InsertPosition InsertBefore=nullptr)
Construct a compare instruction, given the opcode, the predicate and the two operands.
Predicate getPredicate() const
Return the predicate for this instruction.
An abstraction over a floating-point predicate, and a pack of an integer predicate with samesign info...
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Conditional Branch instruction.
static LLVM_ABI Constant * getBitCast(Constant *C, Type *Ty, bool OnlyIfReduced=false)
static LLVM_ABI Constant * getNeg(Constant *C, bool HasNSW=false)
This is the shared class of boolean and integer constants.
static LLVM_ABI ConstantInt * getTrue(LLVMContext &Context)
static ConstantInt * getSigned(IntegerType *Ty, int64_t V, bool ImplicitTrunc=false)
Return a ConstantInt with the specified value for the specified type.
bool isZero() const
This is just a convenience method to make client code smaller for a common code.
static LLVM_ABI ConstantInt * getFalse(LLVMContext &Context)
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 LLVM_ABI Constant * getSplat(ElementCount EC, Constant *Elt)
Return a ConstantVector with the specified constant in each element.
static LLVM_ABI Constant * get(ArrayRef< Constant * > V)
This is an important base class in LLVM.
static LLVM_ABI Constant * getAllOnesValue(Type *Ty)
static LLVM_ABI Constant * getNullValue(Type *Ty)
Constructor to create a '0' constant of arbitrary type.
A parsed version of the target data layout string in and methods for querying it.
LLVM_ABI void removeFromParent()
Record of a variable value-assignment, aka a non instruction representation of the dbg....
LocationType Type
Classification of the debug-info record that this DbgVariableRecord represents.
LLVM_ABI void replaceVariableLocationOp(Value *OldValue, Value *NewValue, bool AllowEmpty=false)
LLVM_ABI iterator_range< location_op_iterator > location_ops() const
Get the locations corresponding to the variable referenced by the debug info intrinsic.
iterator find(const_arg_type_t< KeyT > Val)
bool erase(const KeyT &Val)
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
LLVM_ABI void deleteBB(BasicBlock *DelBB)
Delete DelBB.
Analysis pass which computes a DominatorTree.
static constexpr UpdateKind Insert
Legacy analysis pass which computes a DominatorTree.
LLVM_ABI 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 LLVM_ABI FixedVectorType * get(Type *ElementType, unsigned NumElts)
FunctionPass class - This class is used to implement most global optimizations.
const BasicBlock & getEntryBlock() const
LLVM_ABI 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...
DomTreeT & getDomTree()
Flush DomTree updates and return DomTree.
void applyUpdates(ArrayRef< UpdateT > Updates)
Submit updates to all available trees.
void flush()
Apply all pending updates to available trees and flush all BasicBlocks awaiting deletion.
bool isBBPendingDeletion(BasicBlockT *DelBB) const
Returns true if DelBB is awaiting deletion.
an instruction for type-safe pointer arithmetic to access elements of arrays and structs
static LLVM_ABI Type * getIndexedType(Type *Ty, ArrayRef< Value * > IdxList)
Returns the result type of a getelementptr with the given source element type and indexes.
LLVM_ABI bool canIncreaseAlignment() const
Returns true if the alignment of the value can be unilaterally increased.
bool isThreadLocal() const
If the value is "Thread Local", its value isn't shared by the threads.
LLVM_ABI uint64_t getGlobalSize(const DataLayout &DL) const
Get the size of this global variable in bytes.
void setAlignment(Align Align)
Sets the alignment attribute of the GlobalVariable.
This instruction compares its operands according to the predicate given to the constructor.
bool isEquality() const
Return true if this predicate is either EQ or NE.
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
LLVM_ABI Instruction * clone() const
Create a copy of 'this' instruction that is identical in all ways except the following:
LLVM_ABI void removeFromParent()
This method unlinks 'this' from the containing basic block, but does not delete it.
LLVM_ABI bool isDebugOrPseudoInst() const LLVM_READONLY
Return true if the instruction is a DbgInfoIntrinsic or PseudoProbeInst.
LLVM_ABI void setHasNoSignedWrap(bool b=true)
Set or clear the nsw flag on this instruction, which must be an operator which supports this flag.
const DebugLoc & getDebugLoc() const
Return the debug location for this node as a DebugLoc.
LLVM_ABI void moveAfter(Instruction *MovePos)
Unlink this instruction from its current basic block and insert it into the basic block that MovePos ...
LLVM_ABI void moveBefore(InstListType::iterator InsertPos)
Unlink this instruction from its current basic block and insert it into the basic block that MovePos ...
LLVM_ABI void insertBefore(InstListType::iterator InsertPos)
Insert an unlinked instruction into a basic block immediately before the specified position.
bool isEHPad() const
Return true if the instruction is a variety of EH-block.
LLVM_ABI 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...
LLVM_ABI const Function * getFunction() const
Return the function this instruction belongs to.
LLVM_ABI bool mayHaveSideEffects() const LLVM_READONLY
Return true if the instruction may have side effects.
LLVM_ABI bool comesBefore(const Instruction *Other) const
Given an instruction Other in the same basic block as this instruction, return true if this instructi...
LLVM_ABI bool mayReadFromMemory() const LLVM_READONLY
Return true if this instruction may read memory.
LLVM_ABI void setMetadata(unsigned KindID, MDNode *Node)
Set the metadata of the specified kind to the specified node.
LLVM_ABI FastMathFlags getFastMathFlags() const LLVM_READONLY
Convenience function for getting all the fast-math flags, which must be an operator which supports th...
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
LLVM_ABI void dropPoisonGeneratingFlags()
Drops flags that may cause this instruction to evaluate to poison despite having non-poison inputs.
LLVM_ABI 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.
LLVM_ABI void copyMetadata(const Instruction &SrcInst, ArrayRef< unsigned > WL=ArrayRef< unsigned >())
Copy metadata from SrcInst to this instruction.
LLVM_ABI void insertAfter(Instruction *InsertPos)
Insert an unlinked instruction into a basic block immediately after the specified instruction.
A wrapper class for inspecting calls to intrinsic functions.
Intrinsic::ID getIntrinsicID() const
Return the intrinsic ID of this intrinsic.
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.
void verify(const DominatorTreeBase< BlockT, false > &DomTree) const
void analyze(const DominatorTreeBase< BlockT, false > &DomTree)
Create the loop forest using a stable algorithm.
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.
static MVT getIntegerVT(unsigned BitWidth)
LLVM_ABI void replacePhiUsesWith(MachineBasicBlock *Old, MachineBasicBlock *New)
Update all phi nodes in this basic block to refer to basic block New instead of basic block Old.
This class implements a map that also provides access to all stored values in a deterministic order.
VectorType::iterator erase(typename VectorType::iterator Iterator)
Remove the element given by Iterator.
iterator find(const KeyT &Key)
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
op_range incoming_values()
Value * getIncomingValueForBlock(const BasicBlock *BB) const
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
unsigned getNumIncomingValues() const
Return the number of incoming edges.
static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr="", InsertPosition InsertBefore=nullptr)
Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...
PointerIntPair - This class implements a pair of a pointer and small integer.
static LLVM_ABI 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.
PreservedAnalyses & 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.
bool isFunctionColdInCallGraph(const FuncT *F, BFIT &BFI) const
Returns true if F contains only cold code.
LLVM_ABI bool isFunctionHotnessUnknown(const Function &F) const
Returns true if the hotness of F is unknown.
bool isFunctionHotInCallGraph(const FuncT *F, BFIT &BFI) const
Returns true if F contains hot code.
LLVM_ABI bool hasPartialSampleProfile() const
Returns true if module M has partial-profile sample profile.
LLVM_ABI bool hasHugeWorkingSetSize() const
Returns true if the working set size of the code is considered huge.
Value * getReturnValue() const
Convenience accessor. Returns null if there is no return value.
This class represents the LLVM 'select' instruction.
static SelectInst * Create(Value *C, Value *S1, Value *S2, const Twine &NameStr="", InsertPosition InsertBefore=nullptr, const Instruction *MDFrom=nullptr)
size_type count(const_arg_type key) const
Count the number of elements of a given key in the SetVector.
void clear()
Completely clear 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()
VectorType * getType() const
Overload to return most specific vector type.
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
bool erase(PtrType Ptr)
Remove pointer from the set.
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
void insert_range(Range &&R)
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
bool contains(ConstPtrType Ptr) const
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
size_type count(const T &V) const
count - Return 1 if the element is in the set, 0 otherwise.
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()
TypeSize getElementOffset(unsigned Idx) const
Analysis pass providing the TargetTransformInfo.
Analysis pass providing the TargetLibraryInfo.
Provides information about what library functions are available for the current target.
bool getLibFunc(StringRef funcName, LibFunc &F) const
Searches for a particular function name.
int InstructionOpcodeToISD(unsigned Opcode) const
Get the ISD node that corresponds to the Instruction class opcode.
EVT getValueType(const DataLayout &DL, Type *Ty, bool AllowUnknown=false) const
Return the EVT corresponding to this LLVM type.
virtual bool isSelectSupported(SelectSupportKind) const
virtual bool isEqualityCmpFoldedWithSignedCmp() const
Return true if instruction generated for equality comparison is folded with instruction generated for...
virtual bool shouldFormOverflowOp(unsigned Opcode, EVT VT, bool MathUsed) const
Try to convert math with an overflow comparison into the corresponding DAG node operation.
virtual bool isMaskAndCmp0FoldingBeneficial(const Instruction &AndI) const
Return if the target supports combining a chain like:
virtual bool shouldOptimizeMulOverflowWithZeroHighBits(LLVMContext &Context, EVT VT) const
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 isCtpopFast(EVT VT) const
Return true if ctpop instruction is fast.
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.
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 bool hasMultipleConditionRegisters(EVT VT) const
Does the target have multiple (allocatable) condition registers that can be used to store the results...
virtual EVT getTypeToTransformTo(LLVMContext &Context, EVT VT) const
For types supported by the target, this is an identity function.
virtual MVT getPreferredSwitchConditionType(LLVMContext &Context, EVT ConditionVT) const
Returns preferred type for switch condition.
bool isCondCodeLegal(ISD::CondCode CC, MVT VT) const
Return true if the specified condition code is legal for a comparison of the specified types on this ...
virtual bool canCombineStoreAndExtract(Type *VectorTy, Value *Idx, unsigned &Cost) const
Return true if the target can combine store(extractelement VectorTy,Idx).
bool isTypeLegal(EVT VT) const
Return true if the target has native support for the specified value type.
virtual bool isFreeAddrSpaceCast(unsigned SrcAS, unsigned DestAS) const
Returns true if a cast from SrcAS to DestAS is "cheap", such that e.g.
virtual bool shouldConsiderGEPOffsetSplit() const
bool isExtFree(const Instruction *I) const
Return true if the extension represented by I is free.
bool isOperationLegalOrCustom(unsigned Op, EVT VT, bool LegalOnly=false) const
Return true if the specified operation is legal on this target or can be made legal with custom lower...
bool isPredictableSelectExpensive() const
Return true if selects are only cheaper than branches if the branch is unlikely to be predicted right...
virtual bool isMultiStoresCheaperThanBitsMerge(EVT LTy, EVT HTy) const
Return true if it is cheaper to split the store of a merged int val from a pair of smaller values int...
virtual bool getAddrModeArguments(const IntrinsicInst *, SmallVectorImpl< Value * > &, Type *&) const
CodeGenPrepare sinks address calculations into the same BB as Load/Store instructions reading the add...
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...
bool isLoadLegal(EVT ValVT, EVT MemVT, Align Alignment, unsigned AddrSpace, unsigned ExtType, bool Atomic) const
Return true if the specified load with extension is legal on this target.
virtual bool addressingModeSupportsTLS(const GlobalValue &) const
Returns true if the targets addressing mode can target thread local storage (TLS).
virtual bool shouldConvertPhiType(Type *From, Type *To) const
Given a set in interconnected phis of type 'From' that are loaded/stored or bitcast to type 'To',...
virtual bool isFAbsFree(EVT VT) const
Return true if an fabs operation is free to the point where it is never worthwhile to replace it with...
virtual bool preferZeroCompareBranch() const
Return true if the heuristic to prefer icmp eq zero should be used in code gen prepare.
virtual bool isLegalAddressingMode(const DataLayout &DL, const AddrMode &AM, Type *Ty, unsigned AddrSpace, Instruction *I=nullptr) const
Return true if the addressing mode represented by AM is legal for this target, for a load/store of th...
virtual bool optimizeExtendOrTruncateConversion(Instruction *I, Loop *L, const TargetTransformInfo &TTI) const
Try to optimize extending or truncating conversion instructions (like zext, trunc,...
This class defines information used to lower LLVM code to legal SelectionDAG operators that the targe...
std::vector< AsmOperandInfo > AsmOperandInfoVector
virtual 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.
virtual bool isNoopAddrSpaceCast(unsigned SrcAS, unsigned DestAS) const
Returns true if a cast between SrcAS and DestAS is a noop.
virtual const TargetSubtargetInfo * getSubtargetImpl(const Function &) const
Virtual method implemented by subclasses that returns a reference to that target's TargetSubtargetInf...
unsigned EnableFastISel
EnableFastISel - This flag enables fast-path instruction selection which trades away generated code q...
Target-Independent Code Generator Pass Configuration Options.
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
virtual const TargetRegisterInfo * getRegisterInfo() const =0
Return the target's register information.
virtual const TargetLowering * getTargetLowering() const
virtual bool addrSinkUsingGEPs() const
Sink addresses into blocks using GEP instructions rather than pointer casts and arithmetic.
The instances of the Type class are immutable: once they are created, they are never changed.
LLVM_ABI unsigned getIntegerBitWidth() const
bool isVectorTy() const
True if this is an instance of VectorType.
LLVM_ABI bool isScalableTy(SmallPtrSetImpl< const Type * > &Visited) const
Return true if this is a type whose size is a known multiple of vscale.
static LLVM_ABI IntegerType * getInt32Ty(LLVMContext &C)
LLVM_ABI unsigned getPointerAddressSpace() const
Get the address space of this pointer or pointer vector type.
Type * getScalarType() const
If this is a vector type, return the element type, otherwise return 'this'.
LLVM_ABI Type * getWithNewBitWidth(unsigned NewBitWidth) const
Given an integer or vector type, change the lane bitwidth to NewBitwidth, whilst keeping the old numb...
LLVM_ABI unsigned getScalarSizeInBits() const LLVM_READONLY
If this is a vector type, return the getPrimitiveSizeInBits value for the element type.
bool isIntOrPtrTy() const
Return true if this is an integer type or a pointer type.
bool isIntegerTy() const
True if this is an instance of IntegerType.
static LLVM_ABI IntegerType * getIntNTy(LLVMContext &C, unsigned N)
BasicBlock * getSuccessor(unsigned i=0) const
static LLVM_ABI 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.
const Use & getOperandUse(unsigned i) const
void setOperand(unsigned i, Value *Val)
LLVM_ABI bool replaceUsesOfWith(Value *From, Value *To)
Replace uses of one Value with another.
Value * getOperand(unsigned i) const
unsigned getNumOperands() const
LLVM Value Representation.
Type * getType() const
All values are typed, get the type of this value.
user_iterator user_begin()
LLVM_ABI 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.
LLVM_ABI void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
LLVMContext & getContext() const
All values hold a context through their type.
iterator_range< user_iterator > users()
LLVM_ABI Align getPointerAlignment(const DataLayout &DL) const
Returns an alignment of the pointer value.
LLVM_ABI bool isUsedInBasicBlock(const BasicBlock *BB) const
Check if this value is used in the specified basic block.
LLVM_ABI void printAsOperand(raw_ostream &O, bool PrintType=true, const Module *M=nullptr) const
Print the name of this Value out to the specified raw_ostream.
LLVM_ABI const Value * stripPointerCasts() const
Strip off pointer casts, all-zero GEPs and address space casts.
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
LLVM_ABI StringRef getName() const
Return a constant reference to the value's name.
LLVM_ABI void takeName(Value *V)
Transfer the name from V to this value.
LLVM_ABI void dump() const
Support for debugging, callable in GDB: V->dump()
bool pointsToAliveValue() const
int getNumOccurrences() const
constexpr ScalarTy getFixedValue() const
constexpr bool isNonZero() const
constexpr bool isScalable() const
Returns whether the quantity is scaled by a runtime quantity (vscale).
StructType * getStructTypeOrNull() const
TypeSize getSequentialElementStride(const DataLayout &DL) const
const ParentTy * getParent() const
self_iterator getIterator()
NodeTy * getNextNode()
Get the next node, or nullptr for the list tail.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
constexpr char Align[]
Key for Kernel::Arg::Metadata::mAlign.
@ C
The default llvm calling convention, compatible with C.
unsigned getAddrMode(MCInstrInfo const &MCII, MCInst const &MCI)
@ BasicBlock
Various leaf nodes.
SpecificConstantMatch m_ZeroInt()
Convenience matchers for specific integer values.
OneUse_match< SubPat > m_OneUse(const SubPat &SP)
cst_pred_ty< is_all_ones > m_AllOnes()
Match an integer or vector with all bits set.
BinaryOp_match< LHS, RHS, Instruction::Add > m_Add(const LHS &L, const RHS &R)
class_match< BinaryOperator > m_BinOp()
Match an arbitrary binary operation and ignore it.
OverflowingBinaryOp_match< LHS, RHS, Instruction::Add, OverflowingBinaryOperator::NoUnsignedWrap > m_NUWAdd(const LHS &L, const RHS &R)
BinaryOp_match< LHS, RHS, Instruction::URem > m_URem(const LHS &L, const RHS &R)
class_match< Constant > m_Constant()
Match an arbitrary Constant and ignore it.
ap_match< APInt > m_APInt(const APInt *&Res)
Match a ConstantInt or splatted ConstantVector, binding the specified pointer to the contained APInt.
BinaryOp_match< LHS, RHS, Instruction::Xor > m_Xor(const LHS &L, const RHS &R)
ap_match< APInt > m_APIntAllowPoison(const APInt *&Res)
Match APInt while allowing poison in splat vector constants.
specific_intval< false > m_SpecificInt(const APInt &V)
Match a specific integer value or vector with all elements equal to the value.
bool match(Val *V, const Pattern &P)
bind_ty< Instruction > m_Instruction(Instruction *&I)
Match an instruction, capturing it if we match.
specificval_ty m_Specific(const Value *V)
Match if we have a specific specified value.
BinOpPred_match< LHS, RHS, is_right_shift_op > m_Shr(const LHS &L, const RHS &R)
Matches logical shift operations.
OverflowingBinaryOp_match< LHS, RHS, Instruction::Add, OverflowingBinaryOperator::NoUnsignedWrap, true > m_c_NUWAdd(const LHS &L, const RHS &R)
class_match< ConstantInt > m_ConstantInt()
Match an arbitrary ConstantInt and ignore it.
cst_pred_ty< is_one > m_One()
Match an integer 1 or a vector with all elements equal to 1.
IntrinsicID_match m_Intrinsic()
Match intrinsic calls like this: m_Intrinsic<Intrinsic::fabs>(m_Value(X))
ThreeOps_match< Cond, LHS, RHS, Instruction::Select > m_Select(const Cond &C, const LHS &L, const RHS &R)
Matches SelectInst.
ExtractValue_match< Ind, Val_t > m_ExtractValue(const Val_t &V)
Match a single index ExtractValue instruction.
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)
match_immconstant_ty m_ImmConstant()
Match an arbitrary immediate Constant and ignore it.
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
OverflowingBinaryOp_match< LHS, RHS, Instruction::Add, OverflowingBinaryOperator::NoSignedWrap > m_NSWAdd(const LHS &L, const RHS &R)
CmpClass_match< LHS, RHS, ICmpInst > m_ICmp(CmpPredicate &Pred, const LHS &L, const RHS &R)
BinaryOp_match< LHS, RHS, Instruction::Shl > m_Shl(const LHS &L, const RHS &R)
UAddWithOverflow_match< LHS_t, RHS_t, Sum_t > m_UAddWithOverflow(const LHS_t &L, const RHS_t &R, const Sum_t &S)
Match an icmp instruction checking for unsigned overflow on addition.
auto m_LogicalAnd()
Matches L && R where L and R are arbitrary values.
auto m_Undef()
Match an arbitrary undef constant.
BinaryOp_match< LHS, RHS, Instruction::Or, true > m_c_Or(const LHS &L, const RHS &R)
Matches an Or with LHS and RHS in either order.
ThreeOps_match< Val_t, Elt_t, Idx_t, Instruction::InsertElement > m_InsertElt(const Val_t &Val, const Elt_t &Elt, const Idx_t &Idx)
Matches InsertElementInst.
BinaryOp_match< LHS, RHS, Instruction::Sub > m_Sub(const LHS &L, const RHS &R)
match_combine_or< LTy, RTy > m_CombineOr(const LTy &L, const RTy &R)
Combine two pattern matchers matching L || R.
int compare(DigitsT LDigits, int16_t LScale, DigitsT RDigits, int16_t RScale)
Compare two scaled numbers.
@ CE
Windows NT (Windows on ARM)
initializer< Ty > init(const Ty &Val)
PointerTypeMap run(const Module &M)
Compute the PointerTypeMap for the module M.
@ Assume
Do not drop type tests (default).
@ User
could "use" a pointer
NodeAddr< PhiNode * > Phi
NodeAddr< UseNode * > Use
SmallVector< Node, 4 > NodeList
friend class Instruction
Iterator for Instructions in a `BasicBlock.
LLVM_ABI iterator begin() const
BaseReg
Stack frame base register. Bit 0 of FREInfo.Info.
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)
FunctionAddr VTableAddr Value
std::enable_if_t< std::is_signed_v< T >, T > MulOverflow(T X, T Y, T &Result)
Multiply two signed integers, computing the two's complement truncated result, returning true if an o...
auto find(R &&Range, const T &Val)
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly.
LLVM_ABI 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.
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.
LLVM_ABI 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.
LLVM_ABI 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...
LLVM_ABI void findDbgValues(Value *V, SmallVectorImpl< DbgVariableRecord * > &DbgVariableRecords)
Finds the dbg.values describing a value.
decltype(auto) dyn_cast(const From &Val)
dyn_cast<X> - Return the argument parameter cast to the specified type.
APInt operator*(APInt a, uint64_t RHS)
bool isAligned(Align Lhs, uint64_t SizeInBytes)
Checks that SizeInBytes is a multiple of the alignment.
LLVM_ABI 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)
OuterAnalysisManagerProxy< ModuleAnalysisManager, Function > ModuleAnalysisManagerFunctionProxy
Provide the ModuleAnalysisManager to Function proxy.
LLVM_ABI 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)
constexpr from_range_t from_range
LLVM_ABI BasicBlock * splitBlockBefore(BasicBlock *Old, BasicBlock::iterator SplitPt, DomTreeUpdater *DTU, LoopInfo *LI, MemorySSAUpdater *MSSAU, const Twine &BBName="")
Split the specified block at the specified instruction SplitPt.
LLVM_ABI 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.
LLVM_ABI bool SplitIndirectBrCriticalEdges(Function &F, bool IgnoreBlocksWithoutPHI, BranchProbabilityInfo *BPI=nullptr, BlockFrequencyInfo *BFI=nullptr, DomTreeUpdater *DTU=nullptr)
void append_range(Container &C, Range &&R)
Wrapper function to append range R to container C.
LLVM_ABI 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...
LLVM_ABI void DeleteDeadBlock(BasicBlock *BB, DomTreeUpdater *DTU=nullptr, bool KeepOneInputPHIs=false)
Delete the specified block, which must have no predecessors.
LLVM_ABI bool isSafeToSpeculativelyExecute(const Instruction *I, const Instruction *CtxI=nullptr, AssumptionCache *AC=nullptr, const DominatorTree *DT=nullptr, const TargetLibraryInfo *TLI=nullptr, bool UseVariableInfo=true, bool IgnoreUBImplyingAttrs=true)
Return true if the instruction does not have any effects besides calculating the result and does not ...
auto unique(Range &&R, Predicate P)
LLVM_ABI Value * getSplatValue(const Value *V)
Get splat value if the input is a splat vector or return nullptr.
LLVM_ABI bool hasBranchWeightOrigin(const Instruction &I)
Check if Branch Weight Metadata has an "expected" field from an llvm.expect* intrinsic.
constexpr auto equal_to(T &&Arg)
Functor variant of std::equal_to that can be used as a UnaryPredicate in functional algorithms like a...
bool operator==(const AddressRangeValuePair &LHS, const AddressRangeValuePair &RHS)
constexpr int popcount(T Value) noexcept
Count the number of set bits in a value.
LLVM_ABI Value * simplifyInstruction(Instruction *I, const SimplifyQuery &Q)
See if we can compute a simplified version of this instruction.
LLVM_ABI Value * simplifyAddInst(Value *LHS, Value *RHS, bool IsNSW, bool IsNUW, const SimplifyQuery &Q)
Given operands for an Add, fold the result or return null.
auto dyn_cast_or_null(const Y &Val)
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.
LLVM_ABI 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...
LLVM_ABI 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.
LLVM_ABI 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)
LLVM_ABI bool recognizeBSwapOrBitReverseIdiom(Instruction *I, bool MatchBSwaps, bool MatchBitReversals, SmallVectorImpl< Instruction * > &InsertedInsts)
Try to match a bswap or bitreverse idiom.
void sort(IteratorTy Start, IteratorTy End)
FPClassTest
Floating-point class tests, supported by 'is_fpclass' intrinsic.
LLVM_ABI 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...
LLVM_ABI 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.
auto make_first_range(ContainerTy &&c)
Given a container of pairs, return a range over the first elements.
generic_gep_type_iterator<> gep_type_iterator
LLVM_ABI FunctionPass * createCodeGenPrepareLegacyPass()
createCodeGenPrepareLegacyPass - Transform the code to expose more pattern matching during instructio...
ISD::CondCode getFCmpCondCode(FCmpInst::Predicate Pred)
getFCmpCondCode - Return the ISD condition code corresponding to the given LLVM IR floating-point con...
LLVM_ABI bool VerifyLoopInfo
Enable verification of loop info.
class LLVM_GSL_OWNER SmallVector
Forward declaration of SmallVector so that calculateSmallVectorDefaultInlinedElements can reference s...
bool isa(const From &Val)
isa<X> - Return true if the parameter to the template is an instance of one of the template type argu...
LLVM_ATTRIBUTE_VISIBILITY_DEFAULT AnalysisKey InnerAnalysisManagerProxy< AnalysisManagerT, IRUnitT, ExtraArgTs... >::Key
LLVM_ABI bool isKnownNonZero(const Value *V, const SimplifyQuery &Q, unsigned Depth=0)
Return true if the given value is known to be non-zero when defined.
@ First
Helpers to iterate all locations in the MemoryEffectsBase class.
bool attributesPermitTailCall(const Function *F, const Instruction *I, const ReturnInst *Ret, const TargetLoweringBase &TLI, bool *AllowDifferingSizes=nullptr)
Test if given that the input instruction is in the tail call position, if there is an attribute misma...
IRBuilder(LLVMContext &, FolderTy, InserterTy, MDNode *, ArrayRef< OperandBundleDef >) -> IRBuilder< FolderTy, InserterTy >
LLVM_ABI 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.
@ Or
Bitwise or logical OR of integers.
@ Xor
Bitwise or logical XOR of integers.
@ And
Bitwise or logical AND of integers.
@ Sub
Subtraction of integers.
LLVM_ABI BasicBlock * SplitBlock(BasicBlock *Old, BasicBlock::iterator SplitPt, DominatorTree *DT, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, const Twine &BBName="")
Split the specified block at the specified instruction.
FunctionAddr VTableAddr Next
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...
DWARFExpression::Operation Op
bool bypassSlowDivision(BasicBlock *BB, const DenseMap< unsigned int, unsigned int > &BypassWidth, DomTreeUpdater *DTU=nullptr, LoopInfo *LI=nullptr)
This optimization identifies DIV instructions in a BB that can be profitably bypassed and carried out...
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
LLVM_ABI 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.
ArrayRef(const T &OneElt) -> ArrayRef< T >
LLVM_ABI bool VerifyDomInfo
Enables verification of dominator trees.
constexpr unsigned BitWidth
LLVM_ABI bool extractBranchWeights(const MDNode *ProfileData, SmallVectorImpl< uint32_t > &Weights)
Extract branch weights from MD_prof metadata.
decltype(auto) cast(const From &Val)
cast<X> - Return the argument parameter cast to the specified type.
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)
std::enable_if_t< std::is_signed_v< T >, T > AddOverflow(T X, T Y, T &Result)
Add two signed integers, computing the two's complement truncated result, returning true if overflow ...
LLVM_ABI 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 ...
AnalysisManager< Function > FunctionAnalysisManager
Convenience typedef for the Function analysis manager.
LLVM_ABI 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...
std::pair< Value *, FPClassTest > fcmpToClassTest(FCmpInst::Predicate Pred, const Function &F, Value *LHS, Value *RHS, bool LookThroughSrc=true)
Returns a pair of values, which if passed to llvm.is.fpclass, returns the same result as an fcmp with...
static auto filterDbgVars(iterator_range< simple_ilist< DbgRecord >::iterator > R)
Filter the DbgRecord range to DbgVariableRecord types only and downcast.
LLVM_ABI Value * simplifyURemInst(Value *LHS, Value *RHS, const SimplifyQuery &Q)
Given operands for a URem, fold the result or return null.
DenseMap< const Value *, Value * > ValueToValueMap
LLVM_ABI 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 LLVM_ABI EVT getEVT(Type *Ty, bool HandleUnknown=false)
Return the value type corresponding to the specified type.
MVT getSimpleVT() const
Return the SimpleValueType held in the specified simple EVT.
bool isRound() const
Return true if the size is a power-of-two number of bytes.
bool isInteger() const
Return true if this is an integer or a vector integer type.
This contains information for each constraint that we are lowering.