170572Sobrien//===- ScheduleDAGVLIW.cpp - SelectionDAG list scheduler for VLIW -*- C++ -*-=// 2178027Smarcel// 370741Sbenno// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 470572Sobrien// See https://llvm.org/LICENSE.txt for license information. 570572Sobrien// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 670572Sobrien// 770572Sobrien//===----------------------------------------------------------------------===// 870572Sobrien// 970572Sobrien// This implements a top-down list scheduler, using standard algorithms. 1070572Sobrien// The basic approach uses a priority queue of available nodes to schedule. 1170572Sobrien// One at a time, nodes are taken from the priority queue (thus in priority 1270572Sobrien// order), checked for legality to schedule, and emitted if legal. 1370572Sobrien// 1470572Sobrien// Nodes may not be legal to schedule either due to structural hazards (e.g. 1570572Sobrien// pipeline or resource constraints) or because an input to the instruction has 1670572Sobrien// not completed execution. 1770572Sobrien// 1870572Sobrien//===----------------------------------------------------------------------===// 1970572Sobrien 2070572Sobrien#include "ScheduleDAGSDNodes.h" 2170572Sobrien#include "llvm/ADT/Statistic.h" 2270572Sobrien#include "llvm/CodeGen/ResourcePriorityQueue.h" 2370572Sobrien#include "llvm/CodeGen/ScheduleHazardRecognizer.h" 2470572Sobrien#include "llvm/CodeGen/SchedulerRegistry.h" 2570572Sobrien#include "llvm/CodeGen/SelectionDAGISel.h" 2670572Sobrien#include "llvm/CodeGen/TargetInstrInfo.h" 2770572Sobrien#include "llvm/CodeGen/TargetSubtargetInfo.h" 2870572Sobrien#include "llvm/Support/Debug.h" 2970572Sobrien#include "llvm/Support/ErrorHandling.h" 3070572Sobrien#include "llvm/Support/raw_ostream.h" 3170572Sobrienusing namespace llvm; 3270572Sobrien 3370572Sobrien#define DEBUG_TYPE "pre-RA-sched" 3470572Sobrien 35143063SjoergSTATISTIC(NumNoops , "Number of noops inserted"); 36143063SjoergSTATISTIC(NumStalls, "Number of pipeline stalls"); 37143063Sjoerg 38143063Sjoergstatic RegisterScheduler 39235931Smarcel VLIWScheduler("vliw-td", "VLIW scheduler", 40235931Smarcel createVLIWDAGScheduler); 41235931Smarcel 42235931Smarcelnamespace { 43235931Smarcel//===----------------------------------------------------------------------===// 44235931Smarcel/// ScheduleDAGVLIW - The actual DFA list scheduler implementation. This 45235931Smarcel/// supports / top-down scheduling. 46235931Smarcel/// 47235931Smarcelclass ScheduleDAGVLIW : public ScheduleDAGSDNodes { 48235931Smarcelprivate: 49235931Smarcel /// AvailableQueue - The priority queue to use for the available SUnits. 50235931Smarcel /// 51234584Snwhitehorn SchedulingPriorityQueue *AvailableQueue; 52234590Snwhitehorn 53234584Snwhitehorn /// PendingQueue - This contains all of the instructions whose operands have 54235931Smarcel /// been issued, but their results are not ready yet (due to the latency of 55235943Snwhitehorn /// the operation). Once the operands become available, the instruction is 56234590Snwhitehorn /// added to the AvailableQueue. 57235942Smarcel std::vector<SUnit*> PendingQueue; 58235942Smarcel 59235946Sbz /// HazardRec - The hazard recognizer to use. 60235942Smarcel ScheduleHazardRecognizer *HazardRec; 61235931Smarcel 62234590Snwhitehorn /// AA - AAResults for making memory reference queries. 63234584Snwhitehorn AAResults *AA; 64234584Snwhitehorn 65178027Smarcelpublic: 66178027Smarcel ScheduleDAGVLIW(MachineFunction &mf, AAResults *aa, 6770572Sobrien SchedulingPriorityQueue *availqueue) 6870572Sobrien : ScheduleDAGSDNodes(mf), AvailableQueue(availqueue), AA(aa) { 69222198Sattilio const TargetSubtargetInfo &STI = mf.getSubtarget(); 70178027Smarcel HazardRec = STI.getInstrInfo()->CreateTargetHazardRecognizer(&STI, this); 71178027Smarcel } 72178027Smarcel 73178027Smarcel ~ScheduleDAGVLIW() override { 74178027Smarcel delete HazardRec; 75178027Smarcel delete AvailableQueue; 76178027Smarcel } 77178027Smarcel 78222198Sattilio void Schedule() override; 7970572Sobrien 80209975Snwhitehornprivate: 81222198Sattilio void releaseSucc(SUnit *SU, const SDep &D); 82209975Snwhitehorn void releaseSuccessors(SUnit *SU); 83209975Snwhitehorn void scheduleNodeTopDown(SUnit *SU, unsigned CurCycle); 84209975Snwhitehorn void listScheduleTopDown(); 85209975Snwhitehorn}; 86209975Snwhitehorn} // end anonymous namespace 87209975Snwhitehorn 88209975Snwhitehorn/// Schedule - Schedule the DAG using list scheduling. 89209975Snwhitehornvoid ScheduleDAGVLIW::Schedule() { 90222198Sattilio LLVM_DEBUG(dbgs() << "********** List Scheduling " << printMBBReference(*BB) 91209975Snwhitehorn << " '" << BB->getName() << "' **********\n"); 92222198Sattilio 93222198Sattilio // Build the scheduling graph. 94222198Sattilio BuildSchedGraph(AA); 95222198Sattilio 96222198Sattilio AvailableQueue->initNodes(SUnits); 97222198Sattilio 98222198Sattilio listScheduleTopDown(); 99222198Sattilio 100222198Sattilio AvailableQueue->releaseState(); 101222198Sattilio} 102209975Snwhitehorn 10370572Sobrien//===----------------------------------------------------------------------===// 104222198Sattilio// Top-Down Scheduling 105178027Smarcel//===----------------------------------------------------------------------===// 106222198Sattilio 107222198Sattilio/// releaseSucc - Decrement the NumPredsLeft count of a successor. Add it to 108222198Sattilio/// the PendingQueue if the count reaches zero. Also update its cycle bound. 109178027Smarcelvoid ScheduleDAGVLIW::releaseSucc(SUnit *SU, const SDep &D) { 110178027Smarcel SUnit *SuccSU = D.getSUnit(); 111178027Smarcel 112222198Sattilio#ifndef NDEBUG 113222198Sattilio if (SuccSU->NumPredsLeft == 0) { 114222198Sattilio dbgs() << "*** Scheduling failed! ***\n"; 115234590Snwhitehorn dumpNode(*SuccSU); 116178027Smarcel dbgs() << " has been released too many times!\n"; 117178027Smarcel llvm_unreachable(nullptr); 118178027Smarcel } 119222198Sattilio#endif 120222198Sattilio assert(!D.isWeak() && "unexpected artificial DAG edge"); 121234590Snwhitehorn 122222198Sattilio --SuccSU->NumPredsLeft; 123178027Smarcel 124178027Smarcel SuccSU->setDepthToAtLeast(SU->getDepth() + D.getLatency()); 12570572Sobrien 126222198Sattilio // If all the node's predecessors are scheduled, this node is ready 127222198Sattilio // to be scheduled. Ignore the special ExitSU node. 128222198Sattilio if (SuccSU->NumPredsLeft == 0 && SuccSU != &ExitSU) { 129222198Sattilio PendingQueue.push_back(SuccSU); 130222198Sattilio } 131222198Sattilio} 132222198Sattilio 133209975Snwhitehornvoid ScheduleDAGVLIW::releaseSuccessors(SUnit *SU) { 134222198Sattilio // Top down: release successors. 135222198Sattilio for (SDep &Succ : SU->Succs) { 136222198Sattilio assert(!Succ.isAssignedRegDep() && 137222198Sattilio "The list-td scheduler doesn't yet support physreg dependencies!"); 138222198Sattilio 139222198Sattilio releaseSucc(SU, Succ); 140222198Sattilio } 141209975Snwhitehorn} 142222198Sattilio 143222198Sattilio/// scheduleNodeTopDown - Add the node to the schedule. Decrement the pending 144222198Sattilio/// count of its successors. If a successor pending count is zero, add it to 145178027Smarcel/// the Available queue. 146178027Smarcelvoid ScheduleDAGVLIW::scheduleNodeTopDown(SUnit *SU, unsigned CurCycle) { 147222198Sattilio LLVM_DEBUG(dbgs() << "*** Scheduling [" << CurCycle << "]: "); 148222198Sattilio LLVM_DEBUG(dumpNode(*SU)); 14970572Sobrien 150178027Smarcel Sequence.push_back(SU); 151178027Smarcel assert(CurCycle >= SU->getDepth() && "Node scheduled above its depth!"); 152178027Smarcel SU->setDepthToAtLeast(CurCycle); 153178027Smarcel 15470572Sobrien releaseSuccessors(SU); 155222198Sattilio SU->isScheduled = true; 156178027Smarcel AvailableQueue->scheduledNode(SU); 157178027Smarcel} 158178027Smarcel 159178027Smarcel/// listScheduleTopDown - The main loop of list scheduling for top-down 160178027Smarcel/// schedulers. 161178027Smarcelvoid ScheduleDAGVLIW::listScheduleTopDown() { 162178027Smarcel unsigned CurCycle = 0; 163178027Smarcel 164222198Sattilio // Release any successors of the special Entry node. 16570572Sobrien releaseSuccessors(&EntrySU); 166209975Snwhitehorn 167222198Sattilio // All leaves to AvailableQueue. 168209975Snwhitehorn for (SUnit &SU : SUnits) { 169209975Snwhitehorn // It is available if it has no predecessors. 170209975Snwhitehorn if (SU.Preds.empty()) { 171209975Snwhitehorn AvailableQueue->push(&SU); 172209975Snwhitehorn SU.isAvailable = true; 173209975Snwhitehorn } 174209975Snwhitehorn } 175209975Snwhitehorn 176222198Sattilio // While AvailableQueue is not empty, grab the node with the highest 177209975Snwhitehorn // priority. If it is not ready put it back. Schedule the node. 178222198Sattilio std::vector<SUnit*> NotReady; 179222198Sattilio Sequence.reserve(SUnits.size()); 180222198Sattilio while (!AvailableQueue->empty() || !PendingQueue.empty()) { 181222198Sattilio // Check to see if any of the pending instructions are ready to issue. If 182222198Sattilio // so, add them to the available queue. 183222198Sattilio for (unsigned i = 0, e = PendingQueue.size(); i != e; ++i) { 184222198Sattilio if (PendingQueue[i]->getDepth() == CurCycle) { 185222198Sattilio AvailableQueue->push(PendingQueue[i]); 186222198Sattilio PendingQueue[i]->isAvailable = true; 187222198Sattilio PendingQueue[i] = PendingQueue.back(); 188209975Snwhitehorn PendingQueue.pop_back(); 18970572Sobrien --i; --e; 190222198Sattilio } 191178027Smarcel else { 192222198Sattilio assert(PendingQueue[i]->getDepth() > CurCycle && "Negative latency?"); 193222198Sattilio } 194222198Sattilio } 195178027Smarcel 196178027Smarcel // If there are no instructions available, don't try to issue anything, and 197178027Smarcel // don't advance the hazard recognizer. 198222198Sattilio if (AvailableQueue->empty()) { 199222198Sattilio // Reset DFA state. 200222198Sattilio AvailableQueue->scheduledNode(nullptr); 201234590Snwhitehorn ++CurCycle; 202178027Smarcel continue; 203178027Smarcel } 204178027Smarcel 205222198Sattilio SUnit *FoundSUnit = nullptr; 206222198Sattilio 207234590Snwhitehorn bool HasNoopHazards = false; 208222198Sattilio while (!AvailableQueue->empty()) { 209178027Smarcel SUnit *CurSUnit = AvailableQueue->pop(); 210178027Smarcel 21170572Sobrien ScheduleHazardRecognizer::HazardType HT = 212222198Sattilio HazardRec->getHazardType(CurSUnit, 0/*no stalls*/); 213222198Sattilio if (HT == ScheduleHazardRecognizer::NoHazard) { 214222198Sattilio FoundSUnit = CurSUnit; 215222198Sattilio break; 216222198Sattilio } 217222198Sattilio 218222198Sattilio // Remember if this is a noop hazard. 219222198Sattilio HasNoopHazards |= HT == ScheduleHazardRecognizer::NoopHazard; 220209975Snwhitehorn 221222198Sattilio NotReady.push_back(CurSUnit); 222222198Sattilio } 223222198Sattilio 224222198Sattilio // Add the nodes that aren't ready back onto the available list. 225222198Sattilio if (!NotReady.empty()) { 226222198Sattilio AvailableQueue->push_all(NotReady); 227222198Sattilio NotReady.clear(); 228209975Snwhitehorn } 229222198Sattilio 230222198Sattilio // If we found a node to schedule, do it now. 231222198Sattilio if (FoundSUnit) { 232178027Smarcel scheduleNodeTopDown(FoundSUnit, CurCycle); 233178027Smarcel HazardRec->EmitInstruction(FoundSUnit); 234222198Sattilio 235222198Sattilio // If this is a pseudo-op node, we don't want to increment the current 236178027Smarcel // cycle. 23770741Sbenno if (FoundSUnit->Latency) // Don't increment CurCycle for pseudo-ops! 238178027Smarcel ++CurCycle; 23970741Sbenno } else if (!HasNoopHazards) { 240178027Smarcel // Otherwise, we have a pipeline stall, but no other problem, just advance 24170741Sbenno // the current cycle and try again. 242178027Smarcel LLVM_DEBUG(dbgs() << "*** Advancing cycle, no work to do\n"); 243178027Smarcel HazardRec->AdvanceCycle(); 244178027Smarcel ++NumStalls; 245178027Smarcel ++CurCycle; 24670572Sobrien } else { 247178027Smarcel // Otherwise, we have no instructions to issue and we have instructions 248178027Smarcel // that will fault if we don't do this right. This is the case for 249178027Smarcel // processors without pipeline interlocks and other cases. 250178027Smarcel LLVM_DEBUG(dbgs() << "*** Emitting noop\n"); 25170572Sobrien HazardRec->EmitNoop(); 252178027Smarcel Sequence.push_back(nullptr); // NULL here means noop 253178027Smarcel ++NumNoops; 254178027Smarcel ++CurCycle; 255178027Smarcel } 25670572Sobrien } 257222198Sattilio 258178027Smarcel#ifndef NDEBUG 259178027Smarcel VerifyScheduledSequence(/*isBottomUp=*/false); 260178027Smarcel#endif 261178027Smarcel} 262178027Smarcel 263178027Smarcel//===----------------------------------------------------------------------===// 264178027Smarcel// Public Constructor Functions 265178027Smarcel//===----------------------------------------------------------------------===// 266222198Sattilio 26770572Sobrien/// createVLIWDAGScheduler - This creates a top-down list scheduler. 268209975SnwhitehornScheduleDAGSDNodes * 269222198Sattiliollvm::createVLIWDAGScheduler(SelectionDAGISel *IS, CodeGenOpt::Level) { 270209975Snwhitehorn return new ScheduleDAGVLIW(*IS->MF, IS->AA, new ResourcePriorityQueue(IS)); 271209975Snwhitehorn} 272209975Snwhitehorn