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