Coverage Report

Created: 2018-11-12 17:33

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/include/llvm/Support/BranchProbability.h
Line
Count
Source (jump to first uncovered line)
1
//===- BranchProbability.h - Branch Probability Wrapper ---------*- C++ -*-===//
2
//
3
//                     The LLVM Compiler Infrastructure
4
//
5
// This file is distributed under the University of Illinois Open Source
6
// License. See LICENSE.TXT for details.
7
//
8
//===----------------------------------------------------------------------===//
9
//
10
// Definition of BranchProbability shared by IR and Machine Instructions.
11
//
12
//===----------------------------------------------------------------------===//
13
14
#ifndef LLVM_SUPPORT_BRANCHPROBABILITY_H
15
#define LLVM_SUPPORT_BRANCHPROBABILITY_H
16
17
#include "llvm/Support/DataTypes.h"
18
#include <algorithm>
19
#include <cassert>
20
#include <climits>
21
#include <numeric>
22
23
namespace llvm {
24
25
class raw_ostream;
26
27
// This class represents Branch Probability as a non-negative fraction that is
28
// no greater than 1. It uses a fixed-point-like implementation, in which the
29
// denominator is always a constant value (here we use 1<<31 for maximum
30
// precision).
31
0
class BranchProbability {
Unexecuted instantiation: llvm::BranchProbability::operator=(llvm::BranchProbability const&)
Unexecuted instantiation: llvm::BranchProbability::operator=(llvm::BranchProbability&&)
32
  // Numerator
33
  uint32_t N;
34
35
  // Denominator, which is a constant value.
36
  static const uint32_t D = 1u << 31;
37
  static const uint32_t UnknownN = UINT32_MAX;
38
39
  // Construct a BranchProbability with only numerator assuming the denominator
40
  // is 1<<31. For internal use only.
41
41.5M
  explicit BranchProbability(uint32_t n) : N(n) {}
42
43
public:
44
16.8M
  BranchProbability() : N(UnknownN) {}
45
  BranchProbability(uint32_t Numerator, uint32_t Denominator);
46
47
18
  bool isZero() const { return N == 0; }
48
42.5M
  bool isUnknown() const { return N == UnknownN; }
49
50
15.6M
  static BranchProbability getZero() { return BranchProbability(0); }
51
4.45M
  static BranchProbability getOne() { return BranchProbability(D); }
52
5.44M
  static BranchProbability getUnknown() { return BranchProbability(UnknownN); }
53
  // Create a BranchProbability object with the given numerator and 1<<31
54
  // as denominator.
55
105k
  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);
59
60
  // Normalize given probabilties so that the sum of them becomes approximate
61
  // one.
62
  template <class ProbabilityIter>
63
  static void normalizeProbabilities(ProbabilityIter Begin,
64
                                     ProbabilityIter End);
65
66
42.0M
  uint32_t getNumerator() const { return N; }
67
39.4k
  static uint32_t getDenominator() { return D; }
68
69
  // Return (1 - Probability).
70
15.9M
  BranchProbability getCompl() const { return BranchProbability(D - N); }
71
72
  raw_ostream &print(raw_ostream &OS) const;
73
74
  void dump() const;
75
76
  /// Scale a large integer.
77
  ///
78
  /// Scales \c Num.  Guarantees full precision.  Returns the floor of the
79
  /// result.
80
  ///
81
  /// \return \c Num times \c this.
82
  uint64_t scale(uint64_t Num) const;
83
84
  /// Scale a large integer by the inverse.
85
  ///
86
  /// Scales \c Num by the inverse of \c this.  Guarantees full precision.
87
  /// Returns the floor of the result.
88
  ///
89
  /// \return \c Num divided by \c this.
90
  uint64_t scaleByInverse(uint64_t Num) const;
91
92
1.71M
  BranchProbability &operator+=(BranchProbability RHS) {
93
1.71M
    assert(N != UnknownN && RHS.N != UnknownN &&
94
1.71M
           "Unknown probability cannot participate in arithmetics.");
95
1.71M
    // Saturate the result in case of overflow.
96
1.71M
    N = (uint64_t(N) + RHS.N > D) ? 
D6.46k
:
N + RHS.N1.71M
;
97
1.71M
    return *this;
98
1.71M
  }
99
100
1.42M
  BranchProbability &operator-=(BranchProbability RHS) {
101
1.42M
    assert(N != UnknownN && RHS.N != UnknownN &&
102
1.42M
           "Unknown probability cannot participate in arithmetics.");
103
1.42M
    // Saturate the result in case of underflow.
104
1.42M
    N = N < RHS.N ? 
024
:
N - RHS.N1.42M
;
105
1.42M
    return *this;
106
1.42M
  }
107
108
12.3k
  BranchProbability &operator*=(BranchProbability RHS) {
109
12.3k
    assert(N != UnknownN && RHS.N != UnknownN &&
110
12.3k
           "Unknown probability cannot participate in arithmetics.");
111
12.3k
    N = (static_cast<uint64_t>(N) * RHS.N + D / 2) / D;
112
12.3k
    return *this;
113
12.3k
  }
114
115
89.2k
  BranchProbability &operator*=(uint32_t RHS) {
116
89.2k
    assert(N != UnknownN &&
117
89.2k
           "Unknown probability cannot participate in arithmetics.");
118
89.2k
    N = (uint64_t(N) * RHS > D) ? 
D4
:
N * RHS89.2k
;
119
89.2k
    return *this;
120
89.2k
  }
121
122
14.4M
  BranchProbability &operator/=(uint32_t RHS) {
123
14.4M
    assert(N != UnknownN &&
124
14.4M
           "Unknown probability cannot participate in arithmetics.");
125
14.4M
    assert(RHS > 0 && "The divider cannot be zero.");
126
14.4M
    N /= RHS;
127
14.4M
    return *this;
128
14.4M
  }
129
130
54.7k
  BranchProbability operator+(BranchProbability RHS) const {
131
54.7k
    BranchProbability Prob(*this);
132
54.7k
    return Prob += RHS;
133
54.7k
  }
134
135
324k
  BranchProbability operator-(BranchProbability RHS) const {
136
324k
    BranchProbability Prob(*this);
137
324k
    return Prob -= RHS;
138
324k
  }
139
140
12.2k
  BranchProbability operator*(BranchProbability RHS) const {
141
12.2k
    BranchProbability Prob(*this);
142
12.2k
    return Prob *= RHS;
143
12.2k
  }
144
145
89.2k
  BranchProbability operator*(uint32_t RHS) const {
146
89.2k
    BranchProbability Prob(*this);
147
89.2k
    return Prob *= RHS;
148
89.2k
  }
149
150
14.4M
  BranchProbability operator/(uint32_t RHS) const {
151
14.4M
    BranchProbability Prob(*this);
152
14.4M
    return Prob /= RHS;
153
14.4M
  }
154
155
21.4k
  bool operator==(BranchProbability RHS) const { return N == RHS.N; }
156
17.9k
  bool operator!=(BranchProbability RHS) const { return !(*this == RHS); }
157
158
2.26M
  bool operator<(BranchProbability RHS) const {
159
2.26M
    assert(N != UnknownN && RHS.N != UnknownN &&
160
2.26M
           "Unknown probability cannot participate in comparisons.");
161
2.26M
    return N < RHS.N;
162
2.26M
  }
163
164
472k
  bool operator>(BranchProbability RHS) const {
165
472k
    assert(N != UnknownN && RHS.N != UnknownN &&
166
472k
           "Unknown probability cannot participate in comparisons.");
167
472k
    return RHS < *this;
168
472k
  }
169
170
262k
  bool operator<=(BranchProbability RHS) const {
171
262k
    assert(N != UnknownN && RHS.N != UnknownN &&
172
262k
           "Unknown probability cannot participate in comparisons.");
173
262k
    return !(RHS < *this);
174
262k
  }
175
176
450k
  bool operator>=(BranchProbability RHS) const {
177
450k
    assert(N != UnknownN && RHS.N != UnknownN &&
178
450k
           "Unknown probability cannot participate in comparisons.");
179
450k
    return !(*this < RHS);
180
450k
  }
181
};
182
183
921
inline raw_ostream &operator<<(raw_ostream &OS, BranchProbability Prob) {
184
921
  return Prob.print(OS);
185
921
}
186
187
template <class ProbabilityIter>
188
void BranchProbability::normalizeProbabilities(ProbabilityIter Begin,
189
989k
                                               ProbabilityIter End) {
190
989k
  if (Begin == End)
191
24.8k
    return;
192
965k
193
965k
  unsigned UnknownProbCount = 0;
194
965k
  uint64_t Sum = std::accumulate(Begin, End, uint64_t(0),
195
1.93M
                                 [&](uint64_t S, const BranchProbability &BP) {
196
1.93M
                                   if (!BP.isUnknown())
197
1.93M
                                     return S + BP.N;
198
7.05k
                                   UnknownProbCount++;
199
7.05k
                                   return S;
200
7.05k
                                 });
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
195
1.83M
                                 [&](uint64_t S, const BranchProbability &BP) {
196
1.83M
                                   if (!BP.isUnknown())
197
1.83M
                                     return S + BP.N;
198
5.34k
                                   UnknownProbCount++;
199
5.34k
                                   return S;
200
5.34k
                                 });
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
195
99.2k
                                 [&](uint64_t S, const BranchProbability &BP) {
196
99.2k
                                   if (!BP.isUnknown())
197
97.5k
                                     return S + BP.N;
198
1.71k
                                   UnknownProbCount++;
199
1.71k
                                   return S;
200
1.71k
                                 });
201
965k
202
965k
  if (UnknownProbCount > 0) {
203
5.24k
    BranchProbability ProbForUnknown = BranchProbability::getZero();
204
5.24k
    // If the sum of all known probabilities is less than one, evenly distribute
205
5.24k
    // the complement of sum to unknown probabilities. Otherwise, set unknown
206
5.24k
    // probabilities to zeros and continue to normalize known probabilities.
207
5.24k
    if (Sum < BranchProbability::getDenominator())
208
5.24k
      ProbForUnknown = BranchProbability::getRaw(
209
5.24k
          (BranchProbability::getDenominator() - Sum) / UnknownProbCount);
210
5.24k
211
5.24k
    std::replace_if(Begin, End,
212
7.06k
                    [](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
212
5.34k
                    [](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
212
1.72k
                    [](const BranchProbability &BP) { return BP.isUnknown(); },
213
5.24k
                    ProbForUnknown);
214
5.24k
215
5.24k
    if (Sum <= BranchProbability::getDenominator())
216
5.24k
      return;
217
959k
  }
218
959k
219
959k
  if (Sum == 0) {
220
354
    BranchProbability BP(1, std::distance(Begin, End));
221
354
    std::fill(Begin, End, BP);
222
354
    return;
223
354
  }
224
959k
225
2.89M
  
for (auto I = Begin; 959k
I != End;
++I1.93M
)
226
1.93M
    I->N = (I->N * uint64_t(D) + Sum / 2) / Sum;
227
959k
}
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
189
940k
                                               ProbabilityIter End) {
190
940k
  if (Begin == End)
191
24.8k
    return;
192
915k
193
915k
  unsigned UnknownProbCount = 0;
194
915k
  uint64_t Sum = std::accumulate(Begin, End, uint64_t(0),
195
915k
                                 [&](uint64_t S, const BranchProbability &BP) {
196
915k
                                   if (!BP.isUnknown())
197
915k
                                     return S + BP.N;
198
915k
                                   UnknownProbCount++;
199
915k
                                   return S;
200
915k
                                 });
201
915k
202
915k
  if (UnknownProbCount > 0) {
203
4.40k
    BranchProbability ProbForUnknown = BranchProbability::getZero();
204
4.40k
    // If the sum of all known probabilities is less than one, evenly distribute
205
4.40k
    // the complement of sum to unknown probabilities. Otherwise, set unknown
206
4.40k
    // probabilities to zeros and continue to normalize known probabilities.
207
4.40k
    if (Sum < BranchProbability::getDenominator())
208
4.40k
      ProbForUnknown = BranchProbability::getRaw(
209
4.40k
          (BranchProbability::getDenominator() - Sum) / UnknownProbCount);
210
4.40k
211
4.40k
    std::replace_if(Begin, End,
212
4.40k
                    [](const BranchProbability &BP) { return BP.isUnknown(); },
213
4.40k
                    ProbForUnknown);
214
4.40k
215
4.40k
    if (Sum <= BranchProbability::getDenominator())
216
4.40k
      return;
217
911k
  }
218
911k
219
911k
  if (Sum == 0) {
220
353
    BranchProbability BP(1, std::distance(Begin, End));
221
353
    std::fill(Begin, End, BP);
222
353
    return;
223
353
  }
224
910k
225
2.74M
  
for (auto I = Begin; 910k
I != End;
++I1.83M
)
226
1.83M
    I->N = (I->N * uint64_t(D) + Sum / 2) / Sum;
227
910k
}
void llvm::BranchProbability::normalizeProbabilities<llvm::BranchProbability*>(llvm::BranchProbability*, llvm::BranchProbability*)
Line
Count
Source
189
49.5k
                                               ProbabilityIter End) {
190
49.5k
  if (Begin == End)
191
0
    return;
192
49.5k
193
49.5k
  unsigned UnknownProbCount = 0;
194
49.5k
  uint64_t Sum = std::accumulate(Begin, End, uint64_t(0),
195
49.5k
                                 [&](uint64_t S, const BranchProbability &BP) {
196
49.5k
                                   if (!BP.isUnknown())
197
49.5k
                                     return S + BP.N;
198
49.5k
                                   UnknownProbCount++;
199
49.5k
                                   return S;
200
49.5k
                                 });
201
49.5k
202
49.5k
  if (UnknownProbCount > 0) {
203
836
    BranchProbability ProbForUnknown = BranchProbability::getZero();
204
836
    // If the sum of all known probabilities is less than one, evenly distribute
205
836
    // the complement of sum to unknown probabilities. Otherwise, set unknown
206
836
    // probabilities to zeros and continue to normalize known probabilities.
207
836
    if (Sum < BranchProbability::getDenominator())
208
833
      ProbForUnknown = BranchProbability::getRaw(
209
833
          (BranchProbability::getDenominator() - Sum) / UnknownProbCount);
210
836
211
836
    std::replace_if(Begin, End,
212
836
                    [](const BranchProbability &BP) { return BP.isUnknown(); },
213
836
                    ProbForUnknown);
214
836
215
836
    if (Sum <= BranchProbability::getDenominator())
216
835
      return;
217
48.7k
  }
218
48.7k
219
48.7k
  if (Sum == 0) {
220
1
    BranchProbability BP(1, std::distance(Begin, End));
221
1
    std::fill(Begin, End, BP);
222
1
    return;
223
1
  }
224
48.7k
225
146k
  
for (auto I = Begin; 48.7k
I != End;
++I97.5k
)
226
97.5k
    I->N = (I->N * uint64_t(D) + Sum / 2) / Sum;
227
48.7k
}
228
229
}
230
231
#endif