diff --git a/llvm/lib/Transforms/Utils/SCCPSolver.cpp b/llvm/lib/Transforms/Utils/SCCPSolver.cpp
--- a/llvm/lib/Transforms/Utils/SCCPSolver.cpp
+++ b/llvm/lib/Transforms/Utils/SCCPSolver.cpp
@@ -122,7 +122,8 @@
   DenseSet<Edge> KnownFeasibleEdges;
 
   DenseMap<Function *, AnalysisResultsForFn> AnalysisResults;
-  DenseMap<Value *, SmallPtrSet<User *, 2>> AdditionalUsers;
+  DenseMap<Value *, SmallPtrSet<User *, 8>> AdditionalUsers;
+  DenseMap<User *, SmallPtrSet<Value *, 8>> AdditionalUserOf;
 
   LLVMContext &Ctx;
 
@@ -236,8 +237,8 @@
 
   // Add U as additional user of V.
   void addAdditionalUser(Value *V, User *U) {
-    auto Iter = AdditionalUsers.insert({V, {}});
-    Iter.first->second.insert(U);
+    AdditionalUsers[V].insert(U);
+    AdditionalUserOf[U].insert(V);
   }
 
   // Mark I's users as changed, including AdditionalUsers.
@@ -257,17 +258,10 @@
           operandChangedState(UI);
     }
 
-    auto Iter = AdditionalUsers.find(I);
-    if (Iter != AdditionalUsers.end()) {
-      // Copy additional users before notifying them of changes, because new
-      // users may be added, potentially invalidating the iterator.
-      SmallVector<Instruction *, 2> ToNotify;
-      for (User *U : Iter->second)
-        if (auto *UI = dyn_cast<Instruction>(U))
-          ToNotify.push_back(UI);
-      for (Instruction *UI : ToNotify)
-        operandChangedState(UI);
-    }
+    SmallVector<Instruction *, 8> ToNotify;
+    findAdditionalUsersFor(I, ToNotify);
+    for (Instruction *UI : ToNotify)
+      operandChangedState(UI);
   }
   void handleCallOverdefined(CallBase &CB);
   void handleCallResult(CallBase &CB);
@@ -348,6 +342,36 @@
     return A->second.PredInfo->removePredicateInfoFor(I);
   }
 
+  void removeFromAdditionalUsers(User *U) {
+    auto AUO = AdditionalUserOf.find(U);
+    if (AUO != AdditionalUserOf.end()) {
+      for (Value *V : AUO->second) {
+        auto AU = AdditionalUsers.find(V);
+        if (AU != AdditionalUsers.end())
+          AU->second.erase(U);
+      }
+    }
+  }
+
+  void removeFromAdditionalUserOf(Value *V) {
+    auto AU = AdditionalUsers.find(V);
+    if (AU != AdditionalUsers.end()) {
+      for (User *U : AU->second) {
+        auto AUO = AdditionalUserOf.find(U);
+        if (AUO != AdditionalUserOf.end())
+          AUO->second.erase(V);
+      }
+    }
+  }
+
+  void findAdditionalUsersFor(Value *V, SmallVectorImpl<Instruction *> &Users) {
+    auto Iter = AdditionalUsers.find(V);
+    if (Iter != AdditionalUsers.end())
+      for (User *U : Iter->second)
+        if (auto *I = dyn_cast<Instruction>(U))
+          Users.push_back(I);
+  }
+
   DomTreeUpdater getDTU(Function &F) {
     auto A = AnalysisResults.find(&F);
     assert(A != AnalysisResults.end() && "Need analysis results for function.");