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