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 <cassert>
  19
  20 namespace llvm {
  21
  22 class raw_ostream;
  23
  24 // This class represents Branch Probability as a non-negative fraction that is
  25 // no greater than 1. It uses a fixed-point-like implementation, in which the
  26 // denominator is always a constant value (here we use 1<<31 for maximum
  27 // precision).
  28 class BranchProbability {
  29   // Numerator
  30   uint32_t N;
  31
  32   // Denominator, which is a constant value.
  33   static const uint32_t D = 1u << 31;
  34
  35   // Construct a BranchProbability with only numerator assuming the denominator
  36   // is 1<<31. For internal use only.
  37   explicit BranchProbability(uint32_t n) : N(n) {}
  38
  39 public:
  40   BranchProbability() : N(0) {}
  41   BranchProbability(uint32_t Numerator, uint32_t Denominator);
  42
  43   bool isZero() const { return N == 0; }
  44
  45   static BranchProbability getZero() { return BranchProbability(0); }
  46   static BranchProbability getOne() { return BranchProbability(D); }
  47   // Create a BranchProbability object with the given numerator and 1<<31
  48   // as denominator.
  49   static BranchProbability getRaw(uint32_t N) { return BranchProbability(N); }
  50
  51   // Normalize given probabilties so that the sum of them becomes approximate
  52   // one.
  53   template <class ProbabilityList>
  54   static void normalizeProbabilities(ProbabilityList &Probs);
  55
  56   uint32_t getNumerator() const { return N; }
  57   static uint32_t getDenominator() { return D; }
  58
  59   // Return (1 - Probability).
  60   BranchProbability getCompl() const { return BranchProbability(D - N); }
  61
  62   raw_ostream &print(raw_ostream &OS) const;
  63
  64   void dump() const;
  65
  66   /// \brief Scale a large integer.
  67   ///
  68   /// Scales \c Num.  Guarantees full precision.  Returns the floor of the
  69   /// result.
  70   ///
  71   /// \return \c Num times \c this.
  72   uint64_t scale(uint64_t Num) const;
  73
  74   /// \brief Scale a large integer by the inverse.
  75   ///
  76   /// Scales \c Num by the inverse of \c this.  Guarantees full precision.
  77   /// Returns the floor of the result.
  78   ///
  79   /// \return \c Num divided by \c this.
  80   uint64_t scaleByInverse(uint64_t Num) const;
  81
  82   BranchProbability &operator+=(BranchProbability RHS) {
  83     assert(N <= D - RHS.N &&
  84            "The sum of branch probabilities should not exceed one!");
  85     N += RHS.N;
  86     return *this;
  87   }
  88
  89   BranchProbability &operator-=(BranchProbability RHS) {
  90     assert(N >= RHS.N &&
  91            "Can only subtract a smaller probability from a larger one!");
  92     N -= RHS.N;
  93     return *this;
  94   }
  95
  96   BranchProbability &operator*=(BranchProbability RHS) {
  97     N = (static_cast<uint64_t>(N) * RHS.N + D / 2) / D;
  98     return *this;
  99   }
 100
 101   BranchProbability operator+(BranchProbability RHS) const {
 102     BranchProbability Prob(*this);
 103     return Prob += RHS;
 104   }
 105
 106   BranchProbability operator-(BranchProbability RHS) const {
 107     BranchProbability Prob(*this);
 108     return Prob -= RHS;
 109   }
 110
 111   BranchProbability operator*(BranchProbability RHS) const {
 112     BranchProbability Prob(*this);
 113     return Prob *= RHS;
 114   }
 115
 116   bool operator==(BranchProbability RHS) const { return N == RHS.N; }
 117   bool operator!=(BranchProbability RHS) const { return !(*this == RHS); }
 118   bool operator<(BranchProbability RHS) const { return N < RHS.N; }
 119   bool operator>(BranchProbability RHS) const { return RHS < *this; }
 120   bool operator<=(BranchProbability RHS) const { return !(RHS < *this); }
 121   bool operator>=(BranchProbability RHS) const { return !(*this < RHS); }
 122 };
 123
 124 inline raw_ostream &operator<<(raw_ostream &OS, BranchProbability Prob) {
 125   return Prob.print(OS);
 126 }
 127
 128 template <class ProbabilityList>
 129 void BranchProbability::normalizeProbabilities(ProbabilityList &Probs) {
 130   uint64_t Sum = 0;
 131   for (auto Prob : Probs)
 132     Sum += Prob.N;
 133   assert(Sum > 0);
 134   for (auto &Prob : Probs)
 135     Prob.N = (Prob.N * uint64_t(D) + Sum / 2) / Sum;
 136 }
 137
 138 }
 139
 140 #endif