lib/Support/ScaledNumber.cpp

   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
 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");
 124
 125   uint64_t L_adjusted = L >> ScaleDiff;
 126   if (L_adjusted < R)
 127     return -1;
 128   if (L_adjusted > R)
 129     return 1;
 130
 131   return L > L_adjusted << ScaleDiff ? 1 : 0;
 132 }