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/ADT/SetVector.h" 16 #include "llvm/Analysis/LazyBlockFrequencyInfo.h" 17 #include "llvm/Analysis/ProfileSummaryInfo.h" 18 #include "llvm/CodeGen/GlobalISel/GISelChangeObserver.h" 19 #include "llvm/CodeGen/GlobalISel/GISelKnownBits.h" 20 #include "llvm/CodeGen/GlobalISel/InstructionSelector.h" 21 #include "llvm/CodeGen/GlobalISel/LegalizerInfo.h" 22 #include "llvm/CodeGen/GlobalISel/Utils.h" 23 #include "llvm/CodeGen/MachineFrameInfo.h" 24 #include "llvm/CodeGen/MachineOptimizationRemarkEmitter.h" 25 #include "llvm/CodeGen/MachineRegisterInfo.h" 26 #include "llvm/CodeGen/TargetLowering.h" 27 #include "llvm/CodeGen/TargetOpcodes.h" 28 #include "llvm/CodeGen/TargetPassConfig.h" 29 #include "llvm/CodeGen/TargetSubtargetInfo.h" 30 #include "llvm/Config/config.h" 31 #include "llvm/IR/Function.h" 32 #include "llvm/MC/TargetRegistry.h" 33 #include "llvm/Support/CodeGenCoverage.h" 34 #include "llvm/Support/Debug.h" 35 #include "llvm/Support/DebugCounter.h" 36 #include "llvm/Target/TargetMachine.h" 37 38 #define DEBUG_TYPE "instruction-select" 39 40 using namespace llvm; 41 42 DEBUG_COUNTER(GlobalISelCounter, "globalisel", 43 "Controls whether to select function with GlobalISel"); 44 45 #ifdef LLVM_GISEL_COV_PREFIX 46 static cl::opt<std::string> 47 CoveragePrefix("gisel-coverage-prefix", cl::init(LLVM_GISEL_COV_PREFIX), 48 cl::desc("Record GlobalISel rule coverage files of this " 49 "prefix if instrumentation was generated")); 50 #else 51 static const std::string CoveragePrefix; 52 #endif 53 54 char InstructionSelect::ID = 0; 55 INITIALIZE_PASS_BEGIN(InstructionSelect, DEBUG_TYPE, 56 "Select target instructions out of generic instructions", 57 false, false) 58 INITIALIZE_PASS_DEPENDENCY(TargetPassConfig) 59 INITIALIZE_PASS_DEPENDENCY(GISelKnownBitsAnalysis) 60 INITIALIZE_PASS_DEPENDENCY(ProfileSummaryInfoWrapperPass) 61 INITIALIZE_PASS_DEPENDENCY(LazyBlockFrequencyInfoPass) 62 INITIALIZE_PASS_END(InstructionSelect, DEBUG_TYPE, 63 "Select target instructions out of generic instructions", 64 false, false) 65 66 InstructionSelect::InstructionSelect(CodeGenOptLevel OL, char &PassID) 67 : MachineFunctionPass(PassID), OptLevel(OL) {} 68 69 /// This class observes instruction insertions/removals. 70 /// InstructionSelect stores an iterator of the instruction prior to the one 71 /// that is currently being selected to determine which instruction to select 72 /// next. Previously this meant that selecting multiple instructions at once was 73 /// illegal behavior due to potential invalidation of this iterator. This is 74 /// a non-obvious limitation for selector implementers. Therefore, to allow 75 /// deletion of arbitrary instructions, we detect this case and continue 76 /// selection with the predecessor of the deleted instruction. 77 class InstructionSelect::MIIteratorMaintainer : public GISelChangeObserver { 78 #ifndef NDEBUG 79 SmallSetVector<const MachineInstr *, 32> CreatedInstrs; 80 #endif 81 public: 82 MachineBasicBlock::reverse_iterator MII; 83 84 void changingInstr(MachineInstr &MI) override { 85 llvm_unreachable("InstructionSelect does not track changed instructions!"); 86 } 87 void changedInstr(MachineInstr &MI) override { 88 llvm_unreachable("InstructionSelect does not track changed instructions!"); 89 } 90 91 void createdInstr(MachineInstr &MI) override { 92 LLVM_DEBUG(dbgs() << "Creating: " << MI; CreatedInstrs.insert(&MI)); 93 } 94 95 void erasingInstr(MachineInstr &MI) override { 96 LLVM_DEBUG(dbgs() << "Erasing: " << MI; CreatedInstrs.remove(&MI)); 97 if (MII.getInstrIterator().getNodePtr() == &MI) { 98 // If the iterator points to the MI that will be erased (i.e. the MI prior 99 // to the MI that is currently being selected), the iterator would be 100 // invalidated. Continue selection with its predecessor. 101 ++MII; 102 LLVM_DEBUG(dbgs() << "Instruction removal updated iterator.\n"); 103 } 104 } 105 106 void reportFullyCreatedInstrs() { 107 LLVM_DEBUG({ 108 if (CreatedInstrs.empty()) { 109 dbgs() << "Created no instructions.\n"; 110 } else { 111 dbgs() << "Created:\n"; 112 for (const auto *MI : CreatedInstrs) { 113 dbgs() << " " << *MI; 114 } 115 CreatedInstrs.clear(); 116 } 117 }); 118 } 119 }; 120 121 void InstructionSelect::getAnalysisUsage(AnalysisUsage &AU) const { 122 AU.addRequired<TargetPassConfig>(); 123 AU.addRequired<GISelKnownBitsAnalysis>(); 124 AU.addPreserved<GISelKnownBitsAnalysis>(); 125 126 if (OptLevel != CodeGenOptLevel::None) { 127 AU.addRequired<ProfileSummaryInfoWrapperPass>(); 128 LazyBlockFrequencyInfoPass::getLazyBFIAnalysisUsage(AU); 129 } 130 getSelectionDAGFallbackAnalysisUsage(AU); 131 MachineFunctionPass::getAnalysisUsage(AU); 132 } 133 134 bool InstructionSelect::runOnMachineFunction(MachineFunction &MF) { 135 // If the ISel pipeline failed, do not bother running that pass. 136 if (MF.getProperties().hasProperty( 137 MachineFunctionProperties::Property::FailedISel)) 138 return false; 139 140 ISel = MF.getSubtarget().getInstructionSelector(); 141 ISel->TPC = &getAnalysis<TargetPassConfig>(); 142 143 // FIXME: Properly override OptLevel in TargetMachine. See OptLevelChanger 144 CodeGenOptLevel OldOptLevel = OptLevel; 145 auto RestoreOptLevel = make_scope_exit([=]() { OptLevel = OldOptLevel; }); 146 OptLevel = MF.getFunction().hasOptNone() ? CodeGenOptLevel::None 147 : MF.getTarget().getOptLevel(); 148 149 KB = &getAnalysis<GISelKnownBitsAnalysis>().get(MF); 150 if (OptLevel != CodeGenOptLevel::None) { 151 PSI = &getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI(); 152 if (PSI && PSI->hasProfileSummary()) 153 BFI = &getAnalysis<LazyBlockFrequencyInfoPass>().getBFI(); 154 } 155 156 return selectMachineFunction(MF); 157 } 158 159 bool InstructionSelect::selectMachineFunction(MachineFunction &MF) { 160 LLVM_DEBUG(dbgs() << "Selecting function: " << MF.getName() << '\n'); 161 assert(ISel && "Cannot work without InstructionSelector"); 162 163 const TargetPassConfig &TPC = *ISel->TPC; 164 CodeGenCoverage CoverageInfo; 165 ISel->setupMF(MF, KB, &CoverageInfo, PSI, BFI); 166 167 // An optimization remark emitter. Used to report failures. 168 MachineOptimizationRemarkEmitter MORE(MF, /*MBFI=*/nullptr); 169 ISel->MORE = &MORE; 170 171 // FIXME: There are many other MF/MFI fields we need to initialize. 172 173 MachineRegisterInfo &MRI = MF.getRegInfo(); 174 #ifndef NDEBUG 175 // Check that our input is fully legal: we require the function to have the 176 // Legalized property, so it should be. 177 // FIXME: This should be in the MachineVerifier, as the RegBankSelected 178 // property check already is. 179 if (!DisableGISelLegalityCheck) 180 if (const MachineInstr *MI = machineFunctionIsIllegal(MF)) { 181 reportGISelFailure(MF, TPC, MORE, "gisel-select", 182 "instruction is not legal", *MI); 183 return false; 184 } 185 // FIXME: We could introduce new blocks and will need to fix the outer loop. 186 // Until then, keep track of the number of blocks to assert that we don't. 187 const size_t NumBlocks = MF.size(); 188 #endif 189 // Keep track of selected blocks, so we can delete unreachable ones later. 190 DenseSet<MachineBasicBlock *> SelectedBlocks; 191 192 { 193 // Observe IR insertions and removals during selection. 194 // We only install a MachineFunction::Delegate instead of a 195 // GISelChangeObserver, because we do not want notifications about changed 196 // instructions. This prevents significant compile-time regressions from 197 // e.g. constrainOperandRegClass(). 198 GISelObserverWrapper AllObservers; 199 MIIteratorMaintainer MIIMaintainer; 200 AllObservers.addObserver(&MIIMaintainer); 201 RAIIDelegateInstaller DelInstaller(MF, &AllObservers); 202 ISel->AllObservers = &AllObservers; 203 204 for (MachineBasicBlock *MBB : post_order(&MF)) { 205 ISel->CurMBB = MBB; 206 SelectedBlocks.insert(MBB); 207 208 // Select instructions in reverse block order. 209 MIIMaintainer.MII = MBB->rbegin(); 210 for (auto End = MBB->rend(); MIIMaintainer.MII != End;) { 211 MachineInstr &MI = *MIIMaintainer.MII; 212 // Increment early to skip instructions inserted by select(). 213 ++MIIMaintainer.MII; 214 215 LLVM_DEBUG(dbgs() << "\nSelect: " << MI); 216 if (!selectInstr(MI)) { 217 LLVM_DEBUG(dbgs() << "Selection failed!\n"; 218 MIIMaintainer.reportFullyCreatedInstrs()); 219 reportGISelFailure(MF, TPC, MORE, "gisel-select", "cannot select", 220 MI); 221 return false; 222 } 223 LLVM_DEBUG(MIIMaintainer.reportFullyCreatedInstrs()); 224 } 225 } 226 } 227 228 for (MachineBasicBlock &MBB : MF) { 229 if (MBB.empty()) 230 continue; 231 232 if (!SelectedBlocks.contains(&MBB)) { 233 // This is an unreachable block and therefore hasn't been selected, since 234 // the main selection loop above uses a postorder block traversal. 235 // We delete all the instructions in this block since it's unreachable. 236 MBB.clear(); 237 // Don't delete the block in case the block has it's address taken or is 238 // still being referenced by a phi somewhere. 239 continue; 240 } 241 // Try to find redundant copies b/w vregs of the same register class. 242 for (auto MII = MBB.rbegin(), End = MBB.rend(); MII != End;) { 243 MachineInstr &MI = *MII; 244 ++MII; 245 246 if (MI.getOpcode() != TargetOpcode::COPY) 247 continue; 248 Register SrcReg = MI.getOperand(1).getReg(); 249 Register DstReg = MI.getOperand(0).getReg(); 250 if (SrcReg.isVirtual() && DstReg.isVirtual()) { 251 auto SrcRC = MRI.getRegClass(SrcReg); 252 auto DstRC = MRI.getRegClass(DstReg); 253 if (SrcRC == DstRC) { 254 MRI.replaceRegWith(DstReg, SrcReg); 255 MI.eraseFromParent(); 256 } 257 } 258 } 259 } 260 261 #ifndef NDEBUG 262 const TargetRegisterInfo &TRI = *MF.getSubtarget().getRegisterInfo(); 263 // Now that selection is complete, there are no more generic vregs. Verify 264 // that the size of the now-constrained vreg is unchanged and that it has a 265 // register class. 266 for (unsigned I = 0, E = MRI.getNumVirtRegs(); I != E; ++I) { 267 Register VReg = Register::index2VirtReg(I); 268 269 MachineInstr *MI = nullptr; 270 if (!MRI.def_empty(VReg)) 271 MI = &*MRI.def_instr_begin(VReg); 272 else if (!MRI.use_empty(VReg)) { 273 MI = &*MRI.use_instr_begin(VReg); 274 // Debug value instruction is permitted to use undefined vregs. 275 if (MI->isDebugValue()) 276 continue; 277 } 278 if (!MI) 279 continue; 280 281 const TargetRegisterClass *RC = MRI.getRegClassOrNull(VReg); 282 if (!RC) { 283 reportGISelFailure(MF, TPC, MORE, "gisel-select", 284 "VReg has no regclass after selection", *MI); 285 return false; 286 } 287 288 const LLT Ty = MRI.getType(VReg); 289 if (Ty.isValid() && 290 TypeSize::isKnownGT(Ty.getSizeInBits(), TRI.getRegSizeInBits(*RC))) { 291 reportGISelFailure( 292 MF, TPC, MORE, "gisel-select", 293 "VReg's low-level type and register class have different sizes", *MI); 294 return false; 295 } 296 } 297 298 if (MF.size() != NumBlocks) { 299 MachineOptimizationRemarkMissed R("gisel-select", "GISelFailure", 300 MF.getFunction().getSubprogram(), 301 /*MBB=*/nullptr); 302 R << "inserting blocks is not supported yet"; 303 reportGISelFailure(MF, TPC, MORE, R); 304 return false; 305 } 306 #endif 307 308 if (!DebugCounter::shouldExecute(GlobalISelCounter)) { 309 dbgs() << "Falling back for function " << MF.getName() << "\n"; 310 MF.getProperties().set(MachineFunctionProperties::Property::FailedISel); 311 return false; 312 } 313 314 // Determine if there are any calls in this machine function. Ported from 315 // SelectionDAG. 316 MachineFrameInfo &MFI = MF.getFrameInfo(); 317 for (const auto &MBB : MF) { 318 if (MFI.hasCalls() && MF.hasInlineAsm()) 319 break; 320 321 for (const auto &MI : MBB) { 322 if ((MI.isCall() && !MI.isReturn()) || MI.isStackAligningInlineAsm()) 323 MFI.setHasCalls(true); 324 if (MI.isInlineAsm()) 325 MF.setHasInlineAsm(true); 326 } 327 } 328 329 // FIXME: FinalizeISel pass calls finalizeLowering, so it's called twice. 330 auto &TLI = *MF.getSubtarget().getTargetLowering(); 331 TLI.finalizeLowering(MF); 332 333 LLVM_DEBUG({ 334 dbgs() << "Rules covered by selecting function: " << MF.getName() << ":"; 335 for (auto RuleID : CoverageInfo.covered()) 336 dbgs() << " id" << RuleID; 337 dbgs() << "\n\n"; 338 }); 339 CoverageInfo.emit(CoveragePrefix, 340 TLI.getTargetMachine().getTarget().getBackendName()); 341 342 // If we successfully selected the function nothing is going to use the vreg 343 // types after us (otherwise MIRPrinter would need them). Make sure the types 344 // disappear. 345 MRI.clearVirtRegTypes(); 346 347 // FIXME: Should we accurately track changes? 348 return true; 349 } 350 351 bool InstructionSelect::selectInstr(MachineInstr &MI) { 352 MachineRegisterInfo &MRI = ISel->MF->getRegInfo(); 353 354 // We could have folded this instruction away already, making it dead. 355 // If so, erase it. 356 if (isTriviallyDead(MI, MRI)) { 357 LLVM_DEBUG(dbgs() << "Is dead.\n"); 358 salvageDebugInfo(MRI, MI); 359 MI.eraseFromParent(); 360 return true; 361 } 362 363 // Eliminate hints or G_CONSTANT_FOLD_BARRIER. 364 if (isPreISelGenericOptimizationHint(MI.getOpcode()) || 365 MI.getOpcode() == TargetOpcode::G_CONSTANT_FOLD_BARRIER) { 366 auto [DstReg, SrcReg] = MI.getFirst2Regs(); 367 368 // At this point, the destination register class of the op may have 369 // been decided. 370 // 371 // Propagate that through to the source register. 372 const TargetRegisterClass *DstRC = MRI.getRegClassOrNull(DstReg); 373 if (DstRC) 374 MRI.setRegClass(SrcReg, DstRC); 375 assert(canReplaceReg(DstReg, SrcReg, MRI) && 376 "Must be able to replace dst with src!"); 377 MI.eraseFromParent(); 378 MRI.replaceRegWith(DstReg, SrcReg); 379 return true; 380 } 381 382 if (MI.getOpcode() == TargetOpcode::G_INVOKE_REGION_START) { 383 MI.eraseFromParent(); 384 return true; 385 } 386 387 return ISel->select(MI); 388 } 389