]> git.lizzy.rs Git - rust.git/commit - src/tools/miri
Rollup merge of #85017 - clarfonthey:carrying_widening, r=m-ou-se
authorMara Bos <m-ou.se@m-ou.se>
Tue, 31 Aug 2021 15:54:52 +0000 (17:54 +0200)
committerGitHub <noreply@github.com>
Tue, 31 Aug 2021 15:54:52 +0000 (17:54 +0200)
commite7a247dba431d6fa505ca0393ffcab5bfc65e9cb
treee8808a25e900f48cfb286b2fa4bc315b4588ac18
parent76d18cfb8945f824c8777e04981e930d2037954e
parentcc15047d505c2cb6bba7475b18450f9785a78d7e
Rollup merge of #85017 - clarfonthey:carrying_widening, r=m-ou-se

Add carrying_add, borrowing_sub, widening_mul, carrying_mul methods to integers

This comes in part from my own attempts to make (crude) big integer implementations, and also due to the stalled discussion in [RFC 2417](https://github.com/rust-lang/rfcs/pull/2417). My understanding is that changes like these are best offered directly as code and then an RFC can be opened if there needs to be more discussion before stabilisation. Since all of these methods are unstable from the start, I figured I might as well offer them now.

I tried looking into intrinsics, messed around with a few different implementations, and ultimately concluded that these are "good enough" implementations for now to at least put up some code and maybe start bikeshedding on a proper API for these.

For the `carrying_add` and `borrowing_sub`, I tried looking into potential architecture-specific code and realised that even using the LLVM intrinsics for `addcarry` and `subborrow` on x86 specifically, I was getting exactly the same assembly as the naive implementation using `overflowing_add` and `overflowing_sub`, although the LLVM IR did differ because of the architecture-specific code. Longer-term I think that they would be best suited to specific intrinsics as that would make optimisations easier (instructions like add-carry tend to use implicit flags, and thus can only be optimised if they're done one-after-another, and thus it would make the most sense to have compact intrinsics that can be merged together easily).

For `widening_mul` and `carrying_mul`, for now at least, I simply cast to the larger type and perform arithmetic that way, since we currently have no intrinsic that would work better for 128-bit integers. In the future, I also think that some form of intrinsic would work best to cover that case, but for now at least, I think that they're "good enough" for now.

The main reasoning for offering these directly to the standard library even though they're relatively niche optimisations is to help ensure that the code generated for them is optimal. Plus, these operations alone aren't enough to create big integer implementations, although they could help simplify the code required to do so and make it a bit more accessible for the average implementor.

That said, I 100% understand if any or all of these methods are not desired simply because of how niche they are. Up to you. 🤷🏻
library/core/src/num/int_macros.rs
library/core/src/num/mod.rs
library/core/src/num/uint_macros.rs