//
// This file defines the LoopInfo class that is used to identify natural loops
// and determine the loop depth of various nodes of the CFG. Note that natural
-// loops may actually be several loops that share the same header node...
+// loops may actually be several loops that share the same header node.
//
// This analysis calculates the nesting structure of loops in a function. For
// each natural loop identified, this analysis identifies natural loops
Loop(const Loop &); // DO NOT IMPLEMENT
const Loop &operator=(const Loop &); // DO NOT IMPLEMENT
public:
+ /// Loop ctor - This creates an empty loop.
+ Loop() : ParentLoop(0), LoopDepth(0) {
+ }
unsigned getLoopDepth() const { return LoopDepth; }
BasicBlock *getHeader() const { return Blocks.front(); }
///
void changeExitBlock(BasicBlock *Old, BasicBlock *New);
+ /// replaceChildLoopWith - This is used when splitting loops up. It replaces
+ /// the OldChild entry in our children list with NewChild, and updates the
+ /// parent pointer of OldChild to be null and the NewChild to be this loop.
+ /// This updates the loop depth of the new child.
+ void replaceChildLoopWith(Loop *OldChild, Loop *NewChild);
+
+ /// addChildLoop - Add the specified loop to be a child of this loop. This
+ /// updates the loop depth of the new child.
+ ///
+ void addChildLoop(Loop *NewChild);
+
+ /// removeChildLoop - 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.
+ Loop *removeChildLoop(iterator OldChild);
+
+ /// addExitBlock - Add the specified exit block to the loop.
+ ///
+ void addExitBlock(BasicBlock *BB) {
+ ExitBlocks.push_back(BB);
+ }
+
+ /// addBlockEntry - 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.
+ void addBlockEntry(BasicBlock *BB) {
+ Blocks.push_back(BB);
+ }
+
+ /// removeBlockFromLoop - This removes the specified basic block from the
+ /// current loop, updating the Blocks and ExitBlocks lists as appropriate.
+ /// This does not update the mapping in the LoopInfo class.
+ void removeBlockFromLoop(BasicBlock *BB);
+
void print(std::ostream &O, unsigned Depth = 0) const;
void dump() const;
private:
friend class LoopInfo;
- inline Loop(BasicBlock *BB) : ParentLoop(0) {
+ Loop(BasicBlock *BB) : ParentLoop(0) {
Blocks.push_back(BB); LoopDepth = 0;
}
~Loop() {
///
virtual void getAnalysisUsage(AnalysisUsage &AU) const;
+ /// changeLoopFor - Change the top-level loop that contains BB to the
+ /// specified loop. This should be used by transformations that restructure
+ /// the loop hierarchy tree.
+ void changeLoopFor(BasicBlock *BB, Loop *L);
+
+ /// changeTopLevelLoop - Replace the specified loop in the top-level loops
+ /// list with the indicated loop.
+ void changeTopLevelLoop(Loop *OldLoop, Loop *NewLoop);
+
static void stub(); // Noop
private:
void Calculate(const DominatorSet &DS);
#include "llvm/Support/CFG.h"
#include "Support/DepthFirstIterator.h"
#include <algorithm>
-
-namespace llvm {
+using namespace llvm;
static RegisterAnalysis<LoopInfo>
X("loops", "Natural Loop Construction", true);
L->ParentLoop = Parent;
}
+/// changeLoopFor - Change the top-level loop that contains BB to the
+/// specified loop. This should be used by transformations that restructure
+/// the loop hierarchy tree.
+void LoopInfo::changeLoopFor(BasicBlock *BB, Loop *L) {
+ Loop *&OldLoop = BBMap[BB];
+ assert(OldLoop && "Block not in a loop yet!");
+ OldLoop = L;
+}
+/// changeTopLevelLoop - Replace the specified loop in the top-level loops
+/// list with the indicated loop.
+void LoopInfo::changeTopLevelLoop(Loop *OldLoop, Loop *NewLoop) {
+ std::vector<Loop*>::iterator I = std::find(TopLevelLoops.begin(),
+ TopLevelLoops.end(), OldLoop);
+ assert(I != TopLevelLoops.end() && "Old loop not at top level!");
+ *I = NewLoop;
+ assert(NewLoop->ParentLoop == 0 && OldLoop->ParentLoop == 0 &&
+ "Loops already embedded into a subloop!");
+}
/// getLoopPreheader - If there is a preheader for this loop, return it. A
/// loop has a preheader if there is only one edge to the header of the loop
/// valid to replace the loop header with this method.
///
void Loop::addBasicBlockToLoop(BasicBlock *NewBB, LoopInfo &LI) {
- assert(LI[getHeader()] == this && "Incorrect LI specified for this loop!");
+ assert((Blocks.empty() || LI[getHeader()] == this) &&
+ "Incorrect LI specified for this loop!");
assert(NewBB && "Cannot add a null basic block to the loop!");
assert(LI[NewBB] == 0 && "BasicBlock already in the loop!");
}
}
-} // End llvm namespace
+/// replaceChildLoopWith - This is used when splitting loops up. It replaces
+/// the OldChild entry in our children list with NewChild, and updates the
+/// parent pointers of the two loops as appropriate.
+void Loop::replaceChildLoopWith(Loop *OldChild, Loop *NewChild) {
+ assert(OldChild->ParentLoop == this && "This loop is already broken!");
+ assert(NewChild->ParentLoop == 0 && "NewChild already has a parent!");
+ std::vector<Loop*>::iterator I = std::find(SubLoops.begin(), SubLoops.end(),
+ OldChild);
+ assert(I != SubLoops.end() && "OldChild not in loop!");
+ *I = NewChild;
+ OldChild->ParentLoop = 0;
+ NewChild->ParentLoop = this;
+
+ // Update the loop depth of the new child.
+ NewChild->setLoopDepth(LoopDepth+1);
+}
+
+/// addChildLoop - Add the specified loop to be a child of this loop.
+///
+void Loop::addChildLoop(Loop *NewChild) {
+ assert(NewChild->ParentLoop == 0 && "NewChild already has a parent!");
+ NewChild->ParentLoop = this;
+ SubLoops.push_back(NewChild);
+
+ // Update the loop depth of the new child.
+ NewChild->setLoopDepth(LoopDepth+1);
+}
+
+template<typename T>
+static void RemoveFromVector(std::vector<T*> &V, T *N) {
+ typename std::vector<T*>::iterator I = std::find(V.begin(), V.end(), N);
+ assert(I != V.end() && "N is not in this list!");
+ V.erase(I);
+}
+
+/// removeChildLoop - 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.
+Loop *Loop::removeChildLoop(iterator I) {
+ assert(I != SubLoops.end() && "Cannot remove end iterator!");
+ Loop *Child = *I;
+ assert(Child->ParentLoop == this && "Child is not a child of this loop!");
+ SubLoops.erase(SubLoops.begin()+(I-begin()));
+ Child->ParentLoop = 0;
+ return Child;
+}
+
+
+/// removeBlockFromLoop - This removes the specified basic block from the
+/// current loop, updating the Blocks and ExitBlocks lists as appropriate. This
+/// does not update the mapping in the LoopInfo class.
+void Loop::removeBlockFromLoop(BasicBlock *BB) {
+ RemoveFromVector(Blocks, BB);
+
+ // If this block branched out of this loop, remove any exit blocks entries due
+ // to it.
+ for (succ_iterator SI = succ_begin(BB), E = succ_end(BB); SI != E; ++SI)
+ if (!contains(*SI) && *SI != BB)
+ RemoveFromVector(ExitBlocks, *SI);
+
+ // If any blocks in this loop branch to BB, add it to the exit blocks set.
+ for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI)
+ if (contains(*PI))
+ ExitBlocks.push_back(BB);
+}
projects / oota-llvm.git / commitdiff