LLVM  14.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"
30 #include "llvm/IR/DataLayout.h"
31 #include "llvm/Support/Debug.h"
34 #include <climits>
35 using namespace llvm;
36 
37 #define DEBUG_TYPE "pre-RA-sched"
38 
39 STATISTIC(NumNoops , "Number of noops inserted");
40 STATISTIC(NumStalls, "Number of pipeline stalls");
41 
42 static RegisterScheduler
43  VLIWScheduler("vliw-td", "VLIW scheduler",
45 
46 namespace {
47 //===----------------------------------------------------------------------===//
48 /// ScheduleDAGVLIW - The actual DFA list scheduler implementation. This
49 /// supports / top-down scheduling.
50 ///
51 class ScheduleDAGVLIW : public ScheduleDAGSDNodes {
52 private:
53  /// AvailableQueue - The priority queue to use for the available SUnits.
54  ///
55  SchedulingPriorityQueue *AvailableQueue;
56 
57  /// PendingQueue - This contains all of the instructions whose operands have
58  /// been issued, but their results are not ready yet (due to the latency of
59  /// the operation). Once the operands become available, the instruction is
60  /// added to the AvailableQueue.
61  std::vector<SUnit*> PendingQueue;
62 
63  /// HazardRec - The hazard recognizer to use.
64  ScheduleHazardRecognizer *HazardRec;
65 
66  /// AA - AAResults for making memory reference queries.
67  AAResults *AA;
68 
69 public:
70  ScheduleDAGVLIW(MachineFunction &mf, AAResults *aa,
71  SchedulingPriorityQueue *availqueue)
72  : ScheduleDAGSDNodes(mf), AvailableQueue(availqueue), AA(aa) {
73  const TargetSubtargetInfo &STI = mf.getSubtarget();
74  HazardRec = STI.getInstrInfo()->CreateTargetHazardRecognizer(&STI, this);
75  }
76 
77  ~ScheduleDAGVLIW() override {
78  delete HazardRec;
79  delete AvailableQueue;
80  }
81 
82  void Schedule() override;
83 
84 private:
85  void releaseSucc(SUnit *SU, const SDep &D);
86  void releaseSuccessors(SUnit *SU);
87  void scheduleNodeTopDown(SUnit *SU, unsigned CurCycle);
88  void listScheduleTopDown();
89 };
90 } // end anonymous namespace
91 
92 /// Schedule - Schedule the DAG using list scheduling.
93 void ScheduleDAGVLIW::Schedule() {
94  LLVM_DEBUG(dbgs() << "********** List Scheduling " << printMBBReference(*BB)
95  << " '" << BB->getName() << "' **********\n");
96 
97  // Build the scheduling graph.
98  BuildSchedGraph(AA);
99 
100  AvailableQueue->initNodes(SUnits);
101 
102  listScheduleTopDown();
103 
104  AvailableQueue->releaseState();
105 }
106 
107 //===----------------------------------------------------------------------===//
108 // Top-Down Scheduling
109 //===----------------------------------------------------------------------===//
110 
111 /// releaseSucc - Decrement the NumPredsLeft count of a successor. Add it to
112 /// the PendingQueue if the count reaches zero. Also update its cycle bound.
113 void ScheduleDAGVLIW::releaseSucc(SUnit *SU, const SDep &D) {
114  SUnit *SuccSU = D.getSUnit();
115 
116 #ifndef NDEBUG
117  if (SuccSU->NumPredsLeft == 0) {
118  dbgs() << "*** Scheduling failed! ***\n";
119  dumpNode(*SuccSU);
120  dbgs() << " has been released too many times!\n";
121  llvm_unreachable(nullptr);
122  }
123 #endif
124  assert(!D.isWeak() && "unexpected artificial DAG edge");
125 
126  --SuccSU->NumPredsLeft;
127 
128  SuccSU->setDepthToAtLeast(SU->getDepth() + D.getLatency());
129 
130  // If all the node's predecessors are scheduled, this node is ready
131  // to be scheduled. Ignore the special ExitSU node.
132  if (SuccSU->NumPredsLeft == 0 && SuccSU != &ExitSU) {
133  PendingQueue.push_back(SuccSU);
134  }
135 }
136 
137 void ScheduleDAGVLIW::releaseSuccessors(SUnit *SU) {
138  // Top down: release successors.
139  for (SDep &Succ : SU->Succs) {
140  assert(!Succ.isAssignedRegDep() &&
141  "The list-td scheduler doesn't yet support physreg dependencies!");
142 
143  releaseSucc(SU, Succ);
144  }
145 }
146 
147 /// scheduleNodeTopDown - Add the node to the schedule. Decrement the pending
148 /// count of its successors. If a successor pending count is zero, add it to
149 /// the Available queue.
150 void ScheduleDAGVLIW::scheduleNodeTopDown(SUnit *SU, unsigned CurCycle) {
151  LLVM_DEBUG(dbgs() << "*** Scheduling [" << CurCycle << "]: ");
152  LLVM_DEBUG(dumpNode(*SU));
153 
154  Sequence.push_back(SU);
155  assert(CurCycle >= SU->getDepth() && "Node scheduled above its depth!");
156  SU->setDepthToAtLeast(CurCycle);
157 
158  releaseSuccessors(SU);
159  SU->isScheduled = true;
160  AvailableQueue->scheduledNode(SU);
161 }
162 
163 /// listScheduleTopDown - The main loop of list scheduling for top-down
164 /// schedulers.
165 void ScheduleDAGVLIW::listScheduleTopDown() {
166  unsigned CurCycle = 0;
167 
168  // Release any successors of the special Entry node.
169  releaseSuccessors(&EntrySU);
170 
171  // All leaves to AvailableQueue.
172  for (unsigned i = 0, e = SUnits.size(); i != e; ++i) {
173  // It is available if it has no predecessors.
174  if (SUnits[i].Preds.empty()) {
175  AvailableQueue->push(&SUnits[i]);
176  SUnits[i].isAvailable = true;
177  }
178  }
179 
180  // While AvailableQueue is not empty, grab the node with the highest
181  // priority. If it is not ready put it back. Schedule the node.
182  std::vector<SUnit*> NotReady;
183  Sequence.reserve(SUnits.size());
184  while (!AvailableQueue->empty() || !PendingQueue.empty()) {
185  // Check to see if any of the pending instructions are ready to issue. If
186  // so, add them to the available queue.
187  for (unsigned i = 0, e = PendingQueue.size(); i != e; ++i) {
188  if (PendingQueue[i]->getDepth() == CurCycle) {
189  AvailableQueue->push(PendingQueue[i]);
190  PendingQueue[i]->isAvailable = true;
191  PendingQueue[i] = PendingQueue.back();
192  PendingQueue.pop_back();
193  --i; --e;
194  }
195  else {
196  assert(PendingQueue[i]->getDepth() > CurCycle && "Negative latency?");
197  }
198  }
199 
200  // If there are no instructions available, don't try to issue anything, and
201  // don't advance the hazard recognizer.
202  if (AvailableQueue->empty()) {
203  // Reset DFA state.
204  AvailableQueue->scheduledNode(nullptr);
205  ++CurCycle;
206  continue;
207  }
208 
209  SUnit *FoundSUnit = nullptr;
210 
211  bool HasNoopHazards = false;
212  while (!AvailableQueue->empty()) {
213  SUnit *CurSUnit = AvailableQueue->pop();
214 
216  HazardRec->getHazardType(CurSUnit, 0/*no stalls*/);
218  FoundSUnit = CurSUnit;
219  break;
220  }
221 
222  // Remember if this is a noop hazard.
223  HasNoopHazards |= HT == ScheduleHazardRecognizer::NoopHazard;
224 
225  NotReady.push_back(CurSUnit);
226  }
227 
228  // Add the nodes that aren't ready back onto the available list.
229  if (!NotReady.empty()) {
230  AvailableQueue->push_all(NotReady);
231  NotReady.clear();
232  }
233 
234  // If we found a node to schedule, do it now.
235  if (FoundSUnit) {
236  scheduleNodeTopDown(FoundSUnit, CurCycle);
237  HazardRec->EmitInstruction(FoundSUnit);
238 
239  // If this is a pseudo-op node, we don't want to increment the current
240  // cycle.
241  if (FoundSUnit->Latency) // Don't increment CurCycle for pseudo-ops!
242  ++CurCycle;
243  } else if (!HasNoopHazards) {
244  // Otherwise, we have a pipeline stall, but no other problem, just advance
245  // the current cycle and try again.
246  LLVM_DEBUG(dbgs() << "*** Advancing cycle, no work to do\n");
247  HazardRec->AdvanceCycle();
248  ++NumStalls;
249  ++CurCycle;
250  } else {
251  // Otherwise, we have no instructions to issue and we have instructions
252  // that will fault if we don't do this right. This is the case for
253  // processors without pipeline interlocks and other cases.
254  LLVM_DEBUG(dbgs() << "*** Emitting noop\n");
255  HazardRec->EmitNoop();
256  Sequence.push_back(nullptr); // NULL here means noop
257  ++NumNoops;
258  ++CurCycle;
259  }
260  }
261 
262 #ifndef NDEBUG
263  VerifyScheduledSequence(/*isBottomUp=*/false);
264 #endif
265 }
266 
267 //===----------------------------------------------------------------------===//
268 // Public Constructor Functions
269 //===----------------------------------------------------------------------===//
270 
271 /// createVLIWDAGScheduler - This creates a top-down list scheduler.
274  return new ScheduleDAGVLIW(*IS->MF, IS->AA, new ResourcePriorityQueue(IS));
275 }
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:542
llvm
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
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:1046
aa
aa
Definition: AliasAnalysis.cpp:846
SchedulerRegistry.h
llvm::TargetSubtargetInfo::getInstrInfo
virtual const TargetInstrInfo * getInstrInfo() const
Definition: TargetSubtargetInfo.h:92
Statistic.h
llvm::printMBBReference
Printable printMBBReference(const MachineBasicBlock &MBB)
Prints a machine basic block reference.
Definition: MachineBasicBlock.cpp:119
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:456
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:626
LatencyPriorityQueue.h
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:57
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:273
llvm::SchedulingPriorityQueue::pop
virtual SUnit * pop()=0
llvm::MachineFunction
Definition: MachineFunction.h:230
SelectionDAGISel.h
DataLayout.h
llvm_unreachable
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Definition: ErrorHandling.h:136
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:59
llvm::ScheduleHazardRecognizer::NoopHazard
@ NoopHazard
Definition: ScheduleHazardRecognizer.h:40
llvm::SDep
Scheduling dependency.
Definition: ScheduleDAG.h:49
llvm::SelectionDAGISel::MF
MachineFunction * MF
Definition: SelectionDAGISel.h:45
llvm::SchedulingPriorityQueue::releaseState
virtual void releaseState()=0
llvm::SelectionDAGISel::AA
AAResults * AA
Definition: SelectionDAGISel.h:49
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:39
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
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
TargetRegisterInfo.h
Debug.h