47#define DEBUG_TYPE "select-optimize"
50 "Number of select groups considered for conversion to branch");
52 "Number of select groups converted due to expensive cold operand");
54 "Number of select groups converted due to high-predictability");
56 "Number of select groups not converted due to unpredictability");
58 "Number of select groups not converted due to cold basic block");
60 "Number of select groups converted due to loop-level analysis");
61STATISTIC(NumSelectsConverted,
"Number of selects converted");
64 "cold-operand-threshold",
65 cl::desc(
"Maximum frequency of path for an operand to be considered cold."),
69 "cold-operand-max-cost-multiplier",
70 cl::desc(
"Maximum cost multiplier of TCC_expensive for the dependence "
71 "slice of a cold operand to be considered inexpensive."),
76 cl::desc(
"Gradient gain threshold (%)."),
81 cl::desc(
"Minimum gain per loop (in cycles) threshold."),
85 "select-opti-loop-relative-gain-threshold",
87 "Minimum relative gain per loop threshold (1/X). Defaults to 12.5%"),
92 cl::desc(
"Default mispredict rate (initialized to 25%)."));
97 cl::desc(
"Disable loop-level heuristics."));
101class SelectOptimizeImpl {
113 SelectOptimizeImpl() =
default;
139 if (isa<SelectInst>(I))
140 return SelectLike(I);
147 X->getType()->isIntegerTy(1))
148 return SelectLike(I);
150 return SelectLike(
nullptr);
163 Value *getCondition()
const {
164 if (
auto *Sel = dyn_cast<SelectInst>(I))
165 return Sel->getCondition();
167 if (
auto *BO = dyn_cast<BinaryOperator>(I)) {
184 Value *getTrueValue()
const {
185 if (
auto *Sel = dyn_cast<SelectInst>(I))
186 return Sel->getTrueValue();
189 if (isa<BinaryOperator>(I))
198 Value *getFalseValue()
const {
199 if (
auto *Sel = dyn_cast<SelectInst>(I))
200 return Sel->getFalseValue();
202 if (
auto *BO = dyn_cast<BinaryOperator>(I)) {
206 return BO->getOperand(1);
209 return BO->getOperand(0);
219 if (
auto *Sel = dyn_cast<SelectInst>(I))
220 if (
auto *I = dyn_cast<Instruction>(Sel->getTrueValue()))
221 return InstCostMap.
contains(I) ? InstCostMap[
I].NonPredCost
225 if (isa<BinaryOperator>(I))
226 if (
auto I = dyn_cast<Instruction>(getFalseValue()))
230 {TargetTransformInfo::OK_AnyValue,
231 TargetTransformInfo::OP_None},
232 {TTI::OK_UniformConstantValue, TTI::OP_PowerOf2});
233 return InstCostMap[
I].NonPredCost +
245 if (
auto *Sel = dyn_cast<SelectInst>(I))
246 if (
auto *I = dyn_cast<Instruction>(Sel->getFalseValue()))
247 return InstCostMap.
contains(I) ? InstCostMap[
I].NonPredCost
251 if (isa<BinaryOperator>(I))
252 if (
auto I = dyn_cast<Instruction>(getFalseValue()))
254 return InstCostMap[
I].NonPredCost;
274 void optimizeSelectsBase(
Function &
F, SelectGroups &ProfSIGroups);
275 void optimizeSelectsInnerLoops(
Function &
F, SelectGroups &ProfSIGroups);
279 void convertProfitableSIGroups(SelectGroups &ProfSIGroups);
282 void collectSelectGroups(
BasicBlock &BB, SelectGroups &SIGroups);
286 void findProfitableSIGroupsBase(SelectGroups &SIGroups,
287 SelectGroups &ProfSIGroups);
288 void findProfitableSIGroupsInnerLoops(
const Loop *L, SelectGroups &SIGroups,
289 SelectGroups &ProfSIGroups);
293 bool isConvertToBranchProfitableBase(
const SelectGroup &ASI);
298 bool hasExpensiveColdOperand(
const SelectGroup &ASI);
303 void getExclBackwardsSlice(
Instruction *
I, std::stack<Instruction *> &Slice,
307 bool isSelectHighlyPredictable(
const SelectLike SI);
311 bool checkLoopHeuristics(
const Loop *L,
const CostInfo LoopDepth[2]);
315 bool computeLoopCosts(
const Loop *L,
const SelectGroups &SIGroups,
321 getSImap(
const SelectGroups &SIGroups);
324 std::optional<uint64_t> computeInstCost(
const Instruction *
I);
327 Scaled64 getMispredictionCost(
const SelectLike SI,
const Scaled64 CondCost);
331 const SelectLike SI);
334 bool isSelectKindSupported(
const SelectLike SI);
338 SelectOptimizeImpl Impl;
348 return Impl.runOnFunction(
F, *
this);
365 SelectOptimizeImpl Impl(
TM);
366 return Impl.run(
F,
FAM);
369char SelectOptimize::ID = 0;
386 TSI =
TM->getSubtargetImpl(
F);
402 .getCachedResult<ProfileSummaryAnalysis>(*
F.getParent());
403 assert(PSI &&
"This pass requires module analysis pass `profile-summary`!");
412 TSchedModel.
init(TSI);
414 bool Changed = optimizeSelects(
F);
420 TSI =
TM->getSubtargetImpl(
F);
440 TSchedModel.
init(TSI);
446 return optimizeSelects(
F);
449bool SelectOptimizeImpl::optimizeSelects(
Function &
F) {
451 SelectGroups ProfSIGroups;
453 optimizeSelectsBase(
F, ProfSIGroups);
455 optimizeSelectsInnerLoops(
F, ProfSIGroups);
459 convertProfitableSIGroups(ProfSIGroups);
462 return !ProfSIGroups.empty();
465void SelectOptimizeImpl::optimizeSelectsBase(
Function &
F,
466 SelectGroups &ProfSIGroups) {
468 SelectGroups SIGroups;
472 if (L &&
L->isInnermost())
474 collectSelectGroups(BB, SIGroups);
478 findProfitableSIGroupsBase(SIGroups, ProfSIGroups);
481void SelectOptimizeImpl::optimizeSelectsInnerLoops(
Function &
F,
482 SelectGroups &ProfSIGroups) {
485 for (
unsigned long i = 0; i <
Loops.size(); ++i)
486 for (
Loop *ChildL :
Loops[i]->getSubLoops())
487 Loops.push_back(ChildL);
490 if (!
L->isInnermost())
493 SelectGroups SIGroups;
495 collectSelectGroups(*BB, SIGroups);
497 findProfitableSIGroupsInnerLoops(L, SIGroups, ProfSIGroups);
510 for (
SelectInst *DefSI = dyn_cast<SelectInst>(SI.getI());
511 DefSI !=
nullptr && Selects.
count(DefSI);
512 DefSI = dyn_cast<SelectInst>(V)) {
513 assert(DefSI->getCondition() == SI.getCondition() &&
514 "The condition of DefSI does not match with SI");
515 V = (isTrue ? DefSI->getTrueValue() : DefSI->getFalseValue());
518 if (isa<BinaryOperator>(SI.getI())) {
519 assert(SI.getI()->getOpcode() == Instruction::Or &&
520 "Only currently handling Or instructions.");
521 V = SI.getFalseValue();
523 V = IB.CreateOr(V, ConstantInt::get(V->getType(), 1));
526 assert(V &&
"Failed to get select true/false value");
530void SelectOptimizeImpl::convertProfitableSIGroups(SelectGroups &ProfSIGroups) {
531 for (SelectGroup &ASI : ProfSIGroups) {
571 typedef std::stack<Instruction *>::size_type StackSizeType;
572 StackSizeType maxTrueSliceLen = 0, maxFalseSliceLen = 0;
573 for (SelectLike SI : ASI) {
576 if (
auto *TI = dyn_cast_or_null<Instruction>(
SI.getTrueValue())) {
577 std::stack<Instruction *> TrueSlice;
578 getExclBackwardsSlice(TI, TrueSlice,
SI.getI(),
true);
579 maxTrueSliceLen = std::max(maxTrueSliceLen, TrueSlice.size());
582 if (
auto *FI = dyn_cast_or_null<Instruction>(
SI.getFalseValue())) {
583 if (isa<SelectInst>(
SI.getI()) || !FI->hasOneUse()) {
584 std::stack<Instruction *> FalseSlice;
585 getExclBackwardsSlice(FI, FalseSlice,
SI.getI(),
true);
586 maxFalseSliceLen = std::max(maxFalseSliceLen, FalseSlice.size());
602 for (StackSizeType IS = 0; IS < maxTrueSliceLen; ++IS) {
603 for (
auto &S : TrueSlices) {
605 TrueSlicesInterleaved.
push_back(S.top());
610 for (StackSizeType IS = 0; IS < maxFalseSliceLen; ++IS) {
611 for (
auto &S : FalseSlices) {
613 FalseSlicesInterleaved.
push_back(S.top());
620 SelectLike
SI = ASI.front();
621 SelectLike LastSI = ASI.back();
629 SplitPt.setHeadBit(
true);
631 BFI->setBlockFreq(EndBlock,
BFI->getBlockFreq(StartBlock));
638 auto DIt =
SI.getI()->getIterator();
639 while (&*DIt != LastSI.getI()) {
640 if (DIt->isDebugOrPseudoInst())
644 for (
auto *DI : DebugPseudoINS) {
663 std::next(LastSI.getI()->getIterator()));
668 BasicBlock *TrueBlock =
nullptr, *FalseBlock =
nullptr;
669 BranchInst *TrueBranch =
nullptr, *FalseBranch =
nullptr;
670 if (!TrueSlicesInterleaved.
empty()) {
674 TrueBranch->
setDebugLoc(LastSI.getI()->getDebugLoc());
675 for (
Instruction *TrueInst : TrueSlicesInterleaved)
676 TrueInst->moveBefore(TrueBranch);
678 if (!FalseSlicesInterleaved.
empty()) {
683 FalseBranch->setDebugLoc(LastSI.getI()->getDebugLoc());
684 for (
Instruction *FalseInst : FalseSlicesInterleaved)
685 FalseInst->moveBefore(FalseBranch);
689 if (TrueBlock == FalseBlock) {
690 assert(TrueBlock ==
nullptr &&
691 "Unexpected basic block transform while optimizing select");
696 FalseBranch->setDebugLoc(
SI.getI()->getDebugLoc());
705 if (TrueBlock ==
nullptr) {
708 TrueBlock = StartBlock;
709 }
else if (FalseBlock ==
nullptr) {
712 FalseBlock = StartBlock;
718 auto *CondFr =
IB.CreateFreeze(
SI.getCondition(),
719 SI.getCondition()->getName() +
".frozen");
728 for (
auto It = ASI.rbegin(); It != ASI.rend(); ++It) {
737 SI.getI()->replaceAllUsesWith(PN);
739 ++NumSelectsConverted;
741 IB.CreateCondBr(CondFr, TT, FT,
SI.getI());
745 SI.getI()->eraseFromParent();
749void SelectOptimizeImpl::collectSelectGroups(
BasicBlock &BB,
750 SelectGroups &SIGroups) {
752 while (BBIt != BB.
end()) {
754 if (SelectLike SI = SelectLike::match(
I)) {
759 SIGroup.push_back(SI);
760 while (BBIt != BB.
end()) {
770 if (!isa<SelectInst>(NI))
773 SelectLike NSI = SelectLike::match(NI);
774 if (NSI &&
SI.getCondition() == NSI.getCondition()) {
775 SIGroup.push_back(NSI);
783 if (!isSelectKindSupported(SI))
786 SIGroups.push_back(SIGroup);
791void SelectOptimizeImpl::findProfitableSIGroupsBase(
792 SelectGroups &SIGroups, SelectGroups &ProfSIGroups) {
793 for (SelectGroup &ASI : SIGroups) {
794 ++NumSelectOptAnalyzed;
795 if (isConvertToBranchProfitableBase(ASI))
796 ProfSIGroups.push_back(ASI);
806void SelectOptimizeImpl::findProfitableSIGroupsInnerLoops(
807 const Loop *L, SelectGroups &SIGroups, SelectGroups &ProfSIGroups) {
808 NumSelectOptAnalyzed += SIGroups.size();
822 if (!computeLoopCosts(L, SIGroups, InstCostMap, LoopCost) ||
823 !checkLoopHeuristics(L, LoopCost)) {
827 for (SelectGroup &ASI : SIGroups) {
831 for (SelectLike SI : ASI) {
832 SelectCost = std::max(SelectCost, InstCostMap[
SI.getI()].PredCost);
833 BranchCost = std::max(BranchCost, InstCostMap[
SI.getI()].NonPredCost);
835 if (BranchCost < SelectCost) {
837 OR <<
"Profitable to convert to branch (loop analysis). BranchCost="
838 << BranchCost.toString() <<
", SelectCost=" << SelectCost.
toString()
841 ++NumSelectConvertedLoop;
842 ProfSIGroups.push_back(ASI);
846 ORmiss <<
"Select is more profitable (loop analysis). BranchCost="
847 << BranchCost.toString()
848 <<
", SelectCost=" << SelectCost.
toString() <<
". ";
854bool SelectOptimizeImpl::isConvertToBranchProfitableBase(
855 const SelectGroup &ASI) {
856 SelectLike
SI = ASI.front();
865 ORmiss <<
"Not converted to branch because of cold basic block. ";
871 if (
SI.getI()->getMetadata(LLVMContext::MD_unpredictable)) {
873 ORmiss <<
"Not converted to branch because of unpredictable branch. ";
881 ++NumSelectConvertedHighPred;
882 OR <<
"Converted to branch because of highly predictable branch. ";
889 if (hasExpensiveColdOperand(ASI)) {
890 ++NumSelectConvertedExpColdOperand;
891 OR <<
"Converted to branch because of expensive cold operand.";
896 ORmiss <<
"Not profitable to convert to branch (base heuristic).";
903 return (Numerator + (Denominator / 2)) / Denominator;
908 if (isa<SelectInst>(SI.getI()))
913bool SelectOptimizeImpl::hasExpensiveColdOperand(
const SelectGroup &ASI) {
914 bool ColdOperand =
false;
915 uint64_t TrueWeight, FalseWeight, TotalWeight;
917 uint64_t MinWeight = std::min(TrueWeight, FalseWeight);
918 TotalWeight = TrueWeight + FalseWeight;
924 ORmiss <<
"Profile data available but missing branch-weights metadata for "
925 "select instruction. ";
932 for (SelectLike SI : ASI) {
935 if (TrueWeight < FalseWeight) {
936 ColdI = dyn_cast_or_null<Instruction>(
SI.getTrueValue());
937 HotWeight = FalseWeight;
939 ColdI = dyn_cast_or_null<Instruction>(
SI.getFalseValue());
940 HotWeight = TrueWeight;
943 std::stack<Instruction *> ColdSlice;
944 getExclBackwardsSlice(ColdI, ColdSlice,
SI.getI());
946 while (!ColdSlice.empty()) {
970 if (LoadI->
getParent() != SI->getParent())
974 if (It->mayWriteToMemory())
987void SelectOptimizeImpl::getExclBackwardsSlice(
Instruction *
I,
988 std::stack<Instruction *> &Slice,
992 std::queue<Instruction *> Worklist;
994 while (!Worklist.empty()) {
999 if (!Visited.
insert(II).second)
1009 isa<SelectInst>(II) || isa<PHINode>(II)))
1021 if (
BFI->getBlockFreq(II->
getParent()) <
BFI->getBlockFreq(
I->getParent()))
1029 if (
auto *OpI = dyn_cast<Instruction>(II->
getOperand(k)))
1034bool SelectOptimizeImpl::isSelectHighlyPredictable(
const SelectLike SI) {
1038 uint64_t Sum = TrueWeight + FalseWeight;
1048bool SelectOptimizeImpl::checkLoopHeuristics(
const Loop *L,
1049 const CostInfo LoopCost[2]) {
1057 L->getHeader()->getFirstNonPHI());
1059 if (LoopCost[0].NonPredCost > LoopCost[0].PredCost ||
1060 LoopCost[1].NonPredCost >= LoopCost[1].PredCost) {
1061 ORmissL <<
"No select conversion in the loop due to no reduction of loop's "
1067 Scaled64 Gain[2] = {LoopCost[0].PredCost - LoopCost[0].NonPredCost,
1068 LoopCost[1].PredCost - LoopCost[1].NonPredCost};
1076 ORmissL <<
"No select conversion in the loop due to small reduction of "
1077 "loop's critical path. Gain="
1079 <<
", RelativeGain=" << RelativeGain.
toString() <<
"%. ";
1089 if (Gain[1] > Gain[0]) {
1091 (LoopCost[1].PredCost - LoopCost[0].PredCost);
1093 ORmissL <<
"No select conversion in the loop due to small gradient gain. "
1095 << GradientGain.
toString() <<
"%. ";
1101 else if (Gain[1] < Gain[0]) {
1103 <<
"No select conversion in the loop due to negative gradient gain. ";
1117bool SelectOptimizeImpl::computeLoopCosts(
1118 const Loop *L,
const SelectGroups &SIGroups,
1120 LLVM_DEBUG(
dbgs() <<
"Calculating Latency / IPredCost / INonPredCost of loop "
1121 <<
L->getHeader()->getName() <<
"\n");
1122 const auto &SImap = getSImap(SIGroups);
1125 const unsigned Iterations = 2;
1126 for (
unsigned Iter = 0; Iter < Iterations; ++Iter) {
1128 CostInfo &MaxCost = LoopCost[Iter];
1131 if (
I.isDebugOrPseudoInst())
1140 for (
const Use &U :
I.operands()) {
1141 auto UI = dyn_cast<Instruction>(
U.get());
1144 if (InstCostMap.
count(UI)) {
1145 IPredCost = std::max(IPredCost, InstCostMap[UI].PredCost);
1146 INonPredCost = std::max(INonPredCost, InstCostMap[UI].NonPredCost);
1149 auto ILatency = computeInstCost(&
I);
1152 ORmissL <<
"Invalid instruction cost preventing analysis and "
1153 "optimization of the inner-most loop containing this "
1167 if (SImap.contains(&
I)) {
1168 auto SI = SImap.at(&
I);
1172 getPredictedPathCost(TrueOpCost, FalseOpCost, SI);
1175 if (
auto *CI = dyn_cast<Instruction>(
SI.getCondition()))
1176 if (InstCostMap.
count(CI))
1177 CondCost = InstCostMap[CI].NonPredCost;
1178 Scaled64 MispredictCost = getMispredictionCost(SI, CondCost);
1180 INonPredCost = PredictedPathCost + MispredictCost;
1183 << INonPredCost <<
" for " <<
I <<
"\n");
1185 InstCostMap[&
I] = {IPredCost, INonPredCost};
1186 MaxCost.PredCost = std::max(MaxCost.PredCost, IPredCost);
1187 MaxCost.NonPredCost = std::max(MaxCost.NonPredCost, INonPredCost);
1191 <<
" MaxCost = " << MaxCost.PredCost <<
" "
1192 << MaxCost.NonPredCost <<
"\n");
1198SelectOptimizeImpl::getSImap(
const SelectGroups &SIGroups) {
1200 for (
const SelectGroup &ASI : SIGroups)
1201 for (SelectLike SI : ASI)
1206std::optional<uint64_t>
1207SelectOptimizeImpl::computeInstCost(
const Instruction *
I) {
1211 return std::optional<uint64_t>(*OC);
1212 return std::nullopt;
1216SelectOptimizeImpl::getMispredictionCost(
const SelectLike SI,
1225 if (isSelectHighlyPredictable(SI))
1236 return MispredictCost;
1242SelectOptimizeImpl::getPredictedPathCost(
Scaled64 TrueCost,
Scaled64 FalseCost,
1243 const SelectLike SI) {
1247 uint64_t SumWeight = TrueWeight + FalseWeight;
1248 if (SumWeight != 0) {
1252 return PredPathCost;
1257 PredPathCost = std::max(TrueCost *
Scaled64::get(3) + FalseCost,
1260 return PredPathCost;
1263bool SelectOptimizeImpl::isSelectKindSupported(
const SelectLike SI) {
1264 bool VectorCond = !
SI.getCondition()->getType()->isIntegerTy(1);
1268 if (
SI.getType()->isVectorTy())
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 bool runOnFunction(Function &F, bool PostInlining)
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
FunctionAnalysisManager FAM
const char LLVMTargetMachineRef TM
#define INITIALIZE_PASS_DEPENDENCY(depName)
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
This file contains the declarations for profiling metadata utility functions.
static bool isValid(const char C)
Returns true if C is a valid mangled character: <0-9a-zA-Z_>.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
static bool isSafeToSinkLoad(Instruction *LoadI, Instruction *SI)
static cl::opt< unsigned > ColdOperandMaxCostMultiplier("cold-operand-max-cost-multiplier", cl::desc("Maximum cost multiplier of TCC_expensive for the dependence " "slice of a cold operand to be considered inexpensive."), cl::init(1), cl::Hidden)
static cl::opt< unsigned > ColdOperandThreshold("cold-operand-threshold", cl::desc("Maximum frequency of path for an operand to be considered cold."), cl::init(20), cl::Hidden)
static cl::opt< bool > DisableLoopLevelHeuristics("disable-loop-level-heuristics", cl::Hidden, cl::init(false), cl::desc("Disable loop-level heuristics."))
static cl::opt< unsigned > GainCycleThreshold("select-opti-loop-cycle-gain-threshold", cl::desc("Minimum gain per loop (in cycles) threshold."), cl::init(4), cl::Hidden)
static cl::opt< unsigned > MispredictDefaultRate("mispredict-default-rate", cl::Hidden, cl::init(25), cl::desc("Default mispredict rate (initialized to 25%)."))
static void EmitAndPrintRemark(OptimizationRemarkEmitter *ORE, DiagnosticInfoOptimizationBase &Rem)
static cl::opt< unsigned > GainGradientThreshold("select-opti-loop-gradient-gain-threshold", cl::desc("Gradient gain threshold (%)."), cl::init(25), cl::Hidden)
static cl::opt< unsigned > GainRelativeThreshold("select-opti-loop-relative-gain-threshold", cl::desc("Minimum relative gain per loop threshold (1/X). Defaults to 12.5%"), cl::init(8), cl::Hidden)
This file contains the declaration of the SelectOptimizePass class, its corresponding pass name is se...
This file defines the SmallVector class.
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
static SymbolRef::Type getType(const Symbol *Sym)
This file describes how to lower LLVM code to machine code.
Target-Independent Code Generator Pass Configuration Options pass.
A container for analyses that lazily runs them and caches their results.
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Represent the analysis usage information of a pass.
AnalysisUsage & addRequired()
LLVM Basic Block Representation.
iterator begin()
Instruction iterator methods.
const_iterator getFirstInsertionPt() const
Returns an iterator to the first instruction in this block that is suitable for inserting a non-PHI i...
void insertDbgRecordBefore(DbgRecord *DR, InstListType::iterator Here)
Insert a DbgRecord into a block at the position given by Here.
static BasicBlock * Create(LLVMContext &Context, const Twine &Name="", Function *Parent=nullptr, BasicBlock *InsertBefore=nullptr)
Creates a new BasicBlock.
BasicBlock * splitBasicBlock(iterator I, const Twine &BBName="", bool Before=false)
Split the basic block into two basic blocks at the specified instruction.
const Function * getParent() const
Return the enclosing method, or null if none.
InstListType::iterator iterator
Instruction iterators...
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...
Analysis pass which computes BlockFrequencyInfo.
Legacy analysis pass which computes BlockFrequencyInfo.
BlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate IR basic block frequen...
Conditional or Unconditional Branch instruction.
static BranchInst * Create(BasicBlock *IfTrue, BasicBlock::iterator InsertBefore)
static BranchProbability getBranchProbability(uint64_t Numerator, uint64_t Denominator)
Base class for non-instruction debug metadata records that have positions within IR.
std::pair< iterator, bool > try_emplace(KeyT &&Key, Ts &&... Args)
size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
bool contains(const_arg_type_t< KeyT > Val) const
Return true if the specified key is in the map, false otherwise.
Common features for diagnostics dealing with optimization remarks that are used by both IR and MIR pa...
std::string getMsg() const
FunctionPass class - This class is used to implement most global optimizations.
virtual bool runOnFunction(Function &F)=0
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass.
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
std::optional< CostType > getValue() const
This function is intended to be used as sparingly as possible, since the class provides the full rang...
bool isDebugOrPseudoInst() const LLVM_READONLY
Return true if the instruction is a DbgInfoIntrinsic or PseudoProbeInst.
void insertBefore(Instruction *InsertPos)
Insert an unlinked instruction into a basic block immediately before the specified instruction.
const BasicBlock * getParent() const
InstListType::iterator eraseFromParent()
This method unlinks 'this' from the containing basic block and deletes it.
bool mayHaveSideEffects() const LLVM_READONLY
Return true if the instruction may have side effects.
bool isTerminator() const
bool mayReadFromMemory() const LLVM_READONLY
Return true if this instruction may read memory.
void setDebugLoc(DebugLoc Loc)
Set the debug location information for this instruction.
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.
An analysis over an "inner" IR unit that provides access to an analysis manager over a "outer" IR uni...
void addIncoming(Value *V, BasicBlock *BB)
Add an incoming value to the end of the PHI list.
static PHINode * Create(Type *Ty, unsigned NumReservedValues, const Twine &NameStr, BasicBlock::iterator InsertBefore)
Constructors - NumReservedValues is a hint for the number of incoming edges that this phi node will h...
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Pass interface - Implemented by all 'passes'.
virtual void getAnalysisUsage(AnalysisUsage &) const
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
A set of analyses that are preserved following a run of a transformation pass.
static PreservedAnalyses none()
Convenience factory function for the empty preserved set.
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
An analysis pass based on legacy pass manager to deliver ProfileSummaryInfo.
Analysis providing profile information.
bool hasProfileSummary() const
Returns true if profile summary is available.
bool isColdBlock(const BBType *BB, BFIT *BFI) const
Returns true if BasicBlock BB is considered cold.
std::string toString(unsigned Precision=DefaultPrecision)
Convert to a decimal representation in a string.
static ScaledNumber get(uint64_t N)
static ScaledNumber getZero()
This class represents the LLVM 'select' instruction.
PreservedAnalyses run(Function &F, FunctionAnalysisManager &FAM)
bool erase(PtrType Ptr)
erase - If the set contains the specified pointer, remove it and return true, otherwise return false.
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
void push_back(const T &Elt)
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Analysis pass providing the TargetTransformInfo.
virtual bool isSelectSupported(SelectSupportKind) const
SelectSupportKind
Enum that describes what type of support for selects the target has.
bool isPredictableSelectExpensive() const
Return true if selects are only cheaper than branches if the branch is unlikely to be predicted right...
This class defines information used to lower LLVM code to legal SelectionDAG operators that the targe...
Primary interface to the complete machine description for the target machine.
Target-Independent Code Generator Pass Configuration Options.
Provide an instruction scheduling machine model to CodeGen passes.
const MCSchedModel * getMCSchedModel() const
void init(const TargetSubtargetInfo *TSInfo)
Initialize the machine model for instruction scheduling.
TargetSubtargetInfo - Generic base class for all target subtargets.
virtual const TargetLowering * getTargetLowering() const
The instances of the Type class are immutable: once they are created, they are never changed.
A Use represents the edge between a Value definition and its users.
Value * getOperand(unsigned i) const
unsigned getNumOperands() const
LLVM Value Representation.
bool hasOneUse() const
Return true if there is exactly one use of this value.
void takeName(Value *V)
Transfer the name from V to this value.
self_iterator getIterator()
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
bool match(Val *V, const Pattern &P)
OneUse_match< T > m_OneUse(const T &SubPattern)
CastInst_match< OpTy, ZExtInst > m_ZExt(const OpTy &Op)
Matches ZExt.
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
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.
initializer< Ty > init(const Ty &Val)
PointerTypeMap run(const Module &M)
Compute the PointerTypeMap for the module M.
This is an optimization pass for GlobalISel generic memory operations.
UnaryFunction for_each(R &&Range, UnaryFunction F)
Provide wrappers to std::for_each which take ranges instead of having to pass begin/end explicitly.
FunctionPass * createSelectOptimizePass()
This pass converts conditional moves to conditional jumps when profitable.
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
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...
uint64_t divideNearest(uint64_t Numerator, uint64_t Denominator)
Returns the integer nearest(Numerator / Denominator).
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
bool extractBranchWeights(const MDNode *ProfileData, SmallVectorImpl< uint32_t > &Weights)
Extract branch weights from MD_prof metadata.
void initializeSelectOptimizePass(PassRegistry &)
unsigned MispredictPenalty