[LICM] Sink entire inner loops.

[chrisdiamand_arm]

Summary

[LICM] Sink entire inner loops.

Currently, LICM can only move individual instructions. However, inner
loops can also be moved: If the outputs of a loop, (which are just
the phi nodes in the exit block, thanks to LCSSA form) are not used
in the outer loop, it can be sunk.

This patch teaches the LICM pass to sink an entire inner loop to the
exit block of its parent loop.

[jmolloy]

Hi Chris,

Thanks for working on this! This is a very impressively written patch. Most of my comments are to do with coding style and using more of LLVM's frameworks to avoid using helper functions.

Cheers,

James

test/Analysis/ScalarEvolution/2012-03-26-LoadConstant.ll

1

Why have these orders changed?

test/Transforms/LICM/inner-loop-dont-sink.ll

5

We generally only use CHECK-LABEL: for delineating between multiple testcases. Its only purpose is to stop llvm-lit running from one testcase to another.

As you've only got one testcase here, you should just use CHECK:.

[jmolloy]

include/llvm/Analysis/LoopInfo.h

369

This is a very public header, so please add good doxygen comments.

lib/Transforms/Scalar/LICM.cpp

331

don't need to check PN here because the loop condition has already checked it.

344

s/BB->getInstList()/*BB/

345

instead of !dyn_cast, use !isa<PHINode>().

383

s/TODO/FIXME/

392

Same comment as above: use isa<> instead of dyn_cast<> here if you're not using the result.

409

I'd rename this "replaceSuccessorIf", which implies the predicate. Functions that take predicates are also nicer to call if the predicate is last (it makes formatting a lambda easier).

Actually, I'd call it "replaceFirstSuccessorIf", as it doesn't replace multiple successors.

412

Capital "I" is the convention.

461

Single-line if statements should have their braces elided.

468

You should never need to directly modify InstList. Instead, just do:

PN->moveBefore(NewExitBlock->getTerminator())

(and remove PN->removeFromParent()).

OOI, it looks like NewExitBlock doesn't have a Terminator instruction at this point. I find it's always easier to make the block well-formed (add a terminator) as soon as possible, as it makes dumps, sanity checks and insertions (like this) easier.

473

You don't need this helper function:

SubLoopPredecessor->getTerminator()->replaceUsesOfWith(SubLoopHeader, OldExitBlock);

478

for (auto *PN = OldExitBlock.begin(); isa<PHINode>(PN); ++PN)
  PN->replaceUsesOfWith(ExitingBlock, SubLoopPredecessor);

483

You can use RAUW just like in line 473 to remove the need for the helper.

487

No braces around single-line statements.

Also:

for (auto *BB : SubLoop->blocks())
  CurLoop->removeBlockFromLoop(BB);

512

Assuming you've added a dummy terminator before now to keep NewExitBlock well-formed, you can simply do:

PreheaderTerminator->moveBefore(NewExitBlock->getTerminator());
NewExitBlock->getTerminator()->eraseFromParent();

533

Algorithmically this might be easier done by first splitting the outer loop's exit block after all PHI nodes then inserting the subloop in between. (see BasicBlock::split)

596

*BB, not BB->getInstList()

659

These should be inside DEBUG() macros for release builds.

1437

I'm not sure I understand why these have been changed?

[chrisdiamand_arm]

lib/Transforms/Scalar/LICM.cpp

208

This conflicts with r260892 committed yesterday - I'll fix the merge conflicts in the next version.

659

Isn't everything in verifyLoop() wrapped in #ifndef NDEBUG anyway?

1437

The lookup() method inserts a null value into LoopToAliasSetMap when the key isn't found. This means that the assert(LoopToAliasSetMap.empty()) statement in doFinalization() fails.

find() doesn't add an entry when one doesn't already exist, so avoids this.

test/Analysis/ScalarEvolution/2012-03-26-LoadConstant.ll

1

When I first wrote it I had to switch them for some reason, but I've just tried it again and it's no longer needed. Will put them back.

[reames]

Taking a step back, can you give a motivating example on why we might want to do this? Your tests look like they'd be caught by loop-unswitch and LICM together, but I suspect that's just because the tests are (correctly) simple.

test/Transforms/LICM/inner-loop-dont-sink.ll

5

Er, this disagrees with quite a few other tests. :) Using CHECK-LABEL to ensure things are in the right basic block seems entirely reasonable to me.

[chrisdiamand_arm]

Hopefully this address all your feedback, James.

• I've completed removed the replaceSuccessor helper function, and replacePhiUses now no longer requires a predicate (as it's only used for one thing).
• It also now uses splitBasicBlock during sinking, and inserts the loop between the two parts of the original exit block. The loop over the outer loop's exit block's phi nodes is still required, although I've updated the comment to explain it more clearly.
• Style issues should be fixed.

Thanks!
Chris

[chrisdiamand_arm]

In D17203#354312, @reames wrote:

Taking a step back, can you give a motivating example on why we might want to do this? Your tests look like they'd be caught by loop-unswitch and LICM together, but I suspect that's just because the tests are (correctly) simple.

The motivation behind this is to handle things like the following:

void expensive_loop(...) {
  for (...)
    do_stuff;
}

for (int i = 0; i < big_number; ++i)
  expensive_loop(...);

I noticed that setting __attribute__((noinline)) on expensive_loop() made it run much faster. If inlining is disabled, the call to expensive_loop() can be sunk and is only run once. With inlining, the loop in expensive_loop() gets turned into a subloop, and can't be moved, so the inner loop is run big_number times. This patch would allow the inlined contents of expensive_loop() to be removed from the outer loop.

Cheers!
Chris

[mcrosier]

test/Transforms/LICM/inner-loop-dont-sink.ll

7

I tend to agree with Philip here. It also avoids issues if/when someone adds an additional test case to this file.

[chrisdiamand_arm]

test/Transforms/LICM/inner-loop-dont-sink.ll

7

Ok, I've just looked this up here:

It is treated identically to a normal CHECK directive except that FileCheck makes an additional assumption that a line matched by the directive cannot also be matched by any other check present in match-filename

So James is correct in that it shouldn't be used on every label, but that's because a label (e.g. entry) may not be unique if another test case is added. I think I need to do something like:

; CHECK-LABEL: main
; CHECK: entry:
...

...because main is a unique function name within the file, even if another test is added.
Does that sound reasonable?

[mcrosier]

test/Transforms/LICM/inner-loop-dont-sink.ll

7

Correct. You should have a CHECK-LABEL directive on main and only main. Generally, each function name within a file (which must be unique) should have an associated CHECK-LABEL.

[chrisdiamand_arm]

This adds one '; CHECK-LABEL: @main(' line to each new test.

[reames]

I'm still going over the code, but the subloop management looks highly suspect. I'm deeply suspicions that this is not interacting properly with the LoopPassManager. Good places to look for inspiration are LoopUnswitch and LoopDeletion since they both manipulate the loop nest structure.

lib/Transforms/Scalar/LICM.cpp

720

FYI, this part in particular looks really really suspect. I'm not quite sure what the right way to solve this is, but this probably isn't it. :)

[reames]

More random comments. Note that this is likely fairly far from submission in it's current form. You might want to think about options for splitting this up so that we don't get caught in a long review cycle.

lib/Transforms/Scalar/LICM.cpp

120

You'll need to enumerate which passes are preserved without this.

351

This should be checked by the caller. Possible in that helper function: isHeaderOfImmediateSubLoop?

354

Given these two sets of checks are repeated, a helper function would be good. Alternatively, is isLoopSimplifyForm sufficient?

361

Do we have any guarantee at this point that CurLoop has only one exit? If so, assert it.

379

Everywhere you have isa<BranchInst> you probably want to introduce handle all terminators except invokes.

384

This is a *really* expensive way to phrase this query. It'll be general, but slow. Can you look for an alternate way to express this for the entire loop in one go?

609

BB is already available in this scope.

613

Introducing a helper function isHeaderOfSubLoop would make this far easier to follow.

622

I don't see that your updating DT here. This is problematic since we'll be walking a stale tree.

[chrisdiamand_arm]

Hi, thanks for taking a look at this! Comments inline.

lib/Transforms/Scalar/LICM.cpp

354

isLoopSimplifyForm allows multiple exit blocks, so it's not sufficient as currently written. LICM can sink individual instructions to multiple exit blocks IIRC, but it has to duplicate the instruction for each exit block. I'm not sure we'd want to duplicate entire inner loops though?

361

Good point, this should be checked by canHoistSubLoop. I'll add an assert, too.

379

I'm not sure about this - wouldn't that allow something like an indirect branch to a function with side-effects to be hoisted?

384

I think all of this stuff has to be checked for every instruction at some point. I think some checks are redundant though - canSinkOrHoistInst actually calls isSafeToExecuteUnconditionally, so the second call is redundant, for example (I just have both because that's what the original hoisting code does).

Some of this stuff is calculated during normal single instruction hoisting/sinking, so I'll investigate if information from that can be reused somehow.

609

Good point :)

622

Ok. I'll take a look at the other passes you mentioned to see what they do about this.

720

This bit was pretty tricky, and I agree it's not ideal. Here I used LP to access LICM::deleteAnalysisSubloop, which frees the AST (maybe it looks like I'm trying to tell the LoopPassManager about the deleted loop here?). An alternative would be to make sinkRegion and hoistRegion methods of LICM.

Either way, the AST management has to change a bit, otherwise hoisted subloops' ASTs don't get freed.

[chrisdiamand_arm]

This update removes the hoisting code, in a bid to make the diff a bit more manageable.

It addresses two main issues pointed out by Philip:

• It now tells the LPPassManager about loops which have been moved.
• It recalculates the dominator tree after each pass.

There's also some other stuff, mostly factoring out various checks so they can be re-used for hoisting in a later patch.

In particular I'd welcome any comments on the dominator tree handling. My assumption here is that we don't need to update the DT in sinkRegion() (even though it's being traversed), because all the children of a subloop have already been visited by the time the sinking actually happens. One benefit of leaving out the hoisting for now is that the above assumption doesn't hold for hoisting...

Cheers!

lib/Transforms/Scalar/LICM.cpp

120

I think Chandler's recent patches to LICM et al now mean I now don't need to add anything here.

613

I'm not sure what you're after here, is it really that unclear? I've kept this check out of canSinkSubLoop() so that I can do everything after this line in terms of Loop *SubLoop instead of referring to the subloop by its header.

[chrisdiamand_arm]

This now updates the DominatorTree incrementally, rather than recalculating the whole thing at the end of runOnLoop().

[chrisdiamand_arm]

Has anyone had a chance to look at this yet?

Cheers!
Chris

[chrisdiamand_arm]

Ping. Also (I should have mentioned this earlier), I've tested this with the regression tests, the LLVM test suite, and several proprietary benchmarks.

[chrisdiamand_arm]

Ping.

[chrisdiamand_arm]

Updating the diff after rebasing on ToT (there was a conflict with some reformatting).

Has anyone got any comments on this? In particular, the interaction with the LoopPassManager, and keeping the DominatorTree up-to-date have been improved since Philip pointed those issues out.

Cheers,
Chris

[chrisdiamand_arm]

Ping. Anyone?

[chrisdiamand_arm]

Ping.

[• dberlin]

Generally looks good to me.
I can't approve it, though.

lib/Transforms/Scalar/LICM.cpp

359

Any reason to not just use the block iterator instead of converting operands to blocks repeatedly?

374

Please add a message

394

The number of times you do this makes me wonder if we shouldn't just have a phi_iterator for the basic block.

421

Do we really have no branch redirect utility that does this?
(I thought we did have one that did this and also updated dominators)

[chrisdiamand_arm]

Replies inline - cheers!

lib/Transforms/Scalar/LICM.cpp

359

Yep - the index is required for setIncomingBlock anyway, so I thought it seemed cleaner to use it throughout instead of mixing indices and iterators.

394

That would be extremely useful, I think there are 4 here. Probably outside the scope of this patch though...

421

Not that I can find, through lots of recursive grepping. This particular code is quite specific to LICM (or at least loop transformations) anyway - it has to redirect only the branches which point outside the subloop. Are there any other passes which replace loop exit blocks that could benefit from this being factored out?

[chrisdiamand_arm]

Add messages to assertions.

[chrisdiamand_arm]

Rebase and fix conflicts with renaming 'LICMSafetyInfo' to 'LoopSafetyInfo'. Also ping :)

[chrisdiamand_arm]

Hi - does anyone have any thoughts on this?

[sanjoy]

Inactive, as far as I can tell.

include/llvm/Analysis/LoopInfo.h

 
   /// Return true if the specified value is loop invariant.
   bool isLoopInvariant(const Value *V) const;
 
   /// Return true if all the operands of the specified instruction are loop
   /// invariant.
   bool hasLoopInvariantOperands(const Instruction *I) const;
 
+  bool isLoopInvariantOutsideSubLoop(const Value *V,
+                                     const Loop *Sub) const;
+
+  bool hasLoopInvariantOperandsOutsideSubLoop(const Instruction *I,
+                                              const Loop *Sub) const;
+
   /// If the given value is an instruction inside of the loop and it can be
   /// hoisted, do so to make it trivially loop-invariant.
   /// Return true if the value after any hoisting is loop invariant. This
   /// function can be used as a slightly more aggressive replacement for
   /// isLoopInvariant.
   ///
   /// If InsertPt is specified, it is the point to hoist instructions to.
   /// If null, the terminator of the loop preheader is used.

include/llvm/Transforms/Utils/LoopUtils.h

 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_TRANSFORMS_UTILS_LOOPUTILS_H
 #define LLVM_TRANSFORMS_UTILS_LOOPUTILS_H
 
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/EHPersonalities.h"
+#include "llvm/Analysis/LoopPass.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/IRBuilder.h"
 
 namespace llvm {
 class AliasSet;
 class AliasSetTracker;
 class AssumptionCache;
 class BasicBlock;

 /// reverse depth first order w.r.t the DominatorTree. This allows us to visit
 /// uses before definitions, allowing us to sink a loop body in one pass without
 /// iteration. Takes DomTreeNode, AliasAnalysis, LoopInfo, DominatorTree,
 /// DataLayout, TargetLibraryInfo, Loop, AliasSet information for all
 /// instructions of the loop and loop safety information as arguments.
 /// It returns changed status.
 bool sinkRegion(DomTreeNode *, AliasAnalysis *, LoopInfo *, DominatorTree *,
                 TargetLibraryInfo *, Loop *, AliasSetTracker *,
-                LICMSafetyInfo *);
+                LICMSafetyInfo *, LoopPass *);
 
 /// \brief Walk the specified region of the CFG (defined by all blocks
 /// dominated by the specified block, and that are in the current loop) in depth
 /// first order w.r.t the DominatorTree.  This allows us to visit definitions
 /// before uses, allowing us to hoist a loop body in one pass without iteration.
 /// Takes DomTreeNode, AliasAnalysis, LoopInfo, DominatorTree, DataLayout,
 /// TargetLibraryInfo, Loop, AliasSet information for all instructions of the
 /// loop and loop safety information as arguments. It returns changed status.
 bool hoistRegion(DomTreeNode *, AliasAnalysis *, LoopInfo *, DominatorTree *,
                  TargetLibraryInfo *, Loop *, AliasSetTracker *,
-                 LICMSafetyInfo *);
+                 LICMSafetyInfo *, LoopPass *);
 
 /// \brief Try to promote memory values to scalars by sinking stores out of
 /// the loop and moving loads to before the loop.  We do this by looping over
 /// the stores in the loop, looking for stores to Must pointers which are
 /// loop invariant. It takes AliasSet, Loop exit blocks vector, loop exit blocks
 /// insertion point vector, PredIteratorCache, LoopInfo, DominatorTree, Loop,
 /// AliasSet information for all instructions of the loop and loop safety
 /// information as arguments. It returns changed status.

lib/Analysis/LoopInfo.cpp

     return !contains(I);
   return true;  // All non-instructions are loop invariant
 }
 
 bool Loop::hasLoopInvariantOperands(const Instruction *I) const {
   return all_of(I->operands(), [this](Value *V) { return isLoopInvariant(V); });
 }
 
+bool Loop::isLoopInvariantOutsideSubLoop(const Value *V,
+                                         const Loop *Sub) const {
+  if (const Instruction *I = dyn_cast<Instruction>(V)) {
+    // It's defined in the subloop or outside the outer loop.
+    return Sub->contains(I) || !contains(I);
+  }
+  return true;
+}
+
+bool Loop::hasLoopInvariantOperandsOutsideSubLoop(const Instruction *I,
+                                                  const Loop *Sub) const {
+  return all_of(I->operands(),
+                [this, Sub](Value *V) {
+                  return isLoopInvariantOutsideSubLoop(V, Sub);
+                });
+}
+
 bool Loop::makeLoopInvariant(Value *V, bool &Changed,
                              Instruction *InsertPt) const {
   if (Instruction *I = dyn_cast<Instruction>(V))
     return makeLoopInvariant(I, Changed, InsertPt);
   return true;  // All non-instructions are loop-invariant.
 }
 
 bool Loop::makeLoopInvariant(Instruction *I, bool &Changed,

lib/Transforms/Scalar/LICM.cpp

 static Instruction *
 CloneInstructionInExitBlock(Instruction &I, BasicBlock &ExitBlock, PHINode &PN,
                             const LoopInfo *LI,
                             const LICMSafetyInfo *SafetyInfo);
 static bool canSinkOrHoistInst(Instruction &I, AliasAnalysis *AA,
                                DominatorTree *DT, TargetLibraryInfo *TLI,
                                Loop *CurLoop, AliasSetTracker *CurAST,
                                LICMSafetyInfo *SafetyInfo);
+static bool isTriviallyReplacablePHI(const PHINode &PN, const Instruction &I);
 
 namespace {
   struct LICM : public LoopPass {
     static char ID; // Pass identification, replacement for typeid
     LICM() : LoopPass(ID) {
       initializeLICMPass(*PassRegistry::getPassRegistry());
     }
 
     bool runOnLoop(Loop *L, LPPassManager &LPM) override;
 
     /// This transformation requires natural loop information & requires that
     /// loop preheaders be inserted into the CFG...
     ///
     void getAnalysisUsage(AnalysisUsage &AU) const override {
-      AU.setPreservesCFG();
       AU.addRequired<DominatorTreeWrapperPass>();
       AU.addRequired<LoopInfoWrapperPass>();
       AU.addRequiredID(LoopSimplifyID);
       AU.addPreservedID(LoopSimplifyID);
       AU.addRequiredID(LCSSAID);
       AU.addPreservedID(LCSSAID);
       AU.addRequired<AAResultsWrapperPass>();
       AU.addPreserved<AAResultsWrapperPass>();

 
   TLI = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
 
   assert(L->isLCSSAForm(*DT) && "Loop is not in LCSSA form.");
 
   CurAST = new AliasSetTracker(*AA);
   // Collect Alias info from subloops.
   for (Loop *InnerL : L->getSubLoops()) {
-    AliasSetTracker *InnerAST = LoopToAliasSetMap[InnerL];
-    assert(InnerAST && "Where is my AST?");
-
-    // What if InnerLoop was modified by other passes ?
-    CurAST->add(*InnerAST);
-
-    // Once we've incorporated the inner loop's AST into ours, we don't need the
-    // subloop's anymore.
-    delete InnerAST;
-    LoopToAliasSetMap.erase(InnerL);
+    auto ASTI = LoopToAliasSetMap.find(InnerL);
+    // Subloop alias info may have already been merged into another subloop's
+    // AST if it was hoisted from an inner loop.
+    if (ASTI != LoopToAliasSetMap.end()) {
+      AliasSetTracker *InnerAST = ASTI->second;
+      assert(InnerAST);
+
+      // What if InnerLoop was modified by other passes ?
+      CurAST->add(*InnerAST);
+
+      delete InnerAST;
+      LoopToAliasSetMap.erase(InnerL);
+    }
   }
 
   CurLoop = L;
 
   // Get the preheader block to move instructions into...
   Preheader = L->getLoopPreheader();
 
   // Loop over the body of this loop, looking for calls, invokes, and stores.

   //
   // 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
   // us to sink instructions in one pass, without iteration.  After sinking
   // instructions, we perform another pass to hoist them out of the loop.
   //
   if (L->hasDedicatedExits())
     Changed |= sinkRegion(DT->getNode(L->getHeader()), AA, LI, DT, TLI, CurLoop,
-                          CurAST, &SafetyInfo);
+                          CurAST, &SafetyInfo, this);
   if (Preheader)
     Changed |= hoistRegion(DT->getNode(L->getHeader()), AA, LI, DT, TLI,
-                           CurLoop, CurAST, &SafetyInfo);
+                           CurLoop, CurAST, &SafetyInfo, this);
 
   // Now that all loop invariants have been removed from the loop, promote any
   // memory references to scalars that we can.
   if (!DisablePromotion && (Preheader || L->hasDedicatedExits())) {
     SmallVector<BasicBlock *, 8> ExitBlocks;
     SmallVector<Instruction *, 8> InsertPts;
     PredIteratorCache PIC;
 

   // for when we process the outer loop.
   if (L->getParentLoop())
     LoopToAliasSetMap[L] = CurAST;
   else
     delete CurAST;
   return Changed;
 }
 
+static bool canSinkSubLoop(Loop *SubLoop, AliasAnalysis *AA, LoopInfo *LI,
+                           DominatorTree *DT, TargetLibraryInfo *TLI,
+                           Loop *CurLoop, AliasSetTracker *CurAST,
+                           LICMSafetyInfo *SafetyInfo) {
+  // Only loops at level n+1.
+  if (SubLoop->getParentLoop() != CurLoop)
+    return false;
+
+  auto ExitBlock = SubLoop->getExitBlock();
+  // Don't sink if it has multiple exit or entry blocks, or if there's no
+  // single exit block we can sink to.
+  if (!ExitBlock || !SubLoop->getLoopPreheader() || !CurLoop->getExitBlock()) {
+    return false;
+  }
+
+  // Don't sink the subloop unless it's guaranteed to execute, i.e. all paths
+  // to the outer loop's exit block go through the subloop.
+  if (!DT->dominates(SubLoop->getHeader(), CurLoop->getExitBlock())) {
+    DEBUG(dbgs() << "Not sinking subloop: " << SubLoop->getHeader()->getName()
+                 << " does not dominate outer loop exit: "
+                 << CurLoop->getExitBlock()->getName() << "\n");
+    return false;
+  }
+
+  // Find any LCSSA phi nodes and check they're not used inside the loop.
+  std::vector<PHINode *> PhisToMove;
+  PHINode *PN;
+  for (auto II = ExitBlock->begin(); (PN = dyn_cast<PHINode>(II)); ++II) {
+    if (PN && PN->getNumOperands() == 1 &&
+        SubLoop->contains(PN->getIncomingBlock(0))) {
+      if (!isNotUsedInLoop(*PN, CurLoop, SafetyInfo)) {
+        DEBUG(dbgs() << "Not sinking subloop: "
+                     << SubLoop->getHeader()->getName()
+                     << ": Inner loop value used in outer loop.\n");
+        return false;
+      }
+    }
+  }
+
+  // Check we can sink each instruction inside the loop.
+  for (BasicBlock *BB : SubLoop->blocks()) {
+    for (Instruction &I : BB->getInstList()) {
+      if (!dyn_cast<PHINode>(&I) &&
+          !dyn_cast<BranchInst>(&I) &&
+          !canSinkOrHoistInst(I, AA, DT, TLI, CurLoop, CurAST, SafetyInfo)) {
+        DEBUG(dbgs() << "Not sinking subloop: "
+                     << SubLoop->getHeader()->getName() << ": Can't sink " << I
+                     << "\n");
+        return false;
+      }
+    }
+  }
+
+  return true;
+}
+
+static bool canHoistSubLoop(Loop *SubLoop, AliasAnalysis *AA, LoopInfo *LI,
+                            DominatorTree *DT, TargetLibraryInfo *TLI,
+                            Loop *CurLoop, AliasSetTracker *CurAST,
+                            LICMSafetyInfo *SafetyInfo) {
+  // Only loops at level n+1.
+  if (SubLoop->getParentLoop() != CurLoop)
+    return false;
+
+  // Don't hoist if it has multiple exit or entry blocks.
+  if (!SubLoop->getExitBlock() || !SubLoop->getLoopPreheader()) {
+    DEBUG(dbgs() << "Not hoisting subloop: " << SubLoop->getHeader()->getName()
+                 << ": Missing exit block or preheader.");
+    return false;
+  }
+
+  if (!DT->dominates(SubLoop->getHeader(), CurLoop->getExitBlock())) {
+    DEBUG(dbgs() << "Not hoisting subloop: " << SubLoop->getHeader()->getName()
+                 << " does not dominate outer loop exit: "
+                 << CurLoop->getExitBlock()->getName() << "\n");
+    return false;
+  }
+
+  // Go through all instructions in the subloop, and return if one of them
+  // means the loop can't be hoisted.
+  // TODO: Only do this loop once, share result between sinking and hoisting.
+  for (BasicBlock *BB : SubLoop->blocks()) {
+    for (Instruction &I : BB->getInstList()) {
+      if (!CurLoop->hasLoopInvariantOperandsOutsideSubLoop(&I, SubLoop)) {
+        DEBUG(dbgs() << "Not hoisting subloop: "
+                     << SubLoop->getHeader()->getName()
+                     << ": Instruction has loop-variant operands: " << I
+                     << "\n");
+        return false;
+      } else if (dyn_cast<PHINode>(&I) ||
+                 dyn_cast<BranchInst>(&I)) {
+        continue;
+      } else if (!canSinkOrHoistInst(I, AA, DT, TLI, CurLoop,
+                                     CurAST, SafetyInfo)) {
+        return false;
+      } else if (!isSafeToExecuteUnconditionally(I, DT, TLI, CurLoop, SafetyInfo,
+                                 CurLoop->getLoopPreheader()->getTerminator())) {
+        return false;
+      }
+    }
+  }
+
+  return true;
+}
+
+template <typename PredTy>
+static void replaceSuccessor(BasicBlock *BB, PredTy Predicate,
+                             BasicBlock *NewSucc) {
+  auto Term = BB->getTerminator();
+  for (unsigned i = 0; i < Term->getNumSuccessors(); ++i) {
+    if (Predicate(Term->getSuccessor(i))) {
+      Term->setSuccessor(i, NewSucc);
+      return;
+    }
+  }
+  assert(false && "Block has no such existing successor");
+}
+
+/// \brief Update all phi nodes for which Predicate holds to refer to New.
+template <typename PredTy>
+static void replacePhiUses(BasicBlock *BB, PredTy Predicate, BasicBlock *New) {
+  PHINode *PN;
+  for (auto II = BB->begin(); (PN = dyn_cast<PHINode>(II)); ++II) {
+    for (unsigned i = 0; i < PN->getNumOperands(); ++i) {
+      BasicBlock *Incoming = PN->getIncomingBlock(i);
+      if (Predicate(Incoming))
+        PN->setIncomingBlock(i, New);
+    }
+  }
+}
+
+static void removeSubLoop(Loop *SubLoop, AliasAnalysis *AA, LoopInfo *LI,
+                          DominatorTree *DT, TargetLibraryInfo *TLI,
+                          Loop *CurLoop, AliasSetTracker *CurAST,
+                          LICMSafetyInfo *SafetyInfo) {
+  auto &SubLoops = CurLoop->getSubLoops();
+  BasicBlock *SubLoopHeader = SubLoop->getHeader();
+  Loop::iterator it = std::find(SubLoops.begin(), SubLoops.end(), SubLoop);
+  assert(it != SubLoops.end() && *it == SubLoop);
+  SubLoop = CurLoop->removeChildLoop(it);
+
+  auto OldExitBlock = SubLoop->getExitBlock();
+  assert(OldExitBlock);
+
+  // Create a new exit block, which will be hoisted along with the loop to
+  // preserve LCSSA.
+  BasicBlock *NewExitBlock =
+      BasicBlock::Create(SubLoopHeader->getContext(),
+                         SubLoopHeader->getName() + ".licm_exit",
+                         SubLoopHeader->getParent());
+
+  // Find any LCSSA phi nodes and add them to the new exit block.
+  std::vector<PHINode *> PhisToMove;
+  PHINode *PN;
+  for (auto II = OldExitBlock->begin(); (PN = dyn_cast<PHINode>(II)); ++II) {
+    if (PN && PN->getNumOperands() == 1 &&
+        SubLoop->contains(PN->getIncomingBlock(0))) {
+      auto Inst = dyn_cast<Instruction>(PN->getIncomingValue(0));
+      if (Inst && SubLoop->contains(Inst)) {
+        PhisToMove.push_back(PN);
+      }
+    }
+  }
+  for (auto PN : PhisToMove) {
+    PN->removeFromParent();
+    NewExitBlock->getInstList().push_back(PN);
+  }
+
+  // Point the subloop's predecessor at its exit block.
+  BasicBlock *SubLoopPredecessor = SubLoop->getLoopPredecessor();
+  replaceSuccessor(SubLoopPredecessor, [SubLoopHeader](BasicBlock *BB) {
+                                         return BB == SubLoopHeader;
+                                       }, OldExitBlock);
+
+  auto ExitingBlock = SubLoop->getExitingBlock();
+  replacePhiUses(OldExitBlock, [ExitingBlock](BasicBlock *BB) {
+                                 return BB == ExitingBlock;
+                               }, SubLoopPredecessor);
+
+  // Branch from the subloop's exiting block to the new exit block.
+  replaceSuccessor(ExitingBlock, [SubLoop](BasicBlock *BB) {
+                                   return !SubLoop->contains(BB);
+                                 }, NewExitBlock);
+
+  for (auto BBI = SubLoop->block_begin(); BBI != SubLoop->block_end(); ++BBI) {
+    CurLoop->removeBlockFromLoop(*BBI);
+  }
+}
+
+// Insert the subloop between the outer loop's preheader and header.
+static void insertLoopAfterPreheader(Loop *SubLoop, AliasAnalysis *AA,
+                                     LoopInfo *LI, DominatorTree *DT,
+                                     TargetLibraryInfo *TLI, Loop *CurLoop,
+                                     AliasSetTracker *CurAST,
+                                     LICMSafetyInfo *SafetyInfo) {
+  BasicBlock *SubLoopHeader = SubLoop->getHeader();
+  BasicBlock *Preheader = CurLoop->getLoopPreheader();
+  BasicBlock *NewExitBlock = SubLoop->getExitBlock();
+
+  DEBUG(dbgs() << "LICM hoisting to " << Preheader->getName() << ": ");
+  DEBUG(SubLoop->dump());
+
+  // The preheader's successors are having (one of) their predeccessors
+  // replaced with NewExitBlock, so update their phis.
+  Preheader->replaceSuccessorsPhiUsesWith(NewExitBlock);
+
+  // Move the preheader's terminator to the hoisted subloop's new exit block.
+  auto PreheaderTerminator = Preheader->getTerminator();
+  PreheaderTerminator->removeFromParent();
+  NewExitBlock->getInstList().push_back(PreheaderTerminator);
+
+  // Branch from the preheader to the hoisted subloop.
+  BranchInst::Create(SubLoopHeader, Preheader);
+  // Fix up invalid phis in the subloop header. If a block in a phi is _not_ a
+  // predeccessor, it's invalid and it should point to the preheader instead.
+  replacePhiUses(SubLoopHeader,
+                 [SubLoopHeader](BasicBlock *Incoming) {
+                   return std::find(pred_begin(SubLoopHeader),
+                                    pred_end(SubLoopHeader), Incoming)
+                          == pred_end(SubLoopHeader);
+                 }, Preheader);
+
+  Loop *ParentLoop = CurLoop->getParentLoop();
+  if (ParentLoop) {
+    ParentLoop->addChildLoop(SubLoop);
+    ParentLoop->addBasicBlockToLoop(NewExitBlock, *LI);
+  }
+}
+
+// Insert the subloop after the outer loop's exit block. Then, sink all the
+// original exit block's instructions down to the subloop's exit block,
+// *except* phi nodes.
+static void sinkSubLoopToExit(Loop *SubLoop, AliasAnalysis *AA, LoopInfo *LI,
+                              DominatorTree *DT, TargetLibraryInfo *TLI,
+                              Loop *CurLoop, AliasSetTracker *CurAST,
+                              LICMSafetyInfo *SafetyInfo) {
+  BasicBlock *SubLoopHeader = SubLoop->getHeader();
+  BasicBlock *ExitBlock = CurLoop->getExitBlock();
+  BasicBlock *SubLoopExitBlock = SubLoop->getExitBlock();
+  assert(SubLoopHeader && ExitBlock && SubLoopExitBlock);
+
+  DEBUG(dbgs() << "LICM sinking to " << ExitBlock->getName() << ": ");
+  DEBUG(SubLoop->dump());
+
+  // Fix up invalid phis in the subloop header. If a block in a phi is _not_ a
+  // predeccessor, it's invalid and it should point to the outer loop exit
+  // block instead.
+  replacePhiUses(SubLoopHeader,
+                 [SubLoopHeader](BasicBlock *Incoming) {
+                   return std::find(pred_begin(SubLoopHeader),
+                                    pred_end(SubLoopHeader), Incoming)
+                          == pred_end(SubLoopHeader);
+                 }, ExitBlock);
+
+  // Sink instructions from the main loop's exit block to the subloop's.
+  ExitBlock->replaceSuccessorsPhiUsesWith(SubLoopExitBlock);
+  std::vector<Instruction *> InstructionsToMove, InstructionsToErase;
+  for (auto II = ExitBlock->begin(); II != ExitBlock->end(); ++II) {
+    Instruction *I = &*II;
+    // Because we're sinking it, we know that no value from the subloop has a
+    // use in the outer loop. Therefore, any phi nodes referencing a subloop
+    // value in the outer loop's exit block must be trivial LCSSA ones.
+    if (auto PN = dyn_cast<PHINode>(I)) {
+      auto Incoming = dyn_cast<Instruction>(PN->getIncomingValue(0));
+      if (Incoming && PN->getNumOperands() > 0 &&
+          isTriviallyReplacablePHI(*PN, *Incoming)) {
+        if (Incoming->getParent() == SubLoopExitBlock) {
+          PN->replaceAllUsesWith(Incoming);
+          InstructionsToErase.push_back(PN);
+        }
+      }
+    } else {
+      InstructionsToMove.push_back(I);
+    }
+  }
+
+  for (auto I : InstructionsToMove) {
+    I->removeFromParent();
+    SubLoopExitBlock->getInstList().push_back(I);
+  }
+  for (auto I : InstructionsToErase) {
+    DEBUG(dbgs() << "Erasing inst " << I << "\n");
+    I->eraseFromParent();
+  }
+
+  // Branch from the outer loop's exit block to the sunk subloop.
+  BranchInst::Create(SubLoopHeader, ExitBlock);
+
+  // The sunk subloop may use values which were defined in the outer loop. To
+  // preserve LCSSA, find these and add phis in the outer loop's exit block.
+  SmallVector<BasicBlock *, 8> ExitingBlocks;
+  CurLoop->getExitingBlocks(ExitingBlocks);
+  for (BasicBlock *BB : SubLoop->blocks()) {
+    for (Instruction &I : BB->getInstList()) {
+      for (unsigned Idx = 0; Idx < I.getNumOperands(); ++Idx) {
+        auto Op = dyn_cast<Instruction>(I.getOperand(Idx));
+        if (Op && CurLoop->contains(Op->getParent())) {
+          auto PN =
+              PHINode::Create(Op->getType(), 0, Op->getName() + ".licm_lcssa",
+                              &*ExitBlock->begin());
+          for (BasicBlock *ExitingBlock : ExitingBlocks) {
+            PN->addIncoming(Op, ExitingBlock);
+          }
+          I.setOperand(Idx, PN);
+          DEBUG(dbgs() << "Creating PHI node: " << *PN << "\n");
+        }
+      }
+    }
+  }
+
+  Loop *ParentLoop = CurLoop->getParentLoop();
+  if (ParentLoop) {
+    ParentLoop->addChildLoop(SubLoop);
+    ParentLoop->addBasicBlockToLoop(SubLoopExitBlock, *LI);
+  }
+}
+
 /// Walk the specified region of the CFG (defined by all blocks dominated by
 /// the specified block, and that are in the current loop) in reverse depth 
 /// first order w.r.t the DominatorTree.  This allows us to visit uses before
 /// definitions, allowing us to sink a loop body in one pass without iteration.
 ///
 bool llvm::sinkRegion(DomTreeNode *N, AliasAnalysis *AA, LoopInfo *LI,
                       DominatorTree *DT, TargetLibraryInfo *TLI, Loop *CurLoop,
-                      AliasSetTracker *CurAST, LICMSafetyInfo *SafetyInfo) {
+                      AliasSetTracker *CurAST, LICMSafetyInfo *SafetyInfo,
+                      LoopPass *LP) {
 
   // Verify inputs.
   assert(N != nullptr && AA != nullptr && LI != nullptr && 
          DT != nullptr && CurLoop != nullptr && CurAST != nullptr && 
          SafetyInfo != nullptr && "Unexpected input to sinkRegion");
 
   BasicBlock *BB = N->getBlock();
   // If this subregion is not in the top level loop at all, exit.
   if (!CurLoop->contains(BB)) return false;
 
   // We are processing blocks in reverse dfo, so process children first.
   bool Changed = false;
   const std::vector<DomTreeNode*> &Children = N->getChildren();
   for (DomTreeNode *Child : Children)
-    Changed |= sinkRegion(Child, AA, LI, DT, TLI, CurLoop, CurAST, SafetyInfo);
+    Changed |=
+        sinkRegion(Child, AA, LI, DT, TLI, CurLoop, CurAST, SafetyInfo, LP);
 
   // Only need to process the contents of this block if it is not part of a
   // subloop (which would already have been processed).
-  if (inSubLoop(BB,CurLoop,LI)) return Changed;
+  if (inSubLoop(BB, CurLoop, LI)) {
+    BasicBlock *BB = N->getBlock();
+    Loop *SubLoop = LI->getLoopFor(BB);
+
+    // Make sure this is the dominating block.
+    if (SubLoop->getHeader() == BB) {
+      if (canSinkSubLoop(SubLoop, AA, LI, DT, TLI, CurLoop, CurAST,
+                         SafetyInfo)) {
+        removeSubLoop(SubLoop, AA, LI, DT, TLI, CurLoop, CurAST, SafetyInfo);
+        sinkSubLoopToExit(SubLoop, AA, LI, DT, TLI, CurLoop, CurAST,
+                          SafetyInfo);
+        SubLoop->verifyLoop();
+        CurLoop->verifyLoop();
+        Changed = true;
+        // runOnLoop uses the subloop list to find out what to free. Because
+        // SubLoop is no longer in that list, free it here instead.
+        if (LP && !CurLoop->getParentLoop())
+          LP->deleteAnalysisLoop(SubLoop);
+      }
+    }
+    return Changed;
+  }
 
   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');

 
 /// Walk the specified region of the CFG (defined by all blocks dominated by
 /// the specified block, and that are in the current loop) in depth first
 /// order w.r.t the DominatorTree.  This allows us to visit definitions before
 /// uses, allowing us to hoist a loop body in one pass without iteration.
 ///
 bool llvm::hoistRegion(DomTreeNode *N, AliasAnalysis *AA, LoopInfo *LI,
                        DominatorTree *DT, TargetLibraryInfo *TLI, Loop *CurLoop,
-                       AliasSetTracker *CurAST, LICMSafetyInfo *SafetyInfo) {
+                       AliasSetTracker *CurAST, LICMSafetyInfo *SafetyInfo,
+                       LoopPass *LP) {
   // Verify inputs.
   assert(N != nullptr && AA != nullptr && LI != nullptr && 
          DT != nullptr && CurLoop != nullptr && CurAST != nullptr && 
          SafetyInfo != nullptr && "Unexpected input to hoistRegion");
 
   BasicBlock *BB = N->getBlock();
 
   // If this subregion is not in the top level loop at all, exit.
   if (!CurLoop->contains(BB)) return false;
 
   // Only need to process the contents of this block if it is not part of a
   // subloop (which would already have been processed).
   bool Changed = false;
-  if (!inSubLoop(BB, CurLoop, LI))
+  if (!inSubLoop(BB, CurLoop, LI)) {
     for (BasicBlock::iterator II = BB->begin(), E = BB->end(); II != E; ) {
       Instruction &I = *II++;
       // Try constant folding this instruction.  If all the operands are
       // constants, it is technically hoistable, but it would be better to just
       // fold it.
       if (Constant *C = ConstantFoldInstruction(
               &I, I.getModule()->getDataLayout(), TLI)) {
         DEBUG(dbgs() << "LICM folding inst: " << I << "  --> " << *C << '\n');

       // is safe to hoist the instruction.
       //
       if (CurLoop->hasLoopInvariantOperands(&I) &&
           canSinkOrHoistInst(I, AA, DT, TLI, CurLoop, CurAST, SafetyInfo) &&
           isSafeToExecuteUnconditionally(I, DT, TLI, CurLoop, SafetyInfo,
                                  CurLoop->getLoopPreheader()->getTerminator()))
         Changed |= hoist(I, DT, CurLoop, SafetyInfo);
     }
+  } else { // See if we can hoist the entire subloop.
+    BasicBlock *BB = N->getBlock();
+    Loop *SubLoop = LI->getLoopFor(BB);
+
+    // Make sure this is the dominating block.
+    if (SubLoop->getHeader() == BB) {
+      if (canHoistSubLoop(SubLoop, AA, LI, DT, TLI, CurLoop, CurAST,
+                          SafetyInfo)) {
+        removeSubLoop(SubLoop, AA, LI, DT, TLI, CurLoop, CurAST, SafetyInfo);
+        insertLoopAfterPreheader(SubLoop, AA, LI, DT, TLI, CurLoop, CurAST,
+                                 SafetyInfo);
+        SubLoop->verifyLoop();
+        Changed = true;
+        // runOnLoop uses the subloop list to find out what to free. Because
+        // SubLoop is no longer in that list, free it here instead.
+        if (LP && !CurLoop->getParentLoop())
+          LP->deleteAnalysisLoop(SubLoop);
+      }
+    }
+  }
 
   const std::vector<DomTreeNode*> &Children = N->getChildren();
-  for (DomTreeNode *Child : Children)
-    Changed |= hoistRegion(Child, AA, LI, DT, TLI, CurLoop, CurAST, SafetyInfo);
+  for (DomTreeNode *Child : Children) {
+    Changed |=
+        hoistRegion(Child, AA, LI, DT, TLI, CurLoop, CurAST, SafetyInfo, LP);
+  }
   return Changed;
 }
 
 /// Computes loop safety information, checks loop body & header
 /// for the possibility of may throw exception.
 ///
 void llvm::computeLICMSafetyInfo(LICMSafetyInfo * SafetyInfo, Loop * CurLoop) {
   assert(CurLoop != nullptr && "CurLoop cant be null");

     PreheaderLoad->eraseFromParent();
 
   return Changed;
 }
 
 /// Simple analysis hook. Clone alias set info.
 ///
 void LICM::cloneBasicBlockAnalysis(BasicBlock *From, BasicBlock *To, Loop *L) {
-  AliasSetTracker *AST = LoopToAliasSetMap.lookup(L);
-  if (!AST)
-    return;
+  auto ASTI = LoopToAliasSetMap.find(L);
+  if (ASTI != LoopToAliasSetMap.end()) {
+    AliasSetTracker *AST = ASTI->second;
+    assert(AST);
 
     AST->copyValue(From, To);
+  }
 }
 
 /// Simple Analysis hook. Delete value V from alias set
 ///
 void LICM::deleteAnalysisValue(Value *V, Loop *L) {
-  AliasSetTracker *AST = LoopToAliasSetMap.lookup(L);
-  if (!AST)
-    return;
+  auto ASTI = LoopToAliasSetMap.find(L);
+
+  if (ASTI != LoopToAliasSetMap.end()) {
+    AliasSetTracker *AST = ASTI->second;
+    assert(AST);
 
     AST->deleteValue(V);
+  }
 }
 
 /// Simple Analysis hook. Delete value L from alias set map.
 ///
 void LICM::deleteAnalysisLoop(Loop *L) {
-  AliasSetTracker *AST = LoopToAliasSetMap.lookup(L);
-  if (!AST)
-    return;
+  auto ASTI = LoopToAliasSetMap.find(L);
+  if (ASTI != LoopToAliasSetMap.end()) {
+    AliasSetTracker *AST = ASTI->second;
+    assert(AST);
 
     delete AST;
     LoopToAliasSetMap.erase(L);
+  }
 }
 
 
 /// Return true if the body of this loop may store into the memory
 /// location pointed to by V.
 ///
 static bool pointerInvalidatedByLoop(Value *V, uint64_t Size,
                                      const AAMDNodes &AAInfo, 

test/Analysis/ScalarEvolution/2012-03-26-LoadConstant.ll

-; RUN: opt < %s -basicaa -globalopt -instcombine -loop-rotate -licm -instcombine -indvars -loop-deletion -constmerge -S | FileCheck %s
+; RUN: opt < %s -basicaa -globalopt -instcombine -loop-rotate -licm -instcombine -indvars -constmerge -loop-deletion -S | FileCheck %s
 ; PR11882: ComputeLoadConstantCompareExitLimit crash.
 ;
 ; for.body is deleted leaving a loop-invariant load.
-; CHECK-NOT: for.body
+; CHECK-NOT: for.body:
 target datalayout = "e-p:64:64:64-n32:64"
 
 @func_21_l_773 = external global i32, align 4
 @g_814 = external global i32, align 4
 @g_244 = internal global [1 x [0 x i32]] zeroinitializer, align 4
 
 define void @func_21() nounwind uwtable ssp {
 entry:

test/Transforms/LICM/inner-loop-dont-sink.ll

+; RUN: opt < %s -S -licm | FileCheck %s
+
+define void @main() #0 {
+entry:
+; CHECK-LABEL: entry:
+; CHECK-NEXT: br label %outer.header
+  br label %outer.header
+
+outer.header:
+; CHECK-LABEL: outer.header:
+; CHECK: br i1 undef, label %if.then, label %outer.latch
+  br i1 undef, label %if.then, label %outer.latch
+
+if.then:
+; CHECK-LABEL: if.then:
+  %call = tail call i32 @generate()
+; CHECK: br label %inner.body
+  br label %inner.body
+
+inner.body:
+; CHECK-LABEL: inner.body:
+  %arrayctor.done = icmp eq i32 undef, %call
+; CHECK: br i1 %arrayctor.done, label %outer.latch.loopexit, label %inner.body
+  br i1 %arrayctor.done, label %outer.latch, label %inner.body
+
+outer.latch:
+  br i1 undef, label %outer.exit, label %outer.header
+
+outer.exit:
+  ret void
+}
+
+declare i32 @generate() #1

test/Transforms/LICM/inner-loop-hoist.ll

+; RUN: opt < %s -S -licm -loop-unswitch | FileCheck %s
+
+; Function Attrs: nounwind uwtable
+define i32 @main() #1 {
+entry:
+; CHECK-LABEL: entry:
+; CHECK-NEXT: br label %third.body
+  br label %first.header
+
+first.header:
+; CHECK-LABEL: first.header:
+; CHECK-NEXT: br label %third.body.licm_exit
+  br label %second.header
+
+second.header:
+; CHECK-LABEL: second.header:
+; CHECK-NEXT: br label %second.exiting
+  br label %third.body
+
+third.body:
+; CHECK-LABEL: third.body:
+  %xor1.i = phi i32 [ 0, %second.header ], [ %xor1, %third.body ]
+  %xor1 = xor i32 %xor1.i, 1234567
+; CHECK: br i1 false, label %third.body, label %third.body.licm_exit
+  br i1 undef, label %third.body, label %second.exiting
+
+second.exiting:
+; CHECK-LABEL: second.exiting:
+  %xor1.lcssa = phi i32 [ %xor1, %third.body ]
+  %call1 = tail call i32 (i32) @putchar(i32 %xor1.lcssa)
+; CHECK: br i1 false, label %second.header, label %first.exiting
+  br i1 undef, label %second.header, label %first.exiting
+
+first.exiting:
+  %xor1.lcssa2 = phi i32 [ %xor1.lcssa, %second.exiting ]
+  %call2 = tail call i32 (i32) @putchar(i32 %xor1.lcssa2)
+  br i1 false, label %first.header, label %first.exit
+
+first.exit:
+  ret i32 0
+
+; CHECK-LABEL: third.body.licm_exit:
+; CHECK-NEXT: br label %second.header
+
+; CHECK-LABEL: third.body.licm_exit1:
+; CHECK-NEXT: phi i32 [ %xor1, %third.body ]
+; CHECK-NEXT br label %first.header
+}
+
+; Function Attrs: nounwind
+declare i32 @putchar(i32) #2

test/Transforms/LICM/inner-loop-sink-multiple-phi.ll

+; RUN: opt < %s -S -licm -loop-unswitch | FileCheck %s
+
+define void @main() #0 {
+entry:
+; CHECK-LABEL: entry:
+; CHECK: br label %outer.header
+  br label %outer.header
+
+outer.header:
+  br label %inner.body
+
+inner.body:
+; CHECK-LABEL: inner.body:
+; CHECK-NEXT: %y = phi i32 [ 0, %outer.exit ], [ %add1, %inner.body ]
+; CHECK-NEXT: %z = phi i32 [ 0, %outer.exit ], [ %add2, %inner.body ]
+  %y = phi i32 [ 0, %outer.header ], [ %add1, %inner.body ]
+  %z = phi i32 [ 0, %outer.header ], [ %add2, %inner.body ]
+  %add1 = add i32 %y, 7
+  %add2 = add i32 %z, 11
+; CHECK: br i1 false, label %inner.body, label %inner.body.licm_exit
+  br i1 undef, label %inner.body, label %outer.inc
+
+outer.inc:
+; CHECK-LABEL: outer.inc:
+; CHECK-NEXT: br i1 false, label %outer.header, label %outer.exit
+  %y.lcssa = phi i32 [ %add1, %inner.body ]
+  %z.lcssa = phi i32 [ %add2, %inner.body ]
+  br i1 undef, label %outer.header, label %outer.exit
+
+outer.exit:
+; CHECK-LABEL: outer.exit:
+; CHECK-NEXT: br label %inner.body
+  %y.0.lcssa = phi i32 [ %y.lcssa, %outer.inc ]
+  %z.0.lcssa = phi i32 [ %z.lcssa, %outer.inc ]
+  ret void
+
+; CHECK-LABEL: inner.body.licm_exit:
+; CHECK-NEXT: %y.lcssa = phi i32 [ %add1, %inner.body ]
+; CHECK-NEXT: %z.lcssa = phi i32 [ %add2, %inner.body ]
+; CHECK-NEXT: ret void
+}

test/Transforms/LICM/sinking.ll

   ret void
 
 lab20:
   br label %lab21
 
 lab21:
 ; CHECK: lab21:
 ; CHECK-NOT: store
-; CHECK: br i1 false, label %lab21, label %lab22
+; CHECK: br i1 false, label %lab21, label %lab21.licm_exit
   store i32 36127957, i32* undef, align 4
   br i1 undef, label %lab21, label %lab22
 
 lab22:
 ; CHECK: lab22:
 ; CHECK: store
 ; CHECK-NEXT: indirectbr i8* undef
   indirectbr i8* undef, [label %lab5, label %lab6, label %lab7]