MachineBranchProbabilityInfo.cpp revision 234353
1224133Sdim//===- MachineBranchProbabilityInfo.cpp - Machine Branch Probability Info -===// 2224133Sdim// 3224133Sdim// The LLVM Compiler Infrastructure 4224133Sdim// 5224133Sdim// This file is distributed under the University of Illinois Open Source 6224133Sdim// License. See LICENSE.TXT for details. 7224133Sdim// 8224133Sdim//===----------------------------------------------------------------------===// 9224133Sdim// 10224133Sdim// This analysis uses probability info stored in Machine Basic Blocks. 11224133Sdim// 12224133Sdim//===----------------------------------------------------------------------===// 13224133Sdim 14224133Sdim#include "llvm/Instructions.h" 15224133Sdim#include "llvm/CodeGen/MachineBranchProbabilityInfo.h" 16224133Sdim#include "llvm/CodeGen/MachineBasicBlock.h" 17224133Sdim#include "llvm/Support/Debug.h" 18224133Sdim#include "llvm/Support/raw_ostream.h" 19224133Sdim 20224133Sdimusing namespace llvm; 21224133Sdim 22224133SdimINITIALIZE_PASS_BEGIN(MachineBranchProbabilityInfo, "machine-branch-prob", 23224133Sdim "Machine Branch Probability Analysis", false, true) 24224133SdimINITIALIZE_PASS_END(MachineBranchProbabilityInfo, "machine-branch-prob", 25224133Sdim "Machine Branch Probability Analysis", false, true) 26224133Sdim 27224133Sdimchar MachineBranchProbabilityInfo::ID = 0; 28224133Sdim 29234353Sdimvoid MachineBranchProbabilityInfo::anchor() { } 30234353Sdim 31224133Sdimuint32_t MachineBranchProbabilityInfo:: 32234353SdimgetSumForBlock(const MachineBasicBlock *MBB, uint32_t &Scale) const { 33234353Sdim // First we compute the sum with 64-bits of precision, ensuring that cannot 34234353Sdim // overflow by bounding the number of weights considered. Hopefully no one 35234353Sdim // actually needs 2^32 successors. 36234353Sdim assert(MBB->succ_size() < UINT32_MAX); 37234353Sdim uint64_t Sum = 0; 38234353Sdim Scale = 1; 39224133Sdim for (MachineBasicBlock::const_succ_iterator I = MBB->succ_begin(), 40224133Sdim E = MBB->succ_end(); I != E; ++I) { 41234353Sdim uint32_t Weight = getEdgeWeight(MBB, *I); 42224133Sdim Sum += Weight; 43224133Sdim } 44224133Sdim 45234353Sdim // If the computed sum fits in 32-bits, we're done. 46234353Sdim if (Sum <= UINT32_MAX) 47234353Sdim return Sum; 48234353Sdim 49234353Sdim // Otherwise, compute the scale necessary to cause the weights to fit, and 50234353Sdim // re-sum with that scale applied. 51234353Sdim assert((Sum / UINT32_MAX) < UINT32_MAX); 52234353Sdim Scale = (Sum / UINT32_MAX) + 1; 53234353Sdim Sum = 0; 54234353Sdim for (MachineBasicBlock::const_succ_iterator I = MBB->succ_begin(), 55234353Sdim E = MBB->succ_end(); I != E; ++I) { 56234353Sdim uint32_t Weight = getEdgeWeight(MBB, *I); 57234353Sdim Sum += Weight / Scale; 58234353Sdim } 59234353Sdim assert(Sum <= UINT32_MAX); 60224133Sdim return Sum; 61224133Sdim} 62224133Sdim 63224133Sdimuint32_t 64234353SdimMachineBranchProbabilityInfo::getEdgeWeight(const MachineBasicBlock *Src, 65234353Sdim const MachineBasicBlock *Dst) const { 66224133Sdim uint32_t Weight = Src->getSuccWeight(Dst); 67224133Sdim if (!Weight) 68224133Sdim return DEFAULT_WEIGHT; 69224133Sdim return Weight; 70224133Sdim} 71224133Sdim 72224133Sdimbool MachineBranchProbabilityInfo::isEdgeHot(MachineBasicBlock *Src, 73224133Sdim MachineBasicBlock *Dst) const { 74224133Sdim // Hot probability is at least 4/5 = 80% 75234353Sdim // FIXME: Compare against a static "hot" BranchProbability. 76234353Sdim return getEdgeProbability(Src, Dst) > BranchProbability(4, 5); 77224133Sdim} 78224133Sdim 79224133SdimMachineBasicBlock * 80224133SdimMachineBranchProbabilityInfo::getHotSucc(MachineBasicBlock *MBB) const { 81224133Sdim uint32_t MaxWeight = 0; 82224133Sdim MachineBasicBlock *MaxSucc = 0; 83224133Sdim for (MachineBasicBlock::const_succ_iterator I = MBB->succ_begin(), 84224133Sdim E = MBB->succ_end(); I != E; ++I) { 85234353Sdim uint32_t Weight = getEdgeWeight(MBB, *I); 86224133Sdim if (Weight > MaxWeight) { 87224133Sdim MaxWeight = Weight; 88234353Sdim MaxSucc = *I; 89224133Sdim } 90224133Sdim } 91224133Sdim 92234353Sdim if (getEdgeProbability(MBB, MaxSucc) >= BranchProbability(4, 5)) 93224133Sdim return MaxSucc; 94224133Sdim 95224133Sdim return 0; 96224133Sdim} 97224133Sdim 98224133SdimBranchProbability 99224133SdimMachineBranchProbabilityInfo::getEdgeProbability(MachineBasicBlock *Src, 100224133Sdim MachineBasicBlock *Dst) const { 101234353Sdim uint32_t Scale = 1; 102234353Sdim uint32_t D = getSumForBlock(Src, Scale); 103234353Sdim uint32_t N = getEdgeWeight(Src, Dst) / Scale; 104224133Sdim 105224133Sdim return BranchProbability(N, D); 106224133Sdim} 107224133Sdim 108224133Sdimraw_ostream &MachineBranchProbabilityInfo:: 109224133SdimprintEdgeProbability(raw_ostream &OS, MachineBasicBlock *Src, 110224133Sdim MachineBasicBlock *Dst) const { 111224133Sdim 112224133Sdim const BranchProbability Prob = getEdgeProbability(Src, Dst); 113224133Sdim OS << "edge MBB#" << Src->getNumber() << " -> MBB#" << Dst->getNumber() 114224133Sdim << " probability is " << Prob 115224133Sdim << (isEdgeHot(Src, Dst) ? " [HOT edge]\n" : "\n"); 116224133Sdim 117224133Sdim return OS; 118224133Sdim} 119