/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/include/llvm/Support/BranchProbability.h
Line | Count | Source |
1 | | //===- BranchProbability.h - Branch Probability Wrapper ---------*- C++ -*-===// |
2 | | // |
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 |
6 | | // |
7 | | //===----------------------------------------------------------------------===// |
8 | | // |
9 | | // Definition of BranchProbability shared by IR and Machine Instructions. |
10 | | // |
11 | | //===----------------------------------------------------------------------===// |
12 | | |
13 | | #ifndef LLVM_SUPPORT_BRANCHPROBABILITY_H |
14 | | #define LLVM_SUPPORT_BRANCHPROBABILITY_H |
15 | | |
16 | | #include "llvm/Support/DataTypes.h" |
17 | | #include <algorithm> |
18 | | #include <cassert> |
19 | | #include <climits> |
20 | | #include <numeric> |
21 | | |
22 | | namespace llvm { |
23 | | |
24 | | class raw_ostream; |
25 | | |
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). |
30 | | class BranchProbability { |
31 | | // Numerator |
32 | | uint32_t N; |
33 | | |
34 | | // Denominator, which is a constant value. |
35 | | static const uint32_t D = 1u << 31; |
36 | | static const uint32_t UnknownN = UINT32_MAX; |
37 | | |
38 | | // Construct a BranchProbability with only numerator assuming the denominator |
39 | | // is 1<<31. For internal use only. |
40 | 47.6M | explicit BranchProbability(uint32_t n) : N(n) {} |
41 | | |
42 | | public: |
43 | 14.5M | BranchProbability() : N(UnknownN) {} |
44 | | BranchProbability(uint32_t Numerator, uint32_t Denominator); |
45 | | |
46 | 18 | bool isZero() const { return N == 0; } |
47 | 49.5M | bool isUnknown() const { return N == UnknownN; } |
48 | | |
49 | 19.1M | static BranchProbability getZero() { return BranchProbability(0); } |
50 | 4.37M | static BranchProbability getOne() { return BranchProbability(D); } |
51 | 4.57M | static BranchProbability getUnknown() { return BranchProbability(UnknownN); } |
52 | | // Create a BranchProbability object with the given numerator and 1<<31 |
53 | | // as denominator. |
54 | 115k | static BranchProbability getRaw(uint32_t N) { return BranchProbability(N); } |
55 | | // Create a BranchProbability object from 64-bit integers. |
56 | | static BranchProbability getBranchProbability(uint64_t Numerator, |
57 | | uint64_t Denominator); |
58 | | |
59 | | // Normalize given probabilties so that the sum of them becomes approximate |
60 | | // one. |
61 | | template <class ProbabilityIter> |
62 | | static void normalizeProbabilities(ProbabilityIter Begin, |
63 | | ProbabilityIter End); |
64 | | |
65 | 40.8M | uint32_t getNumerator() const { return N; } |
66 | 59.7k | static uint32_t getDenominator() { return D; } |
67 | | |
68 | | // Return (1 - Probability). |
69 | 19.4M | BranchProbability getCompl() const { return BranchProbability(D - N); } |
70 | | |
71 | | raw_ostream &print(raw_ostream &OS) const; |
72 | | |
73 | | void dump() const; |
74 | | |
75 | | /// Scale a large integer. |
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 | | |
83 | | /// Scale a large integer by the inverse. |
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 | | |
91 | 1.21M | BranchProbability &operator+=(BranchProbability RHS) { |
92 | 1.21M | assert(N != UnknownN && RHS.N != UnknownN && |
93 | 1.21M | "Unknown probability cannot participate in arithmetics."); |
94 | 1.21M | // Saturate the result in case of overflow. |
95 | 1.21M | N = (uint64_t(N) + RHS.N > D) ? D17.7k : N + RHS.N1.19M ; |
96 | 1.21M | return *this; |
97 | 1.21M | } |
98 | | |
99 | 1.36M | BranchProbability &operator-=(BranchProbability RHS) { |
100 | 1.36M | assert(N != UnknownN && RHS.N != UnknownN && |
101 | 1.36M | "Unknown probability cannot participate in arithmetics."); |
102 | 1.36M | // Saturate the result in case of underflow. |
103 | 1.36M | N = N < RHS.N ? 018 : N - RHS.N1.36M ; |
104 | 1.36M | return *this; |
105 | 1.36M | } |
106 | | |
107 | 7.36k | BranchProbability &operator*=(BranchProbability RHS) { |
108 | 7.36k | assert(N != UnknownN && RHS.N != UnknownN && |
109 | 7.36k | "Unknown probability cannot participate in arithmetics."); |
110 | 7.36k | N = (static_cast<uint64_t>(N) * RHS.N + D / 2) / D; |
111 | 7.36k | return *this; |
112 | 7.36k | } |
113 | | |
114 | 80.9k | BranchProbability &operator*=(uint32_t RHS) { |
115 | 80.9k | assert(N != UnknownN && |
116 | 80.9k | "Unknown probability cannot participate in arithmetics."); |
117 | 80.9k | N = (uint64_t(N) * RHS > D) ? D6 : N * RHS80.9k ; |
118 | 80.9k | return *this; |
119 | 80.9k | } |
120 | | |
121 | 117 | BranchProbability &operator/=(BranchProbability RHS) { |
122 | 117 | assert(N != UnknownN && RHS.N != UnknownN && |
123 | 117 | "Unknown probability cannot participate in arithmetics."); |
124 | 117 | N = (static_cast<uint64_t>(N) * D + RHS.N / 2) / RHS.N; |
125 | 117 | return *this; |
126 | 117 | } |
127 | | |
128 | 18.0M | BranchProbability &operator/=(uint32_t RHS) { |
129 | 18.0M | assert(N != UnknownN && |
130 | 18.0M | "Unknown probability cannot participate in arithmetics."); |
131 | 18.0M | assert(RHS > 0 && "The divider cannot be zero."); |
132 | 18.0M | N /= RHS; |
133 | 18.0M | return *this; |
134 | 18.0M | } |
135 | | |
136 | 38.8k | BranchProbability operator+(BranchProbability RHS) const { |
137 | 38.8k | BranchProbability Prob(*this); |
138 | 38.8k | Prob += RHS; |
139 | 38.8k | return Prob; |
140 | 38.8k | } |
141 | | |
142 | 270k | BranchProbability operator-(BranchProbability RHS) const { |
143 | 270k | BranchProbability Prob(*this); |
144 | 270k | Prob -= RHS; |
145 | 270k | return Prob; |
146 | 270k | } |
147 | | |
148 | 7.31k | BranchProbability operator*(BranchProbability RHS) const { |
149 | 7.31k | BranchProbability Prob(*this); |
150 | 7.31k | Prob *= RHS; |
151 | 7.31k | return Prob; |
152 | 7.31k | } |
153 | | |
154 | 80.9k | BranchProbability operator*(uint32_t RHS) const { |
155 | 80.9k | BranchProbability Prob(*this); |
156 | 80.9k | Prob *= RHS; |
157 | 80.9k | return Prob; |
158 | 80.9k | } |
159 | | |
160 | 117 | BranchProbability operator/(BranchProbability RHS) const { |
161 | 117 | BranchProbability Prob(*this); |
162 | 117 | Prob /= RHS; |
163 | 117 | return Prob; |
164 | 117 | } |
165 | | |
166 | 18.0M | BranchProbability operator/(uint32_t RHS) const { |
167 | 18.0M | BranchProbability Prob(*this); |
168 | 18.0M | Prob /= RHS; |
169 | 18.0M | return Prob; |
170 | 18.0M | } |
171 | | |
172 | 33.4k | bool operator==(BranchProbability RHS) const { return N == RHS.N; } |
173 | 29.7k | bool operator!=(BranchProbability RHS) const { return !(*this == RHS); } |
174 | | |
175 | 2.15M | bool operator<(BranchProbability RHS) const { |
176 | 2.15M | assert(N != UnknownN && RHS.N != UnknownN && |
177 | 2.15M | "Unknown probability cannot participate in comparisons."); |
178 | 2.15M | return N < RHS.N; |
179 | 2.15M | } |
180 | | |
181 | 494k | bool operator>(BranchProbability RHS) const { |
182 | 494k | assert(N != UnknownN && RHS.N != UnknownN && |
183 | 494k | "Unknown probability cannot participate in comparisons."); |
184 | 494k | return RHS < *this; |
185 | 494k | } |
186 | | |
187 | 185k | bool operator<=(BranchProbability RHS) const { |
188 | 185k | assert(N != UnknownN && RHS.N != UnknownN && |
189 | 185k | "Unknown probability cannot participate in comparisons."); |
190 | 185k | return !(RHS < *this); |
191 | 185k | } |
192 | | |
193 | 470k | bool operator>=(BranchProbability RHS) const { |
194 | 470k | assert(N != UnknownN && RHS.N != UnknownN && |
195 | 470k | "Unknown probability cannot participate in comparisons."); |
196 | 470k | return !(*this < RHS); |
197 | 470k | } |
198 | | }; |
199 | | |
200 | 939 | inline raw_ostream &operator<<(raw_ostream &OS, BranchProbability Prob) { |
201 | 939 | return Prob.print(OS); |
202 | 939 | } |
203 | | |
204 | | template <class ProbabilityIter> |
205 | | void BranchProbability::normalizeProbabilities(ProbabilityIter Begin, |
206 | 699k | ProbabilityIter End) { |
207 | 699k | if (Begin == End) |
208 | 62.8k | return; |
209 | 636k | |
210 | 636k | unsigned UnknownProbCount = 0; |
211 | 636k | uint64_t Sum = std::accumulate(Begin, End, uint64_t(0), |
212 | 1.27M | [&](uint64_t S, const BranchProbability &BP) { |
213 | 1.27M | if (!BP.isUnknown()) |
214 | 1.26M | return S + BP.N; |
215 | 8.97k | UnknownProbCount++; |
216 | 8.97k | return S; |
217 | 8.97k | }); void llvm::BranchProbability::normalizeProbabilities<std::__1::__wrap_iter<llvm::BranchProbability*> >(std::__1::__wrap_iter<llvm::BranchProbability*>, std::__1::__wrap_iter<llvm::BranchProbability*>)::'lambda'(unsigned long long, llvm::BranchProbability const&)::operator()(unsigned long long, llvm::BranchProbability const&) const Line | Count | Source | 212 | 1.19M | [&](uint64_t S, const BranchProbability &BP) { | 213 | 1.19M | if (!BP.isUnknown()) | 214 | 1.19M | return S + BP.N; | 215 | 6.09k | UnknownProbCount++; | 216 | 6.09k | return S; | 217 | 6.09k | }); |
void llvm::BranchProbability::normalizeProbabilities<llvm::BranchProbability*>(llvm::BranchProbability*, llvm::BranchProbability*)::'lambda'(unsigned long long, llvm::BranchProbability const&)::operator()(unsigned long long, llvm::BranchProbability const&) const Line | Count | Source | 212 | 75.0k | [&](uint64_t S, const BranchProbability &BP) { | 213 | 75.0k | if (!BP.isUnknown()) | 214 | 72.1k | return S + BP.N; | 215 | 2.88k | UnknownProbCount++; | 216 | 2.88k | return S; | 217 | 2.88k | }); |
|
218 | 636k | |
219 | 636k | if (UnknownProbCount > 0) { |
220 | 6.26k | BranchProbability ProbForUnknown = BranchProbability::getZero(); |
221 | 6.26k | // If the sum of all known probabilities is less than one, evenly distribute |
222 | 6.26k | // the complement of sum to unknown probabilities. Otherwise, set unknown |
223 | 6.26k | // probabilities to zeros and continue to normalize known probabilities. |
224 | 6.26k | if (Sum < BranchProbability::getDenominator()) |
225 | 6.26k | ProbForUnknown = BranchProbability::getRaw( |
226 | 6.26k | (BranchProbability::getDenominator() - Sum) / UnknownProbCount); |
227 | 6.26k | |
228 | 6.26k | std::replace_if(Begin, End, |
229 | 8.99k | [](const BranchProbability &BP) { return BP.isUnknown(); }, void llvm::BranchProbability::normalizeProbabilities<std::__1::__wrap_iter<llvm::BranchProbability*> >(std::__1::__wrap_iter<llvm::BranchProbability*>, std::__1::__wrap_iter<llvm::BranchProbability*>)::'lambda'(llvm::BranchProbability const&)::operator()(llvm::BranchProbability const&) const Line | Count | Source | 229 | 6.10k | [](const BranchProbability &BP) { return BP.isUnknown(); }, |
void llvm::BranchProbability::normalizeProbabilities<llvm::BranchProbability*>(llvm::BranchProbability*, llvm::BranchProbability*)::'lambda'(llvm::BranchProbability const&)::operator()(llvm::BranchProbability const&) const Line | Count | Source | 229 | 2.89k | [](const BranchProbability &BP) { return BP.isUnknown(); }, |
|
230 | 6.26k | ProbForUnknown); |
231 | 6.26k | |
232 | 6.26k | if (Sum <= BranchProbability::getDenominator()) |
233 | 6.26k | return; |
234 | 630k | } |
235 | 630k | |
236 | 630k | if (Sum == 0) { |
237 | 834 | BranchProbability BP(1, std::distance(Begin, End)); |
238 | 834 | std::fill(Begin, End, BP); |
239 | 834 | return; |
240 | 834 | } |
241 | 629k | |
242 | 1.89M | for (auto I = Begin; 629k I != End; ++I1.26M ) |
243 | 1.26M | I->N = (I->N * uint64_t(D) + Sum / 2) / Sum; |
244 | 629k | } void llvm::BranchProbability::normalizeProbabilities<std::__1::__wrap_iter<llvm::BranchProbability*> >(std::__1::__wrap_iter<llvm::BranchProbability*>, std::__1::__wrap_iter<llvm::BranchProbability*>) Line | Count | Source | 206 | 661k | ProbabilityIter End) { | 207 | 661k | if (Begin == End) | 208 | 62.8k | return; | 209 | 598k | | 210 | 598k | unsigned UnknownProbCount = 0; | 211 | 598k | uint64_t Sum = std::accumulate(Begin, End, uint64_t(0), | 212 | 598k | [&](uint64_t S, const BranchProbability &BP) { | 213 | 598k | if (!BP.isUnknown()) | 214 | 598k | return S + BP.N; | 215 | 598k | UnknownProbCount++; | 216 | 598k | return S; | 217 | 598k | }); | 218 | 598k | | 219 | 598k | if (UnknownProbCount > 0) { | 220 | 4.84k | BranchProbability ProbForUnknown = BranchProbability::getZero(); | 221 | 4.84k | // If the sum of all known probabilities is less than one, evenly distribute | 222 | 4.84k | // the complement of sum to unknown probabilities. Otherwise, set unknown | 223 | 4.84k | // probabilities to zeros and continue to normalize known probabilities. | 224 | 4.84k | if (Sum < BranchProbability::getDenominator()) | 225 | 4.84k | ProbForUnknown = BranchProbability::getRaw( | 226 | 4.84k | (BranchProbability::getDenominator() - Sum) / UnknownProbCount); | 227 | 4.84k | | 228 | 4.84k | std::replace_if(Begin, End, | 229 | 4.84k | [](const BranchProbability &BP) { return BP.isUnknown(); }, | 230 | 4.84k | ProbForUnknown); | 231 | 4.84k | | 232 | 4.84k | if (Sum <= BranchProbability::getDenominator()) | 233 | 4.84k | return; | 234 | 593k | } | 235 | 593k | | 236 | 593k | if (Sum == 0) { | 237 | 833 | BranchProbability BP(1, std::distance(Begin, End)); | 238 | 833 | std::fill(Begin, End, BP); | 239 | 833 | return; | 240 | 833 | } | 241 | 593k | | 242 | 1.78M | for (auto I = Begin; 593k I != End; ++I1.19M ) | 243 | 1.19M | I->N = (I->N * uint64_t(D) + Sum / 2) / Sum; | 244 | 593k | } |
void llvm::BranchProbability::normalizeProbabilities<llvm::BranchProbability*>(llvm::BranchProbability*, llvm::BranchProbability*) Line | Count | Source | 206 | 37.4k | ProbabilityIter End) { | 207 | 37.4k | if (Begin == End) | 208 | 0 | return; | 209 | 37.4k | | 210 | 37.4k | unsigned UnknownProbCount = 0; | 211 | 37.4k | uint64_t Sum = std::accumulate(Begin, End, uint64_t(0), | 212 | 37.4k | [&](uint64_t S, const BranchProbability &BP) { | 213 | 37.4k | if (!BP.isUnknown()) | 214 | 37.4k | return S + BP.N; | 215 | 37.4k | UnknownProbCount++; | 216 | 37.4k | return S; | 217 | 37.4k | }); | 218 | 37.4k | | 219 | 37.4k | if (UnknownProbCount > 0) { | 220 | 1.42k | BranchProbability ProbForUnknown = BranchProbability::getZero(); | 221 | 1.42k | // If the sum of all known probabilities is less than one, evenly distribute | 222 | 1.42k | // the complement of sum to unknown probabilities. Otherwise, set unknown | 223 | 1.42k | // probabilities to zeros and continue to normalize known probabilities. | 224 | 1.42k | if (Sum < BranchProbability::getDenominator()) | 225 | 1.41k | ProbForUnknown = BranchProbability::getRaw( | 226 | 1.41k | (BranchProbability::getDenominator() - Sum) / UnknownProbCount); | 227 | 1.42k | | 228 | 1.42k | std::replace_if(Begin, End, | 229 | 1.42k | [](const BranchProbability &BP) { return BP.isUnknown(); }, | 230 | 1.42k | ProbForUnknown); | 231 | 1.42k | | 232 | 1.42k | if (Sum <= BranchProbability::getDenominator()) | 233 | 1.42k | return; | 234 | 36.0k | } | 235 | 36.0k | | 236 | 36.0k | if (Sum == 0) { | 237 | 1 | BranchProbability BP(1, std::distance(Begin, End)); | 238 | 1 | std::fill(Begin, End, BP); | 239 | 1 | return; | 240 | 1 | } | 241 | 36.0k | | 242 | 108k | for (auto I = Begin; 36.0k I != End; ++I72.1k ) | 243 | 72.1k | I->N = (I->N * uint64_t(D) + Sum / 2) / Sum; | 244 | 36.0k | } |
|
245 | | |
246 | | } |
247 | | |
248 | | #endif |