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