Math support in core

[japaric]

Background

Currently the core crate doesn't provide support for mathematical functions like sqrt or sin.
To do math in a #![no_std] program one has the following options:

• Link to a C implementation of libm, i.e. libm.a. This is cumbersome as the programmer needs to
  obtain a compiled version of libm for their target, or compile libm themselves which implies a C
  cross toolchain when the target system and the build system are not the same architecture / OS.

• Use a pure Rust implementation of libm, like the libm crate. On stable, (a) the performance of
  such implementation won't be on par with a C implementation, or (b) to achieve the same
  performance the user would require a C (cross) toolchain.

To elaborate on (a) and (b). Consider the following contrived program that computes the square root
of a number:

#![no_std]

extern crate libm;

use core::ptr;

use libm::F32Ext;

#[no_mangle]
pub unsafe fn foo() {
    // volatile memory accesses to prevent the compiler from optimizing away everything
    let x: f32 = ptr::read_volatile(0x2000_0000 as *const _);
    let y = x.sqrt();
    ptr::write_volatile(0x2000_1000 as *mut _, y);
}

When compiled for the thumbv7em-none-eabihf target it produces the following machine code:

00000000 <foo>:
   0:   f04f 5000       mov.w   r0, #536870912  ; 0x20000000
   4:   ed90 0a00       vldr    s0, [r0]
   8:   ee10 1a10       vmov    r1, s0
   c:   f001 40ff       and.w   r0, r1, #2139095040     ; 0x7f800000
  10:   f1b0 4fff       cmp.w   r0, #2139095040 ; 0x7f800000
  14:   d108            bne.n   28 <foo+0x28>
  16:   ee00 0a00       vmla.f32        s0, s0, s0
  (..)
 2f4:   ed80 0a00       vstr    s0, [r0]
 2f8:   4770            bx      lr

This is extremely inefficient machine code because the target has a hardware FPU that supports
computing the square root in a single instruction. Ideally, the program should compile down to the
following machine code:

00000000 <foo>:
   0:   f04f 5000       mov.w   r0, #536870912  ; 0x20000000
   4:   ed90 0a00       vldr    s0, [r0]
   8:   f241 0000       movw    r0, #4096       ; 0x1000
   c:   f2c2 0000       movt    r0, #8192       ; 0x2000
  10:   eeb1 0ac0       vsqrt.f32       s0, s0
  14:   ed80 0a00       vstr    s0, [r0]
  18:   4770            bx      lr

If the target had access to the standard library the program would compile down to that machine code
because the implementation of f32.sqrt in std looks like this:

#![feature(core_intrinsics)]

use std::intrinsics;

impl f32 {
    fn sqrt(self) -> Self {
        intrinsics::sqrtf32(self)
    }
}

sqrtf32 is an unstable, thin wrapper around an LLVM intrinsic that either compiles down to a
hardware implementation of square root if the target architecture supports it in its instruction
set, or it produces a call to the sqrtf routine if it doesn't (*). std makes use of 30+ of such
LLVM intrinsics for performance of math functions.

(*) The llvm.sqrt.* LLVM intrinsic, which sqrtf32 wraps, is not quite specified like that but
that's the observable effect.

The libm crate can't make use of this intrinsic on stable because it's unstable and feature
gated. However, the libm crate could replicate the behavior of the sqrtf32 intrinsic using
conditional compilation and external assembly files as shown below:

// crate: libm

// NOTE heavily simplified because it ignores architectures other than ARM
impl F32Ext for f32 {
    #[cfg(target_arch = "arm")]
    fn sqrt(self) -> Self {
        extern "C" {
            // provided by an external assembly file
            fn vsqrt_f32(x: f32) -> f32;
        }

        unsafe { vsqrt_f32(self) }
    }

    #[cfg(not(target_arch = "arm"))]
    fn sqrt(self) -> Self {
        // software implementation
    }
}

But this would heavily complicate the implementation of the libm crate, which would likely
introduce bugs. Also, as it's not possible to use inline assembly (asm!) on stable the vsqrt.f32
instruction would have to be invoked via FFI and an external assembly file. External assembly files
mean that the user would require a C (cross) toolchain to build the crate negating the main benefit
of using a pure Rust implementation of libm.

Possible solutions

I see two options for improving the situation here:

a. We stabilize the family of sqrtf32 LLVM intrinsics. This way crates like libm can achieve the
performance of the std implementation on stable without requiring complex conditional
compilation and C toolchains. Or,

b. We move all the existing math support from std to core. For the user this means that e.g.
f32.sqrt will also work in #![no_std] programs.

Option (a) is kind of bad (maybe?) for alternative backends like cranelift as they would have to
support / implement these LLVM intrinsics to be on parity with the rustc+LLVM compiler.

Option (b) requires us (*) to provide an implementation of math functions (symbols) like sqrtf
for targets that do not link to libm by default. If we don't do this those targets will hit
"undefined reference to sqrtf" linker errors when using math methods like f32.sqrt.

(*) "us" as in: we must provide symbols like sqrtf in the compiler-builtins crate. Note that we
are already providing such symbols for the wasm32-unknown-unknown target, and we are
using the libm crate to do that.

If we go ahead with option (b) we must be careful to not provide the math symbols in
compiler-builtins for targets that are currently using system libm (e.g.
x86_64-unknown-linux-gnu). Because if we do provide the symbols then all existing programs will
start using the libm crate implementation instead of the system libm implementation -- this is due
to how we invoke the linker: libcompiler_builtins.rlib appears before -lm in the linker
arguments -- and that may degrade performance in some cases where system libm has architecture
optimized implementations of some functions.

With option (b) I believe that #![no_std] programs that are currently linking to some C
implementation of libm for math support will end up using the libm crate implementation as a side
effect. I don't see a way to avoid this: even if we mark the math symbols in compiler-builtins as
weak the way we invoke the linker will cause the program to use the libm crate implementation.

Final thoughts

IMO, math support should be in the core crate as it doesn't depend on OS, or I/O, abstractions
like other std-only API does (e.g. std::fs, std::net). Also, std makes math like sqrt feel built-in because the functionality is provided as inherent methods -- it feels weird that such "built-in" functionality is not available in #![no_std].

---

Thoughts? Should we do (a) or (b)? Or is there some other solution? Or should we leave math out of core?

cc @SimonSapin (T-libs), @jethrogb @Ericson2314 (T-portability), @joshtriplett @korken89 (some stakeholders)

[SimonSapin]

Previous discussion of this: rust-lang/rust#50145

I don’t understand the difference between option (a) and (b), they seem to be effectively the same. Stabilizing an intrinsic is typically done by adding a stable (and safe) wrapper function. The existing support in std is a stable wrapper function/method.

feel built-in because the functionality is provided as inherent methods

For what it’s worth we have other precedent of inherent methods not being present in libcore, for example [T]::to_vec.

[nagisa]

Seems like this would be a non-problem with a portability lint thing. In that case the floating point functions could be cfgd away like atomics are. On Jul 23, 2018 11:27 AM, "Simon Sapin" <notifications@github.com> wrote: Previous discussion of this: rust-lang/rust#50145 <rust-lang/rust#50145> I don’t understand the difference between option (a) and (b), they seem to be effectively the same. Stabilizing an intrinsic is typically done by adding a stable (and safe) wrapper function. The existing support in std is a stable wrapper function/method. feel built-in because the functionality is provided as inherent methods For what it’s worth we have other precedent of inherent methods not being present in libcore, for example [T]::to_vec. — You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub <#2505 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AApc0uFh-Fc1p7V6fapv43cqAUcvXg6oks5uJYjagaJpZM4VafqZ> .

[hanna-kruppe]

Option (a) is kind of bad (maybe?) for alternative backends like cranelift as they would have to
support / implement these LLVM intrinsics to be on parity with the rustc+LLVM compiler.

A cranelift backend for rustc already needs to gracefully handle a long list of rustc intrinsics. In this case always translating the rustc intrinsic to a sqrt call should be easy & functional, it wouldn't even have to impact cranelift code. (cc @eddyb)

[japaric]

@SimonSapin

I don’t understand the difference between option (a) and (b), they seem to be effectively the same.

They are pretty similar but they are not exactly the same. In option (b) core becomes the
provider of math functionality. With option (a) any crate can provide math functionality that's on
par with the performance of std (cf. sqrtf32 example).

Thinking about it some more I think option (a) will also run into the problems that option (b) has
with respect to shadowing system libm.

Also, I originally thought (but didn't comment above) that having option (a) would good because the
ecosystem could grow architecture optimized versions of the libm crate and a user would be free to
pick one of those for their project. I don't think that would work well on stable because
architecture optimized versions would very likely involve external assembly files, which require a C
cross toolchain. Additionally, having a bunch of crates like libm-x86_64 and libm-arm-neon on
crates.io would probably lead to fragmentation. It seems better to have core as the only provider
of math functions and to have everyone contribute architecture optimized implementations to it --
core can make use of unstable features like asm! and global_asm! and it comes pre-compiled so
it doesn't add a dependency on a C toolchain.

TL;DR Option (b) (still) sounds best to me.

For what it’s worth we have other precedent of inherent methods not being present in libcore, for
example [T]::to_vec.

I think that's the only inherent method that involves a type that's not built into the language
(Vec), which makes it a bit of a special case / exception. I believe to_vec was turned into an
inherent method before the ToOwned trait was added to the standard library, and I think that
having ToOwned in the std prelude, and potentially in an alloc (pseudo) prelude, reduces or
eliminates the need for it.

@nagisa

I cc-ed T-portability people because they also look into issues that aim to close the gap between
standard programs and no_std programs like having io::{Read,Write} in core, and less so
because this is related to the portability lint.

I think math functions should not be cfg-ed away. Even if the target doesn't have a FPU, software
emulation of floats is always possible; 128-bit integer support is in a similar situation and we
don't cfg that today. (I know some targets have problems with LLVM bugs that may prevent core
compiling for them if it gained math functions; in that case we could temporarily cfg away math
support until the LLVM bug is fixed. I believe pure MIR rlibs would also sidestep the LLVM problem
and I would prefer that over using #[cfg])

@rkruppe

Right, other backends will have to port other Rust intrinsics as things stand today. Perhaps, 30
more intrinsics is not that much extra work.

---

Finally, this is a bit of speculation because I have not tested it but I think that putting the math
symbols / functions in core, rather than in compiler-builtins, may let the compiler perform
inlining -- the intrinsics / functions in compiler-builtins never get inlined, not even with LTO
enabled, because that crate is always a separate object file.

[SimonSapin]

For what it’s worth we have other precedent of inherent methods not being present in libcore, for example [T]::to_vec.

I think that's the only inherent method that involves a type that's not built into the language
(Vec), which makes it a bit of a special case / exception.

Currently there are 21 inherent methods defined on primitive types outside of libcore because they involve Vec or String in their signature or in their implementation.

This doesn’t invalidate this issue, I think having math support in libcore would be good. I’m only saying it wouldn’t entirely remove the weirdness of inherent methods being "magically" added just by adding a dependency on a non-core standard library crate.

#[lang = "slice_alloc"]
impl<T> [T] {
    pub fn sort(&mut self) where T: Ord {…}
    pub fn sort_by<F>(&mut self, mut compare: F) where F: FnMut(&T, &T) -> Ordering {…}
    pub fn sort_by_key<K, F>(&mut self, mut f: F) where F: FnMut(&T) -> K, K: Ord {…}
    pub fn sort_by_cached_key<K, F>(&mut self, f: F) where F: FnMut(&T) -> K, K: Ord {…}
    pub fn to_vec(&self) -> Vec<T>  where T: Clone {…}
    pub fn into_vec(self: Box<Self>) -> Vec<T> {…}
    pub fn repeat(&self, n: usize) -> Vec<T> where T: Copy {…}
}

#[lang = "slice_u8_alloc"]
impl [u8] {
    pub fn to_ascii_uppercase(&self) -> Vec<u8> {…}
    pub fn to_ascii_lowercase(&self) -> Vec<u8> {…}
}

#[lang = "str_alloc"]
impl str {
    pub fn into_boxed_bytes(self: Box<str>) -> Box<[u8]> {…}
    pub fn replace<'a, P: Pattern<'a>>(&'a self, from: P, to: &str) -> String {…}
    pub fn replacen<'a, P: Pattern<'a>>(&'a self, pat: P, to: &str, count: usize) -> String {…}
    pub fn to_lowercase(&self) -> String {…}
    pub fn to_uppercase(&self) -> String {…}
    pub fn escape_debug(&self) -> String {…}
    pub fn escape_default(&self) -> String {…}
    pub fn escape_unicode(&self) -> String {…}
    pub fn into_string(self: Box<str>) -> String {…}
    pub fn repeat(&self, n: usize) -> String {…}
    pub fn to_ascii_uppercase(&self) -> String {…}
    pub fn to_ascii_lowercase(&self) -> String {…}
}

[SimonSapin]

Back on topic:

@japaric, I think I don’t quite understand how LLVM intrinsics, the libm crate, and system/toolchain-provided -lm C library all interact with each other, in your (a) and (b) options. In particular:

We stabilize the family of sqrtf32 LLVM intrinsics. This way crates like libm can achieve

Do you mean that the libm crate would call the intrinsic? Then what would provide the sqrtf symbol called by the intrinsic on targets that don’t have a dedicated instruction?

(Note that rust-lang/rust#27823 moved a number of f32 and f64 methods from libcore to libstd in order to make libcore not depend on a libm C library that needs to be provided separately.)

Regardless, I think this is largely independent of what user-facing API we want to stabilize, which at first I thought was what your (a) v.s. (b) was about:

• Unsafe functions in the core::intrinsics modules, or
• Safe inherent methods on the f32 and f64 types.

I think the latter API is obviously superior, assuming identical implementations.

[SimonSapin]

CC @alexcrichton who discussed this in rust-lang/rust#32110 (comment).

[jethrogb]

@japaric is sqrtf32 the only intrinsic that needs to be stabilized or is that just an example and there's others for other math functions?

[alexcrichton]

I do sort of agree with @japaric about the goal here of basically moving everything to libcore, but my main point of hesitation would be performance and accuracy of these intrinsics vs various libm implementations. @japaric would it be possible to collect some data about the efficiency of the various implementations in the Rust libm vs some native libm implementations? I'm less worried about things like sqrt which have intrinsics and can be optimized, but am more interested in things like trigonometric functions which don't have inherent compiler/architecture support. I think it'd also be interesting to check out the performance across platforms, it may be the case that the Rust libm is mega-fast on OSX (or something like that) but super slow on Linux

[SimonSapin]

@jethrogb It’s an example. This is what’s in src/libstd/f64.rs today. f32 is similar.

#[lang = "f64_runtime"]
impl f64 {
    pub fn floor(self) -> f64 {…} // intrinsics::floorf64
    pub fn ceil(self) -> f64 {…} // intrinsics::ceilf64
    pub fn round(self) -> f64 {…} // intrinsics::roundf64
    pub fn trunc(self) -> f64 {…} // intrinsics::truncf64
    pub fn abs(self) -> f64 {…} // intrinsics::fabsf64
    pub fn signum(self) -> f64 {…} // intrinsics::copysignf64
    pub fn mul_add(self, a: f64, b: f64) -> f64 {…} // intrinsics::fmaf64
    pub fn powi(self, n: i32) -> f64 {…} // intrinsics::powif64
    pub fn powf(self, n: f64) -> f64 {…} // intrinsics::powf64
    pub fn sqrt(self) -> f64 {…} // intrinsics::sqrtf64
    pub fn exp(self) -> f64 {…} // intrinsics::expf64
    pub fn exp2(self) -> f64 {…} // intrinsics::exp2f64
    pub fn ln(self) -> f64 {…} // intrinsics::logf64
    pub fn log2(self) -> f64 {…} // intrinsics::log2f64
    pub fn log10(self) -> f64 {…} // intrinsics::log10f64
    pub fn sin(self) -> f64 {…} // intrinsics::sinf64
    pub fn cos(self) -> f64 {…} // intrinsics::cosf64

    pub fn abs_sub(self, other: f64) -> f64 {…} // cmath::fdim
    pub fn cbrt(self) -> f64 {…} // cmath::cbrt
    pub fn hypot(self, other: f64) -> f64 {…} // cmath::hypot
    pub fn tan(self) -> f64 {…} // cmath::tan
    pub fn asin(self) -> f64 {…} // cmath::asin
    pub fn acos(self) -> f64 {…} // cmath::acos
    pub fn atan(self) -> f64 {…} // cmath::atan
    pub fn atan2(self, other: f64) -> f64 {…} // cmath::atan2
    pub fn exp_m1(self) -> f64 {…} // cmath::expm1
    pub fn ln_1p(self) -> f64 {…} // cmath::log1p
    pub fn sinh(self) -> f64 {…} // cmath::sinh
    pub fn cosh(self) -> f64 {…} // cmath::cosh
    pub fn tanh(self) -> f64 {…} // cmath::tanh

    // Based on other methods, but not directly on intrinsics or cmatch
    pub fn log(self, base: f64) -> f64 {…}
    pub fn fract(self) -> f64 {…}
    pub fn div_euc(self, rhs: f64) -> f64 {…}
    pub fn mod_euc(self, rhs: f64) -> f64 {…}
    pub fn sin_cos(self) -> (f64, f64) {…}
    pub fn asinh(self) -> f64 {…}
    pub fn acosh(self) -> f64 {…}
    pub fn atanh(self) -> f64 {…}
}

Where cmath contains #[link_name = "m"] extern {…} bindings, and Rust intrinsics map to LLVM intrinsics:

$ grep "llvm.*f64" src/librustc_codegen_llvm/intrinsic.rs
        "sqrtf64" => "llvm.sqrt.f64",
        "powif64" => "llvm.powi.f64",
        "sinf64" => "llvm.sin.f64",
        "cosf64" => "llvm.cos.f64",
        "powf64" => "llvm.pow.f64",
        "expf64" => "llvm.exp.f64",
        "exp2f64" => "llvm.exp2.f64",
        "logf64" => "llvm.log.f64",
        "log10f64" => "llvm.log10.f64",
        "log2f64" => "llvm.log2.f64",
        "fmaf64" => "llvm.fma.f64",
        "fabsf64" => "llvm.fabs.f64",
        "copysignf64" => "llvm.copysign.f64",
        "floorf64" => "llvm.floor.f64",
        "ceilf64" => "llvm.ceil.f64",
        "truncf64" => "llvm.trunc.f64",
        "rintf64" => "llvm.rint.f64",
        "nearbyintf64" => "llvm.nearbyint.f64",
        "roundf64" => "llvm.round.f64",

cmath binds to a libm library that is expected to be provided by the C toolchain, and LLVM intrinsics may compile to calls that do the same.

[hanna-kruppe]

However, note that (to the best of my knowledge) the vast majority of those intrinsics are lowered to libcalls rather than single instructions on most or all architectures. They are still useful to LLVM for optimizations (constant folding, code motion and dead code elimination based on the fact that they don't access errno, etc.), but most of them don't impact instruction selection the way @japaric demonstrated with sqrt.

[japaric]

@SimonSapin

I think I don’t quite understand how LLVM intrinsics, the libm crate, and
system/toolchain-provided -lm C library all interact with each other

The (observable) behavior of the sqrtf32 intrinsic is depicted below:

// user writes
fn my_sqrt(x: f32) -> f32 {
    intrinsics::sqrtf32(x)
}

// For ARM Cortex-M4F, LLVM lowers `my_sqrt` to
fn my_sqrt(x: f32) -> f32 {
    let y;
    unsafe {
        asm!("vsqrt $0, $1" : "=w"(y) : "w"(x));
    }
    y
}

// For targets that don't have an instruction for the sqrt operation, LLVM lowers `my_sqrt` to
fn my_sqrt(x: f32) -> f32 {
    extern "C" {
        fn sqrtf(_: f32) -> f32;
    }

    unsafe {
        sqrtf(x)
    }
}

On targets like x86_64 Linux std contains an extern block with #[link(name = "m")]. This makes
rustc pass -lm to the linker and libm.a provides the sqrtf symbol.

Do you mean that the libm crate would call the intrinsic?

Yes, the libm crate would use intrinsics::sqrtf32 to implement F32Ext.sqrt.

Then what would provide the sqrtf symbol called by the intrinsic on targets that don’t have a
dedicated instruction?

The libm crate itself can do that:

impl F32Ext for f32 {
    fn sqrt(x: f32) -> f32 {
        unsafe {
            intrinsics::sqrtf32(x)
        }
    }
}

#[no_mangle]
pub extern "C" fn sqrtf(x: f32) -> f32 {
    // Software implementation
}

---

@alexcrichton

@japaric would it be possible to collect some data about the efficiency of the various
implementations in the Rust libm vs some native libm implementations?

We can, but we don't have to force our libm implementation on the targets that are currently using
the system libm.a. For now, we can hold off on providing symbols like sqrtf in compiler-builtins
for those targets (see below) and they would see no change in performance / accuracy.

// crate: core
impl f32 {
    fn sqrt(self) -> Self {
        unsafe { intrinsics::sqrtf32(self) }

    }
}

// crate: compiler-builtins
#[cfg(any(target_os = "none", target_os = "unknown"))]
#[no_mangle]
pub fn sqrtf(x: f32) -> f32 {
    // Software implementation
}

Targets like x86_64-unknown-linux-gnu would continue to use the sqrtf symbol that comes from
-lm.

Also, right off the bat, I can tell you that most of the f32 math functions that we have ported
from MUSL have pretty bad runtime performance on 32-bit architectures because they internally use
f64 operations / functions. We want to replace the implementations of f32 ops with a port of
newlib. newlib implements f32 functions using only f32 operations. See rust-lang/libm#118 for
details.

[SimonSapin]

@japaric So your (a) proposal is adding APIs to libcore that, when used, adds a dependency on a symbol being provided externally somehow. The precedent of rust-lang/rust#27823 and rust-lang/rust#32110 (comment) seems to be that libcore should avoid precisely this.

[Ericson2314]

Agree with japaric that plan (b) is the way to. Normally [very much! Haha] want things to be stable code, and hopefully move to nursery crate, but the case of polyfilling code that may just be generated instead is clearly a special case, where the compiler coupling is inherent to the problem. And tying ourselves to LLVM in stable interfaces is definitely no good.

Let my also through out that on the general front of the compiler-builtins–core dependency cycle, #2492 may be of some assistance. That might remove the downsides of plan (b) eventually.

[alexcrichton]

@japaric

For now, we can hold off on providing symbols like sqrtf in compiler-builtins
for those targets (see below) and they would see no change in performance / accuracy.

True! We don't have a great way of adding -lm to core though, on targets like x86_64-unknown-linux-gnu. :(