diff --git a/llvm/lib/CodeGen/PHIElimination.cpp b/llvm/lib/CodeGen/PHIElimination.cpp
--- a/llvm/lib/CodeGen/PHIElimination.cpp
+++ b/llvm/lib/CodeGen/PHIElimination.cpp
@@ -107,6 +107,7 @@
     using BBVRegPair = std::pair<unsigned, Register>;
     using VRegPHIUse = DenseMap<BBVRegPair, unsigned>;
 
+    // Count the number of non-undef PHI uses of each register in each BB.
     VRegPHIUse VRegPHIUseCount;
 
     // Defs of PHI sources which are implicit_def.
@@ -426,9 +427,13 @@
   }
 
   // Adjust the VRegPHIUseCount map to account for the removal of this PHI node.
-  for (unsigned i = 1; i != MPhi->getNumOperands(); i += 2)
-    --VRegPHIUseCount[BBVRegPair(MPhi->getOperand(i+1).getMBB()->getNumber(),
-                                 MPhi->getOperand(i).getReg())];
+  for (unsigned i = 1; i != MPhi->getNumOperands(); i += 2) {
+    if (!MPhi->getOperand(i).isUndef()) {
+      --VRegPHIUseCount[BBVRegPair(
+          MPhi->getOperand(i + 1).getMBB()->getNumber(),
+          MPhi->getOperand(i).getReg())];
+    }
+  }
 
   // Now loop over all of the incoming arguments, changing them to copy into the
   // IncomingReg register in the corresponding predecessor basic block.
@@ -630,14 +635,19 @@
 /// used in a PHI node. We map that to the BB the vreg is coming from. This is
 /// used later to determine when the vreg is killed in the BB.
 void PHIElimination::analyzePHINodes(const MachineFunction& MF) {
-  for (const auto &MBB : MF)
+  for (const auto &MBB : MF) {
     for (const auto &BBI : MBB) {
       if (!BBI.isPHI())
         break;
-      for (unsigned i = 1, e = BBI.getNumOperands(); i != e; i += 2)
-        ++VRegPHIUseCount[BBVRegPair(BBI.getOperand(i+1).getMBB()->getNumber(),
-                                     BBI.getOperand(i).getReg())];
+      for (unsigned i = 1, e = BBI.getNumOperands(); i != e; i += 2) {
+        if (!BBI.getOperand(i).isUndef()) {
+          ++VRegPHIUseCount[BBVRegPair(
+              BBI.getOperand(i + 1).getMBB()->getNumber(),
+              BBI.getOperand(i).getReg())];
+        }
+      }
     }
+  }
 }
 
 bool PHIElimination::SplitPHIEdges(MachineFunction &MF,
diff --git a/llvm/test/CodeGen/X86/phielim-undef.mir b/llvm/test/CodeGen/X86/phielim-undef.mir
new file mode 100644
--- /dev/null
+++ b/llvm/test/CodeGen/X86/phielim-undef.mir
@@ -0,0 +1,97 @@
+# NOTE: Assertions have been autogenerated by utils/update_mir_test_checks.py
+# RUN: llc -mtriple=x86_64-- -verify-machineinstrs -o - %s -run-pass=livevars,phi-node-elimination,twoaddressinstruction | FileCheck %s
+
+--- |
+  @b114 = external global i16, align 1
+
+  define void @f245() {
+  entry:
+    unreachable
+  }
+...
+---
+name: f245
+tracksRegLiveness: true
+body: |
+  ; CHECK-LABEL: name: f245
+  ; CHECK: bb.0:
+  ; CHECK-NEXT:   successors: %bb.5(0x40000000), %bb.1(0x40000000)
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT:   [[MOV64rm:%[0-9]+]]:gr64 = MOV64rm $rip, 1, $noreg, target-flags(x86-gotpcrel) @b114, $noreg
+  ; CHECK-NEXT:   [[MOV16rm:%[0-9]+]]:gr16 = MOV16rm killed [[MOV64rm]], 1, $noreg, 0, $noreg :: (load (s16) from @b114, align 1)
+  ; CHECK-NEXT:   TEST8ri undef %2:gr8, 1, implicit-def $eflags
+  ; CHECK-NEXT:   JCC_1 %bb.5, 5, implicit killed $eflags
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT: bb.1:
+  ; CHECK-NEXT:   successors: %bb.2(0x80000000)
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT:   [[COPY:%[0-9]+]]:gr16 = COPY killed [[MOV16rm]]
+  ; CHECK-NEXT:   JMP_1 %bb.2
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT: bb.2:
+  ; CHECK-NEXT:   successors: %bb.4(0x40000000), %bb.3(0x40000000)
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT:   dead %5:gr16 = IMPLICIT_DEF
+  ; CHECK-NEXT:   [[COPY1:%[0-9]+]]:gr16 = COPY killed [[COPY]]
+  ; CHECK-NEXT:   TEST8ri undef %7:gr8, 1, implicit-def $eflags
+  ; CHECK-NEXT:   JCC_1 %bb.4, 5, implicit killed $eflags
+  ; CHECK-NEXT:   JMP_1 %bb.3
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT: bb.3:
+  ; CHECK-NEXT:   successors: %bb.6(0x40000000), %bb.4(0x40000000)
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT:   [[MOV32r0_:%[0-9]+]]:gr32 = MOV32r0 implicit-def dead $eflags
+  ; CHECK-NEXT:   dead %9:gr16 = COPY killed [[MOV32r0_]].sub_16bit
+  ; CHECK-NEXT:   CMP16ri8 killed [[COPY1]], 0, implicit-def $eflags
+  ; CHECK-NEXT:   JCC_1 %bb.6, 5, implicit killed $eflags
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT: bb.4:
+  ; CHECK-NEXT:   successors: %bb.2(0x80000000)
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT:   [[DEF:%[0-9]+]]:gr16 = IMPLICIT_DEF
+  ; CHECK-NEXT:   JMP_1 %bb.2
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT: bb.5:
+  ; CHECK-NEXT:   RETQ
+  ; CHECK-NEXT: {{  $}}
+  ; CHECK-NEXT: bb.6:
+  bb.0:
+    successors: %bb.6(0x40000000), %bb.1(0x40000000)
+
+    %5:gr64 = MOV64rm $rip, 1, $noreg, target-flags(x86-gotpcrel) @b114, $noreg
+    %6:gr16 = MOV16rm killed %5, 1, $noreg, 0, $noreg :: (load (s16) from @b114, align 1)
+    TEST8ri undef %4:gr8, 1, implicit-def $eflags
+    JCC_1 %bb.6, 5, implicit killed $eflags
+
+  bb.1:
+    successors: %bb.2(0x80000000)
+
+    JMP_1 %bb.2
+
+  bb.2:
+    successors: %bb.5(0x40000000), %bb.4(0x40000000)
+
+    %1:gr16 = PHI %6, %bb.1, undef %10:gr16, %bb.5
+    dead %2:gr16 = PHI undef %6, %bb.1, undef %3:gr16, %bb.5
+    TEST8ri undef %7:gr8, 1, implicit-def $eflags
+    JCC_1 %bb.5, 5, implicit killed $eflags
+    JMP_1 %bb.4
+
+  bb.4:
+    successors: %bb.7(0x40000000), %bb.5(0x40000000)
+
+    %8:gr32 = MOV32r0 implicit-def dead $eflags
+    %9:gr16 = COPY killed %8.sub_16bit
+    CMP16ri8 killed %1, 0, implicit-def $eflags
+    JCC_1 %bb.7, 5, implicit killed $eflags
+
+  bb.5:
+    successors: %bb.2(0x80000000)
+
+    JMP_1 %bb.2
+
+  bb.6:
+    RETQ
+
+  bb.7:
+...