Coverage Report

Created: 2018-07-19 03:59

/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
40.3M
  explicit BranchProbability(uint32_t n) : N(n) {}
42
43
public:
44
16.3M
  BranchProbability() : N(UnknownN) {}
45
  BranchProbability(uint32_t Numerator, uint32_t Denominator);
46
47
18
  bool isZero() const { return N == 0; }
48
41.4M
  bool isUnknown() const { return N == UnknownN; }
49
50
15.1M
  static BranchProbability getZero() { return BranchProbability(0); }
51
4.33M
  static BranchProbability getOne() { return BranchProbability(D); }
52
5.28M
  static BranchProbability getUnknown() { return BranchProbability(UnknownN); }
53
  // Create a BranchProbability object with the given numerator and 1<<31
54
  // as denominator.
55
101k
  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
40.9M
  uint32_t getNumerator() const { return N; }
67
36.5k
  static uint32_t getDenominator() { return D; }
68
69
  // Return (1 - Probability).
70
15.4M
  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.66M
  BranchProbability &operator+=(BranchProbability RHS) {
93
1.66M
    assert(N != UnknownN && RHS.N != UnknownN &&
94
1.66M
           "Unknown probability cannot participate in arithmetics.");
95
1.66M
    // Saturate the result in case of overflow.
96
1.66M
    N = (uint64_t(N) + RHS.N > D) ? 
D6.60k
:
N + RHS.N1.66M
;
97
1.66M
    return *this;
98
1.66M
  }
99
100
1.37M
  BranchProbability &operator-=(BranchProbability RHS) {
101
1.37M
    assert(N != UnknownN && RHS.N != UnknownN &&
102
1.37M
           "Unknown probability cannot participate in arithmetics.");
103
1.37M
    // Saturate the result in case of underflow.
104
1.37M
    N = N < RHS.N ? 
024
:
N - RHS.N1.37M
;
105
1.37M
    return *this;
106
1.37M
  }
107
108
11.8k
  BranchProbability &operator*=(BranchProbability RHS) {
109
11.8k
    assert(N != UnknownN && RHS.N != UnknownN &&
110
11.8k
           "Unknown probability cannot participate in arithmetics.");
111
11.8k
    N = (static_cast<uint64_t>(N) * RHS.N + D / 2) / D;
112
11.8k
    return *this;
113
11.8k
  }
114
115
81.7k
  BranchProbability &operator*=(uint32_t RHS) {
116
81.7k
    assert(N != UnknownN &&
117
81.7k
           "Unknown probability cannot participate in arithmetics.");
118
81.7k
    N = (uint64_t(N) * RHS > D) ? 
D4
:
N * RHS81.7k
;
119
81.7k
    return *this;
120
81.7k
  }
121
122
14.1M
  BranchProbability &operator/=(uint32_t RHS) {
123
14.1M
    assert(N != UnknownN &&
124
14.1M
           "Unknown probability cannot participate in arithmetics.");
125
14.1M
    assert(RHS > 0 && "The divider cannot be zero.");
126
14.1M
    N /= RHS;
127
14.1M
    return *this;
128
14.1M
  }
129
130
54.6k
  BranchProbability operator+(BranchProbability RHS) const {
131
54.6k
    BranchProbability Prob(*this);
132
54.6k
    return Prob += RHS;
133
54.6k
  }
134
135
311k
  BranchProbability operator-(BranchProbability RHS) const {
136
311k
    BranchProbability Prob(*this);
137
311k
    return Prob -= RHS;
138
311k
  }
139
140
11.8k
  BranchProbability operator*(BranchProbability RHS) const {
141
11.8k
    BranchProbability Prob(*this);
142
11.8k
    return Prob *= RHS;
143
11.8k
  }
144
145
81.7k
  BranchProbability operator*(uint32_t RHS) const {
146
81.7k
    BranchProbability Prob(*this);
147
81.7k
    return Prob *= RHS;
148
81.7k
  }
149
150
14.1M
  BranchProbability operator/(uint32_t RHS) const {
151
14.1M
    BranchProbability Prob(*this);
152
14.1M
    return Prob /= RHS;
153
14.1M
  }
154
155
21.4k
  bool operator==(BranchProbability RHS) const { return N == RHS.N; }
156
18.0k
  bool operator!=(BranchProbability RHS) const { return !(*this == RHS); }
157
158
2.19M
  bool operator<(BranchProbability RHS) const {
159
2.19M
    assert(N != UnknownN && RHS.N != UnknownN &&
160
2.19M
           "Unknown probability cannot participate in comparisons.");
161
2.19M
    return N < RHS.N;
162
2.19M
  }
163
164
457k
  bool operator>(BranchProbability RHS) const {
165
457k
    assert(N != UnknownN && RHS.N != UnknownN &&
166
457k
           "Unknown probability cannot participate in comparisons.");
167
457k
    return RHS < *this;
168
457k
  }
169
170
250k
  bool operator<=(BranchProbability RHS) const {
171
250k
    assert(N != UnknownN && RHS.N != UnknownN &&
172
250k
           "Unknown probability cannot participate in comparisons.");
173
250k
    return !(RHS < *this);
174
250k
  }
175
176
444k
  bool operator>=(BranchProbability RHS) const {
177
444k
    assert(N != UnknownN && RHS.N != UnknownN &&
178
444k
           "Unknown probability cannot participate in comparisons.");
179
444k
    return !(*this < RHS);
180
444k
  }
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
961k
                                               ProbabilityIter End) {
190
961k
  if (Begin == End)
191
23.7k
    return;
192
938k
193
938k
  unsigned UnknownProbCount = 0;
194
938k
  uint64_t Sum = std::accumulate(Begin, End, uint64_t(0),
195
1.88M
                                 [&](uint64_t S, const BranchProbability &BP) {
196
1.88M
                                   if (!BP.isUnknown())
197
1.87M
                                     return S + BP.N;
198
6.53k
                                   UnknownProbCount++;
199
6.53k
                                   return S;
200
6.53k
                                 });
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.78M
                                 [&](uint64_t S, const BranchProbability &BP) {
196
1.78M
                                   if (!BP.isUnknown())
197
1.77M
                                     return S + BP.N;
198
4.99k
                                   UnknownProbCount++;
199
4.99k
                                   return S;
200
4.99k
                                 });
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.3k
                                 [&](uint64_t S, const BranchProbability &BP) {
196
99.3k
                                   if (!BP.isUnknown())
197
97.8k
                                     return S + BP.N;
198
1.53k
                                   UnknownProbCount++;
199
1.53k
                                   return S;
200
1.53k
                                 });
201
938k
202
938k
  if (UnknownProbCount > 0) {
203
4.90k
    BranchProbability ProbForUnknown = BranchProbability::getZero();
204
4.90k
    // If the sum of all known probabilities is less than one, evenly distribute
205
4.90k
    // the complement of sum to unknown probabilities. Otherwise, set unknown
206
4.90k
    // probabilities to zeros and continue to normalize known probabilities.
207
4.90k
    if (Sum < BranchProbability::getDenominator())
208
4.89k
      ProbForUnknown = BranchProbability::getRaw(
209
4.89k
          (BranchProbability::getDenominator() - Sum) / UnknownProbCount);
210
4.90k
211
4.90k
    std::replace_if(Begin, End,
212
6.55k
                    [](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.00k
                    [](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.54k
                    [](const BranchProbability &BP) { return BP.isUnknown(); },
213
4.90k
                    ProbForUnknown);
214
4.90k
215
4.90k
    if (Sum <= BranchProbability::getDenominator())
216
4.89k
      return;
217
933k
  }
218
933k
219
933k
  if (Sum == 0) {
220
291
    BranchProbability BP(1, std::distance(Begin, End));
221
291
    std::fill(Begin, End, BP);
222
291
    return;
223
291
  }
224
932k
225
2.80M
  
for (auto I = Begin; 932k
I != End;
++I1.87M
)
226
1.87M
    I->N = (I->N * uint64_t(D) + Sum / 2) / Sum;
227
932k
}
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
912k
                                               ProbabilityIter End) {
190
912k
  if (Begin == End)
191
23.7k
    return;
192
888k
193
888k
  unsigned UnknownProbCount = 0;
194
888k
  uint64_t Sum = std::accumulate(Begin, End, uint64_t(0),
195
888k
                                 [&](uint64_t S, const BranchProbability &BP) {
196
888k
                                   if (!BP.isUnknown())
197
888k
                                     return S + BP.N;
198
888k
                                   UnknownProbCount++;
199
888k
                                   return S;
200
888k
                                 });
201
888k
202
888k
  if (UnknownProbCount > 0) {
203
4.14k
    BranchProbability ProbForUnknown = BranchProbability::getZero();
204
4.14k
    // If the sum of all known probabilities is less than one, evenly distribute
205
4.14k
    // the complement of sum to unknown probabilities. Otherwise, set unknown
206
4.14k
    // probabilities to zeros and continue to normalize known probabilities.
207
4.14k
    if (Sum < BranchProbability::getDenominator())
208
4.14k
      ProbForUnknown = BranchProbability::getRaw(
209
4.14k
          (BranchProbability::getDenominator() - Sum) / UnknownProbCount);
210
4.14k
211
4.14k
    std::replace_if(Begin, End,
212
4.14k
                    [](const BranchProbability &BP) { return BP.isUnknown(); },
213
4.14k
                    ProbForUnknown);
214
4.14k
215
4.14k
    if (Sum <= BranchProbability::getDenominator())
216
4.14k
      return;
217
884k
  }
218
884k
219
884k
  if (Sum == 0) {
220
290
    BranchProbability BP(1, std::distance(Begin, End));
221
290
    std::fill(Begin, End, BP);
222
290
    return;
223
290
  }
224
883k
225
2.66M
  
for (auto I = Begin; 883k
I != End;
++I1.77M
)
226
1.77M
    I->N = (I->N * uint64_t(D) + Sum / 2) / Sum;
227
883k
}
void llvm::BranchProbability::normalizeProbabilities<llvm::BranchProbability*>(llvm::BranchProbability*, llvm::BranchProbability*)
Line
Count
Source
189
49.6k
                                               ProbabilityIter End) {
190
49.6k
  if (Begin == End)
191
0
    return;
192
49.6k
193
49.6k
  unsigned UnknownProbCount = 0;
194
49.6k
  uint64_t Sum = std::accumulate(Begin, End, uint64_t(0),
195
49.6k
                                 [&](uint64_t S, const BranchProbability &BP) {
196
49.6k
                                   if (!BP.isUnknown())
197
49.6k
                                     return S + BP.N;
198
49.6k
                                   UnknownProbCount++;
199
49.6k
                                   return S;
200
49.6k
                                 });
201
49.6k
202
49.6k
  if (UnknownProbCount > 0) {
203
751
    BranchProbability ProbForUnknown = BranchProbability::getZero();
204
751
    // If the sum of all known probabilities is less than one, evenly distribute
205
751
    // the complement of sum to unknown probabilities. Otherwise, set unknown
206
751
    // probabilities to zeros and continue to normalize known probabilities.
207
751
    if (Sum < BranchProbability::getDenominator())
208
748
      ProbForUnknown = BranchProbability::getRaw(
209
748
          (BranchProbability::getDenominator() - Sum) / UnknownProbCount);
210
751
211
751
    std::replace_if(Begin, End,
212
751
                    [](const BranchProbability &BP) { return BP.isUnknown(); },
213
751
                    ProbForUnknown);
214
751
215
751
    if (Sum <= BranchProbability::getDenominator())
216
750
      return;
217
48.8k
  }
218
48.8k
219
48.8k
  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.8k
225
146k
  
for (auto I = Begin; 48.8k
I != End;
++I97.7k
)
226
97.7k
    I->N = (I->N * uint64_t(D) + Sum / 2) / Sum;
227
48.8k
}
228
229
}
230
231
#endif