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   SmallPtrSet<SUnit*, 4> 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 static inline bool isCopyFromLiveIn(const SUnit *SU) {
 418   SDNode *N = SU->Node;
 419   return N->getOpcode() == ISD::CopyFromReg &&
 420     N->getOperand(N->getNumOperands()-1).getValueType() != MVT::Flag;
 421 }
 422
 423 namespace {
 424   template<class SF>
 425   class VISIBILITY_HIDDEN RegReductionPriorityQueue
 426    : public SchedulingPriorityQueue {
 427     std::priority_queue<SUnit*, std::vector<SUnit*>, SF> Queue;
 428
 429   public:
 430     RegReductionPriorityQueue() :
 431     Queue(SF(this)) {}
 432
 433     virtual void initNodes(DenseMap<SDNode*, SUnit*> &sumap,
 434                            std::vector<SUnit> &sunits) {}
 435     virtual void releaseState() {}
 436
 437     virtual unsigned getNodePriority(const SUnit *SU) const {
 438       return 0;
 439     }
 440
 441     bool empty() const { return Queue.empty(); }
 442
 443     void push(SUnit *U) {
 444       Queue.push(U);
 445     }
 446     void push_all(const std::vector<SUnit *> &Nodes) {
 447       for (unsigned i = 0, e = Nodes.size(); i != e; ++i)
 448         Queue.push(Nodes[i]);
 449     }
 450
 451     SUnit *pop() {
 452       if (empty()) return NULL;
 453       SUnit *V = Queue.top();
 454       Queue.pop();
 455       return V;
 456     }
 457
 458     virtual bool isDUOperand(const SUnit *SU1, const SUnit *SU2) {
 459       return false;
 460     }
 461   };
 462
 463   template<class SF>
 464   class VISIBILITY_HIDDEN BURegReductionPriorityQueue
 465    : public RegReductionPriorityQueue<SF> {
 466     // SUnitMap SDNode to SUnit mapping (n -> 1).
 467     DenseMap<SDNode*, SUnit*> *SUnitMap;
 468
 469     // SUnits - The SUnits for the current graph.
 470     const std::vector<SUnit> *SUnits;
 471
 472     // SethiUllmanNumbers - The SethiUllman number for each node.
 473     std::vector<unsigned> SethiUllmanNumbers;
 474
 475     const TargetInstrInfo *TII;
 476   public:
 477     BURegReductionPriorityQueue(const TargetInstrInfo *tii)
 478       : TII(tii) {}
 479
 480     void initNodes(DenseMap<SDNode*, SUnit*> &sumap,
 481                    std::vector<SUnit> &sunits) {
 482       SUnitMap = &sumap;
 483       SUnits = &sunits;
 484       // Add pseudo dependency edges for two-address nodes.
 485       AddPseudoTwoAddrDeps();
 486       // Calculate node priorities.
 487       CalculateSethiUllmanNumbers();
 488     }
 489
 490     void releaseState() {
 491       SUnits = 0;
 492       SethiUllmanNumbers.clear();
 493     }
 494
 495     unsigned getNodePriority(const SUnit *SU) const {
 496       assert(SU->NodeNum < SethiUllmanNumbers.size());
 497       unsigned Opc = SU->Node->getOpcode();
 498       if (Opc == ISD::CopyFromReg && !isCopyFromLiveIn(SU))
 499         // CopyFromReg should be close to its def because it restricts
 500         // allocation choices. But if it is a livein then perhaps we want it
 501         // closer to its uses so it can be coalesced.
 502         return 0xffff;
 503       else if (Opc == ISD::TokenFactor || Opc == ISD::CopyToReg)
 504         // CopyToReg should be close to its uses to facilitate coalescing and
 505         // avoid spilling.
 506         return 0;
 507       else if (SU->NumSuccs == 0)
 508         // If SU does not have a use, i.e. it doesn't produce a value that would
 509         // be consumed (e.g. store), then it terminates a chain of computation.
 510         // Give it a large SethiUllman number so it will be scheduled right
 511         // before its predecessors that it doesn't lengthen their live ranges.
 512         return 0xffff;
 513       else if (SU->NumPreds == 0)
 514         // If SU does not have a def, schedule it close to its uses because it
 515         // does not lengthen any live ranges.
 516         return 0;
 517       else
 518         return SethiUllmanNumbers[SU->NodeNum];
 519     }
 520
 521     bool isDUOperand(const SUnit *SU1, const SUnit *SU2) {
 522       unsigned Opc = SU1->Node->getTargetOpcode();
 523       unsigned NumRes = ScheduleDAG::CountResults(SU1->Node);
 524       unsigned NumOps = ScheduleDAG::CountOperands(SU1->Node);
 525       for (unsigned i = 0; i != NumOps; ++i) {
 526         if (TII->getOperandConstraint(Opc, i+NumRes, TOI::TIED_TO) == -1)
 527           continue;
 528         if (SU1->Node->getOperand(i).isOperand(SU2->Node))
 529           return true;
 530       }
 531       return false;
 532     }
 533   private:
 534     bool canClobber(SUnit *SU, SUnit *Op);
 535     void AddPseudoTwoAddrDeps();
 536     void CalculateSethiUllmanNumbers();
 537     unsigned CalcNodeSethiUllmanNumber(const SUnit *SU);
 538   };
 539
 540
 541   template<class SF>
 542   class TDRegReductionPriorityQueue : public RegReductionPriorityQueue<SF> {
 543     // SUnitMap SDNode to SUnit mapping (n -> 1).
 544     DenseMap<SDNode*, SUnit*> *SUnitMap;
 545
 546     // SUnits - The SUnits for the current graph.
 547     const std::vector<SUnit> *SUnits;
 548
 549     // SethiUllmanNumbers - The SethiUllman number for each node.
 550     std::vector<unsigned> SethiUllmanNumbers;
 551
 552   public:
 553     TDRegReductionPriorityQueue() {}
 554
 555     void initNodes(DenseMap<SDNode*, SUnit*> &sumap,
 556                    std::vector<SUnit> &sunits) {
 557       SUnitMap = &sumap;
 558       SUnits = &sunits;
 559       // Calculate node priorities.
 560       CalculateSethiUllmanNumbers();
 561     }
 562
 563     void releaseState() {
 564       SUnits = 0;
 565       SethiUllmanNumbers.clear();
 566     }
 567
 568     unsigned getNodePriority(const SUnit *SU) const {
 569       assert(SU->NodeNum < SethiUllmanNumbers.size());
 570       return SethiUllmanNumbers[SU->NodeNum];
 571     }
 572
 573   private:
 574     void CalculateSethiUllmanNumbers();
 575     unsigned CalcNodeSethiUllmanNumber(const SUnit *SU);
 576   };
 577 }
 578
 579 /// closestSucc - Returns the scheduled cycle of the successor which is
 580 /// closet to the current cycle.
 581 static unsigned closestSucc(const SUnit *SU) {
 582   unsigned MaxCycle = 0;
 583   for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
 584        I != E; ++I) {
 585     unsigned Cycle = I->first->Cycle;
 586     // If there are bunch of CopyToRegs stacked up, they should be considered
 587     // to be at the same position.
 588     if (I->first->Node->getOpcode() == ISD::CopyToReg)
 589       Cycle = closestSucc(I->first)+1;
 590     if (Cycle > MaxCycle)
 591       MaxCycle = Cycle;
 592   }
 593   return MaxCycle;
 594 }
 595
 596 /// calcMaxScratches - Returns an cost estimate of the worse case requirement
 597 /// for scratch registers. Live-in operands and live-out results don't count
 598 /// since they are "fixed".
 599 static unsigned calcMaxScratches(const SUnit *SU) {
 600   unsigned Scratches = 0;
 601   for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
 602        I != E; ++I) {
 603     if (I->second) continue;  // ignore chain preds
 604     if (I->first->Node->getOpcode() != ISD::CopyFromReg)
 605       Scratches++;
 606   }
 607   for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
 608        I != E; ++I) {
 609     if (I->second) continue;  // ignore chain succs
 610     if (I->first->Node->getOpcode() != ISD::CopyToReg)
 611       Scratches += 10;
 612   }
 613   return Scratches;
 614 }
 615
 616 // Bottom up
 617 bool bu_ls_rr_sort::operator()(const SUnit *left, const SUnit *right) const {
 618   bool LIsTarget = left->Node->isTargetOpcode();
 619   bool RIsTarget = right->Node->isTargetOpcode();
 620
 621   // There used to be a special tie breaker here that looked for
 622   // two-address instructions and preferred the instruction with a
 623   // def&use operand.  The special case triggered diagnostics when
 624   // _GLIBCXX_DEBUG was enabled because it broke the strict weak
 625   // ordering that priority_queue requires. It didn't help much anyway
 626   // because AddPseudoTwoAddrDeps already covers many of the cases
 627   // where it would have applied.  In addition, it's counter-intuitive
 628   // that a tie breaker would be the first thing attempted.  There's a
 629   // "real" tie breaker below that is the operation of last resort.
 630   // The fact that the "special tie breaker" would trigger when there
 631   // wasn't otherwise a tie is what broke the strict weak ordering
 632   // constraint.
 633
 634   unsigned LPriority = SPQ->getNodePriority(left);
 635   unsigned RPriority = SPQ->getNodePriority(right);
 636   if (LPriority > RPriority)
 637     return true;
 638   else if (LPriority == RPriority) {
 639     // Try schedule def + use closer when Sethi-Ullman numbers are the same.
 640     // e.g.
 641     // t1 = op t2, c1
 642     // t3 = op t4, c2
 643     //
 644     // and the following instructions are both ready.
 645     // t2 = op c3
 646     // t4 = op c4
 647     //
 648     // Then schedule t2 = op first.
 649     // i.e.
 650     // t4 = op c4
 651     // t2 = op c3
 652     // t1 = op t2, c1
 653     // t3 = op t4, c2
 654     //
 655     // This creates more short live intervals.
 656     unsigned LDist = closestSucc(left);
 657     unsigned RDist = closestSucc(right);
 658     if (LDist < RDist)
 659       return true;
 660     else if (LDist == RDist) {
 661       // Intuitively, it's good to push down instructions whose results are
 662       // liveout so their long live ranges won't conflict with other values
 663       // which are needed inside the BB. Further prioritize liveout instructions
 664       // by the number of operands which are calculated within the BB.
 665       unsigned LScratch = calcMaxScratches(left);
 666       unsigned RScratch = calcMaxScratches(right);
 667       if (LScratch > RScratch)
 668         return true;
 669       else if (LScratch == RScratch)
 670         if (left->Height > right->Height)
 671           return true;
 672         else if (left->Height == right->Height)
 673           if (left->Depth < right->Depth)
 674             return true;
 675           else if (left->Depth == right->Depth)
 676             if (left->CycleBound > right->CycleBound)
 677               return true;
 678     }
 679   }
 680   return false;
 681 }
 682
 683 // FIXME: This is probably too slow!
 684 static void isReachable(SUnit *SU, SUnit *TargetSU,
 685                         SmallPtrSet<SUnit*, 32> &Visited, bool &Reached) {
 686   if (Reached) return;
 687   if (SU == TargetSU) {
 688     Reached = true;
 689     return;
 690   }
 691   if (!Visited.insert(SU)) return;
 692
 693   for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); I != E;
 694        ++I)
 695     isReachable(I->first, TargetSU, Visited, Reached);
 696 }
 697
 698 static bool isReachable(SUnit *SU, SUnit *TargetSU) {
 699   SmallPtrSet<SUnit*, 32> Visited;
 700   bool Reached = false;
 701   isReachable(SU, TargetSU, Visited, Reached);
 702   return Reached;
 703 }
 704
 705 template<class SF>
 706 bool BURegReductionPriorityQueue<SF>::canClobber(SUnit *SU, SUnit *Op) {
 707   if (SU->isTwoAddress) {
 708     unsigned Opc = SU->Node->getTargetOpcode();
 709     unsigned NumRes = ScheduleDAG::CountResults(SU->Node);
 710     unsigned NumOps = ScheduleDAG::CountOperands(SU->Node);
 711     for (unsigned i = 0; i != NumOps; ++i) {
 712       if (TII->getOperandConstraint(Opc, i+NumRes, TOI::TIED_TO) != -1) {
 713         SDNode *DU = SU->Node->getOperand(i).Val;
 714         if (Op == (*SUnitMap)[DU])
 715           return true;
 716       }
 717     }
 718   }
 719   return false;
 720 }
 721
 722
 723 /// AddPseudoTwoAddrDeps - If two nodes share an operand and one of them uses
 724 /// it as a def&use operand. Add a pseudo control edge from it to the other
 725 /// node (if it won't create a cycle) so the two-address one will be scheduled
 726 /// first (lower in the schedule).
 727 template<class SF>
 728 void BURegReductionPriorityQueue<SF>::AddPseudoTwoAddrDeps() {
 729   for (unsigned i = 0, e = SUnits->size(); i != e; ++i) {
 730     SUnit *SU = (SUnit *)&((*SUnits)[i]);
 731     if (!SU->isTwoAddress)
 732       continue;
 733
 734     SDNode *Node = SU->Node;
 735     if (!Node->isTargetOpcode())
 736       continue;
 737
 738     unsigned Opc = Node->getTargetOpcode();
 739     unsigned NumRes = ScheduleDAG::CountResults(Node);
 740     unsigned NumOps = ScheduleDAG::CountOperands(Node);
 741     for (unsigned j = 0; j != NumOps; ++j) {
 742       if (TII->getOperandConstraint(Opc, j+NumRes, TOI::TIED_TO) != -1) {
 743         SDNode *DU = SU->Node->getOperand(j).Val;
 744         SUnit *DUSU = (*SUnitMap)[DU];
 745         if (!DUSU) continue;
 746         for (SUnit::succ_iterator I = DUSU->Succs.begin(),E = DUSU->Succs.end();
 747              I != E; ++I) {
 748           if (I->second) continue;
 749           SUnit *SuccSU = I->first;
 750           if (SuccSU != SU &&
 751               (!canClobber(SuccSU, DUSU) ||
 752                (!SU->isCommutable && SuccSU->isCommutable))){
 753             if (SuccSU->Depth == SU->Depth && !isReachable(SuccSU, SU)) {
 754               DOUT << "Adding an edge from SU # " << SU->NodeNum
 755                    << " to SU #" << SuccSU->NodeNum << "\n";
 756               if (SU->addPred(SuccSU, true))
 757                 SU->NumChainPredsLeft++;
 758               if (SuccSU->addSucc(SU, true))
 759                 SuccSU->NumChainSuccsLeft++;
 760             }
 761           }
 762         }
 763       }
 764     }
 765   }
 766 }
 767
 768 /// CalcNodeSethiUllmanNumber - Priority is the Sethi Ullman number.
 769 /// Smaller number is the higher priority.
 770 template<class SF>
 771 unsigned BURegReductionPriorityQueue<SF>::
 772 CalcNodeSethiUllmanNumber(const SUnit *SU) {
 773   unsigned &SethiUllmanNumber = SethiUllmanNumbers[SU->NodeNum];
 774   if (SethiUllmanNumber != 0)
 775     return SethiUllmanNumber;
 776
 777   unsigned Extra = 0;
 778   for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
 779        I != E; ++I) {
 780     if (I->second) continue;  // ignore chain preds
 781     SUnit *PredSU = I->first;
 782     unsigned PredSethiUllman = CalcNodeSethiUllmanNumber(PredSU);
 783     if (PredSethiUllman > SethiUllmanNumber) {
 784       SethiUllmanNumber = PredSethiUllman;
 785       Extra = 0;
 786     } else if (PredSethiUllman == SethiUllmanNumber && !I->second)
 787       Extra++;
 788   }
 789
 790   SethiUllmanNumber += Extra;
 791
 792   if (SethiUllmanNumber == 0)
 793     SethiUllmanNumber = 1;
 794
 795   return SethiUllmanNumber;
 796 }
 797
 798 /// CalculateSethiUllmanNumbers - Calculate Sethi-Ullman numbers of all
 799 /// scheduling units.
 800 template<class SF>
 801 void BURegReductionPriorityQueue<SF>::CalculateSethiUllmanNumbers() {
 802   SethiUllmanNumbers.assign(SUnits->size(), 0);
 803
 804   for (unsigned i = 0, e = SUnits->size(); i != e; ++i)
 805     CalcNodeSethiUllmanNumber(&(*SUnits)[i]);
 806 }
 807
 808 static unsigned SumOfUnscheduledPredsOfSuccs(const SUnit *SU) {
 809   unsigned Sum = 0;
 810   for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
 811        I != E; ++I) {
 812     SUnit *SuccSU = I->first;
 813     for (SUnit::const_pred_iterator II = SuccSU->Preds.begin(),
 814          EE = SuccSU->Preds.end(); II != EE; ++II) {
 815       SUnit *PredSU = II->first;
 816       if (!PredSU->isScheduled)
 817         Sum++;
 818     }
 819   }
 820
 821   return Sum;
 822 }
 823
 824
 825 // Top down
 826 bool td_ls_rr_sort::operator()(const SUnit *left, const SUnit *right) const {
 827   unsigned LPriority = SPQ->getNodePriority(left);
 828   unsigned RPriority = SPQ->getNodePriority(right);
 829   bool LIsTarget = left->Node->isTargetOpcode();
 830   bool RIsTarget = right->Node->isTargetOpcode();
 831   bool LIsFloater = LIsTarget && left->NumPreds == 0;
 832   bool RIsFloater = RIsTarget && right->NumPreds == 0;
 833   unsigned LBonus = (SumOfUnscheduledPredsOfSuccs(left) == 1) ? 2 : 0;
 834   unsigned RBonus = (SumOfUnscheduledPredsOfSuccs(right) == 1) ? 2 : 0;
 835
 836   if (left->NumSuccs == 0 && right->NumSuccs != 0)
 837     return false;
 838   else if (left->NumSuccs != 0 && right->NumSuccs == 0)
 839     return true;
 840
 841   // Special tie breaker: if two nodes share a operand, the one that use it
 842   // as a def&use operand is preferred.
 843   if (LIsTarget && RIsTarget) {
 844     if (left->isTwoAddress && !right->isTwoAddress) {
 845       SDNode *DUNode = left->Node->getOperand(0).Val;
 846       if (DUNode->isOperand(right->Node))
 847         RBonus += 2;
 848     }
 849     if (!left->isTwoAddress && right->isTwoAddress) {
 850       SDNode *DUNode = right->Node->getOperand(0).Val;
 851       if (DUNode->isOperand(left->Node))
 852         LBonus += 2;
 853     }
 854   }
 855   if (LIsFloater)
 856     LBonus -= 2;
 857   if (RIsFloater)
 858     RBonus -= 2;
 859   if (left->NumSuccs == 1)
 860     LBonus += 2;
 861   if (right->NumSuccs == 1)
 862     RBonus += 2;
 863
 864   if (LPriority+LBonus < RPriority+RBonus)
 865     return true;
 866   else if (LPriority == RPriority)
 867     if (left->Depth < right->Depth)
 868       return true;
 869     else if (left->Depth == right->Depth)
 870       if (left->NumSuccsLeft > right->NumSuccsLeft)
 871         return true;
 872       else if (left->NumSuccsLeft == right->NumSuccsLeft)
 873         if (left->CycleBound > right->CycleBound)
 874           return true;
 875   return false;
 876 }
 877
 878 /// CalcNodeSethiUllmanNumber - Priority is the Sethi Ullman number.
 879 /// Smaller number is the higher priority.
 880 template<class SF>
 881 unsigned TDRegReductionPriorityQueue<SF>::
 882 CalcNodeSethiUllmanNumber(const SUnit *SU) {
 883   unsigned &SethiUllmanNumber = SethiUllmanNumbers[SU->NodeNum];
 884   if (SethiUllmanNumber != 0)
 885     return SethiUllmanNumber;
 886
 887   unsigned Opc = SU->Node->getOpcode();
 888   if (Opc == ISD::TokenFactor || Opc == ISD::CopyToReg)
 889     SethiUllmanNumber = 0xffff;
 890   else if (SU->NumSuccsLeft == 0)
 891     // If SU does not have a use, i.e. it doesn't produce a value that would
 892     // be consumed (e.g. store), then it terminates a chain of computation.
 893     // Give it a small SethiUllman number so it will be scheduled right before
 894     // its predecessors that it doesn't lengthen their live ranges.
 895     SethiUllmanNumber = 0;
 896   else if (SU->NumPredsLeft == 0 &&
 897            (Opc != ISD::CopyFromReg || isCopyFromLiveIn(SU)))
 898     SethiUllmanNumber = 0xffff;
 899   else {
 900     int Extra = 0;
 901     for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
 902          I != E; ++I) {
 903       if (I->second) continue;  // ignore chain preds
 904       SUnit *PredSU = I->first;
 905       unsigned PredSethiUllman = CalcNodeSethiUllmanNumber(PredSU);
 906       if (PredSethiUllman > SethiUllmanNumber) {
 907         SethiUllmanNumber = PredSethiUllman;
 908         Extra = 0;
 909       } else if (PredSethiUllman == SethiUllmanNumber && !I->second)
 910         Extra++;
 911     }
 912
 913     SethiUllmanNumber += Extra;
 914   }
 915
 916   return SethiUllmanNumber;
 917 }
 918
 919 /// CalculateSethiUllmanNumbers - Calculate Sethi-Ullman numbers of all
 920 /// scheduling units.
 921 template<class SF>
 922 void TDRegReductionPriorityQueue<SF>::CalculateSethiUllmanNumbers() {
 923   SethiUllmanNumbers.assign(SUnits->size(), 0);
 924
 925   for (unsigned i = 0, e = SUnits->size(); i != e; ++i)
 926     CalcNodeSethiUllmanNumber(&(*SUnits)[i]);
 927 }
 928
 929 //===----------------------------------------------------------------------===//
 930 //                         Public Constructor Functions
 931 //===----------------------------------------------------------------------===//
 932
 933 llvm::ScheduleDAG* llvm::createBURRListDAGScheduler(SelectionDAGISel *IS,
 934                                                     SelectionDAG *DAG,
 935                                                     MachineBasicBlock *BB) {
 936   const TargetInstrInfo *TII = DAG->getTarget().getInstrInfo();
 937   return new ScheduleDAGRRList(*DAG, BB, DAG->getTarget(), true,
 938                            new BURegReductionPriorityQueue<bu_ls_rr_sort>(TII));
 939 }
 940
 941 llvm::ScheduleDAG* llvm::createTDRRListDAGScheduler(SelectionDAGISel *IS,
 942                                                     SelectionDAG *DAG,
 943                                                     MachineBasicBlock *BB) {
 944   return new ScheduleDAGRRList(*DAG, BB, DAG->getTarget(), false,
 945                               new TDRegReductionPriorityQueue<td_ls_rr_sort>());
 946 }
 947