lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp

   1 //===-- SelectionDAGISel.cpp - Implement the SelectionDAGISel class -------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This implements the SelectionDAGISel class.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "ScheduleDAGSDNodes.h"
  15 #include "SelectionDAGBuilder.h"
  16 #include "llvm/ADT/APInt.h"
  17 #include "llvm/ADT/DenseMap.h"
  18 #include "llvm/ADT/None.h"
  19 #include "llvm/ADT/PostOrderIterator.h"
  20 #include "llvm/ADT/SmallPtrSet.h"
  21 #include "llvm/ADT/SmallSet.h"
  22 #include "llvm/ADT/SmallVector.h"
  23 #include "llvm/ADT/Statistic.h"
  24 #include "llvm/ADT/STLExtras.h"
  25 #include "llvm/ADT/StringRef.h"
  26 #include "llvm/Analysis/AliasAnalysis.h"
  27 #include "llvm/Analysis/BranchProbabilityInfo.h"
  28 #include "llvm/Analysis/CFG.h"
  29 #include "llvm/Analysis/OptimizationDiagnosticInfo.h"
  30 #include "llvm/Analysis/TargetLibraryInfo.h"
  31 #include "llvm/CodeGen/FastISel.h"
  32 #include "llvm/CodeGen/FunctionLoweringInfo.h"
  33 #include "llvm/CodeGen/GCMetadata.h"
  34 #include "llvm/CodeGen/MachineBasicBlock.h"
  35 #include "llvm/CodeGen/MachineFrameInfo.h"
  36 #include "llvm/CodeGen/MachineFunction.h"
  37 #include "llvm/CodeGen/MachineFunctionPass.h"
  38 #include "llvm/CodeGen/MachineInstr.h"
  39 #include "llvm/CodeGen/MachineInstrBuilder.h"
  40 #include "llvm/CodeGen/MachineMemOperand.h"
  41 #include "llvm/CodeGen/MachineModuleInfo.h"
  42 #include "llvm/CodeGen/MachineOperand.h"
  43 #include "llvm/CodeGen/MachinePassRegistry.h"
  44 #include "llvm/CodeGen/MachineRegisterInfo.h"
  45 #include "llvm/CodeGen/MachineValueType.h"
  46 #include "llvm/CodeGen/SchedulerRegistry.h"
  47 #include "llvm/CodeGen/SelectionDAG.h"
  48 #include "llvm/CodeGen/SelectionDAGISel.h"
  49 #include "llvm/CodeGen/SelectionDAGNodes.h"
  50 #include "llvm/CodeGen/StackProtector.h"
  51 #include "llvm/CodeGen/ValueTypes.h"
  52 #include "llvm/IR/BasicBlock.h"
  53 #include "llvm/IR/Constants.h"
  54 #include "llvm/IR/DebugInfoMetadata.h"
  55 #include "llvm/IR/DebugLoc.h"
  56 #include "llvm/IR/DiagnosticInfo.h"
  57 #include "llvm/IR/Function.h"
  58 #include "llvm/IR/InlineAsm.h"
  59 #include "llvm/IR/InstrTypes.h"
  60 #include "llvm/IR/Instruction.h"
  61 #include "llvm/IR/Instructions.h"
  62 #include "llvm/IR/IntrinsicInst.h"
  63 #include "llvm/IR/Intrinsics.h"
  64 #include "llvm/IR/Metadata.h"
  65 #include "llvm/IR/Type.h"
  66 #include "llvm/IR/User.h"
  67 #include "llvm/MC/MCInstrDesc.h"
  68 #include "llvm/MC/MCRegisterInfo.h"
  69 #include "llvm/Pass.h"
  70 #include "llvm/Support/BranchProbability.h"
  71 #include "llvm/Support/Casting.h"
  72 #include "llvm/Support/CodeGen.h"
  73 #include "llvm/Support/CommandLine.h"
  74 #include "llvm/Support/Compiler.h"
  75 #include "llvm/Support/Debug.h"
  76 #include "llvm/Support/ErrorHandling.h"
  77 #include "llvm/Support/KnownBits.h"
  78 #include "llvm/Support/Timer.h"
  79 #include "llvm/Support/raw_ostream.h"
  80 #include "llvm/Target/TargetInstrInfo.h"
  81 #include "llvm/Target/TargetIntrinsicInfo.h"
  82 #include "llvm/Target/TargetLowering.h"
  83 #include "llvm/Target/TargetMachine.h"
  84 #include "llvm/Target/TargetOptions.h"
  85 #include "llvm/Target/TargetRegisterInfo.h"
  86 #include "llvm/Target/TargetSubtargetInfo.h"
  87 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
  88 #include <algorithm>
  89 #include <cassert>
  90 #include <cstdint>
  91 #include <iterator>
  92 #include <memory>
  93 #include <string>
  94 #include <utility>
  95 #include <vector>
  96
  97 using namespace llvm;
  98
  99 #define DEBUG_TYPE "isel"
 100
 101 STATISTIC(NumFastIselFailures, "Number of instructions fast isel failed on");
 102 STATISTIC(NumFastIselSuccess, "Number of instructions fast isel selected");
 103 STATISTIC(NumFastIselBlocks, "Number of blocks selected entirely by fast isel");
 104 STATISTIC(NumDAGBlocks, "Number of blocks selected using DAG");
 105 STATISTIC(NumDAGIselRetries,"Number of times dag isel has to try another path");
 106 STATISTIC(NumEntryBlocks, "Number of entry blocks encountered");
 107 STATISTIC(NumFastIselFailLowerArguments,
 108           "Number of entry blocks where fast isel failed to lower arguments");
 109
 110 static cl::opt<int> EnableFastISelAbort(
 111     "fast-isel-abort", cl::Hidden,
 112     cl::desc("Enable abort calls when \"fast\" instruction selection "
 113              "fails to lower an instruction: 0 disable the abort, 1 will "
 114              "abort but for args, calls and terminators, 2 will also "
 115              "abort for argument lowering, and 3 will never fallback "
 116              "to SelectionDAG."));
 117
 118 static cl::opt<bool> EnableFastISelFallbackReport(
 119     "fast-isel-report-on-fallback", cl::Hidden,
 120     cl::desc("Emit a diagnostic when \"fast\" instruction selection "
 121              "falls back to SelectionDAG."));
 122
 123 static cl::opt<bool>
 124 UseMBPI("use-mbpi",
 125         cl::desc("use Machine Branch Probability Info"),
 126         cl::init(true), cl::Hidden);
 127
 128 #ifndef NDEBUG
 129 static cl::opt<std::string>
 130 FilterDAGBasicBlockName("filter-view-dags", cl::Hidden,
 131                         cl::desc("Only display the basic block whose name "
 132                                  "matches this for all view-*-dags options"));
 133 static cl::opt<bool>
 134 ViewDAGCombine1("view-dag-combine1-dags", cl::Hidden,
 135           cl::desc("Pop up a window to show dags before the first "
 136                    "dag combine pass"));
 137 static cl::opt<bool>
 138 ViewLegalizeTypesDAGs("view-legalize-types-dags", cl::Hidden,
 139           cl::desc("Pop up a window to show dags before legalize types"));
 140 static cl::opt<bool>
 141 ViewLegalizeDAGs("view-legalize-dags", cl::Hidden,
 142           cl::desc("Pop up a window to show dags before legalize"));
 143 static cl::opt<bool>
 144 ViewDAGCombine2("view-dag-combine2-dags", cl::Hidden,
 145           cl::desc("Pop up a window to show dags before the second "
 146                    "dag combine pass"));
 147 static cl::opt<bool>
 148 ViewDAGCombineLT("view-dag-combine-lt-dags", cl::Hidden,
 149           cl::desc("Pop up a window to show dags before the post legalize types"
 150                    " dag combine pass"));
 151 static cl::opt<bool>
 152 ViewISelDAGs("view-isel-dags", cl::Hidden,
 153           cl::desc("Pop up a window to show isel dags as they are selected"));
 154 static cl::opt<bool>
 155 ViewSchedDAGs("view-sched-dags", cl::Hidden,
 156           cl::desc("Pop up a window to show sched dags as they are processed"));
 157 static cl::opt<bool>
 158 ViewSUnitDAGs("view-sunit-dags", cl::Hidden,
 159       cl::desc("Pop up a window to show SUnit dags after they are processed"));
 160 #else
 161 static const bool ViewDAGCombine1 = false,
 162                   ViewLegalizeTypesDAGs = false, ViewLegalizeDAGs = false,
 163                   ViewDAGCombine2 = false,
 164                   ViewDAGCombineLT = false,
 165                   ViewISelDAGs = false, ViewSchedDAGs = false,
 166                   ViewSUnitDAGs = false;
 167 #endif
 168
 169 //===---------------------------------------------------------------------===//
 170 ///
 171 /// RegisterScheduler class - Track the registration of instruction schedulers.
 172 ///
 173 //===---------------------------------------------------------------------===//
 174 MachinePassRegistry RegisterScheduler::Registry;
 175
 176 //===---------------------------------------------------------------------===//
 177 ///
 178 /// ISHeuristic command line option for instruction schedulers.
 179 ///
 180 //===---------------------------------------------------------------------===//
 181 static cl::opt<RegisterScheduler::FunctionPassCtor, false,
 182                RegisterPassParser<RegisterScheduler>>
 183 ISHeuristic("pre-RA-sched",
 184             cl::init(&createDefaultScheduler), cl::Hidden,
 185             cl::desc("Instruction schedulers available (before register"
 186                      " allocation):"));
 187
 188 static RegisterScheduler
 189 defaultListDAGScheduler("default", "Best scheduler for the target",
 190                         createDefaultScheduler);
 191
 192 namespace llvm {
 193
 194   //===--------------------------------------------------------------------===//
 195   /// \brief This class is used by SelectionDAGISel to temporarily override
 196   /// the optimization level on a per-function basis.
 197   class OptLevelChanger {
 198     SelectionDAGISel &IS;
 199     CodeGenOpt::Level SavedOptLevel;
 200     bool SavedFastISel;
 201
 202   public:
 203     OptLevelChanger(SelectionDAGISel &ISel,
 204                     CodeGenOpt::Level NewOptLevel) : IS(ISel) {
 205       SavedOptLevel = IS.OptLevel;
 206       if (NewOptLevel == SavedOptLevel)
 207         return;
 208       IS.OptLevel = NewOptLevel;
 209       IS.TM.setOptLevel(NewOptLevel);
 210       DEBUG(dbgs() << "\nChanging optimization level for Function "
 211             << IS.MF->getFunction()->getName() << "\n");
 212       DEBUG(dbgs() << "\tBefore: -O" << SavedOptLevel
 213             << " ; After: -O" << NewOptLevel << "\n");
 214       SavedFastISel = IS.TM.Options.EnableFastISel;
 215       if (NewOptLevel == CodeGenOpt::None) {
 216         IS.TM.setFastISel(IS.TM.getO0WantsFastISel());
 217         DEBUG(dbgs() << "\tFastISel is "
 218               << (IS.TM.Options.EnableFastISel ? "enabled" : "disabled")
 219               << "\n");
 220       }
 221     }
 222
 223     ~OptLevelChanger() {
 224       if (IS.OptLevel == SavedOptLevel)
 225         return;
 226       DEBUG(dbgs() << "\nRestoring optimization level for Function "
 227             << IS.MF->getFunction()->getName() << "\n");
 228       DEBUG(dbgs() << "\tBefore: -O" << IS.OptLevel
 229             << " ; After: -O" << SavedOptLevel << "\n");
 230       IS.OptLevel = SavedOptLevel;
 231       IS.TM.setOptLevel(SavedOptLevel);
 232       IS.TM.setFastISel(SavedFastISel);
 233     }
 234   };
 235
 236   //===--------------------------------------------------------------------===//
 237   /// createDefaultScheduler - This creates an instruction scheduler appropriate
 238   /// for the target.
 239   ScheduleDAGSDNodes* createDefaultScheduler(SelectionDAGISel *IS,
 240                                              CodeGenOpt::Level OptLevel) {
 241     const TargetLowering *TLI = IS->TLI;
 242     const TargetSubtargetInfo &ST = IS->MF->getSubtarget();
 243
 244     // Try first to see if the Target has its own way of selecting a scheduler
 245     if (auto *SchedulerCtor = ST.getDAGScheduler(OptLevel)) {
 246       return SchedulerCtor(IS, OptLevel);
 247     }
 248
 249     if (OptLevel == CodeGenOpt::None ||
 250         (ST.enableMachineScheduler() && ST.enableMachineSchedDefaultSched()) ||
 251         TLI->getSchedulingPreference() == Sched::Source)
 252       return createSourceListDAGScheduler(IS, OptLevel);
 253     if (TLI->getSchedulingPreference() == Sched::RegPressure)
 254       return createBURRListDAGScheduler(IS, OptLevel);
 255     if (TLI->getSchedulingPreference() == Sched::Hybrid)
 256       return createHybridListDAGScheduler(IS, OptLevel);
 257     if (TLI->getSchedulingPreference() == Sched::VLIW)
 258       return createVLIWDAGScheduler(IS, OptLevel);
 259     assert(TLI->getSchedulingPreference() == Sched::ILP &&
 260            "Unknown sched type!");
 261     return createILPListDAGScheduler(IS, OptLevel);
 262   }
 263
 264 } // end namespace llvm
 265
 266 // EmitInstrWithCustomInserter - This method should be implemented by targets
 267 // that mark instructions with the 'usesCustomInserter' flag.  These
 268 // instructions are special in various ways, which require special support to
 269 // insert.  The specified MachineInstr is created but not inserted into any
 270 // basic blocks, and this method is called to expand it into a sequence of
 271 // instructions, potentially also creating new basic blocks and control flow.
 272 // When new basic blocks are inserted and the edges from MBB to its successors
 273 // are modified, the method should insert pairs of <OldSucc, NewSucc> into the
 274 // DenseMap.
 275 MachineBasicBlock *
 276 TargetLowering::EmitInstrWithCustomInserter(MachineInstr &MI,
 277                                             MachineBasicBlock *MBB) const {
 278 #ifndef NDEBUG
 279   dbgs() << "If a target marks an instruction with "
 280           "'usesCustomInserter', it must implement "
 281           "TargetLowering::EmitInstrWithCustomInserter!";
 282 #endif
 283   llvm_unreachable(nullptr);
 284 }
 285
 286 void TargetLowering::AdjustInstrPostInstrSelection(MachineInstr &MI,
 287                                                    SDNode *Node) const {
 288   assert(!MI.hasPostISelHook() &&
 289          "If a target marks an instruction with 'hasPostISelHook', "
 290          "it must implement TargetLowering::AdjustInstrPostInstrSelection!");
 291 }
 292
 293 //===----------------------------------------------------------------------===//
 294 // SelectionDAGISel code
 295 //===----------------------------------------------------------------------===//
 296
 297 SelectionDAGISel::SelectionDAGISel(TargetMachine &tm,
 298                                    CodeGenOpt::Level OL) :
 299   MachineFunctionPass(ID), TM(tm),
 300   FuncInfo(new FunctionLoweringInfo()),
 301   CurDAG(new SelectionDAG(tm, OL)),
 302   SDB(new SelectionDAGBuilder(*CurDAG, *FuncInfo, OL)),
 303   AA(), GFI(),
 304   OptLevel(OL),
 305   DAGSize(0) {
 306     initializeGCModuleInfoPass(*PassRegistry::getPassRegistry());
 307     initializeBranchProbabilityInfoWrapperPassPass(
 308         *PassRegistry::getPassRegistry());
 309     initializeAAResultsWrapperPassPass(*PassRegistry::getPassRegistry());
 310     initializeTargetLibraryInfoWrapperPassPass(
 311         *PassRegistry::getPassRegistry());
 312   }
 313
 314 SelectionDAGISel::~SelectionDAGISel() {
 315   delete SDB;
 316   delete CurDAG;
 317   delete FuncInfo;
 318 }
 319
 320 void SelectionDAGISel::getAnalysisUsage(AnalysisUsage &AU) const {
 321   if (OptLevel != CodeGenOpt::None)
 322     AU.addRequired<AAResultsWrapperPass>();
 323   AU.addRequired<GCModuleInfo>();
 324   AU.addRequired<StackProtector>();
 325   AU.addPreserved<StackProtector>();
 326   AU.addPreserved<GCModuleInfo>();
 327   AU.addRequired<TargetLibraryInfoWrapperPass>();
 328   if (UseMBPI && OptLevel != CodeGenOpt::None)
 329     AU.addRequired<BranchProbabilityInfoWrapperPass>();
 330   MachineFunctionPass::getAnalysisUsage(AU);
 331 }
 332
 333 /// SplitCriticalSideEffectEdges - Look for critical edges with a PHI value that
 334 /// may trap on it.  In this case we have to split the edge so that the path
 335 /// through the predecessor block that doesn't go to the phi block doesn't
 336 /// execute the possibly trapping instruction.
 337 ///
 338 /// This is required for correctness, so it must be done at -O0.
 339 ///
 340 static void SplitCriticalSideEffectEdges(Function &Fn) {
 341   // Loop for blocks with phi nodes.
 342   for (BasicBlock &BB : Fn) {
 343     PHINode *PN = dyn_cast<PHINode>(BB.begin());
 344     if (!PN) continue;
 345
 346   ReprocessBlock:
 347     // For each block with a PHI node, check to see if any of the input values
 348     // are potentially trapping constant expressions.  Constant expressions are
 349     // the only potentially trapping value that can occur as the argument to a
 350     // PHI.
 351     for (BasicBlock::iterator I = BB.begin(); (PN = dyn_cast<PHINode>(I)); ++I)
 352       for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
 353         ConstantExpr *CE = dyn_cast<ConstantExpr>(PN->getIncomingValue(i));
 354         if (!CE || !CE->canTrap()) continue;
 355
 356         // The only case we have to worry about is when the edge is critical.
 357         // Since this block has a PHI Node, we assume it has multiple input
 358         // edges: check to see if the pred has multiple successors.
 359         BasicBlock *Pred = PN->getIncomingBlock(i);
 360         if (Pred->getTerminator()->getNumSuccessors() == 1)
 361           continue;
 362
 363         // Okay, we have to split this edge.
 364         SplitCriticalEdge(
 365             Pred->getTerminator(), GetSuccessorNumber(Pred, &BB),
 366             CriticalEdgeSplittingOptions().setMergeIdenticalEdges());
 367         goto ReprocessBlock;
 368       }
 369   }
 370 }
 371
 372 bool SelectionDAGISel::runOnMachineFunction(MachineFunction &mf) {
 373   // If we already selected that function, we do not need to run SDISel.
 374   if (mf.getProperties().hasProperty(
 375           MachineFunctionProperties::Property::Selected))
 376     return false;
 377   // Do some sanity-checking on the command-line options.
 378   assert((!EnableFastISelAbort || TM.Options.EnableFastISel) &&
 379          "-fast-isel-abort > 0 requires -fast-isel");
 380
 381   const Function &Fn = *mf.getFunction();
 382   MF = &mf;
 383
 384   // Reset the target options before resetting the optimization
 385   // level below.
 386   // FIXME: This is a horrible hack and should be processed via
 387   // codegen looking at the optimization level explicitly when
 388   // it wants to look at it.
 389   TM.resetTargetOptions(Fn);
 390   // Reset OptLevel to None for optnone functions.
 391   CodeGenOpt::Level NewOptLevel = OptLevel;
 392   if (OptLevel != CodeGenOpt::None && skipFunction(Fn))
 393     NewOptLevel = CodeGenOpt::None;
 394   OptLevelChanger OLC(*this, NewOptLevel);
 395
 396   TII = MF->getSubtarget().getInstrInfo();
 397   TLI = MF->getSubtarget().getTargetLowering();
 398   RegInfo = &MF->getRegInfo();
 399   LibInfo = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
 400   GFI = Fn.hasGC() ? &getAnalysis<GCModuleInfo>().getFunctionInfo(Fn) : nullptr;
 401   ORE = make_unique<OptimizationRemarkEmitter>(&Fn);
 402
 403   DEBUG(dbgs() << "\n\n\n=== " << Fn.getName() << "\n");
 404
 405   SplitCriticalSideEffectEdges(const_cast<Function &>(Fn));
 406
 407   CurDAG->init(*MF, *ORE);
 408   FuncInfo->set(Fn, *MF, CurDAG);
 409
 410   // Now get the optional analyzes if we want to.
 411   // This is based on the possibly changed OptLevel (after optnone is taken
 412   // into account).  That's unfortunate but OK because it just means we won't
 413   // ask for passes that have been required anyway.
 414
 415   if (UseMBPI && OptLevel != CodeGenOpt::None)
 416     FuncInfo->BPI = &getAnalysis<BranchProbabilityInfoWrapperPass>().getBPI();
 417   else
 418     FuncInfo->BPI = nullptr;
 419
 420   if (OptLevel != CodeGenOpt::None)
 421     AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
 422   else
 423     AA = nullptr;
 424
 425   SDB->init(GFI, AA, LibInfo);
 426
 427   MF->setHasInlineAsm(false);
 428
 429   FuncInfo->SplitCSR = false;
 430
 431   // We split CSR if the target supports it for the given function
 432   // and the function has only return exits.
 433   if (OptLevel != CodeGenOpt::None && TLI->supportSplitCSR(MF)) {
 434     FuncInfo->SplitCSR = true;
 435
 436     // Collect all the return blocks.
 437     for (const BasicBlock &BB : Fn) {
 438       if (!succ_empty(&BB))
 439         continue;
 440
 441       const TerminatorInst *Term = BB.getTerminator();
 442       if (isa<UnreachableInst>(Term) || isa<ReturnInst>(Term))
 443         continue;
 444
 445       // Bail out if the exit block is not Return nor Unreachable.
 446       FuncInfo->SplitCSR = false;
 447       break;
 448     }
 449   }
 450
 451   MachineBasicBlock *EntryMBB = &MF->front();
 452   if (FuncInfo->SplitCSR)
 453     // This performs initialization so lowering for SplitCSR will be correct.
 454     TLI->initializeSplitCSR(EntryMBB);
 455
 456   SelectAllBasicBlocks(Fn);
 457   if (FastISelFailed && EnableFastISelFallbackReport) {
 458     DiagnosticInfoISelFallback DiagFallback(Fn);
 459     Fn.getContext().diagnose(DiagFallback);
 460   }
 461
 462   // If the first basic block in the function has live ins that need to be
 463   // copied into vregs, emit the copies into the top of the block before
 464   // emitting the code for the block.
 465   const TargetRegisterInfo &TRI = *MF->getSubtarget().getRegisterInfo();
 466   RegInfo->EmitLiveInCopies(EntryMBB, TRI, *TII);
 467
 468   // Insert copies in the entry block and the return blocks.
 469   if (FuncInfo->SplitCSR) {
 470     SmallVector<MachineBasicBlock*, 4> Returns;
 471     // Collect all the return blocks.
 472     for (MachineBasicBlock &MBB : mf) {
 473       if (!MBB.succ_empty())
 474         continue;
 475
 476       MachineBasicBlock::iterator Term = MBB.getFirstTerminator();
 477       if (Term != MBB.end() && Term->isReturn()) {
 478         Returns.push_back(&MBB);
 479         continue;
 480       }
 481     }
 482     TLI->insertCopiesSplitCSR(EntryMBB, Returns);
 483   }
 484
 485   DenseMap<unsigned, unsigned> LiveInMap;
 486   if (!FuncInfo->ArgDbgValues.empty())
 487     for (MachineRegisterInfo::livein_iterator LI = RegInfo->livein_begin(),
 488            E = RegInfo->livein_end(); LI != E; ++LI)
 489       if (LI->second)
 490         LiveInMap.insert(std::make_pair(LI->first, LI->second));
 491
 492   // Insert DBG_VALUE instructions for function arguments to the entry block.
 493   for (unsigned i = 0, e = FuncInfo->ArgDbgValues.size(); i != e; ++i) {
 494     MachineInstr *MI = FuncInfo->ArgDbgValues[e-i-1];
 495     bool hasFI = MI->getOperand(0).isFI();
 496     unsigned Reg =
 497         hasFI ? TRI.getFrameRegister(*MF) : MI->getOperand(0).getReg();
 498     if (TargetRegisterInfo::isPhysicalRegister(Reg))
 499       EntryMBB->insert(EntryMBB->begin(), MI);
 500     else {
 501       MachineInstr *Def = RegInfo->getVRegDef(Reg);
 502       if (Def) {
 503         MachineBasicBlock::iterator InsertPos = Def;
 504         // FIXME: VR def may not be in entry block.
 505         Def->getParent()->insert(std::next(InsertPos), MI);
 506       } else
 507         DEBUG(dbgs() << "Dropping debug info for dead vreg"
 508               << TargetRegisterInfo::virtReg2Index(Reg) << "\n");
 509     }
 510
 511     // If Reg is live-in then update debug info to track its copy in a vreg.
 512     DenseMap<unsigned, unsigned>::iterator LDI = LiveInMap.find(Reg);
 513     if (LDI != LiveInMap.end()) {
 514       assert(!hasFI && "There's no handling of frame pointer updating here yet "
 515                        "- add if needed");
 516       MachineInstr *Def = RegInfo->getVRegDef(LDI->second);
 517       MachineBasicBlock::iterator InsertPos = Def;
 518       const MDNode *Variable = MI->getDebugVariable();
 519       const MDNode *Expr = MI->getDebugExpression();
 520       DebugLoc DL = MI->getDebugLoc();
 521       bool IsIndirect = MI->isIndirectDebugValue();
 522       unsigned Offset = IsIndirect ? MI->getOperand(1).getImm() : 0;
 523       assert(cast<DILocalVariable>(Variable)->isValidLocationForIntrinsic(DL) &&
 524              "Expected inlined-at fields to agree");
 525       // Def is never a terminator here, so it is ok to increment InsertPos.
 526       BuildMI(*EntryMBB, ++InsertPos, DL, TII->get(TargetOpcode::DBG_VALUE),
 527               IsIndirect, LDI->second, Offset, Variable, Expr);
 528
 529       // If this vreg is directly copied into an exported register then
 530       // that COPY instructions also need DBG_VALUE, if it is the only
 531       // user of LDI->second.
 532       MachineInstr *CopyUseMI = nullptr;
 533       for (MachineRegisterInfo::use_instr_iterator
 534            UI = RegInfo->use_instr_begin(LDI->second),
 535            E = RegInfo->use_instr_end(); UI != E; ) {
 536         MachineInstr *UseMI = &*(UI++);
 537         if (UseMI->isDebugValue()) continue;
 538         if (UseMI->isCopy() && !CopyUseMI && UseMI->getParent() == EntryMBB) {
 539           CopyUseMI = UseMI; continue;
 540         }
 541         // Otherwise this is another use or second copy use.
 542         CopyUseMI = nullptr; break;
 543       }
 544       if (CopyUseMI) {
 545         // Use MI's debug location, which describes where Variable was
 546         // declared, rather than whatever is attached to CopyUseMI.
 547         MachineInstr *NewMI =
 548             BuildMI(*MF, DL, TII->get(TargetOpcode::DBG_VALUE), IsIndirect,
 549                     CopyUseMI->getOperand(0).getReg(), Offset, Variable, Expr);
 550         MachineBasicBlock::iterator Pos = CopyUseMI;
 551         EntryMBB->insertAfter(Pos, NewMI);
 552       }
 553     }
 554   }
 555
 556   // Determine if there are any calls in this machine function.
 557   MachineFrameInfo &MFI = MF->getFrameInfo();
 558   for (const auto &MBB : *MF) {
 559     if (MFI.hasCalls() && MF->hasInlineAsm())
 560       break;
 561
 562     for (const auto &MI : MBB) {
 563       const MCInstrDesc &MCID = TII->get(MI.getOpcode());
 564       if ((MCID.isCall() && !MCID.isReturn()) ||
 565           MI.isStackAligningInlineAsm()) {
 566         MFI.setHasCalls(true);
 567       }
 568       if (MI.isInlineAsm()) {
 569         MF->setHasInlineAsm(true);
 570       }
 571     }
 572   }
 573
 574   // Determine if there is a call to setjmp in the machine function.
 575   MF->setExposesReturnsTwice(Fn.callsFunctionThatReturnsTwice());
 576
 577   // Replace forward-declared registers with the registers containing
 578   // the desired value.
 579   MachineRegisterInfo &MRI = MF->getRegInfo();
 580   for (DenseMap<unsigned, unsigned>::iterator
 581        I = FuncInfo->RegFixups.begin(), E = FuncInfo->RegFixups.end();
 582        I != E; ++I) {
 583     unsigned From = I->first;
 584     unsigned To = I->second;
 585     // If To is also scheduled to be replaced, find what its ultimate
 586     // replacement is.
 587     while (true) {
 588       DenseMap<unsigned, unsigned>::iterator J = FuncInfo->RegFixups.find(To);
 589       if (J == E) break;
 590       To = J->second;
 591     }
 592     // Make sure the new register has a sufficiently constrained register class.
 593     if (TargetRegisterInfo::isVirtualRegister(From) &&
 594         TargetRegisterInfo::isVirtualRegister(To))
 595       MRI.constrainRegClass(To, MRI.getRegClass(From));
 596     // Replace it.
 597
 598
 599     // Replacing one register with another won't touch the kill flags.
 600     // We need to conservatively clear the kill flags as a kill on the old
 601     // register might dominate existing uses of the new register.
 602     if (!MRI.use_empty(To))
 603       MRI.clearKillFlags(From);
 604     MRI.replaceRegWith(From, To);
 605   }
 606
 607   TLI->finalizeLowering(*MF);
 608
 609   // Release function-specific state. SDB and CurDAG are already cleared
 610   // at this point.
 611   FuncInfo->clear();
 612
 613   DEBUG(dbgs() << "*** MachineFunction at end of ISel ***\n");
 614   DEBUG(MF->print(dbgs()));
 615
 616   return true;
 617 }
 618
 619 static void reportFastISelFailure(MachineFunction &MF,
 620                                   OptimizationRemarkEmitter &ORE,
 621                                   OptimizationRemarkMissed &R,
 622                                   bool ShouldAbort) {
 623   // Print the function name explicitly if we don't have a debug location (which
 624   // makes the diagnostic less useful) or if we're going to emit a raw error.
 625   if (!R.getLocation().isValid() || ShouldAbort)
 626     R << (" (in function: " + MF.getName() + ")").str();
 627
 628   if (ShouldAbort)
 629     report_fatal_error(R.getMsg());
 630
 631   ORE.emit(R);
 632 }
 633
 634 void SelectionDAGISel::SelectBasicBlock(BasicBlock::const_iterator Begin,
 635                                         BasicBlock::const_iterator End,
 636                                         bool &HadTailCall) {
 637   // Lower the instructions. If a call is emitted as a tail call, cease emitting
 638   // nodes for this block.
 639   for (BasicBlock::const_iterator I = Begin; I != End && !SDB->HasTailCall; ++I) {
 640     if (!ElidedArgCopyInstrs.count(&*I))
 641       SDB->visit(*I);
 642   }
 643
 644   // Make sure the root of the DAG is up-to-date.
 645   CurDAG->setRoot(SDB->getControlRoot());
 646   HadTailCall = SDB->HasTailCall;
 647   SDB->clear();
 648
 649   // Final step, emit the lowered DAG as machine code.
 650   CodeGenAndEmitDAG();
 651 }
 652
 653 void SelectionDAGISel::ComputeLiveOutVRegInfo() {
 654   SmallPtrSet<SDNode*, 16> VisitedNodes;
 655   SmallVector<SDNode*, 128> Worklist;
 656
 657   Worklist.push_back(CurDAG->getRoot().getNode());
 658
 659   KnownBits Known;
 660
 661   do {
 662     SDNode *N = Worklist.pop_back_val();
 663
 664     // If we've already seen this node, ignore it.
 665     if (!VisitedNodes.insert(N).second)
 666       continue;
 667
 668     // Otherwise, add all chain operands to the worklist.
 669     for (const SDValue &Op : N->op_values())
 670       if (Op.getValueType() == MVT::Other)
 671         Worklist.push_back(Op.getNode());
 672
 673     // If this is a CopyToReg with a vreg dest, process it.
 674     if (N->getOpcode() != ISD::CopyToReg)
 675       continue;
 676
 677     unsigned DestReg = cast<RegisterSDNode>(N->getOperand(1))->getReg();
 678     if (!TargetRegisterInfo::isVirtualRegister(DestReg))
 679       continue;
 680
 681     // Ignore non-scalar or non-integer values.
 682     SDValue Src = N->getOperand(2);
 683     EVT SrcVT = Src.getValueType();
 684     if (!SrcVT.isInteger() || SrcVT.isVector())
 685       continue;
 686
 687     unsigned NumSignBits = CurDAG->ComputeNumSignBits(Src);
 688     CurDAG->computeKnownBits(Src, Known);
 689     FuncInfo->AddLiveOutRegInfo(DestReg, NumSignBits, Known);
 690   } while (!Worklist.empty());
 691 }
 692
 693 void SelectionDAGISel::CodeGenAndEmitDAG() {
 694   StringRef GroupName = "sdag";
 695   StringRef GroupDescription = "Instruction Selection and Scheduling";
 696   std::string BlockName;
 697   int BlockNumber = -1;
 698   (void)BlockNumber;
 699   bool MatchFilterBB = false; (void)MatchFilterBB;
 700
 701   // Pre-type legalization allow creation of any node types.
 702   CurDAG->NewNodesMustHaveLegalTypes = false;
 703
 704 #ifndef NDEBUG
 705   MatchFilterBB = (FilterDAGBasicBlockName.empty() ||
 706                    FilterDAGBasicBlockName ==
 707                        FuncInfo->MBB->getBasicBlock()->getName().str());
 708 #endif
 709 #ifdef NDEBUG
 710   if (ViewDAGCombine1 || ViewLegalizeTypesDAGs || ViewLegalizeDAGs ||
 711       ViewDAGCombine2 || ViewDAGCombineLT || ViewISelDAGs || ViewSchedDAGs ||
 712       ViewSUnitDAGs)
 713 #endif
 714   {
 715     BlockNumber = FuncInfo->MBB->getNumber();
 716     BlockName =
 717         (MF->getName() + ":" + FuncInfo->MBB->getBasicBlock()->getName()).str();
 718   }
 719   DEBUG(dbgs() << "Initial selection DAG: BB#" << BlockNumber
 720         << " '" << BlockName << "'\n"; CurDAG->dump());
 721
 722   if (ViewDAGCombine1 && MatchFilterBB)
 723     CurDAG->viewGraph("dag-combine1 input for " + BlockName);
 724
 725   // Run the DAG combiner in pre-legalize mode.
 726   {
 727     NamedRegionTimer T("combine1", "DAG Combining 1", GroupName,
 728                        GroupDescription, TimePassesIsEnabled);
 729     CurDAG->Combine(BeforeLegalizeTypes, AA, OptLevel);
 730   }
 731
 732   DEBUG(dbgs() << "Optimized lowered selection DAG: BB#" << BlockNumber
 733         << " '" << BlockName << "'\n"; CurDAG->dump());
 734
 735   // Second step, hack on the DAG until it only uses operations and types that
 736   // the target supports.
 737   if (ViewLegalizeTypesDAGs && MatchFilterBB)
 738     CurDAG->viewGraph("legalize-types input for " + BlockName);
 739
 740   bool Changed;
 741   {
 742     NamedRegionTimer T("legalize_types", "Type Legalization", GroupName,
 743                        GroupDescription, TimePassesIsEnabled);
 744     Changed = CurDAG->LegalizeTypes();
 745   }
 746
 747   DEBUG(dbgs() << "Type-legalized selection DAG: BB#" << BlockNumber
 748         << " '" << BlockName << "'\n"; CurDAG->dump());
 749
 750   // Only allow creation of legal node types.
 751   CurDAG->NewNodesMustHaveLegalTypes = true;
 752
 753   if (Changed) {
 754     if (ViewDAGCombineLT && MatchFilterBB)
 755       CurDAG->viewGraph("dag-combine-lt input for " + BlockName);
 756
 757     // Run the DAG combiner in post-type-legalize mode.
 758     {
 759       NamedRegionTimer T("combine_lt", "DAG Combining after legalize types",
 760                          GroupName, GroupDescription, TimePassesIsEnabled);
 761       CurDAG->Combine(AfterLegalizeTypes, AA, OptLevel);
 762     }
 763
 764     DEBUG(dbgs() << "Optimized type-legalized selection DAG: BB#" << BlockNumber
 765           << " '" << BlockName << "'\n"; CurDAG->dump());
 766
 767   }
 768
 769   {
 770     NamedRegionTimer T("legalize_vec", "Vector Legalization", GroupName,
 771                        GroupDescription, TimePassesIsEnabled);
 772     Changed = CurDAG->LegalizeVectors();
 773   }
 774
 775   if (Changed) {
 776     DEBUG(dbgs() << "Vector-legalized selection DAG: BB#" << BlockNumber
 777           << " '" << BlockName << "'\n"; CurDAG->dump());
 778
 779     {
 780       NamedRegionTimer T("legalize_types2", "Type Legalization 2", GroupName,
 781                          GroupDescription, TimePassesIsEnabled);
 782       CurDAG->LegalizeTypes();
 783     }
 784
 785     DEBUG(dbgs() << "Vector/type-legalized selection DAG: BB#" << BlockNumber
 786           << " '" << BlockName << "'\n"; CurDAG->dump());
 787
 788     if (ViewDAGCombineLT && MatchFilterBB)
 789       CurDAG->viewGraph("dag-combine-lv input for " + BlockName);
 790
 791     // Run the DAG combiner in post-type-legalize mode.
 792     {
 793       NamedRegionTimer T("combine_lv", "DAG Combining after legalize vectors",
 794                          GroupName, GroupDescription, TimePassesIsEnabled);
 795       CurDAG->Combine(AfterLegalizeVectorOps, AA, OptLevel);
 796     }
 797
 798     DEBUG(dbgs() << "Optimized vector-legalized selection DAG: BB#"
 799           << BlockNumber << " '" << BlockName << "'\n"; CurDAG->dump());
 800   }
 801
 802   if (ViewLegalizeDAGs && MatchFilterBB)
 803     CurDAG->viewGraph("legalize input for " + BlockName);
 804
 805   {
 806     NamedRegionTimer T("legalize", "DAG Legalization", GroupName,
 807                        GroupDescription, TimePassesIsEnabled);
 808     CurDAG->Legalize();
 809   }
 810
 811   DEBUG(dbgs() << "Legalized selection DAG: BB#" << BlockNumber
 812         << " '" << BlockName << "'\n"; CurDAG->dump());
 813
 814   if (ViewDAGCombine2 && MatchFilterBB)
 815     CurDAG->viewGraph("dag-combine2 input for " + BlockName);
 816
 817   // Run the DAG combiner in post-legalize mode.
 818   {
 819     NamedRegionTimer T("combine2", "DAG Combining 2", GroupName,
 820                        GroupDescription, TimePassesIsEnabled);
 821     CurDAG->Combine(AfterLegalizeDAG, AA, OptLevel);
 822   }
 823
 824   DEBUG(dbgs() << "Optimized legalized selection DAG: BB#" << BlockNumber
 825         << " '" << BlockName << "'\n"; CurDAG->dump());
 826
 827   if (OptLevel != CodeGenOpt::None)
 828     ComputeLiveOutVRegInfo();
 829
 830   if (ViewISelDAGs && MatchFilterBB)
 831     CurDAG->viewGraph("isel input for " + BlockName);
 832
 833   // Third, instruction select all of the operations to machine code, adding the
 834   // code to the MachineBasicBlock.
 835   {
 836     NamedRegionTimer T("isel", "Instruction Selection", GroupName,
 837                        GroupDescription, TimePassesIsEnabled);
 838     DoInstructionSelection();
 839   }
 840
 841   DEBUG(dbgs() << "Selected selection DAG: BB#" << BlockNumber
 842         << " '" << BlockName << "'\n"; CurDAG->dump());
 843
 844   if (ViewSchedDAGs && MatchFilterBB)
 845     CurDAG->viewGraph("scheduler input for " + BlockName);
 846
 847   // Schedule machine code.
 848   ScheduleDAGSDNodes *Scheduler = CreateScheduler();
 849   {
 850     NamedRegionTimer T("sched", "Instruction Scheduling", GroupName,
 851                        GroupDescription, TimePassesIsEnabled);
 852     Scheduler->Run(CurDAG, FuncInfo->MBB);
 853   }
 854
 855   if (ViewSUnitDAGs && MatchFilterBB)
 856     Scheduler->viewGraph();
 857
 858   // Emit machine code to BB.  This can change 'BB' to the last block being
 859   // inserted into.
 860   MachineBasicBlock *FirstMBB = FuncInfo->MBB, *LastMBB;
 861   {
 862     NamedRegionTimer T("emit", "Instruction Creation", GroupName,
 863                        GroupDescription, TimePassesIsEnabled);
 864
 865     // FuncInfo->InsertPt is passed by reference and set to the end of the
 866     // scheduled instructions.
 867     LastMBB = FuncInfo->MBB = Scheduler->EmitSchedule(FuncInfo->InsertPt);
 868   }
 869
 870   // If the block was split, make sure we update any references that are used to
 871   // update PHI nodes later on.
 872   if (FirstMBB != LastMBB)
 873     SDB->UpdateSplitBlock(FirstMBB, LastMBB);
 874
 875   // Free the scheduler state.
 876   {
 877     NamedRegionTimer T("cleanup", "Instruction Scheduling Cleanup", GroupName,
 878                        GroupDescription, TimePassesIsEnabled);
 879     delete Scheduler;
 880   }
 881
 882   // Free the SelectionDAG state, now that we're finished with it.
 883   CurDAG->clear();
 884 }
 885
 886 namespace {
 887
 888 /// ISelUpdater - helper class to handle updates of the instruction selection
 889 /// graph.
 890 class ISelUpdater : public SelectionDAG::DAGUpdateListener {
 891   SelectionDAG::allnodes_iterator &ISelPosition;
 892
 893 public:
 894   ISelUpdater(SelectionDAG &DAG, SelectionDAG::allnodes_iterator &isp)
 895     : SelectionDAG::DAGUpdateListener(DAG), ISelPosition(isp) {}
 896
 897   /// NodeDeleted - Handle nodes deleted from the graph. If the node being
 898   /// deleted is the current ISelPosition node, update ISelPosition.
 899   ///
 900   void NodeDeleted(SDNode *N, SDNode *E) override {
 901     if (ISelPosition == SelectionDAG::allnodes_iterator(N))
 902       ++ISelPosition;
 903   }
 904 };
 905
 906 } // end anonymous namespace
 907
 908 static bool isStrictFPOp(SDNode *Node, unsigned &NewOpc) {
 909   unsigned OrigOpc = Node->getOpcode();
 910   switch (OrigOpc) {
 911     case ISD::STRICT_FADD: NewOpc = ISD::FADD; return true;
 912     case ISD::STRICT_FSUB: NewOpc = ISD::FSUB; return true;
 913     case ISD::STRICT_FMUL: NewOpc = ISD::FMUL; return true;
 914     case ISD::STRICT_FDIV: NewOpc = ISD::FDIV; return true;
 915     case ISD::STRICT_FREM: NewOpc = ISD::FREM; return true;
 916     default: return false;
 917   }
 918 }
 919
 920 SDNode* SelectionDAGISel::MutateStrictFPToFP(SDNode *Node, unsigned NewOpc) {
 921   assert(((Node->getOpcode() == ISD::STRICT_FADD && NewOpc == ISD::FADD) ||
 922           (Node->getOpcode() == ISD::STRICT_FSUB && NewOpc == ISD::FSUB) ||
 923           (Node->getOpcode() == ISD::STRICT_FMUL && NewOpc == ISD::FMUL) ||
 924           (Node->getOpcode() == ISD::STRICT_FDIV && NewOpc == ISD::FDIV) ||
 925           (Node->getOpcode() == ISD::STRICT_FREM && NewOpc == ISD::FREM)) &&
 926           "Unexpected StrictFP opcode!");
 927
 928   // We're taking this node out of the chain, so we need to re-link things.
 929   SDValue InputChain = Node->getOperand(0);
 930   SDValue OutputChain = SDValue(Node, 1);
 931   CurDAG->ReplaceAllUsesOfValueWith(OutputChain, InputChain);
 932
 933   SDVTList VTs = CurDAG->getVTList(Node->getOperand(1).getValueType());
 934   SDValue Ops[2] = { Node->getOperand(1), Node->getOperand(2) };
 935   SDNode *Res = CurDAG->MorphNodeTo(Node, NewOpc, VTs, Ops);
 936
 937   // MorphNodeTo can operate in two ways: if an existing node with the
 938   // specified operands exists, it can just return it.  Otherwise, it
 939   // updates the node in place to have the requested operands.
 940   if (Res == Node) {
 941     // If we updated the node in place, reset the node ID.  To the isel,
 942     // this should be just like a newly allocated machine node.
 943     Res->setNodeId(-1);
 944   } else {
 945     CurDAG->ReplaceAllUsesWith(Node, Res);
 946     CurDAG->RemoveDeadNode(Node);
 947   }
 948
 949   return Res;
 950 }
 951
 952 void SelectionDAGISel::DoInstructionSelection() {
 953   DEBUG(dbgs() << "===== Instruction selection begins: BB#"
 954         << FuncInfo->MBB->getNumber()
 955         << " '" << FuncInfo->MBB->getName() << "'\n");
 956
 957   PreprocessISelDAG();
 958
 959   // Select target instructions for the DAG.
 960   {
 961     // Number all nodes with a topological order and set DAGSize.
 962     DAGSize = CurDAG->AssignTopologicalOrder();
 963
 964     // Create a dummy node (which is not added to allnodes), that adds
 965     // a reference to the root node, preventing it from being deleted,
 966     // and tracking any changes of the root.
 967     HandleSDNode Dummy(CurDAG->getRoot());
 968     SelectionDAG::allnodes_iterator ISelPosition (CurDAG->getRoot().getNode());
 969     ++ISelPosition;
 970
 971     // Make sure that ISelPosition gets properly updated when nodes are deleted
 972     // in calls made from this function.
 973     ISelUpdater ISU(*CurDAG, ISelPosition);
 974
 975     // The AllNodes list is now topological-sorted. Visit the
 976     // nodes by starting at the end of the list (the root of the
 977     // graph) and preceding back toward the beginning (the entry
 978     // node).
 979     while (ISelPosition != CurDAG->allnodes_begin()) {
 980       SDNode *Node = &*--ISelPosition;
 981       // Skip dead nodes. DAGCombiner is expected to eliminate all dead nodes,
 982       // but there are currently some corner cases that it misses. Also, this
 983       // makes it theoretically possible to disable the DAGCombiner.
 984       if (Node->use_empty())
 985         continue;
 986
 987       // When we are using non-default rounding modes or FP exception behavior
 988       // FP operations are represented by StrictFP pseudo-operations.  They
 989       // need to be simplified here so that the target-specific instruction
 990       // selectors know how to handle them.
 991       //
 992       // If the current node is a strict FP pseudo-op, the isStrictFPOp()
 993       // function will provide the corresponding normal FP opcode to which the
 994       // node should be mutated.
 995       unsigned NormalFPOpc = ISD::UNDEF;
 996       bool IsStrictFPOp = isStrictFPOp(Node, NormalFPOpc);
 997       if (IsStrictFPOp)
 998         Node = MutateStrictFPToFP(Node, NormalFPOpc);
 999
1000       Select(Node);
1001
1002       // FIXME: Add code here to attach an implicit def and use of
1003       // target-specific FP environment registers.
1004     }
1005
1006     CurDAG->setRoot(Dummy.getValue());
1007   }
1008
1009   DEBUG(dbgs() << "===== Instruction selection ends:\n");
1010
1011   PostprocessISelDAG();
1012 }
1013
1014 static bool hasExceptionPointerOrCodeUser(const CatchPadInst *CPI) {
1015   for (const User *U : CPI->users()) {
1016     if (const IntrinsicInst *EHPtrCall = dyn_cast<IntrinsicInst>(U)) {
1017       Intrinsic::ID IID = EHPtrCall->getIntrinsicID();
1018       if (IID == Intrinsic::eh_exceptionpointer ||
1019           IID == Intrinsic::eh_exceptioncode)
1020         return true;
1021     }
1022   }
1023   return false;
1024 }
1025
1026 /// PrepareEHLandingPad - Emit an EH_LABEL, set up live-in registers, and
1027 /// do other setup for EH landing-pad blocks.
1028 bool SelectionDAGISel::PrepareEHLandingPad() {
1029   MachineBasicBlock *MBB = FuncInfo->MBB;
1030   const Constant *PersonalityFn = FuncInfo->Fn->getPersonalityFn();
1031   const BasicBlock *LLVMBB = MBB->getBasicBlock();
1032   const TargetRegisterClass *PtrRC =
1033       TLI->getRegClassFor(TLI->getPointerTy(CurDAG->getDataLayout()));
1034
1035   // Catchpads have one live-in register, which typically holds the exception
1036   // pointer or code.
1037   if (const auto *CPI = dyn_cast<CatchPadInst>(LLVMBB->getFirstNonPHI())) {
1038     if (hasExceptionPointerOrCodeUser(CPI)) {
1039       // Get or create the virtual register to hold the pointer or code.  Mark
1040       // the live in physreg and copy into the vreg.
1041       MCPhysReg EHPhysReg = TLI->getExceptionPointerRegister(PersonalityFn);
1042       assert(EHPhysReg && "target lacks exception pointer register");
1043       MBB->addLiveIn(EHPhysReg);
1044       unsigned VReg = FuncInfo->getCatchPadExceptionPointerVReg(CPI, PtrRC);
1045       BuildMI(*MBB, FuncInfo->InsertPt, SDB->getCurDebugLoc(),
1046               TII->get(TargetOpcode::COPY), VReg)
1047           .addReg(EHPhysReg, RegState::Kill);
1048     }
1049     return true;
1050   }
1051
1052   if (!LLVMBB->isLandingPad())
1053     return true;
1054
1055   // Add a label to mark the beginning of the landing pad.  Deletion of the
1056   // landing pad can thus be detected via the MachineModuleInfo.
1057   MCSymbol *Label = MF->addLandingPad(MBB);
1058
1059   // Assign the call site to the landing pad's begin label.
1060   MF->setCallSiteLandingPad(Label, SDB->LPadToCallSiteMap[MBB]);
1061
1062   const MCInstrDesc &II = TII->get(TargetOpcode::EH_LABEL);
1063   BuildMI(*MBB, FuncInfo->InsertPt, SDB->getCurDebugLoc(), II)
1064     .addSym(Label);
1065
1066   // Mark exception register as live in.
1067   if (unsigned Reg = TLI->getExceptionPointerRegister(PersonalityFn))
1068     FuncInfo->ExceptionPointerVirtReg = MBB->addLiveIn(Reg, PtrRC);
1069
1070   // Mark exception selector register as live in.
1071   if (unsigned Reg = TLI->getExceptionSelectorRegister(PersonalityFn))
1072     FuncInfo->ExceptionSelectorVirtReg = MBB->addLiveIn(Reg, PtrRC);
1073
1074   return true;
1075 }
1076
1077 /// isFoldedOrDeadInstruction - Return true if the specified instruction is
1078 /// side-effect free and is either dead or folded into a generated instruction.
1079 /// Return false if it needs to be emitted.
1080 static bool isFoldedOrDeadInstruction(const Instruction *I,
1081                                       FunctionLoweringInfo *FuncInfo) {
1082   return !I->mayWriteToMemory() && // Side-effecting instructions aren't folded.
1083          !isa<TerminatorInst>(I) &&    // Terminators aren't folded.
1084          !isa<DbgInfoIntrinsic>(I) &&  // Debug instructions aren't folded.
1085          !I->isEHPad() &&              // EH pad instructions aren't folded.
1086          !FuncInfo->isExportedInst(I); // Exported instrs must be computed.
1087 }
1088
1089 /// Set up SwiftErrorVals by going through the function. If the function has
1090 /// swifterror argument, it will be the first entry.
1091 static void setupSwiftErrorVals(const Function &Fn, const TargetLowering *TLI,
1092                                 FunctionLoweringInfo *FuncInfo) {
1093   if (!TLI->supportSwiftError())
1094     return;
1095
1096   FuncInfo->SwiftErrorVals.clear();
1097   FuncInfo->SwiftErrorVRegDefMap.clear();
1098   FuncInfo->SwiftErrorVRegUpwardsUse.clear();
1099   FuncInfo->SwiftErrorArg = nullptr;
1100
1101   // Check if function has a swifterror argument.
1102   bool HaveSeenSwiftErrorArg = false;
1103   for (Function::const_arg_iterator AI = Fn.arg_begin(), AE = Fn.arg_end();
1104        AI != AE; ++AI)
1105     if (AI->hasSwiftErrorAttr()) {
1106       assert(!HaveSeenSwiftErrorArg &&
1107              "Must have only one swifterror parameter");
1108       (void)HaveSeenSwiftErrorArg; // silence warning.
1109       HaveSeenSwiftErrorArg = true;
1110       FuncInfo->SwiftErrorArg = &*AI;
1111       FuncInfo->SwiftErrorVals.push_back(&*AI);
1112     }
1113
1114   for (const auto &LLVMBB : Fn)
1115     for (const auto &Inst : LLVMBB) {
1116       if (const AllocaInst *Alloca = dyn_cast<AllocaInst>(&Inst))
1117         if (Alloca->isSwiftError())
1118           FuncInfo->SwiftErrorVals.push_back(Alloca);
1119     }
1120 }
1121
1122 static void createSwiftErrorEntriesInEntryBlock(FunctionLoweringInfo *FuncInfo,
1123                                                 FastISel *FastIS,
1124                                                 const TargetLowering *TLI,
1125                                                 const TargetInstrInfo *TII,
1126                                                 SelectionDAGBuilder *SDB) {
1127   if (!TLI->supportSwiftError())
1128     return;
1129
1130   // We only need to do this when we have swifterror parameter or swifterror
1131   // alloc.
1132   if (FuncInfo->SwiftErrorVals.empty())
1133     return;
1134
1135   assert(FuncInfo->MBB == &*FuncInfo->MF->begin() &&
1136          "expected to insert into entry block");
1137   auto &DL = FuncInfo->MF->getDataLayout();
1138   auto const *RC = TLI->getRegClassFor(TLI->getPointerTy(DL));
1139   for (const auto *SwiftErrorVal : FuncInfo->SwiftErrorVals) {
1140     // We will always generate a copy from the argument. It is always used at
1141     // least by the 'return' of the swifterror.
1142     if (FuncInfo->SwiftErrorArg && FuncInfo->SwiftErrorArg == SwiftErrorVal)
1143       continue;
1144     unsigned VReg = FuncInfo->MF->getRegInfo().createVirtualRegister(RC);
1145     // Assign Undef to Vreg. We construct MI directly to make sure it works
1146     // with FastISel.
1147     BuildMI(*FuncInfo->MBB, FuncInfo->MBB->getFirstNonPHI(),
1148             SDB->getCurDebugLoc(), TII->get(TargetOpcode::IMPLICIT_DEF),
1149             VReg);
1150
1151     // Keep FastIS informed about the value we just inserted.
1152     if (FastIS)
1153       FastIS->setLastLocalValue(&*std::prev(FuncInfo->InsertPt));
1154
1155     FuncInfo->setCurrentSwiftErrorVReg(FuncInfo->MBB, SwiftErrorVal, VReg);
1156   }
1157 }
1158
1159 /// Collect llvm.dbg.declare information. This is done after argument lowering
1160 /// in case the declarations refer to arguments.
1161 static void processDbgDeclares(FunctionLoweringInfo *FuncInfo) {
1162   MachineFunction *MF = FuncInfo->MF;
1163   const DataLayout &DL = MF->getDataLayout();
1164   for (const BasicBlock &BB : *FuncInfo->Fn) {
1165     for (const Instruction &I : BB) {
1166       const DbgDeclareInst *DI = dyn_cast<DbgDeclareInst>(&I);
1167       if (!DI)
1168         continue;
1169
1170       assert(DI->getVariable() && "Missing variable");
1171       assert(DI->getDebugLoc() && "Missing location");
1172       const Value *Address = DI->getAddress();
1173       if (!Address)
1174         continue;
1175
1176       // Look through casts and constant offset GEPs. These mostly come from
1177       // inalloca.
1178       APInt Offset(DL.getPointerSizeInBits(0), 0);
1179       Address = Address->stripAndAccumulateInBoundsConstantOffsets(DL, Offset);
1180
1181       // Check if the variable is a static alloca or a byval or inalloca
1182       // argument passed in memory. If it is not, then we will ignore this
1183       // intrinsic and handle this during isel like dbg.value.
1184       int FI = INT_MAX;
1185       if (const auto *AI = dyn_cast<AllocaInst>(Address)) {
1186         auto SI = FuncInfo->StaticAllocaMap.find(AI);
1187         if (SI != FuncInfo->StaticAllocaMap.end())
1188           FI = SI->second;
1189       } else if (const auto *Arg = dyn_cast<Argument>(Address))
1190         FI = FuncInfo->getArgumentFrameIndex(Arg);
1191
1192       if (FI == INT_MAX)
1193         continue;
1194
1195       DIExpression *Expr = DI->getExpression();
1196       if (Offset.getBoolValue())
1197         Expr = DIExpression::prepend(Expr, DIExpression::NoDeref,
1198                                      Offset.getZExtValue());
1199       MF->setVariableDbgInfo(DI->getVariable(), Expr, FI, DI->getDebugLoc());
1200     }
1201   }
1202 }
1203
1204 /// Propagate swifterror values through the machine function CFG.
1205 static void propagateSwiftErrorVRegs(FunctionLoweringInfo *FuncInfo) {
1206   auto *TLI = FuncInfo->TLI;
1207   if (!TLI->supportSwiftError())
1208     return;
1209
1210   // We only need to do this when we have swifterror parameter or swifterror
1211   // alloc.
1212   if (FuncInfo->SwiftErrorVals.empty())
1213     return;
1214
1215   // For each machine basic block in reverse post order.
1216   ReversePostOrderTraversal<MachineFunction *> RPOT(FuncInfo->MF);
1217   for (ReversePostOrderTraversal<MachineFunction *>::rpo_iterator
1218            It = RPOT.begin(),
1219            E = RPOT.end();
1220        It != E; ++It) {
1221     MachineBasicBlock *MBB = *It;
1222
1223     // For each swifterror value in the function.
1224     for(const auto *SwiftErrorVal : FuncInfo->SwiftErrorVals) {
1225       auto Key = std::make_pair(MBB, SwiftErrorVal);
1226       auto UUseIt = FuncInfo->SwiftErrorVRegUpwardsUse.find(Key);
1227       auto VRegDefIt = FuncInfo->SwiftErrorVRegDefMap.find(Key);
1228       bool UpwardsUse = UUseIt != FuncInfo->SwiftErrorVRegUpwardsUse.end();
1229       unsigned UUseVReg = UpwardsUse ? UUseIt->second : 0;
1230       bool DownwardDef = VRegDefIt != FuncInfo->SwiftErrorVRegDefMap.end();
1231       assert(!(UpwardsUse && !DownwardDef) &&
1232              "We can't have an upwards use but no downwards def");
1233
1234       // If there is no upwards exposed use and an entry for the swifterror in
1235       // the def map for this value we don't need to do anything: We already
1236       // have a downward def for this basic block.
1237       if (!UpwardsUse && DownwardDef)
1238         continue;
1239
1240       // Otherwise we either have an upwards exposed use vreg that we need to
1241       // materialize or need to forward the downward def from predecessors.
1242
1243       // Check whether we have a single vreg def from all predecessors.
1244       // Otherwise we need a phi.
1245       SmallVector<std::pair<MachineBasicBlock *, unsigned>, 4> VRegs;
1246       SmallSet<const MachineBasicBlock*, 8> Visited;
1247       for (auto *Pred : MBB->predecessors()) {
1248         if (!Visited.insert(Pred).second)
1249           continue;
1250         VRegs.push_back(std::make_pair(
1251             Pred, FuncInfo->getOrCreateSwiftErrorVReg(Pred, SwiftErrorVal)));
1252         if (Pred != MBB)
1253           continue;
1254         // We have a self-edge.
1255         // If there was no upwards use in this basic block there is now one: the
1256         // phi needs to use it self.
1257         if (!UpwardsUse) {
1258           UpwardsUse = true;
1259           UUseIt = FuncInfo->SwiftErrorVRegUpwardsUse.find(Key);
1260           assert(UUseIt != FuncInfo->SwiftErrorVRegUpwardsUse.end());
1261           UUseVReg = UUseIt->second;
1262         }
1263       }
1264
1265       // We need a phi node if we have more than one predecessor with different
1266       // downward defs.
1267       bool needPHI =
1268           VRegs.size() >= 1 &&
1269           std::find_if(
1270               VRegs.begin(), VRegs.end(),
1271               [&](const std::pair<const MachineBasicBlock *, unsigned> &V)
1272                   -> bool { return V.second != VRegs[0].second; }) !=
1273               VRegs.end();
1274
1275       // If there is no upwards exposed used and we don't need a phi just
1276       // forward the swifterror vreg from the predecessor(s).
1277       if (!UpwardsUse && !needPHI) {
1278         assert(!VRegs.empty() &&
1279                "No predecessors? The entry block should bail out earlier");
1280         // Just forward the swifterror vreg from the predecessor(s).
1281         FuncInfo->setCurrentSwiftErrorVReg(MBB, SwiftErrorVal, VRegs[0].second);
1282         continue;
1283       }
1284
1285       auto DLoc = isa<Instruction>(SwiftErrorVal)
1286                       ? dyn_cast<Instruction>(SwiftErrorVal)->getDebugLoc()
1287                       : DebugLoc();
1288       const auto *TII = FuncInfo->MF->getSubtarget().getInstrInfo();
1289
1290       // If we don't need a phi create a copy to the upward exposed vreg.
1291       if (!needPHI) {
1292         assert(UpwardsUse);
1293         unsigned DestReg = UUseVReg;
1294         BuildMI(*MBB, MBB->getFirstNonPHI(), DLoc, TII->get(TargetOpcode::COPY),
1295                 DestReg)
1296             .addReg(VRegs[0].second);
1297         continue;
1298       }
1299
1300       // We need a phi: if there is an upwards exposed use we already have a
1301       // destination virtual register number otherwise we generate a new one.
1302       auto &DL = FuncInfo->MF->getDataLayout();
1303       auto const *RC = TLI->getRegClassFor(TLI->getPointerTy(DL));
1304       unsigned PHIVReg =
1305           UpwardsUse ? UUseVReg
1306                      : FuncInfo->MF->getRegInfo().createVirtualRegister(RC);
1307       MachineInstrBuilder SwiftErrorPHI =
1308           BuildMI(*MBB, MBB->getFirstNonPHI(), DLoc,
1309                   TII->get(TargetOpcode::PHI), PHIVReg);
1310       for (auto BBRegPair : VRegs) {
1311         SwiftErrorPHI.addReg(BBRegPair.second).addMBB(BBRegPair.first);
1312       }
1313
1314       // We did not have a definition in this block before: store the phi's vreg
1315       // as this block downward exposed def.
1316       if (!UpwardsUse)
1317         FuncInfo->setCurrentSwiftErrorVReg(MBB, SwiftErrorVal, PHIVReg);
1318     }
1319   }
1320 }
1321
1322 void SelectionDAGISel::SelectAllBasicBlocks(const Function &Fn) {
1323   FastISelFailed = false;
1324   // Initialize the Fast-ISel state, if needed.
1325   FastISel *FastIS = nullptr;
1326   if (TM.Options.EnableFastISel)
1327     FastIS = TLI->createFastISel(*FuncInfo, LibInfo);
1328
1329   setupSwiftErrorVals(Fn, TLI, FuncInfo);
1330
1331   ReversePostOrderTraversal<const Function*> RPOT(&Fn);
1332
1333   // Lower arguments up front. An RPO iteration always visits the entry block
1334   // first.
1335   assert(*RPOT.begin() == &Fn.getEntryBlock());
1336   ++NumEntryBlocks;
1337
1338   // Set up FuncInfo for ISel. Entry blocks never have PHIs.
1339   FuncInfo->MBB = FuncInfo->MBBMap[&Fn.getEntryBlock()];
1340   FuncInfo->InsertPt = FuncInfo->MBB->begin();
1341
1342   if (!FastIS) {
1343     LowerArguments(Fn);
1344   } else {
1345     // See if fast isel can lower the arguments.
1346     FastIS->startNewBlock();
1347     if (!FastIS->lowerArguments()) {
1348       FastISelFailed = true;
1349       // Fast isel failed to lower these arguments
1350       ++NumFastIselFailLowerArguments;
1351
1352       OptimizationRemarkMissed R("sdagisel", "FastISelFailure",
1353                                  Fn.getSubprogram(),
1354                                  &Fn.getEntryBlock());
1355       R << "FastISel didn't lower all arguments: "
1356         << ore::NV("Prototype", Fn.getType());
1357       reportFastISelFailure(*MF, *ORE, R, EnableFastISelAbort > 1);
1358
1359       // Use SelectionDAG argument lowering
1360       LowerArguments(Fn);
1361       CurDAG->setRoot(SDB->getControlRoot());
1362       SDB->clear();
1363       CodeGenAndEmitDAG();
1364     }
1365
1366     // If we inserted any instructions at the beginning, make a note of
1367     // where they are, so we can be sure to emit subsequent instructions
1368     // after them.
1369     if (FuncInfo->InsertPt != FuncInfo->MBB->begin())
1370       FastIS->setLastLocalValue(&*std::prev(FuncInfo->InsertPt));
1371     else
1372       FastIS->setLastLocalValue(nullptr);
1373   }
1374   createSwiftErrorEntriesInEntryBlock(FuncInfo, FastIS, TLI, TII, SDB);
1375
1376   processDbgDeclares(FuncInfo);
1377
1378   // Iterate over all basic blocks in the function.
1379   for (const BasicBlock *LLVMBB : RPOT) {
1380     if (OptLevel != CodeGenOpt::None) {
1381       bool AllPredsVisited = true;
1382       for (const_pred_iterator PI = pred_begin(LLVMBB), PE = pred_end(LLVMBB);
1383            PI != PE; ++PI) {
1384         if (!FuncInfo->VisitedBBs.count(*PI)) {
1385           AllPredsVisited = false;
1386           break;
1387         }
1388       }
1389
1390       if (AllPredsVisited) {
1391         for (BasicBlock::const_iterator I = LLVMBB->begin();
1392              const PHINode *PN = dyn_cast<PHINode>(I); ++I)
1393           FuncInfo->ComputePHILiveOutRegInfo(PN);
1394       } else {
1395         for (BasicBlock::const_iterator I = LLVMBB->begin();
1396              const PHINode *PN = dyn_cast<PHINode>(I); ++I)
1397           FuncInfo->InvalidatePHILiveOutRegInfo(PN);
1398       }
1399
1400       FuncInfo->VisitedBBs.insert(LLVMBB);
1401     }
1402
1403     BasicBlock::const_iterator const Begin =
1404         LLVMBB->getFirstNonPHI()->getIterator();
1405     BasicBlock::const_iterator const End = LLVMBB->end();
1406     BasicBlock::const_iterator BI = End;
1407
1408     FuncInfo->MBB = FuncInfo->MBBMap[LLVMBB];
1409     if (!FuncInfo->MBB)
1410       continue; // Some blocks like catchpads have no code or MBB.
1411
1412     // Insert new instructions after any phi or argument setup code.
1413     FuncInfo->InsertPt = FuncInfo->MBB->end();
1414
1415     // Setup an EH landing-pad block.
1416     FuncInfo->ExceptionPointerVirtReg = 0;
1417     FuncInfo->ExceptionSelectorVirtReg = 0;
1418     if (LLVMBB->isEHPad())
1419       if (!PrepareEHLandingPad())
1420         continue;
1421
1422     // Before doing SelectionDAG ISel, see if FastISel has been requested.
1423     if (FastIS) {
1424       if (LLVMBB != &Fn.getEntryBlock())
1425         FastIS->startNewBlock();
1426
1427       unsigned NumFastIselRemaining = std::distance(Begin, End);
1428       // Do FastISel on as many instructions as possible.
1429       for (; BI != Begin; --BI) {
1430         const Instruction *Inst = &*std::prev(BI);
1431
1432         // If we no longer require this instruction, skip it.
1433         if (isFoldedOrDeadInstruction(Inst, FuncInfo) ||
1434             ElidedArgCopyInstrs.count(Inst)) {
1435           --NumFastIselRemaining;
1436           continue;
1437         }
1438
1439         // Bottom-up: reset the insert pos at the top, after any local-value
1440         // instructions.
1441         FastIS->recomputeInsertPt();
1442
1443         // Try to select the instruction with FastISel.
1444         if (FastIS->selectInstruction(Inst)) {
1445           FastISelFailed = true;
1446           --NumFastIselRemaining;
1447           ++NumFastIselSuccess;
1448           // If fast isel succeeded, skip over all the folded instructions, and
1449           // then see if there is a load right before the selected instructions.
1450           // Try to fold the load if so.
1451           const Instruction *BeforeInst = Inst;
1452           while (BeforeInst != &*Begin) {
1453             BeforeInst = &*std::prev(BasicBlock::const_iterator(BeforeInst));
1454             if (!isFoldedOrDeadInstruction(BeforeInst, FuncInfo))
1455               break;
1456           }
1457           if (BeforeInst != Inst && isa<LoadInst>(BeforeInst) &&
1458               BeforeInst->hasOneUse() &&
1459               FastIS->tryToFoldLoad(cast<LoadInst>(BeforeInst), Inst)) {
1460             // If we succeeded, don't re-select the load.
1461             BI = std::next(BasicBlock::const_iterator(BeforeInst));
1462             --NumFastIselRemaining;
1463             ++NumFastIselSuccess;
1464           }
1465           continue;
1466         }
1467
1468         // Then handle certain instructions as single-LLVM-Instruction blocks.
1469         if (isa<CallInst>(Inst)) {
1470           OptimizationRemarkMissed R("sdagisel", "FastISelFailure",
1471                                      Inst->getDebugLoc(), LLVMBB);
1472
1473           R << "FastISel missed call";
1474
1475           if (R.isEnabled() || EnableFastISelAbort) {
1476             std::string InstStrStorage;
1477             raw_string_ostream InstStr(InstStrStorage);
1478             InstStr << *Inst;
1479
1480             R << ": " << InstStr.str();
1481           }
1482
1483           reportFastISelFailure(*MF, *ORE, R, EnableFastISelAbort > 2);
1484
1485           if (!Inst->getType()->isVoidTy() && !Inst->getType()->isTokenTy() &&
1486               !Inst->use_empty()) {
1487             unsigned &R = FuncInfo->ValueMap[Inst];
1488             if (!R)
1489               R = FuncInfo->CreateRegs(Inst->getType());
1490           }
1491
1492           bool HadTailCall = false;
1493           MachineBasicBlock::iterator SavedInsertPt = FuncInfo->InsertPt;
1494           SelectBasicBlock(Inst->getIterator(), BI, HadTailCall);
1495
1496           // If the call was emitted as a tail call, we're done with the block.
1497           // We also need to delete any previously emitted instructions.
1498           if (HadTailCall) {
1499             FastIS->removeDeadCode(SavedInsertPt, FuncInfo->MBB->end());
1500             --BI;
1501             break;
1502           }
1503
1504           // Recompute NumFastIselRemaining as Selection DAG instruction
1505           // selection may have handled the call, input args, etc.
1506           unsigned RemainingNow = std::distance(Begin, BI);
1507           NumFastIselFailures += NumFastIselRemaining - RemainingNow;
1508           NumFastIselRemaining = RemainingNow;
1509           continue;
1510         }
1511
1512         OptimizationRemarkMissed R("sdagisel", "FastISelFailure",
1513                                    Inst->getDebugLoc(), LLVMBB);
1514
1515         bool ShouldAbort = EnableFastISelAbort;
1516         if (isa<TerminatorInst>(Inst)) {
1517           // Use a different message for terminator misses.
1518           R << "FastISel missed terminator";
1519           // Don't abort for terminator unless the level is really high
1520           ShouldAbort = (EnableFastISelAbort > 2);
1521         } else {
1522           R << "FastISel missed";
1523         }
1524
1525         if (R.isEnabled() || EnableFastISelAbort) {
1526           std::string InstStrStorage;
1527           raw_string_ostream InstStr(InstStrStorage);
1528           InstStr << *Inst;
1529           R << ": " << InstStr.str();
1530         }
1531
1532         reportFastISelFailure(*MF, *ORE, R, ShouldAbort);
1533
1534         NumFastIselFailures += NumFastIselRemaining;
1535         break;
1536       }
1537
1538       FastIS->recomputeInsertPt();
1539     }
1540
1541     if (getAnalysis<StackProtector>().shouldEmitSDCheck(*LLVMBB)) {
1542       bool FunctionBasedInstrumentation =
1543           TLI->getSSPStackGuardCheck(*Fn.getParent());
1544       SDB->SPDescriptor.initialize(LLVMBB, FuncInfo->MBBMap[LLVMBB],
1545                                    FunctionBasedInstrumentation);
1546     }
1547
1548     if (Begin != BI)
1549       ++NumDAGBlocks;
1550     else
1551       ++NumFastIselBlocks;
1552
1553     if (Begin != BI) {
1554       // Run SelectionDAG instruction selection on the remainder of the block
1555       // not handled by FastISel. If FastISel is not run, this is the entire
1556       // block.
1557       bool HadTailCall;
1558       SelectBasicBlock(Begin, BI, HadTailCall);
1559
1560       // But if FastISel was run, we already selected some of the block.
1561       // If we emitted a tail-call, we need to delete any previously emitted
1562       // instruction that follows it.
1563       if (HadTailCall && FuncInfo->InsertPt != FuncInfo->MBB->end())
1564         FastIS->removeDeadCode(FuncInfo->InsertPt, FuncInfo->MBB->end());
1565     }
1566
1567     FinishBasicBlock();
1568     FuncInfo->PHINodesToUpdate.clear();
1569     ElidedArgCopyInstrs.clear();
1570   }
1571
1572   propagateSwiftErrorVRegs(FuncInfo);
1573
1574   delete FastIS;
1575   SDB->clearDanglingDebugInfo();
1576   SDB->SPDescriptor.resetPerFunctionState();
1577 }
1578
1579 /// Given that the input MI is before a partial terminator sequence TSeq, return
1580 /// true if M + TSeq also a partial terminator sequence.
1581 ///
1582 /// A Terminator sequence is a sequence of MachineInstrs which at this point in
1583 /// lowering copy vregs into physical registers, which are then passed into
1584 /// terminator instructors so we can satisfy ABI constraints. A partial
1585 /// terminator sequence is an improper subset of a terminator sequence (i.e. it
1586 /// may be the whole terminator sequence).
1587 static bool MIIsInTerminatorSequence(const MachineInstr &MI) {
1588   // If we do not have a copy or an implicit def, we return true if and only if
1589   // MI is a debug value.
1590   if (!MI.isCopy() && !MI.isImplicitDef())
1591     // Sometimes DBG_VALUE MI sneak in between the copies from the vregs to the
1592     // physical registers if there is debug info associated with the terminator
1593     // of our mbb. We want to include said debug info in our terminator
1594     // sequence, so we return true in that case.
1595     return MI.isDebugValue();
1596
1597   // We have left the terminator sequence if we are not doing one of the
1598   // following:
1599   //
1600   // 1. Copying a vreg into a physical register.
1601   // 2. Copying a vreg into a vreg.
1602   // 3. Defining a register via an implicit def.
1603
1604   // OPI should always be a register definition...
1605   MachineInstr::const_mop_iterator OPI = MI.operands_begin();
1606   if (!OPI->isReg() || !OPI->isDef())
1607     return false;
1608
1609   // Defining any register via an implicit def is always ok.
1610   if (MI.isImplicitDef())
1611     return true;
1612
1613   // Grab the copy source...
1614   MachineInstr::const_mop_iterator OPI2 = OPI;
1615   ++OPI2;
1616   assert(OPI2 != MI.operands_end()
1617          && "Should have a copy implying we should have 2 arguments.");
1618
1619   // Make sure that the copy dest is not a vreg when the copy source is a
1620   // physical register.
1621   if (!OPI2->isReg() ||
1622       (!TargetRegisterInfo::isPhysicalRegister(OPI->getReg()) &&
1623        TargetRegisterInfo::isPhysicalRegister(OPI2->getReg())))
1624     return false;
1625
1626   return true;
1627 }
1628
1629 /// Find the split point at which to splice the end of BB into its success stack
1630 /// protector check machine basic block.
1631 ///
1632 /// On many platforms, due to ABI constraints, terminators, even before register
1633 /// allocation, use physical registers. This creates an issue for us since
1634 /// physical registers at this point can not travel across basic
1635 /// blocks. Luckily, selectiondag always moves physical registers into vregs
1636 /// when they enter functions and moves them through a sequence of copies back
1637 /// into the physical registers right before the terminator creating a
1638 /// ``Terminator Sequence''. This function is searching for the beginning of the
1639 /// terminator sequence so that we can ensure that we splice off not just the
1640 /// terminator, but additionally the copies that move the vregs into the
1641 /// physical registers.
1642 static MachineBasicBlock::iterator
1643 FindSplitPointForStackProtector(MachineBasicBlock *BB) {
1644   MachineBasicBlock::iterator SplitPoint = BB->getFirstTerminator();
1645   //
1646   if (SplitPoint == BB->begin())
1647     return SplitPoint;
1648
1649   MachineBasicBlock::iterator Start = BB->begin();
1650   MachineBasicBlock::iterator Previous = SplitPoint;
1651   --Previous;
1652
1653   while (MIIsInTerminatorSequence(*Previous)) {
1654     SplitPoint = Previous;
1655     if (Previous == Start)
1656       break;
1657     --Previous;
1658   }
1659
1660   return SplitPoint;
1661 }
1662
1663 void
1664 SelectionDAGISel::FinishBasicBlock() {
1665   DEBUG(dbgs() << "Total amount of phi nodes to update: "
1666                << FuncInfo->PHINodesToUpdate.size() << "\n";
1667         for (unsigned i = 0, e = FuncInfo->PHINodesToUpdate.size(); i != e; ++i)
1668           dbgs() << "Node " << i << " : ("
1669                  << FuncInfo->PHINodesToUpdate[i].first
1670                  << ", " << FuncInfo->PHINodesToUpdate[i].second << ")\n");
1671
1672   // Next, now that we know what the last MBB the LLVM BB expanded is, update
1673   // PHI nodes in successors.
1674   for (unsigned i = 0, e = FuncInfo->PHINodesToUpdate.size(); i != e; ++i) {
1675     MachineInstrBuilder PHI(*MF, FuncInfo->PHINodesToUpdate[i].first);
1676     assert(PHI->isPHI() &&
1677            "This is not a machine PHI node that we are updating!");
1678     if (!FuncInfo->MBB->isSuccessor(PHI->getParent()))
1679       continue;
1680     PHI.addReg(FuncInfo->PHINodesToUpdate[i].second).addMBB(FuncInfo->MBB);
1681   }
1682
1683   // Handle stack protector.
1684   if (SDB->SPDescriptor.shouldEmitFunctionBasedCheckStackProtector()) {
1685     // The target provides a guard check function. There is no need to
1686     // generate error handling code or to split current basic block.
1687     MachineBasicBlock *ParentMBB = SDB->SPDescriptor.getParentMBB();
1688
1689     // Add load and check to the basicblock.
1690     FuncInfo->MBB = ParentMBB;
1691     FuncInfo->InsertPt =
1692         FindSplitPointForStackProtector(ParentMBB);
1693     SDB->visitSPDescriptorParent(SDB->SPDescriptor, ParentMBB);
1694     CurDAG->setRoot(SDB->getRoot());
1695     SDB->clear();
1696     CodeGenAndEmitDAG();
1697
1698     // Clear the Per-BB State.
1699     SDB->SPDescriptor.resetPerBBState();
1700   } else if (SDB->SPDescriptor.shouldEmitStackProtector()) {
1701     MachineBasicBlock *ParentMBB = SDB->SPDescriptor.getParentMBB();
1702     MachineBasicBlock *SuccessMBB = SDB->SPDescriptor.getSuccessMBB();
1703
1704     // Find the split point to split the parent mbb. At the same time copy all
1705     // physical registers used in the tail of parent mbb into virtual registers
1706     // before the split point and back into physical registers after the split
1707     // point. This prevents us needing to deal with Live-ins and many other
1708     // register allocation issues caused by us splitting the parent mbb. The
1709     // register allocator will clean up said virtual copies later on.
1710     MachineBasicBlock::iterator SplitPoint =
1711         FindSplitPointForStackProtector(ParentMBB);
1712
1713     // Splice the terminator of ParentMBB into SuccessMBB.
1714     SuccessMBB->splice(SuccessMBB->end(), ParentMBB,
1715                        SplitPoint,
1716                        ParentMBB->end());
1717
1718     // Add compare/jump on neq/jump to the parent BB.
1719     FuncInfo->MBB = ParentMBB;
1720     FuncInfo->InsertPt = ParentMBB->end();
1721     SDB->visitSPDescriptorParent(SDB->SPDescriptor, ParentMBB);
1722     CurDAG->setRoot(SDB->getRoot());
1723     SDB->clear();
1724     CodeGenAndEmitDAG();
1725
1726     // CodeGen Failure MBB if we have not codegened it yet.
1727     MachineBasicBlock *FailureMBB = SDB->SPDescriptor.getFailureMBB();
1728     if (FailureMBB->empty()) {
1729       FuncInfo->MBB = FailureMBB;
1730       FuncInfo->InsertPt = FailureMBB->end();
1731       SDB->visitSPDescriptorFailure(SDB->SPDescriptor);
1732       CurDAG->setRoot(SDB->getRoot());
1733       SDB->clear();
1734       CodeGenAndEmitDAG();
1735     }
1736
1737     // Clear the Per-BB State.
1738     SDB->SPDescriptor.resetPerBBState();
1739   }
1740
1741   // Lower each BitTestBlock.
1742   for (auto &BTB : SDB->BitTestCases) {
1743     // Lower header first, if it wasn't already lowered
1744     if (!BTB.Emitted) {
1745       // Set the current basic block to the mbb we wish to insert the code into
1746       FuncInfo->MBB = BTB.Parent;
1747       FuncInfo->InsertPt = FuncInfo->MBB->end();
1748       // Emit the code
1749       SDB->visitBitTestHeader(BTB, FuncInfo->MBB);
1750       CurDAG->setRoot(SDB->getRoot());
1751       SDB->clear();
1752       CodeGenAndEmitDAG();
1753     }
1754
1755     BranchProbability UnhandledProb = BTB.Prob;
1756     for (unsigned j = 0, ej = BTB.Cases.size(); j != ej; ++j) {
1757       UnhandledProb -= BTB.Cases[j].ExtraProb;
1758       // Set the current basic block to the mbb we wish to insert the code into
1759       FuncInfo->MBB = BTB.Cases[j].ThisBB;
1760       FuncInfo->InsertPt = FuncInfo->MBB->end();
1761       // Emit the code
1762
1763       // If all cases cover a contiguous range, it is not necessary to jump to
1764       // the default block after the last bit test fails. This is because the
1765       // range check during bit test header creation has guaranteed that every
1766       // case here doesn't go outside the range. In this case, there is no need
1767       // to perform the last bit test, as it will always be true. Instead, make
1768       // the second-to-last bit-test fall through to the target of the last bit
1769       // test, and delete the last bit test.
1770
1771       MachineBasicBlock *NextMBB;
1772       if (BTB.ContiguousRange && j + 2 == ej) {
1773         // Second-to-last bit-test with contiguous range: fall through to the
1774         // target of the final bit test.
1775         NextMBB = BTB.Cases[j + 1].TargetBB;
1776       } else if (j + 1 == ej) {
1777         // For the last bit test, fall through to Default.
1778         NextMBB = BTB.Default;
1779       } else {
1780         // Otherwise, fall through to the next bit test.
1781         NextMBB = BTB.Cases[j + 1].ThisBB;
1782       }
1783
1784       SDB->visitBitTestCase(BTB, NextMBB, UnhandledProb, BTB.Reg, BTB.Cases[j],
1785                             FuncInfo->MBB);
1786
1787       CurDAG->setRoot(SDB->getRoot());
1788       SDB->clear();
1789       CodeGenAndEmitDAG();
1790
1791       if (BTB.ContiguousRange && j + 2 == ej) {
1792         // Since we're not going to use the final bit test, remove it.
1793         BTB.Cases.pop_back();
1794         break;
1795       }
1796     }
1797
1798     // Update PHI Nodes
1799     for (unsigned pi = 0, pe = FuncInfo->PHINodesToUpdate.size();
1800          pi != pe; ++pi) {
1801       MachineInstrBuilder PHI(*MF, FuncInfo->PHINodesToUpdate[pi].first);
1802       MachineBasicBlock *PHIBB = PHI->getParent();
1803       assert(PHI->isPHI() &&
1804              "This is not a machine PHI node that we are updating!");
1805       // This is "default" BB. We have two jumps to it. From "header" BB and
1806       // from last "case" BB, unless the latter was skipped.
1807       if (PHIBB == BTB.Default) {
1808         PHI.addReg(FuncInfo->PHINodesToUpdate[pi].second).addMBB(BTB.Parent);
1809         if (!BTB.ContiguousRange) {
1810           PHI.addReg(FuncInfo->PHINodesToUpdate[pi].second)
1811               .addMBB(BTB.Cases.back().ThisBB);
1812          }
1813       }
1814       // One of "cases" BB.
1815       for (unsigned j = 0, ej = BTB.Cases.size();
1816            j != ej; ++j) {
1817         MachineBasicBlock* cBB = BTB.Cases[j].ThisBB;
1818         if (cBB->isSuccessor(PHIBB))
1819           PHI.addReg(FuncInfo->PHINodesToUpdate[pi].second).addMBB(cBB);
1820       }
1821     }
1822   }
1823   SDB->BitTestCases.clear();
1824
1825   // If the JumpTable record is filled in, then we need to emit a jump table.
1826   // Updating the PHI nodes is tricky in this case, since we need to determine
1827   // whether the PHI is a successor of the range check MBB or the jump table MBB
1828   for (unsigned i = 0, e = SDB->JTCases.size(); i != e; ++i) {
1829     // Lower header first, if it wasn't already lowered
1830     if (!SDB->JTCases[i].first.Emitted) {
1831       // Set the current basic block to the mbb we wish to insert the code into
1832       FuncInfo->MBB = SDB->JTCases[i].first.HeaderBB;
1833       FuncInfo->InsertPt = FuncInfo->MBB->end();
1834       // Emit the code
1835       SDB->visitJumpTableHeader(SDB->JTCases[i].second, SDB->JTCases[i].first,
1836                                 FuncInfo->MBB);
1837       CurDAG->setRoot(SDB->getRoot());
1838       SDB->clear();
1839       CodeGenAndEmitDAG();
1840     }
1841
1842     // Set the current basic block to the mbb we wish to insert the code into
1843     FuncInfo->MBB = SDB->JTCases[i].second.MBB;
1844     FuncInfo->InsertPt = FuncInfo->MBB->end();
1845     // Emit the code
1846     SDB->visitJumpTable(SDB->JTCases[i].second);
1847     CurDAG->setRoot(SDB->getRoot());
1848     SDB->clear();
1849     CodeGenAndEmitDAG();
1850
1851     // Update PHI Nodes
1852     for (unsigned pi = 0, pe = FuncInfo->PHINodesToUpdate.size();
1853          pi != pe; ++pi) {
1854       MachineInstrBuilder PHI(*MF, FuncInfo->PHINodesToUpdate[pi].first);
1855       MachineBasicBlock *PHIBB = PHI->getParent();
1856       assert(PHI->isPHI() &&
1857              "This is not a machine PHI node that we are updating!");
1858       // "default" BB. We can go there only from header BB.
1859       if (PHIBB == SDB->JTCases[i].second.Default)
1860         PHI.addReg(FuncInfo->PHINodesToUpdate[pi].second)
1861            .addMBB(SDB->JTCases[i].first.HeaderBB);
1862       // JT BB. Just iterate over successors here
1863       if (FuncInfo->MBB->isSuccessor(PHIBB))
1864         PHI.addReg(FuncInfo->PHINodesToUpdate[pi].second).addMBB(FuncInfo->MBB);
1865     }
1866   }
1867   SDB->JTCases.clear();
1868
1869   // If we generated any switch lowering information, build and codegen any
1870   // additional DAGs necessary.
1871   for (unsigned i = 0, e = SDB->SwitchCases.size(); i != e; ++i) {
1872     // Set the current basic block to the mbb we wish to insert the code into
1873     FuncInfo->MBB = SDB->SwitchCases[i].ThisBB;
1874     FuncInfo->InsertPt = FuncInfo->MBB->end();
1875
1876     // Determine the unique successors.
1877     SmallVector<MachineBasicBlock *, 2> Succs;
1878     Succs.push_back(SDB->SwitchCases[i].TrueBB);
1879     if (SDB->SwitchCases[i].TrueBB != SDB->SwitchCases[i].FalseBB)
1880       Succs.push_back(SDB->SwitchCases[i].FalseBB);
1881
1882     // Emit the code. Note that this could result in FuncInfo->MBB being split.
1883     SDB->visitSwitchCase(SDB->SwitchCases[i], FuncInfo->MBB);
1884     CurDAG->setRoot(SDB->getRoot());
1885     SDB->clear();
1886     CodeGenAndEmitDAG();
1887
1888     // Remember the last block, now that any splitting is done, for use in
1889     // populating PHI nodes in successors.
1890     MachineBasicBlock *ThisBB = FuncInfo->MBB;
1891
1892     // Handle any PHI nodes in successors of this chunk, as if we were coming
1893     // from the original BB before switch expansion.  Note that PHI nodes can
1894     // occur multiple times in PHINodesToUpdate.  We have to be very careful to
1895     // handle them the right number of times.
1896     for (unsigned i = 0, e = Succs.size(); i != e; ++i) {
1897       FuncInfo->MBB = Succs[i];
1898       FuncInfo->InsertPt = FuncInfo->MBB->end();
1899       // FuncInfo->MBB may have been removed from the CFG if a branch was
1900       // constant folded.
1901       if (ThisBB->isSuccessor(FuncInfo->MBB)) {
1902         for (MachineBasicBlock::iterator
1903              MBBI = FuncInfo->MBB->begin(), MBBE = FuncInfo->MBB->end();
1904              MBBI != MBBE && MBBI->isPHI(); ++MBBI) {
1905           MachineInstrBuilder PHI(*MF, MBBI);
1906           // This value for this PHI node is recorded in PHINodesToUpdate.
1907           for (unsigned pn = 0; ; ++pn) {
1908             assert(pn != FuncInfo->PHINodesToUpdate.size() &&
1909                    "Didn't find PHI entry!");
1910             if (FuncInfo->PHINodesToUpdate[pn].first == PHI) {
1911               PHI.addReg(FuncInfo->PHINodesToUpdate[pn].second).addMBB(ThisBB);
1912               break;
1913             }
1914           }
1915         }
1916       }
1917     }
1918   }
1919   SDB->SwitchCases.clear();
1920 }
1921
1922 /// Create the scheduler. If a specific scheduler was specified
1923 /// via the SchedulerRegistry, use it, otherwise select the
1924 /// one preferred by the target.
1925 ///
1926 ScheduleDAGSDNodes *SelectionDAGISel::CreateScheduler() {
1927   return ISHeuristic(this, OptLevel);
1928 }
1929
1930 //===----------------------------------------------------------------------===//
1931 // Helper functions used by the generated instruction selector.
1932 //===----------------------------------------------------------------------===//
1933 // Calls to these methods are generated by tblgen.
1934
1935 /// CheckAndMask - The isel is trying to match something like (and X, 255).  If
1936 /// the dag combiner simplified the 255, we still want to match.  RHS is the
1937 /// actual value in the DAG on the RHS of an AND, and DesiredMaskS is the value
1938 /// specified in the .td file (e.g. 255).
1939 bool SelectionDAGISel::CheckAndMask(SDValue LHS, ConstantSDNode *RHS,
1940                                     int64_t DesiredMaskS) const {
1941   const APInt &ActualMask = RHS->getAPIntValue();
1942   const APInt &DesiredMask = APInt(LHS.getValueSizeInBits(), DesiredMaskS);
1943
1944   // If the actual mask exactly matches, success!
1945   if (ActualMask == DesiredMask)
1946     return true;
1947
1948   // If the actual AND mask is allowing unallowed bits, this doesn't match.
1949   if (ActualMask.intersects(~DesiredMask))
1950     return false;
1951
1952   // Otherwise, the DAG Combiner may have proven that the value coming in is
1953   // either already zero or is not demanded.  Check for known zero input bits.
1954   APInt NeededMask = DesiredMask & ~ActualMask;
1955   if (CurDAG->MaskedValueIsZero(LHS, NeededMask))
1956     return true;
1957
1958   // TODO: check to see if missing bits are just not demanded.
1959
1960   // Otherwise, this pattern doesn't match.
1961   return false;
1962 }
1963
1964 /// CheckOrMask - The isel is trying to match something like (or X, 255).  If
1965 /// the dag combiner simplified the 255, we still want to match.  RHS is the
1966 /// actual value in the DAG on the RHS of an OR, and DesiredMaskS is the value
1967 /// specified in the .td file (e.g. 255).
1968 bool SelectionDAGISel::CheckOrMask(SDValue LHS, ConstantSDNode *RHS,
1969                                    int64_t DesiredMaskS) const {
1970   const APInt &ActualMask = RHS->getAPIntValue();
1971   const APInt &DesiredMask = APInt(LHS.getValueSizeInBits(), DesiredMaskS);
1972
1973   // If the actual mask exactly matches, success!
1974   if (ActualMask == DesiredMask)
1975     return true;
1976
1977   // If the actual AND mask is allowing unallowed bits, this doesn't match.
1978   if (ActualMask.intersects(~DesiredMask))
1979     return false;
1980
1981   // Otherwise, the DAG Combiner may have proven that the value coming in is
1982   // either already zero or is not demanded.  Check for known zero input bits.
1983   APInt NeededMask = DesiredMask & ~ActualMask;
1984
1985   KnownBits Known;
1986   CurDAG->computeKnownBits(LHS, Known);
1987
1988   // If all the missing bits in the or are already known to be set, match!
1989   if (NeededMask.isSubsetOf(Known.One))
1990     return true;
1991
1992   // TODO: check to see if missing bits are just not demanded.
1993
1994   // Otherwise, this pattern doesn't match.
1995   return false;
1996 }
1997
1998 /// SelectInlineAsmMemoryOperands - Calls to this are automatically generated
1999 /// by tblgen.  Others should not call it.
2000 void SelectionDAGISel::SelectInlineAsmMemoryOperands(std::vector<SDValue> &Ops,
2001                                                      const SDLoc &DL) {
2002   std::vector<SDValue> InOps;
2003   std::swap(InOps, Ops);
2004
2005   Ops.push_back(InOps[InlineAsm::Op_InputChain]); // 0
2006   Ops.push_back(InOps[InlineAsm::Op_AsmString]);  // 1
2007   Ops.push_back(InOps[InlineAsm::Op_MDNode]);     // 2, !srcloc
2008   Ops.push_back(InOps[InlineAsm::Op_ExtraInfo]);  // 3 (SideEffect, AlignStack)
2009
2010   unsigned i = InlineAsm::Op_FirstOperand, e = InOps.size();
2011   if (InOps[e-1].getValueType() == MVT::Glue)
2012     --e;  // Don't process a glue operand if it is here.
2013
2014   while (i != e) {
2015     unsigned Flags = cast<ConstantSDNode>(InOps[i])->getZExtValue();
2016     if (!InlineAsm::isMemKind(Flags)) {
2017       // Just skip over this operand, copying the operands verbatim.
2018       Ops.insert(Ops.end(), InOps.begin()+i,
2019                  InOps.begin()+i+InlineAsm::getNumOperandRegisters(Flags) + 1);
2020       i += InlineAsm::getNumOperandRegisters(Flags) + 1;
2021     } else {
2022       assert(InlineAsm::getNumOperandRegisters(Flags) == 1 &&
2023              "Memory operand with multiple values?");
2024
2025       unsigned TiedToOperand;
2026       if (InlineAsm::isUseOperandTiedToDef(Flags, TiedToOperand)) {
2027         // We need the constraint ID from the operand this is tied to.
2028         unsigned CurOp = InlineAsm::Op_FirstOperand;
2029         Flags = cast<ConstantSDNode>(InOps[CurOp])->getZExtValue();
2030         for (; TiedToOperand; --TiedToOperand) {
2031           CurOp += InlineAsm::getNumOperandRegisters(Flags)+1;
2032           Flags = cast<ConstantSDNode>(InOps[CurOp])->getZExtValue();
2033         }
2034       }
2035
2036       // Otherwise, this is a memory operand.  Ask the target to select it.
2037       std::vector<SDValue> SelOps;
2038       unsigned ConstraintID = InlineAsm::getMemoryConstraintID(Flags);
2039       if (SelectInlineAsmMemoryOperand(InOps[i+1], ConstraintID, SelOps))
2040         report_fatal_error("Could not match memory address.  Inline asm"
2041                            " failure!");
2042
2043       // Add this to the output node.
2044       unsigned NewFlags =
2045         InlineAsm::getFlagWord(InlineAsm::Kind_Mem, SelOps.size());
2046       NewFlags = InlineAsm::getFlagWordForMem(NewFlags, ConstraintID);
2047       Ops.push_back(CurDAG->getTargetConstant(NewFlags, DL, MVT::i32));
2048       Ops.insert(Ops.end(), SelOps.begin(), SelOps.end());
2049       i += 2;
2050     }
2051   }
2052
2053   // Add the glue input back if present.
2054   if (e != InOps.size())
2055     Ops.push_back(InOps.back());
2056 }
2057
2058 /// findGlueUse - Return use of MVT::Glue value produced by the specified
2059 /// SDNode.
2060 ///
2061 static SDNode *findGlueUse(SDNode *N) {
2062   unsigned FlagResNo = N->getNumValues()-1;
2063   for (SDNode::use_iterator I = N->use_begin(), E = N->use_end(); I != E; ++I) {
2064     SDUse &Use = I.getUse();
2065     if (Use.getResNo() == FlagResNo)
2066       return Use.getUser();
2067   }
2068   return nullptr;
2069 }
2070
2071 /// findNonImmUse - Return true if "Use" is a non-immediate use of "Def".
2072 /// This function recursively traverses up the operand chain, ignoring
2073 /// certain nodes.
2074 static bool findNonImmUse(SDNode *Use, SDNode* Def, SDNode *ImmedUse,
2075                           SDNode *Root, SmallPtrSetImpl<SDNode*> &Visited,
2076                           bool IgnoreChains) {
2077   // The NodeID's are given uniques ID's where a node ID is guaranteed to be
2078   // greater than all of its (recursive) operands.  If we scan to a point where
2079   // 'use' is smaller than the node we're scanning for, then we know we will
2080   // never find it.
2081   //
2082   // The Use may be -1 (unassigned) if it is a newly allocated node.  This can
2083   // happen because we scan down to newly selected nodes in the case of glue
2084   // uses.
2085   if ((Use->getNodeId() < Def->getNodeId() && Use->getNodeId() != -1))
2086     return false;
2087
2088   // Don't revisit nodes if we already scanned it and didn't fail, we know we
2089   // won't fail if we scan it again.
2090   if (!Visited.insert(Use).second)
2091     return false;
2092
2093   for (const SDValue &Op : Use->op_values()) {
2094     // Ignore chain uses, they are validated by HandleMergeInputChains.
2095     if (Op.getValueType() == MVT::Other && IgnoreChains)
2096       continue;
2097
2098     SDNode *N = Op.getNode();
2099     if (N == Def) {
2100       if (Use == ImmedUse || Use == Root)
2101         continue;  // We are not looking for immediate use.
2102       assert(N != Root);
2103       return true;
2104     }
2105
2106     // Traverse up the operand chain.
2107     if (findNonImmUse(N, Def, ImmedUse, Root, Visited, IgnoreChains))
2108       return true;
2109   }
2110   return false;
2111 }
2112
2113 /// IsProfitableToFold - Returns true if it's profitable to fold the specific
2114 /// operand node N of U during instruction selection that starts at Root.
2115 bool SelectionDAGISel::IsProfitableToFold(SDValue N, SDNode *U,
2116                                           SDNode *Root) const {
2117   if (OptLevel == CodeGenOpt::None) return false;
2118   return N.hasOneUse();
2119 }
2120
2121 /// IsLegalToFold - Returns true if the specific operand node N of
2122 /// U can be folded during instruction selection that starts at Root.
2123 bool SelectionDAGISel::IsLegalToFold(SDValue N, SDNode *U, SDNode *Root,
2124                                      CodeGenOpt::Level OptLevel,
2125                                      bool IgnoreChains) {
2126   if (OptLevel == CodeGenOpt::None) return false;
2127
2128   // If Root use can somehow reach N through a path that that doesn't contain
2129   // U then folding N would create a cycle. e.g. In the following
2130   // diagram, Root can reach N through X. If N is folded into into Root, then
2131   // X is both a predecessor and a successor of U.
2132   //
2133   //          [N*]           //
2134   //         ^   ^           //
2135   //        /     \          //
2136   //      [U*]    [X]?       //
2137   //        ^     ^          //
2138   //         \   /           //
2139   //          \ /            //
2140   //         [Root*]         //
2141   //
2142   // * indicates nodes to be folded together.
2143   //
2144   // If Root produces glue, then it gets (even more) interesting. Since it
2145   // will be "glued" together with its glue use in the scheduler, we need to
2146   // check if it might reach N.
2147   //
2148   //          [N*]           //
2149   //         ^   ^           //
2150   //        /     \          //
2151   //      [U*]    [X]?       //
2152   //        ^       ^        //
2153   //         \       \       //
2154   //          \      |       //
2155   //         [Root*] |       //
2156   //          ^      |       //
2157   //          f      |       //
2158   //          |      /       //
2159   //         [Y]    /        //
2160   //           ^   /         //
2161   //           f  /          //
2162   //           | /           //
2163   //          [GU]           //
2164   //
2165   // If GU (glue use) indirectly reaches N (the load), and Root folds N
2166   // (call it Fold), then X is a predecessor of GU and a successor of
2167   // Fold. But since Fold and GU are glued together, this will create
2168   // a cycle in the scheduling graph.
2169
2170   // If the node has glue, walk down the graph to the "lowest" node in the
2171   // glueged set.
2172   EVT VT = Root->getValueType(Root->getNumValues()-1);
2173   while (VT == MVT::Glue) {
2174     SDNode *GU = findGlueUse(Root);
2175     if (!GU)
2176       break;
2177     Root = GU;
2178     VT = Root->getValueType(Root->getNumValues()-1);
2179
2180     // If our query node has a glue result with a use, we've walked up it.  If
2181     // the user (which has already been selected) has a chain or indirectly uses
2182     // the chain, our WalkChainUsers predicate will not consider it.  Because of
2183     // this, we cannot ignore chains in this predicate.
2184     IgnoreChains = false;
2185   }
2186
2187   SmallPtrSet<SDNode*, 16> Visited;
2188   return !findNonImmUse(Root, N.getNode(), U, Root, Visited, IgnoreChains);
2189 }
2190
2191 void SelectionDAGISel::Select_INLINEASM(SDNode *N) {
2192   SDLoc DL(N);
2193
2194   std::vector<SDValue> Ops(N->op_begin(), N->op_end());
2195   SelectInlineAsmMemoryOperands(Ops, DL);
2196
2197   const EVT VTs[] = {MVT::Other, MVT::Glue};
2198   SDValue New = CurDAG->getNode(ISD::INLINEASM, DL, VTs, Ops);
2199   New->setNodeId(-1);
2200   ReplaceUses(N, New.getNode());
2201   CurDAG->RemoveDeadNode(N);
2202 }
2203
2204 void SelectionDAGISel::Select_READ_REGISTER(SDNode *Op) {
2205   SDLoc dl(Op);
2206   MDNodeSDNode *MD = dyn_cast<MDNodeSDNode>(Op->getOperand(1));
2207   const MDString *RegStr = dyn_cast<MDString>(MD->getMD()->getOperand(0));
2208   unsigned Reg =
2209       TLI->getRegisterByName(RegStr->getString().data(), Op->getValueType(0),
2210                              *CurDAG);
2211   SDValue New = CurDAG->getCopyFromReg(
2212                         Op->getOperand(0), dl, Reg, Op->getValueType(0));
2213   New->setNodeId(-1);
2214   ReplaceUses(Op, New.getNode());
2215   CurDAG->RemoveDeadNode(Op);
2216 }
2217
2218 void SelectionDAGISel::Select_WRITE_REGISTER(SDNode *Op) {
2219   SDLoc dl(Op);
2220   MDNodeSDNode *MD = dyn_cast<MDNodeSDNode>(Op->getOperand(1));
2221   const MDString *RegStr = dyn_cast<MDString>(MD->getMD()->getOperand(0));
2222   unsigned Reg = TLI->getRegisterByName(RegStr->getString().data(),
2223                                         Op->getOperand(2).getValueType(),
2224                                         *CurDAG);
2225   SDValue New = CurDAG->getCopyToReg(
2226                         Op->getOperand(0), dl, Reg, Op->getOperand(2));
2227   New->setNodeId(-1);
2228   ReplaceUses(Op, New.getNode());
2229   CurDAG->RemoveDeadNode(Op);
2230 }
2231
2232 void SelectionDAGISel::Select_UNDEF(SDNode *N) {
2233   CurDAG->SelectNodeTo(N, TargetOpcode::IMPLICIT_DEF, N->getValueType(0));
2234 }
2235
2236 /// GetVBR - decode a vbr encoding whose top bit is set.
2237 LLVM_ATTRIBUTE_ALWAYS_INLINE static inline uint64_t
2238 GetVBR(uint64_t Val, const unsigned char *MatcherTable, unsigned &Idx) {
2239   assert(Val >= 128 && "Not a VBR");
2240   Val &= 127;  // Remove first vbr bit.
2241
2242   unsigned Shift = 7;
2243   uint64_t NextBits;
2244   do {
2245     NextBits = MatcherTable[Idx++];
2246     Val |= (NextBits&127) << Shift;
2247     Shift += 7;
2248   } while (NextBits & 128);
2249
2250   return Val;
2251 }
2252
2253 /// When a match is complete, this method updates uses of interior chain results
2254 /// to use the new results.
2255 void SelectionDAGISel::UpdateChains(
2256     SDNode *NodeToMatch, SDValue InputChain,
2257     SmallVectorImpl<SDNode *> &ChainNodesMatched, bool isMorphNodeTo) {
2258   SmallVector<SDNode*, 4> NowDeadNodes;
2259
2260   // Now that all the normal results are replaced, we replace the chain and
2261   // glue results if present.
2262   if (!ChainNodesMatched.empty()) {
2263     assert(InputChain.getNode() &&
2264            "Matched input chains but didn't produce a chain");
2265     // Loop over all of the nodes we matched that produced a chain result.
2266     // Replace all the chain results with the final chain we ended up with.
2267     for (unsigned i = 0, e = ChainNodesMatched.size(); i != e; ++i) {
2268       SDNode *ChainNode = ChainNodesMatched[i];
2269       // If ChainNode is null, it's because we replaced it on a previous
2270       // iteration and we cleared it out of the map. Just skip it.
2271       if (!ChainNode)
2272         continue;
2273
2274       assert(ChainNode->getOpcode() != ISD::DELETED_NODE &&
2275              "Deleted node left in chain");
2276
2277       // Don't replace the results of the root node if we're doing a
2278       // MorphNodeTo.
2279       if (ChainNode == NodeToMatch && isMorphNodeTo)
2280         continue;
2281
2282       SDValue ChainVal = SDValue(ChainNode, ChainNode->getNumValues()-1);
2283       if (ChainVal.getValueType() == MVT::Glue)
2284         ChainVal = ChainVal.getValue(ChainVal->getNumValues()-2);
2285       assert(ChainVal.getValueType() == MVT::Other && "Not a chain?");
2286       SelectionDAG::DAGNodeDeletedListener NDL(
2287           *CurDAG, [&](SDNode *N, SDNode *E) {
2288             std::replace(ChainNodesMatched.begin(), ChainNodesMatched.end(), N,
2289                          static_cast<SDNode *>(nullptr));
2290           });
2291       CurDAG->ReplaceAllUsesOfValueWith(ChainVal, InputChain);
2292
2293       // If the node became dead and we haven't already seen it, delete it.
2294       if (ChainNode != NodeToMatch && ChainNode->use_empty() &&
2295           !std::count(NowDeadNodes.begin(), NowDeadNodes.end(), ChainNode))
2296         NowDeadNodes.push_back(ChainNode);
2297     }
2298   }
2299
2300   if (!NowDeadNodes.empty())
2301     CurDAG->RemoveDeadNodes(NowDeadNodes);
2302
2303   DEBUG(dbgs() << "ISEL: Match complete!\n");
2304 }
2305
2306 enum ChainResult {
2307   CR_Simple,
2308   CR_InducesCycle,
2309   CR_LeadsToInteriorNode
2310 };
2311
2312 /// WalkChainUsers - Walk down the users of the specified chained node that is
2313 /// part of the pattern we're matching, looking at all of the users we find.
2314 /// This determines whether something is an interior node, whether we have a
2315 /// non-pattern node in between two pattern nodes (which prevent folding because
2316 /// it would induce a cycle) and whether we have a TokenFactor node sandwiched
2317 /// between pattern nodes (in which case the TF becomes part of the pattern).
2318 ///
2319 /// The walk we do here is guaranteed to be small because we quickly get down to
2320 /// already selected nodes "below" us.
2321 static ChainResult
2322 WalkChainUsers(const SDNode *ChainedNode,
2323                SmallVectorImpl<SDNode *> &ChainedNodesInPattern,
2324                DenseMap<const SDNode *, ChainResult> &TokenFactorResult,
2325                SmallVectorImpl<SDNode *> &InteriorChainedNodes) {
2326   ChainResult Result = CR_Simple;
2327
2328   for (SDNode::use_iterator UI = ChainedNode->use_begin(),
2329          E = ChainedNode->use_end(); UI != E; ++UI) {
2330     // Make sure the use is of the chain, not some other value we produce.
2331     if (UI.getUse().getValueType() != MVT::Other) continue;
2332
2333     SDNode *User = *UI;
2334
2335     if (User->getOpcode() == ISD::HANDLENODE)  // Root of the graph.
2336       continue;
2337
2338     // If we see an already-selected machine node, then we've gone beyond the
2339     // pattern that we're selecting down into the already selected chunk of the
2340     // DAG.
2341     unsigned UserOpcode = User->getOpcode();
2342     if (User->isMachineOpcode() ||
2343         UserOpcode == ISD::CopyToReg ||
2344         UserOpcode == ISD::CopyFromReg ||
2345         UserOpcode == ISD::INLINEASM ||
2346         UserOpcode == ISD::EH_LABEL ||
2347         UserOpcode == ISD::LIFETIME_START ||
2348         UserOpcode == ISD::LIFETIME_END) {
2349       // If their node ID got reset to -1 then they've already been selected.
2350       // Treat them like a MachineOpcode.
2351       if (User->getNodeId() == -1)
2352         continue;
2353     }
2354
2355     // If we have a TokenFactor, we handle it specially.
2356     if (User->getOpcode() != ISD::TokenFactor) {
2357       // If the node isn't a token factor and isn't part of our pattern, then it
2358       // must be a random chained node in between two nodes we're selecting.
2359       // This happens when we have something like:
2360       //   x = load ptr
2361       //   call
2362       //   y = x+4
2363       //   store y -> ptr
2364       // Because we structurally match the load/store as a read/modify/write,
2365       // but the call is chained between them.  We cannot fold in this case
2366       // because it would induce a cycle in the graph.
2367       if (!std::count(ChainedNodesInPattern.begin(),
2368                       ChainedNodesInPattern.end(), User))
2369         return CR_InducesCycle;
2370
2371       // Otherwise we found a node that is part of our pattern.  For example in:
2372       //   x = load ptr
2373       //   y = x+4
2374       //   store y -> ptr
2375       // This would happen when we're scanning down from the load and see the
2376       // store as a user.  Record that there is a use of ChainedNode that is
2377       // part of the pattern and keep scanning uses.
2378       Result = CR_LeadsToInteriorNode;
2379       InteriorChainedNodes.push_back(User);
2380       continue;
2381     }
2382
2383     // If we found a TokenFactor, there are two cases to consider: first if the
2384     // TokenFactor is just hanging "below" the pattern we're matching (i.e. no
2385     // uses of the TF are in our pattern) we just want to ignore it.  Second,
2386     // the TokenFactor can be sandwiched in between two chained nodes, like so:
2387     //     [Load chain]
2388     //         ^
2389     //         |
2390     //       [Load]
2391     //       ^    ^
2392     //       |    \                    DAG's like cheese
2393     //      /       \                       do you?
2394     //     /         |
2395     // [TokenFactor] [Op]
2396     //     ^          ^
2397     //     |          |
2398     //      \        /
2399     //       \      /
2400     //       [Store]
2401     //
2402     // In this case, the TokenFactor becomes part of our match and we rewrite it
2403     // as a new TokenFactor.
2404     //
2405     // To distinguish these two cases, do a recursive walk down the uses.
2406     auto MemoizeResult = TokenFactorResult.find(User);
2407     bool Visited = MemoizeResult != TokenFactorResult.end();
2408     // Recursively walk chain users only if the result is not memoized.
2409     if (!Visited) {
2410       auto Res = WalkChainUsers(User, ChainedNodesInPattern, TokenFactorResult,
2411                                 InteriorChainedNodes);
2412       MemoizeResult = TokenFactorResult.insert(std::make_pair(User, Res)).first;
2413     }
2414     switch (MemoizeResult->second) {
2415     case CR_Simple:
2416       // If the uses of the TokenFactor are just already-selected nodes, ignore
2417       // it, it is "below" our pattern.
2418       continue;
2419     case CR_InducesCycle:
2420       // If the uses of the TokenFactor lead to nodes that are not part of our
2421       // pattern that are not selected, folding would turn this into a cycle,
2422       // bail out now.
2423       return CR_InducesCycle;
2424     case CR_LeadsToInteriorNode:
2425       break;  // Otherwise, keep processing.
2426     }
2427
2428     // Okay, we know we're in the interesting interior case.  The TokenFactor
2429     // is now going to be considered part of the pattern so that we rewrite its
2430     // uses (it may have uses that are not part of the pattern) with the
2431     // ultimate chain result of the generated code.  We will also add its chain
2432     // inputs as inputs to the ultimate TokenFactor we create.
2433     Result = CR_LeadsToInteriorNode;
2434     if (!Visited) {
2435       ChainedNodesInPattern.push_back(User);
2436       InteriorChainedNodes.push_back(User);
2437     }
2438   }
2439
2440   return Result;
2441 }
2442
2443 /// HandleMergeInputChains - This implements the OPC_EmitMergeInputChains
2444 /// operation for when the pattern matched at least one node with a chains.  The
2445 /// input vector contains a list of all of the chained nodes that we match.  We
2446 /// must determine if this is a valid thing to cover (i.e. matching it won't
2447 /// induce cycles in the DAG) and if so, creating a TokenFactor node. that will
2448 /// be used as the input node chain for the generated nodes.
2449 static SDValue
2450 HandleMergeInputChains(SmallVectorImpl<SDNode*> &ChainNodesMatched,
2451                        SelectionDAG *CurDAG) {
2452   // Used for memoization. Without it WalkChainUsers could take exponential
2453   // time to run.
2454   DenseMap<const SDNode *, ChainResult> TokenFactorResult;
2455   // Walk all of the chained nodes we've matched, recursively scanning down the
2456   // users of the chain result. This adds any TokenFactor nodes that are caught
2457   // in between chained nodes to the chained and interior nodes list.
2458   SmallVector<SDNode*, 3> InteriorChainedNodes;
2459   for (unsigned i = 0, e = ChainNodesMatched.size(); i != e; ++i) {
2460     if (WalkChainUsers(ChainNodesMatched[i], ChainNodesMatched,
2461                        TokenFactorResult,
2462                        InteriorChainedNodes) == CR_InducesCycle)
2463       return SDValue(); // Would induce a cycle.
2464   }
2465
2466   // Okay, we have walked all the matched nodes and collected TokenFactor nodes
2467   // that we are interested in.  Form our input TokenFactor node.
2468   SmallVector<SDValue, 3> InputChains;
2469   for (unsigned i = 0, e = ChainNodesMatched.size(); i != e; ++i) {
2470     // Add the input chain of this node to the InputChains list (which will be
2471     // the operands of the generated TokenFactor) if it's not an interior node.
2472     SDNode *N = ChainNodesMatched[i];
2473     if (N->getOpcode() != ISD::TokenFactor) {
2474       if (std::count(InteriorChainedNodes.begin(),InteriorChainedNodes.end(),N))
2475         continue;
2476
2477       // Otherwise, add the input chain.
2478       SDValue InChain = ChainNodesMatched[i]->getOperand(0);
2479       assert(InChain.getValueType() == MVT::Other && "Not a chain");
2480       InputChains.push_back(InChain);
2481       continue;
2482     }
2483
2484     // If we have a token factor, we want to add all inputs of the token factor
2485     // that are not part of the pattern we're matching.
2486     for (const SDValue &Op : N->op_values()) {
2487       if (!std::count(ChainNodesMatched.begin(), ChainNodesMatched.end(),
2488                       Op.getNode()))
2489         InputChains.push_back(Op);
2490     }
2491   }
2492
2493   if (InputChains.size() == 1)
2494     return InputChains[0];
2495   return CurDAG->getNode(ISD::TokenFactor, SDLoc(ChainNodesMatched[0]),
2496                          MVT::Other, InputChains);
2497 }
2498
2499 /// MorphNode - Handle morphing a node in place for the selector.
2500 SDNode *SelectionDAGISel::
2501 MorphNode(SDNode *Node, unsigned TargetOpc, SDVTList VTList,
2502           ArrayRef<SDValue> Ops, unsigned EmitNodeInfo) {
2503   // It is possible we're using MorphNodeTo to replace a node with no
2504   // normal results with one that has a normal result (or we could be
2505   // adding a chain) and the input could have glue and chains as well.
2506   // In this case we need to shift the operands down.
2507   // FIXME: This is a horrible hack and broken in obscure cases, no worse
2508   // than the old isel though.
2509   int OldGlueResultNo = -1, OldChainResultNo = -1;
2510
2511   unsigned NTMNumResults = Node->getNumValues();
2512   if (Node->getValueType(NTMNumResults-1) == MVT::Glue) {
2513     OldGlueResultNo = NTMNumResults-1;
2514     if (NTMNumResults != 1 &&
2515         Node->getValueType(NTMNumResults-2) == MVT::Other)
2516       OldChainResultNo = NTMNumResults-2;
2517   } else if (Node->getValueType(NTMNumResults-1) == MVT::Other)
2518     OldChainResultNo = NTMNumResults-1;
2519
2520   // Call the underlying SelectionDAG routine to do the transmogrification. Note
2521   // that this deletes operands of the old node that become dead.
2522   SDNode *Res = CurDAG->MorphNodeTo(Node, ~TargetOpc, VTList, Ops);
2523
2524   // MorphNodeTo can operate in two ways: if an existing node with the
2525   // specified operands exists, it can just return it.  Otherwise, it
2526   // updates the node in place to have the requested operands.
2527   if (Res == Node) {
2528     // If we updated the node in place, reset the node ID.  To the isel,
2529     // this should be just like a newly allocated machine node.
2530     Res->setNodeId(-1);
2531   }
2532
2533   unsigned ResNumResults = Res->getNumValues();
2534   // Move the glue if needed.
2535   if ((EmitNodeInfo & OPFL_GlueOutput) && OldGlueResultNo != -1 &&
2536       (unsigned)OldGlueResultNo != ResNumResults-1)
2537     CurDAG->ReplaceAllUsesOfValueWith(SDValue(Node, OldGlueResultNo),
2538                                       SDValue(Res, ResNumResults-1));
2539
2540   if ((EmitNodeInfo & OPFL_GlueOutput) != 0)
2541     --ResNumResults;
2542
2543   // Move the chain reference if needed.
2544   if ((EmitNodeInfo & OPFL_Chain) && OldChainResultNo != -1 &&
2545       (unsigned)OldChainResultNo != ResNumResults-1)
2546     CurDAG->ReplaceAllUsesOfValueWith(SDValue(Node, OldChainResultNo),
2547                                       SDValue(Res, ResNumResults-1));
2548
2549   // Otherwise, no replacement happened because the node already exists. Replace
2550   // Uses of the old node with the new one.
2551   if (Res != Node) {
2552     CurDAG->ReplaceAllUsesWith(Node, Res);
2553     CurDAG->RemoveDeadNode(Node);
2554   }
2555
2556   return Res;
2557 }
2558
2559 /// CheckSame - Implements OP_CheckSame.
2560 LLVM_ATTRIBUTE_ALWAYS_INLINE static inline bool
2561 CheckSame(const unsigned char *MatcherTable, unsigned &MatcherIndex,
2562           SDValue N,
2563           const SmallVectorImpl<std::pair<SDValue, SDNode*>> &RecordedNodes) {
2564   // Accept if it is exactly the same as a previously recorded node.
2565   unsigned RecNo = MatcherTable[MatcherIndex++];
2566   assert(RecNo < RecordedNodes.size() && "Invalid CheckSame");
2567   return N == RecordedNodes[RecNo].first;
2568 }
2569
2570 /// CheckChildSame - Implements OP_CheckChildXSame.
2571 LLVM_ATTRIBUTE_ALWAYS_INLINE static inline bool
2572 CheckChildSame(const unsigned char *MatcherTable, unsigned &MatcherIndex,
2573               SDValue N,
2574               const SmallVectorImpl<std::pair<SDValue, SDNode*>> &RecordedNodes,
2575               unsigned ChildNo) {
2576   if (ChildNo >= N.getNumOperands())
2577     return false;  // Match fails if out of range child #.
2578   return ::CheckSame(MatcherTable, MatcherIndex, N.getOperand(ChildNo),
2579                      RecordedNodes);
2580 }
2581
2582 /// CheckPatternPredicate - Implements OP_CheckPatternPredicate.
2583 LLVM_ATTRIBUTE_ALWAYS_INLINE static inline bool
2584 CheckPatternPredicate(const unsigned char *MatcherTable, unsigned &MatcherIndex,
2585                       const SelectionDAGISel &SDISel) {
2586   return SDISel.CheckPatternPredicate(MatcherTable[MatcherIndex++]);
2587 }
2588
2589 /// CheckNodePredicate - Implements OP_CheckNodePredicate.
2590 LLVM_ATTRIBUTE_ALWAYS_INLINE static inline bool
2591 CheckNodePredicate(const unsigned char *MatcherTable, unsigned &MatcherIndex,
2592                    const SelectionDAGISel &SDISel, SDNode *N) {
2593   return SDISel.CheckNodePredicate(N, MatcherTable[MatcherIndex++]);
2594 }
2595
2596 LLVM_ATTRIBUTE_ALWAYS_INLINE static inline bool
2597 CheckOpcode(const unsigned char *MatcherTable, unsigned &MatcherIndex,
2598             SDNode *N) {
2599   uint16_t Opc = MatcherTable[MatcherIndex++];
2600   Opc |= (unsigned short)MatcherTable[MatcherIndex++] << 8;
2601   return N->getOpcode() == Opc;
2602 }
2603
2604 LLVM_ATTRIBUTE_ALWAYS_INLINE static inline bool
2605 CheckType(const unsigned char *MatcherTable, unsigned &MatcherIndex, SDValue N,
2606           const TargetLowering *TLI, const DataLayout &DL) {
2607   MVT::SimpleValueType VT = (MVT::SimpleValueType)MatcherTable[MatcherIndex++];
2608   if (N.getValueType() == VT) return true;
2609
2610   // Handle the case when VT is iPTR.
2611   return VT == MVT::iPTR && N.getValueType() == TLI->getPointerTy(DL);
2612 }
2613
2614 LLVM_ATTRIBUTE_ALWAYS_INLINE static inline bool
2615 CheckChildType(const unsigned char *MatcherTable, unsigned &MatcherIndex,
2616                SDValue N, const TargetLowering *TLI, const DataLayout &DL,
2617                unsigned ChildNo) {
2618   if (ChildNo >= N.getNumOperands())
2619     return false;  // Match fails if out of range child #.
2620   return ::CheckType(MatcherTable, MatcherIndex, N.getOperand(ChildNo), TLI,
2621                      DL);
2622 }
2623
2624 LLVM_ATTRIBUTE_ALWAYS_INLINE static inline bool
2625 CheckCondCode(const unsigned char *MatcherTable, unsigned &MatcherIndex,
2626               SDValue N) {
2627   return cast<CondCodeSDNode>(N)->get() ==
2628       (ISD::CondCode)MatcherTable[MatcherIndex++];
2629 }
2630
2631 LLVM_ATTRIBUTE_ALWAYS_INLINE static inline bool
2632 CheckValueType(const unsigned char *MatcherTable, unsigned &MatcherIndex,
2633                SDValue N, const TargetLowering *TLI, const DataLayout &DL) {
2634   MVT::SimpleValueType VT = (MVT::SimpleValueType)MatcherTable[MatcherIndex++];
2635   if (cast<VTSDNode>(N)->getVT() == VT)
2636     return true;
2637
2638   // Handle the case when VT is iPTR.
2639   return VT == MVT::iPTR && cast<VTSDNode>(N)->getVT() == TLI->getPointerTy(DL);
2640 }
2641
2642 LLVM_ATTRIBUTE_ALWAYS_INLINE static inline bool
2643 CheckInteger(const unsigned char *MatcherTable, unsigned &MatcherIndex,
2644              SDValue N) {
2645   int64_t Val = MatcherTable[MatcherIndex++];
2646   if (Val & 128)
2647     Val = GetVBR(Val, MatcherTable, MatcherIndex);
2648
2649   ConstantSDNode *C = dyn_cast<ConstantSDNode>(N);
2650   return C && C->getSExtValue() == Val;
2651 }
2652
2653 LLVM_ATTRIBUTE_ALWAYS_INLINE static inline bool
2654 CheckChildInteger(const unsigned char *MatcherTable, unsigned &MatcherIndex,
2655                   SDValue N, unsigned ChildNo) {
2656   if (ChildNo >= N.getNumOperands())
2657     return false;  // Match fails if out of range child #.
2658   return ::CheckInteger(MatcherTable, MatcherIndex, N.getOperand(ChildNo));
2659 }
2660
2661 LLVM_ATTRIBUTE_ALWAYS_INLINE static inline bool
2662 CheckAndImm(const unsigned char *MatcherTable, unsigned &MatcherIndex,
2663             SDValue N, const SelectionDAGISel &SDISel) {
2664   int64_t Val = MatcherTable[MatcherIndex++];
2665   if (Val & 128)
2666     Val = GetVBR(Val, MatcherTable, MatcherIndex);
2667
2668   if (N->getOpcode() != ISD::AND) return false;
2669
2670   ConstantSDNode *C = dyn_cast<ConstantSDNode>(N->getOperand(1));
2671   return C && SDISel.CheckAndMask(N.getOperand(0), C, Val);
2672 }
2673
2674 LLVM_ATTRIBUTE_ALWAYS_INLINE static inline bool
2675 CheckOrImm(const unsigned char *MatcherTable, unsigned &MatcherIndex,
2676            SDValue N, const SelectionDAGISel &SDISel) {
2677   int64_t Val = MatcherTable[MatcherIndex++];
2678   if (Val & 128)
2679     Val = GetVBR(Val, MatcherTable, MatcherIndex);
2680
2681   if (N->getOpcode() != ISD::OR) return false;
2682
2683   ConstantSDNode *C = dyn_cast<ConstantSDNode>(N->getOperand(1));
2684   return C && SDISel.CheckOrMask(N.getOperand(0), C, Val);
2685 }
2686
2687 /// IsPredicateKnownToFail - If we know how and can do so without pushing a
2688 /// scope, evaluate the current node.  If the current predicate is known to
2689 /// fail, set Result=true and return anything.  If the current predicate is
2690 /// known to pass, set Result=false and return the MatcherIndex to continue
2691 /// with.  If the current predicate is unknown, set Result=false and return the
2692 /// MatcherIndex to continue with.
2693 static unsigned IsPredicateKnownToFail(const unsigned char *Table,
2694                                        unsigned Index, SDValue N,
2695                                        bool &Result,
2696                                        const SelectionDAGISel &SDISel,
2697                   SmallVectorImpl<std::pair<SDValue, SDNode*>> &RecordedNodes) {
2698   switch (Table[Index++]) {
2699   default:
2700     Result = false;
2701     return Index-1;  // Could not evaluate this predicate.
2702   case SelectionDAGISel::OPC_CheckSame:
2703     Result = !::CheckSame(Table, Index, N, RecordedNodes);
2704     return Index;
2705   case SelectionDAGISel::OPC_CheckChild0Same:
2706   case SelectionDAGISel::OPC_CheckChild1Same:
2707   case SelectionDAGISel::OPC_CheckChild2Same:
2708   case SelectionDAGISel::OPC_CheckChild3Same:
2709     Result = !::CheckChildSame(Table, Index, N, RecordedNodes,
2710                         Table[Index-1] - SelectionDAGISel::OPC_CheckChild0Same);
2711     return Index;
2712   case SelectionDAGISel::OPC_CheckPatternPredicate:
2713     Result = !::CheckPatternPredicate(Table, Index, SDISel);
2714     return Index;
2715   case SelectionDAGISel::OPC_CheckPredicate:
2716     Result = !::CheckNodePredicate(Table, Index, SDISel, N.getNode());
2717     return Index;
2718   case SelectionDAGISel::OPC_CheckOpcode:
2719     Result = !::CheckOpcode(Table, Index, N.getNode());
2720     return Index;
2721   case SelectionDAGISel::OPC_CheckType:
2722     Result = !::CheckType(Table, Index, N, SDISel.TLI,
2723                           SDISel.CurDAG->getDataLayout());
2724     return Index;
2725   case SelectionDAGISel::OPC_CheckChild0Type:
2726   case SelectionDAGISel::OPC_CheckChild1Type:
2727   case SelectionDAGISel::OPC_CheckChild2Type:
2728   case SelectionDAGISel::OPC_CheckChild3Type:
2729   case SelectionDAGISel::OPC_CheckChild4Type:
2730   case SelectionDAGISel::OPC_CheckChild5Type:
2731   case SelectionDAGISel::OPC_CheckChild6Type:
2732   case SelectionDAGISel::OPC_CheckChild7Type:
2733     Result = !::CheckChildType(
2734                  Table, Index, N, SDISel.TLI, SDISel.CurDAG->getDataLayout(),
2735                  Table[Index - 1] - SelectionDAGISel::OPC_CheckChild0Type);
2736     return Index;
2737   case SelectionDAGISel::OPC_CheckCondCode:
2738     Result = !::CheckCondCode(Table, Index, N);
2739     return Index;
2740   case SelectionDAGISel::OPC_CheckValueType:
2741     Result = !::CheckValueType(Table, Index, N, SDISel.TLI,
2742                                SDISel.CurDAG->getDataLayout());
2743     return Index;
2744   case SelectionDAGISel::OPC_CheckInteger:
2745     Result = !::CheckInteger(Table, Index, N);
2746     return Index;
2747   case SelectionDAGISel::OPC_CheckChild0Integer:
2748   case SelectionDAGISel::OPC_CheckChild1Integer:
2749   case SelectionDAGISel::OPC_CheckChild2Integer:
2750   case SelectionDAGISel::OPC_CheckChild3Integer:
2751   case SelectionDAGISel::OPC_CheckChild4Integer:
2752     Result = !::CheckChildInteger(Table, Index, N,
2753                      Table[Index-1] - SelectionDAGISel::OPC_CheckChild0Integer);
2754     return Index;
2755   case SelectionDAGISel::OPC_CheckAndImm:
2756     Result = !::CheckAndImm(Table, Index, N, SDISel);
2757     return Index;
2758   case SelectionDAGISel::OPC_CheckOrImm:
2759     Result = !::CheckOrImm(Table, Index, N, SDISel);
2760     return Index;
2761   }
2762 }
2763
2764 namespace {
2765
2766 struct MatchScope {
2767   /// FailIndex - If this match fails, this is the index to continue with.
2768   unsigned FailIndex;
2769
2770   /// NodeStack - The node stack when the scope was formed.
2771   SmallVector<SDValue, 4> NodeStack;
2772
2773   /// NumRecordedNodes - The number of recorded nodes when the scope was formed.
2774   unsigned NumRecordedNodes;
2775
2776   /// NumMatchedMemRefs - The number of matched memref entries.
2777   unsigned NumMatchedMemRefs;
2778
2779   /// InputChain/InputGlue - The current chain/glue
2780   SDValue InputChain, InputGlue;
2781
2782   /// HasChainNodesMatched - True if the ChainNodesMatched list is non-empty.
2783   bool HasChainNodesMatched;
2784 };
2785
2786 /// \\brief A DAG update listener to keep the matching state
2787 /// (i.e. RecordedNodes and MatchScope) uptodate if the target is allowed to
2788 /// change the DAG while matching.  X86 addressing mode matcher is an example
2789 /// for this.
2790 class MatchStateUpdater : public SelectionDAG::DAGUpdateListener
2791 {
2792   SDNode **NodeToMatch;
2793   SmallVectorImpl<std::pair<SDValue, SDNode *>> &RecordedNodes;
2794   SmallVectorImpl<MatchScope> &MatchScopes;
2795
2796 public:
2797   MatchStateUpdater(SelectionDAG &DAG, SDNode **NodeToMatch,
2798                     SmallVectorImpl<std::pair<SDValue, SDNode *>> &RN,
2799                     SmallVectorImpl<MatchScope> &MS)
2800       : SelectionDAG::DAGUpdateListener(DAG), NodeToMatch(NodeToMatch),
2801         RecordedNodes(RN), MatchScopes(MS) {}
2802
2803   void NodeDeleted(SDNode *N, SDNode *E) override {
2804     // Some early-returns here to avoid the search if we deleted the node or
2805     // if the update comes from MorphNodeTo (MorphNodeTo is the last thing we
2806     // do, so it's unnecessary to update matching state at that point).
2807     // Neither of these can occur currently because we only install this
2808     // update listener during matching a complex patterns.
2809     if (!E || E->isMachineOpcode())
2810       return;
2811     // Check if NodeToMatch was updated.
2812     if (N == *NodeToMatch)
2813       *NodeToMatch = E;
2814     // Performing linear search here does not matter because we almost never
2815     // run this code.  You'd have to have a CSE during complex pattern
2816     // matching.
2817     for (auto &I : RecordedNodes)
2818       if (I.first.getNode() == N)
2819         I.first.setNode(E);
2820
2821     for (auto &I : MatchScopes)
2822       for (auto &J : I.NodeStack)
2823         if (J.getNode() == N)
2824           J.setNode(E);
2825   }
2826 };
2827
2828 } // end anonymous namespace
2829
2830 void SelectionDAGISel::SelectCodeCommon(SDNode *NodeToMatch,
2831                                         const unsigned char *MatcherTable,
2832                                         unsigned TableSize) {
2833   // FIXME: Should these even be selected?  Handle these cases in the caller?
2834   switch (NodeToMatch->getOpcode()) {
2835   default:
2836     break;
2837   case ISD::EntryToken:       // These nodes remain the same.
2838   case ISD::BasicBlock:
2839   case ISD::Register:
2840   case ISD::RegisterMask:
2841   case ISD::HANDLENODE:
2842   case ISD::MDNODE_SDNODE:
2843   case ISD::TargetConstant:
2844   case ISD::TargetConstantFP:
2845   case ISD::TargetConstantPool:
2846   case ISD::TargetFrameIndex:
2847   case ISD::TargetExternalSymbol:
2848   case ISD::MCSymbol:
2849   case ISD::TargetBlockAddress:
2850   case ISD::TargetJumpTable:
2851   case ISD::TargetGlobalTLSAddress:
2852   case ISD::TargetGlobalAddress:
2853   case ISD::TokenFactor:
2854   case ISD::CopyFromReg:
2855   case ISD::CopyToReg:
2856   case ISD::EH_LABEL:
2857   case ISD::LIFETIME_START:
2858   case ISD::LIFETIME_END:
2859     NodeToMatch->setNodeId(-1); // Mark selected.
2860     return;
2861   case ISD::AssertSext:
2862   case ISD::AssertZext:
2863     CurDAG->ReplaceAllUsesOfValueWith(SDValue(NodeToMatch, 0),
2864                                       NodeToMatch->getOperand(0));
2865     CurDAG->RemoveDeadNode(NodeToMatch);
2866     return;
2867   case ISD::INLINEASM:
2868     Select_INLINEASM(NodeToMatch);
2869     return;
2870   case ISD::READ_REGISTER:
2871     Select_READ_REGISTER(NodeToMatch);
2872     return;
2873   case ISD::WRITE_REGISTER:
2874     Select_WRITE_REGISTER(NodeToMatch);
2875     return;
2876   case ISD::UNDEF:
2877     Select_UNDEF(NodeToMatch);
2878     return;
2879   }
2880
2881   assert(!NodeToMatch->isMachineOpcode() && "Node already selected!");
2882
2883   // Set up the node stack with NodeToMatch as the only node on the stack.
2884   SmallVector<SDValue, 8> NodeStack;
2885   SDValue N = SDValue(NodeToMatch, 0);
2886   NodeStack.push_back(N);
2887
2888   // MatchScopes - Scopes used when matching, if a match failure happens, this
2889   // indicates where to continue checking.
2890   SmallVector<MatchScope, 8> MatchScopes;
2891
2892   // RecordedNodes - This is the set of nodes that have been recorded by the
2893   // state machine.  The second value is the parent of the node, or null if the
2894   // root is recorded.
2895   SmallVector<std::pair<SDValue, SDNode*>, 8> RecordedNodes;
2896
2897   // MatchedMemRefs - This is the set of MemRef's we've seen in the input
2898   // pattern.
2899   SmallVector<MachineMemOperand*, 2> MatchedMemRefs;
2900
2901   // These are the current input chain and glue for use when generating nodes.
2902   // Various Emit operations change these.  For example, emitting a copytoreg
2903   // uses and updates these.
2904   SDValue InputChain, InputGlue;
2905
2906   // ChainNodesMatched - If a pattern matches nodes that have input/output
2907   // chains, the OPC_EmitMergeInputChains operation is emitted which indicates
2908   // which ones they are.  The result is captured into this list so that we can
2909   // update the chain results when the pattern is complete.
2910   SmallVector<SDNode*, 3> ChainNodesMatched;
2911
2912   DEBUG(dbgs() << "ISEL: Starting pattern match on root node: ";
2913         NodeToMatch->dump(CurDAG);
2914         dbgs() << '\n');
2915
2916   // Determine where to start the interpreter.  Normally we start at opcode #0,
2917   // but if the state machine starts with an OPC_SwitchOpcode, then we
2918   // accelerate the first lookup (which is guaranteed to be hot) with the
2919   // OpcodeOffset table.
2920   unsigned MatcherIndex = 0;
2921
2922   if (!OpcodeOffset.empty()) {
2923     // Already computed the OpcodeOffset table, just index into it.
2924     if (N.getOpcode() < OpcodeOffset.size())
2925       MatcherIndex = OpcodeOffset[N.getOpcode()];
2926     DEBUG(dbgs() << "  Initial Opcode index to " << MatcherIndex << "\n");
2927
2928   } else if (MatcherTable[0] == OPC_SwitchOpcode) {
2929     // Otherwise, the table isn't computed, but the state machine does start
2930     // with an OPC_SwitchOpcode instruction.  Populate the table now, since this
2931     // is the first time we're selecting an instruction.
2932     unsigned Idx = 1;
2933     while (true) {
2934       // Get the size of this case.
2935       unsigned CaseSize = MatcherTable[Idx++];
2936       if (CaseSize & 128)
2937         CaseSize = GetVBR(CaseSize, MatcherTable, Idx);
2938       if (CaseSize == 0) break;
2939
2940       // Get the opcode, add the index to the table.
2941       uint16_t Opc = MatcherTable[Idx++];
2942       Opc |= (unsigned short)MatcherTable[Idx++] << 8;
2943       if (Opc >= OpcodeOffset.size())
2944         OpcodeOffset.resize((Opc+1)*2);
2945       OpcodeOffset[Opc] = Idx;
2946       Idx += CaseSize;
2947     }
2948
2949     // Okay, do the lookup for the first opcode.
2950     if (N.getOpcode() < OpcodeOffset.size())
2951       MatcherIndex = OpcodeOffset[N.getOpcode()];
2952   }
2953
2954   while (true) {
2955     assert(MatcherIndex < TableSize && "Invalid index");
2956 #ifndef NDEBUG
2957     unsigned CurrentOpcodeIndex = MatcherIndex;
2958 #endif
2959     BuiltinOpcodes Opcode = (BuiltinOpcodes)MatcherTable[MatcherIndex++];
2960     switch (Opcode) {
2961     case OPC_Scope: {
2962       // Okay, the semantics of this operation are that we should push a scope
2963       // then evaluate the first child.  However, pushing a scope only to have
2964       // the first check fail (which then pops it) is inefficient.  If we can
2965       // determine immediately that the first check (or first several) will
2966       // immediately fail, don't even bother pushing a scope for them.
2967       unsigned FailIndex;
2968
2969       while (true) {
2970         unsigned NumToSkip = MatcherTable[MatcherIndex++];
2971         if (NumToSkip & 128)
2972           NumToSkip = GetVBR(NumToSkip, MatcherTable, MatcherIndex);
2973         // Found the end of the scope with no match.
2974         if (NumToSkip == 0) {
2975           FailIndex = 0;
2976           break;
2977         }
2978
2979         FailIndex = MatcherIndex+NumToSkip;
2980
2981         unsigned MatcherIndexOfPredicate = MatcherIndex;
2982         (void)MatcherIndexOfPredicate; // silence warning.
2983
2984         // If we can't evaluate this predicate without pushing a scope (e.g. if
2985         // it is a 'MoveParent') or if the predicate succeeds on this node, we
2986         // push the scope and evaluate the full predicate chain.
2987         bool Result;
2988         MatcherIndex = IsPredicateKnownToFail(MatcherTable, MatcherIndex, N,
2989                                               Result, *this, RecordedNodes);
2990         if (!Result)
2991           break;
2992
2993         DEBUG(dbgs() << "  Skipped scope entry (due to false predicate) at "
2994                      << "index " << MatcherIndexOfPredicate
2995                      << ", continuing at " << FailIndex << "\n");
2996         ++NumDAGIselRetries;
2997
2998         // Otherwise, we know that this case of the Scope is guaranteed to fail,
2999         // move to the next case.
3000         MatcherIndex = FailIndex;
3001       }
3002
3003       // If the whole scope failed to match, bail.
3004       if (FailIndex == 0) break;
3005
3006       // Push a MatchScope which indicates where to go if the first child fails
3007       // to match.
3008       MatchScope NewEntry;
3009       NewEntry.FailIndex = FailIndex;
3010       NewEntry.NodeStack.append(NodeStack.begin(), NodeStack.end());
3011       NewEntry.NumRecordedNodes = RecordedNodes.size();
3012       NewEntry.NumMatchedMemRefs = MatchedMemRefs.size();
3013       NewEntry.InputChain = InputChain;
3014       NewEntry.InputGlue = InputGlue;
3015       NewEntry.HasChainNodesMatched = !ChainNodesMatched.empty();
3016       MatchScopes.push_back(NewEntry);
3017       continue;
3018     }
3019     case OPC_RecordNode: {
3020       // Remember this node, it may end up being an operand in the pattern.
3021       SDNode *Parent = nullptr;
3022       if (NodeStack.size() > 1)
3023         Parent = NodeStack[NodeStack.size()-2].getNode();
3024       RecordedNodes.push_back(std::make_pair(N, Parent));
3025       continue;
3026     }
3027
3028     case OPC_RecordChild0: case OPC_RecordChild1:
3029     case OPC_RecordChild2: case OPC_RecordChild3:
3030     case OPC_RecordChild4: case OPC_RecordChild5:
3031     case OPC_RecordChild6: case OPC_RecordChild7: {
3032       unsigned ChildNo = Opcode-OPC_RecordChild0;
3033       if (ChildNo >= N.getNumOperands())
3034         break;  // Match fails if out of range child #.
3035
3036       RecordedNodes.push_back(std::make_pair(N->getOperand(ChildNo),
3037                                              N.getNode()));
3038       continue;
3039     }
3040     case OPC_RecordMemRef:
3041       MatchedMemRefs.push_back(cast<MemSDNode>(N)->getMemOperand());
3042       continue;
3043
3044     case OPC_CaptureGlueInput:
3045       // If the current node has an input glue, capture it in InputGlue.
3046       if (N->getNumOperands() != 0 &&
3047           N->getOperand(N->getNumOperands()-1).getValueType() == MVT::Glue)
3048         InputGlue = N->getOperand(N->getNumOperands()-1);
3049       continue;
3050
3051     case OPC_MoveChild: {
3052       unsigned ChildNo = MatcherTable[MatcherIndex++];
3053       if (ChildNo >= N.getNumOperands())
3054         break;  // Match fails if out of range child #.
3055       N = N.getOperand(ChildNo);
3056       NodeStack.push_back(N);
3057       continue;
3058     }
3059
3060     case OPC_MoveChild0: case OPC_MoveChild1:
3061     case OPC_MoveChild2: case OPC_MoveChild3:
3062     case OPC_MoveChild4: case OPC_MoveChild5:
3063     case OPC_MoveChild6: case OPC_MoveChild7: {
3064       unsigned ChildNo = Opcode-OPC_MoveChild0;
3065       if (ChildNo >= N.getNumOperands())
3066         break;  // Match fails if out of range child #.
3067       N = N.getOperand(ChildNo);
3068       NodeStack.push_back(N);
3069       continue;
3070     }
3071
3072     case OPC_MoveParent:
3073       // Pop the current node off the NodeStack.
3074       NodeStack.pop_back();
3075       assert(!NodeStack.empty() && "Node stack imbalance!");
3076       N = NodeStack.back();
3077       continue;
3078
3079     case OPC_CheckSame:
3080       if (!::CheckSame(MatcherTable, MatcherIndex, N, RecordedNodes)) break;
3081       continue;
3082
3083     case OPC_CheckChild0Same: case OPC_CheckChild1Same:
3084     case OPC_CheckChild2Same: case OPC_CheckChild3Same:
3085       if (!::CheckChildSame(MatcherTable, MatcherIndex, N, RecordedNodes,
3086                             Opcode-OPC_CheckChild0Same))
3087         break;
3088       continue;
3089
3090     case OPC_CheckPatternPredicate:
3091       if (!::CheckPatternPredicate(MatcherTable, MatcherIndex, *this)) break;
3092       continue;
3093     case OPC_CheckPredicate:
3094       if (!::CheckNodePredicate(MatcherTable, MatcherIndex, *this,
3095                                 N.getNode()))
3096         break;
3097       continue;
3098     case OPC_CheckComplexPat: {
3099       unsigned CPNum = MatcherTable[MatcherIndex++];
3100       unsigned RecNo = MatcherTable[MatcherIndex++];
3101       assert(RecNo < RecordedNodes.size() && "Invalid CheckComplexPat");
3102
3103       // If target can modify DAG during matching, keep the matching state
3104       // consistent.
3105       std::unique_ptr<MatchStateUpdater> MSU;
3106       if (ComplexPatternFuncMutatesDAG())
3107         MSU.reset(new MatchStateUpdater(*CurDAG, &NodeToMatch, RecordedNodes,
3108                                         MatchScopes));
3109
3110       if (!CheckComplexPattern(NodeToMatch, RecordedNodes[RecNo].second,
3111                                RecordedNodes[RecNo].first, CPNum,
3112                                RecordedNodes))
3113         break;
3114       continue;
3115     }
3116     case OPC_CheckOpcode:
3117       if (!::CheckOpcode(MatcherTable, MatcherIndex, N.getNode())) break;
3118       continue;
3119
3120     case OPC_CheckType:
3121       if (!::CheckType(MatcherTable, MatcherIndex, N, TLI,
3122                        CurDAG->getDataLayout()))
3123         break;
3124       continue;
3125
3126     case OPC_SwitchOpcode: {
3127       unsigned CurNodeOpcode = N.getOpcode();
3128       unsigned SwitchStart = MatcherIndex-1; (void)SwitchStart;
3129       unsigned CaseSize;
3130       while (true) {
3131         // Get the size of this case.
3132         CaseSize = MatcherTable[MatcherIndex++];
3133         if (CaseSize & 128)
3134           CaseSize = GetVBR(CaseSize, MatcherTable, MatcherIndex);
3135         if (CaseSize == 0) break;
3136
3137         uint16_t Opc = MatcherTable[MatcherIndex++];
3138         Opc |= (unsigned short)MatcherTable[MatcherIndex++] << 8;
3139
3140         // If the opcode matches, then we will execute this case.
3141         if (CurNodeOpcode == Opc)
3142           break;
3143
3144         // Otherwise, skip over this case.
3145         MatcherIndex += CaseSize;
3146       }
3147
3148       // If no cases matched, bail out.
3149       if (CaseSize == 0) break;
3150
3151       // Otherwise, execute the case we found.
3152       DEBUG(dbgs() << "  OpcodeSwitch from " << SwitchStart
3153                    << " to " << MatcherIndex << "\n");
3154       continue;
3155     }
3156
3157     case OPC_SwitchType: {
3158       MVT CurNodeVT = N.getSimpleValueType();
3159       unsigned SwitchStart = MatcherIndex-1; (void)SwitchStart;
3160       unsigned CaseSize;
3161       while (true) {
3162         // Get the size of this case.
3163         CaseSize = MatcherTable[MatcherIndex++];
3164         if (CaseSize & 128)
3165           CaseSize = GetVBR(CaseSize, MatcherTable, MatcherIndex);
3166         if (CaseSize == 0) break;
3167
3168         MVT CaseVT = (MVT::SimpleValueType)MatcherTable[MatcherIndex++];
3169         if (CaseVT == MVT::iPTR)
3170           CaseVT = TLI->getPointerTy(CurDAG->getDataLayout());
3171
3172         // If the VT matches, then we will execute this case.
3173         if (CurNodeVT == CaseVT)
3174           break;
3175
3176         // Otherwise, skip over this case.
3177         MatcherIndex += CaseSize;
3178       }
3179
3180       // If no cases matched, bail out.
3181       if (CaseSize == 0) break;
3182
3183       // Otherwise, execute the case we found.
3184       DEBUG(dbgs() << "  TypeSwitch[" << EVT(CurNodeVT).getEVTString()
3185                    << "] from " << SwitchStart << " to " << MatcherIndex<<'\n');
3186       continue;
3187     }
3188     case OPC_CheckChild0Type: case OPC_CheckChild1Type:
3189     case OPC_CheckChild2Type: case OPC_CheckChild3Type:
3190     case OPC_CheckChild4Type: case OPC_CheckChild5Type:
3191     case OPC_CheckChild6Type: case OPC_CheckChild7Type:
3192       if (!::CheckChildType(MatcherTable, MatcherIndex, N, TLI,
3193                             CurDAG->getDataLayout(),
3194                             Opcode - OPC_CheckChild0Type))
3195         break;
3196       continue;
3197     case OPC_CheckCondCode:
3198       if (!::CheckCondCode(MatcherTable, MatcherIndex, N)) break;
3199       continue;
3200     case OPC_CheckValueType:
3201       if (!::CheckValueType(MatcherTable, MatcherIndex, N, TLI,
3202                             CurDAG->getDataLayout()))
3203         break;
3204       continue;
3205     case OPC_CheckInteger:
3206       if (!::CheckInteger(MatcherTable, MatcherIndex, N)) break;
3207       continue;
3208     case OPC_CheckChild0Integer: case OPC_CheckChild1Integer:
3209     case OPC_CheckChild2Integer: case OPC_CheckChild3Integer:
3210     case OPC_CheckChild4Integer:
3211       if (!::CheckChildInteger(MatcherTable, MatcherIndex, N,
3212                                Opcode-OPC_CheckChild0Integer)) break;
3213       continue;
3214     case OPC_CheckAndImm:
3215       if (!::CheckAndImm(MatcherTable, MatcherIndex, N, *this)) break;
3216       continue;
3217     case OPC_CheckOrImm:
3218       if (!::CheckOrImm(MatcherTable, MatcherIndex, N, *this)) break;
3219       continue;
3220
3221     case OPC_CheckFoldableChainNode: {
3222       assert(NodeStack.size() != 1 && "No parent node");
3223       // Verify that all intermediate nodes between the root and this one have
3224       // a single use.
3225       bool HasMultipleUses = false;
3226       for (unsigned i = 1, e = NodeStack.size()-1; i != e; ++i)
3227         if (!NodeStack[i].getNode()->hasOneUse()) {
3228           HasMultipleUses = true;
3229           break;
3230         }
3231       if (HasMultipleUses) break;
3232
3233       // Check to see that the target thinks this is profitable to fold and that
3234       // we can fold it without inducing cycles in the graph.
3235       if (!IsProfitableToFold(N, NodeStack[NodeStack.size()-2].getNode(),
3236                               NodeToMatch) ||
3237           !IsLegalToFold(N, NodeStack[NodeStack.size()-2].getNode(),
3238                          NodeToMatch, OptLevel,
3239                          true/*We validate our own chains*/))
3240         break;
3241
3242       continue;
3243     }
3244     case OPC_EmitInteger: {
3245       MVT::SimpleValueType VT =
3246         (MVT::SimpleValueType)MatcherTable[MatcherIndex++];
3247       int64_t Val = MatcherTable[MatcherIndex++];
3248       if (Val & 128)
3249         Val = GetVBR(Val, MatcherTable, MatcherIndex);
3250       RecordedNodes.push_back(std::pair<SDValue, SDNode*>(
3251                               CurDAG->getTargetConstant(Val, SDLoc(NodeToMatch),
3252                                                         VT), nullptr));
3253       continue;
3254     }
3255     case OPC_EmitRegister: {
3256       MVT::SimpleValueType VT =
3257         (MVT::SimpleValueType)MatcherTable[MatcherIndex++];
3258       unsigned RegNo = MatcherTable[MatcherIndex++];
3259       RecordedNodes.push_back(std::pair<SDValue, SDNode*>(
3260                               CurDAG->getRegister(RegNo, VT), nullptr));
3261       continue;
3262     }
3263     case OPC_EmitRegister2: {
3264       // For targets w/ more than 256 register names, the register enum
3265       // values are stored in two bytes in the matcher table (just like
3266       // opcodes).
3267       MVT::SimpleValueType VT =
3268         (MVT::SimpleValueType)MatcherTable[MatcherIndex++];
3269       unsigned RegNo = MatcherTable[MatcherIndex++];
3270       RegNo |= MatcherTable[MatcherIndex++] << 8;
3271       RecordedNodes.push_back(std::pair<SDValue, SDNode*>(
3272                               CurDAG->getRegister(RegNo, VT), nullptr));
3273       continue;
3274     }
3275
3276     case OPC_EmitConvertToTarget:  {
3277       // Convert from IMM/FPIMM to target version.
3278       unsigned RecNo = MatcherTable[MatcherIndex++];
3279       assert(RecNo < RecordedNodes.size() && "Invalid EmitConvertToTarget");
3280       SDValue Imm = RecordedNodes[RecNo].first;
3281
3282       if (Imm->getOpcode() == ISD::Constant) {
3283         const ConstantInt *Val=cast<ConstantSDNode>(Imm)->getConstantIntValue();
3284         Imm = CurDAG->getTargetConstant(*Val, SDLoc(NodeToMatch),
3285                                         Imm.getValueType());
3286       } else if (Imm->getOpcode() == ISD::ConstantFP) {
3287         const ConstantFP *Val=cast<ConstantFPSDNode>(Imm)->getConstantFPValue();
3288         Imm = CurDAG->getTargetConstantFP(*Val, SDLoc(NodeToMatch),
3289                                           Imm.getValueType());
3290       }
3291
3292       RecordedNodes.push_back(std::make_pair(Imm, RecordedNodes[RecNo].second));
3293       continue;
3294     }
3295
3296     case OPC_EmitMergeInputChains1_0:    // OPC_EmitMergeInputChains, 1, 0
3297     case OPC_EmitMergeInputChains1_1:    // OPC_EmitMergeInputChains, 1, 1
3298     case OPC_EmitMergeInputChains1_2: {  // OPC_EmitMergeInputChains, 1, 2
3299       // These are space-optimized forms of OPC_EmitMergeInputChains.
3300       assert(!InputChain.getNode() &&
3301              "EmitMergeInputChains should be the first chain producing node");
3302       assert(ChainNodesMatched.empty() &&
3303              "Should only have one EmitMergeInputChains per match");
3304
3305       // Read all of the chained nodes.
3306       unsigned RecNo = Opcode - OPC_EmitMergeInputChains1_0;
3307       assert(RecNo < RecordedNodes.size() && "Invalid EmitMergeInputChains");
3308       ChainNodesMatched.push_back(RecordedNodes[RecNo].first.getNode());
3309
3310       // FIXME: What if other value results of the node have uses not matched
3311       // by this pattern?
3312       if (ChainNodesMatched.back() != NodeToMatch &&
3313           !RecordedNodes[RecNo].first.hasOneUse()) {
3314         ChainNodesMatched.clear();
3315         break;
3316       }
3317
3318       // Merge the input chains if they are not intra-pattern references.
3319       InputChain = HandleMergeInputChains(ChainNodesMatched, CurDAG);
3320
3321       if (!InputChain.getNode())
3322         break;  // Failed to merge.
3323       continue;
3324     }
3325
3326     case OPC_EmitMergeInputChains: {
3327       assert(!InputChain.getNode() &&
3328              "EmitMergeInputChains should be the first chain producing node");
3329       // This node gets a list of nodes we matched in the input that have
3330       // chains.  We want to token factor all of the input chains to these nodes
3331       // together.  However, if any of the input chains is actually one of the
3332       // nodes matched in this pattern, then we have an intra-match reference.
3333       // Ignore these because the newly token factored chain should not refer to
3334       // the old nodes.
3335       unsigned NumChains = MatcherTable[MatcherIndex++];
3336       assert(NumChains != 0 && "Can't TF zero chains");
3337
3338       assert(ChainNodesMatched.empty() &&
3339              "Should only have one EmitMergeInputChains per match");
3340
3341       // Read all of the chained nodes.
3342       for (unsigned i = 0; i != NumChains; ++i) {
3343         unsigned RecNo = MatcherTable[MatcherIndex++];
3344         assert(RecNo < RecordedNodes.size() && "Invalid EmitMergeInputChains");
3345         ChainNodesMatched.push_back(RecordedNodes[RecNo].first.getNode());
3346
3347         // FIXME: What if other value results of the node have uses not matched
3348         // by this pattern?
3349         if (ChainNodesMatched.back() != NodeToMatch &&
3350             !RecordedNodes[RecNo].first.hasOneUse()) {
3351           ChainNodesMatched.clear();
3352           break;
3353         }
3354       }
3355
3356       // If the inner loop broke out, the match fails.
3357       if (ChainNodesMatched.empty())
3358         break;
3359
3360       // Merge the input chains if they are not intra-pattern references.
3361       InputChain = HandleMergeInputChains(ChainNodesMatched, CurDAG);
3362
3363       if (!InputChain.getNode())
3364         break;  // Failed to merge.
3365
3366       continue;
3367     }
3368
3369     case OPC_EmitCopyToReg: {
3370       unsigned RecNo = MatcherTable[MatcherIndex++];
3371       assert(RecNo < RecordedNodes.size() && "Invalid EmitCopyToReg");
3372       unsigned DestPhysReg = MatcherTable[MatcherIndex++];
3373
3374       if (!InputChain.getNode())
3375         InputChain = CurDAG->getEntryNode();
3376
3377       InputChain = CurDAG->getCopyToReg(InputChain, SDLoc(NodeToMatch),
3378                                         DestPhysReg, RecordedNodes[RecNo].first,
3379                                         InputGlue);
3380
3381       InputGlue = InputChain.getValue(1);
3382       continue;
3383     }
3384
3385     case OPC_EmitNodeXForm: {
3386       unsigned XFormNo = MatcherTable[MatcherIndex++];
3387       unsigned RecNo = MatcherTable[MatcherIndex++];
3388       assert(RecNo < RecordedNodes.size() && "Invalid EmitNodeXForm");
3389       SDValue Res = RunSDNodeXForm(RecordedNodes[RecNo].first, XFormNo);
3390       RecordedNodes.push_back(std::pair<SDValue,SDNode*>(Res, nullptr));
3391       continue;
3392     }
3393     case OPC_Coverage: {
3394       // This is emitted right before MorphNode/EmitNode.
3395       // So it should be safe to assume that this node has been selected
3396       unsigned index = MatcherTable[MatcherIndex++];
3397       index |= (MatcherTable[MatcherIndex++] << 8);
3398       dbgs() << "COVERED: " << getPatternForIndex(index) << "\n";
3399       dbgs() << "INCLUDED: " << getIncludePathForIndex(index) << "\n";
3400       continue;
3401     }
3402
3403     case OPC_EmitNode:     case OPC_MorphNodeTo:
3404     case OPC_EmitNode0:    case OPC_EmitNode1:    case OPC_EmitNode2:
3405     case OPC_MorphNodeTo0: case OPC_MorphNodeTo1: case OPC_MorphNodeTo2: {
3406       uint16_t TargetOpc = MatcherTable[MatcherIndex++];
3407       TargetOpc |= (unsigned short)MatcherTable[MatcherIndex++] << 8;
3408       unsigned EmitNodeInfo = MatcherTable[MatcherIndex++];
3409       // Get the result VT list.
3410       unsigned NumVTs;
3411       // If this is one of the compressed forms, get the number of VTs based
3412       // on the Opcode. Otherwise read the next byte from the table.
3413       if (Opcode >= OPC_MorphNodeTo0 && Opcode <= OPC_MorphNodeTo2)
3414         NumVTs = Opcode - OPC_MorphNodeTo0;
3415       else if (Opcode >= OPC_EmitNode0 && Opcode <= OPC_EmitNode2)
3416         NumVTs = Opcode - OPC_EmitNode0;
3417       else
3418         NumVTs = MatcherTable[MatcherIndex++];
3419       SmallVector<EVT, 4> VTs;
3420       for (unsigned i = 0; i != NumVTs; ++i) {
3421         MVT::SimpleValueType VT =
3422           (MVT::SimpleValueType)MatcherTable[MatcherIndex++];
3423         if (VT == MVT::iPTR)
3424           VT = TLI->getPointerTy(CurDAG->getDataLayout()).SimpleTy;
3425         VTs.push_back(VT);
3426       }
3427
3428       if (EmitNodeInfo & OPFL_Chain)
3429         VTs.push_back(MVT::Other);
3430       if (EmitNodeInfo & OPFL_GlueOutput)
3431         VTs.push_back(MVT::Glue);
3432
3433       // This is hot code, so optimize the two most common cases of 1 and 2
3434       // results.
3435       SDVTList VTList;
3436       if (VTs.size() == 1)
3437         VTList = CurDAG->getVTList(VTs[0]);
3438       else if (VTs.size() == 2)
3439         VTList = CurDAG->getVTList(VTs[0], VTs[1]);
3440       else
3441         VTList = CurDAG->getVTList(VTs);
3442
3443       // Get the operand list.
3444       unsigned NumOps = MatcherTable[MatcherIndex++];
3445       SmallVector<SDValue, 8> Ops;
3446       for (unsigned i = 0; i != NumOps; ++i) {
3447         unsigned RecNo = MatcherTable[MatcherIndex++];
3448         if (RecNo & 128)
3449           RecNo = GetVBR(RecNo, MatcherTable, MatcherIndex);
3450
3451         assert(RecNo < RecordedNodes.size() && "Invalid EmitNode");
3452         Ops.push_back(RecordedNodes[RecNo].first);
3453       }
3454
3455       // If there are variadic operands to add, handle them now.
3456       if (EmitNodeInfo & OPFL_VariadicInfo) {
3457         // Determine the start index to copy from.
3458         unsigned FirstOpToCopy = getNumFixedFromVariadicInfo(EmitNodeInfo);
3459         FirstOpToCopy += (EmitNodeInfo & OPFL_Chain) ? 1 : 0;
3460         assert(NodeToMatch->getNumOperands() >= FirstOpToCopy &&
3461                "Invalid variadic node");
3462         // Copy all of the variadic operands, not including a potential glue
3463         // input.
3464         for (unsigned i = FirstOpToCopy, e = NodeToMatch->getNumOperands();
3465              i != e; ++i) {
3466           SDValue V = NodeToMatch->getOperand(i);
3467           if (V.getValueType() == MVT::Glue) break;
3468           Ops.push_back(V);
3469         }
3470       }
3471
3472       // If this has chain/glue inputs, add them.
3473       if (EmitNodeInfo & OPFL_Chain)
3474         Ops.push_back(InputChain);
3475       if ((EmitNodeInfo & OPFL_GlueInput) && InputGlue.getNode() != nullptr)
3476         Ops.push_back(InputGlue);
3477
3478       // Create the node.
3479       SDNode *Res = nullptr;
3480       bool IsMorphNodeTo = Opcode == OPC_MorphNodeTo ||
3481                      (Opcode >= OPC_MorphNodeTo0 && Opcode <= OPC_MorphNodeTo2);
3482       if (!IsMorphNodeTo) {
3483         // If this is a normal EmitNode command, just create the new node and
3484         // add the results to the RecordedNodes list.
3485         Res = CurDAG->getMachineNode(TargetOpc, SDLoc(NodeToMatch),
3486                                      VTList, Ops);
3487
3488         // Add all the non-glue/non-chain results to the RecordedNodes list.
3489         for (unsigned i = 0, e = VTs.size(); i != e; ++i) {
3490           if (VTs[i] == MVT::Other || VTs[i] == MVT::Glue) break;
3491           RecordedNodes.push_back(std::pair<SDValue,SDNode*>(SDValue(Res, i),
3492                                                              nullptr));
3493         }
3494       } else {
3495         assert(NodeToMatch->getOpcode() != ISD::DELETED_NODE &&
3496                "NodeToMatch was removed partway through selection");
3497         SelectionDAG::DAGNodeDeletedListener NDL(*CurDAG, [&](SDNode *N,
3498                                                               SDNode *E) {
3499           auto &Chain = ChainNodesMatched;
3500           assert((!E || !is_contained(Chain, N)) &&
3501                  "Chain node replaced during MorphNode");
3502           Chain.erase(std::remove(Chain.begin(), Chain.end(), N), Chain.end());
3503         });
3504         Res = MorphNode(NodeToMatch, TargetOpc, VTList, Ops, EmitNodeInfo);
3505       }
3506
3507       // If the node had chain/glue results, update our notion of the current
3508       // chain and glue.
3509       if (EmitNodeInfo & OPFL_GlueOutput) {
3510         InputGlue = SDValue(Res, VTs.size()-1);
3511         if (EmitNodeInfo & OPFL_Chain)
3512           InputChain = SDValue(Res, VTs.size()-2);
3513       } else if (EmitNodeInfo & OPFL_Chain)
3514         InputChain = SDValue(Res, VTs.size()-1);
3515
3516       // If the OPFL_MemRefs glue is set on this node, slap all of the
3517       // accumulated memrefs onto it.
3518       //
3519       // FIXME: This is vastly incorrect for patterns with multiple outputs
3520       // instructions that access memory and for ComplexPatterns that match
3521       // loads.
3522       if (EmitNodeInfo & OPFL_MemRefs) {
3523         // Only attach load or store memory operands if the generated
3524         // instruction may load or store.
3525         const MCInstrDesc &MCID = TII->get(TargetOpc);
3526         bool mayLoad = MCID.mayLoad();
3527         bool mayStore = MCID.mayStore();
3528
3529         unsigned NumMemRefs = 0;
3530         for (SmallVectorImpl<MachineMemOperand *>::const_iterator I =
3531                MatchedMemRefs.begin(), E = MatchedMemRefs.end(); I != E; ++I) {
3532           if ((*I)->isLoad()) {
3533             if (mayLoad)
3534               ++NumMemRefs;
3535           } else if ((*I)->isStore()) {
3536             if (mayStore)
3537               ++NumMemRefs;
3538           } else {
3539             ++NumMemRefs;
3540           }
3541         }
3542
3543         MachineSDNode::mmo_iterator MemRefs =
3544           MF->allocateMemRefsArray(NumMemRefs);
3545
3546         MachineSDNode::mmo_iterator MemRefsPos = MemRefs;
3547         for (SmallVectorImpl<MachineMemOperand *>::const_iterator I =
3548                MatchedMemRefs.begin(), E = MatchedMemRefs.end(); I != E; ++I) {
3549           if ((*I)->isLoad()) {
3550             if (mayLoad)
3551               *MemRefsPos++ = *I;
3552           } else if ((*I)->isStore()) {
3553             if (mayStore)
3554               *MemRefsPos++ = *I;
3555           } else {
3556             *MemRefsPos++ = *I;
3557           }
3558         }
3559
3560         cast<MachineSDNode>(Res)
3561           ->setMemRefs(MemRefs, MemRefs + NumMemRefs);
3562       }
3563
3564       DEBUG(dbgs() << "  "
3565                    << (IsMorphNodeTo ? "Morphed" : "Created")
3566                    << " node: "; Res->dump(CurDAG); dbgs() << "\n");
3567
3568       // If this was a MorphNodeTo then we're completely done!
3569       if (IsMorphNodeTo) {
3570         // Update chain uses.
3571         UpdateChains(Res, InputChain, ChainNodesMatched, true);
3572         return;
3573       }
3574       continue;
3575     }
3576
3577     case OPC_CompleteMatch: {
3578       // The match has been completed, and any new nodes (if any) have been
3579       // created.  Patch up references to the matched dag to use the newly
3580       // created nodes.
3581       unsigned NumResults = MatcherTable[MatcherIndex++];
3582
3583       for (unsigned i = 0; i != NumResults; ++i) {
3584         unsigned ResSlot = MatcherTable[MatcherIndex++];
3585         if (ResSlot & 128)
3586           ResSlot = GetVBR(ResSlot, MatcherTable, MatcherIndex);
3587
3588         assert(ResSlot < RecordedNodes.size() && "Invalid CompleteMatch");
3589         SDValue Res = RecordedNodes[ResSlot].first;
3590
3591         assert(i < NodeToMatch->getNumValues() &&
3592                NodeToMatch->getValueType(i) != MVT::Other &&
3593                NodeToMatch->getValueType(i) != MVT::Glue &&
3594                "Invalid number of results to complete!");
3595         assert((NodeToMatch->getValueType(i) == Res.getValueType() ||
3596                 NodeToMatch->getValueType(i) == MVT::iPTR ||
3597                 Res.getValueType() == MVT::iPTR ||
3598                 NodeToMatch->getValueType(i).getSizeInBits() ==
3599                     Res.getValueSizeInBits()) &&
3600                "invalid replacement");
3601         CurDAG->ReplaceAllUsesOfValueWith(SDValue(NodeToMatch, i), Res);
3602       }
3603
3604       // Update chain uses.
3605       UpdateChains(NodeToMatch, InputChain, ChainNodesMatched, false);
3606
3607       // If the root node defines glue, we need to update it to the glue result.
3608       // TODO: This never happens in our tests and I think it can be removed /
3609       // replaced with an assert, but if we do it this the way the change is
3610       // NFC.
3611       if (NodeToMatch->getValueType(NodeToMatch->getNumValues() - 1) ==
3612               MVT::Glue &&
3613           InputGlue.getNode())
3614         CurDAG->ReplaceAllUsesOfValueWith(
3615             SDValue(NodeToMatch, NodeToMatch->getNumValues() - 1), InputGlue);
3616
3617       assert(NodeToMatch->use_empty() &&
3618              "Didn't replace all uses of the node?");
3619       CurDAG->RemoveDeadNode(NodeToMatch);
3620
3621       return;
3622     }
3623     }
3624
3625     // If the code reached this point, then the match failed.  See if there is
3626     // another child to try in the current 'Scope', otherwise pop it until we
3627     // find a case to check.
3628     DEBUG(dbgs() << "  Match failed at index " << CurrentOpcodeIndex << "\n");
3629     ++NumDAGIselRetries;
3630     while (true) {
3631       if (MatchScopes.empty()) {
3632         CannotYetSelect(NodeToMatch);
3633         return;
3634       }
3635
3636       // Restore the interpreter state back to the point where the scope was
3637       // formed.
3638       MatchScope &LastScope = MatchScopes.back();
3639       RecordedNodes.resize(LastScope.NumRecordedNodes);
3640       NodeStack.clear();
3641       NodeStack.append(LastScope.NodeStack.begin(), LastScope.NodeStack.end());
3642       N = NodeStack.back();
3643
3644       if (LastScope.NumMatchedMemRefs != MatchedMemRefs.size())
3645         MatchedMemRefs.resize(LastScope.NumMatchedMemRefs);
3646       MatcherIndex = LastScope.FailIndex;
3647
3648       DEBUG(dbgs() << "  Continuing at " << MatcherIndex << "\n");
3649
3650       InputChain = LastScope.InputChain;
3651       InputGlue = LastScope.InputGlue;
3652       if (!LastScope.HasChainNodesMatched)
3653         ChainNodesMatched.clear();
3654
3655       // Check to see what the offset is at the new MatcherIndex.  If it is zero
3656       // we have reached the end of this scope, otherwise we have another child
3657       // in the current scope to try.
3658       unsigned NumToSkip = MatcherTable[MatcherIndex++];
3659       if (NumToSkip & 128)
3660         NumToSkip = GetVBR(NumToSkip, MatcherTable, MatcherIndex);
3661
3662       // If we have another child in this scope to match, update FailIndex and
3663       // try it.
3664       if (NumToSkip != 0) {
3665         LastScope.FailIndex = MatcherIndex+NumToSkip;
3666         break;
3667       }
3668
3669       // End of this scope, pop it and try the next child in the containing
3670       // scope.
3671       MatchScopes.pop_back();
3672     }
3673   }
3674 }
3675
3676 void SelectionDAGISel::CannotYetSelect(SDNode *N) {
3677   std::string msg;
3678   raw_string_ostream Msg(msg);
3679   Msg << "Cannot select: ";
3680
3681   if (N->getOpcode() != ISD::INTRINSIC_W_CHAIN &&
3682       N->getOpcode() != ISD::INTRINSIC_WO_CHAIN &&
3683       N->getOpcode() != ISD::INTRINSIC_VOID) {
3684     N->printrFull(Msg, CurDAG);
3685     Msg << "\nIn function: " << MF->getName();
3686   } else {
3687     bool HasInputChain = N->getOperand(0).getValueType() == MVT::Other;
3688     unsigned iid =
3689       cast<ConstantSDNode>(N->getOperand(HasInputChain))->getZExtValue();
3690     if (iid < Intrinsic::num_intrinsics)
3691       Msg << "intrinsic %" << Intrinsic::getName((Intrinsic::ID)iid, None);
3692     else if (const TargetIntrinsicInfo *TII = TM.getIntrinsicInfo())
3693       Msg << "target intrinsic %" << TII->getName(iid);
3694     else
3695       Msg << "unknown intrinsic #" << iid;
3696   }
3697   report_fatal_error(Msg.str());
3698 }
3699
3700 char SelectionDAGISel::ID = 0;