SelectionDAGISel.cpp revision 223017
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#define DEBUG_TYPE "isel" 15#include "ScheduleDAGSDNodes.h" 16#include "SelectionDAGBuilder.h" 17#include "llvm/CodeGen/FunctionLoweringInfo.h" 18#include "llvm/CodeGen/SelectionDAGISel.h" 19#include "llvm/Analysis/AliasAnalysis.h" 20#include "llvm/Analysis/DebugInfo.h" 21#include "llvm/Constants.h" 22#include "llvm/Function.h" 23#include "llvm/InlineAsm.h" 24#include "llvm/Instructions.h" 25#include "llvm/Intrinsics.h" 26#include "llvm/IntrinsicInst.h" 27#include "llvm/LLVMContext.h" 28#include "llvm/Module.h" 29#include "llvm/CodeGen/FastISel.h" 30#include "llvm/CodeGen/GCStrategy.h" 31#include "llvm/CodeGen/GCMetadata.h" 32#include "llvm/CodeGen/MachineFrameInfo.h" 33#include "llvm/CodeGen/MachineFunction.h" 34#include "llvm/CodeGen/MachineInstrBuilder.h" 35#include "llvm/CodeGen/MachineModuleInfo.h" 36#include "llvm/CodeGen/MachineRegisterInfo.h" 37#include "llvm/CodeGen/ScheduleHazardRecognizer.h" 38#include "llvm/CodeGen/SchedulerRegistry.h" 39#include "llvm/CodeGen/SelectionDAG.h" 40#include "llvm/Target/TargetRegisterInfo.h" 41#include "llvm/Target/TargetIntrinsicInfo.h" 42#include "llvm/Target/TargetInstrInfo.h" 43#include "llvm/Target/TargetLowering.h" 44#include "llvm/Target/TargetMachine.h" 45#include "llvm/Target/TargetOptions.h" 46#include "llvm/Transforms/Utils/BasicBlockUtils.h" 47#include "llvm/Support/Compiler.h" 48#include "llvm/Support/Debug.h" 49#include "llvm/Support/ErrorHandling.h" 50#include "llvm/Support/Timer.h" 51#include "llvm/Support/raw_ostream.h" 52#include "llvm/ADT/PostOrderIterator.h" 53#include "llvm/ADT/Statistic.h" 54#include <algorithm> 55using namespace llvm; 56 57STATISTIC(NumFastIselFailures, "Number of instructions fast isel failed on"); 58STATISTIC(NumFastIselSuccess, "Number of instructions fast isel selected"); 59STATISTIC(NumFastIselBlocks, "Number of blocks selected entirely by fast isel"); 60STATISTIC(NumDAGBlocks, "Number of blocks selected using DAG"); 61STATISTIC(NumDAGIselRetries,"Number of times dag isel has to try another path"); 62 63static cl::opt<bool> 64EnableFastISelVerbose("fast-isel-verbose", cl::Hidden, 65 cl::desc("Enable verbose messages in the \"fast\" " 66 "instruction selector")); 67static cl::opt<bool> 68EnableFastISelAbort("fast-isel-abort", cl::Hidden, 69 cl::desc("Enable abort calls when \"fast\" instruction fails")); 70 71#ifndef NDEBUG 72static cl::opt<bool> 73ViewDAGCombine1("view-dag-combine1-dags", cl::Hidden, 74 cl::desc("Pop up a window to show dags before the first " 75 "dag combine pass")); 76static cl::opt<bool> 77ViewLegalizeTypesDAGs("view-legalize-types-dags", cl::Hidden, 78 cl::desc("Pop up a window to show dags before legalize types")); 79static cl::opt<bool> 80ViewLegalizeDAGs("view-legalize-dags", cl::Hidden, 81 cl::desc("Pop up a window to show dags before legalize")); 82static cl::opt<bool> 83ViewDAGCombine2("view-dag-combine2-dags", cl::Hidden, 84 cl::desc("Pop up a window to show dags before the second " 85 "dag combine pass")); 86static cl::opt<bool> 87ViewDAGCombineLT("view-dag-combine-lt-dags", cl::Hidden, 88 cl::desc("Pop up a window to show dags before the post legalize types" 89 " dag combine pass")); 90static cl::opt<bool> 91ViewISelDAGs("view-isel-dags", cl::Hidden, 92 cl::desc("Pop up a window to show isel dags as they are selected")); 93static cl::opt<bool> 94ViewSchedDAGs("view-sched-dags", cl::Hidden, 95 cl::desc("Pop up a window to show sched dags as they are processed")); 96static cl::opt<bool> 97ViewSUnitDAGs("view-sunit-dags", cl::Hidden, 98 cl::desc("Pop up a window to show SUnit dags after they are processed")); 99#else 100static const bool ViewDAGCombine1 = false, 101 ViewLegalizeTypesDAGs = false, ViewLegalizeDAGs = false, 102 ViewDAGCombine2 = false, 103 ViewDAGCombineLT = false, 104 ViewISelDAGs = false, ViewSchedDAGs = false, 105 ViewSUnitDAGs = false; 106#endif 107 108//===---------------------------------------------------------------------===// 109/// 110/// RegisterScheduler class - Track the registration of instruction schedulers. 111/// 112//===---------------------------------------------------------------------===// 113MachinePassRegistry RegisterScheduler::Registry; 114 115//===---------------------------------------------------------------------===// 116/// 117/// ISHeuristic command line option for instruction schedulers. 118/// 119//===---------------------------------------------------------------------===// 120static cl::opt<RegisterScheduler::FunctionPassCtor, false, 121 RegisterPassParser<RegisterScheduler> > 122ISHeuristic("pre-RA-sched", 123 cl::init(&createDefaultScheduler), 124 cl::desc("Instruction schedulers available (before register" 125 " allocation):")); 126 127static RegisterScheduler 128defaultListDAGScheduler("default", "Best scheduler for the target", 129 createDefaultScheduler); 130 131namespace llvm { 132 //===--------------------------------------------------------------------===// 133 /// createDefaultScheduler - This creates an instruction scheduler appropriate 134 /// for the target. 135 ScheduleDAGSDNodes* createDefaultScheduler(SelectionDAGISel *IS, 136 CodeGenOpt::Level OptLevel) { 137 const TargetLowering &TLI = IS->getTargetLowering(); 138 139 if (OptLevel == CodeGenOpt::None) 140 return createSourceListDAGScheduler(IS, OptLevel); 141 if (TLI.getSchedulingPreference() == Sched::Latency) 142 return createTDListDAGScheduler(IS, OptLevel); 143 if (TLI.getSchedulingPreference() == Sched::RegPressure) 144 return createBURRListDAGScheduler(IS, OptLevel); 145 if (TLI.getSchedulingPreference() == Sched::Hybrid) 146 return createHybridListDAGScheduler(IS, OptLevel); 147 assert(TLI.getSchedulingPreference() == Sched::ILP && 148 "Unknown sched type!"); 149 return createILPListDAGScheduler(IS, OptLevel); 150 } 151} 152 153// EmitInstrWithCustomInserter - This method should be implemented by targets 154// that mark instructions with the 'usesCustomInserter' flag. These 155// instructions are special in various ways, which require special support to 156// insert. The specified MachineInstr is created but not inserted into any 157// basic blocks, and this method is called to expand it into a sequence of 158// instructions, potentially also creating new basic blocks and control flow. 159// When new basic blocks are inserted and the edges from MBB to its successors 160// are modified, the method should insert pairs of <OldSucc, NewSucc> into the 161// DenseMap. 162MachineBasicBlock * 163TargetLowering::EmitInstrWithCustomInserter(MachineInstr *MI, 164 MachineBasicBlock *MBB) const { 165#ifndef NDEBUG 166 dbgs() << "If a target marks an instruction with " 167 "'usesCustomInserter', it must implement " 168 "TargetLowering::EmitInstrWithCustomInserter!"; 169#endif 170 llvm_unreachable(0); 171 return 0; 172} 173 174//===----------------------------------------------------------------------===// 175// SelectionDAGISel code 176//===----------------------------------------------------------------------===// 177 178SelectionDAGISel::SelectionDAGISel(const TargetMachine &tm, 179 CodeGenOpt::Level OL) : 180 MachineFunctionPass(ID), TM(tm), TLI(*tm.getTargetLowering()), 181 FuncInfo(new FunctionLoweringInfo(TLI)), 182 CurDAG(new SelectionDAG(tm)), 183 SDB(new SelectionDAGBuilder(*CurDAG, *FuncInfo, OL)), 184 GFI(), 185 OptLevel(OL), 186 DAGSize(0) { 187 initializeGCModuleInfoPass(*PassRegistry::getPassRegistry()); 188 initializeAliasAnalysisAnalysisGroup(*PassRegistry::getPassRegistry()); 189 } 190 191SelectionDAGISel::~SelectionDAGISel() { 192 delete SDB; 193 delete CurDAG; 194 delete FuncInfo; 195} 196 197void SelectionDAGISel::getAnalysisUsage(AnalysisUsage &AU) const { 198 AU.addRequired<AliasAnalysis>(); 199 AU.addPreserved<AliasAnalysis>(); 200 AU.addRequired<GCModuleInfo>(); 201 AU.addPreserved<GCModuleInfo>(); 202 MachineFunctionPass::getAnalysisUsage(AU); 203} 204 205/// SplitCriticalSideEffectEdges - Look for critical edges with a PHI value that 206/// may trap on it. In this case we have to split the edge so that the path 207/// through the predecessor block that doesn't go to the phi block doesn't 208/// execute the possibly trapping instruction. 209/// 210/// This is required for correctness, so it must be done at -O0. 211/// 212static void SplitCriticalSideEffectEdges(Function &Fn, Pass *SDISel) { 213 // Loop for blocks with phi nodes. 214 for (Function::iterator BB = Fn.begin(), E = Fn.end(); BB != E; ++BB) { 215 PHINode *PN = dyn_cast<PHINode>(BB->begin()); 216 if (PN == 0) continue; 217 218 ReprocessBlock: 219 // For each block with a PHI node, check to see if any of the input values 220 // are potentially trapping constant expressions. Constant expressions are 221 // the only potentially trapping value that can occur as the argument to a 222 // PHI. 223 for (BasicBlock::iterator I = BB->begin(); (PN = dyn_cast<PHINode>(I)); ++I) 224 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { 225 ConstantExpr *CE = dyn_cast<ConstantExpr>(PN->getIncomingValue(i)); 226 if (CE == 0 || !CE->canTrap()) continue; 227 228 // The only case we have to worry about is when the edge is critical. 229 // Since this block has a PHI Node, we assume it has multiple input 230 // edges: check to see if the pred has multiple successors. 231 BasicBlock *Pred = PN->getIncomingBlock(i); 232 if (Pred->getTerminator()->getNumSuccessors() == 1) 233 continue; 234 235 // Okay, we have to split this edge. 236 SplitCriticalEdge(Pred->getTerminator(), 237 GetSuccessorNumber(Pred, BB), SDISel, true); 238 goto ReprocessBlock; 239 } 240 } 241} 242 243bool SelectionDAGISel::runOnMachineFunction(MachineFunction &mf) { 244 // Do some sanity-checking on the command-line options. 245 assert((!EnableFastISelVerbose || EnableFastISel) && 246 "-fast-isel-verbose requires -fast-isel"); 247 assert((!EnableFastISelAbort || EnableFastISel) && 248 "-fast-isel-abort requires -fast-isel"); 249 250 const Function &Fn = *mf.getFunction(); 251 const TargetInstrInfo &TII = *TM.getInstrInfo(); 252 const TargetRegisterInfo &TRI = *TM.getRegisterInfo(); 253 254 MF = &mf; 255 RegInfo = &MF->getRegInfo(); 256 AA = &getAnalysis<AliasAnalysis>(); 257 GFI = Fn.hasGC() ? &getAnalysis<GCModuleInfo>().getFunctionInfo(Fn) : 0; 258 259 DEBUG(dbgs() << "\n\n\n=== " << Fn.getName() << "\n"); 260 261 SplitCriticalSideEffectEdges(const_cast<Function&>(Fn), this); 262 263 CurDAG->init(*MF); 264 FuncInfo->set(Fn, *MF); 265 SDB->init(GFI, *AA); 266 267 SelectAllBasicBlocks(Fn); 268 269 // If the first basic block in the function has live ins that need to be 270 // copied into vregs, emit the copies into the top of the block before 271 // emitting the code for the block. 272 MachineBasicBlock *EntryMBB = MF->begin(); 273 RegInfo->EmitLiveInCopies(EntryMBB, TRI, TII); 274 275 DenseMap<unsigned, unsigned> LiveInMap; 276 if (!FuncInfo->ArgDbgValues.empty()) 277 for (MachineRegisterInfo::livein_iterator LI = RegInfo->livein_begin(), 278 E = RegInfo->livein_end(); LI != E; ++LI) 279 if (LI->second) 280 LiveInMap.insert(std::make_pair(LI->first, LI->second)); 281 282 // Insert DBG_VALUE instructions for function arguments to the entry block. 283 for (unsigned i = 0, e = FuncInfo->ArgDbgValues.size(); i != e; ++i) { 284 MachineInstr *MI = FuncInfo->ArgDbgValues[e-i-1]; 285 unsigned Reg = MI->getOperand(0).getReg(); 286 if (TargetRegisterInfo::isPhysicalRegister(Reg)) 287 EntryMBB->insert(EntryMBB->begin(), MI); 288 else { 289 MachineInstr *Def = RegInfo->getVRegDef(Reg); 290 MachineBasicBlock::iterator InsertPos = Def; 291 // FIXME: VR def may not be in entry block. 292 Def->getParent()->insert(llvm::next(InsertPos), MI); 293 } 294 295 // If Reg is live-in then update debug info to track its copy in a vreg. 296 DenseMap<unsigned, unsigned>::iterator LDI = LiveInMap.find(Reg); 297 if (LDI != LiveInMap.end()) { 298 MachineInstr *Def = RegInfo->getVRegDef(LDI->second); 299 MachineBasicBlock::iterator InsertPos = Def; 300 const MDNode *Variable = 301 MI->getOperand(MI->getNumOperands()-1).getMetadata(); 302 unsigned Offset = MI->getOperand(1).getImm(); 303 // Def is never a terminator here, so it is ok to increment InsertPos. 304 BuildMI(*EntryMBB, ++InsertPos, MI->getDebugLoc(), 305 TII.get(TargetOpcode::DBG_VALUE)) 306 .addReg(LDI->second, RegState::Debug) 307 .addImm(Offset).addMetadata(Variable); 308 309 // If this vreg is directly copied into an exported register then 310 // that COPY instructions also need DBG_VALUE, if it is the only 311 // user of LDI->second. 312 MachineInstr *CopyUseMI = NULL; 313 for (MachineRegisterInfo::use_iterator 314 UI = RegInfo->use_begin(LDI->second); 315 MachineInstr *UseMI = UI.skipInstruction();) { 316 if (UseMI->isDebugValue()) continue; 317 if (UseMI->isCopy() && !CopyUseMI && UseMI->getParent() == EntryMBB) { 318 CopyUseMI = UseMI; continue; 319 } 320 // Otherwise this is another use or second copy use. 321 CopyUseMI = NULL; break; 322 } 323 if (CopyUseMI) { 324 MachineInstr *NewMI = 325 BuildMI(*MF, CopyUseMI->getDebugLoc(), 326 TII.get(TargetOpcode::DBG_VALUE)) 327 .addReg(CopyUseMI->getOperand(0).getReg(), RegState::Debug) 328 .addImm(Offset).addMetadata(Variable); 329 EntryMBB->insertAfter(CopyUseMI, NewMI); 330 } 331 } 332 } 333 334 // Determine if there are any calls in this machine function. 335 MachineFrameInfo *MFI = MF->getFrameInfo(); 336 if (!MFI->hasCalls()) { 337 for (MachineFunction::const_iterator 338 I = MF->begin(), E = MF->end(); I != E; ++I) { 339 const MachineBasicBlock *MBB = I; 340 for (MachineBasicBlock::const_iterator 341 II = MBB->begin(), IE = MBB->end(); II != IE; ++II) { 342 const TargetInstrDesc &TID = TM.getInstrInfo()->get(II->getOpcode()); 343 344 if ((TID.isCall() && !TID.isReturn()) || 345 II->isStackAligningInlineAsm()) { 346 MFI->setHasCalls(true); 347 goto done; 348 } 349 } 350 } 351 done:; 352 } 353 354 // Determine if there is a call to setjmp in the machine function. 355 MF->setCallsSetJmp(Fn.callsFunctionThatReturnsTwice()); 356 357 // Replace forward-declared registers with the registers containing 358 // the desired value. 359 MachineRegisterInfo &MRI = MF->getRegInfo(); 360 for (DenseMap<unsigned, unsigned>::iterator 361 I = FuncInfo->RegFixups.begin(), E = FuncInfo->RegFixups.end(); 362 I != E; ++I) { 363 unsigned From = I->first; 364 unsigned To = I->second; 365 // If To is also scheduled to be replaced, find what its ultimate 366 // replacement is. 367 for (;;) { 368 DenseMap<unsigned, unsigned>::iterator J = 369 FuncInfo->RegFixups.find(To); 370 if (J == E) break; 371 To = J->second; 372 } 373 // Replace it. 374 MRI.replaceRegWith(From, To); 375 } 376 377 // Release function-specific state. SDB and CurDAG are already cleared 378 // at this point. 379 FuncInfo->clear(); 380 381 return true; 382} 383 384void SelectionDAGISel::SelectBasicBlock(BasicBlock::const_iterator Begin, 385 BasicBlock::const_iterator End, 386 bool &HadTailCall) { 387 // Lower all of the non-terminator instructions. If a call is emitted 388 // as a tail call, cease emitting nodes for this block. Terminators 389 // are handled below. 390 for (BasicBlock::const_iterator I = Begin; I != End && !SDB->HasTailCall; ++I) 391 SDB->visit(*I); 392 393 // Make sure the root of the DAG is up-to-date. 394 CurDAG->setRoot(SDB->getControlRoot()); 395 HadTailCall = SDB->HasTailCall; 396 SDB->clear(); 397 398 // Final step, emit the lowered DAG as machine code. 399 CodeGenAndEmitDAG(); 400} 401 402void SelectionDAGISel::ComputeLiveOutVRegInfo() { 403 SmallPtrSet<SDNode*, 128> VisitedNodes; 404 SmallVector<SDNode*, 128> Worklist; 405 406 Worklist.push_back(CurDAG->getRoot().getNode()); 407 408 APInt Mask; 409 APInt KnownZero; 410 APInt KnownOne; 411 412 do { 413 SDNode *N = Worklist.pop_back_val(); 414 415 // If we've already seen this node, ignore it. 416 if (!VisitedNodes.insert(N)) 417 continue; 418 419 // Otherwise, add all chain operands to the worklist. 420 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) 421 if (N->getOperand(i).getValueType() == MVT::Other) 422 Worklist.push_back(N->getOperand(i).getNode()); 423 424 // If this is a CopyToReg with a vreg dest, process it. 425 if (N->getOpcode() != ISD::CopyToReg) 426 continue; 427 428 unsigned DestReg = cast<RegisterSDNode>(N->getOperand(1))->getReg(); 429 if (!TargetRegisterInfo::isVirtualRegister(DestReg)) 430 continue; 431 432 // Ignore non-scalar or non-integer values. 433 SDValue Src = N->getOperand(2); 434 EVT SrcVT = Src.getValueType(); 435 if (!SrcVT.isInteger() || SrcVT.isVector()) 436 continue; 437 438 unsigned NumSignBits = CurDAG->ComputeNumSignBits(Src); 439 Mask = APInt::getAllOnesValue(SrcVT.getSizeInBits()); 440 CurDAG->ComputeMaskedBits(Src, Mask, KnownZero, KnownOne); 441 FuncInfo->AddLiveOutRegInfo(DestReg, NumSignBits, KnownZero, KnownOne); 442 } while (!Worklist.empty()); 443} 444 445void SelectionDAGISel::CodeGenAndEmitDAG() { 446 std::string GroupName; 447 if (TimePassesIsEnabled) 448 GroupName = "Instruction Selection and Scheduling"; 449 std::string BlockName; 450 int BlockNumber = -1; 451#ifdef NDEBUG 452 if (ViewDAGCombine1 || ViewLegalizeTypesDAGs || ViewLegalizeDAGs || 453 ViewDAGCombine2 || ViewDAGCombineLT || ViewISelDAGs || ViewSchedDAGs || 454 ViewSUnitDAGs) 455#endif 456 { 457 BlockNumber = FuncInfo->MBB->getNumber(); 458 BlockName = MF->getFunction()->getNameStr() + ":" + 459 FuncInfo->MBB->getBasicBlock()->getNameStr(); 460 } 461 DEBUG(dbgs() << "Initial selection DAG: BB#" << BlockNumber 462 << " '" << BlockName << "'\n"; CurDAG->dump()); 463 464 if (ViewDAGCombine1) CurDAG->viewGraph("dag-combine1 input for " + BlockName); 465 466 // Run the DAG combiner in pre-legalize mode. 467 { 468 NamedRegionTimer T("DAG Combining 1", GroupName, TimePassesIsEnabled); 469 CurDAG->Combine(Unrestricted, *AA, OptLevel); 470 } 471 472 DEBUG(dbgs() << "Optimized lowered selection DAG: BB#" << BlockNumber 473 << " '" << BlockName << "'\n"; CurDAG->dump()); 474 475 // Second step, hack on the DAG until it only uses operations and types that 476 // the target supports. 477 if (ViewLegalizeTypesDAGs) CurDAG->viewGraph("legalize-types input for " + 478 BlockName); 479 480 bool Changed; 481 { 482 NamedRegionTimer T("Type Legalization", GroupName, TimePassesIsEnabled); 483 Changed = CurDAG->LegalizeTypes(); 484 } 485 486 DEBUG(dbgs() << "Type-legalized selection DAG: BB#" << BlockNumber 487 << " '" << BlockName << "'\n"; CurDAG->dump()); 488 489 if (Changed) { 490 if (ViewDAGCombineLT) 491 CurDAG->viewGraph("dag-combine-lt input for " + BlockName); 492 493 // Run the DAG combiner in post-type-legalize mode. 494 { 495 NamedRegionTimer T("DAG Combining after legalize types", GroupName, 496 TimePassesIsEnabled); 497 CurDAG->Combine(NoIllegalTypes, *AA, OptLevel); 498 } 499 500 DEBUG(dbgs() << "Optimized type-legalized selection DAG: BB#" << BlockNumber 501 << " '" << BlockName << "'\n"; CurDAG->dump()); 502 } 503 504 { 505 NamedRegionTimer T("Vector Legalization", GroupName, TimePassesIsEnabled); 506 Changed = CurDAG->LegalizeVectors(); 507 } 508 509 if (Changed) { 510 { 511 NamedRegionTimer T("Type Legalization 2", GroupName, TimePassesIsEnabled); 512 CurDAG->LegalizeTypes(); 513 } 514 515 if (ViewDAGCombineLT) 516 CurDAG->viewGraph("dag-combine-lv input for " + BlockName); 517 518 // Run the DAG combiner in post-type-legalize mode. 519 { 520 NamedRegionTimer T("DAG Combining after legalize vectors", GroupName, 521 TimePassesIsEnabled); 522 CurDAG->Combine(NoIllegalOperations, *AA, OptLevel); 523 } 524 525 DEBUG(dbgs() << "Optimized vector-legalized selection DAG: BB#" 526 << BlockNumber << " '" << BlockName << "'\n"; CurDAG->dump()); 527 } 528 529 if (ViewLegalizeDAGs) CurDAG->viewGraph("legalize input for " + BlockName); 530 531 { 532 NamedRegionTimer T("DAG Legalization", GroupName, TimePassesIsEnabled); 533 CurDAG->Legalize(); 534 } 535 536 DEBUG(dbgs() << "Legalized selection DAG: BB#" << BlockNumber 537 << " '" << BlockName << "'\n"; CurDAG->dump()); 538 539 if (ViewDAGCombine2) CurDAG->viewGraph("dag-combine2 input for " + BlockName); 540 541 // Run the DAG combiner in post-legalize mode. 542 { 543 NamedRegionTimer T("DAG Combining 2", GroupName, TimePassesIsEnabled); 544 CurDAG->Combine(NoIllegalOperations, *AA, OptLevel); 545 } 546 547 DEBUG(dbgs() << "Optimized legalized selection DAG: BB#" << BlockNumber 548 << " '" << BlockName << "'\n"; CurDAG->dump()); 549 550 if (OptLevel != CodeGenOpt::None) 551 ComputeLiveOutVRegInfo(); 552 553 if (ViewISelDAGs) CurDAG->viewGraph("isel input for " + BlockName); 554 555 // Third, instruction select all of the operations to machine code, adding the 556 // code to the MachineBasicBlock. 557 { 558 NamedRegionTimer T("Instruction Selection", GroupName, TimePassesIsEnabled); 559 DoInstructionSelection(); 560 } 561 562 DEBUG(dbgs() << "Selected selection DAG: BB#" << BlockNumber 563 << " '" << BlockName << "'\n"; CurDAG->dump()); 564 565 if (ViewSchedDAGs) CurDAG->viewGraph("scheduler input for " + BlockName); 566 567 // Schedule machine code. 568 ScheduleDAGSDNodes *Scheduler = CreateScheduler(); 569 { 570 NamedRegionTimer T("Instruction Scheduling", GroupName, 571 TimePassesIsEnabled); 572 Scheduler->Run(CurDAG, FuncInfo->MBB, FuncInfo->InsertPt); 573 } 574 575 if (ViewSUnitDAGs) Scheduler->viewGraph(); 576 577 // Emit machine code to BB. This can change 'BB' to the last block being 578 // inserted into. 579 MachineBasicBlock *FirstMBB = FuncInfo->MBB, *LastMBB; 580 { 581 NamedRegionTimer T("Instruction Creation", GroupName, TimePassesIsEnabled); 582 583 LastMBB = FuncInfo->MBB = Scheduler->EmitSchedule(); 584 FuncInfo->InsertPt = Scheduler->InsertPos; 585 } 586 587 // If the block was split, make sure we update any references that are used to 588 // update PHI nodes later on. 589 if (FirstMBB != LastMBB) 590 SDB->UpdateSplitBlock(FirstMBB, LastMBB); 591 592 // Free the scheduler state. 593 { 594 NamedRegionTimer T("Instruction Scheduling Cleanup", GroupName, 595 TimePassesIsEnabled); 596 delete Scheduler; 597 } 598 599 // Free the SelectionDAG state, now that we're finished with it. 600 CurDAG->clear(); 601} 602 603void SelectionDAGISel::DoInstructionSelection() { 604 DEBUG(errs() << "===== Instruction selection begins: BB#" 605 << FuncInfo->MBB->getNumber() 606 << " '" << FuncInfo->MBB->getName() << "'\n"); 607 608 PreprocessISelDAG(); 609 610 // Select target instructions for the DAG. 611 { 612 // Number all nodes with a topological order and set DAGSize. 613 DAGSize = CurDAG->AssignTopologicalOrder(); 614 615 // Create a dummy node (which is not added to allnodes), that adds 616 // a reference to the root node, preventing it from being deleted, 617 // and tracking any changes of the root. 618 HandleSDNode Dummy(CurDAG->getRoot()); 619 ISelPosition = SelectionDAG::allnodes_iterator(CurDAG->getRoot().getNode()); 620 ++ISelPosition; 621 622 // The AllNodes list is now topological-sorted. Visit the 623 // nodes by starting at the end of the list (the root of the 624 // graph) and preceding back toward the beginning (the entry 625 // node). 626 while (ISelPosition != CurDAG->allnodes_begin()) { 627 SDNode *Node = --ISelPosition; 628 // Skip dead nodes. DAGCombiner is expected to eliminate all dead nodes, 629 // but there are currently some corner cases that it misses. Also, this 630 // makes it theoretically possible to disable the DAGCombiner. 631 if (Node->use_empty()) 632 continue; 633 634 SDNode *ResNode = Select(Node); 635 636 // FIXME: This is pretty gross. 'Select' should be changed to not return 637 // anything at all and this code should be nuked with a tactical strike. 638 639 // If node should not be replaced, continue with the next one. 640 if (ResNode == Node || Node->getOpcode() == ISD::DELETED_NODE) 641 continue; 642 // Replace node. 643 if (ResNode) 644 ReplaceUses(Node, ResNode); 645 646 // If after the replacement this node is not used any more, 647 // remove this dead node. 648 if (Node->use_empty()) { // Don't delete EntryToken, etc. 649 ISelUpdater ISU(ISelPosition); 650 CurDAG->RemoveDeadNode(Node, &ISU); 651 } 652 } 653 654 CurDAG->setRoot(Dummy.getValue()); 655 } 656 657 DEBUG(errs() << "===== Instruction selection ends:\n"); 658 659 PostprocessISelDAG(); 660} 661 662/// PrepareEHLandingPad - Emit an EH_LABEL, set up live-in registers, and 663/// do other setup for EH landing-pad blocks. 664void SelectionDAGISel::PrepareEHLandingPad() { 665 // Add a label to mark the beginning of the landing pad. Deletion of the 666 // landing pad can thus be detected via the MachineModuleInfo. 667 MCSymbol *Label = MF->getMMI().addLandingPad(FuncInfo->MBB); 668 669 const TargetInstrDesc &II = TM.getInstrInfo()->get(TargetOpcode::EH_LABEL); 670 BuildMI(*FuncInfo->MBB, FuncInfo->InsertPt, SDB->getCurDebugLoc(), II) 671 .addSym(Label); 672 673 // Mark exception register as live in. 674 unsigned Reg = TLI.getExceptionAddressRegister(); 675 if (Reg) FuncInfo->MBB->addLiveIn(Reg); 676 677 // Mark exception selector register as live in. 678 Reg = TLI.getExceptionSelectorRegister(); 679 if (Reg) FuncInfo->MBB->addLiveIn(Reg); 680 681 // FIXME: Hack around an exception handling flaw (PR1508): the personality 682 // function and list of typeids logically belong to the invoke (or, if you 683 // like, the basic block containing the invoke), and need to be associated 684 // with it in the dwarf exception handling tables. Currently however the 685 // information is provided by an intrinsic (eh.selector) that can be moved 686 // to unexpected places by the optimizers: if the unwind edge is critical, 687 // then breaking it can result in the intrinsics being in the successor of 688 // the landing pad, not the landing pad itself. This results 689 // in exceptions not being caught because no typeids are associated with 690 // the invoke. This may not be the only way things can go wrong, but it 691 // is the only way we try to work around for the moment. 692 const BasicBlock *LLVMBB = FuncInfo->MBB->getBasicBlock(); 693 const BranchInst *Br = dyn_cast<BranchInst>(LLVMBB->getTerminator()); 694 695 if (Br && Br->isUnconditional()) { // Critical edge? 696 BasicBlock::const_iterator I, E; 697 for (I = LLVMBB->begin(), E = --LLVMBB->end(); I != E; ++I) 698 if (isa<EHSelectorInst>(I)) 699 break; 700 701 if (I == E) 702 // No catch info found - try to extract some from the successor. 703 CopyCatchInfo(Br->getSuccessor(0), LLVMBB, &MF->getMMI(), *FuncInfo); 704 } 705} 706 707 708 709/// TryToFoldFastISelLoad - We're checking to see if we can fold the specified 710/// load into the specified FoldInst. Note that we could have a sequence where 711/// multiple LLVM IR instructions are folded into the same machineinstr. For 712/// example we could have: 713/// A: x = load i32 *P 714/// B: y = icmp A, 42 715/// C: br y, ... 716/// 717/// In this scenario, LI is "A", and FoldInst is "C". We know about "B" (and 718/// any other folded instructions) because it is between A and C. 719/// 720/// If we succeed in folding the load into the operation, return true. 721/// 722bool SelectionDAGISel::TryToFoldFastISelLoad(const LoadInst *LI, 723 const Instruction *FoldInst, 724 FastISel *FastIS) { 725 // We know that the load has a single use, but don't know what it is. If it 726 // isn't one of the folded instructions, then we can't succeed here. Handle 727 // this by scanning the single-use users of the load until we get to FoldInst. 728 unsigned MaxUsers = 6; // Don't scan down huge single-use chains of instrs. 729 730 const Instruction *TheUser = LI->use_back(); 731 while (TheUser != FoldInst && // Scan up until we find FoldInst. 732 // Stay in the right block. 733 TheUser->getParent() == FoldInst->getParent() && 734 --MaxUsers) { // Don't scan too far. 735 // If there are multiple or no uses of this instruction, then bail out. 736 if (!TheUser->hasOneUse()) 737 return false; 738 739 TheUser = TheUser->use_back(); 740 } 741 742 // Don't try to fold volatile loads. Target has to deal with alignment 743 // constraints. 744 if (LI->isVolatile()) return false; 745 746 // Figure out which vreg this is going into. If there is no assigned vreg yet 747 // then there actually was no reference to it. Perhaps the load is referenced 748 // by a dead instruction. 749 unsigned LoadReg = FastIS->getRegForValue(LI); 750 if (LoadReg == 0) 751 return false; 752 753 // Check to see what the uses of this vreg are. If it has no uses, or more 754 // than one use (at the machine instr level) then we can't fold it. 755 MachineRegisterInfo::reg_iterator RI = RegInfo->reg_begin(LoadReg); 756 if (RI == RegInfo->reg_end()) 757 return false; 758 759 // See if there is exactly one use of the vreg. If there are multiple uses, 760 // then the instruction got lowered to multiple machine instructions or the 761 // use of the loaded value ended up being multiple operands of the result, in 762 // either case, we can't fold this. 763 MachineRegisterInfo::reg_iterator PostRI = RI; ++PostRI; 764 if (PostRI != RegInfo->reg_end()) 765 return false; 766 767 assert(RI.getOperand().isUse() && 768 "The only use of the vreg must be a use, we haven't emitted the def!"); 769 770 MachineInstr *User = &*RI; 771 772 // Set the insertion point properly. Folding the load can cause generation of 773 // other random instructions (like sign extends) for addressing modes, make 774 // sure they get inserted in a logical place before the new instruction. 775 FuncInfo->InsertPt = User; 776 FuncInfo->MBB = User->getParent(); 777 778 // Ask the target to try folding the load. 779 return FastIS->TryToFoldLoad(User, RI.getOperandNo(), LI); 780} 781 782/// isFoldedOrDeadInstruction - Return true if the specified instruction is 783/// side-effect free and is either dead or folded into a generated instruction. 784/// Return false if it needs to be emitted. 785static bool isFoldedOrDeadInstruction(const Instruction *I, 786 FunctionLoweringInfo *FuncInfo) { 787 return !I->mayWriteToMemory() && // Side-effecting instructions aren't folded. 788 !isa<TerminatorInst>(I) && // Terminators aren't folded. 789 !isa<DbgInfoIntrinsic>(I) && // Debug instructions aren't folded. 790 !FuncInfo->isExportedInst(I); // Exported instrs must be computed. 791} 792 793void SelectionDAGISel::SelectAllBasicBlocks(const Function &Fn) { 794 // Initialize the Fast-ISel state, if needed. 795 FastISel *FastIS = 0; 796 if (EnableFastISel) 797 FastIS = TLI.createFastISel(*FuncInfo); 798 799 // Iterate over all basic blocks in the function. 800 ReversePostOrderTraversal<const Function*> RPOT(&Fn); 801 for (ReversePostOrderTraversal<const Function*>::rpo_iterator 802 I = RPOT.begin(), E = RPOT.end(); I != E; ++I) { 803 const BasicBlock *LLVMBB = *I; 804 805 if (OptLevel != CodeGenOpt::None) { 806 bool AllPredsVisited = true; 807 for (const_pred_iterator PI = pred_begin(LLVMBB), PE = pred_end(LLVMBB); 808 PI != PE; ++PI) { 809 if (!FuncInfo->VisitedBBs.count(*PI)) { 810 AllPredsVisited = false; 811 break; 812 } 813 } 814 815 if (AllPredsVisited) { 816 for (BasicBlock::const_iterator I = LLVMBB->begin(); 817 isa<PHINode>(I); ++I) 818 FuncInfo->ComputePHILiveOutRegInfo(cast<PHINode>(I)); 819 } else { 820 for (BasicBlock::const_iterator I = LLVMBB->begin(); 821 isa<PHINode>(I); ++I) 822 FuncInfo->InvalidatePHILiveOutRegInfo(cast<PHINode>(I)); 823 } 824 825 FuncInfo->VisitedBBs.insert(LLVMBB); 826 } 827 828 FuncInfo->MBB = FuncInfo->MBBMap[LLVMBB]; 829 FuncInfo->InsertPt = FuncInfo->MBB->getFirstNonPHI(); 830 831 BasicBlock::const_iterator const Begin = LLVMBB->getFirstNonPHI(); 832 BasicBlock::const_iterator const End = LLVMBB->end(); 833 BasicBlock::const_iterator BI = End; 834 835 FuncInfo->InsertPt = FuncInfo->MBB->getFirstNonPHI(); 836 837 // Setup an EH landing-pad block. 838 if (FuncInfo->MBB->isLandingPad()) 839 PrepareEHLandingPad(); 840 841 // Lower any arguments needed in this block if this is the entry block. 842 if (LLVMBB == &Fn.getEntryBlock()) 843 LowerArguments(LLVMBB); 844 845 // Before doing SelectionDAG ISel, see if FastISel has been requested. 846 if (FastIS) { 847 FastIS->startNewBlock(); 848 849 // Emit code for any incoming arguments. This must happen before 850 // beginning FastISel on the entry block. 851 if (LLVMBB == &Fn.getEntryBlock()) { 852 CurDAG->setRoot(SDB->getControlRoot()); 853 SDB->clear(); 854 CodeGenAndEmitDAG(); 855 856 // If we inserted any instructions at the beginning, make a note of 857 // where they are, so we can be sure to emit subsequent instructions 858 // after them. 859 if (FuncInfo->InsertPt != FuncInfo->MBB->begin()) 860 FastIS->setLastLocalValue(llvm::prior(FuncInfo->InsertPt)); 861 else 862 FastIS->setLastLocalValue(0); 863 } 864 865 // Do FastISel on as many instructions as possible. 866 for (; BI != Begin; --BI) { 867 const Instruction *Inst = llvm::prior(BI); 868 869 // If we no longer require this instruction, skip it. 870 if (isFoldedOrDeadInstruction(Inst, FuncInfo)) 871 continue; 872 873 // Bottom-up: reset the insert pos at the top, after any local-value 874 // instructions. 875 FastIS->recomputeInsertPt(); 876 877 // Try to select the instruction with FastISel. 878 if (FastIS->SelectInstruction(Inst)) { 879 ++NumFastIselSuccess; 880 // If fast isel succeeded, skip over all the folded instructions, and 881 // then see if there is a load right before the selected instructions. 882 // Try to fold the load if so. 883 const Instruction *BeforeInst = Inst; 884 while (BeforeInst != Begin) { 885 BeforeInst = llvm::prior(BasicBlock::const_iterator(BeforeInst)); 886 if (!isFoldedOrDeadInstruction(BeforeInst, FuncInfo)) 887 break; 888 } 889 if (BeforeInst != Inst && isa<LoadInst>(BeforeInst) && 890 BeforeInst->hasOneUse() && 891 TryToFoldFastISelLoad(cast<LoadInst>(BeforeInst), Inst, FastIS)) 892 // If we succeeded, don't re-select the load. 893 BI = llvm::next(BasicBlock::const_iterator(BeforeInst)); 894 continue; 895 } 896 897 // Then handle certain instructions as single-LLVM-Instruction blocks. 898 if (isa<CallInst>(Inst)) { 899 ++NumFastIselFailures; 900 if (EnableFastISelVerbose || EnableFastISelAbort) { 901 dbgs() << "FastISel missed call: "; 902 Inst->dump(); 903 } 904 905 if (!Inst->getType()->isVoidTy() && !Inst->use_empty()) { 906 unsigned &R = FuncInfo->ValueMap[Inst]; 907 if (!R) 908 R = FuncInfo->CreateRegs(Inst->getType()); 909 } 910 911 bool HadTailCall = false; 912 SelectBasicBlock(Inst, BI, HadTailCall); 913 914 // If the call was emitted as a tail call, we're done with the block. 915 if (HadTailCall) { 916 --BI; 917 break; 918 } 919 920 continue; 921 } 922 923 if (isa<TerminatorInst>(Inst) && !isa<BranchInst>(Inst)) { 924 // Don't abort, and use a different message for terminator misses. 925 ++NumFastIselFailures; 926 if (EnableFastISelVerbose || EnableFastISelAbort) { 927 dbgs() << "FastISel missed terminator: "; 928 Inst->dump(); 929 } 930 } else { 931 ++NumFastIselFailures; 932 if (EnableFastISelVerbose || EnableFastISelAbort) { 933 dbgs() << "FastISel miss: "; 934 Inst->dump(); 935 } 936 if (EnableFastISelAbort) 937 // The "fast" selector couldn't handle something and bailed. 938 // For the purpose of debugging, just abort. 939 llvm_unreachable("FastISel didn't select the entire block"); 940 } 941 break; 942 } 943 944 FastIS->recomputeInsertPt(); 945 } 946 947 if (Begin != BI) 948 ++NumDAGBlocks; 949 else 950 ++NumFastIselBlocks; 951 952 if (Begin != BI) { 953 // Run SelectionDAG instruction selection on the remainder of the block 954 // not handled by FastISel. If FastISel is not run, this is the entire 955 // block. 956 bool HadTailCall; 957 SelectBasicBlock(Begin, BI, HadTailCall); 958 } 959 960 FinishBasicBlock(); 961 FuncInfo->PHINodesToUpdate.clear(); 962 } 963 964 delete FastIS; 965 SDB->clearDanglingDebugInfo(); 966} 967 968void 969SelectionDAGISel::FinishBasicBlock() { 970 971 DEBUG(dbgs() << "Total amount of phi nodes to update: " 972 << FuncInfo->PHINodesToUpdate.size() << "\n"; 973 for (unsigned i = 0, e = FuncInfo->PHINodesToUpdate.size(); i != e; ++i) 974 dbgs() << "Node " << i << " : (" 975 << FuncInfo->PHINodesToUpdate[i].first 976 << ", " << FuncInfo->PHINodesToUpdate[i].second << ")\n"); 977 978 // Next, now that we know what the last MBB the LLVM BB expanded is, update 979 // PHI nodes in successors. 980 if (SDB->SwitchCases.empty() && 981 SDB->JTCases.empty() && 982 SDB->BitTestCases.empty()) { 983 for (unsigned i = 0, e = FuncInfo->PHINodesToUpdate.size(); i != e; ++i) { 984 MachineInstr *PHI = FuncInfo->PHINodesToUpdate[i].first; 985 assert(PHI->isPHI() && 986 "This is not a machine PHI node that we are updating!"); 987 if (!FuncInfo->MBB->isSuccessor(PHI->getParent())) 988 continue; 989 PHI->addOperand( 990 MachineOperand::CreateReg(FuncInfo->PHINodesToUpdate[i].second, false)); 991 PHI->addOperand(MachineOperand::CreateMBB(FuncInfo->MBB)); 992 } 993 return; 994 } 995 996 for (unsigned i = 0, e = SDB->BitTestCases.size(); i != e; ++i) { 997 // Lower header first, if it wasn't already lowered 998 if (!SDB->BitTestCases[i].Emitted) { 999 // Set the current basic block to the mbb we wish to insert the code into 1000 FuncInfo->MBB = SDB->BitTestCases[i].Parent; 1001 FuncInfo->InsertPt = FuncInfo->MBB->end(); 1002 // Emit the code 1003 SDB->visitBitTestHeader(SDB->BitTestCases[i], FuncInfo->MBB); 1004 CurDAG->setRoot(SDB->getRoot()); 1005 SDB->clear(); 1006 CodeGenAndEmitDAG(); 1007 } 1008 1009 for (unsigned j = 0, ej = SDB->BitTestCases[i].Cases.size(); j != ej; ++j) { 1010 // Set the current basic block to the mbb we wish to insert the code into 1011 FuncInfo->MBB = SDB->BitTestCases[i].Cases[j].ThisBB; 1012 FuncInfo->InsertPt = FuncInfo->MBB->end(); 1013 // Emit the code 1014 if (j+1 != ej) 1015 SDB->visitBitTestCase(SDB->BitTestCases[i], 1016 SDB->BitTestCases[i].Cases[j+1].ThisBB, 1017 SDB->BitTestCases[i].Reg, 1018 SDB->BitTestCases[i].Cases[j], 1019 FuncInfo->MBB); 1020 else 1021 SDB->visitBitTestCase(SDB->BitTestCases[i], 1022 SDB->BitTestCases[i].Default, 1023 SDB->BitTestCases[i].Reg, 1024 SDB->BitTestCases[i].Cases[j], 1025 FuncInfo->MBB); 1026 1027 1028 CurDAG->setRoot(SDB->getRoot()); 1029 SDB->clear(); 1030 CodeGenAndEmitDAG(); 1031 } 1032 1033 // Update PHI Nodes 1034 for (unsigned pi = 0, pe = FuncInfo->PHINodesToUpdate.size(); 1035 pi != pe; ++pi) { 1036 MachineInstr *PHI = FuncInfo->PHINodesToUpdate[pi].first; 1037 MachineBasicBlock *PHIBB = PHI->getParent(); 1038 assert(PHI->isPHI() && 1039 "This is not a machine PHI node that we are updating!"); 1040 // This is "default" BB. We have two jumps to it. From "header" BB and 1041 // from last "case" BB. 1042 if (PHIBB == SDB->BitTestCases[i].Default) { 1043 PHI->addOperand(MachineOperand:: 1044 CreateReg(FuncInfo->PHINodesToUpdate[pi].second, 1045 false)); 1046 PHI->addOperand(MachineOperand::CreateMBB(SDB->BitTestCases[i].Parent)); 1047 PHI->addOperand(MachineOperand:: 1048 CreateReg(FuncInfo->PHINodesToUpdate[pi].second, 1049 false)); 1050 PHI->addOperand(MachineOperand::CreateMBB(SDB->BitTestCases[i].Cases. 1051 back().ThisBB)); 1052 } 1053 // One of "cases" BB. 1054 for (unsigned j = 0, ej = SDB->BitTestCases[i].Cases.size(); 1055 j != ej; ++j) { 1056 MachineBasicBlock* cBB = SDB->BitTestCases[i].Cases[j].ThisBB; 1057 if (cBB->isSuccessor(PHIBB)) { 1058 PHI->addOperand(MachineOperand:: 1059 CreateReg(FuncInfo->PHINodesToUpdate[pi].second, 1060 false)); 1061 PHI->addOperand(MachineOperand::CreateMBB(cBB)); 1062 } 1063 } 1064 } 1065 } 1066 SDB->BitTestCases.clear(); 1067 1068 // If the JumpTable record is filled in, then we need to emit a jump table. 1069 // Updating the PHI nodes is tricky in this case, since we need to determine 1070 // whether the PHI is a successor of the range check MBB or the jump table MBB 1071 for (unsigned i = 0, e = SDB->JTCases.size(); i != e; ++i) { 1072 // Lower header first, if it wasn't already lowered 1073 if (!SDB->JTCases[i].first.Emitted) { 1074 // Set the current basic block to the mbb we wish to insert the code into 1075 FuncInfo->MBB = SDB->JTCases[i].first.HeaderBB; 1076 FuncInfo->InsertPt = FuncInfo->MBB->end(); 1077 // Emit the code 1078 SDB->visitJumpTableHeader(SDB->JTCases[i].second, SDB->JTCases[i].first, 1079 FuncInfo->MBB); 1080 CurDAG->setRoot(SDB->getRoot()); 1081 SDB->clear(); 1082 CodeGenAndEmitDAG(); 1083 } 1084 1085 // Set the current basic block to the mbb we wish to insert the code into 1086 FuncInfo->MBB = SDB->JTCases[i].second.MBB; 1087 FuncInfo->InsertPt = FuncInfo->MBB->end(); 1088 // Emit the code 1089 SDB->visitJumpTable(SDB->JTCases[i].second); 1090 CurDAG->setRoot(SDB->getRoot()); 1091 SDB->clear(); 1092 CodeGenAndEmitDAG(); 1093 1094 // Update PHI Nodes 1095 for (unsigned pi = 0, pe = FuncInfo->PHINodesToUpdate.size(); 1096 pi != pe; ++pi) { 1097 MachineInstr *PHI = FuncInfo->PHINodesToUpdate[pi].first; 1098 MachineBasicBlock *PHIBB = PHI->getParent(); 1099 assert(PHI->isPHI() && 1100 "This is not a machine PHI node that we are updating!"); 1101 // "default" BB. We can go there only from header BB. 1102 if (PHIBB == SDB->JTCases[i].second.Default) { 1103 PHI->addOperand 1104 (MachineOperand::CreateReg(FuncInfo->PHINodesToUpdate[pi].second, 1105 false)); 1106 PHI->addOperand 1107 (MachineOperand::CreateMBB(SDB->JTCases[i].first.HeaderBB)); 1108 } 1109 // JT BB. Just iterate over successors here 1110 if (FuncInfo->MBB->isSuccessor(PHIBB)) { 1111 PHI->addOperand 1112 (MachineOperand::CreateReg(FuncInfo->PHINodesToUpdate[pi].second, 1113 false)); 1114 PHI->addOperand(MachineOperand::CreateMBB(FuncInfo->MBB)); 1115 } 1116 } 1117 } 1118 SDB->JTCases.clear(); 1119 1120 // If the switch block involved a branch to one of the actual successors, we 1121 // need to update PHI nodes in that block. 1122 for (unsigned i = 0, e = FuncInfo->PHINodesToUpdate.size(); i != e; ++i) { 1123 MachineInstr *PHI = FuncInfo->PHINodesToUpdate[i].first; 1124 assert(PHI->isPHI() && 1125 "This is not a machine PHI node that we are updating!"); 1126 if (FuncInfo->MBB->isSuccessor(PHI->getParent())) { 1127 PHI->addOperand( 1128 MachineOperand::CreateReg(FuncInfo->PHINodesToUpdate[i].second, false)); 1129 PHI->addOperand(MachineOperand::CreateMBB(FuncInfo->MBB)); 1130 } 1131 } 1132 1133 // If we generated any switch lowering information, build and codegen any 1134 // additional DAGs necessary. 1135 for (unsigned i = 0, e = SDB->SwitchCases.size(); i != e; ++i) { 1136 // Set the current basic block to the mbb we wish to insert the code into 1137 FuncInfo->MBB = SDB->SwitchCases[i].ThisBB; 1138 FuncInfo->InsertPt = FuncInfo->MBB->end(); 1139 1140 // Determine the unique successors. 1141 SmallVector<MachineBasicBlock *, 2> Succs; 1142 Succs.push_back(SDB->SwitchCases[i].TrueBB); 1143 if (SDB->SwitchCases[i].TrueBB != SDB->SwitchCases[i].FalseBB) 1144 Succs.push_back(SDB->SwitchCases[i].FalseBB); 1145 1146 // Emit the code. Note that this could result in FuncInfo->MBB being split. 1147 SDB->visitSwitchCase(SDB->SwitchCases[i], FuncInfo->MBB); 1148 CurDAG->setRoot(SDB->getRoot()); 1149 SDB->clear(); 1150 CodeGenAndEmitDAG(); 1151 1152 // Remember the last block, now that any splitting is done, for use in 1153 // populating PHI nodes in successors. 1154 MachineBasicBlock *ThisBB = FuncInfo->MBB; 1155 1156 // Handle any PHI nodes in successors of this chunk, as if we were coming 1157 // from the original BB before switch expansion. Note that PHI nodes can 1158 // occur multiple times in PHINodesToUpdate. We have to be very careful to 1159 // handle them the right number of times. 1160 for (unsigned i = 0, e = Succs.size(); i != e; ++i) { 1161 FuncInfo->MBB = Succs[i]; 1162 FuncInfo->InsertPt = FuncInfo->MBB->end(); 1163 // FuncInfo->MBB may have been removed from the CFG if a branch was 1164 // constant folded. 1165 if (ThisBB->isSuccessor(FuncInfo->MBB)) { 1166 for (MachineBasicBlock::iterator Phi = FuncInfo->MBB->begin(); 1167 Phi != FuncInfo->MBB->end() && Phi->isPHI(); 1168 ++Phi) { 1169 // This value for this PHI node is recorded in PHINodesToUpdate. 1170 for (unsigned pn = 0; ; ++pn) { 1171 assert(pn != FuncInfo->PHINodesToUpdate.size() && 1172 "Didn't find PHI entry!"); 1173 if (FuncInfo->PHINodesToUpdate[pn].first == Phi) { 1174 Phi->addOperand(MachineOperand:: 1175 CreateReg(FuncInfo->PHINodesToUpdate[pn].second, 1176 false)); 1177 Phi->addOperand(MachineOperand::CreateMBB(ThisBB)); 1178 break; 1179 } 1180 } 1181 } 1182 } 1183 } 1184 } 1185 SDB->SwitchCases.clear(); 1186} 1187 1188 1189/// Create the scheduler. If a specific scheduler was specified 1190/// via the SchedulerRegistry, use it, otherwise select the 1191/// one preferred by the target. 1192/// 1193ScheduleDAGSDNodes *SelectionDAGISel::CreateScheduler() { 1194 RegisterScheduler::FunctionPassCtor Ctor = RegisterScheduler::getDefault(); 1195 1196 if (!Ctor) { 1197 Ctor = ISHeuristic; 1198 RegisterScheduler::setDefault(Ctor); 1199 } 1200 1201 return Ctor(this, OptLevel); 1202} 1203 1204//===----------------------------------------------------------------------===// 1205// Helper functions used by the generated instruction selector. 1206//===----------------------------------------------------------------------===// 1207// Calls to these methods are generated by tblgen. 1208 1209/// CheckAndMask - The isel is trying to match something like (and X, 255). If 1210/// the dag combiner simplified the 255, we still want to match. RHS is the 1211/// actual value in the DAG on the RHS of an AND, and DesiredMaskS is the value 1212/// specified in the .td file (e.g. 255). 1213bool SelectionDAGISel::CheckAndMask(SDValue LHS, ConstantSDNode *RHS, 1214 int64_t DesiredMaskS) const { 1215 const APInt &ActualMask = RHS->getAPIntValue(); 1216 const APInt &DesiredMask = APInt(LHS.getValueSizeInBits(), DesiredMaskS); 1217 1218 // If the actual mask exactly matches, success! 1219 if (ActualMask == DesiredMask) 1220 return true; 1221 1222 // If the actual AND mask is allowing unallowed bits, this doesn't match. 1223 if (ActualMask.intersects(~DesiredMask)) 1224 return false; 1225 1226 // Otherwise, the DAG Combiner may have proven that the value coming in is 1227 // either already zero or is not demanded. Check for known zero input bits. 1228 APInt NeededMask = DesiredMask & ~ActualMask; 1229 if (CurDAG->MaskedValueIsZero(LHS, NeededMask)) 1230 return true; 1231 1232 // TODO: check to see if missing bits are just not demanded. 1233 1234 // Otherwise, this pattern doesn't match. 1235 return false; 1236} 1237 1238/// CheckOrMask - The isel is trying to match something like (or X, 255). If 1239/// the dag combiner simplified the 255, we still want to match. RHS is the 1240/// actual value in the DAG on the RHS of an OR, and DesiredMaskS is the value 1241/// specified in the .td file (e.g. 255). 1242bool SelectionDAGISel::CheckOrMask(SDValue LHS, ConstantSDNode *RHS, 1243 int64_t DesiredMaskS) const { 1244 const APInt &ActualMask = RHS->getAPIntValue(); 1245 const APInt &DesiredMask = APInt(LHS.getValueSizeInBits(), DesiredMaskS); 1246 1247 // If the actual mask exactly matches, success! 1248 if (ActualMask == DesiredMask) 1249 return true; 1250 1251 // If the actual AND mask is allowing unallowed bits, this doesn't match. 1252 if (ActualMask.intersects(~DesiredMask)) 1253 return false; 1254 1255 // Otherwise, the DAG Combiner may have proven that the value coming in is 1256 // either already zero or is not demanded. Check for known zero input bits. 1257 APInt NeededMask = DesiredMask & ~ActualMask; 1258 1259 APInt KnownZero, KnownOne; 1260 CurDAG->ComputeMaskedBits(LHS, NeededMask, KnownZero, KnownOne); 1261 1262 // If all the missing bits in the or are already known to be set, match! 1263 if ((NeededMask & KnownOne) == NeededMask) 1264 return true; 1265 1266 // TODO: check to see if missing bits are just not demanded. 1267 1268 // Otherwise, this pattern doesn't match. 1269 return false; 1270} 1271 1272 1273/// SelectInlineAsmMemoryOperands - Calls to this are automatically generated 1274/// by tblgen. Others should not call it. 1275void SelectionDAGISel:: 1276SelectInlineAsmMemoryOperands(std::vector<SDValue> &Ops) { 1277 std::vector<SDValue> InOps; 1278 std::swap(InOps, Ops); 1279 1280 Ops.push_back(InOps[InlineAsm::Op_InputChain]); // 0 1281 Ops.push_back(InOps[InlineAsm::Op_AsmString]); // 1 1282 Ops.push_back(InOps[InlineAsm::Op_MDNode]); // 2, !srcloc 1283 Ops.push_back(InOps[InlineAsm::Op_ExtraInfo]); // 3 (SideEffect, AlignStack) 1284 1285 unsigned i = InlineAsm::Op_FirstOperand, e = InOps.size(); 1286 if (InOps[e-1].getValueType() == MVT::Glue) 1287 --e; // Don't process a glue operand if it is here. 1288 1289 while (i != e) { 1290 unsigned Flags = cast<ConstantSDNode>(InOps[i])->getZExtValue(); 1291 if (!InlineAsm::isMemKind(Flags)) { 1292 // Just skip over this operand, copying the operands verbatim. 1293 Ops.insert(Ops.end(), InOps.begin()+i, 1294 InOps.begin()+i+InlineAsm::getNumOperandRegisters(Flags) + 1); 1295 i += InlineAsm::getNumOperandRegisters(Flags) + 1; 1296 } else { 1297 assert(InlineAsm::getNumOperandRegisters(Flags) == 1 && 1298 "Memory operand with multiple values?"); 1299 // Otherwise, this is a memory operand. Ask the target to select it. 1300 std::vector<SDValue> SelOps; 1301 if (SelectInlineAsmMemoryOperand(InOps[i+1], 'm', SelOps)) 1302 report_fatal_error("Could not match memory address. Inline asm" 1303 " failure!"); 1304 1305 // Add this to the output node. 1306 unsigned NewFlags = 1307 InlineAsm::getFlagWord(InlineAsm::Kind_Mem, SelOps.size()); 1308 Ops.push_back(CurDAG->getTargetConstant(NewFlags, MVT::i32)); 1309 Ops.insert(Ops.end(), SelOps.begin(), SelOps.end()); 1310 i += 2; 1311 } 1312 } 1313 1314 // Add the glue input back if present. 1315 if (e != InOps.size()) 1316 Ops.push_back(InOps.back()); 1317} 1318 1319/// findGlueUse - Return use of MVT::Glue value produced by the specified 1320/// SDNode. 1321/// 1322static SDNode *findGlueUse(SDNode *N) { 1323 unsigned FlagResNo = N->getNumValues()-1; 1324 for (SDNode::use_iterator I = N->use_begin(), E = N->use_end(); I != E; ++I) { 1325 SDUse &Use = I.getUse(); 1326 if (Use.getResNo() == FlagResNo) 1327 return Use.getUser(); 1328 } 1329 return NULL; 1330} 1331 1332/// findNonImmUse - Return true if "Use" is a non-immediate use of "Def". 1333/// This function recursively traverses up the operand chain, ignoring 1334/// certain nodes. 1335static bool findNonImmUse(SDNode *Use, SDNode* Def, SDNode *ImmedUse, 1336 SDNode *Root, SmallPtrSet<SDNode*, 16> &Visited, 1337 bool IgnoreChains) { 1338 // The NodeID's are given uniques ID's where a node ID is guaranteed to be 1339 // greater than all of its (recursive) operands. If we scan to a point where 1340 // 'use' is smaller than the node we're scanning for, then we know we will 1341 // never find it. 1342 // 1343 // The Use may be -1 (unassigned) if it is a newly allocated node. This can 1344 // happen because we scan down to newly selected nodes in the case of glue 1345 // uses. 1346 if ((Use->getNodeId() < Def->getNodeId() && Use->getNodeId() != -1)) 1347 return false; 1348 1349 // Don't revisit nodes if we already scanned it and didn't fail, we know we 1350 // won't fail if we scan it again. 1351 if (!Visited.insert(Use)) 1352 return false; 1353 1354 for (unsigned i = 0, e = Use->getNumOperands(); i != e; ++i) { 1355 // Ignore chain uses, they are validated by HandleMergeInputChains. 1356 if (Use->getOperand(i).getValueType() == MVT::Other && IgnoreChains) 1357 continue; 1358 1359 SDNode *N = Use->getOperand(i).getNode(); 1360 if (N == Def) { 1361 if (Use == ImmedUse || Use == Root) 1362 continue; // We are not looking for immediate use. 1363 assert(N != Root); 1364 return true; 1365 } 1366 1367 // Traverse up the operand chain. 1368 if (findNonImmUse(N, Def, ImmedUse, Root, Visited, IgnoreChains)) 1369 return true; 1370 } 1371 return false; 1372} 1373 1374/// IsProfitableToFold - Returns true if it's profitable to fold the specific 1375/// operand node N of U during instruction selection that starts at Root. 1376bool SelectionDAGISel::IsProfitableToFold(SDValue N, SDNode *U, 1377 SDNode *Root) const { 1378 if (OptLevel == CodeGenOpt::None) return false; 1379 return N.hasOneUse(); 1380} 1381 1382/// IsLegalToFold - Returns true if the specific operand node N of 1383/// U can be folded during instruction selection that starts at Root. 1384bool SelectionDAGISel::IsLegalToFold(SDValue N, SDNode *U, SDNode *Root, 1385 CodeGenOpt::Level OptLevel, 1386 bool IgnoreChains) { 1387 if (OptLevel == CodeGenOpt::None) return false; 1388 1389 // If Root use can somehow reach N through a path that that doesn't contain 1390 // U then folding N would create a cycle. e.g. In the following 1391 // diagram, Root can reach N through X. If N is folded into into Root, then 1392 // X is both a predecessor and a successor of U. 1393 // 1394 // [N*] // 1395 // ^ ^ // 1396 // / \ // 1397 // [U*] [X]? // 1398 // ^ ^ // 1399 // \ / // 1400 // \ / // 1401 // [Root*] // 1402 // 1403 // * indicates nodes to be folded together. 1404 // 1405 // If Root produces glue, then it gets (even more) interesting. Since it 1406 // will be "glued" together with its glue use in the scheduler, we need to 1407 // check if it might reach N. 1408 // 1409 // [N*] // 1410 // ^ ^ // 1411 // / \ // 1412 // [U*] [X]? // 1413 // ^ ^ // 1414 // \ \ // 1415 // \ | // 1416 // [Root*] | // 1417 // ^ | // 1418 // f | // 1419 // | / // 1420 // [Y] / // 1421 // ^ / // 1422 // f / // 1423 // | / // 1424 // [GU] // 1425 // 1426 // If GU (glue use) indirectly reaches N (the load), and Root folds N 1427 // (call it Fold), then X is a predecessor of GU and a successor of 1428 // Fold. But since Fold and GU are glued together, this will create 1429 // a cycle in the scheduling graph. 1430 1431 // If the node has glue, walk down the graph to the "lowest" node in the 1432 // glueged set. 1433 EVT VT = Root->getValueType(Root->getNumValues()-1); 1434 while (VT == MVT::Glue) { 1435 SDNode *GU = findGlueUse(Root); 1436 if (GU == NULL) 1437 break; 1438 Root = GU; 1439 VT = Root->getValueType(Root->getNumValues()-1); 1440 1441 // If our query node has a glue result with a use, we've walked up it. If 1442 // the user (which has already been selected) has a chain or indirectly uses 1443 // the chain, our WalkChainUsers predicate will not consider it. Because of 1444 // this, we cannot ignore chains in this predicate. 1445 IgnoreChains = false; 1446 } 1447 1448 1449 SmallPtrSet<SDNode*, 16> Visited; 1450 return !findNonImmUse(Root, N.getNode(), U, Root, Visited, IgnoreChains); 1451} 1452 1453SDNode *SelectionDAGISel::Select_INLINEASM(SDNode *N) { 1454 std::vector<SDValue> Ops(N->op_begin(), N->op_end()); 1455 SelectInlineAsmMemoryOperands(Ops); 1456 1457 std::vector<EVT> VTs; 1458 VTs.push_back(MVT::Other); 1459 VTs.push_back(MVT::Glue); 1460 SDValue New = CurDAG->getNode(ISD::INLINEASM, N->getDebugLoc(), 1461 VTs, &Ops[0], Ops.size()); 1462 New->setNodeId(-1); 1463 return New.getNode(); 1464} 1465 1466SDNode *SelectionDAGISel::Select_UNDEF(SDNode *N) { 1467 return CurDAG->SelectNodeTo(N, TargetOpcode::IMPLICIT_DEF,N->getValueType(0)); 1468} 1469 1470/// GetVBR - decode a vbr encoding whose top bit is set. 1471LLVM_ATTRIBUTE_ALWAYS_INLINE static uint64_t 1472GetVBR(uint64_t Val, const unsigned char *MatcherTable, unsigned &Idx) { 1473 assert(Val >= 128 && "Not a VBR"); 1474 Val &= 127; // Remove first vbr bit. 1475 1476 unsigned Shift = 7; 1477 uint64_t NextBits; 1478 do { 1479 NextBits = MatcherTable[Idx++]; 1480 Val |= (NextBits&127) << Shift; 1481 Shift += 7; 1482 } while (NextBits & 128); 1483 1484 return Val; 1485} 1486 1487 1488/// UpdateChainsAndGlue - When a match is complete, this method updates uses of 1489/// interior glue and chain results to use the new glue and chain results. 1490void SelectionDAGISel:: 1491UpdateChainsAndGlue(SDNode *NodeToMatch, SDValue InputChain, 1492 const SmallVectorImpl<SDNode*> &ChainNodesMatched, 1493 SDValue InputGlue, 1494 const SmallVectorImpl<SDNode*> &GlueResultNodesMatched, 1495 bool isMorphNodeTo) { 1496 SmallVector<SDNode*, 4> NowDeadNodes; 1497 1498 ISelUpdater ISU(ISelPosition); 1499 1500 // Now that all the normal results are replaced, we replace the chain and 1501 // glue results if present. 1502 if (!ChainNodesMatched.empty()) { 1503 assert(InputChain.getNode() != 0 && 1504 "Matched input chains but didn't produce a chain"); 1505 // Loop over all of the nodes we matched that produced a chain result. 1506 // Replace all the chain results with the final chain we ended up with. 1507 for (unsigned i = 0, e = ChainNodesMatched.size(); i != e; ++i) { 1508 SDNode *ChainNode = ChainNodesMatched[i]; 1509 1510 // If this node was already deleted, don't look at it. 1511 if (ChainNode->getOpcode() == ISD::DELETED_NODE) 1512 continue; 1513 1514 // Don't replace the results of the root node if we're doing a 1515 // MorphNodeTo. 1516 if (ChainNode == NodeToMatch && isMorphNodeTo) 1517 continue; 1518 1519 SDValue ChainVal = SDValue(ChainNode, ChainNode->getNumValues()-1); 1520 if (ChainVal.getValueType() == MVT::Glue) 1521 ChainVal = ChainVal.getValue(ChainVal->getNumValues()-2); 1522 assert(ChainVal.getValueType() == MVT::Other && "Not a chain?"); 1523 CurDAG->ReplaceAllUsesOfValueWith(ChainVal, InputChain, &ISU); 1524 1525 // If the node became dead and we haven't already seen it, delete it. 1526 if (ChainNode->use_empty() && 1527 !std::count(NowDeadNodes.begin(), NowDeadNodes.end(), ChainNode)) 1528 NowDeadNodes.push_back(ChainNode); 1529 } 1530 } 1531 1532 // If the result produces glue, update any glue results in the matched 1533 // pattern with the glue result. 1534 if (InputGlue.getNode() != 0) { 1535 // Handle any interior nodes explicitly marked. 1536 for (unsigned i = 0, e = GlueResultNodesMatched.size(); i != e; ++i) { 1537 SDNode *FRN = GlueResultNodesMatched[i]; 1538 1539 // If this node was already deleted, don't look at it. 1540 if (FRN->getOpcode() == ISD::DELETED_NODE) 1541 continue; 1542 1543 assert(FRN->getValueType(FRN->getNumValues()-1) == MVT::Glue && 1544 "Doesn't have a glue result"); 1545 CurDAG->ReplaceAllUsesOfValueWith(SDValue(FRN, FRN->getNumValues()-1), 1546 InputGlue, &ISU); 1547 1548 // If the node became dead and we haven't already seen it, delete it. 1549 if (FRN->use_empty() && 1550 !std::count(NowDeadNodes.begin(), NowDeadNodes.end(), FRN)) 1551 NowDeadNodes.push_back(FRN); 1552 } 1553 } 1554 1555 if (!NowDeadNodes.empty()) 1556 CurDAG->RemoveDeadNodes(NowDeadNodes, &ISU); 1557 1558 DEBUG(errs() << "ISEL: Match complete!\n"); 1559} 1560 1561enum ChainResult { 1562 CR_Simple, 1563 CR_InducesCycle, 1564 CR_LeadsToInteriorNode 1565}; 1566 1567/// WalkChainUsers - Walk down the users of the specified chained node that is 1568/// part of the pattern we're matching, looking at all of the users we find. 1569/// This determines whether something is an interior node, whether we have a 1570/// non-pattern node in between two pattern nodes (which prevent folding because 1571/// it would induce a cycle) and whether we have a TokenFactor node sandwiched 1572/// between pattern nodes (in which case the TF becomes part of the pattern). 1573/// 1574/// The walk we do here is guaranteed to be small because we quickly get down to 1575/// already selected nodes "below" us. 1576static ChainResult 1577WalkChainUsers(SDNode *ChainedNode, 1578 SmallVectorImpl<SDNode*> &ChainedNodesInPattern, 1579 SmallVectorImpl<SDNode*> &InteriorChainedNodes) { 1580 ChainResult Result = CR_Simple; 1581 1582 for (SDNode::use_iterator UI = ChainedNode->use_begin(), 1583 E = ChainedNode->use_end(); UI != E; ++UI) { 1584 // Make sure the use is of the chain, not some other value we produce. 1585 if (UI.getUse().getValueType() != MVT::Other) continue; 1586 1587 SDNode *User = *UI; 1588 1589 // If we see an already-selected machine node, then we've gone beyond the 1590 // pattern that we're selecting down into the already selected chunk of the 1591 // DAG. 1592 if (User->isMachineOpcode() || 1593 User->getOpcode() == ISD::HANDLENODE) // Root of the graph. 1594 continue; 1595 1596 if (User->getOpcode() == ISD::CopyToReg || 1597 User->getOpcode() == ISD::CopyFromReg || 1598 User->getOpcode() == ISD::INLINEASM || 1599 User->getOpcode() == ISD::EH_LABEL) { 1600 // If their node ID got reset to -1 then they've already been selected. 1601 // Treat them like a MachineOpcode. 1602 if (User->getNodeId() == -1) 1603 continue; 1604 } 1605 1606 // If we have a TokenFactor, we handle it specially. 1607 if (User->getOpcode() != ISD::TokenFactor) { 1608 // If the node isn't a token factor and isn't part of our pattern, then it 1609 // must be a random chained node in between two nodes we're selecting. 1610 // This happens when we have something like: 1611 // x = load ptr 1612 // call 1613 // y = x+4 1614 // store y -> ptr 1615 // Because we structurally match the load/store as a read/modify/write, 1616 // but the call is chained between them. We cannot fold in this case 1617 // because it would induce a cycle in the graph. 1618 if (!std::count(ChainedNodesInPattern.begin(), 1619 ChainedNodesInPattern.end(), User)) 1620 return CR_InducesCycle; 1621 1622 // Otherwise we found a node that is part of our pattern. For example in: 1623 // x = load ptr 1624 // y = x+4 1625 // store y -> ptr 1626 // This would happen when we're scanning down from the load and see the 1627 // store as a user. Record that there is a use of ChainedNode that is 1628 // part of the pattern and keep scanning uses. 1629 Result = CR_LeadsToInteriorNode; 1630 InteriorChainedNodes.push_back(User); 1631 continue; 1632 } 1633 1634 // If we found a TokenFactor, there are two cases to consider: first if the 1635 // TokenFactor is just hanging "below" the pattern we're matching (i.e. no 1636 // uses of the TF are in our pattern) we just want to ignore it. Second, 1637 // the TokenFactor can be sandwiched in between two chained nodes, like so: 1638 // [Load chain] 1639 // ^ 1640 // | 1641 // [Load] 1642 // ^ ^ 1643 // | \ DAG's like cheese 1644 // / \ do you? 1645 // / | 1646 // [TokenFactor] [Op] 1647 // ^ ^ 1648 // | | 1649 // \ / 1650 // \ / 1651 // [Store] 1652 // 1653 // In this case, the TokenFactor becomes part of our match and we rewrite it 1654 // as a new TokenFactor. 1655 // 1656 // To distinguish these two cases, do a recursive walk down the uses. 1657 switch (WalkChainUsers(User, ChainedNodesInPattern, InteriorChainedNodes)) { 1658 case CR_Simple: 1659 // If the uses of the TokenFactor are just already-selected nodes, ignore 1660 // it, it is "below" our pattern. 1661 continue; 1662 case CR_InducesCycle: 1663 // If the uses of the TokenFactor lead to nodes that are not part of our 1664 // pattern that are not selected, folding would turn this into a cycle, 1665 // bail out now. 1666 return CR_InducesCycle; 1667 case CR_LeadsToInteriorNode: 1668 break; // Otherwise, keep processing. 1669 } 1670 1671 // Okay, we know we're in the interesting interior case. The TokenFactor 1672 // is now going to be considered part of the pattern so that we rewrite its 1673 // uses (it may have uses that are not part of the pattern) with the 1674 // ultimate chain result of the generated code. We will also add its chain 1675 // inputs as inputs to the ultimate TokenFactor we create. 1676 Result = CR_LeadsToInteriorNode; 1677 ChainedNodesInPattern.push_back(User); 1678 InteriorChainedNodes.push_back(User); 1679 continue; 1680 } 1681 1682 return Result; 1683} 1684 1685/// HandleMergeInputChains - This implements the OPC_EmitMergeInputChains 1686/// operation for when the pattern matched at least one node with a chains. The 1687/// input vector contains a list of all of the chained nodes that we match. We 1688/// must determine if this is a valid thing to cover (i.e. matching it won't 1689/// induce cycles in the DAG) and if so, creating a TokenFactor node. that will 1690/// be used as the input node chain for the generated nodes. 1691static SDValue 1692HandleMergeInputChains(SmallVectorImpl<SDNode*> &ChainNodesMatched, 1693 SelectionDAG *CurDAG) { 1694 // Walk all of the chained nodes we've matched, recursively scanning down the 1695 // users of the chain result. This adds any TokenFactor nodes that are caught 1696 // in between chained nodes to the chained and interior nodes list. 1697 SmallVector<SDNode*, 3> InteriorChainedNodes; 1698 for (unsigned i = 0, e = ChainNodesMatched.size(); i != e; ++i) { 1699 if (WalkChainUsers(ChainNodesMatched[i], ChainNodesMatched, 1700 InteriorChainedNodes) == CR_InducesCycle) 1701 return SDValue(); // Would induce a cycle. 1702 } 1703 1704 // Okay, we have walked all the matched nodes and collected TokenFactor nodes 1705 // that we are interested in. Form our input TokenFactor node. 1706 SmallVector<SDValue, 3> InputChains; 1707 for (unsigned i = 0, e = ChainNodesMatched.size(); i != e; ++i) { 1708 // Add the input chain of this node to the InputChains list (which will be 1709 // the operands of the generated TokenFactor) if it's not an interior node. 1710 SDNode *N = ChainNodesMatched[i]; 1711 if (N->getOpcode() != ISD::TokenFactor) { 1712 if (std::count(InteriorChainedNodes.begin(),InteriorChainedNodes.end(),N)) 1713 continue; 1714 1715 // Otherwise, add the input chain. 1716 SDValue InChain = ChainNodesMatched[i]->getOperand(0); 1717 assert(InChain.getValueType() == MVT::Other && "Not a chain"); 1718 InputChains.push_back(InChain); 1719 continue; 1720 } 1721 1722 // If we have a token factor, we want to add all inputs of the token factor 1723 // that are not part of the pattern we're matching. 1724 for (unsigned op = 0, e = N->getNumOperands(); op != e; ++op) { 1725 if (!std::count(ChainNodesMatched.begin(), ChainNodesMatched.end(), 1726 N->getOperand(op).getNode())) 1727 InputChains.push_back(N->getOperand(op)); 1728 } 1729 } 1730 1731 SDValue Res; 1732 if (InputChains.size() == 1) 1733 return InputChains[0]; 1734 return CurDAG->getNode(ISD::TokenFactor, ChainNodesMatched[0]->getDebugLoc(), 1735 MVT::Other, &InputChains[0], InputChains.size()); 1736} 1737 1738/// MorphNode - Handle morphing a node in place for the selector. 1739SDNode *SelectionDAGISel:: 1740MorphNode(SDNode *Node, unsigned TargetOpc, SDVTList VTList, 1741 const SDValue *Ops, unsigned NumOps, unsigned EmitNodeInfo) { 1742 // It is possible we're using MorphNodeTo to replace a node with no 1743 // normal results with one that has a normal result (or we could be 1744 // adding a chain) and the input could have glue and chains as well. 1745 // In this case we need to shift the operands down. 1746 // FIXME: This is a horrible hack and broken in obscure cases, no worse 1747 // than the old isel though. 1748 int OldGlueResultNo = -1, OldChainResultNo = -1; 1749 1750 unsigned NTMNumResults = Node->getNumValues(); 1751 if (Node->getValueType(NTMNumResults-1) == MVT::Glue) { 1752 OldGlueResultNo = NTMNumResults-1; 1753 if (NTMNumResults != 1 && 1754 Node->getValueType(NTMNumResults-2) == MVT::Other) 1755 OldChainResultNo = NTMNumResults-2; 1756 } else if (Node->getValueType(NTMNumResults-1) == MVT::Other) 1757 OldChainResultNo = NTMNumResults-1; 1758 1759 // Call the underlying SelectionDAG routine to do the transmogrification. Note 1760 // that this deletes operands of the old node that become dead. 1761 SDNode *Res = CurDAG->MorphNodeTo(Node, ~TargetOpc, VTList, Ops, NumOps); 1762 1763 // MorphNodeTo can operate in two ways: if an existing node with the 1764 // specified operands exists, it can just return it. Otherwise, it 1765 // updates the node in place to have the requested operands. 1766 if (Res == Node) { 1767 // If we updated the node in place, reset the node ID. To the isel, 1768 // this should be just like a newly allocated machine node. 1769 Res->setNodeId(-1); 1770 } 1771 1772 unsigned ResNumResults = Res->getNumValues(); 1773 // Move the glue if needed. 1774 if ((EmitNodeInfo & OPFL_GlueOutput) && OldGlueResultNo != -1 && 1775 (unsigned)OldGlueResultNo != ResNumResults-1) 1776 CurDAG->ReplaceAllUsesOfValueWith(SDValue(Node, OldGlueResultNo), 1777 SDValue(Res, ResNumResults-1)); 1778 1779 if ((EmitNodeInfo & OPFL_GlueOutput) != 0) 1780 --ResNumResults; 1781 1782 // Move the chain reference if needed. 1783 if ((EmitNodeInfo & OPFL_Chain) && OldChainResultNo != -1 && 1784 (unsigned)OldChainResultNo != ResNumResults-1) 1785 CurDAG->ReplaceAllUsesOfValueWith(SDValue(Node, OldChainResultNo), 1786 SDValue(Res, ResNumResults-1)); 1787 1788 // Otherwise, no replacement happened because the node already exists. Replace 1789 // Uses of the old node with the new one. 1790 if (Res != Node) 1791 CurDAG->ReplaceAllUsesWith(Node, Res); 1792 1793 return Res; 1794} 1795 1796/// CheckPatternPredicate - Implements OP_CheckPatternPredicate. 1797LLVM_ATTRIBUTE_ALWAYS_INLINE static bool 1798CheckSame(const unsigned char *MatcherTable, unsigned &MatcherIndex, 1799 SDValue N, 1800 const SmallVectorImpl<std::pair<SDValue, SDNode*> > &RecordedNodes) { 1801 // Accept if it is exactly the same as a previously recorded node. 1802 unsigned RecNo = MatcherTable[MatcherIndex++]; 1803 assert(RecNo < RecordedNodes.size() && "Invalid CheckSame"); 1804 return N == RecordedNodes[RecNo].first; 1805} 1806 1807/// CheckPatternPredicate - Implements OP_CheckPatternPredicate. 1808LLVM_ATTRIBUTE_ALWAYS_INLINE static bool 1809CheckPatternPredicate(const unsigned char *MatcherTable, unsigned &MatcherIndex, 1810 SelectionDAGISel &SDISel) { 1811 return SDISel.CheckPatternPredicate(MatcherTable[MatcherIndex++]); 1812} 1813 1814/// CheckNodePredicate - Implements OP_CheckNodePredicate. 1815LLVM_ATTRIBUTE_ALWAYS_INLINE static bool 1816CheckNodePredicate(const unsigned char *MatcherTable, unsigned &MatcherIndex, 1817 SelectionDAGISel &SDISel, SDNode *N) { 1818 return SDISel.CheckNodePredicate(N, MatcherTable[MatcherIndex++]); 1819} 1820 1821LLVM_ATTRIBUTE_ALWAYS_INLINE static bool 1822CheckOpcode(const unsigned char *MatcherTable, unsigned &MatcherIndex, 1823 SDNode *N) { 1824 uint16_t Opc = MatcherTable[MatcherIndex++]; 1825 Opc |= (unsigned short)MatcherTable[MatcherIndex++] << 8; 1826 return N->getOpcode() == Opc; 1827} 1828 1829LLVM_ATTRIBUTE_ALWAYS_INLINE static bool 1830CheckType(const unsigned char *MatcherTable, unsigned &MatcherIndex, 1831 SDValue N, const TargetLowering &TLI) { 1832 MVT::SimpleValueType VT = (MVT::SimpleValueType)MatcherTable[MatcherIndex++]; 1833 if (N.getValueType() == VT) return true; 1834 1835 // Handle the case when VT is iPTR. 1836 return VT == MVT::iPTR && N.getValueType() == TLI.getPointerTy(); 1837} 1838 1839LLVM_ATTRIBUTE_ALWAYS_INLINE static bool 1840CheckChildType(const unsigned char *MatcherTable, unsigned &MatcherIndex, 1841 SDValue N, const TargetLowering &TLI, 1842 unsigned ChildNo) { 1843 if (ChildNo >= N.getNumOperands()) 1844 return false; // Match fails if out of range child #. 1845 return ::CheckType(MatcherTable, MatcherIndex, N.getOperand(ChildNo), TLI); 1846} 1847 1848 1849LLVM_ATTRIBUTE_ALWAYS_INLINE static bool 1850CheckCondCode(const unsigned char *MatcherTable, unsigned &MatcherIndex, 1851 SDValue N) { 1852 return cast<CondCodeSDNode>(N)->get() == 1853 (ISD::CondCode)MatcherTable[MatcherIndex++]; 1854} 1855 1856LLVM_ATTRIBUTE_ALWAYS_INLINE static bool 1857CheckValueType(const unsigned char *MatcherTable, unsigned &MatcherIndex, 1858 SDValue N, const TargetLowering &TLI) { 1859 MVT::SimpleValueType VT = (MVT::SimpleValueType)MatcherTable[MatcherIndex++]; 1860 if (cast<VTSDNode>(N)->getVT() == VT) 1861 return true; 1862 1863 // Handle the case when VT is iPTR. 1864 return VT == MVT::iPTR && cast<VTSDNode>(N)->getVT() == TLI.getPointerTy(); 1865} 1866 1867LLVM_ATTRIBUTE_ALWAYS_INLINE static bool 1868CheckInteger(const unsigned char *MatcherTable, unsigned &MatcherIndex, 1869 SDValue N) { 1870 int64_t Val = MatcherTable[MatcherIndex++]; 1871 if (Val & 128) 1872 Val = GetVBR(Val, MatcherTable, MatcherIndex); 1873 1874 ConstantSDNode *C = dyn_cast<ConstantSDNode>(N); 1875 return C != 0 && C->getSExtValue() == Val; 1876} 1877 1878LLVM_ATTRIBUTE_ALWAYS_INLINE static bool 1879CheckAndImm(const unsigned char *MatcherTable, unsigned &MatcherIndex, 1880 SDValue N, SelectionDAGISel &SDISel) { 1881 int64_t Val = MatcherTable[MatcherIndex++]; 1882 if (Val & 128) 1883 Val = GetVBR(Val, MatcherTable, MatcherIndex); 1884 1885 if (N->getOpcode() != ISD::AND) return false; 1886 1887 ConstantSDNode *C = dyn_cast<ConstantSDNode>(N->getOperand(1)); 1888 return C != 0 && SDISel.CheckAndMask(N.getOperand(0), C, Val); 1889} 1890 1891LLVM_ATTRIBUTE_ALWAYS_INLINE static bool 1892CheckOrImm(const unsigned char *MatcherTable, unsigned &MatcherIndex, 1893 SDValue N, SelectionDAGISel &SDISel) { 1894 int64_t Val = MatcherTable[MatcherIndex++]; 1895 if (Val & 128) 1896 Val = GetVBR(Val, MatcherTable, MatcherIndex); 1897 1898 if (N->getOpcode() != ISD::OR) return false; 1899 1900 ConstantSDNode *C = dyn_cast<ConstantSDNode>(N->getOperand(1)); 1901 return C != 0 && SDISel.CheckOrMask(N.getOperand(0), C, Val); 1902} 1903 1904/// IsPredicateKnownToFail - If we know how and can do so without pushing a 1905/// scope, evaluate the current node. If the current predicate is known to 1906/// fail, set Result=true and return anything. If the current predicate is 1907/// known to pass, set Result=false and return the MatcherIndex to continue 1908/// with. If the current predicate is unknown, set Result=false and return the 1909/// MatcherIndex to continue with. 1910static unsigned IsPredicateKnownToFail(const unsigned char *Table, 1911 unsigned Index, SDValue N, 1912 bool &Result, SelectionDAGISel &SDISel, 1913 SmallVectorImpl<std::pair<SDValue, SDNode*> > &RecordedNodes) { 1914 switch (Table[Index++]) { 1915 default: 1916 Result = false; 1917 return Index-1; // Could not evaluate this predicate. 1918 case SelectionDAGISel::OPC_CheckSame: 1919 Result = !::CheckSame(Table, Index, N, RecordedNodes); 1920 return Index; 1921 case SelectionDAGISel::OPC_CheckPatternPredicate: 1922 Result = !::CheckPatternPredicate(Table, Index, SDISel); 1923 return Index; 1924 case SelectionDAGISel::OPC_CheckPredicate: 1925 Result = !::CheckNodePredicate(Table, Index, SDISel, N.getNode()); 1926 return Index; 1927 case SelectionDAGISel::OPC_CheckOpcode: 1928 Result = !::CheckOpcode(Table, Index, N.getNode()); 1929 return Index; 1930 case SelectionDAGISel::OPC_CheckType: 1931 Result = !::CheckType(Table, Index, N, SDISel.TLI); 1932 return Index; 1933 case SelectionDAGISel::OPC_CheckChild0Type: 1934 case SelectionDAGISel::OPC_CheckChild1Type: 1935 case SelectionDAGISel::OPC_CheckChild2Type: 1936 case SelectionDAGISel::OPC_CheckChild3Type: 1937 case SelectionDAGISel::OPC_CheckChild4Type: 1938 case SelectionDAGISel::OPC_CheckChild5Type: 1939 case SelectionDAGISel::OPC_CheckChild6Type: 1940 case SelectionDAGISel::OPC_CheckChild7Type: 1941 Result = !::CheckChildType(Table, Index, N, SDISel.TLI, 1942 Table[Index-1] - SelectionDAGISel::OPC_CheckChild0Type); 1943 return Index; 1944 case SelectionDAGISel::OPC_CheckCondCode: 1945 Result = !::CheckCondCode(Table, Index, N); 1946 return Index; 1947 case SelectionDAGISel::OPC_CheckValueType: 1948 Result = !::CheckValueType(Table, Index, N, SDISel.TLI); 1949 return Index; 1950 case SelectionDAGISel::OPC_CheckInteger: 1951 Result = !::CheckInteger(Table, Index, N); 1952 return Index; 1953 case SelectionDAGISel::OPC_CheckAndImm: 1954 Result = !::CheckAndImm(Table, Index, N, SDISel); 1955 return Index; 1956 case SelectionDAGISel::OPC_CheckOrImm: 1957 Result = !::CheckOrImm(Table, Index, N, SDISel); 1958 return Index; 1959 } 1960} 1961 1962namespace { 1963 1964struct MatchScope { 1965 /// FailIndex - If this match fails, this is the index to continue with. 1966 unsigned FailIndex; 1967 1968 /// NodeStack - The node stack when the scope was formed. 1969 SmallVector<SDValue, 4> NodeStack; 1970 1971 /// NumRecordedNodes - The number of recorded nodes when the scope was formed. 1972 unsigned NumRecordedNodes; 1973 1974 /// NumMatchedMemRefs - The number of matched memref entries. 1975 unsigned NumMatchedMemRefs; 1976 1977 /// InputChain/InputGlue - The current chain/glue 1978 SDValue InputChain, InputGlue; 1979 1980 /// HasChainNodesMatched - True if the ChainNodesMatched list is non-empty. 1981 bool HasChainNodesMatched, HasGlueResultNodesMatched; 1982}; 1983 1984} 1985 1986SDNode *SelectionDAGISel:: 1987SelectCodeCommon(SDNode *NodeToMatch, const unsigned char *MatcherTable, 1988 unsigned TableSize) { 1989 // FIXME: Should these even be selected? Handle these cases in the caller? 1990 switch (NodeToMatch->getOpcode()) { 1991 default: 1992 break; 1993 case ISD::EntryToken: // These nodes remain the same. 1994 case ISD::BasicBlock: 1995 case ISD::Register: 1996 //case ISD::VALUETYPE: 1997 //case ISD::CONDCODE: 1998 case ISD::HANDLENODE: 1999 case ISD::MDNODE_SDNODE: 2000 case ISD::TargetConstant: 2001 case ISD::TargetConstantFP: 2002 case ISD::TargetConstantPool: 2003 case ISD::TargetFrameIndex: 2004 case ISD::TargetExternalSymbol: 2005 case ISD::TargetBlockAddress: 2006 case ISD::TargetJumpTable: 2007 case ISD::TargetGlobalTLSAddress: 2008 case ISD::TargetGlobalAddress: 2009 case ISD::TokenFactor: 2010 case ISD::CopyFromReg: 2011 case ISD::CopyToReg: 2012 case ISD::EH_LABEL: 2013 NodeToMatch->setNodeId(-1); // Mark selected. 2014 return 0; 2015 case ISD::AssertSext: 2016 case ISD::AssertZext: 2017 CurDAG->ReplaceAllUsesOfValueWith(SDValue(NodeToMatch, 0), 2018 NodeToMatch->getOperand(0)); 2019 return 0; 2020 case ISD::INLINEASM: return Select_INLINEASM(NodeToMatch); 2021 case ISD::UNDEF: return Select_UNDEF(NodeToMatch); 2022 } 2023 2024 assert(!NodeToMatch->isMachineOpcode() && "Node already selected!"); 2025 2026 // Set up the node stack with NodeToMatch as the only node on the stack. 2027 SmallVector<SDValue, 8> NodeStack; 2028 SDValue N = SDValue(NodeToMatch, 0); 2029 NodeStack.push_back(N); 2030 2031 // MatchScopes - Scopes used when matching, if a match failure happens, this 2032 // indicates where to continue checking. 2033 SmallVector<MatchScope, 8> MatchScopes; 2034 2035 // RecordedNodes - This is the set of nodes that have been recorded by the 2036 // state machine. The second value is the parent of the node, or null if the 2037 // root is recorded. 2038 SmallVector<std::pair<SDValue, SDNode*>, 8> RecordedNodes; 2039 2040 // MatchedMemRefs - This is the set of MemRef's we've seen in the input 2041 // pattern. 2042 SmallVector<MachineMemOperand*, 2> MatchedMemRefs; 2043 2044 // These are the current input chain and glue for use when generating nodes. 2045 // Various Emit operations change these. For example, emitting a copytoreg 2046 // uses and updates these. 2047 SDValue InputChain, InputGlue; 2048 2049 // ChainNodesMatched - If a pattern matches nodes that have input/output 2050 // chains, the OPC_EmitMergeInputChains operation is emitted which indicates 2051 // which ones they are. The result is captured into this list so that we can 2052 // update the chain results when the pattern is complete. 2053 SmallVector<SDNode*, 3> ChainNodesMatched; 2054 SmallVector<SDNode*, 3> GlueResultNodesMatched; 2055 2056 DEBUG(errs() << "ISEL: Starting pattern match on root node: "; 2057 NodeToMatch->dump(CurDAG); 2058 errs() << '\n'); 2059 2060 // Determine where to start the interpreter. Normally we start at opcode #0, 2061 // but if the state machine starts with an OPC_SwitchOpcode, then we 2062 // accelerate the first lookup (which is guaranteed to be hot) with the 2063 // OpcodeOffset table. 2064 unsigned MatcherIndex = 0; 2065 2066 if (!OpcodeOffset.empty()) { 2067 // Already computed the OpcodeOffset table, just index into it. 2068 if (N.getOpcode() < OpcodeOffset.size()) 2069 MatcherIndex = OpcodeOffset[N.getOpcode()]; 2070 DEBUG(errs() << " Initial Opcode index to " << MatcherIndex << "\n"); 2071 2072 } else if (MatcherTable[0] == OPC_SwitchOpcode) { 2073 // Otherwise, the table isn't computed, but the state machine does start 2074 // with an OPC_SwitchOpcode instruction. Populate the table now, since this 2075 // is the first time we're selecting an instruction. 2076 unsigned Idx = 1; 2077 while (1) { 2078 // Get the size of this case. 2079 unsigned CaseSize = MatcherTable[Idx++]; 2080 if (CaseSize & 128) 2081 CaseSize = GetVBR(CaseSize, MatcherTable, Idx); 2082 if (CaseSize == 0) break; 2083 2084 // Get the opcode, add the index to the table. 2085 uint16_t Opc = MatcherTable[Idx++]; 2086 Opc |= (unsigned short)MatcherTable[Idx++] << 8; 2087 if (Opc >= OpcodeOffset.size()) 2088 OpcodeOffset.resize((Opc+1)*2); 2089 OpcodeOffset[Opc] = Idx; 2090 Idx += CaseSize; 2091 } 2092 2093 // Okay, do the lookup for the first opcode. 2094 if (N.getOpcode() < OpcodeOffset.size()) 2095 MatcherIndex = OpcodeOffset[N.getOpcode()]; 2096 } 2097 2098 while (1) { 2099 assert(MatcherIndex < TableSize && "Invalid index"); 2100#ifndef NDEBUG 2101 unsigned CurrentOpcodeIndex = MatcherIndex; 2102#endif 2103 BuiltinOpcodes Opcode = (BuiltinOpcodes)MatcherTable[MatcherIndex++]; 2104 switch (Opcode) { 2105 case OPC_Scope: { 2106 // Okay, the semantics of this operation are that we should push a scope 2107 // then evaluate the first child. However, pushing a scope only to have 2108 // the first check fail (which then pops it) is inefficient. If we can 2109 // determine immediately that the first check (or first several) will 2110 // immediately fail, don't even bother pushing a scope for them. 2111 unsigned FailIndex; 2112 2113 while (1) { 2114 unsigned NumToSkip = MatcherTable[MatcherIndex++]; 2115 if (NumToSkip & 128) 2116 NumToSkip = GetVBR(NumToSkip, MatcherTable, MatcherIndex); 2117 // Found the end of the scope with no match. 2118 if (NumToSkip == 0) { 2119 FailIndex = 0; 2120 break; 2121 } 2122 2123 FailIndex = MatcherIndex+NumToSkip; 2124 2125 unsigned MatcherIndexOfPredicate = MatcherIndex; 2126 (void)MatcherIndexOfPredicate; // silence warning. 2127 2128 // If we can't evaluate this predicate without pushing a scope (e.g. if 2129 // it is a 'MoveParent') or if the predicate succeeds on this node, we 2130 // push the scope and evaluate the full predicate chain. 2131 bool Result; 2132 MatcherIndex = IsPredicateKnownToFail(MatcherTable, MatcherIndex, N, 2133 Result, *this, RecordedNodes); 2134 if (!Result) 2135 break; 2136 2137 DEBUG(errs() << " Skipped scope entry (due to false predicate) at " 2138 << "index " << MatcherIndexOfPredicate 2139 << ", continuing at " << FailIndex << "\n"); 2140 ++NumDAGIselRetries; 2141 2142 // Otherwise, we know that this case of the Scope is guaranteed to fail, 2143 // move to the next case. 2144 MatcherIndex = FailIndex; 2145 } 2146 2147 // If the whole scope failed to match, bail. 2148 if (FailIndex == 0) break; 2149 2150 // Push a MatchScope which indicates where to go if the first child fails 2151 // to match. 2152 MatchScope NewEntry; 2153 NewEntry.FailIndex = FailIndex; 2154 NewEntry.NodeStack.append(NodeStack.begin(), NodeStack.end()); 2155 NewEntry.NumRecordedNodes = RecordedNodes.size(); 2156 NewEntry.NumMatchedMemRefs = MatchedMemRefs.size(); 2157 NewEntry.InputChain = InputChain; 2158 NewEntry.InputGlue = InputGlue; 2159 NewEntry.HasChainNodesMatched = !ChainNodesMatched.empty(); 2160 NewEntry.HasGlueResultNodesMatched = !GlueResultNodesMatched.empty(); 2161 MatchScopes.push_back(NewEntry); 2162 continue; 2163 } 2164 case OPC_RecordNode: { 2165 // Remember this node, it may end up being an operand in the pattern. 2166 SDNode *Parent = 0; 2167 if (NodeStack.size() > 1) 2168 Parent = NodeStack[NodeStack.size()-2].getNode(); 2169 RecordedNodes.push_back(std::make_pair(N, Parent)); 2170 continue; 2171 } 2172 2173 case OPC_RecordChild0: case OPC_RecordChild1: 2174 case OPC_RecordChild2: case OPC_RecordChild3: 2175 case OPC_RecordChild4: case OPC_RecordChild5: 2176 case OPC_RecordChild6: case OPC_RecordChild7: { 2177 unsigned ChildNo = Opcode-OPC_RecordChild0; 2178 if (ChildNo >= N.getNumOperands()) 2179 break; // Match fails if out of range child #. 2180 2181 RecordedNodes.push_back(std::make_pair(N->getOperand(ChildNo), 2182 N.getNode())); 2183 continue; 2184 } 2185 case OPC_RecordMemRef: 2186 MatchedMemRefs.push_back(cast<MemSDNode>(N)->getMemOperand()); 2187 continue; 2188 2189 case OPC_CaptureGlueInput: 2190 // If the current node has an input glue, capture it in InputGlue. 2191 if (N->getNumOperands() != 0 && 2192 N->getOperand(N->getNumOperands()-1).getValueType() == MVT::Glue) 2193 InputGlue = N->getOperand(N->getNumOperands()-1); 2194 continue; 2195 2196 case OPC_MoveChild: { 2197 unsigned ChildNo = MatcherTable[MatcherIndex++]; 2198 if (ChildNo >= N.getNumOperands()) 2199 break; // Match fails if out of range child #. 2200 N = N.getOperand(ChildNo); 2201 NodeStack.push_back(N); 2202 continue; 2203 } 2204 2205 case OPC_MoveParent: 2206 // Pop the current node off the NodeStack. 2207 NodeStack.pop_back(); 2208 assert(!NodeStack.empty() && "Node stack imbalance!"); 2209 N = NodeStack.back(); 2210 continue; 2211 2212 case OPC_CheckSame: 2213 if (!::CheckSame(MatcherTable, MatcherIndex, N, RecordedNodes)) break; 2214 continue; 2215 case OPC_CheckPatternPredicate: 2216 if (!::CheckPatternPredicate(MatcherTable, MatcherIndex, *this)) break; 2217 continue; 2218 case OPC_CheckPredicate: 2219 if (!::CheckNodePredicate(MatcherTable, MatcherIndex, *this, 2220 N.getNode())) 2221 break; 2222 continue; 2223 case OPC_CheckComplexPat: { 2224 unsigned CPNum = MatcherTable[MatcherIndex++]; 2225 unsigned RecNo = MatcherTable[MatcherIndex++]; 2226 assert(RecNo < RecordedNodes.size() && "Invalid CheckComplexPat"); 2227 if (!CheckComplexPattern(NodeToMatch, RecordedNodes[RecNo].second, 2228 RecordedNodes[RecNo].first, CPNum, 2229 RecordedNodes)) 2230 break; 2231 continue; 2232 } 2233 case OPC_CheckOpcode: 2234 if (!::CheckOpcode(MatcherTable, MatcherIndex, N.getNode())) break; 2235 continue; 2236 2237 case OPC_CheckType: 2238 if (!::CheckType(MatcherTable, MatcherIndex, N, TLI)) break; 2239 continue; 2240 2241 case OPC_SwitchOpcode: { 2242 unsigned CurNodeOpcode = N.getOpcode(); 2243 unsigned SwitchStart = MatcherIndex-1; (void)SwitchStart; 2244 unsigned CaseSize; 2245 while (1) { 2246 // Get the size of this case. 2247 CaseSize = MatcherTable[MatcherIndex++]; 2248 if (CaseSize & 128) 2249 CaseSize = GetVBR(CaseSize, MatcherTable, MatcherIndex); 2250 if (CaseSize == 0) break; 2251 2252 uint16_t Opc = MatcherTable[MatcherIndex++]; 2253 Opc |= (unsigned short)MatcherTable[MatcherIndex++] << 8; 2254 2255 // If the opcode matches, then we will execute this case. 2256 if (CurNodeOpcode == Opc) 2257 break; 2258 2259 // Otherwise, skip over this case. 2260 MatcherIndex += CaseSize; 2261 } 2262 2263 // If no cases matched, bail out. 2264 if (CaseSize == 0) break; 2265 2266 // Otherwise, execute the case we found. 2267 DEBUG(errs() << " OpcodeSwitch from " << SwitchStart 2268 << " to " << MatcherIndex << "\n"); 2269 continue; 2270 } 2271 2272 case OPC_SwitchType: { 2273 MVT CurNodeVT = N.getValueType().getSimpleVT(); 2274 unsigned SwitchStart = MatcherIndex-1; (void)SwitchStart; 2275 unsigned CaseSize; 2276 while (1) { 2277 // Get the size of this case. 2278 CaseSize = MatcherTable[MatcherIndex++]; 2279 if (CaseSize & 128) 2280 CaseSize = GetVBR(CaseSize, MatcherTable, MatcherIndex); 2281 if (CaseSize == 0) break; 2282 2283 MVT CaseVT = (MVT::SimpleValueType)MatcherTable[MatcherIndex++]; 2284 if (CaseVT == MVT::iPTR) 2285 CaseVT = TLI.getPointerTy(); 2286 2287 // If the VT matches, then we will execute this case. 2288 if (CurNodeVT == CaseVT) 2289 break; 2290 2291 // Otherwise, skip over this case. 2292 MatcherIndex += CaseSize; 2293 } 2294 2295 // If no cases matched, bail out. 2296 if (CaseSize == 0) break; 2297 2298 // Otherwise, execute the case we found. 2299 DEBUG(errs() << " TypeSwitch[" << EVT(CurNodeVT).getEVTString() 2300 << "] from " << SwitchStart << " to " << MatcherIndex<<'\n'); 2301 continue; 2302 } 2303 case OPC_CheckChild0Type: case OPC_CheckChild1Type: 2304 case OPC_CheckChild2Type: case OPC_CheckChild3Type: 2305 case OPC_CheckChild4Type: case OPC_CheckChild5Type: 2306 case OPC_CheckChild6Type: case OPC_CheckChild7Type: 2307 if (!::CheckChildType(MatcherTable, MatcherIndex, N, TLI, 2308 Opcode-OPC_CheckChild0Type)) 2309 break; 2310 continue; 2311 case OPC_CheckCondCode: 2312 if (!::CheckCondCode(MatcherTable, MatcherIndex, N)) break; 2313 continue; 2314 case OPC_CheckValueType: 2315 if (!::CheckValueType(MatcherTable, MatcherIndex, N, TLI)) break; 2316 continue; 2317 case OPC_CheckInteger: 2318 if (!::CheckInteger(MatcherTable, MatcherIndex, N)) break; 2319 continue; 2320 case OPC_CheckAndImm: 2321 if (!::CheckAndImm(MatcherTable, MatcherIndex, N, *this)) break; 2322 continue; 2323 case OPC_CheckOrImm: 2324 if (!::CheckOrImm(MatcherTable, MatcherIndex, N, *this)) break; 2325 continue; 2326 2327 case OPC_CheckFoldableChainNode: { 2328 assert(NodeStack.size() != 1 && "No parent node"); 2329 // Verify that all intermediate nodes between the root and this one have 2330 // a single use. 2331 bool HasMultipleUses = false; 2332 for (unsigned i = 1, e = NodeStack.size()-1; i != e; ++i) 2333 if (!NodeStack[i].hasOneUse()) { 2334 HasMultipleUses = true; 2335 break; 2336 } 2337 if (HasMultipleUses) break; 2338 2339 // Check to see that the target thinks this is profitable to fold and that 2340 // we can fold it without inducing cycles in the graph. 2341 if (!IsProfitableToFold(N, NodeStack[NodeStack.size()-2].getNode(), 2342 NodeToMatch) || 2343 !IsLegalToFold(N, NodeStack[NodeStack.size()-2].getNode(), 2344 NodeToMatch, OptLevel, 2345 true/*We validate our own chains*/)) 2346 break; 2347 2348 continue; 2349 } 2350 case OPC_EmitInteger: { 2351 MVT::SimpleValueType VT = 2352 (MVT::SimpleValueType)MatcherTable[MatcherIndex++]; 2353 int64_t Val = MatcherTable[MatcherIndex++]; 2354 if (Val & 128) 2355 Val = GetVBR(Val, MatcherTable, MatcherIndex); 2356 RecordedNodes.push_back(std::pair<SDValue, SDNode*>( 2357 CurDAG->getTargetConstant(Val, VT), (SDNode*)0)); 2358 continue; 2359 } 2360 case OPC_EmitRegister: { 2361 MVT::SimpleValueType VT = 2362 (MVT::SimpleValueType)MatcherTable[MatcherIndex++]; 2363 unsigned RegNo = MatcherTable[MatcherIndex++]; 2364 RecordedNodes.push_back(std::pair<SDValue, SDNode*>( 2365 CurDAG->getRegister(RegNo, VT), (SDNode*)0)); 2366 continue; 2367 } 2368 case OPC_EmitRegister2: { 2369 // For targets w/ more than 256 register names, the register enum 2370 // values are stored in two bytes in the matcher table (just like 2371 // opcodes). 2372 MVT::SimpleValueType VT = 2373 (MVT::SimpleValueType)MatcherTable[MatcherIndex++]; 2374 unsigned RegNo = MatcherTable[MatcherIndex++]; 2375 RegNo |= MatcherTable[MatcherIndex++] << 8; 2376 RecordedNodes.push_back(std::pair<SDValue, SDNode*>( 2377 CurDAG->getRegister(RegNo, VT), (SDNode*)0)); 2378 continue; 2379 } 2380 2381 case OPC_EmitConvertToTarget: { 2382 // Convert from IMM/FPIMM to target version. 2383 unsigned RecNo = MatcherTable[MatcherIndex++]; 2384 assert(RecNo < RecordedNodes.size() && "Invalid CheckSame"); 2385 SDValue Imm = RecordedNodes[RecNo].first; 2386 2387 if (Imm->getOpcode() == ISD::Constant) { 2388 int64_t Val = cast<ConstantSDNode>(Imm)->getZExtValue(); 2389 Imm = CurDAG->getTargetConstant(Val, Imm.getValueType()); 2390 } else if (Imm->getOpcode() == ISD::ConstantFP) { 2391 const ConstantFP *Val=cast<ConstantFPSDNode>(Imm)->getConstantFPValue(); 2392 Imm = CurDAG->getTargetConstantFP(*Val, Imm.getValueType()); 2393 } 2394 2395 RecordedNodes.push_back(std::make_pair(Imm, RecordedNodes[RecNo].second)); 2396 continue; 2397 } 2398 2399 case OPC_EmitMergeInputChains1_0: // OPC_EmitMergeInputChains, 1, 0 2400 case OPC_EmitMergeInputChains1_1: { // OPC_EmitMergeInputChains, 1, 1 2401 // These are space-optimized forms of OPC_EmitMergeInputChains. 2402 assert(InputChain.getNode() == 0 && 2403 "EmitMergeInputChains should be the first chain producing node"); 2404 assert(ChainNodesMatched.empty() && 2405 "Should only have one EmitMergeInputChains per match"); 2406 2407 // Read all of the chained nodes. 2408 unsigned RecNo = Opcode == OPC_EmitMergeInputChains1_1; 2409 assert(RecNo < RecordedNodes.size() && "Invalid CheckSame"); 2410 ChainNodesMatched.push_back(RecordedNodes[RecNo].first.getNode()); 2411 2412 // FIXME: What if other value results of the node have uses not matched 2413 // by this pattern? 2414 if (ChainNodesMatched.back() != NodeToMatch && 2415 !RecordedNodes[RecNo].first.hasOneUse()) { 2416 ChainNodesMatched.clear(); 2417 break; 2418 } 2419 2420 // Merge the input chains if they are not intra-pattern references. 2421 InputChain = HandleMergeInputChains(ChainNodesMatched, CurDAG); 2422 2423 if (InputChain.getNode() == 0) 2424 break; // Failed to merge. 2425 continue; 2426 } 2427 2428 case OPC_EmitMergeInputChains: { 2429 assert(InputChain.getNode() == 0 && 2430 "EmitMergeInputChains should be the first chain producing node"); 2431 // This node gets a list of nodes we matched in the input that have 2432 // chains. We want to token factor all of the input chains to these nodes 2433 // together. However, if any of the input chains is actually one of the 2434 // nodes matched in this pattern, then we have an intra-match reference. 2435 // Ignore these because the newly token factored chain should not refer to 2436 // the old nodes. 2437 unsigned NumChains = MatcherTable[MatcherIndex++]; 2438 assert(NumChains != 0 && "Can't TF zero chains"); 2439 2440 assert(ChainNodesMatched.empty() && 2441 "Should only have one EmitMergeInputChains per match"); 2442 2443 // Read all of the chained nodes. 2444 for (unsigned i = 0; i != NumChains; ++i) { 2445 unsigned RecNo = MatcherTable[MatcherIndex++]; 2446 assert(RecNo < RecordedNodes.size() && "Invalid CheckSame"); 2447 ChainNodesMatched.push_back(RecordedNodes[RecNo].first.getNode()); 2448 2449 // FIXME: What if other value results of the node have uses not matched 2450 // by this pattern? 2451 if (ChainNodesMatched.back() != NodeToMatch && 2452 !RecordedNodes[RecNo].first.hasOneUse()) { 2453 ChainNodesMatched.clear(); 2454 break; 2455 } 2456 } 2457 2458 // If the inner loop broke out, the match fails. 2459 if (ChainNodesMatched.empty()) 2460 break; 2461 2462 // Merge the input chains if they are not intra-pattern references. 2463 InputChain = HandleMergeInputChains(ChainNodesMatched, CurDAG); 2464 2465 if (InputChain.getNode() == 0) 2466 break; // Failed to merge. 2467 2468 continue; 2469 } 2470 2471 case OPC_EmitCopyToReg: { 2472 unsigned RecNo = MatcherTable[MatcherIndex++]; 2473 assert(RecNo < RecordedNodes.size() && "Invalid CheckSame"); 2474 unsigned DestPhysReg = MatcherTable[MatcherIndex++]; 2475 2476 if (InputChain.getNode() == 0) 2477 InputChain = CurDAG->getEntryNode(); 2478 2479 InputChain = CurDAG->getCopyToReg(InputChain, NodeToMatch->getDebugLoc(), 2480 DestPhysReg, RecordedNodes[RecNo].first, 2481 InputGlue); 2482 2483 InputGlue = InputChain.getValue(1); 2484 continue; 2485 } 2486 2487 case OPC_EmitNodeXForm: { 2488 unsigned XFormNo = MatcherTable[MatcherIndex++]; 2489 unsigned RecNo = MatcherTable[MatcherIndex++]; 2490 assert(RecNo < RecordedNodes.size() && "Invalid CheckSame"); 2491 SDValue Res = RunSDNodeXForm(RecordedNodes[RecNo].first, XFormNo); 2492 RecordedNodes.push_back(std::pair<SDValue,SDNode*>(Res, (SDNode*) 0)); 2493 continue; 2494 } 2495 2496 case OPC_EmitNode: 2497 case OPC_MorphNodeTo: { 2498 uint16_t TargetOpc = MatcherTable[MatcherIndex++]; 2499 TargetOpc |= (unsigned short)MatcherTable[MatcherIndex++] << 8; 2500 unsigned EmitNodeInfo = MatcherTable[MatcherIndex++]; 2501 // Get the result VT list. 2502 unsigned NumVTs = MatcherTable[MatcherIndex++]; 2503 SmallVector<EVT, 4> VTs; 2504 for (unsigned i = 0; i != NumVTs; ++i) { 2505 MVT::SimpleValueType VT = 2506 (MVT::SimpleValueType)MatcherTable[MatcherIndex++]; 2507 if (VT == MVT::iPTR) VT = TLI.getPointerTy().SimpleTy; 2508 VTs.push_back(VT); 2509 } 2510 2511 if (EmitNodeInfo & OPFL_Chain) 2512 VTs.push_back(MVT::Other); 2513 if (EmitNodeInfo & OPFL_GlueOutput) 2514 VTs.push_back(MVT::Glue); 2515 2516 // This is hot code, so optimize the two most common cases of 1 and 2 2517 // results. 2518 SDVTList VTList; 2519 if (VTs.size() == 1) 2520 VTList = CurDAG->getVTList(VTs[0]); 2521 else if (VTs.size() == 2) 2522 VTList = CurDAG->getVTList(VTs[0], VTs[1]); 2523 else 2524 VTList = CurDAG->getVTList(VTs.data(), VTs.size()); 2525 2526 // Get the operand list. 2527 unsigned NumOps = MatcherTable[MatcherIndex++]; 2528 SmallVector<SDValue, 8> Ops; 2529 for (unsigned i = 0; i != NumOps; ++i) { 2530 unsigned RecNo = MatcherTable[MatcherIndex++]; 2531 if (RecNo & 128) 2532 RecNo = GetVBR(RecNo, MatcherTable, MatcherIndex); 2533 2534 assert(RecNo < RecordedNodes.size() && "Invalid EmitNode"); 2535 Ops.push_back(RecordedNodes[RecNo].first); 2536 } 2537 2538 // If there are variadic operands to add, handle them now. 2539 if (EmitNodeInfo & OPFL_VariadicInfo) { 2540 // Determine the start index to copy from. 2541 unsigned FirstOpToCopy = getNumFixedFromVariadicInfo(EmitNodeInfo); 2542 FirstOpToCopy += (EmitNodeInfo & OPFL_Chain) ? 1 : 0; 2543 assert(NodeToMatch->getNumOperands() >= FirstOpToCopy && 2544 "Invalid variadic node"); 2545 // Copy all of the variadic operands, not including a potential glue 2546 // input. 2547 for (unsigned i = FirstOpToCopy, e = NodeToMatch->getNumOperands(); 2548 i != e; ++i) { 2549 SDValue V = NodeToMatch->getOperand(i); 2550 if (V.getValueType() == MVT::Glue) break; 2551 Ops.push_back(V); 2552 } 2553 } 2554 2555 // If this has chain/glue inputs, add them. 2556 if (EmitNodeInfo & OPFL_Chain) 2557 Ops.push_back(InputChain); 2558 if ((EmitNodeInfo & OPFL_GlueInput) && InputGlue.getNode() != 0) 2559 Ops.push_back(InputGlue); 2560 2561 // Create the node. 2562 SDNode *Res = 0; 2563 if (Opcode != OPC_MorphNodeTo) { 2564 // If this is a normal EmitNode command, just create the new node and 2565 // add the results to the RecordedNodes list. 2566 Res = CurDAG->getMachineNode(TargetOpc, NodeToMatch->getDebugLoc(), 2567 VTList, Ops.data(), Ops.size()); 2568 2569 // Add all the non-glue/non-chain results to the RecordedNodes list. 2570 for (unsigned i = 0, e = VTs.size(); i != e; ++i) { 2571 if (VTs[i] == MVT::Other || VTs[i] == MVT::Glue) break; 2572 RecordedNodes.push_back(std::pair<SDValue,SDNode*>(SDValue(Res, i), 2573 (SDNode*) 0)); 2574 } 2575 2576 } else { 2577 Res = MorphNode(NodeToMatch, TargetOpc, VTList, Ops.data(), Ops.size(), 2578 EmitNodeInfo); 2579 } 2580 2581 // If the node had chain/glue results, update our notion of the current 2582 // chain and glue. 2583 if (EmitNodeInfo & OPFL_GlueOutput) { 2584 InputGlue = SDValue(Res, VTs.size()-1); 2585 if (EmitNodeInfo & OPFL_Chain) 2586 InputChain = SDValue(Res, VTs.size()-2); 2587 } else if (EmitNodeInfo & OPFL_Chain) 2588 InputChain = SDValue(Res, VTs.size()-1); 2589 2590 // If the OPFL_MemRefs glue is set on this node, slap all of the 2591 // accumulated memrefs onto it. 2592 // 2593 // FIXME: This is vastly incorrect for patterns with multiple outputs 2594 // instructions that access memory and for ComplexPatterns that match 2595 // loads. 2596 if (EmitNodeInfo & OPFL_MemRefs) { 2597 // Only attach load or store memory operands if the generated 2598 // instruction may load or store. 2599 const TargetInstrDesc &TID = TM.getInstrInfo()->get(TargetOpc); 2600 bool mayLoad = TID.mayLoad(); 2601 bool mayStore = TID.mayStore(); 2602 2603 unsigned NumMemRefs = 0; 2604 for (SmallVector<MachineMemOperand*, 2>::const_iterator I = 2605 MatchedMemRefs.begin(), E = MatchedMemRefs.end(); I != E; ++I) { 2606 if ((*I)->isLoad()) { 2607 if (mayLoad) 2608 ++NumMemRefs; 2609 } else if ((*I)->isStore()) { 2610 if (mayStore) 2611 ++NumMemRefs; 2612 } else { 2613 ++NumMemRefs; 2614 } 2615 } 2616 2617 MachineSDNode::mmo_iterator MemRefs = 2618 MF->allocateMemRefsArray(NumMemRefs); 2619 2620 MachineSDNode::mmo_iterator MemRefsPos = MemRefs; 2621 for (SmallVector<MachineMemOperand*, 2>::const_iterator I = 2622 MatchedMemRefs.begin(), E = MatchedMemRefs.end(); I != E; ++I) { 2623 if ((*I)->isLoad()) { 2624 if (mayLoad) 2625 *MemRefsPos++ = *I; 2626 } else if ((*I)->isStore()) { 2627 if (mayStore) 2628 *MemRefsPos++ = *I; 2629 } else { 2630 *MemRefsPos++ = *I; 2631 } 2632 } 2633 2634 cast<MachineSDNode>(Res) 2635 ->setMemRefs(MemRefs, MemRefs + NumMemRefs); 2636 } 2637 2638 DEBUG(errs() << " " 2639 << (Opcode == OPC_MorphNodeTo ? "Morphed" : "Created") 2640 << " node: "; Res->dump(CurDAG); errs() << "\n"); 2641 2642 // If this was a MorphNodeTo then we're completely done! 2643 if (Opcode == OPC_MorphNodeTo) { 2644 // Update chain and glue uses. 2645 UpdateChainsAndGlue(NodeToMatch, InputChain, ChainNodesMatched, 2646 InputGlue, GlueResultNodesMatched, true); 2647 return Res; 2648 } 2649 2650 continue; 2651 } 2652 2653 case OPC_MarkGlueResults: { 2654 unsigned NumNodes = MatcherTable[MatcherIndex++]; 2655 2656 // Read and remember all the glue-result nodes. 2657 for (unsigned i = 0; i != NumNodes; ++i) { 2658 unsigned RecNo = MatcherTable[MatcherIndex++]; 2659 if (RecNo & 128) 2660 RecNo = GetVBR(RecNo, MatcherTable, MatcherIndex); 2661 2662 assert(RecNo < RecordedNodes.size() && "Invalid CheckSame"); 2663 GlueResultNodesMatched.push_back(RecordedNodes[RecNo].first.getNode()); 2664 } 2665 continue; 2666 } 2667 2668 case OPC_CompleteMatch: { 2669 // The match has been completed, and any new nodes (if any) have been 2670 // created. Patch up references to the matched dag to use the newly 2671 // created nodes. 2672 unsigned NumResults = MatcherTable[MatcherIndex++]; 2673 2674 for (unsigned i = 0; i != NumResults; ++i) { 2675 unsigned ResSlot = MatcherTable[MatcherIndex++]; 2676 if (ResSlot & 128) 2677 ResSlot = GetVBR(ResSlot, MatcherTable, MatcherIndex); 2678 2679 assert(ResSlot < RecordedNodes.size() && "Invalid CheckSame"); 2680 SDValue Res = RecordedNodes[ResSlot].first; 2681 2682 assert(i < NodeToMatch->getNumValues() && 2683 NodeToMatch->getValueType(i) != MVT::Other && 2684 NodeToMatch->getValueType(i) != MVT::Glue && 2685 "Invalid number of results to complete!"); 2686 assert((NodeToMatch->getValueType(i) == Res.getValueType() || 2687 NodeToMatch->getValueType(i) == MVT::iPTR || 2688 Res.getValueType() == MVT::iPTR || 2689 NodeToMatch->getValueType(i).getSizeInBits() == 2690 Res.getValueType().getSizeInBits()) && 2691 "invalid replacement"); 2692 CurDAG->ReplaceAllUsesOfValueWith(SDValue(NodeToMatch, i), Res); 2693 } 2694 2695 // If the root node defines glue, add it to the glue nodes to update list. 2696 if (NodeToMatch->getValueType(NodeToMatch->getNumValues()-1) == MVT::Glue) 2697 GlueResultNodesMatched.push_back(NodeToMatch); 2698 2699 // Update chain and glue uses. 2700 UpdateChainsAndGlue(NodeToMatch, InputChain, ChainNodesMatched, 2701 InputGlue, GlueResultNodesMatched, false); 2702 2703 assert(NodeToMatch->use_empty() && 2704 "Didn't replace all uses of the node?"); 2705 2706 // FIXME: We just return here, which interacts correctly with SelectRoot 2707 // above. We should fix this to not return an SDNode* anymore. 2708 return 0; 2709 } 2710 } 2711 2712 // If the code reached this point, then the match failed. See if there is 2713 // another child to try in the current 'Scope', otherwise pop it until we 2714 // find a case to check. 2715 DEBUG(errs() << " Match failed at index " << CurrentOpcodeIndex << "\n"); 2716 ++NumDAGIselRetries; 2717 while (1) { 2718 if (MatchScopes.empty()) { 2719 CannotYetSelect(NodeToMatch); 2720 return 0; 2721 } 2722 2723 // Restore the interpreter state back to the point where the scope was 2724 // formed. 2725 MatchScope &LastScope = MatchScopes.back(); 2726 RecordedNodes.resize(LastScope.NumRecordedNodes); 2727 NodeStack.clear(); 2728 NodeStack.append(LastScope.NodeStack.begin(), LastScope.NodeStack.end()); 2729 N = NodeStack.back(); 2730 2731 if (LastScope.NumMatchedMemRefs != MatchedMemRefs.size()) 2732 MatchedMemRefs.resize(LastScope.NumMatchedMemRefs); 2733 MatcherIndex = LastScope.FailIndex; 2734 2735 DEBUG(errs() << " Continuing at " << MatcherIndex << "\n"); 2736 2737 InputChain = LastScope.InputChain; 2738 InputGlue = LastScope.InputGlue; 2739 if (!LastScope.HasChainNodesMatched) 2740 ChainNodesMatched.clear(); 2741 if (!LastScope.HasGlueResultNodesMatched) 2742 GlueResultNodesMatched.clear(); 2743 2744 // Check to see what the offset is at the new MatcherIndex. If it is zero 2745 // we have reached the end of this scope, otherwise we have another child 2746 // in the current scope to try. 2747 unsigned NumToSkip = MatcherTable[MatcherIndex++]; 2748 if (NumToSkip & 128) 2749 NumToSkip = GetVBR(NumToSkip, MatcherTable, MatcherIndex); 2750 2751 // If we have another child in this scope to match, update FailIndex and 2752 // try it. 2753 if (NumToSkip != 0) { 2754 LastScope.FailIndex = MatcherIndex+NumToSkip; 2755 break; 2756 } 2757 2758 // End of this scope, pop it and try the next child in the containing 2759 // scope. 2760 MatchScopes.pop_back(); 2761 } 2762 } 2763} 2764 2765 2766 2767void SelectionDAGISel::CannotYetSelect(SDNode *N) { 2768 std::string msg; 2769 raw_string_ostream Msg(msg); 2770 Msg << "Cannot select: "; 2771 2772 if (N->getOpcode() != ISD::INTRINSIC_W_CHAIN && 2773 N->getOpcode() != ISD::INTRINSIC_WO_CHAIN && 2774 N->getOpcode() != ISD::INTRINSIC_VOID) { 2775 N->printrFull(Msg, CurDAG); 2776 } else { 2777 bool HasInputChain = N->getOperand(0).getValueType() == MVT::Other; 2778 unsigned iid = 2779 cast<ConstantSDNode>(N->getOperand(HasInputChain))->getZExtValue(); 2780 if (iid < Intrinsic::num_intrinsics) 2781 Msg << "intrinsic %" << Intrinsic::getName((Intrinsic::ID)iid); 2782 else if (const TargetIntrinsicInfo *TII = TM.getIntrinsicInfo()) 2783 Msg << "target intrinsic %" << TII->getName(iid); 2784 else 2785 Msg << "unknown intrinsic #" << iid; 2786 } 2787 report_fatal_error(Msg.str()); 2788} 2789 2790char SelectionDAGISel::ID = 0; 2791