lib/CodeGen/ScheduleDAG.cpp

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