Coverage Report

Created: 2018-09-23 16:00

/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.3M
  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.4M
  bool isUnknown() const { return N == UnknownN; }
49
50
15.5M
  static BranchProbability getZero() { return BranchProbability(0); }
51
4.45M
  static BranchProbability getOne() { return BranchProbability(D); }
52
5.43M
  static BranchProbability getUnknown() { return BranchProbability(UnknownN); }
53
  // Create a BranchProbability object with the given numerator and 1<<31
54
  // as denominator.
55
103k
  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
37.3k
  static uint32_t getDenominator() { return D; }
68
69
  // Return (1 - Probability).
70
15.8M
  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.68k
:
N + RHS.N1.71M
;
97
1.71M
    return *this;
98
1.71M
  }
99
100
1.41M
  BranchProbability &operator-=(BranchProbability RHS) {
101
1.41M
    assert(N != UnknownN && RHS.N != UnknownN &&
102
1.41M
           "Unknown probability cannot participate in arithmetics.");
103
1.41M
    // Saturate the result in case of underflow.
104
1.41M
    N = N < RHS.N ? 
030
:
N - RHS.N1.41M
;
105
1.41M
    return *this;
106
1.41M
  }
107
108
12.4k
  BranchProbability &operator*=(BranchProbability RHS) {
109
12.4k
    assert(N != UnknownN && RHS.N != UnknownN &&
110
12.4k
           "Unknown probability cannot participate in arithmetics.");
111
12.4k
    N = (static_cast<uint64_t>(N) * RHS.N + D / 2) / D;
112
12.4k
    return *this;
113
12.4k
  }
114
115
86.7k
  BranchProbability &operator*=(uint32_t RHS) {
116
86.7k
    assert(N != UnknownN &&
117
86.7k
           "Unknown probability cannot participate in arithmetics.");
118
86.7k
    N = (uint64_t(N) * RHS > D) ? 
D4
:
N * RHS86.7k
;
119
86.7k
    return *this;
120
86.7k
  }
121
122
14.3M
  BranchProbability &operator/=(uint32_t RHS) {
123
14.3M
    assert(N != UnknownN &&
124
14.3M
           "Unknown probability cannot participate in arithmetics.");
125
14.3M
    assert(RHS > 0 && "The divider cannot be zero.");
126
14.3M
    N /= RHS;
127
14.3M
    return *this;
128
14.3M
  }
129
130
55.7k
  BranchProbability operator+(BranchProbability RHS) const {
131
55.7k
    BranchProbability Prob(*this);
132
55.7k
    return Prob += RHS;
133
55.7k
  }
134
135
320k
  BranchProbability operator-(BranchProbability RHS) const {
136
320k
    BranchProbability Prob(*this);
137
320k
    return Prob -= RHS;
138
320k
  }
139
140
12.4k
  BranchProbability operator*(BranchProbability RHS) const {
141
12.4k
    BranchProbability Prob(*this);
142
12.4k
    return Prob *= RHS;
143
12.4k
  }
144
145
86.7k
  BranchProbability operator*(uint32_t RHS) const {
146
86.7k
    BranchProbability Prob(*this);
147
86.7k
    return Prob *= RHS;
148
86.7k
  }
149
150
14.3M
  BranchProbability operator/(uint32_t RHS) const {
151
14.3M
    BranchProbability Prob(*this);
152
14.3M
    return Prob /= RHS;
153
14.3M
  }
154
155
21.7k
  bool operator==(BranchProbability RHS) const { return N == RHS.N; }
156
18.3k
  bool operator!=(BranchProbability RHS) const { return !(*this == RHS); }
157
158
2.25M
  bool operator<(BranchProbability RHS) const {
159
2.25M
    assert(N != UnknownN && RHS.N != UnknownN &&
160
2.25M
           "Unknown probability cannot participate in comparisons.");
161
2.25M
    return N < RHS.N;
162
2.25M
  }
163
164
469k
  bool operator>(BranchProbability RHS) const {
165
469k
    assert(N != UnknownN && RHS.N != UnknownN &&
166
469k
           "Unknown probability cannot participate in comparisons.");
167
469k
    return RHS < *this;
168
469k
  }
169
170
258k
  bool operator<=(BranchProbability RHS) const {
171
258k
    assert(N != UnknownN && RHS.N != UnknownN &&
172
258k
           "Unknown probability cannot participate in comparisons.");
173
258k
    return !(RHS < *this);
174
258k
  }
175
176
449k
  bool operator>=(BranchProbability RHS) const {
177
449k
    assert(N != UnknownN && RHS.N != UnknownN &&
178
449k
           "Unknown probability cannot participate in comparisons.");
179
449k
    return !(*this < RHS);
180
449k
  }
181
};
182
183
910
inline raw_ostream &operator<<(raw_ostream &OS, BranchProbability Prob) {
184
910
  return Prob.print(OS);
185
910
}
186
187
template <class ProbabilityIter>
188
void BranchProbability::normalizeProbabilities(ProbabilityIter Begin,
189
990k
                                               ProbabilityIter End) {
190
990k
  if (Begin == End)
191
24.5k
    return;
192
966k
193
966k
  unsigned UnknownProbCount = 0;
194
966k
  uint64_t Sum = std::accumulate(Begin, End, uint64_t(0),
195
1.94M
                                 [&](uint64_t S, const BranchProbability &BP) {
196
1.94M
                                   if (!BP.isUnknown())
197
1.93M
                                     return S + BP.N;
198
6.73k
                                   UnknownProbCount++;
199
6.73k
                                   return S;
200
6.73k
                                 });
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.13k
                                   UnknownProbCount++;
199
5.13k
                                   return S;
200
5.13k
                                 });
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
100k
                                 [&](uint64_t S, const BranchProbability &BP) {
196
100k
                                   if (!BP.isUnknown())
197
99.3k
                                     return S + BP.N;
198
1.60k
                                   UnknownProbCount++;
199
1.60k
                                   return S;
200
1.60k
                                 });
201
966k
202
966k
  if (UnknownProbCount > 0) {
203
5.02k
    BranchProbability ProbForUnknown = BranchProbability::getZero();
204
5.02k
    // If the sum of all known probabilities is less than one, evenly distribute
205
5.02k
    // the complement of sum to unknown probabilities. Otherwise, set unknown
206
5.02k
    // probabilities to zeros and continue to normalize known probabilities.
207
5.02k
    if (Sum < BranchProbability::getDenominator())
208
5.02k
      ProbForUnknown = BranchProbability::getRaw(
209
5.02k
          (BranchProbability::getDenominator() - Sum) / UnknownProbCount);
210
5.02k
211
5.02k
    std::replace_if(Begin, End,
212
6.75k
                    [](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.13k
                    [](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.61k
                    [](const BranchProbability &BP) { return BP.isUnknown(); },
213
5.02k
                    ProbForUnknown);
214
5.02k
215
5.02k
    if (Sum <= BranchProbability::getDenominator())
216
5.02k
      return;
217
961k
  }
218
961k
219
961k
  if (Sum == 0) {
220
312
    BranchProbability BP(1, std::distance(Begin, End));
221
312
    std::fill(Begin, End, BP);
222
312
    return;
223
312
  }
224
960k
225
2.89M
  
for (auto I = Begin; 960k
I != End;
++I1.93M
)
226
1.93M
    I->N = (I->N * uint64_t(D) + Sum / 2) / Sum;
227
960k
}
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.5k
    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.23k
    BranchProbability ProbForUnknown = BranchProbability::getZero();
204
4.23k
    // If the sum of all known probabilities is less than one, evenly distribute
205
4.23k
    // the complement of sum to unknown probabilities. Otherwise, set unknown
206
4.23k
    // probabilities to zeros and continue to normalize known probabilities.
207
4.23k
    if (Sum < BranchProbability::getDenominator())
208
4.23k
      ProbForUnknown = BranchProbability::getRaw(
209
4.23k
          (BranchProbability::getDenominator() - Sum) / UnknownProbCount);
210
4.23k
211
4.23k
    std::replace_if(Begin, End,
212
4.23k
                    [](const BranchProbability &BP) { return BP.isUnknown(); },
213
4.23k
                    ProbForUnknown);
214
4.23k
215
4.23k
    if (Sum <= BranchProbability::getDenominator())
216
4.23k
      return;
217
911k
  }
218
911k
219
911k
  if (Sum == 0) {
220
311
    BranchProbability BP(1, std::distance(Begin, End));
221
311
    std::fill(Begin, End, BP);
222
311
    return;
223
311
  }
224
911k
225
2.74M
  
for (auto I = Begin; 911k
I != End;
++I1.83M
)
226
1.83M
    I->N = (I->N * uint64_t(D) + Sum / 2) / Sum;
227
911k
}
void llvm::BranchProbability::normalizeProbabilities<llvm::BranchProbability*>(llvm::BranchProbability*, llvm::BranchProbability*)
Line
Count
Source
189
50.4k
                                               ProbabilityIter End) {
190
50.4k
  if (Begin == End)
191
0
    return;
192
50.4k
193
50.4k
  unsigned UnknownProbCount = 0;
194
50.4k
  uint64_t Sum = std::accumulate(Begin, End, uint64_t(0),
195
50.4k
                                 [&](uint64_t S, const BranchProbability &BP) {
196
50.4k
                                   if (!BP.isUnknown())
197
50.4k
                                     return S + BP.N;
198
50.4k
                                   UnknownProbCount++;
199
50.4k
                                   return S;
200
50.4k
                                 });
201
50.4k
202
50.4k
  if (UnknownProbCount > 0) {
203
785
    BranchProbability ProbForUnknown = BranchProbability::getZero();
204
785
    // If the sum of all known probabilities is less than one, evenly distribute
205
785
    // the complement of sum to unknown probabilities. Otherwise, set unknown
206
785
    // probabilities to zeros and continue to normalize known probabilities.
207
785
    if (Sum < BranchProbability::getDenominator())
208
782
      ProbForUnknown = BranchProbability::getRaw(
209
782
          (BranchProbability::getDenominator() - Sum) / UnknownProbCount);
210
785
211
785
    std::replace_if(Begin, End,
212
785
                    [](const BranchProbability &BP) { return BP.isUnknown(); },
213
785
                    ProbForUnknown);
214
785
215
785
    if (Sum <= BranchProbability::getDenominator())
216
784
      return;
217
49.6k
  }
218
49.6k
219
49.6k
  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
49.6k
225
149k
  
for (auto I = Begin; 49.6k
I != End;
++I99.3k
)
226
99.3k
    I->N = (I->N * uint64_t(D) + Sum / 2) / Sum;
227
49.6k
}
228
229
}
230
231
#endif