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 BranchProbability MachineBranchProbabilityInfo::getEdgeProbability(
  32     const MachineBasicBlock *Src,
  33     MachineBasicBlock::const_succ_iterator Dst) const {
  34   return Src->getSuccProbability(Dst);
  35 }
  36
  37 BranchProbability MachineBranchProbabilityInfo::getEdgeProbability(
  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 getEdgeProbability(Src,
  42                             std::find(Src->succ_begin(), Src->succ_end(), Dst));
  43 }
  44
  45 bool
  46 MachineBranchProbabilityInfo::isEdgeHot(const MachineBasicBlock *Src,
  47                                         const MachineBasicBlock *Dst) const {
  48   // Hot probability is at least 4/5 = 80%
  49   static BranchProbability HotProb(4, 5);
  50   return getEdgeProbability(Src, Dst) > HotProb;
  51 }
  52
  53 MachineBasicBlock *
  54 MachineBranchProbabilityInfo::getHotSucc(MachineBasicBlock *MBB) const {
  55   auto MaxProb = BranchProbability::getZero();
  56   MachineBasicBlock *MaxSucc = nullptr;
  57   for (MachineBasicBlock::const_succ_iterator I = MBB->succ_begin(),
  58        E = MBB->succ_end(); I != E; ++I) {
  59     auto Prob = getEdgeProbability(MBB, I);
  60     if (Prob > MaxProb) {
  61       MaxProb = Prob;
  62       MaxSucc = *I;
  63     }
  64   }
  65
  66   static BranchProbability HotProb(4, 5);
  67   if (getEdgeProbability(MBB, MaxSucc) >= HotProb)
  68     return MaxSucc;
  69
  70   return nullptr;
  71 }
  72
  73 raw_ostream &MachineBranchProbabilityInfo::printEdgeProbability(
  74     raw_ostream &OS, const MachineBasicBlock *Src,
  75     const MachineBasicBlock *Dst) const {
  76
  77   const BranchProbability Prob = getEdgeProbability(Src, Dst);
  78   OS << "edge MBB#" << Src->getNumber() << " -> MBB#" << Dst->getNumber()
  79      << " probability is " << Prob
  80      << (isEdgeHot(Src, Dst) ? " [HOT edge]\n" : "\n");
  81
  82   return OS;
  83 }