LLVM API Documentation

SelectionDAGISel.cpp
Go to the documentation of this file.
00001 //===-- SelectionDAGISel.cpp - Implement the SelectionDAGISel class -------===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This implements the SelectionDAGISel class.
00011 //
00012 //===----------------------------------------------------------------------===//
00013 
00014 #define DEBUG_TYPE "isel"
00015 #include "llvm/CodeGen/SelectionDAGISel.h"
00016 #include "ScheduleDAGSDNodes.h"
00017 #include "SelectionDAGBuilder.h"
00018 #include "llvm/ADT/PostOrderIterator.h"
00019 #include "llvm/ADT/Statistic.h"
00020 #include "llvm/Analysis/AliasAnalysis.h"
00021 #include "llvm/Analysis/BranchProbabilityInfo.h"
00022 #include "llvm/Analysis/CFG.h"
00023 #include "llvm/CodeGen/FastISel.h"
00024 #include "llvm/CodeGen/FunctionLoweringInfo.h"
00025 #include "llvm/CodeGen/GCMetadata.h"
00026 #include "llvm/CodeGen/GCStrategy.h"
00027 #include "llvm/CodeGen/MachineFrameInfo.h"
00028 #include "llvm/CodeGen/MachineFunction.h"
00029 #include "llvm/CodeGen/MachineInstrBuilder.h"
00030 #include "llvm/CodeGen/MachineModuleInfo.h"
00031 #include "llvm/CodeGen/MachineRegisterInfo.h"
00032 #include "llvm/CodeGen/ScheduleHazardRecognizer.h"
00033 #include "llvm/CodeGen/SchedulerRegistry.h"
00034 #include "llvm/CodeGen/SelectionDAG.h"
00035 #include "llvm/IR/Constants.h"
00036 #include "llvm/IR/DebugInfo.h"
00037 #include "llvm/IR/Function.h"
00038 #include "llvm/IR/InlineAsm.h"
00039 #include "llvm/IR/Instructions.h"
00040 #include "llvm/IR/IntrinsicInst.h"
00041 #include "llvm/IR/Intrinsics.h"
00042 #include "llvm/IR/LLVMContext.h"
00043 #include "llvm/IR/Module.h"
00044 #include "llvm/Support/Compiler.h"
00045 #include "llvm/Support/Debug.h"
00046 #include "llvm/Support/ErrorHandling.h"
00047 #include "llvm/Support/Timer.h"
00048 #include "llvm/Support/raw_ostream.h"
00049 #include "llvm/Target/TargetInstrInfo.h"
00050 #include "llvm/Target/TargetIntrinsicInfo.h"
00051 #include "llvm/Target/TargetLibraryInfo.h"
00052 #include "llvm/Target/TargetLowering.h"
00053 #include "llvm/Target/TargetMachine.h"
00054 #include "llvm/Target/TargetOptions.h"
00055 #include "llvm/Target/TargetRegisterInfo.h"
00056 #include "llvm/Target/TargetSubtargetInfo.h"
00057 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
00058 #include <algorithm>
00059 using namespace llvm;
00060 
00061 STATISTIC(NumFastIselFailures, "Number of instructions fast isel failed on");
00062 STATISTIC(NumFastIselSuccess, "Number of instructions fast isel selected");
00063 STATISTIC(NumFastIselBlocks, "Number of blocks selected entirely by fast isel");
00064 STATISTIC(NumDAGBlocks, "Number of blocks selected using DAG");
00065 STATISTIC(NumDAGIselRetries,"Number of times dag isel has to try another path");
00066 STATISTIC(NumEntryBlocks, "Number of entry blocks encountered");
00067 STATISTIC(NumFastIselFailLowerArguments,
00068           "Number of entry blocks where fast isel failed to lower arguments");
00069 
00070 #ifndef NDEBUG
00071 static cl::opt<bool>
00072 EnableFastISelVerbose2("fast-isel-verbose2", cl::Hidden,
00073           cl::desc("Enable extra verbose messages in the \"fast\" "
00074                    "instruction selector"));
00075 
00076   // Terminators
00077 STATISTIC(NumFastIselFailRet,"Fast isel fails on Ret");
00078 STATISTIC(NumFastIselFailBr,"Fast isel fails on Br");
00079 STATISTIC(NumFastIselFailSwitch,"Fast isel fails on Switch");
00080 STATISTIC(NumFastIselFailIndirectBr,"Fast isel fails on IndirectBr");
00081 STATISTIC(NumFastIselFailInvoke,"Fast isel fails on Invoke");
00082 STATISTIC(NumFastIselFailResume,"Fast isel fails on Resume");
00083 STATISTIC(NumFastIselFailUnreachable,"Fast isel fails on Unreachable");
00084 
00085   // Standard binary operators...
00086 STATISTIC(NumFastIselFailAdd,"Fast isel fails on Add");
00087 STATISTIC(NumFastIselFailFAdd,"Fast isel fails on FAdd");
00088 STATISTIC(NumFastIselFailSub,"Fast isel fails on Sub");
00089 STATISTIC(NumFastIselFailFSub,"Fast isel fails on FSub");
00090 STATISTIC(NumFastIselFailMul,"Fast isel fails on Mul");
00091 STATISTIC(NumFastIselFailFMul,"Fast isel fails on FMul");
00092 STATISTIC(NumFastIselFailUDiv,"Fast isel fails on UDiv");
00093 STATISTIC(NumFastIselFailSDiv,"Fast isel fails on SDiv");
00094 STATISTIC(NumFastIselFailFDiv,"Fast isel fails on FDiv");
00095 STATISTIC(NumFastIselFailURem,"Fast isel fails on URem");
00096 STATISTIC(NumFastIselFailSRem,"Fast isel fails on SRem");
00097 STATISTIC(NumFastIselFailFRem,"Fast isel fails on FRem");
00098 
00099   // Logical operators...
00100 STATISTIC(NumFastIselFailAnd,"Fast isel fails on And");
00101 STATISTIC(NumFastIselFailOr,"Fast isel fails on Or");
00102 STATISTIC(NumFastIselFailXor,"Fast isel fails on Xor");
00103 
00104   // Memory instructions...
00105 STATISTIC(NumFastIselFailAlloca,"Fast isel fails on Alloca");
00106 STATISTIC(NumFastIselFailLoad,"Fast isel fails on Load");
00107 STATISTIC(NumFastIselFailStore,"Fast isel fails on Store");
00108 STATISTIC(NumFastIselFailAtomicCmpXchg,"Fast isel fails on AtomicCmpXchg");
00109 STATISTIC(NumFastIselFailAtomicRMW,"Fast isel fails on AtomicRWM");
00110 STATISTIC(NumFastIselFailFence,"Fast isel fails on Frence");
00111 STATISTIC(NumFastIselFailGetElementPtr,"Fast isel fails on GetElementPtr");
00112 
00113   // Convert instructions...
00114 STATISTIC(NumFastIselFailTrunc,"Fast isel fails on Trunc");
00115 STATISTIC(NumFastIselFailZExt,"Fast isel fails on ZExt");
00116 STATISTIC(NumFastIselFailSExt,"Fast isel fails on SExt");
00117 STATISTIC(NumFastIselFailFPTrunc,"Fast isel fails on FPTrunc");
00118 STATISTIC(NumFastIselFailFPExt,"Fast isel fails on FPExt");
00119 STATISTIC(NumFastIselFailFPToUI,"Fast isel fails on FPToUI");
00120 STATISTIC(NumFastIselFailFPToSI,"Fast isel fails on FPToSI");
00121 STATISTIC(NumFastIselFailUIToFP,"Fast isel fails on UIToFP");
00122 STATISTIC(NumFastIselFailSIToFP,"Fast isel fails on SIToFP");
00123 STATISTIC(NumFastIselFailIntToPtr,"Fast isel fails on IntToPtr");
00124 STATISTIC(NumFastIselFailPtrToInt,"Fast isel fails on PtrToInt");
00125 STATISTIC(NumFastIselFailBitCast,"Fast isel fails on BitCast");
00126 
00127   // Other instructions...
00128 STATISTIC(NumFastIselFailICmp,"Fast isel fails on ICmp");
00129 STATISTIC(NumFastIselFailFCmp,"Fast isel fails on FCmp");
00130 STATISTIC(NumFastIselFailPHI,"Fast isel fails on PHI");
00131 STATISTIC(NumFastIselFailSelect,"Fast isel fails on Select");
00132 STATISTIC(NumFastIselFailCall,"Fast isel fails on Call");
00133 STATISTIC(NumFastIselFailShl,"Fast isel fails on Shl");
00134 STATISTIC(NumFastIselFailLShr,"Fast isel fails on LShr");
00135 STATISTIC(NumFastIselFailAShr,"Fast isel fails on AShr");
00136 STATISTIC(NumFastIselFailVAArg,"Fast isel fails on VAArg");
00137 STATISTIC(NumFastIselFailExtractElement,"Fast isel fails on ExtractElement");
00138 STATISTIC(NumFastIselFailInsertElement,"Fast isel fails on InsertElement");
00139 STATISTIC(NumFastIselFailShuffleVector,"Fast isel fails on ShuffleVector");
00140 STATISTIC(NumFastIselFailExtractValue,"Fast isel fails on ExtractValue");
00141 STATISTIC(NumFastIselFailInsertValue,"Fast isel fails on InsertValue");
00142 STATISTIC(NumFastIselFailLandingPad,"Fast isel fails on LandingPad");
00143 #endif
00144 
00145 static cl::opt<bool>
00146 EnableFastISelVerbose("fast-isel-verbose", cl::Hidden,
00147           cl::desc("Enable verbose messages in the \"fast\" "
00148                    "instruction selector"));
00149 static cl::opt<bool>
00150 EnableFastISelAbort("fast-isel-abort", cl::Hidden,
00151           cl::desc("Enable abort calls when \"fast\" instruction selection "
00152                    "fails to lower an instruction"));
00153 static cl::opt<bool>
00154 EnableFastISelAbortArgs("fast-isel-abort-args", cl::Hidden,
00155           cl::desc("Enable abort calls when \"fast\" instruction selection "
00156                    "fails to lower a formal argument"));
00157 
00158 static cl::opt<bool>
00159 UseMBPI("use-mbpi",
00160         cl::desc("use Machine Branch Probability Info"),
00161         cl::init(true), cl::Hidden);
00162 
00163 #ifndef NDEBUG
00164 static cl::opt<bool>
00165 ViewDAGCombine1("view-dag-combine1-dags", cl::Hidden,
00166           cl::desc("Pop up a window to show dags before the first "
00167                    "dag combine pass"));
00168 static cl::opt<bool>
00169 ViewLegalizeTypesDAGs("view-legalize-types-dags", cl::Hidden,
00170           cl::desc("Pop up a window to show dags before legalize types"));
00171 static cl::opt<bool>
00172 ViewLegalizeDAGs("view-legalize-dags", cl::Hidden,
00173           cl::desc("Pop up a window to show dags before legalize"));
00174 static cl::opt<bool>
00175 ViewDAGCombine2("view-dag-combine2-dags", cl::Hidden,
00176           cl::desc("Pop up a window to show dags before the second "
00177                    "dag combine pass"));
00178 static cl::opt<bool>
00179 ViewDAGCombineLT("view-dag-combine-lt-dags", cl::Hidden,
00180           cl::desc("Pop up a window to show dags before the post legalize types"
00181                    " dag combine pass"));
00182 static cl::opt<bool>
00183 ViewISelDAGs("view-isel-dags", cl::Hidden,
00184           cl::desc("Pop up a window to show isel dags as they are selected"));
00185 static cl::opt<bool>
00186 ViewSchedDAGs("view-sched-dags", cl::Hidden,
00187           cl::desc("Pop up a window to show sched dags as they are processed"));
00188 static cl::opt<bool>
00189 ViewSUnitDAGs("view-sunit-dags", cl::Hidden,
00190       cl::desc("Pop up a window to show SUnit dags after they are processed"));
00191 #else
00192 static const bool ViewDAGCombine1 = false,
00193                   ViewLegalizeTypesDAGs = false, ViewLegalizeDAGs = false,
00194                   ViewDAGCombine2 = false,
00195                   ViewDAGCombineLT = false,
00196                   ViewISelDAGs = false, ViewSchedDAGs = false,
00197                   ViewSUnitDAGs = false;
00198 #endif
00199 
00200 //===---------------------------------------------------------------------===//
00201 ///
00202 /// RegisterScheduler class - Track the registration of instruction schedulers.
00203 ///
00204 //===---------------------------------------------------------------------===//
00205 MachinePassRegistry RegisterScheduler::Registry;
00206 
00207 //===---------------------------------------------------------------------===//
00208 ///
00209 /// ISHeuristic command line option for instruction schedulers.
00210 ///
00211 //===---------------------------------------------------------------------===//
00212 static cl::opt<RegisterScheduler::FunctionPassCtor, false,
00213                RegisterPassParser<RegisterScheduler> >
00214 ISHeuristic("pre-RA-sched",
00215             cl::init(&createDefaultScheduler), cl::Hidden,
00216             cl::desc("Instruction schedulers available (before register"
00217                      " allocation):"));
00218 
00219 static RegisterScheduler
00220 defaultListDAGScheduler("default", "Best scheduler for the target",
00221                         createDefaultScheduler);
00222 
00223 namespace llvm {
00224   //===--------------------------------------------------------------------===//
00225   /// \brief This class is used by SelectionDAGISel to temporarily override
00226   /// the optimization level on a per-function basis.
00227   class OptLevelChanger {
00228     SelectionDAGISel &IS;
00229     CodeGenOpt::Level SavedOptLevel;
00230     bool SavedFastISel;
00231 
00232   public:
00233     OptLevelChanger(SelectionDAGISel &ISel,
00234                     CodeGenOpt::Level NewOptLevel) : IS(ISel) {
00235       SavedOptLevel = IS.OptLevel;
00236       if (NewOptLevel == SavedOptLevel)
00237         return;
00238       IS.OptLevel = NewOptLevel;
00239       IS.TM.setOptLevel(NewOptLevel);
00240       SavedFastISel = IS.TM.Options.EnableFastISel;
00241       if (NewOptLevel == CodeGenOpt::None)
00242         IS.TM.setFastISel(true);
00243       DEBUG(dbgs() << "\nChanging optimization level for Function "
00244             << IS.MF->getFunction()->getName() << "\n");
00245       DEBUG(dbgs() << "\tBefore: -O" << SavedOptLevel
00246             << " ; After: -O" << NewOptLevel << "\n");
00247     }
00248 
00249     ~OptLevelChanger() {
00250       if (IS.OptLevel == SavedOptLevel)
00251         return;
00252       DEBUG(dbgs() << "\nRestoring optimization level for Function "
00253             << IS.MF->getFunction()->getName() << "\n");
00254       DEBUG(dbgs() << "\tBefore: -O" << IS.OptLevel
00255             << " ; After: -O" << SavedOptLevel << "\n");
00256       IS.OptLevel = SavedOptLevel;
00257       IS.TM.setOptLevel(SavedOptLevel);
00258       IS.TM.setFastISel(SavedFastISel);
00259     }
00260   };
00261 
00262   //===--------------------------------------------------------------------===//
00263   /// createDefaultScheduler - This creates an instruction scheduler appropriate
00264   /// for the target.
00265   ScheduleDAGSDNodes* createDefaultScheduler(SelectionDAGISel *IS,
00266                                              CodeGenOpt::Level OptLevel) {
00267     const TargetLowering *TLI = IS->getTargetLowering();
00268     const TargetSubtargetInfo &ST = IS->TM.getSubtarget<TargetSubtargetInfo>();
00269 
00270     if (OptLevel == CodeGenOpt::None || ST.useMachineScheduler() ||
00271         TLI->getSchedulingPreference() == Sched::Source)
00272       return createSourceListDAGScheduler(IS, OptLevel);
00273     if (TLI->getSchedulingPreference() == Sched::RegPressure)
00274       return createBURRListDAGScheduler(IS, OptLevel);
00275     if (TLI->getSchedulingPreference() == Sched::Hybrid)
00276       return createHybridListDAGScheduler(IS, OptLevel);
00277     if (TLI->getSchedulingPreference() == Sched::VLIW)
00278       return createVLIWDAGScheduler(IS, OptLevel);
00279     assert(TLI->getSchedulingPreference() == Sched::ILP &&
00280            "Unknown sched type!");
00281     return createILPListDAGScheduler(IS, OptLevel);
00282   }
00283 }
00284 
00285 // EmitInstrWithCustomInserter - This method should be implemented by targets
00286 // that mark instructions with the 'usesCustomInserter' flag.  These
00287 // instructions are special in various ways, which require special support to
00288 // insert.  The specified MachineInstr is created but not inserted into any
00289 // basic blocks, and this method is called to expand it into a sequence of
00290 // instructions, potentially also creating new basic blocks and control flow.
00291 // When new basic blocks are inserted and the edges from MBB to its successors
00292 // are modified, the method should insert pairs of <OldSucc, NewSucc> into the
00293 // DenseMap.
00294 MachineBasicBlock *
00295 TargetLowering::EmitInstrWithCustomInserter(MachineInstr *MI,
00296                                             MachineBasicBlock *MBB) const {
00297 #ifndef NDEBUG
00298   dbgs() << "If a target marks an instruction with "
00299           "'usesCustomInserter', it must implement "
00300           "TargetLowering::EmitInstrWithCustomInserter!";
00301 #endif
00302   llvm_unreachable(nullptr);
00303 }
00304 
00305 void TargetLowering::AdjustInstrPostInstrSelection(MachineInstr *MI,
00306                                                    SDNode *Node) const {
00307   assert(!MI->hasPostISelHook() &&
00308          "If a target marks an instruction with 'hasPostISelHook', "
00309          "it must implement TargetLowering::AdjustInstrPostInstrSelection!");
00310 }
00311 
00312 //===----------------------------------------------------------------------===//
00313 // SelectionDAGISel code
00314 //===----------------------------------------------------------------------===//
00315 
00316 SelectionDAGISel::SelectionDAGISel(TargetMachine &tm,
00317                                    CodeGenOpt::Level OL) :
00318   MachineFunctionPass(ID), TM(tm),
00319   FuncInfo(new FunctionLoweringInfo(TM)),
00320   CurDAG(new SelectionDAG(tm, OL)),
00321   SDB(new SelectionDAGBuilder(*CurDAG, *FuncInfo, OL)),
00322   GFI(),
00323   OptLevel(OL),
00324   DAGSize(0) {
00325     initializeGCModuleInfoPass(*PassRegistry::getPassRegistry());
00326     initializeAliasAnalysisAnalysisGroup(*PassRegistry::getPassRegistry());
00327     initializeBranchProbabilityInfoPass(*PassRegistry::getPassRegistry());
00328     initializeTargetLibraryInfoPass(*PassRegistry::getPassRegistry());
00329   }
00330 
00331 SelectionDAGISel::~SelectionDAGISel() {
00332   delete SDB;
00333   delete CurDAG;
00334   delete FuncInfo;
00335 }
00336 
00337 void SelectionDAGISel::getAnalysisUsage(AnalysisUsage &AU) const {
00338   AU.addRequired<AliasAnalysis>();
00339   AU.addPreserved<AliasAnalysis>();
00340   AU.addRequired<GCModuleInfo>();
00341   AU.addPreserved<GCModuleInfo>();
00342   AU.addRequired<TargetLibraryInfo>();
00343   if (UseMBPI && OptLevel != CodeGenOpt::None)
00344     AU.addRequired<BranchProbabilityInfo>();
00345   MachineFunctionPass::getAnalysisUsage(AU);
00346 }
00347 
00348 /// SplitCriticalSideEffectEdges - Look for critical edges with a PHI value that
00349 /// may trap on it.  In this case we have to split the edge so that the path
00350 /// through the predecessor block that doesn't go to the phi block doesn't
00351 /// execute the possibly trapping instruction.
00352 ///
00353 /// This is required for correctness, so it must be done at -O0.
00354 ///
00355 static void SplitCriticalSideEffectEdges(Function &Fn, Pass *SDISel) {
00356   // Loop for blocks with phi nodes.
00357   for (Function::iterator BB = Fn.begin(), E = Fn.end(); BB != E; ++BB) {
00358     PHINode *PN = dyn_cast<PHINode>(BB->begin());
00359     if (!PN) continue;
00360 
00361   ReprocessBlock:
00362     // For each block with a PHI node, check to see if any of the input values
00363     // are potentially trapping constant expressions.  Constant expressions are
00364     // the only potentially trapping value that can occur as the argument to a
00365     // PHI.
00366     for (BasicBlock::iterator I = BB->begin(); (PN = dyn_cast<PHINode>(I)); ++I)
00367       for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
00368         ConstantExpr *CE = dyn_cast<ConstantExpr>(PN->getIncomingValue(i));
00369         if (!CE || !CE->canTrap()) continue;
00370 
00371         // The only case we have to worry about is when the edge is critical.
00372         // Since this block has a PHI Node, we assume it has multiple input
00373         // edges: check to see if the pred has multiple successors.
00374         BasicBlock *Pred = PN->getIncomingBlock(i);
00375         if (Pred->getTerminator()->getNumSuccessors() == 1)
00376           continue;
00377 
00378         // Okay, we have to split this edge.
00379         SplitCriticalEdge(Pred->getTerminator(),
00380                           GetSuccessorNumber(Pred, BB), SDISel, true);
00381         goto ReprocessBlock;
00382       }
00383   }
00384 }
00385 
00386 bool SelectionDAGISel::runOnMachineFunction(MachineFunction &mf) {
00387   // Do some sanity-checking on the command-line options.
00388   assert((!EnableFastISelVerbose || TM.Options.EnableFastISel) &&
00389          "-fast-isel-verbose requires -fast-isel");
00390   assert((!EnableFastISelAbort || TM.Options.EnableFastISel) &&
00391          "-fast-isel-abort requires -fast-isel");
00392 
00393   const Function &Fn = *mf.getFunction();
00394   const TargetInstrInfo &TII = *TM.getInstrInfo();
00395   const TargetRegisterInfo &TRI = *TM.getRegisterInfo();
00396   const TargetLowering *TLI = TM.getTargetLowering();
00397 
00398   MF = &mf;
00399   RegInfo = &MF->getRegInfo();
00400   AA = &getAnalysis<AliasAnalysis>();
00401   LibInfo = &getAnalysis<TargetLibraryInfo>();
00402   GFI = Fn.hasGC() ? &getAnalysis<GCModuleInfo>().getFunctionInfo(Fn) : nullptr;
00403 
00404   TargetSubtargetInfo &ST =
00405     const_cast<TargetSubtargetInfo&>(TM.getSubtarget<TargetSubtargetInfo>());
00406   ST.resetSubtargetFeatures(MF);
00407   TM.resetTargetOptions(MF);
00408 
00409   // Reset OptLevel to None for optnone functions.
00410   CodeGenOpt::Level NewOptLevel = OptLevel;
00411   if (Fn.hasFnAttribute(Attribute::OptimizeNone))
00412     NewOptLevel = CodeGenOpt::None;
00413   OptLevelChanger OLC(*this, NewOptLevel);
00414 
00415   DEBUG(dbgs() << "\n\n\n=== " << Fn.getName() << "\n");
00416 
00417   SplitCriticalSideEffectEdges(const_cast<Function&>(Fn), this);
00418 
00419   CurDAG->init(*MF, TLI);
00420   FuncInfo->set(Fn, *MF, CurDAG);
00421 
00422   if (UseMBPI && OptLevel != CodeGenOpt::None)
00423     FuncInfo->BPI = &getAnalysis<BranchProbabilityInfo>();
00424   else
00425     FuncInfo->BPI = nullptr;
00426 
00427   SDB->init(GFI, *AA, LibInfo);
00428 
00429   MF->setHasInlineAsm(false);
00430 
00431   SelectAllBasicBlocks(Fn);
00432 
00433   // If the first basic block in the function has live ins that need to be
00434   // copied into vregs, emit the copies into the top of the block before
00435   // emitting the code for the block.
00436   MachineBasicBlock *EntryMBB = MF->begin();
00437   RegInfo->EmitLiveInCopies(EntryMBB, TRI, TII);
00438 
00439   DenseMap<unsigned, unsigned> LiveInMap;
00440   if (!FuncInfo->ArgDbgValues.empty())
00441     for (MachineRegisterInfo::livein_iterator LI = RegInfo->livein_begin(),
00442            E = RegInfo->livein_end(); LI != E; ++LI)
00443       if (LI->second)
00444         LiveInMap.insert(std::make_pair(LI->first, LI->second));
00445 
00446   // Insert DBG_VALUE instructions for function arguments to the entry block.
00447   for (unsigned i = 0, e = FuncInfo->ArgDbgValues.size(); i != e; ++i) {
00448     MachineInstr *MI = FuncInfo->ArgDbgValues[e-i-1];
00449     bool hasFI = MI->getOperand(0).isFI();
00450     unsigned Reg =
00451         hasFI ? TRI.getFrameRegister(*MF) : MI->getOperand(0).getReg();
00452     if (TargetRegisterInfo::isPhysicalRegister(Reg))
00453       EntryMBB->insert(EntryMBB->begin(), MI);
00454     else {
00455       MachineInstr *Def = RegInfo->getVRegDef(Reg);
00456       if (Def) {
00457         MachineBasicBlock::iterator InsertPos = Def;
00458         // FIXME: VR def may not be in entry block.
00459         Def->getParent()->insert(std::next(InsertPos), MI);
00460       } else
00461         DEBUG(dbgs() << "Dropping debug info for dead vreg"
00462               << TargetRegisterInfo::virtReg2Index(Reg) << "\n");
00463     }
00464 
00465     // If Reg is live-in then update debug info to track its copy in a vreg.
00466     DenseMap<unsigned, unsigned>::iterator LDI = LiveInMap.find(Reg);
00467     if (LDI != LiveInMap.end()) {
00468       assert(!hasFI && "There's no handling of frame pointer updating here yet "
00469                        "- add if needed");
00470       MachineInstr *Def = RegInfo->getVRegDef(LDI->second);
00471       MachineBasicBlock::iterator InsertPos = Def;
00472       const MDNode *Variable =
00473         MI->getOperand(MI->getNumOperands()-1).getMetadata();
00474       bool IsIndirect = MI->isIndirectDebugValue();
00475       unsigned Offset = IsIndirect ? MI->getOperand(1).getImm() : 0;
00476       // Def is never a terminator here, so it is ok to increment InsertPos.
00477       BuildMI(*EntryMBB, ++InsertPos, MI->getDebugLoc(),
00478               TII.get(TargetOpcode::DBG_VALUE),
00479               IsIndirect,
00480               LDI->second, Offset, Variable);
00481 
00482       // If this vreg is directly copied into an exported register then
00483       // that COPY instructions also need DBG_VALUE, if it is the only
00484       // user of LDI->second.
00485       MachineInstr *CopyUseMI = nullptr;
00486       for (MachineRegisterInfo::use_instr_iterator
00487            UI = RegInfo->use_instr_begin(LDI->second),
00488            E = RegInfo->use_instr_end(); UI != E; ) {
00489         MachineInstr *UseMI = &*(UI++);
00490         if (UseMI->isDebugValue()) continue;
00491         if (UseMI->isCopy() && !CopyUseMI && UseMI->getParent() == EntryMBB) {
00492           CopyUseMI = UseMI; continue;
00493         }
00494         // Otherwise this is another use or second copy use.
00495         CopyUseMI = nullptr; break;
00496       }
00497       if (CopyUseMI) {
00498         MachineInstr *NewMI =
00499           BuildMI(*MF, CopyUseMI->getDebugLoc(),
00500                   TII.get(TargetOpcode::DBG_VALUE),
00501                   IsIndirect,
00502                   CopyUseMI->getOperand(0).getReg(),
00503                   Offset, Variable);
00504         MachineBasicBlock::iterator Pos = CopyUseMI;
00505         EntryMBB->insertAfter(Pos, NewMI);
00506       }
00507     }
00508   }
00509 
00510   // Determine if there are any calls in this machine function.
00511   MachineFrameInfo *MFI = MF->getFrameInfo();
00512   for (MachineFunction::const_iterator I = MF->begin(), E = MF->end(); I != E;
00513        ++I) {
00514 
00515     if (MFI->hasCalls() && MF->hasInlineAsm())
00516       break;
00517 
00518     const MachineBasicBlock *MBB = I;
00519     for (MachineBasicBlock::const_iterator II = MBB->begin(), IE = MBB->end();
00520          II != IE; ++II) {
00521       const MCInstrDesc &MCID = TM.getInstrInfo()->get(II->getOpcode());
00522       if ((MCID.isCall() && !MCID.isReturn()) ||
00523           II->isStackAligningInlineAsm()) {
00524         MFI->setHasCalls(true);
00525       }
00526       if (II->isInlineAsm()) {
00527         MF->setHasInlineAsm(true);
00528       }
00529     }
00530   }
00531 
00532   // Determine if there is a call to setjmp in the machine function.
00533   MF->setExposesReturnsTwice(Fn.callsFunctionThatReturnsTwice());
00534 
00535   // Replace forward-declared registers with the registers containing
00536   // the desired value.
00537   MachineRegisterInfo &MRI = MF->getRegInfo();
00538   for (DenseMap<unsigned, unsigned>::iterator
00539        I = FuncInfo->RegFixups.begin(), E = FuncInfo->RegFixups.end();
00540        I != E; ++I) {
00541     unsigned From = I->first;
00542     unsigned To = I->second;
00543     // If To is also scheduled to be replaced, find what its ultimate
00544     // replacement is.
00545     for (;;) {
00546       DenseMap<unsigned, unsigned>::iterator J = FuncInfo->RegFixups.find(To);
00547       if (J == E) break;
00548       To = J->second;
00549     }
00550     // Make sure the new register has a sufficiently constrained register class.
00551     if (TargetRegisterInfo::isVirtualRegister(From) &&
00552         TargetRegisterInfo::isVirtualRegister(To))
00553       MRI.constrainRegClass(To, MRI.getRegClass(From));
00554     // Replace it.
00555     MRI.replaceRegWith(From, To);
00556   }
00557 
00558   // Freeze the set of reserved registers now that MachineFrameInfo has been
00559   // set up. All the information required by getReservedRegs() should be
00560   // available now.
00561   MRI.freezeReservedRegs(*MF);
00562 
00563   // Release function-specific state. SDB and CurDAG are already cleared
00564   // at this point.
00565   FuncInfo->clear();
00566 
00567   DEBUG(dbgs() << "*** MachineFunction at end of ISel ***\n");
00568   DEBUG(MF->print(dbgs()));
00569 
00570   return true;
00571 }
00572 
00573 void SelectionDAGISel::SelectBasicBlock(BasicBlock::const_iterator Begin,
00574                                         BasicBlock::const_iterator End,
00575                                         bool &HadTailCall) {
00576   // Lower all of the non-terminator instructions. If a call is emitted
00577   // as a tail call, cease emitting nodes for this block. Terminators
00578   // are handled below.
00579   for (BasicBlock::const_iterator I = Begin; I != End && !SDB->HasTailCall; ++I)
00580     SDB->visit(*I);
00581 
00582   // Make sure the root of the DAG is up-to-date.
00583   CurDAG->setRoot(SDB->getControlRoot());
00584   HadTailCall = SDB->HasTailCall;
00585   SDB->clear();
00586 
00587   // Final step, emit the lowered DAG as machine code.
00588   CodeGenAndEmitDAG();
00589 }
00590 
00591 void SelectionDAGISel::ComputeLiveOutVRegInfo() {
00592   SmallPtrSet<SDNode*, 128> VisitedNodes;
00593   SmallVector<SDNode*, 128> Worklist;
00594 
00595   Worklist.push_back(CurDAG->getRoot().getNode());
00596 
00597   APInt KnownZero;
00598   APInt KnownOne;
00599 
00600   do {
00601     SDNode *N = Worklist.pop_back_val();
00602 
00603     // If we've already seen this node, ignore it.
00604     if (!VisitedNodes.insert(N))
00605       continue;
00606 
00607     // Otherwise, add all chain operands to the worklist.
00608     for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i)
00609       if (N->getOperand(i).getValueType() == MVT::Other)
00610         Worklist.push_back(N->getOperand(i).getNode());
00611 
00612     // If this is a CopyToReg with a vreg dest, process it.
00613     if (N->getOpcode() != ISD::CopyToReg)
00614       continue;
00615 
00616     unsigned DestReg = cast<RegisterSDNode>(N->getOperand(1))->getReg();
00617     if (!TargetRegisterInfo::isVirtualRegister(DestReg))
00618       continue;
00619 
00620     // Ignore non-scalar or non-integer values.
00621     SDValue Src = N->getOperand(2);
00622     EVT SrcVT = Src.getValueType();
00623     if (!SrcVT.isInteger() || SrcVT.isVector())
00624       continue;
00625 
00626     unsigned NumSignBits = CurDAG->ComputeNumSignBits(Src);
00627     CurDAG->ComputeMaskedBits(Src, KnownZero, KnownOne);
00628     FuncInfo->AddLiveOutRegInfo(DestReg, NumSignBits, KnownZero, KnownOne);
00629   } while (!Worklist.empty());
00630 }
00631 
00632 void SelectionDAGISel::CodeGenAndEmitDAG() {
00633   std::string GroupName;
00634   if (TimePassesIsEnabled)
00635     GroupName = "Instruction Selection and Scheduling";
00636   std::string BlockName;
00637   int BlockNumber = -1;
00638   (void)BlockNumber;
00639 #ifdef NDEBUG
00640   if (ViewDAGCombine1 || ViewLegalizeTypesDAGs || ViewLegalizeDAGs ||
00641       ViewDAGCombine2 || ViewDAGCombineLT || ViewISelDAGs || ViewSchedDAGs ||
00642       ViewSUnitDAGs)
00643 #endif
00644   {
00645     BlockNumber = FuncInfo->MBB->getNumber();
00646     BlockName = MF->getName().str() + ":" +
00647                 FuncInfo->MBB->getBasicBlock()->getName().str();
00648   }
00649   DEBUG(dbgs() << "Initial selection DAG: BB#" << BlockNumber
00650         << " '" << BlockName << "'\n"; CurDAG->dump());
00651 
00652   if (ViewDAGCombine1) CurDAG->viewGraph("dag-combine1 input for " + BlockName);
00653 
00654   // Run the DAG combiner in pre-legalize mode.
00655   {
00656     NamedRegionTimer T("DAG Combining 1", GroupName, TimePassesIsEnabled);
00657     CurDAG->Combine(BeforeLegalizeTypes, *AA, OptLevel);
00658   }
00659 
00660   DEBUG(dbgs() << "Optimized lowered selection DAG: BB#" << BlockNumber
00661         << " '" << BlockName << "'\n"; CurDAG->dump());
00662 
00663   // Second step, hack on the DAG until it only uses operations and types that
00664   // the target supports.
00665   if (ViewLegalizeTypesDAGs) CurDAG->viewGraph("legalize-types input for " +
00666                                                BlockName);
00667 
00668   bool Changed;
00669   {
00670     NamedRegionTimer T("Type Legalization", GroupName, TimePassesIsEnabled);
00671     Changed = CurDAG->LegalizeTypes();
00672   }
00673 
00674   DEBUG(dbgs() << "Type-legalized selection DAG: BB#" << BlockNumber
00675         << " '" << BlockName << "'\n"; CurDAG->dump());
00676 
00677   CurDAG->NewNodesMustHaveLegalTypes = true;
00678 
00679   if (Changed) {
00680     if (ViewDAGCombineLT)
00681       CurDAG->viewGraph("dag-combine-lt input for " + BlockName);
00682 
00683     // Run the DAG combiner in post-type-legalize mode.
00684     {
00685       NamedRegionTimer T("DAG Combining after legalize types", GroupName,
00686                          TimePassesIsEnabled);
00687       CurDAG->Combine(AfterLegalizeTypes, *AA, OptLevel);
00688     }
00689 
00690     DEBUG(dbgs() << "Optimized type-legalized selection DAG: BB#" << BlockNumber
00691           << " '" << BlockName << "'\n"; CurDAG->dump());
00692 
00693   }
00694 
00695   {
00696     NamedRegionTimer T("Vector Legalization", GroupName, TimePassesIsEnabled);
00697     Changed = CurDAG->LegalizeVectors();
00698   }
00699 
00700   if (Changed) {
00701     {
00702       NamedRegionTimer T("Type Legalization 2", GroupName, TimePassesIsEnabled);
00703       CurDAG->LegalizeTypes();
00704     }
00705 
00706     if (ViewDAGCombineLT)
00707       CurDAG->viewGraph("dag-combine-lv input for " + BlockName);
00708 
00709     // Run the DAG combiner in post-type-legalize mode.
00710     {
00711       NamedRegionTimer T("DAG Combining after legalize vectors", GroupName,
00712                          TimePassesIsEnabled);
00713       CurDAG->Combine(AfterLegalizeVectorOps, *AA, OptLevel);
00714     }
00715 
00716     DEBUG(dbgs() << "Optimized vector-legalized selection DAG: BB#"
00717           << BlockNumber << " '" << BlockName << "'\n"; CurDAG->dump());
00718   }
00719 
00720   if (ViewLegalizeDAGs) CurDAG->viewGraph("legalize input for " + BlockName);
00721 
00722   {
00723     NamedRegionTimer T("DAG Legalization", GroupName, TimePassesIsEnabled);
00724     CurDAG->Legalize();
00725   }
00726 
00727   DEBUG(dbgs() << "Legalized selection DAG: BB#" << BlockNumber
00728         << " '" << BlockName << "'\n"; CurDAG->dump());
00729 
00730   if (ViewDAGCombine2) CurDAG->viewGraph("dag-combine2 input for " + BlockName);
00731 
00732   // Run the DAG combiner in post-legalize mode.
00733   {
00734     NamedRegionTimer T("DAG Combining 2", GroupName, TimePassesIsEnabled);
00735     CurDAG->Combine(AfterLegalizeDAG, *AA, OptLevel);
00736   }
00737 
00738   DEBUG(dbgs() << "Optimized legalized selection DAG: BB#" << BlockNumber
00739         << " '" << BlockName << "'\n"; CurDAG->dump());
00740 
00741   if (OptLevel != CodeGenOpt::None)
00742     ComputeLiveOutVRegInfo();
00743 
00744   if (ViewISelDAGs) CurDAG->viewGraph("isel input for " + BlockName);
00745 
00746   // Third, instruction select all of the operations to machine code, adding the
00747   // code to the MachineBasicBlock.
00748   {
00749     NamedRegionTimer T("Instruction Selection", GroupName, TimePassesIsEnabled);
00750     DoInstructionSelection();
00751   }
00752 
00753   DEBUG(dbgs() << "Selected selection DAG: BB#" << BlockNumber
00754         << " '" << BlockName << "'\n"; CurDAG->dump());
00755 
00756   if (ViewSchedDAGs) CurDAG->viewGraph("scheduler input for " + BlockName);
00757 
00758   // Schedule machine code.
00759   ScheduleDAGSDNodes *Scheduler = CreateScheduler();
00760   {
00761     NamedRegionTimer T("Instruction Scheduling", GroupName,
00762                        TimePassesIsEnabled);
00763     Scheduler->Run(CurDAG, FuncInfo->MBB);
00764   }
00765 
00766   if (ViewSUnitDAGs) Scheduler->viewGraph();
00767 
00768   // Emit machine code to BB.  This can change 'BB' to the last block being
00769   // inserted into.
00770   MachineBasicBlock *FirstMBB = FuncInfo->MBB, *LastMBB;
00771   {
00772     NamedRegionTimer T("Instruction Creation", GroupName, TimePassesIsEnabled);
00773 
00774     // FuncInfo->InsertPt is passed by reference and set to the end of the
00775     // scheduled instructions.
00776     LastMBB = FuncInfo->MBB = Scheduler->EmitSchedule(FuncInfo->InsertPt);
00777   }
00778 
00779   // If the block was split, make sure we update any references that are used to
00780   // update PHI nodes later on.
00781   if (FirstMBB != LastMBB)
00782     SDB->UpdateSplitBlock(FirstMBB, LastMBB);
00783 
00784   // Free the scheduler state.
00785   {
00786     NamedRegionTimer T("Instruction Scheduling Cleanup", GroupName,
00787                        TimePassesIsEnabled);
00788     delete Scheduler;
00789   }
00790 
00791   // Free the SelectionDAG state, now that we're finished with it.
00792   CurDAG->clear();
00793 }
00794 
00795 namespace {
00796 /// ISelUpdater - helper class to handle updates of the instruction selection
00797 /// graph.
00798 class ISelUpdater : public SelectionDAG::DAGUpdateListener {
00799   SelectionDAG::allnodes_iterator &ISelPosition;
00800 public:
00801   ISelUpdater(SelectionDAG &DAG, SelectionDAG::allnodes_iterator &isp)
00802     : SelectionDAG::DAGUpdateListener(DAG), ISelPosition(isp) {}
00803 
00804   /// NodeDeleted - Handle nodes deleted from the graph. If the node being
00805   /// deleted is the current ISelPosition node, update ISelPosition.
00806   ///
00807   void NodeDeleted(SDNode *N, SDNode *E) override {
00808     if (ISelPosition == SelectionDAG::allnodes_iterator(N))
00809       ++ISelPosition;
00810   }
00811 };
00812 } // end anonymous namespace
00813 
00814 void SelectionDAGISel::DoInstructionSelection() {
00815   DEBUG(dbgs() << "===== Instruction selection begins: BB#"
00816         << FuncInfo->MBB->getNumber()
00817         << " '" << FuncInfo->MBB->getName() << "'\n");
00818 
00819   PreprocessISelDAG();
00820 
00821   // Select target instructions for the DAG.
00822   {
00823     // Number all nodes with a topological order and set DAGSize.
00824     DAGSize = CurDAG->AssignTopologicalOrder();
00825 
00826     // Create a dummy node (which is not added to allnodes), that adds
00827     // a reference to the root node, preventing it from being deleted,
00828     // and tracking any changes of the root.
00829     HandleSDNode Dummy(CurDAG->getRoot());
00830     SelectionDAG::allnodes_iterator ISelPosition (CurDAG->getRoot().getNode());
00831     ++ISelPosition;
00832 
00833     // Make sure that ISelPosition gets properly updated when nodes are deleted
00834     // in calls made from this function.
00835     ISelUpdater ISU(*CurDAG, ISelPosition);
00836 
00837     // The AllNodes list is now topological-sorted. Visit the
00838     // nodes by starting at the end of the list (the root of the
00839     // graph) and preceding back toward the beginning (the entry
00840     // node).
00841     while (ISelPosition != CurDAG->allnodes_begin()) {
00842       SDNode *Node = --ISelPosition;
00843       // Skip dead nodes. DAGCombiner is expected to eliminate all dead nodes,
00844       // but there are currently some corner cases that it misses. Also, this
00845       // makes it theoretically possible to disable the DAGCombiner.
00846       if (Node->use_empty())
00847         continue;
00848 
00849       SDNode *ResNode = Select(Node);
00850 
00851       // FIXME: This is pretty gross.  'Select' should be changed to not return
00852       // anything at all and this code should be nuked with a tactical strike.
00853 
00854       // If node should not be replaced, continue with the next one.
00855       if (ResNode == Node || Node->getOpcode() == ISD::DELETED_NODE)
00856         continue;
00857       // Replace node.
00858       if (ResNode) {
00859         ReplaceUses(Node, ResNode);
00860       }
00861 
00862       // If after the replacement this node is not used any more,
00863       // remove this dead node.
00864       if (Node->use_empty()) // Don't delete EntryToken, etc.
00865         CurDAG->RemoveDeadNode(Node);
00866     }
00867 
00868     CurDAG->setRoot(Dummy.getValue());
00869   }
00870 
00871   DEBUG(dbgs() << "===== Instruction selection ends:\n");
00872 
00873   PostprocessISelDAG();
00874 }
00875 
00876 /// PrepareEHLandingPad - Emit an EH_LABEL, set up live-in registers, and
00877 /// do other setup for EH landing-pad blocks.
00878 void SelectionDAGISel::PrepareEHLandingPad() {
00879   MachineBasicBlock *MBB = FuncInfo->MBB;
00880 
00881   // Add a label to mark the beginning of the landing pad.  Deletion of the
00882   // landing pad can thus be detected via the MachineModuleInfo.
00883   MCSymbol *Label = MF->getMMI().addLandingPad(MBB);
00884 
00885   // Assign the call site to the landing pad's begin label.
00886   MF->getMMI().setCallSiteLandingPad(Label, SDB->LPadToCallSiteMap[MBB]);
00887 
00888   const MCInstrDesc &II = TM.getInstrInfo()->get(TargetOpcode::EH_LABEL);
00889   BuildMI(*MBB, FuncInfo->InsertPt, SDB->getCurDebugLoc(), II)
00890     .addSym(Label);
00891 
00892   // Mark exception register as live in.
00893   const TargetLowering *TLI = getTargetLowering();
00894   const TargetRegisterClass *PtrRC = TLI->getRegClassFor(TLI->getPointerTy());
00895   if (unsigned Reg = TLI->getExceptionPointerRegister())
00896     FuncInfo->ExceptionPointerVirtReg = MBB->addLiveIn(Reg, PtrRC);
00897 
00898   // Mark exception selector register as live in.
00899   if (unsigned Reg = TLI->getExceptionSelectorRegister())
00900     FuncInfo->ExceptionSelectorVirtReg = MBB->addLiveIn(Reg, PtrRC);
00901 }
00902 
00903 /// isFoldedOrDeadInstruction - Return true if the specified instruction is
00904 /// side-effect free and is either dead or folded into a generated instruction.
00905 /// Return false if it needs to be emitted.
00906 static bool isFoldedOrDeadInstruction(const Instruction *I,
00907                                       FunctionLoweringInfo *FuncInfo) {
00908   return !I->mayWriteToMemory() && // Side-effecting instructions aren't folded.
00909          !isa<TerminatorInst>(I) && // Terminators aren't folded.
00910          !isa<DbgInfoIntrinsic>(I) &&  // Debug instructions aren't folded.
00911          !isa<LandingPadInst>(I) &&    // Landingpad instructions aren't folded.
00912          !FuncInfo->isExportedInst(I); // Exported instrs must be computed.
00913 }
00914 
00915 #ifndef NDEBUG
00916 // Collect per Instruction statistics for fast-isel misses.  Only those
00917 // instructions that cause the bail are accounted for.  It does not account for
00918 // instructions higher in the block.  Thus, summing the per instructions stats
00919 // will not add up to what is reported by NumFastIselFailures.
00920 static void collectFailStats(const Instruction *I) {
00921   switch (I->getOpcode()) {
00922   default: assert (0 && "<Invalid operator> ");
00923 
00924   // Terminators
00925   case Instruction::Ret:         NumFastIselFailRet++; return;
00926   case Instruction::Br:          NumFastIselFailBr++; return;
00927   case Instruction::Switch:      NumFastIselFailSwitch++; return;
00928   case Instruction::IndirectBr:  NumFastIselFailIndirectBr++; return;
00929   case Instruction::Invoke:      NumFastIselFailInvoke++; return;
00930   case Instruction::Resume:      NumFastIselFailResume++; return;
00931   case Instruction::Unreachable: NumFastIselFailUnreachable++; return;
00932 
00933   // Standard binary operators...
00934   case Instruction::Add:  NumFastIselFailAdd++; return;
00935   case Instruction::FAdd: NumFastIselFailFAdd++; return;
00936   case Instruction::Sub:  NumFastIselFailSub++; return;
00937   case Instruction::FSub: NumFastIselFailFSub++; return;
00938   case Instruction::Mul:  NumFastIselFailMul++; return;
00939   case Instruction::FMul: NumFastIselFailFMul++; return;
00940   case Instruction::UDiv: NumFastIselFailUDiv++; return;
00941   case Instruction::SDiv: NumFastIselFailSDiv++; return;
00942   case Instruction::FDiv: NumFastIselFailFDiv++; return;
00943   case Instruction::URem: NumFastIselFailURem++; return;
00944   case Instruction::SRem: NumFastIselFailSRem++; return;
00945   case Instruction::FRem: NumFastIselFailFRem++; return;
00946 
00947   // Logical operators...
00948   case Instruction::And: NumFastIselFailAnd++; return;
00949   case Instruction::Or:  NumFastIselFailOr++; return;
00950   case Instruction::Xor: NumFastIselFailXor++; return;
00951 
00952   // Memory instructions...
00953   case Instruction::Alloca:        NumFastIselFailAlloca++; return;
00954   case Instruction::Load:          NumFastIselFailLoad++; return;
00955   case Instruction::Store:         NumFastIselFailStore++; return;
00956   case Instruction::AtomicCmpXchg: NumFastIselFailAtomicCmpXchg++; return;
00957   case Instruction::AtomicRMW:     NumFastIselFailAtomicRMW++; return;
00958   case Instruction::Fence:         NumFastIselFailFence++; return;
00959   case Instruction::GetElementPtr: NumFastIselFailGetElementPtr++; return;
00960 
00961   // Convert instructions...
00962   case Instruction::Trunc:    NumFastIselFailTrunc++; return;
00963   case Instruction::ZExt:     NumFastIselFailZExt++; return;
00964   case Instruction::SExt:     NumFastIselFailSExt++; return;
00965   case Instruction::FPTrunc:  NumFastIselFailFPTrunc++; return;
00966   case Instruction::FPExt:    NumFastIselFailFPExt++; return;
00967   case Instruction::FPToUI:   NumFastIselFailFPToUI++; return;
00968   case Instruction::FPToSI:   NumFastIselFailFPToSI++; return;
00969   case Instruction::UIToFP:   NumFastIselFailUIToFP++; return;
00970   case Instruction::SIToFP:   NumFastIselFailSIToFP++; return;
00971   case Instruction::IntToPtr: NumFastIselFailIntToPtr++; return;
00972   case Instruction::PtrToInt: NumFastIselFailPtrToInt++; return;
00973   case Instruction::BitCast:  NumFastIselFailBitCast++; return;
00974 
00975   // Other instructions...
00976   case Instruction::ICmp:           NumFastIselFailICmp++; return;
00977   case Instruction::FCmp:           NumFastIselFailFCmp++; return;
00978   case Instruction::PHI:            NumFastIselFailPHI++; return;
00979   case Instruction::Select:         NumFastIselFailSelect++; return;
00980   case Instruction::Call:           NumFastIselFailCall++; return;
00981   case Instruction::Shl:            NumFastIselFailShl++; return;
00982   case Instruction::LShr:           NumFastIselFailLShr++; return;
00983   case Instruction::AShr:           NumFastIselFailAShr++; return;
00984   case Instruction::VAArg:          NumFastIselFailVAArg++; return;
00985   case Instruction::ExtractElement: NumFastIselFailExtractElement++; return;
00986   case Instruction::InsertElement:  NumFastIselFailInsertElement++; return;
00987   case Instruction::ShuffleVector:  NumFastIselFailShuffleVector++; return;
00988   case Instruction::ExtractValue:   NumFastIselFailExtractValue++; return;
00989   case Instruction::InsertValue:    NumFastIselFailInsertValue++; return;
00990   case Instruction::LandingPad:     NumFastIselFailLandingPad++; return;
00991   }
00992 }
00993 #endif
00994 
00995 void SelectionDAGISel::SelectAllBasicBlocks(const Function &Fn) {
00996   // Initialize the Fast-ISel state, if needed.
00997   FastISel *FastIS = nullptr;
00998   if (TM.Options.EnableFastISel)
00999     FastIS = getTargetLowering()->createFastISel(*FuncInfo, LibInfo);
01000 
01001   // Iterate over all basic blocks in the function.
01002   ReversePostOrderTraversal<const Function*> RPOT(&Fn);
01003   for (ReversePostOrderTraversal<const Function*>::rpo_iterator
01004        I = RPOT.begin(), E = RPOT.end(); I != E; ++I) {
01005     const BasicBlock *LLVMBB = *I;
01006 
01007     if (OptLevel != CodeGenOpt::None) {
01008       bool AllPredsVisited = true;
01009       for (const_pred_iterator PI = pred_begin(LLVMBB), PE = pred_end(LLVMBB);
01010            PI != PE; ++PI) {
01011         if (!FuncInfo->VisitedBBs.count(*PI)) {
01012           AllPredsVisited = false;
01013           break;
01014         }
01015       }
01016 
01017       if (AllPredsVisited) {
01018         for (BasicBlock::const_iterator I = LLVMBB->begin();
01019              const PHINode *PN = dyn_cast<PHINode>(I); ++I)
01020           FuncInfo->ComputePHILiveOutRegInfo(PN);
01021       } else {
01022         for (BasicBlock::const_iterator I = LLVMBB->begin();
01023              const PHINode *PN = dyn_cast<PHINode>(I); ++I)
01024           FuncInfo->InvalidatePHILiveOutRegInfo(PN);
01025       }
01026 
01027       FuncInfo->VisitedBBs.insert(LLVMBB);
01028     }
01029 
01030     BasicBlock::const_iterator const Begin = LLVMBB->getFirstNonPHI();
01031     BasicBlock::const_iterator const End = LLVMBB->end();
01032     BasicBlock::const_iterator BI = End;
01033 
01034     FuncInfo->MBB = FuncInfo->MBBMap[LLVMBB];
01035     FuncInfo->InsertPt = FuncInfo->MBB->getFirstNonPHI();
01036 
01037     // Setup an EH landing-pad block.
01038     FuncInfo->ExceptionPointerVirtReg = 0;
01039     FuncInfo->ExceptionSelectorVirtReg = 0;
01040     if (FuncInfo->MBB->isLandingPad())
01041       PrepareEHLandingPad();
01042 
01043     // Before doing SelectionDAG ISel, see if FastISel has been requested.
01044     if (FastIS) {
01045       FastIS->startNewBlock();
01046 
01047       // Emit code for any incoming arguments. This must happen before
01048       // beginning FastISel on the entry block.
01049       if (LLVMBB == &Fn.getEntryBlock()) {
01050         ++NumEntryBlocks;
01051 
01052         // Lower any arguments needed in this block if this is the entry block.
01053         if (!FastIS->LowerArguments()) {
01054           // Fast isel failed to lower these arguments
01055           ++NumFastIselFailLowerArguments;
01056           if (EnableFastISelAbortArgs)
01057             llvm_unreachable("FastISel didn't lower all arguments");
01058 
01059           // Use SelectionDAG argument lowering
01060           LowerArguments(Fn);
01061           CurDAG->setRoot(SDB->getControlRoot());
01062           SDB->clear();
01063           CodeGenAndEmitDAG();
01064         }
01065 
01066         // If we inserted any instructions at the beginning, make a note of
01067         // where they are, so we can be sure to emit subsequent instructions
01068         // after them.
01069         if (FuncInfo->InsertPt != FuncInfo->MBB->begin())
01070           FastIS->setLastLocalValue(std::prev(FuncInfo->InsertPt));
01071         else
01072           FastIS->setLastLocalValue(nullptr);
01073       }
01074 
01075       unsigned NumFastIselRemaining = std::distance(Begin, End);
01076       // Do FastISel on as many instructions as possible.
01077       for (; BI != Begin; --BI) {
01078         const Instruction *Inst = std::prev(BI);
01079 
01080         // If we no longer require this instruction, skip it.
01081         if (isFoldedOrDeadInstruction(Inst, FuncInfo)) {
01082           --NumFastIselRemaining;
01083           continue;
01084         }
01085 
01086         // Bottom-up: reset the insert pos at the top, after any local-value
01087         // instructions.
01088         FastIS->recomputeInsertPt();
01089 
01090         // Try to select the instruction with FastISel.
01091         if (FastIS->SelectInstruction(Inst)) {
01092           --NumFastIselRemaining;
01093           ++NumFastIselSuccess;
01094           // If fast isel succeeded, skip over all the folded instructions, and
01095           // then see if there is a load right before the selected instructions.
01096           // Try to fold the load if so.
01097           const Instruction *BeforeInst = Inst;
01098           while (BeforeInst != Begin) {
01099             BeforeInst = std::prev(BasicBlock::const_iterator(BeforeInst));
01100             if (!isFoldedOrDeadInstruction(BeforeInst, FuncInfo))
01101               break;
01102           }
01103           if (BeforeInst != Inst && isa<LoadInst>(BeforeInst) &&
01104               BeforeInst->hasOneUse() &&
01105               FastIS->tryToFoldLoad(cast<LoadInst>(BeforeInst), Inst)) {
01106             // If we succeeded, don't re-select the load.
01107             BI = std::next(BasicBlock::const_iterator(BeforeInst));
01108             --NumFastIselRemaining;
01109             ++NumFastIselSuccess;
01110           }
01111           continue;
01112         }
01113 
01114 #ifndef NDEBUG
01115         if (EnableFastISelVerbose2)
01116           collectFailStats(Inst);
01117 #endif
01118 
01119         // Then handle certain instructions as single-LLVM-Instruction blocks.
01120         if (isa<CallInst>(Inst)) {
01121 
01122           if (EnableFastISelVerbose || EnableFastISelAbort) {
01123             dbgs() << "FastISel missed call: ";
01124             Inst->dump();
01125           }
01126 
01127           if (!Inst->getType()->isVoidTy() && !Inst->use_empty()) {
01128             unsigned &R = FuncInfo->ValueMap[Inst];
01129             if (!R)
01130               R = FuncInfo->CreateRegs(Inst->getType());
01131           }
01132 
01133           bool HadTailCall = false;
01134           MachineBasicBlock::iterator SavedInsertPt = FuncInfo->InsertPt;
01135           SelectBasicBlock(Inst, BI, HadTailCall);
01136 
01137           // If the call was emitted as a tail call, we're done with the block.
01138           // We also need to delete any previously emitted instructions.
01139           if (HadTailCall) {
01140             FastIS->removeDeadCode(SavedInsertPt, FuncInfo->MBB->end());
01141             --BI;
01142             break;
01143           }
01144 
01145           // Recompute NumFastIselRemaining as Selection DAG instruction
01146           // selection may have handled the call, input args, etc.
01147           unsigned RemainingNow = std::distance(Begin, BI);
01148           NumFastIselFailures += NumFastIselRemaining - RemainingNow;
01149           NumFastIselRemaining = RemainingNow;
01150           continue;
01151         }
01152 
01153         if (isa<TerminatorInst>(Inst) && !isa<BranchInst>(Inst)) {
01154           // Don't abort, and use a different message for terminator misses.
01155           NumFastIselFailures += NumFastIselRemaining;
01156           if (EnableFastISelVerbose || EnableFastISelAbort) {
01157             dbgs() << "FastISel missed terminator: ";
01158             Inst->dump();
01159           }
01160         } else {
01161           NumFastIselFailures += NumFastIselRemaining;
01162           if (EnableFastISelVerbose || EnableFastISelAbort) {
01163             dbgs() << "FastISel miss: ";
01164             Inst->dump();
01165           }
01166           if (EnableFastISelAbort)
01167             // The "fast" selector couldn't handle something and bailed.
01168             // For the purpose of debugging, just abort.
01169             llvm_unreachable("FastISel didn't select the entire block");
01170         }
01171         break;
01172       }
01173 
01174       FastIS->recomputeInsertPt();
01175     } else {
01176       // Lower any arguments needed in this block if this is the entry block.
01177       if (LLVMBB == &Fn.getEntryBlock()) {
01178         ++NumEntryBlocks;
01179         LowerArguments(Fn);
01180       }
01181     }
01182 
01183     if (Begin != BI)
01184       ++NumDAGBlocks;
01185     else
01186       ++NumFastIselBlocks;
01187 
01188     if (Begin != BI) {
01189       // Run SelectionDAG instruction selection on the remainder of the block
01190       // not handled by FastISel. If FastISel is not run, this is the entire
01191       // block.
01192       bool HadTailCall;
01193       SelectBasicBlock(Begin, BI, HadTailCall);
01194     }
01195 
01196     FinishBasicBlock();
01197     FuncInfo->PHINodesToUpdate.clear();
01198   }
01199 
01200   delete FastIS;
01201   SDB->clearDanglingDebugInfo();
01202   SDB->SPDescriptor.resetPerFunctionState();
01203 }
01204 
01205 /// Given that the input MI is before a partial terminator sequence TSeq, return
01206 /// true if M + TSeq also a partial terminator sequence.
01207 ///
01208 /// A Terminator sequence is a sequence of MachineInstrs which at this point in
01209 /// lowering copy vregs into physical registers, which are then passed into
01210 /// terminator instructors so we can satisfy ABI constraints. A partial
01211 /// terminator sequence is an improper subset of a terminator sequence (i.e. it
01212 /// may be the whole terminator sequence).
01213 static bool MIIsInTerminatorSequence(const MachineInstr *MI) {
01214   // If we do not have a copy or an implicit def, we return true if and only if
01215   // MI is a debug value.
01216   if (!MI->isCopy() && !MI->isImplicitDef())
01217     // Sometimes DBG_VALUE MI sneak in between the copies from the vregs to the
01218     // physical registers if there is debug info associated with the terminator
01219     // of our mbb. We want to include said debug info in our terminator
01220     // sequence, so we return true in that case.
01221     return MI->isDebugValue();
01222 
01223   // We have left the terminator sequence if we are not doing one of the
01224   // following:
01225   //
01226   // 1. Copying a vreg into a physical register.
01227   // 2. Copying a vreg into a vreg.
01228   // 3. Defining a register via an implicit def.
01229 
01230   // OPI should always be a register definition...
01231   MachineInstr::const_mop_iterator OPI = MI->operands_begin();
01232   if (!OPI->isReg() || !OPI->isDef())
01233     return false;
01234 
01235   // Defining any register via an implicit def is always ok.
01236   if (MI->isImplicitDef())
01237     return true;
01238 
01239   // Grab the copy source...
01240   MachineInstr::const_mop_iterator OPI2 = OPI;
01241   ++OPI2;
01242   assert(OPI2 != MI->operands_end()
01243          && "Should have a copy implying we should have 2 arguments.");
01244 
01245   // Make sure that the copy dest is not a vreg when the copy source is a
01246   // physical register.
01247   if (!OPI2->isReg() ||
01248       (!TargetRegisterInfo::isPhysicalRegister(OPI->getReg()) &&
01249        TargetRegisterInfo::isPhysicalRegister(OPI2->getReg())))
01250     return false;
01251 
01252   return true;
01253 }
01254 
01255 /// Find the split point at which to splice the end of BB into its success stack
01256 /// protector check machine basic block.
01257 ///
01258 /// On many platforms, due to ABI constraints, terminators, even before register
01259 /// allocation, use physical registers. This creates an issue for us since
01260 /// physical registers at this point can not travel across basic
01261 /// blocks. Luckily, selectiondag always moves physical registers into vregs
01262 /// when they enter functions and moves them through a sequence of copies back
01263 /// into the physical registers right before the terminator creating a
01264 /// ``Terminator Sequence''. This function is searching for the beginning of the
01265 /// terminator sequence so that we can ensure that we splice off not just the
01266 /// terminator, but additionally the copies that move the vregs into the
01267 /// physical registers.
01268 static MachineBasicBlock::iterator
01269 FindSplitPointForStackProtector(MachineBasicBlock *BB, DebugLoc DL) {
01270   MachineBasicBlock::iterator SplitPoint = BB->getFirstTerminator();
01271   //
01272   if (SplitPoint == BB->begin())
01273     return SplitPoint;
01274 
01275   MachineBasicBlock::iterator Start = BB->begin();
01276   MachineBasicBlock::iterator Previous = SplitPoint;
01277   --Previous;
01278 
01279   while (MIIsInTerminatorSequence(Previous)) {
01280     SplitPoint = Previous;
01281     if (Previous == Start)
01282       break;
01283     --Previous;
01284   }
01285 
01286   return SplitPoint;
01287 }
01288 
01289 void
01290 SelectionDAGISel::FinishBasicBlock() {
01291 
01292   DEBUG(dbgs() << "Total amount of phi nodes to update: "
01293                << FuncInfo->PHINodesToUpdate.size() << "\n";
01294         for (unsigned i = 0, e = FuncInfo->PHINodesToUpdate.size(); i != e; ++i)
01295           dbgs() << "Node " << i << " : ("
01296                  << FuncInfo->PHINodesToUpdate[i].first
01297                  << ", " << FuncInfo->PHINodesToUpdate[i].second << ")\n");
01298 
01299   const bool MustUpdatePHINodes = SDB->SwitchCases.empty() &&
01300                                   SDB->JTCases.empty() &&
01301                                   SDB->BitTestCases.empty();
01302 
01303   // Next, now that we know what the last MBB the LLVM BB expanded is, update
01304   // PHI nodes in successors.
01305   if (MustUpdatePHINodes) {
01306     for (unsigned i = 0, e = FuncInfo->PHINodesToUpdate.size(); i != e; ++i) {
01307       MachineInstrBuilder PHI(*MF, FuncInfo->PHINodesToUpdate[i].first);
01308       assert(PHI->isPHI() &&
01309              "This is not a machine PHI node that we are updating!");
01310       if (!FuncInfo->MBB->isSuccessor(PHI->getParent()))
01311         continue;
01312       PHI.addReg(FuncInfo->PHINodesToUpdate[i].second).addMBB(FuncInfo->MBB);
01313     }
01314   }
01315 
01316   // Handle stack protector.
01317   if (SDB->SPDescriptor.shouldEmitStackProtector()) {
01318     MachineBasicBlock *ParentMBB = SDB->SPDescriptor.getParentMBB();
01319     MachineBasicBlock *SuccessMBB = SDB->SPDescriptor.getSuccessMBB();
01320 
01321     // Find the split point to split the parent mbb. At the same time copy all
01322     // physical registers used in the tail of parent mbb into virtual registers
01323     // before the split point and back into physical registers after the split
01324     // point. This prevents us needing to deal with Live-ins and many other
01325     // register allocation issues caused by us splitting the parent mbb. The
01326     // register allocator will clean up said virtual copies later on.
01327     MachineBasicBlock::iterator SplitPoint =
01328       FindSplitPointForStackProtector(ParentMBB, SDB->getCurDebugLoc());
01329 
01330     // Splice the terminator of ParentMBB into SuccessMBB.
01331     SuccessMBB->splice(SuccessMBB->end(), ParentMBB,
01332                        SplitPoint,
01333                        ParentMBB->end());
01334 
01335     // Add compare/jump on neq/jump to the parent BB.
01336     FuncInfo->MBB = ParentMBB;
01337     FuncInfo->InsertPt = ParentMBB->end();
01338     SDB->visitSPDescriptorParent(SDB->SPDescriptor, ParentMBB);
01339     CurDAG->setRoot(SDB->getRoot());
01340     SDB->clear();
01341     CodeGenAndEmitDAG();
01342 
01343     // CodeGen Failure MBB if we have not codegened it yet.
01344     MachineBasicBlock *FailureMBB = SDB->SPDescriptor.getFailureMBB();
01345     if (!FailureMBB->size()) {
01346       FuncInfo->MBB = FailureMBB;
01347       FuncInfo->InsertPt = FailureMBB->end();
01348       SDB->visitSPDescriptorFailure(SDB->SPDescriptor);
01349       CurDAG->setRoot(SDB->getRoot());
01350       SDB->clear();
01351       CodeGenAndEmitDAG();
01352     }
01353 
01354     // Clear the Per-BB State.
01355     SDB->SPDescriptor.resetPerBBState();
01356   }
01357 
01358   // If we updated PHI Nodes, return early.
01359   if (MustUpdatePHINodes)
01360     return;
01361 
01362   for (unsigned i = 0, e = SDB->BitTestCases.size(); i != e; ++i) {
01363     // Lower header first, if it wasn't already lowered
01364     if (!SDB->BitTestCases[i].Emitted) {
01365       // Set the current basic block to the mbb we wish to insert the code into
01366       FuncInfo->MBB = SDB->BitTestCases[i].Parent;
01367       FuncInfo->InsertPt = FuncInfo->MBB->end();
01368       // Emit the code
01369       SDB->visitBitTestHeader(SDB->BitTestCases[i], FuncInfo->MBB);
01370       CurDAG->setRoot(SDB->getRoot());
01371       SDB->clear();
01372       CodeGenAndEmitDAG();
01373     }
01374 
01375     uint32_t UnhandledWeight = 0;
01376     for (unsigned j = 0, ej = SDB->BitTestCases[i].Cases.size(); j != ej; ++j)
01377       UnhandledWeight += SDB->BitTestCases[i].Cases[j].ExtraWeight;
01378 
01379     for (unsigned j = 0, ej = SDB->BitTestCases[i].Cases.size(); j != ej; ++j) {
01380       UnhandledWeight -= SDB->BitTestCases[i].Cases[j].ExtraWeight;
01381       // Set the current basic block to the mbb we wish to insert the code into
01382       FuncInfo->MBB = SDB->BitTestCases[i].Cases[j].ThisBB;
01383       FuncInfo->InsertPt = FuncInfo->MBB->end();
01384       // Emit the code
01385       if (j+1 != ej)
01386         SDB->visitBitTestCase(SDB->BitTestCases[i],
01387                               SDB->BitTestCases[i].Cases[j+1].ThisBB,
01388                               UnhandledWeight,
01389                               SDB->BitTestCases[i].Reg,
01390                               SDB->BitTestCases[i].Cases[j],
01391                               FuncInfo->MBB);
01392       else
01393         SDB->visitBitTestCase(SDB->BitTestCases[i],
01394                               SDB->BitTestCases[i].Default,
01395                               UnhandledWeight,
01396                               SDB->BitTestCases[i].Reg,
01397                               SDB->BitTestCases[i].Cases[j],
01398                               FuncInfo->MBB);
01399 
01400 
01401       CurDAG->setRoot(SDB->getRoot());
01402       SDB->clear();
01403       CodeGenAndEmitDAG();
01404     }
01405 
01406     // Update PHI Nodes
01407     for (unsigned pi = 0, pe = FuncInfo->PHINodesToUpdate.size();
01408          pi != pe; ++pi) {
01409       MachineInstrBuilder PHI(*MF, FuncInfo->PHINodesToUpdate[pi].first);
01410       MachineBasicBlock *PHIBB = PHI->getParent();
01411       assert(PHI->isPHI() &&
01412              "This is not a machine PHI node that we are updating!");
01413       // This is "default" BB. We have two jumps to it. From "header" BB and
01414       // from last "case" BB.
01415       if (PHIBB == SDB->BitTestCases[i].Default)
01416         PHI.addReg(FuncInfo->PHINodesToUpdate[pi].second)
01417            .addMBB(SDB->BitTestCases[i].Parent)
01418            .addReg(FuncInfo->PHINodesToUpdate[pi].second)
01419            .addMBB(SDB->BitTestCases[i].Cases.back().ThisBB);
01420       // One of "cases" BB.
01421       for (unsigned j = 0, ej = SDB->BitTestCases[i].Cases.size();
01422            j != ej; ++j) {
01423         MachineBasicBlock* cBB = SDB->BitTestCases[i].Cases[j].ThisBB;
01424         if (cBB->isSuccessor(PHIBB))
01425           PHI.addReg(FuncInfo->PHINodesToUpdate[pi].second).addMBB(cBB);
01426       }
01427     }
01428   }
01429   SDB->BitTestCases.clear();
01430 
01431   // If the JumpTable record is filled in, then we need to emit a jump table.
01432   // Updating the PHI nodes is tricky in this case, since we need to determine
01433   // whether the PHI is a successor of the range check MBB or the jump table MBB
01434   for (unsigned i = 0, e = SDB->JTCases.size(); i != e; ++i) {
01435     // Lower header first, if it wasn't already lowered
01436     if (!SDB->JTCases[i].first.Emitted) {
01437       // Set the current basic block to the mbb we wish to insert the code into
01438       FuncInfo->MBB = SDB->JTCases[i].first.HeaderBB;
01439       FuncInfo->InsertPt = FuncInfo->MBB->end();
01440       // Emit the code
01441       SDB->visitJumpTableHeader(SDB->JTCases[i].second, SDB->JTCases[i].first,
01442                                 FuncInfo->MBB);
01443       CurDAG->setRoot(SDB->getRoot());
01444       SDB->clear();
01445       CodeGenAndEmitDAG();
01446     }
01447 
01448     // Set the current basic block to the mbb we wish to insert the code into
01449     FuncInfo->MBB = SDB->JTCases[i].second.MBB;
01450     FuncInfo->InsertPt = FuncInfo->MBB->end();
01451     // Emit the code
01452     SDB->visitJumpTable(SDB->JTCases[i].second);
01453     CurDAG->setRoot(SDB->getRoot());
01454     SDB->clear();
01455     CodeGenAndEmitDAG();
01456 
01457     // Update PHI Nodes
01458     for (unsigned pi = 0, pe = FuncInfo->PHINodesToUpdate.size();
01459          pi != pe; ++pi) {
01460       MachineInstrBuilder PHI(*MF, FuncInfo->PHINodesToUpdate[pi].first);
01461       MachineBasicBlock *PHIBB = PHI->getParent();
01462       assert(PHI->isPHI() &&
01463              "This is not a machine PHI node that we are updating!");
01464       // "default" BB. We can go there only from header BB.
01465       if (PHIBB == SDB->JTCases[i].second.Default)
01466         PHI.addReg(FuncInfo->PHINodesToUpdate[pi].second)
01467            .addMBB(SDB->JTCases[i].first.HeaderBB);
01468       // JT BB. Just iterate over successors here
01469       if (FuncInfo->MBB->isSuccessor(PHIBB))
01470         PHI.addReg(FuncInfo->PHINodesToUpdate[pi].second).addMBB(FuncInfo->MBB);
01471     }
01472   }
01473   SDB->JTCases.clear();
01474 
01475   // If the switch block involved a branch to one of the actual successors, we
01476   // need to update PHI nodes in that block.
01477   for (unsigned i = 0, e = FuncInfo->PHINodesToUpdate.size(); i != e; ++i) {
01478     MachineInstrBuilder PHI(*MF, FuncInfo->PHINodesToUpdate[i].first);
01479     assert(PHI->isPHI() &&
01480            "This is not a machine PHI node that we are updating!");
01481     if (FuncInfo->MBB->isSuccessor(PHI->getParent()))
01482       PHI.addReg(FuncInfo->PHINodesToUpdate[i].second).addMBB(FuncInfo->MBB);
01483   }
01484 
01485   // If we generated any switch lowering information, build and codegen any
01486   // additional DAGs necessary.
01487   for (unsigned i = 0, e = SDB->SwitchCases.size(); i != e; ++i) {
01488     // Set the current basic block to the mbb we wish to insert the code into
01489     FuncInfo->MBB = SDB->SwitchCases[i].ThisBB;
01490     FuncInfo->InsertPt = FuncInfo->MBB->end();
01491 
01492     // Determine the unique successors.
01493     SmallVector<MachineBasicBlock *, 2> Succs;
01494     Succs.push_back(SDB->SwitchCases[i].TrueBB);
01495     if (SDB->SwitchCases[i].TrueBB != SDB->SwitchCases[i].FalseBB)
01496       Succs.push_back(SDB->SwitchCases[i].FalseBB);
01497 
01498     // Emit the code. Note that this could result in FuncInfo->MBB being split.
01499     SDB->visitSwitchCase(SDB->SwitchCases[i], FuncInfo->MBB);
01500     CurDAG->setRoot(SDB->getRoot());
01501     SDB->clear();
01502     CodeGenAndEmitDAG();
01503 
01504     // Remember the last block, now that any splitting is done, for use in
01505     // populating PHI nodes in successors.
01506     MachineBasicBlock *ThisBB = FuncInfo->MBB;
01507 
01508     // Handle any PHI nodes in successors of this chunk, as if we were coming
01509     // from the original BB before switch expansion.  Note that PHI nodes can
01510     // occur multiple times in PHINodesToUpdate.  We have to be very careful to
01511     // handle them the right number of times.
01512     for (unsigned i = 0, e = Succs.size(); i != e; ++i) {
01513       FuncInfo->MBB = Succs[i];
01514       FuncInfo->InsertPt = FuncInfo->MBB->end();
01515       // FuncInfo->MBB may have been removed from the CFG if a branch was
01516       // constant folded.
01517       if (ThisBB->isSuccessor(FuncInfo->MBB)) {
01518         for (MachineBasicBlock::iterator
01519              MBBI = FuncInfo->MBB->begin(), MBBE = FuncInfo->MBB->end();
01520              MBBI != MBBE && MBBI->isPHI(); ++MBBI) {
01521           MachineInstrBuilder PHI(*MF, MBBI);
01522           // This value for this PHI node is recorded in PHINodesToUpdate.
01523           for (unsigned pn = 0; ; ++pn) {
01524             assert(pn != FuncInfo->PHINodesToUpdate.size() &&
01525                    "Didn't find PHI entry!");
01526             if (FuncInfo->PHINodesToUpdate[pn].first == PHI) {
01527               PHI.addReg(FuncInfo->PHINodesToUpdate[pn].second).addMBB(ThisBB);
01528               break;
01529             }
01530           }
01531         }
01532       }
01533     }
01534   }
01535   SDB->SwitchCases.clear();
01536 }
01537 
01538 
01539 /// Create the scheduler. If a specific scheduler was specified
01540 /// via the SchedulerRegistry, use it, otherwise select the
01541 /// one preferred by the target.
01542 ///
01543 ScheduleDAGSDNodes *SelectionDAGISel::CreateScheduler() {
01544   RegisterScheduler::FunctionPassCtor Ctor = RegisterScheduler::getDefault();
01545 
01546   if (!Ctor) {
01547     Ctor = ISHeuristic;
01548     RegisterScheduler::setDefault(Ctor);
01549   }
01550 
01551   return Ctor(this, OptLevel);
01552 }
01553 
01554 //===----------------------------------------------------------------------===//
01555 // Helper functions used by the generated instruction selector.
01556 //===----------------------------------------------------------------------===//
01557 // Calls to these methods are generated by tblgen.
01558 
01559 /// CheckAndMask - The isel is trying to match something like (and X, 255).  If
01560 /// the dag combiner simplified the 255, we still want to match.  RHS is the
01561 /// actual value in the DAG on the RHS of an AND, and DesiredMaskS is the value
01562 /// specified in the .td file (e.g. 255).
01563 bool SelectionDAGISel::CheckAndMask(SDValue LHS, ConstantSDNode *RHS,
01564                                     int64_t DesiredMaskS) const {
01565   const APInt &ActualMask = RHS->getAPIntValue();
01566   const APInt &DesiredMask = APInt(LHS.getValueSizeInBits(), DesiredMaskS);
01567 
01568   // If the actual mask exactly matches, success!
01569   if (ActualMask == DesiredMask)
01570     return true;
01571 
01572   // If the actual AND mask is allowing unallowed bits, this doesn't match.
01573   if (ActualMask.intersects(~DesiredMask))
01574     return false;
01575 
01576   // Otherwise, the DAG Combiner may have proven that the value coming in is
01577   // either already zero or is not demanded.  Check for known zero input bits.
01578   APInt NeededMask = DesiredMask & ~ActualMask;
01579   if (CurDAG->MaskedValueIsZero(LHS, NeededMask))
01580     return true;
01581 
01582   // TODO: check to see if missing bits are just not demanded.
01583 
01584   // Otherwise, this pattern doesn't match.
01585   return false;
01586 }
01587 
01588 /// CheckOrMask - The isel is trying to match something like (or X, 255).  If
01589 /// the dag combiner simplified the 255, we still want to match.  RHS is the
01590 /// actual value in the DAG on the RHS of an OR, and DesiredMaskS is the value
01591 /// specified in the .td file (e.g. 255).
01592 bool SelectionDAGISel::CheckOrMask(SDValue LHS, ConstantSDNode *RHS,
01593                                    int64_t DesiredMaskS) const {
01594   const APInt &ActualMask = RHS->getAPIntValue();
01595   const APInt &DesiredMask = APInt(LHS.getValueSizeInBits(), DesiredMaskS);
01596 
01597   // If the actual mask exactly matches, success!
01598   if (ActualMask == DesiredMask)
01599     return true;
01600 
01601   // If the actual AND mask is allowing unallowed bits, this doesn't match.
01602   if (ActualMask.intersects(~DesiredMask))
01603     return false;
01604 
01605   // Otherwise, the DAG Combiner may have proven that the value coming in is
01606   // either already zero or is not demanded.  Check for known zero input bits.
01607   APInt NeededMask = DesiredMask & ~ActualMask;
01608 
01609   APInt KnownZero, KnownOne;
01610   CurDAG->ComputeMaskedBits(LHS, KnownZero, KnownOne);
01611 
01612   // If all the missing bits in the or are already known to be set, match!
01613   if ((NeededMask & KnownOne) == NeededMask)
01614     return true;
01615 
01616   // TODO: check to see if missing bits are just not demanded.
01617 
01618   // Otherwise, this pattern doesn't match.
01619   return false;
01620 }
01621 
01622 
01623 /// SelectInlineAsmMemoryOperands - Calls to this are automatically generated
01624 /// by tblgen.  Others should not call it.
01625 void SelectionDAGISel::
01626 SelectInlineAsmMemoryOperands(std::vector<SDValue> &Ops) {
01627   std::vector<SDValue> InOps;
01628   std::swap(InOps, Ops);
01629 
01630   Ops.push_back(InOps[InlineAsm::Op_InputChain]); // 0
01631   Ops.push_back(InOps[InlineAsm::Op_AsmString]);  // 1
01632   Ops.push_back(InOps[InlineAsm::Op_MDNode]);     // 2, !srcloc
01633   Ops.push_back(InOps[InlineAsm::Op_ExtraInfo]);  // 3 (SideEffect, AlignStack)
01634 
01635   unsigned i = InlineAsm::Op_FirstOperand, e = InOps.size();
01636   if (InOps[e-1].getValueType() == MVT::Glue)
01637     --e;  // Don't process a glue operand if it is here.
01638 
01639   while (i != e) {
01640     unsigned Flags = cast<ConstantSDNode>(InOps[i])->getZExtValue();
01641     if (!InlineAsm::isMemKind(Flags)) {
01642       // Just skip over this operand, copying the operands verbatim.
01643       Ops.insert(Ops.end(), InOps.begin()+i,
01644                  InOps.begin()+i+InlineAsm::getNumOperandRegisters(Flags) + 1);
01645       i += InlineAsm::getNumOperandRegisters(Flags) + 1;
01646     } else {
01647       assert(InlineAsm::getNumOperandRegisters(Flags) == 1 &&
01648              "Memory operand with multiple values?");
01649       // Otherwise, this is a memory operand.  Ask the target to select it.
01650       std::vector<SDValue> SelOps;
01651       if (SelectInlineAsmMemoryOperand(InOps[i+1], 'm', SelOps))
01652         report_fatal_error("Could not match memory address.  Inline asm"
01653                            " failure!");
01654 
01655       // Add this to the output node.
01656       unsigned NewFlags =
01657         InlineAsm::getFlagWord(InlineAsm::Kind_Mem, SelOps.size());
01658       Ops.push_back(CurDAG->getTargetConstant(NewFlags, MVT::i32));
01659       Ops.insert(Ops.end(), SelOps.begin(), SelOps.end());
01660       i += 2;
01661     }
01662   }
01663 
01664   // Add the glue input back if present.
01665   if (e != InOps.size())
01666     Ops.push_back(InOps.back());
01667 }
01668 
01669 /// findGlueUse - Return use of MVT::Glue value produced by the specified
01670 /// SDNode.
01671 ///
01672 static SDNode *findGlueUse(SDNode *N) {
01673   unsigned FlagResNo = N->getNumValues()-1;
01674   for (SDNode::use_iterator I = N->use_begin(), E = N->use_end(); I != E; ++I) {
01675     SDUse &Use = I.getUse();
01676     if (Use.getResNo() == FlagResNo)
01677       return Use.getUser();
01678   }
01679   return nullptr;
01680 }
01681 
01682 /// findNonImmUse - Return true if "Use" is a non-immediate use of "Def".
01683 /// This function recursively traverses up the operand chain, ignoring
01684 /// certain nodes.
01685 static bool findNonImmUse(SDNode *Use, SDNode* Def, SDNode *ImmedUse,
01686                           SDNode *Root, SmallPtrSet<SDNode*, 16> &Visited,
01687                           bool IgnoreChains) {
01688   // The NodeID's are given uniques ID's where a node ID is guaranteed to be
01689   // greater than all of its (recursive) operands.  If we scan to a point where
01690   // 'use' is smaller than the node we're scanning for, then we know we will
01691   // never find it.
01692   //
01693   // The Use may be -1 (unassigned) if it is a newly allocated node.  This can
01694   // happen because we scan down to newly selected nodes in the case of glue
01695   // uses.
01696   if ((Use->getNodeId() < Def->getNodeId() && Use->getNodeId() != -1))
01697     return false;
01698 
01699   // Don't revisit nodes if we already scanned it and didn't fail, we know we
01700   // won't fail if we scan it again.
01701   if (!Visited.insert(Use))
01702     return false;
01703 
01704   for (unsigned i = 0, e = Use->getNumOperands(); i != e; ++i) {
01705     // Ignore chain uses, they are validated by HandleMergeInputChains.
01706     if (Use->getOperand(i).getValueType() == MVT::Other && IgnoreChains)
01707       continue;
01708 
01709     SDNode *N = Use->getOperand(i).getNode();
01710     if (N == Def) {
01711       if (Use == ImmedUse || Use == Root)
01712         continue;  // We are not looking for immediate use.
01713       assert(N != Root);
01714       return true;
01715     }
01716 
01717     // Traverse up the operand chain.
01718     if (findNonImmUse(N, Def, ImmedUse, Root, Visited, IgnoreChains))
01719       return true;
01720   }
01721   return false;
01722 }
01723 
01724 /// IsProfitableToFold - Returns true if it's profitable to fold the specific
01725 /// operand node N of U during instruction selection that starts at Root.
01726 bool SelectionDAGISel::IsProfitableToFold(SDValue N, SDNode *U,
01727                                           SDNode *Root) const {
01728   if (OptLevel == CodeGenOpt::None) return false;
01729   return N.hasOneUse();
01730 }
01731 
01732 /// IsLegalToFold - Returns true if the specific operand node N of
01733 /// U can be folded during instruction selection that starts at Root.
01734 bool SelectionDAGISel::IsLegalToFold(SDValue N, SDNode *U, SDNode *Root,
01735                                      CodeGenOpt::Level OptLevel,
01736                                      bool IgnoreChains) {
01737   if (OptLevel == CodeGenOpt::None) return false;
01738 
01739   // If Root use can somehow reach N through a path that that doesn't contain
01740   // U then folding N would create a cycle. e.g. In the following
01741   // diagram, Root can reach N through X. If N is folded into into Root, then
01742   // X is both a predecessor and a successor of U.
01743   //
01744   //          [N*]           //
01745   //         ^   ^           //
01746   //        /     \          //
01747   //      [U*]    [X]?       //
01748   //        ^     ^          //
01749   //         \   /           //
01750   //          \ /            //
01751   //         [Root*]         //
01752   //
01753   // * indicates nodes to be folded together.
01754   //
01755   // If Root produces glue, then it gets (even more) interesting. Since it
01756   // will be "glued" together with its glue use in the scheduler, we need to
01757   // check if it might reach N.
01758   //
01759   //          [N*]           //
01760   //         ^   ^           //
01761   //        /     \          //
01762   //      [U*]    [X]?       //
01763   //        ^       ^        //
01764   //         \       \       //
01765   //          \      |       //
01766   //         [Root*] |       //
01767   //          ^      |       //
01768   //          f      |       //
01769   //          |      /       //
01770   //         [Y]    /        //
01771   //           ^   /         //
01772   //           f  /          //
01773   //           | /           //
01774   //          [GU]           //
01775   //
01776   // If GU (glue use) indirectly reaches N (the load), and Root folds N
01777   // (call it Fold), then X is a predecessor of GU and a successor of
01778   // Fold. But since Fold and GU are glued together, this will create
01779   // a cycle in the scheduling graph.
01780 
01781   // If the node has glue, walk down the graph to the "lowest" node in the
01782   // glueged set.
01783   EVT VT = Root->getValueType(Root->getNumValues()-1);
01784   while (VT == MVT::Glue) {
01785     SDNode *GU = findGlueUse(Root);
01786     if (!GU)
01787       break;
01788     Root = GU;
01789     VT = Root->getValueType(Root->getNumValues()-1);
01790 
01791     // If our query node has a glue result with a use, we've walked up it.  If
01792     // the user (which has already been selected) has a chain or indirectly uses
01793     // the chain, our WalkChainUsers predicate will not consider it.  Because of
01794     // this, we cannot ignore chains in this predicate.
01795     IgnoreChains = false;
01796   }
01797 
01798 
01799   SmallPtrSet<SDNode*, 16> Visited;
01800   return !findNonImmUse(Root, N.getNode(), U, Root, Visited, IgnoreChains);
01801 }
01802 
01803 SDNode *SelectionDAGISel::Select_INLINEASM(SDNode *N) {
01804   std::vector<SDValue> Ops(N->op_begin(), N->op_end());
01805   SelectInlineAsmMemoryOperands(Ops);
01806 
01807   EVT VTs[] = { MVT::Other, MVT::Glue };
01808   SDValue New = CurDAG->getNode(ISD::INLINEASM, SDLoc(N),
01809                                 VTs, &Ops[0], Ops.size());
01810   New->setNodeId(-1);
01811   return New.getNode();
01812 }
01813 
01814 SDNode *SelectionDAGISel::Select_UNDEF(SDNode *N) {
01815   return CurDAG->SelectNodeTo(N, TargetOpcode::IMPLICIT_DEF,N->getValueType(0));
01816 }
01817 
01818 /// GetVBR - decode a vbr encoding whose top bit is set.
01819 LLVM_ATTRIBUTE_ALWAYS_INLINE static uint64_t
01820 GetVBR(uint64_t Val, const unsigned char *MatcherTable, unsigned &Idx) {
01821   assert(Val >= 128 && "Not a VBR");
01822   Val &= 127;  // Remove first vbr bit.
01823 
01824   unsigned Shift = 7;
01825   uint64_t NextBits;
01826   do {
01827     NextBits = MatcherTable[Idx++];
01828     Val |= (NextBits&127) << Shift;
01829     Shift += 7;
01830   } while (NextBits & 128);
01831 
01832   return Val;
01833 }
01834 
01835 
01836 /// UpdateChainsAndGlue - When a match is complete, this method updates uses of
01837 /// interior glue and chain results to use the new glue and chain results.
01838 void SelectionDAGISel::
01839 UpdateChainsAndGlue(SDNode *NodeToMatch, SDValue InputChain,
01840                     const SmallVectorImpl<SDNode*> &ChainNodesMatched,
01841                     SDValue InputGlue,
01842                     const SmallVectorImpl<SDNode*> &GlueResultNodesMatched,
01843                     bool isMorphNodeTo) {
01844   SmallVector<SDNode*, 4> NowDeadNodes;
01845 
01846   // Now that all the normal results are replaced, we replace the chain and
01847   // glue results if present.
01848   if (!ChainNodesMatched.empty()) {
01849     assert(InputChain.getNode() &&
01850            "Matched input chains but didn't produce a chain");
01851     // Loop over all of the nodes we matched that produced a chain result.
01852     // Replace all the chain results with the final chain we ended up with.
01853     for (unsigned i = 0, e = ChainNodesMatched.size(); i != e; ++i) {
01854       SDNode *ChainNode = ChainNodesMatched[i];
01855 
01856       // If this node was already deleted, don't look at it.
01857       if (ChainNode->getOpcode() == ISD::DELETED_NODE)
01858         continue;
01859 
01860       // Don't replace the results of the root node if we're doing a
01861       // MorphNodeTo.
01862       if (ChainNode == NodeToMatch && isMorphNodeTo)
01863         continue;
01864 
01865       SDValue ChainVal = SDValue(ChainNode, ChainNode->getNumValues()-1);
01866       if (ChainVal.getValueType() == MVT::Glue)
01867         ChainVal = ChainVal.getValue(ChainVal->getNumValues()-2);
01868       assert(ChainVal.getValueType() == MVT::Other && "Not a chain?");
01869       CurDAG->ReplaceAllUsesOfValueWith(ChainVal, InputChain);
01870 
01871       // If the node became dead and we haven't already seen it, delete it.
01872       if (ChainNode->use_empty() &&
01873           !std::count(NowDeadNodes.begin(), NowDeadNodes.end(), ChainNode))
01874         NowDeadNodes.push_back(ChainNode);
01875     }
01876   }
01877 
01878   // If the result produces glue, update any glue results in the matched
01879   // pattern with the glue result.
01880   if (InputGlue.getNode()) {
01881     // Handle any interior nodes explicitly marked.
01882     for (unsigned i = 0, e = GlueResultNodesMatched.size(); i != e; ++i) {
01883       SDNode *FRN = GlueResultNodesMatched[i];
01884 
01885       // If this node was already deleted, don't look at it.
01886       if (FRN->getOpcode() == ISD::DELETED_NODE)
01887         continue;
01888 
01889       assert(FRN->getValueType(FRN->getNumValues()-1) == MVT::Glue &&
01890              "Doesn't have a glue result");
01891       CurDAG->ReplaceAllUsesOfValueWith(SDValue(FRN, FRN->getNumValues()-1),
01892                                         InputGlue);
01893 
01894       // If the node became dead and we haven't already seen it, delete it.
01895       if (FRN->use_empty() &&
01896           !std::count(NowDeadNodes.begin(), NowDeadNodes.end(), FRN))
01897         NowDeadNodes.push_back(FRN);
01898     }
01899   }
01900 
01901   if (!NowDeadNodes.empty())
01902     CurDAG->RemoveDeadNodes(NowDeadNodes);
01903 
01904   DEBUG(dbgs() << "ISEL: Match complete!\n");
01905 }
01906 
01907 enum ChainResult {
01908   CR_Simple,
01909   CR_InducesCycle,
01910   CR_LeadsToInteriorNode
01911 };
01912 
01913 /// WalkChainUsers - Walk down the users of the specified chained node that is
01914 /// part of the pattern we're matching, looking at all of the users we find.
01915 /// This determines whether something is an interior node, whether we have a
01916 /// non-pattern node in between two pattern nodes (which prevent folding because
01917 /// it would induce a cycle) and whether we have a TokenFactor node sandwiched
01918 /// between pattern nodes (in which case the TF becomes part of the pattern).
01919 ///
01920 /// The walk we do here is guaranteed to be small because we quickly get down to
01921 /// already selected nodes "below" us.
01922 static ChainResult
01923 WalkChainUsers(const SDNode *ChainedNode,
01924                SmallVectorImpl<SDNode*> &ChainedNodesInPattern,
01925                SmallVectorImpl<SDNode*> &InteriorChainedNodes) {
01926   ChainResult Result = CR_Simple;
01927 
01928   for (SDNode::use_iterator UI = ChainedNode->use_begin(),
01929          E = ChainedNode->use_end(); UI != E; ++UI) {
01930     // Make sure the use is of the chain, not some other value we produce.
01931     if (UI.getUse().getValueType() != MVT::Other) continue;
01932 
01933     SDNode *User = *UI;
01934 
01935     if (User->getOpcode() == ISD::HANDLENODE)  // Root of the graph.
01936       continue;
01937 
01938     // If we see an already-selected machine node, then we've gone beyond the
01939     // pattern that we're selecting down into the already selected chunk of the
01940     // DAG.
01941     unsigned UserOpcode = User->getOpcode();
01942     if (User->isMachineOpcode() ||
01943         UserOpcode == ISD::CopyToReg ||
01944         UserOpcode == ISD::CopyFromReg ||
01945         UserOpcode == ISD::INLINEASM ||
01946         UserOpcode == ISD::EH_LABEL ||
01947         UserOpcode == ISD::LIFETIME_START ||
01948         UserOpcode == ISD::LIFETIME_END) {
01949       // If their node ID got reset to -1 then they've already been selected.
01950       // Treat them like a MachineOpcode.
01951       if (User->getNodeId() == -1)
01952         continue;
01953     }
01954 
01955     // If we have a TokenFactor, we handle it specially.
01956     if (User->getOpcode() != ISD::TokenFactor) {
01957       // If the node isn't a token factor and isn't part of our pattern, then it
01958       // must be a random chained node in between two nodes we're selecting.
01959       // This happens when we have something like:
01960       //   x = load ptr
01961       //   call
01962       //   y = x+4
01963       //   store y -> ptr
01964       // Because we structurally match the load/store as a read/modify/write,
01965       // but the call is chained between them.  We cannot fold in this case
01966       // because it would induce a cycle in the graph.
01967       if (!std::count(ChainedNodesInPattern.begin(),
01968                       ChainedNodesInPattern.end(), User))
01969         return CR_InducesCycle;
01970 
01971       // Otherwise we found a node that is part of our pattern.  For example in:
01972       //   x = load ptr
01973       //   y = x+4
01974       //   store y -> ptr
01975       // This would happen when we're scanning down from the load and see the
01976       // store as a user.  Record that there is a use of ChainedNode that is
01977       // part of the pattern and keep scanning uses.
01978       Result = CR_LeadsToInteriorNode;
01979       InteriorChainedNodes.push_back(User);
01980       continue;
01981     }
01982 
01983     // If we found a TokenFactor, there are two cases to consider: first if the
01984     // TokenFactor is just hanging "below" the pattern we're matching (i.e. no
01985     // uses of the TF are in our pattern) we just want to ignore it.  Second,
01986     // the TokenFactor can be sandwiched in between two chained nodes, like so:
01987     //     [Load chain]
01988     //         ^
01989     //         |
01990     //       [Load]
01991     //       ^    ^
01992     //       |    \                    DAG's like cheese
01993     //      /       \                       do you?
01994     //     /         |
01995     // [TokenFactor] [Op]
01996     //     ^          ^
01997     //     |          |
01998     //      \        /
01999     //       \      /
02000     //       [Store]
02001     //
02002     // In this case, the TokenFactor becomes part of our match and we rewrite it
02003     // as a new TokenFactor.
02004     //
02005     // To distinguish these two cases, do a recursive walk down the uses.
02006     switch (WalkChainUsers(User, ChainedNodesInPattern, InteriorChainedNodes)) {
02007     case CR_Simple:
02008       // If the uses of the TokenFactor are just already-selected nodes, ignore
02009       // it, it is "below" our pattern.
02010       continue;
02011     case CR_InducesCycle:
02012       // If the uses of the TokenFactor lead to nodes that are not part of our
02013       // pattern that are not selected, folding would turn this into a cycle,
02014       // bail out now.
02015       return CR_InducesCycle;
02016     case CR_LeadsToInteriorNode:
02017       break;  // Otherwise, keep processing.
02018     }
02019 
02020     // Okay, we know we're in the interesting interior case.  The TokenFactor
02021     // is now going to be considered part of the pattern so that we rewrite its
02022     // uses (it may have uses that are not part of the pattern) with the
02023     // ultimate chain result of the generated code.  We will also add its chain
02024     // inputs as inputs to the ultimate TokenFactor we create.
02025     Result = CR_LeadsToInteriorNode;
02026     ChainedNodesInPattern.push_back(User);
02027     InteriorChainedNodes.push_back(User);
02028     continue;
02029   }
02030 
02031   return Result;
02032 }
02033 
02034 /// HandleMergeInputChains - This implements the OPC_EmitMergeInputChains
02035 /// operation for when the pattern matched at least one node with a chains.  The
02036 /// input vector contains a list of all of the chained nodes that we match.  We
02037 /// must determine if this is a valid thing to cover (i.e. matching it won't
02038 /// induce cycles in the DAG) and if so, creating a TokenFactor node. that will
02039 /// be used as the input node chain for the generated nodes.
02040 static SDValue
02041 HandleMergeInputChains(SmallVectorImpl<SDNode*> &ChainNodesMatched,
02042                        SelectionDAG *CurDAG) {
02043   // Walk all of the chained nodes we've matched, recursively scanning down the
02044   // users of the chain result. This adds any TokenFactor nodes that are caught
02045   // in between chained nodes to the chained and interior nodes list.
02046   SmallVector<SDNode*, 3> InteriorChainedNodes;
02047   for (unsigned i = 0, e = ChainNodesMatched.size(); i != e; ++i) {
02048     if (WalkChainUsers(ChainNodesMatched[i], ChainNodesMatched,
02049                        InteriorChainedNodes) == CR_InducesCycle)
02050       return SDValue(); // Would induce a cycle.
02051   }
02052 
02053   // Okay, we have walked all the matched nodes and collected TokenFactor nodes
02054   // that we are interested in.  Form our input TokenFactor node.
02055   SmallVector<SDValue, 3> InputChains;
02056   for (unsigned i = 0, e = ChainNodesMatched.size(); i != e; ++i) {
02057     // Add the input chain of this node to the InputChains list (which will be
02058     // the operands of the generated TokenFactor) if it's not an interior node.
02059     SDNode *N = ChainNodesMatched[i];
02060     if (N->getOpcode() != ISD::TokenFactor) {
02061       if (std::count(InteriorChainedNodes.begin(),InteriorChainedNodes.end(),N))
02062         continue;
02063 
02064       // Otherwise, add the input chain.
02065       SDValue InChain = ChainNodesMatched[i]->getOperand(0);
02066       assert(InChain.getValueType() == MVT::Other && "Not a chain");
02067       InputChains.push_back(InChain);
02068       continue;
02069     }
02070 
02071     // If we have a token factor, we want to add all inputs of the token factor
02072     // that are not part of the pattern we're matching.
02073     for (unsigned op = 0, e = N->getNumOperands(); op != e; ++op) {
02074       if (!std::count(ChainNodesMatched.begin(), ChainNodesMatched.end(),
02075                       N->getOperand(op).getNode()))
02076         InputChains.push_back(N->getOperand(op));
02077     }
02078   }
02079 
02080   if (InputChains.size() == 1)
02081     return InputChains[0];
02082   return CurDAG->getNode(ISD::TokenFactor, SDLoc(ChainNodesMatched[0]),
02083                          MVT::Other, &InputChains[0], InputChains.size());
02084 }
02085 
02086 /// MorphNode - Handle morphing a node in place for the selector.
02087 SDNode *SelectionDAGISel::
02088 MorphNode(SDNode *Node, unsigned TargetOpc, SDVTList VTList,
02089           const SDValue *Ops, unsigned NumOps, unsigned EmitNodeInfo) {
02090   // It is possible we're using MorphNodeTo to replace a node with no
02091   // normal results with one that has a normal result (or we could be
02092   // adding a chain) and the input could have glue and chains as well.
02093   // In this case we need to shift the operands down.
02094   // FIXME: This is a horrible hack and broken in obscure cases, no worse
02095   // than the old isel though.
02096   int OldGlueResultNo = -1, OldChainResultNo = -1;
02097 
02098   unsigned NTMNumResults = Node->getNumValues();
02099   if (Node->getValueType(NTMNumResults-1) == MVT::Glue) {
02100     OldGlueResultNo = NTMNumResults-1;
02101     if (NTMNumResults != 1 &&
02102         Node->getValueType(NTMNumResults-2) == MVT::Other)
02103       OldChainResultNo = NTMNumResults-2;
02104   } else if (Node->getValueType(NTMNumResults-1) == MVT::Other)
02105     OldChainResultNo = NTMNumResults-1;
02106 
02107   // Call the underlying SelectionDAG routine to do the transmogrification. Note
02108   // that this deletes operands of the old node that become dead.
02109   SDNode *Res = CurDAG->MorphNodeTo(Node, ~TargetOpc, VTList, Ops, NumOps);
02110 
02111   // MorphNodeTo can operate in two ways: if an existing node with the
02112   // specified operands exists, it can just return it.  Otherwise, it
02113   // updates the node in place to have the requested operands.
02114   if (Res == Node) {
02115     // If we updated the node in place, reset the node ID.  To the isel,
02116     // this should be just like a newly allocated machine node.
02117     Res->setNodeId(-1);
02118   }
02119 
02120   unsigned ResNumResults = Res->getNumValues();
02121   // Move the glue if needed.
02122   if ((EmitNodeInfo & OPFL_GlueOutput) && OldGlueResultNo != -1 &&
02123       (unsigned)OldGlueResultNo != ResNumResults-1)
02124     CurDAG->ReplaceAllUsesOfValueWith(SDValue(Node, OldGlueResultNo),
02125                                       SDValue(Res, ResNumResults-1));
02126 
02127   if ((EmitNodeInfo & OPFL_GlueOutput) != 0)
02128     --ResNumResults;
02129 
02130   // Move the chain reference if needed.
02131   if ((EmitNodeInfo & OPFL_Chain) && OldChainResultNo != -1 &&
02132       (unsigned)OldChainResultNo != ResNumResults-1)
02133     CurDAG->ReplaceAllUsesOfValueWith(SDValue(Node, OldChainResultNo),
02134                                       SDValue(Res, ResNumResults-1));
02135 
02136   // Otherwise, no replacement happened because the node already exists. Replace
02137   // Uses of the old node with the new one.
02138   if (Res != Node)
02139     CurDAG->ReplaceAllUsesWith(Node, Res);
02140 
02141   return Res;
02142 }
02143 
02144 /// CheckSame - Implements OP_CheckSame.
02145 LLVM_ATTRIBUTE_ALWAYS_INLINE static bool
02146 CheckSame(const unsigned char *MatcherTable, unsigned &MatcherIndex,
02147           SDValue N,
02148           const SmallVectorImpl<std::pair<SDValue, SDNode*> > &RecordedNodes) {
02149   // Accept if it is exactly the same as a previously recorded node.
02150   unsigned RecNo = MatcherTable[MatcherIndex++];
02151   assert(RecNo < RecordedNodes.size() && "Invalid CheckSame");
02152   return N == RecordedNodes[RecNo].first;
02153 }
02154 
02155 /// CheckChildSame - Implements OP_CheckChildXSame.
02156 LLVM_ATTRIBUTE_ALWAYS_INLINE static bool
02157 CheckChildSame(const unsigned char *MatcherTable, unsigned &MatcherIndex,
02158              SDValue N,
02159              const SmallVectorImpl<std::pair<SDValue, SDNode*> > &RecordedNodes,
02160              unsigned ChildNo) {
02161   if (ChildNo >= N.getNumOperands())
02162     return false;  // Match fails if out of range child #.
02163   return ::CheckSame(MatcherTable, MatcherIndex, N.getOperand(ChildNo),
02164                      RecordedNodes);
02165 }
02166 
02167 /// CheckPatternPredicate - Implements OP_CheckPatternPredicate.
02168 LLVM_ATTRIBUTE_ALWAYS_INLINE static bool
02169 CheckPatternPredicate(const unsigned char *MatcherTable, unsigned &MatcherIndex,
02170                       const SelectionDAGISel &SDISel) {
02171   return SDISel.CheckPatternPredicate(MatcherTable[MatcherIndex++]);
02172 }
02173 
02174 /// CheckNodePredicate - Implements OP_CheckNodePredicate.
02175 LLVM_ATTRIBUTE_ALWAYS_INLINE static bool
02176 CheckNodePredicate(const unsigned char *MatcherTable, unsigned &MatcherIndex,
02177                    const SelectionDAGISel &SDISel, SDNode *N) {
02178   return SDISel.CheckNodePredicate(N, MatcherTable[MatcherIndex++]);
02179 }
02180 
02181 LLVM_ATTRIBUTE_ALWAYS_INLINE static bool
02182 CheckOpcode(const unsigned char *MatcherTable, unsigned &MatcherIndex,
02183             SDNode *N) {
02184   uint16_t Opc = MatcherTable[MatcherIndex++];
02185   Opc |= (unsigned short)MatcherTable[MatcherIndex++] << 8;
02186   return N->getOpcode() == Opc;
02187 }
02188 
02189 LLVM_ATTRIBUTE_ALWAYS_INLINE static bool
02190 CheckType(const unsigned char *MatcherTable, unsigned &MatcherIndex,
02191           SDValue N, const TargetLowering *TLI) {
02192   MVT::SimpleValueType VT = (MVT::SimpleValueType)MatcherTable[MatcherIndex++];
02193   if (N.getValueType() == VT) return true;
02194 
02195   // Handle the case when VT is iPTR.
02196   return VT == MVT::iPTR && N.getValueType() == TLI->getPointerTy();
02197 }
02198 
02199 LLVM_ATTRIBUTE_ALWAYS_INLINE static bool
02200 CheckChildType(const unsigned char *MatcherTable, unsigned &MatcherIndex,
02201                SDValue N, const TargetLowering *TLI, unsigned ChildNo) {
02202   if (ChildNo >= N.getNumOperands())
02203     return false;  // Match fails if out of range child #.
02204   return ::CheckType(MatcherTable, MatcherIndex, N.getOperand(ChildNo), TLI);
02205 }
02206 
02207 LLVM_ATTRIBUTE_ALWAYS_INLINE static bool
02208 CheckCondCode(const unsigned char *MatcherTable, unsigned &MatcherIndex,
02209               SDValue N) {
02210   return cast<CondCodeSDNode>(N)->get() ==
02211       (ISD::CondCode)MatcherTable[MatcherIndex++];
02212 }
02213 
02214 LLVM_ATTRIBUTE_ALWAYS_INLINE static bool
02215 CheckValueType(const unsigned char *MatcherTable, unsigned &MatcherIndex,
02216                SDValue N, const TargetLowering *TLI) {
02217   MVT::SimpleValueType VT = (MVT::SimpleValueType)MatcherTable[MatcherIndex++];
02218   if (cast<VTSDNode>(N)->getVT() == VT)
02219     return true;
02220 
02221   // Handle the case when VT is iPTR.
02222   return VT == MVT::iPTR && cast<VTSDNode>(N)->getVT() == TLI->getPointerTy();
02223 }
02224 
02225 LLVM_ATTRIBUTE_ALWAYS_INLINE static bool
02226 CheckInteger(const unsigned char *MatcherTable, unsigned &MatcherIndex,
02227              SDValue N) {
02228   int64_t Val = MatcherTable[MatcherIndex++];
02229   if (Val & 128)
02230     Val = GetVBR(Val, MatcherTable, MatcherIndex);
02231 
02232   ConstantSDNode *C = dyn_cast<ConstantSDNode>(N);
02233   return C && C->getSExtValue() == Val;
02234 }
02235 
02236 LLVM_ATTRIBUTE_ALWAYS_INLINE static bool
02237 CheckChildInteger(const unsigned char *MatcherTable, unsigned &MatcherIndex,
02238                   SDValue N, unsigned ChildNo) {
02239   if (ChildNo >= N.getNumOperands())
02240     return false;  // Match fails if out of range child #.
02241   return ::CheckInteger(MatcherTable, MatcherIndex, N.getOperand(ChildNo));
02242 }
02243 
02244 LLVM_ATTRIBUTE_ALWAYS_INLINE static bool
02245 CheckAndImm(const unsigned char *MatcherTable, unsigned &MatcherIndex,
02246             SDValue N, const SelectionDAGISel &SDISel) {
02247   int64_t Val = MatcherTable[MatcherIndex++];
02248   if (Val & 128)
02249     Val = GetVBR(Val, MatcherTable, MatcherIndex);
02250 
02251   if (N->getOpcode() != ISD::AND) return false;
02252 
02253   ConstantSDNode *C = dyn_cast<ConstantSDNode>(N->getOperand(1));
02254   return C && SDISel.CheckAndMask(N.getOperand(0), C, Val);
02255 }
02256 
02257 LLVM_ATTRIBUTE_ALWAYS_INLINE static bool
02258 CheckOrImm(const unsigned char *MatcherTable, unsigned &MatcherIndex,
02259            SDValue N, const SelectionDAGISel &SDISel) {
02260   int64_t Val = MatcherTable[MatcherIndex++];
02261   if (Val & 128)
02262     Val = GetVBR(Val, MatcherTable, MatcherIndex);
02263 
02264   if (N->getOpcode() != ISD::OR) return false;
02265 
02266   ConstantSDNode *C = dyn_cast<ConstantSDNode>(N->getOperand(1));
02267   return C && SDISel.CheckOrMask(N.getOperand(0), C, Val);
02268 }
02269 
02270 /// IsPredicateKnownToFail - If we know how and can do so without pushing a
02271 /// scope, evaluate the current node.  If the current predicate is known to
02272 /// fail, set Result=true and return anything.  If the current predicate is
02273 /// known to pass, set Result=false and return the MatcherIndex to continue
02274 /// with.  If the current predicate is unknown, set Result=false and return the
02275 /// MatcherIndex to continue with.
02276 static unsigned IsPredicateKnownToFail(const unsigned char *Table,
02277                                        unsigned Index, SDValue N,
02278                                        bool &Result,
02279                                        const SelectionDAGISel &SDISel,
02280                  SmallVectorImpl<std::pair<SDValue, SDNode*> > &RecordedNodes) {
02281   switch (Table[Index++]) {
02282   default:
02283     Result = false;
02284     return Index-1;  // Could not evaluate this predicate.
02285   case SelectionDAGISel::OPC_CheckSame:
02286     Result = !::CheckSame(Table, Index, N, RecordedNodes);
02287     return Index;
02288   case SelectionDAGISel::OPC_CheckChild0Same:
02289   case SelectionDAGISel::OPC_CheckChild1Same:
02290   case SelectionDAGISel::OPC_CheckChild2Same:
02291   case SelectionDAGISel::OPC_CheckChild3Same:
02292     Result = !::CheckChildSame(Table, Index, N, RecordedNodes,
02293                         Table[Index-1] - SelectionDAGISel::OPC_CheckChild0Same);
02294     return Index;
02295   case SelectionDAGISel::OPC_CheckPatternPredicate:
02296     Result = !::CheckPatternPredicate(Table, Index, SDISel);
02297     return Index;
02298   case SelectionDAGISel::OPC_CheckPredicate:
02299     Result = !::CheckNodePredicate(Table, Index, SDISel, N.getNode());
02300     return Index;
02301   case SelectionDAGISel::OPC_CheckOpcode:
02302     Result = !::CheckOpcode(Table, Index, N.getNode());
02303     return Index;
02304   case SelectionDAGISel::OPC_CheckType:
02305     Result = !::CheckType(Table, Index, N, SDISel.getTargetLowering());
02306     return Index;
02307   case SelectionDAGISel::OPC_CheckChild0Type:
02308   case SelectionDAGISel::OPC_CheckChild1Type:
02309   case SelectionDAGISel::OPC_CheckChild2Type:
02310   case SelectionDAGISel::OPC_CheckChild3Type:
02311   case SelectionDAGISel::OPC_CheckChild4Type:
02312   case SelectionDAGISel::OPC_CheckChild5Type:
02313   case SelectionDAGISel::OPC_CheckChild6Type:
02314   case SelectionDAGISel::OPC_CheckChild7Type:
02315     Result = !::CheckChildType(Table, Index, N, SDISel.getTargetLowering(),
02316                         Table[Index-1] - SelectionDAGISel::OPC_CheckChild0Type);
02317     return Index;
02318   case SelectionDAGISel::OPC_CheckCondCode:
02319     Result = !::CheckCondCode(Table, Index, N);
02320     return Index;
02321   case SelectionDAGISel::OPC_CheckValueType:
02322     Result = !::CheckValueType(Table, Index, N, SDISel.getTargetLowering());
02323     return Index;
02324   case SelectionDAGISel::OPC_CheckInteger:
02325     Result = !::CheckInteger(Table, Index, N);
02326     return Index;
02327   case SelectionDAGISel::OPC_CheckChild0Integer:
02328   case SelectionDAGISel::OPC_CheckChild1Integer:
02329   case SelectionDAGISel::OPC_CheckChild2Integer:
02330   case SelectionDAGISel::OPC_CheckChild3Integer:
02331   case SelectionDAGISel::OPC_CheckChild4Integer:
02332     Result = !::CheckChildInteger(Table, Index, N,
02333                      Table[Index-1] - SelectionDAGISel::OPC_CheckChild0Integer);
02334     return Index;
02335   case SelectionDAGISel::OPC_CheckAndImm:
02336     Result = !::CheckAndImm(Table, Index, N, SDISel);
02337     return Index;
02338   case SelectionDAGISel::OPC_CheckOrImm:
02339     Result = !::CheckOrImm(Table, Index, N, SDISel);
02340     return Index;
02341   }
02342 }
02343 
02344 namespace {
02345 
02346 struct MatchScope {
02347   /// FailIndex - If this match fails, this is the index to continue with.
02348   unsigned FailIndex;
02349 
02350   /// NodeStack - The node stack when the scope was formed.
02351   SmallVector<SDValue, 4> NodeStack;
02352 
02353   /// NumRecordedNodes - The number of recorded nodes when the scope was formed.
02354   unsigned NumRecordedNodes;
02355 
02356   /// NumMatchedMemRefs - The number of matched memref entries.
02357   unsigned NumMatchedMemRefs;
02358 
02359   /// InputChain/InputGlue - The current chain/glue
02360   SDValue InputChain, InputGlue;
02361 
02362   /// HasChainNodesMatched - True if the ChainNodesMatched list is non-empty.
02363   bool HasChainNodesMatched, HasGlueResultNodesMatched;
02364 };
02365 
02366 }
02367 
02368 SDNode *SelectionDAGISel::
02369 SelectCodeCommon(SDNode *NodeToMatch, const unsigned char *MatcherTable,
02370                  unsigned TableSize) {
02371   // FIXME: Should these even be selected?  Handle these cases in the caller?
02372   switch (NodeToMatch->getOpcode()) {
02373   default:
02374     break;
02375   case ISD::EntryToken:       // These nodes remain the same.
02376   case ISD::BasicBlock:
02377   case ISD::Register:
02378   case ISD::RegisterMask:
02379   //case ISD::VALUETYPE:
02380   //case ISD::CONDCODE:
02381   case ISD::HANDLENODE:
02382   case ISD::MDNODE_SDNODE:
02383   case ISD::TargetConstant:
02384   case ISD::TargetConstantFP:
02385   case ISD::TargetConstantPool:
02386   case ISD::TargetFrameIndex:
02387   case ISD::TargetExternalSymbol:
02388   case ISD::TargetBlockAddress:
02389   case ISD::TargetJumpTable:
02390   case ISD::TargetGlobalTLSAddress:
02391   case ISD::TargetGlobalAddress:
02392   case ISD::TokenFactor:
02393   case ISD::CopyFromReg:
02394   case ISD::CopyToReg:
02395   case ISD::EH_LABEL:
02396   case ISD::LIFETIME_START:
02397   case ISD::LIFETIME_END:
02398     NodeToMatch->setNodeId(-1); // Mark selected.
02399     return nullptr;
02400   case ISD::AssertSext:
02401   case ISD::AssertZext:
02402     CurDAG->ReplaceAllUsesOfValueWith(SDValue(NodeToMatch, 0),
02403                                       NodeToMatch->getOperand(0));
02404     return nullptr;
02405   case ISD::INLINEASM: return Select_INLINEASM(NodeToMatch);
02406   case ISD::UNDEF:     return Select_UNDEF(NodeToMatch);
02407   }
02408 
02409   assert(!NodeToMatch->isMachineOpcode() && "Node already selected!");
02410 
02411   // Set up the node stack with NodeToMatch as the only node on the stack.
02412   SmallVector<SDValue, 8> NodeStack;
02413   SDValue N = SDValue(NodeToMatch, 0);
02414   NodeStack.push_back(N);
02415 
02416   // MatchScopes - Scopes used when matching, if a match failure happens, this
02417   // indicates where to continue checking.
02418   SmallVector<MatchScope, 8> MatchScopes;
02419 
02420   // RecordedNodes - This is the set of nodes that have been recorded by the
02421   // state machine.  The second value is the parent of the node, or null if the
02422   // root is recorded.
02423   SmallVector<std::pair<SDValue, SDNode*>, 8> RecordedNodes;
02424 
02425   // MatchedMemRefs - This is the set of MemRef's we've seen in the input
02426   // pattern.
02427   SmallVector<MachineMemOperand*, 2> MatchedMemRefs;
02428 
02429   // These are the current input chain and glue for use when generating nodes.
02430   // Various Emit operations change these.  For example, emitting a copytoreg
02431   // uses and updates these.
02432   SDValue InputChain, InputGlue;
02433 
02434   // ChainNodesMatched - If a pattern matches nodes that have input/output
02435   // chains, the OPC_EmitMergeInputChains operation is emitted which indicates
02436   // which ones they are.  The result is captured into this list so that we can
02437   // update the chain results when the pattern is complete.
02438   SmallVector<SDNode*, 3> ChainNodesMatched;
02439   SmallVector<SDNode*, 3> GlueResultNodesMatched;
02440 
02441   DEBUG(dbgs() << "ISEL: Starting pattern match on root node: ";
02442         NodeToMatch->dump(CurDAG);
02443         dbgs() << '\n');
02444 
02445   // Determine where to start the interpreter.  Normally we start at opcode #0,
02446   // but if the state machine starts with an OPC_SwitchOpcode, then we
02447   // accelerate the first lookup (which is guaranteed to be hot) with the
02448   // OpcodeOffset table.
02449   unsigned MatcherIndex = 0;
02450 
02451   if (!OpcodeOffset.empty()) {
02452     // Already computed the OpcodeOffset table, just index into it.
02453     if (N.getOpcode() < OpcodeOffset.size())
02454       MatcherIndex = OpcodeOffset[N.getOpcode()];
02455     DEBUG(dbgs() << "  Initial Opcode index to " << MatcherIndex << "\n");
02456 
02457   } else if (MatcherTable[0] == OPC_SwitchOpcode) {
02458     // Otherwise, the table isn't computed, but the state machine does start
02459     // with an OPC_SwitchOpcode instruction.  Populate the table now, since this
02460     // is the first time we're selecting an instruction.
02461     unsigned Idx = 1;
02462     while (1) {
02463       // Get the size of this case.
02464       unsigned CaseSize = MatcherTable[Idx++];
02465       if (CaseSize & 128)
02466         CaseSize = GetVBR(CaseSize, MatcherTable, Idx);
02467       if (CaseSize == 0) break;
02468 
02469       // Get the opcode, add the index to the table.
02470       uint16_t Opc = MatcherTable[Idx++];
02471       Opc |= (unsigned short)MatcherTable[Idx++] << 8;
02472       if (Opc >= OpcodeOffset.size())
02473         OpcodeOffset.resize((Opc+1)*2);
02474       OpcodeOffset[Opc] = Idx;
02475       Idx += CaseSize;
02476     }
02477 
02478     // Okay, do the lookup for the first opcode.
02479     if (N.getOpcode() < OpcodeOffset.size())
02480       MatcherIndex = OpcodeOffset[N.getOpcode()];
02481   }
02482 
02483   while (1) {
02484     assert(MatcherIndex < TableSize && "Invalid index");
02485 #ifndef NDEBUG
02486     unsigned CurrentOpcodeIndex = MatcherIndex;
02487 #endif
02488     BuiltinOpcodes Opcode = (BuiltinOpcodes)MatcherTable[MatcherIndex++];
02489     switch (Opcode) {
02490     case OPC_Scope: {
02491       // Okay, the semantics of this operation are that we should push a scope
02492       // then evaluate the first child.  However, pushing a scope only to have
02493       // the first check fail (which then pops it) is inefficient.  If we can
02494       // determine immediately that the first check (or first several) will
02495       // immediately fail, don't even bother pushing a scope for them.
02496       unsigned FailIndex;
02497 
02498       while (1) {
02499         unsigned NumToSkip = MatcherTable[MatcherIndex++];
02500         if (NumToSkip & 128)
02501           NumToSkip = GetVBR(NumToSkip, MatcherTable, MatcherIndex);
02502         // Found the end of the scope with no match.
02503         if (NumToSkip == 0) {
02504           FailIndex = 0;
02505           break;
02506         }
02507 
02508         FailIndex = MatcherIndex+NumToSkip;
02509 
02510         unsigned MatcherIndexOfPredicate = MatcherIndex;
02511         (void)MatcherIndexOfPredicate; // silence warning.
02512 
02513         // If we can't evaluate this predicate without pushing a scope (e.g. if
02514         // it is a 'MoveParent') or if the predicate succeeds on this node, we
02515         // push the scope and evaluate the full predicate chain.
02516         bool Result;
02517         MatcherIndex = IsPredicateKnownToFail(MatcherTable, MatcherIndex, N,
02518                                               Result, *this, RecordedNodes);
02519         if (!Result)
02520           break;
02521 
02522         DEBUG(dbgs() << "  Skipped scope entry (due to false predicate) at "
02523                      << "index " << MatcherIndexOfPredicate
02524                      << ", continuing at " << FailIndex << "\n");
02525         ++NumDAGIselRetries;
02526 
02527         // Otherwise, we know that this case of the Scope is guaranteed to fail,
02528         // move to the next case.
02529         MatcherIndex = FailIndex;
02530       }
02531 
02532       // If the whole scope failed to match, bail.
02533       if (FailIndex == 0) break;
02534 
02535       // Push a MatchScope which indicates where to go if the first child fails
02536       // to match.
02537       MatchScope NewEntry;
02538       NewEntry.FailIndex = FailIndex;
02539       NewEntry.NodeStack.append(NodeStack.begin(), NodeStack.end());
02540       NewEntry.NumRecordedNodes = RecordedNodes.size();
02541       NewEntry.NumMatchedMemRefs = MatchedMemRefs.size();
02542       NewEntry.InputChain = InputChain;
02543       NewEntry.InputGlue = InputGlue;
02544       NewEntry.HasChainNodesMatched = !ChainNodesMatched.empty();
02545       NewEntry.HasGlueResultNodesMatched = !GlueResultNodesMatched.empty();
02546       MatchScopes.push_back(NewEntry);
02547       continue;
02548     }
02549     case OPC_RecordNode: {
02550       // Remember this node, it may end up being an operand in the pattern.
02551       SDNode *Parent = nullptr;
02552       if (NodeStack.size() > 1)
02553         Parent = NodeStack[NodeStack.size()-2].getNode();
02554       RecordedNodes.push_back(std::make_pair(N, Parent));
02555       continue;
02556     }
02557 
02558     case OPC_RecordChild0: case OPC_RecordChild1:
02559     case OPC_RecordChild2: case OPC_RecordChild3:
02560     case OPC_RecordChild4: case OPC_RecordChild5:
02561     case OPC_RecordChild6: case OPC_RecordChild7: {
02562       unsigned ChildNo = Opcode-OPC_RecordChild0;
02563       if (ChildNo >= N.getNumOperands())
02564         break;  // Match fails if out of range child #.
02565 
02566       RecordedNodes.push_back(std::make_pair(N->getOperand(ChildNo),
02567                                              N.getNode()));
02568       continue;
02569     }
02570     case OPC_RecordMemRef:
02571       MatchedMemRefs.push_back(cast<MemSDNode>(N)->getMemOperand());
02572       continue;
02573 
02574     case OPC_CaptureGlueInput:
02575       // If the current node has an input glue, capture it in InputGlue.
02576       if (N->getNumOperands() != 0 &&
02577           N->getOperand(N->getNumOperands()-1).getValueType() == MVT::Glue)
02578         InputGlue = N->getOperand(N->getNumOperands()-1);
02579       continue;
02580 
02581     case OPC_MoveChild: {
02582       unsigned ChildNo = MatcherTable[MatcherIndex++];
02583       if (ChildNo >= N.getNumOperands())
02584         break;  // Match fails if out of range child #.
02585       N = N.getOperand(ChildNo);
02586       NodeStack.push_back(N);
02587       continue;
02588     }
02589 
02590     case OPC_MoveParent:
02591       // Pop the current node off the NodeStack.
02592       NodeStack.pop_back();
02593       assert(!NodeStack.empty() && "Node stack imbalance!");
02594       N = NodeStack.back();
02595       continue;
02596 
02597     case OPC_CheckSame:
02598       if (!::CheckSame(MatcherTable, MatcherIndex, N, RecordedNodes)) break;
02599       continue;
02600 
02601     case OPC_CheckChild0Same: case OPC_CheckChild1Same:
02602     case OPC_CheckChild2Same: case OPC_CheckChild3Same:
02603       if (!::CheckChildSame(MatcherTable, MatcherIndex, N, RecordedNodes,
02604                             Opcode-OPC_CheckChild0Same))
02605         break;
02606       continue;
02607 
02608     case OPC_CheckPatternPredicate:
02609       if (!::CheckPatternPredicate(MatcherTable, MatcherIndex, *this)) break;
02610       continue;
02611     case OPC_CheckPredicate:
02612       if (!::CheckNodePredicate(MatcherTable, MatcherIndex, *this,
02613                                 N.getNode()))
02614         break;
02615       continue;
02616     case OPC_CheckComplexPat: {
02617       unsigned CPNum = MatcherTable[MatcherIndex++];
02618       unsigned RecNo = MatcherTable[MatcherIndex++];
02619       assert(RecNo < RecordedNodes.size() && "Invalid CheckComplexPat");
02620       if (!CheckComplexPattern(NodeToMatch, RecordedNodes[RecNo].second,
02621                                RecordedNodes[RecNo].first, CPNum,
02622                                RecordedNodes))
02623         break;
02624       continue;
02625     }
02626     case OPC_CheckOpcode:
02627       if (!::CheckOpcode(MatcherTable, MatcherIndex, N.getNode())) break;
02628       continue;
02629 
02630     case OPC_CheckType:
02631       if (!::CheckType(MatcherTable, MatcherIndex, N, getTargetLowering()))
02632         break;
02633       continue;
02634 
02635     case OPC_SwitchOpcode: {
02636       unsigned CurNodeOpcode = N.getOpcode();
02637       unsigned SwitchStart = MatcherIndex-1; (void)SwitchStart;
02638       unsigned CaseSize;
02639       while (1) {
02640         // Get the size of this case.
02641         CaseSize = MatcherTable[MatcherIndex++];
02642         if (CaseSize & 128)
02643           CaseSize = GetVBR(CaseSize, MatcherTable, MatcherIndex);
02644         if (CaseSize == 0) break;
02645 
02646         uint16_t Opc = MatcherTable[MatcherIndex++];
02647         Opc |= (unsigned short)MatcherTable[MatcherIndex++] << 8;
02648 
02649         // If the opcode matches, then we will execute this case.
02650         if (CurNodeOpcode == Opc)
02651           break;
02652 
02653         // Otherwise, skip over this case.
02654         MatcherIndex += CaseSize;
02655       }
02656 
02657       // If no cases matched, bail out.
02658       if (CaseSize == 0) break;
02659 
02660       // Otherwise, execute the case we found.
02661       DEBUG(dbgs() << "  OpcodeSwitch from " << SwitchStart
02662                    << " to " << MatcherIndex << "\n");
02663       continue;
02664     }
02665 
02666     case OPC_SwitchType: {
02667       MVT CurNodeVT = N.getSimpleValueType();
02668       unsigned SwitchStart = MatcherIndex-1; (void)SwitchStart;
02669       unsigned CaseSize;
02670       while (1) {
02671         // Get the size of this case.
02672         CaseSize = MatcherTable[MatcherIndex++];
02673         if (CaseSize & 128)
02674           CaseSize = GetVBR(CaseSize, MatcherTable, MatcherIndex);
02675         if (CaseSize == 0) break;
02676 
02677         MVT CaseVT = (MVT::SimpleValueType)MatcherTable[MatcherIndex++];
02678         if (CaseVT == MVT::iPTR)
02679           CaseVT = getTargetLowering()->getPointerTy();
02680 
02681         // If the VT matches, then we will execute this case.
02682         if (CurNodeVT == CaseVT)
02683           break;
02684 
02685         // Otherwise, skip over this case.
02686         MatcherIndex += CaseSize;
02687       }
02688 
02689       // If no cases matched, bail out.
02690       if (CaseSize == 0) break;
02691 
02692       // Otherwise, execute the case we found.
02693       DEBUG(dbgs() << "  TypeSwitch[" << EVT(CurNodeVT).getEVTString()
02694                    << "] from " << SwitchStart << " to " << MatcherIndex<<'\n');
02695       continue;
02696     }
02697     case OPC_CheckChild0Type: case OPC_CheckChild1Type:
02698     case OPC_CheckChild2Type: case OPC_CheckChild3Type:
02699     case OPC_CheckChild4Type: case OPC_CheckChild5Type:
02700     case OPC_CheckChild6Type: case OPC_CheckChild7Type:
02701       if (!::CheckChildType(MatcherTable, MatcherIndex, N, getTargetLowering(),
02702                             Opcode-OPC_CheckChild0Type))
02703         break;
02704       continue;
02705     case OPC_CheckCondCode:
02706       if (!::CheckCondCode(MatcherTable, MatcherIndex, N)) break;
02707       continue;
02708     case OPC_CheckValueType:
02709       if (!::CheckValueType(MatcherTable, MatcherIndex, N, getTargetLowering()))
02710         break;
02711       continue;
02712     case OPC_CheckInteger:
02713       if (!::CheckInteger(MatcherTable, MatcherIndex, N)) break;
02714       continue;
02715     case OPC_CheckChild0Integer: case OPC_CheckChild1Integer:
02716     case OPC_CheckChild2Integer: case OPC_CheckChild3Integer:
02717     case OPC_CheckChild4Integer:
02718       if (!::CheckChildInteger(MatcherTable, MatcherIndex, N,
02719                                Opcode-OPC_CheckChild0Integer)) break;
02720       continue;
02721     case OPC_CheckAndImm:
02722       if (!::CheckAndImm(MatcherTable, MatcherIndex, N, *this)) break;
02723       continue;
02724     case OPC_CheckOrImm:
02725       if (!::CheckOrImm(MatcherTable, MatcherIndex, N, *this)) break;
02726       continue;
02727 
02728     case OPC_CheckFoldableChainNode: {
02729       assert(NodeStack.size() != 1 && "No parent node");
02730       // Verify that all intermediate nodes between the root and this one have
02731       // a single use.
02732       bool HasMultipleUses = false;
02733       for (unsigned i = 1, e = NodeStack.size()-1; i != e; ++i)
02734         if (!NodeStack[i].hasOneUse()) {
02735           HasMultipleUses = true;
02736           break;
02737         }
02738       if (HasMultipleUses) break;
02739 
02740       // Check to see that the target thinks this is profitable to fold and that
02741       // we can fold it without inducing cycles in the graph.
02742       if (!IsProfitableToFold(N, NodeStack[NodeStack.size()-2].getNode(),
02743                               NodeToMatch) ||
02744           !IsLegalToFold(N, NodeStack[NodeStack.size()-2].getNode(),
02745                          NodeToMatch, OptLevel,
02746                          true/*We validate our own chains*/))
02747         break;
02748 
02749       continue;
02750     }
02751     case OPC_EmitInteger: {
02752       MVT::SimpleValueType VT =
02753         (MVT::SimpleValueType)MatcherTable[MatcherIndex++];
02754       int64_t Val = MatcherTable[MatcherIndex++];
02755       if (Val & 128)
02756         Val = GetVBR(Val, MatcherTable, MatcherIndex);
02757       RecordedNodes.push_back(std::pair<SDValue, SDNode*>(
02758                               CurDAG->getTargetConstant(Val, VT), nullptr));
02759       continue;
02760     }
02761     case OPC_EmitRegister: {
02762       MVT::SimpleValueType VT =
02763         (MVT::SimpleValueType)MatcherTable[MatcherIndex++];
02764       unsigned RegNo = MatcherTable[MatcherIndex++];
02765       RecordedNodes.push_back(std::pair<SDValue, SDNode*>(
02766                               CurDAG->getRegister(RegNo, VT), nullptr));
02767       continue;
02768     }
02769     case OPC_EmitRegister2: {
02770       // For targets w/ more than 256 register names, the register enum
02771       // values are stored in two bytes in the matcher table (just like
02772       // opcodes).
02773       MVT::SimpleValueType VT =
02774         (MVT::SimpleValueType)MatcherTable[MatcherIndex++];
02775       unsigned RegNo = MatcherTable[MatcherIndex++];
02776       RegNo |= MatcherTable[MatcherIndex++] << 8;
02777       RecordedNodes.push_back(std::pair<SDValue, SDNode*>(
02778                               CurDAG->getRegister(RegNo, VT), nullptr));
02779       continue;
02780     }
02781 
02782     case OPC_EmitConvertToTarget:  {
02783       // Convert from IMM/FPIMM to target version.
02784       unsigned RecNo = MatcherTable[MatcherIndex++];
02785       assert(RecNo < RecordedNodes.size() && "Invalid EmitConvertToTarget");
02786       SDValue Imm = RecordedNodes[RecNo].first;
02787 
02788       if (Imm->getOpcode() == ISD::Constant) {
02789         const ConstantInt *Val=cast<ConstantSDNode>(Imm)->getConstantIntValue();
02790         Imm = CurDAG->getConstant(*Val, Imm.getValueType(), true);
02791       } else if (Imm->getOpcode() == ISD::ConstantFP) {
02792         const ConstantFP *Val=cast<ConstantFPSDNode>(Imm)->getConstantFPValue();
02793         Imm = CurDAG->getConstantFP(*Val, Imm.getValueType(), true);
02794       }
02795 
02796       RecordedNodes.push_back(std::make_pair(Imm, RecordedNodes[RecNo].second));
02797       continue;
02798     }
02799 
02800     case OPC_EmitMergeInputChains1_0:    // OPC_EmitMergeInputChains, 1, 0
02801     case OPC_EmitMergeInputChains1_1: {  // OPC_EmitMergeInputChains, 1, 1
02802       // These are space-optimized forms of OPC_EmitMergeInputChains.
02803       assert(!InputChain.getNode() &&
02804              "EmitMergeInputChains should be the first chain producing node");
02805       assert(ChainNodesMatched.empty() &&
02806              "Should only have one EmitMergeInputChains per match");
02807 
02808       // Read all of the chained nodes.
02809       unsigned RecNo = Opcode == OPC_EmitMergeInputChains1_1;
02810       assert(RecNo < RecordedNodes.size() && "Invalid EmitMergeInputChains");
02811       ChainNodesMatched.push_back(RecordedNodes[RecNo].first.getNode());
02812 
02813       // FIXME: What if other value results of the node have uses not matched
02814       // by this pattern?
02815       if (ChainNodesMatched.back() != NodeToMatch &&
02816           !RecordedNodes[RecNo].first.hasOneUse()) {
02817         ChainNodesMatched.clear();
02818         break;
02819       }
02820 
02821       // Merge the input chains if they are not intra-pattern references.
02822       InputChain = HandleMergeInputChains(ChainNodesMatched, CurDAG);
02823 
02824       if (!InputChain.getNode())
02825         break;  // Failed to merge.
02826       continue;
02827     }
02828 
02829     case OPC_EmitMergeInputChains: {
02830       assert(!InputChain.getNode() &&
02831              "EmitMergeInputChains should be the first chain producing node");
02832       // This node gets a list of nodes we matched in the input that have
02833       // chains.  We want to token factor all of the input chains to these nodes
02834       // together.  However, if any of the input chains is actually one of the
02835       // nodes matched in this pattern, then we have an intra-match reference.
02836       // Ignore these because the newly token factored chain should not refer to
02837       // the old nodes.
02838       unsigned NumChains = MatcherTable[MatcherIndex++];
02839       assert(NumChains != 0 && "Can't TF zero chains");
02840 
02841       assert(ChainNodesMatched.empty() &&
02842              "Should only have one EmitMergeInputChains per match");
02843 
02844       // Read all of the chained nodes.
02845       for (unsigned i = 0; i != NumChains; ++i) {
02846         unsigned RecNo = MatcherTable[MatcherIndex++];
02847         assert(RecNo < RecordedNodes.size() && "Invalid EmitMergeInputChains");
02848         ChainNodesMatched.push_back(RecordedNodes[RecNo].first.getNode());
02849 
02850         // FIXME: What if other value results of the node have uses not matched
02851         // by this pattern?
02852         if (ChainNodesMatched.back() != NodeToMatch &&
02853             !RecordedNodes[RecNo].first.hasOneUse()) {
02854           ChainNodesMatched.clear();
02855           break;
02856         }
02857       }
02858 
02859       // If the inner loop broke out, the match fails.
02860       if (ChainNodesMatched.empty())
02861         break;
02862 
02863       // Merge the input chains if they are not intra-pattern references.
02864       InputChain = HandleMergeInputChains(ChainNodesMatched, CurDAG);
02865 
02866       if (!InputChain.getNode())
02867         break;  // Failed to merge.
02868 
02869       continue;
02870     }
02871 
02872     case OPC_EmitCopyToReg: {
02873       unsigned RecNo = MatcherTable[MatcherIndex++];
02874       assert(RecNo < RecordedNodes.size() && "Invalid EmitCopyToReg");
02875       unsigned DestPhysReg = MatcherTable[MatcherIndex++];
02876 
02877       if (!InputChain.getNode())
02878         InputChain = CurDAG->getEntryNode();
02879 
02880       InputChain = CurDAG->getCopyToReg(InputChain, SDLoc(NodeToMatch),
02881                                         DestPhysReg, RecordedNodes[RecNo].first,
02882                                         InputGlue);
02883 
02884       InputGlue = InputChain.getValue(1);
02885       continue;
02886     }
02887 
02888     case OPC_EmitNodeXForm: {
02889       unsigned XFormNo = MatcherTable[MatcherIndex++];
02890       unsigned RecNo = MatcherTable[MatcherIndex++];
02891       assert(RecNo < RecordedNodes.size() && "Invalid EmitNodeXForm");
02892       SDValue Res = RunSDNodeXForm(RecordedNodes[RecNo].first, XFormNo);
02893       RecordedNodes.push_back(std::pair<SDValue,SDNode*>(Res, nullptr));
02894       continue;
02895     }
02896 
02897     case OPC_EmitNode:
02898     case OPC_MorphNodeTo: {
02899       uint16_t TargetOpc = MatcherTable[MatcherIndex++];
02900       TargetOpc |= (unsigned short)MatcherTable[MatcherIndex++] << 8;
02901       unsigned EmitNodeInfo = MatcherTable[MatcherIndex++];
02902       // Get the result VT list.
02903       unsigned NumVTs = MatcherTable[MatcherIndex++];
02904       SmallVector<EVT, 4> VTs;
02905       for (unsigned i = 0; i != NumVTs; ++i) {
02906         MVT::SimpleValueType VT =
02907           (MVT::SimpleValueType)MatcherTable[MatcherIndex++];
02908         if (VT == MVT::iPTR) VT = getTargetLowering()->getPointerTy().SimpleTy;
02909         VTs.push_back(VT);
02910       }
02911 
02912       if (EmitNodeInfo & OPFL_Chain)
02913         VTs.push_back(MVT::Other);
02914       if (EmitNodeInfo & OPFL_GlueOutput)
02915         VTs.push_back(MVT::Glue);
02916 
02917       // This is hot code, so optimize the two most common cases of 1 and 2
02918       // results.
02919       SDVTList VTList;
02920       if (VTs.size() == 1)
02921         VTList = CurDAG->getVTList(VTs[0]);
02922       else if (VTs.size() == 2)
02923         VTList = CurDAG->getVTList(VTs[0], VTs[1]);
02924       else
02925         VTList = CurDAG->getVTList(VTs);
02926 
02927       // Get the operand list.
02928       unsigned NumOps = MatcherTable[MatcherIndex++];
02929       SmallVector<SDValue, 8> Ops;
02930       for (unsigned i = 0; i != NumOps; ++i) {
02931         unsigned RecNo = MatcherTable[MatcherIndex++];
02932         if (RecNo & 128)
02933           RecNo = GetVBR(RecNo, MatcherTable, MatcherIndex);
02934 
02935         assert(RecNo < RecordedNodes.size() && "Invalid EmitNode");
02936         Ops.push_back(RecordedNodes[RecNo].first);
02937       }
02938 
02939       // If there are variadic operands to add, handle them now.
02940       if (EmitNodeInfo & OPFL_VariadicInfo) {
02941         // Determine the start index to copy from.
02942         unsigned FirstOpToCopy = getNumFixedFromVariadicInfo(EmitNodeInfo);
02943         FirstOpToCopy += (EmitNodeInfo & OPFL_Chain) ? 1 : 0;
02944         assert(NodeToMatch->getNumOperands() >= FirstOpToCopy &&
02945                "Invalid variadic node");
02946         // Copy all of the variadic operands, not including a potential glue
02947         // input.
02948         for (unsigned i = FirstOpToCopy, e = NodeToMatch->getNumOperands();
02949              i != e; ++i) {
02950           SDValue V = NodeToMatch->getOperand(i);
02951           if (V.getValueType() == MVT::Glue) break;
02952           Ops.push_back(V);
02953         }
02954       }
02955 
02956       // If this has chain/glue inputs, add them.
02957       if (EmitNodeInfo & OPFL_Chain)
02958         Ops.push_back(InputChain);
02959       if ((EmitNodeInfo & OPFL_GlueInput) && InputGlue.getNode() != nullptr)
02960         Ops.push_back(InputGlue);
02961 
02962       // Create the node.
02963       SDNode *Res = nullptr;
02964       if (Opcode != OPC_MorphNodeTo) {
02965         // If this is a normal EmitNode command, just create the new node and
02966         // add the results to the RecordedNodes list.
02967         Res = CurDAG->getMachineNode(TargetOpc, SDLoc(NodeToMatch),
02968                                      VTList, Ops);
02969 
02970         // Add all the non-glue/non-chain results to the RecordedNodes list.
02971         for (unsigned i = 0, e = VTs.size(); i != e; ++i) {
02972           if (VTs[i] == MVT::Other || VTs[i] == MVT::Glue) break;
02973           RecordedNodes.push_back(std::pair<SDValue,SDNode*>(SDValue(Res, i),
02974                                                              nullptr));
02975         }
02976 
02977       } else if (NodeToMatch->getOpcode() != ISD::DELETED_NODE) {
02978         Res = MorphNode(NodeToMatch, TargetOpc, VTList, Ops.data(), Ops.size(),
02979                         EmitNodeInfo);
02980       } else {
02981         // NodeToMatch was eliminated by CSE when the target changed the DAG.
02982         // We will visit the equivalent node later.
02983         DEBUG(dbgs() << "Node was eliminated by CSE\n");
02984         return nullptr;
02985       }
02986 
02987       // If the node had chain/glue results, update our notion of the current
02988       // chain and glue.
02989       if (EmitNodeInfo & OPFL_GlueOutput) {
02990         InputGlue = SDValue(Res, VTs.size()-1);
02991         if (EmitNodeInfo & OPFL_Chain)
02992           InputChain = SDValue(Res, VTs.size()-2);
02993       } else if (EmitNodeInfo & OPFL_Chain)
02994         InputChain = SDValue(Res, VTs.size()-1);
02995 
02996       // If the OPFL_MemRefs glue is set on this node, slap all of the
02997       // accumulated memrefs onto it.
02998       //
02999       // FIXME: This is vastly incorrect for patterns with multiple outputs
03000       // instructions that access memory and for ComplexPatterns that match
03001       // loads.
03002       if (EmitNodeInfo & OPFL_MemRefs) {
03003         // Only attach load or store memory operands if the generated
03004         // instruction may load or store.
03005         const MCInstrDesc &MCID = TM.getInstrInfo()->get(TargetOpc);
03006         bool mayLoad = MCID.mayLoad();
03007         bool mayStore = MCID.mayStore();
03008 
03009         unsigned NumMemRefs = 0;
03010         for (SmallVectorImpl<MachineMemOperand *>::const_iterator I =
03011                MatchedMemRefs.begin(), E = MatchedMemRefs.end(); I != E; ++I) {
03012           if ((*I)->isLoad()) {
03013             if (mayLoad)
03014               ++NumMemRefs;
03015           } else if ((*I)->isStore()) {
03016             if (mayStore)
03017               ++NumMemRefs;
03018           } else {
03019             ++NumMemRefs;
03020           }
03021         }
03022 
03023         MachineSDNode::mmo_iterator MemRefs =
03024           MF->allocateMemRefsArray(NumMemRefs);
03025 
03026         MachineSDNode::mmo_iterator MemRefsPos = MemRefs;
03027         for (SmallVectorImpl<MachineMemOperand *>::const_iterator I =
03028                MatchedMemRefs.begin(), E = MatchedMemRefs.end(); I != E; ++I) {
03029           if ((*I)->isLoad()) {
03030             if (mayLoad)
03031               *MemRefsPos++ = *I;
03032           } else if ((*I)->isStore()) {
03033             if (mayStore)
03034               *MemRefsPos++ = *I;
03035           } else {
03036             *MemRefsPos++ = *I;
03037           }
03038         }
03039 
03040         cast<MachineSDNode>(Res)
03041           ->setMemRefs(MemRefs, MemRefs + NumMemRefs);
03042       }
03043 
03044       DEBUG(dbgs() << "  "
03045                    << (Opcode == OPC_MorphNodeTo ? "Morphed" : "Created")
03046                    << " node: "; Res->dump(CurDAG); dbgs() << "\n");
03047 
03048       // If this was a MorphNodeTo then we're completely done!
03049       if (Opcode == OPC_MorphNodeTo) {
03050         // Update chain and glue uses.
03051         UpdateChainsAndGlue(NodeToMatch, InputChain, ChainNodesMatched,
03052                             InputGlue, GlueResultNodesMatched, true);
03053         return Res;
03054       }
03055 
03056       continue;
03057     }
03058 
03059     case OPC_MarkGlueResults: {
03060       unsigned NumNodes = MatcherTable[MatcherIndex++];
03061 
03062       // Read and remember all the glue-result nodes.
03063       for (unsigned i = 0; i != NumNodes; ++i) {
03064         unsigned RecNo = MatcherTable[MatcherIndex++];
03065         if (RecNo & 128)
03066           RecNo = GetVBR(RecNo, MatcherTable, MatcherIndex);
03067 
03068         assert(RecNo < RecordedNodes.size() && "Invalid MarkGlueResults");
03069         GlueResultNodesMatched.push_back(RecordedNodes[RecNo].first.getNode());
03070       }
03071       continue;
03072     }
03073 
03074     case OPC_CompleteMatch: {
03075       // The match has been completed, and any new nodes (if any) have been
03076       // created.  Patch up references to the matched dag to use the newly
03077       // created nodes.
03078       unsigned NumResults = MatcherTable[MatcherIndex++];
03079 
03080       for (unsigned i = 0; i != NumResults; ++i) {
03081         unsigned ResSlot = MatcherTable[MatcherIndex++];
03082         if (ResSlot & 128)
03083           ResSlot = GetVBR(ResSlot, MatcherTable, MatcherIndex);
03084 
03085         assert(ResSlot < RecordedNodes.size() && "Invalid CompleteMatch");
03086         SDValue Res = RecordedNodes[ResSlot].first;
03087 
03088         assert(i < NodeToMatch->getNumValues() &&
03089                NodeToMatch->getValueType(i) != MVT::Other &&
03090                NodeToMatch->getValueType(i) != MVT::Glue &&
03091                "Invalid number of results to complete!");
03092         assert((NodeToMatch->getValueType(i) == Res.getValueType() ||
03093                 NodeToMatch->getValueType(i) == MVT::iPTR ||
03094                 Res.getValueType() == MVT::iPTR ||
03095                 NodeToMatch->getValueType(i).getSizeInBits() ==
03096                     Res.getValueType().getSizeInBits()) &&
03097                "invalid replacement");
03098         CurDAG->ReplaceAllUsesOfValueWith(SDValue(NodeToMatch, i), Res);
03099       }
03100 
03101       // If the root node defines glue, add it to the glue nodes to update list.
03102       if (NodeToMatch->getValueType(NodeToMatch->getNumValues()-1) == MVT::Glue)
03103         GlueResultNodesMatched.push_back(NodeToMatch);
03104 
03105       // Update chain and glue uses.
03106       UpdateChainsAndGlue(NodeToMatch, InputChain, ChainNodesMatched,
03107                           InputGlue, GlueResultNodesMatched, false);
03108 
03109       assert(NodeToMatch->use_empty() &&
03110              "Didn't replace all uses of the node?");
03111 
03112       // FIXME: We just return here, which interacts correctly with SelectRoot
03113       // above.  We should fix this to not return an SDNode* anymore.
03114       return nullptr;
03115     }
03116     }
03117 
03118     // If the code reached this point, then the match failed.  See if there is
03119     // another child to try in the current 'Scope', otherwise pop it until we
03120     // find a case to check.
03121     DEBUG(dbgs() << "  Match failed at index " << CurrentOpcodeIndex << "\n");
03122     ++NumDAGIselRetries;
03123     while (1) {
03124       if (MatchScopes.empty()) {
03125         CannotYetSelect(NodeToMatch);
03126         return nullptr;
03127       }
03128 
03129       // Restore the interpreter state back to the point where the scope was
03130       // formed.
03131       MatchScope &LastScope = MatchScopes.back();
03132       RecordedNodes.resize(LastScope.NumRecordedNodes);
03133       NodeStack.clear();
03134       NodeStack.append(LastScope.NodeStack.begin(), LastScope.NodeStack.end());
03135       N = NodeStack.back();
03136 
03137       if (LastScope.NumMatchedMemRefs != MatchedMemRefs.size())
03138         MatchedMemRefs.resize(LastScope.NumMatchedMemRefs);
03139       MatcherIndex = LastScope.FailIndex;
03140 
03141       DEBUG(dbgs() << "  Continuing at " << MatcherIndex << "\n");
03142 
03143       InputChain = LastScope.InputChain;
03144       InputGlue = LastScope.InputGlue;
03145       if (!LastScope.HasChainNodesMatched)
03146         ChainNodesMatched.clear();
03147       if (!LastScope.HasGlueResultNodesMatched)
03148         GlueResultNodesMatched.clear();
03149 
03150       // Check to see what the offset is at the new MatcherIndex.  If it is zero
03151       // we have reached the end of this scope, otherwise we have another child
03152       // in the current scope to try.
03153       unsigned NumToSkip = MatcherTable[MatcherIndex++];
03154       if (NumToSkip & 128)
03155         NumToSkip = GetVBR(NumToSkip, MatcherTable, MatcherIndex);
03156 
03157       // If we have another child in this scope to match, update FailIndex and
03158       // try it.
03159       if (NumToSkip != 0) {
03160         LastScope.FailIndex = MatcherIndex+NumToSkip;
03161         break;
03162       }
03163 
03164       // End of this scope, pop it and try the next child in the containing
03165       // scope.
03166       MatchScopes.pop_back();
03167     }
03168   }
03169 }
03170 
03171 
03172 
03173 void SelectionDAGISel::CannotYetSelect(SDNode *N) {
03174   std::string msg;
03175   raw_string_ostream Msg(msg);
03176   Msg << "Cannot select: ";
03177 
03178   if (N->getOpcode() != ISD::INTRINSIC_W_CHAIN &&
03179       N->getOpcode() != ISD::INTRINSIC_WO_CHAIN &&
03180       N->getOpcode() != ISD::INTRINSIC_VOID) {
03181     N->printrFull(Msg, CurDAG);
03182     Msg << "\nIn function: " << MF->getName();
03183   } else {
03184     bool HasInputChain = N->getOperand(0).getValueType() == MVT::Other;
03185     unsigned iid =
03186       cast<ConstantSDNode>(N->getOperand(HasInputChain))->getZExtValue();
03187     if (iid < Intrinsic::num_intrinsics)
03188       Msg << "intrinsic %" << Intrinsic::getName((Intrinsic::ID)iid);
03189     else if (const TargetIntrinsicInfo *TII = TM.getIntrinsicInfo())
03190       Msg << "target intrinsic %" << TII->getName(iid);
03191     else
03192       Msg << "unknown intrinsic #" << iid;
03193   }
03194   report_fatal_error(Msg.str());
03195 }
03196 
03197 char SelectionDAGISel::ID = 0;