diff --git a/llvm/lib/CodeGen/RegAllocFast.cpp b/llvm/lib/CodeGen/RegAllocFast.cpp
--- a/llvm/lib/CodeGen/RegAllocFast.cpp
+++ b/llvm/lib/CodeGen/RegAllocFast.cpp
@@ -1381,29 +1381,34 @@
   }
 
   // Allocate virtreg uses and insert reloads as necessary.
+  // Implicit MOs can get moved/removed by useVirtReg(), so loop multiple
+  // times to ensure no operand is missed.
   bool HasUndefUse = false;
-  for (unsigned I = 0; I < MI.getNumOperands(); ++I) {
-    MachineOperand &MO = MI.getOperand(I);
-    if (!MO.isReg() || !MO.isUse())
-      continue;
-    Register Reg = MO.getReg();
-    if (!Reg.isVirtual() || !shouldAllocateRegister(Reg))
-      continue;
-
-    if (MO.isUndef()) {
-      HasUndefUse = true;
-      continue;
-    }
-
+  bool ChangedOperands = true;
+  while (ChangedOperands) {
+    ChangedOperands = false;
+    for (unsigned I = 0; I < MI.getNumOperands(); ++I) {
+      MachineOperand &MO = MI.getOperand(I);
+      if (!MO.isReg() || !MO.isUse())
+        continue;
+      Register Reg = MO.getReg();
+      if (!Reg.isVirtual() || !shouldAllocateRegister(Reg))
+        continue;
 
-    // Populate MayLiveAcrossBlocks in case the use block is allocated before
-    // the def block (removing the vreg uses).
-    mayLiveIn(Reg);
+      if (MO.isUndef()) {
+        HasUndefUse = true;
+        continue;
+      }
 
+      // Populate MayLiveAcrossBlocks in case the use block is allocated before
+      // the def block (removing the vreg uses).
+      mayLiveIn(Reg);
 
-    assert(!MO.isInternalRead() && "Bundles not supported");
-    assert(MO.readsReg() && "reading use");
-    useVirtReg(MI, I, Reg);
+      assert(!MO.isInternalRead() && "Bundles not supported");
+      assert(MO.readsReg() && "reading use");
+      useVirtReg(MI, I, Reg);
+      ChangedOperands = true;
+    }
   }
 
   // Allocate undef operands. This is a separate step because in a situation
diff --git a/llvm/test/CodeGen/ARM/regalloc-fast-rewrite-implicits.mir b/llvm/test/CodeGen/ARM/regalloc-fast-rewrite-implicits.mir
new file mode 100644
--- /dev/null
+++ b/llvm/test/CodeGen/ARM/regalloc-fast-rewrite-implicits.mir
@@ -0,0 +1,63 @@
+# NOTE: Assertions have been autogenerated by utils/update_mir_test_checks.py
+# RUN: llc -mtriple=armv7-apple-ios -run-pass=regallocfast -o - %s | FileCheck %s
+
+
+# tBX_RET uses an implicit vreg with a sub-register. That implicit use will
+# typically be rewritten as a use of the relevant super-register. Make sure
+# regallocfast is able to process the remaining operands (here, %2) and rewrite
+# them to use physical registers.
+---
+name:            different_vreg
+tracksRegLiveness: true
+body:             |
+  bb.0:
+    liveins: $d2, $d4, $d7
+
+    ; CHECK-LABEL: name: different_vreg
+    ; CHECK: liveins: $d2, $d4, $d7
+    ; CHECK-NEXT: {{  $}}
+    ; CHECK-NEXT: renamable $d5 = COPY killed $d4
+    ; CHECK-NEXT: renamable $d4 = COPY killed $d2
+    ; CHECK-NEXT: undef renamable $d0 = COPY renamable $d5, implicit-def $q0_q1
+    ; CHECK-NEXT: renamable $d1 = COPY renamable $d4
+    ; CHECK-NEXT: renamable $d2 = COPY killed renamable $d5
+    ; CHECK-NEXT: renamable $d3 = COPY killed renamable $d4
+    ; CHECK-NEXT: tBX_RET 14 /* CC::al */, $noreg, implicit killed renamable $d7, implicit killed $q0_q1
+    %0:dpr_vfp2 = COPY $d4
+    %1:dpr_vfp2 = COPY $d2
+    %2:dpr_vfp2 = COPY $d7
+    undef %4.dsub_0:dquad = COPY %0
+    %4.dsub_1:dquad = COPY %1
+    %4.dsub_2:dquad = COPY %0
+    %4.dsub_3:dquad = COPY %1
+    tBX_RET 14, $noreg, implicit %4.dsub_3, implicit %2
+...
+
+
+# tBX_RET uses the same vreg twice, make sure regallocfast is able to allocate a
+# physical register for it and replace both references.
+---
+name:            same_vreg_twice
+tracksRegLiveness: true
+body:             |
+  bb.0:
+    liveins: $d2, $d4
+
+    ; CHECK-LABEL: name: same_vreg_twice
+    ; CHECK: liveins: $d2, $d4
+    ; CHECK-NEXT: {{  $}}
+    ; CHECK-NEXT: renamable $d5 = COPY killed $d4
+    ; CHECK-NEXT: renamable $d4 = COPY killed $d2
+    ; CHECK-NEXT: undef renamable $d0 = COPY renamable $d5, implicit-def $q0_q1
+    ; CHECK-NEXT: renamable $d1 = COPY renamable $d4
+    ; CHECK-NEXT: renamable $d2 = COPY killed renamable $d5
+    ; CHECK-NEXT: renamable $d3 = COPY killed renamable $d4
+    ; CHECK-NEXT: tBX_RET 14 /* CC::al */, $noreg, implicit renamable $d3, implicit killed $q0_q1
+    %0:dpr_vfp2 = COPY $d4
+    %1:dpr_vfp2 = COPY $d2
+    undef %4.dsub_0:dquad = COPY %0
+    %4.dsub_1:dquad = COPY %1
+    %4.dsub_2:dquad = COPY %0
+    %4.dsub_3:dquad = COPY %1
+    tBX_RET 14, $noreg, implicit %4.dsub_1, implicit %4.dsub_3
+...