Last month I woke up to a fresh regression on llvm-test-suite where the automotive-bitcount benchmark was 46% slower on RISC-V.
What had happened was that SLP began vectorizing the following sequence in a hot loop:
andi a3, a1, 0xf
slli a4, a1, 0x38
slli a5, a1, 0x34
srli a4, a4, 0x3c
add a3, a3, s4
add a4, a4, s4
srli a5, a5, 0x3c
slli a6, a1, 0x30
add a5, a5, s4
srli a6, a6, 0x3c
add a6, a6, s4
slli a7, a1, 0x2c
srli a7, a7, 0x3c
lbu a3, 0x0(a3)
lbu a4, 0x0(a4)
lbu a5, 0x0(a5)
lbu a6, 0x0(a6)
add a7, a7, s4
slli t0, a1, 0x28
slli t1, a1, 0x24
srli t0, t0, 0x3c
srli t1, t1, 0x3c
add t0, t0, s4
add t1, t1, s4
lbu a7, 0x0(a7)
lbu t0, 0x0(t0)
lbu t1, 0x0(t1)
srliw t2, a1, 0x1c
add t2, t2, s4
add a3, a3, a4
lbu a4, 0x0(t2)
add a5, a5, a6
add a7, a7, t0
add a3, a3, a5
add a7, a7, t1
add a3, a3, a7
add a2, a2, a4
addi a1, a1, 0xd
add a2, a2, a3
bne a1, a0, 0xaf8 <main+0x2b0>
To this indexed gather vluxei64.v of 8 elements on RISC-V:
vsetvli zero, 0x8, e64, m4, ta, ma
vmv.v.x v16, a2
vsrl.vv v16, v16, v12
vand.vi v16, v16, 0xf
vsetvli zero, zero, e8, mf2, ta, ma
vluxei64.v v20, (s4), v16
vsetvli zero, zero, e32, m2, ta, ma
vzext.vf4 v16, v20
vwaddu.wv v8, v8, v16
addi a1, a1, -0x1
addi a2, a2, 0xd
bnez a1, 0xb04 <main+0x2bc>
On the surface the new vectorized code looks pretty reasonable, but in reality the vectorized code takes 51.9M cycles whilst the original scalar only takes 12.3M. vluxei64.v and other indexed memory operations are pretty slow on most available RISC-V hardware today, typically only processing elements one at a time, and to make matters worse we have to do a bunch of 64-bit pointer arithmetic at a wide LMUL too.
So there was somewhere where we weren’t taking this into account in the cost model, either in the RISC-V backend or in the SLP vectorizer. Just as I was about to crank up the cost for vluxei64.v I took a step back and looked at the original C source for that function.
static char bits[256] = {0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, ...};
static int ntbl_bitcount(long x) {
return bits[(int)(x & 0x0000000FUL)] +
bits[(int)((x & 0x000000F0UL) >> 4)] +
bits[(int)((x & 0x00000F00UL) >> 8)] +
bits[(int)((x & 0x0000F000UL) >> 12)] +
bits[(int)((x & 0x000F0000UL) >> 16)] +
bits[(int)((x & 0x00F00000UL) >> 20)] +
bits[(int)((x & 0x0F000000UL) >> 24)] +
bits[(int)((x & 0xF0000000UL) >> 28)];
}
As it turns out, this function is just popcount: it computes the number of bits set in a 32-bit integer x. And we have an instruction for this on RISC-V, cpop! So why aren’t we lowering to it?
AggressiveInstCombine can recognise some forms of popcount that directly manipulate the bits of the input, but the twist in arithmetic-bitcount is that it uses a table lookup on precomputed values instead.
x comes in as a long but is cast to a 32-bit int. The function then breaks up the 32-bit int into 4-bit nibbles, shifting and masking it with 0xF, and looks up the popcount of each 4-bit nibble. Then it returns the sum of the 4-bit popcounts.
Doing it per-nibble is a nice approach as it keeps the accessed part of the lookup table small at just 16 bytes, so it should all fit inside a single cache line. But even if all 8 loads are L1 cache hits, it’s not as fast as a native cpop on RISC-V. So how can we match this pattern? Here’s the IR before we reach AggressiveInstCombine:
@bits = internal unnamed_addr constant [256 x i8] c"\00\01\01\02\01\02\02\03\01\02\02\03\02\03\03\04\01\02\02\03\02\03\03\04\02\03\03\04\03\04\04\05\01\02\02\03\02\03\03\04\02\03\03\04\03\04\04\05\02\03\03\04\03\04\04\05\03\04\04\05\04\05\05\06\01\02\02\03\02\03\03\04\02\03\03\04\03\04\04\05\02\03\03\04\03\04\04\05\03\04\04\05\04\05\05\06\02\03\03\04\03\04\04\05\03\04\04\05\04\05\05\06\03\04\04\05\04\05\05\06\04\05\05\06\05\06\06\07\01\02\02\03\02\03\03\04\02\03\03\04\03\04\04\05\02\03\03\04\03\04\04\05\03\04\04\05\04\05\05\06\02\03\03\04\03\04\04\05\03\04\04\05\04\05\05\06\03\04\04\05\04\05\05\06\04\05\05\06\05\06\06\07\02\03\03\04\03\04\04\05\03\04\04\05\04\05\05\06\03\04\04\05\04\05\05\06\04\05\05\06\05\06\06\07\03\04\04\05\04\05\05\06\04\05\05\06\05\06\06\07\04\05\05\06\05\06\06\07\05\06\06\07\06\07\07\08", align 1
define dso_local signext range(i32 0, 2041) i32 @ntbl_bitcount(i64 noundef %x) local_unnamed_addr #0 {
entry:
%conv = and i64 %x, 15
%arrayidx = getelementptr inbounds nuw i8, ptr @bits, i64 %conv
%0 = load i8, ptr %arrayidx, align 1, !tbaa !4
%conv1 = zext i8 %0 to i32
%1 = lshr i64 %x, 4
%conv3 = and i64 %1, 15
%arrayidx5 = getelementptr inbounds nuw i8, ptr @bits, i64 %conv3
%2 = load i8, ptr %arrayidx5, align 1, !tbaa !4
%conv6 = zext i8 %2 to i32
%add = add nuw nsw i32 %conv1, %conv6
%3 = lshr i64 %x, 8
%conv9 = and i64 %3, 15
%arrayidx11 = getelementptr inbounds nuw i8, ptr @bits, i64 %conv9
%4 = load i8, ptr %arrayidx11, align 1, !tbaa !4
%conv12 = zext i8 %4 to i32
%add13 = add nuw nsw i32 %add, %conv12
%5 = lshr i64 %x, 12
%conv16 = and i64 %5, 15
%arrayidx18 = getelementptr inbounds nuw i8, ptr @bits, i64 %conv16
%6 = load i8, ptr %arrayidx18, align 1, !tbaa !4
%conv19 = zext i8 %6 to i32
%add20 = add nuw nsw i32 %add13, %conv19
%7 = lshr i64 %x, 16
%conv23 = and i64 %7, 15
%arrayidx25 = getelementptr inbounds nuw i8, ptr @bits, i64 %conv23
%8 = load i8, ptr %arrayidx25, align 1, !tbaa !4
%conv26 = zext i8 %8 to i32
%add27 = add nuw nsw i32 %add20, %conv26
%9 = lshr i64 %x, 20
%conv30 = and i64 %9, 15
%arrayidx32 = getelementptr inbounds nuw i8, ptr @bits, i64 %conv30
%10 = load i8, ptr %arrayidx32, align 1, !tbaa !4
%conv33 = zext i8 %10 to i32
%add34 = add nuw nsw i32 %add27, %conv33
%11 = lshr i64 %x, 24
%conv37 = and i64 %11, 15
%arrayidx39 = getelementptr inbounds nuw i8, ptr @bits, i64 %conv37
%12 = load i8, ptr %arrayidx39, align 1, !tbaa !4
%conv40 = zext i8 %12 to i32
%add41 = add nuw nsw i32 %add34, %conv40
%13 = lshr i64 %x, 28
%idxprom45 = and i64 %13, 15
%arrayidx46 = getelementptr inbounds nuw i8, ptr @bits, i64 %idxprom45
%14 = load i8, ptr %arrayidx46, align 1, !tbaa !4
%conv47 = zext i8 %14 to i32
%add48 = add nuw nsw i32 %add41, %conv47
ret i32 %add48
}
You could write one big optimisation to recognise the whole chain, but it’s often better practice to do things as smaller, composable chunks. Lets start with a smaller chunk of the IR, focusing on a single table lookup:
%gep = getelementptr [256 x i8], ptr @bits, i64 %x
%ctpop = load i8, ptr %gep
What’s important to note is that any read outside of @bits is undefined behaviour, so we’re free to assume that %x lies somewhere within it. So given a load from some global variable @bits and an index into it %x, if every element in the global variable maps to bits[i] = popcount(i), then we can replace bits[%x] with popcount(%x). Here’s the implementation in AggressiveInstCombine, landed in #231225:
static bool tryToRecognizeTableBasedCtpop(LoadInst *LI, Type *AccessType,
GlobalVariable *GVTable,
Value *GepIdx, const APInt &GEPScale,
const DataLayout &DL,
const TargetTransformInfo &TTI) {
Type *IdxTy = GepIdx->getType();
unsigned IdxBits = IdxTy->getIntegerBitWidth();
if (!LI->isSimple() || !isPowerOf2_32(IdxBits) ||
TTI.getPopcntSupport(IdxBits) != TargetTransformInfo::PSK_FastHardware)
return false;
// GEPScale = the i8 in getelementptr [256 x i8]
// AccessSize = the i8 in load i8
uint64_t TableSize = DL.getTypeAllocSize(GVTable->getValueType());
unsigned AccessSize = DL.getTypeStoreSize(AccessType);
if (GEPScale != AccessSize)
return false;
uint64_t NumEntries = TableSize / AccessSize;
// Is this a popcount table?
for (uint64_t I = 0; I < NumEntries; I++) {
auto *C = dyn_cast_or_null<ConstantInt>(ConstantFoldLoadFromConst(
GVTable->getInitializer(), AccessType, I * GEPScale, DL));
if (!C || C->getValue() != popcount(I))
return false;
}
// Zero extend or truncate as needed
replaceWithPopCount(*LI, GepIdx);
return true;
}
With a quick profitability query and a check to make sure we’re loading from a popcount table, we collapse a lookup into a call to the dedicated popcount intrinsic @llvm.ctpop (plus a truncate to get it back to the right size):
%ctpop = call i64 @llvm.ctpop(i64 %x)
%ctpop.trunc = trunc i64 %ctpop to i8
When applied to the IR from the benchmark we’re left with a chain of ctpops all operating on 4-bit chunks at a time, summed together:
define dso_local signext range(i32 0, 2041) i32 @ntbl_bitcount(i64 noundef %x) local_unnamed_addr #0 {
entry:
%conv = and i64 %x, 15
%0 = tail call range(i64 0, 5) i64 @llvm.ctpop.i64(i64 %conv)
%conv1 = trunc nuw nsw i64 %0 to i32
%1 = lshr i64 %x, 4
%conv3 = and i64 %1, 15
%2 = tail call range(i64 0, 5) i64 @llvm.ctpop.i64(i64 %conv3)
%conv6 = trunc nuw nsw i64 %2 to i32
%add = add nuw nsw i32 %conv6, %conv1
%3 = lshr i64 %x, 8
%conv9 = and i64 %3, 15
%4 = tail call range(i64 0, 5) i64 @llvm.ctpop.i64(i64 %conv9)
%conv12 = trunc nuw nsw i64 %4 to i32
%add13 = add nuw nsw i32 %add, %conv12
%5 = lshr i64 %x, 12
%conv16 = and i64 %5, 15
%6 = tail call range(i64 0, 5) i64 @llvm.ctpop.i64(i64 %conv16)
%conv19 = trunc nuw nsw i64 %6 to i32
%add20 = add nuw nsw i32 %add13, %conv19
%7 = lshr i64 %x, 16
%conv23 = and i64 %7, 15
%8 = tail call range(i64 0, 5) i64 @llvm.ctpop.i64(i64 %conv23)
%conv26 = trunc nuw nsw i64 %8 to i32
%add27 = add nuw nsw i32 %add20, %conv26
%9 = lshr i64 %x, 20
%conv30 = and i64 %9, 15
%10 = tail call range(i64 0, 5) i64 @llvm.ctpop.i64(i64 %conv30)
%conv33 = trunc nuw nsw i64 %10 to i32
%add34 = add nuw nsw i32 %add27, %conv33
%11 = lshr i64 %x, 24
%conv37 = and i64 %11, 15
%12 = tail call range(i64 0, 5) i64 @llvm.ctpop.i64(i64 %conv37)
%conv40 = trunc nuw nsw i64 %12 to i32
%add41 = add nuw nsw i32 %add34, %conv40
%13 = lshr i64 %x, 28
%idxprom45 = and i64 %13, 15
%14 = tail call range(i64 0, 5) i64 @llvm.ctpop.i64(i64 %idxprom45)
%conv47 = trunc nuw nsw i64 %14 to i32
%add48 = add nuw nsw i32 %add41, %conv47
ret i32 %add48
}
We’re still using 8 ctpops to compute 1 ctpop though, so the next step is to merge these together.
If we have ctpop(X) + ctpop(Y) we can fold that into ctpop(X | Y) if X and Y don’t share any set bits. For example, if X = 0b11110000 and Y = 0b00001111, because they’re disjoint we have ctpop(X) + ctpop(Y) = ctpop(0b11111111) = 8. This combine already exists in InstCombine:
// ctpop(A) + ctpop(B) => ctpop(A | B) if A and B have no bits set in common.
if (match(LHS, m_OneUse(m_Ctpop(m_Value(A)))) &&
match(RHS, m_OneUse(m_Ctpop(m_Value(B)))) &&
haveNoCommonBitsSet(A, B, SQ.getWithInstruction(&I)))
return replaceInstUsesWith(
I, Builder.CreateIntrinsic(Intrinsic::ctpop, {I.getType()},
{Builder.CreateDisjointOr(A, B)}));
But our motivating IR is slightly different. We have ctpop(X & 0xf) + ctpop((X >> 4) & 0xf) + ctpop((X >> 8) & 0xf) + .... Each 4-bit nibble overlaps in the same least significant bits which prevents the fold above, but:
- the individual bits that we extract from
Xare distinct. - it doesn’t matter where the bits are placed in
ctpop.ctpop(X)andctpop(X << 4)give the same result as long as no bits of X are shifted out. - we know that we can fold
ctpop(X) + ctpop(Y) -> ctpop(X | Y)when the bits are distinct.
So what we can do is shift back up the bits of X up so that they’re now in distinct bit positions, which allows us to do the earlier fold that combines the add:
ctpop(X & 0x0f) + ctpop((X >> 4) & 0xf)
=>
; shift the bits back up so they don't overlap
ctpop(X & 0x0f) + ctpop(((X >> 4) & 0xf) << 4)
=>
ctpop(X & 0x0f) + ctpop(X & 0xf0)
=>
ctpop(X & (0x0f | 0xf0))
=>
ctpop(X & 0xff)
We can generalise this to arbitrary shifts and masks, and then we get this code in InstCombine (#231321):
/// Given (X >> C) & M, returns {X, M << C} (the source and a mask of what bits
/// of the source are in \p V).
static std::pair<Value *, APInt> matchMaskedBits(Value *V) {
unsigned BitWidth = V->getType()->getScalarSizeInBits();
APInt Mask = APInt::getAllOnes(BitWidth);
Value *Src;
const APInt *M;
uint64_t ShAmt;
if (match(V, m_And(m_Value(Src), m_APInt(M)))) {
V = Src;
Mask = *M;
}
if (match(V, m_LShrOrSelf(m_Value(Src), ShAmt)) && ShAmt < BitWidth) {
V = Src;
Mask <<= ShAmt;
}
return {V, Mask};
}
/// ctpop((X >> C1) & M1) + ctpop((X >> C2) & M2)
/// =>
/// ctpop(X & ((M1 << C1) | (M2 << C2))) if M1 << C1 and M2 << C2 are disjoint
static Value *foldAddOfMaskedCtpops(BinaryOperator &I,
InstCombiner::BuilderTy &Builder) {
Value *A, *B;
if (!match(I.getOperand(0), m_OneUse(m_Ctpop(m_Value(A)))) ||
!match(I.getOperand(1), m_OneUse(m_Ctpop(m_Value(B)))))
return nullptr;
auto [XA, MaskA] = matchMaskedBits(A);
auto [XB, MaskB] = matchMaskedBits(B);
if (XA != XB || MaskA.intersects(MaskB))
return nullptr;
Value *Masked = Builder.CreateAnd(XA, MaskA | MaskB);
return Builder.CreateUnaryIntrinsic(Intrinsic::ctpop, Masked);
}
If we try this out: Nothing changes! We don’t actually match the ctpop(X & 0x0f) + ctpop((X >> 4) & 0xf) pattern here because there’s truncates in between.
%conv = and i64 %x, 15
%0 = tail call range(i64 0, 5) i64 @llvm.ctpop.i64(i64 %conv)
%conv1 = trunc nuw nsw i64 %0 to i32
%1 = lshr i64 %x, 4
%conv3 = and i64 %1, 15
%2 = tail call range(i64 0, 5) i64 @llvm.ctpop.i64(i64 %conv3)
%conv6 = trunc nuw nsw i64 %2 to i32
%add = add nuw nsw i32 %conv6, %conv1
...
We can strip off the individual truncates by pulling them outside of the adds in InstCombine (#231332):
// trunc(ctpop(A)) + trunc(ctpop(B)) => trunc(ctpop(A) + ctpop(B))
if (match(LHS, m_OneUse(m_Trunc(m_Value(A, m_Ctpop(m_Value()))))) &&
match(RHS, m_OneUse(m_Trunc(m_Value(B, m_Ctpop(m_Value()))))) &&
A->getType() == B->getType())
return new TruncInst(Builder.CreateAdd(A, B), I.getType());
Which now gives us the right shape for our ctpop pattern:
%conv = and i64 %x, 15
%0 = tail call range(i64 0, 5) i64 @llvm.ctpop.i64(i64 %conv)
%1 = lshr i64 %x, 4
%conv3 = and i64 %1, 15
%2 = tail call range(i64 0, 5) i64 @llvm.ctpop.i64(i64 %conv3)
%3 = add nuw nsw i64 %2, %0
%add = trunc nuw nsw i64 %3 to i32
...
And finally the entire function folds away to one call:
define dso_local signext range(i32 0, 33) i32 @ntbl_bitcount(i64 noundef %x) local_unnamed_addr #0 {
entry:
%0 = and i64 %x, 4294967295
%1 = call range(i64 0, 33) i64 @llvm.ctpop.i64(i64 %0)
%add48 = trunc nuw nsw i64 %1 to i32
ret i32 %add48
}
Which gives us a single RISC-V instruction:
ntbl_bitcount: # @ntbl_bitcount
.cfi_startproc
# %bb.0: # %entry
cpopw a0, a0
ret
As an added bonus, ntbl_bitcount is inlined within the loop its called from. So if we’re compiling with Zvbb (which rva23u64 contains), the loop vectorizer is able to kick in and we get a vectorized reduction using vcpop.v:
# %bb.1: # %vector.ph
vsetvli a2, zero, e64, m2, ta, ma
vmv.v.x v10, a0
vid.v v8
li a0, 13
vmadd.vx v8, a0, v10
vmv.v.i v10, 0
li a0, -1
srli a0, a0, 32
.LBB1_2: # %vector.body
# =>This Inner Loop Header: Depth=1
vsetvli a2, a1, e64, m2, ta, ma
vand.vx v12, v8, a0
vcpop.v v12, v12
sh1add a3, a2, a2
vsetvli zero, zero, e64, m2, tu, ma
vadd.vv v10, v12, v10
sh2add a3, a3, a2
vsetvli zero, zero, e64, m2, ta, ma
vadd.vx v8, v8, a3
sub a1, a1, a2
bnez a1, .LBB1_2
# %bb.3: # %for.cond.cleanup.loopexit
vsetvli a0, zero, e64, m2, ta, ma
vmv.s.x v8, zero
vredsum.vs v8, v10, v8
vmv.x.s a0, v8
ret
The final vcpop.v reduction is a mighty 115x times faster than the original SLP vectorized version as measured on a SpacemiT-K3. Not bad!
Now with all this said, automotive-bitcount as a benchmark is very artificial. It just consists of a bunch of different implementations of popcount, each executed in a loop. However out of the 8 implementations, with these patches LLVM is able to lower 6 of them to llvm.ctpop intrinsics. In fact LLVM’s AggressiveInstCombine can already recognise various implementations of popcount, and there’s a whole zoo of different formats that tryToRecognizePopCount/tryToRecognizePopCount1/tryToRecognizePopCount2n3 detect:
int popcount(unsigned int i) {
i = i - ((i >> 1) & 0x55555555);
i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
i = ((i + (i >> 4)) & 0x0F0F0F0F);
return (i * 0x01010101) >> 24;
}
int popcnt(unsigned x) {
x = x - ((x >> 1) & 0x55555555);
x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
x = (x + (x >> 4)) & 0x0F0F0F0F;
x = x + (x >> 8);
x = x + (x >> 16);
return x & 0x0000003F;
}
int popcnt(unsigned x) {
x = x - ((x >> 1) & 0x55555555);
x = x - 3*((x >> 2) & 0x33333333);
x = (x + (x >> 4)) & 0x0F0F0F0F;
x = x + (x >> 8);
x = x + (x >> 16);
return x & 0x0000003F;
}
// Ref. Hackers Delight
int popcount32(unsigned int i) {
uWord = (uWord & 0x55555555) + ((uWord>>1) & 0x55555555);
uWord = (uWord & 0x33333333) + ((uWord>>2) & 0x33333333);
uWord = (uWord & 0x0F0F0F0F) + ((uWord>>4) & 0x0F0F0F0F);
uWord = (uWord & 0x00FF00FF) + ((uWord>>8) & 0x00FF00FF);
return (uWord & 0x0000FFFF) + (uWord>>16);
}
int popcount64(unsigned long i) {
uWord = (uWord & 0x5555555555555555) + ((uWord>>1) & 0x5555555555555555);
uWord = (uWord & 0x3333333333333333) + ((uWord>>2) & 0x3333333333333333);
uWord = (uWord & 0x0F0F0F0F0F0F0F0F) + ((uWord>>4) & 0x0F0F0F0F0F0F0F0F);
uWord = (uWord & 0x00FF00FF00FF00FF) + ((uWord>>8) & 0x00FF00FF00FF00FF);
uWord = (uWord & 0x0000FFFF0000FFFF) + ((uWord>>16) & 0x0000FFFF0000FFFF);
return (uWord & 0x00000000FFFFFFFF) + (uWord>>32) & 0x00000000FFFFFFFF;
}
Try as you might to be clever with your magic constants and fancy bit shifts, LLVM sees through it all and steamrolls over it it with relish.
I invite anyone to try and tackle the remaining two, bitcount and bit_shifter, since even though this series of patches stemmed from an artificial benchmark the table lookup popcount pattern shows up in a few places in the real world, notably Redis and GCC. So sometimes chasing down these benchmarks can be for both fun and profit!






























































︎



