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 }
126