ctpop lowering in legalize

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

1 files changed, 33 insertions, 1 deletions

diff --git a/lib/CodeGen/SelectionDAG/LegalizeDAG.cpp b/lib/CodeGen/SelectionDAG/LegalizeDAG.cpp
index 020a373844..122ef59008 100644
--- a/lib/CodeGen/SelectionDAG/LegalizeDAG.cpp
+++ b/lib/CodeGen/SelectionDAG/LegalizeDAG.cpp
@@ -1027,7 +1027,39 @@ SDOperand SelectionDAGLegalize::LegalizeOp(SDOperand Op) {
     case TargetLowering::Custom:
       assert(0 && "Cannot custom handle this yet!");
     case TargetLowering::Expand:
-      assert(0 && "Cannot expand this yet!");
+      switch(Node->getOpcode())
+      {
+      case ISD::CTPOP: {
+        static const uint64_t mask[6][9] = {
+          {0, 0x55, 0x5555, 0, 0x55555555, 0, 0, 0, 0x5555555555555555ULL},
+          {0, 0x33, 0x3333, 0, 0x33333333, 0, 0, 0, 0x3333333333333333ULL},
+          {0, 0x0F, 0x0F0F, 0, 0x0F0F0F0F, 0, 0, 0, 0x0F0F0F0F0F0F0F0FULL},
+          {0,    0, 0x00FF, 0, 0x00FF00FF, 0, 0, 0, 0x00FF00FF00FF00FFULL},
+          {0,    0,      0, 0, 0x0000FFFF, 0, 0, 0, 0x0000FFFF0000FFFFULL},
+          {0,    0,      0, 0,          0, 0, 0, 0, 0x00000000FFFFFFFFULL}};
+        MVT::ValueType VT = Tmp1.getValueType();
+        int len = getSizeInBits(VT);
+        for (int i = 0; (1 << i) <= (len / 2); ++i) {
+          //x = (x & mask[i][len/8]) + (x >> (1 << i) & mask[i][len/8])
+          Tmp2 = DAG.getConstant(mask[i][len/8], VT);
+          Tmp3 = DAG.getConstant(1 << i, VT);
+          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::CTTZ:
+//         break;
+//       case ISD::CTLZ:
+//         break;
+      default:
+        assert(0 && "Cannot expand this yet!");
+        break;
+      }
       break;
     }
     break;