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/CodeGen/MachineBranchProbabilityInfo.h" 15224133Sdim#include "llvm/CodeGen/MachineBasicBlock.h" 16249423Sdim#include "llvm/IR/Instructions.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) { 41243830Sdim 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) { 56243830Sdim uint32_t Weight = getEdgeWeight(MBB, I); 57234353Sdim Sum += Weight / Scale; 58234353Sdim } 59234353Sdim assert(Sum <= UINT32_MAX); 60224133Sdim return Sum; 61224133Sdim} 62224133Sdim 63243830Sdimuint32_t MachineBranchProbabilityInfo:: 64243830SdimgetEdgeWeight(const MachineBasicBlock *Src, 65243830Sdim MachineBasicBlock::const_succ_iterator Dst) const { 66224133Sdim uint32_t Weight = Src->getSuccWeight(Dst); 67224133Sdim if (!Weight) 68224133Sdim return DEFAULT_WEIGHT; 69224133Sdim return Weight; 70224133Sdim} 71224133Sdim 72243830Sdimuint32_t MachineBranchProbabilityInfo:: 73243830SdimgetEdgeWeight(const MachineBasicBlock *Src, 74243830Sdim const MachineBasicBlock *Dst) const { 75243830Sdim // This is a linear search. Try to use the const_succ_iterator version when 76243830Sdim // possible. 77243830Sdim return getEdgeWeight(Src, std::find(Src->succ_begin(), Src->succ_end(), Dst)); 78243830Sdim} 79243830Sdim 80224133Sdimbool MachineBranchProbabilityInfo::isEdgeHot(MachineBasicBlock *Src, 81224133Sdim MachineBasicBlock *Dst) const { 82224133Sdim // Hot probability is at least 4/5 = 80% 83234353Sdim // FIXME: Compare against a static "hot" BranchProbability. 84234353Sdim return getEdgeProbability(Src, Dst) > BranchProbability(4, 5); 85224133Sdim} 86224133Sdim 87224133SdimMachineBasicBlock * 88224133SdimMachineBranchProbabilityInfo::getHotSucc(MachineBasicBlock *MBB) const { 89224133Sdim uint32_t MaxWeight = 0; 90224133Sdim MachineBasicBlock *MaxSucc = 0; 91224133Sdim for (MachineBasicBlock::const_succ_iterator I = MBB->succ_begin(), 92224133Sdim E = MBB->succ_end(); I != E; ++I) { 93243830Sdim uint32_t Weight = getEdgeWeight(MBB, I); 94224133Sdim if (Weight > MaxWeight) { 95224133Sdim MaxWeight = Weight; 96234353Sdim MaxSucc = *I; 97224133Sdim } 98224133Sdim } 99224133Sdim 100234353Sdim if (getEdgeProbability(MBB, MaxSucc) >= BranchProbability(4, 5)) 101224133Sdim return MaxSucc; 102224133Sdim 103224133Sdim return 0; 104224133Sdim} 105224133Sdim 106224133SdimBranchProbability 107224133SdimMachineBranchProbabilityInfo::getEdgeProbability(MachineBasicBlock *Src, 108224133Sdim MachineBasicBlock *Dst) const { 109234353Sdim uint32_t Scale = 1; 110234353Sdim uint32_t D = getSumForBlock(Src, Scale); 111234353Sdim uint32_t N = getEdgeWeight(Src, Dst) / Scale; 112224133Sdim 113224133Sdim return BranchProbability(N, D); 114224133Sdim} 115224133Sdim 116224133Sdimraw_ostream &MachineBranchProbabilityInfo:: 117224133SdimprintEdgeProbability(raw_ostream &OS, MachineBasicBlock *Src, 118224133Sdim MachineBasicBlock *Dst) const { 119224133Sdim 120224133Sdim const BranchProbability Prob = getEdgeProbability(Src, Dst); 121224133Sdim OS << "edge MBB#" << Src->getNumber() << " -> MBB#" << Dst->getNumber() 122224133Sdim << " probability is " << Prob 123224133Sdim << (isEdgeHot(Src, Dst) ? " [HOT edge]\n" : "\n"); 124224133Sdim 125224133Sdim return OS; 126224133Sdim} 127