diff --git a/llvm/include/llvm/Analysis/LoopCacheAnalysis.h b/llvm/include/llvm/Analysis/LoopCacheAnalysis.h
--- a/llvm/include/llvm/Analysis/LoopCacheAnalysis.h
+++ b/llvm/include/llvm/Analysis/LoopCacheAnalysis.h
@@ -243,9 +243,10 @@
 
   /// Sort the LoopCosts vector by decreasing cache cost.
   void sortLoopCosts() {
-    sort(LoopCosts, [](const LoopCacheCostTy &A, const LoopCacheCostTy &B) {
-      return A.second > B.second;
-    });
+    stable_sort(LoopCosts,
+                [](const LoopCacheCostTy &A, const LoopCacheCostTy &B) {
+                  return A.second > B.second;
+                });
   }
 
 private:
diff --git a/llvm/test/Analysis/LoopCacheAnalysis/PowerPC/LoopnestFixedSize.ll b/llvm/test/Analysis/LoopCacheAnalysis/PowerPC/LoopnestFixedSize.ll
--- a/llvm/test/Analysis/LoopCacheAnalysis/PowerPC/LoopnestFixedSize.ll
+++ b/llvm/test/Analysis/LoopCacheAnalysis/PowerPC/LoopnestFixedSize.ll
@@ -6,8 +6,8 @@
 ; Check delinearization in loop cache analysis can handle fixed-size arrays.
 ; The IR is copied from llvm/test/Analysis/DependenceAnalysis/SimpleSIVNoValidityCheckFixedSize.ll
 
-; CHECK-DAG: Loop 'for.body' has cost = 4186116
-; CHECK-DAG: Loop 'for.body4' has cost = 128898
+; CHECK: Loop 'for.body' has cost = 4186116
+; CHECK: Loop 'for.body4' has cost = 128898
 
 ;; #define N 1024
 ;; #define M 2048
@@ -48,8 +48,8 @@
 }
 
 
-; CHECK-DAG: Loop 'for.body' has cost = 4186116
-; CHECK-DAG: Loop 'for.body4' has cost = 128898
+; CHECK: Loop 'for.body' has cost = 4186116
+; CHECK: Loop 'for.body4' has cost = 128898
 
 define void @t2([2048 x i32]* %a) {
 entry:
@@ -83,11 +83,11 @@
 
 declare [2048 x i32]* @func_with_returned_arg([2048 x i32]* returned %arg)
 
-; CHECK-DAG: Loop 'for.body' has cost = 4472886244958208
-; CHECK-DAG: Loop 'for.body4' has cost = 4472886244958208
-; CHECK-DAG: Loop 'for.body8' has cost = 4472886244958208
-; CHECK-DAG: Loop 'for.body12' has cost = 4472886244958208
-; CHECK-DAG: Loop 'for.body16' has cost = 137728168833024
+; CHECK: Loop 'for.body' has cost = 4472886244958208
+; CHECK: Loop 'for.body4' has cost = 4472886244958208
+; CHECK: Loop 'for.body8' has cost = 4472886244958208
+; CHECK: Loop 'for.body12' has cost = 4472886244958208
+; CHECK: Loop 'for.body16' has cost = 137728168833024
 
 
 ;; #define N 1024
diff --git a/llvm/test/Analysis/LoopCacheAnalysis/PowerPC/loads-store.ll b/llvm/test/Analysis/LoopCacheAnalysis/PowerPC/loads-store.ll
--- a/llvm/test/Analysis/LoopCacheAnalysis/PowerPC/loads-store.ll
+++ b/llvm/test/Analysis/LoopCacheAnalysis/PowerPC/loads-store.ll
@@ -10,9 +10,9 @@
 ;         A[i][k][j] += B[i][k][j] + C[i][j][k];
 ; }
 
-; CHECK-DAG: Loop 'for.i' has cost = 3000000
-; CHECK-DAG: Loop 'for.k' has cost = 2030000
-; CHECK-DAG: Loop 'for.j' has cost = 1060000
+; CHECK: Loop 'for.i' has cost = 3000000
+; CHECK: Loop 'for.k' has cost = 2030000
+; CHECK: Loop 'for.j' has cost = 1060000
 
 define void @foo(i64 %n, i64 %m, i64 %o, i32* %A, i32* %B, i32* %C) {
 entry:
diff --git a/llvm/test/Analysis/LoopCacheAnalysis/PowerPC/matmul.ll b/llvm/test/Analysis/LoopCacheAnalysis/PowerPC/matmul.ll
--- a/llvm/test/Analysis/LoopCacheAnalysis/PowerPC/matmul.ll
+++ b/llvm/test/Analysis/LoopCacheAnalysis/PowerPC/matmul.ll
@@ -10,9 +10,9 @@
 ;         C[i][j] = C[i][j] + A[i][k] * B[k][j];
 ; }
 
-; CHECK-DAG:Loop 'for.i' has cost = 2010000
-; CHECK-DAG:Loop 'for.k' has cost = 1040000
-; CHECK-DAG:Loop 'for.j' has cost = 70000
+; CHECK:Loop 'for.i' has cost = 2010000
+; CHECK:Loop 'for.k' has cost = 1040000
+; CHECK:Loop 'for.j' has cost = 70000
     
 define void @matmul(i64 %n, i64 %m, i64 %o, i32* %A, i32* %B, i32* %C) {
 entry:
diff --git a/llvm/test/Analysis/LoopCacheAnalysis/PowerPC/matvecmul.ll b/llvm/test/Analysis/LoopCacheAnalysis/PowerPC/matvecmul.ll
--- a/llvm/test/Analysis/LoopCacheAnalysis/PowerPC/matvecmul.ll
+++ b/llvm/test/Analysis/LoopCacheAnalysis/PowerPC/matvecmul.ll
@@ -14,11 +14,11 @@
 ;                 y[k+1][j][i][l] = y[k+1][j][i][l] + b[k][j][i][m][l]*x[k][j][i][m]
 ; }
 
-; CHECK-DAG: Loop 'k_loop' has cost = 30000000000
-; CHECK-DAG: Loop 'j_loop' has cost = 30000000000
-; CHECK-DAG: Loop 'i_loop' has cost = 30000000000
-; CHECK-DAG: Loop 'm_loop' has cost = 10700000000
-; CHECK-DAG: Loop 'l_loop' has cost = 1300000000
+; CHECK: Loop 'k_loop' has cost = 30000000000
+; CHECK: Loop 'j_loop' has cost = 30000000000
+; CHECK: Loop 'i_loop' has cost = 30000000000
+; CHECK: Loop 'm_loop' has cost = 10700000000
+; CHECK: Loop 'l_loop' has cost = 1300000000
 
 %_elem_type_of_double = type <{ double }>
 
diff --git a/llvm/test/Analysis/LoopCacheAnalysis/PowerPC/single-store.ll b/llvm/test/Analysis/LoopCacheAnalysis/PowerPC/single-store.ll
--- a/llvm/test/Analysis/LoopCacheAnalysis/PowerPC/single-store.ll
+++ b/llvm/test/Analysis/LoopCacheAnalysis/PowerPC/single-store.ll
@@ -10,9 +10,9 @@
 ;         A[2*i+3][3*j-4][2*k+7] = 1;
 ; }
 
-; CHECK-DAG: Loop 'for.i' has cost = 1000000
-; CHECK-DAG: Loop 'for.j' has cost = 1000000
-; CHECK-DAG: Loop 'for.k' has cost = 60000
+; CHECK: Loop 'for.i' has cost = 1000000
+; CHECK: Loop 'for.j' has cost = 1000000
+; CHECK: Loop 'for.k' has cost = 60000
 
 define void @foo(i64 %n, i64 %m, i64 %o, i32* %A) {
 entry:
diff --git a/llvm/test/Analysis/LoopCacheAnalysis/PowerPC/stencil.ll b/llvm/test/Analysis/LoopCacheAnalysis/PowerPC/stencil.ll
--- a/llvm/test/Analysis/LoopCacheAnalysis/PowerPC/stencil.ll
+++ b/llvm/test/Analysis/LoopCacheAnalysis/PowerPC/stencil.ll
@@ -11,8 +11,8 @@
 ;     }   
 ; }
 
-; CHECK-DAG: Loop 'for.i' has cost = 20600
-; CHECK-DAG: Loop 'for.j' has cost = 800
+; CHECK: Loop 'for.i' has cost = 20600
+; CHECK: Loop 'for.j' has cost = 800
 
 define void @foo(i64 %n, i64 %m, i32* %A, i32* %B, i32* %C) {
 entry: