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 Priority1;                      // Scheduling priority 1.
  48   int Priority2;                      // Scheduling priority 2.
  49   bool isTwoAddress;                  // Is a two-address instruction.
  50   bool isDefNUseOperand;              // Is a def&use operand.
  51   unsigned Latency;                   // Node latency.
  52   unsigned CycleBound;                // Upper/lower cycle to be scheduled at.
  53   unsigned Slot;                      // Cycle node is scheduled at.
  54   SUnit *Next;
  55
  56   SUnit(SDNode *node)
  57     : Node(node), NumPredsLeft(0), NumSuccsLeft(0),
  58       NumChainPredsLeft(0), NumChainSuccsLeft(0),
  59       Priority1(INT_MIN), Priority2(INT_MIN),
  60       isTwoAddress(false), isDefNUseOperand(false),
  61       Latency(0), CycleBound(0), Slot(0), Next(NULL) {}
  62
  63   void dump(const SelectionDAG *G, bool All=true) const;
  64 };
  65
  66 void SUnit::dump(const SelectionDAG *G, bool All) const {
  67   std::cerr << "SU: ";
  68   Node->dump(G);
  69   std::cerr << "\n";
  70   if (FlaggedNodes.size() != 0) {
  71     for (unsigned i = 0, e = FlaggedNodes.size(); i != e; i++) {
  72       std::cerr << "    ";
  73       FlaggedNodes[i]->dump(G);
  74       std::cerr << "\n";
  75     }
  76   }
  77
  78   if (All) {
  79     std::cerr << "  # preds left       : " << NumPredsLeft << "\n";
  80     std::cerr << "  # succs left       : " << NumSuccsLeft << "\n";
  81     std::cerr << "  # chain preds left : " << NumChainPredsLeft << "\n";
  82     std::cerr << "  # chain succs left : " << NumChainSuccsLeft << "\n";
  83     std::cerr << "  Latency            : " << Latency << "\n";
  84     std::cerr << "  Priority           : " << Priority1 << " , "
  85               << Priority2 << "\n";
  86
  87     if (Preds.size() != 0) {
  88       std::cerr << "  Predecessors:\n";
  89       for (std::set<SUnit*>::const_iterator I = Preds.begin(),
  90              E = Preds.end(); I != E; ++I) {
  91         std::cerr << "    ";
  92         (*I)->dump(G, false);
  93       }
  94     }
  95     if (ChainPreds.size() != 0) {
  96       std::cerr << "  Chained Preds:\n";
  97       for (std::set<SUnit*>::const_iterator I = ChainPreds.begin(),
  98              E = ChainPreds.end(); I != E; ++I) {
  99         std::cerr << "    ";
 100         (*I)->dump(G, false);
 101       }
 102     }
 103     if (Succs.size() != 0) {
 104       std::cerr << "  Successors:\n";
 105       for (std::set<SUnit*>::const_iterator I = Succs.begin(),
 106              E = Succs.end(); I != E; ++I) {
 107         std::cerr << "    ";
 108         (*I)->dump(G, false);
 109       }
 110     }
 111     if (ChainSuccs.size() != 0) {
 112       std::cerr << "  Chained succs:\n";
 113       for (std::set<SUnit*>::const_iterator I = ChainSuccs.begin(),
 114              E = ChainSuccs.end(); I != E; ++I) {
 115         std::cerr << "    ";
 116         (*I)->dump(G, false);
 117       }
 118     }
 119   }
 120 }
 121
 122 /// Sorting functions for the Available queue.
 123 struct ls_rr_sort : public std::binary_function<SUnit*, SUnit*, bool> {
 124   bool operator()(const SUnit* left, const SUnit* right) const {
 125     bool LFloater = (left ->Preds.size() == 0);
 126     bool RFloater = (right->Preds.size() == 0);
 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     int LPriority1 = left ->Priority1 - LBonus;
 144     int RPriority1 = right->Priority1 - RBonus;
 145     int LPriority2 = left ->Priority2 + LBonus;
 146     int RPriority2 = right->Priority2 + RBonus;
 147
 148     // Favor floaters (i.e. node with no non-passive predecessors):
 149     // e.g. MOV32ri.
 150     if (!LFloater && RFloater)
 151       return true;
 152     else if (LFloater == RFloater)
 153       if (LPriority1 > RPriority1)
 154         return true;
 155       else if (LPriority1 == RPriority1)
 156         if (LPriority2 < RPriority2)
 157           return true;
 158         else if (LPriority1 == RPriority1)
 159           if (left->CycleBound > right->CycleBound)
 160             return true;
 161
 162     return false;
 163   }
 164 };
 165
 166
 167 /// HazardRecognizer - This determines whether or not an instruction can be
 168 /// issued this cycle, and whether or not a noop needs to be inserted to handle
 169 /// the hazard.
 170 namespace {
 171   class HazardRecognizer {
 172   public:
 173     virtual ~HazardRecognizer() {}
 174
 175     enum HazardType {
 176       NoHazard,      // This instruction can be emitted at this cycle.
 177       Hazard,        // This instruction can't be emitted at this cycle.
 178       NoopHazard,    // This instruction can't be emitted, and needs noops.
 179     };
 180
 181     /// getHazardType - Return the hazard type of emitting this node.  There are
 182     /// three possible results.  Either:
 183     ///  * NoHazard: it is legal to issue this instruction on this cycle.
 184     ///  * Hazard: issuing this instruction would stall the machine.  If some
 185     ///     other instruction is available, issue it first.
 186     ///  * NoopHazard: issuing this instruction would break the program.  If
 187     ///     some other instruction can be issued, do so, otherwise issue a noop.
 188     virtual HazardType getHazardType(SDNode *Node) {
 189       return NoHazard;
 190     }
 191
 192     /// EmitInstruction - This callback is invoked when an instruction is
 193     /// emitted, to advance the hazard state.
 194     virtual void EmitInstruction(SDNode *Node) {
 195     }
 196
 197     /// AdvanceCycle - This callback is invoked when no instructions can be
 198     /// issued on this cycle without a hazard.  This should increment the
 199     /// internal state of the hazard recognizer so that previously "Hazard"
 200     /// instructions will now not be hazards.
 201     virtual void AdvanceCycle() {
 202     }
 203
 204     /// EmitNoop - This callback is invoked when a noop was added to the
 205     /// instruction stream.
 206     virtual void EmitNoop() {
 207     }
 208   };
 209 }
 210
 211
 212 /// ScheduleDAGList - List scheduler.
 213 class ScheduleDAGList : public ScheduleDAG {
 214 private:
 215   // SDNode to SUnit mapping (many to one).
 216   std::map<SDNode*, SUnit*> SUnitMap;
 217   // The schedule.
 218   std::vector<SUnit*> Sequence;
 219   // Current scheduling cycle.
 220   unsigned CurrCycle;
 221   // First and last SUnit created.
 222   SUnit *HeadSUnit, *TailSUnit;
 223
 224   /// isBottomUp - This is true if the scheduling problem is bottom-up, false if
 225   /// it is top-down.
 226   bool isBottomUp;
 227
 228   /// HazardRec - The hazard recognizer to use.
 229   HazardRecognizer *HazardRec;
 230
 231   typedef std::priority_queue<SUnit*, std::vector<SUnit*>, ls_rr_sort>
 232     AvailableQueueTy;
 233
 234 public:
 235   ScheduleDAGList(SelectionDAG &dag, MachineBasicBlock *bb,
 236                   const TargetMachine &tm, bool isbottomup,
 237                   HazardRecognizer *HR = 0)
 238     : ScheduleDAG(listSchedulingBURR, dag, bb, tm),
 239       CurrCycle(0), HeadSUnit(NULL), TailSUnit(NULL), isBottomUp(isbottomup) {
 240       if (HR == 0) HR = new HazardRecognizer();
 241         HazardRec = HR;
 242     }
 243
 244   ~ScheduleDAGList() {
 245     SUnit *SU = HeadSUnit;
 246     while (SU) {
 247       SUnit *NextSU = SU->Next;
 248       delete SU;
 249       SU = NextSU;
 250     }
 251
 252     delete HazardRec;
 253   }
 254
 255   void Schedule();
 256
 257   void dump() const;
 258
 259 private:
 260   SUnit *NewSUnit(SDNode *N);
 261   void ReleasePred(AvailableQueueTy &Avail,SUnit *PredSU, bool isChain = false);
 262   void ReleaseSucc(AvailableQueueTy &Avail,SUnit *SuccSU, bool isChain = false);
 263   void ScheduleNodeBottomUp(AvailableQueueTy &Avail, SUnit *SU);
 264   void ScheduleNodeTopDown(AvailableQueueTy &Avail, SUnit *SU);
 265   int  CalcNodePriority(SUnit *SU);
 266   void CalculatePriorities();
 267   void ListScheduleTopDown();
 268   void ListScheduleBottomUp();
 269   void BuildSchedUnits();
 270   void EmitSchedule();
 271 };
 272 }  // end namespace
 273
 274
 275 /// NewSUnit - Creates a new SUnit and return a ptr to it.
 276 SUnit *ScheduleDAGList::NewSUnit(SDNode *N) {
 277   SUnit *CurrSUnit = new SUnit(N);
 278
 279   if (HeadSUnit == NULL)
 280     HeadSUnit = CurrSUnit;
 281   if (TailSUnit != NULL)
 282     TailSUnit->Next = CurrSUnit;
 283   TailSUnit = CurrSUnit;
 284
 285   return CurrSUnit;
 286 }
 287
 288 /// ReleasePred - Decrement the NumSuccsLeft count of a predecessor. Add it to
 289 /// the Available queue is the count reaches zero. Also update its cycle bound.
 290 void ScheduleDAGList::ReleasePred(AvailableQueueTy &Available,
 291                                   SUnit *PredSU, bool isChain) {
 292   // FIXME: the distance between two nodes is not always == the predecessor's
 293   // latency. For example, the reader can very well read the register written
 294   // by the predecessor later than the issue cycle. It also depends on the
 295   // interrupt model (drain vs. freeze).
 296   PredSU->CycleBound = std::max(PredSU->CycleBound, CurrCycle + PredSU->Latency);
 297
 298   if (!isChain) {
 299     PredSU->NumSuccsLeft--;
 300     PredSU->Priority1++;
 301   } else
 302     PredSU->NumChainSuccsLeft--;
 303
 304 #ifndef NDEBUG
 305   if (PredSU->NumSuccsLeft < 0 || PredSU->NumChainSuccsLeft < 0) {
 306     std::cerr << "*** List scheduling failed! ***\n";
 307     PredSU->dump(&DAG);
 308     std::cerr << " has been released too many times!\n";
 309     assert(0);
 310   }
 311 #endif
 312
 313   if ((PredSU->NumSuccsLeft + PredSU->NumChainSuccsLeft) == 0) {
 314     // EntryToken has to go last!  Special case it here.
 315     if (PredSU->Node->getOpcode() != ISD::EntryToken)
 316       Available.push(PredSU);
 317   }
 318 }
 319
 320 /// ReleaseSucc - Decrement the NumPredsLeft count of a successor. Add it to
 321 /// the Available queue is the count reaches zero. Also update its cycle bound.
 322 void ScheduleDAGList::ReleaseSucc(AvailableQueueTy &Available,
 323                                   SUnit *SuccSU, bool isChain) {
 324   // FIXME: the distance between two nodes is not always == the predecessor's
 325   // latency. For example, the reader can very well read the register written
 326   // by the predecessor later than the issue cycle. It also depends on the
 327   // interrupt model (drain vs. freeze).
 328   SuccSU->CycleBound = std::max(SuccSU->CycleBound, CurrCycle + SuccSU->Latency);
 329
 330   if (!isChain) {
 331     SuccSU->NumPredsLeft--;
 332     SuccSU->Priority1++;          // FIXME: ??
 333   } else
 334     SuccSU->NumChainPredsLeft--;
 335
 336 #ifndef NDEBUG
 337   if (SuccSU->NumPredsLeft < 0 || SuccSU->NumChainPredsLeft < 0) {
 338     std::cerr << "*** List scheduling failed! ***\n";
 339     SuccSU->dump(&DAG);
 340     std::cerr << " has been released too many times!\n";
 341     abort();
 342   }
 343 #endif
 344
 345   if ((SuccSU->NumPredsLeft + SuccSU->NumChainPredsLeft) == 0)
 346     Available.push(SuccSU);
 347 }
 348
 349 /// ScheduleNodeBottomUp - Add the node to the schedule. Decrement the pending
 350 /// count of its predecessors. If a predecessor pending count is zero, add it to
 351 /// the Available queue.
 352 void ScheduleDAGList::ScheduleNodeBottomUp(AvailableQueueTy &Available,
 353                                            SUnit *SU) {
 354   DEBUG(std::cerr << "*** Scheduling: ");
 355   DEBUG(SU->dump(&DAG, false));
 356
 357   Sequence.push_back(SU);
 358   SU->Slot = CurrCycle;
 359
 360   // Bottom up: release predecessors
 361   for (std::set<SUnit*>::iterator I1 = SU->Preds.begin(),
 362          E1 = SU->Preds.end(); I1 != E1; ++I1) {
 363     ReleasePred(Available, *I1);
 364     SU->NumPredsLeft--;
 365     SU->Priority1--;
 366   }
 367   for (std::set<SUnit*>::iterator I2 = SU->ChainPreds.begin(),
 368          E2 = SU->ChainPreds.end(); I2 != E2; ++I2)
 369     ReleasePred(Available, *I2, true);
 370
 371   CurrCycle++;
 372 }
 373
 374 /// ScheduleNodeTopDown - Add the node to the schedule. Decrement the pending
 375 /// count of its successors. If a successor pending count is zero, add it to
 376 /// the Available queue.
 377 void ScheduleDAGList::ScheduleNodeTopDown(AvailableQueueTy &Available,
 378                                           SUnit *SU) {
 379   DEBUG(std::cerr << "*** Scheduling: ");
 380   DEBUG(SU->dump(&DAG, false));
 381
 382   Sequence.push_back(SU);
 383   SU->Slot = CurrCycle;
 384
 385   // Bottom up: release successors.
 386   for (std::set<SUnit*>::iterator I1 = SU->Succs.begin(),
 387        E1 = SU->Succs.end(); I1 != E1; ++I1) {
 388     ReleaseSucc(Available, *I1);
 389     SU->NumSuccsLeft--;
 390     SU->Priority1--;           // FIXME: what is this??
 391   }
 392   for (std::set<SUnit*>::iterator I2 = SU->ChainSuccs.begin(),
 393        E2 = SU->ChainSuccs.end(); I2 != E2; ++I2)
 394     ReleaseSucc(Available, *I2, true);
 395
 396   CurrCycle++;
 397 }
 398
 399 /// isReady - True if node's lower cycle bound is less or equal to the current
 400 /// scheduling cycle. Always true if all nodes have uniform latency 1.
 401 static inline bool isReady(SUnit *SU, unsigned CurrCycle) {
 402   return SU->CycleBound <= CurrCycle;
 403 }
 404
 405 /// ListScheduleBottomUp - The main loop of list scheduling for bottom-up
 406 /// schedulers.
 407 void ScheduleDAGList::ListScheduleBottomUp() {
 408   // Available queue.
 409   AvailableQueueTy Available;
 410
 411   // Add root to Available queue.
 412   Available.push(SUnitMap[DAG.getRoot().Val]);
 413
 414   // While Available queue is not empty, grab the node with the highest
 415   // priority. If it is not ready put it back. Schedule the node.
 416   std::vector<SUnit*> NotReady;
 417   while (!Available.empty()) {
 418     SUnit *CurrNode = Available.top();
 419     Available.pop();
 420
 421     while (!isReady(CurrNode, CurrCycle)) {
 422       NotReady.push_back(CurrNode);
 423       CurrNode = Available.top();
 424       Available.pop();
 425     }
 426
 427     // Add the nodes that aren't ready back onto the available list.
 428     while (!NotReady.empty()) {
 429       Available.push(NotReady.back());
 430       NotReady.pop_back();
 431     }
 432
 433     ScheduleNodeBottomUp(Available, CurrNode);
 434   }
 435
 436   // Add entry node last
 437   if (DAG.getEntryNode().Val != DAG.getRoot().Val) {
 438     SUnit *Entry = SUnitMap[DAG.getEntryNode().Val];
 439     Entry->Slot = CurrCycle;
 440     Sequence.push_back(Entry);
 441   }
 442
 443   // Reverse the order if it is bottom up.
 444   std::reverse(Sequence.begin(), Sequence.end());
 445
 446
 447 #ifndef NDEBUG
 448   // Verify that all SUnits were scheduled.
 449   bool AnyNotSched = false;
 450   for (SUnit *SU = HeadSUnit; SU != NULL; SU = SU->Next) {
 451     if (SU->NumSuccsLeft != 0 || SU->NumChainSuccsLeft != 0) {
 452       if (!AnyNotSched)
 453         std::cerr << "*** List scheduling failed! ***\n";
 454       SU->dump(&DAG);
 455       std::cerr << "has not been scheduled!\n";
 456       AnyNotSched = true;
 457     }
 458   }
 459   assert(!AnyNotSched);
 460 #endif
 461 }
 462
 463 /// ListScheduleTopDown - The main loop of list scheduling for top-down
 464 /// schedulers.
 465 void ScheduleDAGList::ListScheduleTopDown() {
 466   // Available queue.
 467   AvailableQueueTy Available;
 468
 469   // Emit the entry node first.
 470   SUnit *Entry = SUnitMap[DAG.getEntryNode().Val];
 471   ScheduleNodeTopDown(Available, Entry);
 472   HazardRec->EmitInstruction(Entry->Node);
 473
 474   // All leaves to Available queue.
 475   for (SUnit *SU = HeadSUnit; SU != NULL; SU = SU->Next) {
 476     // It is available if it has no predecessors.
 477     if ((SU->Preds.size() + SU->ChainPreds.size()) == 0 && SU != Entry)
 478       Available.push(SU);
 479   }
 480
 481   // While Available queue is not empty, grab the node with the highest
 482   // priority. If it is not ready put it back.  Schedule the node.
 483   std::vector<SUnit*> NotReady;
 484   while (!Available.empty()) {
 485     SUnit *FoundNode = 0;
 486
 487     bool HasNoopHazards = false;
 488     do {
 489       SUnit *CurrNode = Available.top();
 490       Available.pop();
 491       HazardRecognizer::HazardType HT =
 492         HazardRec->getHazardType(CurrNode->Node);
 493       if (HT == HazardRecognizer::NoHazard) {
 494         FoundNode = CurrNode;
 495         break;
 496       }
 497
 498       // Remember if this is a noop hazard.
 499       HasNoopHazards |= HT == HazardRecognizer::NoopHazard;
 500
 501       NotReady.push_back(CurrNode);
 502     } while (!Available.empty());
 503
 504     // Add the nodes that aren't ready back onto the available list.
 505     while (!NotReady.empty()) {
 506       Available.push(NotReady.back());
 507       NotReady.pop_back();
 508     }
 509
 510     // If we found a node to schedule, do it now.
 511     if (FoundNode) {
 512       ScheduleNodeTopDown(Available, FoundNode);
 513       HazardRec->EmitInstruction(FoundNode->Node);
 514     } else if (!HasNoopHazards) {
 515       // Otherwise, we have a pipeline stall, but no other problem, just advance
 516       // the current cycle and try again.
 517       DEBUG(std::cerr << "*** Advancing cycle, no work to do");
 518       HazardRec->AdvanceCycle();
 519       ++NumStalls;
 520     } else {
 521       // Otherwise, we have no instructions to issue and we have instructions
 522       // that will fault if we don't do this right.  This is the case for
 523       // processors without pipeline interlocks and other cases.
 524       DEBUG(std::cerr << "*** Emitting noop");
 525       HazardRec->EmitNoop();
 526       // FIXME: Add a noop to the schedule!!
 527       ++NumNoops;
 528     }
 529   }
 530
 531 #ifndef NDEBUG
 532   // Verify that all SUnits were scheduled.
 533   bool AnyNotSched = false;
 534   for (SUnit *SU = HeadSUnit; SU != NULL; SU = SU->Next) {
 535     if (SU->NumPredsLeft != 0 || SU->NumChainPredsLeft != 0) {
 536       if (!AnyNotSched)
 537         std::cerr << "*** List scheduling failed! ***\n";
 538       SU->dump(&DAG);
 539       std::cerr << "has not been scheduled!\n";
 540       AnyNotSched = true;
 541     }
 542   }
 543   assert(!AnyNotSched);
 544 #endif
 545 }
 546
 547
 548 /// CalcNodePriority - Priority1 is just the number of live range genned -
 549 /// number of live range killed. Priority2 is the Sethi Ullman number. It
 550 /// returns Priority2 since it is calculated recursively.
 551 /// Smaller number is the higher priority for Priority2. Reverse is true for
 552 /// Priority1.
 553 int ScheduleDAGList::CalcNodePriority(SUnit *SU) {
 554   if (SU->Priority2 != INT_MIN)
 555     return SU->Priority2;
 556
 557   SU->Priority1 = SU->NumPredsLeft - SU->NumSuccsLeft;
 558
 559   if (SU->Preds.size() == 0) {
 560     SU->Priority2 = 1;
 561   } else {
 562     int Extra = 0;
 563     for (std::set<SUnit*>::iterator I = SU->Preds.begin(),
 564            E = SU->Preds.end(); I != E; ++I) {
 565       SUnit *PredSU = *I;
 566       int PredPriority = CalcNodePriority(PredSU);
 567       if (PredPriority > SU->Priority2) {
 568         SU->Priority2 = PredPriority;
 569         Extra = 0;
 570       } else if (PredPriority == SU->Priority2)
 571         Extra++;
 572     }
 573
 574     if (SU->Node->getOpcode() != ISD::TokenFactor)
 575       SU->Priority2 += Extra;
 576     else
 577       SU->Priority2 = (Extra == 1) ? 0 : Extra-1;
 578   }
 579
 580   return SU->Priority2;
 581 }
 582
 583 /// CalculatePriorities - Calculate priorities of all scheduling units.
 584 void ScheduleDAGList::CalculatePriorities() {
 585   for (SUnit *SU = HeadSUnit; SU != NULL; SU = SU->Next) {
 586     // FIXME: assumes uniform latency for now.
 587     SU->Latency = 1;
 588     (void)CalcNodePriority(SU);
 589     DEBUG(SU->dump(&DAG));
 590     DEBUG(std::cerr << "\n");
 591   }
 592 }
 593
 594 void ScheduleDAGList::BuildSchedUnits() {
 595   // Pass 1: create the SUnit's.
 596   for (unsigned i = 0, NC = NodeCount; i < NC; i++) {
 597     NodeInfo *NI = &Info[i];
 598     SDNode *N = NI->Node;
 599     if (isPassiveNode(N))
 600       continue;
 601
 602     SUnit *SU;
 603     if (NI->isInGroup()) {
 604       if (NI != NI->Group->getBottom())  // Bottom up, so only look at bottom
 605         continue;                        // node of the NodeGroup
 606
 607       SU = NewSUnit(N);
 608       // Find the flagged nodes.
 609       SDOperand  FlagOp = N->getOperand(N->getNumOperands() - 1);
 610       SDNode    *Flag   = FlagOp.Val;
 611       unsigned   ResNo  = FlagOp.ResNo;
 612       while (Flag->getValueType(ResNo) == MVT::Flag) {
 613         NodeInfo *FNI = getNI(Flag);
 614         assert(FNI->Group == NI->Group);
 615         SU->FlaggedNodes.insert(SU->FlaggedNodes.begin(), Flag);
 616         SUnitMap[Flag] = SU;
 617
 618         FlagOp = Flag->getOperand(Flag->getNumOperands() - 1);
 619         Flag   = FlagOp.Val;
 620         ResNo  = FlagOp.ResNo;
 621       }
 622     } else {
 623       SU = NewSUnit(N);
 624     }
 625     SUnitMap[N] = SU;
 626   }
 627
 628   // Pass 2: add the preds, succs, etc.
 629   for (SUnit *SU = HeadSUnit; SU != NULL; SU = SU->Next) {
 630     SDNode   *N  = SU->Node;
 631     NodeInfo *NI = getNI(N);
 632
 633     if (N->isTargetOpcode() && TII->isTwoAddrInstr(N->getTargetOpcode()))
 634       SU->isTwoAddress = true;
 635
 636     if (NI->isInGroup()) {
 637       // Find all predecessors (of the group).
 638       NodeGroupOpIterator NGOI(NI);
 639       while (!NGOI.isEnd()) {
 640         SDOperand Op  = NGOI.next();
 641         SDNode   *OpN = Op.Val;
 642         MVT::ValueType VT = OpN->getValueType(Op.ResNo);
 643         NodeInfo *OpNI = getNI(OpN);
 644         if (OpNI->Group != NI->Group && !isPassiveNode(OpN)) {
 645           assert(VT != MVT::Flag);
 646           SUnit *OpSU = SUnitMap[OpN];
 647           if (VT == MVT::Other) {
 648             if (SU->ChainPreds.insert(OpSU).second)
 649               SU->NumChainPredsLeft++;
 650             if (OpSU->ChainSuccs.insert(SU).second)
 651               OpSU->NumChainSuccsLeft++;
 652           } else {
 653             if (SU->Preds.insert(OpSU).second)
 654               SU->NumPredsLeft++;
 655             if (OpSU->Succs.insert(SU).second)
 656               OpSU->NumSuccsLeft++;
 657           }
 658         }
 659       }
 660     } else {
 661       // Find node predecessors.
 662       for (unsigned j = 0, e = N->getNumOperands(); j != e; j++) {
 663         SDOperand Op  = N->getOperand(j);
 664         SDNode   *OpN = Op.Val;
 665         MVT::ValueType VT = OpN->getValueType(Op.ResNo);
 666         if (!isPassiveNode(OpN)) {
 667           assert(VT != MVT::Flag);
 668           SUnit *OpSU = SUnitMap[OpN];
 669           if (VT == MVT::Other) {
 670             if (SU->ChainPreds.insert(OpSU).second)
 671               SU->NumChainPredsLeft++;
 672             if (OpSU->ChainSuccs.insert(SU).second)
 673               OpSU->NumChainSuccsLeft++;
 674           } else {
 675             if (SU->Preds.insert(OpSU).second)
 676               SU->NumPredsLeft++;
 677             if (OpSU->Succs.insert(SU).second)
 678               OpSU->NumSuccsLeft++;
 679             if (j == 0 && SU->isTwoAddress)
 680               OpSU->isDefNUseOperand = true;
 681           }
 682         }
 683       }
 684     }
 685   }
 686 }
 687
 688 /// EmitSchedule - Emit the machine code in scheduled order.
 689 void ScheduleDAGList::EmitSchedule() {
 690   for (unsigned i = 0, e = Sequence.size(); i != e; i++) {
 691     SDNode *N;
 692     SUnit *SU = Sequence[i];
 693     for (unsigned j = 0, ee = SU->FlaggedNodes.size(); j != ee; j++) {
 694       N = SU->FlaggedNodes[j];
 695       EmitNode(getNI(N));
 696     }
 697     EmitNode(getNI(SU->Node));
 698   }
 699 }
 700
 701 /// dump - dump the schedule.
 702 void ScheduleDAGList::dump() const {
 703   for (unsigned i = 0, e = Sequence.size(); i != e; i++) {
 704     SUnit *SU = Sequence[i];
 705     SU->dump(&DAG, false);
 706   }
 707 }
 708
 709 /// Schedule - Schedule the DAG using list scheduling.
 710 /// FIXME: Right now it only supports the burr (bottom up register reducing)
 711 /// heuristic.
 712 void ScheduleDAGList::Schedule() {
 713   DEBUG(std::cerr << "********** List Scheduling **********\n");
 714
 715   // Build scheduling units.
 716   BuildSchedUnits();
 717
 718   // Calculate node prirorities.
 719   CalculatePriorities();
 720
 721   // Execute the actual scheduling loop Top-Down or Bottom-Up as appropriate.
 722   if (isBottomUp)
 723     ListScheduleBottomUp();
 724   else
 725     ListScheduleTopDown();
 726
 727   DEBUG(std::cerr << "*** Final schedule ***\n");
 728   DEBUG(dump());
 729   DEBUG(std::cerr << "\n");
 730
 731   // Emit in scheduled order
 732   EmitSchedule();
 733 }
 734
 735 llvm::ScheduleDAG* llvm::createBURRListDAGScheduler(SelectionDAG &DAG,
 736                                                     MachineBasicBlock *BB) {
 737   return new ScheduleDAGList(DAG, BB, DAG.getTarget(), true);
 738 }
 739
 740 /// G5HazardRecognizer - A hazard recognizer for the PowerPC G5 processor.
 741 /// FIXME: Move to the PowerPC backend.
 742 class G5HazardRecognizer : public HazardRecognizer {
 743   // Totally bogus hazard recognizer, used to test noop insertion. This requires
 744   // a noop between copyfromreg's.
 745   unsigned EmittedCopyFromReg;
 746 public:
 747   G5HazardRecognizer() {
 748     EmittedCopyFromReg = 0;
 749   }
 750
 751   virtual HazardType getHazardType(SDNode *Node) {
 752     if (Node->getOpcode() == ISD::CopyFromReg && EmittedCopyFromReg)
 753       return NoopHazard;
 754     return NoHazard;
 755   }
 756
 757   /// EmitInstruction - This callback is invoked when an instruction is
 758   /// emitted, to advance the hazard state.
 759   virtual void EmitInstruction(SDNode *Node) {
 760     if (Node->getOpcode() == ISD::CopyFromReg) {
 761       EmittedCopyFromReg = 5;
 762     } else if (EmittedCopyFromReg) {
 763       --EmittedCopyFromReg;
 764     }
 765   }
 766
 767   /// AdvanceCycle - This callback is invoked when no instructions can be
 768   /// issued on this cycle without a hazard.  This should increment the
 769   /// internal state of the hazard recognizer so that previously "Hazard"
 770   /// instructions will now not be hazards.
 771   virtual void AdvanceCycle() {
 772   }
 773
 774   /// EmitNoop - This callback is invoked when a noop was added to the
 775   /// instruction stream.
 776   virtual void EmitNoop() {
 777     --EmittedCopyFromReg;
 778   }
 779 };
 780
 781
 782 /// createTDG5ListDAGScheduler - This creates a top-down list scheduler for
 783 /// the PowerPC G5.  FIXME: pull the priority function out into the PPC
 784 /// backend!
 785 ScheduleDAG* llvm::createTDG5ListDAGScheduler(SelectionDAG &DAG,
 786                                               MachineBasicBlock *BB) {
 787   return new ScheduleDAGList(DAG, BB, DAG.getTarget(), false,
 788                              new G5HazardRecognizer());
 789 }