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