From 7f2cd21ddd31d74b25f671e31eb89c0c9775b602 Mon Sep 17 00:00:00 2001
From: "Duncan P. N. Exon Smith" <dexonsmith@apple.com>
Date: Tue, 5 Aug 2014 17:49:48 +0000
Subject: [PATCH] BitcodeReader: Fix non-determinism in use-list order

`BasicBlockFwdRefs` (and `BlockAddrFwdRefs` before it) was being emptied
in a non-deterministic order.  When predicting use-list order I've
worked around this another way, but even when parsing lazily (and we
can't recreate use-list order) use-lists should be deterministic.

Make them so by using a side-queue of functions with forward-referenced
blocks that gets visited in order.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@214899 91177308-0d34-0410-b5e6-96231b3b80d8
---
 lib/Bitcode/Reader/BitcodeReader.cpp | 16 +++++++++++++---
 lib/Bitcode/Reader/BitcodeReader.h   |  2 ++
 2 files changed, 15 insertions(+), 3 deletions(-)

diff --git a/lib/Bitcode/Reader/BitcodeReader.cpp b/lib/Bitcode/Reader/BitcodeReader.cpp
index 85dde397916..79085248770 100644
--- a/lib/Bitcode/Reader/BitcodeReader.cpp
+++ b/lib/Bitcode/Reader/BitcodeReader.cpp
@@ -38,9 +38,14 @@ std::error_code BitcodeReader::materializeForwardReferencedFunctions() {
   // Prevent recursion.
   WillMaterializeAllForwardRefs = true;
 
-  while (!BasicBlockFwdRefs.empty()) {
-    Function *F = BasicBlockFwdRefs.begin()->first;
+  while (!BasicBlockFwdRefQueue.empty()) {
+    Function *F = BasicBlockFwdRefQueue.front();
+    BasicBlockFwdRefQueue.pop_front();
     assert(F && "Expected valid function");
+    if (!BasicBlockFwdRefs.count(F))
+      // Already materialized.
+      continue;
+
     // Check for a function that isn't materializable to prevent an infinite
     // loop.  When parsing a blockaddress stored in a global variable, there
     // isn't a trivial way to check if a function will have a body without a
@@ -52,6 +57,7 @@ std::error_code BitcodeReader::materializeForwardReferencedFunctions() {
     if (std::error_code EC = Materialize(F))
       return EC;
   }
+  assert(BasicBlockFwdRefs.empty() && "Function missing from queue");
 
   // Reset state.
   WillMaterializeAllForwardRefs = false;
@@ -72,6 +78,7 @@ void BitcodeReader::FreeState() {
   MDKindMap.clear();
 
   assert(BasicBlockFwdRefs.empty() && "Unresolved blockaddress fwd references");
+  BasicBlockFwdRefQueue.clear();
 }
 
 //===----------------------------------------------------------------------===//
@@ -1629,7 +1636,10 @@ std::error_code BitcodeReader::ParseConstants() {
         // Otherwise insert a placeholder and remember it so it can be inserted
         // when the function is parsed.
         BB = BasicBlock::Create(Context);
-        BasicBlockFwdRefs[Fn].emplace_back(BBID, BB);
+        auto &FwdBBs = BasicBlockFwdRefs[Fn];
+        if (FwdBBs.empty())
+          BasicBlockFwdRefQueue.push_back(Fn);
+        FwdBBs.emplace_back(BBID, BB);
       }
       V = BlockAddress::get(Fn, BB);
       break;
diff --git a/lib/Bitcode/Reader/BitcodeReader.h b/lib/Bitcode/Reader/BitcodeReader.h
index a25ab37a4e3..0b3c1c17c49 100644
--- a/lib/Bitcode/Reader/BitcodeReader.h
+++ b/lib/Bitcode/Reader/BitcodeReader.h
@@ -22,6 +22,7 @@
 #include "llvm/IR/OperandTraits.h"
 #include "llvm/IR/Type.h"
 #include "llvm/IR/ValueHandle.h"
+#include <deque>
 #include <system_error>
 #include <vector>
 
@@ -183,6 +184,7 @@ class BitcodeReader : public GVMaterializer {
   /// inserted lazily into functions when they're loaded.
   typedef std::pair<unsigned, BasicBlock *> BasicBlockRefTy;
   DenseMap<Function *, std::vector<BasicBlockRefTy>> BasicBlockFwdRefs;
+  std::deque<Function *> BasicBlockFwdRefQueue;
 
   /// UseRelativeIDs - Indicates that we are using a new encoding for
   /// instruction operands where most operands in the current
-- 
2.34.1