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 MachineBranchProbabilityInfo::getEdgeWeight(
  32     const MachineBasicBlock *Src,
  33     MachineBasicBlock::const_succ_iterator Dst) const {
  34   return Src->getSuccProbability(Dst).getNumerator();
  35 }
  36
  37 uint32_t MachineBranchProbabilityInfo::getEdgeWeight(
  38     const MachineBasicBlock *Src, const MachineBasicBlock *Dst) const {
  39   // This is a linear search. Try to use the const_succ_iterator version when
  40   // possible.
  41   return getEdgeWeight(Src, std::find(Src->succ_begin(), Src->succ_end(), Dst));
  42 }
  43
  44 BranchProbability MachineBranchProbabilityInfo::getEdgeProbability(
  45     const MachineBasicBlock *Src,
  46     MachineBasicBlock::const_succ_iterator Dst) const {
  47   return Src->getSuccProbability(Dst);
  48 }
  49
  50 BranchProbability MachineBranchProbabilityInfo::getEdgeProbability(
  51     const MachineBasicBlock *Src, const MachineBasicBlock *Dst) const {
  52   // This is a linear search. Try to use the const_succ_iterator version when
  53   // possible.
  54   return getEdgeProbability(Src,
  55                             std::find(Src->succ_begin(), Src->succ_end(), Dst));
  56 }
  57
  58 bool
  59 MachineBranchProbabilityInfo::isEdgeHot(const MachineBasicBlock *Src,
  60                                         const MachineBasicBlock *Dst) const {
  61   // Hot probability is at least 4/5 = 80%
  62   static BranchProbability HotProb(4, 5);
  63   return getEdgeProbability(Src, Dst) > HotProb;
  64 }
  65
  66 MachineBasicBlock *
  67 MachineBranchProbabilityInfo::getHotSucc(MachineBasicBlock *MBB) const {
  68   auto MaxProb = BranchProbability::getZero();
  69   MachineBasicBlock *MaxSucc = nullptr;
  70   for (MachineBasicBlock::const_succ_iterator I = MBB->succ_begin(),
  71        E = MBB->succ_end(); I != E; ++I) {
  72     auto Prob = getEdgeProbability(MBB, I);
  73     if (Prob > MaxProb) {
  74       MaxProb = Prob;
  75       MaxSucc = *I;
  76     }
  77   }
  78
  79   static BranchProbability HotProb(4, 5);
  80   if (getEdgeProbability(MBB, MaxSucc) >= HotProb)
  81     return MaxSucc;
  82
  83   return nullptr;
  84 }
  85
  86 raw_ostream &MachineBranchProbabilityInfo::printEdgeProbability(
  87     raw_ostream &OS, const MachineBasicBlock *Src,
  88     const MachineBasicBlock *Dst) const {
  89
  90   const BranchProbability Prob = getEdgeProbability(Src, Dst);
  91   OS << "edge MBB#" << Src->getNumber() << " -> MBB#" << Dst->getNumber()
  92      << " probability is " << Prob
  93      << (isEdgeHot(Src, Dst) ? " [HOT edge]\n" : "\n");
  94
  95   return OS;
  96 }