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/LatencyPriorityQueue.h" 23 #include "llvm/CodeGen/ResourcePriorityQueue.h" 24 #include "llvm/CodeGen/ScheduleHazardRecognizer.h" 25 #include "llvm/CodeGen/SchedulerRegistry.h" 26 #include "llvm/CodeGen/SelectionDAGISel.h" 27 #include "llvm/CodeGen/TargetInstrInfo.h" 28 #include "llvm/CodeGen/TargetRegisterInfo.h" 29 #include "llvm/CodeGen/TargetSubtargetInfo.h" 30 #include "llvm/IR/DataLayout.h" 31 #include "llvm/Support/Debug.h" 32 #include "llvm/Support/ErrorHandling.h" 33 #include "llvm/Support/raw_ostream.h" 34 #include <climits> 35 using namespace llvm; 36 37 #define DEBUG_TYPE "pre-RA-sched" 38 39 STATISTIC(NumNoops , "Number of noops inserted"); 40 STATISTIC(NumStalls, "Number of pipeline stalls"); 41 42 static RegisterScheduler 43 VLIWScheduler("vliw-td", "VLIW scheduler", 44 createVLIWDAGScheduler); 45 46 namespace { 47 //===----------------------------------------------------------------------===// 48 /// ScheduleDAGVLIW - The actual DFA list scheduler implementation. This 49 /// supports / top-down scheduling. 50 /// 51 class ScheduleDAGVLIW : public ScheduleDAGSDNodes { 52 private: 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 - AAResults for making memory reference queries. 67 AAResults *AA; 68 69 public: 70 ScheduleDAGVLIW(MachineFunction &mf, AAResults *aa, 71 SchedulingPriorityQueue *availqueue) 72 : ScheduleDAGSDNodes(mf), AvailableQueue(availqueue), AA(aa) { 73 const TargetSubtargetInfo &STI = mf.getSubtarget(); 74 HazardRec = STI.getInstrInfo()->CreateTargetHazardRecognizer(&STI, this); 75 } 76 77 ~ScheduleDAGVLIW() override { 78 delete HazardRec; 79 delete AvailableQueue; 80 } 81 82 void Schedule() override; 83 84 private: 85 void releaseSucc(SUnit *SU, const SDep &D); 86 void releaseSuccessors(SUnit *SU); 87 void scheduleNodeTopDown(SUnit *SU, unsigned CurCycle); 88 void listScheduleTopDown(); 89 }; 90 } // end anonymous namespace 91 92 /// Schedule - Schedule the DAG using list scheduling. 93 void ScheduleDAGVLIW::Schedule() { 94 LLVM_DEBUG(dbgs() << "********** List Scheduling " << printMBBReference(*BB) 95 << " '" << BB->getName() << "' **********\n"); 96 97 // Build the scheduling graph. 98 BuildSchedGraph(AA); 99 100 AvailableQueue->initNodes(SUnits); 101 102 listScheduleTopDown(); 103 104 AvailableQueue->releaseState(); 105 } 106 107 //===----------------------------------------------------------------------===// 108 // Top-Down Scheduling 109 //===----------------------------------------------------------------------===// 110 111 /// releaseSucc - Decrement the NumPredsLeft count of a successor. Add it to 112 /// the PendingQueue if the count reaches zero. Also update its cycle bound. 113 void ScheduleDAGVLIW::releaseSucc(SUnit *SU, const SDep &D) { 114 SUnit *SuccSU = D.getSUnit(); 115 116 #ifndef NDEBUG 117 if (SuccSU->NumPredsLeft == 0) { 118 dbgs() << "*** Scheduling failed! ***\n"; 119 dumpNode(*SuccSU); 120 dbgs() << " has been released too many times!\n"; 121 llvm_unreachable(nullptr); 122 } 123 #endif 124 assert(!D.isWeak() && "unexpected artificial DAG edge"); 125 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 137 void 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. 151 void ScheduleDAGVLIW::scheduleNodeTopDown(SUnit *SU, unsigned CurCycle) { 152 LLVM_DEBUG(dbgs() << "*** Scheduling [" << CurCycle << "]: "); 153 LLVM_DEBUG(dumpNode(*SU)); 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. 166 void 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(nullptr); 206 ++CurCycle; 207 continue; 208 } 209 210 SUnit *FoundSUnit = nullptr; 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 LLVM_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 LLVM_DEBUG(dbgs() << "*** Emitting noop\n"); 256 HazardRec->EmitNoop(); 257 Sequence.push_back(nullptr); // NULL here means noop 258 ++NumNoops; 259 ++CurCycle; 260 } 261 } 262 263 #ifndef NDEBUG 264 VerifyScheduledSequence(/*isBottomUp=*/false); 265 #endif 266 } 267 268 //===----------------------------------------------------------------------===// 269 // Public Constructor Functions 270 //===----------------------------------------------------------------------===// 271 272 /// createVLIWDAGScheduler - This creates a top-down list scheduler. 273 ScheduleDAGSDNodes * 274 llvm::createVLIWDAGScheduler(SelectionDAGISel *IS, CodeGenOpt::Level) { 275 return new ScheduleDAGVLIW(*IS->MF, IS->AA, new ResourcePriorityQueue(IS)); 276 } 277