Add PassManagerImpl.h to hide implementation details

[rnk]

Summary

ClangBuildAnalyzer results show that a lot of time is spent
instantiating AnalysisManager::getResultImpl across the code base:

**** Templates that took longest to instantiate:
 50445 ms: llvm::AnalysisManager<llvm::Function>::getResultImpl (412 times, avg 122 ms)
 47797 ms: llvm::AnalysisManager<llvm::Function>::getResult<llvm::TargetLibraryAnalysis> (389 times, avg 122 ms)
 46894 ms: std::tie<const unsigned long long, const bool> (2452 times, avg 19 ms)
 43851 ms: llvm::BumpPtrAllocatorImpl<llvm::MallocAllocator, 4096, 4096>::Allocate (3228 times, avg 13 ms)
 33911 ms: std::tie<const unsigned int, const unsigned int, const unsigned int, const unsigned int> (897 times, avg 37 ms)
 33854 ms: std::tie<const unsigned long long, const unsigned long long> (1897 times, avg 17 ms)
 27886 ms: std::basic_string<char, std::char_traits<char>, std::allocator<char> >::basic_string (11156 times, avg 2 ms)

I mentioned this result to @chandlerc, and he suggested this direction.

AnalysisManager is already explicitly instantiated, and getResultImpl
doesn't need to be inlined. Move the definition to an Impl header, and
include that header in files that explicitly instantiate
AnalysisManager. There are only four (real) IR units:

• function
• module
• loop
• cgscc

Looking at a specific transform (ArgumentPromotion.cpp), here are three
compilations before & after this change:

BEFORE:
$ for i in $(seq 3) ; do ./ccit.bat ; done
peak memory: 258.15MB
real: 0m6.297s
peak memory: 257.54MB
real: 0m5.906s
peak memory: 257.47MB
real: 0m6.219s

AFTER:
$ for i in $(seq 3) ; do ./ccit.bat ; done
peak memory: 235.35MB
real: 0m5.454s
peak memory: 234.72MB
real: 0m5.235s
peak memory: 234.39MB
real: 0m5.469s

The 20MB of memory saved seems real, and the time improvement seems like
it is there.

[merge_guards_bot]

Unit tests: pass. 62378 tests passed, 0 failed and 839 were skipped.

clang-tidy: fail. clang-tidy found 0 errors and 1 warnings. 0 of them are added as review comments below (why?).

clang-format: pass.

Build artifacts: diff.json, clang-tidy.txt, clang-format.patch, CMakeCache.txt, console-log.txt, test-results.xml

Pre-merge checks is in beta. Report issue. Please join beta or enable it for your project.

[MaskRay]

include/llvm/IR/PassManager.h is directly included by ~300 files. In most cases the moved functions are not used. Adding PassManagerImpl.h to files (4) that need them sounds good.

[aprantl]

It looks like this may have broken the modules build? Could you take a look?

(To reproduce, pass -DLLVM_ENABLE_MODULES=1 to cmake.)

http://green.lab.llvm.org/green/view/LLDB/job/lldb-cmake/7775/

project/llvm/include/llvm/IR/PassManagerImpl.h:18:
In file included from <module-includes>:1:
/Users/buildslave/jenkins/workspace/lldb-cmake/llvm-project/llvm/include/llvm/IR/Argument.h:19:10: fatal error: cyclic dependency in module 'LLVM_IR': LLVM_IR -> LLVM_intrinsic_gen -> LLVM_IR
#include "llvm/IR/Value.h"
         ^
While building module 'LLVM_IR' imported from /Users/buildslave/jenkins/workspace/lldb-cmake/llvm-project/llvm/lib/IR/DIBuilder.cpp:13:
In file included from <module-includes>:36:
/Users/buildslave/jenkins/workspace/lldb-cmake/llvm-project/llvm/include/llvm/IR/PassManagerImpl.h:18:10: fatal error: could not build module 'LLVM_intrinsic_gen'
#include "llvm/IR/PassManager.h"
 ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
/Users/buildslave/jenkins/workspace/lldb-cmake/llvm-project/llvm/lib/IR/DIBuilder.cpp:13:10: fatal error: could not build module 'LLVM_IR'
#include "llvm/IR/DIBuilder.h"
 ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~
3 errors generated.

[dblaikie]

Any idea why is this class being instantiated/spending a lot of time on that instantiation if it's the subject of an explicit instantiation decl/def?

[dblaikie]

@rsmith - ping, just in case you've got thoughts on whether this should be a compile time performance improvement or a bug/problem in the compiler to be fixed (or something else about the way the source should be structured to avoid the cost)

[rnk]

@aprantl, thanks, I fixed it in a follow-up module.map change: rGf8c4d70d1138.

In D73817#1855806, @dblaikie wrote:

Any idea why is this class being instantiated/spending a lot of time on that instantiation if it's the subject of an explicit instantiation decl/def?

As for why it's instantiated, most TUs instantiate AnalysisManager::getResult. I see 83 files with call sites in lib/Transforms. So, it is actually commonly required functionality. I haven't nailed down if it gets instantiated accidentally just from including PassManager.h. I think the answer is no, but either way this is an improvement.

As for why it's expensive, there are two DenseMaps in AnalysisManager, and this function inserts into both maps. In -ftime-trace, those instantiations happen to be attributed to getResultImpl. It's possible that some of those DenseMapPair & std::pair instantiations happen later anyway after this change, but you can see the memory usage reduction is real.

[dblaikie]

In D73817#1855867, @rnk wrote:

@aprantl, thanks, I fixed it in a follow-up module.map change: rGf8c4d70d1138.

In D73817#1855806, @dblaikie wrote:

Any idea why is this class being instantiated/spending a lot of time on that instantiation if it's the subject of an explicit instantiation decl/def?

As for why it's instantiated, most TUs instantiate AnalysisManager::getResult. I see 83 files with call sites in lib/Transforms. So, it is actually commonly required functionality. I haven't nailed down if it gets instantiated accidentally just from including PassManager.h. I think the answer is no, but either way this is an improvement.

But there's an explicit instantiation declaration, right? Which should prevent any implicit instantiation.

As for why it's expensive, there are two DenseMaps in AnalysisManager, and this function inserts into both maps. In -ftime-trace, those instantiations happen to be attributed to getResultImpl. It's possible that some of those DenseMapPair & std::pair instantiations happen later anyway after this change, but you can see the memory usage reduction is real.

My understanding is that the explicit instantiation declaration should actually make it invalid for the C++ compiler to instantiate the function at all, except where it sees the explicit instantiation definition.

For instance this example:

template<typename T>
void f1() {

typename T::u v;

}
extern template void f1<int>();
int main() {

f1<int>();

}

Successfully compiles because the compiler doesn't instantiate the contents of f1<int> due to the presence of the explicit instantiation declaration. If you add the "inline" keyword to the f1 declaration, then the compiler is allowed to instantiate f1<int> in this TU and it does reject it due to "T::u" being invalid for T=int.

[aprantl]

Thanks a lot, Reid!

[rnk]

In D73817#1855896, @dblaikie wrote:

But there's an explicit instantiation declaration, right? Which should prevent any implicit instantiation.

I think Clang will instantiate the template anyway to make an available_externally definition for optimization purposes.

As for why it's expensive, there are two DenseMaps in AnalysisManager, and this function inserts into both maps. In -ftime-trace, those instantiations happen to be attributed to getResultImpl. It's possible that some of those DenseMapPair & std::pair instantiations happen later anyway after this change, but you can see the memory usage reduction is real.

My understanding is that the explicit instantiation declaration should actually make it invalid for the C++ compiler to instantiate the function at all, except where it sees the explicit instantiation definition.

For instance this example:

template<typename T>
void f1() {

typename T::u v;

}
extern template void f1<int>();
int main() {

f1<int>();

}

Successfully compiles because the compiler doesn't instantiate the contents of f1<int> due to the presence of the explicit instantiation declaration. If you add the "inline" keyword to the f1 declaration, then the compiler is allowed to instantiate f1<int> in this TU and it does reject it due to "T::u" being invalid for T=int.

That's interesting. Clang produces the error if you put the function in a class template:

template <typename T> struct Foo {
  static void f1() { typename T::u v; }
};
extern template struct Foo<int>;
int main() { Foo<int>::f1(); }

It also errors if you add inline:

template <typename T> inline void f1() { typename T::u v; }
extern template void f1<int>();
int main() { f1<int>(); }

I think this proves the theory about available_externally definitions. In other words, extern template isn't as useful as we think it is.

[dblaikie]

In D73817#1858364, @rnk wrote:

In D73817#1855896, @dblaikie wrote:

But there's an explicit instantiation declaration, right? Which should prevent any implicit instantiation.

I think Clang will instantiate the template anyway to make an available_externally definition for optimization purposes.

My understanding is that it's not allowed to do this if the inline keyword is not present (which it doesn't appear to be in this case on any of the functions... oh, right, because they're defined inline so they're implicitly 'inline').

As for why it's expensive, there are two DenseMaps in AnalysisManager, and this function inserts into both maps. In -ftime-trace, those instantiations happen to be attributed to getResultImpl. It's possible that some of those DenseMapPair & std::pair instantiations happen later anyway after this change, but you can see the memory usage reduction is real.

My understanding is that the explicit instantiation declaration should actually make it invalid for the C++ compiler to instantiate the function at all, except where it sees the explicit instantiation definition.

For instance this example:

template<typename T>
void f1() {

typename T::u v;

}
extern template void f1<int>();
int main() {

f1<int>();

}

Successfully compiles because the compiler doesn't instantiate the contents of f1<int> due to the presence of the explicit instantiation declaration. If you add the "inline" keyword to the f1 declaration, then the compiler is allowed to instantiate f1<int> in this TU and it does reject it due to "T::u" being invalid for T=int.

That's interesting. Clang produces the error if you put the function in a class template:

template <typename T> struct Foo {
  static void f1() { typename T::u v; }
};
extern template struct Foo<int>;
int main() { Foo<int>::f1(); }

Ah, right - I missed the implicit inline in class members.

It also errors if you add inline:

template <typename T> inline void f1() { typename T::u v; }
extern template void f1<int>();
int main() { f1<int>(); }

I think this proves the theory about available_externally definitions. In other words, extern template isn't as useful as we think it is.

Except it can only do this if they're 'inline' (implicitly or explicitly), and with optimizations enabled. But if there's no particular benefit to inlining these, I can see the desire to disable that even in optimized builds by having the explicit instantiation.

With that in mind, I believe you could get the same functionality with your patch without splitting into a separate file that would need to be #included in certain places, by putting those definitions outside the class definition (as they are in the separate file) after the class definition in the same file.

This would make it harder to break the build (I believe this change broke some polly compilation - at least I couldn't figure out how to fix it & eventually removed polly from my LLVM_ENABLE_PROJECTS build) by keeping the header standalone/implicitly instantiable, but still getting the compile time benefits of the explicit instantiations

[rnk]

Looks like polly was fixed here: rGd4c8230a0fdbcaf65

I guess I like the current code structure, but I don't feel that strongly about it. Even if moving the code back into the header but moving it out of the class body gets the same compile time benefits, it puts tokens into a widely included header that we don't need. The current structure raises the cost of instantiating new Pass & Analysis managers. You have to try to link, spot the link error, find the symbol, add the include as appropriate. Given how few instantiations (IR units) we expect there to be, it seems like a reasonable tradeoff.

llvm/include/llvm/IR/PassManager.h

private:
 
     SmallDenseMap<AnalysisKey *, bool, 8> &IsResultInvalidated;
     const AnalysisResultMapT &Results;
   };
 
   /// Construct an empty analysis manager.
   ///
   /// If \p DebugLogging is true, we'll log our progress to llvm::dbgs().
-  AnalysisManager(bool DebugLogging = false) : DebugLogging(DebugLogging) {}
-  AnalysisManager(AnalysisManager &&) = default;
-  AnalysisManager &operator=(AnalysisManager &&) = default;
+  AnalysisManager(bool DebugLogging = false);
+  AnalysisManager(AnalysisManager &&);
+  AnalysisManager &operator=(AnalysisManager &&);
 
   /// Returns true if the analysis manager has an empty results cache.
   bool empty() const {
     assert(AnalysisResults.empty() == AnalysisResultLists.empty() &&
            "The storage and index of analysis results disagree on how many "
            "there are!");
     return AnalysisResults.empty();
   }
 
   /// Clear any cached analysis results for a single unit of IR.
   ///
   /// This doesn't invalidate, but instead simply deletes, the relevant results.
   /// It is useful when the IR is being removed and we want to clear out all the
   /// memory pinned for it.
-  void clear(IRUnitT &IR, llvm::StringRef Name) {
-    if (DebugLogging)
-      dbgs() << "Clearing all analysis results for: " << Name << "\n";
-
-    auto ResultsListI = AnalysisResultLists.find(&IR);
-    if (ResultsListI == AnalysisResultLists.end())
-      return;
-    // Delete the map entries that point into the results list.
-    for (auto &IDAndResult : ResultsListI->second)
-      AnalysisResults.erase({IDAndResult.first, &IR});
-
-    // And actually destroy and erase the results associated with this IR.
-    AnalysisResultLists.erase(ResultsListI);
-  }
+  void clear(IRUnitT &IR, llvm::StringRef Name);
 
   /// Clear all analysis results cached by this AnalysisManager.
   ///
   /// Like \c clear(IRUnitT&), this doesn't invalidate the results; it simply
   /// deletes them.  This lets you clean up the AnalysisManager when the set of
   /// IR units itself has potentially changed, and thus we can't even look up a
   /// a result and invalidate/clear it directly.
   void clear() {
assert(AnalysisPasses.count(PassT::ID()) &&
            "This analysis pass was not registered prior to being invalidated");
     invalidateImpl(PassT::ID(), IR);
   }
 
   /// Invalidate cached analyses for an IR unit.
   ///
   /// Walk through all of the analyses pertaining to this unit of IR and
   /// invalidate them, unless they are preserved by the PreservedAnalyses set.
-  void invalidate(IRUnitT &IR, const PreservedAnalyses &PA) {
-    // We're done if all analyses on this IR unit are preserved.
-    if (PA.allAnalysesInSetPreserved<AllAnalysesOn<IRUnitT>>())
-      return;
-
-    if (DebugLogging)
-      dbgs() << "Invalidating all non-preserved analyses for: " << IR.getName()
-             << "\n";
-
-    // Track whether each analysis's result is invalidated in
-    // IsResultInvalidated.
-    SmallDenseMap<AnalysisKey *, bool, 8> IsResultInvalidated;
-    Invalidator Inv(IsResultInvalidated, AnalysisResults);
-    AnalysisResultListT &ResultsList = AnalysisResultLists[&IR];
-    for (auto &AnalysisResultPair : ResultsList) {
-      // This is basically the same thing as Invalidator::invalidate, but we
-      // can't call it here because we're operating on the type-erased result.
-      // Moreover if we instead called invalidate() directly, it would do an
-      // unnecessary look up in ResultsList.
-      AnalysisKey *ID = AnalysisResultPair.first;
-      auto &Result = *AnalysisResultPair.second;
-
-      auto IMapI = IsResultInvalidated.find(ID);
-      if (IMapI != IsResultInvalidated.end())
-        // This result was already handled via the Invalidator.
-        continue;
-
-      // Try to invalidate the result, giving it the Invalidator so it can
-      // recursively query for any dependencies it has and record the result.
-      // Note that we cannot reuse 'IMapI' here or pre-insert the ID, as
-      // Result.invalidate may insert things into the map, invalidating our
-      // iterator.
-      bool Inserted =
-          IsResultInvalidated.insert({ID, Result.invalidate(IR, PA, Inv)})
-              .second;
-      (void)Inserted;
-      assert(Inserted && "Should never have already inserted this ID, likely "
-                         "indicates a cycle!");
-    }
-
-    // Now erase the results that were marked above as invalidated.
-    if (!IsResultInvalidated.empty()) {
-      for (auto I = ResultsList.begin(), E = ResultsList.end(); I != E;) {
-        AnalysisKey *ID = I->first;
-        if (!IsResultInvalidated.lookup(ID)) {
-          ++I;
-          continue;
-        }
-
-        if (DebugLogging)
-          dbgs() << "Invalidating analysis: " << this->lookUpPass(ID).name()
-                 << " on " << IR.getName() << "\n";
-
-        I = ResultsList.erase(I);
-        AnalysisResults.erase({ID, &IR});
-      }
-    }
-
-    if (ResultsList.empty())
-      AnalysisResultLists.erase(&IR);
-  }
+  void invalidate(IRUnitT &IR, const PreservedAnalyses &PA);
 
 private:
   /// Look up a registered analysis pass.
   PassConceptT &lookUpPass(AnalysisKey *ID) {
     typename AnalysisPassMapT::iterator PI = AnalysisPasses.find(ID);
     assert(PI != AnalysisPasses.end() &&
            "Analysis passes must be registered prior to being queried!");
     return *PI->second;
   }
 
   /// Look up a registered analysis pass.
   const PassConceptT &lookUpPass(AnalysisKey *ID) const {
     typename AnalysisPassMapT::const_iterator PI = AnalysisPasses.find(ID);
     assert(PI != AnalysisPasses.end() &&
            "Analysis passes must be registered prior to being queried!");
     return *PI->second;
   }
 
   /// Get an analysis result, running the pass if necessary.
   ResultConceptT &getResultImpl(AnalysisKey *ID, IRUnitT &IR,
-                                ExtraArgTs... ExtraArgs) {
-    typename AnalysisResultMapT::iterator RI;
-    bool Inserted;
-    std::tie(RI, Inserted) = AnalysisResults.insert(std::make_pair(
-        std::make_pair(ID, &IR), typename AnalysisResultListT::iterator()));
-
-    // If we don't have a cached result for this function, look up the pass and
-    // run it to produce a result, which we then add to the cache.
-    if (Inserted) {
-      auto &P = this->lookUpPass(ID);
-      if (DebugLogging)
-        dbgs() << "Running analysis: " << P.name() << " on " << IR.getName()
-               << "\n";
-
-      PassInstrumentation PI;
-      if (ID != PassInstrumentationAnalysis::ID()) {
-        PI = getResult<PassInstrumentationAnalysis>(IR, ExtraArgs...);
-        PI.runBeforeAnalysis(P, IR);
-      }
-
-      AnalysisResultListT &ResultList = AnalysisResultLists[&IR];
-      ResultList.emplace_back(ID, P.run(IR, *this, ExtraArgs...));
-
-      PI.runAfterAnalysis(P, IR);
-
-      // P.run may have inserted elements into AnalysisResults and invalidated
-      // RI.
-      RI = AnalysisResults.find({ID, &IR});
-      assert(RI != AnalysisResults.end() && "we just inserted it!");
-
-      RI->second = std::prev(ResultList.end());
-    }
-
-    return *RI->second->second;
-  }
+                                ExtraArgTs... ExtraArgs);
 
   /// Get a cached analysis result or return null.
   ResultConceptT *getCachedResultImpl(AnalysisKey *ID, IRUnitT &IR) const {
     typename AnalysisResultMapT::const_iterator RI =
         AnalysisResults.find({ID, &IR});
     return RI == AnalysisResults.end() ? nullptr : &*RI->second->second;
   }
 

llvm/include/llvm/IR/PassManagerImpl.h

+//===- PassManagerImpl.h - Pass management infrastructure -------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+///
+/// Provides implementations for PassManager and AnalysisManager template
+/// methods. These classes should be explicitly instantiated for any IR unit,
+/// and files doing the explicit instantiation should include this header.
+///
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_IR_PASSMANAGERIMPL_H
+#define LLVM_IR_PASSMANAGERIMPL_H
+
+#include "llvm/IR/PassManager.h"
+
+namespace llvm {
+
+template <typename IRUnitT, typename... ExtraArgTs>
+inline AnalysisManager<IRUnitT, ExtraArgTs...>::AnalysisManager(
+    bool DebugLogging)
+    : DebugLogging(DebugLogging) {}
+
+template <typename IRUnitT, typename... ExtraArgTs>
+inline AnalysisManager<IRUnitT, ExtraArgTs...>::AnalysisManager(
+    AnalysisManager &&) = default;
+
+template <typename IRUnitT, typename... ExtraArgTs>
+inline AnalysisManager<IRUnitT, ExtraArgTs...> &
+AnalysisManager<IRUnitT, ExtraArgTs...>::operator=(AnalysisManager &&) =
+    default;
+
+template <typename IRUnitT, typename... ExtraArgTs>
+inline void
+AnalysisManager<IRUnitT, ExtraArgTs...>::clear(IRUnitT &IR,
+                                               llvm::StringRef Name) {
+  if (DebugLogging)
+    dbgs() << "Clearing all analysis results for: " << Name << "\n";
+
+  auto ResultsListI = AnalysisResultLists.find(&IR);
+  if (ResultsListI == AnalysisResultLists.end())
+    return;
+  // Delete the map entries that point into the results list.
+  for (auto &IDAndResult : ResultsListI->second)
+    AnalysisResults.erase({IDAndResult.first, &IR});
+
+  // And actually destroy and erase the results associated with this IR.
+  AnalysisResultLists.erase(ResultsListI);
+}
+
+template <typename IRUnitT, typename... ExtraArgTs>
+inline typename AnalysisManager<IRUnitT, ExtraArgTs...>::ResultConceptT &
+AnalysisManager<IRUnitT, ExtraArgTs...>::getResultImpl(
+    AnalysisKey *ID, IRUnitT &IR, ExtraArgTs... ExtraArgs) {
+  typename AnalysisResultMapT::iterator RI;
+  bool Inserted;
+  std::tie(RI, Inserted) = AnalysisResults.insert(std::make_pair(
+      std::make_pair(ID, &IR), typename AnalysisResultListT::iterator()));
+
+  // If we don't have a cached result for this function, look up the pass and
+  // run it to produce a result, which we then add to the cache.
+  if (Inserted) {
+    auto &P = this->lookUpPass(ID);
+    if (DebugLogging)
+      dbgs() << "Running analysis: " << P.name() << " on " << IR.getName()
+             << "\n";
+
+    PassInstrumentation PI;
+    if (ID != PassInstrumentationAnalysis::ID()) {
+      PI = getResult<PassInstrumentationAnalysis>(IR, ExtraArgs...);
+      PI.runBeforeAnalysis(P, IR);
+    }
+
+    AnalysisResultListT &ResultList = AnalysisResultLists[&IR];
+    ResultList.emplace_back(ID, P.run(IR, *this, ExtraArgs...));
+
+    PI.runAfterAnalysis(P, IR);
+
+    // P.run may have inserted elements into AnalysisResults and invalidated
+    // RI.
+    RI = AnalysisResults.find({ID, &IR});
+    assert(RI != AnalysisResults.end() && "we just inserted it!");
+
+    RI->second = std::prev(ResultList.end());
+  }
+
+  return *RI->second->second;
+}
+
+template <typename IRUnitT, typename... ExtraArgTs>
+inline void AnalysisManager<IRUnitT, ExtraArgTs...>::invalidate(
+    IRUnitT &IR, const PreservedAnalyses &PA) {
+  // We're done if all analyses on this IR unit are preserved.
+  if (PA.allAnalysesInSetPreserved<AllAnalysesOn<IRUnitT>>())
+    return;
+
+  if (DebugLogging)
+    dbgs() << "Invalidating all non-preserved analyses for: " << IR.getName()
+           << "\n";
+
+  // Track whether each analysis's result is invalidated in
+  // IsResultInvalidated.
+  SmallDenseMap<AnalysisKey *, bool, 8> IsResultInvalidated;
+  Invalidator Inv(IsResultInvalidated, AnalysisResults);
+  AnalysisResultListT &ResultsList = AnalysisResultLists[&IR];
+  for (auto &AnalysisResultPair : ResultsList) {
+    // This is basically the same thing as Invalidator::invalidate, but we
+    // can't call it here because we're operating on the type-erased result.
+    // Moreover if we instead called invalidate() directly, it would do an
+    // unnecessary look up in ResultsList.
+    AnalysisKey *ID = AnalysisResultPair.first;
+    auto &Result = *AnalysisResultPair.second;
+
+    auto IMapI = IsResultInvalidated.find(ID);
+    if (IMapI != IsResultInvalidated.end())
+      // This result was already handled via the Invalidator.
+      continue;
+
+    // Try to invalidate the result, giving it the Invalidator so it can
+    // recursively query for any dependencies it has and record the result.
+    // Note that we cannot reuse 'IMapI' here or pre-insert the ID, as
+    // Result.invalidate may insert things into the map, invalidating our
+    // iterator.
+    bool Inserted =
+        IsResultInvalidated.insert({ID, Result.invalidate(IR, PA, Inv)}).second;
+    (void)Inserted;
+    assert(Inserted && "Should never have already inserted this ID, likely "
+                       "indicates a cycle!");
+  }
+
+  // Now erase the results that were marked above as invalidated.
+  if (!IsResultInvalidated.empty()) {
+    for (auto I = ResultsList.begin(), E = ResultsList.end(); I != E;) {
+      AnalysisKey *ID = I->first;
+      if (!IsResultInvalidated.lookup(ID)) {
+        ++I;
+        continue;
+      }
+
+      if (DebugLogging)
+        dbgs() << "Invalidating analysis: " << this->lookUpPass(ID).name()
+               << " on " << IR.getName() << "\n";
+
+      I = ResultsList.erase(I);
+      AnalysisResults.erase({ID, &IR});
+    }
+  }
+
+  if (ResultsList.empty())
+    AnalysisResultLists.erase(&IR);
+}
+} // end namespace llvm
+
+#endif // LLVM_IR_PASSMANAGERIMPL_H

llvm/lib/Analysis/CGSCCPassManager.cpp

 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/iterator_range.h"
 #include "llvm/Analysis/LazyCallGraph.h"
 #include "llvm/IR/CallSite.h"
 #include "llvm/IR/Constant.h"
 #include "llvm/IR/InstIterator.h"
 #include "llvm/IR/Instruction.h"
 #include "llvm/IR/PassManager.h"
+#include "llvm/IR/PassManagerImpl.h"
 #include "llvm/Support/Casting.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
 #include <algorithm>
 #include <cassert>
 #include <iterator>
 
 #define DEBUG_TYPE "cgscc"

llvm/lib/Analysis/LoopAnalysisManager.cpp

 //===- LoopAnalysisManager.cpp - Loop analysis management -----------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Analysis/LoopAnalysisManager.h"
 #include "llvm/Analysis/BasicAliasAnalysis.h"
 #include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/MemorySSA.h"
 #include "llvm/Analysis/ScalarEvolution.h"
 #include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"
 #include "llvm/IR/Dominators.h"
+#include "llvm/IR/PassManagerImpl.h"
 
 using namespace llvm;
 
 namespace llvm {
 // Explicit template instantiations and specialization definitions for core
 // template typedefs.
 template class AllAnalysesOn<Loop>;
 template class AnalysisManager<Loop, LoopStandardAnalysisResults &>;

llvm/lib/IR/PassManager.cpp

 //===- PassManager.cpp - Infrastructure for managing & running IR passes --===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/IR/PassManager.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/IR/LLVMContext.h"
+#include "llvm/IR/PassManagerImpl.h"
 
 using namespace llvm;
 
 // Explicit template instantiations and specialization defininitions for core
 // template typedefs.
 namespace llvm {
 template class AllAnalysesOn<Module>;
 template class AllAnalysesOn<Function>;

llvm/unittests/IR/PassManagerTest.cpp

 //===- llvm/unittest/IR/PassManager.cpp - PassManager tests ---------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/IR/PassManager.h"
 #include "llvm/AsmParser/Parser.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/Module.h"
+#include "llvm/IR/PassManagerImpl.h"
 #include "llvm/Support/SourceMgr.h"
 #include "gtest/gtest.h"
 
 using namespace llvm;
 
 namespace {
 
 class TestFunctionAnalysis : public AnalysisInfoMixin<TestFunctionAnalysis> {