0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
1 //===- BranchProbability.h - Branch Probability Wrapper ---------*- C++ -*-===//
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
2 //
|
|
147
|
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
|
|
|
4 // See https://llvm.org/LICENSE.txt for license information.
|
|
|
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
6 //
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
7 //===----------------------------------------------------------------------===//
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
8 //
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
9 // Definition of BranchProbability shared by IR and Machine Instructions.
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
10 //
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
11 //===----------------------------------------------------------------------===//
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
12
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
13 #ifndef LLVM_SUPPORT_BRANCHPROBABILITY_H
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
14 #define LLVM_SUPPORT_BRANCHPROBABILITY_H
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
15
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
16 #include "llvm/Support/DataTypes.h"
|
|
100
|
17 #include <algorithm>
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
18 #include <cassert>
|
|
100
|
19 #include <climits>
|
|
|
20 #include <numeric>
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
21
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
22 namespace llvm {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
23
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
24 class raw_ostream;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
25
|
|
95
|
26 // This class represents Branch Probability as a non-negative fraction that is
|
|
|
27 // no greater than 1. It uses a fixed-point-like implementation, in which the
|
|
|
28 // denominator is always a constant value (here we use 1<<31 for maximum
|
|
|
29 // precision).
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
30 class BranchProbability {
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
31 // Numerator
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
32 uint32_t N;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
33
|
|
95
|
34 // Denominator, which is a constant value.
|
|
|
35 static const uint32_t D = 1u << 31;
|
|
100
|
36 static const uint32_t UnknownN = UINT32_MAX;
|
|
95
|
37
|
|
|
38 // Construct a BranchProbability with only numerator assuming the denominator
|
|
|
39 // is 1<<31. For internal use only.
|
|
|
40 explicit BranchProbability(uint32_t n) : N(n) {}
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
41
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
42 public:
|
|
100
|
43 BranchProbability() : N(UnknownN) {}
|
|
95
|
44 BranchProbability(uint32_t Numerator, uint32_t Denominator);
|
|
|
45
|
|
|
46 bool isZero() const { return N == 0; }
|
|
100
|
47 bool isUnknown() const { return N == UnknownN; }
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
48
|
|
95
|
49 static BranchProbability getZero() { return BranchProbability(0); }
|
|
|
50 static BranchProbability getOne() { return BranchProbability(D); }
|
|
100
|
51 static BranchProbability getUnknown() { return BranchProbability(UnknownN); }
|
|
95
|
52 // Create a BranchProbability object with the given numerator and 1<<31
|
|
|
53 // as denominator.
|
|
|
54 static BranchProbability getRaw(uint32_t N) { return BranchProbability(N); }
|
|
100
|
55 // Create a BranchProbability object from 64-bit integers.
|
|
|
56 static BranchProbability getBranchProbability(uint64_t Numerator,
|
|
|
57 uint64_t Denominator);
|
|
95
|
58
|
|
|
59 // Normalize given probabilties so that the sum of them becomes approximate
|
|
|
60 // one.
|
|
100
|
61 template <class ProbabilityIter>
|
|
|
62 static void normalizeProbabilities(ProbabilityIter Begin,
|
|
|
63 ProbabilityIter End);
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
64
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
65 uint32_t getNumerator() const { return N; }
|
|
95
|
66 static uint32_t getDenominator() { return D; }
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
67
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
68 // Return (1 - Probability).
|
|
95
|
69 BranchProbability getCompl() const { return BranchProbability(D - N); }
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
70
|
|
77
|
71 raw_ostream &print(raw_ostream &OS) const;
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
72
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
73 void dump() const;
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
74
|
|
147
|
75 /// Scale a large integer.
|
|
77
|
76 ///
|
|
|
77 /// Scales \c Num. Guarantees full precision. Returns the floor of the
|
|
|
78 /// result.
|
|
|
79 ///
|
|
|
80 /// \return \c Num times \c this.
|
|
|
81 uint64_t scale(uint64_t Num) const;
|
|
|
82
|
|
147
|
83 /// Scale a large integer by the inverse.
|
|
77
|
84 ///
|
|
|
85 /// Scales \c Num by the inverse of \c this. Guarantees full precision.
|
|
|
86 /// Returns the floor of the result.
|
|
|
87 ///
|
|
|
88 /// \return \c Num divided by \c this.
|
|
|
89 uint64_t scaleByInverse(uint64_t Num) const;
|
|
|
90
|
|
95
|
91 BranchProbability &operator+=(BranchProbability RHS) {
|
|
100
|
92 assert(N != UnknownN && RHS.N != UnknownN &&
|
|
|
93 "Unknown probability cannot participate in arithmetics.");
|
|
|
94 // Saturate the result in case of overflow.
|
|
|
95 N = (uint64_t(N) + RHS.N > D) ? D : N + RHS.N;
|
|
95
|
96 return *this;
|
|
|
97 }
|
|
|
98
|
|
|
99 BranchProbability &operator-=(BranchProbability RHS) {
|
|
100
|
100 assert(N != UnknownN && RHS.N != UnknownN &&
|
|
|
101 "Unknown probability cannot participate in arithmetics.");
|
|
|
102 // Saturate the result in case of underflow.
|
|
|
103 N = N < RHS.N ? 0 : N - RHS.N;
|
|
95
|
104 return *this;
|
|
|
105 }
|
|
|
106
|
|
|
107 BranchProbability &operator*=(BranchProbability RHS) {
|
|
100
|
108 assert(N != UnknownN && RHS.N != UnknownN &&
|
|
|
109 "Unknown probability cannot participate in arithmetics.");
|
|
95
|
110 N = (static_cast<uint64_t>(N) * RHS.N + D / 2) / D;
|
|
|
111 return *this;
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
112 }
|
|
95
|
113
|
|
121
|
114 BranchProbability &operator*=(uint32_t RHS) {
|
|
|
115 assert(N != UnknownN &&
|
|
|
116 "Unknown probability cannot participate in arithmetics.");
|
|
|
117 N = (uint64_t(N) * RHS > D) ? D : N * RHS;
|
|
|
118 return *this;
|
|
|
119 }
|
|
|
120
|
|
147
|
121 BranchProbability &operator/=(BranchProbability RHS) {
|
|
|
122 assert(N != UnknownN && RHS.N != UnknownN &&
|
|
|
123 "Unknown probability cannot participate in arithmetics.");
|
|
|
124 N = (static_cast<uint64_t>(N) * D + RHS.N / 2) / RHS.N;
|
|
|
125 return *this;
|
|
|
126 }
|
|
|
127
|
|
100
|
128 BranchProbability &operator/=(uint32_t RHS) {
|
|
|
129 assert(N != UnknownN &&
|
|
|
130 "Unknown probability cannot participate in arithmetics.");
|
|
|
131 assert(RHS > 0 && "The divider cannot be zero.");
|
|
|
132 N /= RHS;
|
|
|
133 return *this;
|
|
|
134 }
|
|
|
135
|
|
95
|
136 BranchProbability operator+(BranchProbability RHS) const {
|
|
|
137 BranchProbability Prob(*this);
|
|
147
|
138 Prob += RHS;
|
|
|
139 return Prob;
|
|
95
|
140 }
|
|
|
141
|
|
|
142 BranchProbability operator-(BranchProbability RHS) const {
|
|
|
143 BranchProbability Prob(*this);
|
|
147
|
144 Prob -= RHS;
|
|
|
145 return Prob;
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
146 }
|
|
95
|
147
|
|
|
148 BranchProbability operator*(BranchProbability RHS) const {
|
|
|
149 BranchProbability Prob(*this);
|
|
147
|
150 Prob *= RHS;
|
|
|
151 return Prob;
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
152 }
|
|
95
|
153
|
|
121
|
154 BranchProbability operator*(uint32_t RHS) const {
|
|
|
155 BranchProbability Prob(*this);
|
|
147
|
156 Prob *= RHS;
|
|
|
157 return Prob;
|
|
|
158 }
|
|
|
159
|
|
|
160 BranchProbability operator/(BranchProbability RHS) const {
|
|
|
161 BranchProbability Prob(*this);
|
|
|
162 Prob /= RHS;
|
|
|
163 return Prob;
|
|
121
|
164 }
|
|
|
165
|
|
100
|
166 BranchProbability operator/(uint32_t RHS) const {
|
|
|
167 BranchProbability Prob(*this);
|
|
147
|
168 Prob /= RHS;
|
|
|
169 return Prob;
|
|
100
|
170 }
|
|
|
171
|
|
95
|
172 bool operator==(BranchProbability RHS) const { return N == RHS.N; }
|
|
|
173 bool operator!=(BranchProbability RHS) const { return !(*this == RHS); }
|
|
100
|
174
|
|
|
175 bool operator<(BranchProbability RHS) const {
|
|
|
176 assert(N != UnknownN && RHS.N != UnknownN &&
|
|
|
177 "Unknown probability cannot participate in comparisons.");
|
|
|
178 return N < RHS.N;
|
|
|
179 }
|
|
|
180
|
|
|
181 bool operator>(BranchProbability RHS) const {
|
|
|
182 assert(N != UnknownN && RHS.N != UnknownN &&
|
|
|
183 "Unknown probability cannot participate in comparisons.");
|
|
|
184 return RHS < *this;
|
|
|
185 }
|
|
|
186
|
|
|
187 bool operator<=(BranchProbability RHS) const {
|
|
|
188 assert(N != UnknownN && RHS.N != UnknownN &&
|
|
|
189 "Unknown probability cannot participate in comparisons.");
|
|
|
190 return !(RHS < *this);
|
|
|
191 }
|
|
|
192
|
|
|
193 bool operator>=(BranchProbability RHS) const {
|
|
|
194 assert(N != UnknownN && RHS.N != UnknownN &&
|
|
|
195 "Unknown probability cannot participate in comparisons.");
|
|
|
196 return !(*this < RHS);
|
|
|
197 }
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
198 };
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
199
|
|
95
|
200 inline raw_ostream &operator<<(raw_ostream &OS, BranchProbability Prob) {
|
|
77
|
201 return Prob.print(OS);
|
|
|
202 }
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
203
|
|
100
|
204 template <class ProbabilityIter>
|
|
|
205 void BranchProbability::normalizeProbabilities(ProbabilityIter Begin,
|
|
|
206 ProbabilityIter End) {
|
|
|
207 if (Begin == End)
|
|
|
208 return;
|
|
|
209
|
|
|
210 unsigned UnknownProbCount = 0;
|
|
|
211 uint64_t Sum = std::accumulate(Begin, End, uint64_t(0),
|
|
|
212 [&](uint64_t S, const BranchProbability &BP) {
|
|
|
213 if (!BP.isUnknown())
|
|
|
214 return S + BP.N;
|
|
|
215 UnknownProbCount++;
|
|
|
216 return S;
|
|
|
217 });
|
|
|
218
|
|
|
219 if (UnknownProbCount > 0) {
|
|
|
220 BranchProbability ProbForUnknown = BranchProbability::getZero();
|
|
|
221 // If the sum of all known probabilities is less than one, evenly distribute
|
|
|
222 // the complement of sum to unknown probabilities. Otherwise, set unknown
|
|
|
223 // probabilities to zeros and continue to normalize known probabilities.
|
|
|
224 if (Sum < BranchProbability::getDenominator())
|
|
|
225 ProbForUnknown = BranchProbability::getRaw(
|
|
|
226 (BranchProbability::getDenominator() - Sum) / UnknownProbCount);
|
|
|
227
|
|
|
228 std::replace_if(Begin, End,
|
|
|
229 [](const BranchProbability &BP) { return BP.isUnknown(); },
|
|
|
230 ProbForUnknown);
|
|
|
231
|
|
|
232 if (Sum <= BranchProbability::getDenominator())
|
|
|
233 return;
|
|
|
234 }
|
|
120
|
235
|
|
100
|
236 if (Sum == 0) {
|
|
|
237 BranchProbability BP(1, std::distance(Begin, End));
|
|
|
238 std::fill(Begin, End, BP);
|
|
|
239 return;
|
|
|
240 }
|
|
|
241
|
|
|
242 for (auto I = Begin; I != End; ++I)
|
|
|
243 I->N = (I->N * uint64_t(D) + Sum / 2) / Sum;
|
|
95
|
244 }
|
|
|
245
|
0
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
246 }
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
247
|
Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
parents:
diff
changeset
|
248 #endif
|
