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