lib/CodeGen/MachineBranchProbabilityInfo.cpp

   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/CodeGen/MachineBranchProbabilityInfo.h"
  15 #include "llvm/CodeGen/MachineBasicBlock.h"
  16 #include "llvm/IR/Instructions.h"
  17 #include "llvm/Support/Debug.h"
  18 #include "llvm/Support/raw_ostream.h"
  19
  20 using namespace llvm;
  21
  22 INITIALIZE_PASS_BEGIN(MachineBranchProbabilityInfo, "machine-branch-prob",
  23                       "Machine Branch Probability Analysis", false, true)
  24 INITIALIZE_PASS_END(MachineBranchProbabilityInfo, "machine-branch-prob",
  25                     "Machine Branch Probability Analysis", false, true)
  26
  27 char MachineBranchProbabilityInfo::ID = 0;
  28
  29 void MachineBranchProbabilityInfo::anchor() { }
  30
  31 uint32_t
  32 MachineBranchProbabilityInfo::getSumForBlock(MachineBasicBlock *MBB) const {
  33   // Normalize the weights of MBB's all successors so that the sum is guaranteed
  34   // to be no greater than UINT32_MAX.
  35   MBB->normalizeSuccWeights();
  36
  37   SmallVector<uint32_t, 8> Weights;
  38   for (MachineBasicBlock::const_succ_iterator I = MBB->succ_begin(),
  39                                               E = MBB->succ_end();
  40        I != E; ++I)
  41     Weights.push_back(getEdgeWeight(MBB, I));
  42
  43   return std::accumulate(Weights.begin(), Weights.end(), 0u);
  44 }
  45
  46 uint32_t
  47 MachineBranchProbabilityInfo::getSumForBlock(const MachineBasicBlock *MBB,
  48                                              uint32_t &Scale) const {
  49   SmallVector<uint32_t, 8> Weights;
  50   for (MachineBasicBlock::const_succ_iterator I = MBB->succ_begin(),
  51                                               E = MBB->succ_end();
  52        I != E; ++I)
  53     Weights.push_back(getEdgeWeight(MBB, I));
  54
  55   if (MBB->areSuccWeightsNormalized())
  56     Scale = 1;
  57   else
  58     Scale = MachineBranchProbabilityInfo::normalizeEdgeWeights(Weights);
  59   return std::accumulate(Weights.begin(), Weights.end(), 0u);
  60 }
  61
  62 uint32_t MachineBranchProbabilityInfo::
  63 getEdgeWeight(const MachineBasicBlock *Src,
  64               MachineBasicBlock::const_succ_iterator Dst) const {
  65   uint32_t Weight = Src->getSuccWeight(Dst);
  66   if (!Weight)
  67     return DEFAULT_WEIGHT;
  68   return Weight;
  69 }
  70
  71 uint32_t MachineBranchProbabilityInfo::
  72 getEdgeWeight(const MachineBasicBlock *Src,
  73               const MachineBasicBlock *Dst) const {
  74   // This is a linear search. Try to use the const_succ_iterator version when
  75   // possible.
  76   return getEdgeWeight(Src, std::find(Src->succ_begin(), Src->succ_end(), Dst));
  77 }
  78
  79 bool
  80 MachineBranchProbabilityInfo::isEdgeHot(const MachineBasicBlock *Src,
  81                                         const 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
  87 MachineBasicBlock *
  88 MachineBranchProbabilityInfo::getHotSucc(MachineBasicBlock *MBB) const {
  89   uint32_t MaxWeight = 0;
  90   MachineBasicBlock *MaxSucc = nullptr;
  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 nullptr;
 104 }
 105
 106 BranchProbability MachineBranchProbabilityInfo::getEdgeProbability(
 107     const MachineBasicBlock *Src, const MachineBasicBlock *Dst) const {
 108   uint32_t Scale = 1;
 109   uint32_t D = getSumForBlock(Src, Scale);
 110   uint32_t N = getEdgeWeight(Src, Dst) / Scale;
 111
 112   return BranchProbability(N, D);
 113 }
 114
 115 raw_ostream &MachineBranchProbabilityInfo::printEdgeProbability(
 116     raw_ostream &OS, const MachineBasicBlock *Src,
 117     const MachineBasicBlock *Dst) const {
 118
 119   const BranchProbability Prob = getEdgeProbability(Src, Dst);
 120   OS << "edge MBB#" << Src->getNumber() << " -> MBB#" << Dst->getNumber()
 121      << " probability is " << Prob
 122      << (isEdgeHot(Src, Dst) ? " [HOT edge]\n" : "\n");
 123
 124   return OS;
 125 }