Mercurial > hg > CbC > CbC_llvm

comparison include/llvm/Support/BranchProbability.h @ 100:7d135dc70f03 LLVM 3.9

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
LLVM 3.9
author Miyagi Mitsuki <e135756@ie.u-ryukyu.ac.jp>
date Tue, 26 Jan 2016 22:53:40 +0900
parents afa8332a0e37
children 1172e4bd9c6f
comparison
equal deleted inserted replaced
96:6418606d0ead 100:7d135dc70f03
13 13
14 #ifndef LLVM_SUPPORT_BRANCHPROBABILITY_H 14 #ifndef LLVM_SUPPORT_BRANCHPROBABILITY_H
15 #define LLVM_SUPPORT_BRANCHPROBABILITY_H 15 #define LLVM_SUPPORT_BRANCHPROBABILITY_H
16 16
17 #include "llvm/Support/DataTypes.h" 17 #include "llvm/Support/DataTypes.h"
18 #include <algorithm>
18 #include <cassert> 19 #include <cassert>
20 #include <climits>
21 #include <numeric>
19 22
20 namespace llvm { 23 namespace llvm {
21 24
22 class raw_ostream; 25 class raw_ostream;
23 26
29 // Numerator 32 // Numerator
30 uint32_t N; 33 uint32_t N;
31 34
32 // Denominator, which is a constant value. 35 // Denominator, which is a constant value.
33 static const uint32_t D = 1u << 31; 36 static const uint32_t D = 1u << 31;
37 static const uint32_t UnknownN = UINT32_MAX;
34 38
35 // Construct a BranchProbability with only numerator assuming the denominator 39 // Construct a BranchProbability with only numerator assuming the denominator
36 // is 1<<31. For internal use only. 40 // is 1<<31. For internal use only.
37 explicit BranchProbability(uint32_t n) : N(n) {} 41 explicit BranchProbability(uint32_t n) : N(n) {}
38 42
39 public: 43 public:
40 BranchProbability() : N(0) {} 44 BranchProbability() : N(UnknownN) {}
41 BranchProbability(uint32_t Numerator, uint32_t Denominator); 45 BranchProbability(uint32_t Numerator, uint32_t Denominator);
42 46
43 bool isZero() const { return N == 0; } 47 bool isZero() const { return N == 0; }
48 bool isUnknown() const { return N == UnknownN; }
44 49
45 static BranchProbability getZero() { return BranchProbability(0); } 50 static BranchProbability getZero() { return BranchProbability(0); }
46 static BranchProbability getOne() { return BranchProbability(D); } 51 static BranchProbability getOne() { return BranchProbability(D); }
52 static BranchProbability getUnknown() { return BranchProbability(UnknownN); }
47 // Create a BranchProbability object with the given numerator and 1<<31 53 // Create a BranchProbability object with the given numerator and 1<<31
48 // as denominator. 54 // as denominator.
49 static BranchProbability getRaw(uint32_t N) { return BranchProbability(N); } 55 static BranchProbability getRaw(uint32_t N) { return BranchProbability(N); }
56 // Create a BranchProbability object from 64-bit integers.
57 static BranchProbability getBranchProbability(uint64_t Numerator,
58 uint64_t Denominator);
50 59
51 // Normalize given probabilties so that the sum of them becomes approximate 60 // Normalize given probabilties so that the sum of them becomes approximate
52 // one. 61 // one.
53 template <class ProbabilityList> 62 template <class ProbabilityIter>
54 static void normalizeProbabilities(ProbabilityList &Probs); 63 static void normalizeProbabilities(ProbabilityIter Begin,
64 ProbabilityIter End);
55 65
56 uint32_t getNumerator() const { return N; } 66 uint32_t getNumerator() const { return N; }
57 static uint32_t getDenominator() { return D; } 67 static uint32_t getDenominator() { return D; }
58 68
59 // Return (1 - Probability). 69 // Return (1 - Probability).
78 /// 88 ///
79 /// \return \c Num divided by \c this. 89 /// \return \c Num divided by \c this.
80 uint64_t scaleByInverse(uint64_t Num) const; 90 uint64_t scaleByInverse(uint64_t Num) const;
81 91
82 BranchProbability &operator+=(BranchProbability RHS) { 92 BranchProbability &operator+=(BranchProbability RHS) {
83 assert(N <= D - RHS.N && 93 assert(N != UnknownN && RHS.N != UnknownN &&
84 "The sum of branch probabilities should not exceed one!"); 94 "Unknown probability cannot participate in arithmetics.");
85 N += RHS.N; 95 // Saturate the result in case of overflow.
96 N = (uint64_t(N) + RHS.N > D) ? D : N + RHS.N;
86 return *this; 97 return *this;
87 } 98 }
88 99
89 BranchProbability &operator-=(BranchProbability RHS) { 100 BranchProbability &operator-=(BranchProbability RHS) {
90 assert(N >= RHS.N && 101 assert(N != UnknownN && RHS.N != UnknownN &&
91 "Can only subtract a smaller probability from a larger one!"); 102 "Unknown probability cannot participate in arithmetics.");
92 N -= RHS.N; 103 // Saturate the result in case of underflow.
104 N = N < RHS.N ? 0 : N - RHS.N;
93 return *this; 105 return *this;
94 } 106 }
95 107
96 BranchProbability &operator*=(BranchProbability RHS) { 108 BranchProbability &operator*=(BranchProbability RHS) {
109 assert(N != UnknownN && RHS.N != UnknownN &&
110 "Unknown probability cannot participate in arithmetics.");
97 N = (static_cast<uint64_t>(N) * RHS.N + D / 2) / D; 111 N = (static_cast<uint64_t>(N) * RHS.N + D / 2) / D;
98 return *this; 112 return *this;
99 } 113 }
100 114
115 BranchProbability &operator/=(uint32_t RHS) {
116 assert(N != UnknownN &&
117 "Unknown probability cannot participate in arithmetics.");
118 assert(RHS > 0 && "The divider cannot be zero.");
119 N /= RHS;
120 return *this;
121 }
122
101 BranchProbability operator+(BranchProbability RHS) const { 123 BranchProbability operator+(BranchProbability RHS) const {
102 BranchProbability Prob(*this); 124 BranchProbability Prob(*this);
103 return Prob += RHS; 125 return Prob += RHS;
104 } 126 }
105 127
109 } 131 }
110 132
111 BranchProbability operator*(BranchProbability RHS) const { 133 BranchProbability operator*(BranchProbability RHS) const {
112 BranchProbability Prob(*this); 134 BranchProbability Prob(*this);
113 return Prob *= RHS; 135 return Prob *= RHS;
136 }
137
138 BranchProbability operator/(uint32_t RHS) const {
139 BranchProbability Prob(*this);
140 return Prob /= RHS;
114 } 141 }
115 142
116 bool operator==(BranchProbability RHS) const { return N == RHS.N; } 143 bool operator==(BranchProbability RHS) const { return N == RHS.N; }
117 bool operator!=(BranchProbability RHS) const { return !(*this == RHS); } 144 bool operator!=(BranchProbability RHS) const { return !(*this == RHS); }
118 bool operator<(BranchProbability RHS) const { return N < RHS.N; } 145
119 bool operator>(BranchProbability RHS) const { return RHS < *this; } 146 bool operator<(BranchProbability RHS) const {
120 bool operator<=(BranchProbability RHS) const { return !(RHS < *this); } 147 assert(N != UnknownN && RHS.N != UnknownN &&
121 bool operator>=(BranchProbability RHS) const { return !(*this < RHS); } 148 "Unknown probability cannot participate in comparisons.");
149 return N < RHS.N;
150 }
151
152 bool operator>(BranchProbability RHS) const {
153 assert(N != UnknownN && RHS.N != UnknownN &&
154 "Unknown probability cannot participate in comparisons.");
155 return RHS < *this;
156 }
157
158 bool operator<=(BranchProbability RHS) const {
159 assert(N != UnknownN && RHS.N != UnknownN &&
160 "Unknown probability cannot participate in comparisons.");
161 return !(RHS < *this);
162 }
163
164 bool operator>=(BranchProbability RHS) const {
165 assert(N != UnknownN && RHS.N != UnknownN &&
166 "Unknown probability cannot participate in comparisons.");
167 return !(*this < RHS);
168 }
122 }; 169 };
123 170
124 inline raw_ostream &operator<<(raw_ostream &OS, BranchProbability Prob) { 171 inline raw_ostream &operator<<(raw_ostream &OS, BranchProbability Prob) {
125 return Prob.print(OS); 172 return Prob.print(OS);
126 } 173 }
127 174
128 template <class ProbabilityList> 175 template <class ProbabilityIter>
129 void BranchProbability::normalizeProbabilities(ProbabilityList &Probs) { 176 void BranchProbability::normalizeProbabilities(ProbabilityIter Begin,
130 uint64_t Sum = 0; 177 ProbabilityIter End) {
131 for (auto Prob : Probs) 178 if (Begin == End)
132 Sum += Prob.N; 179 return;
133 assert(Sum > 0); 180
134 for (auto &Prob : Probs) 181 unsigned UnknownProbCount = 0;
135 Prob.N = (Prob.N * uint64_t(D) + Sum / 2) / Sum; 182 uint64_t Sum = std::accumulate(Begin, End, uint64_t(0),
183 [&](uint64_t S, const BranchProbability &BP) {
184 if (!BP.isUnknown())
185 return S + BP.N;
186 UnknownProbCount++;
187 return S;
188 });
189
190 if (UnknownProbCount > 0) {
191 BranchProbability ProbForUnknown = BranchProbability::getZero();
192 // If the sum of all known probabilities is less than one, evenly distribute
193 // the complement of sum to unknown probabilities. Otherwise, set unknown
194 // probabilities to zeros and continue to normalize known probabilities.
195 if (Sum < BranchProbability::getDenominator())
196 ProbForUnknown = BranchProbability::getRaw(
197 (BranchProbability::getDenominator() - Sum) / UnknownProbCount);
198
199 std::replace_if(Begin, End,
200 [](const BranchProbability &BP) { return BP.isUnknown(); },
201 ProbForUnknown);
202
203 if (Sum <= BranchProbability::getDenominator())
204 return;
205 }
206
207 if (Sum == 0) {
208 BranchProbability BP(1, std::distance(Begin, End));
209 std::fill(Begin, End, BP);
210 return;
211 }
212
213 for (auto I = Begin; I != End; ++I)
214 I->N = (I->N * uint64_t(D) + Sum / 2) / Sum;
136 } 215 }
137 216
138 } 217 }
139 218
140 #endif 219 #endif