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;
960 BasicBlock *DestBB = findDestBlockOfMergeableEmptyBlock(BB);
962 !isMergingEmptyBlockProfitable(BB, DestBB, Preheaders.
count(BB)))
965 ResetLI |= eliminateMostlyEmptyBlock(BB);
971bool CodeGenPrepare::isMergingEmptyBlockProfitable(BasicBlock *BB,
1022 SmallPtrSet<BasicBlock *, 16> SameIncomingValueBBs;
1027 if (DestBBPred == BB)
1031 return DestPN.getIncomingValueForBlock(BB) ==
1032 DestPN.getIncomingValueForBlock(DestBBPred);
1034 SameIncomingValueBBs.
insert(DestBBPred);
1040 if (SameIncomingValueBBs.
count(Pred))
1043 BlockFrequency PredFreq = BFI->getBlockFreq(Pred);
1044 BlockFrequency
BBFreq = BFI->getBlockFreq(BB);
1046 for (
auto *SameValueBB : SameIncomingValueBBs)
1047 if (SameValueBB->getUniquePredecessor() == Pred &&
1048 DestBB == findDestBlockOfMergeableEmptyBlock(SameValueBB))
1049 BBFreq += BFI->getBlockFreq(SameValueBB);
1052 return !Limit || PredFreq <= *Limit;
1058bool CodeGenPrepare::canMergeBlocks(
const BasicBlock *BB,
1059 const BasicBlock *DestBB)
const {
1063 for (
const PHINode &PN : BB->
phis()) {
1064 for (
const User *U : PN.users()) {
1073 for (
unsigned I = 0,
E = UPN->getNumIncomingValues();
I !=
E; ++
I) {
1076 Insn->
getParent() != UPN->getIncomingBlock(
I))
1091 SmallPtrSet<const BasicBlock *, 16> BBPreds;
1094 for (
unsigned i = 0, e = BBPN->getNumIncomingValues(); i != e; ++i)
1095 BBPreds.
insert(BBPN->getIncomingBlock(i));
1103 if (BBPreds.
count(Pred)) {
1104 for (
const PHINode &PN : DestBB->
phis()) {
1105 const Value *V1 = PN.getIncomingValueForBlock(Pred);
1106 const Value *V2 = PN.getIncomingValueForBlock(BB);
1110 if (V2PN->getParent() == BB)
1111 V2 = V2PN->getIncomingValueForBlock(Pred);
1142bool CodeGenPrepare::eliminateMostlyEmptyBlock(BasicBlock *BB) {
1152 if (SinglePred != DestBB) {
1153 assert(SinglePred == BB &&
1154 "Single predecessor not the same as predecessor");
1163 FreshBBs.
insert(SinglePred);
1164 FreshBBs.
erase(DestBB);
1172 for (PHINode &PN : DestBB->
phis()) {
1174 Value *InVal = PN.removeIncomingValue(BB,
false);
1179 if (InValPhi && InValPhi->
getParent() == BB) {
1188 for (
unsigned i = 0, e = BBPN->getNumIncomingValues(); i != e; ++i)
1189 PN.addIncoming(InVal, BBPN->getIncomingBlock(i));
1192 PN.addIncoming(InVal, Pred);
1198 if (BI->hasMetadata(LLVMContext::MD_loop)) {
1206 SmallPtrSet<BasicBlock *, 8> SeenPreds;
1210 if (!PredOfDestBB.contains(Pred)) {
1211 if (SeenPreds.
insert(Pred).second)
1212 DTUpdates.
push_back({DominatorTree::Insert, Pred, DestBB});
1217 if (SeenPreds.
insert(Pred).second)
1218 DTUpdates.
push_back({DominatorTree::Delete, Pred, BB});
1220 DTUpdates.
push_back({DominatorTree::Delete, BB, DestBB});
1240 for (
auto *ThisRelocate : AllRelocateCalls) {
1241 auto K = std::make_pair(ThisRelocate->getBasePtrIndex(),
1242 ThisRelocate->getDerivedPtrIndex());
1243 RelocateIdxMap.
insert(std::make_pair(K, ThisRelocate));
1245 for (
auto &Item : RelocateIdxMap) {
1246 std::pair<unsigned, unsigned>
Key = Item.first;
1247 if (
Key.first ==
Key.second)
1252 auto BaseKey = std::make_pair(
Key.first,
Key.first);
1255 auto MaybeBase = RelocateIdxMap.
find(BaseKey);
1256 if (MaybeBase == RelocateIdxMap.
end())
1261 RelocateInstMap[MaybeBase->second].push_back(
I);
1269 for (
unsigned i = 1; i <
GEP->getNumOperands(); i++) {
1272 if (!
Op ||
Op->getZExtValue() > 20)
1276 for (
unsigned i = 1; i <
GEP->getNumOperands(); i++)
1286 bool MadeChange =
false;
1293 for (
auto R = RelocatedBase->
getParent()->getFirstInsertionPt();
1294 &*R != RelocatedBase; ++R)
1298 RelocatedBase->
moveBefore(RI->getIterator());
1305 "Not relocating a derived object of the original base object");
1306 if (ToReplace->getBasePtrIndex() == ToReplace->getDerivedPtrIndex()) {
1311 if (RelocatedBase->
getParent() != ToReplace->getParent()) {
1321 if (!Derived || Derived->getPointerOperand() !=
Base)
1330 "Should always have one since it's not a terminator");
1334 Builder.SetCurrentDebugLocation(ToReplace->getDebugLoc());
1358 Value *ActualRelocatedBase = RelocatedBase;
1359 if (RelocatedBase->
getType() !=
Base->getType()) {
1360 ActualRelocatedBase =
1361 Builder.CreateBitCast(RelocatedBase,
Base->getType());
1363 Value *Replacement =
1364 Builder.CreateGEP(Derived->getSourceElementType(), ActualRelocatedBase,
1370 Value *ActualReplacement = Replacement;
1371 if (Replacement->
getType() != ToReplace->getType()) {
1373 Builder.CreateBitCast(Replacement, ToReplace->
getType());
1376 ToReplace->eraseFromParent();
1400bool CodeGenPrepare::simplifyOffsetableRelocate(GCStatepointInst &
I) {
1401 bool MadeChange =
false;
1403 for (
auto *U :
I.users())
1410 if (AllRelocateCalls.
size() < 2)
1415 MapVector<GCRelocateInst *, SmallVector<GCRelocateInst *, 0>> RelocateInstMap;
1417 if (RelocateInstMap.
empty())
1420 for (
auto &Item : RelocateInstMap)
1434 bool MadeChange =
false;
1437 Use &TheUse = UI.getUse();
1444 UserBB = PN->getIncomingBlock(TheUse);
1452 if (
User->isEHPad())
1462 if (UserBB == DefBB)
1466 CastInst *&InsertedCast = InsertedCasts[UserBB];
1468 if (!InsertedCast) {
1476 TheUse = InsertedCast;
1502 ASC->getDestAddressSpace()))
1557static std::optional<std::pair<Instruction *, Constant *>>
1560 if (!L || L->getHeader() != PN->
getParent() || !L->getLoopLatch())
1561 return std::nullopt;
1564 if (!IVInc || LI->
getLoopFor(IVInc->getParent()) != L)
1565 return std::nullopt;
1569 return std::make_pair(IVInc, Step);
1570 return std::nullopt;
1583 return IVInc->first ==
I;
1587bool CodeGenPrepare::replaceMathCmpWithIntrinsic(BinaryOperator *BO,
1591 auto IsReplacableIVIncrement = [
this, &
Cmp](BinaryOperator *BO) {
1594 const Loop *
L = LI->getLoopFor(BO->
getParent());
1595 assert(L &&
"L should not be null after isIVIncrement()");
1597 if (LI->getLoopFor(
Cmp->getParent()) != L)
1610 return BO->
hasOneUse() && DT.dominates(
Cmp->getParent(),
L->getLoopLatch());
1612 if (BO->
getParent() !=
Cmp->getParent() && !IsReplacableIVIncrement(BO)) {
1635 if (BO->
getOpcode() == Instruction::Add &&
1636 IID == Intrinsic::usub_with_overflow) {
1643 for (Instruction &Iter : *
Cmp->getParent()) {
1646 if ((BO->
getOpcode() != Instruction::Xor && &Iter == BO) || &Iter == Cmp) {
1651 assert(InsertPt !=
nullptr &&
"Parent block did not contain cmp or binop");
1654 Value *MathOV = Builder.CreateBinaryIntrinsic(IID, Arg0, Arg1);
1655 if (BO->
getOpcode() != Instruction::Xor) {
1656 Value *Math = Builder.CreateExtractValue(MathOV, 0,
"math");
1660 "Patterns with XOr should use the BO only in the compare");
1661 Value *OV = Builder.CreateExtractValue(MathOV, 1,
"ov");
1663 Cmp->eraseFromParent();
1673 Value *
A = Cmp->getOperand(0), *
B = Cmp->getOperand(1);
1681 B = ConstantInt::get(
B->getType(), 1);
1689 for (
User *U :
A->users()) {
1700bool CodeGenPrepare::combineToUAddWithOverflow(CmpInst *Cmp,
1701 ModifyDT &ModifiedDT) {
1702 bool EdgeCase =
false;
1704 BinaryOperator *
Add;
1709 A =
Add->getOperand(0);
1710 B =
Add->getOperand(1);
1716 Add->hasNUsesOrMore(EdgeCase ? 1 : 2)))
1722 if (
Add->getParent() !=
Cmp->getParent() && !
Add->hasOneUse())
1725 if (!replaceMathCmpWithIntrinsic(
Add,
A,
B, Cmp,
1726 Intrinsic::uadd_with_overflow))
1730 ModifiedDT = ModifyDT::ModifyInstDT;
1734bool CodeGenPrepare::combineToUSubWithOverflow(CmpInst *Cmp,
1735 ModifyDT &ModifiedDT) {
1742 ICmpInst::Predicate Pred =
Cmp->getPredicate();
1743 if (Pred == ICmpInst::ICMP_UGT) {
1745 Pred = ICmpInst::ICMP_ULT;
1749 B = ConstantInt::get(
B->getType(), 1);
1750 Pred = ICmpInst::ICMP_ULT;
1755 Pred = ICmpInst::ICMP_ULT;
1757 if (Pred != ICmpInst::ICMP_ULT)
1764 BinaryOperator *
Sub =
nullptr;
1765 for (User *U : CmpVariableOperand->
users()) {
1773 const APInt *CmpC, *AddC;
1785 Sub->hasNUsesOrMore(1)))
1791 if (
Sub->getParent() !=
Cmp->getParent() && !
Sub->hasOneUse())
1794 if (!replaceMathCmpWithIntrinsic(
Sub,
Sub->getOperand(0),
Sub->getOperand(1),
1795 Cmp, Intrinsic::usub_with_overflow))
1799 ModifiedDT = ModifyDT::ModifyInstDT;
1806bool CodeGenPrepare::unfoldPowerOf2Test(CmpInst *Cmp) {
1819 if (!IsStrictlyPowerOf2Test && !IsPowerOf2OrZeroTest)
1825 Type *OpTy =
X->getType();
1833 if (Pred == ICmpInst::ICMP_EQ) {
1834 Cmp->setOperand(1, ConstantInt::get(OpTy, 2));
1835 Cmp->setPredicate(ICmpInst::ICMP_ULT);
1837 Cmp->setPredicate(ICmpInst::ICMP_UGT);
1843 if (IsPowerOf2OrZeroTest ||
1854 NewCmp = Builder.CreateICmp(NewPred,
And, ConstantInt::getNullValue(OpTy));
1863 NewCmp = Builder.CreateICmp(NewPred,
Xor,
Sub);
1866 Cmp->replaceAllUsesWith(NewCmp);
1886 bool UsedInPhiOrCurrentBlock =
any_of(Cmp->users(), [Cmp](
User *U) {
1887 return isa<PHINode>(U) ||
1888 cast<Instruction>(U)->getParent() == Cmp->getParent();
1893 if (UsedInPhiOrCurrentBlock && Cmp->getOperand(0)->getType()->isIntegerTy() &&
1894 Cmp->getOperand(0)->getType()->getScalarSizeInBits() >
1895 DL.getLargestLegalIntTypeSizeInBits())
1901 bool MadeChange =
false;
1904 Use &TheUse = UI.getUse();
1919 if (UserBB == DefBB)
1923 CmpInst *&InsertedCmp = InsertedCmps[UserBB];
1929 Cmp->getOperand(0), Cmp->getOperand(1),
"");
1936 TheUse = InsertedCmp;
1942 if (Cmp->use_empty()) {
1943 Cmp->eraseFromParent();
1980 for (
User *U : Cmp->users()) {
2002 if (CmpBB != FalseBB)
2005 Value *CmpOp0 = Cmp->getOperand(0), *CmpOp1 = Cmp->getOperand(1);
2019 for (
User *U : Cmp->users()) {
2021 BI->swapSuccessors();
2027 SI->swapProfMetadata();
2039 Value *Op0 = Cmp->getOperand(0);
2040 Value *Op1 = Cmp->getOperand(1);
2049 unsigned NumInspected = 0;
2052 if (++NumInspected > 128)
2060 if (GoodToSwap > 0) {
2061 Cmp->swapOperands();
2081 auto ShouldReverseTransform = [](
FPClassTest ClassTest) {
2084 auto [ClassVal, ClassTest] =
2090 if (!ShouldReverseTransform(ClassTest) && !ShouldReverseTransform(~ClassTest))
2094 Value *IsFPClass = Builder.createIsFPClass(ClassVal, ClassTest);
2095 Cmp->replaceAllUsesWith(IsFPClass);
2103 Value *Incr, *RemAmt;
2108 Value *AddInst, *AddOffset;
2111 if (PN !=
nullptr) {
2113 AddOffset =
nullptr;
2122 if (PN !=
nullptr) {
2135 if (PN->getNumIncomingValues() != 2)
2140 if (!L || !L->getLoopPreheader() || !L->getLoopLatch())
2144 if (!L->contains(Rem))
2148 if (!L->isLoopInvariant(RemAmt))
2152 if (AddOffset && !L->isLoopInvariant(AddOffset))
2173 AddInstOut = AddInst;
2174 AddOffsetOut = AddOffset;
2193 Value *AddOffset, *RemAmt, *AddInst;
2196 AddOffset, LoopIncrPN))
2221 assert(AddOffset &&
"We found an add but missing values");
2240 Builder.SetInsertPoint(LoopIncrPN);
2241 PHINode *NewRem = Builder.CreatePHI(Ty, 2);
2246 Value *RemAdd = Builder.CreateNUWAdd(NewRem, ConstantInt::get(Ty, 1));
2251 NewRem->
addIncoming(Start, L->getLoopPreheader());
2256 FreshBBs.
insert(L->getLoopLatch());
2267bool CodeGenPrepare::optimizeURem(Instruction *Rem) {
2273bool CodeGenPrepare::optimizeCmp(CmpInst *Cmp, ModifyDT &ModifiedDT) {
2277 if (combineToUAddWithOverflow(Cmp, ModifiedDT))
2280 if (combineToUSubWithOverflow(Cmp, ModifiedDT))
2283 if (unfoldPowerOf2Test(Cmp))
2304 SetOfInstrs &InsertedInsts) {
2307 assert(!InsertedInsts.count(AndI) &&
2308 "Attempting to optimize already optimized and instruction");
2309 (void)InsertedInsts;
2323 for (
auto *U : AndI->
users()) {
2331 if (!CmpC || !CmpC->
isZero())
2346 Use &TheUse = UI.getUse();
2364 TheUse = InsertedAnd;
2381 if (
User->getOpcode() != Instruction::And ||
2387 if ((Cimm & (Cimm + 1)).getBoolValue())
2401 bool MadeChange =
false;
2404 TruncE = TruncI->user_end();
2405 TruncUI != TruncE;) {
2407 Use &TruncTheUse = TruncUI.getUse();
2432 if (UserBB == TruncUserBB)
2436 CastInst *&InsertedTrunc = InsertedTruncs[TruncUserBB];
2438 if (!InsertedShift && !InsertedTrunc) {
2442 if (ShiftI->
getOpcode() == Instruction::AShr)
2444 BinaryOperator::CreateAShr(ShiftI->
getOperand(0), CI,
"");
2447 BinaryOperator::CreateLShr(ShiftI->
getOperand(0), CI,
"");
2455 TruncInsertPt.setHeadBit(
true);
2456 assert(TruncInsertPt != TruncUserBB->
end());
2460 InsertedTrunc->
insertBefore(*TruncUserBB, TruncInsertPt);
2461 InsertedTrunc->
setDebugLoc(TruncI->getDebugLoc());
2465 TruncTheUse = InsertedTrunc;
2498 bool MadeChange =
false;
2501 Use &TheUse = UI.getUse();
2515 if (UserBB == DefBB) {
2543 if (!InsertedShift) {
2547 if (ShiftI->
getOpcode() == Instruction::AShr)
2549 BinaryOperator::CreateAShr(ShiftI->
getOperand(0), CI,
"");
2552 BinaryOperator::CreateLShr(ShiftI->
getOperand(0), CI,
"");
2560 TheUse = InsertedShift;
2608 unsigned SizeInBits = Ty->getScalarSizeInBits();
2609 if (Ty->isVectorTy())
2620 nullptr,
"cond.false");
2622 FreshBBs.
insert(CallBlock);
2629 SplitPt.setHeadBit(
true);
2631 nullptr,
"cond.end");
2633 FreshBBs.
insert(EndBlock);
2638 Builder.SetCurrentDebugLocation(CountZeros->
getDebugLoc());
2645 Op = Builder.CreateFreeze(
Op,
Op->getName() +
".fr");
2646 Value *Cmp = Builder.CreateICmpEQ(
Op, Zero,
"cmpz");
2647 Builder.CreateCondBr(Cmp, EndBlock, CallBlock);
2653 Builder.SetInsertPoint(EndBlock, EndBlock->
begin());
2654 PHINode *PN = Builder.CreatePHI(Ty, 2,
"ctz");
2664 ModifiedDT = ModifyDT::ModifyBBDT;
2668bool CodeGenPrepare::optimizeCallInst(CallInst *CI, ModifyDT &ModifiedDT) {
2672 if (CI->
isInlineAsm() && optimizeInlineAsmInst(CI))
2680 for (
auto &Arg : CI->
args()) {
2685 if (!Arg->getType()->isPointerTy())
2687 APInt
Offset(
DL->getIndexSizeInBits(
2690 Value *Val = Arg->stripAndAccumulateInBoundsConstantOffsets(*
DL,
Offset);
2691 uint64_t Offset2 =
Offset.getLimitedValue();
2697 if (AllocaSize && AllocaSize->getKnownMinValue() >= MinSize + Offset2)
2715 MaybeAlign MIDestAlign =
MI->getDestAlign();
2716 if (!MIDestAlign || DestAlign > *MIDestAlign)
2717 MI->setDestAlignment(DestAlign);
2719 MaybeAlign MTISrcAlign = MTI->getSourceAlign();
2721 if (!MTISrcAlign || SrcAlign > *MTISrcAlign)
2722 MTI->setSourceAlignment(SrcAlign);
2732 for (
auto &Arg : CI->
args()) {
2733 if (!Arg->getType()->isPointerTy())
2735 unsigned AS = Arg->getType()->getPointerAddressSpace();
2736 if (optimizeMemoryInst(CI, Arg, Arg->getType(), AS))
2742 switch (
II->getIntrinsicID()) {
2745 case Intrinsic::assume:
2747 case Intrinsic::allow_runtime_check:
2748 case Intrinsic::allow_ubsan_check:
2749 case Intrinsic::experimental_widenable_condition: {
2753 if (
II->use_empty()) {
2754 II->eraseFromParent();
2758 resetIteratorIfInvalidatedWhileCalling(BB, [&]() {
2763 case Intrinsic::objectsize:
2765 case Intrinsic::is_constant:
2767 case Intrinsic::aarch64_stlxr:
2768 case Intrinsic::aarch64_stxr: {
2777 InsertedInsts.insert(ExtVal);
2781 case Intrinsic::launder_invariant_group:
2782 case Intrinsic::strip_invariant_group: {
2783 Value *ArgVal =
II->getArgOperand(0);
2784 auto it = LargeOffsetGEPMap.
find(
II);
2785 if (it != LargeOffsetGEPMap.
end()) {
2789 auto GEPs = std::move(it->second);
2790 LargeOffsetGEPMap[ArgVal].append(GEPs.begin(), GEPs.end());
2795 II->eraseFromParent();
2798 case Intrinsic::cttz:
2799 case Intrinsic::ctlz:
2803 case Intrinsic::fshl:
2804 case Intrinsic::fshr:
2805 return optimizeFunnelShift(
II);
2806 case Intrinsic::masked_gather:
2807 return optimizeGatherScatterInst(
II,
II->getArgOperand(0));
2808 case Intrinsic::masked_scatter:
2809 return optimizeGatherScatterInst(
II,
II->getArgOperand(1));
2810 case Intrinsic::masked_load:
2813 if (VT->getNumElements() == 1) {
2814 Value *PtrVal =
II->getArgOperand(0);
2816 if (optimizeMemoryInst(
II, PtrVal, VT->getElementType(), AS))
2821 case Intrinsic::masked_store:
2825 if (VT->getNumElements() == 1) {
2826 Value *PtrVal =
II->getArgOperand(1);
2828 if (optimizeMemoryInst(
II, PtrVal, VT->getElementType(), AS))
2833 case Intrinsic::umul_with_overflow:
2834 return optimizeMulWithOverflow(
II,
false, ModifiedDT);
2835 case Intrinsic::smul_with_overflow:
2836 return optimizeMulWithOverflow(
II,
true, ModifiedDT);
2839 SmallVector<Value *, 2> PtrOps;
2842 while (!PtrOps.
empty()) {
2845 if (optimizeMemoryInst(
II, PtrVal, AccessTy, AS))
2859 FortifiedLibCallSimplifier Simplifier(TLInfo,
true);
2861 if (
Value *V = Simplifier.optimizeCall(CI, Builder)) {
2871 auto GetUniformReturnValue = [](
const Function *
F) -> GlobalVariable * {
2872 if (!
F->getReturnType()->isPointerTy())
2875 GlobalVariable *UniformValue =
nullptr;
2876 for (
auto &BB : *
F) {
2881 else if (V != UniformValue)
2889 return UniformValue;
2892 if (
Callee->hasExactDefinition()) {
2893 if (GlobalVariable *RV = GetUniformReturnValue(Callee)) {
2894 bool MadeChange =
false;
2920 switch (
II->getIntrinsicID()) {
2921 case Intrinsic::memset:
2922 case Intrinsic::memcpy:
2923 case Intrinsic::memmove:
2931 if (Callee && TLInfo && TLInfo->
getLibFunc(*Callee, LF))
2933 case LibFunc_strcpy:
2934 case LibFunc_strncpy:
2935 case LibFunc_strcat:
2936 case LibFunc_strncat:
2977bool CodeGenPrepare::dupRetToEnableTailCallOpts(BasicBlock *BB,
2978 ModifyDT &ModifiedDT) {
2986 assert(LI->getLoopFor(BB) ==
nullptr &&
"A return block cannot be in a loop");
2988 PHINode *PN =
nullptr;
2989 ExtractValueInst *EVI =
nullptr;
2990 BitCastInst *BCI =
nullptr;
3010 auto isLifetimeEndOrBitCastFor = [](
const Instruction *Inst) {
3016 return II->getIntrinsicID() == Intrinsic::lifetime_end;
3022 auto isFakeUse = [&FakeUses](
const Instruction *Inst) {
3024 II &&
II->getIntrinsicID() == Intrinsic::fake_use) {
3046 isLifetimeEndOrBitCastFor(&*BI) || isFakeUse(&*BI))
3053 auto MayBePermittedAsTailCall = [&](
const auto *CI) {
3070 MayBePermittedAsTailCall(CI)) {
3091 MayBePermittedAsTailCall(CI)) {
3098 SmallPtrSet<BasicBlock *, 4> VisitedBBs;
3100 if (!VisitedBBs.
insert(Pred).second)
3102 if (Instruction *
I = Pred->rbegin()->getPrevNode()) {
3104 if (CI && CI->
use_empty() && MayBePermittedAsTailCall(CI)) {
3119 for (
auto const &TailCallBB : TailCallBBs) {
3129 BFI->getBlockFreq(BB) >= BFI->getBlockFreq(TailCallBB));
3130 BFI->setBlockFreq(BB,
3131 (BFI->getBlockFreq(BB) - BFI->getBlockFreq(TailCallBB)));
3132 ModifiedDT = ModifyDT::ModifyBBDT;
3141 for (
auto *CI : CallInsts) {
3142 for (
auto const *FakeUse : FakeUses) {
3143 auto *ClonedInst = FakeUse->clone();
3161struct ExtAddrMode :
public TargetLowering::AddrMode {
3162 Value *BaseReg =
nullptr;
3163 Value *ScaledReg =
nullptr;
3164 Value *OriginalValue =
nullptr;
3165 bool InBounds =
true;
3169 BaseRegField = 0x01,
3171 BaseOffsField = 0x04,
3172 ScaledRegField = 0x08,
3174 MultipleFields = 0xff
3177 ExtAddrMode() =
default;
3179 void print(raw_ostream &OS)
const;
3186 if (ScaledReg == From)
3190 FieldName
compare(
const ExtAddrMode &other) {
3193 if (BaseReg && other.
BaseReg &&
3195 return MultipleFields;
3196 if (BaseGV && other.BaseGV && BaseGV->getType() != other.BaseGV->getType())
3197 return MultipleFields;
3200 return MultipleFields;
3203 if (InBounds != other.InBounds)
3204 return MultipleFields;
3207 unsigned Result = NoField;
3210 if (BaseGV != other.BaseGV)
3212 if (BaseOffs != other.BaseOffs)
3215 Result |= ScaledRegField;
3218 if (Scale && other.
Scale && Scale != other.
Scale)
3222 return MultipleFields;
3224 return static_cast<FieldName
>(
Result);
3234 return !BaseOffs && !Scale && !(BaseGV &&
BaseReg);
3245 case ScaledRegField:
3252 void SetCombinedField(FieldName
Field,
Value *V,
3253 const SmallVectorImpl<ExtAddrMode> &AddrModes) {
3258 case ExtAddrMode::BaseRegField:
3261 case ExtAddrMode::BaseGVField:
3264 assert(BaseReg ==
nullptr);
3268 case ExtAddrMode::ScaledRegField:
3273 for (
const ExtAddrMode &AM : AddrModes)
3279 case ExtAddrMode::BaseOffsField:
3282 assert(ScaledReg ==
nullptr);
3292static inline raw_ostream &
operator<<(raw_ostream &OS,
const ExtAddrMode &AM) {
3298#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
3299void ExtAddrMode::print(raw_ostream &OS)
const {
3300 bool NeedPlus =
false;
3306 BaseGV->printAsOperand(OS,
false);
3311 OS << (NeedPlus ?
" + " :
"") << BaseOffs;
3316 OS << (NeedPlus ?
" + " :
"") <<
"Base:";
3317 BaseReg->printAsOperand(OS,
false);
3321 OS << (NeedPlus ?
" + " :
"") << Scale <<
"*";
3344class TypePromotionTransaction {
3348 class TypePromotionAction {
3356 TypePromotionAction(Instruction *Inst) : Inst(Inst) {}
3358 virtual ~TypePromotionAction() =
default;
3365 virtual void undo() = 0;
3370 virtual void commit() {
3376 class InsertionHandler {
3385 std::optional<DbgRecord::self_iterator> BeforeDbgRecord = std::nullopt;
3388 bool HasPrevInstruction;
3392 InsertionHandler(Instruction *Inst) {
3400 if (HasPrevInstruction) {
3408 void insert(Instruction *Inst) {
3409 if (HasPrevInstruction) {
3421 Inst->
getParent()->reinsertInstInDbgRecords(Inst, BeforeDbgRecord);
3426 class InstructionMoveBefore :
public TypePromotionAction {
3428 InsertionHandler Position;
3433 : TypePromotionAction(Inst), Position(Inst) {
3434 LLVM_DEBUG(
dbgs() <<
"Do: move: " << *Inst <<
"\nbefore: " << *Before
3440 void undo()
override {
3442 Position.insert(Inst);
3447 class OperandSetter :
public TypePromotionAction {
3456 OperandSetter(Instruction *Inst,
unsigned Idx,
Value *NewVal)
3457 : TypePromotionAction(Inst), Idx(Idx) {
3459 <<
"for:" << *Inst <<
"\n"
3460 <<
"with:" << *NewVal <<
"\n");
3466 void undo()
override {
3468 <<
"for: " << *Inst <<
"\n"
3469 <<
"with: " << *Origin <<
"\n");
3476 class OperandsHider :
public TypePromotionAction {
3478 SmallVector<Value *, 4> OriginalValues;
3482 OperandsHider(Instruction *Inst) : TypePromotionAction(Inst) {
3485 OriginalValues.
reserve(NumOpnds);
3486 for (
unsigned It = 0; It < NumOpnds; ++It) {
3498 void undo()
override {
3500 for (
unsigned It = 0, EndIt = OriginalValues.
size(); It != EndIt; ++It)
3506 class TruncBuilder :
public TypePromotionAction {
3513 TruncBuilder(Instruction *Opnd,
Type *Ty) : TypePromotionAction(Opnd) {
3515 Builder.SetCurrentDebugLocation(
DebugLoc());
3516 Val = Builder.CreateTrunc(Opnd, Ty,
"promoted");
3521 Value *getBuiltValue() {
return Val; }
3524 void undo()
override {
3527 IVal->eraseFromParent();
3532 class SExtBuilder :
public TypePromotionAction {
3539 SExtBuilder(Instruction *InsertPt,
Value *Opnd,
Type *Ty)
3540 : TypePromotionAction(InsertPt) {
3542 Val = Builder.CreateSExt(Opnd, Ty,
"promoted");
3547 Value *getBuiltValue() {
return Val; }
3550 void undo()
override {
3553 IVal->eraseFromParent();
3558 class ZExtBuilder :
public TypePromotionAction {
3565 ZExtBuilder(Instruction *InsertPt,
Value *Opnd,
Type *Ty)
3566 : TypePromotionAction(InsertPt) {
3568 Builder.SetCurrentDebugLocation(
DebugLoc());
3569 Val = Builder.CreateZExt(Opnd, Ty,
"promoted");
3574 Value *getBuiltValue() {
return Val; }
3577 void undo()
override {
3580 IVal->eraseFromParent();
3585 class TypeMutator :
public TypePromotionAction {
3591 TypeMutator(Instruction *Inst,
Type *NewTy)
3592 : TypePromotionAction(Inst), OrigTy(Inst->
getType()) {
3593 LLVM_DEBUG(
dbgs() <<
"Do: MutateType: " << *Inst <<
" with " << *NewTy
3599 void undo()
override {
3600 LLVM_DEBUG(
dbgs() <<
"Undo: MutateType: " << *Inst <<
" with " << *OrigTy
3607 class UsesReplacer :
public TypePromotionAction {
3609 struct InstructionAndIdx {
3616 InstructionAndIdx(Instruction *Inst,
unsigned Idx)
3617 : Inst(Inst), Idx(Idx) {}
3623 SmallVector<DbgVariableRecord *, 1> DbgVariableRecords;
3633 UsesReplacer(Instruction *Inst,
Value *New)
3634 : TypePromotionAction(Inst),
New(
New) {
3635 LLVM_DEBUG(
dbgs() <<
"Do: UsersReplacer: " << *Inst <<
" with " << *New
3638 for (Use &U : Inst->
uses()) {
3640 OriginalUses.
push_back(InstructionAndIdx(UserI,
U.getOperandNo()));
3651 void undo()
override {
3653 for (InstructionAndIdx &Use : OriginalUses)
3654 Use.Inst->setOperand(
Use.Idx, Inst);
3659 for (DbgVariableRecord *DVR : DbgVariableRecords)
3660 DVR->replaceVariableLocationOp(New, Inst);
3665 class InstructionRemover :
public TypePromotionAction {
3667 InsertionHandler Inserter;
3671 OperandsHider Hider;
3674 UsesReplacer *Replacer =
nullptr;
3677 SetOfInstrs &RemovedInsts;
3684 InstructionRemover(Instruction *Inst, SetOfInstrs &RemovedInsts,
3685 Value *New =
nullptr)
3686 : TypePromotionAction(Inst), Inserter(Inst), Hider(Inst),
3687 RemovedInsts(RemovedInsts) {
3689 Replacer =
new UsesReplacer(Inst, New);
3690 LLVM_DEBUG(
dbgs() <<
"Do: InstructionRemover: " << *Inst <<
"\n");
3691 RemovedInsts.insert(Inst);
3698 ~InstructionRemover()
override {
delete Replacer; }
3700 InstructionRemover &operator=(
const InstructionRemover &other) =
delete;
3701 InstructionRemover(
const InstructionRemover &other) =
delete;
3705 void undo()
override {
3706 LLVM_DEBUG(
dbgs() <<
"Undo: InstructionRemover: " << *Inst <<
"\n");
3707 Inserter.insert(Inst);
3711 RemovedInsts.erase(Inst);
3719 using ConstRestorationPt =
const TypePromotionAction *;
3721 TypePromotionTransaction(SetOfInstrs &RemovedInsts)
3722 : RemovedInsts(RemovedInsts) {}
3729 void rollback(ConstRestorationPt Point);
3732 ConstRestorationPt getRestorationPoint()
const;
3737 void setOperand(Instruction *Inst,
unsigned Idx,
Value *NewVal);
3746 void mutateType(Instruction *Inst,
Type *NewTy);
3749 Value *createTrunc(Instruction *Opnd,
Type *Ty);
3762 SmallVectorImpl<std::unique_ptr<TypePromotionAction>>::iterator;
3764 SetOfInstrs &RemovedInsts;
3769void TypePromotionTransaction::setOperand(Instruction *Inst,
unsigned Idx,
3771 Actions.push_back(std::make_unique<TypePromotionTransaction::OperandSetter>(
3772 Inst, Idx, NewVal));
3775void TypePromotionTransaction::eraseInstruction(Instruction *Inst,
3778 std::make_unique<TypePromotionTransaction::InstructionRemover>(
3779 Inst, RemovedInsts, NewVal));
3782void TypePromotionTransaction::replaceAllUsesWith(Instruction *Inst,
3785 std::make_unique<TypePromotionTransaction::UsesReplacer>(Inst, New));
3788void TypePromotionTransaction::mutateType(Instruction *Inst,
Type *NewTy) {
3790 std::make_unique<TypePromotionTransaction::TypeMutator>(Inst, NewTy));
3793Value *TypePromotionTransaction::createTrunc(Instruction *Opnd,
Type *Ty) {
3794 std::unique_ptr<TruncBuilder> Ptr(
new TruncBuilder(Opnd, Ty));
3795 Value *Val = Ptr->getBuiltValue();
3796 Actions.push_back(std::move(Ptr));
3800Value *TypePromotionTransaction::createSExt(Instruction *Inst,
Value *Opnd,
3802 std::unique_ptr<SExtBuilder> Ptr(
new SExtBuilder(Inst, Opnd, Ty));
3803 Value *Val = Ptr->getBuiltValue();
3804 Actions.push_back(std::move(Ptr));
3808Value *TypePromotionTransaction::createZExt(Instruction *Inst,
Value *Opnd,
3810 std::unique_ptr<ZExtBuilder> Ptr(
new ZExtBuilder(Inst, Opnd, Ty));
3811 Value *Val = Ptr->getBuiltValue();
3812 Actions.push_back(std::move(Ptr));
3816TypePromotionTransaction::ConstRestorationPt
3817TypePromotionTransaction::getRestorationPoint()
const {
3818 return !Actions.empty() ? Actions.back().get() :
nullptr;
3821bool TypePromotionTransaction::commit() {
3822 for (std::unique_ptr<TypePromotionAction> &Action : Actions)
3829void TypePromotionTransaction::rollback(
3830 TypePromotionTransaction::ConstRestorationPt Point) {
3831 while (!Actions.empty() && Point != Actions.back().get()) {
3832 std::unique_ptr<TypePromotionAction> Curr = Actions.pop_back_val();
3842class AddressingModeMatcher {
3843 SmallVectorImpl<Instruction *> &AddrModeInsts;
3844 const TargetLowering &TLI;
3845 const TargetRegisterInfo &
TRI;
3846 const DataLayout &
DL;
3848 const std::function<
const DominatorTree &()> getDTFn;
3861 const SetOfInstrs &InsertedInsts;
3864 InstrToOrigTy &PromotedInsts;
3867 TypePromotionTransaction &TPT;
3870 std::pair<AssertingVH<GetElementPtrInst>, int64_t> &LargeOffsetGEP;
3874 bool IgnoreProfitability;
3877 bool OptSize =
false;
3879 ProfileSummaryInfo *PSI;
3880 BlockFrequencyInfo *BFI;
3882 AddressingModeMatcher(
3883 SmallVectorImpl<Instruction *> &AMI,
const TargetLowering &TLI,
3884 const TargetRegisterInfo &
TRI,
const LoopInfo &LI,
3885 const std::function<
const DominatorTree &()> getDTFn,
Type *AT,
3886 unsigned AS, Instruction *
MI, ExtAddrMode &AM,
3887 const SetOfInstrs &InsertedInsts, InstrToOrigTy &PromotedInsts,
3888 TypePromotionTransaction &TPT,
3889 std::pair<AssertingVH<GetElementPtrInst>, int64_t> &LargeOffsetGEP,
3890 bool OptSize, ProfileSummaryInfo *PSI, BlockFrequencyInfo *BFI)
3891 : AddrModeInsts(AMI), TLI(TLI),
TRI(
TRI),
3892 DL(
MI->getDataLayout()), LI(LI), getDTFn(getDTFn),
3893 AccessTy(AT), AddrSpace(AS), MemoryInst(
MI),
AddrMode(AM),
3894 InsertedInsts(InsertedInsts), PromotedInsts(PromotedInsts), TPT(TPT),
3895 LargeOffsetGEP(LargeOffsetGEP), OptSize(OptSize), PSI(PSI), BFI(BFI) {
3896 IgnoreProfitability =
false;
3908 Match(
Value *V,
Type *AccessTy,
unsigned AS, Instruction *MemoryInst,
3909 SmallVectorImpl<Instruction *> &AddrModeInsts,
3910 const TargetLowering &TLI,
const LoopInfo &LI,
3911 const std::function<
const DominatorTree &()> getDTFn,
3912 const TargetRegisterInfo &
TRI,
const SetOfInstrs &InsertedInsts,
3913 InstrToOrigTy &PromotedInsts, TypePromotionTransaction &TPT,
3914 std::pair<AssertingVH<GetElementPtrInst>, int64_t> &LargeOffsetGEP,
3915 bool OptSize, ProfileSummaryInfo *PSI, BlockFrequencyInfo *BFI) {
3918 bool Success = AddressingModeMatcher(AddrModeInsts, TLI,
TRI, LI, getDTFn,
3919 AccessTy, AS, MemoryInst, Result,
3920 InsertedInsts, PromotedInsts, TPT,
3921 LargeOffsetGEP, OptSize, PSI, BFI)
3929 bool matchScaledValue(
Value *ScaleReg, int64_t Scale,
unsigned Depth);
3931 bool matchOperationAddr(User *AddrInst,
unsigned Opcode,
unsigned Depth,
3932 bool *MovedAway =
nullptr);
3933 bool isProfitableToFoldIntoAddressingMode(Instruction *
I,
3934 ExtAddrMode &AMBefore,
3935 ExtAddrMode &AMAfter);
3936 bool valueAlreadyLiveAtInst(
Value *Val,
Value *KnownLive1,
Value *KnownLive2);
3937 bool isPromotionProfitable(
unsigned NewCost,
unsigned OldCost,
3938 Value *PromotedOperand)
const;
3944class PhiNodeSetIterator {
3945 PhiNodeSet *
const Set;
3946 size_t CurrentIndex = 0;
3951 PhiNodeSetIterator(PhiNodeSet *
const Set,
size_t Start);
3953 PhiNodeSetIterator &operator++();
3969 friend class PhiNodeSetIterator;
3971 using MapType = SmallDenseMap<PHINode *, size_t, 32>;
3972 using iterator = PhiNodeSetIterator;
3987 size_t FirstValidElement = 0;
3993 bool insert(PHINode *Ptr) {
3994 if (NodeMap.insert(std::make_pair(Ptr,
NodeList.
size())).second) {
4004 bool erase(PHINode *Ptr) {
4005 if (NodeMap.erase(Ptr)) {
4006 SkipRemovedElements(FirstValidElement);
4016 FirstValidElement = 0;
4022 if (FirstValidElement == 0)
4023 SkipRemovedElements(FirstValidElement);
4024 return PhiNodeSetIterator(
this, FirstValidElement);
4031 size_t size()
const {
return NodeMap.size(); }
4034 size_t count(PHINode *Ptr)
const {
return NodeMap.count(Ptr); }
4042 void SkipRemovedElements(
size_t &CurrentIndex) {
4044 auto it = NodeMap.find(NodeList[CurrentIndex]);
4047 if (it != NodeMap.end() && it->second == CurrentIndex)
4054PhiNodeSetIterator::PhiNodeSetIterator(PhiNodeSet *
const Set,
size_t Start)
4057PHINode *PhiNodeSetIterator::operator*()
const {
4059 "PhiNodeSet access out of range");
4060 return Set->NodeList[CurrentIndex];
4063PhiNodeSetIterator &PhiNodeSetIterator::operator++() {
4065 "PhiNodeSet access out of range");
4067 Set->SkipRemovedElements(CurrentIndex);
4071bool PhiNodeSetIterator::operator==(
const PhiNodeSetIterator &
RHS)
const {
4072 return CurrentIndex ==
RHS.CurrentIndex;
4075bool PhiNodeSetIterator::operator!=(
const PhiNodeSetIterator &
RHS)
const {
4076 return !((*this) ==
RHS);
4082class SimplificationTracker {
4083 DenseMap<Value *, Value *> Storage;
4086 PhiNodeSet AllPhiNodes;
4088 SmallPtrSet<SelectInst *, 32> AllSelectNodes;
4093 auto SV = Storage.
find(V);
4094 if (SV == Storage.
end())
4102 void ReplacePhi(PHINode *From, PHINode *To) {
4103 Value *OldReplacement = Get(From);
4104 while (OldReplacement != From) {
4107 OldReplacement = Get(From);
4109 assert(To && Get(To) == To &&
"Replacement PHI node is already replaced.");
4112 AllPhiNodes.erase(From);
4116 PhiNodeSet &newPhiNodes() {
return AllPhiNodes; }
4118 void insertNewPhi(PHINode *PN) { AllPhiNodes.insert(PN); }
4120 void insertNewSelect(SelectInst *SI) { AllSelectNodes.
insert(SI); }
4122 unsigned countNewPhiNodes()
const {
return AllPhiNodes.size(); }
4124 unsigned countNewSelectNodes()
const {
return AllSelectNodes.
size(); }
4126 void destroyNewNodes(
Type *CommonType) {
4129 for (
auto *
I : AllPhiNodes) {
4130 I->replaceAllUsesWith(Dummy);
4131 I->eraseFromParent();
4133 AllPhiNodes.clear();
4134 for (
auto *
I : AllSelectNodes) {
4135 I->replaceAllUsesWith(Dummy);
4136 I->eraseFromParent();
4138 AllSelectNodes.clear();
4143class AddressingModeCombiner {
4144 typedef DenseMap<Value *, Value *> FoldAddrToValueMapping;
4145 typedef std::pair<PHINode *, PHINode *> PHIPair;
4152 ExtAddrMode::FieldName DifferentField = ExtAddrMode::NoField;
4155 bool AllAddrModesTrivial =
true;
4158 Type *CommonType =
nullptr;
4160 const DataLayout &
DL;
4166 Value *CommonValue =
nullptr;
4169 AddressingModeCombiner(
const DataLayout &
DL,
Value *OriginalValue)
4170 :
DL(
DL), Original(OriginalValue) {}
4172 ~AddressingModeCombiner() { eraseCommonValueIfDead(); }
4175 const ExtAddrMode &
getAddrMode()
const {
return AddrModes[0]; }
4180 bool addNewAddrMode(ExtAddrMode &NewAddrMode) {
4184 AllAddrModesTrivial = AllAddrModesTrivial && NewAddrMode.isTrivial();
4187 if (AddrModes.
empty()) {
4195 ExtAddrMode::FieldName ThisDifferentField =
4196 AddrModes[0].compare(NewAddrMode);
4197 if (DifferentField == ExtAddrMode::NoField)
4198 DifferentField = ThisDifferentField;
4199 else if (DifferentField != ThisDifferentField)
4200 DifferentField = ExtAddrMode::MultipleFields;
4203 bool CanHandle = DifferentField != ExtAddrMode::MultipleFields;
4206 CanHandle = CanHandle && DifferentField != ExtAddrMode::ScaleField;
4211 CanHandle = CanHandle && (DifferentField != ExtAddrMode::BaseOffsField ||
4216 CanHandle = CanHandle && (DifferentField != ExtAddrMode::BaseGVField ||
4217 !NewAddrMode.HasBaseReg);
4234 bool combineAddrModes() {
4236 if (AddrModes.
size() == 0)
4240 if (AddrModes.
size() == 1 || DifferentField == ExtAddrMode::NoField)
4245 if (AllAddrModesTrivial)
4248 if (!addrModeCombiningAllowed())
4254 FoldAddrToValueMapping
Map;
4255 if (!initializeMap(Map))
4258 CommonValue = findCommon(Map);
4260 AddrModes[0].SetCombinedField(DifferentField, CommonValue, AddrModes);
4261 return CommonValue !=
nullptr;
4267 void eraseCommonValueIfDead() {
4268 if (CommonValue && CommonValue->
use_empty())
4270 CommonInst->eraseFromParent();
4278 bool initializeMap(FoldAddrToValueMapping &Map) {
4281 SmallVector<Value *, 2> NullValue;
4282 Type *IntPtrTy =
DL.getIntPtrType(AddrModes[0].OriginalValue->
getType());
4283 for (
auto &AM : AddrModes) {
4284 Value *DV = AM.GetFieldAsValue(DifferentField, IntPtrTy);
4287 if (CommonType && CommonType !=
Type)
4290 Map[AM.OriginalValue] = DV;
4295 assert(CommonType &&
"At least one non-null value must be!");
4296 for (
auto *V : NullValue)
4324 Value *findCommon(FoldAddrToValueMapping &Map) {
4332 SimplificationTracker
ST;
4337 InsertPlaceholders(Map, TraverseOrder, ST);
4340 FillPlaceholders(Map, TraverseOrder, ST);
4343 ST.destroyNewNodes(CommonType);
4348 unsigned PhiNotMatchedCount = 0;
4350 ST.destroyNewNodes(CommonType);
4354 auto *
Result =
ST.Get(
Map.find(Original)->second);
4356 NumMemoryInstsPhiCreated +=
ST.countNewPhiNodes() + PhiNotMatchedCount;
4357 NumMemoryInstsSelectCreated +=
ST.countNewSelectNodes();
4364 bool MatchPhiNode(PHINode *
PHI, PHINode *Candidate,
4365 SmallSetVector<PHIPair, 8> &Matcher,
4366 PhiNodeSet &PhiNodesToMatch) {
4369 SmallPtrSet<PHINode *, 8> MatchedPHIs;
4372 SmallSet<PHIPair, 8> Visited;
4373 while (!WorkList.
empty()) {
4375 if (!Visited.
insert(Item).second)
4382 for (
auto *
B : Item.first->blocks()) {
4383 Value *FirstValue = Item.first->getIncomingValueForBlock(
B);
4384 Value *SecondValue = Item.second->getIncomingValueForBlock(
B);
4385 if (FirstValue == SecondValue)
4395 if (!FirstPhi || !SecondPhi || !PhiNodesToMatch.count(FirstPhi) ||
4400 if (Matcher.
count({FirstPhi, SecondPhi}))
4405 if (MatchedPHIs.
insert(FirstPhi).second)
4406 Matcher.
insert({FirstPhi, SecondPhi});
4408 WorkList.
push_back({FirstPhi, SecondPhi});
4417 bool MatchPhiSet(SimplificationTracker &ST,
bool AllowNewPhiNodes,
4418 unsigned &PhiNotMatchedCount) {
4422 SmallSetVector<PHIPair, 8> Matched;
4423 SmallPtrSet<PHINode *, 8> WillNotMatch;
4424 PhiNodeSet &PhiNodesToMatch =
ST.newPhiNodes();
4425 while (PhiNodesToMatch.size()) {
4426 PHINode *
PHI = *PhiNodesToMatch.begin();
4429 WillNotMatch.
clear();
4433 bool IsMatched =
false;
4434 for (
auto &
P :
PHI->getParent()->phis()) {
4436 if (PhiNodesToMatch.count(&
P))
4438 if ((IsMatched = MatchPhiNode(
PHI, &
P, Matched, PhiNodesToMatch)))
4448 for (
auto MV : Matched)
4449 ST.ReplacePhi(MV.first, MV.second);
4454 if (!AllowNewPhiNodes)
4457 PhiNotMatchedCount += WillNotMatch.
size();
4458 for (
auto *
P : WillNotMatch)
4459 PhiNodesToMatch.erase(
P);
4464 void FillPlaceholders(FoldAddrToValueMapping &Map,
4465 SmallVectorImpl<Value *> &TraverseOrder,
4466 SimplificationTracker &ST) {
4467 while (!TraverseOrder.
empty()) {
4469 assert(
Map.contains(Current) &&
"No node to fill!!!");
4475 auto *TrueValue = CurrentSelect->getTrueValue();
4476 assert(
Map.contains(TrueValue) &&
"No True Value!");
4477 Select->setTrueValue(
ST.Get(Map[TrueValue]));
4478 auto *FalseValue = CurrentSelect->getFalseValue();
4479 assert(
Map.contains(FalseValue) &&
"No False Value!");
4480 Select->setFalseValue(
ST.Get(Map[FalseValue]));
4487 assert(
Map.contains(PV) &&
"No predecessor Value!");
4488 PHI->addIncoming(
ST.Get(Map[PV]),
B);
4499 void InsertPlaceholders(FoldAddrToValueMapping &Map,
4500 SmallVectorImpl<Value *> &TraverseOrder,
4501 SimplificationTracker &ST) {
4504 "Address must be a Phi or Select node");
4507 while (!Worklist.
empty()) {
4510 if (
Map.contains(Current))
4521 CurrentSelect->getName(),
4522 CurrentSelect->getIterator(), CurrentSelect);
4526 Worklist.
push_back(CurrentSelect->getTrueValue());
4527 Worklist.
push_back(CurrentSelect->getFalseValue());
4535 ST.insertNewPhi(
PHI);
4541 bool addrModeCombiningAllowed() {
4544 switch (DifferentField) {
4547 case ExtAddrMode::BaseRegField:
4549 case ExtAddrMode::BaseGVField:
4551 case ExtAddrMode::BaseOffsField:
4553 case ExtAddrMode::ScaledRegField:
4563bool AddressingModeMatcher::matchScaledValue(
Value *ScaleReg, int64_t Scale,
4568 return matchAddr(ScaleReg,
Depth);
4579 ExtAddrMode TestAddrMode =
AddrMode;
4583 TestAddrMode.
Scale += Scale;
4597 ConstantInt *CI =
nullptr;
4598 Value *AddLHS =
nullptr;
4602 TestAddrMode.InBounds =
false;
4619 auto GetConstantStep =
4620 [
this](
const Value *
V) -> std::optional<std::pair<Instruction *, APInt>> {
4623 return std::nullopt;
4626 return std::nullopt;
4634 if (OIVInc->hasNoSignedWrap() || OIVInc->hasNoUnsignedWrap())
4635 return std::nullopt;
4637 return std::make_pair(IVInc->first, ConstantStep->getValue());
4638 return std::nullopt;
4653 if (
auto IVStep = GetConstantStep(ScaleReg)) {
4660 APInt Step = IVStep->second;
4662 if (
Offset.isSignedIntN(64)) {
4663 TestAddrMode.InBounds =
false;
4665 TestAddrMode.BaseOffs -=
Offset.getLimitedValue();
4670 getDTFn().
dominates(IVInc, MemoryInst)) {
4690 switch (
I->getOpcode()) {
4691 case Instruction::BitCast:
4692 case Instruction::AddrSpaceCast:
4694 if (
I->getType() ==
I->getOperand(0)->getType())
4696 return I->getType()->isIntOrPtrTy();
4697 case Instruction::PtrToInt:
4700 case Instruction::IntToPtr:
4703 case Instruction::Add:
4705 case Instruction::Mul:
4706 case Instruction::Shl:
4709 case Instruction::GetElementPtr:
4737class TypePromotionHelper {
4740 static void addPromotedInst(InstrToOrigTy &PromotedInsts,
4741 Instruction *ExtOpnd,
bool IsSExt) {
4742 ExtType ExtTy = IsSExt ? SignExtension : ZeroExtension;
4743 auto [It,
Inserted] = PromotedInsts.try_emplace(ExtOpnd);
4747 if (It->second.getInt() == ExtTy)
4753 ExtTy = BothExtension;
4755 It->second = TypeIsSExt(ExtOpnd->
getType(), ExtTy);
4762 static const Type *getOrigType(
const InstrToOrigTy &PromotedInsts,
4763 Instruction *Opnd,
bool IsSExt) {
4764 ExtType ExtTy = IsSExt ? SignExtension : ZeroExtension;
4765 InstrToOrigTy::const_iterator It = PromotedInsts.find(Opnd);
4766 if (It != PromotedInsts.end() && It->second.getInt() == ExtTy)
4767 return It->second.getPointer();
4782 static bool canGetThrough(
const Instruction *Inst,
Type *ConsideredExtType,
4783 const InstrToOrigTy &PromotedInsts,
bool IsSExt);
4787 static bool shouldExtOperand(
const Instruction *Inst,
int OpIdx) {
4800 static Value *promoteOperandForTruncAndAnyExt(
4801 Instruction *Ext, TypePromotionTransaction &TPT,
4802 InstrToOrigTy &PromotedInsts,
unsigned &CreatedInstsCost,
4803 SmallVectorImpl<Instruction *> *Exts,
4804 SmallVectorImpl<Instruction *> *Truncs,
const TargetLowering &TLI);
4815 static Value *promoteOperandForOther(Instruction *Ext,
4816 TypePromotionTransaction &TPT,
4817 InstrToOrigTy &PromotedInsts,
4818 unsigned &CreatedInstsCost,
4819 SmallVectorImpl<Instruction *> *Exts,
4820 SmallVectorImpl<Instruction *> *Truncs,
4821 const TargetLowering &TLI,
bool IsSExt);
4824 static Value *signExtendOperandForOther(
4825 Instruction *Ext, TypePromotionTransaction &TPT,
4826 InstrToOrigTy &PromotedInsts,
unsigned &CreatedInstsCost,
4827 SmallVectorImpl<Instruction *> *Exts,
4828 SmallVectorImpl<Instruction *> *Truncs,
const TargetLowering &TLI) {
4829 return promoteOperandForOther(Ext, TPT, PromotedInsts, CreatedInstsCost,
4830 Exts, Truncs, TLI,
true);
4834 static Value *zeroExtendOperandForOther(
4835 Instruction *Ext, TypePromotionTransaction &TPT,
4836 InstrToOrigTy &PromotedInsts,
unsigned &CreatedInstsCost,
4837 SmallVectorImpl<Instruction *> *Exts,
4838 SmallVectorImpl<Instruction *> *Truncs,
const TargetLowering &TLI) {
4839 return promoteOperandForOther(Ext, TPT, PromotedInsts, CreatedInstsCost,
4840 Exts, Truncs, TLI,
false);
4845 using Action =
Value *(*)(Instruction *Ext, TypePromotionTransaction &TPT,
4846 InstrToOrigTy &PromotedInsts,
4847 unsigned &CreatedInstsCost,
4848 SmallVectorImpl<Instruction *> *Exts,
4849 SmallVectorImpl<Instruction *> *Truncs,
4850 const TargetLowering &TLI);
4861 static Action getAction(Instruction *Ext,
const SetOfInstrs &InsertedInsts,
4862 const TargetLowering &TLI,
4863 const InstrToOrigTy &PromotedInsts);
4868bool TypePromotionHelper::canGetThrough(
const Instruction *Inst,
4869 Type *ConsideredExtType,
4870 const InstrToOrigTy &PromotedInsts,
4890 ((!IsSExt && BinOp->hasNoUnsignedWrap()) ||
4891 (IsSExt && BinOp->hasNoSignedWrap())))
4895 if ((Inst->
getOpcode() == Instruction::And ||
4900 if (Inst->
getOpcode() == Instruction::Xor) {
4903 if (!Cst->getValue().isAllOnes())
4912 if (Inst->
getOpcode() == Instruction::LShr && !IsSExt)
4922 if (ExtInst->hasOneUse()) {
4924 if (AndInst && AndInst->getOpcode() == Instruction::And) {
4957 const Type *OpndType = getOrigType(PromotedInsts, Opnd, IsSExt);
4970TypePromotionHelper::Action TypePromotionHelper::getAction(
4971 Instruction *Ext,
const SetOfInstrs &InsertedInsts,
4972 const TargetLowering &TLI,
const InstrToOrigTy &PromotedInsts) {
4974 "Unexpected instruction type");
4981 if (!ExtOpnd || !canGetThrough(ExtOpnd, ExtTy, PromotedInsts, IsSExt))
4994 return promoteOperandForTruncAndAnyExt;
5000 return IsSExt ? signExtendOperandForOther : zeroExtendOperandForOther;
5003Value *TypePromotionHelper::promoteOperandForTruncAndAnyExt(
5004 Instruction *SExt, TypePromotionTransaction &TPT,
5005 InstrToOrigTy &PromotedInsts,
unsigned &CreatedInstsCost,
5006 SmallVectorImpl<Instruction *> *Exts,
5007 SmallVectorImpl<Instruction *> *Truncs,
const TargetLowering &TLI) {
5011 Value *ExtVal = SExt;
5012 bool HasMergedNonFreeExt =
false;
5016 HasMergedNonFreeExt = !TLI.
isExtFree(SExtOpnd);
5019 TPT.replaceAllUsesWith(SExt, ZExt);
5020 TPT.eraseInstruction(SExt);
5025 TPT.setOperand(SExt, 0, SExtOpnd->
getOperand(0));
5027 CreatedInstsCost = 0;
5031 TPT.eraseInstruction(SExtOpnd);
5039 CreatedInstsCost = !TLI.
isExtFree(ExtInst) && !HasMergedNonFreeExt;
5047 TPT.eraseInstruction(ExtInst, NextVal);
5051Value *TypePromotionHelper::promoteOperandForOther(
5052 Instruction *Ext, TypePromotionTransaction &TPT,
5053 InstrToOrigTy &PromotedInsts,
unsigned &CreatedInstsCost,
5054 SmallVectorImpl<Instruction *> *Exts,
5055 SmallVectorImpl<Instruction *> *Truncs,
const TargetLowering &TLI,
5060 CreatedInstsCost = 0;
5066 Value *Trunc = TPT.createTrunc(Ext, ExtOpnd->
getType());
5069 ITrunc->moveAfter(ExtOpnd);
5074 TPT.replaceAllUsesWith(ExtOpnd, Trunc);
5077 TPT.setOperand(Ext, 0, ExtOpnd);
5087 addPromotedInst(PromotedInsts, ExtOpnd, IsSExt);
5089 TPT.mutateType(ExtOpnd, Ext->
getType());
5091 TPT.replaceAllUsesWith(Ext, ExtOpnd);
5098 !shouldExtOperand(ExtOpnd,
OpIdx)) {
5107 APInt CstVal = IsSExt ? Cst->getValue().sext(
BitWidth)
5109 TPT.setOperand(ExtOpnd,
OpIdx, ConstantInt::get(Ext->
getType(), CstVal));
5120 Value *ValForExtOpnd = IsSExt
5121 ? TPT.createSExt(ExtOpnd, Opnd, Ext->
getType())
5122 : TPT.createZExt(ExtOpnd, Opnd, Ext->
getType());
5123 TPT.setOperand(ExtOpnd,
OpIdx, ValForExtOpnd);
5125 if (!InstForExtOpnd)
5131 CreatedInstsCost += !TLI.
isExtFree(InstForExtOpnd);
5134 TPT.eraseInstruction(Ext);
5146bool AddressingModeMatcher::isPromotionProfitable(
5147 unsigned NewCost,
unsigned OldCost,
Value *PromotedOperand)
const {
5148 LLVM_DEBUG(
dbgs() <<
"OldCost: " << OldCost <<
"\tNewCost: " << NewCost
5153 if (NewCost > OldCost)
5155 if (NewCost < OldCost)
5174bool AddressingModeMatcher::matchOperationAddr(User *AddrInst,
unsigned Opcode,
5186 case Instruction::PtrToInt:
5189 case Instruction::IntToPtr: {
5197 case Instruction::BitCast:
5207 case Instruction::AddrSpaceCast: {
5215 case Instruction::Add: {
5218 ExtAddrMode BackupAddrMode =
AddrMode;
5219 unsigned OldSize = AddrModeInsts.
size();
5224 TypePromotionTransaction::ConstRestorationPt LastKnownGood =
5225 TPT.getRestorationPoint();
5229 int First = 0, Second = 1;
5240 AddrModeInsts.
resize(OldSize);
5241 TPT.rollback(LastKnownGood);
5251 AddrModeInsts.
resize(OldSize);
5252 TPT.rollback(LastKnownGood);
5258 case Instruction::Mul:
5259 case Instruction::Shl: {
5263 if (!
RHS ||
RHS->getBitWidth() > 64)
5265 int64_t Scale = Opcode == Instruction::Shl
5266 ? 1LL <<
RHS->getLimitedValue(
RHS->getBitWidth() - 1)
5267 :
RHS->getSExtValue();
5271 case Instruction::GetElementPtr: {
5274 int VariableOperand = -1;
5275 unsigned VariableScale = 0;
5277 int64_t ConstantOffset = 0;
5279 for (
unsigned i = 1, e = AddrInst->
getNumOperands(); i != e; ++i, ++GTI) {
5281 const StructLayout *SL =
DL.getStructLayout(STy);
5292 if (ConstantInt *CI =
5294 const APInt &CVal = CI->
getValue();
5301 if (VariableOperand != -1)
5305 VariableOperand = i;
5306 VariableScale = TypeSize;
5313 if (VariableOperand == -1) {
5314 AddrMode.BaseOffs += ConstantOffset;
5320 AddrMode.BaseOffs -= ConstantOffset;
5324 ConstantOffset > 0) {
5337 BasicBlock *Parent = BaseI ? BaseI->getParent()
5338 : &
GEP->getFunction()->getEntryBlock();
5340 LargeOffsetGEP = std::make_pair(
GEP, ConstantOffset);
5348 ExtAddrMode BackupAddrMode =
AddrMode;
5349 unsigned OldSize = AddrModeInsts.
size();
5352 AddrMode.BaseOffs += ConstantOffset;
5361 AddrModeInsts.
resize(OldSize);
5369 if (!matchScaledValue(AddrInst->
getOperand(VariableOperand), VariableScale,
5374 AddrModeInsts.
resize(OldSize);
5379 AddrMode.BaseOffs += ConstantOffset;
5380 if (!matchScaledValue(AddrInst->
getOperand(VariableOperand),
5381 VariableScale,
Depth)) {
5384 AddrModeInsts.
resize(OldSize);
5391 case Instruction::SExt:
5392 case Instruction::ZExt: {
5399 TypePromotionHelper::Action TPH =
5400 TypePromotionHelper::getAction(Ext, InsertedInsts, TLI, PromotedInsts);
5404 TypePromotionTransaction::ConstRestorationPt LastKnownGood =
5405 TPT.getRestorationPoint();
5406 unsigned CreatedInstsCost = 0;
5408 Value *PromotedOperand =
5409 TPH(Ext, TPT, PromotedInsts, CreatedInstsCost,
nullptr,
nullptr, TLI);
5424 assert(PromotedOperand &&
5425 "TypePromotionHelper should have filtered out those cases");
5427 ExtAddrMode BackupAddrMode =
AddrMode;
5428 unsigned OldSize = AddrModeInsts.
size();
5430 if (!matchAddr(PromotedOperand,
Depth) ||
5435 !isPromotionProfitable(CreatedInstsCost,
5436 ExtCost + (AddrModeInsts.
size() - OldSize),
5439 AddrModeInsts.
resize(OldSize);
5440 LLVM_DEBUG(
dbgs() <<
"Sign extension does not pay off: rollback\n");
5441 TPT.rollback(LastKnownGood);
5446 AddrMode.replaceWith(Ext, PromotedOperand);
5449 case Instruction::Call:
5451 if (
II->getIntrinsicID() == Intrinsic::threadlocal_address) {
5467bool AddressingModeMatcher::matchAddr(
Value *Addr,
unsigned Depth) {
5470 TypePromotionTransaction::ConstRestorationPt LastKnownGood =
5471 TPT.getRestorationPoint();
5495 ExtAddrMode BackupAddrMode =
AddrMode;
5496 unsigned OldSize = AddrModeInsts.
size();
5499 bool MovedAway =
false;
5500 if (matchOperationAddr(
I,
I->getOpcode(),
Depth, &MovedAway)) {
5508 if (
I->hasOneUse() ||
5509 isProfitableToFoldIntoAddressingMode(
I, BackupAddrMode,
AddrMode)) {
5516 AddrModeInsts.
resize(OldSize);
5517 TPT.rollback(LastKnownGood);
5520 if (matchOperationAddr(CE,
CE->getOpcode(),
Depth))
5522 TPT.rollback(LastKnownGood);
5549 TPT.rollback(LastKnownGood);
5568 if (OpInfo.CallOperandVal == OpVal &&
5570 !OpInfo.isIndirect))
5586 if (!ConsideredInsts.
insert(
I).second)
5594 for (
Use &U :
I->uses()) {
5602 MemoryUses.push_back({&U, LI->getType()});
5609 MemoryUses.push_back({&U,
SI->getValueOperand()->getType()});
5616 MemoryUses.push_back({&U, RMW->getValOperand()->getType()});
5623 MemoryUses.push_back({&U, CmpX->getCompareOperand()->getType()});
5633 if (!
find(PtrOps, U.get()))
5636 MemoryUses.push_back({&U, AccessTy});
5641 if (CI->hasFnAttr(Attribute::Cold)) {
5659 PSI, BFI, SeenInsts))
5670 unsigned SeenInsts = 0;
5673 PSI, BFI, SeenInsts);
5681bool AddressingModeMatcher::valueAlreadyLiveAtInst(
Value *Val,
5683 Value *KnownLive2) {
5685 if (Val ==
nullptr || Val == KnownLive1 || Val == KnownLive2)
5726bool AddressingModeMatcher::isProfitableToFoldIntoAddressingMode(
5727 Instruction *
I, ExtAddrMode &AMBefore, ExtAddrMode &AMAfter) {
5728 if (IgnoreProfitability)
5746 if (valueAlreadyLiveAtInst(ScaledReg, AMBefore.
BaseReg, AMBefore.
ScaledReg))
5747 ScaledReg =
nullptr;
5751 if (!BaseReg && !ScaledReg)
5772 for (
const std::pair<Use *, Type *> &Pair : MemoryUses) {
5775 Type *AddressAccessTy = Pair.second;
5776 unsigned AS =
Address->getType()->getPointerAddressSpace();
5782 std::pair<AssertingVH<GetElementPtrInst>, int64_t> LargeOffsetGEP(
nullptr,
5784 TypePromotionTransaction::ConstRestorationPt LastKnownGood =
5785 TPT.getRestorationPoint();
5786 AddressingModeMatcher Matcher(MatchedAddrModeInsts, TLI,
TRI, LI, getDTFn,
5787 AddressAccessTy, AS, UserI, Result,
5788 InsertedInsts, PromotedInsts, TPT,
5789 LargeOffsetGEP, OptSize, PSI, BFI);
5790 Matcher.IgnoreProfitability =
true;
5798 TPT.rollback(LastKnownGood);
5804 MatchedAddrModeInsts.
clear();
5814 return I->getParent() != BB;
5830 return std::next(AddrInst->getIterator());
5841 Earliest = UserInst;
5866bool CodeGenPrepare::optimizeMemoryInst(Instruction *MemoryInst,
Value *Addr,
5867 Type *AccessTy,
unsigned AddrSpace) {
5872 SmallVector<Value *, 8> worklist;
5873 SmallPtrSet<Value *, 16> Visited;
5879 bool PhiOrSelectSeen =
false;
5880 SmallVector<Instruction *, 16> AddrModeInsts;
5881 AddressingModeCombiner AddrModes(*
DL, Addr);
5882 TypePromotionTransaction TPT(RemovedInsts);
5883 TypePromotionTransaction::ConstRestorationPt LastKnownGood =
5884 TPT.getRestorationPoint();
5885 while (!worklist.
empty()) {
5897 if (!Visited.
insert(V).second)
5903 PhiOrSelectSeen =
true;
5910 PhiOrSelectSeen =
true;
5917 AddrModeInsts.
clear();
5918 std::pair<AssertingVH<GetElementPtrInst>, int64_t> LargeOffsetGEP(
nullptr,
5923 auto getDTFn = [
this]() ->
const DominatorTree & {
return getDT(); };
5924 ExtAddrMode NewAddrMode = AddressingModeMatcher::Match(
5925 V, AccessTy, AddrSpace, MemoryInst, AddrModeInsts, *TLI, *LI, getDTFn,
5926 *
TRI, InsertedInsts, PromotedInsts, TPT, LargeOffsetGEP, OptSize, PSI,
5929 GetElementPtrInst *
GEP = LargeOffsetGEP.first;
5934 LargeOffsetGEPMap[
GEP->getPointerOperand()].push_back(LargeOffsetGEP);
5935 LargeOffsetGEPID.
insert(std::make_pair(
GEP, LargeOffsetGEPID.
size()));
5938 NewAddrMode.OriginalValue =
V;
5939 if (!AddrModes.addNewAddrMode(NewAddrMode))
5946 if (!AddrModes.combineAddrModes()) {
5947 TPT.rollback(LastKnownGood);
5953 ExtAddrMode
AddrMode = AddrModes.getAddrMode();
5959 if (!PhiOrSelectSeen &&
none_of(AddrModeInsts, [&](
Value *V) {
5973 WeakTrackingVH SunkAddrVH = SunkAddrs[Addr];
5995 <<
" for " << *MemoryInst <<
"\n");
5999 !
DL->isNonIntegralPointerType(Addr->
getType())) {
6005 SunkAddr = Builder.CreatePtrToInt(SunkAddr, IntPtrTy,
"sunkaddr");
6007 Builder.CreateIntToPtr(SunkAddr, Addr->
getType(),
"sunkaddr");
6009 SunkAddr = Builder.CreatePointerCast(SunkAddr, Addr->
getType());
6016 <<
" for " << *MemoryInst <<
"\n");
6017 Value *ResultPtr =
nullptr, *ResultIndex =
nullptr;
6028 if (ResultPtr ||
AddrMode.Scale != 1)
6049 GlobalValue *BaseGV =
AddrMode.BaseGV;
6050 if (BaseGV !=
nullptr) {
6055 ResultPtr = Builder.CreateThreadLocalAddress(BaseGV);
6064 if (!
DL->isNonIntegralPointerType(Addr->
getType())) {
6065 if (!ResultPtr &&
AddrMode.BaseReg) {
6069 }
else if (!ResultPtr &&
AddrMode.Scale == 1) {
6070 ResultPtr = Builder.CreateIntToPtr(
AddrMode.ScaledReg, Addr->
getType(),
6079 }
else if (!ResultPtr) {
6092 if (
V->getType() != IntPtrTy)
6093 V = Builder.CreateIntCast(V, IntPtrTy,
true,
"sunkaddr");
6101 if (
V->getType() == IntPtrTy) {
6106 "We can't transform if ScaledReg is too narrow");
6107 V = Builder.CreateTrunc(V, IntPtrTy,
"sunkaddr");
6111 V = Builder.CreateMul(
6114 ResultIndex = Builder.CreateAdd(ResultIndex, V,
"sunkaddr");
6125 if (ResultPtr->
getType() != I8PtrTy)
6126 ResultPtr = Builder.CreatePointerCast(ResultPtr, I8PtrTy);
6127 ResultPtr = Builder.CreatePtrAdd(ResultPtr, ResultIndex,
"sunkaddr",
6140 if (PtrInst && PtrInst->getParent() != MemoryInst->
getParent())
6142 SunkAddr = ResultPtr;
6144 if (ResultPtr->
getType() != I8PtrTy)
6145 ResultPtr = Builder.CreatePointerCast(ResultPtr, I8PtrTy);
6146 SunkAddr = Builder.CreatePtrAdd(ResultPtr, ResultIndex,
"sunkaddr",
6153 !
DL->isNonIntegralPointerType(Addr->
getType())) {
6159 SunkAddr = Builder.CreatePtrToInt(SunkAddr, IntPtrTy,
"sunkaddr");
6161 Builder.CreateIntToPtr(SunkAddr, Addr->
getType(),
"sunkaddr");
6163 SunkAddr = Builder.CreatePointerCast(SunkAddr, Addr->
getType());
6173 if (
DL->isNonIntegralPointerType(Addr->
getType()) ||
6174 (BasePtrTy &&
DL->isNonIntegralPointerType(BasePtrTy)) ||
6175 (ScalePtrTy &&
DL->isNonIntegralPointerType(ScalePtrTy)) ||
6177 DL->isNonIntegralPointerType(
AddrMode.BaseGV->getType())))
6181 <<
" for " << *MemoryInst <<
"\n");
6192 if (
V->getType()->isPointerTy())
6193 V = Builder.CreatePtrToInt(V, IntPtrTy,
"sunkaddr");
6194 if (
V->getType() != IntPtrTy)
6195 V = Builder.CreateIntCast(V, IntPtrTy,
true,
"sunkaddr");
6202 if (
V->getType() == IntPtrTy) {
6204 }
else if (
V->getType()->isPointerTy()) {
6205 V = Builder.CreatePtrToInt(V, IntPtrTy,
"sunkaddr");
6208 V = Builder.CreateTrunc(V, IntPtrTy,
"sunkaddr");
6217 I->eraseFromParent();
6221 V = Builder.CreateMul(
6224 Result = Builder.CreateAdd(Result, V,
"sunkaddr");
6230 GlobalValue *BaseGV =
AddrMode.BaseGV;
6231 if (BaseGV !=
nullptr) {
6234 BaseGVPtr = Builder.CreateThreadLocalAddress(BaseGV);
6238 Value *
V = Builder.CreatePtrToInt(BaseGVPtr, IntPtrTy,
"sunkaddr");
6240 Result = Builder.CreateAdd(Result, V,
"sunkaddr");
6249 Result = Builder.CreateAdd(Result, V,
"sunkaddr");
6257 SunkAddr = Builder.CreateIntToPtr(Result, Addr->
getType(),
"sunkaddr");
6263 SunkAddrs[Addr] = WeakTrackingVH(SunkAddr);
6268 resetIteratorIfInvalidatedWhileCalling(CurInstIterator->getParent(), [&]() {
6269 RecursivelyDeleteTriviallyDeadInstructions(
6270 Repl, TLInfo, nullptr,
6271 [&](Value *V) { removeAllAssertingVHReferences(V); });
6295bool CodeGenPrepare::optimizeGatherScatterInst(Instruction *MemoryInst,
6301 if (!
GEP->hasIndices())
6309 SmallVector<Value *, 2>
Ops(
GEP->operands());
6311 bool RewriteGEP =
false;
6320 unsigned FinalIndex =
Ops.size() - 1;
6325 for (
unsigned i = 1; i < FinalIndex; ++i) {
6330 C =
C->getSplatValue();
6332 if (!CI || !CI->
isZero())
6339 if (
Ops[FinalIndex]->
getType()->isVectorTy()) {
6343 if (!
C || !
C->isZero()) {
6344 Ops[FinalIndex] =
V;
6352 if (!RewriteGEP &&
Ops.size() == 2)
6359 Type *SourceTy =
GEP->getSourceElementType();
6360 Type *ScalarIndexTy =
DL->getIndexType(
Ops[0]->
getType()->getScalarType());
6364 if (!
Ops[FinalIndex]->
getType()->isVectorTy()) {
6365 NewAddr = Builder.CreateGEP(SourceTy,
Ops[0],
ArrayRef(
Ops).drop_front());
6366 auto *IndexTy = VectorType::get(ScalarIndexTy, NumElts);
6376 if (
Ops.size() != 2) {
6386 NewAddr = Builder.CreateGEP(SourceTy,
Base, Index);
6400 Type *ScalarIndexTy =
DL->getIndexType(
V->getType()->getScalarType());
6401 auto *IndexTy = VectorType::get(ScalarIndexTy, NumElts);
6404 Intrinsic::masked_gather) {
6408 Intrinsic::masked_scatter);
6423 Ptr, TLInfo,
nullptr,
6424 [&](
Value *V) { removeAllAssertingVHReferences(V); });
6435 if (
I->hasNUsesOrMore(3))
6438 for (
User *U :
I->users()) {
6440 if (!Extract || Extract->getNumIndices() != 1)
6443 unsigned Index = Extract->getIndices()[0];
6445 MulExtract = Extract;
6446 else if (Index == 1)
6447 OverflowExtract = Extract;
6474bool CodeGenPrepare::optimizeMulWithOverflow(Instruction *
I,
bool IsSigned,
6475 ModifyDT &ModifiedDT) {
6482 ExtractValueInst *MulExtract =
nullptr, *OverflowExtract =
nullptr;
6487 InsertedInsts.insert(
I);
6498 OverflowEntryBB->
takeName(
I->getParent());
6504 NoOverflowBB->
moveAfter(OverflowEntryBB);
6512 Value *LoLHS = Builder.CreateTrunc(
LHS, LegalTy,
"lo.lhs");
6513 Value *HiLHS = Builder.CreateLShr(
LHS, VTHalfBitWidth,
"lhs.lsr");
6514 HiLHS = Builder.CreateTrunc(HiLHS, LegalTy,
"hi.lhs");
6517 Value *LoRHS = Builder.CreateTrunc(
RHS, LegalTy,
"lo.rhs");
6518 Value *HiRHS = Builder.CreateLShr(
RHS, VTHalfBitWidth,
"rhs.lsr");
6519 HiRHS = Builder.CreateTrunc(HiRHS, LegalTy,
"hi.rhs");
6521 Value *IsAnyBitTrue;
6524 Builder.CreateAShr(LoLHS, VTHalfBitWidth - 1,
"sign.lo.lhs");
6526 Builder.CreateAShr(LoRHS, VTHalfBitWidth - 1,
"sign.lo.rhs");
6527 Value *XorLHS = Builder.CreateXor(HiLHS, SignLoLHS);
6528 Value *XorRHS = Builder.CreateXor(HiRHS, SignLoRHS);
6529 Value *
Or = Builder.CreateOr(XorLHS, XorRHS,
"or.lhs.rhs");
6530 IsAnyBitTrue = Builder.CreateCmp(ICmpInst::ICMP_NE,
Or,
6531 ConstantInt::getNullValue(
Or->getType()));
6533 Value *CmpLHS = Builder.CreateCmp(ICmpInst::ICMP_NE, HiLHS,
6534 ConstantInt::getNullValue(LegalTy));
6535 Value *CmpRHS = Builder.CreateCmp(ICmpInst::ICMP_NE, HiRHS,
6536 ConstantInt::getNullValue(LegalTy));
6537 IsAnyBitTrue = Builder.CreateOr(CmpLHS, CmpRHS,
"or.lhs.rhs");
6539 Builder.CreateCondBr(IsAnyBitTrue, OverflowBB, NoOverflowBB);
6542 Builder.SetInsertPoint(NoOverflowBB);
6543 Value *ExtLoLHS, *ExtLoRHS;
6545 ExtLoLHS = Builder.CreateSExt(LoLHS, Ty,
"lo.lhs.ext");
6546 ExtLoRHS = Builder.CreateSExt(LoRHS, Ty,
"lo.rhs.ext");
6548 ExtLoLHS = Builder.CreateZExt(LoLHS, Ty,
"lo.lhs.ext");
6549 ExtLoRHS = Builder.CreateZExt(LoRHS, Ty,
"lo.rhs.ext");
6552 Value *
Mul = Builder.CreateMul(ExtLoLHS, ExtLoRHS,
"mul.overflow.no");
6557 OverflowResBB->
setName(
"overflow.res");
6560 Builder.CreateBr(OverflowResBB);
6568 PHINode *OverflowResPHI = Builder.CreatePHI(Ty, 2),
6570 Builder.CreatePHI(IntegerType::getInt1Ty(
I->getContext()), 2);
6582 if (OverflowExtract) {
6583 OverflowExtract->replaceAllUsesWith(OverflowFlagPHI);
6584 OverflowExtract->eraseFromParent();
6589 I->removeFromParent();
6591 I->insertInto(OverflowBB, OverflowBB->
end());
6592 Builder.SetInsertPoint(OverflowBB, OverflowBB->
end());
6594 Value *OverflowFlag = Builder.CreateExtractValue(
I, {1},
"overflow.flag");
6595 Builder.CreateBr(OverflowResBB);
6599 OverflowFlagPHI->addIncoming(OverflowFlag, OverflowBB);
6601 DTU->
applyUpdates({{DominatorTree::Insert, OverflowEntryBB, OverflowBB},
6602 {DominatorTree::Insert, OverflowEntryBB, NoOverflowBB},
6603 {DominatorTree::Insert, NoOverflowBB, OverflowResBB},
6604 {DominatorTree::Delete, OverflowEntryBB, OverflowResBB},
6605 {DominatorTree::Insert, OverflowBB, OverflowResBB}});
6607 ModifiedDT = ModifyDT::ModifyBBDT;
6613bool CodeGenPrepare::optimizeInlineAsmInst(CallInst *CS) {
6614 bool MadeChange =
false;
6616 const TargetRegisterInfo *
TRI =
6621 for (TargetLowering::AsmOperandInfo &OpInfo : TargetConstraints) {
6627 OpInfo.isIndirect) {
6629 MadeChange |= optimizeMemoryInst(CS, OpVal, OpVal->
getType(), ~0u);
6692bool CodeGenPrepare::tryToPromoteExts(
6693 TypePromotionTransaction &TPT,
const SmallVectorImpl<Instruction *> &Exts,
6694 SmallVectorImpl<Instruction *> &ProfitablyMovedExts,
6695 unsigned CreatedInstsCost) {
6696 bool Promoted =
false;
6699 for (
auto *
I : Exts) {
6714 TypePromotionHelper::Action TPH =
6715 TypePromotionHelper::getAction(
I, InsertedInsts, *TLI, PromotedInsts);
6724 TypePromotionTransaction::ConstRestorationPt LastKnownGood =
6725 TPT.getRestorationPoint();
6726 SmallVector<Instruction *, 4> NewExts;
6727 unsigned NewCreatedInstsCost = 0;
6730 Value *PromotedVal = TPH(
I, TPT, PromotedInsts, NewCreatedInstsCost,
6731 &NewExts,
nullptr, *TLI);
6733 "TypePromotionHelper should have filtered out those cases");
6743 long long TotalCreatedInstsCost = CreatedInstsCost + NewCreatedInstsCost;
6746 TotalCreatedInstsCost =
6747 std::max((
long long)0, (TotalCreatedInstsCost - ExtCost));
6749 (TotalCreatedInstsCost > 1 ||
6751 (ExtCost == 0 && NewExts.
size() > 1))) {
6755 TPT.rollback(LastKnownGood);
6760 SmallVector<Instruction *, 2> NewlyMovedExts;
6761 (void)tryToPromoteExts(TPT, NewExts, NewlyMovedExts, TotalCreatedInstsCost);
6762 bool NewPromoted =
false;
6763 for (
auto *ExtInst : NewlyMovedExts) {
6773 ProfitablyMovedExts.
push_back(MovedExt);
6780 TPT.rollback(LastKnownGood);
6791bool CodeGenPrepare::mergeSExts(Function &
F) {
6793 for (
auto &Entry : ValToSExtendedUses) {
6794 SExts &Insts =
Entry.second;
6796 for (Instruction *Inst : Insts) {
6800 bool inserted =
false;
6801 for (
auto &Pt : CurPts) {
6804 RemovedInsts.insert(Pt);
6805 Pt->removeFromParent();
6816 RemovedInsts.insert(Inst);
6823 CurPts.push_back(Inst);
6865bool CodeGenPrepare::splitLargeGEPOffsets() {
6867 for (
auto &Entry : LargeOffsetGEPMap) {
6869 SmallVectorImpl<std::pair<AssertingVH<GetElementPtrInst>, int64_t>>
6870 &LargeOffsetGEPs =
Entry.second;
6871 auto compareGEPOffset =
6872 [&](
const std::pair<GetElementPtrInst *, int64_t> &
LHS,
6873 const std::pair<GetElementPtrInst *, int64_t> &
RHS) {
6874 if (
LHS.first ==
RHS.first)
6876 if (
LHS.second !=
RHS.second)
6877 return LHS.second <
RHS.second;
6878 return LargeOffsetGEPID[
LHS.first] < LargeOffsetGEPID[
RHS.first];
6881 llvm::sort(LargeOffsetGEPs, compareGEPOffset);
6884 if (LargeOffsetGEPs.
front().second == LargeOffsetGEPs.
back().second)
6886 GetElementPtrInst *BaseGEP = LargeOffsetGEPs.
begin()->first;
6887 int64_t BaseOffset = LargeOffsetGEPs.
begin()->second;
6888 Value *NewBaseGEP =
nullptr;
6890 auto createNewBase = [&](int64_t BaseOffset,
Value *OldBase,
6891 GetElementPtrInst *
GEP) {
6892 LLVMContext &Ctx =
GEP->getContext();
6893 Type *PtrIdxTy =
DL->getIndexType(
GEP->getType());
6895 PointerType::get(Ctx,
GEP->getType()->getPointerAddressSpace());
6907 SplitEdge(NewBaseInsertBB, Invoke->getNormalDest(), &getDT(), LI);
6910 NewBaseInsertPt = std::next(BaseI->getIterator());
6917 IRBuilder<> NewBaseBuilder(NewBaseInsertBB, NewBaseInsertPt);
6923 NewBaseGEP = OldBase;
6924 if (NewBaseGEP->
getType() != I8PtrTy)
6925 NewBaseGEP = NewBaseBuilder.CreatePointerCast(NewBaseGEP, I8PtrTy);
6927 NewBaseBuilder.CreatePtrAdd(NewBaseGEP, BaseIndex,
"splitgep");
6928 NewGEPBases.
insert(NewBaseGEP);
6934 LargeOffsetGEPs.
front().second, LargeOffsetGEPs.
back().second)) {
6935 BaseOffset = PreferBase;
6938 createNewBase(BaseOffset, OldBase, BaseGEP);
6941 auto *LargeOffsetGEP = LargeOffsetGEPs.
begin();
6942 while (LargeOffsetGEP != LargeOffsetGEPs.
end()) {
6943 GetElementPtrInst *
GEP = LargeOffsetGEP->first;
6944 int64_t
Offset = LargeOffsetGEP->second;
6945 if (
Offset != BaseOffset) {
6952 GEP->getResultElementType(),
6953 GEP->getAddressSpace())) {
6959 NewBaseGEP =
nullptr;
6964 Type *PtrIdxTy =
DL->getIndexType(
GEP->getType());
6969 createNewBase(BaseOffset, OldBase,
GEP);
6973 Value *NewGEP = NewBaseGEP;
6974 if (
Offset != BaseOffset) {
6977 NewGEP = Builder.CreatePtrAdd(NewBaseGEP, Index);
6981 LargeOffsetGEP = LargeOffsetGEPs.
erase(LargeOffsetGEP);
6982 GEP->eraseFromParent();
6989bool CodeGenPrepare::optimizePhiType(
6990 PHINode *
I, SmallPtrSetImpl<PHINode *> &Visited,
6991 SmallPtrSetImpl<Instruction *> &DeletedInstrs) {
6996 Type *PhiTy =
I->getType();
6997 Type *ConvertTy =
nullptr;
6999 (!
I->getType()->isIntegerTy() && !
I->getType()->isFloatingPointTy()))
7002 SmallVector<Instruction *, 4> Worklist;
7004 SmallPtrSet<PHINode *, 4> PhiNodes;
7005 SmallPtrSet<ConstantData *, 4>
Constants;
7008 SmallPtrSet<Instruction *, 4> Defs;
7009 SmallPtrSet<Instruction *, 4>
Uses;
7015 bool AnyAnchored =
false;
7017 while (!Worklist.
empty()) {
7022 for (
Value *V :
Phi->incoming_values()) {
7024 if (!PhiNodes.
count(OpPhi)) {
7025 if (!Visited.
insert(OpPhi).second)
7031 if (!OpLoad->isSimple())
7033 if (Defs.
insert(OpLoad).second)
7036 if (Defs.
insert(OpEx).second)
7040 ConvertTy = OpBC->getOperand(0)->getType();
7041 if (OpBC->getOperand(0)->getType() != ConvertTy)
7043 if (Defs.
insert(OpBC).second) {
7056 for (User *V :
II->users()) {
7058 if (!PhiNodes.
count(OpPhi)) {
7059 if (Visited.
count(OpPhi))
7066 if (!OpStore->isSimple() || OpStore->getOperand(0) !=
II)
7068 Uses.insert(OpStore);
7071 ConvertTy = OpBC->getType();
7072 if (OpBC->getType() != ConvertTy)
7076 any_of(OpBC->users(), [](User *U) { return !isa<StoreInst>(U); });
7083 if (!ConvertTy || !AnyAnchored || PhiTy == ConvertTy ||
7087 LLVM_DEBUG(
dbgs() <<
"Converting " << *
I <<
"\n and connected nodes to "
7088 << *ConvertTy <<
"\n");
7093 for (ConstantData *
C : Constants)
7095 for (Instruction *
D : Defs) {
7097 ValMap[
D] =
D->getOperand(0);
7101 ValMap[
D] =
new BitCastInst(
D, ConvertTy,
D->getName() +
".bc", insertPt);
7104 for (PHINode *Phi : PhiNodes)
7106 Phi->getName() +
".tc",
Phi->getIterator());
7108 for (PHINode *Phi : PhiNodes) {
7110 for (
int i = 0, e =
Phi->getNumIncomingValues(); i < e; i++)
7112 Phi->getIncomingBlock(i));
7116 for (Instruction *U :
Uses) {
7121 U->setOperand(0,
new BitCastInst(ValMap[
U->getOperand(0)], PhiTy,
"bc",
7131bool CodeGenPrepare::optimizePhiTypes(Function &
F) {
7136 SmallPtrSet<PHINode *, 4> Visited;
7137 SmallPtrSet<Instruction *, 4> DeletedInstrs;
7141 for (
auto &Phi : BB.
phis())
7142 Changed |= optimizePhiType(&Phi, Visited, DeletedInstrs);
7145 for (
auto *
I : DeletedInstrs) {
7147 I->eraseFromParent();
7155bool CodeGenPrepare::canFormExtLd(
7156 const SmallVectorImpl<Instruction *> &MovedExts, LoadInst *&LI,
7157 Instruction *&Inst,
bool HasPromoted) {
7158 for (
auto *MovedExtInst : MovedExts) {
7161 Inst = MovedExtInst;
7213bool CodeGenPrepare::optimizeExt(Instruction *&Inst) {
7214 bool AllowPromotionWithoutCommonHeader =
false;
7219 *Inst, AllowPromotionWithoutCommonHeader);
7220 TypePromotionTransaction TPT(RemovedInsts);
7221 TypePromotionTransaction::ConstRestorationPt LastKnownGood =
7222 TPT.getRestorationPoint();
7224 SmallVector<Instruction *, 2> SpeculativelyMovedExts;
7227 bool HasPromoted = tryToPromoteExts(TPT, Exts, SpeculativelyMovedExts);
7230 LoadInst *LI =
nullptr;
7235 if (canFormExtLd(SpeculativelyMovedExts, LI, ExtFedByLoad, HasPromoted)) {
7236 assert(LI && ExtFedByLoad &&
"Expect a valid load and extension");
7241 Inst = ExtFedByLoad;
7246 if (ATPConsiderable &&
7247 performAddressTypePromotion(Inst, AllowPromotionWithoutCommonHeader,
7248 HasPromoted, TPT, SpeculativelyMovedExts))
7251 TPT.rollback(LastKnownGood);
7260bool CodeGenPrepare::performAddressTypePromotion(
7261 Instruction *&Inst,
bool AllowPromotionWithoutCommonHeader,
7262 bool HasPromoted, TypePromotionTransaction &TPT,
7263 SmallVectorImpl<Instruction *> &SpeculativelyMovedExts) {
7264 bool Promoted =
false;
7265 SmallPtrSet<Instruction *, 1> UnhandledExts;
7266 bool AllSeenFirst =
true;
7267 for (
auto *
I : SpeculativelyMovedExts) {
7268 Value *HeadOfChain =
I->getOperand(0);
7269 auto AlreadySeen = SeenChainsForSExt.
find(HeadOfChain);
7272 if (AlreadySeen != SeenChainsForSExt.
end()) {
7273 if (AlreadySeen->second !=
nullptr)
7274 UnhandledExts.
insert(AlreadySeen->second);
7275 AllSeenFirst =
false;
7279 if (!AllSeenFirst || (AllowPromotionWithoutCommonHeader &&
7280 SpeculativelyMovedExts.size() == 1)) {
7284 for (
auto *
I : SpeculativelyMovedExts) {
7285 Value *HeadOfChain =
I->getOperand(0);
7286 SeenChainsForSExt[HeadOfChain] =
nullptr;
7287 ValToSExtendedUses[HeadOfChain].push_back(
I);
7290 Inst = SpeculativelyMovedExts.pop_back_val();
7295 for (
auto *
I : SpeculativelyMovedExts) {
7296 Value *HeadOfChain =
I->getOperand(0);
7297 SeenChainsForSExt[HeadOfChain] = Inst;
7302 if (!AllSeenFirst && !UnhandledExts.
empty())
7303 for (
auto *VisitedSExt : UnhandledExts) {
7304 if (RemovedInsts.count(VisitedSExt))
7306 TypePromotionTransaction TPT(RemovedInsts);
7308 SmallVector<Instruction *, 2> Chains;
7310 bool HasPromoted = tryToPromoteExts(TPT, Exts, Chains);
7314 for (
auto *
I : Chains) {
7315 Value *HeadOfChain =
I->getOperand(0);
7317 SeenChainsForSExt[HeadOfChain] =
nullptr;
7318 ValToSExtendedUses[HeadOfChain].push_back(
I);
7324bool CodeGenPrepare::optimizeExtUses(Instruction *
I) {
7329 Value *Src =
I->getOperand(0);
7330 if (Src->hasOneUse())
7342 bool DefIsLiveOut =
false;
7343 for (User *U :
I->users()) {
7348 if (UserBB == DefBB)
7350 DefIsLiveOut =
true;
7357 for (User *U : Src->users()) {
7360 if (UserBB == DefBB)
7369 DenseMap<BasicBlock *, Instruction *> InsertedTruncs;
7371 bool MadeChange =
false;
7372 for (Use &U : Src->uses()) {
7377 if (UserBB == DefBB)
7381 Instruction *&InsertedTrunc = InsertedTruncs[UserBB];
7383 if (!InsertedTrunc) {
7386 InsertedTrunc =
new TruncInst(
I, Src->getType(),
"");
7388 InsertedInsts.insert(InsertedTrunc);
7451bool CodeGenPrepare::optimizeLoadExt(LoadInst *Load) {
7452 if (!
Load->isSimple() || !
Load->getType()->isIntOrPtrTy())
7456 if (
Load->hasOneUse() &&
7462 SmallVector<Instruction *, 8> WorkList;
7463 SmallPtrSet<Instruction *, 16> Visited;
7464 SmallVector<Instruction *, 8> AndsToMaybeRemove;
7465 SmallVector<Instruction *, 8> DropFlags;
7466 for (
auto *U :
Load->users())
7478 while (!WorkList.
empty()) {
7482 if (!Visited.
insert(
I).second)
7487 for (
auto *U :
Phi->users())
7492 switch (
I->getOpcode()) {
7493 case Instruction::And: {
7497 APInt AndBits = AndC->getValue();
7498 DemandBits |= AndBits;
7500 if (AndBits.
ugt(WidestAndBits))
7501 WidestAndBits = AndBits;
7502 if (AndBits == WidestAndBits &&
I->getOperand(0) == Load)
7507 case Instruction::Shl: {
7511 uint64_t ShiftAmt = ShlC->getLimitedValue(
BitWidth - 1);
7512 DemandBits.setLowBits(
BitWidth - ShiftAmt);
7517 case Instruction::Trunc: {
7520 DemandBits.setLowBits(TruncBitWidth);
7530 uint32_t ActiveBits = DemandBits.getActiveBits();
7542 if (ActiveBits <= 1 || !DemandBits.isMask(ActiveBits) ||
7543 WidestAndBits != DemandBits)
7546 LLVMContext &Ctx =
Load->getType()->getContext();
7547 Type *TruncTy = Type::getIntNTy(Ctx, ActiveBits);
7558 Builder.CreateAnd(Load, ConstantInt::get(Ctx, DemandBits)));
7561 InsertedInsts.insert(NewAnd);
7566 NewAnd->setOperand(0, Load);
7569 for (
auto *
And : AndsToMaybeRemove)
7574 if (&*CurInstIterator ==
And)
7575 CurInstIterator = std::next(
And->getIterator());
7576 And->eraseFromParent();
7581 for (
auto *Inst : DropFlags)
7595 TTI->isExpensiveToSpeculativelyExecute(
I);
7613 uint64_t Max = std::max(TrueWeight, FalseWeight);
7614 uint64_t Sum = TrueWeight + FalseWeight;
7617 if (Probability >
TTI->getPredictableBranchThreshold())
7627 if (!Cmp || !Cmp->hasOneUse())
7650 assert(DefSI->getCondition() ==
SI->getCondition() &&
7651 "The condition of DefSI does not match with SI");
7652 V = (isTrue ? DefSI->getTrueValue() : DefSI->getFalseValue());
7655 assert(V &&
"Failed to get select true/false value");
7659bool CodeGenPrepare::optimizeShiftInst(BinaryOperator *Shift) {
7683 BinaryOperator::BinaryOps Opcode = Shift->
getOpcode();
7684 Value *NewTVal = Builder.CreateBinOp(Opcode, Shift->
getOperand(0), TVal);
7685 Value *NewFVal = Builder.CreateBinOp(Opcode, Shift->
getOperand(0), FVal);
7686 Value *NewSel = Builder.CreateSelect(
Cond, NewTVal, NewFVal);
7692bool CodeGenPrepare::optimizeFunnelShift(IntrinsicInst *Fsh) {
7694 assert((Opcode == Intrinsic::fshl || Opcode == Intrinsic::fshr) &&
7695 "Expected a funnel shift");
7719 Value *NewTVal = Builder.CreateIntrinsic(Opcode, Ty, {
X,
Y, TVal});
7720 Value *NewFVal = Builder.CreateIntrinsic(Opcode, Ty, {
X,
Y, FVal});
7721 Value *NewSel = Builder.CreateSelect(
Cond, NewTVal, NewFVal);
7729bool CodeGenPrepare::optimizeSelectInst(SelectInst *SI) {
7741 It !=
SI->getParent()->
end(); ++It) {
7743 if (
I &&
SI->getCondition() ==
I->getCondition()) {
7750 SelectInst *LastSI = ASI.
back();
7753 CurInstIterator = std::next(LastSI->
getIterator());
7757 for (SelectInst *SI :
ArrayRef(ASI).drop_front())
7758 fixupDbgVariableRecordsOnInst(*SI);
7760 bool VectorCond = !
SI->getCondition()->getType()->isIntegerTy(1);
7763 if (VectorCond ||
SI->getMetadata(LLVMContext::MD_unpredictable))
7766 TargetLowering::SelectSupportKind SelectKind;
7767 if (
SI->getType()->isVectorTy())
7768 SelectKind = TargetLowering::ScalarCondVectorVal;
7770 SelectKind = TargetLowering::ScalarValSelect;
7808 for (SelectInst *SI : ASI) {
7820 SplitPt.setHeadBit(
true);
7823 auto *CondFr =
IB.CreateFreeze(
SI->getCondition(),
SI->getName() +
".frozen");
7828 UncondBrInst *TrueBranch =
nullptr;
7829 UncondBrInst *FalseBranch =
nullptr;
7830 if (TrueInstrs.
size() == 0) {
7833 FalseBlock = FalseBranch->getParent();
7835 }
else if (FalseInstrs.
size() == 0) {
7838 TrueBlock = TrueBranch->getParent();
7847 TrueBlock = TrueBranch->getParent();
7848 FalseBlock = FalseBranch->getParent();
7852 EndBlock->
setName(
"select.end");
7854 TrueBlock->
setName(
"select.true.sink");
7856 FalseBlock->
setName(FalseInstrs.
size() == 0 ?
"select.false"
7857 :
"select.false.sink");
7861 FreshBBs.
insert(TrueBlock);
7863 FreshBBs.
insert(FalseBlock);
7864 FreshBBs.
insert(EndBlock);
7869 static const unsigned MD[] = {
7870 LLVMContext::MD_prof, LLVMContext::MD_unpredictable,
7871 LLVMContext::MD_make_implicit, LLVMContext::MD_dbg};
7876 for (Instruction *
I : TrueInstrs)
7877 I->moveBefore(TrueBranch->getIterator());
7878 for (Instruction *
I : FalseInstrs)
7879 I->moveBefore(FalseBranch->getIterator());
7885 if (TrueBlock ==
nullptr)
7886 TrueBlock = StartBlock;
7887 else if (FalseBlock ==
nullptr)
7888 FalseBlock = StartBlock;
7904 SI->eraseFromParent();
7906 ++NumSelectsExpanded;
7910 CurInstIterator = StartBlock->
end();
7917bool CodeGenPrepare::optimizeShuffleVectorInst(ShuffleVectorInst *SVI) {
7929 "Expected a type of the same size!");
7935 Builder.SetInsertPoint(SVI);
7936 Value *BC1 = Builder.CreateBitCast(
7938 Value *Shuffle = Builder.CreateVectorSplat(NewVecType->getNumElements(), BC1);
7939 Value *BC2 = Builder.CreateBitCast(Shuffle, SVIVecType);
7943 SVI, TLInfo,
nullptr,
7944 [&](
Value *V) { removeAllAssertingVHReferences(V); });
7951 !
Op->isTerminator() && !
Op->isEHPad())
7957bool CodeGenPrepare::tryToSinkFreeOperands(Instruction *
I) {
7972 for (Use *U :
reverse(OpsToSink)) {
7984 SetVector<Instruction *> MaybeDead;
7985 DenseMap<Instruction *, Instruction *> NewInstructions;
7986 for (Use *U : ToReplace) {
7995 FreshBBs.
insert(OpDef->getParent());
7998 NewInstructions[UI] = NI;
8003 InsertedInsts.insert(NI);
8009 if (
auto It = NewInstructions.
find(OldI); It != NewInstructions.
end())
8010 It->second->setOperand(
U->getOperandNo(), NI);
8017 for (
auto *
I : MaybeDead) {
8018 if (!
I->hasNUsesOrMore(1)) {
8020 I->eraseFromParent();
8027bool CodeGenPrepare::optimizeSwitchType(SwitchInst *SI) {
8033 unsigned RegWidth =
RegType.getSizeInBits();
8044 auto *NewType = Type::getIntNTy(
Context, RegWidth);
8053 ExtType = Instruction::SExt;
8056 if (Arg->hasSExtAttr())
8057 ExtType = Instruction::SExt;
8058 if (Arg->hasZExtAttr())
8059 ExtType = Instruction::ZExt;
8065 SI->setCondition(ExtInst);
8066 for (
auto Case :
SI->cases()) {
8067 const APInt &NarrowConst = Case.getCaseValue()->getValue();
8068 APInt WideConst = (ExtType == Instruction::ZExt)
8069 ? NarrowConst.
zext(RegWidth)
8070 : NarrowConst.
sext(RegWidth);
8071 Case.setValue(ConstantInt::get(
Context, WideConst));
8077bool CodeGenPrepare::optimizeSwitchPhiConstants(SwitchInst *SI) {
8084 Value *Condition =
SI->getCondition();
8093 for (
const SwitchInst::CaseHandle &Case :
SI->cases()) {
8094 ConstantInt *CaseValue = Case.getCaseValue();
8095 BasicBlock *CaseBB = Case.getCaseSuccessor();
8098 bool CheckedForSinglePred =
false;
8099 for (PHINode &
PHI : CaseBB->
phis()) {
8100 Type *PHIType =
PHI.getType();
8108 if (PHIType == ConditionType || TryZExt) {
8110 bool SkipCase =
false;
8111 Value *Replacement =
nullptr;
8112 for (
unsigned I = 0,
E =
PHI.getNumIncomingValues();
I !=
E;
I++) {
8113 Value *PHIValue =
PHI.getIncomingValue(
I);
8114 if (PHIValue != CaseValue) {
8123 if (
PHI.getIncomingBlock(
I) != SwitchBB)
8128 if (!CheckedForSinglePred) {
8129 CheckedForSinglePred =
true;
8130 if (
SI->findCaseDest(CaseBB) ==
nullptr) {
8136 if (Replacement ==
nullptr) {
8137 if (PHIValue == CaseValue) {
8138 Replacement = Condition;
8141 Replacement = Builder.CreateZExt(Condition, PHIType);
8144 PHI.setIncomingValue(
I, Replacement);
8155bool CodeGenPrepare::optimizeSwitchInst(SwitchInst *SI) {
8156 bool Changed = optimizeSwitchType(SI);
8157 Changed |= optimizeSwitchPhiConstants(SI);
8178class VectorPromoteHelper {
8180 const DataLayout &
DL;
8183 const TargetLowering &TLI;
8186 const TargetTransformInfo &
TTI;
8192 SmallVector<Instruction *, 4> InstsToBePromoted;
8195 unsigned StoreExtractCombineCost;
8204 if (InstsToBePromoted.
empty())
8206 return InstsToBePromoted.
back();
8212 unsigned getTransitionOriginalValueIdx()
const {
8214 "Other kind of transitions are not supported yet");
8221 unsigned getTransitionIdx()
const {
8223 "Other kind of transitions are not supported yet");
8231 Type *getTransitionType()
const {
8242 void promoteImpl(Instruction *ToBePromoted);
8246 bool isProfitableToPromote() {
8247 Value *ValIdx = Transition->
getOperand(getTransitionOriginalValueIdx());
8251 Type *PromotedType = getTransitionType();
8254 unsigned AS =
ST->getPointerAddressSpace();
8272 for (
const auto &Inst : InstsToBePromoted) {
8280 TargetTransformInfo::OperandValueInfo Arg0Info, Arg1Info;
8292 dbgs() <<
"Estimated cost of computation to be promoted:\nScalar: "
8293 << ScalarCost <<
"\nVector: " << VectorCost <<
'\n');
8294 return ScalarCost > VectorCost;
8306 unsigned ExtractIdx = std::numeric_limits<unsigned>::max();
8321 if (!
EC.isScalable()) {
8322 SmallVector<Constant *, 4> ConstVec;
8324 for (
unsigned Idx = 0; Idx !=
EC.getKnownMinValue(); ++Idx) {
8325 if (Idx == ExtractIdx)
8333 "Generate scalable vector for non-splat is unimplemented");
8338 static bool canCauseUndefinedBehavior(
const Instruction *Use,
8339 unsigned OperandIdx) {
8342 if (OperandIdx != 1)
8344 switch (
Use->getOpcode()) {
8347 case Instruction::SDiv:
8348 case Instruction::UDiv:
8349 case Instruction::SRem:
8350 case Instruction::URem:
8352 case Instruction::FDiv:
8353 case Instruction::FRem:
8354 return !
Use->hasNoNaNs();
8360 VectorPromoteHelper(
const DataLayout &
DL,
const TargetLowering &TLI,
8361 const TargetTransformInfo &
TTI, Instruction *Transition,
8362 unsigned CombineCost)
8363 :
DL(
DL), TLI(TLI),
TTI(
TTI), Transition(Transition),
8364 StoreExtractCombineCost(CombineCost) {
8365 assert(Transition &&
"Do not know how to promote null");
8369 bool canPromote(
const Instruction *ToBePromoted)
const {
8376 bool shouldPromote(
const Instruction *ToBePromoted)
const {
8379 for (
const Use &U : ToBePromoted->
operands()) {
8380 const Value *Val =
U.get();
8381 if (Val == getEndOfTransition()) {
8385 if (canCauseUndefinedBehavior(ToBePromoted,
U.getOperandNo()))
8408 void enqueueForPromotion(Instruction *ToBePromoted) {
8409 InstsToBePromoted.push_back(ToBePromoted);
8413 void recordCombineInstruction(Instruction *ToBeCombined) {
8415 CombineInst = ToBeCombined;
8425 if (InstsToBePromoted.empty() || !CombineInst)
8433 for (
auto &ToBePromoted : InstsToBePromoted)
8434 promoteImpl(ToBePromoted);
8435 InstsToBePromoted.clear();
8442void VectorPromoteHelper::promoteImpl(Instruction *ToBePromoted) {
8452 "The type of the result of the transition does not match "
8457 Type *TransitionTy = getTransitionType();
8462 for (Use &U : ToBePromoted->
operands()) {
8464 Value *NewVal =
nullptr;
8465 if (Val == Transition)
8466 NewVal = Transition->
getOperand(getTransitionOriginalValueIdx());
8473 canCauseUndefinedBehavior(ToBePromoted,
U.getOperandNo()));
8477 ToBePromoted->
setOperand(
U.getOperandNo(), NewVal);
8480 Transition->
setOperand(getTransitionOriginalValueIdx(), ToBePromoted);
8486bool CodeGenPrepare::optimizeExtractElementInst(Instruction *Inst) {
8487 unsigned CombineCost = std::numeric_limits<unsigned>::max();
8502 LLVM_DEBUG(
dbgs() <<
"Found an interesting transition: " << *Inst <<
'\n');
8503 VectorPromoteHelper VPH(*
DL, *TLI, *
TTI, Inst, CombineCost);
8510 if (ToBePromoted->
getParent() != Parent) {
8511 LLVM_DEBUG(
dbgs() <<
"Instruction to promote is in a different block ("
8513 <<
") than the transition (" << Parent->
getName()
8518 if (VPH.canCombine(ToBePromoted)) {
8520 <<
"will be combined with: " << *ToBePromoted <<
'\n');
8521 VPH.recordCombineInstruction(ToBePromoted);
8523 NumStoreExtractExposed +=
Changed;
8528 if (!VPH.canPromote(ToBePromoted) || !VPH.shouldPromote(ToBePromoted))
8531 LLVM_DEBUG(
dbgs() <<
"Promoting is possible... Enqueue for promotion!\n");
8533 VPH.enqueueForPromotion(ToBePromoted);
8534 Inst = ToBePromoted;
8574 Type *StoreType =
SI.getValueOperand()->getType();
8583 if (!
DL.typeSizeEqualsStoreSize(StoreType) ||
8584 DL.getTypeSizeInBits(StoreType) == 0)
8587 unsigned HalfValBitSize =
DL.getTypeSizeInBits(StoreType) / 2;
8589 if (!
DL.typeSizeEqualsStoreSize(SplitStoreType))
8605 if (!
match(
SI.getValueOperand(),
8612 if (!
LValue->getType()->isIntegerTy() ||
8613 DL.getTypeSizeInBits(
LValue->getType()) > HalfValBitSize ||
8615 DL.getTypeSizeInBits(HValue->
getType()) > HalfValBitSize)
8631 Builder.SetInsertPoint(&
SI);
8635 if (LBC && LBC->getParent() !=
SI.getParent())
8636 LValue = Builder.CreateBitCast(LBC->getOperand(0), LBC->getType());
8637 if (HBC && HBC->getParent() !=
SI.getParent())
8638 HValue = Builder.CreateBitCast(HBC->getOperand(0), HBC->getType());
8640 bool IsLE =
SI.getDataLayout().isLittleEndian();
8641 auto CreateSplitStore = [&](
Value *V,
bool Upper) {
8642 V = Builder.CreateZExtOrBitCast(V, SplitStoreType);
8643 Value *Addr =
SI.getPointerOperand();
8644 Align Alignment =
SI.getAlign();
8645 const bool IsOffsetStore = (IsLE &&
Upper) || (!IsLE && !
Upper);
8646 if (IsOffsetStore) {
8647 Addr = Builder.CreateGEP(
8648 SplitStoreType, Addr,
8656 Builder.CreateAlignedStore(V, Addr, Alignment);
8659 CreateSplitStore(
LValue,
false);
8660 CreateSplitStore(HValue,
true);
8663 SI.eraseFromParent();
8671 return GEP->getNumOperands() == 2 &&
I.isSequential() &&
8753 if (GEPIOpI->getParent() != SrcBlock)
8758 if (auto *I = dyn_cast<Instruction>(Usr)) {
8759 if (I->getParent() != SrcBlock) {
8767 std::vector<GetElementPtrInst *> UGEPIs;
8770 for (User *Usr : GEPIOp->
users()) {
8789 if (UGEPI->getOperand(0) != GEPIOp)
8791 if (UGEPI->getSourceElementType() != GEPI->getSourceElementType())
8793 if (GEPIIdx->getType() !=
8801 UGEPIs.push_back(UGEPI);
8803 if (UGEPIs.size() == 0)
8806 for (GetElementPtrInst *UGEPI : UGEPIs) {
8808 APInt NewIdx = UGEPIIdx->
getValue() - GEPIIdx->getValue();
8815 for (GetElementPtrInst *UGEPI : UGEPIs) {
8816 UGEPI->setOperand(0, GEPI);
8818 auto NewIdx = UGEPIIdx->
getValue() - GEPIIdx->getValue();
8819 Constant *NewUGEPIIdx = ConstantInt::get(GEPIIdx->getType(), NewIdx);
8820 UGEPI->setOperand(1, NewUGEPIIdx);
8822 auto SourceFlags = GEPI->getNoWrapFlags();
8825 UGEPI->getNoWrapFlags().intersectForOffsetAdd(SourceFlags);
8827 if (NewIdx.
isNegative() && TargetFlags.hasNoUnsignedWrap())
8828 TargetFlags = TargetFlags.withoutNoUnsignedWrap();
8829 UGEPI->setNoWrapFlags(TargetFlags);
8835 return cast<Instruction>(Usr)->getParent() != SrcBlock;
8837 "GEPIOp is used outside SrcBlock");
8861 Value *
X = Cmp->getOperand(0);
8862 if (!
X->hasUseList())
8867 for (
auto *U :
X->users()) {
8871 (UI->
getParent() != Branch->getParent() &&
8872 UI->
getParent() != Branch->getSuccessor(0) &&
8873 UI->
getParent() != Branch->getSuccessor(1)) ||
8874 (UI->
getParent() != Branch->getParent() &&
8875 !UI->
getParent()->getSinglePredecessor()))
8881 if (UI->
getParent() != Branch->getParent())
8885 ConstantInt::get(UI->
getType(), 0));
8887 LLVM_DEBUG(
dbgs() <<
" to compare on zero: " << *NewCmp <<
"\n");
8891 if (Cmp->isEquality() &&
8896 if (UI->
getParent() != Branch->getParent())
8899 Value *NewCmp = Builder.CreateCmp(Cmp->getPredicate(), UI,
8900 ConstantInt::get(UI->
getType(), 0));
8902 LLVM_DEBUG(
dbgs() <<
" to compare on zero: " << *NewCmp <<
"\n");
8910bool CodeGenPrepare::optimizeInst(Instruction *
I, ModifyDT &ModifiedDT) {
8911 bool AnyChange =
false;
8912 AnyChange = fixupDbgVariableRecordsOnInst(*
I);
8916 if (InsertedInsts.count(
I))
8925 LargeOffsetGEPMap.erase(
P);
8927 P->eraseFromParent();
8950 I, LI->getLoopFor(
I->getParent()), *
TTI))
8958 TargetLowering::TypeExpandInteger) {
8962 I, LI->getLoopFor(
I->getParent()), *
TTI))
8965 bool MadeChange = optimizeExt(
I);
8966 return MadeChange | optimizeExtUses(
I);
8973 if (optimizeCmp(Cmp, ModifiedDT))
8977 if (optimizeURem(
I))
8981 LI->
setMetadata(LLVMContext::MD_invariant_group,
nullptr);
8982 bool Modified = optimizeLoadExt(LI);
8991 SI->setMetadata(LLVMContext::MD_invariant_group,
nullptr);
8992 unsigned AS =
SI->getPointerAddressSpace();
8993 return optimizeMemoryInst(
I,
SI->getOperand(1),
8994 SI->getOperand(0)->getType(), AS);
8998 unsigned AS = RMW->getPointerAddressSpace();
8999 return optimizeMemoryInst(
I, RMW->getPointerOperand(), RMW->getType(), AS);
9003 unsigned AS = CmpX->getPointerAddressSpace();
9004 return optimizeMemoryInst(
I, CmpX->getPointerOperand(),
9005 CmpX->getCompareOperand()->getType(), AS);
9015 if (BinOp && (BinOp->
getOpcode() == Instruction::AShr ||
9016 BinOp->
getOpcode() == Instruction::LShr)) {
9024 if (GEPI->hasAllZeroIndices()) {
9026 Instruction *
NC =
new BitCastInst(GEPI->getOperand(0), GEPI->getType(),
9027 GEPI->getName(), GEPI->getIterator());
9028 NC->setDebugLoc(GEPI->getDebugLoc());
9031 GEPI, TLInfo,
nullptr,
9032 [&](
Value *V) { removeAllAssertingVHReferences(V); });
9034 optimizeInst(
NC, ModifiedDT);
9057 if (Const0 || Const1) {
9058 if (!Const0 || !Const1) {
9059 auto *
F =
new FreezeInst(Const0 ? Op1 : Op0,
"", CmpI->
getIterator());
9064 FI->eraseFromParent();
9071 if (tryToSinkFreeOperands(
I))
9074 switch (
I->getOpcode()) {
9075 case Instruction::Shl:
9076 case Instruction::LShr:
9077 case Instruction::AShr:
9079 case Instruction::Call:
9081 case Instruction::Select:
9083 case Instruction::ShuffleVector:
9085 case Instruction::Switch:
9087 case Instruction::ExtractElement:
9089 case Instruction::CondBr:
9098bool CodeGenPrepare::makeBitReverse(Instruction &
I) {
9099 if (!
I.getType()->isIntegerTy() ||
9104 SmallVector<Instruction *, 4> Insts;
9110 &
I, TLInfo,
nullptr,
9111 [&](
Value *V) { removeAllAssertingVHReferences(V); });
9118bool CodeGenPrepare::optimizeBlock(BasicBlock &BB, ModifyDT &ModifiedDT) {
9120 bool MadeChange =
false;
9123 CurInstIterator = BB.
begin();
9124 ModifiedDT = ModifyDT::NotModifyDT;
9125 while (CurInstIterator != BB.
end()) {
9126 MadeChange |= optimizeInst(&*CurInstIterator++, ModifiedDT);
9127 if (ModifiedDT != ModifyDT::NotModifyDT) {
9136 }
while (ModifiedDT == ModifyDT::ModifyInstDT);
9138 bool MadeBitReverse =
true;
9139 while (MadeBitReverse) {
9140 MadeBitReverse =
false;
9142 if (makeBitReverse(
I)) {
9143 MadeBitReverse = MadeChange =
true;
9148 MadeChange |= dupRetToEnableTailCallOpts(&BB, ModifiedDT);
9153bool CodeGenPrepare::fixupDbgVariableRecordsOnInst(Instruction &
I) {
9154 bool AnyChange =
false;
9155 for (DbgVariableRecord &DVR :
filterDbgVars(
I.getDbgRecordRange()))
9156 AnyChange |= fixupDbgVariableRecord(DVR);
9162bool CodeGenPrepare::fixupDbgVariableRecord(DbgVariableRecord &DVR) {
9163 if (DVR.
Type != DbgVariableRecord::LocationType::Value &&
9164 DVR.
Type != DbgVariableRecord::LocationType::Assign)
9168 bool AnyChange =
false;
9169 SmallDenseSet<Value *> LocationOps(DVR.
location_ops().begin(),
9171 for (
Value *Location : LocationOps) {
9172 WeakTrackingVH SunkAddrVH = SunkAddrs[
Location];
9201bool CodeGenPrepare::placeDbgValues(Function &
F) {
9202 bool MadeChange =
false;
9203 DominatorTree &DT = getDT();
9205 auto DbgProcessor = [&](
auto *DbgItem,
Instruction *Position) {
9206 SmallVector<Instruction *, 4> VIs;
9207 for (
Value *V : DbgItem->location_ops())
9215 for (Instruction *VI : VIs) {
9216 if (
VI->isTerminator())
9221 if (
isa<PHINode>(VI) &&
VI->getParent()->getTerminator()->isEHPad())
9232 if (VIs.size() > 1) {
9235 <<
"Unable to find valid location for Debug Value, undefing:\n"
9237 DbgItem->setKillLocation();
9242 << *DbgItem <<
' ' << *VI);
9249 for (BasicBlock &BB :
F) {
9255 if (DVR.
Type != DbgVariableRecord::LocationType::Value)
9257 DbgProcessor(&DVR, &Insn);
9268bool CodeGenPrepare::placePseudoProbes(Function &
F) {
9269 bool MadeChange =
false;
9272 auto FirstInst =
Block.getFirstInsertionPt();
9273 while (FirstInst !=
Block.end() && FirstInst->isDebugOrPseudoInst())
9277 while (
I !=
Block.end()) {
9279 II->moveBefore(FirstInst);
9309bool CodeGenPrepare::splitBranchCondition(Function &
F) {
9313 bool MadeChange =
false;
9314 for (
auto &BB :
F) {
9327 if (Br1->getMetadata(LLVMContext::MD_unpredictable))
9335 Value *Cond1, *Cond2;
9338 Opc = Instruction::And;
9341 Opc = Instruction::Or;
9351 if (!IsGoodCond(Cond1) || !IsGoodCond(Cond2))
9365 Br1->setCondition(Cond1);
9370 if (
Opc == Instruction::And)
9371 Br1->setSuccessor(0, TmpBB);
9373 Br1->setSuccessor(1, TmpBB);
9378 I->removeFromParent();
9379 I->insertBefore(Br2->getIterator());
9391 if (
Opc == Instruction::Or)
9398 for (PHINode &PN : FBB->
phis()) {
9403 if (Loop *L = LI->getLoopFor(&BB))
9404 L->addBasicBlockToLoop(TmpBB, *LI);
9408 DTU->
applyUpdates({{DominatorTree::Insert, &BB, TmpBB},
9409 {DominatorTree::Insert, TmpBB,
TBB},
9410 {DominatorTree::Insert, TmpBB, FBB},
9411 {DominatorTree::Delete, &BB,
TBB}});
9415 if (
Opc == Instruction::Or) {
9435 uint64_t TrueWeight, FalseWeight;
9437 uint64_t NewTrueWeight = TrueWeight;
9438 uint64_t NewFalseWeight = TrueWeight + 2 * FalseWeight;
9442 NewTrueWeight = TrueWeight;
9443 NewFalseWeight = 2 * FalseWeight;
9466 uint64_t TrueWeight, FalseWeight;
9468 uint64_t NewTrueWeight = 2 * TrueWeight + FalseWeight;
9469 uint64_t NewFalseWeight = FalseWeight;
9473 NewTrueWeight = 2 * TrueWeight;
9474 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.
auto m_Cmp()
Matches any compare instruction and ignore it.
BinaryOp_match< LHS, RHS, Instruction::Add > m_Add(const LHS &L, const RHS &R)
OverflowingBinaryOp_match< LHS, RHS, Instruction::Add, OverflowingBinaryOperator::NoUnsignedWrap > m_NUWAdd(const LHS &L, const RHS &R)
BinaryOp_match< LHS, RHS, Instruction::URem > m_URem(const LHS &L, const RHS &R)
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.
IntrinsicID_match m_Intrinsic()
Match intrinsic calls like this: m_Intrinsic<Intrinsic::fabs>(m_Value(X))
ThreeOps_match< Cond, LHS, RHS, Instruction::Select > m_Select(const Cond &C, const LHS &L, const RHS &R)
Matches SelectInst.
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_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.
m_Intrinsic_Ty< Opnd0 >::Ty m_Ctpop(const Opnd0 &Op0)
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)
FunctionAddr VTableAddr Value
std::enable_if_t< std::is_signed_v< T >, T > MulOverflow(T X, T Y, T &Result)
Multiply two signed integers, computing the two's complement truncated result, returning true if an o...
auto find(R &&Range, const T &Val)
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly.
LLVM_ABI bool RemoveRedundantDbgInstrs(BasicBlock *BB)
Try to remove redundant dbg.value instructions from given basic block.
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
auto size(R &&Range, std::enable_if_t< std::is_base_of< std::random_access_iterator_tag, typename std::iterator_traits< decltype(Range.begin())>::iterator_category >::value, void > *=nullptr)
Get the size of a range.
LLVM_ABI bool RecursivelyDeleteTriviallyDeadInstructions(Value *V, const TargetLibraryInfo *TLI=nullptr, MemorySSAUpdater *MSSAU=nullptr, std::function< void(Value *)> AboutToDeleteCallback=std::function< void(Value *)>())
If the specified value is a trivially dead instruction, delete it.
LLVM_ABI bool ConstantFoldTerminator(BasicBlock *BB, bool DeleteDeadConditions=false, const TargetLibraryInfo *TLI=nullptr, DomTreeUpdater *DTU=nullptr)
If a terminator instruction is predicated on a constant value, convert it into an unconditional branc...
LLVM_ABI void findDbgValues(Value *V, SmallVectorImpl< DbgVariableRecord * > &DbgVariableRecords)
Finds the dbg.values describing a value.
decltype(auto) dyn_cast(const From &Val)
dyn_cast<X> - Return the argument parameter cast to the specified type.
APInt operator*(APInt a, uint64_t RHS)
bool isAligned(Align Lhs, uint64_t SizeInBytes)
Checks that SizeInBytes is a multiple of the alignment.
LLVM_ABI void salvageDebugInfo(const MachineRegisterInfo &MRI, MachineInstr &MI)
Assuming the instruction MI is going to be deleted, attempt to salvage debug users of MI by writing t...
auto successors(const MachineBasicBlock *BB)
OuterAnalysisManagerProxy< ModuleAnalysisManager, Function > ModuleAnalysisManagerFunctionProxy
Provide the ModuleAnalysisManager to Function proxy.
LLVM_ABI ReturnInst * FoldReturnIntoUncondBranch(ReturnInst *RI, BasicBlock *BB, BasicBlock *Pred, DomTreeUpdater *DTU=nullptr)
This method duplicates the specified return instruction into a predecessor which ends in an unconditi...
bool operator!=(uint64_t V1, const APInt &V2)
constexpr from_range_t from_range
LLVM_ABI BasicBlock * splitBlockBefore(BasicBlock *Old, BasicBlock::iterator SplitPt, DomTreeUpdater *DTU, LoopInfo *LI, MemorySSAUpdater *MSSAU, const Twine &BBName="")
Split the specified block at the specified instruction SplitPt.
LLVM_ABI Instruction * SplitBlockAndInsertIfElse(Value *Cond, BasicBlock::iterator SplitBefore, bool Unreachable, MDNode *BranchWeights=nullptr, DomTreeUpdater *DTU=nullptr, LoopInfo *LI=nullptr, BasicBlock *ElseBlock=nullptr)
Similar to SplitBlockAndInsertIfThen, but the inserted block is on the false path of the branch.
LLVM_ABI bool SplitIndirectBrCriticalEdges(Function &F, bool IgnoreBlocksWithoutPHI, BranchProbabilityInfo *BPI=nullptr, BlockFrequencyInfo *BFI=nullptr, DomTreeUpdater *DTU=nullptr)
void append_range(Container &C, Range &&R)
Wrapper function to append range R to container C.
LLVM_ABI bool shouldOptimizeForSize(const MachineFunction *MF, ProfileSummaryInfo *PSI, const MachineBlockFrequencyInfo *BFI, PGSOQueryType QueryType=PGSOQueryType::Other)
Returns true if machine function MF is suggested to be size-optimized based on the profile.
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
LLVM_ABI void DeleteDeadBlock(BasicBlock *BB, DomTreeUpdater *DTU=nullptr, bool KeepOneInputPHIs=false)
Delete the specified block, which must have no predecessors.
LLVM_ABI bool isSafeToSpeculativelyExecute(const Instruction *I, const Instruction *CtxI=nullptr, AssumptionCache *AC=nullptr, const DominatorTree *DT=nullptr, const TargetLibraryInfo *TLI=nullptr, bool UseVariableInfo=true, bool IgnoreUBImplyingAttrs=true)
Return true if the instruction does not have any effects besides calculating the result and does not ...
auto unique(Range &&R, Predicate P)
LLVM_ABI Value * getSplatValue(const Value *V)
Get splat value if the input is a splat vector or return nullptr.
LLVM_ABI bool hasBranchWeightOrigin(const Instruction &I)
Check if Branch Weight Metadata has an "expected" field from an llvm.expect* intrinsic.
constexpr auto equal_to(T &&Arg)
Functor variant of std::equal_to that can be used as a UnaryPredicate in functional algorithms like a...
bool operator==(const AddressRangeValuePair &LHS, const AddressRangeValuePair &RHS)
constexpr int popcount(T Value) noexcept
Count the number of set bits in a value.
LLVM_ABI 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...
LLVM_ABI Value * simplifyInstruction(Instruction *I, const SimplifyQuery &Q)
See if we can compute a simplified version of this instruction.
LLVM_ABI Value * simplifyAddInst(Value *LHS, Value *RHS, bool IsNSW, bool IsNUW, const SimplifyQuery &Q)
Given operands for an Add, fold the result or return null.
auto dyn_cast_or_null(const Y &Val)
Align getKnownAlignment(Value *V, const DataLayout &DL, const Instruction *CxtI=nullptr, AssumptionCache *AC=nullptr, const DominatorTree *DT=nullptr)
Try to infer an alignment for the specified pointer.
void erase(Container &C, ValueType V)
Wrapper function to remove a value from a container:
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
LLVM_ABI bool isSplatValue(const Value *V, int Index=-1, unsigned Depth=0)
Return true if each element of the vector value V is poisoned or equal to every other non-poisoned el...
LLVM_ABI bool DeleteDeadPHIs(BasicBlock *BB, const TargetLibraryInfo *TLI=nullptr, MemorySSAUpdater *MSSAU=nullptr)
Examine each PHI in the given block and delete it if it is dead.
LLVM_ABI bool replaceAndRecursivelySimplify(Instruction *I, Value *SimpleV, const TargetLibraryInfo *TLI=nullptr, const DominatorTree *DT=nullptr, AssumptionCache *AC=nullptr, SmallSetVector< Instruction *, 8 > *UnsimplifiedUsers=nullptr)
Replace all uses of 'I' with 'SimpleV' and simplify the uses recursively.
auto reverse(ContainerTy &&C)
LLVM_ABI bool recognizeBSwapOrBitReverseIdiom(Instruction *I, bool MatchBSwaps, bool MatchBitReversals, SmallVectorImpl< Instruction * > &InsertedInsts)
Try to match a bswap or bitreverse idiom.
void sort(IteratorTy Start, IteratorTy End)
FPClassTest
Floating-point class tests, supported by 'is_fpclass' intrinsic.
LLVM_ABI void SplitBlockAndInsertIfThenElse(Value *Cond, BasicBlock::iterator SplitBefore, Instruction **ThenTerm, Instruction **ElseTerm, MDNode *BranchWeights=nullptr, DomTreeUpdater *DTU=nullptr, LoopInfo *LI=nullptr)
SplitBlockAndInsertIfThenElse is similar to SplitBlockAndInsertIfThen, but also creates the ElseBlock...
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
bool none_of(R &&Range, UnaryPredicate P)
Provide wrappers to std::none_of which take ranges instead of having to pass begin/end explicitly.
auto make_first_range(ContainerTy &&c)
Given a container of pairs, return a range over the first elements.
generic_gep_type_iterator<> gep_type_iterator
LLVM_ABI FunctionPass * createCodeGenPrepareLegacyPass()
createCodeGenPrepareLegacyPass - Transform the code to expose more pattern matching during instructio...
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.
FunctionAddr VTableAddr Next
auto count(R &&Range, const E &Element)
Wrapper function around std::count to count the number of times an element Element occurs in the give...
DWARFExpression::Operation Op
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
LLVM_ABI bool isGuaranteedNotToBeUndefOrPoison(const Value *V, AssumptionCache *AC=nullptr, const Instruction *CtxI=nullptr, const DominatorTree *DT=nullptr, unsigned Depth=0)
Return true if this function can prove that V does not have undef bits and is never poison.
ArrayRef(const T &OneElt) -> ArrayRef< T >
LLVM_ABI bool VerifyDomInfo
Enables verification of dominator trees.
constexpr unsigned BitWidth
LLVM_ABI bool extractBranchWeights(const MDNode *ProfileData, SmallVectorImpl< uint32_t > &Weights)
Extract branch weights from MD_prof metadata.
decltype(auto) cast(const From &Val)
cast<X> - Return the argument parameter cast to the specified type.
gep_type_iterator gep_type_begin(const User *GEP)
void erase_if(Container &C, UnaryPredicate P)
Provide a container algorithm similar to C++ Library Fundamentals v2's erase_if which is equivalent t...
auto predecessors(const MachineBasicBlock *BB)
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
Align commonAlignment(Align A, uint64_t Offset)
Returns the alignment that satisfies both alignments.
bool pred_empty(const BasicBlock *BB)
std::enable_if_t< std::is_signed_v< T >, T > AddOverflow(T X, T Y, T &Result)
Add two signed integers, computing the two's complement truncated result, returning true if overflow ...
LLVM_ABI Instruction * SplitBlockAndInsertIfThen(Value *Cond, BasicBlock::iterator SplitBefore, bool Unreachable, MDNode *BranchWeights=nullptr, DomTreeUpdater *DTU=nullptr, LoopInfo *LI=nullptr, BasicBlock *ThenBlock=nullptr)
Split the containing block at the specified instruction - everything before SplitBefore stays in the ...
AnalysisManager< Function > FunctionAnalysisManager
Convenience typedef for the Function analysis manager.
LLVM_ABI BasicBlock * SplitEdge(BasicBlock *From, BasicBlock *To, DominatorTree *DT=nullptr, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, const Twine &BBName="")
Split the edge connecting the specified blocks, and return the newly created basic block between From...
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.