xref: /freebsd/contrib/llvm-project/llvm/lib/CodeGen/GlobalISel/InstructionSelect.cpp (revision 7029da5c36f2d3cf6bb6c81bf551229f416399e8)
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/Twine.h"
15 #include "llvm/CodeGen/GlobalISel/InstructionSelector.h"
16 #include "llvm/CodeGen/GlobalISel/LegalizerInfo.h"
17 #include "llvm/CodeGen/GlobalISel/Utils.h"
18 #include "llvm/CodeGen/MachineOptimizationRemarkEmitter.h"
19 #include "llvm/CodeGen/MachineRegisterInfo.h"
20 #include "llvm/CodeGen/TargetLowering.h"
21 #include "llvm/CodeGen/TargetPassConfig.h"
22 #include "llvm/CodeGen/TargetSubtargetInfo.h"
23 #include "llvm/Config/config.h"
24 #include "llvm/IR/Constants.h"
25 #include "llvm/IR/Function.h"
26 #include "llvm/Support/CommandLine.h"
27 #include "llvm/Support/Debug.h"
28 #include "llvm/Support/TargetRegistry.h"
29 
30 #define DEBUG_TYPE "instruction-select"
31 
32 using namespace llvm;
33 
34 #ifdef LLVM_GISEL_COV_PREFIX
35 static cl::opt<std::string>
36     CoveragePrefix("gisel-coverage-prefix", cl::init(LLVM_GISEL_COV_PREFIX),
37                    cl::desc("Record GlobalISel rule coverage files of this "
38                             "prefix if instrumentation was generated"));
39 #else
40 static const std::string CoveragePrefix = "";
41 #endif
42 
43 char InstructionSelect::ID = 0;
44 INITIALIZE_PASS_BEGIN(InstructionSelect, DEBUG_TYPE,
45                       "Select target instructions out of generic instructions",
46                       false, false)
47 INITIALIZE_PASS_DEPENDENCY(TargetPassConfig)
48 INITIALIZE_PASS_END(InstructionSelect, DEBUG_TYPE,
49                     "Select target instructions out of generic instructions",
50                     false, false)
51 
52 InstructionSelect::InstructionSelect() : MachineFunctionPass(ID) { }
53 
54 void InstructionSelect::getAnalysisUsage(AnalysisUsage &AU) const {
55   AU.addRequired<TargetPassConfig>();
56   getSelectionDAGFallbackAnalysisUsage(AU);
57   MachineFunctionPass::getAnalysisUsage(AU);
58 }
59 
60 bool InstructionSelect::runOnMachineFunction(MachineFunction &MF) {
61   // If the ISel pipeline failed, do not bother running that pass.
62   if (MF.getProperties().hasProperty(
63           MachineFunctionProperties::Property::FailedISel))
64     return false;
65 
66   LLVM_DEBUG(dbgs() << "Selecting function: " << MF.getName() << '\n');
67 
68   const TargetPassConfig &TPC = getAnalysis<TargetPassConfig>();
69   const InstructionSelector *ISel = MF.getSubtarget().getInstructionSelector();
70   CodeGenCoverage CoverageInfo;
71   assert(ISel && "Cannot work without InstructionSelector");
72 
73   // An optimization remark emitter. Used to report failures.
74   MachineOptimizationRemarkEmitter MORE(MF, /*MBFI=*/nullptr);
75 
76   // FIXME: There are many other MF/MFI fields we need to initialize.
77 
78   MachineRegisterInfo &MRI = MF.getRegInfo();
79 #ifndef NDEBUG
80   // Check that our input is fully legal: we require the function to have the
81   // Legalized property, so it should be.
82   // FIXME: This should be in the MachineVerifier, as the RegBankSelected
83   // property check already is.
84   if (!DisableGISelLegalityCheck)
85     if (const MachineInstr *MI = machineFunctionIsIllegal(MF)) {
86       reportGISelFailure(MF, TPC, MORE, "gisel-select",
87                          "instruction is not legal", *MI);
88       return false;
89     }
90   // FIXME: We could introduce new blocks and will need to fix the outer loop.
91   // Until then, keep track of the number of blocks to assert that we don't.
92   const size_t NumBlocks = MF.size();
93 #endif
94 
95   for (MachineBasicBlock *MBB : post_order(&MF)) {
96     if (MBB->empty())
97       continue;
98 
99     // Select instructions in reverse block order. We permit erasing so have
100     // to resort to manually iterating and recognizing the begin (rend) case.
101     bool ReachedBegin = false;
102     for (auto MII = std::prev(MBB->end()), Begin = MBB->begin();
103          !ReachedBegin;) {
104 #ifndef NDEBUG
105       // Keep track of the insertion range for debug printing.
106       const auto AfterIt = std::next(MII);
107 #endif
108       // Select this instruction.
109       MachineInstr &MI = *MII;
110 
111       // And have our iterator point to the next instruction, if there is one.
112       if (MII == Begin)
113         ReachedBegin = true;
114       else
115         --MII;
116 
117       LLVM_DEBUG(dbgs() << "Selecting: \n  " << MI);
118 
119       // We could have folded this instruction away already, making it dead.
120       // If so, erase it.
121       if (isTriviallyDead(MI, MRI)) {
122         LLVM_DEBUG(dbgs() << "Is dead; erasing.\n");
123         MI.eraseFromParentAndMarkDBGValuesForRemoval();
124         continue;
125       }
126 
127       if (!ISel->select(MI, CoverageInfo)) {
128         // FIXME: It would be nice to dump all inserted instructions.  It's
129         // not obvious how, esp. considering select() can insert after MI.
130         reportGISelFailure(MF, TPC, MORE, "gisel-select", "cannot select", MI);
131         return false;
132       }
133 
134       // Dump the range of instructions that MI expanded into.
135       LLVM_DEBUG({
136         auto InsertedBegin = ReachedBegin ? MBB->begin() : std::next(MII);
137         dbgs() << "Into:\n";
138         for (auto &InsertedMI : make_range(InsertedBegin, AfterIt))
139           dbgs() << "  " << InsertedMI;
140         dbgs() << '\n';
141       });
142     }
143   }
144 
145   for (MachineBasicBlock &MBB : MF) {
146     if (MBB.empty())
147       continue;
148 
149     // Try to find redundant copies b/w vregs of the same register class.
150     bool ReachedBegin = false;
151     for (auto MII = std::prev(MBB.end()), Begin = MBB.begin(); !ReachedBegin;) {
152       // Select this instruction.
153       MachineInstr &MI = *MII;
154 
155       // And have our iterator point to the next instruction, if there is one.
156       if (MII == Begin)
157         ReachedBegin = true;
158       else
159         --MII;
160       if (MI.getOpcode() != TargetOpcode::COPY)
161         continue;
162       unsigned SrcReg = MI.getOperand(1).getReg();
163       unsigned DstReg = MI.getOperand(0).getReg();
164       if (TargetRegisterInfo::isVirtualRegister(SrcReg) &&
165           TargetRegisterInfo::isVirtualRegister(DstReg)) {
166         auto SrcRC = MRI.getRegClass(SrcReg);
167         auto DstRC = MRI.getRegClass(DstReg);
168         if (SrcRC == DstRC) {
169           MRI.replaceRegWith(DstReg, SrcReg);
170           MI.eraseFromParentAndMarkDBGValuesForRemoval();
171         }
172       }
173     }
174   }
175 
176 #ifndef NDEBUG
177   const TargetRegisterInfo &TRI = *MF.getSubtarget().getRegisterInfo();
178   // Now that selection is complete, there are no more generic vregs.  Verify
179   // that the size of the now-constrained vreg is unchanged and that it has a
180   // register class.
181   for (unsigned I = 0, E = MRI.getNumVirtRegs(); I != E; ++I) {
182     unsigned VReg = TargetRegisterInfo::index2VirtReg(I);
183 
184     MachineInstr *MI = nullptr;
185     if (!MRI.def_empty(VReg))
186       MI = &*MRI.def_instr_begin(VReg);
187     else if (!MRI.use_empty(VReg))
188       MI = &*MRI.use_instr_begin(VReg);
189     if (!MI)
190       continue;
191 
192     const TargetRegisterClass *RC = MRI.getRegClassOrNull(VReg);
193     if (!RC) {
194       reportGISelFailure(MF, TPC, MORE, "gisel-select",
195                          "VReg has no regclass after selection", *MI);
196       return false;
197     }
198 
199     const LLT Ty = MRI.getType(VReg);
200     if (Ty.isValid() && Ty.getSizeInBits() > TRI.getRegSizeInBits(*RC)) {
201       reportGISelFailure(
202           MF, TPC, MORE, "gisel-select",
203           "VReg's low-level type and register class have different sizes", *MI);
204       return false;
205     }
206   }
207 
208   if (MF.size() != NumBlocks) {
209     MachineOptimizationRemarkMissed R("gisel-select", "GISelFailure",
210                                       MF.getFunction().getSubprogram(),
211                                       /*MBB=*/nullptr);
212     R << "inserting blocks is not supported yet";
213     reportGISelFailure(MF, TPC, MORE, R);
214     return false;
215   }
216 #endif
217   auto &TLI = *MF.getSubtarget().getTargetLowering();
218   TLI.finalizeLowering(MF);
219 
220   LLVM_DEBUG({
221     dbgs() << "Rules covered by selecting function: " << MF.getName() << ":";
222     for (auto RuleID : CoverageInfo.covered())
223       dbgs() << " id" << RuleID;
224     dbgs() << "\n\n";
225   });
226   CoverageInfo.emit(CoveragePrefix,
227                     MF.getSubtarget()
228                         .getTargetLowering()
229                         ->getTargetMachine()
230                         .getTarget()
231                         .getBackendName());
232 
233   // If we successfully selected the function nothing is going to use the vreg
234   // types after us (otherwise MIRPrinter would need them). Make sure the types
235   // disappear.
236   MRI.clearVirtRegTypes();
237 
238   // FIXME: Should we accurately track changes?
239   return true;
240 }
241