diff --git a/llvm/lib/CodeGen/DeadMachineInstructionElim.cpp b/llvm/lib/CodeGen/DeadMachineInstructionElim.cpp
--- a/llvm/lib/CodeGen/DeadMachineInstructionElim.cpp
+++ b/llvm/lib/CodeGen/DeadMachineInstructionElim.cpp
@@ -10,6 +10,7 @@
 //
 //===----------------------------------------------------------------------===//
 
+#include "llvm/ADT/PostOrderIterator.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/CodeGen/MachineFunctionPass.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
@@ -48,6 +49,8 @@
 
   private:
     bool isDead(const MachineInstr *MI) const;
+
+    bool eliminateDeadMI(MachineFunction &MF);
   };
 }
 char DeadMachineInstructionElim::ID = 0;
@@ -107,7 +110,13 @@
 bool DeadMachineInstructionElim::runOnMachineFunction(MachineFunction &MF) {
   if (skipFunction(MF.getFunction()))
     return false;
+  bool AnyChanges = eliminateDeadMI(MF);
+  while (AnyChanges && eliminateDeadMI(MF))
+    ;
+  return AnyChanges;
+}
 
+bool DeadMachineInstructionElim::eliminateDeadMI(MachineFunction &MF) {
   bool AnyChanges = false;
   MRI = &MF.getRegInfo();
   TRI = MF.getSubtarget().getRegisterInfo();
@@ -116,22 +125,24 @@
   // Loop over all instructions in all blocks, from bottom to top, so that it's
   // more likely that chains of dependent but ultimately dead instructions will
   // be cleaned up.
-  for (MachineBasicBlock &MBB : make_range(MF.rbegin(), MF.rend())) {
+  for (MachineBasicBlock *MBB : post_order(&MF)) {
     // Start out assuming that reserved registers are live out of this block.
     LivePhysRegs = MRI->getReservedRegs();
 
     // Add live-ins from successors to LivePhysRegs. Normally, physregs are not
     // live across blocks, but some targets (x86) can have flags live out of a
     // block.
-    for (MachineBasicBlock::succ_iterator S = MBB.succ_begin(),
-           E = MBB.succ_end(); S != E; S++)
+    for (MachineBasicBlock::succ_iterator S = MBB->succ_begin(),
+                                          E = MBB->succ_end();
+         S != E; S++)
       for (const auto &LI : (*S)->liveins())
         LivePhysRegs.set(LI.PhysReg);
 
     // Now scan the instructions and delete dead ones, tracking physreg
     // liveness as we go.
-    for (MachineBasicBlock::reverse_iterator MII = MBB.rbegin(),
-         MIE = MBB.rend(); MII != MIE; ) {
+    for (MachineBasicBlock::reverse_iterator MII = MBB->rbegin(),
+                                             MIE = MBB->rend();
+         MII != MIE;) {
       MachineInstr *MI = &*MII++;
 
       // If the instruction is dead, delete it!
diff --git a/llvm/test/CodeGen/AArch64/elim-dead-mi.mir b/llvm/test/CodeGen/AArch64/elim-dead-mi.mir
new file mode 100644
--- /dev/null
+++ b/llvm/test/CodeGen/AArch64/elim-dead-mi.mir
@@ -0,0 +1,61 @@
+# RUN: llc -mtriple=aarch64-arm-none-eabi -o - %s \
+# RUN: -run-pass dead-mi-elimination | FileCheck %s
+--- |
+  @c = internal unnamed_addr global [3 x i8] zeroinitializer, align 4
+  @d = common dso_local local_unnamed_addr global i32 0, align 4
+
+  define dso_local i32 @main() local_unnamed_addr {
+  %scevgep = getelementptr i8, i8* getelementptr inbounds ([3 x i8], [3 x i8]* @c, i64 0, i64 1), i64 0
+  ret i32 0
+  }
+...
+---
+name:            main
+tracksRegLiveness: true
+registers:
+  - { id: 0, class: gpr64, preferred-register: '' }
+  - { id: 1, class: gpr64common, preferred-register: '' }
+  - { id: 2, class: gpr64, preferred-register: '' }
+  - { id: 3, class: gpr64common, preferred-register: '' }
+  - { id: 4, class: gpr32, preferred-register: '' }
+  - { id: 5, class: gpr32all, preferred-register: '' }
+  - { id: 6, class: gpr64, preferred-register: '' }
+body:             |
+  bb.0:
+    successors: %bb.4(0x30000000), %bb.5(0x50000000)
+
+    %0:gpr64 = MOVaddr target-flags(aarch64-page) @c, target-flags(aarch64-pageoff, aarch64-nc) @c
+    CBZX killed %0, %bb.4
+    B %bb.5
+
+  bb.1:
+    successors: %bb.3(0x04000000), %bb.2(0x7c000000)
+
+    %1:gpr64common = MOVaddr target-flags(aarch64-page) @c, target-flags(aarch64-pageoff, aarch64-nc) @c
+    %2:gpr64 = SUBSXri %1, 2, 0, implicit-def $nzcv
+    Bcc 0, %bb.3, implicit $nzcv
+    B %bb.2
+
+  bb.2:
+    successors: %bb.1(0x80000000)
+    %3:gpr64common = ADDXrr %6, %2
+    %4:gpr32 = LDRBBui killed %3, 1 :: (load 1 from %ir.scevgep)
+    %5:gpr32all = COPY %4
+    B %bb.1
+
+  bb.3:
+    ADJCALLSTACKDOWN 0, 0, implicit-def dead $sp, implicit $sp
+    $x0 = MOVaddr target-flags(aarch64-page) @c, target-flags(aarch64-pageoff, aarch64-nc) @c
+    ADJCALLSTACKUP 0, 0, implicit-def dead $sp, implicit $sp
+    RET_ReallyLR implicit $w0
+
+  bb.4:
+    successors: %bb.5(0x80000000)
+
+  bb.5:
+    successors: %bb.1(0x80000000)
+    ; CHECK: bb.5
+    ; CHECK-NOT: %6:gpr64 = MOVaddr target-flags(aarch64-page) @c, target-flags(aarch64-pageoff, aarch64-nc) @c
+    %6:gpr64 = MOVaddr target-flags(aarch64-page) @c, target-flags(aarch64-pageoff, aarch64-nc) @c
+    B %bb.1
+...