#include "llvm/Constants.h"
#include "llvm/Instructions.h"
#include "llvm/Analysis/Dominators.h"
-#include "llvm/Analysis/LoopIterator.h"
#include "llvm/Assembly/Writer.h"
#include "llvm/Support/CFG.h"
#include "llvm/Support/CommandLine.h"
print(dbgs());
}
-//===----------------------------------------------------------------------===//
-// UnloopUpdater implementation
-//
-
-/// 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 updateSubloopParents();
-
-protected:
- Loop *getNearestLoop(BasicBlock *BB, Loop *BBLoop);
-};
-
-/// updateBlockParents - Update the parent loop for all blocks that are directly
-/// contained within the original "unloop".
-void UnloopUpdater::updateBlockParents() {
- {
- // 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;
- }
- }
- }
-}
-
-/// updateSubloopParents - Update the parent loop for all subloops directly
-/// nested within unloop.
-void UnloopUpdater::updateSubloopParents() {
- while (!Unloop->empty()) {
- Loop *Subloop = *(Unloop->end()-1);
- Unloop->removeChildLoop(Unloop->end()-1);
-
- assert(SubloopParents.count(Subloop) && "DFS failed to visit subloop");
- if (SubloopParents[Subloop])
- SubloopParents[Subloop]->addChildLoop(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) {
-
- // Initialy 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;
-}
-
//===----------------------------------------------------------------------===//
// LoopInfo implementation
//
return false;
}
-/// updateUnloop - The last backedge has been removed from a loop--now the
-/// "unloop". Find a new parent for the blocks contained within unloop and
-/// update the loop tree. We don't necessarilly have valid dominators at this
-/// point, but LoopInfo is still valid except for the removal of this loop.
-void LoopInfo::updateUnloop(Loop *Unloop) {
-
- // First handle the special case of no parent loop to simplify the algorithm.
- if (!Unloop->getParentLoop()) {
- // Since BBLoop had no parent, Unloop blocks are no longer in a loop.
- for (Loop::block_iterator I = Unloop->block_begin(),
- E = Unloop->block_end(); I != E; ++I) {
-
- // Don't reparent blocks in subloops.
- if (getLoopFor(*I) != Unloop)
- continue;
-
- // Blocks no longer have a parent but are still referenced by Unloop until
- // the Unloop object is deleted.
- LI.changeLoopFor(*I, 0);
- }
-
- // 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 == Unloop) {
- LI.removeLoop(I);
- break;
- }
- }
-
- // Move all of the subloops to the top-level.
- while (!Unloop->empty())
- LI.addTopLevelLoop(Unloop->removeChildLoop(Unloop->end()-1));
-
- return;
- }
-
- // Update the parent loop for all blocks within the loop. Blocks within
- // subloops will not change parents.
- UnloopUpdater Updater(Unloop, this);
- Updater.updateBlockParents();
-
- // Remove unloop's blocks from all ancestors below their new parents.
- for (Loop::block_iterator BI = Unloop->block_begin(),
- BE = Unloop->block_end(); BI != BE; ++BI) {
- Loop *NewParent = getLoopFor(*BI);
- // If this block is in a subloop, skip it.
- if (Unloop->contains(NewParent))
- continue;
-
- // Remove blocks from former Ancestors except Unloop itself which will be
- // deleted.
- for (Loop *OldParent = Unloop->getParentLoop(); OldParent != NewParent;
- OldParent = OldParent->getParentLoop()) {
- assert(OldParent && "new loop is not an ancestor of the original");
- OldParent->removeBlockFromLoop(*BI);
- }
- }
-
- // Add direct subloops as children in their new parent loop.
- Updater.updateSubloopParents();
-
- // Remove unloop from its parent loop.
- Loop *ParentLoop = Unloop->getParentLoop();
- for (Loop::iterator I = ParentLoop->begin(), E = ParentLoop->end();; ++I) {
- assert(I != E && "Couldn't find loop");
- if (*I == Unloop) {
- ParentLoop->removeChildLoop(I);
- break;
- }
- }
-}
-
void LoopInfo::verifyAnalysis() const {
// LoopInfo is a FunctionPass, but verifying every loop in the function
// each time verifyAnalysis is called is very expensive. The
/// Delete loop from the loop queue and loop hierarchy (LoopInfo).
void LPPassManager::deleteLoopFromQueue(Loop *L) {
- LI->updateUnloop(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;
// 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) {
projects / oota-llvm.git / commitdiff