1//===- BranchProbabilityInfo.h - Branch Probability Analysis ----*- C++ -*-===// 3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4// See https://llvm.org/LICENSE.txt for license information. 5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 7//===----------------------------------------------------------------------===// 9// This pass is used to evaluate branch probabilties. 11//===----------------------------------------------------------------------===// 13#ifndef LLVM_ANALYSIS_BRANCHPROBABILITYINFO_H 14#define LLVM_ANALYSIS_BRANCHPROBABILITYINFO_H 37classPostDominatorTree;
38classTargetLibraryInfo;
41/// Analysis providing branch probability information. 43/// This is a function analysis which provides information on the relative 44/// probabilities of each "edge" in the function's CFG where such an edge is 45/// defined by a pair (PredBlock and an index in the successors). The 46/// probability of an edge from one block is always relative to the 47/// probabilities of other edges from the block. The probabilites of all edges 48/// from a block sum to exactly one (100%). 49/// We use a pair (PredBlock and an index in the successors) to uniquely 50/// identify an edge, since we can have multiple edges from Src to Dst. 51/// As an example, we can have a switch which jumps to Dst with value 0 and 54/// Process of computing branch probabilities can be logically viewed as three 57/// First, if there is a profile information associated with the branch then 58/// it is trivially translated to branch probabilities. There is one exception 59/// from this rule though. Probabilities for edges leading to "unreachable" 60/// blocks (blocks with the estimated weight not greater than 61/// UNREACHABLE_WEIGHT) are evaluated according to static estimation and 62/// override profile information. If no branch probabilities were calculated 63/// on this step then take the next one. 65/// Second, estimate absolute execution weights for each block based on 66/// statically known information. Roots of such information are "cold", 67/// "unreachable", "noreturn" and "unwind" blocks. Those blocks get their 68/// weights set to BlockExecWeight::COLD, BlockExecWeight::UNREACHABLE, 69/// BlockExecWeight::NORETURN and BlockExecWeight::UNWIND respectively. Then the 70/// weights are propagated to the other blocks up the domination line. In 71/// addition, if all successors have estimated weights set then maximum of these 72/// weights assigned to the block itself (while this is not ideal heuristic in 73/// theory it's simple and works reasonably well in most cases) and the process 74/// repeats. Once the process of weights propagation converges branch 75/// probabilities are set for all such branches that have at least one successor 76/// with the weight set. Default execution weight (BlockExecWeight::DEFAULT) is 77/// used for any successors which doesn't have its weight set. For loop back 78/// branches we use their weights scaled by loop trip count equal to 79/// 'LBH_TAKEN_WEIGHT/LBH_NOTTAKEN_WEIGHT'. 81/// Here is a simple example demonstrating how the described algorithm works. 91/// Initially, ColdBB is associated with COLD_WEIGHT and UnreachBB with 92/// UNREACHABLE_WEIGHT. COLD_WEIGHT is set to BB2 as maximum between its 93/// successors. BB1 and BB3 has no explicit estimated weights and assumed to 94/// have DEFAULT_WEIGHT. Based on assigned weights branches will have the 95/// following probabilities: 96/// P(BB1->BB2) = COLD_WEIGHT/(COLD_WEIGHT + DEFAULT_WEIGHT) = 97/// 0xffff / (0xffff + 0xfffff) = 0.0588(5.9%) 98/// P(BB1->BB3) = DEFAULT_WEIGHT_WEIGHT/(COLD_WEIGHT + DEFAULT_WEIGHT) = 99/// 0xfffff / (0xffff + 0xfffff) = 0.941(94.1%) 100/// P(BB2->ColdBB) = COLD_WEIGHT/(COLD_WEIGHT + UNREACHABLE_WEIGHT) = 1(100%) 101/// P(BB2->UnreachBB) = 102/// UNREACHABLE_WEIGHT/(COLD_WEIGHT+UNREACHABLE_WEIGHT) = 0(0%) 104/// If no branch probabilities were calculated on this step then take the next 107/// Third, apply different kinds of local heuristics for each individual 108/// branch until first match. For example probability of a pointer to be null is 109/// estimated as PH_TAKEN_WEIGHT/(PH_TAKEN_WEIGHT + PH_NONTAKEN_WEIGHT). If 110/// no local heuristic has been matched then branch is left with no explicit 111/// probability set and assumed to have default probability. 126 EstimatedBlockWeight(
std::
move(Arg.EstimatedBlockWeight)) {
127for (
auto &Handle : Handles)
136 Handles = std::move(
RHS.Handles);
137 Probs = std::move(
RHS.Probs);
138 EstimatedBlockWeight = std::move(
RHS.EstimatedBlockWeight);
139for (
auto &Handle : Handles)
151 /// Get an edge's probability, relative to other out-edges of the Src. 153 /// This routine provides access to the fractional probability between zero 154 /// (0%) and one (100%) of this edge executing, relative to other edges 155 /// leaving the 'Src' block. The returned probability is never zero, and can 156 /// only be one if the source block has only one successor. 158unsigned IndexInSuccessors)
const;
160 /// Get the probability of going from Src to Dst. 162 /// It returns the sum of all probabilities for edges from Src to Dst. 169 /// Test if an edge is hot relative to other out-edges of the Src. 171 /// Check whether this edge out of the source block is 'hot'. We define hot 172 /// as having a relative probability > 80%. 175 /// Print an edge's probability. 177 /// Retrieves an edge's probability similarly to \see getEdgeProbability, but 178 /// then prints that probability to the provided stream. That stream is then 184 /// Set the raw probabilities for all edges from the given block. 186 /// This allows a pass to explicitly set edge probabilities for a block. It 187 /// can be used when updating the CFG to update the branch probability 192 /// Copy outgoing edge probabilities from \p Src to \p Dst. 194 /// This allows to keep probabilities unset for the destination if they were 195 /// unset for source. 198 /// Swap outgoing edges probabilities for \p Src with branch terminator 203return IsLikely ? LikelyProb : LikelyProb.
getCompl();
210 /// Forget analysis results for the given basic block. 213// Data structure to track SCCs for handling irreducible loops. 215// Enum of types to classify basic blocks in SCC. Basic block belonging to 216// SCC is 'Inner' until it is either 'Header' or 'Exiting'. Note that a 217// basic block can be 'Header' and 'Exiting' at the same time. 223// Map of basic blocks to SCC IDs they belong to. If basic block doesn't 224// belong to any SCC it is not in the map. 226// Each basic block in SCC is attributed with one or several types from 227// SccBlockType. Map value has uint32_t type (instead of SccBlockType) 228// since basic block may be for example "Header" and "Exiting" at the same 229// time and we need to be able to keep more than one value from 232// Vector containing classification of basic blocks for all SCCs where i'th 233// vector element corresponds to SCC with ID equal to i. 234usingSccBlockTypeMaps = std::vector<SccBlockTypeMap>;
237 SccBlockTypeMaps SccBlocks;
242 /// If \p BB belongs to some SCC then ID of that SCC is returned, otherwise 243 /// -1 is returned. If \p BB belongs to more than one SCC at the same time 244 /// result is undefined. 246 /// Returns true if \p BB is a 'header' block in SCC with \p SccNum ID, 249return getSccBlockType(BB, SccNum) & Header;
251 /// Returns true if \p BB is an 'exiting' block in SCC with \p SccNum ID, 254return getSccBlockType(BB, SccNum) & Exiting;
256 /// Fills in \p Enters vector with all such blocks that don't belong to 257 /// SCC with \p SccNum ID but there is an edge to a block belonging to the 261 /// Fills in \p Exits vector with all such blocks that don't belong to 262 /// SCC with \p SccNum ID but there is an edge from a block belonging to the 268 /// Returns \p BB's type according to classification given by SccBlockType 269 /// enum. Please note that \p BB must belong to SSC with \p SccNum ID. 271 /// Calculates \p BB's type and stores it in internal data structures for 272 /// future use. Please note that \p BB must belong to SSC with \p SccNum ID. 273void calculateSccBlockType(
constBasicBlock *BB,
int SccNum);
277// We need to store CallbackVH's in order to correctly handle basic block 279classBasicBlockCallbackVH final :
publicCallbackVH {
282void deleted()
override{
284 BPI->eraseBlock(cast<BasicBlock>(
getValPtr()));
294 /// Pair of Loop and SCC ID number. Used to unify handling of normal and 295 /// SCC based loop representations. 296usingLoopData = std::pair<Loop *, int>;
297 /// Helper class to keep basic block along with its loop data information. 300explicit LoopBlock(
const BasicBlock *BB,
const LoopInfo &LI,
305 LoopData getLoopData()
const{
returnLD; }
306 Loop *getLoop()
const{
returnLD.first; }
307int getSccNum()
const{
returnLD.second; }
309bool belongsToLoop()
const{
return getLoop() || getSccNum() != -1; }
310bool belongsToSameLoop(
const LoopBlock &LB)
const{
311return (LB.getLoop() && getLoop() == LB.getLoop()) ||
312 (LB.getSccNum() != -1 && getSccNum() == LB.getSccNum());
317 LoopData
LD = {
nullptr, -1};
320// Pair of LoopBlocks representing an edge from first to second block. 321usingLoopEdge = std::pair<const LoopBlock &, const LoopBlock &>;
323 DenseSet<BasicBlockCallbackVH, DenseMapInfo<Value*>> Handles;
325// Since we allow duplicate edges from one basic block to another, we use 326// a pair (PredBlock and an index in the successors) to specify an edge. 327usingEdge = std::pair<const BasicBlock *, unsigned>;
329 DenseMap<Edge, BranchProbability> Probs;
331 /// Track the last function we run over for printing. 334const LoopInfo *LI =
nullptr;
336 /// Keeps information about all SCCs in a function. 337 std::unique_ptr<const SccInfo> SccI;
339 /// Keeps mapping of a basic block to its estimated weight. 340 SmallDenseMap<const BasicBlock *, uint32_t> EstimatedBlockWeight;
342 /// Keeps mapping of a loop to estimated weight to enter the loop. 343 SmallDenseMap<LoopData, uint32_t> EstimatedLoopWeight;
345 /// Helper to construct LoopBlock for \p BB. 346 LoopBlock getLoopBlock(
const BasicBlock *BB)
const{
347return LoopBlock(BB, *LI, *SccI);
350 /// Returns true if destination block belongs to some loop and source block is 351 /// either doesn't belong to any loop or belongs to a loop which is not inner 352 /// relative to the destination block. 353bool isLoopEnteringEdge(
const LoopEdge &Edge)
const;
354 /// Returns true if source block belongs to some loop and destination block is 355 /// either doesn't belong to any loop or belongs to a loop which is not inner 356 /// relative to the source block. 357bool isLoopExitingEdge(
const LoopEdge &Edge)
const;
358 /// Returns true if \p Edge is either enters to or exits from some loop, false 359 /// in all other cases. 360bool isLoopEnteringExitingEdge(
const LoopEdge &Edge)
const;
361 /// Returns true if source and destination blocks belongs to the same loop and 362 /// destination block is loop header. 363bool isLoopBackEdge(
const LoopEdge &Edge)
const;
364// Fills in \p Enters vector with all "enter" blocks to a loop \LB belongs to. 365void getLoopEnterBlocks(
const LoopBlock &LB,
366 SmallVectorImpl<BasicBlock *> &Enters)
const;
367// Fills in \p Exits vector with all "exit" blocks from a loop \LB belongs to. 368void getLoopExitBlocks(
const LoopBlock &LB,
369 SmallVectorImpl<BasicBlock *> &Exits)
const;
371 /// Returns estimated weight for \p BB. std::nullopt if \p BB has no estimated 373 std::optional<uint32_t> getEstimatedBlockWeight(
const BasicBlock *BB)
const;
375 /// Returns estimated weight to enter \p L. In other words it is weight of 376 /// loop's header block not scaled by trip count. Returns std::nullopt if \p L 377 /// has no no estimated weight. 378 std::optional<uint32_t> getEstimatedLoopWeight(
const LoopData &L)
const;
380 /// Return estimated weight for \p Edge. Returns std::nullopt if estimated 381 /// weight is unknown. 382 std::optional<uint32_t> getEstimatedEdgeWeight(
const LoopEdge &Edge)
const;
384 /// Iterates over all edges leading from \p SrcBB to \p Successors and 385 /// returns maximum of all estimated weights. If at least one edge has unknown 386 /// estimated weight std::nullopt is returned. 387template <
class IterT>
388 std::optional<uint32_t>
389 getMaxEstimatedEdgeWeight(
const LoopBlock &SrcBB,
390 iterator_range<IterT> Successors)
const;
392 /// If \p LoopBB has no estimated weight then set it to \p BBWeight and 393 /// return true. Otherwise \p BB's weight remains unchanged and false is 394 /// returned. In addition all blocks/loops that might need their weight to be 395 /// re-estimated are put into BlockWorkList/LoopWorkList. 396bool updateEstimatedBlockWeight(LoopBlock &LoopBB,
uint32_t BBWeight,
397 SmallVectorImpl<BasicBlock *> &BlockWorkList,
398 SmallVectorImpl<LoopBlock> &LoopWorkList);
400 /// Starting from \p LoopBB (including \p LoopBB itself) propagate \p BBWeight 401 /// up the domination tree. 402void propagateEstimatedBlockWeight(
const LoopBlock &LoopBB, DominatorTree *DT,
403 PostDominatorTree *PDT,
uint32_t BBWeight,
404 SmallVectorImpl<BasicBlock *> &WorkList,
405 SmallVectorImpl<LoopBlock> &LoopWorkList);
407 /// Returns block's weight encoded in the IR. 408 std::optional<uint32_t> getInitialEstimatedBlockWeight(
const BasicBlock *BB);
410// Computes estimated weights for all blocks in \p F. 411void computeEestimateBlockWeight(
const Function &
F, DominatorTree *DT,
412 PostDominatorTree *PDT);
414 /// Based on computed weights by \p computeEstimatedBlockWeight set 415 /// probabilities on branches. 416bool calcEstimatedHeuristics(
const BasicBlock *BB);
417bool calcMetadataWeights(
const BasicBlock *BB);
418bool calcPointerHeuristics(
const BasicBlock *BB);
419bool calcZeroHeuristics(
const BasicBlock *BB,
const TargetLibraryInfo *TLI);
420bool calcFloatingPointHeuristics(
const BasicBlock *BB);
423/// Analysis pass which computes \c BranchProbabilityInfo. 431 /// Provide the result type for this analysis pass. 434 /// Run the analysis pass over a function and produce BPI. 438/// Printer pass for the \c BranchProbabilityAnalysis results. 451/// Legacy analysis pass which computes \c BranchProbabilityInfo. 469}
// end namespace llvm 471#endif// LLVM_ANALYSIS_BRANCHPROBABILITYINFO_H This file defines DenseMapInfo traits for DenseMap.
This file defines the DenseMap class.
This file defines the DenseSet and SmallDenseSet classes.
This file provides various utilities for inspecting and working with the control flow graph in LLVM I...
This header defines various interfaces for pass management in LLVM.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
API to communicate dependencies between analyses during invalidation.
A container for analyses that lazily runs them and caches their results.
Represent the analysis usage information of a pass.
LLVM Basic Block Representation.
Analysis pass which computes BranchProbabilityInfo.
BranchProbabilityInfo run(Function &F, FunctionAnalysisManager &AM)
Run the analysis pass over a function and produce BPI.
Legacy analysis pass which computes BranchProbabilityInfo.
void releaseMemory() override
releaseMemory() - This member can be implemented by a pass if it wants to be able to release its memo...
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
const BranchProbabilityInfo & getBPI() const
BranchProbabilityInfoWrapperPass()
bool runOnFunction(Function &F) override
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass.
void print(raw_ostream &OS, const Module *M=nullptr) const override
print - Print out the internal state of the pass.
BranchProbabilityInfo & getBPI()
bool isSCCHeader(const BasicBlock *BB, int SccNum) const
Returns true if BB is a 'header' block in SCC with SccNum ID, false otherwise.
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...
bool isSCCExitingBlock(const BasicBlock *BB, int SccNum) const
Returns true if BB is an 'exiting' block in SCC with SccNum ID, false otherwise.
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...
int getSCCNum(const BasicBlock *BB) const
If BB belongs to some SCC then ID of that SCC is returned, otherwise -1 is returned.
Analysis providing branch probability information.
void eraseBlock(const BasicBlock *BB)
Forget analysis results for the given basic block.
void setEdgeProbability(const BasicBlock *Src, const SmallVectorImpl< BranchProbability > &Probs)
Set the raw probabilities for all edges from the given block.
BranchProbabilityInfo(const BranchProbabilityInfo &)=delete
bool invalidate(Function &, const PreservedAnalyses &PA, FunctionAnalysisManager::Invalidator &)
BranchProbability getEdgeProbability(const BasicBlock *Src, unsigned IndexInSuccessors) const
Get an edge's probability, relative to other out-edges of the Src.
static BranchProbability getBranchProbStackProtector(bool IsLikely)
void calculate(const Function &F, const LoopInfo &LI, const TargetLibraryInfo *TLI, DominatorTree *DT, PostDominatorTree *PDT)
BranchProbabilityInfo & operator=(BranchProbabilityInfo &&RHS)
BranchProbabilityInfo()=default
bool isEdgeHot(const BasicBlock *Src, const BasicBlock *Dst) const
Test if an edge is hot relative to other out-edges of the Src.
void swapSuccEdgesProbabilities(const BasicBlock *Src)
Swap outgoing edges probabilities for Src with branch terminator.
BranchProbabilityInfo(BranchProbabilityInfo &&Arg)
void print(raw_ostream &OS) const
BranchProbabilityInfo(const Function &F, const LoopInfo &LI, const TargetLibraryInfo *TLI=nullptr, DominatorTree *DT=nullptr, PostDominatorTree *PDT=nullptr)
BranchProbabilityInfo & operator=(const BranchProbabilityInfo &)=delete
raw_ostream & printEdgeProbability(raw_ostream &OS, const BasicBlock *Src, const BasicBlock *Dst) const
Print an edge's probability.
void copyEdgeProbabilities(BasicBlock *Src, BasicBlock *Dst)
Copy outgoing edge probabilities from Src to Dst.
Printer pass for the BranchProbabilityAnalysis results.
BranchProbabilityPrinterPass(raw_ostream &OS)
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
BranchProbability getCompl() const
Value handle with callbacks on RAUW and destruction.
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
FunctionPass class - This class is used to implement most global optimizations.
A Module instance is used to store all the information related to an LLVM module.
PostDominatorTree Class - Concrete subclass of DominatorTree that is used to compute the post-dominat...
A set of analyses that are preserved following a run of a transformation pass.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Provides information about what library functions are available for the current target.
Value * getValPtr() const
This class implements an extremely fast bulk output stream that can only output to a stream.
@ BasicBlock
Various leaf nodes.
This is an optimization pass for GlobalISel generic memory operations.
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.
Implement std::hash so that hash_code can be used in STL containers.
A CRTP mix-in that provides informational APIs needed for analysis passes.
A special type used by analysis passes to provide an address that identifies that particular analysis...
A CRTP mix-in to automatically provide informational APIs needed for passes.
