LCOV - code coverage report
Current view: top level - lib/Support - BranchProbability.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 41 41 100.0 %
Date: 2017-09-14 15:23:50 Functions: 7 7 100.0 %
Legend: Lines: hit not hit

          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/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       17851 : raw_ostream &BranchProbability::print(raw_ostream &OS) const {
      25       17851 :   if (isUnknown())
      26        6241 :     return OS << "?%";
      27             : 
      28             :   // Get a percentage rounded to two decimal digits. This avoids
      29             :   // implementation-defined rounding inside printf.
      30       11610 :   double Percent = rint(((double)N / D) * 100.0 * 100.0) / 100.0;
      31       34830 :   return OS << format("0x%08" PRIx32 " / 0x%08" PRIx32 " = %.2f%%", N, D,
      32       11610 :                       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     3006657 : 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     3006657 :   if (Denominator == D)
      43      662293 :     N = Numerator;
      44             :   else {
      45     2344364 :     uint64_t Prob64 =
      46     2344364 :         (Numerator * static_cast<uint64_t>(D) + Denominator / 2) / Denominator;
      47     2344364 :     N = static_cast<uint32_t>(Prob64);
      48             :   }
      49     3006657 : }
      50             : 
      51             : BranchProbability
      52        1401 : 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        1401 :   int Scale = 0;
      57        4897 :   while (Denominator > UINT32_MAX) {
      58        1748 :     Denominator >>= 1;
      59        1748 :     Scale++;
      60             :   }
      61        1401 :   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     2185875 : static uint64_t scale(uint64_t Num, uint32_t N, uint32_t D) {
      69             :   if (ConstD > 0)
      70     2184242 :     D = ConstD;
      71             : 
      72             :   assert(D && "divide by 0");
      73             : 
      74             :   // Fast path for multiplying by 1.0.
      75     2185875 :   if (!Num || D == N)
      76             :     return Num;
      77             : 
      78             :   // Split Num into upper and lower parts to multiply, then recombine.
      79      925108 :   uint64_t ProductHigh = (Num >> 32) * N;
      80      925108 :   uint64_t ProductLow = (Num & UINT32_MAX) * N;
      81             : 
      82             :   // Split into 32-bit digits.
      83      925108 :   uint32_t Upper32 = ProductHigh >> 32;
      84      925108 :   uint32_t Lower32 = ProductLow & UINT32_MAX;
      85      925108 :   uint32_t Mid32Partial = ProductHigh & UINT32_MAX;
      86      925108 :   uint32_t Mid32 = Mid32Partial + (ProductLow >> 32);
      87             : 
      88             :   // Carry.
      89      925108 :   Upper32 += Mid32 < Mid32Partial;
      90             : 
      91             :   // Check for overflow.
      92      925108 :   if (Upper32 >= D)
      93             :     return UINT64_MAX;
      94             : 
      95      925103 :   uint64_t Rem = (uint64_t(Upper32) << 32) | Mid32;
      96      925103 :   uint64_t UpperQ = Rem / D;
      97             : 
      98             :   // Check for overflow.
      99      925103 :   if (UpperQ > UINT32_MAX)
     100             :     return UINT64_MAX;
     101             : 
     102      925103 :   Rem = ((Rem % D) << 32) | Lower32;
     103      925103 :   uint64_t LowerQ = Rem / D;
     104      925103 :   uint64_t Q = (UpperQ << 32) + LowerQ;
     105             : 
     106             :   // Check for overflow.
     107      925103 :   return Q < LowerQ ? UINT64_MAX : Q;
     108             : }
     109             : 
     110     2184242 : uint64_t BranchProbability::scale(uint64_t Num) const {
     111     2184242 :   return ::scale<D>(Num, N, D);
     112             : }
     113             : 
     114        1633 : uint64_t BranchProbability::scaleByInverse(uint64_t Num) const {
     115        1633 :   return ::scale<0>(Num, D, N);
     116             : }

Generated by: LCOV version 1.13