LLVM API Documentation

ScheduleDAGRRList.cpp

Go to the documentation of this file.
00001 //===----- ScheduleDAGList.cpp - Reg pressure reduction list scheduler ----===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file was developed by Evan Cheng and is distributed under the
00006 // University of Illinois Open Source License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This implements bottom-up and top-down register pressure reduction list
00011 // schedulers, using standard algorithms.  The basic approach uses a priority
00012 // queue of available nodes to schedule.  One at a time, nodes are taken from
00013 // the priority queue (thus in priority order), checked for legality to
00014 // schedule, and emitted if legal.
00015 //
00016 //===----------------------------------------------------------------------===//
00017 
00018 #define DEBUG_TYPE "sched"
00019 #include "llvm/CodeGen/ScheduleDAG.h"
00020 #include "llvm/CodeGen/SSARegMap.h"
00021 #include "llvm/Target/MRegisterInfo.h"
00022 #include "llvm/Target/TargetData.h"
00023 #include "llvm/Target/TargetMachine.h"
00024 #include "llvm/Target/TargetInstrInfo.h"
00025 #include "llvm/Support/Debug.h"
00026 #include "llvm/Support/Visibility.h"
00027 #include "llvm/ADT/Statistic.h"
00028 #include <climits>
00029 #include <iostream>
00030 #include <queue>
00031 #include "llvm/Support/CommandLine.h"
00032 using namespace llvm;
00033 
00034 namespace {
00035 //===----------------------------------------------------------------------===//
00036 /// ScheduleDAGRRList - The actual register reduction list scheduler
00037 /// implementation.  This supports both top-down and bottom-up scheduling.
00038 ///
00039 
00040 class VISIBILITY_HIDDEN ScheduleDAGRRList : public ScheduleDAG {
00041 private:
00042   /// isBottomUp - This is true if the scheduling problem is bottom-up, false if
00043   /// it is top-down.
00044   bool isBottomUp;
00045   
00046   /// AvailableQueue - The priority queue to use for the available SUnits.
00047   ///
00048   SchedulingPriorityQueue *AvailableQueue;
00049 
00050 public:
00051   ScheduleDAGRRList(SelectionDAG &dag, MachineBasicBlock *bb,
00052                   const TargetMachine &tm, bool isbottomup,
00053                   SchedulingPriorityQueue *availqueue)
00054     : ScheduleDAG(dag, bb, tm), isBottomUp(isbottomup),
00055       AvailableQueue(availqueue) {
00056     }
00057 
00058   ~ScheduleDAGRRList() {
00059     delete AvailableQueue;
00060   }
00061 
00062   void Schedule();
00063 
00064 private:
00065   void ReleasePred(SUnit *PredSU, bool isChain, unsigned CurCycle);
00066   void ReleaseSucc(SUnit *SuccSU, bool isChain, unsigned CurCycle);
00067   void ScheduleNodeBottomUp(SUnit *SU, unsigned CurCycle);
00068   void ScheduleNodeTopDown(SUnit *SU, unsigned CurCycle);
00069   void ListScheduleTopDown();
00070   void ListScheduleBottomUp();
00071   void CommuteNodesToReducePressure();
00072 };
00073 }  // end anonymous namespace
00074 
00075 
00076 /// Schedule - Schedule the DAG using list scheduling.
00077 void ScheduleDAGRRList::Schedule() {
00078   DEBUG(std::cerr << "********** List Scheduling **********\n");
00079   
00080   // Build scheduling units.
00081   BuildSchedUnits();
00082 
00083   CalculateDepths();
00084   CalculateHeights();
00085   DEBUG(for (unsigned su = 0, e = SUnits.size(); su != e; ++su)
00086         SUnits[su].dumpAll(&DAG));
00087 
00088   AvailableQueue->initNodes(SUnits);
00089 
00090   // Execute the actual scheduling loop Top-Down or Bottom-Up as appropriate.
00091   if (isBottomUp)
00092     ListScheduleBottomUp();
00093   else
00094     ListScheduleTopDown();
00095   
00096   AvailableQueue->releaseState();
00097 
00098   CommuteNodesToReducePressure();
00099   
00100   DEBUG(std::cerr << "*** Final schedule ***\n");
00101   DEBUG(dumpSchedule());
00102   DEBUG(std::cerr << "\n");
00103   
00104   // Emit in scheduled order
00105   EmitSchedule();
00106 }
00107 
00108 /// CommuteNodesToReducePressure - Is a node is two-address and commutable, and
00109 /// it is not the last use of its first operand, add it to the CommuteSet if
00110 /// possible. It will be commuted when it is translated to a MI.
00111 void ScheduleDAGRRList::CommuteNodesToReducePressure() {
00112   std::set<SUnit *> OperandSeen;
00113   for (unsigned i = Sequence.size()-1; i != 0; --i) {  // Ignore first node.
00114     SUnit *SU = Sequence[i];
00115     if (!SU) continue;
00116     if (SU->isTwoAddress && SU->isCommutable) {
00117       SDNode *OpN = SU->Node->getOperand(0).Val;
00118       SUnit *OpSU = SUnitMap[OpN];
00119       if (OpSU && OperandSeen.count(OpSU) == 1) {
00120         // Ok, so SU is not the last use of OpSU, but SU is two-address so
00121         // it will clobber OpSU. Try to commute it if possible.
00122         bool DoCommute = true;
00123         for (unsigned j = 1, e = SU->Node->getNumOperands(); j != e; ++j) {
00124           OpN = SU->Node->getOperand(j).Val;
00125           OpSU = SUnitMap[OpN];
00126           if (OpSU && OperandSeen.count(OpSU) == 1) {
00127             DoCommute = false;
00128             break;
00129           }
00130         }
00131         if (DoCommute)
00132           CommuteSet.insert(SU->Node);
00133       }
00134     }
00135 
00136     for (std::set<std::pair<SUnit*, bool> >::iterator I = SU->Preds.begin(),
00137            E = SU->Preds.end(); I != E; ++I) {
00138       if (!I->second)
00139         OperandSeen.insert(I->first);
00140     }
00141   }
00142 }
00143 
00144 //===----------------------------------------------------------------------===//
00145 //  Bottom-Up Scheduling
00146 //===----------------------------------------------------------------------===//
00147 
00148 static const TargetRegisterClass *getRegClass(SUnit *SU,
00149                                               const TargetInstrInfo *TII,
00150                                               const MRegisterInfo *MRI,
00151                                               SSARegMap *RegMap) {
00152   if (SU->Node->isTargetOpcode()) {
00153     unsigned Opc = SU->Node->getTargetOpcode();
00154     const TargetInstrDescriptor &II = TII->get(Opc);
00155     return MRI->getRegClass(II.OpInfo->RegClass);
00156   } else {
00157     assert(SU->Node->getOpcode() == ISD::CopyFromReg);
00158     unsigned SrcReg = cast<RegisterSDNode>(SU->Node->getOperand(1))->getReg();
00159     if (MRegisterInfo::isVirtualRegister(SrcReg))
00160       return RegMap->getRegClass(SrcReg);
00161     else {
00162       for (MRegisterInfo::regclass_iterator I = MRI->regclass_begin(),
00163              E = MRI->regclass_end(); I != E; ++I)
00164         if ((*I)->hasType(SU->Node->getValueType(0)) &&
00165             (*I)->contains(SrcReg))
00166           return *I;
00167       assert(false && "Couldn't find register class for reg copy!");
00168     }
00169     return NULL;
00170   }
00171 }
00172 
00173 static unsigned getNumResults(SUnit *SU) {
00174   unsigned NumResults = 0;
00175   for (unsigned i = 0, e = SU->Node->getNumValues(); i != e; ++i) {
00176     MVT::ValueType VT = SU->Node->getValueType(i);
00177     if (VT != MVT::Other && VT != MVT::Flag)
00178       NumResults++;
00179   }
00180   return NumResults;
00181 }
00182 
00183 /// ReleasePred - Decrement the NumSuccsLeft count of a predecessor. Add it to
00184 /// the Available queue is the count reaches zero. Also update its cycle bound.
00185 void ScheduleDAGRRList::ReleasePred(SUnit *PredSU, bool isChain, 
00186                                     unsigned CurCycle) {
00187   // FIXME: the distance between two nodes is not always == the predecessor's
00188   // latency. For example, the reader can very well read the register written
00189   // by the predecessor later than the issue cycle. It also depends on the
00190   // interrupt model (drain vs. freeze).
00191   PredSU->CycleBound = std::max(PredSU->CycleBound, CurCycle + PredSU->Latency);
00192 
00193   if (!isChain)
00194     PredSU->NumSuccsLeft--;
00195   else
00196     PredSU->NumChainSuccsLeft--;
00197   
00198 #ifndef NDEBUG
00199   if (PredSU->NumSuccsLeft < 0 || PredSU->NumChainSuccsLeft < 0) {
00200     std::cerr << "*** List scheduling failed! ***\n";
00201     PredSU->dump(&DAG);
00202     std::cerr << " has been released too many times!\n";
00203     assert(0);
00204   }
00205 #endif
00206   
00207   if ((PredSU->NumSuccsLeft + PredSU->NumChainSuccsLeft) == 0) {
00208     // EntryToken has to go last!  Special case it here.
00209     if (PredSU->Node->getOpcode() != ISD::EntryToken) {
00210       PredSU->isAvailable = true;
00211       AvailableQueue->push(PredSU);
00212     }
00213   }
00214 }
00215 
00216 /// ScheduleNodeBottomUp - Add the node to the schedule. Decrement the pending
00217 /// count of its predecessors. If a predecessor pending count is zero, add it to
00218 /// the Available queue.
00219 void ScheduleDAGRRList::ScheduleNodeBottomUp(SUnit *SU, unsigned CurCycle) {
00220   DEBUG(std::cerr << "*** Scheduling [" << CurCycle << "]: ");
00221   DEBUG(SU->dump(&DAG));
00222   SU->Cycle = CurCycle;
00223 
00224   AvailableQueue->ScheduledNode(SU);
00225   Sequence.push_back(SU);
00226 
00227   // Bottom up: release predecessors
00228   for (std::set<std::pair<SUnit*, bool> >::iterator I = SU->Preds.begin(),
00229          E = SU->Preds.end(); I != E; ++I)
00230     ReleasePred(I->first, I->second, CurCycle);
00231   SU->isScheduled = true;
00232 }
00233 
00234 /// isReady - True if node's lower cycle bound is less or equal to the current
00235 /// scheduling cycle. Always true if all nodes have uniform latency 1.
00236 static inline bool isReady(SUnit *SU, unsigned CurCycle) {
00237   return SU->CycleBound <= CurCycle;
00238 }
00239 
00240 /// ListScheduleBottomUp - The main loop of list scheduling for bottom-up
00241 /// schedulers.
00242 void ScheduleDAGRRList::ListScheduleBottomUp() {
00243   unsigned CurCycle = 0;
00244   // Add root to Available queue.
00245   AvailableQueue->push(SUnitMap[DAG.getRoot().Val]);
00246 
00247   // While Available queue is not empty, grab the node with the highest
00248   // priority. If it is not ready put it back. Schedule the node.
00249   std::vector<SUnit*> NotReady;
00250   SUnit *CurNode = NULL;
00251   while (!AvailableQueue->empty()) {
00252     SUnit *CurNode = AvailableQueue->pop();
00253     while (CurNode && !isReady(CurNode, CurCycle)) {
00254       NotReady.push_back(CurNode);
00255       CurNode = AvailableQueue->pop();
00256     }
00257     
00258     // Add the nodes that aren't ready back onto the available list.
00259     AvailableQueue->push_all(NotReady);
00260     NotReady.clear();
00261 
00262     if (CurNode != NULL)
00263       ScheduleNodeBottomUp(CurNode, CurCycle);
00264     CurCycle++;
00265   }
00266 
00267   // Add entry node last
00268   if (DAG.getEntryNode().Val != DAG.getRoot().Val) {
00269     SUnit *Entry = SUnitMap[DAG.getEntryNode().Val];
00270     Sequence.push_back(Entry);
00271   }
00272 
00273   // Reverse the order if it is bottom up.
00274   std::reverse(Sequence.begin(), Sequence.end());
00275   
00276   
00277 #ifndef NDEBUG
00278   // Verify that all SUnits were scheduled.
00279   bool AnyNotSched = false;
00280   for (unsigned i = 0, e = SUnits.size(); i != e; ++i) {
00281     if (SUnits[i].NumSuccsLeft != 0 || SUnits[i].NumChainSuccsLeft != 0) {
00282       if (!AnyNotSched)
00283         std::cerr << "*** List scheduling failed! ***\n";
00284       SUnits[i].dump(&DAG);
00285       std::cerr << "has not been scheduled!\n";
00286       AnyNotSched = true;
00287     }
00288   }
00289   assert(!AnyNotSched);
00290 #endif
00291 }
00292 
00293 //===----------------------------------------------------------------------===//
00294 //  Top-Down Scheduling
00295 //===----------------------------------------------------------------------===//
00296 
00297 /// ReleaseSucc - Decrement the NumPredsLeft count of a successor. Add it to
00298 /// the PendingQueue if the count reaches zero.
00299 void ScheduleDAGRRList::ReleaseSucc(SUnit *SuccSU, bool isChain, 
00300                                     unsigned CurCycle) {
00301   // FIXME: the distance between two nodes is not always == the predecessor's
00302   // latency. For example, the reader can very well read the register written
00303   // by the predecessor later than the issue cycle. It also depends on the
00304   // interrupt model (drain vs. freeze).
00305   SuccSU->CycleBound = std::max(SuccSU->CycleBound, CurCycle + SuccSU->Latency);
00306 
00307   if (!isChain)
00308     SuccSU->NumPredsLeft--;
00309   else
00310     SuccSU->NumChainPredsLeft--;
00311   
00312 #ifndef NDEBUG
00313   if (SuccSU->NumPredsLeft < 0 || SuccSU->NumChainPredsLeft < 0) {
00314     std::cerr << "*** List scheduling failed! ***\n";
00315     SuccSU->dump(&DAG);
00316     std::cerr << " has been released too many times!\n";
00317     assert(0);
00318   }
00319 #endif
00320   
00321   if ((SuccSU->NumPredsLeft + SuccSU->NumChainPredsLeft) == 0) {
00322     SuccSU->isAvailable = true;
00323     AvailableQueue->push(SuccSU);
00324   }
00325 }
00326 
00327 
00328 /// ScheduleNodeTopDown - Add the node to the schedule. Decrement the pending
00329 /// count of its successors. If a successor pending count is zero, add it to
00330 /// the Available queue.
00331 void ScheduleDAGRRList::ScheduleNodeTopDown(SUnit *SU, unsigned CurCycle) {
00332   DEBUG(std::cerr << "*** Scheduling [" << CurCycle << "]: ");
00333   DEBUG(SU->dump(&DAG));
00334   SU->Cycle = CurCycle;
00335 
00336   AvailableQueue->ScheduledNode(SU);
00337   Sequence.push_back(SU);
00338 
00339   // Top down: release successors
00340   for (std::set<std::pair<SUnit*, bool> >::iterator I = SU->Succs.begin(),
00341          E = SU->Succs.end(); I != E; ++I)
00342     ReleaseSucc(I->first, I->second, CurCycle);
00343   SU->isScheduled = true;
00344 }
00345 
00346 void ScheduleDAGRRList::ListScheduleTopDown() {
00347   unsigned CurCycle = 0;
00348   SUnit *Entry = SUnitMap[DAG.getEntryNode().Val];
00349 
00350   // All leaves to Available queue.
00351   for (unsigned i = 0, e = SUnits.size(); i != e; ++i) {
00352     // It is available if it has no predecessors.
00353     if (SUnits[i].Preds.size() == 0 && &SUnits[i] != Entry) {
00354       AvailableQueue->push(&SUnits[i]);
00355       SUnits[i].isAvailable = true;
00356     }
00357   }
00358   
00359   // Emit the entry node first.
00360   ScheduleNodeTopDown(Entry, CurCycle);
00361   CurCycle++;
00362 
00363   // While Available queue is not empty, grab the node with the highest
00364   // priority. If it is not ready put it back. Schedule the node.
00365   std::vector<SUnit*> NotReady;
00366   SUnit *CurNode = NULL;
00367   while (!AvailableQueue->empty()) {
00368     SUnit *CurNode = AvailableQueue->pop();
00369     while (CurNode && !isReady(CurNode, CurCycle)) {
00370       NotReady.push_back(CurNode);
00371       CurNode = AvailableQueue->pop();
00372     }
00373     
00374     // Add the nodes that aren't ready back onto the available list.
00375     AvailableQueue->push_all(NotReady);
00376     NotReady.clear();
00377 
00378     if (CurNode != NULL)
00379       ScheduleNodeTopDown(CurNode, CurCycle);
00380     CurCycle++;
00381   }
00382   
00383   
00384 #ifndef NDEBUG
00385   // Verify that all SUnits were scheduled.
00386   bool AnyNotSched = false;
00387   for (unsigned i = 0, e = SUnits.size(); i != e; ++i) {
00388     if (!SUnits[i].isScheduled) {
00389       if (!AnyNotSched)
00390         std::cerr << "*** List scheduling failed! ***\n";
00391       SUnits[i].dump(&DAG);
00392       std::cerr << "has not been scheduled!\n";
00393       AnyNotSched = true;
00394     }
00395   }
00396   assert(!AnyNotSched);
00397 #endif
00398 }
00399 
00400 
00401 
00402 //===----------------------------------------------------------------------===//
00403 //                RegReductionPriorityQueue Implementation
00404 //===----------------------------------------------------------------------===//
00405 //
00406 // This is a SchedulingPriorityQueue that schedules using Sethi Ullman numbers
00407 // to reduce register pressure.
00408 // 
00409 namespace {
00410   template<class SF>
00411   class RegReductionPriorityQueue;
00412   
00413   /// Sorting functions for the Available queue.
00414   struct bu_ls_rr_sort : public std::binary_function<SUnit*, SUnit*, bool> {
00415     RegReductionPriorityQueue<bu_ls_rr_sort> *SPQ;
00416     bu_ls_rr_sort(RegReductionPriorityQueue<bu_ls_rr_sort> *spq) : SPQ(spq) {}
00417     bu_ls_rr_sort(const bu_ls_rr_sort &RHS) : SPQ(RHS.SPQ) {}
00418     
00419     bool operator()(const SUnit* left, const SUnit* right) const;
00420   };
00421 
00422   struct td_ls_rr_sort : public std::binary_function<SUnit*, SUnit*, bool> {
00423     RegReductionPriorityQueue<td_ls_rr_sort> *SPQ;
00424     td_ls_rr_sort(RegReductionPriorityQueue<td_ls_rr_sort> *spq) : SPQ(spq) {}
00425     td_ls_rr_sort(const td_ls_rr_sort &RHS) : SPQ(RHS.SPQ) {}
00426     
00427     bool operator()(const SUnit* left, const SUnit* right) const;
00428   };
00429 }  // end anonymous namespace
00430 
00431 namespace {
00432   template<class SF>
00433   class VISIBILITY_HIDDEN RegReductionPriorityQueue
00434    : public SchedulingPriorityQueue {
00435     std::priority_queue<SUnit*, std::vector<SUnit*>, SF> Queue;
00436 
00437   public:
00438     RegReductionPriorityQueue() :
00439     Queue(SF(this)) {}
00440     
00441     virtual void initNodes(const std::vector<SUnit> &sunits) {}
00442     virtual void releaseState() {}
00443     
00444     virtual int getSethiUllmanNumber(unsigned NodeNum) const {
00445       return 0;
00446     }
00447     
00448     bool empty() const { return Queue.empty(); }
00449     
00450     void push(SUnit *U) {
00451       Queue.push(U);
00452     }
00453     void push_all(const std::vector<SUnit *> &Nodes) {
00454       for (unsigned i = 0, e = Nodes.size(); i != e; ++i)
00455         Queue.push(Nodes[i]);
00456     }
00457     
00458     SUnit *pop() {
00459       if (empty()) return NULL;
00460       SUnit *V = Queue.top();
00461       Queue.pop();
00462       return V;
00463     }
00464   };
00465 
00466   template<class SF>
00467   class VISIBILITY_HIDDEN BURegReductionPriorityQueue
00468    : public RegReductionPriorityQueue<SF> {
00469     // SUnits - The SUnits for the current graph.
00470     const std::vector<SUnit> *SUnits;
00471     
00472     // SethiUllmanNumbers - The SethiUllman number for each node.
00473     std::vector<int> SethiUllmanNumbers;
00474 
00475   public:
00476     BURegReductionPriorityQueue() {}
00477 
00478     void initNodes(const std::vector<SUnit> &sunits) {
00479       SUnits = &sunits;
00480       // Add pseudo dependency edges for two-address nodes.
00481       AddPseudoTwoAddrDeps();
00482       // Calculate node priorities.
00483       CalculatePriorities();
00484     }
00485 
00486     void releaseState() {
00487       SUnits = 0;
00488       SethiUllmanNumbers.clear();
00489     }
00490 
00491     int getSethiUllmanNumber(unsigned NodeNum) const {
00492       assert(NodeNum < SethiUllmanNumbers.size());
00493       return SethiUllmanNumbers[NodeNum];
00494     }
00495 
00496   private:
00497     void AddPseudoTwoAddrDeps();
00498     void CalculatePriorities();
00499     int CalcNodePriority(const SUnit *SU);
00500   };
00501 
00502 
00503   template<class SF>
00504   class TDRegReductionPriorityQueue : public RegReductionPriorityQueue<SF> {
00505     // SUnits - The SUnits for the current graph.
00506     const std::vector<SUnit> *SUnits;
00507     
00508     // SethiUllmanNumbers - The SethiUllman number for each node.
00509     std::vector<int> SethiUllmanNumbers;
00510 
00511   public:
00512     TDRegReductionPriorityQueue() {}
00513 
00514     void initNodes(const std::vector<SUnit> &sunits) {
00515       SUnits = &sunits;
00516       // Calculate node priorities.
00517       CalculatePriorities();
00518     }
00519 
00520     void releaseState() {
00521       SUnits = 0;
00522       SethiUllmanNumbers.clear();
00523     }
00524 
00525     int getSethiUllmanNumber(unsigned NodeNum) const {
00526       assert(NodeNum < SethiUllmanNumbers.size());
00527       return SethiUllmanNumbers[NodeNum];
00528     }
00529 
00530   private:
00531     void CalculatePriorities();
00532     int CalcNodePriority(const SUnit *SU);
00533   };
00534 }
00535 
00536 static bool isFloater(const SUnit *SU) {
00537   if (SU->Node->isTargetOpcode()) {
00538     if (SU->NumPreds == 0)
00539       return true;
00540     if (SU->NumPreds == 1) {
00541       for (std::set<std::pair<SUnit*, bool> >::iterator I = SU->Preds.begin(),
00542              E = SU->Preds.end(); I != E; ++I) {
00543         if (I->second) continue;
00544 
00545         SUnit *PredSU = I->first;
00546         unsigned Opc = PredSU->Node->getOpcode();
00547         if (Opc != ISD::EntryToken && Opc != ISD::TokenFactor &&
00548             Opc != ISD::CopyFromReg && Opc != ISD::CopyToReg)
00549           return false;
00550       }
00551       return true;
00552     }
00553   }
00554   return false;
00555 }
00556 
00557 static bool isSimpleFloaterUse(const SUnit *SU) {
00558   unsigned NumOps = 0;
00559   for (std::set<std::pair<SUnit*, bool> >::iterator I = SU->Preds.begin(),
00560          E = SU->Preds.end(); I != E; ++I) {
00561     if (I->second) continue;
00562     if (++NumOps > 1)
00563       return false;
00564     if (!isFloater(I->first))
00565       return false;
00566   }
00567   return true;
00568 }
00569 
00570 // Bottom up
00571 bool bu_ls_rr_sort::operator()(const SUnit *left, const SUnit *right) const {
00572   unsigned LeftNum  = left->NodeNum;
00573   unsigned RightNum = right->NodeNum;
00574   bool LIsTarget = left->Node->isTargetOpcode();
00575   bool RIsTarget = right->Node->isTargetOpcode();
00576   int LPriority = SPQ->getSethiUllmanNumber(LeftNum);
00577   int RPriority = SPQ->getSethiUllmanNumber(RightNum);
00578   int LBonus = 0;
00579   int RBonus = 0;
00580 
00581   // Schedule floaters (e.g. load from some constant address) and those nodes
00582   // with a single predecessor each first. They maintain / reduce register
00583   // pressure.
00584   if (isFloater(left) || isSimpleFloaterUse(left))
00585     LBonus += 2;
00586   if (isFloater(right) || isSimpleFloaterUse(right))
00587     RBonus += 2;
00588 
00589   // Special tie breaker: if two nodes share a operand, the one that use it
00590   // as a def&use operand is preferred.
00591   if (LIsTarget && RIsTarget) {
00592     if (left->isTwoAddress && !right->isTwoAddress) {
00593       SDNode *DUNode = left->Node->getOperand(0).Val;
00594       if (DUNode->isOperand(right->Node))
00595         LBonus += 2;
00596     }
00597     if (!left->isTwoAddress && right->isTwoAddress) {
00598       SDNode *DUNode = right->Node->getOperand(0).Val;
00599       if (DUNode->isOperand(left->Node))
00600         RBonus += 2;
00601     }
00602   }
00603 
00604   if (LPriority+LBonus < RPriority+RBonus)
00605     return true;
00606   else if (LPriority+LBonus == RPriority+RBonus)
00607     if (left->Height > right->Height)
00608       return true;
00609     else if (left->Height == right->Height)
00610       if (left->Depth < right->Depth)
00611         return true;
00612       else if (left->Depth == right->Depth)
00613         if (left->CycleBound > right->CycleBound) 
00614           return true;
00615   return false;
00616 }
00617 
00618 static inline bool isCopyFromLiveIn(const SUnit *SU) {
00619   SDNode *N = SU->Node;
00620   return N->getOpcode() == ISD::CopyFromReg &&
00621     N->getOperand(N->getNumOperands()-1).getValueType() != MVT::Flag;
00622 }
00623 
00624 // FIXME: This is probably too slow!
00625 static void isReachable(SUnit *SU, SUnit *TargetSU,
00626                         std::set<SUnit *> &Visited, bool &Reached) {
00627   if (Reached) return;
00628   if (SU == TargetSU) {
00629     Reached = true;
00630     return;
00631   }
00632   if (!Visited.insert(SU).second) return;
00633 
00634   for (std::set<std::pair<SUnit*, bool> >::iterator I = SU->Preds.begin(),
00635          E = SU->Preds.end(); I != E; ++I)
00636     isReachable(I->first, TargetSU, Visited, Reached);
00637 }
00638 
00639 static bool isReachable(SUnit *SU, SUnit *TargetSU) {
00640   std::set<SUnit *> Visited;
00641   bool Reached = false;
00642   isReachable(SU, TargetSU, Visited, Reached);
00643   return Reached;
00644 }
00645 
00646 static SUnit *getDefUsePredecessor(SUnit *SU) {
00647   SDNode *DU = SU->Node->getOperand(0).Val;
00648   for (std::set<std::pair<SUnit*, bool> >::iterator
00649          I = SU->Preds.begin(), E = SU->Preds.end(); I != E; ++I) {
00650     if (I->second) continue;  // ignore chain preds
00651     SUnit *PredSU = I->first;
00652     if (PredSU->Node == DU)
00653       return PredSU;
00654   }
00655 
00656   // Must be flagged.
00657   return NULL;
00658 }
00659 
00660 static bool canClobber(SUnit *SU, SUnit *Op) {
00661   if (SU->isTwoAddress)
00662     return Op == getDefUsePredecessor(SU);
00663   return false;
00664 }
00665 
00666 /// AddPseudoTwoAddrDeps - If two nodes share an operand and one of them uses
00667 /// it as a def&use operand. Add a pseudo control edge from it to the other
00668 /// node (if it won't create a cycle) so the two-address one will be scheduled
00669 /// first (lower in the schedule).
00670 template<class SF>
00671 void BURegReductionPriorityQueue<SF>::AddPseudoTwoAddrDeps() {
00672   for (unsigned i = 0, e = SUnits->size(); i != e; ++i) {
00673     SUnit *SU = (SUnit *)&((*SUnits)[i]);
00674     SDNode *Node = SU->Node;
00675     if (!Node->isTargetOpcode())
00676       continue;
00677 
00678     if (SU->isTwoAddress) {
00679       SUnit *DUSU = getDefUsePredecessor(SU);
00680       if (!DUSU) continue;
00681 
00682       for (std::set<std::pair<SUnit*, bool> >::iterator I = DUSU->Succs.begin(),
00683              E = DUSU->Succs.end(); I != E; ++I) {
00684         if (I->second) continue;
00685         SUnit *SuccSU = I->first;
00686         if (SuccSU != SU &&
00687             (!canClobber(SuccSU, DUSU) ||
00688              (!SU->isCommutable && SuccSU->isCommutable))){
00689           if (SuccSU->Depth == SU->Depth && !isReachable(SuccSU, SU)) {
00690             DEBUG(std::cerr << "Adding an edge from SU # " << SU->NodeNum
00691                   << " to SU #" << SuccSU->NodeNum << "\n");
00692             if (SU->Preds.insert(std::make_pair(SuccSU, true)).second)
00693               SU->NumChainPredsLeft++;
00694             if (SuccSU->Succs.insert(std::make_pair(SU, true)).second)
00695               SuccSU->NumChainSuccsLeft++;
00696           }
00697         }
00698       }
00699     }
00700   }
00701 }
00702 
00703 /// CalcNodePriority - Priority is the Sethi Ullman number. 
00704 /// Smaller number is the higher priority.
00705 template<class SF>
00706 int BURegReductionPriorityQueue<SF>::CalcNodePriority(const SUnit *SU) {
00707   int &SethiUllmanNumber = SethiUllmanNumbers[SU->NodeNum];
00708   if (SethiUllmanNumber != 0)
00709     return SethiUllmanNumber;
00710 
00711   unsigned Opc = SU->Node->getOpcode();
00712   if (Opc == ISD::TokenFactor || Opc == ISD::CopyToReg)
00713     SethiUllmanNumber = INT_MAX - 10;
00714   else if (SU->NumSuccsLeft == 0)
00715     // If SU does not have a use, i.e. it doesn't produce a value that would
00716     // be consumed (e.g. store), then it terminates a chain of computation.
00717     // Give it a small SethiUllman number so it will be scheduled right before its
00718     // predecessors that it doesn't lengthen their live ranges.
00719     SethiUllmanNumber = INT_MIN + 10;
00720   // FIXME: remove this else if? It seems to reduce register spills but often
00721   // ends up increasing runtime. Need to investigate.
00722   else if (SU->NumPredsLeft == 0 &&
00723            (Opc != ISD::CopyFromReg || isCopyFromLiveIn(SU)))
00724     SethiUllmanNumber = INT_MAX - 10;
00725   else {
00726     int Extra = 0;
00727     for (std::set<std::pair<SUnit*, bool> >::const_iterator
00728          I = SU->Preds.begin(), E = SU->Preds.end(); I != E; ++I) {
00729       if (I->second) continue;  // ignore chain preds
00730       SUnit *PredSU = I->first;
00731       int PredSethiUllman = CalcNodePriority(PredSU);
00732       if (PredSethiUllman > SethiUllmanNumber) {
00733         SethiUllmanNumber = PredSethiUllman;
00734         Extra = 0;
00735       } else if (PredSethiUllman == SethiUllmanNumber && !I->second)
00736         Extra++;
00737     }
00738 
00739     SethiUllmanNumber += Extra;
00740   }
00741   
00742   return SethiUllmanNumber;
00743 }
00744 
00745 /// CalculatePriorities - Calculate priorities of all scheduling units.
00746 template<class SF>
00747 void BURegReductionPriorityQueue<SF>::CalculatePriorities() {
00748   SethiUllmanNumbers.assign(SUnits->size(), 0);
00749   
00750   for (unsigned i = 0, e = SUnits->size(); i != e; ++i)
00751     CalcNodePriority(&(*SUnits)[i]);
00752 }
00753 
00754 static unsigned SumOfUnscheduledPredsOfSuccs(const SUnit *SU) {
00755   unsigned Sum = 0;
00756   for (std::set<std::pair<SUnit*, bool> >::const_iterator
00757          I = SU->Succs.begin(), E = SU->Succs.end(); I != E; ++I) {
00758     SUnit *SuccSU = I->first;
00759     for (std::set<std::pair<SUnit*, bool> >::const_iterator
00760          II = SuccSU->Preds.begin(), EE = SuccSU->Preds.end(); II != EE; ++II) {
00761       SUnit *PredSU = II->first;
00762       if (!PredSU->isScheduled)
00763         Sum++;
00764     }
00765   }
00766 
00767   return Sum;
00768 }
00769 
00770 
00771 // Top down
00772 bool td_ls_rr_sort::operator()(const SUnit *left, const SUnit *right) const {
00773   unsigned LeftNum  = left->NodeNum;
00774   unsigned RightNum = right->NodeNum;
00775   int LPriority = SPQ->getSethiUllmanNumber(LeftNum);
00776   int RPriority = SPQ->getSethiUllmanNumber(RightNum);
00777   bool LIsTarget = left->Node->isTargetOpcode();
00778   bool RIsTarget = right->Node->isTargetOpcode();
00779   bool LIsFloater = LIsTarget && left->NumPreds == 0;
00780   bool RIsFloater = RIsTarget && right->NumPreds == 0;
00781   unsigned LBonus = (SumOfUnscheduledPredsOfSuccs(left) == 1) ? 2 : 0;
00782   unsigned RBonus = (SumOfUnscheduledPredsOfSuccs(right) == 1) ? 2 : 0;
00783 
00784   if (left->NumSuccs == 0 && right->NumSuccs != 0)
00785     return false;
00786   else if (left->NumSuccs != 0 && right->NumSuccs == 0)
00787     return true;
00788 
00789   // Special tie breaker: if two nodes share a operand, the one that use it
00790   // as a def&use operand is preferred.
00791   if (LIsTarget && RIsTarget) {
00792     if (left->isTwoAddress && !right->isTwoAddress) {
00793       SDNode *DUNode = left->Node->getOperand(0).Val;
00794       if (DUNode->isOperand(right->Node))
00795         RBonus += 2;
00796     }
00797     if (!left->isTwoAddress && right->isTwoAddress) {
00798       SDNode *DUNode = right->Node->getOperand(0).Val;
00799       if (DUNode->isOperand(left->Node))
00800         LBonus += 2;
00801     }
00802   }
00803   if (LIsFloater)
00804     LBonus -= 2;
00805   if (RIsFloater)
00806     RBonus -= 2;
00807   if (left->NumSuccs == 1)
00808     LBonus += 2;
00809   if (right->NumSuccs == 1)
00810     RBonus += 2;
00811 
00812   if (LPriority+LBonus < RPriority+RBonus)
00813     return true;
00814   else if (LPriority == RPriority)
00815     if (left->Depth < right->Depth)
00816       return true;
00817     else if (left->Depth == right->Depth)
00818       if (left->NumSuccsLeft > right->NumSuccsLeft)
00819         return true;
00820       else if (left->NumSuccsLeft == right->NumSuccsLeft)
00821         if (left->CycleBound > right->CycleBound) 
00822           return true;
00823   return false;
00824 }
00825 
00826 /// CalcNodePriority - Priority is the Sethi Ullman number. 
00827 /// Smaller number is the higher priority.
00828 template<class SF>
00829 int TDRegReductionPriorityQueue<SF>::CalcNodePriority(const SUnit *SU) {
00830   int &SethiUllmanNumber = SethiUllmanNumbers[SU->NodeNum];
00831   if (SethiUllmanNumber != 0)
00832     return SethiUllmanNumber;
00833 
00834   unsigned Opc = SU->Node->getOpcode();
00835   if (Opc == ISD::TokenFactor || Opc == ISD::CopyToReg)
00836     SethiUllmanNumber = INT_MAX - 10;
00837   else if (SU->NumSuccsLeft == 0)
00838     // If SU does not have a use, i.e. it doesn't produce a value that would
00839     // be consumed (e.g. store), then it terminates a chain of computation.
00840     // Give it a small SethiUllman number so it will be scheduled right before its
00841     // predecessors that it doesn't lengthen their live ranges.
00842     SethiUllmanNumber = INT_MIN + 10;
00843   else if (SU->NumPredsLeft == 0 &&
00844            (Opc != ISD::CopyFromReg || isCopyFromLiveIn(SU)))
00845     SethiUllmanNumber = 1;
00846   else {
00847     int Extra = 0;
00848     for (std::set<std::pair<SUnit*, bool> >::const_iterator
00849          I = SU->Preds.begin(), E = SU->Preds.end(); I != E; ++I) {
00850       if (I->second) continue;  // ignore chain preds
00851       SUnit *PredSU = I->first;
00852       int PredSethiUllman = CalcNodePriority(PredSU);
00853       if (PredSethiUllman > SethiUllmanNumber) {
00854         SethiUllmanNumber = PredSethiUllman;
00855         Extra = 0;
00856       } else if (PredSethiUllman == SethiUllmanNumber && !I->second)
00857         Extra++;
00858     }
00859 
00860     SethiUllmanNumber += Extra;
00861   }
00862   
00863   return SethiUllmanNumber;
00864 }
00865 
00866 /// CalculatePriorities - Calculate priorities of all scheduling units.
00867 template<class SF>
00868 void TDRegReductionPriorityQueue<SF>::CalculatePriorities() {
00869   SethiUllmanNumbers.assign(SUnits->size(), 0);
00870   
00871   for (unsigned i = 0, e = SUnits->size(); i != e; ++i)
00872     CalcNodePriority(&(*SUnits)[i]);
00873 }
00874 
00875 //===----------------------------------------------------------------------===//
00876 //                         Public Constructor Functions
00877 //===----------------------------------------------------------------------===//
00878 
00879 llvm::ScheduleDAG* llvm::createBURRListDAGScheduler(SelectionDAG &DAG,
00880                                                     MachineBasicBlock *BB) {
00881   return new ScheduleDAGRRList(DAG, BB, DAG.getTarget(), true,
00882                                new BURegReductionPriorityQueue<bu_ls_rr_sort>());
00883 }
00884 
00885 llvm::ScheduleDAG* llvm::createTDRRListDAGScheduler(SelectionDAG &DAG,
00886                                                     MachineBasicBlock *BB) {
00887   return new ScheduleDAGRRList(DAG, BB, DAG.getTarget(), false,
00888                                new TDRegReductionPriorityQueue<td_ls_rr_sort>());
00889 }
00890