Go to the documentation of this file.
50 #define DEBUG_TYPE "branch-prob"
54 cl::desc(
"Print the branch probability info."));
58 cl::desc(
"The option to specify the name of the function "
59 "whose branch probability info is printed."));
62 "Branch Probability Analysis",
false,
true)
224 const std::vector<const BasicBlock *> &Scc = *It;
229 for (
const auto *
BB : Scc) {
231 SccNums[
BB] = SccNum;
232 calculateSccBlockType(
BB, SccNum);
239 auto SccIt = SccNums.find(
BB);
240 if (SccIt == SccNums.end())
242 return SccIt->second;
248 for (
auto MapIt : SccBlocks[SccNum]) {
249 const auto *
BB = MapIt.first;
250 if (isSCCHeader(
BB, SccNum))
252 if (getSCCNum(Pred) != SccNum)
259 for (
auto MapIt : SccBlocks[SccNum]) {
260 const auto *
BB = MapIt.first;
261 if (isSCCExitingBlock(
BB, SccNum))
263 if (getSCCNum(Succ) != SccNum)
264 Exits.push_back(
const_cast<BasicBlock *
>(Succ));
272 assert(SccBlocks.size() >
static_cast<unsigned>(SccNum) &&
"Unknown SCC");
273 const auto &SccBlockTypes = SccBlocks[SccNum];
275 auto It = SccBlockTypes.find(
BB);
276 if (It != SccBlockTypes.end()) {
282 void BranchProbabilityInfo::SccInfo::calculateSccBlockType(
const BasicBlock *
BB,
290 return getSCCNum(Pred) != SccNum;
295 return getSCCNum(Succ) != SccNum;
301 if (SccBlocks.size() <=
static_cast<unsigned>(SccNum))
302 SccBlocks.resize(SccNum + 1);
303 auto &SccBlockTypes = SccBlocks[SccNum];
307 std::tie(std::ignore, IsInserted) =
308 SccBlockTypes.insert(std::make_pair(
BB,
BlockType));
309 assert(IsInserted &&
"Duplicated block in SCC");
313 BranchProbabilityInfo::LoopBlock::LoopBlock(
const BasicBlock *
BB,
319 LD.second = SccI.getSCCNum(
BB);
323 bool BranchProbabilityInfo::isLoopEnteringEdge(
const LoopEdge &Edge)
const {
324 const auto &SrcBlock = Edge.first;
325 const auto &DstBlock = Edge.second;
326 return (DstBlock.getLoop() &&
327 !DstBlock.getLoop()->contains(SrcBlock.getLoop())) ||
329 (DstBlock.getSccNum() != -1 &&
330 SrcBlock.getSccNum() != DstBlock.getSccNum());
333 bool BranchProbabilityInfo::isLoopExitingEdge(
const LoopEdge &Edge)
const {
334 return isLoopEnteringEdge({Edge.second, Edge.first});
337 bool BranchProbabilityInfo::isLoopEnteringExitingEdge(
338 const LoopEdge &Edge)
const {
339 return isLoopEnteringEdge(Edge) || isLoopExitingEdge(Edge);
342 bool BranchProbabilityInfo::isLoopBackEdge(
const LoopEdge &Edge)
const {
343 const auto &SrcBlock = Edge.first;
344 const auto &DstBlock = Edge.second;
345 return SrcBlock.belongsToSameLoop(DstBlock) &&
346 ((DstBlock.getLoop() &&
347 DstBlock.getLoop()->getHeader() == DstBlock.getBlock()) ||
348 (DstBlock.getSccNum() != -1 &&
349 SccI->isSCCHeader(DstBlock.getBlock(), DstBlock.getSccNum())));
352 void BranchProbabilityInfo::getLoopEnterBlocks(
355 auto *Header = LB.getLoop()->getHeader();
358 assert(LB.getSccNum() != -1 &&
"LB doesn't belong to any loop?");
359 SccI->getSccEnterBlocks(LB.getSccNum(), Enters);
363 void BranchProbabilityInfo::getLoopExitBlocks(
366 LB.getLoop()->getExitBlocks(Exits);
368 assert(LB.getSccNum() != -1 &&
"LB doesn't belong to any loop?");
369 SccI->getSccExitBlocks(LB.getSccNum(), Exits);
377 bool BranchProbabilityInfo::calcMetadataWeights(
const BasicBlock *
BB) {
380 if (!(isa<BranchInst>(TI) || isa<SwitchInst>(TI) || isa<IndirectBrInst>(TI) ||
381 isa<InvokeInst>(TI)))
406 mdconst::dyn_extract<ConstantInt>(WeightsNode->
getOperand(
I));
410 "Too many bits for uint32_t");
412 WeightSum += Weights.back();
413 const LoopBlock SrcLoopBB = getLoopBlock(
BB);
414 const LoopBlock DstLoopBB = getLoopBlock(TI->
getSuccessor(
I - 1));
415 auto EstimatedWeight = getEstimatedEdgeWeight({SrcLoopBB, DstLoopBB});
416 if (EstimatedWeight &&
417 EstimatedWeight.getValue() <=
419 UnreachableIdxs.push_back(
I - 1);
421 ReachableIdxs.push_back(
I - 1);
428 (WeightSum > UINT32_MAX) ? WeightSum / UINT32_MAX + 1 : 1;
430 if (ScalingFactor > 1) {
433 Weights[
I] /= ScalingFactor;
434 WeightSum += Weights[
I];
437 assert(WeightSum <= UINT32_MAX &&
438 "Expected weights to scale down to 32 bits");
440 if (WeightSum == 0 || ReachableIdxs.size() == 0) {
449 BP.push_back({ Weights[
I],
static_cast<uint32_t>(WeightSum) });
453 if (UnreachableIdxs.size() == 0 || ReachableIdxs.size() == 0) {
459 for (
auto I : UnreachableIdxs)
460 if (UnreachableProb < BP[
I]) {
461 BP[
I] = UnreachableProb;
485 for (
auto I : UnreachableIdxs)
486 NewUnreachableSum += BP[
I];
492 for (
auto I : ReachableIdxs)
493 OldReachableSum += BP[
I];
495 if (OldReachableSum != NewReachableSum) {
496 if (OldReachableSum.
isZero()) {
501 for (
auto I : ReachableIdxs)
504 for (
auto I : ReachableIdxs) {
510 BP[
I].getNumerator();
525 bool BranchProbabilityInfo::calcPointerHeuristics(
const BasicBlock *
BB) {
526 const BranchInst *BI = dyn_cast<BranchInst>(
BB->getTerminator());
576 const BranchInst *BI = dyn_cast<BranchInst>(
BB->getTerminator());
582 if (!CI || !isa<Instruction>(CI->
getOperand(0)) ||
590 PHINode *CmpPHI = dyn_cast<PHINode>(CmpLHS);
594 while (!CmpPHI && CmpLHS && isa<BinaryOperator>(CmpLHS) &&
599 InstChain.push_back(cast<BinaryOperator>(CmpLHS));
600 CmpLHS = dyn_cast<Instruction>(CmpLHS->
getOperand(0));
602 CmpPHI = dyn_cast<PHINode>(CmpLHS);
604 if (!CmpPHI || !L->
contains(CmpPHI))
610 WorkList.push_back(CmpPHI);
611 VisitedInsts.
insert(CmpPHI);
612 while (!WorkList.empty()) {
618 Value *V =
P->getIncomingValueForBlock(
B);
621 if (
PHINode *PN = dyn_cast<PHINode>(V)) {
622 if (VisitedInsts.
insert(PN).second)
623 WorkList.push_back(PN);
629 Constant *CmpLHSConst = dyn_cast<Constant>(V);
635 cast<Constant>(
I->getOperand(1)),
true);
643 CmpLHSConst, CmpConst,
true);
655 BranchProbabilityInfo::getEstimatedBlockWeight(
const BasicBlock *
BB)
const {
656 auto WeightIt = EstimatedBlockWeight.find(
BB);
657 if (WeightIt == EstimatedBlockWeight.end())
659 return WeightIt->second;
663 BranchProbabilityInfo::getEstimatedLoopWeight(
const LoopData &L)
const {
664 auto WeightIt = EstimatedLoopWeight.
find(L);
665 if (WeightIt == EstimatedLoopWeight.
end())
667 return WeightIt->second;
671 BranchProbabilityInfo::getEstimatedEdgeWeight(
const LoopEdge &Edge)
const {
674 return isLoopEnteringEdge(Edge)
675 ? getEstimatedLoopWeight(Edge.second.getLoopData())
676 : getEstimatedBlockWeight(Edge.second.getBlock());
679 template <
class IterT>
685 const LoopBlock DstLoopBB = getLoopBlock(DstBB);
686 auto Weight = getEstimatedEdgeWeight({SrcLoopBB, DstLoopBB});
703 bool BranchProbabilityInfo::updateEstimatedBlockWeight(
704 LoopBlock &LoopBB,
uint32_t BBWeight,
714 if (!EstimatedBlockWeight.insert({BB, BBWeight}).second)
718 LoopBlock PredLoop = getLoopBlock(PredBlock);
720 if (isLoopExitingEdge({PredLoop, LoopBB})) {
721 if (!EstimatedLoopWeight.
count(PredLoop.getLoopData()))
722 LoopWorkList.push_back(PredLoop);
723 }
else if (!EstimatedBlockWeight.count(PredBlock))
724 BlockWorkList.push_back(PredBlock);
741 void BranchProbabilityInfo::propagateEstimatedBlockWeight(
746 const auto *DTStartNode = DT->
getNode(
BB);
747 const auto *PDTStartNode = PDT->
getNode(
BB);
750 for (
const auto *DTNode = DTStartNode; DTNode !=
nullptr;
751 DTNode = DTNode->getIDom()) {
752 auto *DomBB = DTNode->getBlock();
759 LoopBlock DomLoopBB = getLoopBlock(DomBB);
760 const LoopEdge Edge{DomLoopBB, LoopBB};
762 if (!isLoopEnteringExitingEdge(Edge)) {
763 if (!updateEstimatedBlockWeight(DomLoopBB, BBWeight, BlockWorkList,
768 }
else if (isLoopExitingEdge(Edge)) {
769 LoopWorkList.push_back(DomLoopBB);
779 if (
const CallInst *CI = dyn_cast<CallInst>(&
I))
780 if (CI->hasFnAttr(Attribute::NoReturn))
789 if (isa<UnreachableInst>(
BB->getTerminator()) ||
794 BB->getTerminatingDeoptimizeCall())
795 return hasNoReturn(
BB)
802 if (
const auto *II = dyn_cast<InvokeInst>(Pred->
getTerminator()))
803 if (II->getUnwindDest() ==
BB)
807 for (
const auto &
I : *
BB)
808 if (
const CallInst *CI = dyn_cast<CallInst>(&
I))
818 void BranchProbabilityInfo::computeEestimateBlockWeight(
826 for (
const auto *
BB : RPOT)
827 if (
auto BBWeight = getInitialEstimatedBlockWeight(
BB))
830 propagateEstimatedBlockWeight(getLoopBlock(
BB), DT, PDT,
831 BBWeight.getValue(), BlockWorkList,
839 while (!LoopWorkList.empty()) {
842 if (EstimatedLoopWeight.
count(LoopBB.getLoopData()))
846 getLoopExitBlocks(LoopBB, Exits);
847 auto LoopWeight = getMaxEstimatedEdgeWeight(
848 LoopBB,
make_range(Exits.begin(), Exits.end()));
855 EstimatedLoopWeight.
insert(
856 {LoopBB.getLoopData(), LoopWeight.getValue()});
858 getLoopEnterBlocks(LoopBB, BlockWorkList);
862 while (!BlockWorkList.empty()) {
865 if (EstimatedBlockWeight.count(
BB))
874 const LoopBlock LoopBB = getLoopBlock(
BB);
875 auto MaxWeight = getMaxEstimatedEdgeWeight(LoopBB,
successors(
BB));
878 propagateEstimatedBlockWeight(LoopBB, DT, PDT, MaxWeight.
getValue(),
879 BlockWorkList, LoopWorkList);
881 }
while (!BlockWorkList.empty() || !LoopWorkList.empty());
887 bool BranchProbabilityInfo::calcEstimatedHeuristics(
const BasicBlock *
BB) {
888 assert(
BB->getTerminator()->getNumSuccessors() > 1 &&
889 "expected more than one successor!");
891 const LoopBlock LoopBB = getLoopBlock(
BB);
895 if (LoopBB.getLoop())
899 bool FoundEstimatedWeight =
false;
905 const LoopBlock SuccLoopBB = getLoopBlock(SuccBB);
906 const LoopEdge Edge{LoopBB, SuccLoopBB};
908 Weight = getEstimatedEdgeWeight(Edge);
910 if (isLoopExitingEdge(Edge) &&
919 bool IsUnlikelyEdge = LoopBB.getLoop() && UnlikelyBlocks.
contains(SuccBB);
920 if (IsUnlikelyEdge &&
931 FoundEstimatedWeight =
true;
935 TotalWeight += WeightVal;
936 SuccWeights.push_back(WeightVal);
942 if (!FoundEstimatedWeight || TotalWeight == 0)
946 const unsigned SuccCount = SuccWeights.size();
950 if (TotalWeight > UINT32_MAX) {
951 uint64_t ScalingFactor = TotalWeight / UINT32_MAX + 1;
953 for (
unsigned Idx = 0; Idx < SuccCount; ++Idx) {
954 SuccWeights[Idx] /= ScalingFactor;
958 TotalWeight += SuccWeights[Idx];
960 assert(TotalWeight <= UINT32_MAX &&
"Total weight overflows");
967 for (
unsigned Idx = 0; Idx < SuccCount; ++Idx) {
968 EdgeProbabilities[Idx] =
975 bool BranchProbabilityInfo::calcZeroHeuristics(
const BasicBlock *
BB,
977 const BranchInst *BI = dyn_cast<BranchInst>(
BB->getTerminator());
987 if (
auto *
I = dyn_cast<BitCastInst>(V))
988 return dyn_cast<ConstantInt>(
I->getOperand(0));
989 return dyn_cast<ConstantInt>(V);
1000 if (
LHS->getOpcode() == Instruction::And)
1002 if (AndRHS->getValue().isPowerOf2())
1012 ProbabilityTable::const_iterator Search;
1013 if (Func == LibFunc_strcasecmp ||
1014 Func == LibFunc_strcmp ||
1015 Func == LibFunc_strncasecmp ||
1016 Func == LibFunc_strncmp ||
1017 Func == LibFunc_memcmp ||
1018 Func == LibFunc_bcmp) {
1022 }
else if (CV->
isZero()) {
1026 }
else if (CV->
isOne()) {
1042 bool BranchProbabilityInfo::calcFloatingPointHeuristics(
const BasicBlock *
BB) {
1043 const BranchInst *BI = dyn_cast<BranchInst>(
BB->getTerminator());
1063 ProbList = Search->second;
1085 OS <<
"---- Branch Probabilities ----\n";
1088 assert(LastF &&
"Cannot print prior to running over a function");
1089 for (
const auto &BI : *LastF) {
1108 unsigned IndexInSuccessors)
const {
1109 auto I = Probs.find(std::make_pair(Src, IndexInSuccessors));
1110 assert((Probs.end() == Probs.find(std::make_pair(Src, 0))) ==
1111 (Probs.end() ==
I) &&
1112 "Probability for I-th successor must always be defined along with the "
1113 "probability for the first successor");
1115 if (
I != Probs.end())
1132 if (!Probs.count(std::make_pair(Src, 0)))
1138 Prob += Probs.find(std::make_pair(Src,
I.getSuccessorIndex()))->second;
1146 assert(Src->getTerminator()->getNumSuccessors() == Probs.size());
1148 if (Probs.size() == 0)
1151 Handles.insert(BasicBlockCallbackVH(Src,
this));
1153 for (
unsigned SuccIdx = 0; SuccIdx < Probs.size(); ++SuccIdx) {
1154 this->Probs[std::make_pair(Src, SuccIdx)] = Probs[SuccIdx];
1155 LLVM_DEBUG(
dbgs() <<
"set edge " << Src->getName() <<
" -> " << SuccIdx
1156 <<
" successor probability to " << Probs[SuccIdx]
1158 TotalNumerator += Probs[SuccIdx].getNumerator();
1168 (void)TotalNumerator;
1174 unsigned NumSuccessors = Src->getTerminator()->getNumSuccessors();
1175 assert(NumSuccessors == Dst->getTerminator()->getNumSuccessors());
1176 if (NumSuccessors == 0)
1178 if (this->Probs.find(std::make_pair(Src, 0)) ==
this->Probs.end())
1181 Handles.insert(BasicBlockCallbackVH(Dst,
this));
1182 for (
unsigned SuccIdx = 0; SuccIdx < NumSuccessors; ++SuccIdx) {
1183 auto Prob = this->Probs[std::make_pair(Src, SuccIdx)];
1184 this->Probs[std::make_pair(Dst, SuccIdx)] = Prob;
1185 LLVM_DEBUG(
dbgs() <<
"set edge " << Dst->getName() <<
" -> " << SuccIdx
1186 <<
" successor probability to " << Prob <<
"\n");
1195 OS <<
"edge " << Src->getName() <<
" -> " << Dst->getName()
1196 <<
" probability is " << Prob
1197 << (
isEdgeHot(Src, Dst) ?
" [HOT edge]\n" :
"\n");
1212 Handles.erase(BasicBlockCallbackVH(
BB,
this));
1213 for (
unsigned I = 0;; ++
I) {
1214 auto MapI = Probs.find(std::make_pair(
BB,
I));
1215 if (MapI == Probs.end()) {
1216 assert(Probs.count(std::make_pair(
BB,
I + 1)) == 0 &&
1217 "Must be no more successors");
1233 SccI = std::make_unique<SccInfo>(
F);
1235 assert(EstimatedBlockWeight.empty());
1238 std::unique_ptr<DominatorTree> DTPtr;
1239 std::unique_ptr<PostDominatorTree> PDTPtr;
1242 DTPtr = std::make_unique<DominatorTree>(
const_cast<Function &
>(
F));
1247 PDTPtr = std::make_unique<PostDominatorTree>(
const_cast<Function &
>(
F));
1251 computeEestimateBlockWeight(
F, DT, PDT);
1259 if (
BB->getTerminator()->getNumSuccessors() < 2)
1261 if (calcMetadataWeights(
BB))
1263 if (calcEstimatedHeuristics(
BB))
1265 if (calcPointerHeuristics(
BB))
1267 if (calcZeroHeuristics(
BB, TLI))
1269 if (calcFloatingPointHeuristics(
BB))
1273 EstimatedLoopWeight.
clear();
1274 EstimatedBlockWeight.clear();
1298 const LoopInfo &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
1300 getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(
F);
1301 DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
1303 getAnalysis<PostDominatorTreeWrapperPass>().getPostDomTree();
1304 BPI.calculate(
F, LI, &TLI, &DT, &PDT);
1328 OS <<
"Printing analysis results of BPI for function "
1329 <<
"'" <<
F.getName() <<
"':"
static const uint32_t PH_NONTAKEN_WEIGHT
A set of analyses that are preserved following a run of a transformation pass.
@ UNREACHABLE
Weight to an 'unreachable' block.
This is an optimization pass for GlobalISel generic memory operations.
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
void getSccExitBlocks(int SccNum, SmallVectorImpl< BasicBlock * > &Exits) const
Fills in Exits vector with all such blocks that don't belong to SCC with SccNum ID but there is an ed...
BlockExecWeight
Set of dedicated "absolute" execution weights for a block.
bool isPointerTy() const
True if this is an instance of PointerType.
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Interval::succ_iterator succ_end(Interval *I)
Represents a single loop in the control flow graph.
uint32_t getNumerator() const
This currently compiles esp xmm0 movsd esp eax eax esp ret We should use not the dag combiner This is because dagcombine2 needs to be able to see through the X86ISD::Wrapper which DAGCombine can t really do The code for turning x load into a single vector load is target independent and should be moved to the dag combiner The code for turning x load into a vector load can only handle a direct load from a global or a direct load from the stack It should be generalized to handle any load from P
bool contains(const LoopT *L) const
Return true if the specified loop is contained within in this loop.
static const ProbabilityTable ICmpWithLibCallTable
strcmp and similar functions return zero, negative, or positive, if the first string is equal,...
static const ProbabilityTable ICmpWithOneTable
Integer compares with 1:
const APInt & getValue() const
Return the constant as an APInt value reference.
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
@ COLD
Weight to a 'cold' block.
INITIALIZE_PASS_BEGIN(BranchProbabilityInfoWrapperPass, "branch-prob", "Branch Probability Analysis", false, true) INITIALIZE_PASS_END(BranchProbabilityInfoWrapperPass
This templated class represents "all analyses that operate over <a particular IR unit>" (e....
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
@ ICMP_SGT
signed greater than
static const BranchProbability UR_TAKEN_PROB
Unreachable-terminating branch taken probability.
static BranchProbability getZero()
auto reverse(ContainerTy &&C, std::enable_if_t< has_rbegin< ContainerTy >::value > *=nullptr)
The legacy pass manager's analysis pass to compute loop information.
DomTreeNodeBase< NodeT > * getNode(const NodeT *BB) const
getNode - return the (Post)DominatorTree node for the specified basic block.
size_type count(const_arg_type_t< KeyT > Val) const
Return 1 if the specified key is in the map, 0 otherwise.
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
auto successors(MachineBasicBlock *BB)
LLVM_NODISCARD T pop_back_val()
@ NORETURN
Weight to a block containing non returning call.
static cl::opt< bool > PrintBranchProb("print-bpi", cl::init(false), cl::Hidden, cl::desc("Print the branch probability info."))
LLVM Basic Block Representation.
unsigned getNumOperands() const
Return number of MDNode operands.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
static const BranchProbability FPOrdUntakenProb(FPH_UNO_WEIGHT, FPH_ORD_WEIGHT+FPH_UNO_WEIGHT)
This is the shared class of boolean and integer constants.
unsigned getNumSuccessors() const
Return the number of successors that this instruction has.
Analysis pass which computes BranchProbabilityInfo.
static const ProbabilityTable ICmpWithMinusOneTable
Integer compares with -1:
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
static uint32_t getDenominator()
Legacy analysis pass which computes BranchProbabilityInfo.
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
void getSccEnterBlocks(int SccNum, SmallVectorImpl< BasicBlock * > &Enters) const
Fills in Enters vector with all such blocks that don't belong to SCC with SccNum ID but there is an e...
void append(in_iter in_start, in_iter in_end)
Add the specified range to the end of the SmallVector.
unsigned succ_size(const Instruction *I)
static const ProbabilityTable FCmpTable
Floating-Point compares:
This instruction compares its operands according to the predicate given to the constructor.
Analysis providing branch probability information.
Represent the analysis usage information of a pass.
static bool isEquality(Predicate Pred)
constexpr T getValueOr(U &&value) const &
@ DEFAULT
Default weight is used in cases when there is no dedicated execution weight set.
BranchProbabilityInfo run(Function &F, FunctionAnalysisManager &AM)
Run the analysis pass over a function and produce BPI.
static ConstantInt * GetConstantInt(Value *V, const DataLayout &DL)
Extract ConstantInt from value, looking through IntToPtr and PointerNullValue.
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
bool getLibFunc(StringRef funcName, LibFunc &F) const
Searches for a particular function name.
@ FCMP_UNO
1 0 0 0 True if unordered: isnan(X) | isnan(Y)
static const uint32_t LBH_TAKEN_WEIGHT
Legacy analysis pass which computes a DominatorTree.
auto predecessors(MachineBasicBlock *BB)
This class implements an extremely fast bulk output stream that can only output to a stream.
static const uint32_t FPH_ORD_WEIGHT
This is the probability for an ordered floating point comparison.
BasicBlock * getSuccessor(unsigned Idx) const
Return the specified successor. This instruction must be a terminator.
API to communicate dependencies between analyses during invalidation.
static const BranchProbability FPOrdTakenProb(FPH_ORD_WEIGHT, FPH_ORD_WEIGHT+FPH_UNO_WEIGHT)
static BranchProbability getUnknown()
static const ProbabilityTable PointerTable
Pointer comparisons:
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
MDNode * getMetadata(unsigned KindID) const
Get the metadata of given kind attached to this Instruction.
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
scc_iterator< T > scc_begin(const T &G)
Construct the begin iterator for a deduced graph type T.
Value * getCondition() const
static const BranchProbability FPUntakenProb(FPH_NONTAKEN_WEIGHT, FPH_TAKEN_WEIGHT+FPH_NONTAKEN_WEIGHT)
static const uint32_t FPH_TAKEN_WEIGHT
This class is the base class for the comparison instructions.
cl::opt< std::string > PrintBranchProbFuncName("print-bpi-func-name", cl::Hidden, cl::desc("The option to specify the name of the function " "whose branch probability info is printed."))
const MDOperand & getOperand(unsigned I) const
static Constant * getCompare(unsigned short pred, Constant *C1, Constant *C2, bool OnlyIfReduced=false)
Return an ICmp or FCmp comparison operator constant expression.
This is an important base class in LLVM.
This instruction compares its operands according to the predicate given to the constructor.
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...
static const uint32_t ZH_TAKEN_WEIGHT
Zero Heuristics (ZH)
Enumerate the SCCs of a directed graph in reverse topological order of the SCC DAG.
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
void copyEdgeProbabilities(BasicBlock *Src, BasicBlock *Dst)
Copy outgoing edge probabilities from Src to Dst.
A special type used by analysis passes to provide an address that identifies that particular analysis...
SmallVector< BranchProbability > ProbabilityList
static Constant * get(unsigned Opcode, Constant *C1, unsigned Flags=0, Type *OnlyIfReducedTy=nullptr)
get - Return a unary operator constant expression, folding if possible.
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
Interval::succ_iterator succ_begin(Interval *I)
succ_begin/succ_end - define methods so that Intervals may be used just like BasicBlocks can with the...
void releaseMemory() override
releaseMemory() - This member can be implemented by a pass if it wants to be able to release its memo...
initializer< Ty > init(const Ty &Val)
bool is_contained(R &&Range, const E &Element)
Wrapper function around std::find to detect if an element exists in a container.
static bool isEquality(Predicate P)
Return true if this predicate is either EQ or NE.
static const uint32_t PH_TAKEN_WEIGHT
Heuristics and lookup tables for non-loop branches: Pointer Heuristics (PH)
static const ProbabilityTable ICmpWithZeroTable
Integer compares with 0:
iterator find(const_arg_type_t< KeyT > Val)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
constexpr const T & getValue() const &
void eraseBlock(const BasicBlock *BB)
Forget analysis results for the given basic block.
void print(raw_ostream &OS, const Module *M=nullptr) const override
print - Print out the internal state of the pass.
A Module instance is used to store all the information related to an LLVM module.
BranchProbability getEdgeProbability(const BasicBlock *Src, unsigned IndexInSuccessors) const
Get an edge's probability, relative to other out-edges of the Src.
static BranchProbability getOne()
@ ICMP_SLT
signed less than
static const uint32_t FPH_UNO_WEIGHT
This is the probability for an unordered floating point comparison, it means one or two of the operan...
void setEdgeProbability(const BasicBlock *Src, const SmallVectorImpl< BranchProbability > &Probs)
Set the raw probabilities for all edges from the given block.
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
SmallVector< MachineOperand, 4 > Cond
Analysis the ScalarEvolution expression for r is this
static const BranchProbability FPTakenProb(FPH_TAKEN_WEIGHT, FPH_TAKEN_WEIGHT+FPH_NONTAKEN_WEIGHT)
PostDominatorTree Class - Concrete subclass of DominatorTree that is used to compute the post-dominat...
Type * getType() const
All values are typed, get the type of this value.
Represents analyses that only rely on functions' control flow.
bool isZero() const
This is just a convenience method to make client code smaller for a common code.
bool isMinusOne() const
This function will return true iff every bit in this constant is set to true.
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
raw_ostream & printEdgeProbability(raw_ostream &OS, const BasicBlock *Src, const BasicBlock *Dst) const
Print an edge's probability.
uint64_t getZExtValue() const
Return the constant as a 64-bit unsigned integer value after it has been zero extended as appropriate...
LLVM_NODISCARD bool empty() const
bool runOnFunction(Function &F) override
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass.
@ ZERO
Special weight used for cases with exact zero probability.
void setPreservesAll()
Set by analyses that do not transform their input at all.
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
void print(raw_ostream &OS) const
std::map< CmpInst::Predicate, ProbabilityList > ProbabilityTable
Interval::pred_iterator pred_end(Interval *I)
iterator_range< po_iterator< T > > post_order(const T &G)
Provides information about what library functions are available for the current target.
static void computeUnlikelySuccessors(const BasicBlock *BB, Loop *L, SmallPtrSetImpl< const BasicBlock * > &UnlikelyBlocks)
void calculate(const Function &F, const LoopInfo &LI, const TargetLibraryInfo *TLI, DominatorTree *DT, PostDominatorTree *PDT)
bool isTrueWhenEqual() const
This is just a convenience.
static const uint32_t FPH_NONTAKEN_WEIGHT
static BranchProbability getRaw(uint32_t N)
Interval::pred_iterator pred_begin(Interval *I)
pred_begin/pred_end - define methods so that Intervals may be used just like BasicBlocks can with the...
Analysis pass which computes a DominatorTree.
bool isEdgeHot(const BasicBlock *Src, const BasicBlock *Dst) const
Test if an edge is hot relative to other out-edges of the Src.
static const BranchProbability ZeroTakenProb(ZH_TAKEN_WEIGHT, ZH_TAKEN_WEIGHT+ZH_NONTAKEN_WEIGHT)
static const BranchProbability PtrTakenProb(PH_TAKEN_WEIGHT, PH_TAKEN_WEIGHT+PH_NONTAKEN_WEIGHT)
Predicate getPredicate() const
Return the predicate for this instruction.
void initializeBranchProbabilityInfoWrapperPassPass(PassRegistry &)
Align max(MaybeAlign Lhs, Align Rhs)
unsigned getActiveBits() const
Compute the number of active bits in the value.
A range adaptor for a pair of iterators.
BlockType
Used as immediate MachineOperands for block signatures.
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...
static const uint32_t ZH_NONTAKEN_WEIGHT
@ LOWEST_NON_ZERO
Minimal possible non zero weight.
PreservedAnalysisChecker getChecker() const
Build a checker for this PreservedAnalyses and the specified analysis type.
A container for analyses that lazily runs them and caches their results.
bool invalidate(Function &, const PreservedAnalyses &PA, FunctionAnalysisManager::Invalidator &)
FunctionPass class - This class is used to implement most global optimizations.
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
This class represents a function call, abstracting a target machine's calling convention.
@ UNWIND
Weight to 'unwind' block of an invoke instruction.
bool isOne() const
This is just a convenience method to make client code smaller for a common case.
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Analysis pass which computes a PostDominatorTree.
AnalysisUsage & addRequired()
Value * getOperand(unsigned i) const
static const BranchProbability PtrUntakenProb(PH_NONTAKEN_WEIGHT, PH_TAKEN_WEIGHT+PH_NONTAKEN_WEIGHT)
Conditional or Unconditional Branch instruction.
static const BranchProbability ZeroUntakenProb(ZH_NONTAKEN_WEIGHT, ZH_TAKEN_WEIGHT+ZH_NONTAKEN_WEIGHT)
bool contains(ConstPtrType Ptr) const
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
void reserve(size_type N)
bool dominates(const Instruction *I1, const Instruction *I2) const
Return true if I1 dominates I2.
uint64_t divideNearest(uint64_t Numerator, uint64_t Denominator)
Returns the integer nearest(Numerator / Denominator).
LLVM Value Representation.
static const uint32_t LBH_NONTAKEN_WEIGHT
Analysis pass providing the TargetLibraryInfo.
int getSCCNum(const BasicBlock *BB) const
If BB belongs to some SCC then ID of that SCC is returned, otherwise -1 is returned.
bool isConditional() const
@ FCMP_ORD
0 1 1 1 True if ordered (no nans)
BasicBlock * getSuccessor(unsigned i) const
Analysis pass that exposes the LoopInfo for a function.
SccInfo(const Function &F)
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.