388 lines · cpp
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-exception6//7//===----------------------------------------------------------------------===//8/// \file9/// 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/GISelValueTracking.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 40using namespace llvm;41 42DEBUG_COUNTER(GlobalISelCounter, "globalisel",43 "Controls whether to select function with GlobalISel");44 45#ifdef LLVM_GISEL_COV_PREFIX46static 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#else51static const std::string CoveragePrefix;52#endif53 54char InstructionSelect::ID = 0;55INITIALIZE_PASS_BEGIN(InstructionSelect, DEBUG_TYPE,56 "Select target instructions out of generic instructions",57 false, false)58INITIALIZE_PASS_DEPENDENCY(TargetPassConfig)59INITIALIZE_PASS_DEPENDENCY(GISelValueTrackingAnalysisLegacy)60INITIALIZE_PASS_DEPENDENCY(ProfileSummaryInfoWrapperPass)61INITIALIZE_PASS_DEPENDENCY(LazyBlockFrequencyInfoPass)62INITIALIZE_PASS_END(InstructionSelect, DEBUG_TYPE,63 "Select target instructions out of generic instructions",64 false, false)65 66InstructionSelect::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 one71/// that is currently being selected to determine which instruction to select72/// next. Previously this meant that selecting multiple instructions at once was73/// illegal behavior due to potential invalidation of this iterator. This is74/// a non-obvious limitation for selector implementers. Therefore, to allow75/// deletion of arbitrary instructions, we detect this case and continue76/// selection with the predecessor of the deleted instruction.77class InstructionSelect::MIIteratorMaintainer : public GISelChangeObserver {78#ifndef NDEBUG79 SmallSetVector<const MachineInstr *, 32> CreatedInstrs;80#endif81public: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 prior99 // to the MI that is currently being selected), the iterator would be100 // 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 121void InstructionSelect::getAnalysisUsage(AnalysisUsage &AU) const {122 AU.addRequired<TargetPassConfig>();123 AU.addRequired<GISelValueTrackingAnalysisLegacy>();124 AU.addPreserved<GISelValueTrackingAnalysisLegacy>();125 126 if (OptLevel != CodeGenOptLevel::None) {127 AU.addRequired<ProfileSummaryInfoWrapperPass>();128 LazyBlockFrequencyInfoPass::getLazyBFIAnalysisUsage(AU);129 }130 getSelectionDAGFallbackAnalysisUsage(AU);131 MachineFunctionPass::getAnalysisUsage(AU);132}133 134bool InstructionSelect::runOnMachineFunction(MachineFunction &MF) {135 // If the ISel pipeline failed, do not bother running that pass.136 if (MF.getProperties().hasFailedISel())137 return false;138 139 ISel = MF.getSubtarget().getInstructionSelector();140 ISel->TPC = &getAnalysis<TargetPassConfig>();141 142 // FIXME: Properly override OptLevel in TargetMachine. See OptLevelChanger143 CodeGenOptLevel OldOptLevel = OptLevel;144 auto RestoreOptLevel = make_scope_exit([=]() { OptLevel = OldOptLevel; });145 OptLevel = MF.getFunction().hasOptNone() ? CodeGenOptLevel::None146 : MF.getTarget().getOptLevel();147 148 VT = &getAnalysis<GISelValueTrackingAnalysisLegacy>().get(MF);149 if (OptLevel != CodeGenOptLevel::None) {150 PSI = &getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI();151 if (PSI && PSI->hasProfileSummary())152 BFI = &getAnalysis<LazyBlockFrequencyInfoPass>().getBFI();153 }154 155 return selectMachineFunction(MF);156}157 158bool InstructionSelect::selectMachineFunction(MachineFunction &MF) {159 LLVM_DEBUG(dbgs() << "Selecting function: " << MF.getName() << '\n');160 assert(ISel && "Cannot work without InstructionSelector");161 162 const TargetPassConfig &TPC = *ISel->TPC;163 CodeGenCoverage CoverageInfo;164 ISel->setupMF(MF, VT, &CoverageInfo, PSI, BFI);165 166 // An optimization remark emitter. Used to report failures.167 MachineOptimizationRemarkEmitter MORE(MF, /*MBFI=*/nullptr);168 ISel->MORE = &MORE;169 170 // FIXME: There are many other MF/MFI fields we need to initialize.171 172 MachineRegisterInfo &MRI = MF.getRegInfo();173#ifndef NDEBUG174 // Check that our input is fully legal: we require the function to have the175 // Legalized property, so it should be.176 // FIXME: This should be in the MachineVerifier, as the RegBankSelected177 // property check already is.178 if (!DisableGISelLegalityCheck)179 if (const MachineInstr *MI = machineFunctionIsIllegal(MF)) {180 reportGISelFailure(MF, TPC, MORE, "gisel-select",181 "instruction is not legal", *MI);182 return false;183 }184 // FIXME: We could introduce new blocks and will need to fix the outer loop.185 // Until then, keep track of the number of blocks to assert that we don't.186 const size_t NumBlocks = MF.size();187#endif188 // Keep track of selected blocks, so we can delete unreachable ones later.189 DenseSet<MachineBasicBlock *> SelectedBlocks;190 191 {192 // Observe IR insertions and removals during selection.193 // We only install a MachineFunction::Delegate instead of a194 // GISelChangeObserver, because we do not want notifications about changed195 // instructions. This prevents significant compile-time regressions from196 // e.g. constrainOperandRegClass().197 GISelObserverWrapper AllObservers;198 MIIteratorMaintainer MIIMaintainer;199 AllObservers.addObserver(&MIIMaintainer);200 RAIIDelegateInstaller DelInstaller(MF, &AllObservers);201 ISel->AllObservers = &AllObservers;202 203 for (MachineBasicBlock *MBB : post_order(&MF)) {204 ISel->CurMBB = MBB;205 SelectedBlocks.insert(MBB);206 207 // Select instructions in reverse block order.208 MIIMaintainer.MII = MBB->rbegin();209 for (auto End = MBB->rend(); MIIMaintainer.MII != End;) {210 MachineInstr &MI = *MIIMaintainer.MII;211 // Increment early to skip instructions inserted by select().212 ++MIIMaintainer.MII;213 214 LLVM_DEBUG(dbgs() << "\nSelect: " << MI);215 if (!selectInstr(MI)) {216 LLVM_DEBUG(dbgs() << "Selection failed!\n";217 MIIMaintainer.reportFullyCreatedInstrs());218 reportGISelFailure(MF, TPC, MORE, "gisel-select", "cannot select",219 MI);220 return false;221 }222 LLVM_DEBUG(MIIMaintainer.reportFullyCreatedInstrs());223 }224 }225 }226 227 for (MachineBasicBlock &MBB : MF) {228 if (MBB.empty())229 continue;230 231 if (!SelectedBlocks.contains(&MBB)) {232 // This is an unreachable block and therefore hasn't been selected, since233 // the main selection loop above uses a postorder block traversal.234 // We delete all the instructions in this block since it's unreachable.235 MBB.clear();236 // Don't delete the block in case the block has it's address taken or is237 // still being referenced by a phi somewhere.238 continue;239 }240 // Try to find redundant copies b/w vregs of the same register class.241 for (auto MII = MBB.rbegin(), End = MBB.rend(); MII != End;) {242 MachineInstr &MI = *MII;243 ++MII;244 245 if (MI.getOpcode() != TargetOpcode::COPY)246 continue;247 Register SrcReg = MI.getOperand(1).getReg();248 Register DstReg = MI.getOperand(0).getReg();249 if (SrcReg.isVirtual() && DstReg.isVirtual()) {250 auto SrcRC = MRI.getRegClass(SrcReg);251 auto DstRC = MRI.getRegClass(DstReg);252 if (SrcRC == DstRC) {253 MRI.replaceRegWith(DstReg, SrcReg);254 MI.eraseFromParent();255 }256 }257 }258 }259 260#ifndef NDEBUG261 const TargetRegisterInfo &TRI = *MF.getSubtarget().getRegisterInfo();262 // Now that selection is complete, there are no more generic vregs. Verify263 // that the size of the now-constrained vreg is unchanged and that it has a264 // register class.265 for (unsigned I = 0, E = MRI.getNumVirtRegs(); I != E; ++I) {266 Register VReg = Register::index2VirtReg(I);267 268 MachineInstr *MI = nullptr;269 if (!MRI.def_empty(VReg))270 MI = &*MRI.def_instr_begin(VReg);271 else if (!MRI.use_empty(VReg)) {272 MI = &*MRI.use_instr_begin(VReg);273 // Debug value instruction is permitted to use undefined vregs.274 if (MI->isDebugValue())275 continue;276 }277 if (!MI)278 continue;279 280 const TargetRegisterClass *RC = MRI.getRegClassOrNull(VReg);281 if (!RC) {282 reportGISelFailure(MF, TPC, MORE, "gisel-select",283 "VReg has no regclass after selection", *MI);284 return false;285 }286 287 const LLT Ty = MRI.getType(VReg);288 if (Ty.isValid() &&289 TypeSize::isKnownGT(Ty.getSizeInBits(), TRI.getRegSizeInBits(*RC))) {290 reportGISelFailure(291 MF, TPC, MORE, "gisel-select",292 "VReg's low-level type and register class have different sizes", *MI);293 return false;294 }295 }296 297 if (MF.size() != NumBlocks) {298 MachineOptimizationRemarkMissed R("gisel-select", "GISelFailure",299 MF.getFunction().getSubprogram(),300 /*MBB=*/nullptr);301 R << "inserting blocks is not supported yet";302 reportGISelFailure(MF, TPC, MORE, R);303 return false;304 }305#endif306 307 if (!DebugCounter::shouldExecute(GlobalISelCounter)) {308 dbgs() << "Falling back for function " << MF.getName() << "\n";309 MF.getProperties().setFailedISel();310 return false;311 }312 313 // Determine if there are any calls in this machine function. Ported from314 // SelectionDAG.315 MachineFrameInfo &MFI = MF.getFrameInfo();316 for (const auto &MBB : MF) {317 if (MFI.hasCalls() && MF.hasInlineAsm())318 break;319 320 for (const auto &MI : MBB) {321 if ((MI.isCall() && !MI.isReturn()) || MI.isStackAligningInlineAsm())322 MFI.setHasCalls(true);323 if (MI.isInlineAsm())324 MF.setHasInlineAsm(true);325 }326 }327 328 // FIXME: FinalizeISel pass calls finalizeLowering, so it's called twice.329 auto &TLI = *MF.getSubtarget().getTargetLowering();330 TLI.finalizeLowering(MF);331 332 LLVM_DEBUG({333 dbgs() << "Rules covered by selecting function: " << MF.getName() << ":";334 for (auto RuleID : CoverageInfo.covered())335 dbgs() << " id" << RuleID;336 dbgs() << "\n\n";337 });338 CoverageInfo.emit(CoveragePrefix,339 TLI.getTargetMachine().getTarget().getBackendName());340 341 // If we successfully selected the function nothing is going to use the vreg342 // types after us (otherwise MIRPrinter would need them). Make sure the types343 // disappear.344 MRI.clearVirtRegTypes();345 346 // FIXME: Should we accurately track changes?347 return true;348}349 350bool InstructionSelect::selectInstr(MachineInstr &MI) {351 MachineRegisterInfo &MRI = ISel->MF->getRegInfo();352 353 // We could have folded this instruction away already, making it dead.354 // If so, erase it.355 if (isTriviallyDead(MI, MRI)) {356 LLVM_DEBUG(dbgs() << "Is dead.\n");357 salvageDebugInfo(MRI, MI);358 MI.eraseFromParent();359 return true;360 }361 362 // Eliminate hints or G_CONSTANT_FOLD_BARRIER.363 if (isPreISelGenericOptimizationHint(MI.getOpcode()) ||364 MI.getOpcode() == TargetOpcode::G_CONSTANT_FOLD_BARRIER) {365 auto [DstReg, SrcReg] = MI.getFirst2Regs();366 367 // At this point, the destination register class of the op may have368 // been decided.369 //370 // Propagate that through to the source register.371 const TargetRegisterClass *DstRC = MRI.getRegClassOrNull(DstReg);372 if (DstRC)373 MRI.setRegClass(SrcReg, DstRC);374 assert(canReplaceReg(DstReg, SrcReg, MRI) &&375 "Must be able to replace dst with src!");376 MI.eraseFromParent();377 MRI.replaceRegWith(DstReg, SrcReg);378 return true;379 }380 381 if (MI.getOpcode() == TargetOpcode::G_INVOKE_REGION_START) {382 MI.eraseFromParent();383 return true;384 }385 386 return ISel->select(MI);387}388