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