LCOV - code coverage report
Current view: top level - lib/CodeGen/SelectionDAG - ScheduleDAGSDNodes.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 382 396 96.5 %
Date: 2018-07-13 00:08:38 Functions: 25 27 92.6 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : //===--- ScheduleDAGSDNodes.cpp - Implement the ScheduleDAGSDNodes class --===//
       2             : //
       3             : //                     The LLVM Compiler Infrastructure
       4             : //
       5             : // This file is distributed under the University of Illinois Open Source
       6             : // License. See LICENSE.TXT for details.
       7             : //
       8             : //===----------------------------------------------------------------------===//
       9             : //
      10             : // This implements the ScheduleDAG class, which is a base class used by
      11             : // scheduling implementation classes.
      12             : //
      13             : //===----------------------------------------------------------------------===//
      14             : 
      15             : #include "ScheduleDAGSDNodes.h"
      16             : #include "InstrEmitter.h"
      17             : #include "SDNodeDbgValue.h"
      18             : #include "llvm/ADT/DenseMap.h"
      19             : #include "llvm/ADT/SmallPtrSet.h"
      20             : #include "llvm/ADT/SmallSet.h"
      21             : #include "llvm/ADT/SmallVector.h"
      22             : #include "llvm/ADT/Statistic.h"
      23             : #include "llvm/CodeGen/MachineInstrBuilder.h"
      24             : #include "llvm/CodeGen/MachineRegisterInfo.h"
      25             : #include "llvm/CodeGen/SelectionDAG.h"
      26             : #include "llvm/CodeGen/TargetInstrInfo.h"
      27             : #include "llvm/CodeGen/TargetLowering.h"
      28             : #include "llvm/CodeGen/TargetRegisterInfo.h"
      29             : #include "llvm/CodeGen/TargetSubtargetInfo.h"
      30             : #include "llvm/Config/llvm-config.h"
      31             : #include "llvm/MC/MCInstrItineraries.h"
      32             : #include "llvm/Support/CommandLine.h"
      33             : #include "llvm/Support/Debug.h"
      34             : #include "llvm/Support/raw_ostream.h"
      35             : using namespace llvm;
      36             : 
      37             : #define DEBUG_TYPE "pre-RA-sched"
      38             : 
      39             : STATISTIC(LoadsClustered, "Number of loads clustered together");
      40             : 
      41             : // This allows the latency-based scheduler to notice high latency instructions
      42             : // without a target itinerary. The choice of number here has more to do with
      43             : // balancing scheduler heuristics than with the actual machine latency.
      44       99743 : static cl::opt<int> HighLatencyCycles(
      45      199486 :   "sched-high-latency-cycles", cl::Hidden, cl::init(10),
      46       99743 :   cl::desc("Roughly estimate the number of cycles that 'long latency'"
      47       99743 :            "instructions take for targets with no itinerary"));
      48             : 
      49      363303 : ScheduleDAGSDNodes::ScheduleDAGSDNodes(MachineFunction &mf)
      50             :     : ScheduleDAG(mf), BB(nullptr), DAG(nullptr),
      51      726606 :       InstrItins(mf.getSubtarget().getInstrItineraryData()) {}
      52             : 
      53             : /// Run - perform scheduling.
      54             : ///
      55      363303 : void ScheduleDAGSDNodes::Run(SelectionDAG *dag, MachineBasicBlock *bb) {
      56      363303 :   BB = bb;
      57      363303 :   DAG = dag;
      58             : 
      59             :   // Clear the scheduler's SUnit DAG.
      60      363303 :   ScheduleDAG::clearDAG();
      61             :   Sequence.clear();
      62             : 
      63             :   // Invoke the target's selection of scheduler.
      64      363303 :   Schedule();
      65      363303 : }
      66             : 
      67             : /// NewSUnit - Creates a new SUnit and return a ptr to it.
      68             : ///
      69     4020057 : SUnit *ScheduleDAGSDNodes::newSUnit(SDNode *N) {
      70             : #ifndef NDEBUG
      71             :   const SUnit *Addr = nullptr;
      72             :   if (!SUnits.empty())
      73             :     Addr = &SUnits[0];
      74             : #endif
      75     8040114 :   SUnits.emplace_back(N, (unsigned)SUnits.size());
      76             :   assert((Addr == nullptr || Addr == &SUnits[0]) &&
      77             :          "SUnits std::vector reallocated on the fly!");
      78     4020057 :   SUnits.back().OrigNode = &SUnits.back();
      79             :   SUnit *SU = &SUnits.back();
      80     4020057 :   const TargetLowering &TLI = DAG->getTargetLoweringInfo();
      81     8039852 :   if (!N ||
      82     6970626 :       (N->isMachineOpcode() &&
      83             :        N->getMachineOpcode() == TargetOpcode::IMPLICIT_DEF))
      84       25932 :     SU->SchedulingPref = Sched::None;
      85             :   else
      86     3994125 :     SU->SchedulingPref = TLI.getSchedulingPreference(N);
      87     4020057 :   return SU;
      88             : }
      89             : 
      90       20442 : SUnit *ScheduleDAGSDNodes::Clone(SUnit *Old) {
      91       20442 :   SUnit *SU = newSUnit(Old->getNode());
      92       20442 :   SU->OrigNode = Old->OrigNode;
      93       20442 :   SU->Latency = Old->Latency;
      94       20442 :   SU->isVRegCycle = Old->isVRegCycle;
      95       20442 :   SU->isCall = Old->isCall;
      96       20442 :   SU->isCallOp = Old->isCallOp;
      97       20442 :   SU->isTwoAddress = Old->isTwoAddress;
      98       20442 :   SU->isCommutable = Old->isCommutable;
      99       20442 :   SU->hasPhysRegDefs = Old->hasPhysRegDefs;
     100       20442 :   SU->hasPhysRegClobbers = Old->hasPhysRegClobbers;
     101       20442 :   SU->isScheduleHigh = Old->isScheduleHigh;
     102       20442 :   SU->isScheduleLow = Old->isScheduleLow;
     103       20442 :   SU->SchedulingPref = Old->SchedulingPref;
     104       20442 :   Old->isCloned = true;
     105       20442 :   return SU;
     106             : }
     107             : 
     108             : /// CheckForPhysRegDependency - Check if the dependency between def and use of
     109             : /// a specified operand is a physical register dependency. If so, returns the
     110             : /// register and the cost of copying the register.
     111     4846841 : static void CheckForPhysRegDependency(SDNode *Def, SDNode *User, unsigned Op,
     112             :                                       const TargetRegisterInfo *TRI,
     113             :                                       const TargetInstrInfo *TII,
     114             :                                       unsigned &PhysReg, int &Cost) {
     115     4846841 :   if (Op != 2 || User->getOpcode() != ISD::CopyToReg)
     116             :     return;
     117             : 
     118     1419946 :   unsigned Reg = cast<RegisterSDNode>(User->getOperand(1))->getReg();
     119      709973 :   if (TargetRegisterInfo::isVirtualRegister(Reg))
     120             :     return;
     121             : 
     122      546618 :   unsigned ResNo = User->getOperand(2).getResNo();
     123     1144898 :   if (Def->getOpcode() == ISD::CopyFromReg &&
     124      103324 :       cast<RegisterSDNode>(Def->getOperand(1))->getReg() == Reg) {
     125        5448 :     PhysReg = Reg;
     126      541170 :   } else if (Def->isMachineOpcode()) {
     127      494956 :     const MCInstrDesc &II = TII->get(Def->getMachineOpcode());
     128     1127867 :     if (ResNo >= II.getNumDefs() &&
     129      137955 :         II.ImplicitDefs[ResNo - II.getNumDefs()] == Reg)
     130      137824 :       PhysReg = Reg;
     131             :   }
     132             : 
     133      546618 :   if (PhysReg != 0) {
     134             :     const TargetRegisterClass *RC =
     135      143272 :         TRI->getMinimalPhysRegClass(Reg, Def->getSimpleValueType(ResNo));
     136      286544 :     Cost = RC->getCopyCost();
     137             :   }
     138             : }
     139             : 
     140             : // Helper for AddGlue to clone node operands.
     141       32923 : static void CloneNodeWithValues(SDNode *N, SelectionDAG *DAG, ArrayRef<EVT> VTs,
     142             :                                 SDValue ExtraOper = SDValue()) {
     143       32923 :   SmallVector<SDValue, 8> Ops(N->op_begin(), N->op_end());
     144       32923 :   if (ExtraOper.getNode())
     145       14876 :     Ops.push_back(ExtraOper);
     146             : 
     147       32923 :   SDVTList VTList = DAG->getVTList(VTs);
     148             :   MachineSDNode::mmo_iterator Begin = nullptr, End = nullptr;
     149             :   MachineSDNode *MN = dyn_cast<MachineSDNode>(N);
     150             : 
     151             :   // Store memory references.
     152             :   if (MN) {
     153       32923 :     Begin = MN->memoperands_begin();
     154       32923 :     End = MN->memoperands_end();
     155             :   }
     156             : 
     157       32923 :   DAG->MorphNodeTo(N, N->getOpcode(), VTList, Ops);
     158             : 
     159             :   // Reset the memory references
     160       32923 :   if (MN)
     161             :     MN->setMemRefs(Begin, End);
     162       32923 : }
     163             : 
     164       56705 : static bool AddGlue(SDNode *N, SDValue Glue, bool AddGlue, SelectionDAG *DAG) {
     165       56705 :   SDNode *GlueDestNode = Glue.getNode();
     166             : 
     167             :   // Don't add glue from a node to itself.
     168       56705 :   if (GlueDestNode == N) return false;
     169             : 
     170             :   // Don't add a glue operand to something that already uses glue.
     171       56698 :   if (GlueDestNode &&
     172       44715 :       N->getOperand(N->getNumOperands()-1).getValueType() == MVT::Glue) {
     173             :     return false;
     174             :   }
     175             :   // Don't add glue to something that already has a glue value.
     176      113384 :   if (N->getValueType(N->getNumValues() - 1) == MVT::Glue) return false;
     177             : 
     178       32896 :   SmallVector<EVT, 4> VTs(N->value_begin(), N->value_end());
     179       32896 :   if (AddGlue)
     180       14903 :     VTs.push_back(MVT::Glue);
     181             : 
     182       32896 :   CloneNodeWithValues(N, DAG, VTs, Glue);
     183             : 
     184             :   return true;
     185             : }
     186             : 
     187             : // Cleanup after unsuccessful AddGlue. Use the standard method of morphing the
     188             : // node even though simply shrinking the value list is sufficient.
     189          27 : static void RemoveUnusedGlue(SDNode *N, SelectionDAG *DAG) {
     190             :   assert((N->getValueType(N->getNumValues() - 1) == MVT::Glue &&
     191             :           !N->hasAnyUseOfValue(N->getNumValues() - 1)) &&
     192             :          "expected an unused glue value");
     193             : 
     194          27 :   CloneNodeWithValues(N, DAG,
     195          54 :                       makeArrayRef(N->value_begin(), N->getNumValues() - 1));
     196          27 : }
     197             : 
     198             : /// ClusterNeighboringLoads - Force nearby loads together by "gluing" them.
     199             : /// This function finds loads of the same base and different offsets. If the
     200             : /// offsets are not far apart (target specific), it add MVT::Glue inputs and
     201             : /// outputs to ensure they are scheduled together and in order. This
     202             : /// optimization may benefit some targets by improving cache locality.
     203      532337 : void ScheduleDAGSDNodes::ClusterNeighboringLoads(SDNode *Node) {
     204             :   SDNode *Chain = nullptr;
     205      532337 :   unsigned NumOps = Node->getNumOperands();
     206     1064674 :   if (Node->getOperand(NumOps-1).getValueType() == MVT::Other)
     207      892354 :     Chain = Node->getOperand(NumOps-1).getNode();
     208      532337 :   if (!Chain)
     209      514317 :     return;
     210             : 
     211             :   // Look for other loads of the same chain. Find loads that are loading from
     212             :   // the same base pointer and different offsets.
     213             :   SmallPtrSet<SDNode*, 16> Visited;
     214             :   SmallVector<int64_t, 4> Offsets;
     215             :   DenseMap<long long, SDNode*> O2SMap;  // Map from offset to SDNode.
     216             :   bool Cluster = false;
     217             :   SDNode *Base = Node;
     218             :   // This algorithm requires a reasonably low use count before finding a match
     219             :   // to avoid uselessly blowing up compile time in large blocks.
     220             :   unsigned UseCount = 0;
     221     3376270 :   for (SDNode::use_iterator I = Chain->use_begin(), E = Chain->use_end();
     222     3376270 :        I != E && UseCount < 100; ++I, ++UseCount) {
     223             :     SDNode *User = *I;
     224     3384271 :     if (User == Node || !Visited.insert(User).second)
     225     3079865 :       continue;
     226             :     int64_t Offset1, Offset2;
     227     4951937 :     if (!TII->areLoadsFromSameBasePtr(Base, User, Offset1, Offset2) ||
     228      304513 :         Offset1 == Offset2)
     229             :       // FIXME: Should be ok if they addresses are identical. But earlier
     230             :       // optimizations really should have eliminated one of the loads.
     231     2171509 :       continue;
     232      304406 :     if (O2SMap.insert(std::make_pair(Offset1, Base)).second)
     233       19727 :       Offsets.push_back(Offset1);
     234      608812 :     O2SMap.insert(std::make_pair(Offset2, User));
     235      304406 :     Offsets.push_back(Offset2);
     236      304406 :     if (Offset2 < Offset1)
     237             :       Base = User;
     238             :     Cluster = true;
     239             :     // Reset UseCount to allow more matches.
     240             :     UseCount = 0;
     241             :   }
     242             : 
     243      446177 :   if (!Cluster)
     244             :     return;
     245             : 
     246             :   // Sort them in increasing order.
     247             :   llvm::sort(Offsets.begin(), Offsets.end());
     248             : 
     249             :   // Check if the loads are close enough.
     250             :   SmallVector<SDNode*, 4> Loads;
     251             :   unsigned NumLoads = 0;
     252       19727 :   int64_t BaseOff = Offsets[0];
     253       39454 :   SDNode *BaseLoad = O2SMap[BaseOff];
     254       19727 :   Loads.push_back(BaseLoad);
     255       58412 :   for (unsigned i = 1, e = Offsets.size(); i != e; ++i) {
     256       90732 :     int64_t Offset = Offsets[i];
     257       90732 :     SDNode *Load = O2SMap[Offset];
     258       45366 :     if (!TII->shouldScheduleLoadsNear(BaseLoad, Load, BaseOff, Offset,NumLoads))
     259             :       break; // Stop right here. Ignore loads that are further away.
     260       38685 :     Loads.push_back(Load);
     261       38685 :     ++NumLoads;
     262             :   }
     263             : 
     264       19727 :   if (NumLoads == 0)
     265             :     return;
     266             : 
     267             :   // Cluster loads by adding MVT::Glue outputs and inputs. This also
     268             :   // ensure they are scheduled in order of increasing addresses.
     269       18020 :   SDNode *Lead = Loads[0];
     270             :   SDValue InGlue = SDValue(nullptr, 0);
     271       18020 :   if (AddGlue(Lead, InGlue, true, DAG))
     272       23228 :     InGlue = SDValue(Lead, Lead->getNumValues() - 1);
     273       56705 :   for (unsigned I = 1, E = Loads.size(); I != E; ++I) {
     274       38685 :     bool OutGlue = I < E - 1;
     275       77370 :     SDNode *Load = Loads[I];
     276             : 
     277             :     // If AddGlue fails, we could leave an unsused glue value. This should not
     278             :     // cause any
     279       38685 :     if (AddGlue(Load, InGlue, OutGlue, DAG)) {
     280       21282 :       if (OutGlue)
     281        6578 :         InGlue = SDValue(Load, Load->getNumValues() - 1);
     282             : 
     283             :       ++LoadsClustered;
     284             :     }
     285       17403 :     else if (!OutGlue && InGlue.getNode())
     286          27 :       RemoveUnusedGlue(InGlue.getNode(), DAG);
     287             :   }
     288             : }
     289             : 
     290             : /// ClusterNodes - Cluster certain nodes which should be scheduled together.
     291             : ///
     292      363289 : void ScheduleDAGSDNodes::ClusterNodes() {
     293    10184703 :   for (SDNode &NI : DAG->allnodes()) {
     294             :     SDNode *Node = &NI;
     295    15748453 :     if (!Node || !Node->isMachineOpcode())
     296     6290328 :       continue;
     297             : 
     298             :     unsigned Opc = Node->getMachineOpcode();
     299     3167797 :     const MCInstrDesc &MCID = TII->get(Opc);
     300     6335594 :     if (MCID.mayLoad())
     301             :       // Cluster loads from "near" addresses into combined SUnits.
     302      532337 :       ClusterNeighboringLoads(Node);
     303             :   }
     304      363289 : }
     305             : 
     306      363289 : void ScheduleDAGSDNodes::BuildSchedUnits() {
     307             :   // During scheduling, the NodeId field of SDNode is used to map SDNodes
     308             :   // to their associated SUnits by holding SUnits table indices. A value
     309             :   // of -1 means the SDNode does not yet have an associated SUnit.
     310             :   unsigned NumNodes = 0;
     311    10184703 :   for (SDNode &NI : DAG->allnodes()) {
     312             :     NI.setNodeId(-1);
     313     9458125 :     ++NumNodes;
     314             :   }
     315             : 
     316             :   // Reserve entries in the vector for each of the SUnits we are creating.  This
     317             :   // ensure that reallocation of the vector won't happen, so SUnit*'s won't get
     318             :   // invalidated.
     319             :   // FIXME: Multiply by 2 because we may clone nodes during scheduling.
     320             :   // This is a temporary workaround.
     321      363289 :   SUnits.reserve(NumNodes * 2);
     322             : 
     323             :   // Add all nodes in depth first order.
     324             :   SmallVector<SDNode*, 64> Worklist;
     325             :   SmallPtrSet<SDNode*, 32> Visited;
     326      363289 :   Worklist.push_back(DAG->getRoot().getNode());
     327      363289 :   Visited.insert(DAG->getRoot().getNode());
     328             : 
     329             :   SmallVector<SUnit*, 8> CallSUnits;
     330     9799240 :   while (!Worklist.empty()) {
     331             :     SDNode *NI = Worklist.pop_back_val();
     332             : 
     333             :     // Add all operands to the worklist unless they've already been added.
     334    27623714 :     for (const SDValue &Op : NI->op_values())
     335    18187763 :       if (Visited.insert(Op.getNode()).second)
     336     9072662 :         Worklist.push_back(Op.getNode());
     337             : 
     338     9435951 :     if (isPassiveNode(NI))  // Leaf node, e.g. a TargetImmediate.
     339    10022904 :       continue;
     340             : 
     341             :     // If this node has already been processed, stop now.
     342     4862821 :     if (NI->getNodeId() != -1) continue;
     343             : 
     344     3986177 :     SUnit *NodeSUnit = newSUnit(NI);
     345             : 
     346             :     // See if anything is glued to this node, if so, add them to glued
     347             :     // nodes.  Nodes can have at most one glue input and one glue output.  Glue
     348             :     // is required to be the last operand and result of a node.
     349             : 
     350             :     // Scan up to find glued preds.
     351             :     SDNode *N = NI;
     352     9702032 :     while (N->getNumOperands() &&
     353     9543338 :            N->getOperand(N->getNumOperands()-1).getValueType() == MVT::Glue) {
     354             :       N = N->getOperand(N->getNumOperands()-1).getNode();
     355             :       assert(N->getNodeId() == -1 && "Node already inserted!");
     356      864839 :       N->setNodeId(NodeSUnit->NodeNum);
     357     1588112 :       if (N->isMachineOpcode() && TII->get(N->getMachineOpcode()).isCall())
     358      173818 :         NodeSUnit->isCall = true;
     359             :     }
     360             : 
     361             :     // Scan down to find any glued succs.
     362             :     N = NI;
     363     8007769 :     while (N->getValueType(N->getNumValues()-1) == MVT::Glue) {
     364      766452 :       SDValue GlueVal(N, N->getNumValues()-1);
     365             : 
     366             :       // There are either zero or one users of the Glue result.
     367             :       bool HasGlueUse = false;
     368      383226 :       for (SDNode::use_iterator UI = N->use_begin(), E = N->use_end();
     369      903638 :            UI != E; ++UI)
     370      532217 :         if (GlueVal.isOperandOf(*UI)) {
     371             :           HasGlueUse = true;
     372             :           assert(N->getNodeId() == -1 && "Node already inserted!");
     373       11805 :           N->setNodeId(NodeSUnit->NodeNum);
     374             :           N = *UI;
     375       30936 :           if (N->isMachineOpcode() && TII->get(N->getMachineOpcode()).isCall())
     376           0 :             NodeSUnit->isCall = true;
     377             :           break;
     378             :         }
     379      383226 :       if (!HasGlueUse) break;
     380             :     }
     381             : 
     382     3986177 :     if (NodeSUnit->isCall)
     383      173818 :       CallSUnits.push_back(NodeSUnit);
     384             : 
     385             :     // Schedule zero-latency TokenFactor below any nodes that may increase the
     386             :     // schedule height. Otherwise, ancestors of the TokenFactor may appear to
     387             :     // have false stalls.
     388     3986177 :     if (NI->getOpcode() == ISD::TokenFactor)
     389      215320 :       NodeSUnit->isScheduleLow = true;
     390             : 
     391             :     // If there are glue operands involved, N is now the bottom-most node
     392             :     // of the sequence of nodes that are glued together.
     393             :     // Update the SUnit.
     394     3986177 :     NodeSUnit->setNode(N);
     395             :     assert(N->getNodeId() == -1 && "Node already inserted!");
     396     3986177 :     N->setNodeId(NodeSUnit->NodeNum);
     397             : 
     398             :     // Compute NumRegDefsLeft. This must be done before AddSchedEdges.
     399     3986177 :     InitNumRegDefsLeft(NodeSUnit);
     400             : 
     401             :     // Assign the Latency field of NodeSUnit using target-provided information.
     402     3986177 :     computeLatency(NodeSUnit);
     403             :   }
     404             : 
     405             :   // Find all call operands.
     406      537107 :   while (!CallSUnits.empty()) {
     407             :     SUnit *SU = CallSUnits.pop_back_val();
     408      173818 :     for (const SDNode *SUNode = SU->getNode(); SUNode;
     409             :          SUNode = SUNode->getGluedNode()) {
     410      715719 :       if (SUNode->getOpcode() != ISD::CopyToReg)
     411      395089 :         continue;
     412      320630 :       SDNode *SrcN = SUNode->getOperand(2).getNode();
     413      320630 :       if (isPassiveNode(SrcN)) continue;   // Not scheduled.
     414      255175 :       SUnit *SrcSU = &SUnits[SrcN->getNodeId()];
     415      255175 :       SrcSU->isCallOp = true;
     416             :     }
     417             :   }
     418      363289 : }
     419             : 
     420      363289 : void ScheduleDAGSDNodes::AddSchedEdges() {
     421      363289 :   const TargetSubtargetInfo &ST = MF.getSubtarget();
     422             : 
     423             :   // Check to see if the scheduler cares about latencies.
     424      363289 :   bool UnitLatencies = forceUnitLatencies();
     425             : 
     426             :   // Pass 2: add the preds, succs, etc.
     427     4712755 :   for (unsigned su = 0, e = SUnits.size(); su != e; ++su) {
     428     3986177 :     SUnit *SU = &SUnits[su];
     429     3986177 :     SDNode *MainNode = SU->getNode();
     430             : 
     431     3986177 :     if (MainNode->isMachineOpcode()) {
     432             :       unsigned Opc = MainNode->getMachineOpcode();
     433     2913912 :       const MCInstrDesc &MCID = TII->get(Opc);
     434    37808337 :       for (unsigned i = 0; i != MCID.getNumOperands(); ++i) {
     435             :         if (MCID.getOperandConstraint(i, MCOI::TIED_TO) != -1) {
     436      265059 :           SU->isTwoAddress = true;
     437      265059 :           break;
     438             :         }
     439             :       }
     440     5827824 :       if (MCID.isCommutable())
     441      145166 :         SU->isCommutable = true;
     442             :     }
     443             : 
     444             :     // Find all predecessors and successors of the group.
     445     4862821 :     for (SDNode *N = SU->getNode(); N; N = N->getGluedNode()) {
     446     8027502 :       if (N->isMachineOpcode() &&
     447     9494043 :           TII->get(N->getMachineOpcode()).getImplicitDefs()) {
     448      765826 :         SU->hasPhysRegClobbers = true;
     449      765826 :         unsigned NumUsed = InstrEmitter::CountResults(N);
     450     1374751 :         while (NumUsed != 0 && !N->hasAnyUseOfValue(NumUsed - 1))
     451             :           --NumUsed;    // Skip over unused values at the end.
     452     3063304 :         if (NumUsed > TII->get(N->getMachineOpcode()).getNumDefs())
     453      116462 :           SU->hasPhysRegDefs = true;
     454             :       }
     455             : 
     456    46101168 :       for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) {
     457    36375526 :         SDNode *OpN = N->getOperand(i).getNode();
     458    31528685 :         if (isPassiveNode(OpN)) continue;   // Not scheduled.
     459     6524415 :         SUnit *OpSU = &SUnits[OpN->getNodeId()];
     460             :         assert(OpSU && "Node has no SUnit!");
     461     6524415 :         if (OpSU == SU) continue;           // In the same group.
     462             : 
     463     4846841 :         EVT OpVT = N->getOperand(i).getValueType();
     464             :         assert(OpVT != MVT::Glue && "Glued nodes should be in same sunit!");
     465             :         bool isChain = OpVT == MVT::Other;
     466             : 
     467     4846841 :         unsigned PhysReg = 0;
     468     4846841 :         int Cost = 1;
     469             :         // Determine if this is a physical register dependency.
     470     4846841 :         CheckForPhysRegDependency(OpN, N, i, TRI, TII, PhysReg, Cost);
     471             :         assert((PhysReg == 0 || !isChain) &&
     472             :                "Chain dependence via physreg data?");
     473             :         // FIXME: See ScheduleDAGSDNodes::EmitCopyFromReg. For now, scheduler
     474             :         // emits a copy from the physical register to a virtual register unless
     475             :         // it requires a cross class copy (cost < 0). That means we are only
     476             :         // treating "expensive to copy" register dependency as physical register
     477             :         // dependency. This may change in the future though.
     478     4846841 :         if (Cost >= 0 && !StressSched)
     479     4708540 :           PhysReg = 0;
     480             : 
     481             :         // If this is a ctrl dep, latency is 1.
     482     4846841 :         unsigned OpLatency = isChain ? 1 : OpSU->Latency;
     483             :         // Special-case TokenFactor chains as zero-latency.
     484     4846841 :         if(isChain && OpN->getOpcode() == ISD::TokenFactor)
     485             :           OpLatency = 0;
     486             : 
     487             :         SDep Dep = isChain ? SDep(OpSU, SDep::Barrier)
     488     7807840 :           : SDep(OpSU, SDep::Data, PhysReg);
     489             :         Dep.setLatency(OpLatency);
     490     4846841 :         if (!isChain && !UnitLatencies) {
     491      181338 :           computeOperandLatency(OpN, N, i, Dep);
     492      181338 :           ST.adjustSchedDependency(OpSU, SU, Dep);
     493             :         }
     494             : 
     495     4925344 :         if (!SU->addPred(Dep) && !Dep.isCtrl() && OpSU->NumRegDefsLeft > 1) {
     496             :           // Multiple register uses are combined in the same SUnit. For example,
     497             :           // we could have a set of glued nodes with all their defs consumed by
     498             :           // another set of glued nodes. Register pressure tracking sees this as
     499             :           // a single use, so to keep pressure balanced we reduce the defs.
     500             :           //
     501             :           // We can't tell (without more book-keeping) if this results from
     502             :           // glued nodes or duplicate operands. As long as we don't reduce
     503             :           // NumRegDefsLeft to zero, we handle the common cases well.
     504        7380 :           --OpSU->NumRegDefsLeft;
     505             :         }
     506             :       }
     507             :     }
     508             :   }
     509      363289 : }
     510             : 
     511             : /// BuildSchedGraph - Build the SUnit graph from the selection dag that we
     512             : /// are input.  This SUnit graph is similar to the SelectionDAG, but
     513             : /// excludes nodes that aren't interesting to scheduling, and represents
     514             : /// glued together nodes with a single SUnit.
     515      363289 : void ScheduleDAGSDNodes::BuildSchedGraph(AliasAnalysis *AA) {
     516             :   // Cluster certain nodes which should be scheduled together.
     517      363289 :   ClusterNodes();
     518             :   // Populate the SUnits array.
     519      363289 :   BuildSchedUnits();
     520             :   // Compute all the scheduling dependencies between nodes.
     521      363289 :   AddSchedEdges();
     522      363289 : }
     523             : 
     524             : // Initialize NumNodeDefs for the current Node's opcode.
     525     5841492 : void ScheduleDAGSDNodes::RegDefIter::InitNodeNumDefs() {
     526             :   // Check for phys reg copy.
     527     5841492 :   if (!Node)
     528     2060863 :     return;
     529             : 
     530     5841492 :   if (!Node->isMachineOpcode()) {
     531     2033881 :     if (Node->getOpcode() == ISD::CopyFromReg)
     532      815026 :       NodeNumDefs = 1;
     533             :     else
     534     1218855 :       NodeNumDefs = 0;
     535             :     return;
     536             :   }
     537             :   unsigned POpc = Node->getMachineOpcode();
     538     3807611 :   if (POpc == TargetOpcode::IMPLICIT_DEF) {
     539             :     // No register need be allocated for this.
     540       26869 :     NodeNumDefs = 0;
     541       26869 :     return;
     542             :   }
     543     3780742 :   if (POpc == TargetOpcode::PATCHPOINT &&
     544         176 :       Node->getValueType(0) == MVT::Other) {
     545             :     // PATCHPOINT is defined to have one result, but it might really have none
     546             :     // if we're not using CallingConv::AnyReg. Don't mistake the chain for a
     547             :     // real definition.
     548         113 :     NodeNumDefs = 0;
     549         113 :     return;
     550             :   }
     551    11341887 :   unsigned NRegDefs = SchedDAG->TII->get(Node->getMachineOpcode()).getNumDefs();
     552             :   // Some instructions define regs that are not represented in the selection DAG
     553             :   // (e.g. unused flags). See tMOVi8. Make sure we don't access past NumValues.
     554    11341887 :   NodeNumDefs = std::min(Node->getNumValues(), NRegDefs);
     555     3780629 :   DefIdx = 0;
     556             : }
     557             : 
     558             : // Construct a RegDefIter for this SUnit and find the first valid value.
     559     4792457 : ScheduleDAGSDNodes::RegDefIter::RegDefIter(const SUnit *SU,
     560     4792457 :                                            const ScheduleDAGSDNodes *SD)
     561     4792457 :   : SchedDAG(SD), Node(SU->getNode()), DefIdx(0), NodeNumDefs(0) {
     562     4792457 :   InitNodeNumDefs();
     563     4792457 :   Advance();
     564     4792457 : }
     565             : 
     566             : // Advance to the next valid value defined by the SUnit.
     567     7582524 : void ScheduleDAGSDNodes::RegDefIter::Advance() {
     568     9680594 :   for (;Node;) { // Visit all glued nodes.
     569     8706271 :     for (;DefIdx < NodeNumDefs; ++DefIdx) {
     570     2994810 :       if (!Node->hasAnyUseOfValue(DefIdx))
     571             :         continue;
     572     5914908 :       ValueType = Node->getSimpleValueType(DefIdx);
     573     2957454 :       ++DefIdx;
     574     2957454 :       return; // Found a normal regdef.
     575             :     }
     576    11348210 :     Node = Node->getGluedNode();
     577     5674105 :     if (!Node) {
     578             :       return; // No values left to visit.
     579             :     }
     580     1049035 :     InitNodeNumDefs();
     581             :   }
     582             : }
     583             : 
     584     3999353 : void ScheduleDAGSDNodes::InitNumRegDefsLeft(SUnit *SU) {
     585             :   assert(SU->NumRegDefsLeft == 0 && "expect a new node");
     586     6209580 :   for (RegDefIter I(SU, this); I.IsValid(); I.Advance()) {
     587             :     assert(SU->NumRegDefsLeft < USHRT_MAX && "overflow is ok but unexpected");
     588     2210227 :     ++SU->NumRegDefsLeft;
     589             :   }
     590     3999353 : }
     591             : 
     592     3999353 : void ScheduleDAGSDNodes::computeLatency(SUnit *SU) {
     593     3999353 :   SDNode *N = SU->getNode();
     594             : 
     595             :   // TokenFactor operands are considered zero latency, and some schedulers
     596             :   // (e.g. Top-Down list) may rely on the fact that operand latency is nonzero
     597             :   // whenever node latency is nonzero.
     598     3999353 :   if (N && N->getOpcode() == ISD::TokenFactor) {
     599      215320 :     SU->Latency = 0;
     600      215320 :     return;
     601             :   }
     602             : 
     603             :   // Check to see if the scheduler cares about latencies.
     604     3784033 :   if (forceUnitLatencies()) {
     605     3569676 :     SU->Latency = 1;
     606     3569676 :     return;
     607             :   }
     608             : 
     609      214357 :   if (!InstrItins || InstrItins->isEmpty()) {
     610      217389 :     if (N && N->isMachineOpcode() &&
     611      192208 :         TII->isHighLatencyDef(N->getMachineOpcode()))
     612           0 :       SU->Latency = HighLatencyCycles;
     613             :     else
     614      121285 :       SU->Latency = 1;
     615             :     return;
     616             :   }
     617             : 
     618             :   // Compute the latency for the node.  We use the sum of the latencies for
     619             :   // all nodes glued together into this SUnit.
     620       93072 :   SU->Latency = 0;
     621      214723 :   for (SDNode *N = SU->getNode(); N; N = N->getGluedNode())
     622      121651 :     if (N->isMachineOpcode())
     623       78513 :       SU->Latency += TII->getInstrLatency(InstrItins, N);
     624             : }
     625             : 
     626      181338 : void ScheduleDAGSDNodes::computeOperandLatency(SDNode *Def, SDNode *Use,
     627             :                                                unsigned OpIdx, SDep& dep) const{
     628             :   // Check to see if the scheduler cares about latencies.
     629      181338 :   if (forceUnitLatencies())
     630             :     return;
     631             : 
     632      181338 :   if (dep.getKind() != SDep::Data)
     633             :     return;
     634             : 
     635      362676 :   unsigned DefIdx = Use->getOperand(OpIdx).getResNo();
     636      181338 :   if (Use->isMachineOpcode())
     637             :     // Adjust the use operand index by num of defs.
     638      558372 :     OpIdx += TII->get(Use->getMachineOpcode()).getNumDefs();
     639      181338 :   int Latency = TII->getOperandLatency(InstrItins, Def, DefIdx, Use, OpIdx);
     640      188090 :   if (Latency > 1 && Use->getOpcode() == ISD::CopyToReg &&
     641        6752 :       !BB->succ_empty()) {
     642         536 :     unsigned Reg = cast<RegisterSDNode>(Use->getOperand(1))->getReg();
     643         268 :     if (TargetRegisterInfo::isVirtualRegister(Reg))
     644             :       // This copy is a liveout value. It is likely coalesced, so reduce the
     645             :       // latency so not to penalize the def.
     646             :       // FIXME: need target specific adjustment here?
     647          85 :       Latency = (Latency > 1) ? Latency - 1 : 1;
     648             :   }
     649      181338 :   if (Latency >= 0)
     650       60902 :     dep.setLatency(Latency);
     651             : }
     652             : 
     653           0 : void ScheduleDAGSDNodes::dumpNode(const SUnit *SU) const {
     654             :   // Cannot completely remove virtual function even in release mode.
     655             : #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
     656             :   if (!SU->getNode()) {
     657             :     dbgs() << "PHYS REG COPY\n";
     658             :     return;
     659             :   }
     660             : 
     661             :   SU->getNode()->dump(DAG);
     662             :   dbgs() << "\n";
     663             :   SmallVector<SDNode *, 4> GluedNodes;
     664             :   for (SDNode *N = SU->getNode()->getGluedNode(); N; N = N->getGluedNode())
     665             :     GluedNodes.push_back(N);
     666             :   while (!GluedNodes.empty()) {
     667             :     dbgs() << "    ";
     668             :     GluedNodes.back()->dump(DAG);
     669             :     dbgs() << "\n";
     670             :     GluedNodes.pop_back();
     671             :   }
     672             : #endif
     673           0 : }
     674             : 
     675             : #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
     676             : void ScheduleDAGSDNodes::dumpSchedule() const {
     677             :   for (unsigned i = 0, e = Sequence.size(); i != e; i++) {
     678             :     if (SUnit *SU = Sequence[i])
     679             :       SU->dump(this);
     680             :     else
     681             :       dbgs() << "**** NOOP ****\n";
     682             :   }
     683             : }
     684             : #endif
     685             : 
     686             : #ifndef NDEBUG
     687             : /// VerifyScheduledSequence - Verify that all SUnits were scheduled and that
     688             : /// their state is consistent with the nodes listed in Sequence.
     689             : ///
     690             : void ScheduleDAGSDNodes::VerifyScheduledSequence(bool isBottomUp) {
     691             :   unsigned ScheduledNodes = ScheduleDAG::VerifyScheduledDAG(isBottomUp);
     692             :   unsigned Noops = 0;
     693             :   for (unsigned i = 0, e = Sequence.size(); i != e; ++i)
     694             :     if (!Sequence[i])
     695             :       ++Noops;
     696             :   assert(Sequence.size() - Noops == ScheduledNodes &&
     697             :          "The number of nodes scheduled doesn't match the expected number!");
     698             : }
     699             : #endif // NDEBUG
     700             : 
     701             : /// ProcessSDDbgValues - Process SDDbgValues associated with this node.
     702             : static void
     703       56183 : ProcessSDDbgValues(SDNode *N, SelectionDAG *DAG, InstrEmitter &Emitter,
     704             :                    SmallVectorImpl<std::pair<unsigned, MachineInstr*> > &Orders,
     705             :                    DenseMap<SDValue, unsigned> &VRBaseMap, unsigned Order) {
     706       56183 :   if (!N->getHasDebugValue())
     707             :     return;
     708             : 
     709             :   // Opportunistically insert immediate dbg_value uses, i.e. those with the same
     710             :   // source order number as N.
     711        4671 :   MachineBasicBlock *BB = Emitter.getBlock();
     712             :   MachineBasicBlock::iterator InsertPos = Emitter.getInsertPos();
     713       29782 :   for (auto DV : DAG->GetDbgValues(N)) {
     714       10220 :     if (DV->isInvalidated())
     715             :       continue;
     716       10220 :     unsigned DVOrder = DV->getOrder();
     717       10220 :     if (!Order || DVOrder == Order) {
     718        9749 :       MachineInstr *DbgMI = Emitter.EmitDbgValue(DV, VRBaseMap);
     719        9749 :       if (DbgMI) {
     720       19498 :         Orders.push_back({DVOrder, DbgMI});
     721             :         BB->insert(InsertPos, DbgMI);
     722             :       }
     723             :       DV->setIsInvalidated();
     724             :     }
     725             :   }
     726             : }
     727             : 
     728             : // ProcessSourceNode - Process nodes with source order numbers. These are added
     729             : // to a vector which EmitSchedule uses to determine how to insert dbg_value
     730             : // instructions in the right order.
     731             : static void
     732       60356 : ProcessSourceNode(SDNode *N, SelectionDAG *DAG, InstrEmitter &Emitter,
     733             :                   DenseMap<SDValue, unsigned> &VRBaseMap,
     734             :                   SmallVectorImpl<std::pair<unsigned, MachineInstr*> > &Orders,
     735             :                   SmallSet<unsigned, 8> &Seen) {
     736       60356 :   unsigned Order = N->getIROrder();
     737       60356 :   if (!Order || !Seen.insert(Order).second) {
     738             :     // Process any valid SDDbgValues even if node does not have any order
     739             :     // assigned.
     740       34858 :     ProcessSDDbgValues(N, DAG, Emitter, Orders, VRBaseMap, 0);
     741       73889 :     return;
     742             :   }
     743             : 
     744       25498 :   MachineBasicBlock *BB = Emitter.getBlock();
     745             :   auto IP = Emitter.getInsertPos();
     746       25498 :   if (IP == BB->begin() || BB->back().isPHI() ||
     747             :       // Fast-isel may have inserted some instructions, in which case the
     748             :       // BB->back().isPHI() test will not fire when we want it to.
     749             :       std::prev(IP)->isPHI()) {
     750             :     // Did not insert any instruction.
     751        8346 :     Orders.push_back({Order, (MachineInstr *)nullptr});
     752        4173 :     return;
     753             :   }
     754             : 
     755       42650 :   Orders.push_back({Order, &*std::prev(IP)});
     756       21325 :   ProcessSDDbgValues(N, DAG, Emitter, Orders, VRBaseMap, Order);
     757             : }
     758             : 
     759         262 : void ScheduleDAGSDNodes::
     760             : EmitPhysRegCopy(SUnit *SU, DenseMap<SUnit*, unsigned> &VRBaseMap,
     761             :                 MachineBasicBlock::iterator InsertPos) {
     762           0 :   for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
     763         262 :        I != E; ++I) {
     764         262 :     if (I->isCtrl()) continue;  // ignore chain preds
     765         262 :     if (I->getSUnit()->CopyDstRC) {
     766             :       // Copy to physical register.
     767         131 :       DenseMap<SUnit*, unsigned>::iterator VRI = VRBaseMap.find(I->getSUnit());
     768             :       assert(VRI != VRBaseMap.end() && "Node emitted out of order - late");
     769             :       // Find the destination physical register.
     770             :       unsigned Reg = 0;
     771          12 :       for (SUnit::const_succ_iterator II = SU->Succs.begin(),
     772         143 :              EE = SU->Succs.end(); II != EE; ++II) {
     773         143 :         if (II->isCtrl()) continue;  // ignore chain preds
     774         142 :         if (II->getReg()) {
     775             :           Reg = II->getReg();
     776             :           break;
     777             :         }
     778             :       }
     779         524 :       BuildMI(*BB, InsertPos, DebugLoc(), TII->get(TargetOpcode::COPY), Reg)
     780         131 :         .addReg(VRI->second);
     781             :     } else {
     782             :       // Copy from physical register.
     783             :       assert(I->getReg() && "Unknown physical register!");
     784         262 :       unsigned VRBase = MRI.createVirtualRegister(SU->CopyDstRC);
     785         262 :       bool isNew = VRBaseMap.insert(std::make_pair(SU, VRBase)).second;
     786             :       (void)isNew; // Silence compiler warning.
     787             :       assert(isNew && "Node emitted out of order - early");
     788         524 :       BuildMI(*BB, InsertPos, DebugLoc(), TII->get(TargetOpcode::COPY), VRBase)
     789         131 :         .addReg(I->getReg());
     790             :     }
     791             :     break;
     792             :   }
     793         262 : }
     794             : 
     795             : /// EmitSchedule - Emit the machine code in scheduled order. Return the new
     796             : /// InsertPos and MachineBasicBlock that contains this insertion
     797             : /// point. ScheduleDAGSDNodes holds a BB pointer for convenience, but this does
     798             : /// not necessarily refer to returned BB. The emitter may split blocks.
     799      363289 : MachineBasicBlock *ScheduleDAGSDNodes::
     800             : EmitSchedule(MachineBasicBlock::iterator &InsertPos) {
     801      363289 :   InstrEmitter Emitter(BB, InsertPos);
     802             :   DenseMap<SDValue, unsigned> VRBaseMap;
     803             :   DenseMap<SUnit*, unsigned> CopyVRBaseMap;
     804             :   SmallVector<std::pair<unsigned, MachineInstr*>, 32> Orders;
     805      363289 :   SmallSet<unsigned, 8> Seen;
     806      363289 :   bool HasDbg = DAG->hasDebugValues();
     807             : 
     808             :   // If this is the first BB, emit byval parameter dbg_value's.
     809      368233 :   if (HasDbg && BB->getParent()->begin() == MachineFunction::iterator(BB)) {
     810             :     SDDbgInfo::DbgIterator PDI = DAG->ByvalParmDbgBegin();
     811             :     SDDbgInfo::DbgIterator PDE = DAG->ByvalParmDbgEnd();
     812         449 :     for (; PDI != PDE; ++PDI) {
     813           6 :       MachineInstr *DbgMI= Emitter.EmitDbgValue(*PDI, VRBaseMap);
     814           6 :       if (DbgMI)
     815           6 :         BB->insert(InsertPos, DbgMI);
     816             :     }
     817             :   }
     818             : 
     819     4740047 :   for (unsigned i = 0, e = Sequence.size(); i != e; i++) {
     820     8026938 :     SUnit *SU = Sequence[i];
     821     4013469 :     if (!SU) {
     822             :       // Null SUnit* is a noop.
     823           0 :       TII->insertNoop(*Emitter.getBlock(), InsertPos);
     824         262 :       continue;
     825             :     }
     826             : 
     827             :     // For pre-regalloc scheduling, create instructions corresponding to the
     828             :     // SDNode and any glued SDNodes and append them to the block.
     829     4013731 :     if (!SU->getNode()) {
     830             :       // Emit a copy.
     831         262 :       EmitPhysRegCopy(SU, CopyVRBaseMap, InsertPos);
     832         262 :       continue;
     833             :     }
     834             : 
     835             :     SmallVector<SDNode *, 4> GluedNodes;
     836     9779706 :     for (SDNode *N = SU->getNode()->getGluedNode(); N; N = N->getGluedNode())
     837      876646 :       GluedNodes.push_back(N);
     838     4889853 :     while (!GluedNodes.empty()) {
     839      876646 :       SDNode *N = GluedNodes.back();
     840      876646 :       Emitter.EmitNode(N, SU->OrigNode != SU, SU->isCloned, VRBaseMap);
     841             :       // Remember the source order of the inserted instruction.
     842      876646 :       if (HasDbg)
     843       10434 :         ProcessSourceNode(N, DAG, Emitter, VRBaseMap, Orders, Seen);
     844             :       GluedNodes.pop_back();
     845             :     }
     846     4013207 :     Emitter.EmitNode(SU->getNode(), SU->OrigNode != SU, SU->isCloned,
     847             :                      VRBaseMap);
     848             :     // Remember the source order of the inserted instruction.
     849     4013207 :     if (HasDbg)
     850       49922 :       ProcessSourceNode(SU->getNode(), DAG, Emitter, VRBaseMap, Orders,
     851             :                         Seen);
     852             :   }
     853             : 
     854             :   // Insert all the dbg_values which have not already been inserted in source
     855             :   // order sequence.
     856      363289 :   if (HasDbg) {
     857        4944 :     MachineBasicBlock::iterator BBBegin = BB->getFirstNonPHI();
     858             : 
     859             :     // Sort the source order instructions and use the order to insert debug
     860             :     // values. Use stable_sort so that DBG_VALUEs are inserted in the same order
     861             :     // regardless of the host's implementation fo std::sort.
     862             :     std::stable_sort(Orders.begin(), Orders.end(), less_first());
     863        4944 :     std::stable_sort(DAG->DbgBegin(), DAG->DbgEnd(),
     864             :                      [](const SDDbgValue *LHS, const SDDbgValue *RHS) {
     865       77406 :                        return LHS->getOrder() < RHS->getOrder();
     866             :                      });
     867             : 
     868        4944 :     SDDbgInfo::DbgIterator DI = DAG->DbgBegin();
     869             :     SDDbgInfo::DbgIterator DE = DAG->DbgEnd();
     870             :     // Now emit the rest according to source order.
     871             :     unsigned LastOrder = 0;
     872       33782 :     for (unsigned i = 0, e = Orders.size(); i != e && DI != DE; ++i) {
     873       57676 :       unsigned Order = Orders[i].first;
     874       28838 :       MachineInstr *MI = Orders[i].second;
     875             :       // Insert all SDDbgValue's whose order(s) are before "Order".
     876       28838 :       if (!MI)
     877        4171 :         continue;
     878       91533 :       for (; DI != DE; ++DI) {
     879       53476 :         if ((*DI)->getOrder() < LastOrder || (*DI)->getOrder() >= Order)
     880             :           break;
     881       33433 :         if ((*DI)->isInvalidated())
     882       19291 :           continue;
     883             : 
     884       14142 :         MachineInstr *DbgMI = Emitter.EmitDbgValue(*DI, VRBaseMap);
     885       14142 :         if (DbgMI) {
     886       14142 :           if (!LastOrder)
     887             :             // Insert to start of the BB (after PHIs).
     888        7787 :             BB->insert(BBBegin, DbgMI);
     889             :           else {
     890             :             // Insert at the instruction, which may be in a different
     891             :             // block, if the block was split by a custom inserter.
     892             :             MachineBasicBlock::iterator Pos = MI;
     893        6355 :             MI->getParent()->insert(Pos, DbgMI);
     894             :           }
     895             :         }
     896             :       }
     897             :       LastOrder = Order;
     898             :     }
     899             :     // Add trailing DbgValue's before the terminator. FIXME: May want to add
     900             :     // some of them before one or more conditional branches?
     901             :     SmallVector<MachineInstr*, 8> DbgMIs;
     902        6322 :     for (; DI != DE; ++DI) {
     903         689 :       if ((*DI)->isInvalidated())
     904         385 :         continue;
     905             :       assert((*DI)->getOrder() >= LastOrder &&
     906             :              "emitting DBG_VALUE out of order");
     907         304 :       if (MachineInstr *DbgMI = Emitter.EmitDbgValue(*DI, VRBaseMap))
     908         304 :         DbgMIs.push_back(DbgMI);
     909             :     }
     910             : 
     911        4944 :     MachineBasicBlock *InsertBB = Emitter.getBlock();
     912        4944 :     MachineBasicBlock::iterator Pos = InsertBB->getFirstTerminator();
     913             :     InsertBB->insert(Pos, DbgMIs.begin(), DbgMIs.end());
     914             : 
     915        4944 :     SDDbgInfo::DbgLabelIterator DLI = DAG->DbgLabelBegin();
     916             :     SDDbgInfo::DbgLabelIterator DLE = DAG->DbgLabelEnd();
     917             :     // Now emit the rest according to source order.
     918             :     LastOrder = 0;
     919       13198 :     for (const auto &InstrOrder : Orders) {
     920        8971 :       unsigned Order = InstrOrder.first;
     921        8971 :       MachineInstr *MI = InstrOrder.second;
     922        8971 :       if (!MI)
     923        4127 :         continue;
     924             : 
     925             :       // Insert all SDDbgLabel's whose order(s) are before "Order".
     926           0 :       for (; DLI != DLE &&
     927        4844 :              (*DLI)->getOrder() >= LastOrder && (*DLI)->getOrder() < Order;
     928             :              ++DLI) {
     929           0 :         MachineInstr *DbgMI = Emitter.EmitDbgLabel(*DLI);
     930           0 :         if (DbgMI) {
     931           0 :           if (!LastOrder)
     932             :             // Insert to start of the BB (after PHIs).
     933           0 :             BB->insert(BBBegin, DbgMI);
     934             :           else {
     935             :             // Insert at the instruction, which may be in a different
     936             :             // block, if the block was split by a custom inserter.
     937             :             MachineBasicBlock::iterator Pos = MI;
     938           0 :             MI->getParent()->insert(Pos, DbgMI);
     939             :           }
     940             :         }
     941             :       }
     942        4844 :       if (DLI == DLE)
     943             :         break;
     944             : 
     945             :       LastOrder = Order;
     946             :     }
     947             :   }
     948             : 
     949      363289 :   InsertPos = Emitter.getInsertPos();
     950      726578 :   return Emitter.getBlock();
     951             : }
     952             : 
     953             : /// Return the basic block label.
     954           0 : std::string ScheduleDAGSDNodes::getDAGName() const {
     955           0 :   return "sunit-dag." + BB->getFullName();
     956      299229 : }

Generated by: LCOV version 1.13