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.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@21676 91177308-0d34-0410-b5e6-96231b3b80d8

2 files changed, 13 insertions, 4 deletions

diff --git a/include/llvm/CodeGen/SelectionDAG.h b/include/llvm/CodeGen/SelectionDAG.h
index f3d41ce..a8b42e7 100644
--- a/include/llvm/CodeGen/SelectionDAG.h
+++ b/include/llvm/CodeGen/SelectionDAG.h
@@ -44,6 +44,10 @@ class SelectionDAG {
 
   // AllNodes - All of the nodes in the DAG
   std::vector<SDNode*> AllNodes;
+
+  // ValueNodes - track SrcValue nodes
+  std::map<std::pair<const Value*, int>, SDNode*> ValueNodes;
+
 public:
   SelectionDAG(TargetLowering &tli, MachineFunction &mf) : TLI(tli), MF(mf) {
     EntryNode = Root = getNode(ISD::EntryToken, MVT::Other);
@@ -183,7 +187,7 @@ public:
   SDOperand getLoad(MVT::ValueType VT, SDOperand Chain, SDOperand Ptr, SDOperand SV);
 
   // getSrcValue - construct a node to track a Value* through the backend
-  SDOperand getSrcValue(const Value* I);
+  SDOperand getSrcValue(const Value* I, int offset = 0);
 
   void replaceAllUsesWith(SDOperand Old, SDOperand New) {
     assert(Old != New && "RAUW self!");
diff --git a/include/llvm/CodeGen/SelectionDAGNodes.h b/include/llvm/CodeGen/SelectionDAGNodes.h
index f3be334..97584d7 100644
--- a/include/llvm/CodeGen/SelectionDAGNodes.h
+++ b/include/llvm/CodeGen/SelectionDAGNodes.h
@@ -100,6 +100,9 @@ namespace ISD {
     // Bitwise operators.
     AND, OR, XOR, SHL, SRA, SRL,
 
+    // Counting operators
+    CTTZ, CTLZ, CTPOP,
+
     // Select operator.
     SELECT,
 
@@ -546,7 +549,7 @@ protected:
       ND = N4.Val->getNodeDepth();
     NodeDepth = ND+1;
 
-    Operands.reserve(3); Operands.push_back(N1); Operands.push_back(N2);
+    Operands.reserve(4); Operands.push_back(N1); Operands.push_back(N2);
     Operands.push_back(N3); Operands.push_back(N4);
     N1.Val->Uses.push_back(this); N2.Val->Uses.push_back(this);
     N3.Val->Uses.push_back(this); N4.Val->Uses.push_back(this);
@@ -748,13 +751,15 @@ public:
 
 class SrcValueSDNode : public SDNode {
   const Value *V;
+  int offset;
 protected:
   friend class SelectionDAG;
-  SrcValueSDNode(const Value* v)
-    : SDNode(ISD::SRCVALUE, MVT::Other), V(v) {}
+  SrcValueSDNode(const Value* v, int o)
+    : SDNode(ISD::SRCVALUE, MVT::Other), V(v), offset(o) {}
 
 public:
   const Value *getValue() const { return V; }
+  int getOffset() const { return offset; }
 
   static bool classof(const SrcValueSDNode *) { return true; }
   static bool classof(const SDNode *N) {