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

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.

Subscribers: llvm-commits

Differential Revision: http://reviews.llvm.org/D11064

llvm-svn: 241809

2 files changed, 30 insertions, 30 deletions

diff --git a/llvm/test/Analysis/LoopAccessAnalysis/number-of-memchecks.ll b/llvm/test/Analysis/LoopAccessAnalysis/number-of-memchecks.ll
index 76c96abbe96..52a4cd06bbd 100644
--- a/llvm/test/Analysis/LoopAccessAnalysis/number-of-memchecks.ll
+++ b/llvm/test/Analysis/LoopAccessAnalysis/number-of-memchecks.ll
@@ -82,29 +82,29 @@ for.end:                                          ; preds = %for.body
 ; 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,
@@ -154,29 +154,29 @@ for.end:                                          ; preds = %for.body
 ; 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,
diff --git a/llvm/test/Analysis/LoopAccessAnalysis/unsafe-and-rt-checks.ll b/llvm/test/Analysis/LoopAccessAnalysis/unsafe-and-rt-checks.ll
index 237cbc8b987..25dfc35d5cd 100644
--- a/llvm/test/Analysis/LoopAccessAnalysis/unsafe-and-rt-checks.ll
+++ b/llvm/test/Analysis/LoopAccessAnalysis/unsafe-and-rt-checks.ll
@@ -15,14 +15,14 @@ target triple = "x86_64-apple-macosx10.10.0"
 ; 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