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