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 constexpr 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 constexpr int clz(T val);
  34 template <> LIBC_INLINE int clz<unsigned int>(unsigned int val) {
  35   return __builtin_clz(val);
  36 }
  37 template <>
  38 LIBC_INLINE constexpr int clz<unsigned long int>(unsigned long int val) {
  39   return __builtin_clzl(val);
  40 }
  41 template <>
  42 LIBC_INLINE constexpr int
  43 clz<unsigned long long int>(unsigned long long int val) {
  44   return __builtin_clzll(val);
  45 }
  46
  47 template <typename T> LIBC_INLINE constexpr int ctz(T val);
  48 template <> LIBC_INLINE int ctz<unsigned int>(unsigned int val) {
  49   return __builtin_ctz(val);
  50 }
  51 template <>
  52 LIBC_INLINE constexpr int ctz<unsigned long int>(unsigned long int val) {
  53   return __builtin_ctzl(val);
  54 }
  55 template <>
  56 LIBC_INLINE constexpr int
  57 ctz<unsigned long long int>(unsigned long long int val) {
  58   return __builtin_ctzll(val);
  59 }
  60 } // namespace __internal
  61
  62 template <typename T> LIBC_INLINE constexpr int safe_ctz(T val) {
  63   return __internal::correct_zero(val, __internal::ctz(val));
  64 }
  65
  66 template <typename T> LIBC_INLINE constexpr int unsafe_ctz(T val) {
  67   return __internal::ctz(val);
  68 }
  69
  70 template <typename T> LIBC_INLINE constexpr int safe_clz(T val) {
  71   return __internal::correct_zero(val, __internal::clz(val));
  72 }
  73
  74 template <typename T> LIBC_INLINE constexpr int unsafe_clz(T val) {
  75   return __internal::clz(val);
  76 }
  77
  78 // Add with carry
  79 DEFINE_NAMED_PAIR_TEMPLATE(SumCarry, sum, carry);
  80
  81 // This version is always valid for constexpr.
  82 template <typename T>
  83 LIBC_INLINE constexpr cpp::enable_if_t<
  84     cpp::is_integral_v<T> && cpp::is_unsigned_v<T>, SumCarry<T>>
  85 add_with_carry_const(T a, T b, T carry_in) {
  86   T tmp = a + carry_in;
  87   T sum = b + tmp;
  88   T carry_out = (sum < b) + (tmp < a);
  89   return {sum, carry_out};
  90 }
  91
  92 // This version is not always valid for constepxr because it's overriden below
  93 // if builtins are available.
  94 template <typename T>
  95 LIBC_INLINE cpp::enable_if_t<cpp::is_integral_v<T> && cpp::is_unsigned_v<T>,
  96                              SumCarry<T>>
  97 add_with_carry(T a, T b, T carry_in) {
  98   return add_with_carry_const<T>(a, b, carry_in);
  99 }
 100
 101 #if LIBC_HAS_BUILTIN(__builtin_addc)
 102 // https://clang.llvm.org/docs/LanguageExtensions.html#multiprecision-arithmetic-builtins
 103
 104 template <>
 105 LIBC_INLINE SumCarry<unsigned char>
 106 add_with_carry<unsigned char>(unsigned char a, unsigned char b,
 107                               unsigned char carry_in) {
 108   SumCarry<unsigned char> result{0, 0};
 109   result.sum = __builtin_addcb(a, b, carry_in, &result.carry);
 110   return result;
 111 }
 112
 113 template <>
 114 LIBC_INLINE SumCarry<unsigned short>
 115 add_with_carry<unsigned short>(unsigned short a, unsigned short b,
 116                                unsigned short carry_in) {
 117   SumCarry<unsigned short> result{0, 0};
 118   result.sum = __builtin_addcs(a, b, carry_in, &result.carry);
 119   return result;
 120 }
 121
 122 template <>
 123 LIBC_INLINE SumCarry<unsigned int>
 124 add_with_carry<unsigned int>(unsigned int a, unsigned int b,
 125                              unsigned int carry_in) {
 126   SumCarry<unsigned int> result{0, 0};
 127   result.sum = __builtin_addc(a, b, carry_in, &result.carry);
 128   return result;
 129 }
 130
 131 template <>
 132 LIBC_INLINE SumCarry<unsigned long>
 133 add_with_carry<unsigned long>(unsigned long a, unsigned long b,
 134                               unsigned long carry_in) {
 135   SumCarry<unsigned long> result{0, 0};
 136   result.sum = __builtin_addcl(a, b, carry_in, &result.carry);
 137   return result;
 138 }
 139
 140 template <>
 141 LIBC_INLINE SumCarry<unsigned long long>
 142 add_with_carry<unsigned long long>(unsigned long long a, unsigned long long b,
 143                                    unsigned long long carry_in) {
 144   SumCarry<unsigned long long> result{0, 0};
 145   result.sum = __builtin_addcll(a, b, carry_in, &result.carry);
 146   return result;
 147 }
 148
 149 #endif // LIBC_HAS_BUILTIN(__builtin_addc)
 150
 151 // Subtract with borrow
 152 DEFINE_NAMED_PAIR_TEMPLATE(DiffBorrow, diff, borrow);
 153
 154 // This version is always valid for constexpr.
 155 template <typename T>
 156 LIBC_INLINE constexpr cpp::enable_if_t<
 157     cpp::is_integral_v<T> && cpp::is_unsigned_v<T>, DiffBorrow<T>>
 158 sub_with_borrow_const(T a, T b, T borrow_in) {
 159   T tmp = a - b;
 160   T diff = tmp - borrow_in;
 161   T borrow_out = (diff > tmp) + (tmp > a);
 162   return {diff, borrow_out};
 163 }
 164
 165 // This version is not always valid for constepxr because it's overriden below
 166 // if builtins are available.
 167 template <typename T>
 168 LIBC_INLINE cpp::enable_if_t<cpp::is_integral_v<T> && cpp::is_unsigned_v<T>,
 169                              DiffBorrow<T>>
 170 sub_with_borrow(T a, T b, T borrow_in) {
 171   return sub_with_borrow_const<T>(a, b, borrow_in);
 172 }
 173
 174 #if LIBC_HAS_BUILTIN(__builtin_subc)
 175 // https://clang.llvm.org/docs/LanguageExtensions.html#multiprecision-arithmetic-builtins
 176
 177 template <>
 178 LIBC_INLINE DiffBorrow<unsigned char>
 179 sub_with_borrow<unsigned char>(unsigned char a, unsigned char b,
 180                                unsigned char borrow_in) {
 181   DiffBorrow<unsigned char> result{0, 0};
 182   result.diff = __builtin_subcb(a, b, borrow_in, &result.borrow);
 183   return result;
 184 }
 185
 186 template <>
 187 LIBC_INLINE DiffBorrow<unsigned short>
 188 sub_with_borrow<unsigned short>(unsigned short a, unsigned short b,
 189                                 unsigned short borrow_in) {
 190   DiffBorrow<unsigned short> result{0, 0};
 191   result.diff = __builtin_subcs(a, b, borrow_in, &result.borrow);
 192   return result;
 193 }
 194
 195 template <>
 196 LIBC_INLINE DiffBorrow<unsigned int>
 197 sub_with_borrow<unsigned int>(unsigned int a, unsigned int b,
 198                               unsigned int borrow_in) {
 199   DiffBorrow<unsigned int> result{0, 0};
 200   result.diff = __builtin_subc(a, b, borrow_in, &result.borrow);
 201   return result;
 202 }
 203
 204 template <>
 205 LIBC_INLINE DiffBorrow<unsigned long>
 206 sub_with_borrow<unsigned long>(unsigned long a, unsigned long b,
 207                                unsigned long borrow_in) {
 208   DiffBorrow<unsigned long> result{0, 0};
 209   result.diff = __builtin_subcl(a, b, borrow_in, &result.borrow);
 210   return result;
 211 }
 212
 213 template <>
 214 LIBC_INLINE DiffBorrow<unsigned long long>
 215 sub_with_borrow<unsigned long long>(unsigned long long a, unsigned long long b,
 216                                     unsigned long long borrow_in) {
 217   DiffBorrow<unsigned long long> result{0, 0};
 218   result.diff = __builtin_subcll(a, b, borrow_in, &result.borrow);
 219   return result;
 220 }
 221
 222 #endif // LIBC_HAS_BUILTIN(__builtin_subc)
 223
 224 } // namespace __llvm_libc
 225
 226 #endif // LLVM_LIBC_SRC_SUPPORT_BUILTIN_WRAPPERS_H