Tracking compiler inefficiencies

[mratsim]

As mentioned in https://github.com/mratsim/constantine/blob/661a481/README-PERFORMANCE.md#compiler-caveats
Compilers have a hard time optimizing bigint operations, even as simple as an addition with carries.

This issue track their evolution and the quality of the code generated with compiler builtins for ISAs of interest.

Note that as of February 2024, we use:

• _addcarry_u64 on x86-64
• uint128 on other ISAs

2019, GCC 9.2 and Clang 9.0

The original problem:
https://gcc.godbolt.org/z/2h768y

Even with intrinsics, an operation as simple as addition-with-carry is uglily implemented in GCC.
This has been mentioned by the GMP folks 30 years ago: https://gmplib.org/manual/Assembly-Carry-Propagation.html

2024, GCC 13.2 and Clang 17.0

https://gcc.godbolt.org/z/jdecvffaP

GMP fixed the x86 intrinsics but unfortunately the portable intrinsics has a terribad codegen and hence makes a terrible fallback for ARM.

Current status

Due to GCC abysmal __builtin__addcll it is a non-starter.
Clang has decent codegen.

Assembly is still very much needed.

This also explains the bad ARM performance on Apple M1, M2, M3, mentioned by @agnxsh (#354 (comment)) and @bkomuves