45#include "llvm/Config/llvm-config.h"
66#include "llvm/IR/IntrinsicsAArch64.h"
110#define DEBUG_TYPE "codegenprepare"
113STATISTIC(NumPHIsElim,
"Number of trivial PHIs eliminated");
114STATISTIC(NumGEPsElim,
"Number of GEPs converted to casts");
115STATISTIC(NumCmpUses,
"Number of uses of Cmp expressions replaced with uses of "
117STATISTIC(NumCastUses,
"Number of uses of Cast expressions replaced with uses "
119STATISTIC(NumMemoryInsts,
"Number of memory instructions whose address "
120 "computations were sunk");
122 "Number of phis created when address "
123 "computations were sunk to memory instructions");
125 "Number of select created when address "
126 "computations were sunk to memory instructions");
127STATISTIC(NumExtsMoved,
"Number of [s|z]ext instructions combined with loads");
128STATISTIC(NumExtUses,
"Number of uses of [s|z]ext instructions optimized");
130 "Number of and mask instructions added to form ext loads");
131STATISTIC(NumAndUses,
"Number of uses of and mask instructions optimized");
132STATISTIC(NumRetsDup,
"Number of return instructions duplicated");
133STATISTIC(NumDbgValueMoved,
"Number of debug value instructions moved");
134STATISTIC(NumSelectsExpanded,
"Number of selects turned into branches");
135STATISTIC(NumStoreExtractExposed,
"Number of store(extractelement) exposed");
139 cl::desc(
"Disable branch optimizations in CodeGenPrepare"));
143 cl::desc(
"Disable GC optimizations in CodeGenPrepare"));
148 cl::desc(
"Disable select to branch conversion."));
152 cl::desc(
"Address sinking in CGP using GEPs."));
156 cl::desc(
"Enable sinking and/cmp into branches."));
160 cl::desc(
"Disable store(extract) optimizations in CodeGenPrepare"));
164 cl::desc(
"Stress test store(extract) optimizations in CodeGenPrepare"));
168 cl::desc(
"Disable ext(promotable(ld)) -> promoted(ext(ld)) optimization in "
173 cl::desc(
"Stress test ext(promotable(ld)) -> promoted(ext(ld)) "
174 "optimization in CodeGenPrepare"));
178 cl::desc(
"Disable protection against removing loop preheaders"));
182 cl::desc(
"Use profile info to add section prefix for hot/cold functions"));
185 "profile-unknown-in-special-section",
cl::Hidden,
186 cl::desc(
"In profiling mode like sampleFDO, if a function doesn't have "
187 "profile, we cannot tell the function is cold for sure because "
188 "it may be a function newly added without ever being sampled. "
189 "With the flag enabled, compiler can put such profile unknown "
190 "functions into a special section, so runtime system can choose "
191 "to handle it in a different way than .text section, to save "
192 "RAM for example. "));
196 cl::desc(
"Use the basic-block-sections profile to determine the text "
197 "section prefix for hot functions. Functions with "
198 "basic-block-sections profile will be placed in `.text.hot` "
199 "regardless of their FDO profile info. Other functions won't be "
200 "impacted, i.e., their prefixes will be decided by FDO/sampleFDO "
205 cl::desc(
"Skip merging empty blocks if (frequency of empty block) / "
206 "(frequency of destination block) is greater than this ratio"));
210 cl::desc(
"Force store splitting no matter what the target query says."));
214 cl::desc(
"Enable merging of redundant sexts when one is dominating"
220 cl::desc(
"Disables combining addressing modes with different parts "
221 "in optimizeMemoryInst."));
225 cl::desc(
"Allow creation of Phis in Address sinking."));
229 cl::desc(
"Allow creation of selects in Address sinking."));
233 cl::desc(
"Allow combining of BaseReg field in Address sinking."));
237 cl::desc(
"Allow combining of BaseGV field in Address sinking."));
241 cl::desc(
"Allow combining of BaseOffs field in Address sinking."));
245 cl::desc(
"Allow combining of ScaledReg field in Address sinking."));
250 cl::desc(
"Enable splitting large offset of GEP."));
254 cl::desc(
"Enable ICMP_EQ to ICMP_S(L|G)T conversion."));
258 cl::desc(
"Enable BFI update verification for "
263 cl::desc(
"Enable converting phi types in CodeGenPrepare"));
267 cl::desc(
"Least BB number of huge function."));
272 cl::desc(
"Max number of address users to look at"));
276 cl::desc(
"Disable elimination of dead PHI nodes."));
304class TypePromotionTransaction;
306class CodeGenPrepare {
307 friend class CodeGenPrepareLegacyPass;
308 const TargetMachine *TM =
nullptr;
309 const TargetSubtargetInfo *SubtargetInfo =
nullptr;
310 const TargetLowering *TLI =
nullptr;
311 const TargetRegisterInfo *TRI =
nullptr;
312 const TargetTransformInfo *TTI =
nullptr;
313 const BasicBlockSectionsProfileReader *BBSectionsProfileReader =
nullptr;
314 const TargetLibraryInfo *TLInfo =
nullptr;
315 LoopInfo *LI =
nullptr;
316 std::unique_ptr<BlockFrequencyInfo> BFI;
317 std::unique_ptr<BranchProbabilityInfo> BPI;
318 ProfileSummaryInfo *PSI =
nullptr;
329 ValueMap<Value *, WeakTrackingVH> SunkAddrs;
332 SetOfInstrs InsertedInsts;
336 InstrToOrigTy PromotedInsts;
339 SetOfInstrs RemovedInsts;
342 DenseMap<Value *, Instruction *> SeenChainsForSExt;
347 MapVector<AssertingVH<Value>,
352 SmallSet<AssertingVH<Value>, 2> NewGEPBases;
355 DenseMap<AssertingVH<GetElementPtrInst>,
int> LargeOffsetGEPID;
358 ValueToSExts ValToSExtendedUses;
364 const DataLayout *DL =
nullptr;
368 std::unique_ptr<DominatorTree> DT;
371 CodeGenPrepare() =
default;
372 CodeGenPrepare(
const TargetMachine *TM) : TM(TM){};
374 bool IsHugeFunc =
false;
380 SmallPtrSet<BasicBlock *, 32> FreshBBs;
382 void releaseMemory() {
384 InsertedInsts.clear();
385 PromotedInsts.clear();
394 template <
typename F>
395 void resetIteratorIfInvalidatedWhileCalling(BasicBlock *BB,
F f) {
399 Value *CurValue = &*CurInstIterator;
400 WeakTrackingVH IterHandle(CurValue);
406 if (IterHandle != CurValue) {
407 CurInstIterator = BB->
begin();
413 DominatorTree &getDT(Function &
F) {
415 DT = std::make_unique<DominatorTree>(
F);
419 void removeAllAssertingVHReferences(
Value *V);
420 bool eliminateAssumptions(Function &
F);
421 bool eliminateFallThrough(Function &
F, DominatorTree *DT =
nullptr);
422 bool eliminateMostlyEmptyBlocks(Function &
F);
423 BasicBlock *findDestBlockOfMergeableEmptyBlock(BasicBlock *BB);
424 bool canMergeBlocks(
const BasicBlock *BB,
const BasicBlock *DestBB)
const;
425 void eliminateMostlyEmptyBlock(BasicBlock *BB);
426 bool isMergingEmptyBlockProfitable(BasicBlock *BB, BasicBlock *DestBB,
428 bool makeBitReverse(Instruction &
I);
430 bool optimizeInst(Instruction *
I, ModifyDT &ModifiedDT);
431 bool optimizeMemoryInst(Instruction *MemoryInst,
Value *Addr,
Type *AccessTy,
433 bool optimizeGatherScatterInst(Instruction *MemoryInst,
Value *Ptr);
434 bool optimizeMulWithOverflow(Instruction *
I,
bool IsSigned,
435 ModifyDT &ModifiedDT);
436 bool optimizeInlineAsmInst(CallInst *CS);
438 bool optimizeExt(Instruction *&
I);
439 bool optimizeExtUses(Instruction *
I);
440 bool optimizeLoadExt(LoadInst *Load);
441 bool optimizeShiftInst(BinaryOperator *BO);
442 bool optimizeFunnelShift(IntrinsicInst *Fsh);
443 bool optimizeSelectInst(SelectInst *SI);
444 bool optimizeShuffleVectorInst(ShuffleVectorInst *SVI);
445 bool optimizeSwitchType(SwitchInst *SI);
446 bool optimizeSwitchPhiConstants(SwitchInst *SI);
447 bool optimizeSwitchInst(SwitchInst *SI);
448 bool optimizeExtractElementInst(Instruction *Inst);
449 bool dupRetToEnableTailCallOpts(BasicBlock *BB, ModifyDT &ModifiedDT);
450 bool fixupDbgVariableRecord(DbgVariableRecord &
I);
451 bool fixupDbgVariableRecordsOnInst(Instruction &
I);
452 bool placeDbgValues(Function &
F);
453 bool placePseudoProbes(Function &
F);
454 bool canFormExtLd(
const SmallVectorImpl<Instruction *> &MovedExts,
455 LoadInst *&LI, Instruction *&Inst,
bool HasPromoted);
456 bool tryToPromoteExts(TypePromotionTransaction &TPT,
457 const SmallVectorImpl<Instruction *> &Exts,
458 SmallVectorImpl<Instruction *> &ProfitablyMovedExts,
459 unsigned CreatedInstsCost = 0);
460 bool mergeSExts(Function &
F);
461 bool splitLargeGEPOffsets();
462 bool optimizePhiType(PHINode *Inst, SmallPtrSetImpl<PHINode *> &Visited,
463 SmallPtrSetImpl<Instruction *> &DeletedInstrs);
464 bool optimizePhiTypes(Function &
F);
465 bool performAddressTypePromotion(
466 Instruction *&Inst,
bool AllowPromotionWithoutCommonHeader,
467 bool HasPromoted, TypePromotionTransaction &TPT,
468 SmallVectorImpl<Instruction *> &SpeculativelyMovedExts);
469 bool splitBranchCondition(Function &
F, ModifyDT &ModifiedDT);
470 bool simplifyOffsetableRelocate(GCStatepointInst &
I);
472 bool tryToSinkFreeOperands(Instruction *
I);
473 bool replaceMathCmpWithIntrinsic(BinaryOperator *BO,
Value *Arg0,
Value *Arg1,
475 bool optimizeCmp(CmpInst *Cmp, ModifyDT &ModifiedDT);
476 bool optimizeURem(Instruction *Rem);
477 bool combineToUSubWithOverflow(CmpInst *Cmp, ModifyDT &ModifiedDT);
478 bool combineToUAddWithOverflow(CmpInst *Cmp, ModifyDT &ModifiedDT);
479 bool unfoldPowerOf2Test(CmpInst *Cmp);
480 void verifyBFIUpdates(Function &
F);
481 bool _run(Function &
F);
488 CodeGenPrepareLegacyPass() : FunctionPass(ID) {
494 StringRef getPassName()
const override {
return "CodeGen Prepare"; }
496 void getAnalysisUsage(AnalysisUsage &AU)
const override {
509char CodeGenPrepareLegacyPass::ID = 0;
511bool CodeGenPrepareLegacyPass::runOnFunction(
Function &
F) {
514 auto TM = &getAnalysis<TargetPassConfig>().getTM<TargetMachine>();
515 CodeGenPrepare CGP(TM);
516 CGP.DL = &
F.getDataLayout();
519 CGP.TRI = CGP.SubtargetInfo->getRegisterInfo();
520 CGP.TLInfo = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(
F);
521 CGP.TTI = &getAnalysis<TargetTransformInfoWrapperPass>().getTTI(
F);
522 CGP.LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
523 CGP.BPI.reset(
new BranchProbabilityInfo(
F, *CGP.LI));
524 CGP.BFI.reset(
new BlockFrequencyInfo(
F, *CGP.BPI, *CGP.LI));
525 CGP.PSI = &getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI();
527 getAnalysisIfAvailable<BasicBlockSectionsProfileReaderWrapperPass>();
528 CGP.BBSectionsProfileReader = BBSPRWP ? &BBSPRWP->getBBSPR() :
nullptr;
534 "Optimize for code generation",
false,
false)
545 return new CodeGenPrepareLegacyPass();
550 CodeGenPrepare CGP(TM);
563 DL = &
F.getDataLayout();
574 BBSectionsProfileReader =
580 bool EverMadeChange =
false;
582 OptSize =
F.hasOptSize();
587 (void)
F.setSectionPrefix(
"hot");
592 if (
F.hasFnAttribute(Attribute::Hot) ||
594 (void)
F.setSectionPrefix(
"hot");
599 F.hasFnAttribute(Attribute::Cold))
600 (void)
F.setSectionPrefix(
"unlikely");
603 (void)
F.setSectionPrefix(
"unknown");
609 const DenseMap<unsigned int, unsigned int> &BypassWidths =
612 while (BB !=
nullptr) {
625 EverMadeChange |= eliminateAssumptions(
F);
629 EverMadeChange |= eliminateMostlyEmptyBlocks(
F);
631 ModifyDT ModifiedDT = ModifyDT::NotModifyDT;
633 EverMadeChange |= splitBranchCondition(
F, ModifiedDT);
647 LI->analyze(getDT(
F));
649 bool MadeChange =
true;
650 bool FuncIterated =
false;
655 if (FuncIterated && !FreshBBs.
contains(&BB))
658 ModifyDT ModifiedDTOnIteration = ModifyDT::NotModifyDT;
661 if (ModifiedDTOnIteration == ModifyDT::ModifyBBDT)
677 else if (FuncIterated)
682 if (ModifiedDTOnIteration != ModifyDT::NotModifyDT)
687 FuncIterated = IsHugeFunc;
690 MadeChange |= mergeSExts(
F);
691 if (!LargeOffsetGEPMap.
empty())
692 MadeChange |= splitLargeGEPOffsets();
693 MadeChange |= optimizePhiTypes(
F);
696 eliminateFallThrough(
F, DT.get());
700 LI->verify(getDT(
F));
704 for (Instruction *
I : RemovedInsts)
707 EverMadeChange |= MadeChange;
708 SeenChainsForSExt.
clear();
709 ValToSExtendedUses.clear();
710 RemovedInsts.clear();
711 LargeOffsetGEPMap.
clear();
712 LargeOffsetGEPID.
clear();
723 SmallSetVector<BasicBlock *, 8> WorkList;
724 for (BasicBlock &BB :
F) {
730 for (BasicBlock *Succ : Successors)
736 MadeChange |= !WorkList.
empty();
737 while (!WorkList.
empty()) {
743 for (BasicBlock *Succ : Successors)
750 if (EverMadeChange || MadeChange)
751 MadeChange |= eliminateFallThrough(
F);
753 EverMadeChange |= MadeChange;
758 for (BasicBlock &BB :
F)
759 for (Instruction &
I : BB)
762 for (
auto &
I : Statepoints)
763 EverMadeChange |= simplifyOffsetableRelocate(*
I);
768 EverMadeChange |= placeDbgValues(
F);
769 EverMadeChange |= placePseudoProbes(
F);
776 return EverMadeChange;
779bool CodeGenPrepare::eliminateAssumptions(Function &
F) {
780 bool MadeChange =
false;
781 for (BasicBlock &BB :
F) {
782 CurInstIterator = BB.begin();
783 while (CurInstIterator != BB.end()) {
788 Assume->eraseFromParent();
790 resetIteratorIfInvalidatedWhileCalling(&BB, [&]() {
801void CodeGenPrepare::removeAllAssertingVHReferences(
Value *V) {
802 LargeOffsetGEPMap.
erase(V);
803 NewGEPBases.
erase(V);
811 auto VecI = LargeOffsetGEPMap.
find(
GEP->getPointerOperand());
812 if (VecI == LargeOffsetGEPMap.
end())
815 auto &GEPVector = VecI->second;
818 if (GEPVector.empty())
819 LargeOffsetGEPMap.
erase(VecI);
823[[maybe_unused]]
void CodeGenPrepare::verifyBFIUpdates(Function &
F) {
824 DominatorTree NewDT(
F);
825 LoopInfo NewLI(NewDT);
826 BranchProbabilityInfo NewBPI(
F, NewLI, TLInfo);
827 BlockFrequencyInfo NewBFI(
F, NewBPI, NewLI);
828 NewBFI.verifyMatch(*BFI);
834bool CodeGenPrepare::eliminateFallThrough(Function &
F, DominatorTree *DT) {
842 SmallSet<WeakTrackingVH, 16> Preds;
843 for (
auto &
Block : Blocks) {
849 BasicBlock *SinglePred = BB->getSinglePredecessor();
852 if (!SinglePred || SinglePred == BB || BB->hasAddressTaken())
860 if (Term && !
Term->isConditional()) {
872 FreshBBs.
insert(SinglePred);
880 for (
const auto &Pred : Preds)
888BasicBlock *CodeGenPrepare::findDestBlockOfMergeableEmptyBlock(BasicBlock *BB) {
897 if (BBI != BB->
begin()) {
908 if (!canMergeBlocks(BB, DestBB))
918bool CodeGenPrepare::eliminateMostlyEmptyBlocks(Function &
F) {
919 SmallPtrSet<BasicBlock *, 16> Preheaders;
921 while (!LoopList.empty()) {
922 Loop *
L = LoopList.pop_back_val();
924 if (BasicBlock *Preheader =
L->getLoopPreheader())
925 Preheaders.
insert(Preheader);
928 bool MadeChange =
false;
940 for (
auto &
Block : Blocks) {
944 BasicBlock *DestBB = findDestBlockOfMergeableEmptyBlock(BB);
946 !isMergingEmptyBlockProfitable(BB, DestBB, Preheaders.
count(BB)))
949 eliminateMostlyEmptyBlock(BB);
955bool CodeGenPrepare::isMergingEmptyBlockProfitable(BasicBlock *BB,
1006 SmallPtrSet<BasicBlock *, 16> SameIncomingValueBBs;
1011 if (DestBBPred == BB)
1015 return DestPN.getIncomingValueForBlock(BB) ==
1016 DestPN.getIncomingValueForBlock(DestBBPred);
1018 SameIncomingValueBBs.
insert(DestBBPred);
1024 if (SameIncomingValueBBs.
count(Pred))
1027 BlockFrequency PredFreq = BFI->getBlockFreq(Pred);
1028 BlockFrequency
BBFreq = BFI->getBlockFreq(BB);
1030 for (
auto *SameValueBB : SameIncomingValueBBs)
1031 if (SameValueBB->getUniquePredecessor() == Pred &&
1032 DestBB == findDestBlockOfMergeableEmptyBlock(SameValueBB))
1033 BBFreq += BFI->getBlockFreq(SameValueBB);
1036 return !Limit || PredFreq <= *Limit;
1042bool CodeGenPrepare::canMergeBlocks(
const BasicBlock *BB,
1043 const BasicBlock *DestBB)
const {
1047 for (
const PHINode &PN : BB->
phis()) {
1048 for (
const User *U : PN.users()) {
1057 for (
unsigned I = 0,
E = UPN->getNumIncomingValues();
I !=
E; ++
I) {
1060 Insn->
getParent() != UPN->getIncomingBlock(
I))
1075 SmallPtrSet<const BasicBlock *, 16> BBPreds;
1078 for (
unsigned i = 0, e = BBPN->getNumIncomingValues(); i != e; ++i)
1079 BBPreds.
insert(BBPN->getIncomingBlock(i));
1087 if (BBPreds.
count(Pred)) {
1088 for (
const PHINode &PN : DestBB->
phis()) {
1089 const Value *V1 = PN.getIncomingValueForBlock(Pred);
1090 const Value *V2 = PN.getIncomingValueForBlock(BB);
1094 if (V2PN->getParent() == BB)
1095 V2 = V2PN->getIncomingValueForBlock(Pred);
1125void CodeGenPrepare::eliminateMostlyEmptyBlock(BasicBlock *BB) {
1135 if (SinglePred != DestBB) {
1136 assert(SinglePred == BB &&
1137 "Single predecessor not the same as predecessor");
1146 FreshBBs.
insert(SinglePred);
1147 FreshBBs.
erase(DestBB);
1155 for (PHINode &PN : DestBB->
phis()) {
1157 Value *InVal = PN.removeIncomingValue(BB,
false);
1162 if (InValPhi && InValPhi->
getParent() == BB) {
1171 for (
unsigned i = 0, e = BBPN->getNumIncomingValues(); i != e; ++i)
1172 PN.addIncoming(InVal, BBPN->getIncomingBlock(i));
1175 PN.addIncoming(InVal, Pred);
1205 for (
auto *ThisRelocate : AllRelocateCalls) {
1206 auto K = std::make_pair(ThisRelocate->getBasePtrIndex(),
1207 ThisRelocate->getDerivedPtrIndex());
1208 RelocateIdxMap.
insert(std::make_pair(K, ThisRelocate));
1210 for (
auto &Item : RelocateIdxMap) {
1211 std::pair<unsigned, unsigned>
Key = Item.first;
1212 if (
Key.first ==
Key.second)
1217 auto BaseKey = std::make_pair(
Key.first,
Key.first);
1220 auto MaybeBase = RelocateIdxMap.
find(BaseKey);
1221 if (MaybeBase == RelocateIdxMap.
end())
1226 RelocateInstMap[MaybeBase->second].push_back(
I);
1234 for (
unsigned i = 1; i <
GEP->getNumOperands(); i++) {
1237 if (!
Op ||
Op->getZExtValue() > 20)
1241 for (
unsigned i = 1; i <
GEP->getNumOperands(); i++)
1251 bool MadeChange =
false;
1258 for (
auto R = RelocatedBase->
getParent()->getFirstInsertionPt();
1259 &*R != RelocatedBase; ++R)
1263 RelocatedBase->
moveBefore(RI->getIterator());
1270 "Not relocating a derived object of the original base object");
1271 if (ToReplace->getBasePtrIndex() == ToReplace->getDerivedPtrIndex()) {
1276 if (RelocatedBase->
getParent() != ToReplace->getParent()) {
1286 if (!Derived || Derived->getPointerOperand() !=
Base)
1295 "Should always have one since it's not a terminator");
1299 Builder.SetCurrentDebugLocation(ToReplace->getDebugLoc());
1323 Value *ActualRelocatedBase = RelocatedBase;
1324 if (RelocatedBase->
getType() !=
Base->getType()) {
1325 ActualRelocatedBase =
1326 Builder.CreateBitCast(RelocatedBase,
Base->getType());
1328 Value *Replacement =
1329 Builder.CreateGEP(Derived->getSourceElementType(), ActualRelocatedBase,
1335 Value *ActualReplacement = Replacement;
1336 if (Replacement->
getType() != ToReplace->getType()) {
1338 Builder.CreateBitCast(Replacement, ToReplace->
getType());
1341 ToReplace->eraseFromParent();
1365bool CodeGenPrepare::simplifyOffsetableRelocate(GCStatepointInst &
I) {
1366 bool MadeChange =
false;
1368 for (
auto *U :
I.users())
1375 if (AllRelocateCalls.
size() < 2)
1380 MapVector<GCRelocateInst *, SmallVector<GCRelocateInst *, 0>> RelocateInstMap;
1382 if (RelocateInstMap.
empty())
1385 for (
auto &Item : RelocateInstMap)
1399 bool MadeChange =
false;
1402 Use &TheUse = UI.getUse();
1409 UserBB = PN->getIncomingBlock(TheUse);
1417 if (
User->isEHPad())
1427 if (UserBB == DefBB)
1431 CastInst *&InsertedCast = InsertedCasts[UserBB];
1433 if (!InsertedCast) {
1441 TheUse = InsertedCast;
1467 ASC->getDestAddressSpace()))
1522static std::optional<std::pair<Instruction *, Constant *>>
1525 if (!L || L->getHeader() != PN->
getParent() || !L->getLoopLatch())
1526 return std::nullopt;
1529 if (!IVInc || LI->
getLoopFor(IVInc->getParent()) != L)
1530 return std::nullopt;
1534 return std::make_pair(IVInc, Step);
1535 return std::nullopt;
1548 return IVInc->first ==
I;
1552bool CodeGenPrepare::replaceMathCmpWithIntrinsic(BinaryOperator *BO,
1556 auto IsReplacableIVIncrement = [
this, &
Cmp](BinaryOperator *BO) {
1559 const Loop *
L = LI->getLoopFor(BO->
getParent());
1560 assert(L &&
"L should not be null after isIVIncrement()");
1562 if (LI->getLoopFor(
Cmp->getParent()) != L)
1568 auto &DT = getDT(*BO->
getParent()->getParent());
1577 if (BO->
getParent() !=
Cmp->getParent() && !IsReplacableIVIncrement(BO)) {
1600 if (BO->
getOpcode() == Instruction::Add &&
1601 IID == Intrinsic::usub_with_overflow) {
1608 for (Instruction &Iter : *
Cmp->getParent()) {
1611 if ((BO->
getOpcode() != Instruction::Xor && &Iter == BO) || &Iter == Cmp) {
1616 assert(InsertPt !=
nullptr &&
"Parent block did not contain cmp or binop");
1619 Value *MathOV = Builder.CreateBinaryIntrinsic(IID, Arg0, Arg1);
1620 if (BO->
getOpcode() != Instruction::Xor) {
1621 Value *Math = Builder.CreateExtractValue(MathOV, 0,
"math");
1625 "Patterns with XOr should use the BO only in the compare");
1626 Value *OV = Builder.CreateExtractValue(MathOV, 1,
"ov");
1628 Cmp->eraseFromParent();
1638 Value *
A = Cmp->getOperand(0), *
B = Cmp->getOperand(1);
1646 B = ConstantInt::get(
B->getType(), 1);
1654 for (
User *U :
A->users()) {
1665bool CodeGenPrepare::combineToUAddWithOverflow(CmpInst *Cmp,
1666 ModifyDT &ModifiedDT) {
1667 bool EdgeCase =
false;
1669 BinaryOperator *
Add;
1674 A =
Add->getOperand(0);
1675 B =
Add->getOperand(1);
1681 Add->hasNUsesOrMore(EdgeCase ? 1 : 2)))
1687 if (
Add->getParent() !=
Cmp->getParent() && !
Add->hasOneUse())
1690 if (!replaceMathCmpWithIntrinsic(
Add,
A,
B, Cmp,
1691 Intrinsic::uadd_with_overflow))
1695 ModifiedDT = ModifyDT::ModifyInstDT;
1699bool CodeGenPrepare::combineToUSubWithOverflow(CmpInst *Cmp,
1700 ModifyDT &ModifiedDT) {
1707 ICmpInst::Predicate Pred =
Cmp->getPredicate();
1708 if (Pred == ICmpInst::ICMP_UGT) {
1710 Pred = ICmpInst::ICMP_ULT;
1714 B = ConstantInt::get(
B->getType(), 1);
1715 Pred = ICmpInst::ICMP_ULT;
1720 Pred = ICmpInst::ICMP_ULT;
1722 if (Pred != ICmpInst::ICMP_ULT)
1729 BinaryOperator *
Sub =
nullptr;
1730 for (User *U : CmpVariableOperand->
users()) {
1738 const APInt *CmpC, *AddC;
1750 Sub->hasNUsesOrMore(1)))
1756 if (
Sub->getParent() !=
Cmp->getParent() && !
Sub->hasOneUse())
1759 if (!replaceMathCmpWithIntrinsic(
Sub,
Sub->getOperand(0),
Sub->getOperand(1),
1760 Cmp, Intrinsic::usub_with_overflow))
1764 ModifiedDT = ModifyDT::ModifyInstDT;
1771bool CodeGenPrepare::unfoldPowerOf2Test(CmpInst *Cmp) {
1785 if (!IsStrictlyPowerOf2Test && !IsPowerOf2OrZeroTest)
1791 Type *OpTy =
X->getType();
1799 if (Pred == ICmpInst::ICMP_EQ) {
1800 Cmp->setOperand(1, ConstantInt::get(OpTy, 2));
1801 Cmp->setPredicate(ICmpInst::ICMP_ULT);
1803 Cmp->setPredicate(ICmpInst::ICMP_UGT);
1809 if (IsPowerOf2OrZeroTest ||
1820 NewCmp = Builder.CreateICmp(NewPred,
And, ConstantInt::getNullValue(OpTy));
1829 NewCmp = Builder.CreateICmp(NewPred,
Xor,
Sub);
1832 Cmp->replaceAllUsesWith(NewCmp);
1852 bool UsedInPhiOrCurrentBlock =
any_of(Cmp->users(), [Cmp](
User *U) {
1853 return isa<PHINode>(U) ||
1854 cast<Instruction>(U)->getParent() == Cmp->getParent();
1859 if (UsedInPhiOrCurrentBlock && Cmp->getOperand(0)->getType()->isIntegerTy() &&
1860 Cmp->getOperand(0)->getType()->getScalarSizeInBits() >
1861 DL.getLargestLegalIntTypeSizeInBits())
1867 bool MadeChange =
false;
1870 Use &TheUse = UI.getUse();
1885 if (UserBB == DefBB)
1889 CmpInst *&InsertedCmp = InsertedCmps[UserBB];
1895 Cmp->getOperand(0), Cmp->getOperand(1),
"");
1902 TheUse = InsertedCmp;
1908 if (Cmp->use_empty()) {
1909 Cmp->eraseFromParent();
1946 for (
User *U : Cmp->users()) {
1968 if (CmpBB != FalseBB)
1971 Value *CmpOp0 = Cmp->getOperand(0), *CmpOp1 = Cmp->getOperand(1);
1985 for (
User *U : Cmp->users()) {
1994 SI->swapProfMetadata();
2006 Value *Op0 = Cmp->getOperand(0);
2007 Value *Op1 = Cmp->getOperand(1);
2016 unsigned NumInspected = 0;
2019 if (++NumInspected > 128)
2027 if (GoodToSwap > 0) {
2028 Cmp->swapOperands();
2048 auto ShouldReverseTransform = [](
FPClassTest ClassTest) {
2051 auto [ClassVal, ClassTest] =
2057 if (!ShouldReverseTransform(ClassTest) && !ShouldReverseTransform(~ClassTest))
2061 Value *IsFPClass = Builder.createIsFPClass(ClassVal, ClassTest);
2062 Cmp->replaceAllUsesWith(IsFPClass);
2070 Value *Incr, *RemAmt;
2075 Value *AddInst, *AddOffset;
2078 if (PN !=
nullptr) {
2080 AddOffset =
nullptr;
2089 if (PN !=
nullptr) {
2102 if (PN->getNumIncomingValues() != 2)
2107 if (!L || !L->getLoopPreheader() || !L->getLoopLatch())
2111 if (!L->contains(Rem))
2115 if (!L->isLoopInvariant(RemAmt))
2119 if (AddOffset && !L->isLoopInvariant(AddOffset))
2140 AddInstOut = AddInst;
2141 AddOffsetOut = AddOffset;
2160 Value *AddOffset, *RemAmt, *AddInst;
2163 AddOffset, LoopIncrPN))
2188 assert(AddOffset &&
"We found an add but missing values");
2207 Builder.SetInsertPoint(LoopIncrPN);
2208 PHINode *NewRem = Builder.CreatePHI(Ty, 2);
2213 Value *RemAdd = Builder.CreateNUWAdd(NewRem, ConstantInt::get(Ty, 1));
2218 NewRem->
addIncoming(Start, L->getLoopPreheader());
2223 FreshBBs.
insert(L->getLoopLatch());
2234bool CodeGenPrepare::optimizeURem(Instruction *Rem) {
2240bool CodeGenPrepare::optimizeCmp(CmpInst *Cmp, ModifyDT &ModifiedDT) {
2244 if (combineToUAddWithOverflow(Cmp, ModifiedDT))
2247 if (combineToUSubWithOverflow(Cmp, ModifiedDT))
2250 if (unfoldPowerOf2Test(Cmp))
2271 SetOfInstrs &InsertedInsts) {
2274 assert(!InsertedInsts.count(AndI) &&
2275 "Attempting to optimize already optimized and instruction");
2276 (void)InsertedInsts;
2290 for (
auto *U : AndI->
users()) {
2298 if (!CmpC || !CmpC->
isZero())
2313 Use &TheUse = UI.getUse();
2331 TheUse = InsertedAnd;
2348 if (
User->getOpcode() != Instruction::And ||
2354 if ((Cimm & (Cimm + 1)).getBoolValue())
2368 bool MadeChange =
false;
2371 TruncE = TruncI->user_end();
2372 TruncUI != TruncE;) {
2374 Use &TruncTheUse = TruncUI.getUse();
2399 if (UserBB == TruncUserBB)
2403 CastInst *&InsertedTrunc = InsertedTruncs[TruncUserBB];
2405 if (!InsertedShift && !InsertedTrunc) {
2409 if (ShiftI->
getOpcode() == Instruction::AShr)
2411 BinaryOperator::CreateAShr(ShiftI->
getOperand(0), CI,
"");
2414 BinaryOperator::CreateLShr(ShiftI->
getOperand(0), CI,
"");
2422 TruncInsertPt.setHeadBit(
true);
2423 assert(TruncInsertPt != TruncUserBB->
end());
2427 InsertedTrunc->
insertBefore(*TruncUserBB, TruncInsertPt);
2428 InsertedTrunc->
setDebugLoc(TruncI->getDebugLoc());
2432 TruncTheUse = InsertedTrunc;
2465 bool MadeChange =
false;
2468 Use &TheUse = UI.getUse();
2482 if (UserBB == DefBB) {
2510 if (!InsertedShift) {
2514 if (ShiftI->
getOpcode() == Instruction::AShr)
2516 BinaryOperator::CreateAShr(ShiftI->
getOperand(0), CI,
"");
2519 BinaryOperator::CreateLShr(ShiftI->
getOperand(0), CI,
"");
2527 TheUse = InsertedShift;
2574 unsigned SizeInBits = Ty->getScalarSizeInBits();
2575 if (Ty->isVectorTy())
2587 FreshBBs.
insert(CallBlock);
2594 SplitPt.setHeadBit(
true);
2597 FreshBBs.
insert(EndBlock);
2602 L->addBasicBlockToLoop(CallBlock, LI);
2603 L->addBasicBlockToLoop(EndBlock, LI);
2609 Builder.SetCurrentDebugLocation(CountZeros->
getDebugLoc());
2616 Op = Builder.CreateFreeze(
Op,
Op->getName() +
".fr");
2617 Value *Cmp = Builder.CreateICmpEQ(
Op, Zero,
"cmpz");
2618 Builder.CreateCondBr(Cmp, EndBlock, CallBlock);
2623 Builder.SetInsertPoint(EndBlock, EndBlock->
begin());
2624 PHINode *PN = Builder.CreatePHI(Ty, 2,
"ctz");
2634 ModifiedDT = ModifyDT::ModifyBBDT;
2638bool CodeGenPrepare::optimizeCallInst(CallInst *CI, ModifyDT &ModifiedDT) {
2642 if (CI->
isInlineAsm() && optimizeInlineAsmInst(CI))
2650 for (
auto &Arg : CI->
args()) {
2655 if (!Arg->getType()->isPointerTy())
2657 APInt
Offset(
DL->getIndexSizeInBits(
2660 Value *Val = Arg->stripAndAccumulateInBoundsConstantOffsets(*
DL,
Offset);
2661 uint64_t Offset2 =
Offset.getLimitedValue();
2667 if (AllocaSize && AllocaSize->getKnownMinValue() >= MinSize + Offset2)
2685 MaybeAlign MIDestAlign =
MI->getDestAlign();
2686 if (!MIDestAlign || DestAlign > *MIDestAlign)
2687 MI->setDestAlignment(DestAlign);
2689 MaybeAlign MTISrcAlign = MTI->getSourceAlign();
2691 if (!MTISrcAlign || SrcAlign > *MTISrcAlign)
2692 MTI->setSourceAlignment(SrcAlign);
2702 for (
auto &Arg : CI->
args()) {
2703 if (!Arg->getType()->isPointerTy())
2705 unsigned AS = Arg->getType()->getPointerAddressSpace();
2706 if (optimizeMemoryInst(CI, Arg, Arg->getType(), AS))
2712 switch (
II->getIntrinsicID()) {
2715 case Intrinsic::assume:
2717 case Intrinsic::allow_runtime_check:
2718 case Intrinsic::allow_ubsan_check:
2719 case Intrinsic::experimental_widenable_condition: {
2723 if (
II->use_empty()) {
2724 II->eraseFromParent();
2728 resetIteratorIfInvalidatedWhileCalling(BB, [&]() {
2733 case Intrinsic::objectsize:
2735 case Intrinsic::is_constant:
2737 case Intrinsic::aarch64_stlxr:
2738 case Intrinsic::aarch64_stxr: {
2747 InsertedInsts.insert(ExtVal);
2751 case Intrinsic::launder_invariant_group:
2752 case Intrinsic::strip_invariant_group: {
2753 Value *ArgVal =
II->getArgOperand(0);
2754 auto it = LargeOffsetGEPMap.
find(
II);
2755 if (it != LargeOffsetGEPMap.
end()) {
2759 auto GEPs = std::move(it->second);
2760 LargeOffsetGEPMap[ArgVal].append(GEPs.begin(), GEPs.end());
2765 II->eraseFromParent();
2768 case Intrinsic::cttz:
2769 case Intrinsic::ctlz:
2773 case Intrinsic::fshl:
2774 case Intrinsic::fshr:
2775 return optimizeFunnelShift(
II);
2776 case Intrinsic::masked_gather:
2777 return optimizeGatherScatterInst(
II,
II->getArgOperand(0));
2778 case Intrinsic::masked_scatter:
2779 return optimizeGatherScatterInst(
II,
II->getArgOperand(1));
2780 case Intrinsic::masked_load:
2783 if (VT->getNumElements() == 1) {
2784 Value *PtrVal =
II->getArgOperand(0);
2786 if (optimizeMemoryInst(
II, PtrVal, VT->getElementType(), AS))
2791 case Intrinsic::masked_store:
2795 if (VT->getNumElements() == 1) {
2796 Value *PtrVal =
II->getArgOperand(1);
2798 if (optimizeMemoryInst(
II, PtrVal, VT->getElementType(), AS))
2803 case Intrinsic::umul_with_overflow:
2804 return optimizeMulWithOverflow(
II,
false, ModifiedDT);
2805 case Intrinsic::smul_with_overflow:
2806 return optimizeMulWithOverflow(
II,
true, ModifiedDT);
2809 SmallVector<Value *, 2> PtrOps;
2812 while (!PtrOps.
empty()) {
2815 if (optimizeMemoryInst(
II, PtrVal, AccessTy, AS))
2829 FortifiedLibCallSimplifier Simplifier(TLInfo,
true);
2831 if (
Value *V = Simplifier.optimizeCall(CI, Builder)) {
2841 auto GetUniformReturnValue = [](
const Function *
F) -> GlobalVariable * {
2842 if (!
F->getReturnType()->isPointerTy())
2845 GlobalVariable *UniformValue =
nullptr;
2846 for (
auto &BB : *
F) {
2851 else if (V != UniformValue)
2859 return UniformValue;
2862 if (
Callee->hasExactDefinition()) {
2863 if (GlobalVariable *RV = GetUniformReturnValue(Callee)) {
2864 bool MadeChange =
false;
2890 switch (
II->getIntrinsicID()) {
2891 case Intrinsic::memset:
2892 case Intrinsic::memcpy:
2893 case Intrinsic::memmove:
2901 if (Callee && TLInfo && TLInfo->
getLibFunc(*Callee, LF))
2903 case LibFunc_strcpy:
2904 case LibFunc_strncpy:
2905 case LibFunc_strcat:
2906 case LibFunc_strncat:
2947bool CodeGenPrepare::dupRetToEnableTailCallOpts(BasicBlock *BB,
2948 ModifyDT &ModifiedDT) {
2956 assert(LI->getLoopFor(BB) ==
nullptr &&
"A return block cannot be in a loop");
2958 PHINode *PN =
nullptr;
2959 ExtractValueInst *EVI =
nullptr;
2960 BitCastInst *BCI =
nullptr;
2980 auto isLifetimeEndOrBitCastFor = [](
const Instruction *Inst) {
2986 return II->getIntrinsicID() == Intrinsic::lifetime_end;
2992 auto isFakeUse = [&FakeUses](
const Instruction *Inst) {
2994 II &&
II->getIntrinsicID() == Intrinsic::fake_use) {
3016 isLifetimeEndOrBitCastFor(&*BI) || isFakeUse(&*BI))
3023 auto MayBePermittedAsTailCall = [&](
const auto *CI) {
3040 MayBePermittedAsTailCall(CI)) {
3061 MayBePermittedAsTailCall(CI)) {
3068 SmallPtrSet<BasicBlock *, 4> VisitedBBs;
3070 if (!VisitedBBs.
insert(Pred).second)
3072 if (Instruction *
I = Pred->rbegin()->getPrevNode()) {
3074 if (CI && CI->
use_empty() && MayBePermittedAsTailCall(CI)) {
3089 for (
auto const &TailCallBB : TailCallBBs) {
3099 BFI->getBlockFreq(BB) >= BFI->getBlockFreq(TailCallBB));
3100 BFI->setBlockFreq(BB,
3101 (BFI->getBlockFreq(BB) - BFI->getBlockFreq(TailCallBB)));
3102 ModifiedDT = ModifyDT::ModifyBBDT;
3111 for (
auto *CI : CallInsts) {
3112 for (
auto const *FakeUse : FakeUses) {
3113 auto *ClonedInst = FakeUse->clone();
3131struct ExtAddrMode :
public TargetLowering::AddrMode {
3132 Value *BaseReg =
nullptr;
3133 Value *ScaledReg =
nullptr;
3134 Value *OriginalValue =
nullptr;
3135 bool InBounds =
true;
3139 BaseRegField = 0x01,
3141 BaseOffsField = 0x04,
3142 ScaledRegField = 0x08,
3144 MultipleFields = 0xff
3147 ExtAddrMode() =
default;
3149 void print(raw_ostream &OS)
const;
3156 if (ScaledReg == From)
3160 FieldName
compare(
const ExtAddrMode &other) {
3163 if (BaseReg && other.
BaseReg &&
3165 return MultipleFields;
3166 if (BaseGV && other.BaseGV && BaseGV->getType() != other.BaseGV->getType())
3167 return MultipleFields;
3170 return MultipleFields;
3173 if (InBounds != other.InBounds)
3174 return MultipleFields;
3177 unsigned Result = NoField;
3180 if (BaseGV != other.BaseGV)
3182 if (BaseOffs != other.BaseOffs)
3185 Result |= ScaledRegField;
3188 if (Scale && other.
Scale && Scale != other.
Scale)
3192 return MultipleFields;
3194 return static_cast<FieldName
>(
Result);
3204 return !BaseOffs && !Scale && !(BaseGV &&
BaseReg);
3215 case ScaledRegField:
3222 void SetCombinedField(FieldName
Field,
Value *V,
3223 const SmallVectorImpl<ExtAddrMode> &AddrModes) {
3228 case ExtAddrMode::BaseRegField:
3231 case ExtAddrMode::BaseGVField:
3234 assert(BaseReg ==
nullptr);
3238 case ExtAddrMode::ScaledRegField:
3243 for (
const ExtAddrMode &AM : AddrModes)
3249 case ExtAddrMode::BaseOffsField:
3252 assert(ScaledReg ==
nullptr);
3262static inline raw_ostream &
operator<<(raw_ostream &OS,
const ExtAddrMode &AM) {
3268#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
3269void ExtAddrMode::print(raw_ostream &OS)
const {
3270 bool NeedPlus =
false;
3276 BaseGV->printAsOperand(OS,
false);
3281 OS << (NeedPlus ?
" + " :
"") << BaseOffs;
3286 OS << (NeedPlus ?
" + " :
"") <<
"Base:";
3287 BaseReg->printAsOperand(OS,
false);
3291 OS << (NeedPlus ?
" + " :
"") << Scale <<
"*";
3314class TypePromotionTransaction {
3318 class TypePromotionAction {
3326 TypePromotionAction(Instruction *Inst) : Inst(Inst) {}
3328 virtual ~TypePromotionAction() =
default;
3335 virtual void undo() = 0;
3340 virtual void commit() {
3346 class InsertionHandler {
3355 std::optional<DbgRecord::self_iterator> BeforeDbgRecord = std::nullopt;
3358 bool HasPrevInstruction;
3362 InsertionHandler(Instruction *Inst) {
3370 if (HasPrevInstruction) {
3378 void insert(Instruction *Inst) {
3379 if (HasPrevInstruction) {
3391 Inst->
getParent()->reinsertInstInDbgRecords(Inst, BeforeDbgRecord);
3396 class InstructionMoveBefore :
public TypePromotionAction {
3398 InsertionHandler Position;
3403 : TypePromotionAction(Inst), Position(Inst) {
3404 LLVM_DEBUG(
dbgs() <<
"Do: move: " << *Inst <<
"\nbefore: " << *Before
3410 void undo()
override {
3412 Position.insert(Inst);
3417 class OperandSetter :
public TypePromotionAction {
3426 OperandSetter(Instruction *Inst,
unsigned Idx,
Value *NewVal)
3427 : TypePromotionAction(Inst), Idx(Idx) {
3429 <<
"for:" << *Inst <<
"\n"
3430 <<
"with:" << *NewVal <<
"\n");
3436 void undo()
override {
3438 <<
"for: " << *Inst <<
"\n"
3439 <<
"with: " << *Origin <<
"\n");
3446 class OperandsHider :
public TypePromotionAction {
3448 SmallVector<Value *, 4> OriginalValues;
3452 OperandsHider(Instruction *Inst) : TypePromotionAction(Inst) {
3455 OriginalValues.
reserve(NumOpnds);
3456 for (
unsigned It = 0; It < NumOpnds; ++It) {
3468 void undo()
override {
3470 for (
unsigned It = 0, EndIt = OriginalValues.
size(); It != EndIt; ++It)
3476 class TruncBuilder :
public TypePromotionAction {
3483 TruncBuilder(Instruction *Opnd,
Type *Ty) : TypePromotionAction(Opnd) {
3485 Builder.SetCurrentDebugLocation(
DebugLoc());
3486 Val = Builder.CreateTrunc(Opnd, Ty,
"promoted");
3491 Value *getBuiltValue() {
return Val; }
3494 void undo()
override {
3497 IVal->eraseFromParent();
3502 class SExtBuilder :
public TypePromotionAction {
3509 SExtBuilder(Instruction *InsertPt,
Value *Opnd,
Type *Ty)
3510 : TypePromotionAction(InsertPt) {
3512 Val = Builder.CreateSExt(Opnd, Ty,
"promoted");
3517 Value *getBuiltValue() {
return Val; }
3520 void undo()
override {
3523 IVal->eraseFromParent();
3528 class ZExtBuilder :
public TypePromotionAction {
3535 ZExtBuilder(Instruction *InsertPt,
Value *Opnd,
Type *Ty)
3536 : TypePromotionAction(InsertPt) {
3538 Builder.SetCurrentDebugLocation(
DebugLoc());
3539 Val = Builder.CreateZExt(Opnd, Ty,
"promoted");
3544 Value *getBuiltValue() {
return Val; }
3547 void undo()
override {
3550 IVal->eraseFromParent();
3555 class TypeMutator :
public TypePromotionAction {
3561 TypeMutator(Instruction *Inst,
Type *NewTy)
3562 : TypePromotionAction(Inst), OrigTy(Inst->
getType()) {
3563 LLVM_DEBUG(
dbgs() <<
"Do: MutateType: " << *Inst <<
" with " << *NewTy
3569 void undo()
override {
3570 LLVM_DEBUG(
dbgs() <<
"Undo: MutateType: " << *Inst <<
" with " << *OrigTy
3577 class UsesReplacer :
public TypePromotionAction {
3579 struct InstructionAndIdx {
3586 InstructionAndIdx(Instruction *Inst,
unsigned Idx)
3587 : Inst(Inst), Idx(Idx) {}
3593 SmallVector<DbgVariableRecord *, 1> DbgVariableRecords;
3603 UsesReplacer(Instruction *Inst,
Value *New)
3604 : TypePromotionAction(Inst),
New(
New) {
3605 LLVM_DEBUG(
dbgs() <<
"Do: UsersReplacer: " << *Inst <<
" with " << *New
3608 for (Use &U : Inst->
uses()) {
3610 OriginalUses.
push_back(InstructionAndIdx(UserI,
U.getOperandNo()));
3621 void undo()
override {
3623 for (InstructionAndIdx &Use : OriginalUses)
3624 Use.Inst->setOperand(
Use.Idx, Inst);
3629 for (DbgVariableRecord *DVR : DbgVariableRecords)
3630 DVR->replaceVariableLocationOp(New, Inst);
3635 class InstructionRemover :
public TypePromotionAction {
3637 InsertionHandler Inserter;
3641 OperandsHider Hider;
3644 UsesReplacer *Replacer =
nullptr;
3647 SetOfInstrs &RemovedInsts;
3654 InstructionRemover(Instruction *Inst, SetOfInstrs &RemovedInsts,
3655 Value *New =
nullptr)
3656 : TypePromotionAction(Inst), Inserter(Inst), Hider(Inst),
3657 RemovedInsts(RemovedInsts) {
3659 Replacer =
new UsesReplacer(Inst, New);
3660 LLVM_DEBUG(
dbgs() <<
"Do: InstructionRemover: " << *Inst <<
"\n");
3661 RemovedInsts.insert(Inst);
3668 ~InstructionRemover()
override {
delete Replacer; }
3670 InstructionRemover &operator=(
const InstructionRemover &other) =
delete;
3671 InstructionRemover(
const InstructionRemover &other) =
delete;
3675 void undo()
override {
3676 LLVM_DEBUG(
dbgs() <<
"Undo: InstructionRemover: " << *Inst <<
"\n");
3677 Inserter.insert(Inst);
3681 RemovedInsts.erase(Inst);
3689 using ConstRestorationPt =
const TypePromotionAction *;
3691 TypePromotionTransaction(SetOfInstrs &RemovedInsts)
3692 : RemovedInsts(RemovedInsts) {}
3699 void rollback(ConstRestorationPt Point);
3702 ConstRestorationPt getRestorationPoint()
const;
3707 void setOperand(Instruction *Inst,
unsigned Idx,
Value *NewVal);
3716 void mutateType(Instruction *Inst,
Type *NewTy);
3719 Value *createTrunc(Instruction *Opnd,
Type *Ty);
3732 SmallVectorImpl<std::unique_ptr<TypePromotionAction>>::iterator;
3734 SetOfInstrs &RemovedInsts;
3739void TypePromotionTransaction::setOperand(Instruction *Inst,
unsigned Idx,
3741 Actions.push_back(std::make_unique<TypePromotionTransaction::OperandSetter>(
3742 Inst, Idx, NewVal));
3745void TypePromotionTransaction::eraseInstruction(Instruction *Inst,
3748 std::make_unique<TypePromotionTransaction::InstructionRemover>(
3749 Inst, RemovedInsts, NewVal));
3752void TypePromotionTransaction::replaceAllUsesWith(Instruction *Inst,
3755 std::make_unique<TypePromotionTransaction::UsesReplacer>(Inst, New));
3758void TypePromotionTransaction::mutateType(Instruction *Inst,
Type *NewTy) {
3760 std::make_unique<TypePromotionTransaction::TypeMutator>(Inst, NewTy));
3763Value *TypePromotionTransaction::createTrunc(Instruction *Opnd,
Type *Ty) {
3764 std::unique_ptr<TruncBuilder> Ptr(
new TruncBuilder(Opnd, Ty));
3765 Value *Val = Ptr->getBuiltValue();
3766 Actions.push_back(std::move(Ptr));
3770Value *TypePromotionTransaction::createSExt(Instruction *Inst,
Value *Opnd,
3772 std::unique_ptr<SExtBuilder> Ptr(
new SExtBuilder(Inst, Opnd, Ty));
3773 Value *Val = Ptr->getBuiltValue();
3774 Actions.push_back(std::move(Ptr));
3778Value *TypePromotionTransaction::createZExt(Instruction *Inst,
Value *Opnd,
3780 std::unique_ptr<ZExtBuilder> Ptr(
new ZExtBuilder(Inst, Opnd, Ty));
3781 Value *Val = Ptr->getBuiltValue();
3782 Actions.push_back(std::move(Ptr));
3786TypePromotionTransaction::ConstRestorationPt
3787TypePromotionTransaction::getRestorationPoint()
const {
3788 return !Actions.empty() ? Actions.back().get() :
nullptr;
3791bool TypePromotionTransaction::commit() {
3792 for (std::unique_ptr<TypePromotionAction> &Action : Actions)
3799void TypePromotionTransaction::rollback(
3800 TypePromotionTransaction::ConstRestorationPt Point) {
3801 while (!Actions.empty() && Point != Actions.back().get()) {
3802 std::unique_ptr<TypePromotionAction> Curr = Actions.pop_back_val();
3812class AddressingModeMatcher {
3813 SmallVectorImpl<Instruction *> &AddrModeInsts;
3814 const TargetLowering &TLI;
3815 const TargetRegisterInfo &
TRI;
3816 const DataLayout &
DL;
3818 const std::function<
const DominatorTree &()> getDTFn;
3831 const SetOfInstrs &InsertedInsts;
3834 InstrToOrigTy &PromotedInsts;
3837 TypePromotionTransaction &TPT;
3840 std::pair<AssertingVH<GetElementPtrInst>, int64_t> &LargeOffsetGEP;
3844 bool IgnoreProfitability;
3847 bool OptSize =
false;
3849 ProfileSummaryInfo *PSI;
3850 BlockFrequencyInfo *BFI;
3852 AddressingModeMatcher(
3853 SmallVectorImpl<Instruction *> &AMI,
const TargetLowering &TLI,
3854 const TargetRegisterInfo &
TRI,
const LoopInfo &LI,
3855 const std::function<
const DominatorTree &()> getDTFn,
Type *AT,
3856 unsigned AS, Instruction *
MI, ExtAddrMode &AM,
3857 const SetOfInstrs &InsertedInsts, InstrToOrigTy &PromotedInsts,
3858 TypePromotionTransaction &TPT,
3859 std::pair<AssertingVH<GetElementPtrInst>, int64_t> &LargeOffsetGEP,
3860 bool OptSize, ProfileSummaryInfo *PSI, BlockFrequencyInfo *BFI)
3861 : AddrModeInsts(AMI), TLI(TLI),
TRI(
TRI),
3862 DL(
MI->getDataLayout()), LI(LI), getDTFn(getDTFn),
3863 AccessTy(AT), AddrSpace(AS), MemoryInst(
MI),
AddrMode(AM),
3864 InsertedInsts(InsertedInsts), PromotedInsts(PromotedInsts), TPT(TPT),
3865 LargeOffsetGEP(LargeOffsetGEP), OptSize(OptSize), PSI(PSI), BFI(BFI) {
3866 IgnoreProfitability =
false;
3878 Match(
Value *V,
Type *AccessTy,
unsigned AS, Instruction *MemoryInst,
3879 SmallVectorImpl<Instruction *> &AddrModeInsts,
3880 const TargetLowering &TLI,
const LoopInfo &LI,
3881 const std::function<
const DominatorTree &()> getDTFn,
3882 const TargetRegisterInfo &
TRI,
const SetOfInstrs &InsertedInsts,
3883 InstrToOrigTy &PromotedInsts, TypePromotionTransaction &TPT,
3884 std::pair<AssertingVH<GetElementPtrInst>, int64_t> &LargeOffsetGEP,
3885 bool OptSize, ProfileSummaryInfo *PSI, BlockFrequencyInfo *BFI) {
3888 bool Success = AddressingModeMatcher(AddrModeInsts, TLI,
TRI, LI, getDTFn,
3889 AccessTy, AS, MemoryInst, Result,
3890 InsertedInsts, PromotedInsts, TPT,
3891 LargeOffsetGEP, OptSize, PSI, BFI)
3899 bool matchScaledValue(
Value *ScaleReg, int64_t Scale,
unsigned Depth);
3901 bool matchOperationAddr(User *AddrInst,
unsigned Opcode,
unsigned Depth,
3902 bool *MovedAway =
nullptr);
3903 bool isProfitableToFoldIntoAddressingMode(Instruction *
I,
3904 ExtAddrMode &AMBefore,
3905 ExtAddrMode &AMAfter);
3906 bool valueAlreadyLiveAtInst(
Value *Val,
Value *KnownLive1,
Value *KnownLive2);
3907 bool isPromotionProfitable(
unsigned NewCost,
unsigned OldCost,
3908 Value *PromotedOperand)
const;
3914class PhiNodeSetIterator {
3915 PhiNodeSet *
const Set;
3916 size_t CurrentIndex = 0;
3921 PhiNodeSetIterator(PhiNodeSet *
const Set,
size_t Start);
3923 PhiNodeSetIterator &operator++();
3939 friend class PhiNodeSetIterator;
3941 using MapType = SmallDenseMap<PHINode *, size_t, 32>;
3942 using iterator = PhiNodeSetIterator;
3957 size_t FirstValidElement = 0;
3963 bool insert(PHINode *Ptr) {
3964 if (NodeMap.insert(std::make_pair(Ptr,
NodeList.
size())).second) {
3974 bool erase(PHINode *Ptr) {
3975 if (NodeMap.erase(Ptr)) {
3976 SkipRemovedElements(FirstValidElement);
3986 FirstValidElement = 0;
3992 if (FirstValidElement == 0)
3993 SkipRemovedElements(FirstValidElement);
3994 return PhiNodeSetIterator(
this, FirstValidElement);
4001 size_t size()
const {
return NodeMap.size(); }
4004 size_t count(PHINode *Ptr)
const {
return NodeMap.count(Ptr); }
4012 void SkipRemovedElements(
size_t &CurrentIndex) {
4014 auto it = NodeMap.find(NodeList[CurrentIndex]);
4017 if (it != NodeMap.end() && it->second == CurrentIndex)
4024PhiNodeSetIterator::PhiNodeSetIterator(PhiNodeSet *
const Set,
size_t Start)
4027PHINode *PhiNodeSetIterator::operator*()
const {
4029 "PhiNodeSet access out of range");
4030 return Set->NodeList[CurrentIndex];
4033PhiNodeSetIterator &PhiNodeSetIterator::operator++() {
4035 "PhiNodeSet access out of range");
4037 Set->SkipRemovedElements(CurrentIndex);
4041bool PhiNodeSetIterator::operator==(
const PhiNodeSetIterator &
RHS)
const {
4042 return CurrentIndex ==
RHS.CurrentIndex;
4045bool PhiNodeSetIterator::operator!=(
const PhiNodeSetIterator &
RHS)
const {
4046 return !((*this) ==
RHS);
4052class SimplificationTracker {
4053 DenseMap<Value *, Value *> Storage;
4056 PhiNodeSet AllPhiNodes;
4058 SmallPtrSet<SelectInst *, 32> AllSelectNodes;
4063 auto SV = Storage.
find(V);
4064 if (SV == Storage.
end())
4072 void ReplacePhi(PHINode *From, PHINode *To) {
4073 Value *OldReplacement = Get(From);
4074 while (OldReplacement != From) {
4077 OldReplacement = Get(From);
4079 assert(To && Get(To) == To &&
"Replacement PHI node is already replaced.");
4082 AllPhiNodes.erase(From);
4086 PhiNodeSet &newPhiNodes() {
return AllPhiNodes; }
4088 void insertNewPhi(PHINode *PN) { AllPhiNodes.insert(PN); }
4090 void insertNewSelect(SelectInst *SI) { AllSelectNodes.
insert(SI); }
4092 unsigned countNewPhiNodes()
const {
return AllPhiNodes.size(); }
4094 unsigned countNewSelectNodes()
const {
return AllSelectNodes.
size(); }
4096 void destroyNewNodes(
Type *CommonType) {
4099 for (
auto *
I : AllPhiNodes) {
4100 I->replaceAllUsesWith(Dummy);
4101 I->eraseFromParent();
4103 AllPhiNodes.clear();
4104 for (
auto *
I : AllSelectNodes) {
4105 I->replaceAllUsesWith(Dummy);
4106 I->eraseFromParent();
4108 AllSelectNodes.clear();
4113class AddressingModeCombiner {
4114 typedef DenseMap<Value *, Value *> FoldAddrToValueMapping;
4115 typedef std::pair<PHINode *, PHINode *> PHIPair;
4122 ExtAddrMode::FieldName DifferentField = ExtAddrMode::NoField;
4125 bool AllAddrModesTrivial =
true;
4128 Type *CommonType =
nullptr;
4130 const DataLayout &
DL;
4136 Value *CommonValue =
nullptr;
4139 AddressingModeCombiner(
const DataLayout &
DL,
Value *OriginalValue)
4140 :
DL(
DL), Original(OriginalValue) {}
4142 ~AddressingModeCombiner() { eraseCommonValueIfDead(); }
4145 const ExtAddrMode &
getAddrMode()
const {
return AddrModes[0]; }
4150 bool addNewAddrMode(ExtAddrMode &NewAddrMode) {
4154 AllAddrModesTrivial = AllAddrModesTrivial && NewAddrMode.isTrivial();
4157 if (AddrModes.
empty()) {
4165 ExtAddrMode::FieldName ThisDifferentField =
4166 AddrModes[0].compare(NewAddrMode);
4167 if (DifferentField == ExtAddrMode::NoField)
4168 DifferentField = ThisDifferentField;
4169 else if (DifferentField != ThisDifferentField)
4170 DifferentField = ExtAddrMode::MultipleFields;
4173 bool CanHandle = DifferentField != ExtAddrMode::MultipleFields;
4176 CanHandle = CanHandle && DifferentField != ExtAddrMode::ScaleField;
4181 CanHandle = CanHandle && (DifferentField != ExtAddrMode::BaseOffsField ||
4186 CanHandle = CanHandle && (DifferentField != ExtAddrMode::BaseGVField ||
4187 !NewAddrMode.HasBaseReg);
4204 bool combineAddrModes() {
4206 if (AddrModes.
size() == 0)
4210 if (AddrModes.
size() == 1 || DifferentField == ExtAddrMode::NoField)
4215 if (AllAddrModesTrivial)
4218 if (!addrModeCombiningAllowed())
4224 FoldAddrToValueMapping
Map;
4225 if (!initializeMap(Map))
4228 CommonValue = findCommon(Map);
4230 AddrModes[0].SetCombinedField(DifferentField, CommonValue, AddrModes);
4231 return CommonValue !=
nullptr;
4237 void eraseCommonValueIfDead() {
4238 if (CommonValue && CommonValue->
use_empty())
4240 CommonInst->eraseFromParent();
4248 bool initializeMap(FoldAddrToValueMapping &Map) {
4251 SmallVector<Value *, 2> NullValue;
4252 Type *IntPtrTy =
DL.getIntPtrType(AddrModes[0].OriginalValue->
getType());
4253 for (
auto &AM : AddrModes) {
4254 Value *DV = AM.GetFieldAsValue(DifferentField, IntPtrTy);
4257 if (CommonType && CommonType !=
Type)
4260 Map[AM.OriginalValue] = DV;
4265 assert(CommonType &&
"At least one non-null value must be!");
4266 for (
auto *V : NullValue)
4294 Value *findCommon(FoldAddrToValueMapping &Map) {
4302 SimplificationTracker
ST;
4307 InsertPlaceholders(Map, TraverseOrder, ST);
4310 FillPlaceholders(Map, TraverseOrder, ST);
4313 ST.destroyNewNodes(CommonType);
4318 unsigned PhiNotMatchedCount = 0;
4320 ST.destroyNewNodes(CommonType);
4324 auto *
Result =
ST.Get(
Map.find(Original)->second);
4326 NumMemoryInstsPhiCreated +=
ST.countNewPhiNodes() + PhiNotMatchedCount;
4327 NumMemoryInstsSelectCreated +=
ST.countNewSelectNodes();
4334 bool MatchPhiNode(PHINode *
PHI, PHINode *Candidate,
4335 SmallSetVector<PHIPair, 8> &Matcher,
4336 PhiNodeSet &PhiNodesToMatch) {
4339 SmallPtrSet<PHINode *, 8> MatchedPHIs;
4342 SmallSet<PHIPair, 8> Visited;
4343 while (!WorkList.
empty()) {
4345 if (!Visited.
insert(Item).second)
4352 for (
auto *
B : Item.first->blocks()) {
4353 Value *FirstValue = Item.first->getIncomingValueForBlock(
B);
4354 Value *SecondValue = Item.second->getIncomingValueForBlock(
B);
4355 if (FirstValue == SecondValue)
4365 if (!FirstPhi || !SecondPhi || !PhiNodesToMatch.count(FirstPhi) ||
4370 if (Matcher.
count({FirstPhi, SecondPhi}))
4375 if (MatchedPHIs.
insert(FirstPhi).second)
4376 Matcher.
insert({FirstPhi, SecondPhi});
4378 WorkList.
push_back({FirstPhi, SecondPhi});
4387 bool MatchPhiSet(SimplificationTracker &ST,
bool AllowNewPhiNodes,
4388 unsigned &PhiNotMatchedCount) {
4392 SmallSetVector<PHIPair, 8> Matched;
4393 SmallPtrSet<PHINode *, 8> WillNotMatch;
4394 PhiNodeSet &PhiNodesToMatch =
ST.newPhiNodes();
4395 while (PhiNodesToMatch.size()) {
4396 PHINode *
PHI = *PhiNodesToMatch.begin();
4399 WillNotMatch.
clear();
4403 bool IsMatched =
false;
4404 for (
auto &
P :
PHI->getParent()->phis()) {
4406 if (PhiNodesToMatch.count(&
P))
4408 if ((IsMatched = MatchPhiNode(
PHI, &
P, Matched, PhiNodesToMatch)))
4418 for (
auto MV : Matched)
4419 ST.ReplacePhi(MV.first, MV.second);
4424 if (!AllowNewPhiNodes)
4427 PhiNotMatchedCount += WillNotMatch.
size();
4428 for (
auto *
P : WillNotMatch)
4429 PhiNodesToMatch.erase(
P);
4434 void FillPlaceholders(FoldAddrToValueMapping &Map,
4435 SmallVectorImpl<Value *> &TraverseOrder,
4436 SimplificationTracker &ST) {
4437 while (!TraverseOrder.
empty()) {
4439 assert(
Map.contains(Current) &&
"No node to fill!!!");
4445 auto *TrueValue = CurrentSelect->getTrueValue();
4446 assert(
Map.contains(TrueValue) &&
"No True Value!");
4447 Select->setTrueValue(
ST.Get(Map[TrueValue]));
4448 auto *FalseValue = CurrentSelect->getFalseValue();
4449 assert(
Map.contains(FalseValue) &&
"No False Value!");
4450 Select->setFalseValue(
ST.Get(Map[FalseValue]));
4457 assert(
Map.contains(PV) &&
"No predecessor Value!");
4458 PHI->addIncoming(
ST.Get(Map[PV]),
B);
4469 void InsertPlaceholders(FoldAddrToValueMapping &Map,
4470 SmallVectorImpl<Value *> &TraverseOrder,
4471 SimplificationTracker &ST) {
4474 "Address must be a Phi or Select node");
4477 while (!Worklist.
empty()) {
4480 if (
Map.contains(Current))
4491 CurrentSelect->getName(),
4492 CurrentSelect->getIterator(), CurrentSelect);
4496 Worklist.
push_back(CurrentSelect->getTrueValue());
4497 Worklist.
push_back(CurrentSelect->getFalseValue());
4505 ST.insertNewPhi(
PHI);
4511 bool addrModeCombiningAllowed() {
4514 switch (DifferentField) {
4517 case ExtAddrMode::BaseRegField:
4519 case ExtAddrMode::BaseGVField:
4521 case ExtAddrMode::BaseOffsField:
4523 case ExtAddrMode::ScaledRegField:
4533bool AddressingModeMatcher::matchScaledValue(
Value *ScaleReg, int64_t Scale,
4538 return matchAddr(ScaleReg,
Depth);
4549 ExtAddrMode TestAddrMode =
AddrMode;
4553 TestAddrMode.
Scale += Scale;
4567 ConstantInt *CI =
nullptr;
4568 Value *AddLHS =
nullptr;
4572 TestAddrMode.InBounds =
false;
4589 auto GetConstantStep =
4590 [
this](
const Value *
V) -> std::optional<std::pair<Instruction *, APInt>> {
4593 return std::nullopt;
4596 return std::nullopt;
4604 if (OIVInc->hasNoSignedWrap() || OIVInc->hasNoUnsignedWrap())
4605 return std::nullopt;
4607 return std::make_pair(IVInc->first, ConstantStep->getValue());
4608 return std::nullopt;
4623 if (
auto IVStep = GetConstantStep(ScaleReg)) {
4630 APInt Step = IVStep->second;
4632 if (
Offset.isSignedIntN(64)) {
4633 TestAddrMode.InBounds =
false;
4635 TestAddrMode.BaseOffs -=
Offset.getLimitedValue();
4640 getDTFn().
dominates(IVInc, MemoryInst)) {
4660 switch (
I->getOpcode()) {
4661 case Instruction::BitCast:
4662 case Instruction::AddrSpaceCast:
4664 if (
I->getType() ==
I->getOperand(0)->getType())
4666 return I->getType()->isIntOrPtrTy();
4667 case Instruction::PtrToInt:
4670 case Instruction::IntToPtr:
4673 case Instruction::Add:
4675 case Instruction::Mul:
4676 case Instruction::Shl:
4679 case Instruction::GetElementPtr:
4707class TypePromotionHelper {
4710 static void addPromotedInst(InstrToOrigTy &PromotedInsts,
4711 Instruction *ExtOpnd,
bool IsSExt) {
4712 ExtType ExtTy = IsSExt ? SignExtension : ZeroExtension;
4713 auto [It,
Inserted] = PromotedInsts.try_emplace(ExtOpnd);
4717 if (It->second.getInt() == ExtTy)
4723 ExtTy = BothExtension;
4725 It->second = TypeIsSExt(ExtOpnd->
getType(), ExtTy);
4732 static const Type *getOrigType(
const InstrToOrigTy &PromotedInsts,
4733 Instruction *Opnd,
bool IsSExt) {
4734 ExtType ExtTy = IsSExt ? SignExtension : ZeroExtension;
4735 InstrToOrigTy::const_iterator It = PromotedInsts.find(Opnd);
4736 if (It != PromotedInsts.end() && It->second.getInt() == ExtTy)
4737 return It->second.getPointer();
4752 static bool canGetThrough(
const Instruction *Inst,
Type *ConsideredExtType,
4753 const InstrToOrigTy &PromotedInsts,
bool IsSExt);
4757 static bool shouldExtOperand(
const Instruction *Inst,
int OpIdx) {
4770 static Value *promoteOperandForTruncAndAnyExt(
4771 Instruction *Ext, TypePromotionTransaction &TPT,
4772 InstrToOrigTy &PromotedInsts,
unsigned &CreatedInstsCost,
4773 SmallVectorImpl<Instruction *> *Exts,
4774 SmallVectorImpl<Instruction *> *Truncs,
const TargetLowering &TLI);
4785 static Value *promoteOperandForOther(Instruction *Ext,
4786 TypePromotionTransaction &TPT,
4787 InstrToOrigTy &PromotedInsts,
4788 unsigned &CreatedInstsCost,
4789 SmallVectorImpl<Instruction *> *Exts,
4790 SmallVectorImpl<Instruction *> *Truncs,
4791 const TargetLowering &TLI,
bool IsSExt);
4794 static Value *signExtendOperandForOther(
4795 Instruction *Ext, TypePromotionTransaction &TPT,
4796 InstrToOrigTy &PromotedInsts,
unsigned &CreatedInstsCost,
4797 SmallVectorImpl<Instruction *> *Exts,
4798 SmallVectorImpl<Instruction *> *Truncs,
const TargetLowering &TLI) {
4799 return promoteOperandForOther(Ext, TPT, PromotedInsts, CreatedInstsCost,
4800 Exts, Truncs, TLI,
true);
4804 static Value *zeroExtendOperandForOther(
4805 Instruction *Ext, TypePromotionTransaction &TPT,
4806 InstrToOrigTy &PromotedInsts,
unsigned &CreatedInstsCost,
4807 SmallVectorImpl<Instruction *> *Exts,
4808 SmallVectorImpl<Instruction *> *Truncs,
const TargetLowering &TLI) {
4809 return promoteOperandForOther(Ext, TPT, PromotedInsts, CreatedInstsCost,
4810 Exts, Truncs, TLI,
false);
4815 using Action =
Value *(*)(Instruction *Ext, TypePromotionTransaction &TPT,
4816 InstrToOrigTy &PromotedInsts,
4817 unsigned &CreatedInstsCost,
4818 SmallVectorImpl<Instruction *> *Exts,
4819 SmallVectorImpl<Instruction *> *Truncs,
4820 const TargetLowering &TLI);
4831 static Action getAction(Instruction *Ext,
const SetOfInstrs &InsertedInsts,
4832 const TargetLowering &TLI,
4833 const InstrToOrigTy &PromotedInsts);
4838bool TypePromotionHelper::canGetThrough(
const Instruction *Inst,
4839 Type *ConsideredExtType,
4840 const InstrToOrigTy &PromotedInsts,
4860 ((!IsSExt && BinOp->hasNoUnsignedWrap()) ||
4861 (IsSExt && BinOp->hasNoSignedWrap())))
4865 if ((Inst->
getOpcode() == Instruction::And ||
4870 if (Inst->
getOpcode() == Instruction::Xor) {
4873 if (!Cst->getValue().isAllOnes())
4882 if (Inst->
getOpcode() == Instruction::LShr && !IsSExt)
4892 if (ExtInst->hasOneUse()) {
4894 if (AndInst && AndInst->getOpcode() == Instruction::And) {
4927 const Type *OpndType = getOrigType(PromotedInsts, Opnd, IsSExt);
4940TypePromotionHelper::Action TypePromotionHelper::getAction(
4941 Instruction *Ext,
const SetOfInstrs &InsertedInsts,
4942 const TargetLowering &TLI,
const InstrToOrigTy &PromotedInsts) {
4944 "Unexpected instruction type");
4951 if (!ExtOpnd || !canGetThrough(ExtOpnd, ExtTy, PromotedInsts, IsSExt))
4964 return promoteOperandForTruncAndAnyExt;
4970 return IsSExt ? signExtendOperandForOther : zeroExtendOperandForOther;
4973Value *TypePromotionHelper::promoteOperandForTruncAndAnyExt(
4974 Instruction *SExt, TypePromotionTransaction &TPT,
4975 InstrToOrigTy &PromotedInsts,
unsigned &CreatedInstsCost,
4976 SmallVectorImpl<Instruction *> *Exts,
4977 SmallVectorImpl<Instruction *> *Truncs,
const TargetLowering &TLI) {
4981 Value *ExtVal = SExt;
4982 bool HasMergedNonFreeExt =
false;
4986 HasMergedNonFreeExt = !TLI.
isExtFree(SExtOpnd);
4989 TPT.replaceAllUsesWith(SExt, ZExt);
4990 TPT.eraseInstruction(SExt);
4995 TPT.setOperand(SExt, 0, SExtOpnd->
getOperand(0));
4997 CreatedInstsCost = 0;
5001 TPT.eraseInstruction(SExtOpnd);
5009 CreatedInstsCost = !TLI.
isExtFree(ExtInst) && !HasMergedNonFreeExt;
5017 TPT.eraseInstruction(ExtInst, NextVal);
5021Value *TypePromotionHelper::promoteOperandForOther(
5022 Instruction *Ext, TypePromotionTransaction &TPT,
5023 InstrToOrigTy &PromotedInsts,
unsigned &CreatedInstsCost,
5024 SmallVectorImpl<Instruction *> *Exts,
5025 SmallVectorImpl<Instruction *> *Truncs,
const TargetLowering &TLI,
5030 CreatedInstsCost = 0;
5036 Value *Trunc = TPT.createTrunc(Ext, ExtOpnd->
getType());
5039 ITrunc->moveAfter(ExtOpnd);
5044 TPT.replaceAllUsesWith(ExtOpnd, Trunc);
5047 TPT.setOperand(Ext, 0, ExtOpnd);
5057 addPromotedInst(PromotedInsts, ExtOpnd, IsSExt);
5059 TPT.mutateType(ExtOpnd, Ext->
getType());
5061 TPT.replaceAllUsesWith(Ext, ExtOpnd);
5068 !shouldExtOperand(ExtOpnd,
OpIdx)) {
5077 APInt CstVal = IsSExt ? Cst->getValue().sext(
BitWidth)
5079 TPT.setOperand(ExtOpnd,
OpIdx, ConstantInt::get(Ext->
getType(), CstVal));
5090 Value *ValForExtOpnd = IsSExt
5091 ? TPT.createSExt(ExtOpnd, Opnd, Ext->
getType())
5092 : TPT.createZExt(ExtOpnd, Opnd, Ext->
getType());
5093 TPT.setOperand(ExtOpnd,
OpIdx, ValForExtOpnd);
5095 if (!InstForExtOpnd)
5101 CreatedInstsCost += !TLI.
isExtFree(InstForExtOpnd);
5104 TPT.eraseInstruction(Ext);
5116bool AddressingModeMatcher::isPromotionProfitable(
5117 unsigned NewCost,
unsigned OldCost,
Value *PromotedOperand)
const {
5118 LLVM_DEBUG(
dbgs() <<
"OldCost: " << OldCost <<
"\tNewCost: " << NewCost
5123 if (NewCost > OldCost)
5125 if (NewCost < OldCost)
5144bool AddressingModeMatcher::matchOperationAddr(User *AddrInst,
unsigned Opcode,
5156 case Instruction::PtrToInt:
5159 case Instruction::IntToPtr: {
5167 case Instruction::BitCast:
5177 case Instruction::AddrSpaceCast: {
5185 case Instruction::Add: {
5188 ExtAddrMode BackupAddrMode =
AddrMode;
5189 unsigned OldSize = AddrModeInsts.
size();
5194 TypePromotionTransaction::ConstRestorationPt LastKnownGood =
5195 TPT.getRestorationPoint();
5199 int First = 0, Second = 1;
5210 AddrModeInsts.
resize(OldSize);
5211 TPT.rollback(LastKnownGood);
5221 AddrModeInsts.
resize(OldSize);
5222 TPT.rollback(LastKnownGood);
5228 case Instruction::Mul:
5229 case Instruction::Shl: {
5233 if (!
RHS ||
RHS->getBitWidth() > 64)
5235 int64_t Scale = Opcode == Instruction::Shl
5236 ? 1LL <<
RHS->getLimitedValue(
RHS->getBitWidth() - 1)
5237 :
RHS->getSExtValue();
5241 case Instruction::GetElementPtr: {
5244 int VariableOperand = -1;
5245 unsigned VariableScale = 0;
5247 int64_t ConstantOffset = 0;
5249 for (
unsigned i = 1, e = AddrInst->
getNumOperands(); i != e; ++i, ++GTI) {
5251 const StructLayout *SL =
DL.getStructLayout(STy);
5262 if (ConstantInt *CI =
5264 const APInt &CVal = CI->
getValue();
5271 if (VariableOperand != -1)
5275 VariableOperand = i;
5276 VariableScale = TypeSize;
5283 if (VariableOperand == -1) {
5284 AddrMode.BaseOffs += ConstantOffset;
5290 AddrMode.BaseOffs -= ConstantOffset;
5294 ConstantOffset > 0) {
5307 BasicBlock *Parent = BaseI ? BaseI->getParent()
5308 : &
GEP->getFunction()->getEntryBlock();
5310 LargeOffsetGEP = std::make_pair(
GEP, ConstantOffset);
5318 ExtAddrMode BackupAddrMode =
AddrMode;
5319 unsigned OldSize = AddrModeInsts.
size();
5322 AddrMode.BaseOffs += ConstantOffset;
5331 AddrModeInsts.
resize(OldSize);
5339 if (!matchScaledValue(AddrInst->
getOperand(VariableOperand), VariableScale,
5344 AddrModeInsts.
resize(OldSize);
5349 AddrMode.BaseOffs += ConstantOffset;
5350 if (!matchScaledValue(AddrInst->
getOperand(VariableOperand),
5351 VariableScale,
Depth)) {
5354 AddrModeInsts.
resize(OldSize);
5361 case Instruction::SExt:
5362 case Instruction::ZExt: {
5369 TypePromotionHelper::Action TPH =
5370 TypePromotionHelper::getAction(Ext, InsertedInsts, TLI, PromotedInsts);
5374 TypePromotionTransaction::ConstRestorationPt LastKnownGood =
5375 TPT.getRestorationPoint();
5376 unsigned CreatedInstsCost = 0;
5378 Value *PromotedOperand =
5379 TPH(Ext, TPT, PromotedInsts, CreatedInstsCost,
nullptr,
nullptr, TLI);
5394 assert(PromotedOperand &&
5395 "TypePromotionHelper should have filtered out those cases");
5397 ExtAddrMode BackupAddrMode =
AddrMode;
5398 unsigned OldSize = AddrModeInsts.
size();
5400 if (!matchAddr(PromotedOperand,
Depth) ||
5405 !isPromotionProfitable(CreatedInstsCost,
5406 ExtCost + (AddrModeInsts.
size() - OldSize),
5409 AddrModeInsts.
resize(OldSize);
5410 LLVM_DEBUG(
dbgs() <<
"Sign extension does not pay off: rollback\n");
5411 TPT.rollback(LastKnownGood);
5416 AddrMode.replaceWith(Ext, PromotedOperand);
5419 case Instruction::Call:
5421 if (
II->getIntrinsicID() == Intrinsic::threadlocal_address) {
5437bool AddressingModeMatcher::matchAddr(
Value *Addr,
unsigned Depth) {
5440 TypePromotionTransaction::ConstRestorationPt LastKnownGood =
5441 TPT.getRestorationPoint();
5465 ExtAddrMode BackupAddrMode =
AddrMode;
5466 unsigned OldSize = AddrModeInsts.
size();
5469 bool MovedAway =
false;
5470 if (matchOperationAddr(
I,
I->getOpcode(),
Depth, &MovedAway)) {
5478 if (
I->hasOneUse() ||
5479 isProfitableToFoldIntoAddressingMode(
I, BackupAddrMode,
AddrMode)) {
5486 AddrModeInsts.
resize(OldSize);
5487 TPT.rollback(LastKnownGood);
5490 if (matchOperationAddr(CE,
CE->getOpcode(),
Depth))
5492 TPT.rollback(LastKnownGood);
5519 TPT.rollback(LastKnownGood);
5538 if (OpInfo.CallOperandVal == OpVal &&
5540 !OpInfo.isIndirect))
5556 if (!ConsideredInsts.
insert(
I).second)
5564 for (
Use &U :
I->uses()) {
5572 MemoryUses.push_back({&U, LI->getType()});
5579 MemoryUses.push_back({&U,
SI->getValueOperand()->getType()});
5586 MemoryUses.push_back({&U, RMW->getValOperand()->getType()});
5593 MemoryUses.push_back({&U, CmpX->getCompareOperand()->getType()});
5603 if (!
find(PtrOps, U.get()))
5606 MemoryUses.push_back({&U, AccessTy});
5611 if (CI->hasFnAttr(Attribute::Cold)) {
5629 PSI, BFI, SeenInsts))
5640 unsigned SeenInsts = 0;
5643 PSI, BFI, SeenInsts);
5651bool AddressingModeMatcher::valueAlreadyLiveAtInst(
Value *Val,
5653 Value *KnownLive2) {
5655 if (Val ==
nullptr || Val == KnownLive1 || Val == KnownLive2)
5696bool AddressingModeMatcher::isProfitableToFoldIntoAddressingMode(
5697 Instruction *
I, ExtAddrMode &AMBefore, ExtAddrMode &AMAfter) {
5698 if (IgnoreProfitability)
5716 if (valueAlreadyLiveAtInst(ScaledReg, AMBefore.
BaseReg, AMBefore.
ScaledReg))
5717 ScaledReg =
nullptr;
5721 if (!BaseReg && !ScaledReg)
5742 for (
const std::pair<Use *, Type *> &Pair : MemoryUses) {
5745 Type *AddressAccessTy = Pair.second;
5746 unsigned AS =
Address->getType()->getPointerAddressSpace();
5752 std::pair<AssertingVH<GetElementPtrInst>, int64_t> LargeOffsetGEP(
nullptr,
5754 TypePromotionTransaction::ConstRestorationPt LastKnownGood =
5755 TPT.getRestorationPoint();
5756 AddressingModeMatcher Matcher(MatchedAddrModeInsts, TLI,
TRI, LI, getDTFn,
5757 AddressAccessTy, AS, UserI, Result,
5758 InsertedInsts, PromotedInsts, TPT,
5759 LargeOffsetGEP, OptSize, PSI, BFI);
5760 Matcher.IgnoreProfitability =
true;
5768 TPT.rollback(LastKnownGood);
5774 MatchedAddrModeInsts.
clear();
5784 return I->getParent() != BB;
5800 return std::next(AddrInst->getIterator());
5811 Earliest = UserInst;
5836bool CodeGenPrepare::optimizeMemoryInst(Instruction *MemoryInst,
Value *Addr,
5837 Type *AccessTy,
unsigned AddrSpace) {
5842 SmallVector<Value *, 8> worklist;
5843 SmallPtrSet<Value *, 16> Visited;
5849 bool PhiOrSelectSeen =
false;
5850 SmallVector<Instruction *, 16> AddrModeInsts;
5851 AddressingModeCombiner AddrModes(*
DL, Addr);
5852 TypePromotionTransaction TPT(RemovedInsts);
5853 TypePromotionTransaction::ConstRestorationPt LastKnownGood =
5854 TPT.getRestorationPoint();
5855 while (!worklist.
empty()) {
5867 if (!Visited.
insert(V).second)
5873 PhiOrSelectSeen =
true;
5880 PhiOrSelectSeen =
true;
5887 AddrModeInsts.
clear();
5888 std::pair<AssertingVH<GetElementPtrInst>, int64_t> LargeOffsetGEP(
nullptr,
5893 auto getDTFn = [MemoryInst,
this]() ->
const DominatorTree & {
5895 return this->getDT(*
F);
5897 ExtAddrMode NewAddrMode = AddressingModeMatcher::Match(
5898 V, AccessTy, AddrSpace, MemoryInst, AddrModeInsts, *TLI, *LI, getDTFn,
5899 *
TRI, InsertedInsts, PromotedInsts, TPT, LargeOffsetGEP, OptSize, PSI,
5902 GetElementPtrInst *
GEP = LargeOffsetGEP.first;
5907 LargeOffsetGEPMap[
GEP->getPointerOperand()].push_back(LargeOffsetGEP);
5908 LargeOffsetGEPID.
insert(std::make_pair(
GEP, LargeOffsetGEPID.
size()));
5911 NewAddrMode.OriginalValue =
V;
5912 if (!AddrModes.addNewAddrMode(NewAddrMode))
5919 if (!AddrModes.combineAddrModes()) {
5920 TPT.rollback(LastKnownGood);
5926 ExtAddrMode
AddrMode = AddrModes.getAddrMode();
5932 if (!PhiOrSelectSeen &&
none_of(AddrModeInsts, [&](
Value *V) {
5946 WeakTrackingVH SunkAddrVH = SunkAddrs[Addr];
5968 <<
" for " << *MemoryInst <<
"\n");
5972 !
DL->isNonIntegralPointerType(Addr->
getType())) {
5978 SunkAddr = Builder.CreatePtrToInt(SunkAddr, IntPtrTy,
"sunkaddr");
5980 Builder.CreateIntToPtr(SunkAddr, Addr->
getType(),
"sunkaddr");
5982 SunkAddr = Builder.CreatePointerCast(SunkAddr, Addr->
getType());
5989 <<
" for " << *MemoryInst <<
"\n");
5990 Value *ResultPtr =
nullptr, *ResultIndex =
nullptr;
6001 if (ResultPtr ||
AddrMode.Scale != 1)
6022 GlobalValue *BaseGV =
AddrMode.BaseGV;
6023 if (BaseGV !=
nullptr) {
6028 ResultPtr = Builder.CreateThreadLocalAddress(BaseGV);
6037 if (!
DL->isNonIntegralPointerType(Addr->
getType())) {
6038 if (!ResultPtr &&
AddrMode.BaseReg) {
6042 }
else if (!ResultPtr &&
AddrMode.Scale == 1) {
6043 ResultPtr = Builder.CreateIntToPtr(
AddrMode.ScaledReg, Addr->
getType(),
6052 }
else if (!ResultPtr) {
6065 if (
V->getType() != IntPtrTy)
6066 V = Builder.CreateIntCast(V, IntPtrTy,
true,
"sunkaddr");
6074 if (
V->getType() == IntPtrTy) {
6079 "We can't transform if ScaledReg is too narrow");
6080 V = Builder.CreateTrunc(V, IntPtrTy,
"sunkaddr");
6084 V = Builder.CreateMul(
6087 ResultIndex = Builder.CreateAdd(ResultIndex, V,
"sunkaddr");
6098 if (ResultPtr->
getType() != I8PtrTy)
6099 ResultPtr = Builder.CreatePointerCast(ResultPtr, I8PtrTy);
6100 ResultPtr = Builder.CreatePtrAdd(ResultPtr, ResultIndex,
"sunkaddr",
6113 if (PtrInst && PtrInst->getParent() != MemoryInst->
getParent())
6115 SunkAddr = ResultPtr;
6117 if (ResultPtr->
getType() != I8PtrTy)
6118 ResultPtr = Builder.CreatePointerCast(ResultPtr, I8PtrTy);
6119 SunkAddr = Builder.CreatePtrAdd(ResultPtr, ResultIndex,
"sunkaddr",
6126 !
DL->isNonIntegralPointerType(Addr->
getType())) {
6132 SunkAddr = Builder.CreatePtrToInt(SunkAddr, IntPtrTy,
"sunkaddr");
6134 Builder.CreateIntToPtr(SunkAddr, Addr->
getType(),
"sunkaddr");
6136 SunkAddr = Builder.CreatePointerCast(SunkAddr, Addr->
getType());
6146 if (
DL->isNonIntegralPointerType(Addr->
getType()) ||
6147 (BasePtrTy &&
DL->isNonIntegralPointerType(BasePtrTy)) ||
6148 (ScalePtrTy &&
DL->isNonIntegralPointerType(ScalePtrTy)) ||
6150 DL->isNonIntegralPointerType(
AddrMode.BaseGV->getType())))
6154 <<
" for " << *MemoryInst <<
"\n");
6165 if (
V->getType()->isPointerTy())
6166 V = Builder.CreatePtrToInt(V, IntPtrTy,
"sunkaddr");
6167 if (
V->getType() != IntPtrTy)
6168 V = Builder.CreateIntCast(V, IntPtrTy,
true,
"sunkaddr");
6175 if (
V->getType() == IntPtrTy) {
6177 }
else if (
V->getType()->isPointerTy()) {
6178 V = Builder.CreatePtrToInt(V, IntPtrTy,
"sunkaddr");
6181 V = Builder.CreateTrunc(V, IntPtrTy,
"sunkaddr");
6190 I->eraseFromParent();
6194 V = Builder.CreateMul(
6197 Result = Builder.CreateAdd(Result, V,
"sunkaddr");
6203 GlobalValue *BaseGV =
AddrMode.BaseGV;
6204 if (BaseGV !=
nullptr) {
6207 BaseGVPtr = Builder.CreateThreadLocalAddress(BaseGV);
6211 Value *
V = Builder.CreatePtrToInt(BaseGVPtr, IntPtrTy,
"sunkaddr");
6213 Result = Builder.CreateAdd(Result, V,
"sunkaddr");
6222 Result = Builder.CreateAdd(Result, V,
"sunkaddr");
6230 SunkAddr = Builder.CreateIntToPtr(Result, Addr->
getType(),
"sunkaddr");
6236 SunkAddrs[Addr] = WeakTrackingVH(SunkAddr);
6241 resetIteratorIfInvalidatedWhileCalling(CurInstIterator->getParent(), [&]() {
6242 RecursivelyDeleteTriviallyDeadInstructions(
6243 Repl, TLInfo, nullptr,
6244 [&](Value *V) { removeAllAssertingVHReferences(V); });
6268bool CodeGenPrepare::optimizeGatherScatterInst(Instruction *MemoryInst,
6274 if (!
GEP->hasIndices())
6282 SmallVector<Value *, 2>
Ops(
GEP->operands());
6284 bool RewriteGEP =
false;
6293 unsigned FinalIndex =
Ops.size() - 1;
6298 for (
unsigned i = 1; i < FinalIndex; ++i) {
6303 C =
C->getSplatValue();
6305 if (!CI || !CI->
isZero())
6312 if (
Ops[FinalIndex]->
getType()->isVectorTy()) {
6316 if (!
C || !
C->isZero()) {
6317 Ops[FinalIndex] =
V;
6325 if (!RewriteGEP &&
Ops.size() == 2)
6332 Type *SourceTy =
GEP->getSourceElementType();
6333 Type *ScalarIndexTy =
DL->getIndexType(
Ops[0]->
getType()->getScalarType());
6337 if (!
Ops[FinalIndex]->
getType()->isVectorTy()) {
6338 NewAddr = Builder.CreateGEP(SourceTy,
Ops[0],
ArrayRef(
Ops).drop_front());
6339 auto *IndexTy = VectorType::get(ScalarIndexTy, NumElts);
6349 if (
Ops.size() != 2) {
6359 NewAddr = Builder.CreateGEP(SourceTy,
Base, Index);
6373 Type *ScalarIndexTy =
DL->getIndexType(
V->getType()->getScalarType());
6374 auto *IndexTy = VectorType::get(ScalarIndexTy, NumElts);
6377 Intrinsic::masked_gather) {
6381 Intrinsic::masked_scatter);
6396 Ptr, TLInfo,
nullptr,
6397 [&](
Value *V) { removeAllAssertingVHReferences(V); });
6408 if (
I->hasNUsesOrMore(3))
6411 for (
User *U :
I->users()) {
6413 if (!Extract || Extract->getNumIndices() != 1)
6416 unsigned Index = Extract->getIndices()[0];
6418 MulExtract = Extract;
6419 else if (Index == 1)
6420 OverflowExtract = Extract;
6447bool CodeGenPrepare::optimizeMulWithOverflow(Instruction *
I,
bool IsSigned,
6448 ModifyDT &ModifiedDT) {
6455 ExtractValueInst *MulExtract =
nullptr, *OverflowExtract =
nullptr;
6460 InsertedInsts.insert(
I);
6470 I->getParent()->splitBasicBlock(
I,
"",
true);
6471 OverflowEntryBB->
takeName(
I->getParent());
6477 NoOverflowBB->
moveAfter(OverflowEntryBB);
6485 Value *LoLHS = Builder.CreateTrunc(
LHS, LegalTy,
"lo.lhs");
6486 Value *HiLHS = Builder.CreateLShr(
LHS, VTHalfBitWidth,
"lhs.lsr");
6487 HiLHS = Builder.CreateTrunc(HiLHS, LegalTy,
"hi.lhs");
6490 Value *LoRHS = Builder.CreateTrunc(
RHS, LegalTy,
"lo.rhs");
6491 Value *HiRHS = Builder.CreateLShr(
RHS, VTHalfBitWidth,
"rhs.lsr");
6492 HiRHS = Builder.CreateTrunc(HiRHS, LegalTy,
"hi.rhs");
6494 Value *IsAnyBitTrue;
6497 Builder.CreateAShr(LoLHS, VTHalfBitWidth - 1,
"sign.lo.lhs");
6499 Builder.CreateAShr(LoRHS, VTHalfBitWidth - 1,
"sign.lo.rhs");
6500 Value *XorLHS = Builder.CreateXor(HiLHS, SignLoLHS);
6501 Value *XorRHS = Builder.CreateXor(HiRHS, SignLoRHS);
6502 Value *
Or = Builder.CreateOr(XorLHS, XorRHS,
"or.lhs.rhs");
6503 IsAnyBitTrue = Builder.CreateCmp(ICmpInst::ICMP_NE,
Or,
6504 ConstantInt::getNullValue(
Or->getType()));
6506 Value *CmpLHS = Builder.CreateCmp(ICmpInst::ICMP_NE, HiLHS,
6507 ConstantInt::getNullValue(LegalTy));
6508 Value *CmpRHS = Builder.CreateCmp(ICmpInst::ICMP_NE, HiRHS,
6509 ConstantInt::getNullValue(LegalTy));
6510 IsAnyBitTrue = Builder.CreateOr(CmpLHS, CmpRHS,
"or.lhs.rhs");
6512 Builder.CreateCondBr(IsAnyBitTrue, OverflowBB, NoOverflowBB);
6515 Builder.SetInsertPoint(NoOverflowBB);
6516 Value *ExtLoLHS, *ExtLoRHS;
6518 ExtLoLHS = Builder.CreateSExt(LoLHS, Ty,
"lo.lhs.ext");
6519 ExtLoRHS = Builder.CreateSExt(LoRHS, Ty,
"lo.rhs.ext");
6521 ExtLoLHS = Builder.CreateZExt(LoLHS, Ty,
"lo.lhs.ext");
6522 ExtLoRHS = Builder.CreateZExt(LoRHS, Ty,
"lo.rhs.ext");
6525 Value *
Mul = Builder.CreateMul(ExtLoLHS, ExtLoRHS,
"mul.overflow.no");
6530 OverflowResBB->
setName(
"overflow.res");
6533 Builder.CreateBr(OverflowResBB);
6541 PHINode *OverflowResPHI = Builder.CreatePHI(Ty, 2),
6543 Builder.CreatePHI(IntegerType::getInt1Ty(
I->getContext()), 2);
6555 if (OverflowExtract) {
6556 OverflowExtract->replaceAllUsesWith(OverflowFlagPHI);
6557 OverflowExtract->eraseFromParent();
6562 I->removeFromParent();
6564 I->insertInto(OverflowBB, OverflowBB->
end());
6565 Builder.SetInsertPoint(OverflowBB, OverflowBB->
end());
6567 Value *OverflowFlag = Builder.CreateExtractValue(
I, {1},
"overflow.flag");
6568 Builder.CreateBr(OverflowResBB);
6572 OverflowFlagPHI->addIncoming(OverflowFlag, OverflowBB);
6574 ModifiedDT = ModifyDT::ModifyBBDT;
6580bool CodeGenPrepare::optimizeInlineAsmInst(CallInst *CS) {
6581 bool MadeChange =
false;
6583 const TargetRegisterInfo *
TRI =
6588 for (TargetLowering::AsmOperandInfo &OpInfo : TargetConstraints) {
6594 OpInfo.isIndirect) {
6596 MadeChange |= optimizeMemoryInst(CS, OpVal, OpVal->
getType(), ~0u);
6659bool CodeGenPrepare::tryToPromoteExts(
6660 TypePromotionTransaction &TPT,
const SmallVectorImpl<Instruction *> &Exts,
6661 SmallVectorImpl<Instruction *> &ProfitablyMovedExts,
6662 unsigned CreatedInstsCost) {
6663 bool Promoted =
false;
6666 for (
auto *
I : Exts) {
6681 TypePromotionHelper::Action TPH =
6682 TypePromotionHelper::getAction(
I, InsertedInsts, *TLI, PromotedInsts);
6691 TypePromotionTransaction::ConstRestorationPt LastKnownGood =
6692 TPT.getRestorationPoint();
6693 SmallVector<Instruction *, 4> NewExts;
6694 unsigned NewCreatedInstsCost = 0;
6697 Value *PromotedVal = TPH(
I, TPT, PromotedInsts, NewCreatedInstsCost,
6698 &NewExts,
nullptr, *TLI);
6700 "TypePromotionHelper should have filtered out those cases");
6710 long long TotalCreatedInstsCost = CreatedInstsCost + NewCreatedInstsCost;
6713 TotalCreatedInstsCost =
6714 std::max((
long long)0, (TotalCreatedInstsCost - ExtCost));
6716 (TotalCreatedInstsCost > 1 ||
6718 (ExtCost == 0 && NewExts.
size() > 1))) {
6722 TPT.rollback(LastKnownGood);
6727 SmallVector<Instruction *, 2> NewlyMovedExts;
6728 (void)tryToPromoteExts(TPT, NewExts, NewlyMovedExts, TotalCreatedInstsCost);
6729 bool NewPromoted =
false;
6730 for (
auto *ExtInst : NewlyMovedExts) {
6740 ProfitablyMovedExts.
push_back(MovedExt);
6747 TPT.rollback(LastKnownGood);
6758bool CodeGenPrepare::mergeSExts(Function &
F) {
6760 for (
auto &Entry : ValToSExtendedUses) {
6761 SExts &Insts =
Entry.second;
6763 for (Instruction *Inst : Insts) {
6767 bool inserted =
false;
6768 for (
auto &Pt : CurPts) {
6771 RemovedInsts.insert(Pt);
6772 Pt->removeFromParent();
6783 RemovedInsts.insert(Inst);
6790 CurPts.push_back(Inst);
6832bool CodeGenPrepare::splitLargeGEPOffsets() {
6834 for (
auto &Entry : LargeOffsetGEPMap) {
6836 SmallVectorImpl<std::pair<AssertingVH<GetElementPtrInst>, int64_t>>
6837 &LargeOffsetGEPs =
Entry.second;
6838 auto compareGEPOffset =
6839 [&](
const std::pair<GetElementPtrInst *, int64_t> &
LHS,
6840 const std::pair<GetElementPtrInst *, int64_t> &
RHS) {
6841 if (
LHS.first ==
RHS.first)
6843 if (
LHS.second !=
RHS.second)
6844 return LHS.second <
RHS.second;
6845 return LargeOffsetGEPID[
LHS.first] < LargeOffsetGEPID[
RHS.first];
6848 llvm::sort(LargeOffsetGEPs, compareGEPOffset);
6851 if (LargeOffsetGEPs.
front().second == LargeOffsetGEPs.
back().second)
6853 GetElementPtrInst *BaseGEP = LargeOffsetGEPs.
begin()->first;
6854 int64_t BaseOffset = LargeOffsetGEPs.
begin()->second;
6855 Value *NewBaseGEP =
nullptr;
6857 auto createNewBase = [&](int64_t BaseOffset,
Value *OldBase,
6858 GetElementPtrInst *
GEP) {
6859 LLVMContext &Ctx =
GEP->getContext();
6860 Type *PtrIdxTy =
DL->getIndexType(
GEP->getType());
6862 PointerType::get(Ctx,
GEP->getType()->getPointerAddressSpace());
6874 SplitEdge(NewBaseInsertBB, Invoke->getNormalDest(), DT.get(), LI);
6877 NewBaseInsertPt = std::next(BaseI->getIterator());
6884 IRBuilder<> NewBaseBuilder(NewBaseInsertBB, NewBaseInsertPt);
6890 NewBaseGEP = OldBase;
6891 if (NewBaseGEP->
getType() != I8PtrTy)
6892 NewBaseGEP = NewBaseBuilder.CreatePointerCast(NewBaseGEP, I8PtrTy);
6894 NewBaseBuilder.CreatePtrAdd(NewBaseGEP, BaseIndex,
"splitgep");
6895 NewGEPBases.
insert(NewBaseGEP);
6901 LargeOffsetGEPs.
front().second, LargeOffsetGEPs.
back().second)) {
6902 BaseOffset = PreferBase;
6905 createNewBase(BaseOffset, OldBase, BaseGEP);
6908 auto *LargeOffsetGEP = LargeOffsetGEPs.
begin();
6909 while (LargeOffsetGEP != LargeOffsetGEPs.
end()) {
6910 GetElementPtrInst *
GEP = LargeOffsetGEP->first;
6911 int64_t
Offset = LargeOffsetGEP->second;
6912 if (
Offset != BaseOffset) {
6919 GEP->getResultElementType(),
6920 GEP->getAddressSpace())) {
6926 NewBaseGEP =
nullptr;
6931 Type *PtrIdxTy =
DL->getIndexType(
GEP->getType());
6936 createNewBase(BaseOffset, OldBase,
GEP);
6940 Value *NewGEP = NewBaseGEP;
6941 if (
Offset != BaseOffset) {
6944 NewGEP = Builder.CreatePtrAdd(NewBaseGEP, Index);
6948 LargeOffsetGEP = LargeOffsetGEPs.
erase(LargeOffsetGEP);
6949 GEP->eraseFromParent();
6956bool CodeGenPrepare::optimizePhiType(
6957 PHINode *
I, SmallPtrSetImpl<PHINode *> &Visited,
6958 SmallPtrSetImpl<Instruction *> &DeletedInstrs) {
6963 Type *PhiTy =
I->getType();
6964 Type *ConvertTy =
nullptr;
6966 (!
I->getType()->isIntegerTy() && !
I->getType()->isFloatingPointTy()))
6969 SmallVector<Instruction *, 4> Worklist;
6971 SmallPtrSet<PHINode *, 4> PhiNodes;
6972 SmallPtrSet<ConstantData *, 4>
Constants;
6975 SmallPtrSet<Instruction *, 4> Defs;
6976 SmallPtrSet<Instruction *, 4>
Uses;
6982 bool AnyAnchored =
false;
6984 while (!Worklist.
empty()) {
6989 for (
Value *V :
Phi->incoming_values()) {
6991 if (!PhiNodes.
count(OpPhi)) {
6992 if (!Visited.
insert(OpPhi).second)
6998 if (!OpLoad->isSimple())
7000 if (Defs.
insert(OpLoad).second)
7003 if (Defs.
insert(OpEx).second)
7007 ConvertTy = OpBC->getOperand(0)->getType();
7008 if (OpBC->getOperand(0)->getType() != ConvertTy)
7010 if (Defs.
insert(OpBC).second) {
7023 for (User *V :
II->users()) {
7025 if (!PhiNodes.
count(OpPhi)) {
7026 if (Visited.
count(OpPhi))
7033 if (!OpStore->isSimple() || OpStore->getOperand(0) !=
II)
7035 Uses.insert(OpStore);
7038 ConvertTy = OpBC->getType();
7039 if (OpBC->getType() != ConvertTy)
7043 any_of(OpBC->users(), [](User *U) { return !isa<StoreInst>(U); });
7050 if (!ConvertTy || !AnyAnchored ||
7054 LLVM_DEBUG(
dbgs() <<
"Converting " << *
I <<
"\n and connected nodes to "
7055 << *ConvertTy <<
"\n");
7060 for (ConstantData *
C : Constants)
7062 for (Instruction *
D : Defs) {
7064 ValMap[
D] =
D->getOperand(0);
7068 ValMap[
D] =
new BitCastInst(
D, ConvertTy,
D->getName() +
".bc", insertPt);
7071 for (PHINode *Phi : PhiNodes)
7073 Phi->getName() +
".tc",
Phi->getIterator());
7075 for (PHINode *Phi : PhiNodes) {
7077 for (
int i = 0, e =
Phi->getNumIncomingValues(); i < e; i++)
7079 Phi->getIncomingBlock(i));
7083 for (Instruction *U :
Uses) {
7088 U->setOperand(0,
new BitCastInst(ValMap[
U->getOperand(0)], PhiTy,
"bc",
7098bool CodeGenPrepare::optimizePhiTypes(Function &
F) {
7103 SmallPtrSet<PHINode *, 4> Visited;
7104 SmallPtrSet<Instruction *, 4> DeletedInstrs;
7108 for (
auto &Phi : BB.
phis())
7109 Changed |= optimizePhiType(&Phi, Visited, DeletedInstrs);
7112 for (
auto *
I : DeletedInstrs) {
7114 I->eraseFromParent();
7122bool CodeGenPrepare::canFormExtLd(
7123 const SmallVectorImpl<Instruction *> &MovedExts, LoadInst *&LI,
7124 Instruction *&Inst,
bool HasPromoted) {
7125 for (
auto *MovedExtInst : MovedExts) {
7128 Inst = MovedExtInst;
7180bool CodeGenPrepare::optimizeExt(Instruction *&Inst) {
7181 bool AllowPromotionWithoutCommonHeader =
false;
7186 *Inst, AllowPromotionWithoutCommonHeader);
7187 TypePromotionTransaction TPT(RemovedInsts);
7188 TypePromotionTransaction::ConstRestorationPt LastKnownGood =
7189 TPT.getRestorationPoint();
7191 SmallVector<Instruction *, 2> SpeculativelyMovedExts;
7194 bool HasPromoted = tryToPromoteExts(TPT, Exts, SpeculativelyMovedExts);
7197 LoadInst *LI =
nullptr;
7202 if (canFormExtLd(SpeculativelyMovedExts, LI, ExtFedByLoad, HasPromoted)) {
7203 assert(LI && ExtFedByLoad &&
"Expect a valid load and extension");
7208 Inst = ExtFedByLoad;
7213 if (ATPConsiderable &&
7214 performAddressTypePromotion(Inst, AllowPromotionWithoutCommonHeader,
7215 HasPromoted, TPT, SpeculativelyMovedExts))
7218 TPT.rollback(LastKnownGood);
7227bool CodeGenPrepare::performAddressTypePromotion(
7228 Instruction *&Inst,
bool AllowPromotionWithoutCommonHeader,
7229 bool HasPromoted, TypePromotionTransaction &TPT,
7230 SmallVectorImpl<Instruction *> &SpeculativelyMovedExts) {
7231 bool Promoted =
false;
7232 SmallPtrSet<Instruction *, 1> UnhandledExts;
7233 bool AllSeenFirst =
true;
7234 for (
auto *
I : SpeculativelyMovedExts) {
7235 Value *HeadOfChain =
I->getOperand(0);
7236 DenseMap<Value *, Instruction *>::iterator AlreadySeen =
7237 SeenChainsForSExt.
find(HeadOfChain);
7240 if (AlreadySeen != SeenChainsForSExt.
end()) {
7241 if (AlreadySeen->second !=
nullptr)
7242 UnhandledExts.
insert(AlreadySeen->second);
7243 AllSeenFirst =
false;
7247 if (!AllSeenFirst || (AllowPromotionWithoutCommonHeader &&
7248 SpeculativelyMovedExts.size() == 1)) {
7252 for (
auto *
I : SpeculativelyMovedExts) {
7253 Value *HeadOfChain =
I->getOperand(0);
7254 SeenChainsForSExt[HeadOfChain] =
nullptr;
7255 ValToSExtendedUses[HeadOfChain].push_back(
I);
7258 Inst = SpeculativelyMovedExts.pop_back_val();
7263 for (
auto *
I : SpeculativelyMovedExts) {
7264 Value *HeadOfChain =
I->getOperand(0);
7265 SeenChainsForSExt[HeadOfChain] = Inst;
7270 if (!AllSeenFirst && !UnhandledExts.
empty())
7271 for (
auto *VisitedSExt : UnhandledExts) {
7272 if (RemovedInsts.count(VisitedSExt))
7274 TypePromotionTransaction TPT(RemovedInsts);
7276 SmallVector<Instruction *, 2> Chains;
7278 bool HasPromoted = tryToPromoteExts(TPT, Exts, Chains);
7282 for (
auto *
I : Chains) {
7283 Value *HeadOfChain =
I->getOperand(0);
7285 SeenChainsForSExt[HeadOfChain] =
nullptr;
7286 ValToSExtendedUses[HeadOfChain].push_back(
I);
7292bool CodeGenPrepare::optimizeExtUses(Instruction *
I) {
7297 Value *Src =
I->getOperand(0);
7298 if (Src->hasOneUse())
7310 bool DefIsLiveOut =
false;
7311 for (User *U :
I->users()) {
7316 if (UserBB == DefBB)
7318 DefIsLiveOut =
true;
7325 for (User *U : Src->users()) {
7328 if (UserBB == DefBB)
7337 DenseMap<BasicBlock *, Instruction *> InsertedTruncs;
7339 bool MadeChange =
false;
7340 for (Use &U : Src->uses()) {
7345 if (UserBB == DefBB)
7349 Instruction *&InsertedTrunc = InsertedTruncs[UserBB];
7351 if (!InsertedTrunc) {
7354 InsertedTrunc =
new TruncInst(
I, Src->getType(),
"");
7356 InsertedInsts.insert(InsertedTrunc);
7419bool CodeGenPrepare::optimizeLoadExt(LoadInst *Load) {
7420 if (!
Load->isSimple() || !
Load->getType()->isIntOrPtrTy())
7424 if (
Load->hasOneUse() &&
7430 SmallVector<Instruction *, 8> WorkList;
7431 SmallPtrSet<Instruction *, 16> Visited;
7432 SmallVector<Instruction *, 8> AndsToMaybeRemove;
7433 SmallVector<Instruction *, 8> DropFlags;
7434 for (
auto *U :
Load->users())
7446 while (!WorkList.
empty()) {
7450 if (!Visited.
insert(
I).second)
7455 for (
auto *U :
Phi->users())
7460 switch (
I->getOpcode()) {
7461 case Instruction::And: {
7465 APInt AndBits = AndC->getValue();
7466 DemandBits |= AndBits;
7468 if (AndBits.
ugt(WidestAndBits))
7469 WidestAndBits = AndBits;
7470 if (AndBits == WidestAndBits &&
I->getOperand(0) == Load)
7475 case Instruction::Shl: {
7479 uint64_t ShiftAmt = ShlC->getLimitedValue(
BitWidth - 1);
7480 DemandBits.setLowBits(
BitWidth - ShiftAmt);
7485 case Instruction::Trunc: {
7488 DemandBits.setLowBits(TruncBitWidth);
7498 uint32_t ActiveBits = DemandBits.getActiveBits();
7510 if (ActiveBits <= 1 || !DemandBits.isMask(ActiveBits) ||
7511 WidestAndBits != DemandBits)
7514 LLVMContext &Ctx =
Load->getType()->getContext();
7515 Type *TruncTy = Type::getIntNTy(Ctx, ActiveBits);
7525 Builder.CreateAnd(Load, ConstantInt::get(Ctx, DemandBits)));
7528 InsertedInsts.insert(NewAnd);
7533 NewAnd->setOperand(0, Load);
7536 for (
auto *
And : AndsToMaybeRemove)
7541 if (&*CurInstIterator ==
And)
7542 CurInstIterator = std::next(
And->getIterator());
7543 And->eraseFromParent();
7548 for (
auto *Inst : DropFlags)
7562 TTI->isExpensiveToSpeculativelyExecute(
I);
7580 uint64_t Max = std::max(TrueWeight, FalseWeight);
7581 uint64_t Sum = TrueWeight + FalseWeight;
7584 if (Probability >
TTI->getPredictableBranchThreshold())
7594 if (!Cmp || !Cmp->hasOneUse())
7617 assert(DefSI->getCondition() ==
SI->getCondition() &&
7618 "The condition of DefSI does not match with SI");
7619 V = (isTrue ? DefSI->getTrueValue() : DefSI->getFalseValue());
7622 assert(V &&
"Failed to get select true/false value");
7626bool CodeGenPrepare::optimizeShiftInst(BinaryOperator *Shift) {
7650 BinaryOperator::BinaryOps Opcode = Shift->
getOpcode();
7651 Value *NewTVal = Builder.CreateBinOp(Opcode, Shift->
getOperand(0), TVal);
7652 Value *NewFVal = Builder.CreateBinOp(Opcode, Shift->
getOperand(0), FVal);
7653 Value *NewSel = Builder.CreateSelect(
Cond, NewTVal, NewFVal);
7659bool CodeGenPrepare::optimizeFunnelShift(IntrinsicInst *Fsh) {
7661 assert((Opcode == Intrinsic::fshl || Opcode == Intrinsic::fshr) &&
7662 "Expected a funnel shift");
7686 Value *NewTVal = Builder.CreateIntrinsic(Opcode, Ty, {
X,
Y, TVal});
7687 Value *NewFVal = Builder.CreateIntrinsic(Opcode, Ty, {
X,
Y, FVal});
7688 Value *NewSel = Builder.CreateSelect(
Cond, NewTVal, NewFVal);
7696bool CodeGenPrepare::optimizeSelectInst(SelectInst *SI) {
7708 It !=
SI->getParent()->
end(); ++It) {
7710 if (
I &&
SI->getCondition() ==
I->getCondition()) {
7717 SelectInst *LastSI = ASI.
back();
7720 CurInstIterator = std::next(LastSI->
getIterator());
7724 for (SelectInst *SI :
ArrayRef(ASI).drop_front())
7725 fixupDbgVariableRecordsOnInst(*SI);
7727 bool VectorCond = !
SI->getCondition()->getType()->isIntegerTy(1);
7730 if (VectorCond ||
SI->getMetadata(LLVMContext::MD_unpredictable))
7733 TargetLowering::SelectSupportKind SelectKind;
7734 if (
SI->getType()->isVectorTy())
7735 SelectKind = TargetLowering::ScalarCondVectorVal;
7737 SelectKind = TargetLowering::ScalarValSelect;
7778 for (SelectInst *SI : ASI) {
7790 SplitPt.setHeadBit(
true);
7793 auto *CondFr =
IB.CreateFreeze(
SI->getCondition(),
SI->getName() +
".frozen");
7798 BranchInst *TrueBranch =
nullptr;
7799 BranchInst *FalseBranch =
nullptr;
7800 if (TrueInstrs.
size() == 0) {
7802 CondFr, SplitPt,
false,
nullptr,
nullptr, LI));
7805 }
else if (FalseInstrs.
size() == 0) {
7807 CondFr, SplitPt,
false,
nullptr,
nullptr, LI));
7814 nullptr,
nullptr, LI);
7822 EndBlock->
setName(
"select.end");
7824 TrueBlock->
setName(
"select.true.sink");
7826 FalseBlock->
setName(FalseInstrs.
size() == 0 ?
"select.false"
7827 :
"select.false.sink");
7831 FreshBBs.
insert(TrueBlock);
7833 FreshBBs.
insert(FalseBlock);
7834 FreshBBs.
insert(EndBlock);
7839 static const unsigned MD[] = {
7840 LLVMContext::MD_prof, LLVMContext::MD_unpredictable,
7841 LLVMContext::MD_make_implicit, LLVMContext::MD_dbg};
7846 for (Instruction *
I : TrueInstrs)
7848 for (Instruction *
I : FalseInstrs)
7855 if (TrueBlock ==
nullptr)
7856 TrueBlock = StartBlock;
7857 else if (FalseBlock ==
nullptr)
7858 FalseBlock = StartBlock;
7874 SI->eraseFromParent();
7876 ++NumSelectsExpanded;
7880 CurInstIterator = StartBlock->
end();
7887bool CodeGenPrepare::optimizeShuffleVectorInst(ShuffleVectorInst *SVI) {
7899 "Expected a type of the same size!");
7905 Builder.SetInsertPoint(SVI);
7906 Value *BC1 = Builder.CreateBitCast(
7908 Value *Shuffle = Builder.CreateVectorSplat(NewVecType->getNumElements(), BC1);
7909 Value *BC2 = Builder.CreateBitCast(Shuffle, SVIVecType);
7913 SVI, TLInfo,
nullptr,
7914 [&](
Value *V) { removeAllAssertingVHReferences(V); });
7921 !
Op->isTerminator() && !
Op->isEHPad())
7927bool CodeGenPrepare::tryToSinkFreeOperands(Instruction *
I) {
7942 DenseMap<const Instruction *, unsigned long> InstOrdering;
7943 unsigned long InstNumber = 0;
7944 for (
const auto &
I : *TargetBB)
7945 InstOrdering[&
I] = InstNumber++;
7947 for (Use *U :
reverse(OpsToSink)) {
7952 if (InstOrdering[UI] < InstOrdering[InsertPoint])
7959 SetVector<Instruction *> MaybeDead;
7960 DenseMap<Instruction *, Instruction *> NewInstructions;
7961 for (Use *U : ToReplace) {
7970 FreshBBs.
insert(OpDef->getParent());
7973 NewInstructions[UI] = NI;
7978 InsertedInsts.insert(NI);
7984 if (
auto It = NewInstructions.
find(OldI); It != NewInstructions.
end())
7985 It->second->setOperand(
U->getOperandNo(), NI);
7992 for (
auto *
I : MaybeDead) {
7993 if (!
I->hasNUsesOrMore(1)) {
7995 I->eraseFromParent();
8002bool CodeGenPrepare::optimizeSwitchType(SwitchInst *SI) {
8019 auto *NewType = Type::getIntNTy(
Context, RegWidth);
8028 ExtType = Instruction::SExt;
8031 if (Arg->hasSExtAttr())
8032 ExtType = Instruction::SExt;
8033 if (Arg->hasZExtAttr())
8034 ExtType = Instruction::ZExt;
8040 SI->setCondition(ExtInst);
8041 for (
auto Case :
SI->cases()) {
8042 const APInt &NarrowConst = Case.getCaseValue()->getValue();
8043 APInt WideConst = (ExtType == Instruction::ZExt)
8044 ? NarrowConst.
zext(RegWidth)
8045 : NarrowConst.
sext(RegWidth);
8046 Case.setValue(ConstantInt::get(
Context, WideConst));
8052bool CodeGenPrepare::optimizeSwitchPhiConstants(SwitchInst *SI) {
8059 Value *Condition =
SI->getCondition();
8068 for (
const SwitchInst::CaseHandle &Case :
SI->cases()) {
8069 ConstantInt *CaseValue = Case.getCaseValue();
8070 BasicBlock *CaseBB = Case.getCaseSuccessor();
8073 bool CheckedForSinglePred =
false;
8074 for (PHINode &
PHI : CaseBB->
phis()) {
8075 Type *PHIType =
PHI.getType();
8083 if (PHIType == ConditionType || TryZExt) {
8085 bool SkipCase =
false;
8086 Value *Replacement =
nullptr;
8087 for (
unsigned I = 0,
E =
PHI.getNumIncomingValues();
I !=
E;
I++) {
8088 Value *PHIValue =
PHI.getIncomingValue(
I);
8089 if (PHIValue != CaseValue) {
8098 if (
PHI.getIncomingBlock(
I) != SwitchBB)
8103 if (!CheckedForSinglePred) {
8104 CheckedForSinglePred =
true;
8105 if (
SI->findCaseDest(CaseBB) ==
nullptr) {
8111 if (Replacement ==
nullptr) {
8112 if (PHIValue == CaseValue) {
8113 Replacement = Condition;
8116 Replacement = Builder.CreateZExt(Condition, PHIType);
8119 PHI.setIncomingValue(
I, Replacement);
8130bool CodeGenPrepare::optimizeSwitchInst(SwitchInst *SI) {
8131 bool Changed = optimizeSwitchType(SI);
8132 Changed |= optimizeSwitchPhiConstants(SI);
8153class VectorPromoteHelper {
8155 const DataLayout &
DL;
8158 const TargetLowering &TLI;
8161 const TargetTransformInfo &
TTI;
8167 SmallVector<Instruction *, 4> InstsToBePromoted;
8170 unsigned StoreExtractCombineCost;
8179 if (InstsToBePromoted.
empty())
8181 return InstsToBePromoted.
back();
8187 unsigned getTransitionOriginalValueIdx()
const {
8189 "Other kind of transitions are not supported yet");
8196 unsigned getTransitionIdx()
const {
8198 "Other kind of transitions are not supported yet");
8206 Type *getTransitionType()
const {
8217 void promoteImpl(Instruction *ToBePromoted);
8221 bool isProfitableToPromote() {
8222 Value *ValIdx = Transition->
getOperand(getTransitionOriginalValueIdx());
8226 Type *PromotedType = getTransitionType();
8229 unsigned AS =
ST->getPointerAddressSpace();
8247 for (
const auto &Inst : InstsToBePromoted) {
8255 TargetTransformInfo::OperandValueInfo Arg0Info, Arg1Info;
8267 dbgs() <<
"Estimated cost of computation to be promoted:\nScalar: "
8268 << ScalarCost <<
"\nVector: " << VectorCost <<
'\n');
8269 return ScalarCost > VectorCost;
8281 unsigned ExtractIdx = std::numeric_limits<unsigned>::max();
8296 if (!
EC.isScalable()) {
8297 SmallVector<Constant *, 4> ConstVec;
8299 for (
unsigned Idx = 0; Idx !=
EC.getKnownMinValue(); ++Idx) {
8300 if (Idx == ExtractIdx)
8308 "Generate scalable vector for non-splat is unimplemented");
8313 static bool canCauseUndefinedBehavior(
const Instruction *Use,
8314 unsigned OperandIdx) {
8317 if (OperandIdx != 1)
8319 switch (
Use->getOpcode()) {
8322 case Instruction::SDiv:
8323 case Instruction::UDiv:
8324 case Instruction::SRem:
8325 case Instruction::URem:
8327 case Instruction::FDiv:
8328 case Instruction::FRem:
8329 return !
Use->hasNoNaNs();
8335 VectorPromoteHelper(
const DataLayout &
DL,
const TargetLowering &TLI,
8336 const TargetTransformInfo &
TTI, Instruction *Transition,
8337 unsigned CombineCost)
8338 :
DL(
DL), TLI(TLI),
TTI(
TTI), Transition(Transition),
8339 StoreExtractCombineCost(CombineCost) {
8340 assert(Transition &&
"Do not know how to promote null");
8344 bool canPromote(
const Instruction *ToBePromoted)
const {
8351 bool shouldPromote(
const Instruction *ToBePromoted)
const {
8354 for (
const Use &U : ToBePromoted->
operands()) {
8355 const Value *Val =
U.get();
8356 if (Val == getEndOfTransition()) {
8360 if (canCauseUndefinedBehavior(ToBePromoted,
U.getOperandNo()))
8383 void enqueueForPromotion(Instruction *ToBePromoted) {
8384 InstsToBePromoted.push_back(ToBePromoted);
8388 void recordCombineInstruction(Instruction *ToBeCombined) {
8390 CombineInst = ToBeCombined;
8400 if (InstsToBePromoted.empty() || !CombineInst)
8408 for (
auto &ToBePromoted : InstsToBePromoted)
8409 promoteImpl(ToBePromoted);
8410 InstsToBePromoted.clear();
8417void VectorPromoteHelper::promoteImpl(Instruction *ToBePromoted) {
8427 "The type of the result of the transition does not match "
8432 Type *TransitionTy = getTransitionType();
8437 for (Use &U : ToBePromoted->
operands()) {
8439 Value *NewVal =
nullptr;
8440 if (Val == Transition)
8441 NewVal = Transition->
getOperand(getTransitionOriginalValueIdx());
8448 canCauseUndefinedBehavior(ToBePromoted,
U.getOperandNo()));
8452 ToBePromoted->
setOperand(
U.getOperandNo(), NewVal);
8455 Transition->
setOperand(getTransitionOriginalValueIdx(), ToBePromoted);
8461bool CodeGenPrepare::optimizeExtractElementInst(Instruction *Inst) {
8462 unsigned CombineCost = std::numeric_limits<unsigned>::max();
8477 LLVM_DEBUG(
dbgs() <<
"Found an interesting transition: " << *Inst <<
'\n');
8478 VectorPromoteHelper VPH(*
DL, *TLI, *
TTI, Inst, CombineCost);
8485 if (ToBePromoted->
getParent() != Parent) {
8486 LLVM_DEBUG(
dbgs() <<
"Instruction to promote is in a different block ("
8488 <<
") than the transition (" << Parent->
getName()
8493 if (VPH.canCombine(ToBePromoted)) {
8495 <<
"will be combined with: " << *ToBePromoted <<
'\n');
8496 VPH.recordCombineInstruction(ToBePromoted);
8498 NumStoreExtractExposed +=
Changed;
8503 if (!VPH.canPromote(ToBePromoted) || !VPH.shouldPromote(ToBePromoted))
8506 LLVM_DEBUG(
dbgs() <<
"Promoting is possible... Enqueue for promotion!\n");
8508 VPH.enqueueForPromotion(ToBePromoted);
8509 Inst = ToBePromoted;
8549 Type *StoreType =
SI.getValueOperand()->getType();
8558 if (!
DL.typeSizeEqualsStoreSize(StoreType) ||
8559 DL.getTypeSizeInBits(StoreType) == 0)
8562 unsigned HalfValBitSize =
DL.getTypeSizeInBits(StoreType) / 2;
8564 if (!
DL.typeSizeEqualsStoreSize(SplitStoreType))
8568 if (
SI.isVolatile())
8580 if (!
match(
SI.getValueOperand(),
8587 if (!
LValue->getType()->isIntegerTy() ||
8588 DL.getTypeSizeInBits(
LValue->getType()) > HalfValBitSize ||
8590 DL.getTypeSizeInBits(HValue->
getType()) > HalfValBitSize)
8606 Builder.SetInsertPoint(&
SI);
8610 if (LBC && LBC->getParent() !=
SI.getParent())
8611 LValue = Builder.CreateBitCast(LBC->getOperand(0), LBC->getType());
8612 if (HBC && HBC->getParent() !=
SI.getParent())
8613 HValue = Builder.CreateBitCast(HBC->getOperand(0), HBC->getType());
8615 bool IsLE =
SI.getDataLayout().isLittleEndian();
8616 auto CreateSplitStore = [&](
Value *V,
bool Upper) {
8617 V = Builder.CreateZExtOrBitCast(V, SplitStoreType);
8618 Value *Addr =
SI.getPointerOperand();
8619 Align Alignment =
SI.getAlign();
8620 const bool IsOffsetStore = (IsLE &&
Upper) || (!IsLE && !
Upper);
8621 if (IsOffsetStore) {
8622 Addr = Builder.CreateGEP(
8623 SplitStoreType, Addr,
8631 Builder.CreateAlignedStore(V, Addr, Alignment);
8634 CreateSplitStore(
LValue,
false);
8635 CreateSplitStore(HValue,
true);
8638 SI.eraseFromParent();
8646 return GEP->getNumOperands() == 2 &&
I.isSequential() &&
8728 if (GEPIOpI->getParent() != SrcBlock)
8733 if (auto *I = dyn_cast<Instruction>(Usr)) {
8734 if (I->getParent() != SrcBlock) {
8742 std::vector<GetElementPtrInst *> UGEPIs;
8745 for (User *Usr : GEPIOp->
users()) {
8764 if (UGEPI->getOperand(0) != GEPIOp)
8766 if (UGEPI->getSourceElementType() != GEPI->getSourceElementType())
8768 if (GEPIIdx->getType() !=
8776 UGEPIs.push_back(UGEPI);
8778 if (UGEPIs.size() == 0)
8781 for (GetElementPtrInst *UGEPI : UGEPIs) {
8783 APInt NewIdx = UGEPIIdx->
getValue() - GEPIIdx->getValue();
8790 for (GetElementPtrInst *UGEPI : UGEPIs) {
8791 UGEPI->setOperand(0, GEPI);
8793 Constant *NewUGEPIIdx = ConstantInt::get(
8794 GEPIIdx->getType(), UGEPIIdx->
getValue() - GEPIIdx->getValue());
8795 UGEPI->setOperand(1, NewUGEPIIdx);
8798 if (!GEPI->isInBounds()) {
8799 UGEPI->setIsInBounds(
false);
8806 return cast<Instruction>(Usr)->getParent() != SrcBlock;
8808 "GEPIOp is used outside SrcBlock");
8832 Value *
X = Cmp->getOperand(0);
8833 if (!
X->hasUseList())
8838 for (
auto *U :
X->users()) {
8842 (UI->
getParent() != Branch->getParent() &&
8843 UI->
getParent() != Branch->getSuccessor(0) &&
8844 UI->
getParent() != Branch->getSuccessor(1)) ||
8845 (UI->
getParent() != Branch->getParent() &&
8846 !UI->
getParent()->getSinglePredecessor()))
8852 if (UI->
getParent() != Branch->getParent())
8856 ConstantInt::get(UI->
getType(), 0));
8858 LLVM_DEBUG(
dbgs() <<
" to compare on zero: " << *NewCmp <<
"\n");
8862 if (Cmp->isEquality() &&
8867 if (UI->
getParent() != Branch->getParent())
8870 Value *NewCmp = Builder.CreateCmp(Cmp->getPredicate(), UI,
8871 ConstantInt::get(UI->
getType(), 0));
8873 LLVM_DEBUG(
dbgs() <<
" to compare on zero: " << *NewCmp <<
"\n");
8881bool CodeGenPrepare::optimizeInst(Instruction *
I, ModifyDT &ModifiedDT) {
8882 bool AnyChange =
false;
8883 AnyChange = fixupDbgVariableRecordsOnInst(*
I);
8887 if (InsertedInsts.count(
I))
8896 LargeOffsetGEPMap.erase(
P);
8898 P->eraseFromParent();
8921 I, LI->getLoopFor(
I->getParent()), *
TTI))
8929 TargetLowering::TypeExpandInteger) {
8933 I, LI->getLoopFor(
I->getParent()), *
TTI))
8936 bool MadeChange = optimizeExt(
I);
8937 return MadeChange | optimizeExtUses(
I);
8944 if (optimizeCmp(Cmp, ModifiedDT))
8948 if (optimizeURem(
I))
8952 LI->
setMetadata(LLVMContext::MD_invariant_group,
nullptr);
8953 bool Modified = optimizeLoadExt(LI);
8962 SI->setMetadata(LLVMContext::MD_invariant_group,
nullptr);
8963 unsigned AS =
SI->getPointerAddressSpace();
8964 return optimizeMemoryInst(
I,
SI->getOperand(1),
8965 SI->getOperand(0)->getType(), AS);
8969 unsigned AS = RMW->getPointerAddressSpace();
8970 return optimizeMemoryInst(
I, RMW->getPointerOperand(), RMW->getType(), AS);
8974 unsigned AS = CmpX->getPointerAddressSpace();
8975 return optimizeMemoryInst(
I, CmpX->getPointerOperand(),
8976 CmpX->getCompareOperand()->getType(), AS);
8986 if (BinOp && (BinOp->
getOpcode() == Instruction::AShr ||
8987 BinOp->
getOpcode() == Instruction::LShr)) {
8995 if (GEPI->hasAllZeroIndices()) {
8997 Instruction *
NC =
new BitCastInst(GEPI->getOperand(0), GEPI->getType(),
8998 GEPI->getName(), GEPI->getIterator());
8999 NC->setDebugLoc(GEPI->getDebugLoc());
9002 GEPI, TLInfo,
nullptr,
9003 [&](
Value *V) { removeAllAssertingVHReferences(V); });
9005 optimizeInst(
NC, ModifiedDT);
9028 if (Const0 || Const1) {
9029 if (!Const0 || !Const1) {
9030 auto *
F =
new FreezeInst(Const0 ? Op1 : Op0,
"", CmpI->
getIterator());
9035 FI->eraseFromParent();
9042 if (tryToSinkFreeOperands(
I))
9045 switch (
I->getOpcode()) {
9046 case Instruction::Shl:
9047 case Instruction::LShr:
9048 case Instruction::AShr:
9050 case Instruction::Call:
9052 case Instruction::Select:
9054 case Instruction::ShuffleVector:
9056 case Instruction::Switch:
9058 case Instruction::ExtractElement:
9060 case Instruction::Br:
9069bool CodeGenPrepare::makeBitReverse(Instruction &
I) {
9070 if (!
I.getType()->isIntegerTy() ||
9075 SmallVector<Instruction *, 4> Insts;
9081 &
I, TLInfo,
nullptr,
9082 [&](
Value *V) { removeAllAssertingVHReferences(V); });
9089bool CodeGenPrepare::optimizeBlock(BasicBlock &BB, ModifyDT &ModifiedDT) {
9091 bool MadeChange =
false;
9094 CurInstIterator = BB.
begin();
9095 ModifiedDT = ModifyDT::NotModifyDT;
9096 while (CurInstIterator != BB.
end()) {
9097 MadeChange |= optimizeInst(&*CurInstIterator++, ModifiedDT);
9098 if (ModifiedDT != ModifyDT::NotModifyDT) {
9111 }
while (ModifiedDT == ModifyDT::ModifyInstDT);
9113 bool MadeBitReverse =
true;
9114 while (MadeBitReverse) {
9115 MadeBitReverse =
false;
9117 if (makeBitReverse(
I)) {
9118 MadeBitReverse = MadeChange =
true;
9123 MadeChange |= dupRetToEnableTailCallOpts(&BB, ModifiedDT);
9128bool CodeGenPrepare::fixupDbgVariableRecordsOnInst(Instruction &
I) {
9129 bool AnyChange =
false;
9130 for (DbgVariableRecord &DVR :
filterDbgVars(
I.getDbgRecordRange()))
9131 AnyChange |= fixupDbgVariableRecord(DVR);
9137bool CodeGenPrepare::fixupDbgVariableRecord(DbgVariableRecord &DVR) {
9138 if (DVR.
Type != DbgVariableRecord::LocationType::Value &&
9139 DVR.
Type != DbgVariableRecord::LocationType::Assign)
9143 bool AnyChange =
false;
9144 SmallDenseSet<Value *> LocationOps(DVR.
location_ops().begin(),
9146 for (
Value *Location : LocationOps) {
9147 WeakTrackingVH SunkAddrVH = SunkAddrs[
Location];
9176bool CodeGenPrepare::placeDbgValues(Function &
F) {
9177 bool MadeChange =
false;
9178 DominatorTree DT(
F);
9180 auto DbgProcessor = [&](
auto *DbgItem,
Instruction *Position) {
9181 SmallVector<Instruction *, 4> VIs;
9182 for (
Value *V : DbgItem->location_ops())
9190 for (Instruction *VI : VIs) {
9191 if (
VI->isTerminator())
9196 if (
isa<PHINode>(VI) &&
VI->getParent()->getTerminator()->isEHPad())
9207 if (VIs.size() > 1) {
9210 <<
"Unable to find valid location for Debug Value, undefing:\n"
9212 DbgItem->setKillLocation();
9217 << *DbgItem <<
' ' << *VI);
9224 for (BasicBlock &BB :
F) {
9230 if (DVR.
Type != DbgVariableRecord::LocationType::Value)
9232 DbgProcessor(&DVR, &Insn);
9243bool CodeGenPrepare::placePseudoProbes(Function &
F) {
9244 bool MadeChange =
false;
9247 auto FirstInst =
Block.getFirstInsertionPt();
9248 while (FirstInst !=
Block.end() && FirstInst->isDebugOrPseudoInst())
9252 while (
I !=
Block.end()) {
9254 II->moveBefore(FirstInst);
9264 uint64_t NewMax = (NewTrue > NewFalse) ? NewTrue : NewFalse;
9265 uint32_t Scale = (NewMax / std::numeric_limits<uint32_t>::max()) + 1;
9266 NewTrue = NewTrue / Scale;
9267 NewFalse = NewFalse / Scale;
9292bool CodeGenPrepare::splitBranchCondition(Function &
F, ModifyDT &ModifiedDT) {
9296 bool MadeChange =
false;
9297 for (
auto &BB :
F) {
9310 if (Br1->getMetadata(LLVMContext::MD_unpredictable))
9318 Value *Cond1, *Cond2;
9321 Opc = Instruction::And;
9324 Opc = Instruction::Or;
9334 if (!IsGoodCond(Cond1) || !IsGoodCond(Cond2))
9348 Br1->setCondition(Cond1);
9353 if (
Opc == Instruction::And)
9354 Br1->setSuccessor(0, TmpBB);
9356 Br1->setSuccessor(1, TmpBB);
9361 I->removeFromParent();
9362 I->insertBefore(Br2->getIterator());
9374 if (
Opc == Instruction::Or)
9381 for (PHINode &PN : FBB->
phis()) {
9388 if (
Opc == Instruction::Or) {
9408 uint64_t TrueWeight, FalseWeight;
9410 uint64_t NewTrueWeight = TrueWeight;
9411 uint64_t NewFalseWeight = TrueWeight + 2 * FalseWeight;
9413 Br1->setMetadata(LLVMContext::MD_prof,
9414 MDBuilder(Br1->getContext())
9415 .createBranchWeights(TrueWeight, FalseWeight,
9418 NewTrueWeight = TrueWeight;
9419 NewFalseWeight = 2 * FalseWeight;
9421 Br2->setMetadata(LLVMContext::MD_prof,
9422 MDBuilder(Br2->getContext())
9423 .createBranchWeights(TrueWeight, FalseWeight));
9444 uint64_t TrueWeight, FalseWeight;
9446 uint64_t NewTrueWeight = 2 * TrueWeight + FalseWeight;
9447 uint64_t NewFalseWeight = FalseWeight;
9449 Br1->setMetadata(LLVMContext::MD_prof,
9450 MDBuilder(Br1->getContext())
9451 .createBranchWeights(TrueWeight, FalseWeight));
9453 NewTrueWeight = 2 * TrueWeight;
9454 NewFalseWeight = FalseWeight;
9456 Br2->setMetadata(LLVMContext::MD_prof,
9457 MDBuilder(Br2->getContext())
9458 .createBranchWeights(TrueWeight, FalseWeight));
9462 ModifiedDT = ModifyDT::ModifyBBDT;
static unsigned getIntrinsicID(const SDNode *N)
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
AMDGPU Register Bank Select
This file implements a class to represent arbitrary precision integral constant values and operations...
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
static void print(raw_ostream &Out, object::Archive::Kind Kind, T Val)
This file contains the simple types necessary to represent the attributes associated with functions a...
static const Function * getParent(const Value *V)
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static bool sinkAndCmp0Expression(Instruction *AndI, const TargetLowering &TLI, SetOfInstrs &InsertedInsts)
Duplicate and sink the given 'and' instruction into user blocks where it is used in a compare to allo...
static bool SinkShiftAndTruncate(BinaryOperator *ShiftI, Instruction *User, ConstantInt *CI, DenseMap< BasicBlock *, BinaryOperator * > &InsertedShifts, const TargetLowering &TLI, const DataLayout &DL)
Sink both shift and truncate instruction to the use of truncate's BB.
static bool getGEPSmallConstantIntOffsetV(GetElementPtrInst *GEP, SmallVectorImpl< Value * > &OffsetV)
static bool sinkSelectOperand(const TargetTransformInfo *TTI, Value *V)
Check if V (an operand of a select instruction) is an expensive instruction that is only used once.
static bool isExtractBitsCandidateUse(Instruction *User)
Check if the candidates could be combined with a shift instruction, which includes:
static cl::opt< unsigned > MaxAddressUsersToScan("cgp-max-address-users-to-scan", cl::init(100), cl::Hidden, cl::desc("Max number of address users to look at"))
static cl::opt< bool > OptimizePhiTypes("cgp-optimize-phi-types", cl::Hidden, cl::init(true), cl::desc("Enable converting phi types in CodeGenPrepare"))
static cl::opt< bool > DisableStoreExtract("disable-cgp-store-extract", cl::Hidden, cl::init(false), cl::desc("Disable store(extract) optimizations in CodeGenPrepare"))
static bool foldFCmpToFPClassTest(CmpInst *Cmp, const TargetLowering &TLI, const DataLayout &DL)
static void scaleWeights(uint64_t &NewTrue, uint64_t &NewFalse)
Scale down both weights to fit into uint32_t.
static cl::opt< bool > ProfileUnknownInSpecialSection("profile-unknown-in-special-section", cl::Hidden, cl::desc("In profiling mode like sampleFDO, if a function doesn't have " "profile, we cannot tell the function is cold for sure because " "it may be a function newly added without ever being sampled. " "With the flag enabled, compiler can put such profile unknown " "functions into a special section, so runtime system can choose " "to handle it in a different way than .text section, to save " "RAM for example. "))
static bool OptimizeExtractBits(BinaryOperator *ShiftI, ConstantInt *CI, const TargetLowering &TLI, const DataLayout &DL)
Sink the shift right instruction into user blocks if the uses could potentially be combined with this...
static cl::opt< bool > DisableExtLdPromotion("disable-cgp-ext-ld-promotion", cl::Hidden, cl::init(false), cl::desc("Disable ext(promotable(ld)) -> promoted(ext(ld)) optimization in " "CodeGenPrepare"))
static cl::opt< bool > DisablePreheaderProtect("disable-preheader-prot", cl::Hidden, cl::init(false), cl::desc("Disable protection against removing loop preheaders"))
static cl::opt< bool > AddrSinkCombineBaseOffs("addr-sink-combine-base-offs", cl::Hidden, cl::init(true), cl::desc("Allow combining of BaseOffs field in Address sinking."))
static bool OptimizeNoopCopyExpression(CastInst *CI, const TargetLowering &TLI, const DataLayout &DL)
If the specified cast instruction is a noop copy (e.g.
static bool splitMergedValStore(StoreInst &SI, const DataLayout &DL, const TargetLowering &TLI)
For the instruction sequence of store below, F and I values are bundled together as an i64 value befo...
static bool SinkCast(CastInst *CI)
Sink the specified cast instruction into its user blocks.
static bool swapICmpOperandsToExposeCSEOpportunities(CmpInst *Cmp)
Many architectures use the same instruction for both subtract and cmp.
static cl::opt< bool > AddrSinkCombineBaseReg("addr-sink-combine-base-reg", cl::Hidden, cl::init(true), cl::desc("Allow combining of BaseReg field in Address sinking."))
static bool FindAllMemoryUses(Instruction *I, SmallVectorImpl< std::pair< Use *, Type * > > &MemoryUses, SmallPtrSetImpl< Instruction * > &ConsideredInsts, const TargetLowering &TLI, const TargetRegisterInfo &TRI, bool OptSize, ProfileSummaryInfo *PSI, BlockFrequencyInfo *BFI, unsigned &SeenInsts)
Recursively walk all the uses of I until we find a memory use.
static cl::opt< bool > StressStoreExtract("stress-cgp-store-extract", cl::Hidden, cl::init(false), cl::desc("Stress test store(extract) optimizations in CodeGenPrepare"))
static bool isFormingBranchFromSelectProfitable(const TargetTransformInfo *TTI, const TargetLowering *TLI, SelectInst *SI)
Returns true if a SelectInst should be turned into an explicit branch.
static std::optional< std::pair< Instruction *, Constant * > > getIVIncrement(const PHINode *PN, const LoopInfo *LI)
If given PN is an inductive variable with value IVInc coming from the backedge, and on each iteration...
static cl::opt< bool > AddrSinkCombineBaseGV("addr-sink-combine-base-gv", cl::Hidden, cl::init(true), cl::desc("Allow combining of BaseGV field in Address sinking."))
static cl::opt< bool > AddrSinkUsingGEPs("addr-sink-using-gep", cl::Hidden, cl::init(true), cl::desc("Address sinking in CGP using GEPs."))
static Value * getTrueOrFalseValue(SelectInst *SI, bool isTrue, const SmallPtrSet< const Instruction *, 2 > &Selects)
If isTrue is true, return the true value of SI, otherwise return false value of SI.
static cl::opt< bool > DisableBranchOpts("disable-cgp-branch-opts", cl::Hidden, cl::init(false), cl::desc("Disable branch optimizations in CodeGenPrepare"))
static cl::opt< bool > EnableTypePromotionMerge("cgp-type-promotion-merge", cl::Hidden, cl::desc("Enable merging of redundant sexts when one is dominating" " the other."), cl::init(true))
static cl::opt< bool > ProfileGuidedSectionPrefix("profile-guided-section-prefix", cl::Hidden, cl::init(true), cl::desc("Use profile info to add section prefix for hot/cold functions"))
static cl::opt< unsigned > HugeFuncThresholdInCGPP("cgpp-huge-func", cl::init(10000), cl::Hidden, cl::desc("Least BB number of huge function."))
static cl::opt< bool > AddrSinkNewSelects("addr-sink-new-select", cl::Hidden, cl::init(true), cl::desc("Allow creation of selects in Address sinking."))
static bool foldURemOfLoopIncrement(Instruction *Rem, const DataLayout *DL, const LoopInfo *LI, SmallPtrSet< BasicBlock *, 32 > &FreshBBs, bool IsHuge)
static bool optimizeBranch(BranchInst *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 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 bool despeculateCountZeros(IntrinsicInst *CountZeros, 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 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)
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 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 TableGen::Emitter::OptClass< SkeletonEmitter > X("gen-skeleton-class", "Generate example skeleton class")
static SymbolRef::Type getType(const Symbol *Sym)
static bool canCombine(MachineBasicBlock &MBB, MachineOperand &MO, unsigned CombineOpc=0)
This file describes how to lower LLVM code to machine code.
static cl::opt< bool > DisableSelectOptimize("disable-select-optimize", cl::init(true), cl::Hidden, cl::desc("Disable the select-optimization pass from running"))
Disable the select optimization pass.
Target-Independent Code Generator Pass Configuration Options pass.
static unsigned getBitWidth(Type *Ty, const DataLayout &DL)
Returns the bitwidth of the given scalar or pointer type.
static Constant * getConstantVector(MVT VT, ArrayRef< APInt > Bits, const APInt &Undefs, LLVMContext &C)
Class for arbitrary precision integers.
LLVM_ABI APInt zext(unsigned width) const
Zero extend to a new width.
bool ugt(const APInt &RHS) const
Unsigned greater than comparison.
bool isZero() const
Determine if this value is zero, i.e. all bits are clear.
bool isSignedIntN(unsigned N) const
Check if this APInt has an N-bits signed integer value.
unsigned getSignificantBits() const
Get the minimum bit size for this signed APInt.
unsigned logBase2() const
LLVM_ABI APInt sext(unsigned width) const
Sign extend to a new width.
bool isPowerOf2() const
Check if this APInt's value is a power of two greater than zero.
int64_t getSExtValue() const
Get sign extended value.
LLVM_ABI bool isStaticAlloca() const
Return true if this alloca is in the entry block of the function and is a constant size.
Align getAlign() const
Return the alignment of the memory that is being allocated by the instruction.
LLVM_ABI std::optional< TypeSize > getAllocationSize(const DataLayout &DL) const
Get allocation size in bytes.
void setAlignment(Align Align)
PassT::Result * getCachedResult(IRUnitT &IR) const
Get the cached result of an analysis pass for a given IR unit.
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
AnalysisUsage & addUsedIfAvailable()
Add the specified Pass class to the set of analyses used by this pass.
AnalysisUsage & addRequired()
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
An instruction that atomically checks whether a specified value is in a memory location,...
static unsigned getPointerOperandIndex()
an instruction that atomically reads a memory location, combines it with another value,...
static unsigned getPointerOperandIndex()
Analysis pass providing the BasicBlockSectionsProfileReader.
bool isFunctionHot(StringRef FuncName) const
LLVM Basic Block Representation.
iterator begin()
Instruction iterator methods.
iterator_range< const_phi_iterator > phis() const
Returns a range that iterates over the phis in the basic block.
LLVM_ABI const_iterator getFirstInsertionPt() const
Returns an iterator to the first instruction in this block that is suitable for inserting a non-PHI i...
const Function * getParent() const
Return the enclosing method, or null if none.
bool hasAddressTaken() const
Returns true if there are any uses of this basic block other than direct branches,...
LLVM_ABI InstListType::const_iterator getFirstNonPHIIt() const
Returns an iterator to the first instruction in this block that is not a PHINode instruction.
LLVM_ABI void insertDbgRecordBefore(DbgRecord *DR, InstListType::iterator Here)
Insert a DbgRecord into a block at the position given by Here.
InstListType::const_iterator const_iterator
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
LLVM_ABI void moveAfter(BasicBlock *MovePos)
Unlink this basic block from its current function and insert it right after MovePos in the function M...
LLVM_ABI InstListType::const_iterator getFirstNonPHIOrDbg(bool SkipPseudoOp=true) const
Returns a pointer to the first instruction in this block that is not a PHINode or a debug intrinsic,...
LLVM_ABI BasicBlock * splitBasicBlock(iterator I, const Twine &BBName="", bool Before=false)
Split the basic block into two basic blocks at the specified instruction.
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 SymbolTableList< BasicBlock >::iterator eraseFromParent()
Unlink 'this' from the containing function and delete it.
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 if the block is well formed or null if the block is not well forme...
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.
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.
Conditional or Unconditional Branch instruction.
LLVM_ABI void swapSuccessors()
Swap the successors of this branch instruction.
bool isConditional() const
BasicBlock * getSuccessor(unsigned i) const
bool isUnconditional() const
Analysis providing branch probability information.
static LLVM_ABI BranchProbability getBranchProbability(uint64_t Numerator, uint64_t Denominator)
bool isInlineAsm() const
Check if this call is an inline asm statement.
Function * getCalledFunction() const
Returns the function called, or null if this is an indirect function invocation or the function signa...
bool hasFnAttr(Attribute::AttrKind Kind) const
Determine whether this call has the given attribute.
Value * getArgOperand(unsigned i) const
void setArgOperand(unsigned i, Value *v)
iterator_range< User::op_iterator > args()
Iteration adapter for range-for loops.
This class represents a function call, abstracting a target machine's calling convention.
This is the base class for all instructions that perform data casts.
static LLVM_ABI CastInst * Create(Instruction::CastOps, Value *S, Type *Ty, const Twine &Name="", InsertPosition InsertBefore=nullptr)
Provides a way to construct any of the CastInst subclasses using an opcode instead of the subclass's ...
This class is the base class for the comparison instructions.
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
@ ICMP_SLT
signed less than
@ ICMP_UGT
unsigned greater than
@ ICMP_SGT
signed greater than
@ ICMP_ULT
unsigned less than
@ ICMP_ULE
unsigned less or equal
Predicate getSwappedPredicate() const
For example, EQ->EQ, SLE->SGE, ULT->UGT, OEQ->OEQ, ULE->UGE, OLT->OGT, etc.
static LLVM_ABI CmpInst * Create(OtherOps Op, Predicate Pred, Value *S1, Value *S2, const Twine &Name="", InsertPosition InsertBefore=nullptr)
Construct a compare instruction, given the opcode, the predicate and the two operands.
Predicate getPredicate() const
Return the predicate for this instruction.
An abstraction over a floating-point predicate, and a pack of an integer predicate with samesign info...
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
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 bool isReachableFromEntry(const Use &U) const
Provide an overload for a Use.
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...
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.
Type * getValueType() const
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 ...
bool hasMetadata() const
Return true if this instruction has any metadata attached to it.
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.
TypeSize getSizeInBits() const
Returns the size of the specified MVT in bits.
static MVT getIntegerVT(unsigned BitWidth)
LLVM_ABI void replacePhiUsesWith(MachineBasicBlock *Old, MachineBasicBlock *New)
Update all phi nodes in this basic block to refer to basic block New instead of basic block Old.
This class implements a map that also provides access to all stored values in a deterministic order.
VectorType::iterator erase(typename VectorType::iterator Iterator)
Remove the element given by Iterator.
iterator find(const KeyT &Key)
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
op_range incoming_values()
Value * getIncomingValueForBlock(const BasicBlock *BB) const
BasicBlock * getIncomingBlock(unsigned i) const
Return incoming basic block number i.
Value * getIncomingValue(unsigned i) const
Return incoming value number x.
unsigned getNumIncomingValues() const
Return the number of incoming edges.
static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr="", InsertPosition InsertBefore=nullptr)
Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...
static LLVM_ABI PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
PointerIntPair - This class implements a pair of a pointer and small integer.
static LLVM_ABI PoisonValue * get(Type *T)
Static factory methods - Return an 'poison' object of the specified type.
A set of analyses that are preserved following a run of a transformation pass.
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
PreservedAnalyses & preserve()
Mark an analysis as preserved.
An analysis pass based on the new PM to deliver ProfileSummaryInfo.
An analysis pass based on legacy pass manager to deliver ProfileSummaryInfo.
Analysis providing profile information.
bool isFunctionColdInCallGraph(const FuncT *F, BFIT &BFI) const
Returns true if F contains only cold code.
LLVM_ABI bool isFunctionHotnessUnknown(const Function &F) const
Returns true if the hotness of F is unknown.
bool isFunctionHotInCallGraph(const FuncT *F, BFIT &BFI) const
Returns true if F contains hot code.
LLVM_ABI bool hasPartialSampleProfile() const
Returns true if module M has partial-profile sample profile.
LLVM_ABI bool hasHugeWorkingSetSize() const
Returns true if the working set size of the code is considered huge.
Value * getReturnValue() const
Convenience accessor. Returns null if there is no return value.
This class represents the LLVM 'select' instruction.
static SelectInst * Create(Value *C, Value *S1, Value *S2, const Twine &NameStr="", InsertPosition InsertBefore=nullptr, const Instruction *MDFrom=nullptr)
size_type count(const_arg_type key) const
Count the number of elements of a given key in the SetVector.
void clear()
Completely clear the SetVector.
bool empty() const
Determine if the SetVector is empty or not.
bool insert(const value_type &X)
Insert a new element into the SetVector.
value_type pop_back_val()
VectorType * getType() const
Overload to return most specific vector type.
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
bool erase(PtrType Ptr)
Remove pointer from the set.
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
void insert_range(Range &&R)
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
bool contains(ConstPtrType Ptr) const
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
size_type count(const T &V) const
count - Return 1 if the element is in the set, 0 otherwise.
std::pair< const_iterator, bool > insert(const T &V)
insert - Insert an element into the set if it isn't already there.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
reference emplace_back(ArgTypes &&... Args)
void reserve(size_type N)
iterator erase(const_iterator CI)
typename SuperClass::iterator iterator
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
An instruction for storing to memory.
static unsigned getPointerOperandIndex()
TypeSize getElementOffset(unsigned Idx) const
Analysis pass providing the TargetTransformInfo.
Analysis pass providing the TargetLibraryInfo.
Provides information about what library functions are available for the current target.
bool getLibFunc(StringRef funcName, LibFunc &F) const
Searches for a particular function name.
int InstructionOpcodeToISD(unsigned Opcode) const
Get the ISD node that corresponds to the Instruction class opcode.
EVT getValueType(const DataLayout &DL, Type *Ty, bool AllowUnknown=false) const
Return the EVT corresponding to this LLVM type.
virtual bool isSelectSupported(SelectSupportKind) const
virtual bool isEqualityCmpFoldedWithSignedCmp() const
Return true if instruction generated for equality comparison is folded with instruction generated for...
virtual bool shouldFormOverflowOp(unsigned Opcode, EVT VT, bool MathUsed) const
Try to convert math with an overflow comparison into the corresponding DAG node operation.
virtual bool isMaskAndCmp0FoldingBeneficial(const Instruction &AndI) const
Return if the target supports combining a chain like:
virtual bool shouldOptimizeMulOverflowWithZeroHighBits(LLVMContext &Context, EVT VT) const
bool isExtLoad(const LoadInst *Load, const Instruction *Ext, const DataLayout &DL) const
Return true if Load and Ext can form an ExtLoad.
virtual bool isSExtCheaperThanZExt(EVT FromTy, EVT ToTy) const
Return true if sign-extension from FromTy to ToTy is cheaper than zero-extension.
const TargetMachine & getTargetMachine() const
virtual bool isCtpopFast(EVT VT) const
Return true if ctpop instruction is fast.
virtual bool isZExtFree(Type *FromTy, Type *ToTy) const
Return true if any actual instruction that defines a value of type FromTy implicitly zero-extends the...
bool enableExtLdPromotion() const
Return true if the target wants to use the optimization that turns ext(promotableInst1(....
virtual bool isCheapToSpeculateCttz(Type *Ty) const
Return true if it is cheap to speculate a call to intrinsic cttz.
bool isJumpExpensive() const
Return true if Flow Control is an expensive operation that should be avoided.
bool hasExtractBitsInsn() const
Return true if the target has BitExtract instructions.
virtual bool allowsMisalignedMemoryAccesses(EVT, unsigned AddrSpace=0, Align Alignment=Align(1), MachineMemOperand::Flags Flags=MachineMemOperand::MONone, unsigned *=nullptr) const
Determine if the target supports unaligned memory accesses.
bool isSlowDivBypassed() const
Returns true if target has indicated at least one type should be bypassed.
virtual bool isTruncateFree(Type *FromTy, Type *ToTy) const
Return true if it's free to truncate a value of type FromTy to type ToTy.
virtual bool hasMultipleConditionRegisters(EVT VT) const
Does the target have multiple (allocatable) condition registers that can be used to store the results...
virtual EVT getTypeToTransformTo(LLVMContext &Context, EVT VT) const
For types supported by the target, this is an identity function.
virtual MVT getPreferredSwitchConditionType(LLVMContext &Context, EVT ConditionVT) const
Returns preferred type for switch condition.
bool isCondCodeLegal(ISD::CondCode CC, MVT VT) const
Return true if the specified condition code is legal for a comparison of the specified types on this ...
virtual bool canCombineStoreAndExtract(Type *VectorTy, Value *Idx, unsigned &Cost) const
Return true if the target can combine store(extractelement VectorTy,Idx).
bool isTypeLegal(EVT VT) const
Return true if the target has native support for the specified value type.
virtual bool isFreeAddrSpaceCast(unsigned SrcAS, unsigned DestAS) const
Returns true if a cast from SrcAS to DestAS is "cheap", such that e.g.
virtual bool shouldConsiderGEPOffsetSplit() const
bool isExtFree(const Instruction *I) const
Return true if the extension represented by I is free.
bool isOperationLegalOrCustom(unsigned Op, EVT VT, bool LegalOnly=false) const
Return true if the specified operation is legal on this target or can be made legal with custom lower...
bool isPredictableSelectExpensive() const
Return true if selects are only cheaper than branches if the branch is unlikely to be predicted right...
virtual bool isMultiStoresCheaperThanBitsMerge(EVT LTy, EVT HTy) const
Return true if it is cheaper to split the store of a merged int val from a pair of smaller values int...
virtual bool getAddrModeArguments(const IntrinsicInst *, SmallVectorImpl< Value * > &, Type *&) const
CodeGenPrepare sinks address calculations into the same BB as Load/Store instructions reading the add...
bool isLoadExtLegal(unsigned ExtType, EVT ValVT, EVT MemVT) const
Return true if the specified load with extension is legal on this target.
const DenseMap< unsigned int, unsigned int > & getBypassSlowDivWidths() const
Returns map of slow types for division or remainder with corresponding fast types.
virtual bool isCheapToSpeculateCtlz(Type *Ty) const
Return true if it is cheap to speculate a call to intrinsic ctlz.
virtual bool useSoftFloat() const
virtual int64_t getPreferredLargeGEPBaseOffset(int64_t MinOffset, int64_t MaxOffset) const
Return the prefered common base offset.
LegalizeTypeAction getTypeAction(LLVMContext &Context, EVT VT) const
Return how we should legalize values of this type, either it is already legal (return 'Legal') or we ...
virtual bool shouldAlignPointerArgs(CallInst *, unsigned &, Align &) const
Return true if the pointer arguments to CI should be aligned by aligning the object whose address is ...
virtual Type * shouldConvertSplatType(ShuffleVectorInst *SVI) const
Given a shuffle vector SVI representing a vector splat, return a new scalar type of size equal to SVI...
virtual bool addressingModeSupportsTLS(const GlobalValue &) const
Returns true if the targets addressing mode can target thread local storage (TLS).
virtual bool shouldConvertPhiType(Type *From, Type *To) const
Given a set in interconnected phis of type 'From' that are loaded/stored or bitcast to type 'To',...
virtual bool isFAbsFree(EVT VT) const
Return true if an fabs operation is free to the point where it is never worthwhile to replace it with...
virtual bool preferZeroCompareBranch() const
Return true if the heuristic to prefer icmp eq zero should be used in code gen prepare.
virtual bool 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)
static LLVM_ABI UndefValue * get(Type *T)
Static factory methods - Return an 'undef' object of the specified type.
A Use represents the edge between a Value definition and its users.
const Use & getOperandUse(unsigned i) const
void setOperand(unsigned i, Value *Val)
LLVM_ABI bool replaceUsesOfWith(Value *From, Value *To)
Replace uses of one Value with another.
Value * getOperand(unsigned i) const
unsigned getNumOperands() const
LLVM Value Representation.
Type * getType() const
All values are typed, get the type of this value.
user_iterator user_begin()
LLVM_ABI void setName(const Twine &Name)
Change the name of the value.
bool hasOneUse() const
Return true if there is exactly one use of this value.
LLVM_ABI void replaceAllUsesWith(Value *V)
Change all uses of this to point to a new Value.
LLVMContext & getContext() const
All values hold a context through their type.
iterator_range< user_iterator > users()
LLVM_ABI Align getPointerAlignment(const DataLayout &DL) const
Returns an alignment of the pointer value.
LLVM_ABI bool isUsedInBasicBlock(const BasicBlock *BB) const
Check if this value is used in the specified basic block.
LLVM_ABI void printAsOperand(raw_ostream &O, bool PrintType=true, const Module *M=nullptr) const
Print the name of this Value out to the specified raw_ostream.
LLVM_ABI const Value * stripPointerCasts() const
Strip off pointer casts, all-zero GEPs and address space casts.
iterator_range< use_iterator > uses()
void mutateType(Type *Ty)
Mutate the type of this Value to be of the specified type.
user_iterator_impl< User > user_iterator
LLVM_ABI StringRef getName() const
Return a constant reference to the value's name.
LLVM_ABI void takeName(Value *V)
Transfer the name from V to this value.
LLVM_ABI void dump() const
Support for debugging, callable in GDB: V->dump()
bool pointsToAliveValue() const
int getNumOccurrences() const
constexpr ScalarTy getFixedValue() const
constexpr bool isNonZero() const
constexpr bool isScalable() const
Returns whether the quantity is scaled by a runtime quantity (vscale).
StructType * getStructTypeOrNull() const
TypeSize getSequentialElementStride(const DataLayout &DL) const
const ParentTy * getParent() const
self_iterator getIterator()
NodeTy * getNextNode()
Get the next node, or nullptr for the list tail.
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
constexpr char Align[]
Key for Kernel::Arg::Metadata::mAlign.
@ C
The default llvm calling convention, compatible with C.
unsigned getAddrMode(MCInstrInfo const &MCII, MCInst const &MCI)
@ BasicBlock
Various leaf nodes.
SpecificConstantMatch m_ZeroInt()
Convenience matchers for specific integer values.
OneUse_match< SubPat > m_OneUse(const SubPat &SP)
cst_pred_ty< is_all_ones > m_AllOnes()
Match an integer or vector with all bits set.
BinaryOp_match< LHS, RHS, Instruction::Add > m_Add(const LHS &L, const RHS &R)
class_match< BinaryOperator > m_BinOp()
Match an arbitrary binary operation and ignore it.
OverflowingBinaryOp_match< LHS, RHS, Instruction::Add, OverflowingBinaryOperator::NoUnsignedWrap > m_NUWAdd(const LHS &L, const RHS &R)
BinaryOp_match< LHS, RHS, Instruction::URem > m_URem(const LHS &L, const RHS &R)
class_match< Constant > m_Constant()
Match an arbitrary Constant and ignore it.
ap_match< APInt > m_APInt(const APInt *&Res)
Match a ConstantInt or splatted ConstantVector, binding the specified pointer to the contained APInt.
BinaryOp_match< LHS, RHS, Instruction::Xor > m_Xor(const LHS &L, const RHS &R)
ap_match< APInt > m_APIntAllowPoison(const APInt *&Res)
Match APInt while allowing poison in splat vector constants.
specific_intval< false > m_SpecificInt(const APInt &V)
Match a specific integer value or vector with all elements equal to the value.
bool match(Val *V, const Pattern &P)
bind_ty< Instruction > m_Instruction(Instruction *&I)
Match an instruction, capturing it if we match.
specificval_ty m_Specific(const Value *V)
Match if we have a specific specified value.
BinOpPred_match< LHS, RHS, is_right_shift_op > m_Shr(const LHS &L, const RHS &R)
Matches logical shift operations.
OverflowingBinaryOp_match< LHS, RHS, Instruction::Add, OverflowingBinaryOperator::NoUnsignedWrap, true > m_c_NUWAdd(const LHS &L, const RHS &R)
class_match< ConstantInt > m_ConstantInt()
Match an arbitrary ConstantInt and ignore it.
cst_pred_ty< is_one > m_One()
Match an integer 1 or a vector with all elements equal to 1.
IntrinsicID_match m_Intrinsic()
Match intrinsic calls like this: m_Intrinsic<Intrinsic::fabs>(m_Value(X))
ThreeOps_match< Cond, LHS, RHS, Instruction::Select > m_Select(const Cond &C, const LHS &L, const RHS &R)
Matches SelectInst.
ExtractValue_match< Ind, Val_t > m_ExtractValue(const Val_t &V)
Match a single index ExtractValue instruction.
auto m_LogicalOr()
Matches L || R where L and R are arbitrary values.
TwoOps_match< V1_t, V2_t, Instruction::ShuffleVector > m_Shuffle(const V1_t &v1, const V2_t &v2)
Matches ShuffleVectorInst independently of mask value.
CastInst_match< OpTy, ZExtInst > m_ZExt(const OpTy &Op)
Matches ZExt.
class_match< CmpInst > m_Cmp()
Matches any compare instruction and ignore it.
brc_match< Cond_t, bind_ty< BasicBlock >, bind_ty< BasicBlock > > m_Br(const Cond_t &C, BasicBlock *&T, BasicBlock *&F)
match_immconstant_ty m_ImmConstant()
Match an arbitrary immediate Constant and ignore it.
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
OverflowingBinaryOp_match< LHS, RHS, Instruction::Add, OverflowingBinaryOperator::NoSignedWrap > m_NSWAdd(const LHS &L, const RHS &R)
CmpClass_match< LHS, RHS, ICmpInst > m_ICmp(CmpPredicate &Pred, const LHS &L, const RHS &R)
BinaryOp_match< LHS, RHS, Instruction::Shl > m_Shl(const LHS &L, const RHS &R)
UAddWithOverflow_match< LHS_t, RHS_t, Sum_t > m_UAddWithOverflow(const LHS_t &L, const RHS_t &R, const Sum_t &S)
Match an icmp instruction checking for unsigned overflow on addition.
auto m_LogicalAnd()
Matches L && R where L and R are arbitrary values.
auto m_Undef()
Match an arbitrary undef constant.
BinaryOp_match< LHS, RHS, Instruction::Or, true > m_c_Or(const LHS &L, const RHS &R)
Matches an Or with LHS and RHS in either order.
ThreeOps_match< Val_t, Elt_t, Idx_t, Instruction::InsertElement > m_InsertElt(const Val_t &Val, const Elt_t &Elt, const Idx_t &Idx)
Matches InsertElementInst.
BinaryOp_match< LHS, RHS, Instruction::Sub > m_Sub(const LHS &L, const RHS &R)
match_combine_or< LTy, RTy > m_CombineOr(const LTy &L, const RTy &R)
Combine two pattern matchers matching L || R.
int compare(DigitsT LDigits, int16_t LScale, DigitsT RDigits, int16_t RScale)
Compare two scaled numbers.
@ CE
Windows NT (Windows on ARM)
initializer< Ty > init(const Ty &Val)
PointerTypeMap run(const Module &M)
Compute the PointerTypeMap for the module M.
@ Assume
Do not drop type tests (default).
@ User
could "use" a pointer
NodeAddr< PhiNode * > Phi
NodeAddr< UseNode * > Use
SmallVector< Node, 4 > NodeList
friend class Instruction
Iterator for Instructions in a `BasicBlock.
LLVM_ABI iterator begin() const
BaseReg
Stack frame base register. Bit 0 of FREInfo.Info.
This is an optimization pass for GlobalISel generic memory operations.
auto drop_begin(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the first N elements excluded.
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
FunctionAddr VTableAddr Value
std::enable_if_t< std::is_signed_v< T >, T > MulOverflow(T X, T Y, T &Result)
Multiply two signed integers, computing the two's complement truncated result, returning true if an o...
auto find(R &&Range, const T &Val)
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly.
LLVM_ABI bool RemoveRedundantDbgInstrs(BasicBlock *BB)
Try to remove redundant dbg.value instructions from given basic block.
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
auto size(R &&Range, std::enable_if_t< std::is_base_of< std::random_access_iterator_tag, typename std::iterator_traits< decltype(Range.begin())>::iterator_category >::value, void > *=nullptr)
Get the size of a range.
LLVM_ABI bool RecursivelyDeleteTriviallyDeadInstructions(Value *V, const TargetLibraryInfo *TLI=nullptr, MemorySSAUpdater *MSSAU=nullptr, std::function< void(Value *)> AboutToDeleteCallback=std::function< void(Value *)>())
If the specified value is a trivially dead instruction, delete it.
LLVM_ABI bool ConstantFoldTerminator(BasicBlock *BB, bool DeleteDeadConditions=false, const TargetLibraryInfo *TLI=nullptr, DomTreeUpdater *DTU=nullptr)
If a terminator instruction is predicated on a constant value, convert it into an unconditional branc...
LLVM_ABI void findDbgValues(Value *V, SmallVectorImpl< DbgVariableRecord * > &DbgVariableRecords)
Finds the dbg.values describing a value.
decltype(auto) dyn_cast(const From &Val)
dyn_cast<X> - Return the argument parameter cast to the specified type.
APInt operator*(APInt a, uint64_t RHS)
bool isAligned(Align Lhs, uint64_t SizeInBytes)
Checks that SizeInBytes is a multiple of the alignment.
LLVM_ABI void salvageDebugInfo(const MachineRegisterInfo &MRI, MachineInstr &MI)
Assuming the instruction MI is going to be deleted, attempt to salvage debug users of MI by writing t...
auto successors(const MachineBasicBlock *BB)
OuterAnalysisManagerProxy< ModuleAnalysisManager, Function > ModuleAnalysisManagerFunctionProxy
Provide the ModuleAnalysisManager to Function proxy.
LLVM_ABI ReturnInst * FoldReturnIntoUncondBranch(ReturnInst *RI, BasicBlock *BB, BasicBlock *Pred, DomTreeUpdater *DTU=nullptr)
This method duplicates the specified return instruction into a predecessor which ends in an unconditi...
bool operator!=(uint64_t V1, const APInt &V2)
constexpr from_range_t from_range
LLVM_ABI Instruction * SplitBlockAndInsertIfElse(Value *Cond, BasicBlock::iterator SplitBefore, bool Unreachable, MDNode *BranchWeights=nullptr, DomTreeUpdater *DTU=nullptr, LoopInfo *LI=nullptr, BasicBlock *ElseBlock=nullptr)
Similar to SplitBlockAndInsertIfThen, but the inserted block is on the false path of the branch.
void append_range(Container &C, Range &&R)
Wrapper function to append range R to container C.
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...
auto cast_or_null(const Y &Val)
LLVM_ABI void DeleteDeadBlock(BasicBlock *BB, DomTreeUpdater *DTU=nullptr, bool KeepOneInputPHIs=false)
Delete the specified block, which must have no predecessors.
LLVM_ABI void initializeCodeGenPrepareLegacyPassPass(PassRegistry &)
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 SplitIndirectBrCriticalEdges(Function &F, bool IgnoreBlocksWithoutPHI, BranchProbabilityInfo *BPI=nullptr, BlockFrequencyInfo *BFI=nullptr)
LLVM_ABI Value * simplifyInstruction(Instruction *I, const SimplifyQuery &Q)
See if we can compute a simplified version of this instruction.
LLVM_ABI Value * simplifyAddInst(Value *LHS, Value *RHS, bool IsNSW, bool IsNUW, const SimplifyQuery &Q)
Given operands for an Add, fold the result or return null.
auto dyn_cast_or_null(const Y &Val)
Align getKnownAlignment(Value *V, const DataLayout &DL, const Instruction *CxtI=nullptr, AssumptionCache *AC=nullptr, const DominatorTree *DT=nullptr)
Try to infer an alignment for the specified pointer.
void erase(Container &C, ValueType V)
Wrapper function to remove a value from a container:
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
LLVM_ABI bool isSplatValue(const Value *V, int Index=-1, unsigned Depth=0)
Return true if each element of the vector value V is poisoned or equal to every other non-poisoned el...
LLVM_ABI bool DeleteDeadPHIs(BasicBlock *BB, const TargetLibraryInfo *TLI=nullptr, MemorySSAUpdater *MSSAU=nullptr)
Examine each PHI in the given block and delete it if it is dead.
LLVM_ABI bool replaceAndRecursivelySimplify(Instruction *I, Value *SimpleV, const TargetLibraryInfo *TLI=nullptr, const DominatorTree *DT=nullptr, AssumptionCache *AC=nullptr, SmallSetVector< Instruction *, 8 > *UnsimplifiedUsers=nullptr)
Replace all uses of 'I' with 'SimpleV' and simplify the uses recursively.
auto reverse(ContainerTy &&C)
LLVM_ABI bool recognizeBSwapOrBitReverseIdiom(Instruction *I, bool MatchBSwaps, bool MatchBitReversals, SmallVectorImpl< Instruction * > &InsertedInsts)
Try to match a bswap or bitreverse idiom.
void sort(IteratorTy Start, IteratorTy End)
FPClassTest
Floating-point class tests, supported by 'is_fpclass' intrinsic.
LLVM_ABI void SplitBlockAndInsertIfThenElse(Value *Cond, BasicBlock::iterator SplitBefore, Instruction **ThenTerm, Instruction **ElseTerm, MDNode *BranchWeights=nullptr, DomTreeUpdater *DTU=nullptr, LoopInfo *LI=nullptr)
SplitBlockAndInsertIfThenElse is similar to SplitBlockAndInsertIfThen, but also creates the ElseBlock...
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
bool none_of(R &&Range, UnaryPredicate P)
Provide wrappers to std::none_of which take ranges instead of having to pass begin/end explicitly.
auto make_first_range(ContainerTy &&c)
Given a container of pairs, return a range over the first elements.
generic_gep_type_iterator<> gep_type_iterator
LLVM_ABI FunctionPass * createCodeGenPrepareLegacyPass()
createCodeGenPrepareLegacyPass - Transform the code to expose more pattern matching during instructio...
ISD::CondCode getFCmpCondCode(FCmpInst::Predicate Pred)
getFCmpCondCode - Return the ISD condition code corresponding to the given LLVM IR floating-point con...
LLVM_ABI bool VerifyLoopInfo
Enable verification of loop info.
class LLVM_GSL_OWNER SmallVector
Forward declaration of SmallVector so that calculateSmallVectorDefaultInlinedElements can reference s...
bool isa(const From &Val)
isa<X> - Return true if the parameter to the template is an instance of one of the template type argu...
LLVM_ATTRIBUTE_VISIBILITY_DEFAULT AnalysisKey InnerAnalysisManagerProxy< AnalysisManagerT, IRUnitT, ExtraArgTs... >::Key
LLVM_ABI bool isKnownNonZero(const Value *V, const SimplifyQuery &Q, unsigned Depth=0)
Return true if the given value is known to be non-zero when defined.
@ First
Helpers to iterate all locations in the MemoryEffectsBase class.
bool attributesPermitTailCall(const Function *F, const Instruction *I, const ReturnInst *Ret, const TargetLoweringBase &TLI, bool *AllowDifferingSizes=nullptr)
Test if given that the input instruction is in the tail call position, if there is an attribute misma...
IRBuilder(LLVMContext &, FolderTy, InserterTy, MDNode *, ArrayRef< OperandBundleDef >) -> IRBuilder< FolderTy, InserterTy >
LLVM_ABI bool MergeBlockIntoPredecessor(BasicBlock *BB, DomTreeUpdater *DTU=nullptr, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, MemoryDependenceResults *MemDep=nullptr, bool PredecessorWithTwoSuccessors=false, DominatorTree *DT=nullptr)
Attempts to merge a block into its predecessor, if possible.
@ Or
Bitwise or logical OR of integers.
@ Xor
Bitwise or logical XOR of integers.
@ And
Bitwise or logical AND of integers.
@ Sub
Subtraction of integers.
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 >
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.
bool bypassSlowDivision(BasicBlock *BB, const DenseMap< unsigned int, unsigned int > &BypassWidth)
This optimization identifies DIV instructions in a BB that can be profitably bypassed and carried out...
gep_type_iterator gep_type_begin(const User *GEP)
void erase_if(Container &C, UnaryPredicate P)
Provide a container algorithm similar to C++ Library Fundamentals v2's erase_if which is equivalent t...
auto predecessors(const MachineBasicBlock *BB)
iterator_range< pointer_iterator< WrappedIteratorT > > make_pointer_range(RangeT &&Range)
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
Align commonAlignment(Align A, uint64_t Offset)
Returns the alignment that satisfies both alignments.
bool pred_empty(const BasicBlock *BB)
std::enable_if_t< std::is_signed_v< T >, T > AddOverflow(T X, T Y, T &Result)
Add two signed integers, computing the two's complement truncated result, returning true if overflow ...
LLVM_ABI Instruction * SplitBlockAndInsertIfThen(Value *Cond, BasicBlock::iterator SplitBefore, bool Unreachable, MDNode *BranchWeights=nullptr, DomTreeUpdater *DTU=nullptr, LoopInfo *LI=nullptr, BasicBlock *ThenBlock=nullptr)
Split the containing block at the specified instruction - everything before SplitBefore stays in the ...
AnalysisManager< Function > FunctionAnalysisManager
Convenience typedef for the Function analysis manager.
LLVM_ABI BasicBlock * SplitEdge(BasicBlock *From, BasicBlock *To, DominatorTree *DT=nullptr, LoopInfo *LI=nullptr, MemorySSAUpdater *MSSAU=nullptr, const Twine &BBName="")
Split the edge connecting the specified blocks, and return the newly created basic block between From...
std::pair< Value *, FPClassTest > fcmpToClassTest(FCmpInst::Predicate Pred, const Function &F, Value *LHS, Value *RHS, bool LookThroughSrc=true)
Returns a pair of values, which if passed to llvm.is.fpclass, returns the same result as an fcmp with...
static auto filterDbgVars(iterator_range< simple_ilist< DbgRecord >::iterator > R)
Filter the DbgRecord range to DbgVariableRecord types only and downcast.
LLVM_ABI Value * simplifyURemInst(Value *LHS, Value *RHS, const SimplifyQuery &Q)
Given operands for a URem, fold the result or return null.
DenseMap< const Value *, Value * > ValueToValueMap
LLVM_ABI CGPassBuilderOption getCGPassBuilderOption()
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
This struct is a compact representation of a valid (non-zero power of two) alignment.
bool bitsGT(EVT VT) const
Return true if this has more bits than VT.
bool bitsLT(EVT VT) const
Return true if this has less bits than VT.
TypeSize getSizeInBits() const
Return the size of the specified value type in bits.
static LLVM_ABI EVT getEVT(Type *Ty, bool HandleUnknown=false)
Return the value type corresponding to the specified type.
MVT getSimpleVT() const
Return the SimpleValueType held in the specified simple EVT.
bool isRound() const
Return true if the size is a power-of-two number of bytes.
bool isInteger() const
Return true if this is an integer or a vector integer type.
This contains information for each constraint that we are lowering.