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
23namespace llvm {
24
25class 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).
31class 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  explicit BranchProbability(uint32_t n) : N(n) {}
42
43public:
44  BranchProbability() : N(UnknownN) {}
45  BranchProbability(uint32_t Numerator, uint32_t Denominator);
46
47  bool isZero() const { return N == 0; }
48  bool isUnknown() const { return N == UnknownN; }
49
50  static BranchProbability getZero() { return BranchProbability(0); }
51  static BranchProbability getOne() { return BranchProbability(D); }
52  static BranchProbability getUnknown() { return BranchProbability(UnknownN); }
53  // Create a BranchProbability object with the given numerator and 1<<31
54  // as denominator.
55  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  uint32_t getNumerator() const { return N; }
67  static uint32_t getDenominator() { return D; }
68
69  // Return (1 - Probability).
70  BranchProbability getCompl() const { return BranchProbability(D - N); }
71
72  raw_ostream &print(raw_ostream &OS) const;
73
74  void dump() const;
75
76  /// \brief 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  /// \brief 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  BranchProbability &operator+=(BranchProbability RHS) {
93    assert(N != UnknownN && RHS.N != UnknownN &&
94           "Unknown probability cannot participate in arithmetics.");
95    // Saturate the result in case of overflow.
96    N = (uint64_t(N) + RHS.N > D) ? D : N + RHS.N;
97    return *this;
98  }
99
100  BranchProbability &operator-=(BranchProbability RHS) {
101    assert(N != UnknownN && RHS.N != UnknownN &&
102           "Unknown probability cannot participate in arithmetics.");
103    // Saturate the result in case of underflow.
104    N = N < RHS.N ? 0 : N - RHS.N;
105    return *this;
106  }
107
108  BranchProbability &operator*=(BranchProbability RHS) {
109    assert(N != UnknownN && RHS.N != UnknownN &&
110           "Unknown probability cannot participate in arithmetics.");
111    N = (static_cast<uint64_t>(N) * RHS.N + D / 2) / D;
112    return *this;
113  }
114
115  BranchProbability &operator/=(uint32_t RHS) {
116    assert(N != UnknownN &&
117           "Unknown probability cannot participate in arithmetics.");
118    assert(RHS > 0 && "The divider cannot be zero.");
119    N /= RHS;
120    return *this;
121  }
122
123  BranchProbability operator+(BranchProbability RHS) const {
124    BranchProbability Prob(*this);
125    return Prob += RHS;
126  }
127
128  BranchProbability operator-(BranchProbability RHS) const {
129    BranchProbability Prob(*this);
130    return Prob -= RHS;
131  }
132
133  BranchProbability operator*(BranchProbability RHS) const {
134    BranchProbability Prob(*this);
135    return Prob *= RHS;
136  }
137
138  BranchProbability operator/(uint32_t RHS) const {
139    BranchProbability Prob(*this);
140    return Prob /= RHS;
141  }
142
143  bool operator==(BranchProbability RHS) const { return N == RHS.N; }
144  bool operator!=(BranchProbability RHS) const { return !(*this == RHS); }
145
146  bool operator<(BranchProbability RHS) const {
147    assert(N != UnknownN && RHS.N != UnknownN &&
148           "Unknown probability cannot participate in comparisons.");
149    return N < RHS.N;
150  }
151
152  bool operator>(BranchProbability RHS) const {
153    assert(N != UnknownN && RHS.N != UnknownN &&
154           "Unknown probability cannot participate in comparisons.");
155    return RHS < *this;
156  }
157
158  bool operator<=(BranchProbability RHS) const {
159    assert(N != UnknownN && RHS.N != UnknownN &&
160           "Unknown probability cannot participate in comparisons.");
161    return !(RHS < *this);
162  }
163
164  bool operator>=(BranchProbability RHS) const {
165    assert(N != UnknownN && RHS.N != UnknownN &&
166           "Unknown probability cannot participate in comparisons.");
167    return !(*this < RHS);
168  }
169};
170
171inline raw_ostream &operator<<(raw_ostream &OS, BranchProbability Prob) {
172  return Prob.print(OS);
173}
174
175template <class ProbabilityIter>
176void BranchProbability::normalizeProbabilities(ProbabilityIter Begin,
177                                               ProbabilityIter End) {
178  if (Begin == End)
179    return;
180
181  unsigned UnknownProbCount = 0;
182  uint64_t Sum = std::accumulate(Begin, End, uint64_t(0),
183                                 [&](uint64_t S, const BranchProbability &BP) {
184                                   if (!BP.isUnknown())
185                                     return S + BP.N;
186                                   UnknownProbCount++;
187                                   return S;
188                                 });
189
190  if (UnknownProbCount > 0) {
191    BranchProbability ProbForUnknown = BranchProbability::getZero();
192    // If the sum of all known probabilities is less than one, evenly distribute
193    // the complement of sum to unknown probabilities. Otherwise, set unknown
194    // probabilities to zeros and continue to normalize known probabilities.
195    if (Sum < BranchProbability::getDenominator())
196      ProbForUnknown = BranchProbability::getRaw(
197          (BranchProbability::getDenominator() - Sum) / UnknownProbCount);
198
199    std::replace_if(Begin, End,
200                    [](const BranchProbability &BP) { return BP.isUnknown(); },
201                    ProbForUnknown);
202
203    if (Sum <= BranchProbability::getDenominator())
204      return;
205  }
206
207  if (Sum == 0) {
208    BranchProbability BP(1, std::distance(Begin, End));
209    std::fill(Begin, End, BP);
210    return;
211  }
212
213  for (auto I = Begin; I != End; ++I)
214    I->N = (I->N * uint64_t(D) + Sum / 2) / Sum;
215}
216
217}
218
219#endif
220