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