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