//===- ScheduleDAGVLIW.cpp - SelectionDAG list scheduler for VLIW -*- C++ -*-=// // // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. // See https://llvm.org/LICENSE.txt for license information. // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception // //===----------------------------------------------------------------------===// // // This implements a top-down list scheduler, using standard algorithms. // The basic approach uses a priority queue of available nodes to schedule. // One at a time, nodes are taken from the priority queue (thus in priority // order), checked for legality to schedule, and emitted if legal. // // Nodes may not be legal to schedule either due to structural hazards (e.g. // pipeline or resource constraints) or because an input to the instruction has // not completed execution. // //===----------------------------------------------------------------------===// #include "ScheduleDAGSDNodes.h" #include "llvm/ADT/Statistic.h" #include "llvm/CodeGen/ResourcePriorityQueue.h" #include "llvm/CodeGen/ScheduleHazardRecognizer.h" #include "llvm/CodeGen/SchedulerRegistry.h" #include "llvm/CodeGen/SelectionDAGISel.h" #include "llvm/CodeGen/TargetInstrInfo.h" #include "llvm/CodeGen/TargetSubtargetInfo.h" #include "llvm/Support/Debug.h" #include "llvm/Support/ErrorHandling.h" #include "llvm/Support/raw_ostream.h" using namespace llvm; #define DEBUG_TYPE "pre-RA-sched" STATISTIC(NumNoops , "Number of noops inserted"); STATISTIC(NumStalls, "Number of pipeline stalls"); static RegisterScheduler VLIWScheduler("vliw-td", "VLIW scheduler", createVLIWDAGScheduler); namespace { //===----------------------------------------------------------------------===// /// ScheduleDAGVLIW - The actual DFA list scheduler implementation. This /// supports / top-down scheduling. /// class ScheduleDAGVLIW : public ScheduleDAGSDNodes { private: /// AvailableQueue - The priority queue to use for the available SUnits. /// SchedulingPriorityQueue *AvailableQueue; /// PendingQueue - This contains all of the instructions whose operands have /// been issued, but their results are not ready yet (due to the latency of /// the operation). Once the operands become available, the instruction is /// added to the AvailableQueue. std::vector PendingQueue; /// HazardRec - The hazard recognizer to use. ScheduleHazardRecognizer *HazardRec; /// AA - AAResults for making memory reference queries. AAResults *AA; public: ScheduleDAGVLIW(MachineFunction &mf, AAResults *aa, SchedulingPriorityQueue *availqueue) : ScheduleDAGSDNodes(mf), AvailableQueue(availqueue), AA(aa) { const TargetSubtargetInfo &STI = mf.getSubtarget(); HazardRec = STI.getInstrInfo()->CreateTargetHazardRecognizer(&STI, this); } ~ScheduleDAGVLIW() override { delete HazardRec; delete AvailableQueue; } void Schedule() override; private: void releaseSucc(SUnit *SU, const SDep &D); void releaseSuccessors(SUnit *SU); void scheduleNodeTopDown(SUnit *SU, unsigned CurCycle); void listScheduleTopDown(); }; } // end anonymous namespace /// Schedule - Schedule the DAG using list scheduling. void ScheduleDAGVLIW::Schedule() { LLVM_DEBUG(dbgs() << "********** List Scheduling " << printMBBReference(*BB) << " '" << BB->getName() << "' **********\n"); // Build the scheduling graph. BuildSchedGraph(AA); AvailableQueue->initNodes(SUnits); listScheduleTopDown(); AvailableQueue->releaseState(); } //===----------------------------------------------------------------------===// // Top-Down Scheduling //===----------------------------------------------------------------------===// /// releaseSucc - Decrement the NumPredsLeft count of a successor. Add it to /// the PendingQueue if the count reaches zero. Also update its cycle bound. void ScheduleDAGVLIW::releaseSucc(SUnit *SU, const SDep &D) { SUnit *SuccSU = D.getSUnit(); #ifndef NDEBUG if (SuccSU->NumPredsLeft == 0) { dbgs() << "*** Scheduling failed! ***\n"; dumpNode(*SuccSU); dbgs() << " has been released too many times!\n"; llvm_unreachable(nullptr); } #endif assert(!D.isWeak() && "unexpected artificial DAG edge"); --SuccSU->NumPredsLeft; SuccSU->setDepthToAtLeast(SU->getDepth() + D.getLatency()); // If all the node's predecessors are scheduled, this node is ready // to be scheduled. Ignore the special ExitSU node. if (SuccSU->NumPredsLeft == 0 && SuccSU != &ExitSU) { PendingQueue.push_back(SuccSU); } } void ScheduleDAGVLIW::releaseSuccessors(SUnit *SU) { // Top down: release successors. for (SDep &Succ : SU->Succs) { assert(!Succ.isAssignedRegDep() && "The list-td scheduler doesn't yet support physreg dependencies!"); releaseSucc(SU, Succ); } } /// scheduleNodeTopDown - Add the node to the schedule. Decrement the pending /// count of its successors. If a successor pending count is zero, add it to /// the Available queue. void ScheduleDAGVLIW::scheduleNodeTopDown(SUnit *SU, unsigned CurCycle) { LLVM_DEBUG(dbgs() << "*** Scheduling [" << CurCycle << "]: "); LLVM_DEBUG(dumpNode(*SU)); Sequence.push_back(SU); assert(CurCycle >= SU->getDepth() && "Node scheduled above its depth!"); SU->setDepthToAtLeast(CurCycle); releaseSuccessors(SU); SU->isScheduled = true; AvailableQueue->scheduledNode(SU); } /// listScheduleTopDown - The main loop of list scheduling for top-down /// schedulers. void ScheduleDAGVLIW::listScheduleTopDown() { unsigned CurCycle = 0; // Release any successors of the special Entry node. releaseSuccessors(&EntrySU); // All leaves to AvailableQueue. for (SUnit &SU : SUnits) { // It is available if it has no predecessors. if (SU.Preds.empty()) { AvailableQueue->push(&SU); SU.isAvailable = true; } } // While AvailableQueue is not empty, grab the node with the highest // priority. If it is not ready put it back. Schedule the node. std::vector NotReady; Sequence.reserve(SUnits.size()); while (!AvailableQueue->empty() || !PendingQueue.empty()) { // Check to see if any of the pending instructions are ready to issue. If // so, add them to the available queue. for (unsigned i = 0, e = PendingQueue.size(); i != e; ++i) { if (PendingQueue[i]->getDepth() == CurCycle) { AvailableQueue->push(PendingQueue[i]); PendingQueue[i]->isAvailable = true; PendingQueue[i] = PendingQueue.back(); PendingQueue.pop_back(); --i; --e; } else { assert(PendingQueue[i]->getDepth() > CurCycle && "Negative latency?"); } } // If there are no instructions available, don't try to issue anything, and // don't advance the hazard recognizer. if (AvailableQueue->empty()) { // Reset DFA state. AvailableQueue->scheduledNode(nullptr); ++CurCycle; continue; } SUnit *FoundSUnit = nullptr; bool HasNoopHazards = false; while (!AvailableQueue->empty()) { SUnit *CurSUnit = AvailableQueue->pop(); ScheduleHazardRecognizer::HazardType HT = HazardRec->getHazardType(CurSUnit, 0/*no stalls*/); if (HT == ScheduleHazardRecognizer::NoHazard) { FoundSUnit = CurSUnit; break; } // Remember if this is a noop hazard. HasNoopHazards |= HT == ScheduleHazardRecognizer::NoopHazard; NotReady.push_back(CurSUnit); } // Add the nodes that aren't ready back onto the available list. if (!NotReady.empty()) { AvailableQueue->push_all(NotReady); NotReady.clear(); } // If we found a node to schedule, do it now. if (FoundSUnit) { scheduleNodeTopDown(FoundSUnit, CurCycle); HazardRec->EmitInstruction(FoundSUnit); // If this is a pseudo-op node, we don't want to increment the current // cycle. if (FoundSUnit->Latency) // Don't increment CurCycle for pseudo-ops! ++CurCycle; } else if (!HasNoopHazards) { // Otherwise, we have a pipeline stall, but no other problem, just advance // the current cycle and try again. LLVM_DEBUG(dbgs() << "*** Advancing cycle, no work to do\n"); HazardRec->AdvanceCycle(); ++NumStalls; ++CurCycle; } else { // Otherwise, we have no instructions to issue and we have instructions // that will fault if we don't do this right. This is the case for // processors without pipeline interlocks and other cases. LLVM_DEBUG(dbgs() << "*** Emitting noop\n"); HazardRec->EmitNoop(); Sequence.push_back(nullptr); // NULL here means noop ++NumNoops; ++CurCycle; } } #ifndef NDEBUG VerifyScheduledSequence(/*isBottomUp=*/false); #endif } //===----------------------------------------------------------------------===// // Public Constructor Functions //===----------------------------------------------------------------------===// /// createVLIWDAGScheduler - This creates a top-down list scheduler. ScheduleDAGSDNodes * llvm::createVLIWDAGScheduler(SelectionDAGISel *IS, CodeGenOpt::Level) { return new ScheduleDAGVLIW(*IS->MF, IS->AA, new ResourcePriorityQueue(IS)); }