[LICM] Precompute memory writers for AST aliasing analysis

[mkazantsev]

Summary

Current aliasing algorithm with AST traverses through all instructions in the loop
whenever it sees a load. However, the only instructions it really needs to check is
memory writing instructions. In this patch, we precompute a set of memory writers
and keep it up to date, avoiding redundant checks.

This patch is NFC for current default (zero) threshold and profitable when loop
has more than 1 load and total loop size is below limit. In current implementation,
it may cause redundant computations when loop exceeds the limit and this limit is
non-zero. Need to think how to tackle this.

This gives us up to 25% speedup on some extreme case in big loop with many loads
and few writing instructions.

[mkazantsev]

llvm/lib/Transforms/Scalar/LICM.cpp

2246

Currently, None here means either:

• it was called outside of LICM and no one really tried recompute writers;
• the writer computation has hit the limit.

We don't really need to do this in latter case. But I could not find any smart way to convey this info. Any design advice here is welcome.

[asbirlea]

One general comment: could this use case be added only when using AST (the creation of the set, updating it, etc)? It could even be included in the AST creation/update, or push inside the eraseInstruction calls if it's easier to have a common place to add it.
Otherwise this is adding unnecessary overhead when using MemorySSA, which is the current default.

The usecase for this improvement sounds very interesting. Could you provide more details about it and how using MemorySSA compares to the AST in this case?

llvm/lib/Transforms/Scalar/LICM.cpp

782

Would this also be useful inside sinkRegion(), or have it precomputed outside the calls?

[mkazantsev]

One general comment: could this use case be added only when using AST (the creation of the set, updating it, etc)?

Good catch, will do!

The usecase for this improvement sounds very interesting. Could you provide more details about it and how using MemorySSA compares to the AST in this case?

I'm planning to check; in the past there were some functional problems with MSSA in our environment but by now they could have been fixed. I'll post you up to date when I have the results!

[mkazantsev]

llvm/lib/Transforms/Scalar/LICM.cpp

782

Need to check, thanks for catching this.

[mkazantsev]

Regarding MSSA: in my setup (we use custom pipeline, LICM takes ~8% total time) this patch gives 1% total and mean compile time decrease on workload (approx. 12.5% of LICM time). Turning on MSSA for all loop passes causes ~6% total and mean compile time increase. MSSA doesn't give any performance gains on my test. However I am not sure how representative this workload is, we might have gains in some other case.

[mkazantsev]

Addressed comments.

[mkazantsev]

Ping?

[asbirlea]

Looks good overall, just a few nits inline.

llvm/lib/Transforms/Scalar/LICM.cpp

143

Optional<DenseSet<Instruction *> > clang-format adds that space between > >?
It's consistent throughout, so I guess so...it just looks odd to me :-).

313

Does it make sense to create the DenseSet here and pass it to the sinkRegion and hoistRegion below, instead of creating in each?

It may save some time to only create once if the set it properly updated after each of those calls, but then it's also expanding the signature of sinkRegion and hoistRegion.
An option may be to put the set inside a data structure, such as the SinkAndHoistLICMFlags?

811

NIt: no braces

1563

Nit: no braces.

1645

Nit: no new line needed.

1666

Nit: no braces.

[mkazantsev]

llvm/lib/Transforms/Scalar/LICM.cpp

143

Will double-check, but I guess it was clang-format.

313

I also was considering it and didn't do it because of impact on sink/hoistRegion API. I will take another look, maybe we can indeed encapsulate it somewhere.

[mkazantsev]

llvm/lib/Transforms/Scalar/LICM.cpp

811

Good catch, its a remnant of logging that was there. :)

[mkazantsev]

llvm/lib/Transforms/Scalar/LICM.cpp

143

Yes, it must be legacy since times where C++ parser was confusing <X <Y>> with shift. :)

llvm/include/llvm/Transforms/Utils/LoopUtils.h

 /// possible introduction of faults.  Reasoning about potential faulting
 /// instructions is the responsibility of the caller since it is challenging to
 /// do efficiently from within this routine.
 /// \p TargetExecutesOncePerLoop is true only when it is guaranteed that the
 /// target executes at most once per execution of the loop body.  This is used
 /// to assess the legality of duplicating atomic loads.  Generally, this is
 /// true when moving out of loop and not true when moving into loops.
 /// If \p ORE is set use it to emit optimization remarks.
-bool canSinkOrHoistInst(Instruction &I, AAResults *AA, DominatorTree *DT,
-                        Loop *CurLoop, AliasSetTracker *CurAST,
-                        MemorySSAUpdater *MSSAU, bool TargetExecutesOncePerLoop,
-                        SinkAndHoistLICMFlags *LICMFlags = nullptr,
-                        OptimizationRemarkEmitter *ORE = nullptr);
+bool canSinkOrHoistInst(
+    Instruction &I, AAResults *AA, DominatorTree *DT, Loop *CurLoop,
+    AliasSetTracker *CurAST, MemorySSAUpdater *MSSAU,
+    bool TargetExecutesOncePerLoop, SinkAndHoistLICMFlags *LICMFlags = nullptr,
+    OptimizationRemarkEmitter *ORE = nullptr,
+    const Optional<DenseSet<Instruction *> > &LoopMemWrites = None);
 
 /// Returns a Min/Max operation corresponding to MinMaxRecurrenceKind.
 Value *createMinMaxOp(IRBuilderBase &Builder,
                       RecurrenceDescriptor::MinMaxRecurrenceKind RK,
                       Value *Left, Value *Right);
 
 /// Generates an ordered vector reduction using extracts to reduce the value.
 Value *

llvm/lib/Transforms/Scalar/LICM.cpp

cl::desc("[LICM & MemorySSA] When MSSA in LICM is disabled, this has no "
              "enable memory promotion."));
 
 static bool inSubLoop(BasicBlock *BB, Loop *CurLoop, LoopInfo *LI);
 static bool isNotUsedOrFreeInLoop(const Instruction &I, const Loop *CurLoop,
                                   const LoopSafetyInfo *SafetyInfo,
                                   TargetTransformInfo *TTI, bool &FreeInLoop);
 static void hoist(Instruction &I, const DominatorTree *DT, const Loop *CurLoop,
                   BasicBlock *Dest, ICFLoopSafetyInfo *SafetyInfo,
+                  Optional<DenseSet<Instruction *> > LoopMemWrites,
                   MemorySSAUpdater *MSSAU, ScalarEvolution *SE,
                   OptimizationRemarkEmitter *ORE);
 static bool sink(Instruction &I, LoopInfo *LI, DominatorTree *DT,
                  const Loop *CurLoop, ICFLoopSafetyInfo *SafetyInfo,
+                 Optional<DenseSet<Instruction *> > LoopMemWrites,
                  MemorySSAUpdater *MSSAU, OptimizationRemarkEmitter *ORE);
 static bool isSafeToExecuteUnconditionally(Instruction &Inst,
                                            const DominatorTree *DT,
                                            const Loop *CurLoop,
                                            const LoopSafetyInfo *SafetyInfo,
                                            OptimizationRemarkEmitter *ORE,
                                            const Instruction *CtxI = nullptr);
-static bool pointerInvalidatedByLoop(MemoryLocation MemLoc,
-                                     AliasSetTracker *CurAST, Loop *CurLoop,
-                                     AliasAnalysis *AA);
+static Optional<DenseSet<Instruction *> > collectMemWrites(Loop *CurLoop);
+static bool pointerInvalidatedByLoop(
+    MemoryLocation MemLoc, AliasSetTracker *CurAST, Loop *CurLoop,
+    AliasAnalysis *AA, const Optional<DenseSet<Instruction *> > &LoopMemWrites);
 static bool pointerInvalidatedByLoopWithMSSA(MemorySSA *MSSA, MemoryUse *MU,
                                              Loop *CurLoop,
                                              SinkAndHoistLICMFlags &Flags);
 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);
+                             AliasSetTracker *AST,
+                             Optional<DenseSet<Instruction *> > LoopMemWrites,
+                             MemorySSAUpdater *MSSAU);
 
 static void moveInstructionBefore(Instruction &I, Instruction &Dest,
                                   ICFLoopSafetyInfo &SafetyInfo,
                                   MemorySSAUpdater *MSSAU, ScalarEvolution *SE);
 
 namespace {
 struct LoopInvariantCodeMotion {
   bool runOnLoop(Loop *L, AliasAnalysis *AA, LoopInfo *LI, DominatorTree *DT,
bool LoopInvariantCodeMotion::runOnLoop(
 
   std::unique_ptr<AliasSetTracker> CurAST;
   std::unique_ptr<MemorySSAUpdater> MSSAU;
   bool NoOfMemAccTooLarge = false;
   unsigned LicmMssaOptCounter = 0;
 
   if (!MSSA) {
     LLVM_DEBUG(dbgs() << "LICM: Using Alias Set Tracker.\n");
     CurAST = collectAliasInfoForLoop(L, LI, AA);
   } 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) {
bool llvm::sinkRegion(DomTreeNode *N, AliasAnalysis *AA, LoopInfo *LI,
   assert(((CurAST != nullptr) ^ (MSSAU != nullptr)) &&
          "Either AliasSetTracker or MemorySSA should be initialized.");
 
   // We want to visit children before parents. We will enque all the parents
   // before their children in the worklist and process the worklist in reverse
   // order.
   SmallVector<DomTreeNode *, 16> Worklist = collectChildrenInLoop(N, CurLoop);
 
+  // Collect memory-writing instructions. This is needed for AST mode only.
+  auto LoopMemWrites = CurAST ? collectMemWrites(CurLoop) : None;
+
   bool Changed = false;
   for (DomTreeNode *DTN : reverse(Worklist)) {
     BasicBlock *BB = DTN->getBlock();
     // Only need to process the contents of this block if it is not part of a
     // subloop (which would already have been processed).
     if (inSubLoop(BB, CurLoop, LI))
       continue;
 
     for (BasicBlock::iterator II = BB->end(); II != BB->begin();) {
       Instruction &I = *--II;
 
       // If the instruction is dead, we would try to sink it because it isn't
       // used in the loop, instead, just delete it.
       if (isInstructionTriviallyDead(&I, TLI)) {
         LLVM_DEBUG(dbgs() << "LICM deleting dead inst: " << I << '\n');
         salvageKnowledge(&I);
         salvageDebugInfo(I);
         ++II;
-        eraseInstruction(I, *SafetyInfo, CurAST, MSSAU);
+        eraseInstruction(I, *SafetyInfo, CurAST, LoopMemWrites, MSSAU);
         Changed = true;
         continue;
       }
 
       // Check to see if we can sink this instruction to the exit blocks
       // of the loop.  We can do this if the all users of the instruction are
       // outside of the loop.  In this case, it doesn't even matter if the
       // operands of the instruction are loop invariant.
       //
       bool FreeInLoop = false;
       if (!I.mayHaveSideEffects() &&
           isNotUsedOrFreeInLoop(I, CurLoop, SafetyInfo, TTI, FreeInLoop) &&
           canSinkOrHoistInst(I, AA, DT, CurLoop, CurAST, MSSAU, true, &Flags,
                              ORE)) {
-        if (sink(I, LI, DT, CurLoop, SafetyInfo, MSSAU, ORE)) {
+        if (sink(I, LI, DT, CurLoop, SafetyInfo, LoopMemWrites, MSSAU, ORE)) {
           if (!FreeInLoop) {
             ++II;
             salvageDebugInfoOrMarkUndef(I);
-            eraseInstruction(I, *SafetyInfo, CurAST, MSSAU);
+            eraseInstruction(I, *SafetyInfo, CurAST, LoopMemWrites, MSSAU);
           }
           Changed = true;
         }
       }
     }
   }
   if (MSSAU && VerifyMemorySSA)
     MSSAU->getMemorySSA()->verifyMemorySSA();
assert(((CurAST != nullptr) ^ (MSSAU != nullptr)) &&
          "Either AliasSetTracker or MemorySSA should be initialized.");
 
   ControlFlowHoister CFH(LI, DT, CurLoop, MSSAU);
 
   // Keep track of instructions that have been hoisted, as they may need to be
   // re-hoisted if they end up not dominating all of their uses.
   SmallVector<Instruction *, 16> HoistedInstructions;
 
+  // Collect memory-writing instructions. This is needed for AST mode only.
+  auto LoopMemWrites = CurAST ? collectMemWrites(CurLoop) : None;
+
   // For PHI hoisting to work we need to hoist blocks before their successors.
   // We can do this by iterating through the blocks in the loop in reverse
   // post-order.
   LoopBlocksRPO Worklist(CurLoop);
   Worklist.perform(LI);
   bool Changed = false;
   for (BasicBlock *BB : Worklist) {
     // Only need to process the contents of this block if it is not part of a
for (BasicBlock::iterator II = BB->begin(), E = BB->end(); II != E;) {
       if (Constant *C = ConstantFoldInstruction(
               &I, I.getModule()->getDataLayout(), TLI)) {
         LLVM_DEBUG(dbgs() << "LICM folding inst: " << I << "  --> " << *C
                           << '\n');
         if (CurAST)
           CurAST->copyValue(&I, C);
         // FIXME MSSA: Such replacements may make accesses unoptimized (D51960).
         I.replaceAllUsesWith(C);
-        if (isInstructionTriviallyDead(&I, TLI))
-          eraseInstruction(I, *SafetyInfo, CurAST, MSSAU);
+        if (isInstructionTriviallyDead(&I, TLI)) {
+          eraseInstruction(I, *SafetyInfo, CurAST, LoopMemWrites, MSSAU);
+        }
         Changed = true;
         continue;
       }
 
       // Try hoisting the instruction out to the preheader.  We can only do
       // this if all of the operands of the instruction are loop invariant and
       // if it is safe to hoist the instruction.
       // TODO: It may be safe to hoist if we are hoisting to a conditional block
       // and we have accurately duplicated the control flow from the loop header
       // to that block.
       if (CurLoop->hasLoopInvariantOperands(&I) &&
           canSinkOrHoistInst(I, AA, DT, CurLoop, CurAST, MSSAU, true, &Flags,
-                             ORE) &&
+                             ORE, LoopMemWrites) &&
           isSafeToExecuteUnconditionally(
               I, DT, CurLoop, SafetyInfo, ORE,
               CurLoop->getLoopPreheader()->getTerminator())) {
         hoist(I, DT, CurLoop, CFH.getOrCreateHoistedBlock(BB), SafetyInfo,
-              MSSAU, SE, ORE);
+              LoopMemWrites, MSSAU, SE, ORE);
         HoistedInstructions.push_back(&I);
         Changed = true;
         continue;
       }
 
       // Attempt to remove floating point division out of the loop by
       // converting it to a reciprocal multiplication.
       if (I.getOpcode() == Instruction::FDiv && I.hasAllowReciprocal() &&
           CurLoop->isLoopInvariant(I.getOperand(1))) {
         auto Divisor = I.getOperand(1);
         auto One = llvm::ConstantFP::get(Divisor->getType(), 1.0);
         auto ReciprocalDivisor = BinaryOperator::CreateFDiv(One, Divisor);
         ReciprocalDivisor->setFastMathFlags(I.getFastMathFlags());
         SafetyInfo->insertInstructionTo(ReciprocalDivisor, I.getParent());
         ReciprocalDivisor->insertBefore(&I);
 
         auto Product =
             BinaryOperator::CreateFMul(I.getOperand(0), ReciprocalDivisor);
         Product->setFastMathFlags(I.getFastMathFlags());
         SafetyInfo->insertInstructionTo(Product, I.getParent());
         Product->insertAfter(&I);
         I.replaceAllUsesWith(Product);
-        eraseInstruction(I, *SafetyInfo, CurAST, MSSAU);
-
+        eraseInstruction(I, *SafetyInfo, CurAST, LoopMemWrites, MSSAU);
         hoist(*ReciprocalDivisor, DT, CurLoop, CFH.getOrCreateHoistedBlock(BB),
-              SafetyInfo, MSSAU, SE, ORE);
+              SafetyInfo, LoopMemWrites, MSSAU, SE, ORE);
         HoistedInstructions.push_back(ReciprocalDivisor);
         Changed = true;
         continue;
       }
 
       auto IsInvariantStart = [&](Instruction &I) {
         using namespace PatternMatch;
         return I.use_empty() &&
                match(&I, m_Intrinsic<Intrinsic::invariant_start>());
       };
       auto MustExecuteWithoutWritesBefore = [&](Instruction &I) {
         return SafetyInfo->isGuaranteedToExecute(I, DT, CurLoop) &&
                SafetyInfo->doesNotWriteMemoryBefore(I, CurLoop);
       };
       if ((IsInvariantStart(I) || isGuard(&I)) &&
           CurLoop->hasLoopInvariantOperands(&I) &&
           MustExecuteWithoutWritesBefore(I)) {
         hoist(I, DT, CurLoop, CFH.getOrCreateHoistedBlock(BB), SafetyInfo,
-              MSSAU, SE, ORE);
+              LoopMemWrites, MSSAU, SE, ORE);
         HoistedInstructions.push_back(&I);
         Changed = true;
         continue;
       }
 
       if (PHINode *PN = dyn_cast<PHINode>(&I)) {
         if (CFH.canHoistPHI(PN)) {
           // Redirect incoming blocks first to ensure that we create hoisted
           // versions of those blocks before we hoist the phi.
           for (unsigned int i = 0; i < PN->getNumIncomingValues(); ++i)
             PN->setIncomingBlock(
                 i, CFH.getOrCreateHoistedBlock(PN->getIncomingBlock(i)));
           hoist(*PN, DT, CurLoop, CFH.getOrCreateHoistedBlock(BB), SafetyInfo,
-                MSSAU, SE, ORE);
+                LoopMemWrites, MSSAU, SE, ORE);
           assert(DT->dominates(PN, BB) && "Conditional PHIs not expected");
           Changed = true;
           continue;
         }
       }
 
       // Remember possibly hoistable branches so we can actually hoist them
       // later if needed.
if (auto *Accs = MSSAU->getMemorySSA()->getBlockAccesses(BB)) {
         if (MUD->getMemoryInst() != I || NotAPhi++ == 1)
           return false;
       }
     }
   return true;
 }
 }
 
-bool llvm::canSinkOrHoistInst(Instruction &I, AAResults *AA, DominatorTree *DT,
-                              Loop *CurLoop, AliasSetTracker *CurAST,
-                              MemorySSAUpdater *MSSAU,
-                              bool TargetExecutesOncePerLoop,
-                              SinkAndHoistLICMFlags *Flags,
-                              OptimizationRemarkEmitter *ORE) {
+bool llvm::canSinkOrHoistInst(
+    Instruction &I, AAResults *AA, DominatorTree *DT, Loop *CurLoop,
+    AliasSetTracker *CurAST, MemorySSAUpdater *MSSAU,
+    bool TargetExecutesOncePerLoop, SinkAndHoistLICMFlags *Flags,
+    OptimizationRemarkEmitter *ORE,
+    const Optional<DenseSet<Instruction *> > &LoopMemWrites) {
   // If we don't understand the instruction, bail early.
   if (!isHoistableAndSinkableInst(I))
     return false;
 
   MemorySSA *MSSA = MSSAU ? MSSAU->getMemorySSA() : nullptr;
   if (MSSA)
     assert(Flags != nullptr && "Flags cannot be null.");
 
if (LoadInst *LI = dyn_cast<LoadInst>(&I)) {
 
     // This checks for an invariant.start dominating the load.
     if (isLoadInvariantInLoop(LI, DT, CurLoop))
       return true;
 
     bool Invalidated;
     if (CurAST)
       Invalidated = pointerInvalidatedByLoop(MemoryLocation::get(LI), CurAST,
-                                             CurLoop, AA);
+                                             CurLoop, AA, LoopMemWrites);
     else
       Invalidated = pointerInvalidatedByLoopWithMSSA(
           MSSA, cast<MemoryUse>(MSSA->getMemoryAccess(LI)), CurLoop, *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(
if (AliasAnalysis::onlyReadsMemory(Behavior)) {
       if (AliasAnalysis::onlyAccessesArgPointees(Behavior)) {
         // TODO: expand to writeable arguments
         for (Value *Op : CI->arg_operands())
           if (Op->getType()->isPointerTy()) {
             bool Invalidated;
             if (CurAST)
               Invalidated = pointerInvalidatedByLoop(
                   MemoryLocation(Op, LocationSize::unknown(), AAMDNodes()),
-                  CurAST, CurLoop, AA);
+                  CurAST, CurLoop, AA, LoopMemWrites);
             else
               Invalidated = pointerInvalidatedByLoopWithMSSA(
                   MSSA, cast<MemoryUse>(MSSA->getMemoryAccess(CI)), CurLoop,
                   *Flags);
             if (Invalidated)
               return false;
           }
         return true;
if (Instruction *OInst = dyn_cast<Instruction>(*OI))
           for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i)
             OpPN->addIncoming(OInst, PN.getIncomingBlock(i));
           *OI = OpPN;
         }
   return New;
 }
 
 static void eraseInstruction(Instruction &I, ICFLoopSafetyInfo &SafetyInfo,
-                             AliasSetTracker *AST, MemorySSAUpdater *MSSAU) {
-  if (AST)
+                             AliasSetTracker *AST,
+                             Optional<DenseSet<Instruction *> > LoopMemWrites,
+                             MemorySSAUpdater *MSSAU) {
+  if (AST) {
+    if (LoopMemWrites && I.mayWriteToMemory())
+      LoopMemWrites->erase(&I);
     AST->deleteValue(&I);
+  }
   if (MSSAU)
     MSSAU->removeMemoryAccess(&I);
   SafetyInfo.removeInstruction(&I);
   I.eraseFromParent();
 }
 
 static void moveInstructionBefore(Instruction &I, Instruction &Dest,
                                   ICFLoopSafetyInfo &SafetyInfo,

 
 /// When an instruction is found to only be used outside of the loop, this
 /// function moves it to the exit blocks and patches up SSA form as needed.
 /// This method is guaranteed to remove the original instruction from its
 /// position, and may either delete it or move it to outside of the loop.
 ///
 static bool sink(Instruction &I, LoopInfo *LI, DominatorTree *DT,
                  const Loop *CurLoop, ICFLoopSafetyInfo *SafetyInfo,
+                 Optional<DenseSet<Instruction *> > LoopMemWrites,
                  MemorySSAUpdater *MSSAU, OptimizationRemarkEmitter *ORE) {
   LLVM_DEBUG(dbgs() << "LICM sinking instruction: " << I << "\n");
   ORE->emit([&]() {
     return OptimizationRemark(DEBUG_TYPE, "InstSunk", &I)
            << "sinking " << ore::NV("Inst", &I);
   });
   bool Changed = false;
   if (isa<LoadInst>(I))
     ++NumMovedLoads;
   else if (isa<CallInst>(I))
     ++NumMovedCalls;
   ++NumSunk;
 
+  if (LoopMemWrites && I.mayWriteToMemory()) {
+    LoopMemWrites->erase(&I);
+  }
+
   // Iterate over users to be ready for actual sinking. Replace users via
   // unreachable blocks with undef and make all user PHIs trivially replaceable.
   SmallPtrSet<Instruction *, 8> VisitedUsers;
   for (Value::user_iterator UI = I.user_begin(), UE = I.user_end(); UI != UE;) {
     auto *User = cast<Instruction>(*UI);
     Use &U = UI.getUse();
     ++UI;
 
for (auto *UI : Users) {
 
     PHINode *PN = cast<PHINode>(User);
     assert(ExitBlockSet.count(PN->getParent()) &&
            "The LCSSA PHI is not in an exit block!");
     // The PHI must be trivially replaceable.
     Instruction *New = sinkThroughTriviallyReplaceablePHI(
         PN, &I, LI, SunkCopies, SafetyInfo, CurLoop, MSSAU);
     PN->replaceAllUsesWith(New);
-    eraseInstruction(*PN, *SafetyInfo, nullptr, nullptr);
+    eraseInstruction(*PN, *SafetyInfo, nullptr, None, nullptr);
     Changed = true;
   }
+
   return Changed;
 }
 
 /// When an instruction is found to only use loop invariant operands that
 /// is safe to hoist, this instruction is called to do the dirty work.
 ///
 static void hoist(Instruction &I, const DominatorTree *DT, const Loop *CurLoop,
                   BasicBlock *Dest, ICFLoopSafetyInfo *SafetyInfo,
+                  Optional<DenseSet<Instruction *> > LoopMemWrites,
                   MemorySSAUpdater *MSSAU, ScalarEvolution *SE,
                   OptimizationRemarkEmitter *ORE) {
   LLVM_DEBUG(dbgs() << "LICM hoisting to " << Dest->getName() << ": " << I
                     << "\n");
   ORE->emit([&]() {
     return OptimizationRemark(DEBUG_TYPE, "Hoisted", &I) << "hoisting "
                                                          << ore::NV("Inst", &I);
   });
 
+  if (LoopMemWrites && I.mayWriteToMemory()) {
+    LoopMemWrites->erase(&I);
+  }
+
   // Metadata can be dependent on conditions we are hoisting above.
   // Conservatively strip all metadata on the instruction unless we were
   // guaranteed to execute I if we entered the loop, in which case the metadata
   // is valid in the loop preheader.
   if (I.hasMetadataOtherThanDebugLoc() &&
       // The check on hasMetadataOtherThanDebugLoc is to prevent us from burning
       // time in isGuaranteedToExecute if we don't actually have anything to
       // drop.  It is a compile time optimization, not required for correctness.
bool llvm::promoteLoopAccessesToScalars(
   // Rewrite all the loads in the loop and remember all the definitions from
   // stores in the loop.
   Promoter.run(LoopUses);
 
   if (MSSAU && VerifyMemorySSA)
     MSSAU->getMemorySSA()->verifyMemorySSA();
   // If the SSAUpdater didn't use the load in the preheader, just zap it now.
   if (PreheaderLoad->use_empty())
-    eraseInstruction(*PreheaderLoad, *SafetyInfo, CurAST, MSSAU);
+    eraseInstruction(*PreheaderLoad, *SafetyInfo, CurAST, None, MSSAU);
 
   return true;
 }
 
 /// Returns an owning pointer to an alias set which incorporates aliasing info
 /// from L and all subloops of L.
 std::unique_ptr<AliasSetTracker>
 LoopInvariantCodeMotion::collectAliasInfoForLoop(Loop *L, LoopInfo *LI,

 LoopInvariantCodeMotion::collectAliasInfoForLoopWithMSSA(
     Loop *L, AliasAnalysis *AA, MemorySSAUpdater *MSSAU) {
   auto *MSSA = MSSAU->getMemorySSA();
   auto CurAST = std::make_unique<AliasSetTracker>(*AA, MSSA, L);
   CurAST->addAllInstructionsInLoopUsingMSSA();
   return CurAST;
 }
 
-static bool pointerInvalidatedByLoop(MemoryLocation MemLoc,
-                                     AliasSetTracker *CurAST, Loop *CurLoop,
-                                     AliasAnalysis *AA) {
+static Optional<DenseSet<Instruction *> > collectMemWrites(Loop *CurLoop) {
+  DenseSet<Instruction *> Dest;
+  int N = 0;
+  for (BasicBlock *BB : CurLoop->blocks())
+    for (Instruction &I : *BB) {
+      if (N++ >= LICMN2Theshold) {
+        LLVM_DEBUG(dbgs() << "Alasing N2 threshold exhausted\n");
+        return None;
+      }
+      if (I.mayWriteToMemory())
+        Dest.insert(&I);
+    }
+  return Dest;
+}
+
+static bool pointerInvalidatedByLoop(
+    MemoryLocation MemLoc, AliasSetTracker *CurAST, Loop *CurLoop,
+    AliasAnalysis *AA,
+    const Optional<DenseSet<Instruction *> > &LoopMemWrites) {
   // First check to see if any of the basic blocks in CurLoop invalidate *V.
   bool isInvalidatedAccordingToAST = CurAST->getAliasSetFor(MemLoc).isMod();
 
   if (!isInvalidatedAccordingToAST || !LICMN2Theshold)
     return isInvalidatedAccordingToAST;
 
   // Check with a diagnostic analysis if we can refine the information above.
   // This is to identify the limitations of using the AST.
   // The alias set mechanism used by LICM has a major weakness in that it
   // combines all things which may alias into a single set *before* asking
   // modref questions. As a result, a single readonly call within a loop will
   // collapse all loads and stores into a single alias set and report
   // invalidation if the loop contains any store. For example, readonly calls
   // with deopt states have this form and create a general alias set with all
   // loads and stores.  In order to get any LICM in loops containing possible
   // deopt states we need a more precise invalidation of checking the mod ref
   // info of each instruction within the loop and LI. This has a complexity of
   // O(N^2), so currently, it is used only as a diagnostic tool since the
   // default value of LICMN2Threshold is zero.
 
   // Don't look at nested loops.
   if (CurLoop->begin() != CurLoop->end())
     return true;
 
-  int N = 0;
-  for (BasicBlock *BB : CurLoop->getBlocks())
-    for (Instruction &I : *BB) {
-      if (N >= LICMN2Theshold) {
-        LLVM_DEBUG(dbgs() << "Alasing N2 threshold exhausted for "
-                          << *(MemLoc.Ptr) << "\n");
-        return true;
-      }
-      N++;
-      auto Res = AA->getModRefInfo(&I, MemLoc);
-      if (isModSet(Res)) {
-        LLVM_DEBUG(dbgs() << "Aliasing failed on " << I << " for "
-                          << *(MemLoc.Ptr) << "\n");
-        return true;
-      }
-    }
+  Optional<DenseSet<Instruction *> > WritesToProcess = LoopMemWrites;
+
+  // If nothing was passed, compute it anew.
+  if (!WritesToProcess)
+    WritesToProcess = collectMemWrites(CurLoop);
+
+  // Too many writes to process.
+  if (!WritesToProcess)
+
+#ifndef NDEBUG
+  auto ControlGroup = collectMemWrites(CurLoop);
+  assert(ControlGroup && "Failed to collect properly!");
+
+  assert(ControlGroup->size() == WritesToProcess->size() && "Sizes mismatch!");
+  for (Instruction *I : *ControlGroup)
+    assert(WritesToProcess->count(I) &&
+           "Data about memory-writing instructions is wrong!");
+#endif
+
+  for (Instruction *I : *WritesToProcess) {
+    auto Res = AA->getModRefInfo(I, MemLoc);
+      LLVM_DEBUG(dbgs() << "Aliasing failed on " << *I << " for "
+
   LLVM_DEBUG(dbgs() << "Aliasing okay for " << *(MemLoc.Ptr) << "\n");
   return false;
 }
 
 static bool pointerInvalidatedByLoopWithMSSA(MemorySSA *MSSA, MemoryUse *MU,
                                              Loop *CurLoop,
                                              SinkAndHoistLICMFlags &Flags) {
   // For hoisting, use the walker to determine safety
   if (!Flags.IsSink) {
     MemoryAccess *Source;

llvm/test/Transforms/LICM/hoisting.ll

loop:
   %sum.next = add i32 %sel, %sum
   %indvar.next = add i32 %indvar, 1
   %cond = icmp slt i32 %indvar.next, %n
   br i1 %cond, label %loop, label %loopexit
 
 loopexit:
   ret i32 %sum
 }
+
+define i32 @test_store_load(i32* noalias %a, i32* noalias %b, i32* noalias %c, i32* noalias %d) {
+entry:
+  br label %loop
+
+loop:
+  %indvar = phi i32 [ %indvar.next, %loop ], [ 0, %entry ]
+  %x = load i32, i32* %a
+  store i32 123, i32* %b
+  %y = load i32, i32* %c
+  store i32 456, i32* %d
+  %sum = add i32 %x, %y
+  %indvar.next = add i32 %indvar, 1
+  %cond = icmp slt i32 %indvar.next, 1000
+  br i1 %cond, label %loop, label %exit
+
+exit:
+  ret i32 %sum
+}