ScheduleDAGVLIW.cpp revision ee498d3254b86bceb4f441741e9f442990647ce6
1//===- ScheduleDAGVLIW.cpp - SelectionDAG list scheduler for VLIW -*- C++ -*-=// 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 "pre-RA-sched" 22#include "ScheduleDAGSDNodes.h" 23#include "llvm/CodeGen/LatencyPriorityQueue.h" 24#include "llvm/CodeGen/ScheduleHazardRecognizer.h" 25#include "llvm/CodeGen/SchedulerRegistry.h" 26#include "llvm/CodeGen/SelectionDAGISel.h" 27#include "llvm/Target/TargetRegisterInfo.h" 28#include "llvm/Target/TargetData.h" 29#include "llvm/Target/TargetInstrInfo.h" 30#include "llvm/Support/Debug.h" 31#include "llvm/Support/ErrorHandling.h" 32#include "llvm/Support/raw_ostream.h" 33#include "llvm/ADT/Statistic.h" 34#include "llvm/CodeGen/ResourcePriorityQueue.h" 35#include <climits> 36using namespace llvm; 37 38STATISTIC(NumNoops , "Number of noops inserted"); 39STATISTIC(NumStalls, "Number of pipeline stalls"); 40 41static RegisterScheduler 42 VLIWScheduler("vliw-td", "VLIW scheduler", 43 createVLIWDAGScheduler); 44 45namespace { 46//===----------------------------------------------------------------------===// 47/// ScheduleDAGVLIW - The actual DFA list scheduler implementation. This 48/// supports / top-down scheduling. 49/// 50class ScheduleDAGVLIW : public ScheduleDAGSDNodes { 51private: 52 /// AvailableQueue - The priority queue to use for the available SUnits. 53 /// 54 SchedulingPriorityQueue *AvailableQueue; 55 56 /// PendingQueue - This contains all of the instructions whose operands have 57 /// been issued, but their results are not ready yet (due to the latency of 58 /// the operation). Once the operands become available, the instruction is 59 /// added to the AvailableQueue. 60 std::vector<SUnit*> PendingQueue; 61 62 /// HazardRec - The hazard recognizer to use. 63 ScheduleHazardRecognizer *HazardRec; 64 65 /// AA - AliasAnalysis for making memory reference queries. 66 AliasAnalysis *AA; 67 68public: 69 ScheduleDAGVLIW(MachineFunction &mf, 70 AliasAnalysis *aa, 71 SchedulingPriorityQueue *availqueue) 72 : ScheduleDAGSDNodes(mf), AvailableQueue(availqueue), AA(aa) { 73 74 const TargetMachine &tm = mf.getTarget(); 75 HazardRec = tm.getInstrInfo()->CreateTargetHazardRecognizer(&tm, this); 76 } 77 78 ~ScheduleDAGVLIW() { 79 delete HazardRec; 80 delete AvailableQueue; 81 } 82 83 void Schedule(); 84 85private: 86 void releaseSucc(SUnit *SU, const SDep &D); 87 void releaseSuccessors(SUnit *SU); 88 void scheduleNodeTopDown(SUnit *SU, unsigned CurCycle); 89 void listScheduleTopDown(); 90}; 91} // end anonymous namespace 92 93/// Schedule - Schedule the DAG using list scheduling. 94void ScheduleDAGVLIW::Schedule() { 95 DEBUG(dbgs() 96 << "********** List Scheduling BB#" << BB->getNumber() 97 << " '" << BB->getName() << "' **********\n"); 98 99 // Build the scheduling graph. 100 BuildSchedGraph(AA); 101 102 AvailableQueue->initNodes(SUnits); 103 104 listScheduleTopDown(); 105 106 AvailableQueue->releaseState(); 107} 108 109//===----------------------------------------------------------------------===// 110// Top-Down Scheduling 111//===----------------------------------------------------------------------===// 112 113/// releaseSucc - Decrement the NumPredsLeft count of a successor. Add it to 114/// the PendingQueue if the count reaches zero. Also update its cycle bound. 115void ScheduleDAGVLIW::releaseSucc(SUnit *SU, const SDep &D) { 116 SUnit *SuccSU = D.getSUnit(); 117 118#ifndef NDEBUG 119 if (SuccSU->NumPredsLeft == 0) { 120 dbgs() << "*** Scheduling failed! ***\n"; 121 SuccSU->dump(this); 122 dbgs() << " has been released too many times!\n"; 123 llvm_unreachable(0); 124 } 125#endif 126 --SuccSU->NumPredsLeft; 127 128 SuccSU->setDepthToAtLeast(SU->getDepth() + D.getLatency()); 129 130 // If all the node's predecessors are scheduled, this node is ready 131 // to be scheduled. Ignore the special ExitSU node. 132 if (SuccSU->NumPredsLeft == 0 && SuccSU != &ExitSU) { 133 PendingQueue.push_back(SuccSU); 134 } 135} 136 137void ScheduleDAGVLIW::releaseSuccessors(SUnit *SU) { 138 // Top down: release successors. 139 for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); 140 I != E; ++I) { 141 assert(!I->isAssignedRegDep() && 142 "The list-td scheduler doesn't yet support physreg dependencies!"); 143 144 releaseSucc(SU, *I); 145 } 146} 147 148/// scheduleNodeTopDown - Add the node to the schedule. Decrement the pending 149/// count of its successors. If a successor pending count is zero, add it to 150/// the Available queue. 151void ScheduleDAGVLIW::scheduleNodeTopDown(SUnit *SU, unsigned CurCycle) { 152 DEBUG(dbgs() << "*** Scheduling [" << CurCycle << "]: "); 153 DEBUG(SU->dump(this)); 154 155 Sequence.push_back(SU); 156 assert(CurCycle >= SU->getDepth() && "Node scheduled above its depth!"); 157 SU->setDepthToAtLeast(CurCycle); 158 159 releaseSuccessors(SU); 160 SU->isScheduled = true; 161 AvailableQueue->ScheduledNode(SU); 162} 163 164/// listScheduleTopDown - The main loop of list scheduling for top-down 165/// schedulers. 166void ScheduleDAGVLIW::listScheduleTopDown() { 167 unsigned CurCycle = 0; 168 169 // Release any successors of the special Entry node. 170 releaseSuccessors(&EntrySU); 171 172 // All leaves to AvailableQueue. 173 for (unsigned i = 0, e = SUnits.size(); i != e; ++i) { 174 // It is available if it has no predecessors. 175 if (SUnits[i].Preds.empty()) { 176 AvailableQueue->push(&SUnits[i]); 177 SUnits[i].isAvailable = true; 178 } 179 } 180 181 // While AvailableQueue is not empty, grab the node with the highest 182 // priority. If it is not ready put it back. Schedule the node. 183 std::vector<SUnit*> NotReady; 184 Sequence.reserve(SUnits.size()); 185 while (!AvailableQueue->empty() || !PendingQueue.empty()) { 186 // Check to see if any of the pending instructions are ready to issue. If 187 // so, add them to the available queue. 188 for (unsigned i = 0, e = PendingQueue.size(); i != e; ++i) { 189 if (PendingQueue[i]->getDepth() == CurCycle) { 190 AvailableQueue->push(PendingQueue[i]); 191 PendingQueue[i]->isAvailable = true; 192 PendingQueue[i] = PendingQueue.back(); 193 PendingQueue.pop_back(); 194 --i; --e; 195 } 196 else { 197 assert(PendingQueue[i]->getDepth() > CurCycle && "Negative latency?"); 198 } 199 } 200 201 // If there are no instructions available, don't try to issue anything, and 202 // don't advance the hazard recognizer. 203 if (AvailableQueue->empty()) { 204 // Reset DFA state. 205 AvailableQueue->ScheduledNode(0); 206 ++CurCycle; 207 continue; 208 } 209 210 SUnit *FoundSUnit = 0; 211 212 bool HasNoopHazards = false; 213 while (!AvailableQueue->empty()) { 214 SUnit *CurSUnit = AvailableQueue->pop(); 215 216 ScheduleHazardRecognizer::HazardType HT = 217 HazardRec->getHazardType(CurSUnit, 0/*no stalls*/); 218 if (HT == ScheduleHazardRecognizer::NoHazard) { 219 FoundSUnit = CurSUnit; 220 break; 221 } 222 223 // Remember if this is a noop hazard. 224 HasNoopHazards |= HT == ScheduleHazardRecognizer::NoopHazard; 225 226 NotReady.push_back(CurSUnit); 227 } 228 229 // Add the nodes that aren't ready back onto the available list. 230 if (!NotReady.empty()) { 231 AvailableQueue->push_all(NotReady); 232 NotReady.clear(); 233 } 234 235 // If we found a node to schedule, do it now. 236 if (FoundSUnit) { 237 scheduleNodeTopDown(FoundSUnit, CurCycle); 238 HazardRec->EmitInstruction(FoundSUnit); 239 240 // If this is a pseudo-op node, we don't want to increment the current 241 // cycle. 242 if (FoundSUnit->Latency) // Don't increment CurCycle for pseudo-ops! 243 ++CurCycle; 244 } else if (!HasNoopHazards) { 245 // Otherwise, we have a pipeline stall, but no other problem, just advance 246 // the current cycle and try again. 247 DEBUG(dbgs() << "*** Advancing cycle, no work to do\n"); 248 HazardRec->AdvanceCycle(); 249 ++NumStalls; 250 ++CurCycle; 251 } else { 252 // Otherwise, we have no instructions to issue and we have instructions 253 // that will fault if we don't do this right. This is the case for 254 // processors without pipeline interlocks and other cases. 255 DEBUG(dbgs() << "*** Emitting noop\n"); 256 HazardRec->EmitNoop(); 257 Sequence.push_back(0); // NULL here means noop 258 ++NumNoops; 259 ++CurCycle; 260 } 261 } 262 263#ifndef NDEBUG 264 VerifySchedule(/*isBottomUp=*/false); 265#endif 266} 267 268//===----------------------------------------------------------------------===// 269// Public Constructor Functions 270//===----------------------------------------------------------------------===// 271 272/// createVLIWDAGScheduler - This creates a top-down list scheduler. 273ScheduleDAGSDNodes * 274llvm::createVLIWDAGScheduler(SelectionDAGISel *IS, CodeGenOpt::Level) { 275 return new ScheduleDAGVLIW(*IS->MF, IS->AA, new ResourcePriorityQueue(IS)); 276} 277