1 //===-------------- lib/Support/BranchProbability.cpp -----------*- 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 // This file implements Branch Probability class. 11 // 12 //===----------------------------------------------------------------------===// 13 14 #include "llvm/Support/BranchProbability.h" 15 #include "llvm/Support/Debug.h" 16 #include "llvm/Support/Format.h" 17 #include "llvm/Support/raw_ostream.h" 18 #include <cassert> 19 20 using namespace llvm; 21 22 const uint32_t BranchProbability::D; 23 24 raw_ostream &BranchProbability::print(raw_ostream &OS) const { 25 // Get a percentage rounded to two decimal digits. This avoids 26 // implementation-defined rounding inside printf. 27 double Percent = rint(((double)N / D) * 100.0 * 100.0) / 100.0; 28 OS << format("0x%08" PRIx32 " / 0x%08" PRIx32 " = %.2f%%", N, D, Percent); 29 return OS; 30 } 31 32 void BranchProbability::dump() const { print(dbgs()) << '\n'; } 33 34 BranchProbability::BranchProbability(uint32_t Numerator, uint32_t Denominator) { 35 assert(Denominator > 0 && "Denominator cannot be 0!"); 36 assert(Numerator <= Denominator && "Probability cannot be bigger than 1!"); 37 if (Denominator == D) 38 N = Numerator; 39 else { 40 uint64_t Prob64 = 41 (Numerator * static_cast<uint64_t>(D) + Denominator / 2) / Denominator; 42 N = static_cast<uint32_t>(Prob64); 43 } 44 } 45 46 // If ConstD is not zero, then replace D by ConstD so that division and modulo 47 // operations by D can be optimized, in case this function is not inlined by the 48 // compiler. 49 template <uint32_t ConstD> 50 static uint64_t scale(uint64_t Num, uint32_t N, uint32_t D) { 51 if (ConstD > 0) 52 D = ConstD; 53 54 assert(D && "divide by 0"); 55 56 // Fast path for multiplying by 1.0. 57 if (!Num || D == N) 58 return Num; 59 60 // Split Num into upper and lower parts to multiply, then recombine. 61 uint64_t ProductHigh = (Num >> 32) * N; 62 uint64_t ProductLow = (Num & UINT32_MAX) * N; 63 64 // Split into 32-bit digits. 65 uint32_t Upper32 = ProductHigh >> 32; 66 uint32_t Lower32 = ProductLow & UINT32_MAX; 67 uint32_t Mid32Partial = ProductHigh & UINT32_MAX; 68 uint32_t Mid32 = Mid32Partial + (ProductLow >> 32); 69 70 // Carry. 71 Upper32 += Mid32 < Mid32Partial; 72 73 // Check for overflow. 74 if (Upper32 >= D) 75 return UINT64_MAX; 76 77 uint64_t Rem = (uint64_t(Upper32) << 32) | Mid32; 78 uint64_t UpperQ = Rem / D; 79 80 // Check for overflow. 81 if (UpperQ > UINT32_MAX) 82 return UINT64_MAX; 83 84 Rem = ((Rem % D) << 32) | Lower32; 85 uint64_t LowerQ = Rem / D; 86 uint64_t Q = (UpperQ << 32) + LowerQ; 87 88 // Check for overflow. 89 return Q < LowerQ ? UINT64_MAX : Q; 90 } 91 92 uint64_t BranchProbability::scale(uint64_t Num) const { 93 return ::scale<D>(Num, N, D); 94 } 95 96 uint64_t BranchProbability::scaleByInverse(uint64_t Num) const { 97 return ::scale<0>(Num, D, N); 98 } 99