path: root/contrib/libs/llvm12/include/llvm/Transforms/Scalar/LoopPassManager.h

#pragma once

#ifdef __GNUC__
#pragma GCC diagnostic push
#pragma GCC diagnostic ignored "-Wunused-parameter"
#endif

//===- 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/Dominators.h"
#include "llvm/IR/PassInstrumentation.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;

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: 
  /// Construct a pass manager. 
  /// 
  /// If \p DebugLogging is true, we'll log our progress to llvm::dbgs(). 
  explicit PassManager(bool DebugLogging = false) 
      : DebugLogging(DebugLogging) {} 

  // 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)), 
        DebugLogging(std::move(Arg.DebugLogging)) {} 
 
  PassManager &operator=(PassManager &&RHS) { 
    IsLoopNestPass = std::move(RHS.IsLoopNestPass); 
    LoopPasses = std::move(RHS.LoopPasses); 
    LoopNestPasses = std::move(RHS.LoopNestPasses); 
    DebugLogging = std::move(RHS.DebugLogging); 
    return *this; 
  } 
 
  PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM, 
                        LoopStandardAnalysisResults &AR, LPMUpdater &U); 
 
  /// 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> 
  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); 
    LoopPasses.emplace_back(new LoopPassModelT(std::move(Pass))); 
  } 
 
  template <typename PassT> 
  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); 
    LoopNestPasses.emplace_back(new LoopNestPassModelT(std::move(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> 
  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); 
    LoopPasses.emplace_back(new RepeatedLoopPassModelT(std::move(Pass))); 
  } 
 
  template <typename PassT> 
  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); 
    LoopNestPasses.emplace_back( 
        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; 
 
  /// Flag indicating whether we should do debug logging. 
  bool DebugLogging; 
 
  /// Run either a loop pass or a loop-nest pass. Returns `None` if 
  /// PassInstrumentation's BeforePass returns false. Otherwise, returns the 
  /// preserved analyses of the pass. 
  template <typename IRUnitT, typename PassT> 
  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); 
}; 
 
/// 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();
  }
};

/// 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) {
    assert((!LoopNestMode || L.isOutermost()) && 
           "L should be a top-level loop in loop-nest mode."); 
    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;
  }

  /// 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) {
#ifndef 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);
  }

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; 

#ifndef NDEBUG
  // 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) 
      : Worklist(Worklist), LAM(LAM), LoopNestMode(LoopNestMode) {} 
};

template <typename IRUnitT, typename PassT> 
Optional<PreservedAnalyses> LoopPassManager::runSinglePass( 
    IRUnitT &IR, PassT &Pass, LoopAnalysisManager &AM, 
    LoopStandardAnalysisResults &AR, LPMUpdater &U, PassInstrumentation &PI) { 
  // Check the PassInstrumentation's BeforePass callbacks before running the 
  // pass, skip its execution completely if asked to (callback returns false). 
  if (!PI.runBeforePass<IRUnitT>(*Pass, IR)) 
    return None; 
 
  PreservedAnalyses PA; 
  { 
    TimeTraceScope TimeScope(Pass->name(), IR.getName()); 
    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<IRUnitT>(*Pass, IR, 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 DebugLogging = false, 
                                     bool LoopNestMode = false) 
      : Pass(std::move(Pass)), LoopCanonicalizationFPM(DebugLogging),
        UseMemorySSA(UseMemorySSA), 
        UseBlockFrequencyInfo(UseBlockFrequencyInfo), 
        LoopNestMode(LoopNestMode) { 
    LoopCanonicalizationFPM.addPass(LoopSimplifyPass());
    LoopCanonicalizationFPM.addPass(LCSSAPass());
  }

  /// Runs the loop passes across every loop in the function.
  PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); 

  static bool isRequired() { return true; } 

  bool isLoopNestMode() const { return LoopNestMode; } 

private:
  std::unique_ptr<PassConceptT> Pass; 

  FunctionPassManager LoopCanonicalizationFPM;

  bool UseMemorySSA = false;
  bool UseBlockFrequencyInfo = 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 DebugLogging = false) {
  using PassModelT = 
      detail::PassModel<Loop, LoopPassT, PreservedAnalyses, LoopAnalysisManager, 
                        LoopStandardAnalysisResults &, LPMUpdater &>; 
  return FunctionToLoopPassAdaptor( 
      std::make_unique<PassModelT>(std::move(Pass)), UseMemorySSA, 
      UseBlockFrequencyInfo, DebugLogging, 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 DebugLogging = false) { 
  LoopPassManager LPM(DebugLogging); 
  LPM.addPass(std::move(Pass)); 
  using PassModelT = 
      detail::PassModel<Loop, LoopPassManager, PreservedAnalyses, 
                        LoopAnalysisManager, LoopStandardAnalysisResults &, 
                        LPMUpdater &>; 
  return FunctionToLoopPassAdaptor(std::make_unique<PassModelT>(std::move(LPM)), 
                                   UseMemorySSA, UseBlockFrequencyInfo, 
                                   DebugLogging, 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 DebugLogging) { 
  // 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); 
  return FunctionToLoopPassAdaptor(std::make_unique<PassModelT>(std::move(LPM)), 
                                   UseMemorySSA, UseBlockFrequencyInfo, 
                                   DebugLogging, 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

#ifdef __GNUC__
#pragma GCC diagnostic pop
#endif