1 //==- lib/Support/ScaledNumber.cpp - Support for scaled numbers -*- 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 // Implementation of some scaled number algorithms. 11 // 12 //===----------------------------------------------------------------------===// 13 14 #include "llvm/Support/ScaledNumber.h" 15 16 using namespace llvm; 17 using namespace llvm::ScaledNumbers; 18 19 std::pair<uint64_t, int16_t> ScaledNumbers::multiply64(uint64_t LHS, 20 uint64_t RHS) { 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); 25 26 // Compute cross products. 27 uint64_t P1 = UL * UR, P2 = UL * LR, P3 = LL * UR, P4 = LL * LR; 28 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); 34 Lower = NewLower; 35 }; 36 addWithCarry(P2); 37 addWithCarry(P3); 38 39 // Check whether the upper digit is empty. 40 if (!Upper) 41 return std::make_pair(Lower, 0); 42 43 // Shift as little as possible to maximize precision. 44 unsigned LeadingZeros = countLeadingZeros(Upper); 45 int Shift = 64 - LeadingZeros; 46 if (LeadingZeros) 47 Upper = Upper << LeadingZeros | Lower >> Shift; 48 return getRounded(Upper, Shift, 49 Shift && (Lower & UINT64_C(1) << (Shift - 1))); 50 } 51 52 static uint64_t getHalf(uint64_t N) { return (N >> 1) + (N & 1); } 53 54 std::pair<uint32_t, int16_t> ScaledNumbers::divide32(uint32_t Dividend, 55 uint32_t Divisor) { 56 assert(Dividend && "expected non-zero dividend"); 57 assert(Divisor && "expected non-zero divisor"); 58 59 // Use 64-bit math and canonicalize the dividend to gain precision. 60 uint64_t Dividend64 = Dividend; 61 int Shift = 0; 62 if (int Zeros = countLeadingZeros(Dividend64)) { 63 Shift -= Zeros; 64 Dividend64 <<= Zeros; 65 } 66 uint64_t Quotient = Dividend64 / Divisor; 67 uint64_t Remainder = Dividend64 % Divisor; 68 69 // If Quotient needs to be shifted, leave the rounding to getAdjusted(). 70 if (Quotient > UINT32_MAX) 71 return getAdjusted<uint32_t>(Quotient, Shift); 72 73 // Round based on the value of the next bit. 74 return getRounded<uint32_t>(Quotient, Shift, Remainder >= getHalf(Divisor)); 75 } 76 77 std::pair<uint64_t, int16_t> ScaledNumbers::divide64(uint64_t Dividend, 78 uint64_t Divisor) { 79 assert(Dividend && "expected non-zero dividend"); 80 assert(Divisor && "expected non-zero divisor"); 81 82 // Minimize size of divisor. 83 int Shift = 0; 84 if (int Zeros = countTrailingZeros(Divisor)) { 85 Shift -= Zeros; 86 Divisor >>= Zeros; 87 } 88 89 // Check for powers of two. 90 if (Divisor == 1) 91 return std::make_pair(Dividend, Shift); 92 93 // Maximize size of dividend. 94 if (int Zeros = countLeadingZeros(Dividend)) { 95 Shift -= Zeros; 96 Dividend <<= Zeros; 97 } 98 99 // Start with the result of a divide. 100 uint64_t Quotient = Dividend / Divisor; 101 Dividend %= Divisor; 102 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; 107 Dividend <<= 1; 108 --Shift; 109 110 // Get the next bit of Quotient. 111 Quotient <<= 1; 112 if (IsOverflow || Divisor <= Dividend) { 113 Quotient |= 1; 114 Dividend -= Divisor; 115 } 116 } 117 118 return getRounded(Quotient, Shift, Dividend >= getHalf(Divisor)); 119 } 120