Implement count leading zeros (ctlz), count trailing zeros (cttz), and count
population (ctpop). Generic lowering is implemented, however only promotion
is implemented for SelectionDAG at the moment.
More coming soon.
llvm-svn: 21676
diff --git a/llvm/lib/CodeGen/SelectionDAG/LegalizeDAG.cpp b/llvm/lib/CodeGen/SelectionDAG/LegalizeDAG.cpp
index 5257082..adb88bf 100644
--- a/llvm/lib/CodeGen/SelectionDAG/LegalizeDAG.cpp
+++ b/llvm/lib/CodeGen/SelectionDAG/LegalizeDAG.cpp
@@ -987,6 +987,51 @@
}
break;
+ 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, MVT::i1, 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:
+ assert(0 && "Cannot expand this yet!");
+ break;
+ }
+ break;
+
// Unary operators
case ISD::FABS:
case ISD::FNEG:
diff --git a/llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp b/llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
index f9b347d..f4d7adc 100644
--- a/llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
+++ b/llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
@@ -1328,10 +1328,13 @@
return SDOperand(N, 0);
}
-SDOperand SelectionDAG::getSrcValue(const Value* v) {
- SDNode *N = new SrcValueSDNode(v);
+SDOperand SelectionDAG::getSrcValue(const Value* v, int offset) {
+ if (v && ValueNodes[std::make_pair(v,offset)])
+ return SDOperand(ValueNodes[std::make_pair(v,offset)], 0);
+ SDNode *N = new SrcValueSDNode(v, offset);
N->setValueTypes(MVT::Other);
- // FIXME: memoize NODES
+ if (v) //only track non-null values
+ ValueNodes[std::make_pair(v,offset)] = N;
AllNodes.push_back(N);
return SDOperand(N, 0);
}
diff --git a/llvm/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp b/llvm/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp
index 20483d4..26be651 100644
--- a/llvm/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp
+++ b/llvm/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp
@@ -707,6 +707,21 @@
DAG.setRoot(DAG.getNode(ISD::PCMARKER, MVT::Other, getRoot(), Num));
return;
}
+ case Intrinsic::cttz:
+ setValue(&I, DAG.getNode(ISD::CTTZ,
+ getValue(I.getOperand(1)).getValueType(),
+ getValue(I.getOperand(1))));
+ return;
+ case Intrinsic::ctlz:
+ setValue(&I, DAG.getNode(ISD::CTLZ,
+ getValue(I.getOperand(1)).getValueType(),
+ getValue(I.getOperand(1))));
+ return;
+ case Intrinsic::ctpop:
+ setValue(&I, DAG.getNode(ISD::CTPOP,
+ getValue(I.getOperand(1)).getValueType(),
+ getValue(I.getOperand(1))));
+ return;
}
SDOperand Callee;