LLVM API Documentation

ScheduleDAGRRList.cpp

Go to the documentation of this file.
00001 //===----- ScheduleDAGRRList.cpp - Reg pressure reduction list scheduler --===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // 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 "pre-RA-sched"
00019 #include "ScheduleDAGSDNodes.h"
00020 #include "llvm/CodeGen/SchedulerRegistry.h"
00021 #include "llvm/CodeGen/SelectionDAGISel.h"
00022 #include "llvm/Target/TargetRegisterInfo.h"
00023 #include "llvm/Target/TargetData.h"
00024 #include "llvm/Target/TargetMachine.h"
00025 #include "llvm/Target/TargetInstrInfo.h"
00026 #include "llvm/Support/Debug.h"
00027 #include "llvm/Support/Compiler.h"
00028 #include "llvm/Support/ErrorHandling.h"
00029 #include "llvm/ADT/PriorityQueue.h"
00030 #include "llvm/ADT/SmallSet.h"
00031 #include "llvm/ADT/Statistic.h"
00032 #include "llvm/ADT/STLExtras.h"
00033 #include <climits>
00034 using namespace llvm;
00035 
00036 STATISTIC(NumBacktracks, "Number of times scheduler backtracked");
00037 STATISTIC(NumUnfolds,    "Number of nodes unfolded");
00038 STATISTIC(NumDups,       "Number of duplicated nodes");
00039 STATISTIC(NumPRCopies,   "Number of physical register copies");
00040 
00041 static RegisterScheduler
00042   burrListDAGScheduler("list-burr",
00043                        "Bottom-up register reduction list scheduling",
00044                        createBURRListDAGScheduler);
00045 static RegisterScheduler
00046   tdrListrDAGScheduler("list-tdrr",
00047                        "Top-down register reduction list scheduling",
00048                        createTDRRListDAGScheduler);
00049 
00050 namespace {
00051 //===----------------------------------------------------------------------===//
00052 /// ScheduleDAGRRList - The actual register reduction list scheduler
00053 /// implementation.  This supports both top-down and bottom-up scheduling.
00054 ///
00055 class VISIBILITY_HIDDEN ScheduleDAGRRList : public ScheduleDAGSDNodes {
00056 private:
00057   /// isBottomUp - This is true if the scheduling problem is bottom-up, false if
00058   /// it is top-down.
00059   bool isBottomUp;
00060 
00061   /// AvailableQueue - The priority queue to use for the available SUnits.
00062   SchedulingPriorityQueue *AvailableQueue;
00063 
00064   /// LiveRegDefs - A set of physical registers and their definition
00065   /// that are "live". These nodes must be scheduled before any other nodes that
00066   /// modifies the registers can be scheduled.
00067   unsigned NumLiveRegs;
00068   std::vector<SUnit*> LiveRegDefs;
00069   std::vector<unsigned> LiveRegCycles;
00070 
00071   /// Topo - A topological ordering for SUnits which permits fast IsReachable
00072   /// and similar queries.
00073   ScheduleDAGTopologicalSort Topo;
00074 
00075 public:
00076   ScheduleDAGRRList(MachineFunction &mf,
00077                     bool isbottomup,
00078                     SchedulingPriorityQueue *availqueue)
00079     : ScheduleDAGSDNodes(mf), isBottomUp(isbottomup),
00080       AvailableQueue(availqueue), Topo(SUnits) {
00081     }
00082 
00083   ~ScheduleDAGRRList() {
00084     delete AvailableQueue;
00085   }
00086 
00087   void Schedule();
00088 
00089   /// IsReachable - Checks if SU is reachable from TargetSU.
00090   bool IsReachable(const SUnit *SU, const SUnit *TargetSU) {
00091     return Topo.IsReachable(SU, TargetSU);
00092   }
00093 
00094   /// WillCreateCycle - Returns true if adding an edge from SU to TargetSU will
00095   /// create a cycle.
00096   bool WillCreateCycle(SUnit *SU, SUnit *TargetSU) {
00097     return Topo.WillCreateCycle(SU, TargetSU);
00098   }
00099 
00100   /// AddPred - adds a predecessor edge to SUnit SU.
00101   /// This returns true if this is a new predecessor.
00102   /// Updates the topological ordering if required.
00103   void AddPred(SUnit *SU, const SDep &D) {
00104     Topo.AddPred(SU, D.getSUnit());
00105     SU->addPred(D);
00106   }
00107 
00108   /// RemovePred - removes a predecessor edge from SUnit SU.
00109   /// This returns true if an edge was removed.
00110   /// Updates the topological ordering if required.
00111   void RemovePred(SUnit *SU, const SDep &D) {
00112     Topo.RemovePred(SU, D.getSUnit());
00113     SU->removePred(D);
00114   }
00115 
00116 private:
00117   void ReleasePred(SUnit *SU, const SDep *PredEdge);
00118   void ReleasePredecessors(SUnit *SU, unsigned CurCycle);
00119   void ReleaseSucc(SUnit *SU, const SDep *SuccEdge);
00120   void ReleaseSuccessors(SUnit *SU);
00121   void CapturePred(SDep *PredEdge);
00122   void ScheduleNodeBottomUp(SUnit*, unsigned);
00123   void ScheduleNodeTopDown(SUnit*, unsigned);
00124   void UnscheduleNodeBottomUp(SUnit*);
00125   void BacktrackBottomUp(SUnit*, unsigned, unsigned&);
00126   SUnit *CopyAndMoveSuccessors(SUnit*);
00127   void InsertCopiesAndMoveSuccs(SUnit*, unsigned,
00128                                 const TargetRegisterClass*,
00129                                 const TargetRegisterClass*,
00130                                 SmallVector<SUnit*, 2>&);
00131   bool DelayForLiveRegsBottomUp(SUnit*, SmallVector<unsigned, 4>&);
00132   void ListScheduleTopDown();
00133   void ListScheduleBottomUp();
00134 
00135 
00136   /// CreateNewSUnit - Creates a new SUnit and returns a pointer to it.
00137   /// Updates the topological ordering if required.
00138   SUnit *CreateNewSUnit(SDNode *N) {
00139     unsigned NumSUnits = SUnits.size();
00140     SUnit *NewNode = NewSUnit(N);
00141     // Update the topological ordering.
00142     if (NewNode->NodeNum >= NumSUnits)
00143       Topo.InitDAGTopologicalSorting();
00144     return NewNode;
00145   }
00146 
00147   /// CreateClone - Creates a new SUnit from an existing one.
00148   /// Updates the topological ordering if required.
00149   SUnit *CreateClone(SUnit *N) {
00150     unsigned NumSUnits = SUnits.size();
00151     SUnit *NewNode = Clone(N);
00152     // Update the topological ordering.
00153     if (NewNode->NodeNum >= NumSUnits)
00154       Topo.InitDAGTopologicalSorting();
00155     return NewNode;
00156   }
00157 
00158   /// ForceUnitLatencies - Return true, since register-pressure-reducing
00159   /// scheduling doesn't need actual latency information.
00160   bool ForceUnitLatencies() const { return true; }
00161 };
00162 }  // end anonymous namespace
00163 
00164 
00165 /// Schedule - Schedule the DAG using list scheduling.
00166 void ScheduleDAGRRList::Schedule() {
00167   DOUT << "********** List Scheduling **********\n";
00168 
00169   NumLiveRegs = 0;
00170   LiveRegDefs.resize(TRI->getNumRegs(), NULL);  
00171   LiveRegCycles.resize(TRI->getNumRegs(), 0);
00172 
00173   // Build the scheduling graph.
00174   BuildSchedGraph();
00175 
00176   DEBUG(for (unsigned su = 0, e = SUnits.size(); su != e; ++su)
00177           SUnits[su].dumpAll(this));
00178   Topo.InitDAGTopologicalSorting();
00179 
00180   AvailableQueue->initNodes(SUnits);
00181   
00182   // Execute the actual scheduling loop Top-Down or Bottom-Up as appropriate.
00183   if (isBottomUp)
00184     ListScheduleBottomUp();
00185   else
00186     ListScheduleTopDown();
00187   
00188   AvailableQueue->releaseState();
00189 }
00190 
00191 //===----------------------------------------------------------------------===//
00192 //  Bottom-Up Scheduling
00193 //===----------------------------------------------------------------------===//
00194 
00195 /// ReleasePred - Decrement the NumSuccsLeft count of a predecessor. Add it to
00196 /// the AvailableQueue if the count reaches zero. Also update its cycle bound.
00197 void ScheduleDAGRRList::ReleasePred(SUnit *SU, const SDep *PredEdge) {
00198   SUnit *PredSU = PredEdge->getSUnit();
00199   --PredSU->NumSuccsLeft;
00200   
00201 #ifndef NDEBUG
00202   if (PredSU->NumSuccsLeft < 0) {
00203     cerr << "*** Scheduling failed! ***\n";
00204     PredSU->dump(this);
00205     cerr << " has been released too many times!\n";
00206     llvm_unreachable(0);
00207   }
00208 #endif
00209   
00210   // If all the node's successors are scheduled, this node is ready
00211   // to be scheduled. Ignore the special EntrySU node.
00212   if (PredSU->NumSuccsLeft == 0 && PredSU != &EntrySU) {
00213     PredSU->isAvailable = true;
00214     AvailableQueue->push(PredSU);
00215   }
00216 }
00217 
00218 void ScheduleDAGRRList::ReleasePredecessors(SUnit *SU, unsigned CurCycle) {
00219   // Bottom up: release predecessors
00220   for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
00221        I != E; ++I) {
00222     ReleasePred(SU, &*I);
00223     if (I->isAssignedRegDep()) {
00224       // This is a physical register dependency and it's impossible or
00225       // expensive to copy the register. Make sure nothing that can 
00226       // clobber the register is scheduled between the predecessor and
00227       // this node.
00228       if (!LiveRegDefs[I->getReg()]) {
00229         ++NumLiveRegs;
00230         LiveRegDefs[I->getReg()] = I->getSUnit();
00231         LiveRegCycles[I->getReg()] = CurCycle;
00232       }
00233     }
00234   }
00235 }
00236 
00237 /// ScheduleNodeBottomUp - Add the node to the schedule. Decrement the pending
00238 /// count of its predecessors. If a predecessor pending count is zero, add it to
00239 /// the Available queue.
00240 void ScheduleDAGRRList::ScheduleNodeBottomUp(SUnit *SU, unsigned CurCycle) {
00241   DOUT << "*** Scheduling [" << CurCycle << "]: ";
00242   DEBUG(SU->dump(this));
00243 
00244   assert(CurCycle >= SU->getHeight() && "Node scheduled below its height!");
00245   SU->setHeightToAtLeast(CurCycle);
00246   Sequence.push_back(SU);
00247 
00248   ReleasePredecessors(SU, CurCycle);
00249 
00250   // Release all the implicit physical register defs that are live.
00251   for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
00252        I != E; ++I) {
00253     if (I->isAssignedRegDep()) {
00254       if (LiveRegCycles[I->getReg()] == I->getSUnit()->getHeight()) {
00255         assert(NumLiveRegs > 0 && "NumLiveRegs is already zero!");
00256         assert(LiveRegDefs[I->getReg()] == SU &&
00257                "Physical register dependency violated?");
00258         --NumLiveRegs;
00259         LiveRegDefs[I->getReg()] = NULL;
00260         LiveRegCycles[I->getReg()] = 0;
00261       }
00262     }
00263   }
00264 
00265   SU->isScheduled = true;
00266   AvailableQueue->ScheduledNode(SU);
00267 }
00268 
00269 /// CapturePred - This does the opposite of ReleasePred. Since SU is being
00270 /// unscheduled, incrcease the succ left count of its predecessors. Remove
00271 /// them from AvailableQueue if necessary.
00272 void ScheduleDAGRRList::CapturePred(SDep *PredEdge) {  
00273   SUnit *PredSU = PredEdge->getSUnit();
00274   if (PredSU->isAvailable) {
00275     PredSU->isAvailable = false;
00276     if (!PredSU->isPending)
00277       AvailableQueue->remove(PredSU);
00278   }
00279 
00280   ++PredSU->NumSuccsLeft;
00281 }
00282 
00283 /// UnscheduleNodeBottomUp - Remove the node from the schedule, update its and
00284 /// its predecessor states to reflect the change.
00285 void ScheduleDAGRRList::UnscheduleNodeBottomUp(SUnit *SU) {
00286   DOUT << "*** Unscheduling [" << SU->getHeight() << "]: ";
00287   DEBUG(SU->dump(this));
00288 
00289   AvailableQueue->UnscheduledNode(SU);
00290 
00291   for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
00292        I != E; ++I) {
00293     CapturePred(&*I);
00294     if (I->isAssignedRegDep() && SU->getHeight() == LiveRegCycles[I->getReg()]) {
00295       assert(NumLiveRegs > 0 && "NumLiveRegs is already zero!");
00296       assert(LiveRegDefs[I->getReg()] == I->getSUnit() &&
00297              "Physical register dependency violated?");
00298       --NumLiveRegs;
00299       LiveRegDefs[I->getReg()] = NULL;
00300       LiveRegCycles[I->getReg()] = 0;
00301     }
00302   }
00303 
00304   for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
00305        I != E; ++I) {
00306     if (I->isAssignedRegDep()) {
00307       if (!LiveRegDefs[I->getReg()]) {
00308         LiveRegDefs[I->getReg()] = SU;
00309         ++NumLiveRegs;
00310       }
00311       if (I->getSUnit()->getHeight() < LiveRegCycles[I->getReg()])
00312         LiveRegCycles[I->getReg()] = I->getSUnit()->getHeight();
00313     }
00314   }
00315 
00316   SU->setHeightDirty();
00317   SU->isScheduled = false;
00318   SU->isAvailable = true;
00319   AvailableQueue->push(SU);
00320 }
00321 
00322 /// BacktrackBottomUp - Backtrack scheduling to a previous cycle specified in
00323 /// BTCycle in order to schedule a specific node.
00324 void ScheduleDAGRRList::BacktrackBottomUp(SUnit *SU, unsigned BtCycle,
00325                                           unsigned &CurCycle) {
00326   SUnit *OldSU = NULL;
00327   while (CurCycle > BtCycle) {
00328     OldSU = Sequence.back();
00329     Sequence.pop_back();
00330     if (SU->isSucc(OldSU))
00331       // Don't try to remove SU from AvailableQueue.
00332       SU->isAvailable = false;
00333     UnscheduleNodeBottomUp(OldSU);
00334     --CurCycle;
00335   }
00336 
00337   assert(!SU->isSucc(OldSU) && "Something is wrong!");
00338 
00339   ++NumBacktracks;
00340 }
00341 
00342 /// CopyAndMoveSuccessors - Clone the specified node and move its scheduled
00343 /// successors to the newly created node.
00344 SUnit *ScheduleDAGRRList::CopyAndMoveSuccessors(SUnit *SU) {
00345   if (SU->getNode()->getFlaggedNode())
00346     return NULL;
00347 
00348   SDNode *N = SU->getNode();
00349   if (!N)
00350     return NULL;
00351 
00352   SUnit *NewSU;
00353   bool TryUnfold = false;
00354   for (unsigned i = 0, e = N->getNumValues(); i != e; ++i) {
00355     EVT VT = N->getValueType(i);
00356     if (VT == MVT::Flag)
00357       return NULL;
00358     else if (VT == MVT::Other)
00359       TryUnfold = true;
00360   }
00361   for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) {
00362     const SDValue &Op = N->getOperand(i);
00363     EVT VT = Op.getNode()->getValueType(Op.getResNo());
00364     if (VT == MVT::Flag)
00365       return NULL;
00366   }
00367 
00368   if (TryUnfold) {
00369     SmallVector<SDNode*, 2> NewNodes;
00370     if (!TII->unfoldMemoryOperand(*DAG, N, NewNodes))
00371       return NULL;
00372 
00373     DOUT << "Unfolding SU # " << SU->NodeNum << "\n";
00374     assert(NewNodes.size() == 2 && "Expected a load folding node!");
00375 
00376     N = NewNodes[1];
00377     SDNode *LoadNode = NewNodes[0];
00378     unsigned NumVals = N->getNumValues();
00379     unsigned OldNumVals = SU->getNode()->getNumValues();
00380     for (unsigned i = 0; i != NumVals; ++i)
00381       DAG->ReplaceAllUsesOfValueWith(SDValue(SU->getNode(), i), SDValue(N, i));
00382     DAG->ReplaceAllUsesOfValueWith(SDValue(SU->getNode(), OldNumVals-1),
00383                                    SDValue(LoadNode, 1));
00384 
00385     // LoadNode may already exist. This can happen when there is another
00386     // load from the same location and producing the same type of value
00387     // but it has different alignment or volatileness.
00388     bool isNewLoad = true;
00389     SUnit *LoadSU;
00390     if (LoadNode->getNodeId() != -1) {
00391       LoadSU = &SUnits[LoadNode->getNodeId()];
00392       isNewLoad = false;
00393     } else {
00394       LoadSU = CreateNewSUnit(LoadNode);
00395       LoadNode->setNodeId(LoadSU->NodeNum);
00396       ComputeLatency(LoadSU);
00397     }
00398 
00399     SUnit *NewSU = CreateNewSUnit(N);
00400     assert(N->getNodeId() == -1 && "Node already inserted!");
00401     N->setNodeId(NewSU->NodeNum);
00402       
00403     const TargetInstrDesc &TID = TII->get(N->getMachineOpcode());
00404     for (unsigned i = 0; i != TID.getNumOperands(); ++i) {
00405       if (TID.getOperandConstraint(i, TOI::TIED_TO) != -1) {
00406         NewSU->isTwoAddress = true;
00407         break;
00408       }
00409     }
00410     if (TID.isCommutable())
00411       NewSU->isCommutable = true;
00412     ComputeLatency(NewSU);
00413 
00414     // Record all the edges to and from the old SU, by category.
00415     SmallVector<SDep, 4> ChainPreds;
00416     SmallVector<SDep, 4> ChainSuccs;
00417     SmallVector<SDep, 4> LoadPreds;
00418     SmallVector<SDep, 4> NodePreds;
00419     SmallVector<SDep, 4> NodeSuccs;
00420     for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
00421          I != E; ++I) {
00422       if (I->isCtrl())
00423         ChainPreds.push_back(*I);
00424       else if (I->getSUnit()->getNode() &&
00425                I->getSUnit()->getNode()->isOperandOf(LoadNode))
00426         LoadPreds.push_back(*I);
00427       else
00428         NodePreds.push_back(*I);
00429     }
00430     for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
00431          I != E; ++I) {
00432       if (I->isCtrl())
00433         ChainSuccs.push_back(*I);
00434       else
00435         NodeSuccs.push_back(*I);
00436     }
00437 
00438     // Now assign edges to the newly-created nodes.
00439     for (unsigned i = 0, e = ChainPreds.size(); i != e; ++i) {
00440       const SDep &Pred = ChainPreds[i];
00441       RemovePred(SU, Pred);
00442       if (isNewLoad)
00443         AddPred(LoadSU, Pred);
00444     }
00445     for (unsigned i = 0, e = LoadPreds.size(); i != e; ++i) {
00446       const SDep &Pred = LoadPreds[i];
00447       RemovePred(SU, Pred);
00448       if (isNewLoad)
00449         AddPred(LoadSU, Pred);
00450     }
00451     for (unsigned i = 0, e = NodePreds.size(); i != e; ++i) {
00452       const SDep &Pred = NodePreds[i];
00453       RemovePred(SU, Pred);
00454       AddPred(NewSU, Pred);
00455     }
00456     for (unsigned i = 0, e = NodeSuccs.size(); i != e; ++i) {
00457       SDep D = NodeSuccs[i];
00458       SUnit *SuccDep = D.getSUnit();
00459       D.setSUnit(SU);
00460       RemovePred(SuccDep, D);
00461       D.setSUnit(NewSU);
00462       AddPred(SuccDep, D);
00463     }
00464     for (unsigned i = 0, e = ChainSuccs.size(); i != e; ++i) {
00465       SDep D = ChainSuccs[i];
00466       SUnit *SuccDep = D.getSUnit();
00467       D.setSUnit(SU);
00468       RemovePred(SuccDep, D);
00469       if (isNewLoad) {
00470         D.setSUnit(LoadSU);
00471         AddPred(SuccDep, D);
00472       }
00473     } 
00474 
00475     // Add a data dependency to reflect that NewSU reads the value defined
00476     // by LoadSU.
00477     AddPred(NewSU, SDep(LoadSU, SDep::Data, LoadSU->Latency));
00478 
00479     if (isNewLoad)
00480       AvailableQueue->addNode(LoadSU);
00481     AvailableQueue->addNode(NewSU);
00482 
00483     ++NumUnfolds;
00484 
00485     if (NewSU->NumSuccsLeft == 0) {
00486       NewSU->isAvailable = true;
00487       return NewSU;
00488     }
00489     SU = NewSU;
00490   }
00491 
00492   DOUT << "Duplicating SU # " << SU->NodeNum << "\n";
00493   NewSU = CreateClone(SU);
00494 
00495   // New SUnit has the exact same predecessors.
00496   for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
00497        I != E; ++I)
00498     if (!I->isArtificial())
00499       AddPred(NewSU, *I);
00500 
00501   // Only copy scheduled successors. Cut them from old node's successor
00502   // list and move them over.
00503   SmallVector<std::pair<SUnit *, SDep>, 4> DelDeps;
00504   for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
00505        I != E; ++I) {
00506     if (I->isArtificial())
00507       continue;
00508     SUnit *SuccSU = I->getSUnit();
00509     if (SuccSU->isScheduled) {
00510       SDep D = *I;
00511       D.setSUnit(NewSU);
00512       AddPred(SuccSU, D);
00513       D.setSUnit(SU);
00514       DelDeps.push_back(std::make_pair(SuccSU, D));
00515     }
00516   }
00517   for (unsigned i = 0, e = DelDeps.size(); i != e; ++i)
00518     RemovePred(DelDeps[i].first, DelDeps[i].second);
00519 
00520   AvailableQueue->updateNode(SU);
00521   AvailableQueue->addNode(NewSU);
00522 
00523   ++NumDups;
00524   return NewSU;
00525 }
00526 
00527 /// InsertCopiesAndMoveSuccs - Insert register copies and move all
00528 /// scheduled successors of the given SUnit to the last copy.
00529 void ScheduleDAGRRList::InsertCopiesAndMoveSuccs(SUnit *SU, unsigned Reg,
00530                                                const TargetRegisterClass *DestRC,
00531                                                const TargetRegisterClass *SrcRC,
00532                                                SmallVector<SUnit*, 2> &Copies) {
00533   SUnit *CopyFromSU = CreateNewSUnit(NULL);
00534   CopyFromSU->CopySrcRC = SrcRC;
00535   CopyFromSU->CopyDstRC = DestRC;
00536 
00537   SUnit *CopyToSU = CreateNewSUnit(NULL);
00538   CopyToSU->CopySrcRC = DestRC;
00539   CopyToSU->CopyDstRC = SrcRC;
00540 
00541   // Only copy scheduled successors. Cut them from old node's successor
00542   // list and move them over.
00543   SmallVector<std::pair<SUnit *, SDep>, 4> DelDeps;
00544   for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
00545        I != E; ++I) {
00546     if (I->isArtificial())
00547       continue;
00548     SUnit *SuccSU = I->getSUnit();
00549     if (SuccSU->isScheduled) {
00550       SDep D = *I;
00551       D.setSUnit(CopyToSU);
00552       AddPred(SuccSU, D);
00553       DelDeps.push_back(std::make_pair(SuccSU, *I));
00554     }
00555   }
00556   for (unsigned i = 0, e = DelDeps.size(); i != e; ++i)
00557     RemovePred(DelDeps[i].first, DelDeps[i].second);
00558 
00559   AddPred(CopyFromSU, SDep(SU, SDep::Data, SU->Latency, Reg));
00560   AddPred(CopyToSU, SDep(CopyFromSU, SDep::Data, CopyFromSU->Latency, 0));
00561 
00562   AvailableQueue->updateNode(SU);
00563   AvailableQueue->addNode(CopyFromSU);
00564   AvailableQueue->addNode(CopyToSU);
00565   Copies.push_back(CopyFromSU);
00566   Copies.push_back(CopyToSU);
00567 
00568   ++NumPRCopies;
00569 }
00570 
00571 /// getPhysicalRegisterVT - Returns the ValueType of the physical register
00572 /// definition of the specified node.
00573 /// FIXME: Move to SelectionDAG?
00574 static EVT getPhysicalRegisterVT(SDNode *N, unsigned Reg,
00575                                  const TargetInstrInfo *TII) {
00576   const TargetInstrDesc &TID = TII->get(N->getMachineOpcode());
00577   assert(TID.ImplicitDefs && "Physical reg def must be in implicit def list!");
00578   unsigned NumRes = TID.getNumDefs();
00579   for (const unsigned *ImpDef = TID.getImplicitDefs(); *ImpDef; ++ImpDef) {
00580     if (Reg == *ImpDef)
00581       break;
00582     ++NumRes;
00583   }
00584   return N->getValueType(NumRes);
00585 }
00586 
00587 /// CheckForLiveRegDef - Return true and update live register vector if the
00588 /// specified register def of the specified SUnit clobbers any "live" registers.
00589 static bool CheckForLiveRegDef(SUnit *SU, unsigned Reg,
00590                                std::vector<SUnit*> &LiveRegDefs,
00591                                SmallSet<unsigned, 4> &RegAdded,
00592                                SmallVector<unsigned, 4> &LRegs,
00593                                const TargetRegisterInfo *TRI) {
00594   bool Added = false;
00595   if (LiveRegDefs[Reg] && LiveRegDefs[Reg] != SU) {
00596     if (RegAdded.insert(Reg)) {
00597       LRegs.push_back(Reg);
00598       Added = true;
00599     }
00600   }
00601   for (const unsigned *Alias = TRI->getAliasSet(Reg); *Alias; ++Alias)
00602     if (LiveRegDefs[*Alias] && LiveRegDefs[*Alias] != SU) {
00603       if (RegAdded.insert(*Alias)) {
00604         LRegs.push_back(*Alias);
00605         Added = true;
00606       }
00607     }
00608   return Added;
00609 }
00610 
00611 /// DelayForLiveRegsBottomUp - Returns true if it is necessary to delay
00612 /// scheduling of the given node to satisfy live physical register dependencies.
00613 /// If the specific node is the last one that's available to schedule, do
00614 /// whatever is necessary (i.e. backtracking or cloning) to make it possible.
00615 bool ScheduleDAGRRList::DelayForLiveRegsBottomUp(SUnit *SU,
00616                                                  SmallVector<unsigned, 4> &LRegs){
00617   if (NumLiveRegs == 0)
00618     return false;
00619 
00620   SmallSet<unsigned, 4> RegAdded;
00621   // If this node would clobber any "live" register, then it's not ready.
00622   for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
00623        I != E; ++I) {
00624     if (I->isAssignedRegDep())
00625       CheckForLiveRegDef(I->getSUnit(), I->getReg(), LiveRegDefs,
00626                          RegAdded, LRegs, TRI);
00627   }
00628 
00629   for (SDNode *Node = SU->getNode(); Node; Node = Node->getFlaggedNode()) {
00630     if (Node->getOpcode() == ISD::INLINEASM) {
00631       // Inline asm can clobber physical defs.
00632       unsigned NumOps = Node->getNumOperands();
00633       if (Node->getOperand(NumOps-1).getValueType() == MVT::Flag)
00634         --NumOps;  // Ignore the flag operand.
00635 
00636       for (unsigned i = 2; i != NumOps;) {
00637         unsigned Flags =
00638           cast<ConstantSDNode>(Node->getOperand(i))->getZExtValue();
00639         unsigned NumVals = (Flags & 0xffff) >> 3;
00640 
00641         ++i; // Skip the ID value.
00642         if ((Flags & 7) == 2 || (Flags & 7) == 6) {
00643           // Check for def of register or earlyclobber register.
00644           for (; NumVals; --NumVals, ++i) {
00645             unsigned Reg = cast<RegisterSDNode>(Node->getOperand(i))->getReg();
00646             if (TargetRegisterInfo::isPhysicalRegister(Reg))
00647               CheckForLiveRegDef(SU, Reg, LiveRegDefs, RegAdded, LRegs, TRI);
00648           }
00649         } else
00650           i += NumVals;
00651       }
00652       continue;
00653     }
00654 
00655     if (!Node->isMachineOpcode())
00656       continue;
00657     const TargetInstrDesc &TID = TII->get(Node->getMachineOpcode());
00658     if (!TID.ImplicitDefs)
00659       continue;
00660     for (const unsigned *Reg = TID.ImplicitDefs; *Reg; ++Reg)
00661       CheckForLiveRegDef(SU, *Reg, LiveRegDefs, RegAdded, LRegs, TRI);
00662   }
00663   return !LRegs.empty();
00664 }
00665 
00666 
00667 /// ListScheduleBottomUp - The main loop of list scheduling for bottom-up
00668 /// schedulers.
00669 void ScheduleDAGRRList::ListScheduleBottomUp() {
00670   unsigned CurCycle = 0;
00671 
00672   // Release any predecessors of the special Exit node.
00673   ReleasePredecessors(&ExitSU, CurCycle);
00674 
00675   // Add root to Available queue.
00676   if (!SUnits.empty()) {
00677     SUnit *RootSU = &SUnits[DAG->getRoot().getNode()->getNodeId()];
00678     assert(RootSU->Succs.empty() && "Graph root shouldn't have successors!");
00679     RootSU->isAvailable = true;
00680     AvailableQueue->push(RootSU);
00681   }
00682 
00683   // While Available queue is not empty, grab the node with the highest
00684   // priority. If it is not ready put it back.  Schedule the node.
00685   SmallVector<SUnit*, 4> NotReady;
00686   DenseMap<SUnit*, SmallVector<unsigned, 4> > LRegsMap;
00687   Sequence.reserve(SUnits.size());
00688   while (!AvailableQueue->empty()) {
00689     bool Delayed = false;
00690     LRegsMap.clear();
00691     SUnit *CurSU = AvailableQueue->pop();
00692     while (CurSU) {
00693       SmallVector<unsigned, 4> LRegs;
00694       if (!DelayForLiveRegsBottomUp(CurSU, LRegs))
00695         break;
00696       Delayed = true;
00697       LRegsMap.insert(std::make_pair(CurSU, LRegs));
00698 
00699       CurSU->isPending = true;  // This SU is not in AvailableQueue right now.
00700       NotReady.push_back(CurSU);
00701       CurSU = AvailableQueue->pop();
00702     }
00703 
00704     // All candidates are delayed due to live physical reg dependencies.
00705     // Try backtracking, code duplication, or inserting cross class copies
00706     // to resolve it.
00707     if (Delayed && !CurSU) {
00708       for (unsigned i = 0, e = NotReady.size(); i != e; ++i) {
00709         SUnit *TrySU = NotReady[i];
00710         SmallVector<unsigned, 4> &LRegs = LRegsMap[TrySU];
00711 
00712         // Try unscheduling up to the point where it's safe to schedule
00713         // this node.
00714         unsigned LiveCycle = CurCycle;
00715         for (unsigned j = 0, ee = LRegs.size(); j != ee; ++j) {
00716           unsigned Reg = LRegs[j];
00717           unsigned LCycle = LiveRegCycles[Reg];
00718           LiveCycle = std::min(LiveCycle, LCycle);
00719         }
00720         SUnit *OldSU = Sequence[LiveCycle];
00721         if (!WillCreateCycle(TrySU, OldSU))  {
00722           BacktrackBottomUp(TrySU, LiveCycle, CurCycle);
00723           // Force the current node to be scheduled before the node that
00724           // requires the physical reg dep.
00725           if (OldSU->isAvailable) {
00726             OldSU->isAvailable = false;
00727             AvailableQueue->remove(OldSU);
00728           }
00729           AddPred(TrySU, SDep(OldSU, SDep::Order, /*Latency=*/1,
00730                               /*Reg=*/0, /*isNormalMemory=*/false,
00731                               /*isMustAlias=*/false, /*isArtificial=*/true));
00732           // If one or more successors has been unscheduled, then the current
00733           // node is no longer avaialable. Schedule a successor that's now
00734           // available instead.
00735           if (!TrySU->isAvailable)
00736             CurSU = AvailableQueue->pop();
00737           else {
00738             CurSU = TrySU;
00739             TrySU->isPending = false;
00740             NotReady.erase(NotReady.begin()+i);
00741           }
00742           break;
00743         }
00744       }
00745 
00746       if (!CurSU) {
00747         // Can't backtrack. If it's too expensive to copy the value, then try
00748         // duplicate the nodes that produces these "too expensive to copy"
00749         // values to break the dependency. In case even that doesn't work,
00750         // insert cross class copies.
00751         // If it's not too expensive, i.e. cost != -1, issue copies.
00752         SUnit *TrySU = NotReady[0];
00753         SmallVector<unsigned, 4> &LRegs = LRegsMap[TrySU];
00754         assert(LRegs.size() == 1 && "Can't handle this yet!");
00755         unsigned Reg = LRegs[0];
00756         SUnit *LRDef = LiveRegDefs[Reg];
00757         EVT VT = getPhysicalRegisterVT(LRDef->getNode(), Reg, TII);
00758         const TargetRegisterClass *RC =
00759           TRI->getPhysicalRegisterRegClass(Reg, VT);
00760         const TargetRegisterClass *DestRC = TRI->getCrossCopyRegClass(RC);
00761 
00762         // If cross copy register class is null, then it must be possible copy
00763         // the value directly. Do not try duplicate the def.
00764         SUnit *NewDef = 0;
00765         if (DestRC)
00766           NewDef = CopyAndMoveSuccessors(LRDef);
00767         else
00768           DestRC = RC;
00769         if (!NewDef) {
00770           // Issue copies, these can be expensive cross register class copies.
00771           SmallVector<SUnit*, 2> Copies;
00772           InsertCopiesAndMoveSuccs(LRDef, Reg, DestRC, RC, Copies);
00773           DOUT << "Adding an edge from SU #" << TrySU->NodeNum
00774                << " to SU #" << Copies.front()->NodeNum << "\n";
00775           AddPred(TrySU, SDep(Copies.front(), SDep::Order, /*Latency=*/1,
00776                               /*Reg=*/0, /*isNormalMemory=*/false,
00777                               /*isMustAlias=*/false,
00778                               /*isArtificial=*/true));
00779           NewDef = Copies.back();
00780         }
00781 
00782         DOUT << "Adding an edge from SU #" << NewDef->NodeNum
00783              << " to SU #" << TrySU->NodeNum << "\n";
00784         LiveRegDefs[Reg] = NewDef;
00785         AddPred(NewDef, SDep(TrySU, SDep::Order, /*Latency=*/1,
00786                              /*Reg=*/0, /*isNormalMemory=*/false,
00787                              /*isMustAlias=*/false,
00788                              /*isArtificial=*/true));
00789         TrySU->isAvailable = false;
00790         CurSU = NewDef;
00791       }
00792 
00793       assert(CurSU && "Unable to resolve live physical register dependencies!");
00794     }
00795 
00796     // Add the nodes that aren't ready back onto the available list.
00797     for (unsigned i = 0, e = NotReady.size(); i != e; ++i) {
00798       NotReady[i]->isPending = false;
00799       // May no longer be available due to backtracking.
00800       if (NotReady[i]->isAvailable)
00801         AvailableQueue->push(NotReady[i]);
00802     }
00803     NotReady.clear();
00804 
00805     if (CurSU)
00806       ScheduleNodeBottomUp(CurSU, CurCycle);
00807     ++CurCycle;
00808   }
00809 
00810   // Reverse the order if it is bottom up.
00811   std::reverse(Sequence.begin(), Sequence.end());
00812   
00813 #ifndef NDEBUG
00814   VerifySchedule(isBottomUp);
00815 #endif
00816 }
00817 
00818 //===----------------------------------------------------------------------===//
00819 //  Top-Down Scheduling
00820 //===----------------------------------------------------------------------===//
00821 
00822 /// ReleaseSucc - Decrement the NumPredsLeft count of a successor. Add it to
00823 /// the AvailableQueue if the count reaches zero. Also update its cycle bound.
00824 void ScheduleDAGRRList::ReleaseSucc(SUnit *SU, const SDep *SuccEdge) {
00825   SUnit *SuccSU = SuccEdge->getSUnit();
00826   --SuccSU->NumPredsLeft;
00827   
00828 #ifndef NDEBUG
00829   if (SuccSU->NumPredsLeft < 0) {
00830     cerr << "*** Scheduling failed! ***\n";
00831     SuccSU->dump(this);
00832     cerr << " has been released too many times!\n";
00833     llvm_unreachable(0);
00834   }
00835 #endif
00836   
00837   // If all the node's predecessors are scheduled, this node is ready
00838   // to be scheduled. Ignore the special ExitSU node.
00839   if (SuccSU->NumPredsLeft == 0 && SuccSU != &ExitSU) {
00840     SuccSU->isAvailable = true;
00841     AvailableQueue->push(SuccSU);
00842   }
00843 }
00844 
00845 void ScheduleDAGRRList::ReleaseSuccessors(SUnit *SU) {
00846   // Top down: release successors
00847   for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
00848        I != E; ++I) {
00849     assert(!I->isAssignedRegDep() &&
00850            "The list-tdrr scheduler doesn't yet support physreg dependencies!");
00851 
00852     ReleaseSucc(SU, &*I);
00853   }
00854 }
00855 
00856 /// ScheduleNodeTopDown - Add the node to the schedule. Decrement the pending
00857 /// count of its successors. If a successor pending count is zero, add it to
00858 /// the Available queue.
00859 void ScheduleDAGRRList::ScheduleNodeTopDown(SUnit *SU, unsigned CurCycle) {
00860   DOUT << "*** Scheduling [" << CurCycle << "]: ";
00861   DEBUG(SU->dump(this));
00862 
00863   assert(CurCycle >= SU->getDepth() && "Node scheduled above its depth!");
00864   SU->setDepthToAtLeast(CurCycle);
00865   Sequence.push_back(SU);
00866 
00867   ReleaseSuccessors(SU);
00868   SU->isScheduled = true;
00869   AvailableQueue->ScheduledNode(SU);
00870 }
00871 
00872 /// ListScheduleTopDown - The main loop of list scheduling for top-down
00873 /// schedulers.
00874 void ScheduleDAGRRList::ListScheduleTopDown() {
00875   unsigned CurCycle = 0;
00876 
00877   // Release any successors of the special Entry node.
00878   ReleaseSuccessors(&EntrySU);
00879 
00880   // All leaves to Available queue.
00881   for (unsigned i = 0, e = SUnits.size(); i != e; ++i) {
00882     // It is available if it has no predecessors.
00883     if (SUnits[i].Preds.empty()) {
00884       AvailableQueue->push(&SUnits[i]);
00885       SUnits[i].isAvailable = true;
00886     }
00887   }
00888   
00889   // While Available queue is not empty, grab the node with the highest
00890   // priority. If it is not ready put it back.  Schedule the node.
00891   Sequence.reserve(SUnits.size());
00892   while (!AvailableQueue->empty()) {
00893     SUnit *CurSU = AvailableQueue->pop();
00894     
00895     if (CurSU)
00896       ScheduleNodeTopDown(CurSU, CurCycle);
00897     ++CurCycle;
00898   }
00899   
00900 #ifndef NDEBUG
00901   VerifySchedule(isBottomUp);
00902 #endif
00903 }
00904 
00905 
00906 //===----------------------------------------------------------------------===//
00907 //                RegReductionPriorityQueue Implementation
00908 //===----------------------------------------------------------------------===//
00909 //
00910 // This is a SchedulingPriorityQueue that schedules using Sethi Ullman numbers
00911 // to reduce register pressure.
00912 // 
00913 namespace {
00914   template<class SF>
00915   class RegReductionPriorityQueue;
00916   
00917   /// Sorting functions for the Available queue.
00918   struct bu_ls_rr_sort : public std::binary_function<SUnit*, SUnit*, bool> {
00919     RegReductionPriorityQueue<bu_ls_rr_sort> *SPQ;
00920     bu_ls_rr_sort(RegReductionPriorityQueue<bu_ls_rr_sort> *spq) : SPQ(spq) {}
00921     bu_ls_rr_sort(const bu_ls_rr_sort &RHS) : SPQ(RHS.SPQ) {}
00922     
00923     bool operator()(const SUnit* left, const SUnit* right) const;
00924   };
00925 
00926   struct td_ls_rr_sort : public std::binary_function<SUnit*, SUnit*, bool> {
00927     RegReductionPriorityQueue<td_ls_rr_sort> *SPQ;
00928     td_ls_rr_sort(RegReductionPriorityQueue<td_ls_rr_sort> *spq) : SPQ(spq) {}
00929     td_ls_rr_sort(const td_ls_rr_sort &RHS) : SPQ(RHS.SPQ) {}
00930     
00931     bool operator()(const SUnit* left, const SUnit* right) const;
00932   };
00933 }  // end anonymous namespace
00934 
00935 /// CalcNodeSethiUllmanNumber - Compute Sethi Ullman number.
00936 /// Smaller number is the higher priority.
00937 static unsigned
00938 CalcNodeSethiUllmanNumber(const SUnit *SU, std::vector<unsigned> &SUNumbers) {
00939   unsigned &SethiUllmanNumber = SUNumbers[SU->NodeNum];
00940   if (SethiUllmanNumber != 0)
00941     return SethiUllmanNumber;
00942 
00943   unsigned Extra = 0;
00944   for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
00945        I != E; ++I) {
00946     if (I->isCtrl()) continue;  // ignore chain preds
00947     SUnit *PredSU = I->getSUnit();
00948     unsigned PredSethiUllman = CalcNodeSethiUllmanNumber(PredSU, SUNumbers);
00949     if (PredSethiUllman > SethiUllmanNumber) {
00950       SethiUllmanNumber = PredSethiUllman;
00951       Extra = 0;
00952     } else if (PredSethiUllman == SethiUllmanNumber)
00953       ++Extra;
00954   }
00955 
00956   SethiUllmanNumber += Extra;
00957 
00958   if (SethiUllmanNumber == 0)
00959     SethiUllmanNumber = 1;
00960   
00961   return SethiUllmanNumber;
00962 }
00963 
00964 namespace {
00965   template<class SF>
00966   class VISIBILITY_HIDDEN RegReductionPriorityQueue
00967    : public SchedulingPriorityQueue {
00968     PriorityQueue<SUnit*, std::vector<SUnit*>, SF> Queue;
00969     unsigned currentQueueId;
00970 
00971   protected:
00972     // SUnits - The SUnits for the current graph.
00973     std::vector<SUnit> *SUnits;
00974     
00975     const TargetInstrInfo *TII;
00976     const TargetRegisterInfo *TRI;
00977     ScheduleDAGRRList *scheduleDAG;
00978 
00979     // SethiUllmanNumbers - The SethiUllman number for each node.
00980     std::vector<unsigned> SethiUllmanNumbers;
00981 
00982   public:
00983     RegReductionPriorityQueue(const TargetInstrInfo *tii,
00984                               const TargetRegisterInfo *tri) :
00985     Queue(SF(this)), currentQueueId(0),
00986     TII(tii), TRI(tri), scheduleDAG(NULL) {}
00987     
00988     void initNodes(std::vector<SUnit> &sunits) {
00989       SUnits = &sunits;
00990       // Add pseudo dependency edges for two-address nodes.
00991       AddPseudoTwoAddrDeps();
00992       // Reroute edges to nodes with multiple uses.
00993       PrescheduleNodesWithMultipleUses();
00994       // Calculate node priorities.
00995       CalculateSethiUllmanNumbers();
00996     }
00997 
00998     void addNode(const SUnit *SU) {
00999       unsigned SUSize = SethiUllmanNumbers.size();
01000       if (SUnits->size() > SUSize)
01001         SethiUllmanNumbers.resize(SUSize*2, 0);
01002       CalcNodeSethiUllmanNumber(SU, SethiUllmanNumbers);
01003     }
01004 
01005     void updateNode(const SUnit *SU) {
01006       SethiUllmanNumbers[SU->NodeNum] = 0;
01007       CalcNodeSethiUllmanNumber(SU, SethiUllmanNumbers);
01008     }
01009 
01010     void releaseState() {
01011       SUnits = 0;
01012       SethiUllmanNumbers.clear();
01013     }
01014 
01015     unsigned getNodePriority(const SUnit *SU) const {
01016       assert(SU->NodeNum < SethiUllmanNumbers.size());
01017       unsigned Opc = SU->getNode() ? SU->getNode()->getOpcode() : 0;
01018       if (Opc == ISD::TokenFactor || Opc == ISD::CopyToReg)
01019         // CopyToReg should be close to its uses to facilitate coalescing and
01020         // avoid spilling.
01021         return 0;
01022       if (Opc == TargetInstrInfo::EXTRACT_SUBREG ||
01023           Opc == TargetInstrInfo::SUBREG_TO_REG ||
01024           Opc == TargetInstrInfo::INSERT_SUBREG)
01025         // EXTRACT_SUBREG, INSERT_SUBREG, and SUBREG_TO_REG nodes should be
01026         // close to their uses to facilitate coalescing.
01027         return 0;
01028       if (SU->NumSuccs == 0 && SU->NumPreds != 0)
01029         // If SU does not have a register use, i.e. it doesn't produce a value
01030         // that would be consumed (e.g. store), then it terminates a chain of
01031         // computation.  Give it a large SethiUllman number so it will be
01032         // scheduled right before its predecessors that it doesn't lengthen
01033         // their live ranges.
01034         return 0xffff;
01035       if (SU->NumPreds == 0 && SU->NumSuccs != 0)
01036         // If SU does not have a register def, schedule it close to its uses
01037         // because it does not lengthen any live ranges.
01038         return 0;
01039       return SethiUllmanNumbers[SU->NodeNum];
01040     }
01041     
01042     unsigned size() const { return Queue.size(); }
01043 
01044     bool empty() const { return Queue.empty(); }
01045     
01046     void push(SUnit *U) {
01047       assert(!U->NodeQueueId && "Node in the queue already");
01048       U->NodeQueueId = ++currentQueueId;
01049       Queue.push(U);
01050     }
01051 
01052     void push_all(const std::vector<SUnit *> &Nodes) {
01053       for (unsigned i = 0, e = Nodes.size(); i != e; ++i)
01054         push(Nodes[i]);
01055     }
01056     
01057     SUnit *pop() {
01058       if (empty()) return NULL;
01059       SUnit *V = Queue.top();
01060       Queue.pop();
01061       V->NodeQueueId = 0;
01062       return V;
01063     }
01064 
01065     void remove(SUnit *SU) {
01066       assert(!Queue.empty() && "Queue is empty!");
01067       assert(SU->NodeQueueId != 0 && "Not in queue!");
01068       Queue.erase_one(SU);
01069       SU->NodeQueueId = 0;
01070     }
01071 
01072     void setScheduleDAG(ScheduleDAGRRList *scheduleDag) { 
01073       scheduleDAG = scheduleDag; 
01074     }
01075 
01076   protected:
01077     bool canClobber(const SUnit *SU, const SUnit *Op);
01078     void AddPseudoTwoAddrDeps();
01079     void PrescheduleNodesWithMultipleUses();
01080     void CalculateSethiUllmanNumbers();
01081   };
01082 
01083   typedef RegReductionPriorityQueue<bu_ls_rr_sort>
01084     BURegReductionPriorityQueue;
01085 
01086   typedef RegReductionPriorityQueue<td_ls_rr_sort>
01087     TDRegReductionPriorityQueue;
01088 }
01089 
01090 /// closestSucc - Returns the scheduled cycle of the successor which is
01091 /// closest to the current cycle.
01092 static unsigned closestSucc(const SUnit *SU) {
01093   unsigned MaxHeight = 0;
01094   for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
01095        I != E; ++I) {
01096     if (I->isCtrl()) continue;  // ignore chain succs
01097     unsigned Height = I->getSUnit()->getHeight();
01098     // If there are bunch of CopyToRegs stacked up, they should be considered
01099     // to be at the same position.
01100     if (I->getSUnit()->getNode() &&
01101         I->getSUnit()->getNode()->getOpcode() == ISD::CopyToReg)
01102       Height = closestSucc(I->getSUnit())+1;
01103     if (Height > MaxHeight)
01104       MaxHeight = Height;
01105   }
01106   return MaxHeight;
01107 }
01108 
01109 /// calcMaxScratches - Returns an cost estimate of the worse case requirement
01110 /// for scratch registers, i.e. number of data dependencies.
01111 static unsigned calcMaxScratches(const SUnit *SU) {
01112   unsigned Scratches = 0;
01113   for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
01114        I != E; ++I) {
01115     if (I->isCtrl()) continue;  // ignore chain preds
01116     Scratches++;
01117   }
01118   return Scratches;
01119 }
01120 
01121 // Bottom up
01122 bool bu_ls_rr_sort::operator()(const SUnit *left, const SUnit *right) const {
01123   unsigned LPriority = SPQ->getNodePriority(left);
01124   unsigned RPriority = SPQ->getNodePriority(right);
01125   if (LPriority != RPriority)
01126     return LPriority > RPriority;
01127 
01128   // Try schedule def + use closer when Sethi-Ullman numbers are the same.
01129   // e.g.
01130   // t1 = op t2, c1
01131   // t3 = op t4, c2
01132   //
01133   // and the following instructions are both ready.
01134   // t2 = op c3
01135   // t4 = op c4
01136   //
01137   // Then schedule t2 = op first.
01138   // i.e.
01139   // t4 = op c4
01140   // t2 = op c3
01141   // t1 = op t2, c1
01142   // t3 = op t4, c2
01143   //
01144   // This creates more short live intervals.
01145   unsigned LDist = closestSucc(left);
01146   unsigned RDist = closestSucc(right);
01147   if (LDist != RDist)
01148     return LDist < RDist;
01149 
01150   // How many registers becomes live when the node is scheduled.
01151   unsigned LScratch = calcMaxScratches(left);
01152   unsigned RScratch = calcMaxScratches(right);
01153   if (LScratch != RScratch)
01154     return LScratch > RScratch;
01155 
01156   if (left->getHeight() != right->getHeight())
01157     return left->getHeight() > right->getHeight();
01158   
01159   if (left->getDepth() != right->getDepth())
01160     return left->getDepth() < right->getDepth();
01161 
01162   assert(left->NodeQueueId && right->NodeQueueId && 
01163          "NodeQueueId cannot be zero");
01164   return (left->NodeQueueId > right->NodeQueueId);
01165 }
01166 
01167 template<class SF>
01168 bool
01169 RegReductionPriorityQueue<SF>::canClobber(const SUnit *SU, const SUnit *Op) {
01170   if (SU->isTwoAddress) {
01171     unsigned Opc = SU->getNode()->getMachineOpcode();
01172     const TargetInstrDesc &TID = TII->get(Opc);
01173     unsigned NumRes = TID.getNumDefs();
01174     unsigned NumOps = TID.getNumOperands() - NumRes;
01175     for (unsigned i = 0; i != NumOps; ++i) {
01176       if (TID.getOperandConstraint(i+NumRes, TOI::TIED_TO) != -1) {
01177         SDNode *DU = SU->getNode()->getOperand(i).getNode();
01178         if (DU->getNodeId() != -1 &&
01179             Op->OrigNode == &(*SUnits)[DU->getNodeId()])
01180           return true;
01181       }
01182     }
01183   }
01184   return false;
01185 }
01186 
01187 
01188 /// hasCopyToRegUse - Return true if SU has a value successor that is a
01189 /// CopyToReg node.
01190 static bool hasCopyToRegUse(const SUnit *SU) {
01191   for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
01192        I != E; ++I) {
01193     if (I->isCtrl()) continue;
01194     const SUnit *SuccSU = I->getSUnit();
01195     if (SuccSU->getNode() && SuccSU->getNode()->getOpcode() == ISD::CopyToReg)
01196       return true;
01197   }
01198   return false;
01199 }
01200 
01201 /// canClobberPhysRegDefs - True if SU would clobber one of SuccSU's
01202 /// physical register defs.
01203 static bool canClobberPhysRegDefs(const SUnit *SuccSU, const SUnit *SU,
01204                                   const TargetInstrInfo *TII,
01205                                   const TargetRegisterInfo *TRI) {
01206   SDNode *N = SuccSU->getNode();
01207   unsigned NumDefs = TII->get(N->getMachineOpcode()).getNumDefs();
01208   const unsigned *ImpDefs = TII->get(N->getMachineOpcode()).getImplicitDefs();
01209   assert(ImpDefs && "Caller should check hasPhysRegDefs");
01210   for (const SDNode *SUNode = SU->getNode(); SUNode;
01211        SUNode = SUNode->getFlaggedNode()) {
01212     if (!SUNode->isMachineOpcode())
01213       continue;
01214     const unsigned *SUImpDefs =
01215       TII->get(SUNode->getMachineOpcode()).getImplicitDefs();
01216     if (!SUImpDefs)
01217       return false;
01218     for (unsigned i = NumDefs, e = N->getNumValues(); i != e; ++i) {
01219       EVT VT = N->getValueType(i);
01220       if (VT == MVT::Flag || VT == MVT::Other)
01221         continue;
01222       if (!N->hasAnyUseOfValue(i))
01223         continue;
01224       unsigned Reg = ImpDefs[i - NumDefs];
01225       for (;*SUImpDefs; ++SUImpDefs) {
01226         unsigned SUReg = *SUImpDefs;
01227         if (TRI->regsOverlap(Reg, SUReg))
01228           return true;
01229       }
01230     }
01231   }
01232   return false;
01233 }
01234 
01235 /// PrescheduleNodesWithMultipleUses - Nodes with multiple uses
01236 /// are not handled well by the general register pressure reduction
01237 /// heuristics. When presented with code like this:
01238 ///
01239 ///      N
01240 ///    / |
01241 ///   /  |
01242 ///  U  store
01243 ///  |
01244 /// ...
01245 ///
01246 /// the heuristics tend to push the store up, but since the
01247 /// operand of the store has another use (U), this would increase
01248 /// the length of that other use (the U->N edge).
01249 ///
01250 /// This function transforms code like the above to route U's
01251 /// dependence through the store when possible, like this:
01252 ///
01253 ///      N
01254 ///      ||
01255 ///      ||
01256 ///     store
01257 ///       |
01258 ///       U
01259 ///       |
01260 ///      ...
01261 ///
01262 /// This results in the store being scheduled immediately
01263 /// after N, which shortens the U->N live range, reducing
01264 /// register pressure.
01265 ///
01266 template<class SF>
01267 void RegReductionPriorityQueue<SF>::PrescheduleNodesWithMultipleUses() {
01268   // Visit all the nodes in topological order, working top-down.
01269   for (unsigned i = 0, e = SUnits->size(); i != e; ++i) {
01270     SUnit *SU = &(*SUnits)[i];
01271     // For now, only look at nodes with no data successors, such as stores.
01272     // These are especially important, due to the heuristics in
01273     // getNodePriority for nodes with no data successors.
01274     if (SU->NumSuccs != 0)
01275       continue;
01276     // For now, only look at nodes with exactly one data predecessor.
01277     if (SU->NumPreds != 1)
01278       continue;
01279     // Avoid prescheduling copies to virtual registers, which don't behave
01280     // like other nodes from the perspective of scheduling heuristics.
01281     if (SDNode *N = SU->getNode())
01282       if (N->getOpcode() == ISD::CopyToReg &&
01283           TargetRegisterInfo::isVirtualRegister
01284             (cast<RegisterSDNode>(N->getOperand(1))->getReg()))
01285         continue;
01286 
01287     // Locate the single data predecessor.
01288     SUnit *PredSU = 0;
01289     for (SUnit::const_pred_iterator II = SU->Preds.begin(),
01290          EE = SU->Preds.end(); II != EE; ++II)
01291       if (!II->isCtrl()) {
01292         PredSU = II->getSUnit();
01293         break;
01294       }
01295     assert(PredSU);
01296 
01297     // Don't rewrite edges that carry physregs, because that requires additional
01298     // support infrastructure.
01299     if (PredSU->hasPhysRegDefs)
01300       continue;
01301     // Short-circuit the case where SU is PredSU's only data successor.
01302     if (PredSU->NumSuccs == 1)
01303       continue;
01304     // Avoid prescheduling to copies from virtual registers, which don't behave
01305     // like other nodes from the perspective of scheduling // heuristics.
01306     if (SDNode *N = SU->getNode())
01307       if (N->getOpcode() == ISD::CopyFromReg &&
01308           TargetRegisterInfo::isVirtualRegister
01309             (cast<RegisterSDNode>(N->getOperand(1))->getReg()))
01310         continue;
01311 
01312     // Perform checks on the successors of PredSU.
01313     for (SUnit::const_succ_iterator II = PredSU->Succs.begin(),
01314          EE = PredSU->Succs.end(); II != EE; ++II) {
01315       SUnit *PredSuccSU = II->getSUnit();
01316       if (PredSuccSU == SU) continue;
01317       // If PredSU has another successor with no data successors, for
01318       // now don't attempt to choose either over the other.
01319       if (PredSuccSU->NumSuccs == 0)
01320         goto outer_loop_continue;
01321       // Don't break physical register dependencies.
01322       if (SU->hasPhysRegClobbers && PredSuccSU->hasPhysRegDefs)
01323         if (canClobberPhysRegDefs(PredSuccSU, SU, TII, TRI))
01324           goto outer_loop_continue;
01325       // Don't introduce graph cycles.
01326       if (scheduleDAG->IsReachable(SU, PredSuccSU))
01327         goto outer_loop_continue;
01328     }
01329 
01330     // Ok, the transformation is safe and the heuristics suggest it is
01331     // profitable. Update the graph.
01332     DOUT << "Prescheduling SU # " << SU->NodeNum
01333          << " next to PredSU # " << PredSU->NodeNum
01334          << " to guide scheduling in the presence of multiple uses\n";
01335     for (unsigned i = 0; i != PredSU->Succs.size(); ++i) {
01336       SDep Edge = PredSU->Succs[i];
01337       assert(!Edge.isAssignedRegDep());
01338       SUnit *SuccSU = Edge.getSUnit();
01339       if (SuccSU != SU) {
01340         Edge.setSUnit(PredSU);
01341         scheduleDAG->RemovePred(SuccSU, Edge);
01342         scheduleDAG->AddPred(SU, Edge);
01343         Edge.setSUnit(SU);
01344         scheduleDAG->AddPred(SuccSU, Edge);
01345         --i;
01346       }
01347     }
01348   outer_loop_continue:;
01349   }
01350 }
01351 
01352 /// AddPseudoTwoAddrDeps - If two nodes share an operand and one of them uses
01353 /// it as a def&use operand. Add a pseudo control edge from it to the other
01354 /// node (if it won't create a cycle) so the two-address one will be scheduled
01355 /// first (lower in the schedule). If both nodes are two-address, favor the
01356 /// one that has a CopyToReg use (more likely to be a loop induction update).
01357 /// If both are two-address, but one is commutable while the other is not
01358 /// commutable, favor the one that's not commutable.
01359 template<class SF>
01360 void RegReductionPriorityQueue<SF>::AddPseudoTwoAddrDeps() {
01361   for (unsigned i = 0, e = SUnits->size(); i != e; ++i) {
01362     SUnit *SU = &(*SUnits)[i];
01363     if (!SU->isTwoAddress)
01364       continue;
01365 
01366     SDNode *Node = SU->getNode();
01367     if (!Node || !Node->isMachineOpcode() || SU->getNode()->getFlaggedNode())
01368       continue;
01369 
01370     unsigned Opc = Node->getMachineOpcode();
01371     const TargetInstrDesc &TID = TII->get(Opc);
01372     unsigned NumRes = TID.getNumDefs();
01373     unsigned NumOps = TID.getNumOperands() - NumRes;
01374     for (unsigned j = 0; j != NumOps; ++j) {
01375       if (TID.getOperandConstraint(j+NumRes, TOI::TIED_TO) == -1)
01376         continue;
01377       SDNode *DU = SU->getNode()->getOperand(j).getNode();
01378       if (DU->getNodeId() == -1)
01379         continue;
01380       const SUnit *DUSU = &(*SUnits)[DU->getNodeId()];
01381       if (!DUSU) continue;
01382       for (SUnit::const_succ_iterator I = DUSU->Succs.begin(),
01383            E = DUSU->Succs.end(); I != E; ++I) {
01384         if (I->isCtrl()) continue;
01385         SUnit *SuccSU = I->getSUnit();
01386         if (SuccSU == SU)
01387           continue;
01388         // Be conservative. Ignore if nodes aren't at roughly the same
01389         // depth and height.
01390         if (SuccSU->getHeight() < SU->getHeight() &&
01391             (SU->getHeight() - SuccSU->getHeight()) > 1)
01392           continue;
01393         // Skip past COPY_TO_REGCLASS nodes, so that the pseudo edge
01394         // constrains whatever is using the copy, instead of the copy
01395         // itself. In the case that the copy is coalesced, this
01396         // preserves the intent of the pseudo two-address heurietics.
01397         while (SuccSU->Succs.size() == 1 &&
01398                SuccSU->getNode()->isMachineOpcode() &&
01399                SuccSU->getNode()->getMachineOpcode() ==
01400                  TargetInstrInfo::COPY_TO_REGCLASS)
01401           SuccSU = SuccSU->Succs.front().getSUnit();
01402         // Don't constrain non-instruction nodes.
01403         if (!SuccSU->getNode() || !SuccSU->getNode()->isMachineOpcode())
01404           continue;
01405         // Don't constrain nodes with physical register defs if the
01406         // predecessor can clobber them.
01407         if (SuccSU->hasPhysRegDefs && SU->hasPhysRegClobbers) {
01408           if (canClobberPhysRegDefs(SuccSU, SU, TII, TRI))
01409             continue;
01410         }
01411         // Don't constrain EXTRACT_SUBREG, INSERT_SUBREG, and SUBREG_TO_REG;
01412         // these may be coalesced away. We want them close to their uses.
01413         unsigned SuccOpc = SuccSU->getNode()->getMachineOpcode();
01414         if (SuccOpc == TargetInstrInfo::EXTRACT_SUBREG ||
01415             SuccOpc == TargetInstrInfo::INSERT_SUBREG ||
01416             SuccOpc == TargetInstrInfo::SUBREG_TO_REG)
01417           continue;
01418         if ((!canClobber(SuccSU, DUSU) ||
01419              (hasCopyToRegUse(SU) && !hasCopyToRegUse(SuccSU)) ||
01420              (!SU->isCommutable && SuccSU->isCommutable)) &&
01421             !scheduleDAG->IsReachable(SuccSU, SU)) {
01422           DOUT << "Adding a pseudo-two-addr edge from SU # " << SU->NodeNum
01423                << " to SU #" << SuccSU->NodeNum << "\n";
01424           scheduleDAG->AddPred(SU, SDep(SuccSU, SDep::Order, /*Latency=*/0,
01425                                         /*Reg=*/0, /*isNormalMemory=*/false,
01426                                         /*isMustAlias=*/false,
01427                                         /*isArtificial=*/true));
01428         }
01429       }
01430     }
01431   }
01432 }
01433 
01434 /// CalculateSethiUllmanNumbers - Calculate Sethi-Ullman numbers of all
01435 /// scheduling units.
01436 template<class SF>
01437 void RegReductionPriorityQueue<SF>::CalculateSethiUllmanNumbers() {
01438   SethiUllmanNumbers.assign(SUnits->size(), 0);
01439   
01440   for (unsigned i = 0, e = SUnits->size(); i != e; ++i)
01441     CalcNodeSethiUllmanNumber(&(*SUnits)[i], SethiUllmanNumbers);
01442 }
01443 
01444 /// LimitedSumOfUnscheduledPredsOfSuccs - Compute the sum of the unscheduled
01445 /// predecessors of the successors of the SUnit SU. Stop when the provided
01446 /// limit is exceeded.
01447 static unsigned LimitedSumOfUnscheduledPredsOfSuccs(const SUnit *SU, 
01448                                                     unsigned Limit) {
01449   unsigned Sum = 0;
01450   for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
01451        I != E; ++I) {
01452     const SUnit *SuccSU = I->getSUnit();
01453     for (SUnit::const_pred_iterator II = SuccSU->Preds.begin(),
01454          EE = SuccSU->Preds.end(); II != EE; ++II) {
01455       SUnit *PredSU = II->getSUnit();
01456       if (!PredSU->isScheduled)
01457         if (++Sum > Limit)
01458           return Sum;
01459     }
01460   }
01461   return Sum;
01462 }
01463 
01464 
01465 // Top down
01466 bool td_ls_rr_sort::operator()(const SUnit *left, const SUnit *right) const {
01467   unsigned LPriority = SPQ->getNodePriority(left);
01468   unsigned RPriority = SPQ->getNodePriority(right);
01469   bool LIsTarget = left->getNode() && left->getNode()->isMachineOpcode();
01470   bool RIsTarget = right->getNode() && right->getNode()->isMachineOpcode();
01471   bool LIsFloater = LIsTarget && left->NumPreds == 0;
01472   bool RIsFloater = RIsTarget && right->NumPreds == 0;
01473   unsigned LBonus = (LimitedSumOfUnscheduledPredsOfSuccs(left,1) == 1) ? 2 : 0;
01474   unsigned RBonus = (LimitedSumOfUnscheduledPredsOfSuccs(right,1) == 1) ? 2 : 0;
01475 
01476   if (left->NumSuccs == 0 && right->NumSuccs != 0)
01477     return false;
01478   else if (left->NumSuccs != 0 && right->NumSuccs == 0)
01479     return true;
01480 
01481   if (LIsFloater)
01482     LBonus -= 2;
01483   if (RIsFloater)
01484     RBonus -= 2;
01485   if (left->NumSuccs == 1)
01486     LBonus += 2;
01487   if (right->NumSuccs == 1)
01488     RBonus += 2;
01489 
01490   if (LPriority+LBonus != RPriority+RBonus)
01491     return LPriority+LBonus < RPriority+RBonus;
01492 
01493   if (left->getDepth() != right->getDepth())
01494     return left->getDepth() < right->getDepth();
01495 
01496   if (left->NumSuccsLeft != right->NumSuccsLeft)
01497     return left->NumSuccsLeft > right->NumSuccsLeft;
01498 
01499   assert(left->NodeQueueId && right->NodeQueueId && 
01500          "NodeQueueId cannot be zero");
01501   return (left->NodeQueueId > right->NodeQueueId);
01502 }
01503 
01504 //===----------------------------------------------------------------------===//
01505 //                         Public Constructor Functions
01506 //===----------------------------------------------------------------------===//
01507 
01508 llvm::ScheduleDAGSDNodes *
01509 llvm::createBURRListDAGScheduler(SelectionDAGISel *IS, CodeGenOpt::Level) {
01510   const TargetMachine &TM = IS->TM;
01511   const TargetInstrInfo *TII = TM.getInstrInfo();
01512   const TargetRegisterInfo *TRI = TM.getRegisterInfo();
01513   
01514   BURegReductionPriorityQueue *PQ = new BURegReductionPriorityQueue(TII, TRI);
01515 
01516   ScheduleDAGRRList *SD =
01517     new ScheduleDAGRRList(*IS->MF, true, PQ);
01518   PQ->setScheduleDAG(SD);
01519   return SD;  
01520 }
01521 
01522 llvm::ScheduleDAGSDNodes *
01523 llvm::createTDRRListDAGScheduler(SelectionDAGISel *IS, CodeGenOpt::Level) {
01524   const TargetMachine &TM = IS->TM;
01525   const TargetInstrInfo *TII = TM.getInstrInfo();
01526   const TargetRegisterInfo *TRI = TM.getRegisterInfo();
01527   
01528   TDRegReductionPriorityQueue *PQ = new TDRegReductionPriorityQueue(TII, TRI);
01529 
01530   ScheduleDAGRRList *SD =
01531     new ScheduleDAGRRList(*IS->MF, false, PQ);
01532   PQ->setScheduleDAG(SD);
01533   return SD;
01534 }