Index: llvm/lib/IR/Value.cpp
===================================================================
--- llvm/lib/IR/Value.cpp
+++ llvm/lib/IR/Value.cpp
@@ -531,6 +531,8 @@
   assert(New->getType() == getType() &&
          "replaceUses of value with new value of different type!");
 
+  SetVector<Constant*> Consts;
+
   for (use_iterator UI = use_begin(), E = use_end(); UI != E;) {
     Use &U = *UI;
     ++UI;
@@ -540,12 +542,18 @@
     // constant because they are uniqued.
     if (auto *C = dyn_cast<Constant>(U.getUser())) {
       if (!isa<GlobalValue>(C)) {
-        C->handleOperandChange(this, New);
+        Consts.insert(C);
         continue;
       }
     }
     U.set(New);
   }
+
+  while (!Consts.empty()) {
+    // FIXME: handleOperandChange() updates all the uses in a given Constant,
+    //        not just the one passed to ShouldReplace
+    Consts.pop_back_val()->handleOperandChange(this, New);
+  }
 }
 
 /// Replace llvm.dbg.* uses of MetadataAsValue(ValueAsMetadata(V)) outside BB