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