[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

7 files changed, 929 insertions, 0 deletions

diff --git a/include/llvm/Analysis/CGSCCPassManager.h b/include/llvm/Analysis/CGSCCPassManager.h
new file mode 100644
index 0000000000..618fee153c
--- /dev/null
+++ b/include/llvm/Analysis/CGSCCPassManager.h
@@ -0,0 +1,591 @@
+//===- CGSCCPassManager.h - Call graph pass management ----------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+/// \file
+///
+/// This header provides classes for managing passes over SCCs of the call
+/// graph. These passes form an important component of LLVM's interprocedural
+/// optimizations. Because they operate on the SCCs of the call graph, and they
+/// wtraverse the graph in post order, they can effectively do pair-wise
+/// interprocedural optimizations for all call edges in the program. At each
+/// call site edge, the callee has already been optimized as much as is
+/// possible. This in turn allows very accurate analysis of it for IPO.
+///
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_ANALYSIS_CGSCC_PASS_MANAGER_H
+#define LLVM_ANALYSIS_CGSCC_PASS_MANAGER_H
+
+#include "llvm/IR/PassManager.h"
+#include "llvm/Analysis/LazyCallGraph.h"
+
+namespace llvm {
+
+class CGSCCAnalysisManager;
+
+class CGSCCPassManager {
+public:
+  // We have to explicitly define all the special member functions because MSVC
+  // refuses to generate them.
+  CGSCCPassManager() {}
+  CGSCCPassManager(CGSCCPassManager &&Arg) : Passes(std::move(Arg.Passes)) {}
+  CGSCCPassManager &operator=(CGSCCPassManager &&RHS) {
+    Passes = std::move(RHS.Passes);
+    return *this;
+  }
+
+  /// \brief Run all of the CGSCC passes in this pass manager over a SCC.
+  PreservedAnalyses run(LazyCallGraph::SCC *C,
+                        CGSCCAnalysisManager *AM = nullptr);
+
+  template <typename CGSCCPassT> void addPass(CGSCCPassT Pass) {
+    Passes.emplace_back(new CGSCCPassModel<CGSCCPassT>(std::move(Pass)));
+  }
+
+  static StringRef name() { return "CGSCCPassManager"; }
+
+private:
+  // Pull in the concept type and model template specialized for SCCs.
+  typedef detail::PassConcept<LazyCallGraph::SCC *, CGSCCAnalysisManager>
+  CGSCCPassConcept;
+  template <typename PassT>
+  struct CGSCCPassModel
+      : detail::PassModel<LazyCallGraph::SCC *, CGSCCAnalysisManager, PassT> {
+    CGSCCPassModel(PassT Pass)
+        : detail::PassModel<LazyCallGraph::SCC *, CGSCCAnalysisManager, PassT>(
+              std::move(Pass)) {}
+  };
+
+  CGSCCPassManager(const CGSCCPassManager &) LLVM_DELETED_FUNCTION;
+  CGSCCPassManager &operator=(const CGSCCPassManager &) LLVM_DELETED_FUNCTION;
+
+  std::vector<std::unique_ptr<CGSCCPassConcept>> Passes;
+};
+
+/// \brief A function analysis manager to coordinate and cache analyses run over
+/// a module.
+class CGSCCAnalysisManager : public detail::AnalysisManagerBase<
+                                 CGSCCAnalysisManager, LazyCallGraph::SCC *> {
+  friend class detail::AnalysisManagerBase<CGSCCAnalysisManager,
+                                           LazyCallGraph::SCC *>;
+  typedef detail::AnalysisManagerBase<CGSCCAnalysisManager,
+                                      LazyCallGraph::SCC *> BaseT;
+  typedef BaseT::ResultConceptT ResultConceptT;
+  typedef BaseT::PassConceptT PassConceptT;
+
+public:
+  // Most public APIs are inherited from the CRTP base class.
+
+  // We have to explicitly define all the special member functions because MSVC
+  // refuses to generate them.
+  CGSCCAnalysisManager() {}
+  CGSCCAnalysisManager(CGSCCAnalysisManager &&Arg)
+      : BaseT(std::move(static_cast<BaseT &>(Arg))),
+        CGSCCAnalysisResults(std::move(Arg.CGSCCAnalysisResults)) {}
+  CGSCCAnalysisManager &operator=(CGSCCAnalysisManager &&RHS) {
+    BaseT::operator=(std::move(static_cast<BaseT &>(RHS)));
+    CGSCCAnalysisResults = std::move(RHS.CGSCCAnalysisResults);
+    return *this;
+  }
+
+  /// \brief Returns true if the analysis manager has an empty results cache.
+  bool empty() const;
+
+  /// \brief Clear the function analysis result cache.
+  ///
+  /// This routine allows cleaning up when the set of functions itself has
+  /// potentially changed, and thus we can't even look up a a result and
+  /// invalidate it directly. Notably, this does *not* call invalidate
+  /// functions as there is nothing to be done for them.
+  void clear();
+
+private:
+  CGSCCAnalysisManager(const CGSCCAnalysisManager &) LLVM_DELETED_FUNCTION;
+  CGSCCAnalysisManager &
+  operator=(const CGSCCAnalysisManager &) LLVM_DELETED_FUNCTION;
+
+  /// \brief Get a function pass result, running the pass if necessary.
+  ResultConceptT &getResultImpl(void *PassID, LazyCallGraph::SCC *C);
+
+  /// \brief Get a cached function pass result or return null.
+  ResultConceptT *getCachedResultImpl(void *PassID,
+                                      LazyCallGraph::SCC *C) const;
+
+  /// \brief Invalidate a function pass result.
+  void invalidateImpl(void *PassID, LazyCallGraph::SCC *C);
+
+  /// \brief Invalidate the results for a function..
+  void invalidateImpl(LazyCallGraph::SCC *C, const PreservedAnalyses &PA);
+
+  /// \brief List of function analysis pass IDs and associated concept pointers.
+  ///
+  /// Requires iterators to be valid across appending new entries and arbitrary
+  /// erases. Provides both the pass ID and concept pointer such that it is
+  /// half of a bijection and provides storage for the actual result concept.
+  typedef std::list<
+      std::pair<void *, std::unique_ptr<detail::AnalysisResultConcept<
+                            LazyCallGraph::SCC *>>>> CGSCCAnalysisResultListT;
+
+  /// \brief Map type from function pointer to our custom list type.
+  typedef DenseMap<LazyCallGraph::SCC *, CGSCCAnalysisResultListT>
+  CGSCCAnalysisResultListMapT;
+
+  /// \brief Map from function to a list of function analysis results.
+  ///
+  /// Provides linear time removal of all analysis results for a function and
+  /// the ultimate storage for a particular cached analysis result.
+  CGSCCAnalysisResultListMapT CGSCCAnalysisResultLists;
+
+  /// \brief Map type from a pair of analysis ID and function pointer to an
+  /// iterator into a particular result list.
+  typedef DenseMap<std::pair<void *, LazyCallGraph::SCC *>,
+                   CGSCCAnalysisResultListT::iterator> CGSCCAnalysisResultMapT;
+
+  /// \brief Map from an analysis ID and function to a particular cached
+  /// analysis result.
+  CGSCCAnalysisResultMapT CGSCCAnalysisResults;
+};
+
+/// \brief A module analysis which acts as a proxy for a CGSCC analysis
+/// manager.
+///
+/// This primarily proxies invalidation information from the module analysis
+/// manager and module pass manager to a CGSCC analysis manager. You should
+/// never use a CGSCC analysis manager from within (transitively) a module
+/// pass manager unless your parent module pass has received a proxy result
+/// object for it.
+class CGSCCAnalysisManagerModuleProxy {
+public:
+  class Result {
+  public:
+    explicit Result(CGSCCAnalysisManager &CGAM) : CGAM(&CGAM) {}
+    // We have to explicitly define all the special member functions because
+    // MSVC refuses to generate them.
+    Result(const Result &Arg) : CGAM(Arg.CGAM) {}
+    Result(Result &&Arg) : CGAM(std::move(Arg.CGAM)) {}
+    Result &operator=(Result RHS) {
+      std::swap(CGAM, RHS.CGAM);
+      return *this;
+    }
+    ~Result();
+
+    /// \brief Accessor for the \c CGSCCAnalysisManager.
+    CGSCCAnalysisManager &getManager() { return *CGAM; }
+
+    /// \brief Handler for invalidation of the module.
+    ///
+    /// If this analysis itself is preserved, then we assume that the call
+    /// graph of the module hasn't changed and thus we don't need to invalidate
+    /// *all* cached data associated with a \c SCC* in the \c
+    /// CGSCCAnalysisManager.
+    ///
+    /// Regardless of whether this analysis is marked as preserved, all of the
+    /// analyses in the \c CGSCCAnalysisManager are potentially invalidated
+    /// based on the set of preserved analyses.
+    bool invalidate(Module *M, const PreservedAnalyses &PA);
+
+  private:
+    CGSCCAnalysisManager *CGAM;
+  };
+
+  static void *ID() { return (void *)&PassID; }
+
+  explicit CGSCCAnalysisManagerModuleProxy(CGSCCAnalysisManager &CGAM)
+      : CGAM(&CGAM) {}
+  // We have to explicitly define all the special member functions because MSVC
+  // refuses to generate them.
+  CGSCCAnalysisManagerModuleProxy(
+      const CGSCCAnalysisManagerModuleProxy &Arg)
+      : CGAM(Arg.CGAM) {}
+  CGSCCAnalysisManagerModuleProxy(CGSCCAnalysisManagerModuleProxy &&Arg)
+      : CGAM(std::move(Arg.CGAM)) {}
+  CGSCCAnalysisManagerModuleProxy &
+  operator=(CGSCCAnalysisManagerModuleProxy RHS) {
+    std::swap(CGAM, RHS.CGAM);
+    return *this;
+  }
+
+  /// \brief Run the analysis pass and create our proxy result object.
+  ///
+  /// This doesn't do any interesting work, it is primarily used to insert our
+  /// proxy result object into the module analysis cache so that we can proxy
+  /// invalidation to the CGSCC analysis manager.
+  ///
+  /// In debug builds, it will also assert that the analysis manager is empty
+  /// as no queries should arrive at the CGSCC analysis manager prior to
+  /// this analysis being requested.
+  Result run(Module *M);
+
+private:
+  static char PassID;
+
+  CGSCCAnalysisManager *CGAM;
+};
+
+/// \brief A CGSCC analysis which acts as a proxy for a module analysis
+/// manager.
+///
+/// This primarily provides an accessor to a parent module analysis manager to
+/// CGSCC passes. Only the const interface of the module analysis manager is
+/// provided to indicate that once inside of a CGSCC analysis pass you
+/// cannot request a module analysis to actually run. Instead, the user must
+/// rely on the \c getCachedResult API.
+///
+/// This proxy *doesn't* manage the invalidation in any way. That is handled by
+/// the recursive return path of each layer of the pass manager and the
+/// returned PreservedAnalysis set.
+class ModuleAnalysisManagerCGSCCProxy {
+public:
+  /// \brief Result proxy object for \c ModuleAnalysisManagerCGSCCProxy.
+  class Result {
+  public:
+    explicit Result(const ModuleAnalysisManager &MAM) : MAM(&MAM) {}
+    // We have to explicitly define all the special member functions because
+    // MSVC refuses to generate them.
+    Result(const Result &Arg) : MAM(Arg.MAM) {}
+    Result(Result &&Arg) : MAM(std::move(Arg.MAM)) {}
+    Result &operator=(Result RHS) {
+      std::swap(MAM, RHS.MAM);
+      return *this;
+    }
+
+    const ModuleAnalysisManager &getManager() const { return *MAM; }
+
+    /// \brief Handle invalidation by ignoring it, this pass is immutable.
+    bool invalidate(LazyCallGraph::SCC *) { return false; }
+
+  private:
+    const ModuleAnalysisManager *MAM;
+  };
+
+  static void *ID() { return (void *)&PassID; }
+
+  ModuleAnalysisManagerCGSCCProxy(const ModuleAnalysisManager &MAM)
+      : MAM(&MAM) {}
+  // We have to explicitly define all the special member functions because MSVC
+  // refuses to generate them.
+  ModuleAnalysisManagerCGSCCProxy(
+      const ModuleAnalysisManagerCGSCCProxy &Arg)
+      : MAM(Arg.MAM) {}
+  ModuleAnalysisManagerCGSCCProxy(ModuleAnalysisManagerCGSCCProxy &&Arg)
+      : MAM(std::move(Arg.MAM)) {}
+  ModuleAnalysisManagerCGSCCProxy &
+  operator=(ModuleAnalysisManagerCGSCCProxy RHS) {
+    std::swap(MAM, RHS.MAM);
+    return *this;
+  }
+
+  /// \brief Run the analysis pass and create our proxy result object.
+  /// Nothing to see here, it just forwards the \c MAM reference into the
+  /// result.
+  Result run(LazyCallGraph::SCC *) { return Result(*MAM); }
+
+private:
+  static char PassID;
+
+  const ModuleAnalysisManager *MAM;
+};
+
+/// \brief The core module pass which does a post-order walk of the SCCs and
+/// runs a CGSCC pass over each one.
+///
+/// Designed to allow composition of a CGSCCPass(Manager) and
+/// a ModulePassManager. Note that this pass must be run with a module analysis
+/// manager as it uses the LazyCallGraph analysis. It will also run the
+/// \c CGSCCAnalysisManagerModuleProxy analysis prior to running the CGSCC
+/// pass over the module to enable a \c FunctionAnalysisManager to be used
+/// within this run safely.
+template <typename CGSCCPassT> class ModuleToPostOrderCGSCCPassAdaptor {
+public:
+  explicit ModuleToPostOrderCGSCCPassAdaptor(CGSCCPassT Pass)
+      : Pass(std::move(Pass)) {}
+  // We have to explicitly define all the special member functions because MSVC
+  // refuses to generate them.
+  ModuleToPostOrderCGSCCPassAdaptor(
+      const ModuleToPostOrderCGSCCPassAdaptor &Arg)
+      : Pass(Arg.Pass) {}
+  ModuleToPostOrderCGSCCPassAdaptor(ModuleToPostOrderCGSCCPassAdaptor &&Arg)
+      : Pass(std::move(Arg.Pass)) {}
+  friend void swap(ModuleToPostOrderCGSCCPassAdaptor &LHS,
+                   ModuleToPostOrderCGSCCPassAdaptor &RHS) {
+    using std::swap;
+    swap(LHS.Pass, RHS.Pass);
+  }
+  ModuleToPostOrderCGSCCPassAdaptor &
+  operator=(ModuleToPostOrderCGSCCPassAdaptor RHS) {
+    swap(*this, RHS);
+    return *this;
+  }
+
+  /// \brief Runs the CGSCC pass across every SCC in the module.
+  PreservedAnalyses run(Module *M, ModuleAnalysisManager *AM) {
+    assert(AM && "We need analyses to compute the call graph!");
+
+    // Setup the CGSCC analysis manager from its proxy.
+    CGSCCAnalysisManager &CGAM =
+        AM->getResult<CGSCCAnalysisManagerModuleProxy>(M).getManager();
+
+    // Get the call graph for this module.
+    LazyCallGraph &CG = AM->getResult<LazyCallGraphAnalysis>(M);
+
+    PreservedAnalyses PA = PreservedAnalyses::all();
+    for (LazyCallGraph::SCC *C : CG.postorder_sccs()) {
+      PreservedAnalyses PassPA = Pass.run(C, &CGAM);
+
+      // We know that the CGSCC pass couldn't have invalidated any other
+      // SCC's analyses (that's the contract of a CGSCC pass), so
+      // directly handle the CGSCC analysis manager's invalidation here.
+      // FIXME: This isn't quite correct. We need to handle the case where the
+      // pass updated the CG, particularly some child of the current SCC, and
+      // invalidate its analyses.
+      CGAM.invalidate(C, PassPA);
+
+      // Then intersect the preserved set so that invalidation of module
+      // analyses will eventually occur when the module pass completes.
+      PA.intersect(std::move(PassPA));
+    }
+
+    // By definition we preserve the proxy. This precludes *any* invalidation
+    // of CGSCC analyses by the proxy, but that's OK because we've taken
+    // care to invalidate analyses in the CGSCC analysis manager
+    // incrementally above.
+    PA.preserve<CGSCCAnalysisManagerModuleProxy>();
+    return PA;
+  }
+
+  static StringRef name() { return "ModuleToPostOrderCGSCCPassAdaptor"; }
+
+private:
+  CGSCCPassT Pass;
+};
+
+/// \brief A function to deduce a function pass type and wrap it in the
+/// templated adaptor.
+template <typename CGSCCPassT>
+ModuleToPostOrderCGSCCPassAdaptor<CGSCCPassT>
+createModuleToPostOrderCGSCCPassAdaptor(CGSCCPassT Pass) {
+  return std::move(
+      ModuleToPostOrderCGSCCPassAdaptor<CGSCCPassT>(std::move(Pass)));
+}
+
+/// \brief A CGSCC analysis which acts as a proxy for a function analysis
+/// manager.
+///
+/// This primarily proxies invalidation information from the CGSCC analysis
+/// manager and CGSCC pass manager to a function analysis manager. You should
+/// never use a function analysis manager from within (transitively) a CGSCC
+/// pass manager unless your parent CGSCC pass has received a proxy result
+/// object for it.
+class FunctionAnalysisManagerCGSCCProxy {
+public:
+  class Result {
+  public:
+    explicit Result(FunctionAnalysisManager &FAM) : FAM(&FAM) {}
+    // We have to explicitly define all the special member functions because
+    // MSVC refuses to generate them.
+    Result(const Result &Arg) : FAM(Arg.FAM) {}
+    Result(Result &&Arg) : FAM(std::move(Arg.FAM)) {}
+    Result &operator=(Result RHS) {
+      std::swap(FAM, RHS.FAM);
+      return *this;
+    }
+    ~Result();
+
+    /// \brief Accessor for the \c FunctionAnalysisManager.
+    FunctionAnalysisManager &getManager() { return *FAM; }
+
+    /// \brief Handler for invalidation of the SCC.
+    ///
+    /// If this analysis itself is preserved, then we assume that the set of \c
+    /// Function objects in the \c SCC hasn't changed and thus we don't need
+    /// to invalidate *all* cached data associated with a \c Function* in the \c
+    /// FunctionAnalysisManager.
+    ///
+    /// Regardless of whether this analysis is marked as preserved, all of the
+    /// analyses in the \c FunctionAnalysisManager are potentially invalidated
+    /// based on the set of preserved analyses.
+    bool invalidate(LazyCallGraph::SCC *C, const PreservedAnalyses &PA);
+
+  private:
+    FunctionAnalysisManager *FAM;
+  };
+
+  static void *ID() { return (void *)&PassID; }
+
+  explicit FunctionAnalysisManagerCGSCCProxy(FunctionAnalysisManager &FAM)
+      : FAM(&FAM) {}
+  // We have to explicitly define all the special member functions because MSVC
+  // refuses to generate them.
+  FunctionAnalysisManagerCGSCCProxy(
+      const FunctionAnalysisManagerCGSCCProxy &Arg)
+      : FAM(Arg.FAM) {}
+  FunctionAnalysisManagerCGSCCProxy(FunctionAnalysisManagerCGSCCProxy &&Arg)
+      : FAM(std::move(Arg.FAM)) {}
+  FunctionAnalysisManagerCGSCCProxy &
+  operator=(FunctionAnalysisManagerCGSCCProxy RHS) {
+    std::swap(FAM, RHS.FAM);
+    return *this;
+  }
+
+  /// \brief Run the analysis pass and create our proxy result object.
+  ///
+  /// This doesn't do any interesting work, it is primarily used to insert our
+  /// proxy result object into the module analysis cache so that we can proxy
+  /// invalidation to the function analysis manager.
+  ///
+  /// In debug builds, it will also assert that the analysis manager is empty
+  /// as no queries should arrive at the function analysis manager prior to
+  /// this analysis being requested.
+  Result run(LazyCallGraph::SCC *C);
+
+private:
+  static char PassID;
+
+  FunctionAnalysisManager *FAM;
+};
+
+/// \brief A function analysis which acts as a proxy for a CGSCC analysis
+/// manager.
+///
+/// This primarily provides an accessor to a parent CGSCC analysis manager to
+/// function passes. Only the const interface of the CGSCC analysis manager is
+/// provided to indicate that once inside of a function analysis pass you
+/// cannot request a CGSCC analysis to actually run. Instead, the user must
+/// rely on the \c getCachedResult API.
+///
+/// This proxy *doesn't* manage the invalidation in any way. That is handled by
+/// the recursive return path of each layer of the pass manager and the
+/// returned PreservedAnalysis set.
+class CGSCCAnalysisManagerFunctionProxy {
+public:
+  /// \brief Result proxy object for \c ModuleAnalysisManagerFunctionProxy.
+  class Result {
+  public:
+    explicit Result(const CGSCCAnalysisManager &CGAM) : CGAM(&CGAM) {}
+    // We have to explicitly define all the special member functions because
+    // MSVC refuses to generate them.
+    Result(const Result &Arg) : CGAM(Arg.CGAM) {}
+    Result(Result &&Arg) : CGAM(std::move(Arg.CGAM)) {}
+    Result &operator=(Result RHS) {
+      std::swap(CGAM, RHS.CGAM);
+      return *this;
+    }
+
+    const CGSCCAnalysisManager &getManager() const { return *CGAM; }
+
+    /// \brief Handle invalidation by ignoring it, this pass is immutable.
+    bool invalidate(Function *) { return false; }
+
+  private:
+    const CGSCCAnalysisManager *CGAM;
+  };
+
+  static void *ID() { return (void *)&PassID; }
+
+  CGSCCAnalysisManagerFunctionProxy(const CGSCCAnalysisManager &CGAM)
+      : CGAM(&CGAM) {}
+  // We have to explicitly define all the special member functions because MSVC
+  // refuses to generate them.
+  CGSCCAnalysisManagerFunctionProxy(
+      const CGSCCAnalysisManagerFunctionProxy &Arg)
+      : CGAM(Arg.CGAM) {}
+  CGSCCAnalysisManagerFunctionProxy(CGSCCAnalysisManagerFunctionProxy &&Arg)
+      : CGAM(std::move(Arg.CGAM)) {}
+  CGSCCAnalysisManagerFunctionProxy &
+  operator=(CGSCCAnalysisManagerFunctionProxy RHS) {
+    std::swap(CGAM, RHS.CGAM);
+    return *this;
+  }
+
+  /// \brief Run the analysis pass and create our proxy result object.
+  /// Nothing to see here, it just forwards the \c CGAM reference into the
+  /// result.
+  Result run(Function *) { return Result(*CGAM); }
+
+private:
+  static char PassID;
+
+  const CGSCCAnalysisManager *CGAM;
+};
+
+/// \brief Adaptor that maps from a SCC to its functions.
+///
+/// Designed to allow composition of a FunctionPass(Manager) and
+/// a CGSCCPassManager. Note that if this pass is constructed with a pointer
+/// to a \c CGSCCAnalysisManager it will run the
+/// \c FunctionAnalysisManagerCGSCCProxy analysis prior to running the function
+/// pass over the SCC to enable a \c FunctionAnalysisManager to be used
+/// within this run safely.
+template <typename FunctionPassT> class CGSCCToFunctionPassAdaptor {
+public:
+  explicit CGSCCToFunctionPassAdaptor(FunctionPassT Pass)
+      : Pass(std::move(Pass)) {}
+  // We have to explicitly define all the special member functions because MSVC
+  // refuses to generate them.
+  CGSCCToFunctionPassAdaptor(const CGSCCToFunctionPassAdaptor &Arg)
+      : Pass(Arg.Pass) {}
+  CGSCCToFunctionPassAdaptor(CGSCCToFunctionPassAdaptor &&Arg)
+      : Pass(std::move(Arg.Pass)) {}
+  friend void swap(CGSCCToFunctionPassAdaptor &LHS, CGSCCToFunctionPassAdaptor &RHS) {
+    using std::swap;
+    swap(LHS.Pass, RHS.Pass);
+  }
+  CGSCCToFunctionPassAdaptor &operator=(CGSCCToFunctionPassAdaptor RHS) {
+    swap(*this, RHS);
+    return *this;
+  }
+
+  /// \brief Runs the function pass across every function in the module.
+  PreservedAnalyses run(LazyCallGraph::SCC *C, CGSCCAnalysisManager *AM) {
+    FunctionAnalysisManager *FAM = nullptr;
+    if (AM)
+      // Setup the function analysis manager from its proxy.
+      FAM = &AM->getResult<FunctionAnalysisManagerCGSCCProxy>(C).getManager();
+
+    PreservedAnalyses PA = PreservedAnalyses::all();
+    for (LazyCallGraph::Node *N : *C) {
+      PreservedAnalyses PassPA = Pass.run(&N->getFunction(), FAM);
+
+      // We know that the function pass couldn't have invalidated any other
+      // function's analyses (that's the contract of a function pass), so
+      // directly handle the function analysis manager's invalidation here.
+      if (FAM)
+        FAM->invalidate(&N->getFunction(), PassPA);
+
+      // Then intersect the preserved set so that invalidation of module
+      // analyses will eventually occur when the module pass completes.
+      PA.intersect(std::move(PassPA));
+    }
+
+    // By definition we preserve the proxy. This precludes *any* invalidation
+    // of function analyses by the proxy, but that's OK because we've taken
+    // care to invalidate analyses in the function analysis manager
+    // incrementally above.
+    // FIXME: We need to update the call graph here to account for any deleted
+    // edges!
+    PA.preserve<FunctionAnalysisManagerCGSCCProxy>();
+    return PA;
+  }
+
+  static StringRef name() { return "CGSCCToFunctionPassAdaptor"; }
+
+private:
+  FunctionPassT Pass;
+};
+
+/// \brief A function to deduce a function pass type and wrap it in the
+/// templated adaptor.
+template <typename FunctionPassT>
+CGSCCToFunctionPassAdaptor<FunctionPassT>
+createCGSCCToFunctionPassAdaptor(FunctionPassT Pass) {
+  return std::move(CGSCCToFunctionPassAdaptor<FunctionPassT>(std::move(Pass)));
+}
+
+}
+
+#endif
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;
diff --git a/lib/Analysis/CMakeLists.txt b/lib/Analysis/CMakeLists.txt
index c6d4573885..7c38be149b 100644
--- a/lib/Analysis/CMakeLists.txt
+++ b/lib/Analysis/CMakeLists.txt
@@ -10,6 +10,7 @@ add_llvm_library(LLVMAnalysis
   BranchProbabilityInfo.cpp
   CFG.cpp
   CFGPrinter.cpp
+  CGSCCPassManager.cpp
   CaptureTracking.cpp
   CostModel.cpp
   CodeMetrics.cpp
diff --git a/test/Other/pass-pipeline-parsing.ll b/test/Other/pass-pipeline-parsing.ll
index ba336108c9..4ec4162cd4 100644
--- a/test/Other/pass-pipeline-parsing.ll
+++ b/test/Other/pass-pipeline-parsing.ll
@@ -105,6 +105,42 @@
 ; RUN:     | FileCheck %s --check-prefix=CHECK-UNBALANCED10
 ; CHECK-UNBALANCED10: unable to parse pass pipeline description
 
+; RUN: opt -disable-output -debug-pass-manager -debug-cgscc-pass-manager \
+; RUN:     -passes=no-op-cgscc,no-op-cgscc %s 2>&1 \
+; RUN:     | FileCheck %s --check-prefix=CHECK-TWO-NOOP-CG
+; CHECK-TWO-NOOP-CG: Starting module pass manager
+; CHECK-TWO-NOOP-CG: Running module pass: ModuleToPostOrderCGSCCPassAdaptor
+; CHECK-TWO-NOOP-CG: Starting CGSCC pass manager
+; CHECK-TWO-NOOP-CG: Running CGSCC pass: NoOpCGSCCPass
+; CHECK-TWO-NOOP-CG: Running CGSCC pass: NoOpCGSCCPass
+; CHECK-TWO-NOOP-CG: Finished CGSCC pass manager
+; CHECK-TWO-NOOP-CG: Finished module pass manager
+
+; RUN: opt -disable-output -debug-pass-manager -debug-cgscc-pass-manager \
+; RUN:     -passes='module(function(no-op-function),cgscc(no-op-cgscc,function(no-op-function),no-op-cgscc),function(no-op-function))' %s 2>&1 \
+; RUN:     | FileCheck %s --check-prefix=CHECK-NESTED-MP-CG-FP
+; CHECK-NESTED-MP-CG-FP: Starting module pass manager
+; CHECK-NESTED-MP-CG-FP: Starting module pass manager
+; CHECK-NESTED-MP-CG-FP: Running module pass: ModuleToFunctionPassAdaptor
+; CHECK-NESTED-MP-CG-FP: Starting function pass manager
+; CHECK-NESTED-MP-CG-FP: Running function pass: NoOpFunctionPass
+; CHECK-NESTED-MP-CG-FP: Finished function pass manager
+; CHECK-NESTED-MP-CG-FP: Running module pass: ModuleToPostOrderCGSCCPassAdaptor
+; CHECK-NESTED-MP-CG-FP: Starting CGSCC pass manager
+; CHECK-NESTED-MP-CG-FP: Running CGSCC pass: NoOpCGSCCPass
+; CHECK-NESTED-MP-CG-FP: Running CGSCC pass: CGSCCToFunctionPassAdaptor
+; CHECK-NESTED-MP-CG-FP: Starting function pass manager
+; CHECK-NESTED-MP-CG-FP: Running function pass: NoOpFunctionPass
+; CHECK-NESTED-MP-CG-FP: Finished function pass manager
+; CHECK-NESTED-MP-CG-FP: Running CGSCC pass: NoOpCGSCCPass
+; CHECK-NESTED-MP-CG-FP: Finished CGSCC pass manager
+; CHECK-NESTED-MP-CG-FP: Running module pass: ModuleToFunctionPassAdaptor
+; CHECK-NESTED-MP-CG-FP: Starting function pass manager
+; CHECK-NESTED-MP-CG-FP: Running function pass: NoOpFunctionPass
+; CHECK-NESTED-MP-CG-FP: Finished function pass manager
+; CHECK-NESTED-MP-CG-FP: Finished module pass manager
+; CHECK-NESTED-MP-CG-FP: Finished module pass manager
+
 define void @f() {
  ret void
 }
diff --git a/tools/opt/NewPMDriver.cpp b/tools/opt/NewPMDriver.cpp
index 39a6579356..8076ff4487 100644
--- a/tools/opt/NewPMDriver.cpp
+++ b/tools/opt/NewPMDriver.cpp
@@ -16,6 +16,7 @@
 #include "NewPMDriver.h"
 #include "Passes.h"
 #include "llvm/ADT/StringRef.h"
+#include "llvm/Analysis/CGSCCPassManager.h"
 #include "llvm/Analysis/LazyCallGraph.h"
 #include "llvm/Bitcode/BitcodeWriterPass.h"
 #include "llvm/IR/IRPrintingPasses.h"
@@ -34,18 +35,27 @@ bool llvm::runPassPipeline(StringRef Arg0, LLVMContext &Context, Module &M,
                            tool_output_file *Out, StringRef PassPipeline,
                            OutputKind OK, VerifierKind VK) {
   FunctionAnalysisManager FAM;
+  CGSCCAnalysisManager CGAM;
   ModuleAnalysisManager MAM;
 
 #define MODULE_ANALYSIS(NAME, CREATE_PASS) \
   MAM.registerPass(CREATE_PASS);
 #include "PassRegistry.def"
 
+#define CGSCC_ANALYSIS(NAME, CREATE_PASS) \
+  CGAM.registerPass(CREATE_PASS);
+#include "PassRegistry.def"
+
 #define FUNCTION_ANALYSIS(NAME, CREATE_PASS) \
   FAM.registerPass(CREATE_PASS);
 #include "PassRegistry.def"
 
   // Cross register the analysis managers through their proxies.
   MAM.registerPass(FunctionAnalysisManagerModuleProxy(FAM));
+  MAM.registerPass(CGSCCAnalysisManagerModuleProxy(CGAM));
+  CGAM.registerPass(FunctionAnalysisManagerCGSCCProxy(FAM));
+  CGAM.registerPass(ModuleAnalysisManagerCGSCCProxy(MAM));
+  FAM.registerPass(CGSCCAnalysisManagerFunctionProxy(CGAM));
   FAM.registerPass(ModuleAnalysisManagerFunctionProxy(MAM));
 
   ModulePassManager MPM;
diff --git a/tools/opt/PassRegistry.def b/tools/opt/PassRegistry.def
index 92ab2d932f..e1e49004c7 100644
--- a/tools/opt/PassRegistry.def
+++ b/tools/opt/PassRegistry.def
@@ -29,6 +29,16 @@ MODULE_PASS("print", PrintModulePass(dbgs()))
 MODULE_PASS("print-cg", LazyCallGraphPrinterPass(dbgs()))
 #undef MODULE_PASS
 
+#ifndef CGSCC_ANALYSIS
+#define CGSCC_ANALYSIS(NAME, CREATE_PASS)
+#endif
+#undef CGSCC_ANALYSIS
+
+#ifndef CGSCC_PASS
+#define CGSCC_PASS(NAME, CREATE_PASS)
+#endif
+#undef CGSCC_PASS
+
 #ifndef FUNCTION_ANALYSIS
 #define FUNCTION_ANALYSIS(NAME, CREATE_PASS)
 #endif
diff --git a/tools/opt/Passes.cpp b/tools/opt/Passes.cpp
index e4791b8ac8..a171f42691 100644
--- a/tools/opt/Passes.cpp
+++ b/tools/opt/Passes.cpp
@@ -15,6 +15,7 @@
 //===----------------------------------------------------------------------===//
 
 #include "Passes.h"
+#include "llvm/Analysis/CGSCCPassManager.h"
 #include "llvm/Analysis/LazyCallGraph.h"
 #include "llvm/IR/IRPrintingPasses.h"
 #include "llvm/IR/PassManager.h"
@@ -31,6 +32,14 @@ struct NoOpModulePass {
   static StringRef name() { return "NoOpModulePass"; }
 };
 
+/// \brief No-op CGSCC pass which does nothing.
+struct NoOpCGSCCPass {
+  PreservedAnalyses run(LazyCallGraph::SCC *C) {
+    return PreservedAnalyses::all();
+  }
+  static StringRef name() { return "NoOpCGSCCPass"; }
+};
+
 /// \brief No-op function pass which does nothing.
 struct NoOpFunctionPass {
   PreservedAnalyses run(Function *F) { return PreservedAnalyses::all(); }
@@ -48,6 +57,15 @@ static bool isModulePassName(StringRef Name) {
   return false;
 }
 
+static bool isCGSCCPassName(StringRef Name) {
+  if (Name == "no-op-cgscc") return true;
+
+#define CGSCC_PASS(NAME, CREATE_PASS) if (Name == NAME) return true;
+#include "PassRegistry.def"
+
+  return false;
+}
+
 static bool isFunctionPassName(StringRef Name) {
   if (Name == "no-op-function") return true;
 
@@ -73,6 +91,22 @@ static bool parseModulePassName(ModulePassManager &MPM, StringRef Name) {
   return false;
 }
 
+static bool parseCGSCCPassName(CGSCCPassManager &CGPM, StringRef Name) {
+  if (Name == "no-op-cgscc") {
+    CGPM.addPass(NoOpCGSCCPass());
+    return true;
+  }
+
+#define CGSCC_PASS(NAME, CREATE_PASS)                                          \
+  if (Name == NAME) {                                                          \
+    CGPM.addPass(CREATE_PASS);                                                 \
+    return true;                                                               \
+  }
+#include "PassRegistry.def"
+
+  return false;
+}
+
 static bool parseFunctionPassName(FunctionPassManager &FPM, StringRef Name) {
   if (Name == "no-op-function") {
     FPM.addPass(NoOpFunctionPass());
@@ -126,6 +160,55 @@ static bool parseFunctionPassPipeline(FunctionPassManager &FPM,
   }
 }
 
+static bool parseCGSCCPassPipeline(CGSCCPassManager &CGPM,
+                                      StringRef &PipelineText,
+                                      bool VerifyEachPass) {
+  for (;;) {
+    // Parse nested pass managers by recursing.
+    if (PipelineText.startswith("cgscc(")) {
+      CGSCCPassManager NestedCGPM;
+
+      // Parse the inner pipeline into the nested manager.
+      PipelineText = PipelineText.substr(strlen("cgscc("));
+      if (!parseCGSCCPassPipeline(NestedCGPM, PipelineText, VerifyEachPass) ||
+          PipelineText.empty())
+        return false;
+      assert(PipelineText[0] == ')');
+      PipelineText = PipelineText.substr(1);
+
+      // Add the nested pass manager with the appropriate adaptor.
+      CGPM.addPass(std::move(NestedCGPM));
+    } else if (PipelineText.startswith("function(")) {
+      FunctionPassManager NestedFPM;
+
+      // Parse the inner pipeline inte the nested manager.
+      PipelineText = PipelineText.substr(strlen("function("));
+      if (!parseFunctionPassPipeline(NestedFPM, PipelineText, VerifyEachPass) ||
+          PipelineText.empty())
+        return false;
+      assert(PipelineText[0] == ')');
+      PipelineText = PipelineText.substr(1);
+
+      // Add the nested pass manager with the appropriate adaptor.
+      CGPM.addPass(createCGSCCToFunctionPassAdaptor(std::move(NestedFPM)));
+    } else {
+      // Otherwise try to parse a pass name.
+      size_t End = PipelineText.find_first_of(",)");
+      if (!parseCGSCCPassName(CGPM, PipelineText.substr(0, End)))
+        return false;
+      // FIXME: No verifier support for CGSCC passes!
+
+      PipelineText = PipelineText.substr(End);
+    }
+
+    if (PipelineText.empty() || PipelineText[0] == ')')
+      return true;
+
+    assert(PipelineText[0] == ',');
+    PipelineText = PipelineText.substr(1);
+  }
+}
+
 static bool parseModulePassPipeline(ModulePassManager &MPM,
                                     StringRef &PipelineText,
                                     bool VerifyEachPass) {
@@ -144,6 +227,20 @@ static bool parseModulePassPipeline(ModulePassManager &MPM,
 
       // Now add the nested manager as a module pass.
       MPM.addPass(std::move(NestedMPM));
+    } else if (PipelineText.startswith("cgscc(")) {
+      CGSCCPassManager NestedCGPM;
+
+      // Parse the inner pipeline inte the nested manager.
+      PipelineText = PipelineText.substr(strlen("cgscc("));
+      if (!parseCGSCCPassPipeline(NestedCGPM, PipelineText, VerifyEachPass) ||
+          PipelineText.empty())
+        return false;
+      assert(PipelineText[0] == ')');
+      PipelineText = PipelineText.substr(1);
+
+      // Add the nested pass manager with the appropriate adaptor.
+      MPM.addPass(
+          createModuleToPostOrderCGSCCPassAdaptor(std::move(NestedCGPM)));
     } else if (PipelineText.startswith("function(")) {
       FunctionPassManager NestedFPM;
 
@@ -185,6 +282,14 @@ bool llvm::parsePassPipeline(ModulePassManager &MPM, StringRef PipelineText,
   if (PipelineText.startswith("module("))
     return parseModulePassPipeline(MPM, PipelineText, VerifyEachPass) &&
            PipelineText.empty();
+  if (PipelineText.startswith("cgscc(")) {
+    CGSCCPassManager CGPM;
+    if (!parseCGSCCPassPipeline(CGPM, PipelineText, VerifyEachPass) ||
+        !PipelineText.empty())
+      return false;
+    MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM)));
+    return true;
+  }
   if (PipelineText.startswith("function(")) {
     FunctionPassManager FPM;
     if (!parseFunctionPassPipeline(FPM, PipelineText, VerifyEachPass) ||
@@ -201,6 +306,15 @@ bool llvm::parsePassPipeline(ModulePassManager &MPM, StringRef PipelineText,
     return parseModulePassPipeline(MPM, PipelineText, VerifyEachPass) &&
            PipelineText.empty();
 
+  if (isCGSCCPassName(FirstName)) {
+    CGSCCPassManager CGPM;
+    if (!parseCGSCCPassPipeline(CGPM, PipelineText, VerifyEachPass) ||
+        !PipelineText.empty())
+      return false;
+    MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM)));
+    return true;
+  }
+
   if (isFunctionPassName(FirstName)) {
     FunctionPassManager FPM;
     if (!parseFunctionPassPipeline(FPM, PipelineText, VerifyEachPass) ||