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