/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 | } |