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