Subversion Repositories QNX 8.QNX8 LLVM/Clang compiler suite

//===- LoopPassManager.h - Loop pass management -----------------*- C++ -*-===//

//

// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.

// See https://llvm.org/LICENSE.txt for license information.

// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception

//

//===----------------------------------------------------------------------===//

/// \file

///

/// This header provides classes for managing a pipeline of passes over loops

/// in LLVM IR.

///

/// The primary loop pass pipeline is managed in a very particular way to

/// provide a set of core guarantees:

/// 1) Loops are, where possible, in simplified form.

/// 2) Loops are *always* in LCSSA form.

/// 3) A collection of Loop-specific analysis results are available:

///    - LoopInfo

///    - DominatorTree

///    - ScalarEvolution

///    - AAManager

/// 4) All loop passes preserve #1 (where possible), #2, and #3.

/// 5) Loop passes run over each loop in the loop nest from the innermost to

///    the outermost. Specifically, all inner loops are processed before

///    passes run over outer loops. When running the pipeline across an inner

///    loop creates new inner loops, those are added and processed in this

///    order as well.

///

/// This process is designed to facilitate transformations which simplify,

/// reduce, and remove loops. For passes which are more oriented towards

/// optimizing loops, especially optimizing loop *nests* instead of single

/// loops in isolation, this framework is less interesting.

///

//===----------------------------------------------------------------------===//

#ifndef LLVM_TRANSFORMS_SCALAR_LOOPPASSMANAGER_H

#define LLVM_TRANSFORMS_SCALAR_LOOPPASSMANAGER_H

#include "llvm/ADT/PriorityWorklist.h"

#include "llvm/Analysis/LoopAnalysisManager.h"

#include "llvm/Analysis/LoopInfo.h"

#include "llvm/Analysis/LoopNestAnalysis.h"

#include "llvm/IR/PassManager.h"

#include "llvm/Transforms/Utils/LCSSA.h"

#include "llvm/Transforms/Utils/LoopSimplify.h"

#include "llvm/Transforms/Utils/LoopUtils.h"

#include <memory>

namespace llvm {

// Forward declarations of an update tracking API used in the pass manager.

class LPMUpdater;

class PassInstrumentation;

namespace {

template <typename PassT>

using HasRunOnLoopT = decltype(std::declval<PassT>().run(

    std::declval<Loop &>(), std::declval<LoopAnalysisManager &>(),

    std::declval<LoopStandardAnalysisResults &>(),

    std::declval<LPMUpdater &>()));

} // namespace

// Explicit specialization and instantiation declarations for the pass manager.

// See the comments on the definition of the specialization for details on how

// it differs from the primary template.

template <>

class PassManager<Loop, LoopAnalysisManager, LoopStandardAnalysisResults &,

                  LPMUpdater &>

    : public PassInfoMixin<

          PassManager<Loop, LoopAnalysisManager, LoopStandardAnalysisResults &,

                      LPMUpdater &>> {

public:

  explicit PassManager() = default;

  // FIXME: These are equivalent to the default move constructor/move

  // assignment. However, using = default triggers linker errors due to the

  // explicit instantiations below. Find a way to use the default and remove the

  // duplicated code here.

  PassManager(PassManager &&Arg)

      : IsLoopNestPass(std::move(Arg.IsLoopNestPass)),

        LoopPasses(std::move(Arg.LoopPasses)),

        LoopNestPasses(std::move(Arg.LoopNestPasses)) {}

  PassManager &operator=(PassManager &&RHS) {

    IsLoopNestPass = std::move(RHS.IsLoopNestPass);

    LoopPasses = std::move(RHS.LoopPasses);

    LoopNestPasses = std::move(RHS.LoopNestPasses);

    return *this;

  }

  PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM,

                        LoopStandardAnalysisResults &AR, LPMUpdater &U);

  void printPipeline(raw_ostream &OS,

                     function_ref<StringRef(StringRef)> MapClassName2PassName);

  /// Add either a loop pass or a loop-nest pass to the pass manager. Append \p

  /// Pass to the list of loop passes if it has a dedicated \fn run() method for

  /// loops and to the list of loop-nest passes if the \fn run() method is for

  /// loop-nests instead. Also append whether \p Pass is loop-nest pass or not

  /// to the end of \var IsLoopNestPass so we can easily identify the types of

  /// passes in the pass manager later.

  template <typename PassT>

  LLVM_ATTRIBUTE_MINSIZE

      std::enable_if_t<is_detected<HasRunOnLoopT, PassT>::value>

      addPass(PassT &&Pass) {

    using LoopPassModelT =

        detail::PassModel<Loop, PassT, PreservedAnalyses, LoopAnalysisManager,

                          LoopStandardAnalysisResults &, LPMUpdater &>;

    IsLoopNestPass.push_back(false);

    // Do not use make_unique or emplace_back, they cause too many template

    // instantiations, causing terrible compile times.

    LoopPasses.push_back(std::unique_ptr<LoopPassConceptT>(

        new LoopPassModelT(std::forward<PassT>(Pass))));

  }

  template <typename PassT>

  LLVM_ATTRIBUTE_MINSIZE

      std::enable_if_t<!is_detected<HasRunOnLoopT, PassT>::value>

      addPass(PassT &&Pass) {

    using LoopNestPassModelT =

        detail::PassModel<LoopNest, PassT, PreservedAnalyses,

                          LoopAnalysisManager, LoopStandardAnalysisResults &,

                          LPMUpdater &>;

    IsLoopNestPass.push_back(true);

    // Do not use make_unique or emplace_back, they cause too many template

    // instantiations, causing terrible compile times.

    LoopNestPasses.push_back(std::unique_ptr<LoopNestPassConceptT>(

        new LoopNestPassModelT(std::forward<PassT>(Pass))));

  }

  // Specializations of `addPass` for `RepeatedPass`. These are necessary since

  // `RepeatedPass` has a templated `run` method that will result in incorrect

  // detection of `HasRunOnLoopT`.

  template <typename PassT>

  LLVM_ATTRIBUTE_MINSIZE

      std::enable_if_t<is_detected<HasRunOnLoopT, PassT>::value>

      addPass(RepeatedPass<PassT> &&Pass) {

    using RepeatedLoopPassModelT =

        detail::PassModel<Loop, RepeatedPass<PassT>, PreservedAnalyses,

                          LoopAnalysisManager, LoopStandardAnalysisResults &,

                          LPMUpdater &>;

    IsLoopNestPass.push_back(false);

    // Do not use make_unique or emplace_back, they cause too many template

    // instantiations, causing terrible compile times.

    LoopPasses.push_back(std::unique_ptr<LoopPassConceptT>(

        new RepeatedLoopPassModelT(std::move(Pass))));

  }

  template <typename PassT>

  LLVM_ATTRIBUTE_MINSIZE

      std::enable_if_t<!is_detected<HasRunOnLoopT, PassT>::value>

      addPass(RepeatedPass<PassT> &&Pass) {

    using RepeatedLoopNestPassModelT =

        detail::PassModel<LoopNest, RepeatedPass<PassT>, PreservedAnalyses,

                          LoopAnalysisManager, LoopStandardAnalysisResults &,

                          LPMUpdater &>;

    IsLoopNestPass.push_back(true);

    // Do not use make_unique or emplace_back, they cause too many template

    // instantiations, causing terrible compile times.

    LoopNestPasses.push_back(std::unique_ptr<LoopNestPassConceptT>(

        new RepeatedLoopNestPassModelT(std::move(Pass))));

  }

  bool isEmpty() const { return LoopPasses.empty() && LoopNestPasses.empty(); }

  static bool isRequired() { return true; }

  size_t getNumLoopPasses() const { return LoopPasses.size(); }

  size_t getNumLoopNestPasses() const { return LoopNestPasses.size(); }

protected:

  using LoopPassConceptT =

      detail::PassConcept<Loop, LoopAnalysisManager,

                          LoopStandardAnalysisResults &, LPMUpdater &>;

  using LoopNestPassConceptT =

      detail::PassConcept<LoopNest, LoopAnalysisManager,

                          LoopStandardAnalysisResults &, LPMUpdater &>;

  // BitVector that identifies whether the passes are loop passes or loop-nest

  // passes (true for loop-nest passes).

  BitVector IsLoopNestPass;

  std::vector<std::unique_ptr<LoopPassConceptT>> LoopPasses;

  std::vector<std::unique_ptr<LoopNestPassConceptT>> LoopNestPasses;

  /// Run either a loop pass or a loop-nest pass. Returns `std::nullopt` if

  /// PassInstrumentation's BeforePass returns false. Otherwise, returns the

  /// preserved analyses of the pass.

  template <typename IRUnitT, typename PassT>

  std::optional<PreservedAnalyses>

  runSinglePass(IRUnitT &IR, PassT &Pass, LoopAnalysisManager &AM,

                LoopStandardAnalysisResults &AR, LPMUpdater &U,

                PassInstrumentation &PI);

  PreservedAnalyses runWithLoopNestPasses(Loop &L, LoopAnalysisManager &AM,

                                          LoopStandardAnalysisResults &AR,

                                          LPMUpdater &U);

  PreservedAnalyses runWithoutLoopNestPasses(Loop &L, LoopAnalysisManager &AM,

                                             LoopStandardAnalysisResults &AR,

                                             LPMUpdater &U);

private:

  static const Loop &getLoopFromIR(Loop &L) { return L; }

  static const Loop &getLoopFromIR(LoopNest &LN) {

    return LN.getOutermostLoop();

  }

};

/// The Loop pass manager.

///

/// See the documentation for the PassManager template for details. It runs

/// a sequence of Loop passes over each Loop that the manager is run over. This

/// typedef serves as a convenient way to refer to this construct.

typedef PassManager<Loop, LoopAnalysisManager, LoopStandardAnalysisResults &,

                    LPMUpdater &>

    LoopPassManager;

/// A partial specialization of the require analysis template pass to forward

/// the extra parameters from a transformation's run method to the

/// AnalysisManager's getResult.

template <typename AnalysisT>

struct RequireAnalysisPass<AnalysisT, Loop, LoopAnalysisManager,

                           LoopStandardAnalysisResults &, LPMUpdater &>

    : PassInfoMixin<

          RequireAnalysisPass<AnalysisT, Loop, LoopAnalysisManager,

                              LoopStandardAnalysisResults &, LPMUpdater &>> {

  PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM,

                        LoopStandardAnalysisResults &AR, LPMUpdater &) {

    (void)AM.template getResult<AnalysisT>(L, AR);

    return PreservedAnalyses::all();

  }

  void printPipeline(raw_ostream &OS,

                     function_ref<StringRef(StringRef)> MapClassName2PassName) {

    auto ClassName = AnalysisT::name();

    auto PassName = MapClassName2PassName(ClassName);

    OS << "require<" << PassName << ">";

  }

};

/// An alias template to easily name a require analysis loop pass.

template <typename AnalysisT>

using RequireAnalysisLoopPass =

    RequireAnalysisPass<AnalysisT, Loop, LoopAnalysisManager,

                        LoopStandardAnalysisResults &, LPMUpdater &>;

class FunctionToLoopPassAdaptor;

/// This class provides an interface for updating the loop pass manager based

/// on mutations to the loop nest.

///

/// A reference to an instance of this class is passed as an argument to each

/// Loop pass, and Loop passes should use it to update LPM infrastructure if

/// they modify the loop nest structure.

///

/// \c LPMUpdater comes with two modes: the loop mode and the loop-nest mode. In

/// loop mode, all the loops in the function will be pushed into the worklist

/// and when new loops are added to the pipeline, their subloops are also

/// inserted recursively. On the other hand, in loop-nest mode, only top-level

/// loops are contained in the worklist and the addition of new (top-level)

/// loops will not trigger the addition of their subloops.

class LPMUpdater {

public:

  /// This can be queried by loop passes which run other loop passes (like pass

  /// managers) to know whether the loop needs to be skipped due to updates to

  /// the loop nest.

  ///

  /// If this returns true, the loop object may have been deleted, so passes

  /// should take care not to touch the object.

  bool skipCurrentLoop() const { return SkipCurrentLoop; }

  /// Loop passes should use this method to indicate they have deleted a loop

  /// from the nest.

  ///

  /// Note that this loop must either be the current loop or a subloop of the

  /// current loop. This routine must be called prior to removing the loop from

  /// the loop nest.

  ///

  /// If this is called for the current loop, in addition to clearing any

  /// state, this routine will mark that the current loop should be skipped by

  /// the rest of the pass management infrastructure.

  void markLoopAsDeleted(Loop &L, llvm::StringRef Name) {

    LAM.clear(L, Name);

    assert((&L == CurrentL || CurrentL->contains(&L)) &&

           "Cannot delete a loop outside of the "

           "subloop tree currently being processed.");

    if (&L == CurrentL)

      SkipCurrentLoop = true;

  }

  void setParentLoop(Loop *L) {

#ifdef LLVM_ENABLE_ABI_BREAKING_CHECKS

    ParentL = L;

#endif

  }

  /// Loop passes should use this method to indicate they have added new child

  /// loops of the current loop.

  ///

  /// \p NewChildLoops must contain only the immediate children. Any nested

  /// loops within them will be visited in postorder as usual for the loop pass

  /// manager.

  void addChildLoops(ArrayRef<Loop *> NewChildLoops) {

    assert(!LoopNestMode &&

           "Child loops should not be pushed in loop-nest mode.");

    // Insert ourselves back into the worklist first, as this loop should be

    // revisited after all the children have been processed.

    Worklist.insert(CurrentL);

#ifndef NDEBUG

    for (Loop *NewL : NewChildLoops)

      assert(NewL->getParentLoop() == CurrentL && "All of the new loops must "

                                                  "be immediate children of "

                                                  "the current loop!");

#endif

    appendLoopsToWorklist(NewChildLoops, Worklist);

    // Also skip further processing of the current loop--it will be revisited

    // after all of its newly added children are accounted for.

    SkipCurrentLoop = true;

  }

  /// Loop passes should use this method to indicate they have added new

  /// sibling loops to the current loop.

  ///

  /// \p NewSibLoops must only contain the immediate sibling loops. Any nested

  /// loops within them will be visited in postorder as usual for the loop pass

  /// manager.

  void addSiblingLoops(ArrayRef<Loop *> NewSibLoops) {

#if defined(LLVM_ENABLE_ABI_BREAKING_CHECKS) && !defined(NDEBUG)

    for (Loop *NewL : NewSibLoops)

      assert(NewL->getParentLoop() == ParentL &&

             "All of the new loops must be siblings of the current loop!");

#endif

    if (LoopNestMode)

      Worklist.insert(NewSibLoops);

    else

      appendLoopsToWorklist(NewSibLoops, Worklist);

    // No need to skip the current loop or revisit it, as sibling loops

    // shouldn't impact anything.

  }

  /// Restart the current loop.

  ///

  /// Loop passes should call this method to indicate the current loop has been

  /// sufficiently changed that it should be re-visited from the begining of

  /// the loop pass pipeline rather than continuing.

  void revisitCurrentLoop() {

    // Tell the currently in-flight pipeline to stop running.

    SkipCurrentLoop = true;

    // And insert ourselves back into the worklist.

    Worklist.insert(CurrentL);

  }

  bool isLoopNestChanged() const {

    return LoopNestChanged;

  }

  /// Loopnest passes should use this method to indicate if the

  /// loopnest has been modified.

  void markLoopNestChanged(bool Changed) {

    LoopNestChanged = Changed;

  }

private:

  friend class llvm::FunctionToLoopPassAdaptor;

  /// The \c FunctionToLoopPassAdaptor's worklist of loops to process.

  SmallPriorityWorklist<Loop *, 4> &Worklist;

  /// The analysis manager for use in the current loop nest.

  LoopAnalysisManager &LAM;

  Loop *CurrentL;

  bool SkipCurrentLoop;

  const bool LoopNestMode;

  bool LoopNestChanged;

#ifdef LLVM_ENABLE_ABI_BREAKING_CHECKS

  // In debug builds we also track the parent loop to implement asserts even in

  // the face of loop deletion.

  Loop *ParentL;

#endif

  LPMUpdater(SmallPriorityWorklist<Loop *, 4> &Worklist,

             LoopAnalysisManager &LAM, bool LoopNestMode = false,

             bool LoopNestChanged = false)

      : Worklist(Worklist), LAM(LAM), LoopNestMode(LoopNestMode),

        LoopNestChanged(LoopNestChanged) {}

};

template <typename IRUnitT, typename PassT>

std::optional<PreservedAnalyses> LoopPassManager::runSinglePass(

    IRUnitT &IR, PassT &Pass, LoopAnalysisManager &AM,

    LoopStandardAnalysisResults &AR, LPMUpdater &U, PassInstrumentation &PI) {

  // Get the loop in case of Loop pass and outermost loop in case of LoopNest

  // pass which is to be passed to BeforePass and AfterPass call backs.

  const Loop &L = getLoopFromIR(IR);

  // Check the PassInstrumentation's BeforePass callbacks before running the

  // pass, skip its execution completely if asked to (callback returns false).

  if (!PI.runBeforePass<Loop>(*Pass, L))

    return std::nullopt;

  PreservedAnalyses PA = Pass->run(IR, AM, AR, U);

  // do not pass deleted Loop into the instrumentation

  if (U.skipCurrentLoop())

    PI.runAfterPassInvalidated<IRUnitT>(*Pass, PA);

  else

    PI.runAfterPass<Loop>(*Pass, L, PA);

  return PA;

}

/// Adaptor that maps from a function to its loops.

///

/// Designed to allow composition of a LoopPass(Manager) and a

/// FunctionPassManager. Note that if this pass is constructed with a \c

/// FunctionAnalysisManager it will run the \c LoopAnalysisManagerFunctionProxy

/// analysis prior to running the loop passes over the function to enable a \c

/// LoopAnalysisManager to be used within this run safely.

///

/// The adaptor comes with two modes: the loop mode and the loop-nest mode, and

/// the worklist updater lived inside will be in the same mode as the adaptor

/// (refer to the documentation of \c LPMUpdater for more detailed explanation).

/// Specifically, in loop mode, all loops in the funciton will be pushed into

/// the worklist and processed by \p Pass, while only top-level loops are

/// processed in loop-nest mode. Please refer to the various specializations of

/// \fn createLoopFunctionToLoopPassAdaptor to see when loop mode and loop-nest

/// mode are used.

class FunctionToLoopPassAdaptor

    : public PassInfoMixin<FunctionToLoopPassAdaptor> {

public:

  using PassConceptT =

      detail::PassConcept<Loop, LoopAnalysisManager,

                          LoopStandardAnalysisResults &, LPMUpdater &>;

  explicit FunctionToLoopPassAdaptor(std::unique_ptr<PassConceptT> Pass,

                                     bool UseMemorySSA = false,

                                     bool UseBlockFrequencyInfo = false,

                                     bool UseBranchProbabilityInfo = false,

                                     bool LoopNestMode = false)

      : Pass(std::move(Pass)), UseMemorySSA(UseMemorySSA),

        UseBlockFrequencyInfo(UseBlockFrequencyInfo),

        UseBranchProbabilityInfo(UseBranchProbabilityInfo),

        LoopNestMode(LoopNestMode) {

    LoopCanonicalizationFPM.addPass(LoopSimplifyPass());

    LoopCanonicalizationFPM.addPass(LCSSAPass());

  }

  /// Runs the loop passes across every loop in the function.

  PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);

  void printPipeline(raw_ostream &OS,

                     function_ref<StringRef(StringRef)> MapClassName2PassName);

  static bool isRequired() { return true; }

  bool isLoopNestMode() const { return LoopNestMode; }

private:

  std::unique_ptr<PassConceptT> Pass;

  FunctionPassManager LoopCanonicalizationFPM;

  bool UseMemorySSA = false;

  bool UseBlockFrequencyInfo = false;

  bool UseBranchProbabilityInfo = false;

  const bool LoopNestMode;

};

/// A function to deduce a loop pass type and wrap it in the templated

/// adaptor.

///

/// If \p Pass is a loop pass, the returned adaptor will be in loop mode.

template <typename LoopPassT>

inline std::enable_if_t<is_detected<HasRunOnLoopT, LoopPassT>::value,

                        FunctionToLoopPassAdaptor>

createFunctionToLoopPassAdaptor(LoopPassT &&Pass, bool UseMemorySSA = false,

                                bool UseBlockFrequencyInfo = false,

                                bool UseBranchProbabilityInfo = false) {

  using PassModelT =

      detail::PassModel<Loop, LoopPassT, PreservedAnalyses, LoopAnalysisManager,

                        LoopStandardAnalysisResults &, LPMUpdater &>;

  // Do not use make_unique, it causes too many template instantiations,

  // causing terrible compile times.

  return FunctionToLoopPassAdaptor(

      std::unique_ptr<FunctionToLoopPassAdaptor::PassConceptT>(

          new PassModelT(std::forward<LoopPassT>(Pass))),

      UseMemorySSA, UseBlockFrequencyInfo, UseBranchProbabilityInfo, false);

}

/// If \p Pass is a loop-nest pass, \p Pass will first be wrapped into a

/// \c LoopPassManager and the returned adaptor will be in loop-nest mode.

template <typename LoopNestPassT>

inline std::enable_if_t<!is_detected<HasRunOnLoopT, LoopNestPassT>::value,

                        FunctionToLoopPassAdaptor>

createFunctionToLoopPassAdaptor(LoopNestPassT &&Pass, bool UseMemorySSA = false,

                                bool UseBlockFrequencyInfo = false,

                                bool UseBranchProbabilityInfo = false) {

  LoopPassManager LPM;

  LPM.addPass(std::forward<LoopNestPassT>(Pass));

  using PassModelT =

      detail::PassModel<Loop, LoopPassManager, PreservedAnalyses,

                        LoopAnalysisManager, LoopStandardAnalysisResults &,

                        LPMUpdater &>;

  // Do not use make_unique, it causes too many template instantiations,

  // causing terrible compile times.

  return FunctionToLoopPassAdaptor(

      std::unique_ptr<FunctionToLoopPassAdaptor::PassConceptT>(

          new PassModelT(std::move(LPM))),

      UseMemorySSA, UseBlockFrequencyInfo, UseBranchProbabilityInfo, true);

}

/// If \p Pass is an instance of \c LoopPassManager, the returned adaptor will

/// be in loop-nest mode if the pass manager contains only loop-nest passes.

template <>

inline FunctionToLoopPassAdaptor

createFunctionToLoopPassAdaptor<LoopPassManager>(

    LoopPassManager &&LPM, bool UseMemorySSA, bool UseBlockFrequencyInfo,

    bool UseBranchProbabilityInfo) {

  // Check if LPM contains any loop pass and if it does not, returns an adaptor

  // in loop-nest mode.

  using PassModelT =

      detail::PassModel<Loop, LoopPassManager, PreservedAnalyses,

                        LoopAnalysisManager, LoopStandardAnalysisResults &,

                        LPMUpdater &>;

  bool LoopNestMode = (LPM.getNumLoopPasses() == 0);

  // Do not use make_unique, it causes too many template instantiations,

  // causing terrible compile times.

  return FunctionToLoopPassAdaptor(

      std::unique_ptr<FunctionToLoopPassAdaptor::PassConceptT>(

          new PassModelT(std::move(LPM))),

      UseMemorySSA, UseBlockFrequencyInfo, UseBranchProbabilityInfo,

      LoopNestMode);

}

/// Pass for printing a loop's contents as textual IR.

class PrintLoopPass : public PassInfoMixin<PrintLoopPass> {

  raw_ostream &OS;

  std::string Banner;

public:

  PrintLoopPass();

  PrintLoopPass(raw_ostream &OS, const std::string &Banner = "");

  PreservedAnalyses run(Loop &L, LoopAnalysisManager &,

                        LoopStandardAnalysisResults &, LPMUpdater &);

};

}

#endif // LLVM_TRANSFORMS_SCALAR_LOOPPASSMANAGER_H