Analysis providing branch probability information. More...

#include "llvm/Analysis/BranchProbabilityInfo.h"

Classes
class	SccInfo

Public Member Functions
	BranchProbabilityInfo ()=default

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

	BranchProbabilityInfo (BranchProbabilityInfo &&Arg)

	BranchProbabilityInfo (const BranchProbabilityInfo &)=delete

BranchProbabilityInfo &	operator= (const BranchProbabilityInfo &)=delete

BranchProbabilityInfo &	operator= (BranchProbabilityInfo &&RHS)

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

void	releaseMemory ()

void	print (raw_ostream &OS) const

BranchProbability	getEdgeProbability (const BasicBlock *Src, unsigned IndexInSuccessors) const
	Get an edge's probability, relative to other out-edges of the Src.

BranchProbability	getEdgeProbability (const BasicBlock Src, const BasicBlock Dst) const
	Get the probability of going from Src to Dst.

BranchProbability	getEdgeProbability (const BasicBlock *Src, const_succ_iterator Dst) const

bool	isEdgeHot (const BasicBlock Src, const BasicBlock Dst) const
	Test if an edge is hot relative to other out-edges of the Src.

raw_ostream &	printEdgeProbability (raw_ostream &OS, const BasicBlock Src, const BasicBlock Dst) const
	Print an edge's probability.

void	setEdgeProbability (const BasicBlock *Src, const SmallVectorImpl< BranchProbability > &Probs)
	Set the raw probabilities for all edges from the given block.

void	copyEdgeProbabilities (BasicBlock Src, BasicBlock Dst)
	Copy outgoing edge probabilities from `Src` to `Dst`.

void	swapSuccEdgesProbabilities (const BasicBlock *Src)
	Swap outgoing edges probabilities for `Src` with branch terminator.

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

void	eraseBlock (const BasicBlock *BB)
	Forget analysis results for the given basic block.

Static Public Member Functions
static BranchProbability	getBranchProbStackProtector (bool IsLikely)

Detailed 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.

Definition at line 112 of file BranchProbabilityInfo.h.

Constructor & Destructor Documentation

◆ BranchProbabilityInfo() [1/4]

llvm::BranchProbabilityInfo::BranchProbabilityInfo ( )

default

◆ BranchProbabilityInfo() [2/4]

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

inline

Definition at line 116 of file BranchProbabilityInfo.h.

References calculate(), and F.

◆ BranchProbabilityInfo() [3/4]

llvm::BranchProbabilityInfo::BranchProbabilityInfo ( BranchProbabilityInfo && Arg )

inline

Definition at line 123 of file BranchProbabilityInfo.h.

◆ BranchProbabilityInfo() [4/4]

llvm::BranchProbabilityInfo::BranchProbabilityInfo ( const BranchProbabilityInfo & )

delete

Member Function Documentation

◆ calculate()

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

Definition at line 1222 of file BranchProbabilityInfo.cpp.

References assert(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::clear(), llvm::dbgs(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::empty(), F, llvm::Value::getName(), llvm::Instruction::getNumSuccessors(), llvm::BasicBlock::getTerminator(), LLVM_DEBUG, llvm::post_order(), print(), PrintBranchProb, and PrintBranchProbFuncName.

Referenced by BranchProbabilityInfo(), and llvm::BranchProbabilityAnalysis::run().

◆ copyEdgeProbabilities()

void BranchProbabilityInfo::copyEdgeProbabilities	(	BasicBlock *	Src,
		BasicBlock *	Dst
	)

Copy outgoing edge probabilities from Src to Dst.

This allows to keep probabilities unset for the destination if they were unset for source.

Definition at line 1158 of file BranchProbabilityInfo.cpp.

References assert(), llvm::dbgs(), eraseBlock(), and LLVM_DEBUG.

Referenced by llvm::JumpThreadingPass::duplicateCondBranchOnPHIIntoPred().

◆ eraseBlock()

void BranchProbabilityInfo::eraseBlock ( const BasicBlock * BB )

Forget analysis results for the given basic block.

Definition at line 1200 of file BranchProbabilityInfo.cpp.

References assert(), llvm::dbgs(), llvm::Value::getName(), I, and LLVM_DEBUG.

Referenced by copyEdgeProbabilities(), setEdgeProbability(), and llvm::SplitIndirectBrCriticalEdges().

◆ getBranchProbStackProtector()

static BranchProbability llvm::BranchProbabilityInfo::getBranchProbStackProtector ( bool IsLikely )

inlinestatic

Definition at line 201 of file BranchProbabilityInfo.h.

References llvm::BranchProbability::getCompl().

Referenced by InsertStackProtectors().

◆ getEdgeProbability() [1/3]

BranchProbability BranchProbabilityInfo::getEdgeProbability	(	const BasicBlock *	Src,
		const BasicBlock *	Dst
	)		const

Get the probability of going from Src to Dst.

Get the raw edge probability calculated for the block pair.

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

This returns the sum of all raw edge probabilities from Src to Dst.

Definition at line 1117 of file BranchProbabilityInfo.cpp.

References llvm::count(), llvm::BranchProbability::getZero(), I, llvm::succ_begin(), llvm::succ_end(), llvm::succ_size(), and llvm::successors().

◆ getEdgeProbability() [2/3]

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

Definition at line 1109 of file BranchProbabilityInfo.cpp.

References getEdgeProbability().

◆ getEdgeProbability() [3/3]

BranchProbability BranchProbabilityInfo::getEdgeProbability	(	const BasicBlock *	Src,
		unsigned	IndexInSuccessors
	)		const

Get an edge's probability, relative to other out-edges of the Src.

Get the raw edge probability for the edge.

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.

If can't find it, return a default probability 1/N where N is the number of successors. Here an edge is specified using PredBlock and an index to the successors.

Definition at line 1094 of file BranchProbabilityInfo.cpp.

References assert(), I, and llvm::succ_size().

Referenced by llvm::CodeExtractor::extractCodeRegion(), llvm::FastISel::fastEmitBranch(), findUnwindDestinations(), llvm::FastISel::finishCondBranch(), getBranchHint(), llvm::DOTGraphTraits< DOTFuncInfo * >::getEdgeAttributes(), getEdgeProbability(), isEdgeHot(), printEdgeProbability(), and llvm::SplitIndirectBrCriticalEdges().

◆ invalidate()

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

Definition at line 1062 of file BranchProbabilityInfo.cpp.

References llvm::PreservedAnalyses::getChecker().

◆ isEdgeHot()

bool BranchProbabilityInfo::isEdgeHot	(	const BasicBlock *	Src,
		const BasicBlock *	Dst
	)		const

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%.

Definition at line 1082 of file BranchProbabilityInfo.cpp.

References getEdgeProbability().

Referenced by printEdgeProbability(), and llvm::SelectionDAGBuilder::shouldKeepJumpConditionsTogether().

◆ operator=() [1/2]

BranchProbabilityInfo & llvm::BranchProbabilityInfo::operator= ( BranchProbabilityInfo && RHS )

inline

Definition at line 134 of file BranchProbabilityInfo.h.

References releaseMemory(), and RHS.

◆ operator=() [2/2]

BranchProbabilityInfo & llvm::BranchProbabilityInfo::operator= ( const BranchProbabilityInfo & )

delete

◆ print()

void BranchProbabilityInfo::print ( raw_ostream & OS ) const

Definition at line 1071 of file BranchProbabilityInfo.cpp.

References assert(), OS, printEdgeProbability(), and llvm::successors().

Referenced by calculate(), and llvm::BranchProbabilityPrinterPass::run().

◆ printEdgeProbability()

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

Print an edge's probability.

Retrieves an edge's probability similarly to

See also: getEdgeProbability, but then prints that probability to the provided stream. That stream is then returned.

Definition at line 1186 of file BranchProbabilityInfo.cpp.

References getEdgeProbability(), isEdgeHot(), and OS.

Referenced by print().

◆ releaseMemory()

void BranchProbabilityInfo::releaseMemory ( )

Definition at line 1057 of file BranchProbabilityInfo.cpp.

Referenced by operator=().

◆ setEdgeProbability()

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

Set the raw probabilities for all edges from the given block.

Set the edge probability for all edges at once.

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.

Definition at line 1131 of file BranchProbabilityInfo.cpp.

References assert(), llvm::dbgs(), eraseBlock(), llvm::BranchProbability::getDenominator(), LLVM_DEBUG, and llvm::SmallVectorBase< Size_T >::size().

Referenced by llvm::SplitIndirectBrCriticalEdges(), and llvm::JumpThreadingPass::unfoldSelectInstr().