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 cl::opt<unsigned>
  28     StaticLikelyProb("static-likely-prob",
  29                      cl::desc("branch probability threshold in percentage"
  30                               "to be considered very likely"),
  31                      cl::init(80), cl::Hidden);
  32
  33 cl::opt<unsigned> ProfileLikelyProb(
  34     "profile-likely-prob",
  35     cl::desc("branch probability threshold in percentage to be considered"
  36              " very likely when profile is available"),
  37     cl::init(51), cl::Hidden);
  38
  39 char MachineBranchProbabilityInfo::ID = 0;
  40
  41 void MachineBranchProbabilityInfo::anchor() {}
  42
  43 BranchProbability MachineBranchProbabilityInfo::getEdgeProbability(
  44     const MachineBasicBlock *Src,
  45     MachineBasicBlock::const_succ_iterator Dst) const {
  46   return Src->getSuccProbability(Dst);
  47 }
  48
  49 BranchProbability MachineBranchProbabilityInfo::getEdgeProbability(
  50     const MachineBasicBlock *Src, const MachineBasicBlock *Dst) const {
  51   // This is a linear search. Try to use the const_succ_iterator version when
  52   // possible.
  53   return getEdgeProbability(Src, find(Src->successors(), Dst));
  54 }
  55
  56 bool MachineBranchProbabilityInfo::isEdgeHot(
  57     const MachineBasicBlock *Src, const MachineBasicBlock *Dst) const {
  58   BranchProbability HotProb(StaticLikelyProb, 100);
  59   return getEdgeProbability(Src, Dst) > HotProb;
  60 }
  61
  62 MachineBasicBlock *
  63 MachineBranchProbabilityInfo::getHotSucc(MachineBasicBlock *MBB) const {
  64   auto MaxProb = BranchProbability::getZero();
  65   MachineBasicBlock *MaxSucc = nullptr;
  66   for (MachineBasicBlock::const_succ_iterator I = MBB->succ_begin(),
  67        E = MBB->succ_end(); I != E; ++I) {
  68     auto Prob = getEdgeProbability(MBB, I);
  69     if (Prob > MaxProb) {
  70       MaxProb = Prob;
  71       MaxSucc = *I;
  72     }
  73   }
  74
  75   BranchProbability HotProb(StaticLikelyProb, 100);
  76   if (getEdgeProbability(MBB, MaxSucc) >= HotProb)
  77     return MaxSucc;
  78
  79   return nullptr;
  80 }
  81
  82 raw_ostream &MachineBranchProbabilityInfo::printEdgeProbability(
  83     raw_ostream &OS, const MachineBasicBlock *Src,
  84     const MachineBasicBlock *Dst) const {
  85
  86   const BranchProbability Prob = getEdgeProbability(Src, Dst);
  87   OS << "edge " << printMBBReference(*Src) << " -> " << printMBBReference(*Dst)
  88      << " probability is " << Prob
  89      << (isEdgeHot(Src, Dst) ? " [HOT edge]\n" : "\n");
  90
  91   return OS;
  92 }