lib/Analysis/LoopInfo.cpp

   1 //===- LoopInfo.cpp - Natural Loop Calculator -------------------------------=//
   2 //
   3 // This file defines the LoopInfo class that is used to identify natural loops
   4 // and determine the loop depth of various nodes of the CFG.  Note that the
   5 // loops identified may actually be several natural loops that share the same
   6 // header node... not just a single natural loop.
   7 //
   8 //===----------------------------------------------------------------------===//
   9
  10 #include "llvm/Analysis/LoopInfo.h"
  11 #include "llvm/Analysis/Dominators.h"
  12 #include "llvm/Support/CFG.h"
  13 #include "llvm/Assembly/Writer.h"
  14 #include "Support/DepthFirstIterator.h"
  15 #include <algorithm>
  16
  17 static RegisterAnalysis<LoopInfo>
  18 X("loops", "Natural Loop Construction", true);
  19
  20 //===----------------------------------------------------------------------===//
  21 // Loop implementation
  22 //
  23 bool Loop::contains(const BasicBlock *BB) const {
  24   return find(Blocks.begin(), Blocks.end(), BB) != Blocks.end();
  25 }
  26
  27 void Loop::print(std::ostream &OS) const {
  28   OS << std::string(getLoopDepth()*2, ' ') << "Loop Containing: ";
  29
  30   for (unsigned i = 0; i < getBlocks().size(); ++i) {
  31     if (i) OS << ",";
  32     WriteAsOperand(OS, (const Value*)getBlocks()[i]);
  33   }
  34   OS << "\n";
  35
  36   std::copy(getSubLoops().begin(), getSubLoops().end(),
  37             std::ostream_iterator<const Loop*>(OS, "\n"));
  38 }
  39
  40 //===----------------------------------------------------------------------===//
  41 // LoopInfo implementation
  42 //
  43
  44 bool LoopInfo::runOnFunction(Function &) {
  45   releaseMemory();
  46   Calculate(getAnalysis<DominatorSet>());    // 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
  60 void LoopInfo::Calculate(const DominatorSet &DS) {
  61   BasicBlock *RootNode = DS.getRoot();
  62
  63   for (df_iterator<BasicBlock*> NI = df_begin(RootNode),
  64          NE = df_end(RootNode); NI != NE; ++NI)
  65     if (Loop *L = ConsiderForLoop(*NI, DS))
  66       TopLevelLoops.push_back(L);
  67
  68   for (unsigned i = 0; i < TopLevelLoops.size(); ++i)
  69     TopLevelLoops[i]->setLoopDepth(1);
  70 }
  71
  72 void LoopInfo::getAnalysisUsage(AnalysisUsage &AU) const {
  73   AU.setPreservesAll();
  74   AU.addRequired<DominatorSet>();
  75 }
  76
  77 void LoopInfo::print(std::ostream &OS) const {
  78   std::copy(getTopLevelLoops().begin(), getTopLevelLoops().end(),
  79             std::ostream_iterator<const Loop*>(OS, "\n"));
  80 }
  81
  82 Loop *LoopInfo::ConsiderForLoop(BasicBlock *BB, const DominatorSet &DS) {
  83   if (BBMap.find(BB) != BBMap.end()) return 0;   // Havn't processed this node?
  84
  85   std::vector<BasicBlock *> TodoStack;
  86
  87   // Scan the predecessors of BB, checking to see if BB dominates any of
  88   // them.
  89   for (pred_iterator I = pred_begin(BB), E = pred_end(BB); I != E; ++I)
  90     if (DS.dominates(BB, *I))   // If BB dominates it's predecessor...
  91       TodoStack.push_back(*I);
  92
  93   if (TodoStack.empty()) return 0;  // Doesn't dominate any predecessors...
  94
  95   // Create a new loop to represent this basic block...
  96   Loop *L = new Loop(BB);
  97   BBMap[BB] = L;
  98
  99   while (!TodoStack.empty()) {  // Process all the nodes in the loop
 100     BasicBlock *X = TodoStack.back();
 101     TodoStack.pop_back();
 102
 103     if (!L->contains(X)) {                  // As of yet unprocessed??
 104       L->Blocks.push_back(X);
 105
 106       // Add all of the predecessors of X to the end of the work stack...
 107       TodoStack.insert(TodoStack.end(), pred_begin(X), pred_end(X));
 108     }
 109   }
 110
 111   // Add the basic blocks that comprise this loop to the BBMap so that this
 112   // loop can be found for them.  Also check subsidary basic blocks to see if
 113   // they start subloops of their own.
 114   //
 115   for (std::vector<BasicBlock*>::reverse_iterator I = L->Blocks.rbegin(),
 116          E = L->Blocks.rend(); I != E; ++I) {
 117
 118     // Check to see if this block starts a new loop
 119     if (Loop *NewLoop = ConsiderForLoop(*I, DS)) {
 120       L->SubLoops.push_back(NewLoop);
 121       NewLoop->ParentLoop = L;
 122     }
 123
 124     if (BBMap.find(*I) == BBMap.end())
 125       BBMap.insert(std::make_pair(*I, L));
 126   }
 127
 128   return L;
 129 }