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

363

/*CurAST=*/nullptr

397

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

373

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

413

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

250

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/include/llvm/Transforms/Utils/LoopUtils.h

 /// LoopInfo and DominatorTree are required and preserved.
 ///
 /// If ScalarEvolution is passed in, it will be preserved.
 ///
 /// Returns true if any modifications are made to the loop.
 bool formLCSSARecursively(Loop &L, const DominatorTree &DT, const LoopInfo *LI,
                           ScalarEvolution *SE);
 
-struct SinkAndHoistLICMFlags {
-  bool NoOfMemAccTooLarge;
-  unsigned LicmMssaOptCounter;
+/// Flags controlling how much is checked when sinking or hoisting
+/// instructions.  The number of memory access in the loop (and whether there
+/// are too many) is determined in the constructors when using MemorySSA.
+class SinkAndHoistLICMFlags {
+public:
+  // Explicitly set limits.
+  SinkAndHoistLICMFlags(unsigned LicmMssaOptCap,
+                        unsigned LicmMssaNoAccForPromotionCap, bool IsSink,
+                        Loop *L = nullptr, MemorySSA *MSSA = nullptr);
+  // Use default limits.
+  SinkAndHoistLICMFlags(bool IsSink, Loop *L = nullptr,
+                        MemorySSA *MSSA = nullptr);
+
+  void setIsSink(bool B) { IsSink = B; }
+  bool getIsSink() { return IsSink; }
+  bool tooManyMemoryAccesses() { return NoOfMemAccTooLarge; }
+  bool tooManyClobberingCalls() { return LicmMssaOptCounter >= LicmMssaOptCap; }
+  void incrementClobberingCalls() { ++LicmMssaOptCounter; }
+
+protected:
+  bool NoOfMemAccTooLarge = false;
+  unsigned LicmMssaOptCounter = 0;
   unsigned LicmMssaOptCap;
   unsigned LicmMssaNoAccForPromotionCap;
   bool IsSink;
 };
 
 /// Walk the specified region of the CFG (defined by all blocks
 /// dominated by the specified block, and that are in the current loop) in
 /// reverse depth first order w.r.t the DominatorTree. This allows us to visit

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,
INITIALIZE_PASS_END(LegacyLICMPass, "licm", "Loop Invariant Code Motion", false,
                     false)
 
 Pass *llvm::createLICMPass() { return new LegacyLICMPass(); }
 Pass *llvm::createLICMPass(unsigned LicmMssaOptCap,
                            unsigned LicmMssaNoAccForPromotionCap) {
   return new LegacyLICMPass(LicmMssaOptCap, LicmMssaNoAccForPromotionCap);
 }
 
+llvm::SinkAndHoistLICMFlags::SinkAndHoistLICMFlags(bool IsSink, Loop *L,
+                                                   MemorySSA *MSSA)
+    : SinkAndHoistLICMFlags(SetLicmMssaOptCap, SetLicmMssaNoAccForPromotionCap,
+                            IsSink, L, MSSA) {}
+
+llvm::SinkAndHoistLICMFlags::SinkAndHoistLICMFlags(
+    unsigned LicmMssaOptCap, unsigned LicmMssaNoAccForPromotionCap,
+    bool IsSink, Loop *L, MemorySSA *MSSA)
+    : LicmMssaOptCap(LicmMssaOptCap),
+      LicmMssaNoAccForPromotionCap(LicmMssaNoAccForPromotionCap),
+      IsSink(IsSink) {
+  assert(((L != nullptr) == (MSSA != nullptr)) &&
+         "Unexpected values for SinkAndHoistLICMFlags");
+  if (!MSSA)
+    return;
+
+  unsigned AccessCapCount = 0;
+  for (auto *BB : L->getBlocks())
+    if (auto *Accesses = MSSA->getBlockAccesses(BB))
+      for (const auto &MA : *Accesses) {
+        (void)MA;
+        ++AccessCapCount;
+        if (AccessCapCount > LicmMssaNoAccForPromotionCap) {
+          NoOfMemAccTooLarge = true;
+          return;
+        }
+      }
+}
+
+
 /// Hoist expressions out of the specified loop. Note, alias info for inner
 /// loop is not preserved so it is not a good idea to run LICM multiple
 /// times on one loop.
 bool LoopInvariantCodeMotion::runOnLoop(
     Loop *L, AAResults *AA, LoopInfo *LI, DominatorTree *DT,
     BlockFrequencyInfo *BFI, TargetLibraryInfo *TLI, TargetTransformInfo *TTI,
     ScalarEvolution *SE, MemorySSA *MSSA, OptimizationRemarkEmitter *ORE) {
   bool Changed = false;
 
   assert(L->isLCSSAForm(*DT) && "Loop is not in LCSSA form.");
 
   // If this loop has metadata indicating that LICM is not to be performed then
   // just exit.
   if (hasDisableLICMTransformsHint(L)) {
     return false;
   }
 
   std::unique_ptr<AliasSetTracker> CurAST;
   std::unique_ptr<MemorySSAUpdater> MSSAU;
-  bool NoOfMemAccTooLarge = false;
-  unsigned LicmMssaOptCounter = 0;
+  std::unique_ptr<SinkAndHoistLICMFlags> Flags;
 
   if (!MSSA) {
     LLVM_DEBUG(dbgs() << "LICM: Using Alias Set Tracker.\n");
     CurAST = collectAliasInfoForLoop(L, LI, AA);
+    Flags = std::make_unique<SinkAndHoistLICMFlags>(
+        LicmMssaOptCap, LicmMssaNoAccForPromotionCap, /*IsSink=*/true);
   } else {
     LLVM_DEBUG(dbgs() << "LICM: Using MemorySSA.\n");
     MSSAU = std::make_unique<MemorySSAUpdater>(MSSA);
-
-    unsigned AccessCapCount = 0;
-    for (auto *BB : L->getBlocks()) {
-      if (auto *Accesses = MSSA->getBlockAccesses(BB)) {
-        for (const auto &MA : *Accesses) {
-          (void)MA;
-          AccessCapCount++;
-          if (AccessCapCount > LicmMssaNoAccForPromotionCap) {
-            NoOfMemAccTooLarge = true;
-            break;
-          }
-        }
-      }
-      if (NoOfMemAccTooLarge)
-        break;
-    }
+    Flags = std::make_unique<SinkAndHoistLICMFlags>(
+        LicmMssaOptCap, LicmMssaNoAccForPromotionCap, /*IsSink=*/true, L, MSSA);
   }
 
   // Get the preheader block to move instructions into...
   BasicBlock *Preheader = L->getLoopPreheader();
 
   // Compute loop safety information.
   ICFLoopSafetyInfo SafetyInfo;
   SafetyInfo.computeLoopSafetyInfo(L);
 
   // We want to visit all of the instructions in this loop... that are not parts
   // of our subloops (they have already had their invariants hoisted out of
   // their loop, into this loop, so there is no need to process the BODIES of
   // the subloops).
   //
   // Traverse the body of the loop in depth first order on the dominator tree so
   // that we are guaranteed to see definitions before we see uses.  This allows
   // us to sink instructions in one pass, without iteration.  After sinking
   // instructions, we perform another pass to hoist them out of the loop.
-  SinkAndHoistLICMFlags Flags = {NoOfMemAccTooLarge, LicmMssaOptCounter,
-                                 LicmMssaOptCap, LicmMssaNoAccForPromotionCap,
-                                 /*IsSink=*/true};
   if (L->hasDedicatedExits())
     Changed |=
         sinkRegion(DT->getNode(L->getHeader()), AA, LI, DT, BFI, TLI, TTI, L,
-                   CurAST.get(), MSSAU.get(), &SafetyInfo, Flags, ORE);
-  Flags.IsSink = false;
+                   CurAST.get(), MSSAU.get(), &SafetyInfo, *Flags.get(), ORE);
+  Flags->setIsSink(false);
   if (Preheader)
     Changed |=
         hoistRegion(DT->getNode(L->getHeader()), AA, LI, DT, BFI, TLI, L,
-                    CurAST.get(), MSSAU.get(), SE, &SafetyInfo, Flags, ORE);
+                    CurAST.get(), MSSAU.get(), SE, &SafetyInfo, *Flags.get(),
+                    ORE);
 
   // Now that all loop invariants have been removed from the loop, promote any
   // memory references to scalars that we can.
   // Don't sink stores from loops without dedicated block exits. Exits
   // containing indirect branches are not transformed by loop simplify,
   // make sure we catch that. An additional load may be generated in the
   // preheader for SSA updater, so also avoid sinking when no preheader
   // is available.
   if (!DisablePromotion && Preheader && L->hasDedicatedExits() &&
-      !NoOfMemAccTooLarge) {
+      !Flags->tooManyMemoryAccesses()) {
     // Figure out the loop exits and their insertion points
     SmallVector<BasicBlock *, 8> ExitBlocks;
     L->getUniqueExitBlocks(ExitBlocks);
 
     // We can't insert into a catchswitch.
     bool HasCatchSwitch = llvm::any_of(ExitBlocks, [](BasicBlock *Exit) {
       return isa<CatchSwitchInst>(Exit->getTerminator());
     });
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) {
       if (!UniqueI)
         // other memory op, give up
         return false;
       assert(UniqueI == SI && "AS must contain SI");
       return true;
     } else { // MSSAU
       if (isOnlyMemoryAccess(SI, CurLoop, MSSAU))
         return true;
-      // If there are more accesses than the Promotion cap, give up, we're not
-      // walking a list that long.
-      if (Flags->NoOfMemAccTooLarge)
-        return false;
-      // Check store only if there's still "quota" to check clobber.
-      if (Flags->LicmMssaOptCounter >= Flags->LicmMssaOptCap)
+      // If there are more accesses than the Promotion cap or no "quota" to
+      // check clobber, then give up as we're not walking a list that long.
+      if (Flags->tooManyMemoryAccesses() || Flags->tooManyClobberingCalls())
         return false;
       // If there are interfering Uses (i.e. their defining access is in the
       // loop), or ordered loads (stored as Defs!), don't move this store.
       // Could do better here, but this is conservatively correct.
       // TODO: Cache set of Uses on the first walk in runOnLoop, update when
       // moving accesses. Can also extend to dominating uses.
       auto *SIMD = MSSA->getMemoryAccess(SI);
       for (auto *BB : CurLoop->getBlocks())
         if (auto *Accesses = MSSA->getBlockAccesses(BB)) {
           for (const auto &MA : *Accesses)
             if (const auto *MU = dyn_cast<MemoryUse>(&MA)) {
               auto *MD = MU->getDefiningAccess();
               if (!MSSA->isLiveOnEntryDef(MD) &&
                   CurLoop->contains(MD->getBlock()))
                 return false;
               // Disable hoisting past potentially interfering loads. Optimized
               // Uses may point to an access outside the loop, as getClobbering
               // checks the previous iteration when walking the backedge.
               // FIXME: More precise: no Uses that alias SI.
-              if (!Flags->IsSink && !MSSA->dominates(SIMD, MU))
+              if (!Flags->getIsSink() && !MSSA->dominates(SIMD, MU))
                 return false;
             } else if (const auto *MD = dyn_cast<MemoryDef>(&MA)) {
               if (auto *LI = dyn_cast<LoadInst>(MD->getMemoryInst())) {
                 (void)LI; // Silence warning.
                 assert(!LI->isUnordered() && "Expected unordered load");
                 return false;
               }
               // Any call, while it may not be clobbering SI, it may be a use.
               if (auto *CI = dyn_cast<CallInst>(MD->getMemoryInst())) {
                 // Check if the call may read from the memory locattion written
                 // 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->LicmMssaOptCounter++;
+      Flags->incrementClobberingCalls();
       // If there are no clobbering Defs in the loop, store is safe to hoist.
       return MSSA->isLiveOnEntryDef(Source) ||
              !CurLoop->contains(Source->getBlock());
     }
   }
 
   assert(!I.mayReadOrWriteMemory() && "unhandled aliasing");
 
for (Instruction &I : *BB) {
                           << *(MemLoc.Ptr) << "\n");
         return true;
       }
     }
   LLVM_DEBUG(dbgs() << "Aliasing okay for " << *(MemLoc.Ptr) << "\n");
   return false;
 }
 
-static bool pointerInvalidatedByLoopWithMSSA(MemorySSA *MSSA, MemoryUse *MU,
-                                             Loop *CurLoop,
-                                             SinkAndHoistLICMFlags &Flags) {
+bool pointerInvalidatedByLoopWithMSSA(MemorySSA *MSSA, MemoryUse *MU,
+                                      Loop *CurLoop, Instruction &I,
   // For hoisting, use the walker to determine safety
-  if (!Flags.IsSink) {
+  if (!Flags.getIsSink()) {
     MemoryAccess *Source;
     // See declaration of SetLicmMssaOptCap for usage details.
-    if (Flags.LicmMssaOptCounter >= Flags.LicmMssaOptCap)
+    if (Flags.tooManyClobberingCalls())
       Source = MU->getDefiningAccess();
     else {
       Source = MSSA->getSkipSelfWalker()->getClobberingMemoryAccess(MU);
-      Flags.LicmMssaOptCounter++;
+      Flags.incrementClobberingCalls();
     }
     return !MSSA->isLiveOnEntryDef(Source) &&
            CurLoop->contains(Source->getBlock());
   }
 
   // For sinking, we'd need to check all Defs below this use. The getClobbering
   // call will look on the backedge of the loop, but will check aliasing with
   // the instructions on the previous iteration.
   // For example:
   // for (i ... )
   //   load a[i] ( Use (LoE)
   //   store a[i] ( 1 = Def (2), with 2 = Phi for the loop.
   //   i++;
   // The load sees no clobbering inside the loop, as the backedge alias check
   // does phi translation, and will check aliasing against store a[i-1].
   // However sinking the load outside the loop, below the store is incorrect.
 
   // 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.NoOfMemAccTooLarge)
+  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 (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"
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) {
+static bool sinkLoopInvariantInstructions(
+    Loop &L, AAResults &AA, LoopInfo &LI, DominatorTree &DT,
+    BlockFrequencyInfo &BFI, ScalarEvolution *SE, AliasSetTracker *CurAST,
+    MemorySSAUpdater *MSSAU, SinkAndHoistLICMFlags *LICMFlags) {
   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);
-
-  // Compute alias set.
-  for (BasicBlock *BB : L.blocks())
-    CurAST.add(*BB);
-  CurAST.add(*Preheader);
 
   // 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, false, LICMFlags))
       continue;
-    if (sinkInstruction(L, *I, ColdLoopBBs, LoopBlockNumber, LI, DT, BFI))
+    if (sinkInstruction(L, *I, ColdLoopBBs, LoopBlockNumber, LI, DT, BFI,
+                        MSSAU))
       Changed = true;
   }
 
   if (Changed && SE)
     SE->forgetLoopDispositions(&L);
   return Changed;
 }
 
 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 = FAM.getResult<MemorySSAAnalysis>(F).getMSSA();
+  MemorySSAUpdater MSSAU(&MSSA);
 
   // 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;
+
+    SinkAndHoistLICMFlags LICMFlags(/*IsSink=*/true, &L, &MSSA);
     // 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,
+                                             nullptr, &MSSAU, &LICMFlags);
   } while (!PreorderLoops.empty());
 
   if (!Changed)
     return PreservedAnalyses::all();
 
+  if (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;
+
     auto *SE = getAnalysisIfAvailable<ScalarEvolutionWrapperPass>();
+
+    AAResults &AA = getAnalysis<AAResultsWrapperPass>().getAAResults();
+    AliasSetTracker CurAST(AA);
+
+    // Compute alias set.
+    for (BasicBlock *BB : L->blocks())
+      CurAST.add(*BB);
+    CurAST.add(*Preheader);
+
     return sinkLoopInvariantInstructions(
-        *L, getAnalysis<AAResultsWrapperPass>().getAAResults(),
-        getAnalysis<LoopInfoWrapperPass>().getLoopInfo(),
+        *L, AA, getAnalysis<LoopInfoWrapperPass>().getLoopInfo(),
         getAnalysis<DominatorTreeWrapperPass>().getDomTree(),
         getAnalysis<BlockFrequencyInfoWrapperPass>().getBFI(),
-        SE ? &SE->getSE() : nullptr);
+        SE ? &SE->getSE() : nullptr, &CurAST, nullptr, nullptr);
   }
 
   void getAnalysisUsage(AnalysisUsage &AU) const override {
     AU.setPreservesCFG();
     AU.addRequired<BlockFrequencyInfoWrapperPass>();
     getLoopAnalysisUsage(AU);
   }
 };
 }
 
 char LegacyLoopSinkPass::ID = 0;
 INITIALIZE_PASS_BEGIN(LegacyLoopSinkPass, "loop-sink", "Loop Sink", false,
                       false)
 INITIALIZE_PASS_DEPENDENCY(LoopPass)
 INITIALIZE_PASS_DEPENDENCY(BlockFrequencyInfoWrapperPass)
 INITIALIZE_PASS_END(LegacyLoopSinkPass, "loop-sink", "Loop Sink", false, false)
 
 Pass *llvm::createLoopSinkPass() { return new LegacyLoopSinkPass(); }

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

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