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 void MachineBranchProbabilityInfo::anchor() { } 30 31 uint32_t MachineBranchProbabilityInfo:: 32 getSumForBlock(const MachineBasicBlock *MBB, uint32_t &Scale) const { 33 // First we compute the sum with 64-bits of precision, ensuring that cannot 34 // overflow by bounding the number of weights considered. Hopefully no one 35 // actually needs 2^32 successors. 36 assert(MBB->succ_size() < UINT32_MAX); 37 uint64_t Sum = 0; 38 Scale = 1; 39 for (MachineBasicBlock::const_succ_iterator I = MBB->succ_begin(), 40 E = MBB->succ_end(); I != E; ++I) { 41 uint32_t Weight = getEdgeWeight(MBB, *I); 42 Sum += Weight; 43 } 44 45 // If the computed sum fits in 32-bits, we're done. 46 if (Sum <= UINT32_MAX) 47 return Sum; 48 49 // Otherwise, compute the scale necessary to cause the weights to fit, and 50 // re-sum with that scale applied. 51 assert((Sum / UINT32_MAX) < UINT32_MAX); 52 Scale = (Sum / UINT32_MAX) + 1; 53 Sum = 0; 54 for (MachineBasicBlock::const_succ_iterator I = MBB->succ_begin(), 55 E = MBB->succ_end(); I != E; ++I) { 56 uint32_t Weight = getEdgeWeight(MBB, *I); 57 Sum += Weight / Scale; 58 } 59 assert(Sum <= UINT32_MAX); 60 return Sum; 61 } 62 63 uint32_t 64 MachineBranchProbabilityInfo::getEdgeWeight(const MachineBasicBlock *Src, 65 const MachineBasicBlock *Dst) const { 66 uint32_t Weight = Src->getSuccWeight(Dst); 67 if (!Weight) 68 return DEFAULT_WEIGHT; 69 return Weight; 70 } 71 72 bool MachineBranchProbabilityInfo::isEdgeHot(MachineBasicBlock *Src, 73 MachineBasicBlock *Dst) const { 74 // Hot probability is at least 4/5 = 80% 75 // FIXME: Compare against a static "hot" BranchProbability. 76 return getEdgeProbability(Src, Dst) > BranchProbability(4, 5); 77 } 78 79 MachineBasicBlock * 80 MachineBranchProbabilityInfo::getHotSucc(MachineBasicBlock *MBB) const { 81 uint32_t MaxWeight = 0; 82 MachineBasicBlock *MaxSucc = 0; 83 for (MachineBasicBlock::const_succ_iterator I = MBB->succ_begin(), 84 E = MBB->succ_end(); I != E; ++I) { 85 uint32_t Weight = getEdgeWeight(MBB, *I); 86 if (Weight > MaxWeight) { 87 MaxWeight = Weight; 88 MaxSucc = *I; 89 } 90 } 91 92 if (getEdgeProbability(MBB, MaxSucc) >= BranchProbability(4, 5)) 93 return MaxSucc; 94 95 return 0; 96 } 97 98 BranchProbability 99 MachineBranchProbabilityInfo::getEdgeProbability(MachineBasicBlock *Src, 100 MachineBasicBlock *Dst) const { 101 uint32_t Scale = 1; 102 uint32_t D = getSumForBlock(Src, Scale); 103 uint32_t N = getEdgeWeight(Src, Dst) / Scale; 104 105 return BranchProbability(N, D); 106 } 107 108 raw_ostream &MachineBranchProbabilityInfo:: 109 printEdgeProbability(raw_ostream &OS, MachineBasicBlock *Src, 110 MachineBasicBlock *Dst) const { 111 112 const BranchProbability Prob = getEdgeProbability(Src, Dst); 113 OS << "edge MBB#" << Src->getNumber() << " -> MBB#" << Dst->getNumber() 114 << " probability is " << Prob 115 << (isEdgeHot(Src, Dst) ? " [HOT edge]\n" : "\n"); 116 117 return OS; 118 } 119
