[LICM] Use ICFLoopSafetyInfo in LICM

[mkazantsev]

Summary

This patch makes LICM use ICFLoopSafetyInfo that is a smarter version
of LoopSafetyInfo that leverages power of Implicit Control Flow Tracking
to keep track of throwing instructions and give less pessimistic answers
to queries related to throws.

The ICFLoopSafetyInfo itself has been introduced in rL344601. This patch
enables it in LICM only.

[mkazantsev]

I will split this into a functional change and a bunch of NFC's.

[mkazantsev]

test/Transforms/LICM/funclet.ll

60 ↗

(On Diff #159470)

Looks like we've exposed some bug in LICM.

[mkazantsev]

Fixed bug (missing fill of color map in the beginning), rebased on top of API NFC.

[fedor.sergeev]

I'm really worried about LoopSafetyInfo getting more nontrivial state
(Philip already raised a question in D50426 about CurLoop potentially becoming invalid, and here we get even more with addition of ICF).

Before this change LoopSafetyInfo was one-time-per-Loop-worker + constant queries after that, and original interface conveyed that.
Now every query becomes a potentially mutating worker, with a cache (ICF) that causes correctness problems if not being invalidated properly.

I have a feeling that changes suggested to the interface do not fully reflect the new semantics.
I can easily see how people can forget to invalidateBlock.
(and, btw, are we sure that invalidateBlock is not needed in places that use LoopSafetyInfo other than LICM?)

I dont know what should be a better solution, though I do suspect this is a problem frequently seen in LLVM so there should already be solutions
to invalidation of stale information after IR mutation.

Feel free to ignore all the above if it does not bother you :)

[mkazantsev]

It does bother me. I see now other way to make it fast. We can turn off caching in ICF and make it super-expensive but correct. That people may invalidate something is always a problem, we've seen a lot of it in SCEV, but what are the alternatives?

[mkazantsev]

include/llvm/Analysis/MustExecute.h

88 ↗

(On Diff #161012)

Infi -> Info

[reames]

lib/Analysis/MustExecute.cpp

32 ↗

(On Diff #161012)

We could chose to be more precise here by recomputing MayThrow lazily after invalidation.

lib/Transforms/Scalar/LICM.cpp

411

Invalidation is needed eagerly here.

485

BUG. Missing invalidation.

1303

There needs to be some invalidations somewhere within this function.

lib/Transforms/Scalar/LoopUnswitch.cpp

514 ↗

(On Diff #161012)

The fact there is no invalidation in loop unswitch is severely suspicious.

[mkazantsev]

Rebased, added cache invalidation in LICM. Still WIP because need to understand where do we need to invalidate in loop unswitching.

[mkazantsev]

Still wip until invalidation in LoopUnswitching is done properly (or proved that it is not needed).

[mkazantsev]

Added dependency to D51523. Though there is no functional dependency between them, I don't feel comfortable to let it be merged without validation we have there.

[mkazantsev]

Added more invalidation. Base fuzzing suite passes ok.

[fedor.sergeev]

lib/Transforms/Scalar/LoopUnswitch.cpp

525 ↗

(On Diff #163463)

Since we only need SafetyInfo for SanitizeMemory and it has already been converted to a pointer...
Perhaps it will be cleaner to:

• initialize SafetyInfo to non-null only under SanitizeMemory.
• operate on SafetyInfo (e.g. dropping caches) only under if (SanityInfo)
• setting SafetyInfo to null at the end of this function (just to avoid leaving dangling pointer)

[mkazantsev]

lib/Transforms/Scalar/LoopUnswitch.cpp

525 ↗

(On Diff #163463)

Good idea. I would rather not do it in this patch because I want everything which is not connected to the logic be straightforward. Will prepare a follow-up.

[reames]

Another round of bugs found.

I am generally concerned about the lack of progress towards a clearly correct patch here. I think we need to revisit how this is being approached and find a way to split this into individually obviously correct pieces.

One possible split (not the only one) would be the following:

1. Add ICF info to LoopSafetyInfo, but don't remove HeaderMayThrow approach. Enable the use of ICF (for asserts only) under an off by default flag. (Flag could be a param to constructor or cl::opt?)
2. For each pass, review in isolation. Update tests to use off by default flag.
3. Once *all* passes are done, change default and remove flag. (But still only ICF for asserts!)
4. Wait 1 week.
5. Remove HeaderMayThrow, and enhance logic.

lib/Transforms/Scalar/LICM.cpp

1303

It doesn't look like my previous comment has been addressed. There's still a bug here.

lib/Transforms/Scalar/LoopUnswitch.cpp

187 ↗

(On Diff #163463)

Default init to nullptr.

1558 ↗

(On Diff #163463)

Why? I think this is unnecessary.

[mkazantsev]

After digging deeper into the code, I grow more and more convinced that there was no bug to start with, and dangling pointers to instructions that are not tracked by ICF's map (even if they are tracked by OrderedInstructions) cause no problems.

I need to revisit the underlying patches, state clearly when we need to invalidate the ICF. My plan is to discard all invalidation from this code (except for guard motion). It was initially no bug there, and now the attempt to win this non-existent bug has made the code totally unreadable.

[mkazantsev]

https://reviews.llvm.org/D51664 This patch claims to make the OrderedInstructions auto-invalidable. If we build on top of that (and if it works :)), we may give up all invalidation stuff we currently have and only invalidate when we remove ICF instructions from blocks.

[mkazantsev]

Rebased on top of D51664. This patch is really helpful here because it makes the invalidation of OrderedInstructions automatic. With that, we *only* need to invalidate whenever we may actually change the first ICF instruction or when we erase a basic block. With that, I've discarded most of invalidation we've added on the previous steps because it is actually not needed. We don't need to invalidate when we insert Phis or do stuff like that.

I also think that the verification we have now is robust: it's up to OrderedInstructions to assert correctness of its auto-invalidation, and for ICF map we already have a pretty nice assertions that will tell us if we screwed up invalidating properly.

[mkazantsev]

Ping?

[mkazantsev]

Actually review can wait until the D51664 is merged. Might need rebase after that.

[mkazantsev]

I've checked in the underlying ICF logic in a separate class as NFC, see rL344601. The plan is to enable it in different passes one by one. This one enables it in LICM.

[dstenb]

Sorry, I can likely not give any valuable input for this review.

[apilipenko]

Current patch seems to have comments like "this block doesn't need invalidation". Maybe sink this decision down to the SafetyInfo implementation? It should reduce the complexity of the user: just call invalidate every time you delete/insert instructions and you would be fine.

lib/Transforms/Scalar/LICM.cpp

407–409

I'd suggest introducing a helper for removing the instruction. We need to do some invalidation every time an instruction is removed. Having a helper would help to avoid missing invalidation in new code.

1529–1532

Having invalidation in Promoter's callbacks (like instructionDeleted) seems more natural. We invalidate CurAST there.

[mkazantsev]

lib/Transforms/Scalar/LICM.cpp

407–409

We don't always do invalidation by eraseFromParent. There are cases when we move instructions, insert instructions or call run on promoter.

[mkazantsev]

Addressed comments.

[mkazantsev]

Rebased

[mkazantsev]

Updated test/CodeGen/AMDGPU/build-vector-insert-elt-infloop.ll

Without this patch, SaferyInfo falsely assumes that this loop is throwing and therefore prohibits promoter from elimination of the store. With smarter analysis, it is legal to eliminate the store, but the test doesn't expect that. Make store volatile to ensure that it doesn't get removed.

[mkazantsev]

BTW this test is invalid, it has a load from nullptr and therefore contains UB.

[apilipenko]

lib/Transforms/Scalar/LICM.cpp

518

I think we can invalidate once.

I know, in previous comments I was asking to move the complexity of the decision making whether the invalidation needed or not to the implementation of the SafetyInfo, but calling invalidation two times in a row is simple enough to fix in the caller.

[mkazantsev]

lib/Transforms/Scalar/LICM.cpp

518

It is free anyways.

include/llvm/Transforms/Utils/LoopUtils.h

 /// reverse depth first order w.r.t the DominatorTree. This allows us to visit
 /// uses before definitions, allowing us to sink a loop body in one pass without
 /// iteration. Takes DomTreeNode, AliasAnalysis, LoopInfo, DominatorTree,
 /// DataLayout, TargetLibraryInfo, Loop, AliasSet information for all
 /// instructions of the loop and loop safety information as
 /// arguments. Diagnostics is emitted via \p ORE. It returns changed status.
 bool sinkRegion(DomTreeNode *, AliasAnalysis *, LoopInfo *, DominatorTree *,
                 TargetLibraryInfo *, TargetTransformInfo *, Loop *,
-                AliasSetTracker *, LoopSafetyInfo *,
+                AliasSetTracker *, ICFLoopSafetyInfo *,
                 OptimizationRemarkEmitter *ORE);
 
 /// Walk the specified region of the CFG (defined by all blocks
 /// dominated by the specified block, and that are in the current loop) in depth
 /// first order w.r.t the DominatorTree.  This allows us to visit definitions
 /// before uses, allowing us to hoist a loop body in one pass without iteration.
 /// Takes DomTreeNode, AliasAnalysis, LoopInfo, DominatorTree, DataLayout,
 /// TargetLibraryInfo, Loop, AliasSet information for all instructions of the
 /// loop and loop safety information as arguments. Diagnostics is emitted via \p
 /// ORE. It returns changed status.
 bool hoistRegion(DomTreeNode *, AliasAnalysis *, LoopInfo *, DominatorTree *,
                  TargetLibraryInfo *, Loop *, AliasSetTracker *,
-                 LoopSafetyInfo *, OptimizationRemarkEmitter *ORE);
+                 ICFLoopSafetyInfo *, OptimizationRemarkEmitter *ORE);
 
 /// This function deletes dead loops. The caller of this function needs to
 /// guarantee that the loop is infact dead.
 /// The function requires a bunch or prerequisites to be present:
 ///   - The loop needs to be in LCSSA form
 ///   - The loop needs to have a Preheader
 ///   - A unique dedicated exit block must exist
 ///

 /// LoopInfo, DominatorTree, Loop, AliasSet information for all instructions
 /// of the loop and loop safety information as arguments.
 /// Diagnostics is emitted via \p ORE. It returns changed status.
 bool promoteLoopAccessesToScalars(const SmallSetVector<Value *, 8> &,
                                   SmallVectorImpl<BasicBlock *> &,
                                   SmallVectorImpl<Instruction *> &,
                                   PredIteratorCache &, LoopInfo *,
                                   DominatorTree *, const TargetLibraryInfo *,
-                                  Loop *, AliasSetTracker *, LoopSafetyInfo *,
+                                  Loop *, AliasSetTracker *,
+                                  ICFLoopSafetyInfo *,
                                   OptimizationRemarkEmitter *);
 
 /// Does a BFS from a given node to all of its children inside a given loop.
 /// The returned vector of nodes includes the starting point.
 SmallVector<DomTreeNode *, 16> collectChildrenInLoop(DomTreeNode *N,
                                                      const Loop *CurLoop);
 
 /// Returns the instructions that use values defined in the loop.

lib/Transforms/Scalar/LICM.cpp

 LICMN2Theshold("licm-n2-threshold", cl::Hidden, cl::init(0),
                cl::desc("How many instruction to cross product using AA"));
 
 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,
-                  LoopSafetyInfo *SafetyInfo,
+                  ICFLoopSafetyInfo *SafetyInfo,
                   OptimizationRemarkEmitter *ORE);
 static bool sink(Instruction &I, LoopInfo *LI, DominatorTree *DT,
-                 const Loop *CurLoop, LoopSafetyInfo *SafetyInfo,
+                 const Loop *CurLoop, ICFLoopSafetyInfo *SafetyInfo,
                  OptimizationRemarkEmitter *ORE, bool FreeInLoop);
 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,
bool LoopInvariantCodeMotion::runOnLoop(
   assert(L->isLCSSAForm(*DT) && "Loop is not in LCSSA form.");
 
   std::unique_ptr<AliasSetTracker> CurAST = collectAliasInfoForLoop(L, LI, AA);
 
   // Get the preheader block to move instructions into...
   BasicBlock *Preheader = L->getLoopPreheader();
 
   // Compute loop safety information.
-  SimpleLoopSafetyInfo SafetyInfo;
+  ICFLoopSafetyInfo SafetyInfo(DT);
   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

 /// 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 uses before
 /// definitions, allowing us to sink a loop body in one pass without iteration.
 ///
 bool llvm::sinkRegion(DomTreeNode *N, AliasAnalysis *AA, LoopInfo *LI,
                       DominatorTree *DT, TargetLibraryInfo *TLI,
                       TargetTransformInfo *TTI, Loop *CurLoop,
-                      AliasSetTracker *CurAST, LoopSafetyInfo *SafetyInfo,
+                      AliasSetTracker *CurAST, ICFLoopSafetyInfo *SafetyInfo,
                       OptimizationRemarkEmitter *ORE) {
 
   // Verify inputs.
   assert(N != nullptr && AA != nullptr && LI != nullptr && DT != nullptr &&
          CurLoop != nullptr && CurAST && SafetyInfo != nullptr &&
          "Unexpected input to sinkRegion");
 
   // We want to visit children before parents. We will enque all the parents
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');
         salvageDebugInfo(I);
         ++II;
+        SafetyInfo->removeInstruction(&I);
         CurAST->deleteValue(&I);
         I.eraseFromParent();
         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 (isNotUsedOrFreeInLoop(I, CurLoop, SafetyInfo, TTI, FreeInLoop) &&
           canSinkOrHoistInst(I, AA, DT, CurLoop, CurAST, true, ORE) &&
           !I.mayHaveSideEffects()) {
         if (sink(I, LI, DT, CurLoop, SafetyInfo, ORE, FreeInLoop)) {
           if (!FreeInLoop) {
             ++II;
+            SafetyInfo->removeInstruction(&I);
             CurAST->deleteValue(&I);
             I.eraseFromParent();
           }
           Changed = true;
         }
       }
     }
   }
   return Changed;
 }
 
 /// Walk the specified region of the CFG (defined by all blocks dominated by
 /// the specified block, and that are in the current loop) in depth first
 /// order w.r.t the DominatorTree.  This allows us to visit definitions before
 /// uses, allowing us to hoist a loop body in one pass without iteration.
 ///
 bool llvm::hoistRegion(DomTreeNode *N, AliasAnalysis *AA, LoopInfo *LI,
                        DominatorTree *DT, TargetLibraryInfo *TLI, Loop *CurLoop,
-                       AliasSetTracker *CurAST, LoopSafetyInfo *SafetyInfo,
+                       AliasSetTracker *CurAST, ICFLoopSafetyInfo *SafetyInfo,
                        OptimizationRemarkEmitter *ORE) {
   // Verify inputs.
   assert(N != nullptr && AA != nullptr && LI != nullptr && DT != nullptr &&
          CurLoop != nullptr && CurAST != nullptr && SafetyInfo != nullptr &&
          "Unexpected input to hoistRegion");
 
   // We want to visit parents before children. We will enque all the parents
   // before their children in the worklist and process the worklist in order.
for (BasicBlock::iterator II = BB->begin(), E = BB->end(); II != E;) {
       // just fold it.
       if (Constant *C = ConstantFoldInstruction(
               &I, I.getModule()->getDataLayout(), TLI)) {
         LLVM_DEBUG(dbgs() << "LICM folding inst: " << I << "  --> " << *C
                           << '\n');
         CurAST->copyValue(&I, C);
         I.replaceAllUsesWith(C);
         if (isInstructionTriviallyDead(&I, TLI)) {
+          SafetyInfo->removeInstruction(&I);
           CurAST->deleteValue(&I);
           I.eraseFromParent();
         }
         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.
for (BasicBlock::iterator II = BB->begin(), E = BB->end(); II != E;) {
       // converting it to a reciprocal multiplication.
       if (I.getOpcode() == Instruction::FDiv &&
           CurLoop->isLoopInvariant(I.getOperand(1)) &&
           I.hasAllowReciprocal()) {
         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->removeInstruction(&I);
+        SafetyInfo->insertInstructionTo(I.getParent());
         ReciprocalDivisor->insertBefore(&I);
 
         auto Product =
             BinaryOperator::CreateFMul(I.getOperand(0), ReciprocalDivisor);
         Product->setFastMathFlags(I.getFastMathFlags());
+        SafetyInfo->insertInstructionTo(I.getParent());
         Product->insertAfter(&I);
         I.replaceAllUsesWith(Product);
         I.eraseFromParent();
 
         hoist(*ReciprocalDivisor, DT, CurLoop, SafetyInfo, ORE);
         Changed = true;
         continue;
       }

 }
 
 /// 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, LoopSafetyInfo *SafetyInfo,
+                 const Loop *CurLoop, ICFLoopSafetyInfo *SafetyInfo,
                  OptimizationRemarkEmitter *ORE, bool FreeInLoop) {
   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))
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);
     PN->replaceAllUsesWith(New);
+    SafetyInfo->insertInstructionTo(New->getParent());
+    SafetyInfo->removeInstruction(PN);
     PN->eraseFromParent();
     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,
-                  LoopSafetyInfo *SafetyInfo, OptimizationRemarkEmitter *ORE) {
+                  ICFLoopSafetyInfo *SafetyInfo, OptimizationRemarkEmitter *ORE) {
   auto *Preheader = CurLoop->getLoopPreheader();
   LLVM_DEBUG(dbgs() << "LICM hoisting to " << Preheader->getName() << ": " << I
                     << "\n");
   ORE->emit([&]() {
     return OptimizationRemark(DEBUG_TYPE, "Hoisted", &I) << "hoisting "
                                                          << ore::NV("Inst", &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.
       !SafetyInfo->isGuaranteedToExecute(I, DT, CurLoop))
     I.dropUnknownNonDebugMetadata();
 
+  SafetyInfo->removeInstruction(&I);
+  SafetyInfo->insertInstructionTo(Preheader);
   // Move the new node to the Preheader, before its terminator.
   I.moveBefore(Preheader->getTerminator());
 
   // Do not retain debug locations when we are moving instructions to different
   // basic blocks, because we want to avoid jumpy line tables. Calls, however,
   // need to retain their debug locs because they may be inlined.
   // FIXME: How do we retain source locations without causing poor debugging
   // behavior?
class LoopPromoter : public LoadAndStorePromoter {
   SmallVectorImpl<Instruction *> &LoopInsertPts;
   PredIteratorCache &PredCache;
   AliasSetTracker &AST;
   LoopInfo &LI;
   DebugLoc DL;
   int Alignment;
   bool UnorderedAtomic;
   AAMDNodes AATags;
+  ICFLoopSafetyInfo &SafetyInfo;
 
   Value *maybeInsertLCSSAPHI(Value *V, BasicBlock *BB) const {
     if (Instruction *I = dyn_cast<Instruction>(V))
       if (Loop *L = LI.getLoopFor(I->getParent()))
         if (!L->contains(BB)) {
           // We need to create an LCSSA PHI node for the incoming value and
           // store that.
           PHINode *PN = PHINode::Create(I->getType(), PredCache.size(BB),
                                         I->getName() + ".lcssa", &BB->front());
           for (BasicBlock *Pred : PredCache.get(BB))
             PN->addIncoming(I, Pred);
           return PN;
         }
     return V;
   }
 
 public:
   LoopPromoter(Value *SP, ArrayRef<const Instruction *> Insts, SSAUpdater &S,
                const SmallSetVector<Value *, 8> &PMA,
                SmallVectorImpl<BasicBlock *> &LEB,
                SmallVectorImpl<Instruction *> &LIP, PredIteratorCache &PIC,
                AliasSetTracker &ast, LoopInfo &li, DebugLoc dl, int alignment,
-               bool UnorderedAtomic, const AAMDNodes &AATags)
+               bool UnorderedAtomic, const AAMDNodes &AATags,
+               ICFLoopSafetyInfo &SafetyInfo)
       : LoadAndStorePromoter(Insts, S), SomePtr(SP), PointerMustAliases(PMA),
         LoopExitBlocks(LEB), LoopInsertPts(LIP), PredCache(PIC), AST(ast),
         LI(li), DL(std::move(dl)), Alignment(alignment),
-        UnorderedAtomic(UnorderedAtomic), AATags(AATags) {}
+        UnorderedAtomic(UnorderedAtomic), AATags(AATags), SafetyInfo(SafetyInfo)
+      {}
 
   bool isInstInList(Instruction *I,
                     const SmallVectorImpl<Instruction *> &) const override {
     Value *Ptr;
     if (LoadInst *LI = dyn_cast<LoadInst>(I))
       Ptr = LI->getOperand(0);
     else
       Ptr = cast<StoreInst>(I)->getPointerOperand();
for (unsigned i = 0, e = LoopExitBlocks.size(); i != e; ++i) {
         NewSI->setAAMetadata(AATags);
     }
   }
 
   void replaceLoadWithValue(LoadInst *LI, Value *V) const override {
     // Update alias analysis.
     AST.copyValue(LI, V);
   }
-  void instructionDeleted(Instruction *I) const override { AST.deleteValue(I); }
+  void instructionDeleted(Instruction *I) const override {
+    SafetyInfo.removeInstruction(I);
+    AST.deleteValue(I);
+  }
 };
 
 
 /// Return true iff we can prove that a caller of this function can not inspect
 /// the contents of the provided object in a well defined program.
 bool isKnownNonEscaping(Value *Object, const TargetLibraryInfo *TLI) {
   if (isa<AllocaInst>(Object))
     // Since the alloca goes out of scope, we know the caller can't retain a

 /// the stores in the loop, looking for stores to Must pointers which are
 /// loop invariant.
 ///
 bool llvm::promoteLoopAccessesToScalars(
     const SmallSetVector<Value *, 8> &PointerMustAliases,
     SmallVectorImpl<BasicBlock *> &ExitBlocks,
     SmallVectorImpl<Instruction *> &InsertPts, PredIteratorCache &PIC,
     LoopInfo *LI, DominatorTree *DT, const TargetLibraryInfo *TLI,
-    Loop *CurLoop, AliasSetTracker *CurAST, LoopSafetyInfo *SafetyInfo,
+    Loop *CurLoop, AliasSetTracker *CurAST, ICFLoopSafetyInfo *SafetyInfo,
     OptimizationRemarkEmitter *ORE) {
   // Verify inputs.
   assert(LI != nullptr && DT != nullptr && CurLoop != nullptr &&
          CurAST != nullptr && SafetyInfo != nullptr &&
          "Unexpected Input to promoteLoopAccessesToScalars");
 
   Value *SomePtr = *PointerMustAliases.begin();
   BasicBlock *Preheader = CurLoop->getLoopPreheader();
 
   // It is not safe to promote a load/store from the loop if the load/store is
   // conditional.  For example, turning:
   //
   //    for () { if (c) *P += 1; }
   //
   // into:
bool llvm::promoteLoopAccessesToScalars(
   // location is better than none.
   DebugLoc DL = LoopUses[0]->getDebugLoc();
 
   // We use the SSAUpdater interface to insert phi nodes as required.
   SmallVector<PHINode *, 16> NewPHIs;
   SSAUpdater SSA(&NewPHIs);
   LoopPromoter Promoter(SomePtr, LoopUses, SSA, PointerMustAliases, ExitBlocks,
                         InsertPts, PIC, *CurAST, *LI, DL, Alignment,
-                        SawUnorderedAtomic, AATags);
+                        SawUnorderedAtomic, AATags, *SafetyInfo);
 
   // Set up the preheader to have a definition of the value.  It is the live-out
   // value from the preheader that uses in the loop will use.
   LoadInst *PreheaderLoad = new LoadInst(
       SomePtr, SomePtr->getName() + ".promoted", Preheader->getTerminator());
   if (SawUnorderedAtomic)
     PreheaderLoad->setOrdering(AtomicOrdering::Unordered);
   PreheaderLoad->setAlignment(Alignment);
   PreheaderLoad->setDebugLoc(DL);
   if (AATags)
     PreheaderLoad->setAAMetadata(AATags);
   SSA.AddAvailableValue(Preheader, PreheaderLoad);
 
   // Rewrite all the loads in the loop and remember all the definitions from
   // stores in the loop.
   Promoter.run(LoopUses);
 
   // If the SSAUpdater didn't use the load in the preheader, just zap it now.
-  if (PreheaderLoad->use_empty())
+  if (PreheaderLoad->use_empty()) {
+    SafetyInfo->removeInstruction(PreheaderLoad);
     PreheaderLoad->eraseFromParent();
+  }
 
   return true;
 }
 
 /// Returns an owning pointer to an alias set which incorporates aliasing info
 /// from L and all subloops of L.
 /// FIXME: In new pass manager, there is no helper function to handle loop
 /// analysis such as cloneBasicBlockAnalysis, so the AST needs to be recomputed

test/Transforms/LICM/guards.ll

loop:
   call void (i1, ...) @llvm.experimental.guard(i1 %cond) ["deopt" (i32 0)]
   %val = load i32, i32* %ptr
   store i32 0, i32* %ptr
   %x.inc = add i32 %x, %val
   br label %loop
 }
 
 
-; TODO: We can also hoist this load and guard from mustexec non-header block.
+; TODO: We can also hoist this guard from mustexec non-header block.
 define void @test4(i1 %c, i32* %p) {
 
 ; CHECK-LABEL: @test4(
 ; CHECK-LABEL: entry:
-; CHECK-LABEL: loop:
-; CHECK-LABEL: backedge:
 ; CHECK:       %a = load i32, i32* %p
 ; CHECK:       %invariant_cond = icmp ne i32 %a, 100
+; CHECK-LABEL: loop:
+; CHECK-LABEL: backedge:
 ; CHECK:       call void (i1, ...) @llvm.experimental.guard(i1 %invariant_cond)
 
 entry:
   br label %loop
 
 loop:
   %iv = phi i32 [ 0, %entry ], [ %iv.next, %backedge ]
   %iv.next = add i32 %iv, 1

test/Transforms/LICM/hoist-mustexec.ll

backedge:
   %merge = phi i32 [ %a, %if.true ], [ %b, %if.false ]
   %iv.next = add i32 %iv, %merge
   %loop.cond = icmp ult i32 %iv.next, %load
   br i1 %loop.cond, label %loop, label %exit
 
 exit:
   ret void
 }
+
+; Check that we can hoist a mustexecute load from backedge even if something
+; throws after it.
+define void @test_hoist_from_backedge_01(i32* %p, i32 %n) {
+
+; CHECK-LABEL: @test_hoist_from_backedge_01(
+; CHECK:       entry:
+; CHECK-NEXT:  %load = load i32, i32* %p
+; CHECK-NOT:   load i32
+
+entry:
+  br label %loop
+
+loop:
+  %iv = phi i32 [ 0, %entry ], [ %iv.next, %backedge ]
+  %dummy = phi i32 [ 0, %entry ], [ %merge, %backedge ]
+  %cond = icmp slt i32 %iv, %n
+  br i1 %cond, label %if.true, label %if.false
+
+if.true:
+  %a = add i32 %iv, %iv
+  br label %backedge
+
+if.false:
+  %b = mul i32 %iv, %iv
+  br label %backedge
+
+backedge:
+  %merge = phi i32 [ %a, %if.true ], [ %b, %if.false ]
+  %iv.next = add i32 %iv, %merge
+  %load = load i32, i32* %p
+  call void @may_throw()
+  %loop.cond = icmp ult i32 %iv.next, %load
+  br i1 %loop.cond, label %loop, label %exit
+
+exit:
+  ret void
+}
+
+; Check that we don't hoist the load if something before it can throw.
+define void @test_hoist_from_backedge_02(i32* %p, i32 %n) {
+
+; CHECK-LABEL: @test_hoist_from_backedge_02(
+; CHECK:       entry:
+; CHECK:       loop:
+; CHECK:       %load = load i32, i32* %p
+
+entry:
+  br label %loop
+
+loop:
+  %iv = phi i32 [ 0, %entry ], [ %iv.next, %backedge ]
+  %dummy = phi i32 [ 0, %entry ], [ %merge, %backedge ]
+  %cond = icmp slt i32 %iv, %n
+  br i1 %cond, label %if.true, label %if.false
+
+if.true:
+  %a = add i32 %iv, %iv
+  br label %backedge
+
+if.false:
+  %b = mul i32 %iv, %iv
+  br label %backedge
+
+backedge:
+  %merge = phi i32 [ %a, %if.true ], [ %b, %if.false ]
+  %iv.next = add i32 %iv, %merge
+  call void @may_throw()
+  %load = load i32, i32* %p
+  %loop.cond = icmp ult i32 %iv.next, %load
+  br i1 %loop.cond, label %loop, label %exit
+
+exit:
+  ret void
+}
+
+define void @test_hoist_from_backedge_03(i32* %p, i32 %n) {
+
+; CHECK-LABEL: @test_hoist_from_backedge_03(
+; CHECK:       entry:
+; CHECK:       loop:
+; CHECK:       %load = load i32, i32* %p
+
+entry:
+  br label %loop
+
+loop:
+  %iv = phi i32 [ 0, %entry ], [ %iv.next, %backedge ]
+  %dummy = phi i32 [ 0, %entry ], [ %merge, %backedge ]
+  %cond = icmp slt i32 %iv, %n
+  br i1 %cond, label %if.true, label %if.false
+
+if.true:
+  %a = add i32 %iv, %iv
+  br label %backedge
+
+if.false:
+  %b = mul i32 %iv, %iv
+  call void @may_throw()
+  br label %backedge
+
+backedge:
+  %merge = phi i32 [ %a, %if.true ], [ %b, %if.false ]
+  %iv.next = add i32 %iv, %merge
+  %load = load i32, i32* %p
+  %loop.cond = icmp ult i32 %iv.next, %load
+  br i1 %loop.cond, label %loop, label %exit
+
+exit:
+  ret void
+}
+
+define void @test_hoist_from_backedge_04(i32* %p, i32 %n) {
+
+; CHECK-LABEL: @test_hoist_from_backedge_04(
+; CHECK:       entry:
+; CHECK:       loop:
+; CHECK:       %load = load i32, i32* %p
+
+entry:
+  br label %loop
+
+loop:
+  %iv = phi i32 [ 0, %entry ], [ %iv.next, %backedge ]
+  %dummy = phi i32 [ 0, %entry ], [ %merge, %backedge ]
+  call void @may_throw()
+  %cond = icmp slt i32 %iv, %n
+  br i1 %cond, label %if.true, label %if.false
+
+if.true:
+  %a = add i32 %iv, %iv
+  br label %backedge
+
+if.false:
+  %b = mul i32 %iv, %iv
+  br label %backedge
+
+backedge:
+  %merge = phi i32 [ %a, %if.true ], [ %b, %if.false ]
+  %iv.next = add i32 %iv, %merge
+  %load = load i32, i32* %p
+  %loop.cond = icmp ult i32 %iv.next, %load
+  br i1 %loop.cond, label %loop, label %exit
+
+exit:
+  ret void
+}

test/Transforms/LICM/hoist-nounwind.ll

for.body:
   %inc = add i32 %add, %div
   %cmp = icmp slt i32 %inc, %N
   br i1 %cmp, label %for.body, label %for.cond.cleanup
 
 for.cond.cleanup:
   ret i32 0
 }
 
-; Don't hoist load past volatile load.
+; Hoist a non-volatile load past volatile load.
 define i32 @test3(i32* noalias nocapture readonly %a, i32* %v) nounwind uwtable {
 ; CHECK-LABEL: @test3(
 entry:
   br label %for.body
 
+; CHECK: load i32
+; CHECK: for.body:
 ; CHECK: load volatile i32
-; CHECK-NEXT: load i32
+; CHECK-NOT: load
 for.body:
   %i.06 = phi i32 [ 0, %entry ], [ %inc, %for.body ]
   %x.05 = phi i32 [ 0, %entry ], [ %add, %for.body ]
   %xxx = load volatile i32, i32* %v, align 4
   %i1 = load i32, i32* %a, align 4
   %add = add nsw i32 %i1, %x.05
   %inc = add nuw nsw i32 %i.06, 1
   %exitcond = icmp eq i32 %inc, 1000
   br i1 %exitcond, label %for.cond.cleanup, label %for.body
 
 for.cond.cleanup:
   ret i32 %add
 }
+
+; Don't a volatile load past volatile load.
+define i32 @test4(i32* noalias nocapture readonly %a, i32* %v) nounwind uwtable {
+; CHECK-LABEL: @test4(
+entry:
+  br label %for.body
+
+; CHECK: for.body:
+; CHECK: load volatile i32
+; CHECK-NEXT: load volatile i32
+for.body:
+  %i.06 = phi i32 [ 0, %entry ], [ %inc, %for.body ]
+  %x.05 = phi i32 [ 0, %entry ], [ %add, %for.body ]
+  %xxx = load volatile i32, i32* %v, align 4
+  %i1 = load volatile i32, i32* %a, align 4
+  %add = add nsw i32 %i1, %x.05
+  %inc = add nuw nsw i32 %i.06, 1
+  %exitcond = icmp eq i32 %inc, 1000
+  br i1 %exitcond, label %for.cond.cleanup, label %for.body
+
+for.cond.cleanup:
+  ret i32 %add
+}
 No newline at end of file

test/Transforms/LICM/preheader-safe.ll

loop:                                         ; preds = %entry, %for.inc
   %div = udiv i64 %x, %y
   br i1 %cond, label %loop-if, label %exit
 loop-if:
   call void @use(i64 %div)
   br label %loop
 exit:
   ret void
 }
+
+; Positive test - can hoist something that happens before thrower.
+define void @nothrow_header_pos(i64 %x, i64 %y, i1 %cond) {
+; CHECK-LABEL: nothrow_header_pos
+; CHECK-LABEL: entry
+; CHECK: %div = udiv i64 %x, %y
+; CHECK-LABEL: loop
+; CHECK: call void @use(i64 %div)
+entry:
+  br label %loop
+loop:                                         ; preds = %entry, %for.inc
+  br label %loop-if
+loop-if:
+  %div = udiv i64 %x, %y
+  call void @use(i64 %div)
+  br label %loop
+}
+
+
 ; Negative test - can't move out of throwing block
 define void @nothrow_header_neg(i64 %x, i64 %y, i1 %cond) {
 ; CHECK-LABEL: nothrow_header_neg
 ; CHECK-LABEL: entry
 ; CHECK-LABEL: loop
+; CHECK: call void @maythrow()
 ; CHECK: %div = udiv i64 %x, %y
 ; CHECK: call void @use(i64 %div)
 entry:
   br label %loop
 loop:                                         ; preds = %entry, %for.inc
   br label %loop-if
 loop-if:
+  call void @maythrow()
   %div = udiv i64 %x, %y
   call void @use(i64 %div)
   br label %loop
 }