LLVM API Documentation

ScheduleDAGList.cpp

Go to the documentation of this file.
00001 //===---- ScheduleDAGList.cpp - Implement a list scheduler for isel DAG ---===//
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 a top-down list scheduler, using standard algorithms.
00011 // The basic approach uses a priority queue of available nodes to schedule.
00012 // One at a time, nodes are taken from the priority queue (thus in priority
00013 // order), checked for legality to schedule, and emitted if legal.
00014 //
00015 // Nodes may not be legal to schedule either due to structural hazards (e.g.
00016 // pipeline or resource constraints) or because an input to the instruction has
00017 // not completed execution.
00018 //
00019 //===----------------------------------------------------------------------===//
00020 
00021 #define DEBUG_TYPE "pre-RA-sched"
00022 #include "ScheduleDAGSDNodes.h"
00023 #include "llvm/CodeGen/LatencyPriorityQueue.h"
00024 #include "llvm/CodeGen/ScheduleHazardRecognizer.h"
00025 #include "llvm/CodeGen/SchedulerRegistry.h"
00026 #include "llvm/CodeGen/SelectionDAGISel.h"
00027 #include "llvm/Target/TargetRegisterInfo.h"
00028 #include "llvm/Target/TargetData.h"
00029 #include "llvm/Target/TargetInstrInfo.h"
00030 #include "llvm/Support/Debug.h"
00031 #include "llvm/Support/Compiler.h"
00032 #include "llvm/Support/ErrorHandling.h"
00033 #include "llvm/ADT/PriorityQueue.h"
00034 #include "llvm/ADT/Statistic.h"
00035 #include <climits>
00036 using namespace llvm;
00037 
00038 STATISTIC(NumNoops , "Number of noops inserted");
00039 STATISTIC(NumStalls, "Number of pipeline stalls");
00040 
00041 static RegisterScheduler
00042   tdListDAGScheduler("list-td", "Top-down list scheduler",
00043                      createTDListDAGScheduler);
00044    
00045 namespace {
00046 //===----------------------------------------------------------------------===//
00047 /// ScheduleDAGList - The actual list scheduler implementation.  This supports
00048 /// top-down scheduling.
00049 ///
00050 class VISIBILITY_HIDDEN ScheduleDAGList : public ScheduleDAGSDNodes {
00051 private:
00052   /// AvailableQueue - The priority queue to use for the available SUnits.
00053   ///
00054   SchedulingPriorityQueue *AvailableQueue;
00055   
00056   /// PendingQueue - This contains all of the instructions whose operands have
00057   /// been issued, but their results are not ready yet (due to the latency of
00058   /// the operation).  Once the operands become available, the instruction is
00059   /// added to the AvailableQueue.
00060   std::vector<SUnit*> PendingQueue;
00061 
00062   /// HazardRec - The hazard recognizer to use.
00063   ScheduleHazardRecognizer *HazardRec;
00064 
00065 public:
00066   ScheduleDAGList(MachineFunction &mf,
00067                   SchedulingPriorityQueue *availqueue,
00068                   ScheduleHazardRecognizer *HR)
00069     : ScheduleDAGSDNodes(mf),
00070       AvailableQueue(availqueue), HazardRec(HR) {
00071     }
00072 
00073   ~ScheduleDAGList() {
00074     delete HazardRec;
00075     delete AvailableQueue;
00076   }
00077 
00078   void Schedule();
00079 
00080 private:
00081   void ReleaseSucc(SUnit *SU, const SDep &D);
00082   void ReleaseSuccessors(SUnit *SU);
00083   void ScheduleNodeTopDown(SUnit *SU, unsigned CurCycle);
00084   void ListScheduleTopDown();
00085 };
00086 }  // end anonymous namespace
00087 
00088 /// Schedule - Schedule the DAG using list scheduling.
00089 void ScheduleDAGList::Schedule() {
00090   DOUT << "********** List Scheduling **********\n";
00091   
00092   // Build the scheduling graph.
00093   BuildSchedGraph();
00094 
00095   AvailableQueue->initNodes(SUnits);
00096   
00097   ListScheduleTopDown();
00098   
00099   AvailableQueue->releaseState();
00100 }
00101 
00102 //===----------------------------------------------------------------------===//
00103 //  Top-Down Scheduling
00104 //===----------------------------------------------------------------------===//
00105 
00106 /// ReleaseSucc - Decrement the NumPredsLeft count of a successor. Add it to
00107 /// the PendingQueue if the count reaches zero. Also update its cycle bound.
00108 void ScheduleDAGList::ReleaseSucc(SUnit *SU, const SDep &D) {
00109   SUnit *SuccSU = D.getSUnit();
00110   --SuccSU->NumPredsLeft;
00111   
00112 #ifndef NDEBUG
00113   if (SuccSU->NumPredsLeft < 0) {
00114     cerr << "*** Scheduling failed! ***\n";
00115     SuccSU->dump(this);
00116     cerr << " has been released too many times!\n";
00117     llvm_unreachable(0);
00118   }
00119 #endif
00120   
00121   SuccSU->setDepthToAtLeast(SU->getDepth() + D.getLatency());
00122   
00123   // If all the node's predecessors are scheduled, this node is ready
00124   // to be scheduled. Ignore the special ExitSU node.
00125   if (SuccSU->NumPredsLeft == 0 && SuccSU != &ExitSU)
00126     PendingQueue.push_back(SuccSU);
00127 }
00128 
00129 void ScheduleDAGList::ReleaseSuccessors(SUnit *SU) {
00130   // Top down: release successors.
00131   for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
00132        I != E; ++I) {
00133     assert(!I->isAssignedRegDep() &&
00134            "The list-td scheduler doesn't yet support physreg dependencies!");
00135 
00136     ReleaseSucc(SU, *I);
00137   }
00138 }
00139 
00140 /// ScheduleNodeTopDown - Add the node to the schedule. Decrement the pending
00141 /// count of its successors. If a successor pending count is zero, add it to
00142 /// the Available queue.
00143 void ScheduleDAGList::ScheduleNodeTopDown(SUnit *SU, unsigned CurCycle) {
00144   DOUT << "*** Scheduling [" << CurCycle << "]: ";
00145   DEBUG(SU->dump(this));
00146   
00147   Sequence.push_back(SU);
00148   assert(CurCycle >= SU->getDepth() && "Node scheduled above its depth!");
00149   SU->setDepthToAtLeast(CurCycle);
00150 
00151   ReleaseSuccessors(SU);
00152   SU->isScheduled = true;
00153   AvailableQueue->ScheduledNode(SU);
00154 }
00155 
00156 /// ListScheduleTopDown - The main loop of list scheduling for top-down
00157 /// schedulers.
00158 void ScheduleDAGList::ListScheduleTopDown() {
00159   unsigned CurCycle = 0;
00160 
00161   // Release any successors of the special Entry node.
00162   ReleaseSuccessors(&EntrySU);
00163 
00164   // All leaves to Available queue.
00165   for (unsigned i = 0, e = SUnits.size(); i != e; ++i) {
00166     // It is available if it has no predecessors.
00167     if (SUnits[i].Preds.empty()) {
00168       AvailableQueue->push(&SUnits[i]);
00169       SUnits[i].isAvailable = true;
00170     }
00171   }
00172   
00173   // While Available queue is not empty, grab the node with the highest
00174   // priority. If it is not ready put it back.  Schedule the node.
00175   std::vector<SUnit*> NotReady;
00176   Sequence.reserve(SUnits.size());
00177   while (!AvailableQueue->empty() || !PendingQueue.empty()) {
00178     // Check to see if any of the pending instructions are ready to issue.  If
00179     // so, add them to the available queue.
00180     for (unsigned i = 0, e = PendingQueue.size(); i != e; ++i) {
00181       if (PendingQueue[i]->getDepth() == CurCycle) {
00182         AvailableQueue->push(PendingQueue[i]);
00183         PendingQueue[i]->isAvailable = true;
00184         PendingQueue[i] = PendingQueue.back();
00185         PendingQueue.pop_back();
00186         --i; --e;
00187       } else {
00188         assert(PendingQueue[i]->getDepth() > CurCycle && "Negative latency?");
00189       }
00190     }
00191     
00192     // If there are no instructions available, don't try to issue anything, and
00193     // don't advance the hazard recognizer.
00194     if (AvailableQueue->empty()) {
00195       ++CurCycle;
00196       continue;
00197     }
00198 
00199     SUnit *FoundSUnit = 0;
00200     
00201     bool HasNoopHazards = false;
00202     while (!AvailableQueue->empty()) {
00203       SUnit *CurSUnit = AvailableQueue->pop();
00204       
00205       ScheduleHazardRecognizer::HazardType HT =
00206         HazardRec->getHazardType(CurSUnit);
00207       if (HT == ScheduleHazardRecognizer::NoHazard) {
00208         FoundSUnit = CurSUnit;
00209         break;
00210       }
00211     
00212       // Remember if this is a noop hazard.
00213       HasNoopHazards |= HT == ScheduleHazardRecognizer::NoopHazard;
00214       
00215       NotReady.push_back(CurSUnit);
00216     }
00217     
00218     // Add the nodes that aren't ready back onto the available list.
00219     if (!NotReady.empty()) {
00220       AvailableQueue->push_all(NotReady);
00221       NotReady.clear();
00222     }
00223 
00224     // If we found a node to schedule, do it now.
00225     if (FoundSUnit) {
00226       ScheduleNodeTopDown(FoundSUnit, CurCycle);
00227       HazardRec->EmitInstruction(FoundSUnit);
00228 
00229       // If this is a pseudo-op node, we don't want to increment the current
00230       // cycle.
00231       if (FoundSUnit->Latency)  // Don't increment CurCycle for pseudo-ops!
00232         ++CurCycle;        
00233     } else if (!HasNoopHazards) {
00234       // Otherwise, we have a pipeline stall, but no other problem, just advance
00235       // the current cycle and try again.
00236       DOUT << "*** Advancing cycle, no work to do\n";
00237       HazardRec->AdvanceCycle();
00238       ++NumStalls;
00239       ++CurCycle;
00240     } else {
00241       // Otherwise, we have no instructions to issue and we have instructions
00242       // that will fault if we don't do this right.  This is the case for
00243       // processors without pipeline interlocks and other cases.
00244       DOUT << "*** Emitting noop\n";
00245       HazardRec->EmitNoop();
00246       Sequence.push_back(0);   // NULL here means noop
00247       ++NumNoops;
00248       ++CurCycle;
00249     }
00250   }
00251 
00252 #ifndef NDEBUG
00253   VerifySchedule(/*isBottomUp=*/false);
00254 #endif
00255 }
00256 
00257 //===----------------------------------------------------------------------===//
00258 //                         Public Constructor Functions
00259 //===----------------------------------------------------------------------===//
00260 
00261 /// createTDListDAGScheduler - This creates a top-down list scheduler with a
00262 /// new hazard recognizer. This scheduler takes ownership of the hazard
00263 /// recognizer and deletes it when done.
00264 ScheduleDAGSDNodes *
00265 llvm::createTDListDAGScheduler(SelectionDAGISel *IS, CodeGenOpt::Level) {
00266   return new ScheduleDAGList(*IS->MF,
00267                              new LatencyPriorityQueue(),
00268                              IS->CreateTargetHazardRecognizer());
00269 }