1223013Sdim//===-------------- lib/Support/BranchProbability.cpp -----------*- C++ -*-===// 2223013Sdim// 3223013Sdim// The LLVM Compiler Infrastructure 4223013Sdim// 5223013Sdim// This file is distributed under the University of Illinois Open Source 6223013Sdim// License. See LICENSE.TXT for details. 7223013Sdim// 8223013Sdim//===----------------------------------------------------------------------===// 9223013Sdim// 10223013Sdim// This file implements Branch Probability class. 11223013Sdim// 12223013Sdim//===----------------------------------------------------------------------===// 13223013Sdim 14223013Sdim#include "llvm/Support/BranchProbability.h" 15223013Sdim#include "llvm/Support/Debug.h" 16234353Sdim#include "llvm/Support/Format.h" 17223013Sdim#include "llvm/Support/raw_ostream.h" 18296417Sdim#include <cassert> 19223013Sdim 20223013Sdimusing namespace llvm; 21223013Sdim 22296417Sdimconst uint32_t BranchProbability::D; 23296417Sdim 24276479Sdimraw_ostream &BranchProbability::print(raw_ostream &OS) const { 25296417Sdim if (isUnknown()) 26296417Sdim return OS << "?%"; 27296417Sdim 28296417Sdim // Get a percentage rounded to two decimal digits. This avoids 29296417Sdim // implementation-defined rounding inside printf. 30296417Sdim double Percent = rint(((double)N / D) * 100.0 * 100.0) / 100.0; 31296417Sdim return OS << format("0x%08" PRIx32 " / 0x%08" PRIx32 " = %.2f%%", N, D, 32296417Sdim Percent); 33223013Sdim} 34223013Sdim 35276479Sdimvoid BranchProbability::dump() const { print(dbgs()) << '\n'; } 36223013Sdim 37296417SdimBranchProbability::BranchProbability(uint32_t Numerator, uint32_t Denominator) { 38296417Sdim assert(Denominator > 0 && "Denominator cannot be 0!"); 39296417Sdim assert(Numerator <= Denominator && "Probability cannot be bigger than 1!"); 40296417Sdim if (Denominator == D) 41296417Sdim N = Numerator; 42296417Sdim else { 43296417Sdim uint64_t Prob64 = 44296417Sdim (Numerator * static_cast<uint64_t>(D) + Denominator / 2) / Denominator; 45296417Sdim N = static_cast<uint32_t>(Prob64); 46296417Sdim } 47296417Sdim} 48296417Sdim 49296417SdimBranchProbability 50296417SdimBranchProbability::getBranchProbability(uint64_t Numerator, 51296417Sdim uint64_t Denominator) { 52296417Sdim assert(Numerator <= Denominator && "Probability cannot be bigger than 1!"); 53296417Sdim // Scale down Denominator to fit in a 32-bit integer. 54296417Sdim int Scale = 0; 55296417Sdim while (Denominator > UINT32_MAX) { 56296417Sdim Denominator >>= 1; 57296417Sdim Scale++; 58296417Sdim } 59296417Sdim return BranchProbability(Numerator >> Scale, Denominator); 60296417Sdim} 61296417Sdim 62296417Sdim// If ConstD is not zero, then replace D by ConstD so that division and modulo 63296417Sdim// operations by D can be optimized, in case this function is not inlined by the 64296417Sdim// compiler. 65296417Sdimtemplate <uint32_t ConstD> 66276479Sdimstatic uint64_t scale(uint64_t Num, uint32_t N, uint32_t D) { 67296417Sdim if (ConstD > 0) 68296417Sdim D = ConstD; 69296417Sdim 70276479Sdim assert(D && "divide by 0"); 71223013Sdim 72276479Sdim // Fast path for multiplying by 1.0. 73276479Sdim if (!Num || D == N) 74276479Sdim return Num; 75276479Sdim 76276479Sdim // Split Num into upper and lower parts to multiply, then recombine. 77276479Sdim uint64_t ProductHigh = (Num >> 32) * N; 78276479Sdim uint64_t ProductLow = (Num & UINT32_MAX) * N; 79276479Sdim 80276479Sdim // Split into 32-bit digits. 81276479Sdim uint32_t Upper32 = ProductHigh >> 32; 82276479Sdim uint32_t Lower32 = ProductLow & UINT32_MAX; 83276479Sdim uint32_t Mid32Partial = ProductHigh & UINT32_MAX; 84276479Sdim uint32_t Mid32 = Mid32Partial + (ProductLow >> 32); 85276479Sdim 86276479Sdim // Carry. 87276479Sdim Upper32 += Mid32 < Mid32Partial; 88276479Sdim 89276479Sdim // Check for overflow. 90276479Sdim if (Upper32 >= D) 91276479Sdim return UINT64_MAX; 92276479Sdim 93276479Sdim uint64_t Rem = (uint64_t(Upper32) << 32) | Mid32; 94276479Sdim uint64_t UpperQ = Rem / D; 95276479Sdim 96276479Sdim // Check for overflow. 97276479Sdim if (UpperQ > UINT32_MAX) 98276479Sdim return UINT64_MAX; 99276479Sdim 100276479Sdim Rem = ((Rem % D) << 32) | Lower32; 101276479Sdim uint64_t LowerQ = Rem / D; 102276479Sdim uint64_t Q = (UpperQ << 32) + LowerQ; 103276479Sdim 104276479Sdim // Check for overflow. 105276479Sdim return Q < LowerQ ? UINT64_MAX : Q; 106223013Sdim} 107223013Sdim 108276479Sdimuint64_t BranchProbability::scale(uint64_t Num) const { 109296417Sdim return ::scale<D>(Num, N, D); 110223013Sdim} 111276479Sdim 112276479Sdimuint64_t BranchProbability::scaleByInverse(uint64_t Num) const { 113296417Sdim return ::scale<0>(Num, D, N); 114276479Sdim} 115