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 return MachineLoopInfo(MFAM.getResult<MachineDominatorTreeAnalysis>(IR&: MF));
41}
42
43PreservedAnalyses
44MachineLoopPrinterPass::run(MachineFunction &MF,
45 MachineFunctionAnalysisManager &MFAM) {
46 OS << "Machine loop info for machine function '" << MF.getName() << "':\n";
47 MFAM.getResult<MachineLoopAnalysis>(IR&: MF).print(OS);
48 return PreservedAnalyses::all();
49}
50
51char MachineLoopInfoWrapperPass::ID = 0;
52MachineLoopInfoWrapperPass::MachineLoopInfoWrapperPass()
53 : MachineFunctionPass(ID) {}
54INITIALIZE_PASS_BEGIN(MachineLoopInfoWrapperPass, "machine-loops",
55 "Machine Natural Loop Construction", true, true)
56INITIALIZE_PASS_DEPENDENCY(MachineDominatorTreeWrapperPass)
57INITIALIZE_PASS_END(MachineLoopInfoWrapperPass, "machine-loops",
58 "Machine Natural Loop Construction", true, true)
59
60char &llvm::MachineLoopInfoID = MachineLoopInfoWrapperPass::ID;
61
62bool MachineLoopInfoWrapperPass::runOnMachineFunction(MachineFunction &) {
63 LI.calculate(MDT&: getAnalysis<MachineDominatorTreeWrapperPass>().getDomTree());
64 return false;
65}
66
67bool MachineLoopInfo::invalidate(
68 MachineFunction &, const PreservedAnalyses &PA,
69 MachineFunctionAnalysisManager::Invalidator &) {
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
78void MachineLoopInfo::calculate(MachineDominatorTree &MDT) {
79 releaseMemory();
80 analyze(DomTree: MDT);
81}
82
83void MachineLoopInfoWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
84 AU.setPreservesAll();
85 AU.addRequired<MachineDominatorTreeWrapperPass>();
86 MachineFunctionPass::getAnalysisUsage(AU);
87}
88
89MachineBasicBlock *MachineLoop::getTopBlock() {
90 MachineBasicBlock *TopMBB = getHeader();
91 MachineFunction::iterator Begin = TopMBB->getParent()->begin();
92 if (TopMBB->getIterator() != Begin) {
93 MachineBasicBlock *PriorMBB = &*std::prev(x: TopMBB->getIterator());
94 while (contains(BB: PriorMBB)) {
95 TopMBB = PriorMBB;
96 if (TopMBB->getIterator() == Begin)
97 break;
98 PriorMBB = &*std::prev(x: TopMBB->getIterator());
99 }
100 }
101 return TopMBB;
102}
103
104MachineBasicBlock *MachineLoop::getBottomBlock() {
105 MachineBasicBlock *BotMBB = getHeader();
106 MachineFunction::iterator End = BotMBB->getParent()->end();
107 if (BotMBB->getIterator() != std::prev(x: End)) {
108 MachineBasicBlock *NextMBB = &*std::next(x: BotMBB->getIterator());
109 while (contains(BB: NextMBB)) {
110 BotMBB = NextMBB;
111 if (BotMBB == &*std::next(x: BotMBB->getIterator()))
112 break;
113 NextMBB = &*std::next(x: BotMBB->getIterator());
114 }
115 }
116 return BotMBB;
117}
118
119MachineBasicBlock *MachineLoop::findLoopControlBlock() const {
120 if (MachineBasicBlock *Latch = getLoopLatch()) {
121 if (isLoopExiting(BB: Latch))
122 return Latch;
123 else
124 return getExitingBlock();
125 }
126 return nullptr;
127}
128
129DebugLoc MachineLoop::getStartLoc() const {
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
145MachineBasicBlock *
146MachineLoopInfo::findLoopPreheader(MachineLoop *L, bool SpeculativePreheader,
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;
174 MachineLoop *T = getLoopFor(BB: S);
175 if (T && T->getHeader() == S)
176 return nullptr;
177 }
178 }
179 return Preheader;
180}
181
182MDNode *MachineLoop::getLoopID() const {
183 MDNode *LoopID = nullptr;
184
185 // Go through the latch blocks and check the terminator for the metadata
186 SmallVector<MachineBasicBlock *, 4> LatchesBlocks;
187 getLoopLatches(LoopLatches&: LatchesBlocks);
188 for (const auto *MBB : LatchesBlocks) {
189 const auto *BB = MBB->getBasicBlock();
190 if (!BB)
191 return nullptr;
192 const auto *TI = BB->getTerminator();
193 if (!TI)
194 return nullptr;
195
196 MDNode *MD = TI->getMetadata(KindID: LLVMContext::MD_loop);
197 if (!MD)
198 return nullptr;
199
200 if (!LoopID)
201 LoopID = MD;
202 else if (MD != LoopID)
203 return nullptr;
204 }
205
206 if (!LoopID || LoopID->getNumOperands() == 0 ||
207 LoopID->getOperand(I: 0) != LoopID)
208 return nullptr;
209
210 return LoopID;
211}
212
213bool MachineLoop::isLoopInvariantImplicitPhysReg(Register Reg) const {
214 MachineFunction *MF = getHeader()->getParent();
215 MachineRegisterInfo *MRI = &MF->getRegInfo();
216
217 if (MRI->isConstantPhysReg(PhysReg: Reg))
218 return true;
219
220 if (!MF->getSubtarget()
221 .getRegisterInfo()
222 ->shouldAnalyzePhysregInMachineLoopInfo(R: Reg))
223 return false;
224
225 return !llvm::any_of(
226 Range: MRI->def_instructions(Reg),
227 P: [this](const MachineInstr &MI) { return this->contains(Inst: &MI); });
228}
229
230bool MachineLoop::isLoopInvariant(MachineInstr &I,
231 const Register ExcludeReg) const {
232 MachineFunction *MF = I.getParent()->getParent();
233 MachineRegisterInfo *MRI = &MF->getRegInfo();
234 const TargetSubtargetInfo &ST = MF->getSubtarget();
235 const TargetRegisterInfo *TRI = ST.getRegisterInfo();
236 const TargetInstrInfo *TII = ST.getInstrInfo();
237
238 // The instruction is loop invariant if all of its operands are.
239 for (const MachineOperand &MO : I.operands()) {
240 if (!MO.isReg())
241 continue;
242
243 Register Reg = MO.getReg();
244 if (Reg == 0) continue;
245
246 if (ExcludeReg == Reg)
247 continue;
248
249 // An instruction that uses or defines a physical register can't e.g. be
250 // hoisted, so mark this as not invariant.
251 if (Reg.isPhysical()) {
252 if (MO.isUse()) {
253 // If the physreg has no defs anywhere, it's just an ambient register
254 // and we can freely move its uses. Alternatively, if it's allocatable,
255 // it could get allocated to something with a def during allocation.
256 // However, if the physreg is known to always be caller saved/restored
257 // then this use is safe to hoist.
258 if (!isLoopInvariantImplicitPhysReg(Reg) &&
259 !(TRI->isCallerPreservedPhysReg(PhysReg: Reg.asMCReg(), MF: *I.getMF())) &&
260 !TII->isIgnorableUse(MO))
261 return false;
262 // Otherwise it's safe to move.
263 continue;
264 } else if (!MO.isDead()) {
265 // A def that isn't dead can't be moved.
266 return false;
267 } else if (getHeader()->isLiveIn(Reg)) {
268 // If the reg is live into the loop, we can't hoist an instruction
269 // which would clobber it.
270 return false;
271 }
272 }
273
274 if (!MO.readsReg())
275 continue;
276
277 assert(MRI->getVRegDef(Reg) &&
278 "Machine instr not mapped for this vreg?!");
279
280 // If the loop contains the definition of an operand, then the instruction
281 // isn't loop invariant.
282 if (contains(Inst: MRI->getVRegDef(Reg)))
283 return false;
284 }
285
286 // If we got this far, the instruction is loop invariant!
287 return true;
288}
289
290#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
291LLVM_DUMP_METHOD void MachineLoop::dump() const {
292 print(dbgs());
293}
294#endif
295