[LICM] Introduce a finer granularity option to compute early exits.

[trentxintong]

Summary

Instead of keeping a variable indicating whether there are early exits
in the loop. We keep all the early exits. This improves LICM's ability to
move instructions out of the loop based on is-guaranteed-to-execute.

The reason i do not want to compute early exits in LIR and LoopUnswitch is that its
probably not as beneficial as in LICM and its a pain to update the SafetyInfo
in case of LoopUnswitch, i.e. instructions can get deleted.

[trentxintong]

Fix comments

[• dberlin]

include/llvm/Transforms/Utils/LoopUtils.h

62

Would it trouble you too much to move this OBBMAP into Transforms/Utils as a class called "OrderedInstructions" or something.

(IE provides a dominates call, handles calling dt->dominates if they are in different bbs, or checking ordering if they are in the same bb?)

We should encapsulate this.

I'm happy to clean up the existing users if you are willing to encapsulate it :)

[trentxintong]

include/llvm/Transforms/Utils/LoopUtils.h

62

I am thinking about that as well. I will do it

[trentxintong]

Add a dominanance check interface that uses caching for instructions within same basic block.

I do not particularly like the name. I will see whether i can come up with a better one later.

[trentxintong]

Address comments

[trentxintong]

Ping

[efriedma]

include/llvm/Transforms/Utils/OrderedInstructions.h

41

Not sure I like this constructor... easy to misuse.

lib/Transforms/Utils/LoopUtils.cpp

1086

See the FIXME below... but I guess there's another way to do this check: if Inst dominates the backedge, then it's guaranteed to execute even if the loop is infinite. A bit more general than checking that the parent is exactly the header.

[efriedma]

lib/Transforms/Utils/LoopUtils.cpp

1086

Err, wait, no, sorry, the check would be that Inst dominates the backedge, and there isn't any infinite loop between the start of the loop and the backedge. I guess just checking whether Inst is in the header is good enough for now.

[trentxintong]

Minor comment and code modifications. NFC.

[trentxintong]

Edit comments

[trentxintong]

Remove the default constructor for OrderedInstructions.

[trentxintong]

Update more comments

[efriedma]

include/llvm/Transforms/Utils/LoopUtils.h

60

Use AssertingVH here?

test/Transforms/LICM/loop-early-exits.ll

83

Could you add a testcase with a udiv after a nothrow call, to make it clear that an early exit doesn't necessarily involve unwinding?

[trentxintong]

Address comments

[trentxintong]

Fix a bug in how early exits are updated. Apparently, LICM could simplify or delete early exits,
e.g. some calls that are simplifiable, but we treat as early exit.

Build the deleteExit interface for the early exit to be updated. EarlyExits are now kept in a DenseSet
which means iterating over is not deterministic. But this is ok as we need to make sure the interested
instruction dominates ALL.

The test case which the bug is uncovered is Transforms/LICM/pr32129.ll.

[efriedma]

AssertingVH catching a bug. Cool. :)

Some places you're adding calls to invalidateBlock; other places you're calling deleteExit. Why do we need to call one, but not the other, in LICM?

[trentxintong]

Address comments by reworking when SafetyInfo->deleteExit and
SafetyInfo->OrderInstruction.invalidateBlock are called.

The general rule to update OrderedInstruction and EarlyExits in SafetyInfo is as
follow: Before we delete an instruction in the loop, we invalidate the OrderedInstruction
for the block it is in, as OrderedInstruction may still hold pointer to the instruction.
In addition, we check whether it is an early exit. If it is, we remove it from the
early exit list.

We can delete instructions in the loop for various reasons in LICM including : instruction
is simplified and removed, instruction is sunk out of the loop and instruction is
hoisted out of the loop.

[trentxintong]

Minor cosmetic change

[trentxintong]

Minor assert fix

[trentxintong]

Minor change in OrderedInstruction invalidation.

[trentxintong]

Hmm ... last version did not compile. This should be good now.

To reiterate:

The general rule to update OrderedInstruction and EarlyExits in SafetyInfo is as
follow: Before we delete an instruction in the loop, we invalidate the OrderedInstruction
for the block it is in, as OrderedInstruction may still hold pointer to the instruction.

In case we move an instruction, i.e. hoisting, we invalidate the block it is moved to as well.

Additionally, we check whether it is an early exit. If it is, we remove it from the
early exit list.

We can delete instructions in the loop for various reasons in LICM including : instruction
is simplified and removed, instruction is sunk out of the loop and instruction is
hoisted out of the loop.

[trentxintong]

@efriedma can you please finish the review when you have time ? Thanks !

[trentxintong]

Ping. Thanks!

[efriedma]

LGTM.

As a followup to this, could you look into make OrderedInstructions and OrderedBasicBlock use AssertingVH, to try and catch mistakes?

[efriedma]

lib/Transforms/Utils/LoopUtils.cpp

1053

Actually, one more issue we probably need to address.

This is potentially linear in the number of calls in the loop, since we don't try to prune EarlyExits at all. This makes LICM potentially O(n^2) overall. Can we store this information in some more efficient way?

[trentxintong]

lib/Transforms/Utils/LoopUtils.cpp

1053

We could certainly prune the early exits by discovering them walking the dominator tree. If an instruction dominates an early exit (Inst A), it certainly dominates all the other early exits dominated by Inst A. So we do not need to include those early exits in the list.

The drawback with this is that if an early exit is deleted, which is possible but unlikely. We need to invalidate the early exit list (we could try to recompute everything, but probably not worth it).

By doing this, we potentially save a lot of OI.dominates checks. Worst case is still O(n^2) in case of a loop with many basic blocks that do not dominate each other and each one of them have early exits ... but this happens infrequently in practice IMO.

[efriedma]

Thinking about it a bit more, instead of storing a list of instructions which can exit the loop early, you could store a list of basic blocks which are guaranteed to execute, and a mapping from those basic blocks to the first instruction in each basic block which could exit early. That would allow "constant-time" lookups, at the expense of a bit more computation upfront.

I agree it doesn't make sense to try to recompute if an early exit is erased; that should be very rare. (Granted, it might be a little bit more common than it should be: it looks like isGuaranteedToTransferExecutionToSuccessor is missing a few important cases which isInstructionTriviallyDead catches.)

[trentxintong]

In D32720#794481, @efriedma wrote:

Thinking about it a bit more, instead of storing a list of instructions which can exit the loop early, you could store a list of basic blocks which are guaranteed to execute, and a mapping from those basic blocks to the first instruction in each basic block which could exit early. That would allow "constant-time" lookups, at the expense of a bit more computation upfront.

I agree it doesn't make sense to try to recompute if an early exit is erased; that should be very rare. (Granted, it might be a little bit more common than it should be: it looks like isGuaranteedToTransferExecutionToSuccessor is missing a few important cases which isInstructionTriviallyDead catches.)

I think thats a good idea. We need to walk the DT and keep pushing the blocks that are guaranteed to execute into a list. When we hit an early exit instruction, we do not need to process its children on the DT, and we keep a pointer to the instruction.

This way, we only need to lookup this DenseSet of basic blocks and possibly do some fiddling with basic blocks that are partially guaranteed to execute.

[• dberlin]

lib/Transforms/Utils/LoopUtils.cpp

1053

Unless i'm misunderstanding, and maybe i am (!), I believe this can be made optimal:

Here's the normal way:

The ordering is completely described by the DFS in/out numbers of the dom tree + local numbers.

It should completely suffice to, instead of just ordering the in/out of the DT nodes, model in/out of the entire block.

IE

Count = 0
number(root of DT)

number(DTNode):
   In = Count
   for each DT child:
     number(child)
    for each instruction in this block
      InstNum[I] = ++Count
   Out = Count

(or something similar)

The early exits you dominate is, in the same block, any early exit with a number greater than yours, and for other blocks, any block with an in > your in and out < your out.

This is trivially stored in a sorted smallvector.

You dominate all the early exits only if using the above comparator, lower bound says you would appear first in the smallvector.

I believe you can get away with a lot less, but not positive ATM:

By definition, anything that dominates all the early exits must be in a block that has a DT level number <= than all of them.

If all the exits are terminators, than you don't need the local numbering or DFS numbering at all, i think (I rely on Eli to point out any flaw in my reasoning, since i'm dashing this off pretty quickly).

You just need the entries with the lowest DT level (in case they are siblings in the dominator tree)

Then it would just be:

if DT level number < lowest DT level number of an exit, you dominate all exits
if DT level number == lowest DT level number then:
   if vector.size() == 1 && exit block == instruction block 
    you dominate all exits
   else
    you do not (because there must be a sibling you don't dominate)

I think one or the other of the above should work.

The DT level numbers are now available in the DomTree :)

[• dberlin]

Actually, that won't entirely work without the DFS numbers.
You can shortcut the false cases using the level numbers (IE it's not possible for Inst to have level number 5, an early exit have level number 3, and you dominate it), but you still need to know what part of the dom tree you are in.

So you still have to store and stabbing query the dom tree node DFS intervals.

[trentxintong]

Thanks for the suggestions and review so far. I am in middle of a project. I will put this on hold for a couple of weeks and will come back to it.

[hiraditya]

FYI, all the tests in this patch are already handled with the current licm. Do we still need this patch?

$ opt -S -licm loop-early-exits.ll

; ModuleID = 'licm.ll'
source_filename = "licm.ll"

declare void @use(i64)

declare void @use_nothing()

; Function Attrs: nounwind
declare void @call_nothrow() #0

define void @throw_header1(i64 %x, i64 %y, i1* %cond) {
entry:
  %div = udiv i64 %x, %y
  br label %loop

loop:                                             ; preds = %loop, %entry
  call void @use(i64 %div)
  br label %loop
}

define void @throw_header2(i64 %x, i64 %y, i1* %cond) {
entry:
  br label %loop

loop:                                             ; preds = %loop, %entry
  call void @use_nothing()
  %div = udiv i64 %x, %y
  call void @use(i64 %div)
  br label %loop
}

define void @throw_body1(i64 %x, i64 %y, i1* %cond) {
entry:
  %div = udiv i64 %x, %y
  br label %loop

loop:                                             ; preds = %body, %entry
  br label %body

body:                                             ; preds = %loop
  call void @use(i64 %div)
  br i1 false, label %loop, label %exit

exit:                                             ; preds = %body
  ret void
}

define void @throw_body2(i64 %x, i64 %y, i1* %cond) {
entry:
  br label %loop

loop:                                             ; preds = %body, %entry
  br label %body

body:                                             ; preds = %loop
  call void @use_nothing()
  %div = udiv i64 %x, %y
  call void @use(i64 %div)
  br i1 false, label %loop, label %exit

exit:                                             ; preds = %body
  ret void
}

define void @throw_body3(i64 %x, i64 %y, i1* %cond) {
entry:
  br label %loop

loop:                                             ; preds = %body, %entry
  br label %body

body:                                             ; preds = %loop
  call void @call_nothrow()
  %div = udiv i64 %x, %y
  call void @use(i64 %div)
  br i1 false, label %loop, label %exit

exit:                                             ; preds = %body
  ret void
}

attributes #0 = { nounwind }

include/llvm/Transforms/Utils/LoopUtils.h

 #include "llvm/Analysis/EHPersonalities.h"
 #include "llvm/Analysis/TargetTransformInfo.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/IRBuilder.h"
 #include "llvm/IR/InstrTypes.h"
 #include "llvm/IR/Operator.h"
 #include "llvm/IR/ValueHandle.h"
 #include "llvm/Support/Casting.h"
+#include "llvm/Transforms/Utils/OrderedInstructions.h"
 
 namespace llvm {
 
 class AliasSet;
 class AliasSetTracker;
 class BasicBlock;
 class DataLayout;
 class Loop;
 class LoopInfo;
 class OptimizationRemarkEmitter;
 class PredicatedScalarEvolution;
 class PredIteratorCache;
 class ScalarEvolution;
 class SCEV;
 class TargetLibraryInfo;
 class TargetTransformInfo;
 
 /// \brief Captures loop safety information.
 /// It keep information for loop & its header may throw exception.
 struct LoopSafetyInfo {
   bool MayThrow = false;       // The current loop contains an instruction which
                                // may throw.
   bool HeaderMayThrow = false; // Same as previous, but specific to loop header
+
+  // Whether we have computed all the early exits.
+  bool ComputedEarlyExits = false;
+  // The early exits in the loop, excluding loop exits.
+  // These are calls that might throw, infinite loop, etc.
+  DenseSet<AssertingVH<Instruction>> EarlyExits;
+
+  // Utility to check for dominance information with caching.
+  OrderedInstructions OI;
+
   // Used to update funclet bundle operands.
   DenseMap<BasicBlock *, ColorVector> BlockColors;
 
-  LoopSafetyInfo() = default;
+  // Delete the specified early exit. This can happen if the early exit
+  // is removed from the loop.
+  void deleteExit(Instruction *E) { EarlyExits.erase(E); }
+
+  // Return true if this instruction is an early exit, false otherwise.
+  bool isExit(Instruction *E) { return EarlyExits.count(E); }
+
+  // Constructor.
+  LoopSafetyInfo(DominatorTree *DT) : OI(DT) {}
 };
 
 /// The RecurrenceDescriptor is used to identify recurrences variables in a
 /// loop. Reduction is a special case of recurrence that has uses of the
 /// recurrence variable outside the loop. The method isReductionPHI identifies
 /// reductions that are basic recurrences.
 ///
 /// Basic recurrences are defined as the summation, product, OR, AND, XOR, min,
bool promoteLoopAccessesToScalars(AliasSet &, SmallVectorImpl<BasicBlock *> &,
                                   DominatorTree *, const TargetLibraryInfo *,
                                   Loop *, AliasSetTracker *, LoopSafetyInfo *,
                                   OptimizationRemarkEmitter *);
 
 /// \brief 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.
-void computeLoopSafetyInfo(LoopSafetyInfo *, Loop *);
+/// In case ComputeEarlyExits is true, all the early exit points are recorded.
+void computeLoopSafetyInfo(LoopSafetyInfo *, Loop *,
+                           bool ComputeEarlyExits = false);
 
 /// Returns true if the instruction in a loop is guaranteed to execute at least
 /// once.
 bool isGuaranteedToExecute(const Instruction &Inst, const DominatorTree *DT,
-                           const Loop *CurLoop,
-                           const LoopSafetyInfo *SafetyInfo);
+                           const Loop *CurLoop, LoopSafetyInfo *SafetyInfo);
 
 /// \brief Returns the instructions that use values defined in the loop.
 SmallVector<Instruction *, 8> findDefsUsedOutsideOfLoop(Loop *L);
 
 /// \brief Find string metadata for loop
 ///
 /// If it has a value (e.g. {"llvm.distribute", 1} return the value as an
 /// operand or null otherwise.  If the string metadata is not found return

include/llvm/Transforms/Utils/OrderedInstructions.h

 //===- llvm/Transforms/Utils/OrderedInstructions.h -------------*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // This file defines an efficient way to check for dominance relation between 2
 // instructions.
 //
-// This interface dispatches to appropriate dominance check given 2
-// instructions, i.e. in case the instructions are in the same basic block,
-// OrderedBasicBlock (with instruction numbering and caching) are used.
-// Otherwise, dominator tree is used.
-//
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_TRANSFORMS_UTILS_ORDEREDINSTRUCTIONS_H
 #define LLVM_TRANSFORMS_UTILS_ORDEREDINSTRUCTIONS_H
 
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/Analysis/OrderedBasicBlock.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/Operator.h"
 
 namespace llvm {
 
+/// This interface dispatches to appropriate dominance check given 2
+/// instructions, i.e. in case the instructions are in the same basic block,
+/// OrderedBasicBlock (with instruction numbering and caching) are used.
+/// Otherwise, dominator tree is used. This interface relies on the
+/// transformations to invalidate the basic blocks in case instructions in it
+/// are changed.
 class OrderedInstructions {
   /// Used to check dominance for instructions in same basic block.
   mutable DenseMap<const BasicBlock *, std::unique_ptr<OrderedBasicBlock>>
       OBBMap;
 
   /// The dominator tree of the parent function.
   DominatorTree *DT;
 
 public:
   /// Constructor.
   OrderedInstructions(DominatorTree *DT) : DT(DT) {}
 
   /// Return true if first instruction dominates the second.
   bool dominates(const Instruction *, const Instruction *) const;
 
   /// Invalidate the OrderedBasicBlock cache when its basic block changes.
   void invalidateBlock(BasicBlock *BB) { OBBMap.erase(BB); }
 };
 
 } // end namespace llvm
 
 #endif // LLVM_TRANSFORMS_UTILS_ORDEREDINSTRUCTIONS_H

lib/Transforms/Scalar/LICM.cpp

static cl::opt<uint32_t> MaxNumUsesTraversed(
     "licm-max-num-uses-traversed", cl::Hidden, cl::init(8),
     cl::desc("Max num uses visited for identifying load "
              "invariance in loop using invariant start (default = 8)"));
 
 static bool inSubLoop(BasicBlock *BB, Loop *CurLoop, LoopInfo *LI);
 static bool isNotUsedInLoop(const Instruction &I, const Loop *CurLoop,
                             const LoopSafetyInfo *SafetyInfo);
 static bool hoist(Instruction &I, const DominatorTree *DT, const Loop *CurLoop,
-                  const LoopSafetyInfo *SafetyInfo,
-                  OptimizationRemarkEmitter *ORE);
+                  LoopSafetyInfo *SafetyInfo, OptimizationRemarkEmitter *ORE);
 static bool sink(Instruction &I, const LoopInfo *LI, const DominatorTree *DT,
                  const Loop *CurLoop, AliasSetTracker *CurAST,
-                 const LoopSafetyInfo *SafetyInfo,
-                 OptimizationRemarkEmitter *ORE);
+                 LoopSafetyInfo *SafetyInfo, OptimizationRemarkEmitter *ORE);
 static bool isSafeToExecuteUnconditionally(Instruction &Inst,
                                            const DominatorTree *DT,
                                            const Loop *CurLoop,
-                                           const LoopSafetyInfo *SafetyInfo,
+                                           LoopSafetyInfo *SafetyInfo,
                                            OptimizationRemarkEmitter *ORE,
                                            const Instruction *CtxI = nullptr);
 static bool pointerInvalidatedByLoop(Value *V, uint64_t Size,
                                      const AAMDNodes &AAInfo,
                                      AliasSetTracker *CurAST);
 static Instruction *
 CloneInstructionInExitBlock(Instruction &I, BasicBlock &ExitBlock, PHINode &PN,
                             const LoopInfo *LI,
bool LoopInvariantCodeMotion::runOnLoop(Loop *L, AliasAnalysis *AA,
 
   assert(L->isLCSSAForm(*DT) && "Loop is not in LCSSA form.");
 
   AliasSetTracker *CurAST = collectAliasInfoForLoop(L, LI, AA);
 
   // Get the preheader block to move instructions into...
   BasicBlock *Preheader = L->getLoopPreheader();
 
-  // Compute loop safety information.
-  LoopSafetyInfo SafetyInfo;
-  computeLoopSafetyInfo(&SafetyInfo, L);
+  // Compute loop safety information. Along with all the early exits.
+  LoopSafetyInfo SafetyInfo(DT);
+  computeLoopSafetyInfo(&SafetyInfo, L, true);
 
   // We want to visit all of the instructions in this loop... that are not parts
   // of our subloops (they have already had their invariants hoisted out of
   // their loop, into this loop, so there is no need to process the BODIES of
   // the subloops).
   //
   // Traverse the body of the loop in depth first order on the dominator tree so
   // that we are guaranteed to see definitions before we see uses.  This allows
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)) {
       DEBUG(dbgs() << "LICM deleting dead inst: " << I << '\n');
       ++II;
       CurAST->deleteValue(&I);
+      // We could have treated this instruction as an early exit, update the
+      // early exit list.
+      SafetyInfo->deleteExit(&I);
+      // The ordered instruction list for this block is no longer valid.
+      SafetyInfo->OI.invalidateBlock(I.getParent());
       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
for (BasicBlock::iterator II = BB->begin(), E = BB->end(); II != E;) {
       // fold it.
       if (Constant *C = ConstantFoldInstruction(
               &I, I.getModule()->getDataLayout(), TLI)) {
         DEBUG(dbgs() << "LICM folding inst: " << I << "  --> " << *C << '\n');
         CurAST->copyValue(&I, C);
         I.replaceAllUsesWith(C);
         if (isInstructionTriviallyDead(&I, TLI)) {
           CurAST->deleteValue(&I);
+          // We could have treated this instruction as an early exit, update the
+          // early exit list.
+          SafetyInfo->deleteExit(&I);
+          // The ordered instruction list for this block is no longer valid.
+          SafetyInfo->OI.invalidateBlock(I.getParent());
           I.eraseFromParent();
         }
         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()) {
         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);
+        // The ordered instruction list for this block is no longer valid.
+        SafetyInfo->OI.invalidateBlock(I.getParent());
+        // We do not update the early exit list here, i.e. how can we treat this
+        // instruction as an early exit ?
+        assert(!SafetyInfo->isExit(&I) && "Invalid early exit");
         I.eraseFromParent();
 
         hoist(*ReciprocalDivisor, DT, CurLoop, SafetyInfo, ORE);
         Changed = true;
         continue;
       }
 
       // Try hoisting the instruction out to the preheader.  We can only do this
for (DomTreeNode *Child : Children)
     Changed |=
         hoistRegion(Child, AA, LI, DT, TLI, CurLoop, CurAST, SafetyInfo, ORE);
   return Changed;
 }
 
 /// Computes loop safety information, checks loop body & header
 /// for the possibility of may throw exception.
 ///
-void llvm::computeLoopSafetyInfo(LoopSafetyInfo *SafetyInfo, Loop *CurLoop) {
+void llvm::computeLoopSafetyInfo(LoopSafetyInfo *SafetyInfo, Loop *CurLoop,
+                                 bool ComputeEarlyExits) {
   assert(CurLoop != nullptr && "CurLoop cant be null");
   BasicBlock *Header = CurLoop->getHeader();
   // Setting default safety values.
   SafetyInfo->MayThrow = false;
   SafetyInfo->HeaderMayThrow = false;
+  SafetyInfo->EarlyExits.clear();
+  SafetyInfo->ComputedEarlyExits = ComputeEarlyExits;
   // Iterate over header and compute safety info.
-  for (BasicBlock::iterator I = Header->begin(), E = Header->end();
-       (I != E) && !SafetyInfo->HeaderMayThrow; ++I)
-    SafetyInfo->HeaderMayThrow |=
-        !isGuaranteedToTransferExecutionToSuccessor(&*I);
+  for (BasicBlock::iterator I = Header->begin(), E = Header->end(); I != E;
+       ++I) {
+    bool MayThrow = !isGuaranteedToTransferExecutionToSuccessor(&*I);
+    SafetyInfo->HeaderMayThrow |= MayThrow;
+    // Exit as soon as we find an instruction that may throw in case we are
+    // not computing early exits.
+    if (!ComputeEarlyExits && SafetyInfo->HeaderMayThrow)
+      break;
+    if (MayThrow)
+      SafetyInfo->EarlyExits.insert(&*I);
+  }
 
   SafetyInfo->MayThrow = SafetyInfo->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) && !SafetyInfo->MayThrow; ++BB)
-    for (BasicBlock::iterator I = (*BB)->begin(), E = (*BB)->end();
-         (I != E) && !SafetyInfo->MayThrow; ++I)
-      SafetyInfo->MayThrow |= !isGuaranteedToTransferExecutionToSuccessor(&*I);
+       BB != BBE; ++BB)
+    for (BasicBlock::iterator I = (*BB)->begin(), E = (*BB)->end(); I != E;
+         ++I) {
+      bool MayThrow = !isGuaranteedToTransferExecutionToSuccessor(&*I);
+      SafetyInfo->MayThrow |= MayThrow;
+      // Exit as soon as we find an instruction that may throw in case we are
+      // not computing early exits.
+      if (!ComputeEarlyExits && SafetyInfo->MayThrow)
+        break;
+      if (MayThrow)
+        SafetyInfo->EarlyExits.insert(&*I);
+    }
 
   // 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 (isFuncletEHPersonality(classifyEHPersonality(PersonalityFn)))
         SafetyInfo->BlockColors = colorEHFunclets(*Fn);

 
 /// 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, const LoopInfo *LI, const DominatorTree *DT,
                  const Loop *CurLoop, AliasSetTracker *CurAST,
-                 const LoopSafetyInfo *SafetyInfo,
-                 OptimizationRemarkEmitter *ORE) {
+                 LoopSafetyInfo *SafetyInfo, OptimizationRemarkEmitter *ORE) {
   DEBUG(dbgs() << "LICM sinking instruction: " << I << "\n");
   ORE->emit(OptimizationRemark(DEBUG_TYPE, "InstSunk", &I)
             << "sinking " << ore::NV("Inst", &I));
   bool Changed = false;
   if (isa<LoadInst>(I))
     ++NumMovedLoads;
   else if (isa<CallInst>(I))
     ++NumMovedCalls;
while (!I.use_empty()) {
     Instruction *New;
     auto It = SunkCopies.find(ExitBlock);
     if (It != SunkCopies.end())
       New = It->second;
     else
       New = SunkCopies[ExitBlock] =
           CloneInstructionInExitBlock(I, *ExitBlock, *PN, LI, SafetyInfo);
 
+    // The ordered instruction list for this block is no longer valid.
+    SafetyInfo->OI.invalidateBlock(PN->getParent());
     PN->replaceAllUsesWith(New);
     PN->eraseFromParent();
   }
 
+
+  // We could have treated this instruction as an early exit, update the
+  // early exit list.
+  SafetyInfo->deleteExit(&I);
+  // The ordered instruction list for this block is no longer valid.
+  SafetyInfo->OI.invalidateBlock(I.getParent());
   CurAST->deleteValue(&I);
   I.eraseFromParent();
   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 bool hoist(Instruction &I, const DominatorTree *DT, const Loop *CurLoop,
-                  const LoopSafetyInfo *SafetyInfo,
-                  OptimizationRemarkEmitter *ORE) {
+                  LoopSafetyInfo *SafetyInfo, OptimizationRemarkEmitter *ORE) {
   auto *Preheader = CurLoop->getLoopPreheader();
   DEBUG(dbgs() << "LICM hoisting to " << Preheader->getName() << ": " << I
                << "\n");
   ORE->emit(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.
       !isGuaranteedToExecute(I, DT, CurLoop, SafetyInfo))
     I.dropUnknownNonDebugMetadata();
 
+  // We could have treated this instruction as an early exit, update the
+  // early exit list.
+  SafetyInfo->deleteExit(&I);
+  // The ordered instruction list for this block is no longer valid.
+  SafetyInfo->OI.invalidateBlock(Preheader);
+  SafetyInfo->OI.invalidateBlock(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?

 }
 
 /// Only sink or hoist an instruction if it is not a trapping instruction,
 /// or if the instruction is known not to trap when moved to the preheader.
 /// or if it is a trapping instruction and is guaranteed to execute.
 static bool isSafeToExecuteUnconditionally(Instruction &Inst,
                                            const DominatorTree *DT,
                                            const Loop *CurLoop,
-                                           const LoopSafetyInfo *SafetyInfo,
+                                           LoopSafetyInfo *SafetyInfo,
                                            OptimizationRemarkEmitter *ORE,
                                            const Instruction *CtxI) {
   if (isSafeToSpeculativelyExecute(&Inst, CtxI, DT))
     return true;
 
   bool GuaranteedToExecute =
       isGuaranteedToExecute(Inst, DT, CurLoop, SafetyInfo);
 

lib/Transforms/Scalar/LoopIdiomRecognize.cpp

bool LoopIdiomRecognize::runOnCountableLoop() {
   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);
   computeLoopSafetyInfo(&SafetyInfo, CurLoop);
   if (SafetyInfo.MayThrow)
     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;
 
     Loop *currentLoop;
     DominatorTree *DT;
     BasicBlock *loopHeader;
     BasicBlock *loopPreheader;
 
     bool SanitizeMemory;
-    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;
 
     bool hasBranchDivergence;
 
   public:
     static char ID; // Pass ID, replacement for typeid
     explicit LoopUnswitch(bool Os = false, bool hasBranchDivergence = false) :
       LoopPass(ID), OptimizeForSize(Os), redoLoop(false),
       currentLoop(nullptr), DT(nullptr), loopHeader(nullptr),
       loopPreheader(nullptr), hasBranchDivergence(hasBranchDivergence) {
         initializeLoopUnswitchPass(*PassRegistry::getPassRegistry());
       }
 
     bool runOnLoop(Loop *L, LPPassManager &LPM) override;
-    bool processCurrentLoop();
+    bool processCurrentLoop(LoopSafetyInfo *SafetyInfo);
     bool isUnreachableDueToPreviousUnswitching(BasicBlock *);
     /// This transformation requires natural loop information & requires that
     /// loop preheaders be inserted into the CFG.
     ///
     void getAnalysisUsage(AnalysisUsage &AU) const override {
       AU.addRequired<AssumptionCacheTracker>();
       AU.addRequired<TargetTransformInfoWrapperPass>();
       if (hasBranchDivergence)
AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(
       *L->getHeader()->getParent());
   LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
   LPM = &LPM_Ref;
   DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
   currentLoop = L;
   Function *F = currentLoop->getHeader()->getParent();
 
   SanitizeMemory = F->hasFnAttribute(Attribute::SanitizeMemory);
+  LoopSafetyInfo SafetyInfo(DT);
   if (SanitizeMemory)
     computeLoopSafetyInfo(&SafetyInfo, L);
 
   bool Changed = false;
   do {
     assert(currentLoop->isLCSSAForm(*DT));
     redoLoop = false;
-    Changed |= processCurrentLoop();
+    Changed |= processCurrentLoop(&SafetyInfo);
   } while(redoLoop);
 
   // FIXME: Reconstruct dom info, because it is not preserved properly.
   if (Changed)
     DT->recalculate(*F);
   return Changed;
 }
 
while (currentLoop->contains(DomBB)) {
 
     if (DT->dominates(UnreachableSucc, BB))
       return true;
   }
   return false;
 }
 
 /// Do actual work and unswitch loop if possible and profitable.
-bool LoopUnswitch::processCurrentLoop() {
+bool LoopUnswitch::processCurrentLoop(LoopSafetyInfo *SafetyInfo) {
   bool Changed = false;
 
   initLoopData();
 
   // If LoopSimplify was unable to form a preheader, don't do any unswitching.
   if (!loopPreheader)
     return false;
 
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;

lib/Transforms/Utils/LoopUtils.cpp

 //===----------------------------------------------------------------------===//
 
 #include "llvm/Transforms/Utils/LoopUtils.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/BasicAliasAnalysis.h"
 #include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/LoopPass.h"
+#include "llvm/Analysis/OrderedBasicBlock.h"
 #include "llvm/Analysis/ScalarEvolution.h"
 #include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"
 #include "llvm/Analysis/ScalarEvolutionExpander.h"
 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
 #include "llvm/Analysis/TargetTransformInfo.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/Module.h"
Optional<const MDOperand *> llvm::findStringMetadataForLoop(Loop *TheLoop,
   }
   return None;
 }
 
 /// 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.
-
+                                 LoopSafetyInfo *SafetyInfo) {
+  // If we have computed early exits, use it.
+  if (SafetyInfo->ComputedEarlyExits) {
+    // Check wehther the instruction dominates all early exits. If it doesn't,
+    // then there is a path out of the loop which does not execute this
+    // instruction and its not guaranteed to execute.
+    for (Instruction *ExitInst : SafetyInfo->EarlyExits)
+      if (!SafetyInfo->OI.dominates(&Inst, ExitInst))
+        return false;
+  } else {
     // 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.
       return !SafetyInfo->HeaderMayThrow;
 
-  // Somewhere in this loop there is an instruction which may throw and make us
-  // exit the loop.
+    // Somewhere in this loop there is an instruction which may throw and make
+    // us exit the loop.
     if (SafetyInfo->MayThrow)
       return false;
+  }
 
+  // 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.
   // Get the exit blocks for the current loop.
   SmallVector<BasicBlock *, 8> ExitBlocks;
   CurLoop->getExitBlocks(ExitBlocks);
 
   // Verify that the block dominates each of the exit blocks of the loop.
   for (BasicBlock *ExitBlock : ExitBlocks)
     if (!DT->dominates(Inst.getParent(), ExitBlock))
       return false;
 
   // As a degenerate case, if the loop is statically infinite then we haven't
   // proven anything since there are no exit blocks.
-  if (ExitBlocks.empty())
+  // However, we also special case instruction from the header as the header
+  // is always guaranteed to execute.
+  if (ExitBlocks.empty() && Inst.getParent() != CurLoop->getHeader())
     return false;
 
   // FIXME: In general, we have to prove that the loop isn't an infinite loop.
   // See http::llvm.org/PR24078 .  (The "ExitBlocks.empty()" check above is
   // just a special case of this.)
   return true;
 }
 

lib/Transforms/Utils/OrderedInstructions.cpp

 #include "llvm/Transforms/Utils/OrderedInstructions.h"
 using namespace llvm;
 
 /// Given 2 instructions, use OrderedBasicBlock to check for dominance relation
 /// if the instructions are in the same basic block, Otherwise, use dominator
 /// tree.
 bool OrderedInstructions::dominates(const Instruction *InstA,
                                     const Instruction *InstB) const {
+  assert(DT && "Uninitialized dominator tree");
   const BasicBlock *IBB = InstA->getParent();
   // Use ordered basic block to do dominance check in case the 2 instructions
   // are in the same basic block.
   if (IBB == InstB->getParent()) {
     auto OBB = OBBMap.find(IBB);
     if (OBB == OBBMap.end())
       OBB = OBBMap.insert({IBB, make_unique<OrderedBasicBlock>(IBB)}).first;
     return OBB->second->dominates(InstA, InstB);
   } else {
     return DT->dominates(InstA->getParent(), InstB->getParent());
   }
 }

test/Transforms/LICM/loop-early-exits.ll

+; RUN: opt -S -licm < %s | FileCheck %s
+
+declare void @use(i64 %a)
+declare void @use_nothing()
+declare void @call_nothrow() nounwind
+
+; We can move this udiv out of the loop as it comes before 
+; the call instruction that may throw.
+define void @throw_header1(i64 %x, i64 %y, i1* %cond) {
+; CHECK-LABEL: throw_header1
+; CHECK: %div = udiv i64 %x, %y
+; CHECK-LABEL: loop
+; CHECK: call void @use(i64 %div)
+entry:
+  br label %loop
+
+loop:                                         ; preds = %entry, %for.inc
+  %div = udiv i64 %x, %y
+  call void @use(i64 %div)
+  br label %loop
+}
+
+; We can not move this udiv out of the loop as it comes after 
+; the call instruction that may throw.
+define void @throw_header2(i64 %x, i64 %y, i1* %cond) {
+; CHECK-LABEL: throw_header2
+; CHECK-LABEL: loop
+; CHECK: call void @use_nothing()
+; CHECK: %div = udiv i64 %x, %y
+entry:
+  br label %loop
+
+loop:                                         ; preds = %entry, %for.inc
+  call void @use_nothing()
+  %div = udiv i64 %x, %y
+  call void @use(i64 %div)
+  br label %loop
+}
+
+; We can move this udiv out of the loop as it comes before 
+; the call instruction that may throw.
+define void @throw_body1(i64 %x, i64 %y, i1* %cond) {
+; CHECK-LABEL: throw_body1
+; CHECK: %div = udiv i64 %x, %y
+; CHECK-LABEL: loop
+entry:
+  br label %loop
+
+loop:                                         ; preds = %entry, %for.inc
+  br label %body
+
+body:
+  %div = udiv i64 %x, %y
+  call void @use(i64 %div)
+  br i1 undef, label %loop, label %exit
+
+exit:
+  ret void
+}
+
+; We can not move this udiv out of the loop as it comes after 
+; the call instruction that may throw.
+define void @throw_body2(i64 %x, i64 %y, i1* %cond) {
+; CHECK-LABEL: throw_body2
+; CHECK-LABEL: loop
+; CHECK: call void @use_nothing()
+; CHECK: %div = udiv i64 %x, %y
+entry:
+  br label %loop
+
+loop:                                         ; preds = %entry, %for.inc
+  br label %body
+
+body:
+  call void @use_nothing()
+  %div = udiv i64 %x, %y
+  call void @use(i64 %div)
+  br i1 undef, label %loop, label %exit
+
+exit:
+  ret void
+}
+
+
+; We can not move this udiv out of the loop as it comes after 
+; the call instruction that may not transfer execution to successor, even
+; though it does not throw.
+define void @throw_body3(i64 %x, i64 %y, i1* %cond) {
+; CHECK-LABEL: throw_body3
+; CHECK-LABEL: body
+; CHECK: call void @call_nothrow()
+; CHECK: %div = udiv i64 %x, %y
+entry:
+  br label %loop
+
+loop:                                         ; preds = %entry, %for.inc
+  br label %body
+
+body:
+  call void @call_nothrow()
+  %div = udiv i64 %x, %y
+  call void @use(i64 %div)
+  br i1 undef, label %loop, label %exit
+
+exit:
+  ret void
+}

test/Transforms/LICM/preheader-safe.ll

 loop:                                         ; preds = %entry, %for.inc
   %div = udiv i64 %x, %y
   br label %loop2
 
 loop2:
   call void @use_nothrow(i64 %div)
   br label %loop
 }
-; Negative test
-define void @throw_header(i64 %x, i64 %y, i1* %cond) {
-; CHECK-LABEL: throw_header
-; CHECK-LABEL: loop
-; CHECK: %div = udiv i64 %x, %y
-; CHECK: call void @use(i64 %div)
-entry:
-  br label %loop
-
-loop:                                         ; preds = %entry, %for.inc
-  %div = udiv i64 %x, %y
-  call void @use(i64 %div)
-  br label %loop
-}
 
 ; The header is known no throw, but the loop is not.  We can
 ; still lift out of the header.
 define void @nothrow_header(i64 %x, i64 %y, i1 %cond) {
 ; CHECK-LABEL: nothrow_header
 ; CHECK-LABEL: entry
 ; CHECK: %div = udiv i64 %x, %y
 ; CHECK-LABEL: loop