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