Mercurial > hg > CbC > CbC_llvm

annotate lib/CodeGen/MachineBranchProbabilityInfo.cpp @ 134:3a76565eade5 LLVM5.0.1

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
update 5.0.1
author mir3636
date Sat, 17 Feb 2018 09:57:20 +0900
parents 1172e4bd9c6f
children c2174574ed3a
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
0
95c75e76d11b LLVM 3.4
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
1 //===- MachineBranchProbabilityInfo.cpp - Machine Branch Probability Info -===//
95c75e76d11b LLVM 3.4
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
2 //
95c75e76d11b LLVM 3.4
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
3 // The LLVM Compiler Infrastructure
95c75e76d11b LLVM 3.4
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
4 //
95c75e76d11b LLVM 3.4
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
5 // This file is distributed under the University of Illinois Open Source
95c75e76d11b LLVM 3.4
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
6 // License. See LICENSE.TXT for details.
95c75e76d11b LLVM 3.4
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
7 //
95c75e76d11b LLVM 3.4
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
8 //===----------------------------------------------------------------------===//
95c75e76d11b LLVM 3.4
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
9 //
95c75e76d11b LLVM 3.4
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
10 // This analysis uses probability info stored in Machine Basic Blocks.
95c75e76d11b LLVM 3.4
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
11 //
95c75e76d11b LLVM 3.4
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
12 //===----------------------------------------------------------------------===//
95c75e76d11b LLVM 3.4
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
13
95c75e76d11b LLVM 3.4
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
14 #include "llvm/CodeGen/MachineBranchProbabilityInfo.h"
95c75e76d11b LLVM 3.4
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
15 #include "llvm/CodeGen/MachineBasicBlock.h"
95c75e76d11b LLVM 3.4
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
16 #include "llvm/IR/Instructions.h"
95c75e76d11b LLVM 3.4
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
17 #include "llvm/Support/Debug.h"
95c75e76d11b LLVM 3.4
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
18 #include "llvm/Support/raw_ostream.h"
95c75e76d11b LLVM 3.4
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
19
95c75e76d11b LLVM 3.4
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
20 using namespace llvm;
95c75e76d11b LLVM 3.4
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
21
95c75e76d11b LLVM 3.4
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
22 INITIALIZE_PASS_BEGIN(MachineBranchProbabilityInfo, "machine-branch-prob",
95c75e76d11b LLVM 3.4
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
23 "Machine Branch Probability Analysis", false, true)
95c75e76d11b LLVM 3.4
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
24 INITIALIZE_PASS_END(MachineBranchProbabilityInfo, "machine-branch-prob",
95c75e76d11b LLVM 3.4
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
25 "Machine Branch Probability Analysis", false, true)
95c75e76d11b LLVM 3.4
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
26
120
1172e4bd9c6f update 4.0.0
mir3636
parents: 100
diff changeset
27 cl::opt<unsigned>
1172e4bd9c6f update 4.0.0
mir3636
parents: 100
diff changeset
28 StaticLikelyProb("static-likely-prob",
1172e4bd9c6f update 4.0.0
mir3636
parents: 100
diff changeset
29 cl::desc("branch probability threshold in percentage"
1172e4bd9c6f update 4.0.0
mir3636
parents: 100
diff changeset
30 "to be considered very likely"),
1172e4bd9c6f update 4.0.0
mir3636
parents: 100
diff changeset
31 cl::init(80), cl::Hidden);
1172e4bd9c6f update 4.0.0
mir3636
parents: 100
diff changeset
32
1172e4bd9c6f update 4.0.0
mir3636
parents: 100
diff changeset
33 cl::opt<unsigned> ProfileLikelyProb(
1172e4bd9c6f update 4.0.0
mir3636
parents: 100
diff changeset
34 "profile-likely-prob",
1172e4bd9c6f update 4.0.0
mir3636
parents: 100
diff changeset
35 cl::desc("branch probability threshold in percentage to be considered"
1172e4bd9c6f update 4.0.0
mir3636
parents: 100
diff changeset
36 " very likely when profile is available"),
1172e4bd9c6f update 4.0.0
mir3636
parents: 100
diff changeset
37 cl::init(51), cl::Hidden);
1172e4bd9c6f update 4.0.0
mir3636
parents: 100
diff changeset
38
0
95c75e76d11b LLVM 3.4
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
39 char MachineBranchProbabilityInfo::ID = 0;
95c75e76d11b LLVM 3.4
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
40
120
1172e4bd9c6f update 4.0.0
mir3636
parents: 100
diff changeset
41 void MachineBranchProbabilityInfo::anchor() {}
0
95c75e76d11b LLVM 3.4
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
42
100
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents: 77
diff changeset
43 BranchProbability MachineBranchProbabilityInfo::getEdgeProbability(
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents: 77
diff changeset
44 const MachineBasicBlock *Src,
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents: 77
diff changeset
45 MachineBasicBlock::const_succ_iterator Dst) const {
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents: 77
diff changeset
46 return Src->getSuccProbability(Dst);
0
95c75e76d11b LLVM 3.4
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
47 }
95c75e76d11b LLVM 3.4
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
48
100
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents: 77
diff changeset
49 BranchProbability MachineBranchProbabilityInfo::getEdgeProbability(
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents: 77
diff changeset
50 const MachineBasicBlock *Src, const MachineBasicBlock *Dst) const {
0
95c75e76d11b LLVM 3.4
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
51 // This is a linear search. Try to use the const_succ_iterator version when
95c75e76d11b LLVM 3.4
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
52 // possible.
120
1172e4bd9c6f update 4.0.0
mir3636
parents: 100
diff changeset
53 return getEdgeProbability(Src, find(Src->successors(), Dst));
0
95c75e76d11b LLVM 3.4
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
54 }
95c75e76d11b LLVM 3.4
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
55
120
1172e4bd9c6f update 4.0.0
mir3636
parents: 100
diff changeset
56 bool MachineBranchProbabilityInfo::isEdgeHot(
1172e4bd9c6f update 4.0.0
mir3636
parents: 100
diff changeset
57 const MachineBasicBlock *Src, const MachineBasicBlock *Dst) const {
1172e4bd9c6f update 4.0.0
mir3636
parents: 100
diff changeset
58 BranchProbability HotProb(StaticLikelyProb, 100);
100
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents: 77
diff changeset
59 return getEdgeProbability(Src, Dst) > HotProb;
0
95c75e76d11b LLVM 3.4
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
60 }
95c75e76d11b LLVM 3.4
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
61
95c75e76d11b LLVM 3.4
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
62 MachineBasicBlock *
95c75e76d11b LLVM 3.4
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
63 MachineBranchProbabilityInfo::getHotSucc(MachineBasicBlock *MBB) const {
100
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents: 77
diff changeset
64 auto MaxProb = BranchProbability::getZero();
77
54457678186b LLVM 3.6
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
65 MachineBasicBlock *MaxSucc = nullptr;
0
95c75e76d11b LLVM 3.4
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
66 for (MachineBasicBlock::const_succ_iterator I = MBB->succ_begin(),
95c75e76d11b LLVM 3.4
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
67 E = MBB->succ_end(); I != E; ++I) {
100
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents: 77
diff changeset
68 auto Prob = getEdgeProbability(MBB, I);
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents: 77
diff changeset
69 if (Prob > MaxProb) {
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents: 77
diff changeset
70 MaxProb = Prob;
0
95c75e76d11b LLVM 3.4
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
71 MaxSucc = *I;
95c75e76d11b LLVM 3.4
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
72 }
95c75e76d11b LLVM 3.4
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
73 }
95c75e76d11b LLVM 3.4
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
74
120
1172e4bd9c6f update 4.0.0
mir3636
parents: 100
diff changeset
75 BranchProbability HotProb(StaticLikelyProb, 100);
100
7d135dc70f03 LLVM 3.9
Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
parents: 77
diff changeset
76 if (getEdgeProbability(MBB, MaxSucc) >= HotProb)
0
95c75e76d11b LLVM 3.4
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
77 return MaxSucc;
95c75e76d11b LLVM 3.4
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
78
77
54457678186b LLVM 3.6
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
79 return nullptr;
0
95c75e76d11b LLVM 3.4
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
80 }
95c75e76d11b LLVM 3.4
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
81
77
54457678186b LLVM 3.6
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
82 raw_ostream &MachineBranchProbabilityInfo::printEdgeProbability(
54457678186b LLVM 3.6
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
83 raw_ostream &OS, const MachineBasicBlock *Src,
54457678186b LLVM 3.6
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
84 const MachineBasicBlock *Dst) const {
0
95c75e76d11b LLVM 3.4
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
85
95c75e76d11b LLVM 3.4
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
86 const BranchProbability Prob = getEdgeProbability(Src, Dst);
134
3a76565eade5 update 5.0.1
mir3636
parents: 120
diff changeset
87 OS << "edge " << printMBBReference(*Src) << " -> " << printMBBReference(*Dst)
77
54457678186b LLVM 3.6
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents: 0
diff changeset
88 << " probability is " << Prob
0
95c75e76d11b LLVM 3.4
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
89 << (isEdgeHot(Src, Dst) ? " [HOT edge]\n" : "\n");
95c75e76d11b LLVM 3.4
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
90
95c75e76d11b LLVM 3.4
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
91 return OS;
95c75e76d11b LLVM 3.4
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff changeset
92 }