+ case ISD::CTPOP:
+ case ISD::CTTZ:
+ case ISD::CTLZ:
+ Tmp1 = LegalizeOp(Node->getOperand(0)); // Op
+ switch (TLI.getOperationAction(Node->getOpcode(), Node->getValueType(0))) {
+ case TargetLowering::Legal:
+ if (Tmp1 != Node->getOperand(0))
+ Result = DAG.getNode(Node->getOpcode(), Node->getValueType(0), Tmp1);
+ break;
+ case TargetLowering::Promote: {
+ MVT::ValueType OVT = Tmp1.getValueType();
+ MVT::ValueType NVT = TLI.getTypeToPromoteTo(Node->getOpcode(), OVT);
+
+ // Zero extend the argument.
+ Tmp1 = DAG.getNode(ISD::ZERO_EXTEND, NVT, Tmp1);
+ // Perform the larger operation, then subtract if needed.
+ Tmp1 = DAG.getNode(Node->getOpcode(), Node->getValueType(0), Tmp1);
+ switch(Node->getOpcode())
+ {
+ case ISD::CTPOP:
+ Result = Tmp1;
+ break;
+ case ISD::CTTZ:
+ //if Tmp1 == sizeinbits(NVT) then Tmp1 = sizeinbits(Old VT)
+ Tmp2 = DAG.getSetCC(ISD::SETEQ, TLI.getSetCCResultTy(), Tmp1,
+ DAG.getConstant(getSizeInBits(NVT), NVT));
+ Result = DAG.getNode(ISD::SELECT, NVT, Tmp2,
+ DAG.getConstant(getSizeInBits(OVT),NVT), Tmp1);
+ break;
+ case ISD::CTLZ:
+ //Tmp1 = Tmp1 - (sizeinbits(NVT) - sizeinbits(Old VT))
+ Result = DAG.getNode(ISD::SUB, NVT, Tmp1,
+ DAG.getConstant(getSizeInBits(NVT) -
+ getSizeInBits(OVT), NVT));
+ break;
+ }
+ break;
+ }
+ case TargetLowering::Custom:
+ assert(0 && "Cannot custom handle this yet!");
+ case TargetLowering::Expand:
+ switch(Node->getOpcode())
+ {
+ case ISD::CTPOP: {
+ static const uint64_t mask[6] = {
+ 0x5555555555555555ULL, 0x3333333333333333ULL,
+ 0x0F0F0F0F0F0F0F0FULL, 0x00FF00FF00FF00FFULL,
+ 0x0000FFFF0000FFFFULL, 0x00000000FFFFFFFFULL
+ };
+ MVT::ValueType VT = Tmp1.getValueType();
+ MVT::ValueType ShVT = TLI.getShiftAmountTy();
+ unsigned len = getSizeInBits(VT);
+ for (unsigned i = 0; (1U << i) <= (len / 2); ++i) {
+ //x = (x & mask[i][len/8]) + (x >> (1 << i) & mask[i][len/8])
+ Tmp2 = DAG.getConstant(mask[i], VT);
+ Tmp3 = DAG.getConstant(1ULL << i, ShVT);
+ Tmp1 = DAG.getNode(ISD::ADD, VT,
+ DAG.getNode(ISD::AND, VT, Tmp1, Tmp2),
+ DAG.getNode(ISD::AND, VT,
+ DAG.getNode(ISD::SRL, VT, Tmp1, Tmp3),
+ Tmp2));
+ }
+ Result = Tmp1;
+ break;
+ }
+ case ISD::CTLZ: {
+ /* for now, we do this:
+ x = x | (x >> 1);
+ x = x | (x >> 2);
+ ...
+ x = x | (x >>16);
+ x = x | (x >>32); // for 64-bit input
+ return popcount(~x);
+
+ but see also: http://www.hackersdelight.org/HDcode/nlz.cc */
+ MVT::ValueType VT = Tmp1.getValueType();
+ MVT::ValueType ShVT = TLI.getShiftAmountTy();
+ unsigned len = getSizeInBits(VT);
+ for (unsigned i = 0; (1U << i) <= (len / 2); ++i) {
+ Tmp3 = DAG.getConstant(1ULL << i, ShVT);
+ Tmp1 = DAG.getNode(ISD::OR, VT, Tmp1,
+ DAG.getNode(ISD::SRL, VT, Tmp1, Tmp3));
+ }
+ Tmp3 = DAG.getNode(ISD::XOR, VT, Tmp1, DAG.getConstant(~0ULL, VT));
+ Result = LegalizeOp(DAG.getNode(ISD::CTPOP, VT, Tmp3));
+ break;
+ }
+ case ISD::CTTZ: {
+ // for now, we use: { return popcount(~x & (x - 1)); }
+ // unless the target has ctlz but not ctpop, in which case we use:
+ // { return 32 - nlz(~x & (x-1)); }
+ // see also http://www.hackersdelight.org/HDcode/ntz.cc
+ MVT::ValueType VT = Tmp1.getValueType();
+ Tmp2 = DAG.getConstant(~0ULL, VT);
+ Tmp3 = DAG.getNode(ISD::AND, VT,
+ DAG.getNode(ISD::XOR, VT, Tmp1, Tmp2),
+ DAG.getNode(ISD::SUB, VT, Tmp1,
+ DAG.getConstant(1, VT)));
+ // If ISD::CTLZ is legal and CTPOP isn't, then do that instead
+ if (TLI.getOperationAction(ISD::CTPOP, VT) != TargetLowering::Legal &&
+ TLI.getOperationAction(ISD::CTLZ, VT) == TargetLowering::Legal) {
+ Result = LegalizeOp(DAG.getNode(ISD::SUB, VT,
+ DAG.getConstant(getSizeInBits(VT), VT),
+ DAG.getNode(ISD::CTLZ, VT, Tmp3)));
+ } else {
+ Result = LegalizeOp(DAG.getNode(ISD::CTPOP, VT, Tmp3));
+ }
+ break;
+ }
+ default:
+ assert(0 && "Cannot expand this yet!");
+ break;
+ }
+ break;
+ }
+ break;
+