[polly] Fix non-deterministic output due to iteration of unordered ScopArrayInfo

[mgrang]

Summary

This fixes the following failures in the reverse iteration builder:
http://lab.llvm.org:8011/builders/reverse-iteration/builds/25

Polly :: MaximalStaticExpansion/working_deps_between_inners.ll
Polly :: MaximalStaticExpansion/working_expansion_multiple_dependences_per_statement.ll
Polly :: MaximalStaticExpansion/working_expansion_multiple_instruction_per_statement.ll
Polly :: MaximalStaticExpansion/working_phi_expansion.ll

[grosser]

lib/Transform/MaximalStaticExpansion.cpp

504

Why do you need to sort the arrays. The original data structure is a SetVector and should consequently be deterministic. Should we just change the SmallPtrSet into a SmallVector? Would this be sufficient?

[mgrang]

lib/Transform/MaximalStaticExpansion.cpp

504

Yes, we actually do not need to sort as S.arrays() is a SetVector. Consequently, the unit tests do not need to be fixed either. Thanks!

lib/Transform/MaximalStaticExpansion.cpp

bool MaximalStaticExpander::runOnScop(Scop &S) {
   // Get the ORE from OptimizationRemarkEmitterWrapperPass.
   ORE = &(getAnalysis<OptimizationRemarkEmitterWrapperPass>().getORE());
 
   // Get the RAW Dependences.
   auto &DI = getAnalysis<DependenceInfo>();
   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;
     SmallPtrSet<MemoryAccess *, 4> AllReads;
     if (!isExpandable(SAI, AllWrites, AllReads, S, Dependences))
       continue;
 
     if (SAI->isValueKind() || SAI->isArrayKind()) {

test/MaximalStaticExpansion/working_deps_between_inners.ll

 ;   A[i+j] = tmp*B[k];
 ;       }
 ;     }
 ;   }
 ; }
 ;
 ; 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
 ;
 ; CHECK: new: { Stmt_for_body3[i0, i1] -> MemRef_B_Stmt_for_body3_expanded[i0, i1] };
 ; CHECK: new: { Stmt_for_body11[i0, i1, i2] -> MemRef_B_Stmt_for_body3_expanded[i0, i2] };
 ; CHECK: new: { Stmt_for_body11[i0, i1, i2] -> MemRef_A_Stmt_for_body11_expanded[i0, i1, i2] };
 ;
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"

test/MaximalStaticExpansion/working_expansion_multiple_dependences_per_statement.ll

 ; 
 ;     A[j] = B[j];
 ;     C[j] = D[j];
 ;   }
 ; }
 ;
 ; 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] };
 ; CHECK: new: { Stmt_for_body9[i0, i1] -> MemRef_D_Stmt_for_body9_expanded[i0, i1] };
 ; CHECK: new: { Stmt_for_end15[i0] -> MemRef_B_Stmt_for_body4_expanded[i0, i0] };
 ; CHECK: new: { Stmt_for_end15[i0] -> MemRef_A_Stmt_for_end15_expanded[i0] };
 ; CHECK: new: { Stmt_for_end15[i0] -> MemRef_D_Stmt_for_body9_expanded[i0, i0] };
 ; CHECK: new: { Stmt_for_end15[i0] -> MemRef_C_Stmt_for_end15_expanded[i0] };

test/MaximalStaticExpansion/working_expansion_multiple_instruction_per_statement.ll

 ;       D[i] = i;
 ;     }
 ;     A[j] = B[j];
 ;     C[j] = D[j];
 ;   }
 ; }
 ;
 ; 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
 ;
 ; CHECK: new: { Stmt_for_body4[i0, i1] -> MemRef_B_Stmt_for_body4_expanded[i0, i1] };
 ; CHECK: new: { Stmt_for_body4[i0, i1] -> MemRef_D_Stmt_for_body4_expanded[i0, i1] };
 ; CHECK: new: { Stmt_for_end[i0] -> MemRef_B_Stmt_for_body4_expanded[i0, i0] };
 ; CHECK: new: { Stmt_for_end[i0] -> MemRef_A_Stmt_for_end_expanded[i0] };
 ; CHECK: new: { Stmt_for_end[i0] -> MemRef_D_Stmt_for_body4_expanded[i0, i0] };

test/MaximalStaticExpansion/working_phi_expansion.ll

 ;
 ; Check that the pass detects that tmp_04 reads from original value.
 ;
 ; MSE: MemRef_tmp_04__phi read from its original value.
 ;
 ; 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.
 ;
 ; CHECK-NOT: new: { Stmt_for_body[i0] -> MemRef_tmp_04__phi_Stmt_for_body_expanded[i0] };
 ; CHECK: new: { Stmt_for_body[i0] -> MemRef_tmp_11__phi_Stmt_for_inc_expanded[i0, 0] };
 ; CHECK: new: { Stmt_for_inc[i0, i1] -> MemRef_tmp_11__phi_Stmt_for_inc_expanded[i0, 1 + i1] : i1 <= 9998 };
 ; CHECK: new: { Stmt_for_inc[i0, i1] -> MemRef_tmp_11__phi_Stmt_for_inc_expanded[i0, i1] };
 ; CHECK: new: { Stmt_for_inc[i0, 9999] -> MemRef_add_lcssa__phi_Stmt_for_end_expanded[i0] };