ScheduleDAGVLIW.cpp revision dce4a407a24b04eebc6a376f8e62b41aaa7b071f
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(&tm, this); 77 } 78 79 ~ScheduleDAGVLIW() { 80 delete HazardRec; 81 delete AvailableQueue; 82 } 83 84 void Schedule() override; 85 86private: 87 void releaseSucc(SUnit *SU, const SDep &D); 88 void releaseSuccessors(SUnit *SU); 89 void scheduleNodeTopDown(SUnit *SU, unsigned CurCycle); 90 void listScheduleTopDown(); 91}; 92} // end anonymous namespace 93 94/// Schedule - Schedule the DAG using list scheduling. 95void ScheduleDAGVLIW::Schedule() { 96 DEBUG(dbgs() 97 << "********** List Scheduling BB#" << BB->getNumber() 98 << " '" << BB->getName() << "' **********\n"); 99 100 // Build the scheduling graph. 101 BuildSchedGraph(AA); 102 103 AvailableQueue->initNodes(SUnits); 104 105 listScheduleTopDown(); 106 107 AvailableQueue->releaseState(); 108} 109 110//===----------------------------------------------------------------------===// 111// Top-Down Scheduling 112//===----------------------------------------------------------------------===// 113 114/// releaseSucc - Decrement the NumPredsLeft count of a successor. Add it to 115/// the PendingQueue if the count reaches zero. Also update its cycle bound. 116void ScheduleDAGVLIW::releaseSucc(SUnit *SU, const SDep &D) { 117 SUnit *SuccSU = D.getSUnit(); 118 119#ifndef NDEBUG 120 if (SuccSU->NumPredsLeft == 0) { 121 dbgs() << "*** Scheduling failed! ***\n"; 122 SuccSU->dump(this); 123 dbgs() << " has been released too many times!\n"; 124 llvm_unreachable(nullptr); 125 } 126#endif 127 assert(!D.isWeak() && "unexpected artificial DAG edge"); 128 129 --SuccSU->NumPredsLeft; 130 131 SuccSU->setDepthToAtLeast(SU->getDepth() + D.getLatency()); 132 133 // If all the node's predecessors are scheduled, this node is ready 134 // to be scheduled. Ignore the special ExitSU node. 135 if (SuccSU->NumPredsLeft == 0 && SuccSU != &ExitSU) { 136 PendingQueue.push_back(SuccSU); 137 } 138} 139 140void ScheduleDAGVLIW::releaseSuccessors(SUnit *SU) { 141 // Top down: release successors. 142 for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); 143 I != E; ++I) { 144 assert(!I->isAssignedRegDep() && 145 "The list-td scheduler doesn't yet support physreg dependencies!"); 146 147 releaseSucc(SU, *I); 148 } 149} 150 151/// scheduleNodeTopDown - Add the node to the schedule. Decrement the pending 152/// count of its successors. If a successor pending count is zero, add it to 153/// the Available queue. 154void ScheduleDAGVLIW::scheduleNodeTopDown(SUnit *SU, unsigned CurCycle) { 155 DEBUG(dbgs() << "*** Scheduling [" << CurCycle << "]: "); 156 DEBUG(SU->dump(this)); 157 158 Sequence.push_back(SU); 159 assert(CurCycle >= SU->getDepth() && "Node scheduled above its depth!"); 160 SU->setDepthToAtLeast(CurCycle); 161 162 releaseSuccessors(SU); 163 SU->isScheduled = true; 164 AvailableQueue->scheduledNode(SU); 165} 166 167/// listScheduleTopDown - The main loop of list scheduling for top-down 168/// schedulers. 169void ScheduleDAGVLIW::listScheduleTopDown() { 170 unsigned CurCycle = 0; 171 172 // Release any successors of the special Entry node. 173 releaseSuccessors(&EntrySU); 174 175 // All leaves to AvailableQueue. 176 for (unsigned i = 0, e = SUnits.size(); i != e; ++i) { 177 // It is available if it has no predecessors. 178 if (SUnits[i].Preds.empty()) { 179 AvailableQueue->push(&SUnits[i]); 180 SUnits[i].isAvailable = true; 181 } 182 } 183 184 // While AvailableQueue is not empty, grab the node with the highest 185 // priority. If it is not ready put it back. Schedule the node. 186 std::vector<SUnit*> NotReady; 187 Sequence.reserve(SUnits.size()); 188 while (!AvailableQueue->empty() || !PendingQueue.empty()) { 189 // Check to see if any of the pending instructions are ready to issue. If 190 // so, add them to the available queue. 191 for (unsigned i = 0, e = PendingQueue.size(); i != e; ++i) { 192 if (PendingQueue[i]->getDepth() == CurCycle) { 193 AvailableQueue->push(PendingQueue[i]); 194 PendingQueue[i]->isAvailable = true; 195 PendingQueue[i] = PendingQueue.back(); 196 PendingQueue.pop_back(); 197 --i; --e; 198 } 199 else { 200 assert(PendingQueue[i]->getDepth() > CurCycle && "Negative latency?"); 201 } 202 } 203 204 // If there are no instructions available, don't try to issue anything, and 205 // don't advance the hazard recognizer. 206 if (AvailableQueue->empty()) { 207 // Reset DFA state. 208 AvailableQueue->scheduledNode(nullptr); 209 ++CurCycle; 210 continue; 211 } 212 213 SUnit *FoundSUnit = nullptr; 214 215 bool HasNoopHazards = false; 216 while (!AvailableQueue->empty()) { 217 SUnit *CurSUnit = AvailableQueue->pop(); 218 219 ScheduleHazardRecognizer::HazardType HT = 220 HazardRec->getHazardType(CurSUnit, 0/*no stalls*/); 221 if (HT == ScheduleHazardRecognizer::NoHazard) { 222 FoundSUnit = CurSUnit; 223 break; 224 } 225 226 // Remember if this is a noop hazard. 227 HasNoopHazards |= HT == ScheduleHazardRecognizer::NoopHazard; 228 229 NotReady.push_back(CurSUnit); 230 } 231 232 // Add the nodes that aren't ready back onto the available list. 233 if (!NotReady.empty()) { 234 AvailableQueue->push_all(NotReady); 235 NotReady.clear(); 236 } 237 238 // If we found a node to schedule, do it now. 239 if (FoundSUnit) { 240 scheduleNodeTopDown(FoundSUnit, CurCycle); 241 HazardRec->EmitInstruction(FoundSUnit); 242 243 // If this is a pseudo-op node, we don't want to increment the current 244 // cycle. 245 if (FoundSUnit->Latency) // Don't increment CurCycle for pseudo-ops! 246 ++CurCycle; 247 } else if (!HasNoopHazards) { 248 // Otherwise, we have a pipeline stall, but no other problem, just advance 249 // the current cycle and try again. 250 DEBUG(dbgs() << "*** Advancing cycle, no work to do\n"); 251 HazardRec->AdvanceCycle(); 252 ++NumStalls; 253 ++CurCycle; 254 } else { 255 // Otherwise, we have no instructions to issue and we have instructions 256 // that will fault if we don't do this right. This is the case for 257 // processors without pipeline interlocks and other cases. 258 DEBUG(dbgs() << "*** Emitting noop\n"); 259 HazardRec->EmitNoop(); 260 Sequence.push_back(nullptr); // NULL here means noop 261 ++NumNoops; 262 ++CurCycle; 263 } 264 } 265 266#ifndef NDEBUG 267 VerifyScheduledSequence(/*isBottomUp=*/false); 268#endif 269} 270 271//===----------------------------------------------------------------------===// 272// Public Constructor Functions 273//===----------------------------------------------------------------------===// 274 275/// createVLIWDAGScheduler - This creates a top-down list scheduler. 276ScheduleDAGSDNodes * 277llvm::createVLIWDAGScheduler(SelectionDAGISel *IS, CodeGenOpt::Level) { 278 return new ScheduleDAGVLIW(*IS->MF, IS->AA, new ResourcePriorityQueue(IS)); 279} 280