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/MachineOptimizationRemarkEmitter.h" 24 #include "llvm/CodeGen/MachineFrameInfo.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/Support/CommandLine.h" 34 #include "llvm/Support/Debug.h" 35 #include "llvm/Support/TargetRegistry.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 if (OptLevel != CodeGenOpt::None) { 75 AU.addRequired<GISelKnownBitsAnalysis>(); 76 AU.addPreserved<GISelKnownBitsAnalysis>(); 77 AU.addRequired<ProfileSummaryInfoWrapperPass>(); 78 LazyBlockFrequencyInfoPass::getLazyBFIAnalysisUsage(AU); 79 } 80 getSelectionDAGFallbackAnalysisUsage(AU); 81 MachineFunctionPass::getAnalysisUsage(AU); 82 } 83 84 bool InstructionSelect::runOnMachineFunction(MachineFunction &MF) { 85 // If the ISel pipeline failed, do not bother running that pass. 86 if (MF.getProperties().hasProperty( 87 MachineFunctionProperties::Property::FailedISel)) 88 return false; 89 90 LLVM_DEBUG(dbgs() << "Selecting function: " << MF.getName() << '\n'); 91 92 const TargetPassConfig &TPC = getAnalysis<TargetPassConfig>(); 93 InstructionSelector *ISel = MF.getSubtarget().getInstructionSelector(); 94 95 CodeGenOpt::Level OldOptLevel = OptLevel; 96 auto RestoreOptLevel = make_scope_exit([=]() { OptLevel = OldOptLevel; }); 97 OptLevel = MF.getFunction().hasOptNone() ? CodeGenOpt::None 98 : MF.getTarget().getOptLevel(); 99 100 GISelKnownBits *KB = nullptr; 101 if (OptLevel != CodeGenOpt::None) { 102 KB = &getAnalysis<GISelKnownBitsAnalysis>().get(MF); 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 134 for (MachineBasicBlock *MBB : post_order(&MF)) { 135 ISel->CurMBB = 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 MI.eraseFromParentAndMarkDBGValuesForRemoval(); 164 continue; 165 } 166 167 // Eliminate hints. 168 if (isPreISelGenericOptimizationHint(MI.getOpcode())) { 169 Register DstReg = MI.getOperand(0).getReg(); 170 Register SrcReg = MI.getOperand(1).getReg(); 171 172 // At this point, the destination register class of the hint may have 173 // been decided. 174 // 175 // Propagate that through to the source register. 176 const TargetRegisterClass *DstRC = MRI.getRegClassOrNull(DstReg); 177 if (DstRC) 178 MRI.setRegClass(SrcReg, DstRC); 179 assert(canReplaceReg(DstReg, SrcReg, MRI) && 180 "Must be able to replace dst with src!"); 181 MI.eraseFromParent(); 182 MRI.replaceRegWith(DstReg, SrcReg); 183 continue; 184 } 185 186 if (!ISel->select(MI)) { 187 // FIXME: It would be nice to dump all inserted instructions. It's 188 // not obvious how, esp. considering select() can insert after MI. 189 reportGISelFailure(MF, TPC, MORE, "gisel-select", "cannot select", MI); 190 return false; 191 } 192 193 // Dump the range of instructions that MI expanded into. 194 LLVM_DEBUG({ 195 auto InsertedBegin = ReachedBegin ? MBB->begin() : std::next(MII); 196 dbgs() << "Into:\n"; 197 for (auto &InsertedMI : make_range(InsertedBegin, AfterIt)) 198 dbgs() << " " << InsertedMI; 199 dbgs() << '\n'; 200 }); 201 } 202 } 203 204 for (MachineBasicBlock &MBB : MF) { 205 if (MBB.empty()) 206 continue; 207 208 // Try to find redundant copies b/w vregs of the same register class. 209 bool ReachedBegin = false; 210 for (auto MII = std::prev(MBB.end()), Begin = MBB.begin(); !ReachedBegin;) { 211 // Select this instruction. 212 MachineInstr &MI = *MII; 213 214 // And have our iterator point to the next instruction, if there is one. 215 if (MII == Begin) 216 ReachedBegin = true; 217 else 218 --MII; 219 if (MI.getOpcode() != TargetOpcode::COPY) 220 continue; 221 Register SrcReg = MI.getOperand(1).getReg(); 222 Register DstReg = MI.getOperand(0).getReg(); 223 if (Register::isVirtualRegister(SrcReg) && 224 Register::isVirtualRegister(DstReg)) { 225 auto SrcRC = MRI.getRegClass(SrcReg); 226 auto DstRC = MRI.getRegClass(DstReg); 227 if (SrcRC == DstRC) { 228 MRI.replaceRegWith(DstReg, SrcReg); 229 MI.eraseFromParent(); 230 } 231 } 232 } 233 } 234 235 #ifndef NDEBUG 236 const TargetRegisterInfo &TRI = *MF.getSubtarget().getRegisterInfo(); 237 // Now that selection is complete, there are no more generic vregs. Verify 238 // that the size of the now-constrained vreg is unchanged and that it has a 239 // register class. 240 for (unsigned I = 0, E = MRI.getNumVirtRegs(); I != E; ++I) { 241 unsigned VReg = Register::index2VirtReg(I); 242 243 MachineInstr *MI = nullptr; 244 if (!MRI.def_empty(VReg)) 245 MI = &*MRI.def_instr_begin(VReg); 246 else if (!MRI.use_empty(VReg)) 247 MI = &*MRI.use_instr_begin(VReg); 248 if (!MI) 249 continue; 250 251 const TargetRegisterClass *RC = MRI.getRegClassOrNull(VReg); 252 if (!RC) { 253 reportGISelFailure(MF, TPC, MORE, "gisel-select", 254 "VReg has no regclass after selection", *MI); 255 return false; 256 } 257 258 const LLT Ty = MRI.getType(VReg); 259 if (Ty.isValid() && Ty.getSizeInBits() > TRI.getRegSizeInBits(*RC)) { 260 reportGISelFailure( 261 MF, TPC, MORE, "gisel-select", 262 "VReg's low-level type and register class have different sizes", *MI); 263 return false; 264 } 265 } 266 267 if (MF.size() != NumBlocks) { 268 MachineOptimizationRemarkMissed R("gisel-select", "GISelFailure", 269 MF.getFunction().getSubprogram(), 270 /*MBB=*/nullptr); 271 R << "inserting blocks is not supported yet"; 272 reportGISelFailure(MF, TPC, MORE, R); 273 return false; 274 } 275 #endif 276 // Determine if there are any calls in this machine function. Ported from 277 // SelectionDAG. 278 MachineFrameInfo &MFI = MF.getFrameInfo(); 279 for (const auto &MBB : MF) { 280 if (MFI.hasCalls() && MF.hasInlineAsm()) 281 break; 282 283 for (const auto &MI : MBB) { 284 if ((MI.isCall() && !MI.isReturn()) || MI.isStackAligningInlineAsm()) 285 MFI.setHasCalls(true); 286 if (MI.isInlineAsm()) 287 MF.setHasInlineAsm(true); 288 } 289 } 290 291 // FIXME: FinalizeISel pass calls finalizeLowering, so it's called twice. 292 auto &TLI = *MF.getSubtarget().getTargetLowering(); 293 TLI.finalizeLowering(MF); 294 295 LLVM_DEBUG({ 296 dbgs() << "Rules covered by selecting function: " << MF.getName() << ":"; 297 for (auto RuleID : CoverageInfo.covered()) 298 dbgs() << " id" << RuleID; 299 dbgs() << "\n\n"; 300 }); 301 CoverageInfo.emit(CoveragePrefix, 302 TLI.getTargetMachine().getTarget().getBackendName()); 303 304 // If we successfully selected the function nothing is going to use the vreg 305 // types after us (otherwise MIRPrinter would need them). Make sure the types 306 // disappear. 307 MRI.clearVirtRegTypes(); 308 309 // FIXME: Should we accurately track changes? 310 return true; 311 } 312