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) ||