LLVM  16.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 
37 namespace llvm {
38 
39 class MachineDominatorTree;
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  /// Returns true if the instruction is loop invariant.
70  /// I.e., all virtual register operands are defined outside of the loop,
71  /// physical registers aren't accessed explicitly, and there are no side
72  /// effects that aren't captured by the operands or other flags.
73  bool isLoopInvariant(MachineInstr &I) const;
74 
75  void dump() const;
76 
77 private:
79 
82 
83  MachineLoop() = default;
84 };
85 
86 // Implementation in LoopInfoImpl.h
87 extern template class LoopInfoBase<MachineBasicBlock, MachineLoop>;
88 
91 
93 
94 public:
95  static char ID; // Pass identification, replacement for typeid
96 
100  calculate(MDT);
101  }
102  MachineLoopInfo(const MachineLoopInfo &) = delete;
103  MachineLoopInfo &operator=(const MachineLoopInfo &) = delete;
104 
106 
107  /// Find the block that either is the loop preheader, or could
108  /// speculatively be used as the preheader. This is e.g. useful to place
109  /// loop setup code. Code that cannot be speculated should not be placed
110  /// here. SpeculativePreheader is controlling whether it also tries to
111  /// find the speculative preheader if the regular preheader is not present.
112  /// With FindMultiLoopPreheader = false, nullptr will be returned if the found
113  /// preheader is the preheader of multiple loops.
115  findLoopPreheader(MachineLoop *L, bool SpeculativePreheader = false,
116  bool FindMultiLoopPreheader = false) const;
117 
118  /// The iterator interface to the top-level loops in the current function.
120  inline iterator begin() const { return LI.begin(); }
121  inline iterator end() const { return LI.end(); }
122  bool empty() const { return LI.empty(); }
123 
124  /// Return the innermost loop that BB lives in. If a basic block is in no loop
125  /// (for example the entry node), null is returned.
126  inline MachineLoop *getLoopFor(const MachineBasicBlock *BB) const {
127  return LI.getLoopFor(BB);
128  }
129 
130  /// Same as getLoopFor.
131  inline const MachineLoop *operator[](const MachineBasicBlock *BB) const {
132  return LI.getLoopFor(BB);
133  }
134 
135  /// Return the loop nesting level of the specified block.
136  inline unsigned getLoopDepth(const MachineBasicBlock *BB) const {
137  return LI.getLoopDepth(BB);
138  }
139 
140  /// True if the block is a loop header node.
141  inline bool isLoopHeader(const MachineBasicBlock *BB) const {
142  return LI.isLoopHeader(BB);
143  }
144 
145  /// Calculate the natural loop information.
146  bool runOnMachineFunction(MachineFunction &F) override;
147  void calculate(MachineDominatorTree &MDT);
148 
149  void releaseMemory() override { LI.releaseMemory(); }
150 
151  void getAnalysisUsage(AnalysisUsage &AU) const override;
152 
153  /// This removes the specified top-level loop from this loop info object. The
154  /// loop is not deleted, as it will presumably be inserted into another loop.
155  inline MachineLoop *removeLoop(iterator I) { return LI.removeLoop(I); }
156 
157  /// Change the top-level loop that contains BB to the specified loop. This
158  /// should be used by transformations that restructure the loop hierarchy
159  /// tree.
161  LI.changeLoopFor(BB, L);
162  }
163 
164  /// Replace the specified loop in the top-level loops list with the indicated
165  /// loop.
166  inline void changeTopLevelLoop(MachineLoop *OldLoop, MachineLoop *NewLoop) {
167  LI.changeTopLevelLoop(OldLoop, NewLoop);
168  }
169 
170  /// This adds the specified loop to the collection of top-level loops.
171  inline void addTopLevelLoop(MachineLoop *New) {
172  LI.addTopLevelLoop(New);
173  }
174 
175  /// This method completely removes BB from all data structures, including all
176  /// of the Loop objects it is nested in and our mapping from
177  /// MachineBasicBlocks to loops.
179  LI.removeBlock(BB);
180  }
181 };
182 
183 // Allow clients to walk the list of nested loops...
185  using NodeRef = const MachineLoop *;
187 
188  static NodeRef getEntryNode(const MachineLoop *L) { return L; }
189  static ChildIteratorType child_begin(NodeRef N) { return N->begin(); }
190  static ChildIteratorType child_end(NodeRef N) { return N->end(); }
191 };
192 
193 template <> struct GraphTraits<MachineLoop*> {
194  using NodeRef = MachineLoop *;
196 
197  static NodeRef getEntryNode(MachineLoop *L) { return L; }
198  static ChildIteratorType child_begin(NodeRef N) { return N->begin(); }
199  static ChildIteratorType child_end(NodeRef N) { return N->end(); }
200 };
201 
202 } // end namespace llvm
203 
204 #endif // LLVM_CODEGEN_MACHINELOOPINFO_H
llvm::GraphTraits< const MachineLoop * >::child_begin
static ChildIteratorType child_begin(NodeRef N)
Definition: MachineLoopInfo.h:189
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
llvm::MachineLoopInfo::getLoopFor
MachineLoop * getLoopFor(const MachineBasicBlock *BB) const
Return the innermost loop that BB lives in.
Definition: MachineLoopInfo.h:126
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:166
llvm::MachineLoopInfo::iterator
LoopInfoBase< MachineBasicBlock, MachineLoop >::iterator iterator
The iterator interface to the top-level loops in the current function.
Definition: MachineLoopInfo.h:119
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:1027
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:1054
llvm::dump
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
Definition: SparseBitVector.h:877
llvm::GraphTraits< const MachineLoop * >
Definition: MachineLoopInfo.h:184
F
#define F(x, y, z)
Definition: MD5.cpp:55
llvm::MachineLoopInfo
Definition: MachineLoopInfo.h:89
llvm::MachineLoopInfo::changeLoopFor
void changeLoopFor(MachineBasicBlock *BB, MachineLoop *L)
Change the top-level loop that contains BB to the specified loop.
Definition: MachineLoopInfo.h:160
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:149
llvm::MachineLoopInfo::end
iterator end() const
Definition: MachineLoopInfo.h:121
llvm::GraphTraits< MachineLoop * >::child_begin
static ChildIteratorType child_begin(NodeRef N)
Definition: MachineLoopInfo.h:198
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:1046
llvm::MachineLoopInfo::ID
static char ID
Definition: MachineLoopInfo.h:95
DebugLoc.h
llvm::MachineLoopInfo::empty
bool empty() const
Definition: MachineLoopInfo.h:122
llvm::CallingConv::ID
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
llvm::MachineLoopInfo::isLoopHeader
bool isLoopHeader(const MachineBasicBlock *BB) const
True if the block is a loop header node.
Definition: MachineLoopInfo.h:141
llvm::MachineBasicBlock
Definition: MachineBasicBlock.h:94
LoopInfo.h
llvm::MachineLoopInfo::MachineLoopInfo
MachineLoopInfo(MachineDominatorTree &MDT)
Definition: MachineLoopInfo.h:98
llvm::MachineLoop
Definition: MachineLoopInfo.h:44
llvm::MachineInstr
Representation of each machine instruction.
Definition: MachineInstr.h:66
llvm::MachineLoopInfo::removeLoop
MachineLoop * removeLoop(iterator I)
This removes the specified top-level loop from this loop info object.
Definition: MachineLoopInfo.h:155
llvm::LoopInfoBase::getLoopFor
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
Definition: LoopInfo.h:989
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::MachineLoopInfo::addTopLevelLoop
void addTopLevelLoop(MachineLoop *New)
This adds the specified loop to the collection of top-level loops.
Definition: MachineLoopInfo.h:171
MachineFunctionPass.h
llvm::GraphTraits< const MachineLoop * >::ChildIteratorType
MachineLoopInfo::iterator ChildIteratorType
Definition: MachineLoopInfo.h:186
llvm::LoopInfoBase::begin
iterator begin() const
Definition: LoopInfo.h:964
llvm::MachineFunction
Definition: MachineFunction.h:257
llvm::LoopInfoBase::getLoopDepth
unsigned getLoopDepth(const BlockT *BB) const
Return the loop nesting level of the specified block.
Definition: LoopInfo.h:996
llvm::LoopInfoBase::removeLoop
LoopT * removeLoop(iterator I)
This removes the specified top-level loop from this loop info object.
Definition: LoopInfo.h:1016
llvm::GraphTraits< MachineLoop * >::ChildIteratorType
MachineLoopInfo::iterator ChildIteratorType
Definition: MachineLoopInfo.h:195
MBB
MachineBasicBlock & MBB
Definition: AArch64SLSHardening.cpp:74
llvm::LoopInfoBase::isLoopHeader
bool isLoopHeader(const BlockT *BB) const
Definition: LoopInfo.h:1002
llvm::GraphTraits< MachineLoop * >::child_end
static ChildIteratorType child_end(NodeRef N)
Definition: MachineLoopInfo.h:199
llvm::GraphTraits< const MachineLoop * >::child_end
static ChildIteratorType child_end(NodeRef N)
Definition: MachineLoopInfo.h:190
llvm::GraphTraits< MachineLoop * >
Definition: MachineLoopInfo.h:193
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:197
llvm::GraphTraits< const MachineLoop * >::getEntryNode
static NodeRef getEntryNode(const MachineLoop *L)
Definition: MachineLoopInfo.h:188
llvm::MachineLoopInfo::getLoopDepth
unsigned getLoopDepth(const MachineBasicBlock *BB) const
Return the loop nesting level of the specified block.
Definition: MachineLoopInfo.h:136
llvm::MachineLoopInfo::getBase
LoopInfoBase< MachineBasicBlock, MachineLoop > & getBase()
Definition: MachineLoopInfo.h:105
llvm::LoopInfoBase::end
iterator end() const
Definition: LoopInfo.h:965
llvm::MachineLoopInfo::begin
iterator begin() const
Definition: MachineLoopInfo.h:120
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:1037
llvm::LoopInfoBase::releaseMemory
void releaseMemory()
Definition: LoopInfo.h:944
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:178
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:961
llvm::LoopInfoBase::empty
bool empty() const
Definition: LoopInfo.h:968
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:51
llvm::MachineLoopInfo::operator[]
const MachineLoop * operator[](const MachineBasicBlock *BB) const
Same as getLoopFor.
Definition: MachineLoopInfo.h:131