Chapter 15: Error-Correcting Codes — LLVM Validation
LLVM version tested: 23.0.0git (build at ~/llvm-project/build/bin)
Already handled correctly
| Pattern | IR | LLVM output | Notes |
|---|---|---|---|
Power-of-two-or-zero (s & (s-1)) == 0 | (s-1) & s == 0 | leal -1; testl; sete | 3 insns, optimal |
ctpop(x) & 1 via intrinsic (no popcnt) | llvm.ctpop + and 1 | xorb + setnp | 6 insns, uses parity flag |
ctpop(x) & 1 via intrinsic (+popcnt) | llvm.ctpop + and 1 | popcntl + andl | 2 insns, optimal |
Missed optimization: prefix XOR parity chain not lifted to ctpop
Pattern
§15-3 Figure 15-1 computes each Hamming check bit as the parity (XOR of all bits) of a masked subset. The standard software idiom is a 5-step parallel prefix XOR:
x ^= x >> 1;
x ^= x >> 2;
x ^= x >> 4;
x ^= x >> 8;
x ^= x >> 16;
parity = x & 1;This is equivalent to popcount(x) & 1.
Instruction counts
| Target | Current | Optimal | Miss |
|---|---|---|---|
| No POPCNT | 16 | 6 (XOR fold + SETNP) | 10 |
| +popcnt | 16 | 2 (popcntl + andl) | 14 |
Root cause
opt -O2 (InstCombine) does not recognize the XOR-prefix-reduction chain as
ctpop(x) & 1. When written explicitly as llvm.ctpop.i32(x) & 1, llc generates
correct POPCNT or SETNP code. The miss is purely in the IR-level pattern recognizer.
Impact
Every Hamming check-bit computation in Figure 15-1 uses this pattern (6 times, one per check bit). Any software parity routine written in the standard XOR-prefix idiom (common in ECC, CRC, cryptography) is affected.
Note: syndrome decode not simplified (expected)
b = syn - 31 - (syn >> 5) is equivalent to syn & 0x1f only when bit 5 of syn
is set. Without that range constraint in the IR, LLVM correctly cannot simplify.
Test files
| File | What it tests |
|---|---|
ch15_ecc.ll | Prefix XOR parity chain, masked variant (p0), pow2 check, syndrome decode |
bug-parity-prefix-xor.md | Bug report: XOR chain → ctpop not recognized |