#include "llvm/Analysis/BranchProbabilityInfo.h"
#include "llvm/ADT/PostOrderIterator.h"
#include "llvm/ADT/SCCIterator.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/TargetLibraryInfo.h"
#include "llvm/IR/Attributes.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/CFG.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/InstrTypes.h"
#include "llvm/IR/Instruction.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/LLVMContext.h"
#include "llvm/IR/Metadata.h"
#include "llvm/IR/PassManager.h"
#include "llvm/IR/Type.h"
#include "llvm/IR/Value.h"
#include "llvm/Pass.h"
#include "llvm/Support/BranchProbability.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
#include <cassert>
#include <cstdint>
#include <iterator>
#include <utility>

Include dependency graph for BranchProbabilityInfo.cpp:

Macros
#define	DEBUG_TYPE "branch-prob"

Functions
	INITIALIZE_PASS_BEGIN (BranchProbabilityInfoWrapperPass, "branch-prob", "Branch Probability Analysis", false, true) INITIALIZE_PASS_END(BranchProbabilityInfoWrapperPass

static int	getSCCNum (const BasicBlock *BB, const BranchProbabilityInfo::SccInfo &SccI)

static bool	isSCCHeader (const BasicBlock *BB, int SccNum, BranchProbabilityInfo::SccInfo &SccI)

static void	computeUnlikelySuccessors (const BasicBlock BB, Loop L, SmallPtrSetImpl< const BasicBlock *> &UnlikelyBlocks)

Variables
static cl::opt< bool >	PrintBranchProb ("print-bpi", cl::init(false), cl::Hidden, cl::desc("Print the branch probability info."))

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."))

branch	prob

branch Branch Probability	Analysis

branch Branch Probability	false

static const uint32_t	LBH_TAKEN_WEIGHT = 124

static const uint32_t	LBH_NONTAKEN_WEIGHT = 4

static const uint32_t	LBH_UNLIKELY_WEIGHT = 62

static const BranchProbability	UR_TAKEN_PROB = BranchProbability::getRaw(1)
	Unreachable-terminating branch taken probability. More...

static const uint32_t	CC_TAKEN_WEIGHT = 4
	Weight for a branch taken going into a cold block. More...

static const uint32_t	CC_NONTAKEN_WEIGHT = 64
	Weight for a branch not-taken into a cold block. More...

static const uint32_t	PH_TAKEN_WEIGHT = 20

static const uint32_t	PH_NONTAKEN_WEIGHT = 12

static const uint32_t	ZH_TAKEN_WEIGHT = 20

static const uint32_t	ZH_NONTAKEN_WEIGHT = 12

static const uint32_t	FPH_TAKEN_WEIGHT = 20

static const uint32_t	FPH_NONTAKEN_WEIGHT = 12

static const uint32_t	IH_TAKEN_WEIGHT = 1024 * 1024 - 1
	Invoke-terminating normal branch taken weight. More...

static const uint32_t	IH_NONTAKEN_WEIGHT = 1
	Invoke-terminating normal branch not-taken weight. More...

Macro Definition Documentation

◆ DEBUG_TYPE

#define DEBUG_TYPE "branch-prob"

Definition at line 47 of file BranchProbabilityInfo.cpp.

Function Documentation

◆ computeUnlikelySuccessors()

static void computeUnlikelySuccessors	(	const BasicBlock *	BB,
		Loop *	L,
		SmallPtrSetImpl< const BasicBlock *> &	UnlikelyBlocks
	)

static

Definition at line 463 of file BranchProbabilityInfo.cpp.

References B, llvm::SmallVectorTemplateCommon< T >::back(), llvm::PHINode::blocks(), llvm::LoopBase< BlockT, LoopT >::contains(), llvm::SmallPtrSetImpl< PtrType >::count(), llvm::dyn_cast(), E, llvm::SmallVectorBase::empty(), llvm::CmpInst::FCMP_ORD, llvm::CmpInst::FCMP_UNO, llvm::find(), FPH_NONTAKEN_WEIGHT, FPH_TAKEN_WEIGHT, llvm::ConstantExpr::get(), llvm::ConstantExpr::getCompare(), llvm::BranchProbability::getCompl(), llvm::BranchInst::getCondition(), llvm::LoopBase< BlockT, LoopT >::getHeader(), llvm::PHINode::getIncomingValueForBlock(), llvm::TargetLibraryInfo::getLibFunc(), llvm::LoopInfoBase< BlockT, LoopT >::getLoopFor(), llvm::User::getOperand(), llvm::CmpInst::getPredicate(), getSCCNum(), llvm::BranchInst::getSuccessor(), llvm::BasicBlock::getTerminator(), I, llvm::CmpInst::ICMP_EQ, llvm::CmpInst::ICMP_NE, llvm::CmpInst::ICMP_SGT, llvm::CmpInst::ICMP_SLT, IH_NONTAKEN_WEIGHT, IH_TAKEN_WEIGHT, llvm::SmallPtrSetImpl< PtrType >::insert(), llvm::BranchInst::isConditional(), llvm::FCmpInst::isEquality(), llvm::ConstantInt::isMinusOne(), llvm::ConstantInt::isOne(), llvm::Constant::isOneValue(), isSCCHeader(), llvm::CmpInst::isTrueWhenEqual(), llvm::ConstantInt::isZero(), llvm::Constant::isZeroValue(), LBH_NONTAKEN_WEIGHT, LBH_TAKEN_WEIGHT, LBH_UNLIKELY_WEIGHT, llvm::NumLibFuncs, P, llvm::SmallVectorTemplateBase< T >::pop_back(), llvm::SmallVectorTemplateBase< T >::push_back(), llvm::SmallVectorTemplateBase< T, bool >::push_back(), llvm::reverse(), llvm::BranchProbabilityInfo::setEdgeProbability(), llvm::SmallVectorBase::size(), llvm::succ_begin(), llvm::succ_end(), std::swap(), ZH_NONTAKEN_WEIGHT, and ZH_TAKEN_WEIGHT.

◆ getSCCNum()

static int getSCCNum	(	const BasicBlock *	BB,
		const BranchProbabilityInfo::SccInfo &	SccI
	)

static

Definition at line 427 of file BranchProbabilityInfo.cpp.

References llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::end(), llvm::DenseMapBase< DerivedT, KeyT, ValueT, KeyInfoT, BucketT >::find(), and llvm::BranchProbabilityInfo::SccInfo::SccNums.

Referenced by computeUnlikelySuccessors(), and isSCCHeader().

◆ INITIALIZE_PASS_BEGIN()

INITIALIZE_PASS_BEGIN	(	BranchProbabilityInfoWrapperPass	,
		"branch-prob"	,
		"Branch Probability Analysis"	,
		false	,
		true
	)

◆ isSCCHeader()

static bool isSCCHeader	(	const BasicBlock *	BB,
		int	SccNum,
		BranchProbabilityInfo::SccInfo &	SccI
	)

static

Definition at line 436 of file BranchProbabilityInfo.cpp.

References llvm::any_of(), assert(), getSCCNum(), llvm::make_range(), llvm::pred_begin(), llvm::pred_end(), and llvm::BranchProbabilityInfo::SccInfo::SccHeaders.

Referenced by computeUnlikelySuccessors().

Variable Documentation

◆ Analysis

branch Branch Probability Analysis

Definition at line 62 of file BranchProbabilityInfo.cpp.

◆ CC_NONTAKEN_WEIGHT

const uint32_t CC_NONTAKEN_WEIGHT = 64

static

Weight for a branch not-taken into a cold block.

This is the weight for a branch not taken toward a block marked cold.

Definition at line 111 of file BranchProbabilityInfo.cpp.

◆ CC_TAKEN_WEIGHT

const uint32_t CC_TAKEN_WEIGHT = 4

static

Weight for a branch taken going into a cold block.

This is the weight for a branch taken toward a block marked cold. A block is marked cold if it's postdominated by a block containing a call to a cold function. Cold functions are those marked with attribute 'cold'.

Definition at line 105 of file BranchProbabilityInfo.cpp.

◆ false

branch Branch Probability false

Definition at line 62 of file BranchProbabilityInfo.cpp.

◆ FPH_NONTAKEN_WEIGHT

const uint32_t FPH_NONTAKEN_WEIGHT = 12

static

Definition at line 120 of file BranchProbabilityInfo.cpp.

Referenced by computeUnlikelySuccessors().

◆ FPH_TAKEN_WEIGHT

const uint32_t FPH_TAKEN_WEIGHT = 20

static

Definition at line 119 of file BranchProbabilityInfo.cpp.

Referenced by computeUnlikelySuccessors().

◆ IH_NONTAKEN_WEIGHT

const uint32_t IH_NONTAKEN_WEIGHT = 1

static

Invoke-terminating normal branch not-taken weight.

This is the weight for branching to the unwind destination of an invoke instruction. This is essentially never taken.

Definition at line 133 of file BranchProbabilityInfo.cpp.

Referenced by computeUnlikelySuccessors().

◆ IH_TAKEN_WEIGHT

const uint32_t IH_TAKEN_WEIGHT = 1024 * 1024 - 1

static

Invoke-terminating normal branch taken weight.

This is the weight for branching to the normal destination of an invoke instruction. We expect this to happen most of the time. Set the weight to an absurdly high value so that nested loops subsume it.

Definition at line 127 of file BranchProbabilityInfo.cpp.

Referenced by computeUnlikelySuccessors().

◆ LBH_NONTAKEN_WEIGHT

const uint32_t LBH_NONTAKEN_WEIGHT = 4

static

Definition at line 88 of file BranchProbabilityInfo.cpp.

Referenced by computeUnlikelySuccessors().

◆ LBH_TAKEN_WEIGHT

const uint32_t LBH_TAKEN_WEIGHT = 124

static

Definition at line 87 of file BranchProbabilityInfo.cpp.

Referenced by computeUnlikelySuccessors().

◆ LBH_UNLIKELY_WEIGHT

const uint32_t LBH_UNLIKELY_WEIGHT = 62

static

Definition at line 90 of file BranchProbabilityInfo.cpp.

Referenced by computeUnlikelySuccessors().

◆ PH_NONTAKEN_WEIGHT

const uint32_t PH_NONTAKEN_WEIGHT = 12

static

Definition at line 114 of file BranchProbabilityInfo.cpp.

◆ PH_TAKEN_WEIGHT

const uint32_t PH_TAKEN_WEIGHT = 20

static

Definition at line 113 of file BranchProbabilityInfo.cpp.

◆ PrintBranchProb

cl::opt<bool> PrintBranchProb("print-bpi", cl::init(false), cl::Hidden, cl::desc("Print the branch probability info."))

static

Referenced by llvm::BranchProbabilityInfo::calculate().

◆ PrintBranchProbFuncName

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."))

Referenced by llvm::BranchProbabilityInfo::calculate().

◆ prob

branch prob

Definition at line 62 of file BranchProbabilityInfo.cpp.

◆ UR_TAKEN_PROB

const BranchProbability UR_TAKEN_PROB = BranchProbability::getRaw(1)

static

Unreachable-terminating branch taken probability.

This is the probability for a branch being taken to a block that terminates (eventually) in unreachable. These are predicted as unlikely as possible. All reachable probability will equally share the remaining part.

Definition at line 97 of file BranchProbabilityInfo.cpp.

◆ ZH_NONTAKEN_WEIGHT

const uint32_t ZH_NONTAKEN_WEIGHT = 12

static

Definition at line 117 of file BranchProbabilityInfo.cpp.

Referenced by computeUnlikelySuccessors().

◆ ZH_TAKEN_WEIGHT

const uint32_t ZH_TAKEN_WEIGHT = 20

static

Definition at line 116 of file BranchProbabilityInfo.cpp.

Referenced by computeUnlikelySuccessors().

Macros

Functions

Variables

Macro Definition Documentation

◆ DEBUG_TYPE

Function Documentation

◆ computeUnlikelySuccessors()

◆ getSCCNum()

◆ INITIALIZE_PASS_BEGIN()

◆ isSCCHeader()

Variable Documentation

◆ Analysis

◆ CC_NONTAKEN_WEIGHT

◆ CC_TAKEN_WEIGHT

◆ false

◆ FPH_NONTAKEN_WEIGHT

◆ FPH_TAKEN_WEIGHT

◆ IH_NONTAKEN_WEIGHT

◆ IH_TAKEN_WEIGHT

◆ LBH_NONTAKEN_WEIGHT

◆ LBH_TAKEN_WEIGHT

◆ LBH_UNLIKELY_WEIGHT

◆ PH_NONTAKEN_WEIGHT

◆ PH_TAKEN_WEIGHT

◆ PrintBranchProb

◆ PrintBranchProbFuncName

◆ prob

◆ UR_TAKEN_PROB

◆ ZH_NONTAKEN_WEIGHT

◆ ZH_TAKEN_WEIGHT