LLVM: lib/CodeGen/MachineLoopInfo.cpp Source File

LLVM 22.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
16#include "llvm/CodeGen/MachineLoopInfo.h"
17#include "llvm/CodeGen/MachineDominators.h"
18#include "llvm/CodeGen/MachineRegisterInfo.h"
19#include "llvm/CodeGen/TargetInstrInfo.h"
20#include "llvm/CodeGen/TargetSubtargetInfo.h"
21#include "llvm/Config/llvm-config.h"
22#include "llvm/InitializePasses.h"
23#include "llvm/Pass.h"
24#include "llvm/PassRegistry.h"
25#include "llvm/Support/Compiler.h"
26#include "llvm/Support/GenericLoopInfoImpl.h"
27
28using namespace llvm;
29
30// Explicitly instantiate methods in LoopInfoImpl.h for MI-level Loops.
31template class LLVM_EXPORT_TEMPLATE
32 llvm::LoopBase<MachineBasicBlock, MachineLoop>;
33template class LLVM_EXPORT_TEMPLATE
34 llvm::LoopInfoBase<MachineBasicBlock, MachineLoop>;
35
36AnalysisKey MachineLoopAnalysis::Key;
37
38MachineLoopAnalysis::Result
43
44PreservedAnalyses
47 OS << "Machine loop info for machine function '" << MF.getName() << "':\n";
50}
51
52char MachineLoopInfoWrapperPass::ID = 0;
57 INITIALIZE_PASS_BEGIN(MachineLoopInfoWrapperPass, "machine-loops",
58 "Machine Natural Loop Construction", true, true)
59INITIALIZE_PASS_DEPENDENCY(MachineDominatorTreeWrapperPass)
60 INITIALIZE_PASS_END(MachineLoopInfoWrapperPass, "machine-loops",
61 "Machine Natural Loop Construction", true, true)
62
63 char &llvm::MachineLoopInfoID = MachineLoopInfoWrapperPass::ID;
64
69
72 MachineFunctionAnalysisManager::Invalidator &) {
73 // Check whether the analysis, all analyses on functions, or the function's
74 // CFG have been preserved.
75 auto PAC = PA.getChecker<MachineLoopAnalysis>();
76 return !PAC.preserved() &&
77 !PAC.preservedSet<AllAnalysesOn<MachineFunction>>() &&
78 !PAC.preservedSet<CFGAnalyses>();
79}
80
85
91
93 MachineBasicBlock *TopMBB = getHeader();
94 MachineFunction::iterator Begin = TopMBB->getParent()->begin();
95 if (TopMBB->getIterator() != Begin) {
96 MachineBasicBlock *PriorMBB = &*std::prev(TopMBB->getIterator());
97 while (contains(PriorMBB)) {
98 TopMBB = PriorMBB;
99 if (TopMBB->getIterator() == Begin)
100 break;
101 PriorMBB = &*std::prev(TopMBB->getIterator());
102 }
103 }
104 return TopMBB;
105}
106
108 MachineBasicBlock *BotMBB = getHeader();
109 MachineFunction::iterator End = BotMBB->getParent()->end();
110 if (BotMBB->getIterator() != std::prev(End)) {
111 MachineBasicBlock *NextMBB = &*std::next(BotMBB->getIterator());
112 while (contains(NextMBB)) {
113 BotMBB = NextMBB;
114 if (BotMBB == &*std::next(BotMBB->getIterator()))
115 break;
116 NextMBB = &*std::next(BotMBB->getIterator());
117 }
118 }
119 return BotMBB;
120}
121
123 if (MachineBasicBlock *Latch = getLoopLatch()) {
124 if (isLoopExiting(Latch))
125 return Latch;
126 else
127 return getExitingBlock();
128 }
129 return nullptr;
130}
131
133 // Try the pre-header first.
134 if (MachineBasicBlock *PHeadMBB = getLoopPreheader())
135 if (const BasicBlock *PHeadBB = PHeadMBB->getBasicBlock())
136 if (DebugLoc DL = PHeadBB->getTerminator()->getDebugLoc())
137 return DL;
138
139 // If we have no pre-header or there are no instructions with debug
140 // info in it, try the header.
141 if (MachineBasicBlock *HeadMBB = getHeader())
142 if (const BasicBlock *HeadBB = HeadMBB->getBasicBlock())
143 return HeadBB->getTerminator()->getDebugLoc();
144
145 return DebugLoc();
146}
147
148MachineBasicBlock *
149 MachineLoopInfo::findLoopPreheader(MachineLoop *L, bool SpeculativePreheader,
150 bool FindMultiLoopPreheader) const {
151 if (MachineBasicBlock *PB = L->getLoopPreheader())
152 return PB;
153
154 if (!SpeculativePreheader)
155 return nullptr;
156
157 MachineBasicBlock *HB = L->getHeader(), *LB = L->getLoopLatch();
158 if (HB->pred_size() != 2 || HB->hasAddressTaken())
159 return nullptr;
160 // Find the predecessor of the header that is not the latch block.
161 MachineBasicBlock *Preheader = nullptr;
162 for (MachineBasicBlock *P : HB->predecessors()) {
163 if (P == LB)
164 continue;
165 // Sanity.
166 if (Preheader)
167 return nullptr;
168 Preheader = P;
169 }
170
171 // Check if the preheader candidate is a successor of any other loop
172 // headers. We want to avoid having two loop setups in the same block.
173 if (!FindMultiLoopPreheader) {
174 for (MachineBasicBlock *S : Preheader->successors()) {
175 if (S == HB)
176 continue;
178 if (T && T->getHeader() == S)
179 return nullptr;
180 }
181 }
182 return Preheader;
183}
184
186 MDNode *LoopID = nullptr;
187
188 // Go through the latch blocks and check the terminator for the metadata
190 getLoopLatches(LatchesBlocks);
191 for (const auto *MBB : LatchesBlocks) {
192 const auto *BB = MBB->getBasicBlock();
193 if (!BB)
194 return nullptr;
195 const auto *TI = BB->getTerminator();
196 if (!TI)
197 return nullptr;
198
199 MDNode *MD = TI->getMetadata(LLVMContext::MD_loop);
200 if (!MD)
201 return nullptr;
202
203 if (!LoopID)
204 LoopID = MD;
205 else if (MD != LoopID)
206 return nullptr;
207 }
208
209 if (!LoopID || LoopID->getNumOperands() == 0 ||
210 LoopID->getOperand(0) != LoopID)
211 return nullptr;
212
213 return LoopID;
214}
215
216bool MachineLoop::isLoopInvariantImplicitPhysReg(Register Reg) const {
217 MachineFunction *MF = getHeader()->getParent();
218 MachineRegisterInfo *MRI = &MF->getRegInfo();
219
220 if (MRI->isConstantPhysReg(Reg))
221 return true;
222
223 if (!MF->getSubtarget()
224 .getRegisterInfo()
225 ->shouldAnalyzePhysregInMachineLoopInfo(Reg))
226 return false;
227
228 return !llvm::any_of(
229 MRI->def_instructions(Reg),
230 [this](const MachineInstr &MI) { return this->contains(&MI); });
231}
232
234 const Register ExcludeReg) const {
235 MachineFunction *MF = I.getParent()->getParent();
237 const TargetSubtargetInfo &ST = MF->getSubtarget();
238 const TargetRegisterInfo *TRI = ST.getRegisterInfo();
239 const TargetInstrInfo *TII = ST.getInstrInfo();
240
241 // The instruction is loop invariant if all of its operands are.
242 for (const MachineOperand &MO : I.operands()) {
243 if (!MO.isReg())
244 continue;
245
246 Register Reg = MO.getReg();
247 if (Reg == 0) continue;
248
249 if (ExcludeReg == Reg)
250 continue;
251
252 // An instruction that uses or defines a physical register can't e.g. be
253 // hoisted, so mark this as not invariant.
254 if (Reg.isPhysical()) {
255 if (MO.isUse()) {
256 // If the physreg has no defs anywhere, it's just an ambient register
257 // and we can freely move its uses. Alternatively, if it's allocatable,
258 // it could get allocated to something with a def during allocation.
259 // However, if the physreg is known to always be caller saved/restored
260 // then this use is safe to hoist.
261 if (!isLoopInvariantImplicitPhysReg(Reg) &&
262 !(TRI->isCallerPreservedPhysReg(Reg.asMCReg(), *I.getMF())) &&
263 !TII->isIgnorableUse(MO))
264 return false;
265 // Otherwise it's safe to move.
266 continue;
267 } else if (!MO.isDead()) {
268 // A def that isn't dead can't be moved.
269 return false;
270 } else if (getHeader()->isLiveIn(Reg)) {
271 // If the reg is live into the loop, we can't hoist an instruction
272 // which would clobber it.
273 return false;
274 }
275 }
276
277 if (!MO.readsReg())
278 continue;
279
280 assert(MRI->getVRegDef(Reg) &&
281 "Machine instr not mapped for this vreg?!");
282
283 // If the loop contains the definition of an operand, then the instruction
284 // isn't loop invariant.
285 if (contains(MRI->getVRegDef(Reg)))
286 return false;
287 }
288
289 // If we got this far, the instruction is loop invariant!
290 return true;
291}
292
293#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
295 print(dbgs());
296}
297#endif
unsigned const MachineRegisterInfo * MRI
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
MachineBasicBlock & MBB
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
Definition Compiler.h:638
#define LLVM_EXPORT_TEMPLATE
Definition Compiler.h:215
const HexagonInstrInfo * TII
IRTranslator LLVM IR MI
I
#define I(x, y, z)
Definition MD5.cpp:58
Register const TargetRegisterInfo * TRI
T
#define T
P
#define P(N)
PassBuilder PB(Machine, PassOpts->PTO, std::nullopt, &PIC)
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition PassSupport.h:42
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition PassSupport.h:44
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
Definition PassSupport.h:39
This templated class represents "all analyses that operate over <aparticular IR unit>" (e....
Definition Analysis.h:50
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition PassManager.h:412
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:62
Represents analyses that only rely on functions' control flow.
Definition Analysis.h:73
A debug info location.
Definition DebugLoc.h:124
Instances of this class are used to represent loops that are detected in the flow graph.
bool contains(const MachineLoop *L) const
void getLoopLatches(SmallVectorImpl< MachineBasicBlock * > &LoopLatches) const
void print(raw_ostream &OS, bool Verbose=false, bool PrintNested=true, unsigned Depth=0) const
bool isLoopExiting(const MachineBasicBlock *BB) const
This class builds and contains all of the top-level loop structures in the specified function.
void analyze(const DominatorTreeBase< MachineBasicBlock, false > &DomTree)
MachineLoop * getLoopFor(const MachineBasicBlock *BB) const
Metadata node.
Definition Metadata.h:1078
const MDOperand & getOperand(unsigned I) const
Definition Metadata.h:1442
unsigned getNumOperands() const
Return number of MDNode operands.
Definition Metadata.h:1448
unsigned pred_size() const
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...
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.
BasicBlockListType::iterator iterator
Representation of each machine instruction.
Definition MachineInstr.h:72
Analysis pass that exposes the MachineLoopInfo for a machine function.
LLVM_ABI Result run(MachineFunction &MF, MachineFunctionAnalysisManager &MFAM)
bool runOnMachineFunction(MachineFunction &F) override
runOnMachineFunction - This method must be overloaded to perform the desired machine code transformat...
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
LLVM_ABI void calculate(MachineDominatorTree &MDT)
Calculate the natural loop information.
LLVM_ABI bool invalidate(MachineFunction &, const PreservedAnalyses &PA, MachineFunctionAnalysisManager::Invalidator &)
Handle invalidation explicitly.
LLVM_ABI 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.
LLVM_ABI PreservedAnalyses run(MachineFunction &MF, MachineFunctionAnalysisManager &MFAM)
LLVM_ABI MachineBasicBlock * findLoopControlBlock() const
Find the block that contains the loop control variable and the loop test.
LLVM_ABI MDNode * getLoopID() const
Find the llvm.loop metadata for this loop.
LLVM_ABI DebugLoc getStartLoc() const
Return the debug location of the start of this loop.
LLVM_ABI void dump() const
LLVM_ABI MachineBasicBlock * getBottomBlock()
Return the "bottom" block in the loop, which is the last block in the linear layout,...
LLVM_ABI bool isLoopInvariant(MachineInstr &I, const Register ExcludeReg=0) const
Returns true if the instruction is loop invariant.
LLVM_ABI 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 LLVM_ABI PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
AnalysisType & getAnalysis() const
getAnalysis<AnalysisType>() - This function is used by subclasses to get to the analysis information ...
A set of analyses that are preserved following a run of a transformation pass.
Definition Analysis.h:112
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition Analysis.h:118
PreservedAnalysisChecker getChecker() const
Build a checker for this PreservedAnalyses and the specified analysis type.
Definition Analysis.h:275
Wrapper class representing virtual and physical registers.
Definition Register.h:20
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition SmallVector.h:1203
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 =0
Return the target's register information.
self_iterator getIterator()
Definition ilist_node.h:123
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition CallingConv.h:24
@ DebugLoc
This is an optimization pass for GlobalISel generic memory operations.
Definition AddressRanges.h:18
Printable print(const GCNRegPressure &RP, const GCNSubtarget *ST=nullptr, unsigned DynamicVGPRBlockSize=0)
LLVM_ABI void initializeMachineLoopInfoWrapperPassPass(PassRegistry &)
AnalysisManager< MachineFunction > MachineFunctionAnalysisManager
LLVM_ABI 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:1732
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition Debug.cpp:207
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition Analysis.h:29
Generated on for LLVM by doxygen 1.14.0

AltStyle によって変換されたページ (->オリジナル) /