LLVM  10.0.0svn
ScheduleDAG.cpp
Go to the documentation of this file.
1 //===- ScheduleDAG.cpp - Implement the ScheduleDAG class ------------------===//
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 /// \file Implements the ScheduleDAG class, which is a base class used by
10 /// scheduling implementation classes.
11 //
12 //===----------------------------------------------------------------------===//
13 
15 #include "llvm/ADT/STLExtras.h"
16 #include "llvm/ADT/SmallVector.h"
17 #include "llvm/ADT/Statistic.h"
25 #include "llvm/Config/llvm-config.h"
27 #include "llvm/Support/Compiler.h"
28 #include "llvm/Support/Debug.h"
30 #include <algorithm>
31 #include <cassert>
32 #include <iterator>
33 #include <limits>
34 #include <utility>
35 #include <vector>
36 
37 using namespace llvm;
38 
39 #define DEBUG_TYPE "pre-RA-sched"
40 
41 STATISTIC(NumNewPredsAdded, "Number of times a single predecessor was added");
42 STATISTIC(NumTopoInits,
43  "Number of times the topological order has been recomputed");
44 
45 #ifndef NDEBUG
47  "stress-sched", cl::Hidden, cl::init(false),
48  cl::desc("Stress test instruction scheduling"));
49 #endif
50 
51 void SchedulingPriorityQueue::anchor() {}
52 
54  : TM(mf.getTarget()), TII(mf.getSubtarget().getInstrInfo()),
55  TRI(mf.getSubtarget().getRegisterInfo()), MF(mf),
56  MRI(mf.getRegInfo()) {
57 #ifndef NDEBUG
59 #endif
60 }
61 
62 ScheduleDAG::~ScheduleDAG() = default;
63 
65  SUnits.clear();
66  EntrySU = SUnit();
67  ExitSU = SUnit();
68 }
69 
70 const MCInstrDesc *ScheduleDAG::getNodeDesc(const SDNode *Node) const {
71  if (!Node || !Node->isMachineOpcode()) return nullptr;
72  return &TII->get(Node->getMachineOpcode());
73 }
74 
76  switch (getKind()) {
77  case Data: dbgs() << "Data"; break;
78  case Anti: dbgs() << "Anti"; break;
79  case Output: dbgs() << "Out "; break;
80  case Order: dbgs() << "Ord "; break;
81  }
82 
83  switch (getKind()) {
84  case Data:
85  dbgs() << " Latency=" << getLatency();
86  if (TRI && isAssignedRegDep())
87  dbgs() << " Reg=" << printReg(getReg(), TRI);
88  break;
89  case Anti:
90  case Output:
91  dbgs() << " Latency=" << getLatency();
92  break;
93  case Order:
94  dbgs() << " Latency=" << getLatency();
95  switch(Contents.OrdKind) {
96  case Barrier: dbgs() << " Barrier"; break;
97  case MayAliasMem:
98  case MustAliasMem: dbgs() << " Memory"; break;
99  case Artificial: dbgs() << " Artificial"; break;
100  case Weak: dbgs() << " Weak"; break;
101  case Cluster: dbgs() << " Cluster"; break;
102  }
103  break;
104  }
105 }
106 
107 bool SUnit::addPred(const SDep &D, bool Required) {
108  // If this node already has this dependence, don't add a redundant one.
109  for (SDep &PredDep : Preds) {
110  // Zero-latency weak edges may be added purely for heuristic ordering. Don't
111  // add them if another kind of edge already exists.
112  if (!Required && PredDep.getSUnit() == D.getSUnit())
113  return false;
114  if (PredDep.overlaps(D)) {
115  // Extend the latency if needed. Equivalent to
116  // removePred(PredDep) + addPred(D).
117  if (PredDep.getLatency() < D.getLatency()) {
118  SUnit *PredSU = PredDep.getSUnit();
119  // Find the corresponding successor in N.
120  SDep ForwardD = PredDep;
121  ForwardD.setSUnit(this);
122  for (SDep &SuccDep : PredSU->Succs) {
123  if (SuccDep == ForwardD) {
124  SuccDep.setLatency(D.getLatency());
125  break;
126  }
127  }
128  PredDep.setLatency(D.getLatency());
129  }
130  return false;
131  }
132  }
133  // Now add a corresponding succ to N.
134  SDep P = D;
135  P.setSUnit(this);
136  SUnit *N = D.getSUnit();
137  // Update the bookkeeping.
138  if (D.getKind() == SDep::Data) {
140  "NumPreds will overflow!");
142  "NumSuccs will overflow!");
143  ++NumPreds;
144  ++N->NumSuccs;
145  }
146  if (!N->isScheduled) {
147  if (D.isWeak()) {
148  ++WeakPredsLeft;
149  }
150  else {
151  assert(NumPredsLeft < std::numeric_limits<unsigned>::max() &&
152  "NumPredsLeft will overflow!");
153  ++NumPredsLeft;
154  }
155  }
156  if (!isScheduled) {
157  if (D.isWeak()) {
158  ++N->WeakSuccsLeft;
159  }
160  else {
162  "NumSuccsLeft will overflow!");
163  ++N->NumSuccsLeft;
164  }
165  }
166  Preds.push_back(D);
167  N->Succs.push_back(P);
168  if (P.getLatency() != 0) {
169  this->setDepthDirty();
170  N->setHeightDirty();
171  }
172  return true;
173 }
174 
175 void SUnit::removePred(const SDep &D) {
176  // Find the matching predecessor.
178  if (I == Preds.end())
179  return;
180  // Find the corresponding successor in N.
181  SDep P = D;
182  P.setSUnit(this);
183  SUnit *N = D.getSUnit();
185  assert(Succ != N->Succs.end() && "Mismatching preds / succs lists!");
186  N->Succs.erase(Succ);
187  Preds.erase(I);
188  // Update the bookkeeping.
189  if (P.getKind() == SDep::Data) {
190  assert(NumPreds > 0 && "NumPreds will underflow!");
191  assert(N->NumSuccs > 0 && "NumSuccs will underflow!");
192  --NumPreds;
193  --N->NumSuccs;
194  }
195  if (!N->isScheduled) {
196  if (D.isWeak())
197  --WeakPredsLeft;
198  else {
199  assert(NumPredsLeft > 0 && "NumPredsLeft will underflow!");
200  --NumPredsLeft;
201  }
202  }
203  if (!isScheduled) {
204  if (D.isWeak())
205  --N->WeakSuccsLeft;
206  else {
207  assert(N->NumSuccsLeft > 0 && "NumSuccsLeft will underflow!");
208  --N->NumSuccsLeft;
209  }
210  }
211  if (P.getLatency() != 0) {
212  this->setDepthDirty();
213  N->setHeightDirty();
214  }
215 }
216 
218  if (!isDepthCurrent) return;
219  SmallVector<SUnit*, 8> WorkList;
220  WorkList.push_back(this);
221  do {
222  SUnit *SU = WorkList.pop_back_val();
223  SU->isDepthCurrent = false;
224  for (SDep &SuccDep : SU->Succs) {
225  SUnit *SuccSU = SuccDep.getSUnit();
226  if (SuccSU->isDepthCurrent)
227  WorkList.push_back(SuccSU);
228  }
229  } while (!WorkList.empty());
230 }
231 
233  if (!isHeightCurrent) return;
234  SmallVector<SUnit*, 8> WorkList;
235  WorkList.push_back(this);
236  do {
237  SUnit *SU = WorkList.pop_back_val();
238  SU->isHeightCurrent = false;
239  for (SDep &PredDep : SU->Preds) {
240  SUnit *PredSU = PredDep.getSUnit();
241  if (PredSU->isHeightCurrent)
242  WorkList.push_back(PredSU);
243  }
244  } while (!WorkList.empty());
245 }
246 
247 void SUnit::setDepthToAtLeast(unsigned NewDepth) {
248  if (NewDepth <= getDepth())
249  return;
250  setDepthDirty();
251  Depth = NewDepth;
252  isDepthCurrent = true;
253 }
254 
255 void SUnit::setHeightToAtLeast(unsigned NewHeight) {
256  if (NewHeight <= getHeight())
257  return;
258  setHeightDirty();
259  Height = NewHeight;
260  isHeightCurrent = true;
261 }
262 
263 /// Calculates the maximal path from the node to the exit.
264 void SUnit::ComputeDepth() {
265  SmallVector<SUnit*, 8> WorkList;
266  WorkList.push_back(this);
267  do {
268  SUnit *Cur = WorkList.back();
269 
270  bool Done = true;
271  unsigned MaxPredDepth = 0;
272  for (const SDep &PredDep : Cur->Preds) {
273  SUnit *PredSU = PredDep.getSUnit();
274  if (PredSU->isDepthCurrent)
275  MaxPredDepth = std::max(MaxPredDepth,
276  PredSU->Depth + PredDep.getLatency());
277  else {
278  Done = false;
279  WorkList.push_back(PredSU);
280  }
281  }
282 
283  if (Done) {
284  WorkList.pop_back();
285  if (MaxPredDepth != Cur->Depth) {
286  Cur->setDepthDirty();
287  Cur->Depth = MaxPredDepth;
288  }
289  Cur->isDepthCurrent = true;
290  }
291  } while (!WorkList.empty());
292 }
293 
294 /// Calculates the maximal path from the node to the entry.
295 void SUnit::ComputeHeight() {
296  SmallVector<SUnit*, 8> WorkList;
297  WorkList.push_back(this);
298  do {
299  SUnit *Cur = WorkList.back();
300 
301  bool Done = true;
302  unsigned MaxSuccHeight = 0;
303  for (const SDep &SuccDep : Cur->Succs) {
304  SUnit *SuccSU = SuccDep.getSUnit();
305  if (SuccSU->isHeightCurrent)
306  MaxSuccHeight = std::max(MaxSuccHeight,
307  SuccSU->Height + SuccDep.getLatency());
308  else {
309  Done = false;
310  WorkList.push_back(SuccSU);
311  }
312  }
313 
314  if (Done) {
315  WorkList.pop_back();
316  if (MaxSuccHeight != Cur->Height) {
317  Cur->setHeightDirty();
318  Cur->Height = MaxSuccHeight;
319  }
320  Cur->isHeightCurrent = true;
321  }
322  } while (!WorkList.empty());
323 }
324 
326  if (NumPreds < 2)
327  return;
328 
329  SUnit::pred_iterator BestI = Preds.begin();
330  unsigned MaxDepth = BestI->getSUnit()->getDepth();
331  for (SUnit::pred_iterator I = std::next(BestI), E = Preds.end(); I != E;
332  ++I) {
333  if (I->getKind() == SDep::Data && I->getSUnit()->getDepth() > MaxDepth)
334  BestI = I;
335  }
336  if (BestI != Preds.begin())
337  std::swap(*Preds.begin(), *BestI);
338 }
339 
340 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
342  dbgs() << " # preds left : " << NumPredsLeft << "\n";
343  dbgs() << " # succs left : " << NumSuccsLeft << "\n";
344  if (WeakPredsLeft)
345  dbgs() << " # weak preds left : " << WeakPredsLeft << "\n";
346  if (WeakSuccsLeft)
347  dbgs() << " # weak succs left : " << WeakSuccsLeft << "\n";
348  dbgs() << " # rdefs left : " << NumRegDefsLeft << "\n";
349  dbgs() << " Latency : " << Latency << "\n";
350  dbgs() << " Depth : " << getDepth() << "\n";
351  dbgs() << " Height : " << getHeight() << "\n";
352 }
353 
355  if (&SU == &EntrySU)
356  dbgs() << "EntrySU";
357  else if (&SU == &ExitSU)
358  dbgs() << "ExitSU";
359  else
360  dbgs() << "SU(" << SU.NodeNum << ")";
361 }
362 
364  dumpNode(SU);
365  SU.dumpAttributes();
366  if (SU.Preds.size() > 0) {
367  dbgs() << " Predecessors:\n";
368  for (const SDep &Dep : SU.Preds) {
369  dbgs() << " ";
370  dumpNodeName(*Dep.getSUnit());
371  dbgs() << ": ";
372  Dep.dump(TRI);
373  dbgs() << '\n';
374  }
375  }
376  if (SU.Succs.size() > 0) {
377  dbgs() << " Successors:\n";
378  for (const SDep &Dep : SU.Succs) {
379  dbgs() << " ";
380  dumpNodeName(*Dep.getSUnit());
381  dbgs() << ": ";
382  Dep.dump(TRI);
383  dbgs() << '\n';
384  }
385  }
386 }
387 #endif
388 
389 #ifndef NDEBUG
390 unsigned ScheduleDAG::VerifyScheduledDAG(bool isBottomUp) {
391  bool AnyNotSched = false;
392  unsigned DeadNodes = 0;
393  for (const SUnit &SUnit : SUnits) {
394  if (!SUnit.isScheduled) {
395  if (SUnit.NumPreds == 0 && SUnit.NumSuccs == 0) {
396  ++DeadNodes;
397  continue;
398  }
399  if (!AnyNotSched)
400  dbgs() << "*** Scheduling failed! ***\n";
401  dumpNode(SUnit);
402  dbgs() << "has not been scheduled!\n";
403  AnyNotSched = true;
404  }
405  if (SUnit.isScheduled &&
406  (isBottomUp ? SUnit.getHeight() : SUnit.getDepth()) >
407  unsigned(std::numeric_limits<int>::max())) {
408  if (!AnyNotSched)
409  dbgs() << "*** Scheduling failed! ***\n";
410  dumpNode(SUnit);
411  dbgs() << "has an unexpected "
412  << (isBottomUp ? "Height" : "Depth") << " value!\n";
413  AnyNotSched = true;
414  }
415  if (isBottomUp) {
416  if (SUnit.NumSuccsLeft != 0) {
417  if (!AnyNotSched)
418  dbgs() << "*** Scheduling failed! ***\n";
419  dumpNode(SUnit);
420  dbgs() << "has successors left!\n";
421  AnyNotSched = true;
422  }
423  } else {
424  if (SUnit.NumPredsLeft != 0) {
425  if (!AnyNotSched)
426  dbgs() << "*** Scheduling failed! ***\n";
427  dumpNode(SUnit);
428  dbgs() << "has predecessors left!\n";
429  AnyNotSched = true;
430  }
431  }
432  }
433  assert(!AnyNotSched);
434  return SUnits.size() - DeadNodes;
435 }
436 #endif
437 
439  // The idea of the algorithm is taken from
440  // "Online algorithms for managing the topological order of
441  // a directed acyclic graph" by David J. Pearce and Paul H.J. Kelly
442  // This is the MNR algorithm, which was first introduced by
443  // A. Marchetti-Spaccamela, U. Nanni and H. Rohnert in
444  // "Maintaining a topological order under edge insertions".
445  //
446  // Short description of the algorithm:
447  //
448  // Topological ordering, ord, of a DAG maps each node to a topological
449  // index so that for all edges X->Y it is the case that ord(X) < ord(Y).
450  //
451  // This means that if there is a path from the node X to the node Z,
452  // then ord(X) < ord(Z).
453  //
454  // This property can be used to check for reachability of nodes:
455  // if Z is reachable from X, then an insertion of the edge Z->X would
456  // create a cycle.
457  //
458  // The algorithm first computes a topological ordering for the DAG by
459  // initializing the Index2Node and Node2Index arrays and then tries to keep
460  // the ordering up-to-date after edge insertions by reordering the DAG.
461  //
462  // On insertion of the edge X->Y, the algorithm first marks by calling DFS
463  // the nodes reachable from Y, and then shifts them using Shift to lie
464  // immediately after X in Index2Node.
465 
466  // Cancel pending updates, mark as valid.
467  Dirty = false;
468  Updates.clear();
469 
470  unsigned DAGSize = SUnits.size();
471  std::vector<SUnit*> WorkList;
472  WorkList.reserve(DAGSize);
473 
474  Index2Node.resize(DAGSize);
475  Node2Index.resize(DAGSize);
476 
477  // Initialize the data structures.
478  if (ExitSU)
479  WorkList.push_back(ExitSU);
480  for (SUnit &SU : SUnits) {
481  int NodeNum = SU.NodeNum;
482  unsigned Degree = SU.Succs.size();
483  // Temporarily use the Node2Index array as scratch space for degree counts.
484  Node2Index[NodeNum] = Degree;
485 
486  // Is it a node without dependencies?
487  if (Degree == 0) {
488  assert(SU.Succs.empty() && "SUnit should have no successors");
489  // Collect leaf nodes.
490  WorkList.push_back(&SU);
491  }
492  }
493 
494  int Id = DAGSize;
495  while (!WorkList.empty()) {
496  SUnit *SU = WorkList.back();
497  WorkList.pop_back();
498  if (SU->NodeNum < DAGSize)
499  Allocate(SU->NodeNum, --Id);
500  for (const SDep &PredDep : SU->Preds) {
501  SUnit *SU = PredDep.getSUnit();
502  if (SU->NodeNum < DAGSize && !--Node2Index[SU->NodeNum])
503  // If all dependencies of the node are processed already,
504  // then the node can be computed now.
505  WorkList.push_back(SU);
506  }
507  }
508 
509  Visited.resize(DAGSize);
510  NumTopoInits++;
511 
512 #ifndef NDEBUG
513  // Check correctness of the ordering
514  for (SUnit &SU : SUnits) {
515  for (const SDep &PD : SU.Preds) {
516  assert(Node2Index[SU.NodeNum] > Node2Index[PD.getSUnit()->NodeNum] &&
517  "Wrong topological sorting");
518  }
519  }
520 #endif
521 }
522 
523 void ScheduleDAGTopologicalSort::FixOrder() {
524  // Recompute from scratch after new nodes have been added.
525  if (Dirty) {
526  InitDAGTopologicalSorting();
527  return;
528  }
529 
530  // Otherwise apply updates one-by-one.
531  for (auto &U : Updates)
532  AddPred(U.first, U.second);
533  Updates.clear();
534 }
535 
537  // Recomputing the order from scratch is likely more efficient than applying
538  // updates one-by-one for too many updates. The current cut-off is arbitrarily
539  // chosen.
540  Dirty = Dirty || Updates.size() > 10;
541 
542  if (Dirty)
543  return;
544 
545  Updates.emplace_back(Y, X);
546 }
547 
549  int UpperBound, LowerBound;
550  LowerBound = Node2Index[Y->NodeNum];
551  UpperBound = Node2Index[X->NodeNum];
552  bool HasLoop = false;
553  // Is Ord(X) < Ord(Y) ?
554  if (LowerBound < UpperBound) {
555  // Update the topological order.
556  Visited.reset();
557  DFS(Y, UpperBound, HasLoop);
558  assert(!HasLoop && "Inserted edge creates a loop!");
559  // Recompute topological indexes.
560  Shift(Visited, LowerBound, UpperBound);
561  }
562 
563  NumNewPredsAdded++;
564 }
565 
567  // InitDAGTopologicalSorting();
568 }
569 
570 void ScheduleDAGTopologicalSort::DFS(const SUnit *SU, int UpperBound,
571  bool &HasLoop) {
572  std::vector<const SUnit*> WorkList;
573  WorkList.reserve(SUnits.size());
574 
575  WorkList.push_back(SU);
576  do {
577  SU = WorkList.back();
578  WorkList.pop_back();
579  Visited.set(SU->NodeNum);
580  for (const SDep &SuccDep
581  : make_range(SU->Succs.rbegin(), SU->Succs.rend())) {
582  unsigned s = SuccDep.getSUnit()->NodeNum;
583  // Edges to non-SUnits are allowed but ignored (e.g. ExitSU).
584  if (s >= Node2Index.size())
585  continue;
586  if (Node2Index[s] == UpperBound) {
587  HasLoop = true;
588  return;
589  }
590  // Visit successors if not already and in affected region.
591  if (!Visited.test(s) && Node2Index[s] < UpperBound) {
592  WorkList.push_back(SuccDep.getSUnit());
593  }
594  }
595  } while (!WorkList.empty());
596 }
597 
598 std::vector<int> ScheduleDAGTopologicalSort::GetSubGraph(const SUnit &StartSU,
599  const SUnit &TargetSU,
600  bool &Success) {
601  std::vector<const SUnit*> WorkList;
602  int LowerBound = Node2Index[StartSU.NodeNum];
603  int UpperBound = Node2Index[TargetSU.NodeNum];
604  bool Found = false;
605  BitVector VisitedBack;
606  std::vector<int> Nodes;
607 
608  if (LowerBound > UpperBound) {
609  Success = false;
610  return Nodes;
611  }
612 
613  WorkList.reserve(SUnits.size());
614  Visited.reset();
615 
616  // Starting from StartSU, visit all successors up
617  // to UpperBound.
618  WorkList.push_back(&StartSU);
619  do {
620  const SUnit *SU = WorkList.back();
621  WorkList.pop_back();
622  for (int I = SU->Succs.size()-1; I >= 0; --I) {
623  const SUnit *Succ = SU->Succs[I].getSUnit();
624  unsigned s = Succ->NodeNum;
625  // Edges to non-SUnits are allowed but ignored (e.g. ExitSU).
626  if (Succ->isBoundaryNode())
627  continue;
628  if (Node2Index[s] == UpperBound) {
629  Found = true;
630  continue;
631  }
632  // Visit successors if not already and in affected region.
633  if (!Visited.test(s) && Node2Index[s] < UpperBound) {
634  Visited.set(s);
635  WorkList.push_back(Succ);
636  }
637  }
638  } while (!WorkList.empty());
639 
640  if (!Found) {
641  Success = false;
642  return Nodes;
643  }
644 
645  WorkList.clear();
646  VisitedBack.resize(SUnits.size());
647  Found = false;
648 
649  // Starting from TargetSU, visit all predecessors up
650  // to LowerBound. SUs that are visited by the two
651  // passes are added to Nodes.
652  WorkList.push_back(&TargetSU);
653  do {
654  const SUnit *SU = WorkList.back();
655  WorkList.pop_back();
656  for (int I = SU->Preds.size()-1; I >= 0; --I) {
657  const SUnit *Pred = SU->Preds[I].getSUnit();
658  unsigned s = Pred->NodeNum;
659  // Edges to non-SUnits are allowed but ignored (e.g. EntrySU).
660  if (Pred->isBoundaryNode())
661  continue;
662  if (Node2Index[s] == LowerBound) {
663  Found = true;
664  continue;
665  }
666  if (!VisitedBack.test(s) && Visited.test(s)) {
667  VisitedBack.set(s);
668  WorkList.push_back(Pred);
669  Nodes.push_back(s);
670  }
671  }
672  } while (!WorkList.empty());
673 
674  assert(Found && "Error in SUnit Graph!");
675  Success = true;
676  return Nodes;
677 }
678 
679 void ScheduleDAGTopologicalSort::Shift(BitVector& Visited, int LowerBound,
680  int UpperBound) {
681  std::vector<int> L;
682  int shift = 0;
683  int i;
684 
685  for (i = LowerBound; i <= UpperBound; ++i) {
686  // w is node at topological index i.
687  int w = Index2Node[i];
688  if (Visited.test(w)) {
689  // Unmark.
690  Visited.reset(w);
691  L.push_back(w);
692  shift = shift + 1;
693  } else {
694  Allocate(w, i - shift);
695  }
696  }
697 
698  for (unsigned LI : L) {
699  Allocate(LI, i - shift);
700  i = i + 1;
701  }
702 }
703 
705  FixOrder();
706  // Is SU reachable from TargetSU via successor edges?
707  if (IsReachable(SU, TargetSU))
708  return true;
709  for (const SDep &PredDep : TargetSU->Preds)
710  if (PredDep.isAssignedRegDep() &&
711  IsReachable(SU, PredDep.getSUnit()))
712  return true;
713  return false;
714 }
715 
717  const SUnit *TargetSU) {
718  FixOrder();
719  // If insertion of the edge SU->TargetSU would create a cycle
720  // then there is a path from TargetSU to SU.
721  int UpperBound, LowerBound;
722  LowerBound = Node2Index[TargetSU->NodeNum];
723  UpperBound = Node2Index[SU->NodeNum];
724  bool HasLoop = false;
725  // Is Ord(TargetSU) < Ord(SU) ?
726  if (LowerBound < UpperBound) {
727  Visited.reset();
728  // There may be a path from TargetSU to SU. Check for it.
729  DFS(TargetSU, UpperBound, HasLoop);
730  }
731  return HasLoop;
732 }
733 
734 void ScheduleDAGTopologicalSort::Allocate(int n, int index) {
735  Node2Index[n] = index;
736  Index2Node[index] = n;
737 }
738 
740 ScheduleDAGTopologicalSort(std::vector<SUnit> &sunits, SUnit *exitsu)
741  : SUnits(sunits), ExitSU(exitsu) {}
742 
void resize(unsigned N, bool t=false)
resize - Grow or shrink the bitvector.
Definition: BitVector.h:371
BitVector & set()
Definition: BitVector.h:397
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
GCNRegPressure max(const GCNRegPressure &P1, const GCNRegPressure &P2)
unsigned NumPreds
of SDep::Data preds.
Definition: ScheduleDAG.h:266
This class represents lattice values for constants.
Definition: AllocatorList.h:23
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds...
Definition: Compiler.h:473
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
This provides a very simple, boring adaptor for a begin and end iterator into a range type...
Describe properties that are true of each instruction in the target description file.
Definition: MCInstrDesc.h:164
virtual void dumpNode(const SUnit &SU) const =0
bool test(unsigned Idx) const
Definition: BitVector.h:501
void setSUnit(SUnit *SU)
Definition: ScheduleDAG.h:483
STATISTIC(NumFunctions, "Total number of functions")
unsigned const TargetRegisterInfo * TRI
void removePred(const SDep &D)
Removes the specified edge as a pred of the current node if it exists.
bool isAssignedRegDep() const
Tests if this is a Data dependence that is associated with a register.
Definition: ScheduleDAG.h:211
SmallVector< SDep, 4 > Preds
All sunit predecessors.
Definition: ScheduleDAG.h:256
bool isScheduled
True once scheduled.
Definition: ScheduleDAG.h:284
static GCMetadataPrinterRegistry::Add< OcamlGCMetadataPrinter > Y("ocaml", "ocaml 3.10-compatible collector")
SmallVectorImpl< SDep >::iterator pred_iterator
Definition: ScheduleDAG.h:259
unsigned NumSuccs
of SDep::Data sucss.
Definition: ScheduleDAG.h:267
unsigned getLatency() const
Returns the latency value for this edge, which roughly means the minimum number of cycles that must e...
Definition: ScheduleDAG.h:142
unsigned NumSuccsLeft
of succs not scheduled.
Definition: ScheduleDAG.h:269
const HexagonInstrInfo * TII
Printable printReg(unsigned Reg, const TargetRegisterInfo *TRI=nullptr, unsigned SubIdx=0, const MachineRegisterInfo *MRI=nullptr)
Prints virtual and physical registers with or without a TRI instance.
Regular data dependence (aka true-dependence).
Definition: ScheduleDAG.h:53
void InitDAGTopologicalSorting()
Creates the initial topological ordering from the DAG to be scheduled.
std::vector< int > GetSubGraph(const SUnit &StartSU, const SUnit &TargetSU, bool &Success)
Returns an array of SUs that are both in the successor subtree of StartSU and in the predecessor subt...
static cl::opt< bool > StressSchedOpt("stress-sched", cl::Hidden, cl::init(false), cl::desc("Stress test instruction scheduling"))
unsigned WeakSuccsLeft
of weak succs not scheduled.
Definition: ScheduleDAG.h:271
unsigned NumPredsLeft
of preds not scheduled.
Definition: ScheduleDAG.h:268
SUnit * getSUnit() const
Definition: ScheduleDAG.h:480
static int getLatency(LLVMDisasmContext *DC, const MCInst &Inst)
Gets latency information for Inst, based on DC information.
bool isBoundaryNode() const
Boundary nodes are placeholders for the boundary of the scheduling region.
Definition: ScheduleDAG.h:344
void dumpNodeAll(const SUnit &SU) const
void setDepthToAtLeast(unsigned NewDepth)
If NewDepth is greater than this node&#39;s depth value, sets it to be the new depth value.
Scheduling dependency.
Definition: ScheduleDAG.h:49
void setHeightToAtLeast(unsigned NewHeight)
If NewHeight is greater than this node&#39;s height value, set it to be the new height value...
#define P(N)
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:432
void setDepthDirty()
Sets a flag in this node to indicate that its stored Depth value will require recomputation the next ...
bool WillCreateCycle(SUnit *TargetSU, SUnit *SU)
Returns true if addPred(TargetSU, SU) creates a cycle.
unsigned const MachineRegisterInfo * MRI
void clearDAG()
Clears the DAG state (between regions).
Definition: ScheduleDAG.cpp:64
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
BitVector & reset()
Definition: BitVector.h:438
void RemovePred(SUnit *M, SUnit *N)
Updates the topological ordering to accommodate an an edge to be removed from the specified node N fr...
void dumpNodeName(const SUnit &SU) const
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
auto find(R &&Range, const T &Val) -> decltype(adl_begin(Range))
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1213
bool isMachineOpcode() const
Test if this node has a post-isel opcode, directly corresponding to a MachineInstr opcode...
void push_back(bool Val)
Definition: BitVector.h:506
void dump(const TargetRegisterInfo *TRI=nullptr) const
Definition: ScheduleDAG.cpp:75
const unsigned MaxDepth
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:837
void AddPredQueued(SUnit *Y, SUnit *X)
Queues an update to the topological ordering to accommodate an edge to be added from SUnit X to SUnit...
static unsigned getDepth(const SmallVectorImpl< const MachineBasicBlock *> &Stack, const MachineBasicBlock *MBB)
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:374
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
Represents one node in the SelectionDAG.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:940
bool IsReachable(const SUnit *SU, const SUnit *TargetSU)
Checks if SU is reachable from TargetSU.
void biasCriticalPath()
Orders this node&#39;s predecessor edges such that the critical path edge occurs first.
static unsigned getReg(const void *D, unsigned RC, unsigned RegNo)
ScheduleDAG(MachineFunction &mf)
Definition: ScheduleDAG.cpp:53
typename SuperClass::iterator iterator
Definition: SmallVector.h:319
static void DFS(BasicBlock *Root, SetVector< BasicBlock *> &Set)
void setLatency(unsigned Lat)
Sets the latency for this edge.
Definition: ScheduleDAG.h:147
#define Success
SUnit EntrySU
Special node for the region entry.
Definition: ScheduleDAG.h:563
unsigned VerifyScheduledDAG(bool isBottomUp)
Verifies that all SUnits were scheduled and that their state is consistent.
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
SUnit ExitSU
Special node for the region exit.
Definition: ScheduleDAG.h:564
const TargetRegisterInfo * TRI
Target processor register info.
Definition: ScheduleDAG.h:559
LLVM_NODISCARD bool empty() const
Definition: SmallVector.h:55
const MCInstrDesc & get(unsigned Opcode) const
Return the machine instruction descriptor that corresponds to the specified instruction opcode...
Definition: MCInstrInfo.h:44
#define I(x, y, z)
Definition: MD5.cpp:58
#define N
const TargetInstrInfo * TII
Target instruction information.
Definition: ScheduleDAG.h:558
Kind getKind() const
Returns an enum value representing the kind of the dependence.
Definition: ScheduleDAG.h:486
unsigned NodeNum
Entry # of node in the node vector.
Definition: ScheduleDAG.h:264
void setHeightDirty()
Sets a flag in this node to indicate that its stored Height value will require recomputation the next...
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
bool addPred(const SDep &D, bool Required=true)
Adds the specified edge as a pred of the current node if not already.
unsigned getMachineOpcode() const
This may only be called if isMachineOpcode returns true.
SmallVector< SDep, 4 > Succs
All sunit successors.
Definition: ScheduleDAG.h:257
bool isWeak() const
Tests if this a weak dependence.
Definition: ScheduleDAG.h:194
void AddPred(SUnit *Y, SUnit *X)
Updates the topological ordering to accommodate an edge to be added from SUnit X to SUnit Y...
virtual ~ScheduleDAG()
std::vector< SUnit > SUnits
The scheduling units.
Definition: ScheduleDAG.h:562
void dumpAttributes() const
ScheduleDAGTopologicalSort(std::vector< SUnit > &SUnits, SUnit *ExitSU)
Scheduling unit. This is a node in the scheduling DAG.
Definition: ScheduleDAG.h:242