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

11 files changed, 308 insertions, 9 deletions

diff --git a/lib/CodeGen/IntrinsicLowering.cpp b/lib/CodeGen/IntrinsicLowering.cpp
index 36f413a14f..0bad510324 100644
--- a/lib/CodeGen/IntrinsicLowering.cpp
+++ b/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/lib/CodeGen/SelectionDAG/LegalizeDAG.cpp b/lib/CodeGen/SelectionDAG/LegalizeDAG.cpp
index 52570824c3..adb88bf9b1 100644
--- a/lib/CodeGen/SelectionDAG/LegalizeDAG.cpp
+++ b/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/lib/CodeGen/SelectionDAG/SelectionDAG.cpp b/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
index f9b347d4c9..f4d7adcc4e 100644
--- a/lib/CodeGen/SelectionDAG/SelectionDAG.cpp
+++ b/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/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp b/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp
index 20483d4814..26be651581 100644
--- a/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp
+++ b/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;
diff --git a/lib/Target/Alpha/AlphaISelPattern.cpp b/lib/Target/Alpha/AlphaISelPattern.cpp
index 574f8644ee..53d8a9e561 100644
--- a/lib/Target/Alpha/AlphaISelPattern.cpp
+++ b/lib/Target/Alpha/AlphaISelPattern.cpp
@@ -76,6 +76,10 @@ namespace {
       setOperationAction(ISD::SREM     , MVT::f32  , Expand);
       setOperationAction(ISD::SREM     , MVT::f64  , Expand);
 
+      //      setOperationAction(ISD::CTPOP    , MVT::i64  , Expand);
+      //      setOperationAction(ISD::CTTZ     , MVT::i64  , Expand);
+      //      setOperationAction(ISD::CTTZ     , MVT::i64  , Expand);
+
       //If this didn't legalize into a div....
       //      setOperationAction(ISD::SREM     , MVT::i64, Expand);
       //      setOperationAction(ISD::UREM     , MVT::i64, Expand);
@@ -1215,6 +1219,15 @@ unsigned ISel::SelectExpr(SDOperand N) {
     Node->dump();
     assert(0 && "Node not handled!\n");
 
+  case ISD::CTPOP:
+  case ISD::CTTZ:
+  case ISD::CTLZ:
+    Opc = opcode == ISD::CTPOP ? Alpha::CTPOP :
+    (opcode == ISD::CTTZ ? Alpha::CTTZ : Alpha::CTLZ);
+    Tmp1 = SelectExpr(N.getOperand(0));
+    BuildMI(BB, Opc, 1, Result).addReg(Tmp1);
+    return Result;
+
   case ISD::MULHU:
     Tmp1 = SelectExpr(N.getOperand(0));
     Tmp2 = SelectExpr(N.getOperand(1));
diff --git a/lib/Target/Alpha/AlphaInstrInfo.td b/lib/Target/Alpha/AlphaInstrInfo.td
index e341e858cb..c42ad1ed20 100644
--- a/lib/Target/Alpha/AlphaInstrInfo.td
+++ b/lib/Target/Alpha/AlphaInstrInfo.td
@@ -186,12 +186,9 @@ def BIC      : OForm< 0x11, 0x08, (ops GPRC:$RC, GPRC:$RA, GPRC:$RB), "bic $RA,$
 def BICi     : OFormL<0x11, 0x08, (ops GPRC:$RC, GPRC:$RA, u8imm:$L), "bic $RA,$L,$RC">; //Bit clear
 def BIS      : OForm< 0x11, 0x20, (ops GPRC:$RC, GPRC:$RA, GPRC:$RB), "bis $RA,$RB,$RC">; //Logical sum
 def BISi     : OFormL<0x11, 0x20, (ops GPRC:$RC, GPRC:$RA, u8imm:$L), "bis $RA,$L,$RC">; //Logical sum
-def CTLZ     : OForm< 0x1C, 0x32, (ops GPRC:$RC, GPRC:$RA, GPRC:$RB), "CTLZ $RA,$RB,$RC">; //Count leading zero
-def CTLZi    : OFormL<0x1C, 0x32, (ops GPRC:$RC, GPRC:$RA, u8imm:$L), "CTLZ $RA,$L,$RC">; //Count leading zero
-def CTPOP    : OForm< 0x1C, 0x30, (ops GPRC:$RC, GPRC:$RA, GPRC:$RB), "CTPOP $RA,$RB,$RC">; //Count population
-def CTPOPi   : OFormL<0x1C, 0x30, (ops GPRC:$RC, GPRC:$RA, u8imm:$L), "CTPOP $RA,$L,$RC">; //Count population
-def CTTZ     : OForm< 0x1C, 0x33, (ops GPRC:$RC, GPRC:$RA, GPRC:$RB), "CTTZ $RA,$RB,$RC">; //Count trailing zero
-def CTTZi    : OFormL<0x1C, 0x33, (ops GPRC:$RC, GPRC:$RA, u8imm:$L), "CTTZ $RA,$L,$RC">; //Count trailing zero
+def CTLZ     : OForm< 0x1C, 0x32, (ops GPRC:$RC, GPRC:$RB), "CTLZ $RB,$RC">; //Count leading zero
+def CTPOP    : OForm< 0x1C, 0x30, (ops GPRC:$RC, GPRC:$RB), "CTPOP $RB,$RC">; //Count population
+def CTTZ     : OForm< 0x1C, 0x33, (ops GPRC:$RC, GPRC:$RB), "CTTZ $RB,$RC">; //Count trailing zero
 def EQV      : OForm< 0x11, 0x48, (ops GPRC:$RC, GPRC:$RA, GPRC:$RB), "eqv $RA,$RB,$RC">; //Logical equivalence
 def EQVi     : OFormL<0x11, 0x48, (ops GPRC:$RC, GPRC:$RA, u8imm:$L), "eqv $RA,$L,$RC">; //Logical equivalence
 def EXTBL    : OForm< 0x12, 0x06, (ops GPRC:$RC, GPRC:$RA, GPRC:$RB), "EXTBL $RA,$RB,$RC">; //Extract byte low
diff --git a/lib/Target/PowerPC/PPC64ISelPattern.cpp b/lib/Target/PowerPC/PPC64ISelPattern.cpp
index 8614a24743..25fbb98acd 100644
--- a/lib/Target/PowerPC/PPC64ISelPattern.cpp
+++ b/lib/Target/PowerPC/PPC64ISelPattern.cpp
@@ -68,6 +68,11 @@ namespace {
       setOperationAction(ISD::SREM, MVT::i64, Expand);
       setOperationAction(ISD::UREM, MVT::i64, Expand);
 
+      // PowerPC has these, but they are not implemented
+      setOperationAction(ISD::CTPOP, MVT::i64, Expand);
+      setOperationAction(ISD::CTTZ , MVT::i64, Expand);
+      setOperationAction(ISD::CTTZ , MVT::i64, Expand);
+
       setShiftAmountFlavor(Extend);   // shl X, 32 == 0
       addLegalFPImmediate(+0.0); // Necessary for FSEL
       addLegalFPImmediate(-0.0); //
diff --git a/lib/Target/PowerPC/PPCISelPattern.cpp b/lib/Target/PowerPC/PPCISelPattern.cpp
index a5732f0576..6ed33381f3 100644
--- a/lib/Target/PowerPC/PPCISelPattern.cpp
+++ b/lib/Target/PowerPC/PPCISelPattern.cpp
@@ -69,6 +69,11 @@ namespace {
       setOperationAction(ISD::FCOS , MVT::f32, Expand);
       setOperationAction(ISD::FSQRT, MVT::f32, Expand);
 
+      //PowerPC has these, but they are not implemented
+      setOperationAction(ISD::CTPOP, MVT::i32  , Expand);
+      setOperationAction(ISD::CTTZ , MVT::i32  , Expand);
+      setOperationAction(ISD::CTTZ , MVT::i32  , Expand);
+
       setSetCCResultContents(ZeroOrOneSetCCResult);
       addLegalFPImmediate(+0.0); // Necessary for FSEL
       addLegalFPImmediate(-0.0); //
diff --git a/lib/Target/X86/X86ISelPattern.cpp b/lib/Target/X86/X86ISelPattern.cpp
index 8b3f31cecf..0737842749 100644
--- a/lib/Target/X86/X86ISelPattern.cpp
+++ b/lib/Target/X86/X86ISelPattern.cpp
@@ -64,6 +64,9 @@ namespace {
       setOperationAction(ISD::FP_ROUND_INREG   , MVT::f32  , Expand);
       setOperationAction(ISD::SEXTLOAD         , MVT::i1   , Expand);
       setOperationAction(ISD::SREM             , MVT::f64  , Expand);
+      setOperationAction(ISD::CTPOP            , MVT::i32  , Expand);
+      setOperationAction(ISD::CTTZ             , MVT::i32  , Expand);
+      setOperationAction(ISD::CTTZ             , MVT::i32  , Expand);
 
       if (!UnsafeFPMath) {
         setOperationAction(ISD::FSIN           , MVT::f64  , Expand);
diff --git a/lib/VMCore/Function.cpp b/lib/VMCore/Function.cpp
index 6740c6bbb0..f61a4d2326 100644
--- a/lib/VMCore/Function.cpp
+++ b/lib/VMCore/Function.cpp
@@ -206,6 +206,11 @@ unsigned Function::getIntrinsicID() const {
   assert(getName().size() != 5 && "'llvm.' is an invalid intrinsic name!");
 
   switch (getName()[5]) {
+  case 'c':
+    if (getName() == "llvm.ctpop") return Intrinsic::ctpop;
+    if (getName() == "llvm.cttz") return Intrinsic::cttz;
+    if (getName() == "llvm.ctlz") return Intrinsic::ctlz;
+    break;
   case 'd':
     if (getName() == "llvm.dbg.stoppoint")   return Intrinsic::dbg_stoppoint;
     if (getName() == "llvm.dbg.region.start")return Intrinsic::dbg_region_start;
diff --git a/lib/VMCore/Verifier.cpp b/lib/VMCore/Verifier.cpp
index d7b8f50962..ab9e60cc3e 100644
--- a/lib/VMCore/Verifier.cpp
+++ b/lib/VMCore/Verifier.cpp
@@ -723,6 +723,18 @@ void Verifier::visitIntrinsicFunctionCall(Intrinsic::ID ID, CallInst &CI) {
     NumArgs = 2;
     break;
 
+  case Intrinsic::ctpop:
+  case Intrinsic::ctlz:
+  case Intrinsic::cttz:
+    Assert1(FT->getNumParams() == 1,
+            "Illegal # arguments for intrinsic function!", IF);
+    Assert1(FT->getReturnType() == FT->getParamType(0),
+            "Return type does not match source type", IF);
+    Assert1(FT->getParamType(0)->isIntegral(),
+            "Argument must be of an int type!", IF);
+    NumArgs = 1;
+    break;
+
   case Intrinsic::sqrt:
     Assert1(FT->getNumParams() == 1,
             "Illegal # arguments for intrinsic function!", IF);