Line data    Source code

       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/Config/llvm-config.h"
      16             : #include "llvm/Support/Debug.h"
      17             : #include "llvm/Support/Format.h"
      18             : #include "llvm/Support/raw_ostream.h"
      19             : #include <cassert>
      20             : 
      21             : using namespace llvm;
      22             : 
      23             : const uint32_t BranchProbability::D;
      24             : 
      25         921 : raw_ostream &BranchProbability::print(raw_ostream &OS) const {
      26         921 :   if (isUnknown())
      27           0 :     return OS << "?%";
      28             : 
      29             :   // Get a percentage rounded to two decimal digits. This avoids
      30             :   // implementation-defined rounding inside printf.
      31         921 :   double Percent = rint(((double)N / D) * 100.0 * 100.0) / 100.0;
      32         921 :   return OS << format("0x%08" PRIx32 " / 0x%08" PRIx32 " = %.2f%%", N, D,
      33         921 :                       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     5634252 : 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     5634252 :   if (Denominator == D)
      44     1261260 :     N = Numerator;
      45             :   else {
      46     4372992 :     uint64_t Prob64 =
      47     4372992 :         (Numerator * static_cast<uint64_t>(D) + Denominator / 2) / Denominator;
      48     4372992 :     N = static_cast<uint32_t>(Prob64);
      49             :   }
      50     5634252 : }
      51             : 
      52             : BranchProbability
      53        2054 : 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        4884 :   while (Denominator > UINT32_MAX) {
      59        2830 :     Denominator >>= 1;
      60        2830 :     Scale++;
      61             :   }
      62        2054 :   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        3198 : 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        3198 :   if (!Num || D == N)
      77           0 :     return Num;
      78             : 
      79             :   // Split Num into upper and lower parts to multiply, then recombine.
      80        1140 :   uint64_t ProductHigh = (Num >> 32) * N;
      81        1140 :   uint64_t ProductLow = (Num & UINT32_MAX) * N;
      82             : 
      83             :   // Split into 32-bit digits.
      84        1140 :   uint32_t Upper32 = ProductHigh >> 32;
      85             :   uint32_t Lower32 = ProductLow & UINT32_MAX;
      86        1140 :   uint32_t Mid32Partial = ProductHigh & UINT32_MAX;
      87        1140 :   uint32_t Mid32 = Mid32Partial + (ProductLow >> 32);
      88             : 
      89             :   // Carry.
      90        1140 :   Upper32 += Mid32 < Mid32Partial;
      91             : 
      92             :   // Check for overflow.
      93        1140 :   if (Upper32 >= D)
      94           0 :     return UINT64_MAX;
      95             : 
      96        1123 :   uint64_t Rem = (uint64_t(Upper32) << 32) | Mid32;
      97        1123 :   uint64_t UpperQ = Rem / D;
      98             : 
      99             :   // Check for overflow.
     100        1123 :   if (UpperQ > UINT32_MAX)
     101             :     return UINT64_MAX;
     102             : 
     103        1123 :   Rem = ((Rem % D) << 32) | Lower32;
     104        1123 :   uint64_t LowerQ = Rem / D;
     105        1123 :   uint64_t Q = (UpperQ << 32) + LowerQ;
     106             : 
     107             :   // Check for overflow.
     108        1123 :   return Q < LowerQ ? UINT64_MAX : Q;
     109             : }
     110        3198 : 
     111             : uint64_t BranchProbability::scale(uint64_t Num) const {
     112             :   return ::scale<D>(Num, N, D);
     113             : }
     114             : 
     115             : uint64_t BranchProbability::scaleByInverse(uint64_t Num) const {
     116             :   return ::scale<0>(Num, D, N);
     117        3198 : }