BranchProbabilityInfo.h revision 360784
1//===- BranchProbabilityInfo.h - Branch Probability Analysis ----*- C++ -*-===// 2// 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 6// 7//===----------------------------------------------------------------------===// 8// 9// This pass is used to evaluate branch probabilties. 10// 11//===----------------------------------------------------------------------===// 12 13#ifndef LLVM_ANALYSIS_BRANCHPROBABILITYINFO_H 14#define LLVM_ANALYSIS_BRANCHPROBABILITYINFO_H 15 16#include "llvm/ADT/DenseMap.h" 17#include "llvm/ADT/DenseMapInfo.h" 18#include "llvm/ADT/DenseSet.h" 19#include "llvm/ADT/SmallPtrSet.h" 20#include "llvm/IR/BasicBlock.h" 21#include "llvm/IR/CFG.h" 22#include "llvm/IR/PassManager.h" 23#include "llvm/IR/ValueHandle.h" 24#include "llvm/Pass.h" 25#include "llvm/Support/BranchProbability.h" 26#include "llvm/Support/Casting.h" 27#include <algorithm> 28#include <cassert> 29#include <cstdint> 30#include <utility> 31 32namespace llvm { 33 34class Function; 35class LoopInfo; 36class raw_ostream; 37class PostDominatorTree; 38class TargetLibraryInfo; 39class Value; 40 41/// Analysis providing branch probability information. 42/// 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 52/// value 10. 53class BranchProbabilityInfo { 54public: 55 BranchProbabilityInfo() = default; 56 57 BranchProbabilityInfo(const Function &F, const LoopInfo &LI, 58 const TargetLibraryInfo *TLI = nullptr) { 59 calculate(F, LI, TLI); 60 } 61 62 BranchProbabilityInfo(BranchProbabilityInfo &&Arg) 63 : Probs(std::move(Arg.Probs)), LastF(Arg.LastF), 64 PostDominatedByUnreachable(std::move(Arg.PostDominatedByUnreachable)), 65 PostDominatedByColdCall(std::move(Arg.PostDominatedByColdCall)) {} 66 67 BranchProbabilityInfo(const BranchProbabilityInfo &) = delete; 68 BranchProbabilityInfo &operator=(const BranchProbabilityInfo &) = delete; 69 70 BranchProbabilityInfo &operator=(BranchProbabilityInfo &&RHS) { 71 releaseMemory(); 72 Probs = std::move(RHS.Probs); 73 PostDominatedByColdCall = std::move(RHS.PostDominatedByColdCall); 74 PostDominatedByUnreachable = std::move(RHS.PostDominatedByUnreachable); 75 return *this; 76 } 77 78 void releaseMemory(); 79 80 void print(raw_ostream &OS) const; 81 82 /// Get an edge's probability, relative to other out-edges of the Src. 83 /// 84 /// This routine provides access to the fractional probability between zero 85 /// (0%) and one (100%) of this edge executing, relative to other edges 86 /// leaving the 'Src' block. The returned probability is never zero, and can 87 /// only be one if the source block has only one successor. 88 BranchProbability getEdgeProbability(const BasicBlock *Src, 89 unsigned IndexInSuccessors) const; 90 91 /// Get the probability of going from Src to Dst. 92 /// 93 /// It returns the sum of all probabilities for edges from Src to Dst. 94 BranchProbability getEdgeProbability(const BasicBlock *Src, 95 const BasicBlock *Dst) const; 96 97 BranchProbability getEdgeProbability(const BasicBlock *Src, 98 succ_const_iterator Dst) const; 99 100 /// Test if an edge is hot relative to other out-edges of the Src. 101 /// 102 /// Check whether this edge out of the source block is 'hot'. We define hot 103 /// as having a relative probability >= 80%. 104 bool isEdgeHot(const BasicBlock *Src, const BasicBlock *Dst) const; 105 106 /// Retrieve the hot successor of a block if one exists. 107 /// 108 /// Given a basic block, look through its successors and if one exists for 109 /// which \see isEdgeHot would return true, return that successor block. 110 const BasicBlock *getHotSucc(const BasicBlock *BB) const; 111 112 /// Print an edge's probability. 113 /// 114 /// Retrieves an edge's probability similarly to \see getEdgeProbability, but 115 /// then prints that probability to the provided stream. That stream is then 116 /// returned. 117 raw_ostream &printEdgeProbability(raw_ostream &OS, const BasicBlock *Src, 118 const BasicBlock *Dst) const; 119 120 /// Set the raw edge probability for the given edge. 121 /// 122 /// This allows a pass to explicitly set the edge probability for an edge. It 123 /// can be used when updating the CFG to update and preserve the branch 124 /// probability information. Read the implementation of how these edge 125 /// probabilities are calculated carefully before using! 126 void setEdgeProbability(const BasicBlock *Src, unsigned IndexInSuccessors, 127 BranchProbability Prob); 128 129 static BranchProbability getBranchProbStackProtector(bool IsLikely) { 130 static const BranchProbability LikelyProb((1u << 20) - 1, 1u << 20); 131 return IsLikely ? LikelyProb : LikelyProb.getCompl(); 132 } 133 134 void calculate(const Function &F, const LoopInfo &LI, 135 const TargetLibraryInfo *TLI = nullptr); 136 137 /// Forget analysis results for the given basic block. 138 void eraseBlock(const BasicBlock *BB); 139 140 // Use to track SCCs for handling irreducible loops. 141 using SccMap = DenseMap<const BasicBlock *, int>; 142 using SccHeaderMap = DenseMap<const BasicBlock *, bool>; 143 using SccHeaderMaps = std::vector<SccHeaderMap>; 144 struct SccInfo { 145 SccMap SccNums; 146 SccHeaderMaps SccHeaders; 147 }; 148 149private: 150 // We need to store CallbackVH's in order to correctly handle basic block 151 // removal. 152 class BasicBlockCallbackVH final : public CallbackVH { 153 BranchProbabilityInfo *BPI; 154 155 void deleted() override { 156 assert(BPI != nullptr); 157 BPI->eraseBlock(cast<BasicBlock>(getValPtr())); 158 BPI->Handles.erase(*this); 159 } 160 161 public: 162 BasicBlockCallbackVH(const Value *V, BranchProbabilityInfo *BPI = nullptr) 163 : CallbackVH(const_cast<Value *>(V)), BPI(BPI) {} 164 }; 165 166 DenseSet<BasicBlockCallbackVH, DenseMapInfo<Value*>> Handles; 167 168 // Since we allow duplicate edges from one basic block to another, we use 169 // a pair (PredBlock and an index in the successors) to specify an edge. 170 using Edge = std::pair<const BasicBlock *, unsigned>; 171 172 // Default weight value. Used when we don't have information about the edge. 173 // TODO: DEFAULT_WEIGHT makes sense during static predication, when none of 174 // the successors have a weight yet. But it doesn't make sense when providing 175 // weight to an edge that may have siblings with non-zero weights. This can 176 // be handled various ways, but it's probably fine for an edge with unknown 177 // weight to just "inherit" the non-zero weight of an adjacent successor. 178 static const uint32_t DEFAULT_WEIGHT = 16; 179 180 DenseMap<Edge, BranchProbability> Probs; 181 182 /// Track the last function we run over for printing. 183 const Function *LastF = nullptr; 184 185 /// Track the set of blocks directly succeeded by a returning block. 186 SmallPtrSet<const BasicBlock *, 16> PostDominatedByUnreachable; 187 188 /// Track the set of blocks that always lead to a cold call. 189 SmallPtrSet<const BasicBlock *, 16> PostDominatedByColdCall; 190 191 void computePostDominatedByUnreachable(const Function &F, 192 PostDominatorTree *PDT); 193 void computePostDominatedByColdCall(const Function &F, 194 PostDominatorTree *PDT); 195 bool calcUnreachableHeuristics(const BasicBlock *BB); 196 bool calcMetadataWeights(const BasicBlock *BB); 197 bool calcColdCallHeuristics(const BasicBlock *BB); 198 bool calcPointerHeuristics(const BasicBlock *BB); 199 bool calcLoopBranchHeuristics(const BasicBlock *BB, const LoopInfo &LI, 200 SccInfo &SccI); 201 bool calcZeroHeuristics(const BasicBlock *BB, const TargetLibraryInfo *TLI); 202 bool calcFloatingPointHeuristics(const BasicBlock *BB); 203 bool calcInvokeHeuristics(const BasicBlock *BB); 204}; 205 206/// Analysis pass which computes \c BranchProbabilityInfo. 207class BranchProbabilityAnalysis 208 : public AnalysisInfoMixin<BranchProbabilityAnalysis> { 209 friend AnalysisInfoMixin<BranchProbabilityAnalysis>; 210 211 static AnalysisKey Key; 212 213public: 214 /// Provide the result type for this analysis pass. 215 using Result = BranchProbabilityInfo; 216 217 /// Run the analysis pass over a function and produce BPI. 218 BranchProbabilityInfo run(Function &F, FunctionAnalysisManager &AM); 219}; 220 221/// Printer pass for the \c BranchProbabilityAnalysis results. 222class BranchProbabilityPrinterPass 223 : public PassInfoMixin<BranchProbabilityPrinterPass> { 224 raw_ostream &OS; 225 226public: 227 explicit BranchProbabilityPrinterPass(raw_ostream &OS) : OS(OS) {} 228 229 PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); 230}; 231 232/// Legacy analysis pass which computes \c BranchProbabilityInfo. 233class BranchProbabilityInfoWrapperPass : public FunctionPass { 234 BranchProbabilityInfo BPI; 235 236public: 237 static char ID; 238 239 BranchProbabilityInfoWrapperPass(); 240 241 BranchProbabilityInfo &getBPI() { return BPI; } 242 const BranchProbabilityInfo &getBPI() const { return BPI; } 243 244 void getAnalysisUsage(AnalysisUsage &AU) const override; 245 bool runOnFunction(Function &F) override; 246 void releaseMemory() override; 247 void print(raw_ostream &OS, const Module *M = nullptr) const override; 248}; 249 250} // end namespace llvm 251 252#endif // LLVM_ANALYSIS_BRANCHPROBABILITYINFO_H 253