lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp

   1 //===----- ScheduleDAGList.cpp - Reg pressure reduction list scheduler ----===//
   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 register pressure reduction list
  11 // schedulers, using standard algorithms.  The basic approach uses a priority
  12 // queue of available nodes to schedule.  One at a time, nodes are taken from
  13 // the priority queue (thus in priority order), checked for legality to
  14 // schedule, and emitted if legal.
  15 //
  16 //===----------------------------------------------------------------------===//
  17
  18 #define DEBUG_TYPE "sched"
  19 #include "llvm/CodeGen/ScheduleDAG.h"
  20 #include "llvm/CodeGen/SSARegMap.h"
  21 #include "llvm/Target/MRegisterInfo.h"
  22 #include "llvm/Target/TargetMachine.h"
  23 #include "llvm/Target/TargetInstrInfo.h"
  24 #include "llvm/Support/Debug.h"
  25 #include "llvm/ADT/Statistic.h"
  26 #include <climits>
  27 #include <iostream>
  28 #include <queue>
  29 #include "llvm/Support/CommandLine.h"
  30 using namespace llvm;
  31
  32 namespace {
  33   cl::opt<bool> SchedLowerDefNUse("sched-lower-defnuse", cl::Hidden);
  34 }
  35
  36 namespace {
  37 //===----------------------------------------------------------------------===//
  38 /// ScheduleDAGRRList - The actual register reduction list scheduler
  39 /// implementation.  This supports both top-down and bottom-up scheduling.
  40 ///
  41
  42 class ScheduleDAGRRList : public ScheduleDAG {
  43 private:
  44   /// isBottomUp - This is true if the scheduling problem is bottom-up, false if
  45   /// it is top-down.
  46   bool isBottomUp;
  47
  48   /// AvailableQueue - The priority queue to use for the available SUnits.
  49   ///
  50   SchedulingPriorityQueue *AvailableQueue;
  51
  52 public:
  53   ScheduleDAGRRList(SelectionDAG &dag, MachineBasicBlock *bb,
  54                   const TargetMachine &tm, bool isbottomup,
  55                   SchedulingPriorityQueue *availqueue)
  56     : ScheduleDAG(dag, bb, tm), isBottomUp(isbottomup),
  57       AvailableQueue(availqueue) {
  58     }
  59
  60   ~ScheduleDAGRRList() {
  61     delete AvailableQueue;
  62   }
  63
  64   void Schedule();
  65
  66 private:
  67   void ReleasePred(SUnit *PredSU, bool isChain, unsigned CurCycle);
  68   void ReleaseSucc(SUnit *SuccSU, bool isChain, unsigned CurCycle);
  69   void ScheduleNodeBottomUp(SUnit *SU, unsigned& CurCycle);
  70   void ScheduleNodeTopDown(SUnit *SU, unsigned& CurCycle);
  71   void ListScheduleTopDown();
  72   void ListScheduleBottomUp();
  73 };
  74 }  // end anonymous namespace
  75
  76
  77 /// Schedule - Schedule the DAG using list scheduling.
  78 void ScheduleDAGRRList::Schedule() {
  79   DEBUG(std::cerr << "********** List Scheduling **********\n");
  80
  81   // Build scheduling units.
  82   BuildSchedUnits();
  83
  84   CalculateDepths();
  85   CalculateHeights();
  86   DEBUG(for (unsigned su = 0, e = SUnits.size(); su != e; ++su)
  87         SUnits[su].dumpAll(&DAG));
  88
  89   AvailableQueue->initNodes(SUnits);
  90
  91   // Execute the actual scheduling loop Top-Down or Bottom-Up as appropriate.
  92   if (isBottomUp)
  93     ListScheduleBottomUp();
  94   else
  95     ListScheduleTopDown();
  96
  97   AvailableQueue->releaseState();
  98
  99   DEBUG(std::cerr << "*** Final schedule ***\n");
 100   DEBUG(dumpSchedule());
 101   DEBUG(std::cerr << "\n");
 102
 103   // Emit in scheduled order
 104   EmitSchedule();
 105 }
 106
 107
 108 //===----------------------------------------------------------------------===//
 109 //  Bottom-Up Scheduling
 110 //===----------------------------------------------------------------------===//
 111
 112 static const TargetRegisterClass *getRegClass(SUnit *SU,
 113                                               const TargetInstrInfo *TII,
 114                                               const MRegisterInfo *MRI,
 115                                               SSARegMap *RegMap) {
 116   if (SU->Node->isTargetOpcode()) {
 117     unsigned Opc = SU->Node->getTargetOpcode();
 118     const TargetInstrDescriptor &II = TII->get(Opc);
 119     return II.OpInfo->RegClass;
 120   } else {
 121     assert(SU->Node->getOpcode() == ISD::CopyFromReg);
 122     unsigned SrcReg = cast<RegisterSDNode>(SU->Node->getOperand(1))->getReg();
 123     if (MRegisterInfo::isVirtualRegister(SrcReg))
 124       return RegMap->getRegClass(SrcReg);
 125     else {
 126       for (MRegisterInfo::regclass_iterator I = MRI->regclass_begin(),
 127              E = MRI->regclass_end(); I != E; ++I)
 128         if ((*I)->hasType(SU->Node->getValueType(0)) &&
 129             (*I)->contains(SrcReg))
 130           return *I;
 131       assert(false && "Couldn't find register class for reg copy!");
 132     }
 133     return NULL;
 134   }
 135 }
 136
 137 static unsigned getNumResults(SUnit *SU) {
 138   unsigned NumResults = 0;
 139   for (unsigned i = 0, e = SU->Node->getNumValues(); i != e; ++i) {
 140     MVT::ValueType VT = SU->Node->getValueType(i);
 141     if (VT != MVT::Other && VT != MVT::Flag)
 142       NumResults++;
 143   }
 144   return NumResults;
 145 }
 146
 147 /// ReleasePred - Decrement the NumSuccsLeft count of a predecessor. Add it to
 148 /// the Available queue is the count reaches zero. Also update its cycle bound.
 149 void ScheduleDAGRRList::ReleasePred(SUnit *PredSU, bool isChain,
 150                                     unsigned CurCycle) {
 151   // FIXME: the distance between two nodes is not always == the predecessor's
 152   // latency. For example, the reader can very well read the register written
 153   // by the predecessor later than the issue cycle. It also depends on the
 154   // interrupt model (drain vs. freeze).
 155   PredSU->CycleBound = std::max(PredSU->CycleBound, CurCycle + PredSU->Latency);
 156
 157   if (!isChain)
 158     PredSU->NumSuccsLeft--;
 159   else
 160     PredSU->NumChainSuccsLeft--;
 161
 162 #ifndef NDEBUG
 163   if (PredSU->NumSuccsLeft < 0 || PredSU->NumChainSuccsLeft < 0) {
 164     std::cerr << "*** List scheduling failed! ***\n";
 165     PredSU->dump(&DAG);
 166     std::cerr << " has been released too many times!\n";
 167     assert(0);
 168   }
 169 #endif
 170
 171   if ((PredSU->NumSuccsLeft + PredSU->NumChainSuccsLeft) == 0) {
 172     // EntryToken has to go last!  Special case it here.
 173     if (PredSU->Node->getOpcode() != ISD::EntryToken) {
 174       PredSU->isAvailable = true;
 175       AvailableQueue->push(PredSU);
 176     }
 177   }
 178 }
 179
 180 /// ScheduleNodeBottomUp - Add the node to the schedule. Decrement the pending
 181 /// count of its predecessors. If a predecessor pending count is zero, add it to
 182 /// the Available queue.
 183 void ScheduleDAGRRList::ScheduleNodeBottomUp(SUnit *SU, unsigned& CurCycle) {
 184   DEBUG(std::cerr << "*** Scheduling [" << CurCycle << "]: ");
 185   DEBUG(SU->dump(&DAG));
 186   SU->Cycle = CurCycle;
 187
 188   AvailableQueue->ScheduledNode(SU);
 189   Sequence.push_back(SU);
 190
 191   // Bottom up: release predecessors
 192   for (std::set<std::pair<SUnit*, bool> >::iterator I = SU->Preds.begin(),
 193          E = SU->Preds.end(); I != E; ++I)
 194     ReleasePred(I->first, I->second, CurCycle);
 195   SU->isScheduled = true;
 196   CurCycle++;
 197 }
 198
 199 /// isReady - True if node's lower cycle bound is less or equal to the current
 200 /// scheduling cycle. Always true if all nodes have uniform latency 1.
 201 static inline bool isReady(SUnit *SU, unsigned CurCycle) {
 202   return SU->CycleBound <= CurCycle;
 203 }
 204
 205 /// ListScheduleBottomUp - The main loop of list scheduling for bottom-up
 206 /// schedulers.
 207 void ScheduleDAGRRList::ListScheduleBottomUp() {
 208   unsigned CurCycle = 0;
 209   // Add root to Available queue.
 210   AvailableQueue->push(SUnitMap[DAG.getRoot().Val]);
 211
 212   // While Available queue is not empty, grab the node with the highest
 213   // priority. If it is not ready put it back. Schedule the node.
 214   std::vector<SUnit*> NotReady;
 215   SUnit *CurNode = NULL;
 216   while (!AvailableQueue->empty()) {
 217     SUnit *CurNode = AvailableQueue->pop();
 218     while (!isReady(CurNode, CurCycle)) {
 219       NotReady.push_back(CurNode);
 220       CurNode = AvailableQueue->pop();
 221     }
 222
 223     // Add the nodes that aren't ready back onto the available list.
 224     AvailableQueue->push_all(NotReady);
 225     NotReady.clear();
 226
 227     ScheduleNodeBottomUp(CurNode, CurCycle);
 228   }
 229
 230   // Add entry node last
 231   if (DAG.getEntryNode().Val != DAG.getRoot().Val) {
 232     SUnit *Entry = SUnitMap[DAG.getEntryNode().Val];
 233     Sequence.push_back(Entry);
 234   }
 235
 236   // Reverse the order if it is bottom up.
 237   std::reverse(Sequence.begin(), Sequence.end());
 238
 239
 240 #ifndef NDEBUG
 241   // Verify that all SUnits were scheduled.
 242   bool AnyNotSched = false;
 243   for (unsigned i = 0, e = SUnits.size(); i != e; ++i) {
 244     if (SUnits[i].NumSuccsLeft != 0 || SUnits[i].NumChainSuccsLeft != 0) {
 245       if (!AnyNotSched)
 246         std::cerr << "*** List scheduling failed! ***\n";
 247       SUnits[i].dump(&DAG);
 248       std::cerr << "has not been scheduled!\n";
 249       AnyNotSched = true;
 250     }
 251   }
 252   assert(!AnyNotSched);
 253 #endif
 254 }
 255
 256 //===----------------------------------------------------------------------===//
 257 //  Top-Down Scheduling
 258 //===----------------------------------------------------------------------===//
 259
 260 /// ReleaseSucc - Decrement the NumPredsLeft count of a successor. Add it to
 261 /// the PendingQueue if the count reaches zero.
 262 void ScheduleDAGRRList::ReleaseSucc(SUnit *SuccSU, bool isChain,
 263                                     unsigned CurCycle) {
 264   // FIXME: the distance between two nodes is not always == the predecessor's
 265   // latency. For example, the reader can very well read the register written
 266   // by the predecessor later than the issue cycle. It also depends on the
 267   // interrupt model (drain vs. freeze).
 268   SuccSU->CycleBound = std::max(SuccSU->CycleBound, CurCycle + SuccSU->Latency);
 269
 270   if (!isChain)
 271     SuccSU->NumPredsLeft--;
 272   else
 273     SuccSU->NumChainPredsLeft--;
 274
 275 #ifndef NDEBUG
 276   if (SuccSU->NumPredsLeft < 0 || SuccSU->NumChainPredsLeft < 0) {
 277     std::cerr << "*** List scheduling failed! ***\n";
 278     SuccSU->dump(&DAG);
 279     std::cerr << " has been released too many times!\n";
 280     assert(0);
 281   }
 282 #endif
 283
 284   if ((SuccSU->NumPredsLeft + SuccSU->NumChainPredsLeft) == 0) {
 285     SuccSU->isAvailable = true;
 286     AvailableQueue->push(SuccSU);
 287   }
 288 }
 289
 290
 291 /// ScheduleNodeTopDown - Add the node to the schedule. Decrement the pending
 292 /// count of its successors. If a successor pending count is zero, add it to
 293 /// the Available queue.
 294 void ScheduleDAGRRList::ScheduleNodeTopDown(SUnit *SU, unsigned& CurCycle) {
 295   DEBUG(std::cerr << "*** Scheduling [" << CurCycle << "]: ");
 296   DEBUG(SU->dump(&DAG));
 297   SU->Cycle = CurCycle;
 298
 299   AvailableQueue->ScheduledNode(SU);
 300   Sequence.push_back(SU);
 301
 302   // Top down: release successors
 303   for (std::set<std::pair<SUnit*, bool> >::iterator I = SU->Succs.begin(),
 304          E = SU->Succs.end(); I != E; ++I)
 305     ReleaseSucc(I->first, I->second, CurCycle);
 306   SU->isScheduled = true;
 307   CurCycle++;
 308 }
 309
 310 void ScheduleDAGRRList::ListScheduleTopDown() {
 311   unsigned CurCycle = 0;
 312   SUnit *Entry = SUnitMap[DAG.getEntryNode().Val];
 313
 314   // All leaves to Available queue.
 315   for (unsigned i = 0, e = SUnits.size(); i != e; ++i) {
 316     // It is available if it has no predecessors.
 317     if (SUnits[i].Preds.size() == 0 && &SUnits[i] != Entry) {
 318       AvailableQueue->push(&SUnits[i]);
 319       SUnits[i].isAvailable = true;
 320     }
 321   }
 322
 323   // Emit the entry node first.
 324   ScheduleNodeTopDown(Entry, CurCycle);
 325
 326   // While Available queue is not empty, grab the node with the highest
 327   // priority. If it is not ready put it back. Schedule the node.
 328   std::vector<SUnit*> NotReady;
 329   SUnit *CurNode = NULL;
 330   while (!AvailableQueue->empty()) {
 331     SUnit *CurNode = AvailableQueue->pop();
 332     while (!isReady(CurNode, CurCycle)) {
 333       NotReady.push_back(CurNode);
 334       CurNode = AvailableQueue->pop();
 335     }
 336
 337     // Add the nodes that aren't ready back onto the available list.
 338     AvailableQueue->push_all(NotReady);
 339     NotReady.clear();
 340
 341     ScheduleNodeTopDown(CurNode, CurCycle);
 342   }
 343
 344
 345 #ifndef NDEBUG
 346   // Verify that all SUnits were scheduled.
 347   bool AnyNotSched = false;
 348   for (unsigned i = 0, e = SUnits.size(); i != e; ++i) {
 349     if (!SUnits[i].isScheduled) {
 350       if (!AnyNotSched)
 351         std::cerr << "*** List scheduling failed! ***\n";
 352       SUnits[i].dump(&DAG);
 353       std::cerr << "has not been scheduled!\n";
 354       AnyNotSched = true;
 355     }
 356   }
 357   assert(!AnyNotSched);
 358 #endif
 359 }
 360
 361
 362
 363 //===----------------------------------------------------------------------===//
 364 //                RegReductionPriorityQueue Implementation
 365 //===----------------------------------------------------------------------===//
 366 //
 367 // This is a SchedulingPriorityQueue that schedules using Sethi Ullman numbers
 368 // to reduce register pressure.
 369 //
 370 namespace {
 371   template<class SF>
 372   class RegReductionPriorityQueue;
 373
 374   /// Sorting functions for the Available queue.
 375   struct bu_ls_rr_sort : public std::binary_function<SUnit*, SUnit*, bool> {
 376     RegReductionPriorityQueue<bu_ls_rr_sort> *SPQ;
 377     bu_ls_rr_sort(RegReductionPriorityQueue<bu_ls_rr_sort> *spq) : SPQ(spq) {}
 378     bu_ls_rr_sort(const bu_ls_rr_sort &RHS) : SPQ(RHS.SPQ) {}
 379
 380     bool operator()(const SUnit* left, const SUnit* right) const;
 381   };
 382
 383   struct td_ls_rr_sort : public std::binary_function<SUnit*, SUnit*, bool> {
 384     RegReductionPriorityQueue<td_ls_rr_sort> *SPQ;
 385     td_ls_rr_sort(RegReductionPriorityQueue<td_ls_rr_sort> *spq) : SPQ(spq) {}
 386     td_ls_rr_sort(const td_ls_rr_sort &RHS) : SPQ(RHS.SPQ) {}
 387
 388     bool operator()(const SUnit* left, const SUnit* right) const;
 389   };
 390 }  // end anonymous namespace
 391
 392 namespace {
 393   template<class SF>
 394   class RegReductionPriorityQueue : public SchedulingPriorityQueue {
 395     std::priority_queue<SUnit*, std::vector<SUnit*>, SF> Queue;
 396
 397   public:
 398     RegReductionPriorityQueue() :
 399     Queue(SF(this)) {}
 400
 401     virtual void initNodes(const std::vector<SUnit> &sunits) {}
 402     virtual void releaseState() {}
 403
 404     virtual int getSethiUllmanNumber(unsigned NodeNum) const {
 405       return 0;
 406     }
 407
 408     bool empty() const { return Queue.empty(); }
 409
 410     void push(SUnit *U) {
 411       Queue.push(U);
 412     }
 413     void push_all(const std::vector<SUnit *> &Nodes) {
 414       for (unsigned i = 0, e = Nodes.size(); i != e; ++i)
 415         Queue.push(Nodes[i]);
 416     }
 417
 418     SUnit *pop() {
 419       SUnit *V = Queue.top();
 420       Queue.pop();
 421       return V;
 422     }
 423   };
 424
 425   template<class SF>
 426   class BURegReductionPriorityQueue : public RegReductionPriorityQueue<SF> {
 427     // SUnits - The SUnits for the current graph.
 428     const std::vector<SUnit> *SUnits;
 429
 430     // SethiUllmanNumbers - The SethiUllman number for each node.
 431     std::vector<int> SethiUllmanNumbers;
 432
 433   public:
 434     BURegReductionPriorityQueue() {}
 435
 436     void initNodes(const std::vector<SUnit> &sunits) {
 437       SUnits = &sunits;
 438       // Add pseudo dependency edges for two-address nodes.
 439       if (SchedLowerDefNUse)
 440         AddPseudoTwoAddrDeps();
 441       // Calculate node priorities.
 442       CalculatePriorities();
 443     }
 444
 445     void releaseState() {
 446       SUnits = 0;
 447       SethiUllmanNumbers.clear();
 448     }
 449
 450     int getSethiUllmanNumber(unsigned NodeNum) const {
 451       assert(NodeNum < SethiUllmanNumbers.size());
 452       return SethiUllmanNumbers[NodeNum];
 453     }
 454
 455   private:
 456     void AddPseudoTwoAddrDeps();
 457     void CalculatePriorities();
 458     int CalcNodePriority(const SUnit *SU);
 459   };
 460
 461
 462   template<class SF>
 463   class TDRegReductionPriorityQueue : public RegReductionPriorityQueue<SF> {
 464     // SUnits - The SUnits for the current graph.
 465     const std::vector<SUnit> *SUnits;
 466
 467     // SethiUllmanNumbers - The SethiUllman number for each node.
 468     std::vector<int> SethiUllmanNumbers;
 469
 470   public:
 471     TDRegReductionPriorityQueue() {}
 472
 473     void initNodes(const std::vector<SUnit> &sunits) {
 474       SUnits = &sunits;
 475       // Calculate node priorities.
 476       CalculatePriorities();
 477     }
 478
 479     void releaseState() {
 480       SUnits = 0;
 481       SethiUllmanNumbers.clear();
 482     }
 483
 484     int getSethiUllmanNumber(unsigned NodeNum) const {
 485       assert(NodeNum < SethiUllmanNumbers.size());
 486       return SethiUllmanNumbers[NodeNum];
 487     }
 488
 489   private:
 490     void CalculatePriorities();
 491     int CalcNodePriority(const SUnit *SU);
 492   };
 493 }
 494
 495 // Bottom up
 496 bool bu_ls_rr_sort::operator()(const SUnit *left, const SUnit *right) const {
 497   unsigned LeftNum  = left->NodeNum;
 498   unsigned RightNum = right->NodeNum;
 499   bool LIsTarget = left->Node->isTargetOpcode();
 500   bool RIsTarget = right->Node->isTargetOpcode();
 501   int LPriority = SPQ->getSethiUllmanNumber(LeftNum);
 502   int RPriority = SPQ->getSethiUllmanNumber(RightNum);
 503   bool LIsFloater = LIsTarget && (LPriority == 1 || LPriority == 0);
 504   bool RIsFloater = RIsTarget && (RPriority == 1 || RPriority == 0);
 505   int LBonus = 0;
 506   int RBonus = 0;
 507
 508   // Schedule floaters (e.g. load from some constant address) and those nodes
 509   // with a single predecessor each first. They maintain / reduce register
 510   // pressure.
 511   if (LIsFloater)
 512     LBonus += 2;
 513   if (RIsFloater)
 514     RBonus += 2;
 515
 516   if (!SchedLowerDefNUse) {
 517     // Special tie breaker: if two nodes share a operand, the one that use it
 518     // as a def&use operand is preferred.
 519     if (LIsTarget && RIsTarget) {
 520       if (left->isTwoAddress && !right->isTwoAddress) {
 521         SDNode *DUNode = left->Node->getOperand(0).Val;
 522         if (DUNode->isOperand(right->Node))
 523           LBonus += 2;
 524       }
 525       if (!left->isTwoAddress && right->isTwoAddress) {
 526         SDNode *DUNode = right->Node->getOperand(0).Val;
 527         if (DUNode->isOperand(left->Node))
 528           RBonus += 2;
 529       }
 530     }
 531   }
 532
 533   if (LPriority+LBonus < RPriority+RBonus)
 534     return true;
 535   else if (LPriority+LBonus == RPriority+RBonus)
 536     if (left->NumPredsLeft > right->NumPredsLeft)
 537       return true;
 538     else if (left->NumPredsLeft+LBonus == right->NumPredsLeft+RBonus)
 539       if (left->CycleBound > right->CycleBound)
 540         return true;
 541   return false;
 542 }
 543
 544 static inline bool isCopyFromLiveIn(const SUnit *SU) {
 545   SDNode *N = SU->Node;
 546   return N->getOpcode() == ISD::CopyFromReg &&
 547     N->getOperand(N->getNumOperands()-1).getValueType() != MVT::Flag;
 548 }
 549
 550 // FIXME: This is probably too slow!
 551 static void isReachable(SUnit *SU, SUnit *TargetSU,
 552                         std::set<SUnit *> &Visited, bool &Reached) {
 553   if (Reached) return;
 554   if (SU == TargetSU) {
 555     Reached = true;
 556     return;
 557   }
 558   if (!Visited.insert(SU).second) return;
 559
 560   for (std::set<std::pair<SUnit*, bool> >::iterator I = SU->Preds.begin(),
 561          E = SU->Preds.end(); I != E; ++I)
 562     isReachable(I->first, TargetSU, Visited, Reached);
 563 }
 564
 565 static bool isReachable(SUnit *SU, SUnit *TargetSU) {
 566   std::set<SUnit *> Visited;
 567   bool Reached = false;
 568   isReachable(SU, TargetSU, Visited, Reached);
 569   return Reached;
 570 }
 571
 572 static SUnit *getDefUsePredecessor(SUnit *SU) {
 573   SDNode *DU = SU->Node->getOperand(0).Val;
 574   for (std::set<std::pair<SUnit*, bool> >::iterator
 575          I = SU->Preds.begin(), E = SU->Preds.end(); I != E; ++I) {
 576     if (I->second) continue;  // ignore chain preds
 577     SUnit *PredSU = I->first;
 578     if (PredSU->Node == DU)
 579       return PredSU;
 580   }
 581
 582   // Must be flagged.
 583   return NULL;
 584 }
 585
 586 static bool canClobber(SUnit *SU, SUnit *Op) {
 587   if (SU->isTwoAddress)
 588     return Op == getDefUsePredecessor(SU);
 589   return false;
 590 }
 591
 592 /// AddPseudoTwoAddrDeps - If two nodes share an operand and one of them uses
 593 /// it as a def&use operand. Add a pseudo control edge from it to the other
 594 /// node (if it won't create a cycle) so the two-address one will be scheduled
 595 /// first (lower in the schedule).
 596 template<class SF>
 597 void BURegReductionPriorityQueue<SF>::AddPseudoTwoAddrDeps() {
 598   for (unsigned i = 0, e = SUnits->size(); i != e; ++i) {
 599     SUnit *SU = (SUnit *)&((*SUnits)[i]);
 600     SDNode *Node = SU->Node;
 601     if (!Node->isTargetOpcode())
 602       continue;
 603
 604     if (SU->isTwoAddress) {
 605       unsigned Depth = SU->Node->getNodeDepth();
 606       SUnit *DUSU = getDefUsePredecessor(SU);
 607       if (!DUSU) continue;
 608
 609       for (std::set<std::pair<SUnit*, bool> >::iterator I = DUSU->Succs.begin(),
 610              E = DUSU->Succs.end(); I != E; ++I) {
 611         SUnit *SuccSU = I->first;
 612         if (SuccSU != SU && !canClobber(SuccSU, DUSU)) {
 613           if (SuccSU->Node->getNodeDepth() <= Depth+2 &&
 614               !isReachable(SuccSU, SU)) {
 615             DEBUG(std::cerr << "Adding an edge from SU # " << SU->NodeNum
 616                   << " to SU #" << SuccSU->NodeNum << "\n");
 617             if (SU->Preds.insert(std::make_pair(SuccSU, true)).second)
 618               SU->NumChainPredsLeft++;
 619             if (SuccSU->Succs.insert(std::make_pair(SU, true)).second)
 620               SuccSU->NumChainSuccsLeft++;
 621           }
 622         }
 623       }
 624     }
 625   }
 626 }
 627
 628 /// CalcNodePriority - Priority is the Sethi Ullman number.
 629 /// Smaller number is the higher priority.
 630 template<class SF>
 631 int BURegReductionPriorityQueue<SF>::CalcNodePriority(const SUnit *SU) {
 632   int &SethiUllmanNumber = SethiUllmanNumbers[SU->NodeNum];
 633   if (SethiUllmanNumber != 0)
 634     return SethiUllmanNumber;
 635
 636   unsigned Opc = SU->Node->getOpcode();
 637   if (Opc == ISD::TokenFactor || Opc == ISD::CopyToReg)
 638     SethiUllmanNumber = INT_MAX - 10;
 639   else if (SU->NumSuccsLeft == 0)
 640     // If SU does not have a use, i.e. it doesn't produce a value that would
 641     // be consumed (e.g. store), then it terminates a chain of computation.
 642     // Give it a small SethiUllman number so it will be scheduled right before its
 643     // predecessors that it doesn't lengthen their live ranges.
 644     SethiUllmanNumber = INT_MIN + 10;
 645   else if (SU->NumPredsLeft == 0 &&
 646            (Opc != ISD::CopyFromReg || isCopyFromLiveIn(SU)))
 647     SethiUllmanNumber = 1;
 648   else {
 649     int Extra = 0;
 650     for (std::set<std::pair<SUnit*, bool> >::const_iterator
 651          I = SU->Preds.begin(), E = SU->Preds.end(); I != E; ++I) {
 652       if (I->second) continue;  // ignore chain preds
 653       SUnit *PredSU = I->first;
 654       int PredSethiUllman = CalcNodePriority(PredSU);
 655       if (PredSethiUllman > SethiUllmanNumber) {
 656         SethiUllmanNumber = PredSethiUllman;
 657         Extra = 0;
 658       } else if (PredSethiUllman == SethiUllmanNumber && !I->second)
 659         Extra++;
 660     }
 661
 662     SethiUllmanNumber += Extra;
 663   }
 664
 665   return SethiUllmanNumber;
 666 }
 667
 668 /// CalculatePriorities - Calculate priorities of all scheduling units.
 669 template<class SF>
 670 void BURegReductionPriorityQueue<SF>::CalculatePriorities() {
 671   SethiUllmanNumbers.assign(SUnits->size(), 0);
 672
 673   for (unsigned i = 0, e = SUnits->size(); i != e; ++i)
 674     CalcNodePriority(&(*SUnits)[i]);
 675 }
 676
 677 static unsigned SumOfUnscheduledPredsOfSuccs(const SUnit *SU) {
 678   unsigned Sum = 0;
 679   for (std::set<std::pair<SUnit*, bool> >::const_iterator
 680          I = SU->Succs.begin(), E = SU->Succs.end(); I != E; ++I) {
 681     SUnit *SuccSU = I->first;
 682     for (std::set<std::pair<SUnit*, bool> >::const_iterator
 683          II = SuccSU->Preds.begin(), EE = SuccSU->Preds.end(); II != EE; ++II) {
 684       SUnit *PredSU = II->first;
 685       if (!PredSU->isScheduled)
 686         Sum++;
 687     }
 688   }
 689
 690   return Sum;
 691 }
 692
 693
 694 // Top down
 695 bool td_ls_rr_sort::operator()(const SUnit *left, const SUnit *right) const {
 696   unsigned LeftNum  = left->NodeNum;
 697   unsigned RightNum = right->NodeNum;
 698   int LPriority = SPQ->getSethiUllmanNumber(LeftNum);
 699   int RPriority = SPQ->getSethiUllmanNumber(RightNum);
 700   bool LIsTarget = left->Node->isTargetOpcode();
 701   bool RIsTarget = right->Node->isTargetOpcode();
 702   bool LIsFloater = LIsTarget && left->NumPreds == 0;
 703   bool RIsFloater = RIsTarget && right->NumPreds == 0;
 704   unsigned LBonus = (SumOfUnscheduledPredsOfSuccs(left) == 1) ? 2 : 0;
 705   unsigned RBonus = (SumOfUnscheduledPredsOfSuccs(right) == 1) ? 2 : 0;
 706
 707   if (left->NumSuccs == 0 && right->NumSuccs != 0)
 708     return false;
 709   else if (left->NumSuccs != 0 && right->NumSuccs == 0)
 710     return true;
 711
 712   // Special tie breaker: if two nodes share a operand, the one that use it
 713   // as a def&use operand is preferred.
 714   if (LIsTarget && RIsTarget) {
 715     if (left->isTwoAddress && !right->isTwoAddress) {
 716       SDNode *DUNode = left->Node->getOperand(0).Val;
 717       if (DUNode->isOperand(right->Node))
 718         RBonus += 2;
 719     }
 720     if (!left->isTwoAddress && right->isTwoAddress) {
 721       SDNode *DUNode = right->Node->getOperand(0).Val;
 722       if (DUNode->isOperand(left->Node))
 723         LBonus += 2;
 724     }
 725   }
 726   if (LIsFloater)
 727     LBonus -= 2;
 728   if (RIsFloater)
 729     RBonus -= 2;
 730   if (left->NumSuccs == 1)
 731     LBonus += 2;
 732   if (right->NumSuccs == 1)
 733     RBonus += 2;
 734
 735   if (LPriority+LBonus < RPriority+RBonus)
 736     return true;
 737   else if (LPriority == RPriority)
 738     if (left->Depth < right->Depth)
 739       return true;
 740     else if (left->Depth == right->Depth)
 741       if (left->NumSuccsLeft > right->NumSuccsLeft)
 742         return true;
 743       else if (left->NumSuccsLeft == right->NumSuccsLeft)
 744         if (left->CycleBound > right->CycleBound)
 745           return true;
 746   return false;
 747 }
 748
 749 /// CalcNodePriority - Priority is the Sethi Ullman number.
 750 /// Smaller number is the higher priority.
 751 template<class SF>
 752 int TDRegReductionPriorityQueue<SF>::CalcNodePriority(const SUnit *SU) {
 753   int &SethiUllmanNumber = SethiUllmanNumbers[SU->NodeNum];
 754   if (SethiUllmanNumber != 0)
 755     return SethiUllmanNumber;
 756
 757   unsigned Opc = SU->Node->getOpcode();
 758   if (Opc == ISD::TokenFactor || Opc == ISD::CopyToReg)
 759     SethiUllmanNumber = INT_MAX - 10;
 760   else if (SU->NumSuccsLeft == 0)
 761     // If SU does not have a use, i.e. it doesn't produce a value that would
 762     // be consumed (e.g. store), then it terminates a chain of computation.
 763     // Give it a small SethiUllman number so it will be scheduled right before its
 764     // predecessors that it doesn't lengthen their live ranges.
 765     SethiUllmanNumber = INT_MIN + 10;
 766   else if (SU->NumPredsLeft == 0 &&
 767            (Opc != ISD::CopyFromReg || isCopyFromLiveIn(SU)))
 768     SethiUllmanNumber = 1;
 769   else {
 770     int Extra = 0;
 771     for (std::set<std::pair<SUnit*, bool> >::const_iterator
 772          I = SU->Preds.begin(), E = SU->Preds.end(); I != E; ++I) {
 773       if (I->second) continue;  // ignore chain preds
 774       SUnit *PredSU = I->first;
 775       int PredSethiUllman = CalcNodePriority(PredSU);
 776       if (PredSethiUllman > SethiUllmanNumber) {
 777         SethiUllmanNumber = PredSethiUllman;
 778         Extra = 0;
 779       } else if (PredSethiUllman == SethiUllmanNumber && !I->second)
 780         Extra++;
 781     }
 782
 783     SethiUllmanNumber += Extra;
 784   }
 785
 786   return SethiUllmanNumber;
 787 }
 788
 789 /// CalculatePriorities - Calculate priorities of all scheduling units.
 790 template<class SF>
 791 void TDRegReductionPriorityQueue<SF>::CalculatePriorities() {
 792   SethiUllmanNumbers.assign(SUnits->size(), 0);
 793
 794   for (unsigned i = 0, e = SUnits->size(); i != e; ++i)
 795     CalcNodePriority(&(*SUnits)[i]);
 796 }
 797
 798 //===----------------------------------------------------------------------===//
 799 //                         Public Constructor Functions
 800 //===----------------------------------------------------------------------===//
 801
 802 llvm::ScheduleDAG* llvm::createBURRListDAGScheduler(SelectionDAG &DAG,
 803                                                     MachineBasicBlock *BB) {
 804   return new ScheduleDAGRRList(DAG, BB, DAG.getTarget(), true,
 805                                new BURegReductionPriorityQueue<bu_ls_rr_sort>());
 806 }
 807
 808 llvm::ScheduleDAG* llvm::createTDRRListDAGScheduler(SelectionDAG &DAG,
 809                                                     MachineBasicBlock *BB) {
 810   return new ScheduleDAGRRList(DAG, BB, DAG.getTarget(), false,
 811                                new TDRegReductionPriorityQueue<td_ls_rr_sort>());
 812 }
 813