MachineBranchProbabilityInfo.cpp revision 249423
198184Sgordon//===- MachineBranchProbabilityInfo.cpp - Machine Branch Probability Info -===// 298184Sgordon// 398184Sgordon// The LLVM Compiler Infrastructure 498184Sgordon// 598184Sgordon// This file is distributed under the University of Illinois Open Source 698184Sgordon// License. See LICENSE.TXT for details. 7195026Sdougb// 8250804Sjamie//===----------------------------------------------------------------------===// 998184Sgordon// 1098184Sgordon// This analysis uses probability info stored in Machine Basic Blocks. 11118099Smbr// 1298184Sgordon//===----------------------------------------------------------------------===// 1398184Sgordon 1498184Sgordon#include "llvm/CodeGen/MachineBranchProbabilityInfo.h" 1598184Sgordon#include "llvm/CodeGen/MachineBasicBlock.h" 16175722Smtm#include "llvm/IR/Instructions.h" 17203676Semax#include "llvm/Support/Debug.h" 18112849Smtm#include "llvm/Support/raw_ostream.h" 19165683Syar 2098184Sgordonusing namespace llvm; 21200028Sume 22200028SumeINITIALIZE_PASS_BEGIN(MachineBranchProbabilityInfo, "machine-branch-prob", 23175722Smtm "Machine Branch Probability Analysis", false, true) 24175722SmtmINITIALIZE_PASS_END(MachineBranchProbabilityInfo, "machine-branch-prob", 25175722Smtm "Machine Branch Probability Analysis", false, true) 26175722Smtm 27175722Smtmchar MachineBranchProbabilityInfo::ID = 0; 28242301Shrs 29242301Shrsvoid MachineBranchProbabilityInfo::anchor() { } 30242301Shrs 31190575Semaxuint32_t MachineBranchProbabilityInfo:: 32242301ShrsgetSumForBlock(const MachineBasicBlock *MBB, uint32_t &Scale) const { 33208060Sdougb // First we compute the sum with 64-bits of precision, ensuring that cannot 34175722Smtm // overflow by bounding the number of weights considered. Hopefully no one 35175722Smtm // actually needs 2^32 successors. 3698184Sgordon assert(MBB->succ_size() < UINT32_MAX); 3798184Sgordon uint64_t Sum = 0; 38190575Semax Scale = 1; 39190575Semax for (MachineBasicBlock::const_succ_iterator I = MBB->succ_begin(), 40208060Sdougb E = MBB->succ_end(); I != E; ++I) { 41190575Semax uint32_t Weight = getEdgeWeight(MBB, I); 4298184Sgordon Sum += Weight; 4398184Sgordon } 4498184Sgordon 4598184Sgordon // If the computed sum fits in 32-bits, we're done. 46190575Semax if (Sum <= UINT32_MAX) 47160672Syar return Sum; 48156030Swkoszek 4998184Sgordon // Otherwise, compute the scale necessary to cause the weights to fit, and 5098184Sgordon // re-sum with that scale applied. 5198184Sgordon assert((Sum / UINT32_MAX) < UINT32_MAX); 5298184Sgordon Scale = (Sum / UINT32_MAX) + 1; 5398184Sgordon Sum = 0; 5498184Sgordon for (MachineBasicBlock::const_succ_iterator I = MBB->succ_begin(), 5598184Sgordon E = MBB->succ_end(); I != E; ++I) { 56112849Smtm uint32_t Weight = getEdgeWeight(MBB, I); 57160672Syar Sum += Weight / Scale; 58112849Smtm } 59112849Smtm assert(Sum <= UINT32_MAX); 60238277Shrs return Sum; 61238277Shrs} 62238277Shrs 63238277Shrsuint32_t MachineBranchProbabilityInfo:: 64203676SemaxgetEdgeWeight(const MachineBasicBlock *Src, 6598184Sgordon MachineBasicBlock::const_succ_iterator Dst) const { 66203676Semax uint32_t Weight = Src->getSuccWeight(Dst); 67203676Semax if (!Weight) 68203676Semax return DEFAULT_WEIGHT; 69203676Semax return Weight; 70203676Semax} 71203676Semax 72203676Semaxuint32_t MachineBranchProbabilityInfo:: 73203676SemaxgetEdgeWeight(const MachineBasicBlock *Src, 74203676Semax const MachineBasicBlock *Dst) const { 75203676Semax // This is a linear search. Try to use the const_succ_iterator version when 76203676Semax // possible. 77203676Semax return getEdgeWeight(Src, std::find(Src->succ_begin(), Src->succ_end(), Dst)); 78112849Smtm} 79112849Smtm 80220153Semastebool MachineBranchProbabilityInfo::isEdgeHot(MachineBasicBlock *Src, 81200028Sume MachineBasicBlock *Dst) const { 82180296Smtm // Hot probability is at least 4/5 = 80% 83200028Sume // FIXME: Compare against a static "hot" BranchProbability. 84220153Semaste return getEdgeProbability(Src, Dst) > BranchProbability(4, 5); 85200028Sume} 86200028Sume 87200028SumeMachineBasicBlock * 88200028SumeMachineBranchProbabilityInfo::getHotSucc(MachineBasicBlock *MBB) const { 8998184Sgordon uint32_t MaxWeight = 0; 9098184Sgordon MachineBasicBlock *MaxSucc = 0; 91112849Smtm for (MachineBasicBlock::const_succ_iterator I = MBB->succ_begin(), 92112849Smtm E = MBB->succ_end(); I != E; ++I) { 93203676Semax uint32_t Weight = getEdgeWeight(MBB, I); 94203676Semax if (Weight > MaxWeight) { 95112849Smtm MaxWeight = Weight; 96112849Smtm MaxSucc = *I; 97220153Semaste } 98200028Sume } 99220153Semaste 100200028Sume if (getEdgeProbability(MBB, MaxSucc) >= BranchProbability(4, 5)) 101203676Semax return MaxSucc; 102203676Semax 103203676Semax return 0; 104203676Semax} 105203676Semax 106203676SemaxBranchProbability 107203676SemaxMachineBranchProbabilityInfo::getEdgeProbability(MachineBasicBlock *Src, 108203676Semax MachineBasicBlock *Dst) const { 109112849Smtm uint32_t Scale = 1; 110112849Smtm uint32_t D = getSumForBlock(Src, Scale); 11198184Sgordon uint32_t N = getEdgeWeight(Src, Dst) / Scale; 112203676Semax 113203676Semax return BranchProbability(N, D); 114190575Semax} 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