LCOV - code coverage report
Current view: top level - lib/CodeGen/SelectionDAG - ScheduleDAGRRList.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 1157 1301 88.9 %
Date: 2017-09-14 15:23:50 Functions: 83 99 83.8 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : //===----- ScheduleDAGRRList.cpp - Reg pressure reduction list scheduler --===//
       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 bottom-up and top-down register pressure reduction list
      11             : // schedulers, using standard algorithms.  The basic approach uses a priority
      12             : // queue of available nodes to schedule.  One at a time, nodes are taken from
      13             : // the priority queue (thus in priority order), checked for legality to
      14             : // schedule, and emitted if legal.
      15             : //
      16             : //===----------------------------------------------------------------------===//
      17             : 
      18             : #include "ScheduleDAGSDNodes.h"
      19             : #include "llvm/ADT/STLExtras.h"
      20             : #include "llvm/ADT/SmallSet.h"
      21             : #include "llvm/ADT/Statistic.h"
      22             : #include "llvm/CodeGen/MachineRegisterInfo.h"
      23             : #include "llvm/CodeGen/ScheduleHazardRecognizer.h"
      24             : #include "llvm/CodeGen/SchedulerRegistry.h"
      25             : #include "llvm/CodeGen/SelectionDAGISel.h"
      26             : #include "llvm/IR/DataLayout.h"
      27             : #include "llvm/IR/InlineAsm.h"
      28             : #include "llvm/Support/Debug.h"
      29             : #include "llvm/Support/ErrorHandling.h"
      30             : #include "llvm/Support/raw_ostream.h"
      31             : #include "llvm/Target/TargetInstrInfo.h"
      32             : #include "llvm/Target/TargetLowering.h"
      33             : #include "llvm/Target/TargetRegisterInfo.h"
      34             : #include "llvm/Target/TargetSubtargetInfo.h"
      35             : #include <climits>
      36             : using namespace llvm;
      37             : 
      38             : #define DEBUG_TYPE "pre-RA-sched"
      39             : 
      40             : STATISTIC(NumBacktracks, "Number of times scheduler backtracked");
      41             : STATISTIC(NumUnfolds,    "Number of nodes unfolded");
      42             : STATISTIC(NumDups,       "Number of duplicated nodes");
      43             : STATISTIC(NumPRCopies,   "Number of physical register copies");
      44             : 
      45             : static RegisterScheduler
      46       72306 :   burrListDAGScheduler("list-burr",
      47             :                        "Bottom-up register reduction list scheduling",
      48       72306 :                        createBURRListDAGScheduler);
      49             : static RegisterScheduler
      50       72306 :   sourceListDAGScheduler("source",
      51             :                          "Similar to list-burr but schedules in source "
      52             :                          "order when possible",
      53       72306 :                          createSourceListDAGScheduler);
      54             : 
      55             : static RegisterScheduler
      56       72306 :   hybridListDAGScheduler("list-hybrid",
      57             :                          "Bottom-up register pressure aware list scheduling "
      58             :                          "which tries to balance latency and register pressure",
      59       72306 :                          createHybridListDAGScheduler);
      60             : 
      61             : static RegisterScheduler
      62       72306 :   ILPListDAGScheduler("list-ilp",
      63             :                       "Bottom-up register pressure aware list scheduling "
      64             :                       "which tries to balance ILP and register pressure",
      65       72306 :                       createILPListDAGScheduler);
      66             : 
      67       72306 : static cl::opt<bool> DisableSchedCycles(
      68      216918 :   "disable-sched-cycles", cl::Hidden, cl::init(false),
      69      289224 :   cl::desc("Disable cycle-level precision during preRA scheduling"));
      70             : 
      71             : // Temporary sched=list-ilp flags until the heuristics are robust.
      72             : // Some options are also available under sched=list-hybrid.
      73       72306 : static cl::opt<bool> DisableSchedRegPressure(
      74      216918 :   "disable-sched-reg-pressure", cl::Hidden, cl::init(false),
      75      289224 :   cl::desc("Disable regpressure priority in sched=list-ilp"));
      76       72306 : static cl::opt<bool> DisableSchedLiveUses(
      77      216918 :   "disable-sched-live-uses", cl::Hidden, cl::init(true),
      78      289224 :   cl::desc("Disable live use priority in sched=list-ilp"));
      79       72306 : static cl::opt<bool> DisableSchedVRegCycle(
      80      216918 :   "disable-sched-vrcycle", cl::Hidden, cl::init(false),
      81      289224 :   cl::desc("Disable virtual register cycle interference checks"));
      82       72306 : static cl::opt<bool> DisableSchedPhysRegJoin(
      83      216918 :   "disable-sched-physreg-join", cl::Hidden, cl::init(false),
      84      289224 :   cl::desc("Disable physreg def-use affinity"));
      85       72306 : static cl::opt<bool> DisableSchedStalls(
      86      216918 :   "disable-sched-stalls", cl::Hidden, cl::init(true),
      87      289224 :   cl::desc("Disable no-stall priority in sched=list-ilp"));
      88       72306 : static cl::opt<bool> DisableSchedCriticalPath(
      89      216918 :   "disable-sched-critical-path", cl::Hidden, cl::init(false),
      90      289224 :   cl::desc("Disable critical path priority in sched=list-ilp"));
      91       72306 : static cl::opt<bool> DisableSchedHeight(
      92      216918 :   "disable-sched-height", cl::Hidden, cl::init(false),
      93      289224 :   cl::desc("Disable scheduled-height priority in sched=list-ilp"));
      94       72306 : static cl::opt<bool> Disable2AddrHack(
      95      216918 :   "disable-2addr-hack", cl::Hidden, cl::init(true),
      96      289224 :   cl::desc("Disable scheduler's two-address hack"));
      97             : 
      98       72306 : static cl::opt<int> MaxReorderWindow(
      99      216918 :   "max-sched-reorder", cl::Hidden, cl::init(6),
     100      216918 :   cl::desc("Number of instructions to allow ahead of the critical path "
     101       72306 :            "in sched=list-ilp"));
     102             : 
     103       72306 : static cl::opt<unsigned> AvgIPC(
     104      216918 :   "sched-avg-ipc", cl::Hidden, cl::init(1),
     105      289224 :   cl::desc("Average inst/cycle whan no target itinerary exists."));
     106             : 
     107             : namespace {
     108             : //===----------------------------------------------------------------------===//
     109             : /// ScheduleDAGRRList - The actual register reduction list scheduler
     110             : /// implementation.  This supports both top-down and bottom-up scheduling.
     111             : ///
     112             : class ScheduleDAGRRList : public ScheduleDAGSDNodes {
     113             : private:
     114             :   /// NeedLatency - True if the scheduler will make use of latency information.
     115             :   ///
     116             :   bool NeedLatency;
     117             : 
     118             :   /// AvailableQueue - The priority queue to use for the available SUnits.
     119             :   SchedulingPriorityQueue *AvailableQueue;
     120             : 
     121             :   /// PendingQueue - This contains all of the instructions whose operands have
     122             :   /// been issued, but their results are not ready yet (due to the latency of
     123             :   /// the operation).  Once the operands becomes available, the instruction is
     124             :   /// added to the AvailableQueue.
     125             :   std::vector<SUnit*> PendingQueue;
     126             : 
     127             :   /// HazardRec - The hazard recognizer to use.
     128             :   ScheduleHazardRecognizer *HazardRec;
     129             : 
     130             :   /// CurCycle - The current scheduler state corresponds to this cycle.
     131             :   unsigned CurCycle;
     132             : 
     133             :   /// MinAvailableCycle - Cycle of the soonest available instruction.
     134             :   unsigned MinAvailableCycle;
     135             : 
     136             :   /// IssueCount - Count instructions issued in this cycle
     137             :   /// Currently valid only for bottom-up scheduling.
     138             :   unsigned IssueCount;
     139             : 
     140             :   /// LiveRegDefs - A set of physical registers and their definition
     141             :   /// that are "live". These nodes must be scheduled before any other nodes that
     142             :   /// modifies the registers can be scheduled.
     143             :   unsigned NumLiveRegs;
     144             :   std::unique_ptr<SUnit*[]> LiveRegDefs;
     145             :   std::unique_ptr<SUnit*[]> LiveRegGens;
     146             : 
     147             :   // Collect interferences between physical register use/defs.
     148             :   // Each interference is an SUnit and set of physical registers.
     149             :   SmallVector<SUnit*, 4> Interferences;
     150             :   typedef DenseMap<SUnit*, SmallVector<unsigned, 4> > LRegsMapT;
     151             :   LRegsMapT LRegsMap;
     152             : 
     153             :   /// Topo - A topological ordering for SUnits which permits fast IsReachable
     154             :   /// and similar queries.
     155             :   ScheduleDAGTopologicalSort Topo;
     156             : 
     157             :   // Hack to keep track of the inverse of FindCallSeqStart without more crazy
     158             :   // DAG crawling.
     159             :   DenseMap<SUnit*, SUnit*> CallSeqEndForStart;
     160             : 
     161             : public:
     162      279964 :   ScheduleDAGRRList(MachineFunction &mf, bool needlatency,
     163             :                     SchedulingPriorityQueue *availqueue,
     164             :                     CodeGenOpt::Level OptLevel)
     165      279964 :     : ScheduleDAGSDNodes(mf),
     166             :       NeedLatency(needlatency), AvailableQueue(availqueue), CurCycle(0),
     167     1959748 :       Topo(SUnits, nullptr) {
     168             : 
     169      279964 :     const TargetSubtargetInfo &STI = mf.getSubtarget();
     170      279964 :     if (DisableSchedCycles || !NeedLatency)
     171      505830 :       HazardRec = new ScheduleHazardRecognizer();
     172             :     else
     173       27049 :       HazardRec = STI.getInstrInfo()->CreateTargetHazardRecognizer(&STI, this);
     174      279964 :   }
     175             : 
     176     2519676 :   ~ScheduleDAGRRList() override {
     177      279964 :     delete HazardRec;
     178      279964 :     delete AvailableQueue;
     179      559928 :   }
     180             : 
     181             :   void Schedule() override;
     182             : 
     183             :   ScheduleHazardRecognizer *getHazardRec() { return HazardRec; }
     184             : 
     185             :   /// IsReachable - Checks if SU is reachable from TargetSU.
     186             :   bool IsReachable(const SUnit *SU, const SUnit *TargetSU) {
     187         201 :     return Topo.IsReachable(SU, TargetSU);
     188             :   }
     189             : 
     190             :   /// WillCreateCycle - Returns true if adding an edge from SU to TargetSU will
     191             :   /// create a cycle.
     192             :   bool WillCreateCycle(SUnit *SU, SUnit *TargetSU) {
     193       22271 :     return Topo.WillCreateCycle(SU, TargetSU);
     194             :   }
     195             : 
     196             :   /// AddPred - adds a predecessor edge to SUnit SU.
     197             :   /// This returns true if this is a new predecessor.
     198             :   /// Updates the topological ordering if required.
     199       97770 :   void AddPred(SUnit *SU, const SDep &D) {
     200      195540 :     Topo.AddPred(SU, D.getSUnit());
     201       97770 :     SU->addPred(D);
     202       97770 :   }
     203             : 
     204             :   /// RemovePred - removes a predecessor edge from SUnit SU.
     205             :   /// This returns true if an edge was removed.
     206             :   /// Updates the topological ordering if required.
     207       48352 :   void RemovePred(SUnit *SU, const SDep &D) {
     208       96704 :     Topo.RemovePred(SU, D.getSUnit());
     209       48352 :     SU->removePred(D);
     210       48352 :   }
     211             : 
     212             : private:
     213             :   bool isReady(SUnit *SU) {
     214     3334068 :     return DisableSchedCycles || !AvailableQueue->hasReadyFilter() ||
     215           0 :       AvailableQueue->isReady(SU);
     216             :   }
     217             : 
     218             :   void ReleasePred(SUnit *SU, const SDep *PredEdge);
     219             :   void ReleasePredecessors(SUnit *SU);
     220             :   void ReleasePending();
     221             :   void AdvanceToCycle(unsigned NextCycle);
     222             :   void AdvancePastStalls(SUnit *SU);
     223             :   void EmitNode(SUnit *SU);
     224             :   void ScheduleNodeBottomUp(SUnit*);
     225             :   void CapturePred(SDep *PredEdge);
     226             :   void UnscheduleNodeBottomUp(SUnit*);
     227             :   void RestoreHazardCheckerBottomUp();
     228             :   void BacktrackBottomUp(SUnit*, SUnit*);
     229             :   SUnit *TryUnfoldSU(SUnit *);
     230             :   SUnit *CopyAndMoveSuccessors(SUnit*);
     231             :   void InsertCopiesAndMoveSuccs(SUnit*, unsigned,
     232             :                                 const TargetRegisterClass*,
     233             :                                 const TargetRegisterClass*,
     234             :                                 SmallVectorImpl<SUnit*>&);
     235             :   bool DelayForLiveRegsBottomUp(SUnit*, SmallVectorImpl<unsigned>&);
     236             : 
     237             :   void releaseInterferences(unsigned Reg = 0);
     238             : 
     239             :   SUnit *PickNodeToScheduleBottomUp();
     240             :   void ListScheduleBottomUp();
     241             : 
     242             :   /// CreateNewSUnit - Creates a new SUnit and returns a pointer to it.
     243             :   /// Updates the topological ordering if required.
     244       12592 :   SUnit *CreateNewSUnit(SDNode *N) {
     245       25184 :     unsigned NumSUnits = SUnits.size();
     246       12592 :     SUnit *NewNode = newSUnit(N);
     247             :     // Update the topological ordering.
     248       12592 :     if (NewNode->NodeNum >= NumSUnits)
     249       12592 :       Topo.InitDAGTopologicalSorting();
     250       12592 :     return NewNode;
     251             :   }
     252             : 
     253             :   /// CreateClone - Creates a new SUnit from an existing one.
     254             :   /// Updates the topological ordering if required.
     255       19105 :   SUnit *CreateClone(SUnit *N) {
     256       38210 :     unsigned NumSUnits = SUnits.size();
     257       19105 :     SUnit *NewNode = Clone(N);
     258             :     // Update the topological ordering.
     259       19105 :     if (NewNode->NodeNum >= NumSUnits)
     260       19105 :       Topo.InitDAGTopologicalSorting();
     261       19105 :     return NewNode;
     262             :   }
     263             : 
     264             :   /// forceUnitLatencies - Register-pressure-reducing scheduling doesn't
     265             :   /// need actual latency information but the hybrid scheduler does.
     266     3790080 :   bool forceUnitLatencies() const override {
     267     8374984 :     return !NeedLatency;
     268             :   }
     269             : };
     270             : }  // end anonymous namespace
     271             : 
     272             : /// GetCostForDef - Looks up the register class and cost for a given definition.
     273             : /// Typically this just means looking up the representative register class,
     274             : /// but for untyped values (MVT::Untyped) it means inspecting the node's
     275             : /// opcode to determine what register class is being generated.
     276      507981 : static void GetCostForDef(const ScheduleDAGSDNodes::RegDefIter &RegDefPos,
     277             :                           const TargetLowering *TLI,
     278             :                           const TargetInstrInfo *TII,
     279             :                           const TargetRegisterInfo *TRI,
     280             :                           unsigned &RegClass, unsigned &Cost,
     281             :                           const MachineFunction &MF) {
     282      507981 :   MVT VT = RegDefPos.GetValue();
     283             : 
     284             :   // Special handling for untyped values.  These values can only come from
     285             :   // the expansion of custom DAG-to-DAG patterns.
     286      507981 :   if (VT == MVT::Untyped) {
     287        1950 :     const SDNode *Node = RegDefPos.GetNode();
     288             : 
     289             :     // Special handling for CopyFromReg of untyped values.
     290        2086 :     if (!Node->isMachineOpcode() && Node->getOpcode() == ISD::CopyFromReg) {
     291         408 :       unsigned Reg = cast<RegisterSDNode>(Node->getOperand(1))->getReg();
     292         272 :       const TargetRegisterClass *RC = MF.getRegInfo().getRegClass(Reg);
     293         136 :       RegClass = RC->getID();
     294         136 :       Cost = 1;
     295         527 :       return;
     296             :     }
     297             : 
     298        1814 :     unsigned Opcode = Node->getMachineOpcode();
     299        1814 :     if (Opcode == TargetOpcode::REG_SEQUENCE) {
     300        1020 :       unsigned DstRCIdx = cast<ConstantSDNode>(Node->getOperand(0))->getZExtValue();
     301         510 :       const TargetRegisterClass *RC = TRI->getRegClass(DstRCIdx);
     302         255 :       RegClass = RC->getID();
     303         255 :       Cost = 1;
     304         255 :       return;
     305             :     }
     306             : 
     307        3118 :     unsigned Idx = RegDefPos.GetIdx();
     308        3118 :     const MCInstrDesc Desc = TII->get(Opcode);
     309        1559 :     const TargetRegisterClass *RC = TII->getRegClass(Desc, Idx, TRI, MF);
     310        3118 :     RegClass = RC->getID();
     311             :     // FIXME: Cost arbitrarily set to 1 because there doesn't seem to be a
     312             :     // better way to determine it.
     313        1559 :     Cost = 1;
     314             :   } else {
     315     1012062 :     RegClass = TLI->getRepRegClassFor(VT)->getID();
     316      506031 :     Cost = TLI->getRepRegClassCostFor(VT);
     317             :   }
     318             : }
     319             : 
     320             : /// Schedule - Schedule the DAG using list scheduling.
     321      279964 : void ScheduleDAGRRList::Schedule() {
     322             :   DEBUG(dbgs()
     323             :         << "********** List Scheduling BB#" << BB->getNumber()
     324             :         << " '" << BB->getName() << "' **********\n");
     325             : 
     326      279964 :   CurCycle = 0;
     327      279964 :   IssueCount = 0;
     328      279964 :   MinAvailableCycle = DisableSchedCycles ? 0 : UINT_MAX;
     329      279964 :   NumLiveRegs = 0;
     330             :   // Allocate slots for each physical register, plus one for a special register
     331             :   // to track the virtual resource of a calling sequence.
     332      559928 :   LiveRegDefs.reset(new SUnit*[TRI->getNumRegs() + 1]());
     333      559928 :   LiveRegGens.reset(new SUnit*[TRI->getNumRegs() + 1]());
     334      279964 :   CallSeqEndForStart.clear();
     335             :   assert(Interferences.empty() && LRegsMap.empty() && "stale Interferences");
     336             : 
     337             :   // Build the scheduling graph.
     338      279964 :   BuildSchedGraph(nullptr);
     339             : 
     340             :   DEBUG(for (SUnit &SU : SUnits)
     341             :           SU.dumpAll(this));
     342      279964 :   Topo.InitDAGTopologicalSorting();
     343             : 
     344      279964 :   AvailableQueue->initNodes(SUnits);
     345             : 
     346      279964 :   HazardRec->Reset();
     347             : 
     348             :   // Execute the actual scheduling loop.
     349      279964 :   ListScheduleBottomUp();
     350             : 
     351      279964 :   AvailableQueue->releaseState();
     352             : 
     353             :   DEBUG({
     354             :       dbgs() << "*** Final schedule ***\n";
     355             :       dumpSchedule();
     356             :       dbgs() << '\n';
     357             :     });
     358      279964 : }
     359             : 
     360             : //===----------------------------------------------------------------------===//
     361             : //  Bottom-Up Scheduling
     362             : //===----------------------------------------------------------------------===//
     363             : 
     364             : /// ReleasePred - Decrement the NumSuccsLeft count of a predecessor. Add it to
     365             : /// the AvailableQueue if the count reaches zero. Also update its cycle bound.
     366     4584904 : void ScheduleDAGRRList::ReleasePred(SUnit *SU, const SDep *PredEdge) {
     367     4584904 :   SUnit *PredSU = PredEdge->getSUnit();
     368             : 
     369             : #ifndef NDEBUG
     370             :   if (PredSU->NumSuccsLeft == 0) {
     371             :     dbgs() << "*** Scheduling failed! ***\n";
     372             :     PredSU->dump(this);
     373             :     dbgs() << " has been released too many times!\n";
     374             :     llvm_unreachable(nullptr);
     375             :   }
     376             : #endif
     377     4584904 :   --PredSU->NumSuccsLeft;
     378             : 
     379     9169808 :   if (!forceUnitLatencies()) {
     380             :     // Updating predecessor's height. This is now the cycle when the
     381             :     // predecessor can be scheduled without causing a pipeline stall.
     382      462144 :     PredSU->setHeightToAtLeast(SU->getHeight() + PredEdge->getLatency());
     383             :   }
     384             : 
     385             :   // If all the node's successors are scheduled, this node is ready
     386             :   // to be scheduled. Ignore the special EntrySU node.
     387     4584904 :   if (PredSU->NumSuccsLeft == 0 && PredSU != &EntrySU) {
     388     3334068 :     PredSU->isAvailable = true;
     389             : 
     390     6668136 :     unsigned Height = PredSU->getHeight();
     391     3334068 :     if (Height < MinAvailableCycle)
     392     1386925 :       MinAvailableCycle = Height;
     393             : 
     394     3334068 :     if (isReady(PredSU)) {
     395     3334068 :       AvailableQueue->push(PredSU);
     396             :     }
     397             :     // CapturePred and others may have left the node in the pending queue, avoid
     398             :     // adding it twice.
     399           0 :     else if (!PredSU->isPending) {
     400           0 :       PredSU->isPending = true;
     401           0 :       PendingQueue.push_back(PredSU);
     402             :     }
     403             :   }
     404     4584904 : }
     405             : 
     406             : /// IsChainDependent - Test if Outer is reachable from Inner through
     407             : /// chain dependencies.
     408       45940 : static bool IsChainDependent(SDNode *Outer, SDNode *Inner,
     409             :                              unsigned NestLevel,
     410             :                              const TargetInstrInfo *TII) {
     411       45940 :   SDNode *N = Outer;
     412             :   for (;;) {
     413       91948 :     if (N == Inner)
     414             :       return true;
     415             :     // For a TokenFactor, examine each operand. There may be multiple ways
     416             :     // to get to the CALLSEQ_BEGIN, but we need to find the path with the
     417             :     // most nesting in order to ensure that we find the corresponding match.
     418      183890 :     if (N->getOpcode() == ISD::TokenFactor) {
     419       91053 :       for (const SDValue &Op : N->op_values())
     420       40727 :         if (IsChainDependent(Op.getNode(), Inner, NestLevel, TII))
     421             :           return true;
     422             :       return false;
     423             :     }
     424             :     // Check for a lowered CALLSEQ_BEGIN or CALLSEQ_END.
     425       87144 :     if (N->isMachineOpcode()) {
     426      173496 :       if (N->getMachineOpcode() == TII->getCallFrameDestroyOpcode()) {
     427           0 :         ++NestLevel;
     428       86748 :       } else if (N->getMachineOpcode() == TII->getCallFrameSetupOpcode()) {
     429       41136 :         if (NestLevel == 0)
     430             :           return false;
     431           0 :         --NestLevel;
     432             :       }
     433             :     }
     434             :     // Otherwise, find the chain and continue climbing.
     435      646622 :     for (const SDValue &Op : N->op_values())
     436      900921 :       if (Op.getValueType() == MVT::Other) {
     437       46008 :         N = Op.getNode();
     438       46008 :         goto found_chain_operand;
     439             :       }
     440             :     return false;
     441       46008 :   found_chain_operand:;
     442       46008 :     if (N->getOpcode() == ISD::EntryToken)
     443             :       return false;
     444             :   }
     445             : }
     446             : 
     447             : /// FindCallSeqStart - Starting from the (lowered) CALLSEQ_END node, locate
     448             : /// the corresponding (lowered) CALLSEQ_BEGIN node.
     449             : ///
     450             : /// NestLevel and MaxNested are used in recursion to indcate the current level
     451             : /// of nesting of CALLSEQ_BEGIN and CALLSEQ_END pairs, as well as the maximum
     452             : /// level seen so far.
     453             : ///
     454             : /// TODO: It would be better to give CALLSEQ_END an explicit operand to point
     455             : /// to the corresponding CALLSEQ_BEGIN to avoid needing to search for it.
     456             : static SDNode *
     457      308764 : FindCallSeqStart(SDNode *N, unsigned &NestLevel, unsigned &MaxNest,
     458             :                  const TargetInstrInfo *TII) {
     459             :   for (;;) {
     460             :     // For a TokenFactor, examine each operand. There may be multiple ways
     461             :     // to get to the CALLSEQ_BEGIN, but we need to find the path with the
     462             :     // most nesting in order to ensure that we find the corresponding match.
     463     2370956 :     if (N->getOpcode() == ISD::TokenFactor) {
     464       33814 :       SDNode *Best = nullptr;
     465       33814 :       unsigned BestMaxNest = MaxNest;
     466      311912 :       for (const SDValue &Op : N->op_values()) {
     467      122142 :         unsigned MyNestLevel = NestLevel;
     468      122142 :         unsigned MyMaxNest = MaxNest;
     469      122142 :         if (SDNode *New = FindCallSeqStart(Op.getNode(),
     470      122142 :                                            MyNestLevel, MyMaxNest, TII))
     471      122105 :           if (!Best || (MyMaxNest > BestMaxNest)) {
     472       33817 :             Best = New;
     473       33817 :             BestMaxNest = MyMaxNest;
     474             :           }
     475             :       }
     476             :       assert(Best);
     477       33814 :       MaxNest = BestMaxNest;
     478       33814 :       return Best;
     479             :     }
     480             :     // Check for a lowered CALLSEQ_BEGIN or CALLSEQ_END.
     481     1151664 :     if (N->isMachineOpcode()) {
     482     1592416 :       if (N->getMachineOpcode() == TII->getCallFrameDestroyOpcode()) {
     483      186625 :         ++NestLevel;
     484      186625 :         MaxNest = std::max(MaxNest, NestLevel);
     485      609583 :       } else if (N->getMachineOpcode() == TII->getCallFrameSetupOpcode()) {
     486             :         assert(NestLevel != 0);
     487      274916 :         --NestLevel;
     488      274916 :         if (NestLevel == 0)
     489             :           return N;
     490             :       }
     491             :     }
     492             :     // Otherwise, find the chain and continue climbing.
     493     6645331 :     for (const SDValue &Op : N->op_values())
     494     8652870 :       if (Op.getValueType() == MVT::Other) {
     495      876751 :         N = Op.getNode();
     496      876751 :         goto found_chain_operand;
     497             :       }
     498             :     return nullptr;
     499      876751 :   found_chain_operand:;
     500      876751 :     if (N->getOpcode() == ISD::EntryToken)
     501             :       return nullptr;
     502             :   }
     503             : }
     504             : 
     505             : /// Call ReleasePred for each predecessor, then update register live def/gen.
     506             : /// Always update LiveRegDefs for a register dependence even if the current SU
     507             : /// also defines the register. This effectively create one large live range
     508             : /// across a sequence of two-address node. This is important because the
     509             : /// entire chain must be scheduled together. Example:
     510             : ///
     511             : /// flags = (3) add
     512             : /// flags = (2) addc flags
     513             : /// flags = (1) addc flags
     514             : ///
     515             : /// results in
     516             : ///
     517             : /// LiveRegDefs[flags] = 3
     518             : /// LiveRegGens[flags] = 1
     519             : ///
     520             : /// If (2) addc is unscheduled, then (1) addc must also be unscheduled to avoid
     521             : /// interference on flags.
     522     3887878 : void ScheduleDAGRRList::ReleasePredecessors(SUnit *SU) {
     523             :   // Bottom up: release predecessors
     524    16248538 :   for (SDep &Pred : SU->Preds) {
     525     4584904 :     ReleasePred(SU, &Pred);
     526      146971 :     if (Pred.isAssignedRegDep()) {
     527             :       // This is a physical register dependency and it's impossible or
     528             :       // expensive to copy the register. Make sure nothing that can
     529             :       // clobber the register is scheduled between the predecessor and
     530             :       // this node.
     531      293942 :       SUnit *RegDef = LiveRegDefs[Pred.getReg()]; (void)RegDef;
     532             :       assert((!RegDef || RegDef == SU || RegDef == Pred.getSUnit()) &&
     533             :              "interference on register dependence");
     534      440913 :       LiveRegDefs[Pred.getReg()] = Pred.getSUnit();
     535      293942 :       if (!LiveRegGens[Pred.getReg()]) {
     536      128832 :         ++NumLiveRegs;
     537      257664 :         LiveRegGens[Pred.getReg()] = SU;
     538             :       }
     539             :     }
     540             :   }
     541             : 
     542             :   // If we're scheduling a lowered CALLSEQ_END, find the corresponding
     543             :   // CALLSEQ_BEGIN. Inject an artificial physical register dependence between
     544             :   // these nodes, to prevent other calls from being interscheduled with them.
     545     3887878 :   unsigned CallResource = TRI->getNumRegs();
     546     7775756 :   if (!LiveRegDefs[CallResource])
     547     3136878 :     for (SDNode *Node = SU->getNode(); Node; Node = Node->getGluedNode())
     548     5357722 :       if (Node->isMachineOpcode() &&
     549     4365146 :           Node->getMachineOpcode() == TII->getCallFrameDestroyOpcode()) {
     550      186622 :         unsigned NestLevel = 0;
     551      186622 :         unsigned MaxNest = 0;
     552      186622 :         SDNode *N = FindCallSeqStart(Node, NestLevel, MaxNest, TII);
     553             :         assert(N && "Must find call sequence start");
     554             : 
     555      373244 :         SUnit *Def = &SUnits[N->getNodeId()];
     556      373244 :         CallSeqEndForStart[Def] = SU;
     557             : 
     558      186622 :         ++NumLiveRegs;
     559      373244 :         LiveRegDefs[CallResource] = Def;
     560      373244 :         LiveRegGens[CallResource] = SU;
     561             :         break;
     562             :       }
     563     3887878 : }
     564             : 
     565             : /// Check to see if any of the pending instructions are ready to issue.  If
     566             : /// so, add them to the available queue.
     567     3583068 : void ScheduleDAGRRList::ReleasePending() {
     568     3583068 :   if (DisableSchedCycles) {
     569             :     assert(PendingQueue.empty() && "pending instrs not allowed in this mode");
     570             :     return;
     571             :   }
     572             : 
     573             :   // If the available queue is empty, it is safe to reset MinAvailableCycle.
     574     3583068 :   if (AvailableQueue->empty())
     575     1642083 :     MinAvailableCycle = UINT_MAX;
     576             : 
     577             :   // Check to see if any of the pending instructions are ready to issue.  If
     578             :   // so, add them to the available queue.
     579     7166136 :   for (unsigned i = 0, e = PendingQueue.size(); i != e; ++i) {
     580           0 :     unsigned ReadyCycle = PendingQueue[i]->getHeight();
     581           0 :     if (ReadyCycle < MinAvailableCycle)
     582           0 :       MinAvailableCycle = ReadyCycle;
     583             : 
     584           0 :     if (PendingQueue[i]->isAvailable) {
     585           0 :       if (!isReady(PendingQueue[i]))
     586           0 :           continue;
     587           0 :       AvailableQueue->push(PendingQueue[i]);
     588             :     }
     589           0 :     PendingQueue[i]->isPending = false;
     590           0 :     PendingQueue[i] = PendingQueue.back();
     591           0 :     PendingQueue.pop_back();
     592           0 :     --i; --e;
     593             :   }
     594             : }
     595             : 
     596             : /// Move the scheduler state forward by the specified number of Cycles.
     597    10571878 : void ScheduleDAGRRList::AdvanceToCycle(unsigned NextCycle) {
     598    10571878 :   if (NextCycle <= CurCycle)
     599             :     return;
     600             : 
     601     3582447 :   IssueCount = 0;
     602     7164894 :   AvailableQueue->setCurCycle(NextCycle);
     603     3582447 :   if (!HazardRec->isEnabled()) {
     604             :     // Bypass lots of virtual calls in case of long latency.
     605     3539371 :     CurCycle = NextCycle;
     606             :   }
     607             :   else {
     608      248250 :     for (; CurCycle != NextCycle; ++CurCycle) {
     609      102587 :       HazardRec->RecedeCycle();
     610             :     }
     611             :   }
     612             :   // FIXME: Instead of visiting the pending Q each time, set a dirty flag on the
     613             :   // available Q to release pending nodes at least once before popping.
     614     3582447 :   ReleasePending();
     615             : }
     616             : 
     617             : /// Move the scheduler state forward until the specified node's dependents are
     618             : /// ready and can be scheduled with no resource conflicts.
     619     3607914 : void ScheduleDAGRRList::AdvancePastStalls(SUnit *SU) {
     620     3607914 :   if (DisableSchedCycles)
     621             :     return;
     622             : 
     623             :   // FIXME: Nodes such as CopyFromReg probably should not advance the current
     624             :   // cycle. Otherwise, we can wrongly mask real stalls. If the non-machine node
     625             :   // has predecessors the cycle will be advanced when they are scheduled.
     626             :   // But given the crude nature of modeling latency though such nodes, we
     627             :   // currently need to treat these nodes like real instructions.
     628             :   // if (!SU->getNode() || !SU->getNode()->isMachineOpcode()) return;
     629             : 
     630     3607914 :   unsigned ReadyCycle = SU->getHeight();
     631             : 
     632             :   // Bump CurCycle to account for latency. We assume the latency of other
     633             :   // available instructions may be hidden by the stall (not a full pipe stall).
     634             :   // This updates the hazard recognizer's cycle before reserving resources for
     635             :   // this instruction.
     636     3607914 :   AdvanceToCycle(ReadyCycle);
     637             : 
     638             :   // Calls are scheduled in their preceding cycle, so don't conflict with
     639             :   // hazards from instructions after the call. EmitNode will reset the
     640             :   // scoreboard state before emitting the call.
     641     3607914 :   if (SU->isCall)
     642             :     return;
     643             : 
     644             :   // FIXME: For resource conflicts in very long non-pipelined stages, we
     645             :   // should probably skip ahead here to avoid useless scoreboard checks.
     646             :   int Stalls = 0;
     647             :   while (true) {
     648             :     ScheduleHazardRecognizer::HazardType HT =
     649     3430861 :       HazardRec->getHazardType(SU, -Stalls);
     650             : 
     651     3430861 :     if (HT == ScheduleHazardRecognizer::NoHazard)
     652             :       break;
     653             : 
     654        9307 :     ++Stalls;
     655        9307 :   }
     656     3421554 :   AdvanceToCycle(CurCycle + Stalls);
     657             : }
     658             : 
     659             : /// Record this SUnit in the HazardRecognizer.
     660             : /// Does not update CurCycle.
     661     3608022 : void ScheduleDAGRRList::EmitNode(SUnit *SU) {
     662     3608022 :   if (!HazardRec->isEnabled())
     663             :     return;
     664             : 
     665             :   // Check for phys reg copy.
     666       69584 :   if (!SU->getNode())
     667             :     return;
     668             : 
     669      139164 :   switch (SU->getNode()->getOpcode()) {
     670             :   default:
     671             :     assert(SU->getNode()->isMachineOpcode() &&
     672             :            "This target-independent node should not be scheduled.");
     673             :     break;
     674             :   case ISD::MERGE_VALUES:
     675             :   case ISD::TokenFactor:
     676             :   case ISD::LIFETIME_START:
     677             :   case ISD::LIFETIME_END:
     678             :   case ISD::CopyToReg:
     679             :   case ISD::CopyFromReg:
     680             :   case ISD::EH_LABEL:
     681             :     // Noops don't affect the scoreboard state. Copies are likely to be
     682             :     // removed.
     683             :     return;
     684         164 :   case ISD::INLINEASM:
     685             :     // For inline asm, clear the pipeline state.
     686         164 :     HazardRec->Reset();
     687             :     return;
     688             :   }
     689       49264 :   if (SU->isCall) {
     690             :     // Calls are scheduled with their preceding instructions. For bottom-up
     691             :     // scheduling, clear the pipeline state before emitting.
     692        1251 :     HazardRec->Reset();
     693             :   }
     694             : 
     695       49264 :   HazardRec->EmitInstruction(SU);
     696             : }
     697             : 
     698             : static void resetVRegCycle(SUnit *SU);
     699             : 
     700             : /// ScheduleNodeBottomUp - Add the node to the schedule. Decrement the pending
     701             : /// count of its predecessors. If a predecessor pending count is zero, add it to
     702             : /// the Available queue.
     703     3607914 : void ScheduleDAGRRList::ScheduleNodeBottomUp(SUnit *SU) {
     704             :   DEBUG(dbgs() << "\n*** Scheduling [" << CurCycle << "]: ");
     705             :   DEBUG(SU->dump(this));
     706             : 
     707             : #ifndef NDEBUG
     708             :   if (CurCycle < SU->getHeight())
     709             :     DEBUG(dbgs() << "   Height [" << SU->getHeight()
     710             :           << "] pipeline stall!\n");
     711             : #endif
     712             : 
     713             :   // FIXME: Do not modify node height. It may interfere with
     714             :   // backtracking. Instead add a "ready cycle" to SUnit. Before scheduling the
     715             :   // node its ready cycle can aid heuristics, and after scheduling it can
     716             :   // indicate the scheduled cycle.
     717     3607914 :   SU->setHeightToAtLeast(CurCycle);
     718             : 
     719             :   // Reserve resources for the scheduled instruction.
     720     3607914 :   EmitNode(SU);
     721             : 
     722     3607914 :   Sequence.push_back(SU);
     723             : 
     724     3607914 :   AvailableQueue->scheduledNode(SU);
     725             : 
     726             :   // If HazardRec is disabled, and each inst counts as one cycle, then
     727             :   // advance CurCycle before ReleasePredecessors to avoid useless pushes to
     728             :   // PendingQueue for schedulers that implement HasReadyFilter.
     729     7146352 :   if (!HazardRec->isEnabled() && AvgIPC < 2)
     730     3538438 :     AdvanceToCycle(CurCycle + 1);
     731             : 
     732             :   // Update liveness of predecessors before successors to avoid treating a
     733             :   // two-address node as a live range def.
     734     3607914 :   ReleasePredecessors(SU);
     735             : 
     736             :   // Release all the implicit physical register defs that are live.
     737    15403295 :   for (SDep &Succ : SU->Succs) {
     738             :     // LiveRegDegs[Succ.getReg()] != SU when SU is a two-address node.
     739      292008 :     if (Succ.isAssignedRegDep() && LiveRegDefs[Succ.getReg()] == SU) {
     740             :       assert(NumLiveRegs > 0 && "NumLiveRegs is already zero!");
     741      128211 :       --NumLiveRegs;
     742      256422 :       LiveRegDefs[Succ.getReg()] = nullptr;
     743      256422 :       LiveRegGens[Succ.getReg()] = nullptr;
     744      128211 :       releaseInterferences(Succ.getReg());
     745             :     }
     746             :   }
     747             :   // Release the special call resource dependence, if this is the beginning
     748             :   // of a call.
     749     3607914 :   unsigned CallResource = TRI->getNumRegs();
     750     7215828 :   if (LiveRegDefs[CallResource] == SU)
     751      186488 :     for (const SDNode *SUNode = SU->getNode(); SUNode;
     752             :          SUNode = SUNode->getGluedNode()) {
     753      374652 :       if (SUNode->isMachineOpcode() &&
     754      374244 :           SUNode->getMachineOpcode() == TII->getCallFrameSetupOpcode()) {
     755             :         assert(NumLiveRegs > 0 && "NumLiveRegs is already zero!");
     756      186488 :         --NumLiveRegs;
     757      372976 :         LiveRegDefs[CallResource] = nullptr;
     758      372976 :         LiveRegGens[CallResource] = nullptr;
     759      186488 :         releaseInterferences(CallResource);
     760             :       }
     761             :     }
     762             : 
     763     3607914 :   resetVRegCycle(SU);
     764             : 
     765     3607914 :   SU->isScheduled = true;
     766             : 
     767             :   // Conditions under which the scheduler should eagerly advance the cycle:
     768             :   // (1) No available instructions
     769             :   // (2) All pipelines full, so available instructions must have hazards.
     770             :   //
     771             :   // If HazardRec is disabled, the cycle was pre-advanced before calling
     772             :   // ReleasePredecessors. In that case, IssueCount should remain 0.
     773             :   //
     774             :   // Check AvailableQueue after ReleasePredecessors in case of zero latency.
     775     7146352 :   if (HazardRec->isEnabled() || AvgIPC > 1) {
     776       69476 :     if (SU->getNode() && SU->getNode()->isMachineOpcode())
     777       49192 :       ++IssueCount;
     778      138952 :     if ((HazardRec->isEnabled() && HazardRec->atIssueLimit())
     779      134980 :         || (!HazardRec->isEnabled() && IssueCount == AvgIPC))
     780        3972 :       AdvanceToCycle(CurCycle + 1);
     781             :   }
     782     3607914 : }
     783             : 
     784             : /// CapturePred - This does the opposite of ReleasePred. Since SU is being
     785             : /// unscheduled, increase the succ left count of its predecessors. Remove
     786             : /// them from AvailableQueue if necessary.
     787       82106 : void ScheduleDAGRRList::CapturePred(SDep *PredEdge) {
     788       82106 :   SUnit *PredSU = PredEdge->getSUnit();
     789       82106 :   if (PredSU->isAvailable) {
     790       41173 :     PredSU->isAvailable = false;
     791       41173 :     if (!PredSU->isPending)
     792       36454 :       AvailableQueue->remove(PredSU);
     793             :   }
     794             : 
     795             :   assert(PredSU->NumSuccsLeft < UINT_MAX && "NumSuccsLeft will overflow!");
     796       82106 :   ++PredSU->NumSuccsLeft;
     797       82106 : }
     798             : 
     799             : /// UnscheduleNodeBottomUp - Remove the node from the schedule, update its and
     800             : /// its predecessor states to reflect the change.
     801       38410 : void ScheduleDAGRRList::UnscheduleNodeBottomUp(SUnit *SU) {
     802             :   DEBUG(dbgs() << "*** Unscheduling [" << SU->getHeight() << "]: ");
     803             :   DEBUG(SU->dump(this));
     804             : 
     805      197336 :   for (SDep &Pred : SU->Preds) {
     806       82106 :     CapturePred(&Pred);
     807       43698 :     if (Pred.isAssignedRegDep() && SU == LiveRegGens[Pred.getReg()]){
     808             :       assert(NumLiveRegs > 0 && "NumLiveRegs is already zero!");
     809             :       assert(LiveRegDefs[Pred.getReg()] == Pred.getSUnit() &&
     810             :              "Physical register dependency violated?");
     811       20709 :       --NumLiveRegs;
     812       41418 :       LiveRegDefs[Pred.getReg()] = nullptr;
     813       41418 :       LiveRegGens[Pred.getReg()] = nullptr;
     814       20709 :       releaseInterferences(Pred.getReg());
     815             :     }
     816             :   }
     817             : 
     818             :   // Reclaim the special call resource dependence, if this is the beginning
     819             :   // of a call.
     820       38410 :   unsigned CallResource = TRI->getNumRegs();
     821       38410 :   for (const SDNode *SUNode = SU->getNode(); SUNode;
     822             :        SUNode = SUNode->getGluedNode()) {
     823      103677 :     if (SUNode->isMachineOpcode() &&
     824       81442 :         SUNode->getMachineOpcode() == TII->getCallFrameSetupOpcode()) {
     825           6 :       SUnit *SeqEnd = CallSeqEndForStart[SU];
     826             :       assert(SeqEnd && "Call sequence start/end must be known");
     827             :       assert(!LiveRegDefs[CallResource]);
     828             :       assert(!LiveRegGens[CallResource]);
     829           3 :       ++NumLiveRegs;
     830           6 :       LiveRegDefs[CallResource] = SU;
     831           6 :       LiveRegGens[CallResource] = SeqEnd;
     832             :     }
     833             :   }
     834             : 
     835             :   // Release the special call resource dependence, if this is the end
     836             :   // of a call.
     837       76820 :   if (LiveRegGens[CallResource] == SU)
     838         137 :     for (const SDNode *SUNode = SU->getNode(); SUNode;
     839             :          SUNode = SUNode->getGluedNode()) {
     840         548 :       if (SUNode->isMachineOpcode() &&
     841         548 :           SUNode->getMachineOpcode() == TII->getCallFrameDestroyOpcode()) {
     842             :         assert(NumLiveRegs > 0 && "NumLiveRegs is already zero!");
     843             :         assert(LiveRegDefs[CallResource]);
     844             :         assert(LiveRegGens[CallResource]);
     845         137 :         --NumLiveRegs;
     846         274 :         LiveRegDefs[CallResource] = nullptr;
     847         274 :         LiveRegGens[CallResource] = nullptr;
     848         137 :         releaseInterferences(CallResource);
     849             :       }
     850             :     }
     851             : 
     852      191773 :   for (auto &Succ : SU->Succs) {
     853       20770 :     if (Succ.isAssignedRegDep()) {
     854       20770 :       auto Reg = Succ.getReg();
     855       41540 :       if (!LiveRegDefs[Reg])
     856       20088 :         ++NumLiveRegs;
     857             :       // This becomes the nearest def. Note that an earlier def may still be
     858             :       // pending if this is a two-address node.
     859       41540 :       LiveRegDefs[Reg] = SU;
     860             : 
     861             :       // Update LiveRegGen only if was empty before this unscheduling.
     862             :       // This is to avoid incorrect updating LiveRegGen set in previous run.
     863       41540 :       if (!LiveRegGens[Reg]) {
     864             :         // Find the successor with the lowest height.
     865       60264 :         LiveRegGens[Reg] = Succ.getSUnit();
     866      100620 :         for (auto &Succ2 : SU->Succs) {
     867       40176 :           if (Succ2.isAssignedRegDep() && Succ2.getReg() == Reg &&
     868       80352 :               Succ2.getSUnit()->getHeight() < LiveRegGens[Reg]->getHeight())
     869           0 :             LiveRegGens[Reg] = Succ2.getSUnit();
     870             :         }
     871             :       }
     872             :     }
     873             :   }
     874       76820 :   if (SU->getHeight() < MinAvailableCycle)
     875       76006 :     MinAvailableCycle = SU->getHeight();
     876             : 
     877       38410 :   SU->setHeightDirty();
     878       38410 :   SU->isScheduled = false;
     879       38410 :   SU->isAvailable = true;
     880       38410 :   if (!DisableSchedCycles && AvailableQueue->hasReadyFilter()) {
     881             :     // Don't make available until backtracking is complete.
     882           0 :     SU->isPending = true;
     883           0 :     PendingQueue.push_back(SU);
     884             :   }
     885             :   else {
     886       38410 :     AvailableQueue->push(SU);
     887             :   }
     888       38410 :   AvailableQueue->unscheduledNode(SU);
     889       38410 : }
     890             : 
     891             : /// After backtracking, the hazard checker needs to be restored to a state
     892             : /// corresponding the current cycle.
     893         621 : void ScheduleDAGRRList::RestoreHazardCheckerBottomUp() {
     894         621 :   HazardRec->Reset();
     895             : 
     896        1863 :   unsigned LookAhead = std::min((unsigned)Sequence.size(),
     897        1863 :                                 HazardRec->getMaxLookAhead());
     898         621 :   if (LookAhead == 0)
     899             :     return;
     900             : 
     901          16 :   std::vector<SUnit*>::const_iterator I = (Sequence.end() - LookAhead);
     902           8 :   unsigned HazardCycle = (*I)->getHeight();
     903         120 :   for (auto E = Sequence.end(); I != E; ++I) {
     904         108 :     SUnit *SU = *I;
     905         288 :     for (; SU->getHeight() > HazardCycle; ++HazardCycle) {
     906          90 :       HazardRec->RecedeCycle();
     907             :     }
     908         108 :     EmitNode(SU);
     909             :   }
     910             : }
     911             : 
     912             : /// BacktrackBottomUp - Backtrack scheduling to a previous cycle specified in
     913             : /// BTCycle in order to schedule a specific node.
     914         621 : void ScheduleDAGRRList::BacktrackBottomUp(SUnit *SU, SUnit *BtSU) {
     915        1242 :   SUnit *OldSU = Sequence.back();
     916             :   while (true) {
     917       76820 :     Sequence.pop_back();
     918             :     // FIXME: use ready cycle instead of height
     919       38410 :     CurCycle = OldSU->getHeight();
     920       38410 :     UnscheduleNodeBottomUp(OldSU);
     921       76820 :     AvailableQueue->setCurCycle(CurCycle);
     922       38410 :     if (OldSU == BtSU)
     923             :       break;
     924       75578 :     OldSU = Sequence.back();
     925             :   }
     926             : 
     927             :   assert(!SU->isSucc(OldSU) && "Something is wrong!");
     928             : 
     929         621 :   RestoreHazardCheckerBottomUp();
     930             : 
     931         621 :   ReleasePending();
     932             : 
     933         621 :   ++NumBacktracks;
     934         621 : }
     935             : 
     936        2257 : static bool isOperandOf(const SUnit *SU, SDNode *N) {
     937        2257 :   for (const SDNode *SUNode = SU->getNode(); SUNode;
     938             :        SUNode = SUNode->getGluedNode()) {
     939        2284 :     if (SUNode->isOperandOf(N))
     940             :       return true;
     941             :   }
     942             :   return false;
     943             : }
     944             : 
     945             : /// TryUnfold - Attempt to unfold
     946        6211 : SUnit *ScheduleDAGRRList::TryUnfoldSU(SUnit *SU) {
     947        6211 :   SDNode *N = SU->getNode();
     948             :   // Use while over if to ease fall through.
     949       12422 :   SmallVector<SDNode *, 2> NewNodes;
     950        6211 :   if (!TII->unfoldMemoryOperand(*DAG, N, NewNodes))
     951             :     return nullptr;
     952             : 
     953             :   // unfolding an x86 DEC64m operation results in store, dec, load which
     954             :   // can't be handled here so quit
     955        6211 :   if (NewNodes.size() == 3)
     956             :     return nullptr;
     957             : 
     958             :   assert(NewNodes.size() == 2 && "Expected a load folding node!");
     959             : 
     960        6200 :   N = NewNodes[1];
     961        6200 :   SDNode *LoadNode = NewNodes[0];
     962       12400 :   unsigned NumVals = N->getNumValues();
     963       12400 :   unsigned OldNumVals = SU->getNode()->getNumValues();
     964             : 
     965             :   // LoadNode may already exist. This can happen when there is another
     966             :   // load from the same location and producing the same type of value
     967             :   // but it has different alignment or volatileness.
     968        6200 :   bool isNewLoad = true;
     969             :   SUnit *LoadSU;
     970        6200 :   if (LoadNode->getNodeId() != -1) {
     971           2 :     LoadSU = &SUnits[LoadNode->getNodeId()];
     972             :     // If LoadSU has already been scheduled, we should clone it but
     973             :     // this would negate the benefit to unfolding so just return SU.
     974           1 :     if (LoadSU->isScheduled)
     975             :       return SU;
     976             :     isNewLoad = false;
     977             :   } else {
     978        6199 :     LoadSU = CreateNewSUnit(LoadNode);
     979       12398 :     LoadNode->setNodeId(LoadSU->NodeNum);
     980             : 
     981        6199 :     InitNumRegDefsLeft(LoadSU);
     982        6199 :     computeLatency(LoadSU);
     983             :   }
     984             : 
     985             :   DEBUG(dbgs() << "Unfolding SU #" << SU->NodeNum << "\n");
     986             : 
     987             :   // Now that we are committed to unfolding replace DAG Uses.
     988       12916 :   for (unsigned i = 0; i != NumVals; ++i)
     989       20151 :     DAG->ReplaceAllUsesOfValueWith(SDValue(SU->getNode(), i), SDValue(N, i));
     990       18597 :   DAG->ReplaceAllUsesOfValueWith(SDValue(SU->getNode(), OldNumVals - 1),
     991             :                                  SDValue(LoadNode, 1));
     992             : 
     993        6199 :   SUnit *NewSU = CreateNewSUnit(N);
     994             :   assert(N->getNodeId() == -1 && "Node already inserted!");
     995       12398 :   N->setNodeId(NewSU->NodeNum);
     996             : 
     997       18597 :   const MCInstrDesc &MCID = TII->get(N->getMachineOpcode());
     998       36158 :   for (unsigned i = 0; i != MCID.getNumOperands(); ++i) {
     999       12916 :     if (MCID.getOperandConstraint(i, MCOI::TIED_TO) != -1) {
    1000         518 :       NewSU->isTwoAddress = true;
    1001         518 :       break;
    1002             :     }
    1003             :   }
    1004        6199 :   if (MCID.isCommutable())
    1005          41 :     NewSU->isCommutable = true;
    1006             : 
    1007        6199 :   InitNumRegDefsLeft(NewSU);
    1008        6199 :   computeLatency(NewSU);
    1009             : 
    1010             :   // Record all the edges to and from the old SU, by category.
    1011        6199 :   SmallVector<SDep, 4> ChainPreds;
    1012       12398 :   SmallVector<SDep, 4> ChainSuccs;
    1013       12398 :   SmallVector<SDep, 4> LoadPreds;
    1014       12398 :   SmallVector<SDep, 4> NodePreds;
    1015       12398 :   SmallVector<SDep, 4> NodeSuccs;
    1016       25680 :   for (SDep &Pred : SU->Preds) {
    1017        7083 :     if (Pred.isCtrl())
    1018        4826 :       ChainPreds.push_back(Pred);
    1019        2257 :     else if (isOperandOf(Pred.getSUnit(), LoadNode))
    1020        1723 :       LoadPreds.push_back(Pred);
    1021             :     else
    1022         534 :       NodePreds.push_back(Pred);
    1023             :   }
    1024       40404 :   for (SDep &Succ : SU->Succs) {
    1025       21807 :     if (Succ.isCtrl())
    1026        9405 :       ChainSuccs.push_back(Succ);
    1027             :     else
    1028       12402 :       NodeSuccs.push_back(Succ);
    1029             :   }
    1030             : 
    1031             :   // Now assign edges to the newly-created nodes.
    1032       23423 :   for (const SDep &Pred : ChainPreds) {
    1033        4826 :     RemovePred(SU, Pred);
    1034        4826 :     if (isNewLoad)
    1035        4826 :       AddPred(LoadSU, Pred);
    1036             :   }
    1037       20320 :   for (const SDep &Pred : LoadPreds) {
    1038        1723 :     RemovePred(SU, Pred);
    1039        1723 :     if (isNewLoad)
    1040        1723 :       AddPred(LoadSU, Pred);
    1041             :   }
    1042       19131 :   for (const SDep &Pred : NodePreds) {
    1043         534 :     RemovePred(SU, Pred);
    1044         534 :     AddPred(NewSU, Pred);
    1045             :   }
    1046       30999 :   for (SDep D : NodeSuccs) {
    1047       12402 :     SUnit *SuccDep = D.getSUnit();
    1048       12402 :     D.setSUnit(SU);
    1049       12402 :     RemovePred(SuccDep, D);
    1050       12402 :     D.setSUnit(NewSU);
    1051       12402 :     AddPred(SuccDep, D);
    1052             :     // Balance register pressure.
    1053       12402 :     if (AvailableQueue->tracksRegPressure() && SuccDep->isScheduled &&
    1054       12402 :         !D.isCtrl() && NewSU->NumRegDefsLeft > 0)
    1055           0 :       --NewSU->NumRegDefsLeft;
    1056             :   }
    1057       28002 :   for (SDep D : ChainSuccs) {
    1058        9405 :     SUnit *SuccDep = D.getSUnit();
    1059        9405 :     D.setSUnit(SU);
    1060        9405 :     RemovePred(SuccDep, D);
    1061        9405 :     if (isNewLoad) {
    1062        9405 :       D.setSUnit(LoadSU);
    1063        9405 :       AddPred(SuccDep, D);
    1064             :     }
    1065             :   }
    1066             : 
    1067             :   // Add a data dependency to reflect that NewSU reads the value defined
    1068             :   // by LoadSU.
    1069        6199 :   SDep D(LoadSU, SDep::Data, 0);
    1070       12398 :   D.setLatency(LoadSU->Latency);
    1071        6199 :   AddPred(NewSU, D);
    1072             : 
    1073        6199 :   if (isNewLoad)
    1074        6199 :     AvailableQueue->addNode(LoadSU);
    1075        6199 :   AvailableQueue->addNode(NewSU);
    1076             : 
    1077        6199 :   ++NumUnfolds;
    1078             : 
    1079        6199 :   if (NewSU->NumSuccsLeft == 0)
    1080          39 :     NewSU->isAvailable = true;
    1081             : 
    1082        6199 :   return NewSU;
    1083             : }
    1084             : 
    1085             : /// CopyAndMoveSuccessors - Clone the specified node and move its scheduled
    1086             : /// successors to the newly created node.
    1087       19241 : SUnit *ScheduleDAGRRList::CopyAndMoveSuccessors(SUnit *SU) {
    1088       19241 :   SDNode *N = SU->getNode();
    1089       19241 :   if (!N)
    1090             :     return nullptr;
    1091             : 
    1092       19241 :   if (SU->getNode()->getGluedNode())
    1093             :     return nullptr;
    1094             : 
    1095             :   SUnit *NewSU;
    1096       19155 :   bool TryUnfold = false;
    1097       69880 :   for (unsigned i = 0, e = N->getNumValues(); i != e; ++i) {
    1098       31570 :     MVT VT = N->getSimpleValueType(i);
    1099       31570 :     if (VT == MVT::Glue)
    1100             :       return nullptr;
    1101       31570 :     else if (VT == MVT::Other)
    1102        6211 :       TryUnfold = true;
    1103             :   }
    1104      177020 :   for (const SDValue &Op : N->op_values()) {
    1105      138710 :     MVT VT = Op.getNode()->getSimpleValueType(Op.getResNo());
    1106       69355 :     if (VT == MVT::Glue)
    1107             :       return nullptr;
    1108             :   }
    1109             : 
    1110             :   // If possible unfold instruction.
    1111       19155 :   if (TryUnfold) {
    1112        6211 :     SUnit *UnfoldSU = TryUnfoldSU(SU);
    1113        6211 :     if (!UnfoldSU)
    1114             :       return nullptr;
    1115        6200 :     SU = UnfoldSU;
    1116        6200 :     N = SU->getNode();
    1117             :     // If this can be scheduled don't bother duplicating and just return
    1118        6200 :     if (SU->NumSuccsLeft == 0)
    1119             :       return SU;
    1120             :   }
    1121             : 
    1122             :   DEBUG(dbgs() << "    Duplicating SU #" << SU->NodeNum << "\n");
    1123       19105 :   NewSU = CreateClone(SU);
    1124             : 
    1125             :   // New SUnit has the exact same predecessors.
    1126       80076 :   for (SDep &Pred : SU->Preds)
    1127       22761 :     if (!Pred.isArtificial())
    1128       22761 :       AddPred(NewSU, Pred);
    1129             : 
    1130             :   // Only copy scheduled successors. Cut them from old node's successor
    1131             :   // list and move them over.
    1132       19105 :   SmallVector<std::pair<SUnit *, SDep>, 4> DelDeps;
    1133       95869 :   for (SDep &Succ : SU->Succs) {
    1134       38554 :     if (Succ.isArtificial())
    1135           0 :       continue;
    1136       38554 :     SUnit *SuccSU = Succ.getSUnit();
    1137       38554 :     if (SuccSU->isScheduled) {
    1138       19149 :       SDep D = Succ;
    1139       19149 :       D.setSUnit(NewSU);
    1140       19149 :       AddPred(SuccSU, D);
    1141       19149 :       D.setSUnit(SU);
    1142       38298 :       DelDeps.push_back(std::make_pair(SuccSU, D));
    1143             :     }
    1144             :   }
    1145       76464 :   for (auto &DelDep : DelDeps)
    1146       19149 :     RemovePred(DelDep.first, DelDep.second);
    1147             : 
    1148       19105 :   AvailableQueue->updateNode(SU);
    1149       19105 :   AvailableQueue->addNode(NewSU);
    1150             : 
    1151       19105 :   ++NumDups;
    1152       19105 :   return NewSU;
    1153             : }
    1154             : 
    1155             : /// InsertCopiesAndMoveSuccs - Insert register copies and move all
    1156             : /// scheduled successors of the given SUnit to the last copy.
    1157          97 : void ScheduleDAGRRList::InsertCopiesAndMoveSuccs(SUnit *SU, unsigned Reg,
    1158             :                                               const TargetRegisterClass *DestRC,
    1159             :                                               const TargetRegisterClass *SrcRC,
    1160             :                                               SmallVectorImpl<SUnit*> &Copies) {
    1161          97 :   SUnit *CopyFromSU = CreateNewSUnit(nullptr);
    1162          97 :   CopyFromSU->CopySrcRC = SrcRC;
    1163          97 :   CopyFromSU->CopyDstRC = DestRC;
    1164             : 
    1165          97 :   SUnit *CopyToSU = CreateNewSUnit(nullptr);
    1166          97 :   CopyToSU->CopySrcRC = DestRC;
    1167          97 :   CopyToSU->CopyDstRC = SrcRC;
    1168             : 
    1169             :   // Only copy scheduled successors. Cut them from old node's successor
    1170             :   // list and move them over.
    1171         194 :   SmallVector<std::pair<SUnit *, SDep>, 4> DelDeps;
    1172         707 :   for (SDep &Succ : SU->Succs) {
    1173         416 :     if (Succ.isArtificial())
    1174           0 :       continue;
    1175         416 :     SUnit *SuccSU = Succ.getSUnit();
    1176         416 :     if (SuccSU->isScheduled) {
    1177         212 :       SDep D = Succ;
    1178         424 :       D.setSUnit(CopyToSU);
    1179         212 :       AddPred(SuccSU, D);
    1180         424 :       DelDeps.push_back(std::make_pair(SuccSU, Succ));
    1181             :     }
    1182             :     else {
    1183             :       // Avoid scheduling the def-side copy before other successors. Otherwise
    1184             :       // we could introduce another physreg interference on the copy and
    1185             :       // continue inserting copies indefinitely.
    1186         408 :       AddPred(SuccSU, SDep(CopyFromSU, SDep::Artificial));
    1187             :     }
    1188             :   }
    1189         503 :   for (auto &DelDep : DelDeps)
    1190         212 :     RemovePred(DelDep.first, DelDep.second);
    1191             : 
    1192          97 :   SDep FromDep(SU, SDep::Data, Reg);
    1193         194 :   FromDep.setLatency(SU->Latency);
    1194          97 :   AddPred(CopyFromSU, FromDep);
    1195         194 :   SDep ToDep(CopyFromSU, SDep::Data, 0);
    1196         194 :   ToDep.setLatency(CopyFromSU->Latency);
    1197          97 :   AddPred(CopyToSU, ToDep);
    1198             : 
    1199          97 :   AvailableQueue->updateNode(SU);
    1200          97 :   AvailableQueue->addNode(CopyFromSU);
    1201          97 :   AvailableQueue->addNode(CopyToSU);
    1202          97 :   Copies.push_back(CopyFromSU);
    1203          97 :   Copies.push_back(CopyToSU);
    1204             : 
    1205          97 :   ++NumPRCopies;
    1206          97 : }
    1207             : 
    1208             : /// getPhysicalRegisterVT - Returns the ValueType of the physical register
    1209             : /// definition of the specified node.
    1210             : /// FIXME: Move to SelectionDAG?
    1211       19241 : static MVT getPhysicalRegisterVT(SDNode *N, unsigned Reg,
    1212             :                                  const TargetInstrInfo *TII) {
    1213             :   unsigned NumRes;
    1214       38482 :   if (N->getOpcode() == ISD::CopyFromReg) {
    1215             :     // CopyFromReg has: "chain, Val, glue" so operand 1 gives the type.
    1216             :     NumRes = 1;
    1217             :   } else {
    1218       57561 :     const MCInstrDesc &MCID = TII->get(N->getMachineOpcode());
    1219             :     assert(MCID.ImplicitDefs && "Physical reg def must be in implicit def list!");
    1220       19187 :     NumRes = MCID.getNumDefs();
    1221       19189 :     for (const MCPhysReg *ImpDef = MCID.getImplicitDefs(); *ImpDef; ++ImpDef) {
    1222       19189 :       if (Reg == *ImpDef)
    1223             :         break;
    1224           2 :       ++NumRes;
    1225             :     }
    1226             :   }
    1227       19241 :   return N->getSimpleValueType(NumRes);
    1228             : }
    1229             : 
    1230             : /// CheckForLiveRegDef - Return true and update live register vector if the
    1231             : /// specified register def of the specified SUnit clobbers any "live" registers.
    1232      553523 : static void CheckForLiveRegDef(SUnit *SU, unsigned Reg,
    1233             :                                SUnit **LiveRegDefs,
    1234             :                                SmallSet<unsigned, 4> &RegAdded,
    1235             :                                SmallVectorImpl<unsigned> &LRegs,
    1236             :                                const TargetRegisterInfo *TRI) {
    1237     3322586 :   for (MCRegAliasIterator AliasI(Reg, TRI, true); AliasI.isValid(); ++AliasI) {
    1238             : 
    1239             :     // Check if Ref is live.
    1240     1107770 :     if (!LiveRegDefs[*AliasI]) continue;
    1241             : 
    1242             :     // Allow multiple uses of the same def.
    1243      165612 :     if (LiveRegDefs[*AliasI] == SU) continue;
    1244             : 
    1245             :     // Add Reg to the set of interfering live regs.
    1246       38488 :     if (RegAdded.insert(*AliasI).second) {
    1247       51874 :       LRegs.push_back(*AliasI);
    1248             :     }
    1249             :   }
    1250      553523 : }
    1251             : 
    1252             : /// CheckForLiveRegDefMasked - Check for any live physregs that are clobbered
    1253             : /// by RegMask, and add them to LRegs.
    1254        5393 : static void CheckForLiveRegDefMasked(SUnit *SU, const uint32_t *RegMask,
    1255             :                                      ArrayRef<SUnit*> LiveRegDefs,
    1256             :                                      SmallSet<unsigned, 4> &RegAdded,
    1257             :                                      SmallVectorImpl<unsigned> &LRegs) {
    1258             :   // Look at all live registers. Skip Reg0 and the special CallResource.
    1259     1335907 :   for (unsigned i = 1, e = LiveRegDefs.size()-1; i != e; ++i) {
    1260     2661028 :     if (!LiveRegDefs[i]) continue;
    1261         186 :     if (LiveRegDefs[i] == SU) continue;
    1262         372 :     if (!MachineOperand::clobbersPhysReg(RegMask, i)) continue;
    1263         186 :     if (RegAdded.insert(i).second)
    1264           7 :       LRegs.push_back(i);
    1265             :   }
    1266        5393 : }
    1267             : 
    1268             : /// getNodeRegMask - Returns the register mask attached to an SDNode, if any.
    1269             : static const uint32_t *getNodeRegMask(const SDNode *N) {
    1270     9219429 :   for (const SDValue &Op : N->op_values())
    1271     3828227 :     if (const auto *RegOp = dyn_cast<RegisterMaskSDNode>(Op.getNode()))
    1272        5393 :       return RegOp->getRegMask();
    1273             :   return nullptr;
    1274             : }
    1275             : 
    1276             : /// DelayForLiveRegsBottomUp - Returns true if it is necessary to delay
    1277             : /// scheduling of the given node to satisfy live physical register dependencies.
    1278             : /// If the specific node is the last one that's available to schedule, do
    1279             : /// whatever is necessary (i.e. backtracking or cloning) to make it possible.
    1280     3619825 : bool ScheduleDAGRRList::
    1281             : DelayForLiveRegsBottomUp(SUnit *SU, SmallVectorImpl<unsigned> &LRegs) {
    1282     3619825 :   if (NumLiveRegs == 0)
    1283             :     return false;
    1284             : 
    1285     1901002 :   SmallSet<unsigned, 4> RegAdded;
    1286             :   // If this node would clobber any "live" register, then it's not ready.
    1287             :   //
    1288             :   // If SU is the currently live definition of the same register that it uses,
    1289             :   // then we are free to schedule it.
    1290     3951145 :   for (SDep &Pred : SU->Preds) {
    1291       77228 :     if (Pred.isAssignedRegDep() && LiveRegDefs[Pred.getReg()] != SU)
    1292       66426 :       CheckForLiveRegDef(Pred.getSUnit(), Pred.getReg(), LiveRegDefs.get(),
    1293             :                          RegAdded, LRegs, TRI);
    1294             :   }
    1295             : 
    1296      950501 :   for (SDNode *Node = SU->getNode(); Node; Node = Node->getGluedNode()) {
    1297     2004970 :     if (Node->getOpcode() == ISD::INLINEASM) {
    1298             :       // Inline asm can clobber physical defs.
    1299           6 :       unsigned NumOps = Node->getNumOperands();
    1300          12 :       if (Node->getOperand(NumOps-1).getValueType() == MVT::Glue)
    1301           0 :         --NumOps;  // Ignore the glue operand.
    1302             : 
    1303           3 :       for (unsigned i = InlineAsm::Op_FirstOperand; i != NumOps;) {
    1304             :         unsigned Flags =
    1305          32 :           cast<ConstantSDNode>(Node->getOperand(i))->getZExtValue();
    1306           8 :         unsigned NumVals = InlineAsm::getNumOperandRegisters(Flags);
    1307             : 
    1308           8 :         ++i; // Skip the ID value.
    1309          13 :         if (InlineAsm::isRegDefKind(Flags) ||
    1310          18 :             InlineAsm::isRegDefEarlyClobberKind(Flags) ||
    1311           5 :             InlineAsm::isClobberKind(Flags)) {
    1312             :           // Check for def of register or earlyclobber register.
    1313          18 :           for (; NumVals; --NumVals, ++i) {
    1314          18 :             unsigned Reg = cast<RegisterSDNode>(Node->getOperand(i))->getReg();
    1315           6 :             if (TargetRegisterInfo::isPhysicalRegister(Reg))
    1316           6 :               CheckForLiveRegDef(SU, Reg, LiveRegDefs.get(), RegAdded, LRegs, TRI);
    1317             :           }
    1318             :         } else
    1319           2 :           i += NumVals;
    1320             :       }
    1321           3 :       continue;
    1322             :     }
    1323             : 
    1324     1002482 :     if (!Node->isMachineOpcode())
    1325      212905 :       continue;
    1326             :     // If we're in the middle of scheduling a call, don't begin scheduling
    1327             :     // another call. Also, don't allow any physical registers to be live across
    1328             :     // the call.
    1329     1579154 :     if (Node->getMachineOpcode() == TII->getCallFrameDestroyOpcode()) {
    1330             :       // Check the special calling-sequence resource.
    1331        5398 :       unsigned CallResource = TRI->getNumRegs();
    1332       10796 :       if (LiveRegDefs[CallResource]) {
    1333       10426 :         SDNode *Gen = LiveRegGens[CallResource]->getNode();
    1334             :         while (SDNode *Glued = Gen->getGluedNode())
    1335             :           Gen = Glued;
    1336       10423 :         if (!IsChainDependent(Gen, Node, 0, TII) &&
    1337        5210 :             RegAdded.insert(CallResource).second)
    1338        5210 :           LRegs.push_back(CallResource);
    1339             :       }
    1340             :     }
    1341      789577 :     if (const uint32_t *RegMask = getNodeRegMask(Node))
    1342       10786 :       CheckForLiveRegDefMasked(SU, RegMask,
    1343       16179 :                                makeArrayRef(LiveRegDefs.get(), TRI->getNumRegs()),
    1344             :                                RegAdded, LRegs);
    1345             : 
    1346     2368731 :     const MCInstrDesc &MCID = TII->get(Node->getMachineOpcode());
    1347      789577 :     if (MCID.hasOptionalDef()) {
    1348             :       // Most ARM instructions have an OptionalDef for CPSR, to model the S-bit.
    1349             :       // This operand can be either a def of CPSR, if the S bit is set; or a use
    1350             :       // of %noreg.  When the OptionalDef is set to a valid register, we need to
    1351             :       // handle it in the same way as an ImplicitDef.
    1352       10370 :       for (unsigned i = 0; i < MCID.getNumDefs(); ++i)
    1353        3577 :         if (MCID.OpInfo[i].isOptionalDef()) {
    1354        1083 :           const SDValue &OptionalDef = Node->getOperand(i - Node->getNumValues());
    1355         361 :           unsigned Reg = cast<RegisterSDNode>(OptionalDef)->getReg();
    1356         722 :           CheckForLiveRegDef(SU, Reg, LiveRegDefs.get(), RegAdded, LRegs, TRI);
    1357             :         }
    1358             :     }
    1359      789577 :     if (!MCID.ImplicitDefs)
    1360      437917 :       continue;
    1361     1413694 :     for (const MCPhysReg *Reg = MCID.getImplicitDefs(); *Reg; ++Reg)
    1362     1062034 :       CheckForLiveRegDef(SU, *Reg, LiveRegDefs.get(), RegAdded, LRegs, TRI);
    1363             :   }
    1364             : 
    1365      950501 :   return !LRegs.empty();
    1366             : }
    1367             : 
    1368      335545 : void ScheduleDAGRRList::releaseInterferences(unsigned Reg) {
    1369             :   // Add the nodes that aren't ready back onto the available list.
    1370      671090 :   for (unsigned i = Interferences.size(); i > 0; --i) {
    1371     2084230 :     SUnit *SU = Interferences[i-1];
    1372     1042115 :     LRegsMapT::iterator LRegsPos = LRegsMap.find(SU);
    1373     1042115 :     if (Reg) {
    1374     1042115 :       SmallVectorImpl<unsigned> &LRegs = LRegsPos->second;
    1375     1042115 :       if (!is_contained(LRegs, Reg))
    1376     1010963 :         continue;
    1377             :     }
    1378       31152 :     SU->isPending = false;
    1379             :     // The interfering node may no longer be available due to backtracking.
    1380             :     // Furthermore, it may have been made available again, in which case it is
    1381             :     // now already in the AvailableQueue.
    1382       31152 :     if (SU->isAvailable && !SU->NodeQueueId) {
    1383             :       DEBUG(dbgs() << "    Repushing SU #" << SU->NodeNum << '\n');
    1384        7192 :       AvailableQueue->push(SU);
    1385             :     }
    1386       62304 :     if (i < Interferences.size())
    1387           0 :       Interferences[i-1] = Interferences.back();
    1388       62304 :     Interferences.pop_back();
    1389       62304 :     LRegsMap.erase(LRegsPos);
    1390             :   }
    1391      335545 : }
    1392             : 
    1393             : /// Return a node that can be scheduled in this cycle. Requirements:
    1394             : /// (1) Ready: latency has been satisfied
    1395             : /// (2) No Hazards: resources are available
    1396             : /// (3) No Interferences: may unschedule to break register interferences.
    1397     3607914 : SUnit *ScheduleDAGRRList::PickNodeToScheduleBottomUp() {
    1398     3607914 :   SUnit *CurSU = AvailableQueue->empty() ? nullptr : AvailableQueue->pop();
    1399     3608535 :   auto FindAvailableNode = [&]() {
    1400     3764295 :     while (CurSU) {
    1401     3650977 :       SmallVector<unsigned, 4> LRegs;
    1402     3682129 :       if (!DelayForLiveRegsBottomUp(CurSU, LRegs))
    1403             :         break;
    1404             :       DEBUG(dbgs() << "    Interfering reg " <<
    1405             :             (LRegs[0] == TRI->getNumRegs() ? "CallResource"
    1406             :              : TRI->getName(LRegs[0]))
    1407             :              << " SU #" << CurSU->NodeNum << '\n');
    1408             :       std::pair<LRegsMapT::iterator, bool> LRegsPair =
    1409      155760 :         LRegsMap.insert(std::make_pair(CurSU, LRegs));
    1410       31152 :       if (LRegsPair.second) {
    1411       31152 :         CurSU->isPending = true;  // This SU is not in AvailableQueue right now.
    1412       62304 :         Interferences.push_back(CurSU);
    1413             :       }
    1414             :       else {
    1415             :         assert(CurSU->isPending && "Interferences are pending");
    1416             :         // Update the interference with current live regs.
    1417           0 :         LRegsPair.first->second = LRegs;
    1418             :       }
    1419       62304 :       CurSU = AvailableQueue->pop();
    1420             :     }
    1421     7216449 :   };
    1422     3607914 :   FindAvailableNode();
    1423     3607914 :   if (CurSU)
    1424             :     return CurSU;
    1425             : 
    1426             :   // All candidates are delayed due to live physical reg dependencies.
    1427             :   // Try backtracking, code duplication, or inserting cross class copies
    1428             :   // to resolve it.
    1429       81236 :   for (SUnit *TrySU : Interferences) {
    1430       44542 :     SmallVectorImpl<unsigned> &LRegs = LRegsMap[TrySU];
    1431             : 
    1432             :     // Try unscheduling up to the point where it's safe to schedule
    1433             :     // this node.
    1434       22271 :     SUnit *BtSU = nullptr;
    1435       22271 :     unsigned LiveCycle = UINT_MAX;
    1436       89084 :     for (unsigned Reg : LRegs) {
    1437       66813 :       if (LiveRegGens[Reg]->getHeight() < LiveCycle) {
    1438       44542 :         BtSU = LiveRegGens[Reg];
    1439       22271 :         LiveCycle = BtSU->getHeight();
    1440             :       }
    1441             :     }
    1442       44542 :     if (!WillCreateCycle(TrySU, BtSU))  {
    1443             :       // BacktrackBottomUp mutates Interferences!
    1444         621 :       BacktrackBottomUp(TrySU, BtSU);
    1445             : 
    1446             :       // Force the current node to be scheduled before the node that
    1447             :       // requires the physical reg dep.
    1448         621 :       if (BtSU->isAvailable) {
    1449         621 :         BtSU->isAvailable = false;
    1450         621 :         if (!BtSU->isPending)
    1451         621 :           AvailableQueue->remove(BtSU);
    1452             :       }
    1453             :       DEBUG(dbgs() << "ARTIFICIAL edge from SU(" << BtSU->NodeNum << ") to SU("
    1454             :             << TrySU->NodeNum << ")\n");
    1455         621 :       AddPred(TrySU, SDep(BtSU, SDep::Artificial));
    1456             : 
    1457             :       // If one or more successors has been unscheduled, then the current
    1458             :       // node is no longer available.
    1459         621 :       if (!TrySU->isAvailable || !TrySU->NodeQueueId) {
    1460             :         DEBUG(dbgs() << "TrySU not available; choosing node from queue\n");
    1461         249 :         CurSU = AvailableQueue->pop();
    1462             :       } else {
    1463             :         DEBUG(dbgs() << "TrySU available\n");
    1464             :         // Available and in AvailableQueue
    1465         372 :         AvailableQueue->remove(TrySU);
    1466         372 :         CurSU = TrySU;
    1467             :       }
    1468         621 :       FindAvailableNode();
    1469             :       // Interferences has been mutated. We must break.
    1470         621 :       break;
    1471             :     }
    1472             :   }
    1473             : 
    1474       19862 :   if (!CurSU) {
    1475             :     // Can't backtrack. If it's too expensive to copy the value, then try
    1476             :     // duplicate the nodes that produces these "too expensive to copy"
    1477             :     // values to break the dependency. In case even that doesn't work,
    1478             :     // insert cross class copies.
    1479             :     // If it's not too expensive, i.e. cost != -1, issue copies.
    1480       38482 :     SUnit *TrySU = Interferences[0];
    1481       38482 :     SmallVectorImpl<unsigned> &LRegs = LRegsMap[TrySU];
    1482             :     assert(LRegs.size() == 1 && "Can't handle this yet!");
    1483       38482 :     unsigned Reg = LRegs[0];
    1484       38482 :     SUnit *LRDef = LiveRegDefs[Reg];
    1485       19241 :     MVT VT = getPhysicalRegisterVT(LRDef->getNode(), Reg, TII);
    1486             :     const TargetRegisterClass *RC =
    1487       19241 :       TRI->getMinimalPhysRegClass(Reg, VT);
    1488       19241 :     const TargetRegisterClass *DestRC = TRI->getCrossCopyRegClass(RC);
    1489             : 
    1490             :     // If cross copy register class is the same as RC, then it must be possible
    1491             :     // copy the value directly. Do not try duplicate the def.
    1492             :     // If cross copy register class is not the same as RC, then it's possible to
    1493             :     // copy the value but it require cross register class copies and it is
    1494             :     // expensive.
    1495             :     // If cross copy register class is null, then it's not possible to copy
    1496             :     // the value at all.
    1497       19241 :     SUnit *NewDef = nullptr;
    1498       19241 :     if (DestRC != RC) {
    1499       19241 :       NewDef = CopyAndMoveSuccessors(LRDef);
    1500       19241 :       if (!DestRC && !NewDef)
    1501           0 :         report_fatal_error("Can't handle live physical register dependency!");
    1502             :     }
    1503       19241 :     if (!NewDef) {
    1504             :       // Issue copies, these can be expensive cross register class copies.
    1505         194 :       SmallVector<SUnit*, 2> Copies;
    1506          97 :       InsertCopiesAndMoveSuccs(LRDef, Reg, DestRC, RC, Copies);
    1507             :       DEBUG(dbgs() << "    Adding an edge from SU #" << TrySU->NodeNum
    1508             :             << " to SU #" << Copies.front()->NodeNum << "\n");
    1509         291 :       AddPred(TrySU, SDep(Copies.front(), SDep::Artificial));
    1510         194 :       NewDef = Copies.back();
    1511             :     }
    1512             : 
    1513             :     DEBUG(dbgs() << "    Adding an edge from SU #" << NewDef->NodeNum
    1514             :           << " to SU #" << TrySU->NodeNum << "\n");
    1515       38482 :     LiveRegDefs[Reg] = NewDef;
    1516       38482 :     AddPred(NewDef, SDep(TrySU, SDep::Artificial));
    1517       19241 :     TrySU->isAvailable = false;
    1518       19241 :     CurSU = NewDef;
    1519             :   }
    1520             :   assert(CurSU && "Unable to resolve live physical register dependencies!");
    1521       19862 :   return CurSU;
    1522             : }
    1523             : 
    1524             : /// ListScheduleBottomUp - The main loop of list scheduling for bottom-up
    1525             : /// schedulers.
    1526      279964 : void ScheduleDAGRRList::ListScheduleBottomUp() {
    1527             :   // Release any predecessors of the special Exit node.
    1528      279964 :   ReleasePredecessors(&ExitSU);
    1529             : 
    1530             :   // Add root to Available queue.
    1531      559928 :   if (!SUnits.empty()) {
    1532      554460 :     SUnit *RootSU = &SUnits[DAG->getRoot().getNode()->getNodeId()];
    1533             :     assert(RootSU->Succs.empty() && "Graph root shouldn't have successors!");
    1534      277230 :     RootSU->isAvailable = true;
    1535      277230 :     AvailableQueue->push(RootSU);
    1536             :   }
    1537             : 
    1538             :   // While Available queue is not empty, grab the node with the highest
    1539             :   // priority. If it is not ready put it back.  Schedule the node.
    1540      559928 :   Sequence.reserve(SUnits.size());
    1541     3887878 :   while (!AvailableQueue->empty() || !Interferences.empty()) {
    1542             :     DEBUG(dbgs() << "\nExamining Available:\n";
    1543             :           AvailableQueue->dump(this));
    1544             : 
    1545             :     // Pick the best node to schedule taking all constraints into
    1546             :     // consideration.
    1547     3607914 :     SUnit *SU = PickNodeToScheduleBottomUp();
    1548             : 
    1549     3607914 :     AdvancePastStalls(SU);
    1550             : 
    1551     3607914 :     ScheduleNodeBottomUp(SU);
    1552             : 
    1553     3896978 :     while (AvailableQueue->empty() && !PendingQueue.empty()) {
    1554             :       // Advance the cycle to free resources. Skip ahead to the next ready SU.
    1555             :       assert(MinAvailableCycle < UINT_MAX && "MinAvailableCycle uninitialized");
    1556           0 :       AdvanceToCycle(std::max(CurCycle + 1, MinAvailableCycle));
    1557             :     }
    1558             :   }
    1559             : 
    1560             :   // Reverse the order if it is bottom up.
    1561     1119856 :   std::reverse(Sequence.begin(), Sequence.end());
    1562             : 
    1563             : #ifndef NDEBUG
    1564             :   VerifyScheduledSequence(/*isBottomUp=*/true);
    1565             : #endif
    1566      279964 : }
    1567             : 
    1568             : //===----------------------------------------------------------------------===//
    1569             : //                RegReductionPriorityQueue Definition
    1570             : //===----------------------------------------------------------------------===//
    1571             : //
    1572             : // This is a SchedulingPriorityQueue that schedules using Sethi Ullman numbers
    1573             : // to reduce register pressure.
    1574             : //
    1575             : namespace {
    1576             : class RegReductionPQBase;
    1577             : 
    1578             : struct queue_sort : public std::binary_function<SUnit*, SUnit*, bool> {
    1579             :   bool isReady(SUnit* SU, unsigned CurCycle) const { return true; }
    1580             : };
    1581             : 
    1582             : #ifndef NDEBUG
    1583             : template<class SF>
    1584             : struct reverse_sort : public queue_sort {
    1585             :   SF &SortFunc;
    1586             :   reverse_sort(SF &sf) : SortFunc(sf) {}
    1587             : 
    1588             :   bool operator()(SUnit* left, SUnit* right) const {
    1589             :     // reverse left/right rather than simply !SortFunc(left, right)
    1590             :     // to expose different paths in the comparison logic.
    1591             :     return SortFunc(right, left);
    1592             :   }
    1593             : };
    1594             : #endif // NDEBUG
    1595             : 
    1596             : /// bu_ls_rr_sort - Priority function for bottom up register pressure
    1597             : // reduction scheduler.
    1598             : struct bu_ls_rr_sort : public queue_sort {
    1599             :   enum {
    1600             :     IsBottomUp = true,
    1601             :     HasReadyFilter = false
    1602             :   };
    1603             : 
    1604             :   RegReductionPQBase *SPQ;
    1605       12406 :   bu_ls_rr_sort(RegReductionPQBase *spq) : SPQ(spq) {}
    1606             : 
    1607             :   bool operator()(SUnit* left, SUnit* right) const;
    1608             : };
    1609             : 
    1610             : // src_ls_rr_sort - Priority function for source order scheduler.
    1611             : struct src_ls_rr_sort : public queue_sort {
    1612             :   enum {
    1613             :     IsBottomUp = true,
    1614             :     HasReadyFilter = false
    1615             :   };
    1616             : 
    1617             :   RegReductionPQBase *SPQ;
    1618             :   src_ls_rr_sort(RegReductionPQBase *spq)
    1619      240509 :     : SPQ(spq) {}
    1620             : 
    1621             :   bool operator()(SUnit* left, SUnit* right) const;
    1622             : };
    1623             : 
    1624             : // hybrid_ls_rr_sort - Priority function for hybrid scheduler.
    1625             : struct hybrid_ls_rr_sort : public queue_sort {
    1626             :   enum {
    1627             :     IsBottomUp = true,
    1628             :     HasReadyFilter = false
    1629             :   };
    1630             : 
    1631             :   RegReductionPQBase *SPQ;
    1632             :   hybrid_ls_rr_sort(RegReductionPQBase *spq)
    1633       11742 :     : SPQ(spq) {}
    1634             : 
    1635             :   bool isReady(SUnit *SU, unsigned CurCycle) const;
    1636             : 
    1637             :   bool operator()(SUnit* left, SUnit* right) const;
    1638             : };
    1639             : 
    1640             : // ilp_ls_rr_sort - Priority function for ILP (instruction level parallelism)
    1641             : // scheduler.
    1642             : struct ilp_ls_rr_sort : public queue_sort {
    1643             :   enum {
    1644             :     IsBottomUp = true,
    1645             :     HasReadyFilter = false
    1646             :   };
    1647             : 
    1648             :   RegReductionPQBase *SPQ;
    1649             :   ilp_ls_rr_sort(RegReductionPQBase *spq)
    1650       15307 :     : SPQ(spq) {}
    1651             : 
    1652             :   bool isReady(SUnit *SU, unsigned CurCycle) const;
    1653             : 
    1654             :   bool operator()(SUnit* left, SUnit* right) const;
    1655             : };
    1656             : 
    1657     1399820 : class RegReductionPQBase : public SchedulingPriorityQueue {
    1658             : protected:
    1659             :   std::vector<SUnit*> Queue;
    1660             :   unsigned CurQueueId;
    1661             :   bool TracksRegPressure;
    1662             :   bool SrcOrder;
    1663             : 
    1664             :   // SUnits - The SUnits for the current graph.
    1665             :   std::vector<SUnit> *SUnits;
    1666             : 
    1667             :   MachineFunction &MF;
    1668             :   const TargetInstrInfo *TII;
    1669             :   const TargetRegisterInfo *TRI;
    1670             :   const TargetLowering *TLI;
    1671             :   ScheduleDAGRRList *scheduleDAG;
    1672             : 
    1673             :   // SethiUllmanNumbers - The SethiUllman number for each node.
    1674             :   std::vector<unsigned> SethiUllmanNumbers;
    1675             : 
    1676             :   /// RegPressure - Tracking current reg pressure per register class.
    1677             :   ///
    1678             :   std::vector<unsigned> RegPressure;
    1679             : 
    1680             :   /// RegLimit - Tracking the number of allocatable registers per register
    1681             :   /// class.
    1682             :   std::vector<unsigned> RegLimit;
    1683             : 
    1684             : public:
    1685      279964 :   RegReductionPQBase(MachineFunction &mf,
    1686             :                      bool hasReadyFilter,
    1687             :                      bool tracksrp,
    1688             :                      bool srcorder,
    1689             :                      const TargetInstrInfo *tii,
    1690             :                      const TargetRegisterInfo *tri,
    1691             :                      const TargetLowering *tli)
    1692      279964 :     : SchedulingPriorityQueue(hasReadyFilter),
    1693             :       CurQueueId(0), TracksRegPressure(tracksrp), SrcOrder(srcorder),
    1694     1679784 :       MF(mf), TII(tii), TRI(tri), TLI(tli), scheduleDAG(nullptr) {
    1695      279964 :     if (TracksRegPressure) {
    1696       54098 :       unsigned NumRC = TRI->getNumRegClasses();
    1697       27049 :       RegLimit.resize(NumRC);
    1698       27049 :       RegPressure.resize(NumRC);
    1699      108196 :       std::fill(RegLimit.begin(), RegLimit.end(), 0);
    1700      108196 :       std::fill(RegPressure.begin(), RegPressure.end(), 0);
    1701     2192187 :       for (const TargetRegisterClass *RC : TRI->regclasses())
    1702     6414267 :         RegLimit[RC->getID()] = tri->getRegPressureLimit(RC, MF);
    1703             :     }
    1704      279964 :   }
    1705             : 
    1706             :   void setScheduleDAG(ScheduleDAGRRList *scheduleDag) {
    1707      279964 :     scheduleDAG = scheduleDag;
    1708             :   }
    1709             : 
    1710             :   ScheduleHazardRecognizer* getHazardRec() {
    1711     7594975 :     return scheduleDAG->getHazardRec();
    1712             :   }
    1713             : 
    1714             :   void initNodes(std::vector<SUnit> &sunits) override;
    1715             : 
    1716             :   void addNode(const SUnit *SU) override;
    1717             : 
    1718             :   void updateNode(const SUnit *SU) override;
    1719             : 
    1720      279964 :   void releaseState() override {
    1721      279964 :     SUnits = nullptr;
    1722      559928 :     SethiUllmanNumbers.clear();
    1723     1119856 :     std::fill(RegPressure.begin(), RegPressure.end(), 0);
    1724      279964 :   }
    1725             : 
    1726             :   unsigned getNodePriority(const SUnit *SU) const;
    1727             : 
    1728             :   unsigned getNodeOrdering(const SUnit *SU) const {
    1729    27406598 :     if (!SU->getNode()) return 0;
    1730             : 
    1731    27406496 :     return SU->getNode()->getIROrder();
    1732             :   }
    1733             : 
    1734    29373548 :   bool empty() const override { return Queue.empty(); }
    1735             : 
    1736     3656900 :   void push(SUnit *U) override {
    1737             :     assert(!U->NodeQueueId && "Node in the queue already");
    1738     3656900 :     U->NodeQueueId = ++CurQueueId;
    1739     3656900 :     Queue.push_back(U);
    1740     3656900 :   }
    1741             : 
    1742       37447 :   void remove(SUnit *SU) override {
    1743             :     assert(!Queue.empty() && "Queue is empty!");
    1744             :     assert(SU->NodeQueueId != 0 && "Not in queue!");
    1745       74894 :     std::vector<SUnit *>::iterator I = find(Queue, SU);
    1746      149788 :     if (I != std::prev(Queue.end()))
    1747       23438 :       std::swap(*I, Queue.back());
    1748       37447 :     Queue.pop_back();
    1749       37447 :     SU->NodeQueueId = 0;
    1750       37447 :   }
    1751             : 
    1752       12402 :   bool tracksRegPressure() const override { return TracksRegPressure; }
    1753             : 
    1754             :   void dumpRegPressure() const;
    1755             : 
    1756             :   bool HighRegPressure(const SUnit *SU) const;
    1757             : 
    1758             :   bool MayReduceRegPressure(SUnit *SU) const;
    1759             : 
    1760             :   int RegPressureDiff(SUnit *SU, unsigned &LiveUses) const;
    1761             : 
    1762             :   void scheduledNode(SUnit *SU) override;
    1763             : 
    1764             :   void unscheduledNode(SUnit *SU) override;
    1765             : 
    1766             : protected:
    1767             :   bool canClobber(const SUnit *SU, const SUnit *Op);
    1768             :   void AddPseudoTwoAddrDeps();
    1769             :   void PrescheduleNodesWithMultipleUses();
    1770             :   void CalculateSethiUllmanNumbers();
    1771             : };
    1772             : 
    1773             : template<class SF>
    1774     3619453 : static SUnit *popFromQueueImpl(std::vector<SUnit*> &Q, SF &Picker) {
    1775     3619453 :   std::vector<SUnit *>::iterator Best = Q.begin();
    1776    28624081 :   for (auto I = std::next(Q.begin()), E = Q.end(); I != E; ++I)
    1777    14209612 :     if (Picker(*Best, *I))
    1778     3160159 :       Best = I;
    1779     3619453 :   SUnit *V = *Best;
    1780    10858359 :   if (Best != std::prev(Q.end()))
    1781      897078 :     std::swap(*Best, Q.back());
    1782     3619453 :   Q.pop_back();
    1783     3619453 :   return V;
    1784             : }
    1785             : 
    1786             : template<class SF>
    1787             : SUnit *popFromQueue(std::vector<SUnit*> &Q, SF &Picker, ScheduleDAG *DAG) {
    1788             : #ifndef NDEBUG
    1789             :   if (DAG->StressSched) {
    1790             :     reverse_sort<SF> RPicker(Picker);
    1791             :     return popFromQueueImpl(Q, RPicker);
    1792             :   }
    1793             : #endif
    1794             :   (void)DAG;
    1795     3619453 :   return popFromQueueImpl(Q, Picker);
    1796             : }
    1797             : 
    1798             : template<class SF>
    1799      279964 : class RegReductionPriorityQueue : public RegReductionPQBase {
    1800             :   SF Picker;
    1801             : 
    1802             : public:
    1803      279964 :   RegReductionPriorityQueue(MachineFunction &mf,
    1804             :                             bool tracksrp,
    1805             :                             bool srcorder,
    1806             :                             const TargetInstrInfo *tii,
    1807             :                             const TargetRegisterInfo *tri,
    1808             :                             const TargetLowering *tli)
    1809             :     : RegReductionPQBase(mf, SF::HasReadyFilter, tracksrp, srcorder,
    1810             :                          tii, tri, tli),
    1811      559928 :       Picker(this) {}
    1812             : 
    1813           0 :   bool isBottomUp() const override { return SF::IsBottomUp; }
    1814             : 
    1815           0 :   bool isReady(SUnit *U) const override {
    1816           0 :     return Picker.HasReadyFilter && Picker.isReady(U, getCurCycle());
    1817             :   }
    1818             : 
    1819     3627481 :   SUnit *pop() override {
    1820     7254962 :     if (Queue.empty()) return nullptr;
    1821             : 
    1822     7238906 :     SUnit *V = popFromQueue(Queue, Picker, scheduleDAG);
    1823     3619453 :     V->NodeQueueId = 0;
    1824     3619453 :     return V;
    1825             :   }
    1826             : 
    1827             : #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
    1828             :   LLVM_DUMP_METHOD void dump(ScheduleDAG *DAG) const override {
    1829             :     // Emulate pop() without clobbering NodeQueueIds.
    1830             :     std::vector<SUnit*> DumpQueue = Queue;
    1831             :     SF DumpPicker = Picker;
    1832             :     while (!DumpQueue.empty()) {
    1833             :       SUnit *SU = popFromQueue(DumpQueue, DumpPicker, scheduleDAG);
    1834             :       dbgs() << "Height " << SU->getHeight() << ": ";
    1835             :       SU->dump(DAG);
    1836             :     }
    1837             :   }
    1838             : #endif
    1839             : };
    1840             : 
    1841             : typedef RegReductionPriorityQueue<bu_ls_rr_sort>
    1842             : BURegReductionPriorityQueue;
    1843             : 
    1844             : typedef RegReductionPriorityQueue<src_ls_rr_sort>
    1845             : SrcRegReductionPriorityQueue;
    1846             : 
    1847             : typedef RegReductionPriorityQueue<hybrid_ls_rr_sort>
    1848             : HybridBURRPriorityQueue;
    1849             : 
    1850             : typedef RegReductionPriorityQueue<ilp_ls_rr_sort>
    1851             : ILPBURRPriorityQueue;
    1852             : } // end anonymous namespace
    1853             : 
    1854             : //===----------------------------------------------------------------------===//
    1855             : //           Static Node Priority for Register Pressure Reduction
    1856             : //===----------------------------------------------------------------------===//
    1857             : 
    1858             : // Check for special nodes that bypass scheduling heuristics.
    1859             : // Currently this pushes TokenFactor nodes down, but may be used for other
    1860             : // pseudo-ops as well.
    1861             : //
    1862             : // Return -1 to schedule right above left, 1 for left above right.
    1863             : // Return 0 if no bias exists.
    1864             : static int checkSpecialNodes(const SUnit *left, const SUnit *right) {
    1865    14146269 :   bool LSchedLow = left->isScheduleLow;
    1866    14146269 :   bool RSchedLow = right->isScheduleLow;
    1867    14146269 :   if (LSchedLow != RSchedLow)
    1868       77367 :     return LSchedLow < RSchedLow ? 1 : -1;
    1869             :   return 0;
    1870             : }
    1871             : 
    1872             : /// CalcNodeSethiUllmanNumber - Compute Sethi Ullman number.
    1873             : /// Smaller number is the higher priority.
    1874             : static unsigned
    1875     3594905 : CalcNodeSethiUllmanNumber(const SUnit *SU, std::vector<unsigned> &SUNumbers) {
    1876     7189810 :   if (SUNumbers[SU->NodeNum] != 0)
    1877             :     return SUNumbers[SU->NodeNum];
    1878             : 
    1879             :   // Use WorkList to avoid stack overflow on excessively large IRs.
    1880             :   struct WorkState {
    1881     3594905 :     WorkState(const SUnit *SU) : SU(SU) {}
    1882             :     const SUnit *SU;
    1883             :     unsigned PredsProcessed = 0;
    1884             :   };
    1885             : 
    1886     1666833 :   SmallVector<WorkState, 16> WorkList;
    1887     1666833 :   WorkList.push_back(SU);
    1888     7189810 :   while (!WorkList.empty()) {
    1889    11045954 :     auto &Temp = WorkList.back();
    1890     5522977 :     auto *TempSU = Temp.SU;
    1891     5522977 :     bool AllPredsKnown = true;
    1892             :     // Try to find a non-evaluated pred and push it into the processing stack.
    1893    16215388 :     for (unsigned P = Temp.PredsProcessed; P < TempSU->Preds.size(); ++P) {
    1894     9025578 :       auto &Pred = TempSU->Preds[P];
    1895     4512789 :       if (Pred.isCtrl()) continue;  // ignore chain preds
    1896     2608684 :       SUnit *PredSU = Pred.getSUnit();
    1897     5217368 :       if (SUNumbers[PredSU->NodeNum] == 0) {
    1898             : #ifndef NDEBUG
    1899             :         // In debug mode, check that we don't have such element in the stack.
    1900             :         for (auto It : WorkList)
    1901             :           assert(It.SU != PredSU && "Trying to push an element twice?");
    1902             : #endif
    1903             :         // Next time start processing this one starting from the next pred.
    1904     1928072 :         Temp.PredsProcessed = P + 1;
    1905     1928072 :         WorkList.push_back(PredSU);
    1906     1928072 :         AllPredsKnown = false;
    1907             :         break;
    1908             :       }
    1909             :     }
    1910             : 
    1911     1928072 :     if (!AllPredsKnown)
    1912     1928072 :       continue;
    1913             : 
    1914             :     // Once all preds are known, we can calculate the answer for this one.
    1915     3594905 :     unsigned SethiUllmanNumber = 0;
    1916     3594905 :     unsigned Extra = 0;
    1917     8107694 :     for (const SDep &Pred : TempSU->Preds) {
    1918     4512789 :       if (Pred.isCtrl()) continue;  // ignore chain preds
    1919     2608684 :       SUnit *PredSU = Pred.getSUnit();
    1920     5217368 :       unsigned PredSethiUllman = SUNumbers[PredSU->NodeNum];
    1921             :       assert(PredSethiUllman > 0 && "We should have evaluated this pred!");
    1922     2608684 :       if (PredSethiUllman > SethiUllmanNumber) {
    1923             :         SethiUllmanNumber = PredSethiUllman;
    1924             :         Extra = 0;
    1925      742764 :       } else if (PredSethiUllman == SethiUllmanNumber)
    1926      623197 :         ++Extra;
    1927             :     }
    1928             : 
    1929     3594905 :     SethiUllmanNumber += Extra;
    1930     3594905 :     if (SethiUllmanNumber == 0)
    1931     1800458 :       SethiUllmanNumber = 1;
    1932     7189810 :     SUNumbers[TempSU->NodeNum] = SethiUllmanNumber;
    1933             :     WorkList.pop_back();
    1934             :   }
    1935             : 
    1936             :   assert(SUNumbers[SU->NodeNum] > 0 && "SethiUllman should never be zero!");
    1937     3333666 :   return SUNumbers[SU->NodeNum];
    1938             : }
    1939             : 
    1940             : /// CalculateSethiUllmanNumbers - Calculate Sethi-Ullman numbers of all
    1941             : /// scheduling units.
    1942      279964 : void RegReductionPQBase::CalculateSethiUllmanNumbers() {
    1943      839892 :   SethiUllmanNumbers.assign(SUnits->size(), 0);
    1944             : 
    1945     4663862 :   for (const SUnit &SU : *SUnits)
    1946     3544006 :     CalcNodeSethiUllmanNumber(&SU, SethiUllmanNumbers);
    1947      279964 : }
    1948             : 
    1949       31697 : void RegReductionPQBase::addNode(const SUnit *SU) {
    1950       63394 :   unsigned SUSize = SethiUllmanNumbers.size();
    1951       63394 :   if (SUnits->size() > SUSize)
    1952       19117 :     SethiUllmanNumbers.resize(SUSize*2, 0);
    1953       31697 :   CalcNodeSethiUllmanNumber(SU, SethiUllmanNumbers);
    1954       31697 : }
    1955             : 
    1956       19202 : void RegReductionPQBase::updateNode(const SUnit *SU) {
    1957       38404 :   SethiUllmanNumbers[SU->NodeNum] = 0;
    1958       19202 :   CalcNodeSethiUllmanNumber(SU, SethiUllmanNumbers);
    1959       19202 : }
    1960             : 
    1961             : // Lower priority means schedule further down. For bottom-up scheduling, lower
    1962             : // priority SUs are scheduled before higher priority SUs.
    1963    17472084 : unsigned RegReductionPQBase::getNodePriority(const SUnit *SU) const {
    1964             :   assert(SU->NodeNum < SethiUllmanNumbers.size());
    1965    34944168 :   unsigned Opc = SU->getNode() ? SU->getNode()->getOpcode() : 0;
    1966    17472084 :   if (Opc == ISD::TokenFactor || Opc == ISD::CopyToReg)
    1967             :     // CopyToReg should be close to its uses to facilitate coalescing and
    1968             :     // avoid spilling.
    1969             :     return 0;
    1970    34134192 :   if (Opc == TargetOpcode::EXTRACT_SUBREG ||
    1971    34134192 :       Opc == TargetOpcode::SUBREG_TO_REG ||
    1972             :       Opc == TargetOpcode::INSERT_SUBREG)
    1973             :     // EXTRACT_SUBREG, INSERT_SUBREG, and SUBREG_TO_REG nodes should be
    1974             :     // close to their uses to facilitate coalescing.
    1975             :     return 0;
    1976    17067096 :   if (SU->NumSuccs == 0 && SU->NumPreds != 0)
    1977             :     // If SU does not have a register use, i.e. it doesn't produce a value
    1978             :     // that would be consumed (e.g. store), then it terminates a chain of
    1979             :     // computation.  Give it a large SethiUllman number so it will be
    1980             :     // scheduled right before its predecessors that it doesn't lengthen
    1981             :     // their live ranges.
    1982             :     return 0xffff;
    1983    12940086 :   if (SU->NumPreds == 0 && SU->NumSuccs != 0)
    1984             :     // If SU does not have a register def, schedule it close to its uses
    1985             :     // because it does not lengthen any live ranges.
    1986             :     return 0;
    1987             : #if 1
    1988    21854942 :   return SethiUllmanNumbers[SU->NodeNum];
    1989             : #else
    1990             :   unsigned Priority = SethiUllmanNumbers[SU->NodeNum];
    1991             :   if (SU->isCallOp) {
    1992             :     // FIXME: This assumes all of the defs are used as call operands.
    1993             :     int NP = (int)Priority - SU->getNode()->getNumValues();
    1994             :     return (NP > 0) ? NP : 0;
    1995             :   }
    1996             :   return Priority;
    1997             : #endif
    1998             : }
    1999             : 
    2000             : //===----------------------------------------------------------------------===//
    2001             : //                     Register Pressure Tracking
    2002             : //===----------------------------------------------------------------------===//
    2003             : 
    2004             : #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
    2005             : LLVM_DUMP_METHOD void RegReductionPQBase::dumpRegPressure() const {
    2006             :   for (const TargetRegisterClass *RC : TRI->regclasses()) {
    2007             :     unsigned Id = RC->getID();
    2008             :     unsigned RP = RegPressure[Id];
    2009             :     if (!RP) continue;
    2010             :     DEBUG(dbgs() << TRI->getRegClassName(RC) << ": " << RP << " / "
    2011             :           << RegLimit[Id] << '\n');
    2012             :   }
    2013             : }
    2014             : #endif
    2015             : 
    2016      321546 : bool RegReductionPQBase::HighRegPressure(const SUnit *SU) const {
    2017      321546 :   if (!TLI)
    2018             :     return false;
    2019             : 
    2020     1313657 :   for (const SDep &Pred : SU->Preds) {
    2021      368633 :     if (Pred.isCtrl())
    2022       21905 :       continue;
    2023      346728 :     SUnit *PredSU = Pred.getSUnit();
    2024             :     // NumRegDefsLeft is zero when enough uses of this node have been scheduled
    2025             :     // to cover the number of registers defined (they are all live).
    2026      346728 :     if (PredSU->NumRegDefsLeft == 0) {
    2027      144244 :       continue;
    2028             :     }
    2029      410942 :     for (ScheduleDAGSDNodes::RegDefIter RegDefPos(PredSU, scheduleDAG);
    2030      619400 :          RegDefPos.IsValid(); RegDefPos.Advance()) {
    2031             :       unsigned RCId, Cost;
    2032      228072 :       GetCostForDef(RegDefPos, TLI, TII, TRI, RCId, Cost, MF);
    2033             : 
    2034      684216 :       if ((RegPressure[RCId] + Cost) >= RegLimit[RCId])
    2035       19614 :         return true;
    2036             :     }
    2037             :   }
    2038             :   return false;
    2039             : }
    2040             : 
    2041             : bool RegReductionPQBase::MayReduceRegPressure(SUnit *SU) const {
    2042             :   const SDNode *N = SU->getNode();
    2043             : 
    2044             :   if (!N->isMachineOpcode() || !SU->NumSuccs)
    2045             :     return false;
    2046             : 
    2047             :   unsigned NumDefs = TII->get(N->getMachineOpcode()).getNumDefs();
    2048             :   for (unsigned i = 0; i != NumDefs; ++i) {
    2049             :     MVT VT = N->getSimpleValueType(i);
    2050             :     if (!N->hasAnyUseOfValue(i))
    2051             :       continue;
    2052             :     unsigned RCId = TLI->getRepRegClassFor(VT)->getID();
    2053             :     if (RegPressure[RCId] >= RegLimit[RCId])
    2054             :       return true;
    2055             :   }
    2056             :   return false;
    2057             : }
    2058             : 
    2059             : // Compute the register pressure contribution by this instruction by count up
    2060             : // for uses that are not live and down for defs. Only count register classes
    2061             : // that are already under high pressure. As a side effect, compute the number of
    2062             : // uses of registers that are already live.
    2063             : //
    2064             : // FIXME: This encompasses the logic in HighRegPressure and MayReduceRegPressure
    2065             : // so could probably be factored.
    2066      293834 : int RegReductionPQBase::RegPressureDiff(SUnit *SU, unsigned &LiveUses) const {
    2067      293834 :   LiveUses = 0;
    2068      293834 :   int PDiff = 0;
    2069     1192232 :   for (const SDep &Pred : SU->Preds) {
    2070      310730 :     if (Pred.isCtrl())
    2071       26110 :       continue;
    2072      284620 :     SUnit *PredSU = Pred.getSUnit();
    2073             :     // NumRegDefsLeft is zero when enough uses of this node have been scheduled
    2074             :     // to cover the number of registers defined (they are all live).
    2075      352528 :     if (PredSU->NumRegDefsLeft == 0) {
    2076       67908 :       if (PredSU->getNode()->isMachineOpcode())
    2077       56147 :         ++LiveUses;
    2078       67908 :       continue;
    2079             :     }
    2080      433921 :     for (ScheduleDAGSDNodes::RegDefIter RegDefPos(PredSU, scheduleDAG);
    2081      651130 :          RegDefPos.IsValid(); RegDefPos.Advance()) {
    2082      217209 :       MVT VT = RegDefPos.GetValue();
    2083      434418 :       unsigned RCId = TLI->getRepRegClassFor(VT)->getID();
    2084      651627 :       if (RegPressure[RCId] >= RegLimit[RCId])
    2085       82336 :         ++PDiff;
    2086             :     }
    2087             :   }
    2088      293834 :   const SDNode *N = SU->getNode();
    2089             : 
    2090      293834 :   if (!N || !N->isMachineOpcode() || !SU->NumSuccs)
    2091             :     return PDiff;
    2092             : 
    2093      515124 :   unsigned NumDefs = TII->get(N->getMachineOpcode()).getNumDefs();
    2094      257258 :   for (unsigned i = 0; i != NumDefs; ++i) {
    2095      128477 :     MVT VT = N->getSimpleValueType(i);
    2096      128477 :     if (!N->hasAnyUseOfValue(i))
    2097           6 :       continue;
    2098      256942 :     unsigned RCId = TLI->getRepRegClassFor(VT)->getID();
    2099      385413 :     if (RegPressure[RCId] >= RegLimit[RCId])
    2100       25312 :       --PDiff;
    2101             :   }
    2102             :   return PDiff;
    2103             : }
    2104             : 
    2105     3607914 : void RegReductionPQBase::scheduledNode(SUnit *SU) {
    2106     3607914 :   if (!TracksRegPressure)
    2107             :     return;
    2108             : 
    2109      210300 :   if (!SU->getNode())
    2110             :     return;
    2111             : 
    2112      861954 :   for (const SDep &Pred : SU->Preds) {
    2113      231066 :     if (Pred.isCtrl())
    2114       68161 :       continue;
    2115      162905 :     SUnit *PredSU = Pred.getSUnit();
    2116             :     // NumRegDefsLeft is zero when enough uses of this node have been scheduled
    2117             :     // to cover the number of registers defined (they are all live).
    2118      162905 :     if (PredSU->NumRegDefsLeft == 0) {
    2119       24779 :       continue;
    2120             :     }
    2121             :     // FIXME: The ScheduleDAG currently loses information about which of a
    2122             :     // node's values is consumed by each dependence. Consequently, if the node
    2123             :     // defines multiple register classes, we don't know which to pressurize
    2124             :     // here. Instead the following loop consumes the register defs in an
    2125             :     // arbitrary order. At least it handles the common case of clustered loads
    2126             :     // to the same class. For precise liveness, each SDep needs to indicate the
    2127             :     // result number. But that tightly couples the ScheduleDAG with the
    2128             :     // SelectionDAG making updates tricky. A simpler hack would be to attach a
    2129             :     // value type or register class to SDep.
    2130             :     //
    2131             :     // The most important aspect of register tracking is balancing the increase
    2132             :     // here with the reduction further below. Note that this SU may use multiple
    2133             :     // defs in PredSU. The can't be determined here, but we've already
    2134             :     // compensated by reducing NumRegDefsLeft in PredSU during
    2135             :     // ScheduleDAGSDNodes::AddSchedEdges.
    2136      138126 :     --PredSU->NumRegDefsLeft;
    2137      138126 :     unsigned SkipRegDefs = PredSU->NumRegDefsLeft;
    2138      138692 :     for (ScheduleDAGSDNodes::RegDefIter RegDefPos(PredSU, scheduleDAG);
    2139      139258 :          RegDefPos.IsValid(); RegDefPos.Advance(), --SkipRegDefs) {
    2140      138692 :       if (SkipRegDefs)
    2141         566 :         continue;
    2142             : 
    2143             :       unsigned RCId, Cost;
    2144      138126 :       GetCostForDef(RegDefPos, TLI, TII, TRI, RCId, Cost, MF);
    2145      276252 :       RegPressure[RCId] += Cost;
    2146      138126 :       break;
    2147             :     }
    2148             :   }
    2149             : 
    2150             :   // We should have this assert, but there may be dead SDNodes that never
    2151             :   // materialize as SUnits, so they don't appear to generate liveness.
    2152             :   //assert(SU->NumRegDefsLeft == 0 && "not all regdefs have scheduled uses");
    2153      210296 :   int SkipRegDefs = (int)SU->NumRegDefsLeft;
    2154      352088 :   for (ScheduleDAGSDNodes::RegDefIter RegDefPos(SU, scheduleDAG);
    2155      493880 :        RegDefPos.IsValid(); RegDefPos.Advance(), --SkipRegDefs) {
    2156      141792 :     if (SkipRegDefs > 0)
    2157           9 :       continue;
    2158             :     unsigned RCId, Cost;
    2159      141783 :     GetCostForDef(RegDefPos, TLI, TII, TRI, RCId, Cost, MF);
    2160      283566 :     if (RegPressure[RCId] < Cost) {
    2161             :       // Register pressure tracking is imprecise. This can happen. But we try
    2162             :       // hard not to let it happen because it likely results in poor scheduling.
    2163             :       DEBUG(dbgs() << "  SU(" << SU->NodeNum << ") has too many regdefs\n");
    2164        3671 :       RegPressure[RCId] = 0;
    2165             :     }
    2166             :     else {
    2167      138112 :       RegPressure[RCId] -= Cost;
    2168             :     }
    2169             :   }
    2170             :   DEBUG(dumpRegPressure());
    2171             : }
    2172             : 
    2173       38410 : void RegReductionPQBase::unscheduledNode(SUnit *SU) {
    2174       38410 :   if (!TracksRegPressure)
    2175             :     return;
    2176             : 
    2177          77 :   const SDNode *N = SU->getNode();
    2178          77 :   if (!N) return;
    2179             : 
    2180          77 :   if (!N->isMachineOpcode()) {
    2181          10 :     if (N->getOpcode() != ISD::CopyToReg)
    2182             :       return;
    2183             :   } else {
    2184          67 :     unsigned Opc = N->getMachineOpcode();
    2185         134 :     if (Opc == TargetOpcode::EXTRACT_SUBREG ||
    2186          67 :         Opc == TargetOpcode::INSERT_SUBREG ||
    2187          67 :         Opc == TargetOpcode::SUBREG_TO_REG ||
    2188         132 :         Opc == TargetOpcode::REG_SEQUENCE ||
    2189          66 :         Opc == TargetOpcode::IMPLICIT_DEF)
    2190             :       return;
    2191             :   }
    2192             : 
    2193         363 :   for (const SDep &Pred : SU->Preds) {
    2194         165 :     if (Pred.isCtrl())
    2195          25 :       continue;
    2196         140 :     SUnit *PredSU = Pred.getSUnit();
    2197             :     // NumSuccsLeft counts all deps. Don't compare it with NumSuccs which only
    2198             :     // counts data deps.
    2199         280 :     if (PredSU->NumSuccsLeft != PredSU->Succs.size())
    2200          70 :       continue;
    2201          70 :     const SDNode *PN = PredSU->getNode();
    2202          70 :     if (!PN->isMachineOpcode()) {
    2203           6 :       if (PN->getOpcode() == ISD::CopyFromReg) {
    2204           6 :         MVT VT = PN->getSimpleValueType(0);
    2205          12 :         unsigned RCId = TLI->getRepRegClassFor(VT)->getID();
    2206          12 :         RegPressure[RCId] += TLI->getRepRegClassCostFor(VT);
    2207             :       }
    2208           6 :       continue;
    2209             :     }
    2210          64 :     unsigned POpc = PN->getMachineOpcode();
    2211          64 :     if (POpc == TargetOpcode::IMPLICIT_DEF)
    2212           0 :       continue;
    2213         128 :     if (POpc == TargetOpcode::EXTRACT_SUBREG ||
    2214          64 :         POpc == TargetOpcode::INSERT_SUBREG ||
    2215          64 :         POpc == TargetOpcode::SUBREG_TO_REG) {
    2216           2 :       MVT VT = PN->getSimpleValueType(0);
    2217           4 :       unsigned RCId = TLI->getRepRegClassFor(VT)->getID();
    2218           4 :       RegPressure[RCId] += TLI->getRepRegClassCostFor(VT);
    2219           2 :       continue;
    2220             :     }
    2221         186 :     unsigned NumDefs = TII->get(PN->getMachineOpcode()).getNumDefs();
    2222         108 :     for (unsigned i = 0; i != NumDefs; ++i) {
    2223          46 :       MVT VT = PN->getSimpleValueType(i);
    2224          46 :       if (!PN->hasAnyUseOfValue(i))
    2225           3 :         continue;
    2226          86 :       unsigned RCId = TLI->getRepRegClassFor(VT)->getID();
    2227          86 :       if (RegPressure[RCId] < TLI->getRepRegClassCostFor(VT))
    2228             :         // Register pressure tracking is imprecise. This can happen.
    2229          40 :         RegPressure[RCId] = 0;
    2230             :       else
    2231          46 :         RegPressure[RCId] -= TLI->getRepRegClassCostFor(VT);
    2232             :     }
    2233             :   }
    2234             : 
    2235             :   // Check for isMachineOpcode() as PrescheduleNodesWithMultipleUses()
    2236             :   // may transfer data dependencies to CopyToReg.
    2237          66 :   if (SU->NumSuccs && N->isMachineOpcode()) {
    2238         184 :     unsigned NumDefs = TII->get(N->getMachineOpcode()).getNumDefs();
    2239          98 :     for (unsigned i = NumDefs, e = N->getNumValues(); i != e; ++i) {
    2240           6 :       MVT VT = N->getSimpleValueType(i);
    2241           6 :       if (VT == MVT::Glue || VT == MVT::Other)
    2242           0 :         continue;
    2243          11 :       if (!N->hasAnyUseOfValue(i))
    2244           5 :         continue;
    2245           2 :       unsigned RCId = TLI->getRepRegClassFor(VT)->getID();
    2246           2 :       RegPressure[RCId] += TLI->getRepRegClassCostFor(VT);
    2247             :     }
    2248             :   }
    2249             : 
    2250             :   DEBUG(dumpRegPressure());
    2251             : }
    2252             : 
    2253             : //===----------------------------------------------------------------------===//
    2254             : //           Dynamic Node Priority for Register Pressure Reduction
    2255             : //===----------------------------------------------------------------------===//
    2256             : 
    2257             : /// closestSucc - Returns the scheduled cycle of the successor which is
    2258             : /// closest to the current cycle.
    2259    15562345 : static unsigned closestSucc(const SUnit *SU) {
    2260    15562345 :   unsigned MaxHeight = 0;
    2261    64610394 :   for (const SDep &Succ : SU->Succs) {
    2262    17923359 :     if (Succ.isCtrl()) continue;  // ignore chain succs
    2263    26127188 :     unsigned Height = Succ.getSUnit()->getHeight();
    2264             :     // If there are bunch of CopyToRegs stacked up, they should be considered
    2265             :     // to be at the same position.
    2266    26127186 :     if (Succ.getSUnit()->getNode() &&
    2267    13063592 :         Succ.getSUnit()->getNode()->getOpcode() == ISD::CopyToReg)
    2268      242713 :       Height = closestSucc(Succ.getSUnit())+1;
    2269    13063594 :     if (Height > MaxHeight)
    2270    11859249 :       MaxHeight = Height;
    2271             :   }
    2272    15562345 :   return MaxHeight;
    2273             : }
    2274             : 
    2275             : /// calcMaxScratches - Returns an cost estimate of the worse case requirement
    2276             : /// for scratch registers, i.e. number of data dependencies.
    2277             : static unsigned calcMaxScratches(const SUnit *SU) {
    2278     5400814 :   unsigned Scratches = 0;
    2279    26249960 :   for (const SDep &Pred : SU->Preds) {
    2280    10047518 :     if (Pred.isCtrl()) continue;  // ignore chain preds
    2281     7343177 :     Scratches++;
    2282             :   }
    2283             :   return Scratches;
    2284             : }
    2285             : 
    2286             : /// hasOnlyLiveInOpers - Return true if SU has only value predecessors that are
    2287             : /// CopyFromReg from a virtual register.
    2288       47851 : static bool hasOnlyLiveInOpers(const SUnit *SU) {
    2289       47851 :   bool RetVal = false;
    2290      171845 :   for (const SDep &Pred : SU->Preds) {
    2291       51582 :     if (Pred.isCtrl()) continue;
    2292       32462 :     const SUnit *PredSU = Pred.getSUnit();
    2293       32462 :     if (PredSU->getNode() &&
    2294             :         PredSU->getNode()->getOpcode() == ISD::CopyFromReg) {
    2295             :       unsigned Reg =
    2296       31935 :         cast<RegisterSDNode>(PredSU->getNode()->getOperand(1))->getReg();
    2297       19817 :       if (TargetRegisterInfo::isVirtualRegister(Reg)) {
    2298        9172 :         RetVal = true;
    2299        9172 :         continue;
    2300             :       }
    2301             :     }
    2302             :     return false;
    2303             :   }
    2304             :   return RetVal;
    2305             : }
    2306             : 
    2307             : /// hasOnlyLiveOutUses - Return true if SU has only value successors that are
    2308             : /// CopyToReg to a virtual register. This SU def is probably a liveout and
    2309             : /// it has no other use. It should be scheduled closer to the terminator.
    2310        5515 : static bool hasOnlyLiveOutUses(const SUnit *SU) {
    2311        5515 :   bool RetVal = false;
    2312       19155 :   for (const SDep &Succ : SU->Succs) {
    2313        6597 :     if (Succ.isCtrl()) continue;
    2314        5115 :     const SUnit *SuccSU = Succ.getSUnit();
    2315        5115 :     if (SuccSU->getNode() && SuccSU->getNode()->getOpcode() == ISD::CopyToReg) {
    2316             :       unsigned Reg =
    2317        3384 :         cast<RegisterSDNode>(SuccSU->getNode()->getOperand(1))->getReg();
    2318        2256 :       if (TargetRegisterInfo::isVirtualRegister(Reg)) {
    2319        1128 :         RetVal = true;
    2320        1128 :         continue;
    2321             :       }
    2322             :     }
    2323             :     return false;
    2324             :   }
    2325             :   return RetVal;
    2326             : }
    2327             : 
    2328             : // Set isVRegCycle for a node with only live in opers and live out uses. Also
    2329             : // set isVRegCycle for its CopyFromReg operands.
    2330             : //
    2331             : // This is only relevant for single-block loops, in which case the VRegCycle
    2332             : // node is likely an induction variable in which the operand and target virtual
    2333             : // registers should be coalesced (e.g. pre/post increment values). Setting the
    2334             : // isVRegCycle flag helps the scheduler prioritize other uses of the same
    2335             : // CopyFromReg so that this node becomes the virtual register "kill". This
    2336             : // avoids interference between the values live in and out of the block and
    2337             : // eliminates a copy inside the loop.
    2338       47851 : static void initVRegCycle(SUnit *SU) {
    2339       47851 :   if (DisableSchedVRegCycle)
    2340             :     return;
    2341             : 
    2342       47851 :   if (!hasOnlyLiveInOpers(SU) || !hasOnlyLiveOutUses(SU))
    2343             :     return;
    2344             : 
    2345             :   DEBUG(dbgs() << "VRegCycle: SU(" << SU->NodeNum << ")\n");
    2346             : 
    2347         795 :   SU->isVRegCycle = true;
    2348             : 
    2349        3351 :   for (const SDep &Pred : SU->Preds) {
    2350         966 :     if (Pred.isCtrl()) continue;
    2351         950 :     Pred.getSUnit()->isVRegCycle = true;
    2352             :   }
    2353             : }
    2354             : 
    2355             : // After scheduling the definition of a VRegCycle, clear the isVRegCycle flag of
    2356             : // CopyFromReg operands. We should no longer penalize other uses of this VReg.
    2357     3607914 : static void resetVRegCycle(SUnit *SU) {
    2358     3607914 :   if (!SU->isVRegCycle)
    2359             :     return;
    2360             : 
    2361        3351 :   for (const SDep &Pred : SU->Preds) {
    2362         966 :     if (Pred.isCtrl()) continue;  // ignore chain preds
    2363         950 :     SUnit *PredSU = Pred.getSUnit();
    2364         950 :     if (PredSU->isVRegCycle) {
    2365             :       assert(PredSU->getNode()->getOpcode() == ISD::CopyFromReg &&
    2366             :              "VRegCycle def must be CopyFromReg");
    2367         921 :       Pred.getSUnit()->isVRegCycle = false;
    2368             :     }
    2369             :   }
    2370             : }
    2371             : 
    2372             : // Return true if this SUnit uses a CopyFromReg node marked as a VRegCycle. This
    2373             : // means a node that defines the VRegCycle has not been scheduled yet.
    2374     5298108 : static bool hasVRegCycleUse(const SUnit *SU) {
    2375             :   // If this SU also defines the VReg, don't hoist it as a "use".
    2376     5298108 :   if (SU->isVRegCycle)
    2377             :     return false;
    2378             : 
    2379    25213412 :   for (const SDep &Pred : SU->Preds) {
    2380     9320829 :     if (Pred.isCtrl()) continue;  // ignore chain preds
    2381     6963419 :     if (Pred.getSUnit()->isVRegCycle &&
    2382        1222 :         Pred.getSUnit()->getNode()->getOpcode() == ISD::CopyFromReg) {
    2383             :       DEBUG(dbgs() << "  VReg cycle use: SU (" << SU->NodeNum << ")\n");
    2384             :       return true;
    2385             :     }
    2386             :   }
    2387             :   return false;
    2388             : }
    2389             : 
    2390             : // Check for either a dependence (latency) or resource (hazard) stall.
    2391             : //
    2392             : // Note: The ScheduleHazardRecognizer interface requires a non-const SU.
    2393             : static bool BUHasStall(SUnit *SU, int Height, RegReductionPQBase *SPQ) {
    2394     5098968 :   if ((int)SPQ->getCurCycle() < Height) return true;
    2395    10118076 :   if (SPQ->getHazardRec()->getHazardType(SU, 0)
    2396             :       != ScheduleHazardRecognizer::NoHazard)
    2397             :     return true;
    2398             :   return false;
    2399             : }
    2400             : 
    2401             : // Return -1 if left has higher priority, 1 if right has higher priority.
    2402             : // Return 0 if latency-based priority is equivalent.
    2403     2649054 : static int BUCompareLatency(SUnit *left, SUnit *right, bool checkPref,
    2404             :                             RegReductionPQBase *SPQ) {
    2405             :   // Scheduling an instruction that uses a VReg whose postincrement has not yet
    2406             :   // been scheduled will induce a copy. Model this as an extra cycle of latency.
    2407     2649054 :   int LPenalty = hasVRegCycleUse(left) ? 1 : 0;
    2408     2649054 :   int RPenalty = hasVRegCycleUse(right) ? 1 : 0;
    2409     2649054 :   int LHeight = (int)left->getHeight() + LPenalty;
    2410     2649054 :   int RHeight = (int)right->getHeight() + RPenalty;
    2411             : 
    2412     2649054 :   bool LStall = (!checkPref || left->SchedulingPref == Sched::ILP) &&
    2413     2649054 :     BUHasStall(left, LHeight, SPQ);
    2414     2649054 :   bool RStall = (!checkPref || right->SchedulingPref == Sched::ILP) &&
    2415     2649054 :     BUHasStall(right, RHeight, SPQ);
    2416             : 
    2417             :   // If scheduling one of the node will cause a pipeline stall, delay it.
    2418             :   // If scheduling either one of the node will cause a pipeline stall, sort
    2419             :   // them according to their height.
    2420     2649054 :   if (LStall) {
    2421       42031 :     if (!RStall)
    2422             :       return 1;
    2423       36091 :     if (LHeight != RHeight)
    2424        5838 :       return LHeight > RHeight ? 1 : -1;
    2425     2607023 :   } else if (RStall)
    2426             :     return -1;
    2427             : 
    2428             :   // If either node is scheduling for latency, sort them by height/depth
    2429             :   // and latency.
    2430     2724604 :   if (!checkPref || (left->SchedulingPref == Sched::ILP ||
    2431       94945 :                      right->SchedulingPref == Sched::ILP)) {
    2432             :     // If neither instruction stalls (!LStall && !RStall) and HazardRecognizer
    2433             :     // is enabled, grouping instructions by cycle, then its height is already
    2434             :     // covered so only its depth matters. We also reach this point if both stall
    2435             :     // but have the same height.
    2436     5071874 :     if (!SPQ->getHazardRec()->isEnabled()) {
    2437     2434844 :       if (LHeight != RHeight)
    2438      166657 :         return LHeight > RHeight ? 1 : -1;
    2439             :     }
    2440     2369280 :     int LDepth = left->getDepth() - LPenalty;
    2441     2369280 :     int RDepth = right->getDepth() - RPenalty;
    2442     2369280 :     if (LDepth != RDepth) {
    2443             :       DEBUG(dbgs() << "  Comparing latency of SU (" << left->NodeNum
    2444             :             << ") depth " << LDepth << " vs SU (" << right->NodeNum
    2445             :             << ") depth " << RDepth << "\n");
    2446      263772 :       return LDepth < RDepth ? 1 : -1;
    2447             :     }
    2448     2105508 :     if (left->Latency != right->Latency)
    2449        2220 :       return left->Latency > right->Latency ? 1 : -1;
    2450             :   }
    2451             :   return 0;
    2452             : }
    2453             : 
    2454     8761901 : static bool BURRSort(SUnit *left, SUnit *right, RegReductionPQBase *SPQ) {
    2455             :   // Schedule physical register definitions close to their use. This is
    2456             :   // motivated by microarchitectures that can fuse cmp+jump macro-ops. But as
    2457             :   // long as shortening physreg live ranges is generally good, we can defer
    2458             :   // creating a subtarget hook.
    2459     8761901 :   if (!DisableSchedPhysRegJoin) {
    2460     8761901 :     bool LHasPhysReg = left->hasPhysRegDefs;
    2461     8761901 :     bool RHasPhysReg = right->hasPhysRegDefs;
    2462     8761901 :     if (LHasPhysReg != RHasPhysReg) {
    2463             :       #ifndef NDEBUG
    2464             :       static const char *const PhysRegMsg[] = { " has no physreg",
    2465             :                                                 " defines a physreg" };
    2466             :       #endif
    2467             :       DEBUG(dbgs() << "  SU (" << left->NodeNum << ") "
    2468             :             << PhysRegMsg[LHasPhysReg] << " SU(" << right->NodeNum << ") "
    2469             :             << PhysRegMsg[RHasPhysReg] << "\n");
    2470       25859 :       return LHasPhysReg < RHasPhysReg;
    2471             :     }
    2472             :   }
    2473             : 
    2474             :   // Prioritize by Sethi-Ulmann number and push CopyToReg nodes down.
    2475     8736042 :   unsigned LPriority = SPQ->getNodePriority(left);
    2476     8736042 :   unsigned RPriority = SPQ->getNodePriority(right);
    2477             : 
    2478             :   // Be really careful about hoisting call operands above previous calls.
    2479             :   // Only allows it if it would reduce register pressure.
    2480     8736042 :   if (left->isCall && right->isCallOp) {
    2481         992 :     unsigned RNumVals = right->getNode()->getNumValues();
    2482         496 :     RPriority = (RPriority > RNumVals) ? (RPriority - RNumVals) : 0;
    2483             :   }
    2484     8736042 :   if (right->isCall && left->isCallOp) {
    2485        1142 :     unsigned LNumVals = left->getNode()->getNumValues();
    2486         571 :     LPriority = (LPriority > LNumVals) ? (LPriority - LNumVals) : 0;
    2487             :   }
    2488             : 
    2489     8736042 :   if (LPriority != RPriority)
    2490     1075085 :     return LPriority > RPriority;
    2491             : 
    2492             :   // One or both of the nodes are calls and their sethi-ullman numbers are the
    2493             :   // same, then keep source order.
    2494     7660957 :   if (left->isCall || right->isCall) {
    2495       23042 :     unsigned LOrder = SPQ->getNodeOrdering(left);
    2496       23042 :     unsigned ROrder = SPQ->getNodeOrdering(right);
    2497             : 
    2498             :     // Prefer an ordering where the lower the non-zero order number, the higher
    2499             :     // the preference.
    2500       11521 :     if ((LOrder || ROrder) && LOrder != ROrder)
    2501        1141 :       return LOrder != 0 && (LOrder < ROrder || ROrder == 0);
    2502             :   }
    2503             : 
    2504             :   // Try schedule def + use closer when Sethi-Ullman numbers are the same.
    2505             :   // e.g.
    2506             :   // t1 = op t2, c1
    2507             :   // t3 = op t4, c2
    2508             :   //
    2509             :   // and the following instructions are both ready.
    2510             :   // t2 = op c3
    2511             :   // t4 = op c4
    2512             :   //
    2513             :   // Then schedule t2 = op first.
    2514             :   // i.e.
    2515             :   // t4 = op c4
    2516             :   // t2 = op c3
    2517             :   // t1 = op t2, c1
    2518             :   // t3 = op t4, c2
    2519             :   //
    2520             :   // This creates more short live intervals.
    2521     7659816 :   unsigned LDist = closestSucc(left);
    2522     7659816 :   unsigned RDist = closestSucc(right);
    2523     7659816 :   if (LDist != RDist)
    2524     4959409 :     return LDist < RDist;
    2525             : 
    2526             :   // How many registers becomes live when the node is scheduled.
    2527     2700407 :   unsigned LScratch = calcMaxScratches(left);
    2528     2700407 :   unsigned RScratch = calcMaxScratches(right);
    2529     2700407 :   if (LScratch != RScratch)
    2530      189782 :     return LScratch > RScratch;
    2531             : 
    2532             :   // Comparing latency against a call makes little sense unless the node
    2533             :   // is register pressure-neutral.
    2534     2510625 :   if ((left->isCall && RPriority > 0) || (right->isCall && LPriority > 0))
    2535        7035 :     return (left->NodeQueueId > right->NodeQueueId);
    2536             : 
    2537             :   // Do not compare latencies when one or both of the nodes are calls.
    2538     2503590 :   if (!DisableSchedCycles &&
    2539     2503583 :       !(left->isCall || right->isCall)) {
    2540     2503563 :     int result = BUCompareLatency(left, right, false /*checkPref*/, SPQ);
    2541     2503563 :     if (result != 0)
    2542      411966 :       return result > 0;
    2543             :   }
    2544             :   else {
    2545          54 :     if (left->getHeight() != right->getHeight())
    2546           0 :       return left->getHeight() > right->getHeight();
    2547             : 
    2548          54 :     if (left->getDepth() != right->getDepth())
    2549          16 :       return left->getDepth() < right->getDepth();
    2550             :   }
    2551             : 
    2552             :   assert(left->NodeQueueId && right->NodeQueueId &&
    2553             :          "NodeQueueId cannot be zero");
    2554     2091616 :   return (left->NodeQueueId > right->NodeQueueId);
    2555             : }
    2556             : 
    2557             : // Bottom up
    2558             : bool bu_ls_rr_sort::operator()(SUnit *left, SUnit *right) const {
    2559       63136 :   if (int res = checkSpecialNodes(left, right))
    2560         448 :     return res > 0;
    2561             : 
    2562       62895 :   return BURRSort(left, right, SPQ);
    2563             : }
    2564             : 
    2565             : // Source order, otherwise bottom up.
    2566    13765579 : bool src_ls_rr_sort::operator()(SUnit *left, SUnit *right) const {
    2567    13745393 :   if (int res = checkSpecialNodes(left, right))
    2568       73801 :     return res > 0;
    2569             : 
    2570    27383556 :   unsigned LOrder = SPQ->getNodeOrdering(left);
    2571    27383556 :   unsigned ROrder = SPQ->getNodeOrdering(right);
    2572             : 
    2573             :   // Prefer an ordering where the lower the non-zero order number, the higher
    2574             :   // the preference.
    2575    13691778 :   if ((LOrder || ROrder) && LOrder != ROrder)
    2576     5227247 :     return LOrder != 0 && (LOrder < ROrder || ROrder == 0);
    2577             : 
    2578     8464531 :   return BURRSort(left, right, SPQ);
    2579             : }
    2580             : 
    2581             : // If the time between now and when the instruction will be ready can cover
    2582             : // the spill code, then avoid adding it to the ready queue. This gives long
    2583             : // stalls highest priority and allows hoisting across calls. It should also
    2584             : // speed up processing the available queue.
    2585             : bool hybrid_ls_rr_sort::isReady(SUnit *SU, unsigned CurCycle) const {
    2586             :   static const unsigned ReadyDelay = 3;
    2587             : 
    2588             :   if (SPQ->MayReduceRegPressure(SU)) return true;
    2589             : 
    2590             :   if (SU->getHeight() > (CurCycle + ReadyDelay)) return false;
    2591             : 
    2592             :   if (SPQ->getHazardRec()->getHazardType(SU, -ReadyDelay)
    2593             :       != ScheduleHazardRecognizer::NoHazard)
    2594             :     return false;
    2595             : 
    2596             :   return true;
    2597             : }
    2598             : 
    2599             : // Return true if right should be scheduled with higher priority than left.
    2600      164771 : bool hybrid_ls_rr_sort::operator()(SUnit *left, SUnit *right) const {
    2601      164533 :   if (int res = checkSpecialNodes(left, right))
    2602        1238 :     return res > 0;
    2603             : 
    2604      325386 :   if (left->isCall || right->isCall)
    2605             :     // No way to compute latency of calls.
    2606        2760 :     return BURRSort(left, right, SPQ);
    2607             : 
    2608      160773 :   bool LHigh = SPQ->HighRegPressure(left);
    2609      160773 :   bool RHigh = SPQ->HighRegPressure(right);
    2610             :   // Avoid causing spills. If register pressure is high, schedule for
    2611             :   // register pressure reduction.
    2612      160773 :   if (LHigh && !RHigh) {
    2613             :     DEBUG(dbgs() << "  pressure SU(" << left->NodeNum << ") > SU("
    2614             :           << right->NodeNum << ")\n");
    2615             :     return true;
    2616             :   }
    2617      159941 :   else if (!LHigh && RHigh) {
    2618             :     DEBUG(dbgs() << "  pressure SU(" << right->NodeNum << ") > SU("
    2619             :           << left->NodeNum << ")\n");
    2620             :     return false;
    2621             :   }
    2622      149823 :   if (!LHigh && !RHigh) {
    2623      145491 :     int result = BUCompareLatency(left, right, true /*checkPref*/, SPQ);
    2624      145491 :     if (result != 0)
    2625       40078 :       return result > 0;
    2626             :   }
    2627      109745 :   return BURRSort(left, right, SPQ);
    2628             : }
    2629             : 
    2630             : // Schedule as many instructions in each cycle as possible. So don't make an
    2631             : // instruction available unless it is ready in the current cycle.
    2632             : bool ilp_ls_rr_sort::isReady(SUnit *SU, unsigned CurCycle) const {
    2633             :   if (SU->getHeight() > CurCycle) return false;
    2634             : 
    2635             :   if (SPQ->getHazardRec()->getHazardType(SU, 0)
    2636             :       != ScheduleHazardRecognizer::NoHazard)
    2637             :     return false;
    2638             : 
    2639             :   return true;
    2640             : }
    2641             : 
    2642       34182 : static bool canEnableCoalescing(SUnit *SU) {
    2643       68364 :   unsigned Opc = SU->getNode() ? SU->getNode()->getOpcode() : 0;
    2644       34182 :   if (Opc == ISD::TokenFactor || Opc == ISD::CopyToReg)
    2645             :     // CopyToReg should be close to its uses to facilitate coalescing and
    2646             :     // avoid spilling.
    2647             :     return true;
    2648             : 
    2649       51914 :   if (Opc == TargetOpcode::EXTRACT_SUBREG ||
    2650       51914 :       Opc == TargetOpcode::SUBREG_TO_REG ||
    2651             :       Opc == TargetOpcode::INSERT_SUBREG)
    2652             :     // EXTRACT_SUBREG, INSERT_SUBREG, and SUBREG_TO_REG nodes should be
    2653             :     // close to their uses to facilitate coalescing.
    2654             :     return true;
    2655             : 
    2656       25957 :   if (SU->NumPreds == 0 && SU->NumSuccs != 0)
    2657             :     // If SU does not have a register def, schedule it close to its uses
    2658             :     // because it does not lengthen any live ranges.
    2659             :     return true;
    2660             : 
    2661       25957 :   return false;
    2662             : }
    2663             : 
    2664             : // list-ilp is currently an experimental scheduler that allows various
    2665             : // heuristics to be enabled prior to the normal register reduction logic.
    2666      152576 : bool ilp_ls_rr_sort::operator()(SUnit *left, SUnit *right) const {
    2667      152107 :   if (int res = checkSpecialNodes(left, right))
    2668        1880 :     return res > 0;
    2669             : 
    2670      299305 :   if (left->isCall || right->isCall)
    2671             :     // No way to compute latency of calls.
    2672        3779 :     return BURRSort(left, right, SPQ);
    2673             : 
    2674      146917 :   unsigned LLiveUses = 0, RLiveUses = 0;
    2675      146917 :   int LPDiff = 0, RPDiff = 0;
    2676      146917 :   if (!DisableSchedRegPressure || !DisableSchedLiveUses) {
    2677      146917 :     LPDiff = SPQ->RegPressureDiff(left, LLiveUses);
    2678      146917 :     RPDiff = SPQ->RegPressureDiff(right, RLiveUses);
    2679             :   }
    2680      146917 :   if (!DisableSchedRegPressure && LPDiff != RPDiff) {
    2681             :     DEBUG(dbgs() << "RegPressureDiff SU(" << left->NodeNum << "): " << LPDiff
    2682             :           << " != SU(" << right->NodeNum << "): " << RPDiff << "\n");
    2683       17046 :     return LPDiff > RPDiff;
    2684             :   }
    2685             : 
    2686      259742 :   if (!DisableSchedRegPressure && (LPDiff > 0 || RPDiff > 0)) {
    2687       17091 :     bool LReduce = canEnableCoalescing(left);
    2688       17091 :     bool RReduce = canEnableCoalescing(right);
    2689       17091 :     if (LReduce && !RReduce) return false;
    2690       16678 :     if (RReduce && !LReduce) return true;
    2691             :   }
    2692             : 
    2693      129404 :   if (!DisableSchedLiveUses && (LLiveUses != RLiveUses)) {
    2694             :     DEBUG(dbgs() << "Live uses SU(" << left->NodeNum << "): " << LLiveUses
    2695             :           << " != SU(" << right->NodeNum << "): " << RLiveUses << "\n");
    2696           0 :     return LLiveUses < RLiveUses;
    2697             :   }
    2698             : 
    2699      129404 :   if (!DisableSchedStalls) {
    2700           0 :     bool LStall = BUHasStall(left, left->getHeight(), SPQ);
    2701           0 :     bool RStall = BUHasStall(right, right->getHeight(), SPQ);
    2702           0 :     if (LStall != RStall)
    2703           0 :       return left->getHeight() > right->getHeight();
    2704             :   }
    2705             : 
    2706      129404 :   if (!DisableSchedCriticalPath) {
    2707      258808 :     int spread = (int)left->getDepth() - (int)right->getDepth();
    2708      258808 :     if (std::abs(spread) > MaxReorderWindow) {
    2709             :       DEBUG(dbgs() << "Depth of SU(" << left->NodeNum << "): "
    2710             :             << left->getDepth() << " != SU(" << right->NodeNum << "): "
    2711             :             << right->getDepth() << "\n");
    2712        4926 :       return left->getDepth() < right->getDepth();
    2713             :     }
    2714             :   }
    2715             : 
    2716      380823 :   if (!DisableSchedHeight && left->getHeight() != right->getHeight()) {
    2717       95718 :     int spread = (int)left->getHeight() - (int)right->getHeight();
    2718       95718 :     if (std::abs(spread) > MaxReorderWindow)
    2719       17500 :       return left->getHeight() > right->getHeight();
    2720             :   }
    2721             : 
    2722      118191 :   return BURRSort(left, right, SPQ);
    2723             : }
    2724             : 
    2725      279964 : void RegReductionPQBase::initNodes(std::vector<SUnit> &sunits) {
    2726      279964 :   SUnits = &sunits;
    2727             :   // Add pseudo dependency edges for two-address nodes.
    2728      279964 :   if (!Disable2AddrHack)
    2729           0 :     AddPseudoTwoAddrDeps();
    2730             :   // Reroute edges to nodes with multiple uses.
    2731      279964 :   if (!TracksRegPressure && !SrcOrder)
    2732       12406 :     PrescheduleNodesWithMultipleUses();
    2733             :   // Calculate node priorities.
    2734      279964 :   CalculateSethiUllmanNumbers();
    2735             : 
    2736             :   // For single block loops, mark nodes that look like canonical IV increments.
    2737      279964 :   if (scheduleDAG->BB->isSuccessor(scheduleDAG->BB))
    2738       60383 :     for (SUnit &SU : sunits)
    2739       47851 :       initVRegCycle(&SU);
    2740      279964 : }
    2741             : 
    2742             : //===----------------------------------------------------------------------===//
    2743             : //                    Preschedule for Register Pressure
    2744             : //===----------------------------------------------------------------------===//
    2745             : 
    2746           0 : bool RegReductionPQBase::canClobber(const SUnit *SU, const SUnit *Op) {
    2747           0 :   if (SU->isTwoAddress) {
    2748           0 :     unsigned Opc = SU->getNode()->getMachineOpcode();
    2749           0 :     const MCInstrDesc &MCID = TII->get(Opc);
    2750           0 :     unsigned NumRes = MCID.getNumDefs();
    2751           0 :     unsigned NumOps = MCID.getNumOperands() - NumRes;
    2752           0 :     for (unsigned i = 0; i != NumOps; ++i) {
    2753           0 :       if (MCID.getOperandConstraint(i+NumRes, MCOI::TIED_TO) != -1) {
    2754           0 :         SDNode *DU = SU->getNode()->getOperand(i).getNode();
    2755           0 :         if (DU->getNodeId() != -1 &&
    2756           0 :             Op->OrigNode == &(*SUnits)[DU->getNodeId()])
    2757             :           return true;
    2758             :       }
    2759             :     }
    2760             :   }
    2761             :   return false;
    2762             : }
    2763             : 
    2764             : /// canClobberReachingPhysRegUse - True if SU would clobber one of it's
    2765             : /// successor's explicit physregs whose definition can reach DepSU.
    2766             : /// i.e. DepSU should not be scheduled above SU.
    2767           0 : static bool canClobberReachingPhysRegUse(const SUnit *DepSU, const SUnit *SU,
    2768             :                                          ScheduleDAGRRList *scheduleDAG,
    2769             :                                          const TargetInstrInfo *TII,
    2770             :                                          const TargetRegisterInfo *TRI) {
    2771             :   const MCPhysReg *ImpDefs
    2772           0 :     = TII->get(SU->getNode()->getMachineOpcode()).getImplicitDefs();
    2773           0 :   const uint32_t *RegMask = getNodeRegMask(SU->getNode());
    2774           0 :   if(!ImpDefs && !RegMask)
    2775             :     return false;
    2776             : 
    2777           0 :   for (const SDep &Succ : SU->Succs) {
    2778           0 :     SUnit *SuccSU = Succ.getSUnit();
    2779           0 :     for (const SDep &SuccPred : SuccSU->Preds) {
    2780           0 :       if (!SuccPred.isAssignedRegDep())
    2781           0 :         continue;
    2782             : 
    2783           0 :       if (RegMask &&
    2784           0 :           MachineOperand::clobbersPhysReg(RegMask, SuccPred.getReg()) &&
    2785           0 :           scheduleDAG->IsReachable(DepSU, SuccPred.getSUnit()))
    2786             :         return true;
    2787             : 
    2788           0 :       if (ImpDefs)
    2789           0 :         for (const MCPhysReg *ImpDef = ImpDefs; *ImpDef; ++ImpDef)
    2790             :           // Return true if SU clobbers this physical register use and the
    2791             :           // definition of the register reaches from DepSU. IsReachable queries
    2792             :           // a topological forward sort of the DAG (following the successors).
    2793           0 :           if (TRI->regsOverlap(*ImpDef, SuccPred.getReg()) &&
    2794           0 :               scheduleDAG->IsReachable(DepSU, SuccPred.getSUnit()))
    2795             :             return true;
    2796             :     }
    2797             :   }
    2798             :   return false;
    2799             : }
    2800             : 
    2801             : /// canClobberPhysRegDefs - True if SU would clobber one of SuccSU's
    2802             : /// physical register defs.
    2803           0 : static bool canClobberPhysRegDefs(const SUnit *SuccSU, const SUnit *SU,
    2804             :                                   const TargetInstrInfo *TII,
    2805             :                                   const TargetRegisterInfo *TRI) {
    2806           0 :   SDNode *N = SuccSU->getNode();
    2807           0 :   unsigned NumDefs = TII->get(N->getMachineOpcode()).getNumDefs();
    2808           0 :   const MCPhysReg *ImpDefs = TII->get(N->getMachineOpcode()).getImplicitDefs();
    2809             :   assert(ImpDefs && "Caller should check hasPhysRegDefs");
    2810           0 :   for (const SDNode *SUNode = SU->getNode(); SUNode;
    2811             :        SUNode = SUNode->getGluedNode()) {
    2812           0 :     if (!SUNode->isMachineOpcode())
    2813           0 :       continue;
    2814             :     const MCPhysReg *SUImpDefs =
    2815           0 :       TII->get(SUNode->getMachineOpcode()).getImplicitDefs();
    2816           0 :     const uint32_t *SURegMask = getNodeRegMask(SUNode);
    2817           0 :     if (!SUImpDefs && !SURegMask)
    2818           0 :       continue;
    2819           0 :     for (unsigned i = NumDefs, e = N->getNumValues(); i != e; ++i) {
    2820           0 :       MVT VT = N->getSimpleValueType(i);
    2821           0 :       if (VT == MVT::Glue || VT == MVT::Other)
    2822           0 :         continue;
    2823           0 :       if (!N->hasAnyUseOfValue(i))
    2824           0 :         continue;
    2825           0 :       unsigned Reg = ImpDefs[i - NumDefs];
    2826           0 :       if (SURegMask && MachineOperand::clobbersPhysReg(SURegMask, Reg))
    2827             :         return true;
    2828           0 :       if (!SUImpDefs)
    2829           0 :         continue;
    2830           0 :       for (;*SUImpDefs; ++SUImpDefs) {
    2831           0 :         unsigned SUReg = *SUImpDefs;
    2832           0 :         if (TRI->regsOverlap(Reg, SUReg))
    2833             :           return true;
    2834             :       }
    2835             :     }
    2836             :   }
    2837             :   return false;
    2838             : }
    2839             : 
    2840             : /// PrescheduleNodesWithMultipleUses - Nodes with multiple uses
    2841             : /// are not handled well by the general register pressure reduction
    2842             : /// heuristics. When presented with code like this:
    2843             : ///
    2844             : ///      N
    2845             : ///    / |
    2846             : ///   /  |
    2847             : ///  U  store
    2848             : ///  |
    2849             : /// ...
    2850             : ///
    2851             : /// the heuristics tend to push the store up, but since the
    2852             : /// operand of the store has another use (U), this would increase
    2853             : /// the length of that other use (the U->N edge).
    2854             : ///
    2855             : /// This function transforms code like the above to route U's
    2856             : /// dependence through the store when possible, like this:
    2857             : ///
    2858             : ///      N
    2859             : ///      ||
    2860             : ///      ||
    2861             : ///     store
    2862             : ///       |
    2863             : ///       U
    2864             : ///       |
    2865             : ///      ...
    2866             : ///
    2867             : /// This results in the store being scheduled immediately
    2868             : /// after N, which shortens the U->N live range, reducing
    2869             : /// register pressure.
    2870             : ///
    2871       12406 : void RegReductionPQBase::PrescheduleNodesWithMultipleUses() {
    2872             :   // Visit all the nodes in topological order, working top-down.
    2873      129310 :   for (SUnit &SU : *SUnits) {
    2874             :     // For now, only look at nodes with no data successors, such as stores.
    2875             :     // These are especially important, due to the heuristics in
    2876             :     // getNodePriority for nodes with no data successors.
    2877       79686 :     if (SU.NumSuccs != 0)
    2878       54239 :       continue;
    2879             :     // For now, only look at nodes with exactly one data predecessor.
    2880       25447 :     if (SU.NumPreds != 1)
    2881       13786 :       continue;
    2882             :     // Avoid prescheduling copies to virtual registers, which don't behave
    2883             :     // like other nodes from the perspective of scheduling heuristics.
    2884       11661 :     if (SDNode *N = SU.getNode())
    2885       13262 :       if (N->getOpcode() == ISD::CopyToReg &&
    2886             :           TargetRegisterInfo::isVirtualRegister
    2887        6404 :             (cast<RegisterSDNode>(N->getOperand(1))->getReg()))
    2888        1538 :         continue;
    2889             : 
    2890             :     // Locate the single data predecessor.
    2891       10123 :     SUnit *PredSU = nullptr;
    2892       32114 :     for (const SDep &Pred : SU.Preds)
    2893       11868 :       if (!Pred.isCtrl()) {
    2894       10123 :         PredSU = Pred.getSUnit();
    2895       10123 :         break;
    2896             :       }
    2897             :     assert(PredSU);
    2898             : 
    2899             :     // Don't rewrite edges that carry physregs, because that requires additional
    2900             :     // support infrastructure.
    2901       10123 :     if (PredSU->hasPhysRegDefs)
    2902           6 :       continue;
    2903             :     // Short-circuit the case where SU is PredSU's only data successor.
    2904       10117 :     if (PredSU->NumSuccs == 1)
    2905        8943 :       continue;
    2906             :     // Avoid prescheduling to copies from virtual registers, which don't behave
    2907             :     // like other nodes from the perspective of scheduling heuristics.
    2908        1174 :     if (SDNode *N = SU.getNode())
    2909        1182 :       if (N->getOpcode() == ISD::CopyFromReg &&
    2910             :           TargetRegisterInfo::isVirtualRegister
    2911          32 :             (cast<RegisterSDNode>(N->getOperand(1))->getReg()))
    2912           0 :         continue;
    2913             : 
    2914             :     // Perform checks on the successors of PredSU.
    2915        4305 :     for (const SDep &PredSucc : PredSU->Succs) {
    2916        1891 :       SUnit *PredSuccSU = PredSucc.getSUnit();
    2917        1891 :       if (PredSuccSU == &SU) continue;
    2918             :       // If PredSU has another successor with no data successors, for
    2919             :       // now don't attempt to choose either over the other.
    2920        1227 :       if (PredSuccSU->NumSuccs == 0)
    2921             :         goto outer_loop_continue;
    2922             :       // Don't break physical register dependencies.
    2923         201 :       if (SU.hasPhysRegClobbers && PredSuccSU->hasPhysRegDefs)
    2924           0 :         if (canClobberPhysRegDefs(PredSuccSU, &SU, TII, TRI))
    2925             :           goto outer_loop_continue;
    2926             :       // Don't introduce graph cycles.
    2927         402 :       if (scheduleDAG->IsReachable(&SU, PredSuccSU))
    2928             :         goto outer_loop_continue;
    2929             :     }
    2930             : 
    2931             :     // Ok, the transformation is safe and the heuristics suggest it is
    2932             :     // profitable. Update the graph.
    2933             :     DEBUG(dbgs() << "    Prescheduling SU #" << SU.NodeNum
    2934             :                  << " next to PredSU #" << PredSU->NodeNum
    2935             :                  << " to guide scheduling in the presence of multiple uses\n");
    2936         633 :     for (unsigned i = 0; i != PredSU->Succs.size(); ++i) {
    2937         334 :       SDep Edge = PredSU->Succs[i];
    2938             :       assert(!Edge.isAssignedRegDep());
    2939         167 :       SUnit *SuccSU = Edge.getSUnit();
    2940         167 :       if (SuccSU != &SU) {
    2941         101 :         Edge.setSUnit(PredSU);
    2942         101 :         scheduleDAG->RemovePred(SuccSU, Edge);
    2943         101 :         scheduleDAG->AddPred(&SU, Edge);
    2944         101 :         Edge.setSUnit(&SU);
    2945         101 :         scheduleDAG->AddPred(SuccSU, Edge);
    2946         101 :         --i;
    2947             :       }
    2948             :     }
    2949        1174 :   outer_loop_continue:;
    2950             :   }
    2951       12406 : }
    2952             : 
    2953             : /// AddPseudoTwoAddrDeps - If two nodes share an operand and one of them uses
    2954             : /// it as a def&use operand. Add a pseudo control edge from it to the other
    2955             : /// node (if it won't create a cycle) so the two-address one will be scheduled
    2956             : /// first (lower in the schedule). If both nodes are two-address, favor the
    2957             : /// one that has a CopyToReg use (more likely to be a loop induction update).
    2958             : /// If both are two-address, but one is commutable while the other is not
    2959             : /// commutable, favor the one that's not commutable.
    2960           0 : void RegReductionPQBase::AddPseudoTwoAddrDeps() {
    2961           0 :   for (SUnit &SU : *SUnits) {
    2962           0 :     if (!SU.isTwoAddress)
    2963           0 :       continue;
    2964             : 
    2965           0 :     SDNode *Node = SU.getNode();
    2966           0 :     if (!Node || !Node->isMachineOpcode() || SU.getNode()->getGluedNode())
    2967           0 :       continue;
    2968             : 
    2969           0 :     bool isLiveOut = hasOnlyLiveOutUses(&SU);
    2970           0 :     unsigned Opc = Node->getMachineOpcode();
    2971           0 :     const MCInstrDesc &MCID = TII->get(Opc);
    2972           0 :     unsigned NumRes = MCID.getNumDefs();
    2973           0 :     unsigned NumOps = MCID.getNumOperands() - NumRes;
    2974           0 :     for (unsigned j = 0; j != NumOps; ++j) {
    2975           0 :       if (MCID.getOperandConstraint(j+NumRes, MCOI::TIED_TO) == -1)
    2976           0 :         continue;
    2977           0 :       SDNode *DU = SU.getNode()->getOperand(j).getNode();
    2978           0 :       if (DU->getNodeId() == -1)
    2979           0 :         continue;
    2980           0 :       const SUnit *DUSU = &(*SUnits)[DU->getNodeId()];
    2981           0 :       if (!DUSU)
    2982           0 :         continue;
    2983           0 :       for (const SDep &Succ : DUSU->Succs) {
    2984           0 :         if (Succ.isCtrl())
    2985           0 :           continue;
    2986           0 :         SUnit *SuccSU = Succ.getSUnit();
    2987           0 :         if (SuccSU == &SU)
    2988           0 :           continue;
    2989             :         // Be conservative. Ignore if nodes aren't at roughly the same
    2990             :         // depth and height.
    2991           0 :         if (SuccSU->getHeight() < SU.getHeight() &&
    2992           0 :             (SU.getHeight() - SuccSU->getHeight()) > 1)
    2993           0 :           continue;
    2994             :         // Skip past COPY_TO_REGCLASS nodes, so that the pseudo edge
    2995             :         // constrains whatever is using the copy, instead of the copy
    2996             :         // itself. In the case that the copy is coalesced, this
    2997             :         // preserves the intent of the pseudo two-address heurietics.
    2998           0 :         while (SuccSU->Succs.size() == 1 &&
    2999           0 :                SuccSU->getNode()->isMachineOpcode() &&
    3000           0 :                SuccSU->getNode()->getMachineOpcode() ==
    3001             :                  TargetOpcode::COPY_TO_REGCLASS)
    3002           0 :           SuccSU = SuccSU->Succs.front().getSUnit();
    3003             :         // Don't constrain non-instruction nodes.
    3004           0 :         if (!SuccSU->getNode() || !SuccSU->getNode()->isMachineOpcode())
    3005           0 :           continue;
    3006             :         // Don't constrain nodes with physical register defs if the
    3007             :         // predecessor can clobber them.
    3008           0 :         if (SuccSU->hasPhysRegDefs && SU.hasPhysRegClobbers) {
    3009           0 :           if (canClobberPhysRegDefs(SuccSU, &SU, TII, TRI))
    3010           0 :             continue;
    3011             :         }
    3012             :         // Don't constrain EXTRACT_SUBREG, INSERT_SUBREG, and SUBREG_TO_REG;
    3013             :         // these may be coalesced away. We want them close to their uses.
    3014           0 :         unsigned SuccOpc = SuccSU->getNode()->getMachineOpcode();
    3015           0 :         if (SuccOpc == TargetOpcode::EXTRACT_SUBREG ||
    3016           0 :             SuccOpc == TargetOpcode::INSERT_SUBREG ||
    3017           0 :             SuccOpc == TargetOpcode::SUBREG_TO_REG)
    3018           0 :           continue;
    3019           0 :         if (!canClobberReachingPhysRegUse(SuccSU, &SU, scheduleDAG, TII, TRI) &&
    3020           0 :             (!canClobber(SuccSU, DUSU) ||
    3021           0 :              (isLiveOut && !hasOnlyLiveOutUses(SuccSU)) ||
    3022           0 :              (!SU.isCommutable && SuccSU->isCommutable)) &&
    3023           0 :             !scheduleDAG->IsReachable(SuccSU, &SU)) {
    3024             :           DEBUG(dbgs() << "    Adding a pseudo-two-addr edge from SU #"
    3025             :                        << SU.NodeNum << " to SU #" << SuccSU->NodeNum << "\n");
    3026           0 :           scheduleDAG->AddPred(&SU, SDep(SuccSU, SDep::Artificial));
    3027             :         }
    3028             :       }
    3029             :     }
    3030             :   }
    3031           0 : }
    3032             : 
    3033             : //===----------------------------------------------------------------------===//
    3034             : //                         Public Constructor Functions
    3035             : //===----------------------------------------------------------------------===//
    3036             : 
    3037             : llvm::ScheduleDAGSDNodes *
    3038       12406 : llvm::createBURRListDAGScheduler(SelectionDAGISel *IS,
    3039             :                                  CodeGenOpt::Level OptLevel) {
    3040       12406 :   const TargetSubtargetInfo &STI = IS->MF->getSubtarget();
    3041       12406 :   const TargetInstrInfo *TII = STI.getInstrInfo();
    3042       12406 :   const TargetRegisterInfo *TRI = STI.getRegisterInfo();
    3043             : 
    3044             :   BURegReductionPriorityQueue *PQ =
    3045       24812 :     new BURegReductionPriorityQueue(*IS->MF, false, false, TII, TRI, nullptr);
    3046       12406 :   ScheduleDAGRRList *SD = new ScheduleDAGRRList(*IS->MF, false, PQ, OptLevel);
    3047       24812 :   PQ->setScheduleDAG(SD);
    3048       12406 :   return SD;
    3049             : }
    3050             : 
    3051             : llvm::ScheduleDAGSDNodes *
    3052      240509 : llvm::createSourceListDAGScheduler(SelectionDAGISel *IS,
    3053             :                                    CodeGenOpt::Level OptLevel) {
    3054      240509 :   const TargetSubtargetInfo &STI = IS->MF->getSubtarget();
    3055      240509 :   const TargetInstrInfo *TII = STI.getInstrInfo();
    3056      240509 :   const TargetRegisterInfo *TRI = STI.getRegisterInfo();
    3057             : 
    3058             :   SrcRegReductionPriorityQueue *PQ =
    3059      481018 :     new SrcRegReductionPriorityQueue(*IS->MF, false, true, TII, TRI, nullptr);
    3060      240509 :   ScheduleDAGRRList *SD = new ScheduleDAGRRList(*IS->MF, false, PQ, OptLevel);
    3061      481018 :   PQ->setScheduleDAG(SD);
    3062      240509 :   return SD;
    3063             : }
    3064             : 
    3065             : llvm::ScheduleDAGSDNodes *
    3066       11742 : llvm::createHybridListDAGScheduler(SelectionDAGISel *IS,
    3067             :                                    CodeGenOpt::Level OptLevel) {
    3068       11742 :   const TargetSubtargetInfo &STI = IS->MF->getSubtarget();
    3069       11742 :   const TargetInstrInfo *TII = STI.getInstrInfo();
    3070       11742 :   const TargetRegisterInfo *TRI = STI.getRegisterInfo();
    3071       11742 :   const TargetLowering *TLI = IS->TLI;
    3072             : 
    3073             :   HybridBURRPriorityQueue *PQ =
    3074       23484 :     new HybridBURRPriorityQueue(*IS->MF, true, false, TII, TRI, TLI);
    3075             : 
    3076       11742 :   ScheduleDAGRRList *SD = new ScheduleDAGRRList(*IS->MF, true, PQ, OptLevel);
    3077       23484 :   PQ->setScheduleDAG(SD);
    3078       11742 :   return SD;
    3079             : }
    3080             : 
    3081             : llvm::ScheduleDAGSDNodes *
    3082       15307 : llvm::createILPListDAGScheduler(SelectionDAGISel *IS,
    3083             :                                 CodeGenOpt::Level OptLevel) {
    3084       15307 :   const TargetSubtargetInfo &STI = IS->MF->getSubtarget();
    3085       15307 :   const TargetInstrInfo *TII = STI.getInstrInfo();
    3086       15307 :   const TargetRegisterInfo *TRI = STI.getRegisterInfo();
    3087       15307 :   const TargetLowering *TLI = IS->TLI;
    3088             : 
    3089             :   ILPBURRPriorityQueue *PQ =
    3090       30614 :     new ILPBURRPriorityQueue(*IS->MF, true, false, TII, TRI, TLI);
    3091       15307 :   ScheduleDAGRRList *SD = new ScheduleDAGRRList(*IS->MF, true, PQ, OptLevel);
    3092       30614 :   PQ->setScheduleDAG(SD);
    3093       15307 :   return SD;
    3094      216918 : }

Generated by: LCOV version 1.13