MachineBranchProbabilityInfo.cpp revision 243830
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 20using namespace llvm; 21 22INITIALIZE_PASS_BEGIN(MachineBranchProbabilityInfo, "machine-branch-prob", 23 "Machine Branch Probability Analysis", false, true) 24INITIALIZE_PASS_END(MachineBranchProbabilityInfo, "machine-branch-prob", 25 "Machine Branch Probability Analysis", false, true) 26 27char MachineBranchProbabilityInfo::ID = 0; 28 29void MachineBranchProbabilityInfo::anchor() { } 30 31uint32_t MachineBranchProbabilityInfo:: 32getSumForBlock(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 63uint32_t MachineBranchProbabilityInfo:: 64getEdgeWeight(const MachineBasicBlock *Src, 65 MachineBasicBlock::const_succ_iterator Dst) const { 66 uint32_t Weight = Src->getSuccWeight(Dst); 67 if (!Weight) 68 return DEFAULT_WEIGHT; 69 return Weight; 70} 71 72uint32_t MachineBranchProbabilityInfo:: 73getEdgeWeight(const MachineBasicBlock *Src, 74 const MachineBasicBlock *Dst) const { 75 // This is a linear search. Try to use the const_succ_iterator version when 76 // possible. 77 return getEdgeWeight(Src, std::find(Src->succ_begin(), Src->succ_end(), Dst)); 78} 79 80bool MachineBranchProbabilityInfo::isEdgeHot(MachineBasicBlock *Src, 81 MachineBasicBlock *Dst) const { 82 // Hot probability is at least 4/5 = 80% 83 // FIXME: Compare against a static "hot" BranchProbability. 84 return getEdgeProbability(Src, Dst) > BranchProbability(4, 5); 85} 86 87MachineBasicBlock * 88MachineBranchProbabilityInfo::getHotSucc(MachineBasicBlock *MBB) const { 89 uint32_t MaxWeight = 0; 90 MachineBasicBlock *MaxSucc = 0; 91 for (MachineBasicBlock::const_succ_iterator I = MBB->succ_begin(), 92 E = MBB->succ_end(); I != E; ++I) { 93 uint32_t Weight = getEdgeWeight(MBB, I); 94 if (Weight > MaxWeight) { 95 MaxWeight = Weight; 96 MaxSucc = *I; 97 } 98 } 99 100 if (getEdgeProbability(MBB, MaxSucc) >= BranchProbability(4, 5)) 101 return MaxSucc; 102 103 return 0; 104} 105 106BranchProbability 107MachineBranchProbabilityInfo::getEdgeProbability(MachineBasicBlock *Src, 108 MachineBasicBlock *Dst) const { 109 uint32_t Scale = 1; 110 uint32_t D = getSumForBlock(Src, Scale); 111 uint32_t N = getEdgeWeight(Src, Dst) / Scale; 112 113 return BranchProbability(N, D); 114} 115 116raw_ostream &MachineBranchProbabilityInfo:: 117printEdgeProbability(raw_ostream &OS, MachineBasicBlock *Src, 118 MachineBasicBlock *Dst) const { 119 120 const BranchProbability Prob = getEdgeProbability(Src, Dst); 121 OS << "edge MBB#" << Src->getNumber() << " -> MBB#" << Dst->getNumber() 122 << " probability is " << Prob 123 << (isEdgeHot(Src, Dst) ? " [HOT edge]\n" : "\n"); 124 125 return OS; 126} 127