LLVM  14.0.0git
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 class MachineDominatorTree;
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  /// 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  /// Returns true if the instruction is loop invariant.
71  /// I.e., all virtual register operands are defined outside of the loop,
72  /// physical registers aren't accessed explicitly, and there are no side
73  /// effects that aren't captured by the operands or other flags.
74  bool isLoopInvariant(MachineInstr &I) const;
75 
76  void dump() const;
77 
78 private:
80 
83 
84  MachineLoop() = default;
85 };
86 
87 // Implementation in LoopInfoImpl.h
88 extern template class LoopInfoBase<MachineBasicBlock, MachineLoop>;
89 
92 
94 
95 public:
96  static char ID; // Pass identification, replacement for typeid
97 
101  calculate(MDT);
102  }
103  MachineLoopInfo(const MachineLoopInfo &) = delete;
104  MachineLoopInfo &operator=(const MachineLoopInfo &) = delete;
105 
107 
108  /// Find the block that either is the loop preheader, or could
109  /// speculatively be used as the preheader. This is e.g. useful to place
110  /// loop setup code. Code that cannot be speculated should not be placed
111  /// here. SpeculativePreheader is controlling whether it also tries to
112  /// find the speculative preheader if the regular preheader is not present.
113  /// With FindMultiLoopPreheader = false, nullptr will be returned if the found
114  /// preheader is the preheader of multiple loops.
116  findLoopPreheader(MachineLoop *L, bool SpeculativePreheader = false,
117  bool FindMultiLoopPreheader = false) const;
118 
119  /// The iterator interface to the top-level loops in the current function.
121  inline iterator begin() const { return LI.begin(); }
122  inline iterator end() const { return LI.end(); }
123  bool empty() const { return LI.empty(); }
124 
125  /// Return the innermost loop that BB lives in. If a basic block is in no loop
126  /// (for example the entry node), null is returned.
127  inline MachineLoop *getLoopFor(const MachineBasicBlock *BB) const {
128  return LI.getLoopFor(BB);
129  }
130 
131  /// Same as getLoopFor.
132  inline const MachineLoop *operator[](const MachineBasicBlock *BB) const {
133  return LI.getLoopFor(BB);
134  }
135 
136  /// Return the loop nesting level of the specified block.
137  inline unsigned getLoopDepth(const MachineBasicBlock *BB) const {
138  return LI.getLoopDepth(BB);
139  }
140 
141  /// True if the block is a loop header node.
142  inline bool isLoopHeader(const MachineBasicBlock *BB) const {
143  return LI.isLoopHeader(BB);
144  }
145 
146  /// Calculate the natural loop information.
147  bool runOnMachineFunction(MachineFunction &F) override;
148  void calculate(MachineDominatorTree &MDT);
149 
150  void releaseMemory() override { LI.releaseMemory(); }
151 
152  void getAnalysisUsage(AnalysisUsage &AU) const override;
153 
154  /// This removes the specified top-level loop from this loop info object. The
155  /// loop is not deleted, as it will presumably be inserted into another loop.
156  inline MachineLoop *removeLoop(iterator I) { return LI.removeLoop(I); }
157 
158  /// Change the top-level loop that contains BB to the specified loop. This
159  /// should be used by transformations that restructure the loop hierarchy
160  /// tree.
162  LI.changeLoopFor(BB, L);
163  }
164 
165  /// Replace the specified loop in the top-level loops list with the indicated
166  /// loop.
167  inline void changeTopLevelLoop(MachineLoop *OldLoop, MachineLoop *NewLoop) {
168  LI.changeTopLevelLoop(OldLoop, NewLoop);
169  }
170 
171  /// This adds the specified loop to the collection of top-level loops.
172  inline void addTopLevelLoop(MachineLoop *New) {
173  LI.addTopLevelLoop(New);
174  }
175 
176  /// This method completely removes BB from all data structures, including all
177  /// of the Loop objects it is nested in and our mapping from
178  /// MachineBasicBlocks to loops.
180  LI.removeBlock(BB);
181  }
182 };
183 
184 // Allow clients to walk the list of nested loops...
186  using NodeRef = const MachineLoop *;
188 
189  static NodeRef getEntryNode(const MachineLoop *L) { return L; }
190  static ChildIteratorType child_begin(NodeRef N) { return N->begin(); }
191  static ChildIteratorType child_end(NodeRef N) { return N->end(); }
192 };
193 
194 template <> struct GraphTraits<MachineLoop*> {
195  using NodeRef = MachineLoop *;
197 
198  static NodeRef getEntryNode(MachineLoop *L) { return L; }
199  static ChildIteratorType child_begin(NodeRef N) { return N->begin(); }
200  static ChildIteratorType child_end(NodeRef N) { return N->end(); }
201 };
202 
203 } // end namespace llvm
204 
205 #endif // LLVM_CODEGEN_MACHINELOOPINFO_H
llvm::GraphTraits< const MachineLoop * >::child_begin
static ChildIteratorType child_begin(NodeRef N)
Definition: MachineLoopInfo.h:190
llvm
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
llvm::MachineLoopInfo::getLoopFor
MachineLoop * getLoopFor(const MachineBasicBlock *BB) const
Return the innermost loop that BB lives in.
Definition: MachineLoopInfo.h:127
llvm::MachineLoopInfo::changeTopLevelLoop
void changeTopLevelLoop(MachineLoop *OldLoop, MachineLoop *NewLoop)
Replace the specified loop in the top-level loops list with the indicated loop.
Definition: MachineLoopInfo.h:167
llvm::MachineLoopInfo::iterator
LoopInfoBase< MachineBasicBlock, MachineLoop >::iterator iterator
The iterator interface to the top-level loops in the current function.
Definition: MachineLoopInfo.h:120
Pass.h
llvm::LoopBase< MachineBasicBlock, MachineLoop >
llvm::MachineFunctionPass
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
Definition: MachineFunctionPass.h:30
llvm::LoopInfoBase::changeLoopFor
void changeLoopFor(BlockT *BB, LoopT *L)
Change the top-level loop that contains BB to the specified loop.
Definition: LoopInfo.h:1005
MachineBasicBlock.h
llvm::LoopInfoBase::removeBlock
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:1032
llvm::dump
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
Definition: SparseBitVector.h:876
llvm::GraphTraits< const MachineLoop * >
Definition: MachineLoopInfo.h:185
F
#define F(x, y, z)
Definition: MD5.cpp:56
llvm::MachineLoopInfo
Definition: MachineLoopInfo.h:90
llvm::MachineLoopInfo::changeLoopFor
void changeLoopFor(MachineBasicBlock *BB, MachineLoop *L)
Change the top-level loop that contains BB to the specified loop.
Definition: MachineLoopInfo.h:161
llvm::MachineLoopInfo::releaseMemory
void releaseMemory() override
releaseMemory() - This member can be implemented by a pass if it wants to be able to release its memo...
Definition: MachineLoopInfo.h:150
llvm::MachineLoopInfo::end
iterator end() const
Definition: MachineLoopInfo.h:122
llvm::GraphTraits< MachineLoop * >::child_begin
static ChildIteratorType child_begin(NodeRef N)
Definition: MachineLoopInfo.h:199
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
llvm::LoopInfoBase::addTopLevelLoop
void addTopLevelLoop(LoopT *New)
This adds the specified loop to the collection of top-level loops.
Definition: LoopInfo.h:1024
llvm::MachineLoopInfo::ID
static char ID
Definition: MachineLoopInfo.h:96
DebugLoc.h
llvm::MachineLoopInfo::empty
bool empty() const
Definition: MachineLoopInfo.h:123
llvm::MachineLoopInfo::isLoopHeader
bool isLoopHeader(const MachineBasicBlock *BB) const
True if the block is a loop header node.
Definition: MachineLoopInfo.h:142
llvm::MachineBasicBlock
Definition: MachineBasicBlock.h:95
LoopInfo.h
llvm::MachineLoopInfo::MachineLoopInfo
MachineLoopInfo(MachineDominatorTree &MDT)
Definition: MachineLoopInfo.h:99
llvm::MachineLoop
Definition: MachineLoopInfo.h:45
llvm::MachineInstr
Representation of each machine instruction.
Definition: MachineInstr.h:64
llvm::MachineLoopInfo::removeLoop
MachineLoop * removeLoop(iterator I)
This removes the specified top-level loop from this loop info object.
Definition: MachineLoopInfo.h:156
llvm::LoopInfoBase::getLoopFor
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
Definition: LoopInfo.h:967
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::MachineLoopInfo::addTopLevelLoop
void addTopLevelLoop(MachineLoop *New)
This adds the specified loop to the collection of top-level loops.
Definition: MachineLoopInfo.h:172
MachineFunctionPass.h
llvm::GraphTraits< const MachineLoop * >::ChildIteratorType
MachineLoopInfo::iterator ChildIteratorType
Definition: MachineLoopInfo.h:187
llvm::LoopInfoBase::begin
iterator begin() const
Definition: LoopInfo.h:942
llvm::MachineFunction
Definition: MachineFunction.h:230
llvm::LoopInfoBase::getLoopDepth
unsigned getLoopDepth(const BlockT *BB) const
Return the loop nesting level of the specified block.
Definition: LoopInfo.h:974
llvm::LoopInfoBase::removeLoop
LoopT * removeLoop(iterator I)
This removes the specified top-level loop from this loop info object.
Definition: LoopInfo.h:994
llvm::GraphTraits< MachineLoop * >::ChildIteratorType
MachineLoopInfo::iterator ChildIteratorType
Definition: MachineLoopInfo.h:196
MBB
MachineBasicBlock & MBB
Definition: AArch64SLSHardening.cpp:74
llvm::LoopInfoBase::isLoopHeader
bool isLoopHeader(const BlockT *BB) const
Definition: LoopInfo.h:980
llvm::GraphTraits< MachineLoop * >::child_end
static ChildIteratorType child_end(NodeRef N)
Definition: MachineLoopInfo.h:200
llvm::GraphTraits< const MachineLoop * >::child_end
static ChildIteratorType child_end(NodeRef N)
Definition: MachineLoopInfo.h:191
llvm::GraphTraits< MachineLoop * >
Definition: MachineLoopInfo.h:194
llvm::LoopInfoBase
This class builds and contains all of the top-level loop structures in the specified function.
Definition: LoopInfo.h:66
llvm::GraphTraits< MachineLoop * >::getEntryNode
static NodeRef getEntryNode(MachineLoop *L)
Definition: MachineLoopInfo.h:198
llvm::GraphTraits< const MachineLoop * >::getEntryNode
static NodeRef getEntryNode(const MachineLoop *L)
Definition: MachineLoopInfo.h:189
llvm::MachineLoopInfo::getLoopDepth
unsigned getLoopDepth(const MachineBasicBlock *BB) const
Return the loop nesting level of the specified block.
Definition: MachineLoopInfo.h:137
llvm::MachineLoopInfo::getBase
LoopInfoBase< MachineBasicBlock, MachineLoop > & getBase()
Definition: MachineLoopInfo.h:106
llvm::LoopInfoBase::end
iterator end() const
Definition: LoopInfo.h:943
llvm::MachineLoopInfo::begin
iterator begin() const
Definition: MachineLoopInfo.h:121
llvm::LoopInfoBase::changeTopLevelLoop
void changeTopLevelLoop(LoopT *OldLoop, LoopT *NewLoop)
Replace the specified loop in the top-level loops list with the indicated loop.
Definition: LoopInfo.h:1015
llvm::LoopInfoBase::releaseMemory
void releaseMemory()
Definition: LoopInfo.h:922
llvm::MachineLoopInfo::removeBlock
void removeBlock(MachineBasicBlock *BB)
This method completely removes BB from all data structures, including all of the Loop objects it is n...
Definition: MachineLoopInfo.h:179
N
#define N
llvm::LoopInfoBase::iterator
std::vector< LoopT * >::const_iterator iterator
iterator/begin/end - The interface to the top-level loops in the current function.
Definition: LoopInfo.h:939
llvm::LoopInfoBase::empty
bool empty() const
Definition: LoopInfo.h:946
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
llvm::DebugLoc
A debug info location.
Definition: DebugLoc.h:33
llvm::MachineDominatorTree
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...
Definition: MachineDominators.h:45
llvm::MachineLoopInfo::operator[]
const MachineLoop * operator[](const MachineBasicBlock *BB) const
Same as getLoopFor.
Definition: MachineLoopInfo.h:132
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:37