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(0) {}
  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
  57   // Normalize given probabilties so that the sum of them becomes approximate
  58   // one.
  59   template <class ProbabilityList>
  60   static void normalizeProbabilities(ProbabilityList &Probs);
  61
  62   // Normalize a list of weights by scaling them down so that the sum of them
  63   // doesn't exceed UINT32_MAX.
  64   template <class WeightListIter>
  65   static void normalizeEdgeWeights(WeightListIter Begin, WeightListIter End);
  66
  67   uint32_t getNumerator() const { return N; }
  68   static uint32_t getDenominator() { return D; }
  69
  70   // Return (1 - Probability).
  71   BranchProbability getCompl() const { return BranchProbability(D - N); }
  72
  73   raw_ostream &print(raw_ostream &OS) const;
  74
  75   void dump() const;
  76
  77   /// \brief Scale a large integer.
  78   ///
  79   /// Scales \c Num.  Guarantees full precision.  Returns the floor of the
  80   /// result.
  81   ///
  82   /// \return \c Num times \c this.
  83   uint64_t scale(uint64_t Num) const;
  84
  85   /// \brief Scale a large integer by the inverse.
  86   ///
  87   /// Scales \c Num by the inverse of \c this.  Guarantees full precision.
  88   /// Returns the floor of the result.
  89   ///
  90   /// \return \c Num divided by \c this.
  91   uint64_t scaleByInverse(uint64_t Num) const;
  92
  93   BranchProbability &operator+=(BranchProbability RHS) {
  94     assert(N <= D - RHS.N &&
  95            "The sum of branch probabilities should not exceed one!");
  96     N += RHS.N;
  97     return *this;
  98   }
  99
 100   BranchProbability &operator-=(BranchProbability RHS) {
 101     assert(N >= RHS.N &&
 102            "Can only subtract a smaller probability from a larger one!");
 103     N -= RHS.N;
 104     return *this;
 105   }
 106
 107   BranchProbability &operator*=(BranchProbability RHS) {
 108     N = (static_cast<uint64_t>(N) * RHS.N + D / 2) / D;
 109     return *this;
 110   }
 111
 112   BranchProbability operator+(BranchProbability RHS) const {
 113     BranchProbability Prob(*this);
 114     return Prob += RHS;
 115   }
 116
 117   BranchProbability operator-(BranchProbability RHS) const {
 118     BranchProbability Prob(*this);
 119     return Prob -= RHS;
 120   }
 121
 122   BranchProbability operator*(BranchProbability RHS) const {
 123     BranchProbability Prob(*this);
 124     return Prob *= RHS;
 125   }
 126
 127   bool operator==(BranchProbability RHS) const { return N == RHS.N; }
 128   bool operator!=(BranchProbability RHS) const { return !(*this == RHS); }
 129   bool operator<(BranchProbability RHS) const { return N < RHS.N; }
 130   bool operator>(BranchProbability RHS) const { return RHS < *this; }
 131   bool operator<=(BranchProbability RHS) const { return !(RHS < *this); }
 132   bool operator>=(BranchProbability RHS) const { return !(*this < RHS); }
 133 };
 134
 135 inline raw_ostream &operator<<(raw_ostream &OS, BranchProbability Prob) {
 136   return Prob.print(OS);
 137 }
 138
 139 inline BranchProbability operator/(BranchProbability LHS, uint32_t RHS) {
 140   return BranchProbability::getRaw(LHS.getNumerator() / RHS);
 141 }
 142
 143 template <class ProbabilityList>
 144 void BranchProbability::normalizeProbabilities(ProbabilityList &Probs) {
 145   uint64_t Sum = 0;
 146   for (auto Prob : Probs)
 147     Sum += Prob.N;
 148   assert(Sum > 0);
 149   for (auto &Prob : Probs)
 150     Prob.N = (Prob.N * uint64_t(D) + Sum / 2) / Sum;
 151 }
 152
 153 template <class WeightListIter>
 154 void BranchProbability::normalizeEdgeWeights(WeightListIter Begin,
 155                                              WeightListIter End) {
 156   // First we compute the sum with 64-bits of precision.
 157   uint64_t Sum = std::accumulate(Begin, End, uint64_t(0));
 158
 159   if (Sum > UINT32_MAX) {
 160     // Compute the scale necessary to cause the weights to fit, and re-sum with
 161     // that scale applied.
 162     assert(Sum / UINT32_MAX < UINT32_MAX &&
 163            "The sum of weights exceeds UINT32_MAX^2!");
 164     uint32_t Scale = Sum / UINT32_MAX + 1;
 165     for (auto I = Begin; I != End; ++I)
 166       *I /= Scale;
 167     Sum = std::accumulate(Begin, End, uint64_t(0));
 168   }
 169
 170   // Eliminate zero weights.
 171   auto ZeroWeightNum = std::count(Begin, End, 0u);
 172   if (ZeroWeightNum > 0) {
 173     // If all weights are zeros, replace them by 1.
 174     if (Sum == 0)
 175       std::fill(Begin, End, 1u);
 176     else {
 177       // We are converting zeros into ones, and here we need to make sure that
 178       // after this the sum won't exceed UINT32_MAX.
 179       if (Sum + ZeroWeightNum > UINT32_MAX) {
 180         for (auto I = Begin; I != End; ++I)
 181           *I /= 2;
 182         ZeroWeightNum = std::count(Begin, End, 0u);
 183         Sum = std::accumulate(Begin, End, uint64_t(0));
 184       }
 185       // Scale up non-zero weights and turn zero weights into ones.
 186       uint64_t ScalingFactor = (UINT32_MAX - ZeroWeightNum) / Sum;
 187       assert(ScalingFactor >= 1);
 188       if (ScalingFactor > 1)
 189         for (auto I = Begin; I != End; ++I)
 190           *I *= ScalingFactor;
 191       std::replace(Begin, End, 0u, 1u);
 192     }
 193   }
 194 }
 195
 196 }
 197
 198 #endif