MachineBranchProbabilityInfo.cpp revision 224145
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 29uint32_t MachineBranchProbabilityInfo:: 30getSumForBlock(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 46uint32_t 47MachineBranchProbabilityInfo::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 55bool 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 66MachineBasicBlock * 67MachineBranchProbabilityInfo::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 94BranchProbability 95MachineBranchProbabilityInfo::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 103raw_ostream &MachineBranchProbabilityInfo:: 104printEdgeProbability(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