Add options to enable memoryssa for loopsink, expand loopsink testing and fix exposed bug in LICM

[jamieschmeiser]

Summary

Add options to enable memoryssa for loopsink (defaulting to false,
retaining the original functionality). Expand existing loopsink
testing to also test loopsinking using new pass manager. The option
exposed a bug that was previously fixed for loopsink without
memoryssa. When sinking an instruction into a loop, the source block
may not be part of the loop but still needs to be checked for
pointer invalidation. This is the fix for bugzilla #39695 (PR 54659)
expanded to also work with memoryssa. The bug is only exposed when
all the changes are combined. Just expanding the tests will not show the
bug nor will just enabling memoryssa in loopsink. They have to be done
together to show the bug hence both and the fix are all done in this PR.

Respond to comments after attempted landing: move test for profile
data earlier to avoid unnecessary computations.

[jamieschmeiser]

Note that @sidbav made contributions to these changes.

[asbirlea]

• Could you separate the SinkHoistFlag refactoring into an NFC?
• Could you clang-format and fix lints?
• LICM changes look good. AFAICT the MSSA changes in LoopSink are accurate, but it may need more testing than the existing unit tests.
• Why do you want the legacy pass manager to use the AST and the new pass manager MSSA?

[jamieschmeiser]

As requested, I have split the refactoring of the SinkAndHoistLICMFlags
into a separate PR and made this PR a child of that.

In answer to the review question, the intention is not to make the 2
passes different, but rather to advance the new pass manager version
to use memoryssa. It has been observed that LoopSinking in a new
pass manager pipeline can take significant amounts of compile time
for some cases which is mitigated by using memoryssa.

[asbirlea]

I guess my question was more regarding consistency. Why not use MSSA in the LPM as well and drop the AST usage entirely? Or provide a flag that can be used to switch between MSSA and AST version (see LICM or DSE for similar flags using MSSA or alternative analyses), just in case there are users of the AST version.

[jamieschmeiser]

Respond to review comments. Enable Memory SSA in legacy Loop Sink pass
under EnableMSSALoopDependency option control. Update tests accordingly.

[asbirlea]

The current behavior is:

• for the NPM, always use MSSA for LoopSink, which is a Function pass.
• for the LPM, LoopSink is a Loop pass and it will use MSSA conditioned on the EnableMSSALoopDependency flag which is set to true, hence this patch is switching loop sink to use MSSA.

I would suggest adding a different cl::opt, specific to LoopSink and set it to false in this patch, hence not changing the current behavior. Use this flag for both pass managers (or create two flags if you intend to flip just one).
Then in a subsequent patch change the flag(s) to true and update the pipeline tests.
This will provide a simple revert of the cl::opt value if things go wrong, and an option for potential users to disable the MSSA usage only for LoopSink, not for all the other passes (controlled by EnableMSSALoopDependency).

llvm/lib/Transforms/Scalar/LoopSink.cpp

395

/*CurAST=*/nullptr

430

Only create AST in the absence of MSSA.
The checks in canSinkOrHoistInst assume only one of the two analyses is passed in. For LICM, the asserts for this are in sinkRegion/hoistRegion. I added a similar assert in f514b32a899 to ensure this is true here as well.

[jamieschmeiser]

Respond to review comments by adding options controlling whether
memoryssa is used for loopsink, defaulting to false. Expanded the
tests to include these options.

Note that the tests for passes are still changed because the dependency
on memory ssa is required in order to allow the option of using
memory ssa in the legacy pass manager. If my understanding of this
is incorrect, please let me know and I will remove the dependency
and the changes to the passes tests.

[asbirlea]

Thank you, just a couple of small comments below.

llvm/lib/Transforms/Scalar/LoopSink.cpp

405

if (MSSA)
  PA.preserve<MemorySSAAnalysis>();

451

Use EnableMSSAInLegacyLoopSink here. This should change the tests.

[jamieschmeiser]

Respond to review comments: properly indicate preserved analyses,
which also means the changes are not needed for the pipeline tests.

[asbirlea]

lgtm.
Looking forward to having it enabled in a future patch.

llvm/lib/Transforms/Scalar/LoopSink.cpp

258

Beyond the scope of this patch: I'm wondering if there were issues here since the AST was not updated. In LICM, the update looks something like:

if (CurAST)
  CurAST->copyValue(&I, C);
I.replaceAllUsesWith(C);

[jamieschmeiser]

test failures when pushing

The Buildbot has detected a failed build on builder clang-cmake-armv7-quick while building llvm.
Full details are available at:

https://urldefense.proofpoint.com/v2/url?u=http-3A__lab.llvm.org-3A8011_-23builders_107_builds_1659&d=DwICaQ&c=jf_iaSHvJObTbx-siA1ZOg&r=Nr2SnYQn80wzIpml4veK2C-U4ilVZzi0kWYCc2WSLoA&m=v5KeUvUQ3NmVKfDF_PHQ197pdpgdKEZ2Cm6JUebPiEs&s=QQkrhJP0JJLKRQfOOzGYX0pkct6JJhzL0CHRaZMbkEE&e=

Buildbot URL: https://urldefense.proofpoint.com/v2/url?u=http-3A__lab.llvm.org-3A8011_&d=DwICaQ&c=jf_iaSHvJObTbx-siA1ZOg&r=Nr2SnYQn80wzIpml4veK2C-U4ilVZzi0kWYCc2WSLoA&m=v5KeUvUQ3NmVKfDF_PHQ197pdpgdKEZ2Cm6JUebPiEs&s=_gM68RF9ovfGi9Cd5Z7GlMzchqp751e2xZaWYOIO8Ts&e=
Worker for this Build: linaro-armv7-quick
Build Reason: <unknown>
Blamelist: Jamie Schmeiser <[e-mail]>
BUILD FAILED: failed 49489 expected passes 19381 unsupported tests 75 expected failures 1 unexpected failures Unexpected test result output 14 (failure)
Sincerely,
LLVM Buildbot

[jamieschmeiser]

The Buildbot has detected a failed build on builder clang-cmake-armv7-quick while building llvm.
Full details are available at:

https://urldefense.proofpoint.com/v2/url?u=http-3A__lab.llvm.org-3A8011_-23builders_107_builds_1659&d=DwICaQ&c=jf_iaSHvJObTbx-siA1ZOg&r=Nr2SnYQn80wzIpml4veK2C-U4ilVZzi0kWYCc2WSLoA&m=v5KeUvUQ3NmVKfDF_PHQ197pdpgdKEZ2Cm6JUebPiEs&s=QQkrhJP0JJLKRQfOOzGYX0pkct6JJhzL0CHRaZMbkEE&e=

Buildbot URL: https://urldefense.proofpoint.com/v2/url?u=http-3A__lab.llvm.org-3A8011_&d=DwICaQ&c=jf_iaSHvJObTbx-siA1ZOg&r=Nr2SnYQn80wzIpml4veK2C-U4ilVZzi0kWYCc2WSLoA&m=v5KeUvUQ3NmVKfDF_PHQ197pdpgdKEZ2Cm6JUebPiEs&s=_gM68RF9ovfGi9Cd5Z7GlMzchqp751e2xZaWYOIO8Ts&e=
Worker for this Build: linaro-armv7-quick
Build Reason: <unknown>
Blamelist: Jamie Schmeiser <[e-mail]>
BUILD FAILED: failed 49489 expected passes 19381 unsupported tests 75 expected failures 1 unexpected failures Unexpected test result output 14 (failure)
Sincerely,
LLVM Buildbot

[jamieschmeiser]

Looks like a flaky testcase, it passed on next run with my changes in on one build and the other looks like a network issue.

[nikic]

This change showed up as a significant compile-time regression (before it was reverted): https://llvm-compile-time-tracker.com/compare.php?from=85ccdcaa502ee2c478f2d0ba2b1e217117b69032&to=d4ba28bddc89a14885218b9eaa4fbf6654c2a5bd&stat=instructions

From what I understood, the usage of MemorySSA in LoopSink is still supposed to be behind a flag, so this seems unexpected to me?

[nikic]

Looking over the patch, the compile-time regression is likely not related to MemorySSA, but the fact that you moved the AST construction before the !Preheader->getParent()->hasProfileData() check, and the profitability heuristic. This means that expensive AST construction now happens every time, instead of only when useful.

[jamieschmeiser]

@nikic, this is strange because it is off by default. I've already reverted the revert, so I will check the time differences between the relanding and if it shows a regression again, I will pull it.

[jamieschmeiser]

@nikic, saw your second comment after I added mine. I will revert it and take a look.

[jamieschmeiser]

@nikic I have moved the test for profile data before the calculation of the alias sets.

llvm/lib/Transforms/Scalar/LICM.cpp

static bool isSafeToExecuteUnconditionally(Instruction &Inst,
                                            const Loop *CurLoop,
                                            const LoopSafetyInfo *SafetyInfo,
                                            OptimizationRemarkEmitter *ORE,
                                            const Instruction *CtxI = nullptr);
 static bool pointerInvalidatedByLoop(MemoryLocation MemLoc,
                                      AliasSetTracker *CurAST, Loop *CurLoop,
                                      AAResults *AA);
 static bool pointerInvalidatedByLoopWithMSSA(MemorySSA *MSSA, MemoryUse *MU,
-                                             Loop *CurLoop,
+                                             Loop *CurLoop, Instruction &I,
                                              SinkAndHoistLICMFlags &Flags);
+static bool pointerInvalidatedByBlockWithMSSA(BasicBlock &BB, MemorySSA &MSSA,
+                                              MemoryUse &MU);
 static Instruction *cloneInstructionInExitBlock(
     Instruction &I, BasicBlock &ExitBlock, PHINode &PN, const LoopInfo *LI,
     const LoopSafetyInfo *SafetyInfo, MemorySSAUpdater *MSSAU);
 
 static void eraseInstruction(Instruction &I, ICFLoopSafetyInfo &SafetyInfo,
                              AliasSetTracker *AST, MemorySSAUpdater *MSSAU);
 
 static void moveInstructionBefore(Instruction &I, Instruction &Dest,
if (isLoadInvariantInLoop(LI, DT, CurLoop))
       return true;
 
     bool Invalidated;
     if (CurAST)
       Invalidated = pointerInvalidatedByLoop(MemoryLocation::get(LI), CurAST,
                                              CurLoop, AA);
     else
       Invalidated = pointerInvalidatedByLoopWithMSSA(
-          MSSA, cast<MemoryUse>(MSSA->getMemoryAccess(LI)), CurLoop, *Flags);
+          MSSA, cast<MemoryUse>(MSSA->getMemoryAccess(LI)), CurLoop, I, *Flags);
     // Check loop-invariant address because this may also be a sinkable load
     // whose address is not necessarily loop-invariant.
     if (ORE && Invalidated && CurLoop->isLoopInvariant(LI->getPointerOperand()))
       ORE->emit([&]() {
         return OptimizationRemarkMissed(
                    DEBUG_TYPE, "LoadWithLoopInvariantAddressInvalidated", LI)
                << "failed to move load with loop-invariant address "
                   "because the loop may invalidate its value";
if (AAResults::onlyReadsMemory(Behavior)) {
           if (Op->getType()->isPointerTy()) {
             bool Invalidated;
             if (CurAST)
               Invalidated = pointerInvalidatedByLoop(
                   MemoryLocation(Op, LocationSize::unknown(), AAMDNodes()),
                   CurAST, CurLoop, AA);
             else
               Invalidated = pointerInvalidatedByLoopWithMSSA(
-                  MSSA, cast<MemoryUse>(MSSA->getMemoryAccess(CI)), CurLoop,
+                  MSSA, cast<MemoryUse>(MSSA->getMemoryAccess(CI)), CurLoop, I,
                   *Flags);
             if (Invalidated)
               return false;
           }
         return true;
       }
 
       // If this call only reads from memory and there are no writes to memory
if (CurAST) {
                 // to by SI. Check CI's attributes and arguments; the number of
                 // such checks performed is limited above by NoOfMemAccTooLarge.
                 ModRefInfo MRI = AA->getModRefInfo(CI, MemoryLocation::get(SI));
                 if (isModOrRefSet(MRI))
                   return false;
               }
             }
         }
-
       auto *Source = MSSA->getSkipSelfWalker()->getClobberingMemoryAccess(SI);
       Flags->incrementClobberingCalls();
       // If there are no clobbering Defs in the loop, store is safe to hoist.
       return MSSA->isLiveOnEntryDef(Source) ||
              !CurLoop->contains(Source->getBlock());
     }
   }
 
for (Instruction &I : *BB) {
         return true;
       }
     }
   LLVM_DEBUG(dbgs() << "Aliasing okay for " << *(MemLoc.Ptr) << "\n");
   return false;
 }
 
 bool pointerInvalidatedByLoopWithMSSA(MemorySSA *MSSA, MemoryUse *MU,
-                                      Loop *CurLoop,
+                                      Loop *CurLoop, Instruction &I,
                                       SinkAndHoistLICMFlags &Flags) {
   // For hoisting, use the walker to determine safety
   if (!Flags.getIsSink()) {
     MemoryAccess *Source;
     // See declaration of SetLicmMssaOptCap for usage details.
     if (Flags.tooManyClobberingCalls())
       Source = MU->getDefiningAccess();
     else {
bool pointerInvalidatedByLoopWithMSSA(MemorySSA *MSSA, MemoryUse *MU,
   // For now, only sink if there are no Defs in the loop, and the existing ones
   // precede the use and are in the same block.
   // FIXME: Increase precision: Safe to sink if Use post dominates the Def;
   // needs PostDominatorTreeAnalysis.
   // FIXME: More precise: no Defs that alias this Use.
   if (Flags.tooManyMemoryAccesses())
     return true;
   for (auto *BB : CurLoop->getBlocks())
-    if (auto *Accesses = MSSA->getBlockDefs(BB))
-      for (const auto &MA : *Accesses)
-        if (const auto *MD = dyn_cast<MemoryDef>(&MA))
-          if (MU->getBlock() != MD->getBlock() ||
-              !MSSA->locallyDominates(MD, MU))
-            return true;
+    if (pointerInvalidatedByBlockWithMSSA(*BB, *MSSA, *MU))
+      return true;
+  // When sinking, the source block may not be part of the loop so check it.
+  if (!CurLoop->contains(&I))
+    return pointerInvalidatedByBlockWithMSSA(*I.getParent(), *MSSA, *MU);
+
+  return false;
+}
+
+bool pointerInvalidatedByBlockWithMSSA(BasicBlock &BB, MemorySSA &MSSA,
+                                       MemoryUse &MU) {
+  if (const auto *Accesses = MSSA.getBlockDefs(&BB))
+        if (MU.getBlock() != MD->getBlock() || !MSSA.locallyDominates(MD, &MU))
   return false;
 }
 
 /// Little predicate that returns true if the specified basic block is in
 /// a subloop of the current one, not the current one itself.
 ///
 static bool inSubLoop(BasicBlock *BB, Loop *CurLoop, LoopInfo *LI) {
   assert(CurLoop->contains(BB) && "Only valid if BB is IN the loop");
   return LI->getLoopFor(BB) != CurLoop;
 }

llvm/lib/Transforms/Scalar/LoopSink.cpp

 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/AliasSetTracker.h"
 #include "llvm/Analysis/BasicAliasAnalysis.h"
 #include "llvm/Analysis/BlockFrequencyInfo.h"
 #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"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/Metadata.h"
 #include "llvm/InitializePasses.h"
 #include "llvm/Support/CommandLine.h"
static cl::opt<unsigned> SinkFrequencyPercentThreshold(
     "sink-freq-percent-threshold", cl::Hidden, cl::init(90),
     cl::desc("Do not sink instructions that require cloning unless they "
              "execute less than this percent of the time."));
 
 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
 ///   size increase. Thus there is no need to adjust the frequency.
 /// * If there are more than one BB, sinking would lead to code size increase.
 ///   In this case, we add some "tax" to the total frequency to make it harder
 ///   to sink. E.g.
 ///     Freq(Preheader) = 100
if (adjustedSumFreq(BBsToSinkInto, BFI) >
     BBsToSinkInto.clear();
   return BBsToSinkInto;
 }
 
 // Sinks \p I from the loop \p L's preheader to its uses. Returns true if
 // 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()) {
     Instruction *UI = cast<Instruction>(U.getUser());
     // We cannot sink I to PHI-uses.
     if (dyn_cast<PHINode>(UI))
       return false;
     // We cannot sink I if it has uses outside of the loop.
static bool sinkInstruction(
   for (BasicBlock *N : makeArrayRef(SortedBBsToSinkInto).drop_front(1)) {
     assert(LoopBlockNumber.find(N)->second >
                LoopBlockNumber.find(MoveBB)->second &&
            "BBs not sorted!");
     // Clone I and replace its uses.
     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;
     });
     // Replaces uses of I with IC in blocks dominated by N
     replaceDominatedUsesWith(&I, IC, DT, N);
     LLVM_DEBUG(dbgs() << "Sinking a clone of " << I << " To: " << N->getName()
                       << '\n');
     NumLoopSunkCloned++;
   }
   LLVM_DEBUG(dbgs() << "Sinking " << I << " To: " << MoveBB->getName() << '\n');
   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;
 }
 
 /// Sinks instructions from loop's preheader to the loop body if the
 /// sum frequency of inserted copy is smaller than preheader's frequency.
 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.
   if (!Preheader->getParent()->hasProfileData())
     return false;
 
   const BlockFrequency PreheaderFreq = BFI.getBlockFreq(Preheader);
   // If there are no basic blocks with lower frequency than the preheader then
   // we can avoid the detailed analysis as we will never find profitable sinking
   // opportunities.
   if (all_of(L.blocks(), [&](const BasicBlock *BB) {
         return BFI.getBlockFreq(BB) > PreheaderFreq;
       }))
     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;
   SmallDenseMap<BasicBlock *, int, 16> LoopBlockNumber;
   int i = 0;
   for (BasicBlock *B : L.blocks())
     if (BFI.getBlockFreq(B) < BFI.getBlockFreq(L.getLoopPreheader())) {
       ColdLoopBBs.push_back(B);
       LoopBlockNumber[B] = ++i;
     }
   llvm::stable_sort(ColdLoopBBs, [&](BasicBlock *A, BasicBlock *B) {
     return BFI.getBlockFreq(A) < BFI.getBlockFreq(B);
   });
 
   // Traverse preheader's instructions in reverse order becaue if A depends
   // on B (A appears after B), A needs to be sinked first before B can be
   // sinked.
   for (auto II = Preheader->rbegin(), E = Preheader->rend(); II != E;) {
     Instruction *I = &*II++;
     // 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;
   }
 
   if (Changed && SE)
     SE->forgetLoopDispositions(&L);
   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.
   if (LI.empty())
     return PreservedAnalyses::all();
 
   AAResults &AA = FAM.getResult<AAManager>(F);
   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
   // in reverse program order. This isn't expected to matter at all but is more
   // consistent with sinking algorithms which generally work bottom-up.
   SmallVector<Loop *, 4> PreorderLoops = LI.getLoopsInPreorder();
 
   bool Changed = false;
   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)
     return PreservedAnalyses::all();
 
+  if (MSSA && VerifyMemorySSA)
+    MSSA->verifyMemorySSA();
+
   PreservedAnalyses PA;
   PA.preserveSet<CFGAnalyses>();
   return PA;
 }
 
 namespace {
 struct LegacyLoopSinkPass : public LoopPass {
   static char ID;
   LegacyLoopSinkPass() : LoopPass(ID) {
     initializeLegacyLoopSinkPassPass(*PassRegistry::getPassRegistry());
   }
 
   bool runOnLoop(Loop *L, LPPassManager &LPM) override {
     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 (EnableMSSALoopDependency) {
+      AU.addRequired<MemorySSAWrapperPass>();
+      AU.addPreserved<MemorySSAWrapperPass>();
+    }
   }
 };
 }
 
 char LegacyLoopSinkPass::ID = 0;
 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(); }

llvm/test/CodeGen/AMDGPU/opt-pipeline.ll

 ; GCN-O1-NEXT:       Branch Probability Analysis
 ; GCN-O1-NEXT:       Block Frequency Analysis
 ; GCN-O1-NEXT:       Canonicalize natural loops
 ; GCN-O1-NEXT:       LCSSA Verifier
 ; GCN-O1-NEXT:       Loop-Closed SSA Form Pass
 ; GCN-O1-NEXT:       Basic Alias Analysis (stateless AA impl)
 ; GCN-O1-NEXT:       Function Alias Analysis Results
 ; GCN-O1-NEXT:       Scalar Evolution Analysis
+; GCN-O1-NEXT:       Memory SSA
 ; GCN-O1-NEXT:       Block Frequency Analysis
 ; GCN-O1-NEXT:       Loop Pass Manager
 ; GCN-O1-NEXT:         Loop Sink
 ; GCN-O1-NEXT:       Lazy Branch Probability Analysis
 ; GCN-O1-NEXT:       Lazy Block Frequency Analysis
 ; GCN-O1-NEXT:       Optimization Remark Emitter
 ; GCN-O1-NEXT:       Remove redundant instructions
 ; GCN-O1-NEXT:       Hoist/decompose integer division and remainder

 ; GCN-O2-NEXT:       Branch Probability Analysis
 ; GCN-O2-NEXT:       Block Frequency Analysis
 ; GCN-O2-NEXT:       Canonicalize natural loops
 ; GCN-O2-NEXT:       LCSSA Verifier
 ; GCN-O2-NEXT:       Loop-Closed SSA Form Pass
 ; GCN-O2-NEXT:       Basic Alias Analysis (stateless AA impl)
 ; GCN-O2-NEXT:       Function Alias Analysis Results
 ; GCN-O2-NEXT:       Scalar Evolution Analysis
+; GCN-O2-NEXT:       Memory SSA
 ; GCN-O2-NEXT:       Block Frequency Analysis
 ; GCN-O2-NEXT:       Loop Pass Manager
 ; GCN-O2-NEXT:         Loop Sink
 ; GCN-O2-NEXT:       Lazy Branch Probability Analysis
 ; GCN-O2-NEXT:       Lazy Block Frequency Analysis
 ; GCN-O2-NEXT:       Optimization Remark Emitter
 ; GCN-O2-NEXT:       Remove redundant instructions
 ; GCN-O2-NEXT:       Hoist/decompose integer division and remainder

 ; GCN-O3-NEXT:       Branch Probability Analysis
 ; GCN-O3-NEXT:       Block Frequency Analysis
 ; GCN-O3-NEXT:       Canonicalize natural loops
 ; GCN-O3-NEXT:       LCSSA Verifier
 ; GCN-O3-NEXT:       Loop-Closed SSA Form Pass
 ; GCN-O3-NEXT:       Basic Alias Analysis (stateless AA impl)
 ; GCN-O3-NEXT:       Function Alias Analysis Results
 ; GCN-O3-NEXT:       Scalar Evolution Analysis
+; GCN-O3-NEXT:       Memory SSA
 ; GCN-O3-NEXT:       Block Frequency Analysis
 ; GCN-O3-NEXT:       Loop Pass Manager
 ; GCN-O3-NEXT:         Loop Sink
 ; GCN-O3-NEXT:       Lazy Branch Probability Analysis
 ; GCN-O3-NEXT:       Lazy Block Frequency Analysis
 ; GCN-O3-NEXT:       Optimization Remark Emitter
 ; GCN-O3-NEXT:       Remove redundant instructions
 ; GCN-O3-NEXT:       Hoist/decompose integer division and remainder

llvm/test/Other/opt-O2-pipeline.ll

 ; CHECK-NEXT:       Branch Probability Analysis
 ; CHECK-NEXT:       Block Frequency Analysis
 ; CHECK-NEXT:       Canonicalize natural loops
 ; CHECK-NEXT:       LCSSA Verifier
 ; CHECK-NEXT:       Loop-Closed SSA Form Pass
 ; CHECK-NEXT:       Basic Alias Analysis (stateless AA impl)
 ; CHECK-NEXT:       Function Alias Analysis Results
 ; CHECK-NEXT:       Scalar Evolution Analysis
+; CHECK-NEXT:       Memory SSA
 ; CHECK-NEXT:       Block Frequency Analysis
 ; CHECK-NEXT:       Loop Pass Manager
 ; CHECK-NEXT:         Loop Sink
 ; CHECK-NEXT:       Lazy Branch Probability Analysis
 ; CHECK-NEXT:       Lazy Block Frequency Analysis
 ; CHECK-NEXT:       Optimization Remark Emitter
 ; CHECK-NEXT:       Remove redundant instructions
 ; CHECK-NEXT:       Hoist/decompose integer division and remainder

llvm/test/Other/opt-O3-pipeline-enable-matrix.ll

 ; CHECK-NEXT:       Branch Probability Analysis
 ; CHECK-NEXT:       Block Frequency Analysis
 ; CHECK-NEXT:       Canonicalize natural loops
 ; CHECK-NEXT:       LCSSA Verifier
 ; CHECK-NEXT:       Loop-Closed SSA Form Pass
 ; CHECK-NEXT:       Basic Alias Analysis (stateless AA impl)
 ; CHECK-NEXT:       Function Alias Analysis Results
 ; CHECK-NEXT:       Scalar Evolution Analysis
+; CHECK-NEXT:       Memory SSA
 ; CHECK-NEXT:       Block Frequency Analysis
 ; CHECK-NEXT:       Loop Pass Manager
 ; CHECK-NEXT:         Loop Sink
 ; CHECK-NEXT:       Lazy Branch Probability Analysis
 ; CHECK-NEXT:       Lazy Block Frequency Analysis
 ; CHECK-NEXT:       Optimization Remark Emitter
 ; CHECK-NEXT:       Remove redundant instructions
 ; CHECK-NEXT:       Hoist/decompose integer division and remainder

llvm/test/Other/opt-O3-pipeline.ll

 ; CHECK-NEXT:       Branch Probability Analysis
 ; CHECK-NEXT:       Block Frequency Analysis
 ; CHECK-NEXT:       Canonicalize natural loops
 ; CHECK-NEXT:       LCSSA Verifier
 ; CHECK-NEXT:       Loop-Closed SSA Form Pass
 ; CHECK-NEXT:       Basic Alias Analysis (stateless AA impl)
 ; CHECK-NEXT:       Function Alias Analysis Results
 ; CHECK-NEXT:       Scalar Evolution Analysis
+; CHECK-NEXT:       Memory SSA
 ; CHECK-NEXT:       Block Frequency Analysis
 ; CHECK-NEXT:       Loop Pass Manager
 ; CHECK-NEXT:         Loop Sink
 ; CHECK-NEXT:       Lazy Branch Probability Analysis
 ; CHECK-NEXT:       Lazy Block Frequency Analysis
 ; CHECK-NEXT:       Optimization Remark Emitter
 ; CHECK-NEXT:       Remove redundant instructions
 ; CHECK-NEXT:       Hoist/decompose integer division and remainder

llvm/test/Other/opt-Os-pipeline.ll

 ; CHECK-NEXT:       Branch Probability Analysis
 ; CHECK-NEXT:       Block Frequency Analysis
 ; CHECK-NEXT:       Canonicalize natural loops
 ; CHECK-NEXT:       LCSSA Verifier
 ; CHECK-NEXT:       Loop-Closed SSA Form Pass
 ; CHECK-NEXT:       Basic Alias Analysis (stateless AA impl)
 ; CHECK-NEXT:       Function Alias Analysis Results
 ; CHECK-NEXT:       Scalar Evolution Analysis
+; CHECK-NEXT:       Memory SSA
 ; CHECK-NEXT:       Block Frequency Analysis
 ; CHECK-NEXT:       Loop Pass Manager
 ; CHECK-NEXT:         Loop Sink
 ; CHECK-NEXT:       Lazy Branch Probability Analysis
 ; CHECK-NEXT:       Lazy Block Frequency Analysis
 ; CHECK-NEXT:       Optimization Remark Emitter
 ; CHECK-NEXT:       Remove redundant instructions
 ; CHECK-NEXT:       Hoist/decompose integer division and remainder

llvm/test/Transforms/LICM/loopsink-pr38462.ll

 ; RUN: opt -S -loop-sink < %s | FileCheck %s
+; RUN: opt -S -verify-memoryssa -enable-mssa-in-legacy-loop-sink -loop-sink < %s | FileCheck %s
+; RUN: opt -S -aa-pipeline=basic-aa -passes=loop-sink < %s | FileCheck %s
+; RUN: opt -S -verify-memoryssa -enable-mssa-in-loop-sink -aa-pipeline=basic-aa -passes=loop-sink < %s | FileCheck %s
 
 target datalayout = "e-m:w-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-pc-windows-msvc19.13.26128"
 
 %struct.FontInfoData = type { i32 (...)** }
 %struct.S = type { i8 }
 
 ; CHECK: @pr38462

llvm/test/Transforms/LICM/loopsink-pr39570.ll

 ; RUN: opt -S -loop-sink < %s | FileCheck %s
+; RUN: opt -S -verify-memoryssa -enable-mssa-in-legacy-loop-sink -loop-sink < %s | FileCheck %s
+; RUN: opt -S -aa-pipeline=basic-aa -passes=loop-sink < %s | FileCheck %s
+; RUN: opt -S -verify-memoryssa -enable-mssa-in-loop-sink -aa-pipeline=basic-aa -passes=loop-sink < %s | FileCheck %s
 
 ; CHECK: pr39570
 ; Make sure not to assert.
 
 %0 = type { i32, %1*, %2, %6*, %33* }
 %1 = type { i32 (...)** }
 %2 = type { %3* }
 %3 = type { %4, i32, %5* }

llvm/test/Transforms/LICM/loopsink-pr39695.ll

 ; RUN: opt -S -loop-sink < %s | FileCheck %s
+; RUN: opt -S -verify-memoryssa -enable-mssa-in-legacy-loop-sink -loop-sink < %s | FileCheck %s
+; RUN: opt -S -aa-pipeline=basic-aa -passes=loop-sink < %s | FileCheck %s
+; RUN: opt -S -verify-memoryssa -enable-mssa-in-loop-sink -aa-pipeline=basic-aa -passes=loop-sink < %s | FileCheck %s
 
 ; The load instruction should not be sunk into following loop.
 ; CHECK:      @foo
 ; CHECK-NEXT: entry
 ; CHECK-NEXT: %ptr = load i8*, i8** %pp, align 8
 ; CHECK-NEXT: store i8* null, i8** %pp, align 8
 
 define i32 @foo(i32 %n, i8** %pp) !prof !0 {

llvm/test/Transforms/LICM/loopsink.ll

 ; RUN: opt -S -loop-sink < %s | FileCheck %s
+; RUN: opt -S -verify-memoryssa -enable-mssa-in-legacy-loop-sink -loop-sink < %s | FileCheck %s
 ; RUN: opt -S -aa-pipeline=basic-aa -passes=loop-sink < %s | FileCheck %s
+; RUN: opt -S -verify-memoryssa -enable-mssa-in-loop-sink -aa-pipeline=basic-aa -passes=loop-sink < %s | FileCheck %s
 
 @g = global i32 0, align 4
 
 ;     b1
 ;    /  \
 ;   b2  b6
 ;  /  \  |
 ; b3  b4 |