lib/CodeGen/SelectionDAG/ScheduleDAGSDNodes.cpp

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