Running mpn_add_n at less than 1 cycle/limb

[Torbjörn Granlund]

Our measurements of cycle counts for GMP's main mpn loops indicate
impossible cycle counts for many functions.  For exemple, an mpn_add_n
loop with a full dependency on the carry flag cannot exceed the speed of
the underlying add-with-carry instruction.

But why are we seeing things like
https://gmplib.org/devel/tm/gmp/tuneup/success/gran.gmplib.org-stat:64.txt
with lots of number < 1, then?

Because of deeo out-of-order execution, of course!  Two consecutive
mpn_add_n invocations execute with some overlap.

But then we have an interesting case where we get < 1 cycle limb also
for huge enough trip counts, or for cases where we precude overlap
between consecutive invocations: mpn/x86_64/pentium4/aors_n.asm is such
an exception!

Why is that? That mpn_add_n variant actually breaks the carry dependency
chain by branching when carry-in of every 4th limb changes the
carry-out.

Pretty cool, but unfortunately, this is not great for side-channel
leakage.

(To clarify, that pentium4 targeted code does not run at < 1 cycle/limb
on actual pentium4 hardware.  But it does on many current CPUs.)

-- 
Torbjörn
Please encrypt, key id 0xC8601622