LLVM  6.0.0svn
MachineLoopInfo.h
Go to the documentation of this file.
1 //===- llvm/CodeGen/MachineLoopInfo.h - Natural Loop Calculator -*- C++ -*-===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file defines the MachineLoopInfo class that is used to identify natural
11 // loops and determine the loop depth of various nodes of the CFG. Note that
12 // natural loops may actually be several loops that share the same header node.
13 //
14 // This analysis calculates the nesting structure of loops in a function. For
15 // each natural loop identified, this analysis identifies natural loops
16 // contained entirely within the loop and the basic blocks the make up the loop.
17 //
18 // It can calculate on the fly various bits of information, for example:
19 //
20 // * whether there is a preheader for the loop
21 // * the number of back edges to the header
22 // * whether or not a particular block branches out of the loop
23 // * the successor blocks of the loop
24 // * the loop depth
25 // * the trip count
26 // * etc...
27 //
28 //===----------------------------------------------------------------------===//
29 
30 #ifndef LLVM_CODEGEN_MACHINELOOPINFO_H
31 #define LLVM_CODEGEN_MACHINELOOPINFO_H
32 
33 #include "llvm/Analysis/LoopInfo.h"
36 #include "llvm/IR/DebugLoc.h"
37 #include "llvm/Pass.h"
38 
39 namespace llvm {
40 
41 // Implementation in LoopInfoImpl.h
42 class MachineLoop;
43 extern template class LoopBase<MachineBasicBlock, MachineLoop>;
44 
46 public:
47  /// Return the "top" block in the loop, which is the first block in the linear
48  /// layout, ignoring any parts of the loop not contiguous with the part that
49  /// contains the header.
50  MachineBasicBlock *getTopBlock();
51 
52  /// Return the "bottom" block in the loop, which is the last block in the
53  /// linear layout, ignoring any parts of the loop not contiguous with the part
54  /// that contains the header.
55  MachineBasicBlock *getBottomBlock();
56 
57  /// \brief Find the block that contains the loop control variable and the
58  /// loop test. This will return the latch block if it's one of the exiting
59  /// blocks. Otherwise, return the exiting block. Return 'null' when
60  /// multiple exiting blocks are present.
61  MachineBasicBlock *findLoopControlBlock();
62 
63  /// Return the debug location of the start of this loop.
64  /// This looks for a BB terminating instruction with a known debug
65  /// location by looking at the preheader and header blocks. If it
66  /// cannot find a terminating instruction with location information,
67  /// it returns an unknown location.
68  DebugLoc getStartLoc() const;
69 
70  void dump() const;
71 
72 private:
74 
75  explicit MachineLoop(MachineBasicBlock *MBB)
77 
78  MachineLoop() = default;
79 };
80 
81 // Implementation in LoopInfoImpl.h
83 
86 
88 
89 public:
90  static char ID; // Pass identification, replacement for typeid
91 
94  }
95  MachineLoopInfo(const MachineLoopInfo &) = delete;
96  MachineLoopInfo &operator=(const MachineLoopInfo &) = delete;
97 
99 
100  /// \brief Find the block that either is the loop preheader, or could
101  /// speculatively be used as the preheader. This is e.g. useful to place
102  /// loop setup code. Code that cannot be speculated should not be placed
103  /// here. SpeculativePreheader is controlling whether it also tries to
104  /// find the speculative preheader if the regular preheader is not present.
105  MachineBasicBlock *findLoopPreheader(MachineLoop *L,
106  bool SpeculativePreheader = false) const;
107 
108  /// The iterator interface to the top-level loops in the current function.
110  inline iterator begin() const { return LI.begin(); }
111  inline iterator end() const { return LI.end(); }
112  bool empty() const { return LI.empty(); }
113 
114  /// Return the innermost loop that BB lives in. If a basic block is in no loop
115  /// (for example the entry node), null is returned.
116  inline MachineLoop *getLoopFor(const MachineBasicBlock *BB) const {
117  return LI.getLoopFor(BB);
118  }
119 
120  /// Same as getLoopFor.
121  inline const MachineLoop *operator[](const MachineBasicBlock *BB) const {
122  return LI.getLoopFor(BB);
123  }
124 
125  /// Return the loop nesting level of the specified block.
126  inline unsigned getLoopDepth(const MachineBasicBlock *BB) const {
127  return LI.getLoopDepth(BB);
128  }
129 
130  /// True if the block is a loop header node.
131  inline bool isLoopHeader(const MachineBasicBlock *BB) const {
132  return LI.isLoopHeader(BB);
133  }
134 
135  /// Calculate the natural loop information.
136  bool runOnMachineFunction(MachineFunction &F) override;
137 
138  void releaseMemory() override { LI.releaseMemory(); }
139 
140  void getAnalysisUsage(AnalysisUsage &AU) const override;
141 
142  /// This removes the specified top-level loop from this loop info object. The
143  /// loop is not deleted, as it will presumably be inserted into another loop.
144  inline MachineLoop *removeLoop(iterator I) { return LI.removeLoop(I); }
145 
146  /// Change the top-level loop that contains BB to the specified loop. This
147  /// should be used by transformations that restructure the loop hierarchy
148  /// tree.
150  LI.changeLoopFor(BB, L);
151  }
152 
153  /// Replace the specified loop in the top-level loops list with the indicated
154  /// loop.
155  inline void changeTopLevelLoop(MachineLoop *OldLoop, MachineLoop *NewLoop) {
156  LI.changeTopLevelLoop(OldLoop, NewLoop);
157  }
158 
159  /// This adds the specified loop to the collection of top-level loops.
160  inline void addTopLevelLoop(MachineLoop *New) {
161  LI.addTopLevelLoop(New);
162  }
163 
164  /// This method completely removes BB from all data structures, including all
165  /// of the Loop objects it is nested in and our mapping from
166  /// MachineBasicBlocks to loops.
168  LI.removeBlock(BB);
169  }
170 };
171 
172 // Allow clients to walk the list of nested loops...
174  using NodeRef = const MachineLoop *;
176 
177  static NodeRef getEntryNode(const MachineLoop *L) { return L; }
178  static ChildIteratorType child_begin(NodeRef N) { return N->begin(); }
179  static ChildIteratorType child_end(NodeRef N) { return N->end(); }
180 };
181 
182 template <> struct GraphTraits<MachineLoop*> {
183  using NodeRef = MachineLoop *;
185 
186  static NodeRef getEntryNode(MachineLoop *L) { return L; }
187  static ChildIteratorType child_begin(NodeRef N) { return N->begin(); }
188  static ChildIteratorType child_end(NodeRef N) { return N->end(); }
189 };
190 
191 } // end namespace llvm
192 
193 #endif // LLVM_CODEGEN_MACHINELOOPINFO_H
static NodeRef getEntryNode(MachineLoop *L)
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
bool empty() const
Definition: LoopInfo.h:657
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
unsigned getLoopDepth(const BlockT *BB) const
Return the loop nesting level of the specified block.
Definition: LoopInfo.h:685
void addTopLevelLoop(MachineLoop *New)
This adds the specified loop to the collection of top-level loops.
unsigned getLoopDepth(const MachineBasicBlock *BB) const
Return the loop nesting level of the specified block.
A debug info location.
Definition: DebugLoc.h:34
F(f)
void initializeMachineLoopInfoPass(PassRegistry &)
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
Definition: LoopInfo.h:678
std::vector< LoopT * >::const_iterator iterator
iterator/begin/end - The interface to the top-level loops in the current function.
Definition: LoopInfo.h:650
void removeBlock(MachineBasicBlock *BB)
This method completely removes BB from all data structures, including all of the Loop objects it is n...
static ChildIteratorType child_begin(NodeRef N)
void addTopLevelLoop(LoopT *New)
This adds the specified loop to the collection of top-level loops.
Definition: LoopInfo.h:729
void changeTopLevelLoop(MachineLoop *OldLoop, MachineLoop *NewLoop)
Replace the specified loop in the top-level loops list with the indicated loop.
iterator begin() const
void releaseMemory() override
releaseMemory() - This member can be implemented by a pass if it wants to be able to release its memo...
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
MachineLoopInfo::iterator ChildIteratorType
iterator end() const
Definition: LoopInfo.h:654
Represent the analysis usage information of a pass.
const MachineLoop * operator[](const MachineBasicBlock *BB) const
Same as getLoopFor.
static ChildIteratorType child_begin(NodeRef N)
iterator begin() const
Definition: LoopInfo.h:142
static ChildIteratorType child_end(NodeRef N)
LoopT * removeLoop(iterator I)
This removes the specified top-level loop from this loop info object.
Definition: LoopInfo.h:699
iterator begin() const
Definition: LoopInfo.h:653
static NodeRef getEntryNode(const MachineLoop *L)
iterator end() const
bool isLoopHeader(const BlockT *BB) const
Definition: LoopInfo.h:691
MachineLoop * removeLoop(iterator I)
This removes the specified top-level loop from this loop info object.
#define I(x, y, z)
Definition: MD5.cpp:58
#define N
LoopInfoBase< MachineBasicBlock, MachineLoop >::iterator iterator
The iterator interface to the top-level loops in the current function.
void changeLoopFor(MachineBasicBlock *BB, MachineLoop *L)
Change the top-level loop that contains BB to the specified loop.
void changeTopLevelLoop(LoopT *OldLoop, LoopT *NewLoop)
Replace the specified loop in the top-level loops list with the indicated loop.
Definition: LoopInfo.h:720
MachineLoopInfo::iterator ChildIteratorType
iterator end() const
Definition: LoopInfo.h:143
static ChildIteratorType child_end(NodeRef N)
void changeLoopFor(BlockT *BB, LoopT *L)
Change the top-level loop that contains BB to the specified loop.
Definition: LoopInfo.h:710
bool isLoopHeader(const MachineBasicBlock *BB) const
True if the block is a loop header node.
MachineLoop * getLoopFor(const MachineBasicBlock *BB) const
Return the innermost loop that BB lives in.
void releaseMemory()
Definition: LoopInfo.h:633
void removeBlock(BlockT *BB)
This method completely removes BB from all data structures, including all of the Loop objects it is n...
Definition: LoopInfo.h:737
This class builds and contains all of the top-level loop structures in the specified function...
Definition: LoopInfo.h:62
LoopInfoBase< MachineBasicBlock, MachineLoop > & getBase()