LLVM  14.0.0git
Macros | Typedefs | Enumerations | Functions | Variables
BranchProbabilityInfo.cpp File Reference
#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/PostDominators.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/InitializePasses.h"
#include "llvm/Pass.h"
#include "llvm/Support/BranchProbability.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
#include <cassert>
#include <cstdint>
#include <iterator>
#include <map>
#include <utility>
Include dependency graph for BranchProbabilityInfo.cpp:

Go to the source code of this file.

Macros

#define DEBUG_TYPE   "branch-prob"
 

Typedefs

using ProbabilityList = SmallVector< BranchProbability >
 
using ProbabilityTable = std::map< CmpInst::Predicate, ProbabilityList >
 

Enumerations

enum  BlockExecWeight : std::uint32_t {
  BlockExecWeight::ZERO = 0x0, BlockExecWeight::LOWEST_NON_ZERO = 0x1, BlockExecWeight::UNREACHABLE = ZERO, BlockExecWeight::NORETURN = LOWEST_NON_ZERO,
  BlockExecWeight::UNWIND = LOWEST_NON_ZERO, BlockExecWeight::COLD = 0xffff, BlockExecWeight::DEFAULT = 0xfffff
}
 Set of dedicated "absolute" execution weights for a block. More...
 

Functions

 INITIALIZE_PASS_BEGIN (BranchProbabilityInfoWrapperPass, "branch-prob", "Branch Probability Analysis", false, true) INITIALIZE_PASS_END(BranchProbabilityInfoWrapperPass
 
static const BranchProbability PtrTakenProb (PH_TAKEN_WEIGHT, PH_TAKEN_WEIGHT+PH_NONTAKEN_WEIGHT)
 
static const BranchProbability PtrUntakenProb (PH_NONTAKEN_WEIGHT, PH_TAKEN_WEIGHT+PH_NONTAKEN_WEIGHT)
 
static const BranchProbability ZeroTakenProb (ZH_TAKEN_WEIGHT, ZH_TAKEN_WEIGHT+ZH_NONTAKEN_WEIGHT)
 
static const BranchProbability ZeroUntakenProb (ZH_NONTAKEN_WEIGHT, ZH_TAKEN_WEIGHT+ZH_NONTAKEN_WEIGHT)
 
static const BranchProbability FPOrdTakenProb (FPH_ORD_WEIGHT, FPH_ORD_WEIGHT+FPH_UNO_WEIGHT)
 
static const BranchProbability FPOrdUntakenProb (FPH_UNO_WEIGHT, FPH_ORD_WEIGHT+FPH_UNO_WEIGHT)
 
static const BranchProbability FPTakenProb (FPH_TAKEN_WEIGHT, FPH_TAKEN_WEIGHT+FPH_NONTAKEN_WEIGHT)
 
static const BranchProbability FPUntakenProb (FPH_NONTAKEN_WEIGHT, FPH_TAKEN_WEIGHT+FPH_NONTAKEN_WEIGHT)
 
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 BranchProbability UR_TAKEN_PROB = BranchProbability::getRaw(1)
 Unreachable-terminating branch taken probability. More...
 
static const uint32_t PH_TAKEN_WEIGHT = 20
 Heuristics and lookup tables for non-loop branches: Pointer Heuristics (PH) More...
 
static const uint32_t PH_NONTAKEN_WEIGHT = 12
 
static const ProbabilityTable PointerTable
 Pointer comparisons: More...
 
static const uint32_t ZH_TAKEN_WEIGHT = 20
 Zero Heuristics (ZH) More...
 
static const uint32_t ZH_NONTAKEN_WEIGHT = 12
 
static const ProbabilityTable ICmpWithZeroTable
 Integer compares with 0: More...
 
static const ProbabilityTable ICmpWithMinusOneTable
 Integer compares with -1: More...
 
static const ProbabilityTable ICmpWithOneTable
 Integer compares with 1: More...
 
static const ProbabilityTable ICmpWithLibCallTable
 strcmp and similar functions return zero, negative, or positive, if the first string is equal, less, or greater than the second. More...
 
static const uint32_t FPH_TAKEN_WEIGHT = 20
 
static const uint32_t FPH_NONTAKEN_WEIGHT = 12
 
static const uint32_t FPH_ORD_WEIGHT = 1024 * 1024 - 1
 This is the probability for an ordered floating point comparison. More...
 
static const uint32_t FPH_UNO_WEIGHT = 1
 This is the probability for an unordered floating point comparison, it means one or two of the operands are NaN. More...
 
static const ProbabilityTable FCmpTable
 Floating-Point compares: More...
 

Macro Definition Documentation

◆ DEBUG_TYPE

#define DEBUG_TYPE   "branch-prob"

Definition at line 50 of file BranchProbabilityInfo.cpp.

Typedef Documentation

◆ ProbabilityList

Definition at line 117 of file BranchProbabilityInfo.cpp.

◆ ProbabilityTable

Definition at line 118 of file BranchProbabilityInfo.cpp.

Enumeration Type Documentation

◆ BlockExecWeight

enum BlockExecWeight : std::uint32_t
strong

Set of dedicated "absolute" execution weights for a block.

These weights are meaningful relative to each other and their derivatives only.

Enumerator
ZERO 

Special weight used for cases with exact zero probability.

LOWEST_NON_ZERO 

Minimal possible non zero weight.

UNREACHABLE 

Weight to an 'unreachable' block.

NORETURN 

Weight to a block containing non returning call.

UNWIND 

Weight to 'unwind' block of an invoke instruction.

COLD 

Weight to a 'cold' block.

Cold blocks are the ones containing calls marked with attribute 'cold'.

DEFAULT 

Default weight is used in cases when there is no dedicated execution weight set.

It is not propagated through the domination line either.

Definition at line 196 of file BranchProbabilityInfo.cpp.

Function Documentation

◆ computeUnlikelySuccessors()

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

◆ FPOrdTakenProb()

static const BranchProbability FPOrdTakenProb ( FPH_ORD_WEIGHT  ,
FPH_ORD_WEIGHT FPH_UNO_WEIGHT 
)
static

◆ FPOrdUntakenProb()

static const BranchProbability FPOrdUntakenProb ( FPH_UNO_WEIGHT  ,
FPH_ORD_WEIGHT FPH_UNO_WEIGHT 
)
static

◆ FPTakenProb()

static const BranchProbability FPTakenProb ( FPH_TAKEN_WEIGHT  ,
FPH_TAKEN_WEIGHT FPH_NONTAKEN_WEIGHT 
)
static

◆ FPUntakenProb()

static const BranchProbability FPUntakenProb ( FPH_NONTAKEN_WEIGHT  ,
FPH_TAKEN_WEIGHT FPH_NONTAKEN_WEIGHT 
)
static

◆ INITIALIZE_PASS_BEGIN()

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

◆ PtrTakenProb()

static const BranchProbability PtrTakenProb ( PH_TAKEN_WEIGHT  ,
PH_TAKEN_WEIGHT PH_NONTAKEN_WEIGHT 
)
static

◆ PtrUntakenProb()

static const BranchProbability PtrUntakenProb ( PH_NONTAKEN_WEIGHT  ,
PH_TAKEN_WEIGHT PH_NONTAKEN_WEIGHT 
)
static

◆ ZeroTakenProb()

static const BranchProbability ZeroTakenProb ( ZH_TAKEN_WEIGHT  ,
ZH_TAKEN_WEIGHT ZH_NONTAKEN_WEIGHT 
)
static

◆ ZeroUntakenProb()

static const BranchProbability ZeroUntakenProb ( ZH_NONTAKEN_WEIGHT  ,
ZH_TAKEN_WEIGHT ZH_NONTAKEN_WEIGHT 
)
static

Variable Documentation

◆ Analysis

branch Branch Probability Analysis

Definition at line 68 of file BranchProbabilityInfo.cpp.

◆ false

branch Branch Probability false

Definition at line 68 of file BranchProbabilityInfo.cpp.

◆ FCmpTable

const ProbabilityTable FCmpTable
static
Initial value:
{
{FCmpInst::FCMP_ORD, {FPOrdTakenProb, FPOrdUntakenProb}},
{FCmpInst::FCMP_UNO, {FPOrdUntakenProb, FPOrdTakenProb}},
}

Floating-Point compares:

Definition at line 189 of file BranchProbabilityInfo.cpp.

◆ FPH_NONTAKEN_WEIGHT

const uint32_t FPH_NONTAKEN_WEIGHT = 12
static

Definition at line 170 of file BranchProbabilityInfo.cpp.

◆ FPH_ORD_WEIGHT

const uint32_t FPH_ORD_WEIGHT = 1024 * 1024 - 1
static

This is the probability for an ordered floating point comparison.

Definition at line 173 of file BranchProbabilityInfo.cpp.

◆ FPH_TAKEN_WEIGHT

const uint32_t FPH_TAKEN_WEIGHT = 20
static

Definition at line 169 of file BranchProbabilityInfo.cpp.

◆ FPH_UNO_WEIGHT

const uint32_t FPH_UNO_WEIGHT = 1
static

This is the probability for an unordered floating point comparison, it means one or two of the operands are NaN.

Usually it is used to test for an exceptional case, so the result is unlikely.

Definition at line 177 of file BranchProbabilityInfo.cpp.

◆ ICmpWithLibCallTable

const ProbabilityTable ICmpWithLibCallTable
static
Initial value:
{
{CmpInst::ICMP_EQ, {ZeroUntakenProb, ZeroTakenProb}},
{CmpInst::ICMP_NE, {ZeroTakenProb, ZeroUntakenProb}},
}

strcmp and similar functions return zero, negative, or positive, if the first string is equal, less, or greater than the second.

We consider it likely that the strings are not equal, so a comparison with zero is probably false, but also a comparison with any other number is also probably false given that what exactly is returned for nonzero values is not specified. Any kind of comparison other than equality we know nothing about.

Definition at line 163 of file BranchProbabilityInfo.cpp.

◆ ICmpWithMinusOneTable

const ProbabilityTable ICmpWithMinusOneTable
static
Initial value:
{
{CmpInst::ICMP_EQ, {ZeroUntakenProb, ZeroTakenProb}},
{CmpInst::ICMP_NE, {ZeroTakenProb, ZeroUntakenProb}},
{CmpInst::ICMP_SGT, {ZeroTakenProb, ZeroUntakenProb}},
}

Integer compares with -1:

Definition at line 143 of file BranchProbabilityInfo.cpp.

◆ ICmpWithOneTable

const ProbabilityTable ICmpWithOneTable
static
Initial value:
{
{CmpInst::ICMP_SLT, {ZeroUntakenProb, ZeroTakenProb}},
}

Integer compares with 1:

Definition at line 151 of file BranchProbabilityInfo.cpp.

◆ ICmpWithZeroTable

const ProbabilityTable ICmpWithZeroTable
static
Initial value:
{
{CmpInst::ICMP_EQ, {ZeroUntakenProb, ZeroTakenProb}},
{CmpInst::ICMP_NE, {ZeroTakenProb, ZeroUntakenProb}},
{CmpInst::ICMP_SLT, {ZeroUntakenProb, ZeroTakenProb}},
{CmpInst::ICMP_SGT, {ZeroTakenProb, ZeroUntakenProb}},
}

Integer compares with 0:

Definition at line 135 of file BranchProbabilityInfo.cpp.

◆ LBH_NONTAKEN_WEIGHT

const uint32_t LBH_NONTAKEN_WEIGHT = 4
static

Definition at line 99 of file BranchProbabilityInfo.cpp.

◆ LBH_TAKEN_WEIGHT

const uint32_t LBH_TAKEN_WEIGHT = 124
static

Definition at line 98 of file BranchProbabilityInfo.cpp.

◆ PH_NONTAKEN_WEIGHT

const uint32_t PH_NONTAKEN_WEIGHT = 12
static

Definition at line 111 of file BranchProbabilityInfo.cpp.

◆ PH_TAKEN_WEIGHT

const uint32_t PH_TAKEN_WEIGHT = 20
static

Heuristics and lookup tables for non-loop branches: Pointer Heuristics (PH)

Definition at line 110 of file BranchProbabilityInfo.cpp.

◆ PointerTable

const ProbabilityTable PointerTable
static
Initial value:
{
{ICmpInst::ICMP_NE, {PtrTakenProb, PtrUntakenProb}},
{ICmpInst::ICMP_EQ, {PtrUntakenProb, PtrTakenProb}},
}

Pointer comparisons:

Definition at line 121 of file BranchProbabilityInfo.cpp.

◆ PrintBranchProb

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

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

◆ prob

branch prob

Definition at line 67 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 proportionally share the remaining part.

Definition at line 106 of file BranchProbabilityInfo.cpp.

◆ ZH_NONTAKEN_WEIGHT

const uint32_t ZH_NONTAKEN_WEIGHT = 12
static

Definition at line 128 of file BranchProbabilityInfo.cpp.

◆ ZH_TAKEN_WEIGHT

const uint32_t ZH_TAKEN_WEIGHT = 20
static

Zero Heuristics (ZH)

Definition at line 127 of file BranchProbabilityInfo.cpp.

FPOrdUntakenProb
static const BranchProbability FPOrdUntakenProb(FPH_UNO_WEIGHT, FPH_ORD_WEIGHT+FPH_UNO_WEIGHT)
FPOrdTakenProb
static const BranchProbability FPOrdTakenProb(FPH_ORD_WEIGHT, FPH_ORD_WEIGHT+FPH_UNO_WEIGHT)
ZeroTakenProb
static const BranchProbability ZeroTakenProb(ZH_TAKEN_WEIGHT, ZH_TAKEN_WEIGHT+ZH_NONTAKEN_WEIGHT)
PtrTakenProb
static const BranchProbability PtrTakenProb(PH_TAKEN_WEIGHT, PH_TAKEN_WEIGHT+PH_NONTAKEN_WEIGHT)
PtrUntakenProb
static const BranchProbability PtrUntakenProb(PH_NONTAKEN_WEIGHT, PH_TAKEN_WEIGHT+PH_NONTAKEN_WEIGHT)
ZeroUntakenProb
static const BranchProbability ZeroUntakenProb(ZH_NONTAKEN_WEIGHT, ZH_TAKEN_WEIGHT+ZH_NONTAKEN_WEIGHT)