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-exception 6 // 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/BranchProbabilityInfo.h" 26 #include "llvm/Analysis/CFG.h" 27 #include "llvm/Analysis/EHPersonalities.h" 28 #include "llvm/Analysis/LazyBlockFrequencyInfo.h" 29 #include "llvm/Analysis/LegacyDivergenceAnalysis.h" 30 #include "llvm/Analysis/LoopInfo.h" 31 #include "llvm/Analysis/OptimizationRemarkEmitter.h" 32 #include "llvm/Analysis/ProfileSummaryInfo.h" 33 #include "llvm/Analysis/TargetLibraryInfo.h" 34 #include "llvm/Analysis/TargetTransformInfo.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/StackProtector.h" 55 #include "llvm/CodeGen/SwiftErrorValueTracking.h" 56 #include "llvm/CodeGen/TargetInstrInfo.h" 57 #include "llvm/CodeGen/TargetLowering.h" 58 #include "llvm/CodeGen/TargetRegisterInfo.h" 59 #include "llvm/CodeGen/TargetSubtargetInfo.h" 60 #include "llvm/CodeGen/ValueTypes.h" 61 #include "llvm/IR/BasicBlock.h" 62 #include "llvm/IR/Constants.h" 63 #include "llvm/IR/DataLayout.h" 64 #include "llvm/IR/DebugInfoMetadata.h" 65 #include "llvm/IR/DebugLoc.h" 66 #include "llvm/IR/DiagnosticInfo.h" 67 #include "llvm/IR/Dominators.h" 68 #include "llvm/IR/Function.h" 69 #include "llvm/IR/InlineAsm.h" 70 #include "llvm/IR/InstIterator.h" 71 #include "llvm/IR/Instruction.h" 72 #include "llvm/IR/Instructions.h" 73 #include "llvm/IR/IntrinsicInst.h" 74 #include "llvm/IR/Intrinsics.h" 75 #include "llvm/IR/IntrinsicsWebAssembly.h" 76 #include "llvm/IR/Metadata.h" 77 #include "llvm/IR/Statepoint.h" 78 #include "llvm/IR/Type.h" 79 #include "llvm/IR/User.h" 80 #include "llvm/IR/Value.h" 81 #include "llvm/InitializePasses.h" 82 #include "llvm/MC/MCInstrDesc.h" 83 #include "llvm/Pass.h" 84 #include "llvm/Support/BranchProbability.h" 85 #include "llvm/Support/Casting.h" 86 #include "llvm/Support/CodeGen.h" 87 #include "llvm/Support/CommandLine.h" 88 #include "llvm/Support/Compiler.h" 89 #include "llvm/Support/Debug.h" 90 #include "llvm/Support/ErrorHandling.h" 91 #include "llvm/Support/KnownBits.h" 92 #include "llvm/Support/MachineValueType.h" 93 #include "llvm/Support/Timer.h" 94 #include "llvm/Support/raw_ostream.h" 95 #include "llvm/Target/TargetIntrinsicInfo.h" 96 #include "llvm/Target/TargetMachine.h" 97 #include "llvm/Target/TargetOptions.h" 98 #include "llvm/Transforms/Utils/BasicBlockUtils.h" 99 #include <algorithm> 100 #include <cassert> 101 #include <cstdint> 102 #include <iterator> 103 #include <limits> 104 #include <memory> 105 #include <string> 106 #include <utility> 107 #include <vector> 108 109 using namespace llvm; 110 111 #define DEBUG_TYPE "isel" 112 113 STATISTIC(NumFastIselFailures, "Number of instructions fast isel failed on"); 114 STATISTIC(NumFastIselSuccess, "Number of instructions fast isel selected"); 115 STATISTIC(NumFastIselBlocks, "Number of blocks selected entirely by fast isel"); 116 STATISTIC(NumDAGBlocks, "Number of blocks selected using DAG"); 117 STATISTIC(NumDAGIselRetries,"Number of times dag isel has to try another path"); 118 STATISTIC(NumEntryBlocks, "Number of entry blocks encountered"); 119 STATISTIC(NumFastIselFailLowerArguments, 120 "Number of entry blocks where fast isel failed to lower arguments"); 121 122 static cl::opt<int> EnableFastISelAbort( 123 "fast-isel-abort", cl::Hidden, 124 cl::desc("Enable abort calls when \"fast\" instruction selection " 125 "fails to lower an instruction: 0 disable the abort, 1 will " 126 "abort but for args, calls and terminators, 2 will also " 127 "abort for argument lowering, and 3 will never fallback " 128 "to SelectionDAG.")); 129 130 static cl::opt<bool> EnableFastISelFallbackReport( 131 "fast-isel-report-on-fallback", cl::Hidden, 132 cl::desc("Emit a diagnostic when \"fast\" instruction selection " 133 "falls back to SelectionDAG.")); 134 135 static cl::opt<bool> 136 UseMBPI("use-mbpi", 137 cl::desc("use Machine Branch Probability Info"), 138 cl::init(true), cl::Hidden); 139 140 #ifndef NDEBUG 141 static cl::opt<std::string> 142 FilterDAGBasicBlockName("filter-view-dags", cl::Hidden, 143 cl::desc("Only display the basic block whose name " 144 "matches this for all view-*-dags options")); 145 static cl::opt<bool> 146 ViewDAGCombine1("view-dag-combine1-dags", cl::Hidden, 147 cl::desc("Pop up a window to show dags before the first " 148 "dag combine pass")); 149 static cl::opt<bool> 150 ViewLegalizeTypesDAGs("view-legalize-types-dags", cl::Hidden, 151 cl::desc("Pop up a window to show dags before legalize types")); 152 static cl::opt<bool> 153 ViewDAGCombineLT("view-dag-combine-lt-dags", cl::Hidden, 154 cl::desc("Pop up a window to show dags before the post " 155 "legalize types dag combine pass")); 156 static cl::opt<bool> 157 ViewLegalizeDAGs("view-legalize-dags", cl::Hidden, 158 cl::desc("Pop up a window to show dags before legalize")); 159 static cl::opt<bool> 160 ViewDAGCombine2("view-dag-combine2-dags", cl::Hidden, 161 cl::desc("Pop up a window to show dags before the second " 162 "dag combine pass")); 163 static cl::opt<bool> 164 ViewISelDAGs("view-isel-dags", cl::Hidden, 165 cl::desc("Pop up a window to show isel dags as they are selected")); 166 static cl::opt<bool> 167 ViewSchedDAGs("view-sched-dags", cl::Hidden, 168 cl::desc("Pop up a window to show sched dags as they are processed")); 169 static cl::opt<bool> 170 ViewSUnitDAGs("view-sunit-dags", cl::Hidden, 171 cl::desc("Pop up a window to show SUnit dags after they are processed")); 172 #else 173 static const bool ViewDAGCombine1 = false, ViewLegalizeTypesDAGs = false, 174 ViewDAGCombineLT = false, ViewLegalizeDAGs = false, 175 ViewDAGCombine2 = false, ViewISelDAGs = false, 176 ViewSchedDAGs = false, ViewSUnitDAGs = false; 177 #endif 178 179 //===---------------------------------------------------------------------===// 180 /// 181 /// RegisterScheduler class - Track the registration of instruction schedulers. 182 /// 183 //===---------------------------------------------------------------------===// 184 MachinePassRegistry<RegisterScheduler::FunctionPassCtor> 185 RegisterScheduler::Registry; 186 187 //===---------------------------------------------------------------------===// 188 /// 189 /// ISHeuristic command line option for instruction schedulers. 190 /// 191 //===---------------------------------------------------------------------===// 192 static cl::opt<RegisterScheduler::FunctionPassCtor, false, 193 RegisterPassParser<RegisterScheduler>> 194 ISHeuristic("pre-RA-sched", 195 cl::init(&createDefaultScheduler), cl::Hidden, 196 cl::desc("Instruction schedulers available (before register" 197 " allocation):")); 198 199 static RegisterScheduler 200 defaultListDAGScheduler("default", "Best scheduler for the target", 201 createDefaultScheduler); 202 203 namespace llvm { 204 205 //===--------------------------------------------------------------------===// 206 /// This class is used by SelectionDAGISel to temporarily override 207 /// the optimization level on a per-function basis. 208 class OptLevelChanger { 209 SelectionDAGISel &IS; 210 CodeGenOpt::Level SavedOptLevel; 211 bool SavedFastISel; 212 213 public: 214 OptLevelChanger(SelectionDAGISel &ISel, 215 CodeGenOpt::Level NewOptLevel) : IS(ISel) { 216 SavedOptLevel = IS.OptLevel; 217 SavedFastISel = IS.TM.Options.EnableFastISel; 218 if (NewOptLevel == SavedOptLevel) 219 return; 220 IS.OptLevel = NewOptLevel; 221 IS.TM.setOptLevel(NewOptLevel); 222 LLVM_DEBUG(dbgs() << "\nChanging optimization level for Function " 223 << IS.MF->getFunction().getName() << "\n"); 224 LLVM_DEBUG(dbgs() << "\tBefore: -O" << SavedOptLevel << " ; After: -O" 225 << NewOptLevel << "\n"); 226 if (NewOptLevel == CodeGenOpt::None) { 227 IS.TM.setFastISel(IS.TM.getO0WantsFastISel()); 228 LLVM_DEBUG( 229 dbgs() << "\tFastISel is " 230 << (IS.TM.Options.EnableFastISel ? "enabled" : "disabled") 231 << "\n"); 232 } 233 } 234 235 ~OptLevelChanger() { 236 if (IS.OptLevel == SavedOptLevel) 237 return; 238 LLVM_DEBUG(dbgs() << "\nRestoring optimization level for Function " 239 << IS.MF->getFunction().getName() << "\n"); 240 LLVM_DEBUG(dbgs() << "\tBefore: -O" << IS.OptLevel << " ; After: -O" 241 << SavedOptLevel << "\n"); 242 IS.OptLevel = SavedOptLevel; 243 IS.TM.setOptLevel(SavedOptLevel); 244 IS.TM.setFastISel(SavedFastISel); 245 } 246 }; 247 248 //===--------------------------------------------------------------------===// 249 /// createDefaultScheduler - This creates an instruction scheduler appropriate 250 /// for the target. 251 ScheduleDAGSDNodes* createDefaultScheduler(SelectionDAGISel *IS, 252 CodeGenOpt::Level OptLevel) { 253 const TargetLowering *TLI = IS->TLI; 254 const TargetSubtargetInfo &ST = IS->MF->getSubtarget(); 255 256 // Try first to see if the Target has its own way of selecting a scheduler 257 if (auto *SchedulerCtor = ST.getDAGScheduler(OptLevel)) { 258 return SchedulerCtor(IS, OptLevel); 259 } 260 261 if (OptLevel == CodeGenOpt::None || 262 (ST.enableMachineScheduler() && ST.enableMachineSchedDefaultSched()) || 263 TLI->getSchedulingPreference() == Sched::Source) 264 return createSourceListDAGScheduler(IS, OptLevel); 265 if (TLI->getSchedulingPreference() == Sched::RegPressure) 266 return createBURRListDAGScheduler(IS, OptLevel); 267 if (TLI->getSchedulingPreference() == Sched::Hybrid) 268 return createHybridListDAGScheduler(IS, OptLevel); 269 if (TLI->getSchedulingPreference() == Sched::VLIW) 270 return createVLIWDAGScheduler(IS, OptLevel); 271 if (TLI->getSchedulingPreference() == Sched::Fast) 272 return createFastDAGScheduler(IS, OptLevel); 273 if (TLI->getSchedulingPreference() == Sched::Linearize) 274 return createDAGLinearizer(IS, OptLevel); 275 assert(TLI->getSchedulingPreference() == Sched::ILP && 276 "Unknown sched type!"); 277 return createILPListDAGScheduler(IS, OptLevel); 278 } 279 280 } // end namespace llvm 281 282 // EmitInstrWithCustomInserter - This method should be implemented by targets 283 // that mark instructions with the 'usesCustomInserter' flag. These 284 // instructions are special in various ways, which require special support to 285 // insert. The specified MachineInstr is created but not inserted into any 286 // basic blocks, and this method is called to expand it into a sequence of 287 // instructions, potentially also creating new basic blocks and control flow. 288 // When new basic blocks are inserted and the edges from MBB to its successors 289 // are modified, the method should insert pairs of <OldSucc, NewSucc> into the 290 // DenseMap. 291 MachineBasicBlock * 292 TargetLowering::EmitInstrWithCustomInserter(MachineInstr &MI, 293 MachineBasicBlock *MBB) const { 294 #ifndef NDEBUG 295 dbgs() << "If a target marks an instruction with " 296 "'usesCustomInserter', it must implement " 297 "TargetLowering::EmitInstrWithCustomInserter!\n"; 298 #endif 299 llvm_unreachable(nullptr); 300 } 301 302 void TargetLowering::AdjustInstrPostInstrSelection(MachineInstr &MI, 303 SDNode *Node) const { 304 assert(!MI.hasPostISelHook() && 305 "If a target marks an instruction with 'hasPostISelHook', " 306 "it must implement TargetLowering::AdjustInstrPostInstrSelection!"); 307 } 308 309 //===----------------------------------------------------------------------===// 310 // SelectionDAGISel code 311 //===----------------------------------------------------------------------===// 312 313 SelectionDAGISel::SelectionDAGISel(TargetMachine &tm, CodeGenOpt::Level OL) 314 : MachineFunctionPass(ID), TM(tm), FuncInfo(new FunctionLoweringInfo()), 315 SwiftError(new SwiftErrorValueTracking()), 316 CurDAG(new SelectionDAG(tm, OL)), 317 SDB(std::make_unique<SelectionDAGBuilder>(*CurDAG, *FuncInfo, *SwiftError, 318 OL)), 319 OptLevel(OL) { 320 initializeGCModuleInfoPass(*PassRegistry::getPassRegistry()); 321 initializeBranchProbabilityInfoWrapperPassPass( 322 *PassRegistry::getPassRegistry()); 323 initializeAAResultsWrapperPassPass(*PassRegistry::getPassRegistry()); 324 initializeTargetLibraryInfoWrapperPassPass(*PassRegistry::getPassRegistry()); 325 } 326 327 SelectionDAGISel::~SelectionDAGISel() { 328 delete CurDAG; 329 delete SwiftError; 330 } 331 332 void SelectionDAGISel::getAnalysisUsage(AnalysisUsage &AU) const { 333 if (OptLevel != CodeGenOpt::None) 334 AU.addRequired<AAResultsWrapperPass>(); 335 AU.addRequired<GCModuleInfo>(); 336 AU.addRequired<StackProtector>(); 337 AU.addPreserved<GCModuleInfo>(); 338 AU.addRequired<TargetLibraryInfoWrapperPass>(); 339 AU.addRequired<TargetTransformInfoWrapperPass>(); 340 if (UseMBPI && OptLevel != CodeGenOpt::None) 341 AU.addRequired<BranchProbabilityInfoWrapperPass>(); 342 AU.addRequired<ProfileSummaryInfoWrapperPass>(); 343 if (OptLevel != CodeGenOpt::None) 344 LazyBlockFrequencyInfoPass::getLazyBFIAnalysisUsage(AU); 345 MachineFunctionPass::getAnalysisUsage(AU); 346 } 347 348 /// SplitCriticalSideEffectEdges - Look for critical edges with a PHI value that 349 /// may trap on it. In this case we have to split the edge so that the path 350 /// through the predecessor block that doesn't go to the phi block doesn't 351 /// execute the possibly trapping instruction. If available, we pass domtree 352 /// and loop info to be updated when we split critical edges. This is because 353 /// SelectionDAGISel preserves these analyses. 354 /// This is required for correctness, so it must be done at -O0. 355 /// 356 static void SplitCriticalSideEffectEdges(Function &Fn, DominatorTree *DT, 357 LoopInfo *LI) { 358 // Loop for blocks with phi nodes. 359 for (BasicBlock &BB : Fn) { 360 PHINode *PN = dyn_cast<PHINode>(BB.begin()); 361 if (!PN) continue; 362 363 ReprocessBlock: 364 // For each block with a PHI node, check to see if any of the input values 365 // are potentially trapping constant expressions. Constant expressions are 366 // the only potentially trapping value that can occur as the argument to a 367 // PHI. 368 for (BasicBlock::iterator I = BB.begin(); (PN = dyn_cast<PHINode>(I)); ++I) 369 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { 370 Constant *C = dyn_cast<Constant>(PN->getIncomingValue(i)); 371 if (!C || !C->canTrap()) continue; 372 373 // The only case we have to worry about is when the edge is critical. 374 // Since this block has a PHI Node, we assume it has multiple input 375 // edges: check to see if the pred has multiple successors. 376 BasicBlock *Pred = PN->getIncomingBlock(i); 377 if (Pred->getTerminator()->getNumSuccessors() == 1) 378 continue; 379 380 // Okay, we have to split this edge. 381 SplitCriticalEdge( 382 Pred->getTerminator(), GetSuccessorNumber(Pred, &BB), 383 CriticalEdgeSplittingOptions(DT, LI).setMergeIdenticalEdges()); 384 goto ReprocessBlock; 385 } 386 } 387 } 388 389 static void computeUsesMSVCFloatingPoint(const Triple &TT, const Function &F, 390 MachineModuleInfo &MMI) { 391 // Only needed for MSVC 392 if (!TT.isWindowsMSVCEnvironment()) 393 return; 394 395 // If it's already set, nothing to do. 396 if (MMI.usesMSVCFloatingPoint()) 397 return; 398 399 for (const Instruction &I : instructions(F)) { 400 if (I.getType()->isFPOrFPVectorTy()) { 401 MMI.setUsesMSVCFloatingPoint(true); 402 return; 403 } 404 for (const auto &Op : I.operands()) { 405 if (Op->getType()->isFPOrFPVectorTy()) { 406 MMI.setUsesMSVCFloatingPoint(true); 407 return; 408 } 409 } 410 } 411 } 412 413 bool SelectionDAGISel::runOnMachineFunction(MachineFunction &mf) { 414 // If we already selected that function, we do not need to run SDISel. 415 if (mf.getProperties().hasProperty( 416 MachineFunctionProperties::Property::Selected)) 417 return false; 418 // Do some sanity-checking on the command-line options. 419 assert((!EnableFastISelAbort || TM.Options.EnableFastISel) && 420 "-fast-isel-abort > 0 requires -fast-isel"); 421 422 const Function &Fn = mf.getFunction(); 423 MF = &mf; 424 425 // Decide what flavour of variable location debug-info will be used, before 426 // we change the optimisation level. 427 UseInstrRefDebugInfo = mf.useDebugInstrRef(); 428 CurDAG->useInstrRefDebugInfo(UseInstrRefDebugInfo); 429 430 // Reset the target options before resetting the optimization 431 // level below. 432 // FIXME: This is a horrible hack and should be processed via 433 // codegen looking at the optimization level explicitly when 434 // it wants to look at it. 435 TM.resetTargetOptions(Fn); 436 // Reset OptLevel to None for optnone functions. 437 CodeGenOpt::Level NewOptLevel = OptLevel; 438 if (OptLevel != CodeGenOpt::None && skipFunction(Fn)) 439 NewOptLevel = CodeGenOpt::None; 440 OptLevelChanger OLC(*this, NewOptLevel); 441 442 TII = MF->getSubtarget().getInstrInfo(); 443 TLI = MF->getSubtarget().getTargetLowering(); 444 RegInfo = &MF->getRegInfo(); 445 LibInfo = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(Fn); 446 GFI = Fn.hasGC() ? &getAnalysis<GCModuleInfo>().getFunctionInfo(Fn) : nullptr; 447 ORE = std::make_unique<OptimizationRemarkEmitter>(&Fn); 448 auto *DTWP = getAnalysisIfAvailable<DominatorTreeWrapperPass>(); 449 DominatorTree *DT = DTWP ? &DTWP->getDomTree() : nullptr; 450 auto *LIWP = getAnalysisIfAvailable<LoopInfoWrapperPass>(); 451 LoopInfo *LI = LIWP ? &LIWP->getLoopInfo() : nullptr; 452 auto *PSI = &getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI(); 453 BlockFrequencyInfo *BFI = nullptr; 454 if (PSI && PSI->hasProfileSummary() && OptLevel != CodeGenOpt::None) 455 BFI = &getAnalysis<LazyBlockFrequencyInfoPass>().getBFI(); 456 457 LLVM_DEBUG(dbgs() << "\n\n\n=== " << Fn.getName() << "\n"); 458 459 SplitCriticalSideEffectEdges(const_cast<Function &>(Fn), DT, LI); 460 461 CurDAG->init(*MF, *ORE, this, LibInfo, 462 getAnalysisIfAvailable<LegacyDivergenceAnalysis>(), PSI, BFI); 463 FuncInfo->set(Fn, *MF, CurDAG); 464 SwiftError->setFunction(*MF); 465 466 // Now get the optional analyzes if we want to. 467 // This is based on the possibly changed OptLevel (after optnone is taken 468 // into account). That's unfortunate but OK because it just means we won't 469 // ask for passes that have been required anyway. 470 471 if (UseMBPI && OptLevel != CodeGenOpt::None) 472 FuncInfo->BPI = &getAnalysis<BranchProbabilityInfoWrapperPass>().getBPI(); 473 else 474 FuncInfo->BPI = nullptr; 475 476 if (OptLevel != CodeGenOpt::None) 477 AA = &getAnalysis<AAResultsWrapperPass>().getAAResults(); 478 else 479 AA = nullptr; 480 481 SDB->init(GFI, AA, LibInfo); 482 483 MF->setHasInlineAsm(false); 484 485 FuncInfo->SplitCSR = false; 486 487 // We split CSR if the target supports it for the given function 488 // and the function has only return exits. 489 if (OptLevel != CodeGenOpt::None && TLI->supportSplitCSR(MF)) { 490 FuncInfo->SplitCSR = true; 491 492 // Collect all the return blocks. 493 for (const BasicBlock &BB : Fn) { 494 if (!succ_empty(&BB)) 495 continue; 496 497 const Instruction *Term = BB.getTerminator(); 498 if (isa<UnreachableInst>(Term) || isa<ReturnInst>(Term)) 499 continue; 500 501 // Bail out if the exit block is not Return nor Unreachable. 502 FuncInfo->SplitCSR = false; 503 break; 504 } 505 } 506 507 MachineBasicBlock *EntryMBB = &MF->front(); 508 if (FuncInfo->SplitCSR) 509 // This performs initialization so lowering for SplitCSR will be correct. 510 TLI->initializeSplitCSR(EntryMBB); 511 512 SelectAllBasicBlocks(Fn); 513 if (FastISelFailed && EnableFastISelFallbackReport) { 514 DiagnosticInfoISelFallback DiagFallback(Fn); 515 Fn.getContext().diagnose(DiagFallback); 516 } 517 518 // Replace forward-declared registers with the registers containing 519 // the desired value. 520 // Note: it is important that this happens **before** the call to 521 // EmitLiveInCopies, since implementations can skip copies of unused 522 // registers. If we don't apply the reg fixups before, some registers may 523 // appear as unused and will be skipped, resulting in bad MI. 524 MachineRegisterInfo &MRI = MF->getRegInfo(); 525 for (DenseMap<Register, Register>::iterator I = FuncInfo->RegFixups.begin(), 526 E = FuncInfo->RegFixups.end(); 527 I != E; ++I) { 528 Register From = I->first; 529 Register To = I->second; 530 // If To is also scheduled to be replaced, find what its ultimate 531 // replacement is. 532 while (true) { 533 DenseMap<Register, Register>::iterator J = FuncInfo->RegFixups.find(To); 534 if (J == E) 535 break; 536 To = J->second; 537 } 538 // Make sure the new register has a sufficiently constrained register class. 539 if (Register::isVirtualRegister(From) && Register::isVirtualRegister(To)) 540 MRI.constrainRegClass(To, MRI.getRegClass(From)); 541 // Replace it. 542 543 // Replacing one register with another won't touch the kill flags. 544 // We need to conservatively clear the kill flags as a kill on the old 545 // register might dominate existing uses of the new register. 546 if (!MRI.use_empty(To)) 547 MRI.clearKillFlags(From); 548 MRI.replaceRegWith(From, To); 549 } 550 551 // If the first basic block in the function has live ins that need to be 552 // copied into vregs, emit the copies into the top of the block before 553 // emitting the code for the block. 554 const TargetRegisterInfo &TRI = *MF->getSubtarget().getRegisterInfo(); 555 RegInfo->EmitLiveInCopies(EntryMBB, TRI, *TII); 556 557 // Insert copies in the entry block and the return blocks. 558 if (FuncInfo->SplitCSR) { 559 SmallVector<MachineBasicBlock*, 4> Returns; 560 // Collect all the return blocks. 561 for (MachineBasicBlock &MBB : mf) { 562 if (!MBB.succ_empty()) 563 continue; 564 565 MachineBasicBlock::iterator Term = MBB.getFirstTerminator(); 566 if (Term != MBB.end() && Term->isReturn()) { 567 Returns.push_back(&MBB); 568 continue; 569 } 570 } 571 TLI->insertCopiesSplitCSR(EntryMBB, Returns); 572 } 573 574 DenseMap<unsigned, unsigned> LiveInMap; 575 if (!FuncInfo->ArgDbgValues.empty()) 576 for (std::pair<unsigned, unsigned> LI : RegInfo->liveins()) 577 if (LI.second) 578 LiveInMap.insert(LI); 579 580 // Insert DBG_VALUE instructions for function arguments to the entry block. 581 bool InstrRef = MF->useDebugInstrRef(); 582 for (unsigned i = 0, e = FuncInfo->ArgDbgValues.size(); i != e; ++i) { 583 MachineInstr *MI = FuncInfo->ArgDbgValues[e - i - 1]; 584 assert(MI->getOpcode() != TargetOpcode::DBG_VALUE_LIST && 585 "Function parameters should not be described by DBG_VALUE_LIST."); 586 bool hasFI = MI->getOperand(0).isFI(); 587 Register Reg = 588 hasFI ? TRI.getFrameRegister(*MF) : MI->getOperand(0).getReg(); 589 if (Register::isPhysicalRegister(Reg)) 590 EntryMBB->insert(EntryMBB->begin(), MI); 591 else { 592 MachineInstr *Def = RegInfo->getVRegDef(Reg); 593 if (Def) { 594 MachineBasicBlock::iterator InsertPos = Def; 595 // FIXME: VR def may not be in entry block. 596 Def->getParent()->insert(std::next(InsertPos), MI); 597 } else 598 LLVM_DEBUG(dbgs() << "Dropping debug info for dead vreg" 599 << Register::virtReg2Index(Reg) << "\n"); 600 } 601 602 // Don't try and extend through copies in instruction referencing mode. 603 if (InstrRef) 604 continue; 605 606 // If Reg is live-in then update debug info to track its copy in a vreg. 607 DenseMap<unsigned, unsigned>::iterator LDI = LiveInMap.find(Reg); 608 if (LDI != LiveInMap.end()) { 609 assert(!hasFI && "There's no handling of frame pointer updating here yet " 610 "- add if needed"); 611 MachineInstr *Def = RegInfo->getVRegDef(LDI->second); 612 MachineBasicBlock::iterator InsertPos = Def; 613 const MDNode *Variable = MI->getDebugVariable(); 614 const MDNode *Expr = MI->getDebugExpression(); 615 DebugLoc DL = MI->getDebugLoc(); 616 bool IsIndirect = MI->isIndirectDebugValue(); 617 if (IsIndirect) 618 assert(MI->getOperand(1).getImm() == 0 && 619 "DBG_VALUE with nonzero offset"); 620 assert(cast<DILocalVariable>(Variable)->isValidLocationForIntrinsic(DL) && 621 "Expected inlined-at fields to agree"); 622 assert(MI->getOpcode() != TargetOpcode::DBG_VALUE_LIST && 623 "Didn't expect to see a DBG_VALUE_LIST here"); 624 // Def is never a terminator here, so it is ok to increment InsertPos. 625 BuildMI(*EntryMBB, ++InsertPos, DL, TII->get(TargetOpcode::DBG_VALUE), 626 IsIndirect, LDI->second, Variable, Expr); 627 628 // If this vreg is directly copied into an exported register then 629 // that COPY instructions also need DBG_VALUE, if it is the only 630 // user of LDI->second. 631 MachineInstr *CopyUseMI = nullptr; 632 for (MachineRegisterInfo::use_instr_iterator 633 UI = RegInfo->use_instr_begin(LDI->second), 634 E = RegInfo->use_instr_end(); UI != E; ) { 635 MachineInstr *UseMI = &*(UI++); 636 if (UseMI->isDebugValue()) continue; 637 if (UseMI->isCopy() && !CopyUseMI && UseMI->getParent() == EntryMBB) { 638 CopyUseMI = UseMI; continue; 639 } 640 // Otherwise this is another use or second copy use. 641 CopyUseMI = nullptr; break; 642 } 643 if (CopyUseMI && 644 TRI.getRegSizeInBits(LDI->second, MRI) == 645 TRI.getRegSizeInBits(CopyUseMI->getOperand(0).getReg(), MRI)) { 646 // Use MI's debug location, which describes where Variable was 647 // declared, rather than whatever is attached to CopyUseMI. 648 MachineInstr *NewMI = 649 BuildMI(*MF, DL, TII->get(TargetOpcode::DBG_VALUE), IsIndirect, 650 CopyUseMI->getOperand(0).getReg(), Variable, Expr); 651 MachineBasicBlock::iterator Pos = CopyUseMI; 652 EntryMBB->insertAfter(Pos, NewMI); 653 } 654 } 655 } 656 657 // For debug-info, in instruction referencing mode, we need to perform some 658 // post-isel maintenence. 659 if (UseInstrRefDebugInfo) 660 MF->finalizeDebugInstrRefs(); 661 662 // Determine if there are any calls in this machine function. 663 MachineFrameInfo &MFI = MF->getFrameInfo(); 664 for (const auto &MBB : *MF) { 665 if (MFI.hasCalls() && MF->hasInlineAsm()) 666 break; 667 668 for (const auto &MI : MBB) { 669 const MCInstrDesc &MCID = TII->get(MI.getOpcode()); 670 if ((MCID.isCall() && !MCID.isReturn()) || 671 MI.isStackAligningInlineAsm()) { 672 MFI.setHasCalls(true); 673 } 674 if (MI.isInlineAsm()) { 675 MF->setHasInlineAsm(true); 676 } 677 } 678 } 679 680 // Determine if there is a call to setjmp in the machine function. 681 MF->setExposesReturnsTwice(Fn.callsFunctionThatReturnsTwice()); 682 683 // Determine if floating point is used for msvc 684 computeUsesMSVCFloatingPoint(TM.getTargetTriple(), Fn, MF->getMMI()); 685 686 // Release function-specific state. SDB and CurDAG are already cleared 687 // at this point. 688 FuncInfo->clear(); 689 690 LLVM_DEBUG(dbgs() << "*** MachineFunction at end of ISel ***\n"); 691 LLVM_DEBUG(MF->print(dbgs())); 692 693 return true; 694 } 695 696 static void reportFastISelFailure(MachineFunction &MF, 697 OptimizationRemarkEmitter &ORE, 698 OptimizationRemarkMissed &R, 699 bool ShouldAbort) { 700 // Print the function name explicitly if we don't have a debug location (which 701 // makes the diagnostic less useful) or if we're going to emit a raw error. 702 if (!R.getLocation().isValid() || ShouldAbort) 703 R << (" (in function: " + MF.getName() + ")").str(); 704 705 if (ShouldAbort) 706 report_fatal_error(Twine(R.getMsg())); 707 708 ORE.emit(R); 709 LLVM_DEBUG(dbgs() << R.getMsg() << "\n"); 710 } 711 712 void SelectionDAGISel::SelectBasicBlock(BasicBlock::const_iterator Begin, 713 BasicBlock::const_iterator End, 714 bool &HadTailCall) { 715 // Allow creating illegal types during DAG building for the basic block. 716 CurDAG->NewNodesMustHaveLegalTypes = false; 717 718 // Lower the instructions. If a call is emitted as a tail call, cease emitting 719 // nodes for this block. 720 for (BasicBlock::const_iterator I = Begin; I != End && !SDB->HasTailCall; ++I) { 721 if (!ElidedArgCopyInstrs.count(&*I)) 722 SDB->visit(*I); 723 } 724 725 // Make sure the root of the DAG is up-to-date. 726 CurDAG->setRoot(SDB->getControlRoot()); 727 HadTailCall = SDB->HasTailCall; 728 SDB->resolveOrClearDbgInfo(); 729 SDB->clear(); 730 731 // Final step, emit the lowered DAG as machine code. 732 CodeGenAndEmitDAG(); 733 } 734 735 void SelectionDAGISel::ComputeLiveOutVRegInfo() { 736 SmallPtrSet<SDNode *, 16> Added; 737 SmallVector<SDNode*, 128> Worklist; 738 739 Worklist.push_back(CurDAG->getRoot().getNode()); 740 Added.insert(CurDAG->getRoot().getNode()); 741 742 KnownBits Known; 743 744 do { 745 SDNode *N = Worklist.pop_back_val(); 746 747 // Otherwise, add all chain operands to the worklist. 748 for (const SDValue &Op : N->op_values()) 749 if (Op.getValueType() == MVT::Other && Added.insert(Op.getNode()).second) 750 Worklist.push_back(Op.getNode()); 751 752 // If this is a CopyToReg with a vreg dest, process it. 753 if (N->getOpcode() != ISD::CopyToReg) 754 continue; 755 756 unsigned DestReg = cast<RegisterSDNode>(N->getOperand(1))->getReg(); 757 if (!Register::isVirtualRegister(DestReg)) 758 continue; 759 760 // Ignore non-integer values. 761 SDValue Src = N->getOperand(2); 762 EVT SrcVT = Src.getValueType(); 763 if (!SrcVT.isInteger()) 764 continue; 765 766 unsigned NumSignBits = CurDAG->ComputeNumSignBits(Src); 767 Known = CurDAG->computeKnownBits(Src); 768 FuncInfo->AddLiveOutRegInfo(DestReg, NumSignBits, Known); 769 } while (!Worklist.empty()); 770 } 771 772 void SelectionDAGISel::CodeGenAndEmitDAG() { 773 StringRef GroupName = "sdag"; 774 StringRef GroupDescription = "Instruction Selection and Scheduling"; 775 std::string BlockName; 776 bool MatchFilterBB = false; (void)MatchFilterBB; 777 #ifndef NDEBUG 778 TargetTransformInfo &TTI = 779 getAnalysis<TargetTransformInfoWrapperPass>().getTTI(*FuncInfo->Fn); 780 #endif 781 782 // Pre-type legalization allow creation of any node types. 783 CurDAG->NewNodesMustHaveLegalTypes = false; 784 785 #ifndef NDEBUG 786 MatchFilterBB = (FilterDAGBasicBlockName.empty() || 787 FilterDAGBasicBlockName == 788 FuncInfo->MBB->getBasicBlock()->getName()); 789 #endif 790 #ifdef NDEBUG 791 if (ViewDAGCombine1 || ViewLegalizeTypesDAGs || ViewDAGCombineLT || 792 ViewLegalizeDAGs || ViewDAGCombine2 || ViewISelDAGs || ViewSchedDAGs || 793 ViewSUnitDAGs) 794 #endif 795 { 796 BlockName = 797 (MF->getName() + ":" + FuncInfo->MBB->getBasicBlock()->getName()).str(); 798 } 799 LLVM_DEBUG(dbgs() << "Initial selection DAG: " 800 << printMBBReference(*FuncInfo->MBB) << " '" << BlockName 801 << "'\n"; 802 CurDAG->dump()); 803 804 #ifndef NDEBUG 805 if (TTI.hasBranchDivergence()) 806 CurDAG->VerifyDAGDivergence(); 807 #endif 808 809 if (ViewDAGCombine1 && MatchFilterBB) 810 CurDAG->viewGraph("dag-combine1 input for " + BlockName); 811 812 // Run the DAG combiner in pre-legalize mode. 813 { 814 NamedRegionTimer T("combine1", "DAG Combining 1", GroupName, 815 GroupDescription, TimePassesIsEnabled); 816 CurDAG->Combine(BeforeLegalizeTypes, AA, OptLevel); 817 } 818 819 LLVM_DEBUG(dbgs() << "Optimized lowered selection DAG: " 820 << printMBBReference(*FuncInfo->MBB) << " '" << BlockName 821 << "'\n"; 822 CurDAG->dump()); 823 824 #ifndef NDEBUG 825 if (TTI.hasBranchDivergence()) 826 CurDAG->VerifyDAGDivergence(); 827 #endif 828 829 // Second step, hack on the DAG until it only uses operations and types that 830 // the target supports. 831 if (ViewLegalizeTypesDAGs && MatchFilterBB) 832 CurDAG->viewGraph("legalize-types input for " + BlockName); 833 834 bool Changed; 835 { 836 NamedRegionTimer T("legalize_types", "Type Legalization", GroupName, 837 GroupDescription, TimePassesIsEnabled); 838 Changed = CurDAG->LegalizeTypes(); 839 } 840 841 LLVM_DEBUG(dbgs() << "Type-legalized selection DAG: " 842 << printMBBReference(*FuncInfo->MBB) << " '" << BlockName 843 << "'\n"; 844 CurDAG->dump()); 845 846 #ifndef NDEBUG 847 if (TTI.hasBranchDivergence()) 848 CurDAG->VerifyDAGDivergence(); 849 #endif 850 851 // Only allow creation of legal node types. 852 CurDAG->NewNodesMustHaveLegalTypes = true; 853 854 if (Changed) { 855 if (ViewDAGCombineLT && MatchFilterBB) 856 CurDAG->viewGraph("dag-combine-lt input for " + BlockName); 857 858 // Run the DAG combiner in post-type-legalize mode. 859 { 860 NamedRegionTimer T("combine_lt", "DAG Combining after legalize types", 861 GroupName, GroupDescription, TimePassesIsEnabled); 862 CurDAG->Combine(AfterLegalizeTypes, AA, OptLevel); 863 } 864 865 LLVM_DEBUG(dbgs() << "Optimized type-legalized selection DAG: " 866 << printMBBReference(*FuncInfo->MBB) << " '" << BlockName 867 << "'\n"; 868 CurDAG->dump()); 869 870 #ifndef NDEBUG 871 if (TTI.hasBranchDivergence()) 872 CurDAG->VerifyDAGDivergence(); 873 #endif 874 } 875 876 { 877 NamedRegionTimer T("legalize_vec", "Vector Legalization", GroupName, 878 GroupDescription, TimePassesIsEnabled); 879 Changed = CurDAG->LegalizeVectors(); 880 } 881 882 if (Changed) { 883 LLVM_DEBUG(dbgs() << "Vector-legalized selection DAG: " 884 << printMBBReference(*FuncInfo->MBB) << " '" << BlockName 885 << "'\n"; 886 CurDAG->dump()); 887 888 #ifndef NDEBUG 889 if (TTI.hasBranchDivergence()) 890 CurDAG->VerifyDAGDivergence(); 891 #endif 892 893 { 894 NamedRegionTimer T("legalize_types2", "Type Legalization 2", GroupName, 895 GroupDescription, TimePassesIsEnabled); 896 CurDAG->LegalizeTypes(); 897 } 898 899 LLVM_DEBUG(dbgs() << "Vector/type-legalized selection DAG: " 900 << printMBBReference(*FuncInfo->MBB) << " '" << BlockName 901 << "'\n"; 902 CurDAG->dump()); 903 904 #ifndef NDEBUG 905 if (TTI.hasBranchDivergence()) 906 CurDAG->VerifyDAGDivergence(); 907 #endif 908 909 if (ViewDAGCombineLT && MatchFilterBB) 910 CurDAG->viewGraph("dag-combine-lv input for " + BlockName); 911 912 // Run the DAG combiner in post-type-legalize mode. 913 { 914 NamedRegionTimer T("combine_lv", "DAG Combining after legalize vectors", 915 GroupName, GroupDescription, TimePassesIsEnabled); 916 CurDAG->Combine(AfterLegalizeVectorOps, AA, OptLevel); 917 } 918 919 LLVM_DEBUG(dbgs() << "Optimized vector-legalized selection DAG: " 920 << printMBBReference(*FuncInfo->MBB) << " '" << BlockName 921 << "'\n"; 922 CurDAG->dump()); 923 924 #ifndef NDEBUG 925 if (TTI.hasBranchDivergence()) 926 CurDAG->VerifyDAGDivergence(); 927 #endif 928 } 929 930 if (ViewLegalizeDAGs && MatchFilterBB) 931 CurDAG->viewGraph("legalize input for " + BlockName); 932 933 { 934 NamedRegionTimer T("legalize", "DAG Legalization", GroupName, 935 GroupDescription, TimePassesIsEnabled); 936 CurDAG->Legalize(); 937 } 938 939 LLVM_DEBUG(dbgs() << "Legalized selection DAG: " 940 << printMBBReference(*FuncInfo->MBB) << " '" << BlockName 941 << "'\n"; 942 CurDAG->dump()); 943 944 #ifndef NDEBUG 945 if (TTI.hasBranchDivergence()) 946 CurDAG->VerifyDAGDivergence(); 947 #endif 948 949 if (ViewDAGCombine2 && MatchFilterBB) 950 CurDAG->viewGraph("dag-combine2 input for " + BlockName); 951 952 // Run the DAG combiner in post-legalize mode. 953 { 954 NamedRegionTimer T("combine2", "DAG Combining 2", GroupName, 955 GroupDescription, TimePassesIsEnabled); 956 CurDAG->Combine(AfterLegalizeDAG, AA, OptLevel); 957 } 958 959 LLVM_DEBUG(dbgs() << "Optimized legalized selection DAG: " 960 << printMBBReference(*FuncInfo->MBB) << " '" << BlockName 961 << "'\n"; 962 CurDAG->dump()); 963 964 #ifndef NDEBUG 965 if (TTI.hasBranchDivergence()) 966 CurDAG->VerifyDAGDivergence(); 967 #endif 968 969 if (OptLevel != CodeGenOpt::None) 970 ComputeLiveOutVRegInfo(); 971 972 if (ViewISelDAGs && MatchFilterBB) 973 CurDAG->viewGraph("isel input for " + BlockName); 974 975 // Third, instruction select all of the operations to machine code, adding the 976 // code to the MachineBasicBlock. 977 { 978 NamedRegionTimer T("isel", "Instruction Selection", GroupName, 979 GroupDescription, TimePassesIsEnabled); 980 DoInstructionSelection(); 981 } 982 983 LLVM_DEBUG(dbgs() << "Selected selection DAG: " 984 << printMBBReference(*FuncInfo->MBB) << " '" << BlockName 985 << "'\n"; 986 CurDAG->dump()); 987 988 if (ViewSchedDAGs && MatchFilterBB) 989 CurDAG->viewGraph("scheduler input for " + BlockName); 990 991 // Schedule machine code. 992 ScheduleDAGSDNodes *Scheduler = CreateScheduler(); 993 { 994 NamedRegionTimer T("sched", "Instruction Scheduling", GroupName, 995 GroupDescription, TimePassesIsEnabled); 996 Scheduler->Run(CurDAG, FuncInfo->MBB); 997 } 998 999 if (ViewSUnitDAGs && MatchFilterBB) 1000 Scheduler->viewGraph(); 1001 1002 // Emit machine code to BB. This can change 'BB' to the last block being 1003 // inserted into. 1004 MachineBasicBlock *FirstMBB = FuncInfo->MBB, *LastMBB; 1005 { 1006 NamedRegionTimer T("emit", "Instruction Creation", GroupName, 1007 GroupDescription, TimePassesIsEnabled); 1008 1009 // FuncInfo->InsertPt is passed by reference and set to the end of the 1010 // scheduled instructions. 1011 LastMBB = FuncInfo->MBB = Scheduler->EmitSchedule(FuncInfo->InsertPt); 1012 } 1013 1014 // If the block was split, make sure we update any references that are used to 1015 // update PHI nodes later on. 1016 if (FirstMBB != LastMBB) 1017 SDB->UpdateSplitBlock(FirstMBB, LastMBB); 1018 1019 // Free the scheduler state. 1020 { 1021 NamedRegionTimer T("cleanup", "Instruction Scheduling Cleanup", GroupName, 1022 GroupDescription, TimePassesIsEnabled); 1023 delete Scheduler; 1024 } 1025 1026 // Free the SelectionDAG state, now that we're finished with it. 1027 CurDAG->clear(); 1028 } 1029 1030 namespace { 1031 1032 /// ISelUpdater - helper class to handle updates of the instruction selection 1033 /// graph. 1034 class ISelUpdater : public SelectionDAG::DAGUpdateListener { 1035 SelectionDAG::allnodes_iterator &ISelPosition; 1036 1037 public: 1038 ISelUpdater(SelectionDAG &DAG, SelectionDAG::allnodes_iterator &isp) 1039 : SelectionDAG::DAGUpdateListener(DAG), ISelPosition(isp) {} 1040 1041 /// NodeDeleted - Handle nodes deleted from the graph. If the node being 1042 /// deleted is the current ISelPosition node, update ISelPosition. 1043 /// 1044 void NodeDeleted(SDNode *N, SDNode *E) override { 1045 if (ISelPosition == SelectionDAG::allnodes_iterator(N)) 1046 ++ISelPosition; 1047 } 1048 }; 1049 1050 } // end anonymous namespace 1051 1052 // This function is used to enforce the topological node id property 1053 // leveraged during instruction selection. Before the selection process all 1054 // nodes are given a non-negative id such that all nodes have a greater id than 1055 // their operands. As this holds transitively we can prune checks that a node N 1056 // is a predecessor of M another by not recursively checking through M's 1057 // operands if N's ID is larger than M's ID. This significantly improves 1058 // performance of various legality checks (e.g. IsLegalToFold / UpdateChains). 1059 1060 // However, when we fuse multiple nodes into a single node during the 1061 // selection we may induce a predecessor relationship between inputs and 1062 // outputs of distinct nodes being merged, violating the topological property. 1063 // Should a fused node have a successor which has yet to be selected, 1064 // our legality checks would be incorrect. To avoid this we mark all unselected 1065 // successor nodes, i.e. id != -1, as invalid for pruning by bit-negating (x => 1066 // (-(x+1))) the ids and modify our pruning check to ignore negative Ids of M. 1067 // We use bit-negation to more clearly enforce that node id -1 can only be 1068 // achieved by selected nodes. As the conversion is reversable to the original 1069 // Id, topological pruning can still be leveraged when looking for unselected 1070 // nodes. This method is called internally in all ISel replacement related 1071 // functions. 1072 void SelectionDAGISel::EnforceNodeIdInvariant(SDNode *Node) { 1073 SmallVector<SDNode *, 4> Nodes; 1074 Nodes.push_back(Node); 1075 1076 while (!Nodes.empty()) { 1077 SDNode *N = Nodes.pop_back_val(); 1078 for (auto *U : N->uses()) { 1079 auto UId = U->getNodeId(); 1080 if (UId > 0) { 1081 InvalidateNodeId(U); 1082 Nodes.push_back(U); 1083 } 1084 } 1085 } 1086 } 1087 1088 // InvalidateNodeId - As explained in EnforceNodeIdInvariant, mark a 1089 // NodeId with the equivalent node id which is invalid for topological 1090 // pruning. 1091 void SelectionDAGISel::InvalidateNodeId(SDNode *N) { 1092 int InvalidId = -(N->getNodeId() + 1); 1093 N->setNodeId(InvalidId); 1094 } 1095 1096 // getUninvalidatedNodeId - get original uninvalidated node id. 1097 int SelectionDAGISel::getUninvalidatedNodeId(SDNode *N) { 1098 int Id = N->getNodeId(); 1099 if (Id < -1) 1100 return -(Id + 1); 1101 return Id; 1102 } 1103 1104 void SelectionDAGISel::DoInstructionSelection() { 1105 LLVM_DEBUG(dbgs() << "===== Instruction selection begins: " 1106 << printMBBReference(*FuncInfo->MBB) << " '" 1107 << FuncInfo->MBB->getName() << "'\n"); 1108 1109 PreprocessISelDAG(); 1110 1111 // Select target instructions for the DAG. 1112 { 1113 // Number all nodes with a topological order and set DAGSize. 1114 DAGSize = CurDAG->AssignTopologicalOrder(); 1115 1116 // Create a dummy node (which is not added to allnodes), that adds 1117 // a reference to the root node, preventing it from being deleted, 1118 // and tracking any changes of the root. 1119 HandleSDNode Dummy(CurDAG->getRoot()); 1120 SelectionDAG::allnodes_iterator ISelPosition (CurDAG->getRoot().getNode()); 1121 ++ISelPosition; 1122 1123 // Make sure that ISelPosition gets properly updated when nodes are deleted 1124 // in calls made from this function. 1125 ISelUpdater ISU(*CurDAG, ISelPosition); 1126 1127 // The AllNodes list is now topological-sorted. Visit the 1128 // nodes by starting at the end of the list (the root of the 1129 // graph) and preceding back toward the beginning (the entry 1130 // node). 1131 while (ISelPosition != CurDAG->allnodes_begin()) { 1132 SDNode *Node = &*--ISelPosition; 1133 // Skip dead nodes. DAGCombiner is expected to eliminate all dead nodes, 1134 // but there are currently some corner cases that it misses. Also, this 1135 // makes it theoretically possible to disable the DAGCombiner. 1136 if (Node->use_empty()) 1137 continue; 1138 1139 #ifndef NDEBUG 1140 SmallVector<SDNode *, 4> Nodes; 1141 Nodes.push_back(Node); 1142 1143 while (!Nodes.empty()) { 1144 auto N = Nodes.pop_back_val(); 1145 if (N->getOpcode() == ISD::TokenFactor || N->getNodeId() < 0) 1146 continue; 1147 for (const SDValue &Op : N->op_values()) { 1148 if (Op->getOpcode() == ISD::TokenFactor) 1149 Nodes.push_back(Op.getNode()); 1150 else { 1151 // We rely on topological ordering of node ids for checking for 1152 // cycles when fusing nodes during selection. All unselected nodes 1153 // successors of an already selected node should have a negative id. 1154 // This assertion will catch such cases. If this assertion triggers 1155 // it is likely you using DAG-level Value/Node replacement functions 1156 // (versus equivalent ISEL replacement) in backend-specific 1157 // selections. See comment in EnforceNodeIdInvariant for more 1158 // details. 1159 assert(Op->getNodeId() != -1 && 1160 "Node has already selected predecessor node"); 1161 } 1162 } 1163 } 1164 #endif 1165 1166 // When we are using non-default rounding modes or FP exception behavior 1167 // FP operations are represented by StrictFP pseudo-operations. For 1168 // targets that do not (yet) understand strict FP operations directly, 1169 // we convert them to normal FP opcodes instead at this point. This 1170 // will allow them to be handled by existing target-specific instruction 1171 // selectors. 1172 if (!TLI->isStrictFPEnabled() && Node->isStrictFPOpcode()) { 1173 // For some opcodes, we need to call TLI->getOperationAction using 1174 // the first operand type instead of the result type. Note that this 1175 // must match what SelectionDAGLegalize::LegalizeOp is doing. 1176 EVT ActionVT; 1177 switch (Node->getOpcode()) { 1178 case ISD::STRICT_SINT_TO_FP: 1179 case ISD::STRICT_UINT_TO_FP: 1180 case ISD::STRICT_LRINT: 1181 case ISD::STRICT_LLRINT: 1182 case ISD::STRICT_LROUND: 1183 case ISD::STRICT_LLROUND: 1184 case ISD::STRICT_FSETCC: 1185 case ISD::STRICT_FSETCCS: 1186 ActionVT = Node->getOperand(1).getValueType(); 1187 break; 1188 default: 1189 ActionVT = Node->getValueType(0); 1190 break; 1191 } 1192 if (TLI->getOperationAction(Node->getOpcode(), ActionVT) 1193 == TargetLowering::Expand) 1194 Node = CurDAG->mutateStrictFPToFP(Node); 1195 } 1196 1197 LLVM_DEBUG(dbgs() << "\nISEL: Starting selection on root node: "; 1198 Node->dump(CurDAG)); 1199 1200 Select(Node); 1201 } 1202 1203 CurDAG->setRoot(Dummy.getValue()); 1204 } 1205 1206 LLVM_DEBUG(dbgs() << "\n===== Instruction selection ends:\n"); 1207 1208 PostprocessISelDAG(); 1209 } 1210 1211 static bool hasExceptionPointerOrCodeUser(const CatchPadInst *CPI) { 1212 for (const User *U : CPI->users()) { 1213 if (const IntrinsicInst *EHPtrCall = dyn_cast<IntrinsicInst>(U)) { 1214 Intrinsic::ID IID = EHPtrCall->getIntrinsicID(); 1215 if (IID == Intrinsic::eh_exceptionpointer || 1216 IID == Intrinsic::eh_exceptioncode) 1217 return true; 1218 } 1219 } 1220 return false; 1221 } 1222 1223 // wasm.landingpad.index intrinsic is for associating a landing pad index number 1224 // with a catchpad instruction. Retrieve the landing pad index in the intrinsic 1225 // and store the mapping in the function. 1226 static void mapWasmLandingPadIndex(MachineBasicBlock *MBB, 1227 const CatchPadInst *CPI) { 1228 MachineFunction *MF = MBB->getParent(); 1229 // In case of single catch (...), we don't emit LSDA, so we don't need 1230 // this information. 1231 bool IsSingleCatchAllClause = 1232 CPI->getNumArgOperands() == 1 && 1233 cast<Constant>(CPI->getArgOperand(0))->isNullValue(); 1234 // cathchpads for longjmp use an empty type list, e.g. catchpad within %0 [] 1235 // and they don't need LSDA info 1236 bool IsCatchLongjmp = CPI->getNumArgOperands() == 0; 1237 if (!IsSingleCatchAllClause && !IsCatchLongjmp) { 1238 // Create a mapping from landing pad label to landing pad index. 1239 bool IntrFound = false; 1240 for (const User *U : CPI->users()) { 1241 if (const auto *Call = dyn_cast<IntrinsicInst>(U)) { 1242 Intrinsic::ID IID = Call->getIntrinsicID(); 1243 if (IID == Intrinsic::wasm_landingpad_index) { 1244 Value *IndexArg = Call->getArgOperand(1); 1245 int Index = cast<ConstantInt>(IndexArg)->getZExtValue(); 1246 MF->setWasmLandingPadIndex(MBB, Index); 1247 IntrFound = true; 1248 break; 1249 } 1250 } 1251 } 1252 assert(IntrFound && "wasm.landingpad.index intrinsic not found!"); 1253 (void)IntrFound; 1254 } 1255 } 1256 1257 /// PrepareEHLandingPad - Emit an EH_LABEL, set up live-in registers, and 1258 /// do other setup for EH landing-pad blocks. 1259 bool SelectionDAGISel::PrepareEHLandingPad() { 1260 MachineBasicBlock *MBB = FuncInfo->MBB; 1261 const Constant *PersonalityFn = FuncInfo->Fn->getPersonalityFn(); 1262 const BasicBlock *LLVMBB = MBB->getBasicBlock(); 1263 const TargetRegisterClass *PtrRC = 1264 TLI->getRegClassFor(TLI->getPointerTy(CurDAG->getDataLayout())); 1265 1266 auto Pers = classifyEHPersonality(PersonalityFn); 1267 1268 // Catchpads have one live-in register, which typically holds the exception 1269 // pointer or code. 1270 if (isFuncletEHPersonality(Pers)) { 1271 if (const auto *CPI = dyn_cast<CatchPadInst>(LLVMBB->getFirstNonPHI())) { 1272 if (hasExceptionPointerOrCodeUser(CPI)) { 1273 // Get or create the virtual register to hold the pointer or code. Mark 1274 // the live in physreg and copy into the vreg. 1275 MCPhysReg EHPhysReg = TLI->getExceptionPointerRegister(PersonalityFn); 1276 assert(EHPhysReg && "target lacks exception pointer register"); 1277 MBB->addLiveIn(EHPhysReg); 1278 unsigned VReg = FuncInfo->getCatchPadExceptionPointerVReg(CPI, PtrRC); 1279 BuildMI(*MBB, FuncInfo->InsertPt, SDB->getCurDebugLoc(), 1280 TII->get(TargetOpcode::COPY), VReg) 1281 .addReg(EHPhysReg, RegState::Kill); 1282 } 1283 } 1284 return true; 1285 } 1286 1287 // Add a label to mark the beginning of the landing pad. Deletion of the 1288 // landing pad can thus be detected via the MachineModuleInfo. 1289 MCSymbol *Label = MF->addLandingPad(MBB); 1290 1291 const MCInstrDesc &II = TII->get(TargetOpcode::EH_LABEL); 1292 BuildMI(*MBB, FuncInfo->InsertPt, SDB->getCurDebugLoc(), II) 1293 .addSym(Label); 1294 1295 // If the unwinder does not preserve all registers, ensure that the 1296 // function marks the clobbered registers as used. 1297 const TargetRegisterInfo &TRI = *MF->getSubtarget().getRegisterInfo(); 1298 if (auto *RegMask = TRI.getCustomEHPadPreservedMask(*MF)) 1299 MF->getRegInfo().addPhysRegsUsedFromRegMask(RegMask); 1300 1301 if (Pers == EHPersonality::Wasm_CXX) { 1302 if (const auto *CPI = dyn_cast<CatchPadInst>(LLVMBB->getFirstNonPHI())) 1303 mapWasmLandingPadIndex(MBB, CPI); 1304 } else { 1305 // Assign the call site to the landing pad's begin label. 1306 MF->setCallSiteLandingPad(Label, SDB->LPadToCallSiteMap[MBB]); 1307 // Mark exception register as live in. 1308 if (unsigned Reg = TLI->getExceptionPointerRegister(PersonalityFn)) 1309 FuncInfo->ExceptionPointerVirtReg = MBB->addLiveIn(Reg, PtrRC); 1310 // Mark exception selector register as live in. 1311 if (unsigned Reg = TLI->getExceptionSelectorRegister(PersonalityFn)) 1312 FuncInfo->ExceptionSelectorVirtReg = MBB->addLiveIn(Reg, PtrRC); 1313 } 1314 1315 return true; 1316 } 1317 1318 /// isFoldedOrDeadInstruction - Return true if the specified instruction is 1319 /// side-effect free and is either dead or folded into a generated instruction. 1320 /// Return false if it needs to be emitted. 1321 static bool isFoldedOrDeadInstruction(const Instruction *I, 1322 const FunctionLoweringInfo &FuncInfo) { 1323 return !I->mayWriteToMemory() && // Side-effecting instructions aren't folded. 1324 !I->isTerminator() && // Terminators aren't folded. 1325 !isa<DbgInfoIntrinsic>(I) && // Debug instructions aren't folded. 1326 !I->isEHPad() && // EH pad instructions aren't folded. 1327 !FuncInfo.isExportedInst(I); // Exported instrs must be computed. 1328 } 1329 1330 /// Collect llvm.dbg.declare information. This is done after argument lowering 1331 /// in case the declarations refer to arguments. 1332 static void processDbgDeclares(FunctionLoweringInfo &FuncInfo) { 1333 MachineFunction *MF = FuncInfo.MF; 1334 const DataLayout &DL = MF->getDataLayout(); 1335 for (const BasicBlock &BB : *FuncInfo.Fn) { 1336 for (const Instruction &I : BB) { 1337 const DbgDeclareInst *DI = dyn_cast<DbgDeclareInst>(&I); 1338 if (!DI) 1339 continue; 1340 1341 assert(DI->getVariable() && "Missing variable"); 1342 assert(DI->getDebugLoc() && "Missing location"); 1343 const Value *Address = DI->getAddress(); 1344 if (!Address) { 1345 LLVM_DEBUG(dbgs() << "processDbgDeclares skipping " << *DI 1346 << " (bad address)\n"); 1347 continue; 1348 } 1349 1350 // Look through casts and constant offset GEPs. These mostly come from 1351 // inalloca. 1352 APInt Offset(DL.getTypeSizeInBits(Address->getType()), 0); 1353 Address = Address->stripAndAccumulateInBoundsConstantOffsets(DL, Offset); 1354 1355 // Check if the variable is a static alloca or a byval or inalloca 1356 // argument passed in memory. If it is not, then we will ignore this 1357 // intrinsic and handle this during isel like dbg.value. 1358 int FI = std::numeric_limits<int>::max(); 1359 if (const auto *AI = dyn_cast<AllocaInst>(Address)) { 1360 auto SI = FuncInfo.StaticAllocaMap.find(AI); 1361 if (SI != FuncInfo.StaticAllocaMap.end()) 1362 FI = SI->second; 1363 } else if (const auto *Arg = dyn_cast<Argument>(Address)) 1364 FI = FuncInfo.getArgumentFrameIndex(Arg); 1365 1366 if (FI == std::numeric_limits<int>::max()) 1367 continue; 1368 1369 DIExpression *Expr = DI->getExpression(); 1370 if (Offset.getBoolValue()) 1371 Expr = DIExpression::prepend(Expr, DIExpression::ApplyOffset, 1372 Offset.getZExtValue()); 1373 LLVM_DEBUG(dbgs() << "processDbgDeclares: setVariableDbgInfo FI=" << FI 1374 << ", " << *DI << "\n"); 1375 MF->setVariableDbgInfo(DI->getVariable(), Expr, FI, DI->getDebugLoc()); 1376 } 1377 } 1378 } 1379 1380 void SelectionDAGISel::SelectAllBasicBlocks(const Function &Fn) { 1381 FastISelFailed = false; 1382 // Initialize the Fast-ISel state, if needed. 1383 FastISel *FastIS = nullptr; 1384 if (TM.Options.EnableFastISel) { 1385 LLVM_DEBUG(dbgs() << "Enabling fast-isel\n"); 1386 FastIS = TLI->createFastISel(*FuncInfo, LibInfo); 1387 if (FastIS) 1388 FastIS->useInstrRefDebugInfo(UseInstrRefDebugInfo); 1389 } 1390 1391 ReversePostOrderTraversal<const Function*> RPOT(&Fn); 1392 1393 // Lower arguments up front. An RPO iteration always visits the entry block 1394 // first. 1395 assert(*RPOT.begin() == &Fn.getEntryBlock()); 1396 ++NumEntryBlocks; 1397 1398 // Set up FuncInfo for ISel. Entry blocks never have PHIs. 1399 FuncInfo->MBB = FuncInfo->MBBMap[&Fn.getEntryBlock()]; 1400 FuncInfo->InsertPt = FuncInfo->MBB->begin(); 1401 1402 CurDAG->setFunctionLoweringInfo(FuncInfo.get()); 1403 1404 if (!FastIS) { 1405 LowerArguments(Fn); 1406 } else { 1407 // See if fast isel can lower the arguments. 1408 FastIS->startNewBlock(); 1409 if (!FastIS->lowerArguments()) { 1410 FastISelFailed = true; 1411 // Fast isel failed to lower these arguments 1412 ++NumFastIselFailLowerArguments; 1413 1414 OptimizationRemarkMissed R("sdagisel", "FastISelFailure", 1415 Fn.getSubprogram(), 1416 &Fn.getEntryBlock()); 1417 R << "FastISel didn't lower all arguments: " 1418 << ore::NV("Prototype", Fn.getType()); 1419 reportFastISelFailure(*MF, *ORE, R, EnableFastISelAbort > 1); 1420 1421 // Use SelectionDAG argument lowering 1422 LowerArguments(Fn); 1423 CurDAG->setRoot(SDB->getControlRoot()); 1424 SDB->clear(); 1425 CodeGenAndEmitDAG(); 1426 } 1427 1428 // If we inserted any instructions at the beginning, make a note of 1429 // where they are, so we can be sure to emit subsequent instructions 1430 // after them. 1431 if (FuncInfo->InsertPt != FuncInfo->MBB->begin()) 1432 FastIS->setLastLocalValue(&*std::prev(FuncInfo->InsertPt)); 1433 else 1434 FastIS->setLastLocalValue(nullptr); 1435 } 1436 1437 bool Inserted = SwiftError->createEntriesInEntryBlock(SDB->getCurDebugLoc()); 1438 1439 if (FastIS && Inserted) 1440 FastIS->setLastLocalValue(&*std::prev(FuncInfo->InsertPt)); 1441 1442 processDbgDeclares(*FuncInfo); 1443 1444 // Iterate over all basic blocks in the function. 1445 StackProtector &SP = getAnalysis<StackProtector>(); 1446 for (const BasicBlock *LLVMBB : RPOT) { 1447 if (OptLevel != CodeGenOpt::None) { 1448 bool AllPredsVisited = true; 1449 for (const BasicBlock *Pred : predecessors(LLVMBB)) { 1450 if (!FuncInfo->VisitedBBs.count(Pred)) { 1451 AllPredsVisited = false; 1452 break; 1453 } 1454 } 1455 1456 if (AllPredsVisited) { 1457 for (const PHINode &PN : LLVMBB->phis()) 1458 FuncInfo->ComputePHILiveOutRegInfo(&PN); 1459 } else { 1460 for (const PHINode &PN : LLVMBB->phis()) 1461 FuncInfo->InvalidatePHILiveOutRegInfo(&PN); 1462 } 1463 1464 FuncInfo->VisitedBBs.insert(LLVMBB); 1465 } 1466 1467 BasicBlock::const_iterator const Begin = 1468 LLVMBB->getFirstNonPHI()->getIterator(); 1469 BasicBlock::const_iterator const End = LLVMBB->end(); 1470 BasicBlock::const_iterator BI = End; 1471 1472 FuncInfo->MBB = FuncInfo->MBBMap[LLVMBB]; 1473 if (!FuncInfo->MBB) 1474 continue; // Some blocks like catchpads have no code or MBB. 1475 1476 // Insert new instructions after any phi or argument setup code. 1477 FuncInfo->InsertPt = FuncInfo->MBB->end(); 1478 1479 // Setup an EH landing-pad block. 1480 FuncInfo->ExceptionPointerVirtReg = 0; 1481 FuncInfo->ExceptionSelectorVirtReg = 0; 1482 if (LLVMBB->isEHPad()) 1483 if (!PrepareEHLandingPad()) 1484 continue; 1485 1486 // Before doing SelectionDAG ISel, see if FastISel has been requested. 1487 if (FastIS) { 1488 if (LLVMBB != &Fn.getEntryBlock()) 1489 FastIS->startNewBlock(); 1490 1491 unsigned NumFastIselRemaining = std::distance(Begin, End); 1492 1493 // Pre-assign swifterror vregs. 1494 SwiftError->preassignVRegs(FuncInfo->MBB, Begin, End); 1495 1496 // Do FastISel on as many instructions as possible. 1497 for (; BI != Begin; --BI) { 1498 const Instruction *Inst = &*std::prev(BI); 1499 1500 // If we no longer require this instruction, skip it. 1501 if (isFoldedOrDeadInstruction(Inst, *FuncInfo) || 1502 ElidedArgCopyInstrs.count(Inst)) { 1503 --NumFastIselRemaining; 1504 continue; 1505 } 1506 1507 // Bottom-up: reset the insert pos at the top, after any local-value 1508 // instructions. 1509 FastIS->recomputeInsertPt(); 1510 1511 // Try to select the instruction with FastISel. 1512 if (FastIS->selectInstruction(Inst)) { 1513 --NumFastIselRemaining; 1514 ++NumFastIselSuccess; 1515 // If fast isel succeeded, skip over all the folded instructions, and 1516 // then see if there is a load right before the selected instructions. 1517 // Try to fold the load if so. 1518 const Instruction *BeforeInst = Inst; 1519 while (BeforeInst != &*Begin) { 1520 BeforeInst = &*std::prev(BasicBlock::const_iterator(BeforeInst)); 1521 if (!isFoldedOrDeadInstruction(BeforeInst, *FuncInfo)) 1522 break; 1523 } 1524 if (BeforeInst != Inst && isa<LoadInst>(BeforeInst) && 1525 BeforeInst->hasOneUse() && 1526 FastIS->tryToFoldLoad(cast<LoadInst>(BeforeInst), Inst)) { 1527 // If we succeeded, don't re-select the load. 1528 LLVM_DEBUG(dbgs() 1529 << "FastISel folded load: " << *BeforeInst << "\n"); 1530 BI = std::next(BasicBlock::const_iterator(BeforeInst)); 1531 --NumFastIselRemaining; 1532 ++NumFastIselSuccess; 1533 } 1534 continue; 1535 } 1536 1537 FastISelFailed = true; 1538 1539 // Then handle certain instructions as single-LLVM-Instruction blocks. 1540 // We cannot separate out GCrelocates to their own blocks since we need 1541 // to keep track of gc-relocates for a particular gc-statepoint. This is 1542 // done by SelectionDAGBuilder::LowerAsSTATEPOINT, called before 1543 // visitGCRelocate. 1544 if (isa<CallInst>(Inst) && !isa<GCStatepointInst>(Inst) && 1545 !isa<GCRelocateInst>(Inst) && !isa<GCResultInst>(Inst)) { 1546 OptimizationRemarkMissed R("sdagisel", "FastISelFailure", 1547 Inst->getDebugLoc(), LLVMBB); 1548 1549 R << "FastISel missed call"; 1550 1551 if (R.isEnabled() || EnableFastISelAbort) { 1552 std::string InstStrStorage; 1553 raw_string_ostream InstStr(InstStrStorage); 1554 InstStr << *Inst; 1555 1556 R << ": " << InstStr.str(); 1557 } 1558 1559 reportFastISelFailure(*MF, *ORE, R, EnableFastISelAbort > 2); 1560 1561 if (!Inst->getType()->isVoidTy() && !Inst->getType()->isTokenTy() && 1562 !Inst->use_empty()) { 1563 Register &R = FuncInfo->ValueMap[Inst]; 1564 if (!R) 1565 R = FuncInfo->CreateRegs(Inst); 1566 } 1567 1568 bool HadTailCall = false; 1569 MachineBasicBlock::iterator SavedInsertPt = FuncInfo->InsertPt; 1570 SelectBasicBlock(Inst->getIterator(), BI, HadTailCall); 1571 1572 // If the call was emitted as a tail call, we're done with the block. 1573 // We also need to delete any previously emitted instructions. 1574 if (HadTailCall) { 1575 FastIS->removeDeadCode(SavedInsertPt, FuncInfo->MBB->end()); 1576 --BI; 1577 break; 1578 } 1579 1580 // Recompute NumFastIselRemaining as Selection DAG instruction 1581 // selection may have handled the call, input args, etc. 1582 unsigned RemainingNow = std::distance(Begin, BI); 1583 NumFastIselFailures += NumFastIselRemaining - RemainingNow; 1584 NumFastIselRemaining = RemainingNow; 1585 continue; 1586 } 1587 1588 OptimizationRemarkMissed R("sdagisel", "FastISelFailure", 1589 Inst->getDebugLoc(), LLVMBB); 1590 1591 bool ShouldAbort = EnableFastISelAbort; 1592 if (Inst->isTerminator()) { 1593 // Use a different message for terminator misses. 1594 R << "FastISel missed terminator"; 1595 // Don't abort for terminator unless the level is really high 1596 ShouldAbort = (EnableFastISelAbort > 2); 1597 } else { 1598 R << "FastISel missed"; 1599 } 1600 1601 if (R.isEnabled() || EnableFastISelAbort) { 1602 std::string InstStrStorage; 1603 raw_string_ostream InstStr(InstStrStorage); 1604 InstStr << *Inst; 1605 R << ": " << InstStr.str(); 1606 } 1607 1608 reportFastISelFailure(*MF, *ORE, R, ShouldAbort); 1609 1610 NumFastIselFailures += NumFastIselRemaining; 1611 break; 1612 } 1613 1614 FastIS->recomputeInsertPt(); 1615 } 1616 1617 if (SP.shouldEmitSDCheck(*LLVMBB)) { 1618 bool FunctionBasedInstrumentation = 1619 TLI->getSSPStackGuardCheck(*Fn.getParent()); 1620 SDB->SPDescriptor.initialize(LLVMBB, FuncInfo->MBBMap[LLVMBB], 1621 FunctionBasedInstrumentation); 1622 } 1623 1624 if (Begin != BI) 1625 ++NumDAGBlocks; 1626 else 1627 ++NumFastIselBlocks; 1628 1629 if (Begin != BI) { 1630 // Run SelectionDAG instruction selection on the remainder of the block 1631 // not handled by FastISel. If FastISel is not run, this is the entire 1632 // block. 1633 bool HadTailCall; 1634 SelectBasicBlock(Begin, BI, HadTailCall); 1635 1636 // But if FastISel was run, we already selected some of the block. 1637 // If we emitted a tail-call, we need to delete any previously emitted 1638 // instruction that follows it. 1639 if (FastIS && HadTailCall && FuncInfo->InsertPt != FuncInfo->MBB->end()) 1640 FastIS->removeDeadCode(FuncInfo->InsertPt, FuncInfo->MBB->end()); 1641 } 1642 1643 if (FastIS) 1644 FastIS->finishBasicBlock(); 1645 FinishBasicBlock(); 1646 FuncInfo->PHINodesToUpdate.clear(); 1647 ElidedArgCopyInstrs.clear(); 1648 } 1649 1650 SP.copyToMachineFrameInfo(MF->getFrameInfo()); 1651 1652 SwiftError->propagateVRegs(); 1653 1654 delete FastIS; 1655 SDB->clearDanglingDebugInfo(); 1656 SDB->SPDescriptor.resetPerFunctionState(); 1657 } 1658 1659 void 1660 SelectionDAGISel::FinishBasicBlock() { 1661 LLVM_DEBUG(dbgs() << "Total amount of phi nodes to update: " 1662 << FuncInfo->PHINodesToUpdate.size() << "\n"; 1663 for (unsigned i = 0, e = FuncInfo->PHINodesToUpdate.size(); i != e; 1664 ++i) dbgs() 1665 << "Node " << i << " : (" << FuncInfo->PHINodesToUpdate[i].first 1666 << ", " << FuncInfo->PHINodesToUpdate[i].second << ")\n"); 1667 1668 // Next, now that we know what the last MBB the LLVM BB expanded is, update 1669 // PHI nodes in successors. 1670 for (unsigned i = 0, e = FuncInfo->PHINodesToUpdate.size(); i != e; ++i) { 1671 MachineInstrBuilder PHI(*MF, FuncInfo->PHINodesToUpdate[i].first); 1672 assert(PHI->isPHI() && 1673 "This is not a machine PHI node that we are updating!"); 1674 if (!FuncInfo->MBB->isSuccessor(PHI->getParent())) 1675 continue; 1676 PHI.addReg(FuncInfo->PHINodesToUpdate[i].second).addMBB(FuncInfo->MBB); 1677 } 1678 1679 // Handle stack protector. 1680 if (SDB->SPDescriptor.shouldEmitFunctionBasedCheckStackProtector()) { 1681 // The target provides a guard check function. There is no need to 1682 // generate error handling code or to split current basic block. 1683 MachineBasicBlock *ParentMBB = SDB->SPDescriptor.getParentMBB(); 1684 1685 // Add load and check to the basicblock. 1686 FuncInfo->MBB = ParentMBB; 1687 FuncInfo->InsertPt = 1688 findSplitPointForStackProtector(ParentMBB, *TII); 1689 SDB->visitSPDescriptorParent(SDB->SPDescriptor, ParentMBB); 1690 CurDAG->setRoot(SDB->getRoot()); 1691 SDB->clear(); 1692 CodeGenAndEmitDAG(); 1693 1694 // Clear the Per-BB State. 1695 SDB->SPDescriptor.resetPerBBState(); 1696 } else if (SDB->SPDescriptor.shouldEmitStackProtector()) { 1697 MachineBasicBlock *ParentMBB = SDB->SPDescriptor.getParentMBB(); 1698 MachineBasicBlock *SuccessMBB = SDB->SPDescriptor.getSuccessMBB(); 1699 1700 // Find the split point to split the parent mbb. At the same time copy all 1701 // physical registers used in the tail of parent mbb into virtual registers 1702 // before the split point and back into physical registers after the split 1703 // point. This prevents us needing to deal with Live-ins and many other 1704 // register allocation issues caused by us splitting the parent mbb. The 1705 // register allocator will clean up said virtual copies later on. 1706 MachineBasicBlock::iterator SplitPoint = 1707 findSplitPointForStackProtector(ParentMBB, *TII); 1708 1709 // Splice the terminator of ParentMBB into SuccessMBB. 1710 SuccessMBB->splice(SuccessMBB->end(), ParentMBB, 1711 SplitPoint, 1712 ParentMBB->end()); 1713 1714 // Add compare/jump on neq/jump to the parent BB. 1715 FuncInfo->MBB = ParentMBB; 1716 FuncInfo->InsertPt = ParentMBB->end(); 1717 SDB->visitSPDescriptorParent(SDB->SPDescriptor, ParentMBB); 1718 CurDAG->setRoot(SDB->getRoot()); 1719 SDB->clear(); 1720 CodeGenAndEmitDAG(); 1721 1722 // CodeGen Failure MBB if we have not codegened it yet. 1723 MachineBasicBlock *FailureMBB = SDB->SPDescriptor.getFailureMBB(); 1724 if (FailureMBB->empty()) { 1725 FuncInfo->MBB = FailureMBB; 1726 FuncInfo->InsertPt = FailureMBB->end(); 1727 SDB->visitSPDescriptorFailure(SDB->SPDescriptor); 1728 CurDAG->setRoot(SDB->getRoot()); 1729 SDB->clear(); 1730 CodeGenAndEmitDAG(); 1731 } 1732 1733 // Clear the Per-BB State. 1734 SDB->SPDescriptor.resetPerBBState(); 1735 } 1736 1737 // Lower each BitTestBlock. 1738 for (auto &BTB : SDB->SL->BitTestCases) { 1739 // Lower header first, if it wasn't already lowered 1740 if (!BTB.Emitted) { 1741 // Set the current basic block to the mbb we wish to insert the code into 1742 FuncInfo->MBB = BTB.Parent; 1743 FuncInfo->InsertPt = FuncInfo->MBB->end(); 1744 // Emit the code 1745 SDB->visitBitTestHeader(BTB, FuncInfo->MBB); 1746 CurDAG->setRoot(SDB->getRoot()); 1747 SDB->clear(); 1748 CodeGenAndEmitDAG(); 1749 } 1750 1751 BranchProbability UnhandledProb = BTB.Prob; 1752 for (unsigned j = 0, ej = BTB.Cases.size(); j != ej; ++j) { 1753 UnhandledProb -= BTB.Cases[j].ExtraProb; 1754 // Set the current basic block to the mbb we wish to insert the code into 1755 FuncInfo->MBB = BTB.Cases[j].ThisBB; 1756 FuncInfo->InsertPt = FuncInfo->MBB->end(); 1757 // Emit the code 1758 1759 // If all cases cover a contiguous range, it is not necessary to jump to 1760 // the default block after the last bit test fails. This is because the 1761 // range check during bit test header creation has guaranteed that every 1762 // case here doesn't go outside the range. In this case, there is no need 1763 // to perform the last bit test, as it will always be true. Instead, make 1764 // the second-to-last bit-test fall through to the target of the last bit 1765 // test, and delete the last bit test. 1766 1767 MachineBasicBlock *NextMBB; 1768 if ((BTB.ContiguousRange || BTB.FallthroughUnreachable) && j + 2 == ej) { 1769 // Second-to-last bit-test with contiguous range or omitted range 1770 // check: fall through to the target of the final bit test. 1771 NextMBB = BTB.Cases[j + 1].TargetBB; 1772 } else if (j + 1 == ej) { 1773 // For the last bit test, fall through to Default. 1774 NextMBB = BTB.Default; 1775 } else { 1776 // Otherwise, fall through to the next bit test. 1777 NextMBB = BTB.Cases[j + 1].ThisBB; 1778 } 1779 1780 SDB->visitBitTestCase(BTB, NextMBB, UnhandledProb, BTB.Reg, BTB.Cases[j], 1781 FuncInfo->MBB); 1782 1783 CurDAG->setRoot(SDB->getRoot()); 1784 SDB->clear(); 1785 CodeGenAndEmitDAG(); 1786 1787 if ((BTB.ContiguousRange || BTB.FallthroughUnreachable) && j + 2 == ej) { 1788 // Since we're not going to use the final bit test, remove it. 1789 BTB.Cases.pop_back(); 1790 break; 1791 } 1792 } 1793 1794 // Update PHI Nodes 1795 for (const std::pair<MachineInstr *, unsigned> &P : 1796 FuncInfo->PHINodesToUpdate) { 1797 MachineInstrBuilder PHI(*MF, P.first); 1798 MachineBasicBlock *PHIBB = PHI->getParent(); 1799 assert(PHI->isPHI() && 1800 "This is not a machine PHI node that we are updating!"); 1801 // This is "default" BB. We have two jumps to it. From "header" BB and 1802 // from last "case" BB, unless the latter was skipped. 1803 if (PHIBB == BTB.Default) { 1804 PHI.addReg(P.second).addMBB(BTB.Parent); 1805 if (!BTB.ContiguousRange) { 1806 PHI.addReg(P.second).addMBB(BTB.Cases.back().ThisBB); 1807 } 1808 } 1809 // One of "cases" BB. 1810 for (const SwitchCG::BitTestCase &BT : BTB.Cases) { 1811 MachineBasicBlock* cBB = BT.ThisBB; 1812 if (cBB->isSuccessor(PHIBB)) 1813 PHI.addReg(P.second).addMBB(cBB); 1814 } 1815 } 1816 } 1817 SDB->SL->BitTestCases.clear(); 1818 1819 // If the JumpTable record is filled in, then we need to emit a jump table. 1820 // Updating the PHI nodes is tricky in this case, since we need to determine 1821 // whether the PHI is a successor of the range check MBB or the jump table MBB 1822 for (unsigned i = 0, e = SDB->SL->JTCases.size(); i != e; ++i) { 1823 // Lower header first, if it wasn't already lowered 1824 if (!SDB->SL->JTCases[i].first.Emitted) { 1825 // Set the current basic block to the mbb we wish to insert the code into 1826 FuncInfo->MBB = SDB->SL->JTCases[i].first.HeaderBB; 1827 FuncInfo->InsertPt = FuncInfo->MBB->end(); 1828 // Emit the code 1829 SDB->visitJumpTableHeader(SDB->SL->JTCases[i].second, 1830 SDB->SL->JTCases[i].first, FuncInfo->MBB); 1831 CurDAG->setRoot(SDB->getRoot()); 1832 SDB->clear(); 1833 CodeGenAndEmitDAG(); 1834 } 1835 1836 // Set the current basic block to the mbb we wish to insert the code into 1837 FuncInfo->MBB = SDB->SL->JTCases[i].second.MBB; 1838 FuncInfo->InsertPt = FuncInfo->MBB->end(); 1839 // Emit the code 1840 SDB->visitJumpTable(SDB->SL->JTCases[i].second); 1841 CurDAG->setRoot(SDB->getRoot()); 1842 SDB->clear(); 1843 CodeGenAndEmitDAG(); 1844 1845 // Update PHI Nodes 1846 for (unsigned pi = 0, pe = FuncInfo->PHINodesToUpdate.size(); 1847 pi != pe; ++pi) { 1848 MachineInstrBuilder PHI(*MF, FuncInfo->PHINodesToUpdate[pi].first); 1849 MachineBasicBlock *PHIBB = PHI->getParent(); 1850 assert(PHI->isPHI() && 1851 "This is not a machine PHI node that we are updating!"); 1852 // "default" BB. We can go there only from header BB. 1853 if (PHIBB == SDB->SL->JTCases[i].second.Default) 1854 PHI.addReg(FuncInfo->PHINodesToUpdate[pi].second) 1855 .addMBB(SDB->SL->JTCases[i].first.HeaderBB); 1856 // JT BB. Just iterate over successors here 1857 if (FuncInfo->MBB->isSuccessor(PHIBB)) 1858 PHI.addReg(FuncInfo->PHINodesToUpdate[pi].second).addMBB(FuncInfo->MBB); 1859 } 1860 } 1861 SDB->SL->JTCases.clear(); 1862 1863 // If we generated any switch lowering information, build and codegen any 1864 // additional DAGs necessary. 1865 for (unsigned i = 0, e = SDB->SL->SwitchCases.size(); i != e; ++i) { 1866 // Set the current basic block to the mbb we wish to insert the code into 1867 FuncInfo->MBB = SDB->SL->SwitchCases[i].ThisBB; 1868 FuncInfo->InsertPt = FuncInfo->MBB->end(); 1869 1870 // Determine the unique successors. 1871 SmallVector<MachineBasicBlock *, 2> Succs; 1872 Succs.push_back(SDB->SL->SwitchCases[i].TrueBB); 1873 if (SDB->SL->SwitchCases[i].TrueBB != SDB->SL->SwitchCases[i].FalseBB) 1874 Succs.push_back(SDB->SL->SwitchCases[i].FalseBB); 1875 1876 // Emit the code. Note that this could result in FuncInfo->MBB being split. 1877 SDB->visitSwitchCase(SDB->SL->SwitchCases[i], FuncInfo->MBB); 1878 CurDAG->setRoot(SDB->getRoot()); 1879 SDB->clear(); 1880 CodeGenAndEmitDAG(); 1881 1882 // Remember the last block, now that any splitting is done, for use in 1883 // populating PHI nodes in successors. 1884 MachineBasicBlock *ThisBB = FuncInfo->MBB; 1885 1886 // Handle any PHI nodes in successors of this chunk, as if we were coming 1887 // from the original BB before switch expansion. Note that PHI nodes can 1888 // occur multiple times in PHINodesToUpdate. We have to be very careful to 1889 // handle them the right number of times. 1890 for (unsigned i = 0, e = Succs.size(); i != e; ++i) { 1891 FuncInfo->MBB = Succs[i]; 1892 FuncInfo->InsertPt = FuncInfo->MBB->end(); 1893 // FuncInfo->MBB may have been removed from the CFG if a branch was 1894 // constant folded. 1895 if (ThisBB->isSuccessor(FuncInfo->MBB)) { 1896 for (MachineBasicBlock::iterator 1897 MBBI = FuncInfo->MBB->begin(), MBBE = FuncInfo->MBB->end(); 1898 MBBI != MBBE && MBBI->isPHI(); ++MBBI) { 1899 MachineInstrBuilder PHI(*MF, MBBI); 1900 // This value for this PHI node is recorded in PHINodesToUpdate. 1901 for (unsigned pn = 0; ; ++pn) { 1902 assert(pn != FuncInfo->PHINodesToUpdate.size() && 1903 "Didn't find PHI entry!"); 1904 if (FuncInfo->PHINodesToUpdate[pn].first == PHI) { 1905 PHI.addReg(FuncInfo->PHINodesToUpdate[pn].second).addMBB(ThisBB); 1906 break; 1907 } 1908 } 1909 } 1910 } 1911 } 1912 } 1913 SDB->SL->SwitchCases.clear(); 1914 } 1915 1916 /// Create the scheduler. If a specific scheduler was specified 1917 /// via the SchedulerRegistry, use it, otherwise select the 1918 /// one preferred by the target. 1919 /// 1920 ScheduleDAGSDNodes *SelectionDAGISel::CreateScheduler() { 1921 return ISHeuristic(this, OptLevel); 1922 } 1923 1924 //===----------------------------------------------------------------------===// 1925 // Helper functions used by the generated instruction selector. 1926 //===----------------------------------------------------------------------===// 1927 // Calls to these methods are generated by tblgen. 1928 1929 /// CheckAndMask - The isel is trying to match something like (and X, 255). If 1930 /// the dag combiner simplified the 255, we still want to match. RHS is the 1931 /// actual value in the DAG on the RHS of an AND, and DesiredMaskS is the value 1932 /// specified in the .td file (e.g. 255). 1933 bool SelectionDAGISel::CheckAndMask(SDValue LHS, ConstantSDNode *RHS, 1934 int64_t DesiredMaskS) const { 1935 const APInt &ActualMask = RHS->getAPIntValue(); 1936 const APInt &DesiredMask = APInt(LHS.getValueSizeInBits(), DesiredMaskS); 1937 1938 // If the actual mask exactly matches, success! 1939 if (ActualMask == DesiredMask) 1940 return true; 1941 1942 // If the actual AND mask is allowing unallowed bits, this doesn't match. 1943 if (!ActualMask.isSubsetOf(DesiredMask)) 1944 return false; 1945 1946 // Otherwise, the DAG Combiner may have proven that the value coming in is 1947 // either already zero or is not demanded. Check for known zero input bits. 1948 APInt NeededMask = DesiredMask & ~ActualMask; 1949 if (CurDAG->MaskedValueIsZero(LHS, NeededMask)) 1950 return true; 1951 1952 // TODO: check to see if missing bits are just not demanded. 1953 1954 // Otherwise, this pattern doesn't match. 1955 return false; 1956 } 1957 1958 /// CheckOrMask - The isel is trying to match something like (or X, 255). If 1959 /// the dag combiner simplified the 255, we still want to match. RHS is the 1960 /// actual value in the DAG on the RHS of an OR, and DesiredMaskS is the value 1961 /// specified in the .td file (e.g. 255). 1962 bool SelectionDAGISel::CheckOrMask(SDValue LHS, ConstantSDNode *RHS, 1963 int64_t DesiredMaskS) const { 1964 const APInt &ActualMask = RHS->getAPIntValue(); 1965 const APInt &DesiredMask = APInt(LHS.getValueSizeInBits(), DesiredMaskS); 1966 1967 // If the actual mask exactly matches, success! 1968 if (ActualMask == DesiredMask) 1969 return true; 1970 1971 // If the actual AND mask is allowing unallowed bits, this doesn't match. 1972 if (!ActualMask.isSubsetOf(DesiredMask)) 1973 return false; 1974 1975 // Otherwise, the DAG Combiner may have proven that the value coming in is 1976 // either already zero or is not demanded. Check for known zero input bits. 1977 APInt NeededMask = DesiredMask & ~ActualMask; 1978 KnownBits Known = CurDAG->computeKnownBits(LHS); 1979 1980 // If all the missing bits in the or are already known to be set, match! 1981 if (NeededMask.isSubsetOf(Known.One)) 1982 return true; 1983 1984 // TODO: check to see if missing bits are just not demanded. 1985 1986 // Otherwise, this pattern doesn't match. 1987 return false; 1988 } 1989 1990 /// SelectInlineAsmMemoryOperands - Calls to this are automatically generated 1991 /// by tblgen. Others should not call it. 1992 void SelectionDAGISel::SelectInlineAsmMemoryOperands(std::vector<SDValue> &Ops, 1993 const SDLoc &DL) { 1994 std::vector<SDValue> InOps; 1995 std::swap(InOps, Ops); 1996 1997 Ops.push_back(InOps[InlineAsm::Op_InputChain]); // 0 1998 Ops.push_back(InOps[InlineAsm::Op_AsmString]); // 1 1999 Ops.push_back(InOps[InlineAsm::Op_MDNode]); // 2, !srcloc 2000 Ops.push_back(InOps[InlineAsm::Op_ExtraInfo]); // 3 (SideEffect, AlignStack) 2001 2002 unsigned i = InlineAsm::Op_FirstOperand, e = InOps.size(); 2003 if (InOps[e-1].getValueType() == MVT::Glue) 2004 --e; // Don't process a glue operand if it is here. 2005 2006 while (i != e) { 2007 unsigned Flags = cast<ConstantSDNode>(InOps[i])->getZExtValue(); 2008 if (!InlineAsm::isMemKind(Flags)) { 2009 // Just skip over this operand, copying the operands verbatim. 2010 Ops.insert(Ops.end(), InOps.begin()+i, 2011 InOps.begin()+i+InlineAsm::getNumOperandRegisters(Flags) + 1); 2012 i += InlineAsm::getNumOperandRegisters(Flags) + 1; 2013 } else { 2014 assert(InlineAsm::getNumOperandRegisters(Flags) == 1 && 2015 "Memory operand with multiple values?"); 2016 2017 unsigned TiedToOperand; 2018 if (InlineAsm::isUseOperandTiedToDef(Flags, TiedToOperand)) { 2019 // We need the constraint ID from the operand this is tied to. 2020 unsigned CurOp = InlineAsm::Op_FirstOperand; 2021 Flags = cast<ConstantSDNode>(InOps[CurOp])->getZExtValue(); 2022 for (; TiedToOperand; --TiedToOperand) { 2023 CurOp += InlineAsm::getNumOperandRegisters(Flags)+1; 2024 Flags = cast<ConstantSDNode>(InOps[CurOp])->getZExtValue(); 2025 } 2026 } 2027 2028 // Otherwise, this is a memory operand. Ask the target to select it. 2029 std::vector<SDValue> SelOps; 2030 unsigned ConstraintID = InlineAsm::getMemoryConstraintID(Flags); 2031 if (SelectInlineAsmMemoryOperand(InOps[i+1], ConstraintID, SelOps)) 2032 report_fatal_error("Could not match memory address. Inline asm" 2033 " failure!"); 2034 2035 // Add this to the output node. 2036 unsigned NewFlags = 2037 InlineAsm::getFlagWord(InlineAsm::Kind_Mem, SelOps.size()); 2038 NewFlags = InlineAsm::getFlagWordForMem(NewFlags, ConstraintID); 2039 Ops.push_back(CurDAG->getTargetConstant(NewFlags, DL, MVT::i32)); 2040 llvm::append_range(Ops, SelOps); 2041 i += 2; 2042 } 2043 } 2044 2045 // Add the glue input back if present. 2046 if (e != InOps.size()) 2047 Ops.push_back(InOps.back()); 2048 } 2049 2050 /// findGlueUse - Return use of MVT::Glue value produced by the specified 2051 /// SDNode. 2052 /// 2053 static SDNode *findGlueUse(SDNode *N) { 2054 unsigned FlagResNo = N->getNumValues()-1; 2055 for (SDNode::use_iterator I = N->use_begin(), E = N->use_end(); I != E; ++I) { 2056 SDUse &Use = I.getUse(); 2057 if (Use.getResNo() == FlagResNo) 2058 return Use.getUser(); 2059 } 2060 return nullptr; 2061 } 2062 2063 /// findNonImmUse - Return true if "Def" is a predecessor of "Root" via a path 2064 /// beyond "ImmedUse". We may ignore chains as they are checked separately. 2065 static bool findNonImmUse(SDNode *Root, SDNode *Def, SDNode *ImmedUse, 2066 bool IgnoreChains) { 2067 SmallPtrSet<const SDNode *, 16> Visited; 2068 SmallVector<const SDNode *, 16> WorkList; 2069 // Only check if we have non-immediate uses of Def. 2070 if (ImmedUse->isOnlyUserOf(Def)) 2071 return false; 2072 2073 // We don't care about paths to Def that go through ImmedUse so mark it 2074 // visited and mark non-def operands as used. 2075 Visited.insert(ImmedUse); 2076 for (const SDValue &Op : ImmedUse->op_values()) { 2077 SDNode *N = Op.getNode(); 2078 // Ignore chain deps (they are validated by 2079 // HandleMergeInputChains) and immediate uses 2080 if ((Op.getValueType() == MVT::Other && IgnoreChains) || N == Def) 2081 continue; 2082 if (!Visited.insert(N).second) 2083 continue; 2084 WorkList.push_back(N); 2085 } 2086 2087 // Initialize worklist to operands of Root. 2088 if (Root != ImmedUse) { 2089 for (const SDValue &Op : Root->op_values()) { 2090 SDNode *N = Op.getNode(); 2091 // Ignore chains (they are validated by HandleMergeInputChains) 2092 if ((Op.getValueType() == MVT::Other && IgnoreChains) || N == Def) 2093 continue; 2094 if (!Visited.insert(N).second) 2095 continue; 2096 WorkList.push_back(N); 2097 } 2098 } 2099 2100 return SDNode::hasPredecessorHelper(Def, Visited, WorkList, 0, true); 2101 } 2102 2103 /// IsProfitableToFold - Returns true if it's profitable to fold the specific 2104 /// operand node N of U during instruction selection that starts at Root. 2105 bool SelectionDAGISel::IsProfitableToFold(SDValue N, SDNode *U, 2106 SDNode *Root) const { 2107 if (OptLevel == CodeGenOpt::None) return false; 2108 return N.hasOneUse(); 2109 } 2110 2111 /// IsLegalToFold - Returns true if the specific operand node N of 2112 /// U can be folded during instruction selection that starts at Root. 2113 bool SelectionDAGISel::IsLegalToFold(SDValue N, SDNode *U, SDNode *Root, 2114 CodeGenOpt::Level OptLevel, 2115 bool IgnoreChains) { 2116 if (OptLevel == CodeGenOpt::None) return false; 2117 2118 // If Root use can somehow reach N through a path that that doesn't contain 2119 // U then folding N would create a cycle. e.g. In the following 2120 // diagram, Root can reach N through X. If N is folded into Root, then 2121 // X is both a predecessor and a successor of U. 2122 // 2123 // [N*] // 2124 // ^ ^ // 2125 // / \ // 2126 // [U*] [X]? // 2127 // ^ ^ // 2128 // \ / // 2129 // \ / // 2130 // [Root*] // 2131 // 2132 // * indicates nodes to be folded together. 2133 // 2134 // If Root produces glue, then it gets (even more) interesting. Since it 2135 // will be "glued" together with its glue use in the scheduler, we need to 2136 // check if it might reach N. 2137 // 2138 // [N*] // 2139 // ^ ^ // 2140 // / \ // 2141 // [U*] [X]? // 2142 // ^ ^ // 2143 // \ \ // 2144 // \ | // 2145 // [Root*] | // 2146 // ^ | // 2147 // f | // 2148 // | / // 2149 // [Y] / // 2150 // ^ / // 2151 // f / // 2152 // | / // 2153 // [GU] // 2154 // 2155 // If GU (glue use) indirectly reaches N (the load), and Root folds N 2156 // (call it Fold), then X is a predecessor of GU and a successor of 2157 // Fold. But since Fold and GU are glued together, this will create 2158 // a cycle in the scheduling graph. 2159 2160 // If the node has glue, walk down the graph to the "lowest" node in the 2161 // glueged set. 2162 EVT VT = Root->getValueType(Root->getNumValues()-1); 2163 while (VT == MVT::Glue) { 2164 SDNode *GU = findGlueUse(Root); 2165 if (!GU) 2166 break; 2167 Root = GU; 2168 VT = Root->getValueType(Root->getNumValues()-1); 2169 2170 // If our query node has a glue result with a use, we've walked up it. If 2171 // the user (which has already been selected) has a chain or indirectly uses 2172 // the chain, HandleMergeInputChains will not consider it. Because of 2173 // this, we cannot ignore chains in this predicate. 2174 IgnoreChains = false; 2175 } 2176 2177 return !findNonImmUse(Root, N.getNode(), U, IgnoreChains); 2178 } 2179 2180 void SelectionDAGISel::Select_INLINEASM(SDNode *N) { 2181 SDLoc DL(N); 2182 2183 std::vector<SDValue> Ops(N->op_begin(), N->op_end()); 2184 SelectInlineAsmMemoryOperands(Ops, DL); 2185 2186 const EVT VTs[] = {MVT::Other, MVT::Glue}; 2187 SDValue New = CurDAG->getNode(N->getOpcode(), DL, VTs, Ops); 2188 New->setNodeId(-1); 2189 ReplaceUses(N, New.getNode()); 2190 CurDAG->RemoveDeadNode(N); 2191 } 2192 2193 void SelectionDAGISel::Select_READ_REGISTER(SDNode *Op) { 2194 SDLoc dl(Op); 2195 MDNodeSDNode *MD = cast<MDNodeSDNode>(Op->getOperand(1)); 2196 const MDString *RegStr = cast<MDString>(MD->getMD()->getOperand(0)); 2197 2198 EVT VT = Op->getValueType(0); 2199 LLT Ty = VT.isSimple() ? getLLTForMVT(VT.getSimpleVT()) : LLT(); 2200 Register Reg = 2201 TLI->getRegisterByName(RegStr->getString().data(), Ty, 2202 CurDAG->getMachineFunction()); 2203 SDValue New = CurDAG->getCopyFromReg( 2204 Op->getOperand(0), dl, Reg, Op->getValueType(0)); 2205 New->setNodeId(-1); 2206 ReplaceUses(Op, New.getNode()); 2207 CurDAG->RemoveDeadNode(Op); 2208 } 2209 2210 void SelectionDAGISel::Select_WRITE_REGISTER(SDNode *Op) { 2211 SDLoc dl(Op); 2212 MDNodeSDNode *MD = cast<MDNodeSDNode>(Op->getOperand(1)); 2213 const MDString *RegStr = cast<MDString>(MD->getMD()->getOperand(0)); 2214 2215 EVT VT = Op->getOperand(2).getValueType(); 2216 LLT Ty = VT.isSimple() ? getLLTForMVT(VT.getSimpleVT()) : LLT(); 2217 2218 Register Reg = TLI->getRegisterByName(RegStr->getString().data(), Ty, 2219 CurDAG->getMachineFunction()); 2220 SDValue New = CurDAG->getCopyToReg( 2221 Op->getOperand(0), dl, Reg, Op->getOperand(2)); 2222 New->setNodeId(-1); 2223 ReplaceUses(Op, New.getNode()); 2224 CurDAG->RemoveDeadNode(Op); 2225 } 2226 2227 void SelectionDAGISel::Select_UNDEF(SDNode *N) { 2228 CurDAG->SelectNodeTo(N, TargetOpcode::IMPLICIT_DEF, N->getValueType(0)); 2229 } 2230 2231 void SelectionDAGISel::Select_FREEZE(SDNode *N) { 2232 // TODO: We don't have FREEZE pseudo-instruction in MachineInstr-level now. 2233 // If FREEZE instruction is added later, the code below must be changed as 2234 // well. 2235 CurDAG->SelectNodeTo(N, TargetOpcode::COPY, N->getValueType(0), 2236 N->getOperand(0)); 2237 } 2238 2239 void SelectionDAGISel::Select_ARITH_FENCE(SDNode *N) { 2240 CurDAG->SelectNodeTo(N, TargetOpcode::ARITH_FENCE, N->getValueType(0), 2241 N->getOperand(0)); 2242 } 2243 2244 /// GetVBR - decode a vbr encoding whose top bit is set. 2245 LLVM_ATTRIBUTE_ALWAYS_INLINE static uint64_t 2246 GetVBR(uint64_t Val, const unsigned char *MatcherTable, unsigned &Idx) { 2247 assert(Val >= 128 && "Not a VBR"); 2248 Val &= 127; // Remove first vbr bit. 2249 2250 unsigned Shift = 7; 2251 uint64_t NextBits; 2252 do { 2253 NextBits = MatcherTable[Idx++]; 2254 Val |= (NextBits&127) << Shift; 2255 Shift += 7; 2256 } while (NextBits & 128); 2257 2258 return Val; 2259 } 2260 2261 /// When a match is complete, this method updates uses of interior chain results 2262 /// to use the new results. 2263 void SelectionDAGISel::UpdateChains( 2264 SDNode *NodeToMatch, SDValue InputChain, 2265 SmallVectorImpl<SDNode *> &ChainNodesMatched, bool isMorphNodeTo) { 2266 SmallVector<SDNode*, 4> NowDeadNodes; 2267 2268 // Now that all the normal results are replaced, we replace the chain and 2269 // glue results if present. 2270 if (!ChainNodesMatched.empty()) { 2271 assert(InputChain.getNode() && 2272 "Matched input chains but didn't produce a chain"); 2273 // Loop over all of the nodes we matched that produced a chain result. 2274 // Replace all the chain results with the final chain we ended up with. 2275 for (unsigned i = 0, e = ChainNodesMatched.size(); i != e; ++i) { 2276 SDNode *ChainNode = ChainNodesMatched[i]; 2277 // If ChainNode is null, it's because we replaced it on a previous 2278 // iteration and we cleared it out of the map. Just skip it. 2279 if (!ChainNode) 2280 continue; 2281 2282 assert(ChainNode->getOpcode() != ISD::DELETED_NODE && 2283 "Deleted node left in chain"); 2284 2285 // Don't replace the results of the root node if we're doing a 2286 // MorphNodeTo. 2287 if (ChainNode == NodeToMatch && isMorphNodeTo) 2288 continue; 2289 2290 SDValue ChainVal = SDValue(ChainNode, ChainNode->getNumValues()-1); 2291 if (ChainVal.getValueType() == MVT::Glue) 2292 ChainVal = ChainVal.getValue(ChainVal->getNumValues()-2); 2293 assert(ChainVal.getValueType() == MVT::Other && "Not a chain?"); 2294 SelectionDAG::DAGNodeDeletedListener NDL( 2295 *CurDAG, [&](SDNode *N, SDNode *E) { 2296 std::replace(ChainNodesMatched.begin(), ChainNodesMatched.end(), N, 2297 static_cast<SDNode *>(nullptr)); 2298 }); 2299 if (ChainNode->getOpcode() != ISD::TokenFactor) 2300 ReplaceUses(ChainVal, InputChain); 2301 2302 // If the node became dead and we haven't already seen it, delete it. 2303 if (ChainNode != NodeToMatch && ChainNode->use_empty() && 2304 !llvm::is_contained(NowDeadNodes, ChainNode)) 2305 NowDeadNodes.push_back(ChainNode); 2306 } 2307 } 2308 2309 if (!NowDeadNodes.empty()) 2310 CurDAG->RemoveDeadNodes(NowDeadNodes); 2311 2312 LLVM_DEBUG(dbgs() << "ISEL: Match complete!\n"); 2313 } 2314 2315 /// HandleMergeInputChains - This implements the OPC_EmitMergeInputChains 2316 /// operation for when the pattern matched at least one node with a chains. The 2317 /// input vector contains a list of all of the chained nodes that we match. We 2318 /// must determine if this is a valid thing to cover (i.e. matching it won't 2319 /// induce cycles in the DAG) and if so, creating a TokenFactor node. that will 2320 /// be used as the input node chain for the generated nodes. 2321 static SDValue 2322 HandleMergeInputChains(SmallVectorImpl<SDNode*> &ChainNodesMatched, 2323 SelectionDAG *CurDAG) { 2324 2325 SmallPtrSet<const SDNode *, 16> Visited; 2326 SmallVector<const SDNode *, 8> Worklist; 2327 SmallVector<SDValue, 3> InputChains; 2328 unsigned int Max = 8192; 2329 2330 // Quick exit on trivial merge. 2331 if (ChainNodesMatched.size() == 1) 2332 return ChainNodesMatched[0]->getOperand(0); 2333 2334 // Add chains that aren't already added (internal). Peek through 2335 // token factors. 2336 std::function<void(const SDValue)> AddChains = [&](const SDValue V) { 2337 if (V.getValueType() != MVT::Other) 2338 return; 2339 if (V->getOpcode() == ISD::EntryToken) 2340 return; 2341 if (!Visited.insert(V.getNode()).second) 2342 return; 2343 if (V->getOpcode() == ISD::TokenFactor) { 2344 for (const SDValue &Op : V->op_values()) 2345 AddChains(Op); 2346 } else 2347 InputChains.push_back(V); 2348 }; 2349 2350 for (auto *N : ChainNodesMatched) { 2351 Worklist.push_back(N); 2352 Visited.insert(N); 2353 } 2354 2355 while (!Worklist.empty()) 2356 AddChains(Worklist.pop_back_val()->getOperand(0)); 2357 2358 // Skip the search if there are no chain dependencies. 2359 if (InputChains.size() == 0) 2360 return CurDAG->getEntryNode(); 2361 2362 // If one of these chains is a successor of input, we must have a 2363 // node that is both the predecessor and successor of the 2364 // to-be-merged nodes. Fail. 2365 Visited.clear(); 2366 for (SDValue V : InputChains) 2367 Worklist.push_back(V.getNode()); 2368 2369 for (auto *N : ChainNodesMatched) 2370 if (SDNode::hasPredecessorHelper(N, Visited, Worklist, Max, true)) 2371 return SDValue(); 2372 2373 // Return merged chain. 2374 if (InputChains.size() == 1) 2375 return InputChains[0]; 2376 return CurDAG->getNode(ISD::TokenFactor, SDLoc(ChainNodesMatched[0]), 2377 MVT::Other, InputChains); 2378 } 2379 2380 /// MorphNode - Handle morphing a node in place for the selector. 2381 SDNode *SelectionDAGISel:: 2382 MorphNode(SDNode *Node, unsigned TargetOpc, SDVTList VTList, 2383 ArrayRef<SDValue> Ops, unsigned EmitNodeInfo) { 2384 // It is possible we're using MorphNodeTo to replace a node with no 2385 // normal results with one that has a normal result (or we could be 2386 // adding a chain) and the input could have glue and chains as well. 2387 // In this case we need to shift the operands down. 2388 // FIXME: This is a horrible hack and broken in obscure cases, no worse 2389 // than the old isel though. 2390 int OldGlueResultNo = -1, OldChainResultNo = -1; 2391 2392 unsigned NTMNumResults = Node->getNumValues(); 2393 if (Node->getValueType(NTMNumResults-1) == MVT::Glue) { 2394 OldGlueResultNo = NTMNumResults-1; 2395 if (NTMNumResults != 1 && 2396 Node->getValueType(NTMNumResults-2) == MVT::Other) 2397 OldChainResultNo = NTMNumResults-2; 2398 } else if (Node->getValueType(NTMNumResults-1) == MVT::Other) 2399 OldChainResultNo = NTMNumResults-1; 2400 2401 // Call the underlying SelectionDAG routine to do the transmogrification. Note 2402 // that this deletes operands of the old node that become dead. 2403 SDNode *Res = CurDAG->MorphNodeTo(Node, ~TargetOpc, VTList, Ops); 2404 2405 // MorphNodeTo can operate in two ways: if an existing node with the 2406 // specified operands exists, it can just return it. Otherwise, it 2407 // updates the node in place to have the requested operands. 2408 if (Res == Node) { 2409 // If we updated the node in place, reset the node ID. To the isel, 2410 // this should be just like a newly allocated machine node. 2411 Res->setNodeId(-1); 2412 } 2413 2414 unsigned ResNumResults = Res->getNumValues(); 2415 // Move the glue if needed. 2416 if ((EmitNodeInfo & OPFL_GlueOutput) && OldGlueResultNo != -1 && 2417 (unsigned)OldGlueResultNo != ResNumResults-1) 2418 ReplaceUses(SDValue(Node, OldGlueResultNo), 2419 SDValue(Res, ResNumResults - 1)); 2420 2421 if ((EmitNodeInfo & OPFL_GlueOutput) != 0) 2422 --ResNumResults; 2423 2424 // Move the chain reference if needed. 2425 if ((EmitNodeInfo & OPFL_Chain) && OldChainResultNo != -1 && 2426 (unsigned)OldChainResultNo != ResNumResults-1) 2427 ReplaceUses(SDValue(Node, OldChainResultNo), 2428 SDValue(Res, ResNumResults - 1)); 2429 2430 // Otherwise, no replacement happened because the node already exists. Replace 2431 // Uses of the old node with the new one. 2432 if (Res != Node) { 2433 ReplaceNode(Node, Res); 2434 } else { 2435 EnforceNodeIdInvariant(Res); 2436 } 2437 2438 return Res; 2439 } 2440 2441 /// CheckSame - Implements OP_CheckSame. 2442 LLVM_ATTRIBUTE_ALWAYS_INLINE static bool 2443 CheckSame(const unsigned char *MatcherTable, unsigned &MatcherIndex, SDValue N, 2444 const SmallVectorImpl<std::pair<SDValue, SDNode *>> &RecordedNodes) { 2445 // Accept if it is exactly the same as a previously recorded node. 2446 unsigned RecNo = MatcherTable[MatcherIndex++]; 2447 assert(RecNo < RecordedNodes.size() && "Invalid CheckSame"); 2448 return N == RecordedNodes[RecNo].first; 2449 } 2450 2451 /// CheckChildSame - Implements OP_CheckChildXSame. 2452 LLVM_ATTRIBUTE_ALWAYS_INLINE static bool CheckChildSame( 2453 const unsigned char *MatcherTable, unsigned &MatcherIndex, SDValue N, 2454 const SmallVectorImpl<std::pair<SDValue, SDNode *>> &RecordedNodes, 2455 unsigned ChildNo) { 2456 if (ChildNo >= N.getNumOperands()) 2457 return false; // Match fails if out of range child #. 2458 return ::CheckSame(MatcherTable, MatcherIndex, N.getOperand(ChildNo), 2459 RecordedNodes); 2460 } 2461 2462 /// CheckPatternPredicate - Implements OP_CheckPatternPredicate. 2463 LLVM_ATTRIBUTE_ALWAYS_INLINE static bool 2464 CheckPatternPredicate(const unsigned char *MatcherTable, unsigned &MatcherIndex, 2465 const SelectionDAGISel &SDISel) { 2466 return SDISel.CheckPatternPredicate(MatcherTable[MatcherIndex++]); 2467 } 2468 2469 /// CheckNodePredicate - Implements OP_CheckNodePredicate. 2470 LLVM_ATTRIBUTE_ALWAYS_INLINE static bool 2471 CheckNodePredicate(const unsigned char *MatcherTable, unsigned &MatcherIndex, 2472 const SelectionDAGISel &SDISel, SDNode *N) { 2473 return SDISel.CheckNodePredicate(N, MatcherTable[MatcherIndex++]); 2474 } 2475 2476 LLVM_ATTRIBUTE_ALWAYS_INLINE static bool 2477 CheckOpcode(const unsigned char *MatcherTable, unsigned &MatcherIndex, 2478 SDNode *N) { 2479 uint16_t Opc = MatcherTable[MatcherIndex++]; 2480 Opc |= (unsigned short)MatcherTable[MatcherIndex++] << 8; 2481 return N->getOpcode() == Opc; 2482 } 2483 2484 LLVM_ATTRIBUTE_ALWAYS_INLINE static bool 2485 CheckType(const unsigned char *MatcherTable, unsigned &MatcherIndex, SDValue N, 2486 const TargetLowering *TLI, const DataLayout &DL) { 2487 MVT::SimpleValueType VT = (MVT::SimpleValueType)MatcherTable[MatcherIndex++]; 2488 if (N.getValueType() == VT) return true; 2489 2490 // Handle the case when VT is iPTR. 2491 return VT == MVT::iPTR && N.getValueType() == TLI->getPointerTy(DL); 2492 } 2493 2494 LLVM_ATTRIBUTE_ALWAYS_INLINE static bool 2495 CheckChildType(const unsigned char *MatcherTable, unsigned &MatcherIndex, 2496 SDValue N, const TargetLowering *TLI, const DataLayout &DL, 2497 unsigned ChildNo) { 2498 if (ChildNo >= N.getNumOperands()) 2499 return false; // Match fails if out of range child #. 2500 return ::CheckType(MatcherTable, MatcherIndex, N.getOperand(ChildNo), TLI, 2501 DL); 2502 } 2503 2504 LLVM_ATTRIBUTE_ALWAYS_INLINE static bool 2505 CheckCondCode(const unsigned char *MatcherTable, unsigned &MatcherIndex, 2506 SDValue N) { 2507 return cast<CondCodeSDNode>(N)->get() == 2508 (ISD::CondCode)MatcherTable[MatcherIndex++]; 2509 } 2510 2511 LLVM_ATTRIBUTE_ALWAYS_INLINE static bool 2512 CheckChild2CondCode(const unsigned char *MatcherTable, unsigned &MatcherIndex, 2513 SDValue N) { 2514 if (2 >= N.getNumOperands()) 2515 return false; 2516 return ::CheckCondCode(MatcherTable, MatcherIndex, N.getOperand(2)); 2517 } 2518 2519 LLVM_ATTRIBUTE_ALWAYS_INLINE static bool 2520 CheckValueType(const unsigned char *MatcherTable, unsigned &MatcherIndex, 2521 SDValue N, const TargetLowering *TLI, const DataLayout &DL) { 2522 MVT::SimpleValueType VT = (MVT::SimpleValueType)MatcherTable[MatcherIndex++]; 2523 if (cast<VTSDNode>(N)->getVT() == VT) 2524 return true; 2525 2526 // Handle the case when VT is iPTR. 2527 return VT == MVT::iPTR && cast<VTSDNode>(N)->getVT() == TLI->getPointerTy(DL); 2528 } 2529 2530 // Bit 0 stores the sign of the immediate. The upper bits contain the magnitude 2531 // shifted left by 1. 2532 static uint64_t decodeSignRotatedValue(uint64_t V) { 2533 if ((V & 1) == 0) 2534 return V >> 1; 2535 if (V != 1) 2536 return -(V >> 1); 2537 // There is no such thing as -0 with integers. "-0" really means MININT. 2538 return 1ULL << 63; 2539 } 2540 2541 LLVM_ATTRIBUTE_ALWAYS_INLINE static bool 2542 CheckInteger(const unsigned char *MatcherTable, unsigned &MatcherIndex, 2543 SDValue N) { 2544 int64_t Val = MatcherTable[MatcherIndex++]; 2545 if (Val & 128) 2546 Val = GetVBR(Val, MatcherTable, MatcherIndex); 2547 2548 Val = decodeSignRotatedValue(Val); 2549 2550 ConstantSDNode *C = dyn_cast<ConstantSDNode>(N); 2551 return C && C->getSExtValue() == Val; 2552 } 2553 2554 LLVM_ATTRIBUTE_ALWAYS_INLINE static bool 2555 CheckChildInteger(const unsigned char *MatcherTable, unsigned &MatcherIndex, 2556 SDValue N, unsigned ChildNo) { 2557 if (ChildNo >= N.getNumOperands()) 2558 return false; // Match fails if out of range child #. 2559 return ::CheckInteger(MatcherTable, MatcherIndex, N.getOperand(ChildNo)); 2560 } 2561 2562 LLVM_ATTRIBUTE_ALWAYS_INLINE static bool 2563 CheckAndImm(const unsigned char *MatcherTable, unsigned &MatcherIndex, 2564 SDValue N, const SelectionDAGISel &SDISel) { 2565 int64_t Val = MatcherTable[MatcherIndex++]; 2566 if (Val & 128) 2567 Val = GetVBR(Val, MatcherTable, MatcherIndex); 2568 2569 if (N->getOpcode() != ISD::AND) return false; 2570 2571 ConstantSDNode *C = dyn_cast<ConstantSDNode>(N->getOperand(1)); 2572 return C && SDISel.CheckAndMask(N.getOperand(0), C, Val); 2573 } 2574 2575 LLVM_ATTRIBUTE_ALWAYS_INLINE static bool 2576 CheckOrImm(const unsigned char *MatcherTable, unsigned &MatcherIndex, SDValue N, 2577 const SelectionDAGISel &SDISel) { 2578 int64_t Val = MatcherTable[MatcherIndex++]; 2579 if (Val & 128) 2580 Val = GetVBR(Val, MatcherTable, MatcherIndex); 2581 2582 if (N->getOpcode() != ISD::OR) return false; 2583 2584 ConstantSDNode *C = dyn_cast<ConstantSDNode>(N->getOperand(1)); 2585 return C && SDISel.CheckOrMask(N.getOperand(0), C, Val); 2586 } 2587 2588 /// IsPredicateKnownToFail - If we know how and can do so without pushing a 2589 /// scope, evaluate the current node. If the current predicate is known to 2590 /// fail, set Result=true and return anything. If the current predicate is 2591 /// known to pass, set Result=false and return the MatcherIndex to continue 2592 /// with. If the current predicate is unknown, set Result=false and return the 2593 /// MatcherIndex to continue with. 2594 static unsigned IsPredicateKnownToFail(const unsigned char *Table, 2595 unsigned Index, SDValue N, 2596 bool &Result, 2597 const SelectionDAGISel &SDISel, 2598 SmallVectorImpl<std::pair<SDValue, SDNode*>> &RecordedNodes) { 2599 switch (Table[Index++]) { 2600 default: 2601 Result = false; 2602 return Index-1; // Could not evaluate this predicate. 2603 case SelectionDAGISel::OPC_CheckSame: 2604 Result = !::CheckSame(Table, Index, N, RecordedNodes); 2605 return Index; 2606 case SelectionDAGISel::OPC_CheckChild0Same: 2607 case SelectionDAGISel::OPC_CheckChild1Same: 2608 case SelectionDAGISel::OPC_CheckChild2Same: 2609 case SelectionDAGISel::OPC_CheckChild3Same: 2610 Result = !::CheckChildSame(Table, Index, N, RecordedNodes, 2611 Table[Index-1] - SelectionDAGISel::OPC_CheckChild0Same); 2612 return Index; 2613 case SelectionDAGISel::OPC_CheckPatternPredicate: 2614 Result = !::CheckPatternPredicate(Table, Index, SDISel); 2615 return Index; 2616 case SelectionDAGISel::OPC_CheckPredicate: 2617 Result = !::CheckNodePredicate(Table, Index, SDISel, N.getNode()); 2618 return Index; 2619 case SelectionDAGISel::OPC_CheckOpcode: 2620 Result = !::CheckOpcode(Table, Index, N.getNode()); 2621 return Index; 2622 case SelectionDAGISel::OPC_CheckType: 2623 Result = !::CheckType(Table, Index, N, SDISel.TLI, 2624 SDISel.CurDAG->getDataLayout()); 2625 return Index; 2626 case SelectionDAGISel::OPC_CheckTypeRes: { 2627 unsigned Res = Table[Index++]; 2628 Result = !::CheckType(Table, Index, N.getValue(Res), SDISel.TLI, 2629 SDISel.CurDAG->getDataLayout()); 2630 return Index; 2631 } 2632 case SelectionDAGISel::OPC_CheckChild0Type: 2633 case SelectionDAGISel::OPC_CheckChild1Type: 2634 case SelectionDAGISel::OPC_CheckChild2Type: 2635 case SelectionDAGISel::OPC_CheckChild3Type: 2636 case SelectionDAGISel::OPC_CheckChild4Type: 2637 case SelectionDAGISel::OPC_CheckChild5Type: 2638 case SelectionDAGISel::OPC_CheckChild6Type: 2639 case SelectionDAGISel::OPC_CheckChild7Type: 2640 Result = !::CheckChildType( 2641 Table, Index, N, SDISel.TLI, SDISel.CurDAG->getDataLayout(), 2642 Table[Index - 1] - SelectionDAGISel::OPC_CheckChild0Type); 2643 return Index; 2644 case SelectionDAGISel::OPC_CheckCondCode: 2645 Result = !::CheckCondCode(Table, Index, N); 2646 return Index; 2647 case SelectionDAGISel::OPC_CheckChild2CondCode: 2648 Result = !::CheckChild2CondCode(Table, Index, N); 2649 return Index; 2650 case SelectionDAGISel::OPC_CheckValueType: 2651 Result = !::CheckValueType(Table, Index, N, SDISel.TLI, 2652 SDISel.CurDAG->getDataLayout()); 2653 return Index; 2654 case SelectionDAGISel::OPC_CheckInteger: 2655 Result = !::CheckInteger(Table, Index, N); 2656 return Index; 2657 case SelectionDAGISel::OPC_CheckChild0Integer: 2658 case SelectionDAGISel::OPC_CheckChild1Integer: 2659 case SelectionDAGISel::OPC_CheckChild2Integer: 2660 case SelectionDAGISel::OPC_CheckChild3Integer: 2661 case SelectionDAGISel::OPC_CheckChild4Integer: 2662 Result = !::CheckChildInteger(Table, Index, N, 2663 Table[Index-1] - SelectionDAGISel::OPC_CheckChild0Integer); 2664 return Index; 2665 case SelectionDAGISel::OPC_CheckAndImm: 2666 Result = !::CheckAndImm(Table, Index, N, SDISel); 2667 return Index; 2668 case SelectionDAGISel::OPC_CheckOrImm: 2669 Result = !::CheckOrImm(Table, Index, N, SDISel); 2670 return Index; 2671 } 2672 } 2673 2674 namespace { 2675 2676 struct MatchScope { 2677 /// FailIndex - If this match fails, this is the index to continue with. 2678 unsigned FailIndex; 2679 2680 /// NodeStack - The node stack when the scope was formed. 2681 SmallVector<SDValue, 4> NodeStack; 2682 2683 /// NumRecordedNodes - The number of recorded nodes when the scope was formed. 2684 unsigned NumRecordedNodes; 2685 2686 /// NumMatchedMemRefs - The number of matched memref entries. 2687 unsigned NumMatchedMemRefs; 2688 2689 /// InputChain/InputGlue - The current chain/glue 2690 SDValue InputChain, InputGlue; 2691 2692 /// HasChainNodesMatched - True if the ChainNodesMatched list is non-empty. 2693 bool HasChainNodesMatched; 2694 }; 2695 2696 /// \A DAG update listener to keep the matching state 2697 /// (i.e. RecordedNodes and MatchScope) uptodate if the target is allowed to 2698 /// change the DAG while matching. X86 addressing mode matcher is an example 2699 /// for this. 2700 class MatchStateUpdater : public SelectionDAG::DAGUpdateListener 2701 { 2702 SDNode **NodeToMatch; 2703 SmallVectorImpl<std::pair<SDValue, SDNode *>> &RecordedNodes; 2704 SmallVectorImpl<MatchScope> &MatchScopes; 2705 2706 public: 2707 MatchStateUpdater(SelectionDAG &DAG, SDNode **NodeToMatch, 2708 SmallVectorImpl<std::pair<SDValue, SDNode *>> &RN, 2709 SmallVectorImpl<MatchScope> &MS) 2710 : SelectionDAG::DAGUpdateListener(DAG), NodeToMatch(NodeToMatch), 2711 RecordedNodes(RN), MatchScopes(MS) {} 2712 2713 void NodeDeleted(SDNode *N, SDNode *E) override { 2714 // Some early-returns here to avoid the search if we deleted the node or 2715 // if the update comes from MorphNodeTo (MorphNodeTo is the last thing we 2716 // do, so it's unnecessary to update matching state at that point). 2717 // Neither of these can occur currently because we only install this 2718 // update listener during matching a complex patterns. 2719 if (!E || E->isMachineOpcode()) 2720 return; 2721 // Check if NodeToMatch was updated. 2722 if (N == *NodeToMatch) 2723 *NodeToMatch = E; 2724 // Performing linear search here does not matter because we almost never 2725 // run this code. You'd have to have a CSE during complex pattern 2726 // matching. 2727 for (auto &I : RecordedNodes) 2728 if (I.first.getNode() == N) 2729 I.first.setNode(E); 2730 2731 for (auto &I : MatchScopes) 2732 for (auto &J : I.NodeStack) 2733 if (J.getNode() == N) 2734 J.setNode(E); 2735 } 2736 }; 2737 2738 } // end anonymous namespace 2739 2740 void SelectionDAGISel::SelectCodeCommon(SDNode *NodeToMatch, 2741 const unsigned char *MatcherTable, 2742 unsigned TableSize) { 2743 // FIXME: Should these even be selected? Handle these cases in the caller? 2744 switch (NodeToMatch->getOpcode()) { 2745 default: 2746 break; 2747 case ISD::EntryToken: // These nodes remain the same. 2748 case ISD::BasicBlock: 2749 case ISD::Register: 2750 case ISD::RegisterMask: 2751 case ISD::HANDLENODE: 2752 case ISD::MDNODE_SDNODE: 2753 case ISD::TargetConstant: 2754 case ISD::TargetConstantFP: 2755 case ISD::TargetConstantPool: 2756 case ISD::TargetFrameIndex: 2757 case ISD::TargetExternalSymbol: 2758 case ISD::MCSymbol: 2759 case ISD::TargetBlockAddress: 2760 case ISD::TargetJumpTable: 2761 case ISD::TargetGlobalTLSAddress: 2762 case ISD::TargetGlobalAddress: 2763 case ISD::TokenFactor: 2764 case ISD::CopyFromReg: 2765 case ISD::CopyToReg: 2766 case ISD::EH_LABEL: 2767 case ISD::ANNOTATION_LABEL: 2768 case ISD::LIFETIME_START: 2769 case ISD::LIFETIME_END: 2770 case ISD::PSEUDO_PROBE: 2771 NodeToMatch->setNodeId(-1); // Mark selected. 2772 return; 2773 case ISD::AssertSext: 2774 case ISD::AssertZext: 2775 case ISD::AssertAlign: 2776 ReplaceUses(SDValue(NodeToMatch, 0), NodeToMatch->getOperand(0)); 2777 CurDAG->RemoveDeadNode(NodeToMatch); 2778 return; 2779 case ISD::INLINEASM: 2780 case ISD::INLINEASM_BR: 2781 Select_INLINEASM(NodeToMatch); 2782 return; 2783 case ISD::READ_REGISTER: 2784 Select_READ_REGISTER(NodeToMatch); 2785 return; 2786 case ISD::WRITE_REGISTER: 2787 Select_WRITE_REGISTER(NodeToMatch); 2788 return; 2789 case ISD::UNDEF: 2790 Select_UNDEF(NodeToMatch); 2791 return; 2792 case ISD::FREEZE: 2793 Select_FREEZE(NodeToMatch); 2794 return; 2795 case ISD::ARITH_FENCE: 2796 Select_ARITH_FENCE(NodeToMatch); 2797 return; 2798 } 2799 2800 assert(!NodeToMatch->isMachineOpcode() && "Node already selected!"); 2801 2802 // Set up the node stack with NodeToMatch as the only node on the stack. 2803 SmallVector<SDValue, 8> NodeStack; 2804 SDValue N = SDValue(NodeToMatch, 0); 2805 NodeStack.push_back(N); 2806 2807 // MatchScopes - Scopes used when matching, if a match failure happens, this 2808 // indicates where to continue checking. 2809 SmallVector<MatchScope, 8> MatchScopes; 2810 2811 // RecordedNodes - This is the set of nodes that have been recorded by the 2812 // state machine. The second value is the parent of the node, or null if the 2813 // root is recorded. 2814 SmallVector<std::pair<SDValue, SDNode*>, 8> RecordedNodes; 2815 2816 // MatchedMemRefs - This is the set of MemRef's we've seen in the input 2817 // pattern. 2818 SmallVector<MachineMemOperand*, 2> MatchedMemRefs; 2819 2820 // These are the current input chain and glue for use when generating nodes. 2821 // Various Emit operations change these. For example, emitting a copytoreg 2822 // uses and updates these. 2823 SDValue InputChain, InputGlue; 2824 2825 // ChainNodesMatched - If a pattern matches nodes that have input/output 2826 // chains, the OPC_EmitMergeInputChains operation is emitted which indicates 2827 // which ones they are. The result is captured into this list so that we can 2828 // update the chain results when the pattern is complete. 2829 SmallVector<SDNode*, 3> ChainNodesMatched; 2830 2831 LLVM_DEBUG(dbgs() << "ISEL: Starting pattern match\n"); 2832 2833 // Determine where to start the interpreter. Normally we start at opcode #0, 2834 // but if the state machine starts with an OPC_SwitchOpcode, then we 2835 // accelerate the first lookup (which is guaranteed to be hot) with the 2836 // OpcodeOffset table. 2837 unsigned MatcherIndex = 0; 2838 2839 if (!OpcodeOffset.empty()) { 2840 // Already computed the OpcodeOffset table, just index into it. 2841 if (N.getOpcode() < OpcodeOffset.size()) 2842 MatcherIndex = OpcodeOffset[N.getOpcode()]; 2843 LLVM_DEBUG(dbgs() << " Initial Opcode index to " << MatcherIndex << "\n"); 2844 2845 } else if (MatcherTable[0] == OPC_SwitchOpcode) { 2846 // Otherwise, the table isn't computed, but the state machine does start 2847 // with an OPC_SwitchOpcode instruction. Populate the table now, since this 2848 // is the first time we're selecting an instruction. 2849 unsigned Idx = 1; 2850 while (true) { 2851 // Get the size of this case. 2852 unsigned CaseSize = MatcherTable[Idx++]; 2853 if (CaseSize & 128) 2854 CaseSize = GetVBR(CaseSize, MatcherTable, Idx); 2855 if (CaseSize == 0) break; 2856 2857 // Get the opcode, add the index to the table. 2858 uint16_t Opc = MatcherTable[Idx++]; 2859 Opc |= (unsigned short)MatcherTable[Idx++] << 8; 2860 if (Opc >= OpcodeOffset.size()) 2861 OpcodeOffset.resize((Opc+1)*2); 2862 OpcodeOffset[Opc] = Idx; 2863 Idx += CaseSize; 2864 } 2865 2866 // Okay, do the lookup for the first opcode. 2867 if (N.getOpcode() < OpcodeOffset.size()) 2868 MatcherIndex = OpcodeOffset[N.getOpcode()]; 2869 } 2870 2871 while (true) { 2872 assert(MatcherIndex < TableSize && "Invalid index"); 2873 #ifndef NDEBUG 2874 unsigned CurrentOpcodeIndex = MatcherIndex; 2875 #endif 2876 BuiltinOpcodes Opcode = (BuiltinOpcodes)MatcherTable[MatcherIndex++]; 2877 switch (Opcode) { 2878 case OPC_Scope: { 2879 // Okay, the semantics of this operation are that we should push a scope 2880 // then evaluate the first child. However, pushing a scope only to have 2881 // the first check fail (which then pops it) is inefficient. If we can 2882 // determine immediately that the first check (or first several) will 2883 // immediately fail, don't even bother pushing a scope for them. 2884 unsigned FailIndex; 2885 2886 while (true) { 2887 unsigned NumToSkip = MatcherTable[MatcherIndex++]; 2888 if (NumToSkip & 128) 2889 NumToSkip = GetVBR(NumToSkip, MatcherTable, MatcherIndex); 2890 // Found the end of the scope with no match. 2891 if (NumToSkip == 0) { 2892 FailIndex = 0; 2893 break; 2894 } 2895 2896 FailIndex = MatcherIndex+NumToSkip; 2897 2898 unsigned MatcherIndexOfPredicate = MatcherIndex; 2899 (void)MatcherIndexOfPredicate; // silence warning. 2900 2901 // If we can't evaluate this predicate without pushing a scope (e.g. if 2902 // it is a 'MoveParent') or if the predicate succeeds on this node, we 2903 // push the scope and evaluate the full predicate chain. 2904 bool Result; 2905 MatcherIndex = IsPredicateKnownToFail(MatcherTable, MatcherIndex, N, 2906 Result, *this, RecordedNodes); 2907 if (!Result) 2908 break; 2909 2910 LLVM_DEBUG( 2911 dbgs() << " Skipped scope entry (due to false predicate) at " 2912 << "index " << MatcherIndexOfPredicate << ", continuing at " 2913 << FailIndex << "\n"); 2914 ++NumDAGIselRetries; 2915 2916 // Otherwise, we know that this case of the Scope is guaranteed to fail, 2917 // move to the next case. 2918 MatcherIndex = FailIndex; 2919 } 2920 2921 // If the whole scope failed to match, bail. 2922 if (FailIndex == 0) break; 2923 2924 // Push a MatchScope which indicates where to go if the first child fails 2925 // to match. 2926 MatchScope NewEntry; 2927 NewEntry.FailIndex = FailIndex; 2928 NewEntry.NodeStack.append(NodeStack.begin(), NodeStack.end()); 2929 NewEntry.NumRecordedNodes = RecordedNodes.size(); 2930 NewEntry.NumMatchedMemRefs = MatchedMemRefs.size(); 2931 NewEntry.InputChain = InputChain; 2932 NewEntry.InputGlue = InputGlue; 2933 NewEntry.HasChainNodesMatched = !ChainNodesMatched.empty(); 2934 MatchScopes.push_back(NewEntry); 2935 continue; 2936 } 2937 case OPC_RecordNode: { 2938 // Remember this node, it may end up being an operand in the pattern. 2939 SDNode *Parent = nullptr; 2940 if (NodeStack.size() > 1) 2941 Parent = NodeStack[NodeStack.size()-2].getNode(); 2942 RecordedNodes.push_back(std::make_pair(N, Parent)); 2943 continue; 2944 } 2945 2946 case OPC_RecordChild0: case OPC_RecordChild1: 2947 case OPC_RecordChild2: case OPC_RecordChild3: 2948 case OPC_RecordChild4: case OPC_RecordChild5: 2949 case OPC_RecordChild6: case OPC_RecordChild7: { 2950 unsigned ChildNo = Opcode-OPC_RecordChild0; 2951 if (ChildNo >= N.getNumOperands()) 2952 break; // Match fails if out of range child #. 2953 2954 RecordedNodes.push_back(std::make_pair(N->getOperand(ChildNo), 2955 N.getNode())); 2956 continue; 2957 } 2958 case OPC_RecordMemRef: 2959 if (auto *MN = dyn_cast<MemSDNode>(N)) 2960 MatchedMemRefs.push_back(MN->getMemOperand()); 2961 else { 2962 LLVM_DEBUG(dbgs() << "Expected MemSDNode "; N->dump(CurDAG); 2963 dbgs() << '\n'); 2964 } 2965 2966 continue; 2967 2968 case OPC_CaptureGlueInput: 2969 // If the current node has an input glue, capture it in InputGlue. 2970 if (N->getNumOperands() != 0 && 2971 N->getOperand(N->getNumOperands()-1).getValueType() == MVT::Glue) 2972 InputGlue = N->getOperand(N->getNumOperands()-1); 2973 continue; 2974 2975 case OPC_MoveChild: { 2976 unsigned ChildNo = MatcherTable[MatcherIndex++]; 2977 if (ChildNo >= N.getNumOperands()) 2978 break; // Match fails if out of range child #. 2979 N = N.getOperand(ChildNo); 2980 NodeStack.push_back(N); 2981 continue; 2982 } 2983 2984 case OPC_MoveChild0: case OPC_MoveChild1: 2985 case OPC_MoveChild2: case OPC_MoveChild3: 2986 case OPC_MoveChild4: case OPC_MoveChild5: 2987 case OPC_MoveChild6: case OPC_MoveChild7: { 2988 unsigned ChildNo = Opcode-OPC_MoveChild0; 2989 if (ChildNo >= N.getNumOperands()) 2990 break; // Match fails if out of range child #. 2991 N = N.getOperand(ChildNo); 2992 NodeStack.push_back(N); 2993 continue; 2994 } 2995 2996 case OPC_MoveParent: 2997 // Pop the current node off the NodeStack. 2998 NodeStack.pop_back(); 2999 assert(!NodeStack.empty() && "Node stack imbalance!"); 3000 N = NodeStack.back(); 3001 continue; 3002 3003 case OPC_CheckSame: 3004 if (!::CheckSame(MatcherTable, MatcherIndex, N, RecordedNodes)) break; 3005 continue; 3006 3007 case OPC_CheckChild0Same: case OPC_CheckChild1Same: 3008 case OPC_CheckChild2Same: case OPC_CheckChild3Same: 3009 if (!::CheckChildSame(MatcherTable, MatcherIndex, N, RecordedNodes, 3010 Opcode-OPC_CheckChild0Same)) 3011 break; 3012 continue; 3013 3014 case OPC_CheckPatternPredicate: 3015 if (!::CheckPatternPredicate(MatcherTable, MatcherIndex, *this)) break; 3016 continue; 3017 case OPC_CheckPredicate: 3018 if (!::CheckNodePredicate(MatcherTable, MatcherIndex, *this, 3019 N.getNode())) 3020 break; 3021 continue; 3022 case OPC_CheckPredicateWithOperands: { 3023 unsigned OpNum = MatcherTable[MatcherIndex++]; 3024 SmallVector<SDValue, 8> Operands; 3025 3026 for (unsigned i = 0; i < OpNum; ++i) 3027 Operands.push_back(RecordedNodes[MatcherTable[MatcherIndex++]].first); 3028 3029 unsigned PredNo = MatcherTable[MatcherIndex++]; 3030 if (!CheckNodePredicateWithOperands(N.getNode(), PredNo, Operands)) 3031 break; 3032 continue; 3033 } 3034 case OPC_CheckComplexPat: { 3035 unsigned CPNum = MatcherTable[MatcherIndex++]; 3036 unsigned RecNo = MatcherTable[MatcherIndex++]; 3037 assert(RecNo < RecordedNodes.size() && "Invalid CheckComplexPat"); 3038 3039 // If target can modify DAG during matching, keep the matching state 3040 // consistent. 3041 std::unique_ptr<MatchStateUpdater> MSU; 3042 if (ComplexPatternFuncMutatesDAG()) 3043 MSU.reset(new MatchStateUpdater(*CurDAG, &NodeToMatch, RecordedNodes, 3044 MatchScopes)); 3045 3046 if (!CheckComplexPattern(NodeToMatch, RecordedNodes[RecNo].second, 3047 RecordedNodes[RecNo].first, CPNum, 3048 RecordedNodes)) 3049 break; 3050 continue; 3051 } 3052 case OPC_CheckOpcode: 3053 if (!::CheckOpcode(MatcherTable, MatcherIndex, N.getNode())) break; 3054 continue; 3055 3056 case OPC_CheckType: 3057 if (!::CheckType(MatcherTable, MatcherIndex, N, TLI, 3058 CurDAG->getDataLayout())) 3059 break; 3060 continue; 3061 3062 case OPC_CheckTypeRes: { 3063 unsigned Res = MatcherTable[MatcherIndex++]; 3064 if (!::CheckType(MatcherTable, MatcherIndex, N.getValue(Res), TLI, 3065 CurDAG->getDataLayout())) 3066 break; 3067 continue; 3068 } 3069 3070 case OPC_SwitchOpcode: { 3071 unsigned CurNodeOpcode = N.getOpcode(); 3072 unsigned SwitchStart = MatcherIndex-1; (void)SwitchStart; 3073 unsigned CaseSize; 3074 while (true) { 3075 // Get the size of this case. 3076 CaseSize = MatcherTable[MatcherIndex++]; 3077 if (CaseSize & 128) 3078 CaseSize = GetVBR(CaseSize, MatcherTable, MatcherIndex); 3079 if (CaseSize == 0) break; 3080 3081 uint16_t Opc = MatcherTable[MatcherIndex++]; 3082 Opc |= (unsigned short)MatcherTable[MatcherIndex++] << 8; 3083 3084 // If the opcode matches, then we will execute this case. 3085 if (CurNodeOpcode == Opc) 3086 break; 3087 3088 // Otherwise, skip over this case. 3089 MatcherIndex += CaseSize; 3090 } 3091 3092 // If no cases matched, bail out. 3093 if (CaseSize == 0) break; 3094 3095 // Otherwise, execute the case we found. 3096 LLVM_DEBUG(dbgs() << " OpcodeSwitch from " << SwitchStart << " to " 3097 << MatcherIndex << "\n"); 3098 continue; 3099 } 3100 3101 case OPC_SwitchType: { 3102 MVT CurNodeVT = N.getSimpleValueType(); 3103 unsigned SwitchStart = MatcherIndex-1; (void)SwitchStart; 3104 unsigned CaseSize; 3105 while (true) { 3106 // Get the size of this case. 3107 CaseSize = MatcherTable[MatcherIndex++]; 3108 if (CaseSize & 128) 3109 CaseSize = GetVBR(CaseSize, MatcherTable, MatcherIndex); 3110 if (CaseSize == 0) break; 3111 3112 MVT CaseVT = (MVT::SimpleValueType)MatcherTable[MatcherIndex++]; 3113 if (CaseVT == MVT::iPTR) 3114 CaseVT = TLI->getPointerTy(CurDAG->getDataLayout()); 3115 3116 // If the VT matches, then we will execute this case. 3117 if (CurNodeVT == CaseVT) 3118 break; 3119 3120 // Otherwise, skip over this case. 3121 MatcherIndex += CaseSize; 3122 } 3123 3124 // If no cases matched, bail out. 3125 if (CaseSize == 0) break; 3126 3127 // Otherwise, execute the case we found. 3128 LLVM_DEBUG(dbgs() << " TypeSwitch[" << EVT(CurNodeVT).getEVTString() 3129 << "] from " << SwitchStart << " to " << MatcherIndex 3130 << '\n'); 3131 continue; 3132 } 3133 case OPC_CheckChild0Type: case OPC_CheckChild1Type: 3134 case OPC_CheckChild2Type: case OPC_CheckChild3Type: 3135 case OPC_CheckChild4Type: case OPC_CheckChild5Type: 3136 case OPC_CheckChild6Type: case OPC_CheckChild7Type: 3137 if (!::CheckChildType(MatcherTable, MatcherIndex, N, TLI, 3138 CurDAG->getDataLayout(), 3139 Opcode - OPC_CheckChild0Type)) 3140 break; 3141 continue; 3142 case OPC_CheckCondCode: 3143 if (!::CheckCondCode(MatcherTable, MatcherIndex, N)) break; 3144 continue; 3145 case OPC_CheckChild2CondCode: 3146 if (!::CheckChild2CondCode(MatcherTable, MatcherIndex, N)) break; 3147 continue; 3148 case OPC_CheckValueType: 3149 if (!::CheckValueType(MatcherTable, MatcherIndex, N, TLI, 3150 CurDAG->getDataLayout())) 3151 break; 3152 continue; 3153 case OPC_CheckInteger: 3154 if (!::CheckInteger(MatcherTable, MatcherIndex, N)) break; 3155 continue; 3156 case OPC_CheckChild0Integer: case OPC_CheckChild1Integer: 3157 case OPC_CheckChild2Integer: case OPC_CheckChild3Integer: 3158 case OPC_CheckChild4Integer: 3159 if (!::CheckChildInteger(MatcherTable, MatcherIndex, N, 3160 Opcode-OPC_CheckChild0Integer)) break; 3161 continue; 3162 case OPC_CheckAndImm: 3163 if (!::CheckAndImm(MatcherTable, MatcherIndex, N, *this)) break; 3164 continue; 3165 case OPC_CheckOrImm: 3166 if (!::CheckOrImm(MatcherTable, MatcherIndex, N, *this)) break; 3167 continue; 3168 case OPC_CheckImmAllOnesV: 3169 if (!ISD::isConstantSplatVectorAllOnes(N.getNode())) 3170 break; 3171 continue; 3172 case OPC_CheckImmAllZerosV: 3173 if (!ISD::isConstantSplatVectorAllZeros(N.getNode())) 3174 break; 3175 continue; 3176 3177 case OPC_CheckFoldableChainNode: { 3178 assert(NodeStack.size() != 1 && "No parent node"); 3179 // Verify that all intermediate nodes between the root and this one have 3180 // a single use (ignoring chains, which are handled in UpdateChains). 3181 bool HasMultipleUses = false; 3182 for (unsigned i = 1, e = NodeStack.size()-1; i != e; ++i) { 3183 unsigned NNonChainUses = 0; 3184 SDNode *NS = NodeStack[i].getNode(); 3185 for (auto UI = NS->use_begin(), UE = NS->use_end(); UI != UE; ++UI) 3186 if (UI.getUse().getValueType() != MVT::Other) 3187 if (++NNonChainUses > 1) { 3188 HasMultipleUses = true; 3189 break; 3190 } 3191 if (HasMultipleUses) break; 3192 } 3193 if (HasMultipleUses) break; 3194 3195 // Check to see that the target thinks this is profitable to fold and that 3196 // we can fold it without inducing cycles in the graph. 3197 if (!IsProfitableToFold(N, NodeStack[NodeStack.size()-2].getNode(), 3198 NodeToMatch) || 3199 !IsLegalToFold(N, NodeStack[NodeStack.size()-2].getNode(), 3200 NodeToMatch, OptLevel, 3201 true/*We validate our own chains*/)) 3202 break; 3203 3204 continue; 3205 } 3206 case OPC_EmitInteger: 3207 case OPC_EmitStringInteger: { 3208 MVT::SimpleValueType VT = 3209 (MVT::SimpleValueType)MatcherTable[MatcherIndex++]; 3210 int64_t Val = MatcherTable[MatcherIndex++]; 3211 if (Val & 128) 3212 Val = GetVBR(Val, MatcherTable, MatcherIndex); 3213 if (Opcode == OPC_EmitInteger) 3214 Val = decodeSignRotatedValue(Val); 3215 RecordedNodes.push_back(std::pair<SDValue, SDNode*>( 3216 CurDAG->getTargetConstant(Val, SDLoc(NodeToMatch), 3217 VT), nullptr)); 3218 continue; 3219 } 3220 case OPC_EmitRegister: { 3221 MVT::SimpleValueType VT = 3222 (MVT::SimpleValueType)MatcherTable[MatcherIndex++]; 3223 unsigned RegNo = MatcherTable[MatcherIndex++]; 3224 RecordedNodes.push_back(std::pair<SDValue, SDNode*>( 3225 CurDAG->getRegister(RegNo, VT), nullptr)); 3226 continue; 3227 } 3228 case OPC_EmitRegister2: { 3229 // For targets w/ more than 256 register names, the register enum 3230 // values are stored in two bytes in the matcher table (just like 3231 // opcodes). 3232 MVT::SimpleValueType VT = 3233 (MVT::SimpleValueType)MatcherTable[MatcherIndex++]; 3234 unsigned RegNo = MatcherTable[MatcherIndex++]; 3235 RegNo |= MatcherTable[MatcherIndex++] << 8; 3236 RecordedNodes.push_back(std::pair<SDValue, SDNode*>( 3237 CurDAG->getRegister(RegNo, VT), nullptr)); 3238 continue; 3239 } 3240 3241 case OPC_EmitConvertToTarget: { 3242 // Convert from IMM/FPIMM to target version. 3243 unsigned RecNo = MatcherTable[MatcherIndex++]; 3244 assert(RecNo < RecordedNodes.size() && "Invalid EmitConvertToTarget"); 3245 SDValue Imm = RecordedNodes[RecNo].first; 3246 3247 if (Imm->getOpcode() == ISD::Constant) { 3248 const ConstantInt *Val=cast<ConstantSDNode>(Imm)->getConstantIntValue(); 3249 Imm = CurDAG->getTargetConstant(*Val, SDLoc(NodeToMatch), 3250 Imm.getValueType()); 3251 } else if (Imm->getOpcode() == ISD::ConstantFP) { 3252 const ConstantFP *Val=cast<ConstantFPSDNode>(Imm)->getConstantFPValue(); 3253 Imm = CurDAG->getTargetConstantFP(*Val, SDLoc(NodeToMatch), 3254 Imm.getValueType()); 3255 } 3256 3257 RecordedNodes.push_back(std::make_pair(Imm, RecordedNodes[RecNo].second)); 3258 continue; 3259 } 3260 3261 case OPC_EmitMergeInputChains1_0: // OPC_EmitMergeInputChains, 1, 0 3262 case OPC_EmitMergeInputChains1_1: // OPC_EmitMergeInputChains, 1, 1 3263 case OPC_EmitMergeInputChains1_2: { // OPC_EmitMergeInputChains, 1, 2 3264 // These are space-optimized forms of OPC_EmitMergeInputChains. 3265 assert(!InputChain.getNode() && 3266 "EmitMergeInputChains should be the first chain producing node"); 3267 assert(ChainNodesMatched.empty() && 3268 "Should only have one EmitMergeInputChains per match"); 3269 3270 // Read all of the chained nodes. 3271 unsigned RecNo = Opcode - OPC_EmitMergeInputChains1_0; 3272 assert(RecNo < RecordedNodes.size() && "Invalid EmitMergeInputChains"); 3273 ChainNodesMatched.push_back(RecordedNodes[RecNo].first.getNode()); 3274 3275 // If the chained node is not the root, we can't fold it if it has 3276 // multiple uses. 3277 // FIXME: What if other value results of the node have uses not matched 3278 // by this pattern? 3279 if (ChainNodesMatched.back() != NodeToMatch && 3280 !RecordedNodes[RecNo].first.hasOneUse()) { 3281 ChainNodesMatched.clear(); 3282 break; 3283 } 3284 3285 // Merge the input chains if they are not intra-pattern references. 3286 InputChain = HandleMergeInputChains(ChainNodesMatched, CurDAG); 3287 3288 if (!InputChain.getNode()) 3289 break; // Failed to merge. 3290 continue; 3291 } 3292 3293 case OPC_EmitMergeInputChains: { 3294 assert(!InputChain.getNode() && 3295 "EmitMergeInputChains should be the first chain producing node"); 3296 // This node gets a list of nodes we matched in the input that have 3297 // chains. We want to token factor all of the input chains to these nodes 3298 // together. However, if any of the input chains is actually one of the 3299 // nodes matched in this pattern, then we have an intra-match reference. 3300 // Ignore these because the newly token factored chain should not refer to 3301 // the old nodes. 3302 unsigned NumChains = MatcherTable[MatcherIndex++]; 3303 assert(NumChains != 0 && "Can't TF zero chains"); 3304 3305 assert(ChainNodesMatched.empty() && 3306 "Should only have one EmitMergeInputChains per match"); 3307 3308 // Read all of the chained nodes. 3309 for (unsigned i = 0; i != NumChains; ++i) { 3310 unsigned RecNo = MatcherTable[MatcherIndex++]; 3311 assert(RecNo < RecordedNodes.size() && "Invalid EmitMergeInputChains"); 3312 ChainNodesMatched.push_back(RecordedNodes[RecNo].first.getNode()); 3313 3314 // If the chained node is not the root, we can't fold it if it has 3315 // multiple uses. 3316 // FIXME: What if other value results of the node have uses not matched 3317 // by this pattern? 3318 if (ChainNodesMatched.back() != NodeToMatch && 3319 !RecordedNodes[RecNo].first.hasOneUse()) { 3320 ChainNodesMatched.clear(); 3321 break; 3322 } 3323 } 3324 3325 // If the inner loop broke out, the match fails. 3326 if (ChainNodesMatched.empty()) 3327 break; 3328 3329 // Merge the input chains if they are not intra-pattern references. 3330 InputChain = HandleMergeInputChains(ChainNodesMatched, CurDAG); 3331 3332 if (!InputChain.getNode()) 3333 break; // Failed to merge. 3334 3335 continue; 3336 } 3337 3338 case OPC_EmitCopyToReg: 3339 case OPC_EmitCopyToReg2: { 3340 unsigned RecNo = MatcherTable[MatcherIndex++]; 3341 assert(RecNo < RecordedNodes.size() && "Invalid EmitCopyToReg"); 3342 unsigned DestPhysReg = MatcherTable[MatcherIndex++]; 3343 if (Opcode == OPC_EmitCopyToReg2) 3344 DestPhysReg |= MatcherTable[MatcherIndex++] << 8; 3345 3346 if (!InputChain.getNode()) 3347 InputChain = CurDAG->getEntryNode(); 3348 3349 InputChain = CurDAG->getCopyToReg(InputChain, SDLoc(NodeToMatch), 3350 DestPhysReg, RecordedNodes[RecNo].first, 3351 InputGlue); 3352 3353 InputGlue = InputChain.getValue(1); 3354 continue; 3355 } 3356 3357 case OPC_EmitNodeXForm: { 3358 unsigned XFormNo = MatcherTable[MatcherIndex++]; 3359 unsigned RecNo = MatcherTable[MatcherIndex++]; 3360 assert(RecNo < RecordedNodes.size() && "Invalid EmitNodeXForm"); 3361 SDValue Res = RunSDNodeXForm(RecordedNodes[RecNo].first, XFormNo); 3362 RecordedNodes.push_back(std::pair<SDValue,SDNode*>(Res, nullptr)); 3363 continue; 3364 } 3365 case OPC_Coverage: { 3366 // This is emitted right before MorphNode/EmitNode. 3367 // So it should be safe to assume that this node has been selected 3368 unsigned index = MatcherTable[MatcherIndex++]; 3369 index |= (MatcherTable[MatcherIndex++] << 8); 3370 dbgs() << "COVERED: " << getPatternForIndex(index) << "\n"; 3371 dbgs() << "INCLUDED: " << getIncludePathForIndex(index) << "\n"; 3372 continue; 3373 } 3374 3375 case OPC_EmitNode: case OPC_MorphNodeTo: 3376 case OPC_EmitNode0: case OPC_EmitNode1: case OPC_EmitNode2: 3377 case OPC_MorphNodeTo0: case OPC_MorphNodeTo1: case OPC_MorphNodeTo2: { 3378 uint16_t TargetOpc = MatcherTable[MatcherIndex++]; 3379 TargetOpc |= (unsigned short)MatcherTable[MatcherIndex++] << 8; 3380 unsigned EmitNodeInfo = MatcherTable[MatcherIndex++]; 3381 // Get the result VT list. 3382 unsigned NumVTs; 3383 // If this is one of the compressed forms, get the number of VTs based 3384 // on the Opcode. Otherwise read the next byte from the table. 3385 if (Opcode >= OPC_MorphNodeTo0 && Opcode <= OPC_MorphNodeTo2) 3386 NumVTs = Opcode - OPC_MorphNodeTo0; 3387 else if (Opcode >= OPC_EmitNode0 && Opcode <= OPC_EmitNode2) 3388 NumVTs = Opcode - OPC_EmitNode0; 3389 else 3390 NumVTs = MatcherTable[MatcherIndex++]; 3391 SmallVector<EVT, 4> VTs; 3392 for (unsigned i = 0; i != NumVTs; ++i) { 3393 MVT::SimpleValueType VT = 3394 (MVT::SimpleValueType)MatcherTable[MatcherIndex++]; 3395 if (VT == MVT::iPTR) 3396 VT = TLI->getPointerTy(CurDAG->getDataLayout()).SimpleTy; 3397 VTs.push_back(VT); 3398 } 3399 3400 if (EmitNodeInfo & OPFL_Chain) 3401 VTs.push_back(MVT::Other); 3402 if (EmitNodeInfo & OPFL_GlueOutput) 3403 VTs.push_back(MVT::Glue); 3404 3405 // This is hot code, so optimize the two most common cases of 1 and 2 3406 // results. 3407 SDVTList VTList; 3408 if (VTs.size() == 1) 3409 VTList = CurDAG->getVTList(VTs[0]); 3410 else if (VTs.size() == 2) 3411 VTList = CurDAG->getVTList(VTs[0], VTs[1]); 3412 else 3413 VTList = CurDAG->getVTList(VTs); 3414 3415 // Get the operand list. 3416 unsigned NumOps = MatcherTable[MatcherIndex++]; 3417 SmallVector<SDValue, 8> Ops; 3418 for (unsigned i = 0; i != NumOps; ++i) { 3419 unsigned RecNo = MatcherTable[MatcherIndex++]; 3420 if (RecNo & 128) 3421 RecNo = GetVBR(RecNo, MatcherTable, MatcherIndex); 3422 3423 assert(RecNo < RecordedNodes.size() && "Invalid EmitNode"); 3424 Ops.push_back(RecordedNodes[RecNo].first); 3425 } 3426 3427 // If there are variadic operands to add, handle them now. 3428 if (EmitNodeInfo & OPFL_VariadicInfo) { 3429 // Determine the start index to copy from. 3430 unsigned FirstOpToCopy = getNumFixedFromVariadicInfo(EmitNodeInfo); 3431 FirstOpToCopy += (EmitNodeInfo & OPFL_Chain) ? 1 : 0; 3432 assert(NodeToMatch->getNumOperands() >= FirstOpToCopy && 3433 "Invalid variadic node"); 3434 // Copy all of the variadic operands, not including a potential glue 3435 // input. 3436 for (unsigned i = FirstOpToCopy, e = NodeToMatch->getNumOperands(); 3437 i != e; ++i) { 3438 SDValue V = NodeToMatch->getOperand(i); 3439 if (V.getValueType() == MVT::Glue) break; 3440 Ops.push_back(V); 3441 } 3442 } 3443 3444 // If this has chain/glue inputs, add them. 3445 if (EmitNodeInfo & OPFL_Chain) 3446 Ops.push_back(InputChain); 3447 if ((EmitNodeInfo & OPFL_GlueInput) && InputGlue.getNode() != nullptr) 3448 Ops.push_back(InputGlue); 3449 3450 // Check whether any matched node could raise an FP exception. Since all 3451 // such nodes must have a chain, it suffices to check ChainNodesMatched. 3452 // We need to perform this check before potentially modifying one of the 3453 // nodes via MorphNode. 3454 bool MayRaiseFPException = 3455 llvm::any_of(ChainNodesMatched, [this](SDNode *N) { 3456 return mayRaiseFPException(N) && !N->getFlags().hasNoFPExcept(); 3457 }); 3458 3459 // Create the node. 3460 MachineSDNode *Res = nullptr; 3461 bool IsMorphNodeTo = Opcode == OPC_MorphNodeTo || 3462 (Opcode >= OPC_MorphNodeTo0 && Opcode <= OPC_MorphNodeTo2); 3463 if (!IsMorphNodeTo) { 3464 // If this is a normal EmitNode command, just create the new node and 3465 // add the results to the RecordedNodes list. 3466 Res = CurDAG->getMachineNode(TargetOpc, SDLoc(NodeToMatch), 3467 VTList, Ops); 3468 3469 // Add all the non-glue/non-chain results to the RecordedNodes list. 3470 for (unsigned i = 0, e = VTs.size(); i != e; ++i) { 3471 if (VTs[i] == MVT::Other || VTs[i] == MVT::Glue) break; 3472 RecordedNodes.push_back(std::pair<SDValue,SDNode*>(SDValue(Res, i), 3473 nullptr)); 3474 } 3475 } else { 3476 assert(NodeToMatch->getOpcode() != ISD::DELETED_NODE && 3477 "NodeToMatch was removed partway through selection"); 3478 SelectionDAG::DAGNodeDeletedListener NDL(*CurDAG, [&](SDNode *N, 3479 SDNode *E) { 3480 CurDAG->salvageDebugInfo(*N); 3481 auto &Chain = ChainNodesMatched; 3482 assert((!E || !is_contained(Chain, N)) && 3483 "Chain node replaced during MorphNode"); 3484 llvm::erase_value(Chain, N); 3485 }); 3486 Res = cast<MachineSDNode>(MorphNode(NodeToMatch, TargetOpc, VTList, 3487 Ops, EmitNodeInfo)); 3488 } 3489 3490 // Set the NoFPExcept flag when no original matched node could 3491 // raise an FP exception, but the new node potentially might. 3492 if (!MayRaiseFPException && mayRaiseFPException(Res)) { 3493 SDNodeFlags Flags = Res->getFlags(); 3494 Flags.setNoFPExcept(true); 3495 Res->setFlags(Flags); 3496 } 3497 3498 // If the node had chain/glue results, update our notion of the current 3499 // chain and glue. 3500 if (EmitNodeInfo & OPFL_GlueOutput) { 3501 InputGlue = SDValue(Res, VTs.size()-1); 3502 if (EmitNodeInfo & OPFL_Chain) 3503 InputChain = SDValue(Res, VTs.size()-2); 3504 } else if (EmitNodeInfo & OPFL_Chain) 3505 InputChain = SDValue(Res, VTs.size()-1); 3506 3507 // If the OPFL_MemRefs glue is set on this node, slap all of the 3508 // accumulated memrefs onto it. 3509 // 3510 // FIXME: This is vastly incorrect for patterns with multiple outputs 3511 // instructions that access memory and for ComplexPatterns that match 3512 // loads. 3513 if (EmitNodeInfo & OPFL_MemRefs) { 3514 // Only attach load or store memory operands if the generated 3515 // instruction may load or store. 3516 const MCInstrDesc &MCID = TII->get(TargetOpc); 3517 bool mayLoad = MCID.mayLoad(); 3518 bool mayStore = MCID.mayStore(); 3519 3520 // We expect to have relatively few of these so just filter them into a 3521 // temporary buffer so that we can easily add them to the instruction. 3522 SmallVector<MachineMemOperand *, 4> FilteredMemRefs; 3523 for (MachineMemOperand *MMO : MatchedMemRefs) { 3524 if (MMO->isLoad()) { 3525 if (mayLoad) 3526 FilteredMemRefs.push_back(MMO); 3527 } else if (MMO->isStore()) { 3528 if (mayStore) 3529 FilteredMemRefs.push_back(MMO); 3530 } else { 3531 FilteredMemRefs.push_back(MMO); 3532 } 3533 } 3534 3535 CurDAG->setNodeMemRefs(Res, FilteredMemRefs); 3536 } 3537 3538 LLVM_DEBUG(if (!MatchedMemRefs.empty() && Res->memoperands_empty()) dbgs() 3539 << " Dropping mem operands\n"; 3540 dbgs() << " " << (IsMorphNodeTo ? "Morphed" : "Created") 3541 << " node: "; 3542 Res->dump(CurDAG);); 3543 3544 // If this was a MorphNodeTo then we're completely done! 3545 if (IsMorphNodeTo) { 3546 // Update chain uses. 3547 UpdateChains(Res, InputChain, ChainNodesMatched, true); 3548 return; 3549 } 3550 continue; 3551 } 3552 3553 case OPC_CompleteMatch: { 3554 // The match has been completed, and any new nodes (if any) have been 3555 // created. Patch up references to the matched dag to use the newly 3556 // created nodes. 3557 unsigned NumResults = MatcherTable[MatcherIndex++]; 3558 3559 for (unsigned i = 0; i != NumResults; ++i) { 3560 unsigned ResSlot = MatcherTable[MatcherIndex++]; 3561 if (ResSlot & 128) 3562 ResSlot = GetVBR(ResSlot, MatcherTable, MatcherIndex); 3563 3564 assert(ResSlot < RecordedNodes.size() && "Invalid CompleteMatch"); 3565 SDValue Res = RecordedNodes[ResSlot].first; 3566 3567 assert(i < NodeToMatch->getNumValues() && 3568 NodeToMatch->getValueType(i) != MVT::Other && 3569 NodeToMatch->getValueType(i) != MVT::Glue && 3570 "Invalid number of results to complete!"); 3571 assert((NodeToMatch->getValueType(i) == Res.getValueType() || 3572 NodeToMatch->getValueType(i) == MVT::iPTR || 3573 Res.getValueType() == MVT::iPTR || 3574 NodeToMatch->getValueType(i).getSizeInBits() == 3575 Res.getValueSizeInBits()) && 3576 "invalid replacement"); 3577 ReplaceUses(SDValue(NodeToMatch, i), Res); 3578 } 3579 3580 // Update chain uses. 3581 UpdateChains(NodeToMatch, InputChain, ChainNodesMatched, false); 3582 3583 // If the root node defines glue, we need to update it to the glue result. 3584 // TODO: This never happens in our tests and I think it can be removed / 3585 // replaced with an assert, but if we do it this the way the change is 3586 // NFC. 3587 if (NodeToMatch->getValueType(NodeToMatch->getNumValues() - 1) == 3588 MVT::Glue && 3589 InputGlue.getNode()) 3590 ReplaceUses(SDValue(NodeToMatch, NodeToMatch->getNumValues() - 1), 3591 InputGlue); 3592 3593 assert(NodeToMatch->use_empty() && 3594 "Didn't replace all uses of the node?"); 3595 CurDAG->RemoveDeadNode(NodeToMatch); 3596 3597 return; 3598 } 3599 } 3600 3601 // If the code reached this point, then the match failed. See if there is 3602 // another child to try in the current 'Scope', otherwise pop it until we 3603 // find a case to check. 3604 LLVM_DEBUG(dbgs() << " Match failed at index " << CurrentOpcodeIndex 3605 << "\n"); 3606 ++NumDAGIselRetries; 3607 while (true) { 3608 if (MatchScopes.empty()) { 3609 CannotYetSelect(NodeToMatch); 3610 return; 3611 } 3612 3613 // Restore the interpreter state back to the point where the scope was 3614 // formed. 3615 MatchScope &LastScope = MatchScopes.back(); 3616 RecordedNodes.resize(LastScope.NumRecordedNodes); 3617 NodeStack.clear(); 3618 NodeStack.append(LastScope.NodeStack.begin(), LastScope.NodeStack.end()); 3619 N = NodeStack.back(); 3620 3621 if (LastScope.NumMatchedMemRefs != MatchedMemRefs.size()) 3622 MatchedMemRefs.resize(LastScope.NumMatchedMemRefs); 3623 MatcherIndex = LastScope.FailIndex; 3624 3625 LLVM_DEBUG(dbgs() << " Continuing at " << MatcherIndex << "\n"); 3626 3627 InputChain = LastScope.InputChain; 3628 InputGlue = LastScope.InputGlue; 3629 if (!LastScope.HasChainNodesMatched) 3630 ChainNodesMatched.clear(); 3631 3632 // Check to see what the offset is at the new MatcherIndex. If it is zero 3633 // we have reached the end of this scope, otherwise we have another child 3634 // in the current scope to try. 3635 unsigned NumToSkip = MatcherTable[MatcherIndex++]; 3636 if (NumToSkip & 128) 3637 NumToSkip = GetVBR(NumToSkip, MatcherTable, MatcherIndex); 3638 3639 // If we have another child in this scope to match, update FailIndex and 3640 // try it. 3641 if (NumToSkip != 0) { 3642 LastScope.FailIndex = MatcherIndex+NumToSkip; 3643 break; 3644 } 3645 3646 // End of this scope, pop it and try the next child in the containing 3647 // scope. 3648 MatchScopes.pop_back(); 3649 } 3650 } 3651 } 3652 3653 /// Return whether the node may raise an FP exception. 3654 bool SelectionDAGISel::mayRaiseFPException(SDNode *N) const { 3655 // For machine opcodes, consult the MCID flag. 3656 if (N->isMachineOpcode()) { 3657 const MCInstrDesc &MCID = TII->get(N->getMachineOpcode()); 3658 return MCID.mayRaiseFPException(); 3659 } 3660 3661 // For ISD opcodes, only StrictFP opcodes may raise an FP 3662 // exception. 3663 if (N->isTargetOpcode()) 3664 return N->isTargetStrictFPOpcode(); 3665 return N->isStrictFPOpcode(); 3666 } 3667 3668 bool SelectionDAGISel::isOrEquivalentToAdd(const SDNode *N) const { 3669 assert(N->getOpcode() == ISD::OR && "Unexpected opcode"); 3670 auto *C = dyn_cast<ConstantSDNode>(N->getOperand(1)); 3671 if (!C) 3672 return false; 3673 3674 // Detect when "or" is used to add an offset to a stack object. 3675 if (auto *FN = dyn_cast<FrameIndexSDNode>(N->getOperand(0))) { 3676 MachineFrameInfo &MFI = MF->getFrameInfo(); 3677 Align A = MFI.getObjectAlign(FN->getIndex()); 3678 int32_t Off = C->getSExtValue(); 3679 // If the alleged offset fits in the zero bits guaranteed by 3680 // the alignment, then this or is really an add. 3681 return (Off >= 0) && (((A.value() - 1) & Off) == unsigned(Off)); 3682 } 3683 return false; 3684 } 3685 3686 void SelectionDAGISel::CannotYetSelect(SDNode *N) { 3687 std::string msg; 3688 raw_string_ostream Msg(msg); 3689 Msg << "Cannot select: "; 3690 3691 if (N->getOpcode() != ISD::INTRINSIC_W_CHAIN && 3692 N->getOpcode() != ISD::INTRINSIC_WO_CHAIN && 3693 N->getOpcode() != ISD::INTRINSIC_VOID) { 3694 N->printrFull(Msg, CurDAG); 3695 Msg << "\nIn function: " << MF->getName(); 3696 } else { 3697 bool HasInputChain = N->getOperand(0).getValueType() == MVT::Other; 3698 unsigned iid = 3699 cast<ConstantSDNode>(N->getOperand(HasInputChain))->getZExtValue(); 3700 if (iid < Intrinsic::num_intrinsics) 3701 Msg << "intrinsic %" << Intrinsic::getBaseName((Intrinsic::ID)iid); 3702 else if (const TargetIntrinsicInfo *TII = TM.getIntrinsicInfo()) 3703 Msg << "target intrinsic %" << TII->getName(iid); 3704 else 3705 Msg << "unknown intrinsic #" << iid; 3706 } 3707 report_fatal_error(Twine(Msg.str())); 3708 } 3709 3710 char SelectionDAGISel::ID = 0; 3711