[Polly] Migrate -polly-mse to the new pass manager.

[YangKeao]

Summary

This patch implements the MaximalStaticExpansion and its printer in NPM.

[YangKeao]

rebase to the master

[YangKeao]

Format codes

[Meinersbur]

LGTM

Would you like me to commit for you?

polly/lib/Transform/MaximalStaticExpansion.cpp

520

[style] Unnecessary parens.

526

[style] No almost-always-auto.

Here it helps to see that MaximalStaticExpansionImpl will be released by RAII

[YangKeao]

Would you like me to commit for you?

@Meinersbur Sure! Thanks! 🍻

[Meinersbur]

There were two compiler warnings I fixed before committing:

In file included from /home/meinersbur/src/llvm-project/polly/lib/Transform/MaximalStaticExpansion.cpp:14:
/home/meinersbur/src/llvm-project/polly/include/polly/MaximalStaticExpansion.h:14:9: warning: 'POLLY_MAXIMALSTATICEXPANSION_H' is used as a header guard here, followed by #define of a different macro [-Wheader-guard]
#ifndef POLLY_MAXIMALSTATICEXPANSION_H
        ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/home/meinersbur/src/llvm-project/polly/include/polly/MaximalStaticExpansion.h:15:9: note: 'POLLY_MAXIMALSTATICEXPANSIO_H' is defined here; did you mean 'POLLY_MAXIMALSTATICEXPANSION_H'?
#define POLLY_MAXIMALSTATICEXPANSIO_H
        ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
        POLLY_MAXIMALSTATICEXPANSION_H
/home/meinersbur/src/llvm-project/polly/lib/Transform/MaximalStaticExpansion.cpp:414:15: warning: field 'Dependences' will be initialized after field 'ORE' [-Wreorder-ctor]
      : S(S), Dependences(Dependences), ORE(ORE) {}
        ~~~~  ^~~~~~~~~~~~~~~~~~~~~~~~  ~~~~~~~~
        ORE(ORE) S(S)                   Dependences(Dependences)
2 warnings generated.

polly/include/polly/LinkAllPasses.h

 void initializeIslAstInfoPrinterLegacyPassPass(llvm::PassRegistry &);
 void initializeCodeGenerationPass(llvm::PassRegistry &);
 #ifdef GPU_CODEGEN
 void initializePPCGCodeGenerationPass(llvm::PassRegistry &);
 void initializeManagedMemoryRewritePassPass(llvm::PassRegistry &);
 #endif
 void initializeIslScheduleOptimizerWrapperPassPass(llvm::PassRegistry &);
 void initializeIslScheduleOptimizerPrinterLegacyPassPass(llvm::PassRegistry &);
-void initializeMaximalStaticExpanderPass(llvm::PassRegistry &);
+void initializeMaximalStaticExpanderWrapperPassPass(llvm::PassRegistry &);
 void initializePollyCanonicalizePass(llvm::PassRegistry &);
 void initializeFlattenSchedulePass(llvm::PassRegistry &);
 void initializeFlattenSchedulePrinterLegacyPassPass(llvm::PassRegistry &);
 void initializeForwardOpTreeWrapperPassPass(llvm::PassRegistry &);
 void initializeForwardOpTreePrinterLegacyPassPass(PassRegistry &);
 void initializeDeLICMWrapperPassPass(llvm::PassRegistry &);
 void initializeDeLICMPrinterLegacyPassPass(llvm::PassRegistry &);
 void initializeSimplifyWrapperPassPass(llvm::PassRegistry &);
 void initializeSimplifyPrinterLegacyPassPass(llvm::PassRegistry &);
 void initializePruneUnprofitableWrapperPassPass(llvm::PassRegistry &);
 void initializePolyhedralInfoPass(llvm::PassRegistry &);
 void initializePolyhedralInfoPrinterLegacyPassPass(llvm::PassRegistry &);
 } // namespace llvm
 
 #endif

polly/include/polly/MaximalStaticExpansion.h

+//===- polly/MaximalStaticExpansion.h - expand memory access -*- 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
+//
+//===----------------------------------------------------------------------===//
+//
+// This pass fully expand the memory accesses of a Scop to get rid of
+// dependencies.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef POLLY_MAXIMALSTATICEXPANSION_H
+#define POLLY_MAXIMALSTATICEXPANSIO_H
+
+#include "polly/ScopPass.h"
+#include "llvm/IR/PassManager.h"
+
+namespace polly {
+
+class MaximalStaticExpansionPass
+    : public llvm::PassInfoMixin<MaximalStaticExpansionPass> {
+public:
+  llvm::PreservedAnalyses run(Scop &, ScopAnalysisManager &,
+                              ScopStandardAnalysisResults &, SPMUpdater &);
+};
+
+struct MaximalStaticExpansionPrinterPass
+    : llvm::PassInfoMixin<MaximalStaticExpansionPrinterPass> {
+  MaximalStaticExpansionPrinterPass(raw_ostream &OS) : OS(OS) {}
+
+  PreservedAnalyses run(Scop &S, ScopAnalysisManager &,
+                        ScopStandardAnalysisResults &SAR, SPMUpdater &);
+
+private:
+  llvm::raw_ostream &OS;
+};
+
+} // namespace polly
+
+#endif /* POLLY_MAXIMALSTATICEXPANSION_H */

polly/lib/Support/PollyPasses.def

 SCOP_PASS("polly-optree", ForwardOpTreePass())
 SCOP_PASS("print<polly-optree>", ForwardOpTreePrinterPass(llvm::outs()))
 SCOP_PASS("polly-delicm", DeLICMPass())
 SCOP_PASS("print<polly-delicm>", DeLICMPrinterPass(llvm::outs()))
 SCOP_PASS("polly-prune-unprofitable", PruneUnprofitablePass())
 SCOP_PASS("polly-opt-isl", IslScheduleOptimizerPass())
 SCOP_PASS("print<polly-opt-isl>", IslScheduleOptimizerPrinterPass(llvm::outs()))
 SCOP_PASS("polly-dce", DeadCodeElimPass())
+SCOP_PASS("polly-mse", MaximalStaticExpansionPass())
+SCOP_PASS("print<polly-mse>", MaximalStaticExpansionPrinterPass(llvm::outs()))
 #undef SCOP_PASS

polly/lib/Support/RegisterPasses.cpp

 #include "polly/CodeGen/IslAst.h"
 #include "polly/CodePreparation.h"
 #include "polly/DeLICM.h"
 #include "polly/DeadCodeElimination.h"
 #include "polly/DependenceInfo.h"
 #include "polly/ForwardOpTree.h"
 #include "polly/JSONExporter.h"
 #include "polly/LinkAllPasses.h"
+#include "polly/MaximalStaticExpansion.h"
 #include "polly/PolyhedralInfo.h"
 #include "polly/PruneUnprofitable.h"
 #include "polly/ScheduleOptimizer.h"
 #include "polly/ScopDetection.h"
 #include "polly/ScopGraphPrinter.h"
 #include "polly/ScopInfo.h"
 #include "polly/Simplify.h"
 #include "polly/Support/DumpFunctionPass.h"
#endif
   initializeDeadCodeElimWrapperPassPass(Registry);
   initializeDependenceInfoPass(Registry);
   initializeDependenceInfoPrinterLegacyPassPass(Registry);
   initializeDependenceInfoWrapperPassPass(Registry);
   initializeDependenceInfoPrinterLegacyFunctionPassPass(Registry);
   initializeJSONExporterPass(Registry);
   initializeJSONImporterPass(Registry);
   initializeJSONImporterPrinterLegacyPassPass(Registry);
-  initializeMaximalStaticExpanderPass(Registry);
+  initializeMaximalStaticExpanderWrapperPassPass(Registry);
   initializeIslAstInfoWrapperPassPass(Registry);
   initializeIslAstInfoPrinterLegacyPassPass(Registry);
   initializeIslScheduleOptimizerWrapperPassPass(Registry);
   initializeIslScheduleOptimizerPrinterLegacyPassPass(Registry);
   initializePollyCanonicalizePass(Registry);
   initializePolyhedralInfoPass(Registry);
   initializePolyhedralInfoPrinterLegacyPassPass(Registry);
   initializeScopDetectionWrapperPassPass(Registry);

polly/lib/Transform/MaximalStaticExpansion.cpp

 //===- MaximalStaticExpansion.cpp -----------------------------------------===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 //
 // This pass fully expand the memory accesses of a Scop to get rid of
 // dependencies.
 //
 //===----------------------------------------------------------------------===//
 
+#include "polly/MaximalStaticExpansion.h"
 #include "polly/DependenceInfo.h"
 #include "polly/LinkAllPasses.h"
 #include "polly/ScopInfo.h"
 #include "polly/ScopPass.h"
 #include "polly/Support/ISLTools.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Analysis/OptimizationRemarkEmitter.h"
 #include "llvm/InitializePasses.h"
 #include "isl/isl-noexceptions.h"
 #include "isl/union_map.h"
 #include <cassert>
 #include <limits>
 #include <string>
 #include <vector>
 
 using namespace llvm;
 using namespace polly;
 
 #define DEBUG_TYPE "polly-mse"
 
 namespace {
 
-class MaximalStaticExpander final : public ScopPass {
+class MaximalStaticExpanderWrapperPass final : public ScopPass {
 public:
   static char ID;
 
-  explicit MaximalStaticExpander() : ScopPass(ID) {}
+  explicit MaximalStaticExpanderWrapperPass() : ScopPass(ID) {}
 
-  ~MaximalStaticExpander() override = default;
+  ~MaximalStaticExpanderWrapperPass() override = default;
 
   /// Expand the accesses of the SCoP.
   ///
   /// @param S The SCoP that must be expanded.
   bool runOnScop(Scop &S) override;
 
   /// Print the SCoP.
   ///
   /// @param OS The stream where to print.
   /// @param S The SCop that must be printed.
   void printScop(raw_ostream &OS, Scop &S) const override;
 
   /// Register all analyses and transformations required.
   void getAnalysisUsage(AnalysisUsage &AU) const override;
-
-private:
-  /// OptimizationRemarkEmitter object for displaying diagnostic remarks.
-  OptimizationRemarkEmitter *ORE;
-
-  /// Emit remark
-  void emitRemark(StringRef Msg, Instruction *Inst);
-
-  /// Return true if the SAI in parameter is expandable.
-  ///
-  /// @param SAI the SAI that need to be checked.
-  /// @param Writes A set that will contains all the write accesses.
-  /// @param Reads A set that will contains all the read accesses.
-  /// @param S The SCop in which the SAI is in.
-  /// @param Dependences The RAW dependences of the SCop.
-  bool isExpandable(const ScopArrayInfo *SAI,
-                    SmallPtrSetImpl<MemoryAccess *> &Writes,
-                    SmallPtrSetImpl<MemoryAccess *> &Reads, Scop &S,
-                    const isl::union_map &Dependences);
-
-  /// Expand the MemoryAccess according to its domain.
-  ///
-  /// @param S The SCop in which the memory access appears in.
-  /// @param MA The memory access that need to be expanded.
-  ScopArrayInfo *expandAccess(Scop &S, MemoryAccess *MA);
-
-  /// Filter the dependences to have only one related to current memory access.
-  ///
-  /// @param S The SCop in which the memory access appears in.
-  /// @param MapDependences The dependences to filter.
-  /// @param MA The memory access that need to be expanded.
-  isl::union_map filterDependences(Scop &S,
-                                   const isl::union_map &MapDependences,
-                                   MemoryAccess *MA);
-
-  /// Expand the MemoryAccess according to Dependences and already expanded
-  /// MemoryAccesses.
-  ///
-  /// @param The SCop in which the memory access appears in.
-  /// @param The memory access that need to be expanded.
-  /// @param Dependences The RAW dependences of the SCop.
-  /// @param ExpandedSAI The expanded SAI created during write expansion.
-  /// @param Reverse if true, the Dependences union_map is reversed before
-  /// intersection.
-  void mapAccess(Scop &S, SmallPtrSetImpl<MemoryAccess *> &Accesses,
-                 const isl::union_map &Dependences, ScopArrayInfo *ExpandedSAI,
-                 bool Reverse);
-
-  /// Expand PHI memory accesses.
-  ///
-  /// @param The SCop in which the memory access appears in.
-  /// @param The ScopArrayInfo representing the PHI accesses to expand.
-  /// @param Dependences The RAW dependences of the SCop.
-  void expandPhi(Scop &S, const ScopArrayInfo *SAI,
-                 const isl::union_map &Dependences);
 };
-} // namespace
 
 #ifndef NDEBUG
 /// Whether a dimension of a set is bounded (lower and upper) by a constant,
 /// i.e. there are two constants Min and Max, such that every value x of the
 /// chosen dimensions is Min <= x <= Max.
 static bool isDimBoundedByConstant(isl::set Set, unsigned dim) {
   auto ParamDims = unsignedFromIslSize(Set.dim(isl::dim::param));
   Set = Set.project_out(isl::dim::param, 0, ParamDims);
   Set = Set.project_out(isl::dim::set, 0, dim);
   auto SetDims = unsignedFromIslSize(Set.tuple_dim());
   assert(SetDims >= 1);
   Set = Set.project_out(isl::dim::set, 1, SetDims - 1);
   return bool(Set.is_bounded());
 }
 #endif
 
-char MaximalStaticExpander::ID = 0;
+class MaximalStaticExpansionImpl {
+  OptimizationRemarkEmitter &ORE;
+  Scop &S;
+  isl::union_map &Dependences;
+
+  /// Emit remark
+  void emitRemark(StringRef Msg, Instruction *Inst) {
+    ORE.emit(OptimizationRemarkAnalysis(DEBUG_TYPE, "ExpansionRejection", Inst)
+             << Msg);
+  }
 
-isl::union_map MaximalStaticExpander::filterDependences(
-    Scop &S, const isl::union_map &Dependences, MemoryAccess *MA) {
+  /// Filter the dependences to have only one related to current memory access.
+  ///
+  /// @param S The SCop in which the memory access appears in.
+  /// @param MapDependences The dependences to filter.
+  /// @param MA The memory access that need to be expanded.
+  isl::union_map filterDependences(const isl::union_map &Dependences,
+                                   MemoryAccess *MA) {
     auto SAI = MA->getLatestScopArrayInfo();
 
     auto AccessDomainSet = MA->getAccessRelation().domain();
     auto AccessDomainId = AccessDomainSet.get_tuple_id();
 
     isl::union_map MapDependences = isl::union_map::empty(S.getIslCtx());
 
     for (isl::map Map : Dependences.get_map_list()) {
       // Filter out Statement to Statement dependences.
       if (!Map.can_curry())
         continue;
 
       // Intersect with the relevant SAI.
       auto TmpMapDomainId =
           Map.get_space().domain().unwrap().range().get_tuple_id(isl::dim::set);
 
       ScopArrayInfo *UserSAI =
           static_cast<ScopArrayInfo *>(TmpMapDomainId.get_user());
 
       if (SAI != UserSAI)
         continue;
 
       // Get the correct S1[] -> S2[] dependence.
       auto NewMap = Map.factor_domain();
       auto NewMapDomainId = NewMap.domain().get_tuple_id();
 
       if (AccessDomainId.get() != NewMapDomainId.get())
         continue;
 
       // Add the corresponding map to MapDependences.
       MapDependences = MapDependences.unite(NewMap);
     }
 
     return MapDependences;
   }
 
-bool MaximalStaticExpander::isExpandable(
-    const ScopArrayInfo *SAI, SmallPtrSetImpl<MemoryAccess *> &Writes,
-    SmallPtrSetImpl<MemoryAccess *> &Reads, Scop &S,
-    const isl::union_map &Dependences) {
+  /// Return true if the SAI in parameter is expandable.
+  ///
+  /// @param SAI the SAI that need to be checked.
+  /// @param Writes A set that will contains all the write accesses.
+  /// @param Reads A set that will contains all the read accesses.
+  /// @param S The SCop in which the SAI is in.
+  /// @param Dependences The RAW dependences of the SCop.
+  bool isExpandable(const ScopArrayInfo *SAI,
+                    SmallPtrSetImpl<MemoryAccess *> &Writes,
+                    SmallPtrSetImpl<MemoryAccess *> &Reads, Scop &S) {
     if (SAI->isValueKind()) {
       Writes.insert(S.getValueDef(SAI));
       for (auto MA : S.getValueUses(SAI))
         Reads.insert(MA);
       return true;
     } else if (SAI->isPHIKind()) {
       auto Read = S.getPHIRead(SAI);
 
       auto StmtDomain = isl::union_set(Read->getStatement()->getDomain());
 
       auto Writes = S.getPHIIncomings(SAI);
 
       // Get the domain where all the writes are writing to.
       auto WriteDomain = isl::union_set::empty(S.getIslCtx());
 
       for (auto Write : Writes) {
-      auto MapDeps = filterDependences(S, Dependences, Write);
+        auto MapDeps = filterDependences(Dependences, Write);
         for (isl::map Map : MapDeps.get_map_list())
           WriteDomain = WriteDomain.unite(Map.range());
       }
 
       // For now, read from original scalar is not possible.
       if (!StmtDomain.is_equal(WriteDomain)) {
         emitRemark(SAI->getName() + " read from its original value.",
                    Read->getAccessInstruction());
         return false;
       }
 
       return true;
     } else if (SAI->isExitPHIKind()) {
       // For now, we are not able to expand ExitPhi.
       emitRemark(SAI->getName() + " is a ExitPhi node.",
                  S.getEnteringBlock()->getFirstNonPHI());
       return false;
     }
 
     int NumberWrites = 0;
     for (ScopStmt &Stmt : S) {
       auto StmtReads = isl::union_map::empty(S.getIslCtx());
       auto StmtWrites = isl::union_map::empty(S.getIslCtx());
 
       for (MemoryAccess *MA : Stmt) {
         // Check if the current MemoryAccess involved the current SAI.
         if (SAI != MA->getLatestScopArrayInfo())
           continue;
 
         // For now, we are not able to expand array where read come after write
         // (to the same location) in a same statement.
         auto AccRel = isl::union_map(MA->getAccessRelation());
         if (MA->isRead()) {
           // Reject load after store to same location.
           if (!StmtWrites.is_disjoint(AccRel)) {
             emitRemark(SAI->getName() + " has read after write to the same "
                                         "element in same statement. The "
                                         "dependences found during analysis may "
                                         "be wrong because Polly is not able to "
                                         "handle such case for now.",
                        MA->getAccessInstruction());
             return false;
           }
 
           StmtReads = StmtReads.unite(AccRel);
         } else {
           StmtWrites = StmtWrites.unite(AccRel);
         }
 
         // For now, we are not able to expand MayWrite.
         if (MA->isMayWrite()) {
           emitRemark(SAI->getName() + " has a maywrite access.",
                      MA->getAccessInstruction());
           return false;
         }
 
         // For now, we are not able to expand SAI with more than one write.
         if (MA->isMustWrite()) {
           Writes.insert(MA);
           NumberWrites++;
           if (NumberWrites > 1) {
             emitRemark(SAI->getName() + " has more than 1 write access.",
                        MA->getAccessInstruction());
             return false;
           }
         }
 
         // Check if it is possible to expand this read.
         if (MA->isRead()) {
           // Get the domain of the current ScopStmt.
           auto StmtDomain = Stmt.getDomain();
 
           // Get the domain of the future Read access.
           auto ReadDomainSet = MA->getAccessRelation().domain();
           auto ReadDomain = isl::union_set(ReadDomainSet);
 
           // Get the dependences relevant for this MA
-        auto MapDependences = filterDependences(S, Dependences.reverse(), MA);
+          auto MapDependences = filterDependences(Dependences.reverse(), MA);
           unsigned NumberElementMap = isl_union_map_n_map(MapDependences.get());
 
           if (NumberElementMap == 0) {
             emitRemark("The expansion of " + SAI->getName() +
                            " would lead to a read from the original array.",
                        MA->getAccessInstruction());
             return false;
           }
 
           auto DepsDomain = MapDependences.domain();
 
           // If there are multiple maps in the Deps, we cannot handle this case
           // for now.
           if (NumberElementMap != 1) {
             emitRemark(SAI->getName() +
                            " has too many dependences to be handle for now.",
                        MA->getAccessInstruction());
             return false;
           }
 
           auto DepsDomainSet = isl::set(DepsDomain);
 
           // For now, read from the original array is not possible.
           if (!StmtDomain.is_subset(DepsDomainSet)) {
             emitRemark("The expansion of " + SAI->getName() +
                            " would lead to a read from the original array.",
                        MA->getAccessInstruction());
             return false;
           }
 
           Reads.insert(MA);
         }
       }
     }
 
     // No need to expand SAI with no write.
     if (NumberWrites == 0) {
       emitRemark(SAI->getName() + " has 0 write access.",
                  S.getEnteringBlock()->getFirstNonPHI());
       return false;
     }
 
     return true;
   }
 
-void MaximalStaticExpander::mapAccess(Scop &S,
-                                      SmallPtrSetImpl<MemoryAccess *> &Accesses,
-                                      const isl::union_map &Dependences,
-                                      ScopArrayInfo *ExpandedSAI,
-                                      bool Reverse) {
+  /// Expand the MemoryAccess according to Dependences and already expanded
+  /// MemoryAccesses.
+  ///
+  /// @param The SCop in which the memory access appears in.
+  /// @param The memory access that need to be expanded.
+  /// @param Dependences The RAW dependences of the SCop.
+  /// @param ExpandedSAI The expanded SAI created during write expansion.
+  /// @param Reverse if true, the Dependences union_map is reversed before
+  /// intersection.
+  void mapAccess(SmallPtrSetImpl<MemoryAccess *> &Accesses,
+                 const isl::union_map &Dependences, ScopArrayInfo *ExpandedSAI,
     for (auto MA : Accesses) {
       // Get the current AM.
       auto CurrentAccessMap = MA->getAccessRelation();
 
       // Get RAW dependences for the current WA.
       auto DomainSet = MA->getAccessRelation().domain();
       auto Domain = isl::union_set(DomainSet);
 
       // Get the dependences relevant for this MA.
       isl::union_map MapDependences =
-        filterDependences(S, Reverse ? Dependences.reverse() : Dependences, MA);
+          filterDependences(Reverse ? Dependences.reverse() : Dependences, MA);
 
       // If no dependences, no need to modify anything.
       if (MapDependences.is_empty())
         return;
 
       assert(isl_union_map_n_map(MapDependences.get()) == 1 &&
              "There are more than one RAW dependencies in the union map.");
       auto NewAccessMap = isl::map::from_union_map(MapDependences);
 
       auto Id = ExpandedSAI->getBasePtrId();
 
       // Replace the out tuple id with the one of the access array.
       NewAccessMap = NewAccessMap.set_tuple_id(isl::dim::out, Id);
 
       // Set the new access relation.
       MA->setNewAccessRelation(NewAccessMap);
     }
   }
 
-ScopArrayInfo *MaximalStaticExpander::expandAccess(Scop &S, MemoryAccess *MA) {
+  /// Expand the MemoryAccess according to its domain.
+  ///
+  /// @param S The SCop in which the memory access appears in.
+  /// @param MA The memory access that need to be expanded.
+  ScopArrayInfo *expandAccess(MemoryAccess *MA) {
     // Get the current AM.
     auto CurrentAccessMap = MA->getAccessRelation();
 
     unsigned in_dimensions =
         unsignedFromIslSize(CurrentAccessMap.domain_tuple_dim());
 
     // Get domain from the current AM.
     auto Domain = CurrentAccessMap.domain();
 
     // Create a new AM from the domain.
     auto NewAccessMap = isl::map::from_domain(Domain);
 
     // Add dimensions to the new AM according to the current in_dim.
     NewAccessMap = NewAccessMap.add_dims(isl::dim::out, in_dimensions);
 
     // Create the string representing the name of the new SAI.
-  // One new SAI for each statement so that each write go to a different memory
-  // cell.
+    // One new SAI for each statement so that each write go to a different
+    // memory cell.
     auto CurrentStmtDomain = MA->getStatement()->getDomain();
     auto CurrentStmtName = CurrentStmtDomain.get_tuple_name();
     auto CurrentOutId = CurrentAccessMap.get_tuple_id(isl::dim::out);
     std::string CurrentOutIdString =
         MA->getScopArrayInfo()->getName() + "_" + CurrentStmtName + "_expanded";
 
     // Set the tuple id for the out dimension.
     NewAccessMap = NewAccessMap.set_tuple_id(isl::dim::out, CurrentOutId);
 
     // Create the size vector.
     std::vector<unsigned> Sizes;
     for (unsigned i = 0; i < in_dimensions; i++) {
       assert(isDimBoundedByConstant(CurrentStmtDomain, i) &&
              "Domain boundary are not constant.");
       auto UpperBound = getConstant(CurrentStmtDomain.dim_max(i), true, false);
       assert(!UpperBound.is_null() && UpperBound.is_pos() &&
              !UpperBound.is_nan() &&
              "The upper bound is not a positive integer.");
       assert(UpperBound.le(isl::val(CurrentAccessMap.ctx(),
                                     std::numeric_limits<int>::max() - 1)) &&
              "The upper bound overflow a int.");
       Sizes.push_back(UpperBound.get_num_si() + 1);
     }
 
     // Get the ElementType of the current SAI.
     auto ElementType = MA->getLatestScopArrayInfo()->getElementType();
 
     // Create (or get if already existing) the new expanded SAI.
     auto ExpandedSAI =
         S.createScopArrayInfo(ElementType, CurrentOutIdString, Sizes);
     ExpandedSAI->setIsOnHeap(true);
 
     // Get the out Id of the expanded Array.
     auto NewOutId = ExpandedSAI->getBasePtrId();
 
     // Set the out id of the new AM to the new SAI id.
     NewAccessMap = NewAccessMap.set_tuple_id(isl::dim::out, NewOutId);
 
     // Add constraints to linked output with input id.
     auto SpaceMap = NewAccessMap.get_space();
     auto ConstraintBasicMap = isl::basic_map::equal(
         SpaceMap, unsignedFromIslSize(SpaceMap.dim(isl::dim::in)));
     NewAccessMap = isl::map(ConstraintBasicMap);
 
     // Set the new access relation map.
     MA->setNewAccessRelation(NewAccessMap);
 
     return ExpandedSAI;
   }
 
-void MaximalStaticExpander::expandPhi(Scop &S, const ScopArrayInfo *SAI,
-                                      const isl::union_map &Dependences) {
+  /// Expand PHI memory accesses.
+  ///
+  /// @param The SCop in which the memory access appears in.
+  /// @param The ScopArrayInfo representing the PHI accesses to expand.
+  /// @param Dependences The RAW dependences of the SCop.
+  void expandPhi(Scop &S, const ScopArrayInfo *SAI,
     SmallPtrSet<MemoryAccess *, 4> Writes;
     for (auto MA : S.getPHIIncomings(SAI))
       Writes.insert(MA);
     auto Read = S.getPHIRead(SAI);
-  auto ExpandedSAI = expandAccess(S, Read);
-
-  mapAccess(S, Writes, Dependences, ExpandedSAI, false);
-}
+    auto ExpandedSAI = expandAccess(Read);
 
-void MaximalStaticExpander::emitRemark(StringRef Msg, Instruction *Inst) {
-  ORE->emit(OptimizationRemarkAnalysis(DEBUG_TYPE, "ExpansionRejection", Inst)
-            << Msg);
+    mapAccess(Writes, Dependences, ExpandedSAI, false);
   }
 
-bool MaximalStaticExpander::runOnScop(Scop &S) {
-  // Get the ORE from OptimizationRemarkEmitterWrapperPass.
-  ORE = &(getAnalysis<OptimizationRemarkEmitterWrapperPass>().getORE());
-
-  // Get the RAW Dependences.
-  auto &DI = getAnalysis<DependenceInfo>();
-  auto &D = DI.getDependences(Dependences::AL_Reference);
-  isl::union_map Dependences = D.getDependences(Dependences::TYPE_RAW);
+public:
+  MaximalStaticExpansionImpl(Scop &S, isl::union_map &Dependences,
+                             OptimizationRemarkEmitter &ORE)
+      : S(S), Dependences(Dependences), ORE(ORE) {}
 
+  /// Expand the accesses of the SCoP
+  ///
+  /// @param S The SCoP that must be expanded
+  /// @param D The dependencies information of SCoP
+  void expand() {
     SmallVector<ScopArrayInfo *, 4> CurrentSAI(S.arrays().begin(),
                                                S.arrays().end());
-
     for (auto SAI : CurrentSAI) {
       SmallPtrSet<MemoryAccess *, 4> AllWrites;
       SmallPtrSet<MemoryAccess *, 4> AllReads;
-    if (!isExpandable(SAI, AllWrites, AllReads, S, Dependences))
+      if (!isExpandable(SAI, AllWrites, AllReads, S))
         continue;
 
       if (SAI->isValueKind() || SAI->isArrayKind()) {
         assert(AllWrites.size() == 1 || SAI->isValueKind());
 
         auto TheWrite = *(AllWrites.begin());
-      ScopArrayInfo *ExpandedArray = expandAccess(S, TheWrite);
+        ScopArrayInfo *ExpandedArray = expandAccess(TheWrite);
 
-      mapAccess(S, AllReads, Dependences, ExpandedArray, true);
+        mapAccess(AllReads, Dependences, ExpandedArray, true);
       } else if (SAI->isPHIKind()) {
         expandPhi(S, SAI, Dependences);
       }
     }
+  }
+
+  /// Dump the internal information about a performed MSE to @p OS.
+  void print(llvm::raw_ostream &OS) {
+    OS << "After arrays {\n";
+
+    for (auto &Array : S.arrays())
+      Array->print(OS);
+
+    OS << "}\n";
+
+    OS << "After accesses {\n";
+    for (auto &Stmt : S) {
+      OS.indent(4) << Stmt.getBaseName() << "{\n";
+      for (auto *MA : Stmt)
+        MA->print(OS);
+      OS.indent(4) << "}\n";
+    }
+    OS << "}\n";
+  }
+};
+
+static std::unique_ptr<MaximalStaticExpansionImpl>
+runMaximalStaticExpansion(Scop &S, OptimizationRemarkEmitter &ORE,
+                          const Dependences &D) {
+  auto Dependences = D.getDependences(Dependences::TYPE_RAW);
+
+  std::unique_ptr<MaximalStaticExpansionImpl> Impl =
+      std::make_unique<MaximalStaticExpansionImpl>(S, Dependences, ORE);
+
+  Impl->expand();
+  return Impl;
+}
+
+static PreservedAnalyses runMSEUsingNPM(Scop &S, ScopAnalysisManager &SAM,
+                                        ScopStandardAnalysisResults &SAR,
+                                        raw_ostream *OS) {
+  OptimizationRemarkEmitter ORE(&S.getFunction());
+
+  auto &DI = SAM.getResult<DependenceAnalysis>(S, SAR);
+  auto &D = DI.getDependences(Dependences::AL_Reference);
+
+  auto Impl = runMaximalStaticExpansion(S, ORE, D);
+
+  if (OS) {
+    *OS << "Printing analysis 'Polly - Maximal static expansion of SCoP' for "
+           "region: '"
+        << S.getName() << "' in function '" << S.getFunction().getName()
+        << "':\n";
+
+    if (Impl) {
+      *OS << "MSE result:\n";
+      Impl->print(*OS);
+    }
+  }
+
+  return PreservedAnalyses::all();
+}
+
+} // namespace
+
+PreservedAnalyses
+MaximalStaticExpansionPass::run(Scop &S, ScopAnalysisManager &SAM,
+                                ScopStandardAnalysisResults &SAR,
+                                SPMUpdater &) {
+  return runMSEUsingNPM(S, SAM, SAR, nullptr);
+}
+
+PreservedAnalyses
+MaximalStaticExpansionPrinterPass::run(Scop &S, ScopAnalysisManager &SAM,
+                                       ScopStandardAnalysisResults &SAR,
+                                       SPMUpdater &) {
+  return runMSEUsingNPM(S, SAM, SAR, &OS);
+}
+
+char MaximalStaticExpanderWrapperPass::ID = 0;
+
+bool MaximalStaticExpanderWrapperPass::runOnScop(Scop &S) {
+  // Get the ORE from OptimizationRemarkEmitterWrapperPass.
+  OptimizationRemarkEmitter *ORE =
+      &(getAnalysis<OptimizationRemarkEmitterWrapperPass>().getORE());
+
+  // Get the RAW Dependences.
+  auto &DI = getAnalysis<DependenceInfo>();
+  auto &D = DI.getDependences(Dependences::AL_Reference);
+
+  auto Impl = runMaximalStaticExpansion(S, *ORE, D);
 
   return false;
 }
 
-void MaximalStaticExpander::printScop(raw_ostream &OS, Scop &S) const {
+void MaximalStaticExpanderWrapperPass::printScop(raw_ostream &OS,
+                                                 Scop &S) const {
   S.print(OS, false);
 }
 
-void MaximalStaticExpander::getAnalysisUsage(AnalysisUsage &AU) const {
+void MaximalStaticExpanderWrapperPass::getAnalysisUsage(
+    AnalysisUsage &AU) const {
   ScopPass::getAnalysisUsage(AU);
   AU.addRequired<DependenceInfo>();
   AU.addRequired<OptimizationRemarkEmitterWrapperPass>();
 }
 
 Pass *polly::createMaximalStaticExpansionPass() {
-  return new MaximalStaticExpander();
+  return new MaximalStaticExpanderWrapperPass();
 }
 
-INITIALIZE_PASS_BEGIN(MaximalStaticExpander, "polly-mse",
+INITIALIZE_PASS_BEGIN(MaximalStaticExpanderWrapperPass, "polly-mse",
                       "Polly - Maximal static expansion of SCoP", false, false);
 INITIALIZE_PASS_DEPENDENCY(DependenceInfo);
 INITIALIZE_PASS_DEPENDENCY(OptimizationRemarkEmitterWrapperPass);
-INITIALIZE_PASS_END(MaximalStaticExpander, "polly-mse",
+INITIALIZE_PASS_END(MaximalStaticExpanderWrapperPass, "polly-mse",
                     "Polly - Maximal static expansion of SCoP", false, false)

polly/test/MaximalStaticExpansion/load_after_store_same_statement.ll

 ; RUN: opt %loadPolly -polly-stmt-granularity=bb -polly-mse -polly-print-scops -disable-output < %s | FileCheck %s
+; RUN: opt %loadNPMPolly -polly-stmt-granularity=bb "-passes=scop(print<polly-mse>)" -disable-output < %s | FileCheck %s
 ; RUN: opt %loadPolly -polly-stmt-granularity=bb -polly-mse -polly-print-scops -pass-remarks-analysis="polly-mse" -disable-output < %s 2>&1| FileCheck %s --check-prefix=MSE
+; RUN: opt %loadNPMPolly -polly-stmt-granularity=bb "-passes=scop(print<polly-mse>)" -pass-remarks-analysis="polly-mse" -disable-output < %s 2>&1 | FileCheck %s --check-prefix=MSE
 ;
 ; Verify that the expansion of an array with load after store in a same statement is not done.
 ;
 ; Original source code :
 ;
 ; #define Ni 2000
 ; #define Nj 3000
 ;

polly/test/MaximalStaticExpansion/read_from_original.ll

 ; RUN: opt %loadPolly -polly-mse -polly-print-scops -disable-output < %s | FileCheck %s
+; RUN: opt %loadNPMPolly "-passes=scop(print<polly-mse>)" -disable-output < %s | FileCheck %s
 ; RUN: opt %loadPolly -polly-mse -polly-print-scops -pass-remarks-analysis="polly-mse" -disable-output < %s 2>&1| FileCheck %s --check-prefix=MSE
+; RUN: opt %loadNPMPolly "-passes=scop(print<polly-mse>)" -pass-remarks-analysis="polly-mse" -disable-output < %s 2>&1 | FileCheck %s --check-prefix=MSE
 ;
 ; Verify that Polly detects problems and does not expand the array
 ;
 ; Original source code :
 ;
 ; #define Ni 2000
 ; #define Nj 3000
 ;

polly/test/MaximalStaticExpansion/too_many_writes.ll

 ; RUN: opt %loadPolly -polly-mse -polly-print-scops -disable-output < %s | FileCheck %s
+; RUN: opt %loadNPMPolly "-passes=scop(print<polly-mse>)" -disable-output < %s | FileCheck %s
 ; RUN: opt %loadPolly -polly-mse -polly-print-scops -pass-remarks-analysis="polly-mse" -disable-output < %s 2>&1 | FileCheck %s --check-prefix=MSE
+; RUN: opt %loadNPMPolly "-passes=scop(print<polly-mse>)" -pass-remarks-analysis="polly-mse" -disable-output < %s 2>&1 | FileCheck %s --check-prefix=MSE
 ;
 ; Verify that Polly detects problems and does not expand the array
 ;
 ; Original source code :
 ;
 ; #define Ni 2000
 ; #define Nj 2000
 ;

polly/test/MaximalStaticExpansion/working_deps_between_inners.ll

 ; RUN: opt %loadPolly -polly-mse -polly-print-scops -disable-output < %s | FileCheck %s
+; RUN: opt %loadNPMPolly "-passes=scop(print<polly-mse>)" -disable-output < %s | FileCheck %s
 ;
 ; Verify that the accesses are correctly expanded for MemoryKind::Array
 ;
 ; Original source code :
 ;
 ; #define Ni 2000
 ; #define Nj 3000
 ;

polly/test/MaximalStaticExpansion/working_deps_between_inners_phi.ll

 ; RUN: opt %loadPolly -polly-mse -polly-print-scops -disable-output < %s | FileCheck %s
+; RUN: opt %loadNPMPolly "-passes=scop(print<polly-mse>)" -disable-output < %s | FileCheck %s
 ; RUN: opt %loadPolly -polly-mse -polly-print-scops -pass-remarks-analysis="polly-mse" -disable-output < %s 2>&1 | FileCheck %s --check-prefix=MSE
+; RUN: opt %loadNPMPolly -polly-stmt-granularity=bb "-passes=scop(print<polly-mse>)" -pass-remarks-analysis="polly-mse" -disable-output < %s 2>&1 | FileCheck %s --check-prefix=MSE
 ;
 ; Verify that the accesses are correctly expanded for MemoryKind::Array and MemoryKind::PHI.
 ; tmp_06_phi is not expanded because it need copy in.
 ;
 ; Original source code :
 ;
 ; #define Ni 2000
 ; #define Nj 3000

polly/test/MaximalStaticExpansion/working_expansion.ll

 ; RUN: opt %loadPolly -polly-mse -polly-print-scops -disable-output < %s | FileCheck %s
+; RUN: opt %loadNPMPolly "-passes=scop(print<polly-mse>)" -disable-output < %s | FileCheck %s
 ;
 ; Verify that the accesses are correctly expanded for MemoryKind::Array
 ;
 ; Original source code :
 ;
 ; #define Ni 2000
 ; #define Nj 3000
 ;

polly/test/MaximalStaticExpansion/working_expansion_multiple_dependences_per_statement.ll

 ; RUN: opt %loadPolly -polly-stmt-granularity=bb -polly-mse -polly-print-scops -disable-output < %s | FileCheck %s
+; RUN: opt %loadNPMPolly -polly-stmt-granularity=bb "-passes=scop(print<polly-mse>)" -disable-output < %s | FileCheck %s
 ;
 ; Verify that the accesses are correctly expanded
 ;
 ; Original source code :
 ;
 ; #define Ni 2000
 ; #define Nj 3000
 ;

polly/test/MaximalStaticExpansion/working_expansion_multiple_instruction_per_statement.ll

 ; RUN: opt %loadPolly -polly-stmt-granularity=bb -polly-mse -polly-print-scops -disable-output < %s | FileCheck %s
+; RUN: opt %loadNPMPolly -polly-stmt-granularity=bb "-passes=scop(print<polly-mse>)" -disable-output < %s | FileCheck %s
 ;
 ; Verify that the accesses are correctly expanded
 ;
 ; Original source code :
 ;
 ; #define Ni 2000
 ; #define Nj 3000
 ;

polly/test/MaximalStaticExpansion/working_phi_expansion.ll

 ; RUN: opt %loadPolly -polly-mse -polly-print-scops -disable-output < %s | FileCheck %s
+; RUN: opt %loadNPMPolly "-passes=scop(print<polly-mse>)" -disable-output < %s | FileCheck %s
 ; RUN: opt %loadPolly -polly-mse -polly-print-scops -pass-remarks-analysis="polly-mse" -disable-output < %s 2>&1 | FileCheck %s --check-prefix=MSE
+; RUN: opt %loadNPMPolly "-passes=scop(print<polly-mse>)" -pass-remarks-analysis="polly-mse" -disable-output < %s 2>&1 | FileCheck %s --check-prefix=MSE
 ;
 ; Verify that the accesses are correctly expanded for MemoryKind::PHI
 ; tmp_04 is not expanded because it need copy-in.
 ;
 ; Original source code :
 ;
 ; #define Ni 10000
 ; #define Nj 10000

polly/test/MaximalStaticExpansion/working_phi_two_scalars.ll

 ; RUN: opt %loadPolly -polly-stmt-granularity=bb -polly-mse -polly-print-scops -disable-output < %s | FileCheck %s
+; RUN: opt %loadNPMPolly -polly-stmt-granularity=bb "-passes=scop(print<polly-mse>)" -disable-output < %s | FileCheck %s
 ; RUN: opt %loadPolly -polly-stmt-granularity=bb -polly-mse -polly-print-scops -pass-remarks-analysis="polly-mse" -disable-output < %s 2>&1 | FileCheck %s --check-prefix=MSE
+; RUN: opt %loadNPMPolly -polly-stmt-granularity=bb "-passes=scop(print<polly-mse>)" -pass-remarks-analysis="polly-mse" -disable-output < %s 2>&1 | FileCheck %s --check-prefix=MSE
 ;
 ; Verify that the accesses are correctly expanded for MemoryKind::PHI
 ; tmp_05 and tmp2_06 are not expanded because they need copy-in.
 ;
 ; Original source code :
 ;
 ; #define Ni 10000
 ; #define Nj 10000

polly/test/MaximalStaticExpansion/working_value_expansion.ll

 ; RUN: opt %loadPolly -polly-mse -polly-print-scops -disable-output < %s | FileCheck %s
+; RUN: opt %loadNPMPolly "-passes=scop(print<polly-mse>)" -disable-output < %s | FileCheck %s
 ;
 ; Verify that the accesses are correctly expanded for MemoryKind::Value
 ;
 ; Original source code :
 ;
 ; #define Ni 10000
 ; #define Nj 10000
 ;