268 lines · cpp
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-exception6//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 priority12// 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 has16// 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"31using namespace llvm;32 33#define DEBUG_TYPE "pre-RA-sched"34 35STATISTIC(NumNoops , "Number of noops inserted");36STATISTIC(NumStalls, "Number of pipeline stalls");37 38static RegisterScheduler39 VLIWScheduler("vliw-td", "VLIW scheduler",40 createVLIWDAGScheduler);41 42namespace {43//===----------------------------------------------------------------------===//44/// ScheduleDAGVLIW - The actual DFA list scheduler implementation. This45/// supports / top-down scheduling.46///47class ScheduleDAGVLIW : public ScheduleDAGSDNodes {48private: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 have54 /// been issued, but their results are not ready yet (due to the latency of55 /// the operation). Once the operands become available, the instruction is56 /// added to the AvailableQueue.57 std::vector<SUnit*> PendingQueue;58 59 /// HazardRec - The hazard recognizer to use.60 ScheduleHazardRecognizer *HazardRec;61 62public:63 ScheduleDAGVLIW(MachineFunction &MF, SchedulingPriorityQueue *AvailableQueue)64 : ScheduleDAGSDNodes(MF), AvailableQueue(AvailableQueue) {65 const TargetSubtargetInfo &STI = MF.getSubtarget();66 HazardRec = STI.getInstrInfo()->CreateTargetHazardRecognizer(&STI, this);67 }68 69 ~ScheduleDAGVLIW() override {70 delete HazardRec;71 delete AvailableQueue;72 }73 74 void Schedule() override;75 76private:77 void releaseSucc(SUnit *SU, const SDep &D);78 void releaseSuccessors(SUnit *SU);79 void scheduleNodeTopDown(SUnit *SU, unsigned CurCycle);80 void listScheduleTopDown();81};82} // end anonymous namespace83 84/// Schedule - Schedule the DAG using list scheduling.85void ScheduleDAGVLIW::Schedule() {86 LLVM_DEBUG(dbgs() << "********** List Scheduling " << printMBBReference(*BB)87 << " '" << BB->getName() << "' **********\n");88 89 // Build the scheduling graph.90 BuildSchedGraph();91 92 AvailableQueue->initNodes(SUnits);93 94 listScheduleTopDown();95 96 AvailableQueue->releaseState();97}98 99//===----------------------------------------------------------------------===//100// Top-Down Scheduling101//===----------------------------------------------------------------------===//102 103/// releaseSucc - Decrement the NumPredsLeft count of a successor. Add it to104/// the PendingQueue if the count reaches zero. Also update its cycle bound.105void ScheduleDAGVLIW::releaseSucc(SUnit *SU, const SDep &D) {106 SUnit *SuccSU = D.getSUnit();107 108#ifndef NDEBUG109 if (SuccSU->NumPredsLeft == 0) {110 dbgs() << "*** Scheduling failed! ***\n";111 dumpNode(*SuccSU);112 dbgs() << " has been released too many times!\n";113 llvm_unreachable(nullptr);114 }115#endif116 assert(!D.isWeak() && "unexpected artificial DAG edge");117 118 --SuccSU->NumPredsLeft;119 120 SuccSU->setDepthToAtLeast(SU->getDepth() + D.getLatency());121 122 // If all the node's predecessors are scheduled, this node is ready123 // to be scheduled. Ignore the special ExitSU node.124 if (SuccSU->NumPredsLeft == 0 && SuccSU != &ExitSU) {125 PendingQueue.push_back(SuccSU);126 }127}128 129void ScheduleDAGVLIW::releaseSuccessors(SUnit *SU) {130 // Top down: release successors.131 for (SDep &Succ : SU->Succs) {132 assert(!Succ.isAssignedRegDep() &&133 "The list-td scheduler doesn't yet support physreg dependencies!");134 135 releaseSucc(SU, Succ);136 }137}138 139/// scheduleNodeTopDown - Add the node to the schedule. Decrement the pending140/// count of its successors. If a successor pending count is zero, add it to141/// the Available queue.142void ScheduleDAGVLIW::scheduleNodeTopDown(SUnit *SU, unsigned CurCycle) {143 LLVM_DEBUG(dbgs() << "*** Scheduling [" << CurCycle << "]: ");144 LLVM_DEBUG(dumpNode(*SU));145 146 Sequence.push_back(SU);147 assert(CurCycle >= SU->getDepth() && "Node scheduled above its depth!");148 SU->setDepthToAtLeast(CurCycle);149 150 releaseSuccessors(SU);151 SU->isScheduled = true;152 AvailableQueue->scheduledNode(SU);153}154 155/// listScheduleTopDown - The main loop of list scheduling for top-down156/// schedulers.157void ScheduleDAGVLIW::listScheduleTopDown() {158 unsigned CurCycle = 0;159 160 // Release any successors of the special Entry node.161 releaseSuccessors(&EntrySU);162 163 // All leaves to AvailableQueue.164 for (SUnit &SU : SUnits) {165 // It is available if it has no predecessors.166 if (SU.Preds.empty()) {167 AvailableQueue->push(&SU);168 SU.isAvailable = true;169 }170 }171 172 // While AvailableQueue is not empty, grab the node with the highest173 // priority. If it is not ready put it back. Schedule the node.174 std::vector<SUnit*> NotReady;175 Sequence.reserve(SUnits.size());176 while (!AvailableQueue->empty() || !PendingQueue.empty()) {177 // Check to see if any of the pending instructions are ready to issue. If178 // so, add them to the available queue.179 for (unsigned i = 0, e = PendingQueue.size(); i != e; ++i) {180 if (PendingQueue[i]->getDepth() == CurCycle) {181 AvailableQueue->push(PendingQueue[i]);182 PendingQueue[i]->isAvailable = true;183 PendingQueue[i] = PendingQueue.back();184 PendingQueue.pop_back();185 --i; --e;186 }187 else {188 assert(PendingQueue[i]->getDepth() > CurCycle && "Negative latency?");189 }190 }191 192 // If there are no instructions available, don't try to issue anything, and193 // don't advance the hazard recognizer.194 if (AvailableQueue->empty()) {195 // Reset DFA state.196 AvailableQueue->scheduledNode(nullptr);197 ++CurCycle;198 continue;199 }200 201 SUnit *FoundSUnit = nullptr;202 203 bool HasNoopHazards = false;204 while (!AvailableQueue->empty()) {205 SUnit *CurSUnit = AvailableQueue->pop();206 207 ScheduleHazardRecognizer::HazardType HT =208 HazardRec->getHazardType(CurSUnit, 0/*no stalls*/);209 if (HT == ScheduleHazardRecognizer::NoHazard) {210 FoundSUnit = CurSUnit;211 break;212 }213 214 // Remember if this is a noop hazard.215 HasNoopHazards |= HT == ScheduleHazardRecognizer::NoopHazard;216 217 NotReady.push_back(CurSUnit);218 }219 220 // Add the nodes that aren't ready back onto the available list.221 if (!NotReady.empty()) {222 AvailableQueue->push_all(NotReady);223 NotReady.clear();224 }225 226 // If we found a node to schedule, do it now.227 if (FoundSUnit) {228 scheduleNodeTopDown(FoundSUnit, CurCycle);229 HazardRec->EmitInstruction(FoundSUnit);230 231 // If this is a pseudo-op node, we don't want to increment the current232 // cycle.233 if (FoundSUnit->Latency) // Don't increment CurCycle for pseudo-ops!234 ++CurCycle;235 } else if (!HasNoopHazards) {236 // Otherwise, we have a pipeline stall, but no other problem, just advance237 // the current cycle and try again.238 LLVM_DEBUG(dbgs() << "*** Advancing cycle, no work to do\n");239 HazardRec->AdvanceCycle();240 ++NumStalls;241 ++CurCycle;242 } else {243 // Otherwise, we have no instructions to issue and we have instructions244 // that will fault if we don't do this right. This is the case for245 // processors without pipeline interlocks and other cases.246 LLVM_DEBUG(dbgs() << "*** Emitting noop\n");247 HazardRec->EmitNoop();248 Sequence.push_back(nullptr); // NULL here means noop249 ++NumNoops;250 ++CurCycle;251 }252 }253 254#ifndef NDEBUG255 VerifyScheduledSequence(/*isBottomUp=*/false);256#endif257}258 259//===----------------------------------------------------------------------===//260// Public Constructor Functions261//===----------------------------------------------------------------------===//262 263/// createVLIWDAGScheduler - This creates a top-down list scheduler.264ScheduleDAGSDNodes *llvm::createVLIWDAGScheduler(SelectionDAGISel *IS,265 CodeGenOptLevel) {266 return new ScheduleDAGVLIW(*IS->MF, new ResourcePriorityQueue(IS));267}268