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