riscv popcount lowering shouldn't call __muldi3/__mulsi3

[efriedma-quic]

Consider:

int a(unsigned x) { return __builtin_popcount(x); }

With -march=rv32i, this generates a call to __mulsi3. This is likely to be slow; if we don't have "m", we should use shifts instead.

[llvmbot]

@llvm/issue-subscribers-backend-risc-v

Author: Eli Friedman (efriedma-quic)

Consider:

int a(unsigned x) { return __builtin_popcount(x); }

With -march=rv32i, this generates a call to __mulsi3. This is likely to be slow; if we don't have "m", we should use shifts instead.

[wangpc-pp]

We are using multiply here because this is the default expanding of ISD::CTPOP.

llvm-project/llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp

Lines 8653 to 8718 in 72c729f

	SDValue TargetLowering::expandCTPOP(SDNode *Node, SelectionDAG &DAG) const {
	SDLoc dl(Node);
	EVT VT = Node->getValueType(0);
	EVT ShVT = getShiftAmountTy(VT, DAG.getDataLayout());
	SDValue Op = Node->getOperand(0);
	unsigned Len = VT.getScalarSizeInBits();
	assert(VT.isInteger() && "CTPOP not implemented for this type.");
	// TODO: Add support for irregular type lengths.
	if (!(Len <= 128 && Len % 8 == 0))
	return SDValue();
	// Only expand vector types if we have the appropriate vector bit operations.
	if (VT.isVector() && !canExpandVectorCTPOP(*this, VT))
	return SDValue();
	// This is the "best" algorithm from
	// http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel
	SDValue Mask55 =
	DAG.getConstant(APInt::getSplat(Len, APInt(8, 0x55)), dl, VT);
	SDValue Mask33 =
	DAG.getConstant(APInt::getSplat(Len, APInt(8, 0x33)), dl, VT);
	SDValue Mask0F =
	DAG.getConstant(APInt::getSplat(Len, APInt(8, 0x0F)), dl, VT);
	// v = v - ((v >> 1) & 0x55555555...)
	Op = DAG.getNode(ISD::SUB, dl, VT, Op,
	DAG.getNode(ISD::AND, dl, VT,
	DAG.getNode(ISD::SRL, dl, VT, Op,
	DAG.getConstant(1, dl, ShVT)),
	Mask55));
	// v = (v & 0x33333333...) + ((v >> 2) & 0x33333333...)
	Op = DAG.getNode(ISD::ADD, dl, VT, DAG.getNode(ISD::AND, dl, VT, Op, Mask33),
	DAG.getNode(ISD::AND, dl, VT,
	DAG.getNode(ISD::SRL, dl, VT, Op,
	DAG.getConstant(2, dl, ShVT)),
	Mask33));
	// v = (v + (v >> 4)) & 0x0F0F0F0F...
	Op = DAG.getNode(ISD::AND, dl, VT,
	DAG.getNode(ISD::ADD, dl, VT, Op,
	DAG.getNode(ISD::SRL, dl, VT, Op,
	DAG.getConstant(4, dl, ShVT))),
	Mask0F);
	if (Len <= 8)
	return Op;
	// Avoid the multiply if we only have 2 bytes to add.
	// TODO: Only doing this for scalars because vectors weren't as obviously
	// improved.
	if (Len == 16 && !VT.isVector()) {
	// v = (v + (v >> 8)) & 0x00FF;
	return DAG.getNode(ISD::AND, dl, VT,
	DAG.getNode(ISD::ADD, dl, VT, Op,
	DAG.getNode(ISD::SRL, dl, VT, Op,
	DAG.getConstant(8, dl, ShVT))),
	DAG.getConstant(0xFF, dl, VT));
	}
	// v = (v * 0x01010101...) >> (Len - 8)
	SDValue Mask01 =
	DAG.getConstant(APInt::getSplat(Len, APInt(8, 0x01)), dl, VT);
	return DAG.getNode(ISD::SRL, dl, VT,
	DAG.getNode(ISD::MUL, dl, VT, Op, Mask01),
	DAG.getConstant(Len - 8, dl, ShVT));
	}

We may need custom lowering of ISD::CTPOP when there is no m and Zbb.

[topperc]

We are using multiply here because this is the default expanding of ISD::CTPOP.

llvm-project/llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp

Lines 8653 to 8718 in 72c729f

	SDValue TargetLowering::expandCTPOP(SDNode *Node, SelectionDAG &DAG) const {
	SDLoc dl(Node);
	EVT VT = Node->getValueType(0);
	EVT ShVT = getShiftAmountTy(VT, DAG.getDataLayout());
	SDValue Op = Node->getOperand(0);
	unsigned Len = VT.getScalarSizeInBits();
	assert(VT.isInteger() && "CTPOP not implemented for this type.");
	// TODO: Add support for irregular type lengths.
	if (!(Len <= 128 && Len % 8 == 0))
	return SDValue();
	// Only expand vector types if we have the appropriate vector bit operations.
	if (VT.isVector() && !canExpandVectorCTPOP(*this, VT))
	return SDValue();
	// This is the "best" algorithm from
	// http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel
	SDValue Mask55 =
	DAG.getConstant(APInt::getSplat(Len, APInt(8, 0x55)), dl, VT);
	SDValue Mask33 =
	DAG.getConstant(APInt::getSplat(Len, APInt(8, 0x33)), dl, VT);
	SDValue Mask0F =
	DAG.getConstant(APInt::getSplat(Len, APInt(8, 0x0F)), dl, VT);
	// v = v - ((v >> 1) & 0x55555555...)
	Op = DAG.getNode(ISD::SUB, dl, VT, Op,
	DAG.getNode(ISD::AND, dl, VT,
	DAG.getNode(ISD::SRL, dl, VT, Op,
	DAG.getConstant(1, dl, ShVT)),
	Mask55));
	// v = (v & 0x33333333...) + ((v >> 2) & 0x33333333...)
	Op = DAG.getNode(ISD::ADD, dl, VT, DAG.getNode(ISD::AND, dl, VT, Op, Mask33),
	DAG.getNode(ISD::AND, dl, VT,
	DAG.getNode(ISD::SRL, dl, VT, Op,
	DAG.getConstant(2, dl, ShVT)),
	Mask33));
	// v = (v + (v >> 4)) & 0x0F0F0F0F...
	Op = DAG.getNode(ISD::AND, dl, VT,
	DAG.getNode(ISD::ADD, dl, VT, Op,
	DAG.getNode(ISD::SRL, dl, VT, Op,
	DAG.getConstant(4, dl, ShVT))),
	Mask0F);
	if (Len <= 8)
	return Op;
	// Avoid the multiply if we only have 2 bytes to add.
	// TODO: Only doing this for scalars because vectors weren't as obviously
	// improved.
	if (Len == 16 && !VT.isVector()) {
	// v = (v + (v >> 8)) & 0x00FF;
	return DAG.getNode(ISD::AND, dl, VT,
	DAG.getNode(ISD::ADD, dl, VT, Op,
	DAG.getNode(ISD::SRL, dl, VT, Op,
	DAG.getConstant(8, dl, ShVT))),
	DAG.getConstant(0xFF, dl, VT));
	}
	// v = (v * 0x01010101...) >> (Len - 8)
	SDValue Mask01 =
	DAG.getConstant(APInt::getSplat(Len, APInt(8, 0x01)), dl, VT);
	return DAG.getNode(ISD::SRL, dl, VT,
	DAG.getNode(ISD::MUL, dl, VT, Op, Mask01),
	DAG.getConstant(Len - 8, dl, ShVT));
	}

We may need custom lowering of ISD::CTPOP when there is no m and Zbb.

Can we check isOperationLegalOrCustom in the default handler?

[wangpc-pp]

We are using multiply here because this is the default expanding of ISD::CTPOP.

llvm-project/llvm/lib/CodeGen/SelectionDAG/TargetLowering.cpp

Lines 8653 to 8718 in 72c729f

	SDValue TargetLowering::expandCTPOP(SDNode *Node, SelectionDAG &DAG) const {
	SDLoc dl(Node);
	EVT VT = Node->getValueType(0);
	EVT ShVT = getShiftAmountTy(VT, DAG.getDataLayout());
	SDValue Op = Node->getOperand(0);
	unsigned Len = VT.getScalarSizeInBits();
	assert(VT.isInteger() && "CTPOP not implemented for this type.");
	// TODO: Add support for irregular type lengths.
	if (!(Len <= 128 && Len % 8 == 0))
	return SDValue();
	// Only expand vector types if we have the appropriate vector bit operations.
	if (VT.isVector() && !canExpandVectorCTPOP(*this, VT))
	return SDValue();
	// This is the "best" algorithm from
	// http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel
	SDValue Mask55 =
	DAG.getConstant(APInt::getSplat(Len, APInt(8, 0x55)), dl, VT);
	SDValue Mask33 =
	DAG.getConstant(APInt::getSplat(Len, APInt(8, 0x33)), dl, VT);
	SDValue Mask0F =
	DAG.getConstant(APInt::getSplat(Len, APInt(8, 0x0F)), dl, VT);
	// v = v - ((v >> 1) & 0x55555555...)
	Op = DAG.getNode(ISD::SUB, dl, VT, Op,
	DAG.getNode(ISD::AND, dl, VT,
	DAG.getNode(ISD::SRL, dl, VT, Op,
	DAG.getConstant(1, dl, ShVT)),
	Mask55));
	// v = (v & 0x33333333...) + ((v >> 2) & 0x33333333...)
	Op = DAG.getNode(ISD::ADD, dl, VT, DAG.getNode(ISD::AND, dl, VT, Op, Mask33),
	DAG.getNode(ISD::AND, dl, VT,
	DAG.getNode(ISD::SRL, dl, VT, Op,
	DAG.getConstant(2, dl, ShVT)),
	Mask33));
	// v = (v + (v >> 4)) & 0x0F0F0F0F...
	Op = DAG.getNode(ISD::AND, dl, VT,
	DAG.getNode(ISD::ADD, dl, VT, Op,
	DAG.getNode(ISD::SRL, dl, VT, Op,
	DAG.getConstant(4, dl, ShVT))),
	Mask0F);
	if (Len <= 8)
	return Op;
	// Avoid the multiply if we only have 2 bytes to add.
	// TODO: Only doing this for scalars because vectors weren't as obviously
	// improved.
	if (Len == 16 && !VT.isVector()) {
	// v = (v + (v >> 8)) & 0x00FF;
	return DAG.getNode(ISD::AND, dl, VT,
	DAG.getNode(ISD::ADD, dl, VT, Op,
	DAG.getNode(ISD::SRL, dl, VT, Op,
	DAG.getConstant(8, dl, ShVT))),
	DAG.getConstant(0xFF, dl, VT));
	}
	// v = (v * 0x01010101...) >> (Len - 8)
	SDValue Mask01 =
	DAG.getConstant(APInt::getSplat(Len, APInt(8, 0x01)), dl, VT);
	return DAG.getNode(ISD::SRL, dl, VT,
	DAG.getNode(ISD::MUL, dl, VT, Op, Mask01),
	DAG.getConstant(Len - 8, dl, ShVT));
	}

We may need custom lowering of ISD::CTPOP when there is no m and Zbb.

Can we check isOperationLegalOrCustom in the default handler?

Yeah, I think so! But I don't get how to use shifts here...

[efriedma-quic]

x *= 0x01010101; is just x += x << 8; x += x << 16;. Maybe you can save a shift somewhere.

[Explorer09]

I think this should be generic optimization opportunity for converting multiplication with specific constants into shift & add. It would not be limited to the popcount use case.

In #79823, I mentioned that (x * 0x08040201) can be converted to { tmp = x + (x << 9); tmp += (tmp << 18); } and that GCC does perform such optimization.