diff --git a/llvm/lib/Bitcode/Reader/ValueList.cpp b/llvm/lib/Bitcode/Reader/ValueList.cpp
--- a/llvm/lib/Bitcode/Reader/ValueList.cpp
+++ b/llvm/lib/Bitcode/Reader/ValueList.cpp
@@ -8,6 +8,7 @@
 
 #include "ValueList.h"
 #include "llvm/ADT/SmallVector.h"
+#include "llvm/ADT/TinyPtrVector.h"
 #include "llvm/IR/Argument.h"
 #include "llvm/IR/Constant.h"
 #include "llvm/IR/Constants.h"
@@ -151,75 +152,107 @@
 /// constant.  Instead of doing this, we look at all the uses and rewrite all
 /// the place holders at once for any constant that uses a placeholder.
 void BitcodeReaderValueList::resolveConstantForwardRefs() {
-  // Sort the values by-pointer so that they are efficient to look up with a
-  // binary search.
-  llvm::sort(ResolveConstants);
-
+  DenseMap<Constant*, Constant*> ConstantMapping;
+  ConstantMapping.reserve(ResolveConstants.size());
+
+  // For each constant, compute how many of its operands needs to be rewritten.
+  // This is used later to ensure we process constants in the correct order.
+  DenseMap<Constant*, unsigned> NumRewrittenOperands;
+  SmallVector<Constant *, 64> RewriteWorklist;
+  auto CountOperandsOfUsers = [&](Constant* C) {
+    for (Use &ConstantUse : C->uses()) {
+      auto *ConstantUser = dyn_cast<Constant>(ConstantUse.getUser());
+      if (ConstantUser && !isa<GlobalValue>(ConstantUser)) {
+        unsigned NumOperandsFound = ++NumRewrittenOperands[ConstantUser];
+        if (NumOperandsFound == 1)
+          RewriteWorklist.push_back(ConstantUser);
+      }
+    }
+  };
+  for (auto ResolveConstant : ResolveConstants)
+    CountOperandsOfUsers(ResolveConstant.first);
+  while (!RewriteWorklist.empty())
+    CountOperandsOfUsers(RewriteWorklist.pop_back_val());
+
+  // List of constants in the order we process them.  We use this later to
+  // perform the actual replacements.
+  SmallVector<Constant *, 64> RewrittenConstants;
+  // Temporary vector for operands.
   SmallVector<Constant *, 64> NewOps;
-
-  while (!ResolveConstants.empty()) {
-    Value *RealVal = operator[](ResolveConstants.back().second);
-    Constant *Placeholder = ResolveConstants.back().first;
-    ResolveConstants.pop_back();
-
-    // Loop over all users of the placeholder, updating them to reference the
-    // new value.  If they reference more than one placeholder, update them all
-    // at once.
-    while (!Placeholder->use_empty()) {
-      auto UI = Placeholder->user_begin();
-      User *U = *UI;
-
-      // If the using object isn't uniqued, just update the operands.  This
-      // handles instructions and initializers for global variables.
-      if (!isa<Constant>(U) || isa<GlobalValue>(U)) {
-        UI.getUse().set(RealVal);
-        continue;
+  // Mapping from constants which will be rewritten to placeholders for
+  // those constants.
+  DenseMap<Constant*, TinyPtrVector<Constant*>> ConstToPlaceholders;
+
+  // Process a constant that has a finalized mapping.
+  auto MapConstant = [&](Constant* C, Constant *NewC) {
+    ConstantMapping[C] = NewC;
+    RewrittenConstants.push_back(C);
+    for (auto &ConstantUse : C->uses()) {
+      auto *ConstantUser = dyn_cast<Constant>(ConstantUse.getUser());
+      if (ConstantUser && !isa<GlobalValue>(ConstantUser) &&
+          --NumRewrittenOperands[ConstantUser] == 0) {
+        RewriteWorklist.push_back(ConstantUser);
       }
+    }
+  };
+
+  // Initialize the worklist with all the placeholders that are ready
+  // to be processed.
+  for (auto ResolveConstant : ResolveConstants) {
+    Constant *MappedC = cast<Constant>(operator[](ResolveConstant.second));
+    if (NumRewrittenOperands.lookup(MappedC)) {
+      // We have a placeholder that resolves to a constant that needs to
+      // be rewritten; note the mapping, and delay processing it.
+      ConstToPlaceholders[MappedC].push_back(ResolveConstant.first);
+    } else {
+      // The placeholder maps directly to the corresponding constant.
+      MapConstant(ResolveConstant.first, MappedC);
+    }
+  }
+  ResolveConstants.clear();
 
-      // Otherwise, we have a constant that uses the placeholder.  Replace that
-      // constant with a new constant that has *all* placeholder uses updated.
-      Constant *UserC = cast<Constant>(U);
-      for (User::op_iterator I = UserC->op_begin(), E = UserC->op_end(); I != E;
-           ++I) {
-        Value *NewOp;
-        if (!isa<ConstantPlaceHolder>(*I)) {
-          // Not a placeholder reference.
-          NewOp = *I;
-        } else if (*I == Placeholder) {
-          // Common case is that it just references this one placeholder.
-          NewOp = RealVal;
-        } else {
-          // Otherwise, look up the placeholder in ResolveConstants.
-          ResolveConstantsTy::iterator It = llvm::lower_bound(
-              ResolveConstants,
-              std::pair<Constant *, unsigned>(cast<Constant>(*I), 0));
-          assert(It != ResolveConstants.end() && It->first == *I);
-          NewOp = operator[](It->second);
-        }
-
-        NewOps.push_back(cast<Constant>(NewOp));
-      }
+  // Construct the new constants.
+  while (!RewriteWorklist.empty()) {
+    Constant *C = RewriteWorklist.pop_back_val();
 
-      // Make the new constant.
-      Constant *NewC;
-      if (ConstantArray *UserCA = dyn_cast<ConstantArray>(UserC)) {
-        NewC = ConstantArray::get(UserCA->getType(), NewOps);
-      } else if (ConstantStruct *UserCS = dyn_cast<ConstantStruct>(UserC)) {
-        NewC = ConstantStruct::get(UserCS->getType(), NewOps);
-      } else if (isa<ConstantVector>(UserC)) {
-        NewC = ConstantVector::get(NewOps);
-      } else {
-        assert(isa<ConstantExpr>(UserC) && "Must be a ConstantExpr.");
-        NewC = cast<ConstantExpr>(UserC)->getWithOperands(NewOps);
-      }
+    // Remap the constant's operands.
+    for (auto &Operand : C->operands()) {
+      Constant *OperandVal = cast<Constant>(Operand);
+      Constant *NewOp = ConstantMapping.lookup(OperandVal);
+      NewOps.push_back(NewOp ? NewOp : OperandVal);
+    }
 
-      UserC->replaceAllUsesWith(NewC);
-      UserC->destroyConstant();
-      NewOps.clear();
+    // Make the new constant.
+    Constant *NewC;
+    if (ConstantArray *CA = dyn_cast<ConstantArray>(C)) {
+      NewC = ConstantArray::get(CA->getType(), NewOps);
+    } else if (ConstantStruct *CS = dyn_cast<ConstantStruct>(C)) {
+      NewC = ConstantStruct::get(CS->getType(), NewOps);
+    } else if (isa<ConstantVector>(C)) {
+      NewC = ConstantVector::get(NewOps);
+    } else {
+      assert(isa<ConstantExpr>(C) && "Must be a ConstantExpr.");
+      NewC = cast<ConstantExpr>(C)->getWithOperands(NewOps);
+    }
+    NewOps.clear();
+
+    // Map this constant, and any placeholders that correspond to this
+    // constant, to the new value.
+    MapConstant(C, NewC);
+    auto Placeholders = ConstToPlaceholders.find(C);
+    if (Placeholders != ConstToPlaceholders.end()) {
+      for (Constant *Placeholder : Placeholders->second)
+        MapConstant(Placeholder, NewC);
     }
+  }
 
-    // Update all ValueHandles, they should be the only users at this point.
-    Placeholder->replaceAllUsesWith(RealVal);
-    delete cast<ConstantPlaceHolder>(Placeholder);
+  for (Constant *C : reverse(RewrittenConstants)) {
+    // We know this constant has no users that are constants: if there were
+    // any such constants, we destroyed them in an earlier iteration.
+    C->replaceAllUsesWith(ConstantMapping.lookup(C));
+    if (auto *Placeholder = dyn_cast<ConstantPlaceHolder>(C))
+      delete Placeholder;
+    else
+      C->destroyConstant();
   }
 }