[Polly][NewPM] Port Simplify to the new pass manager

[Meinersbur]

Could you add a test that invokes the pass with the new pass manage? E.g. take an existing test for the SimplifyPass, and add a RUN: line that does the same thing with NPM?

Thank you for the patch!

[pzheng]

Thanks for reviewing the patch, @Meinersbur!

I have updated some of the existing tests for the SimplifyPass to also use the NPM. There are still some tests for SimplifyPass which depend on other Polly passes being properly ported first. Those tests will be updated in a follow-up patch.

[pzheng]

minor update to a test

[Meinersbur]

LGTM

A single test test file would be enough to check that the new pass manager pipeline is working. Checking all tests with both pass manager doubles the execution time for check-polly without improving test coverage. There are not too many tests for the simplify pass, but please consider testing it only once with the scalability tests, as these take the most time.

[pzheng]

In D87328#2284308, @Meinersbur wrote:

LGTM

A single test test file would be enough to check that the new pass manager pipeline is working. Checking all tests with both pass manager doubles the execution time for check-polly without improving test coverage. There are not too many tests for the simplify pass, but please consider testing it only once with the scalability tests, as these take the most time.

That makes sense. I will revert changes in the scalability tests when committing.

[Meinersbur]

Thank you

polly/include/polly/Simplify.h

 //===------ Simplify.h ------------------------------------------*- 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
 //
 //===----------------------------------------------------------------------===//
 //
 // Simplify a SCoP by removing unnecessary statements and accesses.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef POLLY_TRANSFORM_SIMPLIFY_H
 #define POLLY_TRANSFORM_SIMPLIFY_H
 
+#include "polly/ScopPass.h"
 #include "llvm/ADT/SmallVector.h"
+#include "llvm/IR/PassManager.h"
 
 namespace llvm {
 class PassRegistry;
 class Pass;
 } // namespace llvm
 
+namespace {
+class SimplifyVisitor {
+private:
+  /// The invocation id (if there are multiple instances in the pass manager's
+  /// pipeline) to determine which statistics to update.
+  int CallNo;
+
+  /// The last/current SCoP that is/has been processed.
+  Scop *S;
+
+  /// Number of statements with empty domains removed from the SCoP.
+  int EmptyDomainsRemoved = 0;
+
+  /// Number of writes that are overwritten anyway.
+  int OverwritesRemoved = 0;
+
+  /// Number of combined writes.
+  int WritesCoalesced = 0;
+
+  /// Number of redundant writes removed from this SCoP.
+  int RedundantWritesRemoved = 0;
+
+  /// Number of writes with empty access domain removed.
+  int EmptyPartialAccessesRemoved = 0;
+
+  /// Number of unused accesses removed from this SCoP.
+  int DeadAccessesRemoved = 0;
+
+  /// Number of unused instructions removed from this SCoP.
+  int DeadInstructionsRemoved = 0;
+
+  /// Number of unnecessary statements removed from the SCoP.
+  int StmtsRemoved = 0;
+
+  /// Return whether at least one simplification has been applied.
+  bool isModified() const;
+
+  /// Remove statements that are never executed due to their domains being
+  /// empty.
+  ///
+  /// In contrast to Scop::simplifySCoP, this removes based on the SCoP's
+  /// effective domain, i.e. including the SCoP's context as used by some other
+  /// simplification methods in this pass. This is necessary because the
+  /// analysis on empty domains is unreliable, e.g. remove a scalar value
+  /// definition MemoryAccesses, but not its use.
+  void removeEmptyDomainStmts();
+
+  /// Remove writes that are overwritten unconditionally later in the same
+  /// statement.
+  ///
+  /// There must be no read of the same value between the write (that is to be
+  /// removed) and the overwrite.
+  void removeOverwrites();
+
+  /// Combine writes that write the same value if possible.
+  ///
+  /// This function is able to combine:
+  /// - Partial writes with disjoint domain.
+  /// - Writes that write to the same array element.
+  ///
+  /// In all cases, both writes must write the same values.
+  void coalesceWrites();
+
+  /// Remove writes that just write the same value already stored in the
+  /// element.
+  void removeRedundantWrites();
+
+  /// Remove statements without side effects.
+  void removeUnnecessaryStmts();
+
+  /// Remove accesses that have an empty domain.
+  void removeEmptyPartialAccesses();
+
+  /// Mark all reachable instructions and access, and sweep those that are not
+  /// reachable.
+  void markAndSweep(LoopInfo *LI);
+
+  /// Print simplification statistics to @p OS.
+  void printStatistics(llvm::raw_ostream &OS, int Indent = 0) const;
+
+  /// Print the current state of all MemoryAccesses to @p OS.
+  void printAccesses(llvm::raw_ostream &OS, int Indent = 0) const;
+
+public:
+  explicit SimplifyVisitor(int CallNo = 0) : CallNo(CallNo) {}
+
+  bool visit(Scop &S, LoopInfo *LI);
+
+  void printScop(raw_ostream &OS, Scop &S) const;
+
+  void releaseMemory();
+};
+} // namespace
+
 namespace polly {
 
 class MemoryAccess;
 class ScopStmt;
 
 /// Return a vector that contains MemoryAccesses in the order in
 /// which they are executed.
 ///

 ///
 /// @param CallNo Disambiguates this instance for when there are multiple
 ///               instances of this pass in the pass manager. It is used only to
 ///               keep the statistics apart and has no influence on the
 ///               simplification itself.
 ///
 /// @return The Simplify pass.
 llvm::Pass *createSimplifyPass(int CallNo = 0);
+
+struct SimplifyPass : public PassInfoMixin<SimplifyPass> {
+  SimplifyPass(int CallNo = 0) : Imp(CallNo) {}
+
+  llvm::PreservedAnalyses run(Scop &S, ScopAnalysisManager &SAM,
+                              ScopStandardAnalysisResults &AR, SPMUpdater &U);
+
+  SimplifyVisitor Imp;
+};
+
+struct SimplifyPrinterPass : public PassInfoMixin<SimplifyPrinterPass> {
+  SimplifyPrinterPass(raw_ostream &OS, int CallNo = 0) : OS(OS), Imp(CallNo) {}
+
+  PreservedAnalyses run(Scop &S, ScopAnalysisManager &,
+                        ScopStandardAnalysisResults &, SPMUpdater &);
+
+  raw_ostream &OS;
+  SimplifyVisitor Imp;
+};
 } // namespace polly
 
 namespace llvm {
-void initializeSimplifyPass(llvm::PassRegistry &);
+void initializeSimplifyLegacyPassPass(llvm::PassRegistry &);
 } // namespace llvm
 
 #endif /* POLLY_TRANSFORM_SIMPLIFY_H */

polly/lib/Support/PollyPasses.def

 #ifndef SCOP_PASS
 #define SCOP_PASS(NAME, CREATE_PASS)
 #endif
 SCOP_PASS("polly-export-jscop", JSONExportPass())
 SCOP_PASS("polly-import-jscop", JSONImportPass())
 SCOP_PASS("print<polly-ast>", IslAstPrinterPass(outs()))
 SCOP_PASS("print<polly-dependences>", DependenceInfoPrinterPass(outs()))
 SCOP_PASS("polly-codegen", CodeGenerationPass())
+SCOP_PASS("polly-simplify", SimplifyPass())
+SCOP_PASS("print<polly-simplify>", SimplifyPrinterPass(outs()))
 #undef SCOP_PASS

polly/lib/Support/RegisterPasses.cpp

#endif
   initializeScopInlinerPass(Registry);
   initializeScopInfoRegionPassPass(Registry);
   initializeScopInfoWrapperPassPass(Registry);
   initializeRewriteByrefParamsPass(Registry);
   initializeCodegenCleanupPass(Registry);
   initializeFlattenSchedulePass(Registry);
   initializeForwardOpTreePass(Registry);
   initializeDeLICMPass(Registry);
-  initializeSimplifyPass(Registry);
+  initializeSimplifyLegacyPassPass(Registry);
   initializeDumpModulePass(Registry);
   initializePruneUnprofitablePass(Registry);
 }
 
 /// Register Polly passes such that they form a polyhedral optimizer.
 ///
 /// The individual Polly passes are registered in the pass manager such that
 /// they form a full polyhedral optimizer. The flow of the optimizer starts with

polly/lib/Transform/Simplify.cpp

static isl::union_map underapproximatedAddMap(isl::union_map UMap,
 
   isl::union_map UResult =
       UMap.subtract(isl::map::universe(PrevMap.get_space()));
   UResult.add_map(Result);
 
   return UResult;
 }
 
-class Simplify : public ScopPass {
-private:
-  /// The invocation id (if there are multiple instances in the pass manager's
-  /// pipeline) to determine which statistics to update.
-  int CallNo;
-
-  /// The last/current SCoP that is/has been processed.
-  Scop *S;
-
-  /// Number of statements with empty domains removed from the SCoP.
-  int EmptyDomainsRemoved = 0;
-
-  /// Number of writes that are overwritten anyway.
-  int OverwritesRemoved = 0;
-
-  /// Number of combined writes.
-  int WritesCoalesced = 0;
-
-  /// Number of redundant writes removed from this SCoP.
-  int RedundantWritesRemoved = 0;
-
-  /// Number of writes with empty access domain removed.
-  int EmptyPartialAccessesRemoved = 0;
-
-  /// Number of unused accesses removed from this SCoP.
-  int DeadAccessesRemoved = 0;
-
-  /// Number of unused instructions removed from this SCoP.
-  int DeadInstructionsRemoved = 0;
-
-  /// Number of unnecessary statements removed from the SCoP.
-  int StmtsRemoved = 0;
-
-  /// Return whether at least one simplification has been applied.
-  bool isModified() const {
-    return EmptyDomainsRemoved > 0 || OverwritesRemoved > 0 ||
-           WritesCoalesced > 0 || RedundantWritesRemoved > 0 ||
-           EmptyPartialAccessesRemoved > 0 || DeadAccessesRemoved > 0 ||
-           DeadInstructionsRemoved > 0 || StmtsRemoved > 0;
-  }
+bool SimplifyVisitor::isModified() const {
 
-  /// Remove statements that are never executed due to their domains being
-  /// empty.
-  ///
-  /// In contrast to Scop::simplifySCoP, this removes based on the SCoP's
-  /// effective domain, i.e. including the SCoP's context as used by some other
-  /// simplification methods in this pass. This is necessary because the
-  /// analysis on empty domains is unreliable, e.g. remove a scalar value
-  /// definition MemoryAccesses, but not its use.
-  void removeEmptyDomainStmts() {
-    size_t NumStmtsBefore = S->getSize();
+void SimplifyVisitor::removeEmptyDomainStmts() {
 
-    S->removeStmts([](ScopStmt &Stmt) -> bool {
-      auto EffectiveDomain =
-          Stmt.getDomain().intersect_params(Stmt.getParent()->getContext());
-      return EffectiveDomain.is_empty();
-    });
 
-    assert(NumStmtsBefore >= S->getSize());
-    EmptyDomainsRemoved = NumStmtsBefore - S->getSize();
-    LLVM_DEBUG(dbgs() << "Removed " << EmptyDomainsRemoved << " (of "
-                      << NumStmtsBefore
-                      << ") statements with empty domains \n");
-    TotalEmptyDomainsRemoved[CallNo] += EmptyDomainsRemoved;
-  }
+                    << NumStmtsBefore << ") statements with empty domains \n");
 
-  /// Remove writes that are overwritten unconditionally later in the same
-  /// statement.
-  ///
-  /// There must be no read of the same value between the write (that is to be
-  /// removed) and the overwrite.
-  void removeOverwrites() {
-    for (auto &Stmt : *S) {
-      isl::set Domain = Stmt.getDomain();
-      isl::union_map WillBeOverwritten =
-          isl::union_map::empty(S->getParamSpace());
+void SimplifyVisitor::removeOverwrites() {
 
-      SmallVector<MemoryAccess *, 32> Accesses(getAccessesInOrder(Stmt));
 
-      // Iterate in reverse order, so the overwrite comes before the write that
-      // is to be removed.
-      for (auto *MA : reverse(Accesses)) {
 
-        // In region statements, the explicit accesses can be in blocks that are
-        // can be executed in any order. We therefore process only the implicit
-        // writes and stop after that.
-        if (Stmt.isRegionStmt() && isExplicitAccess(MA))
-          break;
 
-        auto AccRel = MA->getAccessRelation();
-        AccRel = AccRel.intersect_domain(Domain);
-        AccRel = AccRel.intersect_params(S->getContext());
 
-        // If a value is read in-between, do not consider it as overwritten.
-        if (MA->isRead()) {
-          // Invalidate all overwrites for the array it accesses to avoid too
-          // complex isl sets.
-          isl::map AccRelUniv = isl::map::universe(AccRel.get_space());
-          WillBeOverwritten = WillBeOverwritten.subtract(AccRelUniv);
-          continue;
-        }
 
-        // If all of a write's elements are overwritten, remove it.
-        isl::union_map AccRelUnion = AccRel;
-        if (AccRelUnion.is_subset(WillBeOverwritten)) {
-          LLVM_DEBUG(dbgs() << "Removing " << MA
-                            << " which will be overwritten anyway\n");
 
-          Stmt.removeSingleMemoryAccess(MA);
-          OverwritesRemoved++;
-          TotalOverwritesRemoved[CallNo]++;
-        }
 
-        // Unconditional writes overwrite other values.
-        if (MA->isMustWrite()) {
-          // Avoid too complex isl sets. If necessary, throw away some of the
-          // knowledge.
-          WillBeOverwritten =
-              underapproximatedAddMap(WillBeOverwritten, AccRel);
-        }
-      }
-    }
-  }
+        WillBeOverwritten = underapproximatedAddMap(WillBeOverwritten, AccRel);
 
-  /// Combine writes that write the same value if possible.
-  ///
-  /// This function is able to combine:
-  /// - Partial writes with disjoint domain.
-  /// - Writes that write to the same array element.
-  ///
-  /// In all cases, both writes must write the same values.
-  void coalesceWrites() {
-    for (auto &Stmt : *S) {
-      isl::set Domain = Stmt.getDomain().intersect_params(S->getContext());
+void SimplifyVisitor::coalesceWrites() {
 
-      // We let isl do the lookup for the same-value condition. For this, we
-      // wrap llvm::Value into an isl::set such that isl can do the lookup in
-      // its hashtable implementation. llvm::Values are only compared within a
-      // ScopStmt, so the map can be local to this scope. TODO: Refactor with
-      // ZoneAlgorithm::makeValueSet()
-      SmallDenseMap<Value *, isl::set> ValueSets;
-      auto makeValueSet = [&ValueSets, this](Value *V) -> isl::set {
-        assert(V);
-        isl::set &Result = ValueSets[V];
-        if (Result.is_null()) {
-          isl::ctx Ctx = S->getIslCtx();
-          std::string Name =
-              getIslCompatibleName("Val", V, ValueSets.size() - 1,
-                                   std::string(), UseInstructionNames);
-          isl::id Id = isl::id::alloc(Ctx, Name, V);
-          Result = isl::set::universe(
-              isl::space(Ctx, 0, 0).set_tuple_id(isl::dim::set, Id));
-        }
-        return Result;
-      };
+        std::string Name = getIslCompatibleName(
+            "Val", V, ValueSets.size() - 1, std::string(), UseInstructionNames);
 
-      // List of all eligible (for coalescing) writes of the future.
-      // { [Domain[] -> Element[]] -> [Value[] -> MemoryAccess[]] }
-      isl::union_map FutureWrites = isl::union_map::empty(S->getParamSpace());
 
-      // Iterate over accesses from the last to the first.
-      SmallVector<MemoryAccess *, 32> Accesses(getAccessesInOrder(Stmt));
-      for (MemoryAccess *MA : reverse(Accesses)) {
-        // In region statements, the explicit accesses can be in blocks that can
-        // be executed in any order. We therefore process only the implicit
-        // writes and stop after that.
-        if (Stmt.isRegionStmt() && isExplicitAccess(MA))
-          break;
 
-        // { Domain[] -> Element[] }
-        isl::map AccRel =
-            MA->getLatestAccessRelation().intersect_domain(Domain);
+      isl::map AccRel = MA->getLatestAccessRelation().intersect_domain(Domain);
 
-        // { [Domain[] -> Element[]] }
-        isl::set AccRelWrapped = AccRel.wrap();
 
-        // { Value[] }
-        isl::set ValSet;
 
-        if (MA->isMustWrite() && (MA->isOriginalScalarKind() ||
-                                  isa<StoreInst>(MA->getAccessInstruction()))) {
-          // Normally, tryGetValueStored() should be used to determine which
-          // element is written, but it can return nullptr; For PHI accesses,
-          // getAccessValue() returns the PHI instead of the PHI's incoming
-          // value. In this case, where we only compare values of a single
-          // statement, this is fine, because within a statement, a PHI in a
-          // successor block has always the same value as the incoming write. We
-          // still preferably use the incoming value directly so we also catch
-          // direct uses of that.
-          Value *StoredVal = MA->tryGetValueStored();
-          if (!StoredVal)
-            StoredVal = MA->getAccessValue();
-          ValSet = makeValueSet(StoredVal);
 
-          // { Domain[] }
-          isl::set AccDomain = AccRel.domain();
 
-          // Parts of the statement's domain that is not written by this access.
-          isl::set UndefDomain = Domain.subtract(AccDomain);
 
-          // { Element[] }
-          isl::set ElementUniverse =
-              isl::set::universe(AccRel.get_space().range());
 
-          // { Domain[] -> Element[] }
-          isl::map UndefAnything =
-              isl::map::from_domain_and_range(UndefDomain, ElementUniverse);
 
-          // We are looking a compatible write access. The other write can
-          // access these elements...
-          isl::map AllowedAccesses = AccRel.unite(UndefAnything);
 
-          // ... and must write the same value.
-          // { [Domain[] -> Element[]] -> Value[] }
-          isl::map Filter =
-              isl::map::from_domain_and_range(AllowedAccesses.wrap(), ValSet);
 
-          // Lookup future write that fulfills these conditions.
-          // { [[Domain[] -> Element[]] -> Value[]] -> MemoryAccess[] }
-          isl::union_map Filtered =
-              FutureWrites.uncurry().intersect_domain(Filter.wrap());
 
-          // Iterate through the candidates.
-          for (isl::map Map : Filtered.get_map_list()) {
-            MemoryAccess *OtherMA = (MemoryAccess *)Map.get_space()
-                                        .get_tuple_id(isl::dim::out)
-                                        .get_user();
 
-            isl::map OtherAccRel =
-                OtherMA->getLatestAccessRelation().intersect_domain(Domain);
 
-            // The filter only guaranteed that some of OtherMA's accessed
-            // elements are allowed. Verify that it only accesses allowed
-            // elements. Otherwise, continue with the next candidate.
-            if (!OtherAccRel.is_subset(AllowedAccesses).is_true())
-              continue;
 
-            // The combined access relation.
-            // { Domain[] -> Element[] }
-            isl::map NewAccRel = AccRel.unite(OtherAccRel);
-            simplify(NewAccRel);
 
-            // Carry out the coalescing.
-            Stmt.removeSingleMemoryAccess(MA);
-            OtherMA->setNewAccessRelation(NewAccRel);
 
-            // We removed MA, OtherMA takes its role.
-            MA = OtherMA;
 
-            TotalWritesCoalesced[CallNo]++;
-            WritesCoalesced++;
 
-            // Don't look for more candidates.
-            break;
-          }
-        }
 
-        // Two writes cannot be coalesced if there is another access (to some of
-        // the written elements) between them. Remove all visited write accesses
-        // from the list of eligible writes. Don't just remove the accessed
-        // elements, but any MemoryAccess that touches any of the invalidated
-        // elements.
-        SmallPtrSet<MemoryAccess *, 2> TouchedAccesses;
-        for (isl::map Map :
-             FutureWrites.intersect_domain(AccRelWrapped).get_map_list()) {
-          MemoryAccess *MA = (MemoryAccess *)Map.get_space()
-                                 .range()
-                                 .unwrap()
-                                 .get_tuple_id(isl::dim::out)
-                                 .get_user();
-          TouchedAccesses.insert(MA);
-        }
-        isl::union_map NewFutureWrites =
-            isl::union_map::empty(FutureWrites.get_space());
-        for (isl::map FutureWrite : FutureWrites.get_map_list()) {
-          MemoryAccess *MA = (MemoryAccess *)FutureWrite.get_space()
-                                 .range()
-                                 .unwrap()
-                                 .get_tuple_id(isl::dim::out)
-                                 .get_user();
-          if (!TouchedAccesses.count(MA))
-            NewFutureWrites = NewFutureWrites.add_map(FutureWrite);
-        }
-        FutureWrites = NewFutureWrites;
 
-        if (MA->isMustWrite() && !ValSet.is_null()) {
-          // { MemoryAccess[] }
-          auto AccSet =
-              isl::set::universe(isl::space(S->getIslCtx(), 0, 0)
-                                     .set_tuple_id(isl::dim::set, MA->getId()));
 
-          // { Val[] -> MemoryAccess[] }
-          isl::map ValAccSet = isl::map::from_domain_and_range(ValSet, AccSet);
 
-          // { [Domain[] -> Element[]] -> [Value[] -> MemoryAccess[]] }
-          isl::map AccRelValAcc =
-              isl::map::from_domain_and_range(AccRelWrapped, ValAccSet.wrap());
-          FutureWrites = FutureWrites.add_map(AccRelValAcc);
-        }
-      }
-    }
-  }
 
-  /// Remove writes that just write the same value already stored in the
-  /// element.
-  void removeRedundantWrites() {
-    for (auto &Stmt : *S) {
-      SmallDenseMap<Value *, isl::set> ValueSets;
-      auto makeValueSet = [&ValueSets, this](Value *V) -> isl::set {
-        assert(V);
-        isl::set &Result = ValueSets[V];
-        if (Result.is_null()) {
-          isl_ctx *Ctx = S->getIslCtx().get();
-          std::string Name =
-              getIslCompatibleName("Val", V, ValueSets.size() - 1,
-                                   std::string(), UseInstructionNames);
-          isl::id Id = isl::manage(isl_id_alloc(Ctx, Name.c_str(), V));
-          Result = isl::set::universe(
-              isl::space(Ctx, 0, 0).set_tuple_id(isl::dim::set, Id));
-        }
-        return Result;
-      };
+void SimplifyVisitor::removeRedundantWrites() {
+        std::string Name = getIslCompatibleName(
+            "Val", V, ValueSets.size() - 1, std::string(), UseInstructionNames);
 
-      isl::set Domain = Stmt.getDomain();
-      Domain = Domain.intersect_params(S->getContext());
 
-      // List of element reads that still have the same value while iterating
-      // through the MemoryAccesses.
-      // { [Domain[] -> Element[]] -> Val[] }
-      isl::union_map Known = isl::union_map::empty(S->getParamSpace());
 
-      SmallVector<MemoryAccess *, 32> Accesses(getAccessesInOrder(Stmt));
-      for (MemoryAccess *MA : Accesses) {
-        // Is the memory access in a defined order relative to the other
-        // accesses? In region statements, only the first and the last accesses
-        // have defined order. Execution of those in the middle may depend on
-        // runtime conditions an therefore cannot be modified.
-        bool IsOrdered =
-            Stmt.isBlockStmt() || MA->isOriginalScalarKind() ||
-            (!S->getBoxedLoops().size() && MA->getAccessInstruction() &&
-             Stmt.getEntryBlock() == MA->getAccessInstruction()->getParent());
 
-        isl::map AccRel = MA->getAccessRelation();
-        AccRel = AccRel.intersect_domain(Domain);
-        isl::set AccRelWrapped = AccRel.wrap();
 
-        // Determine whether a write is redundant (stores only values that are
-        // already present in the written array elements) and remove it if this
-        // is the case.
-        if (IsOrdered && MA->isMustWrite() &&
-            (isa<StoreInst>(MA->getAccessInstruction()) ||
-             MA->isOriginalScalarKind())) {
-          Value *StoredVal = MA->tryGetValueStored();
-          if (!StoredVal)
-            StoredVal = MA->getAccessValue();
 
-          if (StoredVal) {
-            // Lookup in the set of known values.
-            isl::map AccRelStoredVal = isl::map::from_domain_and_range(
-                AccRelWrapped, makeValueSet(StoredVal));
-            if (isl::union_map(AccRelStoredVal).is_subset(Known)) {
-              LLVM_DEBUG(dbgs() << "Cleanup of " << MA << ":\n");
-              LLVM_DEBUG(dbgs() << "      Scalar: " << *StoredVal << "\n");
-              LLVM_DEBUG(dbgs() << "      AccRel: " << AccRel << "\n");
 
-              Stmt.removeSingleMemoryAccess(MA);
 
-              RedundantWritesRemoved++;
-              TotalRedundantWritesRemoved[CallNo]++;
-            }
-          }
-        }
 
-        // Update the know values set.
-        if (MA->isRead()) {
-          // Loaded values are the currently known values of the array element
-          // it was loaded from.
-          Value *LoadedVal = MA->getAccessValue();
-          if (LoadedVal && IsOrdered) {
-            isl::map AccRelVal = isl::map::from_domain_and_range(
-                AccRelWrapped, makeValueSet(LoadedVal));
 
-            Known = Known.add_map(AccRelVal);
-          }
-        } else if (MA->isWrite()) {
-          // Remove (possibly) overwritten values from the known elements set.
-          // We remove all elements of the accessed array to avoid too complex
-          // isl sets.
-          isl::set AccRelUniv = isl::set::universe(AccRelWrapped.get_space());
-          Known = Known.subtract_domain(AccRelUniv);
 
-          // At this point, we could add the written value of must-writes.
-          // However, writing same values is already handled by
-          // coalesceWrites().
-        }
-      }
-    }
-  }
 
-  /// Remove statements without side effects.
-  void removeUnnecessaryStmts() {
-    auto NumStmtsBefore = S->getSize();
-    S->simplifySCoP(true);
-    assert(NumStmtsBefore >= S->getSize());
-    StmtsRemoved = NumStmtsBefore - S->getSize();
-    LLVM_DEBUG(dbgs() << "Removed " << StmtsRemoved << " (of " << NumStmtsBefore
-                      << ") statements\n");
-    TotalStmtsRemoved[CallNo] += StmtsRemoved;
-  }
+void SimplifyVisitor::removeUnnecessaryStmts() {
 
-  /// Remove accesses that have an empty domain.
-  void removeEmptyPartialAccesses() {
-    for (ScopStmt &Stmt : *S) {
-      // Defer the actual removal to not invalidate iterators.
-      SmallVector<MemoryAccess *, 8> DeferredRemove;
+void SimplifyVisitor::removeEmptyPartialAccesses() {
 
-      for (MemoryAccess *MA : Stmt) {
-        if (!MA->isWrite())
-          continue;
 
-        isl::map AccRel = MA->getAccessRelation();
-        if (!AccRel.is_empty().is_true())
-          continue;
 
-        LLVM_DEBUG(
-            dbgs() << "Removing " << MA
-                   << " because it's a partial access that never occurs\n");
-        DeferredRemove.push_back(MA);
-      }
 
-      for (MemoryAccess *MA : DeferredRemove) {
-        Stmt.removeSingleMemoryAccess(MA);
-        EmptyPartialAccessesRemoved++;
-        TotalEmptyPartialAccessesRemoved[CallNo]++;
-      }
-    }
-  }
 
-  /// Mark all reachable instructions and access, and sweep those that are not
-  /// reachable.
-  void markAndSweep(LoopInfo *LI) {
-    DenseSet<MemoryAccess *> UsedMA;
-    DenseSet<VirtualInstruction> UsedInsts;
+void SimplifyVisitor::markAndSweep(LoopInfo *LI) {
 
-    // Get all reachable instructions and accesses.
-    markReachable(S, LI, UsedInsts, UsedMA);
 
-    // Remove all non-reachable accesses.
-    // We need get all MemoryAccesses first, in order to not invalidate the
-    // iterators when removing them.
-    SmallVector<MemoryAccess *, 64> AllMAs;
-    for (ScopStmt &Stmt : *S)
-      AllMAs.append(Stmt.begin(), Stmt.end());
 
-    for (MemoryAccess *MA : AllMAs) {
-      if (UsedMA.count(MA))
-        continue;
-      LLVM_DEBUG(dbgs() << "Removing " << MA
-                        << " because its value is not used\n");
-      ScopStmt *Stmt = MA->getStatement();
-      Stmt->removeSingleMemoryAccess(MA);
 
-      DeadAccessesRemoved++;
-      TotalDeadAccessesRemoved[CallNo]++;
-    }
 
-    // Remove all non-reachable instructions.
-    for (ScopStmt &Stmt : *S) {
-      // Note that for region statements, we can only remove the non-terminator
-      // instructions of the entry block. All other instructions are not in the
-      // instructions list, but implicitly always part of the statement.
 
-      SmallVector<Instruction *, 32> AllInsts(Stmt.insts_begin(),
-                                              Stmt.insts_end());
-      SmallVector<Instruction *, 32> RemainInsts;
 
-      for (Instruction *Inst : AllInsts) {
-        auto It = UsedInsts.find({&Stmt, Inst});
-        if (It == UsedInsts.end()) {
-          LLVM_DEBUG(dbgs() << "Removing "; Inst->print(dbgs());
-                     dbgs() << " because it is not used\n");
-          DeadInstructionsRemoved++;
-          TotalDeadInstructionsRemoved[CallNo]++;
-          continue;
-        }
 
-        RemainInsts.push_back(Inst);
 
-        // If instructions appear multiple times, keep only the first.
-        UsedInsts.erase(It);
-      }
 
-      // Set the new instruction list to be only those we did not remove.
-      Stmt.setInstructions(RemainInsts);
-    }
-  }
 
-  /// Print simplification statistics to @p OS.
-  void printStatistics(llvm::raw_ostream &OS, int Indent = 0) const {
-    OS.indent(Indent) << "Statistics {\n";
-    OS.indent(Indent + 4) << "Empty domains removed: " << EmptyDomainsRemoved
-                          << '\n';
-    OS.indent(Indent + 4) << "Overwrites removed: " << OverwritesRemoved
-                          << '\n';
-    OS.indent(Indent + 4) << "Partial writes coalesced: " << WritesCoalesced
-                          << "\n";
-    OS.indent(Indent + 4) << "Redundant writes removed: "
-                          << RedundantWritesRemoved << "\n";
-    OS.indent(Indent + 4) << "Accesses with empty domains removed: "
-                          << EmptyPartialAccessesRemoved << "\n";
-    OS.indent(Indent + 4) << "Dead accesses removed: " << DeadAccessesRemoved
-                          << '\n';
-    OS.indent(Indent + 4) << "Dead instructions removed: "
-                          << DeadInstructionsRemoved << '\n';
-    OS.indent(Indent + 4) << "Stmts removed: " << StmtsRemoved << "\n";
-    OS.indent(Indent) << "}\n";
-  }
+void SimplifyVisitor::printStatistics(llvm::raw_ostream &OS, int Indent) const {
+  OS.indent(Indent + 4) << "Overwrites removed: " << OverwritesRemoved << '\n';
 
-  /// Print the current state of all MemoryAccesses to @p OS.
-  void printAccesses(llvm::raw_ostream &OS, int Indent = 0) const {
-    OS.indent(Indent) << "After accesses {\n";
-    for (auto &Stmt : *S) {
-      OS.indent(Indent + 4) << Stmt.getBaseName() << "\n";
-      for (auto *MA : Stmt)
-        MA->print(OS);
-    }
-    OS.indent(Indent) << "}\n";
-  }
+void SimplifyVisitor::printAccesses(llvm::raw_ostream &OS, int Indent) const {
 
-public:
-  static char ID;
-  explicit Simplify(int CallNo = 0) : ScopPass(ID), CallNo(CallNo) {}
-
-  virtual void getAnalysisUsage(AnalysisUsage &AU) const override {
-    AU.addRequiredTransitive<ScopInfoRegionPass>();
-    AU.addRequired<LoopInfoWrapperPass>();
-    AU.setPreservesAll();
-  }
-
-  virtual bool runOnScop(Scop &S) override {
-    // Reset statistics of last processed SCoP.
-    releaseMemory();
-    assert(!isModified());
+bool SimplifyVisitor::visit(Scop &S, LoopInfo *LI) {
 
-    // Prepare processing of this SCoP.
-    this->S = &S;
-    ScopsProcessed[CallNo]++;
 
-    LLVM_DEBUG(dbgs() << "Removing statements that are never executed...\n");
-    removeEmptyDomainStmts();
 
-    LLVM_DEBUG(dbgs() << "Removing partial writes that never happen...\n");
-    removeEmptyPartialAccesses();
 
-    LLVM_DEBUG(dbgs() << "Removing overwrites...\n");
-    removeOverwrites();
 
-    LLVM_DEBUG(dbgs() << "Coalesce partial writes...\n");
-    coalesceWrites();
 
-    LLVM_DEBUG(dbgs() << "Removing redundant writes...\n");
-    removeRedundantWrites();
 
-    LLVM_DEBUG(dbgs() << "Cleanup unused accesses...\n");
-    LoopInfo *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
-    markAndSweep(LI);
 
-    LLVM_DEBUG(dbgs() << "Removing statements without side effects...\n");
-    removeUnnecessaryStmts();
 
-    if (isModified())
-      ScopsModified[CallNo]++;
-    LLVM_DEBUG(dbgs() << "\nFinal Scop:\n");
-    LLVM_DEBUG(dbgs() << S);
 
-    auto ScopStats = S.getStatistics();
-    NumValueWrites[CallNo] += ScopStats.NumValueWrites;
-    NumValueWritesInLoops[CallNo] += ScopStats.NumValueWritesInLoops;
-    NumPHIWrites[CallNo] += ScopStats.NumPHIWrites;
-    NumPHIWritesInLoops[CallNo] += ScopStats.NumPHIWritesInLoops;
-    NumSingletonWrites[CallNo] += ScopStats.NumSingletonWrites;
-    NumSingletonWritesInLoops[CallNo] += ScopStats.NumSingletonWritesInLoops;
 
-    return false;
-  }
 
-  virtual void printScop(raw_ostream &OS, Scop &S) const override {
-    assert(&S == this->S &&
-           "Can only print analysis for the last processed SCoP");
-    printStatistics(OS);
+void SimplifyVisitor::printScop(raw_ostream &OS, Scop &S) const {
 
-    if (!isModified()) {
-      OS << "SCoP could not be simplified\n";
-      return;
-    }
-    printAccesses(OS);
-  }
 
-  virtual void releaseMemory() override {
-    S = nullptr;
+void SimplifyVisitor::releaseMemory() {
 
-    EmptyDomainsRemoved = 0;
-    OverwritesRemoved = 0;
-    WritesCoalesced = 0;
-    RedundantWritesRemoved = 0;
-    EmptyPartialAccessesRemoved = 0;
-    DeadAccessesRemoved = 0;
-    DeadInstructionsRemoved = 0;
-    StmtsRemoved = 0;
-  }
+
+class SimplifyLegacyPass : public ScopPass {
+public:
+  static char ID;
+  SimplifyVisitor Imp;
+
+  explicit SimplifyLegacyPass(int CallNo = 0) : ScopPass(ID), Imp(CallNo) {}
+
+  virtual void getAnalysisUsage(AnalysisUsage &AU) const override {
+    AU.addRequiredTransitive<ScopInfoRegionPass>();
+    AU.addRequired<LoopInfoWrapperPass>();
+    AU.setPreservesAll();
+  }
+
+  virtual bool runOnScop(Scop &S) override {
+    return Imp.visit(S, &getAnalysis<LoopInfoWrapperPass>().getLoopInfo());
+  }
+
+  virtual void printScop(raw_ostream &OS, Scop &S) const override {
+    Imp.printScop(OS, S);
+  }
+
+  virtual void releaseMemory() override { Imp.releaseMemory(); }
 };
 
-char Simplify::ID;
+char SimplifyLegacyPass::ID;
 } // anonymous namespace
 
 namespace polly {
+llvm::PreservedAnalyses SimplifyPass::run(Scop &S, ScopAnalysisManager &SAM,
+                                          ScopStandardAnalysisResults &SAR,
+                                          SPMUpdater &U) {
+  if (!Imp.visit(S, &SAR.LI))
+    return llvm::PreservedAnalyses::all();
+
+  return llvm::PreservedAnalyses::none();
+}
+
+llvm::PreservedAnalyses
+SimplifyPrinterPass::run(Scop &S, ScopAnalysisManager &SAM,
+                         ScopStandardAnalysisResults &SAR, SPMUpdater &U) {
+  bool Changed = Imp.visit(S, &SAR.LI);
+  Imp.printScop(OS, S);
+
+  if (!Changed)
+    return llvm::PreservedAnalyses::all();
+
+  return llvm::PreservedAnalyses::none();
+}
+
 SmallVector<MemoryAccess *, 32> getAccessesInOrder(ScopStmt &Stmt) {
 
   SmallVector<MemoryAccess *, 32> Accesses;
 
   for (MemoryAccess *MemAcc : Stmt)
     if (isImplicitRead(MemAcc))
       Accesses.push_back(MemAcc);
 
   for (MemoryAccess *MemAcc : Stmt)
     if (isExplicitAccess(MemAcc))
       Accesses.push_back(MemAcc);
 
   for (MemoryAccess *MemAcc : Stmt)
     if (isImplicitWrite(MemAcc))
       Accesses.push_back(MemAcc);
 
   return Accesses;
 }
 } // namespace polly
 
-Pass *polly::createSimplifyPass(int CallNo) { return new Simplify(CallNo); }
+Pass *polly::createSimplifyPass(int CallNo) {
+  return new SimplifyLegacyPass(CallNo);
+}
 
-INITIALIZE_PASS_BEGIN(Simplify, "polly-simplify", "Polly - Simplify", false,
-                      false)
+INITIALIZE_PASS_BEGIN(SimplifyLegacyPass, "polly-simplify", "Polly - Simplify",
+                      false, false)
 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
-INITIALIZE_PASS_END(Simplify, "polly-simplify", "Polly - Simplify", false,
-                    false)
+INITIALIZE_PASS_END(SimplifyLegacyPass, "polly-simplify", "Polly - Simplify",
+                    false, false)

polly/test/Simplify/dead_access_load.ll

 ; RUN: opt %loadPolly -polly-stmt-granularity=bb -polly-simplify -analyze < %s | FileCheck %s -match-full-lines
+; RUN: opt %loadPolly -polly-stmt-granularity=bb "-passes=scop(print<polly-simplify>)" -disable-output -aa-pipeline=basic-aa < %s | FileCheck %s -match-full-lines
 ;
 ; Remove a dead load-instruction
 ; (an load whose result is not used anywhere)
 ;
 ; for (int j = 0; j < n; j += 1) {
 ;   double val = A[0];
 ;   A[0] = 42.0;
 ; }

polly/test/Simplify/dead_access_phi.ll

 ; RUN: opt %loadPolly -polly-stmt-granularity=bb -polly-simplify -analyze < %s | FileCheck %s -match-full-lines
+; RUN: opt %loadPolly -polly-stmt-granularity=bb "-passes=scop(print<polly-simplify>)" -disable-output -aa-pipeline=basic-aa < %s | FileCheck %s -match-full-lines
 ;
 ; Remove a dead PHI write/read pair
 ; (accesses that are effectively not used)
 ;
 ; for (int j = 0; j < n; j += 1) {
 ; body:
 ;   double phi = 42;
 ; 

polly/test/Simplify/dead_access_value.ll

 ; RUN: opt %loadPolly -polly-stmt-granularity=bb -polly-simplify -analyze < %s | FileCheck %s -match-full-lines
+; RUN: opt %loadPolly -polly-stmt-granularity=bb "-passes=scop(print<polly-simplify>)" -disable-output -aa-pipeline=basic-aa < %s | FileCheck %s -match-full-lines
 ;
 ; Remove a dead value write/read pair
 ; (accesses that are effectively not used)
 ;
 ; for (int j = 0; j < n; j += 1) {
 ; body:
 ;   double val = 12.5 + 12.5;
 ; 

polly/test/Simplify/dead_instruction.ll

 ; RUN: opt %loadPolly -polly-stmt-granularity=bb -polly-simplify -analyze < %s | FileCheck %s -match-full-lines
+; RUN: opt %loadPolly -polly-stmt-granularity=bb "-passes=scop(print<polly-simplify>)" -disable-output -aa-pipeline=basic-aa < %s | FileCheck %s -match-full-lines
 ;
 ; Remove a dead instruction
 ; (an instruction whose result is not used anywhere)
 ;
 ; for (int j = 0; j < n; j += 1) {
 ;   double val = 21.0 + 21.0;
 ;   A[0] = 42.0;
 ; }

polly/test/Simplify/notdead_region_exitphi.ll

 ; RUN: opt %loadPolly -polly-simplify -analyze < %s | FileCheck %s -match-full-lines
+; RUN: opt %loadPolly "-passes=scop(print<polly-simplify>)" -disable-output -aa-pipeline=basic-aa < %s | FileCheck %s -match-full-lines
 ;
 ; Do not remove dependencies of a phi node in a region's exit block.
 ;
 define void @func(i32 %n, double* noalias nonnull %A, double %alpha) {
 entry:
   br label %for
 
 for:

polly/test/Simplify/notdead_region_innerphi.ll

 ; RUN: opt %loadPolly -polly-simplify -analyze < %s | FileCheck %s -match-full-lines
+; RUN: opt %loadPolly "-passes=scop(print<polly-simplify>)" -disable-output -aa-pipeline=basic-aa < %s | FileCheck %s -match-full-lines
 ;
 ; Do not remove dependencies of a phi node within a region statement (%phi).
 ;
 define void @func(i32 %n, double* noalias nonnull %A, double %alpha) {
 entry:
   br label %for
 
 for:

polly/test/Simplify/notredundant_region_middle.ll

 ; RUN: opt %loadPolly -polly-simplify -analyze < %s | FileCheck %s -match-full-lines
+; RUN: opt %loadPolly "-passes=scop(print<polly-simplify>)" -disable-output -aa-pipeline=basic-aa < %s | FileCheck %s -match-full-lines
 ;
 ; Do not remove redundant stores in the middle of region statements.
 ; The store in region_true could be removed, but in practice we do try to
 ; determine the relative ordering of block in region statements.
 ;
 ; for (int j = 0; j < n; j += 1) {
 ;   double val = A[0];
 ;   if (val == 0.0)

polly/test/Simplify/notredundant_synthesizable_unknownit.ll

 ; RUN: opt %loadPolly -polly-stmt-granularity=bb -polly-simplify -analyze < %s | FileCheck %s -match-full-lines
+; RUN: opt %loadPolly -polly-stmt-granularity=bb "-passes=scop(print<polly-simplify>)" -disable-output -aa-pipeline=basic-aa < %s | FileCheck %s -match-full-lines
 ;
 ; Do not remove the scalar value write of %i.trunc in inner.for.
 ; It is used by body.
 ; %i.trunc is synthesizable in inner.for, so some code might think it is
 ; synthesizable everywhere such that no scalar write would be needed.
 ;
 ; Note that -polly-simplify rightfully removes %inner.cond. It should
 ; not have been added to the instruction list in the first place.

polly/test/Simplify/overwritten.ll

 ; RUN: opt %loadPolly -polly-stmt-granularity=bb -polly-simplify -analyze < %s | FileCheck -match-full-lines %s 
+; RUN: opt %loadPolly -polly-stmt-granularity=bb "-passes=scop(print<polly-simplify>)" -disable-output -aa-pipeline=basic-aa < %s | FileCheck -match-full-lines %s 
 ;
 ; Remove a store that is overwritten by another store in the same statement.
 ;
 ; for (int j = 0; j < n; j += 1) {
 ;   A[0] = 21.0;
 ;   A[0] = 42.0;
 ; }
 ;

polly/test/Simplify/overwritten_3store.ll

 ; RUN: opt %loadPolly -polly-stmt-granularity=bb -polly-simplify -analyze < %s | FileCheck -match-full-lines %s 
+; RUN: opt %loadPolly -polly-stmt-granularity=bb "-passes=scop(print<polly-simplify>)" -disable-output -aa-pipeline=basic-aa < %s | FileCheck -match-full-lines %s 
 ;
 ; Remove a store that is overwritten by another store in the same statement.
 ; Check that even multiple stores are removed.
 ;
 ; for (int j = 0; j < n; j += 1) {
 ;   A[0] = 10.5;
 ;   A[0] = 21.0;
 ;   A[0] = 42.0;

polly/test/Simplify/overwritten_loadbetween.ll

 ; RUN: opt %loadPolly -polly-simplify -analyze < %s | FileCheck -match-full-lines %s 
+; RUN: opt %loadPolly "-passes=scop(print<polly-simplify>)" -disable-output -aa-pipeline=basic-aa < %s | FileCheck -match-full-lines %s 
 ;
 ; Do not remove overwrites when the value is read before.
 ;
 ; for (int j = 0; j < n; j += 1) {
 ;body:
 ;   A[0] = 21.0;
 ;   val = A[0];
 ;   A[0] = 42.0;

polly/test/Simplify/pass_existence.ll

 ; RUN: opt %loadPolly -polly-simplify -analyze < %s | FileCheck %s
+; RUN: opt %loadPolly -disable-output "-passes=scop(print<polly-simplify>)" < %s -aa-pipeline=basic-aa < %s | FileCheck %s
 ;
 ; Simple test for the existence of the Simplify pass.
 ;
 ; for (int j = 0; j < n; j += 1)
 ;   A[0] = 0.0;
 ;
 define void @func(i32 %n, double* noalias nonnull %A) {
 entry:

polly/test/Simplify/phi_in_regionstmt.ll

 ; RUN: opt %loadPolly -polly-simplify -analyze < %s | FileCheck %s -match-full-lines
+; RUN: opt %loadPolly "-passes=scop(print<polly-simplify>)" -disable-output -aa-pipeline=basic-aa < %s | FileCheck %s -match-full-lines
 ;
 ; The PHINode %cond91.sink.sink.us.sink.6 is in the middle of a region
 ; statement.
 ; Check that we are not expect a MemoryKind::PHI access for it, and no
 ; assertion guarding querying for it.
 ;
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 

polly/test/Simplify/redundant.ll

 ; RUN: opt %loadPolly -polly-simplify -analyze < %s | FileCheck %s -match-full-lines
+; RUN: opt %loadPolly "-passes=scop(print<polly-simplify>)" -disable-output -aa-pipeline=basic-aa < %s | FileCheck %s -match-full-lines
 ;
 ; Remove redundant store (a store that writes the same value already
 ; at the destination)
 ;
 ; for (int j = 0; j < n; j += 1)
 ;   A[0] = A[0];
 ;
 define void @func(i32 %n, double* noalias nonnull %A) {

polly/test/Simplify/redundant_differentindex.ll

 ; RUN: opt %loadPolly -polly-simplify -analyze < %s | FileCheck %s -match-full-lines
+; RUN: opt %loadPolly "-passes=scop(print<polly-simplify>)" -disable-output -aa-pipeline=basic-aa < %s | FileCheck %s -match-full-lines
 ;
 ; A store that has a different index than the load it is storing is
 ; not redundant.
 ;
 ; for (int j = 0; j < n; j += 1)
 ;   A[0] = A[0];
 ;
 define void @func(i32 %n, double* noalias nonnull %A) {

polly/test/Simplify/redundant_storebetween.ll

 ; RUN: opt %loadPolly -polly-simplify -analyze < %s | FileCheck %s -match-full-lines
+; RUN: opt %loadPolly "-passes=scop(print<polly-simplify>)" -disable-output -aa-pipeline=basic-aa < %s | FileCheck %s -match-full-lines
 ;
 ; Don't remove store where there is another store to the same target
 ; in-between them.
 ;
 ; for (int j = 0; j < n; j += 1)
 ;   A[0] = A[0];
 ;
 define void @func(i32 %n, double* noalias nonnull %A) {