rust-num / num-bigint

Big integer types for Rust
Apache License 2.0
534 stars 187 forks source link

Do not turn on LLVM intrinsic dependency by default #206

Closed shamatar closed 4 months ago

shamatar commented 3 years ago

At the moment build script turns on a feature that uses LLVM instrinsics for additions. Unfortunately cranelift backend does not support those instinsics (and potentially other) yet, so can it be moved to an explicit feature?

https://github.com/rust-num/num-bigint/blob/125fbbdb4887b995b0fe566b139f36196b5735b5/build.rs#L27-L30

Also, one can avoid calling intrinsics at all. E.g. this PR to the Rust itself https://github.com/rust-lang/rust/pull/85017 introduces a function that optimized to add/adc chain by LLVM and does not use any intrinsics at all (copying for completeness)

#[inline]
pub const fn carrying_add(self, rhs: u64, carry: bool) -> (u64, bool) {
    // note: longer-term this should be done via an intrinsic, but this has been shown
    //   to generate optimal code for now, and LLVM doesn't have an equivalent intrinsic
    let (a, b) = self.overflowing_add(rhs);
    let (c, d) = a.overflowing_add(carry as u64);
    (c, b | d)
}
cuviper commented 3 years ago

If we can structure the code such that LLVM does a better job itself, that would be far more preferable than using intrinsics.

cuviper commented 3 years ago

I just found that cargo miri doesn't like the intrinsic calls either:

error: unsupported operation: can't call foreign function: llvm.x86.addcarry.64
   --> [...]/core/src/../../stdarch/crates/core_arch/src/x86_64/adx.rs:21:18
    |
21  |     let (a, b) = llvm_addcarry_u64(c_in, a, b);
    |                  ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ can't call foreign function: llvm.x86.addcarry.64
    |
    = help: this is likely not a bug in the program; it indicates that the program performed an operation that the interpreter does not support

    = note: inside `core::arch::x86_64::_addcarry_u64` at [...]/core/src/../../stdarch/crates/core_arch/src/x86_64/adx.rs:21:18
note: inside `biguint::addition::adc` at src/biguint/addition.rs:24:14
   --> src/biguint/addition.rs:24:14
    |
24  |     unsafe { arch::_addcarry_u64(carry, a, b, out) }
    |              ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
clarfonthey commented 3 years ago

Fun story, me making that change was explicitly the result of looking at the implementation here in this crate and wanting the code to be more easily usable without relying on intrinsics. Hopefully at some point in the future we can lower the code to a reliable Rust intrinsic that works properly on all targets.

cuviper commented 4 months ago

AFAICT, those intrinsics are now supported by rustc_codegen_cranelift, rustc_codegen_gcc, and miri (and of course LLVM), and I've still found them to be faster than what the standard library is using. I'm updating the fallback implementations in #308 to copy that though.