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