LoopInfo.h revision 8fc2f2072de83665ae20e06929e28317f449bcdf 
1//===- llvm/Analysis/LoopInfo.h - Natural Loop Calculator --------*- C++ -*--=//
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#ifndef LLVM_ANALYSIS_LOOP_INFO_H
11#define LLVM_ANALYSIS_LOOP_INFO_H
12
13#include "llvm/Pass.h"
14#include <set>
15
16class DominatorSet;
17class LoopInfo;
18
19//===----------------------------------------------------------------------===//
20// Loop class - Instances of this class are used to represent loops that are
21// detected in the flow graph
22//
23class Loop {
24  Loop *ParentLoop;
25  std::vector<BasicBlock *> Blocks;  // First entry is the header node
26  std::vector<Loop*> SubLoops;       // Loops contained entirely within this one
27  unsigned LoopDepth;                // Nesting depth of this loop
28
29  Loop(const Loop &);                  // DO NOT IMPLEMENT
30  const Loop &operator=(const Loop &); // DO NOT IMPLEMENT
31public:
32
33  inline unsigned getLoopDepth() const { return LoopDepth; }
34  inline BasicBlock *getHeader() const { return Blocks.front(); }
35
36  // contains - Return true of the specified basic block is in this loop
37  bool contains(BasicBlock *BB) const;
38
39  // getSubLoops - Return the loops contained entirely within this loop
40  inline const std::vector<Loop*> &getSubLoops() const { return SubLoops; }
41  inline const std::vector<BasicBlock*> &getBlocks() const { return Blocks; }
42
43private:
44  friend class LoopInfo;
45  inline Loop(BasicBlock *BB) { Blocks.push_back(BB); LoopDepth = 0; }
46  ~Loop() {
47    for (unsigned i = 0, e = SubLoops.size(); i != e; ++i)
48      delete SubLoops[i];
49  }
50
51  void setLoopDepth(unsigned Level) {
52    LoopDepth = Level;
53    for (unsigned i = 0, e = SubLoops.size(); i != e; ++i)
54      SubLoops[i]->setLoopDepth(Level+1);
55  }
56};
57
58
59
60//===----------------------------------------------------------------------===//
61// LoopInfo - This class builds and contains all of the top level loop
62// structures in the specified function.
63//
64class LoopInfo : public FunctionPass {
65  // BBMap - Mapping of basic blocks to the inner most loop they occur in
66  std::map<BasicBlock*, Loop*> BBMap;
67  std::vector<Loop*> TopLevelLoops;
68public:
69  static AnalysisID ID;            // LoopInfo Analysis ID
70
71  // LoopInfo ctor - Calculate the natural loop information for a CFG
72  LoopInfo(AnalysisID id) { assert(id == ID); }
73  ~LoopInfo() { releaseMemory(); }
74
75  const std::vector<Loop*> &getTopLevelLoops() const { return TopLevelLoops; }
76
77  // getLoopFor - Return the inner most loop that BB lives in.  If a basic block
78  // is in no loop (for example the entry node), null is returned.
79  //
80  const Loop *getLoopFor(BasicBlock *BB) const {
81    std::map<BasicBlock *, Loop*>::const_iterator I = BBMap.find(BB);
82    return I != BBMap.end() ? I->second : 0;
83  }
84  inline const Loop *operator[](BasicBlock *BB) const {
85    return getLoopFor(BB);
86  }
87
88  // getLoopDepth - Return the loop nesting level of the specified block...
89  unsigned getLoopDepth(BasicBlock *BB) const {
90    const Loop *L = getLoopFor(BB);
91    return L ? L->getLoopDepth() : 0;
92  }
93
94#if 0
95  // isLoopHeader - True if the block is a loop header node
96  bool isLoopHeader(BasicBlock *BB) const {
97    return getLoopFor(BB)->getHeader() == BB;
98  }
99  // isLoopEnd - True if block jumps to loop entry
100  bool isLoopEnd(BasicBlock *BB) const;
101  // isLoopExit - True if block is the loop exit
102  bool isLoopExit(BasicBlock *BB) const;
103#endif
104
105  // runOnFunction - Pass framework implementation
106  virtual bool runOnFunction(Function *F);
107
108  virtual void releaseMemory();
109
110  // getAnalysisUsage - Provide loop info, require dominator set
111  //
112  virtual void getAnalysisUsage(AnalysisUsage &AU) const;
113
114private:
115  void Calculate(const DominatorSet &DS);
116  Loop *ConsiderForLoop(BasicBlock *BB, const DominatorSet &DS);
117};
118
119#endif
120