Home | History | Annotate | Line # | Download | only in Support 
      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 constexpr 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   uint64_t Rem = (uint64_t(Upper32) << 32) | Mid32;
     92   uint64_t UpperQ = Rem / D;
     93 
     94   // Check for overflow.
     95   if (UpperQ > UINT32_MAX)
     96     return UINT64_MAX;
     97 
     98   Rem = ((Rem % D) << 32) | Lower32;
     99   uint64_t LowerQ = Rem / D;
    100   uint64_t Q = (UpperQ << 32) + LowerQ;
    101 
    102   // Check for overflow.
    103   return Q < LowerQ ? UINT64_MAX : Q;
    104 }
    105 
    106 uint64_t BranchProbability::scale(uint64_t Num) const {
    107   return ::scale<D>(Num, N, D);
    108 }
    109 
    110 uint64_t BranchProbability::scaleByInverse(uint64_t Num) const {
    111   return ::scale<0>(Num, D, N);
    112 }
    113