lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp

   1 //===----- ScheduleDAGList.cpp - Reg pressure reduction list scheduler ----===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by Evan Cheng and is distributed under the
   6 // University of Illinois Open Source License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This implements bottom-up and top-down register pressure reduction list
  11 // schedulers, using standard algorithms.  The basic approach uses a priority
  12 // queue of available nodes to schedule.  One at a time, nodes are taken from
  13 // the priority queue (thus in priority order), checked for legality to
  14 // schedule, and emitted if legal.
  15 //
  16 //===----------------------------------------------------------------------===//
  17
  18 #define DEBUG_TYPE "sched"
  19 #include "llvm/CodeGen/ScheduleDAG.h"
  20 #include "llvm/CodeGen/SchedulerRegistry.h"
  21 #include "llvm/CodeGen/SSARegMap.h"
  22 #include "llvm/Target/MRegisterInfo.h"
  23 #include "llvm/Target/TargetData.h"
  24 #include "llvm/Target/TargetMachine.h"
  25 #include "llvm/Target/TargetInstrInfo.h"
  26 #include "llvm/Support/Debug.h"
  27 #include "llvm/Support/Compiler.h"
  28 #include "llvm/ADT/Statistic.h"
  29 #include <climits>
  30 #include <queue>
  31 #include "llvm/Support/CommandLine.h"
  32 using namespace llvm;
  33
  34 static RegisterScheduler
  35   burrListDAGScheduler("list-burr",
  36                        "  Bottom-up register reduction list scheduling",
  37                        createBURRListDAGScheduler);
  38 static RegisterScheduler
  39   tdrListrDAGScheduler("list-tdrr",
  40                        "  Top-down register reduction list scheduling",
  41                        createTDRRListDAGScheduler);
  42
  43 namespace {
  44 //===----------------------------------------------------------------------===//
  45 /// ScheduleDAGRRList - The actual register reduction list scheduler
  46 /// implementation.  This supports both top-down and bottom-up scheduling.
  47 ///
  48
  49 class VISIBILITY_HIDDEN ScheduleDAGRRList : public ScheduleDAG {
  50 private:
  51   /// isBottomUp - This is true if the scheduling problem is bottom-up, false if
  52   /// it is top-down.
  53   bool isBottomUp;
  54
  55   /// AvailableQueue - The priority queue to use for the available SUnits.
  56   ///
  57   SchedulingPriorityQueue *AvailableQueue;
  58
  59 public:
  60   ScheduleDAGRRList(SelectionDAG &dag, MachineBasicBlock *bb,
  61                   const TargetMachine &tm, bool isbottomup,
  62                   SchedulingPriorityQueue *availqueue)
  63     : ScheduleDAG(dag, bb, tm), isBottomUp(isbottomup),
  64       AvailableQueue(availqueue) {
  65     }
  66
  67   ~ScheduleDAGRRList() {
  68     delete AvailableQueue;
  69   }
  70
  71   void Schedule();
  72
  73 private:
  74   void ReleasePred(SUnit *PredSU, bool isChain, unsigned CurCycle);
  75   void ReleaseSucc(SUnit *SuccSU, bool isChain, unsigned CurCycle);
  76   void ScheduleNodeBottomUp(SUnit *SU, unsigned CurCycle);
  77   void ScheduleNodeTopDown(SUnit *SU, unsigned CurCycle);
  78   void ListScheduleTopDown();
  79   void ListScheduleBottomUp();
  80   void CommuteNodesToReducePressure();
  81 };
  82 }  // end anonymous namespace
  83
  84
  85 /// Schedule - Schedule the DAG using list scheduling.
  86 void ScheduleDAGRRList::Schedule() {
  87   DOUT << "********** List Scheduling **********\n";
  88
  89   // Build scheduling units.
  90   BuildSchedUnits();
  91
  92   DEBUG(for (unsigned su = 0, e = SUnits.size(); su != e; ++su)
  93           SUnits[su].dumpAll(&DAG));
  94   CalculateDepths();
  95   CalculateHeights();
  96
  97   AvailableQueue->initNodes(SUnitMap, SUnits);
  98
  99   // Execute the actual scheduling loop Top-Down or Bottom-Up as appropriate.
 100   if (isBottomUp)
 101     ListScheduleBottomUp();
 102   else
 103     ListScheduleTopDown();
 104
 105   AvailableQueue->releaseState();
 106
 107   CommuteNodesToReducePressure();
 108
 109   DOUT << "*** Final schedule ***\n";
 110   DEBUG(dumpSchedule());
 111   DOUT << "\n";
 112
 113   // Emit in scheduled order
 114   EmitSchedule();
 115 }
 116
 117 /// CommuteNodesToReducePressure - If a node is two-address and commutable, and
 118 /// it is not the last use of its first operand, add it to the CommuteSet if
 119 /// possible. It will be commuted when it is translated to a MI.
 120 void ScheduleDAGRRList::CommuteNodesToReducePressure() {
 121   std::set<SUnit *> OperandSeen;
 122   for (unsigned i = Sequence.size()-1; i != 0; --i) {  // Ignore first node.
 123     SUnit *SU = Sequence[i];
 124     if (!SU) continue;
 125     if (SU->isCommutable) {
 126       unsigned Opc = SU->Node->getTargetOpcode();
 127       unsigned NumRes = CountResults(SU->Node);
 128       unsigned NumOps = CountOperands(SU->Node);
 129       for (unsigned j = 0; j != NumOps; ++j) {
 130         if (TII->getOperandConstraint(Opc, j+NumRes, TOI::TIED_TO) == -1)
 131           continue;
 132
 133         SDNode *OpN = SU->Node->getOperand(j).Val;
 134         SUnit *OpSU = SUnitMap[OpN];
 135         if (OpSU && OperandSeen.count(OpSU) == 1) {
 136           // Ok, so SU is not the last use of OpSU, but SU is two-address so
 137           // it will clobber OpSU. Try to commute SU if no other source operands
 138           // are live below.
 139           bool DoCommute = true;
 140           for (unsigned k = 0; k < NumOps; ++k) {
 141             if (k != j) {
 142               OpN = SU->Node->getOperand(k).Val;
 143               OpSU = SUnitMap[OpN];
 144               if (OpSU && OperandSeen.count(OpSU) == 1) {
 145                 DoCommute = false;
 146                 break;
 147               }
 148             }
 149           }
 150           if (DoCommute)
 151             CommuteSet.insert(SU->Node);
 152         }
 153
 154         // Only look at the first use&def node for now.
 155         break;
 156       }
 157     }
 158
 159     for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
 160          I != E; ++I) {
 161       if (!I->second)
 162         OperandSeen.insert(I->first);
 163     }
 164   }
 165 }
 166
 167 //===----------------------------------------------------------------------===//
 168 //  Bottom-Up Scheduling
 169 //===----------------------------------------------------------------------===//
 170
 171 /// ReleasePred - Decrement the NumSuccsLeft count of a predecessor. Add it to
 172 /// the Available queue is the count reaches zero. Also update its cycle bound.
 173 void ScheduleDAGRRList::ReleasePred(SUnit *PredSU, bool isChain,
 174                                     unsigned CurCycle) {
 175   // FIXME: the distance between two nodes is not always == the predecessor's
 176   // latency. For example, the reader can very well read the register written
 177   // by the predecessor later than the issue cycle. It also depends on the
 178   // interrupt model (drain vs. freeze).
 179   PredSU->CycleBound = std::max(PredSU->CycleBound, CurCycle + PredSU->Latency);
 180
 181   if (!isChain)
 182     PredSU->NumSuccsLeft--;
 183   else
 184     PredSU->NumChainSuccsLeft--;
 185
 186 #ifndef NDEBUG
 187   if (PredSU->NumSuccsLeft < 0 || PredSU->NumChainSuccsLeft < 0) {
 188     cerr << "*** List scheduling failed! ***\n";
 189     PredSU->dump(&DAG);
 190     cerr << " has been released too many times!\n";
 191     assert(0);
 192   }
 193 #endif
 194
 195   if ((PredSU->NumSuccsLeft + PredSU->NumChainSuccsLeft) == 0) {
 196     // EntryToken has to go last!  Special case it here.
 197     if (PredSU->Node->getOpcode() != ISD::EntryToken) {
 198       PredSU->isAvailable = true;
 199       AvailableQueue->push(PredSU);
 200     }
 201   }
 202 }
 203
 204 /// ScheduleNodeBottomUp - Add the node to the schedule. Decrement the pending
 205 /// count of its predecessors. If a predecessor pending count is zero, add it to
 206 /// the Available queue.
 207 void ScheduleDAGRRList::ScheduleNodeBottomUp(SUnit *SU, unsigned CurCycle) {
 208   DOUT << "*** Scheduling [" << CurCycle << "]: ";
 209   DEBUG(SU->dump(&DAG));
 210   SU->Cycle = CurCycle;
 211
 212   AvailableQueue->ScheduledNode(SU);
 213   Sequence.push_back(SU);
 214
 215   // Bottom up: release predecessors
 216   for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
 217        I != E; ++I)
 218     ReleasePred(I->first, I->second, CurCycle);
 219   SU->isScheduled = true;
 220 }
 221
 222 /// isReady - True if node's lower cycle bound is less or equal to the current
 223 /// scheduling cycle. Always true if all nodes have uniform latency 1.
 224 static inline bool isReady(SUnit *SU, unsigned CurCycle) {
 225   return SU->CycleBound <= CurCycle;
 226 }
 227
 228 /// ListScheduleBottomUp - The main loop of list scheduling for bottom-up
 229 /// schedulers.
 230 void ScheduleDAGRRList::ListScheduleBottomUp() {
 231   unsigned CurCycle = 0;
 232   // Add root to Available queue.
 233   AvailableQueue->push(SUnitMap[DAG.getRoot().Val]);
 234
 235   // While Available queue is not empty, grab the node with the highest
 236   // priority. If it is not ready put it back. Schedule the node.
 237   std::vector<SUnit*> NotReady;
 238   while (!AvailableQueue->empty()) {
 239     SUnit *CurNode = AvailableQueue->pop();
 240     while (CurNode && !isReady(CurNode, CurCycle)) {
 241       NotReady.push_back(CurNode);
 242       CurNode = AvailableQueue->pop();
 243     }
 244
 245     // Add the nodes that aren't ready back onto the available list.
 246     AvailableQueue->push_all(NotReady);
 247     NotReady.clear();
 248
 249     if (CurNode != NULL)
 250       ScheduleNodeBottomUp(CurNode, CurCycle);
 251     CurCycle++;
 252   }
 253
 254   // Add entry node last
 255   if (DAG.getEntryNode().Val != DAG.getRoot().Val) {
 256     SUnit *Entry = SUnitMap[DAG.getEntryNode().Val];
 257     Sequence.push_back(Entry);
 258   }
 259
 260   // Reverse the order if it is bottom up.
 261   std::reverse(Sequence.begin(), Sequence.end());
 262
 263
 264 #ifndef NDEBUG
 265   // Verify that all SUnits were scheduled.
 266   bool AnyNotSched = false;
 267   for (unsigned i = 0, e = SUnits.size(); i != e; ++i) {
 268     if (SUnits[i].NumSuccsLeft != 0 || SUnits[i].NumChainSuccsLeft != 0) {
 269       if (!AnyNotSched)
 270         cerr << "*** List scheduling failed! ***\n";
 271       SUnits[i].dump(&DAG);
 272       cerr << "has not been scheduled!\n";
 273       AnyNotSched = true;
 274     }
 275   }
 276   assert(!AnyNotSched);
 277 #endif
 278 }
 279
 280 //===----------------------------------------------------------------------===//
 281 //  Top-Down Scheduling
 282 //===----------------------------------------------------------------------===//
 283
 284 /// ReleaseSucc - Decrement the NumPredsLeft count of a successor. Add it to
 285 /// the PendingQueue if the count reaches zero.
 286 void ScheduleDAGRRList::ReleaseSucc(SUnit *SuccSU, bool isChain,
 287                                     unsigned CurCycle) {
 288   // FIXME: the distance between two nodes is not always == the predecessor's
 289   // latency. For example, the reader can very well read the register written
 290   // by the predecessor later than the issue cycle. It also depends on the
 291   // interrupt model (drain vs. freeze).
 292   SuccSU->CycleBound = std::max(SuccSU->CycleBound, CurCycle + SuccSU->Latency);
 293
 294   if (!isChain)
 295     SuccSU->NumPredsLeft--;
 296   else
 297     SuccSU->NumChainPredsLeft--;
 298
 299 #ifndef NDEBUG
 300   if (SuccSU->NumPredsLeft < 0 || SuccSU->NumChainPredsLeft < 0) {
 301     cerr << "*** List scheduling failed! ***\n";
 302     SuccSU->dump(&DAG);
 303     cerr << " has been released too many times!\n";
 304     assert(0);
 305   }
 306 #endif
 307
 308   if ((SuccSU->NumPredsLeft + SuccSU->NumChainPredsLeft) == 0) {
 309     SuccSU->isAvailable = true;
 310     AvailableQueue->push(SuccSU);
 311   }
 312 }
 313
 314
 315 /// ScheduleNodeTopDown - Add the node to the schedule. Decrement the pending
 316 /// count of its successors. If a successor pending count is zero, add it to
 317 /// the Available queue.
 318 void ScheduleDAGRRList::ScheduleNodeTopDown(SUnit *SU, unsigned CurCycle) {
 319   DOUT << "*** Scheduling [" << CurCycle << "]: ";
 320   DEBUG(SU->dump(&DAG));
 321   SU->Cycle = CurCycle;
 322
 323   AvailableQueue->ScheduledNode(SU);
 324   Sequence.push_back(SU);
 325
 326   // Top down: release successors
 327   for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
 328        I != E; ++I)
 329     ReleaseSucc(I->first, I->second, CurCycle);
 330   SU->isScheduled = true;
 331 }
 332
 333 void ScheduleDAGRRList::ListScheduleTopDown() {
 334   unsigned CurCycle = 0;
 335   SUnit *Entry = SUnitMap[DAG.getEntryNode().Val];
 336
 337   // All leaves to Available queue.
 338   for (unsigned i = 0, e = SUnits.size(); i != e; ++i) {
 339     // It is available if it has no predecessors.
 340     if (SUnits[i].Preds.size() == 0 && &SUnits[i] != Entry) {
 341       AvailableQueue->push(&SUnits[i]);
 342       SUnits[i].isAvailable = true;
 343     }
 344   }
 345
 346   // Emit the entry node first.
 347   ScheduleNodeTopDown(Entry, CurCycle);
 348   CurCycle++;
 349
 350   // While Available queue is not empty, grab the node with the highest
 351   // priority. If it is not ready put it back. Schedule the node.
 352   std::vector<SUnit*> NotReady;
 353   while (!AvailableQueue->empty()) {
 354     SUnit *CurNode = AvailableQueue->pop();
 355     while (CurNode && !isReady(CurNode, CurCycle)) {
 356       NotReady.push_back(CurNode);
 357       CurNode = AvailableQueue->pop();
 358     }
 359
 360     // Add the nodes that aren't ready back onto the available list.
 361     AvailableQueue->push_all(NotReady);
 362     NotReady.clear();
 363
 364     if (CurNode != NULL)
 365       ScheduleNodeTopDown(CurNode, CurCycle);
 366     CurCycle++;
 367   }
 368
 369
 370 #ifndef NDEBUG
 371   // Verify that all SUnits were scheduled.
 372   bool AnyNotSched = false;
 373   for (unsigned i = 0, e = SUnits.size(); i != e; ++i) {
 374     if (!SUnits[i].isScheduled) {
 375       if (!AnyNotSched)
 376         cerr << "*** List scheduling failed! ***\n";
 377       SUnits[i].dump(&DAG);
 378       cerr << "has not been scheduled!\n";
 379       AnyNotSched = true;
 380     }
 381   }
 382   assert(!AnyNotSched);
 383 #endif
 384 }
 385
 386
 387
 388 //===----------------------------------------------------------------------===//
 389 //                RegReductionPriorityQueue Implementation
 390 //===----------------------------------------------------------------------===//
 391 //
 392 // This is a SchedulingPriorityQueue that schedules using Sethi Ullman numbers
 393 // to reduce register pressure.
 394 //
 395 namespace {
 396   template<class SF>
 397   class RegReductionPriorityQueue;
 398
 399   /// Sorting functions for the Available queue.
 400   struct bu_ls_rr_sort : public std::binary_function<SUnit*, SUnit*, bool> {
 401     RegReductionPriorityQueue<bu_ls_rr_sort> *SPQ;
 402     bu_ls_rr_sort(RegReductionPriorityQueue<bu_ls_rr_sort> *spq) : SPQ(spq) {}
 403     bu_ls_rr_sort(const bu_ls_rr_sort &RHS) : SPQ(RHS.SPQ) {}
 404
 405     bool operator()(const SUnit* left, const SUnit* right) const;
 406   };
 407
 408   struct td_ls_rr_sort : public std::binary_function<SUnit*, SUnit*, bool> {
 409     RegReductionPriorityQueue<td_ls_rr_sort> *SPQ;
 410     td_ls_rr_sort(RegReductionPriorityQueue<td_ls_rr_sort> *spq) : SPQ(spq) {}
 411     td_ls_rr_sort(const td_ls_rr_sort &RHS) : SPQ(RHS.SPQ) {}
 412
 413     bool operator()(const SUnit* left, const SUnit* right) const;
 414   };
 415 }  // end anonymous namespace
 416
 417 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(std::map<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     std::map<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(std::map<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     std::map<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(std::map<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 // Bottom up
 580 bool bu_ls_rr_sort::operator()(const SUnit *left, const SUnit *right) const {
 581   bool LIsTarget = left->Node->isTargetOpcode();
 582   bool RIsTarget = right->Node->isTargetOpcode();
 583
 584   // Special tie breaker: if two nodes share a operand, the one that use it
 585   // as a def&use operand is preferred.
 586   if (LIsTarget && RIsTarget) {
 587     if (left->isTwoAddress && !right->isTwoAddress)
 588       if (SPQ->isDUOperand(left, right))
 589         return false;
 590     if (!left->isTwoAddress && right->isTwoAddress)
 591       if (SPQ->isDUOperand(right, left))
 592         return true;
 593   }
 594
 595   unsigned LPriority = SPQ->getNodePriority(left);
 596   unsigned RPriority = SPQ->getNodePriority(right);
 597   if (LPriority > RPriority)
 598     return true;
 599   else if (LPriority == RPriority)
 600     if (left->Height > right->Height)
 601       return true;
 602     else if (left->Height == right->Height)
 603       if (left->Depth < right->Depth)
 604         return true;
 605       else if (left->Depth == right->Depth)
 606         if (left->CycleBound > right->CycleBound)
 607           return true;
 608   return false;
 609 }
 610
 611 // FIXME: This is probably too slow!
 612 static void isReachable(SUnit *SU, SUnit *TargetSU,
 613                         std::set<SUnit *> &Visited, bool &Reached) {
 614   if (Reached) return;
 615   if (SU == TargetSU) {
 616     Reached = true;
 617     return;
 618   }
 619   if (!Visited.insert(SU).second) return;
 620
 621   for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); I != E;
 622        ++I)
 623     isReachable(I->first, TargetSU, Visited, Reached);
 624 }
 625
 626 static bool isReachable(SUnit *SU, SUnit *TargetSU) {
 627   std::set<SUnit *> Visited;
 628   bool Reached = false;
 629   isReachable(SU, TargetSU, Visited, Reached);
 630   return Reached;
 631 }
 632
 633 template<class SF>
 634 bool BURegReductionPriorityQueue<SF>::canClobber(SUnit *SU, SUnit *Op) {
 635   if (SU->isTwoAddress) {
 636     unsigned Opc = SU->Node->getTargetOpcode();
 637     unsigned NumRes = ScheduleDAG::CountResults(SU->Node);
 638     unsigned NumOps = ScheduleDAG::CountOperands(SU->Node);
 639     for (unsigned i = 0; i != NumOps; ++i) {
 640       if (TII->getOperandConstraint(Opc, i+NumRes, TOI::TIED_TO) != -1) {
 641         SDNode *DU = SU->Node->getOperand(i).Val;
 642         if (Op == (*SUnitMap)[DU])
 643           return true;
 644       }
 645     }
 646   }
 647   return false;
 648 }
 649
 650
 651 /// AddPseudoTwoAddrDeps - If two nodes share an operand and one of them uses
 652 /// it as a def&use operand. Add a pseudo control edge from it to the other
 653 /// node (if it won't create a cycle) so the two-address one will be scheduled
 654 /// first (lower in the schedule).
 655 template<class SF>
 656 void BURegReductionPriorityQueue<SF>::AddPseudoTwoAddrDeps() {
 657   for (unsigned i = 0, e = SUnits->size(); i != e; ++i) {
 658     SUnit *SU = (SUnit *)&((*SUnits)[i]);
 659     if (!SU->isTwoAddress)
 660       continue;
 661
 662     SDNode *Node = SU->Node;
 663     if (!Node->isTargetOpcode())
 664       continue;
 665
 666     unsigned Opc = Node->getTargetOpcode();
 667     unsigned NumRes = ScheduleDAG::CountResults(Node);
 668     unsigned NumOps = ScheduleDAG::CountOperands(Node);
 669     for (unsigned j = 0; j != NumOps; ++j) {
 670       if (TII->getOperandConstraint(Opc, j+NumRes, TOI::TIED_TO) != -1) {
 671         SDNode *DU = SU->Node->getOperand(j).Val;
 672         SUnit *DUSU = (*SUnitMap)[DU];
 673         if (!DUSU) continue;
 674         for (SUnit::succ_iterator I = DUSU->Succs.begin(),E = DUSU->Succs.end();
 675              I != E; ++I) {
 676           if (I->second) continue;
 677           SUnit *SuccSU = I->first;
 678           if (SuccSU != SU &&
 679               (!canClobber(SuccSU, DUSU) ||
 680                (!SU->isCommutable && SuccSU->isCommutable))){
 681             if (SuccSU->Depth == SU->Depth && !isReachable(SuccSU, SU)) {
 682               DOUT << "Adding an edge from SU # " << SU->NodeNum
 683                    << " to SU #" << SuccSU->NodeNum << "\n";
 684               if (SU->addPred(SuccSU, true))
 685                 SU->NumChainPredsLeft++;
 686               if (SuccSU->addSucc(SU, true))
 687                 SuccSU->NumChainSuccsLeft++;
 688             }
 689           }
 690         }
 691       }
 692     }
 693   }
 694 }
 695
 696 /// CalcNodeSethiUllmanNumber - Priority is the Sethi Ullman number.
 697 /// Smaller number is the higher priority.
 698 template<class SF>
 699 unsigned BURegReductionPriorityQueue<SF>::CalcNodeSethiUllmanNumber(const SUnit *SU) {
 700   unsigned &SethiUllmanNumber = SethiUllmanNumbers[SU->NodeNum];
 701   if (SethiUllmanNumber != 0)
 702     return SethiUllmanNumber;
 703
 704   unsigned Extra = 0;
 705   for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
 706        I != E; ++I) {
 707     if (I->second) continue;  // ignore chain preds
 708     SUnit *PredSU = I->first;
 709     unsigned PredSethiUllman = CalcNodeSethiUllmanNumber(PredSU);
 710     if (PredSethiUllman > SethiUllmanNumber) {
 711       SethiUllmanNumber = PredSethiUllman;
 712       Extra = 0;
 713     } else if (PredSethiUllman == SethiUllmanNumber && !I->second)
 714       Extra++;
 715   }
 716
 717   SethiUllmanNumber += Extra;
 718
 719   if (SethiUllmanNumber == 0)
 720     SethiUllmanNumber = 1;
 721
 722   return SethiUllmanNumber;
 723 }
 724
 725 /// CalculateSethiUllmanNumbers - Calculate Sethi-Ullman numbers of all
 726 /// scheduling units.
 727 template<class SF>
 728 void BURegReductionPriorityQueue<SF>::CalculateSethiUllmanNumbers() {
 729   SethiUllmanNumbers.assign(SUnits->size(), 0);
 730
 731   for (unsigned i = 0, e = SUnits->size(); i != e; ++i)
 732     CalcNodeSethiUllmanNumber(&(*SUnits)[i]);
 733 }
 734
 735 static unsigned SumOfUnscheduledPredsOfSuccs(const SUnit *SU) {
 736   unsigned Sum = 0;
 737   for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
 738        I != E; ++I) {
 739     SUnit *SuccSU = I->first;
 740     for (SUnit::const_pred_iterator II = SuccSU->Preds.begin(),
 741          EE = SuccSU->Preds.end(); II != EE; ++II) {
 742       SUnit *PredSU = II->first;
 743       if (!PredSU->isScheduled)
 744         Sum++;
 745     }
 746   }
 747
 748   return Sum;
 749 }
 750
 751
 752 // Top down
 753 bool td_ls_rr_sort::operator()(const SUnit *left, const SUnit *right) const {
 754   unsigned LPriority = SPQ->getNodePriority(left);
 755   unsigned RPriority = SPQ->getNodePriority(right);
 756   bool LIsTarget = left->Node->isTargetOpcode();
 757   bool RIsTarget = right->Node->isTargetOpcode();
 758   bool LIsFloater = LIsTarget && left->NumPreds == 0;
 759   bool RIsFloater = RIsTarget && right->NumPreds == 0;
 760   unsigned LBonus = (SumOfUnscheduledPredsOfSuccs(left) == 1) ? 2 : 0;
 761   unsigned RBonus = (SumOfUnscheduledPredsOfSuccs(right) == 1) ? 2 : 0;
 762
 763   if (left->NumSuccs == 0 && right->NumSuccs != 0)
 764     return false;
 765   else if (left->NumSuccs != 0 && right->NumSuccs == 0)
 766     return true;
 767
 768   // Special tie breaker: if two nodes share a operand, the one that use it
 769   // as a def&use operand is preferred.
 770   if (LIsTarget && RIsTarget) {
 771     if (left->isTwoAddress && !right->isTwoAddress) {
 772       SDNode *DUNode = left->Node->getOperand(0).Val;
 773       if (DUNode->isOperand(right->Node))
 774         RBonus += 2;
 775     }
 776     if (!left->isTwoAddress && right->isTwoAddress) {
 777       SDNode *DUNode = right->Node->getOperand(0).Val;
 778       if (DUNode->isOperand(left->Node))
 779         LBonus += 2;
 780     }
 781   }
 782   if (LIsFloater)
 783     LBonus -= 2;
 784   if (RIsFloater)
 785     RBonus -= 2;
 786   if (left->NumSuccs == 1)
 787     LBonus += 2;
 788   if (right->NumSuccs == 1)
 789     RBonus += 2;
 790
 791   if (LPriority+LBonus < RPriority+RBonus)
 792     return true;
 793   else if (LPriority == RPriority)
 794     if (left->Depth < right->Depth)
 795       return true;
 796     else if (left->Depth == right->Depth)
 797       if (left->NumSuccsLeft > right->NumSuccsLeft)
 798         return true;
 799       else if (left->NumSuccsLeft == right->NumSuccsLeft)
 800         if (left->CycleBound > right->CycleBound)
 801           return true;
 802   return false;
 803 }
 804
 805 /// CalcNodeSethiUllmanNumber - Priority is the Sethi Ullman number.
 806 /// Smaller number is the higher priority.
 807 template<class SF>
 808 unsigned TDRegReductionPriorityQueue<SF>::CalcNodeSethiUllmanNumber(const SUnit *SU) {
 809   unsigned &SethiUllmanNumber = SethiUllmanNumbers[SU->NodeNum];
 810   if (SethiUllmanNumber != 0)
 811     return SethiUllmanNumber;
 812
 813   unsigned Opc = SU->Node->getOpcode();
 814   if (Opc == ISD::TokenFactor || Opc == ISD::CopyToReg)
 815     SethiUllmanNumber = 0xffff;
 816   else if (SU->NumSuccsLeft == 0)
 817     // If SU does not have a use, i.e. it doesn't produce a value that would
 818     // be consumed (e.g. store), then it terminates a chain of computation.
 819     // Give it a small SethiUllman number so it will be scheduled right before its
 820     // predecessors that it doesn't lengthen their live ranges.
 821     SethiUllmanNumber = 0;
 822   else if (SU->NumPredsLeft == 0 &&
 823            (Opc != ISD::CopyFromReg || isCopyFromLiveIn(SU)))
 824     SethiUllmanNumber = 0xffff;
 825   else {
 826     int Extra = 0;
 827     for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
 828          I != E; ++I) {
 829       if (I->second) continue;  // ignore chain preds
 830       SUnit *PredSU = I->first;
 831       unsigned PredSethiUllman = CalcNodeSethiUllmanNumber(PredSU);
 832       if (PredSethiUllman > SethiUllmanNumber) {
 833         SethiUllmanNumber = PredSethiUllman;
 834         Extra = 0;
 835       } else if (PredSethiUllman == SethiUllmanNumber && !I->second)
 836         Extra++;
 837     }
 838
 839     SethiUllmanNumber += Extra;
 840   }
 841
 842   return SethiUllmanNumber;
 843 }
 844
 845 /// CalculateSethiUllmanNumbers - Calculate Sethi-Ullman numbers of all
 846 /// scheduling units.
 847 template<class SF>
 848 void TDRegReductionPriorityQueue<SF>::CalculateSethiUllmanNumbers() {
 849   SethiUllmanNumbers.assign(SUnits->size(), 0);
 850
 851   for (unsigned i = 0, e = SUnits->size(); i != e; ++i)
 852     CalcNodeSethiUllmanNumber(&(*SUnits)[i]);
 853 }
 854
 855 //===----------------------------------------------------------------------===//
 856 //                         Public Constructor Functions
 857 //===----------------------------------------------------------------------===//
 858
 859 llvm::ScheduleDAG* llvm::createBURRListDAGScheduler(SelectionDAGISel *IS,
 860                                                     SelectionDAG *DAG,
 861                                                     MachineBasicBlock *BB) {
 862   const TargetInstrInfo *TII = DAG->getTarget().getInstrInfo();
 863   return new ScheduleDAGRRList(*DAG, BB, DAG->getTarget(), true,
 864                            new BURegReductionPriorityQueue<bu_ls_rr_sort>(TII));
 865 }
 866
 867 llvm::ScheduleDAG* llvm::createTDRRListDAGScheduler(SelectionDAGISel *IS,
 868                                                     SelectionDAG *DAG,
 869                                                     MachineBasicBlock *BB) {
 870   return new ScheduleDAGRRList(*DAG, BB, DAG->getTarget(), false,
 871                                new TDRegReductionPriorityQueue<td_ls_rr_sort>());
 872 }
 873