Index: llvm/trunk/include/llvm/Analysis/LoopInfo.h =================================================================== --- llvm/trunk/include/llvm/Analysis/LoopInfo.h +++ llvm/trunk/include/llvm/Analysis/LoopInfo.h @@ -146,11 +146,11 @@ bool empty() const { return getSubLoops().empty(); } /// Get a list of the basic blocks which make up this loop. - const std::vector &getBlocks() const { + ArrayRef getBlocks() const { assert(!isInvalid() && "Loop not in a valid state!"); return Blocks; } - typedef typename std::vector::const_iterator block_iterator; + typedef typename ArrayRef::const_iterator block_iterator; block_iterator block_begin() const { return getBlocks().begin(); } block_iterator block_end() const { return getBlocks().end(); } inline iterator_range blocks() const { @@ -165,6 +165,19 @@ return Blocks.size(); } + /// Return a direct, mutable handle to the blocks vector so that we can + /// mutate it efficiently with techniques like `std::remove`. + std::vector &getBlocksVector() { + assert(!isInvalid() && "Loop not in a valid state!"); + return Blocks; + } + /// Return a direct, mutable handle to the blocks set so that we can + /// mutate it efficiently. + SmallPtrSetImpl &getBlocksSet() { + assert(!isInvalid() && "Loop not in a valid state!"); + return DenseBlockSet; + } + /// Return true if this loop is no longer valid. The only valid use of this /// helper is "assert(L.isInvalid())" or equivalent, since IsInvalid is set to /// true by the destructor. In other words, if this accessor returns true, @@ -314,6 +327,12 @@ return Child; } + /// This removes the specified child from being a subloop of this loop. The + /// loop is not deleted, as it will presumably be inserted into another loop. + LoopT *removeChildLoop(LoopT *Child) { + return removeChildLoop(llvm::find(*this, Child)); + } + /// This adds a basic block directly to the basic block list. /// This should only be used by transformations that create new loops. Other /// transformations should use addBasicBlockToLoop. @@ -744,9 +763,16 @@ void verify(const DominatorTreeBase &DomTree) const; -protected: - // Calls the destructor for \p L but keeps the memory for \p L around so that - // the pointer value does not get re-used. + /// Destroy a loop that has been removed from the `LoopInfo` nest. + /// + /// This runs the destructor of the loop object making it invalid to + /// reference afterward. The memory is retained so that the *pointer* to the + /// loop remains valid. + /// + /// The caller is responsible for removing this loop from the loop nest and + /// otherwise disconnecting it from the broader `LoopInfo` data structures. + /// Callers that don't naturally handle this themselves should probably call + /// `erase' instead. void destroy(LoopT *L) { L->~LoopT(); Index: llvm/trunk/include/llvm/Analysis/LoopInfoImpl.h =================================================================== --- llvm/trunk/include/llvm/Analysis/LoopInfoImpl.h +++ llvm/trunk/include/llvm/Analysis/LoopInfoImpl.h @@ -400,7 +400,7 @@ // Discover a subloop of this loop. Subloop->setParentLoop(L); ++NumSubloops; - NumBlocks += Subloop->getBlocks().capacity(); + NumBlocks += Subloop->getBlocksVector().capacity(); PredBB = Subloop->getHeader(); // Continue traversal along predecessors that are not loop-back edges from // within this subloop tree itself. Note that a predecessor may directly Index: llvm/trunk/include/llvm/Transforms/Scalar/LoopPassManager.h =================================================================== --- llvm/trunk/include/llvm/Transforms/Scalar/LoopPassManager.h +++ llvm/trunk/include/llvm/Transforms/Scalar/LoopPassManager.h @@ -217,6 +217,19 @@ // shouldn't impact anything. } + /// Restart the current loop. + /// + /// Loop passes should call this method to indicate the current loop has been + /// sufficiently changed that it should be re-visited from the begining of + /// the loop pass pipeline rather than continuing. + void revisitCurrentLoop() { + // Tell the currently in-flight pipeline to stop running. + SkipCurrentLoop = true; + + // And insert ourselves back into the worklist. + Worklist.insert(CurrentL); + } + private: template friend class llvm::FunctionToLoopPassAdaptor; Index: llvm/trunk/include/llvm/Transforms/Scalar/SimpleLoopUnswitch.h =================================================================== --- llvm/trunk/include/llvm/Transforms/Scalar/SimpleLoopUnswitch.h +++ llvm/trunk/include/llvm/Transforms/Scalar/SimpleLoopUnswitch.h @@ -36,8 +36,10 @@ /// of the loop, to make the unswitching opportunity obvious. /// class SimpleLoopUnswitchPass : public PassInfoMixin { + bool NonTrivial; + public: - SimpleLoopUnswitchPass() = default; + SimpleLoopUnswitchPass(bool NonTrivial = false) : NonTrivial(NonTrivial) {} PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR, LPMUpdater &U); @@ -46,7 +48,7 @@ /// Create the legacy pass object for the simple loop unswitcher. /// /// See the documentaion for `SimpleLoopUnswitchPass` for details. -Pass *createSimpleLoopUnswitchLegacyPass(); +Pass *createSimpleLoopUnswitchLegacyPass(bool NonTrivial = false); } // end namespace llvm Index: llvm/trunk/lib/Analysis/LoopPass.cpp =================================================================== --- llvm/trunk/lib/Analysis/LoopPass.cpp +++ llvm/trunk/lib/Analysis/LoopPass.cpp @@ -46,8 +46,7 @@ } bool runOnLoop(Loop *L, LPPassManager &) override { - auto BBI = find_if(L->blocks().begin(), L->blocks().end(), - [](BasicBlock *BB) { return BB; }); + auto BBI = llvm::find_if(L->blocks(), [](BasicBlock *BB) { return BB; }); if (BBI != L->blocks().end() && isFunctionInPrintList((*BBI)->getParent()->getName())) { printLoop(*L, OS, Banner); Index: llvm/trunk/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp =================================================================== --- llvm/trunk/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp +++ llvm/trunk/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp @@ -17,6 +17,7 @@ #include "llvm/ADT/Statistic.h" #include "llvm/ADT/Twine.h" #include "llvm/Analysis/AssumptionCache.h" +#include "llvm/Analysis/CodeMetrics.h" #include "llvm/Analysis/LoopAnalysisManager.h" #include "llvm/Analysis/LoopInfo.h" #include "llvm/Analysis/LoopPass.h" @@ -28,6 +29,7 @@ #include "llvm/IR/InstrTypes.h" #include "llvm/IR/Instruction.h" #include "llvm/IR/Instructions.h" +#include "llvm/IR/IntrinsicInst.h" #include "llvm/IR/Use.h" #include "llvm/IR/Value.h" #include "llvm/Pass.h" @@ -36,11 +38,15 @@ #include "llvm/Support/ErrorHandling.h" #include "llvm/Support/GenericDomTree.h" #include "llvm/Support/raw_ostream.h" +#include "llvm/Transforms/Scalar/SimpleLoopUnswitch.h" #include "llvm/Transforms/Utils/BasicBlockUtils.h" +#include "llvm/Transforms/Utils/Cloning.h" #include "llvm/Transforms/Utils/LoopUtils.h" +#include "llvm/Transforms/Utils/ValueMapper.h" #include #include #include +#include #include #define DEBUG_TYPE "simple-loop-unswitch" @@ -51,6 +57,15 @@ STATISTIC(NumSwitches, "Number of switches unswitched"); STATISTIC(NumTrivial, "Number of unswitches that are trivial"); +static cl::opt EnableNonTrivialUnswitch( + "enable-nontrivial-unswitch", cl::init(false), cl::Hidden, + cl::desc("Forcibly enables non-trivial loop unswitching rather than " + "following the configuration passed into the pass.")); + +static cl::opt + UnswitchThreshold("unswitch-threshold", cl::init(50), cl::Hidden, + cl::desc("The cost threshold for unswitching a loop.")); + static void replaceLoopUsesWithConstant(Loop &L, Value &LIC, Constant &Replacement) { assert(!isa(LIC) && "Why are we unswitching on a constant?"); @@ -68,24 +83,95 @@ } } -/// Update the dominator tree after removing one exiting predecessor of a loop -/// exit block. -static void updateLoopExitIDom(BasicBlock *LoopExitBB, Loop &L, - DominatorTree &DT) { - assert(pred_begin(LoopExitBB) != pred_end(LoopExitBB) && - "Cannot have empty predecessors of the loop exit block if we split " - "off a block to unswitch!"); +/// Update the IDom for a basic block whose predecessor set has changed. +/// +/// This routine is designed to work when the domtree update is relatively +/// localized by leveraging a known common dominator, often a loop header. +/// +/// FIXME: Should consider hand-rolling a slightly more efficient non-DFS +/// approach here as we can do that easily by persisting the candidate IDom's +/// dominating set between each predecessor. +/// +/// FIXME: Longer term, many uses of this can be replaced by an incremental +/// domtree update strategy that starts from a known dominating block and +/// rebuilds that subtree. +static bool updateIDomWithKnownCommonDominator(BasicBlock *BB, + BasicBlock *KnownDominatingBB, + DominatorTree &DT) { + assert(pred_begin(BB) != pred_end(BB) && + "This routine does not handle unreachable blocks!"); + + BasicBlock *OrigIDom = DT[BB]->getIDom()->getBlock(); + + BasicBlock *IDom = *pred_begin(BB); + assert(DT.dominates(KnownDominatingBB, IDom) && + "Bad known dominating block!"); - BasicBlock *IDom = *pred_begin(LoopExitBB); // Walk all of the other predecessors finding the nearest common dominator // until all predecessors are covered or we reach the loop header. The loop // header necessarily dominates all loop exit blocks in loop simplified form // so we can early-exit the moment we hit that block. - for (auto PI = std::next(pred_begin(LoopExitBB)), PE = pred_end(LoopExitBB); - PI != PE && IDom != L.getHeader(); ++PI) + for (auto PI = std::next(pred_begin(BB)), PE = pred_end(BB); + PI != PE && IDom != KnownDominatingBB; ++PI) { + assert(DT.dominates(KnownDominatingBB, *PI) && + "Bad known dominating block!"); IDom = DT.findNearestCommonDominator(IDom, *PI); + } + + if (IDom == OrigIDom) + return false; - DT.changeImmediateDominator(LoopExitBB, IDom); + DT.changeImmediateDominator(BB, IDom); + return true; +} + +// Note that we don't currently use the IDFCalculator here for two reasons: +// 1) It computes dominator tree levels for the entire function on each run +// of 'compute'. While this isn't terrible, given that we expect to update +// relatively small subtrees of the domtree, it isn't necessarily the right +// tradeoff. +// 2) The interface doesn't fit this usage well. It doesn't operate in +// append-only, and builds several sets that we don't need. +// +// FIXME: Neither of these issues are a big deal and could be addressed with +// some amount of refactoring of IDFCalculator. That would allow us to share +// the core logic here (which is solving the same core problem). +void appendDomFrontier(DomTreeNode *Node, + SmallSetVector &Worklist, + SmallVectorImpl &DomNodes, + SmallPtrSetImpl &DomSet) { + assert(DomNodes.empty() && "Must start with no dominator nodes."); + assert(DomSet.empty() && "Must start with an empty dominator set."); + + // First flatten this subtree into sequence of nodes by doing a pre-order + // walk. + DomNodes.push_back(Node); + // We intentionally re-evaluate the size as each node can add new children. + // Because this is a tree walk, this cannot add any duplicates. + for (int i = 0; i < (int)DomNodes.size(); ++i) + DomNodes.insert(DomNodes.end(), DomNodes[i]->begin(), DomNodes[i]->end()); + + // Now create a set of the basic blocks so we can quickly test for + // dominated successors. We could in theory use the DFS numbers of the + // dominator tree for this, but we want this to remain predictably fast + // even while we mutate the dominator tree in ways that would invalidate + // the DFS numbering. + for (DomTreeNode *InnerN : DomNodes) + DomSet.insert(InnerN->getBlock()); + + // Now re-walk the nodes, appending every successor of every node that isn't + // in the set. Note that we don't append the node itself, even though if it + // is a successor it does not strictly dominate itself and thus it would be + // part of the dominance frontier. The reason we don't append it is that + // the node passed in came *from* the worklist and so it has already been + // processed. + for (DomTreeNode *InnerN : DomNodes) + for (BasicBlock *SuccBB : successors(InnerN->getBlock())) + if (!DomSet.count(SuccBB)) + Worklist.insert(SuccBB); + + DomNodes.clear(); + DomSet.clear(); } /// Update the dominator tree after unswitching a particular former exit block. @@ -127,58 +213,14 @@ // dominator frontier to see if it additionally should move up the dominator // tree. This lambda appends the dominator frontier for a node on the // worklist. - // - // Note that we don't currently use the IDFCalculator here for two reasons: - // 1) It computes dominator tree levels for the entire function on each run - // of 'compute'. While this isn't terrible, given that we expect to update - // relatively small subtrees of the domtree, it isn't necessarily the right - // tradeoff. - // 2) The interface doesn't fit this usage well. It doesn't operate in - // append-only, and builds several sets that we don't need. - // - // FIXME: Neither of these issues are a big deal and could be addressed with - // some amount of refactoring of IDFCalculator. That would allow us to share - // the core logic here (which is solving the same core problem). SmallSetVector Worklist; + + // Scratch data structures reused by domfrontier finding. SmallVector DomNodes; SmallPtrSet DomSet; - auto AppendDomFrontier = [&](DomTreeNode *Node) { - assert(DomNodes.empty() && "Must start with no dominator nodes."); - assert(DomSet.empty() && "Must start with an empty dominator set."); - - // First flatten this subtree into sequence of nodes by doing a pre-order - // walk. - DomNodes.push_back(Node); - // We intentionally re-evaluate the size as each node can add new children. - // Because this is a tree walk, this cannot add any duplicates. - for (int i = 0; i < (int)DomNodes.size(); ++i) - DomNodes.insert(DomNodes.end(), DomNodes[i]->begin(), DomNodes[i]->end()); - - // Now create a set of the basic blocks so we can quickly test for - // dominated successors. We could in theory use the DFS numbers of the - // dominator tree for this, but we want this to remain predictably fast - // even while we mutate the dominator tree in ways that would invalidate - // the DFS numbering. - for (DomTreeNode *InnerN : DomNodes) - DomSet.insert(InnerN->getBlock()); - - // Now re-walk the nodes, appending every successor of every node that isn't - // in the set. Note that we don't append the node itself, even though if it - // is a successor it does not strictly dominate itself and thus it would be - // part of the dominance frontier. The reason we don't append it is that - // the node passed in came *from* the worklist and so it has already been - // processed. - for (DomTreeNode *InnerN : DomNodes) - for (BasicBlock *SuccBB : successors(InnerN->getBlock())) - if (!DomSet.count(SuccBB)) - Worklist.insert(SuccBB); - - DomNodes.clear(); - DomSet.clear(); - }; // Append the initial dom frontier nodes. - AppendDomFrontier(UnswitchedNode); + appendDomFrontier(UnswitchedNode, Worklist, DomNodes, DomSet); // Walk the worklist. We grow the list in the loop and so must recompute size. for (int i = 0; i < (int)Worklist.size(); ++i) { @@ -197,7 +239,7 @@ DT.changeImmediateDominator(Node, OldPHNode); // Now add this node's dominator frontier to the worklist as well. - AppendDomFrontier(Node); + appendDomFrontier(Node, Worklist, DomNodes, DomSet); } } @@ -395,7 +437,7 @@ // one of the predecessors for the loop exit block and may need to update its // idom. if (UnswitchedBB != LoopExitBB) - updateLoopExitIDom(LoopExitBB, L, DT); + updateIDomWithKnownCommonDominator(LoopExitBB, L.getHeader(), DT); // Since this is an i1 condition we can also trivially replace uses of it // within the loop with a constant. @@ -540,7 +582,7 @@ SplitBlock(DefaultExitBB, &DefaultExitBB->front(), &DT, &LI); rewritePHINodesForExitAndUnswitchedBlocks(*DefaultExitBB, *SplitBB, *ParentBB, *OldPH); - updateLoopExitIDom(DefaultExitBB, L, DT); + updateIDomWithKnownCommonDominator(DefaultExitBB, L.getHeader(), DT); DefaultExitBB = SplitExitBBMap[DefaultExitBB] = SplitBB; } } @@ -567,7 +609,7 @@ SplitExitBB = SplitBlock(ExitBB, &ExitBB->front(), &DT, &LI); rewritePHINodesForExitAndUnswitchedBlocks(*ExitBB, *SplitExitBB, *ParentBB, *OldPH); - updateLoopExitIDom(ExitBB, L, DT); + updateIDomWithKnownCommonDominator(ExitBB, L.getHeader(), DT); } // Update the case pair to point to the split block. CasePair.second = SplitExitBB; @@ -708,15 +750,1172 @@ return Changed; } +/// Build the cloned blocks for an unswitched copy of the given loop. +/// +/// The cloned blocks are inserted before the loop preheader (`LoopPH`) and +/// after the split block (`SplitBB`) that will be used to select between the +/// cloned and original loop. +/// +/// This routine handles cloning all of the necessary loop blocks and exit +/// blocks including rewriting their instructions and the relevant PHI nodes. +/// It skips loop and exit blocks that are not necessary based on the provided +/// set. It also correctly creates the unconditional branch in the cloned +/// unswitched parent block to only point at the unswitched successor. +/// +/// This does not handle most of the necessary updates to `LoopInfo`. Only exit +/// block splitting is correctly reflected in `LoopInfo`, essentially all of +/// the cloned blocks (and their loops) are left without full `LoopInfo` +/// updates. This also doesn't fully update `DominatorTree`. It adds the cloned +/// blocks to them but doesn't create the cloned `DominatorTree` structure and +/// instead the caller must recompute an accurate DT. It *does* correctly +/// update the `AssumptionCache` provided in `AC`. +static BasicBlock *buildClonedLoopBlocks( + Loop &L, BasicBlock *LoopPH, BasicBlock *SplitBB, + ArrayRef ExitBlocks, BasicBlock *ParentBB, + BasicBlock *UnswitchedSuccBB, BasicBlock *ContinueSuccBB, + const SmallPtrSetImpl &SkippedLoopAndExitBlocks, + ValueToValueMapTy &VMap, AssumptionCache &AC, DominatorTree &DT, + LoopInfo &LI) { + SmallVector NewBlocks; + NewBlocks.reserve(L.getNumBlocks() + ExitBlocks.size()); + + // We will need to clone a bunch of blocks, wrap up the clone operation in + // a helper. + auto CloneBlock = [&](BasicBlock *OldBB) { + // Clone the basic block and insert it before the new preheader. + BasicBlock *NewBB = CloneBasicBlock(OldBB, VMap, ".us", OldBB->getParent()); + NewBB->moveBefore(LoopPH); + + // Record this block and the mapping. + NewBlocks.push_back(NewBB); + VMap[OldBB] = NewBB; + + // Add the block to the domtree. We'll move it to the correct position + // below. + DT.addNewBlock(NewBB, SplitBB); + + return NewBB; + }; + + // First, clone the preheader. + auto *ClonedPH = CloneBlock(LoopPH); + + // Then clone all the loop blocks, skipping the ones that aren't necessary. + for (auto *LoopBB : L.blocks()) + if (!SkippedLoopAndExitBlocks.count(LoopBB)) + CloneBlock(LoopBB); + + // Split all the loop exit edges so that when we clone the exit blocks, if + // any of the exit blocks are *also* a preheader for some other loop, we + // don't create multiple predecessors entering the loop header. + for (auto *ExitBB : ExitBlocks) { + if (SkippedLoopAndExitBlocks.count(ExitBB)) + continue; + + // When we are going to clone an exit, we don't need to clone all the + // instructions in the exit block and we want to ensure we have an easy + // place to merge the CFG, so split the exit first. This is always safe to + // do because there cannot be any non-loop predecessors of a loop exit in + // loop simplified form. + auto *MergeBB = SplitBlock(ExitBB, &ExitBB->front(), &DT, &LI); + + // Rearrange the names to make it easier to write test cases by having the + // exit block carry the suffix rather than the merge block carrying the + // suffix. + MergeBB->takeName(ExitBB); + ExitBB->setName(Twine(MergeBB->getName()) + ".split"); + + // Now clone the original exit block. + auto *ClonedExitBB = CloneBlock(ExitBB); + assert(ClonedExitBB->getTerminator()->getNumSuccessors() == 1 && + "Exit block should have been split to have one successor!"); + assert(ClonedExitBB->getTerminator()->getSuccessor(0) == MergeBB && + "Cloned exit block has the wrong successor!"); + + // Move the merge block's idom to be the split point as one exit is + // dominated by one header, and the other by another, so we know the split + // point dominates both. While the dominator tree isn't fully accurate, we + // want sub-trees within the original loop to be correctly reflect + // dominance within that original loop (at least) and that requires moving + // the merge block out of that subtree. + // FIXME: This is very brittle as we essentially have a partial contract on + // the dominator tree. We really need to instead update it and keep it + // valid or stop relying on it. + DT.changeImmediateDominator(MergeBB, SplitBB); + + // Remap any cloned instructions and create a merge phi node for them. + for (auto ZippedInsts : llvm::zip_first( + llvm::make_range(ExitBB->begin(), std::prev(ExitBB->end())), + llvm::make_range(ClonedExitBB->begin(), + std::prev(ClonedExitBB->end())))) { + Instruction &I = std::get<0>(ZippedInsts); + Instruction &ClonedI = std::get<1>(ZippedInsts); + + // The only instructions in the exit block should be PHI nodes and + // potentially a landing pad. + assert( + (isa(I) || isa(I) || isa(I)) && + "Bad instruction in exit block!"); + // We should have a value map between the instruction and its clone. + assert(VMap.lookup(&I) == &ClonedI && "Mismatch in the value map!"); + + auto *MergePN = + PHINode::Create(I.getType(), /*NumReservedValues*/ 2, ".us-phi", + &*MergeBB->getFirstInsertionPt()); + I.replaceAllUsesWith(MergePN); + MergePN->addIncoming(&I, ExitBB); + MergePN->addIncoming(&ClonedI, ClonedExitBB); + } + } + + // Rewrite the instructions in the cloned blocks to refer to the instructions + // in the cloned blocks. We have to do this as a second pass so that we have + // everything available. Also, we have inserted new instructions which may + // include assume intrinsics, so we update the assumption cache while + // processing this. + for (auto *ClonedBB : NewBlocks) + for (Instruction &I : *ClonedBB) { + RemapInstruction(&I, VMap, + RF_NoModuleLevelChanges | RF_IgnoreMissingLocals); + if (auto *II = dyn_cast(&I)) + if (II->getIntrinsicID() == Intrinsic::assume) + AC.registerAssumption(II); + } + + // Remove the cloned parent as a predecessor of the cloned continue successor + // if we did in fact clone it. + auto *ClonedParentBB = cast(VMap.lookup(ParentBB)); + if (auto *ClonedContinueSuccBB = + cast_or_null(VMap.lookup(ContinueSuccBB))) + ClonedContinueSuccBB->removePredecessor(ClonedParentBB, + /*DontDeleteUselessPHIs*/ true); + // Replace the cloned branch with an unconditional branch to the cloneed + // unswitched successor. + auto *ClonedSuccBB = cast(VMap.lookup(UnswitchedSuccBB)); + ClonedParentBB->getTerminator()->eraseFromParent(); + BranchInst::Create(ClonedSuccBB, ClonedParentBB); + + // Update any PHI nodes in the cloned successors of the skipped blocks to not + // have spurious incoming values. + for (auto *LoopBB : L.blocks()) + if (SkippedLoopAndExitBlocks.count(LoopBB)) + for (auto *SuccBB : successors(LoopBB)) + if (auto *ClonedSuccBB = cast_or_null(VMap.lookup(SuccBB))) + for (PHINode &PN : ClonedSuccBB->phis()) + PN.removeIncomingValue(LoopBB, /*DeletePHIIfEmpty*/ false); + + return ClonedPH; +} + +/// Recursively clone the specified loop and all of its children. +/// +/// The target parent loop for the clone should be provided, or can be null if +/// the clone is a top-level loop. While cloning, all the blocks are mapped +/// with the provided value map. The entire original loop must be present in +/// the value map. The cloned loop is returned. +static Loop *cloneLoopNest(Loop &OrigRootL, Loop *RootParentL, + const ValueToValueMapTy &VMap, LoopInfo &LI) { + auto AddClonedBlocksToLoop = [&](Loop &OrigL, Loop &ClonedL) { + assert(ClonedL.getBlocks().empty() && "Must start with an empty loop!"); + ClonedL.reserveBlocks(OrigL.getNumBlocks()); + for (auto *BB : OrigL.blocks()) { + auto *ClonedBB = cast(VMap.lookup(BB)); + ClonedL.addBlockEntry(ClonedBB); + if (LI.getLoopFor(BB) == &OrigL) { + assert(!LI.getLoopFor(ClonedBB) && + "Should not have an existing loop for this block!"); + LI.changeLoopFor(ClonedBB, &ClonedL); + } + } + }; + + // We specially handle the first loop because it may get cloned into + // a different parent and because we most commonly are cloning leaf loops. + Loop *ClonedRootL = LI.AllocateLoop(); + if (RootParentL) + RootParentL->addChildLoop(ClonedRootL); + else + LI.addTopLevelLoop(ClonedRootL); + AddClonedBlocksToLoop(OrigRootL, *ClonedRootL); + + if (OrigRootL.empty()) + return ClonedRootL; + + // If we have a nest, we can quickly clone the entire loop nest using an + // iterative approach because it is a tree. We keep the cloned parent in the + // data structure to avoid repeatedly querying through a map to find it. + SmallVector, 16> LoopsToClone; + // Build up the loops to clone in reverse order as we'll clone them from the + // back. + for (Loop *ChildL : llvm::reverse(OrigRootL)) + LoopsToClone.push_back({ClonedRootL, ChildL}); + do { + Loop *ClonedParentL, *L; + std::tie(ClonedParentL, L) = LoopsToClone.pop_back_val(); + Loop *ClonedL = LI.AllocateLoop(); + ClonedParentL->addChildLoop(ClonedL); + AddClonedBlocksToLoop(*L, *ClonedL); + for (Loop *ChildL : llvm::reverse(*L)) + LoopsToClone.push_back({ClonedL, ChildL}); + } while (!LoopsToClone.empty()); + + return ClonedRootL; +} + +/// Build the cloned loops of an original loop from unswitching. +/// +/// Because unswitching simplifies the CFG of the loop, this isn't a trivial +/// operation. We need to re-verify that there even is a loop (as the backedge +/// may not have been cloned), and even if there are remaining backedges the +/// backedge set may be different. However, we know that each child loop is +/// undisturbed, we only need to find where to place each child loop within +/// either any parent loop or within a cloned version of the original loop. +/// +/// Because child loops may end up cloned outside of any cloned version of the +/// original loop, multiple cloned sibling loops may be created. All of them +/// are returned so that the newly introduced loop nest roots can be +/// identified. +static Loop *buildClonedLoops(Loop &OrigL, ArrayRef ExitBlocks, + const ValueToValueMapTy &VMap, LoopInfo &LI, + SmallVectorImpl &NonChildClonedLoops) { + Loop *ClonedL = nullptr; + + auto *OrigPH = OrigL.getLoopPreheader(); + auto *OrigHeader = OrigL.getHeader(); + + auto *ClonedPH = cast(VMap.lookup(OrigPH)); + auto *ClonedHeader = cast(VMap.lookup(OrigHeader)); + + // We need to know the loops of the cloned exit blocks to even compute the + // accurate parent loop. If we only clone exits to some parent of the + // original parent, we want to clone into that outer loop. We also keep track + // of the loops that our cloned exit blocks participate in. + Loop *ParentL = nullptr; + SmallVector ClonedExitsInLoops; + SmallDenseMap ExitLoopMap; + ClonedExitsInLoops.reserve(ExitBlocks.size()); + for (auto *ExitBB : ExitBlocks) + if (auto *ClonedExitBB = cast_or_null(VMap.lookup(ExitBB))) + if (Loop *ExitL = LI.getLoopFor(ExitBB)) { + ExitLoopMap[ClonedExitBB] = ExitL; + ClonedExitsInLoops.push_back(ClonedExitBB); + if (!ParentL || (ParentL != ExitL && ParentL->contains(ExitL))) + ParentL = ExitL; + } + assert((!ParentL || ParentL == OrigL.getParentLoop() || + ParentL->contains(OrigL.getParentLoop())) && + "The computed parent loop should always contain (or be) the parent of " + "the original loop."); + + // We build the set of blocks dominated by the cloned header from the set of + // cloned blocks out of the original loop. While not all of these will + // necessarily be in the cloned loop, it is enough to establish that they + // aren't in unreachable cycles, etc. + SmallSetVector ClonedLoopBlocks; + for (auto *BB : OrigL.blocks()) + if (auto *ClonedBB = cast_or_null(VMap.lookup(BB))) + ClonedLoopBlocks.insert(ClonedBB); + + // Rebuild the set of blocks that will end up in the cloned loop. We may have + // skipped cloning some region of this loop which can in turn skip some of + // the backedges so we have to rebuild the blocks in the loop based on the + // backedges that remain after cloning. + SmallVector Worklist; + SmallPtrSet BlocksInClonedLoop; + for (auto *Pred : predecessors(ClonedHeader)) { + // The only possible non-loop header predecessor is the preheader because + // we know we cloned the loop in simplified form. + if (Pred == ClonedPH) + continue; + + // Because the loop was in simplified form, the only non-loop predecessor + // should be the preheader. + assert(ClonedLoopBlocks.count(Pred) && "Found a predecessor of the loop " + "header other than the preheader " + "that is not part of the loop!"); + + // Insert this block into the loop set and on the first visit (and if it + // isn't the header we're currently walking) put it into the worklist to + // recurse through. + if (BlocksInClonedLoop.insert(Pred).second && Pred != ClonedHeader) + Worklist.push_back(Pred); + } + + // If we had any backedges then there *is* a cloned loop. Put the header into + // the loop set and then walk the worklist backwards to find all the blocks + // that remain within the loop after cloning. + if (!BlocksInClonedLoop.empty()) { + BlocksInClonedLoop.insert(ClonedHeader); + + while (!Worklist.empty()) { + BasicBlock *BB = Worklist.pop_back_val(); + assert(BlocksInClonedLoop.count(BB) && + "Didn't put block into the loop set!"); + + // Insert any predecessors that are in the possible set into the cloned + // set, and if the insert is successful, add them to the worklist. Note + // that we filter on the blocks that are definitely reachable via the + // backedge to the loop header so we may prune out dead code within the + // cloned loop. + for (auto *Pred : predecessors(BB)) + if (ClonedLoopBlocks.count(Pred) && + BlocksInClonedLoop.insert(Pred).second) + Worklist.push_back(Pred); + } + + ClonedL = LI.AllocateLoop(); + if (ParentL) { + ParentL->addBasicBlockToLoop(ClonedPH, LI); + ParentL->addChildLoop(ClonedL); + } else { + LI.addTopLevelLoop(ClonedL); + } + + ClonedL->reserveBlocks(BlocksInClonedLoop.size()); + // We don't want to just add the cloned loop blocks based on how we + // discovered them. The original order of blocks was carefully built in + // a way that doesn't rely on predecessor ordering. Rather than re-invent + // that logic, we just re-walk the original blocks (and those of the child + // loops) and filter them as we add them into the cloned loop. + for (auto *BB : OrigL.blocks()) { + auto *ClonedBB = cast_or_null(VMap.lookup(BB)); + if (!ClonedBB || !BlocksInClonedLoop.count(ClonedBB)) + continue; + + // Directly add the blocks that are only in this loop. + if (LI.getLoopFor(BB) == &OrigL) { + ClonedL->addBasicBlockToLoop(ClonedBB, LI); + continue; + } + + // We want to manually add it to this loop and parents. + // Registering it with LoopInfo will happen when we clone the top + // loop for this block. + for (Loop *PL = ClonedL; PL; PL = PL->getParentLoop()) + PL->addBlockEntry(ClonedBB); + } + + // Now add each child loop whose header remains within the cloned loop. All + // of the blocks within the loop must satisfy the same constraints as the + // header so once we pass the header checks we can just clone the entire + // child loop nest. + for (Loop *ChildL : OrigL) { + auto *ClonedChildHeader = + cast_or_null(VMap.lookup(ChildL->getHeader())); + if (!ClonedChildHeader || !BlocksInClonedLoop.count(ClonedChildHeader)) + continue; + +#ifndef NDEBUG + // We should never have a cloned child loop header but fail to have + // all of the blocks for that child loop. + for (auto *ChildLoopBB : ChildL->blocks()) + assert(BlocksInClonedLoop.count( + cast(VMap.lookup(ChildLoopBB))) && + "Child cloned loop has a header within the cloned outer " + "loop but not all of its blocks!"); +#endif + + cloneLoopNest(*ChildL, ClonedL, VMap, LI); + } + } + + // Now that we've handled all the components of the original loop that were + // cloned into a new loop, we still need to handle anything from the original + // loop that wasn't in a cloned loop. + + // Figure out what blocks are left to place within any loop nest containing + // the unswitched loop. If we never formed a loop, the cloned PH is one of + // them. + SmallPtrSet UnloopedBlockSet; + if (BlocksInClonedLoop.empty()) + UnloopedBlockSet.insert(ClonedPH); + for (auto *ClonedBB : ClonedLoopBlocks) + if (!BlocksInClonedLoop.count(ClonedBB)) + UnloopedBlockSet.insert(ClonedBB); + + // Copy the cloned exits and sort them in ascending loop depth, we'll work + // backwards across these to process them inside out. The order shouldn't + // matter as we're just trying to build up the map from inside-out; we use + // the map in a more stably ordered way below. + auto OrderedClonedExitsInLoops = ClonedExitsInLoops; + std::sort(OrderedClonedExitsInLoops.begin(), OrderedClonedExitsInLoops.end(), + [&](BasicBlock *LHS, BasicBlock *RHS) { + return ExitLoopMap.lookup(LHS)->getLoopDepth() < + ExitLoopMap.lookup(RHS)->getLoopDepth(); + }); + + // Populate the existing ExitLoopMap with everything reachable from each + // exit, starting from the inner most exit. + while (!UnloopedBlockSet.empty() && !OrderedClonedExitsInLoops.empty()) { + assert(Worklist.empty() && "Didn't clear worklist!"); + + BasicBlock *ExitBB = OrderedClonedExitsInLoops.pop_back_val(); + Loop *ExitL = ExitLoopMap.lookup(ExitBB); + + // Walk the CFG back until we hit the cloned PH adding everything reachable + // and in the unlooped set to this exit block's loop. + Worklist.push_back(ExitBB); + do { + BasicBlock *BB = Worklist.pop_back_val(); + // We can stop recursing at the cloned preheader (if we get there). + if (BB == ClonedPH) + continue; + + for (BasicBlock *PredBB : predecessors(BB)) { + // If this pred has already been moved to our set or is part of some + // (inner) loop, no update needed. + if (!UnloopedBlockSet.erase(PredBB)) { + assert( + (BlocksInClonedLoop.count(PredBB) || ExitLoopMap.count(PredBB)) && + "Predecessor not mapped to a loop!"); + continue; + } + + // We just insert into the loop set here. We'll add these blocks to the + // exit loop after we build up the set in an order that doesn't rely on + // predecessor order (which in turn relies on use list order). + bool Inserted = ExitLoopMap.insert({PredBB, ExitL}).second; + (void)Inserted; + assert(Inserted && "Should only visit an unlooped block once!"); + + // And recurse through to its predecessors. + Worklist.push_back(PredBB); + } + } while (!Worklist.empty()); + } + + // Now that the ExitLoopMap gives as mapping for all the non-looping cloned + // blocks to their outer loops, walk the cloned blocks and the cloned exits + // in their original order adding them to the correct loop. + + // We need a stable insertion order. We use the order of the original loop + // order and map into the correct parent loop. + for (auto *BB : llvm::concat( + makeArrayRef(ClonedPH), ClonedLoopBlocks, ClonedExitsInLoops)) + if (Loop *OuterL = ExitLoopMap.lookup(BB)) + OuterL->addBasicBlockToLoop(BB, LI); + +#ifndef NDEBUG + for (auto &BBAndL : ExitLoopMap) { + auto *BB = BBAndL.first; + auto *OuterL = BBAndL.second; + assert(LI.getLoopFor(BB) == OuterL && + "Failed to put all blocks into outer loops!"); + } +#endif + + // Now that all the blocks are placed into the correct containing loop in the + // absence of child loops, find all the potentially cloned child loops and + // clone them into whatever outer loop we placed their header into. + for (Loop *ChildL : OrigL) { + auto *ClonedChildHeader = + cast_or_null(VMap.lookup(ChildL->getHeader())); + if (!ClonedChildHeader || BlocksInClonedLoop.count(ClonedChildHeader)) + continue; + +#ifndef NDEBUG + for (auto *ChildLoopBB : ChildL->blocks()) + assert(VMap.count(ChildLoopBB) && + "Cloned a child loop header but not all of that loops blocks!"); +#endif + + NonChildClonedLoops.push_back(cloneLoopNest( + *ChildL, ExitLoopMap.lookup(ClonedChildHeader), VMap, LI)); + } + + // Return the main cloned loop if any. + return ClonedL; +} + +static void deleteDeadBlocksFromLoop(Loop &L, BasicBlock *DeadSubtreeRoot, + SmallVectorImpl &ExitBlocks, + DominatorTree &DT, LoopInfo &LI) { + // Walk the dominator tree to build up the set of blocks we will delete here. + // The order is designed to allow us to always delete bottom-up and avoid any + // dangling uses. + SmallSetVector DeadBlocks; + DeadBlocks.insert(DeadSubtreeRoot); + for (int i = 0; i < (int)DeadBlocks.size(); ++i) + for (DomTreeNode *ChildN : *DT[DeadBlocks[i]]) { + // FIXME: This assert should pass and that means we don't change nearly + // as much below! Consider rewriting all of this to avoid deleting + // blocks. They are always cloned before being deleted, and so instead + // could just be moved. + // FIXME: This in turn means that we might actually be more able to + // update the domtree. + assert((L.contains(ChildN->getBlock()) || + llvm::find(ExitBlocks, ChildN->getBlock()) != ExitBlocks.end()) && + "Should never reach beyond the loop and exits when deleting!"); + DeadBlocks.insert(ChildN->getBlock()); + } + + // Filter out the dead blocks from the exit blocks list so that it can be + // used in the caller. + llvm::erase_if(ExitBlocks, + [&](BasicBlock *BB) { return DeadBlocks.count(BB); }); + + // Remove these blocks from their successors. + for (auto *BB : DeadBlocks) + for (BasicBlock *SuccBB : successors(BB)) + SuccBB->removePredecessor(BB, /*DontDeleteUselessPHIs*/ true); + + // Walk from this loop up through its parents removing all of the dead blocks. + for (Loop *ParentL = &L; ParentL; ParentL = ParentL->getParentLoop()) { + for (auto *BB : DeadBlocks) + ParentL->getBlocksSet().erase(BB); + llvm::erase_if(ParentL->getBlocksVector(), + [&](BasicBlock *BB) { return DeadBlocks.count(BB); }); + } + + // Now delete the dead child loops. This raw delete will clear them + // recursively. + llvm::erase_if(L.getSubLoopsVector(), [&](Loop *ChildL) { + if (!DeadBlocks.count(ChildL->getHeader())) + return false; + + assert(llvm::all_of(ChildL->blocks(), + [&](BasicBlock *ChildBB) { + return DeadBlocks.count(ChildBB); + }) && + "If the child loop header is dead all blocks in the child loop must " + "be dead as well!"); + LI.destroy(ChildL); + return true; + }); + + // Remove the mappings for the dead blocks. + for (auto *BB : DeadBlocks) + LI.changeLoopFor(BB, nullptr); + + // Drop all the references from these blocks to others to handle cyclic + // references as we start deleting the blocks themselves. + for (auto *BB : DeadBlocks) + BB->dropAllReferences(); + + for (auto *BB : llvm::reverse(DeadBlocks)) { + DT.eraseNode(BB); + BB->eraseFromParent(); + } +} + +/// Recompute the set of blocks in a loop after unswitching. +/// +/// This walks from the original headers predecessors to rebuild the loop. We +/// take advantage of the fact that new blocks can't have been added, and so we +/// filter by the original loop's blocks. This also handles potentially +/// unreachable code that we don't want to explore but might be found examining +/// the predecessors of the header. +/// +/// If the original loop is no longer a loop, this will return an empty set. If +/// it remains a loop, all the blocks within it will be added to the set +/// (including those blocks in inner loops). +static SmallPtrSet recomputeLoopBlockSet(Loop &L, + LoopInfo &LI) { + SmallPtrSet LoopBlockSet; + + auto *PH = L.getLoopPreheader(); + auto *Header = L.getHeader(); + + // A worklist to use while walking backwards from the header. + SmallVector Worklist; + + // First walk the predecessors of the header to find the backedges. This will + // form the basis of our walk. + for (auto *Pred : predecessors(Header)) { + // Skip the preheader. + if (Pred == PH) + continue; + + // Because the loop was in simplified form, the only non-loop predecessor + // is the preheader. + assert(L.contains(Pred) && "Found a predecessor of the loop header other " + "than the preheader that is not part of the " + "loop!"); + + // Insert this block into the loop set and on the first visit and, if it + // isn't the header we're currently walking, put it into the worklist to + // recurse through. + if (LoopBlockSet.insert(Pred).second && Pred != Header) + Worklist.push_back(Pred); + } + + // If no backedges were found, we're done. + if (LoopBlockSet.empty()) + return LoopBlockSet; + + // Add the loop header to the set. + LoopBlockSet.insert(Header); + + // We found backedges, recurse through them to identify the loop blocks. + while (!Worklist.empty()) { + BasicBlock *BB = Worklist.pop_back_val(); + assert(LoopBlockSet.count(BB) && "Didn't put block into the loop set!"); + + // Because we know the inner loop structure remains valid we can use the + // loop structure to jump immediately across the entire nested loop. + // Further, because it is in loop simplified form, we can directly jump + // to its preheader afterward. + if (Loop *InnerL = LI.getLoopFor(BB)) + if (InnerL != &L) { + assert(L.contains(InnerL) && + "Should not reach a loop *outside* this loop!"); + // The preheader is the only possible predecessor of the loop so + // insert it into the set and check whether it was already handled. + auto *InnerPH = InnerL->getLoopPreheader(); + assert(L.contains(InnerPH) && "Cannot contain an inner loop block " + "but not contain the inner loop " + "preheader!"); + if (!LoopBlockSet.insert(InnerPH).second) + // The only way to reach the preheader is through the loop body + // itself so if it has been visited the loop is already handled. + continue; + + // Insert all of the blocks (other than those already present) into + // the loop set. The only block we expect to already be in the set is + // the one we used to find this loop as we immediately handle the + // others the first time we encounter the loop. + for (auto *InnerBB : InnerL->blocks()) { + if (InnerBB == BB) { + assert(LoopBlockSet.count(InnerBB) && + "Block should already be in the set!"); + continue; + } + + bool Inserted = LoopBlockSet.insert(InnerBB).second; + (void)Inserted; + assert(Inserted && "Should only insert an inner loop once!"); + } + + // Add the preheader to the worklist so we will continue past the + // loop body. + Worklist.push_back(InnerPH); + continue; + } + + // Insert any predecessors that were in the original loop into the new + // set, and if the insert is successful, add them to the worklist. + for (auto *Pred : predecessors(BB)) + if (L.contains(Pred) && LoopBlockSet.insert(Pred).second) + Worklist.push_back(Pred); + } + + // We've found all the blocks participating in the loop, return our completed + // set. + return LoopBlockSet; +} + +/// Rebuild a loop after unswitching removes some subset of blocks and edges. +/// +/// The removal may have removed some child loops entirely but cannot have +/// disturbed any remaining child loops. However, they may need to be hoisted +/// to the parent loop (or to be top-level loops). The original loop may be +/// completely removed. +/// +/// The sibling loops resulting from this update are returned. If the original +/// loop remains a valid loop, it will be the first entry in this list with all +/// of the newly sibling loops following it. +/// +/// Returns true if the loop remains a loop after unswitching, and false if it +/// is no longer a loop after unswitching (and should not continue to be +/// referenced). +static bool rebuildLoopAfterUnswitch(Loop &L, ArrayRef ExitBlocks, + LoopInfo &LI, + SmallVectorImpl &HoistedLoops) { + auto *PH = L.getLoopPreheader(); + + // Compute the actual parent loop from the exit blocks. Because we may have + // pruned some exits the loop may be different from the original parent. + Loop *ParentL = nullptr; + SmallVector ExitLoops; + SmallVector ExitsInLoops; + ExitsInLoops.reserve(ExitBlocks.size()); + for (auto *ExitBB : ExitBlocks) + if (Loop *ExitL = LI.getLoopFor(ExitBB)) { + ExitLoops.push_back(ExitL); + ExitsInLoops.push_back(ExitBB); + if (!ParentL || (ParentL != ExitL && ParentL->contains(ExitL))) + ParentL = ExitL; + } + + // Recompute the blocks participating in this loop. This may be empty if it + // is no longer a loop. + auto LoopBlockSet = recomputeLoopBlockSet(L, LI); + + // If we still have a loop, we need to re-set the loop's parent as the exit + // block set changing may have moved it within the loop nest. Note that this + // can only happen when this loop has a parent as it can only hoist the loop + // *up* the nest. + if (!LoopBlockSet.empty() && L.getParentLoop() != ParentL) { + // Remove this loop's (original) blocks from all of the intervening loops. + for (Loop *IL = L.getParentLoop(); IL != ParentL; + IL = IL->getParentLoop()) { + IL->getBlocksSet().erase(PH); + for (auto *BB : L.blocks()) + IL->getBlocksSet().erase(BB); + llvm::erase_if(IL->getBlocksVector(), [&](BasicBlock *BB) { + return BB == PH || L.contains(BB); + }); + } + + LI.changeLoopFor(PH, ParentL); + L.getParentLoop()->removeChildLoop(&L); + if (ParentL) + ParentL->addChildLoop(&L); + else + LI.addTopLevelLoop(&L); + } + + // Now we update all the blocks which are no longer within the loop. + auto &Blocks = L.getBlocksVector(); + auto BlocksSplitI = + LoopBlockSet.empty() + ? Blocks.begin() + : std::stable_partition( + Blocks.begin(), Blocks.end(), + [&](BasicBlock *BB) { return LoopBlockSet.count(BB); }); + + // Before we erase the list of unlooped blocks, build a set of them. + SmallPtrSet UnloopedBlocks(BlocksSplitI, Blocks.end()); + if (LoopBlockSet.empty()) + UnloopedBlocks.insert(PH); + + // Now erase these blocks from the loop. + for (auto *BB : make_range(BlocksSplitI, Blocks.end())) + L.getBlocksSet().erase(BB); + Blocks.erase(BlocksSplitI, Blocks.end()); + + // Sort the exits in ascending loop depth, we'll work backwards across these + // to process them inside out. + std::stable_sort(ExitsInLoops.begin(), ExitsInLoops.end(), + [&](BasicBlock *LHS, BasicBlock *RHS) { + return LI.getLoopDepth(LHS) < LI.getLoopDepth(RHS); + }); + + // We'll build up a set for each exit loop. + SmallPtrSet NewExitLoopBlocks; + Loop *PrevExitL = L.getParentLoop(); // The deepest possible exit loop. + + auto RemoveUnloopedBlocksFromLoop = + [](Loop &L, SmallPtrSetImpl &UnloopedBlocks) { + for (auto *BB : UnloopedBlocks) + L.getBlocksSet().erase(BB); + llvm::erase_if(L.getBlocksVector(), [&](BasicBlock *BB) { + return UnloopedBlocks.count(BB); + }); + }; + + SmallVector Worklist; + while (!UnloopedBlocks.empty() && !ExitsInLoops.empty()) { + assert(Worklist.empty() && "Didn't clear worklist!"); + assert(NewExitLoopBlocks.empty() && "Didn't clear loop set!"); + + // Grab the next exit block, in decreasing loop depth order. + BasicBlock *ExitBB = ExitsInLoops.pop_back_val(); + Loop &ExitL = *LI.getLoopFor(ExitBB); + assert(ExitL.contains(&L) && "Exit loop must contain the inner loop!"); + + // Erase all of the unlooped blocks from the loops between the previous + // exit loop and this exit loop. This works because the ExitInLoops list is + // sorted in increasing order of loop depth and thus we visit loops in + // decreasing order of loop depth. + for (; PrevExitL != &ExitL; PrevExitL = PrevExitL->getParentLoop()) + RemoveUnloopedBlocksFromLoop(*PrevExitL, UnloopedBlocks); + + // Walk the CFG back until we hit the cloned PH adding everything reachable + // and in the unlooped set to this exit block's loop. + Worklist.push_back(ExitBB); + do { + BasicBlock *BB = Worklist.pop_back_val(); + // We can stop recursing at the cloned preheader (if we get there). + if (BB == PH) + continue; + + for (BasicBlock *PredBB : predecessors(BB)) { + // If this pred has already been moved to our set or is part of some + // (inner) loop, no update needed. + if (!UnloopedBlocks.erase(PredBB)) { + assert((NewExitLoopBlocks.count(PredBB) || + ExitL.contains(LI.getLoopFor(PredBB))) && + "Predecessor not in a nested loop (or already visited)!"); + continue; + } + + // We just insert into the loop set here. We'll add these blocks to the + // exit loop after we build up the set in a deterministic order rather + // than the predecessor-influenced visit order. + bool Inserted = NewExitLoopBlocks.insert(PredBB).second; + (void)Inserted; + assert(Inserted && "Should only visit an unlooped block once!"); + + // And recurse through to its predecessors. + Worklist.push_back(PredBB); + } + } while (!Worklist.empty()); + + // If blocks in this exit loop were directly part of the original loop (as + // opposed to a child loop) update the map to point to this exit loop. This + // just updates a map and so the fact that the order is unstable is fine. + for (auto *BB : NewExitLoopBlocks) + if (Loop *BBL = LI.getLoopFor(BB)) + if (BBL == &L || !L.contains(BBL)) + LI.changeLoopFor(BB, &ExitL); + + // We will remove the remaining unlooped blocks from this loop in the next + // iteration or below. + NewExitLoopBlocks.clear(); + } + + // Any remaining unlooped blocks are no longer part of any loop unless they + // are part of some child loop. + for (; PrevExitL; PrevExitL = PrevExitL->getParentLoop()) + RemoveUnloopedBlocksFromLoop(*PrevExitL, UnloopedBlocks); + for (auto *BB : UnloopedBlocks) + if (Loop *BBL = LI.getLoopFor(BB)) + if (BBL == &L || !L.contains(BBL)) + LI.changeLoopFor(BB, nullptr); + + // Sink all the child loops whose headers are no longer in the loop set to + // the parent (or to be top level loops). We reach into the loop and directly + // update its subloop vector to make this batch update efficient. + auto &SubLoops = L.getSubLoopsVector(); + auto SubLoopsSplitI = + LoopBlockSet.empty() + ? SubLoops.begin() + : std::stable_partition( + SubLoops.begin(), SubLoops.end(), [&](Loop *SubL) { + return LoopBlockSet.count(SubL->getHeader()); + }); + for (auto *HoistedL : make_range(SubLoopsSplitI, SubLoops.end())) { + HoistedLoops.push_back(HoistedL); + HoistedL->setParentLoop(nullptr); + + // To compute the new parent of this hoisted loop we look at where we + // placed the preheader above. We can't lookup the header itself because we + // retained the mapping from the header to the hoisted loop. But the + // preheader and header should have the exact same new parent computed + // based on the set of exit blocks from the original loop as the preheader + // is a predecessor of the header and so reached in the reverse walk. And + // because the loops were all in simplified form the preheader of the + // hoisted loop can't be part of some *other* loop. + if (auto *NewParentL = LI.getLoopFor(HoistedL->getLoopPreheader())) + NewParentL->addChildLoop(HoistedL); + else + LI.addTopLevelLoop(HoistedL); + } + SubLoops.erase(SubLoopsSplitI, SubLoops.end()); + + // Actually delete the loop if nothing remained within it. + if (Blocks.empty()) { + assert(SubLoops.empty() && + "Failed to remove all subloops from the original loop!"); + if (Loop *ParentL = L.getParentLoop()) + ParentL->removeChildLoop(llvm::find(*ParentL, &L)); + else + LI.removeLoop(llvm::find(LI, &L)); + LI.destroy(&L); + return false; + } + + return true; +} + +/// Helper to visit a dominator subtree, invoking a callable on each node. +/// +/// Returning false at any point will stop walking past that node of the tree. +template +void visitDomSubTree(DominatorTree &DT, BasicBlock *BB, CallableT Callable) { + SmallVector DomWorklist; + DomWorklist.push_back(DT[BB]); +#ifndef NDEBUG + SmallPtrSet Visited; + Visited.insert(DT[BB]); +#endif + do { + DomTreeNode *N = DomWorklist.pop_back_val(); + + // Visit this node. + if (!Callable(N->getBlock())) + continue; + + // Accumulate the child nodes. + for (DomTreeNode *ChildN : *N) { + assert(Visited.insert(ChildN).second && + "Cannot visit a node twice when walking a tree!"); + DomWorklist.push_back(ChildN); + } + } while (!DomWorklist.empty()); +} + +/// Take an invariant branch that has been determined to be safe and worthwhile +/// to unswitch despite being non-trivial to do so and perform the unswitch. +/// +/// This directly updates the CFG to hoist the predicate out of the loop, and +/// clone the necessary parts of the loop to maintain behavior. +/// +/// It also updates both dominator tree and loopinfo based on the unswitching. +/// +/// Once unswitching has been performed it runs the provided callback to report +/// the new loops and no-longer valid loops to the caller. +static bool unswitchInvariantBranch( + Loop &L, BranchInst &BI, DominatorTree &DT, LoopInfo &LI, + AssumptionCache &AC, + function_ref)> NonTrivialUnswitchCB) { + assert(BI.isConditional() && "Can only unswitch a conditional branch!"); + assert(L.isLoopInvariant(BI.getCondition()) && + "Can only unswitch an invariant branch condition!"); + + // Constant and BBs tracking the cloned and continuing successor. + const int ClonedSucc = 0; + auto *ParentBB = BI.getParent(); + auto *UnswitchedSuccBB = BI.getSuccessor(ClonedSucc); + auto *ContinueSuccBB = BI.getSuccessor(1 - ClonedSucc); + + assert(UnswitchedSuccBB != ContinueSuccBB && + "Should not unswitch a branch that always goes to the same place!"); + + // The branch should be in this exact loop. Any inner loop's invariant branch + // should be handled by unswitching that inner loop. The caller of this + // routine should filter out any candidates that remain (but were skipped for + // whatever reason). + assert(LI.getLoopFor(ParentBB) == &L && "Branch in an inner loop!"); + + SmallVector ExitBlocks; + L.getUniqueExitBlocks(ExitBlocks); + + // We cannot unswitch if exit blocks contain a cleanuppad instruction as we + // don't know how to split those exit blocks. + // FIXME: We should teach SplitBlock to handle this and remove this + // restriction. + for (auto *ExitBB : ExitBlocks) + if (isa(ExitBB->getFirstNonPHI())) + return false; + + SmallPtrSet ExitBlockSet(ExitBlocks.begin(), + ExitBlocks.end()); + + // Compute the parent loop now before we start hacking on things. + Loop *ParentL = L.getParentLoop(); + + // Compute the outer-most loop containing one of our exit blocks. This is the + // furthest up our loopnest which can be mutated, which we will use below to + // update things. + Loop *OuterExitL = &L; + for (auto *ExitBB : ExitBlocks) { + Loop *NewOuterExitL = LI.getLoopFor(ExitBB); + if (!NewOuterExitL) { + // We exited the entire nest with this block, so we're done. + OuterExitL = nullptr; + break; + } + if (NewOuterExitL != OuterExitL && NewOuterExitL->contains(OuterExitL)) + OuterExitL = NewOuterExitL; + } + + // If the edge we *aren't* cloning in the unswitch (the continuing edge) + // dominates its target, we can skip cloning the dominated region of the loop + // and its exits. We compute this as a set of nodes to be skipped. + SmallPtrSet SkippedLoopAndExitBlocks; + if (ContinueSuccBB->getUniquePredecessor() || + llvm::all_of(predecessors(ContinueSuccBB), [&](BasicBlock *PredBB) { + return PredBB == ParentBB || DT.dominates(ContinueSuccBB, PredBB); + })) { + visitDomSubTree(DT, ContinueSuccBB, [&](BasicBlock *BB) { + SkippedLoopAndExitBlocks.insert(BB); + return true; + }); + } + // Similarly, if the edge we *are* cloning in the unswitch (the unswitched + // edge) dominates its target, we will end up with dead nodes in the original + // loop and its exits that will need to be deleted. Here, we just retain that + // the property holds and will compute the deleted set later. + bool DeleteUnswitchedSucc = + UnswitchedSuccBB->getUniquePredecessor() || + llvm::all_of(predecessors(UnswitchedSuccBB), [&](BasicBlock *PredBB) { + return PredBB == ParentBB || DT.dominates(UnswitchedSuccBB, PredBB); + }); + + // Split the preheader, so that we know that there is a safe place to insert + // the conditional branch. We will change the preheader to have a conditional + // branch on LoopCond. The original preheader will become the split point + // between the unswitched versions, and we will have a new preheader for the + // original loop. + BasicBlock *SplitBB = L.getLoopPreheader(); + BasicBlock *LoopPH = SplitEdge(SplitBB, L.getHeader(), &DT, &LI); + + // Keep a mapping for the cloned values. + ValueToValueMapTy VMap; + + // Build the cloned blocks from the loop. + auto *ClonedPH = buildClonedLoopBlocks( + L, LoopPH, SplitBB, ExitBlocks, ParentBB, UnswitchedSuccBB, + ContinueSuccBB, SkippedLoopAndExitBlocks, VMap, AC, DT, LI); + + // Build the cloned loop structure itself. This may be substantially + // different from the original structure due to the simplified CFG. This also + // handles inserting all the cloned blocks into the correct loops. + SmallVector NonChildClonedLoops; + Loop *ClonedL = + buildClonedLoops(L, ExitBlocks, VMap, LI, NonChildClonedLoops); + + // Remove the parent as a predecessor of the unswitched successor. + UnswitchedSuccBB->removePredecessor(ParentBB, /*DontDeleteUselessPHIs*/ true); + + // Now splice the branch from the original loop and use it to select between + // the two loops. + SplitBB->getTerminator()->eraseFromParent(); + SplitBB->getInstList().splice(SplitBB->end(), ParentBB->getInstList(), BI); + BI.setSuccessor(ClonedSucc, ClonedPH); + BI.setSuccessor(1 - ClonedSucc, LoopPH); + + // Create a new unconditional branch to the continuing block (as opposed to + // the one cloned). + BranchInst::Create(ContinueSuccBB, ParentBB); + + // Delete anything that was made dead in the original loop due to + // unswitching. + if (DeleteUnswitchedSucc) + deleteDeadBlocksFromLoop(L, UnswitchedSuccBB, ExitBlocks, DT, LI); + + SmallVector HoistedLoops; + bool IsStillLoop = rebuildLoopAfterUnswitch(L, ExitBlocks, LI, HoistedLoops); + + // This will have completely invalidated the dominator tree. We can't easily + // bound how much is invalid because in some cases we will refine the + // predecessor set of exit blocks of the loop which can move large unrelated + // regions of code into a new subtree. + // + // FIXME: Eventually, we should use an incremental update utility that + // leverages the existing information in the dominator tree (and potentially + // the nature of the change) to more efficiently update things. + DT.recalculate(*SplitBB->getParent()); + + // We can change which blocks are exit blocks of all the cloned sibling + // loops, the current loop, and any parent loops which shared exit blocks + // with the current loop. As a consequence, we need to re-form LCSSA for + // them. But we shouldn't need to re-form LCSSA for any child loops. + // FIXME: This could be made more efficient by tracking which exit blocks are + // new, and focusing on them, but that isn't likely to be necessary. + // + // In order to reasonably rebuild LCSSA we need to walk inside-out across the + // loop nest and update every loop that could have had its exits changed. We + // also need to cover any intervening loops. We add all of these loops to + // a list and sort them by loop depth to achieve this without updating + // unnecessary loops. + auto UpdateLCSSA = [&](Loop &UpdateL) { +#ifndef NDEBUG + for (Loop *ChildL : UpdateL) + assert(ChildL->isRecursivelyLCSSAForm(DT, LI) && + "Perturbed a child loop's LCSSA form!"); +#endif + formLCSSA(UpdateL, DT, &LI, nullptr); + }; + + // For non-child cloned loops and hoisted loops, we just need to update LCSSA + // and we can do it in any order as they don't nest relative to each other. + for (Loop *UpdatedL : llvm::concat(NonChildClonedLoops, HoistedLoops)) + UpdateLCSSA(*UpdatedL); + + // If the original loop had exit blocks, walk up through the outer most loop + // of those exit blocks to update LCSSA and form updated dedicated exits. + if (OuterExitL != &L) { + SmallVector OuterLoops; + // We start with the cloned loop and the current loop if they are loops and + // move toward OuterExitL. Also, if either the cloned loop or the current + // loop have become top level loops we need to walk all the way out. + if (ClonedL) { + OuterLoops.push_back(ClonedL); + if (!ClonedL->getParentLoop()) + OuterExitL = nullptr; + } + if (IsStillLoop) { + OuterLoops.push_back(&L); + if (!L.getParentLoop()) + OuterExitL = nullptr; + } + // Grab all of the enclosing loops now. + for (Loop *OuterL = ParentL; OuterL != OuterExitL; + OuterL = OuterL->getParentLoop()) + OuterLoops.push_back(OuterL); + + // Finally, update our list of outer loops. This is nicely ordered to work + // inside-out. + for (Loop *OuterL : OuterLoops) { + // First build LCSSA for this loop so that we can preserve it when + // forming dedicated exits. We don't want to perturb some other loop's + // LCSSA while doing that CFG edit. + UpdateLCSSA(*OuterL); + + // For loops reached by this loop's original exit blocks we may + // introduced new, non-dedicated exits. At least try to re-form dedicated + // exits for these loops. This may fail if they couldn't have dedicated + // exits to start with. + formDedicatedExitBlocks(OuterL, &DT, &LI, /*PreserveLCSSA*/ true); + } + } + +#ifndef NDEBUG + // Verify the entire loop structure to catch any incorrect updates before we + // progress in the pass pipeline. + LI.verify(DT); +#endif + + // Now that we've unswitched something, make callbacks to report the changes. + // For that we need to merge together the updated loops and the cloned loops + // and check whether the original loop survived. + SmallVector SibLoops; + for (Loop *UpdatedL : llvm::concat(NonChildClonedLoops, HoistedLoops)) + if (UpdatedL->getParentLoop() == ParentL) + SibLoops.push_back(UpdatedL); + NonTrivialUnswitchCB(IsStillLoop, SibLoops); + + ++NumBranches; + return true; +} + +/// Recursively compute the cost of a dominator subtree based on the per-block +/// cost map provided. +/// +/// The recursive computation is memozied into the provided DT-indexed cost map +/// to allow querying it for most nodes in the domtree without it becoming +/// quadratic. +static int +computeDomSubtreeCost(DomTreeNode &N, + const SmallDenseMap &BBCostMap, + SmallDenseMap &DTCostMap) { + // Don't accumulate cost (or recurse through) blocks not in our block cost + // map and thus not part of the duplication cost being considered. + auto BBCostIt = BBCostMap.find(N.getBlock()); + if (BBCostIt == BBCostMap.end()) + return 0; + + // Lookup this node to see if we already computed its cost. + auto DTCostIt = DTCostMap.find(&N); + if (DTCostIt != DTCostMap.end()) + return DTCostIt->second; + + // If not, we have to compute it. We can't use insert above and update + // because computing the cost may insert more things into the map. + int Cost = std::accumulate( + N.begin(), N.end(), BBCostIt->second, [&](int Sum, DomTreeNode *ChildN) { + return Sum + computeDomSubtreeCost(*ChildN, BBCostMap, DTCostMap); + }); + bool Inserted = DTCostMap.insert({&N, Cost}).second; + (void)Inserted; + assert(Inserted && "Should not insert a node while visiting children!"); + return Cost; +} + /// Unswitch control flow predicated on loop invariant conditions. /// /// This first hoists all branches or switches which are trivial (IE, do not /// require duplicating any part of the loop) out of the loop body. It then /// looks at other loop invariant control flows and tries to unswitch those as /// well by cloning the loop if the result is small enough. -static bool unswitchLoop(Loop &L, DominatorTree &DT, LoopInfo &LI, - AssumptionCache &AC) { - assert(L.isLCSSAForm(DT) && +static bool +unswitchLoop(Loop &L, DominatorTree &DT, LoopInfo &LI, AssumptionCache &AC, + TargetTransformInfo &TTI, bool NonTrivial, + function_ref)> NonTrivialUnswitchCB) { + assert(L.isRecursivelyLCSSAForm(DT, LI) && "Loops must be in LCSSA form before unswitching."); bool Changed = false; @@ -727,7 +1926,136 @@ // Try trivial unswitch first before loop over other basic blocks in the loop. Changed |= unswitchAllTrivialConditions(L, DT, LI); - // FIXME: Add support for non-trivial unswitching by cloning the loop. + // If we're not doing non-trivial unswitching, we're done. We both accept + // a parameter but also check a local flag that can be used for testing + // a debugging. + if (!NonTrivial && !EnableNonTrivialUnswitch) + return Changed; + + // Collect all remaining invariant branch conditions within this loop (as + // opposed to an inner loop which would be handled when visiting that inner + // loop). + SmallVector UnswitchCandidates; + for (auto *BB : L.blocks()) + if (LI.getLoopFor(BB) == &L) + if (auto *BI = dyn_cast(BB->getTerminator())) + if (BI->isConditional() && L.isLoopInvariant(BI->getCondition()) && + BI->getSuccessor(0) != BI->getSuccessor(1)) + UnswitchCandidates.push_back(BI); + + // If we didn't find any candidates, we're done. + if (UnswitchCandidates.empty()) + return Changed; + + DEBUG(dbgs() << "Considering " << UnswitchCandidates.size() + << " non-trivial loop invariant conditions for unswitching.\n"); + + // Given that unswitching these terminators will require duplicating parts of + // the loop, so we need to be able to model that cost. Compute the ephemeral + // values and set up a data structure to hold per-BB costs. We cache each + // block's cost so that we don't recompute this when considering different + // subsets of the loop for duplication during unswitching. + SmallPtrSet EphValues; + CodeMetrics::collectEphemeralValues(&L, &AC, EphValues); + SmallDenseMap BBCostMap; + + // Compute the cost of each block, as well as the total loop cost. Also, bail + // out if we see instructions which are incompatible with loop unswitching + // (convergent, noduplicate, or cross-basic-block tokens). + // FIXME: We might be able to safely handle some of these in non-duplicated + // regions. + int LoopCost = 0; + for (auto *BB : L.blocks()) { + int Cost = 0; + for (auto &I : *BB) { + if (EphValues.count(&I)) + continue; + + if (I.getType()->isTokenTy() && I.isUsedOutsideOfBlock(BB)) + return Changed; + if (auto CS = CallSite(&I)) + if (CS.isConvergent() || CS.cannotDuplicate()) + return Changed; + + Cost += TTI.getUserCost(&I); + } + assert(Cost >= 0 && "Must not have negative costs!"); + LoopCost += Cost; + assert(LoopCost >= 0 && "Must not have negative loop costs!"); + BBCostMap[BB] = Cost; + } + DEBUG(dbgs() << " Total loop cost: " << LoopCost << "\n"); + + // Now we find the best candidate by searching for the one with the following + // properties in order: + // + // 1) An unswitching cost below the threshold + // 2) The smallest number of duplicated unswitch candidates (to avoid + // creating redundant subsequent unswitching) + // 3) The smallest cost after unswitching. + // + // We prioritize reducing fanout of unswitch candidates provided the cost + // remains below the threshold because this has a multiplicative effect. + // + // This requires memoizing each dominator subtree to avoid redundant work. + // + // FIXME: Need to actually do the number of candidates part above. + SmallDenseMap DTCostMap; + // Given a terminator which might be unswitched, computes the non-duplicated + // cost for that terminator. + auto ComputeUnswitchedCost = [&](TerminatorInst *TI) { + BasicBlock &BB = *TI->getParent(); + SmallPtrSet Visited; + + int Cost = LoopCost; + for (BasicBlock *SuccBB : successors(&BB)) { + // Don't count successors more than once. + if (!Visited.insert(SuccBB).second) + continue; + + // This successor's domtree will not need to be duplicated after + // unswitching if the edge to the successor dominates it (and thus the + // entire tree). This essentially means there is no other path into this + // subtree and so it will end up live in only one clone of the loop. + if (SuccBB->getUniquePredecessor() || + llvm::all_of(predecessors(SuccBB), [&](BasicBlock *PredBB) { + return PredBB == &BB || DT.dominates(SuccBB, PredBB); + })) { + Cost -= computeDomSubtreeCost(*DT[SuccBB], BBCostMap, DTCostMap); + assert(Cost >= 0 && + "Non-duplicated cost should never exceed total loop cost!"); + } + } + + // Now scale the cost by the number of unique successors minus one. We + // subtract one because there is already at least one copy of the entire + // loop. This is computing the new cost of unswitching a condition. + assert(Visited.size() > 1 && + "Cannot unswitch a condition without multiple distinct successors!"); + return Cost * (Visited.size() - 1); + }; + TerminatorInst *BestUnswitchTI = nullptr; + int BestUnswitchCost; + for (TerminatorInst *CandidateTI : UnswitchCandidates) { + int CandidateCost = ComputeUnswitchedCost(CandidateTI); + DEBUG(dbgs() << " Computed cost of " << CandidateCost + << " for unswitch candidate: " << *CandidateTI << "\n"); + if (!BestUnswitchTI || CandidateCost < BestUnswitchCost) { + BestUnswitchTI = CandidateTI; + BestUnswitchCost = CandidateCost; + } + } + + if (BestUnswitchCost < UnswitchThreshold) { + DEBUG(dbgs() << " Trying to unswitch non-trivial (cost = " + << BestUnswitchCost << ") branch: " << *BestUnswitchTI + << "\n"); + Changed |= unswitchInvariantBranch(L, cast(*BestUnswitchTI), DT, + LI, AC, NonTrivialUnswitchCB); + } else { + DEBUG(dbgs() << "Cannot unswitch, lowest cost found: " << BestUnswitchCost + << "\n"); + } return Changed; } @@ -740,7 +2068,25 @@ DEBUG(dbgs() << "Unswitching loop in " << F.getName() << ": " << L << "\n"); - if (!unswitchLoop(L, AR.DT, AR.LI, AR.AC)) + // Save the current loop name in a variable so that we can report it even + // after it has been deleted. + std::string LoopName = L.getName(); + + auto NonTrivialUnswitchCB = [&L, &U, &LoopName](bool CurrentLoopValid, + ArrayRef NewLoops) { + // If we did a non-trivial unswitch, we have added new (cloned) loops. + U.addSiblingLoops(NewLoops); + + // If the current loop remains valid, we should revisit it to catch any + // other unswitch opportunities. Otherwise, we need to mark it as deleted. + if (CurrentLoopValid) + U.revisitCurrentLoop(); + else + U.markLoopAsDeleted(L, LoopName); + }; + + if (!unswitchLoop(L, AR.DT, AR.LI, AR.AC, AR.TTI, NonTrivial, + NonTrivialUnswitchCB)) return PreservedAnalyses::all(); #ifndef NDEBUG @@ -754,10 +2100,13 @@ namespace { class SimpleLoopUnswitchLegacyPass : public LoopPass { + bool NonTrivial; + public: static char ID; // Pass ID, replacement for typeid - explicit SimpleLoopUnswitchLegacyPass() : LoopPass(ID) { + explicit SimpleLoopUnswitchLegacyPass(bool NonTrivial = false) + : LoopPass(ID), NonTrivial(NonTrivial) { initializeSimpleLoopUnswitchLegacyPassPass( *PassRegistry::getPassRegistry()); } @@ -766,6 +2115,7 @@ void getAnalysisUsage(AnalysisUsage &AU) const override { AU.addRequired(); + AU.addRequired(); getLoopAnalysisUsage(AU); } }; @@ -783,8 +2133,29 @@ auto &DT = getAnalysis().getDomTree(); auto &LI = getAnalysis().getLoopInfo(); auto &AC = getAnalysis().getAssumptionCache(F); + auto &TTI = getAnalysis().getTTI(F); + + auto NonTrivialUnswitchCB = [&L, &LPM](bool CurrentLoopValid, + ArrayRef NewLoops) { + // If we did a non-trivial unswitch, we have added new (cloned) loops. + for (auto *NewL : NewLoops) + LPM.addLoop(*NewL); + + // If the current loop remains valid, re-add it to the queue. This is + // a little wasteful as we'll finish processing the current loop as well, + // but it is the best we can do in the old PM. + if (CurrentLoopValid) + LPM.addLoop(*L); + else + LPM.markLoopAsDeleted(*L); + }; + + bool Changed = + unswitchLoop(*L, DT, LI, AC, TTI, NonTrivial, NonTrivialUnswitchCB); - bool Changed = unswitchLoop(*L, DT, LI, AC); + // If anything was unswitched, also clear any cached information about this + // loop. + LPM.deleteSimpleAnalysisLoop(L); #ifndef NDEBUG // Historically this pass has had issues with the dominator tree so verify it @@ -798,11 +2169,13 @@ INITIALIZE_PASS_BEGIN(SimpleLoopUnswitchLegacyPass, "simple-loop-unswitch", "Simple unswitch loops", false, false) INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker) +INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) +INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass) INITIALIZE_PASS_DEPENDENCY(LoopPass) INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass) INITIALIZE_PASS_END(SimpleLoopUnswitchLegacyPass, "simple-loop-unswitch", "Simple unswitch loops", false, false) -Pass *llvm::createSimpleLoopUnswitchLegacyPass() { - return new SimpleLoopUnswitchLegacyPass(); +Pass *llvm::createSimpleLoopUnswitchLegacyPass(bool NonTrivial) { + return new SimpleLoopUnswitchLegacyPass(NonTrivial); } Index: llvm/trunk/test/Transforms/SimpleLoopUnswitch/2006-06-27-DeadSwitchCase.ll =================================================================== --- llvm/trunk/test/Transforms/SimpleLoopUnswitch/2006-06-27-DeadSwitchCase.ll +++ llvm/trunk/test/Transforms/SimpleLoopUnswitch/2006-06-27-DeadSwitchCase.ll @@ -2,24 +2,30 @@ define void @init_caller_save() { entry: - br label %cond_true78 -cond_next20: ; preds = %cond_true64 - br label %bb31 -bb31: ; preds = %cond_true64, %cond_true64, %cond_next20 - %iftmp.29.1 = phi i32 [ 0, %cond_next20 ], [ 0, %cond_true64 ], [ 0, %cond_true64 ] ; [#uses=0] - br label %bb54 -bb54: ; preds = %cond_true78, %bb31 - br i1 false, label %bb75, label %cond_true64 -cond_true64: ; preds = %bb54 - switch i32 %i.0.0, label %cond_next20 [ - i32 17, label %bb31 - i32 18, label %bb31 - ] -bb75: ; preds = %bb54 - %tmp74.0 = add i32 %i.0.0, 1 ; [#uses=1] - br label %cond_true78 -cond_true78: ; preds = %bb75, %entry - %i.0.0 = phi i32 [ 0, %entry ], [ %tmp74.0, %bb75 ] ; [#uses=2] - br label %bb54 + br label %cond_true78 + +cond_true78: ; preds = %bb75, %entry + %i.0.0 = phi i32 [ 0, %entry ], [ %tmp74.0, %bb75 ] ; [#uses=2] + br label %bb54 + +bb54: ; preds = %cond_true78, %bb31 + br i1 false, label %bb75, label %cond_true64 + +cond_true64: ; preds = %bb54 + switch i32 %i.0.0, label %cond_next20 [ + i32 17, label %bb31 + i32 18, label %bb31 + ] + +cond_next20: ; preds = %cond_true64 + br label %bb31 + +bb31: ; preds = %cond_true64, %cond_true64, %cond_next20 + %iftmp.29.1 = phi i32 [ 0, %cond_next20 ], [ 0, %cond_true64 ], [ 0, %cond_true64 ] ; [#uses=0] + br label %bb54 + +bb75: ; preds = %bb54 + %tmp74.0 = add i32 %i.0.0, 1 ; [#uses=1] + br label %cond_true78 } Index: llvm/trunk/test/Transforms/SimpleLoopUnswitch/nontrivial-unswitch-cost.ll =================================================================== --- llvm/trunk/test/Transforms/SimpleLoopUnswitch/nontrivial-unswitch-cost.ll +++ llvm/trunk/test/Transforms/SimpleLoopUnswitch/nontrivial-unswitch-cost.ll @@ -0,0 +1,501 @@ +; Specifically exercise the cost modeling for non-trivial loop unswitching. +; +; RUN: opt -passes='loop(unswitch),verify' -enable-nontrivial-unswitch -unswitch-threshold=5 -S < %s | FileCheck %s +; RUN: opt -simple-loop-unswitch -enable-nontrivial-unswitch -unswitch-threshold=5 -S < %s | FileCheck %s + +declare void @a() +declare void @b() +declare void @x() + +; First establish enough code size in the duplicated 'loop_begin' block to +; suppress unswitching. +define void @test_no_unswitch(i1* %ptr, i1 %cond) { +; CHECK-LABEL: @test_no_unswitch( +entry: + br label %loop_begin +; CHECK-NEXT: entry: +; CHECK-NEXT: br label %loop_begin +; +; We shouldn't have unswitched into any other block either. +; CHECK-NOT: br i1 %cond + +loop_begin: + call void @x() + call void @x() + call void @x() + call void @x() + br i1 %cond, label %loop_a, label %loop_b +; CHECK: loop_begin: +; CHECK-NEXT: call void @x() +; CHECK-NEXT: call void @x() +; CHECK-NEXT: call void @x() +; CHECK-NEXT: call void @x() +; CHECK-NEXT: br i1 %cond, label %loop_a, label %loop_b + +loop_a: + call void @a() + br label %loop_latch + +loop_b: + call void @b() + br label %loop_latch + +loop_latch: + %v = load i1, i1* %ptr + br i1 %v, label %loop_begin, label %loop_exit + +loop_exit: + ret void +} + +; Now check that the smaller formulation of 'loop_begin' does in fact unswitch +; with our low threshold. +define void @test_unswitch(i1* %ptr, i1 %cond) { +; CHECK-LABEL: @test_unswitch( +entry: + br label %loop_begin +; CHECK-NEXT: entry: +; CHECK-NEXT: br i1 %cond, label %entry.split.us, label %entry.split + +loop_begin: + call void @x() + br i1 %cond, label %loop_a, label %loop_b + +loop_a: + call void @a() + br label %loop_latch +; The 'loop_a' unswitched loop. +; +; CHECK: entry.split.us: +; CHECK-NEXT: br label %loop_begin.us +; +; CHECK: loop_begin.us: +; CHECK-NEXT: call void @x() +; CHECK-NEXT: br label %loop_a.us +; +; CHECK: loop_a.us: +; CHECK-NEXT: call void @a() +; CHECK-NEXT: br label %loop_latch.us +; +; CHECK: loop_latch.us: +; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr +; CHECK-NEXT: br i1 %[[V]], label %loop_begin.us, label %loop_exit.split.us +; +; CHECK: loop_exit.split.us: +; CHECK-NEXT: br label %loop_exit + +loop_b: + call void @b() + br label %loop_latch +; The 'loop_b' unswitched loop. +; +; CHECK: entry.split: +; CHECK-NEXT: br label %loop_begin +; +; CHECK: loop_begin: +; CHECK-NEXT: call void @x() +; CHECK-NEXT: br label %loop_b +; +; CHECK: loop_b: +; CHECK-NEXT: call void @b() +; CHECK-NEXT: br label %loop_latch +; +; CHECK: loop_latch: +; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr +; CHECK-NEXT: br i1 %[[V]], label %loop_begin, label %loop_exit.split +; +; CHECK: loop_exit.split: +; CHECK-NEXT: br label %loop_exit + +loop_latch: + %v = load i1, i1* %ptr + br i1 %v, label %loop_begin, label %loop_exit + +loop_exit: + ret void +; CHECK: loop_exit: +; CHECK-NEXT: ret void +} + +; Check that even with large amounts of code on either side of the unswitched +; branch, if that code would be kept in only one of the unswitched clones it +; doesn't contribute to the cost. +define void @test_unswitch_non_dup_code(i1* %ptr, i1 %cond) { +; CHECK-LABEL: @test_unswitch_non_dup_code( +entry: + br label %loop_begin +; CHECK-NEXT: entry: +; CHECK-NEXT: br i1 %cond, label %entry.split.us, label %entry.split + +loop_begin: + call void @x() + br i1 %cond, label %loop_a, label %loop_b + +loop_a: + call void @a() + call void @a() + call void @a() + call void @a() + br label %loop_latch +; The 'loop_a' unswitched loop. +; +; CHECK: entry.split.us: +; CHECK-NEXT: br label %loop_begin.us +; +; CHECK: loop_begin.us: +; CHECK-NEXT: call void @x() +; CHECK-NEXT: br label %loop_a.us +; +; CHECK: loop_a.us: +; CHECK-NEXT: call void @a() +; CHECK-NEXT: call void @a() +; CHECK-NEXT: call void @a() +; CHECK-NEXT: call void @a() +; CHECK-NEXT: br label %loop_latch.us +; +; CHECK: loop_latch.us: +; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr +; CHECK-NEXT: br i1 %[[V]], label %loop_begin.us, label %loop_exit.split.us +; +; CHECK: loop_exit.split.us: +; CHECK-NEXT: br label %loop_exit + +loop_b: + call void @b() + call void @b() + call void @b() + call void @b() + br label %loop_latch +; The 'loop_b' unswitched loop. +; +; CHECK: entry.split: +; CHECK-NEXT: br label %loop_begin +; +; CHECK: loop_begin: +; CHECK-NEXT: call void @x() +; CHECK-NEXT: br label %loop_b +; +; CHECK: loop_b: +; CHECK-NEXT: call void @b() +; CHECK-NEXT: call void @b() +; CHECK-NEXT: call void @b() +; CHECK-NEXT: call void @b() +; CHECK-NEXT: br label %loop_latch +; +; CHECK: loop_latch: +; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr +; CHECK-NEXT: br i1 %[[V]], label %loop_begin, label %loop_exit.split +; +; CHECK: loop_exit.split: +; CHECK-NEXT: br label %loop_exit + +loop_latch: + %v = load i1, i1* %ptr + br i1 %v, label %loop_begin, label %loop_exit + +loop_exit: + ret void +; CHECK: loop_exit: +; CHECK-NEXT: ret void +} + +; Much like with non-duplicated code directly in the successor, we also won't +; duplicate even interesting CFGs. +define void @test_unswitch_non_dup_code_in_cfg(i1* %ptr, i1 %cond) { +; CHECK-LABEL: @test_unswitch_non_dup_code_in_cfg( +entry: + br label %loop_begin +; CHECK-NEXT: entry: +; CHECK-NEXT: br i1 %cond, label %entry.split.us, label %entry.split + +loop_begin: + call void @x() + br i1 %cond, label %loop_a, label %loop_b + +loop_a: + %v1 = load i1, i1* %ptr + br i1 %v1, label %loop_a_a, label %loop_a_b + +loop_a_a: + call void @a() + br label %loop_latch + +loop_a_b: + call void @a() + br label %loop_latch +; The 'loop_a' unswitched loop. +; +; CHECK: entry.split.us: +; CHECK-NEXT: br label %loop_begin.us +; +; CHECK: loop_begin.us: +; CHECK-NEXT: call void @x() +; CHECK-NEXT: br label %loop_a.us +; +; CHECK: loop_a.us: +; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr +; CHECK-NEXT: br i1 %[[V]], label %loop_a_a.us, label %loop_a_b.us +; +; CHECK: loop_a_b.us: +; CHECK-NEXT: call void @a() +; CHECK-NEXT: br label %loop_latch.us +; +; CHECK: loop_a_a.us: +; CHECK-NEXT: call void @a() +; CHECK-NEXT: br label %loop_latch.us +; +; CHECK: loop_latch.us: +; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr +; CHECK-NEXT: br i1 %[[V]], label %loop_begin.us, label %loop_exit.split.us +; +; CHECK: loop_exit.split.us: +; CHECK-NEXT: br label %loop_exit + +loop_b: + %v2 = load i1, i1* %ptr + br i1 %v2, label %loop_b_a, label %loop_b_b + +loop_b_a: + call void @b() + br label %loop_latch + +loop_b_b: + call void @b() + br label %loop_latch +; The 'loop_b' unswitched loop. +; +; CHECK: entry.split: +; CHECK-NEXT: br label %loop_begin +; +; CHECK: loop_begin: +; CHECK-NEXT: call void @x() +; CHECK-NEXT: br label %loop_b +; +; CHECK: loop_b: +; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr +; CHECK-NEXT: br i1 %[[V]], label %loop_b_a, label %loop_b_b +; +; CHECK: loop_b_a: +; CHECK-NEXT: call void @b() +; CHECK-NEXT: br label %loop_latch +; +; CHECK: loop_b_b: +; CHECK-NEXT: call void @b() +; CHECK-NEXT: br label %loop_latch +; +; CHECK: loop_latch: +; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr +; CHECK-NEXT: br i1 %[[V]], label %loop_begin, label %loop_exit.split +; +; CHECK: loop_exit.split: +; CHECK-NEXT: br label %loop_exit + +loop_latch: + %v3 = load i1, i1* %ptr + br i1 %v3, label %loop_begin, label %loop_exit + +loop_exit: + ret void +; CHECK: loop_exit: +; CHECK-NEXT: ret void +} + +; Check that even if there is *some* non-duplicated code on one side of an +; unswitch, we don't count any other code in the loop that will in fact have to +; be duplicated. +define void @test_no_unswitch_non_dup_code(i1* %ptr, i1 %cond) { +; CHECK-LABEL: @test_no_unswitch_non_dup_code( +entry: + br label %loop_begin +; CHECK-NEXT: entry: +; CHECK-NEXT: br label %loop_begin +; +; We shouldn't have unswitched into any other block either. +; CHECK-NOT: br i1 %cond + +loop_begin: + call void @x() + br i1 %cond, label %loop_a, label %loop_b +; CHECK: loop_begin: +; CHECK-NEXT: call void @x() +; CHECK-NEXT: br i1 %cond, label %loop_a, label %loop_b + +loop_a: + %v1 = load i1, i1* %ptr + br i1 %v1, label %loop_a_a, label %loop_a_b + +loop_a_a: + call void @a() + br label %loop_latch + +loop_a_b: + call void @a() + br label %loop_latch + +loop_b: + %v2 = load i1, i1* %ptr + br i1 %v2, label %loop_b_a, label %loop_b_b + +loop_b_a: + call void @b() + br label %loop_latch + +loop_b_b: + call void @b() + br label %loop_latch + +loop_latch: + call void @x() + call void @x() + %v = load i1, i1* %ptr + br i1 %v, label %loop_begin, label %loop_exit + +loop_exit: + ret void +} + +; Check that we still unswitch when the exit block contains lots of code, even +; though we do clone the exit block as part of unswitching. This should work +; because we should split the exit block before anything inside it. +define void @test_unswitch_large_exit(i1* %ptr, i1 %cond) { +; CHECK-LABEL: @test_unswitch_large_exit( +entry: + br label %loop_begin +; CHECK-NEXT: entry: +; CHECK-NEXT: br i1 %cond, label %entry.split.us, label %entry.split + +loop_begin: + call void @x() + br i1 %cond, label %loop_a, label %loop_b + +loop_a: + call void @a() + br label %loop_latch +; The 'loop_a' unswitched loop. +; +; CHECK: entry.split.us: +; CHECK-NEXT: br label %loop_begin.us +; +; CHECK: loop_begin.us: +; CHECK-NEXT: call void @x() +; CHECK-NEXT: br label %loop_a.us +; +; CHECK: loop_a.us: +; CHECK-NEXT: call void @a() +; CHECK-NEXT: br label %loop_latch.us +; +; CHECK: loop_latch.us: +; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr +; CHECK-NEXT: br i1 %[[V]], label %loop_begin.us, label %loop_exit.split.us +; +; CHECK: loop_exit.split.us: +; CHECK-NEXT: br label %loop_exit + +loop_b: + call void @b() + br label %loop_latch +; The 'loop_b' unswitched loop. +; +; CHECK: entry.split: +; CHECK-NEXT: br label %loop_begin +; +; CHECK: loop_begin: +; CHECK-NEXT: call void @x() +; CHECK-NEXT: br label %loop_b +; +; CHECK: loop_b: +; CHECK-NEXT: call void @b() +; CHECK-NEXT: br label %loop_latch +; +; CHECK: loop_latch: +; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr +; CHECK-NEXT: br i1 %[[V]], label %loop_begin, label %loop_exit.split +; +; CHECK: loop_exit.split: +; CHECK-NEXT: br label %loop_exit + +loop_latch: + %v = load i1, i1* %ptr + br i1 %v, label %loop_begin, label %loop_exit + +loop_exit: + call void @x() + call void @x() + call void @x() + call void @x() + ret void +; CHECK: loop_exit: +; CHECK-NEXT: call void @x() +; CHECK-NEXT: call void @x() +; CHECK-NEXT: call void @x() +; CHECK-NEXT: call void @x() +; CHECK-NEXT: ret void +} + +; Check that we handle a dedicated exit edge unswitch which is still +; non-trivial and has lots of code in the exit. +define void @test_unswitch_dedicated_exiting(i1* %ptr, i1 %cond) { +; CHECK-LABEL: @test_unswitch_dedicated_exiting( +entry: + br label %loop_begin +; CHECK-NEXT: entry: +; CHECK-NEXT: br i1 %cond, label %entry.split.us, label %entry.split + +loop_begin: + call void @x() + br i1 %cond, label %loop_a, label %loop_b_exit + +loop_a: + call void @a() + br label %loop_latch +; The 'loop_a' unswitched loop. +; +; CHECK: entry.split.us: +; CHECK-NEXT: br label %loop_begin.us +; +; CHECK: loop_begin.us: +; CHECK-NEXT: call void @x() +; CHECK-NEXT: br label %loop_a.us +; +; CHECK: loop_a.us: +; CHECK-NEXT: call void @a() +; CHECK-NEXT: br label %loop_latch.us +; +; CHECK: loop_latch.us: +; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr +; CHECK-NEXT: br i1 %[[V]], label %loop_begin.us, label %loop_exit.split.us +; +; CHECK: loop_exit.split.us: +; CHECK-NEXT: br label %loop_exit + +loop_b_exit: + call void @b() + call void @b() + call void @b() + call void @b() + ret void +; The 'loop_b_exit' unswitched exit path. +; +; CHECK: entry.split: +; CHECK-NEXT: br label %loop_begin +; +; CHECK: loop_begin: +; CHECK-NEXT: call void @x() +; CHECK-NEXT: br label %loop_b_exit +; +; CHECK: loop_b_exit: +; CHECK-NEXT: call void @b() +; CHECK-NEXT: call void @b() +; CHECK-NEXT: call void @b() +; CHECK-NEXT: call void @b() +; CHECK-NEXT: ret void + +loop_latch: + %v = load i1, i1* %ptr + br i1 %v, label %loop_begin, label %loop_exit + +loop_exit: + ret void +; CHECK: loop_exit: +; CHECK-NEXT: ret void +} Index: llvm/trunk/test/Transforms/SimpleLoopUnswitch/nontrivial-unswitch.ll =================================================================== --- llvm/trunk/test/Transforms/SimpleLoopUnswitch/nontrivial-unswitch.ll +++ llvm/trunk/test/Transforms/SimpleLoopUnswitch/nontrivial-unswitch.ll @@ -0,0 +1,2352 @@ +; RUN: opt -passes='loop(unswitch),verify' -enable-nontrivial-unswitch -S < %s | FileCheck %s +; RUN: opt -simple-loop-unswitch -enable-nontrivial-unswitch -S < %s | FileCheck %s + +declare void @a() +declare void @b() +declare void @c() +declare void @d() + +declare void @sink1(i32) +declare void @sink2(i32) + +; Negative test: we cannot unswitch convergent calls. +define void @test_no_unswitch_convergent(i1* %ptr, i1 %cond) { +; CHECK-LABEL: @test_no_unswitch_convergent( +entry: + br label %loop_begin +; CHECK-NEXT: entry: +; CHECK-NEXT: br label %loop_begin +; +; We shouldn't have unswitched into any other block either. +; CHECK-NOT: br i1 %cond + +loop_begin: + br i1 %cond, label %loop_a, label %loop_b +; CHECK: loop_begin: +; CHECK-NEXT: br i1 %cond, label %loop_a, label %loop_b + +loop_a: + call void @a() convergent + br label %loop_latch + +loop_b: + call void @b() + br label %loop_latch + +loop_latch: + %v = load i1, i1* %ptr + br i1 %v, label %loop_begin, label %loop_exit + +loop_exit: + ret void +} + +; Negative test: we cannot unswitch noduplicate calls. +define void @test_no_unswitch_noduplicate(i1* %ptr, i1 %cond) { +; CHECK-LABEL: @test_no_unswitch_noduplicate( +entry: + br label %loop_begin +; CHECK-NEXT: entry: +; CHECK-NEXT: br label %loop_begin +; +; We shouldn't have unswitched into any other block either. +; CHECK-NOT: br i1 %cond + +loop_begin: + br i1 %cond, label %loop_a, label %loop_b +; CHECK: loop_begin: +; CHECK-NEXT: br i1 %cond, label %loop_a, label %loop_b + +loop_a: + call void @a() noduplicate + br label %loop_latch + +loop_b: + call void @b() + br label %loop_latch + +loop_latch: + %v = load i1, i1* %ptr + br i1 %v, label %loop_begin, label %loop_exit + +loop_exit: + ret void +} + +declare i32 @__CxxFrameHandler3(...) + +; Negative test: we cannot unswitch when tokens are used across blocks as we +; might introduce PHIs. +define void @test_no_unswitch_cross_block_token(i1* %ptr, i1 %cond) nounwind personality i32 (...)* @__CxxFrameHandler3 { +; CHECK-LABEL: @test_no_unswitch_cross_block_token( +entry: + br label %loop_begin +; CHECK-NEXT: entry: +; CHECK-NEXT: br label %loop_begin +; +; We shouldn't have unswitched into any other block either. +; CHECK-NOT: br i1 %cond + +loop_begin: + br i1 %cond, label %loop_a, label %loop_b +; CHECK: loop_begin: +; CHECK-NEXT: br i1 %cond, label %loop_a, label %loop_b + +loop_a: + call void @a() + br label %loop_cont + +loop_b: + call void @b() + br label %loop_cont + +loop_cont: + invoke void @a() + to label %loop_latch unwind label %loop_catch + +loop_latch: + br label %loop_begin + +loop_catch: + %catch = catchswitch within none [label %loop_catch_latch, label %loop_exit] unwind to caller + +loop_catch_latch: + %catchpad_latch = catchpad within %catch [] + catchret from %catchpad_latch to label %loop_begin + +loop_exit: + %catchpad_exit = catchpad within %catch [] + catchret from %catchpad_exit to label %exit + +exit: + ret void +} + + +; Non-trivial loop unswitching where there are two distinct trivial conditions +; to unswitch within the loop. +define i32 @test1(i1* %ptr, i1 %cond1, i1 %cond2) { +; CHECK-LABEL: @test1( +entry: + br label %loop_begin +; CHECK-NEXT: entry: +; CHECK-NEXT: br i1 %cond1, label %entry.split.us, label %entry.split + +loop_begin: + br i1 %cond1, label %loop_a, label %loop_b + +loop_a: + call void @a() + br label %latch +; The 'loop_a' unswitched loop. +; +; CHECK: entry.split.us: +; CHECK-NEXT: br label %loop_begin.us +; +; CHECK: loop_begin.us: +; CHECK-NEXT: br label %loop_a.us +; +; CHECK: loop_a.us: +; CHECK-NEXT: call void @a() +; CHECK-NEXT: br label %latch.us +; +; CHECK: latch.us: +; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr +; CHECK-NEXT: br i1 %[[V]], label %loop_begin.us, label %loop_exit.split.us +; +; CHECK: loop_exit.split.us: +; CHECK-NEXT: br label %loop_exit + +loop_b: + br i1 %cond2, label %loop_b_a, label %loop_b_b +; The second unswitched condition. +; +; CHECK: entry.split: +; CHECK-NEXT: br i1 %cond2, label %entry.split.split.us, label %entry.split.split + +loop_b_a: + call void @b() + br label %latch +; The 'loop_b_a' unswitched loop. +; +; CHECK: entry.split.split.us: +; CHECK-NEXT: br label %loop_begin.us1 +; +; CHECK: loop_begin.us1: +; CHECK-NEXT: br label %loop_b.us +; +; CHECK: loop_b.us: +; CHECK-NEXT: br label %loop_b_a.us +; +; CHECK: loop_b_a.us: +; CHECK-NEXT: call void @b() +; CHECK-NEXT: br label %latch.us2 +; +; CHECK: latch.us2: +; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr +; CHECK-NEXT: br i1 %[[V]], label %loop_begin.us1, label %loop_exit.split.split.us +; +; CHECK: loop_exit.split.split.us: +; CHECK-NEXT: br label %loop_exit.split + +loop_b_b: + call void @c() + br label %latch +; The 'loop_b_b' unswitched loop. +; +; CHECK: entry.split.split: +; CHECK-NEXT: br label %loop_begin +; +; CHECK: loop_begin: +; CHECK-NEXT: br label %loop_b +; +; CHECK: loop_b: +; CHECK-NEXT: br label %loop_b_b +; +; CHECK: loop_b_b: +; CHECK-NEXT: call void @c() +; CHECK-NEXT: br label %latch +; +; CHECK: latch: +; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr +; CHECK-NEXT: br i1 %[[V]], label %loop_begin, label %loop_exit.split.split +; +; CHECK: loop_exit.split.split: +; CHECK-NEXT: br label %loop_exit.split + +latch: + %v = load i1, i1* %ptr + br i1 %v, label %loop_begin, label %loop_exit + +loop_exit: + ret i32 0 +; CHECK: loop_exit.split: +; CHECK-NEXT: br label %loop_exit +; +; CHECK: loop_exit: +; CHECK-NEXT: ret +} + +define i32 @test2(i1* %ptr, i1 %cond1, i32* %a.ptr, i32* %b.ptr, i32* %c.ptr) { +; CHECK-LABEL: @test2( +entry: + br label %loop_begin +; CHECK-NEXT: entry: +; CHECK-NEXT: br i1 %cond1, label %entry.split.us, label %entry.split + +loop_begin: + %v = load i1, i1* %ptr + br i1 %cond1, label %loop_a, label %loop_b + +loop_a: + %a = load i32, i32* %a.ptr + %ac = load i32, i32* %c.ptr + br i1 %v, label %loop_begin, label %loop_exit +; The 'loop_a' unswitched loop. +; +; CHECK: entry.split.us: +; CHECK-NEXT: br label %loop_begin.us +; +; CHECK: loop_begin.us: +; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr +; CHECK-NEXT: br label %loop_a.us +; +; CHECK: loop_a.us: +; CHECK-NEXT: %[[A:.*]] = load i32, i32* %a.ptr +; CHECK-NEXT: %[[AC:.*]] = load i32, i32* %c.ptr +; CHECK-NEXT: br i1 %[[V]], label %loop_begin.backedge.us, label %loop_exit.split.us +; +; CHECK: loop_exit.split.us: +; CHECK-NEXT: %[[A_LCSSA:.*]] = phi i32 [ %[[A]], %loop_a.us ] +; CHECK-NEXT: %[[AC_LCSSA:.*]] = phi i32 [ %[[AC]], %loop_a.us ] +; CHECK-NEXT: br label %loop_exit + +loop_b: + %b = load i32, i32* %b.ptr + %bc = load i32, i32* %c.ptr + br i1 %v, label %loop_begin, label %loop_exit +; The 'loop_b' unswitched loop. +; +; CHECK: entry.split: +; CHECK-NEXT: br label %loop_begin +; +; CHECK: loop_begin: +; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr +; CHECK-NEXT: br label %loop_b +; +; CHECK: loop_b: +; CHECK-NEXT: %[[B:.*]] = load i32, i32* %b.ptr +; CHECK-NEXT: %[[BC:.*]] = load i32, i32* %c.ptr +; CHECK-NEXT: br i1 %[[V]], label %loop_begin.backedge, label %loop_exit.split +; +; CHECK: loop_exit.split: +; CHECK-NEXT: %[[B_LCSSA:.*]] = phi i32 [ %[[B]], %loop_b ] +; CHECK-NEXT: %[[BC_LCSSA:.*]] = phi i32 [ %[[BC]], %loop_b ] +; CHECK-NEXT: br label %loop_exit + +loop_exit: + %ab.phi = phi i32 [ %a, %loop_a ], [ %b, %loop_b ] + %c.phi = phi i32 [ %ac, %loop_a ], [ %bc, %loop_b ] + %result = add i32 %ab.phi, %c.phi + ret i32 %result +; CHECK: loop_exit: +; CHECK-NEXT: %[[AB_PHI:.*]] = phi i32 [ %[[B_LCSSA]], %loop_exit.split ], [ %[[A_LCSSA]], %loop_exit.split.us ] +; CHECK-NEXT: %[[C_PHI:.*]] = phi i32 [ %[[BC_LCSSA]], %loop_exit.split ], [ %[[AC_LCSSA]], %loop_exit.split.us ] +; CHECK-NEXT: %[[RESULT:.*]] = add i32 %[[AB_PHI]], %[[C_PHI]] +; CHECK-NEXT: ret i32 %[[RESULT]] +} + +; Test a non-trivial unswitch of an exiting edge to an exit block with other +; in-loop predecessors. +define i32 @test3a(i1* %ptr, i1 %cond1, i32* %a.ptr, i32* %b.ptr) { +; CHECK-LABEL: @test3a( +entry: + br label %loop_begin +; CHECK-NEXT: entry: +; CHECK-NEXT: br i1 %cond1, label %entry.split.us, label %entry.split + +loop_begin: + %v = load i1, i1* %ptr + %a = load i32, i32* %a.ptr + br i1 %cond1, label %loop_exit, label %loop_b +; The 'loop_exit' clone. +; +; CHECK: entry.split.us: +; CHECK-NEXT: br label %loop_begin.us +; +; CHECK: loop_begin.us: +; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr +; CHECK-NEXT: %[[A:.*]] = load i32, i32* %a.ptr +; CHECK-NEXT: br label %loop_exit.split.us +; +; CHECK: loop_exit.split.us: +; CHECK-NEXT: %[[A_LCSSA:.*]] = phi i32 [ %[[A]], %loop_begin.us ] +; CHECK-NEXT: br label %loop_exit + +loop_b: + %b = load i32, i32* %b.ptr + br i1 %v, label %loop_begin, label %loop_exit +; The 'loop_b' unswitched loop. +; +; CHECK: entry.split: +; CHECK-NEXT: br label %loop_begin +; +; CHECK: loop_begin: +; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr +; CHECK-NEXT: %[[A:.*]] = load i32, i32* %a.ptr +; CHECK-NEXT: br label %loop_b +; +; CHECK: loop_b: +; CHECK-NEXT: %[[B:.*]] = load i32, i32* %b.ptr +; CHECK-NEXT: br i1 %[[V]], label %loop_begin, label %loop_exit.split +; +; CHECK: loop_exit.split: +; CHECK-NEXT: %[[B_LCSSA:.*]] = phi i32 [ %[[B]], %loop_b ] +; CHECK-NEXT: br label %loop_exit + +loop_exit: + %ab.phi = phi i32 [ %a, %loop_begin ], [ %b, %loop_b ] + ret i32 %ab.phi +; CHECK: loop_exit: +; CHECK-NEXT: %[[AB_PHI:.*]] = phi i32 [ %[[B_LCSSA]], %loop_exit.split ], [ %[[A_LCSSA]], %loop_exit.split.us ] +; CHECK-NEXT: ret i32 %[[AB_PHI]] +} + +; Test a non-trivial unswitch of an exiting edge to an exit block with other +; in-loop predecessors. This is the same as @test3a but with the reversed order +; of successors so that the exiting edge is *not* the cloned edge. +define i32 @test3b(i1* %ptr, i1 %cond1, i32* %a.ptr, i32* %b.ptr) { +; CHECK-LABEL: @test3b( +entry: + br label %loop_begin +; CHECK-NEXT: entry: +; CHECK-NEXT: br i1 %cond1, label %entry.split.us, label %entry.split + +loop_begin: + %v = load i1, i1* %ptr + %a = load i32, i32* %a.ptr + br i1 %cond1, label %loop_b, label %loop_exit +; The 'loop_b' unswitched loop. +; +; CHECK: entry.split.us: +; CHECK-NEXT: br label %loop_begin.us +; +; CHECK: loop_begin.us: +; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr +; CHECK-NEXT: %[[A:.*]] = load i32, i32* %a.ptr +; CHECK-NEXT: br label %loop_b.us +; +; CHECK: loop_b.us: +; CHECK-NEXT: %[[B:.*]] = load i32, i32* %b.ptr +; CHECK-NEXT: br i1 %[[V]], label %loop_begin.us, label %loop_exit.split.us +; +; CHECK: loop_exit.split.us: +; CHECK-NEXT: %[[B_LCSSA:.*]] = phi i32 [ %[[B]], %loop_b.us ] +; CHECK-NEXT: br label %loop_exit + +loop_b: + %b = load i32, i32* %b.ptr + br i1 %v, label %loop_begin, label %loop_exit +; The 'loop_b' unswitched loop. +; +; CHECK: entry.split: +; CHECK-NEXT: br label %loop_begin +; +; CHECK: loop_begin: +; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr +; CHECK-NEXT: %[[A:.*]] = load i32, i32* %a.ptr +; CHECK-NEXT: br label %loop_exit.split +; +; CHECK: loop_exit.split: +; CHECK-NEXT: %[[A_LCSSA:.*]] = phi i32 [ %[[A]], %loop_begin ] +; CHECK-NEXT: br label %loop_exit + +loop_exit: + %ab.phi = phi i32 [ %b, %loop_b ], [ %a, %loop_begin ] + ret i32 %ab.phi +; CHECK: loop_exit: +; CHECK-NEXT: %[[AB_PHI:.*]] = phi i32 [ %[[A_LCSSA]], %loop_exit.split ], [ %[[B_LCSSA]], %loop_exit.split.us ] +; CHECK-NEXT: ret i32 %[[AB_PHI]] +} + +; Test a non-trivial unswitch of an exiting edge to an exit block with no other +; in-loop predecessors. +define void @test4a(i1* %ptr, i1 %cond1, i32* %a.ptr, i32* %b.ptr) { +; CHECK-LABEL: @test4a( +entry: + br label %loop_begin +; CHECK-NEXT: entry: +; CHECK-NEXT: br i1 %cond1, label %entry.split.us, label %entry.split + +loop_begin: + %v = load i1, i1* %ptr + %a = load i32, i32* %a.ptr + br i1 %cond1, label %loop_exit1, label %loop_b +; The 'loop_exit' clone. +; +; CHECK: entry.split.us: +; CHECK-NEXT: br label %loop_begin.us +; +; CHECK: loop_begin.us: +; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr +; CHECK-NEXT: %[[A:.*]] = load i32, i32* %a.ptr +; CHECK-NEXT: br label %loop_exit1.split.us +; +; CHECK: loop_exit1.split.us: +; CHECK-NEXT: %[[A_LCSSA:.*]] = phi i32 [ %[[A]], %loop_begin.us ] +; CHECK-NEXT: br label %loop_exit1 + +loop_b: + %b = load i32, i32* %b.ptr + br i1 %v, label %loop_begin, label %loop_exit2 +; The 'loop_b' unswitched loop. +; +; CHECK: entry.split: +; CHECK-NEXT: br label %loop_begin +; +; CHECK: loop_begin: +; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr +; CHECK-NEXT: %[[A:.*]] = load i32, i32* %a.ptr +; CHECK-NEXT: br label %loop_b +; +; CHECK: loop_b: +; CHECK-NEXT: %[[B:.*]] = load i32, i32* %b.ptr +; CHECK-NEXT: br i1 %[[V]], label %loop_begin, label %loop_exit2 + +loop_exit1: + %a.phi = phi i32 [ %a, %loop_begin ] + call void @sink1(i32 %a.phi) + ret void +; CHECK: loop_exit1: +; CHECK-NEXT: %[[A_PHI:.*]] = phi i32 [ %[[A_LCSSA]], %loop_exit1.split.us ] +; CHECK-NEXT: call void @sink1(i32 %[[A_PHI]]) +; CHECK-NEXT: ret void + +loop_exit2: + %b.phi = phi i32 [ %b, %loop_b ] + call void @sink2(i32 %b.phi) + ret void +; CHECK: loop_exit2: +; CHECK-NEXT: %[[B_PHI:.*]] = phi i32 [ %[[B]], %loop_b ] +; CHECK-NEXT: call void @sink2(i32 %[[B_PHI]]) +; CHECK-NEXT: ret void +} + +; Test a non-trivial unswitch of an exiting edge to an exit block with no other +; in-loop predecessors. This is the same as @test4a but with the edges reversed +; so that the exiting edge is *not* the cloned edge. +define void @test4b(i1* %ptr, i1 %cond1, i32* %a.ptr, i32* %b.ptr) { +; CHECK-LABEL: @test4b( +entry: + br label %loop_begin +; CHECK-NEXT: entry: +; CHECK-NEXT: br i1 %cond1, label %entry.split.us, label %entry.split + +loop_begin: + %v = load i1, i1* %ptr + %a = load i32, i32* %a.ptr + br i1 %cond1, label %loop_b, label %loop_exit1 +; The 'loop_b' clone. +; +; CHECK: entry.split.us: +; CHECK-NEXT: br label %loop_begin.us +; +; CHECK: loop_begin.us: +; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr +; CHECK-NEXT: %[[A:.*]] = load i32, i32* %a.ptr +; CHECK-NEXT: br label %loop_b.us +; +; CHECK: loop_b.us: +; CHECK-NEXT: %[[B:.*]] = load i32, i32* %b.ptr +; CHECK-NEXT: br i1 %[[V]], label %loop_begin.us, label %loop_exit2.split.us +; +; CHECK: loop_exit2.split.us: +; CHECK-NEXT: %[[B_LCSSA:.*]] = phi i32 [ %[[B]], %loop_b.us ] +; CHECK-NEXT: br label %loop_exit2 + +loop_b: + %b = load i32, i32* %b.ptr + br i1 %v, label %loop_begin, label %loop_exit2 +; The 'loop_exit' unswitched path. +; +; CHECK: entry.split: +; CHECK-NEXT: br label %loop_begin +; +; CHECK: loop_begin: +; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr +; CHECK-NEXT: %[[A:.*]] = load i32, i32* %a.ptr +; CHECK-NEXT: br label %loop_exit1 + +loop_exit1: + %a.phi = phi i32 [ %a, %loop_begin ] + call void @sink1(i32 %a.phi) + ret void +; CHECK: loop_exit1: +; CHECK-NEXT: %[[A_PHI:.*]] = phi i32 [ %[[A]], %loop_begin ] +; CHECK-NEXT: call void @sink1(i32 %[[A_PHI]]) +; CHECK-NEXT: ret void + +loop_exit2: + %b.phi = phi i32 [ %b, %loop_b ] + call void @sink2(i32 %b.phi) + ret void +; CHECK: loop_exit2: +; CHECK-NEXT: %[[B_PHI:.*]] = phi i32 [ %[[B_LCSSA]], %loop_exit2.split.us ] +; CHECK-NEXT: call void @sink2(i32 %[[B_PHI]]) +; CHECK-NEXT: ret void +} + +; Test a non-trivial unswitch of an exiting edge to an exit block with no other +; in-loop predecessors. This is the same as @test4a but with a common merge +; block after the independent loop exits. This requires a different structural +; update to the dominator tree. +define void @test4c(i1* %ptr, i1 %cond1, i32* %a.ptr, i32* %b.ptr) { +; CHECK-LABEL: @test4c( +entry: + br label %loop_begin +; CHECK-NEXT: entry: +; CHECK-NEXT: br i1 %cond1, label %entry.split.us, label %entry.split + +loop_begin: + %v = load i1, i1* %ptr + %a = load i32, i32* %a.ptr + br i1 %cond1, label %loop_exit1, label %loop_b +; The 'loop_exit' clone. +; +; CHECK: entry.split.us: +; CHECK-NEXT: br label %loop_begin.us +; +; CHECK: loop_begin.us: +; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr +; CHECK-NEXT: %[[A:.*]] = load i32, i32* %a.ptr +; CHECK-NEXT: br label %loop_exit1.split.us +; +; CHECK: loop_exit1.split.us: +; CHECK-NEXT: %[[A_LCSSA:.*]] = phi i32 [ %[[A]], %loop_begin.us ] +; CHECK-NEXT: br label %loop_exit1 + +loop_b: + %b = load i32, i32* %b.ptr + br i1 %v, label %loop_begin, label %loop_exit2 +; The 'loop_b' unswitched loop. +; +; CHECK: entry.split: +; CHECK-NEXT: br label %loop_begin +; +; CHECK: loop_begin: +; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr +; CHECK-NEXT: %[[A:.*]] = load i32, i32* %a.ptr +; CHECK-NEXT: br label %loop_b +; +; CHECK: loop_b: +; CHECK-NEXT: %[[B:.*]] = load i32, i32* %b.ptr +; CHECK-NEXT: br i1 %[[V]], label %loop_begin, label %loop_exit2 + +loop_exit1: + %a.phi = phi i32 [ %a, %loop_begin ] + call void @sink1(i32 %a.phi) + br label %exit +; CHECK: loop_exit1: +; CHECK-NEXT: %[[A_PHI:.*]] = phi i32 [ %[[A_LCSSA]], %loop_exit1.split.us ] +; CHECK-NEXT: call void @sink1(i32 %[[A_PHI]]) +; CHECK-NEXT: br label %exit + +loop_exit2: + %b.phi = phi i32 [ %b, %loop_b ] + call void @sink2(i32 %b.phi) + br label %exit +; CHECK: loop_exit2: +; CHECK-NEXT: %[[B_PHI:.*]] = phi i32 [ %[[B]], %loop_b ] +; CHECK-NEXT: call void @sink2(i32 %[[B_PHI]]) +; CHECK-NEXT: br label %exit + +exit: + ret void +; CHECK: exit: +; CHECK-NEXT: ret void +} + +; Test that we can unswitch a condition out of multiple layers of a loop nest. +define i32 @test5(i1* %ptr, i1 %cond1, i32* %a.ptr, i32* %b.ptr) { +; CHECK-LABEL: @test5( +entry: + br label %loop_begin +; CHECK-NEXT: entry: +; CHECK-NEXT: br i1 %cond1, label %loop_begin.split.us, label %entry.split +; +; CHECK: entry.split: +; CHECK-NEXT: br label %loop_begin +; +; CHECK: loop_begin: +; CHECK-NEXT: br label %loop_begin.split + +loop_begin: + br label %inner_loop_begin + +inner_loop_begin: + %v = load i1, i1* %ptr + %a = load i32, i32* %a.ptr + br i1 %cond1, label %loop_exit, label %inner_loop_b +; The 'loop_exit' clone. +; +; CHECK: loop_begin.split.us: +; CHECK-NEXT: br label %inner_loop_begin.us +; +; CHECK: inner_loop_begin.us: +; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr +; CHECK-NEXT: %[[A:.*]] = load i32, i32* %a.ptr +; CHECK-NEXT: br label %loop_exit.loopexit.split.us +; +; CHECK: loop_exit.loopexit.split.us: +; CHECK-NEXT: %[[A_LCSSA:.*]] = phi i32 [ %[[A]], %inner_loop_begin.us ] +; CHECK-NEXT: br label %loop_exit + +inner_loop_b: + %b = load i32, i32* %b.ptr + br i1 %v, label %inner_loop_begin, label %loop_latch +; The 'inner_loop_b' unswitched loop. +; +; CHECK: loop_begin.split: +; CHECK-NEXT: br label %inner_loop_begin +; +; CHECK: inner_loop_begin: +; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr +; CHECK-NEXT: %[[A:.*]] = load i32, i32* %a.ptr +; CHECK-NEXT: br label %inner_loop_b +; +; CHECK: inner_loop_b: +; CHECK-NEXT: %[[B:.*]] = load i32, i32* %b.ptr +; CHECK-NEXT: br i1 %[[V]], label %inner_loop_begin, label %loop_latch + +loop_latch: + %b.phi = phi i32 [ %b, %inner_loop_b ] + %v2 = load i1, i1* %ptr + br i1 %v2, label %loop_begin, label %loop_exit +; CHECK: loop_latch: +; CHECK-NEXT: %[[B_LCSSA:.*]] = phi i32 [ %[[B]], %inner_loop_b ] +; CHECK-NEXT: %[[V2:.*]] = load i1, i1* %ptr +; CHECK-NEXT: br i1 %[[V2]], label %loop_begin, label %loop_exit.loopexit1 + +loop_exit: + %ab.phi = phi i32 [ %a, %inner_loop_begin ], [ %b.phi, %loop_latch ] + ret i32 %ab.phi +; CHECK: loop_exit.loopexit: +; CHECK-NEXT: %[[A_PHI:.*]] = phi i32 [ %[[A_LCSSA]], %loop_exit.loopexit.split.us ] +; CHECK-NEXT: br label %loop_exit +; +; CHECK: loop_exit.loopexit1: +; CHECK-NEXT: %[[B_PHI:.*]] = phi i32 [ %[[B_LCSSA]], %loop_latch ] +; CHECK-NEXT: br label %loop_exit +; +; CHECK: loop_exit: +; CHECK-NEXT: %[[AB_PHI:.*]] = phi i32 [ %[[A_PHI]], %loop_exit.loopexit ], [ %[[B_PHI]], %loop_exit.loopexit1 ] +; CHECK-NEXT: ret i32 %[[AB_PHI]] +} + +; Test that we can unswitch a condition where we end up only cloning some of +; the nested loops and needing to delete some of the nested loops. +define i32 @test6(i1* %ptr, i1 %cond1, i32* %a.ptr, i32* %b.ptr) { +; CHECK-LABEL: @test6( +entry: + br label %loop_begin +; CHECK-NEXT: entry: +; CHECK-NEXT: br i1 %cond1, label %entry.split.us, label %entry.split + +loop_begin: + %v = load i1, i1* %ptr + br i1 %cond1, label %loop_a, label %loop_b + +loop_a: + br label %loop_a_inner + +loop_a_inner: + %va = load i1, i1* %ptr + %a = load i32, i32* %a.ptr + br i1 %va, label %loop_a_inner, label %loop_a_inner_exit + +loop_a_inner_exit: + %a.lcssa = phi i32 [ %a, %loop_a_inner ] + br label %latch +; The 'loop_a' cloned loop. +; +; CHECK: entry.split.us: +; CHECK-NEXT: br label %loop_begin.us +; +; CHECK: loop_begin.us: +; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr +; CHECK-NEXT: br label %loop_a.us +; +; CHECK: loop_a.us: +; CHECK-NEXT: br label %loop_a_inner.us +; +; CHECK: loop_a_inner.us +; CHECK-NEXT: %[[VA:.*]] = load i1, i1* %ptr +; CHECK-NEXT: %[[A:.*]] = load i32, i32* %a.ptr +; CHECK-NEXT: br i1 %[[VA]], label %loop_a_inner.us, label %loop_a_inner_exit.us +; +; CHECK: loop_a_inner_exit.us: +; CHECK-NEXT: %[[A_INNER_LCSSA:.*]] = phi i32 [ %[[A]], %loop_a_inner.us ] +; CHECK-NEXT: br label %latch.us +; +; CHECK: latch.us: +; CHECK-NEXT: %[[A_PHI:.*]] = phi i32 [ %[[A_INNER_LCSSA]], %loop_a_inner_exit.us ] +; CHECK-NEXT: br i1 %[[V]], label %loop_begin.us, label %loop_exit.split.us +; +; CHECK: loop_exit.split.us: +; CHECK-NEXT: %[[A_LCSSA:.*]] = phi i32 [ %[[A_PHI]], %latch.us ] +; CHECK-NEXT: br label %loop_exit + +loop_b: + br label %loop_b_inner + +loop_b_inner: + %vb = load i1, i1* %ptr + %b = load i32, i32* %b.ptr + br i1 %vb, label %loop_b_inner, label %loop_b_inner_exit + +loop_b_inner_exit: + %b.lcssa = phi i32 [ %b, %loop_b_inner ] + br label %latch + +latch: + %ab.phi = phi i32 [ %a.lcssa, %loop_a_inner_exit ], [ %b.lcssa, %loop_b_inner_exit ] + br i1 %v, label %loop_begin, label %loop_exit +; The 'loop_b' unswitched loop. +; +; CHECK: entry.split: +; CHECK-NEXT: br label %loop_begin +; +; CHECK: loop_begin: +; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr +; CHECK-NEXT: br label %loop_b +; +; CHECK: loop_b: +; CHECK-NEXT: br label %loop_b_inner +; +; CHECK: loop_b_inner +; CHECK-NEXT: %[[VB:.*]] = load i1, i1* %ptr +; CHECK-NEXT: %[[B:.*]] = load i32, i32* %b.ptr +; CHECK-NEXT: br i1 %[[VB]], label %loop_b_inner, label %loop_b_inner_exit +; +; CHECK: loop_b_inner_exit: +; CHECK-NEXT: %[[B_INNER_LCSSA:.*]] = phi i32 [ %[[B]], %loop_b_inner ] +; CHECK-NEXT: br label %latch +; +; CHECK: latch: +; CHECK-NEXT: %[[B_PHI:.*]] = phi i32 [ %[[B_INNER_LCSSA]], %loop_b_inner_exit ] +; CHECK-NEXT: br i1 %[[V]], label %loop_begin, label %loop_exit.split +; +; CHECK: loop_exit.split: +; CHECK-NEXT: %[[B_LCSSA:.*]] = phi i32 [ %[[B_PHI]], %latch ] +; CHECK-NEXT: br label %loop_exit + +loop_exit: + %ab.lcssa = phi i32 [ %ab.phi, %latch ] + ret i32 %ab.lcssa +; CHECK: loop_exit: +; CHECK-NEXT: %[[AB_PHI:.*]] = phi i32 [ %[[B_LCSSA]], %loop_exit.split ], [ %[[A_LCSSA]], %loop_exit.split.us ] +; CHECK-NEXT: ret i32 %[[AB_PHI]] +} + +; Test that when unswitching a deeply nested loop condition in a way that +; produces a non-loop clone that can reach multiple exit blocks which are part +; of different outer loops we correctly divide the cloned loop blocks between +; the outer loops based on reachability. +define i32 @test7a(i1* %ptr, i1* %cond.ptr, i32* %a.ptr, i32* %b.ptr) { +; CHECK-LABEL: @test7a( +entry: + br label %loop_begin +; CHECK-NEXT: entry: +; CHECK-NEXT: br label %loop_begin + +loop_begin: + %a = load i32, i32* %a.ptr + br label %inner_loop_begin +; CHECK: loop_begin: +; CHECK-NEXT: %[[A:.*]] = load i32, i32* %a.ptr +; CHECK-NEXT: br label %inner_loop_begin + +inner_loop_begin: + %a.phi = phi i32 [ %a, %loop_begin ], [ %a2, %inner_inner_loop_exit ] + %cond = load i1, i1* %cond.ptr + %b = load i32, i32* %b.ptr + br label %inner_inner_loop_begin +; CHECK: inner_loop_begin: +; CHECK-NEXT: %[[A_INNER_PHI:.*]] = phi i32 [ %[[A]], %loop_begin ], [ %[[A2:.*]], %inner_inner_loop_exit ] +; CHECK-NEXT: %[[COND:.*]] = load i1, i1* %cond.ptr +; CHECK-NEXT: %[[B:.*]] = load i32, i32* %b.ptr +; CHECK-NEXT: br i1 %[[COND]], label %inner_loop_begin.split.us, label %inner_loop_begin.split + +inner_inner_loop_begin: + %v1 = load i1, i1* %ptr + br i1 %v1, label %inner_inner_loop_a, label %inner_inner_loop_b + +inner_inner_loop_a: + %v2 = load i1, i1* %ptr + br i1 %v2, label %loop_exit, label %inner_inner_loop_c + +inner_inner_loop_b: + %v3 = load i1, i1* %ptr + br i1 %v3, label %inner_inner_loop_exit, label %inner_inner_loop_c + +inner_inner_loop_c: + %v4 = load i1, i1* %ptr + br i1 %v4, label %inner_loop_exit, label %inner_inner_loop_d + +inner_inner_loop_d: + br i1 %cond, label %inner_loop_exit, label %inner_inner_loop_begin +; The cloned copy that always exits with the adjustments required to fix up +; loop exits. +; +; CHECK: inner_loop_begin.split.us: +; CHECK-NEXT: br label %inner_inner_loop_begin.us +; +; CHECK: inner_inner_loop_begin.us: +; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr +; CHECK-NEXT: br i1 %[[V]], label %inner_inner_loop_a.us, label %inner_inner_loop_b.us +; +; CHECK: inner_inner_loop_b.us: +; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr +; CHECK-NEXT: br i1 %[[V]], label %inner_inner_loop_exit.split.us, label %inner_inner_loop_c.us.loopexit +; +; CHECK: inner_inner_loop_a.us: +; CHECK-NEXT: %[[A_NEW_LCSSA:.*]] = phi i32 [ %[[A_INNER_PHI]], %inner_inner_loop_begin.us ] +; CHECK-NEXT: %[[B_NEW_LCSSA:.*]] = phi i32 [ %[[B]], %inner_inner_loop_begin.us ] +; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr +; CHECK-NEXT: br i1 %[[V]], label %loop_exit.split.us, label %inner_inner_loop_c.us +; +; CHECK: inner_inner_loop_c.us.loopexit: +; CHECK-NEXT: br label %inner_inner_loop_c.us +; +; CHECK: inner_inner_loop_c.us: +; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr +; CHECK-NEXT: br i1 %[[V]], label %inner_loop_exit.loopexit.split.us, label %inner_inner_loop_d.us +; +; CHECK: inner_inner_loop_d.us: +; CHECK-NEXT: br label %inner_loop_exit.loopexit.split +; +; CHECK: inner_inner_loop_exit.split.us: +; CHECK-NEXT: br label %inner_inner_loop_exit +; +; CHECK: loop_exit.split.us: +; CHECK-NEXT: %[[A_LCSSA_US:.*]] = phi i32 [ %[[A_NEW_LCSSA]], %inner_inner_loop_a.us ] +; CHECK-NEXT: %[[B_LCSSA_US:.*]] = phi i32 [ %[[B_NEW_LCSSA]], %inner_inner_loop_a.us ] +; CHECK-NEXT: br label %loop_exit +; +; CHECK: inner_loop_exit.loopexit.split.us: +; CHECK-NEXT: br label %inner_loop_exit.loopexit +; +; The original copy that continues to loop. +; +; CHECK: inner_loop_begin.split: +; CHECK-NEXT: br label %inner_inner_loop_begin +; +; CHECK: inner_inner_loop_begin: +; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr +; CHECK-NEXT: br i1 %[[V]], label %inner_inner_loop_a, label %inner_inner_loop_b +; +; CHECK: inner_inner_loop_a: +; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr +; CHECK-NEXT: br i1 %[[V]], label %loop_exit.split, label %inner_inner_loop_c +; +; CHECK: inner_inner_loop_b: +; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr +; CHECK-NEXT: br i1 %[[V]], label %inner_inner_loop_exit.split, label %inner_inner_loop_c +; +; CHECK: inner_inner_loop_c: +; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr +; CHECK-NEXT: br i1 %[[V]], label %inner_loop_exit.loopexit.split, label %inner_inner_loop_d +; +; CHECK: inner_inner_loop_d: +; CHECK-NEXT: br label %inner_inner_loop_begin +; +; CHECK: inner_inner_loop_exit.split: +; CHECK-NEXT: br label %inner_inner_loop_exit + +inner_inner_loop_exit: + %a2 = load i32, i32* %a.ptr + %v5 = load i1, i1* %ptr + br i1 %v5, label %inner_loop_exit, label %inner_loop_begin +; CHECK: inner_inner_loop_exit: +; CHECK-NEXT: %[[A2]] = load i32, i32* %a.ptr +; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr +; CHECK-NEXT: br i1 %[[V]], label %inner_loop_exit.loopexit1, label %inner_loop_begin + +inner_loop_exit: + br label %loop_begin +; CHECK: inner_loop_exit.loopexit.split: +; CHECK-NEXT: br label %inner_loop_exit.loopexit +; +; CHECK: inner_loop_exit.loopexit: +; CHECK-NEXT: br label %inner_loop_exit +; +; CHECK: inner_loop_exit.loopexit1: +; CHECK-NEXT: br label %inner_loop_exit +; +; CHECK: inner_loop_exit: +; CHECK-NEXT: br label %loop_begin + +loop_exit: + %a.lcssa = phi i32 [ %a.phi, %inner_inner_loop_a ] + %b.lcssa = phi i32 [ %b, %inner_inner_loop_a ] + %result = add i32 %a.lcssa, %b.lcssa + ret i32 %result +; CHECK: loop_exit.split: +; CHECK-NEXT: %[[A_LCSSA:.*]] = phi i32 [ %[[A_INNER_PHI]], %inner_inner_loop_a ] +; CHECK-NEXT: %[[B_LCSSA:.*]] = phi i32 [ %[[B]], %inner_inner_loop_a ] +; CHECK-NEXT: br label %loop_exit +; +; CHECK: loop_exit: +; CHECK-NEXT: %[[A_PHI:.*]] = phi i32 [ %[[A_LCSSA]], %loop_exit.split ], [ %[[A_LCSSA_US]], %loop_exit.split.us ] +; CHECK-NEXT: %[[B_PHI:.*]] = phi i32 [ %[[B_LCSSA]], %loop_exit.split ], [ %[[B_LCSSA_US]], %loop_exit.split.us ] +; CHECK-NEXT: %[[RESULT:.*]] = add i32 %[[A_PHI]], %[[B_PHI]] +; CHECK-NEXT: ret i32 %[[RESULT]] +} + +; Same pattern as @test7a but here the original loop becomes a non-loop that +; can reach multiple exit blocks which are part of different outer loops. +define i32 @test7b(i1* %ptr, i1* %cond.ptr, i32* %a.ptr, i32* %b.ptr) { +; CHECK-LABEL: @test7b( +entry: + br label %loop_begin +; CHECK-NEXT: entry: +; CHECK-NEXT: br label %loop_begin + +loop_begin: + %a = load i32, i32* %a.ptr + br label %inner_loop_begin +; CHECK: loop_begin: +; CHECK-NEXT: %[[A:.*]] = load i32, i32* %a.ptr +; CHECK-NEXT: br label %inner_loop_begin + +inner_loop_begin: + %a.phi = phi i32 [ %a, %loop_begin ], [ %a2, %inner_inner_loop_exit ] + %cond = load i1, i1* %cond.ptr + %b = load i32, i32* %b.ptr + br label %inner_inner_loop_begin +; CHECK: inner_loop_begin: +; CHECK-NEXT: %[[A_INNER_PHI:.*]] = phi i32 [ %[[A]], %loop_begin ], [ %[[A2:.*]], %inner_inner_loop_exit ] +; CHECK-NEXT: %[[COND:.*]] = load i1, i1* %cond.ptr +; CHECK-NEXT: %[[B:.*]] = load i32, i32* %b.ptr +; CHECK-NEXT: br i1 %[[COND]], label %inner_loop_begin.split.us, label %inner_loop_begin.split + +inner_inner_loop_begin: + %v1 = load i1, i1* %ptr + br i1 %v1, label %inner_inner_loop_a, label %inner_inner_loop_b + +inner_inner_loop_a: + %v2 = load i1, i1* %ptr + br i1 %v2, label %loop_exit, label %inner_inner_loop_c + +inner_inner_loop_b: + %v3 = load i1, i1* %ptr + br i1 %v3, label %inner_inner_loop_exit, label %inner_inner_loop_c + +inner_inner_loop_c: + %v4 = load i1, i1* %ptr + br i1 %v4, label %inner_loop_exit, label %inner_inner_loop_d + +inner_inner_loop_d: + br i1 %cond, label %inner_inner_loop_begin, label %inner_loop_exit +; The cloned copy that continues looping. +; +; CHECK: inner_loop_begin.split.us: +; CHECK-NEXT: br label %inner_inner_loop_begin.us +; +; CHECK: inner_inner_loop_begin.us: +; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr +; CHECK-NEXT: br i1 %[[V]], label %inner_inner_loop_a.us, label %inner_inner_loop_b.us +; +; CHECK: inner_inner_loop_b.us: +; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr +; CHECK-NEXT: br i1 %[[V]], label %inner_inner_loop_exit.split.us, label %inner_inner_loop_c.us +; +; CHECK: inner_inner_loop_a.us: +; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr +; CHECK-NEXT: br i1 %[[V]], label %loop_exit.split.us, label %inner_inner_loop_c.us +; +; CHECK: inner_inner_loop_c.us: +; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr +; CHECK-NEXT: br i1 %[[V]], label %inner_loop_exit.loopexit.split.us, label %inner_inner_loop_d.us +; +; CHECK: inner_inner_loop_d.us: +; CHECK-NEXT: br label %inner_inner_loop_begin.us +; +; CHECK: inner_inner_loop_exit.split.us: +; CHECK-NEXT: br label %inner_inner_loop_exit +; +; CHECK: loop_exit.split.us: +; CHECK-NEXT: %[[A_LCSSA_US:.*]] = phi i32 [ %[[A_INNER_PHI]], %inner_inner_loop_a.us ] +; CHECK-NEXT: %[[B_LCSSA_US:.*]] = phi i32 [ %[[B]], %inner_inner_loop_a.us ] +; CHECK-NEXT: br label %loop_exit +; +; CHECK: inner_loop_exit.loopexit.split.us: +; CHECK-NEXT: br label %inner_loop_exit.loopexit +; +; The original copy that now always exits and needs adjustments for exit +; blocks. +; +; CHECK: inner_loop_begin.split: +; CHECK-NEXT: br label %inner_inner_loop_begin +; +; CHECK: inner_inner_loop_begin: +; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr +; CHECK-NEXT: br i1 %[[V]], label %inner_inner_loop_a, label %inner_inner_loop_b +; +; CHECK: inner_inner_loop_a: +; CHECK-NEXT: %[[A_NEW_LCSSA:.*]] = phi i32 [ %[[A_INNER_PHI]], %inner_inner_loop_begin ] +; CHECK-NEXT: %[[B_NEW_LCSSA:.*]] = phi i32 [ %[[B]], %inner_inner_loop_begin ] +; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr +; CHECK-NEXT: br i1 %[[V]], label %loop_exit.split, label %inner_inner_loop_c +; +; CHECK: inner_inner_loop_b: +; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr +; CHECK-NEXT: br i1 %[[V]], label %inner_inner_loop_exit.split, label %inner_inner_loop_c.loopexit +; +; CHECK: inner_inner_loop_c.loopexit: +; CHECK-NEXT: br label %inner_inner_loop_c +; +; CHECK: inner_inner_loop_c: +; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr +; CHECK-NEXT: br i1 %[[V]], label %inner_loop_exit.loopexit.split, label %inner_inner_loop_d +; +; CHECK: inner_inner_loop_d: +; CHECK-NEXT: br label %inner_loop_exit.loopexit.split +; +; CHECK: inner_inner_loop_exit.split: +; CHECK-NEXT: br label %inner_inner_loop_exit + +inner_inner_loop_exit: + %a2 = load i32, i32* %a.ptr + %v5 = load i1, i1* %ptr + br i1 %v5, label %inner_loop_exit, label %inner_loop_begin +; CHECK: inner_inner_loop_exit: +; CHECK-NEXT: %[[A2]] = load i32, i32* %a.ptr +; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr +; CHECK-NEXT: br i1 %[[V]], label %inner_loop_exit.loopexit1, label %inner_loop_begin + +inner_loop_exit: + br label %loop_begin +; CHECK: inner_loop_exit.loopexit.split: +; CHECK-NEXT: br label %inner_loop_exit.loopexit +; +; CHECK: inner_loop_exit.loopexit: +; CHECK-NEXT: br label %inner_loop_exit +; +; CHECK: inner_loop_exit.loopexit1: +; CHECK-NEXT: br label %inner_loop_exit +; +; CHECK: inner_loop_exit: +; CHECK-NEXT: br label %loop_begin + +loop_exit: + %a.lcssa = phi i32 [ %a.phi, %inner_inner_loop_a ] + %b.lcssa = phi i32 [ %b, %inner_inner_loop_a ] + %result = add i32 %a.lcssa, %b.lcssa + ret i32 %result +; CHECK: loop_exit.split: +; CHECK-NEXT: %[[A_LCSSA:.*]] = phi i32 [ %[[A_NEW_LCSSA]], %inner_inner_loop_a ] +; CHECK-NEXT: %[[B_LCSSA:.*]] = phi i32 [ %[[B_NEW_LCSSA]], %inner_inner_loop_a ] +; CHECK-NEXT: br label %loop_exit +; +; CHECK: loop_exit: +; CHECK-NEXT: %[[A_PHI:.*]] = phi i32 [ %[[A_LCSSA]], %loop_exit.split ], [ %[[A_LCSSA_US]], %loop_exit.split.us ] +; CHECK-NEXT: %[[B_PHI:.*]] = phi i32 [ %[[B_LCSSA]], %loop_exit.split ], [ %[[B_LCSSA_US]], %loop_exit.split.us ] +; CHECK-NEXT: %[[RESULT:.*]] = add i32 %[[A_PHI]], %[[B_PHI]] +; CHECK-NEXT: ret i32 %[[RESULT]] +} + +; Test that when the exit block set of an inner loop changes to start at a less +; high level of the loop nest we correctly hoist the loop up the nest. +define i32 @test8a(i1* %ptr, i1* %cond.ptr, i32* %a.ptr, i32* %b.ptr) { +; CHECK-LABEL: @test8a( +entry: + br label %loop_begin +; CHECK-NEXT: entry: +; CHECK-NEXT: br label %loop_begin + +loop_begin: + %a = load i32, i32* %a.ptr + br label %inner_loop_begin +; CHECK: loop_begin: +; CHECK-NEXT: %[[A:.*]] = load i32, i32* %a.ptr +; CHECK-NEXT: br label %inner_loop_begin + +inner_loop_begin: + %a.phi = phi i32 [ %a, %loop_begin ], [ %a2, %inner_inner_loop_exit ] + %cond = load i1, i1* %cond.ptr + %b = load i32, i32* %b.ptr + br label %inner_inner_loop_begin +; CHECK: inner_loop_begin: +; CHECK-NEXT: %[[A_INNER_PHI:.*]] = phi i32 [ %[[A]], %loop_begin ], [ %[[A2:.*]], %inner_inner_loop_exit ] +; CHECK-NEXT: %[[COND:.*]] = load i1, i1* %cond.ptr +; CHECK-NEXT: %[[B:.*]] = load i32, i32* %b.ptr +; CHECK-NEXT: br i1 %[[COND]], label %inner_loop_begin.split.us, label %inner_loop_begin.split + +inner_inner_loop_begin: + %v1 = load i1, i1* %ptr + br i1 %v1, label %inner_inner_loop_a, label %inner_inner_loop_b + +inner_inner_loop_a: + %v2 = load i1, i1* %ptr + br i1 %v2, label %inner_inner_loop_latch, label %inner_loop_exit + +inner_inner_loop_b: + br i1 %cond, label %inner_inner_loop_latch, label %inner_inner_loop_exit + +inner_inner_loop_latch: + br label %inner_inner_loop_begin +; The cloned region is now an exit from the inner loop. +; +; CHECK: inner_loop_begin.split.us: +; CHECK-NEXT: %[[A_INNER_INNER_LCSSA:.*]] = phi i32 [ %[[A_INNER_PHI]], %inner_loop_begin ] +; CHECK-NEXT: br label %inner_inner_loop_begin.us +; +; CHECK: inner_inner_loop_begin.us: +; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr +; CHECK-NEXT: br i1 %[[V]], label %inner_inner_loop_a.us, label %inner_inner_loop_b.us +; +; CHECK: inner_inner_loop_b.us: +; CHECK-NEXT: br label %inner_inner_loop_latch.us +; +; CHECK: inner_inner_loop_a.us: +; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr +; CHECK-NEXT: br i1 %[[V]], label %inner_inner_loop_latch.us, label %inner_loop_exit.loopexit.split.us +; +; CHECK: inner_inner_loop_latch.us: +; CHECK-NEXT: br label %inner_inner_loop_begin.us +; +; CHECK: inner_loop_exit.loopexit.split.us: +; CHECK-NEXT: %[[A_INNER_LCSSA_US:.*]] = phi i32 [ %[[A_INNER_INNER_LCSSA]], %inner_inner_loop_a.us ] +; CHECK-NEXT: br label %inner_loop_exit.loopexit +; +; The original region exits the loop earlier. +; +; CHECK: inner_loop_begin.split: +; CHECK-NEXT: br label %inner_inner_loop_begin +; +; CHECK: inner_inner_loop_begin: +; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr +; CHECK-NEXT: br i1 %[[V]], label %inner_inner_loop_a, label %inner_inner_loop_b +; +; CHECK: inner_inner_loop_a: +; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr +; CHECK-NEXT: br i1 %[[V]], label %inner_inner_loop_latch, label %inner_loop_exit.loopexit.split +; +; CHECK: inner_inner_loop_b: +; CHECK-NEXT: br label %inner_inner_loop_exit +; +; CHECK: inner_inner_loop_latch: +; CHECK-NEXT: br label %inner_inner_loop_begin + +inner_inner_loop_exit: + %a2 = load i32, i32* %a.ptr + %v4 = load i1, i1* %ptr + br i1 %v4, label %inner_loop_exit, label %inner_loop_begin +; CHECK: inner_inner_loop_exit: +; CHECK-NEXT: %[[A2]] = load i32, i32* %a.ptr +; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr +; CHECK-NEXT: br i1 %[[V]], label %inner_loop_exit.loopexit1, label %inner_loop_begin + +inner_loop_exit: + %v5 = load i1, i1* %ptr + br i1 %v5, label %loop_exit, label %loop_begin +; CHECK: inner_loop_exit.loopexit.split: +; CHECK-NEXT: %[[A_INNER_LCSSA:.*]] = phi i32 [ %[[A_INNER_PHI]], %inner_inner_loop_a ] +; CHECK-NEXT: br label %inner_loop_exit.loopexit +; +; CHECK: inner_loop_exit.loopexit: +; CHECK-NEXT: %[[A_INNER_US_PHI:.*]] = phi i32 [ %[[A_INNER_LCSSA]], %inner_loop_exit.loopexit.split ], [ %[[A_INNER_LCSSA_US]], %inner_loop_exit.loopexit.split.us ] +; CHECK-NEXT: br label %inner_loop_exit +; +; CHECK: inner_loop_exit.loopexit1: +; CHECK-NEXT: %[[A_INNER_LCSSA2:.*]] = phi i32 [ %[[A_INNER_PHI]], %inner_inner_loop_exit ] +; CHECK-NEXT: br label %inner_loop_exit +; +; CHECK: inner_loop_exit: +; CHECK-NEXT: %[[A_INNER_PHI:.*]] = phi i32 [ %[[A_INNER_LCSSA2]], %inner_loop_exit.loopexit1 ], [ %[[A_INNER_US_PHI]], %inner_loop_exit.loopexit ] +; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr +; CHECK-NEXT: br i1 %[[V]], label %loop_exit, label %loop_begin + +loop_exit: + %a.lcssa = phi i32 [ %a.phi, %inner_loop_exit ] + ret i32 %a.lcssa +; CHECK: loop_exit: +; CHECK-NEXT: %[[A_LCSSA:.*]] = phi i32 [ %[[A_INNER_PHI]], %inner_loop_exit ] +; CHECK-NEXT: ret i32 %[[A_LCSSA]] +} + +; Same pattern as @test8a but where the original loop looses an exit block and +; needs to be hoisted up the nest. +define i32 @test8b(i1* %ptr, i1* %cond.ptr, i32* %a.ptr, i32* %b.ptr) { +; CHECK-LABEL: @test8b( +entry: + br label %loop_begin +; CHECK-NEXT: entry: +; CHECK-NEXT: br label %loop_begin + +loop_begin: + %a = load i32, i32* %a.ptr + br label %inner_loop_begin +; CHECK: loop_begin: +; CHECK-NEXT: %[[A:.*]] = load i32, i32* %a.ptr +; CHECK-NEXT: br label %inner_loop_begin + +inner_loop_begin: + %a.phi = phi i32 [ %a, %loop_begin ], [ %a2, %inner_inner_loop_exit ] + %cond = load i1, i1* %cond.ptr + %b = load i32, i32* %b.ptr + br label %inner_inner_loop_begin +; CHECK: inner_loop_begin: +; CHECK-NEXT: %[[A_INNER_PHI:.*]] = phi i32 [ %[[A]], %loop_begin ], [ %[[A2:.*]], %inner_inner_loop_exit ] +; CHECK-NEXT: %[[COND:.*]] = load i1, i1* %cond.ptr +; CHECK-NEXT: %[[B:.*]] = load i32, i32* %b.ptr +; CHECK-NEXT: br i1 %[[COND]], label %inner_loop_begin.split.us, label %inner_loop_begin.split + +inner_inner_loop_begin: + %v1 = load i1, i1* %ptr + br i1 %v1, label %inner_inner_loop_a, label %inner_inner_loop_b + +inner_inner_loop_a: + %v2 = load i1, i1* %ptr + br i1 %v2, label %inner_inner_loop_latch, label %inner_loop_exit + +inner_inner_loop_b: + br i1 %cond, label %inner_inner_loop_exit, label %inner_inner_loop_latch + +inner_inner_loop_latch: + br label %inner_inner_loop_begin +; The cloned region is similar to before but with one earlier exit. +; +; CHECK: inner_loop_begin.split.us: +; CHECK-NEXT: br label %inner_inner_loop_begin.us +; +; CHECK: inner_inner_loop_begin.us: +; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr +; CHECK-NEXT: br i1 %[[V]], label %inner_inner_loop_a.us, label %inner_inner_loop_b.us +; +; CHECK: inner_inner_loop_b.us: +; CHECK-NEXT: br label %inner_inner_loop_exit.split.us +; +; CHECK: inner_inner_loop_a.us: +; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr +; CHECK-NEXT: br i1 %[[V]], label %inner_inner_loop_latch.us, label %inner_loop_exit.loopexit.split.us +; +; CHECK: inner_inner_loop_latch.us: +; CHECK-NEXT: br label %inner_inner_loop_begin.us +; +; CHECK: inner_inner_loop_exit.split.us: +; CHECK-NEXT: br label %inner_inner_loop_exit +; +; CHECK: inner_loop_exit.loopexit.split.us: +; CHECK-NEXT: %[[A_INNER_LCSSA_US:.*]] = phi i32 [ %[[A_INNER_PHI]], %inner_inner_loop_a.us ] +; CHECK-NEXT: br label %inner_loop_exit.loopexit +; +; The original region is now an exit in the preheader. +; +; CHECK: inner_loop_begin.split: +; CHECK-NEXT: %[[A_INNER_INNER_LCSSA:.*]] = phi i32 [ %[[A_INNER_PHI]], %inner_loop_begin ] +; CHECK-NEXT: br label %inner_inner_loop_begin +; +; CHECK: inner_inner_loop_begin: +; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr +; CHECK-NEXT: br i1 %[[V]], label %inner_inner_loop_a, label %inner_inner_loop_b +; +; CHECK: inner_inner_loop_a: +; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr +; CHECK-NEXT: br i1 %[[V]], label %inner_inner_loop_latch, label %inner_loop_exit.loopexit.split +; +; CHECK: inner_inner_loop_b: +; CHECK-NEXT: br label %inner_inner_loop_latch +; +; CHECK: inner_inner_loop_latch: +; CHECK-NEXT: br label %inner_inner_loop_begin + +inner_inner_loop_exit: + %a2 = load i32, i32* %a.ptr + %v4 = load i1, i1* %ptr + br i1 %v4, label %inner_loop_exit, label %inner_loop_begin +; CHECK: inner_inner_loop_exit: +; CHECK-NEXT: %[[A2]] = load i32, i32* %a.ptr +; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr +; CHECK-NEXT: br i1 %[[V]], label %inner_loop_exit.loopexit1, label %inner_loop_begin + +inner_loop_exit: + %v5 = load i1, i1* %ptr + br i1 %v5, label %loop_exit, label %loop_begin +; CHECK: inner_loop_exit.loopexit.split: +; CHECK-NEXT: %[[A_INNER_LCSSA:.*]] = phi i32 [ %[[A_INNER_INNER_LCSSA]], %inner_inner_loop_a ] +; CHECK-NEXT: br label %inner_loop_exit.loopexit +; +; CHECK: inner_loop_exit.loopexit: +; CHECK-NEXT: %[[A_INNER_US_PHI:.*]] = phi i32 [ %[[A_INNER_LCSSA]], %inner_loop_exit.loopexit.split ], [ %[[A_INNER_LCSSA_US]], %inner_loop_exit.loopexit.split.us ] +; CHECK-NEXT: br label %inner_loop_exit +; +; CHECK: inner_loop_exit.loopexit1: +; CHECK-NEXT: %[[A_INNER_LCSSA2:.*]] = phi i32 [ %[[A_INNER_PHI]], %inner_inner_loop_exit ] +; CHECK-NEXT: br label %inner_loop_exit +; +; CHECK: inner_loop_exit: +; CHECK-NEXT: %[[A_INNER_PHI:.*]] = phi i32 [ %[[A_INNER_LCSSA2]], %inner_loop_exit.loopexit1 ], [ %[[A_INNER_US_PHI]], %inner_loop_exit.loopexit ] +; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr +; CHECK-NEXT: br i1 %[[V]], label %loop_exit, label %loop_begin + +loop_exit: + %a.lcssa = phi i32 [ %a.phi, %inner_loop_exit ] + ret i32 %a.lcssa +; CHECK: loop_exit: +; CHECK-NEXT: %[[A_LCSSA:.*]] = phi i32 [ %[[A_INNER_PHI]], %inner_loop_exit ] +; CHECK-NEXT: ret i32 %[[A_LCSSA]] +} + +; Test for when unswitching produces a clone of an inner loop but +; the clone no longer has an exiting edge *at all* and loops infinitely. +; Because it doesn't ever exit to the outer loop it is no longer an inner loop +; but needs to be hoisted up the nest to be a top-level loop. +define i32 @test9a(i1* %ptr, i1* %cond.ptr, i32* %a.ptr, i32* %b.ptr) { +; CHECK-LABEL: @test9a( +entry: + br label %loop_begin +; CHECK-NEXT: entry: +; CHECK-NEXT: br label %loop_begin + +loop_begin: + %b = load i32, i32* %b.ptr + %cond = load i1, i1* %cond.ptr + br label %inner_loop_begin +; CHECK: loop_begin: +; CHECK-NEXT: %[[B:.*]] = load i32, i32* %b.ptr +; CHECK-NEXT: %[[COND:.*]] = load i1, i1* %cond.ptr +; CHECK-NEXT: br i1 %[[COND]], label %loop_begin.split.us, label %loop_begin.split + +inner_loop_begin: + %a = load i32, i32* %a.ptr + br i1 %cond, label %inner_loop_latch, label %inner_loop_exit + +inner_loop_latch: + call void @sink1(i32 %b) + br label %inner_loop_begin +; The cloned inner loop ends up as an infinite loop and thus being a top-level +; loop with the preheader as an exit block of the outer loop. +; +; CHECK: loop_begin.split.us +; CHECK-NEXT: %[[B_LCSSA:.*]] = phi i32 [ %[[B]], %loop_begin ] +; CHECK-NEXT: br label %inner_loop_begin.us +; +; CHECK: inner_loop_begin.us: +; CHECK-NEXT: %[[A:.*]] = load i32, i32* %a.ptr +; CHECK-NEXT: br label %inner_loop_latch.us +; +; CHECK: inner_loop_latch.us: +; CHECK-NEXT: call void @sink1(i32 %[[B_LCSSA]]) +; CHECK-NEXT: br label %inner_loop_begin.us +; +; The original loop becomes boring non-loop code. +; +; CHECK: loop_begin.split +; CHECK-NEXT: br label %inner_loop_begin +; +; CHECK: inner_loop_begin: +; CHECK-NEXT: %[[A:.*]] = load i32, i32* %a.ptr +; CHECK-NEXT: br label %inner_loop_exit + +inner_loop_exit: + %a.inner_lcssa = phi i32 [ %a, %inner_loop_begin ] + %v = load i1, i1* %ptr + br i1 %v, label %loop_begin, label %loop_exit +; CHECK: inner_loop_exit: +; CHECK-NEXT: %[[A_INNER_LCSSA:.*]] = phi i32 [ %[[A]], %inner_loop_begin ] +; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr +; CHECK-NEXT: br i1 %[[V]], label %loop_begin, label %loop_exit + +loop_exit: + %a.lcssa = phi i32 [ %a.inner_lcssa, %inner_loop_exit ] + ret i32 %a.lcssa +; CHECK: loop_exit: +; CHECK-NEXT: %[[A_LCSSA:.*]] = phi i32 [ %[[A_INNER_LCSSA]], %inner_loop_exit ] +; CHECK-NEXT: ret i32 %[[A_LCSSA]] +} + +; The same core pattern as @test9a, but instead of the cloned loop becoming an +; infinite loop, the original loop has its only exit unswitched and the +; original loop becomes infinite and must be hoisted out of the loop nest. +define i32 @test9b(i1* %ptr, i1* %cond.ptr, i32* %a.ptr, i32* %b.ptr) { +; CHECK-LABEL: @test9b( +entry: + br label %loop_begin +; CHECK-NEXT: entry: +; CHECK-NEXT: br label %loop_begin + +loop_begin: + %b = load i32, i32* %b.ptr + %cond = load i1, i1* %cond.ptr + br label %inner_loop_begin +; CHECK: loop_begin: +; CHECK-NEXT: %[[B:.*]] = load i32, i32* %b.ptr +; CHECK-NEXT: %[[COND:.*]] = load i1, i1* %cond.ptr +; CHECK-NEXT: br i1 %[[COND]], label %loop_begin.split.us, label %loop_begin.split + +inner_loop_begin: + %a = load i32, i32* %a.ptr + br i1 %cond, label %inner_loop_exit, label %inner_loop_latch + +inner_loop_latch: + call void @sink1(i32 %b) + br label %inner_loop_begin +; The cloned inner loop becomes a boring non-loop. +; +; CHECK: loop_begin.split.us +; CHECK-NEXT: br label %inner_loop_begin.us +; +; CHECK: inner_loop_begin.us: +; CHECK-NEXT: %[[A:.*]] = load i32, i32* %a.ptr +; CHECK-NEXT: br label %inner_loop_exit.split.us +; +; CHECK: inner_loop_exit.split.us +; CHECK-NEXT: %[[A_INNER_LCSSA_US:.*]] = phi i32 [ %[[A]], %inner_loop_begin.us ] +; CHECK-NEXT: br label %inner_loop_exit +; +; The original loop becomes an infinite loop and thus a top-level loop with the +; preheader as an exit block for the outer loop. +; +; CHECK: loop_begin.split +; CHECK-NEXT: %[[B_LCSSA:.*]] = phi i32 [ %[[B]], %loop_begin ] +; CHECK-NEXT: br label %inner_loop_begin +; +; CHECK: inner_loop_begin: +; CHECK-NEXT: %[[A:.*]] = load i32, i32* %a.ptr +; CHECK-NEXT: br label %inner_loop_latch +; +; CHECK: inner_loop_latch: +; CHECK-NEXT: call void @sink1(i32 %[[B_LCSSA]]) +; CHECK-NEXT: br label %inner_loop_begin + +inner_loop_exit: + %a.inner_lcssa = phi i32 [ %a, %inner_loop_begin ] + %v = load i1, i1* %ptr + br i1 %v, label %loop_begin, label %loop_exit +; CHECK: inner_loop_exit: +; CHECK-NEXT: %[[A_INNER_LCSSA:.*]] = phi i32 [ %[[A_INNER_LCSSA_US]], %inner_loop_exit.split.us ] +; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr +; CHECK-NEXT: br i1 %[[V]], label %loop_begin, label %loop_exit + +loop_exit: + %a.lcssa = phi i32 [ %a.inner_lcssa, %inner_loop_exit ] + ret i32 %a.lcssa +; CHECK: loop_exit: +; CHECK-NEXT: %[[A_LCSSA:.*]] = phi i32 [ %[[A_INNER_LCSSA]], %inner_loop_exit ] +; CHECK-NEXT: ret i32 %[[A_LCSSA]] +} + +; Test that requires re-forming dedicated exits for the cloned loop. +define i32 @test10a(i1* %ptr, i1 %cond, i32* %a.ptr) { +; CHECK-LABEL: @test10a( +entry: + br label %loop_begin +; CHECK-NEXT: entry: +; CHECK-NEXT: br i1 %cond, label %entry.split.us, label %entry.split + +loop_begin: + %a = load i32, i32* %a.ptr + %v1 = load i1, i1* %ptr + br i1 %v1, label %loop_a, label %loop_b + +loop_a: + %v2 = load i1, i1* %ptr + br i1 %v2, label %loop_exit, label %loop_begin + +loop_b: + br i1 %cond, label %loop_exit, label %loop_begin +; The cloned loop with one edge as a direct exit. +; +; CHECK: entry.split.us: +; CHECK-NEXT: br label %loop_begin.us +; +; CHECK: loop_begin.us: +; CHECK-NEXT: %[[A:.*]] = load i32, i32* %a.ptr +; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr +; CHECK-NEXT: br i1 %[[V]], label %loop_a.us, label %loop_b.us +; +; CHECK: loop_b.us: +; CHECK-NEXT: %[[A_LCSSA_B:.*]] = phi i32 [ %[[A]], %loop_begin.us ] +; CHECK-NEXT: br label %loop_exit.split.us +; +; CHECK: loop_a.us: +; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr +; CHECK-NEXT: br i1 %[[V]], label %loop_exit.split.us.loopexit, label %loop_begin.backedge.us +; +; CHECK: loop_begin.backedge.us: +; CHECK-NEXT: br label %loop_begin.us +; +; CHECK: loop_exit.split.us.loopexit: +; CHECK-NEXT: %[[A_LCSSA_A:.*]] = phi i32 [ %[[A]], %loop_a.us ] +; CHECK-NEXT: br label %loop_exit +; +; CHECK: loop_exit.split.us: +; CHECK-NEXT: %[[A_PHI_US:.*]] = phi i32 [ %[[A_LCSSA_B]], %loop_b.us ], [ %[[A_LCSSA_A]], %loop_exit.split.us.loopexit ] +; CHECK-NEXT: br label %loop_exit + +; The original loop without one 'loop_exit' edge. +; +; CHECK: entry.split: +; CHECK-NEXT: br label %loop_begin +; +; CHECK: loop_begin: +; CHECK-NEXT: %[[A:.*]] = load i32, i32* %a.ptr +; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr +; CHECK-NEXT: br i1 %[[V]], label %loop_a, label %loop_b +; +; CHECK: loop_a: +; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr +; CHECK-NEXT: br i1 %[[V]], label %loop_exit.split, label %loop_begin.backedge +; +; CHECK: loop_begin.backedge: +; CHECK-NEXT: br label %loop_begin +; +; CHECK: loop_b: +; CHECK-NEXT: br label %loop_begin.backedge +; +; CHECK: loop_exit.split: +; CHECK-NEXT: %[[A_LCSSA:.*]] = phi i32 [ %[[A]], %loop_a ] +; CHECK-NEXT: br label %loop_exit + +loop_exit: + %a.lcssa = phi i32 [ %a, %loop_a ], [ %a, %loop_b ] + ret i32 %a.lcssa +; CHECK: loop_exit: +; CHECK-NEXT: %[[A_PHI:.*]] = phi i32 [ %[[A_LCSSA]], %loop_exit.split ], [ %[[A_PHI_US]], %loop_exit.split.us ] +; CHECK-NEXT: ret i32 %[[AB_PHI]] +} + +; Test that requires re-forming dedicated exits for the original loop. +define i32 @test10b(i1* %ptr, i1 %cond, i32* %a.ptr) { +; CHECK-LABEL: @test10b( +entry: + br label %loop_begin +; CHECK-NEXT: entry: +; CHECK-NEXT: br i1 %cond, label %entry.split.us, label %entry.split + +loop_begin: + %a = load i32, i32* %a.ptr + %v1 = load i1, i1* %ptr + br i1 %v1, label %loop_a, label %loop_b + +loop_a: + %v2 = load i1, i1* %ptr + br i1 %v2, label %loop_begin, label %loop_exit + +loop_b: + br i1 %cond, label %loop_begin, label %loop_exit +; The cloned loop without one of the exits. +; +; CHECK: entry.split.us: +; CHECK-NEXT: br label %loop_begin.us +; +; CHECK: loop_begin.us: +; CHECK-NEXT: %[[A:.*]] = load i32, i32* %a.ptr +; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr +; CHECK-NEXT: br i1 %[[V]], label %loop_a.us, label %loop_b.us +; +; CHECK: loop_b.us: +; CHECK-NEXT: br label %loop_begin.backedge.us +; +; CHECK: loop_a.us: +; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr +; CHECK-NEXT: br i1 %[[V]], label %loop_begin.backedge.us, label %loop_exit.split.us +; +; CHECK: loop_begin.backedge.us: +; CHECK-NEXT: br label %loop_begin.us +; +; CHECK: loop_exit.split.us: +; CHECK-NEXT: %[[A_LCSSA_US:.*]] = phi i32 [ %[[A]], %loop_a.us ] +; CHECK-NEXT: br label %loop_exit + +; The original loop without one 'loop_exit' edge. +; +; CHECK: entry.split: +; CHECK-NEXT: br label %loop_begin +; +; CHECK: loop_begin: +; CHECK-NEXT: %[[A:.*]] = load i32, i32* %a.ptr +; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr +; CHECK-NEXT: br i1 %[[V]], label %loop_a, label %loop_b +; +; CHECK: loop_a: +; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr +; CHECK-NEXT: br i1 %[[V]], label %loop_begin.backedge, label %loop_exit.split.loopexit +; +; CHECK: loop_begin.backedge: +; CHECK-NEXT: br label %loop_begin +; +; CHECK: loop_b: +; CHECK-NEXT: %[[A_LCSSA_B:.*]] = phi i32 [ %[[A]], %loop_begin ] +; CHECK-NEXT: br label %loop_exit.split +; +; CHECK: loop_exit.split.loopexit: +; CHECK-NEXT: %[[A_LCSSA_A:.*]] = phi i32 [ %[[A]], %loop_a ] +; CHECK-NEXT: br label %loop_exit.split +; +; CHECK: loop_exit.split: +; CHECK-NEXT: %[[A_PHI_SPLIT:.*]] = phi i32 [ %[[A_LCSSA_B]], %loop_b ], [ %[[A_LCSSA_A]], %loop_exit.split.loopexit ] +; CHECK-NEXT: br label %loop_exit + +loop_exit: + %a.lcssa = phi i32 [ %a, %loop_a ], [ %a, %loop_b ] + ret i32 %a.lcssa +; CHECK: loop_exit: +; CHECK-NEXT: %[[A_PHI:.*]] = phi i32 [ %[[A_PHI_SPLIT]], %loop_exit.split ], [ %[[A_LCSSA_US]], %loop_exit.split.us ] +; CHECK-NEXT: ret i32 %[[AB_PHI]] +} + +; Check that if a cloned inner loop after unswitching doesn't loop and directly +; exits even an outer loop, we don't add the cloned preheader to the outer +; loop and do add the needed LCSSA phi nodes for the new exit block from the +; outer loop. +define i32 @test11a(i1* %ptr, i1* %cond.ptr, i32* %a.ptr, i32* %b.ptr) { +; CHECK-LABEL: @test11a( +entry: + br label %loop_begin +; CHECK-NEXT: entry: +; CHECK-NEXT: br label %loop_begin + +loop_begin: + %b = load i32, i32* %b.ptr + %v1 = load i1, i1* %ptr + br i1 %v1, label %loop_latch, label %inner_loop_ph +; CHECK: loop_begin: +; CHECK-NEXT: %[[B:.*]] = load i32, i32* %b.ptr +; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr +; CHECK-NEXT: br i1 %[[V]], label %loop_latch, label %inner_loop_ph + +inner_loop_ph: + %cond = load i1, i1* %cond.ptr + br label %inner_loop_begin +; CHECK: inner_loop_ph: +; CHECK-NEXT: %[[COND:.*]] = load i1, i1* %cond.ptr +; CHECK-NEXT: br i1 %[[COND]], label %inner_loop_ph.split.us, label %inner_loop_ph.split + +inner_loop_begin: + call void @sink1(i32 %b) + %a = load i32, i32* %a.ptr + br i1 %cond, label %loop_exit, label %inner_loop_a + +inner_loop_a: + %v2 = load i1, i1* %ptr + br i1 %v2, label %inner_loop_exit, label %inner_loop_begin +; The cloned path doesn't actually loop and is an exit from the outer loop as +; well. +; +; CHECK: inner_loop_ph.split.us: +; CHECK-NEXT: %[[B_LCSSA:.*]] = phi i32 [ %[[B]], %inner_loop_ph ] +; CHECK-NEXT: br label %inner_loop_begin.us +; +; CHECK: inner_loop_begin.us: +; CHECK-NEXT: call void @sink1(i32 %[[B_LCSSA]]) +; CHECK-NEXT: %[[A:.*]] = load i32, i32* %a.ptr +; CHECK-NEXT: br label %loop_exit.loopexit.split.us +; +; CHECK: loop_exit.loopexit.split.us: +; CHECK-NEXT: %[[A_INNER_LCSSA_US:.*]] = phi i32 [ %[[A]], %inner_loop_begin.us ] +; CHECK-NEXT: br label %loop_exit.loopexit +; +; The original remains a loop losing the exit edge. +; +; CHECK: inner_loop_ph.split: +; CHECK-NEXT: br label %inner_loop_begin +; +; CHECK: inner_loop_begin: +; CHECK-NEXT: call void @sink1(i32 %[[B]]) +; CHECK-NEXT: %[[A:.*]] = load i32, i32* %a.ptr +; CHECK-NEXT: br label %inner_loop_a +; +; CHECK: inner_loop_a: +; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr +; CHECK-NEXT: br i1 %[[V]], label %inner_loop_exit, label %inner_loop_begin + +inner_loop_exit: + %a.inner_lcssa = phi i32 [ %a, %inner_loop_a ] + %v3 = load i1, i1* %ptr + br i1 %v3, label %loop_latch, label %loop_exit +; CHECK: inner_loop_exit: +; CHECK-NEXT: %[[A_INNER_LCSSA:.*]] = phi i32 [ %[[A]], %inner_loop_a ] +; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr +; CHECK-NEXT: br i1 %[[V]], label %loop_latch, label %loop_exit.loopexit1 + +loop_latch: + br label %loop_begin +; CHECK: loop_latch: +; CHECK-NEXT: br label %loop_begin + +loop_exit: + %a.lcssa = phi i32 [ %a, %inner_loop_begin ], [ %a.inner_lcssa, %inner_loop_exit ] + ret i32 %a.lcssa +; CHECK: loop_exit.loopexit: +; CHECK-NEXT: %[[A_LCSSA_US:.*]] = phi i32 [ %[[A_INNER_LCSSA_US]], %loop_exit.loopexit.split.us ] +; CHECK-NEXT: br label %loop_exit +; +; CHECK: loop_exit.loopexit1: +; CHECK-NEXT: %[[A_LCSSA:.*]] = phi i32 [ %[[A_INNER_LCSSA]], %inner_loop_exit ] +; CHECK-NEXT: br label %loop_exit +; +; CHECK: loop_exit: +; CHECK-NEXT: %[[A_PHI:.*]] = phi i32 [ %[[A_LCSSA_US]], %loop_exit.loopexit ], [ %[[A_LCSSA]], %loop_exit.loopexit1 ] +; CHECK-NEXT: ret i32 %[[A_PHI]] +} + +; Check that if the original inner loop after unswitching doesn't loop and +; directly exits even an outer loop, we remove the original preheader from the +; outer loop and add needed LCSSA phi nodes for the new exit block from the +; outer loop. +define i32 @test11b(i1* %ptr, i1* %cond.ptr, i32* %a.ptr, i32* %b.ptr) { +; CHECK-LABEL: @test11b( +entry: + br label %loop_begin +; CHECK-NEXT: entry: +; CHECK-NEXT: br label %loop_begin + +loop_begin: + %b = load i32, i32* %b.ptr + %v1 = load i1, i1* %ptr + br i1 %v1, label %loop_latch, label %inner_loop_ph +; CHECK: loop_begin: +; CHECK-NEXT: %[[B:.*]] = load i32, i32* %b.ptr +; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr +; CHECK-NEXT: br i1 %[[V]], label %loop_latch, label %inner_loop_ph + +inner_loop_ph: + %cond = load i1, i1* %cond.ptr + br label %inner_loop_begin +; CHECK: inner_loop_ph: +; CHECK-NEXT: %[[COND:.*]] = load i1, i1* %cond.ptr +; CHECK-NEXT: br i1 %[[COND]], label %inner_loop_ph.split.us, label %inner_loop_ph.split + +inner_loop_begin: + call void @sink1(i32 %b) + %a = load i32, i32* %a.ptr + br i1 %cond, label %inner_loop_a, label %loop_exit + +inner_loop_a: + %v2 = load i1, i1* %ptr + br i1 %v2, label %inner_loop_exit, label %inner_loop_begin +; The cloned path continues to loop without the exit out of the entire nest. +; +; CHECK: inner_loop_ph.split.us: +; CHECK-NEXT: br label %inner_loop_begin.us +; +; CHECK: inner_loop_begin.us: +; CHECK-NEXT: call void @sink1(i32 %[[B]]) +; CHECK-NEXT: %[[A:.*]] = load i32, i32* %a.ptr +; CHECK-NEXT: br label %inner_loop_a.us +; +; CHECK: inner_loop_a.us: +; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr +; CHECK-NEXT: br i1 %[[V]], label %inner_loop_exit.split.us, label %inner_loop_begin.us +; +; CHECK: inner_loop_exit.split.us: +; CHECK-NEXT: %[[A_INNER_LCSSA_US:.*]] = phi i32 [ %[[A]], %inner_loop_a.us ] +; CHECK-NEXT: br label %inner_loop_exit +; +; The original remains a loop losing the exit edge. +; +; CHECK: inner_loop_ph.split: +; CHECK-NEXT: %[[B_LCSSA:.*]] = phi i32 [ %[[B]], %inner_loop_ph ] +; CHECK-NEXT: br label %inner_loop_begin +; +; CHECK: inner_loop_begin: +; CHECK-NEXT: call void @sink1(i32 %[[B_LCSSA]]) +; CHECK-NEXT: %[[A:.*]] = load i32, i32* %a.ptr +; CHECK-NEXT: br label %loop_exit.loopexit + +inner_loop_exit: + %a.inner_lcssa = phi i32 [ %a, %inner_loop_a ] + %v3 = load i1, i1* %ptr + br i1 %v3, label %loop_latch, label %loop_exit +; CHECK: inner_loop_exit: +; CHECK-NEXT: %[[A_INNER_PHI:.*]] = phi i32 [ %[[A_INNER_LCSSA_US]], %inner_loop_exit.split.us ] +; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr +; CHECK-NEXT: br i1 %[[V]], label %loop_latch, label %loop_exit.loopexit1 + +loop_latch: + br label %loop_begin +; CHECK: loop_latch: +; CHECK-NEXT: br label %loop_begin + +loop_exit: + %a.lcssa = phi i32 [ %a, %inner_loop_begin ], [ %a.inner_lcssa, %inner_loop_exit ] + ret i32 %a.lcssa +; CHECK: loop_exit.loopexit: +; CHECK-NEXT: %[[A_LCSSA:.*]] = phi i32 [ %[[A]], %inner_loop_begin ] +; CHECK-NEXT: br label %loop_exit +; +; CHECK: loop_exit.loopexit1: +; CHECK-NEXT: %[[A_LCSSA_US:.*]] = phi i32 [ %[[A_INNER_PHI]], %inner_loop_exit ] +; CHECK-NEXT: br label %loop_exit +; +; CHECK: loop_exit: +; CHECK-NEXT: %[[A_PHI:.*]] = phi i32 [ %[[A_LCSSA]], %loop_exit.loopexit ], [ %[[A_LCSSA_US]], %loop_exit.loopexit1 ] +; CHECK-NEXT: ret i32 %[[A_PHI]] +} + +; Like test11a, but checking that when the whole thing is wrapped in yet +; another loop, we correctly attribute the cloned preheader to that outermost +; loop rather than only handling the case where the preheader is not in any loop +; at all. +define i32 @test12a(i1* %ptr, i1* %cond.ptr, i32* %a.ptr, i32* %b.ptr) { +; CHECK-LABEL: @test12a( +entry: + br label %loop_begin +; CHECK-NEXT: entry: +; CHECK-NEXT: br label %loop_begin + +loop_begin: + br label %inner_loop_begin +; CHECK: loop_begin: +; CHECK-NEXT: br label %inner_loop_begin + +inner_loop_begin: + %b = load i32, i32* %b.ptr + %v1 = load i1, i1* %ptr + br i1 %v1, label %inner_loop_latch, label %inner_inner_loop_ph +; CHECK: inner_loop_begin: +; CHECK-NEXT: %[[B:.*]] = load i32, i32* %b.ptr +; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr +; CHECK-NEXT: br i1 %[[V]], label %inner_loop_latch, label %inner_inner_loop_ph + +inner_inner_loop_ph: + %cond = load i1, i1* %cond.ptr + br label %inner_inner_loop_begin +; CHECK: inner_inner_loop_ph: +; CHECK-NEXT: %[[COND:.*]] = load i1, i1* %cond.ptr +; CHECK-NEXT: br i1 %[[COND]], label %inner_inner_loop_ph.split.us, label %inner_inner_loop_ph.split + +inner_inner_loop_begin: + call void @sink1(i32 %b) + %a = load i32, i32* %a.ptr + br i1 %cond, label %inner_loop_exit, label %inner_inner_loop_a + +inner_inner_loop_a: + %v2 = load i1, i1* %ptr + br i1 %v2, label %inner_inner_loop_exit, label %inner_inner_loop_begin +; The cloned path doesn't actually loop and is an exit from the outer loop as +; well. +; +; CHECK: inner_inner_loop_ph.split.us: +; CHECK-NEXT: %[[B_LCSSA:.*]] = phi i32 [ %[[B]], %inner_inner_loop_ph ] +; CHECK-NEXT: br label %inner_inner_loop_begin.us +; +; CHECK: inner_inner_loop_begin.us: +; CHECK-NEXT: call void @sink1(i32 %[[B_LCSSA]]) +; CHECK-NEXT: %[[A:.*]] = load i32, i32* %a.ptr +; CHECK-NEXT: br label %inner_loop_exit.loopexit.split.us +; +; CHECK: inner_loop_exit.loopexit.split.us: +; CHECK-NEXT: %[[A_INNER_INNER_LCSSA_US:.*]] = phi i32 [ %[[A]], %inner_inner_loop_begin.us ] +; CHECK-NEXT: br label %inner_loop_exit.loopexit +; +; The original remains a loop losing the exit edge. +; +; CHECK: inner_inner_loop_ph.split: +; CHECK-NEXT: br label %inner_inner_loop_begin +; +; CHECK: inner_inner_loop_begin: +; CHECK-NEXT: call void @sink1(i32 %[[B]]) +; CHECK-NEXT: %[[A:.*]] = load i32, i32* %a.ptr +; CHECK-NEXT: br label %inner_inner_loop_a +; +; CHECK: inner_inner_loop_a: +; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr +; CHECK-NEXT: br i1 %[[V]], label %inner_inner_loop_exit, label %inner_inner_loop_begin + +inner_inner_loop_exit: + %a.inner_inner_lcssa = phi i32 [ %a, %inner_inner_loop_a ] + %v3 = load i1, i1* %ptr + br i1 %v3, label %inner_loop_latch, label %inner_loop_exit +; CHECK: inner_inner_loop_exit: +; CHECK-NEXT: %[[A_INNER_INNER_LCSSA:.*]] = phi i32 [ %[[A]], %inner_inner_loop_a ] +; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr +; CHECK-NEXT: br i1 %[[V]], label %inner_loop_latch, label %inner_loop_exit.loopexit1 + +inner_loop_latch: + br label %inner_loop_begin +; CHECK: inner_loop_latch: +; CHECK-NEXT: br label %inner_loop_begin + +inner_loop_exit: + %a.inner_lcssa = phi i32 [ %a, %inner_inner_loop_begin ], [ %a.inner_inner_lcssa, %inner_inner_loop_exit ] + %v4 = load i1, i1* %ptr + br i1 %v4, label %loop_begin, label %loop_exit +; CHECK: inner_loop_exit.loopexit: +; CHECK-NEXT: %[[A_INNER_LCSSA_US:.*]] = phi i32 [ %[[A_INNER_INNER_LCSSA_US]], %inner_loop_exit.loopexit.split.us ] +; CHECK-NEXT: br label %inner_loop_exit +; +; CHECK: inner_loop_exit.loopexit1: +; CHECK-NEXT: %[[A_INNER_LCSSA:.*]] = phi i32 [ %[[A_INNER_INNER_LCSSA]], %inner_inner_loop_exit ] +; CHECK-NEXT: br label %inner_loop_exit +; +; CHECK: inner_loop_exit: +; CHECK-NEXT: %[[A_INNER_PHI:.*]] = phi i32 [ %[[A_INNER_LCSSA_US]], %inner_loop_exit.loopexit ], [ %[[A_INNER_LCSSA]], %inner_loop_exit.loopexit1 ] +; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr +; CHECK-NEXT: br i1 %[[V]], label %loop_begin, label %loop_exit + +loop_exit: + %a.lcssa = phi i32 [ %a.inner_lcssa, %inner_loop_exit ] + ret i32 %a.lcssa +; CHECK: loop_exit: +; CHECK-NEXT: %[[A_LCSSA:.*]] = phi i32 [ %[[A_INNER_PHI]], %inner_loop_exit ] +; CHECK-NEXT: ret i32 %[[A_LCSSA]] +} + +; Like test11b, but checking that when the whole thing is wrapped in yet +; another loop, we correctly sink the preheader to the outermost loop rather +; than only handling the case where the preheader is completely removed from +; a loop. +define i32 @test12b(i1* %ptr, i1* %cond.ptr, i32* %a.ptr, i32* %b.ptr) { +; CHECK-LABEL: @test12b( +entry: + br label %loop_begin +; CHECK-NEXT: entry: +; CHECK-NEXT: br label %loop_begin + +loop_begin: + br label %inner_loop_begin +; CHECK: loop_begin: +; CHECK-NEXT: br label %inner_loop_begin + +inner_loop_begin: + %b = load i32, i32* %b.ptr + %v1 = load i1, i1* %ptr + br i1 %v1, label %inner_loop_latch, label %inner_inner_loop_ph +; CHECK: inner_loop_begin: +; CHECK-NEXT: %[[B:.*]] = load i32, i32* %b.ptr +; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr +; CHECK-NEXT: br i1 %[[V]], label %inner_loop_latch, label %inner_inner_loop_ph + +inner_inner_loop_ph: + %cond = load i1, i1* %cond.ptr + br label %inner_inner_loop_begin +; CHECK: inner_inner_loop_ph: +; CHECK-NEXT: %[[COND:.*]] = load i1, i1* %cond.ptr +; CHECK-NEXT: br i1 %[[COND]], label %inner_inner_loop_ph.split.us, label %inner_inner_loop_ph.split + +inner_inner_loop_begin: + call void @sink1(i32 %b) + %a = load i32, i32* %a.ptr + br i1 %cond, label %inner_inner_loop_a, label %inner_loop_exit + +inner_inner_loop_a: + %v2 = load i1, i1* %ptr + br i1 %v2, label %inner_inner_loop_exit, label %inner_inner_loop_begin +; The cloned path continues to loop without the exit out of the entire nest. +; +; CHECK: inner_inner_loop_ph.split.us: +; CHECK-NEXT: br label %inner_inner_loop_begin.us +; +; CHECK: inner_inner_loop_begin.us: +; CHECK-NEXT: call void @sink1(i32 %[[B]]) +; CHECK-NEXT: %[[A:.*]] = load i32, i32* %a.ptr +; CHECK-NEXT: br label %inner_inner_loop_a.us +; +; CHECK: inner_inner_loop_a.us: +; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr +; CHECK-NEXT: br i1 %[[V]], label %inner_inner_loop_exit.split.us, label %inner_inner_loop_begin.us +; +; CHECK: inner_inner_loop_exit.split.us: +; CHECK-NEXT: %[[A_INNER_INNER_LCSSA_US:.*]] = phi i32 [ %[[A]], %inner_inner_loop_a.us ] +; CHECK-NEXT: br label %inner_inner_loop_exit +; +; The original remains a loop losing the exit edge. +; +; CHECK: inner_inner_loop_ph.split: +; CHECK-NEXT: %[[B_LCSSA:.*]] = phi i32 [ %[[B]], %inner_inner_loop_ph ] +; CHECK-NEXT: br label %inner_inner_loop_begin +; +; CHECK: inner_inner_loop_begin: +; CHECK-NEXT: call void @sink1(i32 %[[B_LCSSA]]) +; CHECK-NEXT: %[[A:.*]] = load i32, i32* %a.ptr +; CHECK-NEXT: br label %inner_loop_exit.loopexit + +inner_inner_loop_exit: + %a.inner_inner_lcssa = phi i32 [ %a, %inner_inner_loop_a ] + %v3 = load i1, i1* %ptr + br i1 %v3, label %inner_loop_latch, label %inner_loop_exit +; CHECK: inner_inner_loop_exit: +; CHECK-NEXT: %[[A_INNER_INNER_PHI:.*]] = phi i32 [ %[[A_INNER_INNER_LCSSA_US]], %inner_inner_loop_exit.split.us ] +; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr +; CHECK-NEXT: br i1 %[[V]], label %inner_loop_latch, label %inner_loop_exit.loopexit1 + +inner_loop_latch: + br label %inner_loop_begin +; CHECK: inner_loop_latch: +; CHECK-NEXT: br label %inner_loop_begin + +inner_loop_exit: + %a.inner_lcssa = phi i32 [ %a, %inner_inner_loop_begin ], [ %a.inner_inner_lcssa, %inner_inner_loop_exit ] + %v4 = load i1, i1* %ptr + br i1 %v4, label %loop_begin, label %loop_exit +; CHECK: inner_loop_exit.loopexit: +; CHECK-NEXT: %[[A_INNER_LCSSA:.*]] = phi i32 [ %[[A]], %inner_inner_loop_begin ] +; CHECK-NEXT: br label %inner_loop_exit +; +; CHECK: inner_loop_exit.loopexit1: +; CHECK-NEXT: %[[A_INNER_LCSSA_US:.*]] = phi i32 [ %[[A_INNER_INNER_PHI]], %inner_inner_loop_exit ] +; CHECK-NEXT: br label %inner_loop_exit +; +; CHECK: inner_loop_exit: +; CHECK-NEXT: %[[A_INNER_PHI:.*]] = phi i32 [ %[[A_INNER_LCSSA]], %inner_loop_exit.loopexit ], [ %[[A_INNER_LCSSA_US]], %inner_loop_exit.loopexit1 ] +; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr +; CHECK-NEXT: br i1 %[[V]], label %loop_begin, label %loop_exit + +loop_exit: + %a.lcssa = phi i32 [ %a.inner_lcssa, %inner_loop_exit ] + ret i32 %a.lcssa +; CHECK: loop_exit: +; CHECK-NEXT: %[[A_LCSSA:.*]] = phi i32 [ %[[A_INNER_PHI]], %inner_loop_exit ] +; CHECK-NEXT: ret i32 %[[A_LCSSA]] +} + +; Test where the cloned loop has an inner loop that has to be traversed to form +; the cloned loop, and where this inner loop has multiple blocks, and where the +; exiting block that connects the inner loop to the cloned loop is not the header +; block. This ensures that we correctly handle interesting corner cases of +; traversing back to the header when establishing the cloned loop. +define i32 @test13a(i1* %ptr, i1 %cond, i32* %a.ptr, i32* %b.ptr) { +; CHECK-LABEL: @test13a( +entry: + br label %loop_begin +; CHECK-NEXT: entry: +; CHECK-NEXT: br i1 %cond, label %entry.split.us, label %entry.split + +loop_begin: + %a = load i32, i32* %a.ptr + %v1 = load i1, i1* %ptr + br i1 %v1, label %loop_a, label %loop_b + +loop_a: + %v2 = load i1, i1* %ptr + br i1 %v2, label %loop_exit, label %loop_latch + +loop_b: + %b = load i32, i32* %b.ptr + br i1 %cond, label %loop_b_inner_ph, label %loop_exit + +loop_b_inner_ph: + br label %loop_b_inner_header + +loop_b_inner_header: + %v3 = load i1, i1* %ptr + br i1 %v3, label %loop_b_inner_latch, label %loop_b_inner_body + +loop_b_inner_body: + %v4 = load i1, i1* %ptr + br i1 %v4, label %loop_b_inner_latch, label %loop_b_inner_exit + +loop_b_inner_latch: + br label %loop_b_inner_header + +loop_b_inner_exit: + br label %loop_latch + +loop_latch: + br label %loop_begin +; The cloned loop contains an inner loop within it. +; +; CHECK: entry.split.us: +; CHECK-NEXT: br label %loop_begin.us +; +; CHECK: loop_begin.us: +; CHECK-NEXT: %[[A:.*]] = load i32, i32* %a.ptr +; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr +; CHECK-NEXT: br i1 %[[V]], label %loop_a.us, label %loop_b.us +; +; CHECK: loop_b.us: +; CHECK-NEXT: %[[B:.*]] = load i32, i32* %b.ptr +; CHECK-NEXT: br label %loop_b_inner_ph.us +; +; CHECK: loop_b_inner_ph.us: +; CHECK-NEXT: br label %loop_b_inner_header.us +; +; CHECK: loop_b_inner_header.us: +; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr +; CHECK-NEXT: br i1 %[[V]], label %loop_b_inner_latch.us, label %loop_b_inner_body.us +; +; CHECK: loop_b_inner_body.us: +; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr +; CHECK-NEXT: br i1 %[[V]], label %loop_b_inner_latch.us, label %loop_b_inner_exit.us +; +; CHECK: loop_b_inner_exit.us: +; CHECK-NEXT: br label %loop_latch.us +; +; CHECK: loop_b_inner_latch.us: +; CHECK-NEXT: br label %loop_b_inner_header.us +; +; CHECK: loop_a.us: +; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr +; CHECK-NEXT: br i1 %[[V]], label %loop_exit.split.us, label %loop_latch.us +; +; CHECK: loop_latch.us: +; CHECK-NEXT: br label %loop_begin.us +; +; CHECK: loop_exit.split.us: +; CHECK-NEXT: %[[A_LCSSA_US:.*]] = phi i32 [ %[[A]], %loop_a.us ] +; CHECK-NEXT: br label %loop_exit +; +; And the original loop no longer contains an inner loop. +; +; CHECK: entry.split: +; CHECK-NEXT: br label %loop_begin +; +; CHECK: loop_begin: +; CHECK-NEXT: %[[A:.*]] = load i32, i32* %a.ptr +; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr +; CHECK-NEXT: br i1 %[[V]], label %loop_a, label %loop_b +; +; CHECK: loop_a: +; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr +; CHECK-NEXT: br i1 %[[V]], label %loop_exit.split.loopexit, label %loop_latch +; +; CHECK: loop_b: +; CHECK-NEXT: %[[B:.*]] = load i32, i32* %b.ptr +; CHECK-NEXT: br label %loop_exit.split +; +; CHECK: loop_latch: +; CHECK-NEXT: br label %loop_begin + +loop_exit: + %lcssa = phi i32 [ %a, %loop_a ], [ %b, %loop_b ] + ret i32 %lcssa +; CHECK: loop_exit.split.loopexit: +; CHECK-NEXT: %[[A_LCSSA:.*]] = phi i32 [ %[[A]], %loop_a ] +; CHECK-NEXT: br label %loop_exit.split +; +; CHECK: loop_exit.split: +; CHECK-NEXT: %[[AB_PHI:.*]] = phi i32 [ %[[B]], %loop_b ], [ %[[A_LCSSA]], %loop_exit.split.loopexit ] +; CHECK-NEXT: br label %loop_exit +; +; CHECK: loop_exit: +; CHECK-NEXT: %[[AB_PHI_US:.*]] = phi i32 [ %[[AB_PHI]], %loop_exit.split ], [ %[[A_LCSSA_US]], %loop_exit.split.us ] +; CHECK-NEXT: ret i32 %[[AB_PHI_US]] +} + +; Test where the original loop has an inner loop that has to be traversed to +; rebuild the loop, and where this inner loop has multiple blocks, and where +; the exiting block that connects the inner loop to the original loop is not +; the header block. This ensures that we correctly handle interesting corner +; cases of traversing back to the header when re-establishing the original loop +; still exists after unswitching. +define i32 @test13b(i1* %ptr, i1 %cond, i32* %a.ptr, i32* %b.ptr) { +; CHECK-LABEL: @test13b( +entry: + br label %loop_begin +; CHECK-NEXT: entry: +; CHECK-NEXT: br i1 %cond, label %entry.split.us, label %entry.split + +loop_begin: + %a = load i32, i32* %a.ptr + %v1 = load i1, i1* %ptr + br i1 %v1, label %loop_a, label %loop_b + +loop_a: + %v2 = load i1, i1* %ptr + br i1 %v2, label %loop_exit, label %loop_latch + +loop_b: + %b = load i32, i32* %b.ptr + br i1 %cond, label %loop_exit, label %loop_b_inner_ph + +loop_b_inner_ph: + br label %loop_b_inner_header + +loop_b_inner_header: + %v3 = load i1, i1* %ptr + br i1 %v3, label %loop_b_inner_latch, label %loop_b_inner_body + +loop_b_inner_body: + %v4 = load i1, i1* %ptr + br i1 %v4, label %loop_b_inner_latch, label %loop_b_inner_exit + +loop_b_inner_latch: + br label %loop_b_inner_header + +loop_b_inner_exit: + br label %loop_latch + +loop_latch: + br label %loop_begin +; The cloned loop doesn't contain an inner loop. +; +; CHECK: entry.split.us: +; CHECK-NEXT: br label %loop_begin.us +; +; CHECK: loop_begin.us: +; CHECK-NEXT: %[[A:.*]] = load i32, i32* %a.ptr +; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr +; CHECK-NEXT: br i1 %[[V]], label %loop_a.us, label %loop_b.us +; +; CHECK: loop_b.us: +; CHECK-NEXT: %[[B:.*]] = load i32, i32* %b.ptr +; CHECK-NEXT: br label %loop_exit.split.us +; +; CHECK: loop_a.us: +; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr +; CHECK-NEXT: br i1 %[[V]], label %loop_exit.split.us.loopexit, label %loop_latch.us +; +; CHECK: loop_latch.us: +; CHECK-NEXT: br label %loop_begin.us +; +; CHECK: loop_exit.split.us.loopexit: +; CHECK-NEXT: %[[A_LCSSA_US:.*]] = phi i32 [ %[[A]], %loop_a.us ] +; CHECK-NEXT: br label %loop_exit.split.us +; +; CHECK: loop_exit.split.us: +; CHECK-NEXT: %[[AB_PHI_US:.*]] = phi i32 [ %[[B]], %loop_b.us ], [ %[[A_LCSSA_US]], %loop_exit.split.us.loopexit ] +; CHECK-NEXT: br label %loop_exit +; +; But the original loop contains an inner loop that must be traversed.; +; +; CHECK: entry.split: +; CHECK-NEXT: br label %loop_begin +; +; CHECK: loop_begin: +; CHECK-NEXT: %[[A:.*]] = load i32, i32* %a.ptr +; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr +; CHECK-NEXT: br i1 %[[V]], label %loop_a, label %loop_b +; +; CHECK: loop_a: +; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr +; CHECK-NEXT: br i1 %[[V]], label %loop_exit.split, label %loop_latch +; +; CHECK: loop_b: +; CHECK-NEXT: %[[B:.*]] = load i32, i32* %b.ptr +; CHECK-NEXT: br label %loop_b_inner_ph +; +; CHECK: loop_b_inner_ph: +; CHECK-NEXT: br label %loop_b_inner_header +; +; CHECK: loop_b_inner_header: +; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr +; CHECK-NEXT: br i1 %[[V]], label %loop_b_inner_latch, label %loop_b_inner_body +; +; CHECK: loop_b_inner_body: +; CHECK-NEXT: %[[V:.*]] = load i1, i1* %ptr +; CHECK-NEXT: br i1 %[[V]], label %loop_b_inner_latch, label %loop_b_inner_exit +; +; CHECK: loop_b_inner_latch: +; CHECK-NEXT: br label %loop_b_inner_header +; +; CHECK: loop_b_inner_exit: +; CHECK-NEXT: br label %loop_latch +; +; CHECK: loop_latch: +; CHECK-NEXT: br label %loop_begin + +loop_exit: + %lcssa = phi i32 [ %a, %loop_a ], [ %b, %loop_b ] + ret i32 %lcssa +; CHECK: loop_exit.split: +; CHECK-NEXT: %[[A_LCSSA:.*]] = phi i32 [ %[[A]], %loop_a ] +; CHECK-NEXT: br label %loop_exit +; +; CHECK: loop_exit: +; CHECK-NEXT: %[[AB_PHI:.*]] = phi i32 [ %[[A_LCSSA]], %loop_exit.split ], [ %[[AB_PHI_US]], %loop_exit.split.us ] +; CHECK-NEXT: ret i32 %[[AB_PHI]] +} + +define i32 @test20(i32* %var, i32 %cond1, i32 %cond2) { +; CHECK-LABEL: @test20( +entry: + br label %loop_begin +; CHECK-NEXT: entry: +; CHECK-NEXT: br label %loop_begin + +loop_begin: + %var_val = load i32, i32* %var + switch i32 %cond2, label %loop_a [ + i32 0, label %loop_b + i32 1, label %loop_b + i32 13, label %loop_c + i32 2, label %loop_b + i32 42, label %loop_exit + ] +; CHECK: loop_begin: +; CHECK-NEXT: %[[V:.*]] = load i32, i32* %var +; CHECK-NEXT: switch i32 %cond2, label %loop_a [ +; CHECK-NEXT: i32 0, label %loop_b +; CHECK-NEXT: i32 1, label %loop_b +; CHECK-NEXT: i32 13, label %loop_c +; CHECK-NEXT: i32 2, label %loop_b +; CHECK-NEXT: i32 42, label %loop_exit +; CHECK-NEXT: ] + +loop_a: + call void @a() + br label %loop_latch +; CHECK: loop_a: +; CHECK-NEXT: call void @a() +; CHECK-NEXT: br label %loop_latch + +loop_b: + call void @b() + br label %loop_latch +; CHECK: loop_b: +; CHECK-NEXT: call void @b() +; CHECK-NEXT: br label %loop_latch + +loop_c: + call void @c() noreturn nounwind + br label %loop_latch +; CHECK: loop_c: +; CHECK-NEXT: call void @c() +; CHECK-NEXT: br label %loop_latch + +loop_latch: + br label %loop_begin +; CHECK: loop_latch: +; CHECK-NEXT: br label %loop_begin + +loop_exit: + %lcssa = phi i32 [ %var_val, %loop_begin ] + ret i32 %lcssa +; CHECK: loop_exit: +; CHECK-NEXT: %[[LCSSA:.*]] = phi i32 [ %[[V]], %loop_begin ] +; CHECK-NEXT: ret i32 %[[LCSSA]] +}