1//===--- BranchProbabilityInfo.h - Branch Probability Analysis --*- C++ -*-===//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// This pass is used to evaluate branch probabilties.
11//
12//===----------------------------------------------------------------------===//
13
14#ifndef LLVM_ANALYSIS_BRANCHPROBABILITYINFO_H
15#define LLVM_ANALYSIS_BRANCHPROBABILITYINFO_H
16
17#include "llvm/ADT/DenseMap.h"
18#include "llvm/ADT/SmallPtrSet.h"
19#include "llvm/IR/CFG.h"
20#include "llvm/IR/PassManager.h"
21#include "llvm/InitializePasses.h"
22#include "llvm/Pass.h"
23#include "llvm/Support/BranchProbability.h"
24
25namespace llvm {
26class LoopInfo;
27class raw_ostream;
28
29/// \brief Analysis providing branch probability information.
30///
31/// This is a function analysis which provides information on the relative
32/// probabilities of each "edge" in the function's CFG where such an edge is
33/// defined by a pair (PredBlock and an index in the successors). The
34/// probability of an edge from one block is always relative to the
35/// probabilities of other edges from the block. The probabilites of all edges
36/// from a block sum to exactly one (100%).
37/// We use a pair (PredBlock and an index in the successors) to uniquely
38/// identify an edge, since we can have multiple edges from Src to Dst.
39/// As an example, we can have a switch which jumps to Dst with value 0 and
40/// value 10.
41class BranchProbabilityInfo {
42public:
43  BranchProbabilityInfo() {}
44  BranchProbabilityInfo(const Function &F, const LoopInfo &LI) {
45    calculate(F, LI);
46  }
47
48  BranchProbabilityInfo(BranchProbabilityInfo &&Arg)
49      : Probs(std::move(Arg.Probs)), LastF(Arg.LastF),
50        PostDominatedByUnreachable(std::move(Arg.PostDominatedByUnreachable)),
51        PostDominatedByColdCall(std::move(Arg.PostDominatedByColdCall)) {}
52
53  BranchProbabilityInfo &operator=(BranchProbabilityInfo &&RHS) {
54    releaseMemory();
55    Probs = std::move(RHS.Probs);
56    PostDominatedByColdCall = std::move(RHS.PostDominatedByColdCall);
57    PostDominatedByUnreachable = std::move(RHS.PostDominatedByUnreachable);
58    return *this;
59  }
60
61  void releaseMemory();
62
63  void print(raw_ostream &OS) const;
64
65  /// \brief Get an edge's probability, relative to other out-edges of the Src.
66  ///
67  /// This routine provides access to the fractional probability between zero
68  /// (0%) and one (100%) of this edge executing, relative to other edges
69  /// leaving the 'Src' block. The returned probability is never zero, and can
70  /// only be one if the source block has only one successor.
71  BranchProbability getEdgeProbability(const BasicBlock *Src,
72                                       unsigned IndexInSuccessors) const;
73
74  /// \brief Get the probability of going from Src to Dst.
75  ///
76  /// It returns the sum of all probabilities for edges from Src to Dst.
77  BranchProbability getEdgeProbability(const BasicBlock *Src,
78                                       const BasicBlock *Dst) const;
79
80  BranchProbability getEdgeProbability(const BasicBlock *Src,
81                                       succ_const_iterator Dst) const;
82
83  /// \brief Test if an edge is hot relative to other out-edges of the Src.
84  ///
85  /// Check whether this edge out of the source block is 'hot'. We define hot
86  /// as having a relative probability >= 80%.
87  bool isEdgeHot(const BasicBlock *Src, const BasicBlock *Dst) const;
88
89  /// \brief Retrieve the hot successor of a block if one exists.
90  ///
91  /// Given a basic block, look through its successors and if one exists for
92  /// which \see isEdgeHot would return true, return that successor block.
93  const BasicBlock *getHotSucc(const BasicBlock *BB) const;
94
95  /// \brief Print an edge's probability.
96  ///
97  /// Retrieves an edge's probability similarly to \see getEdgeProbability, but
98  /// then prints that probability to the provided stream. That stream is then
99  /// returned.
100  raw_ostream &printEdgeProbability(raw_ostream &OS, const BasicBlock *Src,
101                                    const BasicBlock *Dst) const;
102
103  /// \brief Set the raw edge probability for the given edge.
104  ///
105  /// This allows a pass to explicitly set the edge probability for an edge. It
106  /// can be used when updating the CFG to update and preserve the branch
107  /// probability information. Read the implementation of how these edge
108  /// probabilities are calculated carefully before using!
109  void setEdgeProbability(const BasicBlock *Src, unsigned IndexInSuccessors,
110                          BranchProbability Prob);
111
112  static BranchProbability getBranchProbStackProtector(bool IsLikely) {
113    static const BranchProbability LikelyProb((1u << 20) - 1, 1u << 20);
114    return IsLikely ? LikelyProb : LikelyProb.getCompl();
115  }
116
117  void calculate(const Function &F, const LoopInfo &LI);
118
119private:
120  void operator=(const BranchProbabilityInfo &) = delete;
121  BranchProbabilityInfo(const BranchProbabilityInfo &) = delete;
122
123  // Since we allow duplicate edges from one basic block to another, we use
124  // a pair (PredBlock and an index in the successors) to specify an edge.
125  typedef std::pair<const BasicBlock *, unsigned> Edge;
126
127  // Default weight value. Used when we don't have information about the edge.
128  // TODO: DEFAULT_WEIGHT makes sense during static predication, when none of
129  // the successors have a weight yet. But it doesn't make sense when providing
130  // weight to an edge that may have siblings with non-zero weights. This can
131  // be handled various ways, but it's probably fine for an edge with unknown
132  // weight to just "inherit" the non-zero weight of an adjacent successor.
133  static const uint32_t DEFAULT_WEIGHT = 16;
134
135  DenseMap<Edge, BranchProbability> Probs;
136
137  /// \brief Track the last function we run over for printing.
138  const Function *LastF;
139
140  /// \brief Track the set of blocks directly succeeded by a returning block.
141  SmallPtrSet<const BasicBlock *, 16> PostDominatedByUnreachable;
142
143  /// \brief Track the set of blocks that always lead to a cold call.
144  SmallPtrSet<const BasicBlock *, 16> PostDominatedByColdCall;
145
146  bool calcUnreachableHeuristics(const BasicBlock *BB);
147  bool calcMetadataWeights(const BasicBlock *BB);
148  bool calcColdCallHeuristics(const BasicBlock *BB);
149  bool calcPointerHeuristics(const BasicBlock *BB);
150  bool calcLoopBranchHeuristics(const BasicBlock *BB, const LoopInfo &LI);
151  bool calcZeroHeuristics(const BasicBlock *BB);
152  bool calcFloatingPointHeuristics(const BasicBlock *BB);
153  bool calcInvokeHeuristics(const BasicBlock *BB);
154};
155
156/// \brief Analysis pass which computes \c BranchProbabilityInfo.
157class BranchProbabilityAnalysis
158    : public AnalysisInfoMixin<BranchProbabilityAnalysis> {
159  friend AnalysisInfoMixin<BranchProbabilityAnalysis>;
160  static char PassID;
161
162public:
163  /// \brief Provide the result typedef for this analysis pass.
164  typedef BranchProbabilityInfo Result;
165
166  /// \brief Run the analysis pass over a function and produce BPI.
167  BranchProbabilityInfo run(Function &F, AnalysisManager<Function> &AM);
168};
169
170/// \brief Printer pass for the \c BranchProbabilityAnalysis results.
171class BranchProbabilityPrinterPass
172    : public PassInfoMixin<BranchProbabilityPrinterPass> {
173  raw_ostream &OS;
174
175public:
176  explicit BranchProbabilityPrinterPass(raw_ostream &OS) : OS(OS) {}
177  PreservedAnalyses run(Function &F, AnalysisManager<Function> &AM);
178};
179
180/// \brief Legacy analysis pass which computes \c BranchProbabilityInfo.
181class BranchProbabilityInfoWrapperPass : public FunctionPass {
182  BranchProbabilityInfo BPI;
183
184public:
185  static char ID;
186
187  BranchProbabilityInfoWrapperPass() : FunctionPass(ID) {
188    initializeBranchProbabilityInfoWrapperPassPass(
189        *PassRegistry::getPassRegistry());
190  }
191
192  BranchProbabilityInfo &getBPI() { return BPI; }
193  const BranchProbabilityInfo &getBPI() const { return BPI; }
194
195  void getAnalysisUsage(AnalysisUsage &AU) const override;
196  bool runOnFunction(Function &F) override;
197  void releaseMemory() override;
198  void print(raw_ostream &OS, const Module *M = nullptr) const override;
199};
200
201}
202
203#endif
204