Index: lib/Transform/MaximalStaticExpansion.cpp
===================================================================
--- lib/Transform/MaximalStaticExpansion.cpp
+++ lib/Transform/MaximalStaticExpansion.cpp
@@ -496,8 +496,12 @@
   auto &D = DI.getDependences(Dependences::AL_Reference);
   auto Dependences = isl::give(D.getDependences(Dependences::TYPE_RAW));
 
-  SmallPtrSet<ScopArrayInfo *, 4> CurrentSAI(S.arrays().begin(),
+  // Sort the ScopArrayInfo to avoid non-deterministic output.
+  SmallVector<ScopArrayInfo *, 4> CurrentSAI(S.arrays().begin(),
                                              S.arrays().end());
+  std::sort(CurrentSAI.begin(), CurrentSAI.end(),
+            [](ScopArrayInfo *A, ScopArrayInfo *B) {
+               return A->getName() < B->getName(); });
 
   for (auto SAI : CurrentSAI) {
     SmallPtrSet<MemoryAccess *, 4> AllWrites;
Index: test/MaximalStaticExpansion/working_deps_between_inners.ll
===================================================================
--- test/MaximalStaticExpansion/working_deps_between_inners.ll
+++ test/MaximalStaticExpansion/working_deps_between_inners.ll
@@ -26,8 +26,8 @@
 ;
 ; Check if the expanded SAI are created
 ;
-; CHECK: double MemRef_B_Stmt_for_body3_expanded[10000][10000]; // Element size 8
 ; CHECK: double MemRef_A_Stmt_for_body11_expanded[10000][10000][10000]; // Element size 8
+; CHECK: double MemRef_B_Stmt_for_body3_expanded[10000][10000]; // Element size 8
 ;
 ; Check if the memory accesses are modified
 ;
Index: test/MaximalStaticExpansion/working_expansion_multiple_dependences_per_statement.ll
===================================================================
--- test/MaximalStaticExpansion/working_expansion_multiple_dependences_per_statement.ll
+++ test/MaximalStaticExpansion/working_expansion_multiple_dependences_per_statement.ll
@@ -23,10 +23,10 @@
 ;
 ; Check that expanded SAI are created
 ;
-; CHECK: double MemRef_B_Stmt_for_body4_expanded[10000][10000]; // Element size 8
-; CHECK: double MemRef_D_Stmt_for_body9_expanded[10000][10000]; // Element size 8
 ; CHECK: i64 MemRef_A_Stmt_for_end15_expanded[10000]; // Element size 8
+; CHECK: double MemRef_B_Stmt_for_body4_expanded[10000][10000]; // Element size 8
 ; CHECK: i64 MemRef_C_Stmt_for_end15_expanded[10000]; // Element size 8
+; CHECK: double MemRef_D_Stmt_for_body9_expanded[10000][10000]; // Element size 8
 ;
 ; Check that the memory accesses are modified
 ; CHECK: new: { Stmt_for_body4[i0, i1] -> MemRef_B_Stmt_for_body4_expanded[i0, i1] };
Index: test/MaximalStaticExpansion/working_expansion_multiple_instruction_per_statement.ll
===================================================================
--- test/MaximalStaticExpansion/working_expansion_multiple_instruction_per_statement.ll
+++ test/MaximalStaticExpansion/working_expansion_multiple_instruction_per_statement.ll
@@ -20,10 +20,10 @@
 ; }
 ;
 ; Check that expanded SAI are created
-; CHECK: double MemRef_B_Stmt_for_body4_expanded[10000][10000]; // Element size 8
-; CHECK: double MemRef_D_Stmt_for_body4_expanded[10000][10000]; // Element size 8
 ; CHECK: i64 MemRef_A_Stmt_for_end_expanded[10000]; // Element size 8
+; CHECK: double MemRef_B_Stmt_for_body4_expanded[10000][10000]; // Element size 8
 ; CHECK: i64 MemRef_C_Stmt_for_end_expanded[10000]; // Element size 8
+; CHECK: double MemRef_D_Stmt_for_body4_expanded[10000][10000]; // Element size 8
 ;
 ; Check that the memory access are modified
 ;
Index: test/MaximalStaticExpansion/working_phi_expansion.ll
===================================================================
--- test/MaximalStaticExpansion/working_phi_expansion.ll
+++ test/MaximalStaticExpansion/working_phi_expansion.ll
@@ -26,9 +26,9 @@
 ; Check that the SAI are created except the expanded SAI of tmp_04.
 ;
 ; CHECK-NOT: double MemRef_tmp_04__phi_Stmt_for_body_expanded[10000]; // Element size 8
-; CHECK: double MemRef_tmp_11__phi_Stmt_for_inc_expanded[10000][10000]; // Element size
-; CHECK: double MemRef_add_lcssa__phi_Stmt_for_end_expanded[10000]; // Element size 8
 ; CHECK: double MemRef_B_Stmt_for_end_expanded[10000]; // Element size 8
+; CHECK: double MemRef_add_lcssa__phi_Stmt_for_end_expanded[10000]; // Element size 8
+; CHECK: double MemRef_tmp_11__phi_Stmt_for_inc_expanded[10000][10000]; // Element size 8
 ;
 ; Check that the memory accesses are modified except those related to tmp_04.
 ;