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