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