LLVM API Documentation
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 }