contrib/llvm/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,
  54                             std::find(Src->succ_begin(), Src->succ_end(), Dst));
  55 }
  56
  57 bool MachineBranchProbabilityInfo::isEdgeHot(
  58     const MachineBasicBlock *Src, const MachineBasicBlock *Dst) const {
  59   BranchProbability HotProb(StaticLikelyProb, 100);
  60   return getEdgeProbability(Src, Dst) > HotProb;
  61 }
  62
  63 MachineBasicBlock *
  64 MachineBranchProbabilityInfo::getHotSucc(MachineBasicBlock *MBB) const {
  65   auto MaxProb = BranchProbability::getZero();
  66   MachineBasicBlock *MaxSucc = nullptr;
  67   for (MachineBasicBlock::const_succ_iterator I = MBB->succ_begin(),
  68        E = MBB->succ_end(); I != E; ++I) {
  69     auto Prob = getEdgeProbability(MBB, I);
  70     if (Prob > MaxProb) {
  71       MaxProb = Prob;
  72       MaxSucc = *I;
  73     }
  74   }
  75
  76   BranchProbability HotProb(StaticLikelyProb, 100);
  77   if (getEdgeProbability(MBB, MaxSucc) >= HotProb)
  78     return MaxSucc;
  79
  80   return nullptr;
  81 }
  82
  83 raw_ostream &MachineBranchProbabilityInfo::printEdgeProbability(
  84     raw_ostream &OS, const MachineBasicBlock *Src,
  85     const MachineBasicBlock *Dst) const {
  86
  87   const BranchProbability Prob = getEdgeProbability(Src, Dst);
  88   OS << "edge MBB#" << Src->getNumber() << " -> MBB#" << Dst->getNumber()
  89      << " probability is " << Prob
  90      << (isEdgeHot(Src, Dst) ? " [HOT edge]\n" : "\n");
  91
  92   return OS;
  93 }