Coverage Report

Created: 2017-10-03 07:32

/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/lib/Support/BranchProbability.cpp
Line
Count
Source (jump to first uncovered line)
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
17.8k
raw_ostream &BranchProbability::print(raw_ostream &OS) const {
25
17.8k
  if (isUnknown())
26
6.24k
    return OS << "?%";
27
11.6k
28
11.6k
  // Get a percentage rounded to two decimal digits. This avoids
29
11.6k
  // implementation-defined rounding inside printf.
30
11.6k
  double Percent = rint(((double)N / D) * 100.0 * 100.0) / 100.0;
31
11.6k
  return OS << format("0x%08" PRIx32 " / 0x%08" PRIx32 " = %.2f%%", N, D,
32
11.6k
                      Percent);
33
11.6k
}
34
35
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
36
LLVM_DUMP_METHOD void BranchProbability::dump() const { print(dbgs()) << '\n'; }
37
#endif
38
39
86.4M
BranchProbability::BranchProbability(uint32_t Numerator, uint32_t Denominator) {
40
86.4M
  assert(Denominator > 0 && "Denominator cannot be 0!");
41
86.4M
  assert(Numerator <= Denominator && "Probability cannot be bigger than 1!");
42
86.4M
  if (Denominator == D)
43
18.2M
    N = Numerator;
44
68.2M
  else {
45
68.2M
    uint64_t Prob64 =
46
68.2M
        (Numerator * static_cast<uint64_t>(D) + Denominator / 2) / Denominator;
47
68.2M
    N = static_cast<uint32_t>(Prob64);
48
68.2M
  }
49
86.4M
}
50
51
BranchProbability
52
BranchProbability::getBranchProbability(uint64_t Numerator,
53
36.8k
                                        uint64_t Denominator) {
54
36.8k
  assert(Numerator <= Denominator && "Probability cannot be bigger than 1!");
55
36.8k
  // Scale down Denominator to fit in a 32-bit integer.
56
36.8k
  int Scale = 0;
57
49.5k
  while (
Denominator > UINT32_MAX49.5k
) {
58
12.6k
    Denominator >>= 1;
59
12.6k
    Scale++;
60
12.6k
  }
61
36.8k
  return BranchProbability(Numerator >> Scale, Denominator);
62
36.8k
}
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
60.2M
static uint64_t scale(uint64_t Num, uint32_t N, uint32_t D) {
69
60.2M
  if (ConstD > 0)
70
60.0M
    D = ConstD;
71
60.2M
72
60.2M
  assert(D && "divide by 0");
73
60.2M
74
60.2M
  // Fast path for multiplying by 1.0.
75
60.2M
  if (
!Num || 60.2M
D == N59.8M
)
76
34.4M
    return Num;
77
25.8M
78
25.8M
  // Split Num into upper and lower parts to multiply, then recombine.
79
25.8M
  uint64_t ProductHigh = (Num >> 32) * N;
80
25.8M
  uint64_t ProductLow = (Num & UINT32_MAX) * N;
81
25.8M
82
25.8M
  // Split into 32-bit digits.
83
25.8M
  uint32_t Upper32 = ProductHigh >> 32;
84
25.8M
  uint32_t Lower32 = ProductLow & UINT32_MAX;
85
25.8M
  uint32_t Mid32Partial = ProductHigh & UINT32_MAX;
86
25.8M
  uint32_t Mid32 = Mid32Partial + (ProductLow >> 32);
87
25.8M
88
25.8M
  // Carry.
89
25.8M
  Upper32 += Mid32 < Mid32Partial;
90
25.8M
91
25.8M
  // Check for overflow.
92
25.8M
  if (Upper32 >= D)
93
41
    return UINT64_MAX;
94
25.8M
95
25.8M
  uint64_t Rem = (uint64_t(Upper32) << 32) | Mid32;
96
25.8M
  uint64_t UpperQ = Rem / D;
97
25.8M
98
25.8M
  // Check for overflow.
99
25.8M
  if (UpperQ > UINT32_MAX)
100
0
    return UINT64_MAX;
101
25.8M
102
25.8M
  Rem = ((Rem % D) << 32) | Lower32;
103
25.8M
  uint64_t LowerQ = Rem / D;
104
25.8M
  uint64_t Q = (UpperQ << 32) + LowerQ;
105
25.8M
106
25.8M
  // Check for overflow.
107
25.8M
  return Q < LowerQ ? UINT64_MAX : Q;
108
60.2M
}
BranchProbability.cpp:unsigned long long scale<2147483648u>(unsigned long long, unsigned int, unsigned int)
Line
Count
Source
68
60.0M
static uint64_t scale(uint64_t Num, uint32_t N, uint32_t D) {
69
60.0M
  if (ConstD > 0)
70
60.0M
    D = ConstD;
71
60.0M
72
60.0M
  assert(D && "divide by 0");
73
60.0M
74
60.0M
  // Fast path for multiplying by 1.0.
75
60.0M
  if (
!Num || 60.0M
D == N59.7M
)
76
34.3M
    return Num;
77
25.7M
78
25.7M
  // Split Num into upper and lower parts to multiply, then recombine.
79
25.7M
  uint64_t ProductHigh = (Num >> 32) * N;
80
25.7M
  uint64_t ProductLow = (Num & UINT32_MAX) * N;
81
25.7M
82
25.7M
  // Split into 32-bit digits.
83
25.7M
  uint32_t Upper32 = ProductHigh >> 32;
84
25.7M
  uint32_t Lower32 = ProductLow & UINT32_MAX;
85
25.7M
  uint32_t Mid32Partial = ProductHigh & UINT32_MAX;
86
25.7M
  uint32_t Mid32 = Mid32Partial + (ProductLow >> 32);
87
25.7M
88
25.7M
  // Carry.
89
25.7M
  Upper32 += Mid32 < Mid32Partial;
90
25.7M
91
25.7M
  // Check for overflow.
92
25.7M
  if (Upper32 >= D)
93
0
    return UINT64_MAX;
94
25.7M
95
25.7M
  uint64_t Rem = (uint64_t(Upper32) << 32) | Mid32;
96
25.7M
  uint64_t UpperQ = Rem / D;
97
25.7M
98
25.7M
  // Check for overflow.
99
25.7M
  if (UpperQ > UINT32_MAX)
100
0
    return UINT64_MAX;
101
25.7M
102
25.7M
  Rem = ((Rem % D) << 32) | Lower32;
103
25.7M
  uint64_t LowerQ = Rem / D;
104
25.7M
  uint64_t Q = (UpperQ << 32) + LowerQ;
105
25.7M
106
25.7M
  // Check for overflow.
107
25.7M
  return Q < LowerQ ? UINT64_MAX : Q;
108
60.0M
}
BranchProbability.cpp:unsigned long long scale<0u>(unsigned long long, unsigned int, unsigned int)
Line
Count
Source
68
202k
static uint64_t scale(uint64_t Num, uint32_t N, uint32_t D) {
69
202k
  if (ConstD > 0)
70
0
    D = ConstD;
71
202k
72
202k
  assert(D && "divide by 0");
73
202k
74
202k
  // Fast path for multiplying by 1.0.
75
202k
  if (
!Num || 202k
D == N144k
)
76
60.8k
    return Num;
77
142k
78
142k
  // Split Num into upper and lower parts to multiply, then recombine.
79
142k
  uint64_t ProductHigh = (Num >> 32) * N;
80
142k
  uint64_t ProductLow = (Num & UINT32_MAX) * N;
81
142k
82
142k
  // Split into 32-bit digits.
83
142k
  uint32_t Upper32 = ProductHigh >> 32;
84
142k
  uint32_t Lower32 = ProductLow & UINT32_MAX;
85
142k
  uint32_t Mid32Partial = ProductHigh & UINT32_MAX;
86
142k
  uint32_t Mid32 = Mid32Partial + (ProductLow >> 32);
87
142k
88
142k
  // Carry.
89
142k
  Upper32 += Mid32 < Mid32Partial;
90
142k
91
142k
  // Check for overflow.
92
142k
  if (Upper32 >= D)
93
41
    return UINT64_MAX;
94
142k
95
142k
  uint64_t Rem = (uint64_t(Upper32) << 32) | Mid32;
96
142k
  uint64_t UpperQ = Rem / D;
97
142k
98
142k
  // Check for overflow.
99
142k
  if (UpperQ > UINT32_MAX)
100
0
    return UINT64_MAX;
101
142k
102
142k
  Rem = ((Rem % D) << 32) | Lower32;
103
142k
  uint64_t LowerQ = Rem / D;
104
142k
  uint64_t Q = (UpperQ << 32) + LowerQ;
105
142k
106
142k
  // Check for overflow.
107
142k
  return Q < LowerQ ? UINT64_MAX : Q;
108
202k
}
109
110
60.0M
uint64_t BranchProbability::scale(uint64_t Num) const {
111
60.0M
  return ::scale<D>(Num, N, D);
112
60.0M
}
113
114
202k
uint64_t BranchProbability::scaleByInverse(uint64_t Num) const {
115
202k
  return ::scale<0>(Num, D, N);
116
202k
}