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 anchor()29 void MachineBranchProbabilityInfo::anchor() { } 30 getEdgeProbability(const MachineBasicBlock * Src,MachineBasicBlock::const_succ_iterator Dst) const31 BranchProbability MachineBranchProbabilityInfo::getEdgeProbability( 32 const MachineBasicBlock *Src, 33 MachineBasicBlock::const_succ_iterator Dst) const { 34 return Src->getSuccProbability(Dst); 35 } 36 getEdgeProbability(const MachineBasicBlock * Src,const MachineBasicBlock * Dst) const37 BranchProbability MachineBranchProbabilityInfo::getEdgeProbability( 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 getEdgeProbability(Src, 42 std::find(Src->succ_begin(), Src->succ_end(), Dst)); 43 } 44 45 bool isEdgeHot(const MachineBasicBlock * Src,const MachineBasicBlock * Dst) const46 MachineBranchProbabilityInfo::isEdgeHot(const MachineBasicBlock *Src, 47 const MachineBasicBlock *Dst) const { 48 // Hot probability is at least 4/5 = 80% 49 static BranchProbability HotProb(4, 5); 50 return getEdgeProbability(Src, Dst) > HotProb; 51 } 52 53 MachineBasicBlock * getHotSucc(MachineBasicBlock * MBB) const54 MachineBranchProbabilityInfo::getHotSucc(MachineBasicBlock *MBB) const { 55 auto MaxProb = BranchProbability::getZero(); 56 MachineBasicBlock *MaxSucc = nullptr; 57 for (MachineBasicBlock::const_succ_iterator I = MBB->succ_begin(), 58 E = MBB->succ_end(); I != E; ++I) { 59 auto Prob = getEdgeProbability(MBB, I); 60 if (Prob > MaxProb) { 61 MaxProb = Prob; 62 MaxSucc = *I; 63 } 64 } 65 66 static BranchProbability HotProb(4, 5); 67 if (getEdgeProbability(MBB, MaxSucc) >= HotProb) 68 return MaxSucc; 69 70 return nullptr; 71 } 72 printEdgeProbability(raw_ostream & OS,const MachineBasicBlock * Src,const MachineBasicBlock * Dst) const73 raw_ostream &MachineBranchProbabilityInfo::printEdgeProbability( 74 raw_ostream &OS, const MachineBasicBlock *Src, 75 const MachineBasicBlock *Dst) const { 76 77 const BranchProbability Prob = getEdgeProbability(Src, Dst); 78 OS << "edge MBB#" << Src->getNumber() << " -> MBB#" << Dst->getNumber() 79 << " probability is " << Prob 80 << (isEdgeHot(Src, Dst) ? " [HOT edge]\n" : "\n"); 81 82 return OS; 83 } 84