LLVM  16.0.0git
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 {
152  "NumPredsLeft will overflow!");
153  ++NumPredsLeft;
154  }
155  }
156  if (!isScheduled) {
157  if (D.isWeak()) {
158  ++N->WeakSuccsLeft;
159  }
160  else {
161  assert(N->NumSuccsLeft < std::numeric_limits<unsigned>::max() &&
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) {
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 : llvm::reverse(SU->Succs)) {
581  unsigned s = SuccDep.getSUnit()->NodeNum;
582  // Edges to non-SUnits are allowed but ignored (e.g. ExitSU).
583  if (s >= Node2Index.size())
584  continue;
585  if (Node2Index[s] == UpperBound) {
586  HasLoop = true;
587  return;
588  }
589  // Visit successors if not already and in affected region.
590  if (!Visited.test(s) && Node2Index[s] < UpperBound) {
591  WorkList.push_back(SuccDep.getSUnit());
592  }
593  }
594  } while (!WorkList.empty());
595 }
596 
597 std::vector<int> ScheduleDAGTopologicalSort::GetSubGraph(const SUnit &StartSU,
598  const SUnit &TargetSU,
599  bool &Success) {
600  std::vector<const SUnit*> WorkList;
601  int LowerBound = Node2Index[StartSU.NodeNum];
602  int UpperBound = Node2Index[TargetSU.NodeNum];
603  bool Found = false;
604  BitVector VisitedBack;
605  std::vector<int> Nodes;
606 
607  if (LowerBound > UpperBound) {
608  Success = false;
609  return Nodes;
610  }
611 
612  WorkList.reserve(SUnits.size());
613  Visited.reset();
614 
615  // Starting from StartSU, visit all successors up
616  // to UpperBound.
617  WorkList.push_back(&StartSU);
618  do {
619  const SUnit *SU = WorkList.back();
620  WorkList.pop_back();
621  for (const SDep &SD : llvm::reverse(SU->Succs)) {
622  const SUnit *Succ = SD.getSUnit();
623  unsigned s = Succ->NodeNum;
624  // Edges to non-SUnits are allowed but ignored (e.g. ExitSU).
625  if (Succ->isBoundaryNode())
626  continue;
627  if (Node2Index[s] == UpperBound) {
628  Found = true;
629  continue;
630  }
631  // Visit successors if not already and in affected region.
632  if (!Visited.test(s) && Node2Index[s] < UpperBound) {
633  Visited.set(s);
634  WorkList.push_back(Succ);
635  }
636  }
637  } while (!WorkList.empty());
638 
639  if (!Found) {
640  Success = false;
641  return Nodes;
642  }
643 
644  WorkList.clear();
645  VisitedBack.resize(SUnits.size());
646  Found = false;
647 
648  // Starting from TargetSU, visit all predecessors up
649  // to LowerBound. SUs that are visited by the two
650  // passes are added to Nodes.
651  WorkList.push_back(&TargetSU);
652  do {
653  const SUnit *SU = WorkList.back();
654  WorkList.pop_back();
655  for (const SDep &SD : llvm::reverse(SU->Preds)) {
656  const SUnit *Pred = SD.getSUnit();
657  unsigned s = Pred->NodeNum;
658  // Edges to non-SUnits are allowed but ignored (e.g. EntrySU).
659  if (Pred->isBoundaryNode())
660  continue;
661  if (Node2Index[s] == LowerBound) {
662  Found = true;
663  continue;
664  }
665  if (!VisitedBack.test(s) && Visited.test(s)) {
666  VisitedBack.set(s);
667  WorkList.push_back(Pred);
668  Nodes.push_back(s);
669  }
670  }
671  } while (!WorkList.empty());
672 
673  assert(Found && "Error in SUnit Graph!");
674  Success = true;
675  return Nodes;
676 }
677 
678 void ScheduleDAGTopologicalSort::Shift(BitVector& Visited, int LowerBound,
679  int UpperBound) {
680  std::vector<int> L;
681  int shift = 0;
682  int i;
683 
684  for (i = LowerBound; i <= UpperBound; ++i) {
685  // w is node at topological index i.
686  int w = Index2Node[i];
687  if (Visited.test(w)) {
688  // Unmark.
689  Visited.reset(w);
690  L.push_back(w);
691  shift = shift + 1;
692  } else {
693  Allocate(w, i - shift);
694  }
695  }
696 
697  for (unsigned LI : L) {
698  Allocate(LI, i - shift);
699  i = i + 1;
700  }
701 }
702 
704  FixOrder();
705  // Is SU reachable from TargetSU via successor edges?
706  if (IsReachable(SU, TargetSU))
707  return true;
708  for (const SDep &PredDep : TargetSU->Preds)
709  if (PredDep.isAssignedRegDep() &&
710  IsReachable(SU, PredDep.getSUnit()))
711  return true;
712  return false;
713 }
714 
716  assert(SU->NodeNum == Index2Node.size() && "Node cannot be added at the end");
717  assert(SU->NumPreds == 0 && "Can only add SU's with no predecessors");
718  Node2Index.push_back(Index2Node.size());
719  Index2Node.push_back(SU->NodeNum);
720  Visited.resize(Node2Index.size());
721 }
722 
724  const SUnit *TargetSU) {
725  FixOrder();
726  // If insertion of the edge SU->TargetSU would create a cycle
727  // then there is a path from TargetSU to SU.
728  int UpperBound, LowerBound;
729  LowerBound = Node2Index[TargetSU->NodeNum];
730  UpperBound = Node2Index[SU->NodeNum];
731  bool HasLoop = false;
732  // Is Ord(TargetSU) < Ord(SU) ?
733  if (LowerBound < UpperBound) {
734  Visited.reset();
735  // There may be a path from TargetSU to SU. Check for it.
736  DFS(TargetSU, UpperBound, HasLoop);
737  }
738  return HasLoop;
739 }
740 
741 void ScheduleDAGTopologicalSort::Allocate(int n, int index) {
742  Node2Index[n] = index;
743  Index2Node[index] = n;
744 }
745 
747 ScheduleDAGTopologicalSort(std::vector<SUnit> &sunits, SUnit *exitsu)
748  : SUnits(sunits), ExitSU(exitsu) {}
749 
i
i
Definition: README.txt:29
llvm::ScheduleDAGTopologicalSort::RemovePred
void RemovePred(SUnit *M, SUnit *N)
Updates the topological ordering to accommodate an an edge to be removed from the specified node N fr...
Definition: ScheduleDAG.cpp:566
llvm::SUnit::dumpAttributes
void dumpAttributes() const
Definition: ScheduleDAG.cpp:341
ScheduleDAG.h
llvm::BitVector::push_back
void push_back(bool Val)
Definition: BitVector.h:459
LLVM_DUMP_METHOD
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
Definition: Compiler.h:492
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
llvm::ScheduleDAGTopologicalSort::WillCreateCycle
bool WillCreateCycle(SUnit *TargetSU, SUnit *SU)
Returns true if addPred(TargetSU, SU) creates a cycle.
Definition: ScheduleDAG.cpp:703
llvm::SUnit::NumPredsLeft
unsigned NumPredsLeft
Definition: ScheduleDAG.h:268
llvm::SDep::MustAliasMem
@ MustAliasMem
Nonvolatile load/Store instructions that must alias.
Definition: ScheduleDAG.h:71
llvm::SDep::Artificial
@ Artificial
Arbitrary strong DAG edge (no real dependence).
Definition: ScheduleDAG.h:72
P
This currently compiles esp xmm0 movsd esp eax eax esp ret We should use not the dag combiner This is because dagcombine2 needs to be able to see through the X86ISD::Wrapper which DAGCombine can t really do The code for turning x load into a single vector load is target independent and should be moved to the dag combiner The code for turning x load into a vector load can only handle a direct load from a global or a direct load from the stack It should be generalized to handle any load from P
Definition: README-SSE.txt:411
llvm::BitVector::set
BitVector & set()
Definition: BitVector.h:344
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1181
Statistic.h
llvm::ScheduleDAGTopologicalSort::IsReachable
bool IsReachable(const SUnit *SU, const SUnit *TargetSU)
Checks if SU is reachable from TargetSU.
Definition: ScheduleDAG.cpp:723
llvm::SUnit::NumSuccsLeft
unsigned NumSuccsLeft
Definition: ScheduleDAG.h:269
llvm::SDep::Anti
@ Anti
A register anti-dependence (aka WAR).
Definition: ScheduleDAG.h:54
llvm::SDNode
Represents one node in the SelectionDAG.
Definition: SelectionDAGNodes.h:462
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:140
llvm::TargetRegisterInfo
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
Definition: TargetRegisterInfo.h:237
llvm::BitVector::resize
void resize(unsigned N, bool t=false)
resize - Grow or shrink the bitvector.
Definition: BitVector.h:334
TargetInstrInfo.h
llvm::SUnit::Succs
SmallVector< SDep, 4 > Succs
All sunit successors.
Definition: ScheduleDAG.h:257
llvm::SUnit::getDepth
unsigned getDepth() const
Returns the depth of this node, which is the length of the maximum path up to any node which has no p...
Definition: ScheduleDAG.h:398
llvm::max
Expected< ExpressionValue > max(const ExpressionValue &Lhs, const ExpressionValue &Rhs)
Definition: FileCheck.cpp:337
STLExtras.h
llvm::SDep::setSUnit
void setSUnit(SUnit *SU)
Definition: ScheduleDAG.h:483
llvm::ScheduleDAG::~ScheduleDAG
virtual ~ScheduleDAG()
TRI
unsigned const TargetRegisterInfo * TRI
Definition: MachineSink.cpp:1628
llvm::ScheduleDAGTopologicalSort::AddPredQueued
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...
Definition: ScheduleDAG.cpp:536
llvm::ScheduleDAG::ScheduleDAG
ScheduleDAG(MachineFunction &mf)
Definition: ScheduleDAG.cpp:53
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
CommandLine.h
llvm::X86II::PD
@ PD
Definition: X86BaseInfo.h:787
llvm::SUnit::isBoundaryNode
bool isBoundaryNode() const
Boundary nodes are placeholders for the boundary of the scheduling region.
Definition: ScheduleDAG.h:344
llvm::SDep::Weak
@ Weak
Arbitrary weak DAG edge.
Definition: ScheduleDAG.h:73
ScheduleHazardRecognizer.h
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::ScheduleHazardRecognizer::~ScheduleHazardRecognizer
virtual ~ScheduleHazardRecognizer()
llvm::SUnit::setDepthDirty
void setDepthDirty()
Sets a flag in this node to indicate that its stored Depth value will require recomputation the next ...
Definition: ScheduleDAG.cpp:217
SelectionDAGNodes.h
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
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
llvm::cl::Required
@ Required
Definition: CommandLine.h:118
llvm::SUnit::setDepthToAtLeast
void setDepthToAtLeast(unsigned NewDepth)
If NewDepth is greater than this node's depth value, sets it to be the new depth value.
Definition: ScheduleDAG.cpp:247
llvm::SUnit::NodeNum
unsigned NodeNum
Entry # of node in the node vector.
Definition: ScheduleDAG.h:264
Y
static GCMetadataPrinterRegistry::Add< OcamlGCMetadataPrinter > Y("ocaml", "ocaml 3.10-compatible collector")
TII
const HexagonInstrInfo * TII
Definition: HexagonCopyToCombine.cpp:125
llvm::SUnit::NumPreds
unsigned NumPreds
Definition: ScheduleDAG.h:266
llvm::MCInstrDesc
Describe properties that are true of each instruction in the target description file.
Definition: MCInstrDesc.h:197
llvm::ScheduleDAGTopologicalSort::AddPred
void AddPred(SUnit *Y, SUnit *X)
Updates the topological ordering to accommodate an edge to be added from SUnit X to SUnit Y.
Definition: ScheduleDAG.cpp:548
llvm::STATISTIC
STATISTIC(NumFunctions, "Total number of functions")
llvm::SDep::Output
@ Output
A register output-dependence (aka WAW).
Definition: ScheduleDAG.h:55
llvm::SDep::Data
@ Data
Regular data dependence (aka true-dependence).
Definition: ScheduleDAG.h:53
llvm::BitVector
Definition: BitVector.h:75
X
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
llvm::ScheduleDAG::VerifyScheduledDAG
unsigned VerifyScheduledDAG(bool isBottomUp)
Verifies that all SUnits were scheduled and that their state is consistent.
Definition: ScheduleDAG.cpp:390
llvm::SDep::Order
@ Order
Any other ordering dependency.
Definition: ScheduleDAG.h:56
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::ScheduleDAGTopologicalSort::ScheduleDAGTopologicalSort
ScheduleDAGTopologicalSort(std::vector< SUnit > &SUnits, SUnit *ExitSU)
Definition: ScheduleDAG.cpp:747
llvm::cl::opt< bool >
llvm::SUnit::WeakSuccsLeft
unsigned WeakSuccsLeft
Definition: ScheduleDAG.h:271
index
splat index
Definition: README_ALTIVEC.txt:181
StressSchedOpt
static cl::opt< bool > StressSchedOpt("stress-sched", cl::Hidden, cl::init(false), cl::desc("Stress test instruction scheduling"))
D
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
llvm::SUnit::NumRegDefsLeft
unsigned short NumRegDefsLeft
Definition: ScheduleDAG.h:272
llvm::find
auto find(R &&Range, const T &Val)
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1610
s
multiplies can be turned into SHL s
Definition: README.txt:370
I
#define I(x, y, z)
Definition: MD5.cpp:58
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::cl::init
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:440
llvm::SDep::MayAliasMem
@ MayAliasMem
Nonvolatile load/Store instructions that may alias.
Definition: ScheduleDAG.h:70
llvm::SUnit::biasCriticalPath
void biasCriticalPath()
Orders this node's predecessor edges such that the critical path edge occurs first.
Definition: ScheduleDAG.cpp:325
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
std::swap
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:853
iterator_range.h
llvm::ScheduleDAG::dumpNodeAll
void dumpNodeAll(const SUnit &SU) const
Definition: ScheduleDAG.cpp:363
llvm::MachineFunction
Definition: MachineFunction.h:257
llvm::ScheduleDAG::StressSched
bool StressSched
Definition: ScheduleDAG.h:568
llvm::ScheduleDAG::dumpNode
virtual void dumpNode(const SUnit &SU) const =0
llvm::ScheduleDAG::TRI
const TargetRegisterInfo * TRI
Target processor register info.
Definition: ScheduleDAG.h:558
llvm::SDep::getSUnit
SUnit * getSUnit() const
Definition: ScheduleDAG.h:480
Compiler.h
llvm::SDep::Barrier
@ Barrier
An unknown scheduling barrier.
Definition: ScheduleDAG.h:69
TargetSubtargetInfo.h
llvm::ScheduleDAG::EntrySU
SUnit EntrySU
Special node for the region entry.
Definition: ScheduleDAG.h:562
llvm::SDep::isAssignedRegDep
bool isAssignedRegDep() const
Tests if this is a Data dependence that is associated with a register.
Definition: ScheduleDAG.h:211
MRI
unsigned const MachineRegisterInfo * MRI
Definition: AArch64AdvSIMDScalarPass.cpp:105
MaxDepth
static const unsigned MaxDepth
Definition: InstCombineMulDivRem.cpp:968
llvm::SDep
Scheduling dependency.
Definition: ScheduleDAG.h:49
llvm::SUnit::WeakPredsLeft
unsigned WeakPredsLeft
Definition: ScheduleDAG.h:270
llvm::ScheduleDAG::SUnits
std::vector< SUnit > SUnits
The scheduling units.
Definition: ScheduleDAG.h:561
llvm::BitVector::test
bool test(unsigned Idx) const
Definition: BitVector.h:454
llvm::SUnit::NumSuccs
unsigned NumSuccs
Definition: ScheduleDAG.h:267
llvm::SUnit::setHeightDirty
void setHeightDirty()
Sets a flag in this node to indicate that its stored Height value will require recomputation the next...
Definition: ScheduleDAG.cpp:232
llvm::SDep::setLatency
void setLatency(unsigned Lat)
Sets the latency for this edge.
Definition: ScheduleDAG.h:147
llvm::ScheduleDAG::TII
const TargetInstrInfo * TII
Target instruction information.
Definition: ScheduleDAG.h:557
Success
#define Success
Definition: AArch64Disassembler.cpp:280
llvm::ScheduleDAGTopologicalSort::InitDAGTopologicalSorting
void InitDAGTopologicalSorting()
Creates the initial topological ordering from the DAG to be scheduled.
Definition: ScheduleDAG.cpp:438
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::BitVector::reset
BitVector & reset()
Definition: BitVector.h:385
llvm::SDep::getKind
Kind getKind() const
Returns an enum value representing the kind of the dependence.
Definition: ScheduleDAG.h:486
SmallVector.h
llvm::SmallVectorImpl::iterator
typename SuperClass::iterator iterator
Definition: SmallVector.h:563
N
#define N
llvm::SmallVectorImpl::pop_back_val
T pop_back_val()
Definition: SmallVector.h:659
llvm::ScheduleDAG::dumpNodeName
void dumpNodeName(const SUnit &SU) const
Definition: ScheduleDAG.cpp:354
shift
http eax xorl edx cl sete al setne dl sall eax sall edx But that requires good bit subreg support this might be better It s an extra shift
Definition: README.txt:30
llvm::SDep::Cluster
@ Cluster
Weak DAG edge linking a chain of clustered instrs.
Definition: ScheduleDAG.h:74
llvm::ScheduleDAGTopologicalSort::GetSubGraph
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...
Definition: ScheduleDAG.cpp:597
llvm::reverse
auto reverse(ContainerTy &&C)
Definition: STLExtras.h:365
TM
const char LLVMTargetMachineRef TM
Definition: PassBuilderBindings.cpp:47
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
llvm::MCInstrInfo::get
const MCInstrDesc & get(unsigned Opcode) const
Return the machine instruction descriptor that corresponds to the specified instruction opcode.
Definition: MCInstrInfo.h:63
llvm::SUnit::pred_iterator
SmallVectorImpl< SDep >::iterator pred_iterator
Definition: ScheduleDAG.h:259
llvm::cl::desc
Definition: CommandLine.h:413
llvm::SDep::dump
void dump(const TargetRegisterInfo *TRI=nullptr) const
Definition: ScheduleDAG.cpp:75
raw_ostream.h
llvm::AMDGPU::VGPRIndexMode::Id
Id
Definition: SIDefines.h:241
n
The same transformation can work with an even modulo with the addition of a and shrink the compare RHS by the same amount Unless the target supports that transformation probably isn t worthwhile The transformation can also easily be made to work with non zero equality for n
Definition: README.txt:685
MachineFunction.h
llvm::printReg
Printable printReg(Register Reg, const TargetRegisterInfo *TRI=nullptr, unsigned SubIdx=0, const MachineRegisterInfo *MRI=nullptr)
Prints virtual and physical registers with or without a TRI instance.
Definition: TargetRegisterInfo.cpp:111
llvm::SmallVectorImpl::reserve
void reserve(size_type N)
Definition: SmallVector.h:649
llvm::ScheduleDAG::clearDAG
void clearDAG()
Clears the DAG state (between regions).
Definition: ScheduleDAG.cpp:64
TargetRegisterInfo.h
Debug.h
llvm::ScheduleDAG::ExitSU
SUnit ExitSU
Special node for the region exit.
Definition: ScheduleDAG.h:563
llvm::SDep::getLatency
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
llvm::ScheduleDAGTopologicalSort::AddSUnitWithoutPredecessors
void AddSUnitWithoutPredecessors(const SUnit *SU)
Add a SUnit without predecessors to the end of the topological order.
Definition: ScheduleDAG.cpp:715