- // Add the basic blocks that comprise this loop to the BBMap so that this
- // loop can be found for them.
- //
- for (typename std::vector<BlockT*>::iterator I = L->Blocks.begin(),
- E = L->Blocks.end(); I != E; ++I)
- BBMap.insert(std::make_pair(*I, L));
-
- // Now that we have a list of all of the child loops of this loop, check to
- // see if any of them should actually be nested inside of each other. We
- // can accidentally pull loops our of their parents, so we must make sure to
- // organize the loop nests correctly now.
- {
- std::map<BlockT *, LoopT *> ContainingLoops;
- for (unsigned i = 0; i != L->SubLoops.size(); ++i) {
- LoopT *Child = L->SubLoops[i];
- assert(Child->getParentLoop() == L && "Not proper child loop?");
-
- if (LoopT *ContainingLoop = ContainingLoops[Child->getHeader()]) {
- // If there is already a loop which contains this loop, move this loop
- // into the containing loop.
- MoveSiblingLoopInto(Child, ContainingLoop);
- --i; // The loop got removed from the SubLoops list.
- } else {
- // This is currently considered to be a top-level loop. Check to see
- // if any of the contained blocks are loop headers for subloops we
- // have already processed.
- for (unsigned b = 0, e = Child->Blocks.size(); b != e; ++b) {
- LoopT *&BlockLoop = ContainingLoops[Child->Blocks[b]];
- if (BlockLoop == 0) { // Child block not processed yet...
- BlockLoop = Child;
- } else if (BlockLoop != Child) {
- LoopT *SubLoop = BlockLoop;
- // Reparent all of the blocks which used to belong to BlockLoops
- for (unsigned j = 0, e = SubLoop->Blocks.size(); j != e; ++j)
- ContainingLoops[SubLoop->Blocks[j]] = Child;
-
- // There is already a loop which contains this block, that means
- // that we should reparent the loop which the block is currently
- // considered to belong to to be a child of this loop.
- MoveSiblingLoopInto(SubLoop, Child);
- --i; // We just shrunk the SubLoops list.
- }
- }
- }
- }
- }
-
- return L;
- }
-
- /// MoveSiblingLoopInto - This method moves the NewChild loop to live inside
- /// of the NewParent Loop, instead of being a sibling of it.
- void MoveSiblingLoopInto(LoopT *NewChild,
- LoopT *NewParent) {
- LoopT *OldParent = NewChild->getParentLoop();
- assert(OldParent && OldParent == NewParent->getParentLoop() &&
- NewChild != NewParent && "Not sibling loops!");
-
- // Remove NewChild from being a child of OldParent
- typename std::vector<LoopT *>::iterator I =
- std::find(OldParent->SubLoops.begin(), OldParent->SubLoops.end(),
- NewChild);
- assert(I != OldParent->SubLoops.end() && "Parent fields incorrect??");
- OldParent->SubLoops.erase(I); // Remove from parent's subloops list
- NewChild->ParentLoop = 0;
-
- InsertLoopInto(NewChild, NewParent);
- }
-
- /// InsertLoopInto - This inserts loop L into the specified parent loop. If
- /// the parent loop contains a loop which should contain L, the loop gets
- /// inserted into L instead.
- void InsertLoopInto(LoopT *L, LoopT *Parent) {
- BlockT *LHeader = L->getHeader();
- assert(Parent->contains(LHeader) &&
- "This loop should not be inserted here!");
-
- // Check to see if it belongs in a child loop...
- for (unsigned i = 0, e = static_cast<unsigned>(Parent->SubLoops.size());
- i != e; ++i)
- if (Parent->SubLoops[i]->contains(LHeader)) {
- InsertLoopInto(L, Parent->SubLoops[i]);
- return;
- }
-
- // If not, insert it here!
- Parent->SubLoops.push_back(L);
- L->ParentLoop = Parent;
- }
-
- // Debugging
-
- void print(raw_ostream &OS) const {
- for (unsigned i = 0; i < TopLevelLoops.size(); ++i)
- TopLevelLoops[i]->print(OS);
- #if 0
- for (std::map<BasicBlock*, LoopT*>::const_iterator I = BBMap.begin(),
- E = BBMap.end(); I != E; ++I)
- OS << "BB '" << I->first->getName() << "' level = "
- << I->second->getLoopDepth() << "\n";
- #endif
- }
-};
-
-class LoopInfo : public FunctionPass {
- LoopInfoBase<BasicBlock, Loop> LI;