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