[x86] @llvm.ctpop.v8i32 custom lowering

[bruno]

Summary

This patch adds x86 custom lowering for the @llvm.ctpop.v8i32 intrinsic.

Currently, the expansion of @llvm.ctpop.v8i32 uses vector element extractions,
insertions and individual calls to @llvm.ctpop.i32. Local haswell measurements
show that @llvm.ctpop.v8i32 gets faster by using vector parallel bit twiddling approaches
than using @llvm.ctpop.i32 for each element, based on:

v = v - ((v >> 1) & 0x55555555);
v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
v = ((v + (v >> 4) & 0xF0F0F0F)
v = v + (v >> 8)
v = v + (v >> 16)
v = v & 0x0000003F
(from http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel)

Some toy microbenchmark presented a ~2x speedup, whereas vector types with smaller number of elements
are still better with the old approach (see results below). Hence this
patch only implements it for v8i32 type. The results indicate it might also be profitable
to implement this approach for v32i8 and v16i16, but I haven't measured that yet.

AVX1 ctpop.v8i32 is broken into two ctpop.v4i32, which is only slightly better than old expansion. However,
this patch does not implement custom lowering for the general ctpop.v4i32 type, since it's not profitable.

[core-avx2]

v8i32-new: 10.3506
v8i32-old: 18.3879
v4i32-new: 10.3699
v4i32-old: 8.01387
v4i64-new: 11.7464
v4i64-old: 10.3043
v2i64-new: 11.7922
v2i64-old: 5.20916

[corei7-avx]

v8i32-new: 16.5359
v8i32-old: 18.2479
v4i32-new: 10.2069
v4i32-old: 8.03686
v4i64-new: 17.8085
v4i64-old: 10.2366
v2i64-new: 11.7623
v2i64-old: 5.11533

[nadav]

LGTM! Thank you for the detailed measurements!

Do you think that other targets may also benefit from this kind of transformation?

Thanks,
Nadav

[bruno]

Chandler,

Thanks for the help, the assembly for v8i32-new/old:
http://pastebin.com/4gnd41Je

About the principled split: I rather go the other way around, i.e., since SelectionDAGLegalize::ExpandBitCount already emits the bit-math for scalarized versions it makes more sense to custom split to other known vector types only when we already know it's profitable.

Nadav and Hal,

There are potential benefits for other targets I believe, but this customisation generates a bunch of vector instructions and I'm afraid that if one or other vector instruction isn't well supported on a target, that could lead to a lot of scalarized instructions which may lead to worse code than before? I might be wrong though. I just rather go into the direction that if other targets implement it and succeed, we than move it to target independent code. Additional thoughts?

Actually, back to x86, if popcnt isn't supported by some x86 target it currently leads to this bitmath scalarized code for each element and it would be always profitable to emit the vectorized code instead - tested it for v4i32, v2i64, v4i64 and v8i32 and it performs better. Gonna update the patch to reflect that. For instance "-arch x86_64" doesn't assume popcnt by default, since it is a separate feature, in cases like this we would always win.

[bruno]

Patch updated!

[bruno]

Ping :-)

[chandlerc]

I see you've gone ahead and committed this.

Please actually implement the significantly better algorithm I point you at
if you're going to have an x86-speciifc implementation. Also please
implement this for the other vector types. I really don't want this to be
left in a half-done state forever.

Expanding to other vector types doesn't seem unreasonable to do in a
follow-up patch, but I think it would have been better to start off with
the final algorithm. We now have a pretty substantial pile of code in the
x86 backend that will be completely replaced. =/

[bruno]

I see you've gone ahead and committed this.

Please actually implement the significantly better algorithm I point you at
if you're going to have an x86-speciifc implementation. Also please
implement this for the other vector types. I really don't want this to be
left in a half-done state forever.

I understand your concern, I'll get to it, promise :-)

Expanding to other vector types doesn't seem unreasonable to do in a
follow-up patch, but I think it would have been better to start off with
the final algorithm. We now have a pretty substantial pile of code in the
x86 backend that will be completely replaced. =/

Although you're probably right, I rather not do it before giving it appropriate
measurements which I couldn't get yet. Also, since we already know this performs
better than previous expansions, at least we have better generation for ctpop
in the meantime.

Thanks for the feedback and ideas :D

[chandlerc]

And three months later, you still haven't implemented the requested changes during code review.

Please do so, and quickly. I'm really unhappy about the behavior of promising to make changes requested during code review in order to get past code review, and then failing to follow through on them. I'm very tempted to just revert the patch until you actually have time to address this fully.

[bruno]

I guess this makes it four months later now =T

Really sorry for the late reply. You're totally right, my bad I
haven't tackled this from my priority list despite promises.
However, I intend to resume this work in one week or two, but fell
free to revert it if that's sounds like another vague promise :-)

Cheers,

[bruno]

Hi,

This patch implements a faster vector population count based on the algorithm
described in http://wm.ite.pl/articles/sse-popcount.html

It does so by using an in-register lookup table and the pshufb instruction to
compute the popcnt for each byte. Additional instructions are then used to sum
the bytes and produce the result for wider element types. Numbers:

v4i32-avx:

sselookup (v4i32): 1.10211
scalar + ctpop (v4i32): 0.907016 <-- best == ToT
parallelbitmath (v4i32): 1.14124

v8i32-avx:

sselookup (v8i32): 1.97514 <-- best == patch
scalar + ctpop (v8i32): 2.37118

v8i32-avx2:

sselookup (v8i32): 1.17823
parallelbitmath (v8i32): 1.15288 <-- best == ToT

v2i64-avx:

scalar + ctpop (v2i64): 0.589292 <-- best == ToT
sselookup (v2i64): 0.865797
parallelbitmath (v2i64): 1.31027

v4i64-avx:

scalar + ctpop (v4i64): 0.903523 <-- best == ToT
sselookup (v4i64): 1.11988

v4i64-avx2:

scalar + ctpop (v4i64): 0.895486
sselookup (v4i64): 0.677801 <-- best == patch
parallelbitmath (v4i64): 1.02711

v16i8-avx:

scalar + ctpop (v16i8): 4.1569
sselookup (v16i8): 0.508693 <-- best == patch

v32i8-avx:

scalar + ctpop (v32i8): 8.32336
sselookup (v32i8): 0.961657 <-- best == patch

v32i8-avx2:

scalar + ctpop (v32i8): 8.79509
sselookup (v32i8): 0.487716 <-- best == patch

v8i16-avx:

scalar + ctpop (v8i16): 1.86908
sselookup (v8i16): 0.755885 <-- best == patch

v16i16-avx:

scalar + ctpop (v16i16): 4.08575
sselookup (v16i16): 1.32838 <-- best == patch

v16i16-avx2:

scalar + ctpop (v16i16): 4.19101
sselookup (v16i16): 1.18095 <-- best == patch

More info available at
https://github.com/bcardosolopes/llvm-vpopcount

One unexpected case is v8i32-avx2. Although sselookup and parallelbitmath vary
in which runs faster, I've seen the latter yielding slightly better results in
multiple runs. I would expect sselookup to always be faster because it has
fewer instructions but looks like there's some latency/resource conflict issue
going on.

Given the slightly perf diff between sselookup and parallelbitmath for
v8i32-avx2, I've removed parallelbitmath completely in this patch and left
sselookup as the default for this type too. We can later on change the behavior
for this type back to parallelbitmath (see the next paragraph).

This patch only improves the x86 specific part of vector popcnt. The previous
approach implemented for x86 in Dec 2014, the parallelbitmath, is generally
inferior. Given its target independent nature it will get resubmitted in a next
patch as a target independent expansion for vector popcnt, since (although not
anymore for x86) it's much better than the current scalar expansion we
currently do.

[bruno]

The assembly for v8i32-avx2 cases:

https://github.com/bcardosolopes/llvm-vpopcount/blob/master/v8i32/avx2/v8i32-bitmath.s
https://github.com/bcardosolopes/llvm-vpopcount/blob/master/v8i32/avx2/v8i32-sselookup.s

[bruno]

Abandon this one since a improved version was committed way back in http://reviews.llvm.org/D10084.

lib/Target/X86/X86ISelLowering.cpp

if (!TM.Options.UseSoftFloat && Subtarget->hasFp256()) {
     setOperationAction(ISD::ZERO_EXTEND,       MVT::v16i16, Custom);
     setOperationAction(ISD::ANY_EXTEND,        MVT::v4i64, Custom);
     setOperationAction(ISD::ANY_EXTEND,        MVT::v8i32, Custom);
     setOperationAction(ISD::ANY_EXTEND,        MVT::v16i16, Custom);
     setOperationAction(ISD::TRUNCATE,          MVT::v16i8, Custom);
     setOperationAction(ISD::TRUNCATE,          MVT::v8i16, Custom);
     setOperationAction(ISD::TRUNCATE,          MVT::v4i32, Custom);
 
+    setOperationAction(ISD::CTPOP,             MVT::v8i32, Custom);
+
     if (Subtarget->hasFMA() || Subtarget->hasFMA4()) {
       setOperationAction(ISD::FMA,             MVT::v8f32, Legal);
       setOperationAction(ISD::FMA,             MVT::v4f64, Legal);
       setOperationAction(ISD::FMA,             MVT::v4f32, Legal);
       setOperationAction(ISD::FMA,             MVT::v2f64, Legal);
       setOperationAction(ISD::FMA,             MVT::f32, Legal);
       setOperationAction(ISD::FMA,             MVT::f64, Legal);
     }
if (DstVT==MVT::i64 && SrcVT.isVector())
     return Op;
   // MMX <=> MMX conversions are Legal.
   if (SrcVT.isVector() && DstVT.isVector())
     return Op;
   // All other conversions need to be expanded.
   return SDValue();
 }
 
+static SDValue LowerCTPOP(SDValue Op, const X86Subtarget *Subtarget,
+                          SelectionDAG &DAG) {
+  SDNode *Node = Op.getNode();
+  SDLoc dl(Node);
+
+  Op = Op.getOperand(0);
+  EVT VT = Op.getValueType();
+  assert((VT.is128BitVector() || VT.is256BitVector()) &&
+         "CTPOP lowering only implemented for 128/256-bit wide vector types");
+
+  unsigned NumElts = VT.getVectorNumElements();
+  EVT EltVT = VT.getVectorElementType();
+  unsigned Len = EltVT.getSizeInBits();
+
+  assert(EltVT.isInteger() && Len == 32 &&
+         "CTPOP not implemented for this vector element type.");
+
+  if (VT.is256BitVector() && !Subtarget->hasInt256()) {
+    // Split v8i32 into two 128-bit CTPOP and merge back the result. Note
+    // that ctpop.v4i32 is not custom lowered by default, however we do it here
+    // because two ctpop.v4i32 for v8i32 are still better than the default
+    // implementation.
+    SDValue V0 = Extract128BitVector(Op, 0, DAG, dl);
+    SDValue V1 = Extract128BitVector(Op, NumElts/2, DAG, dl);
+    V0 = LowerCTPOP(DAG.getNode(ISD::CTPOP, dl, V0.getValueType(), V0),
+                    Subtarget, DAG);
+    V1 = LowerCTPOP(DAG.getNode(ISD::CTPOP, dl, V1.getValueType(), V1),
+                    Subtarget, DAG);
+    return DAG.getNode(ISD::CONCAT_VECTORS, dl, VT, V0, V1);
+  }
+
+  // X86 canonicalize ANDs to vXi64, generate the appropriate bitcasts to avoid
+  // extra legalization.
+  MVT BitcastVT = VT.is256BitVector() ? MVT::v4i64 : MVT::v2i64;
+
+  // This is the "best" algorithm from
+  // http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel
+  // with a minor tweak to use a series of adds + shifts instead of vector
+  // multiplications.
+  SDValue Cst55 = DAG.getConstant(APInt::getSplat(Len, APInt(8, 0x55)), EltVT);
+  SDValue Cst33 = DAG.getConstant(APInt::getSplat(Len, APInt(8, 0x33)), EltVT);
+  SDValue Cst0F = DAG.getConstant(APInt::getSplat(Len, APInt(8, 0x0F)), EltVT);
+
+  // v = v - ((v >> 1) & 0x55555555...)
+  SmallVector<SDValue, 8> Ones(NumElts, DAG.getConstant(1, EltVT));
+  SDValue OnesV = DAG.getNode(ISD::BUILD_VECTOR, dl, VT, Ones);
+  SDValue Srl = DAG.getNode(ISD::SRL, dl, VT, Op, OnesV);
+  Srl = DAG.getNode(ISD::BITCAST, dl, BitcastVT, Srl);
+
+  SmallVector<SDValue, 8> Mask55(NumElts, Cst55);
+  SDValue M55 = DAG.getNode(ISD::BUILD_VECTOR, dl, VT, Mask55);
+  M55 = DAG.getNode(ISD::BITCAST, dl, BitcastVT, M55);
+
+  SDValue And = DAG.getNode(ISD::AND, dl, Srl.getValueType(), Srl, M55);
+  And = DAG.getNode(ISD::BITCAST, dl, VT, And);
+  SDValue Sub = DAG.getNode(ISD::SUB, dl, VT, Op, And);
+
+  // v = (v & 0x33333333...) + ((v >> 2) & 0x33333333...)
+  SmallVector<SDValue, 8> Mask33(NumElts, Cst33);
+  SDValue M33 = DAG.getNode(ISD::BUILD_VECTOR, dl, VT, Mask33);
+  SmallVector<SDValue, 8> Twos(NumElts, DAG.getConstant(2, EltVT));
+  SDValue TwosV = DAG.getNode(ISD::BUILD_VECTOR, dl, VT, Twos);
+
+  Srl = DAG.getNode(ISD::SRL, dl, VT, Sub, TwosV);
+  Srl = DAG.getNode(ISD::BITCAST, dl, BitcastVT, Srl);
+  M33 = DAG.getNode(ISD::BITCAST, dl, BitcastVT, M33);
+  Sub = DAG.getNode(ISD::BITCAST, dl, BitcastVT, Sub);
+
+  SDValue AndRHS = DAG.getNode(ISD::AND, dl, M33.getValueType(), Srl, M33);
+  SDValue AndLHS = DAG.getNode(ISD::AND, dl, M33.getValueType(), Sub, M33);
+  if (VT != AndRHS.getValueType()) {
+    AndRHS = DAG.getNode(ISD::BITCAST, dl, VT, AndRHS);
+    AndLHS = DAG.getNode(ISD::BITCAST, dl, VT, AndLHS);
+  }
+  SDValue Add = DAG.getNode(ISD::ADD, dl, VT, AndLHS, AndRHS);
+
+  // v = (v + (v >> 4)) & 0x0F0F0F0F...
+  SmallVector<SDValue, 8> Fours(NumElts, DAG.getConstant(4, EltVT));
+  SDValue FoursV = DAG.getNode(ISD::BUILD_VECTOR, dl, VT, Fours);
+  Srl = DAG.getNode(ISD::SRL, dl, VT, Add, FoursV);
+  Add = DAG.getNode(ISD::ADD, dl, VT, Add, Srl);
+
+  SmallVector<SDValue, 8> Mask0F(NumElts, Cst0F);
+  SDValue M0F = DAG.getNode(ISD::BUILD_VECTOR, dl, VT, Mask0F);
+  Add = DAG.getNode(ISD::BITCAST, dl, BitcastVT, Add);
+  M0F = DAG.getNode(ISD::BITCAST, dl, BitcastVT, M0F);
+  And = DAG.getNode(ISD::AND, dl, M0F.getValueType(), Add, M0F);
+  And = DAG.getNode(ISD::BITCAST, dl, VT, And);
+
+  // The algorithm mentioned above uses:
+  //    v = (v * 0x01010101...) >> (Len - 8)
+  //
+  // Change it to use vector adds + vector shifts which yield faster results on
+  // Haswell than using vector integer multiplication.
+  //
+  // For i32 elements:
+  //    v = v + (v >> 8)
+  //    v = v + (v >> 16)
+  //
+  Add = And;
+  SmallVector<SDValue, 8> Csts;
+  for (unsigned i = 8; i <= Len/2; i *= 2) {
+    Csts.assign(NumElts, DAG.getConstant(i, EltVT));
+    SDValue CstsV = DAG.getNode(ISD::BUILD_VECTOR, dl, VT, Csts);
+    Srl = DAG.getNode(ISD::SRL, dl, VT, Add, CstsV);
+    Add = DAG.getNode(ISD::ADD, dl, VT, Add, Srl);
+    Csts.clear();
+  }
+
+  // The result is on the least significant 6-bits
+  SDValue Cst3F = DAG.getConstant(APInt(Len, 0x3F), EltVT);
+  SmallVector<SDValue, 8> Cst3FV(NumElts, Cst3F);
+  SDValue M3F = DAG.getNode(ISD::BUILD_VECTOR, dl, VT, Cst3FV);
+  Add = DAG.getNode(ISD::BITCAST, dl, BitcastVT, Add);
+  M3F = DAG.getNode(ISD::BITCAST, dl, BitcastVT, M3F);
+  And = DAG.getNode(ISD::AND, dl, M3F.getValueType(), Add, M3F);
+  And = DAG.getNode(ISD::BITCAST, dl, VT, And);
+
+  return And;
+}
+
 static SDValue LowerLOAD_SUB(SDValue Op, SelectionDAG &DAG) {
   SDNode *Node = Op.getNode();
   SDLoc dl(Node);
   EVT T = Node->getValueType(0);
   SDValue negOp = DAG.getNode(ISD::SUB, dl, T,
                               DAG.getConstant(0, T), Node->getOperand(2));
   return DAG.getAtomic(ISD::ATOMIC_LOAD_ADD, dl,
                        cast<AtomicSDNode>(Node)->getMemoryVT(),

 ///
 SDValue X86TargetLowering::LowerOperation(SDValue Op, SelectionDAG &DAG) const {
   switch (Op.getOpcode()) {
   default: llvm_unreachable("Should not custom lower this!");
   case ISD::SIGN_EXTEND_INREG:  return LowerSIGN_EXTEND_INREG(Op,DAG);
   case ISD::ATOMIC_FENCE:       return LowerATOMIC_FENCE(Op, Subtarget, DAG);
   case ISD::ATOMIC_CMP_SWAP_WITH_SUCCESS:
     return LowerCMP_SWAP(Op, Subtarget, DAG);
+  case ISD::CTPOP:              return LowerCTPOP(Op, Subtarget, DAG);
   case ISD::ATOMIC_LOAD_SUB:    return LowerLOAD_SUB(Op,DAG);
   case ISD::ATOMIC_STORE:       return LowerATOMIC_STORE(Op,DAG);
   case ISD::BUILD_VECTOR:       return LowerBUILD_VECTOR(Op, DAG);
   case ISD::CONCAT_VECTORS:     return LowerCONCAT_VECTORS(Op, DAG);
   case ISD::VECTOR_SHUFFLE:     return LowerVECTOR_SHUFFLE(Op, DAG);
   case ISD::VSELECT:            return LowerVSELECT(Op, DAG);
   case ISD::EXTRACT_VECTOR_ELT: return LowerEXTRACT_VECTOR_ELT(Op, DAG);
   case ISD::INSERT_VECTOR_ELT:  return LowerINSERT_VECTOR_ELT(Op, DAG);

test/CodeGen/X86/vector-ctpop.ll

+; RUN: llc < %s -mtriple=x86_64-apple-darwin -mcpu=corei7-avx | FileCheck -check-prefix=AVX1 %s
+; RUN: llc < %s -mtriple=x86_64-apple-darwin -mcpu=core-avx2 | FileCheck -check-prefix=AVX2 %s
+
+; This tests the x86 custom lowering for the llvm.ctpop.v8i32 instrinc. It
+; implements a vectorized version of the following algorithm:
+;
+; v = v - ((v >> 1) & 0x55555555);
+; v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
+; v = ((v + (v >> 4) & 0xF0F0F0F)
+; v = v + (v >> 8)
+; v = v + (v >> 16)
+; v = v & 0x0000003F
+
+define <8 x i32> @test0(<8 x i32> %x) {
+; AVX2-LABEL: @test0
+; AVX1-LABEL: @test0
+entry:
+; AVX2:  vpsrld  $1, %ymm
+; AVX2-NEXT:  vpbroadcastd
+; AVX2-NEXT:  vpand
+; AVX2-NEXT:  vpsubd
+; AVX2-NEXT:  vpbroadcastd
+; AVX2-NEXT:  vpand
+; AVX2-NEXT:  vpsrld  $2
+; AVX2-NEXT:  vpand
+; AVX2-NEXT:  vpaddd
+; AVX2-NEXT:  vpsrld  $4
+; AVX2-NEXT:  vpaddd
+; AVX2-NEXT:  vpbroadcastd
+; AVX2-NEXT:  vpand
+; AVX2-NEXT:  vpsrld  $8
+; AVX2-NEXT:  vpaddd
+; AVX2-NEXT:  vpsrld  $16
+; AVX2-NEXT:  vpaddd
+; AVX2-NEXT:  vpbroadcastd
+; AVX2-NEXT:  vpand
+; AVX1: vextractf128  $1, %ymm
+; AVX1-NEXT:  vpsrld  $1, %xmm
+; AVX1-NEXT:  vmovdqa
+; AVX1-NEXT:  vpand
+; AVX1-NEXT:  vpsubd
+; AVX1-NEXT:  vmovdqa
+; AVX1-NEXT:  vpand
+; AVX1-NEXT:  vpsrld  $2
+; AVX1-NEXT:  vpand
+; AVX1-NEXT:  vpaddd
+; AVX1-NEXT:  vpsrld  $4
+; AVX1-NEXT:  vpaddd
+; AVX1-NEXT:  vmovdqa
+; AVX1-NEXT:  vpand
+; AVX1-NEXT:  vpsrld  $8
+; AVX1-NEXT:  vpaddd
+; AVX1-NEXT:  vpsrld  $16
+; AVX1-NEXT:  vpaddd
+; AVX1-NEXT:  vmovdqa
+; AVX1-NEXT:  vpand
+; AVX1-NEXT:  vpsrld  $1, %xmm
+; AVX1-NEXT:  vpand
+; AVX1-NEXT:  vpsubd
+; AVX1-NEXT:  vpand
+; AVX1-NEXT:  vpsrld  $2
+; AVX1-NEXT:  vpand
+; AVX1-NEXT:  vpaddd
+; AVX1-NEXT:  vpsrld  $4
+; AVX1-NEXT:  vpaddd
+; AVX1-NEXT:  vpand
+; AVX1-NEXT:  vpsrld  $8
+; AVX1-NEXT:  vpaddd
+; AVX1-NEXT:  vpsrld  $16
+; AVX1-NEXT:  vpaddd
+; AVX1-NEXT:  vpand
+; AVX1-NEXT:  vinsertf128 $1
+  %y = call <8 x i32> @llvm.ctpop.v8i32(<8 x i32> %x)
+  ret <8 x i32> %y
+}
+
+declare <8 x i32> @llvm.ctpop.v8i32(<8 x i32>)
+