Line data Source code
1 : //===- BranchProbabilityInfo.cpp - Branch Probability Analysis ------------===//
2 : //
3 : // The LLVM Compiler Infrastructure
4 : //
5 : // This file is distributed under the University of Illinois Open Source
6 : // License. See LICENSE.TXT for details.
7 : //
8 : //===----------------------------------------------------------------------===//
9 : //
10 : // Loops should be simplified before this analysis.
11 : //
12 : //===----------------------------------------------------------------------===//
13 :
14 : #include "llvm/Analysis/BranchProbabilityInfo.h"
15 : #include "llvm/ADT/PostOrderIterator.h"
16 : #include "llvm/ADT/SCCIterator.h"
17 : #include "llvm/ADT/STLExtras.h"
18 : #include "llvm/ADT/SmallVector.h"
19 : #include "llvm/Analysis/LoopInfo.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/Type.h"
34 : #include "llvm/IR/Value.h"
35 : #include "llvm/Pass.h"
36 : #include "llvm/Support/BranchProbability.h"
37 : #include "llvm/Support/Casting.h"
38 : #include "llvm/Support/Debug.h"
39 : #include "llvm/Support/raw_ostream.h"
40 : #include <cassert>
41 : #include <cstdint>
42 : #include <iterator>
43 : #include <utility>
44 :
45 : using namespace llvm;
46 :
47 : #define DEBUG_TYPE "branch-prob"
48 :
49 : static cl::opt<bool> PrintBranchProb(
50 : "print-bpi", cl::init(false), cl::Hidden,
51 : cl::desc("Print the branch probability info."));
52 :
53 : cl::opt<std::string> PrintBranchProbFuncName(
54 : "print-bpi-func-name", cl::Hidden,
55 : cl::desc("The option to specify the name of the function "
56 : "whose branch probability info is printed."));
57 :
58 39825 : INITIALIZE_PASS_BEGIN(BranchProbabilityInfoWrapperPass, "branch-prob",
59 : "Branch Probability Analysis", false, true)
60 39825 : INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
61 39825 : INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
62 251210 : INITIALIZE_PASS_END(BranchProbabilityInfoWrapperPass, "branch-prob",
63 : "Branch Probability Analysis", false, true)
64 :
65 : char BranchProbabilityInfoWrapperPass::ID = 0;
66 :
67 : // Weights are for internal use only. They are used by heuristics to help to
68 : // estimate edges' probability. Example:
69 : //
70 : // Using "Loop Branch Heuristics" we predict weights of edges for the
71 : // block BB2.
72 : // ...
73 : // |
74 : // V
75 : // BB1<-+
76 : // | |
77 : // | | (Weight = 124)
78 : // V |
79 : // BB2--+
80 : // |
81 : // | (Weight = 4)
82 : // V
83 : // BB3
84 : //
85 : // Probability of the edge BB2->BB1 = 124 / (124 + 4) = 0.96875
86 : // Probability of the edge BB2->BB3 = 4 / (124 + 4) = 0.03125
87 : static const uint32_t LBH_TAKEN_WEIGHT = 124;
88 : static const uint32_t LBH_NONTAKEN_WEIGHT = 4;
89 : // Unlikely edges within a loop are half as likely as other edges
90 : static const uint32_t LBH_UNLIKELY_WEIGHT = 62;
91 :
92 : /// Unreachable-terminating branch taken probability.
93 : ///
94 : /// This is the probability for a branch being taken to a block that terminates
95 : /// (eventually) in unreachable. These are predicted as unlikely as possible.
96 : /// All reachable probability will equally share the remaining part.
97 : static const BranchProbability UR_TAKEN_PROB = BranchProbability::getRaw(1);
98 :
99 : /// Weight for a branch taken going into a cold block.
100 : ///
101 : /// This is the weight for a branch taken toward a block marked
102 : /// cold. A block is marked cold if it's postdominated by a
103 : /// block containing a call to a cold function. Cold functions
104 : /// are those marked with attribute 'cold'.
105 : static const uint32_t CC_TAKEN_WEIGHT = 4;
106 :
107 : /// Weight for a branch not-taken into a cold block.
108 : ///
109 : /// This is the weight for a branch not taken toward a block marked
110 : /// cold.
111 : static const uint32_t CC_NONTAKEN_WEIGHT = 64;
112 :
113 : static const uint32_t PH_TAKEN_WEIGHT = 20;
114 : static const uint32_t PH_NONTAKEN_WEIGHT = 12;
115 :
116 : static const uint32_t ZH_TAKEN_WEIGHT = 20;
117 : static const uint32_t ZH_NONTAKEN_WEIGHT = 12;
118 :
119 : static const uint32_t FPH_TAKEN_WEIGHT = 20;
120 : static const uint32_t FPH_NONTAKEN_WEIGHT = 12;
121 :
122 : /// Invoke-terminating normal branch taken weight
123 : ///
124 : /// This is the weight for branching to the normal destination of an invoke
125 : /// instruction. We expect this to happen most of the time. Set the weight to an
126 : /// absurdly high value so that nested loops subsume it.
127 : static const uint32_t IH_TAKEN_WEIGHT = 1024 * 1024 - 1;
128 :
129 : /// Invoke-terminating normal branch not-taken weight.
130 : ///
131 : /// This is the weight for branching to the unwind destination of an invoke
132 : /// instruction. This is essentially never taken.
133 : static const uint32_t IH_NONTAKEN_WEIGHT = 1;
134 :
135 : /// Add \p BB to PostDominatedByUnreachable set if applicable.
136 : void
137 2226272 : BranchProbabilityInfo::updatePostDominatedByUnreachable(const BasicBlock *BB) {
138 2226272 : const Instruction *TI = BB->getTerminator();
139 2226272 : if (TI->getNumSuccessors() == 0) {
140 1619344 : if (isa<UnreachableInst>(TI) ||
141 : // If this block is terminated by a call to
142 : // @llvm.experimental.deoptimize then treat it like an unreachable since
143 : // the @llvm.experimental.deoptimize call is expected to practically
144 : // never execute.
145 723145 : BB->getTerminatingDeoptimizeCall())
146 173059 : PostDominatedByUnreachable.insert(BB);
147 896199 : return;
148 : }
149 :
150 : // If the terminator is an InvokeInst, check only the normal destination block
151 : // as the unwind edge of InvokeInst is also very unlikely taken.
152 : if (auto *II = dyn_cast<InvokeInst>(TI)) {
153 635438 : if (PostDominatedByUnreachable.count(II->getNormalDest()))
154 19293 : PostDominatedByUnreachable.insert(BB);
155 317719 : return;
156 : }
157 :
158 2103876 : for (auto *I : successors(BB))
159 : // If any of successor is not post dominated then BB is also not.
160 1041867 : if (!PostDominatedByUnreachable.count(I))
161 : return;
162 :
163 49654 : PostDominatedByUnreachable.insert(BB);
164 : }
165 :
166 : /// Add \p BB to PostDominatedByColdCall set if applicable.
167 : void
168 2226272 : BranchProbabilityInfo::updatePostDominatedByColdCall(const BasicBlock *BB) {
169 : assert(!PostDominatedByColdCall.count(BB));
170 2226272 : const Instruction *TI = BB->getTerminator();
171 2226272 : if (TI->getNumSuccessors() == 0)
172 : return;
173 :
174 : // If all of successor are post dominated then BB is also done.
175 1330074 : if (llvm::all_of(successors(BB), [&](const BasicBlock *SuccBB) {
176 0 : return PostDominatedByColdCall.count(SuccBB);
177 : })) {
178 102 : PostDominatedByColdCall.insert(BB);
179 102 : return;
180 : }
181 :
182 : // If the terminator is an InvokeInst, check only the normal destination
183 : // block as the unwind edge of InvokeInst is also very unlikely taken.
184 : if (auto *II = dyn_cast<InvokeInst>(TI))
185 635432 : if (PostDominatedByColdCall.count(II->getNormalDest())) {
186 492 : PostDominatedByColdCall.insert(BB);
187 492 : return;
188 : }
189 :
190 : // Otherwise, if the block itself contains a cold function, add it to the
191 : // set of blocks post-dominated by a cold call.
192 14668703 : for (auto &I : *BB)
193 : if (const CallInst *CI = dyn_cast<CallInst>(&I))
194 1578511 : if (CI->hasFnAttr(Attribute::Cold)) {
195 335 : PostDominatedByColdCall.insert(BB);
196 : return;
197 : }
198 : }
199 :
200 : /// Calculate edge weights for successors lead to unreachable.
201 : ///
202 : /// Predict that a successor which leads necessarily to an
203 : /// unreachable-terminated block as extremely unlikely.
204 415223 : bool BranchProbabilityInfo::calcUnreachableHeuristics(const BasicBlock *BB) {
205 : const Instruction *TI = BB->getTerminator();
206 : (void) TI;
207 : assert(TI->getNumSuccessors() > 1 && "expected more than one successor!");
208 : assert(!isa<InvokeInst>(TI) &&
209 : "Invokes should have already been handled by calcInvokeHeuristics");
210 :
211 : SmallVector<unsigned, 4> UnreachableEdges;
212 : SmallVector<unsigned, 4> ReachableEdges;
213 :
214 1273808 : for (succ_const_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I)
215 858585 : if (PostDominatedByUnreachable.count(*I))
216 45916 : UnreachableEdges.push_back(I.getSuccessorIndex());
217 : else
218 812669 : ReachableEdges.push_back(I.getSuccessorIndex());
219 :
220 : // Skip probabilities if all were reachable.
221 415223 : if (UnreachableEdges.empty())
222 : return false;
223 :
224 28510 : if (ReachableEdges.empty()) {
225 12559 : BranchProbability Prob(1, UnreachableEdges.size());
226 37996 : for (unsigned SuccIdx : UnreachableEdges)
227 25437 : setEdgeProbability(BB, SuccIdx, Prob);
228 : return true;
229 : }
230 :
231 15951 : auto UnreachableProb = UR_TAKEN_PROB;
232 : auto ReachableProb =
233 : (BranchProbability::getOne() - UR_TAKEN_PROB * UnreachableEdges.size()) /
234 15951 : ReachableEdges.size();
235 :
236 36430 : for (unsigned SuccIdx : UnreachableEdges)
237 20479 : setEdgeProbability(BB, SuccIdx, UnreachableProb);
238 33830 : for (unsigned SuccIdx : ReachableEdges)
239 17879 : setEdgeProbability(BB, SuccIdx, ReachableProb);
240 :
241 : return true;
242 : }
243 :
244 : // Propagate existing explicit probabilities from either profile data or
245 : // 'expect' intrinsic processing. Examine metadata against unreachable
246 : // heuristic. The probability of the edge coming to unreachable block is
247 : // set to min of metadata and unreachable heuristic.
248 755782 : bool BranchProbabilityInfo::calcMetadataWeights(const BasicBlock *BB) {
249 755782 : const Instruction *TI = BB->getTerminator();
250 : assert(TI->getNumSuccessors() > 1 && "expected more than one successor!");
251 755782 : if (!(isa<BranchInst>(TI) || isa<SwitchInst>(TI) || isa<IndirectBrInst>(TI)))
252 : return false;
253 :
254 : MDNode *WeightsNode = TI->getMetadata(LLVMContext::MD_prof);
255 389506 : if (!WeightsNode)
256 415115 : return false;
257 :
258 : // Check that the number of successors is manageable.
259 : assert(TI->getNumSuccessors() < UINT32_MAX && "Too many successors");
260 :
261 : // Ensure there are weights for all of the successors. Note that the first
262 : // operand to the metadata node is a name, not a weight.
263 22848 : if (WeightsNode->getNumOperands() != TI->getNumSuccessors() + 1)
264 : return false;
265 :
266 : // Build up the final weights that will be used in a temporary buffer.
267 : // Compute the sum of all weights to later decide whether they need to
268 : // be scaled to fit in 32 bits.
269 : uint64_t WeightSum = 0;
270 : SmallVector<uint32_t, 2> Weights;
271 : SmallVector<unsigned, 2> UnreachableIdxs;
272 : SmallVector<unsigned, 2> ReachableIdxs;
273 22840 : Weights.reserve(TI->getNumSuccessors());
274 68966 : for (unsigned i = 1, e = WeightsNode->getNumOperands(); i != e; ++i) {
275 : ConstantInt *Weight =
276 : mdconst::dyn_extract<ConstantInt>(WeightsNode->getOperand(i));
277 : if (!Weight)
278 : return false;
279 : assert(Weight->getValue().getActiveBits() <= 32 &&
280 : "Too many bits for uint32_t");
281 46126 : Weights.push_back(Weight->getZExtValue());
282 46126 : WeightSum += Weights.back();
283 46126 : if (PostDominatedByUnreachable.count(TI->getSuccessor(i - 1)))
284 17310 : UnreachableIdxs.push_back(i - 1);
285 : else
286 28816 : ReachableIdxs.push_back(i - 1);
287 : }
288 : assert(Weights.size() == TI->getNumSuccessors() && "Checked above");
289 :
290 : // If the sum of weights does not fit in 32 bits, scale every weight down
291 : // accordingly.
292 : uint64_t ScalingFactor =
293 22840 : (WeightSum > UINT32_MAX) ? WeightSum / UINT32_MAX + 1 : 1;
294 :
295 : if (ScalingFactor > 1) {
296 : WeightSum = 0;
297 84 : for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) {
298 65 : Weights[i] /= ScalingFactor;
299 65 : WeightSum += Weights[i];
300 : }
301 : }
302 : assert(WeightSum <= UINT32_MAX &&
303 : "Expected weights to scale down to 32 bits");
304 :
305 22840 : if (WeightSum == 0 || ReachableIdxs.size() == 0) {
306 489 : for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i)
307 658 : Weights[i] = 1;
308 160 : WeightSum = TI->getNumSuccessors();
309 : }
310 :
311 : // Set the probability.
312 : SmallVector<BranchProbability, 2> BP;
313 68966 : for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i)
314 92252 : BP.push_back({ Weights[i], static_cast<uint32_t>(WeightSum) });
315 :
316 : // Examine the metadata against unreachable heuristic.
317 : // If the unreachable heuristic is more strong then we use it for this edge.
318 45680 : if (UnreachableIdxs.size() > 0 && ReachableIdxs.size() > 0) {
319 : auto ToDistribute = BranchProbability::getZero();
320 16933 : auto UnreachableProb = UR_TAKEN_PROB;
321 33920 : for (auto i : UnreachableIdxs)
322 33974 : if (UnreachableProb < BP[i]) {
323 : ToDistribute += BP[i] - UnreachableProb;
324 16978 : BP[i] = UnreachableProb;
325 : }
326 :
327 : // If we modified the probability of some edges then we must distribute
328 : // the difference between reachable blocks.
329 16933 : if (ToDistribute > BranchProbability::getZero()) {
330 16927 : BranchProbability PerEdge = ToDistribute / ReachableIdxs.size();
331 33875 : for (auto i : ReachableIdxs)
332 16948 : BP[i] += PerEdge;
333 : }
334 : }
335 :
336 68966 : for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i)
337 92252 : setEdgeProbability(BB, i, BP[i]);
338 :
339 : return true;
340 : }
341 :
342 : /// Calculate edge weights for edges leading to cold blocks.
343 : ///
344 : /// A cold block is one post-dominated by a block with a call to a
345 : /// cold function. Those edges are unlikely to be taken, so we give
346 : /// them relatively low weight.
347 : ///
348 : /// Return true if we could compute the weights for cold edges.
349 : /// Return false, otherwise.
350 386713 : bool BranchProbabilityInfo::calcColdCallHeuristics(const BasicBlock *BB) {
351 : const Instruction *TI = BB->getTerminator();
352 : (void) TI;
353 : assert(TI->getNumSuccessors() > 1 && "expected more than one successor!");
354 : assert(!isa<InvokeInst>(TI) &&
355 : "Invokes should have already been handled by calcInvokeHeuristics");
356 :
357 : // Determine which successors are post-dominated by a cold block.
358 : SmallVector<unsigned, 4> ColdEdges;
359 : SmallVector<unsigned, 4> NormalEdges;
360 1181503 : for (succ_const_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I)
361 794790 : if (PostDominatedByColdCall.count(*I))
362 364 : ColdEdges.push_back(I.getSuccessorIndex());
363 : else
364 794426 : NormalEdges.push_back(I.getSuccessorIndex());
365 :
366 : // Skip probabilities if no cold edges.
367 386713 : if (ColdEdges.empty())
368 : return false;
369 :
370 322 : if (NormalEdges.empty()) {
371 42 : BranchProbability Prob(1, ColdEdges.size());
372 126 : for (unsigned SuccIdx : ColdEdges)
373 84 : setEdgeProbability(BB, SuccIdx, Prob);
374 : return true;
375 : }
376 :
377 : auto ColdProb = BranchProbability::getBranchProbability(
378 : CC_TAKEN_WEIGHT,
379 280 : (CC_TAKEN_WEIGHT + CC_NONTAKEN_WEIGHT) * uint64_t(ColdEdges.size()));
380 : auto NormalProb = BranchProbability::getBranchProbability(
381 : CC_NONTAKEN_WEIGHT,
382 560 : (CC_TAKEN_WEIGHT + CC_NONTAKEN_WEIGHT) * uint64_t(NormalEdges.size()));
383 :
384 560 : for (unsigned SuccIdx : ColdEdges)
385 280 : setEdgeProbability(BB, SuccIdx, ColdProb);
386 560 : for (unsigned SuccIdx : NormalEdges)
387 280 : setEdgeProbability(BB, SuccIdx, NormalProb);
388 :
389 : return true;
390 : }
391 :
392 : // Calculate Edge Weights using "Pointer Heuristics". Predict a comparison
393 : // between two pointer or pointer and NULL will fail.
394 333811 : bool BranchProbabilityInfo::calcPointerHeuristics(const BasicBlock *BB) {
395 333811 : const BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator());
396 327947 : if (!BI || !BI->isConditional())
397 : return false;
398 :
399 : Value *Cond = BI->getCondition();
400 : ICmpInst *CI = dyn_cast<ICmpInst>(Cond);
401 263475 : if (!CI || !CI->isEquality())
402 : return false;
403 :
404 : Value *LHS = CI->getOperand(0);
405 :
406 451814 : if (!LHS->getType()->isPointerTy())
407 : return false;
408 :
409 : assert(CI->getOperand(1)->getType()->isPointerTy());
410 :
411 : // p != 0 -> isProb = true
412 : // p == 0 -> isProb = false
413 : // p != q -> isProb = true
414 : // p == q -> isProb = false;
415 : unsigned TakenIdx = 0, NonTakenIdx = 1;
416 : bool isProb = CI->getPredicate() == ICmpInst::ICMP_NE;
417 128640 : if (!isProb)
418 : std::swap(TakenIdx, NonTakenIdx);
419 :
420 : BranchProbability TakenProb(PH_TAKEN_WEIGHT,
421 128640 : PH_TAKEN_WEIGHT + PH_NONTAKEN_WEIGHT);
422 128640 : setEdgeProbability(BB, TakenIdx, TakenProb);
423 257280 : setEdgeProbability(BB, NonTakenIdx, TakenProb.getCompl());
424 128640 : return true;
425 : }
426 :
427 : static int getSCCNum(const BasicBlock *BB,
428 : const BranchProbabilityInfo::SccInfo &SccI) {
429 277159 : auto SccIt = SccI.SccNums.find(BB);
430 277159 : if (SccIt == SccI.SccNums.end())
431 : return -1;
432 839 : return SccIt->second;
433 : }
434 :
435 : // Consider any block that is an entry point to the SCC as a header.
436 839 : static bool isSCCHeader(const BasicBlock *BB, int SccNum,
437 : BranchProbabilityInfo::SccInfo &SccI) {
438 : assert(getSCCNum(BB, SccI) == SccNum);
439 :
440 : // Lazily compute the set of headers for a given SCC and cache the results
441 : // in the SccHeaderMap.
442 1678 : if (SccI.SccHeaders.size() <= static_cast<unsigned>(SccNum))
443 56 : SccI.SccHeaders.resize(SccNum + 1);
444 839 : auto &HeaderMap = SccI.SccHeaders[SccNum];
445 : bool Inserted;
446 : BranchProbabilityInfo::SccHeaderMap::iterator HeaderMapIt;
447 839 : std::tie(HeaderMapIt, Inserted) = HeaderMap.insert(std::make_pair(BB, false));
448 839 : if (Inserted) {
449 600 : bool IsHeader = llvm::any_of(make_range(pred_begin(BB), pred_end(BB)),
450 : [&](const BasicBlock *Pred) {
451 : return getSCCNum(Pred, SccI) != SccNum;
452 : });
453 600 : HeaderMapIt->second = IsHeader;
454 600 : return IsHeader;
455 : } else
456 239 : return HeaderMapIt->second;
457 : }
458 :
459 : // Compute the unlikely successors to the block BB in the loop L, specifically
460 : // those that are unlikely because this is a loop, and add them to the
461 : // UnlikelyBlocks set.
462 : static void
463 110316 : computeUnlikelySuccessors(const BasicBlock *BB, Loop *L,
464 : SmallPtrSetImpl<const BasicBlock*> &UnlikelyBlocks) {
465 : // Sometimes in a loop we have a branch whose condition is made false by
466 : // taking it. This is typically something like
467 : // int n = 0;
468 : // while (...) {
469 : // if (++n >= MAX) {
470 : // n = 0;
471 : // }
472 : // }
473 : // In this sort of situation taking the branch means that at the very least it
474 : // won't be taken again in the next iteration of the loop, so we should
475 : // consider it less likely than a typical branch.
476 : //
477 : // We detect this by looking back through the graph of PHI nodes that sets the
478 : // value that the condition depends on, and seeing if we can reach a successor
479 : // block which can be determined to make the condition false.
480 : //
481 : // FIXME: We currently consider unlikely blocks to be half as likely as other
482 : // blocks, but if we consider the example above the likelyhood is actually
483 : // 1/MAX. We could therefore be more precise in how unlikely we consider
484 : // blocks to be, but it would require more careful examination of the form
485 : // of the comparison expression.
486 110316 : const BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator());
487 108823 : if (!BI || !BI->isConditional())
488 91884 : return;
489 :
490 : // Check if the branch is based on an instruction compared with a constant
491 : CmpInst *CI = dyn_cast<CmpInst>(BI->getCondition());
492 185982 : if (!CI || !isa<Instruction>(CI->getOperand(0)) ||
493 : !isa<Constant>(CI->getOperand(1)))
494 : return;
495 :
496 : // Either the instruction must be a PHI, or a chain of operations involving
497 : // constants that ends in a PHI which we can then collapse into a single value
498 : // if the PHI value is known.
499 : Instruction *CmpLHS = dyn_cast<Instruction>(CI->getOperand(0));
500 59572 : PHINode *CmpPHI = dyn_cast<PHINode>(CmpLHS);
501 : Constant *CmpConst = dyn_cast<Constant>(CI->getOperand(1));
502 : // Collect the instructions until we hit a PHI
503 : SmallVector<BinaryOperator *, 1> InstChain;
504 95356 : while (!CmpPHI && CmpLHS && isa<BinaryOperator>(CmpLHS) &&
505 19554 : isa<Constant>(CmpLHS->getOperand(1))) {
506 : // Stop if the chain extends outside of the loop
507 16635 : if (!L->contains(CmpLHS))
508 : return;
509 16230 : InstChain.push_back(cast<BinaryOperator>(CmpLHS));
510 : CmpLHS = dyn_cast<Instruction>(CmpLHS->getOperand(0));
511 : if (CmpLHS)
512 16161 : CmpPHI = dyn_cast<PHINode>(CmpLHS);
513 : }
514 77811 : if (!CmpPHI || !L->contains(CmpPHI))
515 40735 : return;
516 :
517 : // Trace the phi node to find all values that come from successors of BB
518 : SmallPtrSet<PHINode*, 8> VisitedInsts;
519 : SmallVector<PHINode*, 8> WorkList;
520 18432 : WorkList.push_back(CmpPHI);
521 18432 : VisitedInsts.insert(CmpPHI);
522 40576 : while (!WorkList.empty()) {
523 22144 : PHINode *P = WorkList.back();
524 : WorkList.pop_back();
525 69546 : for (BasicBlock *B : P->blocks()) {
526 : // Skip blocks that aren't part of the loop
527 47402 : if (!L->contains(B))
528 : continue;
529 31323 : Value *V = P->getIncomingValueForBlock(B);
530 : // If the source is a PHI add it to the work list if we haven't
531 : // already visited it.
532 31323 : if (PHINode *PN = dyn_cast<PHINode>(V)) {
533 6487 : if (VisitedInsts.insert(PN).second)
534 3712 : WorkList.push_back(PN);
535 6487 : continue;
536 : }
537 : // If this incoming value is a constant and B is a successor of BB, then
538 : // we can constant-evaluate the compare to see if it makes the branch be
539 : // taken or not.
540 : Constant *CmpLHSConst = dyn_cast<Constant>(V);
541 5448 : if (!CmpLHSConst ||
542 5448 : std::find(succ_begin(BB), succ_end(BB), B) == succ_end(BB))
543 24392 : continue;
544 : // First collapse InstChain
545 465 : for (Instruction *I : llvm::reverse(InstChain)) {
546 42 : CmpLHSConst = ConstantExpr::get(I->getOpcode(), CmpLHSConst,
547 : cast<Constant>(I->getOperand(1)), true);
548 21 : if (!CmpLHSConst)
549 : break;
550 : }
551 444 : if (!CmpLHSConst)
552 : continue;
553 : // Now constant-evaluate the compare
554 444 : Constant *Result = ConstantExpr::getCompare(CI->getPredicate(),
555 : CmpLHSConst, CmpConst, true);
556 : // If the result means we don't branch to the block then that block is
557 : // unlikely.
558 888 : if (Result &&
559 894 : ((Result->isZeroValue() && B == BI->getSuccessor(0)) ||
560 752 : (Result->isOneValue() && B == BI->getSuccessor(1))))
561 75 : UnlikelyBlocks.insert(B);
562 : }
563 : }
564 : }
565 :
566 : // Calculate Edge Weights using "Loop Branch Heuristics". Predict backedges
567 : // as taken, exiting edges as not-taken.
568 386391 : bool BranchProbabilityInfo::calcLoopBranchHeuristics(const BasicBlock *BB,
569 : const LoopInfo &LI,
570 : SccInfo &SccI) {
571 : int SccNum;
572 : Loop *L = LI.getLoopFor(BB);
573 110316 : if (!L) {
574 : SccNum = getSCCNum(BB, SccI);
575 449 : if (SccNum < 0)
576 275626 : return false;
577 : }
578 :
579 : SmallPtrSet<const BasicBlock*, 8> UnlikelyBlocks;
580 110765 : if (L)
581 110316 : computeUnlikelySuccessors(BB, L, UnlikelyBlocks);
582 :
583 : SmallVector<unsigned, 8> BackEdges;
584 : SmallVector<unsigned, 8> ExitingEdges;
585 : SmallVector<unsigned, 8> InEdges; // Edges from header to the loop.
586 : SmallVector<unsigned, 8> UnlikelyEdges;
587 :
588 336137 : for (succ_const_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I) {
589 : // Use LoopInfo if we have it, otherwise fall-back to SCC info to catch
590 : // irreducible loops.
591 225372 : if (L) {
592 224288 : if (UnlikelyBlocks.count(*I) != 0)
593 75 : UnlikelyEdges.push_back(I.getSuccessorIndex());
594 224213 : else if (!L->contains(*I))
595 53071 : ExitingEdges.push_back(I.getSuccessorIndex());
596 171142 : else if (L->getHeader() == *I)
597 31914 : BackEdges.push_back(I.getSuccessorIndex());
598 : else
599 139228 : InEdges.push_back(I.getSuccessorIndex());
600 : } else {
601 1084 : if (getSCCNum(*I, SccI) != SccNum)
602 245 : ExitingEdges.push_back(I.getSuccessorIndex());
603 839 : else if (isSCCHeader(*I, SccNum, SccI))
604 87 : BackEdges.push_back(I.getSuccessorIndex());
605 : else
606 752 : InEdges.push_back(I.getSuccessorIndex());
607 : }
608 : }
609 :
610 110765 : if (BackEdges.empty() && ExitingEdges.empty() && UnlikelyEdges.empty())
611 : return false;
612 :
613 : // Collect the sum of probabilities of back-edges/in-edges/exiting-edges, and
614 : // normalize them so that they sum up to one.
615 52580 : unsigned Denom = (BackEdges.empty() ? 0 : LBH_TAKEN_WEIGHT) +
616 52580 : (InEdges.empty() ? 0 : LBH_TAKEN_WEIGHT) +
617 52580 : (UnlikelyEdges.empty() ? 0 : LBH_UNLIKELY_WEIGHT) +
618 52580 : (ExitingEdges.empty() ? 0 : LBH_NONTAKEN_WEIGHT);
619 :
620 52580 : if (uint32_t numBackEdges = BackEdges.size()) {
621 31943 : BranchProbability TakenProb = BranchProbability(LBH_TAKEN_WEIGHT, Denom);
622 31943 : auto Prob = TakenProb / numBackEdges;
623 63944 : for (unsigned SuccIdx : BackEdges)
624 32001 : setEdgeProbability(BB, SuccIdx, Prob);
625 : }
626 :
627 52580 : if (uint32_t numInEdges = InEdges.size()) {
628 20990 : BranchProbability TakenProb = BranchProbability(LBH_TAKEN_WEIGHT, Denom);
629 20990 : auto Prob = TakenProb / numInEdges;
630 42540 : for (unsigned SuccIdx : InEdges)
631 21550 : setEdgeProbability(BB, SuccIdx, Prob);
632 : }
633 :
634 52580 : if (uint32_t numExitingEdges = ExitingEdges.size()) {
635 : BranchProbability NotTakenProb = BranchProbability(LBH_NONTAKEN_WEIGHT,
636 52148 : Denom);
637 52148 : auto Prob = NotTakenProb / numExitingEdges;
638 105464 : for (unsigned SuccIdx : ExitingEdges)
639 53316 : setEdgeProbability(BB, SuccIdx, Prob);
640 : }
641 :
642 52580 : if (uint32_t numUnlikelyEdges = UnlikelyEdges.size()) {
643 : BranchProbability UnlikelyProb = BranchProbability(LBH_UNLIKELY_WEIGHT,
644 73 : Denom);
645 73 : auto Prob = UnlikelyProb / numUnlikelyEdges;
646 148 : for (unsigned SuccIdx : UnlikelyEdges)
647 75 : setEdgeProbability(BB, SuccIdx, Prob);
648 : }
649 :
650 : return true;
651 : }
652 :
653 205171 : bool BranchProbabilityInfo::calcZeroHeuristics(const BasicBlock *BB,
654 : const TargetLibraryInfo *TLI) {
655 205171 : const BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator());
656 199307 : if (!BI || !BI->isConditional())
657 : return false;
658 :
659 : Value *Cond = BI->getCondition();
660 : ICmpInst *CI = dyn_cast<ICmpInst>(Cond);
661 : if (!CI)
662 : return false;
663 :
664 : Value *RHS = CI->getOperand(1);
665 : ConstantInt *CV = dyn_cast<ConstantInt>(RHS);
666 : if (!CV)
667 : return false;
668 :
669 : // If the LHS is the result of AND'ing a value with a single bit bitmask,
670 : // we don't have information about probabilities.
671 : if (Instruction *LHS = dyn_cast<Instruction>(CI->getOperand(0)))
672 90077 : if (LHS->getOpcode() == Instruction::And)
673 19069 : if (ConstantInt *AndRHS = dyn_cast<ConstantInt>(LHS->getOperand(1)))
674 17655 : if (AndRHS->getValue().isPowerOf2())
675 : return false;
676 :
677 : // Check if the LHS is the return value of a library function
678 83989 : LibFunc Func = NumLibFuncs;
679 83989 : if (TLI)
680 : if (CallInst *Call = dyn_cast<CallInst>(CI->getOperand(0)))
681 : if (Function *CalledFn = Call->getCalledFunction())
682 6585 : TLI->getLibFunc(*CalledFn, Func);
683 :
684 : bool isProb;
685 83989 : if (Func == LibFunc_strcasecmp ||
686 83616 : Func == LibFunc_strcmp ||
687 83613 : Func == LibFunc_strncasecmp ||
688 83502 : Func == LibFunc_strncmp ||
689 : Func == LibFunc_memcmp) {
690 : // strcmp and similar functions return zero, negative, or positive, if the
691 : // first string is equal, less, or greater than the second. We consider it
692 : // likely that the strings are not equal, so a comparison with zero is
693 : // probably false, but also a comparison with any other number is also
694 : // probably false given that what exactly is returned for nonzero values is
695 : // not specified. Any kind of comparison other than equality we know
696 : // nothing about.
697 691 : switch (CI->getPredicate()) {
698 : case CmpInst::ICMP_EQ:
699 : isProb = false;
700 : break;
701 : case CmpInst::ICMP_NE:
702 : isProb = true;
703 : break;
704 : default:
705 : return false;
706 : }
707 83298 : } else if (CV->isZero()) {
708 50463 : switch (CI->getPredicate()) {
709 : case CmpInst::ICMP_EQ:
710 : // X == 0 -> Unlikely
711 : isProb = false;
712 : break;
713 : case CmpInst::ICMP_NE:
714 : // X != 0 -> Likely
715 : isProb = true;
716 : break;
717 : case CmpInst::ICMP_SLT:
718 : // X < 0 -> Unlikely
719 : isProb = false;
720 : break;
721 : case CmpInst::ICMP_SGT:
722 : // X > 0 -> Likely
723 : isProb = true;
724 : break;
725 : default:
726 : return false;
727 : }
728 32835 : } else if (CV->isOne() && CI->getPredicate() == CmpInst::ICMP_SLT) {
729 : // InstCombine canonicalizes X <= 0 into X < 1.
730 : // X <= 0 -> Unlikely
731 : isProb = false;
732 32667 : } else if (CV->isMinusOne()) {
733 3527 : switch (CI->getPredicate()) {
734 : case CmpInst::ICMP_EQ:
735 : // X == -1 -> Unlikely
736 : isProb = false;
737 : break;
738 : case CmpInst::ICMP_NE:
739 : // X != -1 -> Likely
740 : isProb = true;
741 : break;
742 : case CmpInst::ICMP_SGT:
743 : // InstCombine canonicalizes X >= 0 into X > -1.
744 : // X >= 0 -> Likely
745 : isProb = true;
746 : break;
747 : default:
748 : return false;
749 : }
750 : } else {
751 : return false;
752 : }
753 :
754 : unsigned TakenIdx = 0, NonTakenIdx = 1;
755 :
756 : if (!isProb)
757 : std::swap(TakenIdx, NonTakenIdx);
758 :
759 : BranchProbability TakenProb(ZH_TAKEN_WEIGHT,
760 54522 : ZH_TAKEN_WEIGHT + ZH_NONTAKEN_WEIGHT);
761 54522 : setEdgeProbability(BB, TakenIdx, TakenProb);
762 109044 : setEdgeProbability(BB, NonTakenIdx, TakenProb.getCompl());
763 54522 : return true;
764 : }
765 :
766 150649 : bool BranchProbabilityInfo::calcFloatingPointHeuristics(const BasicBlock *BB) {
767 150649 : const BranchInst *BI = dyn_cast<BranchInst>(BB->getTerminator());
768 144785 : if (!BI || !BI->isConditional())
769 : return false;
770 :
771 : Value *Cond = BI->getCondition();
772 : FCmpInst *FCmp = dyn_cast<FCmpInst>(Cond);
773 : if (!FCmp)
774 : return false;
775 :
776 : bool isProb;
777 : if (FCmp->isEquality()) {
778 : // f1 == f2 -> Unlikely
779 : // f1 != f2 -> Likely
780 : isProb = !FCmp->isTrueWhenEqual();
781 2684 : } else if (FCmp->getPredicate() == FCmpInst::FCMP_ORD) {
782 : // !isnan -> Likely
783 : isProb = true;
784 2579 : } else if (FCmp->getPredicate() == FCmpInst::FCMP_UNO) {
785 : // isnan -> Unlikely
786 : isProb = false;
787 : } else {
788 : return false;
789 : }
790 :
791 : unsigned TakenIdx = 0, NonTakenIdx = 1;
792 :
793 511 : if (!isProb)
794 : std::swap(TakenIdx, NonTakenIdx);
795 :
796 : BranchProbability TakenProb(FPH_TAKEN_WEIGHT,
797 651 : FPH_TAKEN_WEIGHT + FPH_NONTAKEN_WEIGHT);
798 651 : setEdgeProbability(BB, TakenIdx, TakenProb);
799 1302 : setEdgeProbability(BB, NonTakenIdx, TakenProb.getCompl());
800 651 : return true;
801 : }
802 :
803 732942 : bool BranchProbabilityInfo::calcInvokeHeuristics(const BasicBlock *BB) {
804 732942 : const InvokeInst *II = dyn_cast<InvokeInst>(BB->getTerminator());
805 : if (!II)
806 : return false;
807 :
808 : BranchProbability TakenProb(IH_TAKEN_WEIGHT,
809 317719 : IH_TAKEN_WEIGHT + IH_NONTAKEN_WEIGHT);
810 317719 : setEdgeProbability(BB, 0 /*Index for Normal*/, TakenProb);
811 635438 : setEdgeProbability(BB, 1 /*Index for Unwind*/, TakenProb.getCompl());
812 317719 : return true;
813 : }
814 :
815 497604 : void BranchProbabilityInfo::releaseMemory() {
816 497604 : Probs.clear();
817 497604 : }
818 :
819 164 : void BranchProbabilityInfo::print(raw_ostream &OS) const {
820 164 : OS << "---- Branch Probabilities ----\n";
821 : // We print the probabilities from the last function the analysis ran over,
822 : // or the function it is currently running over.
823 : assert(LastF && "Cannot print prior to running over a function");
824 979 : for (const auto &BI : *LastF) {
825 1732 : for (succ_const_iterator SI = succ_begin(&BI), SE = succ_end(&BI); SI != SE;
826 : ++SI) {
827 917 : printEdgeProbability(OS << " ", &BI, *SI);
828 : }
829 : }
830 164 : }
831 :
832 919 : bool BranchProbabilityInfo::
833 : isEdgeHot(const BasicBlock *Src, const BasicBlock *Dst) const {
834 : // Hot probability is at least 4/5 = 80%
835 : // FIXME: Compare against a static "hot" BranchProbability.
836 919 : return getEdgeProbability(Src, Dst) > BranchProbability(4, 5);
837 : }
838 :
839 : const BasicBlock *
840 0 : BranchProbabilityInfo::getHotSucc(const BasicBlock *BB) const {
841 : auto MaxProb = BranchProbability::getZero();
842 : const BasicBlock *MaxSucc = nullptr;
843 :
844 0 : for (succ_const_iterator I = succ_begin(BB), E = succ_end(BB); I != E; ++I) {
845 : const BasicBlock *Succ = *I;
846 0 : auto Prob = getEdgeProbability(BB, Succ);
847 0 : if (Prob > MaxProb) {
848 : MaxProb = Prob;
849 : MaxSucc = Succ;
850 : }
851 : }
852 :
853 : // Hot probability is at least 4/5 = 80%
854 0 : if (MaxProb > BranchProbability(4, 5))
855 0 : return MaxSucc;
856 :
857 : return nullptr;
858 : }
859 :
860 : /// Get the raw edge probability for the edge. If can't find it, return a
861 : /// default probability 1/N where N is the number of successors. Here an edge is
862 : /// specified using PredBlock and an
863 : /// index to the successors.
864 : BranchProbability
865 1808997 : BranchProbabilityInfo::getEdgeProbability(const BasicBlock *Src,
866 : unsigned IndexInSuccessors) const {
867 1808997 : auto I = Probs.find(std::make_pair(Src, IndexInSuccessors));
868 :
869 1808997 : if (I != Probs.end())
870 1034216 : return I->second;
871 :
872 774781 : return {1, static_cast<uint32_t>(succ_size(Src))};
873 : }
874 :
875 : BranchProbability
876 1803632 : BranchProbabilityInfo::getEdgeProbability(const BasicBlock *Src,
877 : succ_const_iterator Dst) const {
878 1803632 : return getEdgeProbability(Src, Dst.getSuccessorIndex());
879 : }
880 :
881 : /// Get the raw edge probability calculated for the block pair. This returns the
882 : /// sum of all raw edge probabilities from Src to Dst.
883 : BranchProbability
884 221921 : BranchProbabilityInfo::getEdgeProbability(const BasicBlock *Src,
885 : const BasicBlock *Dst) const {
886 : auto Prob = BranchProbability::getZero();
887 : bool FoundProb = false;
888 679315 : for (succ_const_iterator I = succ_begin(Src), E = succ_end(Src); I != E; ++I)
889 457394 : if (*I == Dst) {
890 452458 : auto MapI = Probs.find(std::make_pair(Src, I.getSuccessorIndex()));
891 226229 : if (MapI != Probs.end()) {
892 : FoundProb = true;
893 : Prob += MapI->second;
894 : }
895 : }
896 221921 : uint32_t succ_num = std::distance(succ_begin(Src), succ_end(Src));
897 221921 : return FoundProb ? Prob : BranchProbability(1, succ_num);
898 : }
899 :
900 : /// Set the edge probability for a given edge specified by PredBlock and an
901 : /// index to the successors.
902 1220587 : void BranchProbabilityInfo::setEdgeProbability(const BasicBlock *Src,
903 : unsigned IndexInSuccessors,
904 : BranchProbability Prob) {
905 1220587 : Probs[std::make_pair(Src, IndexInSuccessors)] = Prob;
906 1220587 : Handles.insert(BasicBlockCallbackVH(Src, this));
907 : LLVM_DEBUG(dbgs() << "set edge " << Src->getName() << " -> "
908 : << IndexInSuccessors << " successor probability to " << Prob
909 : << "\n");
910 1220587 : }
911 :
912 : raw_ostream &
913 917 : BranchProbabilityInfo::printEdgeProbability(raw_ostream &OS,
914 : const BasicBlock *Src,
915 : const BasicBlock *Dst) const {
916 917 : const BranchProbability Prob = getEdgeProbability(Src, Dst);
917 917 : OS << "edge " << Src->getName() << " -> " << Dst->getName()
918 917 : << " probability is " << Prob
919 1343 : << (isEdgeHot(Src, Dst) ? " [HOT edge]\n" : "\n");
920 :
921 917 : return OS;
922 : }
923 :
924 18862 : void BranchProbabilityInfo::eraseBlock(const BasicBlock *BB) {
925 60044 : for (auto I = Probs.begin(), E = Probs.end(); I != E; ++I) {
926 22320 : auto Key = I->first;
927 22320 : if (Key.first == BB)
928 5732 : Probs.erase(Key);
929 : }
930 18862 : }
931 :
932 697895 : void BranchProbabilityInfo::calculate(const Function &F, const LoopInfo &LI,
933 : const TargetLibraryInfo *TLI) {
934 : LLVM_DEBUG(dbgs() << "---- Branch Probability Info : " << F.getName()
935 : << " ----\n\n");
936 697895 : LastF = &F; // Store the last function we ran on for printing.
937 : assert(PostDominatedByUnreachable.empty());
938 : assert(PostDominatedByColdCall.empty());
939 :
940 : // Record SCC numbers of blocks in the CFG to identify irreducible loops.
941 : // FIXME: We could only calculate this if the CFG is known to be irreducible
942 : // (perhaps cache this info in LoopInfo if we can easily calculate it there?).
943 : int SccNum = 0;
944 : SccInfo SccI;
945 2717304 : for (scc_iterator<const Function *> It = scc_begin(&F); !It.isAtEnd();
946 : ++It, ++SccNum) {
947 : // Ignore single-block SCCs since they either aren't loops or LoopInfo will
948 : // catch them.
949 : const std::vector<const BasicBlock *> &Scc = *It;
950 2019409 : if (Scc.size() == 1)
951 : continue;
952 :
953 : LLVM_DEBUG(dbgs() << "BPI: SCC " << SccNum << ":");
954 245258 : for (auto *BB : Scc) {
955 : LLVM_DEBUG(dbgs() << " " << BB->getName());
956 226061 : SccI.SccNums[BB] = SccNum;
957 : }
958 : LLVM_DEBUG(dbgs() << "\n");
959 : }
960 :
961 : // Walk the basic blocks in post-order so that we can build up state about
962 : // the successors of a block iteratively.
963 3622063 : for (auto BB : post_order(&F.getEntryBlock())) {
964 : LLVM_DEBUG(dbgs() << "Computing probabilities for " << BB->getName()
965 : << "\n");
966 2226273 : updatePostDominatedByUnreachable(BB);
967 2226273 : updatePostDominatedByColdCall(BB);
968 : // If there is no at least two successors, no sense to set probability.
969 2226272 : if (BB->getTerminator()->getNumSuccessors() < 2)
970 : continue;
971 755782 : if (calcMetadataWeights(BB))
972 : continue;
973 732942 : if (calcInvokeHeuristics(BB))
974 : continue;
975 415223 : if (calcUnreachableHeuristics(BB))
976 : continue;
977 386713 : if (calcColdCallHeuristics(BB))
978 : continue;
979 386391 : if (calcLoopBranchHeuristics(BB, LI, SccI))
980 : continue;
981 333811 : if (calcPointerHeuristics(BB))
982 : continue;
983 205171 : if (calcZeroHeuristics(BB, TLI))
984 : continue;
985 150649 : if (calcFloatingPointHeuristics(BB))
986 : continue;
987 : }
988 :
989 697895 : PostDominatedByUnreachable.clear();
990 697895 : PostDominatedByColdCall.clear();
991 :
992 697895 : if (PrintBranchProb &&
993 : (PrintBranchProbFuncName.empty() ||
994 697895 : F.getName().equals(PrintBranchProbFuncName))) {
995 0 : print(dbgs());
996 : }
997 697894 : }
998 :
999 51871 : void BranchProbabilityInfoWrapperPass::getAnalysisUsage(
1000 : AnalysisUsage &AU) const {
1001 : // We require DT so it's available when LI is available. The LI updating code
1002 : // asserts that DT is also present so if we don't make sure that we have DT
1003 : // here, that assert will trigger.
1004 : AU.addRequired<DominatorTreeWrapperPass>();
1005 : AU.addRequired<LoopInfoWrapperPass>();
1006 : AU.addRequired<TargetLibraryInfoWrapperPass>();
1007 : AU.setPreservesAll();
1008 51871 : }
1009 :
1010 497682 : bool BranchProbabilityInfoWrapperPass::runOnFunction(Function &F) {
1011 497682 : const LoopInfo &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
1012 497682 : const TargetLibraryInfo &TLI = getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
1013 497682 : BPI.calculate(F, LI, &TLI);
1014 497681 : return false;
1015 : }
1016 :
1017 497604 : void BranchProbabilityInfoWrapperPass::releaseMemory() { BPI.releaseMemory(); }
1018 :
1019 80 : void BranchProbabilityInfoWrapperPass::print(raw_ostream &OS,
1020 : const Module *) const {
1021 80 : BPI.print(OS);
1022 80 : }
1023 :
1024 : AnalysisKey BranchProbabilityAnalysis::Key;
1025 : BranchProbabilityInfo
1026 1089 : BranchProbabilityAnalysis::run(Function &F, FunctionAnalysisManager &AM) {
1027 1089 : BranchProbabilityInfo BPI;
1028 1089 : BPI.calculate(F, AM.getResult<LoopAnalysis>(F), &AM.getResult<TargetLibraryAnalysis>(F));
1029 1089 : return BPI;
1030 : }
1031 :
1032 : PreservedAnalyses
1033 52 : BranchProbabilityPrinterPass::run(Function &F, FunctionAnalysisManager &AM) {
1034 52 : OS << "Printing analysis results of BPI for function "
1035 52 : << "'" << F.getName() << "':"
1036 52 : << "\n";
1037 52 : AM.getResult<BranchProbabilityAnalysis>(F).print(OS);
1038 52 : return PreservedAnalyses::all();
1039 : }
|
