Reapplying r136844.
An algorithm for incrementally updating LoopInfo within a
LoopPassManager. The incremental update should be extremely cheap in
most cases and can be used in places where it's not feasible to
regenerate the entire loop forest.
- "Unloop" is a node in the loop tree whose last backedge has been removed.
- Perform reverse dataflow on the block inside Unloop to propagate the
nearest loop from the block's successors.
- For reducible CFG, each block in unloop is visited exactly
once. This is because unloop no longer has a backedge and blocks
within subloops don't change parents.
- Immediate subloops are summarized by the nearest loop reachable from
their exits or exits within nested subloops.
- At completion the unloop blocks each have a new parent loop, and
each immediate subloop has a new parent.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@137276 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/lib/Analysis/LoopPass.cpp b/lib/Analysis/LoopPass.cpp
index f8abf3c..7ba3268 100644
--- a/lib/Analysis/LoopPass.cpp
+++ b/lib/Analysis/LoopPass.cpp
@@ -84,62 +84,18 @@
/// Delete loop from the loop queue and loop hierarchy (LoopInfo).
void LPPassManager::deleteLoopFromQueue(Loop *L) {
- if (Loop *ParentLoop = L->getParentLoop()) { // Not a top-level loop.
- // Reparent all of the blocks in this loop. Since BBLoop had a parent,
- // they are now all in it.
- for (Loop::block_iterator I = L->block_begin(), E = L->block_end();
- I != E; ++I)
- if (LI->getLoopFor(*I) == L) // Don't change blocks in subloops.
- LI->changeLoopFor(*I, ParentLoop);
-
- // Remove the loop from its parent loop.
- for (Loop::iterator I = ParentLoop->begin(), E = ParentLoop->end();;
- ++I) {
- assert(I != E && "Couldn't find loop");
- if (*I == L) {
- ParentLoop->removeChildLoop(I);
- break;
- }
- }
-
- // Move all subloops into the parent loop.
- while (!L->empty())
- ParentLoop->addChildLoop(L->removeChildLoop(L->end()-1));
- } else {
- // Reparent all of the blocks in this loop. Since BBLoop had no parent,
- // they no longer in a loop at all.
-
- for (unsigned i = 0; i != L->getBlocks().size(); ++i) {
- // Don't change blocks in subloops.
- if (LI->getLoopFor(L->getBlocks()[i]) == L) {
- LI->removeBlock(L->getBlocks()[i]);
- --i;
- }
- }
-
- // Remove the loop from the top-level LoopInfo object.
- for (LoopInfo::iterator I = LI->begin(), E = LI->end();; ++I) {
- assert(I != E && "Couldn't find loop");
- if (*I == L) {
- LI->removeLoop(I);
- break;
- }
- }
-
- // Move all of the subloops to the top-level.
- while (!L->empty())
- LI->addTopLevelLoop(L->removeChildLoop(L->end()-1));
- }
-
- delete L;
+ LI->updateUnloop(L);
// If L is current loop then skip rest of the passes and let
// runOnFunction remove L from LQ. Otherwise, remove L from LQ now
// and continue applying other passes on CurrentLoop.
- if (CurrentLoop == L) {
+ if (CurrentLoop == L)
skipThisLoop = true;
+
+ delete L;
+
+ if (skipThisLoop)
return;
- }
for (std::deque<Loop *>::iterator I = LQ.begin(),
E = LQ.end(); I != E; ++I) {