1 //==- lib/Support/ScaledNumber.cpp - Support for scaled numbers -*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // Implementation of some scaled number algorithms.
12 //===----------------------------------------------------------------------===//
14 #include "llvm/Support/ScaledNumber.h"
17 using namespace llvm::ScaledNumbers;
19 std::pair<uint64_t, int16_t> ScaledNumbers::multiply64(uint64_t LHS,
21 // Separate into two 32-bit digits (U.L).
22 auto getU = [](uint64_t N) { return N >> 32; };
23 auto getL = [](uint64_t N) { return N & UINT32_MAX; };
24 uint64_t UL = getU(LHS), LL = getL(LHS), UR = getU(RHS), LR = getL(RHS);
26 // Compute cross products.
27 uint64_t P1 = UL * UR, P2 = UL * LR, P3 = LL * UR, P4 = LL * LR;
29 // Sum into two 64-bit digits.
30 uint64_t Upper = P1, Lower = P4;
31 auto addWithCarry = [&](uint64_t N) {
32 uint64_t NewLower = Lower + (getL(N) << 32);
33 Upper += getU(N) + (NewLower < Lower);
39 // Check whether the upper digit is empty.
41 return std::make_pair(Lower, 0);
43 // Shift as little as possible to maximize precision.
44 unsigned LeadingZeros = countLeadingZeros(Upper);
45 int Shift = 64 - LeadingZeros;
47 Upper = Upper << LeadingZeros | Lower >> Shift;
48 return getRounded(Upper, Shift,
49 Shift && (Lower & UINT64_C(1) << (Shift - 1)));
52 static uint64_t getHalf(uint64_t N) { return (N >> 1) + (N & 1); }
54 std::pair<uint32_t, int16_t> ScaledNumbers::divide32(uint32_t Dividend,
56 assert(Dividend && "expected non-zero dividend");
57 assert(Divisor && "expected non-zero divisor");
59 // Use 64-bit math and canonicalize the dividend to gain precision.
60 uint64_t Dividend64 = Dividend;
62 if (int Zeros = countLeadingZeros(Dividend64)) {
66 uint64_t Quotient = Dividend64 / Divisor;
67 uint64_t Remainder = Dividend64 % Divisor;
69 // If Quotient needs to be shifted, leave the rounding to getAdjusted().
70 if (Quotient > UINT32_MAX)
71 return getAdjusted<uint32_t>(Quotient, Shift);
73 // Round based on the value of the next bit.
74 return getRounded<uint32_t>(Quotient, Shift, Remainder >= getHalf(Divisor));
77 std::pair<uint64_t, int16_t> ScaledNumbers::divide64(uint64_t Dividend,
79 assert(Dividend && "expected non-zero dividend");
80 assert(Divisor && "expected non-zero divisor");
82 // Minimize size of divisor.
84 if (int Zeros = countTrailingZeros(Divisor)) {
89 // Check for powers of two.
91 return std::make_pair(Dividend, Shift);
93 // Maximize size of dividend.
94 if (int Zeros = countLeadingZeros(Dividend)) {
99 // Start with the result of a divide.
100 uint64_t Quotient = Dividend / Divisor;
103 // Continue building the quotient with long division.
104 while (!(Quotient >> 63) && Dividend) {
105 // Shift Dividend and check for overflow.
106 bool IsOverflow = Dividend >> 63;
110 // Get the next bit of Quotient.
112 if (IsOverflow || Divisor <= Dividend) {
118 return getRounded(Quotient, Shift, Dividend >= getHalf(Divisor));
121 int ScaledNumbers::compareImpl(uint64_t L, uint64_t R, int ScaleDiff) {
122 assert(ScaleDiff >= 0 && "wrong argument order");
123 assert(ScaleDiff < 64 && "numbers too far apart");
125 uint64_t L_adjusted = L >> ScaleDiff;
131 return L > L_adjusted << ScaleDiff ? 1 : 0;