1193323Sed//===-- SelectionDAGISel.cpp - Implement the SelectionDAGISel class -------===// 2193323Sed// 3193323Sed// The LLVM Compiler Infrastructure 4193323Sed// 5193323Sed// This file is distributed under the University of Illinois Open Source 6193323Sed// License. See LICENSE.TXT for details. 7193323Sed// 8193323Sed//===----------------------------------------------------------------------===// 9193323Sed// 10193323Sed// This implements the SelectionDAGISel class. 11193323Sed// 12193323Sed//===----------------------------------------------------------------------===// 13193323Sed 14193323Sed#define DEBUG_TYPE "isel" 15252723Sdim#include "llvm/CodeGen/SelectionDAGISel.h" 16193323Sed#include "ScheduleDAGSDNodes.h" 17199989Srdivacky#include "SelectionDAGBuilder.h" 18252723Sdim#include "llvm/ADT/PostOrderIterator.h" 19252723Sdim#include "llvm/ADT/Statistic.h" 20245431Sdim#include "llvm/Analysis/AliasAnalysis.h" 21245431Sdim#include "llvm/Analysis/BranchProbabilityInfo.h" 22263509Sdim#include "llvm/Analysis/CFG.h" 23252723Sdim#include "llvm/Analysis/TargetTransformInfo.h" 24193323Sed#include "llvm/CodeGen/FastISel.h" 25245431Sdim#include "llvm/CodeGen/FunctionLoweringInfo.h" 26252723Sdim#include "llvm/CodeGen/GCMetadata.h" 27193323Sed#include "llvm/CodeGen/GCStrategy.h" 28208599Srdivacky#include "llvm/CodeGen/MachineFrameInfo.h" 29193323Sed#include "llvm/CodeGen/MachineFunction.h" 30193323Sed#include "llvm/CodeGen/MachineInstrBuilder.h" 31193323Sed#include "llvm/CodeGen/MachineModuleInfo.h" 32193323Sed#include "llvm/CodeGen/MachineRegisterInfo.h" 33193323Sed#include "llvm/CodeGen/ScheduleHazardRecognizer.h" 34193323Sed#include "llvm/CodeGen/SchedulerRegistry.h" 35193323Sed#include "llvm/CodeGen/SelectionDAG.h" 36252723Sdim#include "llvm/DebugInfo.h" 37252723Sdim#include "llvm/IR/Constants.h" 38252723Sdim#include "llvm/IR/Function.h" 39252723Sdim#include "llvm/IR/InlineAsm.h" 40252723Sdim#include "llvm/IR/Instructions.h" 41252723Sdim#include "llvm/IR/IntrinsicInst.h" 42252723Sdim#include "llvm/IR/Intrinsics.h" 43252723Sdim#include "llvm/IR/LLVMContext.h" 44252723Sdim#include "llvm/IR/Module.h" 45252723Sdim#include "llvm/Support/Compiler.h" 46252723Sdim#include "llvm/Support/Debug.h" 47252723Sdim#include "llvm/Support/ErrorHandling.h" 48252723Sdim#include "llvm/Support/Timer.h" 49252723Sdim#include "llvm/Support/raw_ostream.h" 50252723Sdim#include "llvm/Target/TargetInstrInfo.h" 51198892Srdivacky#include "llvm/Target/TargetIntrinsicInfo.h" 52235633Sdim#include "llvm/Target/TargetLibraryInfo.h" 53193323Sed#include "llvm/Target/TargetLowering.h" 54193323Sed#include "llvm/Target/TargetMachine.h" 55193323Sed#include "llvm/Target/TargetOptions.h" 56252723Sdim#include "llvm/Target/TargetRegisterInfo.h" 57252723Sdim#include "llvm/Target/TargetSubtargetInfo.h" 58218893Sdim#include "llvm/Transforms/Utils/BasicBlockUtils.h" 59193323Sed#include <algorithm> 60193323Sedusing namespace llvm; 61193323Sed 62204792SrdivackySTATISTIC(NumFastIselFailures, "Number of instructions fast isel failed on"); 63223017SdimSTATISTIC(NumFastIselSuccess, "Number of instructions fast isel selected"); 64218893SdimSTATISTIC(NumFastIselBlocks, "Number of blocks selected entirely by fast isel"); 65218893SdimSTATISTIC(NumDAGBlocks, "Number of blocks selected using DAG"); 66206083SrdivackySTATISTIC(NumDAGIselRetries,"Number of times dag isel has to try another path"); 67252723SdimSTATISTIC(NumEntryBlocks, "Number of entry blocks encountered"); 68252723SdimSTATISTIC(NumFastIselFailLowerArguments, 69252723Sdim "Number of entry blocks where fast isel failed to lower arguments"); 70204792Srdivacky 71235633Sdim#ifndef NDEBUG 72193323Sedstatic cl::opt<bool> 73235633SdimEnableFastISelVerbose2("fast-isel-verbose2", cl::Hidden, 74235633Sdim cl::desc("Enable extra verbose messages in the \"fast\" " 75235633Sdim "instruction selector")); 76252723Sdim 77235633Sdim // Terminators 78235633SdimSTATISTIC(NumFastIselFailRet,"Fast isel fails on Ret"); 79235633SdimSTATISTIC(NumFastIselFailBr,"Fast isel fails on Br"); 80235633SdimSTATISTIC(NumFastIselFailSwitch,"Fast isel fails on Switch"); 81235633SdimSTATISTIC(NumFastIselFailIndirectBr,"Fast isel fails on IndirectBr"); 82235633SdimSTATISTIC(NumFastIselFailInvoke,"Fast isel fails on Invoke"); 83235633SdimSTATISTIC(NumFastIselFailResume,"Fast isel fails on Resume"); 84235633SdimSTATISTIC(NumFastIselFailUnreachable,"Fast isel fails on Unreachable"); 85235633Sdim 86235633Sdim // Standard binary operators... 87235633SdimSTATISTIC(NumFastIselFailAdd,"Fast isel fails on Add"); 88235633SdimSTATISTIC(NumFastIselFailFAdd,"Fast isel fails on FAdd"); 89235633SdimSTATISTIC(NumFastIselFailSub,"Fast isel fails on Sub"); 90235633SdimSTATISTIC(NumFastIselFailFSub,"Fast isel fails on FSub"); 91235633SdimSTATISTIC(NumFastIselFailMul,"Fast isel fails on Mul"); 92235633SdimSTATISTIC(NumFastIselFailFMul,"Fast isel fails on FMul"); 93235633SdimSTATISTIC(NumFastIselFailUDiv,"Fast isel fails on UDiv"); 94235633SdimSTATISTIC(NumFastIselFailSDiv,"Fast isel fails on SDiv"); 95235633SdimSTATISTIC(NumFastIselFailFDiv,"Fast isel fails on FDiv"); 96235633SdimSTATISTIC(NumFastIselFailURem,"Fast isel fails on URem"); 97235633SdimSTATISTIC(NumFastIselFailSRem,"Fast isel fails on SRem"); 98235633SdimSTATISTIC(NumFastIselFailFRem,"Fast isel fails on FRem"); 99235633Sdim 100235633Sdim // Logical operators... 101235633SdimSTATISTIC(NumFastIselFailAnd,"Fast isel fails on And"); 102235633SdimSTATISTIC(NumFastIselFailOr,"Fast isel fails on Or"); 103235633SdimSTATISTIC(NumFastIselFailXor,"Fast isel fails on Xor"); 104235633Sdim 105235633Sdim // Memory instructions... 106235633SdimSTATISTIC(NumFastIselFailAlloca,"Fast isel fails on Alloca"); 107235633SdimSTATISTIC(NumFastIselFailLoad,"Fast isel fails on Load"); 108235633SdimSTATISTIC(NumFastIselFailStore,"Fast isel fails on Store"); 109235633SdimSTATISTIC(NumFastIselFailAtomicCmpXchg,"Fast isel fails on AtomicCmpXchg"); 110235633SdimSTATISTIC(NumFastIselFailAtomicRMW,"Fast isel fails on AtomicRWM"); 111235633SdimSTATISTIC(NumFastIselFailFence,"Fast isel fails on Frence"); 112235633SdimSTATISTIC(NumFastIselFailGetElementPtr,"Fast isel fails on GetElementPtr"); 113235633Sdim 114235633Sdim // Convert instructions... 115235633SdimSTATISTIC(NumFastIselFailTrunc,"Fast isel fails on Trunc"); 116235633SdimSTATISTIC(NumFastIselFailZExt,"Fast isel fails on ZExt"); 117235633SdimSTATISTIC(NumFastIselFailSExt,"Fast isel fails on SExt"); 118235633SdimSTATISTIC(NumFastIselFailFPTrunc,"Fast isel fails on FPTrunc"); 119235633SdimSTATISTIC(NumFastIselFailFPExt,"Fast isel fails on FPExt"); 120235633SdimSTATISTIC(NumFastIselFailFPToUI,"Fast isel fails on FPToUI"); 121235633SdimSTATISTIC(NumFastIselFailFPToSI,"Fast isel fails on FPToSI"); 122235633SdimSTATISTIC(NumFastIselFailUIToFP,"Fast isel fails on UIToFP"); 123235633SdimSTATISTIC(NumFastIselFailSIToFP,"Fast isel fails on SIToFP"); 124235633SdimSTATISTIC(NumFastIselFailIntToPtr,"Fast isel fails on IntToPtr"); 125235633SdimSTATISTIC(NumFastIselFailPtrToInt,"Fast isel fails on PtrToInt"); 126235633SdimSTATISTIC(NumFastIselFailBitCast,"Fast isel fails on BitCast"); 127235633Sdim 128235633Sdim // Other instructions... 129235633SdimSTATISTIC(NumFastIselFailICmp,"Fast isel fails on ICmp"); 130235633SdimSTATISTIC(NumFastIselFailFCmp,"Fast isel fails on FCmp"); 131235633SdimSTATISTIC(NumFastIselFailPHI,"Fast isel fails on PHI"); 132235633SdimSTATISTIC(NumFastIselFailSelect,"Fast isel fails on Select"); 133235633SdimSTATISTIC(NumFastIselFailCall,"Fast isel fails on Call"); 134235633SdimSTATISTIC(NumFastIselFailShl,"Fast isel fails on Shl"); 135235633SdimSTATISTIC(NumFastIselFailLShr,"Fast isel fails on LShr"); 136235633SdimSTATISTIC(NumFastIselFailAShr,"Fast isel fails on AShr"); 137235633SdimSTATISTIC(NumFastIselFailVAArg,"Fast isel fails on VAArg"); 138235633SdimSTATISTIC(NumFastIselFailExtractElement,"Fast isel fails on ExtractElement"); 139235633SdimSTATISTIC(NumFastIselFailInsertElement,"Fast isel fails on InsertElement"); 140235633SdimSTATISTIC(NumFastIselFailShuffleVector,"Fast isel fails on ShuffleVector"); 141235633SdimSTATISTIC(NumFastIselFailExtractValue,"Fast isel fails on ExtractValue"); 142235633SdimSTATISTIC(NumFastIselFailInsertValue,"Fast isel fails on InsertValue"); 143235633SdimSTATISTIC(NumFastIselFailLandingPad,"Fast isel fails on LandingPad"); 144235633Sdim#endif 145235633Sdim 146235633Sdimstatic cl::opt<bool> 147193323SedEnableFastISelVerbose("fast-isel-verbose", cl::Hidden, 148193323Sed cl::desc("Enable verbose messages in the \"fast\" " 149193323Sed "instruction selector")); 150193323Sedstatic cl::opt<bool> 151193323SedEnableFastISelAbort("fast-isel-abort", cl::Hidden, 152252723Sdim cl::desc("Enable abort calls when \"fast\" instruction selection " 153252723Sdim "fails to lower an instruction")); 154252723Sdimstatic cl::opt<bool> 155252723SdimEnableFastISelAbortArgs("fast-isel-abort-args", cl::Hidden, 156252723Sdim cl::desc("Enable abort calls when \"fast\" instruction selection " 157252723Sdim "fails to lower a formal argument")); 158193323Sed 159224145Sdimstatic cl::opt<bool> 160224145SdimUseMBPI("use-mbpi", 161224145Sdim cl::desc("use Machine Branch Probability Info"), 162224145Sdim cl::init(true), cl::Hidden); 163224145Sdim 164193323Sed#ifndef NDEBUG 165193323Sedstatic cl::opt<bool> 166193323SedViewDAGCombine1("view-dag-combine1-dags", cl::Hidden, 167193323Sed cl::desc("Pop up a window to show dags before the first " 168193323Sed "dag combine pass")); 169193323Sedstatic cl::opt<bool> 170193323SedViewLegalizeTypesDAGs("view-legalize-types-dags", cl::Hidden, 171193323Sed cl::desc("Pop up a window to show dags before legalize types")); 172193323Sedstatic cl::opt<bool> 173193323SedViewLegalizeDAGs("view-legalize-dags", cl::Hidden, 174193323Sed cl::desc("Pop up a window to show dags before legalize")); 175193323Sedstatic cl::opt<bool> 176193323SedViewDAGCombine2("view-dag-combine2-dags", cl::Hidden, 177193323Sed cl::desc("Pop up a window to show dags before the second " 178193323Sed "dag combine pass")); 179193323Sedstatic cl::opt<bool> 180193323SedViewDAGCombineLT("view-dag-combine-lt-dags", cl::Hidden, 181193323Sed cl::desc("Pop up a window to show dags before the post legalize types" 182193323Sed " dag combine pass")); 183193323Sedstatic cl::opt<bool> 184193323SedViewISelDAGs("view-isel-dags", cl::Hidden, 185193323Sed cl::desc("Pop up a window to show isel dags as they are selected")); 186193323Sedstatic cl::opt<bool> 187193323SedViewSchedDAGs("view-sched-dags", cl::Hidden, 188193323Sed cl::desc("Pop up a window to show sched dags as they are processed")); 189193323Sedstatic cl::opt<bool> 190193323SedViewSUnitDAGs("view-sunit-dags", cl::Hidden, 191193323Sed cl::desc("Pop up a window to show SUnit dags after they are processed")); 192193323Sed#else 193193323Sedstatic const bool ViewDAGCombine1 = false, 194193323Sed ViewLegalizeTypesDAGs = false, ViewLegalizeDAGs = false, 195193323Sed ViewDAGCombine2 = false, 196193323Sed ViewDAGCombineLT = false, 197193323Sed ViewISelDAGs = false, ViewSchedDAGs = false, 198193323Sed ViewSUnitDAGs = false; 199193323Sed#endif 200193323Sed 201193323Sed//===---------------------------------------------------------------------===// 202193323Sed/// 203193323Sed/// RegisterScheduler class - Track the registration of instruction schedulers. 204193323Sed/// 205193323Sed//===---------------------------------------------------------------------===// 206193323SedMachinePassRegistry RegisterScheduler::Registry; 207193323Sed 208193323Sed//===---------------------------------------------------------------------===// 209193323Sed/// 210193323Sed/// ISHeuristic command line option for instruction schedulers. 211193323Sed/// 212193323Sed//===---------------------------------------------------------------------===// 213193323Sedstatic cl::opt<RegisterScheduler::FunctionPassCtor, false, 214193323Sed RegisterPassParser<RegisterScheduler> > 215193323SedISHeuristic("pre-RA-sched", 216193323Sed cl::init(&createDefaultScheduler), 217193323Sed cl::desc("Instruction schedulers available (before register" 218193323Sed " allocation):")); 219193323Sed 220193323Sedstatic RegisterScheduler 221193323SeddefaultListDAGScheduler("default", "Best scheduler for the target", 222193323Sed createDefaultScheduler); 223193323Sed 224193323Sednamespace llvm { 225193323Sed //===--------------------------------------------------------------------===// 226263509Sdim /// \brief This class is used by SelectionDAGISel to temporarily override 227263509Sdim /// the optimization level on a per-function basis. 228263509Sdim class OptLevelChanger { 229263509Sdim SelectionDAGISel &IS; 230263509Sdim CodeGenOpt::Level SavedOptLevel; 231263509Sdim bool SavedFastISel; 232263509Sdim 233263509Sdim public: 234263509Sdim OptLevelChanger(SelectionDAGISel &ISel, 235263509Sdim CodeGenOpt::Level NewOptLevel) : IS(ISel) { 236263509Sdim SavedOptLevel = IS.OptLevel; 237263509Sdim if (NewOptLevel == SavedOptLevel) 238263509Sdim return; 239263509Sdim IS.OptLevel = NewOptLevel; 240263509Sdim IS.TM.setOptLevel(NewOptLevel); 241263509Sdim SavedFastISel = IS.TM.Options.EnableFastISel; 242263509Sdim if (NewOptLevel == CodeGenOpt::None) 243263509Sdim IS.TM.setFastISel(true); 244263509Sdim DEBUG(dbgs() << "\nChanging optimization level for Function " 245263509Sdim << IS.MF->getFunction()->getName() << "\n"); 246263509Sdim DEBUG(dbgs() << "\tBefore: -O" << SavedOptLevel 247263509Sdim << " ; After: -O" << NewOptLevel << "\n"); 248263509Sdim } 249263509Sdim 250263509Sdim ~OptLevelChanger() { 251263509Sdim if (IS.OptLevel == SavedOptLevel) 252263509Sdim return; 253263509Sdim DEBUG(dbgs() << "\nRestoring optimization level for Function " 254263509Sdim << IS.MF->getFunction()->getName() << "\n"); 255263509Sdim DEBUG(dbgs() << "\tBefore: -O" << IS.OptLevel 256263509Sdim << " ; After: -O" << SavedOptLevel << "\n"); 257263509Sdim IS.OptLevel = SavedOptLevel; 258263509Sdim IS.TM.setOptLevel(SavedOptLevel); 259263509Sdim IS.TM.setFastISel(SavedFastISel); 260263509Sdim } 261263509Sdim }; 262263509Sdim 263263509Sdim //===--------------------------------------------------------------------===// 264193323Sed /// createDefaultScheduler - This creates an instruction scheduler appropriate 265193323Sed /// for the target. 266193323Sed ScheduleDAGSDNodes* createDefaultScheduler(SelectionDAGISel *IS, 267193323Sed CodeGenOpt::Level OptLevel) { 268263509Sdim const TargetLowering *TLI = IS->getTargetLowering(); 269252723Sdim const TargetSubtargetInfo &ST = IS->TM.getSubtarget<TargetSubtargetInfo>(); 270193323Sed 271263509Sdim if (OptLevel == CodeGenOpt::None || ST.useMachineScheduler() || 272263509Sdim TLI->getSchedulingPreference() == Sched::Source) 273212904Sdim return createSourceListDAGScheduler(IS, OptLevel); 274263509Sdim if (TLI->getSchedulingPreference() == Sched::RegPressure) 275208599Srdivacky return createBURRListDAGScheduler(IS, OptLevel); 276263509Sdim if (TLI->getSchedulingPreference() == Sched::Hybrid) 277212904Sdim return createHybridListDAGScheduler(IS, OptLevel); 278263509Sdim if (TLI->getSchedulingPreference() == Sched::VLIW) 279235633Sdim return createVLIWDAGScheduler(IS, OptLevel); 280263509Sdim assert(TLI->getSchedulingPreference() == Sched::ILP && 281208599Srdivacky "Unknown sched type!"); 282212904Sdim return createILPListDAGScheduler(IS, OptLevel); 283193323Sed } 284193323Sed} 285193323Sed 286193323Sed// EmitInstrWithCustomInserter - This method should be implemented by targets 287198892Srdivacky// that mark instructions with the 'usesCustomInserter' flag. These 288193323Sed// instructions are special in various ways, which require special support to 289193323Sed// insert. The specified MachineInstr is created but not inserted into any 290198892Srdivacky// basic blocks, and this method is called to expand it into a sequence of 291198892Srdivacky// instructions, potentially also creating new basic blocks and control flow. 292198892Srdivacky// When new basic blocks are inserted and the edges from MBB to its successors 293198892Srdivacky// are modified, the method should insert pairs of <OldSucc, NewSucc> into the 294198892Srdivacky// DenseMap. 295207618SrdivackyMachineBasicBlock * 296207618SrdivackyTargetLowering::EmitInstrWithCustomInserter(MachineInstr *MI, 297207618Srdivacky MachineBasicBlock *MBB) const { 298198090Srdivacky#ifndef NDEBUG 299202375Srdivacky dbgs() << "If a target marks an instruction with " 300198892Srdivacky "'usesCustomInserter', it must implement " 301198090Srdivacky "TargetLowering::EmitInstrWithCustomInserter!"; 302198090Srdivacky#endif 303198090Srdivacky llvm_unreachable(0); 304193323Sed} 305193323Sed 306226890Sdimvoid TargetLowering::AdjustInstrPostInstrSelection(MachineInstr *MI, 307226890Sdim SDNode *Node) const { 308235633Sdim assert(!MI->hasPostISelHook() && 309226890Sdim "If a target marks an instruction with 'hasPostISelHook', " 310226890Sdim "it must implement TargetLowering::AdjustInstrPostInstrSelection!"); 311226890Sdim} 312226890Sdim 313193323Sed//===----------------------------------------------------------------------===// 314193323Sed// SelectionDAGISel code 315193323Sed//===----------------------------------------------------------------------===// 316193323Sed 317263509SdimSelectionDAGISel::SelectionDAGISel(TargetMachine &tm, 318218893Sdim CodeGenOpt::Level OL) : 319263509Sdim MachineFunctionPass(ID), TM(tm), 320263509Sdim FuncInfo(new FunctionLoweringInfo(TM)), 321235633Sdim CurDAG(new SelectionDAG(tm, OL)), 322207618Srdivacky SDB(new SelectionDAGBuilder(*CurDAG, *FuncInfo, OL)), 323193323Sed GFI(), 324193323Sed OptLevel(OL), 325218893Sdim DAGSize(0) { 326218893Sdim initializeGCModuleInfoPass(*PassRegistry::getPassRegistry()); 327218893Sdim initializeAliasAnalysisAnalysisGroup(*PassRegistry::getPassRegistry()); 328224145Sdim initializeBranchProbabilityInfoPass(*PassRegistry::getPassRegistry()); 329235633Sdim initializeTargetLibraryInfoPass(*PassRegistry::getPassRegistry()); 330218893Sdim } 331193323Sed 332193323SedSelectionDAGISel::~SelectionDAGISel() { 333199989Srdivacky delete SDB; 334193323Sed delete CurDAG; 335193323Sed delete FuncInfo; 336193323Sed} 337193323Sed 338193323Sedvoid SelectionDAGISel::getAnalysisUsage(AnalysisUsage &AU) const { 339193323Sed AU.addRequired<AliasAnalysis>(); 340198090Srdivacky AU.addPreserved<AliasAnalysis>(); 341193323Sed AU.addRequired<GCModuleInfo>(); 342198090Srdivacky AU.addPreserved<GCModuleInfo>(); 343235633Sdim AU.addRequired<TargetLibraryInfo>(); 344224145Sdim if (UseMBPI && OptLevel != CodeGenOpt::None) 345224145Sdim AU.addRequired<BranchProbabilityInfo>(); 346198090Srdivacky MachineFunctionPass::getAnalysisUsage(AU); 347193323Sed} 348193323Sed 349218893Sdim/// SplitCriticalSideEffectEdges - Look for critical edges with a PHI value that 350218893Sdim/// may trap on it. In this case we have to split the edge so that the path 351218893Sdim/// through the predecessor block that doesn't go to the phi block doesn't 352218893Sdim/// execute the possibly trapping instruction. 353218893Sdim/// 354218893Sdim/// This is required for correctness, so it must be done at -O0. 355218893Sdim/// 356218893Sdimstatic void SplitCriticalSideEffectEdges(Function &Fn, Pass *SDISel) { 357218893Sdim // Loop for blocks with phi nodes. 358218893Sdim for (Function::iterator BB = Fn.begin(), E = Fn.end(); BB != E; ++BB) { 359218893Sdim PHINode *PN = dyn_cast<PHINode>(BB->begin()); 360218893Sdim if (PN == 0) continue; 361218893Sdim 362218893Sdim ReprocessBlock: 363218893Sdim // For each block with a PHI node, check to see if any of the input values 364218893Sdim // are potentially trapping constant expressions. Constant expressions are 365218893Sdim // the only potentially trapping value that can occur as the argument to a 366218893Sdim // PHI. 367218893Sdim for (BasicBlock::iterator I = BB->begin(); (PN = dyn_cast<PHINode>(I)); ++I) 368218893Sdim for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { 369218893Sdim ConstantExpr *CE = dyn_cast<ConstantExpr>(PN->getIncomingValue(i)); 370218893Sdim if (CE == 0 || !CE->canTrap()) continue; 371218893Sdim 372218893Sdim // The only case we have to worry about is when the edge is critical. 373218893Sdim // Since this block has a PHI Node, we assume it has multiple input 374218893Sdim // edges: check to see if the pred has multiple successors. 375218893Sdim BasicBlock *Pred = PN->getIncomingBlock(i); 376218893Sdim if (Pred->getTerminator()->getNumSuccessors() == 1) 377218893Sdim continue; 378218893Sdim 379218893Sdim // Okay, we have to split this edge. 380218893Sdim SplitCriticalEdge(Pred->getTerminator(), 381218893Sdim GetSuccessorNumber(Pred, BB), SDISel, true); 382218893Sdim goto ReprocessBlock; 383218893Sdim } 384218893Sdim } 385218893Sdim} 386218893Sdim 387198090Srdivackybool SelectionDAGISel::runOnMachineFunction(MachineFunction &mf) { 388193323Sed // Do some sanity-checking on the command-line options. 389235633Sdim assert((!EnableFastISelVerbose || TM.Options.EnableFastISel) && 390193323Sed "-fast-isel-verbose requires -fast-isel"); 391235633Sdim assert((!EnableFastISelAbort || TM.Options.EnableFastISel) && 392193323Sed "-fast-isel-abort requires -fast-isel"); 393193323Sed 394207618Srdivacky const Function &Fn = *mf.getFunction(); 395193323Sed const TargetInstrInfo &TII = *TM.getInstrInfo(); 396193323Sed const TargetRegisterInfo &TRI = *TM.getRegisterInfo(); 397263509Sdim const TargetLowering *TLI = TM.getTargetLowering(); 398193323Sed 399207618Srdivacky MF = &mf; 400193323Sed RegInfo = &MF->getRegInfo(); 401207618Srdivacky AA = &getAnalysis<AliasAnalysis>(); 402235633Sdim LibInfo = &getAnalysis<TargetLibraryInfo>(); 403252723Sdim TTI = getAnalysisIfAvailable<TargetTransformInfo>(); 404207618Srdivacky GFI = Fn.hasGC() ? &getAnalysis<GCModuleInfo>().getFunctionInfo(Fn) : 0; 405207618Srdivacky 406252723Sdim TargetSubtargetInfo &ST = 407252723Sdim const_cast<TargetSubtargetInfo&>(TM.getSubtarget<TargetSubtargetInfo>()); 408252723Sdim ST.resetSubtargetFeatures(MF); 409252723Sdim TM.resetTargetOptions(MF); 410252723Sdim 411263509Sdim // Reset OptLevel to None for optnone functions. 412263509Sdim CodeGenOpt::Level NewOptLevel = OptLevel; 413263509Sdim if (Fn.hasFnAttribute(Attribute::OptimizeNone)) 414263509Sdim NewOptLevel = CodeGenOpt::None; 415263509Sdim OptLevelChanger OLC(*this, NewOptLevel); 416263509Sdim 417202375Srdivacky DEBUG(dbgs() << "\n\n\n=== " << Fn.getName() << "\n"); 418193323Sed 419218893Sdim SplitCriticalSideEffectEdges(const_cast<Function&>(Fn), this); 420218893Sdim 421263509Sdim CurDAG->init(*MF, TTI, TLI); 422263765Sdim FuncInfo->set(Fn, *MF, CurDAG); 423224145Sdim 424224145Sdim if (UseMBPI && OptLevel != CodeGenOpt::None) 425224145Sdim FuncInfo->BPI = &getAnalysis<BranchProbabilityInfo>(); 426224145Sdim else 427224145Sdim FuncInfo->BPI = 0; 428224145Sdim 429235633Sdim SDB->init(GFI, *AA, LibInfo); 430193323Sed 431263765Sdim MF->setHasInlineAsm(false); 432263765Sdim 433207618Srdivacky SelectAllBasicBlocks(Fn); 434193323Sed 435193323Sed // If the first basic block in the function has live ins that need to be 436193323Sed // copied into vregs, emit the copies into the top of the block before 437193323Sed // emitting the code for the block. 438207618Srdivacky MachineBasicBlock *EntryMBB = MF->begin(); 439207618Srdivacky RegInfo->EmitLiveInCopies(EntryMBB, TRI, TII); 440193323Sed 441208599Srdivacky DenseMap<unsigned, unsigned> LiveInMap; 442208599Srdivacky if (!FuncInfo->ArgDbgValues.empty()) 443208599Srdivacky for (MachineRegisterInfo::livein_iterator LI = RegInfo->livein_begin(), 444208599Srdivacky E = RegInfo->livein_end(); LI != E; ++LI) 445218893Sdim if (LI->second) 446208599Srdivacky LiveInMap.insert(std::make_pair(LI->first, LI->second)); 447208599Srdivacky 448207618Srdivacky // Insert DBG_VALUE instructions for function arguments to the entry block. 449207618Srdivacky for (unsigned i = 0, e = FuncInfo->ArgDbgValues.size(); i != e; ++i) { 450207618Srdivacky MachineInstr *MI = FuncInfo->ArgDbgValues[e-i-1]; 451263509Sdim bool hasFI = MI->getOperand(0).isFI(); 452263509Sdim unsigned Reg = hasFI ? TRI.getFrameRegister(*MF) : MI->getOperand(0).getReg(); 453207618Srdivacky if (TargetRegisterInfo::isPhysicalRegister(Reg)) 454207618Srdivacky EntryMBB->insert(EntryMBB->begin(), MI); 455207618Srdivacky else { 456207618Srdivacky MachineInstr *Def = RegInfo->getVRegDef(Reg); 457263509Sdim if (Def) { 458263509Sdim MachineBasicBlock::iterator InsertPos = Def; 459263509Sdim // FIXME: VR def may not be in entry block. 460263509Sdim Def->getParent()->insert(llvm::next(InsertPos), MI); 461263509Sdim } else 462263509Sdim DEBUG(dbgs() << "Dropping debug info for dead vreg" 463263509Sdim << TargetRegisterInfo::virtReg2Index(Reg) << "\n"); 464207618Srdivacky } 465208599Srdivacky 466208599Srdivacky // If Reg is live-in then update debug info to track its copy in a vreg. 467208599Srdivacky DenseMap<unsigned, unsigned>::iterator LDI = LiveInMap.find(Reg); 468208599Srdivacky if (LDI != LiveInMap.end()) { 469263509Sdim assert(!hasFI && "There's no handling of frame pointer updating here yet " 470263509Sdim "- add if needed"); 471208599Srdivacky MachineInstr *Def = RegInfo->getVRegDef(LDI->second); 472208599Srdivacky MachineBasicBlock::iterator InsertPos = Def; 473218893Sdim const MDNode *Variable = 474208599Srdivacky MI->getOperand(MI->getNumOperands()-1).getMetadata(); 475263509Sdim bool IsIndirect = MI->isIndirectDebugValue(); 476263509Sdim unsigned Offset = IsIndirect ? MI->getOperand(1).getImm() : 0; 477208599Srdivacky // Def is never a terminator here, so it is ok to increment InsertPos. 478218893Sdim BuildMI(*EntryMBB, ++InsertPos, MI->getDebugLoc(), 479263509Sdim TII.get(TargetOpcode::DBG_VALUE), 480263509Sdim IsIndirect, 481263509Sdim LDI->second, Offset, Variable); 482218893Sdim 483218893Sdim // If this vreg is directly copied into an exported register then 484218893Sdim // that COPY instructions also need DBG_VALUE, if it is the only 485218893Sdim // user of LDI->second. 486218893Sdim MachineInstr *CopyUseMI = NULL; 487218893Sdim for (MachineRegisterInfo::use_iterator 488218893Sdim UI = RegInfo->use_begin(LDI->second); 489218893Sdim MachineInstr *UseMI = UI.skipInstruction();) { 490218893Sdim if (UseMI->isDebugValue()) continue; 491218893Sdim if (UseMI->isCopy() && !CopyUseMI && UseMI->getParent() == EntryMBB) { 492218893Sdim CopyUseMI = UseMI; continue; 493218893Sdim } 494218893Sdim // Otherwise this is another use or second copy use. 495218893Sdim CopyUseMI = NULL; break; 496218893Sdim } 497218893Sdim if (CopyUseMI) { 498218893Sdim MachineInstr *NewMI = 499218893Sdim BuildMI(*MF, CopyUseMI->getDebugLoc(), 500263509Sdim TII.get(TargetOpcode::DBG_VALUE), 501263509Sdim IsIndirect, 502263509Sdim CopyUseMI->getOperand(0).getReg(), 503263509Sdim Offset, Variable); 504235633Sdim MachineBasicBlock::iterator Pos = CopyUseMI; 505235633Sdim EntryMBB->insertAfter(Pos, NewMI); 506218893Sdim } 507208599Srdivacky } 508207618Srdivacky } 509193323Sed 510208599Srdivacky // Determine if there are any calls in this machine function. 511208599Srdivacky MachineFrameInfo *MFI = MF->getFrameInfo(); 512252723Sdim for (MachineFunction::const_iterator I = MF->begin(), E = MF->end(); I != E; 513252723Sdim ++I) { 514210299Sed 515263765Sdim if (MFI->hasCalls() && MF->hasInlineAsm()) 516252723Sdim break; 517252723Sdim 518252723Sdim const MachineBasicBlock *MBB = I; 519252723Sdim for (MachineBasicBlock::const_iterator II = MBB->begin(), IE = MBB->end(); 520252723Sdim II != IE; ++II) { 521252723Sdim const MCInstrDesc &MCID = TM.getInstrInfo()->get(II->getOpcode()); 522252723Sdim if ((MCID.isCall() && !MCID.isReturn()) || 523252723Sdim II->isStackAligningInlineAsm()) { 524252723Sdim MFI->setHasCalls(true); 525208599Srdivacky } 526263765Sdim if (II->isInlineAsm()) { 527263765Sdim MF->setHasInlineAsm(true); 528252723Sdim } 529208599Srdivacky } 530208599Srdivacky } 531208599Srdivacky 532208599Srdivacky // Determine if there is a call to setjmp in the machine function. 533235633Sdim MF->setExposesReturnsTwice(Fn.callsFunctionThatReturnsTwice()); 534208599Srdivacky 535210299Sed // Replace forward-declared registers with the registers containing 536210299Sed // the desired value. 537210299Sed MachineRegisterInfo &MRI = MF->getRegInfo(); 538210299Sed for (DenseMap<unsigned, unsigned>::iterator 539210299Sed I = FuncInfo->RegFixups.begin(), E = FuncInfo->RegFixups.end(); 540210299Sed I != E; ++I) { 541210299Sed unsigned From = I->first; 542210299Sed unsigned To = I->second; 543210299Sed // If To is also scheduled to be replaced, find what its ultimate 544210299Sed // replacement is. 545210299Sed for (;;) { 546245431Sdim DenseMap<unsigned, unsigned>::iterator J = FuncInfo->RegFixups.find(To); 547210299Sed if (J == E) break; 548210299Sed To = J->second; 549210299Sed } 550263509Sdim // Make sure the new register has a sufficiently constrained register class. 551263509Sdim if (TargetRegisterInfo::isVirtualRegister(From) && 552263509Sdim TargetRegisterInfo::isVirtualRegister(To)) 553263509Sdim MRI.constrainRegClass(To, MRI.getRegClass(From)); 554210299Sed // Replace it. 555210299Sed MRI.replaceRegWith(From, To); 556210299Sed } 557210299Sed 558245431Sdim // Freeze the set of reserved registers now that MachineFrameInfo has been 559245431Sdim // set up. All the information required by getReservedRegs() should be 560245431Sdim // available now. 561245431Sdim MRI.freezeReservedRegs(*MF); 562245431Sdim 563207618Srdivacky // Release function-specific state. SDB and CurDAG are already cleared 564207618Srdivacky // at this point. 565193323Sed FuncInfo->clear(); 566193323Sed 567193323Sed return true; 568193323Sed} 569193323Sed 570221345Sdimvoid SelectionDAGISel::SelectBasicBlock(BasicBlock::const_iterator Begin, 571221345Sdim BasicBlock::const_iterator End, 572221345Sdim bool &HadTailCall) { 573198090Srdivacky // Lower all of the non-terminator instructions. If a call is emitted 574207618Srdivacky // as a tail call, cease emitting nodes for this block. Terminators 575207618Srdivacky // are handled below. 576207618Srdivacky for (BasicBlock::const_iterator I = Begin; I != End && !SDB->HasTailCall; ++I) 577207618Srdivacky SDB->visit(*I); 578200581Srdivacky 579193323Sed // Make sure the root of the DAG is up-to-date. 580199989Srdivacky CurDAG->setRoot(SDB->getControlRoot()); 581207618Srdivacky HadTailCall = SDB->HasTailCall; 582207618Srdivacky SDB->clear(); 583193323Sed 584193323Sed // Final step, emit the lowered DAG as machine code. 585210299Sed CodeGenAndEmitDAG(); 586193323Sed} 587193323Sed 588193323Sedvoid SelectionDAGISel::ComputeLiveOutVRegInfo() { 589193323Sed SmallPtrSet<SDNode*, 128> VisitedNodes; 590193323Sed SmallVector<SDNode*, 128> Worklist; 591198090Srdivacky 592193323Sed Worklist.push_back(CurDAG->getRoot().getNode()); 593198090Srdivacky 594193323Sed APInt KnownZero; 595193323Sed APInt KnownOne; 596198090Srdivacky 597202375Srdivacky do { 598202375Srdivacky SDNode *N = Worklist.pop_back_val(); 599198090Srdivacky 600193323Sed // If we've already seen this node, ignore it. 601193323Sed if (!VisitedNodes.insert(N)) 602193323Sed continue; 603198090Srdivacky 604193323Sed // Otherwise, add all chain operands to the worklist. 605193323Sed for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) 606193323Sed if (N->getOperand(i).getValueType() == MVT::Other) 607193323Sed Worklist.push_back(N->getOperand(i).getNode()); 608198090Srdivacky 609193323Sed // If this is a CopyToReg with a vreg dest, process it. 610193323Sed if (N->getOpcode() != ISD::CopyToReg) 611193323Sed continue; 612198090Srdivacky 613193323Sed unsigned DestReg = cast<RegisterSDNode>(N->getOperand(1))->getReg(); 614193323Sed if (!TargetRegisterInfo::isVirtualRegister(DestReg)) 615193323Sed continue; 616198090Srdivacky 617193323Sed // Ignore non-scalar or non-integer values. 618193323Sed SDValue Src = N->getOperand(2); 619198090Srdivacky EVT SrcVT = Src.getValueType(); 620193323Sed if (!SrcVT.isInteger() || SrcVT.isVector()) 621193323Sed continue; 622198090Srdivacky 623193323Sed unsigned NumSignBits = CurDAG->ComputeNumSignBits(Src); 624235633Sdim CurDAG->ComputeMaskedBits(Src, KnownZero, KnownOne); 625219077Sdim FuncInfo->AddLiveOutRegInfo(DestReg, NumSignBits, KnownZero, KnownOne); 626202375Srdivacky } while (!Worklist.empty()); 627193323Sed} 628193323Sed 629210299Sedvoid SelectionDAGISel::CodeGenAndEmitDAG() { 630193323Sed std::string GroupName; 631193323Sed if (TimePassesIsEnabled) 632193323Sed GroupName = "Instruction Selection and Scheduling"; 633193323Sed std::string BlockName; 634221345Sdim int BlockNumber = -1; 635226890Sdim (void)BlockNumber; 636221345Sdim#ifdef NDEBUG 637193323Sed if (ViewDAGCombine1 || ViewLegalizeTypesDAGs || ViewLegalizeDAGs || 638193323Sed ViewDAGCombine2 || ViewDAGCombineLT || ViewISelDAGs || ViewSchedDAGs || 639193323Sed ViewSUnitDAGs) 640221345Sdim#endif 641221345Sdim { 642221345Sdim BlockNumber = FuncInfo->MBB->getNumber(); 643245431Sdim BlockName = MF->getName().str() + ":" + 644235633Sdim FuncInfo->MBB->getBasicBlock()->getName().str(); 645221345Sdim } 646221345Sdim DEBUG(dbgs() << "Initial selection DAG: BB#" << BlockNumber 647221345Sdim << " '" << BlockName << "'\n"; CurDAG->dump()); 648193323Sed 649193323Sed if (ViewDAGCombine1) CurDAG->viewGraph("dag-combine1 input for " + BlockName); 650193323Sed 651193323Sed // Run the DAG combiner in pre-legalize mode. 652210299Sed { 653210299Sed NamedRegionTimer T("DAG Combining 1", GroupName, TimePassesIsEnabled); 654235633Sdim CurDAG->Combine(BeforeLegalizeTypes, *AA, OptLevel); 655193323Sed } 656198090Srdivacky 657221345Sdim DEBUG(dbgs() << "Optimized lowered selection DAG: BB#" << BlockNumber 658221345Sdim << " '" << BlockName << "'\n"; CurDAG->dump()); 659198090Srdivacky 660193323Sed // Second step, hack on the DAG until it only uses operations and types that 661193323Sed // the target supports. 662200581Srdivacky if (ViewLegalizeTypesDAGs) CurDAG->viewGraph("legalize-types input for " + 663200581Srdivacky BlockName); 664193323Sed 665200581Srdivacky bool Changed; 666210299Sed { 667210299Sed NamedRegionTimer T("Type Legalization", GroupName, TimePassesIsEnabled); 668200581Srdivacky Changed = CurDAG->LegalizeTypes(); 669200581Srdivacky } 670200581Srdivacky 671221345Sdim DEBUG(dbgs() << "Type-legalized selection DAG: BB#" << BlockNumber 672221345Sdim << " '" << BlockName << "'\n"; CurDAG->dump()); 673200581Srdivacky 674263509Sdim CurDAG->NewNodesMustHaveLegalTypes = true; 675263509Sdim 676200581Srdivacky if (Changed) { 677200581Srdivacky if (ViewDAGCombineLT) 678200581Srdivacky CurDAG->viewGraph("dag-combine-lt input for " + BlockName); 679200581Srdivacky 680200581Srdivacky // Run the DAG combiner in post-type-legalize mode. 681210299Sed { 682210299Sed NamedRegionTimer T("DAG Combining after legalize types", GroupName, 683210299Sed TimePassesIsEnabled); 684235633Sdim CurDAG->Combine(AfterLegalizeTypes, *AA, OptLevel); 685193323Sed } 686193323Sed 687221345Sdim DEBUG(dbgs() << "Optimized type-legalized selection DAG: BB#" << BlockNumber 688221345Sdim << " '" << BlockName << "'\n"; CurDAG->dump()); 689263509Sdim 690200581Srdivacky } 691193323Sed 692210299Sed { 693210299Sed NamedRegionTimer T("Vector Legalization", GroupName, TimePassesIsEnabled); 694200581Srdivacky Changed = CurDAG->LegalizeVectors(); 695200581Srdivacky } 696193323Sed 697200581Srdivacky if (Changed) { 698210299Sed { 699210299Sed NamedRegionTimer T("Type Legalization 2", GroupName, TimePassesIsEnabled); 700201360Srdivacky CurDAG->LegalizeTypes(); 701193323Sed } 702193323Sed 703200581Srdivacky if (ViewDAGCombineLT) 704200581Srdivacky CurDAG->viewGraph("dag-combine-lv input for " + BlockName); 705200581Srdivacky 706200581Srdivacky // Run the DAG combiner in post-type-legalize mode. 707210299Sed { 708210299Sed NamedRegionTimer T("DAG Combining after legalize vectors", GroupName, 709210299Sed TimePassesIsEnabled); 710235633Sdim CurDAG->Combine(AfterLegalizeVectorOps, *AA, OptLevel); 711193323Sed } 712193323Sed 713221345Sdim DEBUG(dbgs() << "Optimized vector-legalized selection DAG: BB#" 714221345Sdim << BlockNumber << " '" << BlockName << "'\n"; CurDAG->dump()); 715193323Sed } 716198090Srdivacky 717193323Sed if (ViewLegalizeDAGs) CurDAG->viewGraph("legalize input for " + BlockName); 718193323Sed 719210299Sed { 720210299Sed NamedRegionTimer T("DAG Legalization", GroupName, TimePassesIsEnabled); 721223017Sdim CurDAG->Legalize(); 722193323Sed } 723198090Srdivacky 724221345Sdim DEBUG(dbgs() << "Legalized selection DAG: BB#" << BlockNumber 725221345Sdim << " '" << BlockName << "'\n"; CurDAG->dump()); 726198090Srdivacky 727193323Sed if (ViewDAGCombine2) CurDAG->viewGraph("dag-combine2 input for " + BlockName); 728193323Sed 729193323Sed // Run the DAG combiner in post-legalize mode. 730210299Sed { 731210299Sed NamedRegionTimer T("DAG Combining 2", GroupName, TimePassesIsEnabled); 732235633Sdim CurDAG->Combine(AfterLegalizeDAG, *AA, OptLevel); 733193323Sed } 734198090Srdivacky 735221345Sdim DEBUG(dbgs() << "Optimized legalized selection DAG: BB#" << BlockNumber 736221345Sdim << " '" << BlockName << "'\n"; CurDAG->dump()); 737193323Sed 738210299Sed if (OptLevel != CodeGenOpt::None) 739193323Sed ComputeLiveOutVRegInfo(); 740193323Sed 741205218Srdivacky if (ViewISelDAGs) CurDAG->viewGraph("isel input for " + BlockName); 742205218Srdivacky 743193323Sed // Third, instruction select all of the operations to machine code, adding the 744193323Sed // code to the MachineBasicBlock. 745210299Sed { 746210299Sed NamedRegionTimer T("Instruction Selection", GroupName, TimePassesIsEnabled); 747204642Srdivacky DoInstructionSelection(); 748193323Sed } 749193323Sed 750221345Sdim DEBUG(dbgs() << "Selected selection DAG: BB#" << BlockNumber 751221345Sdim << " '" << BlockName << "'\n"; CurDAG->dump()); 752193323Sed 753193323Sed if (ViewSchedDAGs) CurDAG->viewGraph("scheduler input for " + BlockName); 754193323Sed 755193323Sed // Schedule machine code. 756193323Sed ScheduleDAGSDNodes *Scheduler = CreateScheduler(); 757210299Sed { 758210299Sed NamedRegionTimer T("Instruction Scheduling", GroupName, 759210299Sed TimePassesIsEnabled); 760235633Sdim Scheduler->Run(CurDAG, FuncInfo->MBB); 761193323Sed } 762193323Sed 763193323Sed if (ViewSUnitDAGs) Scheduler->viewGraph(); 764193323Sed 765198090Srdivacky // Emit machine code to BB. This can change 'BB' to the last block being 766193323Sed // inserted into. 767218893Sdim MachineBasicBlock *FirstMBB = FuncInfo->MBB, *LastMBB; 768210299Sed { 769210299Sed NamedRegionTimer T("Instruction Creation", GroupName, TimePassesIsEnabled); 770210299Sed 771235633Sdim // FuncInfo->InsertPt is passed by reference and set to the end of the 772235633Sdim // scheduled instructions. 773235633Sdim LastMBB = FuncInfo->MBB = Scheduler->EmitSchedule(FuncInfo->InsertPt); 774193323Sed } 775193323Sed 776218893Sdim // If the block was split, make sure we update any references that are used to 777218893Sdim // update PHI nodes later on. 778218893Sdim if (FirstMBB != LastMBB) 779218893Sdim SDB->UpdateSplitBlock(FirstMBB, LastMBB); 780218893Sdim 781193323Sed // Free the scheduler state. 782210299Sed { 783210299Sed NamedRegionTimer T("Instruction Scheduling Cleanup", GroupName, 784210299Sed TimePassesIsEnabled); 785193323Sed delete Scheduler; 786193323Sed } 787193323Sed 788207618Srdivacky // Free the SelectionDAG state, now that we're finished with it. 789207618Srdivacky CurDAG->clear(); 790198090Srdivacky} 791193323Sed 792245431Sdimnamespace { 793245431Sdim/// ISelUpdater - helper class to handle updates of the instruction selection 794245431Sdim/// graph. 795245431Sdimclass ISelUpdater : public SelectionDAG::DAGUpdateListener { 796245431Sdim SelectionDAG::allnodes_iterator &ISelPosition; 797245431Sdimpublic: 798245431Sdim ISelUpdater(SelectionDAG &DAG, SelectionDAG::allnodes_iterator &isp) 799245431Sdim : SelectionDAG::DAGUpdateListener(DAG), ISelPosition(isp) {} 800245431Sdim 801245431Sdim /// NodeDeleted - Handle nodes deleted from the graph. If the node being 802245431Sdim /// deleted is the current ISelPosition node, update ISelPosition. 803245431Sdim /// 804245431Sdim virtual void NodeDeleted(SDNode *N, SDNode *E) { 805245431Sdim if (ISelPosition == SelectionDAG::allnodes_iterator(N)) 806245431Sdim ++ISelPosition; 807245431Sdim } 808245431Sdim}; 809245431Sdim} // end anonymous namespace 810245431Sdim 811204642Srdivackyvoid SelectionDAGISel::DoInstructionSelection() { 812252723Sdim DEBUG(dbgs() << "===== Instruction selection begins: BB#" 813221345Sdim << FuncInfo->MBB->getNumber() 814221345Sdim << " '" << FuncInfo->MBB->getName() << "'\n"); 815204642Srdivacky 816204642Srdivacky PreprocessISelDAG(); 817218893Sdim 818204642Srdivacky // Select target instructions for the DAG. 819204642Srdivacky { 820204642Srdivacky // Number all nodes with a topological order and set DAGSize. 821204642Srdivacky DAGSize = CurDAG->AssignTopologicalOrder(); 822218893Sdim 823204642Srdivacky // Create a dummy node (which is not added to allnodes), that adds 824204642Srdivacky // a reference to the root node, preventing it from being deleted, 825204642Srdivacky // and tracking any changes of the root. 826204642Srdivacky HandleSDNode Dummy(CurDAG->getRoot()); 827245431Sdim SelectionDAG::allnodes_iterator ISelPosition (CurDAG->getRoot().getNode()); 828204642Srdivacky ++ISelPosition; 829218893Sdim 830245431Sdim // Make sure that ISelPosition gets properly updated when nodes are deleted 831245431Sdim // in calls made from this function. 832245431Sdim ISelUpdater ISU(*CurDAG, ISelPosition); 833245431Sdim 834204642Srdivacky // The AllNodes list is now topological-sorted. Visit the 835204642Srdivacky // nodes by starting at the end of the list (the root of the 836204642Srdivacky // graph) and preceding back toward the beginning (the entry 837204642Srdivacky // node). 838204642Srdivacky while (ISelPosition != CurDAG->allnodes_begin()) { 839204642Srdivacky SDNode *Node = --ISelPosition; 840204642Srdivacky // Skip dead nodes. DAGCombiner is expected to eliminate all dead nodes, 841204642Srdivacky // but there are currently some corner cases that it misses. Also, this 842204642Srdivacky // makes it theoretically possible to disable the DAGCombiner. 843204642Srdivacky if (Node->use_empty()) 844204642Srdivacky continue; 845218893Sdim 846204642Srdivacky SDNode *ResNode = Select(Node); 847218893Sdim 848204642Srdivacky // FIXME: This is pretty gross. 'Select' should be changed to not return 849204642Srdivacky // anything at all and this code should be nuked with a tactical strike. 850218893Sdim 851204642Srdivacky // If node should not be replaced, continue with the next one. 852204642Srdivacky if (ResNode == Node || Node->getOpcode() == ISD::DELETED_NODE) 853204642Srdivacky continue; 854204642Srdivacky // Replace node. 855252723Sdim if (ResNode) { 856204642Srdivacky ReplaceUses(Node, ResNode); 857252723Sdim } 858218893Sdim 859204642Srdivacky // If after the replacement this node is not used any more, 860204642Srdivacky // remove this dead node. 861245431Sdim if (Node->use_empty()) // Don't delete EntryToken, etc. 862245431Sdim CurDAG->RemoveDeadNode(Node); 863204642Srdivacky } 864218893Sdim 865204642Srdivacky CurDAG->setRoot(Dummy.getValue()); 866218893Sdim } 867208599Srdivacky 868252723Sdim DEBUG(dbgs() << "===== Instruction selection ends:\n"); 869204642Srdivacky 870204642Srdivacky PostprocessISelDAG(); 871204642Srdivacky} 872204642Srdivacky 873207618Srdivacky/// PrepareEHLandingPad - Emit an EH_LABEL, set up live-in registers, and 874207618Srdivacky/// do other setup for EH landing-pad blocks. 875210299Sedvoid SelectionDAGISel::PrepareEHLandingPad() { 876226890Sdim MachineBasicBlock *MBB = FuncInfo->MBB; 877226890Sdim 878207618Srdivacky // Add a label to mark the beginning of the landing pad. Deletion of the 879207618Srdivacky // landing pad can thus be detected via the MachineModuleInfo. 880226890Sdim MCSymbol *Label = MF->getMMI().addLandingPad(MBB); 881204642Srdivacky 882226890Sdim // Assign the call site to the landing pad's begin label. 883226890Sdim MF->getMMI().setCallSiteLandingPad(Label, SDB->LPadToCallSiteMap[MBB]); 884235633Sdim 885224145Sdim const MCInstrDesc &II = TM.getInstrInfo()->get(TargetOpcode::EH_LABEL); 886226890Sdim BuildMI(*MBB, FuncInfo->InsertPt, SDB->getCurDebugLoc(), II) 887210299Sed .addSym(Label); 888207618Srdivacky 889207618Srdivacky // Mark exception register as live in. 890263509Sdim const TargetLowering *TLI = getTargetLowering(); 891263509Sdim const TargetRegisterClass *PtrRC = TLI->getRegClassFor(TLI->getPointerTy()); 892263509Sdim if (unsigned Reg = TLI->getExceptionPointerRegister()) 893252993Sdim FuncInfo->ExceptionPointerVirtReg = MBB->addLiveIn(Reg, PtrRC); 894207618Srdivacky 895207618Srdivacky // Mark exception selector register as live in. 896263509Sdim if (unsigned Reg = TLI->getExceptionSelectorRegister()) 897252993Sdim FuncInfo->ExceptionSelectorVirtReg = MBB->addLiveIn(Reg, PtrRC); 898207618Srdivacky} 899207618Srdivacky 900221345Sdim/// isFoldedOrDeadInstruction - Return true if the specified instruction is 901221345Sdim/// side-effect free and is either dead or folded into a generated instruction. 902221345Sdim/// Return false if it needs to be emitted. 903221345Sdimstatic bool isFoldedOrDeadInstruction(const Instruction *I, 904221345Sdim FunctionLoweringInfo *FuncInfo) { 905221345Sdim return !I->mayWriteToMemory() && // Side-effecting instructions aren't folded. 906221345Sdim !isa<TerminatorInst>(I) && // Terminators aren't folded. 907221345Sdim !isa<DbgInfoIntrinsic>(I) && // Debug instructions aren't folded. 908226890Sdim !isa<LandingPadInst>(I) && // Landingpad instructions aren't folded. 909221345Sdim !FuncInfo->isExportedInst(I); // Exported instrs must be computed. 910221345Sdim} 911221345Sdim 912235633Sdim#ifndef NDEBUG 913235633Sdim// Collect per Instruction statistics for fast-isel misses. Only those 914235633Sdim// instructions that cause the bail are accounted for. It does not account for 915235633Sdim// instructions higher in the block. Thus, summing the per instructions stats 916235633Sdim// will not add up to what is reported by NumFastIselFailures. 917235633Sdimstatic void collectFailStats(const Instruction *I) { 918235633Sdim switch (I->getOpcode()) { 919235633Sdim default: assert (0 && "<Invalid operator> "); 920235633Sdim 921235633Sdim // Terminators 922235633Sdim case Instruction::Ret: NumFastIselFailRet++; return; 923235633Sdim case Instruction::Br: NumFastIselFailBr++; return; 924235633Sdim case Instruction::Switch: NumFastIselFailSwitch++; return; 925235633Sdim case Instruction::IndirectBr: NumFastIselFailIndirectBr++; return; 926235633Sdim case Instruction::Invoke: NumFastIselFailInvoke++; return; 927235633Sdim case Instruction::Resume: NumFastIselFailResume++; return; 928235633Sdim case Instruction::Unreachable: NumFastIselFailUnreachable++; return; 929235633Sdim 930235633Sdim // Standard binary operators... 931235633Sdim case Instruction::Add: NumFastIselFailAdd++; return; 932235633Sdim case Instruction::FAdd: NumFastIselFailFAdd++; return; 933235633Sdim case Instruction::Sub: NumFastIselFailSub++; return; 934235633Sdim case Instruction::FSub: NumFastIselFailFSub++; return; 935235633Sdim case Instruction::Mul: NumFastIselFailMul++; return; 936235633Sdim case Instruction::FMul: NumFastIselFailFMul++; return; 937235633Sdim case Instruction::UDiv: NumFastIselFailUDiv++; return; 938235633Sdim case Instruction::SDiv: NumFastIselFailSDiv++; return; 939235633Sdim case Instruction::FDiv: NumFastIselFailFDiv++; return; 940235633Sdim case Instruction::URem: NumFastIselFailURem++; return; 941235633Sdim case Instruction::SRem: NumFastIselFailSRem++; return; 942235633Sdim case Instruction::FRem: NumFastIselFailFRem++; return; 943235633Sdim 944235633Sdim // Logical operators... 945235633Sdim case Instruction::And: NumFastIselFailAnd++; return; 946235633Sdim case Instruction::Or: NumFastIselFailOr++; return; 947235633Sdim case Instruction::Xor: NumFastIselFailXor++; return; 948235633Sdim 949235633Sdim // Memory instructions... 950235633Sdim case Instruction::Alloca: NumFastIselFailAlloca++; return; 951235633Sdim case Instruction::Load: NumFastIselFailLoad++; return; 952235633Sdim case Instruction::Store: NumFastIselFailStore++; return; 953235633Sdim case Instruction::AtomicCmpXchg: NumFastIselFailAtomicCmpXchg++; return; 954235633Sdim case Instruction::AtomicRMW: NumFastIselFailAtomicRMW++; return; 955235633Sdim case Instruction::Fence: NumFastIselFailFence++; return; 956235633Sdim case Instruction::GetElementPtr: NumFastIselFailGetElementPtr++; return; 957235633Sdim 958235633Sdim // Convert instructions... 959235633Sdim case Instruction::Trunc: NumFastIselFailTrunc++; return; 960235633Sdim case Instruction::ZExt: NumFastIselFailZExt++; return; 961235633Sdim case Instruction::SExt: NumFastIselFailSExt++; return; 962235633Sdim case Instruction::FPTrunc: NumFastIselFailFPTrunc++; return; 963235633Sdim case Instruction::FPExt: NumFastIselFailFPExt++; return; 964235633Sdim case Instruction::FPToUI: NumFastIselFailFPToUI++; return; 965235633Sdim case Instruction::FPToSI: NumFastIselFailFPToSI++; return; 966235633Sdim case Instruction::UIToFP: NumFastIselFailUIToFP++; return; 967235633Sdim case Instruction::SIToFP: NumFastIselFailSIToFP++; return; 968235633Sdim case Instruction::IntToPtr: NumFastIselFailIntToPtr++; return; 969235633Sdim case Instruction::PtrToInt: NumFastIselFailPtrToInt++; return; 970235633Sdim case Instruction::BitCast: NumFastIselFailBitCast++; return; 971235633Sdim 972235633Sdim // Other instructions... 973235633Sdim case Instruction::ICmp: NumFastIselFailICmp++; return; 974235633Sdim case Instruction::FCmp: NumFastIselFailFCmp++; return; 975235633Sdim case Instruction::PHI: NumFastIselFailPHI++; return; 976235633Sdim case Instruction::Select: NumFastIselFailSelect++; return; 977235633Sdim case Instruction::Call: NumFastIselFailCall++; return; 978235633Sdim case Instruction::Shl: NumFastIselFailShl++; return; 979235633Sdim case Instruction::LShr: NumFastIselFailLShr++; return; 980235633Sdim case Instruction::AShr: NumFastIselFailAShr++; return; 981235633Sdim case Instruction::VAArg: NumFastIselFailVAArg++; return; 982235633Sdim case Instruction::ExtractElement: NumFastIselFailExtractElement++; return; 983235633Sdim case Instruction::InsertElement: NumFastIselFailInsertElement++; return; 984235633Sdim case Instruction::ShuffleVector: NumFastIselFailShuffleVector++; return; 985235633Sdim case Instruction::ExtractValue: NumFastIselFailExtractValue++; return; 986235633Sdim case Instruction::InsertValue: NumFastIselFailInsertValue++; return; 987235633Sdim case Instruction::LandingPad: NumFastIselFailLandingPad++; return; 988235633Sdim } 989235633Sdim} 990235633Sdim#endif 991235633Sdim 992207618Srdivackyvoid SelectionDAGISel::SelectAllBasicBlocks(const Function &Fn) { 993193323Sed // Initialize the Fast-ISel state, if needed. 994193323Sed FastISel *FastIS = 0; 995235633Sdim if (TM.Options.EnableFastISel) 996263509Sdim FastIS = getTargetLowering()->createFastISel(*FuncInfo, LibInfo); 997193323Sed 998193323Sed // Iterate over all basic blocks in the function. 999219077Sdim ReversePostOrderTraversal<const Function*> RPOT(&Fn); 1000219077Sdim for (ReversePostOrderTraversal<const Function*>::rpo_iterator 1001219077Sdim I = RPOT.begin(), E = RPOT.end(); I != E; ++I) { 1002219077Sdim const BasicBlock *LLVMBB = *I; 1003219077Sdim 1004219077Sdim if (OptLevel != CodeGenOpt::None) { 1005219077Sdim bool AllPredsVisited = true; 1006219077Sdim for (const_pred_iterator PI = pred_begin(LLVMBB), PE = pred_end(LLVMBB); 1007219077Sdim PI != PE; ++PI) { 1008219077Sdim if (!FuncInfo->VisitedBBs.count(*PI)) { 1009219077Sdim AllPredsVisited = false; 1010219077Sdim break; 1011219077Sdim } 1012219077Sdim } 1013219077Sdim 1014219077Sdim if (AllPredsVisited) { 1015221345Sdim for (BasicBlock::const_iterator I = LLVMBB->begin(); 1016252723Sdim const PHINode *PN = dyn_cast<PHINode>(I); ++I) 1017252723Sdim FuncInfo->ComputePHILiveOutRegInfo(PN); 1018219077Sdim } else { 1019221345Sdim for (BasicBlock::const_iterator I = LLVMBB->begin(); 1020252723Sdim const PHINode *PN = dyn_cast<PHINode>(I); ++I) 1021252723Sdim FuncInfo->InvalidatePHILiveOutRegInfo(PN); 1022219077Sdim } 1023219077Sdim 1024219077Sdim FuncInfo->VisitedBBs.insert(LLVMBB); 1025219077Sdim } 1026219077Sdim 1027207618Srdivacky BasicBlock::const_iterator const Begin = LLVMBB->getFirstNonPHI(); 1028207618Srdivacky BasicBlock::const_iterator const End = LLVMBB->end(); 1029210299Sed BasicBlock::const_iterator BI = End; 1030193323Sed 1031252723Sdim FuncInfo->MBB = FuncInfo->MBBMap[LLVMBB]; 1032210299Sed FuncInfo->InsertPt = FuncInfo->MBB->getFirstNonPHI(); 1033210299Sed 1034210299Sed // Setup an EH landing-pad block. 1035252993Sdim FuncInfo->ExceptionPointerVirtReg = 0; 1036252993Sdim FuncInfo->ExceptionSelectorVirtReg = 0; 1037210299Sed if (FuncInfo->MBB->isLandingPad()) 1038210299Sed PrepareEHLandingPad(); 1039218893Sdim 1040193323Sed // Before doing SelectionDAG ISel, see if FastISel has been requested. 1041207618Srdivacky if (FastIS) { 1042210299Sed FastIS->startNewBlock(); 1043210299Sed 1044193323Sed // Emit code for any incoming arguments. This must happen before 1045193323Sed // beginning FastISel on the entry block. 1046193323Sed if (LLVMBB == &Fn.getEntryBlock()) { 1047252723Sdim ++NumEntryBlocks; 1048210299Sed 1049252723Sdim // Lower any arguments needed in this block if this is the entry block. 1050252723Sdim if (!FastIS->LowerArguments()) { 1051252723Sdim // Fast isel failed to lower these arguments 1052252723Sdim ++NumFastIselFailLowerArguments; 1053252723Sdim if (EnableFastISelAbortArgs) 1054252723Sdim llvm_unreachable("FastISel didn't lower all arguments"); 1055252723Sdim 1056252723Sdim // Use SelectionDAG argument lowering 1057252723Sdim LowerArguments(Fn); 1058252723Sdim CurDAG->setRoot(SDB->getControlRoot()); 1059252723Sdim SDB->clear(); 1060252723Sdim CodeGenAndEmitDAG(); 1061252723Sdim } 1062252723Sdim 1063210299Sed // If we inserted any instructions at the beginning, make a note of 1064210299Sed // where they are, so we can be sure to emit subsequent instructions 1065210299Sed // after them. 1066210299Sed if (FuncInfo->InsertPt != FuncInfo->MBB->begin()) 1067210299Sed FastIS->setLastLocalValue(llvm::prior(FuncInfo->InsertPt)); 1068210299Sed else 1069210299Sed FastIS->setLastLocalValue(0); 1070193323Sed } 1071210299Sed 1072235633Sdim unsigned NumFastIselRemaining = std::distance(Begin, End); 1073193323Sed // Do FastISel on as many instructions as possible. 1074210299Sed for (; BI != Begin; --BI) { 1075210299Sed const Instruction *Inst = llvm::prior(BI); 1076210299Sed 1077210299Sed // If we no longer require this instruction, skip it. 1078235633Sdim if (isFoldedOrDeadInstruction(Inst, FuncInfo)) { 1079235633Sdim --NumFastIselRemaining; 1080210299Sed continue; 1081235633Sdim } 1082210299Sed 1083210299Sed // Bottom-up: reset the insert pos at the top, after any local-value 1084210299Sed // instructions. 1085210299Sed FastIS->recomputeInsertPt(); 1086210299Sed 1087202375Srdivacky // Try to select the instruction with FastISel. 1088218893Sdim if (FastIS->SelectInstruction(Inst)) { 1089235633Sdim --NumFastIselRemaining; 1090223017Sdim ++NumFastIselSuccess; 1091221345Sdim // If fast isel succeeded, skip over all the folded instructions, and 1092221345Sdim // then see if there is a load right before the selected instructions. 1093221345Sdim // Try to fold the load if so. 1094221345Sdim const Instruction *BeforeInst = Inst; 1095221345Sdim while (BeforeInst != Begin) { 1096221345Sdim BeforeInst = llvm::prior(BasicBlock::const_iterator(BeforeInst)); 1097221345Sdim if (!isFoldedOrDeadInstruction(BeforeInst, FuncInfo)) 1098221345Sdim break; 1099221345Sdim } 1100221345Sdim if (BeforeInst != Inst && isa<LoadInst>(BeforeInst) && 1101221345Sdim BeforeInst->hasOneUse() && 1102252723Sdim FastIS->tryToFoldLoad(cast<LoadInst>(BeforeInst), Inst)) { 1103221345Sdim // If we succeeded, don't re-select the load. 1104221345Sdim BI = llvm::next(BasicBlock::const_iterator(BeforeInst)); 1105235633Sdim --NumFastIselRemaining; 1106235633Sdim ++NumFastIselSuccess; 1107235633Sdim } 1108193323Sed continue; 1109218893Sdim } 1110193323Sed 1111235633Sdim#ifndef NDEBUG 1112235633Sdim if (EnableFastISelVerbose2) 1113235633Sdim collectFailStats(Inst); 1114235633Sdim#endif 1115235633Sdim 1116193323Sed // Then handle certain instructions as single-LLVM-Instruction blocks. 1117210299Sed if (isa<CallInst>(Inst)) { 1118235633Sdim 1119193323Sed if (EnableFastISelVerbose || EnableFastISelAbort) { 1120202375Srdivacky dbgs() << "FastISel missed call: "; 1121210299Sed Inst->dump(); 1122193323Sed } 1123193323Sed 1124210299Sed if (!Inst->getType()->isVoidTy() && !Inst->use_empty()) { 1125210299Sed unsigned &R = FuncInfo->ValueMap[Inst]; 1126193323Sed if (!R) 1127210299Sed R = FuncInfo->CreateRegs(Inst->getType()); 1128193323Sed } 1129193323Sed 1130199989Srdivacky bool HadTailCall = false; 1131252723Sdim MachineBasicBlock::iterator SavedInsertPt = FuncInfo->InsertPt; 1132210299Sed SelectBasicBlock(Inst, BI, HadTailCall); 1133199989Srdivacky 1134199989Srdivacky // If the call was emitted as a tail call, we're done with the block. 1135252723Sdim // We also need to delete any previously emitted instructions. 1136199989Srdivacky if (HadTailCall) { 1137252723Sdim FastIS->removeDeadCode(SavedInsertPt, FuncInfo->MBB->end()); 1138210299Sed --BI; 1139199989Srdivacky break; 1140199989Srdivacky } 1141199989Srdivacky 1142252723Sdim // Recompute NumFastIselRemaining as Selection DAG instruction 1143252723Sdim // selection may have handled the call, input args, etc. 1144252723Sdim unsigned RemainingNow = std::distance(Begin, BI); 1145252723Sdim NumFastIselFailures += NumFastIselRemaining - RemainingNow; 1146235633Sdim NumFastIselRemaining = RemainingNow; 1147193323Sed continue; 1148193323Sed } 1149193323Sed 1150223017Sdim if (isa<TerminatorInst>(Inst) && !isa<BranchInst>(Inst)) { 1151223017Sdim // Don't abort, and use a different message for terminator misses. 1152235633Sdim NumFastIselFailures += NumFastIselRemaining; 1153193323Sed if (EnableFastISelVerbose || EnableFastISelAbort) { 1154223017Sdim dbgs() << "FastISel missed terminator: "; 1155223017Sdim Inst->dump(); 1156223017Sdim } 1157223017Sdim } else { 1158235633Sdim NumFastIselFailures += NumFastIselRemaining; 1159223017Sdim if (EnableFastISelVerbose || EnableFastISelAbort) { 1160202375Srdivacky dbgs() << "FastISel miss: "; 1161210299Sed Inst->dump(); 1162193323Sed } 1163193323Sed if (EnableFastISelAbort) 1164193323Sed // The "fast" selector couldn't handle something and bailed. 1165193323Sed // For the purpose of debugging, just abort. 1166198090Srdivacky llvm_unreachable("FastISel didn't select the entire block"); 1167193323Sed } 1168193323Sed break; 1169193323Sed } 1170210299Sed 1171210299Sed FastIS->recomputeInsertPt(); 1172252723Sdim } else { 1173252723Sdim // Lower any arguments needed in this block if this is the entry block. 1174252723Sdim if (LLVMBB == &Fn.getEntryBlock()) { 1175252723Sdim ++NumEntryBlocks; 1176252723Sdim LowerArguments(Fn); 1177252723Sdim } 1178193323Sed } 1179193323Sed 1180218893Sdim if (Begin != BI) 1181218893Sdim ++NumDAGBlocks; 1182218893Sdim else 1183218893Sdim ++NumFastIselBlocks; 1184218893Sdim 1185221345Sdim if (Begin != BI) { 1186221345Sdim // Run SelectionDAG instruction selection on the remainder of the block 1187221345Sdim // not handled by FastISel. If FastISel is not run, this is the entire 1188221345Sdim // block. 1189221345Sdim bool HadTailCall; 1190221345Sdim SelectBasicBlock(Begin, BI, HadTailCall); 1191221345Sdim } 1192193323Sed 1193210299Sed FinishBasicBlock(); 1194207618Srdivacky FuncInfo->PHINodesToUpdate.clear(); 1195193323Sed } 1196193323Sed 1197193323Sed delete FastIS; 1198223017Sdim SDB->clearDanglingDebugInfo(); 1199263509Sdim SDB->SPDescriptor.resetPerFunctionState(); 1200193323Sed} 1201193323Sed 1202263509Sdim/// Given that the input MI is before a partial terminator sequence TSeq, return 1203263509Sdim/// true if M + TSeq also a partial terminator sequence. 1204263509Sdim/// 1205263509Sdim/// A Terminator sequence is a sequence of MachineInstrs which at this point in 1206263509Sdim/// lowering copy vregs into physical registers, which are then passed into 1207263509Sdim/// terminator instructors so we can satisfy ABI constraints. A partial 1208263509Sdim/// terminator sequence is an improper subset of a terminator sequence (i.e. it 1209263509Sdim/// may be the whole terminator sequence). 1210263509Sdimstatic bool MIIsInTerminatorSequence(const MachineInstr *MI) { 1211263509Sdim // If we do not have a copy or an implicit def, we return true if and only if 1212263509Sdim // MI is a debug value. 1213263509Sdim if (!MI->isCopy() && !MI->isImplicitDef()) 1214263509Sdim // Sometimes DBG_VALUE MI sneak in between the copies from the vregs to the 1215263509Sdim // physical registers if there is debug info associated with the terminator 1216263509Sdim // of our mbb. We want to include said debug info in our terminator 1217263509Sdim // sequence, so we return true in that case. 1218263509Sdim return MI->isDebugValue(); 1219263509Sdim 1220263509Sdim // We have left the terminator sequence if we are not doing one of the 1221263509Sdim // following: 1222263509Sdim // 1223263509Sdim // 1. Copying a vreg into a physical register. 1224263509Sdim // 2. Copying a vreg into a vreg. 1225263509Sdim // 3. Defining a register via an implicit def. 1226263509Sdim 1227263509Sdim // OPI should always be a register definition... 1228263509Sdim MachineInstr::const_mop_iterator OPI = MI->operands_begin(); 1229263509Sdim if (!OPI->isReg() || !OPI->isDef()) 1230263509Sdim return false; 1231263509Sdim 1232263509Sdim // Defining any register via an implicit def is always ok. 1233263509Sdim if (MI->isImplicitDef()) 1234263509Sdim return true; 1235263509Sdim 1236263509Sdim // Grab the copy source... 1237263509Sdim MachineInstr::const_mop_iterator OPI2 = OPI; 1238263509Sdim ++OPI2; 1239263509Sdim assert(OPI2 != MI->operands_end() 1240263509Sdim && "Should have a copy implying we should have 2 arguments."); 1241263509Sdim 1242263509Sdim // Make sure that the copy dest is not a vreg when the copy source is a 1243263509Sdim // physical register. 1244263509Sdim if (!OPI2->isReg() || 1245263509Sdim (!TargetRegisterInfo::isPhysicalRegister(OPI->getReg()) && 1246263509Sdim TargetRegisterInfo::isPhysicalRegister(OPI2->getReg()))) 1247263509Sdim return false; 1248263509Sdim 1249263509Sdim return true; 1250263509Sdim} 1251263509Sdim 1252263509Sdim/// Find the split point at which to splice the end of BB into its success stack 1253263509Sdim/// protector check machine basic block. 1254263509Sdim/// 1255263509Sdim/// On many platforms, due to ABI constraints, terminators, even before register 1256263509Sdim/// allocation, use physical registers. This creates an issue for us since 1257263509Sdim/// physical registers at this point can not travel across basic 1258263509Sdim/// blocks. Luckily, selectiondag always moves physical registers into vregs 1259263509Sdim/// when they enter functions and moves them through a sequence of copies back 1260263509Sdim/// into the physical registers right before the terminator creating a 1261263509Sdim/// ``Terminator Sequence''. This function is searching for the beginning of the 1262263509Sdim/// terminator sequence so that we can ensure that we splice off not just the 1263263509Sdim/// terminator, but additionally the copies that move the vregs into the 1264263509Sdim/// physical registers. 1265263509Sdimstatic MachineBasicBlock::iterator 1266263509SdimFindSplitPointForStackProtector(MachineBasicBlock *BB, DebugLoc DL) { 1267263509Sdim MachineBasicBlock::iterator SplitPoint = BB->getFirstTerminator(); 1268263509Sdim // 1269263509Sdim if (SplitPoint == BB->begin()) 1270263509Sdim return SplitPoint; 1271263509Sdim 1272263509Sdim MachineBasicBlock::iterator Start = BB->begin(); 1273263509Sdim MachineBasicBlock::iterator Previous = SplitPoint; 1274263509Sdim --Previous; 1275263509Sdim 1276263509Sdim while (MIIsInTerminatorSequence(Previous)) { 1277263509Sdim SplitPoint = Previous; 1278263509Sdim if (Previous == Start) 1279263509Sdim break; 1280263509Sdim --Previous; 1281263509Sdim } 1282263509Sdim 1283263509Sdim return SplitPoint; 1284263509Sdim} 1285263509Sdim 1286193323Sedvoid 1287210299SedSelectionDAGISel::FinishBasicBlock() { 1288193323Sed 1289202375Srdivacky DEBUG(dbgs() << "Total amount of phi nodes to update: " 1290210299Sed << FuncInfo->PHINodesToUpdate.size() << "\n"; 1291210299Sed for (unsigned i = 0, e = FuncInfo->PHINodesToUpdate.size(); i != e; ++i) 1292202375Srdivacky dbgs() << "Node " << i << " : (" 1293207618Srdivacky << FuncInfo->PHINodesToUpdate[i].first 1294207618Srdivacky << ", " << FuncInfo->PHINodesToUpdate[i].second << ")\n"); 1295198090Srdivacky 1296263509Sdim const bool MustUpdatePHINodes = SDB->SwitchCases.empty() && 1297263509Sdim SDB->JTCases.empty() && 1298263509Sdim SDB->BitTestCases.empty(); 1299263509Sdim 1300193323Sed // Next, now that we know what the last MBB the LLVM BB expanded is, update 1301193323Sed // PHI nodes in successors. 1302263509Sdim if (MustUpdatePHINodes) { 1303207618Srdivacky for (unsigned i = 0, e = FuncInfo->PHINodesToUpdate.size(); i != e; ++i) { 1304252723Sdim MachineInstrBuilder PHI(*MF, FuncInfo->PHINodesToUpdate[i].first); 1305203954Srdivacky assert(PHI->isPHI() && 1306193323Sed "This is not a machine PHI node that we are updating!"); 1307210299Sed if (!FuncInfo->MBB->isSuccessor(PHI->getParent())) 1308204792Srdivacky continue; 1309252723Sdim PHI.addReg(FuncInfo->PHINodesToUpdate[i].second).addMBB(FuncInfo->MBB); 1310193323Sed } 1311193323Sed } 1312193323Sed 1313263509Sdim // Handle stack protector. 1314263509Sdim if (SDB->SPDescriptor.shouldEmitStackProtector()) { 1315263509Sdim MachineBasicBlock *ParentMBB = SDB->SPDescriptor.getParentMBB(); 1316263509Sdim MachineBasicBlock *SuccessMBB = SDB->SPDescriptor.getSuccessMBB(); 1317263509Sdim 1318263509Sdim // Find the split point to split the parent mbb. At the same time copy all 1319263509Sdim // physical registers used in the tail of parent mbb into virtual registers 1320263509Sdim // before the split point and back into physical registers after the split 1321263509Sdim // point. This prevents us needing to deal with Live-ins and many other 1322263509Sdim // register allocation issues caused by us splitting the parent mbb. The 1323263509Sdim // register allocator will clean up said virtual copies later on. 1324263509Sdim MachineBasicBlock::iterator SplitPoint = 1325263509Sdim FindSplitPointForStackProtector(ParentMBB, SDB->getCurDebugLoc()); 1326263509Sdim 1327263509Sdim // Splice the terminator of ParentMBB into SuccessMBB. 1328263509Sdim SuccessMBB->splice(SuccessMBB->end(), ParentMBB, 1329263509Sdim SplitPoint, 1330263509Sdim ParentMBB->end()); 1331263509Sdim 1332263509Sdim // Add compare/jump on neq/jump to the parent BB. 1333263509Sdim FuncInfo->MBB = ParentMBB; 1334263509Sdim FuncInfo->InsertPt = ParentMBB->end(); 1335263509Sdim SDB->visitSPDescriptorParent(SDB->SPDescriptor, ParentMBB); 1336263509Sdim CurDAG->setRoot(SDB->getRoot()); 1337263509Sdim SDB->clear(); 1338263509Sdim CodeGenAndEmitDAG(); 1339263509Sdim 1340263509Sdim // CodeGen Failure MBB if we have not codegened it yet. 1341263509Sdim MachineBasicBlock *FailureMBB = SDB->SPDescriptor.getFailureMBB(); 1342263509Sdim if (!FailureMBB->size()) { 1343263509Sdim FuncInfo->MBB = FailureMBB; 1344263509Sdim FuncInfo->InsertPt = FailureMBB->end(); 1345263509Sdim SDB->visitSPDescriptorFailure(SDB->SPDescriptor); 1346263509Sdim CurDAG->setRoot(SDB->getRoot()); 1347263509Sdim SDB->clear(); 1348263509Sdim CodeGenAndEmitDAG(); 1349263509Sdim } 1350263509Sdim 1351263509Sdim // Clear the Per-BB State. 1352263509Sdim SDB->SPDescriptor.resetPerBBState(); 1353263509Sdim } 1354263509Sdim 1355263509Sdim // If we updated PHI Nodes, return early. 1356263509Sdim if (MustUpdatePHINodes) 1357263509Sdim return; 1358263509Sdim 1359199989Srdivacky for (unsigned i = 0, e = SDB->BitTestCases.size(); i != e; ++i) { 1360193323Sed // Lower header first, if it wasn't already lowered 1361199989Srdivacky if (!SDB->BitTestCases[i].Emitted) { 1362193323Sed // Set the current basic block to the mbb we wish to insert the code into 1363210299Sed FuncInfo->MBB = SDB->BitTestCases[i].Parent; 1364210299Sed FuncInfo->InsertPt = FuncInfo->MBB->end(); 1365193323Sed // Emit the code 1366210299Sed SDB->visitBitTestHeader(SDB->BitTestCases[i], FuncInfo->MBB); 1367199989Srdivacky CurDAG->setRoot(SDB->getRoot()); 1368199989Srdivacky SDB->clear(); 1369210299Sed CodeGenAndEmitDAG(); 1370198090Srdivacky } 1371193323Sed 1372245431Sdim uint32_t UnhandledWeight = 0; 1373245431Sdim for (unsigned j = 0, ej = SDB->BitTestCases[i].Cases.size(); j != ej; ++j) 1374245431Sdim UnhandledWeight += SDB->BitTestCases[i].Cases[j].ExtraWeight; 1375245431Sdim 1376199989Srdivacky for (unsigned j = 0, ej = SDB->BitTestCases[i].Cases.size(); j != ej; ++j) { 1377245431Sdim UnhandledWeight -= SDB->BitTestCases[i].Cases[j].ExtraWeight; 1378193323Sed // Set the current basic block to the mbb we wish to insert the code into 1379210299Sed FuncInfo->MBB = SDB->BitTestCases[i].Cases[j].ThisBB; 1380210299Sed FuncInfo->InsertPt = FuncInfo->MBB->end(); 1381193323Sed // Emit the code 1382193323Sed if (j+1 != ej) 1383218893Sdim SDB->visitBitTestCase(SDB->BitTestCases[i], 1384218893Sdim SDB->BitTestCases[i].Cases[j+1].ThisBB, 1385245431Sdim UnhandledWeight, 1386199989Srdivacky SDB->BitTestCases[i].Reg, 1387207618Srdivacky SDB->BitTestCases[i].Cases[j], 1388210299Sed FuncInfo->MBB); 1389193323Sed else 1390218893Sdim SDB->visitBitTestCase(SDB->BitTestCases[i], 1391218893Sdim SDB->BitTestCases[i].Default, 1392245431Sdim UnhandledWeight, 1393199989Srdivacky SDB->BitTestCases[i].Reg, 1394207618Srdivacky SDB->BitTestCases[i].Cases[j], 1395210299Sed FuncInfo->MBB); 1396198090Srdivacky 1397198090Srdivacky 1398199989Srdivacky CurDAG->setRoot(SDB->getRoot()); 1399199989Srdivacky SDB->clear(); 1400210299Sed CodeGenAndEmitDAG(); 1401193323Sed } 1402193323Sed 1403193323Sed // Update PHI Nodes 1404207618Srdivacky for (unsigned pi = 0, pe = FuncInfo->PHINodesToUpdate.size(); 1405207618Srdivacky pi != pe; ++pi) { 1406252723Sdim MachineInstrBuilder PHI(*MF, FuncInfo->PHINodesToUpdate[pi].first); 1407193323Sed MachineBasicBlock *PHIBB = PHI->getParent(); 1408203954Srdivacky assert(PHI->isPHI() && 1409193323Sed "This is not a machine PHI node that we are updating!"); 1410193323Sed // This is "default" BB. We have two jumps to it. From "header" BB and 1411193323Sed // from last "case" BB. 1412252723Sdim if (PHIBB == SDB->BitTestCases[i].Default) 1413252723Sdim PHI.addReg(FuncInfo->PHINodesToUpdate[pi].second) 1414252723Sdim .addMBB(SDB->BitTestCases[i].Parent) 1415252723Sdim .addReg(FuncInfo->PHINodesToUpdate[pi].second) 1416252723Sdim .addMBB(SDB->BitTestCases[i].Cases.back().ThisBB); 1417193323Sed // One of "cases" BB. 1418199989Srdivacky for (unsigned j = 0, ej = SDB->BitTestCases[i].Cases.size(); 1419193323Sed j != ej; ++j) { 1420199989Srdivacky MachineBasicBlock* cBB = SDB->BitTestCases[i].Cases[j].ThisBB; 1421252723Sdim if (cBB->isSuccessor(PHIBB)) 1422252723Sdim PHI.addReg(FuncInfo->PHINodesToUpdate[pi].second).addMBB(cBB); 1423193323Sed } 1424193323Sed } 1425193323Sed } 1426199989Srdivacky SDB->BitTestCases.clear(); 1427193323Sed 1428193323Sed // If the JumpTable record is filled in, then we need to emit a jump table. 1429193323Sed // Updating the PHI nodes is tricky in this case, since we need to determine 1430193323Sed // whether the PHI is a successor of the range check MBB or the jump table MBB 1431199989Srdivacky for (unsigned i = 0, e = SDB->JTCases.size(); i != e; ++i) { 1432193323Sed // Lower header first, if it wasn't already lowered 1433199989Srdivacky if (!SDB->JTCases[i].first.Emitted) { 1434193323Sed // Set the current basic block to the mbb we wish to insert the code into 1435210299Sed FuncInfo->MBB = SDB->JTCases[i].first.HeaderBB; 1436210299Sed FuncInfo->InsertPt = FuncInfo->MBB->end(); 1437193323Sed // Emit the code 1438207618Srdivacky SDB->visitJumpTableHeader(SDB->JTCases[i].second, SDB->JTCases[i].first, 1439210299Sed FuncInfo->MBB); 1440199989Srdivacky CurDAG->setRoot(SDB->getRoot()); 1441199989Srdivacky SDB->clear(); 1442210299Sed CodeGenAndEmitDAG(); 1443193323Sed } 1444198090Srdivacky 1445193323Sed // Set the current basic block to the mbb we wish to insert the code into 1446210299Sed FuncInfo->MBB = SDB->JTCases[i].second.MBB; 1447210299Sed FuncInfo->InsertPt = FuncInfo->MBB->end(); 1448193323Sed // Emit the code 1449199989Srdivacky SDB->visitJumpTable(SDB->JTCases[i].second); 1450199989Srdivacky CurDAG->setRoot(SDB->getRoot()); 1451199989Srdivacky SDB->clear(); 1452210299Sed CodeGenAndEmitDAG(); 1453198090Srdivacky 1454193323Sed // Update PHI Nodes 1455207618Srdivacky for (unsigned pi = 0, pe = FuncInfo->PHINodesToUpdate.size(); 1456207618Srdivacky pi != pe; ++pi) { 1457252723Sdim MachineInstrBuilder PHI(*MF, FuncInfo->PHINodesToUpdate[pi].first); 1458193323Sed MachineBasicBlock *PHIBB = PHI->getParent(); 1459203954Srdivacky assert(PHI->isPHI() && 1460193323Sed "This is not a machine PHI node that we are updating!"); 1461193323Sed // "default" BB. We can go there only from header BB. 1462252723Sdim if (PHIBB == SDB->JTCases[i].second.Default) 1463252723Sdim PHI.addReg(FuncInfo->PHINodesToUpdate[pi].second) 1464252723Sdim .addMBB(SDB->JTCases[i].first.HeaderBB); 1465193323Sed // JT BB. Just iterate over successors here 1466252723Sdim if (FuncInfo->MBB->isSuccessor(PHIBB)) 1467252723Sdim PHI.addReg(FuncInfo->PHINodesToUpdate[pi].second).addMBB(FuncInfo->MBB); 1468193323Sed } 1469193323Sed } 1470199989Srdivacky SDB->JTCases.clear(); 1471198090Srdivacky 1472193323Sed // If the switch block involved a branch to one of the actual successors, we 1473193323Sed // need to update PHI nodes in that block. 1474207618Srdivacky for (unsigned i = 0, e = FuncInfo->PHINodesToUpdate.size(); i != e; ++i) { 1475252723Sdim MachineInstrBuilder PHI(*MF, FuncInfo->PHINodesToUpdate[i].first); 1476203954Srdivacky assert(PHI->isPHI() && 1477193323Sed "This is not a machine PHI node that we are updating!"); 1478252723Sdim if (FuncInfo->MBB->isSuccessor(PHI->getParent())) 1479252723Sdim PHI.addReg(FuncInfo->PHINodesToUpdate[i].second).addMBB(FuncInfo->MBB); 1480193323Sed } 1481198090Srdivacky 1482193323Sed // If we generated any switch lowering information, build and codegen any 1483193323Sed // additional DAGs necessary. 1484199989Srdivacky for (unsigned i = 0, e = SDB->SwitchCases.size(); i != e; ++i) { 1485193323Sed // Set the current basic block to the mbb we wish to insert the code into 1486218893Sdim FuncInfo->MBB = SDB->SwitchCases[i].ThisBB; 1487210299Sed FuncInfo->InsertPt = FuncInfo->MBB->end(); 1488198090Srdivacky 1489207618Srdivacky // Determine the unique successors. 1490207618Srdivacky SmallVector<MachineBasicBlock *, 2> Succs; 1491207618Srdivacky Succs.push_back(SDB->SwitchCases[i].TrueBB); 1492207618Srdivacky if (SDB->SwitchCases[i].TrueBB != SDB->SwitchCases[i].FalseBB) 1493207618Srdivacky Succs.push_back(SDB->SwitchCases[i].FalseBB); 1494207618Srdivacky 1495218893Sdim // Emit the code. Note that this could result in FuncInfo->MBB being split. 1496210299Sed SDB->visitSwitchCase(SDB->SwitchCases[i], FuncInfo->MBB); 1497199989Srdivacky CurDAG->setRoot(SDB->getRoot()); 1498207618Srdivacky SDB->clear(); 1499210299Sed CodeGenAndEmitDAG(); 1500198090Srdivacky 1501218893Sdim // Remember the last block, now that any splitting is done, for use in 1502218893Sdim // populating PHI nodes in successors. 1503218893Sdim MachineBasicBlock *ThisBB = FuncInfo->MBB; 1504218893Sdim 1505193323Sed // Handle any PHI nodes in successors of this chunk, as if we were coming 1506193323Sed // from the original BB before switch expansion. Note that PHI nodes can 1507193323Sed // occur multiple times in PHINodesToUpdate. We have to be very careful to 1508193323Sed // handle them the right number of times. 1509207618Srdivacky for (unsigned i = 0, e = Succs.size(); i != e; ++i) { 1510210299Sed FuncInfo->MBB = Succs[i]; 1511210299Sed FuncInfo->InsertPt = FuncInfo->MBB->end(); 1512210299Sed // FuncInfo->MBB may have been removed from the CFG if a branch was 1513210299Sed // constant folded. 1514210299Sed if (ThisBB->isSuccessor(FuncInfo->MBB)) { 1515252723Sdim for (MachineBasicBlock::iterator 1516252723Sdim MBBI = FuncInfo->MBB->begin(), MBBE = FuncInfo->MBB->end(); 1517252723Sdim MBBI != MBBE && MBBI->isPHI(); ++MBBI) { 1518252723Sdim MachineInstrBuilder PHI(*MF, MBBI); 1519202375Srdivacky // This value for this PHI node is recorded in PHINodesToUpdate. 1520202375Srdivacky for (unsigned pn = 0; ; ++pn) { 1521207618Srdivacky assert(pn != FuncInfo->PHINodesToUpdate.size() && 1522202375Srdivacky "Didn't find PHI entry!"); 1523252723Sdim if (FuncInfo->PHINodesToUpdate[pn].first == PHI) { 1524252723Sdim PHI.addReg(FuncInfo->PHINodesToUpdate[pn].second).addMBB(ThisBB); 1525202375Srdivacky break; 1526202375Srdivacky } 1527193323Sed } 1528193323Sed } 1529193323Sed } 1530193323Sed } 1531193323Sed } 1532199989Srdivacky SDB->SwitchCases.clear(); 1533193323Sed} 1534193323Sed 1535193323Sed 1536193323Sed/// Create the scheduler. If a specific scheduler was specified 1537193323Sed/// via the SchedulerRegistry, use it, otherwise select the 1538193323Sed/// one preferred by the target. 1539193323Sed/// 1540193323SedScheduleDAGSDNodes *SelectionDAGISel::CreateScheduler() { 1541193323Sed RegisterScheduler::FunctionPassCtor Ctor = RegisterScheduler::getDefault(); 1542198090Srdivacky 1543193323Sed if (!Ctor) { 1544193323Sed Ctor = ISHeuristic; 1545193323Sed RegisterScheduler::setDefault(Ctor); 1546193323Sed } 1547198090Srdivacky 1548193323Sed return Ctor(this, OptLevel); 1549193323Sed} 1550193323Sed 1551193323Sed//===----------------------------------------------------------------------===// 1552193323Sed// Helper functions used by the generated instruction selector. 1553193323Sed//===----------------------------------------------------------------------===// 1554193323Sed// Calls to these methods are generated by tblgen. 1555193323Sed 1556193323Sed/// CheckAndMask - The isel is trying to match something like (and X, 255). If 1557193323Sed/// the dag combiner simplified the 255, we still want to match. RHS is the 1558193323Sed/// actual value in the DAG on the RHS of an AND, and DesiredMaskS is the value 1559193323Sed/// specified in the .td file (e.g. 255). 1560198090Srdivackybool SelectionDAGISel::CheckAndMask(SDValue LHS, ConstantSDNode *RHS, 1561193323Sed int64_t DesiredMaskS) const { 1562193323Sed const APInt &ActualMask = RHS->getAPIntValue(); 1563193323Sed const APInt &DesiredMask = APInt(LHS.getValueSizeInBits(), DesiredMaskS); 1564198090Srdivacky 1565193323Sed // If the actual mask exactly matches, success! 1566193323Sed if (ActualMask == DesiredMask) 1567193323Sed return true; 1568198090Srdivacky 1569193323Sed // If the actual AND mask is allowing unallowed bits, this doesn't match. 1570193323Sed if (ActualMask.intersects(~DesiredMask)) 1571193323Sed return false; 1572198090Srdivacky 1573193323Sed // Otherwise, the DAG Combiner may have proven that the value coming in is 1574193323Sed // either already zero or is not demanded. Check for known zero input bits. 1575193323Sed APInt NeededMask = DesiredMask & ~ActualMask; 1576193323Sed if (CurDAG->MaskedValueIsZero(LHS, NeededMask)) 1577193323Sed return true; 1578198090Srdivacky 1579193323Sed // TODO: check to see if missing bits are just not demanded. 1580193323Sed 1581193323Sed // Otherwise, this pattern doesn't match. 1582193323Sed return false; 1583193323Sed} 1584193323Sed 1585193323Sed/// CheckOrMask - The isel is trying to match something like (or X, 255). If 1586193323Sed/// the dag combiner simplified the 255, we still want to match. RHS is the 1587193323Sed/// actual value in the DAG on the RHS of an OR, and DesiredMaskS is the value 1588193323Sed/// specified in the .td file (e.g. 255). 1589198090Srdivackybool SelectionDAGISel::CheckOrMask(SDValue LHS, ConstantSDNode *RHS, 1590193323Sed int64_t DesiredMaskS) const { 1591193323Sed const APInt &ActualMask = RHS->getAPIntValue(); 1592193323Sed const APInt &DesiredMask = APInt(LHS.getValueSizeInBits(), DesiredMaskS); 1593198090Srdivacky 1594193323Sed // If the actual mask exactly matches, success! 1595193323Sed if (ActualMask == DesiredMask) 1596193323Sed return true; 1597198090Srdivacky 1598193323Sed // If the actual AND mask is allowing unallowed bits, this doesn't match. 1599193323Sed if (ActualMask.intersects(~DesiredMask)) 1600193323Sed return false; 1601198090Srdivacky 1602193323Sed // Otherwise, the DAG Combiner may have proven that the value coming in is 1603193323Sed // either already zero or is not demanded. Check for known zero input bits. 1604193323Sed APInt NeededMask = DesiredMask & ~ActualMask; 1605198090Srdivacky 1606193323Sed APInt KnownZero, KnownOne; 1607235633Sdim CurDAG->ComputeMaskedBits(LHS, KnownZero, KnownOne); 1608198090Srdivacky 1609193323Sed // If all the missing bits in the or are already known to be set, match! 1610193323Sed if ((NeededMask & KnownOne) == NeededMask) 1611193323Sed return true; 1612198090Srdivacky 1613193323Sed // TODO: check to see if missing bits are just not demanded. 1614198090Srdivacky 1615193323Sed // Otherwise, this pattern doesn't match. 1616193323Sed return false; 1617193323Sed} 1618193323Sed 1619193323Sed 1620193323Sed/// SelectInlineAsmMemoryOperands - Calls to this are automatically generated 1621193323Sed/// by tblgen. Others should not call it. 1622193323Sedvoid SelectionDAGISel:: 1623193323SedSelectInlineAsmMemoryOperands(std::vector<SDValue> &Ops) { 1624193323Sed std::vector<SDValue> InOps; 1625193323Sed std::swap(InOps, Ops); 1626193323Sed 1627207618Srdivacky Ops.push_back(InOps[InlineAsm::Op_InputChain]); // 0 1628207618Srdivacky Ops.push_back(InOps[InlineAsm::Op_AsmString]); // 1 1629207618Srdivacky Ops.push_back(InOps[InlineAsm::Op_MDNode]); // 2, !srcloc 1630218893Sdim Ops.push_back(InOps[InlineAsm::Op_ExtraInfo]); // 3 (SideEffect, AlignStack) 1631193323Sed 1632207618Srdivacky unsigned i = InlineAsm::Op_FirstOperand, e = InOps.size(); 1633218893Sdim if (InOps[e-1].getValueType() == MVT::Glue) 1634218893Sdim --e; // Don't process a glue operand if it is here. 1635198090Srdivacky 1636193323Sed while (i != e) { 1637193323Sed unsigned Flags = cast<ConstantSDNode>(InOps[i])->getZExtValue(); 1638207618Srdivacky if (!InlineAsm::isMemKind(Flags)) { 1639193323Sed // Just skip over this operand, copying the operands verbatim. 1640193323Sed Ops.insert(Ops.end(), InOps.begin()+i, 1641193323Sed InOps.begin()+i+InlineAsm::getNumOperandRegisters(Flags) + 1); 1642193323Sed i += InlineAsm::getNumOperandRegisters(Flags) + 1; 1643193323Sed } else { 1644193323Sed assert(InlineAsm::getNumOperandRegisters(Flags) == 1 && 1645193323Sed "Memory operand with multiple values?"); 1646193323Sed // Otherwise, this is a memory operand. Ask the target to select it. 1647193323Sed std::vector<SDValue> SelOps; 1648207618Srdivacky if (SelectInlineAsmMemoryOperand(InOps[i+1], 'm', SelOps)) 1649207618Srdivacky report_fatal_error("Could not match memory address. Inline asm" 1650207618Srdivacky " failure!"); 1651198090Srdivacky 1652193323Sed // Add this to the output node. 1653207618Srdivacky unsigned NewFlags = 1654207618Srdivacky InlineAsm::getFlagWord(InlineAsm::Kind_Mem, SelOps.size()); 1655207618Srdivacky Ops.push_back(CurDAG->getTargetConstant(NewFlags, MVT::i32)); 1656193323Sed Ops.insert(Ops.end(), SelOps.begin(), SelOps.end()); 1657193323Sed i += 2; 1658193323Sed } 1659193323Sed } 1660198090Srdivacky 1661218893Sdim // Add the glue input back if present. 1662193323Sed if (e != InOps.size()) 1663193323Sed Ops.push_back(InOps.back()); 1664193323Sed} 1665193323Sed 1666218893Sdim/// findGlueUse - Return use of MVT::Glue value produced by the specified 1667193323Sed/// SDNode. 1668193323Sed/// 1669218893Sdimstatic SDNode *findGlueUse(SDNode *N) { 1670193323Sed unsigned FlagResNo = N->getNumValues()-1; 1671193323Sed for (SDNode::use_iterator I = N->use_begin(), E = N->use_end(); I != E; ++I) { 1672193323Sed SDUse &Use = I.getUse(); 1673193323Sed if (Use.getResNo() == FlagResNo) 1674193323Sed return Use.getUser(); 1675193323Sed } 1676193323Sed return NULL; 1677193323Sed} 1678193323Sed 1679193323Sed/// findNonImmUse - Return true if "Use" is a non-immediate use of "Def". 1680193323Sed/// This function recursively traverses up the operand chain, ignoring 1681193323Sed/// certain nodes. 1682193323Sedstatic bool findNonImmUse(SDNode *Use, SDNode* Def, SDNode *ImmedUse, 1683204642Srdivacky SDNode *Root, SmallPtrSet<SDNode*, 16> &Visited, 1684204642Srdivacky bool IgnoreChains) { 1685204642Srdivacky // The NodeID's are given uniques ID's where a node ID is guaranteed to be 1686204642Srdivacky // greater than all of its (recursive) operands. If we scan to a point where 1687204642Srdivacky // 'use' is smaller than the node we're scanning for, then we know we will 1688204642Srdivacky // never find it. 1689204642Srdivacky // 1690204642Srdivacky // The Use may be -1 (unassigned) if it is a newly allocated node. This can 1691218893Sdim // happen because we scan down to newly selected nodes in the case of glue 1692204642Srdivacky // uses. 1693204642Srdivacky if ((Use->getNodeId() < Def->getNodeId() && Use->getNodeId() != -1)) 1694193323Sed return false; 1695218893Sdim 1696204642Srdivacky // Don't revisit nodes if we already scanned it and didn't fail, we know we 1697204642Srdivacky // won't fail if we scan it again. 1698204642Srdivacky if (!Visited.insert(Use)) 1699204642Srdivacky return false; 1700193323Sed 1701193323Sed for (unsigned i = 0, e = Use->getNumOperands(); i != e; ++i) { 1702204642Srdivacky // Ignore chain uses, they are validated by HandleMergeInputChains. 1703204642Srdivacky if (Use->getOperand(i).getValueType() == MVT::Other && IgnoreChains) 1704204642Srdivacky continue; 1705218893Sdim 1706193323Sed SDNode *N = Use->getOperand(i).getNode(); 1707193323Sed if (N == Def) { 1708193323Sed if (Use == ImmedUse || Use == Root) 1709193323Sed continue; // We are not looking for immediate use. 1710193323Sed assert(N != Root); 1711193323Sed return true; 1712193323Sed } 1713193323Sed 1714193323Sed // Traverse up the operand chain. 1715204642Srdivacky if (findNonImmUse(N, Def, ImmedUse, Root, Visited, IgnoreChains)) 1716193323Sed return true; 1717193323Sed } 1718193323Sed return false; 1719193323Sed} 1720193323Sed 1721203954Srdivacky/// IsProfitableToFold - Returns true if it's profitable to fold the specific 1722203954Srdivacky/// operand node N of U during instruction selection that starts at Root. 1723203954Srdivackybool SelectionDAGISel::IsProfitableToFold(SDValue N, SDNode *U, 1724203954Srdivacky SDNode *Root) const { 1725193323Sed if (OptLevel == CodeGenOpt::None) return false; 1726203954Srdivacky return N.hasOneUse(); 1727203954Srdivacky} 1728193323Sed 1729203954Srdivacky/// IsLegalToFold - Returns true if the specific operand node N of 1730203954Srdivacky/// U can be folded during instruction selection that starts at Root. 1731204642Srdivackybool SelectionDAGISel::IsLegalToFold(SDValue N, SDNode *U, SDNode *Root, 1732207618Srdivacky CodeGenOpt::Level OptLevel, 1733207618Srdivacky bool IgnoreChains) { 1734203954Srdivacky if (OptLevel == CodeGenOpt::None) return false; 1735203954Srdivacky 1736193323Sed // If Root use can somehow reach N through a path that that doesn't contain 1737193323Sed // U then folding N would create a cycle. e.g. In the following 1738193323Sed // diagram, Root can reach N through X. If N is folded into into Root, then 1739193323Sed // X is both a predecessor and a successor of U. 1740193323Sed // 1741193323Sed // [N*] // 1742193323Sed // ^ ^ // 1743193323Sed // / \ // 1744193323Sed // [U*] [X]? // 1745193323Sed // ^ ^ // 1746193323Sed // \ / // 1747193323Sed // \ / // 1748193323Sed // [Root*] // 1749193323Sed // 1750193323Sed // * indicates nodes to be folded together. 1751193323Sed // 1752218893Sdim // If Root produces glue, then it gets (even more) interesting. Since it 1753218893Sdim // will be "glued" together with its glue use in the scheduler, we need to 1754193323Sed // check if it might reach N. 1755193323Sed // 1756193323Sed // [N*] // 1757193323Sed // ^ ^ // 1758193323Sed // / \ // 1759193323Sed // [U*] [X]? // 1760193323Sed // ^ ^ // 1761193323Sed // \ \ // 1762193323Sed // \ | // 1763193323Sed // [Root*] | // 1764193323Sed // ^ | // 1765193323Sed // f | // 1766193323Sed // | / // 1767193323Sed // [Y] / // 1768193323Sed // ^ / // 1769193323Sed // f / // 1770193323Sed // | / // 1771218893Sdim // [GU] // 1772193323Sed // 1773218893Sdim // If GU (glue use) indirectly reaches N (the load), and Root folds N 1774218893Sdim // (call it Fold), then X is a predecessor of GU and a successor of 1775218893Sdim // Fold. But since Fold and GU are glued together, this will create 1776193323Sed // a cycle in the scheduling graph. 1777193323Sed 1778218893Sdim // If the node has glue, walk down the graph to the "lowest" node in the 1779218893Sdim // glueged set. 1780198090Srdivacky EVT VT = Root->getValueType(Root->getNumValues()-1); 1781218893Sdim while (VT == MVT::Glue) { 1782218893Sdim SDNode *GU = findGlueUse(Root); 1783218893Sdim if (GU == NULL) 1784193323Sed break; 1785218893Sdim Root = GU; 1786193323Sed VT = Root->getValueType(Root->getNumValues()-1); 1787218893Sdim 1788218893Sdim // If our query node has a glue result with a use, we've walked up it. If 1789204792Srdivacky // the user (which has already been selected) has a chain or indirectly uses 1790204792Srdivacky // the chain, our WalkChainUsers predicate will not consider it. Because of 1791204792Srdivacky // this, we cannot ignore chains in this predicate. 1792204792Srdivacky IgnoreChains = false; 1793193323Sed } 1794193323Sed 1795218893Sdim 1796204792Srdivacky SmallPtrSet<SDNode*, 16> Visited; 1797204792Srdivacky return !findNonImmUse(Root, N.getNode(), U, Root, Visited, IgnoreChains); 1798193323Sed} 1799193323Sed 1800202375SrdivackySDNode *SelectionDAGISel::Select_INLINEASM(SDNode *N) { 1801202375Srdivacky std::vector<SDValue> Ops(N->op_begin(), N->op_end()); 1802198892Srdivacky SelectInlineAsmMemoryOperands(Ops); 1803218893Sdim 1804252723Sdim EVT VTs[] = { MVT::Other, MVT::Glue }; 1805263509Sdim SDValue New = CurDAG->getNode(ISD::INLINEASM, SDLoc(N), 1806198892Srdivacky VTs, &Ops[0], Ops.size()); 1807204642Srdivacky New->setNodeId(-1); 1808198892Srdivacky return New.getNode(); 1809198892Srdivacky} 1810193323Sed 1811202375SrdivackySDNode *SelectionDAGISel::Select_UNDEF(SDNode *N) { 1812203954Srdivacky return CurDAG->SelectNodeTo(N, TargetOpcode::IMPLICIT_DEF,N->getValueType(0)); 1813198892Srdivacky} 1814198892Srdivacky 1815204642Srdivacky/// GetVBR - decode a vbr encoding whose top bit is set. 1816218893SdimLLVM_ATTRIBUTE_ALWAYS_INLINE static uint64_t 1817204642SrdivackyGetVBR(uint64_t Val, const unsigned char *MatcherTable, unsigned &Idx) { 1818204642Srdivacky assert(Val >= 128 && "Not a VBR"); 1819204642Srdivacky Val &= 127; // Remove first vbr bit. 1820218893Sdim 1821204642Srdivacky unsigned Shift = 7; 1822204642Srdivacky uint64_t NextBits; 1823204642Srdivacky do { 1824204642Srdivacky NextBits = MatcherTable[Idx++]; 1825204642Srdivacky Val |= (NextBits&127) << Shift; 1826204642Srdivacky Shift += 7; 1827204642Srdivacky } while (NextBits & 128); 1828218893Sdim 1829204642Srdivacky return Val; 1830204642Srdivacky} 1831204642Srdivacky 1832204642Srdivacky 1833218893Sdim/// UpdateChainsAndGlue - When a match is complete, this method updates uses of 1834218893Sdim/// interior glue and chain results to use the new glue and chain results. 1835204642Srdivackyvoid SelectionDAGISel:: 1836218893SdimUpdateChainsAndGlue(SDNode *NodeToMatch, SDValue InputChain, 1837218893Sdim const SmallVectorImpl<SDNode*> &ChainNodesMatched, 1838218893Sdim SDValue InputGlue, 1839218893Sdim const SmallVectorImpl<SDNode*> &GlueResultNodesMatched, 1840218893Sdim bool isMorphNodeTo) { 1841204642Srdivacky SmallVector<SDNode*, 4> NowDeadNodes; 1842218893Sdim 1843204642Srdivacky // Now that all the normal results are replaced, we replace the chain and 1844218893Sdim // glue results if present. 1845204642Srdivacky if (!ChainNodesMatched.empty()) { 1846204642Srdivacky assert(InputChain.getNode() != 0 && 1847204642Srdivacky "Matched input chains but didn't produce a chain"); 1848204642Srdivacky // Loop over all of the nodes we matched that produced a chain result. 1849204642Srdivacky // Replace all the chain results with the final chain we ended up with. 1850204642Srdivacky for (unsigned i = 0, e = ChainNodesMatched.size(); i != e; ++i) { 1851204642Srdivacky SDNode *ChainNode = ChainNodesMatched[i]; 1852218893Sdim 1853204642Srdivacky // If this node was already deleted, don't look at it. 1854204642Srdivacky if (ChainNode->getOpcode() == ISD::DELETED_NODE) 1855204642Srdivacky continue; 1856218893Sdim 1857204642Srdivacky // Don't replace the results of the root node if we're doing a 1858204642Srdivacky // MorphNodeTo. 1859204642Srdivacky if (ChainNode == NodeToMatch && isMorphNodeTo) 1860204642Srdivacky continue; 1861218893Sdim 1862204642Srdivacky SDValue ChainVal = SDValue(ChainNode, ChainNode->getNumValues()-1); 1863218893Sdim if (ChainVal.getValueType() == MVT::Glue) 1864204642Srdivacky ChainVal = ChainVal.getValue(ChainVal->getNumValues()-2); 1865204642Srdivacky assert(ChainVal.getValueType() == MVT::Other && "Not a chain?"); 1866245431Sdim CurDAG->ReplaceAllUsesOfValueWith(ChainVal, InputChain); 1867218893Sdim 1868206083Srdivacky // If the node became dead and we haven't already seen it, delete it. 1869206083Srdivacky if (ChainNode->use_empty() && 1870206083Srdivacky !std::count(NowDeadNodes.begin(), NowDeadNodes.end(), ChainNode)) 1871204642Srdivacky NowDeadNodes.push_back(ChainNode); 1872204642Srdivacky } 1873204642Srdivacky } 1874218893Sdim 1875218893Sdim // If the result produces glue, update any glue results in the matched 1876218893Sdim // pattern with the glue result. 1877218893Sdim if (InputGlue.getNode() != 0) { 1878204642Srdivacky // Handle any interior nodes explicitly marked. 1879218893Sdim for (unsigned i = 0, e = GlueResultNodesMatched.size(); i != e; ++i) { 1880218893Sdim SDNode *FRN = GlueResultNodesMatched[i]; 1881218893Sdim 1882204642Srdivacky // If this node was already deleted, don't look at it. 1883204642Srdivacky if (FRN->getOpcode() == ISD::DELETED_NODE) 1884204642Srdivacky continue; 1885218893Sdim 1886218893Sdim assert(FRN->getValueType(FRN->getNumValues()-1) == MVT::Glue && 1887218893Sdim "Doesn't have a glue result"); 1888204642Srdivacky CurDAG->ReplaceAllUsesOfValueWith(SDValue(FRN, FRN->getNumValues()-1), 1889245431Sdim InputGlue); 1890218893Sdim 1891206083Srdivacky // If the node became dead and we haven't already seen it, delete it. 1892206083Srdivacky if (FRN->use_empty() && 1893206083Srdivacky !std::count(NowDeadNodes.begin(), NowDeadNodes.end(), FRN)) 1894204642Srdivacky NowDeadNodes.push_back(FRN); 1895204642Srdivacky } 1896204642Srdivacky } 1897218893Sdim 1898204642Srdivacky if (!NowDeadNodes.empty()) 1899245431Sdim CurDAG->RemoveDeadNodes(NowDeadNodes); 1900218893Sdim 1901252723Sdim DEBUG(dbgs() << "ISEL: Match complete!\n"); 1902204642Srdivacky} 1903204642Srdivacky 1904204642Srdivackyenum ChainResult { 1905204642Srdivacky CR_Simple, 1906204642Srdivacky CR_InducesCycle, 1907204642Srdivacky CR_LeadsToInteriorNode 1908204642Srdivacky}; 1909204642Srdivacky 1910204642Srdivacky/// WalkChainUsers - Walk down the users of the specified chained node that is 1911204642Srdivacky/// part of the pattern we're matching, looking at all of the users we find. 1912204642Srdivacky/// This determines whether something is an interior node, whether we have a 1913204642Srdivacky/// non-pattern node in between two pattern nodes (which prevent folding because 1914204642Srdivacky/// it would induce a cycle) and whether we have a TokenFactor node sandwiched 1915204642Srdivacky/// between pattern nodes (in which case the TF becomes part of the pattern). 1916204642Srdivacky/// 1917204642Srdivacky/// The walk we do here is guaranteed to be small because we quickly get down to 1918204642Srdivacky/// already selected nodes "below" us. 1919218893Sdimstatic ChainResult 1920245431SdimWalkChainUsers(const SDNode *ChainedNode, 1921204642Srdivacky SmallVectorImpl<SDNode*> &ChainedNodesInPattern, 1922204642Srdivacky SmallVectorImpl<SDNode*> &InteriorChainedNodes) { 1923204642Srdivacky ChainResult Result = CR_Simple; 1924218893Sdim 1925204642Srdivacky for (SDNode::use_iterator UI = ChainedNode->use_begin(), 1926204642Srdivacky E = ChainedNode->use_end(); UI != E; ++UI) { 1927204642Srdivacky // Make sure the use is of the chain, not some other value we produce. 1928204642Srdivacky if (UI.getUse().getValueType() != MVT::Other) continue; 1929218893Sdim 1930204642Srdivacky SDNode *User = *UI; 1931204642Srdivacky 1932255946Sdim if (User->getOpcode() == ISD::HANDLENODE) // Root of the graph. 1933255946Sdim continue; 1934255946Sdim 1935204642Srdivacky // If we see an already-selected machine node, then we've gone beyond the 1936204642Srdivacky // pattern that we're selecting down into the already selected chunk of the 1937204642Srdivacky // DAG. 1938255946Sdim unsigned UserOpcode = User->getOpcode(); 1939204642Srdivacky if (User->isMachineOpcode() || 1940255946Sdim UserOpcode == ISD::CopyToReg || 1941245431Sdim UserOpcode == ISD::CopyFromReg || 1942245431Sdim UserOpcode == ISD::INLINEASM || 1943245431Sdim UserOpcode == ISD::EH_LABEL || 1944245431Sdim UserOpcode == ISD::LIFETIME_START || 1945245431Sdim UserOpcode == ISD::LIFETIME_END) { 1946204642Srdivacky // If their node ID got reset to -1 then they've already been selected. 1947204642Srdivacky // Treat them like a MachineOpcode. 1948204642Srdivacky if (User->getNodeId() == -1) 1949204642Srdivacky continue; 1950204642Srdivacky } 1951204642Srdivacky 1952204642Srdivacky // If we have a TokenFactor, we handle it specially. 1953204642Srdivacky if (User->getOpcode() != ISD::TokenFactor) { 1954204642Srdivacky // If the node isn't a token factor and isn't part of our pattern, then it 1955204642Srdivacky // must be a random chained node in between two nodes we're selecting. 1956204642Srdivacky // This happens when we have something like: 1957204642Srdivacky // x = load ptr 1958204642Srdivacky // call 1959204642Srdivacky // y = x+4 1960204642Srdivacky // store y -> ptr 1961204642Srdivacky // Because we structurally match the load/store as a read/modify/write, 1962204642Srdivacky // but the call is chained between them. We cannot fold in this case 1963204642Srdivacky // because it would induce a cycle in the graph. 1964204642Srdivacky if (!std::count(ChainedNodesInPattern.begin(), 1965204642Srdivacky ChainedNodesInPattern.end(), User)) 1966204642Srdivacky return CR_InducesCycle; 1967218893Sdim 1968204642Srdivacky // Otherwise we found a node that is part of our pattern. For example in: 1969204642Srdivacky // x = load ptr 1970204642Srdivacky // y = x+4 1971204642Srdivacky // store y -> ptr 1972204642Srdivacky // This would happen when we're scanning down from the load and see the 1973204642Srdivacky // store as a user. Record that there is a use of ChainedNode that is 1974204642Srdivacky // part of the pattern and keep scanning uses. 1975204642Srdivacky Result = CR_LeadsToInteriorNode; 1976204642Srdivacky InteriorChainedNodes.push_back(User); 1977204642Srdivacky continue; 1978204642Srdivacky } 1979218893Sdim 1980204642Srdivacky // If we found a TokenFactor, there are two cases to consider: first if the 1981204642Srdivacky // TokenFactor is just hanging "below" the pattern we're matching (i.e. no 1982204642Srdivacky // uses of the TF are in our pattern) we just want to ignore it. Second, 1983204642Srdivacky // the TokenFactor can be sandwiched in between two chained nodes, like so: 1984204642Srdivacky // [Load chain] 1985204642Srdivacky // ^ 1986204642Srdivacky // | 1987204642Srdivacky // [Load] 1988204642Srdivacky // ^ ^ 1989204642Srdivacky // | \ DAG's like cheese 1990204642Srdivacky // / \ do you? 1991204642Srdivacky // / | 1992204642Srdivacky // [TokenFactor] [Op] 1993204642Srdivacky // ^ ^ 1994204642Srdivacky // | | 1995204642Srdivacky // \ / 1996204642Srdivacky // \ / 1997204642Srdivacky // [Store] 1998204642Srdivacky // 1999204642Srdivacky // In this case, the TokenFactor becomes part of our match and we rewrite it 2000204642Srdivacky // as a new TokenFactor. 2001204642Srdivacky // 2002204642Srdivacky // To distinguish these two cases, do a recursive walk down the uses. 2003204642Srdivacky switch (WalkChainUsers(User, ChainedNodesInPattern, InteriorChainedNodes)) { 2004204642Srdivacky case CR_Simple: 2005204642Srdivacky // If the uses of the TokenFactor are just already-selected nodes, ignore 2006204642Srdivacky // it, it is "below" our pattern. 2007204642Srdivacky continue; 2008204642Srdivacky case CR_InducesCycle: 2009204642Srdivacky // If the uses of the TokenFactor lead to nodes that are not part of our 2010204642Srdivacky // pattern that are not selected, folding would turn this into a cycle, 2011204642Srdivacky // bail out now. 2012204642Srdivacky return CR_InducesCycle; 2013204642Srdivacky case CR_LeadsToInteriorNode: 2014204642Srdivacky break; // Otherwise, keep processing. 2015204642Srdivacky } 2016218893Sdim 2017204642Srdivacky // Okay, we know we're in the interesting interior case. The TokenFactor 2018204642Srdivacky // is now going to be considered part of the pattern so that we rewrite its 2019204642Srdivacky // uses (it may have uses that are not part of the pattern) with the 2020204642Srdivacky // ultimate chain result of the generated code. We will also add its chain 2021204642Srdivacky // inputs as inputs to the ultimate TokenFactor we create. 2022204642Srdivacky Result = CR_LeadsToInteriorNode; 2023204642Srdivacky ChainedNodesInPattern.push_back(User); 2024204642Srdivacky InteriorChainedNodes.push_back(User); 2025204642Srdivacky continue; 2026204642Srdivacky } 2027218893Sdim 2028204642Srdivacky return Result; 2029204642Srdivacky} 2030204642Srdivacky 2031204642Srdivacky/// HandleMergeInputChains - This implements the OPC_EmitMergeInputChains 2032204642Srdivacky/// operation for when the pattern matched at least one node with a chains. The 2033204642Srdivacky/// input vector contains a list of all of the chained nodes that we match. We 2034204642Srdivacky/// must determine if this is a valid thing to cover (i.e. matching it won't 2035204642Srdivacky/// induce cycles in the DAG) and if so, creating a TokenFactor node. that will 2036204642Srdivacky/// be used as the input node chain for the generated nodes. 2037204642Srdivackystatic SDValue 2038204642SrdivackyHandleMergeInputChains(SmallVectorImpl<SDNode*> &ChainNodesMatched, 2039204642Srdivacky SelectionDAG *CurDAG) { 2040204642Srdivacky // Walk all of the chained nodes we've matched, recursively scanning down the 2041204642Srdivacky // users of the chain result. This adds any TokenFactor nodes that are caught 2042204642Srdivacky // in between chained nodes to the chained and interior nodes list. 2043204642Srdivacky SmallVector<SDNode*, 3> InteriorChainedNodes; 2044204642Srdivacky for (unsigned i = 0, e = ChainNodesMatched.size(); i != e; ++i) { 2045204642Srdivacky if (WalkChainUsers(ChainNodesMatched[i], ChainNodesMatched, 2046204642Srdivacky InteriorChainedNodes) == CR_InducesCycle) 2047204642Srdivacky return SDValue(); // Would induce a cycle. 2048204642Srdivacky } 2049218893Sdim 2050204642Srdivacky // Okay, we have walked all the matched nodes and collected TokenFactor nodes 2051204642Srdivacky // that we are interested in. Form our input TokenFactor node. 2052204642Srdivacky SmallVector<SDValue, 3> InputChains; 2053204642Srdivacky for (unsigned i = 0, e = ChainNodesMatched.size(); i != e; ++i) { 2054204642Srdivacky // Add the input chain of this node to the InputChains list (which will be 2055204642Srdivacky // the operands of the generated TokenFactor) if it's not an interior node. 2056204642Srdivacky SDNode *N = ChainNodesMatched[i]; 2057204642Srdivacky if (N->getOpcode() != ISD::TokenFactor) { 2058204642Srdivacky if (std::count(InteriorChainedNodes.begin(),InteriorChainedNodes.end(),N)) 2059204642Srdivacky continue; 2060218893Sdim 2061204642Srdivacky // Otherwise, add the input chain. 2062204642Srdivacky SDValue InChain = ChainNodesMatched[i]->getOperand(0); 2063204642Srdivacky assert(InChain.getValueType() == MVT::Other && "Not a chain"); 2064204642Srdivacky InputChains.push_back(InChain); 2065204642Srdivacky continue; 2066204642Srdivacky } 2067218893Sdim 2068204642Srdivacky // If we have a token factor, we want to add all inputs of the token factor 2069204642Srdivacky // that are not part of the pattern we're matching. 2070204642Srdivacky for (unsigned op = 0, e = N->getNumOperands(); op != e; ++op) { 2071204642Srdivacky if (!std::count(ChainNodesMatched.begin(), ChainNodesMatched.end(), 2072204642Srdivacky N->getOperand(op).getNode())) 2073204642Srdivacky InputChains.push_back(N->getOperand(op)); 2074204642Srdivacky } 2075204642Srdivacky } 2076218893Sdim 2077204642Srdivacky if (InputChains.size() == 1) 2078204642Srdivacky return InputChains[0]; 2079263509Sdim return CurDAG->getNode(ISD::TokenFactor, SDLoc(ChainNodesMatched[0]), 2080204642Srdivacky MVT::Other, &InputChains[0], InputChains.size()); 2081218893Sdim} 2082204642Srdivacky 2083204642Srdivacky/// MorphNode - Handle morphing a node in place for the selector. 2084204642SrdivackySDNode *SelectionDAGISel:: 2085204642SrdivackyMorphNode(SDNode *Node, unsigned TargetOpc, SDVTList VTList, 2086204642Srdivacky const SDValue *Ops, unsigned NumOps, unsigned EmitNodeInfo) { 2087204642Srdivacky // It is possible we're using MorphNodeTo to replace a node with no 2088204642Srdivacky // normal results with one that has a normal result (or we could be 2089218893Sdim // adding a chain) and the input could have glue and chains as well. 2090206083Srdivacky // In this case we need to shift the operands down. 2091204642Srdivacky // FIXME: This is a horrible hack and broken in obscure cases, no worse 2092206083Srdivacky // than the old isel though. 2093218893Sdim int OldGlueResultNo = -1, OldChainResultNo = -1; 2094204642Srdivacky 2095204642Srdivacky unsigned NTMNumResults = Node->getNumValues(); 2096218893Sdim if (Node->getValueType(NTMNumResults-1) == MVT::Glue) { 2097218893Sdim OldGlueResultNo = NTMNumResults-1; 2098204642Srdivacky if (NTMNumResults != 1 && 2099204642Srdivacky Node->getValueType(NTMNumResults-2) == MVT::Other) 2100204642Srdivacky OldChainResultNo = NTMNumResults-2; 2101204642Srdivacky } else if (Node->getValueType(NTMNumResults-1) == MVT::Other) 2102204642Srdivacky OldChainResultNo = NTMNumResults-1; 2103204642Srdivacky 2104204642Srdivacky // Call the underlying SelectionDAG routine to do the transmogrification. Note 2105204642Srdivacky // that this deletes operands of the old node that become dead. 2106204642Srdivacky SDNode *Res = CurDAG->MorphNodeTo(Node, ~TargetOpc, VTList, Ops, NumOps); 2107204642Srdivacky 2108204642Srdivacky // MorphNodeTo can operate in two ways: if an existing node with the 2109204642Srdivacky // specified operands exists, it can just return it. Otherwise, it 2110204642Srdivacky // updates the node in place to have the requested operands. 2111204642Srdivacky if (Res == Node) { 2112204642Srdivacky // If we updated the node in place, reset the node ID. To the isel, 2113204642Srdivacky // this should be just like a newly allocated machine node. 2114204642Srdivacky Res->setNodeId(-1); 2115204642Srdivacky } 2116204642Srdivacky 2117204642Srdivacky unsigned ResNumResults = Res->getNumValues(); 2118218893Sdim // Move the glue if needed. 2119218893Sdim if ((EmitNodeInfo & OPFL_GlueOutput) && OldGlueResultNo != -1 && 2120218893Sdim (unsigned)OldGlueResultNo != ResNumResults-1) 2121218893Sdim CurDAG->ReplaceAllUsesOfValueWith(SDValue(Node, OldGlueResultNo), 2122204642Srdivacky SDValue(Res, ResNumResults-1)); 2123204642Srdivacky 2124218893Sdim if ((EmitNodeInfo & OPFL_GlueOutput) != 0) 2125210299Sed --ResNumResults; 2126204642Srdivacky 2127204642Srdivacky // Move the chain reference if needed. 2128204642Srdivacky if ((EmitNodeInfo & OPFL_Chain) && OldChainResultNo != -1 && 2129204642Srdivacky (unsigned)OldChainResultNo != ResNumResults-1) 2130218893Sdim CurDAG->ReplaceAllUsesOfValueWith(SDValue(Node, OldChainResultNo), 2131204642Srdivacky SDValue(Res, ResNumResults-1)); 2132204642Srdivacky 2133204642Srdivacky // Otherwise, no replacement happened because the node already exists. Replace 2134204642Srdivacky // Uses of the old node with the new one. 2135204642Srdivacky if (Res != Node) 2136204642Srdivacky CurDAG->ReplaceAllUsesWith(Node, Res); 2137218893Sdim 2138204642Srdivacky return Res; 2139204642Srdivacky} 2140204642Srdivacky 2141245431Sdim/// CheckSame - Implements OP_CheckSame. 2142218893SdimLLVM_ATTRIBUTE_ALWAYS_INLINE static bool 2143204642SrdivackyCheckSame(const unsigned char *MatcherTable, unsigned &MatcherIndex, 2144218893Sdim SDValue N, 2145218893Sdim const SmallVectorImpl<std::pair<SDValue, SDNode*> > &RecordedNodes) { 2146204642Srdivacky // Accept if it is exactly the same as a previously recorded node. 2147204642Srdivacky unsigned RecNo = MatcherTable[MatcherIndex++]; 2148204642Srdivacky assert(RecNo < RecordedNodes.size() && "Invalid CheckSame"); 2149218893Sdim return N == RecordedNodes[RecNo].first; 2150204642Srdivacky} 2151218893Sdim 2152263509Sdim/// CheckChildSame - Implements OP_CheckChildXSame. 2153263509SdimLLVM_ATTRIBUTE_ALWAYS_INLINE static bool 2154263509SdimCheckChildSame(const unsigned char *MatcherTable, unsigned &MatcherIndex, 2155263509Sdim SDValue N, 2156263509Sdim const SmallVectorImpl<std::pair<SDValue, SDNode*> > &RecordedNodes, 2157263509Sdim unsigned ChildNo) { 2158263509Sdim if (ChildNo >= N.getNumOperands()) 2159263509Sdim return false; // Match fails if out of range child #. 2160263509Sdim return ::CheckSame(MatcherTable, MatcherIndex, N.getOperand(ChildNo), 2161263509Sdim RecordedNodes); 2162263509Sdim} 2163263509Sdim 2164204642Srdivacky/// CheckPatternPredicate - Implements OP_CheckPatternPredicate. 2165218893SdimLLVM_ATTRIBUTE_ALWAYS_INLINE static bool 2166204642SrdivackyCheckPatternPredicate(const unsigned char *MatcherTable, unsigned &MatcherIndex, 2167245431Sdim const SelectionDAGISel &SDISel) { 2168204642Srdivacky return SDISel.CheckPatternPredicate(MatcherTable[MatcherIndex++]); 2169204642Srdivacky} 2170204642Srdivacky 2171204642Srdivacky/// CheckNodePredicate - Implements OP_CheckNodePredicate. 2172218893SdimLLVM_ATTRIBUTE_ALWAYS_INLINE static bool 2173204642SrdivackyCheckNodePredicate(const unsigned char *MatcherTable, unsigned &MatcherIndex, 2174245431Sdim const SelectionDAGISel &SDISel, SDNode *N) { 2175204642Srdivacky return SDISel.CheckNodePredicate(N, MatcherTable[MatcherIndex++]); 2176204642Srdivacky} 2177204642Srdivacky 2178218893SdimLLVM_ATTRIBUTE_ALWAYS_INLINE static bool 2179204642SrdivackyCheckOpcode(const unsigned char *MatcherTable, unsigned &MatcherIndex, 2180204642Srdivacky SDNode *N) { 2181206083Srdivacky uint16_t Opc = MatcherTable[MatcherIndex++]; 2182206083Srdivacky Opc |= (unsigned short)MatcherTable[MatcherIndex++] << 8; 2183206083Srdivacky return N->getOpcode() == Opc; 2184204642Srdivacky} 2185204642Srdivacky 2186218893SdimLLVM_ATTRIBUTE_ALWAYS_INLINE static bool 2187204642SrdivackyCheckType(const unsigned char *MatcherTable, unsigned &MatcherIndex, 2188263509Sdim SDValue N, const TargetLowering *TLI) { 2189204642Srdivacky MVT::SimpleValueType VT = (MVT::SimpleValueType)MatcherTable[MatcherIndex++]; 2190204642Srdivacky if (N.getValueType() == VT) return true; 2191218893Sdim 2192204642Srdivacky // Handle the case when VT is iPTR. 2193263509Sdim return VT == MVT::iPTR && N.getValueType() == TLI->getPointerTy(); 2194204642Srdivacky} 2195204642Srdivacky 2196218893SdimLLVM_ATTRIBUTE_ALWAYS_INLINE static bool 2197204642SrdivackyCheckChildType(const unsigned char *MatcherTable, unsigned &MatcherIndex, 2198263509Sdim SDValue N, const TargetLowering *TLI, 2199204642Srdivacky unsigned ChildNo) { 2200204642Srdivacky if (ChildNo >= N.getNumOperands()) 2201204642Srdivacky return false; // Match fails if out of range child #. 2202204642Srdivacky return ::CheckType(MatcherTable, MatcherIndex, N.getOperand(ChildNo), TLI); 2203204642Srdivacky} 2204204642Srdivacky 2205218893SdimLLVM_ATTRIBUTE_ALWAYS_INLINE static bool 2206204642SrdivackyCheckCondCode(const unsigned char *MatcherTable, unsigned &MatcherIndex, 2207204642Srdivacky SDValue N) { 2208204642Srdivacky return cast<CondCodeSDNode>(N)->get() == 2209204642Srdivacky (ISD::CondCode)MatcherTable[MatcherIndex++]; 2210204642Srdivacky} 2211204642Srdivacky 2212218893SdimLLVM_ATTRIBUTE_ALWAYS_INLINE static bool 2213204642SrdivackyCheckValueType(const unsigned char *MatcherTable, unsigned &MatcherIndex, 2214263509Sdim SDValue N, const TargetLowering *TLI) { 2215204642Srdivacky MVT::SimpleValueType VT = (MVT::SimpleValueType)MatcherTable[MatcherIndex++]; 2216204642Srdivacky if (cast<VTSDNode>(N)->getVT() == VT) 2217204642Srdivacky return true; 2218218893Sdim 2219204642Srdivacky // Handle the case when VT is iPTR. 2220263509Sdim return VT == MVT::iPTR && cast<VTSDNode>(N)->getVT() == TLI->getPointerTy(); 2221204642Srdivacky} 2222204642Srdivacky 2223218893SdimLLVM_ATTRIBUTE_ALWAYS_INLINE static bool 2224204642SrdivackyCheckInteger(const unsigned char *MatcherTable, unsigned &MatcherIndex, 2225204642Srdivacky SDValue N) { 2226204642Srdivacky int64_t Val = MatcherTable[MatcherIndex++]; 2227204642Srdivacky if (Val & 128) 2228204642Srdivacky Val = GetVBR(Val, MatcherTable, MatcherIndex); 2229218893Sdim 2230204642Srdivacky ConstantSDNode *C = dyn_cast<ConstantSDNode>(N); 2231204642Srdivacky return C != 0 && C->getSExtValue() == Val; 2232204642Srdivacky} 2233204642Srdivacky 2234218893SdimLLVM_ATTRIBUTE_ALWAYS_INLINE static bool 2235204642SrdivackyCheckAndImm(const unsigned char *MatcherTable, unsigned &MatcherIndex, 2236245431Sdim SDValue N, const SelectionDAGISel &SDISel) { 2237204642Srdivacky int64_t Val = MatcherTable[MatcherIndex++]; 2238204642Srdivacky if (Val & 128) 2239204642Srdivacky Val = GetVBR(Val, MatcherTable, MatcherIndex); 2240218893Sdim 2241204642Srdivacky if (N->getOpcode() != ISD::AND) return false; 2242218893Sdim 2243204642Srdivacky ConstantSDNode *C = dyn_cast<ConstantSDNode>(N->getOperand(1)); 2244204642Srdivacky return C != 0 && SDISel.CheckAndMask(N.getOperand(0), C, Val); 2245204642Srdivacky} 2246204642Srdivacky 2247218893SdimLLVM_ATTRIBUTE_ALWAYS_INLINE static bool 2248204642SrdivackyCheckOrImm(const unsigned char *MatcherTable, unsigned &MatcherIndex, 2249245431Sdim SDValue N, const SelectionDAGISel &SDISel) { 2250204642Srdivacky int64_t Val = MatcherTable[MatcherIndex++]; 2251204642Srdivacky if (Val & 128) 2252204642Srdivacky Val = GetVBR(Val, MatcherTable, MatcherIndex); 2253218893Sdim 2254204642Srdivacky if (N->getOpcode() != ISD::OR) return false; 2255218893Sdim 2256204642Srdivacky ConstantSDNode *C = dyn_cast<ConstantSDNode>(N->getOperand(1)); 2257204642Srdivacky return C != 0 && SDISel.CheckOrMask(N.getOperand(0), C, Val); 2258204642Srdivacky} 2259204642Srdivacky 2260204642Srdivacky/// IsPredicateKnownToFail - If we know how and can do so without pushing a 2261204642Srdivacky/// scope, evaluate the current node. If the current predicate is known to 2262204642Srdivacky/// fail, set Result=true and return anything. If the current predicate is 2263204642Srdivacky/// known to pass, set Result=false and return the MatcherIndex to continue 2264204642Srdivacky/// with. If the current predicate is unknown, set Result=false and return the 2265218893Sdim/// MatcherIndex to continue with. 2266204642Srdivackystatic unsigned IsPredicateKnownToFail(const unsigned char *Table, 2267204642Srdivacky unsigned Index, SDValue N, 2268245431Sdim bool &Result, 2269245431Sdim const SelectionDAGISel &SDISel, 2270218893Sdim SmallVectorImpl<std::pair<SDValue, SDNode*> > &RecordedNodes) { 2271204642Srdivacky switch (Table[Index++]) { 2272204642Srdivacky default: 2273204642Srdivacky Result = false; 2274204642Srdivacky return Index-1; // Could not evaluate this predicate. 2275204642Srdivacky case SelectionDAGISel::OPC_CheckSame: 2276204642Srdivacky Result = !::CheckSame(Table, Index, N, RecordedNodes); 2277204642Srdivacky return Index; 2278263509Sdim case SelectionDAGISel::OPC_CheckChild0Same: 2279263509Sdim case SelectionDAGISel::OPC_CheckChild1Same: 2280263509Sdim case SelectionDAGISel::OPC_CheckChild2Same: 2281263509Sdim case SelectionDAGISel::OPC_CheckChild3Same: 2282263509Sdim Result = !::CheckChildSame(Table, Index, N, RecordedNodes, 2283263509Sdim Table[Index-1] - SelectionDAGISel::OPC_CheckChild0Same); 2284263509Sdim return Index; 2285204642Srdivacky case SelectionDAGISel::OPC_CheckPatternPredicate: 2286204642Srdivacky Result = !::CheckPatternPredicate(Table, Index, SDISel); 2287204642Srdivacky return Index; 2288204642Srdivacky case SelectionDAGISel::OPC_CheckPredicate: 2289204642Srdivacky Result = !::CheckNodePredicate(Table, Index, SDISel, N.getNode()); 2290204642Srdivacky return Index; 2291204642Srdivacky case SelectionDAGISel::OPC_CheckOpcode: 2292204642Srdivacky Result = !::CheckOpcode(Table, Index, N.getNode()); 2293204642Srdivacky return Index; 2294204642Srdivacky case SelectionDAGISel::OPC_CheckType: 2295263509Sdim Result = !::CheckType(Table, Index, N, SDISel.getTargetLowering()); 2296204642Srdivacky return Index; 2297204642Srdivacky case SelectionDAGISel::OPC_CheckChild0Type: 2298204642Srdivacky case SelectionDAGISel::OPC_CheckChild1Type: 2299204642Srdivacky case SelectionDAGISel::OPC_CheckChild2Type: 2300204642Srdivacky case SelectionDAGISel::OPC_CheckChild3Type: 2301204642Srdivacky case SelectionDAGISel::OPC_CheckChild4Type: 2302204642Srdivacky case SelectionDAGISel::OPC_CheckChild5Type: 2303204642Srdivacky case SelectionDAGISel::OPC_CheckChild6Type: 2304204642Srdivacky case SelectionDAGISel::OPC_CheckChild7Type: 2305263509Sdim Result = !::CheckChildType(Table, Index, N, SDISel.getTargetLowering(), 2306204642Srdivacky Table[Index-1] - SelectionDAGISel::OPC_CheckChild0Type); 2307204642Srdivacky return Index; 2308204642Srdivacky case SelectionDAGISel::OPC_CheckCondCode: 2309204642Srdivacky Result = !::CheckCondCode(Table, Index, N); 2310204642Srdivacky return Index; 2311204642Srdivacky case SelectionDAGISel::OPC_CheckValueType: 2312263509Sdim Result = !::CheckValueType(Table, Index, N, SDISel.getTargetLowering()); 2313204642Srdivacky return Index; 2314204642Srdivacky case SelectionDAGISel::OPC_CheckInteger: 2315204642Srdivacky Result = !::CheckInteger(Table, Index, N); 2316204642Srdivacky return Index; 2317204642Srdivacky case SelectionDAGISel::OPC_CheckAndImm: 2318204642Srdivacky Result = !::CheckAndImm(Table, Index, N, SDISel); 2319204642Srdivacky return Index; 2320204642Srdivacky case SelectionDAGISel::OPC_CheckOrImm: 2321204642Srdivacky Result = !::CheckOrImm(Table, Index, N, SDISel); 2322204642Srdivacky return Index; 2323204642Srdivacky } 2324204642Srdivacky} 2325204642Srdivacky 2326207618Srdivackynamespace { 2327204642Srdivacky 2328204642Srdivackystruct MatchScope { 2329204642Srdivacky /// FailIndex - If this match fails, this is the index to continue with. 2330204642Srdivacky unsigned FailIndex; 2331218893Sdim 2332204642Srdivacky /// NodeStack - The node stack when the scope was formed. 2333204642Srdivacky SmallVector<SDValue, 4> NodeStack; 2334218893Sdim 2335204642Srdivacky /// NumRecordedNodes - The number of recorded nodes when the scope was formed. 2336204642Srdivacky unsigned NumRecordedNodes; 2337218893Sdim 2338204642Srdivacky /// NumMatchedMemRefs - The number of matched memref entries. 2339204642Srdivacky unsigned NumMatchedMemRefs; 2340204642Srdivacky 2341218893Sdim /// InputChain/InputGlue - The current chain/glue 2342218893Sdim SDValue InputChain, InputGlue; 2343218893Sdim 2344204642Srdivacky /// HasChainNodesMatched - True if the ChainNodesMatched list is non-empty. 2345218893Sdim bool HasChainNodesMatched, HasGlueResultNodesMatched; 2346204642Srdivacky}; 2347204642Srdivacky 2348207618Srdivacky} 2349207618Srdivacky 2350204642SrdivackySDNode *SelectionDAGISel:: 2351204642SrdivackySelectCodeCommon(SDNode *NodeToMatch, const unsigned char *MatcherTable, 2352204642Srdivacky unsigned TableSize) { 2353204642Srdivacky // FIXME: Should these even be selected? Handle these cases in the caller? 2354204642Srdivacky switch (NodeToMatch->getOpcode()) { 2355204642Srdivacky default: 2356204642Srdivacky break; 2357204642Srdivacky case ISD::EntryToken: // These nodes remain the same. 2358204642Srdivacky case ISD::BasicBlock: 2359204642Srdivacky case ISD::Register: 2360235633Sdim case ISD::RegisterMask: 2361205218Srdivacky //case ISD::VALUETYPE: 2362205218Srdivacky //case ISD::CONDCODE: 2363204642Srdivacky case ISD::HANDLENODE: 2364207618Srdivacky case ISD::MDNODE_SDNODE: 2365204642Srdivacky case ISD::TargetConstant: 2366204642Srdivacky case ISD::TargetConstantFP: 2367204642Srdivacky case ISD::TargetConstantPool: 2368204642Srdivacky case ISD::TargetFrameIndex: 2369204642Srdivacky case ISD::TargetExternalSymbol: 2370204642Srdivacky case ISD::TargetBlockAddress: 2371204642Srdivacky case ISD::TargetJumpTable: 2372204642Srdivacky case ISD::TargetGlobalTLSAddress: 2373204642Srdivacky case ISD::TargetGlobalAddress: 2374204642Srdivacky case ISD::TokenFactor: 2375204642Srdivacky case ISD::CopyFromReg: 2376204642Srdivacky case ISD::CopyToReg: 2377205218Srdivacky case ISD::EH_LABEL: 2378245431Sdim case ISD::LIFETIME_START: 2379245431Sdim case ISD::LIFETIME_END: 2380204642Srdivacky NodeToMatch->setNodeId(-1); // Mark selected. 2381204642Srdivacky return 0; 2382204642Srdivacky case ISD::AssertSext: 2383204642Srdivacky case ISD::AssertZext: 2384204642Srdivacky CurDAG->ReplaceAllUsesOfValueWith(SDValue(NodeToMatch, 0), 2385204642Srdivacky NodeToMatch->getOperand(0)); 2386204642Srdivacky return 0; 2387204642Srdivacky case ISD::INLINEASM: return Select_INLINEASM(NodeToMatch); 2388204642Srdivacky case ISD::UNDEF: return Select_UNDEF(NodeToMatch); 2389204642Srdivacky } 2390218893Sdim 2391204642Srdivacky assert(!NodeToMatch->isMachineOpcode() && "Node already selected!"); 2392204642Srdivacky 2393204642Srdivacky // Set up the node stack with NodeToMatch as the only node on the stack. 2394204642Srdivacky SmallVector<SDValue, 8> NodeStack; 2395204642Srdivacky SDValue N = SDValue(NodeToMatch, 0); 2396204642Srdivacky NodeStack.push_back(N); 2397204642Srdivacky 2398204642Srdivacky // MatchScopes - Scopes used when matching, if a match failure happens, this 2399204642Srdivacky // indicates where to continue checking. 2400204642Srdivacky SmallVector<MatchScope, 8> MatchScopes; 2401218893Sdim 2402204642Srdivacky // RecordedNodes - This is the set of nodes that have been recorded by the 2403218893Sdim // state machine. The second value is the parent of the node, or null if the 2404218893Sdim // root is recorded. 2405218893Sdim SmallVector<std::pair<SDValue, SDNode*>, 8> RecordedNodes; 2406218893Sdim 2407204642Srdivacky // MatchedMemRefs - This is the set of MemRef's we've seen in the input 2408204642Srdivacky // pattern. 2409204642Srdivacky SmallVector<MachineMemOperand*, 2> MatchedMemRefs; 2410218893Sdim 2411218893Sdim // These are the current input chain and glue for use when generating nodes. 2412204642Srdivacky // Various Emit operations change these. For example, emitting a copytoreg 2413204642Srdivacky // uses and updates these. 2414218893Sdim SDValue InputChain, InputGlue; 2415218893Sdim 2416204642Srdivacky // ChainNodesMatched - If a pattern matches nodes that have input/output 2417204642Srdivacky // chains, the OPC_EmitMergeInputChains operation is emitted which indicates 2418204642Srdivacky // which ones they are. The result is captured into this list so that we can 2419204642Srdivacky // update the chain results when the pattern is complete. 2420204642Srdivacky SmallVector<SDNode*, 3> ChainNodesMatched; 2421218893Sdim SmallVector<SDNode*, 3> GlueResultNodesMatched; 2422218893Sdim 2423252723Sdim DEBUG(dbgs() << "ISEL: Starting pattern match on root node: "; 2424204642Srdivacky NodeToMatch->dump(CurDAG); 2425252723Sdim dbgs() << '\n'); 2426218893Sdim 2427204642Srdivacky // Determine where to start the interpreter. Normally we start at opcode #0, 2428204642Srdivacky // but if the state machine starts with an OPC_SwitchOpcode, then we 2429204642Srdivacky // accelerate the first lookup (which is guaranteed to be hot) with the 2430204642Srdivacky // OpcodeOffset table. 2431204642Srdivacky unsigned MatcherIndex = 0; 2432218893Sdim 2433204642Srdivacky if (!OpcodeOffset.empty()) { 2434204642Srdivacky // Already computed the OpcodeOffset table, just index into it. 2435204642Srdivacky if (N.getOpcode() < OpcodeOffset.size()) 2436204642Srdivacky MatcherIndex = OpcodeOffset[N.getOpcode()]; 2437252723Sdim DEBUG(dbgs() << " Initial Opcode index to " << MatcherIndex << "\n"); 2438204642Srdivacky 2439204642Srdivacky } else if (MatcherTable[0] == OPC_SwitchOpcode) { 2440204642Srdivacky // Otherwise, the table isn't computed, but the state machine does start 2441204642Srdivacky // with an OPC_SwitchOpcode instruction. Populate the table now, since this 2442204642Srdivacky // is the first time we're selecting an instruction. 2443204642Srdivacky unsigned Idx = 1; 2444204642Srdivacky while (1) { 2445204642Srdivacky // Get the size of this case. 2446204642Srdivacky unsigned CaseSize = MatcherTable[Idx++]; 2447204642Srdivacky if (CaseSize & 128) 2448204642Srdivacky CaseSize = GetVBR(CaseSize, MatcherTable, Idx); 2449204642Srdivacky if (CaseSize == 0) break; 2450204642Srdivacky 2451204642Srdivacky // Get the opcode, add the index to the table. 2452206083Srdivacky uint16_t Opc = MatcherTable[Idx++]; 2453206083Srdivacky Opc |= (unsigned short)MatcherTable[Idx++] << 8; 2454204642Srdivacky if (Opc >= OpcodeOffset.size()) 2455204642Srdivacky OpcodeOffset.resize((Opc+1)*2); 2456204642Srdivacky OpcodeOffset[Opc] = Idx; 2457204642Srdivacky Idx += CaseSize; 2458204642Srdivacky } 2459204642Srdivacky 2460204642Srdivacky // Okay, do the lookup for the first opcode. 2461204642Srdivacky if (N.getOpcode() < OpcodeOffset.size()) 2462204642Srdivacky MatcherIndex = OpcodeOffset[N.getOpcode()]; 2463204642Srdivacky } 2464218893Sdim 2465204642Srdivacky while (1) { 2466204642Srdivacky assert(MatcherIndex < TableSize && "Invalid index"); 2467204961Srdivacky#ifndef NDEBUG 2468204961Srdivacky unsigned CurrentOpcodeIndex = MatcherIndex; 2469204961Srdivacky#endif 2470204642Srdivacky BuiltinOpcodes Opcode = (BuiltinOpcodes)MatcherTable[MatcherIndex++]; 2471204642Srdivacky switch (Opcode) { 2472204642Srdivacky case OPC_Scope: { 2473204642Srdivacky // Okay, the semantics of this operation are that we should push a scope 2474204642Srdivacky // then evaluate the first child. However, pushing a scope only to have 2475204642Srdivacky // the first check fail (which then pops it) is inefficient. If we can 2476204642Srdivacky // determine immediately that the first check (or first several) will 2477204642Srdivacky // immediately fail, don't even bother pushing a scope for them. 2478204642Srdivacky unsigned FailIndex; 2479218893Sdim 2480204642Srdivacky while (1) { 2481204642Srdivacky unsigned NumToSkip = MatcherTable[MatcherIndex++]; 2482204642Srdivacky if (NumToSkip & 128) 2483204642Srdivacky NumToSkip = GetVBR(NumToSkip, MatcherTable, MatcherIndex); 2484204642Srdivacky // Found the end of the scope with no match. 2485204642Srdivacky if (NumToSkip == 0) { 2486204642Srdivacky FailIndex = 0; 2487204642Srdivacky break; 2488204642Srdivacky } 2489218893Sdim 2490204642Srdivacky FailIndex = MatcherIndex+NumToSkip; 2491218893Sdim 2492206083Srdivacky unsigned MatcherIndexOfPredicate = MatcherIndex; 2493206083Srdivacky (void)MatcherIndexOfPredicate; // silence warning. 2494218893Sdim 2495204642Srdivacky // If we can't evaluate this predicate without pushing a scope (e.g. if 2496204642Srdivacky // it is a 'MoveParent') or if the predicate succeeds on this node, we 2497204642Srdivacky // push the scope and evaluate the full predicate chain. 2498204642Srdivacky bool Result; 2499204642Srdivacky MatcherIndex = IsPredicateKnownToFail(MatcherTable, MatcherIndex, N, 2500204642Srdivacky Result, *this, RecordedNodes); 2501204642Srdivacky if (!Result) 2502204642Srdivacky break; 2503218893Sdim 2504252723Sdim DEBUG(dbgs() << " Skipped scope entry (due to false predicate) at " 2505206083Srdivacky << "index " << MatcherIndexOfPredicate 2506206083Srdivacky << ", continuing at " << FailIndex << "\n"); 2507206083Srdivacky ++NumDAGIselRetries; 2508218893Sdim 2509204642Srdivacky // Otherwise, we know that this case of the Scope is guaranteed to fail, 2510204642Srdivacky // move to the next case. 2511204642Srdivacky MatcherIndex = FailIndex; 2512204642Srdivacky } 2513218893Sdim 2514204642Srdivacky // If the whole scope failed to match, bail. 2515204642Srdivacky if (FailIndex == 0) break; 2516218893Sdim 2517204642Srdivacky // Push a MatchScope which indicates where to go if the first child fails 2518204642Srdivacky // to match. 2519204642Srdivacky MatchScope NewEntry; 2520204642Srdivacky NewEntry.FailIndex = FailIndex; 2521204642Srdivacky NewEntry.NodeStack.append(NodeStack.begin(), NodeStack.end()); 2522204642Srdivacky NewEntry.NumRecordedNodes = RecordedNodes.size(); 2523204642Srdivacky NewEntry.NumMatchedMemRefs = MatchedMemRefs.size(); 2524204642Srdivacky NewEntry.InputChain = InputChain; 2525218893Sdim NewEntry.InputGlue = InputGlue; 2526204642Srdivacky NewEntry.HasChainNodesMatched = !ChainNodesMatched.empty(); 2527218893Sdim NewEntry.HasGlueResultNodesMatched = !GlueResultNodesMatched.empty(); 2528204642Srdivacky MatchScopes.push_back(NewEntry); 2529204642Srdivacky continue; 2530204642Srdivacky } 2531218893Sdim case OPC_RecordNode: { 2532204642Srdivacky // Remember this node, it may end up being an operand in the pattern. 2533218893Sdim SDNode *Parent = 0; 2534218893Sdim if (NodeStack.size() > 1) 2535218893Sdim Parent = NodeStack[NodeStack.size()-2].getNode(); 2536218893Sdim RecordedNodes.push_back(std::make_pair(N, Parent)); 2537204642Srdivacky continue; 2538218893Sdim } 2539218893Sdim 2540204642Srdivacky case OPC_RecordChild0: case OPC_RecordChild1: 2541204642Srdivacky case OPC_RecordChild2: case OPC_RecordChild3: 2542204642Srdivacky case OPC_RecordChild4: case OPC_RecordChild5: 2543204642Srdivacky case OPC_RecordChild6: case OPC_RecordChild7: { 2544204642Srdivacky unsigned ChildNo = Opcode-OPC_RecordChild0; 2545204642Srdivacky if (ChildNo >= N.getNumOperands()) 2546204642Srdivacky break; // Match fails if out of range child #. 2547204642Srdivacky 2548218893Sdim RecordedNodes.push_back(std::make_pair(N->getOperand(ChildNo), 2549218893Sdim N.getNode())); 2550204642Srdivacky continue; 2551204642Srdivacky } 2552204642Srdivacky case OPC_RecordMemRef: 2553204642Srdivacky MatchedMemRefs.push_back(cast<MemSDNode>(N)->getMemOperand()); 2554204642Srdivacky continue; 2555218893Sdim 2556218893Sdim case OPC_CaptureGlueInput: 2557218893Sdim // If the current node has an input glue, capture it in InputGlue. 2558204642Srdivacky if (N->getNumOperands() != 0 && 2559218893Sdim N->getOperand(N->getNumOperands()-1).getValueType() == MVT::Glue) 2560218893Sdim InputGlue = N->getOperand(N->getNumOperands()-1); 2561204642Srdivacky continue; 2562218893Sdim 2563204642Srdivacky case OPC_MoveChild: { 2564204642Srdivacky unsigned ChildNo = MatcherTable[MatcherIndex++]; 2565204642Srdivacky if (ChildNo >= N.getNumOperands()) 2566204642Srdivacky break; // Match fails if out of range child #. 2567204642Srdivacky N = N.getOperand(ChildNo); 2568204642Srdivacky NodeStack.push_back(N); 2569204642Srdivacky continue; 2570204642Srdivacky } 2571218893Sdim 2572204642Srdivacky case OPC_MoveParent: 2573204642Srdivacky // Pop the current node off the NodeStack. 2574204642Srdivacky NodeStack.pop_back(); 2575204642Srdivacky assert(!NodeStack.empty() && "Node stack imbalance!"); 2576218893Sdim N = NodeStack.back(); 2577204642Srdivacky continue; 2578218893Sdim 2579204642Srdivacky case OPC_CheckSame: 2580204642Srdivacky if (!::CheckSame(MatcherTable, MatcherIndex, N, RecordedNodes)) break; 2581204642Srdivacky continue; 2582263509Sdim 2583263509Sdim case OPC_CheckChild0Same: case OPC_CheckChild1Same: 2584263509Sdim case OPC_CheckChild2Same: case OPC_CheckChild3Same: 2585263509Sdim if (!::CheckChildSame(MatcherTable, MatcherIndex, N, RecordedNodes, 2586263509Sdim Opcode-OPC_CheckChild0Same)) 2587263509Sdim break; 2588263509Sdim continue; 2589263509Sdim 2590204642Srdivacky case OPC_CheckPatternPredicate: 2591204642Srdivacky if (!::CheckPatternPredicate(MatcherTable, MatcherIndex, *this)) break; 2592204642Srdivacky continue; 2593204642Srdivacky case OPC_CheckPredicate: 2594204642Srdivacky if (!::CheckNodePredicate(MatcherTable, MatcherIndex, *this, 2595204642Srdivacky N.getNode())) 2596204642Srdivacky break; 2597204642Srdivacky continue; 2598204792Srdivacky case OPC_CheckComplexPat: { 2599204792Srdivacky unsigned CPNum = MatcherTable[MatcherIndex++]; 2600204792Srdivacky unsigned RecNo = MatcherTable[MatcherIndex++]; 2601204792Srdivacky assert(RecNo < RecordedNodes.size() && "Invalid CheckComplexPat"); 2602218893Sdim if (!CheckComplexPattern(NodeToMatch, RecordedNodes[RecNo].second, 2603218893Sdim RecordedNodes[RecNo].first, CPNum, 2604204792Srdivacky RecordedNodes)) 2605204642Srdivacky break; 2606204642Srdivacky continue; 2607204792Srdivacky } 2608204642Srdivacky case OPC_CheckOpcode: 2609204642Srdivacky if (!::CheckOpcode(MatcherTable, MatcherIndex, N.getNode())) break; 2610204642Srdivacky continue; 2611218893Sdim 2612204642Srdivacky case OPC_CheckType: 2613263509Sdim if (!::CheckType(MatcherTable, MatcherIndex, N, getTargetLowering())) 2614263509Sdim break; 2615204642Srdivacky continue; 2616218893Sdim 2617204642Srdivacky case OPC_SwitchOpcode: { 2618204642Srdivacky unsigned CurNodeOpcode = N.getOpcode(); 2619204642Srdivacky unsigned SwitchStart = MatcherIndex-1; (void)SwitchStart; 2620204642Srdivacky unsigned CaseSize; 2621204642Srdivacky while (1) { 2622204642Srdivacky // Get the size of this case. 2623204642Srdivacky CaseSize = MatcherTable[MatcherIndex++]; 2624204642Srdivacky if (CaseSize & 128) 2625204642Srdivacky CaseSize = GetVBR(CaseSize, MatcherTable, MatcherIndex); 2626204642Srdivacky if (CaseSize == 0) break; 2627204642Srdivacky 2628206083Srdivacky uint16_t Opc = MatcherTable[MatcherIndex++]; 2629206083Srdivacky Opc |= (unsigned short)MatcherTable[MatcherIndex++] << 8; 2630206083Srdivacky 2631204642Srdivacky // If the opcode matches, then we will execute this case. 2632206083Srdivacky if (CurNodeOpcode == Opc) 2633204642Srdivacky break; 2634218893Sdim 2635204642Srdivacky // Otherwise, skip over this case. 2636204642Srdivacky MatcherIndex += CaseSize; 2637204642Srdivacky } 2638218893Sdim 2639204642Srdivacky // If no cases matched, bail out. 2640204642Srdivacky if (CaseSize == 0) break; 2641218893Sdim 2642204642Srdivacky // Otherwise, execute the case we found. 2643252723Sdim DEBUG(dbgs() << " OpcodeSwitch from " << SwitchStart 2644204642Srdivacky << " to " << MatcherIndex << "\n"); 2645204642Srdivacky continue; 2646204642Srdivacky } 2647218893Sdim 2648204642Srdivacky case OPC_SwitchType: { 2649263509Sdim MVT CurNodeVT = N.getSimpleValueType(); 2650204642Srdivacky unsigned SwitchStart = MatcherIndex-1; (void)SwitchStart; 2651204642Srdivacky unsigned CaseSize; 2652204642Srdivacky while (1) { 2653204642Srdivacky // Get the size of this case. 2654204642Srdivacky CaseSize = MatcherTable[MatcherIndex++]; 2655204642Srdivacky if (CaseSize & 128) 2656204642Srdivacky CaseSize = GetVBR(CaseSize, MatcherTable, MatcherIndex); 2657204642Srdivacky if (CaseSize == 0) break; 2658218893Sdim 2659218893Sdim MVT CaseVT = (MVT::SimpleValueType)MatcherTable[MatcherIndex++]; 2660204642Srdivacky if (CaseVT == MVT::iPTR) 2661263509Sdim CaseVT = getTargetLowering()->getPointerTy(); 2662218893Sdim 2663204642Srdivacky // If the VT matches, then we will execute this case. 2664204642Srdivacky if (CurNodeVT == CaseVT) 2665204642Srdivacky break; 2666218893Sdim 2667204642Srdivacky // Otherwise, skip over this case. 2668204642Srdivacky MatcherIndex += CaseSize; 2669204642Srdivacky } 2670218893Sdim 2671204642Srdivacky // If no cases matched, bail out. 2672204642Srdivacky if (CaseSize == 0) break; 2673218893Sdim 2674204642Srdivacky // Otherwise, execute the case we found. 2675252723Sdim DEBUG(dbgs() << " TypeSwitch[" << EVT(CurNodeVT).getEVTString() 2676204642Srdivacky << "] from " << SwitchStart << " to " << MatcherIndex<<'\n'); 2677204642Srdivacky continue; 2678204642Srdivacky } 2679204642Srdivacky case OPC_CheckChild0Type: case OPC_CheckChild1Type: 2680204642Srdivacky case OPC_CheckChild2Type: case OPC_CheckChild3Type: 2681204642Srdivacky case OPC_CheckChild4Type: case OPC_CheckChild5Type: 2682204642Srdivacky case OPC_CheckChild6Type: case OPC_CheckChild7Type: 2683263509Sdim if (!::CheckChildType(MatcherTable, MatcherIndex, N, getTargetLowering(), 2684204642Srdivacky Opcode-OPC_CheckChild0Type)) 2685204642Srdivacky break; 2686204642Srdivacky continue; 2687204642Srdivacky case OPC_CheckCondCode: 2688204642Srdivacky if (!::CheckCondCode(MatcherTable, MatcherIndex, N)) break; 2689204642Srdivacky continue; 2690204642Srdivacky case OPC_CheckValueType: 2691263509Sdim if (!::CheckValueType(MatcherTable, MatcherIndex, N, getTargetLowering())) 2692263509Sdim break; 2693204642Srdivacky continue; 2694204642Srdivacky case OPC_CheckInteger: 2695204642Srdivacky if (!::CheckInteger(MatcherTable, MatcherIndex, N)) break; 2696204642Srdivacky continue; 2697204642Srdivacky case OPC_CheckAndImm: 2698204642Srdivacky if (!::CheckAndImm(MatcherTable, MatcherIndex, N, *this)) break; 2699204642Srdivacky continue; 2700204642Srdivacky case OPC_CheckOrImm: 2701204642Srdivacky if (!::CheckOrImm(MatcherTable, MatcherIndex, N, *this)) break; 2702204642Srdivacky continue; 2703218893Sdim 2704204642Srdivacky case OPC_CheckFoldableChainNode: { 2705204642Srdivacky assert(NodeStack.size() != 1 && "No parent node"); 2706204642Srdivacky // Verify that all intermediate nodes between the root and this one have 2707204642Srdivacky // a single use. 2708204642Srdivacky bool HasMultipleUses = false; 2709204642Srdivacky for (unsigned i = 1, e = NodeStack.size()-1; i != e; ++i) 2710204642Srdivacky if (!NodeStack[i].hasOneUse()) { 2711204642Srdivacky HasMultipleUses = true; 2712204642Srdivacky break; 2713204642Srdivacky } 2714204642Srdivacky if (HasMultipleUses) break; 2715204642Srdivacky 2716204642Srdivacky // Check to see that the target thinks this is profitable to fold and that 2717204642Srdivacky // we can fold it without inducing cycles in the graph. 2718204642Srdivacky if (!IsProfitableToFold(N, NodeStack[NodeStack.size()-2].getNode(), 2719204642Srdivacky NodeToMatch) || 2720204642Srdivacky !IsLegalToFold(N, NodeStack[NodeStack.size()-2].getNode(), 2721207618Srdivacky NodeToMatch, OptLevel, 2722207618Srdivacky true/*We validate our own chains*/)) 2723204642Srdivacky break; 2724218893Sdim 2725204642Srdivacky continue; 2726204642Srdivacky } 2727204642Srdivacky case OPC_EmitInteger: { 2728204642Srdivacky MVT::SimpleValueType VT = 2729204642Srdivacky (MVT::SimpleValueType)MatcherTable[MatcherIndex++]; 2730204642Srdivacky int64_t Val = MatcherTable[MatcherIndex++]; 2731204642Srdivacky if (Val & 128) 2732204642Srdivacky Val = GetVBR(Val, MatcherTable, MatcherIndex); 2733218893Sdim RecordedNodes.push_back(std::pair<SDValue, SDNode*>( 2734218893Sdim CurDAG->getTargetConstant(Val, VT), (SDNode*)0)); 2735204642Srdivacky continue; 2736204642Srdivacky } 2737204642Srdivacky case OPC_EmitRegister: { 2738204642Srdivacky MVT::SimpleValueType VT = 2739204642Srdivacky (MVT::SimpleValueType)MatcherTable[MatcherIndex++]; 2740204642Srdivacky unsigned RegNo = MatcherTable[MatcherIndex++]; 2741218893Sdim RecordedNodes.push_back(std::pair<SDValue, SDNode*>( 2742218893Sdim CurDAG->getRegister(RegNo, VT), (SDNode*)0)); 2743204642Srdivacky continue; 2744204642Srdivacky } 2745221345Sdim case OPC_EmitRegister2: { 2746221345Sdim // For targets w/ more than 256 register names, the register enum 2747221345Sdim // values are stored in two bytes in the matcher table (just like 2748221345Sdim // opcodes). 2749221345Sdim MVT::SimpleValueType VT = 2750221345Sdim (MVT::SimpleValueType)MatcherTable[MatcherIndex++]; 2751221345Sdim unsigned RegNo = MatcherTable[MatcherIndex++]; 2752221345Sdim RegNo |= MatcherTable[MatcherIndex++] << 8; 2753221345Sdim RecordedNodes.push_back(std::pair<SDValue, SDNode*>( 2754221345Sdim CurDAG->getRegister(RegNo, VT), (SDNode*)0)); 2755221345Sdim continue; 2756221345Sdim } 2757218893Sdim 2758204642Srdivacky case OPC_EmitConvertToTarget: { 2759204642Srdivacky // Convert from IMM/FPIMM to target version. 2760204642Srdivacky unsigned RecNo = MatcherTable[MatcherIndex++]; 2761263509Sdim assert(RecNo < RecordedNodes.size() && "Invalid EmitConvertToTarget"); 2762218893Sdim SDValue Imm = RecordedNodes[RecNo].first; 2763204642Srdivacky 2764204642Srdivacky if (Imm->getOpcode() == ISD::Constant) { 2765252723Sdim const ConstantInt *Val=cast<ConstantSDNode>(Imm)->getConstantIntValue(); 2766252723Sdim Imm = CurDAG->getConstant(*Val, Imm.getValueType(), true); 2767204642Srdivacky } else if (Imm->getOpcode() == ISD::ConstantFP) { 2768204642Srdivacky const ConstantFP *Val=cast<ConstantFPSDNode>(Imm)->getConstantFPValue(); 2769252723Sdim Imm = CurDAG->getConstantFP(*Val, Imm.getValueType(), true); 2770204642Srdivacky } 2771218893Sdim 2772218893Sdim RecordedNodes.push_back(std::make_pair(Imm, RecordedNodes[RecNo].second)); 2773204642Srdivacky continue; 2774204642Srdivacky } 2775218893Sdim 2776206083Srdivacky case OPC_EmitMergeInputChains1_0: // OPC_EmitMergeInputChains, 1, 0 2777206083Srdivacky case OPC_EmitMergeInputChains1_1: { // OPC_EmitMergeInputChains, 1, 1 2778206083Srdivacky // These are space-optimized forms of OPC_EmitMergeInputChains. 2779206083Srdivacky assert(InputChain.getNode() == 0 && 2780206083Srdivacky "EmitMergeInputChains should be the first chain producing node"); 2781206083Srdivacky assert(ChainNodesMatched.empty() && 2782206083Srdivacky "Should only have one EmitMergeInputChains per match"); 2783218893Sdim 2784206083Srdivacky // Read all of the chained nodes. 2785206083Srdivacky unsigned RecNo = Opcode == OPC_EmitMergeInputChains1_1; 2786263509Sdim assert(RecNo < RecordedNodes.size() && "Invalid EmitMergeInputChains"); 2787218893Sdim ChainNodesMatched.push_back(RecordedNodes[RecNo].first.getNode()); 2788218893Sdim 2789206083Srdivacky // FIXME: What if other value results of the node have uses not matched 2790206083Srdivacky // by this pattern? 2791206083Srdivacky if (ChainNodesMatched.back() != NodeToMatch && 2792218893Sdim !RecordedNodes[RecNo].first.hasOneUse()) { 2793206083Srdivacky ChainNodesMatched.clear(); 2794206083Srdivacky break; 2795206083Srdivacky } 2796218893Sdim 2797206083Srdivacky // Merge the input chains if they are not intra-pattern references. 2798206083Srdivacky InputChain = HandleMergeInputChains(ChainNodesMatched, CurDAG); 2799218893Sdim 2800206083Srdivacky if (InputChain.getNode() == 0) 2801206083Srdivacky break; // Failed to merge. 2802206083Srdivacky continue; 2803206083Srdivacky } 2804218893Sdim 2805204642Srdivacky case OPC_EmitMergeInputChains: { 2806204642Srdivacky assert(InputChain.getNode() == 0 && 2807204642Srdivacky "EmitMergeInputChains should be the first chain producing node"); 2808204642Srdivacky // This node gets a list of nodes we matched in the input that have 2809204642Srdivacky // chains. We want to token factor all of the input chains to these nodes 2810204642Srdivacky // together. However, if any of the input chains is actually one of the 2811204642Srdivacky // nodes matched in this pattern, then we have an intra-match reference. 2812204642Srdivacky // Ignore these because the newly token factored chain should not refer to 2813204642Srdivacky // the old nodes. 2814204642Srdivacky unsigned NumChains = MatcherTable[MatcherIndex++]; 2815204642Srdivacky assert(NumChains != 0 && "Can't TF zero chains"); 2816204642Srdivacky 2817204642Srdivacky assert(ChainNodesMatched.empty() && 2818204642Srdivacky "Should only have one EmitMergeInputChains per match"); 2819204642Srdivacky 2820204642Srdivacky // Read all of the chained nodes. 2821204642Srdivacky for (unsigned i = 0; i != NumChains; ++i) { 2822204642Srdivacky unsigned RecNo = MatcherTable[MatcherIndex++]; 2823263509Sdim assert(RecNo < RecordedNodes.size() && "Invalid EmitMergeInputChains"); 2824218893Sdim ChainNodesMatched.push_back(RecordedNodes[RecNo].first.getNode()); 2825218893Sdim 2826204642Srdivacky // FIXME: What if other value results of the node have uses not matched 2827204642Srdivacky // by this pattern? 2828204642Srdivacky if (ChainNodesMatched.back() != NodeToMatch && 2829218893Sdim !RecordedNodes[RecNo].first.hasOneUse()) { 2830204642Srdivacky ChainNodesMatched.clear(); 2831204642Srdivacky break; 2832204642Srdivacky } 2833204642Srdivacky } 2834218893Sdim 2835204642Srdivacky // If the inner loop broke out, the match fails. 2836204642Srdivacky if (ChainNodesMatched.empty()) 2837204642Srdivacky break; 2838204642Srdivacky 2839204642Srdivacky // Merge the input chains if they are not intra-pattern references. 2840204642Srdivacky InputChain = HandleMergeInputChains(ChainNodesMatched, CurDAG); 2841218893Sdim 2842204642Srdivacky if (InputChain.getNode() == 0) 2843204642Srdivacky break; // Failed to merge. 2844204642Srdivacky 2845204642Srdivacky continue; 2846204642Srdivacky } 2847218893Sdim 2848204642Srdivacky case OPC_EmitCopyToReg: { 2849204642Srdivacky unsigned RecNo = MatcherTable[MatcherIndex++]; 2850263509Sdim assert(RecNo < RecordedNodes.size() && "Invalid EmitCopyToReg"); 2851204642Srdivacky unsigned DestPhysReg = MatcherTable[MatcherIndex++]; 2852218893Sdim 2853204642Srdivacky if (InputChain.getNode() == 0) 2854204642Srdivacky InputChain = CurDAG->getEntryNode(); 2855218893Sdim 2856263509Sdim InputChain = CurDAG->getCopyToReg(InputChain, SDLoc(NodeToMatch), 2857218893Sdim DestPhysReg, RecordedNodes[RecNo].first, 2858218893Sdim InputGlue); 2859218893Sdim 2860218893Sdim InputGlue = InputChain.getValue(1); 2861204642Srdivacky continue; 2862204642Srdivacky } 2863218893Sdim 2864204642Srdivacky case OPC_EmitNodeXForm: { 2865204642Srdivacky unsigned XFormNo = MatcherTable[MatcherIndex++]; 2866204642Srdivacky unsigned RecNo = MatcherTable[MatcherIndex++]; 2867263509Sdim assert(RecNo < RecordedNodes.size() && "Invalid EmitNodeXForm"); 2868218893Sdim SDValue Res = RunSDNodeXForm(RecordedNodes[RecNo].first, XFormNo); 2869218893Sdim RecordedNodes.push_back(std::pair<SDValue,SDNode*>(Res, (SDNode*) 0)); 2870204642Srdivacky continue; 2871204642Srdivacky } 2872218893Sdim 2873204642Srdivacky case OPC_EmitNode: 2874204642Srdivacky case OPC_MorphNodeTo: { 2875204642Srdivacky uint16_t TargetOpc = MatcherTable[MatcherIndex++]; 2876204642Srdivacky TargetOpc |= (unsigned short)MatcherTable[MatcherIndex++] << 8; 2877204642Srdivacky unsigned EmitNodeInfo = MatcherTable[MatcherIndex++]; 2878204642Srdivacky // Get the result VT list. 2879204642Srdivacky unsigned NumVTs = MatcherTable[MatcherIndex++]; 2880204642Srdivacky SmallVector<EVT, 4> VTs; 2881204642Srdivacky for (unsigned i = 0; i != NumVTs; ++i) { 2882204642Srdivacky MVT::SimpleValueType VT = 2883204642Srdivacky (MVT::SimpleValueType)MatcherTable[MatcherIndex++]; 2884263509Sdim if (VT == MVT::iPTR) VT = getTargetLowering()->getPointerTy().SimpleTy; 2885204642Srdivacky VTs.push_back(VT); 2886204642Srdivacky } 2887218893Sdim 2888204642Srdivacky if (EmitNodeInfo & OPFL_Chain) 2889204642Srdivacky VTs.push_back(MVT::Other); 2890218893Sdim if (EmitNodeInfo & OPFL_GlueOutput) 2891218893Sdim VTs.push_back(MVT::Glue); 2892218893Sdim 2893204642Srdivacky // This is hot code, so optimize the two most common cases of 1 and 2 2894204642Srdivacky // results. 2895204642Srdivacky SDVTList VTList; 2896204642Srdivacky if (VTs.size() == 1) 2897204642Srdivacky VTList = CurDAG->getVTList(VTs[0]); 2898204642Srdivacky else if (VTs.size() == 2) 2899204642Srdivacky VTList = CurDAG->getVTList(VTs[0], VTs[1]); 2900204642Srdivacky else 2901204642Srdivacky VTList = CurDAG->getVTList(VTs.data(), VTs.size()); 2902204642Srdivacky 2903204642Srdivacky // Get the operand list. 2904204642Srdivacky unsigned NumOps = MatcherTable[MatcherIndex++]; 2905204642Srdivacky SmallVector<SDValue, 8> Ops; 2906204642Srdivacky for (unsigned i = 0; i != NumOps; ++i) { 2907204642Srdivacky unsigned RecNo = MatcherTable[MatcherIndex++]; 2908204642Srdivacky if (RecNo & 128) 2909204642Srdivacky RecNo = GetVBR(RecNo, MatcherTable, MatcherIndex); 2910218893Sdim 2911204642Srdivacky assert(RecNo < RecordedNodes.size() && "Invalid EmitNode"); 2912218893Sdim Ops.push_back(RecordedNodes[RecNo].first); 2913204642Srdivacky } 2914218893Sdim 2915204642Srdivacky // If there are variadic operands to add, handle them now. 2916204642Srdivacky if (EmitNodeInfo & OPFL_VariadicInfo) { 2917204642Srdivacky // Determine the start index to copy from. 2918204642Srdivacky unsigned FirstOpToCopy = getNumFixedFromVariadicInfo(EmitNodeInfo); 2919204642Srdivacky FirstOpToCopy += (EmitNodeInfo & OPFL_Chain) ? 1 : 0; 2920204642Srdivacky assert(NodeToMatch->getNumOperands() >= FirstOpToCopy && 2921204642Srdivacky "Invalid variadic node"); 2922218893Sdim // Copy all of the variadic operands, not including a potential glue 2923204642Srdivacky // input. 2924204642Srdivacky for (unsigned i = FirstOpToCopy, e = NodeToMatch->getNumOperands(); 2925204642Srdivacky i != e; ++i) { 2926204642Srdivacky SDValue V = NodeToMatch->getOperand(i); 2927218893Sdim if (V.getValueType() == MVT::Glue) break; 2928204642Srdivacky Ops.push_back(V); 2929204642Srdivacky } 2930204642Srdivacky } 2931218893Sdim 2932218893Sdim // If this has chain/glue inputs, add them. 2933204642Srdivacky if (EmitNodeInfo & OPFL_Chain) 2934204642Srdivacky Ops.push_back(InputChain); 2935218893Sdim if ((EmitNodeInfo & OPFL_GlueInput) && InputGlue.getNode() != 0) 2936218893Sdim Ops.push_back(InputGlue); 2937218893Sdim 2938204642Srdivacky // Create the node. 2939204642Srdivacky SDNode *Res = 0; 2940204642Srdivacky if (Opcode != OPC_MorphNodeTo) { 2941204642Srdivacky // If this is a normal EmitNode command, just create the new node and 2942204642Srdivacky // add the results to the RecordedNodes list. 2943263509Sdim Res = CurDAG->getMachineNode(TargetOpc, SDLoc(NodeToMatch), 2944252723Sdim VTList, Ops); 2945218893Sdim 2946218893Sdim // Add all the non-glue/non-chain results to the RecordedNodes list. 2947204642Srdivacky for (unsigned i = 0, e = VTs.size(); i != e; ++i) { 2948218893Sdim if (VTs[i] == MVT::Other || VTs[i] == MVT::Glue) break; 2949218893Sdim RecordedNodes.push_back(std::pair<SDValue,SDNode*>(SDValue(Res, i), 2950218893Sdim (SDNode*) 0)); 2951204642Srdivacky } 2952218893Sdim 2953245431Sdim } else if (NodeToMatch->getOpcode() != ISD::DELETED_NODE) { 2954204642Srdivacky Res = MorphNode(NodeToMatch, TargetOpc, VTList, Ops.data(), Ops.size(), 2955204642Srdivacky EmitNodeInfo); 2956245431Sdim } else { 2957245431Sdim // NodeToMatch was eliminated by CSE when the target changed the DAG. 2958245431Sdim // We will visit the equivalent node later. 2959245431Sdim DEBUG(dbgs() << "Node was eliminated by CSE\n"); 2960245431Sdim return 0; 2961204642Srdivacky } 2962218893Sdim 2963218893Sdim // If the node had chain/glue results, update our notion of the current 2964218893Sdim // chain and glue. 2965218893Sdim if (EmitNodeInfo & OPFL_GlueOutput) { 2966218893Sdim InputGlue = SDValue(Res, VTs.size()-1); 2967204642Srdivacky if (EmitNodeInfo & OPFL_Chain) 2968204642Srdivacky InputChain = SDValue(Res, VTs.size()-2); 2969204642Srdivacky } else if (EmitNodeInfo & OPFL_Chain) 2970204642Srdivacky InputChain = SDValue(Res, VTs.size()-1); 2971204642Srdivacky 2972218893Sdim // If the OPFL_MemRefs glue is set on this node, slap all of the 2973204642Srdivacky // accumulated memrefs onto it. 2974204642Srdivacky // 2975204642Srdivacky // FIXME: This is vastly incorrect for patterns with multiple outputs 2976204642Srdivacky // instructions that access memory and for ComplexPatterns that match 2977204642Srdivacky // loads. 2978204642Srdivacky if (EmitNodeInfo & OPFL_MemRefs) { 2979223017Sdim // Only attach load or store memory operands if the generated 2980223017Sdim // instruction may load or store. 2981224145Sdim const MCInstrDesc &MCID = TM.getInstrInfo()->get(TargetOpc); 2982224145Sdim bool mayLoad = MCID.mayLoad(); 2983224145Sdim bool mayStore = MCID.mayStore(); 2984223017Sdim 2985223017Sdim unsigned NumMemRefs = 0; 2986263509Sdim for (SmallVectorImpl<MachineMemOperand *>::const_iterator I = 2987263509Sdim MatchedMemRefs.begin(), E = MatchedMemRefs.end(); I != E; ++I) { 2988223017Sdim if ((*I)->isLoad()) { 2989223017Sdim if (mayLoad) 2990223017Sdim ++NumMemRefs; 2991223017Sdim } else if ((*I)->isStore()) { 2992223017Sdim if (mayStore) 2993223017Sdim ++NumMemRefs; 2994223017Sdim } else { 2995223017Sdim ++NumMemRefs; 2996223017Sdim } 2997223017Sdim } 2998223017Sdim 2999204642Srdivacky MachineSDNode::mmo_iterator MemRefs = 3000223017Sdim MF->allocateMemRefsArray(NumMemRefs); 3001223017Sdim 3002223017Sdim MachineSDNode::mmo_iterator MemRefsPos = MemRefs; 3003263509Sdim for (SmallVectorImpl<MachineMemOperand *>::const_iterator I = 3004263509Sdim MatchedMemRefs.begin(), E = MatchedMemRefs.end(); I != E; ++I) { 3005223017Sdim if ((*I)->isLoad()) { 3006223017Sdim if (mayLoad) 3007223017Sdim *MemRefsPos++ = *I; 3008223017Sdim } else if ((*I)->isStore()) { 3009223017Sdim if (mayStore) 3010223017Sdim *MemRefsPos++ = *I; 3011223017Sdim } else { 3012223017Sdim *MemRefsPos++ = *I; 3013223017Sdim } 3014223017Sdim } 3015223017Sdim 3016204642Srdivacky cast<MachineSDNode>(Res) 3017223017Sdim ->setMemRefs(MemRefs, MemRefs + NumMemRefs); 3018204642Srdivacky } 3019218893Sdim 3020252723Sdim DEBUG(dbgs() << " " 3021204642Srdivacky << (Opcode == OPC_MorphNodeTo ? "Morphed" : "Created") 3022252723Sdim << " node: "; Res->dump(CurDAG); dbgs() << "\n"); 3023218893Sdim 3024204642Srdivacky // If this was a MorphNodeTo then we're completely done! 3025204642Srdivacky if (Opcode == OPC_MorphNodeTo) { 3026218893Sdim // Update chain and glue uses. 3027218893Sdim UpdateChainsAndGlue(NodeToMatch, InputChain, ChainNodesMatched, 3028218893Sdim InputGlue, GlueResultNodesMatched, true); 3029204642Srdivacky return Res; 3030204642Srdivacky } 3031218893Sdim 3032204642Srdivacky continue; 3033204642Srdivacky } 3034218893Sdim 3035218893Sdim case OPC_MarkGlueResults: { 3036204642Srdivacky unsigned NumNodes = MatcherTable[MatcherIndex++]; 3037218893Sdim 3038218893Sdim // Read and remember all the glue-result nodes. 3039204642Srdivacky for (unsigned i = 0; i != NumNodes; ++i) { 3040204642Srdivacky unsigned RecNo = MatcherTable[MatcherIndex++]; 3041204642Srdivacky if (RecNo & 128) 3042204642Srdivacky RecNo = GetVBR(RecNo, MatcherTable, MatcherIndex); 3043204642Srdivacky 3044263509Sdim assert(RecNo < RecordedNodes.size() && "Invalid MarkGlueResults"); 3045218893Sdim GlueResultNodesMatched.push_back(RecordedNodes[RecNo].first.getNode()); 3046204642Srdivacky } 3047204642Srdivacky continue; 3048204642Srdivacky } 3049218893Sdim 3050204642Srdivacky case OPC_CompleteMatch: { 3051204642Srdivacky // The match has been completed, and any new nodes (if any) have been 3052204642Srdivacky // created. Patch up references to the matched dag to use the newly 3053204642Srdivacky // created nodes. 3054204642Srdivacky unsigned NumResults = MatcherTable[MatcherIndex++]; 3055204642Srdivacky 3056204642Srdivacky for (unsigned i = 0; i != NumResults; ++i) { 3057204642Srdivacky unsigned ResSlot = MatcherTable[MatcherIndex++]; 3058204642Srdivacky if (ResSlot & 128) 3059204642Srdivacky ResSlot = GetVBR(ResSlot, MatcherTable, MatcherIndex); 3060218893Sdim 3061263509Sdim assert(ResSlot < RecordedNodes.size() && "Invalid CompleteMatch"); 3062218893Sdim SDValue Res = RecordedNodes[ResSlot].first; 3063218893Sdim 3064206083Srdivacky assert(i < NodeToMatch->getNumValues() && 3065206083Srdivacky NodeToMatch->getValueType(i) != MVT::Other && 3066218893Sdim NodeToMatch->getValueType(i) != MVT::Glue && 3067206083Srdivacky "Invalid number of results to complete!"); 3068204642Srdivacky assert((NodeToMatch->getValueType(i) == Res.getValueType() || 3069204642Srdivacky NodeToMatch->getValueType(i) == MVT::iPTR || 3070204642Srdivacky Res.getValueType() == MVT::iPTR || 3071204642Srdivacky NodeToMatch->getValueType(i).getSizeInBits() == 3072204642Srdivacky Res.getValueType().getSizeInBits()) && 3073204642Srdivacky "invalid replacement"); 3074204642Srdivacky CurDAG->ReplaceAllUsesOfValueWith(SDValue(NodeToMatch, i), Res); 3075204642Srdivacky } 3076204642Srdivacky 3077218893Sdim // If the root node defines glue, add it to the glue nodes to update list. 3078218893Sdim if (NodeToMatch->getValueType(NodeToMatch->getNumValues()-1) == MVT::Glue) 3079218893Sdim GlueResultNodesMatched.push_back(NodeToMatch); 3080218893Sdim 3081218893Sdim // Update chain and glue uses. 3082218893Sdim UpdateChainsAndGlue(NodeToMatch, InputChain, ChainNodesMatched, 3083218893Sdim InputGlue, GlueResultNodesMatched, false); 3084218893Sdim 3085204642Srdivacky assert(NodeToMatch->use_empty() && 3086204642Srdivacky "Didn't replace all uses of the node?"); 3087218893Sdim 3088204642Srdivacky // FIXME: We just return here, which interacts correctly with SelectRoot 3089204642Srdivacky // above. We should fix this to not return an SDNode* anymore. 3090204642Srdivacky return 0; 3091204642Srdivacky } 3092204642Srdivacky } 3093218893Sdim 3094204642Srdivacky // If the code reached this point, then the match failed. See if there is 3095204642Srdivacky // another child to try in the current 'Scope', otherwise pop it until we 3096204642Srdivacky // find a case to check. 3097252723Sdim DEBUG(dbgs() << " Match failed at index " << CurrentOpcodeIndex << "\n"); 3098206083Srdivacky ++NumDAGIselRetries; 3099204642Srdivacky while (1) { 3100204642Srdivacky if (MatchScopes.empty()) { 3101204642Srdivacky CannotYetSelect(NodeToMatch); 3102204642Srdivacky return 0; 3103204642Srdivacky } 3104204642Srdivacky 3105204642Srdivacky // Restore the interpreter state back to the point where the scope was 3106204642Srdivacky // formed. 3107204642Srdivacky MatchScope &LastScope = MatchScopes.back(); 3108204642Srdivacky RecordedNodes.resize(LastScope.NumRecordedNodes); 3109204642Srdivacky NodeStack.clear(); 3110204642Srdivacky NodeStack.append(LastScope.NodeStack.begin(), LastScope.NodeStack.end()); 3111204642Srdivacky N = NodeStack.back(); 3112204642Srdivacky 3113204642Srdivacky if (LastScope.NumMatchedMemRefs != MatchedMemRefs.size()) 3114204642Srdivacky MatchedMemRefs.resize(LastScope.NumMatchedMemRefs); 3115204642Srdivacky MatcherIndex = LastScope.FailIndex; 3116218893Sdim 3117252723Sdim DEBUG(dbgs() << " Continuing at " << MatcherIndex << "\n"); 3118218893Sdim 3119204642Srdivacky InputChain = LastScope.InputChain; 3120218893Sdim InputGlue = LastScope.InputGlue; 3121204642Srdivacky if (!LastScope.HasChainNodesMatched) 3122204642Srdivacky ChainNodesMatched.clear(); 3123218893Sdim if (!LastScope.HasGlueResultNodesMatched) 3124218893Sdim GlueResultNodesMatched.clear(); 3125204642Srdivacky 3126204642Srdivacky // Check to see what the offset is at the new MatcherIndex. If it is zero 3127204642Srdivacky // we have reached the end of this scope, otherwise we have another child 3128204642Srdivacky // in the current scope to try. 3129204642Srdivacky unsigned NumToSkip = MatcherTable[MatcherIndex++]; 3130204642Srdivacky if (NumToSkip & 128) 3131204642Srdivacky NumToSkip = GetVBR(NumToSkip, MatcherTable, MatcherIndex); 3132204642Srdivacky 3133204642Srdivacky // If we have another child in this scope to match, update FailIndex and 3134204642Srdivacky // try it. 3135204642Srdivacky if (NumToSkip != 0) { 3136204642Srdivacky LastScope.FailIndex = MatcherIndex+NumToSkip; 3137204642Srdivacky break; 3138204642Srdivacky } 3139218893Sdim 3140204642Srdivacky // End of this scope, pop it and try the next child in the containing 3141204642Srdivacky // scope. 3142204642Srdivacky MatchScopes.pop_back(); 3143204642Srdivacky } 3144204642Srdivacky } 3145204642Srdivacky} 3146204642Srdivacky 3147204642Srdivacky 3148218893Sdim 3149202375Srdivackyvoid SelectionDAGISel::CannotYetSelect(SDNode *N) { 3150198892Srdivacky std::string msg; 3151198892Srdivacky raw_string_ostream Msg(msg); 3152218893Sdim Msg << "Cannot select: "; 3153218893Sdim 3154204792Srdivacky if (N->getOpcode() != ISD::INTRINSIC_W_CHAIN && 3155204792Srdivacky N->getOpcode() != ISD::INTRINSIC_WO_CHAIN && 3156204792Srdivacky N->getOpcode() != ISD::INTRINSIC_VOID) { 3157204792Srdivacky N->printrFull(Msg, CurDAG); 3158245431Sdim Msg << "\nIn function: " << MF->getName(); 3159204792Srdivacky } else { 3160204792Srdivacky bool HasInputChain = N->getOperand(0).getValueType() == MVT::Other; 3161204792Srdivacky unsigned iid = 3162204792Srdivacky cast<ConstantSDNode>(N->getOperand(HasInputChain))->getZExtValue(); 3163204792Srdivacky if (iid < Intrinsic::num_intrinsics) 3164204792Srdivacky Msg << "intrinsic %" << Intrinsic::getName((Intrinsic::ID)iid); 3165204792Srdivacky else if (const TargetIntrinsicInfo *TII = TM.getIntrinsicInfo()) 3166204792Srdivacky Msg << "target intrinsic %" << TII->getName(iid); 3167204792Srdivacky else 3168204792Srdivacky Msg << "unknown intrinsic #" << iid; 3169204792Srdivacky } 3170207618Srdivacky report_fatal_error(Msg.str()); 3171198892Srdivacky} 3172198892Srdivacky 3173193323Sedchar SelectionDAGISel::ID = 0; 3174