[PM] Add a new-PM-style CGSCC pass manager using the newly added

LazyCallGraph analysis framework. Wire it up all the way through the opt
driver and add some very basic testing that we can build pass pipelines
including these components. Still a lot more to do in terms of testing
that all of this works, but the basic pieces are here.

There is a *lot* of boiler plate here. It's something I'm going to
actively look at reducing, but I don't have any immediate ideas that
don't end up making the code terribly complex in order to fold away the
boilerplate. Until I figure out something to minimize the boilerplate,
almost all of this is based on the code for the existing pass managers,
copied and heavily adjusted to suit the needs of the CGSCC pass
management layer.

The actual CG management still has a bunch of FIXMEs in it. Notably, we
don't do *any* updating of the CG as it is potentially invalidated.
I wanted to get this in place to motivate the new analysis, and add
update APIs to the analysis and the pass management layers in concert to
make sure that the *right* APIs are present.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@206745 91177308-0d34-0410-b5e6-96231b3b80d8

1 files changed, 167 insertions, 0 deletions

diff --git a/lib/Analysis/CGSCCPassManager.cpp b/lib/Analysis/CGSCCPassManager.cpp
new file mode 100644
index 0000000000..5d1d8a9c6e
--- /dev/null
+++ b/lib/Analysis/CGSCCPassManager.cpp
@@ -0,0 +1,167 @@
+//===- CGSCCPassManager.cpp - Managing & running CGSCC passes -------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Analysis/CGSCCPassManager.h"
+#include "llvm/Support/CommandLine.h"
+#include "llvm/Support/Debug.h"
+
+using namespace llvm;
+
+static cl::opt<bool>
+DebugPM("debug-cgscc-pass-manager", cl::Hidden,
+        cl::desc("Print CGSCC pass management debugging information"));
+
+PreservedAnalyses CGSCCPassManager::run(LazyCallGraph::SCC *C,
+                                        CGSCCAnalysisManager *AM) {
+  PreservedAnalyses PA = PreservedAnalyses::all();
+
+  if (DebugPM)
+    dbgs() << "Starting CGSCC pass manager run.\n";
+
+  for (unsigned Idx = 0, Size = Passes.size(); Idx != Size; ++Idx) {
+    if (DebugPM)
+      dbgs() << "Running CGSCC pass: " << Passes[Idx]->name() << "\n";
+
+    PreservedAnalyses PassPA = Passes[Idx]->run(C, AM);
+    if (AM)
+      AM->invalidate(C, PassPA);
+    PA.intersect(std::move(PassPA));
+  }
+
+  if (DebugPM)
+    dbgs() << "Finished CGSCC pass manager run.\n";
+
+  return PA;
+}
+
+bool CGSCCAnalysisManager::empty() const {
+  assert(CGSCCAnalysisResults.empty() == CGSCCAnalysisResultLists.empty() &&
+         "The storage and index of analysis results disagree on how many there "
+         "are!");
+  return CGSCCAnalysisResults.empty();
+}
+
+void CGSCCAnalysisManager::clear() {
+  CGSCCAnalysisResults.clear();
+  CGSCCAnalysisResultLists.clear();
+}
+
+CGSCCAnalysisManager::ResultConceptT &
+CGSCCAnalysisManager::getResultImpl(void *PassID, LazyCallGraph::SCC *C) {
+  CGSCCAnalysisResultMapT::iterator RI;
+  bool Inserted;
+  std::tie(RI, Inserted) = CGSCCAnalysisResults.insert(std::make_pair(
+      std::make_pair(PassID, C), CGSCCAnalysisResultListT::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) {
+    CGSCCAnalysisResultListT &ResultList = CGSCCAnalysisResultLists[C];
+    ResultList.emplace_back(PassID, lookupPass(PassID).run(C, this));
+    RI->second = std::prev(ResultList.end());
+  }
+
+  return *RI->second->second;
+}
+
+CGSCCAnalysisManager::ResultConceptT *
+CGSCCAnalysisManager::getCachedResultImpl(void *PassID,
+                                          LazyCallGraph::SCC *C) const {
+  CGSCCAnalysisResultMapT::const_iterator RI =
+      CGSCCAnalysisResults.find(std::make_pair(PassID, C));
+  return RI == CGSCCAnalysisResults.end() ? nullptr : &*RI->second->second;
+}
+
+void CGSCCAnalysisManager::invalidateImpl(void *PassID, LazyCallGraph::SCC *C) {
+  CGSCCAnalysisResultMapT::iterator RI =
+      CGSCCAnalysisResults.find(std::make_pair(PassID, C));
+  if (RI == CGSCCAnalysisResults.end())
+    return;
+
+  CGSCCAnalysisResultLists[C].erase(RI->second);
+}
+
+void CGSCCAnalysisManager::invalidateImpl(LazyCallGraph::SCC *C,
+                                          const PreservedAnalyses &PA) {
+  // Clear all the invalidated results associated specifically with this
+  // function.
+  SmallVector<void *, 8> InvalidatedPassIDs;
+  CGSCCAnalysisResultListT &ResultsList = CGSCCAnalysisResultLists[C];
+  for (CGSCCAnalysisResultListT::iterator I = ResultsList.begin(),
+                                          E = ResultsList.end();
+       I != E;)
+    if (I->second->invalidate(C, PA)) {
+      InvalidatedPassIDs.push_back(I->first);
+      I = ResultsList.erase(I);
+    } else {
+      ++I;
+    }
+  while (!InvalidatedPassIDs.empty())
+    CGSCCAnalysisResults.erase(
+        std::make_pair(InvalidatedPassIDs.pop_back_val(), C));
+  CGSCCAnalysisResultLists.erase(C);
+}
+
+char CGSCCAnalysisManagerModuleProxy::PassID;
+
+CGSCCAnalysisManagerModuleProxy::Result
+CGSCCAnalysisManagerModuleProxy::run(Module *M) {
+  assert(CGAM->empty() && "CGSCC analyses ran prior to the module proxy!");
+  return Result(*CGAM);
+}
+
+CGSCCAnalysisManagerModuleProxy::Result::~Result() {
+  // Clear out the analysis manager if we're being destroyed -- it means we
+  // didn't even see an invalidate call when we got invalidated.
+  CGAM->clear();
+}
+
+bool CGSCCAnalysisManagerModuleProxy::Result::invalidate(
+    Module *M, const PreservedAnalyses &PA) {
+  // If this proxy isn't marked as preserved, then we can't even invalidate
+  // individual CGSCC analyses, there may be an invalid set of SCC objects in
+  // the cache making it impossible to incrementally preserve them.
+  // Just clear the entire manager.
+  if (!PA.preserved(ID()))
+    CGAM->clear();
+
+  // Return false to indicate that this result is still a valid proxy.
+  return false;
+}
+
+char ModuleAnalysisManagerCGSCCProxy::PassID;
+
+char FunctionAnalysisManagerCGSCCProxy::PassID;
+
+FunctionAnalysisManagerCGSCCProxy::Result
+FunctionAnalysisManagerCGSCCProxy::run(LazyCallGraph::SCC *C) {
+  assert(FAM->empty() && "Function analyses ran prior to the CGSCC proxy!");
+  return Result(*FAM);
+}
+
+FunctionAnalysisManagerCGSCCProxy::Result::~Result() {
+  // Clear out the analysis manager if we're being destroyed -- it means we
+  // didn't even see an invalidate call when we got invalidated.
+  FAM->clear();
+}
+
+bool FunctionAnalysisManagerCGSCCProxy::Result::invalidate(
+    LazyCallGraph::SCC *C, const PreservedAnalyses &PA) {
+  // If this proxy isn't marked as preserved, then we can't even invalidate
+  // individual function analyses, there may be an invalid set of Function
+  // objects in the cache making it impossible to incrementally preserve them.
+  // Just clear the entire manager.
+  if (!PA.preserved(ID()))
+    FAM->clear();
+
+  // Return false to indicate that this result is still a valid proxy.
+  return false;
+}
+
+char CGSCCAnalysisManagerFunctionProxy::PassID;