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
|
//==- lib/Support/ScaledNumber.cpp - Support for scaled numbers -*- C++ -*-===//
//
// The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// Implementation of some scaled number algorithms.
//
//===----------------------------------------------------------------------===//
#include "llvm/Support/ScaledNumber.h"
using namespace llvm;
using namespace llvm::ScaledNumbers;
std::pair<uint64_t, int16_t> ScaledNumbers::multiply64(uint64_t LHS,
uint64_t RHS) {
// Separate into two 32-bit digits (U.L).
auto getU = [](uint64_t N) { return N >> 32; };
auto getL = [](uint64_t N) { return N & UINT32_MAX; };
uint64_t UL = getU(LHS), LL = getL(LHS), UR = getU(RHS), LR = getL(RHS);
// Compute cross products.
uint64_t P1 = UL * UR, P2 = UL * LR, P3 = LL * UR, P4 = LL * LR;
// Sum into two 64-bit digits.
uint64_t Upper = P1, Lower = P4;
auto addWithCarry = [&](uint64_t N) {
uint64_t NewLower = Lower + (getL(N) << 32);
Upper += getU(N) + (NewLower < Lower);
Lower = NewLower;
};
addWithCarry(P2);
addWithCarry(P3);
// Check whether the upper digit is empty.
if (!Upper)
return std::make_pair(Lower, 0);
// Shift as little as possible to maximize precision.
unsigned LeadingZeros = countLeadingZeros(Upper);
int Shift = 64 - LeadingZeros;
if (LeadingZeros)
Upper = Upper << LeadingZeros | Lower >> Shift;
return getRounded(Upper, Shift,
Shift && (Lower & UINT64_C(1) << (Shift - 1)));
}
static uint64_t getHalf(uint64_t N) { return (N >> 1) + (N & 1); }
std::pair<uint32_t, int16_t> ScaledNumbers::divide32(uint32_t Dividend,
uint32_t Divisor) {
assert(Dividend && "expected non-zero dividend");
assert(Divisor && "expected non-zero divisor");
// Use 64-bit math and canonicalize the dividend to gain precision.
uint64_t Dividend64 = Dividend;
int Shift = 0;
if (int Zeros = countLeadingZeros(Dividend64)) {
Shift -= Zeros;
Dividend64 <<= Zeros;
}
uint64_t Quotient = Dividend64 / Divisor;
uint64_t Remainder = Dividend64 % Divisor;
// If Quotient needs to be shifted, leave the rounding to getAdjusted().
if (Quotient > UINT32_MAX)
return getAdjusted<uint32_t>(Quotient, Shift);
// Round based on the value of the next bit.
return getRounded<uint32_t>(Quotient, Shift, Remainder >= getHalf(Divisor));
}
std::pair<uint64_t, int16_t> ScaledNumbers::divide64(uint64_t Dividend,
uint64_t Divisor) {
assert(Dividend && "expected non-zero dividend");
assert(Divisor && "expected non-zero divisor");
// Minimize size of divisor.
int Shift = 0;
if (int Zeros = countTrailingZeros(Divisor)) {
Shift -= Zeros;
Divisor >>= Zeros;
}
// Check for powers of two.
if (Divisor == 1)
return std::make_pair(Dividend, Shift);
// Maximize size of dividend.
if (int Zeros = countLeadingZeros(Dividend)) {
Shift -= Zeros;
Dividend <<= Zeros;
}
// Start with the result of a divide.
uint64_t Quotient = Dividend / Divisor;
Dividend %= Divisor;
// Continue building the quotient with long division.
while (!(Quotient >> 63) && Dividend) {
// Shift Dividend and check for overflow.
bool IsOverflow = Dividend >> 63;
Dividend <<= 1;
--Shift;
// Get the next bit of Quotient.
Quotient <<= 1;
if (IsOverflow || Divisor <= Dividend) {
Quotient |= 1;
Dividend -= Divisor;
}
}
return getRounded(Quotient, Shift, Dividend >= getHalf(Divisor));
}
|
