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/Instructions.h" 15 #include "llvm/CodeGen/MachineBranchProbabilityInfo.h" 16 #include "llvm/CodeGen/MachineBasicBlock.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 uint32_t MachineBranchProbabilityInfo:: 30 getSumForBlock(MachineBasicBlock *MBB) const { 31 uint32_t Sum = 0; 32 33 for (MachineBasicBlock::const_succ_iterator I = MBB->succ_begin(), 34 E = MBB->succ_end(); I != E; ++I) { 35 MachineBasicBlock *Succ = *I; 36 uint32_t Weight = getEdgeWeight(MBB, Succ); 37 uint32_t PrevSum = Sum; 38 39 Sum += Weight; 40 assert(Sum > PrevSum); (void) PrevSum; 41 } 42 43 return Sum; 44 } 45 46 uint32_t 47 MachineBranchProbabilityInfo::getEdgeWeight(MachineBasicBlock *Src, 48 MachineBasicBlock *Dst) const { 49 uint32_t Weight = Src->getSuccWeight(Dst); 50 if (!Weight) 51 return DEFAULT_WEIGHT; 52 return Weight; 53 } 54 55 bool MachineBranchProbabilityInfo::isEdgeHot(MachineBasicBlock *Src, 56 MachineBasicBlock *Dst) const { 57 // Hot probability is at least 4/5 = 80% 58 uint32_t Weight = getEdgeWeight(Src, Dst); 59 uint32_t Sum = getSumForBlock(Src); 60 61 // FIXME: Implement BranchProbability::compare then change this code to 62 // compare this BranchProbability against a static "hot" BranchProbability. 63 return (uint64_t)Weight * 5 > (uint64_t)Sum * 4; 64 } 65 66 MachineBasicBlock * 67 MachineBranchProbabilityInfo::getHotSucc(MachineBasicBlock *MBB) const { 68 uint32_t Sum = 0; 69 uint32_t MaxWeight = 0; 70 MachineBasicBlock *MaxSucc = 0; 71 72 for (MachineBasicBlock::const_succ_iterator I = MBB->succ_begin(), 73 E = MBB->succ_end(); I != E; ++I) { 74 MachineBasicBlock *Succ = *I; 75 uint32_t Weight = getEdgeWeight(MBB, Succ); 76 uint32_t PrevSum = Sum; 77 78 Sum += Weight; 79 assert(Sum > PrevSum); (void) PrevSum; 80 81 if (Weight > MaxWeight) { 82 MaxWeight = Weight; 83 MaxSucc = Succ; 84 } 85 } 86 87 // FIXME: Use BranchProbability::compare. 88 if ((uint64_t)MaxWeight * 5 >= (uint64_t)Sum * 4) 89 return MaxSucc; 90 91 return 0; 92 } 93 94 BranchProbability 95 MachineBranchProbabilityInfo::getEdgeProbability(MachineBasicBlock *Src, 96 MachineBasicBlock *Dst) const { 97 uint32_t N = getEdgeWeight(Src, Dst); 98 uint32_t D = getSumForBlock(Src); 99 100 return BranchProbability(N, D); 101 } 102 103 raw_ostream &MachineBranchProbabilityInfo:: 104 printEdgeProbability(raw_ostream &OS, MachineBasicBlock *Src, 105 MachineBasicBlock *Dst) const { 106 107 const BranchProbability Prob = getEdgeProbability(Src, Dst); 108 OS << "edge MBB#" << Src->getNumber() << " -> MBB#" << Dst->getNumber() 109 << " probability is " << Prob 110 << (isEdgeHot(Src, Dst) ? " [HOT edge]\n" : "\n"); 111 112 return OS; 113 } 114
