Don't rely on the DepCands iteration order when constructing checking pointer groups

[sbaranga]

Summary

The checking pointer group construction algorithm relied on the iteration on DepCands.
We would need the same leaders across runs and the same iteration order over the underlying std::set for determinism.

This changes the algorithm to process the pointers in the order in which they were added to the runtime check, which is deterministic.
We need to update the tests, since the order in which pointers appear has changed.

No new tests were added, since it is impossible to test for non-determinism.

[anemet]

llvm/trunk/lib/Analysis/LoopAccessAnalysis.cpp

245

s/indeces/indices

245–253

Are you positive we need to sort the members too?

I think these are hooked up to the equivalence class in program order and it's effectively a linked list, so they should preserve the chaining order.

Either way it needs a comment.

[sbaranga]

llvm/trunk/lib/Analysis/LoopAccessAnalysis.cpp

245–253

I think that's correct, they don't actually need to be sorted - at least with the current implementation of equivalence classes. I think the question is if this is a guarantee or an internal implementation detail. I can't find any place that explicitly makes this guarantee.

[anemet]

llvm/trunk/lib/Analysis/LoopAccessAnalysis.cpp

245–253

Sounds like something that is worth documenting (it removes redundant work in our case).

People can object if there is a reason to keep this unspecified but I don't see why that would be useful.

[sbaranga]

llvm/trunk/lib/Analysis/LoopAccessAnalysis.cpp

245–253

Thanks! I've removed the call to std::sort in r242033, I'll update the documentation in another change.

llvm/trunk/lib/Analysis/LoopAccessAnalysis.cpp

void LoopAccessInfo::RuntimePointerCheck::groupChecks(
   }
 
   unsigned TotalComparisons = 0;
 
   DenseMap<Value *, unsigned> PositionMap;
   for (unsigned Pointer = 0; Pointer < Pointers.size(); ++Pointer)
     PositionMap[Pointers[Pointer]] = Pointer;
 
+  // We need to keep track of what pointers we've already seen so we
+  // don't process them twice.
+  SmallSet<unsigned, 2> Seen;
+
   // Go through all equivalence classes, get the the "pointer check groups"
-  // and add them to the overall solution.
-  for (auto DI = DepCands.begin(), DE = DepCands.end(); DI != DE; ++DI) {
-    if (!DI->isLeader())
+  // and add them to the overall solution. We use the order in which accesses
+  // appear in 'Pointers' to enforce determinism.
+  for (unsigned I = 0; I < Pointers.size(); ++I) {
+    // We've seen this pointer before, and therefore already processed
+    // its equivalence class.
+    if (Seen.count(I))
       continue;
 
+    MemoryDepChecker::MemAccessInfo Access(Pointers[I], IsWritePtr[I]);
+
     SmallVector<CheckingPtrGroup, 2> Groups;
+    auto LeaderI = DepCands.findValue(DepCands.getLeaderValue(Access));
+
+    SmallVector<unsigned, 2> MemberIndices;
 
-    for (auto MI = DepCands.member_begin(DI), ME = DepCands.member_end();
+    // Get all indeces of the members of this equivalence class and sort them.
+    // This will allow us to process all accesses in the order in which they
+    // were added to the RuntimePointerCheck.
+    for (auto MI = DepCands.member_begin(LeaderI), ME = DepCands.member_end();
          MI != ME; ++MI) {
       unsigned Pointer = PositionMap[MI->getPointer()];
+      MemberIndices.push_back(Pointer);
+    }
+    std::sort(MemberIndices.begin(), MemberIndices.end());
+
+    for (unsigned Pointer : MemberIndices) {
       bool Merged = false;
+      // Mark this pointer as seen.
+      Seen.insert(Pointer);
 
       // Go through all the existing sets and see if we can find one
       // which can include this pointer.
       for (CheckingPtrGroup &Group : Groups) {
         // Don't perform more than a certain amount of comparisons.
         // This should limit the cost of grouping the pointers to something
         // reasonable.  If we do end up hitting this threshold, the algorithm
         // will create separate groups for all remaining pointers.

llvm/trunk/test/Analysis/LoopAccessAnalysis/number-of-memchecks.ll

 ; and the writes can be merged as well. This gives us a
 ; total of 2 memory checks.
 
 ; CHECK: function 'testg':
 
 ; CHECK: Run-time memory checks:
 ; CHECK-NEXT:   Check 0:
 ; CHECK-NEXT:     Comparing group 0:
-; CHECK-NEXT:       %arrayidxA1 = getelementptr inbounds i16, i16* %a, i64 %add
-; CHECK-NEXT:       %arrayidxA = getelementptr inbounds i16, i16* %a, i64 %ind
-; CHECK-NEXT:     Against group 2:
-; CHECK-NEXT:       %arrayidxC1 = getelementptr inbounds i16, i16* %c, i64 %store_ind_inc
 ; CHECK-NEXT:       %arrayidxC = getelementptr inbounds i16, i16* %c, i64 %store_ind
-; CHECK-NEXT:   Check 1:
-; CHECK-NEXT:     Comparing group 1:
-; CHECK-NEXT:       %arrayidxB = getelementptr inbounds i16, i16* %b, i64 %ind
-; CHECK-NEXT:     Against group 2:
 ; CHECK-NEXT:       %arrayidxC1 = getelementptr inbounds i16, i16* %c, i64 %store_ind_inc
+; CHECK-NEXT:     Against group 1:
+; CHECK-NEXT:       %arrayidxA = getelementptr inbounds i16, i16* %a, i64 %ind
+; CHECK-NEXT:       %arrayidxA1 = getelementptr inbounds i16, i16* %a, i64 %add
+; CHECK-NEXT:   Check 1:
+; CHECK-NEXT:     Comparing group 0:
 ; CHECK-NEXT:       %arrayidxC = getelementptr inbounds i16, i16* %c, i64 %store_ind
+; CHECK-NEXT:       %arrayidxC1 = getelementptr inbounds i16, i16* %c, i64 %store_ind_inc
+; CHECK-NEXT:     Against group 2:
+; CHECK-NEXT:       %arrayidxB = getelementptr inbounds i16, i16* %b, i64 %ind
 ; CHECK-NEXT:   Grouped accesses:
 ; CHECK-NEXT:    Group 0:
+; CHECK-NEXT:       (Low: %c High: (78 + %c))
+; CHECK-NEXT:         Member: {%c,+,4}
+; CHECK-NEXT:         Member: {(2 + %c),+,4}
+; CHECK-NEXT:     Group 1:
 ; CHECK-NEXT:       (Low: %a High: (40 + %a))
-; CHECK-NEXT:         Member: {(2 + %a),+,2}
 ; CHECK-NEXT:         Member: {%a,+,2}
-; CHECK-NEXT:     Group 1:
+; CHECK-NEXT:         Member: {(2 + %a),+,2}
+; CHECK-NEXT:     Group 2:
 ; CHECK-NEXT:       (Low: %b High: (38 + %b))
 ; CHECK-NEXT:         Member: {%b,+,2}
-; CHECK-NEXT:     Group 2:
-; CHECK-NEXT:       (Low: %c High: (78 + %c))
-; CHECK-NEXT:         Member: {(2 + %c),+,4}
-; CHECK-NEXT:         Member: {%c,+,4}
 
 define void @testg(i16* %a,
                i16* %b,
                i16* %c) {
 entry:
   br label %for.body
 
 for.body:                                         ; preds = %for.body, %entry

 ; group, but the GEPs used for the reads are not marked as inbounds.
 ; We can still merge them because we are using a unit stride for
 ; accesses, so we cannot overflow the GEPs.
 
 ; CHECK: function 'testh':
 ; CHECK: Run-time memory checks:
 ; CHECK-NEXT:   Check 0:
 ; CHECK-NEXT:     Comparing group 0:
-; CHECK-NEXT:         %arrayidxA1 = getelementptr i16, i16* %a, i64 %add
-; CHECK-NEXT:         %arrayidxA = getelementptr i16, i16* %a, i64 %ind
-; CHECK-NEXT:     Against group 2:
-; CHECK-NEXT:         %arrayidxC1 = getelementptr inbounds i16, i16* %c, i64 %store_ind_inc
 ; CHECK-NEXT:         %arrayidxC = getelementptr inbounds i16, i16* %c, i64 %store_ind
-; CHECK-NEXT:   Check 1:
-; CHECK-NEXT:     Comparing group 1:
-; CHECK-NEXT:         %arrayidxB = getelementptr i16, i16* %b, i64 %ind
-; CHECK-NEXT:     Against group 2:
 ; CHECK-NEXT:         %arrayidxC1 = getelementptr inbounds i16, i16* %c, i64 %store_ind_inc
+; CHECK-NEXT:     Against group 1:
+; CHECK-NEXT:         %arrayidxA = getelementptr i16, i16* %a, i64 %ind
+; CHECK-NEXT:         %arrayidxA1 = getelementptr i16, i16* %a, i64 %add
+; CHECK-NEXT:   Check 1:
+; CHECK-NEXT:     Comparing group 0:
 ; CHECK-NEXT:         %arrayidxC = getelementptr inbounds i16, i16* %c, i64 %store_ind
+; CHECK-NEXT:         %arrayidxC1 = getelementptr inbounds i16, i16* %c, i64 %store_ind_inc
+; CHECK-NEXT:     Against group 2:
+; CHECK-NEXT:         %arrayidxB = getelementptr i16, i16* %b, i64 %ind
 ; CHECK-NEXT:   Grouped accesses:
 ; CHECK-NEXT:     Group 0:
+; CHECK-NEXT:       (Low: %c High: (78 + %c))
+; CHECK-NEXT:         Member: {%c,+,4}
+; CHECK-NEXT:         Member: {(2 + %c),+,4}
+; CHECK-NEXT:     Group 1:
 ; CHECK-NEXT:       (Low: %a High: (40 + %a))
-; CHECK-NEXT:         Member: {(2 + %a),+,2}
 ; CHECK-NEXT:         Member: {%a,+,2}
-; CHECK-NEXT:     Group 1:
+; CHECK-NEXT:         Member: {(2 + %a),+,2}
+; CHECK-NEXT:     Group 2:
 ; CHECK-NEXT:       (Low: %b High: (38 + %b))
 ; CHECK-NEXT:         Member: {%b,+,2}
-; CHECK-NEXT:     Group 2:
-; CHECK-NEXT:       (Low: %c High: (78 + %c))
-; CHECK-NEXT:         Member: {(2 + %c),+,4}
-; CHECK-NEXT:         Member: {%c,+,4}
 
 define void @testh(i16* %a,
                i16* %b,
                i16* %c) {
 entry:
   br label %for.body
 
 for.body:                                         ; preds = %for.body, %entry

llvm/trunk/test/Analysis/LoopAccessAnalysis/unsafe-and-rt-checks.ll

 ; CHECK: Report: unsafe dependent memory operations in loop
 ; CHECK-NEXT: Interesting Dependences:
 ; CHECK-NEXT:   Backward:
 ; CHECK-NEXT:     %loadA = load i16, i16* %arrayidxA, align 2 ->
 ; CHECK-NEXT:     store i16 %mul1, i16* %arrayidxA_plus_2, align 2
 ; CHECK: Run-time memory checks:
 ; CHECK-NEXT: 0:
 ; CHECK-NEXT: Comparing group
-; CHECK-NEXT:   %arrayidxA = getelementptr inbounds i16, i16* %a, i64 %storemerge3
 ; CHECK-NEXT:   %arrayidxA_plus_2 = getelementptr inbounds i16, i16* %a, i64 %add
+; CHECK-NEXT:   %arrayidxA = getelementptr inbounds i16, i16* %a, i64 %storemerge3
 ; CHECK-NEXT: Against group
 ; CHECK-NEXT:   %arrayidxB = getelementptr inbounds i16, i16* %b, i64 %storemerge3
 ; CHECK-NEXT: 1:
 ; CHECK-NEXT: Comparing group
-; CHECK-NEXT:   %arrayidxA = getelementptr inbounds i16, i16* %a, i64 %storemerge3
 ; CHECK-NEXT:   %arrayidxA_plus_2 = getelementptr inbounds i16, i16* %a, i64 %add
+; CHECK-NEXT:   %arrayidxA = getelementptr inbounds i16, i16* %a, i64 %storemerge3
 ; CHECK-NEXT: Against group
 ; CHECK-NEXT:   %arrayidxC = getelementptr inbounds i16, i16* %c, i64 %storemerge3
 
 @B = common global i16* null, align 8
 @A = common global i16* null, align 8
 @C = common global i16* null, align 8
 
 define void @f() {