Index: include/polly/ScopInfo.h
===================================================================
--- include/polly/ScopInfo.h
+++ include/polly/ScopInfo.h
@@ -621,6 +621,9 @@
   /// Isl context.
   isl_ctx *IslCtx;
 
+  /// @brief A map from basic blocks to SCoP statements.
+  DenseMap<BasicBlock *, ScopStmt *> StmtMap;
+
   /// Constraints on parameters.
   isl_set *Context;
 
@@ -800,6 +803,9 @@
   /// @brief Get an isl string representing the assumed context.
   std::string getAssumedContextStr() const;
 
+  /// @brief Return the stmt for the given @p BB or nullptr if none.
+  ScopStmt *getStmtForBasicBlock(BasicBlock *BB) const;
+
   /// @name Statements Iterators
   ///
   /// These iterators iterate over all statements of this Scop.
Index: lib/Analysis/ScopInfo.cpp
===================================================================
--- lib/Analysis/ScopInfo.cpp
+++ lib/Analysis/ScopInfo.cpp
@@ -1722,8 +1722,12 @@
       if (isTrivialBB(BB, tempScop))
         continue;
 
-      Stmts.push_back(
-          new ScopStmt(*this, tempScop, CurRegion, *BB, NestLoops, Scatter));
+      ScopStmt *Stmt =
+          new ScopStmt(*this, tempScop, CurRegion, *BB, NestLoops, Scatter);
+
+      // Insert all statements into the statement map and the statement vector.
+      StmtMap[BB] = Stmt;
+      Stmts.push_back(Stmt);
 
       // Increasing the Scattering function is OK for the moment, because
       // we are using a depth first iterator and the program is well structured.
@@ -1739,6 +1743,13 @@
   ++Scatter[loopDepth - 1];
 }
 
+ScopStmt *Scop::getStmtForBasicBlock(BasicBlock *BB) const {
+  const auto &StmtMapIt = StmtMap.find(BB);
+  if (StmtMapIt == StmtMap.end())
+    return nullptr;
+  return StmtMapIt->second;
+}
+
 //===----------------------------------------------------------------------===//
 ScopInfo::ScopInfo() : RegionPass(ID), scop(0) {
   ctx = isl_ctx_alloc();
Index: lib/Support/ScopHelper.cpp
===================================================================
--- lib/Support/ScopHelper.cpp
+++ lib/Support/ScopHelper.cpp
@@ -88,11 +88,8 @@
 
 static void replaceScopAndRegionEntry(polly::Scop *S, BasicBlock *OldEntry,
                                       BasicBlock *NewEntry) {
-  for (polly::ScopStmt *Stmt : *S)
-    if (Stmt->getBasicBlock() == OldEntry) {
-      Stmt->setBasicBlock(NewEntry);
-      break;
-    }
+  if (polly::ScopStmt *Stmt = S->getStmtForBasicBlock(OldEntry))
+    Stmt->setBasicBlock(NewEntry);
 
   S->getRegion().replaceEntryRecursive(NewEntry);
 }