+void Loop::dump() const {
+ print(dbgs());
+}
+
+//===----------------------------------------------------------------------===//
+// UnloopUpdater implementation
+//
+
+namespace {
+/// Find the new parent loop for all blocks within the "unloop" whose last
+/// backedges has just been removed.
+class UnloopUpdater {
+ Loop *Unloop;
+ LoopInfo *LI;
+
+ LoopBlocksDFS DFS;
+
+ // Map unloop's immediate subloops to their nearest reachable parents. Nested
+ // loops within these subloops will not change parents. However, an immediate
+ // subloop's new parent will be the nearest loop reachable from either its own
+ // exits *or* any of its nested loop's exits.
+ DenseMap<Loop*, Loop*> SubloopParents;
+
+ // Flag the presence of an irreducible backedge whose destination is a block
+ // directly contained by the original unloop.
+ bool FoundIB;
+
+public:
+ UnloopUpdater(Loop *UL, LoopInfo *LInfo) :
+ Unloop(UL), LI(LInfo), DFS(UL), FoundIB(false) {}
+
+ void updateBlockParents();
+
+ void removeBlocksFromAncestors();
+
+ void updateSubloopParents();
+
+protected:
+ Loop *getNearestLoop(BasicBlock *BB, Loop *BBLoop);
+};
+} // end anonymous namespace
+
+/// updateBlockParents - Update the parent loop for all blocks that are directly
+/// contained within the original "unloop".
+void UnloopUpdater::updateBlockParents() {
+ if (Unloop->getNumBlocks()) {
+ // Perform a post order CFG traversal of all blocks within this loop,
+ // propagating the nearest loop from sucessors to predecessors.
+ LoopBlocksTraversal Traversal(DFS, LI);
+ for (LoopBlocksTraversal::POTIterator POI = Traversal.begin(),
+ POE = Traversal.end(); POI != POE; ++POI) {
+
+ Loop *L = LI->getLoopFor(*POI);
+ Loop *NL = getNearestLoop(*POI, L);
+
+ if (NL != L) {
+ // For reducible loops, NL is now an ancestor of Unloop.
+ assert((NL != Unloop && (!NL || NL->contains(Unloop))) &&
+ "uninitialized successor");
+ LI->changeLoopFor(*POI, NL);
+ }
+ else {
+ // Or the current block is part of a subloop, in which case its parent
+ // is unchanged.
+ assert((FoundIB || Unloop->contains(L)) && "uninitialized successor");
+ }
+ }
+ }
+ // Each irreducible loop within the unloop induces a round of iteration using
+ // the DFS result cached by Traversal.
+ bool Changed = FoundIB;
+ for (unsigned NIters = 0; Changed; ++NIters) {
+ assert(NIters < Unloop->getNumBlocks() && "runaway iterative algorithm");
+
+ // Iterate over the postorder list of blocks, propagating the nearest loop
+ // from successors to predecessors as before.
+ Changed = false;
+ for (LoopBlocksDFS::POIterator POI = DFS.beginPostorder(),
+ POE = DFS.endPostorder(); POI != POE; ++POI) {
+
+ Loop *L = LI->getLoopFor(*POI);
+ Loop *NL = getNearestLoop(*POI, L);
+ if (NL != L) {
+ assert(NL != Unloop && (!NL || NL->contains(Unloop)) &&
+ "uninitialized successor");
+ LI->changeLoopFor(*POI, NL);
+ Changed = true;
+ }
+ }
+ }
+}
+
+/// removeBlocksFromAncestors - Remove unloop's blocks from all ancestors below
+/// their new parents.
+void UnloopUpdater::removeBlocksFromAncestors() {
+ // Remove all unloop's blocks (including those in nested subloops) from
+ // ancestors below the new parent loop.
+ for (Loop::block_iterator BI = Unloop->block_begin(),
+ BE = Unloop->block_end(); BI != BE; ++BI) {
+ Loop *OuterParent = LI->getLoopFor(*BI);
+ if (Unloop->contains(OuterParent)) {
+ while (OuterParent->getParentLoop() != Unloop)
+ OuterParent = OuterParent->getParentLoop();
+ OuterParent = SubloopParents[OuterParent];
+ }
+ // Remove blocks from former Ancestors except Unloop itself which will be
+ // deleted.
+ for (Loop *OldParent = Unloop->getParentLoop(); OldParent != OuterParent;
+ OldParent = OldParent->getParentLoop()) {
+ assert(OldParent && "new loop is not an ancestor of the original");
+ OldParent->removeBlockFromLoop(*BI);
+ }
+ }
+}
+
+/// updateSubloopParents - Update the parent loop for all subloops directly
+/// nested within unloop.
+void UnloopUpdater::updateSubloopParents() {
+ while (!Unloop->empty()) {
+ Loop *Subloop = *llvm::prior(Unloop->end());
+ Unloop->removeChildLoop(llvm::prior(Unloop->end()));
+
+ assert(SubloopParents.count(Subloop) && "DFS failed to visit subloop");
+ if (SubloopParents[Subloop])
+ SubloopParents[Subloop]->addChildLoop(Subloop);
+ else
+ LI->addTopLevelLoop(Subloop);
+ }
+}
+
+/// getNearestLoop - Return the nearest parent loop among this block's
+/// successors. If a successor is a subloop header, consider its parent to be
+/// the nearest parent of the subloop's exits.
+///
+/// For subloop blocks, simply update SubloopParents and return NULL.
+Loop *UnloopUpdater::getNearestLoop(BasicBlock *BB, Loop *BBLoop) {
+
+ // Initially for blocks directly contained by Unloop, NearLoop == Unloop and
+ // is considered uninitialized.
+ Loop *NearLoop = BBLoop;
+
+ Loop *Subloop = 0;
+ if (NearLoop != Unloop && Unloop->contains(NearLoop)) {
+ Subloop = NearLoop;
+ // Find the subloop ancestor that is directly contained within Unloop.
+ while (Subloop->getParentLoop() != Unloop) {
+ Subloop = Subloop->getParentLoop();
+ assert(Subloop && "subloop is not an ancestor of the original loop");
+ }
+ // Get the current nearest parent of the Subloop exits, initially Unloop.
+ if (!SubloopParents.count(Subloop))
+ SubloopParents[Subloop] = Unloop;
+ NearLoop = SubloopParents[Subloop];
+ }
+
+ succ_iterator I = succ_begin(BB), E = succ_end(BB);
+ if (I == E) {
+ assert(!Subloop && "subloop blocks must have a successor");
+ NearLoop = 0; // unloop blocks may now exit the function.
+ }
+ for (; I != E; ++I) {
+ if (*I == BB)
+ continue; // self loops are uninteresting
+
+ Loop *L = LI->getLoopFor(*I);
+ if (L == Unloop) {
+ // This successor has not been processed. This path must lead to an
+ // irreducible backedge.
+ assert((FoundIB || !DFS.hasPostorder(*I)) && "should have seen IB");
+ FoundIB = true;
+ }
+ if (L != Unloop && Unloop->contains(L)) {
+ // Successor is in a subloop.
+ if (Subloop)
+ continue; // Branching within subloops. Ignore it.
+
+ // BB branches from the original into a subloop header.
+ assert(L->getParentLoop() == Unloop && "cannot skip into nested loops");
+
+ // Get the current nearest parent of the Subloop's exits.
+ L = SubloopParents[L];
+ // L could be Unloop if the only exit was an irreducible backedge.
+ }
+ if (L == Unloop) {
+ continue;
+ }
+ // Handle critical edges from Unloop into a sibling loop.
+ if (L && !L->contains(Unloop)) {
+ L = L->getParentLoop();
+ }
+ // Remember the nearest parent loop among successors or subloop exits.
+ if (NearLoop == Unloop || !NearLoop || NearLoop->contains(L))
+ NearLoop = L;
+ }
+ if (Subloop) {
+ SubloopParents[Subloop] = NearLoop;
+ return BBLoop;
+ }
+ return NearLoop;
+}
+