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/ScopeExit.h" 15 #include "llvm/Analysis/LazyBlockFrequencyInfo.h" 16 #include "llvm/Analysis/ProfileSummaryInfo.h" 17 #include "llvm/CodeGen/GlobalISel/GISelKnownBits.h" 18 #include "llvm/CodeGen/GlobalISel/InstructionSelector.h" 19 #include "llvm/CodeGen/GlobalISel/LegalizerInfo.h" 20 #include "llvm/CodeGen/GlobalISel/Utils.h" 21 #include "llvm/CodeGen/MachineFrameInfo.h" 22 #include "llvm/CodeGen/MachineOptimizationRemarkEmitter.h" 23 #include "llvm/CodeGen/MachineRegisterInfo.h" 24 #include "llvm/CodeGen/TargetLowering.h" 25 #include "llvm/CodeGen/TargetPassConfig.h" 26 #include "llvm/CodeGen/TargetSubtargetInfo.h" 27 #include "llvm/Config/config.h" 28 #include "llvm/IR/Function.h" 29 #include "llvm/MC/TargetRegistry.h" 30 #include "llvm/Support/CodeGenCoverage.h" 31 #include "llvm/Support/CommandLine.h" 32 #include "llvm/Support/Debug.h" 33 #include "llvm/Target/TargetMachine.h" 34 35 #define DEBUG_TYPE "instruction-select" 36 37 using namespace llvm; 38 39 #ifdef LLVM_GISEL_COV_PREFIX 40 static cl::opt<std::string> 41 CoveragePrefix("gisel-coverage-prefix", cl::init(LLVM_GISEL_COV_PREFIX), 42 cl::desc("Record GlobalISel rule coverage files of this " 43 "prefix if instrumentation was generated")); 44 #else 45 static const std::string CoveragePrefix; 46 #endif 47 48 char InstructionSelect::ID = 0; 49 INITIALIZE_PASS_BEGIN(InstructionSelect, DEBUG_TYPE, 50 "Select target instructions out of generic instructions", 51 false, false) 52 INITIALIZE_PASS_DEPENDENCY(TargetPassConfig) 53 INITIALIZE_PASS_DEPENDENCY(GISelKnownBitsAnalysis) 54 INITIALIZE_PASS_DEPENDENCY(ProfileSummaryInfoWrapperPass) 55 INITIALIZE_PASS_DEPENDENCY(LazyBlockFrequencyInfoPass) 56 INITIALIZE_PASS_END(InstructionSelect, DEBUG_TYPE, 57 "Select target instructions out of generic instructions", 58 false, false) 59 60 InstructionSelect::InstructionSelect(CodeGenOpt::Level OL) 61 : MachineFunctionPass(ID), OptLevel(OL) {} 62 63 // In order not to crash when calling getAnalysis during testing with -run-pass 64 // we use the default opt level here instead of None, so that the addRequired() 65 // calls are made in getAnalysisUsage(). 66 InstructionSelect::InstructionSelect() 67 : MachineFunctionPass(ID), OptLevel(CodeGenOpt::Default) {} 68 69 void InstructionSelect::getAnalysisUsage(AnalysisUsage &AU) const { 70 AU.addRequired<TargetPassConfig>(); 71 AU.addRequired<GISelKnownBitsAnalysis>(); 72 AU.addPreserved<GISelKnownBitsAnalysis>(); 73 74 if (OptLevel != CodeGenOpt::None) { 75 AU.addRequired<ProfileSummaryInfoWrapperPass>(); 76 LazyBlockFrequencyInfoPass::getLazyBFIAnalysisUsage(AU); 77 } 78 getSelectionDAGFallbackAnalysisUsage(AU); 79 MachineFunctionPass::getAnalysisUsage(AU); 80 } 81 82 bool InstructionSelect::runOnMachineFunction(MachineFunction &MF) { 83 // If the ISel pipeline failed, do not bother running that pass. 84 if (MF.getProperties().hasProperty( 85 MachineFunctionProperties::Property::FailedISel)) 86 return false; 87 88 LLVM_DEBUG(dbgs() << "Selecting function: " << MF.getName() << '\n'); 89 90 const TargetPassConfig &TPC = getAnalysis<TargetPassConfig>(); 91 InstructionSelector *ISel = MF.getSubtarget().getInstructionSelector(); 92 93 CodeGenOpt::Level OldOptLevel = OptLevel; 94 auto RestoreOptLevel = make_scope_exit([=]() { OptLevel = OldOptLevel; }); 95 OptLevel = MF.getFunction().hasOptNone() ? CodeGenOpt::None 96 : MF.getTarget().getOptLevel(); 97 98 GISelKnownBits *KB = &getAnalysis<GISelKnownBitsAnalysis>().get(MF); 99 if (OptLevel != CodeGenOpt::None) { 100 PSI = &getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI(); 101 if (PSI && PSI->hasProfileSummary()) 102 BFI = &getAnalysis<LazyBlockFrequencyInfoPass>().getBFI(); 103 } 104 105 CodeGenCoverage CoverageInfo; 106 assert(ISel && "Cannot work without InstructionSelector"); 107 ISel->setupMF(MF, KB, CoverageInfo, PSI, BFI); 108 109 // An optimization remark emitter. Used to report failures. 110 MachineOptimizationRemarkEmitter MORE(MF, /*MBFI=*/nullptr); 111 112 // FIXME: There are many other MF/MFI fields we need to initialize. 113 114 MachineRegisterInfo &MRI = MF.getRegInfo(); 115 #ifndef NDEBUG 116 // Check that our input is fully legal: we require the function to have the 117 // Legalized property, so it should be. 118 // FIXME: This should be in the MachineVerifier, as the RegBankSelected 119 // property check already is. 120 if (!DisableGISelLegalityCheck) 121 if (const MachineInstr *MI = machineFunctionIsIllegal(MF)) { 122 reportGISelFailure(MF, TPC, MORE, "gisel-select", 123 "instruction is not legal", *MI); 124 return false; 125 } 126 // FIXME: We could introduce new blocks and will need to fix the outer loop. 127 // Until then, keep track of the number of blocks to assert that we don't. 128 const size_t NumBlocks = MF.size(); 129 #endif 130 // Keep track of selected blocks, so we can delete unreachable ones later. 131 DenseSet<MachineBasicBlock *> SelectedBlocks; 132 133 for (MachineBasicBlock *MBB : post_order(&MF)) { 134 ISel->CurMBB = MBB; 135 SelectedBlocks.insert(MBB); 136 if (MBB->empty()) 137 continue; 138 139 // Select instructions in reverse block order. We permit erasing so have 140 // to resort to manually iterating and recognizing the begin (rend) case. 141 bool ReachedBegin = false; 142 for (auto MII = std::prev(MBB->end()), Begin = MBB->begin(); 143 !ReachedBegin;) { 144 #ifndef NDEBUG 145 // Keep track of the insertion range for debug printing. 146 const auto AfterIt = std::next(MII); 147 #endif 148 // Select this instruction. 149 MachineInstr &MI = *MII; 150 151 // And have our iterator point to the next instruction, if there is one. 152 if (MII == Begin) 153 ReachedBegin = true; 154 else 155 --MII; 156 157 LLVM_DEBUG(dbgs() << "Selecting: \n " << MI); 158 159 // We could have folded this instruction away already, making it dead. 160 // If so, erase it. 161 if (isTriviallyDead(MI, MRI)) { 162 LLVM_DEBUG(dbgs() << "Is dead; erasing.\n"); 163 salvageDebugInfo(MRI, MI); 164 MI.eraseFromParent(); 165 continue; 166 } 167 168 // Eliminate hints. 169 if (isPreISelGenericOptimizationHint(MI.getOpcode())) { 170 Register DstReg = MI.getOperand(0).getReg(); 171 Register SrcReg = MI.getOperand(1).getReg(); 172 173 // At this point, the destination register class of the hint may have 174 // been decided. 175 // 176 // Propagate that through to the source register. 177 const TargetRegisterClass *DstRC = MRI.getRegClassOrNull(DstReg); 178 if (DstRC) 179 MRI.setRegClass(SrcReg, DstRC); 180 assert(canReplaceReg(DstReg, SrcReg, MRI) && 181 "Must be able to replace dst with src!"); 182 MI.eraseFromParent(); 183 MRI.replaceRegWith(DstReg, SrcReg); 184 continue; 185 } 186 187 if (MI.getOpcode() == TargetOpcode::G_INVOKE_REGION_START) { 188 MI.eraseFromParent(); 189 continue; 190 } 191 192 if (!ISel->select(MI)) { 193 // FIXME: It would be nice to dump all inserted instructions. It's 194 // not obvious how, esp. considering select() can insert after MI. 195 reportGISelFailure(MF, TPC, MORE, "gisel-select", "cannot select", MI); 196 return false; 197 } 198 199 // Dump the range of instructions that MI expanded into. 200 LLVM_DEBUG({ 201 auto InsertedBegin = ReachedBegin ? MBB->begin() : std::next(MII); 202 dbgs() << "Into:\n"; 203 for (auto &InsertedMI : make_range(InsertedBegin, AfterIt)) 204 dbgs() << " " << InsertedMI; 205 dbgs() << '\n'; 206 }); 207 } 208 } 209 210 for (MachineBasicBlock &MBB : MF) { 211 if (MBB.empty()) 212 continue; 213 214 if (!SelectedBlocks.contains(&MBB)) { 215 // This is an unreachable block and therefore hasn't been selected, since 216 // the main selection loop above uses a postorder block traversal. 217 // We delete all the instructions in this block since it's unreachable. 218 MBB.clear(); 219 // Don't delete the block in case the block has it's address taken or is 220 // still being referenced by a phi somewhere. 221 continue; 222 } 223 // Try to find redundant copies b/w vregs of the same register class. 224 bool ReachedBegin = false; 225 for (auto MII = std::prev(MBB.end()), Begin = MBB.begin(); !ReachedBegin;) { 226 // Select this instruction. 227 MachineInstr &MI = *MII; 228 229 // And have our iterator point to the next instruction, if there is one. 230 if (MII == Begin) 231 ReachedBegin = true; 232 else 233 --MII; 234 if (MI.getOpcode() != TargetOpcode::COPY) 235 continue; 236 Register SrcReg = MI.getOperand(1).getReg(); 237 Register DstReg = MI.getOperand(0).getReg(); 238 if (SrcReg.isVirtual() && DstReg.isVirtual()) { 239 auto SrcRC = MRI.getRegClass(SrcReg); 240 auto DstRC = MRI.getRegClass(DstReg); 241 if (SrcRC == DstRC) { 242 MRI.replaceRegWith(DstReg, SrcReg); 243 MI.eraseFromParent(); 244 } 245 } 246 } 247 } 248 249 #ifndef NDEBUG 250 const TargetRegisterInfo &TRI = *MF.getSubtarget().getRegisterInfo(); 251 // Now that selection is complete, there are no more generic vregs. Verify 252 // that the size of the now-constrained vreg is unchanged and that it has a 253 // register class. 254 for (unsigned I = 0, E = MRI.getNumVirtRegs(); I != E; ++I) { 255 Register VReg = Register::index2VirtReg(I); 256 257 MachineInstr *MI = nullptr; 258 if (!MRI.def_empty(VReg)) 259 MI = &*MRI.def_instr_begin(VReg); 260 else if (!MRI.use_empty(VReg)) { 261 MI = &*MRI.use_instr_begin(VReg); 262 // Debug value instruction is permitted to use undefined vregs. 263 if (MI->isDebugValue()) 264 continue; 265 } 266 if (!MI) 267 continue; 268 269 const TargetRegisterClass *RC = MRI.getRegClassOrNull(VReg); 270 if (!RC) { 271 reportGISelFailure(MF, TPC, MORE, "gisel-select", 272 "VReg has no regclass after selection", *MI); 273 return false; 274 } 275 276 const LLT Ty = MRI.getType(VReg); 277 if (Ty.isValid() && Ty.getSizeInBits() > TRI.getRegSizeInBits(*RC)) { 278 reportGISelFailure( 279 MF, TPC, MORE, "gisel-select", 280 "VReg's low-level type and register class have different sizes", *MI); 281 return false; 282 } 283 } 284 285 if (MF.size() != NumBlocks) { 286 MachineOptimizationRemarkMissed R("gisel-select", "GISelFailure", 287 MF.getFunction().getSubprogram(), 288 /*MBB=*/nullptr); 289 R << "inserting blocks is not supported yet"; 290 reportGISelFailure(MF, TPC, MORE, R); 291 return false; 292 } 293 #endif 294 // Determine if there are any calls in this machine function. Ported from 295 // SelectionDAG. 296 MachineFrameInfo &MFI = MF.getFrameInfo(); 297 for (const auto &MBB : MF) { 298 if (MFI.hasCalls() && MF.hasInlineAsm()) 299 break; 300 301 for (const auto &MI : MBB) { 302 if ((MI.isCall() && !MI.isReturn()) || MI.isStackAligningInlineAsm()) 303 MFI.setHasCalls(true); 304 if (MI.isInlineAsm()) 305 MF.setHasInlineAsm(true); 306 } 307 } 308 309 // FIXME: FinalizeISel pass calls finalizeLowering, so it's called twice. 310 auto &TLI = *MF.getSubtarget().getTargetLowering(); 311 TLI.finalizeLowering(MF); 312 313 LLVM_DEBUG({ 314 dbgs() << "Rules covered by selecting function: " << MF.getName() << ":"; 315 for (auto RuleID : CoverageInfo.covered()) 316 dbgs() << " id" << RuleID; 317 dbgs() << "\n\n"; 318 }); 319 CoverageInfo.emit(CoveragePrefix, 320 TLI.getTargetMachine().getTarget().getBackendName()); 321 322 // If we successfully selected the function nothing is going to use the vreg 323 // types after us (otherwise MIRPrinter would need them). Make sure the types 324 // disappear. 325 MRI.clearVirtRegTypes(); 326 327 // FIXME: Should we accurately track changes? 328 return true; 329 } 330