diff --git a/include/polly/ScopInfo.h b/include/polly/ScopInfo.h
index b6fcddc..7b6f136 100644
--- a/include/polly/ScopInfo.h
+++ b/include/polly/ScopInfo.h
@@ -1539,9 +1539,7 @@
 
   /// Set the list of instructions for this statement. It replaces the current
   /// list.
-  void setInstructions(ArrayRef<Instruction *> Range) {
-    Instructions.assign(Range.begin(), Range.end());
-  }
+  void setInstructions(ArrayRef<Instruction *> Range);
 
   std::vector<Instruction *>::const_iterator insts_begin() const {
     return Instructions.begin();
@@ -1949,7 +1947,7 @@
   void addScopStmt(Region *R, StringRef Name, Loop *SurroundingLoop,
                    std::vector<Instruction *> EntryBlockInstructions);
 
-  /// Removes @p Stmt from the StmtMap.
+  /// Removes @p Stmt from the StmtMap and InstStmtMap.
   void removeFromStmtMap(ScopStmt &Stmt);
 
   /// Removes all statements where the entry block of the statement does not
@@ -2362,6 +2360,12 @@
     return InstStmtMap.lookup(Inst);
   }
 
+  /// Update the content of InstStmtMap for @p Stmt. @p OldList contains the
+  /// previous instructions in @p Stmt and is updated to contain the
+  /// instructions in @p NewList.
+  void updateInstStmtMap(ArrayRef<Instruction *> OldList,
+                         ArrayRef<Instruction *> NewList, ScopStmt *Stmt);
+
   /// Return the number of statements in the SCoP.
   size_t getSize() const { return Stmts.size(); }
 
diff --git a/lib/Analysis/ScopInfo.cpp b/lib/Analysis/ScopInfo.cpp
index fdb06be..da3e618 100644
--- a/lib/Analysis/ScopInfo.cpp
+++ b/lib/Analysis/ScopInfo.cpp
@@ -1249,6 +1249,11 @@
 
 unsigned ScopStmt::getNumIterators() const { return NestLoops.size(); }
 
+void ScopStmt::setInstructions(ArrayRef<Instruction *> Range) {
+  getParent()->updateInstStmtMap(Instructions, Range, this);
+  Instructions.assign(Range.begin(), Range.end());
+}
+
 const char *ScopStmt::getBaseName() const { return BaseName.c_str(); }
 
 Loop *ScopStmt::getLoopForDimension(unsigned Dimension) const {
@@ -1728,8 +1733,10 @@
 Scop::~Scop() = default;
 
 void Scop::removeFromStmtMap(ScopStmt &Stmt) {
-  for (Instruction *Inst : Stmt.getInstructions())
+  for (Instruction *Inst : Stmt.getInstructions()) {
+    assert(!InstStmtMap.count(Inst) || InstStmtMap.lookup(Inst) == &Stmt);
     InstStmtMap.erase(Inst);
+  }
 
   if (Stmt.isRegionStmt()) {
     for (BasicBlock *BB : Stmt.getRegion()->blocks()) {
@@ -1738,8 +1745,10 @@
       // part of the statement's instruction list.
       if (BB == Stmt.getEntryBlock())
         continue;
-      for (Instruction &Inst : *BB)
+      for (Instruction &Inst : *BB) {
+        assert(!InstStmtMap.count(&Inst) || InstStmtMap.lookup(&Inst) == &Stmt);
         InstStmtMap.erase(&Inst);
+      }
     }
   } else {
     auto StmtMapIt = StmtMap.find(Stmt.getBasicBlock());
@@ -1747,9 +1756,16 @@
       StmtMapIt->second.erase(std::remove(StmtMapIt->second.begin(),
                                           StmtMapIt->second.end(), &Stmt),
                               StmtMapIt->second.end());
-    for (Instruction *Inst : Stmt.getInstructions())
+    for (Instruction *Inst : Stmt.getInstructions()) {
+      assert(!InstStmtMap.count(Inst) || InstStmtMap.lookup(Inst) == &Stmt);
       InstStmtMap.erase(Inst);
+    }
   }
+
+#ifndef NDEBUG
+  for (auto kv : InstStmtMap)
+    assert(kv.getSecond() != &Stmt);
+#endif
 }
 
 void Scop::removeStmts(std::function<bool(ScopStmt &)> ShouldDelete,
@@ -2471,6 +2487,19 @@
   return getStmtListFor(R->getEntry());
 }
 
+void Scop::updateInstStmtMap(ArrayRef<Instruction *> OldList,
+                             ArrayRef<Instruction *> NewList, ScopStmt *Stmt) {
+  for (Instruction *OldInst : OldList) {
+    assert(getStmtFor(OldInst) == Stmt);
+    InstStmtMap.erase(OldInst);
+  }
+
+  for (Instruction *NewInst : NewList) {
+    assert(InstStmtMap.lookup(NewInst) == nullptr);
+    InstStmtMap[NewInst] = Stmt;
+  }
+}
+
 int Scop::getRelativeLoopDepth(const Loop *L) const {
   if (!L || !R.contains(L))
     return -1;