1 //===- llvm/CodeGen/GlobalISel/InstructionSelect.cpp - InstructionSelect ---==//
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
7 //===----------------------------------------------------------------------===//
9 /// This file implements the InstructionSelect class.
10 //===----------------------------------------------------------------------===//
12 #include "llvm/CodeGen/GlobalISel/InstructionSelect.h"
13 #include "llvm/ADT/PostOrderIterator.h"
14 #include "llvm/ADT/Twine.h"
15 #include "llvm/CodeGen/GlobalISel/GISelKnownBits.h"
16 #include "llvm/CodeGen/GlobalISel/InstructionSelector.h"
17 #include "llvm/CodeGen/GlobalISel/LegalizerInfo.h"
18 #include "llvm/CodeGen/GlobalISel/Utils.h"
19 #include "llvm/CodeGen/MachineOptimizationRemarkEmitter.h"
20 #include "llvm/CodeGen/MachineFrameInfo.h"
21 #include "llvm/CodeGen/MachineRegisterInfo.h"
22 #include "llvm/CodeGen/TargetInstrInfo.h"
23 #include "llvm/CodeGen/TargetLowering.h"
24 #include "llvm/CodeGen/TargetPassConfig.h"
25 #include "llvm/CodeGen/TargetSubtargetInfo.h"
26 #include "llvm/Config/config.h"
27 #include "llvm/IR/Constants.h"
28 #include "llvm/IR/Function.h"
29 #include "llvm/Support/CommandLine.h"
30 #include "llvm/Support/Debug.h"
31 #include "llvm/Support/TargetRegistry.h"
33 #define DEBUG_TYPE "instruction-select"
37 #ifdef LLVM_GISEL_COV_PREFIX
38 static cl::opt<std::string>
39 CoveragePrefix("gisel-coverage-prefix", cl::init(LLVM_GISEL_COV_PREFIX),
40 cl::desc("Record GlobalISel rule coverage files of this "
41 "prefix if instrumentation was generated"));
43 static const std::string CoveragePrefix = "";
46 char InstructionSelect::ID = 0;
47 INITIALIZE_PASS_BEGIN(InstructionSelect, DEBUG_TYPE,
48 "Select target instructions out of generic instructions",
50 INITIALIZE_PASS_DEPENDENCY(TargetPassConfig)
51 INITIALIZE_PASS_DEPENDENCY(GISelKnownBitsAnalysis)
52 INITIALIZE_PASS_END(InstructionSelect, DEBUG_TYPE,
53 "Select target instructions out of generic instructions",
56 InstructionSelect::InstructionSelect() : MachineFunctionPass(ID) { }
58 void InstructionSelect::getAnalysisUsage(AnalysisUsage &AU) const {
59 AU.addRequired<TargetPassConfig>();
60 AU.addRequired<GISelKnownBitsAnalysis>();
61 AU.addPreserved<GISelKnownBitsAnalysis>();
62 getSelectionDAGFallbackAnalysisUsage(AU);
63 MachineFunctionPass::getAnalysisUsage(AU);
66 bool InstructionSelect::runOnMachineFunction(MachineFunction &MF) {
67 // If the ISel pipeline failed, do not bother running that pass.
68 if (MF.getProperties().hasProperty(
69 MachineFunctionProperties::Property::FailedISel))
72 LLVM_DEBUG(dbgs() << "Selecting function: " << MF.getName() << '\n');
73 GISelKnownBits &KB = getAnalysis<GISelKnownBitsAnalysis>().get(MF);
75 const TargetPassConfig &TPC = getAnalysis<TargetPassConfig>();
76 InstructionSelector *ISel = MF.getSubtarget().getInstructionSelector();
77 CodeGenCoverage CoverageInfo;
78 assert(ISel && "Cannot work without InstructionSelector");
79 ISel->setupMF(MF, KB, CoverageInfo);
81 // An optimization remark emitter. Used to report failures.
82 MachineOptimizationRemarkEmitter MORE(MF, /*MBFI=*/nullptr);
84 // FIXME: There are many other MF/MFI fields we need to initialize.
86 MachineRegisterInfo &MRI = MF.getRegInfo();
88 // Check that our input is fully legal: we require the function to have the
89 // Legalized property, so it should be.
90 // FIXME: This should be in the MachineVerifier, as the RegBankSelected
91 // property check already is.
92 if (!DisableGISelLegalityCheck)
93 if (const MachineInstr *MI = machineFunctionIsIllegal(MF)) {
94 reportGISelFailure(MF, TPC, MORE, "gisel-select",
95 "instruction is not legal", *MI);
98 // FIXME: We could introduce new blocks and will need to fix the outer loop.
99 // Until then, keep track of the number of blocks to assert that we don't.
100 const size_t NumBlocks = MF.size();
103 for (MachineBasicBlock *MBB : post_order(&MF)) {
107 // Select instructions in reverse block order. We permit erasing so have
108 // to resort to manually iterating and recognizing the begin (rend) case.
109 bool ReachedBegin = false;
110 for (auto MII = std::prev(MBB->end()), Begin = MBB->begin();
113 // Keep track of the insertion range for debug printing.
114 const auto AfterIt = std::next(MII);
116 // Select this instruction.
117 MachineInstr &MI = *MII;
119 // And have our iterator point to the next instruction, if there is one.
125 LLVM_DEBUG(dbgs() << "Selecting: \n " << MI);
127 // We could have folded this instruction away already, making it dead.
129 if (isTriviallyDead(MI, MRI)) {
130 LLVM_DEBUG(dbgs() << "Is dead; erasing.\n");
131 MI.eraseFromParentAndMarkDBGValuesForRemoval();
135 if (!ISel->select(MI)) {
136 // FIXME: It would be nice to dump all inserted instructions. It's
137 // not obvious how, esp. considering select() can insert after MI.
138 reportGISelFailure(MF, TPC, MORE, "gisel-select", "cannot select", MI);
142 // Dump the range of instructions that MI expanded into.
144 auto InsertedBegin = ReachedBegin ? MBB->begin() : std::next(MII);
146 for (auto &InsertedMI : make_range(InsertedBegin, AfterIt))
147 dbgs() << " " << InsertedMI;
153 for (MachineBasicBlock &MBB : MF) {
157 // Try to find redundant copies b/w vregs of the same register class.
158 bool ReachedBegin = false;
159 for (auto MII = std::prev(MBB.end()), Begin = MBB.begin(); !ReachedBegin;) {
160 // Select this instruction.
161 MachineInstr &MI = *MII;
163 // And have our iterator point to the next instruction, if there is one.
168 if (MI.getOpcode() != TargetOpcode::COPY)
170 Register SrcReg = MI.getOperand(1).getReg();
171 Register DstReg = MI.getOperand(0).getReg();
172 if (Register::isVirtualRegister(SrcReg) &&
173 Register::isVirtualRegister(DstReg)) {
174 auto SrcRC = MRI.getRegClass(SrcReg);
175 auto DstRC = MRI.getRegClass(DstReg);
176 if (SrcRC == DstRC) {
177 MRI.replaceRegWith(DstReg, SrcReg);
178 MI.eraseFromParentAndMarkDBGValuesForRemoval();
185 const TargetRegisterInfo &TRI = *MF.getSubtarget().getRegisterInfo();
186 // Now that selection is complete, there are no more generic vregs. Verify
187 // that the size of the now-constrained vreg is unchanged and that it has a
189 for (unsigned I = 0, E = MRI.getNumVirtRegs(); I != E; ++I) {
190 unsigned VReg = Register::index2VirtReg(I);
192 MachineInstr *MI = nullptr;
193 if (!MRI.def_empty(VReg))
194 MI = &*MRI.def_instr_begin(VReg);
195 else if (!MRI.use_empty(VReg))
196 MI = &*MRI.use_instr_begin(VReg);
200 const TargetRegisterClass *RC = MRI.getRegClassOrNull(VReg);
202 reportGISelFailure(MF, TPC, MORE, "gisel-select",
203 "VReg has no regclass after selection", *MI);
207 const LLT Ty = MRI.getType(VReg);
208 if (Ty.isValid() && Ty.getSizeInBits() > TRI.getRegSizeInBits(*RC)) {
210 MF, TPC, MORE, "gisel-select",
211 "VReg's low-level type and register class have different sizes", *MI);
216 if (MF.size() != NumBlocks) {
217 MachineOptimizationRemarkMissed R("gisel-select", "GISelFailure",
218 MF.getFunction().getSubprogram(),
220 R << "inserting blocks is not supported yet";
221 reportGISelFailure(MF, TPC, MORE, R);
225 auto &TLI = *MF.getSubtarget().getTargetLowering();
226 TLI.finalizeLowering(MF);
228 // Determine if there are any calls in this machine function. Ported from
230 MachineFrameInfo &MFI = MF.getFrameInfo();
231 for (const auto &MBB : MF) {
232 if (MFI.hasCalls() && MF.hasInlineAsm())
235 for (const auto &MI : MBB) {
236 if ((MI.isCall() && !MI.isReturn()) || MI.isStackAligningInlineAsm())
237 MFI.setHasCalls(true);
238 if (MI.isInlineAsm())
239 MF.setHasInlineAsm(true);
245 dbgs() << "Rules covered by selecting function: " << MF.getName() << ":";
246 for (auto RuleID : CoverageInfo.covered())
247 dbgs() << " id" << RuleID;
250 CoverageInfo.emit(CoveragePrefix,
257 // If we successfully selected the function nothing is going to use the vreg
258 // types after us (otherwise MIRPrinter would need them). Make sure the types
260 MRI.clearVirtRegTypes();
262 // FIXME: Should we accurately track changes?