[NFC][LoopCacheAnalysis] Use stable_sort() to avoid non-deterministic print output

[congzhe]

Summary

As per discussion in https://reviews.llvm.org/D122857#3483861, https://reviews.llvm.org/D122857#3483912,
the print output of loop cache analysis sometimes has a non-deterministic order (and therefore we have been using CHECK-DAG in its lit tests).

This patch changes the sorting of LoopCosts to llvm::stable_sort() where we compare loop cost numbers and sort the loops. In case of the same loop cost numbers, llvm::stable_sort() now would output a deterministic loop order.

Comments on this patch are appreciated :)

[Meinersbur]

LGTM.

Making output deterministic is always a worthwhile goal.

[fhahn]

LGTM, thanks!

llvm/include/llvm/Analysis/LoopCacheAnalysis.h

245–246

nit: there should be no need to use llvm:: as this is already in the llvm namespace.

[congzhe]

Thanks for the review! Addressed Florian's comment, will land it shortly.

llvm/include/llvm/Analysis/LoopCacheAnalysis.h

private:
   ///     induction variable is used only in the reference subscript associated
   ///     with loop \p L, and (b) the reference stride is less than the cache
   ///     line size, or
   ///   - TripCount otherwise
   CacheCostTy computeRefGroupCacheCost(const ReferenceGroupTy &RG,
                                        const Loop &L) const;
 
   /// Sort the LoopCosts vector by decreasing cache cost.
   void sortLoopCosts() {
-    sort(LoopCosts, [](const LoopCacheCostTy &A, const LoopCacheCostTy &B) {
+    stable_sort(LoopCosts,
+                [](const LoopCacheCostTy &A, const LoopCacheCostTy &B) {
                   return A.second > B.second;
                 });
   }
 
 private:
   /// Loops in the loop nest associated with this object.
   LoopVectorTy Loops;
 
   /// Trip counts for the loops in the loop nest associated with this object.
   SmallVector<LoopTripCountTy, 3> TripCounts;

llvm/test/Analysis/LoopCacheAnalysis/PowerPC/LoopnestFixedSize.ll

 ; RUN: opt < %s -passes='print<loop-cache-cost>' -disable-output 2>&1 | FileCheck %s
 
 target datalayout = "e-m:e-i64:64-n32:64"
 target triple = "powerpc64le-unknown-linux-gnu"
 
 ; 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
 ;; void t1(int a[N][M]) {
 ;;   for (int i = 0; i < N-1; ++i)
 ;;     for (int j = 2; j < M; ++j)
 ;;       a[i][j] = a[i+1][j-2];
 ;; }
for.inc11:                                        ; preds = %for.body4
   %exitcond7 = icmp ne i64 %indvars.iv.next5, 1023
   br i1 %exitcond7, label %for.body, label %for.end13
 
 for.end13:                                        ; preds = %for.inc11
   ret void
 }
 
 
-; 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:
   br label %for.body
 
 for.body:                                         ; preds = %entry, %for.inc11
   %indvars.iv4 = phi i64 [ 0, %entry ], [ %indvars.iv.next5, %for.inc11 ]
   br label %for.body4
for.inc11:                                        ; preds = %for.body4
   br i1 %exitcond7, label %for.body, label %for.end13
 
 for.end13:                                        ; preds = %for.inc11
   ret void
 }
 
 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
 ;; #define M 2048
 ;; void t3(int a[][N][N][N][M]) {
 ;;   for (int i1 = 0; i1 < N-1; ++i1)
 ;;     for (int i2 = 2; i2 < N; ++i2)
 ;;       for (int i3 = 0; i3 < N; ++i3)

llvm/test/Analysis/LoopCacheAnalysis/PowerPC/loads-store.ll

 ; RUN: opt < %s -passes='print<loop-cache-cost>' -disable-output 2>&1 | FileCheck %s
 
 target datalayout = "e-m:e-i64:64-n32:64"
 target triple = "powerpc64le-unknown-linux-gnu"
 
 ; void foo(long n, long m, long o, int A[n][m][o], int B[n][m][o], int C[n][m][o]) {
 ;   for (long i = 0; i < n; i++)
 ;     for (long j = 0; j < m; j++)
 ;       for (long k = 0; k < o; k++)
 ;         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:
   %cmp32 = icmp sgt i64 %n, 0
   %cmp230 = icmp sgt i64 %m, 0
   %cmp528 = icmp sgt i64 %o, 0
   br i1 %cmp32, label %for.cond1.preheader.lr.ph, label %for.end
 

llvm/test/Analysis/LoopCacheAnalysis/PowerPC/matmul.ll

 ; RUN: opt < %s -passes='print<loop-cache-cost>' -disable-output 2>&1 | FileCheck %s
 
 target datalayout = "e-m:e-i64:64-n32:64"
 target triple = "powerpc64le-unknown-linux-gnu"
 
 ; void matmul(long n, long m, long o, int A[n][m], int B[n][m], int C[n]) {
 ;   for (long i = 0; i < n; i++) 
 ;     for (long j = 0; j < m; j++) 
 ;       for (long k = 0; k < o; k++) 
 ;         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:
   br label %for.i
 
 for.i:                                         ; preds = %entry, %for.inc.i
   %i = phi i64 [ 0, %entry ], [ %i.next, %for.inc.i ]
   %muli = mul i64 %i, %m

llvm/test/Analysis/LoopCacheAnalysis/PowerPC/matvecmul.ll

 ; RUN: opt < %s -passes='print<loop-cache-cost>' -disable-output 2>&1 | FileCheck %s
 
 target datalayout = "e-m:e-i64:64-n32:64"
 target triple = "powerpc64le-unknown-linux-gnu"
 
 ; void matvecmul(const double *__restrict y, const double * __restrict x, const double * __restrict b,
 ;    const int * __restrict nb, const int * __restrict nx, const int * __restrict ny, const int * __restrict nz) {
 ;
 ;   for (int k=1;k<nz,++k) 
 ;      for (int j=1;j<ny,++j)
 ;        for (int i=1;i<nx,++i)
 ;          for (int l=1;l<nb,++l)
 ;            for (int m=1;m<nb,++m)
 ;                 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 }>
 
 ; Function Attrs: norecurse nounwind
 define void @mat_vec_mpy([0 x %_elem_type_of_double]* noalias %y, [0 x %_elem_type_of_double]* noalias readonly %x,
     [0 x %_elem_type_of_double]* noalias readonly %b, i32* noalias readonly %nb, i32* noalias readonly %nx, 
     i32* noalias readonly %ny, i32* noalias readonly %nz) {
 mat_times_vec_entry:

llvm/test/Analysis/LoopCacheAnalysis/PowerPC/single-store.ll

 ; RUN: opt < %s -passes='print<loop-cache-cost>' -disable-output 2>&1 | FileCheck %s
 
 target datalayout = "e-m:e-i64:64-n32:64"
 target triple = "powerpc64le-unknown-linux-gnu"
 
 ; void foo(long n, long m, long o, int A[n][m][o]) {
 ;   for (long i = 0; i < n; i++)
 ;     for (long j = 0; j < m; j++)
 ;       for (long k = 0; k < o; k++)
 ;         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:
   %cmp32 = icmp sgt i64 %n, 0
   %cmp230 = icmp sgt i64 %m, 0
   %cmp528 = icmp sgt i64 %o, 0
   br i1 %cmp32, label %for.cond1.preheader.lr.ph, label %for.end
 

llvm/test/Analysis/LoopCacheAnalysis/PowerPC/stencil.ll

 ; RUN: opt < %s -passes='print<loop-cache-cost>' -disable-output 2>&1 | FileCheck %s
 
 target datalayout = "e-m:e-i64:64-n32:64"
 target triple = "powerpc64le-unknown-linux-gnu"
 
 ; void foo(long n, long m, long o, int A[n][m], int B[n][m], int C[n]) {
 ;   for (long i = 0; i < n; i++)
 ;     for (long j = 0; j < m; j++) {
 ;         A[i][j] = A[i][j+1] + B[i-1][j] + B[i+1][j+1] + C[i];
 ;         A[i][j] += B[i][i];
 ;     }   
 ; }
 
-; 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:
   %cmp32 = icmp sgt i64 %n, 0
   %cmp230 = icmp sgt i64 %m, 0
   br i1 %cmp32, label %for.cond1.preheader.lr.ph, label %for.end
 
 for.cond1.preheader.lr.ph:                        ; preds = %entry