| 1 | //===----------------------------------------------------------------------===// |
| 2 | // |
| 3 | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
| 4 | // See https://llvm.org/LICENSE.txt for license information. |
| 5 | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
| 6 | // |
| 7 | //===----------------------------------------------------------------------===// |
| 8 | /// |
| 9 | /// \file |
| 10 | /// Double-precision implementation of exp. |
| 11 | /// |
| 12 | //===----------------------------------------------------------------------===// |
| 13 | |
| 14 | #ifndef LLVM_LIBC_SRC___SUPPORT_MATH_EXP_DOUBLE_EVAL_H |
| 15 | #define LLVM_LIBC_SRC___SUPPORT_MATH_EXP_DOUBLE_EVAL_H |
| 16 | |
| 17 | #include "src/__support/CPP/bit.h" |
| 18 | #include "src/__support/FPUtil/FPBits.h" |
| 19 | #include "src/__support/FPUtil/double_double.h" |
| 20 | #include "src/__support/FPUtil/fp_bitwise.h" |
| 21 | #include "src/__support/FPUtil/multiply_add.h" |
| 22 | #include "src/__support/common.h" |
| 23 | #include "src/__support/macros/attributes.h" |
| 24 | #include "src/__support/macros/config.h" |
| 25 | #include "src/__support/macros/optimization.h" |
| 26 | #include "src/__support/macros/properties/cpu_features.h" |
| 27 | |
| 28 | #ifdef LIBC_MATH_HAS_SKIP_ACCURATE_PASS |
| 29 | #include "src/__support/math/exp_double_utils.h" |
| 30 | #else |
| 31 | #include "src/__support/math/exp_utils.h" |
| 32 | #endif // LIBC_MATH_HAS_SKIP_ACCURATE_PASS |
| 33 | |
| 34 | namespace LIBC_NAMESPACE_DECL { |
| 35 | namespace math { |
| 36 | namespace double_eval { |
| 37 | |
| 38 | LIBC_ALWAYS_INLINE double exp(double x) { |
| 39 | using FPBits = fputil::FPBits<double>; |
| 40 | FPBits xbits(x); |
| 41 | |
| 42 | uint64_t x_u = xbits.uintval(); |
| 43 | uint64_t x_abs = xbits.abs().uintval(); |
| 44 | |
| 45 | // Bound constants (with biased exponent and mantissa bits): |
| 46 | // - Tiny bound: 2^-53 = 0x1.0p-53 (for |x| < 2^-53, exp(x) rounds to 1.0 + x) |
| 47 | constexpr uint64_t TINY_BOUND = 0x3ca0'0000'0000'0000ULL; |
| 48 | // - Overflow bound: |
| 49 | // > round(log(2^1023 * (2 - 2^-52)), D, RU) = 0x1.62e42fefa39f0p+9 |
| 50 | // > round(log(2^1023 * (2 - 2^-52)), D, RD) = 0x1.62e42fefa39efp+9 |
| 51 | // > round(log(2^1023 * (2 - 2^-52)), D, RN) = 0x1.62e42fefa39efp+9 |
| 52 | // > round(exp(0x1.62e42fefa39f0p+9), D, RN) = +inf |
| 53 | constexpr uint64_t OVERFLOW_BOUND = 0x4086'2e42'fefa'39f0ULL; |
| 54 | // -0x1.62e42fefa39f0p+9: |
| 55 | constexpr uint64_t NEG_OVERFLOW_BOUND = 0xc086'2e42'fefa'39f0ULL; |
| 56 | // - Underflow bound: min denormal number / 2 = 2^-1075 |
| 57 | // > round(log(2^-1075), D, RN) = -0x1.74910d52d3052p+9 |
| 58 | constexpr uint64_t UNDERFLOW_BOUND = 0xc087'4910'd52d'3052ULL; |
| 59 | |
| 60 | // Normal range: 2^-53 <= |x| < 0x1.62e42fefa39f0p+9. |
| 61 | if (LIBC_UNLIKELY(x_abs - TINY_BOUND >= OVERFLOW_BOUND - TINY_BOUND)) { |
| 62 | // Exclude non-underflowing negative inputs in |
| 63 | // (UNDERFLOW_BOUND, NEG_OVERFLOW_BOUND]. |
| 64 | if (LIBC_LIKELY(x_u < NEG_OVERFLOW_BOUND || x_u >= UNDERFLOW_BOUND)) |
| 65 | return set_exceptional(x); |
| 66 | } |
| 67 | |
| 68 | // Now -0x1.74910d52d3052p+9 < x <= -0x1.0p-53 or |
| 69 | // 0x1.0p-53 <= x < 0x1.62e42fefa39f0p+9. |
| 70 | |
| 71 | // Range reduction: |
| 72 | // Let x = k * (log(2) / 2^N) + u |
| 73 | // in which: |
| 74 | // k = round(x * 2^N * log2(e)) |
| 75 | // hi = k >> N |
| 76 | // idx = k & (2^N - 1) |
| 77 | // then: |
| 78 | // exp(x) = 2^hi * 2^(idx / 2^N) * exp(u). |
| 79 | // |
| 80 | // Using ROUND_BIAS, ROUND_SHIFT, and ROUND_MASK (see exp_utils.h), we compute |
| 81 | // k_biased = fma(x, LOG2_E_SCALE, ROUND_BIAS) and extract in parallel: |
| 82 | // kd = (k_biased & ROUND_MASK) - ROUND_SHIFT |
| 83 | // hi = (int32_t)(k_bits >> 19) >> (13 + N) |
| 84 | // idx = (k_bits >> 32) & (2^N - 1). |
| 85 | constexpr double LOG2_E_SCALE = EXP_SCALE * LOG2_E_DD.hi; |
| 86 | |
| 87 | double k_biased = fputil::multiply_add(x, y: LOG2_E_SCALE, z: ROUND_BIAS); |
| 88 | double kd = fputil::fp_and(a: k_biased, b: ROUND_MASK) - ROUND_SHIFT; |
| 89 | uint64_t k_bits = cpp::bit_cast<uint64_t>(from: k_biased); |
| 90 | |
| 91 | int hi = static_cast<int32_t>(k_bits >> 19) >> (13 + EXP_N_BITS); |
| 92 | unsigned idx = static_cast<unsigned>(k_bits >> 32) & EXP_MASK; |
| 93 | |
| 94 | #ifdef LIBC_MATH_HAS_SKIP_ACCURATE_PASS |
| 95 | double t1 = fputil::multiply_add(kd, MLOG_2_EXP2_HI, x); // exact |
| 96 | double u = fputil::multiply_add(kd, MLOG_2_EXP2_MID, t1); |
| 97 | return exp2_eval(x, u, hi, idx); |
| 98 | #else // !LIBC_MATH_HAS_SKIP_ACCURATE_PASS |
| 99 | #ifdef LIBC_TARGET_CPU_HAS_FMA_DOUBLE |
| 100 | // With FMA, we use the full 53-bit: |
| 101 | // MLOG_2_HI_53 = -2^-7 * log(2) = -LOG_2_DD.hi * EXP_SCALE_INV (lsb = |
| 102 | // 2^-60) |
| 103 | // to compute: |
| 104 | // u = x - k * 2^-7 * log(2) ~ t1 + d |
| 105 | // where: |
| 106 | // t1 = fma(kd, MLOG_2_HI_53, x) |
| 107 | // d = kd * MLOG_2_LO_53 (|d| < 2^18 * 2^-62 = 2^-44). |
| 108 | // |
| 109 | // For k != 0, |x| >= 2^-8 * log(2) > 2^-9 so lsb(x) >= 2^-61, and since kd is |
| 110 | // an integer, lsb(kd * MLOG_2_HI_53) >= 2^-60. Because |t1| < 2^-8, every |
| 111 | // non-zero bit of x + kd * MLOG_2_HI_53 lies in [2^-61, 2^-9] (at most 53 |
| 112 | // bits), so: |
| 113 | // t1 = fma(kd, MLOG_2_HI_53, x) |
| 114 | // is exact. |
| 115 | // |
| 116 | // In exp2_eval, P(u.hi) is evaluated at u.hi = t1 alone. Writing: |
| 117 | // exp(t1 + d) = exp(t1) * exp(d) |
| 118 | // ~ (1 + t1 + t1^2 * P(t1)) * (1 + d) |
| 119 | // ~ 1 + t1 + d * (1 + t1) + t1^2 * P(t1), |
| 120 | // we fold the linear cross-term t1 * d into: |
| 121 | // u.lo = fma(t1, d, d), |
| 122 | // bounding the omitted term: |
| 123 | // |t1^2 * P(t1) * d| < 2^-63. |
| 124 | constexpr double MLOG_2_HI_53 = -LOG_2_DD.hi * EXP_SCALE_INV; |
| 125 | constexpr double MLOG_2_LO_53 = -LOG_2_DD.lo * EXP_SCALE_INV; |
| 126 | |
| 127 | double t1 = fputil::multiply_add(kd, MLOG_2_HI_53, x); // exact |
| 128 | double d = kd * MLOG_2_LO_53; |
| 129 | double u_lo = fputil::multiply_add(t1, d, d); |
| 130 | DoubleDouble u = {u_lo, t1}; |
| 131 | #else // !LIBC_TARGET_CPU_HAS_FMA_DOUBLE |
| 132 | // Without FMA, we use a 35-bit-precision high part MLOG_2_EXP2_HI (with lsb = |
| 133 | // 2^-42) so that: |
| 134 | // kd * MLOG_2_EXP2_HI |
| 135 | // has at most 18 + 35 = 53 significant bits and is exact in double precision |
| 136 | // for |kd| < 2^18, and: |
| 137 | // t1 = x + kd * MLOG_2_EXP2_HI |
| 138 | // is exact by Sterbenz's lemma. |
| 139 | // |
| 140 | // We then split t1 at 2^-30 before adding t2 = kd * MLOG_2_EXP2_MID: |
| 141 | // u_hi = (t1 + SPLIT_30) - SPLIT_30 (exact, lsb = 2^-30) |
| 142 | // t1_lo = t1 - u_hi (exact, |t1_lo| <= 2^-31) |
| 143 | // u_lo = t1_lo + t2 (|u_lo| < 2^-26). |
| 144 | // This gives lsb(u_hi) >= 2^-30 so that m_hi * u_hi is exact in exp2_eval, |
| 145 | // while keeping |u_lo| < 2^-26 so the rounding error of: |
| 146 | // u_lo = t1_lo + t2 |
| 147 | // is bounded by 2^(-26 - 53) = 2^-79. |
| 148 | double t1 = fputil::multiply_add(x: kd, y: MLOG_2_EXP2_HI, z: x); // exact |
| 149 | double t2 = kd * MLOG_2_EXP2_MID; |
| 150 | double u_hi = (t1 + SPLIT_30) - SPLIT_30; // exact, lsb = 2^-30 |
| 151 | double t1_lo = t1 - u_hi; // exact |
| 152 | double u_lo = t1_lo + t2; |
| 153 | DoubleDouble u = {.lo: u_lo, .hi: u_hi}; |
| 154 | #endif // LIBC_TARGET_CPU_HAS_FMA_DOUBLE |
| 155 | return exp2_eval(x, u, hi, idx, err_d: EXP_ERR_D, log2_base: &LOG2_E_192); |
| 156 | #endif // LIBC_MATH_HAS_SKIP_ACCURATE_PASS |
| 157 | } |
| 158 | |
| 159 | } // namespace double_eval |
| 160 | } // namespace math |
| 161 | } // namespace LIBC_NAMESPACE_DECL |
| 162 | |
| 163 | #endif // LLVM_LIBC_SRC___SUPPORT_MATH_EXP_DOUBLE_EVAL_H |
| 164 | |