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