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