lib/CodeGen/PostRASchedulerList.cpp

   1 //===----- SchedulePostRAList.cpp - list scheduler ------------------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This implements a top-down list scheduler, using standard algorithms.
  11 // The basic approach uses a priority queue of available nodes to schedule.
  12 // One at a time, nodes are taken from the priority queue (thus in priority
  13 // order), checked for legality to schedule, and emitted if legal.
  14 //
  15 // Nodes may not be legal to schedule either due to structural hazards (e.g.
  16 // pipeline or resource constraints) or because an input to the instruction has
  17 // not completed execution.
  18 //
  19 //===----------------------------------------------------------------------===//
  20
  21 #define DEBUG_TYPE "post-RA-sched"
  22 #include "llvm/CodeGen/Passes.h"
  23 #include "llvm/CodeGen/ScheduleDAGInstrs.h"
  24 #include "llvm/CodeGen/LatencyPriorityQueue.h"
  25 #include "llvm/CodeGen/SchedulerRegistry.h"
  26 #include "llvm/CodeGen/MachineFunctionPass.h"
  27 #include "llvm/Support/Compiler.h"
  28 #include "llvm/Support/Debug.h"
  29 #include "llvm/ADT/Statistic.h"
  30 using namespace llvm;
  31
  32 STATISTIC(NumStalls, "Number of pipeline stalls");
  33
  34 namespace {
  35   class VISIBILITY_HIDDEN PostRAScheduler : public MachineFunctionPass {
  36   public:
  37     static char ID;
  38     PostRAScheduler() : MachineFunctionPass(&ID) {}
  39   private:
  40     MachineFunction *MF;
  41     const TargetMachine *TM;
  42   public:
  43     const char *getPassName() const {
  44       return "Post RA top-down list latency scheduler (STUB)";
  45     }
  46
  47     bool runOnMachineFunction(MachineFunction &Fn);
  48   };
  49   char PostRAScheduler::ID = 0;
  50
  51   class VISIBILITY_HIDDEN SchedulePostRATDList : public ScheduleDAGInstrs {
  52   public:
  53     SchedulePostRATDList(MachineBasicBlock *mbb, const TargetMachine &tm)
  54       : ScheduleDAGInstrs(mbb, tm) {}
  55   private:
  56     MachineFunction *MF;
  57     const TargetMachine *TM;
  58
  59     /// AvailableQueue - The priority queue to use for the available SUnits.
  60     ///
  61     LatencyPriorityQueue AvailableQueue;
  62
  63     /// PendingQueue - This contains all of the instructions whose operands have
  64     /// been issued, but their results are not ready yet (due to the latency of
  65     /// the operation).  Once the operands becomes available, the instruction is
  66     /// added to the AvailableQueue.
  67     std::vector<SUnit*> PendingQueue;
  68
  69   public:
  70     const char *getPassName() const {
  71       return "Post RA top-down list latency scheduler (STUB)";
  72     }
  73
  74     bool runOnMachineFunction(MachineFunction &Fn);
  75
  76     void Schedule();
  77
  78   private:
  79     void ReleaseSucc(SUnit *SU, SUnit *SuccSU, bool isChain);
  80     void ScheduleNodeTopDown(SUnit *SU, unsigned CurCycle);
  81     void ListScheduleTopDown();
  82   };
  83 }
  84
  85 bool PostRAScheduler::runOnMachineFunction(MachineFunction &Fn) {
  86   DOUT << "PostRAScheduler\n";
  87   MF = &Fn;
  88   TM = &MF->getTarget();
  89
  90   // Loop over all of the basic blocks
  91   for (MachineFunction::iterator MBB = Fn.begin(), MBBe = Fn.end();
  92        MBB != MBBe; ++MBB) {
  93
  94     SchedulePostRATDList Scheduler(MBB, *TM);
  95
  96     Scheduler.Run();
  97
  98     Scheduler.EmitSchedule();
  99   }
 100
 101   return true;
 102 }
 103
 104 /// Schedule - Schedule the DAG using list scheduling.
 105 void SchedulePostRATDList::Schedule() {
 106   DOUT << "********** List Scheduling **********\n";
 107
 108   // Build scheduling units.
 109   BuildSchedUnits();
 110
 111   AvailableQueue.initNodes(SUnits);
 112
 113   ListScheduleTopDown();
 114
 115   AvailableQueue.releaseState();
 116 }
 117
 118 //===----------------------------------------------------------------------===//
 119 //  Top-Down Scheduling
 120 //===----------------------------------------------------------------------===//
 121
 122 /// ReleaseSucc - Decrement the NumPredsLeft count of a successor. Add it to
 123 /// the PendingQueue if the count reaches zero. Also update its cycle bound.
 124 void SchedulePostRATDList::ReleaseSucc(SUnit *SU, SUnit *SuccSU, bool isChain) {
 125   --SuccSU->NumPredsLeft;
 126
 127 #ifndef NDEBUG
 128   if (SuccSU->NumPredsLeft < 0) {
 129     cerr << "*** Scheduling failed! ***\n";
 130     SuccSU->dump(this);
 131     cerr << " has been released too many times!\n";
 132     assert(0);
 133   }
 134 #endif
 135
 136   // Compute how many cycles it will be before this actually becomes
 137   // available.  This is the max of the start time of all predecessors plus
 138   // their latencies.
 139   // If this is a token edge, we don't need to wait for the latency of the
 140   // preceeding instruction (e.g. a long-latency load) unless there is also
 141   // some other data dependence.
 142   unsigned PredDoneCycle = SU->Cycle;
 143   if (!isChain)
 144     PredDoneCycle += SU->Latency;
 145   else if (SU->Latency)
 146     PredDoneCycle += 1;
 147   SuccSU->CycleBound = std::max(SuccSU->CycleBound, PredDoneCycle);
 148
 149   if (SuccSU->NumPredsLeft == 0) {
 150     PendingQueue.push_back(SuccSU);
 151   }
 152 }
 153
 154 /// ScheduleNodeTopDown - Add the node to the schedule. Decrement the pending
 155 /// count of its successors. If a successor pending count is zero, add it to
 156 /// the Available queue.
 157 void SchedulePostRATDList::ScheduleNodeTopDown(SUnit *SU, unsigned CurCycle) {
 158   DOUT << "*** Scheduling [" << CurCycle << "]: ";
 159   DEBUG(SU->dump(this));
 160
 161   Sequence.push_back(SU);
 162   SU->Cycle = CurCycle;
 163
 164   // Top down: release successors.
 165   for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
 166        I != E; ++I)
 167     ReleaseSucc(SU, I->Dep, I->isCtrl);
 168
 169   SU->isScheduled = true;
 170   AvailableQueue.ScheduledNode(SU);
 171 }
 172
 173 /// ListScheduleTopDown - The main loop of list scheduling for top-down
 174 /// schedulers.
 175 void SchedulePostRATDList::ListScheduleTopDown() {
 176   unsigned CurCycle = 0;
 177
 178   // All leaves to Available queue.
 179   for (unsigned i = 0, e = SUnits.size(); i != e; ++i) {
 180     // It is available if it has no predecessors.
 181     if (SUnits[i].Preds.empty()) {
 182       AvailableQueue.push(&SUnits[i]);
 183       SUnits[i].isAvailable = true;
 184     }
 185   }
 186
 187   // While Available queue is not empty, grab the node with the highest
 188   // priority. If it is not ready put it back.  Schedule the node.
 189   Sequence.reserve(SUnits.size());
 190   while (!AvailableQueue.empty() || !PendingQueue.empty()) {
 191     // Check to see if any of the pending instructions are ready to issue.  If
 192     // so, add them to the available queue.
 193     for (unsigned i = 0, e = PendingQueue.size(); i != e; ++i) {
 194       if (PendingQueue[i]->CycleBound == CurCycle) {
 195         AvailableQueue.push(PendingQueue[i]);
 196         PendingQueue[i]->isAvailable = true;
 197         PendingQueue[i] = PendingQueue.back();
 198         PendingQueue.pop_back();
 199         --i; --e;
 200       } else {
 201         assert(PendingQueue[i]->CycleBound > CurCycle && "Negative latency?");
 202       }
 203     }
 204
 205     // If there are no instructions available, don't try to issue anything, and
 206     // don't advance the hazard recognizer.
 207     if (AvailableQueue.empty()) {
 208       ++CurCycle;
 209       continue;
 210     }
 211
 212     SUnit *FoundSUnit = AvailableQueue.pop();
 213
 214     // If we found a node to schedule, do it now.
 215     if (FoundSUnit) {
 216       ScheduleNodeTopDown(FoundSUnit, CurCycle);
 217
 218       // If this is a pseudo-op node, we don't want to increment the current
 219       // cycle.
 220       if (FoundSUnit->Latency)  // Don't increment CurCycle for pseudo-ops!
 221         ++CurCycle;
 222     } else {
 223       // Otherwise, we have a pipeline stall, but no other problem, just advance
 224       // the current cycle and try again.
 225       DOUT << "*** Advancing cycle, no work to do\n";
 226       ++NumStalls;
 227       ++CurCycle;
 228     }
 229   }
 230
 231 #ifndef NDEBUG
 232   // Verify that all SUnits were scheduled.
 233   bool AnyNotSched = false;
 234   for (unsigned i = 0, e = SUnits.size(); i != e; ++i) {
 235     if (SUnits[i].NumPredsLeft != 0) {
 236       if (!AnyNotSched)
 237         cerr << "*** List scheduling failed! ***\n";
 238       SUnits[i].dump(this);
 239       cerr << "has not been scheduled!\n";
 240       AnyNotSched = true;
 241     }
 242   }
 243   assert(!AnyNotSched);
 244 #endif
 245 }
 246
 247 //===----------------------------------------------------------------------===//
 248 //                         Public Constructor Functions
 249 //===----------------------------------------------------------------------===//
 250
 251 FunctionPass *llvm::createPostRAScheduler() {
 252   return new PostRAScheduler();
 253 }