LLVM  14.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
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  assert(SU->NodeNum == Index2Node.size() && "Node cannot be added at the end");
718  assert(SU->NumPreds == 0 && "Can only add SU's with no predecessors");
719  Node2Index.push_back(Index2Node.size());
720  Index2Node.push_back(SU->NodeNum);
721  Visited.resize(Node2Index.size());
722 }
723 
725  const SUnit *TargetSU) {
726  FixOrder();
727  // If insertion of the edge SU->TargetSU would create a cycle
728  // then there is a path from TargetSU to SU.
729  int UpperBound, LowerBound;
730  LowerBound = Node2Index[TargetSU->NodeNum];
731  UpperBound = Node2Index[SU->NodeNum];
732  bool HasLoop = false;
733  // Is Ord(TargetSU) < Ord(SU) ?
734  if (LowerBound < UpperBound) {
735  Visited.reset();
736  // There may be a path from TargetSU to SU. Check for it.
737  DFS(TargetSU, UpperBound, HasLoop);
738  }
739  return HasLoop;
740 }
741 
742 void ScheduleDAGTopologicalSort::Allocate(int n, int index) {
743  Node2Index[n] = index;
744  Index2Node[index] = n;
745 }
746 
748 ScheduleDAGTopologicalSort(std::vector<SUnit> &sunits, SUnit *exitsu)
749  : SUnits(sunits), ExitSU(exitsu) {}
750 
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:452
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:491
llvm
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
llvm::ScheduleDAGTopologicalSort::WillCreateCycle
bool WillCreateCycle(SUnit *TargetSU, SUnit *SU)
Returns true if addPred(TargetSU, SU) creates a cycle.
Definition: ScheduleDAG.cpp:704
llvm::SUnit::NumPredsLeft
unsigned NumPredsLeft
Definition: ScheduleDAG.h:268
llvm::make_range
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
Definition: iterator_range.h:53
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:343
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1168
Statistic.h
llvm::ScheduleDAGTopologicalSort::IsReachable
bool IsReachable(const SUnit *SU, const SUnit *TargetSU)
Checks if SU is reachable from TargetSU.
Definition: ScheduleDAG.cpp:724
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:455
llvm::cl::Hidden
@ Hidden
Definition: CommandLine.h:143
llvm::TargetRegisterInfo
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
Definition: TargetRegisterInfo.h:233
llvm::BitVector::resize
void resize(unsigned N, bool t=false)
resize - Grow or shrink the bitvector.
Definition: BitVector.h:333
TargetInstrInfo.h
llvm::X86II::PD
@ PD
Definition: X86BaseInfo.h:782
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
STLExtras.h
llvm::SmallVectorImpl::pop_back_val
LLVM_NODISCARD T pop_back_val()
Definition: SmallVector.h:635
llvm::SDep::setSUnit
void setSUnit(SUnit *SU)
Definition: ScheduleDAG.h:483
llvm::ScheduleDAG::~ScheduleDAG
virtual ~ScheduleDAG()
TRI
unsigned const TargetRegisterInfo * TRI
Definition: MachineSink.cpp:1567
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::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:121
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:129
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:195
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:74
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:748
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:1571
s
multiplies can be turned into SHL s
Definition: README.txt:370
I
#define I(x, y, z)
Definition: MD5.cpp:59
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:443
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:840
iterator_range.h
llvm::ScheduleDAG::dumpNodeAll
void dumpNodeAll(const SUnit &SU) const
Definition: ScheduleDAG.cpp:363
llvm::MachineFunction
Definition: MachineFunction.h:230
llvm::ScheduleDAG::StressSched
bool StressSched
Definition: ScheduleDAG.h:569
llvm::ScheduleDAG::dumpNode
virtual void dumpNode(const SUnit &SU) const =0
llvm::ScheduleDAG::TRI
const TargetRegisterInfo * TRI
Target processor register info.
Definition: ScheduleDAG.h:559
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:563
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:870
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:562
llvm::BitVector::test
bool test(unsigned Idx) const
Definition: BitVector.h:447
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:558
Success
#define Success
Definition: AArch64Disassembler.cpp:260
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:384
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:562
N
#define N
llvm::ScheduleDAG::dumpNodeName
void dumpNodeName(const SUnit &SU) const
Definition: ScheduleDAG.cpp:354
llvm::max
Align max(MaybeAlign Lhs, Align Rhs)
Definition: Alignment.h:340
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:598
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:62
llvm::SUnit::pred_iterator
SmallVectorImpl< SDep >::iterator pred_iterator
Definition: ScheduleDAG.h:259
llvm::cl::desc
Definition: CommandLine.h:414
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:228
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:110
llvm::SmallVectorImpl::reserve
void reserve(size_type N)
Definition: SmallVector.h:624
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:564
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:716