LCOV - code coverage report
Current view: top level - lib/CodeGen/SelectionDAG - SelectionDAGISel.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 1325 1376 96.3 %
Date: 2018-07-13 00:08:38 Functions: 53 61 86.9 %
Legend: Lines: hit not hit

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

Generated by: LCOV version 1.13