xref: /freebsd/contrib/llvm-project/llvm/lib/CodeGen/MachineLoopInfo.cpp (revision 56b17de1e8360fe131d425de20b5e75ff3ea897c)
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/GenericLoopInfoImpl.h"
26 
27 using namespace llvm;
28 
29 // Explicitly instantiate methods in LoopInfoImpl.h for MI-level Loops.
30 template class llvm::LoopBase<MachineBasicBlock, MachineLoop>;
31 template class llvm::LoopInfoBase<MachineBasicBlock, MachineLoop>;
32 
33 AnalysisKey MachineLoopAnalysis::Key;
34 
35 MachineLoopAnalysis::Result
36 MachineLoopAnalysis::run(MachineFunction &MF,
37                          MachineFunctionAnalysisManager &MFAM) {
38   return MachineLoopInfo(MFAM.getResult<MachineDominatorTreeAnalysis>(MF));
39 }
40 
41 PreservedAnalyses
42 MachineLoopPrinterPass::run(MachineFunction &MF,
43                             MachineFunctionAnalysisManager &MFAM) {
44   OS << "Machine loop info for machine function '" << MF.getName() << "':\n";
45   MFAM.getResult<MachineLoopAnalysis>(MF).print(OS);
46   return PreservedAnalyses::all();
47 }
48 
49 char MachineLoopInfoWrapperPass::ID = 0;
50 MachineLoopInfoWrapperPass::MachineLoopInfoWrapperPass()
51     : MachineFunctionPass(ID) {
52   initializeMachineLoopInfoWrapperPassPass(*PassRegistry::getPassRegistry());
53 }
54 INITIALIZE_PASS_BEGIN(MachineLoopInfoWrapperPass, "machine-loops",
55                       "Machine Natural Loop Construction", true, true)
56 INITIALIZE_PASS_DEPENDENCY(MachineDominatorTreeWrapperPass)
57 INITIALIZE_PASS_END(MachineLoopInfoWrapperPass, "machine-loops",
58                     "Machine Natural Loop Construction", true, true)
59 
60 char &llvm::MachineLoopInfoID = MachineLoopInfoWrapperPass::ID;
61 
62 bool MachineLoopInfoWrapperPass::runOnMachineFunction(MachineFunction &) {
63   LI.calculate(getAnalysis<MachineDominatorTreeWrapperPass>().getDomTree());
64   return false;
65 }
66 
67 bool 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 
78 void MachineLoopInfo::calculate(MachineDominatorTree &MDT) {
79   releaseMemory();
80   analyze(MDT.getBase());
81 }
82 
83 void MachineLoopInfoWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const {
84   AU.setPreservesAll();
85   AU.addRequired<MachineDominatorTreeWrapperPass>();
86   MachineFunctionPass::getAnalysisUsage(AU);
87 }
88 
89 MachineBasicBlock *MachineLoop::getTopBlock() {
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 
104 MachineBasicBlock *MachineLoop::getBottomBlock() {
105   MachineBasicBlock *BotMBB = getHeader();
106   MachineFunction::iterator End = BotMBB->getParent()->end();
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 
119 MachineBasicBlock *MachineLoop::findLoopControlBlock() const {
120   if (MachineBasicBlock *Latch = getLoopLatch()) {
121     if (isLoopExiting(Latch))
122       return Latch;
123     else
124       return getExitingBlock();
125   }
126   return nullptr;
127 }
128 
129 DebugLoc 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 
145 MachineBasicBlock *
146 MachineLoopInfo::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(S);
175       if (T && T->getHeader() == S)
176         return nullptr;
177     }
178   }
179   return Preheader;
180 }
181 
182 MDNode *MachineLoop::getLoopID() const {
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 
229 bool MachineLoop::isLoopInvariantImplicitPhysReg(Register Reg) const {
230   MachineFunction *MF = getHeader()->getParent();
231   MachineRegisterInfo *MRI = &MF->getRegInfo();
232 
233   if (MRI->isConstantPhysReg(Reg))
234     return true;
235 
236   if (!MF->getSubtarget()
237            .getRegisterInfo()
238            ->shouldAnalyzePhysregInMachineLoopInfo(Reg))
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 
246 bool MachineLoop::isLoopInvariant(MachineInstr &I,
247                                   const Register ExcludeReg) const {
248   MachineFunction *MF = I.getParent()->getParent();
249   MachineRegisterInfo *MRI = &MF->getRegInfo();
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)
307 LLVM_DUMP_METHOD void MachineLoop::dump() const {
308   print(dbgs());
309 }
310 #endif
311