Coverage Report

Created: 2019-07-24 05:18

/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