[RFC] Adding division/modulo on arbitrary precision integers to libgcc
Hello! We would like to add support for division/modulo on large arbitrary precision integers to libgcc/compiler-rt as required by C23's _BitInt type [0]. >From what I know, gcc doesn't yet support C23 _BitInt, but we would still like to ensure that libgcc and compiler-rt can stay compatible in the future. We created a prototype in compiler-rt [1], which uses the following declarations: /// Computes the unsigned division of a / b for two large integers /// composed of n significant words. /// Writes the quotient to quo and the remainder to rem. /// /// \param quo The quotient represented by n words. Must be non-null. /// \param rem The remainder represented by n words. Must be non-null. /// \param a The dividend represented by n + 1 words. Must be non-null. /// \param b The divisor represented by n words. Must be non-null. /// \note The word order is in host endianness. /// \note Might modify a and b. /// \note The storage of 'a' needs to hold n + 1 elements because some /// implementations need extra scratch space in the most significant word. /// The value of that word is ignored. void __udivmodei5(uint32_t *quo, uint32_t *rem, uint32_t *a, uint32_t *b, unsigned n); /// Computes the signed division of a / b. /// See __udivmodei5 for details. void __divmodei5(uint32_t *quo, uint32_t *rem, uint32_t *a, uint32_t *b, unsigned n); The current prototype requires the compiler backend to first promote large integers to a multiple of 32 bits. The extra word of storage in argument `a` is required to allow implementations to use Knuth's algorithm efficiently. We are not fixed on the current function prototypes, and would like to take your feedback. E.g. is the naming of the functions in line with the scheme used by libgcc? Best wishes, Matthias CC'ing Martin Liska as recommended by MaskRay on the PR [0] https://www.open-std.org/jtc1/sc22/wg14/www/docs/n2763.pdf [1] https://reviews.llvm.org/D120327#change-mseSeWmhjTZf Dr. Matthias Gehre SMTS Software Development Engineer | AMD Adaptive Computing Tools -- 2485 Augustine Drive, Santa Clara, CA 95054 Facebook | Twitter | amd.com
AW: [RFC] Adding division/modulo on arbitrary precision integers to libgcc
On Fri, May 06, 2022 at 02:09:21PM +, Matthias Gehre via Gcc wrote: > /// \param quo The quotient represented by n words. Must be non-null. > /// \param rem The remainder represented by n words. Must be non-null. > /// \param a The dividend represented by n + 1 words. Must be non-null. > /// \param b The divisor represented by n words. Must be non-null. > > /// \note The word order is in host endianness. > /// \note Might modify a and b. > /// \note The storage of 'a' needs to hold n + 1 elements because some > /// implementations need extra scratch space in the most significant > word. > /// The value of that word is ignored. > void __udivmodei5(uint32_t *quo, uint32_t *rem, uint32_t *a, > uint32_t *b, unsigned n); > > /// Computes the signed division of a / b. > /// See __udivmodei5 for details. > void __divmodei5(uint32_t *quo, uint32_t *rem, uint32_t *a, uint32_t *b, > unsigned n); > Sizes certainly should be with size_t, not unsigned type. Agreed > Rather than uint32_t, wouldn't using the word size (64-bit for lp64, 32-bit for ilp32) be better? Is there a portable way to specify this in C? (size_t, uintptr_t?) And is the word size clearly defined for each target? (I'm not a backend expert). > And I really don't like the N + 1 stuff you're proposing, at least for > _BigInts that would be represented as an array of those word etc. elements > from least to most significant (or vice versa? That really needs to be > specified too), if they are same precision having to copy one of them just > to get the extra scratch is bad. Yes, that's a trade-off. Knuth algorithm is generally a good choice, but not having the extra scratch space would introduce more branches into it. Also, the proposed __udivmodei5 is allowed to overwrite the inputs, so you might need to copy them anyways. I actually didn't have this N + 1 initially, but then I got a comment on the compiler-rt review, and added it subsequently. Personally, I don't mind either way.
AW: [RFC] Adding division/modulo on arbitrary precision integers to libgcc
> Note that each architecture also needs to specify its _BitInt ABI > (including such things as whether the values of padding bits inside the > size of the _BitInt type, or outside that size but within a register used > for argument passing or return, have specified values or are arbitrary). > HJ has a proposal for x86_64 on a branch of the ABI, but it hasn't been > merged to master yet. Thanks, I didn't know that this is currently in progress. This is still slightly different, because the ABI can choose to make different choices for _BitInt(N) depending on N, but here we need to specify an interface that works independent of N. > This proposed interface doesn't say anything about what aliasing is or > isn't permitted among the four arrays pointed to. Good catch. I would lean into saying that none of the four arrays must alias because allowing them to alias would require most implementations to allocate extra scratch space. What do you think? -- Joseph S. Myers jos...@codesourcery.com
