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 | char MachineLoopInfo::ID = 0; |
34 | MachineLoopInfo::MachineLoopInfo() : MachineFunctionPass(ID) { |
35 | initializeMachineLoopInfoPass(*PassRegistry::getPassRegistry()); |
36 | } |
37 | INITIALIZE_PASS_BEGIN(MachineLoopInfo, "machine-loops" , |
38 | "Machine Natural Loop Construction" , true, true) |
39 | INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree) |
40 | INITIALIZE_PASS_END(MachineLoopInfo, "machine-loops" , |
41 | "Machine Natural Loop Construction" , true, true) |
42 | |
43 | char &llvm::MachineLoopInfoID = MachineLoopInfo::ID; |
44 | |
45 | bool MachineLoopInfo::runOnMachineFunction(MachineFunction &) { |
46 | calculate(MDT&: getAnalysis<MachineDominatorTree>()); |
47 | return false; |
48 | } |
49 | |
50 | void MachineLoopInfo::calculate(MachineDominatorTree &MDT) { |
51 | releaseMemory(); |
52 | LI.analyze(DomTree: MDT.getBase()); |
53 | } |
54 | |
55 | void MachineLoopInfo::getAnalysisUsage(AnalysisUsage &AU) const { |
56 | AU.setPreservesAll(); |
57 | AU.addRequired<MachineDominatorTree>(); |
58 | MachineFunctionPass::getAnalysisUsage(AU); |
59 | } |
60 | |
61 | MachineBasicBlock *MachineLoop::getTopBlock() { |
62 | MachineBasicBlock *TopMBB = getHeader(); |
63 | MachineFunction::iterator Begin = TopMBB->getParent()->begin(); |
64 | if (TopMBB->getIterator() != Begin) { |
65 | MachineBasicBlock *PriorMBB = &*std::prev(x: TopMBB->getIterator()); |
66 | while (contains(BB: PriorMBB)) { |
67 | TopMBB = PriorMBB; |
68 | if (TopMBB->getIterator() == Begin) |
69 | break; |
70 | PriorMBB = &*std::prev(x: TopMBB->getIterator()); |
71 | } |
72 | } |
73 | return TopMBB; |
74 | } |
75 | |
76 | MachineBasicBlock *MachineLoop::getBottomBlock() { |
77 | MachineBasicBlock *BotMBB = getHeader(); |
78 | MachineFunction::iterator End = BotMBB->getParent()->end(); |
79 | if (BotMBB->getIterator() != std::prev(x: End)) { |
80 | MachineBasicBlock *NextMBB = &*std::next(x: BotMBB->getIterator()); |
81 | while (contains(BB: NextMBB)) { |
82 | BotMBB = NextMBB; |
83 | if (BotMBB == &*std::next(x: BotMBB->getIterator())) |
84 | break; |
85 | NextMBB = &*std::next(x: BotMBB->getIterator()); |
86 | } |
87 | } |
88 | return BotMBB; |
89 | } |
90 | |
91 | MachineBasicBlock *MachineLoop::findLoopControlBlock() const { |
92 | if (MachineBasicBlock *Latch = getLoopLatch()) { |
93 | if (isLoopExiting(BB: Latch)) |
94 | return Latch; |
95 | else |
96 | return getExitingBlock(); |
97 | } |
98 | return nullptr; |
99 | } |
100 | |
101 | DebugLoc MachineLoop::getStartLoc() const { |
102 | // Try the pre-header first. |
103 | if (MachineBasicBlock *PHeadMBB = getLoopPreheader()) |
104 | if (const BasicBlock *PHeadBB = PHeadMBB->getBasicBlock()) |
105 | if (DebugLoc DL = PHeadBB->getTerminator()->getDebugLoc()) |
106 | return DL; |
107 | |
108 | // If we have no pre-header or there are no instructions with debug |
109 | // info in it, try the header. |
110 | if (MachineBasicBlock *HeadMBB = getHeader()) |
111 | if (const BasicBlock *HeadBB = HeadMBB->getBasicBlock()) |
112 | return HeadBB->getTerminator()->getDebugLoc(); |
113 | |
114 | return DebugLoc(); |
115 | } |
116 | |
117 | MachineBasicBlock * |
118 | MachineLoopInfo::(MachineLoop *L, bool , |
119 | bool ) const { |
120 | if (MachineBasicBlock *PB = L->getLoopPreheader()) |
121 | return PB; |
122 | |
123 | if (!SpeculativePreheader) |
124 | return nullptr; |
125 | |
126 | MachineBasicBlock *HB = L->getHeader(), *LB = L->getLoopLatch(); |
127 | if (HB->pred_size() != 2 || HB->hasAddressTaken()) |
128 | return nullptr; |
129 | // Find the predecessor of the header that is not the latch block. |
130 | MachineBasicBlock * = nullptr; |
131 | for (MachineBasicBlock *P : HB->predecessors()) { |
132 | if (P == LB) |
133 | continue; |
134 | // Sanity. |
135 | if (Preheader) |
136 | return nullptr; |
137 | Preheader = P; |
138 | } |
139 | |
140 | // Check if the preheader candidate is a successor of any other loop |
141 | // headers. We want to avoid having two loop setups in the same block. |
142 | if (!FindMultiLoopPreheader) { |
143 | for (MachineBasicBlock *S : Preheader->successors()) { |
144 | if (S == HB) |
145 | continue; |
146 | MachineLoop *T = getLoopFor(BB: S); |
147 | if (T && T->getHeader() == S) |
148 | return nullptr; |
149 | } |
150 | } |
151 | return Preheader; |
152 | } |
153 | |
154 | MDNode *MachineLoop::getLoopID() const { |
155 | MDNode *LoopID = nullptr; |
156 | if (const auto *MBB = findLoopControlBlock()) { |
157 | // If there is a single latch block, then the metadata |
158 | // node is attached to its terminating instruction. |
159 | const auto *BB = MBB->getBasicBlock(); |
160 | if (!BB) |
161 | return nullptr; |
162 | if (const auto *TI = BB->getTerminator()) |
163 | LoopID = TI->getMetadata(KindID: LLVMContext::MD_loop); |
164 | } else if (const auto *MBB = getHeader()) { |
165 | // There seem to be multiple latch blocks, so we have to |
166 | // visit all predecessors of the loop header and check |
167 | // their terminating instructions for the metadata. |
168 | if (const auto * = MBB->getBasicBlock()) { |
169 | // Walk over all blocks in the loop. |
170 | for (const auto *MBB : this->blocks()) { |
171 | const auto *BB = MBB->getBasicBlock(); |
172 | if (!BB) |
173 | return nullptr; |
174 | const auto *TI = BB->getTerminator(); |
175 | if (!TI) |
176 | return nullptr; |
177 | MDNode *MD = nullptr; |
178 | // Check if this terminating instruction jumps to the loop header. |
179 | for (const auto *Succ : successors(I: TI)) { |
180 | if (Succ == Header) { |
181 | // This is a jump to the header - gather the metadata from it. |
182 | MD = TI->getMetadata(KindID: LLVMContext::MD_loop); |
183 | break; |
184 | } |
185 | } |
186 | if (!MD) |
187 | return nullptr; |
188 | if (!LoopID) |
189 | LoopID = MD; |
190 | else if (MD != LoopID) |
191 | return nullptr; |
192 | } |
193 | } |
194 | } |
195 | if (LoopID && |
196 | (LoopID->getNumOperands() == 0 || LoopID->getOperand(I: 0) != LoopID)) |
197 | LoopID = nullptr; |
198 | return LoopID; |
199 | } |
200 | |
201 | bool MachineLoop::isLoopInvariant(MachineInstr &I) const { |
202 | MachineFunction *MF = I.getParent()->getParent(); |
203 | MachineRegisterInfo *MRI = &MF->getRegInfo(); |
204 | const TargetSubtargetInfo &ST = MF->getSubtarget(); |
205 | const TargetRegisterInfo *TRI = ST.getRegisterInfo(); |
206 | const TargetInstrInfo *TII = ST.getInstrInfo(); |
207 | |
208 | // The instruction is loop invariant if all of its operands are. |
209 | for (const MachineOperand &MO : I.operands()) { |
210 | if (!MO.isReg()) |
211 | continue; |
212 | |
213 | Register Reg = MO.getReg(); |
214 | if (Reg == 0) continue; |
215 | |
216 | // An instruction that uses or defines a physical register can't e.g. be |
217 | // hoisted, so mark this as not invariant. |
218 | if (Reg.isPhysical()) { |
219 | if (MO.isUse()) { |
220 | // If the physreg has no defs anywhere, it's just an ambient register |
221 | // and we can freely move its uses. Alternatively, if it's allocatable, |
222 | // it could get allocated to something with a def during allocation. |
223 | // However, if the physreg is known to always be caller saved/restored |
224 | // then this use is safe to hoist. |
225 | if (!MRI->isConstantPhysReg(PhysReg: Reg) && |
226 | !(TRI->isCallerPreservedPhysReg(PhysReg: Reg.asMCReg(), MF: *I.getMF())) && |
227 | !TII->isIgnorableUse(MO)) |
228 | return false; |
229 | // Otherwise it's safe to move. |
230 | continue; |
231 | } else if (!MO.isDead()) { |
232 | // A def that isn't dead can't be moved. |
233 | return false; |
234 | } else if (getHeader()->isLiveIn(Reg)) { |
235 | // If the reg is live into the loop, we can't hoist an instruction |
236 | // which would clobber it. |
237 | return false; |
238 | } |
239 | } |
240 | |
241 | if (!MO.isUse()) |
242 | continue; |
243 | |
244 | assert(MRI->getVRegDef(Reg) && |
245 | "Machine instr not mapped for this vreg?!" ); |
246 | |
247 | // If the loop contains the definition of an operand, then the instruction |
248 | // isn't loop invariant. |
249 | if (contains(Inst: MRI->getVRegDef(Reg))) |
250 | return false; |
251 | } |
252 | |
253 | // If we got this far, the instruction is loop invariant! |
254 | return true; |
255 | } |
256 | |
257 | #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) |
258 | LLVM_DUMP_METHOD void MachineLoop::dump() const { |
259 | print(OS&: dbgs()); |
260 | } |
261 | #endif |
262 | |