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