[RFC] Adding division/modulo on arbitrary precision integers to libgcc

[RFC] Adding division/modulo on arbitrary precision integers to libgcc

[Matthias Gehre]

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

Re: [RFC] Adding division/modulo on arbitrary precision integers to libgcc

[Joseph Myers]

On Fri, 6 May 2022, Matthias Gehre via Gcc wrote:

> 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].

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.

> /// 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.

This proposed interface doesn't say anything about what aliasing is or 
isn't permitted among the four arrays pointed to.

-- 
Joseph S. Myers
joseph@codesourcery.com

Re: [RFC] Adding division/modulo on arbitrary precision integers to libgcc

[Jakub Jelinek]

On Fri, May 06, 2022 at 02:09:21PM +0000, 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.
Rather than uint32_t, wouldn't using the word size (64-bit for lp64, 32-bit
for ilp32) be better?
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.

	Jakub

Re: [RFC] Adding division/modulo on arbitrary precision integers to libgcc

[Joseph Myers]

On Fri, 6 May 2022, Jakub Jelinek via Gcc wrote:

> 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.

Note that the proposed x86_64 ABI for _BitInt (branch usr/hjl/bitint) says 
that padding bits are unspecified.  That means that when the width isn't a 
multiple of the word size, either you need to copy to zero-extend / 
sign-extend (in the general case where a variable of _BitInt type is read 
from memory / function argument / ..., so the code doing arithmetic on it 
doesn't have any further information about the values of those bits that 
it might have if it had computed the value itself), even in the absence of 
needing to allocate extra memory or allowing the libgcc function to write 
to those arrays, or you need to pass in a width in bits (rather than a 
number of words) to the libgcc function so that it can tell which bits are 
padding.

-- 
Joseph S. Myers
joseph@codesourcery.com

AW: [RFC] Adding division/modulo on arbitrary precision integers to libgcc

[Matthias Gehre]

On Fri, May 06, 2022 at 02:09:21PM +0000, 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

[Matthias Gehre]

> 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
joseph@codesourcery.com

Re: AW: [RFC] Adding division/modulo on arbitrary precision integers to libgcc

[Joseph Myers]

On Fri, 6 May 2022, Matthias Gehre via Gcc wrote:

> > 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?

Given that all four arrays can be written to, that seems reasonable (along 
with declaring them all as "restrict").

-- 
Joseph S. Myers
joseph@codesourcery.com

Re: AW: [RFC] Adding division/modulo on arbitrary precision integers to libgcc

[Jonathan Lennox]

On Friday, May 6 2022, "Matthias Gehre" wrote to "lennox" saying:

> Jakub Jelinek wrote:
> > 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).

Wouldn't this just be 'unsigned long' by definition?

-- 
Jonathan Lennox
lennox@cs.columbia.edu

Re: [RFC] Adding division/modulo on arbitrary precision integers to libgcc

[Segher Boessenkool]

Hi!

On Fri, May 06, 2022 at 02:09:21PM +0000, Matthias Gehre via Gcc wrote:
> 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.

Why?  Why would that be useful at all?

libgcc is an implementation detail.  It is not meant to be used by
anything but GCC itself, and then only to implement things that aren't
implemented some other way (by target code typically).  The names of the
functions it implements are based on the GCC-internal RTL names, often
identical even.  Defining the libgcc names first is not only futile, but
also the wrong order.

Most functions in libgcc are a not-so-ideal-but-at-least-it-works
implementation that target maintainers who cannot be bothered to
implement this functionality more optimally can use.  Typically what you
really want is not a library routine at all!

As noted elsewhere (I forgot by whom, sorry) the target ABI will
probably have somemthing to say about the actual data representation,
so it is very counterproductive if we have something in libgcc that
does something else.


Segher