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/Support/Compiler.h"
25#include "llvm/Support/GenericLoopInfoImpl.h"
26
27using namespace llvm;
28
29// Explicitly instantiate methods in LoopInfoImpl.h for MI-level Loops.
30template class LLVM_EXPORT_TEMPLATE
31 llvm::LoopBase<MachineBasicBlock, MachineLoop>;
32template class LLVM_EXPORT_TEMPLATE
33 llvm::LoopInfoBase<MachineBasicBlock, MachineLoop>;
34
35AnalysisKey MachineLoopAnalysis::Key;
36
37MachineLoopAnalysis::Result
38MachineLoopAnalysis::run(MachineFunction &MF,
39 MachineFunctionAnalysisManager &MFAM) {
40 MachineLoopInfo LI;
41 // The dominator tree is needed only for an irreducible CFG.
42 LI.calculate(MF, GetDomTree: [&]() -> const MachineDominatorTree & {
43 return MFAM.getResult<MachineDominatorTreeAnalysis>(IR&: MF);
44 });
45 return LI;
46}
47
48PreservedAnalyses
49MachineLoopPrinterPass::run(MachineFunction &MF,
50 MachineFunctionAnalysisManager &MFAM) {
51 OS << "Machine loop info for machine function '" << MF.getName() << "':\n";
52 MFAM.getResult<MachineLoopAnalysis>(IR&: MF).print(OS);
53 return PreservedAnalyses::all();
54}
55
56char MachineLoopInfoWrapperPass::ID = 0;
57MachineLoopInfoWrapperPass::MachineLoopInfoWrapperPass()
58 : MachineFunctionPass(ID) {}
59INITIALIZE_PASS_BEGIN(MachineLoopInfoWrapperPass, "machine-loops",
60 "Machine Natural Loop Construction", true, true)
61INITIALIZE_PASS_DEPENDENCY(MachineDominatorTreeWrapperPass)
62INITIALIZE_PASS_END(MachineLoopInfoWrapperPass, "machine-loops",
63 "Machine Natural Loop Construction", true, true)
64
65char &llvm::MachineLoopInfoID = MachineLoopInfoWrapperPass::ID;
66
67bool MachineLoopInfoWrapperPass::runOnMachineFunction(MachineFunction &) {
68 LI.calculate(MDT&: getAnalysis<MachineDominatorTreeWrapperPass>().getDomTree());
69 return false;
70}
71
72bool MachineLoopInfo::invalidate(
73 MachineFunction &, const PreservedAnalyses &PA,
74 MachineFunctionAnalysisManager::Invalidator &) {
75 // Check whether the analysis, all analyses on functions, or the function's
76 // CFG have been preserved.
77 auto PAC = PA.getChecker<MachineLoopAnalysis>();
78 return !PAC.preserved() &&
79 !PAC.preservedSet<AllAnalysesOn<MachineFunction>>() &&
80 !PAC.preservedSet<CFGAnalyses>();
81}
82
83void MachineLoopInfo::calculate(MachineDominatorTree &MDT) {
84 releaseMemory();
85 analyze(DomTree: MDT);
86}
87
88void MachineLoopInfo::calculate(
89 MachineFunction &MF,
90 function_ref<const DomTreeBase<MachineBasicBlock> &()> GetDomTree) {
91 releaseMemory();
92 analyze(F: &MF, GetDomTree);
93}
94
95void MachineLoopInfoWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
96 AU.setPreservesAll();
97 AU.addRequired<MachineDominatorTreeWrapperPass>();
98 MachineFunctionPass::getAnalysisUsage(AU);
99}
100
101MachineBasicBlock *MachineLoop::getTopBlock() const {
102 MachineBasicBlock *TopMBB = getHeader();
103 MachineFunction::iterator Begin = TopMBB->getParent()->begin();
104 if (TopMBB->getIterator() != Begin) {
105 MachineBasicBlock *PriorMBB = &*std::prev(x: TopMBB->getIterator());
106 while (contains(BB: PriorMBB)) {
107 TopMBB = PriorMBB;
108 if (TopMBB->getIterator() == Begin)
109 break;
110 PriorMBB = &*std::prev(x: TopMBB->getIterator());
111 }
112 }
113 return TopMBB;
114}
115
116MachineBasicBlock *MachineLoop::getBottomBlock() const {
117 MachineBasicBlock *BotMBB = getHeader();
118 MachineFunction::iterator End = BotMBB->getParent()->end();
119 if (BotMBB->getIterator() != std::prev(x: End)) {
120 MachineBasicBlock *NextMBB = &*std::next(x: BotMBB->getIterator());
121 while (contains(BB: NextMBB)) {
122 BotMBB = NextMBB;
123 if (BotMBB == &*std::next(x: BotMBB->getIterator()))
124 break;
125 NextMBB = &*std::next(x: BotMBB->getIterator());
126 }
127 }
128 return BotMBB;
129}
130
131MachineBasicBlock *MachineLoop::findLoopControlBlock() const {
132 if (MachineBasicBlock *Latch = getLoopLatch()) {
133 if (isLoopExiting(BB: Latch))
134 return Latch;
135 else
136 return getExitingBlock();
137 }
138 return nullptr;
139}
140
141DebugLoc MachineLoop::getStartLoc() const {
142 // Try the pre-header first.
143 if (MachineBasicBlock *PHeadMBB = getLoopPreheader())
144 if (const BasicBlock *PHeadBB = PHeadMBB->getBasicBlock())
145 if (DebugLoc DL = PHeadBB->getTerminator()->getDebugLoc())
146 return DL;
147
148 // If we have no pre-header or there are no instructions with debug
149 // info in it, try the header.
150 if (MachineBasicBlock *HeadMBB = getHeader())
151 if (const BasicBlock *HeadBB = HeadMBB->getBasicBlock())
152 return HeadBB->getTerminator()->getDebugLoc();
153
154 return DebugLoc();
155}
156
157MachineBasicBlock *
158MachineLoopInfo::findLoopPreheader(MachineLoop *L, bool SpeculativePreheader,
159 bool FindMultiLoopPreheader) const {
160 if (MachineBasicBlock *PB = L->getLoopPreheader())
161 return PB;
162
163 if (!SpeculativePreheader)
164 return nullptr;
165
166 MachineBasicBlock *HB = L->getHeader(), *LB = L->getLoopLatch();
167 if (HB->pred_size() != 2 || HB->hasAddressTaken())
168 return nullptr;
169 // Find the predecessor of the header that is not the latch block.
170 MachineBasicBlock *Preheader = nullptr;
171 for (MachineBasicBlock *P : HB->predecessors()) {
172 if (P == LB)
173 continue;
174 // Sanity.
175 if (Preheader)
176 return nullptr;
177 Preheader = P;
178 }
179
180 // Check if the preheader candidate is a successor of any other loop
181 // headers. We want to avoid having two loop setups in the same block.
182 if (!FindMultiLoopPreheader) {
183 for (MachineBasicBlock *S : Preheader->successors()) {
184 if (S == HB)
185 continue;
186 MachineLoop *T = getLoopFor(BB: S);
187 if (T && T->getHeader() == S)
188 return nullptr;
189 }
190 }
191 return Preheader;
192}
193
194MDNode *MachineLoop::getLoopID() const {
195 MDNode *LoopID = nullptr;
196
197 // Go through the latch blocks and check the terminator for the metadata
198 SmallVector<MachineBasicBlock *, 4> LatchesBlocks;
199 getLoopLatches(LoopLatches&: LatchesBlocks);
200 for (const auto *MBB : LatchesBlocks) {
201 const auto *BB = MBB->getBasicBlock();
202 if (!BB)
203 return nullptr;
204 const auto *TI = BB->getTerminator();
205 if (!TI)
206 return nullptr;
207
208 MDNode *MD = TI->getMetadata(KindID: LLVMContext::MD_loop);
209 if (!MD)
210 return nullptr;
211
212 if (!LoopID)
213 LoopID = MD;
214 else if (MD != LoopID)
215 return nullptr;
216 }
217
218 if (!LoopID || LoopID->getNumOperands() == 0 ||
219 LoopID->getOperand(I: 0) != LoopID)
220 return nullptr;
221
222 return LoopID;
223}
224
225bool MachineLoop::isLoopInvariantImplicitPhysReg(Register Reg) const {
226 MachineFunction *MF = getHeader()->getParent();
227 MachineRegisterInfo *MRI = &MF->getRegInfo();
228
229 if (MRI->isConstantPhysReg(PhysReg: Reg))
230 return true;
231
232 if (!MF->getSubtarget()
233 .getRegisterInfo()
234 ->shouldAnalyzePhysregInMachineLoopInfo(R: Reg))
235 return false;
236
237 return !llvm::any_of(
238 Range: MRI->def_instructions(Reg),
239 P: [this](const MachineInstr &MI) { return this->contains(Inst: &MI); });
240}
241
242bool MachineLoop::isLoopInvariant(MachineInstr &I,
243 const Register ExcludeReg) const {
244 MachineFunction *MF = I.getParent()->getParent();
245 MachineRegisterInfo *MRI = &MF->getRegInfo();
246 const TargetSubtargetInfo &ST = MF->getSubtarget();
247 const TargetRegisterInfo *TRI = ST.getRegisterInfo();
248 const TargetInstrInfo *TII = ST.getInstrInfo();
249
250 // The instruction is loop invariant if all of its operands are.
251 for (const MachineOperand &MO : I.operands()) {
252 if (!MO.isReg())
253 continue;
254
255 Register Reg = MO.getReg();
256 if (Reg == 0) continue;
257
258 if (ExcludeReg == Reg)
259 continue;
260
261 // An instruction that uses or defines a physical register can't e.g. be
262 // hoisted, so mark this as not invariant.
263 if (Reg.isPhysical()) {
264 if (MO.isUse()) {
265 // If the physreg has no defs anywhere, it's just an ambient register
266 // and we can freely move its uses. Alternatively, if it's allocatable,
267 // it could get allocated to something with a def during allocation.
268 // However, if the physreg is known to always be caller saved/restored
269 // then this use is safe to hoist.
270 if (!isLoopInvariantImplicitPhysReg(Reg) &&
271 !(TRI->isCallerPreservedPhysReg(PhysReg: Reg.asMCReg(), MF: *I.getMF())) &&
272 !TII->isIgnorableUse(MO))
273 return false;
274 // Otherwise it's safe to move.
275 continue;
276 } else if (!MO.isDead()) {
277 // A def that isn't dead can't be moved.
278 return false;
279 } else if (getHeader()->isLiveIn(Reg)) {
280 // If the reg is live into the loop, we can't hoist an instruction
281 // which would clobber it.
282 return false;
283 }
284 }
285
286 if (!MO.readsReg())
287 continue;
288
289 MachineBasicBlock *DefBlock = MRI->getDefBlock(Reg);
290 assert(DefBlock && "Machine instr not mapped for this vreg?!");
291
292 // If the loop contains the definition of an operand, then the instruction
293 // isn't loop invariant.
294 if (contains(BB: DefBlock))
295 return false;
296 }
297
298 // If we got this far, the instruction is loop invariant!
299 return true;
300}
301
302#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
303LLVM_DUMP_METHOD void MachineLoop::dump() const {
304 print(dbgs());
305}
306#endif
307