class BranchProbabilityInfo

Declaration

class BranchProbabilityInfo { /* full declaration omitted */ };

Description

Analysis providing branch probability information. This is a function analysis which provides information on the relative probabilities of each "edge" in the function's CFG where such an edge is defined by a pair (PredBlock and an index in the successors). The probability of an edge from one block is always relative to the probabilities of other edges from the block. The probabilites of all edges from a block sum to exactly one (100%). We use a pair (PredBlock and an index in the successors) to uniquely identify an edge, since we can have multiple edges from Src to Dst. As an example, we can have a switch which jumps to Dst with value 0 and value 10. Process of computing branch probabilities can be logically viewed as three step process: First, if there is a profile information associated with the branch then it is trivially translated to branch probabilities. There is one exception from this rule though. Probabilities for edges leading to "unreachable" blocks (blocks with the estimated weight not greater than UNREACHABLE_WEIGHT) are evaluated according to static estimation and override profile information. If no branch probabilities were calculated on this step then take the next one. Second, estimate absolute execution weights for each block based on statically known information. Roots of such information are "cold", "unreachable", "noreturn" and "unwind" blocks. Those blocks get their weights set to BlockExecWeight::COLD, BlockExecWeight::UNREACHABLE, BlockExecWeight::NORETURN and BlockExecWeight::UNWIND respectively. Then the weights are propagated to the other blocks up the domination line. In addition, if all successors have estimated weights set then maximum of these weights assigned to the block itself (while this is not ideal heuristic in theory it's simple and works reasonably well in most cases) and the process repeats. Once the process of weights propagation converges branch probabilities are set for all such branches that have at least one successor with the weight set. Default execution weight (BlockExecWeight::DEFAULT) is used for any successors which doesn't have its weight set. For loop back branches we use their weights scaled by loop trip count equal to 'LBH_TAKEN_WEIGHT/LBH_NOTTAKEN_WEIGHT'. Here is a simple example demonstrating how the described algorithm works. BB1 / \ /// v v BB2 BB3 / \ /// v v ColdBB UnreachBB Initially, ColdBB is associated with COLD_WEIGHT and UnreachBB with UNREACHABLE_WEIGHT. COLD_WEIGHT is set to BB2 as maximum between its successors. BB1 and BB3 has no explicit estimated weights and assumed to have DEFAULT_WEIGHT. Based on assigned weights branches will have the following probabilities: P(BB1->BB2) = COLD_WEIGHT/(COLD_WEIGHT + DEFAULT_WEIGHT) = 0xffff / (0xffff + 0xfffff) = 0.0588(5.9%) P(BB1->BB3) = DEFAULT_WEIGHT_WEIGHT/(COLD_WEIGHT + DEFAULT_WEIGHT) = 0xfffff / (0xffff + 0xfffff) = 0.941(94.1%) P(BB2->ColdBB) = COLD_WEIGHT/(COLD_WEIGHT + UNREACHABLE_WEIGHT) = 1(100%) P(BB2->UnreachBB) = UNREACHABLE_WEIGHT/(COLD_WEIGHT+UNREACHABLE_WEIGHT) = 0(0%) If no branch probabilities were calculated on this step then take the next one. Third, apply different kinds of local heuristics for each individual branch until first match. For example probability of a pointer to be null is estimated as PH_TAKEN_WEIGHT/(PH_TAKEN_WEIGHT + PH_NONTAKEN_WEIGHT). If no local heuristic has been matched then branch is left with no explicit probability set and assumed to have default probability.

Declared at: llvm/include/llvm/Analysis/BranchProbabilityInfo.h:113

Member Variables

private DenseSet<llvm::BranchProbabilityInfo:: BasicBlockCallbackVH, DenseMapInfo<llvm::Value*>> Handles

private DenseMap<llvm::BranchProbabilityInfo::Edge, llvm::BranchProbability> Probs

private const llvm::Function* LastF = nullptr

Track the last function we run over for printing.

private const llvm::LoopInfo* LI = nullptr

private std::unique_ptr<const SccInfo> SccI

Keeps information about all SCCs in a function.

private SmallDenseMap<const llvm::BasicBlock*, uint32_t> EstimatedBlockWeight

Keeps mapping of a basic block to its estimated weight.

private SmallDenseMap< llvm::BranchProbabilityInfo::LoopData, uint32_t> EstimatedLoopWeight

Keeps mapping of a loop to estimated weight to enter the loop.

Method Overview

• public BranchProbabilityInfo(const llvm::Function & F, const llvm::LoopInfo & LI, const llvm::TargetLibraryInfo * TLI = nullptr, llvm::DominatorTree * DT = nullptr, llvm::PostDominatorTree * PDT = nullptr)
• public BranchProbabilityInfo(llvm::BranchProbabilityInfo && Arg)
• public BranchProbabilityInfo(const llvm::BranchProbabilityInfo &)
• public BranchProbabilityInfo()
• private bool calcEstimatedHeuristics(const llvm::BasicBlock * BB)
• private bool calcFloatingPointHeuristics(const llvm::BasicBlock * BB)
• private bool calcMetadataWeights(const llvm::BasicBlock * BB)
• private bool calcPointerHeuristics(const llvm::BasicBlock * BB)
• private bool calcZeroHeuristics(const llvm::BasicBlock * BB, const llvm::TargetLibraryInfo * TLI)
• public void calculate(const llvm::Function & F, const llvm::LoopInfo & LI, const llvm::TargetLibraryInfo * TLI, llvm::DominatorTree * DT, llvm::PostDominatorTree * PDT)
• private void computeEestimateBlockWeight(const llvm::Function & F, llvm::DominatorTree * DT, llvm::PostDominatorTree * PDT)
• public void copyEdgeProbabilities(llvm::BasicBlock * Src, llvm::BasicBlock * Dst)
• public void eraseBlock(const llvm::BasicBlock * BB)
• public static llvm::BranchProbability getBranchProbStackProtector(bool IsLikely)
• public llvm::BranchProbability getEdgeProbability(const llvm::BasicBlock * Src, llvm::const_succ_iterator Dst) const
• public llvm::BranchProbability getEdgeProbability(const llvm::BasicBlock * Src, const llvm::BasicBlock * Dst) const
• public llvm::BranchProbability getEdgeProbability(const llvm::BasicBlock * Src, unsigned int IndexInSuccessors) const
• private Optional<uint32_t> getEstimatedBlockWeight(const llvm::BasicBlock * BB) const
• private Optional<uint32_t> getEstimatedEdgeWeight(const llvm::BranchProbabilityInfo::LoopEdge & Edge) const
• private Optional<uint32_t> getEstimatedLoopWeight(const llvm::BranchProbabilityInfo::LoopData & L) const
• private Optional<uint32_t> getInitialEstimatedBlockWeight(const llvm::BasicBlock * BB)
• private llvm::BranchProbabilityInfo::LoopBlock getLoopBlock(const llvm::BasicBlock * BB) const
• private void getLoopEnterBlocks(const llvm::BranchProbabilityInfo::LoopBlock & LB, SmallVectorImpl<llvm::BasicBlock *> & Enters) const
• private void getLoopExitBlocks(const llvm::BranchProbabilityInfo::LoopBlock & LB, SmallVectorImpl<llvm::BasicBlock *> & Exits) const
• private template <class IterT>Optional<uint32_t> getMaxEstimatedEdgeWeight(const llvm::BranchProbabilityInfo::LoopBlock & SrcBB, iterator_range<IterT> Successors) const
• public bool invalidate(llvm::Function &, const llvm::PreservedAnalyses & PA, FunctionAnalysisManager::Invalidator &)
• public bool isEdgeHot(const llvm::BasicBlock * Src, const llvm::BasicBlock * Dst) const
• private bool isLoopBackEdge(const llvm::BranchProbabilityInfo::LoopEdge & Edge) const
• private bool isLoopEnteringEdge(const llvm::BranchProbabilityInfo::LoopEdge & Edge) const
• private bool isLoopEnteringExitingEdge(const llvm::BranchProbabilityInfo::LoopEdge & Edge) const
• private bool isLoopExitingEdge(const llvm::BranchProbabilityInfo::LoopEdge & Edge) const
• public void print(llvm::raw_ostream & OS) const
• public llvm::raw_ostream & printEdgeProbability(llvm::raw_ostream & OS, const llvm::BasicBlock * Src, const llvm::BasicBlock * Dst) const
• private void propagateEstimatedBlockWeight(const llvm::BranchProbabilityInfo::LoopBlock & LoopBB, llvm::DominatorTree * DT, llvm::PostDominatorTree * PDT, uint32_t BBWeight, SmallVectorImpl<llvm::BasicBlock *> & WorkList, SmallVectorImpl<llvm::BranchProbabilityInfo::LoopBlock> & LoopWorkList)
• public void releaseMemory()
• public void setEdgeProbability(const llvm::BasicBlock * Src, const SmallVectorImpl<llvm::BranchProbability> & Probs)
• private bool updateEstimatedBlockWeight(llvm::BranchProbabilityInfo::LoopBlock & LoopBB, uint32_t BBWeight, SmallVectorImpl<llvm::BasicBlock *> & BlockWorkList, SmallVectorImpl<llvm::BranchProbabilityInfo::LoopBlock> & LoopWorkList)

Methods

¶BranchProbabilityInfo(
    const llvm::Function& F,
    const llvm::LoopInfo& LI,
    const llvm::TargetLibraryInfo* TLI = nullptr,
    llvm::DominatorTree* DT = nullptr,
    llvm::PostDominatorTree* PDT = nullptr)

Declared at: llvm/include/llvm/Analysis/BranchProbabilityInfo.h:117

Parameters

const llvm::Function& F

const llvm::LoopInfo& LI

const llvm::TargetLibraryInfo* TLI = nullptr

llvm::DominatorTree* DT = nullptr

llvm::PostDominatorTree* PDT = nullptr

¶BranchProbabilityInfo(
    llvm::BranchProbabilityInfo&& Arg)

Declared at: llvm/include/llvm/Analysis/BranchProbabilityInfo.h:124

Parameters

llvm::BranchProbabilityInfo&& Arg

¶BranchProbabilityInfo(
    const llvm::BranchProbabilityInfo&)

Declared at: llvm/include/llvm/Analysis/BranchProbabilityInfo.h:128

Parameters

const llvm::BranchProbabilityInfo&

¶BranchProbabilityInfo()

Declared at: llvm/include/llvm/Analysis/BranchProbabilityInfo.h:115

¶bool calcEstimatedHeuristics(
    const llvm::BasicBlock* BB)

Description

Based on computed weights by \p computeEstimatedBlockWeight set probabilities on branches.

Declared at: llvm/include/llvm/Analysis/BranchProbabilityInfo.h:404

Parameters

const llvm::BasicBlock* BB

¶bool calcFloatingPointHeuristics(
    const llvm::BasicBlock* BB)

Declared at: llvm/include/llvm/Analysis/BranchProbabilityInfo.h:408

Parameters

const llvm::BasicBlock* BB

¶bool calcMetadataWeights(
    const llvm::BasicBlock* BB)

Declared at: llvm/include/llvm/Analysis/BranchProbabilityInfo.h:405

Parameters

const llvm::BasicBlock* BB

¶bool calcPointerHeuristics(
    const llvm::BasicBlock* BB)

Declared at: llvm/include/llvm/Analysis/BranchProbabilityInfo.h:406

Parameters

const llvm::BasicBlock* BB

¶bool calcZeroHeuristics(
    const llvm::BasicBlock* BB,
    const llvm::TargetLibraryInfo* TLI)

Declared at: llvm/include/llvm/Analysis/BranchProbabilityInfo.h:407

Parameters

const llvm::BasicBlock* BB

const llvm::TargetLibraryInfo* TLI

¶void calculate(const llvm::Function& F,
               const llvm::LoopInfo& LI,
               const llvm::TargetLibraryInfo* TLI,
               llvm::DominatorTree* DT,
               llvm::PostDominatorTree* PDT)

Declared at: llvm/include/llvm/Analysis/BranchProbabilityInfo.h:197

Parameters

const llvm::Function& F

const llvm::LoopInfo& LI

const llvm::TargetLibraryInfo* TLI

llvm::DominatorTree* DT

llvm::PostDominatorTree* PDT

¶void computeEestimateBlockWeight(
    const llvm::Function& F,
    llvm::DominatorTree* DT,
    llvm::PostDominatorTree* PDT)

Declared at: llvm/include/llvm/Analysis/BranchProbabilityInfo.h:399

Parameters

const llvm::Function& F

llvm::DominatorTree* DT

llvm::PostDominatorTree* PDT

¶void copyEdgeProbabilities(llvm::BasicBlock* Src,
                           llvm::BasicBlock* Dst)

Description

Copy outgoing edge probabilities from \p Src to \p Dst. This allows to keep probabilities unset for the destination if they were unset for source.

Declared at: llvm/include/llvm/Analysis/BranchProbabilityInfo.h:190

Parameters

llvm::BasicBlock* Src

llvm::BasicBlock* Dst

¶void eraseBlock(const llvm::BasicBlock* BB)

Description

Forget analysis results for the given basic block.

Declared at: llvm/include/llvm/Analysis/BranchProbabilityInfo.h:202

Parameters

const llvm::BasicBlock* BB

¶static llvm::BranchProbability
getBranchProbStackProtector(bool IsLikely)

Declared at: llvm/include/llvm/Analysis/BranchProbabilityInfo.h:192

Parameters

bool IsLikely

¶llvm::BranchProbability getEdgeProbability(
    const llvm::BasicBlock* Src,
    llvm::const_succ_iterator Dst) const

Declared at: llvm/include/llvm/Analysis/BranchProbabilityInfo.h:160

Parameters

const llvm::BasicBlock* Src

llvm::const_succ_iterator Dst

¶llvm::BranchProbability getEdgeProbability(
    const llvm::BasicBlock* Src,
    const llvm::BasicBlock* Dst) const

Description

Get the probability of going from Src to Dst. It returns the sum of all probabilities for edges from Src to Dst.

Declared at: llvm/include/llvm/Analysis/BranchProbabilityInfo.h:157

Parameters

const llvm::BasicBlock* Src

const llvm::BasicBlock* Dst

¶llvm::BranchProbability getEdgeProbability(
    const llvm::BasicBlock* Src,
    unsigned int IndexInSuccessors) const

Description

Get an edge's probability, relative to other out-edges of the Src. This routine provides access to the fractional probability between zero (0%) and one (100%) of this edge executing, relative to other edges leaving the 'Src' block. The returned probability is never zero, and can only be one if the source block has only one successor.

Declared at: llvm/include/llvm/Analysis/BranchProbabilityInfo.h:151

Parameters

const llvm::BasicBlock* Src

unsigned int IndexInSuccessors

¶Optional<uint32_t> getEstimatedBlockWeight(
    const llvm::BasicBlock* BB) const

Description

Returns estimated weight for \p BB. None if \p BB has no estimated weight.

Declared at: llvm/include/llvm/Analysis/BranchProbabilityInfo.h:361

Parameters

const llvm::BasicBlock* BB

¶Optional<uint32_t> getEstimatedEdgeWeight(
    const llvm::BranchProbabilityInfo::LoopEdge&
        Edge) const

Description

Return estimated weight for \p Edge. Returns None if estimated weight is unknown.

Declared at: llvm/include/llvm/Analysis/BranchProbabilityInfo.h:370

Parameters

const llvm::BranchProbabilityInfo::LoopEdge& Edge

¶Optional<uint32_t> getEstimatedLoopWeight(
    const llvm::BranchProbabilityInfo::LoopData&
        L) const

Description

Returns estimated weight to enter \p L. In other words it is weight of loop's header block not scaled by trip count. Returns None if \p L has no no estimated weight.

Declared at: llvm/include/llvm/Analysis/BranchProbabilityInfo.h:366

Parameters

const llvm::BranchProbabilityInfo::LoopData& L

¶Optional<uint32_t> getInitialEstimatedBlockWeight(
    const llvm::BasicBlock* BB)

Description

Returns block's weight encoded in the IR.

Declared at: llvm/include/llvm/Analysis/BranchProbabilityInfo.h:396

Parameters

const llvm::BasicBlock* BB

¶llvm::BranchProbabilityInfo::LoopBlock
getLoopBlock(const llvm::BasicBlock* BB) const

Description

Helper to construct LoopBlock for \p BB.

Declared at: llvm/include/llvm/Analysis/BranchProbabilityInfo.h:335

Parameters

const llvm::BasicBlock* BB

¶void getLoopEnterBlocks(
    const llvm::BranchProbabilityInfo::LoopBlock&
        LB,
    SmallVectorImpl<llvm::BasicBlock*>& Enters)
    const

Declared at: llvm/include/llvm/Analysis/BranchProbabilityInfo.h:354

Parameters

const llvm::BranchProbabilityInfo::LoopBlock& LB

SmallVectorImpl<llvm::BasicBlock*>& Enters

¶void getLoopExitBlocks(
    const llvm::BranchProbabilityInfo::LoopBlock&
        LB,
    SmallVectorImpl<llvm::BasicBlock*>& Exits)
    const

Declared at: llvm/include/llvm/Analysis/BranchProbabilityInfo.h:357

Parameters

const llvm::BranchProbabilityInfo::LoopBlock& LB

SmallVectorImpl<llvm::BasicBlock*>& Exits

¶template <class IterT>
Optional<uint32_t> getMaxEstimatedEdgeWeight(
    const llvm::BranchProbabilityInfo::LoopBlock&
        SrcBB,
    iterator_range<IterT> Successors) const

Description

Iterates over all edges leading from \p SrcBB to \p Successors and returns maximum of all estimated weights. If at least one edge has unknown estimated weight None is returned.

Declared at: llvm/include/llvm/Analysis/BranchProbabilityInfo.h:377

Templates

IterT

Parameters

const llvm::BranchProbabilityInfo::LoopBlock& SrcBB

iterator_range<IterT> Successors

¶bool invalidate(
    llvm::Function&,
    const llvm::PreservedAnalyses& PA,
    FunctionAnalysisManager::Invalidator&)

Declared at: llvm/include/llvm/Analysis/BranchProbabilityInfo.h:138

Parameters

llvm::Function&

const llvm::PreservedAnalyses& PA

FunctionAnalysisManager::Invalidator&

¶bool isEdgeHot(const llvm::BasicBlock* Src,
               const llvm::BasicBlock* Dst) const

Description

Test if an edge is hot relative to other out-edges of the Src. Check whether this edge out of the source block is 'hot'. We define hot as having a relative probability >= 80%.

Declared at: llvm/include/llvm/Analysis/BranchProbabilityInfo.h:167

Parameters

const llvm::BasicBlock* Src

const llvm::BasicBlock* Dst

¶bool isLoopBackEdge(
    const llvm::BranchProbabilityInfo::LoopEdge&
        Edge) const

Description

Returns true if source and destination blocks belongs to the same loop and destination block is loop header.

Declared at: llvm/include/llvm/Analysis/BranchProbabilityInfo.h:352

Parameters

const llvm::BranchProbabilityInfo::LoopEdge& Edge

¶bool isLoopEnteringEdge(
    const llvm::BranchProbabilityInfo::LoopEdge&
        Edge) const

Description

Returns true if destination block belongs to some loop and source block is either doesn't belong to any loop or belongs to a loop which is not inner relative to the destination block.

Declared at: llvm/include/llvm/Analysis/BranchProbabilityInfo.h:342

Parameters

const llvm::BranchProbabilityInfo::LoopEdge& Edge

¶bool isLoopEnteringExitingEdge(
    const llvm::BranchProbabilityInfo::LoopEdge&
        Edge) const

Description

Returns true if \p Edge is either enters to or exits from some loop, false in all other cases.

Declared at: llvm/include/llvm/Analysis/BranchProbabilityInfo.h:349

Parameters

const llvm::BranchProbabilityInfo::LoopEdge& Edge

¶bool isLoopExitingEdge(
    const llvm::BranchProbabilityInfo::LoopEdge&
        Edge) const

Description

Returns true if source block belongs to some loop and destination block is either doesn't belong to any loop or belongs to a loop which is not inner relative to the source block.

Declared at: llvm/include/llvm/Analysis/BranchProbabilityInfo.h:346

Parameters

const llvm::BranchProbabilityInfo::LoopEdge& Edge

¶void print(llvm::raw_ostream& OS) const

Declared at: llvm/include/llvm/Analysis/BranchProbabilityInfo.h:143

Parameters

llvm::raw_ostream& OS

¶llvm::raw_ostream& printEdgeProbability(
    llvm::raw_ostream& OS,
    const llvm::BasicBlock* Src,
    const llvm::BasicBlock* Dst) const

Description

Print an edge's probability. Retrieves an edge's probability similarly to

Declared at: llvm/include/llvm/Analysis/BranchProbabilityInfo.h:174

Parameters

llvm::raw_ostream& OS

const llvm::BasicBlock* Src

const llvm::BasicBlock* Dst

¶void propagateEstimatedBlockWeight(
    const llvm::BranchProbabilityInfo::LoopBlock&
        LoopBB,
    llvm::DominatorTree* DT,
    llvm::PostDominatorTree* PDT,
    uint32_t BBWeight,
    SmallVectorImpl<llvm::BasicBlock*>& WorkList,
    SmallVectorImpl<
        llvm::BranchProbabilityInfo::LoopBlock>&
        LoopWorkList)

Description

Starting from \p LoopBB (including \p LoopBB itself) propagate \p BBWeight up the domination tree.

Declared at: llvm/include/llvm/Analysis/BranchProbabilityInfo.h:390

Parameters

const llvm::BranchProbabilityInfo::LoopBlock& LoopBB

llvm::DominatorTree* DT

llvm::PostDominatorTree* PDT

uint32_t BBWeight

SmallVectorImpl<llvm::BasicBlock*>& WorkList

SmallVectorImpl< llvm::BranchProbabilityInfo::LoopBlock>& LoopWorkList

¶void releaseMemory()

Declared at: llvm/include/llvm/Analysis/BranchProbabilityInfo.h:141

¶void setEdgeProbability(
    const llvm::BasicBlock* Src,
    const SmallVectorImpl<
        llvm::BranchProbability>& Probs)

Description

Set the raw probabilities for all edges from the given block. This allows a pass to explicitly set edge probabilities for a block. It can be used when updating the CFG to update the branch probability information.

Declared at: llvm/include/llvm/Analysis/BranchProbabilityInfo.h:183

Parameters

const llvm::BasicBlock* Src

const SmallVectorImpl<llvm::BranchProbability>& Probs

¶bool updateEstimatedBlockWeight(
    llvm::BranchProbabilityInfo::LoopBlock&
        LoopBB,
    uint32_t BBWeight,
    SmallVectorImpl<llvm::BasicBlock*>&
        BlockWorkList,
    SmallVectorImpl<
        llvm::BranchProbabilityInfo::LoopBlock>&
        LoopWorkList)

Description

If \p LoopBB has no estimated weight then set it to \p BBWeight and return true. Otherwise \p BB's weight remains unchanged and false is returned. In addition all blocks/loops that might need their weight to be re-estimated are put into BlockWorkList/LoopWorkList.

Declared at: llvm/include/llvm/Analysis/BranchProbabilityInfo.h:384

Parameters

llvm::BranchProbabilityInfo::LoopBlock& LoopBB

uint32_t BBWeight

SmallVectorImpl<llvm::BasicBlock*>& BlockWorkList

SmallVectorImpl< llvm::BranchProbabilityInfo::LoopBlock>& LoopWorkList