LLVM  16.0.0git
ScheduleDAGVLIW.cpp
Go to the documentation of this file.
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-exception
6 //
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 priority
12 // 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 has
16 // not completed execution.
17 //
18 //===----------------------------------------------------------------------===//
19 
20 #include "ScheduleDAGSDNodes.h"
21 #include "llvm/ADT/Statistic.h"
28 #include "llvm/Support/Debug.h"
31 using namespace llvm;
32 
33 #define DEBUG_TYPE "pre-RA-sched"
34 
35 STATISTIC(NumNoops , "Number of noops inserted");
36 STATISTIC(NumStalls, "Number of pipeline stalls");
37 
38 static RegisterScheduler
39  VLIWScheduler("vliw-td", "VLIW scheduler",
41 
42 namespace {
43 //===----------------------------------------------------------------------===//
44 /// ScheduleDAGVLIW - The actual DFA list scheduler implementation. This
45 /// supports / top-down scheduling.
46 ///
47 class ScheduleDAGVLIW : public ScheduleDAGSDNodes {
48 private:
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 have
54  /// been issued, but their results are not ready yet (due to the latency of
55  /// the operation). Once the operands become available, the instruction is
56  /// added to the AvailableQueue.
57  std::vector<SUnit*> PendingQueue;
58 
59  /// HazardRec - The hazard recognizer to use.
60  ScheduleHazardRecognizer *HazardRec;
61 
62  /// AA - AAResults for making memory reference queries.
63  AAResults *AA;
64 
65 public:
66  ScheduleDAGVLIW(MachineFunction &mf, AAResults *aa,
67  SchedulingPriorityQueue *availqueue)
68  : ScheduleDAGSDNodes(mf), AvailableQueue(availqueue), AA(aa) {
69  const TargetSubtargetInfo &STI = mf.getSubtarget();
70  HazardRec = STI.getInstrInfo()->CreateTargetHazardRecognizer(&STI, this);
71  }
72 
73  ~ScheduleDAGVLIW() override {
74  delete HazardRec;
75  delete AvailableQueue;
76  }
77 
78  void Schedule() override;
79 
80 private:
81  void releaseSucc(SUnit *SU, const SDep &D);
82  void releaseSuccessors(SUnit *SU);
83  void scheduleNodeTopDown(SUnit *SU, unsigned CurCycle);
84  void listScheduleTopDown();
85 };
86 } // end anonymous namespace
87 
88 /// Schedule - Schedule the DAG using list scheduling.
89 void ScheduleDAGVLIW::Schedule() {
90  LLVM_DEBUG(dbgs() << "********** List Scheduling " << printMBBReference(*BB)
91  << " '" << BB->getName() << "' **********\n");
92 
93  // Build the scheduling graph.
94  BuildSchedGraph(AA);
95 
96  AvailableQueue->initNodes(SUnits);
97 
98  listScheduleTopDown();
99 
100  AvailableQueue->releaseState();
101 }
102 
103 //===----------------------------------------------------------------------===//
104 // Top-Down Scheduling
105 //===----------------------------------------------------------------------===//
106 
107 /// releaseSucc - Decrement the NumPredsLeft count of a successor. Add it to
108 /// the PendingQueue if the count reaches zero. Also update its cycle bound.
109 void ScheduleDAGVLIW::releaseSucc(SUnit *SU, const SDep &D) {
110  SUnit *SuccSU = D.getSUnit();
111 
112 #ifndef NDEBUG
113  if (SuccSU->NumPredsLeft == 0) {
114  dbgs() << "*** Scheduling failed! ***\n";
115  dumpNode(*SuccSU);
116  dbgs() << " has been released too many times!\n";
117  llvm_unreachable(nullptr);
118  }
119 #endif
120  assert(!D.isWeak() && "unexpected artificial DAG edge");
121 
122  --SuccSU->NumPredsLeft;
123 
124  SuccSU->setDepthToAtLeast(SU->getDepth() + D.getLatency());
125 
126  // If all the node's predecessors are scheduled, this node is ready
127  // to be scheduled. Ignore the special ExitSU node.
128  if (SuccSU->NumPredsLeft == 0 && SuccSU != &ExitSU) {
129  PendingQueue.push_back(SuccSU);
130  }
131 }
132 
133 void ScheduleDAGVLIW::releaseSuccessors(SUnit *SU) {
134  // Top down: release successors.
135  for (SDep &Succ : SU->Succs) {
136  assert(!Succ.isAssignedRegDep() &&
137  "The list-td scheduler doesn't yet support physreg dependencies!");
138 
139  releaseSucc(SU, Succ);
140  }
141 }
142 
143 /// scheduleNodeTopDown - Add the node to the schedule. Decrement the pending
144 /// count of its successors. If a successor pending count is zero, add it to
145 /// the Available queue.
146 void ScheduleDAGVLIW::scheduleNodeTopDown(SUnit *SU, unsigned CurCycle) {
147  LLVM_DEBUG(dbgs() << "*** Scheduling [" << CurCycle << "]: ");
148  LLVM_DEBUG(dumpNode(*SU));
149 
150  Sequence.push_back(SU);
151  assert(CurCycle >= SU->getDepth() && "Node scheduled above its depth!");
152  SU->setDepthToAtLeast(CurCycle);
153 
154  releaseSuccessors(SU);
155  SU->isScheduled = true;
156  AvailableQueue->scheduledNode(SU);
157 }
158 
159 /// listScheduleTopDown - The main loop of list scheduling for top-down
160 /// schedulers.
161 void ScheduleDAGVLIW::listScheduleTopDown() {
162  unsigned CurCycle = 0;
163 
164  // Release any successors of the special Entry node.
165  releaseSuccessors(&EntrySU);
166 
167  // All leaves to AvailableQueue.
168  for (SUnit &SU : SUnits) {
169  // It is available if it has no predecessors.
170  if (SU.Preds.empty()) {
171  AvailableQueue->push(&SU);
172  SU.isAvailable = true;
173  }
174  }
175 
176  // While AvailableQueue is not empty, grab the node with the highest
177  // priority. If it is not ready put it back. Schedule the node.
178  std::vector<SUnit*> NotReady;
179  Sequence.reserve(SUnits.size());
180  while (!AvailableQueue->empty() || !PendingQueue.empty()) {
181  // Check to see if any of the pending instructions are ready to issue. If
182  // so, add them to the available queue.
183  for (unsigned i = 0, e = PendingQueue.size(); i != e; ++i) {
184  if (PendingQueue[i]->getDepth() == CurCycle) {
185  AvailableQueue->push(PendingQueue[i]);
186  PendingQueue[i]->isAvailable = true;
187  PendingQueue[i] = PendingQueue.back();
188  PendingQueue.pop_back();
189  --i; --e;
190  }
191  else {
192  assert(PendingQueue[i]->getDepth() > CurCycle && "Negative latency?");
193  }
194  }
195 
196  // If there are no instructions available, don't try to issue anything, and
197  // don't advance the hazard recognizer.
198  if (AvailableQueue->empty()) {
199  // Reset DFA state.
200  AvailableQueue->scheduledNode(nullptr);
201  ++CurCycle;
202  continue;
203  }
204 
205  SUnit *FoundSUnit = nullptr;
206 
207  bool HasNoopHazards = false;
208  while (!AvailableQueue->empty()) {
209  SUnit *CurSUnit = AvailableQueue->pop();
210 
212  HazardRec->getHazardType(CurSUnit, 0/*no stalls*/);
214  FoundSUnit = CurSUnit;
215  break;
216  }
217 
218  // Remember if this is a noop hazard.
219  HasNoopHazards |= HT == ScheduleHazardRecognizer::NoopHazard;
220 
221  NotReady.push_back(CurSUnit);
222  }
223 
224  // Add the nodes that aren't ready back onto the available list.
225  if (!NotReady.empty()) {
226  AvailableQueue->push_all(NotReady);
227  NotReady.clear();
228  }
229 
230  // If we found a node to schedule, do it now.
231  if (FoundSUnit) {
232  scheduleNodeTopDown(FoundSUnit, CurCycle);
233  HazardRec->EmitInstruction(FoundSUnit);
234 
235  // If this is a pseudo-op node, we don't want to increment the current
236  // cycle.
237  if (FoundSUnit->Latency) // Don't increment CurCycle for pseudo-ops!
238  ++CurCycle;
239  } else if (!HasNoopHazards) {
240  // Otherwise, we have a pipeline stall, but no other problem, just advance
241  // the current cycle and try again.
242  LLVM_DEBUG(dbgs() << "*** Advancing cycle, no work to do\n");
243  HazardRec->AdvanceCycle();
244  ++NumStalls;
245  ++CurCycle;
246  } else {
247  // Otherwise, we have no instructions to issue and we have instructions
248  // that will fault if we don't do this right. This is the case for
249  // processors without pipeline interlocks and other cases.
250  LLVM_DEBUG(dbgs() << "*** Emitting noop\n");
251  HazardRec->EmitNoop();
252  Sequence.push_back(nullptr); // NULL here means noop
253  ++NumNoops;
254  ++CurCycle;
255  }
256  }
257 
258 #ifndef NDEBUG
259  VerifyScheduledSequence(/*isBottomUp=*/false);
260 #endif
261 }
262 
263 //===----------------------------------------------------------------------===//
264 // Public Constructor Functions
265 //===----------------------------------------------------------------------===//
266 
267 /// createVLIWDAGScheduler - This creates a top-down list scheduler.
270  return new ScheduleDAGVLIW(*IS->MF, IS->AA, new ResourcePriorityQueue(IS));
271 }
i
i
Definition: README.txt:29
llvm::SchedulingPriorityQueue::scheduledNode
virtual void scheduledNode(SUnit *)
As each node is scheduled, this method is invoked.
Definition: ScheduleDAG.h:541
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
llvm::objcarc::Sequence
Sequence
Definition: PtrState.h:41
llvm::SUnit::NumPredsLeft
unsigned NumPredsLeft
Definition: ScheduleDAG.h:268
llvm::ScheduleDAGSDNodes
ScheduleDAGSDNodes - A ScheduleDAG for scheduling SDNode-based DAGs.
Definition: ScheduleDAGSDNodes.h:46
llvm::TargetInstrInfo::CreateTargetHazardRecognizer
virtual ScheduleHazardRecognizer * CreateTargetHazardRecognizer(const TargetSubtargetInfo *STI, const ScheduleDAG *DAG) const
Allocate and return a hazard recognizer to use for this target when scheduling the machine instructio...
Definition: TargetInstrInfo.cpp:1051
llvm::SUnit::isAvailable
bool isAvailable
True once available.
Definition: ScheduleDAG.h:283
aa
aa
Definition: AliasAnalysis.cpp:771
SchedulerRegistry.h
llvm::TargetSubtargetInfo::getInstrInfo
virtual const TargetInstrInfo * getInstrInfo() const
Definition: TargetSubtargetInfo.h:95
Statistic.h
llvm::printMBBReference
Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.
Definition: MachineBasicBlock.cpp:117
ErrorHandling.h
TargetInstrInfo.h
llvm::SUnit::Succs
SmallVector< SDep, 4 > Succs
All sunit successors.
Definition: ScheduleDAG.h:257
llvm::SUnit::getDepth
unsigned getDepth() const
Returns the depth of this node, which is the length of the maximum path up to any node which has no p...
Definition: ScheduleDAG.h:398
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
ScheduleHazardRecognizer.h
llvm::AAResults
Definition: AliasAnalysis.h:294
llvm::SUnit::Latency
unsigned short Latency
Node latency.
Definition: ScheduleDAG.h:273
llvm::SUnit::setDepthToAtLeast
void setDepthToAtLeast(unsigned NewDepth)
If NewDepth is greater than this node's depth value, sets it to be the new depth value.
Definition: ScheduleDAG.cpp:247
llvm::SchedulingPriorityQueue::empty
virtual bool empty() const =0
llvm::STATISTIC
STATISTIC(NumFunctions, "Total number of functions")
ScheduleDAGSDNodes.h
ResourcePriorityQueue.h
llvm::SchedulingPriorityQueue::push
virtual void push(SUnit *U)=0
llvm::MachineFunction::getSubtarget
const TargetSubtargetInfo & getSubtarget() const
getSubtarget - Return the subtarget for which this machine code is being compiled.
Definition: MachineFunction.h:657
llvm::ScheduleHazardRecognizer::HazardType
HazardType
Definition: ScheduleHazardRecognizer.h:37
D
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
llvm::numbers::e
constexpr double e
Definition: MathExtras.h:53
llvm::SUnit::isScheduled
bool isScheduled
True once scheduled.
Definition: ScheduleDAG.h:284
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::createVLIWDAGScheduler
ScheduleDAGSDNodes * createVLIWDAGScheduler(SelectionDAGISel *IS, CodeGenOpt::Level OptLevel)
createVLIWDAGScheduler - Scheduler for VLIW targets.
Definition: ScheduleDAGVLIW.cpp:269
llvm::SchedulingPriorityQueue::pop
virtual SUnit * pop()=0
llvm::MachineFunction
Definition: MachineFunction.h:257
SelectionDAGISel.h
llvm_unreachable
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Definition: ErrorHandling.h:143
llvm::ScheduleHazardRecognizer::EmitInstruction
virtual void EmitInstruction(SUnit *)
EmitInstruction - This callback is invoked when an instruction is emitted, to advance the hazard stat...
Definition: ScheduleHazardRecognizer.h:71
TargetSubtargetInfo.h
llvm::CodeGenOpt::Level
Level
Definition: CodeGen.h:52
llvm::SDep::isAssignedRegDep
bool isAssignedRegDep() const
Tests if this is a Data dependence that is associated with a register.
Definition: ScheduleDAG.h:211
llvm::TargetSubtargetInfo
TargetSubtargetInfo - Generic base class for all target subtargets.
Definition: TargetSubtargetInfo.h:62
llvm::ScheduleHazardRecognizer::NoopHazard
@ NoopHazard
Definition: ScheduleHazardRecognizer.h:40
llvm::SDep
Scheduling dependency.
Definition: ScheduleDAG.h:49
llvm::SelectionDAGISel::MF
MachineFunction * MF
Definition: SelectionDAGISel.h:47
llvm::SchedulingPriorityQueue::releaseState
virtual void releaseState()=0
llvm::SelectionDAGISel::AA
AAResults * AA
Definition: SelectionDAGISel.h:51
llvm::ScheduleHazardRecognizer::NoHazard
@ NoHazard
Definition: ScheduleHazardRecognizer.h:38
llvm::RegisterScheduler
Definition: SchedulerRegistry.h:31
llvm::ScheduleHazardRecognizer::EmitNoop
virtual void EmitNoop()
EmitNoop - This callback is invoked when a noop was added to the instruction stream.
Definition: ScheduleHazardRecognizer.h:113
llvm::ResourcePriorityQueue
Definition: ResourcePriorityQueue.h:37
llvm::SelectionDAGISel
SelectionDAGISel - This is the common base class used for SelectionDAG-based pattern-matching instruc...
Definition: SelectionDAGISel.h:41
llvm::ScheduleHazardRecognizer::AdvanceCycle
virtual void AdvanceCycle()
AdvanceCycle - This callback is invoked whenever the next top-down instruction to be scheduled cannot...
Definition: ScheduleHazardRecognizer.h:104
llvm::SchedulingPriorityQueue::push_all
void push_all(const std::vector< SUnit * > &Nodes)
Definition: ScheduleDAG.h:527
llvm::SUnit::Preds
SmallVector< SDep, 4 > Preds
All sunit predecessors.
Definition: ScheduleDAG.h:256
llvm::SUnit
Scheduling unit. This is a node in the scheduling DAG.
Definition: ScheduleDAG.h:242
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
llvm::SchedulingPriorityQueue
This interface is used to plug different priorities computation algorithms into the list scheduler.
Definition: ScheduleDAG.h:496
raw_ostream.h
llvm::ScheduleHazardRecognizer
HazardRecognizer - This determines whether or not an instruction can be issued this cycle,...
Definition: ScheduleHazardRecognizer.h:25
VLIWScheduler
static RegisterScheduler VLIWScheduler("vliw-td", "VLIW scheduler", createVLIWDAGScheduler)
llvm::ScheduleHazardRecognizer::getHazardType
virtual HazardType getHazardType(SUnit *, int Stalls=0)
getHazardType - Return the hazard type of emitting this node.
Definition: ScheduleHazardRecognizer.h:60
llvm::SchedulingPriorityQueue::initNodes
virtual void initNodes(std::vector< SUnit > &SUnits)=0
Debug.h