compiler_rt: Ideas and Tracking Issue Big Integer (Arbitrary Length/Precision/Width) Routines

[matu3ba]

This is a first draft to collect ideas. For posteriority, the decision (discussion) https://github.com/ziglang/zig/pull/15285#discussion_r1167228419. Further necessary input is:

• 1. Do we want to support only keeping the result separate or can the result overlap with a or b?
• 2. Does the same hold true for the bit operations or where do we set the boundaries?
• 3. Should we have routines for overlapping and non-overlapping results?

Done	Name	result	a	b	size	ret	Comment
							BigInt Bit Operation
✗	__clzei4	[*c]u32	[*c]u32	∅	usize	i32	count leading zeros
✗	__ctzei4	[*c]u32	[*c]u32	∅	usize	i32	count trailing zeros
✗	__ffsei4	[*c]u32	[*c]u32	∅	usize	i32	find least significant 1bit
✗	__parityei4	[*c]u32	[*c]u32	∅	usize	i32	bit parity
✗	__popcountei4	[*c]u32	[*c]u32	∅	usize	i32	bit population
✗	__bswapei3	[*c]u32	[*c]u32	∅	usize	void	byte swap TODO: which bytes?
✗	__bitdepei4	[*c]u32	[*c]u32	[*c]u32	usize	void	a left-aligned into positions by b TODO: bitsizes?
✗	__bitextei4	[*c]u32	[*c]u32	[*c]u32	usize	void	a selected by b right-aligned into result TODO: bitsizes?
							BigInt Comparison
✗	__cmpei3	∅	[*c]u32	[*c]u32	usize	i32	(a<b) -> 0, (a==b) -> 1, (a>b) -> 2
✗	__ucmpei3	∅	[*c]u32	[*c]u32	usize	i32	(a<b) -> 0, (a==b) -> 1, (a>b) -> 2
							BigInt Arithmetic
✗	__ashlei4	[*c]u32	[*c]u32	usize	usize	void	res=a<<b
✗	__ashrei4	[*c]u32	[*c]u32	usize	usize	void	res=a>>b arithmetic (sign fill)
✗	__lshrei4	[*c]u32	[*c]u32	usize	usize	void	res=a>>b loigcal (zero fill)
✗	__negei3	[*c]u32	[*c]u32	∅	usize	void	-a
✗	__mulei3	[*c]u32	[*c]u32	[*c]u32	usize	void	a * b
✗	__divei4	[*c]u32	[*c]u32	[*c]u32	usize	void	a / b
✓	__udivei4	[*c]u32	[*c]u32	[*c]u32	usize	void	a / b
✗	__modei4	[*c]u32	[*c]u32	[*c]u32	usize	void	a % b
✓	__umodei4	[*c]u32	[*c]u32	[*c]u32	usize	void	a % b
✗	__divmodei5	[*c]u32	[*c]u32	[*c]u32	usize	void	res1=a/b, res2=a%b Alg D by Knuth
✗	__udivmodei5	[*c]u32	[*c]u32	[*c]u32	usize	void	res1=a/b, res2=a%b Alg D by Knuth
							BigInt Arithmetic with Trapping Overflow
✗	__absvei3	[*c]u32	[*c]u32	[*c]u32	usize	void	abs(a)
✗	__negvei3	[*c]u32	[*c]u32	[*c]u32	usize	void	-a
✗	__addvei4	[*c]u32	[*c]u32	[*c]u32	usize	void	a + b
✗	__subvei4	[*c]u32	[*c]u32	[*c]u32	usize	void	a - b
✗	__mulvei4	[*c]u32	[*c]u32	[*c]u32	usize	void	a * b
							BigInt Arithmetic which Return on Overflow[^noptr_faster]
✗	__addoei5	[*c]u32	[*c]u32	[*c]u32	usize	i32	a + b
✗	__suboei5	[*c]u32	[*c]u32	[*c]u32	usize	i32	a - b
✗	__muloei5	[*c]u32	[*c]u32	[*c]u32	usize	i32	a * b

Notes:

• 1. Unfinished and might break. Compatibility with libgcc is preferred.
• 2. Idea is to use integer routines and instead use ei for extended integer and use sum of number of arguments and return argument, if not void.

[andrewrk]

Further necessary input is:

Why do you need any input? The task is to match LLVM compiler_rt and libgcc ABI.

[matu3ba]

Why do you need any input? The task is to match LLVM compiler_rt and libgcc ABI.

There is no such ABI by gcc and the llvm folks and myself do not think they want to introduce one, see this comment by a gcc folk and the subsequent action by llvm.

To quote:

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.

LLVM itself seems to be busy trying to manage all configurations for compiler-rt and unless they have finalized that I dont think they will add incompatible symbols, see this rfc. I'll ask on discord what the current status is.