Index: include/llvm/CodeGen/GlobalISel/LegalizerHelper.h
===================================================================
--- include/llvm/CodeGen/GlobalISel/LegalizerHelper.h
+++ include/llvm/CodeGen/GlobalISel/LegalizerHelper.h
@@ -49,6 +49,7 @@
   };
 
   LegalizerHelper(MachineFunction &MF);
+  LegalizerHelper(MachineFunction &MF, const LegalizerInfo &LI);
 
   /// Replace \p MI by a sequence of legal instructions that can implement the
   /// same operation. Note that this means \p MI may be deleted, so any iterator
@@ -112,6 +113,8 @@
   void extractParts(unsigned Reg, LLT Ty, int NumParts,
                     SmallVectorImpl<unsigned> &Ops);
 
+  LegalizeResult lowerBitCount(MachineInstr &MI, unsigned TypeIdx, LLT Ty);
+
   MachineRegisterInfo &MRI;
   const LegalizerInfo &LI;
 };
Index: include/llvm/CodeGen/GlobalISel/MachineIRBuilder.h
===================================================================
--- include/llvm/CodeGen/GlobalISel/MachineIRBuilder.h
+++ include/llvm/CodeGen/GlobalISel/MachineIRBuilder.h
@@ -664,6 +664,11 @@
   /// \return a MachineInstrBuilder for the newly created instruction.
   MachineInstrBuilder buildICmp(CmpInst::Predicate Pred,
                                 unsigned Res, unsigned Op0, unsigned Op1);
+  template <typename DstTy, typename... UseArgsTy>
+  MachineInstrBuilder buildICmp(CmpInst::Predicate Pred, DstTy &&Dst,
+                                UseArgsTy &&... UseArgs) {
+    return buildICmp(Pred, getDestFromArg(Dst), getRegFromArg(UseArgs)...);
+  }
 
   /// Build and insert a \p Res = G_FCMP \p Pred\p Op0, \p Op1
   ///
@@ -692,6 +697,10 @@
   /// \return a MachineInstrBuilder for the newly created instruction.
   MachineInstrBuilder buildSelect(unsigned Res, unsigned Tst,
                                   unsigned Op0, unsigned Op1);
+  template <typename DstTy, typename... UseArgsTy>
+  MachineInstrBuilder buildSelect(DstTy &&Dst, UseArgsTy &&... UseArgs) {
+    return buildSelect(getDestFromArg(Dst), getRegFromArg(UseArgs)...);
+  }
 
   /// Build and insert \p Res = G_INSERT_VECTOR_ELT \p Val,
   /// \p Elt, \p Idx
Index: include/llvm/Target/GlobalISel/SelectionDAGCompat.td
===================================================================
--- include/llvm/Target/GlobalISel/SelectionDAGCompat.td
+++ include/llvm/Target/GlobalISel/SelectionDAGCompat.td
@@ -83,6 +83,11 @@
 def : GINodeEquiv<G_INTRINSIC_W_SIDE_EFFECTS, intrinsic_w_chain>;
 def : GINodeEquiv<G_BR, br>;
 def : GINodeEquiv<G_BSWAP, bswap>;
+def : GINodeEquiv<G_CTLZ, ctlz>;
+def : GINodeEquiv<G_CTTZ, cttz>;
+def : GINodeEquiv<G_CTLZ_ZERO_UNDEF, ctlz_zero_undef>;
+def : GINodeEquiv<G_CTTZ_ZERO_UNDEF, cttz_zero_undef>;
+def : GINodeEquiv<G_CTPOP, ctpop>;
 
 // Broadly speaking G_LOAD is equivalent to ISD::LOAD but there are some
 // complications that tablegen must take care of. For example, Predicates such
Index: lib/CodeGen/GlobalISel/LegalizerHelper.cpp
===================================================================
--- lib/CodeGen/GlobalISel/LegalizerHelper.cpp
+++ lib/CodeGen/GlobalISel/LegalizerHelper.cpp
@@ -17,6 +17,7 @@
 #include "llvm/CodeGen/GlobalISel/CallLowering.h"
 #include "llvm/CodeGen/GlobalISel/LegalizerInfo.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
+#include "llvm/CodeGen/TargetInstrInfo.h"
 #include "llvm/CodeGen/TargetLowering.h"
 #include "llvm/CodeGen/TargetSubtargetInfo.h"
 #include "llvm/Support/Debug.h"
@@ -33,6 +34,10 @@
   MIRBuilder.setMF(MF);
 }
 
+LegalizerHelper::LegalizerHelper(MachineFunction &MF, const LegalizerInfo &LI)
+    : MRI(MF.getRegInfo()), LI(LI) {
+  MIRBuilder.setMF(MF);
+}
 LegalizerHelper::LegalizeResult
 LegalizerHelper::legalizeInstrStep(MachineInstr &MI) {
   LLVM_DEBUG(dbgs() << "Legalizing: "; MI.print(dbgs()));
@@ -984,6 +989,12 @@
 
     return UnableToLegalize;
   }
+  case TargetOpcode::G_CTLZ_ZERO_UNDEF:
+  case TargetOpcode::G_CTTZ_ZERO_UNDEF:
+  case TargetOpcode::G_CTLZ:
+  case TargetOpcode::G_CTTZ:
+  case TargetOpcode::G_CTPOP:
+    return lowerBitCount(MI, TypeIdx, Ty);
   }
 }
 
@@ -1024,3 +1035,111 @@
   }
   }
 }
+
+LegalizerHelper::LegalizeResult
+LegalizerHelper::lowerBitCount(MachineInstr &MI, unsigned TypeIdx, LLT Ty) {
+  unsigned Opc = MI.getOpcode();
+  auto &TII = *MI.getMF()->getSubtarget().getInstrInfo();
+  auto isLegalOrCustom = [this](const LegalityQuery &Q) {
+    auto QAction = LI.getAction(Q).Action;
+    return QAction == Legal || QAction == Custom;
+  };
+  switch (Opc) {
+  default:
+    return UnableToLegalize;
+  case TargetOpcode::G_CTLZ_ZERO_UNDEF: {
+    // This trivially expands to CTLZ.
+    MI.setDesc(TII.get(TargetOpcode::G_CTLZ));
+    MIRBuilder.recordInsertion(&MI);
+    return Legalized;
+  }
+  case TargetOpcode::G_CTLZ: {
+    unsigned SrcReg = MI.getOperand(1).getReg();
+    unsigned Len = Ty.getSizeInBits();
+    if (isLegalOrCustom({TargetOpcode::G_CTLZ_ZERO_UNDEF, {Ty}})) {
+      // If CTLZ_ZERO_UNDEF is legal or custom, emit that and a select with
+      // zero.
+      auto MIBCtlzZU =
+          MIRBuilder.buildInstr(TargetOpcode::G_CTLZ_ZERO_UNDEF, Ty, SrcReg);
+      auto MIBZero = MIRBuilder.buildConstant(Ty, 0);
+      auto MIBLen = MIRBuilder.buildConstant(Ty, Len);
+      auto MIBICmp = MIRBuilder.buildICmp(CmpInst::ICMP_EQ, LLT::scalar(1),
+                                          SrcReg, MIBZero);
+      MIRBuilder.buildSelect(MI.getOperand(0).getReg(), MIBICmp, MIBLen,
+                             MIBCtlzZU);
+      MI.eraseFromParent();
+      return Legalized;
+    }
+    // for now, we do this:
+    // x = x | (x >> 1);
+    // x = x | (x >> 2);
+    // ...
+    // x = x | (x >>16);
+    // x = x | (x >>32); // for 64-bit input
+    // return popcount(~x);
+    //
+    // Ref: "Hacker's Delight" by Henry Warren
+    unsigned Op = SrcReg;
+    for (unsigned i = 0; (1U << i) <= (Len / 2); ++i) {
+      auto MIBTmp3 = MIRBuilder.buildConstant(Ty, 1ULL << i);
+      auto MIBOp = MIRBuilder.buildInstr(
+          TargetOpcode::G_OR, Ty, Op,
+          MIRBuilder.buildInstr(TargetOpcode::G_LSHR, Ty, Op, MIBTmp3));
+      Op = MIBOp->getOperand(0).getReg();
+    }
+    auto MIBNot = MIRBuilder.buildInstr(TargetOpcode::G_XOR, Ty, Op,
+                                        MIRBuilder.buildConstant(Ty, -1));
+    MIRBuilder.buildInstr(TargetOpcode::G_CTPOP, MI.getOperand(0).getReg(),
+                          MIBNot);
+    MI.eraseFromParent();
+    return Legalized;
+  }
+  case TargetOpcode::G_CTTZ_ZERO_UNDEF: {
+    // This trivially expands to CTTZ.
+    MI.setDesc(TII.get(TargetOpcode::G_CTTZ));
+    MIRBuilder.recordInsertion(&MI);
+    return Legalized;
+  }
+  case TargetOpcode::G_CTTZ: {
+    unsigned SrcReg = MI.getOperand(1).getReg();
+    unsigned Len = Ty.getSizeInBits();
+    if (isLegalOrCustom({TargetOpcode::G_CTTZ_ZERO_UNDEF, {Ty}})) {
+      // If CTTZ_ZERO_UNDEF is legal or custom, emit that and a select with
+      // zero.
+      auto MIBCttzZU =
+          MIRBuilder.buildInstr(TargetOpcode::G_CTTZ_ZERO_UNDEF, Ty, SrcReg);
+      auto MIBZero = MIRBuilder.buildConstant(Ty, 0);
+      auto MIBLen = MIRBuilder.buildConstant(Ty, Len);
+      auto MIBICmp = MIRBuilder.buildICmp(CmpInst::ICMP_EQ, LLT::scalar(1),
+                                          SrcReg, MIBZero);
+      MIRBuilder.buildSelect(MI.getOperand(0).getReg(), MIBICmp, MIBLen,
+                             MIBCttzZU);
+      MI.eraseFromParent();
+      return Legalized;
+    }
+    // for now, we use: { return popcount(~x & (x - 1)); }
+    // unless the target has ctlz but not ctpop, in which case we use:
+    // { return 32 - nlz(~x & (x-1)); }
+    // Ref: "Hacker's Delight" by Henry Warren
+    auto MIBNot = MIRBuilder.buildInstr(TargetOpcode::G_XOR, Ty, SrcReg,
+                                        MIRBuilder.buildConstant(Ty, -1));
+    auto MIBTmp = MIRBuilder.buildInstr(
+        TargetOpcode::G_AND, Ty, MIBNot,
+        MIRBuilder.buildInstr(TargetOpcode::G_SUB, Ty, SrcReg,
+                              MIRBuilder.buildConstant(Ty, 1)));
+    if (!isLegalOrCustom({TargetOpcode::G_CTPOP, {Ty}}) &&
+        isLegalOrCustom({TargetOpcode::G_CTLZ, {Ty}})) {
+      MIRBuilder.buildInstr(
+          TargetOpcode::G_SUB, MI.getOperand(0).getReg(),
+          MIRBuilder.buildConstant(Ty, Len),
+          MIRBuilder.buildInstr(TargetOpcode::G_CTLZ, Ty, MIBTmp));
+      MI.eraseFromParent();
+      return Legalized;
+    }
+    MIRBuilder.buildInstr(TargetOpcode::G_CTPOP, MI.getOperand(0).getReg(),
+                          MIBTmp);
+    MI.eraseFromParent();
+    return Legalized;
+  }
+  }
+}