//===- 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_CGSCCPASSMANAGER_H
#define LLVM_ANALYSIS_CGSCCPASSMANAGER_H

#include "llvm/Analysis/LazyCallGraph.h"
#include "llvm/IR/PassManager.h"

namespace llvm {

/// \brief The CGSCC pass manager.
///
/// See the documentation for the PassManager template for details. It runs
/// a sequency of SCC passes over each SCC that the manager is run over. This
/// typedef serves as a convenient way to refer to this construct.
typedef PassManager<LazyCallGraph::SCC> CGSCCPassManager;

/// \brief The CGSCC analysis manager.
///
/// See the documentation for the AnalysisManager template for detail
/// documentation. This typedef serves as a convenient way to refer to this
/// construct in the adaptors and proxies used to integrate this into the larger
/// pass manager infrastructure.
typedef AnalysisManager<LazyCallGraph::SCC> CGSCCAnalysisManager;

/// \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; }

  static StringRef name() { return "CGSCCAnalysisManagerModuleProxy"; }

  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; }

  static StringRef name() { return "ModuleAnalysisManagerCGSCCProxy"; }

  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. We
      // also update the preserved set of analyses to reflect that invalidated
      // analyses are now safe to preserve.
      // 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.
      PassPA = CGAM.invalidate(C, std::move(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 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; }

  static StringRef name() { return "FunctionAnalysisManagerCGSCCProxy"; }

  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; }

  static StringRef name() { return "CGSCCAnalysisManagerFunctionProxy"; }

  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.
      // Also, update the preserved analyses to reflect that once invalidated
      // these can again be preserved.
      if (FAM)
        PassPA = FAM->invalidate(N->getFunction(), std::move(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 CGSCCToFunctionPassAdaptor<FunctionPassT>(std::move(Pass));
}
}

#endif