diff --git a/include/llvm/Analysis/InstructionPrecedenceTracking.h b/include/llvm/Analysis/InstructionPrecedenceTracking.h
index b754557..073e6ec 100644
--- a/include/llvm/Analysis/InstructionPrecedenceTracking.h
+++ b/include/llvm/Analysis/InstructionPrecedenceTracking.h
@@ -75,8 +75,14 @@
   virtual ~InstructionPrecedenceTracking() = default;
 
 public:
-  /// Clears cached information about this particular block.
-  void invalidateBlock(const BasicBlock *BB);
+  /// Notifies this tracking that we are going to insert a new instruction \p
+  /// Inst to the basic block \p BB. It makes all necessary updates to internal
+  /// caches to keep them consistent.
+  void insertInstructionTo(const Instruction *Inst, const BasicBlock *BB);
+
+  /// Notifies this tracking that we are going to remove the instruction \p Inst
+  /// It makes all necessary updates to internal caches to keep them consistent.
+  void removeInstruction(const Instruction *Inst);
 
   /// Invalidates all information from this tracking.
   void clear();
diff --git a/include/llvm/Analysis/MustExecute.h b/include/llvm/Analysis/MustExecute.h
index b973447..ad3222c 100644
--- a/include/llvm/Analysis/MustExecute.h
+++ b/include/llvm/Analysis/MustExecute.h
@@ -151,9 +151,9 @@
       const;
 
   /// Inform the safety info that we are planning to insert a new instruction
-  /// into the basic block \p BB. It will make all cache updates to keep it
-  /// correct after this insertion.
-  void insertInstructionTo(const BasicBlock *BB);
+  /// \p Inst into the basic block \p BB. It will make all cache updates to keep
+  /// it correct after this insertion.
+  void insertInstructionTo(const Instruction *Inst, const BasicBlock *BB);
 
   /// Inform safety info that we are planning to remove the instruction \p Inst
   /// from its block. It will make all cache updates to keep it correct after
diff --git a/lib/Analysis/InstructionPrecedenceTracking.cpp b/lib/Analysis/InstructionPrecedenceTracking.cpp
index b98975b..816126f 100644
--- a/lib/Analysis/InstructionPrecedenceTracking.cpp
+++ b/lib/Analysis/InstructionPrecedenceTracking.cpp
@@ -99,9 +99,17 @@
 }
 #endif
 
-void InstructionPrecedenceTracking::invalidateBlock(const BasicBlock *BB) {
+void InstructionPrecedenceTracking::insertInstructionTo(const Instruction *Inst,
+                                                        const BasicBlock *BB) {
+  if (isSpecialInstruction(Inst))
+    FirstSpecialInsts.erase(BB);
   OI.invalidateBlock(BB);
-  FirstSpecialInsts.erase(BB);
+}
+
+void InstructionPrecedenceTracking::removeInstruction(const Instruction *Inst) {
+  if (isSpecialInstruction(Inst))
+    FirstSpecialInsts.erase(Inst->getParent());
+  OI.invalidateBlock(Inst->getParent());
 }
 
 void InstructionPrecedenceTracking::clear() {
diff --git a/lib/Analysis/MustExecute.cpp b/lib/Analysis/MustExecute.cpp
index 281b8f5..180c38d 100644
--- a/lib/Analysis/MustExecute.cpp
+++ b/lib/Analysis/MustExecute.cpp
@@ -83,16 +83,15 @@
   computeBlockColors(CurLoop);
 }
 
-void ICFLoopSafetyInfo::insertInstructionTo(const BasicBlock *BB) {
-  ICF.invalidateBlock(BB);
-  MW.invalidateBlock(BB);
+void ICFLoopSafetyInfo::insertInstructionTo(const Instruction *Inst,
+                                            const BasicBlock *BB) {
+  ICF.insertInstructionTo(Inst, BB);
+  MW.insertInstructionTo(Inst, BB);
 }
 
 void ICFLoopSafetyInfo::removeInstruction(const Instruction *Inst) {
-  // TODO: So far we just conservatively drop cache, but maybe we can not do it
-  // when Inst is not an ICF instruction. Follow-up on that.
-  ICF.invalidateBlock(Inst->getParent());
-  MW.invalidateBlock(Inst->getParent());
+  ICF.removeInstruction(Inst);
+  MW.removeInstruction(Inst);
 }
 
 void LoopSafetyInfo::computeBlockColors(const Loop *CurLoop) {
diff --git a/lib/Transforms/Scalar/GVN.cpp b/lib/Transforms/Scalar/GVN.cpp
index 04ed914..9598e59 100644
--- a/lib/Transforms/Scalar/GVN.cpp
+++ b/lib/Transforms/Scalar/GVN.cpp
@@ -2079,10 +2079,9 @@
       salvageDebugInfo(*I);
       if (MD) MD->removeInstruction(I);
       LLVM_DEBUG(verifyRemoved(I));
+      ICF->removeInstruction(I);
       I->eraseFromParent();
     }
-
-    ICF->invalidateBlock(BB);
     InstrsToErase.clear();
 
     if (AtStart)
@@ -2301,7 +2300,7 @@
   LLVM_DEBUG(verifyRemoved(CurInst));
   // FIXME: Intended to be markInstructionForDeletion(CurInst), but it causes
   // some assertion failures.
-  ICF->invalidateBlock(CurrentBlock);
+  ICF->removeInstruction(CurInst);
   CurInst->eraseFromParent();
   ++NumGVNInstr;
 
diff --git a/lib/Transforms/Scalar/LICM.cpp b/lib/Transforms/Scalar/LICM.cpp
index 5ebf035..3b44ac5 100644
--- a/lib/Transforms/Scalar/LICM.cpp
+++ b/lib/Transforms/Scalar/LICM.cpp
@@ -742,13 +742,13 @@
         auto One = llvm::ConstantFP::get(Divisor->getType(), 1.0);
         auto ReciprocalDivisor = BinaryOperator::CreateFDiv(One, Divisor);
         ReciprocalDivisor->setFastMathFlags(I.getFastMathFlags());
-        SafetyInfo->insertInstructionTo(I.getParent());
+        SafetyInfo->insertInstructionTo(ReciprocalDivisor, I.getParent());
         ReciprocalDivisor->insertBefore(&I);
 
         auto Product =
             BinaryOperator::CreateFMul(I.getOperand(0), ReciprocalDivisor);
         Product->setFastMathFlags(I.getFastMathFlags());
-        SafetyInfo->insertInstructionTo(I.getParent());
+        SafetyInfo->insertInstructionTo(Product, I.getParent());
         Product->insertAfter(&I);
         I.replaceAllUsesWith(Product);
         eraseInstruction(I, *SafetyInfo, CurAST);
@@ -1189,7 +1189,7 @@
 static void moveInstructionBefore(Instruction &I, Instruction &Dest,
                                   ICFLoopSafetyInfo &SafetyInfo) {
   SafetyInfo.removeInstruction(&I);
-  SafetyInfo.insertInstructionTo(Dest.getParent());
+  SafetyInfo.insertInstructionTo(&I, Dest.getParent());
   I.moveBefore(&Dest);
 }