LoopInfo.h revision 697954c15da58bd8b186dbafdedd8b06db770201 
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 <vector>
14#include <map>
15#include <set>
16class BasicBlock;
17
18namespace cfg {
19  class DominatorSet;
20  class LoopInfo;
21
22//===----------------------------------------------------------------------===//
23// Loop class - Instances of this class are used to represent loops that are
24// detected in the flow graph
25//
26class Loop {
27  Loop *ParentLoop;
28  std::vector<const BasicBlock *> Blocks; // First entry is the header node
29  std::vector<Loop*> SubLoops;       // Loops contained entirely within this one
30  unsigned LoopDepth;                // Nesting depth of this loop
31
32  Loop(const Loop &);                  // DO NOT IMPLEMENT
33  const Loop &operator=(const Loop &); // DO NOT IMPLEMENT
34public:
35
36  inline unsigned getLoopDepth() const { return LoopDepth; }
37  inline const BasicBlock *getHeader() const { return Blocks.front(); }
38
39  // contains - Return true of the specified basic block is in this loop
40  bool contains(const BasicBlock *BB) const;
41
42  // getSubLoops - Return the loops contained entirely within this loop
43  inline const std::vector<Loop*> &getSubLoops() const { return SubLoops; }
44  inline const std::vector<const BasicBlock*> &getBlocks() const {
45    return Blocks;
46  }
47
48private:
49  friend class LoopInfo;
50  inline Loop(const BasicBlock *BB) { Blocks.push_back(BB); LoopDepth = 0; }
51
52  void setLoopDepth(unsigned Level) {
53    LoopDepth = Level;
54    for (unsigned i = 0; i < SubLoops.size(); ++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 method.
64//
65class LoopInfo {
66  // BBMap - Mapping of basic blocks to the inner most loop they occur in
67  std::map<const BasicBlock *, Loop*> BBMap;
68  std::vector<Loop*> TopLevelLoops;
69public:
70  // LoopInfo ctor - Calculate the natural loop information for a CFG
71  LoopInfo(const DominatorSet &DS);
72
73  const std::vector<Loop*> &getTopLevelLoops() const { return TopLevelLoops; }
74
75  // getLoopFor - Return the inner most loop that BB lives in.  If a basic block
76  // is in no loop (for example the entry node), null is returned.
77  //
78  const Loop *getLoopFor(const BasicBlock *BB) const {
79    std::map<const BasicBlock *, Loop*>::const_iterator I = BBMap.find(BB);
80    return I != BBMap.end() ? I->second : 0;
81  }
82  inline const Loop *operator[](const BasicBlock *BB) const {
83    return getLoopFor(BB);
84  }
85
86  // getLoopDepth - Return the loop nesting level of the specified block...
87  unsigned getLoopDepth(const BasicBlock *BB) const {
88    const Loop *L = getLoopFor(BB);
89    return L ? L->getLoopDepth() : 0;
90  }
91
92#if 0
93  // isLoopHeader - True if the block is a loop header node
94  bool isLoopHeader(const BasicBlock *BB) const {
95    return getLoopFor(BB)->getHeader() == BB;
96  }
97  // isLoopEnd - True if block jumps to loop entry
98  bool isLoopEnd(const BasicBlock *BB) const;
99  // isLoopExit - True if block is the loop exit
100  bool isLoopExit(const BasicBlock *BB) const;
101#endif
102
103private:
104  Loop *ConsiderForLoop(const BasicBlock *BB, const DominatorSet &DS);
105};
106
107}  // End namespace cfg
108
109#endif
110