Update MemorySSA in LoopSimplifyCFG.

[asbirlea]

Summary

Add MemorySSA as a dependency to LoopSimplifyCFG and preserve it.
Disabled by default until all passes preserve MemorySSA.

[chandlerc]

lib/Transforms/Scalar/LoopSimplifyCFG.cpp

77–81

Same comment as on other patch -- could we use an Optional here to avoid heap allocation?

[asbirlea]

Address comment.

[asbirlea]

Updated to allocate mssaupdater.

[asbirlea]

Update to simple constructor.

[chandlerc]

LGTM

[asbirlea]

Thank you for the review!

lib/Transforms/Scalar/LoopSimplifyCFG.cpp

 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/AssumptionCache.h"
 #include "llvm/Analysis/BasicAliasAnalysis.h"
 #include "llvm/Analysis/DependenceAnalysis.h"
 #include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/LoopPass.h"
+#include "llvm/Analysis/MemorySSA.h"
+#include "llvm/Analysis/MemorySSAUpdater.h"
 #include "llvm/Analysis/ScalarEvolution.h"
 #include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"
 #include "llvm/Analysis/TargetTransformInfo.h"
 #include "llvm/IR/DomTreeUpdater.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/Transforms/Scalar.h"
 #include "llvm/Transforms/Scalar/LoopPassManager.h"
 #include "llvm/Transforms/Utils.h"
 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
 #include "llvm/Transforms/Utils/Local.h"
 #include "llvm/Transforms/Utils/LoopUtils.h"
 using namespace llvm;
 
 #define DEBUG_TYPE "loop-simplifycfg"
 
 static bool simplifyLoopCFG(Loop &L, DominatorTree &DT, LoopInfo &LI,
-                            ScalarEvolution &SE) {
+                            ScalarEvolution &SE, MemorySSAUpdater *MSSAU) {
   bool Changed = false;
   DomTreeUpdater DTU(DT, DomTreeUpdater::UpdateStrategy::Eager);
   // Copy blocks into a temporary array to avoid iterator invalidation issues
   // as we remove them.
   SmallVector<WeakTrackingVH, 16> Blocks(L.blocks());
 
   for (auto &Block : Blocks) {
     // Attempt to merge blocks in the trivial case. Don't modify blocks which
     // belong to other loops.
     BasicBlock *Succ = cast_or_null<BasicBlock>(Block);
     if (!Succ)
       continue;
 
     BasicBlock *Pred = Succ->getSinglePredecessor();
     if (!Pred || !Pred->getSingleSuccessor() || LI.getLoopFor(Pred) != &L)
       continue;
 
     // Merge Succ into Pred and delete it.
-    MergeBlockIntoPredecessor(Succ, &DTU, &LI);
+    MergeBlockIntoPredecessor(Succ, &DTU, &LI, MSSAU);
 
     SE.forgetTopmostLoop(&L);
 
     Changed = true;
   }
 
   return Changed;
 }
 
 PreservedAnalyses LoopSimplifyCFGPass::run(Loop &L, LoopAnalysisManager &AM,
                                            LoopStandardAnalysisResults &AR,
                                            LPMUpdater &) {
-  if (!simplifyLoopCFG(L, AR.DT, AR.LI, AR.SE))
+  Optional<MemorySSAUpdater> MSSAU;
+  if (EnableMSSALoopDependency && AR.MSSA)
+    MSSAU = MemorySSAUpdater(AR.MSSA);
+  if (!simplifyLoopCFG(L, AR.DT, AR.LI, AR.SE,
+                       MSSAU.hasValue() ? MSSAU.getPointer() : nullptr))
     return PreservedAnalyses::all();
 
   return getLoopPassPreservedAnalyses();
 }
 
 namespace {
 class LoopSimplifyCFGLegacyPass : public LoopPass {
 public:
   static char ID; // Pass ID, replacement for typeid
   LoopSimplifyCFGLegacyPass() : LoopPass(ID) {
     initializeLoopSimplifyCFGLegacyPassPass(*PassRegistry::getPassRegistry());
   }
 
   bool runOnLoop(Loop *L, LPPassManager &) override {
     if (skipLoop(L))
       return false;
 
     DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
     LoopInfo &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
     ScalarEvolution &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE();
-    return simplifyLoopCFG(*L, DT, LI, SE);
+    Optional<MemorySSAUpdater> MSSAU;
+    if (EnableMSSALoopDependency) {
+      MemorySSA *MSSA = &getAnalysis<MemorySSAWrapperPass>().getMSSA();
+      MSSAU = MemorySSAUpdater(MSSA);
+      if (VerifyMemorySSA)
+        MSSA->verifyMemorySSA();
+    }
+    return simplifyLoopCFG(*L, DT, LI, SE,
+                           MSSAU.hasValue() ? MSSAU.getPointer() : nullptr);
   }
 
   void getAnalysisUsage(AnalysisUsage &AU) const override {
+    if (EnableMSSALoopDependency) {
+      AU.addRequired<MemorySSAWrapperPass>();
+      AU.addPreserved<MemorySSAWrapperPass>();
+    }
     AU.addPreserved<DependenceAnalysisWrapperPass>();
     getLoopAnalysisUsage(AU);
   }
 };
 }
 
 char LoopSimplifyCFGLegacyPass::ID = 0;
 INITIALIZE_PASS_BEGIN(LoopSimplifyCFGLegacyPass, "loop-simplifycfg",
                       "Simplify loop CFG", false, false)
 INITIALIZE_PASS_DEPENDENCY(LoopPass)
+INITIALIZE_PASS_DEPENDENCY(MemorySSAWrapperPass)
 INITIALIZE_PASS_END(LoopSimplifyCFGLegacyPass, "loop-simplifycfg",
                     "Simplify loop CFG", false, false)
 
 Pass *llvm::createLoopSimplifyCFGPass() {
   return new LoopSimplifyCFGLegacyPass();
 }

test/Transforms/LoopSimplifyCFG/merge-header.ll

 ; RUN: opt -S -loop-simplifycfg < %s | FileCheck %s
 ; RUN: opt -S -passes='require<domtree>,loop(simplify-cfg)' < %s | FileCheck %s
+; RUN: opt -S -loop-simplifycfg -enable-mssa-loop-dependency=true -verify-memoryssa < %s | FileCheck %s
 
 ; CHECK-LABEL: foo
 ; CHECK:      entry:
 ; CHECK-NEXT:   br label %[[LOOP:[a-z]+]]
 ; CHECK:      [[LOOP]]:
 ; CHECK-NEXT:   phi
 ; CHECK-NOT:    br label
 ; CHECK:        br i1

test/Transforms/LoopSimplifyCFG/scev.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -S -loop-simplifycfg -verify-scev < %s | FileCheck %s
+; RUN: opt -S -loop-simplifycfg -verify-scev -enable-mssa-loop-dependency=true -verify-memoryssa < %s | FileCheck %s
 
 ; Verify that the scev information is still valid. Verification should not fail
 
 define void @t_run_test() {
 ; CHECK-LABEL: @t_run_test(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label %[[LOOP_PH:.*]]
 ; CHECK:       [[LOOP_PH]]: