LLVM  15.0.0git
BranchProbability.h
Go to the documentation of this file.
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 <numeric>
20 
21 namespace llvm {
22 
23 class raw_ostream;
24 
25 // This class represents Branch Probability as a non-negative fraction that is
26 // no greater than 1. It uses a fixed-point-like implementation, in which the
27 // denominator is always a constant value (here we use 1<<31 for maximum
28 // precision).
30  // Numerator
31  uint32_t N;
32 
33  // Denominator, which is a constant value.
34  static constexpr uint32_t D = 1u << 31;
35  static constexpr uint32_t UnknownN = UINT32_MAX;
36 
37  // Construct a BranchProbability with only numerator assuming the denominator
38  // is 1<<31. For internal use only.
39  explicit BranchProbability(uint32_t n) : N(n) {}
40 
41 public:
42  BranchProbability() : N(UnknownN) {}
43  BranchProbability(uint32_t Numerator, uint32_t Denominator);
44 
45  bool isZero() const { return N == 0; }
46  bool isUnknown() const { return N == UnknownN; }
47 
49  static BranchProbability getOne() { return BranchProbability(D); }
50  static BranchProbability getUnknown() { return BranchProbability(UnknownN); }
51  // Create a BranchProbability object with the given numerator and 1<<31
52  // as denominator.
54  // Create a BranchProbability object from 64-bit integers.
56  uint64_t Denominator);
57 
58  // Normalize given probabilties so that the sum of them becomes approximate
59  // one.
60  template <class ProbabilityIter>
61  static void normalizeProbabilities(ProbabilityIter Begin,
62  ProbabilityIter End);
63 
64  uint32_t getNumerator() const { return N; }
65  static uint32_t getDenominator() { return D; }
66 
67  // Return (1 - Probability).
68  BranchProbability getCompl() const { return BranchProbability(D - N); }
69 
70  raw_ostream &print(raw_ostream &OS) const;
71 
72  void dump() const;
73 
74  /// Scale a large integer.
75  ///
76  /// Scales \c Num. Guarantees full precision. Returns the floor of the
77  /// result.
78  ///
79  /// \return \c Num times \c this.
80  uint64_t scale(uint64_t Num) const;
81 
82  /// Scale a large integer by the inverse.
83  ///
84  /// Scales \c Num by the inverse of \c this. Guarantees full precision.
85  /// Returns the floor of the result.
86  ///
87  /// \return \c Num divided by \c this.
88  uint64_t scaleByInverse(uint64_t Num) const;
89 
91  assert(N != UnknownN && RHS.N != UnknownN &&
92  "Unknown probability cannot participate in arithmetics.");
93  // Saturate the result in case of overflow.
94  N = (uint64_t(N) + RHS.N > D) ? D : N + RHS.N;
95  return *this;
96  }
97 
99  assert(N != UnknownN && RHS.N != UnknownN &&
100  "Unknown probability cannot participate in arithmetics.");
101  // Saturate the result in case of underflow.
102  N = N < RHS.N ? 0 : N - RHS.N;
103  return *this;
104  }
105 
107  assert(N != UnknownN && RHS.N != UnknownN &&
108  "Unknown probability cannot participate in arithmetics.");
109  N = (static_cast<uint64_t>(N) * RHS.N + D / 2) / D;
110  return *this;
111  }
112 
114  assert(N != UnknownN &&
115  "Unknown probability cannot participate in arithmetics.");
116  N = (uint64_t(N) * RHS > D) ? D : N * RHS;
117  return *this;
118  }
119 
121  assert(N != UnknownN && RHS.N != UnknownN &&
122  "Unknown probability cannot participate in arithmetics.");
123  N = (static_cast<uint64_t>(N) * D + RHS.N / 2) / RHS.N;
124  return *this;
125  }
126 
128  assert(N != UnknownN &&
129  "Unknown probability cannot participate in arithmetics.");
130  assert(RHS > 0 && "The divider cannot be zero.");
131  N /= RHS;
132  return *this;
133  }
134 
136  BranchProbability Prob(*this);
137  Prob += RHS;
138  return Prob;
139  }
140 
142  BranchProbability Prob(*this);
143  Prob -= RHS;
144  return Prob;
145  }
146 
148  BranchProbability Prob(*this);
149  Prob *= RHS;
150  return Prob;
151  }
152 
154  BranchProbability Prob(*this);
155  Prob *= RHS;
156  return Prob;
157  }
158 
160  BranchProbability Prob(*this);
161  Prob /= RHS;
162  return Prob;
163  }
164 
166  BranchProbability Prob(*this);
167  Prob /= RHS;
168  return Prob;
169  }
170 
171  bool operator==(BranchProbability RHS) const { return N == RHS.N; }
172  bool operator!=(BranchProbability RHS) const { return !(*this == RHS); }
173 
175  assert(N != UnknownN && RHS.N != UnknownN &&
176  "Unknown probability cannot participate in comparisons.");
177  return N < RHS.N;
178  }
179 
181  assert(N != UnknownN && RHS.N != UnknownN &&
182  "Unknown probability cannot participate in comparisons.");
183  return RHS < *this;
184  }
185 
187  assert(N != UnknownN && RHS.N != UnknownN &&
188  "Unknown probability cannot participate in comparisons.");
189  return !(RHS < *this);
190  }
191 
193  assert(N != UnknownN && RHS.N != UnknownN &&
194  "Unknown probability cannot participate in comparisons.");
195  return !(*this < RHS);
196  }
197 };
198 
200  return Prob.print(OS);
201 }
202 
203 template <class ProbabilityIter>
204 void BranchProbability::normalizeProbabilities(ProbabilityIter Begin,
205  ProbabilityIter End) {
206  if (Begin == End)
207  return;
208 
209  unsigned UnknownProbCount = 0;
210  uint64_t Sum = std::accumulate(Begin, End, uint64_t(0),
211  [&](uint64_t S, const BranchProbability &BP) {
212  if (!BP.isUnknown())
213  return S + BP.N;
214  UnknownProbCount++;
215  return S;
216  });
217 
218  if (UnknownProbCount > 0) {
220  // If the sum of all known probabilities is less than one, evenly distribute
221  // the complement of sum to unknown probabilities. Otherwise, set unknown
222  // probabilities to zeros and continue to normalize known probabilities.
224  ProbForUnknown = BranchProbability::getRaw(
225  (BranchProbability::getDenominator() - Sum) / UnknownProbCount);
226 
227  std::replace_if(Begin, End,
228  [](const BranchProbability &BP) { return BP.isUnknown(); },
229  ProbForUnknown);
230 
232  return;
233  }
234 
235  if (Sum == 0) {
236  BranchProbability BP(1, std::distance(Begin, End));
237  std::fill(Begin, End, BP);
238  return;
239  }
240 
241  for (auto I = Begin; I != End; ++I)
242  I->N = (I->N * uint64_t(D) + Sum / 2) / Sum;
243 }
244 
245 }
246 
247 #endif
llvm::BranchProbability::scaleByInverse
uint64_t scaleByInverse(uint64_t Num) const
Scale a large integer by the inverse.
Definition: BranchProbability.cpp:111
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
llvm::BranchProbability::BranchProbability
BranchProbability()
Definition: BranchProbability.h:42
llvm::BranchProbability::getNumerator
uint32_t getNumerator() const
Definition: BranchProbability.h:64
llvm::BranchProbability::isZero
bool isZero() const
Definition: BranchProbability.h:45
llvm::BranchProbability::operator>
bool operator>(BranchProbability RHS) const
Definition: BranchProbability.h:180
llvm::BranchProbability::getZero
static BranchProbability getZero()
Definition: BranchProbability.h:48
llvm::BranchProbability::operator-
BranchProbability operator-(BranchProbability RHS) const
Definition: BranchProbability.h:141
llvm::BranchProbability::getBranchProbability
static BranchProbability getBranchProbability(uint64_t Numerator, uint64_t Denominator)
Definition: BranchProbability.cpp:53
RHS
Value * RHS
Definition: X86PartialReduction.cpp:76
llvm::BranchProbability::operator<
bool operator<(BranchProbability RHS) const
Definition: BranchProbability.h:174
llvm::BranchProbability::print
raw_ostream & print(raw_ostream &OS) const
Definition: BranchProbability.cpp:25
llvm::BranchProbability::scale
uint64_t scale(uint64_t Num) const
Scale a large integer.
Definition: BranchProbability.cpp:107
llvm::BranchProbability::operator*=
BranchProbability & operator*=(BranchProbability RHS)
Definition: BranchProbability.h:106
llvm::BranchProbability::getDenominator
static uint32_t getDenominator()
Definition: BranchProbability.h:65
llvm::BranchProbability::operator*=
BranchProbability & operator*=(uint32_t RHS)
Definition: BranchProbability.h:113
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:54
llvm::BranchProbability::operator==
bool operator==(BranchProbability RHS) const
Definition: BranchProbability.h:171
llvm::operator<<
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
Definition: APFixedPoint.h:230
llvm::BranchProbability::operator+=
BranchProbability & operator+=(BranchProbability RHS)
Definition: BranchProbability.h:90
llvm::BranchProbability::operator!=
bool operator!=(BranchProbability RHS) const
Definition: BranchProbability.h:172
llvm::BranchProbability::getUnknown
static BranchProbability getUnknown()
Definition: BranchProbability.h:50
llvm::BranchProbability::dump
void dump() const
Definition: BranchProbability.cpp:37
uint64_t
llvm::BranchProbability::operator>=
bool operator>=(BranchProbability RHS) const
Definition: BranchProbability.h:192
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::BranchProbability::operator/=
BranchProbability & operator/=(uint32_t RHS)
Definition: BranchProbability.h:127
llvm::BranchProbability::isUnknown
bool isUnknown() const
Definition: BranchProbability.h:46
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::BranchProbability::operator*
BranchProbability operator*(uint32_t RHS) const
Definition: BranchProbability.h:153
llvm::BranchProbability::operator/
BranchProbability operator/(BranchProbability RHS) const
Definition: BranchProbability.h:159
llvm::BranchProbability::getOne
static BranchProbability getOne()
Definition: BranchProbability.h:49
uint32_t
llvm::BranchProbability
Definition: BranchProbability.h:29
S
add sub stmia L5 ldr r0 bl L_printf $stub Instead of a and a wouldn t it be better to do three moves *Return an aggregate type is even return S
Definition: README.txt:210
llvm::BranchProbability::operator/
BranchProbability operator/(uint32_t RHS) const
Definition: BranchProbability.h:165
llvm::BranchProbability::getCompl
BranchProbability getCompl() const
Definition: BranchProbability.h:68
llvm::BranchProbability::getRaw
static BranchProbability getRaw(uint32_t N)
Definition: BranchProbability.h:53
llvm::BranchProbability::normalizeProbabilities
static void normalizeProbabilities(ProbabilityIter Begin, ProbabilityIter End)
Definition: BranchProbability.h:204
N
#define N
DataTypes.h
n
The same transformation can work with an even modulo with the addition of a and shrink the compare RHS by the same amount Unless the target supports that transformation probably isn t worthwhile The transformation can also easily be made to work with non zero equality for n
Definition: README.txt:685
llvm::BranchProbability::operator+
BranchProbability operator+(BranchProbability RHS) const
Definition: BranchProbability.h:135
llvm::BranchProbability::operator/=
BranchProbability & operator/=(BranchProbability RHS)
Definition: BranchProbability.h:120
llvm::BranchProbability::operator-=
BranchProbability & operator-=(BranchProbability RHS)
Definition: BranchProbability.h:98
llvm::BranchProbability::operator*
BranchProbability operator*(BranchProbability RHS) const
Definition: BranchProbability.h:147
llvm::BranchProbability::operator<=
bool operator<=(BranchProbability RHS) const
Definition: BranchProbability.h:186