LLVM 19.0.0git
MachineLoopInfo.cpp
Go to the documentation of this file.
1//===- MachineLoopInfo.cpp - Natural Loop Calculator ----------------------===//
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// the loops identified may actually be several natural loops that share the
12// same header node... not just a single natural loop.
13//
14//===----------------------------------------------------------------------===//
15
21#include "llvm/Config/llvm-config.h"
23#include "llvm/Pass.h"
24#include "llvm/PassRegistry.h"
26
27using namespace llvm;
28
29// Explicitly instantiate methods in LoopInfoImpl.h for MI-level Loops.
32
33char MachineLoopInfo::ID = 0;
36}
38 "Machine Natural Loop Construction", true, true)
42
44
45bool MachineLoopInfo::runOnMachineFunction(MachineFunction &) {
46 calculate(getAnalysis<MachineDominatorTree>());
47 return false;
48}
49
52 LI.analyze(MDT.getBase());
53}
54
56 AU.setPreservesAll();
59}
60
62 MachineBasicBlock *TopMBB = getHeader();
63 MachineFunction::iterator Begin = TopMBB->getParent()->begin();
64 if (TopMBB->getIterator() != Begin) {
65 MachineBasicBlock *PriorMBB = &*std::prev(TopMBB->getIterator());
66 while (contains(PriorMBB)) {
67 TopMBB = PriorMBB;
68 if (TopMBB->getIterator() == Begin)
69 break;
70 PriorMBB = &*std::prev(TopMBB->getIterator());
71 }
72 }
73 return TopMBB;
74}
75
77 MachineBasicBlock *BotMBB = getHeader();
79 if (BotMBB->getIterator() != std::prev(End)) {
80 MachineBasicBlock *NextMBB = &*std::next(BotMBB->getIterator());
81 while (contains(NextMBB)) {
82 BotMBB = NextMBB;
83 if (BotMBB == &*std::next(BotMBB->getIterator()))
84 break;
85 NextMBB = &*std::next(BotMBB->getIterator());
86 }
87 }
88 return BotMBB;
89}
90
92 if (MachineBasicBlock *Latch = getLoopLatch()) {
93 if (isLoopExiting(Latch))
94 return Latch;
95 else
96 return getExitingBlock();
97 }
98 return nullptr;
99}
100
102 // Try the pre-header first.
103 if (MachineBasicBlock *PHeadMBB = getLoopPreheader())
104 if (const BasicBlock *PHeadBB = PHeadMBB->getBasicBlock())
105 if (DebugLoc DL = PHeadBB->getTerminator()->getDebugLoc())
106 return DL;
107
108 // If we have no pre-header or there are no instructions with debug
109 // info in it, try the header.
110 if (MachineBasicBlock *HeadMBB = getHeader())
111 if (const BasicBlock *HeadBB = HeadMBB->getBasicBlock())
112 return HeadBB->getTerminator()->getDebugLoc();
113
114 return DebugLoc();
115}
116
119 bool FindMultiLoopPreheader) const {
120 if (MachineBasicBlock *PB = L->getLoopPreheader())
121 return PB;
122
123 if (!SpeculativePreheader)
124 return nullptr;
125
126 MachineBasicBlock *HB = L->getHeader(), *LB = L->getLoopLatch();
127 if (HB->pred_size() != 2 || HB->hasAddressTaken())
128 return nullptr;
129 // Find the predecessor of the header that is not the latch block.
130 MachineBasicBlock *Preheader = nullptr;
131 for (MachineBasicBlock *P : HB->predecessors()) {
132 if (P == LB)
133 continue;
134 // Sanity.
135 if (Preheader)
136 return nullptr;
137 Preheader = P;
138 }
139
140 // Check if the preheader candidate is a successor of any other loop
141 // headers. We want to avoid having two loop setups in the same block.
142 if (!FindMultiLoopPreheader) {
143 for (MachineBasicBlock *S : Preheader->successors()) {
144 if (S == HB)
145 continue;
147 if (T && T->getHeader() == S)
148 return nullptr;
149 }
150 }
151 return Preheader;
152}
153
155 MDNode *LoopID = nullptr;
156 if (const auto *MBB = findLoopControlBlock()) {
157 // If there is a single latch block, then the metadata
158 // node is attached to its terminating instruction.
159 const auto *BB = MBB->getBasicBlock();
160 if (!BB)
161 return nullptr;
162 if (const auto *TI = BB->getTerminator())
163 LoopID = TI->getMetadata(LLVMContext::MD_loop);
164 } else if (const auto *MBB = getHeader()) {
165 // There seem to be multiple latch blocks, so we have to
166 // visit all predecessors of the loop header and check
167 // their terminating instructions for the metadata.
168 if (const auto *Header = MBB->getBasicBlock()) {
169 // Walk over all blocks in the loop.
170 for (const auto *MBB : this->blocks()) {
171 const auto *BB = MBB->getBasicBlock();
172 if (!BB)
173 return nullptr;
174 const auto *TI = BB->getTerminator();
175 if (!TI)
176 return nullptr;
177 MDNode *MD = nullptr;
178 // Check if this terminating instruction jumps to the loop header.
179 for (const auto *Succ : successors(TI)) {
180 if (Succ == Header) {
181 // This is a jump to the header - gather the metadata from it.
182 MD = TI->getMetadata(LLVMContext::MD_loop);
183 break;
184 }
185 }
186 if (!MD)
187 return nullptr;
188 if (!LoopID)
189 LoopID = MD;
190 else if (MD != LoopID)
191 return nullptr;
192 }
193 }
194 }
195 if (LoopID &&
196 (LoopID->getNumOperands() == 0 || LoopID->getOperand(0) != LoopID))
197 LoopID = nullptr;
198 return LoopID;
199}
200
201bool MachineLoop::isLoopInvariantImplicitPhysReg(Register Reg) const {
204
205 if (MRI->isConstantPhysReg(Reg))
206 return true;
207
208 if (!MF->getSubtarget()
211 return false;
212
213 return !llvm::any_of(
214 MRI->def_instructions(Reg),
215 [this](const MachineInstr &MI) { return this->contains(&MI); });
216}
217
219 const Register ExcludeReg) const {
220 MachineFunction *MF = I.getParent()->getParent();
222 const TargetSubtargetInfo &ST = MF->getSubtarget();
223 const TargetRegisterInfo *TRI = ST.getRegisterInfo();
224 const TargetInstrInfo *TII = ST.getInstrInfo();
225
226 // The instruction is loop invariant if all of its operands are.
227 for (const MachineOperand &MO : I.operands()) {
228 if (!MO.isReg())
229 continue;
230
231 Register Reg = MO.getReg();
232 if (Reg == 0) continue;
233
234 if (ExcludeReg == Reg)
235 continue;
236
237 // An instruction that uses or defines a physical register can't e.g. be
238 // hoisted, so mark this as not invariant.
239 if (Reg.isPhysical()) {
240 if (MO.isUse()) {
241 // If the physreg has no defs anywhere, it's just an ambient register
242 // and we can freely move its uses. Alternatively, if it's allocatable,
243 // it could get allocated to something with a def during allocation.
244 // However, if the physreg is known to always be caller saved/restored
245 // then this use is safe to hoist.
246 if (!isLoopInvariantImplicitPhysReg(Reg) &&
247 !(TRI->isCallerPreservedPhysReg(Reg.asMCReg(), *I.getMF())) &&
248 !TII->isIgnorableUse(MO))
249 return false;
250 // Otherwise it's safe to move.
251 continue;
252 } else if (!MO.isDead()) {
253 // A def that isn't dead can't be moved.
254 return false;
255 } else if (getHeader()->isLiveIn(Reg)) {
256 // If the reg is live into the loop, we can't hoist an instruction
257 // which would clobber it.
258 return false;
259 }
260 }
261
262 if (!MO.isUse())
263 continue;
264
265 assert(MRI->getVRegDef(Reg) &&
266 "Machine instr not mapped for this vreg?!");
267
268 // If the loop contains the definition of an operand, then the instruction
269 // isn't loop invariant.
270 if (contains(MRI->getVRegDef(Reg)))
271 return false;
272 }
273
274 // If we got this far, the instruction is loop invariant!
275 return true;
276}
277
278#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
280 print(dbgs());
281}
282#endif
unsigned const MachineRegisterInfo * MRI
MachineBasicBlock & MBB
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
basic Basic Alias true
COFF::MachineTypes Machine
Definition: COFFYAML.cpp:371
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
Definition: Compiler.h:529
Dominance Frontier Construction
bool End
Definition: ELF_riscv.cpp:480
const HexagonInstrInfo * TII
IRTranslator LLVM IR MI
loops
Definition: LoopInfo.cpp:1177
#define I(x, y, z)
Definition: MD5.cpp:58
unsigned const TargetRegisterInfo * TRI
#define P(N)
PassBuilder PB(Machine, PassOpts->PTO, std::nullopt, &PIC)
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:55
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:59
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:52
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
Represent the analysis usage information of a pass.
AnalysisUsage & addRequired()
void setPreservesAll()
Set by analyses that do not transform their input at all.
LLVM Basic Block Representation.
Definition: BasicBlock.h:60
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Definition: BasicBlock.h:220
A debug info location.
Definition: DebugLoc.h:33
Instances of this class are used to represent loops that are detected in the flow graph.
bool contains(const MachineLoop *L) const
Return true if the specified loop is contained within in this loop.
MachineBasicBlock * getLoopLatch() const
If there is a single latch block for this loop, return it.
void print(raw_ostream &OS, bool Verbose=false, bool PrintNested=true, unsigned Depth=0) const
Print loop with all the BBs inside it.
iterator_range< block_iterator > blocks() const
MachineBasicBlock * getLoopPreheader() const
If there is a preheader for this loop, return it.
MachineBasicBlock * getExitingBlock() const
If getExitingBlocks would return exactly one block, return that block.
bool isLoopExiting(const MachineBasicBlock *BB) const
True if terminator in the block can branch to another block that is outside of the current loop.
This class builds and contains all of the top-level loop structures in the specified function.
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:44
Metadata node.
Definition: Metadata.h:1067
const MDOperand & getOperand(unsigned I) const
Definition: Metadata.h:1428
unsigned getNumOperands() const
Return number of MDNode operands.
Definition: Metadata.h:1434
unsigned pred_size() const
const BasicBlock * getBasicBlock() const
Return the LLVM basic block that this instance corresponded to originally.
bool hasAddressTaken() const
Test whether this block is used as something other than the target of a terminator,...
const MachineFunction * getParent() const
Return the MachineFunction containing this basic block.
iterator_range< succ_iterator > successors()
iterator_range< pred_iterator > predecessors()
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...
MachineDomTree & getBase()
MachineFunctionPass - This class adapts the FunctionPass interface to allow convenient creation of pa...
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
Representation of each machine instruction.
Definition: MachineInstr.h:69
void calculate(MachineDominatorTree &MDT)
MachineBasicBlock * findLoopPreheader(MachineLoop *L, bool SpeculativePreheader=false, bool FindMultiLoopPreheader=false) const
Find the block that either is the loop preheader, or could speculatively be used as the preheader.
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
void releaseMemory() override
releaseMemory() - This member can be implemented by a pass if it wants to be able to release its memo...
MachineLoop * getLoopFor(const MachineBasicBlock *BB) const
Return the innermost loop that BB lives in.
MachineBasicBlock * findLoopControlBlock() const
Find the block that contains the loop control variable and the loop test.
MDNode * getLoopID() const
Find the llvm.loop metadata for this loop.
DebugLoc getStartLoc() const
Return the debug location of the start of this loop.
MachineBasicBlock * getBottomBlock()
Return the "bottom" block in the loop, which is the last block in the linear layout,...
bool isLoopInvariant(MachineInstr &I, const Register ExcludeReg=0) const
Returns true if the instruction is loop invariant.
MachineBasicBlock * getTopBlock()
Return the "top" block in the loop, which is the first block in the linear layout,...
MachineOperand class - Representation of each machine instruction operand.
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Wrapper class representing virtual and physical registers.
Definition: Register.h:19
TargetInstrInfo - Interface to description of machine instruction set.
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
virtual bool shouldAnalyzePhysregInMachineLoopInfo(MCRegister R) const
Returns true if MachineLoopInfo should analyze the given physreg for loop invariance.
TargetSubtargetInfo - Generic base class for all target subtargets.
virtual const TargetRegisterInfo * getRegisterInfo() const
getRegisterInfo - If register information is available, return it.
self_iterator getIterator()
Definition: ilist_node.h:109
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
auto successors(const MachineBasicBlock *BB)
char & MachineLoopInfoID
MachineLoopInfo - This pass is a loop analysis pass.
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1738
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
void initializeMachineLoopInfoPass(PassRegistry &)