[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

6

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

379

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

6

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;
 
+  // Return true if the specified value is either loop invariant or defined in
+  // the given subloop.
+  bool isLoopInvariantOutsideSubLoop(const Value *V,
+                                     const Loop *Sub) const;
+
+  // Return true if all the operands of the specified instruction are loop
+  // invariant or defined in the given subloop.
+  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.
   bool makeLoopInvariant(Value *V, bool &Changed,
                          Instruction *InsertPt = nullptr) const;
 
   /// If the given instruction is inside of the loop and it can be hoisted, do
   /// so to make it trivially loop-invariant.

include/llvm/Analysis/LoopPass.h

   PassManagerType getPassManagerType() const override {
     return PMT_LoopPassManager;
   }
 
 public:
   // Add a new loop into the loop queue as a child of the given parent, or at
   // the top level if \c ParentLoop is null.
   Loop &addLoop(Loop *ParentLoop);
+  void addExistingLoop(Loop *L, Loop *ParentLoop);
 
   //===--------------------------------------------------------------------===//
   /// SimpleAnalysis - Provides simple interface to update analysis info
   /// maintained by various passes. Note, if required this interface can
   /// be extracted into a separate abstract class but it would require
   /// additional use of multiple inheritance in Pass class hierarchy, something
   /// we are trying to avoid.
 

include/llvm/Transforms/Utils/LoopUtils.h

 class Loop;
 class LoopInfo;
 class Pass;
 class PredicatedScalarEvolution;
 class PredIteratorCache;
 class ScalarEvolution;
 class SCEV;
 class TargetLibraryInfo;
+class LPPassManager;
 
 /// \brief Captures loop safety information.
 /// It keep information for loop & its header may throw exception.
 struct LICMSafetyInfo {
   bool MayThrow;       // The current loop contains an instruction which
                        // may throw.
   bool HeaderMayThrow; // Same as previous, but specific to loop header
   // Used to update funclet bundle operands.

 /// 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 *, LPPassManager *);
 
 /// \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.

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/Analysis/LoopPass.cpp

 
 LPPassManager::LPPassManager()
   : FunctionPass(ID), PMDataManager() {
   LI = nullptr;
   CurrentLoop = nullptr;
 }
 
 // Inset loop into loop nest (LoopInfo) and loop queue (LQ).
-Loop &LPPassManager::addLoop(Loop *ParentLoop) {
-  // Create a new loop. LI will take ownership.
-  Loop *L = new Loop();
-
+void LPPassManager::addExistingLoop(Loop *L, Loop *ParentLoop) {
   // Insert into the loop nest and the loop queue.
   if (!ParentLoop) {
     // This is the top level loop.
     LI->addTopLevelLoop(L);
     LQ.push_front(L);
-    return *L;
+    return;
   }
 
   ParentLoop->addChildLoop(L);
   // Insert L into the loop queue after the parent loop.
   for (auto I = LQ.begin(), E = LQ.end(); I != E; ++I) {
     if (*I == L->getParentLoop()) {
       // deque does not support insert after.
       ++I;
       LQ.insert(I, 1, L);
       break;
     }
   }
+}
+
+Loop &LPPassManager::addLoop(Loop *ParentLoop) {
+  // Create a new loop. LI will take ownership.
+  Loop *L = new Loop();
+  addExistingLoop(L, ParentLoop);
   return *L;
 }
 
 /// cloneBasicBlockSimpleAnalysis - Invoke cloneBasicBlockAnalysis hook for
 /// all loop passes.
 void LPPassManager::cloneBasicBlockSimpleAnalysis(BasicBlock *From,
                                                   BasicBlock *To, Loop *L) {
   for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {

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<TargetLibraryInfoWrapperPass>();
     getLoopAnalysisUsage(AU);
   }
 
   using llvm::Pass::doFinalization;
 
   bool doFinalization() override {
     assert(LoopToAliasSetMap.empty() && "Didn't free loop alias sets");

 
   // 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
   // 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, &LPM);
   if (Preheader)
     Changed |= hoistRegion(DT->getNode(L->getHeader()), AA, LI, DT, TLI,
                            CurLoop, CurAST, &SafetyInfo);
 
   // 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;

     delete CurAST;
 
   if (Changed)
     if (auto *SEWP = getAnalysisIfAvailable<ScalarEvolutionWrapperPass>())
       SEWP->getSE().forgetLoopDispositions(L);
   return Changed;
 }
 
+// Safety checks for subloop movement, shared between hoisting and sinking.
+// These conditions are necessary, but *not* sufficient to allow moving
+// a subloop.
+static bool canSinkOrHoistSubLoop(const Loop *SubLoop, const DominatorTree *DT,
+                                  const Loop *CurLoop,
+                                  const LICMSafetyInfo *SafetyInfo) {
+  // Only move loops one level at a time.
+  if (SubLoop->getParentLoop() != CurLoop)
+    return false;
+
+  // Subloop being moved must have a single exit and entry block.
+  if (!SubLoop->getLoopPredecessor() || !SubLoop->getExitBlock() ||
+      !SubLoop->getExitingBlock()) {
+    DEBUG(dbgs() << "Not hoisting/sinking subloop: "
+                 << SubLoop->getHeader()->getName()
+                 << ": Missing exit block, exiting block, or predecessor.");
+    return false;
+  }
+
+  if (!SubLoop->hasDedicatedExits()) {
+    DEBUG(dbgs() << "Not hoisting/sinking subloop: "
+                 << SubLoop->getHeader()->getName() << ": Exit block "
+                 << SubLoop->getExitBlock()->getName()
+                 << " has out-of-loop predecessor.\n");
+    return false;
+  }
+
+  if (!isGuaranteedToExecute(*SubLoop->getHeader()->begin(), DT, CurLoop,
+                             SafetyInfo)) {
+    DEBUG(dbgs() << "Not hoisting/sinking subloop "
+                 << SubLoop->getHeader()->getName() << " to "
+                 << CurLoop->getHeader()->getName()
+                 << ": not guaranteed to execute.\n");
+    return false;
+  }
+  return true;
+}
+
+static bool canSinkSubLoop(Loop *SubLoop, AliasAnalysis *AA, DominatorTree *DT,
+                           TargetLibraryInfo *TLI, Loop *CurLoop,
+                           AliasSetTracker *CurAST,
+                           LICMSafetyInfo *SafetyInfo) {
+  if (!canSinkOrHoistSubLoop(SubLoop, DT, CurLoop, SafetyInfo))
+    return false;
+
+  assert(CurLoop->hasDedicatedExits()); // Checked in runOnLoop().
+
+  // Make sure the outer loop has a single exit block we can sink to.
+  if (!CurLoop->getExitBlock()) {
+    DEBUG(dbgs() << "Not sinking subloop: " << SubLoop->getHeader()->getName()
+                 << ": Outer loop " << CurLoop->getHeader()->getName()
+                 << " has no dedicated exit block.\n");
+    return false;
+  }
+
+  auto ExitBlock = SubLoop->getExitBlock();
+  assert(ExitBlock);
+  // Find any LCSSA phi nodes and check they're not used inside the loop.
+  PHINode *PN;
+  for (auto II = ExitBlock->begin(); (PN = dyn_cast<PHINode>(II)); ++II) {
+    if (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) {
+      if (!isa<PHINode>(&I) && !isa<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;
+}
+
+// Update all phi nodes for which the incoming block is no longer a predecessor
+// of BB to refer to New.
+static void replaceInvalidPHIOperandsWith(BasicBlock *BB, BasicBlock *New) {
+  PHINode *PN;
+  for (auto II = BB->begin(); (PN = dyn_cast<PHINode>(II)); ++II) {
+    for (unsigned Idx = 0; Idx < PN->getNumOperands(); ++Idx) {
+      BasicBlock *Incoming = PN->getIncomingBlock(Idx);
+      if (std::find(pred_begin(BB), pred_end(BB), Incoming) == pred_end(BB))
+        PN->setIncomingBlock(Idx, New);
+    }
+  }
+}
+
+static void removeSubLoop(Loop *SubLoop, DominatorTree *DT) {
+  // Remove from parent's subloop list.
+  Loop *Parent = SubLoop->getParentLoop();
+  assert(Parent && "Subloop has no parent");
+  auto &SubLoops = Parent->getSubLoops();
+  BasicBlock *SubLoopHeader = SubLoop->getHeader();
+  Loop::iterator it = std::find(SubLoops.begin(), SubLoops.end(), SubLoop);
+  assert(it != SubLoops.end() && *it == SubLoop);
+  SubLoop = Parent->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());
+  DT->addNewBlock(NewExitBlock, SubLoop->getExitingBlock());
+
+  TerminatorInst *DummyTerm =
+      new UnreachableInst(NewExitBlock->getContext(), NewExitBlock);
+
+  // 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->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->moveBefore(DummyTerm);
+
+  // Point the subloop's predecessor at its exit block.
+  BasicBlock *SubLoopPredecessor = SubLoop->getLoopPredecessor();
+  assert(SubLoopPredecessor);
+  SubLoopPredecessor->getTerminator()->replaceUsesOfWith(SubLoopHeader,
+                                                         OldExitBlock);
+
+  auto ExitingBlock = SubLoop->getExitingBlock();
+  for (auto II = OldExitBlock->begin(); isa<PHINode>(II); ++II)
+    II->replaceUsesOfWith(ExitingBlock, SubLoopPredecessor);
+
+  // Branch from the subloop's exiting block to the new exit block.
+  for (auto BBI = succ_begin(ExitingBlock), BBE = succ_end(ExitingBlock);
+       BBI != BBE; ++BBI) {
+    if (!SubLoop->contains(*BBI)) {
+      ExitingBlock->getTerminator()->replaceUsesOfWith(*BBI, NewExitBlock);
+    }
+  }
+
+  for (auto *BB : SubLoop->blocks())
+    Parent->removeBlockFromLoop(BB);
+
+  // We never need to free a subloop's AST here - because we only ever move
+  // *sub*loops, the AST is always freed in collectAliasInfoForLoop(), even if
+  // we're moving this subloop to level 0.
+
+  // The old exit block is now dominated by the subloop's old predecessor.
+  DT->changeImmediateDominator(OldExitBlock, SubLoopPredecessor);
+}
+
+// Insert the subloop after the phis in the outer loop's exit block.
+static void sinkSubLoopToExit(Loop *SubLoop, LoopInfo *LI, DominatorTree *DT,
+                              Loop *CurLoop, LPPassManager *LPM) {
+  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());
+
+  // Split the outer loop's exit block into phi and non-phi parts.
+  BasicBlock *AfterSubLoop = ExitBlock->splitBasicBlock(
+      ExitBlock->getFirstNonPHI(), ExitBlock->getName() + ".licm_post_subloop");
+  DT->addNewBlock(AfterSubLoop, SubLoopExitBlock);
+
+  // Like in hoisting, fix up invalid phis in the subloop header which used to
+  // refer to the loop's predecessors inside the outer loop.
+  replaceInvalidPHIOperandsWith(SubLoopHeader, ExitBlock);
+
+  // The outer loop's exit block may contain LCSSA phi nodes referring to
+  // values defined in the inner loop. But because we've moved the inner loop
+  // to *after* these nodes, they are invalid. RAUW with the *inner* loop's
+  // LCSSA node.
+  std::vector<Instruction *> InstructionsToErase;
+  PHINode *PN;
+  for (auto II = ExitBlock->begin(); (PN = dyn_cast<PHINode>(II)); ++II) {
+    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);
+      }
+    }
+  }
+  for (auto I : InstructionsToErase)
+    I->eraseFromParent();
+
+  // Branch from the sunk subloop's exit block to the non-phi part of the
+  // original exit block.
+  ExitBlock->getTerminator()->moveBefore(SubLoopExitBlock->getTerminator());
+  SubLoopExitBlock->getTerminator()->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) {
+      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);
+        }
+      }
+    }
+  }
+
+  Loop *ParentLoop = CurLoop->getParentLoop();
+  if (ParentLoop) {
+    ParentLoop->addBasicBlockToLoop(SubLoopExitBlock, *LI);
+    ParentLoop->addBasicBlockToLoop(AfterSubLoop, *LI);
+  }
+
+  assert(LPM);
+  LPM->addExistingLoop(SubLoop, CurLoop->getParentLoop());
+
+  // The old outer exit block's children are dominated by the new exit block.
+  DomTreeNode *OldExitNode = (*DT)[ExitBlock];
+  const std::vector<DomTreeNode *> Children(OldExitNode->getChildren().begin(),
+                                            OldExitNode->getChildren().end());
+  for (DomTreeNode *Child : Children)
+    DT->changeImmediateDominator(Child, (*DT)[AfterSubLoop]);
+
+  DT->changeImmediateDominator(SubLoopHeader, ExitBlock);
+  DT->changeImmediateDominator(AfterSubLoop, SubLoopExitBlock);
+}
+
 /// 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,
+                      LPPassManager *LPM) {
 
   // 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();
+  const std::vector<DomTreeNode *> Children(N->getChildren().begin(),
+                                            N->getChildren().end());
   for (DomTreeNode *Child : Children)
-    Changed |= sinkRegion(Child, AA, LI, DT, TLI, CurLoop, CurAST, SafetyInfo);
+    Changed |=
+        sinkRegion(Child, AA, LI, DT, TLI, CurLoop, CurAST, SafetyInfo, LPM);
 
   // 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))
+  // subloop (which would already have been processed). However, we might be
+  // able to sink the entire subloop.
+  if (inSubLoop(BB, CurLoop, LI)) {
+    Loop *SubLoop = LI->getLoopFor(BB);
+
+    // Make sure this is the dominating block.
+    if (SubLoop->getHeader() == BB) {
+      if (canSinkSubLoop(SubLoop, AA, DT, TLI, CurLoop, CurAST, SafetyInfo)) {
+        removeSubLoop(SubLoop, DT);
+        sinkSubLoopToExit(SubLoop, LI, DT, CurLoop, LPM);
+#ifndef NDEBUG
+        SubLoop->verifyLoop();
+        CurLoop->verifyLoop();
+        DT->verifyDomTree();
+        LI->verify();
+#endif
+        Changed = true;
+      }
+    }
     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');
       ++II;
       CurAST->deleteValue(&I);
       I.eraseFromParent();
       Changed = true;
       continue;
     }
 
     // Check to see if we can sink this instruction to the exit blocks
     // of the loop.  We can do this if the all users of the instruction are
     // outside of the loop.  In this case, it doesn't even matter if the
     // operands of the instruction are loop invariant.
     //
     if (isNotUsedInLoop(I, CurLoop, SafetyInfo) &&
         canSinkOrHoistInst(I, AA, DT, TLI, CurLoop, CurAST, SafetyInfo)) {
       ++II;
       Changed |= sink(I, LI, DT, CurLoop, CurAST, SafetyInfo);
     }
   }
   return Changed;
 }
 
 /// Walk the specified region of the CFG (defined by all blocks dominated by
 /// the specified block, and that are in the current loop) in depth first
 /// order w.r.t the DominatorTree.  This allows us to visit definitions before
 /// uses, allowing us to hoist a loop body in one pass without iteration.
 ///
 bool llvm::hoistRegion(DomTreeNode *N, AliasAnalysis *AA, LoopInfo *LI,
                        DominatorTree *DT, TargetLibraryInfo *TLI, Loop *CurLoop,
                        AliasSetTracker *CurAST, LICMSafetyInfo *SafetyInfo) {
   // 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).

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
 ; 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 {
+; CHECK-LABEL: @main(
+entry:
+; CHECK: entry:
+; CHECK-NEXT: br label %outer.header
+  br label %outer.header
+
+outer.header:
+; CHECK: outer.header:
+; CHECK: br i1 undef, label %if.then, label %outer.latch
+  br i1 undef, label %if.then, label %outer.latch
+
+if.then:
+; CHECK: if.then:
+  %call = tail call i32 @generate()
+; CHECK: br label %inner.body
+  br label %inner.body
+
+inner.body:
+; CHECK: 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-sink-multiple-phi.ll

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