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