Coverage Report

Created: 2019-07-24 05:18

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