diff --git a/compiler/dex/quick/ralloc_util.cc b/compiler/dex/quick/ralloc_util.cc
index d59c986..a0b98dd 100644
--- a/compiler/dex/quick/ralloc_util.cc
+++ b/compiler/dex/quick/ralloc_util.cc
@@ -931,7 +931,12 @@
 static int SortCounts(const void *val1, const void *val2) {
   const Mir2Lir::RefCounts* op1 = reinterpret_cast<const Mir2Lir::RefCounts*>(val1);
   const Mir2Lir::RefCounts* op2 = reinterpret_cast<const Mir2Lir::RefCounts*>(val2);
-  return (op1->count == op2->count) ? 0 : (op1->count < op2->count ? 1 : -1);
+  // Note that we fall back to sorting on reg so we get stable output
+  // on differing qsort implementations (such as on host and target or
+  // between local host and build servers).
+  return (op1->count == op2->count)
+          ? (op1->s_reg - op2->s_reg)
+          : (op1->count < op2->count ? 1 : -1);
 }
 
 void Mir2Lir::DumpCounts(const RefCounts* arr, int size, const char* msg) {