758 lines · cpp
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-exception6//7//===----------------------------------------------------------------------===//8//9/// \file Implements the ScheduleDAG class, which is a base class used by10/// 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/CodeGen/MachineFunction.h"19#include "llvm/CodeGen/ScheduleHazardRecognizer.h"20#include "llvm/CodeGen/SelectionDAGNodes.h"21#include "llvm/CodeGen/TargetInstrInfo.h"22#include "llvm/CodeGen/TargetRegisterInfo.h"23#include "llvm/CodeGen/TargetSubtargetInfo.h"24#include "llvm/Config/llvm-config.h"25#include "llvm/Support/CommandLine.h"26#include "llvm/Support/Compiler.h"27#include "llvm/Support/Debug.h"28#include "llvm/Support/raw_ostream.h"29#include <algorithm>30#include <cassert>31#include <iterator>32#include <limits>33#include <utility>34#include <vector>35 36using namespace llvm;37 38#define DEBUG_TYPE "pre-RA-sched"39 40STATISTIC(NumNewPredsAdded, "Number of times a single predecessor was added");41STATISTIC(NumTopoInits,42 "Number of times the topological order has been recomputed");43 44#ifndef NDEBUG45static cl::opt<bool> StressSchedOpt(46 "stress-sched", cl::Hidden, cl::init(false),47 cl::desc("Stress test instruction scheduling"));48#endif49 50void SchedulingPriorityQueue::anchor() {}51 52ScheduleDAG::ScheduleDAG(MachineFunction &mf)53 : TM(mf.getTarget()), TII(mf.getSubtarget().getInstrInfo()),54 TRI(mf.getSubtarget().getRegisterInfo()), MF(mf),55 MRI(mf.getRegInfo()) {56#ifndef NDEBUG57 StressSched = StressSchedOpt;58#endif59}60 61ScheduleDAG::~ScheduleDAG() = default;62 63void ScheduleDAG::clearDAG() {64 SUnits.clear();65 EntrySU = SUnit();66 ExitSU = SUnit();67}68 69const MCInstrDesc *ScheduleDAG::getNodeDesc(const SDNode *Node) const {70 if (!Node || !Node->isMachineOpcode()) return nullptr;71 return &TII->get(Node->getMachineOpcode());72}73 74LLVM_DUMP_METHOD void SDep::dump(const TargetRegisterInfo *TRI) const {75 switch (getKind()) {76 case Data: dbgs() << "Data"; break;77 case Anti: dbgs() << "Anti"; break;78 case Output: dbgs() << "Out "; break;79 case Order: dbgs() << "Ord "; break;80 }81 82 switch (getKind()) {83 case Data:84 dbgs() << " Latency=" << getLatency();85 if (TRI && isAssignedRegDep())86 dbgs() << " Reg=" << printReg(getReg(), TRI);87 break;88 case Anti:89 case Output:90 dbgs() << " Latency=" << getLatency();91 break;92 case Order:93 dbgs() << " Latency=" << getLatency();94 switch(Contents.OrdKind) {95 case Barrier: dbgs() << " Barrier"; break;96 case MayAliasMem:97 case MustAliasMem: dbgs() << " Memory"; break;98 case Artificial: dbgs() << " Artificial"; break;99 case Weak: dbgs() << " Weak"; break;100 case Cluster: dbgs() << " Cluster"; break;101 }102 break;103 }104}105 106bool SUnit::addPred(const SDep &D, bool Required) {107 // If this node already has this dependence, don't add a redundant one.108 for (SDep &PredDep : Preds) {109 // Zero-latency weak edges may be added purely for heuristic ordering. Don't110 // add them if another kind of edge already exists.111 if (!Required && PredDep.getSUnit() == D.getSUnit())112 return false;113 if (PredDep.overlaps(D)) {114 // Extend the latency if needed. Equivalent to115 // removePred(PredDep) + addPred(D).116 if (PredDep.getLatency() < D.getLatency()) {117 SUnit *PredSU = PredDep.getSUnit();118 // Find the corresponding successor in N.119 SDep ForwardD = PredDep;120 ForwardD.setSUnit(this);121 for (SDep &SuccDep : PredSU->Succs) {122 if (SuccDep == ForwardD) {123 SuccDep.setLatency(D.getLatency());124 break;125 }126 }127 PredDep.setLatency(D.getLatency());128 // Changing latency, dirty the involved SUnits.129 this->setDepthDirty();130 D.getSUnit()->setHeightDirty();131 }132 return false;133 }134 }135 // Now add a corresponding succ to N.136 SDep P = D;137 P.setSUnit(this);138 SUnit *N = D.getSUnit();139 // Update the bookkeeping.140 if (D.getKind() == SDep::Data) {141 assert(NumPreds < std::numeric_limits<unsigned>::max() &&142 "NumPreds will overflow!");143 assert(N->NumSuccs < std::numeric_limits<unsigned>::max() &&144 "NumSuccs will overflow!");145 ++NumPreds;146 ++N->NumSuccs;147 }148 if (!N->isScheduled) {149 if (D.isWeak()) {150 ++WeakPredsLeft;151 }152 else {153 assert(NumPredsLeft < std::numeric_limits<unsigned>::max() &&154 "NumPredsLeft will overflow!");155 ++NumPredsLeft;156 }157 }158 if (!isScheduled) {159 if (D.isWeak()) {160 ++N->WeakSuccsLeft;161 }162 else {163 assert(N->NumSuccsLeft < std::numeric_limits<unsigned>::max() &&164 "NumSuccsLeft will overflow!");165 ++N->NumSuccsLeft;166 }167 }168 Preds.push_back(D);169 N->Succs.push_back(P);170 this->setDepthDirty();171 N->setHeightDirty();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 // Update the bookkeeping.187 if (P.getKind() == SDep::Data) {188 assert(NumPreds > 0 && "NumPreds will underflow!");189 assert(N->NumSuccs > 0 && "NumSuccs will underflow!");190 --NumPreds;191 --N->NumSuccs;192 }193 if (!N->isScheduled) {194 if (D.isWeak()) {195 assert(WeakPredsLeft > 0 && "WeakPredsLeft will underflow!");196 --WeakPredsLeft;197 } else {198 assert(NumPredsLeft > 0 && "NumPredsLeft will underflow!");199 --NumPredsLeft;200 }201 }202 if (!isScheduled) {203 if (D.isWeak()) {204 assert(N->WeakSuccsLeft > 0 && "WeakSuccsLeft will underflow!");205 --N->WeakSuccsLeft;206 } else {207 assert(N->NumSuccsLeft > 0 && "NumSuccsLeft will underflow!");208 --N->NumSuccsLeft;209 }210 }211 N->Succs.erase(Succ);212 Preds.erase(I);213 this->setDepthDirty();214 N->setHeightDirty();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 MaxDepth = I->getSUnit()->getDepth();335 BestI = I;336 }337 }338 if (BestI != Preds.begin())339 std::swap(*Preds.begin(), *BestI);340}341 342#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)343LLVM_DUMP_METHOD void SUnit::dumpAttributes() const {344 dbgs() << " # preds left : " << NumPredsLeft << "\n";345 dbgs() << " # succs left : " << NumSuccsLeft << "\n";346 if (WeakPredsLeft)347 dbgs() << " # weak preds left : " << WeakPredsLeft << "\n";348 if (WeakSuccsLeft)349 dbgs() << " # weak succs left : " << WeakSuccsLeft << "\n";350 dbgs() << " # rdefs left : " << NumRegDefsLeft << "\n";351 dbgs() << " Latency : " << Latency << "\n";352 dbgs() << " Depth : " << getDepth() << "\n";353 dbgs() << " Height : " << getHeight() << "\n";354}355 356LLVM_DUMP_METHOD void ScheduleDAG::dumpNodeName(const SUnit &SU) const {357 if (&SU == &EntrySU)358 dbgs() << "EntrySU";359 else if (&SU == &ExitSU)360 dbgs() << "ExitSU";361 else362 dbgs() << "SU(" << SU.NodeNum << ")";363}364 365LLVM_DUMP_METHOD void ScheduleDAG::dumpNodeAll(const SUnit &SU) const {366 dumpNode(SU);367 SU.dumpAttributes();368 if (SU.ParentClusterIdx != InvalidClusterId)369 dbgs() << " Parent Cluster Index: " << SU.ParentClusterIdx << '\n';370 371 if (SU.Preds.size() > 0) {372 dbgs() << " Predecessors:\n";373 for (const SDep &Dep : SU.Preds) {374 dbgs() << " ";375 dumpNodeName(*Dep.getSUnit());376 dbgs() << ": ";377 Dep.dump(TRI);378 dbgs() << '\n';379 }380 }381 if (SU.Succs.size() > 0) {382 dbgs() << " Successors:\n";383 for (const SDep &Dep : SU.Succs) {384 dbgs() << " ";385 dumpNodeName(*Dep.getSUnit());386 dbgs() << ": ";387 Dep.dump(TRI);388 dbgs() << '\n';389 }390 }391}392#endif393 394#ifndef NDEBUG395unsigned ScheduleDAG::VerifyScheduledDAG(bool isBottomUp) {396 bool AnyNotSched = false;397 unsigned DeadNodes = 0;398 for (const SUnit &SUnit : SUnits) {399 if (!SUnit.isScheduled) {400 if (SUnit.NumPreds == 0 && SUnit.NumSuccs == 0) {401 ++DeadNodes;402 continue;403 }404 if (!AnyNotSched)405 dbgs() << "*** Scheduling failed! ***\n";406 dumpNode(SUnit);407 dbgs() << "has not been scheduled!\n";408 AnyNotSched = true;409 }410 if (SUnit.isScheduled &&411 (isBottomUp ? SUnit.getHeight() : SUnit.getDepth()) >412 unsigned(std::numeric_limits<int>::max())) {413 if (!AnyNotSched)414 dbgs() << "*** Scheduling failed! ***\n";415 dumpNode(SUnit);416 dbgs() << "has an unexpected "417 << (isBottomUp ? "Height" : "Depth") << " value!\n";418 AnyNotSched = true;419 }420 if (isBottomUp) {421 if (SUnit.NumSuccsLeft != 0) {422 if (!AnyNotSched)423 dbgs() << "*** Scheduling failed! ***\n";424 dumpNode(SUnit);425 dbgs() << "has successors left!\n";426 AnyNotSched = true;427 }428 } else {429 if (SUnit.NumPredsLeft != 0) {430 if (!AnyNotSched)431 dbgs() << "*** Scheduling failed! ***\n";432 dumpNode(SUnit);433 dbgs() << "has predecessors left!\n";434 AnyNotSched = true;435 }436 }437 }438 assert(!AnyNotSched);439 return SUnits.size() - DeadNodes;440}441#endif442 443void ScheduleDAGTopologicalSort::InitDAGTopologicalSorting() {444 // The idea of the algorithm is taken from445 // "Online algorithms for managing the topological order of446 // a directed acyclic graph" by David J. Pearce and Paul H.J. Kelly447 // This is the MNR algorithm, which was first introduced by448 // A. Marchetti-Spaccamela, U. Nanni and H. Rohnert in449 // "Maintaining a topological order under edge insertions".450 //451 // Short description of the algorithm:452 //453 // Topological ordering, ord, of a DAG maps each node to a topological454 // index so that for all edges X->Y it is the case that ord(X) < ord(Y).455 //456 // This means that if there is a path from the node X to the node Z,457 // then ord(X) < ord(Z).458 //459 // This property can be used to check for reachability of nodes:460 // if Z is reachable from X, then an insertion of the edge Z->X would461 // create a cycle.462 //463 // The algorithm first computes a topological ordering for the DAG by464 // initializing the Index2Node and Node2Index arrays and then tries to keep465 // the ordering up-to-date after edge insertions by reordering the DAG.466 //467 // On insertion of the edge X->Y, the algorithm first marks by calling DFS468 // the nodes reachable from Y, and then shifts them using Shift to lie469 // immediately after X in Index2Node.470 471 // Cancel pending updates, mark as valid.472 Dirty = false;473 Updates.clear();474 475 unsigned DAGSize = SUnits.size();476 std::vector<SUnit*> WorkList;477 WorkList.reserve(DAGSize);478 479 Index2Node.resize(DAGSize);480 Node2Index.resize(DAGSize);481 482 // Initialize the data structures.483 if (ExitSU)484 WorkList.push_back(ExitSU);485 for (SUnit &SU : SUnits) {486 int NodeNum = SU.NodeNum;487 unsigned Degree = SU.Succs.size();488 // Temporarily use the Node2Index array as scratch space for degree counts.489 Node2Index[NodeNum] = Degree;490 491 // Is it a node without dependencies?492 if (Degree == 0) {493 assert(SU.Succs.empty() && "SUnit should have no successors");494 // Collect leaf nodes.495 WorkList.push_back(&SU);496 }497 }498 499 int Id = DAGSize;500 while (!WorkList.empty()) {501 SUnit *SU = WorkList.back();502 WorkList.pop_back();503 if (SU->NodeNum < DAGSize)504 Allocate(SU->NodeNum, --Id);505 for (const SDep &PredDep : SU->Preds) {506 SUnit *SU = PredDep.getSUnit();507 if (SU->NodeNum < DAGSize && !--Node2Index[SU->NodeNum])508 // If all dependencies of the node are processed already,509 // then the node can be computed now.510 WorkList.push_back(SU);511 }512 }513 514 Visited.resize(DAGSize);515 NumTopoInits++;516 517#ifndef NDEBUG518 // Check correctness of the ordering519 for (SUnit &SU : SUnits) {520 for (const SDep &PD : SU.Preds) {521 assert(Node2Index[SU.NodeNum] > Node2Index[PD.getSUnit()->NodeNum] &&522 "Wrong topological sorting");523 }524 }525#endif526}527 528void ScheduleDAGTopologicalSort::FixOrder() {529 // Recompute from scratch after new nodes have been added.530 if (Dirty) {531 InitDAGTopologicalSorting();532 return;533 }534 535 // Otherwise apply updates one-by-one.536 for (auto &U : Updates)537 AddPred(U.first, U.second);538 Updates.clear();539}540 541void ScheduleDAGTopologicalSort::AddPredQueued(SUnit *Y, SUnit *X) {542 // Recomputing the order from scratch is likely more efficient than applying543 // updates one-by-one for too many updates. The current cut-off is arbitrarily544 // chosen.545 Dirty = Dirty || Updates.size() > 10;546 547 if (Dirty)548 return;549 550 Updates.emplace_back(Y, X);551}552 553void ScheduleDAGTopologicalSort::AddPred(SUnit *Y, SUnit *X) {554 int UpperBound, LowerBound;555 LowerBound = Node2Index[Y->NodeNum];556 UpperBound = Node2Index[X->NodeNum];557 bool HasLoop = false;558 // Is Ord(X) < Ord(Y) ?559 if (LowerBound < UpperBound) {560 // Update the topological order.561 Visited.reset();562 DFS(Y, UpperBound, HasLoop);563 assert(!HasLoop && "Inserted edge creates a loop!");564 // Recompute topological indexes.565 Shift(Visited, LowerBound, UpperBound);566 }567 568 NumNewPredsAdded++;569}570 571void ScheduleDAGTopologicalSort::RemovePred(SUnit *M, SUnit *N) {572 // InitDAGTopologicalSorting();573}574 575void ScheduleDAGTopologicalSort::DFS(const SUnit *SU, int UpperBound,576 bool &HasLoop) {577 std::vector<const SUnit*> WorkList;578 WorkList.reserve(SUnits.size());579 580 WorkList.push_back(SU);581 do {582 SU = WorkList.back();583 WorkList.pop_back();584 Visited.set(SU->NodeNum);585 for (const SDep &SuccDep : llvm::reverse(SU->Succs)) {586 unsigned s = SuccDep.getSUnit()->NodeNum;587 // Edges to non-SUnits are allowed but ignored (e.g. ExitSU).588 if (s >= Node2Index.size())589 continue;590 if (Node2Index[s] == UpperBound) {591 HasLoop = true;592 return;593 }594 // Visit successors if not already and in affected region.595 if (!Visited.test(s) && Node2Index[s] < UpperBound) {596 WorkList.push_back(SuccDep.getSUnit());597 }598 }599 } while (!WorkList.empty());600}601 602std::vector<int> ScheduleDAGTopologicalSort::GetSubGraph(const SUnit &StartSU,603 const SUnit &TargetSU,604 bool &Success) {605 std::vector<const SUnit*> WorkList;606 int LowerBound = Node2Index[StartSU.NodeNum];607 int UpperBound = Node2Index[TargetSU.NodeNum];608 bool Found = false;609 BitVector VisitedBack;610 std::vector<int> Nodes;611 612 if (LowerBound > UpperBound) {613 Success = false;614 return Nodes;615 }616 617 WorkList.reserve(SUnits.size());618 Visited.reset();619 620 // Starting from StartSU, visit all successors up621 // to UpperBound.622 WorkList.push_back(&StartSU);623 do {624 const SUnit *SU = WorkList.back();625 WorkList.pop_back();626 for (const SDep &SD : llvm::reverse(SU->Succs)) {627 const SUnit *Succ = SD.getSUnit();628 unsigned s = Succ->NodeNum;629 // Edges to non-SUnits are allowed but ignored (e.g. ExitSU).630 if (Succ->isBoundaryNode())631 continue;632 if (Node2Index[s] == UpperBound) {633 Found = true;634 continue;635 }636 // Visit successors if not already and in affected region.637 if (!Visited.test(s) && Node2Index[s] < UpperBound) {638 Visited.set(s);639 WorkList.push_back(Succ);640 }641 }642 } while (!WorkList.empty());643 644 if (!Found) {645 Success = false;646 return Nodes;647 }648 649 WorkList.clear();650 VisitedBack.resize(SUnits.size());651 Found = false;652 653 // Starting from TargetSU, visit all predecessors up654 // to LowerBound. SUs that are visited by the two655 // passes are added to Nodes.656 WorkList.push_back(&TargetSU);657 do {658 const SUnit *SU = WorkList.back();659 WorkList.pop_back();660 for (const SDep &SD : llvm::reverse(SU->Preds)) {661 const SUnit *Pred = SD.getSUnit();662 unsigned s = Pred->NodeNum;663 // Edges to non-SUnits are allowed but ignored (e.g. EntrySU).664 if (Pred->isBoundaryNode())665 continue;666 if (Node2Index[s] == LowerBound) {667 Found = true;668 continue;669 }670 if (!VisitedBack.test(s) && Visited.test(s)) {671 VisitedBack.set(s);672 WorkList.push_back(Pred);673 Nodes.push_back(s);674 }675 }676 } while (!WorkList.empty());677 678 assert(Found && "Error in SUnit Graph!");679 Success = true;680 return Nodes;681}682 683void ScheduleDAGTopologicalSort::Shift(BitVector& Visited, int LowerBound,684 int UpperBound) {685 std::vector<int> L;686 int shift = 0;687 int i;688 689 for (i = LowerBound; i <= UpperBound; ++i) {690 // w is node at topological index i.691 int w = Index2Node[i];692 if (Visited.test(w)) {693 // Unmark.694 Visited.reset(w);695 L.push_back(w);696 shift = shift + 1;697 } else {698 Allocate(w, i - shift);699 }700 }701 702 for (unsigned LI : L) {703 Allocate(LI, i - shift);704 i = i + 1;705 }706}707 708bool ScheduleDAGTopologicalSort::WillCreateCycle(SUnit *TargetSU, SUnit *SU) {709 FixOrder();710 // Is SU reachable from TargetSU via successor edges?711 if (IsReachable(SU, TargetSU))712 return true;713 for (const SDep &PredDep : TargetSU->Preds)714 if (PredDep.isAssignedRegDep() &&715 IsReachable(SU, PredDep.getSUnit()))716 return true;717 return false;718}719 720void ScheduleDAGTopologicalSort::AddSUnitWithoutPredecessors(const SUnit *SU) {721 assert(SU->NodeNum == Index2Node.size() && "Node cannot be added at the end");722 assert(SU->NumPreds == 0 && "Can only add SU's with no predecessors");723 Node2Index.push_back(Index2Node.size());724 Index2Node.push_back(SU->NodeNum);725 Visited.resize(Node2Index.size());726}727 728bool ScheduleDAGTopologicalSort::IsReachable(const SUnit *SU,729 const SUnit *TargetSU) {730 assert(TargetSU != nullptr && "Invalid target SUnit");731 assert(SU != nullptr && "Invalid SUnit");732 FixOrder();733 // If insertion of the edge SU->TargetSU would create a cycle734 // then there is a path from TargetSU to SU.735 int UpperBound, LowerBound;736 LowerBound = Node2Index[TargetSU->NodeNum];737 UpperBound = Node2Index[SU->NodeNum];738 bool HasLoop = false;739 // Is Ord(TargetSU) < Ord(SU) ?740 if (LowerBound < UpperBound) {741 Visited.reset();742 // There may be a path from TargetSU to SU. Check for it.743 DFS(TargetSU, UpperBound, HasLoop);744 }745 return HasLoop;746}747 748void ScheduleDAGTopologicalSort::Allocate(int n, int index) {749 Node2Index[n] = index;750 Index2Node[index] = n;751}752 753ScheduleDAGTopologicalSort::754ScheduleDAGTopologicalSort(std::vector<SUnit> &sunits, SUnit *exitsu)755 : SUnits(sunits), ExitSU(exitsu) {}756 757ScheduleHazardRecognizer::~ScheduleHazardRecognizer() = default;758