1//===- BranchProbabilityInfo.cpp - Branch Probability Analysis ------------===//
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// Loops should be simplified before this analysis.
10//
11//===----------------------------------------------------------------------===//
12
13#include "llvm/Analysis/BranchProbabilityInfo.h"
14#include "llvm/ADT/PostOrderIterator.h"
15#include "llvm/ADT/STLExtras.h"
16#include "llvm/ADT/SmallVector.h"
17#include "llvm/ADT/SmallVectorExtras.h"
18#include "llvm/Analysis/ConstantFolding.h"
19#include "llvm/Analysis/CycleAnalysis.h"
20#include "llvm/Analysis/PostDominators.h"
21#include "llvm/Analysis/TargetLibraryInfo.h"
22#include "llvm/IR/Attributes.h"
23#include "llvm/IR/BasicBlock.h"
24#include "llvm/IR/CFG.h"
25#include "llvm/IR/Constants.h"
26#include "llvm/IR/Dominators.h"
27#include "llvm/IR/Function.h"
28#include "llvm/IR/InstrTypes.h"
29#include "llvm/IR/Instruction.h"
30#include "llvm/IR/Instructions.h"
31#include "llvm/IR/LLVMContext.h"
32#include "llvm/IR/Metadata.h"
33#include "llvm/IR/PassManager.h"
34#include "llvm/IR/ProfDataUtils.h"
35#include "llvm/IR/Type.h"
36#include "llvm/IR/Value.h"
37#include "llvm/InitializePasses.h"
38#include "llvm/Pass.h"
39#include "llvm/Support/BranchProbability.h"
40#include "llvm/Support/Casting.h"
41#include "llvm/Support/CommandLine.h"
42#include "llvm/Support/Debug.h"
43#include "llvm/Support/raw_ostream.h"
44#include <cassert>
45#include <cstdint>
46#include <utility>
47
48using namespace llvm;
49
50#define DEBUG_TYPE "branch-prob"
51
52static cl::opt<bool> PrintBranchProb(
53 "print-bpi", cl::init(Val: false), cl::Hidden,
54 cl::desc("Print the branch probability info."));
55
56static cl::opt<std::string> PrintBranchProbFuncName(
57 "print-bpi-func-name", cl::Hidden,
58 cl::desc("The option to specify the name of the function "
59 "whose branch probability info is printed."));
60
61INITIALIZE_PASS_BEGIN(BranchProbabilityInfoWrapperPass, "branch-prob",
62 "Branch Probability Analysis", false, true)
63INITIALIZE_PASS_DEPENDENCY(CycleInfoWrapperPass)
64INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
65INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
66INITIALIZE_PASS_DEPENDENCY(PostDominatorTreeWrapperPass)
67INITIALIZE_PASS_END(BranchProbabilityInfoWrapperPass, "branch-prob",
68 "Branch Probability Analysis", false, true)
69
70BranchProbabilityInfoWrapperPass::BranchProbabilityInfoWrapperPass()
71 : FunctionPass(ID) {}
72
73char BranchProbabilityInfoWrapperPass::ID = 0;
74
75// Weights are for internal use only. They are used by heuristics to help to
76// estimate edges' probability. Example:
77//
78// Using "Loop Branch Heuristics" we predict weights of edges for the
79// block BB2.
80// ...
81// |
82// V
83// BB1<-+
84// | |
85// | | (Weight = 124)
86// V |
87// BB2--+
88// |
89// | (Weight = 4)
90// V
91// BB3
92//
93// Probability of the edge BB2->BB1 = 124 / (124 + 4) = 0.96875
94// Probability of the edge BB2->BB3 = 4 / (124 + 4) = 0.03125
95static const uint32_t LBH_TAKEN_WEIGHT = 124;
96static const uint32_t LBH_NONTAKEN_WEIGHT = 4;
97
98/// Unreachable-terminating branch taken probability.
99///
100/// This is the probability for a branch being taken to a block that terminates
101/// (eventually) in unreachable. These are predicted as unlikely as possible.
102/// All reachable probability will proportionally share the remaining part.
103static constexpr BranchProbability UR_TAKEN_PROB = BranchProbability::getRaw(N: 1);
104
105/// Heuristics and lookup tables for non-loop branches:
106/// Pointer Heuristics (PH)
107static const uint32_t PH_TAKEN_WEIGHT = 20;
108static const uint32_t PH_NONTAKEN_WEIGHT = 12;
109static constexpr BranchProbability
110 PtrTakenProb(PH_TAKEN_WEIGHT, PH_TAKEN_WEIGHT + PH_NONTAKEN_WEIGHT);
111static constexpr BranchProbability
112 PtrUntakenProb(PH_NONTAKEN_WEIGHT, PH_TAKEN_WEIGHT + PH_NONTAKEN_WEIGHT);
113
114/// Zero Heuristics (ZH)
115static const uint32_t ZH_TAKEN_WEIGHT = 20;
116static const uint32_t ZH_NONTAKEN_WEIGHT = 12;
117static constexpr BranchProbability
118 ZeroTakenProb(ZH_TAKEN_WEIGHT, ZH_TAKEN_WEIGHT + ZH_NONTAKEN_WEIGHT);
119static constexpr BranchProbability
120 ZeroUntakenProb(ZH_NONTAKEN_WEIGHT, ZH_TAKEN_WEIGHT + ZH_NONTAKEN_WEIGHT);
121
122// Floating-Point Heuristics (FPH)
123static const uint32_t FPH_TAKEN_WEIGHT = 20;
124static const uint32_t FPH_NONTAKEN_WEIGHT = 12;
125
126/// This is the probability for an ordered floating point comparison.
127static const uint32_t FPH_ORD_WEIGHT = 1024 * 1024 - 1;
128/// This is the probability for an unordered floating point comparison, it means
129/// one or two of the operands are NaN. Usually it is used to test for an
130/// exceptional case, so the result is unlikely.
131static const uint32_t FPH_UNO_WEIGHT = 1;
132
133static constexpr BranchProbability
134 FPOrdTakenProb(FPH_ORD_WEIGHT, FPH_ORD_WEIGHT + FPH_UNO_WEIGHT);
135static constexpr BranchProbability
136 FPOrdUntakenProb(FPH_UNO_WEIGHT, FPH_ORD_WEIGHT + FPH_UNO_WEIGHT);
137static constexpr BranchProbability
138 FPTakenProb(FPH_TAKEN_WEIGHT, FPH_TAKEN_WEIGHT + FPH_NONTAKEN_WEIGHT);
139static constexpr BranchProbability
140 FPUntakenProb(FPH_NONTAKEN_WEIGHT, FPH_TAKEN_WEIGHT + FPH_NONTAKEN_WEIGHT);
141
142/// Set of dedicated "absolute" execution weights for a block. These weights are
143/// meaningful relative to each other and their derivatives only.
144enum class BlockExecWeight : std::uint32_t {
145 /// Special weight used for cases with exact zero probability.
146 ZERO = 0x0,
147 /// Minimal possible non zero weight.
148 LOWEST_NON_ZERO = 0x1,
149 /// Weight to an 'unreachable' block.
150 UNREACHABLE = ZERO,
151 /// Weight to a block containing non returning call.
152 NORETURN = LOWEST_NON_ZERO,
153 /// Weight to 'unwind' block of an invoke instruction.
154 UNWIND = LOWEST_NON_ZERO,
155 /// Weight to a 'cold' block. Cold blocks are the ones containing calls marked
156 /// with attribute 'cold'.
157 COLD = 0xffff,
158 /// Default weight is used in cases when there is no dedicated execution
159 /// weight set. It is not propagated through the domination line either.
160 DEFAULT = 0xfffff
161};
162
163namespace {
164class BPIConstruction {
165public:
166 BPIConstruction(BranchProbabilityInfo &BPI) : BPI(BPI) {}
167 void calculate(const Function &F, const CycleInfo &CI,
168 const TargetLibraryInfo *TLI, DominatorTree *DT,
169 PostDominatorTree *PDT);
170
171private:
172 // Pair representing an edge from first to second block.
173 using LoopEdge = std::pair<const BasicBlock *, const BasicBlock *>;
174
175 /// Returns true if destination block belongs to some loop and source block is
176 /// either doesn't belong to any loop or belongs to a loop which is not inner
177 /// relative to the destination block.
178 bool isLoopEnteringEdge(const LoopEdge &Edge) const;
179 /// Returns true if source block belongs to some loop and destination block is
180 /// either doesn't belong to any loop or belongs to a loop which is not inner
181 /// relative to the source block.
182 bool isLoopExitingEdge(const LoopEdge &Edge) const;
183 /// Returns true if \p Edge is either enters to or exits from some loop, false
184 /// in all other cases.
185 bool isLoopEnteringExitingEdge(const LoopEdge &Edge) const;
186 // Fills in \p Enters vector with all "enter" blocks to a loop \LB belongs to.
187 void getLoopEnterBlocks(const BasicBlock *LB,
188 SmallVectorImpl<const BasicBlock *> &Enters) const;
189
190 /// Returns estimated weight for \p BB. std::nullopt if \p BB has no estimated
191 /// weight.
192 std::optional<uint32_t> getEstimatedBlockWeight(const BasicBlock *BB) const;
193
194 /// Returns estimated weight to enter \p L. In other words it is weight of
195 /// loop's header block not scaled by trip count. Returns std::nullopt if \p C
196 /// has no no estimated weight.
197 std::optional<uint32_t> getEstimatedLoopWeight(CycleRef C) const;
198
199 /// Return estimated weight for \p Edge. Returns std::nullopt if estimated
200 /// weight is unknown.
201 std::optional<uint32_t> getEstimatedEdgeWeight(const LoopEdge &Edge) const;
202
203 /// Iterates over all edges leading from \p SrcBB to \p Successors and
204 /// returns maximum of all estimated weights. If at least one edge has unknown
205 /// estimated weight std::nullopt is returned.
206 template <class IterT>
207 std::optional<uint32_t>
208 getMaxEstimatedEdgeWeight(const BasicBlock *SrcBB,
209 iterator_range<IterT> Successors) const;
210
211 /// If \p LoopBB has no estimated weight then set it to \p BBWeight and
212 /// return true. Otherwise \p BB's weight remains unchanged and false is
213 /// returned. In addition all blocks/loops that might need their weight to be
214 /// re-estimated are put into BlockWorkList/LoopWorkList.
215 bool
216 updateEstimatedBlockWeight(const BasicBlock *BB, uint32_t BBWeight,
217 SmallVectorImpl<const BasicBlock *> &BlockWorkList,
218 SmallVectorImpl<const BasicBlock *> &LoopWorkList);
219
220 /// Starting from \p LoopBB (including \p LoopBB itself) propagate \p BBWeight
221 /// up the domination tree.
222 void propagateEstimatedBlockWeight(
223 const BasicBlock *BB, DominatorTree *DT, PostDominatorTree *PDT,
224 uint32_t BBWeight, SmallVectorImpl<const BasicBlock *> &WorkList,
225 SmallVectorImpl<const BasicBlock *> &LoopWorkList);
226
227 /// Returns block's weight encoded in the IR.
228 std::optional<uint32_t> getInitialEstimatedBlockWeight(const BasicBlock *BB);
229
230 // Computes estimated weights for all blocks in \p F.
231 void estimateBlockWeights(const Function &F, DominatorTree *DT,
232 PostDominatorTree *PDT);
233
234 /// Based on computed weights by \p computeEstimatedBlockWeight set
235 /// probabilities on branches.
236 bool calcEstimatedHeuristics(const BasicBlock *BB);
237 bool calcMetadataWeights(const BasicBlock *BB);
238 bool calcPointerHeuristics(const BasicBlock *BB);
239 bool calcZeroHeuristics(const BasicBlock *BB, const TargetLibraryInfo *TLI);
240 bool calcFloatingPointHeuristics(const BasicBlock *BB);
241
242 BranchProbabilityInfo &BPI;
243
244 const CycleInfo *CI = nullptr;
245
246 /// Keeps mapping of a basic block to its estimated weight.
247 SmallDenseMap<const BasicBlock *, uint32_t> EstimatedBlockWeight;
248
249 /// Keeps mapping of a loop to estimated weight to enter the loop.
250 SmallDenseMap<CycleRef, uint32_t> EstimatedLoopWeight;
251};
252
253bool BPIConstruction::isLoopEnteringEdge(const LoopEdge &Edge) const {
254 CycleRef SrcCycle = CI->getCycle(Block: Edge.first);
255 CycleRef DstCycle = CI->getCycle(Block: Edge.second);
256 if (!DstCycle) // Edge into no-cycle is not entering.
257 return false;
258 if (!SrcCycle) // Edge from no-cycle into cycle is entering.
259 return true;
260 return !CI->contains(Outer: DstCycle, Inner: SrcCycle);
261}
262
263bool BPIConstruction::isLoopExitingEdge(const LoopEdge &Edge) const {
264 return isLoopEnteringEdge(Edge: {Edge.second, Edge.first});
265}
266
267bool BPIConstruction::isLoopEnteringExitingEdge(const LoopEdge &Edge) const {
268 return isLoopEnteringEdge(Edge) || isLoopExitingEdge(Edge);
269}
270
271void BPIConstruction::getLoopEnterBlocks(
272 const BasicBlock *BB, SmallVectorImpl<const BasicBlock *> &Enters) const {
273 CycleRef C = CI->getCycle(Block: BB);
274 for (BasicBlock *Entry : CI->getEntries(C))
275 for (const auto *Pred : predecessors(BB: Entry))
276 if (!CI->contains(C, Block: Pred))
277 Enters.push_back(Elt: Pred);
278}
279
280// Propagate existing explicit probabilities from either profile data or
281// 'expect' intrinsic processing. Examine metadata against unreachable
282// heuristic. The probability of the edge coming to unreachable block is
283// set to min of metadata and unreachable heuristic.
284bool BPIConstruction::calcMetadataWeights(const BasicBlock *BB) {
285 const Instruction *TI = BB->getTerminator();
286 assert(TI->getNumSuccessors() > 1 && "expected more than one successor!");
287 if (!(isa<CondBrInst>(Val: TI) || isa<SwitchInst>(Val: TI) || isa<IndirectBrInst>(Val: TI) ||
288 isa<InvokeInst>(Val: TI) || isa<CallBrInst>(Val: TI)))
289 return false;
290
291 MDNode *WeightsNode = getValidBranchWeightMDNode(I: *TI);
292 if (!WeightsNode)
293 return false;
294
295 // Check that the number of successors is manageable.
296 assert(TI->getNumSuccessors() < UINT32_MAX && "Too many successors");
297
298 SmallVector<uint32_t, 2> Weights;
299 SmallVector<unsigned, 2> UnreachableIdxs;
300 SmallVector<unsigned, 2> ReachableIdxs;
301
302 extractBranchWeights(ProfileData: WeightsNode, Weights);
303 auto Succs = succ_begin(I: TI);
304 for (unsigned I = 0, E = Weights.size(); I != E; ++I) {
305 auto EstimatedWeight = getEstimatedEdgeWeight(Edge: {BB, *Succs++});
306 if (EstimatedWeight &&
307 *EstimatedWeight <= static_cast<uint32_t>(BlockExecWeight::UNREACHABLE))
308 UnreachableIdxs.push_back(Elt: I);
309 else
310 ReachableIdxs.push_back(Elt: I);
311 }
312 assert(Weights.size() == TI->getNumSuccessors() && "Checked above");
313
314 // If all successors are unreachable, all edges are equally likely.
315 if (ReachableIdxs.empty())
316 fill(Range&: Weights, Value: 1);
317
318 // Set the probability.
319 SmallVector<BranchProbability> BP =
320 BranchProbabilityInfo::getEdgeProbabilitiesFromWeights(Weights);
321
322 // Examine the metadata against unreachable heuristic.
323 // If the unreachable heuristic is more strong then we use it for this edge.
324 if (UnreachableIdxs.size() == 0 || ReachableIdxs.size() == 0) {
325 BPI.setEdgeProbability(Src: BB, Probs: BP);
326 return true;
327 }
328
329 auto UnreachableProb = UR_TAKEN_PROB;
330 for (auto I : UnreachableIdxs)
331 if (UnreachableProb < BP[I]) {
332 BP[I] = UnreachableProb;
333 }
334
335 // Sum of all edge probabilities must be 1.0. If we modified the probability
336 // of some edges then we must distribute the introduced difference over the
337 // reachable blocks.
338 //
339 // Proportional distribution: the relation between probabilities of the
340 // reachable edges is kept unchanged. That is for any reachable edges i and j:
341 // newBP[i] / newBP[j] == oldBP[i] / oldBP[j] =>
342 // newBP[i] / oldBP[i] == newBP[j] / oldBP[j] == K
343 // Where K is independent of i,j.
344 // newBP[i] == oldBP[i] * K
345 // We need to find K.
346 // Make sum of all reachables of the left and right parts:
347 // sum_of_reachable(newBP) == K * sum_of_reachable(oldBP)
348 // Sum of newBP must be equal to 1.0:
349 // sum_of_reachable(newBP) + sum_of_unreachable(newBP) == 1.0 =>
350 // sum_of_reachable(newBP) = 1.0 - sum_of_unreachable(newBP)
351 // Where sum_of_unreachable(newBP) is what has been just changed.
352 // Finally:
353 // K == sum_of_reachable(newBP) / sum_of_reachable(oldBP) =>
354 // K == (1.0 - sum_of_unreachable(newBP)) / sum_of_reachable(oldBP)
355 BranchProbability NewUnreachableSum = BranchProbability::getZero();
356 for (auto I : UnreachableIdxs)
357 NewUnreachableSum += BP[I];
358
359 BranchProbability NewReachableSum =
360 BranchProbability::getOne() - NewUnreachableSum;
361
362 BranchProbability OldReachableSum = BranchProbability::getZero();
363 for (auto I : ReachableIdxs)
364 OldReachableSum += BP[I];
365
366 if (OldReachableSum != NewReachableSum) { // Anything to dsitribute?
367 if (OldReachableSum.isZero()) {
368 // If all oldBP[i] are zeroes then the proportional distribution results
369 // in all zero probabilities and the error stays big. In this case we
370 // evenly spread NewReachableSum over the reachable edges.
371 BranchProbability PerEdge = NewReachableSum / ReachableIdxs.size();
372 for (auto I : ReachableIdxs)
373 BP[I] = PerEdge;
374 } else {
375 for (auto I : ReachableIdxs) {
376 // We use uint64_t to avoid double rounding error of the following
377 // calculation: BP[i] = BP[i] * NewReachableSum / OldReachableSum
378 // The formula is taken from the private constructor
379 // BranchProbability(uint32_t Numerator, uint32_t Denominator)
380 uint64_t Mul = static_cast<uint64_t>(NewReachableSum.getNumerator()) *
381 BP[I].getNumerator();
382 uint32_t Div = static_cast<uint32_t>(
383 divideNearest(Numerator: Mul, Denominator: OldReachableSum.getNumerator()));
384 BP[I] = BranchProbability::getRaw(N: Div);
385 }
386 }
387 }
388
389 BPI.setEdgeProbability(Src: BB, Probs: BP);
390
391 return true;
392}
393
394// Calculate Edge Weights using "Pointer Heuristics". Predict a comparison
395// between two pointer or pointer and NULL will fail.
396bool BPIConstruction::calcPointerHeuristics(const BasicBlock *BB) {
397 const CondBrInst *BI = dyn_cast<CondBrInst>(Val: BB->getTerminator());
398 if (!BI)
399 return false;
400
401 Value *Cond = BI->getCondition();
402 ICmpInst *CI = dyn_cast<ICmpInst>(Val: Cond);
403 if (!CI || !CI->isEquality())
404 return false;
405
406 Value *LHS = CI->getOperand(i_nocapture: 0);
407
408 if (!LHS->getType()->isPointerTy())
409 return false;
410
411 assert(CI->getOperand(1)->getType()->isPointerTy());
412
413 switch (CI->getPredicate()) {
414 case ICmpInst::ICMP_NE: // p != q -> Likely
415 BPI.setEdgeProbability(Src: BB, Probs: {PtrTakenProb, PtrUntakenProb});
416 return true;
417 case ICmpInst::ICMP_EQ: // p == q -> Unlikely
418 BPI.setEdgeProbability(Src: BB, Probs: {PtrUntakenProb, PtrTakenProb});
419 return true;
420 default:
421 return false;
422 }
423}
424
425// Compute the unlikely successors to the block BB in the cycle C, specifically
426// those that are unlikely because this is a loop, and add them to the
427// UnlikelyBlocks set.
428static void
429computeUnlikelySuccessors(const BasicBlock *BB, const CycleInfo &CI, CycleRef C,
430 SmallPtrSetImpl<const BasicBlock *> &UnlikelyBlocks) {
431 // Sometimes in a loop we have a branch whose condition is made false by
432 // taking it. This is typically something like
433 // int n = 0;
434 // while (...) {
435 // if (++n >= MAX) {
436 // n = 0;
437 // }
438 // }
439 // In this sort of situation taking the branch means that at the very least it
440 // won't be taken again in the next iteration of the loop, so we should
441 // consider it less likely than a typical branch.
442 //
443 // We detect this by looking back through the graph of PHI nodes that sets the
444 // value that the condition depends on, and seeing if we can reach a successor
445 // block which can be determined to make the condition false.
446 //
447 // FIXME: We currently consider unlikely blocks to be half as likely as other
448 // blocks, but if we consider the example above the likelyhood is actually
449 // 1/MAX. We could therefore be more precise in how unlikely we consider
450 // blocks to be, but it would require more careful examination of the form
451 // of the comparison expression.
452 const CondBrInst *BI = dyn_cast<CondBrInst>(Val: BB->getTerminator());
453 if (!BI)
454 return;
455
456 // Check if the branch is based on an instruction compared with a constant
457 CmpInst *Cmp = dyn_cast<CmpInst>(Val: BI->getCondition());
458 if (!Cmp || !isa<Instruction>(Val: Cmp->getOperand(i_nocapture: 0)) ||
459 !isa<Constant>(Val: Cmp->getOperand(i_nocapture: 1)))
460 return;
461
462 // Either the instruction must be a PHI, or a chain of operations involving
463 // constants that ends in a PHI which we can then collapse into a single value
464 // if the PHI value is known.
465 Instruction *CmpLHS = dyn_cast<Instruction>(Val: Cmp->getOperand(i_nocapture: 0));
466 PHINode *CmpPHI = dyn_cast<PHINode>(Val: CmpLHS);
467 Constant *CmpConst = dyn_cast<Constant>(Val: Cmp->getOperand(i_nocapture: 1));
468 // Collect the instructions until we hit a PHI
469 SmallVector<BinaryOperator *, 1> InstChain;
470 while (!CmpPHI && CmpLHS && isa<BinaryOperator>(Val: CmpLHS) &&
471 isa<Constant>(Val: CmpLHS->getOperand(i: 1))) {
472 // Stop if the chain extends outside of the loop
473 if (!CI.contains(C, Block: CmpLHS->getParent()))
474 return;
475 InstChain.push_back(Elt: cast<BinaryOperator>(Val: CmpLHS));
476 CmpLHS = dyn_cast<Instruction>(Val: CmpLHS->getOperand(i: 0));
477 if (CmpLHS)
478 CmpPHI = dyn_cast<PHINode>(Val: CmpLHS);
479 }
480 if (!CmpPHI || !CI.contains(C, Block: CmpPHI->getParent()))
481 return;
482
483 // Trace the phi node to find all values that come from successors of BB
484 SmallPtrSet<PHINode*, 8> VisitedInsts;
485 SmallVector<PHINode*, 8> WorkList;
486 WorkList.push_back(Elt: CmpPHI);
487 VisitedInsts.insert(Ptr: CmpPHI);
488 while (!WorkList.empty()) {
489 PHINode *P = WorkList.pop_back_val();
490 for (BasicBlock *B : P->blocks()) {
491 // Skip blocks that aren't part of the loop
492 if (!CI.contains(C, Block: B))
493 continue;
494 Value *V = P->getIncomingValueForBlock(BB: B);
495 // If the source is a PHI add it to the work list if we haven't
496 // already visited it.
497 if (PHINode *PN = dyn_cast<PHINode>(Val: V)) {
498 if (VisitedInsts.insert(Ptr: PN).second)
499 WorkList.push_back(Elt: PN);
500 continue;
501 }
502 // If this incoming value is a constant and B is a successor of BB, then
503 // we can constant-evaluate the compare to see if it makes the branch be
504 // taken or not.
505 Constant *CmpLHSConst = dyn_cast<Constant>(Val: V);
506 if (!CmpLHSConst || !llvm::is_contained(Range: successors(BB), Element: B))
507 continue;
508 // First collapse InstChain
509 const DataLayout &DL = BB->getDataLayout();
510 for (Instruction *I : llvm::reverse(C&: InstChain)) {
511 CmpLHSConst = ConstantFoldBinaryOpOperands(
512 Opcode: I->getOpcode(), LHS: CmpLHSConst, RHS: cast<Constant>(Val: I->getOperand(i: 1)), DL);
513 if (!CmpLHSConst)
514 break;
515 }
516 if (!CmpLHSConst)
517 continue;
518 // Now constant-evaluate the compare
519 Constant *Result = ConstantFoldCompareInstOperands(
520 Predicate: Cmp->getPredicate(), LHS: CmpLHSConst, RHS: CmpConst, DL);
521 // If the result means we don't branch to the block then that block is
522 // unlikely.
523 if (Result && ((Result->isNullValue() && B == BI->getSuccessor(i: 0)) ||
524 (Result->isOneValue() && B == BI->getSuccessor(i: 1))))
525 UnlikelyBlocks.insert(Ptr: B);
526 }
527 }
528}
529
530std::optional<uint32_t>
531BPIConstruction::getEstimatedBlockWeight(const BasicBlock *BB) const {
532 auto WeightIt = EstimatedBlockWeight.find(Val: BB);
533 if (WeightIt == EstimatedBlockWeight.end())
534 return std::nullopt;
535 return WeightIt->second;
536}
537
538std::optional<uint32_t>
539BPIConstruction::getEstimatedLoopWeight(CycleRef C) const {
540 auto WeightIt = EstimatedLoopWeight.find(Val: C);
541 if (WeightIt == EstimatedLoopWeight.end())
542 return std::nullopt;
543 return WeightIt->second;
544}
545
546std::optional<uint32_t>
547BPIConstruction::getEstimatedEdgeWeight(const LoopEdge &Edge) const {
548 // For edges entering a loop take weight of a loop rather than an individual
549 // block in the loop.
550 return isLoopEnteringEdge(Edge)
551 ? getEstimatedLoopWeight(C: CI->getCycle(Block: Edge.second))
552 : getEstimatedBlockWeight(BB: Edge.second);
553}
554
555template <class IterT>
556std::optional<uint32_t> BPIConstruction::getMaxEstimatedEdgeWeight(
557 const BasicBlock *SrcBB, iterator_range<IterT> Successors) const {
558 std::optional<uint32_t> MaxWeight;
559 for (const BasicBlock *DstBB : Successors) {
560 auto Weight = getEstimatedEdgeWeight(Edge: {SrcBB, DstBB});
561 if (!Weight)
562 return std::nullopt;
563 if (!MaxWeight || *MaxWeight < *Weight)
564 MaxWeight = Weight;
565 }
566
567 return MaxWeight;
568}
569
570// Updates \p LoopBB's weight and returns true. If \p LoopBB has already
571// an associated weight it is unchanged and false is returned.
572//
573// Please note by the algorithm the weight is not expected to change once set
574// thus 'false' status is used to track visited blocks.
575bool BPIConstruction::updateEstimatedBlockWeight(
576 const BasicBlock *BB, uint32_t BBWeight,
577 SmallVectorImpl<const BasicBlock *> &BlockWorkList,
578 SmallVectorImpl<const BasicBlock *> &LoopWorkList) {
579 // In general, weight is assigned to a block when it has final value and
580 // can't/shouldn't be changed. However, there are cases when a block
581 // inherently has several (possibly "contradicting") weights. For example,
582 // "unwind" block may also contain "cold" call. In that case the first
583 // set weight is favored and all consequent weights are ignored.
584 if (!EstimatedBlockWeight.insert(KV: {BB, BBWeight}).second)
585 return false;
586
587 for (const BasicBlock *PredBlock : predecessors(BB)) {
588 // Add affected block/loop to a working list.
589 if (isLoopExitingEdge(Edge: {PredBlock, BB})) {
590 if (!EstimatedLoopWeight.count(Val: CI->getCycle(Block: PredBlock)))
591 LoopWorkList.push_back(Elt: PredBlock);
592 } else if (!EstimatedBlockWeight.count(Val: PredBlock))
593 BlockWorkList.push_back(Elt: PredBlock);
594 }
595 return true;
596}
597
598// Starting from \p BB traverse through dominator blocks and assign \p BBWeight
599// to all such blocks that are post dominated by \BB. In other words to all
600// blocks that the one is executed if and only if another one is executed.
601// Importantly, we skip loops here for two reasons. First weights of blocks in
602// a loop should be scaled by trip count (yet possibly unknown). Second there is
603// no any value in doing that because that doesn't give any additional
604// information regarding distribution of probabilities inside the loop.
605// Exception is loop 'enter' and 'exit' edges that are handled in a special way
606// at calcEstimatedHeuristics.
607//
608// In addition, \p WorkList is populated with basic blocks if at leas one
609// successor has updated estimated weight.
610void BPIConstruction::propagateEstimatedBlockWeight(
611 const BasicBlock *BB, DominatorTree *DT, PostDominatorTree *PDT,
612 uint32_t BBWeight, SmallVectorImpl<const BasicBlock *> &BlockWorkList,
613 SmallVectorImpl<const BasicBlock *> &LoopWorkList) {
614 const auto *DTStartNode = DT->getNode(BB);
615 const auto *PDTStartNode = PDT->getNode(BB);
616
617 // TODO: Consider propagating weight down the domination line as well.
618 for (const auto *DTNode = DTStartNode; DTNode != nullptr;
619 DTNode = DTNode->getIDom()) {
620 auto *DomBB = DTNode->getBlock();
621 // Consider blocks which lie on one 'line'.
622 if (!PDT->dominates(A: PDTStartNode, B: PDT->getNode(BB: DomBB)))
623 // If BB doesn't post dominate DomBB it will not post dominate dominators
624 // of DomBB as well.
625 break;
626
627 const LoopEdge Edge{DomBB, BB};
628 // Don't propagate weight to blocks belonging to different loops.
629 if (!isLoopEnteringExitingEdge(Edge)) {
630 if (!updateEstimatedBlockWeight(BB: DomBB, BBWeight, BlockWorkList,
631 LoopWorkList))
632 // If DomBB has weight set then all it's predecessors are already
633 // processed (since we propagate weight up to the top of IR each time).
634 break;
635 } else if (isLoopExitingEdge(Edge)) {
636 LoopWorkList.push_back(Elt: DomBB);
637 }
638 }
639}
640
641std::optional<uint32_t>
642BPIConstruction::getInitialEstimatedBlockWeight(const BasicBlock *BB) {
643 // Returns true if \p BB has call marked with "NoReturn" attribute.
644 auto hasNoReturn = [&](const BasicBlock *BB) {
645 for (const auto &I : reverse(C: *BB))
646 if (const CallInst *CI = dyn_cast<CallInst>(Val: &I))
647 if (CI->hasFnAttr(Kind: Attribute::NoReturn))
648 return true;
649
650 return false;
651 };
652
653 // Important note regarding the order of checks. They are ordered by weight
654 // from lowest to highest. Doing that allows to avoid "unstable" results
655 // when several conditions heuristics can be applied simultaneously.
656 if (isa<UnreachableInst>(Val: BB->getTerminator()) ||
657 // If this block is terminated by a call to
658 // @llvm.experimental.deoptimize then treat it like an unreachable
659 // since it is expected to practically never execute.
660 // TODO: Should we actually treat as never returning call?
661 BB->getTerminatingDeoptimizeCall())
662 return hasNoReturn(BB)
663 ? static_cast<uint32_t>(BlockExecWeight::NORETURN)
664 : static_cast<uint32_t>(BlockExecWeight::UNREACHABLE);
665
666 // Check if the block is an exception handling block.
667 if (BB->isEHPad())
668 return static_cast<uint32_t>(BlockExecWeight::UNWIND);
669
670 // Check if the block contains 'cold' call.
671 for (const auto &I : *BB)
672 if (const CallInst *CI = dyn_cast<CallInst>(Val: &I))
673 if (CI->hasFnAttr(Kind: Attribute::Cold))
674 return static_cast<uint32_t>(BlockExecWeight::COLD);
675
676 return std::nullopt;
677}
678
679// Does RPO traversal over all blocks in \p F and assigns weights to
680// 'unreachable', 'noreturn', 'cold', 'unwind' blocks. In addition it does its
681// best to propagate the weight to up/down the IR.
682void BPIConstruction::estimateBlockWeights(const Function &F, DominatorTree *DT,
683 PostDominatorTree *PDT) {
684 SmallVector<const BasicBlock *, 8> BlockWorkList;
685 SmallVector<const BasicBlock *, 8> LoopWorkList;
686 SmallDenseMap<CycleRef, SmallVector<BasicBlock *, 4>> LoopExitBlocks;
687
688 // By doing RPO we make sure that all predecessors already have weights
689 // calculated before visiting theirs successors.
690 ReversePostOrderTraversal<const Function *> RPOT(&F);
691 for (const auto *BB : RPOT)
692 if (auto BBWeight = getInitialEstimatedBlockWeight(BB))
693 // If we were able to find estimated weight for the block set it to this
694 // block and propagate up the IR.
695 propagateEstimatedBlockWeight(BB, DT, PDT, BBWeight: *BBWeight, BlockWorkList,
696 LoopWorkList);
697
698 // BlockWorklist/LoopWorkList contains blocks/loops with at least one
699 // successor/exit having estimated weight. Try to propagate weight to such
700 // blocks/loops from successors/exits.
701 // Process loops and blocks. Order is not important.
702 do {
703 while (!LoopWorkList.empty()) {
704 const BasicBlock *LoopBB = LoopWorkList.pop_back_val();
705 CycleRef C = CI->getCycle(Block: LoopBB);
706 if (EstimatedLoopWeight.count(Val: C))
707 continue;
708
709 auto Res = LoopExitBlocks.try_emplace(Key: C);
710 SmallVectorImpl<BasicBlock *> &Exits = Res.first->second;
711 if (Res.second)
712 CI->getExitBlocks(C, TmpStorage&: Exits);
713 auto LoopWeight = getMaxEstimatedEdgeWeight(
714 SrcBB: LoopBB, Successors: make_range(x: Exits.begin(), y: Exits.end()));
715
716 if (LoopWeight) {
717 // If we never exit the loop then we can enter it once at maximum.
718 if (LoopWeight <= static_cast<uint32_t>(BlockExecWeight::UNREACHABLE))
719 LoopWeight = static_cast<uint32_t>(BlockExecWeight::LOWEST_NON_ZERO);
720
721 EstimatedLoopWeight.insert(KV: {C, *LoopWeight});
722 // Add all blocks entering the loop into working list.
723 getLoopEnterBlocks(BB: LoopBB, Enters&: BlockWorkList);
724 }
725 }
726
727 while (!BlockWorkList.empty()) {
728 // We can reach here only if BlockWorkList is not empty.
729 const BasicBlock *BB = BlockWorkList.pop_back_val();
730 if (EstimatedBlockWeight.count(Val: BB))
731 continue;
732
733 // We take maximum over all weights of successors. In other words we take
734 // weight of "hot" path. In theory we can probably find a better function
735 // which gives higher accuracy results (comparing to "maximum") but I
736 // can't
737 // think of any right now. And I doubt it will make any difference in
738 // practice.
739 auto MaxWeight = getMaxEstimatedEdgeWeight(SrcBB: BB, Successors: successors(BB));
740
741 if (MaxWeight)
742 propagateEstimatedBlockWeight(BB, DT, PDT, BBWeight: *MaxWeight, BlockWorkList,
743 LoopWorkList);
744 }
745 } while (!BlockWorkList.empty() || !LoopWorkList.empty());
746}
747
748// Calculate edge probabilities based on block's estimated weight.
749// Note that gathered weights were not scaled for loops. Thus edges entering
750// and exiting loops requires special processing.
751bool BPIConstruction::calcEstimatedHeuristics(const BasicBlock *BB) {
752 assert(BB->getTerminator()->getNumSuccessors() > 1 &&
753 "expected more than one successor!");
754
755 CycleRef BBCycle = CI->getCycle(Block: BB);
756
757 SmallPtrSet<const BasicBlock *, 8> UnlikelyBlocks;
758 uint32_t TC = LBH_TAKEN_WEIGHT / LBH_NONTAKEN_WEIGHT;
759 if (BBCycle)
760 computeUnlikelySuccessors(BB, CI: *CI, C: BBCycle, UnlikelyBlocks);
761
762 // Changed to 'true' if at least one successor has estimated weight.
763 bool FoundEstimatedWeight = false;
764 SmallVector<uint32_t, 4> SuccWeights;
765 uint64_t TotalWeight = 0;
766 // Go over all successors of BB and put their weights into SuccWeights.
767 for (const BasicBlock *SuccBB : successors(BB)) {
768 std::optional<uint32_t> Weight;
769 const LoopEdge Edge{BB, SuccBB};
770
771 Weight = getEstimatedEdgeWeight(Edge);
772
773 if (isLoopExitingEdge(Edge) &&
774 // Avoid adjustment of ZERO weight since it should remain unchanged.
775 Weight != static_cast<uint32_t>(BlockExecWeight::ZERO)) {
776 // Scale down loop exiting weight by trip count.
777 Weight = std::max(
778 a: static_cast<uint32_t>(BlockExecWeight::LOWEST_NON_ZERO),
779 b: Weight.value_or(u: static_cast<uint32_t>(BlockExecWeight::DEFAULT)) /
780 TC);
781 }
782 bool IsUnlikelyEdge = BBCycle && UnlikelyBlocks.contains(Ptr: SuccBB);
783 if (IsUnlikelyEdge &&
784 // Avoid adjustment of ZERO weight since it should remain unchanged.
785 Weight != static_cast<uint32_t>(BlockExecWeight::ZERO)) {
786 // 'Unlikely' blocks have twice lower weight.
787 Weight = std::max(
788 a: static_cast<uint32_t>(BlockExecWeight::LOWEST_NON_ZERO),
789 b: Weight.value_or(u: static_cast<uint32_t>(BlockExecWeight::DEFAULT)) / 2);
790 }
791
792 if (Weight)
793 FoundEstimatedWeight = true;
794
795 auto WeightVal =
796 Weight.value_or(u: static_cast<uint32_t>(BlockExecWeight::DEFAULT));
797 TotalWeight += WeightVal;
798 SuccWeights.push_back(Elt: WeightVal);
799 }
800
801 // If non of blocks have estimated weight bail out.
802 // If TotalWeight is 0 that means weight of each successor is 0 as well and
803 // equally likely. Bail out early to not deal with devision by zero.
804 if (!FoundEstimatedWeight || TotalWeight == 0)
805 return false;
806
807 assert(SuccWeights.size() == succ_size(BB) && "Missed successor?");
808 const unsigned SuccCount = SuccWeights.size();
809
810 // If the sum of weights does not fit in 32 bits, scale every weight down
811 // accordingly.
812 if (TotalWeight > UINT32_MAX) {
813 uint64_t ScalingFactor = TotalWeight / UINT32_MAX + 1;
814 TotalWeight = 0;
815 for (unsigned Idx = 0; Idx < SuccCount; ++Idx) {
816 SuccWeights[Idx] /= ScalingFactor;
817 if (SuccWeights[Idx] == static_cast<uint32_t>(BlockExecWeight::ZERO))
818 SuccWeights[Idx] =
819 static_cast<uint32_t>(BlockExecWeight::LOWEST_NON_ZERO);
820 TotalWeight += SuccWeights[Idx];
821 }
822 assert(TotalWeight <= UINT32_MAX && "Total weight overflows");
823 }
824
825 // Finally set probabilities to edges according to estimated block weights.
826 SmallVector<BranchProbability, 4> EdgeProbabilities(
827 SuccCount, BranchProbability::getUnknown());
828
829 for (unsigned Idx = 0; Idx < SuccCount; ++Idx) {
830 EdgeProbabilities[Idx] =
831 BranchProbability(SuccWeights[Idx], (uint32_t)TotalWeight);
832 }
833 BPI.setEdgeProbability(Src: BB, Probs: EdgeProbabilities);
834 return true;
835}
836
837bool BPIConstruction::calcZeroHeuristics(const BasicBlock *BB,
838 const TargetLibraryInfo *TLI) {
839 const CondBrInst *BI = dyn_cast<CondBrInst>(Val: BB->getTerminator());
840 if (!BI)
841 return false;
842
843 Value *Cond = BI->getCondition();
844 ICmpInst *CI = dyn_cast<ICmpInst>(Val: Cond);
845 if (!CI)
846 return false;
847
848 auto GetConstantInt = [](Value *V) {
849 if (auto *I = dyn_cast<BitCastInst>(Val: V))
850 return dyn_cast<ConstantInt>(Val: I->getOperand(i_nocapture: 0));
851 return dyn_cast<ConstantInt>(Val: V);
852 };
853
854 Value *RHS = CI->getOperand(i_nocapture: 1);
855 ConstantInt *CV = GetConstantInt(RHS);
856 if (!CV)
857 return false;
858
859 // If the LHS is the result of AND'ing a value with a single bit bitmask,
860 // we don't have information about probabilities.
861 if (Instruction *LHS = dyn_cast<Instruction>(Val: CI->getOperand(i_nocapture: 0)))
862 if (LHS->getOpcode() == Instruction::And)
863 if (ConstantInt *AndRHS = GetConstantInt(LHS->getOperand(i: 1)))
864 if (AndRHS->getValue().isPowerOf2())
865 return false;
866
867 // Check if the LHS is the return value of a library function
868 LibFunc Func = LibFunc::NotLibFunc;
869 if (TLI)
870 if (CallInst *Call = dyn_cast<CallInst>(Val: CI->getOperand(i_nocapture: 0)))
871 if (Function *CalledFn = Call->getCalledFunction())
872 Func = TLI->getLibFunc(FDecl: *CalledFn);
873
874 bool Likely;
875 if (Func == LibFunc_strcasecmp ||
876 Func == LibFunc_strcmp ||
877 Func == LibFunc_strncasecmp ||
878 Func == LibFunc_strncmp ||
879 Func == LibFunc_memcmp ||
880 Func == LibFunc_bcmp) {
881 /// strcmp and similar functions return zero, negative, or positive, if the
882 /// first string is equal, less, or greater than the second. We consider it
883 /// likely that the strings are not equal, so a comparison with zero is
884 /// probably false, but also a comparison with any other number is also
885 /// probably false given that what exactly is returned for nonzero values is
886 /// not specified. Any kind of comparison other than equality we know
887 /// nothing about.
888 // clang-format off
889 switch (CI->getPredicate()) {
890 case CmpInst::ICMP_EQ: Likely = false; break;
891 case CmpInst::ICMP_NE: Likely = true; break;
892 default: return false;
893 }
894 // clang-format on
895 } else if (CV->isZero()) {
896 // clang-format off
897 switch (CI->getPredicate()) {
898 case CmpInst::ICMP_EQ: Likely = false; break;
899 case CmpInst::ICMP_NE: Likely = true; break;
900 case CmpInst::ICMP_SLT: Likely = false; break;
901 case CmpInst::ICMP_SGT: Likely = true; break;
902 default: return false;
903 }
904 // clang-format on
905 } else if (CV->isOne()) {
906 // clang-format off
907 switch (CI->getPredicate()) {
908 case CmpInst::ICMP_SLT: Likely = false; break;
909 default: return false;
910 }
911 // clang-format on
912 } else if (CV->isMinusOne()) {
913 // clang-format off
914 switch (CI->getPredicate()) {
915 case CmpInst::ICMP_EQ: Likely = false; break;
916 case CmpInst::ICMP_NE: Likely = true; break;
917 // InstCombine canonicalizes X >= 0 into X > -1
918 case CmpInst::ICMP_SGT: Likely = true; break;
919 default: return false;
920 }
921 // clang-format on
922 } else {
923 return false;
924 }
925
926 if (Likely)
927 BPI.setEdgeProbability(Src: BB, Probs: {ZeroTakenProb, ZeroUntakenProb});
928 else
929 BPI.setEdgeProbability(Src: BB, Probs: {ZeroUntakenProb, ZeroTakenProb});
930 return true;
931}
932
933bool BPIConstruction::calcFloatingPointHeuristics(const BasicBlock *BB) {
934 const CondBrInst *BI = dyn_cast<CondBrInst>(Val: BB->getTerminator());
935 if (!BI)
936 return false;
937
938 Value *Cond = BI->getCondition();
939 FCmpInst *FCmp = dyn_cast<FCmpInst>(Val: Cond);
940 if (!FCmp)
941 return false;
942
943 if (FCmp->isEquality()) {
944 if (!FCmp->isTrueWhenEqual()) // f1 == f2 -> Unlikely
945 BPI.setEdgeProbability(Src: BB, Probs: {FPTakenProb, FPUntakenProb});
946 else // f1 != f2 -> Likely
947 BPI.setEdgeProbability(Src: BB, Probs: {FPUntakenProb, FPTakenProb});
948 } else if (FCmp->getPredicate() == FCmpInst::FCMP_ORD) {
949 BPI.setEdgeProbability(
950 Src: BB, Probs: {FPOrdTakenProb, FPOrdUntakenProb}); // !isnan -> Likely
951 } else if (FCmp->getPredicate() == FCmpInst::FCMP_UNO) {
952 BPI.setEdgeProbability(
953 Src: BB, Probs: {FPOrdUntakenProb, FPOrdTakenProb}); // isnan -> Unlikely
954 } else {
955 return false;
956 }
957 return true;
958}
959void BPIConstruction::calculate(const Function &F, const CycleInfo &CycleI,
960 const TargetLibraryInfo *TLI, DominatorTree *DT,
961 PostDominatorTree *PDT) {
962 CI = &CycleI;
963
964 std::unique_ptr<DominatorTree> DTPtr;
965 std::unique_ptr<PostDominatorTree> PDTPtr;
966
967 if (!DT) {
968 DTPtr = std::make_unique<DominatorTree>(args&: const_cast<Function &>(F));
969 DT = DTPtr.get();
970 }
971
972 if (!PDT) {
973 PDTPtr = std::make_unique<PostDominatorTree>(args&: const_cast<Function &>(F));
974 PDT = PDTPtr.get();
975 }
976
977 estimateBlockWeights(F, DT, PDT);
978
979 // Walk the basic blocks in post-order so that we can build up state about
980 // the successors of a block iteratively.
981 for (const auto *BB : post_order(G: &F.getEntryBlock())) {
982 LLVM_DEBUG(dbgs() << "Computing probabilities for " << BB->getName()
983 << "\n");
984 // If there is no at least two successors, no sense to set probability.
985 if (BB->getTerminator()->getNumSuccessors() < 2)
986 continue;
987 if (calcMetadataWeights(BB))
988 continue;
989 if (calcEstimatedHeuristics(BB))
990 continue;
991 if (calcPointerHeuristics(BB))
992 continue;
993 if (calcZeroHeuristics(BB, TLI))
994 continue;
995 if (calcFloatingPointHeuristics(BB))
996 continue;
997 }
998}
999
1000} // end anonymous namespace
1001
1002MutableArrayRef<BranchProbability>
1003BranchProbabilityInfo::allocEdges(const BasicBlock *BB) {
1004 assert(BB->getParent() == LastF);
1005 assert(BlockNumberEpoch == LastF->getBlockNumberEpoch());
1006 unsigned NumSuccs = succ_size(BB);
1007 if (NumSuccs == 0) {
1008 eraseBlock(BB);
1009 return {};
1010 }
1011 if (EdgeStarts.size() <= BB->getNumber())
1012 EdgeStarts.resize(N: LastF->getMaxBlockNumber(), NV: 0);
1013 unsigned EdgeStart = Probs.size();
1014 EdgeStarts[BB->getNumber()] = EdgeStart + 1; // 0 = no edges.
1015 Probs.append(NumInputs: NumSuccs, Elt: {});
1016 return MutableArrayRef(&Probs[EdgeStart], NumSuccs);
1017}
1018
1019ArrayRef<BranchProbability>
1020BranchProbabilityInfo::getEdges(const BasicBlock *BB) const {
1021 assert(BB->getParent() == LastF);
1022 assert(BlockNumberEpoch == LastF->getBlockNumberEpoch());
1023 if (EdgeStarts.size() <= BB->getNumber())
1024 return {};
1025 if (unsigned EdgeStart = EdgeStarts[BB->getNumber()]) {
1026 const BranchProbability *Start = &Probs[EdgeStart - 1]; // 0 = no edges.
1027 size_t Count = SIZE_MAX; // Avoid querying num successors in release builds.
1028#ifndef NDEBUG
1029 Count = succ_size(BB);
1030#endif
1031 return ArrayRef(Start, Count);
1032 }
1033 return {};
1034}
1035
1036bool BranchProbabilityInfo::invalidate(Function &, const PreservedAnalyses &PA,
1037 FunctionAnalysisManager::Invalidator &) {
1038 // Check whether the analysis, all analyses on functions, or the function's
1039 // CFG have been preserved.
1040 auto PAC = PA.getChecker<BranchProbabilityAnalysis>();
1041 return !(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>() ||
1042 PAC.preservedSet<CFGAnalyses>());
1043}
1044
1045void BranchProbabilityInfo::print(raw_ostream &OS) const {
1046 OS << "---- Branch Probabilities ----\n";
1047 // We print the probabilities from the last function the analysis ran over,
1048 // or the function it is currently running over.
1049 assert(LastF && "Cannot print prior to running over a function");
1050 for (const auto &BI : *LastF) {
1051 for (const BasicBlock *Succ : successors(BB: &BI))
1052 printEdgeProbability(OS&: OS << " ", Src: &BI, Dst: Succ);
1053 }
1054}
1055
1056bool BranchProbabilityInfo::
1057isEdgeHot(const BasicBlock *Src, const BasicBlock *Dst) const {
1058 // Hot probability is at least 4/5 = 80%
1059 // FIXME: Compare against a static "hot" BranchProbability.
1060 return getEdgeProbability(Src, Dst) > BranchProbability(4, 5);
1061}
1062
1063/// Get the raw edge probability for the edge. If can't find it, return a
1064/// default probability 1/N where N is the number of successors. Here an edge is
1065/// specified using PredBlock and an
1066/// index to the successors.
1067BranchProbability
1068BranchProbabilityInfo::getEdgeProbability(const BasicBlock *Src,
1069 unsigned IndexInSuccessors) const {
1070 if (ArrayRef<BranchProbability> P = getEdges(BB: Src); !P.empty())
1071 return P[IndexInSuccessors];
1072 return {1, static_cast<uint32_t>(succ_size(BB: Src))};
1073}
1074
1075/// Get the raw edge probability calculated for the block pair. This returns the
1076/// sum of all raw edge probabilities from Src to Dst.
1077BranchProbability
1078BranchProbabilityInfo::getEdgeProbability(const BasicBlock *Src,
1079 const BasicBlock *Dst) const {
1080 ArrayRef<BranchProbability> P = getEdges(BB: Src);
1081 if (P.empty())
1082 return BranchProbability(llvm::count(Range: successors(BB: Src), Element: Dst), succ_size(BB: Src));
1083
1084 auto Prob = BranchProbability::getZero();
1085 for (auto It : enumerate(First: successors(BB: Src)))
1086 if (It.value() == Dst)
1087 Prob += P[It.index()];
1088
1089 return Prob;
1090}
1091
1092SmallVector<BranchProbability>
1093BranchProbabilityInfo::getEdgeProbabilitiesFromWeights(
1094 ArrayRef<uint32_t> Weights) {
1095 // If the sum of weights does not fit in 32 bits, scale every weight down
1096 // accordingly.
1097 SmallVector<uint32_t> ScaledWeights(Weights);
1098 uint64_t WeightSum = sum_of(Range&: ScaledWeights, Init: uint64_t(0));
1099 if (WeightSum > UINT32_MAX) {
1100 uint64_t ScalingFactor = WeightSum / UINT32_MAX + 1;
1101 for (uint32_t &Weight : ScaledWeights)
1102 Weight /= ScalingFactor;
1103 WeightSum = sum_of(Range&: ScaledWeights, Init: uint64_t(0));
1104 }
1105
1106 assert(WeightSum <= UINT32_MAX &&
1107 "Expected weights to scale down to 32 bits");
1108
1109 if (WeightSum == 0) {
1110 fill(Range&: ScaledWeights, Value: 1);
1111 WeightSum = ScaledWeights.size();
1112 }
1113
1114 return map_to_vector(C&: ScaledWeights, F: [WeightSum](uint32_t Weight) {
1115 return BranchProbability(Weight, static_cast<uint32_t>(WeightSum));
1116 });
1117}
1118
1119/// Set the edge probability for all edges at once.
1120void BranchProbabilityInfo::setEdgeProbability(
1121 const BasicBlock *Src, ArrayRef<BranchProbability> Probs) {
1122 assert(Src->getTerminator()->getNumSuccessors() == Probs.size());
1123 MutableArrayRef<BranchProbability> P = allocEdges(BB: Src);
1124 uint64_t TotalNumerator = 0;
1125 for (unsigned SuccIdx = 0; SuccIdx < Probs.size(); ++SuccIdx) {
1126 P[SuccIdx] = Probs[SuccIdx];
1127 LLVM_DEBUG(dbgs() << "set edge " << Src->getName() << " -> " << SuccIdx
1128 << " successor probability to " << Probs[SuccIdx]
1129 << "\n");
1130 TotalNumerator += Probs[SuccIdx].getNumerator();
1131 }
1132
1133 // Because of rounding errors the total probability cannot be checked to be
1134 // 1.0 exactly. That is TotalNumerator == BranchProbability::getDenominator.
1135 // Instead, every single probability in Probs must be as accurate as possible.
1136 // This results in error 1/denominator at most, thus the total absolute error
1137 // should be within Probs.size / BranchProbability::getDenominator.
1138 if (P.empty())
1139 return; // If we store no probabilities, TotalNumerator is zero.
1140 assert(TotalNumerator <= BranchProbability::getDenominator() + Probs.size());
1141 assert(TotalNumerator >= BranchProbability::getDenominator() - Probs.size());
1142 (void)TotalNumerator;
1143}
1144
1145void BranchProbabilityInfo::copyEdgeProbabilities(BasicBlock *Src,
1146 BasicBlock *Dst) {
1147 assert(succ_size(Src) == succ_size(Dst));
1148 // allocEdges can reallocate and must be called first.
1149 MutableArrayRef<BranchProbability> DstP = allocEdges(BB: Dst);
1150 ArrayRef<BranchProbability> SrcP = getEdges(BB: Src);
1151 if (SrcP.empty()) {
1152 // Nothing to copy from, erase again.
1153 eraseBlock(BB: Dst);
1154 return;
1155 }
1156 for (unsigned i = 0; i != DstP.size(); ++i) {
1157 DstP[i] = SrcP[i];
1158 LLVM_DEBUG(dbgs() << "set edge " << Dst->getName() << " -> " << i
1159 << " successor probability to " << SrcP[i] << "\n");
1160 }
1161}
1162
1163void BranchProbabilityInfo::swapSuccEdgesProbabilities(const BasicBlock *Src) {
1164 assert(Src->getTerminator()->getNumSuccessors() == 2);
1165 ArrayRef<BranchProbability> P = getEdges(BB: Src);
1166 if (P.empty())
1167 return;
1168 MutableArrayRef<BranchProbability> MP(
1169 const_cast<BranchProbability *>(P.data()), P.size());
1170 std::swap(a&: MP[0], b&: MP[1]);
1171}
1172
1173raw_ostream &
1174BranchProbabilityInfo::printEdgeProbability(raw_ostream &OS,
1175 const BasicBlock *Src,
1176 const BasicBlock *Dst) const {
1177 const BranchProbability Prob = getEdgeProbability(Src, Dst);
1178 OS << "edge ";
1179 Src->printAsOperand(O&: OS, PrintType: false, M: Src->getModule());
1180 OS << " -> ";
1181 Dst->printAsOperand(O&: OS, PrintType: false, M: Dst->getModule());
1182 OS << " probability is " << Prob
1183 << (isEdgeHot(Src, Dst) ? " [HOT edge]\n" : "\n");
1184
1185 return OS;
1186}
1187
1188void BranchProbabilityInfo::eraseBlock(const BasicBlock *BB) {
1189 LLVM_DEBUG(dbgs() << "eraseBlock " << BB->getName() << "\n");
1190 assert(BB->getParent() == LastF);
1191 assert(BlockNumberEpoch == LastF->getBlockNumberEpoch());
1192 if (EdgeStarts.size() > BB->getNumber())
1193 EdgeStarts[BB->getNumber()] = 0;
1194}
1195
1196void BranchProbabilityInfo::calculate(const Function &F,
1197 const CycleInfo &CycleI,
1198 const TargetLibraryInfo *TLI,
1199 DominatorTree *DT,
1200 PostDominatorTree *PDT) {
1201 LLVM_DEBUG(dbgs() << "---- Branch Probability Info : " << F.getName()
1202 << " ----\n\n");
1203 LastF = &F; // Store the last function we ran on for printing.
1204 BlockNumberEpoch = F.getBlockNumberEpoch();
1205 Probs.clear();
1206 EdgeStarts.clear();
1207 BPIConstruction(*this).calculate(F, CycleI, TLI, DT, PDT);
1208
1209 if (PrintBranchProb && (PrintBranchProbFuncName.empty() ||
1210 F.getName() == PrintBranchProbFuncName)) {
1211 print(OS&: dbgs());
1212 }
1213}
1214
1215void BranchProbabilityInfoWrapperPass::getAnalysisUsage(
1216 AnalysisUsage &AU) const {
1217 // We require DT so it's available when LI is available. The LI updating code
1218 // asserts that DT is also present so if we don't make sure that we have DT
1219 // here, that assert will trigger.
1220 AU.addRequired<DominatorTreeWrapperPass>();
1221 AU.addRequired<CycleInfoWrapperPass>();
1222 AU.addRequired<TargetLibraryInfoWrapperPass>();
1223 AU.addRequired<DominatorTreeWrapperPass>();
1224 AU.addRequired<PostDominatorTreeWrapperPass>();
1225 AU.setPreservesAll();
1226}
1227
1228bool BranchProbabilityInfoWrapperPass::runOnFunction(Function &F) {
1229 const CycleInfo &CI = getAnalysis<CycleInfoWrapperPass>().getResult();
1230 const TargetLibraryInfo &TLI =
1231 getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F);
1232 DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
1233 PostDominatorTree &PDT =
1234 getAnalysis<PostDominatorTreeWrapperPass>().getPostDomTree();
1235 BPI.calculate(F, CycleI: CI, TLI: &TLI, DT: &DT, PDT: &PDT);
1236 return false;
1237}
1238
1239void BranchProbabilityInfoWrapperPass::print(raw_ostream &OS,
1240 const Module *) const {
1241 BPI.print(OS);
1242}
1243
1244AnalysisKey BranchProbabilityAnalysis::Key;
1245BranchProbabilityInfo
1246BranchProbabilityAnalysis::run(Function &F, FunctionAnalysisManager &AM) {
1247 auto &CI = AM.getResult<CycleAnalysis>(IR&: F);
1248 auto &TLI = AM.getResult<TargetLibraryAnalysis>(IR&: F);
1249 auto &DT = AM.getResult<DominatorTreeAnalysis>(IR&: F);
1250 auto &PDT = AM.getResult<PostDominatorTreeAnalysis>(IR&: F);
1251 BranchProbabilityInfo BPI;
1252 BPI.calculate(F, CycleI: CI, TLI: &TLI, DT: &DT, PDT: &PDT);
1253 return BPI;
1254}
1255
1256PreservedAnalyses
1257BranchProbabilityPrinterPass::run(Function &F, FunctionAnalysisManager &AM) {
1258 OS << "Printing analysis 'Branch Probability Analysis' for function '"
1259 << F.getName() << "':\n";
1260 AM.getResult<BranchProbabilityAnalysis>(IR&: F).print(OS);
1261 return PreservedAnalyses::all();
1262}
1263