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

4 files changed, 262 insertions, 3 deletions

diff --git a/llvm/lib/CodeGen/IntrinsicLowering.cpp b/llvm/lib/CodeGen/IntrinsicLowering.cpp
index 36f413a14f7..0bad510324e 100644
--- a/llvm/lib/CodeGen/IntrinsicLowering.cpp
+++ b/llvm/lib/CodeGen/IntrinsicLowering.cpp
@@ -16,6 +16,7 @@
 #include "llvm/DerivedTypes.h"
 #include "llvm/Module.h"
 #include "llvm/Instructions.h"
+#include "llvm/Type.h"
 #include <iostream>
 
 using namespace llvm;
@@ -164,6 +165,201 @@ void DefaultIntrinsicLowering::LowerIntrinsicCall(CallInst *CI) {
                     AbortFCache);
     break;
   }
+  case Intrinsic::ctpop: {
+    Value *Src = CI->getOperand(1);
+    switch (CI->getOperand(0)->getType()->getTypeID())
+    {
+    case Type::SByteTyID:
+    case Type::UByteTyID:
+      {
+        Value* SA = ConstantUInt::get(Type::UByteTy, 1);
+        Value* MA = ConstantUInt::get(Type::UIntTy, 0x55);
+        Src = BinaryOperator::create(Instruction::Add,
+                BinaryOperator::create(Instruction::And, Src, MA),
+                BinaryOperator::create(Instruction::And, 
+                                       new ShiftInst(Instruction::Shr, Src, SA),
+                                       MA));
+        SA = ConstantUInt::get(Type::UByteTy, 2);
+        MA = ConstantUInt::get(Type::UIntTy, 0x33);
+        Src = BinaryOperator::create(Instruction::Add,
+                BinaryOperator::create(Instruction::And, Src, MA),
+                BinaryOperator::create(Instruction::And,
+                                       new ShiftInst(Instruction::Shr, Src, SA),
+                                       MA));
+        SA = ConstantUInt::get(Type::UByteTy, 4);
+        MA = ConstantUInt::get(Type::UIntTy, 0x0F);
+        Src = BinaryOperator::create(Instruction::Add,
+                BinaryOperator::create(Instruction::And, Src, MA),
+                BinaryOperator::create(Instruction::And, 
+                                       new ShiftInst(Instruction::Shr, Src, SA),
+                                       MA), "ctpop");
+      }
+      break;
+    case Type::ShortTyID:
+    case Type::UShortTyID:
+      {
+        Value* SA = ConstantUInt::get(Type::UByteTy, 1);
+        Value* MA = ConstantUInt::get(Type::UIntTy, 0x5555);
+        Src = BinaryOperator::create(Instruction::Add,
+                BinaryOperator::create(Instruction::And, Src, MA),
+                BinaryOperator::create(Instruction::And, 
+                                       new ShiftInst(Instruction::Shr, Src, SA),
+                                       MA));
+        SA = ConstantUInt::get(Type::UByteTy, 2);
+        MA = ConstantUInt::get(Type::UIntTy, 0x3333);
+        Src = BinaryOperator::create(Instruction::Add,
+                BinaryOperator::create(Instruction::And, Src, MA),
+                BinaryOperator::create(Instruction::And, 
+                                       new ShiftInst(Instruction::Shr, Src, SA),
+                                       MA));
+        SA = ConstantUInt::get(Type::UByteTy, 4);
+        MA = ConstantUInt::get(Type::UIntTy, 0x0F0F);
+        Src = BinaryOperator::create(Instruction::Add,
+                BinaryOperator::create(Instruction::And, Src, MA),
+                BinaryOperator::create(Instruction::And, 
+                                       new ShiftInst(Instruction::Shr, Src, SA),
+                                       MA));
+        SA = ConstantUInt::get(Type::UByteTy, 8);
+        MA = ConstantUInt::get(Type::UIntTy, 0x00FF);
+        Src = BinaryOperator::create(Instruction::Add,
+                BinaryOperator::create(Instruction::And, Src, MA),
+                BinaryOperator::create(Instruction::And, 
+                                       new ShiftInst(Instruction::Shr, Src, SA),
+                                       MA), "ctpop");
+
+      }
+      break;
+    case Type::IntTyID:
+    case Type::UIntTyID:
+      {
+        Value* SA = ConstantUInt::get(Type::UByteTy, 1);
+        Value* MA = ConstantUInt::get(Type::UIntTy, 0x55555555);
+        Src = BinaryOperator::create(Instruction::Add,
+                BinaryOperator::create(Instruction::And, Src, MA),
+                BinaryOperator::create(Instruction::And, 
+                                       new ShiftInst(Instruction::Shr, Src, SA),
+                                       MA));
+        SA = ConstantUInt::get(Type::UByteTy, 2);
+        MA = ConstantUInt::get(Type::UIntTy, 0x33333333);
+        Src = BinaryOperator::create(Instruction::Add,
+                BinaryOperator::create(Instruction::And, Src, MA),
+                BinaryOperator::create(Instruction::And, 
+                                       new ShiftInst(Instruction::Shr, Src, SA),
+                                       MA));
+        SA = ConstantUInt::get(Type::UByteTy, 4);
+        MA = ConstantUInt::get(Type::UIntTy, 0x0F0F0F0F);
+        Src = BinaryOperator::create(Instruction::Add,
+                BinaryOperator::create(Instruction::And, Src, MA),
+                BinaryOperator::create(Instruction::And, 
+                                       new ShiftInst(Instruction::Shr, Src, SA),
+                                       MA));
+        SA = ConstantUInt::get(Type::UByteTy, 8);
+        MA = ConstantUInt::get(Type::UIntTy, 0x00FF00FF);
+        Src = BinaryOperator::create(Instruction::Add,
+                BinaryOperator::create(Instruction::And, Src, MA),
+                BinaryOperator::create(Instruction::And, 
+                                       new ShiftInst(Instruction::Shr, Src, SA),
+                                       MA));
+        SA = ConstantUInt::get(Type::UByteTy, 8);
+        MA = ConstantUInt::get(Type::UIntTy, 0x0000FFFF);
+        Src = BinaryOperator::create(Instruction::Add,
+                BinaryOperator::create(Instruction::And, Src, MA),
+                BinaryOperator::create(Instruction::And, 
+                                       new ShiftInst(Instruction::Shr, Src, SA),
+                                       MA), "ctpop");
+      }
+      break;
+    case Type::LongTyID:
+    case Type::ULongTyID:
+      {
+        Value* SA = ConstantUInt::get(Type::UByteTy, 1);
+        Value* MA = ConstantUInt::get(Type::ULongTy, 0x5555555555555555ULL);
+        Src = BinaryOperator::create(Instruction::Add,
+                BinaryOperator::create(Instruction::And, Src, MA),
+                BinaryOperator::create(Instruction::And, 
+                                       new ShiftInst(Instruction::Shr, Src, SA),
+                                       MA));
+        SA = ConstantUInt::get(Type::UByteTy, 2);
+        MA = ConstantUInt::get(Type::ULongTy, 0x3333333333333333ULL);
+        Src = BinaryOperator::create(Instruction::Add,
+                BinaryOperator::create(Instruction::And, Src, MA),
+                BinaryOperator::create(Instruction::And, 
+                                       new ShiftInst(Instruction::Shr, Src, SA),
+                                       MA));
+        SA = ConstantUInt::get(Type::UByteTy, 4);
+        MA = ConstantUInt::get(Type::ULongTy, 0x0F0F0F0F0F0F0F0FULL);
+        Src = BinaryOperator::create(Instruction::Add,
+                BinaryOperator::create(Instruction::And, Src, MA),
+                BinaryOperator::create(Instruction::And, 
+                                       new ShiftInst(Instruction::Shr, Src, SA),
+                                       MA));
+        SA = ConstantUInt::get(Type::UByteTy, 8);
+        MA = ConstantUInt::get(Type::ULongTy, 0x00FF00FF00FF00FFULL);
+        Src = BinaryOperator::create(Instruction::Add,
+                BinaryOperator::create(Instruction::And, Src, MA),
+                BinaryOperator::create(Instruction::And, 
+                                       new ShiftInst(Instruction::Shr, Src, SA),
+                                       MA));
+        SA = ConstantUInt::get(Type::UByteTy, 16);
+        MA = ConstantUInt::get(Type::ULongTy, 0x00000000FFFFFFFFULL);
+        Src = BinaryOperator::create(Instruction::Add,
+                BinaryOperator::create(Instruction::And, Src, MA),
+                BinaryOperator::create(Instruction::And, 
+                                       new ShiftInst(Instruction::Shr, Src, SA),
+                                       MA), "ctpop");
+      }
+      break;
+    default:
+      abort();
+    }
+        
+    CI->replaceAllUsesWith(Src);
+    break;
+  }
+  case Intrinsic::ctlz: {
+    Value *Src = CI->getOperand(1);
+    Value* SA;
+    switch (CI->getOperand(0)->getType()->getTypeID())
+    {
+    case Type::LongTyID:
+    case Type::ULongTyID:
+      SA = ConstantUInt::get(Type::UByteTy, 32);
+      Src = BinaryOperator::create(Instruction::Or, Src, new ShiftInst(Instruction::Shr, Src, SA));
+    case Type::IntTyID:
+    case Type::UIntTyID:
+      SA = ConstantUInt::get(Type::UByteTy, 16);
+      Src = BinaryOperator::create(Instruction::Or, Src, new ShiftInst(Instruction::Shr, Src, SA));
+    case Type::ShortTyID:
+    case Type::UShortTyID:
+      SA = ConstantUInt::get(Type::UByteTy, 8);
+      Src = BinaryOperator::create(Instruction::Or, Src, new ShiftInst(Instruction::Shr, Src, SA));
+    default:
+      SA = ConstantUInt::get(Type::UByteTy, 1);
+      Src = BinaryOperator::create(Instruction::Or, Src, new ShiftInst(Instruction::Shr, Src, SA));
+      SA = ConstantUInt::get(Type::UByteTy, 2);
+      Src = BinaryOperator::create(Instruction::Or, Src, new ShiftInst(Instruction::Shr, Src, SA));
+      SA = ConstantUInt::get(Type::UByteTy, 4);
+      Src = BinaryOperator::create(Instruction::Or, Src, new ShiftInst(Instruction::Shr, Src, SA));
+    };
+    Src = BinaryOperator::createNot(Src);
+
+    Src = new CallInst(new Function(CI->getCalledFunction()->getFunctionType(),
+                                    CI->getCalledFunction()->getLinkage(),
+                                    "llvm.ctpop"), Src);
+    CI->replaceAllUsesWith(Src);
+    break;
+  }
+  case Intrinsic::cttz: {
+    Value *Src = CI->getOperand(1);
+    Src = BinaryOperator::create(Instruction::And, BinaryOperator::createNot(Src),
+            BinaryOperator::create(Instruction::Sub, Src, 
+                            ConstantUInt::get(CI->getOperand(0)->getType(), 1)));
+    Src = new CallInst(new Function(CI->getCalledFunction()->getFunctionType(),
+                                    CI->getCalledFunction()->getLinkage(),
+                                    "llvm.ctpop"), Src);
+    CI->replaceAllUsesWith(Src);
+    break;
+  }
 
   case Intrinsic::returnaddress:
   case Intrinsic::frameaddress:
diff --git a/llvm/lib/CodeGen/SelectionDAG/LegalizeDAG.cpp b/llvm/lib/CodeGen/SelectionDAG/LegalizeDAG.cpp
index 52570824c3a..adb88bf9b18 100644
--- a/llvm/lib/CodeGen/SelectionDAG/LegalizeDAG.cpp
+++ b/llvm/lib/CodeGen/SelectionDAG/LegalizeDAG.cpp
@@ -987,6 +987,51 @@ SDOperand SelectionDAGLegalize::LegalizeOp(SDOperand Op) {
     }
     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 f9b347d4c93..f4d7adcc4ed 100644
--- a/llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
+++ b/llvm/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
@@ -1328,10 +1328,13 @@ SDOperand SelectionDAG::getNode(unsigned Opcode, MVT::ValueType VT,
   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 20483d48146..26be6515816 100644
--- a/llvm/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp
+++ b/llvm/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp
@@ -707,6 +707,21 @@ void SelectionDAGLowering::visitCall(CallInst &I) {
         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;