Index: llvm/trunk/lib/Analysis/LoopAccessAnalysis.cpp =================================================================== --- llvm/trunk/lib/Analysis/LoopAccessAnalysis.cpp +++ llvm/trunk/lib/Analysis/LoopAccessAnalysis.cpp @@ -222,18 +222,40 @@ 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 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 Groups; + auto LeaderI = DepCands.findValue(DepCands.getLeaderValue(Access)); + + SmallVector 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. Index: llvm/trunk/test/Analysis/LoopAccessAnalysis/number-of-memchecks.ll =================================================================== --- llvm/trunk/test/Analysis/LoopAccessAnalysis/number-of-memchecks.ll +++ llvm/trunk/test/Analysis/LoopAccessAnalysis/number-of-memchecks.ll @@ -82,29 +82,29 @@ ; 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 @@ ; 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, Index: llvm/trunk/test/Analysis/LoopAccessAnalysis/unsafe-and-rt-checks.ll =================================================================== --- llvm/trunk/test/Analysis/LoopAccessAnalysis/unsafe-and-rt-checks.ll +++ llvm/trunk/test/Analysis/LoopAccessAnalysis/unsafe-and-rt-checks.ll @@ -15,14 +15,14 @@ ; 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