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/ADT/SetVector.h"
16#include "llvm/Analysis/BlockFrequencyInfo.h"
17#include "llvm/Analysis/LazyBlockFrequencyInfo.h"
18#include "llvm/Analysis/ProfileSummaryInfo.h"
19#include "llvm/CodeGen/GlobalISel/GISelChangeObserver.h"
20#include "llvm/CodeGen/GlobalISel/GISelValueTracking.h"
21#include "llvm/CodeGen/GlobalISel/InstructionSelector.h"
22#include "llvm/CodeGen/GlobalISel/LegalizerInfo.h"
23#include "llvm/CodeGen/GlobalISel/Utils.h"
24#include "llvm/CodeGen/MachineFrameInfo.h"
25#include "llvm/CodeGen/MachineFunctionAnalysisManager.h"
26#include "llvm/CodeGen/MachineOptimizationRemarkEmitter.h"
27#include "llvm/CodeGen/MachinePassManager.h"
28#include "llvm/CodeGen/MachineRegisterInfo.h"
29#include "llvm/CodeGen/TargetLowering.h"
30#include "llvm/CodeGen/TargetOpcodes.h"
31#include "llvm/CodeGen/TargetPassConfig.h"
32#include "llvm/CodeGen/TargetSubtargetInfo.h"
33#include "llvm/Config/config.h"
34#include "llvm/IR/Analysis.h"
35#include "llvm/IR/Function.h"
36#include "llvm/MC/TargetRegistry.h"
37#include "llvm/Support/CodeGen.h"
38#include "llvm/Support/CodeGenCoverage.h"
39#include "llvm/Support/Debug.h"
40#include "llvm/Support/DebugCounter.h"
41#include "llvm/Support/ErrorHandling.h"
42#include "llvm/Target/TargetMachine.h"
43
44#define DEBUG_TYPE "instruction-select"
45
46using namespace llvm;
47
48DEBUG_COUNTER(GlobalISelCounter, "globalisel",
49 "Controls whether to select function with GlobalISel");
50
51#ifdef LLVM_GISEL_COV_PREFIX
52static cl::opt<std::string>
53 CoveragePrefix("gisel-coverage-prefix", cl::init(LLVM_GISEL_COV_PREFIX),
54 cl::desc("Record GlobalISel rule coverage files of this "
55 "prefix if instrumentation was generated"));
56#else
57static const std::string CoveragePrefix;
58#endif
59
60char InstructionSelectLegacy::ID = 0;
61INITIALIZE_PASS_BEGIN(InstructionSelectLegacy, DEBUG_TYPE,
62 "Select target instructions out of generic instructions",
63 false, false)
64INITIALIZE_PASS_DEPENDENCY(TargetPassConfig)
65INITIALIZE_PASS_DEPENDENCY(GISelValueTrackingAnalysisLegacy)
66INITIALIZE_PASS_DEPENDENCY(ProfileSummaryInfoWrapperPass)
67INITIALIZE_PASS_DEPENDENCY(LazyBlockFrequencyInfoPass)
68INITIALIZE_PASS_END(InstructionSelectLegacy, DEBUG_TYPE,
69 "Select target instructions out of generic instructions",
70 false, false)
71
72InstructionSelectLegacy::InstructionSelectLegacy(CodeGenOptLevel OL,
73 bool RequireRegBankSelection,
74 char &PassID)
75 : MachineFunctionPass(PassID), OptLevel(OL),
76 RequireRegBankSelection(RequireRegBankSelection) {}
77
78InstructionSelectPass::InstructionSelectPass(CodeGenOptLevel OL,
79 bool RequireRegBankSelection)
80 : OptLevel(OL), RequireRegBankSelection(RequireRegBankSelection) {}
81
82InstructionSelectImpl::InstructionSelectImpl(CodeGenOptLevel OL)
83 : OptLevel(OL) {}
84
85/// This class observes instruction insertions/removals.
86/// InstructionSelect stores an iterator of the instruction prior to the one
87/// that is currently being selected to determine which instruction to select
88/// next. Previously this meant that selecting multiple instructions at once was
89/// illegal behavior due to potential invalidation of this iterator. This is
90/// a non-obvious limitation for selector implementers. Therefore, to allow
91/// deletion of arbitrary instructions, we detect this case and continue
92/// selection with the predecessor of the deleted instruction.
93class InstructionSelectImpl::MIIteratorMaintainer : public GISelChangeObserver {
94#ifndef NDEBUG
95 SmallSetVector<const MachineInstr *, 32> CreatedInstrs;
96#endif
97public:
98 MachineBasicBlock::reverse_iterator MII;
99
100 void changingInstr(MachineInstr &MI) override {
101 llvm_unreachable("InstructionSelect does not track changed instructions!");
102 }
103 void changedInstr(MachineInstr &MI) override {
104 llvm_unreachable("InstructionSelect does not track changed instructions!");
105 }
106
107 void createdInstr(MachineInstr &MI) override {
108 LLVM_DEBUG(dbgs() << "Creating: " << MI; CreatedInstrs.insert(&MI));
109 }
110
111 void erasingInstr(MachineInstr &MI) override {
112 LLVM_DEBUG(dbgs() << "Erasing: " << MI; CreatedInstrs.remove(&MI));
113 if (MII.getInstrIterator().getNodePtr() == &MI) {
114 // If the iterator points to the MI that will be erased (i.e. the MI prior
115 // to the MI that is currently being selected), the iterator would be
116 // invalidated. Continue selection with its predecessor.
117 ++MII;
118 LLVM_DEBUG(dbgs() << "Instruction removal updated iterator.\n");
119 }
120 }
121
122 void reportFullyCreatedInstrs() {
123 LLVM_DEBUG({
124 if (CreatedInstrs.empty()) {
125 dbgs() << "Created no instructions.\n";
126 } else {
127 dbgs() << "Created:\n";
128 for (const auto *MI : CreatedInstrs) {
129 dbgs() << " " << *MI;
130 }
131 CreatedInstrs.clear();
132 }
133 });
134 }
135};
136
137void InstructionSelectLegacy::getAnalysisUsage(AnalysisUsage &AU) const {
138 AU.addRequired<TargetPassConfig>();
139 AU.addRequired<GISelValueTrackingAnalysisLegacy>();
140 AU.addPreserved<GISelValueTrackingAnalysisLegacy>();
141
142 if (OptLevel != CodeGenOptLevel::None) {
143 AU.addRequired<ProfileSummaryInfoWrapperPass>();
144 LazyBlockFrequencyInfoPass::getLazyBFIAnalysisUsage(AU);
145 }
146 getSelectionDAGFallbackAnalysisUsage(AU);
147 MachineFunctionPass::getAnalysisUsage(AU);
148}
149
150bool InstructionSelectImpl::runOnMachineFunction(
151 MachineFunction &MF, function_ref<GISelValueTracking *()> GetVT,
152 function_ref<ProfileSummaryInfo *()> GetPSI,
153 function_ref<BlockFrequencyInfo *()> GetBFI) {
154 // If the ISel pipeline failed, do not bother running that pass.
155 if (MF.getProperties().hasFailedISel())
156 return false;
157
158 ISel = MF.getSubtarget().getInstructionSelector();
159
160 // FIXME: Properly override OptLevel in TargetMachine. See OptLevelChanger
161 CodeGenOptLevel OldOptLevel = OptLevel;
162 llvm::scope_exit RestoreOptLevel([=]() { OptLevel = OldOptLevel; });
163 OptLevel = MF.getFunction().hasOptNone() ? CodeGenOptLevel::None
164 : MF.getTarget().getOptLevel();
165
166 VT = GetVT();
167 if (OptLevel != CodeGenOptLevel::None) {
168 PSI = GetPSI();
169 if (PSI && PSI->hasProfileSummary())
170 BFI = GetBFI();
171 }
172
173 return selectMachineFunction(MF);
174}
175
176bool InstructionSelectImpl::selectMachineFunction(MachineFunction &MF) {
177 LLVM_DEBUG(dbgs() << "Selecting function: " << MF.getName() << '\n');
178 assert(ISel && "Cannot work without InstructionSelector");
179
180 CodeGenCoverage CoverageInfo;
181 ISel->setupMF(mf&: MF, vt: VT, covinfo: &CoverageInfo, psi: PSI, bfi: BFI);
182
183 // An optimization remark emitter. Used to report failures.
184 MachineOptimizationRemarkEmitter MORE(MF, /*MBFI=*/nullptr);
185 ISel->MORE = &MORE;
186
187 // FIXME: There are many other MF/MFI fields we need to initialize.
188
189 MachineRegisterInfo &MRI = MF.getRegInfo();
190#ifndef NDEBUG
191 // Check that our input is fully legal: we require the function to have the
192 // Legalized property, so it should be.
193 // FIXME: This should be in the MachineVerifier, as the RegBankSelected
194 // property check already is.
195 if (!DisableGISelLegalityCheck)
196 if (const MachineInstr *MI = machineFunctionIsIllegal(MF)) {
197 reportGISelFailure(MF, MORE, "gisel-select", "instruction is not legal",
198 *MI);
199 return false;
200 }
201 // NumBlocks is an invariant to ensure the number of blocks doesn't change.
202 const size_t NumBlocks = MF.size();
203#endif
204 // Keep track of selected blocks, so we can delete unreachable ones later.
205 DenseSet<MachineBasicBlock *> SelectedBlocks;
206
207 {
208 // Observe IR insertions and removals during selection.
209 // We only install a MachineFunction::Delegate instead of a
210 // GISelChangeObserver, because we do not want notifications about changed
211 // instructions. This prevents significant compile-time regressions from
212 // e.g. constrainOperandRegClass().
213 GISelObserverWrapper AllObservers;
214 MIIteratorMaintainer MIIMaintainer;
215 AllObservers.addObserver(O: &MIIMaintainer);
216 RAIIDelegateInstaller DelInstaller(MF, &AllObservers);
217 ISel->AllObservers = &AllObservers;
218
219 for (MachineBasicBlock *MBB : post_order(G: &MF)) {
220 ISel->CurMBB = MBB;
221 SelectedBlocks.insert(V: MBB);
222
223 // Select instructions in reverse block order.
224 MIIMaintainer.MII = MBB->rbegin();
225 for (auto End = MBB->rend(); MIIMaintainer.MII != End;) {
226 MachineInstr &MI = *MIIMaintainer.MII;
227 // Increment early to skip instructions inserted by select().
228 ++MIIMaintainer.MII;
229
230 LLVM_DEBUG(dbgs() << "\nSelect: " << MI);
231 if (!selectInstr(MI)) {
232 LLVM_DEBUG(dbgs() << "Selection failed!\n";
233 MIIMaintainer.reportFullyCreatedInstrs());
234 reportGISelFailure(MF, MORE, PassName: "gisel-select", Msg: "cannot select", MI);
235 return false;
236 }
237 LLVM_DEBUG(MIIMaintainer.reportFullyCreatedInstrs());
238 }
239 }
240 }
241
242 for (MachineBasicBlock &MBB : MF) {
243 if (MBB.empty())
244 continue;
245
246 if (!SelectedBlocks.contains(V: &MBB)) {
247 // This is an unreachable block and therefore hasn't been selected, since
248 // the main selection loop above uses a postorder block traversal.
249 // We delete all the instructions in this block since it's unreachable.
250 MBB.clear();
251 // Don't delete the block in case the block has it's address taken or is
252 // still being referenced by a phi somewhere.
253 continue;
254 }
255 // Try to find redundant copies b/w vregs of the same register class.
256 for (auto MII = MBB.rbegin(), End = MBB.rend(); MII != End;) {
257 MachineInstr &MI = *MII;
258 ++MII;
259
260 if (MI.getOpcode() != TargetOpcode::COPY)
261 continue;
262 Register SrcReg = MI.getOperand(i: 1).getReg();
263 Register DstReg = MI.getOperand(i: 0).getReg();
264 unsigned SrcSubIdx = MI.getOperand(i: 1).getSubReg();
265 if (!SrcReg.isVirtual() || !DstReg.isVirtual() || SrcSubIdx)
266 continue;
267
268 const TargetRegisterClass *SrcRC = MRI.getRegClass(Reg: SrcReg);
269 const TargetRegisterClass *DstRC = MRI.getRegClass(Reg: DstReg);
270 if (SrcRC == DstRC) {
271 MRI.replaceRegWith(FromReg: DstReg, ToReg: SrcReg);
272 MI.eraseFromParent();
273 }
274 }
275 }
276
277#ifndef NDEBUG
278 const TargetRegisterInfo &TRI = *MF.getSubtarget().getRegisterInfo();
279 // Now that selection is complete, there are no more generic vregs. Verify
280 // that the size of the now-constrained vreg is unchanged and that it has a
281 // register class.
282 for (unsigned I = 0, E = MRI.getNumVirtRegs(); I != E; ++I) {
283 Register VReg = Register::index2VirtReg(I);
284
285 MachineInstr *MI = nullptr;
286 if (!MRI.def_empty(VReg))
287 MI = &*MRI.def_instr_begin(VReg);
288 else if (!MRI.use_empty(VReg)) {
289 MI = &*MRI.use_instr_begin(VReg);
290 // Debug value instruction is permitted to use undefined vregs.
291 if (MI->isDebugValue())
292 continue;
293 }
294 if (!MI)
295 continue;
296
297 const TargetRegisterClass *RC = MRI.getRegClassOrNull(VReg);
298 if (!RC) {
299 reportGISelFailure(MF, MORE, "gisel-select",
300 "VReg has no regclass after selection", *MI);
301 return false;
302 }
303
304 const LLT Ty = MRI.getType(VReg);
305 if (Ty.isValid() &&
306 TypeSize::isKnownGT(Ty.getSizeInBits(), TRI.getRegSizeInBits(*RC))) {
307 reportGISelFailure(
308 MF, MORE, "gisel-select",
309 "VReg's low-level type and register class have different sizes", *MI);
310 return false;
311 }
312 }
313
314 if (MF.size() != NumBlocks) {
315 MachineOptimizationRemarkMissed R("gisel-select", "GISelFailure",
316 MF.getFunction().getSubprogram(),
317 /*MBB=*/nullptr);
318 R << "inserting blocks is not supported yet";
319 reportGISelFailure(MF, MORE, R);
320 return false;
321 }
322#endif
323
324 if (!DebugCounter::shouldExecute(Counter&: GlobalISelCounter)) {
325 dbgs() << "Falling back for function " << MF.getName() << "\n";
326 MF.getProperties().setFailedISel();
327 return false;
328 }
329
330 // Determine if there are any calls in this machine function. Ported from
331 // SelectionDAG.
332 MachineFrameInfo &MFI = MF.getFrameInfo();
333 for (const auto &MBB : MF) {
334 if (MFI.hasCalls() && MF.hasInlineAsm())
335 break;
336
337 for (const auto &MI : MBB) {
338 if ((MI.isCall() && !MI.isReturn()) || MI.isStackAligningInlineAsm())
339 MFI.setHasCalls(true);
340 if (MI.isInlineAsm())
341 MF.setHasInlineAsm(true);
342 }
343 }
344
345 // FIXME: FinalizeISel pass calls finalizeLowering, so it's called twice.
346 auto &TLI = *MF.getSubtarget().getTargetLowering();
347 TLI.finalizeLowering(MF);
348
349 LLVM_DEBUG({
350 dbgs() << "Rules covered by selecting function: " << MF.getName() << ":";
351 for (auto RuleID : CoverageInfo.covered())
352 dbgs() << " id" << RuleID;
353 dbgs() << "\n\n";
354 });
355 CoverageInfo.emit(FilePrefix: CoveragePrefix,
356 BackendName: TLI.getTargetMachine().getTarget().getBackendName());
357
358 // If we successfully selected the function nothing is going to use the vreg
359 // types after us (otherwise MIRPrinter would need them). Make sure the types
360 // disappear.
361 MRI.clearVirtRegTypes();
362
363 // FIXME: Should we accurately track changes?
364 return true;
365}
366
367bool InstructionSelectImpl::selectInstr(MachineInstr &MI) {
368 MachineRegisterInfo &MRI = ISel->MF->getRegInfo();
369
370 // We could have folded this instruction away already, making it dead.
371 // If so, erase it.
372 if (isTriviallyDead(MI, MRI)) {
373 LLVM_DEBUG(dbgs() << "Is dead.\n");
374 salvageDebugInfo(MRI, MI);
375 MI.eraseFromParent();
376 return true;
377 }
378
379 // Eliminate hints or G_CONSTANT_FOLD_BARRIER.
380 if (isPreISelGenericOptimizationHint(Opcode: MI.getOpcode()) ||
381 MI.getOpcode() == TargetOpcode::G_CONSTANT_FOLD_BARRIER) {
382 auto [DstReg, SrcReg] = MI.getFirst2Regs();
383
384 // At this point, the destination register class of the op may have
385 // been decided.
386 //
387 // Propagate that through to the source register.
388 const TargetRegisterClass *DstRC = MRI.getRegClassOrNull(Reg: DstReg);
389 const TargetRegisterClass *SrcRC = MRI.getRegClassOrNull(Reg: SrcReg);
390 if (DstRC && SrcRC)
391 MRI.constrainRegClass(Reg: SrcReg, RC: DstRC);
392 else if (DstRC)
393 MRI.setRegClass(Reg: SrcReg, RC: DstRC);
394 MI.eraseFromParent();
395 MRI.replaceRegWith(FromReg: DstReg, ToReg: SrcReg);
396 return true;
397 }
398
399 if (MI.getOpcode() == TargetOpcode::G_INVOKE_REGION_START) {
400 MI.eraseFromParent();
401 return true;
402 }
403
404 return ISel->select(I&: MI);
405}
406
407bool InstructionSelectLegacy::runOnMachineFunction(MachineFunction &MF) {
408 InstructionSelectImpl Impl(OptLevel);
409 return Impl.runOnMachineFunction(
410 MF,
411 GetVT: [&]() {
412 return &getAnalysis<GISelValueTrackingAnalysisLegacy>().get(MF);
413 },
414 GetPSI: [&]() { return &getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI(); },
415 GetBFI: [&]() { return &getAnalysis<LazyBlockFrequencyInfoPass>().getBFI(); });
416}
417
418PreservedAnalyses
419InstructionSelectPass::run(MachineFunction &MF,
420 MachineFunctionAnalysisManager &MFAM) {
421 MFPropsModifier _(*this, MF);
422 InstructionSelectImpl Impl(OptLevel);
423 bool Changed = Impl.runOnMachineFunction(
424 MF, GetVT: [&]() { return &MFAM.getResult<GISelValueTrackingAnalysis>(IR&: MF); },
425 GetPSI: [&]() {
426 ProfileSummaryInfo *PSI =
427 MFAM.getResult<ModuleAnalysisManagerMachineFunctionProxy>(IR&: MF)
428 .getCachedResult<ProfileSummaryAnalysis>(
429 IR&: *MF.getFunction().getParent());
430 if (!PSI)
431 reportFatalUsageError(reason: "instruction-select requires profile-summary");
432 return PSI;
433 },
434 GetBFI: [&]() {
435 return &MFAM.getResult<FunctionAnalysisManagerMachineFunctionProxy>(IR&: MF)
436 .getManager()
437 .getResult<BlockFrequencyAnalysis>(IR&: MF.getFunction());
438 });
439 return Changed ? getMachineFunctionPassPreservedAnalyses()
440 : PreservedAnalyses::all();
441}
442