From d77a329d71c6c71c0788ca4578d99478cc82ca01 Mon Sep 17 00:00:00 2001
From: Peter Collingbourne <peter@pcc.me.uk>
Date: Wed, 9 Sep 2015 22:30:32 +0000
Subject: [PATCH] LowerBitSets: Fix non-determinism bug.

Visit disjoint sets in a deterministic order based on the maximum BitSetNM
index, otherwise the order in which we visit them will depend on pointer
comparisons. This was being exposed by MSan.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@247201 91177308-0d34-0410-b5e6-96231b3b80d8
---
 lib/Transforms/IPO/LowerBitSets.cpp       | 26 +++++++++++++++++++----
 test/Transforms/LowerBitSets/nonstring.ll |  2 +-
 test/Transforms/LowerBitSets/simple.ll    | 12 +++++------
 3 files changed, 29 insertions(+), 11 deletions(-)

diff --git a/lib/Transforms/IPO/LowerBitSets.cpp b/lib/Transforms/IPO/LowerBitSets.cpp
index de08da8a71f..549c4bf557a 100644
--- a/lib/Transforms/IPO/LowerBitSets.cpp
+++ b/lib/Transforms/IPO/LowerBitSets.cpp
@@ -938,7 +938,7 @@ bool LowerBitSets::buildBitSets() {
     for (unsigned I = 0, E = BitSetNM->getNumOperands(); I != E; ++I) {
       MDNode *Op = BitSetNM->getOperand(I);
       verifyBitSetMDNode(Op);
-      BitSetIdIndices[Op] = I;
+      BitSetIdIndices[Op->getOperand(0)] = I;
     }
   }
 
@@ -988,18 +988,36 @@ bool LowerBitSets::buildBitSets() {
   if (GlobalClasses.empty())
     return false;
 
-  // For each disjoint set we found...
+  // Build a list of disjoint sets ordered by their maximum BitSetNM index
+  // for determinism.
+  std::vector<std::pair<GlobalClassesTy::iterator, unsigned>> Sets;
   for (GlobalClassesTy::iterator I = GlobalClasses.begin(),
                                  E = GlobalClasses.end();
        I != E; ++I) {
     if (!I->isLeader()) continue;
-
     ++NumBitSetDisjointSets;
 
+    unsigned MaxIndex = 0;
+    for (GlobalClassesTy::member_iterator MI = GlobalClasses.member_begin(I);
+         MI != GlobalClasses.member_end(); ++MI) {
+      if ((*MI).is<Metadata *>())
+        MaxIndex = std::max(MaxIndex, BitSetIdIndices[MI->get<Metadata *>()]);
+    }
+    Sets.emplace_back(I, MaxIndex);
+  }
+  std::sort(Sets.begin(), Sets.end(),
+            [](const std::pair<GlobalClassesTy::iterator, unsigned> &S1,
+               const std::pair<GlobalClassesTy::iterator, unsigned> &S2) {
+              return S1.second < S2.second;
+            });
+
+  // For each disjoint set we found...
+  for (const auto &S : Sets) {
     // Build the list of bitsets in this disjoint set.
     std::vector<Metadata *> BitSets;
     std::vector<GlobalObject *> Globals;
-    for (GlobalClassesTy::member_iterator MI = GlobalClasses.member_begin(I);
+    for (GlobalClassesTy::member_iterator MI =
+             GlobalClasses.member_begin(S.first);
          MI != GlobalClasses.member_end(); ++MI) {
       if ((*MI).is<Metadata *>())
         BitSets.push_back(MI->get<Metadata *>());
diff --git a/test/Transforms/LowerBitSets/nonstring.ll b/test/Transforms/LowerBitSets/nonstring.ll
index 0d655da3bb0..e61c9123e08 100644
--- a/test/Transforms/LowerBitSets/nonstring.ll
+++ b/test/Transforms/LowerBitSets/nonstring.ll
@@ -4,8 +4,8 @@
 
 target datalayout = "e-p:32:32"
 
-; CHECK: @[[BNAME:.*]] = private constant { [2 x i32] }
 ; CHECK: @[[ANAME:.*]] = private constant { i32 }
+; CHECK: @[[BNAME:.*]] = private constant { [2 x i32] }
 
 @a = constant i32 1
 @b = constant [2 x i32] [i32 2, i32 3]
diff --git a/test/Transforms/LowerBitSets/simple.ll b/test/Transforms/LowerBitSets/simple.ll
index df2ccf98786..6c9d66ae2bd 100644
--- a/test/Transforms/LowerBitSets/simple.ll
+++ b/test/Transforms/LowerBitSets/simple.ll
@@ -26,16 +26,16 @@ target datalayout = "e-p:32:32"
 !4 = !{!"bitset2", i32* @c, i32 0}
 ; CHECK-NODISCARD-DAG: !{!"bitset2", i32* @c, i32 0}
 
+; Entries whose second operand is null (the result of a global being DCE'd)
+; should be ignored.
+!5 = !{!"bitset2", null, i32 0}
+
 ; Offset 0, 4 byte alignment
-!5 = !{!"bitset3", i32* @a, i32 0}
+!6 = !{!"bitset3", i32* @a, i32 0}
 ; CHECK-NODISCARD-DAG: !{!"bitset3", i32* @a, i32 0}
-!6 = !{!"bitset3", i32* @c, i32 0}
+!7 = !{!"bitset3", i32* @c, i32 0}
 ; CHECK-NODISCARD-DAG: !{!"bitset3", i32* @c, i32 0}
 
-; Entries whose second operand is null (the result of a global being DCE'd)
-; should be ignored.
-!7 = !{!"bitset2", null, i32 0}
-
 !llvm.bitsets = !{ !0, !1, !2, !3, !4, !5, !6, !7 }
 
 ; CHECK: @bits_use{{[0-9]*}} = private alias i8* @bits{{[0-9]*}}
-- 
2.34.1