LLVM  15.0.0git
ScheduleDAGFast.cpp
Go to the documentation of this file.
1 //===----- ScheduleDAGFast.cpp - Fast poor list scheduler -----------------===//
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 fast scheduler.
10 //
11 //===----------------------------------------------------------------------===//
12 
13 #include "InstrEmitter.h"
14 #include "SDNodeDbgValue.h"
15 #include "ScheduleDAGSDNodes.h"
16 #include "llvm/ADT/SmallSet.h"
17 #include "llvm/ADT/Statistic.h"
22 #include "llvm/IR/InlineAsm.h"
23 #include "llvm/Support/Debug.h"
26 using namespace llvm;
27 
28 #define DEBUG_TYPE "pre-RA-sched"
29 
30 STATISTIC(NumUnfolds, "Number of nodes unfolded");
31 STATISTIC(NumDups, "Number of duplicated nodes");
32 STATISTIC(NumPRCopies, "Number of physical copies");
33 
34 static RegisterScheduler
35  fastDAGScheduler("fast", "Fast suboptimal list scheduling",
37 static RegisterScheduler
38  linearizeDAGScheduler("linearize", "Linearize DAG, no scheduling",
40 
41 
42 namespace {
43  /// FastPriorityQueue - A degenerate priority queue that considers
44  /// all nodes to have the same priority.
45  ///
46  struct FastPriorityQueue {
48 
49  bool empty() const { return Queue.empty(); }
50 
51  void push(SUnit *U) {
52  Queue.push_back(U);
53  }
54 
55  SUnit *pop() {
56  if (empty()) return nullptr;
57  return Queue.pop_back_val();
58  }
59  };
60 
61 //===----------------------------------------------------------------------===//
62 /// ScheduleDAGFast - The actual "fast" list scheduler implementation.
63 ///
64 class ScheduleDAGFast : public ScheduleDAGSDNodes {
65 private:
66  /// AvailableQueue - The priority queue to use for the available SUnits.
67  FastPriorityQueue AvailableQueue;
68 
69  /// LiveRegDefs - A set of physical registers and their definition
70  /// that are "live". These nodes must be scheduled before any other nodes that
71  /// modifies the registers can be scheduled.
72  unsigned NumLiveRegs;
73  std::vector<SUnit*> LiveRegDefs;
74  std::vector<unsigned> LiveRegCycles;
75 
76 public:
77  ScheduleDAGFast(MachineFunction &mf)
78  : ScheduleDAGSDNodes(mf) {}
79 
80  void Schedule() override;
81 
82  /// AddPred - adds a predecessor edge to SUnit SU.
83  /// This returns true if this is a new predecessor.
84  void AddPred(SUnit *SU, const SDep &D) {
85  SU->addPred(D);
86  }
87 
88  /// RemovePred - removes a predecessor edge from SUnit SU.
89  /// This returns true if an edge was removed.
90  void RemovePred(SUnit *SU, const SDep &D) {
91  SU->removePred(D);
92  }
93 
94 private:
95  void ReleasePred(SUnit *SU, SDep *PredEdge);
96  void ReleasePredecessors(SUnit *SU, unsigned CurCycle);
97  void ScheduleNodeBottomUp(SUnit*, unsigned);
98  SUnit *CopyAndMoveSuccessors(SUnit*);
99  void InsertCopiesAndMoveSuccs(SUnit*, unsigned,
100  const TargetRegisterClass*,
101  const TargetRegisterClass*,
103  bool DelayForLiveRegsBottomUp(SUnit*, SmallVectorImpl<unsigned>&);
104  void ListScheduleBottomUp();
105 
106  /// forceUnitLatencies - The fast scheduler doesn't care about real latencies.
107  bool forceUnitLatencies() const override { return true; }
108 };
109 } // end anonymous namespace
110 
111 
112 /// Schedule - Schedule the DAG using list scheduling.
113 void ScheduleDAGFast::Schedule() {
114  LLVM_DEBUG(dbgs() << "********** List Scheduling **********\n");
115 
116  NumLiveRegs = 0;
117  LiveRegDefs.resize(TRI->getNumRegs(), nullptr);
118  LiveRegCycles.resize(TRI->getNumRegs(), 0);
119 
120  // Build the scheduling graph.
121  BuildSchedGraph(nullptr);
122 
123  LLVM_DEBUG(dump());
124 
125  // Execute the actual scheduling loop.
126  ListScheduleBottomUp();
127 }
128 
129 //===----------------------------------------------------------------------===//
130 // Bottom-Up Scheduling
131 //===----------------------------------------------------------------------===//
132 
133 /// ReleasePred - Decrement the NumSuccsLeft count of a predecessor. Add it to
134 /// the AvailableQueue if the count reaches zero. Also update its cycle bound.
135 void ScheduleDAGFast::ReleasePred(SUnit *SU, SDep *PredEdge) {
136  SUnit *PredSU = PredEdge->getSUnit();
137 
138 #ifndef NDEBUG
139  if (PredSU->NumSuccsLeft == 0) {
140  dbgs() << "*** Scheduling failed! ***\n";
141  dumpNode(*PredSU);
142  dbgs() << " has been released too many times!\n";
143  llvm_unreachable(nullptr);
144  }
145 #endif
146  --PredSU->NumSuccsLeft;
147 
148  // If all the node's successors are scheduled, this node is ready
149  // to be scheduled. Ignore the special EntrySU node.
150  if (PredSU->NumSuccsLeft == 0 && PredSU != &EntrySU) {
151  PredSU->isAvailable = true;
152  AvailableQueue.push(PredSU);
153  }
154 }
155 
156 void ScheduleDAGFast::ReleasePredecessors(SUnit *SU, unsigned CurCycle) {
157  // Bottom up: release predecessors
158  for (SDep &Pred : SU->Preds) {
159  ReleasePred(SU, &Pred);
160  if (Pred.isAssignedRegDep()) {
161  // This is a physical register dependency and it's impossible or
162  // expensive to copy the register. Make sure nothing that can
163  // clobber the register is scheduled between the predecessor and
164  // this node.
165  if (!LiveRegDefs[Pred.getReg()]) {
166  ++NumLiveRegs;
167  LiveRegDefs[Pred.getReg()] = Pred.getSUnit();
168  LiveRegCycles[Pred.getReg()] = CurCycle;
169  }
170  }
171  }
172 }
173 
174 /// ScheduleNodeBottomUp - Add the node to the schedule. Decrement the pending
175 /// count of its predecessors. If a predecessor pending count is zero, add it to
176 /// the Available queue.
177 void ScheduleDAGFast::ScheduleNodeBottomUp(SUnit *SU, unsigned CurCycle) {
178  LLVM_DEBUG(dbgs() << "*** Scheduling [" << CurCycle << "]: ");
179  LLVM_DEBUG(dumpNode(*SU));
180 
181  assert(CurCycle >= SU->getHeight() && "Node scheduled below its height!");
182  SU->setHeightToAtLeast(CurCycle);
183  Sequence.push_back(SU);
184 
185  ReleasePredecessors(SU, CurCycle);
186 
187  // Release all the implicit physical register defs that are live.
188  for (SDep &Succ : SU->Succs) {
189  if (Succ.isAssignedRegDep()) {
190  if (LiveRegCycles[Succ.getReg()] == Succ.getSUnit()->getHeight()) {
191  assert(NumLiveRegs > 0 && "NumLiveRegs is already zero!");
192  assert(LiveRegDefs[Succ.getReg()] == SU &&
193  "Physical register dependency violated?");
194  --NumLiveRegs;
195  LiveRegDefs[Succ.getReg()] = nullptr;
196  LiveRegCycles[Succ.getReg()] = 0;
197  }
198  }
199  }
200 
201  SU->isScheduled = true;
202 }
203 
204 /// CopyAndMoveSuccessors - Clone the specified node and move its scheduled
205 /// successors to the newly created node.
206 SUnit *ScheduleDAGFast::CopyAndMoveSuccessors(SUnit *SU) {
207  if (SU->getNode()->getGluedNode())
208  return nullptr;
209 
210  SDNode *N = SU->getNode();
211  if (!N)
212  return nullptr;
213 
214  SUnit *NewSU;
215  bool TryUnfold = false;
216  for (unsigned i = 0, e = N->getNumValues(); i != e; ++i) {
217  MVT VT = N->getSimpleValueType(i);
218  if (VT == MVT::Glue)
219  return nullptr;
220  else if (VT == MVT::Other)
221  TryUnfold = true;
222  }
223  for (const SDValue &Op : N->op_values()) {
224  MVT VT = Op.getNode()->getSimpleValueType(Op.getResNo());
225  if (VT == MVT::Glue)
226  return nullptr;
227  }
228 
229  if (TryUnfold) {
230  SmallVector<SDNode*, 2> NewNodes;
231  if (!TII->unfoldMemoryOperand(*DAG, N, NewNodes))
232  return nullptr;
233 
234  LLVM_DEBUG(dbgs() << "Unfolding SU # " << SU->NodeNum << "\n");
235  assert(NewNodes.size() == 2 && "Expected a load folding node!");
236 
237  N = NewNodes[1];
238  SDNode *LoadNode = NewNodes[0];
239  unsigned NumVals = N->getNumValues();
240  unsigned OldNumVals = SU->getNode()->getNumValues();
241  for (unsigned i = 0; i != NumVals; ++i)
242  DAG->ReplaceAllUsesOfValueWith(SDValue(SU->getNode(), i), SDValue(N, i));
243  DAG->ReplaceAllUsesOfValueWith(SDValue(SU->getNode(), OldNumVals-1),
244  SDValue(LoadNode, 1));
245 
246  SUnit *NewSU = newSUnit(N);
247  assert(N->getNodeId() == -1 && "Node already inserted!");
248  N->setNodeId(NewSU->NodeNum);
249 
250  const MCInstrDesc &MCID = TII->get(N->getMachineOpcode());
251  for (unsigned i = 0; i != MCID.getNumOperands(); ++i) {
252  if (MCID.getOperandConstraint(i, MCOI::TIED_TO) != -1) {
253  NewSU->isTwoAddress = true;
254  break;
255  }
256  }
257  if (MCID.isCommutable())
258  NewSU->isCommutable = true;
259 
260  // LoadNode may already exist. This can happen when there is another
261  // load from the same location and producing the same type of value
262  // but it has different alignment or volatileness.
263  bool isNewLoad = true;
264  SUnit *LoadSU;
265  if (LoadNode->getNodeId() != -1) {
266  LoadSU = &SUnits[LoadNode->getNodeId()];
267  isNewLoad = false;
268  } else {
269  LoadSU = newSUnit(LoadNode);
270  LoadNode->setNodeId(LoadSU->NodeNum);
271  }
272 
273  SDep ChainPred;
274  SmallVector<SDep, 4> ChainSuccs;
275  SmallVector<SDep, 4> LoadPreds;
276  SmallVector<SDep, 4> NodePreds;
277  SmallVector<SDep, 4> NodeSuccs;
278  for (SDep &Pred : SU->Preds) {
279  if (Pred.isCtrl())
280  ChainPred = Pred;
281  else if (Pred.getSUnit()->getNode() &&
282  Pred.getSUnit()->getNode()->isOperandOf(LoadNode))
283  LoadPreds.push_back(Pred);
284  else
285  NodePreds.push_back(Pred);
286  }
287  for (SDep &Succ : SU->Succs) {
288  if (Succ.isCtrl())
289  ChainSuccs.push_back(Succ);
290  else
291  NodeSuccs.push_back(Succ);
292  }
293 
294  if (ChainPred.getSUnit()) {
295  RemovePred(SU, ChainPred);
296  if (isNewLoad)
297  AddPred(LoadSU, ChainPred);
298  }
299  for (unsigned i = 0, e = LoadPreds.size(); i != e; ++i) {
300  const SDep &Pred = LoadPreds[i];
301  RemovePred(SU, Pred);
302  if (isNewLoad) {
303  AddPred(LoadSU, Pred);
304  }
305  }
306  for (unsigned i = 0, e = NodePreds.size(); i != e; ++i) {
307  const SDep &Pred = NodePreds[i];
308  RemovePred(SU, Pred);
309  AddPred(NewSU, Pred);
310  }
311  for (unsigned i = 0, e = NodeSuccs.size(); i != e; ++i) {
312  SDep D = NodeSuccs[i];
313  SUnit *SuccDep = D.getSUnit();
314  D.setSUnit(SU);
315  RemovePred(SuccDep, D);
316  D.setSUnit(NewSU);
317  AddPred(SuccDep, D);
318  }
319  for (unsigned i = 0, e = ChainSuccs.size(); i != e; ++i) {
320  SDep D = ChainSuccs[i];
321  SUnit *SuccDep = D.getSUnit();
322  D.setSUnit(SU);
323  RemovePred(SuccDep, D);
324  if (isNewLoad) {
325  D.setSUnit(LoadSU);
326  AddPred(SuccDep, D);
327  }
328  }
329  if (isNewLoad) {
330  SDep D(LoadSU, SDep::Barrier);
331  D.setLatency(LoadSU->Latency);
332  AddPred(NewSU, D);
333  }
334 
335  ++NumUnfolds;
336 
337  if (NewSU->NumSuccsLeft == 0) {
338  NewSU->isAvailable = true;
339  return NewSU;
340  }
341  SU = NewSU;
342  }
343 
344  LLVM_DEBUG(dbgs() << "Duplicating SU # " << SU->NodeNum << "\n");
345  NewSU = Clone(SU);
346 
347  // New SUnit has the exact same predecessors.
348  for (SDep &Pred : SU->Preds)
349  if (!Pred.isArtificial())
350  AddPred(NewSU, Pred);
351 
352  // Only copy scheduled successors. Cut them from old node's successor
353  // list and move them over.
355  for (SDep &Succ : SU->Succs) {
356  if (Succ.isArtificial())
357  continue;
358  SUnit *SuccSU = Succ.getSUnit();
359  if (SuccSU->isScheduled) {
360  SDep D = Succ;
361  D.setSUnit(NewSU);
362  AddPred(SuccSU, D);
363  D.setSUnit(SU);
364  DelDeps.push_back(std::make_pair(SuccSU, D));
365  }
366  }
367  for (unsigned i = 0, e = DelDeps.size(); i != e; ++i)
368  RemovePred(DelDeps[i].first, DelDeps[i].second);
369 
370  ++NumDups;
371  return NewSU;
372 }
373 
374 /// InsertCopiesAndMoveSuccs - Insert register copies and move all
375 /// scheduled successors of the given SUnit to the last copy.
376 void ScheduleDAGFast::InsertCopiesAndMoveSuccs(SUnit *SU, unsigned Reg,
377  const TargetRegisterClass *DestRC,
378  const TargetRegisterClass *SrcRC,
380  SUnit *CopyFromSU = newSUnit(static_cast<SDNode *>(nullptr));
381  CopyFromSU->CopySrcRC = SrcRC;
382  CopyFromSU->CopyDstRC = DestRC;
383 
384  SUnit *CopyToSU = newSUnit(static_cast<SDNode *>(nullptr));
385  CopyToSU->CopySrcRC = DestRC;
386  CopyToSU->CopyDstRC = SrcRC;
387 
388  // Only copy scheduled successors. Cut them from old node's successor
389  // list and move them over.
391  for (SDep &Succ : SU->Succs) {
392  if (Succ.isArtificial())
393  continue;
394  SUnit *SuccSU = Succ.getSUnit();
395  if (SuccSU->isScheduled) {
396  SDep D = Succ;
397  D.setSUnit(CopyToSU);
398  AddPred(SuccSU, D);
399  DelDeps.push_back(std::make_pair(SuccSU, Succ));
400  }
401  }
402  for (unsigned i = 0, e = DelDeps.size(); i != e; ++i) {
403  RemovePred(DelDeps[i].first, DelDeps[i].second);
404  }
405  SDep FromDep(SU, SDep::Data, Reg);
406  FromDep.setLatency(SU->Latency);
407  AddPred(CopyFromSU, FromDep);
408  SDep ToDep(CopyFromSU, SDep::Data, 0);
409  ToDep.setLatency(CopyFromSU->Latency);
410  AddPred(CopyToSU, ToDep);
411 
412  Copies.push_back(CopyFromSU);
413  Copies.push_back(CopyToSU);
414 
415  ++NumPRCopies;
416 }
417 
418 /// getPhysicalRegisterVT - Returns the ValueType of the physical register
419 /// definition of the specified node.
420 /// FIXME: Move to SelectionDAG?
422  const TargetInstrInfo *TII) {
423  unsigned NumRes;
424  if (N->getOpcode() == ISD::CopyFromReg) {
425  // CopyFromReg has: "chain, Val, glue" so operand 1 gives the type.
426  NumRes = 1;
427  } else {
428  const MCInstrDesc &MCID = TII->get(N->getMachineOpcode());
429  assert(MCID.ImplicitDefs && "Physical reg def must be in implicit def list!");
430  NumRes = MCID.getNumDefs();
431  for (const MCPhysReg *ImpDef = MCID.getImplicitDefs(); *ImpDef; ++ImpDef) {
432  if (Reg == *ImpDef)
433  break;
434  ++NumRes;
435  }
436  }
437  return N->getSimpleValueType(NumRes);
438 }
439 
440 /// CheckForLiveRegDef - Return true and update live register vector if the
441 /// specified register def of the specified SUnit clobbers any "live" registers.
442 static bool CheckForLiveRegDef(SUnit *SU, unsigned Reg,
443  std::vector<SUnit*> &LiveRegDefs,
444  SmallSet<unsigned, 4> &RegAdded,
446  const TargetRegisterInfo *TRI) {
447  bool Added = false;
448  for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI) {
449  if (LiveRegDefs[*AI] && LiveRegDefs[*AI] != SU) {
450  if (RegAdded.insert(*AI).second) {
451  LRegs.push_back(*AI);
452  Added = true;
453  }
454  }
455  }
456  return Added;
457 }
458 
459 /// DelayForLiveRegsBottomUp - Returns true if it is necessary to delay
460 /// scheduling of the given node to satisfy live physical register dependencies.
461 /// If the specific node is the last one that's available to schedule, do
462 /// whatever is necessary (i.e. backtracking or cloning) to make it possible.
463 bool ScheduleDAGFast::DelayForLiveRegsBottomUp(SUnit *SU,
465  if (NumLiveRegs == 0)
466  return false;
467 
468  SmallSet<unsigned, 4> RegAdded;
469  // If this node would clobber any "live" register, then it's not ready.
470  for (SDep &Pred : SU->Preds) {
471  if (Pred.isAssignedRegDep()) {
472  CheckForLiveRegDef(Pred.getSUnit(), Pred.getReg(), LiveRegDefs,
473  RegAdded, LRegs, TRI);
474  }
475  }
476 
477  for (SDNode *Node = SU->getNode(); Node; Node = Node->getGluedNode()) {
478  if (Node->getOpcode() == ISD::INLINEASM ||
479  Node->getOpcode() == ISD::INLINEASM_BR) {
480  // Inline asm can clobber physical defs.
481  unsigned NumOps = Node->getNumOperands();
482  if (Node->getOperand(NumOps-1).getValueType() == MVT::Glue)
483  --NumOps; // Ignore the glue operand.
484 
485  for (unsigned i = InlineAsm::Op_FirstOperand; i != NumOps;) {
486  unsigned Flags =
487  cast<ConstantSDNode>(Node->getOperand(i))->getZExtValue();
488  unsigned NumVals = InlineAsm::getNumOperandRegisters(Flags);
489 
490  ++i; // Skip the ID value.
491  if (InlineAsm::isRegDefKind(Flags) ||
493  InlineAsm::isClobberKind(Flags)) {
494  // Check for def of register or earlyclobber register.
495  for (; NumVals; --NumVals, ++i) {
496  unsigned Reg = cast<RegisterSDNode>(Node->getOperand(i))->getReg();
498  CheckForLiveRegDef(SU, Reg, LiveRegDefs, RegAdded, LRegs, TRI);
499  }
500  } else
501  i += NumVals;
502  }
503  continue;
504  }
505  if (!Node->isMachineOpcode())
506  continue;
507  const MCInstrDesc &MCID = TII->get(Node->getMachineOpcode());
508  if (!MCID.ImplicitDefs)
509  continue;
510  for (const MCPhysReg *Reg = MCID.getImplicitDefs(); *Reg; ++Reg) {
511  CheckForLiveRegDef(SU, *Reg, LiveRegDefs, RegAdded, LRegs, TRI);
512  }
513  }
514  return !LRegs.empty();
515 }
516 
517 
518 /// ListScheduleBottomUp - The main loop of list scheduling for bottom-up
519 /// schedulers.
520 void ScheduleDAGFast::ListScheduleBottomUp() {
521  unsigned CurCycle = 0;
522 
523  // Release any predecessors of the special Exit node.
524  ReleasePredecessors(&ExitSU, CurCycle);
525 
526  // Add root to Available queue.
527  if (!SUnits.empty()) {
528  SUnit *RootSU = &SUnits[DAG->getRoot().getNode()->getNodeId()];
529  assert(RootSU->Succs.empty() && "Graph root shouldn't have successors!");
530  RootSU->isAvailable = true;
531  AvailableQueue.push(RootSU);
532  }
533 
534  // While Available queue is not empty, grab the node with the highest
535  // priority. If it is not ready put it back. Schedule the node.
536  SmallVector<SUnit*, 4> NotReady;
538  Sequence.reserve(SUnits.size());
539  while (!AvailableQueue.empty()) {
540  bool Delayed = false;
541  LRegsMap.clear();
542  SUnit *CurSU = AvailableQueue.pop();
543  while (CurSU) {
545  if (!DelayForLiveRegsBottomUp(CurSU, LRegs))
546  break;
547  Delayed = true;
548  LRegsMap.insert(std::make_pair(CurSU, LRegs));
549 
550  CurSU->isPending = true; // This SU is not in AvailableQueue right now.
551  NotReady.push_back(CurSU);
552  CurSU = AvailableQueue.pop();
553  }
554 
555  // All candidates are delayed due to live physical reg dependencies.
556  // Try code duplication or inserting cross class copies
557  // to resolve it.
558  if (Delayed && !CurSU) {
559  if (!CurSU) {
560  // Try duplicating the nodes that produces these
561  // "expensive to copy" values to break the dependency. In case even
562  // that doesn't work, insert cross class copies.
563  SUnit *TrySU = NotReady[0];
564  SmallVectorImpl<unsigned> &LRegs = LRegsMap[TrySU];
565  assert(LRegs.size() == 1 && "Can't handle this yet!");
566  unsigned Reg = LRegs[0];
567  SUnit *LRDef = LiveRegDefs[Reg];
568  MVT VT = getPhysicalRegisterVT(LRDef->getNode(), Reg, TII);
569  const TargetRegisterClass *RC =
571  const TargetRegisterClass *DestRC = TRI->getCrossCopyRegClass(RC);
572 
573  // If cross copy register class is the same as RC, then it must be
574  // possible copy the value directly. Do not try duplicate the def.
575  // If cross copy register class is not the same as RC, then it's
576  // possible to copy the value but it require cross register class copies
577  // and it is expensive.
578  // If cross copy register class is null, then it's not possible to copy
579  // the value at all.
580  SUnit *NewDef = nullptr;
581  if (DestRC != RC) {
582  NewDef = CopyAndMoveSuccessors(LRDef);
583  if (!DestRC && !NewDef)
584  report_fatal_error("Can't handle live physical "
585  "register dependency!");
586  }
587  if (!NewDef) {
588  // Issue copies, these can be expensive cross register class copies.
590  InsertCopiesAndMoveSuccs(LRDef, Reg, DestRC, RC, Copies);
591  LLVM_DEBUG(dbgs() << "Adding an edge from SU # " << TrySU->NodeNum
592  << " to SU #" << Copies.front()->NodeNum << "\n");
593  AddPred(TrySU, SDep(Copies.front(), SDep::Artificial));
594  NewDef = Copies.back();
595  }
596 
597  LLVM_DEBUG(dbgs() << "Adding an edge from SU # " << NewDef->NodeNum
598  << " to SU #" << TrySU->NodeNum << "\n");
599  LiveRegDefs[Reg] = NewDef;
600  AddPred(NewDef, SDep(TrySU, SDep::Artificial));
601  TrySU->isAvailable = false;
602  CurSU = NewDef;
603  }
604 
605  if (!CurSU) {
606  llvm_unreachable("Unable to resolve live physical register dependencies!");
607  }
608  }
609 
610  // Add the nodes that aren't ready back onto the available list.
611  for (unsigned i = 0, e = NotReady.size(); i != e; ++i) {
612  NotReady[i]->isPending = false;
613  // May no longer be available due to backtracking.
614  if (NotReady[i]->isAvailable)
615  AvailableQueue.push(NotReady[i]);
616  }
617  NotReady.clear();
618 
619  if (CurSU)
620  ScheduleNodeBottomUp(CurSU, CurCycle);
621  ++CurCycle;
622  }
623 
624  // Reverse the order since it is bottom up.
625  std::reverse(Sequence.begin(), Sequence.end());
626 
627 #ifndef NDEBUG
628  VerifyScheduledSequence(/*isBottomUp=*/true);
629 #endif
630 }
631 
632 
633 namespace {
634 //===----------------------------------------------------------------------===//
635 // ScheduleDAGLinearize - No scheduling scheduler, it simply linearize the
636 // DAG in topological order.
637 // IMPORTANT: this may not work for targets with phyreg dependency.
638 //
639 class ScheduleDAGLinearize : public ScheduleDAGSDNodes {
640 public:
641  ScheduleDAGLinearize(MachineFunction &mf) : ScheduleDAGSDNodes(mf) {}
642 
643  void Schedule() override;
644 
646  EmitSchedule(MachineBasicBlock::iterator &InsertPos) override;
647 
648 private:
649  std::vector<SDNode*> Sequence;
650  DenseMap<SDNode*, SDNode*> GluedMap; // Cache glue to its user
651 
652  void ScheduleNode(SDNode *N);
653 };
654 } // end anonymous namespace
655 
656 void ScheduleDAGLinearize::ScheduleNode(SDNode *N) {
657  if (N->getNodeId() != 0)
658  llvm_unreachable(nullptr);
659 
660  if (!N->isMachineOpcode() &&
661  (N->getOpcode() == ISD::EntryToken || isPassiveNode(N)))
662  // These nodes do not need to be translated into MIs.
663  return;
664 
665  LLVM_DEBUG(dbgs() << "\n*** Scheduling: ");
666  LLVM_DEBUG(N->dump(DAG));
667  Sequence.push_back(N);
668 
669  unsigned NumOps = N->getNumOperands();
670  if (unsigned NumLeft = NumOps) {
671  SDNode *GluedOpN = nullptr;
672  do {
673  const SDValue &Op = N->getOperand(NumLeft-1);
674  SDNode *OpN = Op.getNode();
675 
676  if (NumLeft == NumOps && Op.getValueType() == MVT::Glue) {
677  // Schedule glue operand right above N.
678  GluedOpN = OpN;
679  assert(OpN->getNodeId() != 0 && "Glue operand not ready?");
680  OpN->setNodeId(0);
681  ScheduleNode(OpN);
682  continue;
683  }
684 
685  if (OpN == GluedOpN)
686  // Glue operand is already scheduled.
687  continue;
688 
689  DenseMap<SDNode*, SDNode*>::iterator DI = GluedMap.find(OpN);
690  if (DI != GluedMap.end() && DI->second != N)
691  // Users of glues are counted against the glued users.
692  OpN = DI->second;
693 
694  unsigned Degree = OpN->getNodeId();
695  assert(Degree > 0 && "Predecessor over-released!");
696  OpN->setNodeId(--Degree);
697  if (Degree == 0)
698  ScheduleNode(OpN);
699  } while (--NumLeft);
700  }
701 }
702 
703 /// findGluedUser - Find the representative use of a glue value by walking
704 /// the use chain.
706  while (SDNode *Glued = N->getGluedUser())
707  N = Glued;
708  return N;
709 }
710 
711 void ScheduleDAGLinearize::Schedule() {
712  LLVM_DEBUG(dbgs() << "********** DAG Linearization **********\n");
713 
715  unsigned DAGSize = 0;
716  for (SDNode &Node : DAG->allnodes()) {
717  SDNode *N = &Node;
718 
719  // Use node id to record degree.
720  unsigned Degree = N->use_size();
721  N->setNodeId(Degree);
722  unsigned NumVals = N->getNumValues();
723  if (NumVals && N->getValueType(NumVals-1) == MVT::Glue &&
724  N->hasAnyUseOfValue(NumVals-1)) {
726  if (User) {
727  Glues.push_back(N);
728  GluedMap.insert(std::make_pair(N, User));
729  }
730  }
731 
732  if (N->isMachineOpcode() ||
733  (N->getOpcode() != ISD::EntryToken && !isPassiveNode(N)))
734  ++DAGSize;
735  }
736 
737  for (unsigned i = 0, e = Glues.size(); i != e; ++i) {
738  SDNode *Glue = Glues[i];
739  SDNode *GUser = GluedMap[Glue];
740  unsigned Degree = Glue->getNodeId();
741  unsigned UDegree = GUser->getNodeId();
742 
743  // Glue user must be scheduled together with the glue operand. So other
744  // users of the glue operand must be treated as its users.
745  SDNode *ImmGUser = Glue->getGluedUser();
746  for (const SDNode *U : Glue->uses())
747  if (U == ImmGUser)
748  --Degree;
749  GUser->setNodeId(UDegree + Degree);
750  Glue->setNodeId(1);
751  }
752 
753  Sequence.reserve(DAGSize);
754  ScheduleNode(DAG->getRoot().getNode());
755 }
756 
758 ScheduleDAGLinearize::EmitSchedule(MachineBasicBlock::iterator &InsertPos) {
759  InstrEmitter Emitter(DAG->getTarget(), BB, InsertPos,
760  DAG->getUseInstrRefDebugInfo());
761  DenseMap<SDValue, Register> VRBaseMap;
762 
763  LLVM_DEBUG({ dbgs() << "\n*** Final schedule ***\n"; });
764 
765  unsigned NumNodes = Sequence.size();
766  MachineBasicBlock *BB = Emitter.getBlock();
767  for (unsigned i = 0; i != NumNodes; ++i) {
768  SDNode *N = Sequence[NumNodes-i-1];
769  LLVM_DEBUG(N->dump(DAG));
770  Emitter.EmitNode(N, false, false, VRBaseMap);
771 
772  // Emit any debug values associated with the node.
773  if (N->getHasDebugValue()) {
774  MachineBasicBlock::iterator InsertPos = Emitter.getInsertPos();
775  for (auto DV : DAG->GetDbgValues(N)) {
776  if (!DV->isEmitted())
777  if (auto *DbgMI = Emitter.EmitDbgValue(DV, VRBaseMap))
778  BB->insert(InsertPos, DbgMI);
779  }
780  }
781  }
782 
783  LLVM_DEBUG(dbgs() << '\n');
784 
785  InsertPos = Emitter.getInsertPos();
786  return Emitter.getBlock();
787 }
788 
789 //===----------------------------------------------------------------------===//
790 // Public Constructor Functions
791 //===----------------------------------------------------------------------===//
792 
795  return new ScheduleDAGFast(*IS->MF);
796 }
797 
800  return new ScheduleDAGLinearize(*IS->MF);
801 }
i
i
Definition: README.txt:29
llvm::MCInstrDesc::getNumDefs
unsigned getNumDefs() const
Return the number of MachineOperands that are register definitions.
Definition: MCInstrDesc.h:245
llvm::InstrEmitter
Definition: InstrEmitter.h:32
llvm::createDAGLinearizer
ScheduleDAGSDNodes * createDAGLinearizer(SelectionDAGISel *IS, CodeGenOpt::Level OptLevel)
createDAGLinearizer - This creates a "no-scheduling" scheduler which linearize the DAG using topologi...
Definition: ScheduleDAGFast.cpp:799
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
llvm::TargetRegisterInfo::getCrossCopyRegClass
virtual const TargetRegisterClass * getCrossCopyRegClass(const TargetRegisterClass *RC) const
Returns a legal register class to copy a register in the specified class to or from.
Definition: TargetRegisterInfo.h:779
llvm::objcarc::Sequence
Sequence
Definition: PtrState.h:41
linearizeDAGScheduler
static RegisterScheduler linearizeDAGScheduler("linearize", "Linearize DAG, no scheduling", createDAGLinearizer)
llvm::ScheduleDAGSDNodes
ScheduleDAGSDNodes - A ScheduleDAG for scheduling SDNode-based DAGs.
Definition: ScheduleDAGSDNodes.h:46
llvm::SDep::Artificial
@ Artificial
Arbitrary strong DAG edge (no real dependence).
Definition: ScheduleDAG.h:72
llvm::SUnit::isAvailable
bool isAvailable
True once available.
Definition: ScheduleDAG.h:283
SchedulerRegistry.h
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1185
Statistic.h
InlineAsm.h
ErrorHandling.h
llvm::MCRegisterInfo::getNumRegs
unsigned getNumRegs() const
Return the number of registers this target has (useful for sizing arrays holding per register informa...
Definition: MCRegisterInfo.h:491
llvm::X86Disassembler::Reg
Reg
All possible values of the reg field in the ModR/M byte.
Definition: X86DisassemblerDecoder.h:462
llvm::SUnit::NumSuccsLeft
unsigned NumSuccsLeft
Definition: ScheduleDAG.h:269
llvm::SUnit::isCommutable
bool isCommutable
Is a commutable instruction.
Definition: ScheduleDAG.h:278
push
static void push(SmallVectorImpl< uint64_t > &R, StringRef Str)
Definition: BitstreamRemarkSerializer.cpp:24
llvm::createFastDAGScheduler
ScheduleDAGSDNodes * createFastDAGScheduler(SelectionDAGISel *IS, CodeGenOpt::Level OptLevel)
createFastDAGScheduler - This creates a "fast" scheduler.
Definition: ScheduleDAGFast.cpp:794
llvm::SDNode
Represents one node in the SelectionDAG.
Definition: SelectionDAGNodes.h:454
llvm::MVT::Glue
@ Glue
Definition: MachineValueType.h:270
llvm::TargetRegisterInfo
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
Definition: TargetRegisterInfo.h:234
llvm::reverse
auto reverse(ContainerTy &&C, std::enable_if_t< has_rbegin< ContainerTy >::value > *=nullptr)
Definition: STLExtras.h:380
TargetInstrInfo.h
llvm::SmallSet
SmallSet - This maintains a set of unique values, optimizing for the case when the set is small (less...
Definition: SmallSet.h:136
llvm::SUnit::Succs
SmallVector< SDep, 4 > Succs
All sunit successors.
Definition: ScheduleDAG.h:257
llvm::dump
void dump(const SparseBitVector< ElementSize > &LHS, raw_ostream &out)
Definition: SparseBitVector.h:877
SDNodeDbgValue.h
TRI
unsigned const TargetRegisterInfo * TRI
Definition: MachineSink.cpp:1628
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
llvm::AMDGPU::HSAMD::ValueKind::Queue
@ Queue
llvm::ISD::INLINEASM
@ INLINEASM
INLINEASM - Represents an inline asm block.
Definition: ISDOpcodes.h:1025
llvm::SDep::isArtificial
bool isArtificial() const
Tests if this is an Order dependence that is marked as "artificial", meaning it isn't necessary for c...
Definition: ScheduleDAG.h:200
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
llvm::SUnit::removePred
void removePred(const SDep &D)
Removes the specified edge as a pred of the current node if it exists.
Definition: ScheduleDAG.cpp:175
llvm::TargetInstrInfo
TargetInstrInfo - Interface to description of machine instruction set.
Definition: TargetInstrInfo.h:97
llvm::User
Definition: User.h:44
llvm::SUnit::setHeightToAtLeast
void setHeightToAtLeast(unsigned NewHeight)
If NewHeight is greater than this node's height value, set it to be the new height value.
Definition: ScheduleDAG.cpp:255
llvm::SUnit::Latency
unsigned short Latency
Node latency.
Definition: ScheduleDAG.h:273
fastDAGScheduler
static RegisterScheduler fastDAGScheduler("fast", "Fast suboptimal list scheduling", createFastDAGScheduler)
llvm::SUnit::NodeNum
unsigned NodeNum
Entry # of node in the node vector.
Definition: ScheduleDAG.h:264
llvm::Register::isPhysicalRegister
static bool isPhysicalRegister(unsigned Reg)
Return true if the specified register number is in the physical register namespace.
Definition: Register.h:65
llvm::TargetRegisterClass
Definition: TargetRegisterInfo.h:45
llvm::MCInstrDesc::getImplicitDefs
const MCPhysReg * getImplicitDefs() const
Return a list of registers that are potentially written by any instance of this machine instruction.
Definition: MCInstrDesc.h:587
TII
const HexagonInstrInfo * TII
Definition: HexagonCopyToCombine.cpp:125
llvm::MCInstrDesc
Describe properties that are true of each instruction in the target description file.
Definition: MCInstrDesc.h:197
llvm::MCInstrDesc::isCommutable
bool isCommutable() const
Return true if this may be a 2- or 3-address instruction (of the form "X = op Y, Z,...
Definition: MCInstrDesc.h:478
llvm::SDNode::uses
iterator_range< use_iterator > uses()
Definition: SelectionDAGNodes.h:793
llvm::InlineAsm::isRegDefKind
static bool isRegDefKind(unsigned Flag)
Definition: InlineAsm.h:294
llvm::report_fatal_error
void report_fatal_error(Error Err, bool gen_crash_diag=true)
Report a serious error, calling any installed error handler.
Definition: Error.cpp:143
llvm::STATISTIC
STATISTIC(NumFunctions, "Total number of functions")
ScheduleDAGSDNodes.h
llvm::SDep::Data
@ Data
Regular data dependence (aka true-dependence).
Definition: ScheduleDAG.h:53
Copies
SI Lower i1 Copies
Definition: SILowerI1Copies.cpp:406
llvm::ISD::EntryToken
@ EntryToken
EntryToken - This is the marker used to indicate the start of a region.
Definition: ISDOpcodes.h:47
llvm::ISD::CopyFromReg
@ CopyFromReg
CopyFromReg - This node indicates that the input value is a virtual or physical register that is defi...
Definition: ISDOpcodes.h:208
llvm::MachineBasicBlock
Definition: MachineBasicBlock.h:94
llvm::SUnit::getHeight
unsigned getHeight() const
Returns the height of this node, which is the length of the maximum path down to any node which has n...
Definition: ScheduleDAG.h:406
llvm::SDNode::getGluedUser
SDNode * getGluedUser() const
If this node has a glue value with a user, return the user (there is at most one).
Definition: SelectionDAGNodes.h:952
llvm::SUnit::isPending
bool isPending
True once pending.
Definition: ScheduleDAG.h:282
findGluedUser
static SDNode * findGluedUser(SDNode *N)
findGluedUser - Find the representative use of a glue value by walking the use chain.
Definition: ScheduleDAGFast.cpp:705
llvm::InlineAsm::isRegDefEarlyClobberKind
static bool isRegDefEarlyClobberKind(unsigned Flag)
Definition: InlineAsm.h:297
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::clear
void clear()
Definition: DenseMap.h:112
llvm::SUnit::CopyDstRC
const TargetRegisterClass * CopyDstRC
Is a special copy node if != nullptr.
Definition: ScheduleDAG.h:302
D
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
llvm::numbers::e
constexpr double e
Definition: MathExtras.h:57
llvm::SDNode::setNodeId
void setNodeId(int Id)
Set unique node id.
Definition: SelectionDAGNodes.h:716
llvm::DenseMap
Definition: DenseMap.h:716
llvm::MCPhysReg
uint16_t MCPhysReg
An unsigned integer type large enough to represent all physical registers, but not necessarily virtua...
Definition: MCRegister.h:21
llvm::SDep::getReg
unsigned getReg() const
Returns the register associated with this edge.
Definition: ScheduleDAG.h:218
llvm::SUnit::isScheduled
bool isScheduled
True once scheduled.
Definition: ScheduleDAG.h:284
llvm::DenseMapBase::find
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:152
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::MVT::Other
@ Other
Definition: MachineValueType.h:42
llvm::SDNode::getNodeId
int getNodeId() const
Return the unique node id.
Definition: SelectionDAGNodes.h:713
llvm::SUnit::CopySrcRC
const TargetRegisterClass * CopySrcRC
Definition: ScheduleDAG.h:304
llvm::zlib::isAvailable
bool isAvailable()
Definition: Compression.cpp:47
llvm::MVT
Machine Value Type.
Definition: MachineValueType.h:31
llvm::MachineFunction
Definition: MachineFunction.h:257
SelectionDAGISel.h
llvm::SDep::getSUnit
SUnit * getSUnit() const
Definition: ScheduleDAG.h:480
llvm_unreachable
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Definition: ErrorHandling.h:143
llvm::SDNode::isOperandOf
bool isOperandOf(const SDNode *N) const
Return true if this node is an operand of N.
Definition: SelectionDAG.cpp:10806
llvm::InlineAsm::isClobberKind
static bool isClobberKind(unsigned Flag)
Definition: InlineAsm.h:300
llvm::SDep::Barrier
@ Barrier
An unknown scheduling barrier.
Definition: ScheduleDAG.h:69
InstrEmitter.h
llvm::CodeGenOpt::Level
Level
Definition: CodeGen.h:52
llvm::SmallSet::insert
std::pair< NoneType, bool > insert(const T &V)
insert - Insert an element into the set if it isn't already there.
Definition: SmallSet.h:182
llvm::DenseMapBase< DenseMap< KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::insert
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: DenseMap.h:209
llvm::SDep::isAssignedRegDep
bool isAssignedRegDep() const
Tests if this is a Data dependence that is associated with a register.
Definition: ScheduleDAG.h:211
llvm::SDep
Scheduling dependency.
Definition: ScheduleDAG.h:49
llvm::SelectionDAGISel::MF
MachineFunction * MF
Definition: SelectionDAGISel.h:46
llvm::empty
constexpr bool empty(const T &RangeOrContainer)
Test whether RangeOrContainer is empty. Similar to C++17 std::empty.
Definition: STLExtras.h:268
CheckForLiveRegDef
static bool CheckForLiveRegDef(SUnit *SU, unsigned Reg, std::vector< SUnit * > &LiveRegDefs, SmallSet< unsigned, 4 > &RegAdded, SmallVectorImpl< unsigned > &LRegs, const TargetRegisterInfo *TRI)
CheckForLiveRegDef - Return true and update live register vector if the specified register def of the...
Definition: ScheduleDAGFast.cpp:442
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:345
llvm::SUnit::getNode
SDNode * getNode() const
Returns the representative SDNode for this SUnit.
Definition: ScheduleDAG.h:355
llvm::RegisterScheduler
Definition: SchedulerRegistry.h:31
llvm::ISD::INLINEASM_BR
@ INLINEASM_BR
INLINEASM_BR - Branching version of inline asm. Used by asm-goto.
Definition: ISDOpcodes.h:1028
llvm::SDValue
Unlike LLVM values, Selection DAG nodes may return multiple values as the result of a computation.
Definition: SelectionDAGNodes.h:137
llvm::SUnit::addPred
bool addPred(const SDep &D, bool Required=true)
Adds the specified edge as a pred of the current node if not already.
Definition: ScheduleDAG.cpp:107
llvm::SDNode::getNumValues
unsigned getNumValues() const
Return the number of values defined/returned by this operator.
Definition: SelectionDAGNodes.h:967
llvm::SmallVectorImpl::clear
void clear()
Definition: SmallVector.h:591
llvm::SUnit::isTwoAddress
bool isTwoAddress
Is a two-address instruction.
Definition: ScheduleDAG.h:277
llvm::MCRegAliasIterator::isValid
bool isValid() const
Definition: MCRegisterInfo.h:813
llvm::SelectionDAGISel
SelectionDAGISel - This is the common base class used for SelectionDAG-based pattern-matching instruc...
Definition: SelectionDAGISel.h:40
llvm::InlineAsm::getNumOperandRegisters
static unsigned getNumOperandRegisters(unsigned Flag)
getNumOperandRegisters - Extract the number of registers field from the inline asm operand flag.
Definition: InlineAsm.h:355
N
#define N
llvm::SmallVectorImpl
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
Definition: APFloat.h:42
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::MCOI::TIED_TO
@ TIED_TO
Definition: MCInstrDesc.h:35
llvm::TargetRegisterInfo::getMinimalPhysRegClass
const TargetRegisterClass * getMinimalPhysRegClass(MCRegister Reg, MVT VT=MVT::Other) const
Returns the Register Class of a physical register of the given type, picking the most sub register cl...
Definition: TargetRegisterInfo.cpp:212
raw_ostream.h
llvm::MachineInstrBundleIterator< MachineInstr >
getPhysicalRegisterVT
static MVT getPhysicalRegisterVT(SDNode *N, unsigned Reg, const TargetInstrInfo *TII)
getPhysicalRegisterVT - Returns the ValueType of the physical register definition of the specified no...
Definition: ScheduleDAGFast.cpp:421
llvm::MCInstrDesc::getOperandConstraint
int getOperandConstraint(unsigned OpNum, MCOI::OperandConstraint Constraint) const
Returns the value of the specified operand constraint if it is present.
Definition: MCInstrDesc.h:212
llvm::InlineAsm::Op_FirstOperand
@ Op_FirstOperand
Definition: InlineAsm.h:220
llvm::SDep::isCtrl
bool isCtrl() const
Shorthand for getKind() != SDep::Data.
Definition: ScheduleDAG.h:161
llvm::MCInstrDesc::getNumOperands
unsigned getNumOperands() const
Return the number of declared MachineOperands for this MachineInstruction.
Definition: MCInstrDesc.h:230
TargetRegisterInfo.h
Debug.h
llvm::MCRegAliasIterator
MCRegAliasIterator enumerates all registers aliasing Reg.
Definition: MCRegisterInfo.h:788
llvm::SDNode::getGluedNode
SDNode * getGluedNode() const
If this node has a glue operand, return the node to which the glue operand points.
Definition: SelectionDAGNodes.h:943
llvm::MCInstrDesc::ImplicitDefs
const MCPhysReg * ImplicitDefs
Definition: MCInstrDesc.h:207
SmallSet.h
llvm::SmallVectorImpl::insert
iterator insert(iterator I, T &&Elt)
Definition: SmallVector.h:792