lib/Support/BranchProbability.cpp

   1 //===-------------- lib/Support/BranchProbability.cpp -----------*- C++ -*-===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 // This file implements Branch Probability class.
  10 //
  11 //===----------------------------------------------------------------------===//
  12
  13 #include "llvm/Support/BranchProbability.h"
  14 #include "llvm/Config/llvm-config.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   if (isUnknown())
  26     return OS << "?%";
  27
  28   // Get a percentage rounded to two decimal digits. This avoids
  29   // implementation-defined rounding inside printf.
  30   double Percent = rint(((double)N / D) * 100.0 * 100.0) / 100.0;
  31   return OS << format("0x%08" PRIx32 " / 0x%08" PRIx32 " = %.2f%%", N, D,
  32                       Percent);
  33 }
  34
  35 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
  36 LLVM_DUMP_METHOD void BranchProbability::dump() const { print(dbgs()) << '\n'; }
  37 #endif
  38
  39 BranchProbability::BranchProbability(uint32_t Numerator, uint32_t Denominator) {
  40   assert(Denominator > 0 && "Denominator cannot be 0!");
  41   assert(Numerator <= Denominator && "Probability cannot be bigger than 1!");
  42   if (Denominator == D)
  43     N = Numerator;
  44   else {
  45     uint64_t Prob64 =
  46         (Numerator * static_cast<uint64_t>(D) + Denominator / 2) / Denominator;
  47     N = static_cast<uint32_t>(Prob64);
  48   }
  49 }
  50
  51 BranchProbability
  52 BranchProbability::getBranchProbability(uint64_t Numerator,
  53                                         uint64_t Denominator) {
  54   assert(Numerator <= Denominator && "Probability cannot be bigger than 1!");
  55   // Scale down Denominator to fit in a 32-bit integer.
  56   int Scale = 0;
  57   while (Denominator > UINT32_MAX) {
  58     Denominator >>= 1;
  59     Scale++;
  60   }
  61   return BranchProbability(Numerator >> Scale, Denominator);
  62 }
  63
  64 // If ConstD is not zero, then replace D by ConstD so that division and modulo
  65 // operations by D can be optimized, in case this function is not inlined by the
  66 // compiler.
  67 template <uint32_t ConstD>
  68 static uint64_t scale(uint64_t Num, uint32_t N, uint32_t D) {
  69   if (ConstD > 0)
  70     D = ConstD;
  71
  72   assert(D && "divide by 0");
  73
  74   // Fast path for multiplying by 1.0.
  75   if (!Num || D == N)
  76     return Num;
  77
  78   // Split Num into upper and lower parts to multiply, then recombine.
  79   uint64_t ProductHigh = (Num >> 32) * N;
  80   uint64_t ProductLow = (Num & UINT32_MAX) * N;
  81
  82   // Split into 32-bit digits.
  83   uint32_t Upper32 = ProductHigh >> 32;
  84   uint32_t Lower32 = ProductLow & UINT32_MAX;
  85   uint32_t Mid32Partial = ProductHigh & UINT32_MAX;
  86   uint32_t Mid32 = Mid32Partial + (ProductLow >> 32);
  87
  88   // Carry.
  89   Upper32 += Mid32 < Mid32Partial;
  90
  91   // Check for overflow.
  92   if (Upper32 >= D)
  93     return UINT64_MAX;
  94
  95   uint64_t Rem = (uint64_t(Upper32) << 32) | Mid32;
  96   uint64_t UpperQ = Rem / D;
  97
  98   // Check for overflow.
  99   if (UpperQ > UINT32_MAX)
 100     return UINT64_MAX;
 101
 102   Rem = ((Rem % D) << 32) | Lower32;
 103   uint64_t LowerQ = Rem / D;
 104   uint64_t Q = (UpperQ << 32) + LowerQ;
 105
 106   // Check for overflow.
 107   return Q < LowerQ ? UINT64_MAX : Q;
 108 }
 109
 110 uint64_t BranchProbability::scale(uint64_t Num) const {
 111   return ::scale<D>(Num, N, D);
 112 }
 113
 114 uint64_t BranchProbability::scaleByInverse(uint64_t Num) const {
 115   return ::scale<0>(Num, D, N);
 116 }