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