Index: llvm/include/llvm/Transforms/InstCombine/InstCombineWorklist.h
===================================================================
--- llvm/include/llvm/Transforms/InstCombine/InstCombineWorklist.h
+++ llvm/include/llvm/Transforms/InstCombine/InstCombineWorklist.h
@@ -24,8 +24,8 @@
 /// InstCombineWorklist - This is the worklist management logic for
 /// InstCombine.
 class InstCombineWorklist {
-  SmallVector<Instruction*, 256> Worklist;
-  DenseMap<Instruction*, unsigned> WorklistMap;
+  SmallVector<Instruction *, 256> Worklist;
+  DenseMap<Instruction *, unsigned> WorklistMap;
 
 public:
   InstCombineWorklist() = default;
@@ -38,6 +38,9 @@
   /// Add - Add the specified instruction to the worklist if it isn't already
   /// in it.
   void Add(Instruction *I) {
+    assert(I);
+    assert(I->getParent() && "Instruction not inserted yet?");
+
     if (WorklistMap.insert(std::make_pair(I, Worklist.size())).second) {
       LLVM_DEBUG(dbgs() << "IC: ADD: " << *I << '\n');
       Worklist.push_back(I);
@@ -87,8 +90,13 @@
   /// now.
   ///
   void AddUsersToWorkList(Instruction &I) {
-    for (User *U : I.users())
-      Add(cast<Instruction>(U));
+    for (User *U : I.users()) {
+      auto *UI = cast<Instruction>(U);
+      // Do not add instructions that haven't been properly inserted yet.
+      if (UI->getParent()) {
+        Add(UI);
+      }
+    }
   }
 
 
Index: llvm/lib/Transforms/InstCombine/InstructionCombining.cpp
===================================================================
--- llvm/lib/Transforms/InstCombine/InstructionCombining.cpp
+++ llvm/lib/Transforms/InstCombine/InstructionCombining.cpp
@@ -3354,10 +3354,6 @@
         // Move the name to the new instruction first.
         Result->takeName(I);
 
-        // Push the new instruction and any users onto the worklist.
-        Worklist.AddUsersToWorkList(*Result);
-        Worklist.Add(Result);
-
         // Insert the new instruction into the basic block...
         BasicBlock *InstParent = I->getParent();
         BasicBlock::iterator InsertPos = I->getIterator();
@@ -3369,6 +3365,10 @@
 
         InstParent->getInstList().insert(InsertPos, Result);
 
+        // Push the new instruction and any users onto the worklist.
+        Worklist.AddUsersToWorkList(*Result);
+        Worklist.Add(Result);
+
         eraseInstFromFunction(*I);
       } else {
         LLVM_DEBUG(dbgs() << "IC: Mod = " << OrigI << '\n'