[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

95

Infi -> Info

[reames]

lib/Analysis/MustExecute.cpp

32

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.

1315

There needs to be some invalidations somewhere within this function.

lib/Transforms/Scalar/LoopUnswitch.cpp

514

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

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

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

1315

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

lib/Transforms/Scalar/LoopUnswitch.cpp

187

Default init to nullptr.

1558

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.

1541–1544

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

522

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

522

It is free anyways.

include/llvm/Analysis/MustExecute.h

 ///
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_ANALYSIS_MUSTEXECUTE_H
 #define LLVM_ANALYSIS_MUSTEXECUTE_H
 
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/Analysis/EHPersonalities.h"
+#include "llvm/Analysis/InstructionPrecedenceTracking.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/Instruction.h"
 
 namespace llvm {
 
 class Instruction;

 /// any thrower instructions have been added or removed from them, or if the
 /// control flow has changed, or in case of other meaningful modifications, the
 /// LoopSafetyInfo needs to be recomputed. If a meaningful modifications to the
 /// loop were made and the info wasn't recomputed properly, the behavior of all
 /// methods except for computeLoopSafetyInfo is undefined.
 class LoopSafetyInfo {
   bool MayThrow = false;       // The current loop contains an instruction which
                                // may throw.
-  bool HeaderMayThrow = false; // Same as previous, but specific to loop header
-
+  // Contains information about implicit control flow in this loop's blocks.
+  mutable ImplicitControlFlowTracking ICF;
   /// Collect all blocks from \p CurLoop which lie on all possible paths from
   /// the header of \p CurLoop (inclusive) to BB (exclusive) into the set
   /// \p Predecessors. If \p BB is the header, \p Predecessors will be empty.
   void collectTransitivePredecessors(
       const Loop *CurLoop, const BasicBlock *BB,
       SmallPtrSetImpl<const BasicBlock *> &Predecessors) const;
 
 public:
   // Used to update funclet bundle operands.
   DenseMap<BasicBlock *, ColorVector> BlockColors;
 
-  /// Returns true iff the header block of the loop for which this info is
-  /// calculated contains an instruction that may throw or otherwise exit
-  /// abnormally.
-  bool headerMayThrow() const;
-
   /// Returns true iff any block of the loop for which this info is contains an
   /// instruction that may throw or otherwise exit abnormally.
   bool anyBlockMayThrow() const;
 
   /// Return true if we must reach the block \p BB under assumption that the
-  /// loop \p CurLoop is entered and no instruction throws or otherwise exits
-  /// abnormally.
+  /// loop \p CurLoop is entered.
   bool allLoopPathsLeadToBlock(const Loop *CurLoop, const BasicBlock *BB,
                                const DominatorTree *DT) const;
 
+  /// Return true if we must execute the instruction \p I under assumption that
+  /// the loop \p CurLoop is entered.
+  bool mustExecuteInLoop(const Loop *CurLoop, const Instruction *I,
+                         const DominatorTree *DT) const;
+
+  /// Drops cached information regarding the implicit control flow in block
+  /// \p BB. It should be called for every block in which we add or remove any
+  /// instructions.
+  void dropCachedInfo(const BasicBlock *BB);
+
   /// Computes safety information for a loop checks loop body & header for
   /// the possibility of may throw exception, it takes LoopSafetyInfo and loop
   /// as argument. Updates safety information in LoopSafetyInfo argument.
   /// Note: This is defined to clear and reinitialize an already initialized
   /// LoopSafetyInfo.  Some callers rely on this fact.
   void computeLoopSafetyInfo(Loop *);
 
-  LoopSafetyInfo() = default;
+  LoopSafetyInfo(DominatorTree *DT): ICF(DT) {}
 };
 
 /// Returns true if the instruction in a loop is guaranteed to execute at least
 /// once (under the assumption that the loop is entered).
+/// TODO: Remove the function, call SafetyInfo->mustExecuteInLoop instead.
 bool isGuaranteedToExecute(const Instruction &Inst, const DominatorTree *DT,
                            const Loop *CurLoop,
                            const LoopSafetyInfo *SafetyInfo);
 
 }
 
 #endif

lib/Analysis/MustExecute.cpp

 #include "llvm/IR/InstIterator.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/Module.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/FormattedStream.h"
 #include "llvm/Support/raw_ostream.h"
 using namespace llvm;
 
-bool LoopSafetyInfo::headerMayThrow() const {
-  return HeaderMayThrow;
-}
-
 bool LoopSafetyInfo::anyBlockMayThrow() const {
   return MayThrow;
 }
 
 void LoopSafetyInfo::computeLoopSafetyInfo(Loop *CurLoop) {
   assert(CurLoop != nullptr && "CurLoop can't be null");
-  BasicBlock *Header = CurLoop->getHeader();
-  // Iterate over header and compute safety info.
-  HeaderMayThrow = !isGuaranteedToTransferExecutionToSuccessor(Header);
-  MayThrow = HeaderMayThrow;
-  // Iterate over loop instructions and compute safety info.
-  // Skip header as it has been computed and stored in HeaderMayThrow.
-  // The first block in loopinfo.Blocks is guaranteed to be the header.
-  assert(Header == *CurLoop->getBlocks().begin() &&
-         "First block must be header");
-  for (Loop::block_iterator BB = std::next(CurLoop->block_begin()),
-                            BBE = CurLoop->block_end();
-       (BB != BBE) && !MayThrow; ++BB)
-    MayThrow |= !isGuaranteedToTransferExecutionToSuccessor(*BB);
+  ICF.clear();
+  MayThrow = false;
+  // Figure out the fact that at least one block may throw.
+  for (auto &BB : CurLoop->blocks())
+    if (ICF.hasICF(&*BB)) {
+      MayThrow = true;
+      break;
+    }
 
   // Compute funclet colors if we might sink/hoist in a function with a funclet
   // personality routine.
   Function *Fn = CurLoop->getHeader()->getParent();
   if (Fn->hasPersonalityFn())
     if (Constant *PersonalityFn = Fn->getPersonalityFn())
       if (isScopedEHPersonality(classifyEHPersonality(PersonalityFn)))
         BlockColors = colorEHFunclets(*Fn);
bool LoopSafetyInfo::allLoopPathsLeadToBlock(const Loop *CurLoop,
   collectTransitivePredecessors(CurLoop, BB, Predecessors);
 
   // Make sure that all successors of all predecessors of BB are either:
   // 1) BB,
   // 2) Also predecessors of BB,
   // 3) Exit blocks which are not taken on 1st iteration.
   // Memoize blocks we've already checked.
   SmallPtrSet<const BasicBlock *, 4> CheckedSuccessors;
-  for (auto *Pred : Predecessors)
+  for (auto *Pred : Predecessors) {
+    // Check if we can exit via throw or other abnormal exit.
+    if (ICF.hasICF(Pred))
+      return false;
     for (auto *Succ : successors(Pred))
       if (CheckedSuccessors.insert(Succ).second &&
           Succ != BB && !Predecessors.count(Succ))
         // By discharging conditions that are not executed on the 1st iteration,
         // we guarantee that *at least* on the first iteration all paths from
         // header that *may* execute will lead us to the block of interest. So
         // that if we had virtually peeled one iteration away, in this peeled
         // iteration the set of predecessors would contain only paths from
         // header to BB without any exiting edges that may execute.
         //
         // TODO: We only do it for exiting edges currently. We could use the
         // same function to skip some of the edges within the loop if we know
         // that they will not be taken on the 1st iteration.
         //
         // TODO: If we somehow know the number of iterations in loop, the same
         // check may be done for any arbitrary N-th iteration as long as N is
         // not greater than minimum number of iterations in this loop.
         if (CurLoop->contains(Succ) ||
             !CanProveNotTakenFirstIteration(Succ, DT, CurLoop))
           return false;
+  }
 
   // All predecessors can only lead us to BB.
   return true;
 }
 
+bool LoopSafetyInfo::mustExecuteInLoop(const Loop *CurLoop,
+                                       const Instruction *I,
+                                       const DominatorTree *DT) const {
+  return !ICF.isDominatedByICFIFromSameBlock(I) &&
+         allLoopPathsLeadToBlock(CurLoop, I->getParent(), DT);
+}
+
+void LoopSafetyInfo::dropCachedInfo(const BasicBlock *BB) {
+  ICF.invalidateBlock(BB);
+}
+
 /// Returns true if the instruction in a loop is guaranteed to execute at least
 /// once.
 bool llvm::isGuaranteedToExecute(const Instruction &Inst,
                                  const DominatorTree *DT, const Loop *CurLoop,
                                  const LoopSafetyInfo *SafetyInfo) {
-  // We have to check to make sure that the instruction dominates all
-  // of the exit blocks.  If it doesn't, then there is a path out of the loop
-  // which does not execute this instruction, so we can't hoist it.
-
-  // If the instruction is in the header block for the loop (which is very
-  // common), it is always guaranteed to dominate the exit blocks.  Since this
-  // is a common case, and can save some work, check it now.
-  if (Inst.getParent() == CurLoop->getHeader())
-    // If there's a throw in the header block, we can't guarantee we'll reach
-    // Inst unless we can prove that Inst comes before the potential implicit
-    // exit.  At the moment, we use a (cheap) hack for the common case where
-    // the instruction of interest is the first one in the block.
-    return !SafetyInfo->headerMayThrow() ||
-      Inst.getParent()->getFirstNonPHIOrDbg() == &Inst;
-
-  // Somewhere in this loop there is an instruction which may throw and make us
-  // exit the loop.
-  if (SafetyInfo->anyBlockMayThrow())
-    return false;
-
-  // If there is a path from header to exit or latch that doesn't lead to our
-  // instruction's block, return false.
-  if (!SafetyInfo->allLoopPathsLeadToBlock(CurLoop, Inst.getParent(), DT))
-    return false;
-
-  return true;
+  return SafetyInfo->mustExecuteInLoop(CurLoop, &Inst, DT);
 }
 
 
 namespace {
   struct MustExecutePrinter : public FunctionPass {
 
     static char ID; // Pass identification, replacement for typeid
     MustExecutePrinter() : FunctionPass(ID) {

 FunctionPass *llvm::createMustExecutePrinter() {
   return new MustExecutePrinter();
 }
 
 static bool isMustExecuteIn(const Instruction &I, Loop *L, DominatorTree *DT) {
   // TODO: merge these two routines.  For the moment, we display the best
   // result obtained by *either* implementation.  This is a bit unfair since no
   // caller actually gets the full power at the moment.
-  LoopSafetyInfo LSI;
+  LoopSafetyInfo LSI(DT);
   LSI.computeLoopSafetyInfo(L);
   return isGuaranteedToExecute(I, DT, L, &LSI) ||
     isGuaranteedToExecuteForEveryIteration(&I, L);
 }
 
 namespace {
 /// An assembly annotator class to print must execute information in
 /// comments.

lib/Transforms/Scalar/LICM.cpp

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.
-  LoopSafetyInfo SafetyInfo;
+  LoopSafetyInfo 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
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->dropCachedInfo(BB);
         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;
             CurAST->deleteValue(&I);
+            // Dropping SafetyInfo is already done within sink, so no need for
+            // it here.
             I.eraseFromParent();
           }
           Changed = true;
         }
       }
     }
   }
   return Changed;
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');
         CurAST->copyValue(&I, C);
         I.replaceAllUsesWith(C);
         if (isInstructionTriviallyDead(&I, TLI)) {
           CurAST->deleteValue(&I);
           I.eraseFromParent();
         }
+        SafetyInfo->dropCachedInfo(BB);
         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.
       //
       if (CurLoop->hasLoopInvariantOperands(&I) &&
           canSinkOrHoistInst(I, AA, DT, CurLoop, CurAST, true, ORE) &&
           (IsMustExecute ||
            isSafeToExecuteUnconditionally(
                I, DT, CurLoop, SafetyInfo, ORE,
                CurLoop->getLoopPreheader()->getTerminator()))) {
         hoist(I, DT, CurLoop, SafetyInfo, ORE);
         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 &&
           CurLoop->isLoopInvariant(I.getOperand(1)) &&
           I.hasAllowReciprocal()) {
+        // We are going to make changes to BB which means we need to invalidate
+        // cached info to have valid info by the moment of hoist.
+        SafetyInfo->dropCachedInfo(BB);
         auto Divisor = I.getOperand(1);
         auto One = llvm::ConstantFP::get(Divisor->getType(), 1.0);
         auto ReciprocalDivisor = BinaryOperator::CreateFDiv(One, Divisor);
         ReciprocalDivisor->setFastMathFlags(I.getFastMathFlags());
         ReciprocalDivisor->insertBefore(&I);
 
         auto Product =
             BinaryOperator::CreateFMul(I.getOperand(0), ReciprocalDivisor);
         Product->setFastMathFlags(I.getFastMathFlags());
         Product->insertAfter(&I);
         I.replaceAllUsesWith(Product);
         I.eraseFromParent();
 

 static bool sink(Instruction &I, LoopInfo *LI, DominatorTree *DT,
                  const Loop *CurLoop, LoopSafetyInfo *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);
   });
+
+  // Contents of a block may change, we need to mark it in safety info.
+  SafetyInfo->dropCachedInfo(I.getParent());
+
   bool Changed = false;
   if (isa<LoadInst>(I))
     ++NumMovedLoads;
   else if (isa<CallInst>(I))
     ++NumMovedCalls;
   ++NumSunk;
 
   // Iterate over users to be ready for actual sinking. Replace users via
for (Value::user_iterator UI = I.user_begin(), UE = I.user_end(); UI != UE;) {
     // The user must be a PHI node.
     PHINode *PN = cast<PHINode>(User);
 
     // Surprisingly, instructions can be used outside of loops without any
     // exits.  This can only happen in PHI nodes if the incoming block is
     // unreachable.
     BasicBlock *BB = PN->getIncomingBlock(U);
     if (!DT->isReachableFromEntry(BB)) {
+      // No need to invalidate the safety info here: U's parent is not a part of
+      // the loop.
       U = UndefValue::get(I.getType());
       Changed = true;
       continue;
     }
 
     VisitedUsers.insert(PN);
     if (isTriviallyReplaceablePHI(*PN, I))
       continue;
if (CurLoop->contains(User))
       continue;
 
     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);
+    // Invalidation of SafetyInfo is not required because PN is outside the
+    // loop.
     PN->replaceAllUsesWith(New);
     PN->eraseFromParent();
     Changed = true;
   }
   return Changed;
 }
 
 /// When an instruction is found to only use loop invariant operands that
static void hoist(Instruction &I, const DominatorTree *DT, const Loop *CurLoop,
   // 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.
       !isGuaranteedToExecute(I, DT, CurLoop, SafetyInfo))
     I.dropUnknownNonDebugMetadata();
 
+  // Contents of a block has changed, we need to mark it in safety info.
+  SafetyInfo->dropCachedInfo(I.getParent());
   // 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?
bool llvm::promoteLoopAccessesToScalars(
     LoopInfo *LI, DominatorTree *DT, const TargetLibraryInfo *TLI,
     Loop *CurLoop, AliasSetTracker *CurAST, LoopSafetyInfo *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(
   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())
     PreheaderLoad->eraseFromParent();
 
   return true;
 }
 
 /// Returns an owning pointer to an alias set which incorporates aliasing info

lib/Transforms/Scalar/LoopIdiomRecognize.cpp

bool LoopIdiomRecognize::runOnCountableLoop() {
   LLVM_DEBUG(dbgs() << "loop-idiom Scanning: F["
                     << CurLoop->getHeader()->getParent()->getName()
                     << "] Loop %" << CurLoop->getHeader()->getName() << "\n");
 
   bool MadeChange = false;
 
   // The following transforms hoist stores/memsets into the loop pre-header.
   // Give up if the loop has instructions may throw.
-  LoopSafetyInfo SafetyInfo;
+  LoopSafetyInfo SafetyInfo(DT);
   SafetyInfo.computeLoopSafetyInfo(CurLoop);
   if (SafetyInfo.anyBlockMayThrow())
     return MadeChange;
 
   // Scan all the blocks in the loop that are not in subloops.
   for (auto *BB : CurLoop->getBlocks()) {
     // Ignore blocks in subloops.
     if (LI->getLoopFor(BB) != CurLoop)

lib/Transforms/Scalar/LoopUnswitch.cpp

class LoopUnswitch : public LoopPass {
     bool redoLoop = false;
 
     Loop *currentLoop = nullptr;
     DominatorTree *DT = nullptr;
     BasicBlock *loopHeader = nullptr;
     BasicBlock *loopPreheader = nullptr;
 
     bool SanitizeMemory;
-    LoopSafetyInfo SafetyInfo;
+    LoopSafetyInfo *SafetyInfo;
 
     // LoopBlocks contains all of the basic blocks of the loop, including the
     // preheader of the loop, the body of the loop, and the exit blocks of the
     // loop, in that order.
     std::vector<BasicBlock*> LoopBlocks;
     // NewBlocks contained cloned copy of basic blocks from LoopBlocks.
     std::vector<BasicBlock*> NewBlocks;
 
static std::pair<Value *, OperatorChain> FindLIVLoopCondition(Value *Cond,
   return {FCond, OpChain};
 }
 
 bool LoopUnswitch::runOnLoop(Loop *L, LPPassManager &LPM_Ref) {
   if (skipLoop(L))
     return false;
 
   AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(
       *L->getHeader()->getParent());
   LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
   LPM = &LPM_Ref;
   DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
+  LoopSafetyInfo LSI(DT);
+  SafetyInfo = &LSI;
   currentLoop = L;
   Function *F = currentLoop->getHeader()->getParent();
 
   SanitizeMemory = F->hasFnAttribute(Attribute::SanitizeMemory);
   if (SanitizeMemory)
-    SafetyInfo.computeLoopSafetyInfo(L);
+    SafetyInfo->computeLoopSafetyInfo(L);
 
   bool Changed = false;
   do {
     assert(currentLoop->isLCSSAForm(*DT));
     redoLoop = false;
     Changed |= processCurrentLoop();
   } while(redoLoop);
 
for (Loop::block_iterator I = currentLoop->block_begin(),
 
     // Unswitching on a potentially uninitialized predicate is not
     // MSan-friendly. Limit this to the cases when the original predicate is
     // guaranteed to execute, to avoid creating a use-of-uninitialized-value
     // in the code that did not have one.
     // This is a workaround for the discrepancy between LLVM IR and MSan
     // semantics. See PR28054 for more details.
     if (SanitizeMemory &&
-        !isGuaranteedToExecute(*TI, DT, currentLoop, &SafetyInfo))
+        !isGuaranteedToExecute(*TI, DT, currentLoop, SafetyInfo))
       continue;
 
     if (BranchInst *BI = dyn_cast<BranchInst>(TI)) {
       // Some branches may be rendered unreachable because of previous
       // unswitching.
       // Unswitch only those branches that are reachable.
       if (isUnreachableDueToPreviousUnswitching(*I))
         continue;
if (IsEqual || (isa<ConstantInt>(Val) &&
 
     for (User *U : LIC->users()) {
       Instruction *UI = dyn_cast<Instruction>(U);
       if (!UI || !L->contains(UI))
         continue;
       Worklist.push_back(UI);
     }
 
-    for (Instruction *UI : Worklist)
+    for (Instruction *UI : Worklist) {
+      SafetyInfo->dropCachedInfo(UI->getParent());
       UI->replaceUsesOfWith(LIC, Replacement);
+    }
 
     SimplifyCode(Worklist, L);
     return;
   }
 
   // Otherwise, we don't know the precise value of LIC, but we do know that it
   // is certainly NOT "Val".  As such, simplify any uses in the loop that we
   // can.  This case occurs when we unswitch switch statements.
for (User *U : LIC->users()) {
     BasicBlock *OldSISucc = *succ_begin(NewSISucc);
     // Create an "unreachable" destination.
     BasicBlock *Abort = BasicBlock::Create(Context, "us-unreachable",
                                            Switch->getParent(),
                                            OldSISucc);
     new UnreachableInst(Context, Abort);
     // Force the new case destination to branch to the "unreachable"
     // block while maintaining a (dead) CFG edge to the old block.
+    SafetyInfo->dropCachedInfo(NewSISucc);
     NewSISucc->getTerminator()->eraseFromParent();
     BranchInst::Create(Abort, OldSISucc,
                        ConstantInt::getTrue(Context), NewSISucc);
     // Release the PHI operands for this edge.
     for (PHINode &PN : NewSISucc->phis())
       PN.setIncomingValue(PN.getBasicBlockIndex(Switch),
                           UndefValue::get(PN.getType()));
     // Tell the domtree about the new block. We don't fully update the
if (isInstructionTriviallyDead(I)) {
       LLVM_DEBUG(dbgs() << "Remove dead instruction '" << *I << "\n");
 
       // Add uses to the worklist, which may be dead now.
       for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i)
         if (Instruction *Use = dyn_cast<Instruction>(I->getOperand(i)))
           Worklist.push_back(Use);
       LPM->deleteSimpleAnalysisValue(I, L);
       RemoveFromWorklist(I, Worklist);
+      SafetyInfo->dropCachedInfo(I->getParent());
       I->eraseFromParent();
       ++NumSimplify;
       continue;
     }
 
     // See if instruction simplification can hack this up.  This is common for
     // things like "select false, X, Y" after unswitching made the condition be
     // 'false'.  TODO: update the domtree properly so we can pass it here.
     if (Value *V = SimplifyInstruction(I, DL))
       if (LI->replacementPreservesLCSSAForm(I, V)) {
+        SafetyInfo->dropCachedInfo(I->getParent());
         ReplaceUsesOfWith(I, V, Worklist, L, LPM);
         continue;
       }
 
     // Special case hacks that appear commonly in unswitched code.
     if (BranchInst *BI = dyn_cast<BranchInst>(I)) {
       if (BI->isUnconditional()) {
         // If BI's parent is the only pred of the successor, fold the two blocks
         // together.
         BasicBlock *Pred = BI->getParent();
         BasicBlock *Succ = BI->getSuccessor(0);
         BasicBlock *SinglePred = Succ->getSinglePredecessor();
         if (!SinglePred) continue;  // Nothing to do.
+        SafetyInfo->dropCachedInfo(Pred);
+        SafetyInfo->dropCachedInfo(Succ);
         assert(SinglePred == Pred && "CFG broken");
 
         LLVM_DEBUG(dbgs() << "Merging blocks: " << Pred->getName() << " <- "
                           << Succ->getName() << "\n");
 
         // Resolve any single entry PHI nodes in Succ.
         while (PHINode *PN = dyn_cast<PHINode>(Succ->begin()))
           ReplaceUsesOfWith(PN, PN->getIncomingValue(0), Worklist, L, LPM);

lib/Transforms/Utils/LoopUnrollAndJam.cpp

bool llvm::isSafeToUnrollAndJam(Loop *L, ScalarEvolution &SE, DominatorTree &DT,
   // outer loop
   if (!hasIterationCountInvariantInParent(SubLoop, SE)) {
     LLVM_DEBUG(dbgs() << "Won't unroll-and-jam; Inner loop iteration count is "
                          "not consistent on each iteration\n");
     return false;
   }
 
   // Check the loop safety info for exceptions.
-  LoopSafetyInfo LSI;
+  LoopSafetyInfo LSI(&DT);
   LSI.computeLoopSafetyInfo(L);
   if (LSI.anyBlockMayThrow()) {
     LLVM_DEBUG(dbgs() << "Won't unroll-and-jam; Something may throw\n");
     return false;
   }
 
   // We've ruled out the easy stuff and now need to check that there are no
   // interdependencies which may prevent us from moving the:

test/Analysis/MustExecute/loop-header.ll

 }
 
 define i1 @split_header(i32* noalias %p, i32 %high) {
 ; CHECK-LABEL: @split_header(
 ; CHECK-LABEL:       loop:
 ; CHECK:          %iv = phi i32 [ 0, %entry ], [ %iv.next, %next ]  ; (mustexec in: loop)
 ; CHECK:          %v = load i32, i32* %p ; (mustexec in: loop)
 ; CHECK:          br label %next ; (mustexec in: loop)
+; CHECK:          call void @maythrow_and_use(i32 %v) ; (mustexec in: loop)
 ; CHECK-NOT: mustexec
 entry:
   br label %loop
 
 loop:
   %iv = phi i32 [0, %entry], [%iv.next, %next]
   %v = load i32, i32* %p
   br label %next

 ; CHECK-LABEL: @nested
 ; CHECK-LABEL: loop:                                             ; preds = %next
 ; CHECK:         %iv = phi i32 [ 0, %entry ], [ %iv.next, %next ] ; (mustexec in: loop)
 ; CHECK:         br label %inner_loop ; (mustexec in: loop)
 ; CHECK-LABEL: inner_loop:
 ; CHECK:         %v = load i32, i32* %p ; (mustexec in: inner_loop)
 ; CHECK:         %inner.test = icmp eq i32 %v, 0  ; (mustexec in: inner_loop)
 ; CHECK:         br i1 %inner.test, label %inner_loop, label %next  ; (mustexec in: inner_loop)
+; CHECK:          call void @maythrow_and_use(i32 %v) ; (mustexec in: loop)
 ; CHECK-NOT: mustexec
 
 entry:
   br label %loop
 
 loop:
   %iv = phi i32 [0, %entry], [%iv.next, %next]
   br label %inner_loop

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
 }