Coverage Report

Created: 2019-02-20 00:17

/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
// 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
0
class BranchProbability {
Unexecuted instantiation: llvm::BranchProbability::operator=(llvm::BranchProbability const&)
Unexecuted instantiation: llvm::BranchProbability::operator=(llvm::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
45.7M
  explicit BranchProbability(uint32_t n) : N(n) {}
41
42
public:
43
16.8M
  BranchProbability() : N(UnknownN) {}
44
  BranchProbability(uint32_t Numerator, uint32_t Denominator);
45
46
18
  bool isZero() const { return N == 0; }
47
46.7M
  bool isUnknown() const { return N == UnknownN; }
48
49
17.7M
  static BranchProbability getZero() { return BranchProbability(0); }
50
4.44M
  static BranchProbability getOne() { return BranchProbability(D); }
51
4.91M
  static BranchProbability getUnknown() { return BranchProbability(UnknownN); }
52
  // Create a BranchProbability object with the given numerator and 1<<31
53
  // as denominator.
54
108k
  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
41.9M
  uint32_t getNumerator() const { return N; }
66
39.9k
  static uint32_t getDenominator() { return D; }
67
68
  // Return (1 - Probability).
69
18.5M
  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.36M
  BranchProbability &operator+=(BranchProbability RHS) {
92
1.36M
    assert(N != UnknownN && RHS.N != UnknownN &&
93
1.36M
           "Unknown probability cannot participate in arithmetics.");
94
1.36M
    // Saturate the result in case of overflow.
95
1.36M
    N = (uint64_t(N) + RHS.N > D) ? 
D5.85k
:
N + RHS.N1.35M
;
96
1.36M
    return *this;
97
1.36M
  }
98
99
1.41M
  BranchProbability &operator-=(BranchProbability RHS) {
100
1.41M
    assert(N != UnknownN && RHS.N != UnknownN &&
101
1.41M
           "Unknown probability cannot participate in arithmetics.");
102
1.41M
    // Saturate the result in case of underflow.
103
1.41M
    N = N < RHS.N ? 
021
:
N - RHS.N1.41M
;
104
1.41M
    return *this;
105
1.41M
  }
106
107
7.47k
  BranchProbability &operator*=(BranchProbability RHS) {
108
7.47k
    assert(N != UnknownN && RHS.N != UnknownN &&
109
7.47k
           "Unknown probability cannot participate in arithmetics.");
110
7.47k
    N = (static_cast<uint64_t>(N) * RHS.N + D / 2) / D;
111
7.47k
    return *this;
112
7.47k
  }
113
114
89.3k
  BranchProbability &operator*=(uint32_t RHS) {
115
89.3k
    assert(N != UnknownN &&
116
89.3k
           "Unknown probability cannot participate in arithmetics.");
117
89.3k
    N = (uint64_t(N) * RHS > D) ? 
D4
:
N * RHS89.3k
;
118
89.3k
    return *this;
119
89.3k
  }
120
121
17.0M
  BranchProbability &operator/=(uint32_t RHS) {
122
17.0M
    assert(N != UnknownN &&
123
17.0M
           "Unknown probability cannot participate in arithmetics.");
124
17.0M
    assert(RHS > 0 && "The divider cannot be zero.");
125
17.0M
    N /= RHS;
126
17.0M
    return *this;
127
17.0M
  }
128
129
42.9k
  BranchProbability operator+(BranchProbability RHS) const {
130
42.9k
    BranchProbability Prob(*this);
131
42.9k
    return Prob += RHS;
132
42.9k
  }
133
134
307k
  BranchProbability operator-(BranchProbability RHS) const {
135
307k
    BranchProbability Prob(*this);
136
307k
    return Prob -= RHS;
137
307k
  }
138
139
7.42k
  BranchProbability operator*(BranchProbability RHS) const {
140
7.42k
    BranchProbability Prob(*this);
141
7.42k
    return Prob *= RHS;
142
7.42k
  }
143
144
89.3k
  BranchProbability operator*(uint32_t RHS) const {
145
89.3k
    BranchProbability Prob(*this);
146
89.3k
    return Prob *= RHS;
147
89.3k
  }
148
149
17.0M
  BranchProbability operator/(uint32_t RHS) const {
150
17.0M
    BranchProbability Prob(*this);
151
17.0M
    return Prob /= RHS;
152
17.0M
  }
153
154
17.8k
  bool operator==(BranchProbability RHS) const { return N == RHS.N; }
155
14.7k
  bool operator!=(BranchProbability RHS) const { return !(*this == RHS); }
156
157
2.14M
  bool operator<(BranchProbability RHS) const {
158
2.14M
    assert(N != UnknownN && RHS.N != UnknownN &&
159
2.14M
           "Unknown probability cannot participate in comparisons.");
160
2.14M
    return N < RHS.N;
161
2.14M
  }
162
163
443k
  bool operator>(BranchProbability RHS) const {
164
443k
    assert(N != UnknownN && RHS.N != UnknownN &&
165
443k
           "Unknown probability cannot participate in comparisons.");
166
443k
    return RHS < *this;
167
443k
  }
168
169
205k
  bool operator<=(BranchProbability RHS) const {
170
205k
    assert(N != UnknownN && RHS.N != UnknownN &&
171
205k
           "Unknown probability cannot participate in comparisons.");
172
205k
    return !(RHS < *this);
173
205k
  }
174
175
440k
  bool operator>=(BranchProbability RHS) const {
176
440k
    assert(N != UnknownN && RHS.N != UnknownN &&
177
440k
           "Unknown probability cannot participate in comparisons.");
178
440k
    return !(*this < RHS);
179
440k
  }
180
};
181
182
939
inline raw_ostream &operator<<(raw_ostream &OS, BranchProbability Prob) {
183
939
  return Prob.print(OS);
184
939
}
185
186
template <class ProbabilityIter>
187
void BranchProbability::normalizeProbabilities(ProbabilityIter Begin,
188
761k
                                               ProbabilityIter End) {
189
761k
  if (Begin == End)
190
25.4k
    return;
191
736k
192
736k
  unsigned UnknownProbCount = 0;
193
736k
  uint64_t Sum = std::accumulate(Begin, End, uint64_t(0),
194
1.47M
                                 [&](uint64_t S, const BranchProbability &BP) {
195
1.47M
                                   if (!BP.isUnknown())
196
1.46M
                                     return S + BP.N;
197
7.52k
                                   UnknownProbCount++;
198
7.52k
                                   return S;
199
7.52k
                                 });
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
194
1.39M
                                 [&](uint64_t S, const BranchProbability &BP) {
195
1.39M
                                   if (!BP.isUnknown())
196
1.38M
                                     return S + BP.N;
197
5.57k
                                   UnknownProbCount++;
198
5.57k
                                   return S;
199
5.57k
                                 });
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
194
81.3k
                                 [&](uint64_t S, const BranchProbability &BP) {
195
81.3k
                                   if (!BP.isUnknown())
196
79.4k
                                     return S + BP.N;
197
1.95k
                                   UnknownProbCount++;
198
1.95k
                                   return S;
199
1.95k
                                 });
200
736k
201
736k
  if (UnknownProbCount > 0) {
202
5.44k
    BranchProbability ProbForUnknown = BranchProbability::getZero();
203
5.44k
    // If the sum of all known probabilities is less than one, evenly distribute
204
5.44k
    // the complement of sum to unknown probabilities. Otherwise, set unknown
205
5.44k
    // probabilities to zeros and continue to normalize known probabilities.
206
5.44k
    if (Sum < BranchProbability::getDenominator())
207
5.44k
      ProbForUnknown = BranchProbability::getRaw(
208
5.44k
          (BranchProbability::getDenominator() - Sum) / UnknownProbCount);
209
5.44k
210
5.44k
    std::replace_if(Begin, End,
211
7.54k
                    [](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
211
5.57k
                    [](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
211
1.96k
                    [](const BranchProbability &BP) { return BP.isUnknown(); },
212
5.44k
                    ProbForUnknown);
213
5.44k
214
5.44k
    if (Sum <= BranchProbability::getDenominator())
215
5.44k
      return;
216
730k
  }
217
730k
218
730k
  if (Sum == 0) {
219
426
    BranchProbability BP(1, std::distance(Begin, End));
220
426
    std::fill(Begin, End, BP);
221
426
    return;
222
426
  }
223
730k
224
2.19M
  
for (auto I = Begin; 730k
I != End;
++I1.46M
)
225
1.46M
    I->N = (I->N * uint64_t(D) + Sum / 2) / Sum;
226
730k
}
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
188
721k
                                               ProbabilityIter End) {
189
721k
  if (Begin == End)
190
25.4k
    return;
191
695k
192
695k
  unsigned UnknownProbCount = 0;
193
695k
  uint64_t Sum = std::accumulate(Begin, End, uint64_t(0),
194
695k
                                 [&](uint64_t S, const BranchProbability &BP) {
195
695k
                                   if (!BP.isUnknown())
196
695k
                                     return S + BP.N;
197
695k
                                   UnknownProbCount++;
198
695k
                                   return S;
199
695k
                                 });
200
695k
201
695k
  if (UnknownProbCount > 0) {
202
4.48k
    BranchProbability ProbForUnknown = BranchProbability::getZero();
203
4.48k
    // If the sum of all known probabilities is less than one, evenly distribute
204
4.48k
    // the complement of sum to unknown probabilities. Otherwise, set unknown
205
4.48k
    // probabilities to zeros and continue to normalize known probabilities.
206
4.48k
    if (Sum < BranchProbability::getDenominator())
207
4.48k
      ProbForUnknown = BranchProbability::getRaw(
208
4.48k
          (BranchProbability::getDenominator() - Sum) / UnknownProbCount);
209
4.48k
210
4.48k
    std::replace_if(Begin, End,
211
4.48k
                    [](const BranchProbability &BP) { return BP.isUnknown(); },
212
4.48k
                    ProbForUnknown);
213
4.48k
214
4.48k
    if (Sum <= BranchProbability::getDenominator())
215
4.48k
      return;
216
691k
  }
217
691k
218
691k
  if (Sum == 0) {
219
425
    BranchProbability BP(1, std::distance(Begin, End));
220
425
    std::fill(Begin, End, BP);
221
425
    return;
222
425
  }
223
690k
224
2.07M
  
for (auto I = Begin; 690k
I != End;
++I1.38M
)
225
1.38M
    I->N = (I->N * uint64_t(D) + Sum / 2) / Sum;
226
690k
}
void llvm::BranchProbability::normalizeProbabilities<llvm::BranchProbability*>(llvm::BranchProbability*, llvm::BranchProbability*)
Line
Count
Source
188
40.6k
                                               ProbabilityIter End) {
189
40.6k
  if (Begin == End)
190
0
    return;
191
40.6k
192
40.6k
  unsigned UnknownProbCount = 0;
193
40.6k
  uint64_t Sum = std::accumulate(Begin, End, uint64_t(0),
194
40.6k
                                 [&](uint64_t S, const BranchProbability &BP) {
195
40.6k
                                   if (!BP.isUnknown())
196
40.6k
                                     return S + BP.N;
197
40.6k
                                   UnknownProbCount++;
198
40.6k
                                   return S;
199
40.6k
                                 });
200
40.6k
201
40.6k
  if (UnknownProbCount > 0) {
202
959
    BranchProbability ProbForUnknown = BranchProbability::getZero();
203
959
    // If the sum of all known probabilities is less than one, evenly distribute
204
959
    // the complement of sum to unknown probabilities. Otherwise, set unknown
205
959
    // probabilities to zeros and continue to normalize known probabilities.
206
959
    if (Sum < BranchProbability::getDenominator())
207
956
      ProbForUnknown = BranchProbability::getRaw(
208
956
          (BranchProbability::getDenominator() - Sum) / UnknownProbCount);
209
959
210
959
    std::replace_if(Begin, End,
211
959
                    [](const BranchProbability &BP) { return BP.isUnknown(); },
212
959
                    ProbForUnknown);
213
959
214
959
    if (Sum <= BranchProbability::getDenominator())
215
958
      return;
216
39.6k
  }
217
39.6k
218
39.6k
  if (Sum == 0) {
219
1
    BranchProbability BP(1, std::distance(Begin, End));
220
1
    std::fill(Begin, End, BP);
221
1
    return;
222
1
  }
223
39.6k
224
119k
  
for (auto I = Begin; 39.6k
I != End;
++I79.4k
)
225
79.4k
    I->N = (I->N * uint64_t(D) + Sum / 2) / Sum;
226
39.6k
}
227
228
}
229
230
#endif