lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp

   1 //===---- ScheduleDAGList.cpp - Implement a list scheduler for isel DAG ---===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by Evan Cheng and is distributed under the
   6 // University of Illinois Open Source License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This implements bottom-up and top-down list schedulers, using standard
  11 // algorithms.  The basic approach uses a priority queue of available nodes to
  12 // schedule.  One at a time, nodes are taken from the priority queue (thus in
  13 // priority order), checked for legality to schedule, and emitted if legal.
  14 //
  15 // Nodes may not be legal to schedule either due to structural hazards (e.g.
  16 // pipeline or resource constraints) or because an input to the instruction has
  17 // not completed execution.
  18 //
  19 //===----------------------------------------------------------------------===//
  20
  21 #define DEBUG_TYPE "sched"
  22 #include "llvm/CodeGen/ScheduleDAG.h"
  23 #include "llvm/Target/TargetMachine.h"
  24 #include "llvm/Target/TargetInstrInfo.h"
  25 #include "llvm/Support/Debug.h"
  26 #include "llvm/ADT/Statistic.h"
  27 #include <climits>
  28 #include <iostream>
  29 #include <queue>
  30 #include <set>
  31 #include <vector>
  32 using namespace llvm;
  33
  34 namespace {
  35   Statistic<> NumNoops ("scheduler", "Number of noops inserted");
  36   Statistic<> NumStalls("scheduler", "Number of pipeline stalls");
  37
  38   /// SUnit - Scheduling unit. It's an wrapper around either a single SDNode or
  39   /// a group of nodes flagged together.
  40   struct SUnit {
  41     SDNode *Node;                       // Representative node.
  42     std::vector<SDNode*> FlaggedNodes;  // All nodes flagged to Node.
  43     std::set<SUnit*> Preds;             // All real predecessors.
  44     std::set<SUnit*> ChainPreds;        // All chain predecessors.
  45     std::set<SUnit*> Succs;             // All real successors.
  46     std::set<SUnit*> ChainSuccs;        // All chain successors.
  47     short NumPredsLeft;                 // # of preds not scheduled.
  48     short NumSuccsLeft;                 // # of succs not scheduled.
  49     short NumChainPredsLeft;            // # of chain preds not scheduled.
  50     short NumChainSuccsLeft;            // # of chain succs not scheduled.
  51     int SethiUllman;                    // Sethi Ullman number.
  52     bool isTwoAddress     : 1;          // Is a two-address instruction.
  53     bool isDefNUseOperand : 1;          // Is a def&use operand.
  54     unsigned short Latency;             // Node latency.
  55     unsigned CycleBound;                // Upper/lower cycle to be scheduled at.
  56
  57     SUnit(SDNode *node)
  58       : Node(node), NumPredsLeft(0), NumSuccsLeft(0),
  59       NumChainPredsLeft(0), NumChainSuccsLeft(0),
  60       SethiUllman(INT_MIN),
  61       isTwoAddress(false), isDefNUseOperand(false),
  62       Latency(0), CycleBound(0) {}
  63
  64     void dump(const SelectionDAG *G, bool All=true) const;
  65   };
  66 }
  67
  68 void SUnit::dump(const SelectionDAG *G, bool All) const {
  69   std::cerr << "SU: ";
  70   Node->dump(G);
  71   std::cerr << "\n";
  72   if (FlaggedNodes.size() != 0) {
  73     for (unsigned i = 0, e = FlaggedNodes.size(); i != e; i++) {
  74       std::cerr << "    ";
  75       FlaggedNodes[i]->dump(G);
  76       std::cerr << "\n";
  77     }
  78   }
  79
  80   if (All) {
  81     std::cerr << "  # preds left       : " << NumPredsLeft << "\n";
  82     std::cerr << "  # succs left       : " << NumSuccsLeft << "\n";
  83     std::cerr << "  # chain preds left : " << NumChainPredsLeft << "\n";
  84     std::cerr << "  # chain succs left : " << NumChainSuccsLeft << "\n";
  85     std::cerr << "  Latency            : " << Latency << "\n";
  86     std::cerr << "  SethiUllman        : " << SethiUllman << "\n";
  87
  88     if (Preds.size() != 0) {
  89       std::cerr << "  Predecessors:\n";
  90       for (std::set<SUnit*>::const_iterator I = Preds.begin(),
  91              E = Preds.end(); I != E; ++I) {
  92         std::cerr << "    ";
  93         (*I)->dump(G, false);
  94       }
  95     }
  96     if (ChainPreds.size() != 0) {
  97       std::cerr << "  Chained Preds:\n";
  98       for (std::set<SUnit*>::const_iterator I = ChainPreds.begin(),
  99              E = ChainPreds.end(); I != E; ++I) {
 100         std::cerr << "    ";
 101         (*I)->dump(G, false);
 102       }
 103     }
 104     if (Succs.size() != 0) {
 105       std::cerr << "  Successors:\n";
 106       for (std::set<SUnit*>::const_iterator I = Succs.begin(),
 107              E = Succs.end(); I != E; ++I) {
 108         std::cerr << "    ";
 109         (*I)->dump(G, false);
 110       }
 111     }
 112     if (ChainSuccs.size() != 0) {
 113       std::cerr << "  Chained succs:\n";
 114       for (std::set<SUnit*>::const_iterator I = ChainSuccs.begin(),
 115              E = ChainSuccs.end(); I != E; ++I) {
 116         std::cerr << "    ";
 117         (*I)->dump(G, false);
 118       }
 119     }
 120   }
 121 }
 122
 123 namespace {
 124 /// Sorting functions for the Available queue.
 125 struct ls_rr_sort : public std::binary_function<SUnit*, SUnit*, bool> {
 126   bool operator()(const SUnit* left, const SUnit* right) const {
 127     int LBonus = (int)left ->isDefNUseOperand;
 128     int RBonus = (int)right->isDefNUseOperand;
 129
 130     // Special tie breaker: if two nodes share a operand, the one that
 131     // use it as a def&use operand is preferred.
 132     if (left->isTwoAddress && !right->isTwoAddress) {
 133       SDNode *DUNode = left->Node->getOperand(0).Val;
 134       if (DUNode->isOperand(right->Node))
 135         LBonus++;
 136     }
 137     if (!left->isTwoAddress && right->isTwoAddress) {
 138       SDNode *DUNode = right->Node->getOperand(0).Val;
 139       if (DUNode->isOperand(left->Node))
 140         RBonus++;
 141     }
 142
 143     // Priority1 is just the number of live range genned.
 144     int LPriority1 = left ->NumPredsLeft - LBonus;
 145     int RPriority1 = right->NumPredsLeft - RBonus;
 146     int LPriority2 = left ->SethiUllman + LBonus;
 147     int RPriority2 = right->SethiUllman + RBonus;
 148
 149     if (LPriority1 > RPriority1)
 150       return true;
 151     else if (LPriority1 == RPriority1)
 152       if (LPriority2 < RPriority2)
 153         return true;
 154       else if (LPriority2 == RPriority2)
 155         if (left->CycleBound > right->CycleBound)
 156           return true;
 157
 158     return false;
 159   }
 160 };
 161 }  // end anonymous namespace
 162
 163
 164 namespace {
 165 /// ScheduleDAGList - List scheduler.
 166 class ScheduleDAGList : public ScheduleDAG {
 167 private:
 168   // SDNode to SUnit mapping (many to one).
 169   std::map<SDNode*, SUnit*> SUnitMap;
 170   // The schedule.  Null SUnit*'s represent noop instructions.
 171   std::vector<SUnit*> Sequence;
 172   // Current scheduling cycle.
 173   unsigned CurrCycle;
 174
 175   // The scheduling units.
 176   std::vector<SUnit> SUnits;
 177
 178   /// isBottomUp - This is true if the scheduling problem is bottom-up, false if
 179   /// it is top-down.
 180   bool isBottomUp;
 181
 182   /// HazardRec - The hazard recognizer to use.
 183   HazardRecognizer *HazardRec;
 184
 185   typedef std::priority_queue<SUnit*, std::vector<SUnit*>, ls_rr_sort>
 186     AvailableQueueTy;
 187
 188 public:
 189   ScheduleDAGList(SelectionDAG &dag, MachineBasicBlock *bb,
 190                   const TargetMachine &tm, bool isbottomup,
 191                   HazardRecognizer *HR)
 192     : ScheduleDAG(listSchedulingBURR, dag, bb, tm),
 193       CurrCycle(0), isBottomUp(isbottomup), HazardRec(HR) {
 194     }
 195
 196   ~ScheduleDAGList() {
 197     delete HazardRec;
 198   }
 199
 200   void Schedule();
 201
 202   void dump() const;
 203
 204 private:
 205   SUnit *NewSUnit(SDNode *N);
 206   void ReleasePred(AvailableQueueTy &Avail,SUnit *PredSU, bool isChain = false);
 207   void ReleaseSucc(AvailableQueueTy &Avail,SUnit *SuccSU, bool isChain = false);
 208   void ScheduleNodeBottomUp(AvailableQueueTy &Avail, SUnit *SU);
 209   void ScheduleNodeTopDown(AvailableQueueTy &Avail, SUnit *SU);
 210   int  CalcNodePriority(SUnit *SU);
 211   void CalculatePriorities();
 212   void ListScheduleTopDown();
 213   void ListScheduleBottomUp();
 214   void BuildSchedUnits();
 215   void EmitSchedule();
 216 };
 217 }  // end anonymous namespace
 218
 219 HazardRecognizer::~HazardRecognizer() {}
 220
 221
 222 /// NewSUnit - Creates a new SUnit and return a ptr to it.
 223 SUnit *ScheduleDAGList::NewSUnit(SDNode *N) {
 224   SUnits.push_back(N);
 225   return &SUnits.back();
 226 }
 227
 228 /// ReleasePred - Decrement the NumSuccsLeft count of a predecessor. Add it to
 229 /// the Available queue is the count reaches zero. Also update its cycle bound.
 230 void ScheduleDAGList::ReleasePred(AvailableQueueTy &Available,
 231                                   SUnit *PredSU, bool isChain) {
 232   // FIXME: the distance between two nodes is not always == the predecessor's
 233   // latency. For example, the reader can very well read the register written
 234   // by the predecessor later than the issue cycle. It also depends on the
 235   // interrupt model (drain vs. freeze).
 236   PredSU->CycleBound = std::max(PredSU->CycleBound,CurrCycle + PredSU->Latency);
 237
 238   if (!isChain)
 239     PredSU->NumSuccsLeft--;
 240   else
 241     PredSU->NumChainSuccsLeft--;
 242
 243 #ifndef NDEBUG
 244   if (PredSU->NumSuccsLeft < 0 || PredSU->NumChainSuccsLeft < 0) {
 245     std::cerr << "*** List scheduling failed! ***\n";
 246     PredSU->dump(&DAG);
 247     std::cerr << " has been released too many times!\n";
 248     assert(0);
 249   }
 250 #endif
 251
 252   if ((PredSU->NumSuccsLeft + PredSU->NumChainSuccsLeft) == 0) {
 253     // EntryToken has to go last!  Special case it here.
 254     if (PredSU->Node->getOpcode() != ISD::EntryToken)
 255       Available.push(PredSU);
 256   }
 257 }
 258
 259 /// ReleaseSucc - Decrement the NumPredsLeft count of a successor. Add it to
 260 /// the Available queue is the count reaches zero. Also update its cycle bound.
 261 void ScheduleDAGList::ReleaseSucc(AvailableQueueTy &Available,
 262                                   SUnit *SuccSU, bool isChain) {
 263   // FIXME: the distance between two nodes is not always == the predecessor's
 264   // latency. For example, the reader can very well read the register written
 265   // by the predecessor later than the issue cycle. It also depends on the
 266   // interrupt model (drain vs. freeze).
 267   SuccSU->CycleBound = std::max(SuccSU->CycleBound,CurrCycle + SuccSU->Latency);
 268
 269   if (!isChain)
 270     SuccSU->NumPredsLeft--;
 271   else
 272     SuccSU->NumChainPredsLeft--;
 273
 274 #ifndef NDEBUG
 275   if (SuccSU->NumPredsLeft < 0 || SuccSU->NumChainPredsLeft < 0) {
 276     std::cerr << "*** List scheduling failed! ***\n";
 277     SuccSU->dump(&DAG);
 278     std::cerr << " has been released too many times!\n";
 279     abort();
 280   }
 281 #endif
 282
 283   if ((SuccSU->NumPredsLeft + SuccSU->NumChainPredsLeft) == 0)
 284     Available.push(SuccSU);
 285 }
 286
 287 /// ScheduleNodeBottomUp - Add the node to the schedule. Decrement the pending
 288 /// count of its predecessors. If a predecessor pending count is zero, add it to
 289 /// the Available queue.
 290 void ScheduleDAGList::ScheduleNodeBottomUp(AvailableQueueTy &Available,
 291                                            SUnit *SU) {
 292   DEBUG(std::cerr << "*** Scheduling: ");
 293   DEBUG(SU->dump(&DAG, false));
 294
 295   Sequence.push_back(SU);
 296
 297   // Bottom up: release predecessors
 298   for (std::set<SUnit*>::iterator I1 = SU->Preds.begin(),
 299          E1 = SU->Preds.end(); I1 != E1; ++I1) {
 300     ReleasePred(Available, *I1);
 301     SU->NumPredsLeft--;
 302   }
 303   for (std::set<SUnit*>::iterator I2 = SU->ChainPreds.begin(),
 304          E2 = SU->ChainPreds.end(); I2 != E2; ++I2)
 305     ReleasePred(Available, *I2, true);
 306
 307   CurrCycle++;
 308 }
 309
 310 /// ScheduleNodeTopDown - Add the node to the schedule. Decrement the pending
 311 /// count of its successors. If a successor pending count is zero, add it to
 312 /// the Available queue.
 313 void ScheduleDAGList::ScheduleNodeTopDown(AvailableQueueTy &Available,
 314                                           SUnit *SU) {
 315   DEBUG(std::cerr << "*** Scheduling: ");
 316   DEBUG(SU->dump(&DAG, false));
 317
 318   Sequence.push_back(SU);
 319
 320   // Bottom up: release successors.
 321   for (std::set<SUnit*>::iterator I1 = SU->Succs.begin(),
 322        E1 = SU->Succs.end(); I1 != E1; ++I1) {
 323     ReleaseSucc(Available, *I1);
 324     SU->NumSuccsLeft--;
 325   }
 326   for (std::set<SUnit*>::iterator I2 = SU->ChainSuccs.begin(),
 327        E2 = SU->ChainSuccs.end(); I2 != E2; ++I2)
 328     ReleaseSucc(Available, *I2, true);
 329
 330   CurrCycle++;
 331 }
 332
 333 /// isReady - True if node's lower cycle bound is less or equal to the current
 334 /// scheduling cycle. Always true if all nodes have uniform latency 1.
 335 static inline bool isReady(SUnit *SU, unsigned CurrCycle) {
 336   return SU->CycleBound <= CurrCycle;
 337 }
 338
 339 /// ListScheduleBottomUp - The main loop of list scheduling for bottom-up
 340 /// schedulers.
 341 void ScheduleDAGList::ListScheduleBottomUp() {
 342   // Available queue.
 343   AvailableQueueTy Available;
 344
 345   // Add root to Available queue.
 346   Available.push(SUnitMap[DAG.getRoot().Val]);
 347
 348   // While Available queue is not empty, grab the node with the highest
 349   // priority. If it is not ready put it back. Schedule the node.
 350   std::vector<SUnit*> NotReady;
 351   while (!Available.empty()) {
 352     SUnit *CurrNode = Available.top();
 353     Available.pop();
 354
 355     while (!isReady(CurrNode, CurrCycle)) {
 356       NotReady.push_back(CurrNode);
 357       CurrNode = Available.top();
 358       Available.pop();
 359     }
 360
 361     // Add the nodes that aren't ready back onto the available list.
 362     while (!NotReady.empty()) {
 363       Available.push(NotReady.back());
 364       NotReady.pop_back();
 365     }
 366
 367     ScheduleNodeBottomUp(Available, CurrNode);
 368   }
 369
 370   // Add entry node last
 371   if (DAG.getEntryNode().Val != DAG.getRoot().Val) {
 372     SUnit *Entry = SUnitMap[DAG.getEntryNode().Val];
 373     Sequence.push_back(Entry);
 374   }
 375
 376   // Reverse the order if it is bottom up.
 377   std::reverse(Sequence.begin(), Sequence.end());
 378
 379
 380 #ifndef NDEBUG
 381   // Verify that all SUnits were scheduled.
 382   bool AnyNotSched = false;
 383   for (unsigned i = 0, e = SUnits.size(); i != e; ++i) {
 384     if (SUnits[i].NumSuccsLeft != 0 || SUnits[i].NumChainSuccsLeft != 0) {
 385       if (!AnyNotSched)
 386         std::cerr << "*** List scheduling failed! ***\n";
 387       SUnits[i].dump(&DAG);
 388       std::cerr << "has not been scheduled!\n";
 389       AnyNotSched = true;
 390     }
 391   }
 392   assert(!AnyNotSched);
 393 #endif
 394 }
 395
 396 /// ListScheduleTopDown - The main loop of list scheduling for top-down
 397 /// schedulers.
 398 void ScheduleDAGList::ListScheduleTopDown() {
 399   // Available queue.
 400   AvailableQueueTy Available;
 401
 402   // Emit the entry node first.
 403   SUnit *Entry = SUnitMap[DAG.getEntryNode().Val];
 404   ScheduleNodeTopDown(Available, Entry);
 405   HazardRec->EmitInstruction(Entry->Node);
 406
 407   // All leaves to Available queue.
 408   for (unsigned i = 0, e = SUnits.size(); i != e; ++i) {
 409     // It is available if it has no predecessors.
 410     if ((SUnits[i].Preds.size() + SUnits[i].ChainPreds.size()) == 0 &&
 411         &SUnits[i] != Entry)
 412       Available.push(&SUnits[i]);
 413   }
 414
 415   // While Available queue is not empty, grab the node with the highest
 416   // priority. If it is not ready put it back.  Schedule the node.
 417   std::vector<SUnit*> NotReady;
 418   while (!Available.empty()) {
 419     SUnit *FoundNode = 0;
 420
 421     bool HasNoopHazards = false;
 422     do {
 423       SUnit *CurNode = Available.top();
 424       Available.pop();
 425
 426       // Get the node represented by this SUnit.
 427       SDNode *N = CurNode->Node;
 428       // If this is a pseudo op, like copyfromreg, look to see if there is a
 429       // real target node flagged to it.  If so, use the target node.
 430       for (unsigned i = 0, e = CurNode->FlaggedNodes.size();
 431            N->getOpcode() < ISD::BUILTIN_OP_END && i != e; ++i)
 432         N = CurNode->FlaggedNodes[i];
 433
 434       HazardRecognizer::HazardType HT = HazardRec->getHazardType(N);
 435       if (HT == HazardRecognizer::NoHazard) {
 436         FoundNode = CurNode;
 437         break;
 438       }
 439
 440       // Remember if this is a noop hazard.
 441       HasNoopHazards |= HT == HazardRecognizer::NoopHazard;
 442
 443       NotReady.push_back(CurNode);
 444     } while (!Available.empty());
 445
 446     // Add the nodes that aren't ready back onto the available list.
 447     while (!NotReady.empty()) {
 448       Available.push(NotReady.back());
 449       NotReady.pop_back();
 450     }
 451
 452     // If we found a node to schedule, do it now.
 453     if (FoundNode) {
 454       ScheduleNodeTopDown(Available, FoundNode);
 455       HazardRec->EmitInstruction(FoundNode->Node);
 456     } else if (!HasNoopHazards) {
 457       // Otherwise, we have a pipeline stall, but no other problem, just advance
 458       // the current cycle and try again.
 459       DEBUG(std::cerr << "*** Advancing cycle, no work to do\n");
 460       HazardRec->AdvanceCycle();
 461       ++NumStalls;
 462     } else {
 463       // Otherwise, we have no instructions to issue and we have instructions
 464       // that will fault if we don't do this right.  This is the case for
 465       // processors without pipeline interlocks and other cases.
 466       DEBUG(std::cerr << "*** Emitting noop\n");
 467       HazardRec->EmitNoop();
 468       Sequence.push_back(0);   // NULL SUnit* -> noop
 469       ++NumNoops;
 470     }
 471   }
 472
 473 #ifndef NDEBUG
 474   // Verify that all SUnits were scheduled.
 475   bool AnyNotSched = false;
 476   for (unsigned i = 0, e = SUnits.size(); i != e; ++i) {
 477     if (SUnits[i].NumPredsLeft != 0 || SUnits[i].NumChainPredsLeft != 0) {
 478       if (!AnyNotSched)
 479         std::cerr << "*** List scheduling failed! ***\n";
 480       SUnits[i].dump(&DAG);
 481       std::cerr << "has not been scheduled!\n";
 482       AnyNotSched = true;
 483     }
 484   }
 485   assert(!AnyNotSched);
 486 #endif
 487 }
 488
 489
 490 /// CalcNodePriority - Priority is the Sethi Ullman number.
 491 /// Smaller number is the higher priority.
 492 int ScheduleDAGList::CalcNodePriority(SUnit *SU) {
 493   if (SU->SethiUllman != INT_MIN)
 494     return SU->SethiUllman;
 495
 496   if (SU->Preds.size() == 0) {
 497     SU->SethiUllman = 1;
 498   } else {
 499     int Extra = 0;
 500     for (std::set<SUnit*>::iterator I = SU->Preds.begin(),
 501            E = SU->Preds.end(); I != E; ++I) {
 502       SUnit *PredSU = *I;
 503       int PredSethiUllman = CalcNodePriority(PredSU);
 504       if (PredSethiUllman > SU->SethiUllman) {
 505         SU->SethiUllman = PredSethiUllman;
 506         Extra = 0;
 507       } else if (PredSethiUllman == SU->SethiUllman)
 508         Extra++;
 509     }
 510
 511     if (SU->Node->getOpcode() != ISD::TokenFactor)
 512       SU->SethiUllman += Extra;
 513     else
 514       SU->SethiUllman = (Extra == 1) ? 0 : Extra-1;
 515   }
 516
 517   return SU->SethiUllman;
 518 }
 519
 520 /// CalculatePriorities - Calculate priorities of all scheduling units.
 521 void ScheduleDAGList::CalculatePriorities() {
 522   for (unsigned i = 0, e = SUnits.size(); i != e; ++i) {
 523     // FIXME: assumes uniform latency for now.
 524     SUnits[i].Latency = 1;
 525     (void)CalcNodePriority(&SUnits[i]);
 526     DEBUG(SUnits[i].dump(&DAG));
 527     DEBUG(std::cerr << "\n");
 528   }
 529 }
 530
 531 void ScheduleDAGList::BuildSchedUnits() {
 532   // Reserve entries in the vector for each of the SUnits we are creating.  This
 533   // ensure that reallocation of the vector won't happen, so SUnit*'s won't get
 534   // invalidated.
 535   SUnits.reserve(NodeCount);
 536
 537   // Pass 1: create the SUnit's.
 538   for (unsigned i = 0, NC = NodeCount; i < NC; i++) {
 539     NodeInfo *NI = &Info[i];
 540     SDNode *N = NI->Node;
 541     if (isPassiveNode(N))
 542       continue;
 543
 544     SUnit *SU;
 545     if (NI->isInGroup()) {
 546       if (NI != NI->Group->getBottom())  // Bottom up, so only look at bottom
 547         continue;                        // node of the NodeGroup
 548
 549       SU = NewSUnit(N);
 550       // Find the flagged nodes.
 551       SDOperand  FlagOp = N->getOperand(N->getNumOperands() - 1);
 552       SDNode    *Flag   = FlagOp.Val;
 553       unsigned   ResNo  = FlagOp.ResNo;
 554       while (Flag->getValueType(ResNo) == MVT::Flag) {
 555         NodeInfo *FNI = getNI(Flag);
 556         assert(FNI->Group == NI->Group);
 557         SU->FlaggedNodes.insert(SU->FlaggedNodes.begin(), Flag);
 558         SUnitMap[Flag] = SU;
 559
 560         FlagOp = Flag->getOperand(Flag->getNumOperands() - 1);
 561         Flag   = FlagOp.Val;
 562         ResNo  = FlagOp.ResNo;
 563       }
 564     } else {
 565       SU = NewSUnit(N);
 566     }
 567     SUnitMap[N] = SU;
 568   }
 569
 570   // Pass 2: add the preds, succs, etc.
 571   for (unsigned i = 0, e = SUnits.size(); i != e; ++i) {
 572     SUnit *SU = &SUnits[i];
 573     SDNode   *N  = SU->Node;
 574     NodeInfo *NI = getNI(N);
 575
 576     if (N->isTargetOpcode() && TII->isTwoAddrInstr(N->getTargetOpcode()))
 577       SU->isTwoAddress = true;
 578
 579     if (NI->isInGroup()) {
 580       // Find all predecessors (of the group).
 581       NodeGroupOpIterator NGOI(NI);
 582       while (!NGOI.isEnd()) {
 583         SDOperand Op  = NGOI.next();
 584         SDNode   *OpN = Op.Val;
 585         MVT::ValueType VT = OpN->getValueType(Op.ResNo);
 586         NodeInfo *OpNI = getNI(OpN);
 587         if (OpNI->Group != NI->Group && !isPassiveNode(OpN)) {
 588           assert(VT != MVT::Flag);
 589           SUnit *OpSU = SUnitMap[OpN];
 590           if (VT == MVT::Other) {
 591             if (SU->ChainPreds.insert(OpSU).second)
 592               SU->NumChainPredsLeft++;
 593             if (OpSU->ChainSuccs.insert(SU).second)
 594               OpSU->NumChainSuccsLeft++;
 595           } else {
 596             if (SU->Preds.insert(OpSU).second)
 597               SU->NumPredsLeft++;
 598             if (OpSU->Succs.insert(SU).second)
 599               OpSU->NumSuccsLeft++;
 600           }
 601         }
 602       }
 603     } else {
 604       // Find node predecessors.
 605       for (unsigned j = 0, e = N->getNumOperands(); j != e; j++) {
 606         SDOperand Op  = N->getOperand(j);
 607         SDNode   *OpN = Op.Val;
 608         MVT::ValueType VT = OpN->getValueType(Op.ResNo);
 609         if (!isPassiveNode(OpN)) {
 610           assert(VT != MVT::Flag);
 611           SUnit *OpSU = SUnitMap[OpN];
 612           if (VT == MVT::Other) {
 613             if (SU->ChainPreds.insert(OpSU).second)
 614               SU->NumChainPredsLeft++;
 615             if (OpSU->ChainSuccs.insert(SU).second)
 616               OpSU->NumChainSuccsLeft++;
 617           } else {
 618             if (SU->Preds.insert(OpSU).second)
 619               SU->NumPredsLeft++;
 620             if (OpSU->Succs.insert(SU).second)
 621               OpSU->NumSuccsLeft++;
 622             if (j == 0 && SU->isTwoAddress)
 623               OpSU->isDefNUseOperand = true;
 624           }
 625         }
 626       }
 627     }
 628   }
 629 }
 630
 631 /// EmitSchedule - Emit the machine code in scheduled order.
 632 void ScheduleDAGList::EmitSchedule() {
 633   for (unsigned i = 0, e = Sequence.size(); i != e; i++) {
 634     if (SUnit *SU = Sequence[i]) {
 635       for (unsigned j = 0, ee = SU->FlaggedNodes.size(); j != ee; j++) {
 636         SDNode *N = SU->FlaggedNodes[j];
 637         EmitNode(getNI(N));
 638       }
 639       EmitNode(getNI(SU->Node));
 640     } else {
 641       // Null SUnit* is a noop.
 642       EmitNoop();
 643     }
 644   }
 645 }
 646
 647 /// dump - dump the schedule.
 648 void ScheduleDAGList::dump() const {
 649   for (unsigned i = 0, e = Sequence.size(); i != e; i++) {
 650     if (SUnit *SU = Sequence[i])
 651       SU->dump(&DAG, false);
 652     else
 653       std::cerr << "**** NOOP ****\n";
 654   }
 655 }
 656
 657 /// Schedule - Schedule the DAG using list scheduling.
 658 /// FIXME: Right now it only supports the burr (bottom up register reducing)
 659 /// heuristic.
 660 void ScheduleDAGList::Schedule() {
 661   DEBUG(std::cerr << "********** List Scheduling **********\n");
 662
 663   // Build scheduling units.
 664   BuildSchedUnits();
 665
 666   // Calculate node priorities.
 667   CalculatePriorities();
 668
 669   // Execute the actual scheduling loop Top-Down or Bottom-Up as appropriate.
 670   if (isBottomUp)
 671     ListScheduleBottomUp();
 672   else
 673     ListScheduleTopDown();
 674
 675   DEBUG(std::cerr << "*** Final schedule ***\n");
 676   DEBUG(dump());
 677   DEBUG(std::cerr << "\n");
 678
 679   // Emit in scheduled order
 680   EmitSchedule();
 681 }
 682
 683 llvm::ScheduleDAG* llvm::createBURRListDAGScheduler(SelectionDAG &DAG,
 684                                                     MachineBasicBlock *BB) {
 685   return new ScheduleDAGList(DAG, BB, DAG.getTarget(), true,
 686                              new HazardRecognizer());
 687 }
 688
 689 /// createTDListDAGScheduler - This creates a top-down list scheduler with the
 690 /// specified hazard recognizer.
 691 ScheduleDAG* llvm::createTDListDAGScheduler(SelectionDAG &DAG,
 692                                             MachineBasicBlock *BB,
 693                                             HazardRecognizer *HR) {
 694   return new ScheduleDAGList(DAG, BB, DAG.getTarget(), false, HR);
 695 }