include/llvm/Support/BranchProbability.h

   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 class 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
  43 public:
  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   // Normalize a list of weights by scaling them down so that the sum of them
  67   // doesn't exceed UINT32_MAX.
  68   template <class WeightListIter>
  69   static void normalizeEdgeWeights(WeightListIter Begin, WeightListIter End);
  70
  71   uint32_t getNumerator() const { return N; }
  72   static uint32_t getDenominator() { return D; }
  73
  74   // Return (1 - Probability).
  75   BranchProbability getCompl() const { return BranchProbability(D - N); }
  76
  77   raw_ostream &print(raw_ostream &OS) const;
  78
  79   void dump() const;
  80
  81   /// \brief Scale a large integer.
  82   ///
  83   /// Scales \c Num.  Guarantees full precision.  Returns the floor of the
  84   /// result.
  85   ///
  86   /// \return \c Num times \c this.
  87   uint64_t scale(uint64_t Num) const;
  88
  89   /// \brief Scale a large integer by the inverse.
  90   ///
  91   /// Scales \c Num by the inverse of \c this.  Guarantees full precision.
  92   /// Returns the floor of the result.
  93   ///
  94   /// \return \c Num divided by \c this.
  95   uint64_t scaleByInverse(uint64_t Num) const;
  96
  97   BranchProbability &operator+=(BranchProbability RHS) {
  98     assert(N != UnknownN && RHS.N != UnknownN &&
  99            "Unknown probability cannot participate in arithmetics.");
 100     // Saturate the result in case of overflow.
 101     N = (uint64_t(N) + RHS.N > D) ? D : N + RHS.N;
 102     return *this;
 103   }
 104
 105   BranchProbability &operator-=(BranchProbability RHS) {
 106     assert(N != UnknownN && RHS.N != UnknownN &&
 107            "Unknown probability cannot participate in arithmetics.");
 108     // Saturate the result in case of underflow.
 109     N = N < RHS.N ? 0 : N - RHS.N;
 110     return *this;
 111   }
 112
 113   BranchProbability &operator*=(BranchProbability RHS) {
 114     assert(N != UnknownN && RHS.N != UnknownN &&
 115            "Unknown probability cannot participate in arithmetics.");
 116     N = (static_cast<uint64_t>(N) * RHS.N + D / 2) / D;
 117     return *this;
 118   }
 119
 120   BranchProbability operator+(BranchProbability RHS) const {
 121     BranchProbability Prob(*this);
 122     return Prob += RHS;
 123   }
 124
 125   BranchProbability operator-(BranchProbability RHS) const {
 126     BranchProbability Prob(*this);
 127     return Prob -= RHS;
 128   }
 129
 130   BranchProbability operator*(BranchProbability RHS) const {
 131     BranchProbability Prob(*this);
 132     return Prob *= RHS;
 133   }
 134
 135   bool operator==(BranchProbability RHS) const { return N == RHS.N; }
 136   bool operator!=(BranchProbability RHS) const { return !(*this == RHS); }
 137
 138   bool operator<(BranchProbability RHS) const {
 139     assert(N != UnknownN && RHS.N != UnknownN &&
 140            "Unknown probability cannot participate in comparisons.");
 141     return N < RHS.N;
 142   }
 143
 144   bool operator>(BranchProbability RHS) const {
 145     assert(N != UnknownN && RHS.N != UnknownN &&
 146            "Unknown probability cannot participate in comparisons.");
 147     return RHS < *this;
 148   }
 149
 150   bool operator<=(BranchProbability RHS) const {
 151     assert(N != UnknownN && RHS.N != UnknownN &&
 152            "Unknown probability cannot participate in comparisons.");
 153     return !(RHS < *this);
 154   }
 155
 156   bool operator>=(BranchProbability RHS) const {
 157     assert(N != UnknownN && RHS.N != UnknownN &&
 158            "Unknown probability cannot participate in comparisons.");
 159     return !(*this < RHS);
 160   }
 161 };
 162
 163 inline raw_ostream &operator<<(raw_ostream &OS, BranchProbability Prob) {
 164   return Prob.print(OS);
 165 }
 166
 167 inline BranchProbability operator/(BranchProbability LHS, uint32_t RHS) {
 168   assert(LHS != BranchProbability::getUnknown() &&
 169          "Unknown probability cannot participate in arithmetics.");
 170   return BranchProbability::getRaw(LHS.getNumerator() / RHS);
 171 }
 172
 173 template <class ProbabilityIter>
 174 void BranchProbability::normalizeProbabilities(ProbabilityIter Begin,
 175                                                ProbabilityIter End) {
 176   if (Begin == End)
 177     return;
 178
 179   auto UnknownProbCount =
 180       std::count(Begin, End, BranchProbability::getUnknown());
 181   assert((UnknownProbCount == 0 ||
 182           UnknownProbCount == std::distance(Begin, End)) &&
 183          "Cannot normalize probabilities with known and unknown ones.");
 184   (void)UnknownProbCount;
 185
 186   uint64_t Sum = std::accumulate(
 187       Begin, End, uint64_t(0),
 188       [](uint64_t S, const BranchProbability &BP) { return S + BP.N; });
 189
 190   if (Sum == 0) {
 191     BranchProbability BP(1, std::distance(Begin, End));
 192     std::fill(Begin, End, BP);
 193     return;
 194   }
 195
 196   for (auto I = Begin; I != End; ++I)
 197     I->N = (I->N * uint64_t(D) + Sum / 2) / Sum;
 198 }
 199
 200 template <class WeightListIter>
 201 void BranchProbability::normalizeEdgeWeights(WeightListIter Begin,
 202                                              WeightListIter End) {
 203   // First we compute the sum with 64-bits of precision.
 204   uint64_t Sum = std::accumulate(Begin, End, uint64_t(0));
 205
 206   if (Sum > UINT32_MAX) {
 207     // Compute the scale necessary to cause the weights to fit, and re-sum with
 208     // that scale applied.
 209     assert(Sum / UINT32_MAX < UINT32_MAX &&
 210            "The sum of weights exceeds UINT32_MAX^2!");
 211     uint32_t Scale = Sum / UINT32_MAX + 1;
 212     for (auto I = Begin; I != End; ++I)
 213       *I /= Scale;
 214     Sum = std::accumulate(Begin, End, uint64_t(0));
 215   }
 216
 217   // Eliminate zero weights.
 218   auto ZeroWeightNum = std::count(Begin, End, 0u);
 219   if (ZeroWeightNum > 0) {
 220     // If all weights are zeros, replace them by 1.
 221     if (Sum == 0)
 222       std::fill(Begin, End, 1u);
 223     else {
 224       // We are converting zeros into ones, and here we need to make sure that
 225       // after this the sum won't exceed UINT32_MAX.
 226       if (Sum + ZeroWeightNum > UINT32_MAX) {
 227         for (auto I = Begin; I != End; ++I)
 228           *I /= 2;
 229         ZeroWeightNum = std::count(Begin, End, 0u);
 230         Sum = std::accumulate(Begin, End, uint64_t(0));
 231       }
 232       // Scale up non-zero weights and turn zero weights into ones.
 233       uint64_t ScalingFactor = (UINT32_MAX - ZeroWeightNum) / Sum;
 234       assert(ScalingFactor >= 1);
 235       if (ScalingFactor > 1)
 236         for (auto I = Begin; I != End; ++I)
 237           *I *= ScalingFactor;
 238       std::replace(Begin, End, 0u, 1u);
 239     }
 240   }
 241 }
 242
 243 }
 244
 245 #endif