include/llvm/Support/ScaledNumber.h

   1 //===- llvm/Support/ScaledNumber.h - 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 // This file contains functions (and a class) useful for working with scaled
  11 // numbers -- in particular, pairs of integers where one represents digits and
  12 // another represents a scale.  The functions are helpers and live in the
  13 // namespace ScaledNumbers.  The class ScaledNumber is useful for modelling
  14 // certain cost metrics that need simple, integer-like semantics that are easy
  15 // to reason about.
  16 //
  17 // These might remind you of soft-floats.  If you want one of those, you're in
  18 // the wrong place.  Look at include/llvm/ADT/APFloat.h instead.
  19 //
  20 //===----------------------------------------------------------------------===//
  21
  22 #ifndef LLVM_SUPPORT_SCALEDNUMBER_H
  23 #define LLVM_SUPPORT_SCALEDNUMBER_H
  24
  25 #include "llvm/Support/MathExtras.h"
  26
  27 #include <cstdint>
  28 #include <limits>
  29 #include <utility>
  30
  31 namespace llvm {
  32 namespace ScaledNumbers {
  33
  34 /// \brief Get the width of a number.
  35 template <class DigitsT> inline int getWidth() { return sizeof(DigitsT) * 8; }
  36
  37 /// \brief Conditionally round up a scaled number.
  38 ///
  39 /// Given \c Digits and \c Scale, round up iff \c ShouldRound is \c true.
  40 /// Always returns \c Scale unless there's an overflow, in which case it
  41 /// returns \c 1+Scale.
  42 ///
  43 /// \pre adding 1 to \c Scale will not overflow INT16_MAX.
  44 template <class DigitsT>
  45 inline std::pair<DigitsT, int16_t> getRounded(DigitsT Digits, int16_t Scale,
  46                                               bool ShouldRound) {
  47   static_assert(!std::numeric_limits<DigitsT>::is_signed, "expected unsigned");
  48
  49   if (ShouldRound)
  50     if (!++Digits)
  51       // Overflow.
  52       return std::make_pair(DigitsT(1) << (getWidth<DigitsT>() - 1), Scale + 1);
  53   return std::make_pair(Digits, Scale);
  54 }
  55
  56 /// \brief Convenience helper for 32-bit rounding.
  57 inline std::pair<uint32_t, int16_t> getRounded32(uint32_t Digits, int16_t Scale,
  58                                                  bool ShouldRound) {
  59   return getRounded(Digits, Scale, ShouldRound);
  60 }
  61
  62 /// \brief Convenience helper for 64-bit rounding.
  63 inline std::pair<uint64_t, int16_t> getRounded64(uint64_t Digits, int16_t Scale,
  64                                                  bool ShouldRound) {
  65   return getRounded(Digits, Scale, ShouldRound);
  66 }
  67
  68 /// \brief Adjust a 64-bit scaled number down to the appropriate width.
  69 ///
  70 /// \pre Adding 64 to \c Scale will not overflow INT16_MAX.
  71 template <class DigitsT>
  72 inline std::pair<DigitsT, int16_t> getAdjusted(uint64_t Digits,
  73                                                int16_t Scale = 0) {
  74   static_assert(!std::numeric_limits<DigitsT>::is_signed, "expected unsigned");
  75
  76   const int Width = getWidth<DigitsT>();
  77   if (Width == 64 || Digits <= std::numeric_limits<DigitsT>::max())
  78     return std::make_pair(Digits, Scale);
  79
  80   // Shift right and round.
  81   int Shift = 64 - Width - countLeadingZeros(Digits);
  82   return getRounded<DigitsT>(Digits >> Shift, Scale + Shift,
  83                              Digits & (UINT64_C(1) << (Shift - 1)));
  84 }
  85
  86 /// \brief Convenience helper for adjusting to 32 bits.
  87 inline std::pair<uint32_t, int16_t> getAdjusted32(uint64_t Digits,
  88                                                   int16_t Scale = 0) {
  89   return getAdjusted<uint32_t>(Digits, Scale);
  90 }
  91
  92 /// \brief Convenience helper for adjusting to 64 bits.
  93 inline std::pair<uint64_t, int16_t> getAdjusted64(uint64_t Digits,
  94                                                   int16_t Scale = 0) {
  95   return getAdjusted<uint64_t>(Digits, Scale);
  96 }
  97
  98 /// \brief Multiply two 64-bit integers to create a 64-bit scaled number.
  99 ///
 100 /// Implemented with four 64-bit integer multiplies.
 101 std::pair<uint64_t, int16_t> multiply64(uint64_t LHS, uint64_t RHS);
 102
 103 /// \brief Multiply two 32-bit integers to create a 32-bit scaled number.
 104 ///
 105 /// Implemented with one 64-bit integer multiply.
 106 template <class DigitsT>
 107 inline std::pair<DigitsT, int16_t> getProduct(DigitsT LHS, DigitsT RHS) {
 108   static_assert(!std::numeric_limits<DigitsT>::is_signed, "expected unsigned");
 109
 110   if (getWidth<DigitsT>() <= 32 || (LHS <= UINT32_MAX && RHS <= UINT32_MAX))
 111     return getAdjusted<DigitsT>(uint64_t(LHS) * RHS);
 112
 113   return multiply64(LHS, RHS);
 114 }
 115
 116 /// \brief Convenience helper for 32-bit product.
 117 inline std::pair<uint32_t, int16_t> getProduct32(uint32_t LHS, uint32_t RHS) {
 118   return getProduct(LHS, RHS);
 119 }
 120
 121 /// \brief Convenience helper for 64-bit product.
 122 inline std::pair<uint64_t, int16_t> getProduct64(uint64_t LHS, uint64_t RHS) {
 123   return getProduct(LHS, RHS);
 124 }
 125
 126 /// \brief Divide two 64-bit integers to create a 64-bit scaled number.
 127 ///
 128 /// Implemented with long division.
 129 ///
 130 /// \pre \c Dividend and \c Divisor are non-zero.
 131 std::pair<uint64_t, int16_t> divide64(uint64_t Dividend, uint64_t Divisor);
 132
 133 /// \brief Divide two 32-bit integers to create a 32-bit scaled number.
 134 ///
 135 /// Implemented with one 64-bit integer divide/remainder pair.
 136 ///
 137 /// \pre \c Dividend and \c Divisor are non-zero.
 138 std::pair<uint32_t, int16_t> divide32(uint32_t Dividend, uint32_t Divisor);
 139
 140 /// \brief Divide two 32-bit numbers to create a 32-bit scaled number.
 141 ///
 142 /// Implemented with one 64-bit integer divide/remainder pair.
 143 ///
 144 /// Returns \c (DigitsT_MAX, INT16_MAX) for divide-by-zero (0 for 0/0).
 145 template <class DigitsT>
 146 std::pair<DigitsT, int16_t> getQuotient(DigitsT Dividend, DigitsT Divisor) {
 147   static_assert(!std::numeric_limits<DigitsT>::is_signed, "expected unsigned");
 148   static_assert(sizeof(DigitsT) == 4 || sizeof(DigitsT) == 8,
 149                 "expected 32-bit or 64-bit digits");
 150
 151   // Check for zero.
 152   if (!Dividend)
 153     return std::make_pair(0, 0);
 154   if (!Divisor)
 155     return std::make_pair(std::numeric_limits<DigitsT>::max(), INT16_MAX);
 156
 157   if (getWidth<DigitsT>() == 64)
 158     return divide64(Dividend, Divisor);
 159   return divide32(Dividend, Divisor);
 160 }
 161
 162 /// \brief Convenience helper for 32-bit quotient.
 163 inline std::pair<uint32_t, int16_t> getQuotient32(uint32_t Dividend,
 164                                                   uint32_t Divisor) {
 165   return getQuotient(Dividend, Divisor);
 166 }
 167
 168 /// \brief Convenience helper for 64-bit quotient.
 169 inline std::pair<uint64_t, int16_t> getQuotient64(uint64_t Dividend,
 170                                                   uint64_t Divisor) {
 171   return getQuotient(Dividend, Divisor);
 172 }
 173
 174 } // end namespace ScaledNumbers
 175 } // end namespace llvm
 176
 177 #endif
 178