1 //===- MachineBranchProbabilityInfo.cpp - Machine Branch Probability Info -===// 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 // This analysis uses probability info stored in Machine Basic Blocks. 11 // 12 //===----------------------------------------------------------------------===// 13 14 #include "llvm/CodeGen/MachineBranchProbabilityInfo.h" 15 #include "llvm/CodeGen/MachineBasicBlock.h" 16 #include "llvm/IR/Instructions.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 char MachineBranchProbabilityInfo::ID = 0; 28 29 void MachineBranchProbabilityInfo::anchor() { } 30 31 uint32_t MachineBranchProbabilityInfo::getEdgeWeight( 32 const MachineBasicBlock *Src, 33 MachineBasicBlock::const_succ_iterator Dst) const { 34 return Src->getSuccProbability(Dst).getNumerator(); 35 } 36 37 uint32_t MachineBranchProbabilityInfo::getEdgeWeight( 38 const MachineBasicBlock *Src, const MachineBasicBlock *Dst) const { 39 // This is a linear search. Try to use the const_succ_iterator version when 40 // possible. 41 return getEdgeWeight(Src, std::find(Src->succ_begin(), Src->succ_end(), Dst)); 42 } 43 44 BranchProbability MachineBranchProbabilityInfo::getEdgeProbability( 45 const MachineBasicBlock *Src, 46 MachineBasicBlock::const_succ_iterator Dst) const { 47 return Src->getSuccProbability(Dst); 48 } 49 50 BranchProbability MachineBranchProbabilityInfo::getEdgeProbability( 51 const MachineBasicBlock *Src, const MachineBasicBlock *Dst) const { 52 // This is a linear search. Try to use the const_succ_iterator version when 53 // possible. 54 return getEdgeProbability(Src, 55 std::find(Src->succ_begin(), Src->succ_end(), Dst)); 56 } 57 58 bool 59 MachineBranchProbabilityInfo::isEdgeHot(const MachineBasicBlock *Src, 60 const MachineBasicBlock *Dst) const { 61 // Hot probability is at least 4/5 = 80% 62 static BranchProbability HotProb(4, 5); 63 return getEdgeProbability(Src, Dst) > HotProb; 64 } 65 66 MachineBasicBlock * 67 MachineBranchProbabilityInfo::getHotSucc(MachineBasicBlock *MBB) const { 68 auto MaxProb = BranchProbability::getZero(); 69 MachineBasicBlock *MaxSucc = nullptr; 70 for (MachineBasicBlock::const_succ_iterator I = MBB->succ_begin(), 71 E = MBB->succ_end(); I != E; ++I) { 72 auto Prob = getEdgeProbability(MBB, I); 73 if (Prob > MaxProb) { 74 MaxProb = Prob; 75 MaxSucc = *I; 76 } 77 } 78 79 static BranchProbability HotProb(4, 5); 80 if (getEdgeProbability(MBB, MaxSucc) >= HotProb) 81 return MaxSucc; 82 83 return nullptr; 84 } 85 86 raw_ostream &MachineBranchProbabilityInfo::printEdgeProbability( 87 raw_ostream &OS, const MachineBasicBlock *Src, 88 const MachineBasicBlock *Dst) const { 89 90 const BranchProbability Prob = getEdgeProbability(Src, Dst); 91 OS << "edge MBB#" << Src->getNumber() << " -> MBB#" << Dst->getNumber() 92 << " probability is " << Prob 93 << (isEdgeHot(Src, Dst) ? " [HOT edge]\n" : "\n"); 94 95 return OS; 96 } 97