1 //===- MachineBranchProbabilityInfo.cpp - Machine Branch Probability Info -===// 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 // This analysis uses probability info stored in Machine Basic Blocks. 10 // 11 //===----------------------------------------------------------------------===// 12 13 #include "llvm/CodeGen/MachineBranchProbabilityInfo.h" 14 #include "llvm/CodeGen/MachineBasicBlock.h" 15 #include "llvm/IR/Instructions.h" 16 #include "llvm/InitializePasses.h" 17 #include "llvm/Support/Debug.h" 18 #include "llvm/Support/raw_ostream.h" 19 20 using namespace llvm; 21 22 INITIALIZE_PASS_BEGIN(MachineBranchProbabilityInfo, "machine-branch-prob", 23 "Machine Branch Probability Analysis", false, true) 24 INITIALIZE_PASS_END(MachineBranchProbabilityInfo, "machine-branch-prob", 25 "Machine Branch Probability Analysis", false, true) 26 27 cl::opt<unsigned> 28 StaticLikelyProb("static-likely-prob", 29 cl::desc("branch probability threshold in percentage" 30 "to be considered very likely"), 31 cl::init(80), cl::Hidden); 32 33 cl::opt<unsigned> ProfileLikelyProb( 34 "profile-likely-prob", 35 cl::desc("branch probability threshold in percentage to be considered" 36 " very likely when profile is available"), 37 cl::init(51), cl::Hidden); 38 39 char MachineBranchProbabilityInfo::ID = 0; 40 41 MachineBranchProbabilityInfo::MachineBranchProbabilityInfo() 42 : ImmutablePass(ID) { 43 PassRegistry &Registry = *PassRegistry::getPassRegistry(); 44 initializeMachineBranchProbabilityInfoPass(Registry); 45 } 46 47 void MachineBranchProbabilityInfo::anchor() {} 48 49 BranchProbability MachineBranchProbabilityInfo::getEdgeProbability( 50 const MachineBasicBlock *Src, 51 MachineBasicBlock::const_succ_iterator Dst) const { 52 return Src->getSuccProbability(Dst); 53 } 54 55 BranchProbability MachineBranchProbabilityInfo::getEdgeProbability( 56 const MachineBasicBlock *Src, const MachineBasicBlock *Dst) const { 57 // This is a linear search. Try to use the const_succ_iterator version when 58 // possible. 59 return getEdgeProbability(Src, find(Src->successors(), Dst)); 60 } 61 62 bool MachineBranchProbabilityInfo::isEdgeHot( 63 const MachineBasicBlock *Src, const MachineBasicBlock *Dst) const { 64 BranchProbability HotProb(StaticLikelyProb, 100); 65 return getEdgeProbability(Src, Dst) > HotProb; 66 } 67 68 MachineBasicBlock * 69 MachineBranchProbabilityInfo::getHotSucc(MachineBasicBlock *MBB) const { 70 auto MaxProb = BranchProbability::getZero(); 71 MachineBasicBlock *MaxSucc = nullptr; 72 for (MachineBasicBlock::const_succ_iterator I = MBB->succ_begin(), 73 E = MBB->succ_end(); I != E; ++I) { 74 auto Prob = getEdgeProbability(MBB, I); 75 if (Prob > MaxProb) { 76 MaxProb = Prob; 77 MaxSucc = *I; 78 } 79 } 80 81 BranchProbability HotProb(StaticLikelyProb, 100); 82 if (getEdgeProbability(MBB, MaxSucc) >= HotProb) 83 return MaxSucc; 84 85 return nullptr; 86 } 87 88 raw_ostream &MachineBranchProbabilityInfo::printEdgeProbability( 89 raw_ostream &OS, const MachineBasicBlock *Src, 90 const MachineBasicBlock *Dst) const { 91 92 const BranchProbability Prob = getEdgeProbability(Src, Dst); 93 OS << "edge " << printMBBReference(*Src) << " -> " << printMBBReference(*Dst) 94 << " probability is " << Prob 95 << (isEdgeHot(Src, Dst) ? " [HOT edge]\n" : "\n"); 96 97 return OS; 98 } 99