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