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