Index: lib/CodeGen/RegAllocFast.cpp
===================================================================
--- lib/CodeGen/RegAllocFast.cpp
+++ lib/CodeGen/RegAllocFast.cpp
@@ -913,8 +913,6 @@
 
     // First scan.
     // Mark physreg uses and early clobbers as used.
-    // Find the end of the virtreg operands
-    unsigned VirtOpEnd = 0;
     bool hasTiedOps = false;
     bool hasEarlyClobbers = false;
     bool hasPartialRedefs = false;
@@ -930,7 +928,6 @@
       unsigned Reg = MO.getReg();
       if (!Reg) continue;
       if (TargetRegisterInfo::isVirtualRegister(Reg)) {
-        VirtOpEnd = i+1;
         if (MO.isUse()) {
           hasTiedOps = hasTiedOps ||
                               MCID.getOperandConstraint(i, MCOI::TIED_TO) != -1;
@@ -974,18 +971,50 @@
 
     // Second scan.
     // Allocate virtreg uses.
-    for (unsigned i = 0; i != VirtOpEnd; ++i) {
-      MachineOperand &MO = MI->getOperand(i);
-      if (!MO.isReg()) continue;
+    // HACK(strager): Allocate larger registers first.
+    SmallVector<unsigned, 8> VirtOps;
+    for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) {
+      const MachineOperand &MO = MI->getOperand(i);
+      if (!MO.isReg())
+        continue;
       unsigned Reg = MO.getReg();
-      if (!TargetRegisterInfo::isVirtualRegister(Reg)) continue;
-      if (MO.isUse()) {
-        LiveRegMap::iterator LRI = reloadVirtReg(*MI, i, Reg, CopyDst);
-        unsigned PhysReg = LRI->PhysReg;
-        CopySrc = (CopySrc == Reg || CopySrc == PhysReg) ? PhysReg : 0;
-        if (setPhysReg(MI, i, PhysReg))
-          killVirtReg(LRI);
-      }
+      if (!TargetRegisterInfo::isVirtualRegister(Reg))
+        continue;
+      if (!MO.isUse())
+        continue;
+      VirtOps.emplace_back(i);
+    }
+    std::sort(VirtOps.begin(), VirtOps.end(),
+              [this, &MI](unsigned i, unsigned j) {
+                auto OpSize = [this](const MachineOperand &MO) -> unsigned {
+                  unsigned Reg = MO.getReg();
+                  if (auto RC = MRI->getRegClassOrRegBank(Reg)) {
+                    if (RC.is<const TargetRegisterClass *>()) {
+#if LLVM_VERSION_MAJOR >= 5
+                      // LLVM 5.0.0.
+                      return TRI->getRegSizeInBits(
+                          *RC.get<const TargetRegisterClass *>());
+#else
+                      // LLVM 4.0.0.
+                      return RC.get<const TargetRegisterClass *>()->getSize();
+#endif
+                    } else {
+                      return 0;
+                    }
+                  } else {
+                    return 0;
+                  }
+                };
+                return OpSize(MI->getOperand(i)) >= OpSize(MI->getOperand(j));
+              });
+    for (unsigned i : VirtOps) {
+      const MachineOperand &MO = MI->getOperand(i);
+      unsigned Reg = MO.getReg();
+      LiveRegMap::iterator LRI = reloadVirtReg(*MI, i, Reg, CopyDst);
+      unsigned PhysReg = LRI->PhysReg;
+      CopySrc = (CopySrc == Reg || CopySrc == PhysReg) ? PhysReg : 0;
+      if (setPhysReg(MI, i, PhysReg))
+        killVirtReg(LRI);
     }
 
     // Track registers defined by instruction - early clobbers and tied uses at
Index: test/CodeGen/ARM/cmpxchg-O0.ll
===================================================================
--- test/CodeGen/ARM/cmpxchg-O0.ll
+++ test/CodeGen/ARM/cmpxchg-O0.ll
@@ -80,6 +80,54 @@
   ret { i64, i1 } %res
 }
 
+; If r9 and fp are reserved, cmpxchg can only use r0/r1, r2/r3, r4/r5, or r6/r7
+; for the 64-bit inputs to ldrexd and strexd. Ensure fast-regalloc can find
+; enough registers without spilling.
+define i64 @test_cmpxchg_64_register_pressure(i64* %addr, i64 %desired, i64 %new) nounwind "no-frame-pointer-elim"="true" "target-features"="+reserve-r9" {
+; CHECK-LABEL: test_cmpxchg_64_register_pressure:
+  %addr.addr = alloca i64*, align 4
+  %desired.addr = alloca i64, align 8
+  %new.addr = alloca i64, align 8
+  store i64* %addr, i64** %addr.addr, align 4
+  store i64 %desired, i64* %desired.addr, align 8
+  store i64 %new, i64* %new.addr, align 8
+  br label %while.cond
+
+while.cond:
+  %addr.tmp = load i64*, i64** %addr.addr, align 4
+  %desired.tmp = load i64, i64* %desired.addr, align 8
+  %new.tmp = load i64, i64* %new.addr, align 8
+
+; CHECK-DAG: mov [[NEWLO:r[0-9]+]], r3
+; CHECK-NEXT:mov [[NEWHI:r[0-9]+]], {{r[0-9]+}}
+; CHECK-DAG: ldrd [[DESIREDLO:r[0-9]+]], [[DESIREDHI:r[0-9]+]], [sp, #{{[0-9]+}}] @ 8-byte Reload
+; CHECK-DAG: dmb ish
+; CHECK: [[INNERRETRY:.LBB[0-9]+_[0-9]+]]:
+; CHECK-NOT: {{ldr[^e]|str}}
+; CHECK:     ldrexd [[OLDLO:r[0-9]+]], [[OLDHI:r[0-9]+]], {{\[}}[[ADDR:r[0-9]+]]{{\]}}
+; CHECK-NOT: {{ldr|str}}
+; CHECK:     cmp [[OLDLO]], [[DESIREDLO]]
+; CHECK-NOT: {{ldr|str}}
+; CHECK:     cmpeq [[OLDHI]], [[DESIREDHI]]
+; CHECK-NOT: {{ldr|str}}
+; CHECK:     bne [[INNERDONE:.LBB[0-9]+_[0-9]+]]
+; CHECK-NOT: {{ldr|str[^e]}}
+; CHECK:     strexd [[STATUS:r[0-9]+]], [[NEWLO]], [[NEWHI]], {{\[}}[[ADDR]]{{\]}}
+; CHECK-NOT: {{ldr|str}}
+; CHECK:     cmp{{(\.w)?}} [[STATUS]], #0
+; CHECK-NOT: {{ldr|str}}
+; CHECK:     bne [[INNERRETRY]]
+; CHECK: [[INNERDONE]]:
+; CHECK:     dmb ish
+  %tmp = cmpxchg i64* %addr.tmp, i64 %desired.tmp, i64 %new.tmp seq_cst seq_cst
+
+  %status = extractvalue { i64, i1 } %tmp, 1
+  br i1 %status, label %done, label %while.cond
+
+done:
+  ret i64 0
+}
+
 define { i64, i1 } @test_nontrivial_args(i64* %addr, i64 %desired, i64 %new) {
 ; CHECK-LABEL: test_nontrivial_args:
 ; CHECK:     dmb ish