PostRASchedulerList.cpp revision d27a0e058661cece449251fef2f9d495f336e85f
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" 30using namespace llvm; 31 32STATISTIC(NumStalls, "Number of pipeline stalls"); 33 34namespace { 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 85bool 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. 105void 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. 124void 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. 157void 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. 175void 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 251FunctionPass *llvm::createPostRAScheduler() { 252 return new PostRAScheduler(); 253} 254