LLVM  9.0.0svn
MachineLoopInfo.h
Go to the documentation of this file.
1 //===- llvm/CodeGen/MachineLoopInfo.h - Natural Loop Calculator -*- C++ -*-===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file defines the MachineLoopInfo class that is used to identify natural
10 // loops and determine the loop depth of various nodes of the CFG. Note that
11 // natural loops may actually be several loops that share the same header node.
12 //
13 // This analysis calculates the nesting structure of loops in a function. For
14 // each natural loop identified, this analysis identifies natural loops
15 // contained entirely within the loop and the basic blocks the make up the loop.
16 //
17 // It can calculate on the fly various bits of information, for example:
18 //
19 // * whether there is a preheader for the loop
20 // * the number of back edges to the header
21 // * whether or not a particular block branches out of the loop
22 // * the successor blocks of the loop
23 // * the loop depth
24 // * the trip count
25 // * etc...
26 //
27 //===----------------------------------------------------------------------===//
28 
29 #ifndef LLVM_CODEGEN_MACHINELOOPINFO_H
30 #define LLVM_CODEGEN_MACHINELOOPINFO_H
31 
32 #include "llvm/Analysis/LoopInfo.h"
35 #include "llvm/IR/DebugLoc.h"
36 #include "llvm/Pass.h"
37 
38 namespace llvm {
39 
40 // Implementation in LoopInfoImpl.h
41 class MachineLoop;
42 extern template class LoopBase<MachineBasicBlock, MachineLoop>;
43 
45 public:
46  /// Return the "top" block in the loop, which is the first block in the linear
47  /// layout, ignoring any parts of the loop not contiguous with the part that
48  /// contains the header.
49  MachineBasicBlock *getTopBlock();
50 
51  /// Return the "bottom" block in the loop, which is the last block in the
52  /// linear layout, ignoring any parts of the loop not contiguous with the part
53  /// that contains the header.
54  MachineBasicBlock *getBottomBlock();
55 
56  /// Find the block that contains the loop control variable and the
57  /// loop test. This will return the latch block if it's one of the exiting
58  /// blocks. Otherwise, return the exiting block. Return 'null' when
59  /// multiple exiting blocks are present.
60  MachineBasicBlock *findLoopControlBlock();
61 
62  /// Return the debug location of the start of this loop.
63  /// This looks for a BB terminating instruction with a known debug
64  /// location by looking at the preheader and header blocks. If it
65  /// cannot find a terminating instruction with location information,
66  /// it returns an unknown location.
67  DebugLoc getStartLoc() const;
68 
69  void dump() const;
70 
71 private:
73 
74  explicit MachineLoop(MachineBasicBlock *MBB)
76 
77  MachineLoop() = default;
78 };
79 
80 // Implementation in LoopInfoImpl.h
82 
85 
87 
88 public:
89  static char ID; // Pass identification, replacement for typeid
90 
93  }
94  MachineLoopInfo(const MachineLoopInfo &) = delete;
95  MachineLoopInfo &operator=(const MachineLoopInfo &) = delete;
96 
98 
99  /// Find the block that either is the loop preheader, or could
100  /// speculatively be used as the preheader. This is e.g. useful to place
101  /// loop setup code. Code that cannot be speculated should not be placed
102  /// here. SpeculativePreheader is controlling whether it also tries to
103  /// find the speculative preheader if the regular preheader is not present.
104  MachineBasicBlock *findLoopPreheader(MachineLoop *L,
105  bool SpeculativePreheader = false) const;
106 
107  /// The iterator interface to the top-level loops in the current function.
109  inline iterator begin() const { return LI.begin(); }
110  inline iterator end() const { return LI.end(); }
111  bool empty() const { return LI.empty(); }
112 
113  /// Return the innermost loop that BB lives in. If a basic block is in no loop
114  /// (for example the entry node), null is returned.
115  inline MachineLoop *getLoopFor(const MachineBasicBlock *BB) const {
116  return LI.getLoopFor(BB);
117  }
118 
119  /// Same as getLoopFor.
120  inline const MachineLoop *operator[](const MachineBasicBlock *BB) const {
121  return LI.getLoopFor(BB);
122  }
123 
124  /// Return the loop nesting level of the specified block.
125  inline unsigned getLoopDepth(const MachineBasicBlock *BB) const {
126  return LI.getLoopDepth(BB);
127  }
128 
129  /// True if the block is a loop header node.
130  inline bool isLoopHeader(const MachineBasicBlock *BB) const {
131  return LI.isLoopHeader(BB);
132  }
133 
134  /// Calculate the natural loop information.
135  bool runOnMachineFunction(MachineFunction &F) override;
136 
137  void releaseMemory() override { LI.releaseMemory(); }
138 
139  void getAnalysisUsage(AnalysisUsage &AU) const override;
140 
141  /// This removes the specified top-level loop from this loop info object. The
142  /// loop is not deleted, as it will presumably be inserted into another loop.
143  inline MachineLoop *removeLoop(iterator I) { return LI.removeLoop(I); }
144 
145  /// Change the top-level loop that contains BB to the specified loop. This
146  /// should be used by transformations that restructure the loop hierarchy
147  /// tree.
149  LI.changeLoopFor(BB, L);
150  }
151 
152  /// Replace the specified loop in the top-level loops list with the indicated
153  /// loop.
154  inline void changeTopLevelLoop(MachineLoop *OldLoop, MachineLoop *NewLoop) {
155  LI.changeTopLevelLoop(OldLoop, NewLoop);
156  }
157 
158  /// This adds the specified loop to the collection of top-level loops.
159  inline void addTopLevelLoop(MachineLoop *New) {
160  LI.addTopLevelLoop(New);
161  }
162 
163  /// This method completely removes BB from all data structures, including all
164  /// of the Loop objects it is nested in and our mapping from
165  /// MachineBasicBlocks to loops.
167  LI.removeBlock(BB);
168  }
169 };
170 
171 // Allow clients to walk the list of nested loops...
173  using NodeRef = const MachineLoop *;
175 
176  static NodeRef getEntryNode(const MachineLoop *L) { return L; }
177  static ChildIteratorType child_begin(NodeRef N) { return N->begin(); }
178  static ChildIteratorType child_end(NodeRef N) { return N->end(); }
179 };
180 
181 template <> struct GraphTraits<MachineLoop*> {
182  using NodeRef = MachineLoop *;
184 
185  static NodeRef getEntryNode(MachineLoop *L) { return L; }
186  static ChildIteratorType child_begin(NodeRef N) { return N->begin(); }
187  static ChildIteratorType child_end(NodeRef N) { return N->end(); }
188 };
189 
190 } // end namespace llvm
191 
192 #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:676
This class represents lattice values for constants.
Definition: AllocatorList.h:23
unsigned getLoopDepth(const BlockT *BB) const
Return the loop nesting level of the specified block.
Definition: LoopInfo.h:704
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:33
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:697
std::vector< LoopT * >::const_iterator iterator
iterator/begin/end - The interface to the top-level loops in the current function.
Definition: LoopInfo.h:669
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:748
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:673
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:718
iterator begin() const
Definition: LoopInfo.h:672
static NodeRef getEntryNode(const MachineLoop *L)
iterator end() const
bool isLoopHeader(const BlockT *BB) const
Definition: LoopInfo.h:710
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:739
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:729
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:652
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:756
This class builds and contains all of the top-level loop structures in the specified function...
Definition: LoopInfo.h:62
LoopInfoBase< MachineBasicBlock, MachineLoop > & getBase()