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