Hi all,
I’d like to propose (and have implemented) a late X86 machine pass that removes a long-standing per-iteration penalty in multi-precision arithmetic loops, and I’d appreciate feedback on the approach before I open a PR. I’m also interested in implementing the follow-up changes that would close the remaining gap to hand-written assembly for this class of code; those are listed at the bottom with code snippets.
The problem
Bignum inner loops written portably with _addcarry_u64 / _subborrow_u64 compile to an ADC/SBB chain that is ideal within an iteration, but the loop-carried carry crosses the back-edge as an i8 value. The canonical multi-word addition:
uint64_t add_n(uint64_t *xp, const uint64_t *yp, int64_t n) {
unsigned char cy = 0;
for (int64_t i = 0; i < n; i++) {
unsigned long long s;
cy = _addcarry_u64(cy, xp[i], yp[i], &s);
xp[i] = s;
}
return cy;
}
Today this compiles (clang -O2, 4-way unrolled hot loop) to:
.LBB0_10:
movq (%rsi,%r8,8), %r9
addb $-1, %cl # rematerialize CF from %cl
adcq %r9, (%rdi,%r8,8) # the chain (4x)
...
setb %cl # save CF back to %cl
addq $4, %r8 # clobbers CF
cmpq %r8, %rdx # clobbers CF
jne .LBB0_10
The setb/addb round-trip costs two instructions per iteration and, worse, threads an extra serial dependence through %cl on a loop whose throughput is its serial carry dependence. Measured on 4000-limb kernels (Coffee Lake, cycles/limb, rdtsc reference cycles): 1.15 for the loop above vs 0.85 for hand-written assembly of the same loop (GMP’s mpn_add_n: 0.93). This is why every serious bignum library still ships .asm files.
ISel can’t do better under the current model: physical EFLAGS can’t be live across basic blocks pre-RA, and X86FlagsCopyLowering’s whole design is to materialize flags into bytes rather than preserve them.
The proposed pass
X86CarryChainLoops runs at the very end of addPreEmitPass and rewrites conforming single-block loops to the shape hand-written mpn kernels use, from the same C source above, no source change:
# preheader: cnt = (limit - i0) >> log2(step); addb $-1, %cl (once)
.LBB0_10:
movq (%rsi,%r8,8), %r9
adcq %r9, (%rdi,%r8,8) # CF arrives from the previous iteration
...
leaq 4(%r8), %r8 # lea: no flags
decq %r11 # dec: preserves CF, sets ZF
jne .LBB0_10
# %bb.11: # split exit edge
setb %cl # exit value; CF survived the exit too
Matching is deliberately narrow: one CF-materialization, a nonempty ADC/SBB run, SETB into the same byte register, a single induction add/inc + CMP + JNE back-edge, and no other EFLAGS reads or writes anywhere in the block. The exit-value SETB sinks out of the loop when the loop has no reader of the carry byte (splitting the critical exit edge the unroller shares with its scalar bypass); loops that consume the byte per iteration keep it inside.
Soundness notes reviewers will care about:
- Trip counts. For step 1 the down-counter count
(limit - i0) mod 2^64matches the original equality-exit loop unconditionally, including wrap-around. For step 2^k the rewrite fires only when the preheader proves divisibility (zeroing idiom for i0 + an AND mask clearing the low k bits—exactly the unroller’s output); otherwise an originally non-terminating loop could terminate, so we bail. - The down-counter comes from a free caller-saved GPR (a callee-saved one would need a prologue save we’re too late to add); if none is free, we bail.
- Placement. This is the part I most want feedback on. MIR models EFLAGS as a single register, so the CF-through-DEC liveness this pass creates is invisible to generic reasoning; X86FixupLEAs happily converted my flag-preserving LEA back into a CF-clobbering ADD until the pass moved after it. Running last (with a comment and tests pinning the shape) is the contained engineering answer; the principled fix is sub-flag register units for EFLAGS, which is a much larger cross-cutting change (and would benefit AArch64’s NZCV equally). I see this pass as evidence for that larger RFC, not a substitute. A middle option is bundling the loop bottom into a pseudo expanded at MC emission. Opinions welcome.
Related reports, and what closes each
This is a recognized deficiency with a decade of reports. What each one is, how they differ, and what in this RFC addresses them:
- #74493: “__builtin_addc loops spill the carry flag unnecessarily” (2023, open; reported from BoringSSL, which resorts to hand-written assembly to avoid the spill). Variable-length carry loops with clang’s generic builtin; the reporter notes ARM64 has the same disease (flag-clobbering ADDS/SUBS where flag-preserving control + CBNZ would do). This is the same underlying back-edge problem this pass fixes, but tested against a reduced reproducer, the pass does not fire on the
__builtin_addcllspelling today: clang lowers the builtin’s 64-bit carry through the wrap-compare idiom (two SETBs and an OR per limb; see change 5), never producing the clean addcarry chain the matcher requires. Change 5’s canonicalization plus this pass close it together. - #24919: “[x86] Silly code generation for _addcarry_u32/u64” (2015, migrated from Bugzilla PR24545; closed January 2019). The ancestor report: straight-line _addcarry chains materialized through setb/addb instead of chained ADC. Its closure in 2019 is the within-block half being fixed, which is why the loop body is perfect today; the loop-carried remnant is what this pass closes.
- #35591: “inefficient codegen for __builtin_addc” (2017). Same family via the generic builtin; within-block chaining has improved since, the loop residue is this pass, and code written with the wrap-compare idiom instead of any builtin is follow-up change 5.
- #33640 (2017) and #40891 (2019): ADCX/ADOX codegen. A different disease: the ADX intrinsics (_addcarryx_u64) are polyfilled into plain addcarry nodes, so ADCX/ADOX never reach the output even when explicitly requested; the dual-chain capability is unreachable. Not addressed by this pass (which manages a single CF chain); follow-up change 4 is the superset fix. It synthesizes the two-flag schedule those intrinsics were meant to expose, from portable code.
Coverage, tested against reduced reproducers of each (contrib/llvm-bug-repros.c in my repo; results below): the pass fixes the _addcarry_u64 loop shape (the main example) and, it turns out, the _addcarryx_u64 loop of #40891/#33640; the polyfill lowers to the same nodes, so the back-edge round-trip disappears there too, though ADCX/ADOX still never appear (that half needs change 4). Fixed-width, fully-unrolled chains with no loop at all (the original #24919/#35591 straight-line complaints, e.g. a 256-bit add written as four consecutive _addcarry_u64 calls) compile to a clean ADC chain already; upstream fixed those years ago; tested: zero SETB/ADDB in the four-limb chain. #74493’s __builtin_addcll spelling needs change 5 first, as above.
Tested against the cited issues
#40891 / #33640 reproducer: _addcarryx_u64 in a variable-length loop (clang unrolls 8-way). Before the pass:
LBB2_10:
addb $-1, %r8b # rematerialize CF -- every iteration
adcq %r9, (%rdi,%rcx,8)
adcq %r8, 8(%rdi,%rcx,8)
... 6 more adc ...
setb %r8b # spill CF -- every iteration
addq $8, %rcx
cmpq %rcx, %rdx # clobbers CF
jne LBB2_10
After the pass (same C, patched llc):
addb $-1, %r8b # ONCE, in the preheader
LBB2_10:
adcq %r9, (%rdi,%rcx,8)
adcq %r8, 8(%rdi,%rcx,8)
... 6 more adc ...
leaq 8(%rcx), %rcx # no flags
decq %r11 # preserves CF
jne LBB2_10
setb %r8b # once, on the exit edge
The ADCX polyfill complaint itself (adcx/adox never emitted; the reporter measured intrinsics 30% slower than inline asm for multiprecision multiplication) is untouched; that is change 4.
#74493 reproducer: __builtin_addcll in a variable-length loop. Before and after are identical; the pass correctly declines because clang lowers the builtin to the wrap-compare idiom, not an addcarry chain:
LBB0_8:
movq (%rdi,%rcx,8), %r9
addq (%rsi,%rcx,8), %r9
setb %r10b # overflow bit 1, materialized
addq %rax, %r9
setb %al # overflow bit 2, materialized
orb %r10b, %al # carry combined as a VALUE
...
addb $-1, %al # partial adc for the second limb only
adcq %r9, 8(%rdi,%rcx,8)
setb %al
This is the change-5 shape: canonicalize it to the addcarry chain and this pass closes the issue as written.
#24919 / #35591 straight-line reproducer: four consecutive _addcarry_u64 calls (a 256-bit add, no loop): compiles to a clean four-ADC chain with zero SETB/ADDB, before and after alike. The within-block half of these reports was fixed upstream years ago; what survived into 2023 (#74493) is the loop-carried case.
Results and testing
- add_n kernel: 1.15 → 0.91 c/l (hand asm 0.85, GMP 0.93). The SETB sinking is worth ~0.11 c/l of that.
-verify-machineinstrsclean; new lit test with positive (add/sub/store-carry) and negative (flag-clobbering consumer) cases. A second RUN line compiles the same IR with-x86-carry-chain-loops=falseand FileChecks that the original codegen (setb + cmp inside the loop) still comes out; i.e., the off switch is itself under test. Existing addcarry/adx/sbb suites and a broad loop/i128 sweep pass unchanged; byte-identical output on a full bignum application (the Benchmarks Game pi-digits task: pidigits description (Benchmarks Game) , via a native bignum spigot) compiled through the patched llc.- Off switch:
-x86-carry-chain-loops=false. I’d propose default-on, but default-off-initially is fine by me.
The rest of the gap: follow-ups I’m willing to implement
The pass above is the first of four changes that would let portable C match hand-written mpn assembly on x86-64. Measured per-change (same 4000-limb methodology, “after” numbers assume the rewrite reproduces the hand schedule, which is what change 1 achieved for its loop):
| # | change | before | after | speedup |
|---|---|---|---|---|
| 1 | carry-chain loops + SETB sinking (this RFC) | 1.15 | 0.91 | 1.26× |
| 2 | ADC loop-body shape | 0.91 | 0.85 | 1.07× |
| 3 | mul_1 value-chain recognition | 1.62 | ≈0.95 | 1.7× |
| 4 | addmul_1 dual-chain synthesis | 2.28 | ≈1.08 | 2.1× |
| 5 | recognize the intrinsic-free full-adder idiom | 2.12 | ≈0.91 | 2.3× |
Change 2: ADC loop-body shape. Same add_n C source as above; this one is purely about which instructions ISel picks for the body. We currently emit read-modify-write ADC with indexed addressing; the faster shape is load / ADC-from-memory (micro-fused) / store with pointer bumps:
# today # faster (GMP’s shape)
movq (%rsi,%r8,8), %r9 movq (%rdi), %r9
adcq %r9, (%rdi,%r8,8) adcq (%rsi), %r9
movq %r9, (%rdi)
# + lea to advance pointers
An instruction-selection/tuning preference—no new modeling, no ordering hazards. Cheapest of the set.
Change 3: mul_1 value chains. In x[] = y[] * m + carry, the quantity flowing between limbs is not a carry bit but a 65-bit value: the previous product’s 64-bit high half, plus possibly one more from adding the low half. Hand-written kernels represent it as a (register, CF) pair and never merge the halves; MULX touches no flags and DEC/JNE preserve CF, so both parts flow to the next limb and across the back-edge intact. C cannot express “keep this bit in the flags register”: its only way to observe the overflow is the wrap comparison below, which forces the bit to be folded into the 64-bit register on every limb; one extra instruction on the serial dependence chain per limb, and the flag half of the pair dies at the back-edge regardless:
// portable idiom (1.62 c/l today)
uint64_t lo = y[i] * m;
uint64_t hi = ((unsigned __int128)y[i] * m) >> 64;
uint64_t s = lo + cy;
if (s < lo) hi++;
x[i] = s;
cy = hi;
The schedule the pass would synthesize from that same C (what hand-written kernels do) keeps the link in CF across the whole (unrolled) body; MULX produces both halves without touching flags, and the carry crosses the back-edge as a (register, CF) pair:
.Lloop:
mulxq (%rsi), %r9, %r10 # rdx = m; no flags touched
mulxq 8(%rsi), %r11, %r12
adcq %rax, %r9 # single adc chain links hi -> next lo
...
movq %r12, %rax # (hiN -> cy, CF) crosses the back-edge
leaq 16(%rsi), %rsi
decq %rcx
jne .Lloop
Recognizing the idiom is a value-flow match (widening multiply split + wrap-compare + accumulator); the rewrite reuses all of change 1’s back-edge machinery. Largest single win for bignum-heavy applications (this is the hottest primitive in pi-digits).
Change 4: addmul_1 dual chains. x[] += y[] * m performs two additions per limb, each with its own overflow bit that must feed the next limb: (1) the product spine: the previous limb’s high half added into this limb’s low half; and (2) the accumulation: that sum added into the destination x[i]. With a single carry flag, one of the two streams must be folded into a register between every pair of additions, serializing the loop. This is precisely what ADX was added for: ADCX is add-with-carry through CF and ADOX is the same operation through OF; two independent carry chains interleaved in one instruction stream, neither disturbing the other. MULX touches neither flag, and loop control must preserve both (LEA + JRCXZ, since DEC preserves CF but clobbers OF). The portable source is the same widening idiom with one more accumulation (2.28 c/l today):
uint64_t lo = y[i] * m;
uint64_t hi = ((unsigned __int128)y[i] * m) >> 64;
uint64_t s = lo + cy;
if (s < lo) hi++; // fold overflow bit 1
uint64_t t = s + x[i];
if (t < s) hi++; // fold overflow bit 2
x[i] = t;
cy = hi;
and the dual-chain schedule it should become:
.Lloop:
mulxq (%rsi), %r9, %r10
...
adcxq %rax, %r9 # CF chain: product spine
adoxq (%rdi), %r9 # OF chain: accumulate into x
movq %r9, (%rdi)
...
movq %r13, %rax # both flags stay live across the edge
leaq -1(%rcx), %rcx
jrcxz .Ldone
jmp .Lloop
To my knowledge no production compiler has ever emitted ADCX/ADOX from portable source; eighteen years after ADX shipped they’re reachable only via intrinsics or asm. This is the hardest and the biggest win: 2.28 → ≈1.08 c/l on the loop that dominates every schoolbook bignum multiplication.
Change 5: the same result from intrinsic-free, fully standard C. A fair question is whether _addcarry_u64 is needed at all, since the full adder is expressible in plain C:
uint64_t s = a + b;
uint64_t c1 = (s < a);
uint64_t s2 = s + cy;
uint64_t c2 = (s2 < s);
xp[i] = s2;
cy = c1 | c2; // the overflows are mutually exclusive
Semantically this says everything the intrinsic says. Measured today, though, it compiles to 2.12 c/l vs the intrinsic’s 1.10: LLVM’s idiom recognition forms one ADC per limb but leaves two SETBs and a register OR of the carry (and the late pass correctly declines the loop; extra flag materializations outside the matched pattern). The fix belongs in the middle end: canonicalize the two-wrap-compare full adder into the same uadd.with.overflow/addcarry chain the intrinsic produces, after which ISel and this pass apply unchanged and standard C; including C23’s ckd_add from <stdckdint.h>, which already maps to uadd.with.overflow; reaches the same 0.91 c/l endpoint with no vendor intrinsics anywhere.
With these, it is possible to write C code that, when compiled with LLVM, beats GMP on pi-digits with no assembly anywhere in the toolchain; I have the end-to-end application numbers if anyone wants them.
Patch for change 1 is ready (one pass file + registration + lit test, ~470 lines at 23% comment density). Happy to open the PR, split things differently, or write the sub-flag-units RFC first if that’s the preferred direction.
Thanks,
Ryan Landay