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
39MachineLoopAnalysis::run(MachineFunction &MF,
40 MachineFunctionAnalysisManager &MFAM) {
41 return MachineLoopInfo(MFAM.getResult<MachineDominatorTreeAnalysis>(IR&: MF));
42}
43
44PreservedAnalyses
45MachineLoopPrinterPass::run(MachineFunction &MF,
46 MachineFunctionAnalysisManager &MFAM) {
47 OS << "Machine loop info for machine function '" << MF.getName() << "':\n";
48 MFAM.getResult<MachineLoopAnalysis>(IR&: MF).print(OS);
49 return PreservedAnalyses::all();
50}
51
52char MachineLoopInfoWrapperPass::ID = 0;
53MachineLoopInfoWrapperPass::MachineLoopInfoWrapperPass()
54 : MachineFunctionPass(ID) {
55 initializeMachineLoopInfoWrapperPassPass(*PassRegistry::getPassRegistry());
56}
57INITIALIZE_PASS_BEGIN(MachineLoopInfoWrapperPass, "machine-loops",
58 "Machine Natural Loop Construction", true, true)
59INITIALIZE_PASS_DEPENDENCY(MachineDominatorTreeWrapperPass)
60INITIALIZE_PASS_END(MachineLoopInfoWrapperPass, "machine-loops",
61 "Machine Natural Loop Construction", true, true)
62
63char &llvm::MachineLoopInfoID = MachineLoopInfoWrapperPass::ID;
64
65bool MachineLoopInfoWrapperPass::runOnMachineFunction(MachineFunction &) {
66 LI.calculate(MDT&: getAnalysis<MachineDominatorTreeWrapperPass>().getDomTree());
67 return false;
68}
69
70bool MachineLoopInfo::invalidate(
71 MachineFunction &, const PreservedAnalyses &PA,
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
81void MachineLoopInfo::calculate(MachineDominatorTree &MDT) {
82 releaseMemory();
83 analyze(DomTree: MDT);
84}
85
86void MachineLoopInfoWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
87 AU.setPreservesAll();
88 AU.addRequired<MachineDominatorTreeWrapperPass>();
89 MachineFunctionPass::getAnalysisUsage(AU);
90}
91
92MachineBasicBlock *MachineLoop::getTopBlock() {
93 MachineBasicBlock *TopMBB = getHeader();
94 MachineFunction::iterator Begin = TopMBB->getParent()->begin();
95 if (TopMBB->getIterator() != Begin) {
96 MachineBasicBlock *PriorMBB = &*std::prev(x: TopMBB->getIterator());
97 while (contains(BB: PriorMBB)) {
98 TopMBB = PriorMBB;
99 if (TopMBB->getIterator() == Begin)
100 break;
101 PriorMBB = &*std::prev(x: TopMBB->getIterator());
102 }
103 }
104 return TopMBB;
105}
106
107MachineBasicBlock *MachineLoop::getBottomBlock() {
108 MachineBasicBlock *BotMBB = getHeader();
109 MachineFunction::iterator End = BotMBB->getParent()->end();
110 if (BotMBB->getIterator() != std::prev(x: End)) {
111 MachineBasicBlock *NextMBB = &*std::next(x: BotMBB->getIterator());
112 while (contains(BB: NextMBB)) {
113 BotMBB = NextMBB;
114 if (BotMBB == &*std::next(x: BotMBB->getIterator()))
115 break;
116 NextMBB = &*std::next(x: BotMBB->getIterator());
117 }
118 }
119 return BotMBB;
120}
121
122MachineBasicBlock *MachineLoop::findLoopControlBlock() const {
123 if (MachineBasicBlock *Latch = getLoopLatch()) {
124 if (isLoopExiting(BB: Latch))
125 return Latch;
126 else
127 return getExitingBlock();
128 }
129 return nullptr;
130}
131
132DebugLoc MachineLoop::getStartLoc() const {
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 *
149MachineLoopInfo::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;
177 MachineLoop *T = getLoopFor(BB: S);
178 if (T && T->getHeader() == S)
179 return nullptr;
180 }
181 }
182 return Preheader;
183}
184
185MDNode *MachineLoop::getLoopID() const {
186 MDNode *LoopID = nullptr;
187
188 // Go through the latch blocks and check the terminator for the metadata
189 SmallVector<MachineBasicBlock *, 4> LatchesBlocks;
190 getLoopLatches(LoopLatches&: 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(KindID: 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(I: 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(PhysReg: Reg))
221 return true;
222
223 if (!MF->getSubtarget()
224 .getRegisterInfo()
225 ->shouldAnalyzePhysregInMachineLoopInfo(R: Reg))
226 return false;
227
228 return !llvm::any_of(
229 Range: MRI->def_instructions(Reg),
230 P: [this](const MachineInstr &MI) { return this->contains(Inst: &MI); });
231}
232
233bool MachineLoop::isLoopInvariant(MachineInstr &I,
234 const Register ExcludeReg) const {
235 MachineFunction *MF = I.getParent()->getParent();
236 MachineRegisterInfo *MRI = &MF->getRegInfo();
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(PhysReg: Reg.asMCReg(), MF: *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(Inst: 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)
294LLVM_DUMP_METHOD void MachineLoop::dump() const {
295 print(dbgs());
296}
297#endif
298