X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FSupport%2FBranchProbability.h;h=26bc888d1cabfb29c7a2b62cec086397925bd3ad;hb=35b01daadc4f50671fe7f5acbd975c7bdc7da0fb;hp=80da81b559721b6b3abcc8612767684d890a76a2;hpb=2ecdd724538d33af61685fb933f19624f2089ae4;p=oota-llvm.git diff --git a/include/llvm/Support/BranchProbability.h b/include/llvm/Support/BranchProbability.h index 80da81b5597..26bc888d1ca 100644 --- a/include/llvm/Support/BranchProbability.h +++ b/include/llvm/Support/BranchProbability.h @@ -15,37 +15,204 @@ #define LLVM_SUPPORT_BRANCHPROBABILITY_H #include "llvm/Support/DataTypes.h" +#include +#include +#include +#include namespace llvm { class raw_ostream; -// This class represents Branch Probability as a non-negative fraction. +// This class represents Branch Probability as a non-negative fraction that is +// no greater than 1. It uses a fixed-point-like implementation, in which the +// denominator is always a constant value (here we use 1<<31 for maximum +// precision). class BranchProbability { - // Numerator uint32_t N; - // Denominator - uint32_t D; + // Denominator, which is a constant value. + static const uint32_t D = 1u << 31; + static const uint32_t UnknownN = UINT32_MAX; + + // Construct a BranchProbability with only numerator assuming the denominator + // is 1<<31. For internal use only. + explicit BranchProbability(uint32_t n) : N(n) {} public: - BranchProbability(uint32_t n, uint32_t d); + BranchProbability() : N(UnknownN) {} + BranchProbability(uint32_t Numerator, uint32_t Denominator); + + bool isZero() const { return N == 0; } + bool isUnknown() const { return N == UnknownN; } + + static BranchProbability getZero() { return BranchProbability(0); } + static BranchProbability getOne() { return BranchProbability(D); } + static BranchProbability getUnknown() { return BranchProbability(UnknownN); } + // Create a BranchProbability object with the given numerator and 1<<31 + // as denominator. + static BranchProbability getRaw(uint32_t N) { return BranchProbability(N); } + // Create a BranchProbability object from 64-bit integers. + static BranchProbability getBranchProbability(uint64_t Numerator, + uint64_t Denominator); + + // Normalize given probabilties so that the sum of them becomes approximate + // one. + template + static void normalizeProbabilities(ProbabilityIter Begin, + ProbabilityIter End); uint32_t getNumerator() const { return N; } - uint32_t getDenominator() const { return D; } + static uint32_t getDenominator() { return D; } // Return (1 - Probability). - BranchProbability getCompl() { - return BranchProbability(D - N, D); - } + BranchProbability getCompl() const { return BranchProbability(D - N); } raw_ostream &print(raw_ostream &OS) const; void dump() const; + + /// \brief Scale a large integer. + /// + /// Scales \c Num. Guarantees full precision. Returns the floor of the + /// result. + /// + /// \return \c Num times \c this. + uint64_t scale(uint64_t Num) const; + + /// \brief Scale a large integer by the inverse. + /// + /// Scales \c Num by the inverse of \c this. Guarantees full precision. + /// Returns the floor of the result. + /// + /// \return \c Num divided by \c this. + uint64_t scaleByInverse(uint64_t Num) const; + + BranchProbability &operator+=(BranchProbability RHS) { + assert(N != UnknownN && RHS.N != UnknownN && + "Unknown probability cannot participate in arithmetics."); + // Saturate the result in case of overflow. + N = (uint64_t(N) + RHS.N > D) ? D : N + RHS.N; + return *this; + } + + BranchProbability &operator-=(BranchProbability RHS) { + assert(N != UnknownN && RHS.N != UnknownN && + "Unknown probability cannot participate in arithmetics."); + // Saturate the result in case of underflow. + N = N < RHS.N ? 0 : N - RHS.N; + return *this; + } + + BranchProbability &operator*=(BranchProbability RHS) { + assert(N != UnknownN && RHS.N != UnknownN && + "Unknown probability cannot participate in arithmetics."); + N = (static_cast(N) * RHS.N + D / 2) / D; + return *this; + } + + BranchProbability &operator/=(uint32_t RHS) { + assert(N != UnknownN && + "Unknown probability cannot participate in arithmetics."); + assert(RHS > 0 && "The divider cannot be zero."); + N /= RHS; + return *this; + } + + BranchProbability operator+(BranchProbability RHS) const { + BranchProbability Prob(*this); + return Prob += RHS; + } + + BranchProbability operator-(BranchProbability RHS) const { + BranchProbability Prob(*this); + return Prob -= RHS; + } + + BranchProbability operator*(BranchProbability RHS) const { + BranchProbability Prob(*this); + return Prob *= RHS; + } + + BranchProbability operator/(uint32_t RHS) const { + BranchProbability Prob(*this); + return Prob /= RHS; + } + + bool operator==(BranchProbability RHS) const { return N == RHS.N; } + bool operator!=(BranchProbability RHS) const { return !(*this == RHS); } + + bool operator<(BranchProbability RHS) const { + assert(N != UnknownN && RHS.N != UnknownN && + "Unknown probability cannot participate in comparisons."); + return N < RHS.N; + } + + bool operator>(BranchProbability RHS) const { + assert(N != UnknownN && RHS.N != UnknownN && + "Unknown probability cannot participate in comparisons."); + return RHS < *this; + } + + bool operator<=(BranchProbability RHS) const { + assert(N != UnknownN && RHS.N != UnknownN && + "Unknown probability cannot participate in comparisons."); + return !(RHS < *this); + } + + bool operator>=(BranchProbability RHS) const { + assert(N != UnknownN && RHS.N != UnknownN && + "Unknown probability cannot participate in comparisons."); + return !(*this < RHS); + } }; -raw_ostream &operator<<(raw_ostream &OS, const BranchProbability &Prob); +inline raw_ostream &operator<<(raw_ostream &OS, BranchProbability Prob) { + return Prob.print(OS); +} + +template +void BranchProbability::normalizeProbabilities(ProbabilityIter Begin, + ProbabilityIter End) { + if (Begin == End) + return; + + unsigned UnknownProbCount = 0; + uint64_t Sum = std::accumulate(Begin, End, uint64_t(0), + [&](uint64_t S, const BranchProbability &BP) { + if (!BP.isUnknown()) + return S + BP.N; + UnknownProbCount++; + return S; + }); + + if (UnknownProbCount > 0) { + BranchProbability ProbForUnknown = BranchProbability::getZero(); + // If the sum of all known probabilities is less than one, evenly distribute + // the complement of sum to unknown probabilities. Otherwise, set unknown + // probabilities to zeros and continue to normalize known probabilities. + if (Sum < BranchProbability::getDenominator()) + ProbForUnknown = BranchProbability::getRaw( + (BranchProbability::getDenominator() - Sum) / UnknownProbCount); + + std::replace_if(Begin, End, + [](const BranchProbability &BP) { return BP.isUnknown(); }, + ProbForUnknown); + + if (Sum <= BranchProbability::getDenominator()) + return; + } + + if (Sum == 0) { + BranchProbability BP(1, std::distance(Begin, End)); + std::fill(Begin, End, BP); + return; + } + + for (auto I = Begin; I != End; ++I) + I->N = (I->N * uint64_t(D) + Sum / 2) / Sum; +} }