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