lib/Analysis/LoopInfo.cpp

   1 //===- LoopInfo.cpp - Natural Loop Calculator -----------------------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by the LLVM research group and is distributed under
   6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file defines the LoopInfo class that is used to identify natural loops
  11 // and determine the loop depth of various nodes of the CFG.  Note that the
  12 // loops identified may actually be several natural loops that share the same
  13 // header node... not just a single natural loop.
  14 //
  15 //===----------------------------------------------------------------------===//
  16
  17 #include "llvm/Analysis/LoopInfo.h"
  18 #include "llvm/Constants.h"
  19 #include "llvm/Instructions.h"
  20 #include "llvm/Analysis/Dominators.h"
  21 #include "llvm/Assembly/Writer.h"
  22 #include "llvm/Support/CFG.h"
  23 #include "llvm/Support/Streams.h"
  24 #include "llvm/ADT/DepthFirstIterator.h"
  25 #include "llvm/ADT/SmallPtrSet.h"
  26 #include <algorithm>
  27 #include <ostream>
  28 using namespace llvm;
  29
  30 char LoopInfo::ID = 0;
  31 static RegisterPass<LoopInfo>
  32 X("loops", "Natural Loop Construction", true);
  33
  34 //===----------------------------------------------------------------------===//
  35 // Loop implementation
  36 //
  37
  38 /// getNumBackEdges - Calculate the number of back edges to the loop header.
  39 ///
  40
  41 //===----------------------------------------------------------------------===//
  42 // LoopInfo implementation
  43 //
  44 bool LoopInfo::runOnFunction(Function &) {
  45   releaseMemory();
  46   Calculate(getAnalysis<DominatorTree>());    // Update
  47   return false;
  48 }
  49
  50 void LoopInfo::releaseMemory() {
  51   for (std::vector<Loop*>::iterator I = TopLevelLoops.begin(),
  52          E = TopLevelLoops.end(); I != E; ++I)
  53     delete *I;   // Delete all of the loops...
  54
  55   BBMap.clear();                             // Reset internal state of analysis
  56   TopLevelLoops.clear();
  57 }
  58
  59 void LoopInfo::Calculate(DominatorTree &DT) {
  60   BasicBlock *RootNode = DT.getRootNode()->getBlock();
  61
  62   for (df_iterator<BasicBlock*> NI = df_begin(RootNode),
  63          NE = df_end(RootNode); NI != NE; ++NI)
  64     if (Loop *L = ConsiderForLoop(*NI, DT))
  65       TopLevelLoops.push_back(L);
  66 }
  67
  68 void LoopInfo::getAnalysisUsage(AnalysisUsage &AU) const {
  69   AU.setPreservesAll();
  70   AU.addRequired<DominatorTree>();
  71 }
  72
  73 void LoopInfo::print(std::ostream &OS, const Module* ) const {
  74   for (unsigned i = 0; i < TopLevelLoops.size(); ++i)
  75     TopLevelLoops[i]->print(OS);
  76 #if 0
  77   for (std::map<BasicBlock*, Loop*>::const_iterator I = BBMap.begin(),
  78          E = BBMap.end(); I != E; ++I)
  79     OS << "BB '" << I->first->getName() << "' level = "
  80        << I->second->getLoopDepth() << "\n";
  81 #endif
  82 }
  83
  84 static bool isNotAlreadyContainedIn(Loop *SubLoop, Loop *ParentLoop) {
  85   if (SubLoop == 0) return true;
  86   if (SubLoop == ParentLoop) return false;
  87   return isNotAlreadyContainedIn(SubLoop->getParentLoop(), ParentLoop);
  88 }
  89
  90 Loop *LoopInfo::ConsiderForLoop(BasicBlock *BB, DominatorTree &DT) {
  91   if (BBMap.find(BB) != BBMap.end()) return 0;   // Haven't processed this node?
  92
  93   std::vector<BasicBlock *> TodoStack;
  94
  95   // Scan the predecessors of BB, checking to see if BB dominates any of
  96   // them.  This identifies backedges which target this node...
  97   for (pred_iterator I = pred_begin(BB), E = pred_end(BB); I != E; ++I)
  98     if (DT.dominates(BB, *I))   // If BB dominates it's predecessor...
  99       TodoStack.push_back(*I);
 100
 101   if (TodoStack.empty()) return 0;  // No backedges to this block...
 102
 103   // Create a new loop to represent this basic block...
 104   Loop *L = new Loop(BB);
 105   BBMap[BB] = L;
 106
 107   BasicBlock *EntryBlock = &BB->getParent()->getEntryBlock();
 108
 109   while (!TodoStack.empty()) {  // Process all the nodes in the loop
 110     BasicBlock *X = TodoStack.back();
 111     TodoStack.pop_back();
 112
 113     if (!L->contains(X) &&         // As of yet unprocessed??
 114         DT.dominates(EntryBlock, X)) {   // X is reachable from entry block?
 115       // Check to see if this block already belongs to a loop.  If this occurs
 116       // then we have a case where a loop that is supposed to be a child of the
 117       // current loop was processed before the current loop.  When this occurs,
 118       // this child loop gets added to a part of the current loop, making it a
 119       // sibling to the current loop.  We have to reparent this loop.
 120       if (Loop *SubLoop = const_cast<Loop*>(getLoopFor(X)))
 121         if (SubLoop->getHeader() == X && isNotAlreadyContainedIn(SubLoop, L)) {
 122           // Remove the subloop from it's current parent...
 123           assert(SubLoop->ParentLoop && SubLoop->ParentLoop != L);
 124           Loop *SLP = SubLoop->ParentLoop;  // SubLoopParent
 125           std::vector<Loop*>::iterator I =
 126             std::find(SLP->SubLoops.begin(), SLP->SubLoops.end(), SubLoop);
 127           assert(I != SLP->SubLoops.end() && "SubLoop not a child of parent?");
 128           SLP->SubLoops.erase(I);   // Remove from parent...
 129
 130           // Add the subloop to THIS loop...
 131           SubLoop->ParentLoop = L;
 132           L->SubLoops.push_back(SubLoop);
 133         }
 134
 135       // Normal case, add the block to our loop...
 136       L->Blocks.push_back(X);
 137
 138       // Add all of the predecessors of X to the end of the work stack...
 139       TodoStack.insert(TodoStack.end(), pred_begin(X), pred_end(X));
 140     }
 141   }
 142
 143   // If there are any loops nested within this loop, create them now!
 144   for (std::vector<BasicBlock*>::iterator I = L->Blocks.begin(),
 145          E = L->Blocks.end(); I != E; ++I)
 146     if (Loop *NewLoop = ConsiderForLoop(*I, DT)) {
 147       L->SubLoops.push_back(NewLoop);
 148       NewLoop->ParentLoop = L;
 149     }
 150
 151   // Add the basic blocks that comprise this loop to the BBMap so that this
 152   // loop can be found for them.
 153   //
 154   for (std::vector<BasicBlock*>::iterator I = L->Blocks.begin(),
 155          E = L->Blocks.end(); I != E; ++I) {
 156     std::map<BasicBlock*, Loop*>::iterator BBMI = BBMap.lower_bound(*I);
 157     if (BBMI == BBMap.end() || BBMI->first != *I)  // Not in map yet...
 158       BBMap.insert(BBMI, std::make_pair(*I, L));   // Must be at this level
 159   }
 160
 161   // Now that we have a list of all of the child loops of this loop, check to
 162   // see if any of them should actually be nested inside of each other.  We can
 163   // accidentally pull loops our of their parents, so we must make sure to
 164   // organize the loop nests correctly now.
 165   {
 166     std::map<BasicBlock*, Loop*> ContainingLoops;
 167     for (unsigned i = 0; i != L->SubLoops.size(); ++i) {
 168       Loop *Child = L->SubLoops[i];
 169       assert(Child->getParentLoop() == L && "Not proper child loop?");
 170
 171       if (Loop *ContainingLoop = ContainingLoops[Child->getHeader()]) {
 172         // If there is already a loop which contains this loop, move this loop
 173         // into the containing loop.
 174         MoveSiblingLoopInto(Child, ContainingLoop);
 175         --i;  // The loop got removed from the SubLoops list.
 176       } else {
 177         // This is currently considered to be a top-level loop.  Check to see if
 178         // any of the contained blocks are loop headers for subloops we have
 179         // already processed.
 180         for (unsigned b = 0, e = Child->Blocks.size(); b != e; ++b) {
 181           Loop *&BlockLoop = ContainingLoops[Child->Blocks[b]];
 182           if (BlockLoop == 0) {   // Child block not processed yet...
 183             BlockLoop = Child;
 184           } else if (BlockLoop != Child) {
 185             Loop *SubLoop = BlockLoop;
 186             // Reparent all of the blocks which used to belong to BlockLoops
 187             for (unsigned j = 0, e = SubLoop->Blocks.size(); j != e; ++j)
 188               ContainingLoops[SubLoop->Blocks[j]] = Child;
 189
 190             // There is already a loop which contains this block, that means
 191             // that we should reparent the loop which the block is currently
 192             // considered to belong to to be a child of this loop.
 193             MoveSiblingLoopInto(SubLoop, Child);
 194             --i;  // We just shrunk the SubLoops list.
 195           }
 196         }
 197       }
 198     }
 199   }
 200
 201   return L;
 202 }
 203
 204 /// MoveSiblingLoopInto - This method moves the NewChild loop to live inside of
 205 /// the NewParent Loop, instead of being a sibling of it.
 206 void LoopInfo::MoveSiblingLoopInto(Loop *NewChild, Loop *NewParent) {
 207   Loop *OldParent = NewChild->getParentLoop();
 208   assert(OldParent && OldParent == NewParent->getParentLoop() &&
 209          NewChild != NewParent && "Not sibling loops!");
 210
 211   // Remove NewChild from being a child of OldParent
 212   std::vector<Loop*>::iterator I =
 213     std::find(OldParent->SubLoops.begin(), OldParent->SubLoops.end(), NewChild);
 214   assert(I != OldParent->SubLoops.end() && "Parent fields incorrect??");
 215   OldParent->SubLoops.erase(I);   // Remove from parent's subloops list
 216   NewChild->ParentLoop = 0;
 217
 218   InsertLoopInto(NewChild, NewParent);
 219 }
 220
 221 /// InsertLoopInto - This inserts loop L into the specified parent loop.  If the
 222 /// parent loop contains a loop which should contain L, the loop gets inserted
 223 /// into L instead.
 224 void LoopInfo::InsertLoopInto(Loop *L, Loop *Parent) {
 225   BasicBlock *LHeader = L->getHeader();
 226   assert(Parent->contains(LHeader) && "This loop should not be inserted here!");
 227
 228   // Check to see if it belongs in a child loop...
 229   for (unsigned i = 0, e = Parent->SubLoops.size(); i != e; ++i)
 230     if (Parent->SubLoops[i]->contains(LHeader)) {
 231       InsertLoopInto(L, Parent->SubLoops[i]);
 232       return;
 233     }
 234
 235   // If not, insert it here!
 236   Parent->SubLoops.push_back(L);
 237   L->ParentLoop = Parent;
 238 }
 239
 240 /// changeLoopFor - Change the top-level loop that contains BB to the
 241 /// specified loop.  This should be used by transformations that restructure
 242 /// the loop hierarchy tree.
 243 void LoopInfo::changeLoopFor(BasicBlock *BB, Loop *L) {
 244   Loop *&OldLoop = BBMap[BB];
 245   assert(OldLoop && "Block not in a loop yet!");
 246   OldLoop = L;
 247 }
 248
 249 /// changeTopLevelLoop - Replace the specified loop in the top-level loops
 250 /// list with the indicated loop.
 251 void LoopInfo::changeTopLevelLoop(Loop *OldLoop, Loop *NewLoop) {
 252   std::vector<Loop*>::iterator I = std::find(TopLevelLoops.begin(),
 253                                              TopLevelLoops.end(), OldLoop);
 254   assert(I != TopLevelLoops.end() && "Old loop not at top level!");
 255   *I = NewLoop;
 256   assert(NewLoop->ParentLoop == 0 && OldLoop->ParentLoop == 0 &&
 257          "Loops already embedded into a subloop!");
 258 }
 259
 260 /// removeLoop - This removes the specified top-level loop from this loop info
 261 /// object.  The loop is not deleted, as it will presumably be inserted into
 262 /// another loop.
 263 Loop *LoopInfo::removeLoop(iterator I) {
 264   assert(I != end() && "Cannot remove end iterator!");
 265   Loop *L = *I;
 266   assert(L->getParentLoop() == 0 && "Not a top-level loop!");
 267   TopLevelLoops.erase(TopLevelLoops.begin() + (I-begin()));
 268   return L;
 269 }
 270
 271 /// removeBlock - This method completely removes BB from all data structures,
 272 /// including all of the Loop objects it is nested in and our mapping from
 273 /// BasicBlocks to loops.
 274 void LoopInfo::removeBlock(BasicBlock *BB) {
 275   std::map<BasicBlock *, Loop*>::iterator I = BBMap.find(BB);
 276   if (I != BBMap.end()) {
 277     for (Loop *L = I->second; L; L = L->getParentLoop())
 278       L->removeBlockFromLoop(BB);
 279
 280     BBMap.erase(I);
 281   }
 282 }
 283
 284 // Ensure this file gets linked when LoopInfo.h is used.
 285 DEFINING_FILE_FOR(LoopInfo)