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