4500 lines · cpp
1//===- SelectionDAGISel.cpp - Implement the SelectionDAGISel class --------===//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//9// This implements the SelectionDAGISel class.10//11//===----------------------------------------------------------------------===//12 13#include "llvm/CodeGen/SelectionDAGISel.h"14#include "ScheduleDAGSDNodes.h"15#include "SelectionDAGBuilder.h"16#include "llvm/ADT/APInt.h"17#include "llvm/ADT/DenseMap.h"18#include "llvm/ADT/PostOrderIterator.h"19#include "llvm/ADT/STLExtras.h"20#include "llvm/ADT/SmallPtrSet.h"21#include "llvm/ADT/SmallVector.h"22#include "llvm/ADT/Statistic.h"23#include "llvm/ADT/StringRef.h"24#include "llvm/Analysis/AliasAnalysis.h"25#include "llvm/Analysis/AssumptionCache.h"26#include "llvm/Analysis/BranchProbabilityInfo.h"27#include "llvm/Analysis/CFG.h"28#include "llvm/Analysis/LazyBlockFrequencyInfo.h"29#include "llvm/Analysis/OptimizationRemarkEmitter.h"30#include "llvm/Analysis/ProfileSummaryInfo.h"31#include "llvm/Analysis/TargetLibraryInfo.h"32#include "llvm/Analysis/TargetTransformInfo.h"33#include "llvm/Analysis/UniformityAnalysis.h"34#include "llvm/CodeGen/AssignmentTrackingAnalysis.h"35#include "llvm/CodeGen/CodeGenCommonISel.h"36#include "llvm/CodeGen/FastISel.h"37#include "llvm/CodeGen/FunctionLoweringInfo.h"38#include "llvm/CodeGen/GCMetadata.h"39#include "llvm/CodeGen/ISDOpcodes.h"40#include "llvm/CodeGen/MachineBasicBlock.h"41#include "llvm/CodeGen/MachineFrameInfo.h"42#include "llvm/CodeGen/MachineFunction.h"43#include "llvm/CodeGen/MachineFunctionPass.h"44#include "llvm/CodeGen/MachineInstr.h"45#include "llvm/CodeGen/MachineInstrBuilder.h"46#include "llvm/CodeGen/MachineMemOperand.h"47#include "llvm/CodeGen/MachineModuleInfo.h"48#include "llvm/CodeGen/MachineOperand.h"49#include "llvm/CodeGen/MachinePassRegistry.h"50#include "llvm/CodeGen/MachineRegisterInfo.h"51#include "llvm/CodeGen/SchedulerRegistry.h"52#include "llvm/CodeGen/SelectionDAG.h"53#include "llvm/CodeGen/SelectionDAGNodes.h"54#include "llvm/CodeGen/SelectionDAGTargetInfo.h"55#include "llvm/CodeGen/StackMaps.h"56#include "llvm/CodeGen/StackProtector.h"57#include "llvm/CodeGen/SwiftErrorValueTracking.h"58#include "llvm/CodeGen/TargetInstrInfo.h"59#include "llvm/CodeGen/TargetLowering.h"60#include "llvm/CodeGen/TargetRegisterInfo.h"61#include "llvm/CodeGen/TargetSubtargetInfo.h"62#include "llvm/CodeGen/ValueTypes.h"63#include "llvm/CodeGen/WinEHFuncInfo.h"64#include "llvm/CodeGenTypes/MachineValueType.h"65#include "llvm/IR/BasicBlock.h"66#include "llvm/IR/Constants.h"67#include "llvm/IR/DataLayout.h"68#include "llvm/IR/DebugInfo.h"69#include "llvm/IR/DebugInfoMetadata.h"70#include "llvm/IR/DebugLoc.h"71#include "llvm/IR/DiagnosticInfo.h"72#include "llvm/IR/EHPersonalities.h"73#include "llvm/IR/Function.h"74#include "llvm/IR/InlineAsm.h"75#include "llvm/IR/InstIterator.h"76#include "llvm/IR/Instruction.h"77#include "llvm/IR/Instructions.h"78#include "llvm/IR/IntrinsicInst.h"79#include "llvm/IR/Intrinsics.h"80#include "llvm/IR/IntrinsicsWebAssembly.h"81#include "llvm/IR/Metadata.h"82#include "llvm/IR/Module.h"83#include "llvm/IR/PrintPasses.h"84#include "llvm/IR/Statepoint.h"85#include "llvm/IR/Type.h"86#include "llvm/IR/User.h"87#include "llvm/IR/Value.h"88#include "llvm/InitializePasses.h"89#include "llvm/MC/MCInstrDesc.h"90#include "llvm/Pass.h"91#include "llvm/Support/BranchProbability.h"92#include "llvm/Support/Casting.h"93#include "llvm/Support/CodeGen.h"94#include "llvm/Support/CommandLine.h"95#include "llvm/Support/Compiler.h"96#include "llvm/Support/Debug.h"97#include "llvm/Support/ErrorHandling.h"98#include "llvm/Support/KnownBits.h"99#include "llvm/Support/Timer.h"100#include "llvm/Support/raw_ostream.h"101#include "llvm/Target/TargetMachine.h"102#include "llvm/Target/TargetOptions.h"103#include "llvm/Transforms/Utils/BasicBlockUtils.h"104#include <cassert>105#include <cstdint>106#include <iterator>107#include <limits>108#include <memory>109#include <optional>110#include <string>111#include <utility>112#include <vector>113 114using namespace llvm;115 116#define DEBUG_TYPE "isel"117#define ISEL_DUMP_DEBUG_TYPE DEBUG_TYPE "-dump"118 119STATISTIC(NumFastIselFailures, "Number of instructions fast isel failed on");120STATISTIC(NumFastIselSuccess, "Number of instructions fast isel selected");121STATISTIC(NumFastIselBlocks, "Number of blocks selected entirely by fast isel");122STATISTIC(NumDAGBlocks, "Number of blocks selected using DAG");123STATISTIC(NumDAGIselRetries,"Number of times dag isel has to try another path");124STATISTIC(NumEntryBlocks, "Number of entry blocks encountered");125STATISTIC(NumFastIselFailLowerArguments,126 "Number of entry blocks where fast isel failed to lower arguments");127 128static cl::opt<int> EnableFastISelAbort(129 "fast-isel-abort", cl::Hidden,130 cl::desc("Enable abort calls when \"fast\" instruction selection "131 "fails to lower an instruction: 0 disable the abort, 1 will "132 "abort but for args, calls and terminators, 2 will also "133 "abort for argument lowering, and 3 will never fallback "134 "to SelectionDAG."));135 136static cl::opt<bool> EnableFastISelFallbackReport(137 "fast-isel-report-on-fallback", cl::Hidden,138 cl::desc("Emit a diagnostic when \"fast\" instruction selection "139 "falls back to SelectionDAG."));140 141static cl::opt<bool>142UseMBPI("use-mbpi",143 cl::desc("use Machine Branch Probability Info"),144 cl::init(true), cl::Hidden);145 146#ifndef NDEBUG147static cl::opt<bool>148 DumpSortedDAG("dump-sorted-dags", cl::Hidden,149 cl::desc("Print DAGs with sorted nodes in debug dump"),150 cl::init(false));151 152static cl::opt<std::string>153FilterDAGBasicBlockName("filter-view-dags", cl::Hidden,154 cl::desc("Only display the basic block whose name "155 "matches this for all view-*-dags options"));156static cl::opt<bool>157ViewDAGCombine1("view-dag-combine1-dags", cl::Hidden,158 cl::desc("Pop up a window to show dags before the first "159 "dag combine pass"));160static cl::opt<bool>161ViewLegalizeTypesDAGs("view-legalize-types-dags", cl::Hidden,162 cl::desc("Pop up a window to show dags before legalize types"));163static cl::opt<bool>164 ViewDAGCombineLT("view-dag-combine-lt-dags", cl::Hidden,165 cl::desc("Pop up a window to show dags before the post "166 "legalize types dag combine pass"));167static cl::opt<bool>168 ViewLegalizeDAGs("view-legalize-dags", cl::Hidden,169 cl::desc("Pop up a window to show dags before legalize"));170static cl::opt<bool>171ViewDAGCombine2("view-dag-combine2-dags", cl::Hidden,172 cl::desc("Pop up a window to show dags before the second "173 "dag combine pass"));174static cl::opt<bool>175ViewISelDAGs("view-isel-dags", cl::Hidden,176 cl::desc("Pop up a window to show isel dags as they are selected"));177static cl::opt<bool>178ViewSchedDAGs("view-sched-dags", cl::Hidden,179 cl::desc("Pop up a window to show sched dags as they are processed"));180static cl::opt<bool>181ViewSUnitDAGs("view-sunit-dags", cl::Hidden,182 cl::desc("Pop up a window to show SUnit dags after they are processed"));183#else184static const bool ViewDAGCombine1 = false, ViewLegalizeTypesDAGs = false,185 ViewDAGCombineLT = false, ViewLegalizeDAGs = false,186 ViewDAGCombine2 = false, ViewISelDAGs = false,187 ViewSchedDAGs = false, ViewSUnitDAGs = false;188#endif189 190#ifndef NDEBUG191#define ISEL_DUMP(X) \192 do { \193 if (llvm::DebugFlag && \194 (isCurrentDebugType(DEBUG_TYPE) || \195 (isCurrentDebugType(ISEL_DUMP_DEBUG_TYPE) && MatchFilterFuncName))) { \196 X; \197 } \198 } while (false)199#else200#define ISEL_DUMP(X) do { } while (false)201#endif202 203//===---------------------------------------------------------------------===//204///205/// RegisterScheduler class - Track the registration of instruction schedulers.206///207//===---------------------------------------------------------------------===//208MachinePassRegistry<RegisterScheduler::FunctionPassCtor>209 RegisterScheduler::Registry;210 211//===---------------------------------------------------------------------===//212///213/// ISHeuristic command line option for instruction schedulers.214///215//===---------------------------------------------------------------------===//216static cl::opt<RegisterScheduler::FunctionPassCtor, false,217 RegisterPassParser<RegisterScheduler>>218ISHeuristic("pre-RA-sched",219 cl::init(&createDefaultScheduler), cl::Hidden,220 cl::desc("Instruction schedulers available (before register"221 " allocation):"));222 223static RegisterScheduler224defaultListDAGScheduler("default", "Best scheduler for the target",225 createDefaultScheduler);226 227static bool dontUseFastISelFor(const Function &Fn) {228 // Don't enable FastISel for functions with swiftasync Arguments.229 // Debug info on those is reliant on good Argument lowering, and FastISel is230 // not capable of lowering the entire function. Mixing the two selectors tend231 // to result in poor lowering of Arguments.232 return any_of(Fn.args(), [](const Argument &Arg) {233 return Arg.hasAttribute(Attribute::AttrKind::SwiftAsync);234 });235}236 237static bool maintainPGOProfile(const TargetMachine &TM,238 CodeGenOptLevel OptLevel) {239 if (OptLevel != CodeGenOptLevel::None)240 return true;241 if (TM.getPGOOption()) {242 const PGOOptions &Options = *TM.getPGOOption();243 return Options.Action == PGOOptions::PGOAction::IRUse ||244 Options.Action == PGOOptions::PGOAction::SampleUse ||245 Options.CSAction == PGOOptions::CSPGOAction::CSIRUse;246 }247 return false;248}249 250namespace llvm {251 252 //===--------------------------------------------------------------------===//253 /// This class is used by SelectionDAGISel to temporarily override254 /// the optimization level on a per-function basis.255 class OptLevelChanger {256 SelectionDAGISel &IS;257 CodeGenOptLevel SavedOptLevel;258 bool SavedFastISel;259 260 public:261 OptLevelChanger(SelectionDAGISel &ISel, CodeGenOptLevel NewOptLevel)262 : IS(ISel) {263 SavedOptLevel = IS.OptLevel;264 SavedFastISel = IS.TM.Options.EnableFastISel;265 if (NewOptLevel != SavedOptLevel) {266 IS.OptLevel = NewOptLevel;267 IS.TM.setOptLevel(NewOptLevel);268 LLVM_DEBUG(dbgs() << "\nChanging optimization level for Function "269 << IS.MF->getFunction().getName() << "\n");270 LLVM_DEBUG(dbgs() << "\tBefore: -O" << static_cast<int>(SavedOptLevel)271 << " ; After: -O" << static_cast<int>(NewOptLevel)272 << "\n");273 if (NewOptLevel == CodeGenOptLevel::None)274 IS.TM.setFastISel(IS.TM.getO0WantsFastISel());275 }276 if (dontUseFastISelFor(IS.MF->getFunction()))277 IS.TM.setFastISel(false);278 LLVM_DEBUG(279 dbgs() << "\tFastISel is "280 << (IS.TM.Options.EnableFastISel ? "enabled" : "disabled")281 << "\n");282 }283 284 ~OptLevelChanger() {285 if (IS.OptLevel == SavedOptLevel)286 return;287 LLVM_DEBUG(dbgs() << "\nRestoring optimization level for Function "288 << IS.MF->getFunction().getName() << "\n");289 LLVM_DEBUG(dbgs() << "\tBefore: -O" << static_cast<int>(IS.OptLevel)290 << " ; After: -O" << static_cast<int>(SavedOptLevel) << "\n");291 IS.OptLevel = SavedOptLevel;292 IS.TM.setOptLevel(SavedOptLevel);293 IS.TM.setFastISel(SavedFastISel);294 }295 };296 297 //===--------------------------------------------------------------------===//298 /// createDefaultScheduler - This creates an instruction scheduler appropriate299 /// for the target.300 ScheduleDAGSDNodes *createDefaultScheduler(SelectionDAGISel *IS,301 CodeGenOptLevel OptLevel) {302 const TargetLowering *TLI = IS->TLI;303 const TargetSubtargetInfo &ST = IS->MF->getSubtarget();304 305 // Try first to see if the Target has its own way of selecting a scheduler306 if (auto *SchedulerCtor = ST.getDAGScheduler(OptLevel)) {307 return SchedulerCtor(IS, OptLevel);308 }309 310 if (OptLevel == CodeGenOptLevel::None ||311 (ST.enableMachineScheduler() && ST.enableMachineSchedDefaultSched()) ||312 TLI->getSchedulingPreference() == Sched::Source)313 return createSourceListDAGScheduler(IS, OptLevel);314 if (TLI->getSchedulingPreference() == Sched::RegPressure)315 return createBURRListDAGScheduler(IS, OptLevel);316 if (TLI->getSchedulingPreference() == Sched::Hybrid)317 return createHybridListDAGScheduler(IS, OptLevel);318 if (TLI->getSchedulingPreference() == Sched::VLIW)319 return createVLIWDAGScheduler(IS, OptLevel);320 if (TLI->getSchedulingPreference() == Sched::Fast)321 return createFastDAGScheduler(IS, OptLevel);322 if (TLI->getSchedulingPreference() == Sched::Linearize)323 return createDAGLinearizer(IS, OptLevel);324 assert(TLI->getSchedulingPreference() == Sched::ILP &&325 "Unknown sched type!");326 return createILPListDAGScheduler(IS, OptLevel);327 }328 329} // end namespace llvm330 331MachineBasicBlock *332TargetLowering::EmitInstrWithCustomInserter(MachineInstr &MI,333 MachineBasicBlock *MBB) const {334#ifndef NDEBUG335 dbgs() << "If a target marks an instruction with "336 "'usesCustomInserter', it must implement "337 "TargetLowering::EmitInstrWithCustomInserter!\n";338#endif339 llvm_unreachable(nullptr);340}341 342void TargetLowering::AdjustInstrPostInstrSelection(MachineInstr &MI,343 SDNode *Node) const {344 assert(!MI.hasPostISelHook() &&345 "If a target marks an instruction with 'hasPostISelHook', "346 "it must implement TargetLowering::AdjustInstrPostInstrSelection!");347}348 349//===----------------------------------------------------------------------===//350// SelectionDAGISel code351//===----------------------------------------------------------------------===//352 353SelectionDAGISelLegacy::SelectionDAGISelLegacy(354 char &ID, std::unique_ptr<SelectionDAGISel> S)355 : MachineFunctionPass(ID), Selector(std::move(S)) {356 initializeGCModuleInfoPass(*PassRegistry::getPassRegistry());357 initializeBranchProbabilityInfoWrapperPassPass(358 *PassRegistry::getPassRegistry());359 initializeAAResultsWrapperPassPass(*PassRegistry::getPassRegistry());360 initializeTargetLibraryInfoWrapperPassPass(*PassRegistry::getPassRegistry());361}362 363bool SelectionDAGISelLegacy::runOnMachineFunction(MachineFunction &MF) {364 // If we already selected that function, we do not need to run SDISel.365 if (MF.getProperties().hasSelected())366 return false;367 368 // Do some sanity-checking on the command-line options.369 if (EnableFastISelAbort && !Selector->TM.Options.EnableFastISel)370 reportFatalUsageError("-fast-isel-abort > 0 requires -fast-isel");371 372 // Decide what flavour of variable location debug-info will be used, before373 // we change the optimisation level.374 MF.setUseDebugInstrRef(MF.shouldUseDebugInstrRef());375 376 // Reset the target options before resetting the optimization377 // level below.378 // FIXME: This is a horrible hack and should be processed via379 // codegen looking at the optimization level explicitly when380 // it wants to look at it.381 Selector->TM.resetTargetOptions(MF.getFunction());382 // Reset OptLevel to None for optnone functions.383 CodeGenOptLevel NewOptLevel = skipFunction(MF.getFunction())384 ? CodeGenOptLevel::None385 : Selector->OptLevel;386 387 Selector->MF = &MF;388 OptLevelChanger OLC(*Selector, NewOptLevel);389 Selector->initializeAnalysisResults(*this);390 return Selector->runOnMachineFunction(MF);391}392 393SelectionDAGISel::SelectionDAGISel(TargetMachine &tm, CodeGenOptLevel OL)394 : TM(tm), FuncInfo(new FunctionLoweringInfo()),395 SwiftError(new SwiftErrorValueTracking()),396 CurDAG(new SelectionDAG(tm, OL)),397 SDB(std::make_unique<SelectionDAGBuilder>(*CurDAG, *FuncInfo, *SwiftError,398 OL)),399 OptLevel(OL) {400 initializeGCModuleInfoPass(*PassRegistry::getPassRegistry());401 initializeBranchProbabilityInfoWrapperPassPass(402 *PassRegistry::getPassRegistry());403 initializeAAResultsWrapperPassPass(*PassRegistry::getPassRegistry());404 initializeTargetLibraryInfoWrapperPassPass(*PassRegistry::getPassRegistry());405}406 407SelectionDAGISel::~SelectionDAGISel() { delete CurDAG; }408 409void SelectionDAGISelLegacy::getAnalysisUsage(AnalysisUsage &AU) const {410 CodeGenOptLevel OptLevel = Selector->OptLevel;411 bool RegisterPGOPasses = maintainPGOProfile(Selector->TM, Selector->OptLevel);412 if (OptLevel != CodeGenOptLevel::None)413 AU.addRequired<AAResultsWrapperPass>();414 AU.addRequired<GCModuleInfo>();415 AU.addRequired<StackProtector>();416 AU.addPreserved<GCModuleInfo>();417 AU.addRequired<TargetLibraryInfoWrapperPass>();418 AU.addRequired<TargetTransformInfoWrapperPass>();419 AU.addRequired<AssumptionCacheTracker>();420 if (UseMBPI && RegisterPGOPasses)421 AU.addRequired<BranchProbabilityInfoWrapperPass>();422 AU.addRequired<ProfileSummaryInfoWrapperPass>();423 // AssignmentTrackingAnalysis only runs if assignment tracking is enabled for424 // the module.425 AU.addRequired<AssignmentTrackingAnalysis>();426 AU.addPreserved<AssignmentTrackingAnalysis>();427 if (RegisterPGOPasses)428 LazyBlockFrequencyInfoPass::getLazyBFIAnalysisUsage(AU);429 MachineFunctionPass::getAnalysisUsage(AU);430}431 432PreservedAnalyses433SelectionDAGISelPass::run(MachineFunction &MF,434 MachineFunctionAnalysisManager &MFAM) {435 // If we already selected that function, we do not need to run SDISel.436 if (MF.getProperties().hasSelected())437 return PreservedAnalyses::all();438 439 // Do some sanity-checking on the command-line options.440 if (EnableFastISelAbort && !Selector->TM.Options.EnableFastISel)441 reportFatalUsageError("-fast-isel-abort > 0 requires -fast-isel");442 443 // Decide what flavour of variable location debug-info will be used, before444 // we change the optimisation level.445 MF.setUseDebugInstrRef(MF.shouldUseDebugInstrRef());446 447 // Reset the target options before resetting the optimization448 // level below.449 // FIXME: This is a horrible hack and should be processed via450 // codegen looking at the optimization level explicitly when451 // it wants to look at it.452 Selector->TM.resetTargetOptions(MF.getFunction());453 // Reset OptLevel to None for optnone functions.454 // TODO: Add a function analysis to handle this.455 Selector->MF = &MF;456 // Reset OptLevel to None for optnone functions.457 CodeGenOptLevel NewOptLevel = MF.getFunction().hasOptNone()458 ? CodeGenOptLevel::None459 : Selector->OptLevel;460 461 OptLevelChanger OLC(*Selector, NewOptLevel);462 Selector->initializeAnalysisResults(MFAM);463 Selector->runOnMachineFunction(MF);464 465 return getMachineFunctionPassPreservedAnalyses();466}467 468void SelectionDAGISel::initializeAnalysisResults(469 MachineFunctionAnalysisManager &MFAM) {470 auto &FAM = MFAM.getResult<FunctionAnalysisManagerMachineFunctionProxy>(*MF)471 .getManager();472 auto &MAMP = MFAM.getResult<ModuleAnalysisManagerMachineFunctionProxy>(*MF);473 Function &Fn = MF->getFunction();474#ifndef NDEBUG475 FuncName = Fn.getName();476 MatchFilterFuncName = isFunctionInPrintList(FuncName);477#else478 (void)MatchFilterFuncName;479#endif480 481 bool RegisterPGOPasses = maintainPGOProfile(TM, OptLevel);482 TII = MF->getSubtarget().getInstrInfo();483 TLI = MF->getSubtarget().getTargetLowering();484 RegInfo = &MF->getRegInfo();485 LibInfo = &FAM.getResult<TargetLibraryAnalysis>(Fn);486 GFI = Fn.hasGC() ? &FAM.getResult<GCFunctionAnalysis>(Fn) : nullptr;487 ORE = std::make_unique<OptimizationRemarkEmitter>(&Fn);488 AC = &FAM.getResult<AssumptionAnalysis>(Fn);489 auto *PSI = MAMP.getCachedResult<ProfileSummaryAnalysis>(*Fn.getParent());490 BlockFrequencyInfo *BFI = nullptr;491 FAM.getResult<BlockFrequencyAnalysis>(Fn);492 if (PSI && PSI->hasProfileSummary() && RegisterPGOPasses)493 BFI = &FAM.getResult<BlockFrequencyAnalysis>(Fn);494 495 FunctionVarLocs const *FnVarLocs = nullptr;496 if (isAssignmentTrackingEnabled(*Fn.getParent()))497 FnVarLocs = &FAM.getResult<DebugAssignmentTrackingAnalysis>(Fn);498 499 auto *UA = FAM.getCachedResult<UniformityInfoAnalysis>(Fn);500 MachineModuleInfo &MMI =501 MAMP.getCachedResult<MachineModuleAnalysis>(*Fn.getParent())->getMMI();502 503 CurDAG->init(*MF, *ORE, MFAM, LibInfo, UA, PSI, BFI, MMI, FnVarLocs);504 505 // Now get the optional analyzes if we want to.506 // This is based on the possibly changed OptLevel (after optnone is taken507 // into account). That's unfortunate but OK because it just means we won't508 // ask for passes that have been required anyway.509 510 if (UseMBPI && RegisterPGOPasses)511 FuncInfo->BPI = &FAM.getResult<BranchProbabilityAnalysis>(Fn);512 else513 FuncInfo->BPI = nullptr;514 515 if (OptLevel != CodeGenOptLevel::None)516 BatchAA.emplace(FAM.getResult<AAManager>(Fn));517 else518 BatchAA = std::nullopt;519 520 SP = &FAM.getResult<SSPLayoutAnalysis>(Fn);521 522 TTI = &FAM.getResult<TargetIRAnalysis>(Fn);523}524 525void SelectionDAGISel::initializeAnalysisResults(MachineFunctionPass &MFP) {526 Function &Fn = MF->getFunction();527#ifndef NDEBUG528 FuncName = Fn.getName();529 MatchFilterFuncName = isFunctionInPrintList(FuncName);530#else531 (void)MatchFilterFuncName;532#endif533 534 bool RegisterPGOPasses = maintainPGOProfile(TM, OptLevel);535 TII = MF->getSubtarget().getInstrInfo();536 TLI = MF->getSubtarget().getTargetLowering();537 RegInfo = &MF->getRegInfo();538 LibInfo = &MFP.getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(Fn);539 GFI = Fn.hasGC() ? &MFP.getAnalysis<GCModuleInfo>().getFunctionInfo(Fn)540 : nullptr;541 ORE = std::make_unique<OptimizationRemarkEmitter>(&Fn);542 AC = &MFP.getAnalysis<AssumptionCacheTracker>().getAssumptionCache(Fn);543 auto *PSI = &MFP.getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI();544 BlockFrequencyInfo *BFI = nullptr;545 if (PSI && PSI->hasProfileSummary() && RegisterPGOPasses)546 BFI = &MFP.getAnalysis<LazyBlockFrequencyInfoPass>().getBFI();547 548 FunctionVarLocs const *FnVarLocs = nullptr;549 if (isAssignmentTrackingEnabled(*Fn.getParent()))550 FnVarLocs = MFP.getAnalysis<AssignmentTrackingAnalysis>().getResults();551 552 UniformityInfo *UA = nullptr;553 if (auto *UAPass = MFP.getAnalysisIfAvailable<UniformityInfoWrapperPass>())554 UA = &UAPass->getUniformityInfo();555 556 MachineModuleInfo &MMI =557 MFP.getAnalysis<MachineModuleInfoWrapperPass>().getMMI();558 559 CurDAG->init(*MF, *ORE, &MFP, LibInfo, UA, PSI, BFI, MMI, FnVarLocs);560 561 // Now get the optional analyzes if we want to.562 // This is based on the possibly changed OptLevel (after optnone is taken563 // into account). That's unfortunate but OK because it just means we won't564 // ask for passes that have been required anyway.565 566 if (UseMBPI && RegisterPGOPasses)567 FuncInfo->BPI =568 &MFP.getAnalysis<BranchProbabilityInfoWrapperPass>().getBPI();569 else570 FuncInfo->BPI = nullptr;571 572 if (OptLevel != CodeGenOptLevel::None)573 BatchAA.emplace(MFP.getAnalysis<AAResultsWrapperPass>().getAAResults());574 else575 BatchAA = std::nullopt;576 577 SP = &MFP.getAnalysis<StackProtector>().getLayoutInfo();578 579 TTI = &MFP.getAnalysis<TargetTransformInfoWrapperPass>().getTTI(Fn);580}581 582bool SelectionDAGISel::runOnMachineFunction(MachineFunction &mf) {583 SwiftError->setFunction(mf);584 const Function &Fn = mf.getFunction();585 586 bool InstrRef = mf.useDebugInstrRef();587 588 FuncInfo->set(MF->getFunction(), *MF, CurDAG);589 590 ISEL_DUMP(dbgs() << "\n\n\n=== " << FuncName << '\n');591 592 SDB->init(GFI, getBatchAA(), AC, LibInfo, *TTI);593 594 MF->setHasInlineAsm(false);595 596 FuncInfo->SplitCSR = false;597 598 // We split CSR if the target supports it for the given function599 // and the function has only return exits.600 if (OptLevel != CodeGenOptLevel::None && TLI->supportSplitCSR(MF)) {601 FuncInfo->SplitCSR = true;602 603 // Collect all the return blocks.604 for (const BasicBlock &BB : Fn) {605 if (!succ_empty(&BB))606 continue;607 608 const Instruction *Term = BB.getTerminator();609 if (isa<UnreachableInst>(Term) || isa<ReturnInst>(Term))610 continue;611 612 // Bail out if the exit block is not Return nor Unreachable.613 FuncInfo->SplitCSR = false;614 break;615 }616 }617 618 MachineBasicBlock *EntryMBB = &MF->front();619 if (FuncInfo->SplitCSR)620 // This performs initialization so lowering for SplitCSR will be correct.621 TLI->initializeSplitCSR(EntryMBB);622 623 SelectAllBasicBlocks(Fn);624 if (FastISelFailed && EnableFastISelFallbackReport) {625 DiagnosticInfoISelFallback DiagFallback(Fn);626 Fn.getContext().diagnose(DiagFallback);627 }628 629 // Replace forward-declared registers with the registers containing630 // the desired value.631 // Note: it is important that this happens **before** the call to632 // EmitLiveInCopies, since implementations can skip copies of unused633 // registers. If we don't apply the reg fixups before, some registers may634 // appear as unused and will be skipped, resulting in bad MI.635 MachineRegisterInfo &MRI = MF->getRegInfo();636 for (DenseMap<Register, Register>::iterator I = FuncInfo->RegFixups.begin(),637 E = FuncInfo->RegFixups.end();638 I != E; ++I) {639 Register From = I->first;640 Register To = I->second;641 // If To is also scheduled to be replaced, find what its ultimate642 // replacement is.643 while (true) {644 DenseMap<Register, Register>::iterator J = FuncInfo->RegFixups.find(To);645 if (J == E)646 break;647 To = J->second;648 }649 // Make sure the new register has a sufficiently constrained register class.650 if (From.isVirtual() && To.isVirtual())651 MRI.constrainRegClass(To, MRI.getRegClass(From));652 // Replace it.653 654 // Replacing one register with another won't touch the kill flags.655 // We need to conservatively clear the kill flags as a kill on the old656 // register might dominate existing uses of the new register.657 if (!MRI.use_empty(To))658 MRI.clearKillFlags(From);659 MRI.replaceRegWith(From, To);660 }661 662 // If the first basic block in the function has live ins that need to be663 // copied into vregs, emit the copies into the top of the block before664 // emitting the code for the block.665 const TargetRegisterInfo &TRI = *MF->getSubtarget().getRegisterInfo();666 RegInfo->EmitLiveInCopies(EntryMBB, TRI, *TII);667 668 // Insert copies in the entry block and the return blocks.669 if (FuncInfo->SplitCSR) {670 SmallVector<MachineBasicBlock*, 4> Returns;671 // Collect all the return blocks.672 for (MachineBasicBlock &MBB : mf) {673 if (!MBB.succ_empty())674 continue;675 676 MachineBasicBlock::iterator Term = MBB.getFirstTerminator();677 if (Term != MBB.end() && Term->isReturn()) {678 Returns.push_back(&MBB);679 continue;680 }681 }682 TLI->insertCopiesSplitCSR(EntryMBB, Returns);683 }684 685 DenseMap<MCRegister, Register> LiveInMap;686 if (!FuncInfo->ArgDbgValues.empty())687 for (std::pair<MCRegister, Register> LI : RegInfo->liveins())688 if (LI.second)689 LiveInMap.insert(LI);690 691 // Insert DBG_VALUE instructions for function arguments to the entry block.692 for (unsigned i = 0, e = FuncInfo->ArgDbgValues.size(); i != e; ++i) {693 MachineInstr *MI = FuncInfo->ArgDbgValues[e - i - 1];694 assert(MI->getOpcode() != TargetOpcode::DBG_VALUE_LIST &&695 "Function parameters should not be described by DBG_VALUE_LIST.");696 bool hasFI = MI->getDebugOperand(0).isFI();697 Register Reg =698 hasFI ? TRI.getFrameRegister(*MF) : MI->getDebugOperand(0).getReg();699 if (Reg.isPhysical())700 EntryMBB->insert(EntryMBB->begin(), MI);701 else {702 MachineInstr *Def = RegInfo->getVRegDef(Reg);703 if (Def) {704 MachineBasicBlock::iterator InsertPos = Def;705 // FIXME: VR def may not be in entry block.706 Def->getParent()->insert(std::next(InsertPos), MI);707 } else708 LLVM_DEBUG(dbgs() << "Dropping debug info for dead vreg"709 << printReg(Reg) << '\n');710 }711 712 // Don't try and extend through copies in instruction referencing mode.713 if (InstrRef)714 continue;715 716 // If Reg is live-in then update debug info to track its copy in a vreg.717 if (!Reg.isPhysical())718 continue;719 DenseMap<MCRegister, Register>::iterator LDI = LiveInMap.find(Reg);720 if (LDI != LiveInMap.end()) {721 assert(!hasFI && "There's no handling of frame pointer updating here yet "722 "- add if needed");723 MachineInstr *Def = RegInfo->getVRegDef(LDI->second);724 MachineBasicBlock::iterator InsertPos = Def;725 const MDNode *Variable = MI->getDebugVariable();726 const MDNode *Expr = MI->getDebugExpression();727 DebugLoc DL = MI->getDebugLoc();728 bool IsIndirect = MI->isIndirectDebugValue();729 if (IsIndirect)730 assert(MI->getDebugOffset().getImm() == 0 &&731 "DBG_VALUE with nonzero offset");732 assert(cast<DILocalVariable>(Variable)->isValidLocationForIntrinsic(DL) &&733 "Expected inlined-at fields to agree");734 assert(MI->getOpcode() != TargetOpcode::DBG_VALUE_LIST &&735 "Didn't expect to see a DBG_VALUE_LIST here");736 // Def is never a terminator here, so it is ok to increment InsertPos.737 BuildMI(*EntryMBB, ++InsertPos, DL, TII->get(TargetOpcode::DBG_VALUE),738 IsIndirect, LDI->second, Variable, Expr);739 740 // If this vreg is directly copied into an exported register then741 // that COPY instructions also need DBG_VALUE, if it is the only742 // user of LDI->second.743 MachineInstr *CopyUseMI = nullptr;744 for (MachineInstr &UseMI : RegInfo->use_instructions(LDI->second)) {745 if (UseMI.isDebugValue())746 continue;747 if (UseMI.isCopy() && !CopyUseMI && UseMI.getParent() == EntryMBB) {748 CopyUseMI = &UseMI;749 continue;750 }751 // Otherwise this is another use or second copy use.752 CopyUseMI = nullptr;753 break;754 }755 if (CopyUseMI &&756 TRI.getRegSizeInBits(LDI->second, MRI) ==757 TRI.getRegSizeInBits(CopyUseMI->getOperand(0).getReg(), MRI)) {758 // Use MI's debug location, which describes where Variable was759 // declared, rather than whatever is attached to CopyUseMI.760 MachineInstr *NewMI =761 BuildMI(*MF, DL, TII->get(TargetOpcode::DBG_VALUE), IsIndirect,762 CopyUseMI->getOperand(0).getReg(), Variable, Expr);763 MachineBasicBlock::iterator Pos = CopyUseMI;764 EntryMBB->insertAfter(Pos, NewMI);765 }766 }767 }768 769 // For debug-info, in instruction referencing mode, we need to perform some770 // post-isel maintenence.771 if (MF->useDebugInstrRef())772 MF->finalizeDebugInstrRefs();773 774 // Determine if there are any calls in this machine function.775 MachineFrameInfo &MFI = MF->getFrameInfo();776 for (const auto &MBB : *MF) {777 if (MFI.hasCalls() && MF->hasInlineAsm())778 break;779 780 for (const auto &MI : MBB) {781 const MCInstrDesc &MCID = TII->get(MI.getOpcode());782 if ((MCID.isCall() && !MCID.isReturn()) ||783 MI.isStackAligningInlineAsm()) {784 MFI.setHasCalls(true);785 }786 if (MI.isInlineAsm()) {787 MF->setHasInlineAsm(true);788 }789 }790 }791 792 // Release function-specific state. SDB and CurDAG are already cleared793 // at this point.794 FuncInfo->clear();795 796 ISEL_DUMP(dbgs() << "*** MachineFunction at end of ISel ***\n");797 ISEL_DUMP(MF->print(dbgs()));798 799 return true;800}801 802static void reportFastISelFailure(MachineFunction &MF,803 OptimizationRemarkEmitter &ORE,804 OptimizationRemarkMissed &R,805 bool ShouldAbort) {806 // Print the function name explicitly if we don't have a debug location (which807 // makes the diagnostic less useful) or if we're going to emit a raw error.808 if (!R.getLocation().isValid() || ShouldAbort)809 R << (" (in function: " + MF.getName() + ")").str();810 811 if (ShouldAbort)812 reportFatalUsageError(Twine(R.getMsg()));813 814 ORE.emit(R);815 LLVM_DEBUG(dbgs() << R.getMsg() << "\n");816}817 818// Detect any fake uses that follow a tail call and move them before the tail819// call. Ignore fake uses that use values that are def'd by or after the tail820// call.821static void preserveFakeUses(BasicBlock::iterator Begin,822 BasicBlock::iterator End) {823 BasicBlock::iterator I = End;824 if (--I == Begin || !isa<ReturnInst>(*I))825 return;826 // Detect whether there are any fake uses trailing a (potential) tail call.827 bool HaveFakeUse = false;828 bool HaveTailCall = false;829 do {830 if (const CallInst *CI = dyn_cast<CallInst>(--I))831 if (CI->isTailCall()) {832 HaveTailCall = true;833 break;834 }835 if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(I))836 if (II->getIntrinsicID() == Intrinsic::fake_use)837 HaveFakeUse = true;838 } while (I != Begin);839 840 // If we didn't find any tail calls followed by fake uses, we are done.841 if (!HaveTailCall || !HaveFakeUse)842 return;843 844 SmallVector<IntrinsicInst *> FakeUses;845 // Record the fake uses we found so we can move them to the front of the846 // tail call. Ignore them if they use a value that is def'd by or after847 // the tail call.848 for (BasicBlock::iterator Inst = I; Inst != End; Inst++) {849 if (IntrinsicInst *FakeUse = dyn_cast<IntrinsicInst>(Inst);850 FakeUse && FakeUse->getIntrinsicID() == Intrinsic::fake_use) {851 if (auto UsedDef = dyn_cast<Instruction>(FakeUse->getOperand(0));852 !UsedDef || UsedDef->getParent() != I->getParent() ||853 UsedDef->comesBefore(&*I))854 FakeUses.push_back(FakeUse);855 }856 }857 858 for (auto *Inst : FakeUses)859 Inst->moveBefore(*Inst->getParent(), I);860}861 862void SelectionDAGISel::SelectBasicBlock(BasicBlock::const_iterator Begin,863 BasicBlock::const_iterator End,864 bool &HadTailCall) {865 // Allow creating illegal types during DAG building for the basic block.866 CurDAG->NewNodesMustHaveLegalTypes = false;867 868 // Lower the instructions. If a call is emitted as a tail call, cease emitting869 // nodes for this block. If an instruction is elided, don't emit it, but do870 // handle any debug-info attached to it.871 for (BasicBlock::const_iterator I = Begin; I != End && !SDB->HasTailCall; ++I) {872 if (!ElidedArgCopyInstrs.count(&*I))873 SDB->visit(*I);874 else875 SDB->visitDbgInfo(*I);876 }877 878 // Make sure the root of the DAG is up-to-date.879 CurDAG->setRoot(SDB->getControlRoot());880 HadTailCall = SDB->HasTailCall;881 SDB->resolveOrClearDbgInfo();882 SDB->clear();883 884 // Final step, emit the lowered DAG as machine code.885 CodeGenAndEmitDAG();886}887 888void SelectionDAGISel::ComputeLiveOutVRegInfo() {889 SmallPtrSet<SDNode *, 16> Added;890 SmallVector<SDNode*, 128> Worklist;891 892 Worklist.push_back(CurDAG->getRoot().getNode());893 Added.insert(CurDAG->getRoot().getNode());894 895 KnownBits Known;896 897 do {898 SDNode *N = Worklist.pop_back_val();899 900 // Otherwise, add all chain operands to the worklist.901 for (const SDValue &Op : N->op_values())902 if (Op.getValueType() == MVT::Other && Added.insert(Op.getNode()).second)903 Worklist.push_back(Op.getNode());904 905 // If this is a CopyToReg with a vreg dest, process it.906 if (N->getOpcode() != ISD::CopyToReg)907 continue;908 909 Register DestReg = cast<RegisterSDNode>(N->getOperand(1))->getReg();910 if (!DestReg.isVirtual())911 continue;912 913 // Ignore non-integer values.914 SDValue Src = N->getOperand(2);915 EVT SrcVT = Src.getValueType();916 if (!SrcVT.isInteger())917 continue;918 919 unsigned NumSignBits = CurDAG->ComputeNumSignBits(Src);920 Known = CurDAG->computeKnownBits(Src);921 FuncInfo->AddLiveOutRegInfo(DestReg, NumSignBits, Known);922 } while (!Worklist.empty());923}924 925void SelectionDAGISel::CodeGenAndEmitDAG() {926 StringRef GroupName = "sdag";927 StringRef GroupDescription = "Instruction Selection and Scheduling";928 std::string BlockName;929 bool MatchFilterBB = false;930 (void)MatchFilterBB;931 932 // Pre-type legalization allow creation of any node types.933 CurDAG->NewNodesMustHaveLegalTypes = false;934 935#ifndef NDEBUG936 MatchFilterBB = (FilterDAGBasicBlockName.empty() ||937 FilterDAGBasicBlockName ==938 FuncInfo->MBB->getBasicBlock()->getName());939#endif940#ifdef NDEBUG941 if (ViewDAGCombine1 || ViewLegalizeTypesDAGs || ViewDAGCombineLT ||942 ViewLegalizeDAGs || ViewDAGCombine2 || ViewISelDAGs || ViewSchedDAGs ||943 ViewSUnitDAGs)944#endif945 {946 BlockName =947 (MF->getName() + ":" + FuncInfo->MBB->getBasicBlock()->getName()).str();948 }949 ISEL_DUMP(dbgs() << "\nInitial selection DAG: "950 << printMBBReference(*FuncInfo->MBB) << " '" << BlockName951 << "'\n";952 CurDAG->dump(DumpSortedDAG));953 954#if !defined(NDEBUG) && LLVM_ENABLE_ABI_BREAKING_CHECKS955 if (TTI->hasBranchDivergence())956 CurDAG->VerifyDAGDivergence();957#endif958 959 if (ViewDAGCombine1 && MatchFilterBB)960 CurDAG->viewGraph("dag-combine1 input for " + BlockName);961 962 // Run the DAG combiner in pre-legalize mode.963 {964 NamedRegionTimer T("combine1", "DAG Combining 1", GroupName,965 GroupDescription, TimePassesIsEnabled);966 CurDAG->Combine(BeforeLegalizeTypes, getBatchAA(), OptLevel);967 }968 969 ISEL_DUMP(dbgs() << "\nOptimized lowered selection DAG: "970 << printMBBReference(*FuncInfo->MBB) << " '" << BlockName971 << "'\n";972 CurDAG->dump(DumpSortedDAG));973 974#if !defined(NDEBUG) && LLVM_ENABLE_ABI_BREAKING_CHECKS975 if (TTI->hasBranchDivergence())976 CurDAG->VerifyDAGDivergence();977#endif978 979 // Second step, hack on the DAG until it only uses operations and types that980 // the target supports.981 if (ViewLegalizeTypesDAGs && MatchFilterBB)982 CurDAG->viewGraph("legalize-types input for " + BlockName);983 984 bool Changed;985 {986 NamedRegionTimer T("legalize_types", "Type Legalization", GroupName,987 GroupDescription, TimePassesIsEnabled);988 Changed = CurDAG->LegalizeTypes();989 }990 991 ISEL_DUMP(dbgs() << "\nType-legalized selection DAG: "992 << printMBBReference(*FuncInfo->MBB) << " '" << BlockName993 << "'\n";994 CurDAG->dump(DumpSortedDAG));995 996#if !defined(NDEBUG) && LLVM_ENABLE_ABI_BREAKING_CHECKS997 if (TTI->hasBranchDivergence())998 CurDAG->VerifyDAGDivergence();999#endif1000 1001 // Only allow creation of legal node types.1002 CurDAG->NewNodesMustHaveLegalTypes = true;1003 1004 if (Changed) {1005 if (ViewDAGCombineLT && MatchFilterBB)1006 CurDAG->viewGraph("dag-combine-lt input for " + BlockName);1007 1008 // Run the DAG combiner in post-type-legalize mode.1009 {1010 NamedRegionTimer T("combine_lt", "DAG Combining after legalize types",1011 GroupName, GroupDescription, TimePassesIsEnabled);1012 CurDAG->Combine(AfterLegalizeTypes, getBatchAA(), OptLevel);1013 }1014 1015 ISEL_DUMP(dbgs() << "\nOptimized type-legalized selection DAG: "1016 << printMBBReference(*FuncInfo->MBB) << " '" << BlockName1017 << "'\n";1018 CurDAG->dump(DumpSortedDAG));1019 1020#if !defined(NDEBUG) && LLVM_ENABLE_ABI_BREAKING_CHECKS1021 if (TTI->hasBranchDivergence())1022 CurDAG->VerifyDAGDivergence();1023#endif1024 }1025 1026 {1027 NamedRegionTimer T("legalize_vec", "Vector Legalization", GroupName,1028 GroupDescription, TimePassesIsEnabled);1029 Changed = CurDAG->LegalizeVectors();1030 }1031 1032 if (Changed) {1033 ISEL_DUMP(dbgs() << "\nVector-legalized selection DAG: "1034 << printMBBReference(*FuncInfo->MBB) << " '" << BlockName1035 << "'\n";1036 CurDAG->dump(DumpSortedDAG));1037 1038#if !defined(NDEBUG) && LLVM_ENABLE_ABI_BREAKING_CHECKS1039 if (TTI->hasBranchDivergence())1040 CurDAG->VerifyDAGDivergence();1041#endif1042 1043 {1044 NamedRegionTimer T("legalize_types2", "Type Legalization 2", GroupName,1045 GroupDescription, TimePassesIsEnabled);1046 CurDAG->LegalizeTypes();1047 }1048 1049 ISEL_DUMP(dbgs() << "\nVector/type-legalized selection DAG: "1050 << printMBBReference(*FuncInfo->MBB) << " '" << BlockName1051 << "'\n";1052 CurDAG->dump(DumpSortedDAG));1053 1054#if !defined(NDEBUG) && LLVM_ENABLE_ABI_BREAKING_CHECKS1055 if (TTI->hasBranchDivergence())1056 CurDAG->VerifyDAGDivergence();1057#endif1058 1059 if (ViewDAGCombineLT && MatchFilterBB)1060 CurDAG->viewGraph("dag-combine-lv input for " + BlockName);1061 1062 // Run the DAG combiner in post-type-legalize mode.1063 {1064 NamedRegionTimer T("combine_lv", "DAG Combining after legalize vectors",1065 GroupName, GroupDescription, TimePassesIsEnabled);1066 CurDAG->Combine(AfterLegalizeVectorOps, getBatchAA(), OptLevel);1067 }1068 1069 ISEL_DUMP(dbgs() << "\nOptimized vector-legalized selection DAG: "1070 << printMBBReference(*FuncInfo->MBB) << " '" << BlockName1071 << "'\n";1072 CurDAG->dump(DumpSortedDAG));1073 1074#if !defined(NDEBUG) && LLVM_ENABLE_ABI_BREAKING_CHECKS1075 if (TTI->hasBranchDivergence())1076 CurDAG->VerifyDAGDivergence();1077#endif1078 }1079 1080 if (ViewLegalizeDAGs && MatchFilterBB)1081 CurDAG->viewGraph("legalize input for " + BlockName);1082 1083 {1084 NamedRegionTimer T("legalize", "DAG Legalization", GroupName,1085 GroupDescription, TimePassesIsEnabled);1086 CurDAG->Legalize();1087 }1088 1089 ISEL_DUMP(dbgs() << "\nLegalized selection DAG: "1090 << printMBBReference(*FuncInfo->MBB) << " '" << BlockName1091 << "'\n";1092 CurDAG->dump(DumpSortedDAG));1093 1094#if !defined(NDEBUG) && LLVM_ENABLE_ABI_BREAKING_CHECKS1095 if (TTI->hasBranchDivergence())1096 CurDAG->VerifyDAGDivergence();1097#endif1098 1099 if (ViewDAGCombine2 && MatchFilterBB)1100 CurDAG->viewGraph("dag-combine2 input for " + BlockName);1101 1102 // Run the DAG combiner in post-legalize mode.1103 {1104 NamedRegionTimer T("combine2", "DAG Combining 2", GroupName,1105 GroupDescription, TimePassesIsEnabled);1106 CurDAG->Combine(AfterLegalizeDAG, getBatchAA(), OptLevel);1107 }1108 1109 ISEL_DUMP(dbgs() << "\nOptimized legalized selection DAG: "1110 << printMBBReference(*FuncInfo->MBB) << " '" << BlockName1111 << "'\n";1112 CurDAG->dump(DumpSortedDAG));1113 1114#if !defined(NDEBUG) && LLVM_ENABLE_ABI_BREAKING_CHECKS1115 if (TTI->hasBranchDivergence())1116 CurDAG->VerifyDAGDivergence();1117#endif1118 1119 if (OptLevel != CodeGenOptLevel::None)1120 ComputeLiveOutVRegInfo();1121 1122 if (ViewISelDAGs && MatchFilterBB)1123 CurDAG->viewGraph("isel input for " + BlockName);1124 1125 // Third, instruction select all of the operations to machine code, adding the1126 // code to the MachineBasicBlock.1127 {1128 NamedRegionTimer T("isel", "Instruction Selection", GroupName,1129 GroupDescription, TimePassesIsEnabled);1130 DoInstructionSelection();1131 }1132 1133 ISEL_DUMP(dbgs() << "\nSelected selection DAG: "1134 << printMBBReference(*FuncInfo->MBB) << " '" << BlockName1135 << "'\n";1136 CurDAG->dump(DumpSortedDAG));1137 1138 if (ViewSchedDAGs && MatchFilterBB)1139 CurDAG->viewGraph("scheduler input for " + BlockName);1140 1141 // Schedule machine code.1142 ScheduleDAGSDNodes *Scheduler = CreateScheduler();1143 {1144 NamedRegionTimer T("sched", "Instruction Scheduling", GroupName,1145 GroupDescription, TimePassesIsEnabled);1146 Scheduler->Run(CurDAG, FuncInfo->MBB);1147 }1148 1149 if (ViewSUnitDAGs && MatchFilterBB)1150 Scheduler->viewGraph();1151 1152 // Emit machine code to BB. This can change 'BB' to the last block being1153 // inserted into.1154 MachineBasicBlock *FirstMBB = FuncInfo->MBB, *LastMBB;1155 {1156 NamedRegionTimer T("emit", "Instruction Creation", GroupName,1157 GroupDescription, TimePassesIsEnabled);1158 1159 // FuncInfo->InsertPt is passed by reference and set to the end of the1160 // scheduled instructions.1161 LastMBB = FuncInfo->MBB = Scheduler->EmitSchedule(FuncInfo->InsertPt);1162 }1163 1164 // If the block was split, make sure we update any references that are used to1165 // update PHI nodes later on.1166 if (FirstMBB != LastMBB)1167 SDB->UpdateSplitBlock(FirstMBB, LastMBB);1168 1169 // Free the scheduler state.1170 {1171 NamedRegionTimer T("cleanup", "Instruction Scheduling Cleanup", GroupName,1172 GroupDescription, TimePassesIsEnabled);1173 delete Scheduler;1174 }1175 1176 // Free the SelectionDAG state, now that we're finished with it.1177 CurDAG->clear();1178}1179 1180namespace {1181 1182/// ISelUpdater - helper class to handle updates of the instruction selection1183/// graph.1184class ISelUpdater : public SelectionDAG::DAGUpdateListener {1185 SelectionDAG::allnodes_iterator &ISelPosition;1186 1187public:1188 ISelUpdater(SelectionDAG &DAG, SelectionDAG::allnodes_iterator &isp)1189 : SelectionDAG::DAGUpdateListener(DAG), ISelPosition(isp) {}1190 1191 /// NodeDeleted - Handle nodes deleted from the graph. If the node being1192 /// deleted is the current ISelPosition node, update ISelPosition.1193 ///1194 void NodeDeleted(SDNode *N, SDNode *E) override {1195 if (ISelPosition == SelectionDAG::allnodes_iterator(N))1196 ++ISelPosition;1197 }1198 1199 /// NodeInserted - Handle new nodes inserted into the graph: propagate1200 /// metadata from root nodes that also applies to new nodes, in case the root1201 /// is later deleted.1202 void NodeInserted(SDNode *N) override {1203 SDNode *CurNode = &*ISelPosition;1204 if (MDNode *MD = DAG.getPCSections(CurNode))1205 DAG.addPCSections(N, MD);1206 if (MDNode *MMRA = DAG.getMMRAMetadata(CurNode))1207 DAG.addMMRAMetadata(N, MMRA);1208 }1209};1210 1211} // end anonymous namespace1212 1213// This function is used to enforce the topological node id property1214// leveraged during instruction selection. Before the selection process all1215// nodes are given a non-negative id such that all nodes have a greater id than1216// their operands. As this holds transitively we can prune checks that a node N1217// is a predecessor of M another by not recursively checking through M's1218// operands if N's ID is larger than M's ID. This significantly improves1219// performance of various legality checks (e.g. IsLegalToFold / UpdateChains).1220 1221// However, when we fuse multiple nodes into a single node during the1222// selection we may induce a predecessor relationship between inputs and1223// outputs of distinct nodes being merged, violating the topological property.1224// Should a fused node have a successor which has yet to be selected,1225// our legality checks would be incorrect. To avoid this we mark all unselected1226// successor nodes, i.e. id != -1, as invalid for pruning by bit-negating (x =>1227// (-(x+1))) the ids and modify our pruning check to ignore negative Ids of M.1228// We use bit-negation to more clearly enforce that node id -1 can only be1229// achieved by selected nodes. As the conversion is reversable to the original1230// Id, topological pruning can still be leveraged when looking for unselected1231// nodes. This method is called internally in all ISel replacement related1232// functions.1233void SelectionDAGISel::EnforceNodeIdInvariant(SDNode *Node) {1234 SmallVector<SDNode *, 4> Nodes;1235 Nodes.push_back(Node);1236 1237 while (!Nodes.empty()) {1238 SDNode *N = Nodes.pop_back_val();1239 for (auto *U : N->users()) {1240 auto UId = U->getNodeId();1241 if (UId > 0) {1242 InvalidateNodeId(U);1243 Nodes.push_back(U);1244 }1245 }1246 }1247}1248 1249// InvalidateNodeId - As explained in EnforceNodeIdInvariant, mark a1250// NodeId with the equivalent node id which is invalid for topological1251// pruning.1252void SelectionDAGISel::InvalidateNodeId(SDNode *N) {1253 int InvalidId = -(N->getNodeId() + 1);1254 N->setNodeId(InvalidId);1255}1256 1257// getUninvalidatedNodeId - get original uninvalidated node id.1258int SelectionDAGISel::getUninvalidatedNodeId(SDNode *N) {1259 int Id = N->getNodeId();1260 if (Id < -1)1261 return -(Id + 1);1262 return Id;1263}1264 1265void SelectionDAGISel::DoInstructionSelection() {1266 LLVM_DEBUG(dbgs() << "===== Instruction selection begins: "1267 << printMBBReference(*FuncInfo->MBB) << " '"1268 << FuncInfo->MBB->getName() << "'\n");1269 1270 PreprocessISelDAG();1271 1272 // Select target instructions for the DAG.1273 {1274 // Number all nodes with a topological order and set DAGSize.1275 DAGSize = CurDAG->AssignTopologicalOrder();1276 1277 // Create a dummy node (which is not added to allnodes), that adds1278 // a reference to the root node, preventing it from being deleted,1279 // and tracking any changes of the root.1280 HandleSDNode Dummy(CurDAG->getRoot());1281 SelectionDAG::allnodes_iterator ISelPosition (CurDAG->getRoot().getNode());1282 ++ISelPosition;1283 1284 // Make sure that ISelPosition gets properly updated when nodes are deleted1285 // in calls made from this function. New nodes inherit relevant metadata.1286 ISelUpdater ISU(*CurDAG, ISelPosition);1287 1288 // The AllNodes list is now topological-sorted. Visit the1289 // nodes by starting at the end of the list (the root of the1290 // graph) and preceding back toward the beginning (the entry1291 // node).1292 while (ISelPosition != CurDAG->allnodes_begin()) {1293 SDNode *Node = &*--ISelPosition;1294 // Skip dead nodes. DAGCombiner is expected to eliminate all dead nodes,1295 // but there are currently some corner cases that it misses. Also, this1296 // makes it theoretically possible to disable the DAGCombiner.1297 if (Node->use_empty())1298 continue;1299 1300#ifndef NDEBUG1301 SmallVector<SDNode *, 4> Nodes;1302 Nodes.push_back(Node);1303 1304 while (!Nodes.empty()) {1305 auto N = Nodes.pop_back_val();1306 if (N->getOpcode() == ISD::TokenFactor || N->getNodeId() < 0)1307 continue;1308 for (const SDValue &Op : N->op_values()) {1309 if (Op->getOpcode() == ISD::TokenFactor)1310 Nodes.push_back(Op.getNode());1311 else {1312 // We rely on topological ordering of node ids for checking for1313 // cycles when fusing nodes during selection. All unselected nodes1314 // successors of an already selected node should have a negative id.1315 // This assertion will catch such cases. If this assertion triggers1316 // it is likely you using DAG-level Value/Node replacement functions1317 // (versus equivalent ISEL replacement) in backend-specific1318 // selections. See comment in EnforceNodeIdInvariant for more1319 // details.1320 assert(Op->getNodeId() != -1 &&1321 "Node has already selected predecessor node");1322 }1323 }1324 }1325#endif1326 1327 // When we are using non-default rounding modes or FP exception behavior1328 // FP operations are represented by StrictFP pseudo-operations. For1329 // targets that do not (yet) understand strict FP operations directly,1330 // we convert them to normal FP opcodes instead at this point. This1331 // will allow them to be handled by existing target-specific instruction1332 // selectors.1333 if (!TLI->isStrictFPEnabled() && Node->isStrictFPOpcode()) {1334 // For some opcodes, we need to call TLI->getOperationAction using1335 // the first operand type instead of the result type. Note that this1336 // must match what SelectionDAGLegalize::LegalizeOp is doing.1337 EVT ActionVT;1338 switch (Node->getOpcode()) {1339 case ISD::STRICT_SINT_TO_FP:1340 case ISD::STRICT_UINT_TO_FP:1341 case ISD::STRICT_LRINT:1342 case ISD::STRICT_LLRINT:1343 case ISD::STRICT_LROUND:1344 case ISD::STRICT_LLROUND:1345 case ISD::STRICT_FSETCC:1346 case ISD::STRICT_FSETCCS:1347 ActionVT = Node->getOperand(1).getValueType();1348 break;1349 default:1350 ActionVT = Node->getValueType(0);1351 break;1352 }1353 if (TLI->getOperationAction(Node->getOpcode(), ActionVT)1354 == TargetLowering::Expand)1355 Node = CurDAG->mutateStrictFPToFP(Node);1356 }1357 1358 LLVM_DEBUG(dbgs() << "\nISEL: Starting selection on root node: ";1359 Node->dump(CurDAG));1360 1361 Select(Node);1362 }1363 1364 CurDAG->setRoot(Dummy.getValue());1365 }1366 1367 LLVM_DEBUG(dbgs() << "\n===== Instruction selection ends:\n");1368 1369 PostprocessISelDAG();1370}1371 1372static bool hasExceptionPointerOrCodeUser(const CatchPadInst *CPI) {1373 for (const User *U : CPI->users()) {1374 if (const IntrinsicInst *EHPtrCall = dyn_cast<IntrinsicInst>(U)) {1375 Intrinsic::ID IID = EHPtrCall->getIntrinsicID();1376 if (IID == Intrinsic::eh_exceptionpointer ||1377 IID == Intrinsic::eh_exceptioncode)1378 return true;1379 }1380 }1381 return false;1382}1383 1384// wasm.landingpad.index intrinsic is for associating a landing pad index number1385// with a catchpad instruction. Retrieve the landing pad index in the intrinsic1386// and store the mapping in the function.1387static void mapWasmLandingPadIndex(MachineBasicBlock *MBB,1388 const CatchPadInst *CPI) {1389 MachineFunction *MF = MBB->getParent();1390 // In case of single catch (...), we don't emit LSDA, so we don't need1391 // this information.1392 bool IsSingleCatchAllClause =1393 CPI->arg_size() == 1 &&1394 cast<Constant>(CPI->getArgOperand(0))->isNullValue();1395 // cathchpads for longjmp use an empty type list, e.g. catchpad within %0 []1396 // and they don't need LSDA info1397 bool IsCatchLongjmp = CPI->arg_size() == 0;1398 if (!IsSingleCatchAllClause && !IsCatchLongjmp) {1399 // Create a mapping from landing pad label to landing pad index.1400 bool IntrFound = false;1401 for (const User *U : CPI->users()) {1402 if (const auto *Call = dyn_cast<IntrinsicInst>(U)) {1403 Intrinsic::ID IID = Call->getIntrinsicID();1404 if (IID == Intrinsic::wasm_landingpad_index) {1405 Value *IndexArg = Call->getArgOperand(1);1406 int Index = cast<ConstantInt>(IndexArg)->getZExtValue();1407 MF->setWasmLandingPadIndex(MBB, Index);1408 IntrFound = true;1409 break;1410 }1411 }1412 }1413 assert(IntrFound && "wasm.landingpad.index intrinsic not found!");1414 (void)IntrFound;1415 }1416}1417 1418/// PrepareEHLandingPad - Emit an EH_LABEL, set up live-in registers, and1419/// do other setup for EH landing-pad blocks.1420bool SelectionDAGISel::PrepareEHLandingPad() {1421 MachineBasicBlock *MBB = FuncInfo->MBB;1422 const Constant *PersonalityFn = FuncInfo->Fn->getPersonalityFn();1423 const BasicBlock *LLVMBB = MBB->getBasicBlock();1424 const TargetRegisterClass *PtrRC =1425 TLI->getRegClassFor(TLI->getPointerTy(CurDAG->getDataLayout()));1426 1427 auto Pers = classifyEHPersonality(PersonalityFn);1428 1429 // Catchpads have one live-in register, which typically holds the exception1430 // pointer or code.1431 if (isFuncletEHPersonality(Pers)) {1432 if (const auto *CPI = dyn_cast<CatchPadInst>(LLVMBB->getFirstNonPHIIt())) {1433 if (hasExceptionPointerOrCodeUser(CPI)) {1434 // Get or create the virtual register to hold the pointer or code. Mark1435 // the live in physreg and copy into the vreg.1436 MCRegister EHPhysReg = TLI->getExceptionPointerRegister(PersonalityFn);1437 assert(EHPhysReg && "target lacks exception pointer register");1438 MBB->addLiveIn(EHPhysReg);1439 Register VReg = FuncInfo->getCatchPadExceptionPointerVReg(CPI, PtrRC);1440 BuildMI(*MBB, FuncInfo->InsertPt, SDB->getCurDebugLoc(),1441 TII->get(TargetOpcode::COPY), VReg)1442 .addReg(EHPhysReg, RegState::Kill);1443 }1444 }1445 return true;1446 }1447 1448 // Add a label to mark the beginning of the landing pad. Deletion of the1449 // landing pad can thus be detected via the MachineModuleInfo.1450 MCSymbol *Label = MF->addLandingPad(MBB);1451 1452 const MCInstrDesc &II = TII->get(TargetOpcode::EH_LABEL);1453 BuildMI(*MBB, FuncInfo->InsertPt, SDB->getCurDebugLoc(), II)1454 .addSym(Label);1455 1456 // If the unwinder does not preserve all registers, ensure that the1457 // function marks the clobbered registers as used.1458 const TargetRegisterInfo &TRI = *MF->getSubtarget().getRegisterInfo();1459 if (auto *RegMask = TRI.getCustomEHPadPreservedMask(*MF))1460 MF->getRegInfo().addPhysRegsUsedFromRegMask(RegMask);1461 1462 if (Pers == EHPersonality::Wasm_CXX) {1463 if (const auto *CPI = dyn_cast<CatchPadInst>(LLVMBB->getFirstNonPHIIt()))1464 mapWasmLandingPadIndex(MBB, CPI);1465 } else {1466 // Assign the call site to the landing pad's begin label.1467 MF->setCallSiteLandingPad(Label, SDB->LPadToCallSiteMap[MBB]);1468 // Mark exception register as live in.1469 if (MCRegister Reg = TLI->getExceptionPointerRegister(PersonalityFn))1470 FuncInfo->ExceptionPointerVirtReg = MBB->addLiveIn(Reg, PtrRC);1471 // Mark exception selector register as live in.1472 if (MCRegister Reg = TLI->getExceptionSelectorRegister(PersonalityFn))1473 FuncInfo->ExceptionSelectorVirtReg = MBB->addLiveIn(Reg, PtrRC);1474 }1475 1476 return true;1477}1478 1479// Mark and Report IPToState for each Block under IsEHa1480void SelectionDAGISel::reportIPToStateForBlocks(MachineFunction *MF) {1481 llvm::WinEHFuncInfo *EHInfo = MF->getWinEHFuncInfo();1482 if (!EHInfo)1483 return;1484 for (MachineBasicBlock &MBB : *MF) {1485 const BasicBlock *BB = MBB.getBasicBlock();1486 int State = EHInfo->BlockToStateMap[BB];1487 if (BB->getFirstMayFaultInst()) {1488 // Report IP range only for blocks with Faulty inst1489 auto MBBb = MBB.getFirstNonPHI();1490 1491 if (MBBb == MBB.end())1492 continue;1493 1494 MachineInstr *MIb = &*MBBb;1495 if (MIb->isTerminator())1496 continue;1497 1498 // Insert EH Labels1499 MCSymbol *BeginLabel = MF->getContext().createTempSymbol();1500 MCSymbol *EndLabel = MF->getContext().createTempSymbol();1501 EHInfo->addIPToStateRange(State, BeginLabel, EndLabel);1502 BuildMI(MBB, MBBb, SDB->getCurDebugLoc(),1503 TII->get(TargetOpcode::EH_LABEL))1504 .addSym(BeginLabel);1505 auto MBBe = MBB.instr_end();1506 MachineInstr *MIe = &*(--MBBe);1507 // insert before (possible multiple) terminators1508 while (MIe->isTerminator())1509 MIe = &*(--MBBe);1510 ++MBBe;1511 BuildMI(MBB, MBBe, SDB->getCurDebugLoc(),1512 TII->get(TargetOpcode::EH_LABEL))1513 .addSym(EndLabel);1514 }1515 }1516}1517 1518/// isFoldedOrDeadInstruction - Return true if the specified instruction is1519/// side-effect free and is either dead or folded into a generated instruction.1520/// Return false if it needs to be emitted.1521static bool isFoldedOrDeadInstruction(const Instruction *I,1522 const FunctionLoweringInfo &FuncInfo) {1523 return !I->mayWriteToMemory() && // Side-effecting instructions aren't folded.1524 !I->isTerminator() && // Terminators aren't folded.1525 !I->isEHPad() && // EH pad instructions aren't folded.1526 !FuncInfo.isExportedInst(I); // Exported instrs must be computed.1527}1528 1529static bool processIfEntryValueDbgDeclare(FunctionLoweringInfo &FuncInfo,1530 const Value *Arg, DIExpression *Expr,1531 DILocalVariable *Var,1532 DebugLoc DbgLoc) {1533 if (!Expr->isEntryValue() || !isa<Argument>(Arg))1534 return false;1535 1536 auto ArgIt = FuncInfo.ValueMap.find(Arg);1537 if (ArgIt == FuncInfo.ValueMap.end())1538 return false;1539 Register ArgVReg = ArgIt->getSecond();1540 1541 // Find the corresponding livein physical register to this argument.1542 for (auto [PhysReg, VirtReg] : FuncInfo.RegInfo->liveins())1543 if (VirtReg == ArgVReg) {1544 // Append an op deref to account for the fact that this is a dbg_declare.1545 Expr = DIExpression::append(Expr, dwarf::DW_OP_deref);1546 FuncInfo.MF->setVariableDbgInfo(Var, Expr, PhysReg, DbgLoc);1547 LLVM_DEBUG(dbgs() << "processDbgDeclare: setVariableDbgInfo Var=" << *Var1548 << ", Expr=" << *Expr << ", MCRegister=" << PhysReg1549 << ", DbgLoc=" << DbgLoc << "\n");1550 return true;1551 }1552 return false;1553}1554 1555static bool processDbgDeclare(FunctionLoweringInfo &FuncInfo,1556 const Value *Address, DIExpression *Expr,1557 DILocalVariable *Var, DebugLoc DbgLoc) {1558 if (!Address) {1559 LLVM_DEBUG(dbgs() << "processDbgDeclares skipping " << *Var1560 << " (bad address)\n");1561 return false;1562 }1563 1564 if (processIfEntryValueDbgDeclare(FuncInfo, Address, Expr, Var, DbgLoc))1565 return true;1566 1567 if (!Address->getType()->isPointerTy())1568 return false;1569 1570 MachineFunction *MF = FuncInfo.MF;1571 const DataLayout &DL = MF->getDataLayout();1572 1573 assert(Var && "Missing variable");1574 assert(DbgLoc && "Missing location");1575 1576 // Look through casts and constant offset GEPs. These mostly come from1577 // inalloca.1578 APInt Offset(DL.getIndexTypeSizeInBits(Address->getType()), 0);1579 Address = Address->stripAndAccumulateInBoundsConstantOffsets(DL, Offset);1580 1581 // Check if the variable is a static alloca or a byval or inalloca1582 // argument passed in memory. If it is not, then we will ignore this1583 // intrinsic and handle this during isel like dbg.value.1584 int FI = std::numeric_limits<int>::max();1585 if (const auto *AI = dyn_cast<AllocaInst>(Address)) {1586 auto SI = FuncInfo.StaticAllocaMap.find(AI);1587 if (SI != FuncInfo.StaticAllocaMap.end())1588 FI = SI->second;1589 } else if (const auto *Arg = dyn_cast<Argument>(Address))1590 FI = FuncInfo.getArgumentFrameIndex(Arg);1591 1592 if (FI == std::numeric_limits<int>::max())1593 return false;1594 1595 if (Offset.getBoolValue())1596 Expr = DIExpression::prepend(Expr, DIExpression::ApplyOffset,1597 Offset.getZExtValue());1598 1599 LLVM_DEBUG(dbgs() << "processDbgDeclare: setVariableDbgInfo Var=" << *Var1600 << ", Expr=" << *Expr << ", FI=" << FI1601 << ", DbgLoc=" << DbgLoc << "\n");1602 MF->setVariableDbgInfo(Var, Expr, FI, DbgLoc);1603 return true;1604}1605 1606/// Collect llvm.dbg.declare information. This is done after argument lowering1607/// in case the declarations refer to arguments.1608static void processDbgDeclares(FunctionLoweringInfo &FuncInfo) {1609 for (const auto &I : instructions(*FuncInfo.Fn)) {1610 for (const DbgVariableRecord &DVR : filterDbgVars(I.getDbgRecordRange())) {1611 if (DVR.Type == DbgVariableRecord::LocationType::Declare &&1612 processDbgDeclare(FuncInfo, DVR.getVariableLocationOp(0),1613 DVR.getExpression(), DVR.getVariable(),1614 DVR.getDebugLoc()))1615 FuncInfo.PreprocessedDVRDeclares.insert(&DVR);1616 }1617 }1618}1619 1620/// Collect single location variable information generated with assignment1621/// tracking. This is done after argument lowering in case the declarations1622/// refer to arguments.1623static void processSingleLocVars(FunctionLoweringInfo &FuncInfo,1624 FunctionVarLocs const *FnVarLocs) {1625 for (auto It = FnVarLocs->single_locs_begin(),1626 End = FnVarLocs->single_locs_end();1627 It != End; ++It) {1628 assert(!It->Values.hasArgList() && "Single loc variadic ops not supported");1629 processDbgDeclare(FuncInfo, It->Values.getVariableLocationOp(0), It->Expr,1630 FnVarLocs->getDILocalVariable(It->VariableID), It->DL);1631 }1632}1633 1634void SelectionDAGISel::SelectAllBasicBlocks(const Function &Fn) {1635 FastISelFailed = false;1636 // Initialize the Fast-ISel state, if needed.1637 FastISel *FastIS = nullptr;1638 if (TM.Options.EnableFastISel) {1639 LLVM_DEBUG(dbgs() << "Enabling fast-isel\n");1640 FastIS = TLI->createFastISel(*FuncInfo, LibInfo);1641 }1642 1643 ReversePostOrderTraversal<const Function*> RPOT(&Fn);1644 1645 // Lower arguments up front. An RPO iteration always visits the entry block1646 // first.1647 assert(*RPOT.begin() == &Fn.getEntryBlock());1648 ++NumEntryBlocks;1649 1650 // Set up FuncInfo for ISel. Entry blocks never have PHIs.1651 FuncInfo->MBB = FuncInfo->getMBB(&Fn.getEntryBlock());1652 FuncInfo->InsertPt = FuncInfo->MBB->begin();1653 1654 CurDAG->setFunctionLoweringInfo(FuncInfo.get());1655 1656 if (!FastIS) {1657 LowerArguments(Fn);1658 } else {1659 // See if fast isel can lower the arguments.1660 FastIS->startNewBlock();1661 if (!FastIS->lowerArguments()) {1662 FastISelFailed = true;1663 // Fast isel failed to lower these arguments1664 ++NumFastIselFailLowerArguments;1665 1666 OptimizationRemarkMissed R("sdagisel", "FastISelFailure",1667 Fn.getSubprogram(),1668 &Fn.getEntryBlock());1669 R << "FastISel didn't lower all arguments: "1670 << ore::NV("Prototype", Fn.getFunctionType());1671 reportFastISelFailure(*MF, *ORE, R, EnableFastISelAbort > 1);1672 1673 // Use SelectionDAG argument lowering1674 LowerArguments(Fn);1675 CurDAG->setRoot(SDB->getControlRoot());1676 SDB->clear();1677 CodeGenAndEmitDAG();1678 }1679 1680 // If we inserted any instructions at the beginning, make a note of1681 // where they are, so we can be sure to emit subsequent instructions1682 // after them.1683 if (FuncInfo->InsertPt != FuncInfo->MBB->begin())1684 FastIS->setLastLocalValue(&*std::prev(FuncInfo->InsertPt));1685 else1686 FastIS->setLastLocalValue(nullptr);1687 }1688 1689 bool Inserted = SwiftError->createEntriesInEntryBlock(SDB->getCurDebugLoc());1690 1691 if (FastIS && Inserted)1692 FastIS->setLastLocalValue(&*std::prev(FuncInfo->InsertPt));1693 1694 if (isAssignmentTrackingEnabled(*Fn.getParent())) {1695 assert(CurDAG->getFunctionVarLocs() &&1696 "expected AssignmentTrackingAnalysis pass results");1697 processSingleLocVars(*FuncInfo, CurDAG->getFunctionVarLocs());1698 } else {1699 processDbgDeclares(*FuncInfo);1700 }1701 1702 // Iterate over all basic blocks in the function.1703 FuncInfo->VisitedBBs.assign(Fn.getMaxBlockNumber(), false);1704 for (const BasicBlock *LLVMBB : RPOT) {1705 if (OptLevel != CodeGenOptLevel::None) {1706 bool AllPredsVisited = true;1707 for (const BasicBlock *Pred : predecessors(LLVMBB)) {1708 if (!FuncInfo->VisitedBBs[Pred->getNumber()]) {1709 AllPredsVisited = false;1710 break;1711 }1712 }1713 1714 if (AllPredsVisited) {1715 for (const PHINode &PN : LLVMBB->phis())1716 FuncInfo->ComputePHILiveOutRegInfo(&PN);1717 } else {1718 for (const PHINode &PN : LLVMBB->phis())1719 FuncInfo->InvalidatePHILiveOutRegInfo(&PN);1720 }1721 1722 FuncInfo->VisitedBBs[LLVMBB->getNumber()] = true;1723 }1724 1725 // Fake uses that follow tail calls are dropped. To avoid this, move1726 // such fake uses in front of the tail call, provided they don't1727 // use anything def'd by or after the tail call.1728 {1729 BasicBlock::iterator BBStart =1730 const_cast<BasicBlock *>(LLVMBB)->getFirstNonPHIIt();1731 BasicBlock::iterator BBEnd = const_cast<BasicBlock *>(LLVMBB)->end();1732 preserveFakeUses(BBStart, BBEnd);1733 }1734 1735 BasicBlock::const_iterator const Begin = LLVMBB->getFirstNonPHIIt();1736 BasicBlock::const_iterator const End = LLVMBB->end();1737 BasicBlock::const_iterator BI = End;1738 1739 FuncInfo->MBB = FuncInfo->getMBB(LLVMBB);1740 if (!FuncInfo->MBB)1741 continue; // Some blocks like catchpads have no code or MBB.1742 1743 // Insert new instructions after any phi or argument setup code.1744 FuncInfo->InsertPt = FuncInfo->MBB->end();1745 1746 // Setup an EH landing-pad block.1747 FuncInfo->ExceptionPointerVirtReg = Register();1748 FuncInfo->ExceptionSelectorVirtReg = Register();1749 if (LLVMBB->isEHPad()) {1750 if (!PrepareEHLandingPad())1751 continue;1752 1753 if (!FastIS) {1754 SDValue NewRoot = TLI->lowerEHPadEntry(CurDAG->getRoot(),1755 SDB->getCurSDLoc(), *CurDAG);1756 if (NewRoot && NewRoot != CurDAG->getRoot())1757 CurDAG->setRoot(NewRoot);1758 }1759 }1760 1761 // Before doing SelectionDAG ISel, see if FastISel has been requested.1762 if (FastIS) {1763 if (LLVMBB != &Fn.getEntryBlock())1764 FastIS->startNewBlock();1765 1766 unsigned NumFastIselRemaining = std::distance(Begin, End);1767 1768 // Pre-assign swifterror vregs.1769 SwiftError->preassignVRegs(FuncInfo->MBB, Begin, End);1770 1771 // Do FastISel on as many instructions as possible.1772 for (; BI != Begin; --BI) {1773 const Instruction *Inst = &*std::prev(BI);1774 1775 // If we no longer require this instruction, skip it.1776 if (isFoldedOrDeadInstruction(Inst, *FuncInfo) ||1777 ElidedArgCopyInstrs.count(Inst)) {1778 --NumFastIselRemaining;1779 FastIS->handleDbgInfo(Inst);1780 continue;1781 }1782 1783 // Bottom-up: reset the insert pos at the top, after any local-value1784 // instructions.1785 FastIS->recomputeInsertPt();1786 1787 // Try to select the instruction with FastISel.1788 if (FastIS->selectInstruction(Inst)) {1789 --NumFastIselRemaining;1790 ++NumFastIselSuccess;1791 1792 FastIS->handleDbgInfo(Inst);1793 // If fast isel succeeded, skip over all the folded instructions, and1794 // then see if there is a load right before the selected instructions.1795 // Try to fold the load if so.1796 const Instruction *BeforeInst = Inst;1797 while (BeforeInst != &*Begin) {1798 BeforeInst = &*std::prev(BasicBlock::const_iterator(BeforeInst));1799 if (!isFoldedOrDeadInstruction(BeforeInst, *FuncInfo))1800 break;1801 }1802 if (BeforeInst != Inst && isa<LoadInst>(BeforeInst) &&1803 BeforeInst->hasOneUse() &&1804 FastIS->tryToFoldLoad(cast<LoadInst>(BeforeInst), Inst)) {1805 // If we succeeded, don't re-select the load.1806 LLVM_DEBUG(dbgs()1807 << "FastISel folded load: " << *BeforeInst << "\n");1808 FastIS->handleDbgInfo(BeforeInst);1809 BI = std::next(BasicBlock::const_iterator(BeforeInst));1810 --NumFastIselRemaining;1811 ++NumFastIselSuccess;1812 }1813 continue;1814 }1815 1816 FastISelFailed = true;1817 1818 // Then handle certain instructions as single-LLVM-Instruction blocks.1819 // We cannot separate out GCrelocates to their own blocks since we need1820 // to keep track of gc-relocates for a particular gc-statepoint. This is1821 // done by SelectionDAGBuilder::LowerAsSTATEPOINT, called before1822 // visitGCRelocate.1823 if (isa<CallInst>(Inst) && !isa<GCStatepointInst>(Inst) &&1824 !isa<GCRelocateInst>(Inst) && !isa<GCResultInst>(Inst)) {1825 OptimizationRemarkMissed R("sdagisel", "FastISelFailure",1826 Inst->getDebugLoc(), LLVMBB);1827 1828 R << "FastISel missed call";1829 1830 if (R.isEnabled() || EnableFastISelAbort) {1831 std::string InstStrStorage;1832 raw_string_ostream InstStr(InstStrStorage);1833 InstStr << *Inst;1834 1835 R << ": " << InstStrStorage;1836 }1837 1838 reportFastISelFailure(*MF, *ORE, R, EnableFastISelAbort > 2);1839 1840 if (!Inst->getType()->isVoidTy() && !Inst->getType()->isTokenTy() &&1841 !Inst->use_empty()) {1842 Register &R = FuncInfo->ValueMap[Inst];1843 if (!R)1844 R = FuncInfo->CreateRegs(Inst);1845 }1846 1847 bool HadTailCall = false;1848 MachineBasicBlock::iterator SavedInsertPt = FuncInfo->InsertPt;1849 SelectBasicBlock(Inst->getIterator(), BI, HadTailCall);1850 1851 // If the call was emitted as a tail call, we're done with the block.1852 // We also need to delete any previously emitted instructions.1853 if (HadTailCall) {1854 FastIS->removeDeadCode(SavedInsertPt, FuncInfo->MBB->end());1855 --BI;1856 break;1857 }1858 1859 // Recompute NumFastIselRemaining as Selection DAG instruction1860 // selection may have handled the call, input args, etc.1861 unsigned RemainingNow = std::distance(Begin, BI);1862 NumFastIselFailures += NumFastIselRemaining - RemainingNow;1863 NumFastIselRemaining = RemainingNow;1864 continue;1865 }1866 1867 OptimizationRemarkMissed R("sdagisel", "FastISelFailure",1868 Inst->getDebugLoc(), LLVMBB);1869 1870 bool ShouldAbort = EnableFastISelAbort;1871 if (Inst->isTerminator()) {1872 // Use a different message for terminator misses.1873 R << "FastISel missed terminator";1874 // Don't abort for terminator unless the level is really high1875 ShouldAbort = (EnableFastISelAbort > 2);1876 } else {1877 R << "FastISel missed";1878 }1879 1880 if (R.isEnabled() || EnableFastISelAbort) {1881 std::string InstStrStorage;1882 raw_string_ostream InstStr(InstStrStorage);1883 InstStr << *Inst;1884 R << ": " << InstStrStorage;1885 }1886 1887 reportFastISelFailure(*MF, *ORE, R, ShouldAbort);1888 1889 NumFastIselFailures += NumFastIselRemaining;1890 break;1891 }1892 1893 FastIS->recomputeInsertPt();1894 }1895 1896 if (SP->shouldEmitSDCheck(*LLVMBB)) {1897 bool FunctionBasedInstrumentation =1898 TLI->getSSPStackGuardCheck(*Fn.getParent()) && Fn.hasMinSize();1899 SDB->SPDescriptor.initialize(LLVMBB, FuncInfo->getMBB(LLVMBB),1900 FunctionBasedInstrumentation);1901 }1902 1903 if (Begin != BI)1904 ++NumDAGBlocks;1905 else1906 ++NumFastIselBlocks;1907 1908 if (Begin != BI) {1909 // Run SelectionDAG instruction selection on the remainder of the block1910 // not handled by FastISel. If FastISel is not run, this is the entire1911 // block.1912 bool HadTailCall;1913 SelectBasicBlock(Begin, BI, HadTailCall);1914 1915 // But if FastISel was run, we already selected some of the block.1916 // If we emitted a tail-call, we need to delete any previously emitted1917 // instruction that follows it.1918 if (FastIS && HadTailCall && FuncInfo->InsertPt != FuncInfo->MBB->end())1919 FastIS->removeDeadCode(FuncInfo->InsertPt, FuncInfo->MBB->end());1920 }1921 1922 if (FastIS)1923 FastIS->finishBasicBlock();1924 FinishBasicBlock();1925 FuncInfo->PHINodesToUpdate.clear();1926 ElidedArgCopyInstrs.clear();1927 }1928 1929 // AsynchEH: Report Block State under -AsynchEH1930 if (Fn.getParent()->getModuleFlag("eh-asynch"))1931 reportIPToStateForBlocks(MF);1932 1933 SP->copyToMachineFrameInfo(MF->getFrameInfo());1934 1935 SwiftError->propagateVRegs();1936 1937 delete FastIS;1938 SDB->clearDanglingDebugInfo();1939 SDB->SPDescriptor.resetPerFunctionState();1940}1941 1942void1943SelectionDAGISel::FinishBasicBlock() {1944 LLVM_DEBUG(dbgs() << "Total amount of phi nodes to update: "1945 << FuncInfo->PHINodesToUpdate.size() << "\n";1946 for (unsigned i = 0, e = FuncInfo->PHINodesToUpdate.size(); i != e;1947 ++i) dbgs()1948 << "Node " << i << " : (" << FuncInfo->PHINodesToUpdate[i].first1949 << ", " << printReg(FuncInfo->PHINodesToUpdate[i].second)1950 << ")\n");1951 1952 // Next, now that we know what the last MBB the LLVM BB expanded is, update1953 // PHI nodes in successors.1954 for (unsigned i = 0, e = FuncInfo->PHINodesToUpdate.size(); i != e; ++i) {1955 MachineInstrBuilder PHI(*MF, FuncInfo->PHINodesToUpdate[i].first);1956 assert(PHI->isPHI() &&1957 "This is not a machine PHI node that we are updating!");1958 if (!FuncInfo->MBB->isSuccessor(PHI->getParent()))1959 continue;1960 PHI.addReg(FuncInfo->PHINodesToUpdate[i].second).addMBB(FuncInfo->MBB);1961 }1962 1963 // Handle stack protector.1964 if (SDB->SPDescriptor.shouldEmitFunctionBasedCheckStackProtector()) {1965 // The target provides a guard check function. There is no need to1966 // generate error handling code or to split current basic block.1967 MachineBasicBlock *ParentMBB = SDB->SPDescriptor.getParentMBB();1968 1969 // Add load and check to the basicblock.1970 FuncInfo->MBB = ParentMBB;1971 FuncInfo->InsertPt = findSplitPointForStackProtector(ParentMBB, *TII);1972 SDB->visitSPDescriptorParent(SDB->SPDescriptor, ParentMBB);1973 CurDAG->setRoot(SDB->getRoot());1974 SDB->clear();1975 CodeGenAndEmitDAG();1976 1977 // Clear the Per-BB State.1978 SDB->SPDescriptor.resetPerBBState();1979 } else if (SDB->SPDescriptor.shouldEmitStackProtector()) {1980 MachineBasicBlock *ParentMBB = SDB->SPDescriptor.getParentMBB();1981 MachineBasicBlock *SuccessMBB = SDB->SPDescriptor.getSuccessMBB();1982 1983 // Find the split point to split the parent mbb. At the same time copy all1984 // physical registers used in the tail of parent mbb into virtual registers1985 // before the split point and back into physical registers after the split1986 // point. This prevents us needing to deal with Live-ins and many other1987 // register allocation issues caused by us splitting the parent mbb. The1988 // register allocator will clean up said virtual copies later on.1989 MachineBasicBlock::iterator SplitPoint =1990 findSplitPointForStackProtector(ParentMBB, *TII);1991 1992 // Splice the terminator of ParentMBB into SuccessMBB.1993 SuccessMBB->splice(SuccessMBB->end(), ParentMBB, SplitPoint,1994 ParentMBB->end());1995 1996 // Add compare/jump on neq/jump to the parent BB.1997 FuncInfo->MBB = ParentMBB;1998 FuncInfo->InsertPt = ParentMBB->end();1999 SDB->visitSPDescriptorParent(SDB->SPDescriptor, ParentMBB);2000 CurDAG->setRoot(SDB->getRoot());2001 SDB->clear();2002 CodeGenAndEmitDAG();2003 2004 // CodeGen Failure MBB if we have not codegened it yet.2005 MachineBasicBlock *FailureMBB = SDB->SPDescriptor.getFailureMBB();2006 if (FailureMBB->empty()) {2007 FuncInfo->MBB = FailureMBB;2008 FuncInfo->InsertPt = FailureMBB->end();2009 SDB->visitSPDescriptorFailure(SDB->SPDescriptor);2010 CurDAG->setRoot(SDB->getRoot());2011 SDB->clear();2012 CodeGenAndEmitDAG();2013 }2014 2015 // Clear the Per-BB State.2016 SDB->SPDescriptor.resetPerBBState();2017 }2018 2019 // Lower each BitTestBlock.2020 for (auto &BTB : SDB->SL->BitTestCases) {2021 // Lower header first, if it wasn't already lowered2022 if (!BTB.Emitted) {2023 // Set the current basic block to the mbb we wish to insert the code into2024 FuncInfo->MBB = BTB.Parent;2025 FuncInfo->InsertPt = FuncInfo->MBB->end();2026 // Emit the code2027 SDB->visitBitTestHeader(BTB, FuncInfo->MBB);2028 CurDAG->setRoot(SDB->getRoot());2029 SDB->clear();2030 CodeGenAndEmitDAG();2031 }2032 2033 BranchProbability UnhandledProb = BTB.Prob;2034 for (unsigned j = 0, ej = BTB.Cases.size(); j != ej; ++j) {2035 UnhandledProb -= BTB.Cases[j].ExtraProb;2036 // Set the current basic block to the mbb we wish to insert the code into2037 FuncInfo->MBB = BTB.Cases[j].ThisBB;2038 FuncInfo->InsertPt = FuncInfo->MBB->end();2039 // Emit the code2040 2041 // If all cases cover a contiguous range, it is not necessary to jump to2042 // the default block after the last bit test fails. This is because the2043 // range check during bit test header creation has guaranteed that every2044 // case here doesn't go outside the range. In this case, there is no need2045 // to perform the last bit test, as it will always be true. Instead, make2046 // the second-to-last bit-test fall through to the target of the last bit2047 // test, and delete the last bit test.2048 2049 MachineBasicBlock *NextMBB;2050 if ((BTB.ContiguousRange || BTB.FallthroughUnreachable) && j + 2 == ej) {2051 // Second-to-last bit-test with contiguous range or omitted range2052 // check: fall through to the target of the final bit test.2053 NextMBB = BTB.Cases[j + 1].TargetBB;2054 } else if (j + 1 == ej) {2055 // For the last bit test, fall through to Default.2056 NextMBB = BTB.Default;2057 } else {2058 // Otherwise, fall through to the next bit test.2059 NextMBB = BTB.Cases[j + 1].ThisBB;2060 }2061 2062 SDB->visitBitTestCase(BTB, NextMBB, UnhandledProb, BTB.Reg, BTB.Cases[j],2063 FuncInfo->MBB);2064 2065 CurDAG->setRoot(SDB->getRoot());2066 SDB->clear();2067 CodeGenAndEmitDAG();2068 2069 if ((BTB.ContiguousRange || BTB.FallthroughUnreachable) && j + 2 == ej) {2070 // Since we're not going to use the final bit test, remove it.2071 BTB.Cases.pop_back();2072 break;2073 }2074 }2075 2076 // Update PHI Nodes2077 for (const std::pair<MachineInstr *, Register> &P :2078 FuncInfo->PHINodesToUpdate) {2079 MachineInstrBuilder PHI(*MF, P.first);2080 MachineBasicBlock *PHIBB = PHI->getParent();2081 assert(PHI->isPHI() &&2082 "This is not a machine PHI node that we are updating!");2083 // This is "default" BB. We have two jumps to it. From "header" BB and2084 // from last "case" BB, unless the latter was skipped.2085 if (PHIBB == BTB.Default) {2086 PHI.addReg(P.second).addMBB(BTB.Parent);2087 if (!BTB.ContiguousRange) {2088 PHI.addReg(P.second).addMBB(BTB.Cases.back().ThisBB);2089 }2090 }2091 // One of "cases" BB.2092 for (const SwitchCG::BitTestCase &BT : BTB.Cases) {2093 MachineBasicBlock* cBB = BT.ThisBB;2094 if (cBB->isSuccessor(PHIBB))2095 PHI.addReg(P.second).addMBB(cBB);2096 }2097 }2098 }2099 SDB->SL->BitTestCases.clear();2100 2101 // If the JumpTable record is filled in, then we need to emit a jump table.2102 // Updating the PHI nodes is tricky in this case, since we need to determine2103 // whether the PHI is a successor of the range check MBB or the jump table MBB2104 for (unsigned i = 0, e = SDB->SL->JTCases.size(); i != e; ++i) {2105 // Lower header first, if it wasn't already lowered2106 if (!SDB->SL->JTCases[i].first.Emitted) {2107 // Set the current basic block to the mbb we wish to insert the code into2108 FuncInfo->MBB = SDB->SL->JTCases[i].first.HeaderBB;2109 FuncInfo->InsertPt = FuncInfo->MBB->end();2110 // Emit the code2111 SDB->visitJumpTableHeader(SDB->SL->JTCases[i].second,2112 SDB->SL->JTCases[i].first, FuncInfo->MBB);2113 CurDAG->setRoot(SDB->getRoot());2114 SDB->clear();2115 CodeGenAndEmitDAG();2116 }2117 2118 // Set the current basic block to the mbb we wish to insert the code into2119 FuncInfo->MBB = SDB->SL->JTCases[i].second.MBB;2120 FuncInfo->InsertPt = FuncInfo->MBB->end();2121 // Emit the code2122 SDB->visitJumpTable(SDB->SL->JTCases[i].second);2123 CurDAG->setRoot(SDB->getRoot());2124 SDB->clear();2125 CodeGenAndEmitDAG();2126 2127 // Update PHI Nodes2128 for (unsigned pi = 0, pe = FuncInfo->PHINodesToUpdate.size();2129 pi != pe; ++pi) {2130 MachineInstrBuilder PHI(*MF, FuncInfo->PHINodesToUpdate[pi].first);2131 MachineBasicBlock *PHIBB = PHI->getParent();2132 assert(PHI->isPHI() &&2133 "This is not a machine PHI node that we are updating!");2134 // "default" BB. We can go there only from header BB.2135 if (PHIBB == SDB->SL->JTCases[i].second.Default)2136 PHI.addReg(FuncInfo->PHINodesToUpdate[pi].second)2137 .addMBB(SDB->SL->JTCases[i].first.HeaderBB);2138 // JT BB. Just iterate over successors here2139 if (FuncInfo->MBB->isSuccessor(PHIBB))2140 PHI.addReg(FuncInfo->PHINodesToUpdate[pi].second).addMBB(FuncInfo->MBB);2141 }2142 }2143 SDB->SL->JTCases.clear();2144 2145 // If we generated any switch lowering information, build and codegen any2146 // additional DAGs necessary.2147 for (unsigned i = 0, e = SDB->SL->SwitchCases.size(); i != e; ++i) {2148 // Set the current basic block to the mbb we wish to insert the code into2149 FuncInfo->MBB = SDB->SL->SwitchCases[i].ThisBB;2150 FuncInfo->InsertPt = FuncInfo->MBB->end();2151 2152 // Determine the unique successors.2153 SmallVector<MachineBasicBlock *, 2> Succs;2154 Succs.push_back(SDB->SL->SwitchCases[i].TrueBB);2155 if (SDB->SL->SwitchCases[i].TrueBB != SDB->SL->SwitchCases[i].FalseBB)2156 Succs.push_back(SDB->SL->SwitchCases[i].FalseBB);2157 2158 // Emit the code. Note that this could result in FuncInfo->MBB being split.2159 SDB->visitSwitchCase(SDB->SL->SwitchCases[i], FuncInfo->MBB);2160 CurDAG->setRoot(SDB->getRoot());2161 SDB->clear();2162 CodeGenAndEmitDAG();2163 2164 // Remember the last block, now that any splitting is done, for use in2165 // populating PHI nodes in successors.2166 MachineBasicBlock *ThisBB = FuncInfo->MBB;2167 2168 // Handle any PHI nodes in successors of this chunk, as if we were coming2169 // from the original BB before switch expansion. Note that PHI nodes can2170 // occur multiple times in PHINodesToUpdate. We have to be very careful to2171 // handle them the right number of times.2172 for (MachineBasicBlock *Succ : Succs) {2173 FuncInfo->MBB = Succ;2174 FuncInfo->InsertPt = FuncInfo->MBB->end();2175 // FuncInfo->MBB may have been removed from the CFG if a branch was2176 // constant folded.2177 if (ThisBB->isSuccessor(FuncInfo->MBB)) {2178 for (MachineBasicBlock::iterator2179 MBBI = FuncInfo->MBB->begin(), MBBE = FuncInfo->MBB->end();2180 MBBI != MBBE && MBBI->isPHI(); ++MBBI) {2181 MachineInstrBuilder PHI(*MF, MBBI);2182 // This value for this PHI node is recorded in PHINodesToUpdate.2183 for (unsigned pn = 0; ; ++pn) {2184 assert(pn != FuncInfo->PHINodesToUpdate.size() &&2185 "Didn't find PHI entry!");2186 if (FuncInfo->PHINodesToUpdate[pn].first == PHI) {2187 PHI.addReg(FuncInfo->PHINodesToUpdate[pn].second).addMBB(ThisBB);2188 break;2189 }2190 }2191 }2192 }2193 }2194 }2195 SDB->SL->SwitchCases.clear();2196}2197 2198/// Create the scheduler. If a specific scheduler was specified2199/// via the SchedulerRegistry, use it, otherwise select the2200/// one preferred by the target.2201///2202ScheduleDAGSDNodes *SelectionDAGISel::CreateScheduler() {2203 return ISHeuristic(this, OptLevel);2204}2205 2206//===----------------------------------------------------------------------===//2207// Helper functions used by the generated instruction selector.2208//===----------------------------------------------------------------------===//2209// Calls to these methods are generated by tblgen.2210 2211/// CheckAndMask - The isel is trying to match something like (and X, 255). If2212/// the dag combiner simplified the 255, we still want to match. RHS is the2213/// actual value in the DAG on the RHS of an AND, and DesiredMaskS is the value2214/// specified in the .td file (e.g. 255).2215bool SelectionDAGISel::CheckAndMask(SDValue LHS, ConstantSDNode *RHS,2216 int64_t DesiredMaskS) const {2217 const APInt &ActualMask = RHS->getAPIntValue();2218 // TODO: Avoid implicit trunc?2219 // See https://github.com/llvm/llvm-project/issues/112510.2220 const APInt &DesiredMask = APInt(LHS.getValueSizeInBits(), DesiredMaskS,2221 /*isSigned=*/false, /*implicitTrunc=*/true);2222 2223 // If the actual mask exactly matches, success!2224 if (ActualMask == DesiredMask)2225 return true;2226 2227 // If the actual AND mask is allowing unallowed bits, this doesn't match.2228 if (!ActualMask.isSubsetOf(DesiredMask))2229 return false;2230 2231 // Otherwise, the DAG Combiner may have proven that the value coming in is2232 // either already zero or is not demanded. Check for known zero input bits.2233 APInt NeededMask = DesiredMask & ~ActualMask;2234 if (CurDAG->MaskedValueIsZero(LHS, NeededMask))2235 return true;2236 2237 // TODO: check to see if missing bits are just not demanded.2238 2239 // Otherwise, this pattern doesn't match.2240 return false;2241}2242 2243/// CheckOrMask - The isel is trying to match something like (or X, 255). If2244/// the dag combiner simplified the 255, we still want to match. RHS is the2245/// actual value in the DAG on the RHS of an OR, and DesiredMaskS is the value2246/// specified in the .td file (e.g. 255).2247bool SelectionDAGISel::CheckOrMask(SDValue LHS, ConstantSDNode *RHS,2248 int64_t DesiredMaskS) const {2249 const APInt &ActualMask = RHS->getAPIntValue();2250 // TODO: Avoid implicit trunc?2251 // See https://github.com/llvm/llvm-project/issues/112510.2252 const APInt &DesiredMask = APInt(LHS.getValueSizeInBits(), DesiredMaskS,2253 /*isSigned=*/false, /*implicitTrunc=*/true);2254 2255 // If the actual mask exactly matches, success!2256 if (ActualMask == DesiredMask)2257 return true;2258 2259 // If the actual AND mask is allowing unallowed bits, this doesn't match.2260 if (!ActualMask.isSubsetOf(DesiredMask))2261 return false;2262 2263 // Otherwise, the DAG Combiner may have proven that the value coming in is2264 // either already zero or is not demanded. Check for known zero input bits.2265 APInt NeededMask = DesiredMask & ~ActualMask;2266 KnownBits Known = CurDAG->computeKnownBits(LHS);2267 2268 // If all the missing bits in the or are already known to be set, match!2269 if (NeededMask.isSubsetOf(Known.One))2270 return true;2271 2272 // TODO: check to see if missing bits are just not demanded.2273 2274 // Otherwise, this pattern doesn't match.2275 return false;2276}2277 2278/// SelectInlineAsmMemoryOperands - Calls to this are automatically generated2279/// by tblgen. Others should not call it.2280void SelectionDAGISel::SelectInlineAsmMemoryOperands(std::vector<SDValue> &Ops,2281 const SDLoc &DL) {2282 // Change the vector of SDValue into a list of SDNodeHandle for x86 might call2283 // replaceAllUses when matching address.2284 2285 std::list<HandleSDNode> Handles;2286 2287 Handles.emplace_back(Ops[InlineAsm::Op_InputChain]); // 02288 Handles.emplace_back(Ops[InlineAsm::Op_AsmString]); // 12289 Handles.emplace_back(Ops[InlineAsm::Op_MDNode]); // 2, !srcloc2290 Handles.emplace_back(2291 Ops[InlineAsm::Op_ExtraInfo]); // 3 (SideEffect, AlignStack)2292 2293 unsigned i = InlineAsm::Op_FirstOperand, e = Ops.size();2294 if (Ops[e - 1].getValueType() == MVT::Glue)2295 --e; // Don't process a glue operand if it is here.2296 2297 while (i != e) {2298 InlineAsm::Flag Flags(Ops[i]->getAsZExtVal());2299 if (!Flags.isMemKind() && !Flags.isFuncKind()) {2300 // Just skip over this operand, copying the operands verbatim.2301 Handles.insert(Handles.end(), Ops.begin() + i,2302 Ops.begin() + i + Flags.getNumOperandRegisters() + 1);2303 i += Flags.getNumOperandRegisters() + 1;2304 } else {2305 assert(Flags.getNumOperandRegisters() == 1 &&2306 "Memory operand with multiple values?");2307 2308 unsigned TiedToOperand;2309 if (Flags.isUseOperandTiedToDef(TiedToOperand)) {2310 // We need the constraint ID from the operand this is tied to.2311 unsigned CurOp = InlineAsm::Op_FirstOperand;2312 Flags = InlineAsm::Flag(Ops[CurOp]->getAsZExtVal());2313 for (; TiedToOperand; --TiedToOperand) {2314 CurOp += Flags.getNumOperandRegisters() + 1;2315 Flags = InlineAsm::Flag(Ops[CurOp]->getAsZExtVal());2316 }2317 }2318 2319 // Otherwise, this is a memory operand. Ask the target to select it.2320 std::vector<SDValue> SelOps;2321 const InlineAsm::ConstraintCode ConstraintID =2322 Flags.getMemoryConstraintID();2323 if (SelectInlineAsmMemoryOperand(Ops[i + 1], ConstraintID, SelOps))2324 report_fatal_error("Could not match memory address. Inline asm"2325 " failure!");2326 2327 // Add this to the output node.2328 Flags = InlineAsm::Flag(Flags.isMemKind() ? InlineAsm::Kind::Mem2329 : InlineAsm::Kind::Func,2330 SelOps.size());2331 Flags.setMemConstraint(ConstraintID);2332 Handles.emplace_back(CurDAG->getTargetConstant(Flags, DL, MVT::i32));2333 llvm::append_range(Handles, SelOps);2334 i += 2;2335 }2336 }2337 2338 // Add the glue input back if present.2339 if (e != Ops.size())2340 Handles.emplace_back(Ops.back());2341 2342 Ops.clear();2343 for (auto &handle : Handles)2344 Ops.push_back(handle.getValue());2345}2346 2347/// findNonImmUse - Return true if "Def" is a predecessor of "Root" via a path2348/// beyond "ImmedUse". We may ignore chains as they are checked separately.2349static bool findNonImmUse(SDNode *Root, SDNode *Def, SDNode *ImmedUse,2350 bool IgnoreChains) {2351 SmallPtrSet<const SDNode *, 16> Visited;2352 SmallVector<const SDNode *, 16> WorkList;2353 // Only check if we have non-immediate uses of Def.2354 if (ImmedUse->isOnlyUserOf(Def))2355 return false;2356 2357 // We don't care about paths to Def that go through ImmedUse so mark it2358 // visited and mark non-def operands as used.2359 Visited.insert(ImmedUse);2360 for (const SDValue &Op : ImmedUse->op_values()) {2361 SDNode *N = Op.getNode();2362 // Ignore chain deps (they are validated by2363 // HandleMergeInputChains) and immediate uses2364 if ((Op.getValueType() == MVT::Other && IgnoreChains) || N == Def)2365 continue;2366 if (!Visited.insert(N).second)2367 continue;2368 WorkList.push_back(N);2369 }2370 2371 // Initialize worklist to operands of Root.2372 if (Root != ImmedUse) {2373 for (const SDValue &Op : Root->op_values()) {2374 SDNode *N = Op.getNode();2375 // Ignore chains (they are validated by HandleMergeInputChains)2376 if ((Op.getValueType() == MVT::Other && IgnoreChains) || N == Def)2377 continue;2378 if (!Visited.insert(N).second)2379 continue;2380 WorkList.push_back(N);2381 }2382 }2383 2384 return SDNode::hasPredecessorHelper(Def, Visited, WorkList, 0, true);2385}2386 2387/// IsProfitableToFold - Returns true if it's profitable to fold the specific2388/// operand node N of U during instruction selection that starts at Root.2389bool SelectionDAGISel::IsProfitableToFold(SDValue N, SDNode *U,2390 SDNode *Root) const {2391 if (OptLevel == CodeGenOptLevel::None)2392 return false;2393 return N.hasOneUse();2394}2395 2396/// IsLegalToFold - Returns true if the specific operand node N of2397/// U can be folded during instruction selection that starts at Root.2398bool SelectionDAGISel::IsLegalToFold(SDValue N, SDNode *U, SDNode *Root,2399 CodeGenOptLevel OptLevel,2400 bool IgnoreChains) {2401 if (OptLevel == CodeGenOptLevel::None)2402 return false;2403 2404 // If Root use can somehow reach N through a path that doesn't contain2405 // U then folding N would create a cycle. e.g. In the following2406 // diagram, Root can reach N through X. If N is folded into Root, then2407 // X is both a predecessor and a successor of U.2408 //2409 // [N*] //2410 // ^ ^ //2411 // / \ //2412 // [U*] [X]? //2413 // ^ ^ //2414 // \ / //2415 // \ / //2416 // [Root*] //2417 //2418 // * indicates nodes to be folded together.2419 //2420 // If Root produces glue, then it gets (even more) interesting. Since it2421 // will be "glued" together with its glue use in the scheduler, we need to2422 // check if it might reach N.2423 //2424 // [N*] //2425 // ^ ^ //2426 // / \ //2427 // [U*] [X]? //2428 // ^ ^ //2429 // \ \ //2430 // \ | //2431 // [Root*] | //2432 // ^ | //2433 // f | //2434 // | / //2435 // [Y] / //2436 // ^ / //2437 // f / //2438 // | / //2439 // [GU] //2440 //2441 // If GU (glue use) indirectly reaches N (the load), and Root folds N2442 // (call it Fold), then X is a predecessor of GU and a successor of2443 // Fold. But since Fold and GU are glued together, this will create2444 // a cycle in the scheduling graph.2445 2446 // If the node has glue, walk down the graph to the "lowest" node in the2447 // glued set.2448 EVT VT = Root->getValueType(Root->getNumValues()-1);2449 while (VT == MVT::Glue) {2450 SDNode *GU = Root->getGluedUser();2451 if (!GU)2452 break;2453 Root = GU;2454 VT = Root->getValueType(Root->getNumValues()-1);2455 2456 // If our query node has a glue result with a use, we've walked up it. If2457 // the user (which has already been selected) has a chain or indirectly uses2458 // the chain, HandleMergeInputChains will not consider it. Because of2459 // this, we cannot ignore chains in this predicate.2460 IgnoreChains = false;2461 }2462 2463 return !findNonImmUse(Root, N.getNode(), U, IgnoreChains);2464}2465 2466void SelectionDAGISel::Select_INLINEASM(SDNode *N) {2467 SDLoc DL(N);2468 2469 std::vector<SDValue> Ops(N->op_begin(), N->op_end());2470 SelectInlineAsmMemoryOperands(Ops, DL);2471 2472 const EVT VTs[] = {MVT::Other, MVT::Glue};2473 SDValue New = CurDAG->getNode(N->getOpcode(), DL, VTs, Ops);2474 New->setNodeId(-1);2475 ReplaceUses(N, New.getNode());2476 CurDAG->RemoveDeadNode(N);2477}2478 2479void SelectionDAGISel::Select_READ_REGISTER(SDNode *Op) {2480 SDLoc dl(Op);2481 MDNodeSDNode *MD = cast<MDNodeSDNode>(Op->getOperand(1));2482 const MDString *RegStr = cast<MDString>(MD->getMD()->getOperand(0));2483 2484 EVT VT = Op->getValueType(0);2485 LLT Ty = VT.isSimple() ? getLLTForMVT(VT.getSimpleVT()) : LLT();2486 2487 const MachineFunction &MF = CurDAG->getMachineFunction();2488 Register Reg = TLI->getRegisterByName(RegStr->getString().data(), Ty, MF);2489 2490 SDValue New;2491 if (!Reg) {2492 const Function &Fn = MF.getFunction();2493 Fn.getContext().diagnose(DiagnosticInfoGenericWithLoc(2494 "invalid register \"" + Twine(RegStr->getString().data()) +2495 "\" for llvm.read_register",2496 Fn, Op->getDebugLoc()));2497 New =2498 SDValue(CurDAG->getMachineNode(TargetOpcode::IMPLICIT_DEF, dl, VT), 0);2499 ReplaceUses(SDValue(Op, 1), Op->getOperand(0));2500 } else {2501 New =2502 CurDAG->getCopyFromReg(Op->getOperand(0), dl, Reg, Op->getValueType(0));2503 }2504 2505 New->setNodeId(-1);2506 ReplaceUses(Op, New.getNode());2507 CurDAG->RemoveDeadNode(Op);2508}2509 2510void SelectionDAGISel::Select_WRITE_REGISTER(SDNode *Op) {2511 SDLoc dl(Op);2512 MDNodeSDNode *MD = cast<MDNodeSDNode>(Op->getOperand(1));2513 const MDString *RegStr = cast<MDString>(MD->getMD()->getOperand(0));2514 2515 EVT VT = Op->getOperand(2).getValueType();2516 LLT Ty = VT.isSimple() ? getLLTForMVT(VT.getSimpleVT()) : LLT();2517 2518 const MachineFunction &MF = CurDAG->getMachineFunction();2519 Register Reg = TLI->getRegisterByName(RegStr->getString().data(), Ty, MF);2520 2521 if (!Reg) {2522 const Function &Fn = MF.getFunction();2523 Fn.getContext().diagnose(DiagnosticInfoGenericWithLoc(2524 "invalid register \"" + Twine(RegStr->getString().data()) +2525 "\" for llvm.write_register",2526 Fn, Op->getDebugLoc()));2527 ReplaceUses(SDValue(Op, 0), Op->getOperand(0));2528 } else {2529 SDValue New =2530 CurDAG->getCopyToReg(Op->getOperand(0), dl, Reg, Op->getOperand(2));2531 New->setNodeId(-1);2532 ReplaceUses(Op, New.getNode());2533 }2534 2535 CurDAG->RemoveDeadNode(Op);2536}2537 2538void SelectionDAGISel::Select_UNDEF(SDNode *N) {2539 CurDAG->SelectNodeTo(N, TargetOpcode::IMPLICIT_DEF, N->getValueType(0));2540}2541 2542// Use the generic target FAKE_USE target opcode. The chain operand2543// must come last, because InstrEmitter::AddOperand() requires it.2544void SelectionDAGISel::Select_FAKE_USE(SDNode *N) {2545 CurDAG->SelectNodeTo(N, TargetOpcode::FAKE_USE, N->getValueType(0),2546 N->getOperand(1), N->getOperand(0));2547}2548 2549void SelectionDAGISel::Select_RELOC_NONE(SDNode *N) {2550 CurDAG->SelectNodeTo(N, TargetOpcode::RELOC_NONE, N->getValueType(0),2551 N->getOperand(1), N->getOperand(0));2552}2553 2554void SelectionDAGISel::Select_FREEZE(SDNode *N) {2555 // TODO: We don't have FREEZE pseudo-instruction in MachineInstr-level now.2556 // If FREEZE instruction is added later, the code below must be changed as2557 // well.2558 CurDAG->SelectNodeTo(N, TargetOpcode::COPY, N->getValueType(0),2559 N->getOperand(0));2560}2561 2562void SelectionDAGISel::Select_ARITH_FENCE(SDNode *N) {2563 CurDAG->SelectNodeTo(N, TargetOpcode::ARITH_FENCE, N->getValueType(0),2564 N->getOperand(0));2565}2566 2567void SelectionDAGISel::Select_MEMBARRIER(SDNode *N) {2568 CurDAG->SelectNodeTo(N, TargetOpcode::MEMBARRIER, N->getValueType(0),2569 N->getOperand(0));2570}2571 2572void SelectionDAGISel::Select_CONVERGENCECTRL_ANCHOR(SDNode *N) {2573 CurDAG->SelectNodeTo(N, TargetOpcode::CONVERGENCECTRL_ANCHOR,2574 N->getValueType(0));2575}2576 2577void SelectionDAGISel::Select_CONVERGENCECTRL_ENTRY(SDNode *N) {2578 CurDAG->SelectNodeTo(N, TargetOpcode::CONVERGENCECTRL_ENTRY,2579 N->getValueType(0));2580}2581 2582void SelectionDAGISel::Select_CONVERGENCECTRL_LOOP(SDNode *N) {2583 CurDAG->SelectNodeTo(N, TargetOpcode::CONVERGENCECTRL_LOOP,2584 N->getValueType(0), N->getOperand(0));2585}2586 2587void SelectionDAGISel::pushStackMapLiveVariable(SmallVectorImpl<SDValue> &Ops,2588 SDValue OpVal, SDLoc DL) {2589 SDNode *OpNode = OpVal.getNode();2590 2591 // FrameIndex nodes should have been directly emitted to TargetFrameIndex2592 // nodes at DAG-construction time.2593 assert(OpNode->getOpcode() != ISD::FrameIndex);2594 2595 if (OpNode->getOpcode() == ISD::Constant) {2596 Ops.push_back(2597 CurDAG->getTargetConstant(StackMaps::ConstantOp, DL, MVT::i64));2598 Ops.push_back(CurDAG->getTargetConstant(OpNode->getAsZExtVal(), DL,2599 OpVal.getValueType()));2600 } else {2601 Ops.push_back(OpVal);2602 }2603}2604 2605void SelectionDAGISel::Select_STACKMAP(SDNode *N) {2606 SmallVector<SDValue, 32> Ops;2607 auto *It = N->op_begin();2608 SDLoc DL(N);2609 2610 // Stash the chain and glue operands so we can move them to the end.2611 SDValue Chain = *It++;2612 SDValue InGlue = *It++;2613 2614 // <id> operand.2615 SDValue ID = *It++;2616 assert(ID.getValueType() == MVT::i64);2617 Ops.push_back(ID);2618 2619 // <numShadowBytes> operand.2620 SDValue Shad = *It++;2621 assert(Shad.getValueType() == MVT::i32);2622 Ops.push_back(Shad);2623 2624 // Live variable operands.2625 for (; It != N->op_end(); It++)2626 pushStackMapLiveVariable(Ops, *It, DL);2627 2628 Ops.push_back(Chain);2629 Ops.push_back(InGlue);2630 2631 SDVTList NodeTys = CurDAG->getVTList(MVT::Other, MVT::Glue);2632 CurDAG->SelectNodeTo(N, TargetOpcode::STACKMAP, NodeTys, Ops);2633}2634 2635void SelectionDAGISel::Select_PATCHPOINT(SDNode *N) {2636 SmallVector<SDValue, 32> Ops;2637 auto *It = N->op_begin();2638 SDLoc DL(N);2639 2640 // Cache arguments that will be moved to the end in the target node.2641 SDValue Chain = *It++;2642 std::optional<SDValue> Glue;2643 if (It->getValueType() == MVT::Glue)2644 Glue = *It++;2645 SDValue RegMask = *It++;2646 2647 // <id> operand.2648 SDValue ID = *It++;2649 assert(ID.getValueType() == MVT::i64);2650 Ops.push_back(ID);2651 2652 // <numShadowBytes> operand.2653 SDValue Shad = *It++;2654 assert(Shad.getValueType() == MVT::i32);2655 Ops.push_back(Shad);2656 2657 // Add the callee.2658 Ops.push_back(*It++);2659 2660 // Add <numArgs>.2661 SDValue NumArgs = *It++;2662 assert(NumArgs.getValueType() == MVT::i32);2663 Ops.push_back(NumArgs);2664 2665 // Calling convention.2666 Ops.push_back(*It++);2667 2668 // Push the args for the call.2669 for (uint64_t I = NumArgs->getAsZExtVal(); I != 0; I--)2670 Ops.push_back(*It++);2671 2672 // Now push the live variables.2673 for (; It != N->op_end(); It++)2674 pushStackMapLiveVariable(Ops, *It, DL);2675 2676 // Finally, the regmask, chain and (if present) glue are moved to the end.2677 Ops.push_back(RegMask);2678 Ops.push_back(Chain);2679 if (Glue.has_value())2680 Ops.push_back(*Glue);2681 2682 SDVTList NodeTys = N->getVTList();2683 CurDAG->SelectNodeTo(N, TargetOpcode::PATCHPOINT, NodeTys, Ops);2684}2685 2686/// GetVBR - decode a vbr encoding whose top bit is set.2687LLVM_ATTRIBUTE_ALWAYS_INLINE static uint64_t2688GetVBR(uint64_t Val, const unsigned char *MatcherTable, unsigned &Idx) {2689 assert(Val >= 128 && "Not a VBR");2690 Val &= 127; // Remove first vbr bit.2691 2692 unsigned Shift = 7;2693 uint64_t NextBits;2694 do {2695 NextBits = MatcherTable[Idx++];2696 Val |= (NextBits&127) << Shift;2697 Shift += 7;2698 } while (NextBits & 128);2699 2700 return Val;2701}2702 2703/// getSimpleVT - Decode a value in MatcherTable, if it's a VBR encoded value,2704/// use GetVBR to decode it.2705LLVM_ATTRIBUTE_ALWAYS_INLINE static MVT::SimpleValueType2706getSimpleVT(const unsigned char *MatcherTable, unsigned &MatcherIndex) {2707 unsigned SimpleVT = MatcherTable[MatcherIndex++];2708 if (SimpleVT & 128)2709 SimpleVT = GetVBR(SimpleVT, MatcherTable, MatcherIndex);2710 2711 return static_cast<MVT::SimpleValueType>(SimpleVT);2712}2713 2714void SelectionDAGISel::Select_JUMP_TABLE_DEBUG_INFO(SDNode *N) {2715 SDLoc dl(N);2716 CurDAG->SelectNodeTo(N, TargetOpcode::JUMP_TABLE_DEBUG_INFO, MVT::Glue,2717 CurDAG->getTargetConstant(N->getConstantOperandVal(1),2718 dl, MVT::i64, true));2719}2720 2721/// When a match is complete, this method updates uses of interior chain results2722/// to use the new results.2723void SelectionDAGISel::UpdateChains(2724 SDNode *NodeToMatch, SDValue InputChain,2725 SmallVectorImpl<SDNode *> &ChainNodesMatched, bool isMorphNodeTo) {2726 SmallVector<SDNode*, 4> NowDeadNodes;2727 2728 // Now that all the normal results are replaced, we replace the chain and2729 // glue results if present.2730 if (!ChainNodesMatched.empty()) {2731 assert(InputChain.getNode() &&2732 "Matched input chains but didn't produce a chain");2733 // Loop over all of the nodes we matched that produced a chain result.2734 // Replace all the chain results with the final chain we ended up with.2735 for (unsigned i = 0, e = ChainNodesMatched.size(); i != e; ++i) {2736 SDNode *ChainNode = ChainNodesMatched[i];2737 // If ChainNode is null, it's because we replaced it on a previous2738 // iteration and we cleared it out of the map. Just skip it.2739 if (!ChainNode)2740 continue;2741 2742 assert(ChainNode->getOpcode() != ISD::DELETED_NODE &&2743 "Deleted node left in chain");2744 2745 // Don't replace the results of the root node if we're doing a2746 // MorphNodeTo.2747 if (ChainNode == NodeToMatch && isMorphNodeTo)2748 continue;2749 2750 SDValue ChainVal = SDValue(ChainNode, ChainNode->getNumValues()-1);2751 if (ChainVal.getValueType() == MVT::Glue)2752 ChainVal = ChainVal.getValue(ChainVal->getNumValues()-2);2753 assert(ChainVal.getValueType() == MVT::Other && "Not a chain?");2754 SelectionDAG::DAGNodeDeletedListener NDL(2755 *CurDAG, [&](SDNode *N, SDNode *E) {2756 llvm::replace(ChainNodesMatched, N, static_cast<SDNode *>(nullptr));2757 });2758 if (ChainNode->getOpcode() != ISD::TokenFactor)2759 ReplaceUses(ChainVal, InputChain);2760 2761 // If the node became dead and we haven't already seen it, delete it.2762 if (ChainNode != NodeToMatch && ChainNode->use_empty() &&2763 !llvm::is_contained(NowDeadNodes, ChainNode))2764 NowDeadNodes.push_back(ChainNode);2765 }2766 }2767 2768 if (!NowDeadNodes.empty())2769 CurDAG->RemoveDeadNodes(NowDeadNodes);2770 2771 LLVM_DEBUG(dbgs() << "ISEL: Match complete!\n");2772}2773 2774/// HandleMergeInputChains - This implements the OPC_EmitMergeInputChains2775/// operation for when the pattern matched at least one node with a chains. The2776/// input vector contains a list of all of the chained nodes that we match. We2777/// must determine if this is a valid thing to cover (i.e. matching it won't2778/// induce cycles in the DAG) and if so, creating a TokenFactor node. that will2779/// be used as the input node chain for the generated nodes.2780static SDValue2781HandleMergeInputChains(const SmallVectorImpl<SDNode *> &ChainNodesMatched,2782 SDValue InputGlue, SelectionDAG *CurDAG) {2783 2784 SmallPtrSet<const SDNode *, 16> Visited;2785 SmallVector<const SDNode *, 8> Worklist;2786 SmallVector<SDValue, 3> InputChains;2787 unsigned int Max = 8192;2788 2789 // Quick exit on trivial merge.2790 if (ChainNodesMatched.size() == 1)2791 return ChainNodesMatched[0]->getOperand(0);2792 2793 // Add chains that aren't already added (internal). Peek through2794 // token factors.2795 std::function<void(const SDValue)> AddChains = [&](const SDValue V) {2796 if (V.getValueType() != MVT::Other)2797 return;2798 if (V->getOpcode() == ISD::EntryToken)2799 return;2800 if (!Visited.insert(V.getNode()).second)2801 return;2802 if (V->getOpcode() == ISD::TokenFactor) {2803 for (const SDValue &Op : V->op_values())2804 AddChains(Op);2805 } else2806 InputChains.push_back(V);2807 };2808 2809 for (auto *N : ChainNodesMatched) {2810 Worklist.push_back(N);2811 Visited.insert(N);2812 }2813 2814 while (!Worklist.empty())2815 AddChains(Worklist.pop_back_val()->getOperand(0));2816 2817 // Skip the search if there are no chain dependencies.2818 if (InputChains.size() == 0)2819 return CurDAG->getEntryNode();2820 2821 // If one of these chains is a successor of input, we must have a2822 // node that is both the predecessor and successor of the2823 // to-be-merged nodes. Fail.2824 Visited.clear();2825 for (SDValue V : InputChains) {2826 // If we need to create a TokenFactor, and any of the input chain nodes will2827 // also be glued to the output, we cannot merge the chains. The TokenFactor2828 // would prevent the glue from being honored.2829 if (InputChains.size() != 1 &&2830 V->getValueType(V->getNumValues() - 1) == MVT::Glue &&2831 InputGlue.getNode() == V.getNode())2832 return SDValue();2833 Worklist.push_back(V.getNode());2834 }2835 2836 for (auto *N : ChainNodesMatched)2837 if (SDNode::hasPredecessorHelper(N, Visited, Worklist, Max, true))2838 return SDValue();2839 2840 // Return merged chain.2841 if (InputChains.size() == 1)2842 return InputChains[0];2843 return CurDAG->getNode(ISD::TokenFactor, SDLoc(ChainNodesMatched[0]),2844 MVT::Other, InputChains);2845}2846 2847/// MorphNode - Handle morphing a node in place for the selector.2848SDNode *SelectionDAGISel::2849MorphNode(SDNode *Node, unsigned TargetOpc, SDVTList VTList,2850 ArrayRef<SDValue> Ops, unsigned EmitNodeInfo) {2851 // It is possible we're using MorphNodeTo to replace a node with no2852 // normal results with one that has a normal result (or we could be2853 // adding a chain) and the input could have glue and chains as well.2854 // In this case we need to shift the operands down.2855 // FIXME: This is a horrible hack and broken in obscure cases, no worse2856 // than the old isel though.2857 int OldGlueResultNo = -1, OldChainResultNo = -1;2858 2859 unsigned NTMNumResults = Node->getNumValues();2860 if (Node->getValueType(NTMNumResults-1) == MVT::Glue) {2861 OldGlueResultNo = NTMNumResults-1;2862 if (NTMNumResults != 1 &&2863 Node->getValueType(NTMNumResults-2) == MVT::Other)2864 OldChainResultNo = NTMNumResults-2;2865 } else if (Node->getValueType(NTMNumResults-1) == MVT::Other)2866 OldChainResultNo = NTMNumResults-1;2867 2868 // Call the underlying SelectionDAG routine to do the transmogrification. Note2869 // that this deletes operands of the old node that become dead.2870 SDNode *Res = CurDAG->MorphNodeTo(Node, ~TargetOpc, VTList, Ops);2871 2872 // MorphNodeTo can operate in two ways: if an existing node with the2873 // specified operands exists, it can just return it. Otherwise, it2874 // updates the node in place to have the requested operands.2875 if (Res == Node) {2876 // If we updated the node in place, reset the node ID. To the isel,2877 // this should be just like a newly allocated machine node.2878 Res->setNodeId(-1);2879 }2880 2881 unsigned ResNumResults = Res->getNumValues();2882 // Move the glue if needed.2883 if ((EmitNodeInfo & OPFL_GlueOutput) && OldGlueResultNo != -1 &&2884 static_cast<unsigned>(OldGlueResultNo) != ResNumResults - 1)2885 ReplaceUses(SDValue(Node, OldGlueResultNo),2886 SDValue(Res, ResNumResults - 1));2887 2888 if ((EmitNodeInfo & OPFL_GlueOutput) != 0)2889 --ResNumResults;2890 2891 // Move the chain reference if needed.2892 if ((EmitNodeInfo & OPFL_Chain) && OldChainResultNo != -1 &&2893 static_cast<unsigned>(OldChainResultNo) != ResNumResults - 1)2894 ReplaceUses(SDValue(Node, OldChainResultNo),2895 SDValue(Res, ResNumResults - 1));2896 2897 // Otherwise, no replacement happened because the node already exists. Replace2898 // Uses of the old node with the new one.2899 if (Res != Node) {2900 ReplaceNode(Node, Res);2901 } else {2902 EnforceNodeIdInvariant(Res);2903 }2904 2905 return Res;2906}2907 2908/// CheckSame - Implements OP_CheckSame.2909LLVM_ATTRIBUTE_ALWAYS_INLINE static bool2910CheckSame(const unsigned char *MatcherTable, unsigned &MatcherIndex, SDValue N,2911 const SmallVectorImpl<std::pair<SDValue, SDNode *>> &RecordedNodes) {2912 // Accept if it is exactly the same as a previously recorded node.2913 unsigned RecNo = MatcherTable[MatcherIndex++];2914 assert(RecNo < RecordedNodes.size() && "Invalid CheckSame");2915 return N == RecordedNodes[RecNo].first;2916}2917 2918/// CheckChildSame - Implements OP_CheckChildXSame.2919LLVM_ATTRIBUTE_ALWAYS_INLINE static bool CheckChildSame(2920 const unsigned char *MatcherTable, unsigned &MatcherIndex, SDValue N,2921 const SmallVectorImpl<std::pair<SDValue, SDNode *>> &RecordedNodes,2922 unsigned ChildNo) {2923 if (ChildNo >= N.getNumOperands())2924 return false; // Match fails if out of range child #.2925 return ::CheckSame(MatcherTable, MatcherIndex, N.getOperand(ChildNo),2926 RecordedNodes);2927}2928 2929/// CheckPatternPredicate - Implements OP_CheckPatternPredicate.2930LLVM_ATTRIBUTE_ALWAYS_INLINE static bool2931CheckPatternPredicate(unsigned Opcode, const unsigned char *MatcherTable,2932 unsigned &MatcherIndex, const SelectionDAGISel &SDISel) {2933 bool TwoBytePredNo =2934 Opcode == SelectionDAGISel::OPC_CheckPatternPredicateTwoByte;2935 unsigned PredNo =2936 TwoBytePredNo || Opcode == SelectionDAGISel::OPC_CheckPatternPredicate2937 ? MatcherTable[MatcherIndex++]2938 : Opcode - SelectionDAGISel::OPC_CheckPatternPredicate0;2939 if (TwoBytePredNo)2940 PredNo |= MatcherTable[MatcherIndex++] << 8;2941 return SDISel.CheckPatternPredicate(PredNo);2942}2943 2944/// CheckNodePredicate - Implements OP_CheckNodePredicate.2945LLVM_ATTRIBUTE_ALWAYS_INLINE static bool2946CheckNodePredicate(unsigned Opcode, const unsigned char *MatcherTable,2947 unsigned &MatcherIndex, const SelectionDAGISel &SDISel,2948 SDValue Op) {2949 unsigned PredNo = Opcode == SelectionDAGISel::OPC_CheckPredicate2950 ? MatcherTable[MatcherIndex++]2951 : Opcode - SelectionDAGISel::OPC_CheckPredicate0;2952 return SDISel.CheckNodePredicate(Op, PredNo);2953}2954 2955LLVM_ATTRIBUTE_ALWAYS_INLINE static bool2956CheckOpcode(const unsigned char *MatcherTable, unsigned &MatcherIndex,2957 SDNode *N) {2958 uint16_t Opc = MatcherTable[MatcherIndex++];2959 Opc |= static_cast<uint16_t>(MatcherTable[MatcherIndex++]) << 8;2960 return N->getOpcode() == Opc;2961}2962 2963LLVM_ATTRIBUTE_ALWAYS_INLINE static bool CheckType(MVT::SimpleValueType VT,2964 SDValue N,2965 const TargetLowering *TLI,2966 const DataLayout &DL) {2967 if (N.getValueType() == VT)2968 return true;2969 2970 // Handle the case when VT is iPTR.2971 return VT == MVT::iPTR && N.getValueType() == TLI->getPointerTy(DL);2972}2973 2974LLVM_ATTRIBUTE_ALWAYS_INLINE static bool2975CheckChildType(MVT::SimpleValueType VT, SDValue N, const TargetLowering *TLI,2976 const DataLayout &DL, unsigned ChildNo) {2977 if (ChildNo >= N.getNumOperands())2978 return false; // Match fails if out of range child #.2979 return ::CheckType(VT, N.getOperand(ChildNo), TLI, DL);2980}2981 2982LLVM_ATTRIBUTE_ALWAYS_INLINE static bool2983CheckCondCode(const unsigned char *MatcherTable, unsigned &MatcherIndex,2984 SDValue N) {2985 return cast<CondCodeSDNode>(N)->get() ==2986 static_cast<ISD::CondCode>(MatcherTable[MatcherIndex++]);2987}2988 2989LLVM_ATTRIBUTE_ALWAYS_INLINE static bool2990CheckChild2CondCode(const unsigned char *MatcherTable, unsigned &MatcherIndex,2991 SDValue N) {2992 if (2 >= N.getNumOperands())2993 return false;2994 return ::CheckCondCode(MatcherTable, MatcherIndex, N.getOperand(2));2995}2996 2997LLVM_ATTRIBUTE_ALWAYS_INLINE static bool2998CheckValueType(const unsigned char *MatcherTable, unsigned &MatcherIndex,2999 SDValue N, const TargetLowering *TLI, const DataLayout &DL) {3000 MVT::SimpleValueType VT = getSimpleVT(MatcherTable, MatcherIndex);3001 if (cast<VTSDNode>(N)->getVT() == VT)3002 return true;3003 3004 // Handle the case when VT is iPTR.3005 return VT == MVT::iPTR && cast<VTSDNode>(N)->getVT() == TLI->getPointerTy(DL);3006}3007 3008// Bit 0 stores the sign of the immediate. The upper bits contain the magnitude3009// shifted left by 1.3010static uint64_t decodeSignRotatedValue(uint64_t V) {3011 if ((V & 1) == 0)3012 return V >> 1;3013 if (V != 1)3014 return -(V >> 1);3015 // There is no such thing as -0 with integers. "-0" really means MININT.3016 return 1ULL << 63;3017}3018 3019LLVM_ATTRIBUTE_ALWAYS_INLINE static bool3020CheckInteger(const unsigned char *MatcherTable, unsigned &MatcherIndex,3021 SDValue N) {3022 int64_t Val = MatcherTable[MatcherIndex++];3023 if (Val & 128)3024 Val = GetVBR(Val, MatcherTable, MatcherIndex);3025 3026 Val = decodeSignRotatedValue(Val);3027 3028 ConstantSDNode *C = dyn_cast<ConstantSDNode>(N);3029 return C && C->getAPIntValue().trySExtValue() == Val;3030}3031 3032LLVM_ATTRIBUTE_ALWAYS_INLINE static bool3033CheckChildInteger(const unsigned char *MatcherTable, unsigned &MatcherIndex,3034 SDValue N, unsigned ChildNo) {3035 if (ChildNo >= N.getNumOperands())3036 return false; // Match fails if out of range child #.3037 return ::CheckInteger(MatcherTable, MatcherIndex, N.getOperand(ChildNo));3038}3039 3040LLVM_ATTRIBUTE_ALWAYS_INLINE static bool3041CheckAndImm(const unsigned char *MatcherTable, unsigned &MatcherIndex,3042 SDValue N, const SelectionDAGISel &SDISel) {3043 int64_t Val = MatcherTable[MatcherIndex++];3044 if (Val & 128)3045 Val = GetVBR(Val, MatcherTable, MatcherIndex);3046 3047 if (N->getOpcode() != ISD::AND) return false;3048 3049 ConstantSDNode *C = dyn_cast<ConstantSDNode>(N->getOperand(1));3050 return C && SDISel.CheckAndMask(N.getOperand(0), C, Val);3051}3052 3053LLVM_ATTRIBUTE_ALWAYS_INLINE static bool3054CheckOrImm(const unsigned char *MatcherTable, unsigned &MatcherIndex, SDValue N,3055 const SelectionDAGISel &SDISel) {3056 int64_t Val = MatcherTable[MatcherIndex++];3057 if (Val & 128)3058 Val = GetVBR(Val, MatcherTable, MatcherIndex);3059 3060 if (N->getOpcode() != ISD::OR) return false;3061 3062 ConstantSDNode *C = dyn_cast<ConstantSDNode>(N->getOperand(1));3063 return C && SDISel.CheckOrMask(N.getOperand(0), C, Val);3064}3065 3066/// IsPredicateKnownToFail - If we know how and can do so without pushing a3067/// scope, evaluate the current node. If the current predicate is known to3068/// fail, set Result=true and return anything. If the current predicate is3069/// known to pass, set Result=false and return the MatcherIndex to continue3070/// with. If the current predicate is unknown, set Result=false and return the3071/// MatcherIndex to continue with.3072static unsigned IsPredicateKnownToFail(const unsigned char *Table,3073 unsigned Index, SDValue N,3074 bool &Result,3075 const SelectionDAGISel &SDISel,3076 SmallVectorImpl<std::pair<SDValue, SDNode*>> &RecordedNodes) {3077 unsigned Opcode = Table[Index++];3078 switch (Opcode) {3079 default:3080 Result = false;3081 return Index-1; // Could not evaluate this predicate.3082 case SelectionDAGISel::OPC_CheckSame:3083 Result = !::CheckSame(Table, Index, N, RecordedNodes);3084 return Index;3085 case SelectionDAGISel::OPC_CheckChild0Same:3086 case SelectionDAGISel::OPC_CheckChild1Same:3087 case SelectionDAGISel::OPC_CheckChild2Same:3088 case SelectionDAGISel::OPC_CheckChild3Same:3089 Result = !::CheckChildSame(Table, Index, N, RecordedNodes,3090 Table[Index-1] - SelectionDAGISel::OPC_CheckChild0Same);3091 return Index;3092 case SelectionDAGISel::OPC_CheckPatternPredicate:3093 case SelectionDAGISel::OPC_CheckPatternPredicate0:3094 case SelectionDAGISel::OPC_CheckPatternPredicate1:3095 case SelectionDAGISel::OPC_CheckPatternPredicate2:3096 case SelectionDAGISel::OPC_CheckPatternPredicate3:3097 case SelectionDAGISel::OPC_CheckPatternPredicate4:3098 case SelectionDAGISel::OPC_CheckPatternPredicate5:3099 case SelectionDAGISel::OPC_CheckPatternPredicate6:3100 case SelectionDAGISel::OPC_CheckPatternPredicate7:3101 case SelectionDAGISel::OPC_CheckPatternPredicateTwoByte:3102 Result = !::CheckPatternPredicate(Opcode, Table, Index, SDISel);3103 return Index;3104 case SelectionDAGISel::OPC_CheckPredicate:3105 case SelectionDAGISel::OPC_CheckPredicate0:3106 case SelectionDAGISel::OPC_CheckPredicate1:3107 case SelectionDAGISel::OPC_CheckPredicate2:3108 case SelectionDAGISel::OPC_CheckPredicate3:3109 case SelectionDAGISel::OPC_CheckPredicate4:3110 case SelectionDAGISel::OPC_CheckPredicate5:3111 case SelectionDAGISel::OPC_CheckPredicate6:3112 case SelectionDAGISel::OPC_CheckPredicate7:3113 Result = !::CheckNodePredicate(Opcode, Table, Index, SDISel, N);3114 return Index;3115 case SelectionDAGISel::OPC_CheckOpcode:3116 Result = !::CheckOpcode(Table, Index, N.getNode());3117 return Index;3118 case SelectionDAGISel::OPC_CheckType:3119 case SelectionDAGISel::OPC_CheckTypeI32:3120 case SelectionDAGISel::OPC_CheckTypeI64: {3121 MVT::SimpleValueType VT;3122 switch (Opcode) {3123 case SelectionDAGISel::OPC_CheckTypeI32:3124 VT = MVT::i32;3125 break;3126 case SelectionDAGISel::OPC_CheckTypeI64:3127 VT = MVT::i64;3128 break;3129 default:3130 VT = getSimpleVT(Table, Index);3131 break;3132 }3133 Result = !::CheckType(VT, N, SDISel.TLI, SDISel.CurDAG->getDataLayout());3134 return Index;3135 }3136 case SelectionDAGISel::OPC_CheckTypeRes: {3137 unsigned Res = Table[Index++];3138 Result = !::CheckType(getSimpleVT(Table, Index), N.getValue(Res),3139 SDISel.TLI, SDISel.CurDAG->getDataLayout());3140 return Index;3141 }3142 case SelectionDAGISel::OPC_CheckChild0Type:3143 case SelectionDAGISel::OPC_CheckChild1Type:3144 case SelectionDAGISel::OPC_CheckChild2Type:3145 case SelectionDAGISel::OPC_CheckChild3Type:3146 case SelectionDAGISel::OPC_CheckChild4Type:3147 case SelectionDAGISel::OPC_CheckChild5Type:3148 case SelectionDAGISel::OPC_CheckChild6Type:3149 case SelectionDAGISel::OPC_CheckChild7Type:3150 case SelectionDAGISel::OPC_CheckChild0TypeI32:3151 case SelectionDAGISel::OPC_CheckChild1TypeI32:3152 case SelectionDAGISel::OPC_CheckChild2TypeI32:3153 case SelectionDAGISel::OPC_CheckChild3TypeI32:3154 case SelectionDAGISel::OPC_CheckChild4TypeI32:3155 case SelectionDAGISel::OPC_CheckChild5TypeI32:3156 case SelectionDAGISel::OPC_CheckChild6TypeI32:3157 case SelectionDAGISel::OPC_CheckChild7TypeI32:3158 case SelectionDAGISel::OPC_CheckChild0TypeI64:3159 case SelectionDAGISel::OPC_CheckChild1TypeI64:3160 case SelectionDAGISel::OPC_CheckChild2TypeI64:3161 case SelectionDAGISel::OPC_CheckChild3TypeI64:3162 case SelectionDAGISel::OPC_CheckChild4TypeI64:3163 case SelectionDAGISel::OPC_CheckChild5TypeI64:3164 case SelectionDAGISel::OPC_CheckChild6TypeI64:3165 case SelectionDAGISel::OPC_CheckChild7TypeI64: {3166 MVT::SimpleValueType VT;3167 unsigned ChildNo;3168 if (Opcode >= SelectionDAGISel::OPC_CheckChild0TypeI32 &&3169 Opcode <= SelectionDAGISel::OPC_CheckChild7TypeI32) {3170 VT = MVT::i32;3171 ChildNo = Opcode - SelectionDAGISel::OPC_CheckChild0TypeI32;3172 } else if (Opcode >= SelectionDAGISel::OPC_CheckChild0TypeI64 &&3173 Opcode <= SelectionDAGISel::OPC_CheckChild7TypeI64) {3174 VT = MVT::i64;3175 ChildNo = Opcode - SelectionDAGISel::OPC_CheckChild0TypeI64;3176 } else {3177 VT = getSimpleVT(Table, Index);3178 ChildNo = Opcode - SelectionDAGISel::OPC_CheckChild0Type;3179 }3180 Result = !::CheckChildType(VT, N, SDISel.TLI,3181 SDISel.CurDAG->getDataLayout(), ChildNo);3182 return Index;3183 }3184 case SelectionDAGISel::OPC_CheckCondCode:3185 Result = !::CheckCondCode(Table, Index, N);3186 return Index;3187 case SelectionDAGISel::OPC_CheckChild2CondCode:3188 Result = !::CheckChild2CondCode(Table, Index, N);3189 return Index;3190 case SelectionDAGISel::OPC_CheckValueType:3191 Result = !::CheckValueType(Table, Index, N, SDISel.TLI,3192 SDISel.CurDAG->getDataLayout());3193 return Index;3194 case SelectionDAGISel::OPC_CheckInteger:3195 Result = !::CheckInteger(Table, Index, N);3196 return Index;3197 case SelectionDAGISel::OPC_CheckChild0Integer:3198 case SelectionDAGISel::OPC_CheckChild1Integer:3199 case SelectionDAGISel::OPC_CheckChild2Integer:3200 case SelectionDAGISel::OPC_CheckChild3Integer:3201 case SelectionDAGISel::OPC_CheckChild4Integer:3202 Result = !::CheckChildInteger(Table, Index, N,3203 Table[Index-1] - SelectionDAGISel::OPC_CheckChild0Integer);3204 return Index;3205 case SelectionDAGISel::OPC_CheckAndImm:3206 Result = !::CheckAndImm(Table, Index, N, SDISel);3207 return Index;3208 case SelectionDAGISel::OPC_CheckOrImm:3209 Result = !::CheckOrImm(Table, Index, N, SDISel);3210 return Index;3211 }3212}3213 3214namespace {3215 3216struct MatchScope {3217 /// FailIndex - If this match fails, this is the index to continue with.3218 unsigned FailIndex;3219 3220 /// NodeStack - The node stack when the scope was formed.3221 SmallVector<SDValue, 4> NodeStack;3222 3223 /// NumRecordedNodes - The number of recorded nodes when the scope was formed.3224 unsigned NumRecordedNodes;3225 3226 /// NumMatchedMemRefs - The number of matched memref entries.3227 unsigned NumMatchedMemRefs;3228 3229 /// InputChain/InputGlue - The current chain/glue3230 SDValue InputChain, InputGlue;3231 3232 /// HasChainNodesMatched - True if the ChainNodesMatched list is non-empty.3233 bool HasChainNodesMatched;3234};3235 3236/// \A DAG update listener to keep the matching state3237/// (i.e. RecordedNodes and MatchScope) uptodate if the target is allowed to3238/// change the DAG while matching. X86 addressing mode matcher is an example3239/// for this.3240class MatchStateUpdater : public SelectionDAG::DAGUpdateListener3241{3242 SDNode **NodeToMatch;3243 SmallVectorImpl<std::pair<SDValue, SDNode *>> &RecordedNodes;3244 SmallVectorImpl<MatchScope> &MatchScopes;3245 3246public:3247 MatchStateUpdater(SelectionDAG &DAG, SDNode **NodeToMatch,3248 SmallVectorImpl<std::pair<SDValue, SDNode *>> &RN,3249 SmallVectorImpl<MatchScope> &MS)3250 : SelectionDAG::DAGUpdateListener(DAG), NodeToMatch(NodeToMatch),3251 RecordedNodes(RN), MatchScopes(MS) {}3252 3253 void NodeDeleted(SDNode *N, SDNode *E) override {3254 // Some early-returns here to avoid the search if we deleted the node or3255 // if the update comes from MorphNodeTo (MorphNodeTo is the last thing we3256 // do, so it's unnecessary to update matching state at that point).3257 // Neither of these can occur currently because we only install this3258 // update listener during matching a complex patterns.3259 if (!E || E->isMachineOpcode())3260 return;3261 // Check if NodeToMatch was updated.3262 if (N == *NodeToMatch)3263 *NodeToMatch = E;3264 // Performing linear search here does not matter because we almost never3265 // run this code. You'd have to have a CSE during complex pattern3266 // matching.3267 for (auto &I : RecordedNodes)3268 if (I.first.getNode() == N)3269 I.first.setNode(E);3270 3271 for (auto &I : MatchScopes)3272 for (auto &J : I.NodeStack)3273 if (J.getNode() == N)3274 J.setNode(E);3275 }3276};3277 3278} // end anonymous namespace3279 3280void SelectionDAGISel::SelectCodeCommon(SDNode *NodeToMatch,3281 const unsigned char *MatcherTable,3282 unsigned TableSize) {3283 // FIXME: Should these even be selected? Handle these cases in the caller?3284 switch (NodeToMatch->getOpcode()) {3285 default:3286 break;3287 case ISD::EntryToken: // These nodes remain the same.3288 case ISD::BasicBlock:3289 case ISD::Register:3290 case ISD::RegisterMask:3291 case ISD::HANDLENODE:3292 case ISD::MDNODE_SDNODE:3293 case ISD::TargetConstant:3294 case ISD::TargetConstantFP:3295 case ISD::TargetConstantPool:3296 case ISD::TargetFrameIndex:3297 case ISD::TargetExternalSymbol:3298 case ISD::MCSymbol:3299 case ISD::TargetBlockAddress:3300 case ISD::TargetJumpTable:3301 case ISD::TargetGlobalTLSAddress:3302 case ISD::TargetGlobalAddress:3303 case ISD::TokenFactor:3304 case ISD::CopyFromReg:3305 case ISD::CopyToReg:3306 case ISD::EH_LABEL:3307 case ISD::ANNOTATION_LABEL:3308 case ISD::LIFETIME_START:3309 case ISD::LIFETIME_END:3310 case ISD::PSEUDO_PROBE:3311 case ISD::DEACTIVATION_SYMBOL:3312 NodeToMatch->setNodeId(-1); // Mark selected.3313 return;3314 case ISD::AssertSext:3315 case ISD::AssertZext:3316 case ISD::AssertNoFPClass:3317 case ISD::AssertAlign:3318 ReplaceUses(SDValue(NodeToMatch, 0), NodeToMatch->getOperand(0));3319 CurDAG->RemoveDeadNode(NodeToMatch);3320 return;3321 case ISD::INLINEASM:3322 case ISD::INLINEASM_BR:3323 Select_INLINEASM(NodeToMatch);3324 return;3325 case ISD::READ_REGISTER:3326 Select_READ_REGISTER(NodeToMatch);3327 return;3328 case ISD::WRITE_REGISTER:3329 Select_WRITE_REGISTER(NodeToMatch);3330 return;3331 case ISD::POISON:3332 case ISD::UNDEF:3333 Select_UNDEF(NodeToMatch);3334 return;3335 case ISD::FAKE_USE:3336 Select_FAKE_USE(NodeToMatch);3337 return;3338 case ISD::RELOC_NONE:3339 Select_RELOC_NONE(NodeToMatch);3340 return;3341 case ISD::FREEZE:3342 Select_FREEZE(NodeToMatch);3343 return;3344 case ISD::ARITH_FENCE:3345 Select_ARITH_FENCE(NodeToMatch);3346 return;3347 case ISD::MEMBARRIER:3348 Select_MEMBARRIER(NodeToMatch);3349 return;3350 case ISD::STACKMAP:3351 Select_STACKMAP(NodeToMatch);3352 return;3353 case ISD::PATCHPOINT:3354 Select_PATCHPOINT(NodeToMatch);3355 return;3356 case ISD::JUMP_TABLE_DEBUG_INFO:3357 Select_JUMP_TABLE_DEBUG_INFO(NodeToMatch);3358 return;3359 case ISD::CONVERGENCECTRL_ANCHOR:3360 Select_CONVERGENCECTRL_ANCHOR(NodeToMatch);3361 return;3362 case ISD::CONVERGENCECTRL_ENTRY:3363 Select_CONVERGENCECTRL_ENTRY(NodeToMatch);3364 return;3365 case ISD::CONVERGENCECTRL_LOOP:3366 Select_CONVERGENCECTRL_LOOP(NodeToMatch);3367 return;3368 }3369 3370 assert(!NodeToMatch->isMachineOpcode() && "Node already selected!");3371 3372 // Set up the node stack with NodeToMatch as the only node on the stack.3373 SmallVector<SDValue, 8> NodeStack;3374 SDValue N = SDValue(NodeToMatch, 0);3375 NodeStack.push_back(N);3376 3377 // MatchScopes - Scopes used when matching, if a match failure happens, this3378 // indicates where to continue checking.3379 SmallVector<MatchScope, 8> MatchScopes;3380 3381 // RecordedNodes - This is the set of nodes that have been recorded by the3382 // state machine. The second value is the parent of the node, or null if the3383 // root is recorded.3384 SmallVector<std::pair<SDValue, SDNode*>, 8> RecordedNodes;3385 3386 // MatchedMemRefs - This is the set of MemRef's we've seen in the input3387 // pattern.3388 SmallVector<MachineMemOperand*, 2> MatchedMemRefs;3389 3390 // These are the current input chain and glue for use when generating nodes.3391 // Various Emit operations change these. For example, emitting a copytoreg3392 // uses and updates these.3393 SDValue InputChain, InputGlue, DeactivationSymbol;3394 3395 // ChainNodesMatched - If a pattern matches nodes that have input/output3396 // chains, the OPC_EmitMergeInputChains operation is emitted which indicates3397 // which ones they are. The result is captured into this list so that we can3398 // update the chain results when the pattern is complete.3399 SmallVector<SDNode*, 3> ChainNodesMatched;3400 3401 LLVM_DEBUG(dbgs() << "ISEL: Starting pattern match\n");3402 3403 // Determine where to start the interpreter. Normally we start at opcode #0,3404 // but if the state machine starts with an OPC_SwitchOpcode, then we3405 // accelerate the first lookup (which is guaranteed to be hot) with the3406 // OpcodeOffset table.3407 unsigned MatcherIndex = 0;3408 3409 if (!OpcodeOffset.empty()) {3410 // Already computed the OpcodeOffset table, just index into it.3411 if (N.getOpcode() < OpcodeOffset.size())3412 MatcherIndex = OpcodeOffset[N.getOpcode()];3413 LLVM_DEBUG(dbgs() << " Initial Opcode index to " << MatcherIndex << "\n");3414 3415 } else if (MatcherTable[0] == OPC_SwitchOpcode) {3416 // Otherwise, the table isn't computed, but the state machine does start3417 // with an OPC_SwitchOpcode instruction. Populate the table now, since this3418 // is the first time we're selecting an instruction.3419 unsigned Idx = 1;3420 while (true) {3421 // Get the size of this case.3422 unsigned CaseSize = MatcherTable[Idx++];3423 if (CaseSize & 128)3424 CaseSize = GetVBR(CaseSize, MatcherTable, Idx);3425 if (CaseSize == 0) break;3426 3427 // Get the opcode, add the index to the table.3428 uint16_t Opc = MatcherTable[Idx++];3429 Opc |= static_cast<uint16_t>(MatcherTable[Idx++]) << 8;3430 if (Opc >= OpcodeOffset.size())3431 OpcodeOffset.resize((Opc+1)*2);3432 OpcodeOffset[Opc] = Idx;3433 Idx += CaseSize;3434 }3435 3436 // Okay, do the lookup for the first opcode.3437 if (N.getOpcode() < OpcodeOffset.size())3438 MatcherIndex = OpcodeOffset[N.getOpcode()];3439 }3440 3441 while (true) {3442 assert(MatcherIndex < TableSize && "Invalid index");3443#ifndef NDEBUG3444 unsigned CurrentOpcodeIndex = MatcherIndex;3445#endif3446 BuiltinOpcodes Opcode =3447 static_cast<BuiltinOpcodes>(MatcherTable[MatcherIndex++]);3448 switch (Opcode) {3449 case OPC_Scope: {3450 // Okay, the semantics of this operation are that we should push a scope3451 // then evaluate the first child. However, pushing a scope only to have3452 // the first check fail (which then pops it) is inefficient. If we can3453 // determine immediately that the first check (or first several) will3454 // immediately fail, don't even bother pushing a scope for them.3455 unsigned FailIndex;3456 3457 while (true) {3458 unsigned NumToSkip = MatcherTable[MatcherIndex++];3459 if (NumToSkip & 128)3460 NumToSkip = GetVBR(NumToSkip, MatcherTable, MatcherIndex);3461 // Found the end of the scope with no match.3462 if (NumToSkip == 0) {3463 FailIndex = 0;3464 break;3465 }3466 3467 FailIndex = MatcherIndex+NumToSkip;3468 3469 unsigned MatcherIndexOfPredicate = MatcherIndex;3470 (void)MatcherIndexOfPredicate; // silence warning.3471 3472 // If we can't evaluate this predicate without pushing a scope (e.g. if3473 // it is a 'MoveParent') or if the predicate succeeds on this node, we3474 // push the scope and evaluate the full predicate chain.3475 bool Result;3476 MatcherIndex = IsPredicateKnownToFail(MatcherTable, MatcherIndex, N,3477 Result, *this, RecordedNodes);3478 if (!Result)3479 break;3480 3481 LLVM_DEBUG(3482 dbgs() << " Skipped scope entry (due to false predicate) at "3483 << "index " << MatcherIndexOfPredicate << ", continuing at "3484 << FailIndex << "\n");3485 ++NumDAGIselRetries;3486 3487 // Otherwise, we know that this case of the Scope is guaranteed to fail,3488 // move to the next case.3489 MatcherIndex = FailIndex;3490 }3491 3492 // If the whole scope failed to match, bail.3493 if (FailIndex == 0) break;3494 3495 // Push a MatchScope which indicates where to go if the first child fails3496 // to match.3497 MatchScope NewEntry;3498 NewEntry.FailIndex = FailIndex;3499 NewEntry.NodeStack.append(NodeStack.begin(), NodeStack.end());3500 NewEntry.NumRecordedNodes = RecordedNodes.size();3501 NewEntry.NumMatchedMemRefs = MatchedMemRefs.size();3502 NewEntry.InputChain = InputChain;3503 NewEntry.InputGlue = InputGlue;3504 NewEntry.HasChainNodesMatched = !ChainNodesMatched.empty();3505 MatchScopes.push_back(NewEntry);3506 continue;3507 }3508 case OPC_RecordNode: {3509 // Remember this node, it may end up being an operand in the pattern.3510 SDNode *Parent = nullptr;3511 if (NodeStack.size() > 1)3512 Parent = NodeStack[NodeStack.size()-2].getNode();3513 RecordedNodes.push_back(std::make_pair(N, Parent));3514 continue;3515 }3516 3517 case OPC_RecordChild0: case OPC_RecordChild1:3518 case OPC_RecordChild2: case OPC_RecordChild3:3519 case OPC_RecordChild4: case OPC_RecordChild5:3520 case OPC_RecordChild6: case OPC_RecordChild7: {3521 unsigned ChildNo = Opcode-OPC_RecordChild0;3522 if (ChildNo >= N.getNumOperands())3523 break; // Match fails if out of range child #.3524 3525 RecordedNodes.push_back(std::make_pair(N->getOperand(ChildNo),3526 N.getNode()));3527 continue;3528 }3529 case OPC_RecordMemRef:3530 if (auto *MN = dyn_cast<MemSDNode>(N))3531 MatchedMemRefs.push_back(MN->getMemOperand());3532 else {3533 LLVM_DEBUG(dbgs() << "Expected MemSDNode "; N->dump(CurDAG);3534 dbgs() << '\n');3535 }3536 3537 continue;3538 3539 case OPC_CaptureGlueInput:3540 // If the current node has an input glue, capture it in InputGlue.3541 if (N->getNumOperands() != 0 &&3542 N->getOperand(N->getNumOperands()-1).getValueType() == MVT::Glue)3543 InputGlue = N->getOperand(N->getNumOperands()-1);3544 continue;3545 3546 case OPC_CaptureDeactivationSymbol:3547 // If the current node has a deactivation symbol, capture it in3548 // DeactivationSymbol.3549 if (N->getNumOperands() != 0 &&3550 N->getOperand(N->getNumOperands() - 1).getOpcode() ==3551 ISD::DEACTIVATION_SYMBOL)3552 DeactivationSymbol = N->getOperand(N->getNumOperands() - 1);3553 continue;3554 3555 case OPC_MoveChild: {3556 unsigned ChildNo = MatcherTable[MatcherIndex++];3557 if (ChildNo >= N.getNumOperands())3558 break; // Match fails if out of range child #.3559 N = N.getOperand(ChildNo);3560 NodeStack.push_back(N);3561 continue;3562 }3563 3564 case OPC_MoveChild0: case OPC_MoveChild1:3565 case OPC_MoveChild2: case OPC_MoveChild3:3566 case OPC_MoveChild4: case OPC_MoveChild5:3567 case OPC_MoveChild6: case OPC_MoveChild7: {3568 unsigned ChildNo = Opcode-OPC_MoveChild0;3569 if (ChildNo >= N.getNumOperands())3570 break; // Match fails if out of range child #.3571 N = N.getOperand(ChildNo);3572 NodeStack.push_back(N);3573 continue;3574 }3575 3576 case OPC_MoveSibling:3577 case OPC_MoveSibling0:3578 case OPC_MoveSibling1:3579 case OPC_MoveSibling2:3580 case OPC_MoveSibling3:3581 case OPC_MoveSibling4:3582 case OPC_MoveSibling5:3583 case OPC_MoveSibling6:3584 case OPC_MoveSibling7: {3585 // Pop the current node off the NodeStack.3586 NodeStack.pop_back();3587 assert(!NodeStack.empty() && "Node stack imbalance!");3588 N = NodeStack.back();3589 3590 unsigned SiblingNo = Opcode == OPC_MoveSibling3591 ? MatcherTable[MatcherIndex++]3592 : Opcode - OPC_MoveSibling0;3593 if (SiblingNo >= N.getNumOperands())3594 break; // Match fails if out of range sibling #.3595 N = N.getOperand(SiblingNo);3596 NodeStack.push_back(N);3597 continue;3598 }3599 case OPC_MoveParent:3600 // Pop the current node off the NodeStack.3601 NodeStack.pop_back();3602 assert(!NodeStack.empty() && "Node stack imbalance!");3603 N = NodeStack.back();3604 continue;3605 3606 case OPC_CheckSame:3607 if (!::CheckSame(MatcherTable, MatcherIndex, N, RecordedNodes)) break;3608 continue;3609 3610 case OPC_CheckChild0Same: case OPC_CheckChild1Same:3611 case OPC_CheckChild2Same: case OPC_CheckChild3Same:3612 if (!::CheckChildSame(MatcherTable, MatcherIndex, N, RecordedNodes,3613 Opcode-OPC_CheckChild0Same))3614 break;3615 continue;3616 3617 case OPC_CheckPatternPredicate:3618 case OPC_CheckPatternPredicate0:3619 case OPC_CheckPatternPredicate1:3620 case OPC_CheckPatternPredicate2:3621 case OPC_CheckPatternPredicate3:3622 case OPC_CheckPatternPredicate4:3623 case OPC_CheckPatternPredicate5:3624 case OPC_CheckPatternPredicate6:3625 case OPC_CheckPatternPredicate7:3626 case OPC_CheckPatternPredicateTwoByte:3627 if (!::CheckPatternPredicate(Opcode, MatcherTable, MatcherIndex, *this))3628 break;3629 continue;3630 case SelectionDAGISel::OPC_CheckPredicate0:3631 case SelectionDAGISel::OPC_CheckPredicate1:3632 case SelectionDAGISel::OPC_CheckPredicate2:3633 case SelectionDAGISel::OPC_CheckPredicate3:3634 case SelectionDAGISel::OPC_CheckPredicate4:3635 case SelectionDAGISel::OPC_CheckPredicate5:3636 case SelectionDAGISel::OPC_CheckPredicate6:3637 case SelectionDAGISel::OPC_CheckPredicate7:3638 case OPC_CheckPredicate:3639 if (!::CheckNodePredicate(Opcode, MatcherTable, MatcherIndex, *this, N))3640 break;3641 continue;3642 case OPC_CheckPredicateWithOperands: {3643 unsigned OpNum = MatcherTable[MatcherIndex++];3644 SmallVector<SDValue, 8> Operands;3645 3646 for (unsigned i = 0; i < OpNum; ++i)3647 Operands.push_back(RecordedNodes[MatcherTable[MatcherIndex++]].first);3648 3649 unsigned PredNo = MatcherTable[MatcherIndex++];3650 if (!CheckNodePredicateWithOperands(N, PredNo, Operands))3651 break;3652 continue;3653 }3654 case OPC_CheckComplexPat:3655 case OPC_CheckComplexPat0:3656 case OPC_CheckComplexPat1:3657 case OPC_CheckComplexPat2:3658 case OPC_CheckComplexPat3:3659 case OPC_CheckComplexPat4:3660 case OPC_CheckComplexPat5:3661 case OPC_CheckComplexPat6:3662 case OPC_CheckComplexPat7: {3663 unsigned CPNum = Opcode == OPC_CheckComplexPat3664 ? MatcherTable[MatcherIndex++]3665 : Opcode - OPC_CheckComplexPat0;3666 unsigned RecNo = MatcherTable[MatcherIndex++];3667 assert(RecNo < RecordedNodes.size() && "Invalid CheckComplexPat");3668 3669 // If target can modify DAG during matching, keep the matching state3670 // consistent.3671 std::unique_ptr<MatchStateUpdater> MSU;3672 if (ComplexPatternFuncMutatesDAG())3673 MSU.reset(new MatchStateUpdater(*CurDAG, &NodeToMatch, RecordedNodes,3674 MatchScopes));3675 3676 if (!CheckComplexPattern(NodeToMatch, RecordedNodes[RecNo].second,3677 RecordedNodes[RecNo].first, CPNum,3678 RecordedNodes))3679 break;3680 continue;3681 }3682 case OPC_CheckOpcode:3683 if (!::CheckOpcode(MatcherTable, MatcherIndex, N.getNode())) break;3684 continue;3685 3686 case OPC_CheckType:3687 case OPC_CheckTypeI32:3688 case OPC_CheckTypeI64:3689 MVT::SimpleValueType VT;3690 switch (Opcode) {3691 case OPC_CheckTypeI32:3692 VT = MVT::i32;3693 break;3694 case OPC_CheckTypeI64:3695 VT = MVT::i64;3696 break;3697 default:3698 VT = getSimpleVT(MatcherTable, MatcherIndex);3699 break;3700 }3701 if (!::CheckType(VT, N, TLI, CurDAG->getDataLayout()))3702 break;3703 continue;3704 3705 case OPC_CheckTypeRes: {3706 unsigned Res = MatcherTable[MatcherIndex++];3707 if (!::CheckType(getSimpleVT(MatcherTable, MatcherIndex), N.getValue(Res),3708 TLI, CurDAG->getDataLayout()))3709 break;3710 continue;3711 }3712 3713 case OPC_SwitchOpcode: {3714 unsigned CurNodeOpcode = N.getOpcode();3715 unsigned SwitchStart = MatcherIndex-1; (void)SwitchStart;3716 unsigned CaseSize;3717 while (true) {3718 // Get the size of this case.3719 CaseSize = MatcherTable[MatcherIndex++];3720 if (CaseSize & 128)3721 CaseSize = GetVBR(CaseSize, MatcherTable, MatcherIndex);3722 if (CaseSize == 0) break;3723 3724 uint16_t Opc = MatcherTable[MatcherIndex++];3725 Opc |= static_cast<uint16_t>(MatcherTable[MatcherIndex++]) << 8;3726 3727 // If the opcode matches, then we will execute this case.3728 if (CurNodeOpcode == Opc)3729 break;3730 3731 // Otherwise, skip over this case.3732 MatcherIndex += CaseSize;3733 }3734 3735 // If no cases matched, bail out.3736 if (CaseSize == 0) break;3737 3738 // Otherwise, execute the case we found.3739 LLVM_DEBUG(dbgs() << " OpcodeSwitch from " << SwitchStart << " to "3740 << MatcherIndex << "\n");3741 continue;3742 }3743 3744 case OPC_SwitchType: {3745 MVT CurNodeVT = N.getSimpleValueType();3746 unsigned SwitchStart = MatcherIndex-1; (void)SwitchStart;3747 unsigned CaseSize;3748 while (true) {3749 // Get the size of this case.3750 CaseSize = MatcherTable[MatcherIndex++];3751 if (CaseSize & 128)3752 CaseSize = GetVBR(CaseSize, MatcherTable, MatcherIndex);3753 if (CaseSize == 0) break;3754 3755 MVT CaseVT = getSimpleVT(MatcherTable, MatcherIndex);3756 if (CaseVT == MVT::iPTR)3757 CaseVT = TLI->getPointerTy(CurDAG->getDataLayout());3758 3759 // If the VT matches, then we will execute this case.3760 if (CurNodeVT == CaseVT)3761 break;3762 3763 // Otherwise, skip over this case.3764 MatcherIndex += CaseSize;3765 }3766 3767 // If no cases matched, bail out.3768 if (CaseSize == 0) break;3769 3770 // Otherwise, execute the case we found.3771 LLVM_DEBUG(dbgs() << " TypeSwitch[" << CurNodeVT3772 << "] from " << SwitchStart << " to " << MatcherIndex3773 << '\n');3774 continue;3775 }3776 case OPC_CheckChild0Type:3777 case OPC_CheckChild1Type:3778 case OPC_CheckChild2Type:3779 case OPC_CheckChild3Type:3780 case OPC_CheckChild4Type:3781 case OPC_CheckChild5Type:3782 case OPC_CheckChild6Type:3783 case OPC_CheckChild7Type:3784 case OPC_CheckChild0TypeI32:3785 case OPC_CheckChild1TypeI32:3786 case OPC_CheckChild2TypeI32:3787 case OPC_CheckChild3TypeI32:3788 case OPC_CheckChild4TypeI32:3789 case OPC_CheckChild5TypeI32:3790 case OPC_CheckChild6TypeI32:3791 case OPC_CheckChild7TypeI32:3792 case OPC_CheckChild0TypeI64:3793 case OPC_CheckChild1TypeI64:3794 case OPC_CheckChild2TypeI64:3795 case OPC_CheckChild3TypeI64:3796 case OPC_CheckChild4TypeI64:3797 case OPC_CheckChild5TypeI64:3798 case OPC_CheckChild6TypeI64:3799 case OPC_CheckChild7TypeI64: {3800 MVT::SimpleValueType VT;3801 unsigned ChildNo;3802 if (Opcode >= SelectionDAGISel::OPC_CheckChild0TypeI32 &&3803 Opcode <= SelectionDAGISel::OPC_CheckChild7TypeI32) {3804 VT = MVT::i32;3805 ChildNo = Opcode - SelectionDAGISel::OPC_CheckChild0TypeI32;3806 } else if (Opcode >= SelectionDAGISel::OPC_CheckChild0TypeI64 &&3807 Opcode <= SelectionDAGISel::OPC_CheckChild7TypeI64) {3808 VT = MVT::i64;3809 ChildNo = Opcode - SelectionDAGISel::OPC_CheckChild0TypeI64;3810 } else {3811 VT = getSimpleVT(MatcherTable, MatcherIndex);3812 ChildNo = Opcode - SelectionDAGISel::OPC_CheckChild0Type;3813 }3814 if (!::CheckChildType(VT, N, TLI, CurDAG->getDataLayout(), ChildNo))3815 break;3816 continue;3817 }3818 case OPC_CheckCondCode:3819 if (!::CheckCondCode(MatcherTable, MatcherIndex, N)) break;3820 continue;3821 case OPC_CheckChild2CondCode:3822 if (!::CheckChild2CondCode(MatcherTable, MatcherIndex, N)) break;3823 continue;3824 case OPC_CheckValueType:3825 if (!::CheckValueType(MatcherTable, MatcherIndex, N, TLI,3826 CurDAG->getDataLayout()))3827 break;3828 continue;3829 case OPC_CheckInteger:3830 if (!::CheckInteger(MatcherTable, MatcherIndex, N)) break;3831 continue;3832 case OPC_CheckChild0Integer: case OPC_CheckChild1Integer:3833 case OPC_CheckChild2Integer: case OPC_CheckChild3Integer:3834 case OPC_CheckChild4Integer:3835 if (!::CheckChildInteger(MatcherTable, MatcherIndex, N,3836 Opcode-OPC_CheckChild0Integer)) break;3837 continue;3838 case OPC_CheckAndImm:3839 if (!::CheckAndImm(MatcherTable, MatcherIndex, N, *this)) break;3840 continue;3841 case OPC_CheckOrImm:3842 if (!::CheckOrImm(MatcherTable, MatcherIndex, N, *this)) break;3843 continue;3844 case OPC_CheckImmAllOnesV:3845 if (!ISD::isConstantSplatVectorAllOnes(N.getNode()))3846 break;3847 continue;3848 case OPC_CheckImmAllZerosV:3849 if (!ISD::isConstantSplatVectorAllZeros(N.getNode()))3850 break;3851 continue;3852 3853 case OPC_CheckFoldableChainNode: {3854 assert(NodeStack.size() != 1 && "No parent node");3855 // Verify that all intermediate nodes between the root and this one have3856 // a single use (ignoring chains, which are handled in UpdateChains).3857 bool HasMultipleUses = false;3858 for (unsigned i = 1, e = NodeStack.size()-1; i != e; ++i) {3859 unsigned NNonChainUses = 0;3860 SDNode *NS = NodeStack[i].getNode();3861 for (const SDUse &U : NS->uses())3862 if (U.getValueType() != MVT::Other)3863 if (++NNonChainUses > 1) {3864 HasMultipleUses = true;3865 break;3866 }3867 if (HasMultipleUses) break;3868 }3869 if (HasMultipleUses) break;3870 3871 // Check to see that the target thinks this is profitable to fold and that3872 // we can fold it without inducing cycles in the graph.3873 if (!IsProfitableToFold(N, NodeStack[NodeStack.size()-2].getNode(),3874 NodeToMatch) ||3875 !IsLegalToFold(N, NodeStack[NodeStack.size()-2].getNode(),3876 NodeToMatch, OptLevel,3877 true/*We validate our own chains*/))3878 break;3879 3880 continue;3881 }3882 case OPC_EmitInteger:3883 case OPC_EmitInteger8:3884 case OPC_EmitInteger16:3885 case OPC_EmitInteger32:3886 case OPC_EmitInteger64:3887 case OPC_EmitStringInteger:3888 case OPC_EmitStringInteger32: {3889 MVT::SimpleValueType VT;3890 switch (Opcode) {3891 case OPC_EmitInteger8:3892 VT = MVT::i8;3893 break;3894 case OPC_EmitInteger16:3895 VT = MVT::i16;3896 break;3897 case OPC_EmitInteger32:3898 case OPC_EmitStringInteger32:3899 VT = MVT::i32;3900 break;3901 case OPC_EmitInteger64:3902 VT = MVT::i64;3903 break;3904 default:3905 VT = getSimpleVT(MatcherTable, MatcherIndex);3906 break;3907 }3908 int64_t Val = MatcherTable[MatcherIndex++];3909 if (Val & 128)3910 Val = GetVBR(Val, MatcherTable, MatcherIndex);3911 if (Opcode >= OPC_EmitInteger && Opcode <= OPC_EmitInteger64)3912 Val = decodeSignRotatedValue(Val);3913 RecordedNodes.push_back(std::pair<SDValue, SDNode *>(3914 CurDAG->getSignedConstant(Val, SDLoc(NodeToMatch), VT,3915 /*isTarget=*/true),3916 nullptr));3917 continue;3918 }3919 case OPC_EmitRegister:3920 case OPC_EmitRegisterI32:3921 case OPC_EmitRegisterI64: {3922 MVT::SimpleValueType VT;3923 switch (Opcode) {3924 case OPC_EmitRegisterI32:3925 VT = MVT::i32;3926 break;3927 case OPC_EmitRegisterI64:3928 VT = MVT::i64;3929 break;3930 default:3931 VT = getSimpleVT(MatcherTable, MatcherIndex);3932 break;3933 }3934 unsigned RegNo = MatcherTable[MatcherIndex++];3935 RecordedNodes.push_back(std::pair<SDValue, SDNode *>(3936 CurDAG->getRegister(RegNo, VT), nullptr));3937 continue;3938 }3939 case OPC_EmitRegister2: {3940 // For targets w/ more than 256 register names, the register enum3941 // values are stored in two bytes in the matcher table (just like3942 // opcodes).3943 MVT::SimpleValueType VT = getSimpleVT(MatcherTable, MatcherIndex);3944 unsigned RegNo = MatcherTable[MatcherIndex++];3945 RegNo |= MatcherTable[MatcherIndex++] << 8;3946 RecordedNodes.push_back(std::pair<SDValue, SDNode*>(3947 CurDAG->getRegister(RegNo, VT), nullptr));3948 continue;3949 }3950 3951 case OPC_EmitConvertToTarget:3952 case OPC_EmitConvertToTarget0:3953 case OPC_EmitConvertToTarget1:3954 case OPC_EmitConvertToTarget2:3955 case OPC_EmitConvertToTarget3:3956 case OPC_EmitConvertToTarget4:3957 case OPC_EmitConvertToTarget5:3958 case OPC_EmitConvertToTarget6:3959 case OPC_EmitConvertToTarget7: {3960 // Convert from IMM/FPIMM to target version.3961 unsigned RecNo = Opcode == OPC_EmitConvertToTarget3962 ? MatcherTable[MatcherIndex++]3963 : Opcode - OPC_EmitConvertToTarget0;3964 assert(RecNo < RecordedNodes.size() && "Invalid EmitConvertToTarget");3965 SDValue Imm = RecordedNodes[RecNo].first;3966 3967 if (Imm->getOpcode() == ISD::Constant) {3968 const ConstantInt *Val=cast<ConstantSDNode>(Imm)->getConstantIntValue();3969 Imm = CurDAG->getTargetConstant(*Val, SDLoc(NodeToMatch),3970 Imm.getValueType());3971 } else if (Imm->getOpcode() == ISD::ConstantFP) {3972 const ConstantFP *Val=cast<ConstantFPSDNode>(Imm)->getConstantFPValue();3973 Imm = CurDAG->getTargetConstantFP(*Val, SDLoc(NodeToMatch),3974 Imm.getValueType());3975 }3976 3977 RecordedNodes.push_back(std::make_pair(Imm, RecordedNodes[RecNo].second));3978 continue;3979 }3980 3981 case OPC_EmitMergeInputChains1_0: // OPC_EmitMergeInputChains, 1, 03982 case OPC_EmitMergeInputChains1_1: // OPC_EmitMergeInputChains, 1, 13983 case OPC_EmitMergeInputChains1_2: { // OPC_EmitMergeInputChains, 1, 23984 // These are space-optimized forms of OPC_EmitMergeInputChains.3985 assert(!InputChain.getNode() &&3986 "EmitMergeInputChains should be the first chain producing node");3987 assert(ChainNodesMatched.empty() &&3988 "Should only have one EmitMergeInputChains per match");3989 3990 // Read all of the chained nodes.3991 unsigned RecNo = Opcode - OPC_EmitMergeInputChains1_0;3992 assert(RecNo < RecordedNodes.size() && "Invalid EmitMergeInputChains");3993 ChainNodesMatched.push_back(RecordedNodes[RecNo].first.getNode());3994 3995 // If the chained node is not the root, we can't fold it if it has3996 // multiple uses.3997 // FIXME: What if other value results of the node have uses not matched3998 // by this pattern?3999 if (ChainNodesMatched.back() != NodeToMatch &&4000 !RecordedNodes[RecNo].first.hasOneUse()) {4001 ChainNodesMatched.clear();4002 break;4003 }4004 4005 // Merge the input chains if they are not intra-pattern references.4006 InputChain = HandleMergeInputChains(ChainNodesMatched, InputGlue, CurDAG);4007 4008 if (!InputChain.getNode())4009 break; // Failed to merge.4010 continue;4011 }4012 4013 case OPC_EmitMergeInputChains: {4014 assert(!InputChain.getNode() &&4015 "EmitMergeInputChains should be the first chain producing node");4016 // This node gets a list of nodes we matched in the input that have4017 // chains. We want to token factor all of the input chains to these nodes4018 // together. However, if any of the input chains is actually one of the4019 // nodes matched in this pattern, then we have an intra-match reference.4020 // Ignore these because the newly token factored chain should not refer to4021 // the old nodes.4022 unsigned NumChains = MatcherTable[MatcherIndex++];4023 assert(NumChains != 0 && "Can't TF zero chains");4024 4025 assert(ChainNodesMatched.empty() &&4026 "Should only have one EmitMergeInputChains per match");4027 4028 // Read all of the chained nodes.4029 for (unsigned i = 0; i != NumChains; ++i) {4030 unsigned RecNo = MatcherTable[MatcherIndex++];4031 assert(RecNo < RecordedNodes.size() && "Invalid EmitMergeInputChains");4032 ChainNodesMatched.push_back(RecordedNodes[RecNo].first.getNode());4033 4034 // If the chained node is not the root, we can't fold it if it has4035 // multiple uses.4036 // FIXME: What if other value results of the node have uses not matched4037 // by this pattern?4038 if (ChainNodesMatched.back() != NodeToMatch &&4039 !RecordedNodes[RecNo].first.hasOneUse()) {4040 ChainNodesMatched.clear();4041 break;4042 }4043 }4044 4045 // If the inner loop broke out, the match fails.4046 if (ChainNodesMatched.empty())4047 break;4048 4049 // Merge the input chains if they are not intra-pattern references.4050 InputChain = HandleMergeInputChains(ChainNodesMatched, InputGlue, CurDAG);4051 4052 if (!InputChain.getNode())4053 break; // Failed to merge.4054 4055 continue;4056 }4057 4058 case OPC_EmitCopyToReg:4059 case OPC_EmitCopyToReg0:4060 case OPC_EmitCopyToReg1:4061 case OPC_EmitCopyToReg2:4062 case OPC_EmitCopyToReg3:4063 case OPC_EmitCopyToReg4:4064 case OPC_EmitCopyToReg5:4065 case OPC_EmitCopyToReg6:4066 case OPC_EmitCopyToReg7:4067 case OPC_EmitCopyToRegTwoByte: {4068 unsigned RecNo =4069 Opcode >= OPC_EmitCopyToReg0 && Opcode <= OPC_EmitCopyToReg74070 ? Opcode - OPC_EmitCopyToReg04071 : MatcherTable[MatcherIndex++];4072 assert(RecNo < RecordedNodes.size() && "Invalid EmitCopyToReg");4073 unsigned DestPhysReg = MatcherTable[MatcherIndex++];4074 if (Opcode == OPC_EmitCopyToRegTwoByte)4075 DestPhysReg |= MatcherTable[MatcherIndex++] << 8;4076 4077 if (!InputChain.getNode())4078 InputChain = CurDAG->getEntryNode();4079 4080 InputChain = CurDAG->getCopyToReg(InputChain, SDLoc(NodeToMatch),4081 DestPhysReg, RecordedNodes[RecNo].first,4082 InputGlue);4083 4084 InputGlue = InputChain.getValue(1);4085 continue;4086 }4087 4088 case OPC_EmitNodeXForm: {4089 unsigned XFormNo = MatcherTable[MatcherIndex++];4090 unsigned RecNo = MatcherTable[MatcherIndex++];4091 assert(RecNo < RecordedNodes.size() && "Invalid EmitNodeXForm");4092 SDValue Res = RunSDNodeXForm(RecordedNodes[RecNo].first, XFormNo);4093 RecordedNodes.push_back(std::pair<SDValue,SDNode*>(Res, nullptr));4094 continue;4095 }4096 case OPC_Coverage: {4097 // This is emitted right before MorphNode/EmitNode.4098 // So it should be safe to assume that this node has been selected4099 unsigned index = MatcherTable[MatcherIndex++];4100 index |= (MatcherTable[MatcherIndex++] << 8);4101 index |= (MatcherTable[MatcherIndex++] << 16);4102 index |= (MatcherTable[MatcherIndex++] << 24);4103 dbgs() << "COVERED: " << getPatternForIndex(index) << "\n";4104 dbgs() << "INCLUDED: " << getIncludePathForIndex(index) << "\n";4105 continue;4106 }4107 4108 case OPC_EmitNode:4109 case OPC_EmitNode0:4110 case OPC_EmitNode1:4111 case OPC_EmitNode2:4112 case OPC_EmitNode0None:4113 case OPC_EmitNode1None:4114 case OPC_EmitNode2None:4115 case OPC_EmitNode0Chain:4116 case OPC_EmitNode1Chain:4117 case OPC_EmitNode2Chain:4118 case OPC_MorphNodeTo:4119 case OPC_MorphNodeTo0:4120 case OPC_MorphNodeTo1:4121 case OPC_MorphNodeTo2:4122 case OPC_MorphNodeTo0None:4123 case OPC_MorphNodeTo1None:4124 case OPC_MorphNodeTo2None:4125 case OPC_MorphNodeTo0Chain:4126 case OPC_MorphNodeTo1Chain:4127 case OPC_MorphNodeTo2Chain:4128 case OPC_MorphNodeTo0GlueInput:4129 case OPC_MorphNodeTo1GlueInput:4130 case OPC_MorphNodeTo2GlueInput:4131 case OPC_MorphNodeTo0GlueOutput:4132 case OPC_MorphNodeTo1GlueOutput:4133 case OPC_MorphNodeTo2GlueOutput: {4134 uint16_t TargetOpc = MatcherTable[MatcherIndex++];4135 TargetOpc |= static_cast<uint16_t>(MatcherTable[MatcherIndex++]) << 8;4136 unsigned EmitNodeInfo;4137 if (Opcode >= OPC_EmitNode0None && Opcode <= OPC_EmitNode2Chain) {4138 if (Opcode >= OPC_EmitNode0Chain && Opcode <= OPC_EmitNode2Chain)4139 EmitNodeInfo = OPFL_Chain;4140 else4141 EmitNodeInfo = OPFL_None;4142 } else if (Opcode >= OPC_MorphNodeTo0None &&4143 Opcode <= OPC_MorphNodeTo2GlueOutput) {4144 if (Opcode >= OPC_MorphNodeTo0Chain && Opcode <= OPC_MorphNodeTo2Chain)4145 EmitNodeInfo = OPFL_Chain;4146 else if (Opcode >= OPC_MorphNodeTo0GlueInput &&4147 Opcode <= OPC_MorphNodeTo2GlueInput)4148 EmitNodeInfo = OPFL_GlueInput;4149 else if (Opcode >= OPC_MorphNodeTo0GlueOutput &&4150 Opcode <= OPC_MorphNodeTo2GlueOutput)4151 EmitNodeInfo = OPFL_GlueOutput;4152 else4153 EmitNodeInfo = OPFL_None;4154 } else4155 EmitNodeInfo = MatcherTable[MatcherIndex++];4156 // Get the result VT list.4157 unsigned NumVTs;4158 // If this is one of the compressed forms, get the number of VTs based4159 // on the Opcode. Otherwise read the next byte from the table.4160 if (Opcode >= OPC_MorphNodeTo0 && Opcode <= OPC_MorphNodeTo2)4161 NumVTs = Opcode - OPC_MorphNodeTo0;4162 else if (Opcode >= OPC_MorphNodeTo0None && Opcode <= OPC_MorphNodeTo2None)4163 NumVTs = Opcode - OPC_MorphNodeTo0None;4164 else if (Opcode >= OPC_MorphNodeTo0Chain &&4165 Opcode <= OPC_MorphNodeTo2Chain)4166 NumVTs = Opcode - OPC_MorphNodeTo0Chain;4167 else if (Opcode >= OPC_MorphNodeTo0GlueInput &&4168 Opcode <= OPC_MorphNodeTo2GlueInput)4169 NumVTs = Opcode - OPC_MorphNodeTo0GlueInput;4170 else if (Opcode >= OPC_MorphNodeTo0GlueOutput &&4171 Opcode <= OPC_MorphNodeTo2GlueOutput)4172 NumVTs = Opcode - OPC_MorphNodeTo0GlueOutput;4173 else if (Opcode >= OPC_EmitNode0 && Opcode <= OPC_EmitNode2)4174 NumVTs = Opcode - OPC_EmitNode0;4175 else if (Opcode >= OPC_EmitNode0None && Opcode <= OPC_EmitNode2None)4176 NumVTs = Opcode - OPC_EmitNode0None;4177 else if (Opcode >= OPC_EmitNode0Chain && Opcode <= OPC_EmitNode2Chain)4178 NumVTs = Opcode - OPC_EmitNode0Chain;4179 else4180 NumVTs = MatcherTable[MatcherIndex++];4181 SmallVector<EVT, 4> VTs;4182 for (unsigned i = 0; i != NumVTs; ++i) {4183 MVT::SimpleValueType VT = getSimpleVT(MatcherTable, MatcherIndex);4184 if (VT == MVT::iPTR)4185 VT = TLI->getPointerTy(CurDAG->getDataLayout()).SimpleTy;4186 VTs.push_back(VT);4187 }4188 4189 if (EmitNodeInfo & OPFL_Chain)4190 VTs.push_back(MVT::Other);4191 if (EmitNodeInfo & OPFL_GlueOutput)4192 VTs.push_back(MVT::Glue);4193 4194 // This is hot code, so optimize the two most common cases of 1 and 24195 // results.4196 SDVTList VTList;4197 if (VTs.size() == 1)4198 VTList = CurDAG->getVTList(VTs[0]);4199 else if (VTs.size() == 2)4200 VTList = CurDAG->getVTList(VTs[0], VTs[1]);4201 else4202 VTList = CurDAG->getVTList(VTs);4203 4204 // Get the operand list.4205 unsigned NumOps = MatcherTable[MatcherIndex++];4206 SmallVector<SDValue, 8> Ops;4207 for (unsigned i = 0; i != NumOps; ++i) {4208 unsigned RecNo = MatcherTable[MatcherIndex++];4209 if (RecNo & 128)4210 RecNo = GetVBR(RecNo, MatcherTable, MatcherIndex);4211 4212 assert(RecNo < RecordedNodes.size() && "Invalid EmitNode");4213 Ops.push_back(RecordedNodes[RecNo].first);4214 }4215 4216 // If there are variadic operands to add, handle them now.4217 if (EmitNodeInfo & OPFL_VariadicInfo) {4218 // Determine the start index to copy from.4219 unsigned FirstOpToCopy = getNumFixedFromVariadicInfo(EmitNodeInfo);4220 FirstOpToCopy += (EmitNodeInfo & OPFL_Chain) ? 1 : 0;4221 assert(NodeToMatch->getNumOperands() >= FirstOpToCopy &&4222 "Invalid variadic node");4223 // Copy all of the variadic operands, not including a potential glue4224 // input.4225 for (unsigned i = FirstOpToCopy, e = NodeToMatch->getNumOperands();4226 i != e; ++i) {4227 SDValue V = NodeToMatch->getOperand(i);4228 if (V.getValueType() == MVT::Glue) break;4229 Ops.push_back(V);4230 }4231 }4232 4233 // If this has chain/glue inputs, add them.4234 if (EmitNodeInfo & OPFL_Chain)4235 Ops.push_back(InputChain);4236 if (DeactivationSymbol.getNode() != nullptr)4237 Ops.push_back(DeactivationSymbol);4238 if ((EmitNodeInfo & OPFL_GlueInput) && InputGlue.getNode() != nullptr)4239 Ops.push_back(InputGlue);4240 4241 // Check whether any matched node could raise an FP exception. Since all4242 // such nodes must have a chain, it suffices to check ChainNodesMatched.4243 // We need to perform this check before potentially modifying one of the4244 // nodes via MorphNode.4245 bool MayRaiseFPException =4246 llvm::any_of(ChainNodesMatched, [this](SDNode *N) {4247 return mayRaiseFPException(N) && !N->getFlags().hasNoFPExcept();4248 });4249 4250 // Create the node.4251 MachineSDNode *Res = nullptr;4252 bool IsMorphNodeTo =4253 Opcode == OPC_MorphNodeTo ||4254 (Opcode >= OPC_MorphNodeTo0 && Opcode <= OPC_MorphNodeTo2GlueOutput);4255 if (!IsMorphNodeTo) {4256 // If this is a normal EmitNode command, just create the new node and4257 // add the results to the RecordedNodes list.4258 Res = CurDAG->getMachineNode(TargetOpc, SDLoc(NodeToMatch),4259 VTList, Ops);4260 4261 // Add all the non-glue/non-chain results to the RecordedNodes list.4262 for (unsigned i = 0, e = VTs.size(); i != e; ++i) {4263 if (VTs[i] == MVT::Other || VTs[i] == MVT::Glue) break;4264 RecordedNodes.push_back(std::pair<SDValue,SDNode*>(SDValue(Res, i),4265 nullptr));4266 }4267 } else {4268 assert(NodeToMatch->getOpcode() != ISD::DELETED_NODE &&4269 "NodeToMatch was removed partway through selection");4270 SelectionDAG::DAGNodeDeletedListener NDL(*CurDAG, [&](SDNode *N,4271 SDNode *E) {4272 CurDAG->salvageDebugInfo(*N);4273 auto &Chain = ChainNodesMatched;4274 assert((!E || !is_contained(Chain, N)) &&4275 "Chain node replaced during MorphNode");4276 llvm::erase(Chain, N);4277 });4278 Res = cast<MachineSDNode>(MorphNode(NodeToMatch, TargetOpc, VTList,4279 Ops, EmitNodeInfo));4280 }4281 4282 // Set the NoFPExcept flag when no original matched node could4283 // raise an FP exception, but the new node potentially might.4284 if (!MayRaiseFPException && mayRaiseFPException(Res))4285 Res->setFlags(Res->getFlags() | SDNodeFlags::NoFPExcept);4286 4287 // If the node had chain/glue results, update our notion of the current4288 // chain and glue.4289 if (EmitNodeInfo & OPFL_GlueOutput) {4290 InputGlue = SDValue(Res, VTs.size()-1);4291 if (EmitNodeInfo & OPFL_Chain)4292 InputChain = SDValue(Res, VTs.size()-2);4293 } else if (EmitNodeInfo & OPFL_Chain)4294 InputChain = SDValue(Res, VTs.size()-1);4295 4296 // If the OPFL_MemRefs glue is set on this node, slap all of the4297 // accumulated memrefs onto it.4298 //4299 // FIXME: This is vastly incorrect for patterns with multiple outputs4300 // instructions that access memory and for ComplexPatterns that match4301 // loads.4302 if (EmitNodeInfo & OPFL_MemRefs) {4303 // Only attach load or store memory operands if the generated4304 // instruction may load or store.4305 const MCInstrDesc &MCID = TII->get(TargetOpc);4306 bool mayLoad = MCID.mayLoad();4307 bool mayStore = MCID.mayStore();4308 4309 // We expect to have relatively few of these so just filter them into a4310 // temporary buffer so that we can easily add them to the instruction.4311 SmallVector<MachineMemOperand *, 4> FilteredMemRefs;4312 for (MachineMemOperand *MMO : MatchedMemRefs) {4313 if (MMO->isLoad()) {4314 if (mayLoad)4315 FilteredMemRefs.push_back(MMO);4316 } else if (MMO->isStore()) {4317 if (mayStore)4318 FilteredMemRefs.push_back(MMO);4319 } else {4320 FilteredMemRefs.push_back(MMO);4321 }4322 }4323 4324 CurDAG->setNodeMemRefs(Res, FilteredMemRefs);4325 }4326 4327 LLVM_DEBUG({4328 if (!MatchedMemRefs.empty() && Res->memoperands_empty())4329 dbgs() << " Dropping mem operands\n";4330 dbgs() << " " << (IsMorphNodeTo ? "Morphed" : "Created") << " node: ";4331 Res->dump(CurDAG);4332 });4333 4334 // If this was a MorphNodeTo then we're completely done!4335 if (IsMorphNodeTo) {4336 // Update chain uses.4337 UpdateChains(Res, InputChain, ChainNodesMatched, true);4338 return;4339 }4340 continue;4341 }4342 4343 case OPC_CompleteMatch: {4344 // The match has been completed, and any new nodes (if any) have been4345 // created. Patch up references to the matched dag to use the newly4346 // created nodes.4347 unsigned NumResults = MatcherTable[MatcherIndex++];4348 4349 for (unsigned i = 0; i != NumResults; ++i) {4350 unsigned ResSlot = MatcherTable[MatcherIndex++];4351 if (ResSlot & 128)4352 ResSlot = GetVBR(ResSlot, MatcherTable, MatcherIndex);4353 4354 assert(ResSlot < RecordedNodes.size() && "Invalid CompleteMatch");4355 SDValue Res = RecordedNodes[ResSlot].first;4356 4357 assert(i < NodeToMatch->getNumValues() &&4358 NodeToMatch->getValueType(i) != MVT::Other &&4359 NodeToMatch->getValueType(i) != MVT::Glue &&4360 "Invalid number of results to complete!");4361 assert((NodeToMatch->getValueType(i) == Res.getValueType() ||4362 NodeToMatch->getValueType(i) == MVT::iPTR ||4363 Res.getValueType() == MVT::iPTR ||4364 NodeToMatch->getValueType(i).getSizeInBits() ==4365 Res.getValueSizeInBits()) &&4366 "invalid replacement");4367 ReplaceUses(SDValue(NodeToMatch, i), Res);4368 }4369 4370 // Update chain uses.4371 UpdateChains(NodeToMatch, InputChain, ChainNodesMatched, false);4372 4373 // If the root node defines glue, we need to update it to the glue result.4374 // TODO: This never happens in our tests and I think it can be removed /4375 // replaced with an assert, but if we do it this the way the change is4376 // NFC.4377 if (NodeToMatch->getValueType(NodeToMatch->getNumValues() - 1) ==4378 MVT::Glue &&4379 InputGlue.getNode())4380 ReplaceUses(SDValue(NodeToMatch, NodeToMatch->getNumValues() - 1),4381 InputGlue);4382 4383 assert(NodeToMatch->use_empty() &&4384 "Didn't replace all uses of the node?");4385 CurDAG->RemoveDeadNode(NodeToMatch);4386 4387 return;4388 }4389 }4390 4391 // If the code reached this point, then the match failed. See if there is4392 // another child to try in the current 'Scope', otherwise pop it until we4393 // find a case to check.4394 LLVM_DEBUG(dbgs() << " Match failed at index " << CurrentOpcodeIndex4395 << "\n");4396 ++NumDAGIselRetries;4397 while (true) {4398 if (MatchScopes.empty()) {4399 CannotYetSelect(NodeToMatch);4400 return;4401 }4402 4403 // Restore the interpreter state back to the point where the scope was4404 // formed.4405 MatchScope &LastScope = MatchScopes.back();4406 RecordedNodes.resize(LastScope.NumRecordedNodes);4407 NodeStack.clear();4408 NodeStack.append(LastScope.NodeStack.begin(), LastScope.NodeStack.end());4409 N = NodeStack.back();4410 4411 if (LastScope.NumMatchedMemRefs != MatchedMemRefs.size())4412 MatchedMemRefs.resize(LastScope.NumMatchedMemRefs);4413 MatcherIndex = LastScope.FailIndex;4414 4415 LLVM_DEBUG(dbgs() << " Continuing at " << MatcherIndex << "\n");4416 4417 InputChain = LastScope.InputChain;4418 InputGlue = LastScope.InputGlue;4419 if (!LastScope.HasChainNodesMatched)4420 ChainNodesMatched.clear();4421 4422 // Check to see what the offset is at the new MatcherIndex. If it is zero4423 // we have reached the end of this scope, otherwise we have another child4424 // in the current scope to try.4425 unsigned NumToSkip = MatcherTable[MatcherIndex++];4426 if (NumToSkip & 128)4427 NumToSkip = GetVBR(NumToSkip, MatcherTable, MatcherIndex);4428 4429 // If we have another child in this scope to match, update FailIndex and4430 // try it.4431 if (NumToSkip != 0) {4432 LastScope.FailIndex = MatcherIndex+NumToSkip;4433 break;4434 }4435 4436 // End of this scope, pop it and try the next child in the containing4437 // scope.4438 MatchScopes.pop_back();4439 }4440 }4441}4442 4443/// Return whether the node may raise an FP exception.4444bool SelectionDAGISel::mayRaiseFPException(SDNode *N) const {4445 // For machine opcodes, consult the MCID flag.4446 if (N->isMachineOpcode()) {4447 const MCInstrDesc &MCID = TII->get(N->getMachineOpcode());4448 return MCID.mayRaiseFPException();4449 }4450 4451 // For ISD opcodes, only StrictFP opcodes may raise an FP4452 // exception.4453 if (N->isTargetOpcode()) {4454 const SelectionDAGTargetInfo &TSI = CurDAG->getSelectionDAGInfo();4455 return TSI.mayRaiseFPException(N->getOpcode());4456 }4457 return N->isStrictFPOpcode();4458}4459 4460bool SelectionDAGISel::isOrEquivalentToAdd(const SDNode *N) const {4461 assert(N->getOpcode() == ISD::OR && "Unexpected opcode");4462 auto *C = dyn_cast<ConstantSDNode>(N->getOperand(1));4463 if (!C)4464 return false;4465 4466 // Detect when "or" is used to add an offset to a stack object.4467 if (auto *FN = dyn_cast<FrameIndexSDNode>(N->getOperand(0))) {4468 MachineFrameInfo &MFI = MF->getFrameInfo();4469 Align A = MFI.getObjectAlign(FN->getIndex());4470 int32_t Off = C->getSExtValue();4471 // If the alleged offset fits in the zero bits guaranteed by4472 // the alignment, then this or is really an add.4473 return (Off >= 0) && (((A.value() - 1) & Off) == unsigned(Off));4474 }4475 return false;4476}4477 4478void SelectionDAGISel::CannotYetSelect(SDNode *N) {4479 std::string msg;4480 raw_string_ostream Msg(msg);4481 Msg << "Cannot select: ";4482 4483 Msg.enable_colors(errs().has_colors());4484 4485 if (N->getOpcode() != ISD::INTRINSIC_W_CHAIN &&4486 N->getOpcode() != ISD::INTRINSIC_WO_CHAIN &&4487 N->getOpcode() != ISD::INTRINSIC_VOID) {4488 N->printrFull(Msg, CurDAG);4489 Msg << "\nIn function: " << MF->getName();4490 } else {4491 bool HasInputChain = N->getOperand(0).getValueType() == MVT::Other;4492 unsigned iid = N->getConstantOperandVal(HasInputChain);4493 if (iid < Intrinsic::num_intrinsics)4494 Msg << "intrinsic %" << Intrinsic::getBaseName((Intrinsic::ID)iid);4495 else4496 Msg << "unknown intrinsic #" << iid;4497 }4498 report_fatal_error(Twine(msg));4499}4500