LLVM 20.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
33AnalysisKey MachineLoopAnalysis::Key;
34
39}
40
44 OS << "Machine loop info for machine function '" << MF.getName() << "':\n";
47}
48
53}
55 "Machine Natural Loop Construction", true, true)
59
61
62bool MachineLoopInfoWrapperPass::runOnMachineFunction(MachineFunction &) {
63 LI.calculate(getAnalysis<MachineDominatorTreeWrapperPass>().getDomTree());
64 return false;
65}
66
70 // Check whether the analysis, all analyses on functions, or the function's
71 // CFG have been preserved.
72 auto PAC = PA.getChecker<MachineLoopAnalysis>();
73 return !PAC.preserved() &&
74 !PAC.preservedSet<AllAnalysesOn<MachineFunction>>() &&
75 !PAC.preservedSet<CFGAnalyses>();
76}
77
80 analyze(MDT.getBase());
81}
82
84 AU.setPreservesAll();
87}
88
90 MachineBasicBlock *TopMBB = getHeader();
91 MachineFunction::iterator Begin = TopMBB->getParent()->begin();
92 if (TopMBB->getIterator() != Begin) {
93 MachineBasicBlock *PriorMBB = &*std::prev(TopMBB->getIterator());
94 while (contains(PriorMBB)) {
95 TopMBB = PriorMBB;
96 if (TopMBB->getIterator() == Begin)
97 break;
98 PriorMBB = &*std::prev(TopMBB->getIterator());
99 }
100 }
101 return TopMBB;
102}
103
105 MachineBasicBlock *BotMBB = getHeader();
107 if (BotMBB->getIterator() != std::prev(End)) {
108 MachineBasicBlock *NextMBB = &*std::next(BotMBB->getIterator());
109 while (contains(NextMBB)) {
110 BotMBB = NextMBB;
111 if (BotMBB == &*std::next(BotMBB->getIterator()))
112 break;
113 NextMBB = &*std::next(BotMBB->getIterator());
114 }
115 }
116 return BotMBB;
117}
118
120 if (MachineBasicBlock *Latch = getLoopLatch()) {
121 if (isLoopExiting(Latch))
122 return Latch;
123 else
124 return getExitingBlock();
125 }
126 return nullptr;
127}
128
130 // Try the pre-header first.
131 if (MachineBasicBlock *PHeadMBB = getLoopPreheader())
132 if (const BasicBlock *PHeadBB = PHeadMBB->getBasicBlock())
133 if (DebugLoc DL = PHeadBB->getTerminator()->getDebugLoc())
134 return DL;
135
136 // If we have no pre-header or there are no instructions with debug
137 // info in it, try the header.
138 if (MachineBasicBlock *HeadMBB = getHeader())
139 if (const BasicBlock *HeadBB = HeadMBB->getBasicBlock())
140 return HeadBB->getTerminator()->getDebugLoc();
141
142 return DebugLoc();
143}
144
147 bool FindMultiLoopPreheader) const {
148 if (MachineBasicBlock *PB = L->getLoopPreheader())
149 return PB;
150
151 if (!SpeculativePreheader)
152 return nullptr;
153
154 MachineBasicBlock *HB = L->getHeader(), *LB = L->getLoopLatch();
155 if (HB->pred_size() != 2 || HB->hasAddressTaken())
156 return nullptr;
157 // Find the predecessor of the header that is not the latch block.
158 MachineBasicBlock *Preheader = nullptr;
159 for (MachineBasicBlock *P : HB->predecessors()) {
160 if (P == LB)
161 continue;
162 // Sanity.
163 if (Preheader)
164 return nullptr;
165 Preheader = P;
166 }
167
168 // Check if the preheader candidate is a successor of any other loop
169 // headers. We want to avoid having two loop setups in the same block.
170 if (!FindMultiLoopPreheader) {
171 for (MachineBasicBlock *S : Preheader->successors()) {
172 if (S == HB)
173 continue;
175 if (T && T->getHeader() == S)
176 return nullptr;
177 }
178 }
179 return Preheader;
180}
181
183 MDNode *LoopID = nullptr;
184 if (const auto *MBB = findLoopControlBlock()) {
185 // If there is a single latch block, then the metadata
186 // node is attached to its terminating instruction.
187 const auto *BB = MBB->getBasicBlock();
188 if (!BB)
189 return nullptr;
190 if (const auto *TI = BB->getTerminator())
191 LoopID = TI->getMetadata(LLVMContext::MD_loop);
192 } else if (const auto *MBB = getHeader()) {
193 // There seem to be multiple latch blocks, so we have to
194 // visit all predecessors of the loop header and check
195 // their terminating instructions for the metadata.
196 if (const auto *Header = MBB->getBasicBlock()) {
197 // Walk over all blocks in the loop.
198 for (const auto *MBB : this->blocks()) {
199 const auto *BB = MBB->getBasicBlock();
200 if (!BB)
201 return nullptr;
202 const auto *TI = BB->getTerminator();
203 if (!TI)
204 return nullptr;
205 MDNode *MD = nullptr;
206 // Check if this terminating instruction jumps to the loop header.
207 for (const auto *Succ : successors(TI)) {
208 if (Succ == Header) {
209 // This is a jump to the header - gather the metadata from it.
210 MD = TI->getMetadata(LLVMContext::MD_loop);
211 break;
212 }
213 }
214 if (!MD)
215 return nullptr;
216 if (!LoopID)
217 LoopID = MD;
218 else if (MD != LoopID)
219 return nullptr;
220 }
221 }
222 }
223 if (LoopID &&
224 (LoopID->getNumOperands() == 0 || LoopID->getOperand(0) != LoopID))
225 LoopID = nullptr;
226 return LoopID;
227}
228
229bool MachineLoop::isLoopInvariantImplicitPhysReg(Register Reg) const {
232
233 if (MRI->isConstantPhysReg(Reg))
234 return true;
235
236 if (!MF->getSubtarget()
239 return false;
240
241 return !llvm::any_of(
242 MRI->def_instructions(Reg),
243 [this](const MachineInstr &MI) { return this->contains(&MI); });
244}
245
247 const Register ExcludeReg) const {
248 MachineFunction *MF = I.getParent()->getParent();
250 const TargetSubtargetInfo &ST = MF->getSubtarget();
251 const TargetRegisterInfo *TRI = ST.getRegisterInfo();
252 const TargetInstrInfo *TII = ST.getInstrInfo();
253
254 // The instruction is loop invariant if all of its operands are.
255 for (const MachineOperand &MO : I.operands()) {
256 if (!MO.isReg())
257 continue;
258
259 Register Reg = MO.getReg();
260 if (Reg == 0) continue;
261
262 if (ExcludeReg == Reg)
263 continue;
264
265 // An instruction that uses or defines a physical register can't e.g. be
266 // hoisted, so mark this as not invariant.
267 if (Reg.isPhysical()) {
268 if (MO.isUse()) {
269 // If the physreg has no defs anywhere, it's just an ambient register
270 // and we can freely move its uses. Alternatively, if it's allocatable,
271 // it could get allocated to something with a def during allocation.
272 // However, if the physreg is known to always be caller saved/restored
273 // then this use is safe to hoist.
274 if (!isLoopInvariantImplicitPhysReg(Reg) &&
275 !(TRI->isCallerPreservedPhysReg(Reg.asMCReg(), *I.getMF())) &&
276 !TII->isIgnorableUse(MO))
277 return false;
278 // Otherwise it's safe to move.
279 continue;
280 } else if (!MO.isDead()) {
281 // A def that isn't dead can't be moved.
282 return false;
283 } else if (getHeader()->isLiveIn(Reg)) {
284 // If the reg is live into the loop, we can't hoist an instruction
285 // which would clobber it.
286 return false;
287 }
288 }
289
290 if (!MO.isUse())
291 continue;
292
293 assert(MRI->getVRegDef(Reg) &&
294 "Machine instr not mapped for this vreg?!");
295
296 // If the loop contains the definition of an operand, then the instruction
297 // isn't loop invariant.
298 if (contains(MRI->getVRegDef(Reg)))
299 return false;
300 }
301
302 // If we got this far, the instruction is loop invariant!
303 return true;
304}
305
306#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
308 print(dbgs());
309}
310#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:537
Dominance Frontier Construction
bool End
Definition: ELF_riscv.cpp:480
const HexagonInstrInfo * TII
IRTranslator LLVM IR MI
loops
Definition: LoopInfo.cpp:1209
#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())
This templated class represents "all analyses that operate over <a particular IR unit>" (e....
Definition: Analysis.h:49
API to communicate dependencies between analyses during invalidation.
Definition: PassManager.h:292
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:253
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:405
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:61
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:229
Represents analyses that only rely on functions' control flow.
Definition: Analysis.h:72
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.
void analyze(const DominatorTreeBase< MachineBasicBlock, false > &DomTree)
Create the loop forest using a stable algorithm.
MachineLoop * getLoopFor(const MachineBasicBlock *BB) const
Return the inner most loop that BB lives in.
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()
Analysis pass which computes a MachineDominatorTree.
Analysis pass which computes a MachineDominatorTree.
DominatorTree Class - Concrete subclass of DominatorTreeBase that is used to compute a normal dominat...
MachineDominatorTree & 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.
StringRef getName() const
getName - Return the name of the corresponding LLVM function.
MachineRegisterInfo & getRegInfo()
getRegInfo - Return information about the registers currently in use.
Representation of each machine instruction.
Definition: MachineInstr.h:69
Analysis pass that exposes the MachineLoopInfo for a machine function.
Result run(MachineFunction &MF, MachineFunctionAnalysisManager &MFAM)
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
void calculate(MachineDominatorTree &MDT)
Calculate the natural loop information.
bool invalidate(MachineFunction &, const PreservedAnalyses &PA, MachineFunctionAnalysisManager::Invalidator &)
Handle invalidation explicitly.
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.
PreservedAnalyses run(MachineFunction &MF, MachineFunctionAnalysisManager &MFAM)
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...
A set of analyses that are preserved following a run of a transformation pass.
Definition: Analysis.h:111
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: Analysis.h:117
PreservedAnalysisChecker getChecker() const
Build a checker for this PreservedAnalyses and the specified analysis type.
Definition: Analysis.h:264
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:132
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
auto successors(const MachineBasicBlock *BB)
void initializeMachineLoopInfoWrapperPassPass(PassRegistry &)
Printable print(const GCNRegPressure &RP, const GCNSubtarget *ST=nullptr)
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:1729
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: Analysis.h:28