Index: flang/include/flang/Parser/provenance.h
===================================================================
--- flang/include/flang/Parser/provenance.h
+++ flang/include/flang/Parser/provenance.h
@@ -298,17 +298,5 @@
   std::map<CharBlock, const CookedSource &, CharBlockPointerComparator> index_;
 };
 
-// For use as a Comparator for maps, sets, sorting, &c.
-class CharBlockComparator {
-public:
-  explicit CharBlockComparator(const AllCookedSources &all) : all_{all} {}
-  bool operator()(CharBlock x, CharBlock y) const {
-    return all_.Precedes(x, y);
-  }
-
-private:
-  const AllCookedSources &all_;
-};
-
 } // namespace Fortran::parser
 #endif // FORTRAN_PARSER_PROVENANCE_H_
Index: flang/include/flang/Semantics/scope.h
===================================================================
--- flang/include/flang/Semantics/scope.h
+++ flang/include/flang/Semantics/scope.h
@@ -249,9 +249,6 @@
   // The range of the source of this and nested scopes.
   const parser::CharBlock &sourceRange() const { return sourceRange_; }
   void AddSourceRange(parser::CharBlock);
-  // Find the smallest scope under this one that contains source
-  const Scope *FindScope(parser::CharBlock) const;
-  Scope *FindScope(parser::CharBlock);
 
   // Attempts to find a match for a derived type instance
   const DeclTypeSpec *FindInstantiatedDerivedType(const DerivedTypeSpec &,
Index: flang/include/flang/Semantics/semantics.h
===================================================================
--- flang/include/flang/Semantics/semantics.h
+++ flang/include/flang/Semantics/semantics.h
@@ -185,6 +185,7 @@
 
   const Scope &FindScope(parser::CharBlock) const;
   Scope &FindScope(parser::CharBlock);
+  void UpdateScopeIndex(Scope &, parser::CharBlock);
 
   bool IsInModuleFile(parser::CharBlock) const;
 
@@ -250,6 +251,13 @@
   CommonBlockList GetCommonBlocks() const;
 
 private:
+  struct ScopeIndexComparator {
+    bool operator()(parser::CharBlock, parser::CharBlock) const;
+  };
+  using ScopeIndex =
+      std::multimap<parser::CharBlock, Scope &, ScopeIndexComparator>;
+  ScopeIndex::iterator SearchScopeIndex(parser::CharBlock);
+
   void CheckIndexVarRedefine(
       const parser::CharBlock &, const Symbol &, parser::MessageFixedText &&);
   void CheckError(const Symbol &);
@@ -269,6 +277,7 @@
   evaluate::TargetCharacteristics targetCharacteristics_;
   Scope globalScope_;
   Scope &intrinsicModulesScope_;
+  ScopeIndex scopeIndex_;
   parser::Messages messages_;
   evaluate::FoldingContext foldingContext_;
   ConstructStack constructStack_;
Index: flang/lib/Semantics/check-io.cpp
===================================================================
--- flang/lib/Semantics/check-io.cpp
+++ flang/lib/Semantics/check-io.cpp
@@ -1036,12 +1036,9 @@
 
 void IoChecker::CheckForPureSubprogram() const { // C1597
   CHECK(context_.location());
-  if (const Scope *
-      scope{context_.globalScope().FindScope(*context_.location())}) {
-    if (FindPureProcedureContaining(*scope)) {
-      context_.Say(
-          "External I/O is not allowed in a pure subprogram"_err_en_US);
-    }
+  const Scope &scope{context_.FindScope(*context_.location())};
+  if (FindPureProcedureContaining(scope)) {
+    context_.Say("External I/O is not allowed in a pure subprogram"_err_en_US);
   }
 }
 
Index: flang/lib/Semantics/scope.cpp
===================================================================
--- flang/lib/Semantics/scope.cpp
+++ flang/lib/Semantics/scope.cpp
@@ -304,23 +304,6 @@
   }
 }
 
-const Scope *Scope::FindScope(parser::CharBlock source) const {
-  return const_cast<Scope *>(this)->FindScope(source);
-}
-
-Scope *Scope::FindScope(parser::CharBlock source) {
-  bool isContained{sourceRange_.Contains(source)};
-  if (!isContained && !IsTopLevel() && kind_ != Kind::Module) {
-    return nullptr;
-  }
-  for (auto &child : children_) {
-    if (auto *scope{child.FindScope(source)}) {
-      return scope;
-    }
-  }
-  return isContained && !IsTopLevel() ? this : nullptr;
-}
-
 void Scope::AddSourceRange(parser::CharBlock source) {
   if (source.empty()) {
     return;
@@ -334,10 +317,14 @@
   for (auto *scope{this}; !scope->IsTopLevel(); scope = &scope->parent()) {
     CHECK(scope->sourceRange_.empty() == (scope->cookedSource_ == nullptr));
     if (!scope->cookedSource_) {
+      context_.UpdateScopeIndex(*scope, source);
       scope->cookedSource_ = cooked;
       scope->sourceRange_ = source;
     } else if (scope->cookedSource_ == cooked) {
-      scope->sourceRange_.ExtendToCover(source);
+      auto combined{scope->sourceRange()};
+      combined.ExtendToCover(source);
+      context_.UpdateScopeIndex(*scope, combined);
+      scope->sourceRange_ = combined;
     } else {
       // There's a bug that will be hard to fix; crash informatively
       const parser::AllSources &allSources{allCookedSources.allSources()};
@@ -361,6 +348,12 @@
                   "source files \"%s\" and \"%s\"",
           scopeDesc.c_str(), newDesc.c_str());
     }
+    // Note: If the "break;" here were unconditional (or, equivalently, if
+    // there were no loop at all) then the source ranges of parent scopes
+    // would not enclose the source ranges of their children.  Timing
+    // shows that it's cheap to maintain this property, with the exceptions
+    // of top-level scopes and for (sub)modules and their descendant
+    // submodules.
     if (scope->IsSubmodule()) {
       break; // Submodules are child scopes but not contained ranges
     }
Index: flang/lib/Semantics/semantics.cpp
===================================================================
--- flang/lib/Semantics/semantics.cpp
+++ flang/lib/Semantics/semantics.cpp
@@ -355,13 +355,34 @@
   }
 }
 
+bool SemanticsContext::ScopeIndexComparator::operator()(
+    parser::CharBlock x, parser::CharBlock y) const {
+  return x.begin() < y.begin() ||
+      (x.begin() == y.begin() && x.size() > y.size());
+}
+
+auto SemanticsContext::SearchScopeIndex(parser::CharBlock source)
+    -> ScopeIndex::iterator {
+  if (!scopeIndex_.empty()) {
+    auto iter{scopeIndex_.upper_bound(source)};
+    auto begin{scopeIndex_.begin()};
+    do {
+      --iter;
+      if (iter->first.Contains(source)) {
+        return iter;
+      }
+    } while (iter != begin);
+  }
+  return scopeIndex_.end();
+}
+
 const Scope &SemanticsContext::FindScope(parser::CharBlock source) const {
   return const_cast<SemanticsContext *>(this)->FindScope(source);
 }
 
 Scope &SemanticsContext::FindScope(parser::CharBlock source) {
-  if (auto *scope{globalScope_.FindScope(source)}) {
-    return *scope;
+  if (auto iter{SearchScopeIndex(source)}; iter != scopeIndex_.end()) {
+    return iter->second;
   } else {
     common::die(
         "SemanticsContext::FindScope(): invalid source location for '%s'",
@@ -369,6 +390,22 @@
   }
 }
 
+void SemanticsContext::UpdateScopeIndex(
+    Scope &scope, parser::CharBlock newSource) {
+  if (scope.sourceRange().empty()) {
+    scopeIndex_.emplace(newSource, scope);
+  } else if (!scope.sourceRange().Contains(newSource)) {
+    auto iter{SearchScopeIndex(scope.sourceRange())};
+    CHECK(iter != scopeIndex_.end());
+    while (&iter->second != &scope) {
+      CHECK(iter != scopeIndex_.begin());
+      --iter;
+    }
+    scopeIndex_.erase(iter);
+    scopeIndex_.emplace(newSource, scope);
+  }
+}
+
 bool SemanticsContext::IsInModuleFile(parser::CharBlock source) const {
   for (const Scope *scope{&FindScope(source)}; !scope->IsGlobal();
        scope = &scope->parent()) {