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();
575 "analysis to be available");
576 BBSectionsProfileReader =
579 DomTreeUpdater::UpdateStrategy::Lazy);
585 bool EverMadeChange =
false;
587 OptSize =
F.hasOptSize();
592 (void)
F.setSectionPrefix(
"hot");
597 if (
F.hasFnAttribute(Attribute::Hot) ||
598 PSI->isFunctionHotInCallGraph(&
F, *BFI))
599 (void)
F.setSectionPrefix(
"hot");
603 else if (PSI->isFunctionColdInCallGraph(&
F, *BFI) ||
604 F.hasFnAttribute(Attribute::Cold))
605 (void)
F.setSectionPrefix(
"unlikely");
607 PSI->isFunctionHotnessUnknown(
F))
608 (void)
F.setSectionPrefix(
"unknown");
614 const DenseMap<unsigned int, unsigned int> &BypassWidths =
617 while (BB !=
nullptr) {
630 EverMadeChange |= eliminateAssumptions(
F);
632 auto resetLoopInfo = [
this]() {
639 bool ResetLI =
false;
640 EverMadeChange |= eliminateMostlyEmptyBlocks(
F, ResetLI);
645 EverMadeChange |= splitBranchCondition(
F);
651 EverMadeChange |=
Split;
657 assert(getDT().
verify(DominatorTree::VerificationLevel::Fast) &&
658 "Incorrect DominatorTree updates in CGP");
668 bool MadeChange =
true;
669 bool FuncIterated =
false;
679 if (FuncIterated && !FreshBBs.
contains(&BB))
682 ModifyDT ModifiedDTOnIteration = ModifyDT::NotModifyDT;
698 else if (FuncIterated)
703 if (ModifiedDTOnIteration != ModifyDT::NotModifyDT)
708 FuncIterated = IsHugeFunc;
711 MadeChange |= mergeSExts(
F);
712 if (!LargeOffsetGEPMap.
empty())
713 MadeChange |= splitLargeGEPOffsets();
714 MadeChange |= optimizePhiTypes(
F);
717 eliminateFallThrough(
F);
721 assert(getDT().
verify(DominatorTree::VerificationLevel::Fast) &&
722 "Incorrect DominatorTree updates in CGP");
729 for (Instruction *
I : RemovedInsts)
732 EverMadeChange |= MadeChange;
733 SeenChainsForSExt.
clear();
734 ValToSExtendedUses.clear();
735 RemovedInsts.clear();
736 LargeOffsetGEPMap.
clear();
737 LargeOffsetGEPID.
clear();
751 SmallSetVector<BasicBlock *, 8> WorkList;
752 for (BasicBlock &BB :
F) {
758 for (BasicBlock *Succ : Successors)
764 MadeChange |= !WorkList.
empty();
765 while (!WorkList.
empty()) {
771 for (BasicBlock *Succ : Successors)
781 if (EverMadeChange || MadeChange)
782 MadeChange |= eliminateFallThrough(
F);
784 EverMadeChange |= MadeChange;
789 for (BasicBlock &BB :
F)
790 for (Instruction &
I : BB)
793 for (
auto &
I : Statepoints)
794 EverMadeChange |= simplifyOffsetableRelocate(*
I);
799 EverMadeChange |= placeDbgValues(
F);
800 EverMadeChange |= placePseudoProbes(
F);
807 return EverMadeChange;
810bool CodeGenPrepare::eliminateAssumptions(Function &
F) {
811 bool MadeChange =
false;
812 for (BasicBlock &BB :
F) {
813 CurInstIterator = BB.begin();
814 while (CurInstIterator != BB.end()) {
819 Assume->eraseFromParent();
821 resetIteratorIfInvalidatedWhileCalling(&BB, [&]() {
832void CodeGenPrepare::removeAllAssertingVHReferences(
Value *V) {
833 LargeOffsetGEPMap.
erase(V);
834 NewGEPBases.
erase(V);
842 auto VecI = LargeOffsetGEPMap.
find(
GEP->getPointerOperand());
843 if (VecI == LargeOffsetGEPMap.
end())
846 auto &GEPVector = VecI->second;
849 if (GEPVector.empty())
850 LargeOffsetGEPMap.
erase(VecI);
854[[maybe_unused]]
void CodeGenPrepare::verifyBFIUpdates(Function &
F) {
855 DominatorTree NewDT(
F);
856 LoopInfo NewLI(NewDT);
857 BranchProbabilityInfo NewBPI(
F, NewLI, TLInfo);
858 BlockFrequencyInfo NewBFI(
F, NewBPI, NewLI);
859 NewBFI.verifyMatch(*BFI);
865bool CodeGenPrepare::eliminateFallThrough(Function &
F) {
867 SmallPtrSet<BasicBlock *, 8> Preds;
875 BasicBlock *SinglePred = BB->getSinglePredecessor();
878 if (!SinglePred || SinglePred == BB || BB->hasAddressTaken())
891 FreshBBs.
insert(SinglePred);
899 for (
auto *Pred : Preds)
907BasicBlock *CodeGenPrepare::findDestBlockOfMergeableEmptyBlock(BasicBlock *BB) {
916 if (BBI != BB->
begin()) {
927 if (!canMergeBlocks(BB, DestBB))
937bool CodeGenPrepare::eliminateMostlyEmptyBlocks(Function &
F,
bool &ResetLI) {
938 SmallPtrSet<BasicBlock *, 16> Preheaders;
940 while (!LoopList.empty()) {
941 Loop *
L = LoopList.pop_back_val();
943 if (BasicBlock *Preheader =
L->getLoopPreheader())
944 Preheaders.
insert(Preheader);
948 bool MadeChange =
false;
949 SmallPtrSet<PHINode *, 32> KnownNonDeadPHIs;
961 BasicBlock *DestBB = findDestBlockOfMergeableEmptyBlock(BB);
963 !isMergingEmptyBlockProfitable(BB, DestBB, Preheaders.
count(BB)))
966 ResetLI |= eliminateMostlyEmptyBlock(BB);
972bool CodeGenPrepare::isMergingEmptyBlockProfitable(BasicBlock *BB,
1023 SmallPtrSet<BasicBlock *, 16> SameIncomingValueBBs;
1028 if (DestBBPred == BB)
1032 return DestPN.getIncomingValueForBlock(BB) ==
1033 DestPN.getIncomingValueForBlock(DestBBPred);
1035 SameIncomingValueBBs.
insert(DestBBPred);
1041 if (SameIncomingValueBBs.
count(Pred))
1044 BlockFrequency PredFreq = BFI->getBlockFreq(Pred);
1045 BlockFrequency
BBFreq = BFI->getBlockFreq(BB);
1047 for (
auto *SameValueBB : SameIncomingValueBBs)
1048 if (SameValueBB->getUniquePredecessor() == Pred &&
1049 DestBB == findDestBlockOfMergeableEmptyBlock(SameValueBB))
1050 BBFreq += BFI->getBlockFreq(SameValueBB);
1053 return !Limit || PredFreq <= *Limit;
1059bool CodeGenPrepare::canMergeBlocks(
const BasicBlock *BB,
1060 const BasicBlock *DestBB)
const {
1064 for (
const PHINode &PN : BB->
phis()) {
1065 for (
const User *U : PN.users()) {
1074 for (
unsigned I = 0,
E = UPN->getNumIncomingValues();
I !=
E; ++
I) {
1077 Insn->
getParent() != UPN->getIncomingBlock(
I))
1092 SmallPtrSet<const BasicBlock *, 16> BBPreds;
1095 for (
unsigned i = 0, e = BBPN->getNumIncomingValues(); i != e; ++i)
1096 BBPreds.
insert(BBPN->getIncomingBlock(i));
1104 if (BBPreds.
count(Pred)) {
1105 for (
const PHINode &PN : DestBB->
phis()) {
1106 const Value *
V1 = PN.getIncomingValueForBlock(Pred);
1107 const Value *V2 = PN.getIncomingValueForBlock(BB);
1111 if (V2PN->getParent() == BB)
1112 V2 = V2PN->getIncomingValueForBlock(Pred);
1143bool CodeGenPrepare::eliminateMostlyEmptyBlock(BasicBlock *BB) {
1153 if (SinglePred != DestBB) {
1154 assert(SinglePred == BB &&
1155 "Single predecessor not the same as predecessor");
1164 FreshBBs.
insert(SinglePred);
1165 FreshBBs.
erase(DestBB);
1173 for (PHINode &PN : DestBB->
phis()) {
1175 Value *InVal = PN.removeIncomingValue(BB,
false);
1180 if (InValPhi && InValPhi->
getParent() == BB) {
1189 for (
unsigned i = 0, e = BBPN->getNumIncomingValues(); i != e; ++i)
1190 PN.addIncoming(InVal, BBPN->getIncomingBlock(i));
1193 PN.addIncoming(InVal, Pred);
1199 if (BI->hasMetadata(LLVMContext::MD_loop)) {
1207 SmallPtrSet<BasicBlock *, 8> SeenPreds;
1211 if (!PredOfDestBB.contains(Pred)) {
1212 if (SeenPreds.
insert(Pred).second)
1213 DTUpdates.
push_back({DominatorTree::Insert, Pred, DestBB});
1218 if (SeenPreds.
insert(Pred).second)
1219 DTUpdates.
push_back({DominatorTree::Delete, Pred, BB});
1221 DTUpdates.
push_back({DominatorTree::Delete, BB, DestBB});
1241 for (
auto *ThisRelocate : AllRelocateCalls) {
1242 auto K = std::make_pair(ThisRelocate->getBasePtrIndex(),
1243 ThisRelocate->getDerivedPtrIndex());
1244 RelocateIdxMap.
insert(std::make_pair(K, ThisRelocate));
1246 for (
auto &Item : RelocateIdxMap) {
1247 std::pair<unsigned, unsigned>
Key = Item.first;
1248 if (
Key.first ==
Key.second)
1253 auto BaseKey = std::make_pair(
Key.first,
Key.first);
1256 auto MaybeBase = RelocateIdxMap.
find(BaseKey);
1257 if (MaybeBase == RelocateIdxMap.
end())
1262 RelocateInstMap[MaybeBase->second].push_back(
I);
1270 for (
unsigned i = 1; i <
GEP->getNumOperands(); i++) {
1273 if (!
Op ||
Op->getZExtValue() > 20)
1277 for (
unsigned i = 1; i <
GEP->getNumOperands(); i++)
1287 bool MadeChange =
false;
1294 for (
auto R = RelocatedBase->
getParent()->getFirstInsertionPt();
1295 &*R != RelocatedBase; ++R)
1299 RelocatedBase->
moveBefore(RI->getIterator());
1306 "Not relocating a derived object of the original base object");
1307 if (ToReplace->getBasePtrIndex() == ToReplace->getDerivedPtrIndex()) {
1312 if (RelocatedBase->
getParent() != ToReplace->getParent()) {
1322 if (!Derived || Derived->getPointerOperand() !=
Base)
1331 "Should always have one since it's not a terminator");
1335 Builder.SetCurrentDebugLocation(ToReplace->getDebugLoc());
1359 Value *ActualRelocatedBase = RelocatedBase;
1360 if (RelocatedBase->
getType() !=
Base->getType()) {
1361 ActualRelocatedBase =
1362 Builder.CreateBitCast(RelocatedBase,
Base->getType());
1364 Value *Replacement =
1365 Builder.CreateGEP(Derived->getSourceElementType(), ActualRelocatedBase,
1371 Value *ActualReplacement = Replacement;
1372 if (Replacement->
getType() != ToReplace->getType()) {
1374 Builder.CreateBitCast(Replacement, ToReplace->
getType());
1377 ToReplace->eraseFromParent();
1401bool CodeGenPrepare::simplifyOffsetableRelocate(GCStatepointInst &
I) {
1402 bool MadeChange =
false;
1404 for (
auto *U :
I.users())
1411 if (AllRelocateCalls.
size() < 2)
1416 MapVector<GCRelocateInst *, SmallVector<GCRelocateInst *, 0>> RelocateInstMap;
1418 if (RelocateInstMap.
empty())
1421 for (
auto &Item : RelocateInstMap)
1435 bool MadeChange =
false;
1438 Use &TheUse = UI.getUse();
1445 UserBB = PN->getIncomingBlock(TheUse);
1453 if (
User->isEHPad())
1463 if (UserBB == DefBB)
1467 CastInst *&InsertedCast = InsertedCasts[UserBB];
1469 if (!InsertedCast) {
1477 TheUse = InsertedCast;
1503 ASC->getDestAddressSpace()))
1558static std::optional<std::pair<Instruction *, Constant *>>
1561 if (!L || L->getHeader() != PN->
getParent() || !L->getLoopLatch())
1562 return std::nullopt;
1565 if (!IVInc || LI->
getLoopFor(IVInc->getParent()) != L)
1566 return std::nullopt;
1570 return std::make_pair(IVInc, Step);
1571 return std::nullopt;
1584 return IVInc->first ==
I;
1588bool CodeGenPrepare::replaceMathCmpWithIntrinsic(BinaryOperator *BO,
1592 auto IsReplacableIVIncrement = [
this, &
Cmp](BinaryOperator *BO) {
1595 const Loop *
L = LI->getLoopFor(BO->
getParent());
1596 assert(L &&
"L should not be null after isIVIncrement()");
1598 if (LI->getLoopFor(
Cmp->getParent()) != L)
1611 return BO->
hasOneUse() && DT.dominates(
Cmp->getParent(),
L->getLoopLatch());
1613 if (BO->
getParent() !=
Cmp->getParent() && !IsReplacableIVIncrement(BO)) {
1636 if (BO->
getOpcode() == Instruction::Add &&
1637 IID == Intrinsic::usub_with_overflow) {
1644 for (Instruction &Iter : *
Cmp->getParent()) {
1647 if ((BO->
getOpcode() != Instruction::Xor && &Iter == BO) || &Iter == Cmp) {
1652 assert(InsertPt !=
nullptr &&
"Parent block did not contain cmp or binop");
1655 Value *MathOV = Builder.CreateBinaryIntrinsic(IID, Arg0, Arg1);
1656 if (BO->
getOpcode() != Instruction::Xor) {
1657 Value *Math = Builder.CreateExtractValue(MathOV, 0,
"math");
1661 "Patterns with XOr should use the BO only in the compare");
1662 Value *OV = Builder.CreateExtractValue(MathOV, 1,
"ov");
1664 Cmp->eraseFromParent();
1674 Value *
A = Cmp->getOperand(0), *
B = Cmp->getOperand(1);
1682 B = ConstantInt::get(
B->getType(), 1);
1690 for (
User *U :
A->users()) {
1701bool CodeGenPrepare::combineToUAddWithOverflow(CmpInst *Cmp,
1702 ModifyDT &ModifiedDT) {
1703 bool EdgeCase =
false;
1705 BinaryOperator *
Add;
1710 A =
Add->getOperand(0);
1711 B =
Add->getOperand(1);
1717 Add->hasNUsesOrMore(EdgeCase ? 1 : 2)))
1723 if (
Add->getParent() !=
Cmp->getParent() && !
Add->hasOneUse())
1726 if (!replaceMathCmpWithIntrinsic(
Add,
A,
B, Cmp,
1727 Intrinsic::uadd_with_overflow))
1731 ModifiedDT = ModifyDT::ModifyInstDT;
1735bool CodeGenPrepare::combineToUSubWithOverflow(CmpInst *Cmp,
1736 ModifyDT &ModifiedDT) {
1743 ICmpInst::Predicate Pred =
Cmp->getPredicate();
1744 if (Pred == ICmpInst::ICMP_UGT) {
1746 Pred = ICmpInst::ICMP_ULT;
1750 B = ConstantInt::get(
B->getType(), 1);
1751 Pred = ICmpInst::ICMP_ULT;
1756 Pred = ICmpInst::ICMP_ULT;
1758 if (Pred != ICmpInst::ICMP_ULT)
1765 BinaryOperator *
Sub =
nullptr;
1766 for (User *U : CmpVariableOperand->
users()) {
1774 const APInt *CmpC, *AddC;
1786 Sub->hasNUsesOrMore(1)))
1792 if (
Sub->getParent() !=
Cmp->getParent() && !
Sub->hasOneUse())
1795 if (!replaceMathCmpWithIntrinsic(
Sub,
Sub->getOperand(0),
Sub->getOperand(1),
1796 Cmp, Intrinsic::usub_with_overflow))
1800 ModifiedDT = ModifyDT::ModifyInstDT;
1807bool CodeGenPrepare::unfoldPowerOf2Test(CmpInst *Cmp) {
1820 if (!IsStrictlyPowerOf2Test && !IsPowerOf2OrZeroTest)
1826 Type *OpTy =
X->getType();
1834 if (Pred == ICmpInst::ICMP_EQ) {
1835 Cmp->setOperand(1, ConstantInt::get(OpTy, 2));
1836 Cmp->setPredicate(ICmpInst::ICMP_ULT);
1838 Cmp->setPredicate(ICmpInst::ICMP_UGT);
1844 if (IsPowerOf2OrZeroTest ||
1855 NewCmp = Builder.CreateICmp(NewPred,
And, ConstantInt::getNullValue(OpTy));
1864 NewCmp = Builder.CreateICmp(NewPred,
Xor,
Sub);
1867 Cmp->replaceAllUsesWith(NewCmp);
1887 bool UsedInPhiOrCurrentBlock =
any_of(Cmp->users(), [Cmp](
User *U) {
1888 return isa<PHINode>(U) ||
1889 cast<Instruction>(U)->getParent() == Cmp->getParent();
1894 if (UsedInPhiOrCurrentBlock && Cmp->getOperand(0)->getType()->isIntegerTy() &&
1895 Cmp->getOperand(0)->getType()->getScalarSizeInBits() >
1896 DL.getLargestLegalIntTypeSizeInBits())
1902 bool MadeChange =
false;
1905 Use &TheUse = UI.getUse();
1920 if (UserBB == DefBB)
1924 CmpInst *&InsertedCmp = InsertedCmps[UserBB];
1930 Cmp->getOperand(0), Cmp->getOperand(1),
"");
1937 TheUse = InsertedCmp;
1943 if (Cmp->use_empty()) {
1944 Cmp->eraseFromParent();
1981 for (
User *U : Cmp->users()) {
2003 if (CmpBB != FalseBB)
2006 Value *CmpOp0 = Cmp->getOperand(0), *CmpOp1 = Cmp->getOperand(1);
2020 for (
User *U : Cmp->users()) {
2022 BI->swapSuccessors();
2028 SI->swapProfMetadata();
2040 Value *Op0 = Cmp->getOperand(0);
2041 Value *Op1 = Cmp->getOperand(1);
2050 unsigned NumInspected = 0;
2053 if (++NumInspected > 128)
2061 if (GoodToSwap > 0) {
2062 Cmp->swapOperands();
2082 auto ShouldReverseTransform = [](
FPClassTest ClassTest) {
2085 auto [ClassVal, ClassTest] =
2091 if (!ShouldReverseTransform(ClassTest) && !ShouldReverseTransform(~ClassTest))
2095 Value *IsFPClass = Builder.createIsFPClass(ClassVal, ClassTest);
2096 Cmp->replaceAllUsesWith(IsFPClass);
2104 Value *Incr, *RemAmt;
2109 Value *AddInst, *AddOffset;
2112 if (PN !=
nullptr) {
2114 AddOffset =
nullptr;
2132 if (!L || !L->getLoopPreheader() || !L->getLoopLatch())
2136 if (!L->contains(Rem))
2140 if (!L->isLoopInvariant(RemAmt))
2144 if (AddOffset && !L->isLoopInvariant(AddOffset))
2165 AddInstOut = AddInst;
2166 AddOffsetOut = AddOffset;
2185 Value *AddOffset, *RemAmt, *AddInst;
2188 AddOffset, LoopIncrPN))
2213 assert(AddOffset &&
"We found an add but missing values");
2232 Builder.SetInsertPoint(LoopIncrPN);
2233 PHINode *NewRem = Builder.CreatePHI(Ty, 2);
2238 Value *RemAdd = Builder.CreateNUWAdd(NewRem, ConstantInt::get(Ty, 1));
2243 NewRem->
addIncoming(Start, L->getLoopPreheader());
2248 FreshBBs.
insert(L->getLoopLatch());
2259bool CodeGenPrepare::optimizeURem(Instruction *Rem) {
2265bool CodeGenPrepare::optimizeCmp(CmpInst *Cmp, ModifyDT &ModifiedDT) {
2269 if (combineToUAddWithOverflow(Cmp, ModifiedDT))
2272 if (combineToUSubWithOverflow(Cmp, ModifiedDT))
2275 if (unfoldPowerOf2Test(Cmp))
2296 SetOfInstrs &InsertedInsts) {
2299 assert(!InsertedInsts.count(AndI) &&
2300 "Attempting to optimize already optimized and instruction");
2301 (void)InsertedInsts;
2315 for (
auto *U : AndI->
users()) {
2323 if (!CmpC || !CmpC->
isZero())
2338 Use &TheUse = UI.getUse();
2356 TheUse = InsertedAnd;
2373 if (
User->getOpcode() != Instruction::And ||
2379 if ((Cimm & (Cimm + 1)).getBoolValue())
2393 bool MadeChange =
false;
2396 TruncE = TruncI->user_end();
2397 TruncUI != TruncE;) {
2399 Use &TruncTheUse = TruncUI.getUse();
2424 if (UserBB == TruncUserBB)
2428 CastInst *&InsertedTrunc = InsertedTruncs[TruncUserBB];
2430 if (!InsertedShift && !InsertedTrunc) {
2434 if (ShiftI->
getOpcode() == Instruction::AShr)
2436 BinaryOperator::CreateAShr(ShiftI->
getOperand(0), CI,
"");
2439 BinaryOperator::CreateLShr(ShiftI->
getOperand(0), CI,
"");
2447 TruncInsertPt.setHeadBit(
true);
2448 assert(TruncInsertPt != TruncUserBB->
end());
2452 InsertedTrunc->
insertBefore(*TruncUserBB, TruncInsertPt);
2453 InsertedTrunc->
setDebugLoc(TruncI->getDebugLoc());
2457 TruncTheUse = InsertedTrunc;
2490 bool MadeChange =
false;
2493 Use &TheUse = UI.getUse();
2507 if (UserBB == DefBB) {
2535 if (!InsertedShift) {
2539 if (ShiftI->
getOpcode() == Instruction::AShr)
2541 BinaryOperator::CreateAShr(ShiftI->
getOperand(0), CI,
"");
2544 BinaryOperator::CreateLShr(ShiftI->
getOperand(0), CI,
"");
2552 TheUse = InsertedShift;
2600 unsigned SizeInBits = Ty->getScalarSizeInBits();
2601 if (Ty->isVectorTy())
2612 nullptr,
"cond.false");
2614 FreshBBs.
insert(CallBlock);
2621 SplitPt.setHeadBit(
true);
2623 nullptr,
"cond.end");
2625 FreshBBs.
insert(EndBlock);
2630 Builder.SetCurrentDebugLocation(CountZeros->
getDebugLoc());
2637 Op = Builder.CreateFreeze(
Op,
Op->getName() +
".fr");
2638 Value *Cmp = Builder.CreateICmpEQ(
Op, Zero,
"cmpz");
2639 Builder.CreateCondBr(Cmp, EndBlock, CallBlock);
2645 Builder.SetInsertPoint(EndBlock, EndBlock->
begin());
2646 PHINode *PN = Builder.CreatePHI(Ty, 2,
"ctz");
2656 ModifiedDT = ModifyDT::ModifyBBDT;
2660bool CodeGenPrepare::optimizeCallInst(CallInst *CI, ModifyDT &ModifiedDT) {
2664 if (CI->
isInlineAsm() && optimizeInlineAsmInst(CI))
2672 for (
auto &Arg : CI->
args()) {
2677 if (!Arg->getType()->isPointerTy())
2679 APInt
Offset(
DL->getIndexSizeInBits(
2682 Value *Val = Arg->stripAndAccumulateInBoundsConstantOffsets(*
DL,
Offset);
2683 uint64_t Offset2 =
Offset.getLimitedValue();
2689 if (AllocaSize && AllocaSize->getKnownMinValue() >= MinSize + Offset2)
2707 MaybeAlign MIDestAlign =
MI->getDestAlign();
2708 if (!MIDestAlign || DestAlign > *MIDestAlign)
2709 MI->setDestAlignment(DestAlign);
2711 MaybeAlign MTISrcAlign = MTI->getSourceAlign();
2713 if (!MTISrcAlign || SrcAlign > *MTISrcAlign)
2714 MTI->setSourceAlignment(SrcAlign);
2724 for (
auto &Arg : CI->
args()) {
2725 if (!Arg->getType()->isPointerTy())
2727 unsigned AS = Arg->getType()->getPointerAddressSpace();
2728 if (optimizeMemoryInst(CI, Arg, Arg->getType(), AS))
2734 switch (
II->getIntrinsicID()) {
2737 case Intrinsic::assume:
2739 case Intrinsic::allow_runtime_check:
2740 case Intrinsic::allow_ubsan_check:
2741 case Intrinsic::experimental_widenable_condition: {
2745 if (
II->use_empty()) {
2746 II->eraseFromParent();
2750 resetIteratorIfInvalidatedWhileCalling(BB, [&]() {
2755 case Intrinsic::objectsize:
2757 case Intrinsic::is_constant:
2759 case Intrinsic::aarch64_stlxr:
2760 case Intrinsic::aarch64_stxr: {
2769 InsertedInsts.insert(ExtVal);
2773 case Intrinsic::launder_invariant_group:
2774 case Intrinsic::strip_invariant_group: {
2775 Value *ArgVal =
II->getArgOperand(0);
2776 auto it = LargeOffsetGEPMap.
find(
II);
2777 if (it != LargeOffsetGEPMap.
end()) {
2781 auto GEPs = std::move(it->second);
2782 LargeOffsetGEPMap[ArgVal].append(GEPs.begin(), GEPs.end());
2787 II->eraseFromParent();
2790 case Intrinsic::cttz:
2791 case Intrinsic::ctlz:
2795 case Intrinsic::fshl:
2796 case Intrinsic::fshr:
2797 return optimizeFunnelShift(
II);
2798 case Intrinsic::masked_gather:
2799 return optimizeGatherScatterInst(
II,
II->getArgOperand(0));
2800 case Intrinsic::masked_scatter:
2801 return optimizeGatherScatterInst(
II,
II->getArgOperand(1));
2802 case Intrinsic::masked_load:
2805 if (VT->getNumElements() == 1) {
2806 Value *PtrVal =
II->getArgOperand(0);
2808 if (optimizeMemoryInst(
II, PtrVal, VT->getElementType(), AS))
2813 case Intrinsic::masked_store:
2817 if (VT->getNumElements() == 1) {
2818 Value *PtrVal =
II->getArgOperand(1);
2820 if (optimizeMemoryInst(
II, PtrVal, VT->getElementType(), AS))
2825 case Intrinsic::umul_with_overflow:
2826 return optimizeMulWithOverflow(
II,
false, ModifiedDT);
2827 case Intrinsic::smul_with_overflow:
2828 return optimizeMulWithOverflow(
II,
true, ModifiedDT);
2831 SmallVector<Value *, 2> PtrOps;
2834 while (!PtrOps.
empty()) {
2837 if (optimizeMemoryInst(
II, PtrVal, AccessTy, AS))
2851 FortifiedLibCallSimplifier Simplifier(TLInfo,
true);
2853 if (
Value *V = Simplifier.optimizeCall(CI, Builder)) {
2863 auto GetUniformReturnValue = [](
const Function *
F) -> GlobalVariable * {
2864 if (!
F->getReturnType()->isPointerTy())
2867 GlobalVariable *UniformValue =
nullptr;
2868 for (
auto &BB : *
F) {
2873 else if (V != UniformValue)
2881 return UniformValue;
2884 if (
Callee->hasExactDefinition()) {
2885 if (GlobalVariable *RV = GetUniformReturnValue(Callee)) {
2886 bool MadeChange =
false;
2912 switch (
II->getIntrinsicID()) {
2913 case Intrinsic::memset:
2914 case Intrinsic::memcpy:
2915 case Intrinsic::memmove:
2923 if (Callee && TLInfo && TLInfo->
getLibFunc(*Callee, LF))
2925 case LibFunc_strcpy:
2926 case LibFunc_strncpy:
2927 case LibFunc_strcat:
2928 case LibFunc_strncat:
2969bool CodeGenPrepare::dupRetToEnableTailCallOpts(BasicBlock *BB,
2970 ModifyDT &ModifiedDT) {
2978 assert(LI->getLoopFor(BB) ==
nullptr &&
"A return block cannot be in a loop");
2980 PHINode *PN =
nullptr;
2981 ExtractValueInst *EVI =
nullptr;
2982 BitCastInst *BCI =
nullptr;
3002 auto isLifetimeEndOrBitCastFor = [](
const Instruction *Inst) {
3008 return II->getIntrinsicID() == Intrinsic::lifetime_end;
3014 auto isFakeUse = [&FakeUses](
const Instruction *Inst) {
3016 II &&
II->getIntrinsicID() == Intrinsic::fake_use) {
3038 isLifetimeEndOrBitCastFor(&*BI) || isFakeUse(&*BI))
3045 auto MayBePermittedAsTailCall = [&](
const auto *CI) {
3062 MayBePermittedAsTailCall(CI)) {
3083 MayBePermittedAsTailCall(CI)) {
3090 SmallPtrSet<BasicBlock *, 4> VisitedBBs;
3092 if (!VisitedBBs.
insert(Pred).second)
3094 if (Instruction *
I = Pred->rbegin()->getPrevNode()) {
3096 if (CI && CI->
use_empty() && MayBePermittedAsTailCall(CI)) {
3111 for (
auto const &TailCallBB : TailCallBBs) {
3121 BFI->getBlockFreq(BB) >= BFI->getBlockFreq(TailCallBB));
3122 BFI->setBlockFreq(BB,
3123 (BFI->getBlockFreq(BB) - BFI->getBlockFreq(TailCallBB)));
3124 ModifiedDT = ModifyDT::ModifyBBDT;
3133 for (
auto *CI : CallInsts) {
3134 for (
auto const *FakeUse : FakeUses) {
3135 auto *ClonedInst = FakeUse->clone();
3153struct ExtAddrMode :
public TargetLowering::AddrMode {
3154 Value *BaseReg =
nullptr;
3155 Value *ScaledReg =
nullptr;
3156 Value *OriginalValue =
nullptr;
3157 bool InBounds =
true;
3161 BaseRegField = 0x01,
3163 BaseOffsField = 0x04,
3164 ScaledRegField = 0x08,
3166 MultipleFields = 0xff
3169 ExtAddrMode() =
default;
3171 void print(raw_ostream &OS)
const;
3178 if (ScaledReg == From)
3182 FieldName
compare(
const ExtAddrMode &other) {
3185 if (BaseReg && other.
BaseReg &&
3187 return MultipleFields;
3188 if (BaseGV && other.BaseGV && BaseGV->getType() != other.BaseGV->getType())
3189 return MultipleFields;
3192 return MultipleFields;
3195 if (InBounds != other.InBounds)
3196 return MultipleFields;
3199 unsigned Result = NoField;
3202 if (BaseGV != other.BaseGV)
3204 if (BaseOffs != other.BaseOffs)
3207 Result |= ScaledRegField;
3210 if (Scale && other.
Scale && Scale != other.
Scale)
3214 return MultipleFields;
3216 return static_cast<FieldName
>(
Result);
3226 return !BaseOffs && !Scale && !(BaseGV &&
BaseReg);
3237 case ScaledRegField:
3244 void SetCombinedField(FieldName
Field,
Value *V,
3245 const SmallVectorImpl<ExtAddrMode> &AddrModes) {
3250 case ExtAddrMode::BaseRegField:
3253 case ExtAddrMode::BaseGVField:
3256 assert(BaseReg ==
nullptr);
3260 case ExtAddrMode::ScaledRegField:
3265 for (
const ExtAddrMode &AM : AddrModes)
3271 case ExtAddrMode::BaseOffsField:
3274 assert(ScaledReg ==
nullptr);
3284static inline raw_ostream &
operator<<(raw_ostream &OS,
const ExtAddrMode &AM) {
3290#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
3291void ExtAddrMode::print(raw_ostream &OS)
const {
3292 bool NeedPlus =
false;
3298 BaseGV->printAsOperand(OS,
false);
3303 OS << (NeedPlus ?
" + " :
"") << BaseOffs;
3308 OS << (NeedPlus ?
" + " :
"") <<
"Base:";
3309 BaseReg->printAsOperand(OS,
false);
3313 OS << (NeedPlus ?
" + " :
"") << Scale <<
"*";
3336class TypePromotionTransaction {
3340 class TypePromotionAction {
3348 TypePromotionAction(Instruction *Inst) : Inst(Inst) {}
3350 virtual ~TypePromotionAction() =
default;
3357 virtual void undo() = 0;
3362 virtual void commit() {
3368 class InsertionHandler {
3377 std::optional<DbgRecord::self_iterator> BeforeDbgRecord = std::nullopt;
3380 bool HasPrevInstruction;
3384 InsertionHandler(Instruction *Inst) {
3392 if (HasPrevInstruction) {
3400 void insert(Instruction *Inst) {
3401 if (HasPrevInstruction) {
3413 Inst->
getParent()->reinsertInstInDbgRecords(Inst, BeforeDbgRecord);
3418 class InstructionMoveBefore :
public TypePromotionAction {
3420 InsertionHandler Position;
3425 : TypePromotionAction(Inst), Position(Inst) {
3426 LLVM_DEBUG(
dbgs() <<
"Do: move: " << *Inst <<
"\nbefore: " << *Before
3432 void undo()
override {
3434 Position.insert(Inst);
3439 class OperandSetter :
public TypePromotionAction {
3448 OperandSetter(Instruction *Inst,
unsigned Idx,
Value *NewVal)
3449 : TypePromotionAction(Inst), Idx(Idx) {
3451 <<
"for:" << *Inst <<
"\n"
3452 <<
"with:" << *NewVal <<
"\n");
3458 void undo()
override {
3460 <<
"for: " << *Inst <<
"\n"
3461 <<
"with: " << *Origin <<
"\n");
3468 class OperandsHider :
public TypePromotionAction {
3470 SmallVector<Value *, 4> OriginalValues;
3474 OperandsHider(Instruction *Inst) : TypePromotionAction(Inst) {
3477 OriginalValues.
reserve(NumOpnds);
3478 for (
unsigned It = 0; It < NumOpnds; ++It) {
3490 void undo()
override {
3492 for (
unsigned It = 0, EndIt = OriginalValues.
size(); It != EndIt; ++It)
3498 class TruncBuilder :
public TypePromotionAction {
3505 TruncBuilder(Instruction *Opnd,
Type *Ty) : TypePromotionAction(Opnd) {
3507 Builder.SetCurrentDebugLocation(
DebugLoc());
3508 Val = Builder.CreateTrunc(Opnd, Ty,
"promoted");
3513 Value *getBuiltValue() {
return Val; }
3516 void undo()
override {
3519 IVal->eraseFromParent();
3524 class SExtBuilder :
public TypePromotionAction {
3531 SExtBuilder(Instruction *InsertPt,
Value *Opnd,
Type *Ty)
3532 : TypePromotionAction(InsertPt) {
3534 Val = Builder.CreateSExt(Opnd, Ty,
"promoted");
3539 Value *getBuiltValue() {
return Val; }
3542 void undo()
override {
3545 IVal->eraseFromParent();
3550 class ZExtBuilder :
public TypePromotionAction {
3557 ZExtBuilder(Instruction *InsertPt,
Value *Opnd,
Type *Ty)
3558 : TypePromotionAction(InsertPt) {
3560 Builder.SetCurrentDebugLocation(
DebugLoc());
3561 Val = Builder.CreateZExt(Opnd, Ty,
"promoted");
3566 Value *getBuiltValue() {
return Val; }
3569 void undo()
override {
3572 IVal->eraseFromParent();
3577 class TypeMutator :
public TypePromotionAction {
3583 TypeMutator(Instruction *Inst,
Type *NewTy)
3584 : TypePromotionAction(Inst), OrigTy(Inst->
getType()) {
3585 LLVM_DEBUG(
dbgs() <<
"Do: MutateType: " << *Inst <<
" with " << *NewTy
3591 void undo()
override {
3592 LLVM_DEBUG(
dbgs() <<
"Undo: MutateType: " << *Inst <<
" with " << *OrigTy
3599 class UsesReplacer :
public TypePromotionAction {
3601 struct InstructionAndIdx {
3608 InstructionAndIdx(Instruction *Inst,
unsigned Idx)
3609 : Inst(Inst), Idx(Idx) {}
3615 SmallVector<DbgVariableRecord *, 1> DbgVariableRecords;
3625 UsesReplacer(Instruction *Inst,
Value *New)
3626 : TypePromotionAction(Inst),
New(
New) {
3627 LLVM_DEBUG(
dbgs() <<
"Do: UsersReplacer: " << *Inst <<
" with " << *New
3630 for (Use &U : Inst->
uses()) {
3632 OriginalUses.
push_back(InstructionAndIdx(UserI,
U.getOperandNo()));
3643 void undo()
override {
3645 for (InstructionAndIdx &Use : OriginalUses)
3646 Use.Inst->setOperand(
Use.Idx, Inst);
3651 for (DbgVariableRecord *DVR : DbgVariableRecords)
3652 DVR->replaceVariableLocationOp(New, Inst);
3657 class InstructionRemover :
public TypePromotionAction {
3659 InsertionHandler Inserter;
3663 OperandsHider Hider;
3666 UsesReplacer *Replacer =
nullptr;
3669 SetOfInstrs &RemovedInsts;
3676 InstructionRemover(Instruction *Inst, SetOfInstrs &RemovedInsts,
3677 Value *New =
nullptr)
3678 : TypePromotionAction(Inst), Inserter(Inst), Hider(Inst),
3679 RemovedInsts(RemovedInsts) {
3681 Replacer =
new UsesReplacer(Inst, New);
3682 LLVM_DEBUG(
dbgs() <<
"Do: InstructionRemover: " << *Inst <<
"\n");
3683 RemovedInsts.insert(Inst);
3690 ~InstructionRemover()
override {
delete Replacer; }
3692 InstructionRemover &operator=(
const InstructionRemover &other) =
delete;
3693 InstructionRemover(
const InstructionRemover &other) =
delete;
3697 void undo()
override {
3698 LLVM_DEBUG(
dbgs() <<
"Undo: InstructionRemover: " << *Inst <<
"\n");
3699 Inserter.insert(Inst);
3703 RemovedInsts.erase(Inst);
3711 using ConstRestorationPt =
const TypePromotionAction *;
3713 TypePromotionTransaction(SetOfInstrs &RemovedInsts)
3714 : RemovedInsts(RemovedInsts) {}
3721 void rollback(ConstRestorationPt Point);
3724 ConstRestorationPt getRestorationPoint()
const;
3729 void setOperand(Instruction *Inst,
unsigned Idx,
Value *NewVal);
3738 void mutateType(Instruction *Inst,
Type *NewTy);
3741 Value *createTrunc(Instruction *Opnd,
Type *Ty);
3754 SmallVectorImpl<std::unique_ptr<TypePromotionAction>>::iterator;
3756 SetOfInstrs &RemovedInsts;
3761void TypePromotionTransaction::setOperand(Instruction *Inst,
unsigned Idx,
3763 Actions.push_back(std::make_unique<TypePromotionTransaction::OperandSetter>(
3764 Inst, Idx, NewVal));
3767void TypePromotionTransaction::eraseInstruction(Instruction *Inst,
3770 std::make_unique<TypePromotionTransaction::InstructionRemover>(
3771 Inst, RemovedInsts, NewVal));
3774void TypePromotionTransaction::replaceAllUsesWith(Instruction *Inst,
3777 std::make_unique<TypePromotionTransaction::UsesReplacer>(Inst, New));
3780void TypePromotionTransaction::mutateType(Instruction *Inst,
Type *NewTy) {
3782 std::make_unique<TypePromotionTransaction::TypeMutator>(Inst, NewTy));
3785Value *TypePromotionTransaction::createTrunc(Instruction *Opnd,
Type *Ty) {
3786 std::unique_ptr<TruncBuilder> Ptr(
new TruncBuilder(Opnd, Ty));
3787 Value *Val = Ptr->getBuiltValue();
3788 Actions.push_back(std::move(Ptr));
3792Value *TypePromotionTransaction::createSExt(Instruction *Inst,
Value *Opnd,
3794 std::unique_ptr<SExtBuilder> Ptr(
new SExtBuilder(Inst, Opnd, Ty));
3795 Value *Val = Ptr->getBuiltValue();
3796 Actions.push_back(std::move(Ptr));
3800Value *TypePromotionTransaction::createZExt(Instruction *Inst,
Value *Opnd,
3802 std::unique_ptr<ZExtBuilder> Ptr(
new ZExtBuilder(Inst, Opnd, Ty));
3803 Value *Val = Ptr->getBuiltValue();
3804 Actions.push_back(std::move(Ptr));
3808TypePromotionTransaction::ConstRestorationPt
3809TypePromotionTransaction::getRestorationPoint()
const {
3810 return !Actions.empty() ? Actions.back().get() :
nullptr;
3813bool TypePromotionTransaction::commit() {
3814 for (std::unique_ptr<TypePromotionAction> &Action : Actions)
3821void TypePromotionTransaction::rollback(
3822 TypePromotionTransaction::ConstRestorationPt Point) {
3823 while (!Actions.empty() && Point != Actions.back().get()) {
3824 std::unique_ptr<TypePromotionAction> Curr = Actions.pop_back_val();
3834class AddressingModeMatcher {
3835 SmallVectorImpl<Instruction *> &AddrModeInsts;
3836 const TargetLowering &TLI;
3837 const TargetRegisterInfo &
TRI;
3838 const DataLayout &
DL;
3840 const std::function<
const DominatorTree &()> getDTFn;
3853 const SetOfInstrs &InsertedInsts;
3856 InstrToOrigTy &PromotedInsts;
3859 TypePromotionTransaction &TPT;
3862 std::pair<AssertingVH<GetElementPtrInst>, int64_t> &LargeOffsetGEP;
3866 bool IgnoreProfitability;
3869 bool OptSize =
false;
3871 ProfileSummaryInfo *PSI;
3872 BlockFrequencyInfo *BFI;
3874 AddressingModeMatcher(
3875 SmallVectorImpl<Instruction *> &AMI,
const TargetLowering &TLI,
3876 const TargetRegisterInfo &
TRI,
const LoopInfo &LI,
3877 const std::function<
const DominatorTree &()> getDTFn,
Type *AT,
3878 unsigned AS, Instruction *
MI, ExtAddrMode &AM,
3879 const SetOfInstrs &InsertedInsts, InstrToOrigTy &PromotedInsts,
3880 TypePromotionTransaction &TPT,
3881 std::pair<AssertingVH<GetElementPtrInst>, int64_t> &LargeOffsetGEP,
3882 bool OptSize, ProfileSummaryInfo *PSI, BlockFrequencyInfo *BFI)
3883 : AddrModeInsts(AMI), TLI(TLI),
TRI(
TRI),
3884 DL(
MI->getDataLayout()), LI(LI), getDTFn(getDTFn),
3885 AccessTy(AT), AddrSpace(AS), MemoryInst(
MI),
AddrMode(AM),
3886 InsertedInsts(InsertedInsts), PromotedInsts(PromotedInsts), TPT(TPT),
3887 LargeOffsetGEP(LargeOffsetGEP), OptSize(OptSize), PSI(PSI), BFI(BFI) {
3888 IgnoreProfitability =
false;
3900 Match(
Value *V,
Type *AccessTy,
unsigned AS, Instruction *MemoryInst,
3901 SmallVectorImpl<Instruction *> &AddrModeInsts,
3902 const TargetLowering &TLI,
const LoopInfo &LI,
3903 const std::function<
const DominatorTree &()> getDTFn,
3904 const TargetRegisterInfo &
TRI,
const SetOfInstrs &InsertedInsts,
3905 InstrToOrigTy &PromotedInsts, TypePromotionTransaction &TPT,
3906 std::pair<AssertingVH<GetElementPtrInst>, int64_t> &LargeOffsetGEP,
3907 bool OptSize, ProfileSummaryInfo *PSI, BlockFrequencyInfo *BFI) {
3910 bool Success = AddressingModeMatcher(AddrModeInsts, TLI,
TRI, LI, getDTFn,
3911 AccessTy, AS, MemoryInst, Result,
3912 InsertedInsts, PromotedInsts, TPT,
3913 LargeOffsetGEP, OptSize, PSI, BFI)
3921 bool matchScaledValue(
Value *ScaleReg, int64_t Scale,
unsigned Depth);
3923 bool matchOperationAddr(User *AddrInst,
unsigned Opcode,
unsigned Depth,
3924 bool *MovedAway =
nullptr);
3925 bool isProfitableToFoldIntoAddressingMode(Instruction *
I,
3926 ExtAddrMode &AMBefore,
3927 ExtAddrMode &AMAfter);
3928 bool valueAlreadyLiveAtInst(
Value *Val,
Value *KnownLive1,
Value *KnownLive2);
3929 bool isPromotionProfitable(
unsigned NewCost,
unsigned OldCost,
3930 Value *PromotedOperand)
const;
3936class PhiNodeSetIterator {
3937 PhiNodeSet *
const Set;
3938 size_t CurrentIndex = 0;
3943 PhiNodeSetIterator(PhiNodeSet *
const Set,
size_t Start);
3945 PhiNodeSetIterator &operator++();
3961 friend class PhiNodeSetIterator;
3963 using MapType = SmallDenseMap<PHINode *, size_t, 32>;
3964 using iterator = PhiNodeSetIterator;
3979 size_t FirstValidElement = 0;
3985 bool insert(PHINode *Ptr) {
3986 if (NodeMap.insert(std::make_pair(Ptr,
NodeList.
size())).second) {
3996 bool erase(PHINode *Ptr) {
3997 if (NodeMap.erase(Ptr)) {
3998 SkipRemovedElements(FirstValidElement);
4008 FirstValidElement = 0;
4014 if (FirstValidElement == 0)
4015 SkipRemovedElements(FirstValidElement);
4016 return PhiNodeSetIterator(
this, FirstValidElement);
4023 size_t size()
const {
return NodeMap.size(); }
4026 size_t count(PHINode *Ptr)
const {
return NodeMap.count(Ptr); }
4034 void SkipRemovedElements(
size_t &CurrentIndex) {
4036 auto it = NodeMap.find(NodeList[CurrentIndex]);
4039 if (it != NodeMap.end() && it->second == CurrentIndex)
4046PhiNodeSetIterator::PhiNodeSetIterator(PhiNodeSet *
const Set,
size_t Start)
4049PHINode *PhiNodeSetIterator::operator*()
const {
4051 "PhiNodeSet access out of range");
4052 return Set->NodeList[CurrentIndex];
4055PhiNodeSetIterator &PhiNodeSetIterator::operator++() {
4057 "PhiNodeSet access out of range");
4059 Set->SkipRemovedElements(CurrentIndex);
4063bool PhiNodeSetIterator::operator==(
const PhiNodeSetIterator &
RHS)
const {
4064 return CurrentIndex ==
RHS.CurrentIndex;
4067bool PhiNodeSetIterator::operator!=(
const PhiNodeSetIterator &
RHS)
const {
4068 return !((*this) ==
RHS);
4074class SimplificationTracker {
4075 DenseMap<Value *, Value *> Storage;
4078 PhiNodeSet AllPhiNodes;
4080 SmallPtrSet<SelectInst *, 32> AllSelectNodes;
4085 auto SV = Storage.
find(V);
4086 if (SV == Storage.
end())
4094 void ReplacePhi(PHINode *From, PHINode *To) {
4095 Value *OldReplacement = Get(From);
4096 while (OldReplacement != From) {
4099 OldReplacement = Get(From);
4101 assert(To && Get(To) == To &&
"Replacement PHI node is already replaced.");
4104 AllPhiNodes.erase(From);
4108 PhiNodeSet &newPhiNodes() {
return AllPhiNodes; }
4110 void insertNewPhi(PHINode *PN) { AllPhiNodes.insert(PN); }
4112 void insertNewSelect(SelectInst *SI) { AllSelectNodes.
insert(SI); }
4114 unsigned countNewPhiNodes()
const {
return AllPhiNodes.size(); }
4116 unsigned countNewSelectNodes()
const {
return AllSelectNodes.
size(); }
4118 void destroyNewNodes(
Type *CommonType) {
4121 for (
auto *
I : AllPhiNodes) {
4122 I->replaceAllUsesWith(Dummy);
4123 I->eraseFromParent();
4125 AllPhiNodes.clear();
4126 for (
auto *
I : AllSelectNodes) {
4127 I->replaceAllUsesWith(Dummy);
4128 I->eraseFromParent();
4130 AllSelectNodes.clear();
4135class AddressingModeCombiner {
4136 typedef DenseMap<Value *, Value *> FoldAddrToValueMapping;
4137 typedef std::pair<PHINode *, PHINode *> PHIPair;
4144 ExtAddrMode::FieldName DifferentField = ExtAddrMode::NoField;
4147 bool AllAddrModesTrivial =
true;
4150 Type *CommonType =
nullptr;
4152 const DataLayout &
DL;
4158 Value *CommonValue =
nullptr;
4161 AddressingModeCombiner(
const DataLayout &
DL,
Value *OriginalValue)
4162 :
DL(
DL), Original(OriginalValue) {}
4164 ~AddressingModeCombiner() { eraseCommonValueIfDead(); }
4167 const ExtAddrMode &
getAddrMode()
const {
return AddrModes[0]; }
4172 bool addNewAddrMode(ExtAddrMode &NewAddrMode) {
4176 AllAddrModesTrivial = AllAddrModesTrivial && NewAddrMode.isTrivial();
4179 if (AddrModes.
empty()) {
4187 ExtAddrMode::FieldName ThisDifferentField =
4188 AddrModes[0].compare(NewAddrMode);
4189 if (DifferentField == ExtAddrMode::NoField)
4190 DifferentField = ThisDifferentField;
4191 else if (DifferentField != ThisDifferentField)
4192 DifferentField = ExtAddrMode::MultipleFields;
4195 bool CanHandle = DifferentField != ExtAddrMode::MultipleFields;
4198 CanHandle = CanHandle && DifferentField != ExtAddrMode::ScaleField;
4203 CanHandle = CanHandle && (DifferentField != ExtAddrMode::BaseOffsField ||
4208 CanHandle = CanHandle && (DifferentField != ExtAddrMode::BaseGVField ||
4209 !NewAddrMode.HasBaseReg);
4226 bool combineAddrModes() {
4228 if (AddrModes.
size() == 0)
4232 if (AddrModes.
size() == 1 || DifferentField == ExtAddrMode::NoField)
4237 if (AllAddrModesTrivial)
4240 if (!addrModeCombiningAllowed())
4246 FoldAddrToValueMapping
Map;
4247 if (!initializeMap(Map))
4250 CommonValue = findCommon(Map);
4252 AddrModes[0].SetCombinedField(DifferentField, CommonValue, AddrModes);
4253 return CommonValue !=
nullptr;
4259 void eraseCommonValueIfDead() {
4260 if (CommonValue && CommonValue->
use_empty())
4262 CommonInst->eraseFromParent();
4270 bool initializeMap(FoldAddrToValueMapping &Map) {
4273 SmallVector<Value *, 2> NullValue;
4275 for (
auto &AM : AddrModes) {
4279 if (CommonType && CommonType !=
Type)
4282 Map[AM.OriginalValue] = DV;
4287 assert(CommonType &&
"At least one non-null value must be!");
4288 for (
auto *V : NullValue)
4316 Value *findCommon(FoldAddrToValueMapping &Map) {
4324 SimplificationTracker
ST;
4329 InsertPlaceholders(Map, TraverseOrder, ST);
4332 FillPlaceholders(Map, TraverseOrder, ST);
4335 ST.destroyNewNodes(CommonType);
4340 unsigned PhiNotMatchedCount = 0;
4342 ST.destroyNewNodes(CommonType);
4346 auto *
Result =
ST.Get(
Map.find(Original)->second);
4348 NumMemoryInstsPhiCreated +=
ST.countNewPhiNodes() + PhiNotMatchedCount;
4349 NumMemoryInstsSelectCreated +=
ST.countNewSelectNodes();
4356 bool MatchPhiNode(PHINode *
PHI, PHINode *Candidate,
4357 SmallSetVector<PHIPair, 8> &Matcher,
4358 PhiNodeSet &PhiNodesToMatch) {
4361 SmallPtrSet<PHINode *, 8> MatchedPHIs;
4364 SmallSet<PHIPair, 8> Visited;
4365 while (!WorkList.
empty()) {
4367 if (!Visited.
insert(Item).second)
4374 for (
auto *
B : Item.first->blocks()) {
4375 Value *FirstValue = Item.first->getIncomingValueForBlock(
B);
4376 Value *SecondValue = Item.second->getIncomingValueForBlock(
B);
4377 if (FirstValue == SecondValue)
4387 if (!FirstPhi || !SecondPhi || !PhiNodesToMatch.count(FirstPhi) ||
4392 if (Matcher.
count({FirstPhi, SecondPhi}))
4397 if (MatchedPHIs.
insert(FirstPhi).second)
4398 Matcher.
insert({FirstPhi, SecondPhi});
4400 WorkList.
push_back({FirstPhi, SecondPhi});
4409 bool MatchPhiSet(SimplificationTracker &ST,
bool AllowNewPhiNodes,
4410 unsigned &PhiNotMatchedCount) {
4414 SmallSetVector<PHIPair, 8> Matched;
4415 SmallPtrSet<PHINode *, 8> WillNotMatch;
4416 PhiNodeSet &PhiNodesToMatch =
ST.newPhiNodes();
4417 while (PhiNodesToMatch.size()) {
4418 PHINode *
PHI = *PhiNodesToMatch.begin();
4421 WillNotMatch.
clear();
4425 bool IsMatched =
false;
4426 for (
auto &
P :
PHI->getParent()->phis()) {
4428 if (PhiNodesToMatch.count(&
P))
4430 if ((IsMatched = MatchPhiNode(
PHI, &
P, Matched, PhiNodesToMatch)))
4440 for (
auto MV : Matched)
4441 ST.ReplacePhi(MV.first, MV.second);
4446 if (!AllowNewPhiNodes)
4449 PhiNotMatchedCount += WillNotMatch.
size();
4450 for (
auto *
P : WillNotMatch)
4451 PhiNodesToMatch.erase(
P);
4456 void FillPlaceholders(FoldAddrToValueMapping &Map,
4457 SmallVectorImpl<Value *> &TraverseOrder,
4458 SimplificationTracker &ST) {
4459 while (!TraverseOrder.
empty()) {
4461 assert(
Map.contains(Current) &&
"No node to fill!!!");
4467 auto *TrueValue = CurrentSelect->getTrueValue();
4468 assert(
Map.contains(TrueValue) &&
"No True Value!");
4469 Select->setTrueValue(
ST.Get(Map[TrueValue]));
4470 auto *FalseValue = CurrentSelect->getFalseValue();
4471 assert(
Map.contains(FalseValue) &&
"No False Value!");
4472 Select->setFalseValue(
ST.Get(Map[FalseValue]));
4479 assert(
Map.contains(PV) &&
"No predecessor Value!");
4480 PHI->addIncoming(
ST.Get(Map[PV]),
B);
4491 void InsertPlaceholders(FoldAddrToValueMapping &Map,
4492 SmallVectorImpl<Value *> &TraverseOrder,
4493 SimplificationTracker &ST) {
4496 "Address must be a Phi or Select node");
4499 while (!Worklist.
empty()) {
4502 if (
Map.contains(Current))
4513 CurrentSelect->getName(),
4514 CurrentSelect->getIterator(), CurrentSelect);
4518 Worklist.
push_back(CurrentSelect->getTrueValue());
4519 Worklist.
push_back(CurrentSelect->getFalseValue());
4527 ST.insertNewPhi(
PHI);
4533 bool addrModeCombiningAllowed() {
4536 switch (DifferentField) {
4539 case ExtAddrMode::BaseRegField:
4541 case ExtAddrMode::BaseGVField:
4543 case ExtAddrMode::BaseOffsField:
4545 case ExtAddrMode::ScaledRegField:
4555bool AddressingModeMatcher::matchScaledValue(
Value *ScaleReg, int64_t Scale,
4560 return matchAddr(ScaleReg,
Depth);
4571 ExtAddrMode TestAddrMode =
AddrMode;
4575 TestAddrMode.
Scale += Scale;
4589 ConstantInt *CI =
nullptr;
4590 Value *AddLHS =
nullptr;
4594 TestAddrMode.InBounds =
false;
4611 auto GetConstantStep =
4612 [
this](
const Value *
V) -> std::optional<std::pair<Instruction *, APInt>> {
4615 return std::nullopt;
4618 return std::nullopt;
4626 if (OIVInc->hasNoSignedWrap() || OIVInc->hasNoUnsignedWrap())
4627 return std::nullopt;
4629 return std::make_pair(IVInc->first, ConstantStep->getValue());
4630 return std::nullopt;
4645 if (
auto IVStep = GetConstantStep(ScaleReg)) {
4652 APInt Step = IVStep->second;
4654 if (
Offset.isSignedIntN(64)) {
4655 TestAddrMode.InBounds =
false;
4657 TestAddrMode.BaseOffs -=
Offset.getLimitedValue();
4662 getDTFn().
dominates(IVInc, MemoryInst)) {
4682 switch (
I->getOpcode()) {
4683 case Instruction::BitCast:
4684 case Instruction::AddrSpaceCast:
4686 if (
I->getType() ==
I->getOperand(0)->getType())
4688 return I->getType()->isIntOrPtrTy();
4689 case Instruction::PtrToInt:
4692 case Instruction::IntToPtr:
4695 case Instruction::Add:
4697 case Instruction::Mul:
4698 case Instruction::Shl:
4701 case Instruction::GetElementPtr:
4729class TypePromotionHelper {
4732 static void addPromotedInst(InstrToOrigTy &PromotedInsts,
4733 Instruction *ExtOpnd,
bool IsSExt) {
4734 ExtType ExtTy = IsSExt ? SignExtension : ZeroExtension;
4735 auto [It,
Inserted] = PromotedInsts.try_emplace(ExtOpnd);
4739 if (It->second.getInt() == ExtTy)
4745 ExtTy = BothExtension;
4747 It->second = TypeIsSExt(ExtOpnd->
getType(), ExtTy);
4754 static const Type *getOrigType(
const InstrToOrigTy &PromotedInsts,
4755 Instruction *Opnd,
bool IsSExt) {
4756 ExtType ExtTy = IsSExt ? SignExtension : ZeroExtension;
4757 InstrToOrigTy::const_iterator It = PromotedInsts.find(Opnd);
4758 if (It != PromotedInsts.end() && It->second.getInt() == ExtTy)
4759 return It->second.getPointer();
4774 static bool canGetThrough(
const Instruction *Inst,
Type *ConsideredExtType,
4775 const InstrToOrigTy &PromotedInsts,
bool IsSExt);
4779 static bool shouldExtOperand(
const Instruction *Inst,
int OpIdx) {
4792 static Value *promoteOperandForTruncAndAnyExt(
4793 Instruction *Ext, TypePromotionTransaction &TPT,
4794 InstrToOrigTy &PromotedInsts,
unsigned &CreatedInstsCost,
4795 SmallVectorImpl<Instruction *> *Exts,
4796 SmallVectorImpl<Instruction *> *Truncs,
const TargetLowering &TLI);
4807 static Value *promoteOperandForOther(Instruction *Ext,
4808 TypePromotionTransaction &TPT,
4809 InstrToOrigTy &PromotedInsts,
4810 unsigned &CreatedInstsCost,
4811 SmallVectorImpl<Instruction *> *Exts,
4812 SmallVectorImpl<Instruction *> *Truncs,
4813 const TargetLowering &TLI,
bool IsSExt);
4816 static Value *signExtendOperandForOther(
4817 Instruction *Ext, TypePromotionTransaction &TPT,
4818 InstrToOrigTy &PromotedInsts,
unsigned &CreatedInstsCost,
4819 SmallVectorImpl<Instruction *> *Exts,
4820 SmallVectorImpl<Instruction *> *Truncs,
const TargetLowering &TLI) {
4821 return promoteOperandForOther(Ext, TPT, PromotedInsts, CreatedInstsCost,
4822 Exts, Truncs, TLI,
true);
4826 static Value *zeroExtendOperandForOther(
4827 Instruction *Ext, TypePromotionTransaction &TPT,
4828 InstrToOrigTy &PromotedInsts,
unsigned &CreatedInstsCost,
4829 SmallVectorImpl<Instruction *> *Exts,
4830 SmallVectorImpl<Instruction *> *Truncs,
const TargetLowering &TLI) {
4831 return promoteOperandForOther(Ext, TPT, PromotedInsts, CreatedInstsCost,
4832 Exts, Truncs, TLI,
false);
4837 using Action =
Value *(*)(Instruction *Ext, TypePromotionTransaction &TPT,
4838 InstrToOrigTy &PromotedInsts,
4839 unsigned &CreatedInstsCost,
4840 SmallVectorImpl<Instruction *> *Exts,
4841 SmallVectorImpl<Instruction *> *Truncs,
4842 const TargetLowering &TLI);
4853 static Action getAction(Instruction *Ext,
const SetOfInstrs &InsertedInsts,
4854 const TargetLowering &TLI,
4855 const InstrToOrigTy &PromotedInsts);
4860bool TypePromotionHelper::canGetThrough(
const Instruction *Inst,
4861 Type *ConsideredExtType,
4862 const InstrToOrigTy &PromotedInsts,
4882 ((!IsSExt && BinOp->hasNoUnsignedWrap()) ||
4883 (IsSExt && BinOp->hasNoSignedWrap())))
4887 if ((Inst->
getOpcode() == Instruction::And ||
4892 if (Inst->
getOpcode() == Instruction::Xor) {
4895 if (!Cst->getValue().isAllOnes())
4904 if (Inst->
getOpcode() == Instruction::LShr && !IsSExt)
4914 if (ExtInst->hasOneUse()) {
4916 if (AndInst && AndInst->getOpcode() == Instruction::And) {
4949 const Type *OpndType = getOrigType(PromotedInsts, Opnd, IsSExt);
4962TypePromotionHelper::Action TypePromotionHelper::getAction(
4963 Instruction *Ext,
const SetOfInstrs &InsertedInsts,
4964 const TargetLowering &TLI,
const InstrToOrigTy &PromotedInsts) {
4966 "Unexpected instruction type");
4973 if (!ExtOpnd || !canGetThrough(ExtOpnd, ExtTy, PromotedInsts, IsSExt))
4986 return promoteOperandForTruncAndAnyExt;
4992 return IsSExt ? signExtendOperandForOther : zeroExtendOperandForOther;
4995Value *TypePromotionHelper::promoteOperandForTruncAndAnyExt(
4996 Instruction *SExt, TypePromotionTransaction &TPT,
4997 InstrToOrigTy &PromotedInsts,
unsigned &CreatedInstsCost,
4998 SmallVectorImpl<Instruction *> *Exts,
4999 SmallVectorImpl<Instruction *> *Truncs,
const TargetLowering &TLI) {
5003 Value *ExtVal = SExt;
5004 bool HasMergedNonFreeExt =
false;
5008 HasMergedNonFreeExt = !TLI.
isExtFree(SExtOpnd);
5011 TPT.replaceAllUsesWith(SExt, ZExt);
5012 TPT.eraseInstruction(SExt);
5017 TPT.setOperand(SExt, 0, SExtOpnd->
getOperand(0));
5019 CreatedInstsCost = 0;
5023 TPT.eraseInstruction(SExtOpnd);
5031 CreatedInstsCost = !TLI.
isExtFree(ExtInst) && !HasMergedNonFreeExt;
5039 TPT.eraseInstruction(ExtInst, NextVal);
5043Value *TypePromotionHelper::promoteOperandForOther(
5044 Instruction *Ext, TypePromotionTransaction &TPT,
5045 InstrToOrigTy &PromotedInsts,
unsigned &CreatedInstsCost,
5046 SmallVectorImpl<Instruction *> *Exts,
5047 SmallVectorImpl<Instruction *> *Truncs,
const TargetLowering &TLI,
5052 CreatedInstsCost = 0;
5058 Value *Trunc = TPT.createTrunc(Ext, ExtOpnd->
getType());
5061 ITrunc->moveAfter(ExtOpnd);
5066 TPT.replaceAllUsesWith(ExtOpnd, Trunc);
5069 TPT.setOperand(Ext, 0, ExtOpnd);
5079 addPromotedInst(PromotedInsts, ExtOpnd, IsSExt);
5081 TPT.mutateType(ExtOpnd, Ext->
getType());
5083 TPT.replaceAllUsesWith(Ext, ExtOpnd);
5090 !shouldExtOperand(ExtOpnd,
OpIdx)) {
5099 APInt CstVal = IsSExt ? Cst->getValue().sext(
BitWidth)
5101 TPT.setOperand(ExtOpnd,
OpIdx, ConstantInt::get(Ext->
getType(), CstVal));
5112 Value *ValForExtOpnd = IsSExt
5113 ? TPT.createSExt(ExtOpnd, Opnd, Ext->
getType())
5114 : TPT.createZExt(ExtOpnd, Opnd, Ext->
getType());
5115 TPT.setOperand(ExtOpnd,
OpIdx, ValForExtOpnd);
5117 if (!InstForExtOpnd)
5123 CreatedInstsCost += !TLI.
isExtFree(InstForExtOpnd);
5126 TPT.eraseInstruction(Ext);
5138bool AddressingModeMatcher::isPromotionProfitable(
5139 unsigned NewCost,
unsigned OldCost,
Value *PromotedOperand)
const {
5140 LLVM_DEBUG(
dbgs() <<
"OldCost: " << OldCost <<
"\tNewCost: " << NewCost
5145 if (NewCost > OldCost)
5147 if (NewCost < OldCost)
5166bool AddressingModeMatcher::matchOperationAddr(User *AddrInst,
unsigned Opcode,
5178 case Instruction::PtrToInt:
5181 case Instruction::IntToPtr: {
5189 case Instruction::BitCast:
5199 case Instruction::AddrSpaceCast: {
5207 case Instruction::Add: {
5210 ExtAddrMode BackupAddrMode =
AddrMode;
5211 unsigned OldSize = AddrModeInsts.
size();
5216 TypePromotionTransaction::ConstRestorationPt LastKnownGood =
5217 TPT.getRestorationPoint();
5221 int First = 0, Second = 1;
5232 AddrModeInsts.
resize(OldSize);
5233 TPT.rollback(LastKnownGood);
5243 AddrModeInsts.
resize(OldSize);
5244 TPT.rollback(LastKnownGood);
5250 case Instruction::Mul:
5251 case Instruction::Shl: {
5255 if (!
RHS ||
RHS->getBitWidth() > 64)
5257 int64_t Scale = Opcode == Instruction::Shl
5258 ? 1LL <<
RHS->getLimitedValue(
RHS->getBitWidth() - 1)
5259 :
RHS->getSExtValue();
5263 case Instruction::GetElementPtr: {
5266 int VariableOperand = -1;
5267 unsigned VariableScale = 0;
5269 int64_t ConstantOffset = 0;
5271 for (
unsigned i = 1, e = AddrInst->
getNumOperands(); i != e; ++i, ++GTI) {
5273 const StructLayout *SL =
DL.getStructLayout(STy);
5284 if (ConstantInt *CI =
5286 const APInt &CVal = CI->
getValue();
5293 if (VariableOperand != -1)
5297 VariableOperand = i;
5298 VariableScale = TypeSize;
5305 if (VariableOperand == -1) {
5306 AddrMode.BaseOffs += ConstantOffset;
5312 AddrMode.BaseOffs -= ConstantOffset;
5316 ConstantOffset > 0) {
5329 BasicBlock *Parent = BaseI ? BaseI->getParent()
5330 : &
GEP->getFunction()->getEntryBlock();
5332 LargeOffsetGEP = std::make_pair(
GEP, ConstantOffset);
5340 ExtAddrMode BackupAddrMode =
AddrMode;
5341 unsigned OldSize = AddrModeInsts.
size();
5344 AddrMode.BaseOffs += ConstantOffset;
5353 AddrModeInsts.
resize(OldSize);
5361 if (!matchScaledValue(AddrInst->
getOperand(VariableOperand), VariableScale,
5366 AddrModeInsts.
resize(OldSize);
5371 AddrMode.BaseOffs += ConstantOffset;
5372 if (!matchScaledValue(AddrInst->
getOperand(VariableOperand),
5373 VariableScale,
Depth)) {
5376 AddrModeInsts.
resize(OldSize);
5383 case Instruction::SExt:
5384 case Instruction::ZExt: {
5391 TypePromotionHelper::Action TPH =
5392 TypePromotionHelper::getAction(Ext, InsertedInsts, TLI, PromotedInsts);
5396 TypePromotionTransaction::ConstRestorationPt LastKnownGood =
5397 TPT.getRestorationPoint();
5398 unsigned CreatedInstsCost = 0;
5400 Value *PromotedOperand =
5401 TPH(Ext, TPT, PromotedInsts, CreatedInstsCost,
nullptr,
nullptr, TLI);
5416 assert(PromotedOperand &&
5417 "TypePromotionHelper should have filtered out those cases");
5419 ExtAddrMode BackupAddrMode =
AddrMode;
5420 unsigned OldSize = AddrModeInsts.
size();
5422 if (!matchAddr(PromotedOperand,
Depth) ||
5427 !isPromotionProfitable(CreatedInstsCost,
5428 ExtCost + (AddrModeInsts.
size() - OldSize),
5431 AddrModeInsts.
resize(OldSize);
5432 LLVM_DEBUG(
dbgs() <<
"Sign extension does not pay off: rollback\n");
5433 TPT.rollback(LastKnownGood);
5438 AddrMode.replaceWith(Ext, PromotedOperand);
5441 case Instruction::Call:
5443 if (
II->getIntrinsicID() == Intrinsic::threadlocal_address) {
5459bool AddressingModeMatcher::matchAddr(
Value *Addr,
unsigned Depth) {
5462 TypePromotionTransaction::ConstRestorationPt LastKnownGood =
5463 TPT.getRestorationPoint();
5487 ExtAddrMode BackupAddrMode =
AddrMode;
5488 unsigned OldSize = AddrModeInsts.
size();
5491 bool MovedAway =
false;
5492 if (matchOperationAddr(
I,
I->getOpcode(),
Depth, &MovedAway)) {
5500 if (
I->hasOneUse() ||
5501 isProfitableToFoldIntoAddressingMode(
I, BackupAddrMode,
AddrMode)) {
5508 AddrModeInsts.
resize(OldSize);
5509 TPT.rollback(LastKnownGood);
5512 if (matchOperationAddr(CE,
CE->getOpcode(),
Depth))
5514 TPT.rollback(LastKnownGood);
5541 TPT.rollback(LastKnownGood);
5560 if (OpInfo.CallOperandVal == OpVal &&
5562 !OpInfo.isIndirect))
5578 if (!ConsideredInsts.
insert(
I).second)
5586 for (
Use &U :
I->uses()) {
5594 MemoryUses.push_back({&U, LI->getType()});
5601 MemoryUses.push_back({&U,
SI->getValueOperand()->getType()});
5608 MemoryUses.push_back({&U, RMW->getValOperand()->getType()});
5615 MemoryUses.push_back({&U, CmpX->getCompareOperand()->getType()});
5625 if (!
find(PtrOps, U.get()))
5628 MemoryUses.push_back({&U, AccessTy});
5633 if (CI->hasFnAttr(Attribute::Cold)) {
5651 PSI, BFI, SeenInsts))
5662 unsigned SeenInsts = 0;
5665 PSI, BFI, SeenInsts);
5673bool AddressingModeMatcher::valueAlreadyLiveAtInst(
Value *Val,
5675 Value *KnownLive2) {
5677 if (Val ==
nullptr || Val == KnownLive1 || Val == KnownLive2)
5718bool AddressingModeMatcher::isProfitableToFoldIntoAddressingMode(
5719 Instruction *
I, ExtAddrMode &AMBefore, ExtAddrMode &AMAfter) {
5720 if (IgnoreProfitability)
5738 if (valueAlreadyLiveAtInst(ScaledReg, AMBefore.
BaseReg, AMBefore.
ScaledReg))
5739 ScaledReg =
nullptr;
5743 if (!BaseReg && !ScaledReg)
5764 for (
const std::pair<Use *, Type *> &Pair : MemoryUses) {
5767 Type *AddressAccessTy = Pair.second;
5768 unsigned AS =
Address->getType()->getPointerAddressSpace();
5774 std::pair<AssertingVH<GetElementPtrInst>, int64_t> LargeOffsetGEP(
nullptr,
5776 TypePromotionTransaction::ConstRestorationPt LastKnownGood =
5777 TPT.getRestorationPoint();
5778 AddressingModeMatcher Matcher(MatchedAddrModeInsts, TLI,
TRI, LI, getDTFn,
5779 AddressAccessTy, AS, UserI, Result,
5780 InsertedInsts, PromotedInsts, TPT,
5781 LargeOffsetGEP, OptSize, PSI, BFI);
5782 Matcher.IgnoreProfitability =
true;
5790 TPT.rollback(LastKnownGood);
5796 MatchedAddrModeInsts.
clear();
5806 return I->getParent() != BB;
5822 return std::next(AddrInst->getIterator());
5833 Earliest = UserInst;
5858bool CodeGenPrepare::optimizeMemoryInst(Instruction *MemoryInst,
Value *Addr,
5859 Type *AccessTy,
unsigned AddrSpace) {
5864 SmallVector<Value *, 8> worklist;
5865 SmallPtrSet<Value *, 16> Visited;
5871 bool PhiOrSelectSeen =
false;
5872 SmallVector<Instruction *, 16> AddrModeInsts;
5873 AddressingModeCombiner AddrModes(*
DL, Addr);
5874 TypePromotionTransaction TPT(RemovedInsts);
5875 TypePromotionTransaction::ConstRestorationPt LastKnownGood =
5876 TPT.getRestorationPoint();
5877 while (!worklist.
empty()) {
5889 if (!Visited.
insert(V).second)
5895 PhiOrSelectSeen =
true;
5902 PhiOrSelectSeen =
true;
5909 AddrModeInsts.
clear();
5910 std::pair<AssertingVH<GetElementPtrInst>, int64_t> LargeOffsetGEP(
nullptr,
5915 auto getDTFn = [
this]() ->
const DominatorTree & {
return getDT(); };
5916 ExtAddrMode NewAddrMode = AddressingModeMatcher::Match(
5917 V, AccessTy, AddrSpace, MemoryInst, AddrModeInsts, *TLI, *LI, getDTFn,
5918 *
TRI, InsertedInsts, PromotedInsts, TPT, LargeOffsetGEP, OptSize, PSI,
5921 GetElementPtrInst *
GEP = LargeOffsetGEP.first;
5926 LargeOffsetGEPMap[
GEP->getPointerOperand()].push_back(LargeOffsetGEP);
5927 LargeOffsetGEPID.
insert(std::make_pair(
GEP, LargeOffsetGEPID.
size()));
5930 NewAddrMode.OriginalValue =
V;
5931 if (!AddrModes.addNewAddrMode(NewAddrMode))
5938 if (!AddrModes.combineAddrModes()) {
5939 TPT.rollback(LastKnownGood);
5945 ExtAddrMode
AddrMode = AddrModes.getAddrMode();
5951 if (!PhiOrSelectSeen &&
none_of(AddrModeInsts, [&](
Value *V) {
5965 WeakTrackingVH SunkAddrVH = SunkAddrs[Addr];
5987 <<
" for " << *MemoryInst <<
"\n");
5991 !
DL->isNonIntegralPointerType(Addr->
getType())) {
5997 SunkAddr = Builder.CreatePtrToInt(SunkAddr,
IntPtrTy,
"sunkaddr");
5999 Builder.CreateIntToPtr(SunkAddr, Addr->
getType(),
"sunkaddr");
6001 SunkAddr = Builder.CreatePointerCast(SunkAddr, Addr->
getType());
6008 <<
" for " << *MemoryInst <<
"\n");
6009 Value *ResultPtr =
nullptr, *ResultIndex =
nullptr;
6020 if (ResultPtr ||
AddrMode.Scale != 1)
6041 GlobalValue *BaseGV =
AddrMode.BaseGV;
6042 if (BaseGV !=
nullptr) {
6047 ResultPtr = Builder.CreateThreadLocalAddress(BaseGV);
6056 if (!
DL->isNonIntegralPointerType(Addr->
getType())) {
6057 if (!ResultPtr &&
AddrMode.BaseReg) {
6061 }
else if (!ResultPtr &&
AddrMode.Scale == 1) {
6062 ResultPtr = Builder.CreateIntToPtr(
AddrMode.ScaledReg, Addr->
getType(),
6071 }
else if (!ResultPtr) {
6085 V = Builder.CreateIntCast(V,
IntPtrTy,
true,
"sunkaddr");
6098 "We can't transform if ScaledReg is too narrow");
6099 V = Builder.CreateTrunc(V,
IntPtrTy,
"sunkaddr");
6103 V = Builder.CreateMul(
6106 ResultIndex = Builder.CreateAdd(ResultIndex, V,
"sunkaddr");
6117 if (ResultPtr->
getType() != I8PtrTy)
6118 ResultPtr = Builder.CreatePointerCast(ResultPtr, I8PtrTy);
6119 ResultPtr = Builder.CreatePtrAdd(ResultPtr, ResultIndex,
"sunkaddr",
6132 if (PtrInst && PtrInst->getParent() != MemoryInst->
getParent())
6134 SunkAddr = ResultPtr;
6136 if (ResultPtr->
getType() != I8PtrTy)
6137 ResultPtr = Builder.CreatePointerCast(ResultPtr, I8PtrTy);
6138 SunkAddr = Builder.CreatePtrAdd(ResultPtr, ResultIndex,
"sunkaddr",
6145 !
DL->isNonIntegralPointerType(Addr->
getType())) {
6151 SunkAddr = Builder.CreatePtrToInt(SunkAddr,
IntPtrTy,
"sunkaddr");
6153 Builder.CreateIntToPtr(SunkAddr, Addr->
getType(),
"sunkaddr");
6155 SunkAddr = Builder.CreatePointerCast(SunkAddr, Addr->
getType());
6165 if (
DL->isNonIntegralPointerType(Addr->
getType()) ||
6166 (BasePtrTy &&
DL->isNonIntegralPointerType(BasePtrTy)) ||
6167 (ScalePtrTy &&
DL->isNonIntegralPointerType(ScalePtrTy)) ||
6169 DL->isNonIntegralPointerType(
AddrMode.BaseGV->getType())))
6173 <<
" for " << *MemoryInst <<
"\n");
6184 if (
V->getType()->isPointerTy())
6185 V = Builder.CreatePtrToInt(V,
IntPtrTy,
"sunkaddr");
6187 V = Builder.CreateIntCast(V,
IntPtrTy,
true,
"sunkaddr");
6196 }
else if (
V->getType()->isPointerTy()) {
6197 V = Builder.CreatePtrToInt(V,
IntPtrTy,
"sunkaddr");
6200 V = Builder.CreateTrunc(V,
IntPtrTy,
"sunkaddr");
6209 I->eraseFromParent();
6213 V = Builder.CreateMul(
6216 Result = Builder.CreateAdd(Result, V,
"sunkaddr");
6222 GlobalValue *BaseGV =
AddrMode.BaseGV;
6223 if (BaseGV !=
nullptr) {
6226 BaseGVPtr = Builder.CreateThreadLocalAddress(BaseGV);
6230 Value *
V = Builder.CreatePtrToInt(BaseGVPtr,
IntPtrTy,
"sunkaddr");
6232 Result = Builder.CreateAdd(Result, V,
"sunkaddr");
6241 Result = Builder.CreateAdd(Result, V,
"sunkaddr");
6249 SunkAddr = Builder.CreateIntToPtr(Result, Addr->
getType(),
"sunkaddr");
6255 SunkAddrs[Addr] = WeakTrackingVH(SunkAddr);
6260 resetIteratorIfInvalidatedWhileCalling(CurInstIterator->getParent(), [&]() {
6261 RecursivelyDeleteTriviallyDeadInstructions(
6262 Repl, TLInfo, nullptr,
6263 [&](Value *V) { removeAllAssertingVHReferences(V); });
6287bool CodeGenPrepare::optimizeGatherScatterInst(Instruction *MemoryInst,
6293 if (!
GEP->hasIndices())
6301 SmallVector<Value *, 2>
Ops(
GEP->operands());
6303 bool RewriteGEP =
false;
6312 unsigned FinalIndex =
Ops.size() - 1;
6317 for (
unsigned i = 1; i < FinalIndex; ++i) {
6322 C =
C->getSplatValue();
6324 if (!CI || !CI->
isZero())
6331 if (
Ops[FinalIndex]->
getType()->isVectorTy()) {
6335 if (!
C || !
C->isZero()) {
6336 Ops[FinalIndex] =
V;
6344 if (!RewriteGEP &&
Ops.size() == 2)
6351 Type *SourceTy =
GEP->getSourceElementType();
6352 Type *ScalarIndexTy =
DL->getIndexType(
Ops[0]->
getType()->getScalarType());
6356 if (!
Ops[FinalIndex]->
getType()->isVectorTy()) {
6357 NewAddr = Builder.CreateGEP(SourceTy,
Ops[0],
ArrayRef(
Ops).drop_front());
6358 auto *IndexTy = VectorType::get(ScalarIndexTy, NumElts);
6368 if (
Ops.size() != 2) {
6378 NewAddr = Builder.CreateGEP(SourceTy,
Base, Index);
6392 Type *ScalarIndexTy =
DL->getIndexType(
V->getType()->getScalarType());
6393 auto *IndexTy = VectorType::get(ScalarIndexTy, NumElts);
6396 Intrinsic::masked_gather) {
6400 Intrinsic::masked_scatter);
6415 Ptr, TLInfo,
nullptr,
6416 [&](
Value *V) { removeAllAssertingVHReferences(V); });
6427 if (
I->hasNUsesOrMore(3))
6430 for (
User *U :
I->users()) {
6432 if (!Extract || Extract->getNumIndices() != 1)
6435 unsigned Index = Extract->getIndices()[0];
6437 MulExtract = Extract;
6438 else if (Index == 1)
6439 OverflowExtract = Extract;
6466bool CodeGenPrepare::optimizeMulWithOverflow(Instruction *
I,
bool IsSigned,
6467 ModifyDT &ModifiedDT) {
6474 ExtractValueInst *MulExtract =
nullptr, *OverflowExtract =
nullptr;
6479 InsertedInsts.insert(
I);
6490 OverflowEntryBB->
takeName(
I->getParent());
6496 NoOverflowBB->
moveAfter(OverflowEntryBB);
6504 Value *LoLHS = Builder.CreateTrunc(
LHS, LegalTy,
"lo.lhs");
6505 Value *HiLHS = Builder.CreateLShr(
LHS, VTHalfBitWidth,
"lhs.lsr");
6506 HiLHS = Builder.CreateTrunc(HiLHS, LegalTy,
"hi.lhs");
6509 Value *LoRHS = Builder.CreateTrunc(
RHS, LegalTy,
"lo.rhs");
6510 Value *HiRHS = Builder.CreateLShr(
RHS, VTHalfBitWidth,
"rhs.lsr");
6511 HiRHS = Builder.CreateTrunc(HiRHS, LegalTy,
"hi.rhs");
6513 Value *IsAnyBitTrue;
6516 Builder.CreateAShr(LoLHS, VTHalfBitWidth - 1,
"sign.lo.lhs");
6518 Builder.CreateAShr(LoRHS, VTHalfBitWidth - 1,
"sign.lo.rhs");
6519 Value *XorLHS = Builder.CreateXor(HiLHS, SignLoLHS);
6520 Value *XorRHS = Builder.CreateXor(HiRHS, SignLoRHS);
6521 Value *
Or = Builder.CreateOr(XorLHS, XorRHS,
"or.lhs.rhs");
6522 IsAnyBitTrue = Builder.CreateCmp(ICmpInst::ICMP_NE,
Or,
6523 ConstantInt::getNullValue(
Or->getType()));
6525 Value *CmpLHS = Builder.CreateCmp(ICmpInst::ICMP_NE, HiLHS,
6526 ConstantInt::getNullValue(LegalTy));
6527 Value *CmpRHS = Builder.CreateCmp(ICmpInst::ICMP_NE, HiRHS,
6528 ConstantInt::getNullValue(LegalTy));
6529 IsAnyBitTrue = Builder.CreateOr(CmpLHS, CmpRHS,
"or.lhs.rhs");
6531 Builder.CreateCondBr(IsAnyBitTrue, OverflowBB, NoOverflowBB);
6534 Builder.SetInsertPoint(NoOverflowBB);
6535 Value *ExtLoLHS, *ExtLoRHS;
6537 ExtLoLHS = Builder.CreateSExt(LoLHS, Ty,
"lo.lhs.ext");
6538 ExtLoRHS = Builder.CreateSExt(LoRHS, Ty,
"lo.rhs.ext");
6540 ExtLoLHS = Builder.CreateZExt(LoLHS, Ty,
"lo.lhs.ext");
6541 ExtLoRHS = Builder.CreateZExt(LoRHS, Ty,
"lo.rhs.ext");
6544 Value *
Mul = Builder.CreateMul(ExtLoLHS, ExtLoRHS,
"mul.overflow.no");
6549 OverflowResBB->
setName(
"overflow.res");
6552 Builder.CreateBr(OverflowResBB);
6560 PHINode *OverflowResPHI = Builder.CreatePHI(Ty, 2),
6562 Builder.CreatePHI(IntegerType::getInt1Ty(
I->getContext()), 2);
6574 if (OverflowExtract) {
6575 OverflowExtract->replaceAllUsesWith(OverflowFlagPHI);
6576 OverflowExtract->eraseFromParent();
6581 I->removeFromParent();
6583 I->insertInto(OverflowBB, OverflowBB->
end());
6584 Builder.SetInsertPoint(OverflowBB, OverflowBB->
end());
6586 Value *OverflowFlag = Builder.CreateExtractValue(
I, {1},
"overflow.flag");
6587 Builder.CreateBr(OverflowResBB);
6591 OverflowFlagPHI->addIncoming(OverflowFlag, OverflowBB);
6593 DTU->
applyUpdates({{DominatorTree::Insert, OverflowEntryBB, OverflowBB},
6594 {DominatorTree::Insert, OverflowEntryBB, NoOverflowBB},
6595 {DominatorTree::Insert, NoOverflowBB, OverflowResBB},
6596 {DominatorTree::Delete, OverflowEntryBB, OverflowResBB},
6597 {DominatorTree::Insert, OverflowBB, OverflowResBB}});
6599 ModifiedDT = ModifyDT::ModifyBBDT;
6605bool CodeGenPrepare::optimizeInlineAsmInst(CallInst *CS) {
6606 bool MadeChange =
false;
6608 const TargetRegisterInfo *
TRI =
6613 for (TargetLowering::AsmOperandInfo &OpInfo : TargetConstraints) {
6619 OpInfo.isIndirect) {
6621 MadeChange |= optimizeMemoryInst(CS, OpVal, OpVal->
getType(), ~0u);
6684bool CodeGenPrepare::tryToPromoteExts(
6685 TypePromotionTransaction &TPT,
const SmallVectorImpl<Instruction *> &Exts,
6686 SmallVectorImpl<Instruction *> &ProfitablyMovedExts,
6687 unsigned CreatedInstsCost) {
6688 bool Promoted =
false;
6691 for (
auto *
I : Exts) {
6706 TypePromotionHelper::Action TPH =
6707 TypePromotionHelper::getAction(
I, InsertedInsts, *TLI, PromotedInsts);
6716 TypePromotionTransaction::ConstRestorationPt LastKnownGood =
6717 TPT.getRestorationPoint();
6718 SmallVector<Instruction *, 4> NewExts;
6719 unsigned NewCreatedInstsCost = 0;
6722 Value *PromotedVal = TPH(
I, TPT, PromotedInsts, NewCreatedInstsCost,
6723 &NewExts,
nullptr, *TLI);
6725 "TypePromotionHelper should have filtered out those cases");
6735 long long TotalCreatedInstsCost = CreatedInstsCost + NewCreatedInstsCost;
6738 TotalCreatedInstsCost =
6739 std::max((
long long)0, (TotalCreatedInstsCost - ExtCost));
6741 (TotalCreatedInstsCost > 1 ||
6743 (ExtCost == 0 && NewExts.
size() > 1))) {
6747 TPT.rollback(LastKnownGood);
6752 SmallVector<Instruction *, 2> NewlyMovedExts;
6753 (void)tryToPromoteExts(TPT, NewExts, NewlyMovedExts, TotalCreatedInstsCost);
6754 bool NewPromoted =
false;
6755 for (
auto *ExtInst : NewlyMovedExts) {
6765 ProfitablyMovedExts.
push_back(MovedExt);
6772 TPT.rollback(LastKnownGood);
6783bool CodeGenPrepare::mergeSExts(Function &
F) {
6785 for (
auto &Entry : ValToSExtendedUses) {
6786 SExts &Insts =
Entry.second;
6788 for (Instruction *Inst : Insts) {
6792 bool inserted =
false;
6793 for (
auto &Pt : CurPts) {
6796 RemovedInsts.insert(Pt);
6797 Pt->removeFromParent();
6808 RemovedInsts.insert(Inst);
6815 CurPts.push_back(Inst);
6857bool CodeGenPrepare::splitLargeGEPOffsets() {
6859 for (
auto &Entry : LargeOffsetGEPMap) {
6861 SmallVectorImpl<std::pair<AssertingVH<GetElementPtrInst>, int64_t>>
6862 &LargeOffsetGEPs =
Entry.second;
6863 auto compareGEPOffset =
6864 [&](
const std::pair<GetElementPtrInst *, int64_t> &
LHS,
6865 const std::pair<GetElementPtrInst *, int64_t> &
RHS) {
6866 if (
LHS.first ==
RHS.first)
6868 if (
LHS.second !=
RHS.second)
6869 return LHS.second <
RHS.second;
6870 return LargeOffsetGEPID[
LHS.first] < LargeOffsetGEPID[
RHS.first];
6873 llvm::sort(LargeOffsetGEPs, compareGEPOffset);
6876 if (LargeOffsetGEPs.
front().second == LargeOffsetGEPs.
back().second)
6878 GetElementPtrInst *BaseGEP = LargeOffsetGEPs.
begin()->first;
6879 int64_t BaseOffset = LargeOffsetGEPs.
begin()->second;
6880 Value *NewBaseGEP =
nullptr;
6882 auto createNewBase = [&](int64_t BaseOffset,
Value *OldBase,
6883 GetElementPtrInst *
GEP) {
6884 LLVMContext &Ctx =
GEP->getContext();
6885 Type *PtrIdxTy =
DL->getIndexType(
GEP->getType());
6887 PointerType::get(Ctx,
GEP->getType()->getPointerAddressSpace());
6899 SplitEdge(NewBaseInsertBB, Invoke->getNormalDest(), &getDT(), LI);
6902 NewBaseInsertPt = std::next(BaseI->getIterator());
6909 IRBuilder<> NewBaseBuilder(NewBaseInsertBB, NewBaseInsertPt);
6915 NewBaseGEP = OldBase;
6916 if (NewBaseGEP->
getType() != I8PtrTy)
6917 NewBaseGEP = NewBaseBuilder.CreatePointerCast(NewBaseGEP, I8PtrTy);
6919 NewBaseBuilder.CreatePtrAdd(NewBaseGEP, BaseIndex,
"splitgep");
6920 NewGEPBases.
insert(NewBaseGEP);
6926 LargeOffsetGEPs.
front().second, LargeOffsetGEPs.
back().second)) {
6927 BaseOffset = PreferBase;
6930 createNewBase(BaseOffset, OldBase, BaseGEP);
6933 auto *LargeOffsetGEP = LargeOffsetGEPs.
begin();
6934 while (LargeOffsetGEP != LargeOffsetGEPs.
end()) {
6935 GetElementPtrInst *
GEP = LargeOffsetGEP->first;
6936 int64_t
Offset = LargeOffsetGEP->second;
6937 if (
Offset != BaseOffset) {
6944 GEP->getResultElementType(),
6945 GEP->getAddressSpace())) {
6951 NewBaseGEP =
nullptr;
6956 Type *PtrIdxTy =
DL->getIndexType(
GEP->getType());
6961 createNewBase(BaseOffset, OldBase,
GEP);
6965 Value *NewGEP = NewBaseGEP;
6966 if (
Offset != BaseOffset) {
6969 NewGEP = Builder.CreatePtrAdd(NewBaseGEP, Index);
6973 LargeOffsetGEP = LargeOffsetGEPs.
erase(LargeOffsetGEP);
6974 GEP->eraseFromParent();
6981bool CodeGenPrepare::optimizePhiType(
6982 PHINode *
I, SmallPtrSetImpl<PHINode *> &Visited,
6983 SmallPtrSetImpl<Instruction *> &DeletedInstrs) {
6988 Type *PhiTy =
I->getType();
6989 Type *ConvertTy =
nullptr;
6991 (!
I->getType()->isIntegerTy() && !
I->getType()->isFloatingPointTy()))
6994 SmallVector<Instruction *, 4> Worklist;
6996 SmallPtrSet<PHINode *, 4> PhiNodes;
6997 SmallPtrSet<ConstantData *, 4>
Constants;
7000 SmallPtrSet<Instruction *, 4> Defs;
7001 SmallPtrSet<Instruction *, 4>
Uses;
7007 bool AnyAnchored =
false;
7009 while (!Worklist.
empty()) {
7014 for (
Value *V :
Phi->incoming_values()) {
7016 if (!PhiNodes.
count(OpPhi)) {
7017 if (!Visited.
insert(OpPhi).second)
7023 if (!OpLoad->isSimple())
7025 if (Defs.
insert(OpLoad).second)
7028 if (Defs.
insert(OpEx).second)
7032 ConvertTy = OpBC->getOperand(0)->getType();
7033 if (OpBC->getOperand(0)->getType() != ConvertTy)
7035 if (Defs.
insert(OpBC).second) {
7048 for (User *V :
II->users()) {
7050 if (!PhiNodes.
count(OpPhi)) {
7051 if (Visited.
count(OpPhi))
7058 if (!OpStore->isSimple() || OpStore->getOperand(0) !=
II)
7060 Uses.insert(OpStore);
7063 ConvertTy = OpBC->getType();
7064 if (OpBC->getType() != ConvertTy)
7068 any_of(OpBC->users(), [](User *U) { return !isa<StoreInst>(U); });
7075 if (!ConvertTy || !AnyAnchored || PhiTy == ConvertTy ||
7079 LLVM_DEBUG(
dbgs() <<
"Converting " << *
I <<
"\n and connected nodes to "
7080 << *ConvertTy <<
"\n");
7085 for (ConstantData *
C : Constants)
7087 for (Instruction *
D : Defs) {
7089 ValMap[
D] =
D->getOperand(0);
7093 ValMap[
D] =
new BitCastInst(
D, ConvertTy,
D->getName() +
".bc", insertPt);
7096 for (PHINode *Phi : PhiNodes)
7098 Phi->getName() +
".tc",
Phi->getIterator());
7100 for (PHINode *Phi : PhiNodes) {
7102 for (
int i = 0, e =
Phi->getNumIncomingValues(); i < e; i++)
7104 Phi->getIncomingBlock(i));
7108 for (Instruction *U :
Uses) {
7113 U->setOperand(0,
new BitCastInst(ValMap[
U->getOperand(0)], PhiTy,
"bc",
7123bool CodeGenPrepare::optimizePhiTypes(Function &
F) {
7128 SmallPtrSet<PHINode *, 4> Visited;
7129 SmallPtrSet<Instruction *, 4> DeletedInstrs;
7133 for (
auto &Phi : BB.
phis())
7134 Changed |= optimizePhiType(&Phi, Visited, DeletedInstrs);
7137 for (
auto *
I : DeletedInstrs) {
7139 I->eraseFromParent();
7147bool CodeGenPrepare::canFormExtLd(
7148 const SmallVectorImpl<Instruction *> &MovedExts, LoadInst *&LI,
7149 Instruction *&Inst,
bool HasPromoted) {
7150 for (
auto *MovedExtInst : MovedExts) {
7153 Inst = MovedExtInst;
7205bool CodeGenPrepare::optimizeExt(Instruction *&Inst) {
7206 bool AllowPromotionWithoutCommonHeader =
false;
7211 *Inst, AllowPromotionWithoutCommonHeader);
7212 TypePromotionTransaction TPT(RemovedInsts);
7213 TypePromotionTransaction::ConstRestorationPt LastKnownGood =
7214 TPT.getRestorationPoint();
7216 SmallVector<Instruction *, 2> SpeculativelyMovedExts;
7219 bool HasPromoted = tryToPromoteExts(TPT, Exts, SpeculativelyMovedExts);
7222 LoadInst *LI =
nullptr;
7227 if (canFormExtLd(SpeculativelyMovedExts, LI, ExtFedByLoad, HasPromoted)) {
7228 assert(LI && ExtFedByLoad &&
"Expect a valid load and extension");
7233 Inst = ExtFedByLoad;
7238 if (ATPConsiderable &&
7239 performAddressTypePromotion(Inst, AllowPromotionWithoutCommonHeader,
7240 HasPromoted, TPT, SpeculativelyMovedExts))
7243 TPT.rollback(LastKnownGood);
7252bool CodeGenPrepare::performAddressTypePromotion(
7253 Instruction *&Inst,
bool AllowPromotionWithoutCommonHeader,
7254 bool HasPromoted, TypePromotionTransaction &TPT,
7255 SmallVectorImpl<Instruction *> &SpeculativelyMovedExts) {
7256 bool Promoted =
false;
7257 SmallPtrSet<Instruction *, 1> UnhandledExts;
7258 bool AllSeenFirst =
true;
7259 for (
auto *
I : SpeculativelyMovedExts) {
7260 Value *HeadOfChain =
I->getOperand(0);
7261 auto AlreadySeen = SeenChainsForSExt.
find(HeadOfChain);
7264 if (AlreadySeen != SeenChainsForSExt.
end()) {
7265 if (AlreadySeen->second !=
nullptr)
7266 UnhandledExts.
insert(AlreadySeen->second);
7267 AllSeenFirst =
false;
7271 if (!AllSeenFirst || (AllowPromotionWithoutCommonHeader &&
7272 SpeculativelyMovedExts.size() == 1)) {
7276 for (
auto *
I : SpeculativelyMovedExts) {
7277 Value *HeadOfChain =
I->getOperand(0);
7278 SeenChainsForSExt[HeadOfChain] =
nullptr;
7279 ValToSExtendedUses[HeadOfChain].push_back(
I);
7282 Inst = SpeculativelyMovedExts.pop_back_val();
7287 for (
auto *
I : SpeculativelyMovedExts) {
7288 Value *HeadOfChain =
I->getOperand(0);
7289 SeenChainsForSExt[HeadOfChain] = Inst;
7294 if (!AllSeenFirst && !UnhandledExts.
empty())
7295 for (
auto *VisitedSExt : UnhandledExts) {
7296 if (RemovedInsts.count(VisitedSExt))
7298 TypePromotionTransaction TPT(RemovedInsts);
7300 SmallVector<Instruction *, 2> Chains;
7302 bool HasPromoted = tryToPromoteExts(TPT, Exts, Chains);
7306 for (
auto *
I : Chains) {
7307 Value *HeadOfChain =
I->getOperand(0);
7309 SeenChainsForSExt[HeadOfChain] =
nullptr;
7310 ValToSExtendedUses[HeadOfChain].push_back(
I);
7316bool CodeGenPrepare::optimizeExtUses(Instruction *
I) {
7321 Value *Src =
I->getOperand(0);
7322 if (Src->hasOneUse())
7334 bool DefIsLiveOut =
false;
7335 for (User *U :
I->users()) {
7340 if (UserBB == DefBB)
7342 DefIsLiveOut =
true;
7349 for (User *U : Src->users()) {
7352 if (UserBB == DefBB)
7361 DenseMap<BasicBlock *, Instruction *> InsertedTruncs;
7363 bool MadeChange =
false;
7364 for (Use &U : Src->uses()) {
7369 if (UserBB == DefBB)
7373 Instruction *&InsertedTrunc = InsertedTruncs[UserBB];
7375 if (!InsertedTrunc) {
7378 InsertedTrunc =
new TruncInst(
I, Src->getType(),
"");
7380 InsertedInsts.insert(InsertedTrunc);
7443bool CodeGenPrepare::optimizeLoadExt(LoadInst *Load) {
7444 if (!
Load->isSimple() || !
Load->getType()->isIntOrPtrTy())
7448 if (
Load->hasOneUse() &&
7454 SmallVector<Instruction *, 8> WorkList;
7455 SmallPtrSet<Instruction *, 16> Visited;
7456 SmallVector<Instruction *, 8> AndsToMaybeRemove;
7457 SmallVector<Instruction *, 8> DropFlags;
7458 for (
auto *U :
Load->users())
7470 while (!WorkList.
empty()) {
7474 if (!Visited.
insert(
I).second)
7479 for (
auto *U :
Phi->users())
7484 switch (
I->getOpcode()) {
7485 case Instruction::And: {
7489 APInt AndBits = AndC->getValue();
7490 DemandBits |= AndBits;
7492 if (AndBits.
ugt(WidestAndBits))
7493 WidestAndBits = AndBits;
7494 if (AndBits == WidestAndBits &&
I->getOperand(0) == Load)
7499 case Instruction::Shl: {
7503 uint64_t ShiftAmt = ShlC->getLimitedValue(
BitWidth - 1);
7504 DemandBits.setLowBits(
BitWidth - ShiftAmt);
7509 case Instruction::Trunc: {
7512 DemandBits.setLowBits(TruncBitWidth);
7522 uint32_t ActiveBits = DemandBits.getActiveBits();
7534 if (ActiveBits <= 1 || !DemandBits.isMask(ActiveBits) ||
7535 WidestAndBits != DemandBits)
7538 LLVMContext &Ctx =
Load->getType()->getContext();
7539 Type *TruncTy = Type::getIntNTy(Ctx, ActiveBits);
7550 Builder.CreateAnd(Load, ConstantInt::get(Ctx, DemandBits)));
7553 InsertedInsts.insert(NewAnd);
7558 NewAnd->setOperand(0, Load);
7561 for (
auto *
And : AndsToMaybeRemove)
7566 if (&*CurInstIterator ==
And)
7567 CurInstIterator = std::next(
And->getIterator());
7568 And->eraseFromParent();
7573 for (
auto *Inst : DropFlags)
7587 TTI->isExpensiveToSpeculativelyExecute(
I);
7605 uint64_t Max = std::max(TrueWeight, FalseWeight);
7606 uint64_t Sum = TrueWeight + FalseWeight;
7609 if (Probability >
TTI->getPredictableBranchThreshold())
7619 if (!Cmp || !Cmp->hasOneUse())
7642 assert(DefSI->getCondition() ==
SI->getCondition() &&
7643 "The condition of DefSI does not match with SI");
7644 V = (isTrue ? DefSI->getTrueValue() : DefSI->getFalseValue());
7647 assert(V &&
"Failed to get select true/false value");
7651bool CodeGenPrepare::optimizeShiftInst(BinaryOperator *Shift) {
7675 BinaryOperator::BinaryOps Opcode = Shift->
getOpcode();
7676 Value *NewTVal = Builder.CreateBinOp(Opcode, Shift->
getOperand(0), TVal);
7677 Value *NewFVal = Builder.CreateBinOp(Opcode, Shift->
getOperand(0), FVal);
7678 Value *NewSel = Builder.CreateSelect(
Cond, NewTVal, NewFVal);
7684bool CodeGenPrepare::optimizeFunnelShift(IntrinsicInst *Fsh) {
7686 assert((Opcode == Intrinsic::fshl || Opcode == Intrinsic::fshr) &&
7687 "Expected a funnel shift");
7711 Value *NewTVal = Builder.CreateIntrinsic(Opcode, Ty, {
X,
Y, TVal});
7712 Value *NewFVal = Builder.CreateIntrinsic(Opcode, Ty, {
X,
Y, FVal});
7713 Value *NewSel = Builder.CreateSelect(
Cond, NewTVal, NewFVal);
7721bool CodeGenPrepare::optimizeSelectInst(SelectInst *SI) {
7733 It !=
SI->getParent()->
end(); ++It) {
7735 if (
I &&
SI->getCondition() ==
I->getCondition()) {
7742 SelectInst *LastSI = ASI.
back();
7745 CurInstIterator = std::next(LastSI->
getIterator());
7749 for (SelectInst *SI :
ArrayRef(ASI).drop_front())
7750 fixupDbgVariableRecordsOnInst(*SI);
7752 bool VectorCond = !
SI->getCondition()->getType()->isIntegerTy(1);
7755 if (VectorCond ||
SI->getMetadata(LLVMContext::MD_unpredictable))
7758 TargetLowering::SelectSupportKind SelectKind;
7759 if (
SI->getType()->isVectorTy())
7760 SelectKind = TargetLowering::ScalarCondVectorVal;
7762 SelectKind = TargetLowering::ScalarValSelect;
7800 for (SelectInst *SI : ASI) {
7812 SplitPt.setHeadBit(
true);
7815 auto *CondFr =
IB.CreateFreeze(
SI->getCondition(),
SI->getName() +
".frozen");
7820 UncondBrInst *TrueBranch =
nullptr;
7821 UncondBrInst *FalseBranch =
nullptr;
7822 if (TrueInstrs.
size() == 0) {
7825 FalseBlock = FalseBranch->getParent();
7827 }
else if (FalseInstrs.
size() == 0) {
7830 TrueBlock = TrueBranch->getParent();
7839 TrueBlock = TrueBranch->getParent();
7840 FalseBlock = FalseBranch->getParent();
7844 EndBlock->
setName(
"select.end");
7846 TrueBlock->
setName(
"select.true.sink");
7848 FalseBlock->
setName(FalseInstrs.
size() == 0 ?
"select.false"
7849 :
"select.false.sink");
7853 FreshBBs.
insert(TrueBlock);
7855 FreshBBs.
insert(FalseBlock);
7856 FreshBBs.
insert(EndBlock);
7861 static const unsigned MD[] = {
7862 LLVMContext::MD_prof, LLVMContext::MD_unpredictable,
7863 LLVMContext::MD_make_implicit, LLVMContext::MD_dbg};
7868 for (Instruction *
I : TrueInstrs)
7869 I->moveBefore(TrueBranch->getIterator());
7870 for (Instruction *
I : FalseInstrs)
7871 I->moveBefore(FalseBranch->getIterator());
7877 if (TrueBlock ==
nullptr)
7878 TrueBlock = StartBlock;
7879 else if (FalseBlock ==
nullptr)
7880 FalseBlock = StartBlock;
7896 SI->eraseFromParent();
7898 ++NumSelectsExpanded;
7902 CurInstIterator = StartBlock->
end();
7909bool CodeGenPrepare::optimizeShuffleVectorInst(ShuffleVectorInst *SVI) {
7921 "Expected a type of the same size!");
7927 Builder.SetInsertPoint(SVI);
7928 Value *BC1 = Builder.CreateBitCast(
7930 Value *Shuffle = Builder.CreateVectorSplat(NewVecType->getNumElements(), BC1);
7931 Value *BC2 = Builder.CreateBitCast(Shuffle, SVIVecType);
7935 SVI, TLInfo,
nullptr,
7936 [&](
Value *V) { removeAllAssertingVHReferences(V); });
7943 !
Op->isTerminator() && !
Op->isEHPad())
7949bool CodeGenPrepare::tryToSinkFreeOperands(Instruction *
I) {
7964 for (Use *U :
reverse(OpsToSink)) {
7976 SetVector<Instruction *> MaybeDead;
7977 DenseMap<Instruction *, Instruction *> NewInstructions;
7978 for (Use *U : ToReplace) {
7987 FreshBBs.
insert(OpDef->getParent());
7990 NewInstructions[UI] = NI;
7995 InsertedInsts.insert(NI);
8001 if (
auto It = NewInstructions.
find(OldI); It != NewInstructions.
end())
8002 It->second->setOperand(
U->getOperandNo(), NI);
8009 for (
auto *
I : MaybeDead) {
8010 if (!
I->hasNUsesOrMore(1)) {
8012 I->eraseFromParent();
8019bool CodeGenPrepare::optimizeSwitchType(SwitchInst *SI) {
8025 unsigned RegWidth =
RegType.getSizeInBits();
8036 auto *NewType = Type::getIntNTy(
Context, RegWidth);
8045 ExtType = Instruction::SExt;
8048 if (Arg->hasSExtAttr())
8049 ExtType = Instruction::SExt;
8050 if (Arg->hasZExtAttr())
8051 ExtType = Instruction::ZExt;
8057 SI->setCondition(ExtInst);
8058 for (
auto Case :
SI->cases()) {
8059 const APInt &NarrowConst = Case.getCaseValue()->getValue();
8060 APInt WideConst = (ExtType == Instruction::ZExt)
8061 ? NarrowConst.
zext(RegWidth)
8062 : NarrowConst.
sext(RegWidth);
8063 Case.setValue(ConstantInt::get(
Context, WideConst));
8069bool CodeGenPrepare::optimizeSwitchPhiConstants(SwitchInst *SI) {
8076 Value *Condition =
SI->getCondition();
8085 for (
const SwitchInst::CaseHandle &Case :
SI->cases()) {
8086 ConstantInt *CaseValue = Case.getCaseValue();
8087 BasicBlock *CaseBB = Case.getCaseSuccessor();
8090 bool CheckedForSinglePred =
false;
8091 for (PHINode &
PHI : CaseBB->
phis()) {
8092 Type *PHIType =
PHI.getType();
8100 if (PHIType == ConditionType || TryZExt) {
8102 bool SkipCase =
false;
8103 Value *Replacement =
nullptr;
8104 for (
unsigned I = 0,
E =
PHI.getNumIncomingValues();
I !=
E;
I++) {
8105 Value *PHIValue =
PHI.getIncomingValue(
I);
8106 if (PHIValue != CaseValue) {
8115 if (
PHI.getIncomingBlock(
I) != SwitchBB)
8120 if (!CheckedForSinglePred) {
8121 CheckedForSinglePred =
true;
8122 if (
SI->findCaseDest(CaseBB) ==
nullptr) {
8128 if (Replacement ==
nullptr) {
8129 if (PHIValue == CaseValue) {
8130 Replacement = Condition;
8133 Replacement = Builder.CreateZExt(Condition, PHIType);
8136 PHI.setIncomingValue(
I, Replacement);
8147bool CodeGenPrepare::optimizeSwitchInst(SwitchInst *SI) {
8148 bool Changed = optimizeSwitchType(SI);
8149 Changed |= optimizeSwitchPhiConstants(SI);
8170class VectorPromoteHelper {
8172 const DataLayout &
DL;
8175 const TargetLowering &TLI;
8178 const TargetTransformInfo &
TTI;
8184 SmallVector<Instruction *, 4> InstsToBePromoted;
8187 unsigned StoreExtractCombineCost;
8196 if (InstsToBePromoted.
empty())
8198 return InstsToBePromoted.
back();
8204 unsigned getTransitionOriginalValueIdx()
const {
8206 "Other kind of transitions are not supported yet");
8213 unsigned getTransitionIdx()
const {
8215 "Other kind of transitions are not supported yet");
8223 Type *getTransitionType()
const {
8234 void promoteImpl(Instruction *ToBePromoted);
8238 bool isProfitableToPromote() {
8239 Value *ValIdx = Transition->
getOperand(getTransitionOriginalValueIdx());
8243 Type *PromotedType = getTransitionType();
8246 unsigned AS =
ST->getPointerAddressSpace();
8264 for (
const auto &Inst : InstsToBePromoted) {
8272 TargetTransformInfo::OperandValueInfo Arg0Info, Arg1Info;
8284 dbgs() <<
"Estimated cost of computation to be promoted:\nScalar: "
8285 << ScalarCost <<
"\nVector: " << VectorCost <<
'\n');
8286 return ScalarCost > VectorCost;
8298 unsigned ExtractIdx = std::numeric_limits<unsigned>::max();
8313 if (!
EC.isScalable()) {
8314 SmallVector<Constant *, 4> ConstVec;
8316 for (
unsigned Idx = 0; Idx !=
EC.getKnownMinValue(); ++Idx) {
8317 if (Idx == ExtractIdx)
8325 "Generate scalable vector for non-splat is unimplemented");
8330 static bool canCauseUndefinedBehavior(
const Instruction *Use,
8331 unsigned OperandIdx) {
8334 if (OperandIdx != 1)
8336 switch (
Use->getOpcode()) {
8339 case Instruction::SDiv:
8340 case Instruction::UDiv:
8341 case Instruction::SRem:
8342 case Instruction::URem:
8344 case Instruction::FDiv:
8345 case Instruction::FRem:
8346 return !
Use->hasNoNaNs();
8352 VectorPromoteHelper(
const DataLayout &
DL,
const TargetLowering &TLI,
8353 const TargetTransformInfo &
TTI, Instruction *Transition,
8354 unsigned CombineCost)
8355 :
DL(
DL), TLI(TLI),
TTI(
TTI), Transition(Transition),
8356 StoreExtractCombineCost(CombineCost) {
8357 assert(Transition &&
"Do not know how to promote null");
8361 bool canPromote(
const Instruction *ToBePromoted)
const {
8368 bool shouldPromote(
const Instruction *ToBePromoted)
const {
8371 for (
const Use &U : ToBePromoted->
operands()) {
8372 const Value *Val =
U.get();
8373 if (Val == getEndOfTransition()) {
8377 if (canCauseUndefinedBehavior(ToBePromoted,
U.getOperandNo()))
8400 void enqueueForPromotion(Instruction *ToBePromoted) {
8401 InstsToBePromoted.push_back(ToBePromoted);
8405 void recordCombineInstruction(Instruction *ToBeCombined) {
8407 CombineInst = ToBeCombined;
8417 if (InstsToBePromoted.empty() || !CombineInst)
8425 for (
auto &ToBePromoted : InstsToBePromoted)
8426 promoteImpl(ToBePromoted);
8427 InstsToBePromoted.clear();
8434void VectorPromoteHelper::promoteImpl(Instruction *ToBePromoted) {
8444 "The type of the result of the transition does not match "
8449 Type *TransitionTy = getTransitionType();
8454 for (Use &U : ToBePromoted->
operands()) {
8456 Value *NewVal =
nullptr;
8457 if (Val == Transition)
8458 NewVal = Transition->
getOperand(getTransitionOriginalValueIdx());
8465 canCauseUndefinedBehavior(ToBePromoted,
U.getOperandNo()));
8469 ToBePromoted->
setOperand(
U.getOperandNo(), NewVal);
8472 Transition->
setOperand(getTransitionOriginalValueIdx(), ToBePromoted);
8478bool CodeGenPrepare::optimizeExtractElementInst(Instruction *Inst) {
8479 unsigned CombineCost = std::numeric_limits<unsigned>::max();
8494 LLVM_DEBUG(
dbgs() <<
"Found an interesting transition: " << *Inst <<
'\n');
8495 VectorPromoteHelper VPH(*
DL, *TLI, *
TTI, Inst, CombineCost);
8502 if (ToBePromoted->
getParent() != Parent) {
8503 LLVM_DEBUG(
dbgs() <<
"Instruction to promote is in a different block ("
8505 <<
") than the transition (" << Parent->
getName()
8510 if (VPH.canCombine(ToBePromoted)) {
8512 <<
"will be combined with: " << *ToBePromoted <<
'\n');
8513 VPH.recordCombineInstruction(ToBePromoted);
8515 NumStoreExtractExposed +=
Changed;
8520 if (!VPH.canPromote(ToBePromoted) || !VPH.shouldPromote(ToBePromoted))
8523 LLVM_DEBUG(
dbgs() <<
"Promoting is possible... Enqueue for promotion!\n");
8525 VPH.enqueueForPromotion(ToBePromoted);
8526 Inst = ToBePromoted;
8566 Type *StoreType =
SI.getValueOperand()->getType();
8575 if (!
DL.typeSizeEqualsStoreSize(StoreType) ||
8576 DL.getTypeSizeInBits(StoreType) == 0)
8579 unsigned HalfValBitSize =
DL.getTypeSizeInBits(StoreType) / 2;
8581 if (!
DL.typeSizeEqualsStoreSize(SplitStoreType))
8597 if (!
match(
SI.getValueOperand(),
8604 if (!
LValue->getType()->isIntegerTy() ||
8605 DL.getTypeSizeInBits(
LValue->getType()) > HalfValBitSize ||
8607 DL.getTypeSizeInBits(HValue->
getType()) > HalfValBitSize)
8623 Builder.SetInsertPoint(&
SI);
8627 if (LBC && LBC->getParent() !=
SI.getParent())
8628 LValue = Builder.CreateBitCast(LBC->getOperand(0), LBC->getType());
8629 if (HBC && HBC->getParent() !=
SI.getParent())
8630 HValue = Builder.CreateBitCast(HBC->getOperand(0), HBC->getType());
8632 bool IsLE =
SI.getDataLayout().isLittleEndian();
8633 auto CreateSplitStore = [&](
Value *V,
bool Upper) {
8634 V = Builder.CreateZExtOrBitCast(V, SplitStoreType);
8635 Value *Addr =
SI.getPointerOperand();
8636 Align Alignment =
SI.getAlign();
8637 const bool IsOffsetStore = (IsLE &&
Upper) || (!IsLE && !
Upper);
8638 if (IsOffsetStore) {
8639 Addr = Builder.CreateGEP(
8640 SplitStoreType, Addr,
8648 Builder.CreateAlignedStore(V, Addr, Alignment);
8651 CreateSplitStore(
LValue,
false);
8652 CreateSplitStore(HValue,
true);
8655 SI.eraseFromParent();
8663 return GEP->getNumOperands() == 2 &&
I.isSequential() &&
8745 if (GEPIOpI->getParent() != SrcBlock)
8750 if (auto *I = dyn_cast<Instruction>(Usr)) {
8751 if (I->getParent() != SrcBlock) {
8759 std::vector<GetElementPtrInst *> UGEPIs;
8762 for (User *Usr : GEPIOp->
users()) {
8781 if (UGEPI->getOperand(0) != GEPIOp)
8783 if (UGEPI->getSourceElementType() != GEPI->getSourceElementType())
8785 if (GEPIIdx->getType() !=
8793 UGEPIs.push_back(UGEPI);
8795 if (UGEPIs.size() == 0)
8798 for (GetElementPtrInst *UGEPI : UGEPIs) {
8800 APInt NewIdx = UGEPIIdx->
getValue() - GEPIIdx->getValue();
8807 for (GetElementPtrInst *UGEPI : UGEPIs) {
8808 UGEPI->setOperand(0, GEPI);
8810 auto NewIdx = UGEPIIdx->
getValue() - GEPIIdx->getValue();
8811 Constant *NewUGEPIIdx = ConstantInt::get(GEPIIdx->getType(), NewIdx);
8812 UGEPI->setOperand(1, NewUGEPIIdx);
8814 auto SourceFlags = GEPI->getNoWrapFlags();
8817 UGEPI->getNoWrapFlags().intersectForOffsetAdd(SourceFlags);
8819 if (NewIdx.
isNegative() && TargetFlags.hasNoUnsignedWrap())
8820 TargetFlags = TargetFlags.withoutNoUnsignedWrap();
8821 UGEPI->setNoWrapFlags(TargetFlags);
8827 return cast<Instruction>(Usr)->getParent() != SrcBlock;
8829 "GEPIOp is used outside SrcBlock");
8853 Value *
X = Cmp->getOperand(0);
8854 if (!
X->hasUseList())
8859 for (
auto *U :
X->users()) {
8863 (UI->
getParent() != Branch->getParent() &&
8864 UI->
getParent() != Branch->getSuccessor(0) &&
8865 UI->
getParent() != Branch->getSuccessor(1)) ||
8866 (UI->
getParent() != Branch->getParent() &&
8867 !UI->
getParent()->getSinglePredecessor()))
8873 if (UI->
getParent() != Branch->getParent())
8877 ConstantInt::get(UI->
getType(), 0));
8879 LLVM_DEBUG(
dbgs() <<
" to compare on zero: " << *NewCmp <<
"\n");
8883 if (Cmp->isEquality() &&
8888 if (UI->
getParent() != Branch->getParent())
8891 Value *NewCmp = Builder.CreateCmp(Cmp->getPredicate(), UI,
8892 ConstantInt::get(UI->
getType(), 0));
8894 LLVM_DEBUG(
dbgs() <<
" to compare on zero: " << *NewCmp <<
"\n");
8902bool CodeGenPrepare::optimizeInst(Instruction *
I, ModifyDT &ModifiedDT) {
8903 bool AnyChange =
false;
8904 AnyChange = fixupDbgVariableRecordsOnInst(*
I);
8908 if (InsertedInsts.count(
I))
8917 LargeOffsetGEPMap.erase(
P);
8919 P->eraseFromParent();
8942 I, LI->getLoopFor(
I->getParent()), *
TTI))
8950 TargetLowering::TypeExpandInteger) {
8954 I, LI->getLoopFor(
I->getParent()), *
TTI))
8957 bool MadeChange = optimizeExt(
I);
8958 return MadeChange | optimizeExtUses(
I);
8965 if (optimizeCmp(Cmp, ModifiedDT))
8969 if (optimizeURem(
I))
8973 LI->
setMetadata(LLVMContext::MD_invariant_group,
nullptr);
8974 bool Modified = optimizeLoadExt(LI);
8983 SI->setMetadata(LLVMContext::MD_invariant_group,
nullptr);
8984 unsigned AS =
SI->getPointerAddressSpace();
8985 return optimizeMemoryInst(
I,
SI->getOperand(1),
8986 SI->getOperand(0)->getType(), AS);
8990 unsigned AS = RMW->getPointerAddressSpace();
8991 return optimizeMemoryInst(
I, RMW->getPointerOperand(), RMW->getType(), AS);
8995 unsigned AS = CmpX->getPointerAddressSpace();
8996 return optimizeMemoryInst(
I, CmpX->getPointerOperand(),
8997 CmpX->getCompareOperand()->getType(), AS);
9007 if (BinOp && (BinOp->
getOpcode() == Instruction::AShr ||
9008 BinOp->
getOpcode() == Instruction::LShr)) {
9016 if (GEPI->hasAllZeroIndices()) {
9018 Instruction *
NC =
new BitCastInst(GEPI->getOperand(0), GEPI->getType(),
9019 GEPI->getName(), GEPI->getIterator());
9020 NC->setDebugLoc(GEPI->getDebugLoc());
9023 GEPI, TLInfo,
nullptr,
9024 [&](
Value *V) { removeAllAssertingVHReferences(V); });
9026 optimizeInst(
NC, ModifiedDT);
9049 if (Const0 || Const1) {
9050 if (!Const0 || !Const1) {
9051 auto *
F =
new FreezeInst(Const0 ? Op1 : Op0,
"", CmpI->
getIterator());
9056 FI->eraseFromParent();
9063 if (tryToSinkFreeOperands(
I))
9066 switch (
I->getOpcode()) {
9067 case Instruction::Shl:
9068 case Instruction::LShr:
9069 case Instruction::AShr:
9071 case Instruction::Call:
9073 case Instruction::Select:
9075 case Instruction::ShuffleVector:
9077 case Instruction::Switch:
9079 case Instruction::ExtractElement:
9081 case Instruction::CondBr:
9090bool CodeGenPrepare::makeBitReverse(Instruction &
I) {
9091 if (!
I.getType()->isIntegerTy() ||
9096 SmallVector<Instruction *, 4> Insts;
9102 &
I, TLInfo,
nullptr,
9103 [&](
Value *V) { removeAllAssertingVHReferences(V); });
9110bool CodeGenPrepare::optimizeBlock(BasicBlock &BB, ModifyDT &ModifiedDT) {
9112 bool MadeChange =
false;
9115 CurInstIterator = BB.
begin();
9116 ModifiedDT = ModifyDT::NotModifyDT;
9117 while (CurInstIterator != BB.
end()) {
9118 MadeChange |= optimizeInst(&*CurInstIterator++, ModifiedDT);
9119 if (ModifiedDT != ModifyDT::NotModifyDT) {
9128 }
while (ModifiedDT == ModifyDT::ModifyInstDT);
9130 bool MadeBitReverse =
true;
9131 while (MadeBitReverse) {
9132 MadeBitReverse =
false;
9134 if (makeBitReverse(
I)) {
9135 MadeBitReverse = MadeChange =
true;
9140 MadeChange |= dupRetToEnableTailCallOpts(&BB, ModifiedDT);
9145bool CodeGenPrepare::fixupDbgVariableRecordsOnInst(Instruction &
I) {
9146 bool AnyChange =
false;
9147 for (DbgVariableRecord &DVR :
filterDbgVars(
I.getDbgRecordRange()))
9148 AnyChange |= fixupDbgVariableRecord(DVR);
9154bool CodeGenPrepare::fixupDbgVariableRecord(DbgVariableRecord &DVR) {
9155 if (DVR.
Type != DbgVariableRecord::LocationType::Value &&
9156 DVR.
Type != DbgVariableRecord::LocationType::Assign)
9160 bool AnyChange =
false;
9161 SmallDenseSet<Value *> LocationOps(DVR.
location_ops().begin(),
9163 for (
Value *Location : LocationOps) {
9164 WeakTrackingVH SunkAddrVH = SunkAddrs[
Location];
9193bool CodeGenPrepare::placeDbgValues(Function &
F) {
9194 bool MadeChange =
false;
9195 DominatorTree &DT = getDT();
9197 auto DbgProcessor = [&](
auto *DbgItem,
Instruction *Position) {
9198 SmallVector<Instruction *, 4> VIs;
9199 for (
Value *V : DbgItem->location_ops())
9207 for (Instruction *VI : VIs) {
9208 if (
VI->isTerminator())
9213 if (
isa<PHINode>(VI) &&
VI->getParent()->getTerminator()->isEHPad())
9224 if (VIs.size() > 1) {
9227 <<
"Unable to find valid location for Debug Value, undefing:\n"
9229 DbgItem->setKillLocation();
9234 << *DbgItem <<
' ' << *VI);
9241 for (BasicBlock &BB :
F) {
9247 if (DVR.
Type != DbgVariableRecord::LocationType::Value)
9249 DbgProcessor(&DVR, &Insn);
9260bool CodeGenPrepare::placePseudoProbes(Function &
F) {
9261 bool MadeChange =
false;
9264 auto FirstInst =
Block.getFirstInsertionPt();
9265 while (FirstInst !=
Block.end() && FirstInst->isDebugOrPseudoInst())
9269 while (
I !=
Block.end()) {
9271 II->moveBefore(FirstInst);
9301bool CodeGenPrepare::splitBranchCondition(Function &
F) {
9305 bool MadeChange =
false;
9306 for (
auto &BB :
F) {
9319 if (Br1->getMetadata(LLVMContext::MD_unpredictable))
9327 Value *Cond1, *Cond2;
9330 Opc = Instruction::And;
9333 Opc = Instruction::Or;
9343 if (!IsGoodCond(Cond1) || !IsGoodCond(Cond2))
9357 Br1->setCondition(Cond1);
9362 if (
Opc == Instruction::And)
9363 Br1->setSuccessor(0, TmpBB);
9365 Br1->setSuccessor(1, TmpBB);
9370 I->removeFromParent();
9371 I->insertBefore(Br2->getIterator());
9383 if (
Opc == Instruction::Or)
9390 for (PHINode &PN : FBB->
phis()) {
9395 if (Loop *L = LI->getLoopFor(&BB))
9396 L->addBasicBlockToLoop(TmpBB, *LI);
9400 DTU->
applyUpdates({{DominatorTree::Insert, &BB, TmpBB},
9401 {DominatorTree::Insert, TmpBB,
TBB},
9402 {DominatorTree::Insert, TmpBB, FBB},
9403 {DominatorTree::Delete, &BB,
TBB}});
9407 if (
Opc == Instruction::Or) {
9427 uint64_t TrueWeight, FalseWeight;
9429 uint64_t NewTrueWeight = TrueWeight;
9430 uint64_t NewFalseWeight = TrueWeight + 2 * FalseWeight;
9434 NewTrueWeight = TrueWeight;
9435 NewFalseWeight = 2 * FalseWeight;
9458 uint64_t TrueWeight, FalseWeight;
9460 uint64_t NewTrueWeight = 2 * TrueWeight + FalseWeight;
9461 uint64_t NewFalseWeight = FalseWeight;
9465 NewTrueWeight = 2 * TrueWeight;
9466 NewFalseWeight = 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 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 isNegative() const
Determine sign of this APInt.
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()
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.
LLVM_ABI 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.
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...
LLVM_ABI 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.
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.
iterator find(const KeyT &Key)
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
VectorType::iterator erase(typename VectorType::iterator Iterator)
Remove the element given by Iterator.
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.
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)
match_combine_or< Ty... > m_CombineOr(const Ty &...Ps)
Combine pattern matchers matching any of Ps patterns.
cst_pred_ty< is_all_ones > m_AllOnes()
Match an integer or vector with all bits set.
match_bind< PHINode > m_Phi(PHINode *&PN)
Match a PHI node, capturing it if we match.
auto m_Cmp()
Matches any compare instruction and ignore it.
BinaryOp_match< LHS, RHS, Instruction::Add > m_Add(const LHS &L, const RHS &R)
BinaryOp_match< LHS, RHS, Instruction::URem > m_URem(const LHS &L, const RHS &R)
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)
match_bind< 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)
cst_pred_ty< is_one > m_One()
Match an integer 1 or a vector with all elements equal to 1.
ThreeOps_match< Cond, LHS, RHS, Instruction::Select > m_Select(const Cond &C, const LHS &L, const RHS &R)
Matches SelectInst.
auto m_BinOp()
Match an arbitrary binary operation and ignore it.
ExtractValue_match< Ind, Val_t > m_ExtractValue(const Val_t &V)
Match a single index ExtractValue instruction.
auto m_Value()
Match an arbitrary value and ignore it.
auto m_Ctpop(const Opnd0 &Op0)
auto m_Constant()
Match an arbitrary Constant and ignore it.
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.
match_immconstant_ty m_ImmConstant()
Match an arbitrary immediate Constant and ignore it.
auto m_Intrinsic(const Ts &...Ops)
Match intrinsic calls like this: m_Intrinsic<Intrinsic::fabs>(m_Value(X))
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.
brc_match< Cond_t, match_bind< BasicBlock >, match_bind< BasicBlock > > m_Br(const Cond_t &C, BasicBlock *&T, BasicBlock *&F)
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)
auto m_ConstantInt()
Match an arbitrary ConstantInt and ignore it.
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)
DXILDebugInfoMap run(Module &M)
@ 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)
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)
LLVM_ABI bool DeleteDeadPHIs(BasicBlock *BB, const TargetLibraryInfo *TLI=nullptr, MemorySSAUpdater *MSSAU=nullptr, SmallPtrSetImpl< PHINode * > *KnownNonDeadPHIs=nullptr)
Examine each PHI in the given block and delete it if it is dead.
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 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...
RelativeUniformCounterPtr ValuesPtrExpr VTableAddr 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 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...
LLVM_ABI 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.
LLVM_ABI 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.
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
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.
RelativeUniformCounterPtr ValuesPtrExpr VTableAddr Next
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...
LLVM_ABI void setFittedBranchWeights(Instruction &I, ArrayRef< uint64_t > Weights, bool IsExpected, bool ElideAllZero=false)
Variant of setBranchWeights where the Weights will be fit first to uint32_t by shifting right.
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()
LLVM_ABI void reportFatalUsageError(Error Err)
Report a fatal error that does not indicate a bug in LLVM.
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.