Index: include/llvm/Analysis/InstructionPrecedenceTracking.h
===================================================================
--- include/llvm/Analysis/InstructionPrecedenceTracking.h
+++ include/llvm/Analysis/InstructionPrecedenceTracking.h
@@ -75,9 +75,15 @@
   virtual ~InstructionPrecedenceTracking() = default;
 
 public:
-  /// Clears cached information about this particular block.
+  /// Clears cached information about this particular block. We need to do it
+  /// whenever we plan to modify blocks contents in a way that may change the
+  /// first special instruction in the block.
   void invalidateBlock(const BasicBlock *BB);
 
+  /// Inform the tracking that we are going to remove or modify the instuction
+  /// \p Insn. It will do the required invalidation if needed.
+  void invalidateInstruction(const Instruction *Insn);
+
   /// Invalidates all information from this tracking.
   void clear();
 };
Index: lib/Analysis/InstructionPrecedenceTracking.cpp
===================================================================
--- lib/Analysis/InstructionPrecedenceTracking.cpp
+++ lib/Analysis/InstructionPrecedenceTracking.cpp
@@ -103,6 +103,20 @@
   FirstSpecialInsts.erase(BB);
 }
 
+void
+InstructionPrecedenceTracking::invalidateInstruction(const Instruction *Insn) {
+  // If we keep track of Insn, drop the cached info for it.
+  if (!isSpecialInstruction(Insn))
+    return;
+
+  auto It = FirstSpecialInsts.find(Insn->getParent());
+  if (It == FirstSpecialInsts.end())
+    return;
+
+  if (It->second == Insn)
+    FirstSpecialInsts.erase(It);
+}
+
 void InstructionPrecedenceTracking::clear() {
   FirstSpecialInsts.clear();
 #ifndef NDEBUG