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
14#include "llvm/CodeGen/ScheduleDAG.h"
15#include "llvm/ADT/STLExtras.h"
16#include "llvm/ADT/SmallVector.h"
17#include "llvm/ADT/Statistic.h"
18#include "llvm/ADT/iterator_range.h"
19#include "llvm/CodeGen/MachineFunction.h"
20#include "llvm/CodeGen/ScheduleHazardRecognizer.h"
21#include "llvm/CodeGen/SelectionDAGNodes.h"
22#include "llvm/CodeGen/TargetInstrInfo.h"
23#include "llvm/CodeGen/TargetRegisterInfo.h"
24#include "llvm/CodeGen/TargetSubtargetInfo.h"
25#include "llvm/Config/llvm-config.h"
26#include "llvm/Support/CommandLine.h"
27#include "llvm/Support/Compiler.h"
28#include "llvm/Support/Debug.h"
29#include "llvm/Support/raw_ostream.h"
30#include <algorithm>
31#include <cassert>
32#include <iterator>
33#include <limits>
34#include <utility>
35#include <vector>
36
37using namespace llvm;
38
39#define DEBUG_TYPE "pre-RA-sched"
40
41STATISTIC(NumNewPredsAdded, "Number of times a  single predecessor was added");
42STATISTIC(NumTopoInits,
43          "Number of times the topological order has been recomputed");
44
45#ifndef NDEBUG
46static cl::opt<bool> StressSchedOpt(
47  "stress-sched", cl::Hidden, cl::init(false),
48  cl::desc("Stress test instruction scheduling"));
49#endif
50
51void SchedulingPriorityQueue::anchor() {}
52
53ScheduleDAG::ScheduleDAG(MachineFunction &mf)
54    : TM(mf.getTarget()), TII(mf.getSubtarget().getInstrInfo()),
55      TRI(mf.getSubtarget().getRegisterInfo()), MF(mf),
56      MRI(mf.getRegInfo()) {
57#ifndef NDEBUG
58  StressSched = StressSchedOpt;
59#endif
60}
61
62ScheduleDAG::~ScheduleDAG() = default;
63
64void ScheduleDAG::clearDAG() {
65  SUnits.clear();
66  EntrySU = SUnit();
67  ExitSU = SUnit();
68}
69
70const MCInstrDesc *ScheduleDAG::getNodeDesc(const SDNode *Node) const {
71  if (!Node || !Node->isMachineOpcode()) return nullptr;
72  return &TII->get(Node->getMachineOpcode());
73}
74
75LLVM_DUMP_METHOD void SDep::dump(const TargetRegisterInfo *TRI) const {
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
107bool 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) {
139    assert(NumPreds < std::numeric_limits<unsigned>::max() &&
140           "NumPreds will overflow!");
141    assert(N->NumSuccs < std::numeric_limits<unsigned>::max() &&
142           "NumSuccs will overflow!");
143    ++NumPreds;
144    ++N->NumSuccs;
145  }
146  if (!N->isScheduled) {
147    if (D.isWeak()) {
148      ++WeakPredsLeft;
149    }
150    else {
151      assert(NumPredsLeft < std::numeric_limits<unsigned>::max() &&
152             "NumPredsLeft will overflow!");
153      ++NumPredsLeft;
154    }
155  }
156  if (!isScheduled) {
157    if (D.isWeak()) {
158      ++N->WeakSuccsLeft;
159    }
160    else {
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
175void SUnit::removePred(const SDep &D) {
176  // Find the matching predecessor.
177  SmallVectorImpl<SDep>::iterator I = llvm::find(Preds, D);
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();
184  SmallVectorImpl<SDep>::iterator Succ = llvm::find(N->Succs, P);
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
217void SUnit::setDepthDirty() {
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
232void SUnit::setHeightDirty() {
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
247void SUnit::setDepthToAtLeast(unsigned NewDepth) {
248  if (NewDepth <= getDepth())
249    return;
250  setDepthDirty();
251  Depth = NewDepth;
252  isDepthCurrent = true;
253}
254
255void 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.
264void 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.
295void 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
325void SUnit::biasCriticalPath() {
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)
341LLVM_DUMP_METHOD void SUnit::dumpAttributes() const {
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
354LLVM_DUMP_METHOD void ScheduleDAG::dumpNodeName(const SUnit &SU) const {
355  if (&SU == &EntrySU)
356    dbgs() << "EntrySU";
357  else if (&SU == &ExitSU)
358    dbgs() << "ExitSU";
359  else
360    dbgs() << "SU(" << SU.NodeNum << ")";
361}
362
363LLVM_DUMP_METHOD void ScheduleDAG::dumpNodeAll(const SUnit &SU) const {
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
390unsigned 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
438void ScheduleDAGTopologicalSort::InitDAGTopologicalSorting() {
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
523void ScheduleDAGTopologicalSort::FixOrder() {
524  // Recompute from scratch after new nodes have been added.
525  if (Dirty) {
526    InitDAGTopologicalSorting();
527    return;
528  }
529
530  // Otherwise apply updates one-by-one.
531  for (auto &U : Updates)
532    AddPred(U.first, U.second);
533  Updates.clear();
534}
535
536void ScheduleDAGTopologicalSort::AddPredQueued(SUnit *Y, SUnit *X) {
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
548void ScheduleDAGTopologicalSort::AddPred(SUnit *Y, SUnit *X) {
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
566void ScheduleDAGTopologicalSort::RemovePred(SUnit *M, SUnit *N) {
567  // InitDAGTopologicalSorting();
568}
569
570void 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
598std::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
679void 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
704bool ScheduleDAGTopologicalSort::WillCreateCycle(SUnit *TargetSU, SUnit *SU) {
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
716bool ScheduleDAGTopologicalSort::IsReachable(const SUnit *SU,
717                                             const SUnit *TargetSU) {
718  FixOrder();
719  // If insertion of the edge SU->TargetSU would create a cycle
720  // then there is a path from TargetSU to SU.
721  int UpperBound, LowerBound;
722  LowerBound = Node2Index[TargetSU->NodeNum];
723  UpperBound = Node2Index[SU->NodeNum];
724  bool HasLoop = false;
725  // Is Ord(TargetSU) < Ord(SU) ?
726  if (LowerBound < UpperBound) {
727    Visited.reset();
728    // There may be a path from TargetSU to SU. Check for it.
729    DFS(TargetSU, UpperBound, HasLoop);
730  }
731  return HasLoop;
732}
733
734void ScheduleDAGTopologicalSort::Allocate(int n, int index) {
735  Node2Index[n] = index;
736  Index2Node[index] = n;
737}
738
739ScheduleDAGTopologicalSort::
740ScheduleDAGTopologicalSort(std::vector<SUnit> &sunits, SUnit *exitsu)
741  : SUnits(sunits), ExitSU(exitsu) {}
742
743ScheduleHazardRecognizer::~ScheduleHazardRecognizer() = default;
744