LLVM  13.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  MachineBasicBlock *findLoopPreheader(MachineLoop *L,
114  bool SpeculativePreheader = false) const;
115 
116  /// The iterator interface to the top-level loops in the current function.
118  inline iterator begin() const { return LI.begin(); }
119  inline iterator end() const { return LI.end(); }
120  bool empty() const { return LI.empty(); }
121 
122  /// Return the innermost loop that BB lives in. If a basic block is in no loop
123  /// (for example the entry node), null is returned.
124  inline MachineLoop *getLoopFor(const MachineBasicBlock *BB) const {
125  return LI.getLoopFor(BB);
126  }
127 
128  /// Same as getLoopFor.
129  inline const MachineLoop *operator[](const MachineBasicBlock *BB) const {
130  return LI.getLoopFor(BB);
131  }
132 
133  /// Return the loop nesting level of the specified block.
134  inline unsigned getLoopDepth(const MachineBasicBlock *BB) const {
135  return LI.getLoopDepth(BB);
136  }
137 
138  /// True if the block is a loop header node.
139  inline bool isLoopHeader(const MachineBasicBlock *BB) const {
140  return LI.isLoopHeader(BB);
141  }
142 
143  /// Calculate the natural loop information.
144  bool runOnMachineFunction(MachineFunction &F) override;
145  void calculate(MachineDominatorTree &MDT);
146 
147  void releaseMemory() override { LI.releaseMemory(); }
148 
149  void getAnalysisUsage(AnalysisUsage &AU) const override;
150 
151  /// This removes the specified top-level loop from this loop info object. The
152  /// loop is not deleted, as it will presumably be inserted into another loop.
153  inline MachineLoop *removeLoop(iterator I) { return LI.removeLoop(I); }
154 
155  /// Change the top-level loop that contains BB to the specified loop. This
156  /// should be used by transformations that restructure the loop hierarchy
157  /// tree.
159  LI.changeLoopFor(BB, L);
160  }
161 
162  /// Replace the specified loop in the top-level loops list with the indicated
163  /// loop.
164  inline void changeTopLevelLoop(MachineLoop *OldLoop, MachineLoop *NewLoop) {
165  LI.changeTopLevelLoop(OldLoop, NewLoop);
166  }
167 
168  /// This adds the specified loop to the collection of top-level loops.
169  inline void addTopLevelLoop(MachineLoop *New) {
170  LI.addTopLevelLoop(New);
171  }
172 
173  /// This method completely removes BB from all data structures, including all
174  /// of the Loop objects it is nested in and our mapping from
175  /// MachineBasicBlocks to loops.
177  LI.removeBlock(BB);
178  }
179 };
180 
181 // Allow clients to walk the list of nested loops...
183  using NodeRef = const MachineLoop *;
185 
186  static NodeRef getEntryNode(const 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 template <> struct GraphTraits<MachineLoop*> {
192  using NodeRef = MachineLoop *;
194 
195  static NodeRef getEntryNode(MachineLoop *L) { return L; }
196  static ChildIteratorType child_begin(NodeRef N) { return N->begin(); }
197  static ChildIteratorType child_end(NodeRef N) { return N->end(); }
198 };
199 
200 } // end namespace llvm
201 
202 #endif // LLVM_CODEGEN_MACHINELOOPINFO_H
llvm::GraphTraits< const MachineLoop * >::child_begin
static ChildIteratorType child_begin(NodeRef N)
Definition: MachineLoopInfo.h:187
llvm
Definition: AllocatorList.h:23
llvm::MachineLoopInfo::getLoopFor
MachineLoop * getLoopFor(const MachineBasicBlock *BB) const
Return the innermost loop that BB lives in.
Definition: MachineLoopInfo.h:124
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:164
llvm::MachineLoopInfo::iterator
LoopInfoBase< MachineBasicBlock, MachineLoop >::iterator iterator
The iterator interface to the top-level loops in the current function.
Definition: MachineLoopInfo.h:117
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:1002
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:1029
llvm::dump
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
Definition: SparseBitVector.h:876
llvm::GraphTraits< const MachineLoop * >
Definition: MachineLoopInfo.h:182
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:158
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:147
llvm::MachineLoopInfo::end
iterator end() const
Definition: MachineLoopInfo.h:119
llvm::GraphTraits< MachineLoop * >::child_begin
static ChildIteratorType child_begin(NodeRef N)
Definition: MachineLoopInfo.h:196
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:1021
llvm::MachineLoopInfo::ID
static char ID
Definition: MachineLoopInfo.h:96
DebugLoc.h
llvm::MachineLoopInfo::empty
bool empty() const
Definition: MachineLoopInfo.h:120
llvm::MachineLoopInfo::isLoopHeader
bool isLoopHeader(const MachineBasicBlock *BB) const
True if the block is a loop header node.
Definition: MachineLoopInfo.h:139
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:153
llvm::LoopInfoBase::getLoopFor
LoopT * getLoopFor(const BlockT *BB) const
Return the inner most loop that BB lives in.
Definition: LoopInfo.h:964
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:169
MachineFunctionPass.h
llvm::GraphTraits< const MachineLoop * >::ChildIteratorType
MachineLoopInfo::iterator ChildIteratorType
Definition: MachineLoopInfo.h:184
llvm::LoopInfoBase::begin
iterator begin() const
Definition: LoopInfo.h:939
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:971
llvm::LoopInfoBase::removeLoop
LoopT * removeLoop(iterator I)
This removes the specified top-level loop from this loop info object.
Definition: LoopInfo.h:991
llvm::GraphTraits< MachineLoop * >::ChildIteratorType
MachineLoopInfo::iterator ChildIteratorType
Definition: MachineLoopInfo.h:193
MBB
MachineBasicBlock & MBB
Definition: AArch64SLSHardening.cpp:74
llvm::LoopInfoBase::isLoopHeader
bool isLoopHeader(const BlockT *BB) const
Definition: LoopInfo.h:977
llvm::GraphTraits< MachineLoop * >::child_end
static ChildIteratorType child_end(NodeRef N)
Definition: MachineLoopInfo.h:197
llvm::GraphTraits< const MachineLoop * >::child_end
static ChildIteratorType child_end(NodeRef N)
Definition: MachineLoopInfo.h:188
llvm::GraphTraits< MachineLoop * >
Definition: MachineLoopInfo.h:191
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:195
llvm::GraphTraits< const MachineLoop * >::getEntryNode
static NodeRef getEntryNode(const MachineLoop *L)
Definition: MachineLoopInfo.h:186
llvm::MachineLoopInfo::getLoopDepth
unsigned getLoopDepth(const MachineBasicBlock *BB) const
Return the loop nesting level of the specified block.
Definition: MachineLoopInfo.h:134
llvm::MachineLoopInfo::getBase
LoopInfoBase< MachineBasicBlock, MachineLoop > & getBase()
Definition: MachineLoopInfo.h:106
llvm::LoopInfoBase::end
iterator end() const
Definition: LoopInfo.h:940
llvm::MachineLoopInfo::begin
iterator begin() const
Definition: MachineLoopInfo.h:118
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:1012
llvm::LoopInfoBase::releaseMemory
void releaseMemory()
Definition: LoopInfo.h:919
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:176
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:936
llvm::LoopInfoBase::empty
bool empty() const
Definition: LoopInfo.h:943
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:129
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:38