Revert "Revert "Expand existing loopsink testing to also test loopsinking using new pass manager and fix LICM bug.""

This reverts commit 562addba652e8bdabe49f9123fd92c21b7a0d640.

Reverted change too quickly, the failing test cases passed on the next build.
So reverting revert (to include the changes).

1 files changed, 108 insertions, 21 deletions

diff --git a/llvm/lib/Transforms/Scalar/LoopSink.cpp b/llvm/lib/Transforms/Scalar/LoopSink.cpp
index 1c03a4b..6b9333c 100644
--- a/llvm/lib/Transforms/Scalar/LoopSink.cpp
+++ b/llvm/lib/Transforms/Scalar/LoopSink.cpp
@@ -39,6 +39,8 @@
 #include "llvm/Analysis/Loads.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/IR/Dominators.h"
@@ -67,6 +69,14 @@ static cl::opt<unsigned> MaxNumberOfUseBBsForSinking(
     "max-uses-for-sinking", cl::Hidden, cl::init(30),
     cl::desc("Do not sink instructions that have too many uses."));
 
+static cl::opt<bool> EnableMSSAInLoopSink(
+    "enable-mssa-in-loop-sink", cl::Hidden, cl::init(false),
+    cl::desc("Enable MemorySSA for LoopSink in new pass manager"));
+
+static cl::opt<bool> EnableMSSAInLegacyLoopSink(
+    "enable-mssa-in-legacy-loop-sink", cl::Hidden, cl::init(false),
+    cl::desc("Enable MemorySSA for LoopSink in legacy pass manager"));
+
 /// Return adjusted total frequency of \p BBs.
 ///
 /// * If there is only one BB, sinking instruction will not introduce code
@@ -172,11 +182,10 @@ findBBsToSinkInto(const Loop &L, const SmallPtrSetImpl<BasicBlock *> &UseBBs,
 // sinking is successful.
 // \p LoopBlockNumber is used to sort the insertion blocks to ensure
 // determinism.
-static bool sinkInstruction(Loop &L, Instruction &I,
-                            const SmallVectorImpl<BasicBlock *> &ColdLoopBBs,
-                            const SmallDenseMap<BasicBlock *, int, 16> &LoopBlockNumber,
-                            LoopInfo &LI, DominatorTree &DT,
-                            BlockFrequencyInfo &BFI) {
+static bool sinkInstruction(
+    Loop &L, Instruction &I, const SmallVectorImpl<BasicBlock *> &ColdLoopBBs,
+    const SmallDenseMap<BasicBlock *, int, 16> &LoopBlockNumber, LoopInfo &LI,
+    DominatorTree &DT, BlockFrequencyInfo &BFI, MemorySSAUpdater *MSSAU) {
   // Compute the set of blocks in loop L which contain a use of I.
   SmallPtrSet<BasicBlock *, 2> BBs;
   for (auto &U : I.uses()) {
@@ -230,6 +239,21 @@ static bool sinkInstruction(Loop &L, Instruction &I,
     Instruction *IC = I.clone();
     IC->setName(I.getName());
     IC->insertBefore(&*N->getFirstInsertionPt());
+
+    if (MSSAU && MSSAU->getMemorySSA()->getMemoryAccess(&I)) {
+      // Create a new MemoryAccess and let MemorySSA set its defining access.
+      MemoryAccess *NewMemAcc =
+          MSSAU->createMemoryAccessInBB(IC, nullptr, N, MemorySSA::Beginning);
+      if (NewMemAcc) {
+        if (auto *MemDef = dyn_cast<MemoryDef>(NewMemAcc))
+          MSSAU->insertDef(MemDef, /*RenameUses=*/true);
+        else {
+          auto *MemUse = cast<MemoryUse>(NewMemAcc);
+          MSSAU->insertUse(MemUse, /*RenameUses=*/true);
+        }
+      }
+    }
+
     // Replaces uses of I with IC in N
     I.replaceUsesWithIf(IC, [N](Use &U) {
       return cast<Instruction>(U.getUser())->getParent() == N;
@@ -244,6 +268,11 @@ static bool sinkInstruction(Loop &L, Instruction &I,
   NumLoopSunk++;
   I.moveBefore(&*MoveBB->getFirstInsertionPt());
 
+  if (MSSAU)
+    if (MemoryUseOrDef *OldMemAcc = cast_or_null<MemoryUseOrDef>(
+            MSSAU->getMemorySSA()->getMemoryAccess(&I)))
+      MSSAU->moveToPlace(OldMemAcc, MoveBB, MemorySSA::Beginning);
+
   return true;
 }
 
@@ -252,10 +281,11 @@ static bool sinkInstruction(Loop &L, Instruction &I,
 static bool sinkLoopInvariantInstructions(Loop &L, AAResults &AA, LoopInfo &LI,
                                           DominatorTree &DT,
                                           BlockFrequencyInfo &BFI,
-                                          ScalarEvolution *SE) {
+                                          ScalarEvolution *SE,
+                                          AliasSetTracker *CurAST,
+                                          MemorySSA *MSSA) {
   BasicBlock *Preheader = L.getLoopPreheader();
-  if (!Preheader)
-    return false;
+  assert(Preheader && "Expected loop to have preheader");
 
   // Enable LoopSink only when runtime profile is available.
   // With static profile, the sinking decision may be sub-optimal.
@@ -271,13 +301,15 @@ static bool sinkLoopInvariantInstructions(Loop &L, AAResults &AA, LoopInfo &LI,
       }))
     return false;
 
-  bool Changed = false;
-  AliasSetTracker CurAST(AA);
+  std::unique_ptr<MemorySSAUpdater> MSSAU;
+  std::unique_ptr<SinkAndHoistLICMFlags> LICMFlags;
+  if (MSSA) {
+    MSSAU = std::make_unique<MemorySSAUpdater>(MSSA);
+    LICMFlags =
+        std::make_unique<SinkAndHoistLICMFlags>(/*IsSink=*/true, &L, MSSA);
+  }
 
-  // Compute alias set.
-  for (BasicBlock *BB : L.blocks())
-    CurAST.add(*BB);
-  CurAST.add(*Preheader);
+  bool Changed = false;
 
   // Sort loop's basic blocks by frequency
   SmallVector<BasicBlock *, 10> ColdLoopBBs;
@@ -300,9 +332,11 @@ static bool sinkLoopInvariantInstructions(Loop &L, AAResults &AA, LoopInfo &LI,
     // No need to check for instruction's operands are loop invariant.
     assert(L.hasLoopInvariantOperands(I) &&
            "Insts in a loop's preheader should have loop invariant operands!");
-    if (!canSinkOrHoistInst(*I, &AA, &DT, &L, &CurAST, nullptr, false))
+    if (!canSinkOrHoistInst(*I, &AA, &DT, &L, CurAST, MSSAU.get(), false,
+                            LICMFlags.get()))
       continue;
-    if (sinkInstruction(L, *I, ColdLoopBBs, LoopBlockNumber, LI, DT, BFI))
+    if (sinkInstruction(L, *I, ColdLoopBBs, LoopBlockNumber, LI, DT, BFI,
+                        MSSAU.get()))
       Changed = true;
   }
 
@@ -311,6 +345,13 @@ static bool sinkLoopInvariantInstructions(Loop &L, AAResults &AA, LoopInfo &LI,
   return Changed;
 }
 
+static void computeAliasSet(Loop &L, BasicBlock &Preheader,
+                            AliasSetTracker &CurAST) {
+  for (BasicBlock *BB : L.blocks())
+    CurAST.add(*BB);
+  CurAST.add(Preheader);
+}
+
 PreservedAnalyses LoopSinkPass::run(Function &F, FunctionAnalysisManager &FAM) {
   LoopInfo &LI = FAM.getResult<LoopAnalysis>(F);
   // Nothing to do if there are no loops.
@@ -321,6 +362,10 @@ PreservedAnalyses LoopSinkPass::run(Function &F, FunctionAnalysisManager &FAM) {
   DominatorTree &DT = FAM.getResult<DominatorTreeAnalysis>(F);
   BlockFrequencyInfo &BFI = FAM.getResult<BlockFrequencyAnalysis>(F);
 
+  MemorySSA *MSSA = EnableMSSAInLoopSink
+                        ? &FAM.getResult<MemorySSAAnalysis>(F).getMSSA()
+                        : nullptr;
+
   // We want to do a postorder walk over the loops. Since loops are a tree this
   // is equivalent to a reversed preorder walk and preorder is easy to compute
   // without recursion. Since we reverse the preorder, we will visit siblings
@@ -332,11 +377,22 @@ PreservedAnalyses LoopSinkPass::run(Function &F, FunctionAnalysisManager &FAM) {
   do {
     Loop &L = *PreorderLoops.pop_back_val();
 
+    BasicBlock *Preheader = L.getLoopPreheader();
+    if (!Preheader)
+      continue;
+
+    std::unique_ptr<AliasSetTracker> CurAST;
+    if (!EnableMSSAInLoopSink) {
+      CurAST = std::make_unique<AliasSetTracker>(AA);
+      computeAliasSet(L, *Preheader, *CurAST.get());
+    }
+
     // Note that we don't pass SCEV here because it is only used to invalidate
     // loops in SCEV and we don't preserve (or request) SCEV at all making that
     // unnecessary.
     Changed |= sinkLoopInvariantInstructions(L, AA, LI, DT, BFI,
-                                             /*ScalarEvolution*/ nullptr);
+                                             /*ScalarEvolution*/ nullptr,
+                                             CurAST.get(), MSSA);
   } while (!PreorderLoops.empty());
 
   if (!Changed)
@@ -344,6 +400,14 @@ PreservedAnalyses LoopSinkPass::run(Function &F, FunctionAnalysisManager &FAM) {
 
   PreservedAnalyses PA;
   PA.preserveSet<CFGAnalyses>();
+
+  if (MSSA) {
+    PA.preserve<MemorySSAAnalysis>();
+
+    if (VerifyMemorySSA)
+      MSSA->verifyMemorySSA();
+  }
+
   return PA;
 }
 
@@ -358,19 +422,41 @@ struct LegacyLoopSinkPass : public LoopPass {
     if (skipLoop(L))
       return false;
 
+    BasicBlock *Preheader = L->getLoopPreheader();
+    if (!Preheader)
+      return false;
+
+    AAResults &AA = getAnalysis<AAResultsWrapperPass>().getAAResults();
     auto *SE = getAnalysisIfAvailable<ScalarEvolutionWrapperPass>();
-    return sinkLoopInvariantInstructions(
-        *L, getAnalysis<AAResultsWrapperPass>().getAAResults(),
-        getAnalysis<LoopInfoWrapperPass>().getLoopInfo(),
+    std::unique_ptr<AliasSetTracker> CurAST;
+    MemorySSA *MSSA = nullptr;
+    if (EnableMSSAInLegacyLoopSink)
+      MSSA = &getAnalysis<MemorySSAWrapperPass>().getMSSA();
+    else {
+      CurAST = std::make_unique<AliasSetTracker>(AA);
+      computeAliasSet(*L, *Preheader, *CurAST.get());
+    }
+
+    bool Changed = sinkLoopInvariantInstructions(
+        *L, AA, getAnalysis<LoopInfoWrapperPass>().getLoopInfo(),
         getAnalysis<DominatorTreeWrapperPass>().getDomTree(),
         getAnalysis<BlockFrequencyInfoWrapperPass>().getBFI(),
-        SE ? &SE->getSE() : nullptr);
+        SE ? &SE->getSE() : nullptr, CurAST.get(), MSSA);
+
+    if (MSSA && VerifyMemorySSA)
+      MSSA->verifyMemorySSA();
+
+    return Changed;
   }
 
   void getAnalysisUsage(AnalysisUsage &AU) const override {
     AU.setPreservesCFG();
     AU.addRequired<BlockFrequencyInfoWrapperPass>();
     getLoopAnalysisUsage(AU);
+    if (EnableMSSAInLegacyLoopSink) {
+      AU.addRequired<MemorySSAWrapperPass>();
+      AU.addPreserved<MemorySSAWrapperPass>();
+    }
   }
 };
 }
@@ -380,6 +466,7 @@ INITIALIZE_PASS_BEGIN(LegacyLoopSinkPass, "loop-sink", "Loop Sink", false,
                       false)
 INITIALIZE_PASS_DEPENDENCY(LoopPass)
 INITIALIZE_PASS_DEPENDENCY(BlockFrequencyInfoWrapperPass)
+INITIALIZE_PASS_DEPENDENCY(MemorySSAWrapperPass)
 INITIALIZE_PASS_END(LegacyLoopSinkPass, "loop-sink", "Loop Sink", false, false)
 
 Pass *llvm::createLoopSinkPass() { return new LegacyLoopSinkPass(); }