1 | //===- llvm/CodeGen/GlobalISel/InstructionSelect.cpp - InstructionSelect ---==// |
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 | /// \file |
9 | /// This file implements the InstructionSelect class. |
10 | //===----------------------------------------------------------------------===// |
11 | |
12 | #include "llvm/CodeGen/GlobalISel/InstructionSelect.h" |
13 | #include "llvm/ADT/PostOrderIterator.h" |
14 | #include "llvm/ADT/ScopeExit.h" |
15 | #include "llvm/Analysis/LazyBlockFrequencyInfo.h" |
16 | #include "llvm/Analysis/ProfileSummaryInfo.h" |
17 | #include "llvm/CodeGen/GlobalISel/GISelKnownBits.h" |
18 | #include "llvm/CodeGen/GlobalISel/InstructionSelector.h" |
19 | #include "llvm/CodeGen/GlobalISel/LegalizerInfo.h" |
20 | #include "llvm/CodeGen/GlobalISel/Utils.h" |
21 | #include "llvm/CodeGen/MachineFrameInfo.h" |
22 | #include "llvm/CodeGen/MachineOptimizationRemarkEmitter.h" |
23 | #include "llvm/CodeGen/MachineRegisterInfo.h" |
24 | #include "llvm/CodeGen/TargetLowering.h" |
25 | #include "llvm/CodeGen/TargetOpcodes.h" |
26 | #include "llvm/CodeGen/TargetPassConfig.h" |
27 | #include "llvm/CodeGen/TargetSubtargetInfo.h" |
28 | #include "llvm/Config/config.h" |
29 | #include "llvm/IR/Function.h" |
30 | #include "llvm/MC/TargetRegistry.h" |
31 | #include "llvm/Support/CodeGenCoverage.h" |
32 | #include "llvm/Support/CommandLine.h" |
33 | #include "llvm/Support/Debug.h" |
34 | #include "llvm/Support/DebugCounter.h" |
35 | #include "llvm/Target/TargetMachine.h" |
36 | |
37 | #define DEBUG_TYPE "instruction-select" |
38 | |
39 | using namespace llvm; |
40 | |
41 | DEBUG_COUNTER(GlobalISelCounter, "globalisel" , |
42 | "Controls whether to select function with GlobalISel" ); |
43 | |
44 | #ifdef LLVM_GISEL_COV_PREFIX |
45 | static cl::opt<std::string> |
46 | CoveragePrefix("gisel-coverage-prefix" , cl::init(LLVM_GISEL_COV_PREFIX), |
47 | cl::desc("Record GlobalISel rule coverage files of this " |
48 | "prefix if instrumentation was generated" )); |
49 | #else |
50 | static const std::string CoveragePrefix; |
51 | #endif |
52 | |
53 | char InstructionSelect::ID = 0; |
54 | INITIALIZE_PASS_BEGIN(InstructionSelect, DEBUG_TYPE, |
55 | "Select target instructions out of generic instructions" , |
56 | false, false) |
57 | INITIALIZE_PASS_DEPENDENCY(TargetPassConfig) |
58 | INITIALIZE_PASS_DEPENDENCY(GISelKnownBitsAnalysis) |
59 | INITIALIZE_PASS_DEPENDENCY(ProfileSummaryInfoWrapperPass) |
60 | INITIALIZE_PASS_DEPENDENCY(LazyBlockFrequencyInfoPass) |
61 | INITIALIZE_PASS_END(InstructionSelect, DEBUG_TYPE, |
62 | "Select target instructions out of generic instructions" , |
63 | false, false) |
64 | |
65 | InstructionSelect::InstructionSelect(CodeGenOptLevel OL) |
66 | : MachineFunctionPass(ID), OptLevel(OL) {} |
67 | |
68 | // In order not to crash when calling getAnalysis during testing with -run-pass |
69 | // we use the default opt level here instead of None, so that the addRequired() |
70 | // calls are made in getAnalysisUsage(). |
71 | InstructionSelect::InstructionSelect() |
72 | : MachineFunctionPass(ID), OptLevel(CodeGenOptLevel::Default) {} |
73 | |
74 | void InstructionSelect::getAnalysisUsage(AnalysisUsage &AU) const { |
75 | AU.addRequired<TargetPassConfig>(); |
76 | AU.addRequired<GISelKnownBitsAnalysis>(); |
77 | AU.addPreserved<GISelKnownBitsAnalysis>(); |
78 | |
79 | if (OptLevel != CodeGenOptLevel::None) { |
80 | AU.addRequired<ProfileSummaryInfoWrapperPass>(); |
81 | LazyBlockFrequencyInfoPass::getLazyBFIAnalysisUsage(AU); |
82 | } |
83 | getSelectionDAGFallbackAnalysisUsage(AU); |
84 | MachineFunctionPass::getAnalysisUsage(AU); |
85 | } |
86 | |
87 | bool InstructionSelect::runOnMachineFunction(MachineFunction &MF) { |
88 | // If the ISel pipeline failed, do not bother running that pass. |
89 | if (MF.getProperties().hasProperty( |
90 | P: MachineFunctionProperties::Property::FailedISel)) |
91 | return false; |
92 | |
93 | LLVM_DEBUG(dbgs() << "Selecting function: " << MF.getName() << '\n'); |
94 | |
95 | const TargetPassConfig &TPC = getAnalysis<TargetPassConfig>(); |
96 | InstructionSelector *ISel = MF.getSubtarget().getInstructionSelector(); |
97 | ISel->setTargetPassConfig(&TPC); |
98 | |
99 | CodeGenOptLevel OldOptLevel = OptLevel; |
100 | auto RestoreOptLevel = make_scope_exit(F: [=]() { OptLevel = OldOptLevel; }); |
101 | OptLevel = MF.getFunction().hasOptNone() ? CodeGenOptLevel::None |
102 | : MF.getTarget().getOptLevel(); |
103 | |
104 | GISelKnownBits *KB = &getAnalysis<GISelKnownBitsAnalysis>().get(MF); |
105 | if (OptLevel != CodeGenOptLevel::None) { |
106 | PSI = &getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI(); |
107 | if (PSI && PSI->hasProfileSummary()) |
108 | BFI = &getAnalysis<LazyBlockFrequencyInfoPass>().getBFI(); |
109 | } |
110 | |
111 | CodeGenCoverage CoverageInfo; |
112 | assert(ISel && "Cannot work without InstructionSelector" ); |
113 | ISel->setupMF(mf&: MF, kb: KB, covinfo: &CoverageInfo, psi: PSI, bfi: BFI); |
114 | |
115 | // An optimization remark emitter. Used to report failures. |
116 | MachineOptimizationRemarkEmitter MORE(MF, /*MBFI=*/nullptr); |
117 | ISel->setRemarkEmitter(&MORE); |
118 | |
119 | // FIXME: There are many other MF/MFI fields we need to initialize. |
120 | |
121 | MachineRegisterInfo &MRI = MF.getRegInfo(); |
122 | #ifndef NDEBUG |
123 | // Check that our input is fully legal: we require the function to have the |
124 | // Legalized property, so it should be. |
125 | // FIXME: This should be in the MachineVerifier, as the RegBankSelected |
126 | // property check already is. |
127 | if (!DisableGISelLegalityCheck) |
128 | if (const MachineInstr *MI = machineFunctionIsIllegal(MF)) { |
129 | reportGISelFailure(MF, TPC, MORE, PassName: "gisel-select" , |
130 | Msg: "instruction is not legal" , MI: *MI); |
131 | return false; |
132 | } |
133 | // FIXME: We could introduce new blocks and will need to fix the outer loop. |
134 | // Until then, keep track of the number of blocks to assert that we don't. |
135 | const size_t NumBlocks = MF.size(); |
136 | #endif |
137 | // Keep track of selected blocks, so we can delete unreachable ones later. |
138 | DenseSet<MachineBasicBlock *> SelectedBlocks; |
139 | |
140 | for (MachineBasicBlock *MBB : post_order(G: &MF)) { |
141 | ISel->CurMBB = MBB; |
142 | SelectedBlocks.insert(V: MBB); |
143 | if (MBB->empty()) |
144 | continue; |
145 | |
146 | // Select instructions in reverse block order. We permit erasing so have |
147 | // to resort to manually iterating and recognizing the begin (rend) case. |
148 | bool ReachedBegin = false; |
149 | for (auto MII = std::prev(x: MBB->end()), Begin = MBB->begin(); |
150 | !ReachedBegin;) { |
151 | #ifndef NDEBUG |
152 | // Keep track of the insertion range for debug printing. |
153 | const auto AfterIt = std::next(x: MII); |
154 | #endif |
155 | // Select this instruction. |
156 | MachineInstr &MI = *MII; |
157 | |
158 | // And have our iterator point to the next instruction, if there is one. |
159 | if (MII == Begin) |
160 | ReachedBegin = true; |
161 | else |
162 | --MII; |
163 | |
164 | LLVM_DEBUG(dbgs() << "Selecting: \n " << MI); |
165 | |
166 | // We could have folded this instruction away already, making it dead. |
167 | // If so, erase it. |
168 | if (isTriviallyDead(MI, MRI)) { |
169 | LLVM_DEBUG(dbgs() << "Is dead; erasing.\n" ); |
170 | salvageDebugInfo(MRI, MI); |
171 | MI.eraseFromParent(); |
172 | continue; |
173 | } |
174 | |
175 | // Eliminate hints or G_CONSTANT_FOLD_BARRIER. |
176 | if (isPreISelGenericOptimizationHint(Opcode: MI.getOpcode()) || |
177 | MI.getOpcode() == TargetOpcode::G_CONSTANT_FOLD_BARRIER) { |
178 | auto [DstReg, SrcReg] = MI.getFirst2Regs(); |
179 | |
180 | // At this point, the destination register class of the op may have |
181 | // been decided. |
182 | // |
183 | // Propagate that through to the source register. |
184 | const TargetRegisterClass *DstRC = MRI.getRegClassOrNull(Reg: DstReg); |
185 | if (DstRC) |
186 | MRI.setRegClass(Reg: SrcReg, RC: DstRC); |
187 | assert(canReplaceReg(DstReg, SrcReg, MRI) && |
188 | "Must be able to replace dst with src!" ); |
189 | MI.eraseFromParent(); |
190 | MRI.replaceRegWith(FromReg: DstReg, ToReg: SrcReg); |
191 | continue; |
192 | } |
193 | |
194 | if (MI.getOpcode() == TargetOpcode::G_INVOKE_REGION_START) { |
195 | MI.eraseFromParent(); |
196 | continue; |
197 | } |
198 | |
199 | if (!ISel->select(I&: MI)) { |
200 | // FIXME: It would be nice to dump all inserted instructions. It's |
201 | // not obvious how, esp. considering select() can insert after MI. |
202 | reportGISelFailure(MF, TPC, MORE, PassName: "gisel-select" , Msg: "cannot select" , MI); |
203 | return false; |
204 | } |
205 | |
206 | // Dump the range of instructions that MI expanded into. |
207 | LLVM_DEBUG({ |
208 | auto InsertedBegin = ReachedBegin ? MBB->begin() : std::next(MII); |
209 | dbgs() << "Into:\n" ; |
210 | for (auto &InsertedMI : make_range(InsertedBegin, AfterIt)) |
211 | dbgs() << " " << InsertedMI; |
212 | dbgs() << '\n'; |
213 | }); |
214 | } |
215 | } |
216 | |
217 | for (MachineBasicBlock &MBB : MF) { |
218 | if (MBB.empty()) |
219 | continue; |
220 | |
221 | if (!SelectedBlocks.contains(V: &MBB)) { |
222 | // This is an unreachable block and therefore hasn't been selected, since |
223 | // the main selection loop above uses a postorder block traversal. |
224 | // We delete all the instructions in this block since it's unreachable. |
225 | MBB.clear(); |
226 | // Don't delete the block in case the block has it's address taken or is |
227 | // still being referenced by a phi somewhere. |
228 | continue; |
229 | } |
230 | // Try to find redundant copies b/w vregs of the same register class. |
231 | bool ReachedBegin = false; |
232 | for (auto MII = std::prev(x: MBB.end()), Begin = MBB.begin(); !ReachedBegin;) { |
233 | // Select this instruction. |
234 | MachineInstr &MI = *MII; |
235 | |
236 | // And have our iterator point to the next instruction, if there is one. |
237 | if (MII == Begin) |
238 | ReachedBegin = true; |
239 | else |
240 | --MII; |
241 | if (MI.getOpcode() != TargetOpcode::COPY) |
242 | continue; |
243 | Register SrcReg = MI.getOperand(i: 1).getReg(); |
244 | Register DstReg = MI.getOperand(i: 0).getReg(); |
245 | if (SrcReg.isVirtual() && DstReg.isVirtual()) { |
246 | auto SrcRC = MRI.getRegClass(Reg: SrcReg); |
247 | auto DstRC = MRI.getRegClass(Reg: DstReg); |
248 | if (SrcRC == DstRC) { |
249 | MRI.replaceRegWith(FromReg: DstReg, ToReg: SrcReg); |
250 | MI.eraseFromParent(); |
251 | } |
252 | } |
253 | } |
254 | } |
255 | |
256 | #ifndef NDEBUG |
257 | const TargetRegisterInfo &TRI = *MF.getSubtarget().getRegisterInfo(); |
258 | // Now that selection is complete, there are no more generic vregs. Verify |
259 | // that the size of the now-constrained vreg is unchanged and that it has a |
260 | // register class. |
261 | for (unsigned I = 0, E = MRI.getNumVirtRegs(); I != E; ++I) { |
262 | Register VReg = Register::index2VirtReg(Index: I); |
263 | |
264 | MachineInstr *MI = nullptr; |
265 | if (!MRI.def_empty(RegNo: VReg)) |
266 | MI = &*MRI.def_instr_begin(RegNo: VReg); |
267 | else if (!MRI.use_empty(RegNo: VReg)) { |
268 | MI = &*MRI.use_instr_begin(RegNo: VReg); |
269 | // Debug value instruction is permitted to use undefined vregs. |
270 | if (MI->isDebugValue()) |
271 | continue; |
272 | } |
273 | if (!MI) |
274 | continue; |
275 | |
276 | const TargetRegisterClass *RC = MRI.getRegClassOrNull(Reg: VReg); |
277 | if (!RC) { |
278 | reportGISelFailure(MF, TPC, MORE, PassName: "gisel-select" , |
279 | Msg: "VReg has no regclass after selection" , MI: *MI); |
280 | return false; |
281 | } |
282 | |
283 | const LLT Ty = MRI.getType(Reg: VReg); |
284 | if (Ty.isValid() && |
285 | TypeSize::isKnownGT(LHS: Ty.getSizeInBits(), RHS: TRI.getRegSizeInBits(RC: *RC))) { |
286 | reportGISelFailure( |
287 | MF, TPC, MORE, PassName: "gisel-select" , |
288 | Msg: "VReg's low-level type and register class have different sizes" , MI: *MI); |
289 | return false; |
290 | } |
291 | } |
292 | |
293 | if (MF.size() != NumBlocks) { |
294 | MachineOptimizationRemarkMissed R("gisel-select" , "GISelFailure" , |
295 | MF.getFunction().getSubprogram(), |
296 | /*MBB=*/nullptr); |
297 | R << "inserting blocks is not supported yet" ; |
298 | reportGISelFailure(MF, TPC, MORE, R); |
299 | return false; |
300 | } |
301 | #endif |
302 | |
303 | if (!DebugCounter::shouldExecute(CounterName: GlobalISelCounter)) { |
304 | dbgs() << "Falling back for function " << MF.getName() << "\n" ; |
305 | MF.getProperties().set(MachineFunctionProperties::Property::FailedISel); |
306 | return false; |
307 | } |
308 | |
309 | // Determine if there are any calls in this machine function. Ported from |
310 | // SelectionDAG. |
311 | MachineFrameInfo &MFI = MF.getFrameInfo(); |
312 | for (const auto &MBB : MF) { |
313 | if (MFI.hasCalls() && MF.hasInlineAsm()) |
314 | break; |
315 | |
316 | for (const auto &MI : MBB) { |
317 | if ((MI.isCall() && !MI.isReturn()) || MI.isStackAligningInlineAsm()) |
318 | MFI.setHasCalls(true); |
319 | if (MI.isInlineAsm()) |
320 | MF.setHasInlineAsm(true); |
321 | } |
322 | } |
323 | |
324 | // FIXME: FinalizeISel pass calls finalizeLowering, so it's called twice. |
325 | auto &TLI = *MF.getSubtarget().getTargetLowering(); |
326 | TLI.finalizeLowering(MF); |
327 | |
328 | LLVM_DEBUG({ |
329 | dbgs() << "Rules covered by selecting function: " << MF.getName() << ":" ; |
330 | for (auto RuleID : CoverageInfo.covered()) |
331 | dbgs() << " id" << RuleID; |
332 | dbgs() << "\n\n" ; |
333 | }); |
334 | CoverageInfo.emit(FilePrefix: CoveragePrefix, |
335 | BackendName: TLI.getTargetMachine().getTarget().getBackendName()); |
336 | |
337 | // If we successfully selected the function nothing is going to use the vreg |
338 | // types after us (otherwise MIRPrinter would need them). Make sure the types |
339 | // disappear. |
340 | MRI.clearVirtRegTypes(); |
341 | |
342 | // FIXME: Should we accurately track changes? |
343 | return true; |
344 | } |
345 | |