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

Generated by: LCOV version 1.13