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