[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

60

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

60

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

40

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

lib/Transforms/Utils/LoopUtils.cpp

1085

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

1085

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

58

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

1052

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

1052

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

1052

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/AliasAnalysis.h"
 #include "llvm/Analysis/EHPersonalities.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;
 
 /// \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.
+  SmallVector<Instruction *, 4> EarlyExits;
+
+  // Utility to check for dominance information with caching.
+  OrderedInstructions OI;
+
   // Used to update funclet bundle operands.
   DenseMap<BasicBlock *, ColorVector> BlockColors;
 
   LoopSafetyInfo() = default;
 };
 
 /// The RecurrenceDescriptor is used to identify recurrences variables in a
 /// loop. Reduction is a special case of recurrence that has uses of the
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 between 2
+// instructions.
+//
+//===----------------------------------------------------------------------===//
+
+#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 {
+
+class OrderedInstructions {
+  /// Used to check dominance for instructions in same basic block.
+  DenseMap<const BasicBlock *, std::unique_ptr<OrderedBasicBlock>> OBBMap;
+
+public:
+  /// Return true if first instruction dominates the second.
+  bool dominates(const Instruction *, const Instruction *,
+                 const DominatorTree *DT);
+
+  /// 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,
 
   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);
+  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 (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.push_back(&*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.push_back(&*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;
   ++NumSunk;
   Changed = true;
 
 #ifndef NDEBUG
   SmallVector<BasicBlock *, 32> ExitBlocks;
   CurLoop->getUniqueExitBlocks(ExitBlocks);
   SmallPtrSet<BasicBlock *, 32> ExitBlockSet(ExitBlocks.begin(),
                                              ExitBlocks.end());
 #endif
 
+  // The OBB for this basic block is no longer valid.
+  SafetyInfo->OI.invalidateBlock(I.getParent());
+
   // Clones of this instruction. Don't create more than one per exit block!
   SmallDenseMap<BasicBlock *, Instruction *, 32> SunkCopies;
 
   // If this instruction is only used outside of the loop, then all users are
   // PHI nodes in exit blocks due to LCSSA form. Just RAUW them with clones of
   // the instruction.
   while (!I.use_empty()) {
     Value::user_iterator UI = I.user_begin();
#endif
   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));
 
+  // The OBB for this basic block is no longer valid.
+  SafetyInfo->OI.invalidateBlock(I.getParent());
+
   // 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.

 }
 
 /// 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/Utils/CMakeLists.txt

add_llvm_library(LLVMTransformUtils
   LoopVersioning.cpp
   LowerInvoke.cpp
   LowerMemIntrinsics.cpp
   LowerSwitch.cpp
   Mem2Reg.cpp
   MetaRenamer.cpp
   ModuleUtils.cpp
   NameAnonGlobals.cpp
+  OrderedInstructions.cpp
   PredicateInfo.cpp
   PromoteMemoryToRegister.cpp
   StripGCRelocates.cpp
   SSAUpdater.cpp
   SanitizerStats.cpp
   SimplifyCFG.cpp
   SimplifyIndVar.cpp
   SimplifyInstructions.cpp

lib/Transforms/Utils/LoopUtils.cpp

 // This file defines common loop utility functions.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Transforms/Utils/LoopUtils.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/BasicAliasAnalysis.h"
 #include "llvm/Analysis/GlobalsModRef.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/IR/Dominators.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/Module.h"
 #include "llvm/IR/PatternMatch.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, DT))
+        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, so we can't hoist it.
   // 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

+//===-- OrderedInstructions.cpp - Instruction dominance function
+//-----------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file defines utility to check dominance information for 2 instructions.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Transforms/Utils/OrderedInstructions.h"
+
+using namespace llvm;
+
+#define DEBUG_TYPE "ordered-insts"
+
+bool OrderedInstructions::dominates(const Instruction *InstA,
+                                    const Instruction *InstB,
+                                    const DominatorTree *DT) {
+  const BasicBlock *IBB = InstA->getParent();
+  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_nothrow(i64 %a) nounwind
+declare void @use_nothing()
+
+; 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_nothrow(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_nothrow(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