1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
|
//====--------------- lib/Support/BlockFrequency.cpp -----------*- C++ -*-====//
//
// The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This file implements Block Frequency class.
//
//===----------------------------------------------------------------------===//
#include "llvm/Support/BranchProbability.h"
#include "llvm/Support/BlockFrequency.h"
#include "llvm/Support/raw_ostream.h"
#include <cassert>
using namespace llvm;
namespace {
/// mult96bit - Multiply FREQ by N and store result in W array.
void mult96bit(uint64_t freq, uint32_t N, uint64_t W[2]) {
uint64_t u0 = freq & UINT32_MAX;
uint64_t u1 = freq >> 32;
// Represent 96-bit value as w[2]:w[1]:w[0];
uint32_t w[3] = { 0, 0, 0 };
uint64_t t = u0 * N;
uint64_t k = t >> 32;
w[0] = t;
t = u1 * N + k;
w[1] = t;
w[2] = t >> 32;
// W[1] - higher bits.
// W[0] - lower bits.
W[0] = w[0] + ((uint64_t) w[1] << 32);
W[1] = w[2];
}
/// div96bit - Divide 96-bit value stored in W array by D. Return 64-bit frequency.
uint64_t div96bit(uint64_t W[2], uint32_t D) {
uint64_t y = W[0];
uint64_t x = W[1];
int i;
for (i = 1; i <= 64 && x; ++i) {
uint32_t t = (int)x >> 31;
x = (x << 1) | (y >> 63);
y = y << 1;
if ((x | t) >= D) {
x -= D;
++y;
}
}
return y << (64 - i + 1);
}
}
BlockFrequency &BlockFrequency::operator*=(const BranchProbability &Prob) {
uint32_t n = Prob.getNumerator();
uint32_t d = Prob.getDenominator();
assert(n <= d && "Probability must be less or equal to 1.");
// Calculate Frequency * n.
uint64_t mulLo = (Frequency & UINT32_MAX) * n;
uint64_t mulHi = (Frequency >> 32) * n;
uint64_t mulRes = (mulHi << 32) + mulLo;
// If there was overflow use 96-bit operations.
if (mulHi > UINT32_MAX || mulRes < mulLo) {
// 96-bit value represented as W[1]:W[0].
uint64_t W[2];
// Probability is less or equal to 1 which means that results must fit
// 64-bit.
mult96bit(Frequency, n, W);
Frequency = div96bit(W, d);
return *this;
}
Frequency = mulRes / d;
return *this;
}
const BlockFrequency
BlockFrequency::operator*(const BranchProbability &Prob) const {
BlockFrequency Freq(Frequency);
Freq *= Prob;
return Freq;
}
BlockFrequency &BlockFrequency::operator+=(const BlockFrequency &Freq) {
uint64_t Before = Freq.Frequency;
Frequency += Freq.Frequency;
// If overflow, set frequency to the maximum value.
if (Frequency < Before)
Frequency = UINT64_MAX;
return *this;
}
const BlockFrequency
BlockFrequency::operator+(const BlockFrequency &Prob) const {
BlockFrequency Freq(Frequency);
Freq += Prob;
return Freq;
}
void BlockFrequency::print(raw_ostream &OS) const {
OS << Frequency;
}
namespace llvm {
raw_ostream &operator<<(raw_ostream &OS, const BlockFrequency &Freq) {
Freq.print(OS);
return OS;
}
}
|
