libc/src/__support/builtin_wrappers.h

   1 //===--Convenient template for builtins -------------------------*- C++ -*-===//
   2 //             (Count Lead Zeroes) and (Count Trailing Zeros)
   3 //
   4 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   5 // See https://llvm.org/LICENSE.txt for license information.
   6 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   7 //
   8 //===----------------------------------------------------------------------===//
   9
  10 #ifndef LLVM_LIBC_SRC_SUPPORT_BUILTIN_WRAPPERS_H
  11 #define LLVM_LIBC_SRC_SUPPORT_BUILTIN_WRAPPERS_H
  12
  13 #include "named_pair.h"
  14 #include "src/__support/CPP/type_traits.h"
  15 #include "src/__support/macros/attributes.h" // LIBC_INLINE
  16 #include "src/__support/macros/config.h"     // LIBC_HAS_BUILTIN
  17
  18 namespace __llvm_libc {
  19
  20 // The following overloads are matched based on what is accepted by
  21 // __builtin_clz/ctz* rather than using the exactly-sized aliases from stdint.h.
  22 // This way, we can avoid making any assumptions about integer sizes and let the
  23 // compiler match for us.
  24 namespace __internal {
  25
  26 template <typename T> LIBC_INLINE int correct_zero(T val, int bits) {
  27   if (val == T(0))
  28     return sizeof(T(0)) * 8;
  29   else
  30     return bits;
  31 }
  32
  33 template <typename T> LIBC_INLINE int clz(T val);
  34 template <> LIBC_INLINE int clz<unsigned int>(unsigned int val) {
  35   return __builtin_clz(val);
  36 }
  37 template <> LIBC_INLINE int clz<unsigned long int>(unsigned long int val) {
  38   return __builtin_clzl(val);
  39 }
  40 template <>
  41 LIBC_INLINE int clz<unsigned long long int>(unsigned long long int val) {
  42   return __builtin_clzll(val);
  43 }
  44
  45 template <typename T> LIBC_INLINE int ctz(T val);
  46 template <> LIBC_INLINE int ctz<unsigned int>(unsigned int val) {
  47   return __builtin_ctz(val);
  48 }
  49 template <> LIBC_INLINE int ctz<unsigned long int>(unsigned long int val) {
  50   return __builtin_ctzl(val);
  51 }
  52 template <>
  53 LIBC_INLINE int ctz<unsigned long long int>(unsigned long long int val) {
  54   return __builtin_ctzll(val);
  55 }
  56 } // namespace __internal
  57
  58 template <typename T> LIBC_INLINE int safe_ctz(T val) {
  59   return __internal::correct_zero(val, __internal::ctz(val));
  60 }
  61
  62 template <typename T> LIBC_INLINE int unsafe_ctz(T val) {
  63   return __internal::ctz(val);
  64 }
  65
  66 template <typename T> LIBC_INLINE int safe_clz(T val) {
  67   return __internal::correct_zero(val, __internal::clz(val));
  68 }
  69
  70 template <typename T> LIBC_INLINE int unsafe_clz(T val) {
  71   return __internal::clz(val);
  72 }
  73
  74 // Add with carry
  75 DEFINE_NAMED_PAIR_TEMPLATE(SumCarry, sum, carry);
  76
  77 // This version is always valid for constexpr.
  78 template <typename T>
  79 LIBC_INLINE constexpr cpp::enable_if_t<
  80     cpp::is_integral_v<T> && cpp::is_unsigned_v<T>, SumCarry<T>>
  81 add_with_carry_const(T a, T b, T carry_in) {
  82   T tmp = a + carry_in;
  83   T sum = b + tmp;
  84   T carry_out = (sum < b) + (tmp < a);
  85   return {sum, carry_out};
  86 }
  87
  88 // This version is not always valid for constepxr because it's overriden below
  89 // if builtins are available.
  90 template <typename T>
  91 LIBC_INLINE cpp::enable_if_t<cpp::is_integral_v<T> && cpp::is_unsigned_v<T>,
  92                              SumCarry<T>>
  93 add_with_carry(T a, T b, T carry_in) {
  94   return add_with_carry_const<T>(a, b, carry_in);
  95 }
  96
  97 #if LIBC_HAS_BUILTIN(__builtin_addc)
  98 // https://clang.llvm.org/docs/LanguageExtensions.html#multiprecision-arithmetic-builtins
  99
 100 template <>
 101 LIBC_INLINE SumCarry<unsigned char>
 102 add_with_carry<unsigned char>(unsigned char a, unsigned char b,
 103                               unsigned char carry_in) {
 104   SumCarry<unsigned char> result{0, 0};
 105   result.sum = __builtin_addcb(a, b, carry_in, &result.carry);
 106   return result;
 107 }
 108
 109 template <>
 110 LIBC_INLINE SumCarry<unsigned short>
 111 add_with_carry<unsigned short>(unsigned short a, unsigned short b,
 112                                unsigned short carry_in) {
 113   SumCarry<unsigned short> result{0, 0};
 114   result.sum = __builtin_addcs(a, b, carry_in, &result.carry);
 115   return result;
 116 }
 117
 118 template <>
 119 LIBC_INLINE SumCarry<unsigned int>
 120 add_with_carry<unsigned int>(unsigned int a, unsigned int b,
 121                              unsigned int carry_in) {
 122   SumCarry<unsigned int> result{0, 0};
 123   result.sum = __builtin_addc(a, b, carry_in, &result.carry);
 124   return result;
 125 }
 126
 127 template <>
 128 LIBC_INLINE SumCarry<unsigned long>
 129 add_with_carry<unsigned long>(unsigned long a, unsigned long b,
 130                               unsigned long carry_in) {
 131   SumCarry<unsigned long> result{0, 0};
 132   result.sum = __builtin_addcl(a, b, carry_in, &result.carry);
 133   return result;
 134 }
 135
 136 template <>
 137 LIBC_INLINE SumCarry<unsigned long long>
 138 add_with_carry<unsigned long long>(unsigned long long a, unsigned long long b,
 139                                    unsigned long long carry_in) {
 140   SumCarry<unsigned long long> result{0, 0};
 141   result.sum = __builtin_addcll(a, b, carry_in, &result.carry);
 142   return result;
 143 }
 144
 145 #endif // LIBC_HAS_BUILTIN(__builtin_addc)
 146
 147 // Subtract with borrow
 148 DEFINE_NAMED_PAIR_TEMPLATE(DiffBorrow, diff, borrow);
 149
 150 // This version is always valid for constexpr.
 151 template <typename T>
 152 LIBC_INLINE constexpr cpp::enable_if_t<
 153     cpp::is_integral_v<T> && cpp::is_unsigned_v<T>, DiffBorrow<T>>
 154 sub_with_borrow_const(T a, T b, T borrow_in) {
 155   T tmp = a - b;
 156   T diff = tmp - borrow_in;
 157   T borrow_out = (diff > tmp) + (tmp > a);
 158   return {diff, borrow_out};
 159 }
 160
 161 // This version is not always valid for constepxr because it's overriden below
 162 // if builtins are available.
 163 template <typename T>
 164 LIBC_INLINE cpp::enable_if_t<cpp::is_integral_v<T> && cpp::is_unsigned_v<T>,
 165                              DiffBorrow<T>>
 166 sub_with_borrow(T a, T b, T borrow_in) {
 167   return sub_with_borrow_const<T>(a, b, borrow_in);
 168 }
 169
 170 #if LIBC_HAS_BUILTIN(__builtin_subc)
 171 // https://clang.llvm.org/docs/LanguageExtensions.html#multiprecision-arithmetic-builtins
 172
 173 template <>
 174 LIBC_INLINE DiffBorrow<unsigned char>
 175 sub_with_borrow<unsigned char>(unsigned char a, unsigned char b,
 176                                unsigned char borrow_in) {
 177   DiffBorrow<unsigned char> result{0, 0};
 178   result.diff = __builtin_subcb(a, b, borrow_in, &result.borrow);
 179   return result;
 180 }
 181
 182 template <>
 183 LIBC_INLINE DiffBorrow<unsigned short>
 184 sub_with_borrow<unsigned short>(unsigned short a, unsigned short b,
 185                                 unsigned short borrow_in) {
 186   DiffBorrow<unsigned short> result{0, 0};
 187   result.diff = __builtin_subcs(a, b, borrow_in, &result.borrow);
 188   return result;
 189 }
 190
 191 template <>
 192 LIBC_INLINE DiffBorrow<unsigned int>
 193 sub_with_borrow<unsigned int>(unsigned int a, unsigned int b,
 194                               unsigned int borrow_in) {
 195   DiffBorrow<unsigned int> result{0, 0};
 196   result.diff = __builtin_subc(a, b, borrow_in, &result.borrow);
 197   return result;
 198 }
 199
 200 template <>
 201 LIBC_INLINE DiffBorrow<unsigned long>
 202 sub_with_borrow<unsigned long>(unsigned long a, unsigned long b,
 203                                unsigned long borrow_in) {
 204   DiffBorrow<unsigned long> result{0, 0};
 205   result.diff = __builtin_subcl(a, b, borrow_in, &result.borrow);
 206   return result;
 207 }
 208
 209 template <>
 210 LIBC_INLINE DiffBorrow<unsigned long long>
 211 sub_with_borrow<unsigned long long>(unsigned long long a, unsigned long long b,
 212                                     unsigned long long borrow_in) {
 213   DiffBorrow<unsigned long long> result{0, 0};
 214   result.diff = __builtin_subcll(a, b, borrow_in, &result.borrow);
 215   return result;
 216 }
 217
 218 #endif // LIBC_HAS_BUILTIN(__builtin_subc)
 219
 220 } // namespace __llvm_libc
 221
 222 #endif // LLVM_LIBC_SRC_SUPPORT_BUILTIN_WRAPPERS_H