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 "llvm/CodeGen/SchedulerRegistry.h" 23#include "ScheduleDAGSDNodes.h" 24#include "llvm/ADT/Statistic.h" 25#include "llvm/CodeGen/LatencyPriorityQueue.h" 26#include "llvm/CodeGen/ResourcePriorityQueue.h" 27#include "llvm/CodeGen/ScheduleHazardRecognizer.h" 28#include "llvm/CodeGen/SelectionDAGISel.h" 29#include "llvm/IR/DataLayout.h" 30#include "llvm/Support/Debug.h" 31#include "llvm/Support/ErrorHandling.h" 32#include "llvm/Support/raw_ostream.h" 33#include "llvm/Target/TargetInstrInfo.h" 34#include "llvm/Target/TargetRegisterInfo.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 assert(!D.isWeak() && "unexpected artificial DAG edge"); 127 128 --SuccSU->NumPredsLeft; 129 130 SuccSU->setDepthToAtLeast(SU->getDepth() + D.getLatency()); 131 132 // If all the node's predecessors are scheduled, this node is ready 133 // to be scheduled. Ignore the special ExitSU node. 134 if (SuccSU->NumPredsLeft == 0 && SuccSU != &ExitSU) { 135 PendingQueue.push_back(SuccSU); 136 } 137} 138 139void ScheduleDAGVLIW::releaseSuccessors(SUnit *SU) { 140 // Top down: release successors. 141 for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); 142 I != E; ++I) { 143 assert(!I->isAssignedRegDep() && 144 "The list-td scheduler doesn't yet support physreg dependencies!"); 145 146 releaseSucc(SU, *I); 147 } 148} 149 150/// scheduleNodeTopDown - Add the node to the schedule. Decrement the pending 151/// count of its successors. If a successor pending count is zero, add it to 152/// the Available queue. 153void ScheduleDAGVLIW::scheduleNodeTopDown(SUnit *SU, unsigned CurCycle) { 154 DEBUG(dbgs() << "*** Scheduling [" << CurCycle << "]: "); 155 DEBUG(SU->dump(this)); 156 157 Sequence.push_back(SU); 158 assert(CurCycle >= SU->getDepth() && "Node scheduled above its depth!"); 159 SU->setDepthToAtLeast(CurCycle); 160 161 releaseSuccessors(SU); 162 SU->isScheduled = true; 163 AvailableQueue->scheduledNode(SU); 164} 165 166/// listScheduleTopDown - The main loop of list scheduling for top-down 167/// schedulers. 168void ScheduleDAGVLIW::listScheduleTopDown() { 169 unsigned CurCycle = 0; 170 171 // Release any successors of the special Entry node. 172 releaseSuccessors(&EntrySU); 173 174 // All leaves to AvailableQueue. 175 for (unsigned i = 0, e = SUnits.size(); i != e; ++i) { 176 // It is available if it has no predecessors. 177 if (SUnits[i].Preds.empty()) { 178 AvailableQueue->push(&SUnits[i]); 179 SUnits[i].isAvailable = true; 180 } 181 } 182 183 // While AvailableQueue is not empty, grab the node with the highest 184 // priority. If it is not ready put it back. Schedule the node. 185 std::vector<SUnit*> NotReady; 186 Sequence.reserve(SUnits.size()); 187 while (!AvailableQueue->empty() || !PendingQueue.empty()) { 188 // Check to see if any of the pending instructions are ready to issue. If 189 // so, add them to the available queue. 190 for (unsigned i = 0, e = PendingQueue.size(); i != e; ++i) { 191 if (PendingQueue[i]->getDepth() == CurCycle) { 192 AvailableQueue->push(PendingQueue[i]); 193 PendingQueue[i]->isAvailable = true; 194 PendingQueue[i] = PendingQueue.back(); 195 PendingQueue.pop_back(); 196 --i; --e; 197 } 198 else { 199 assert(PendingQueue[i]->getDepth() > CurCycle && "Negative latency?"); 200 } 201 } 202 203 // If there are no instructions available, don't try to issue anything, and 204 // don't advance the hazard recognizer. 205 if (AvailableQueue->empty()) { 206 // Reset DFA state. 207 AvailableQueue->scheduledNode(0); 208 ++CurCycle; 209 continue; 210 } 211 212 SUnit *FoundSUnit = 0; 213 214 bool HasNoopHazards = false; 215 while (!AvailableQueue->empty()) { 216 SUnit *CurSUnit = AvailableQueue->pop(); 217 218 ScheduleHazardRecognizer::HazardType HT = 219 HazardRec->getHazardType(CurSUnit, 0/*no stalls*/); 220 if (HT == ScheduleHazardRecognizer::NoHazard) { 221 FoundSUnit = CurSUnit; 222 break; 223 } 224 225 // Remember if this is a noop hazard. 226 HasNoopHazards |= HT == ScheduleHazardRecognizer::NoopHazard; 227 228 NotReady.push_back(CurSUnit); 229 } 230 231 // Add the nodes that aren't ready back onto the available list. 232 if (!NotReady.empty()) { 233 AvailableQueue->push_all(NotReady); 234 NotReady.clear(); 235 } 236 237 // If we found a node to schedule, do it now. 238 if (FoundSUnit) { 239 scheduleNodeTopDown(FoundSUnit, CurCycle); 240 HazardRec->EmitInstruction(FoundSUnit); 241 242 // If this is a pseudo-op node, we don't want to increment the current 243 // cycle. 244 if (FoundSUnit->Latency) // Don't increment CurCycle for pseudo-ops! 245 ++CurCycle; 246 } else if (!HasNoopHazards) { 247 // Otherwise, we have a pipeline stall, but no other problem, just advance 248 // the current cycle and try again. 249 DEBUG(dbgs() << "*** Advancing cycle, no work to do\n"); 250 HazardRec->AdvanceCycle(); 251 ++NumStalls; 252 ++CurCycle; 253 } else { 254 // Otherwise, we have no instructions to issue and we have instructions 255 // that will fault if we don't do this right. This is the case for 256 // processors without pipeline interlocks and other cases. 257 DEBUG(dbgs() << "*** Emitting noop\n"); 258 HazardRec->EmitNoop(); 259 Sequence.push_back(0); // NULL here means noop 260 ++NumNoops; 261 ++CurCycle; 262 } 263 } 264 265#ifndef NDEBUG 266 VerifyScheduledSequence(/*isBottomUp=*/false); 267#endif 268} 269 270//===----------------------------------------------------------------------===// 271// Public Constructor Functions 272//===----------------------------------------------------------------------===// 273 274/// createVLIWDAGScheduler - This creates a top-down list scheduler. 275ScheduleDAGSDNodes * 276llvm::createVLIWDAGScheduler(SelectionDAGISel *IS, CodeGenOpt::Level) { 277 return new ScheduleDAGVLIW(*IS->MF, IS->AA, new ResourcePriorityQueue(IS)); 278} 279