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