LoopInfo.cpp revision 697954c15da58bd8b186dbafdedd8b06db770201 
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/BasicBlock.h"
13#include "Support/DepthFirstIterator.h"
14#include <algorithm>
15
16bool cfg::Loop::contains(const BasicBlock *BB) const {
17  return find(Blocks.begin(), Blocks.end(), BB) != Blocks.end();
18}
19
20cfg::LoopInfo::LoopInfo(const DominatorSet &DS) {
21  const BasicBlock *RootNode = DS.getRoot();
22
23  for (df_iterator<const BasicBlock*> NI = df_begin(RootNode),
24	 NE = df_end(RootNode); NI != NE; ++NI)
25    if (Loop *L = ConsiderForLoop(*NI, DS))
26      TopLevelLoops.push_back(L);
27
28  for (unsigned i = 0; i < TopLevelLoops.size(); ++i)
29    TopLevelLoops[i]->setLoopDepth(1);
30}
31
32cfg::Loop *cfg::LoopInfo::ConsiderForLoop(const BasicBlock *BB,
33					  const DominatorSet &DS) {
34  if (BBMap.find(BB) != BBMap.end()) return 0;   // Havn't processed this node?
35
36  std::vector<const BasicBlock *> TodoStack;
37
38  // Scan the predecessors of BB, checking to see if BB dominates any of
39  // them.
40  for (BasicBlock::pred_const_iterator I = BB->pred_begin(),
41	 E = BB->pred_end(); I != E; ++I)
42    if (DS.dominates(BB, *I))   // If BB dominates it's predecessor...
43      TodoStack.push_back(*I);
44
45  if (TodoStack.empty()) return 0;  // Doesn't dominate any predecessors...
46
47  // Create a new loop to represent this basic block...
48  Loop *L = new Loop(BB);
49  BBMap[BB] = L;
50
51  while (!TodoStack.empty()) {  // Process all the nodes in the loop
52    const BasicBlock *X = TodoStack.back();
53    TodoStack.pop_back();
54
55    if (!L->contains(X)) {                  // As of yet unprocessed??
56      L->Blocks.push_back(X);
57
58      // Add all of the predecessors of X to the end of the work stack...
59      TodoStack.insert(TodoStack.end(), X->pred_begin(), X->pred_end());
60    }
61  }
62
63  // Add the basic blocks that comprise this loop to the BBMap so that this
64  // loop can be found for them.  Also check subsidary basic blocks to see if
65  // they start subloops of their own.
66  //
67  for (std::vector<const BasicBlock*>::reverse_iterator I = L->Blocks.rbegin(),
68	 E = L->Blocks.rend(); I != E; ++I) {
69
70    // Check to see if this block starts a new loop
71    if (Loop *NewLoop = ConsiderForLoop(*I, DS)) {
72      L->SubLoops.push_back(NewLoop);
73      NewLoop->ParentLoop = L;
74    }
75
76    if (BBMap.find(*I) == BBMap.end())
77      BBMap.insert(std::make_pair(*I, L));
78  }
79
80  return L;
81}
82