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 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 46 static cl::opt<bool> StressSchedOpt( 47 "stress-sched", cl::Hidden, cl::init(false), 48 cl::desc("Stress test instruction scheduling")); 49 #endif 50 51 void SchedulingPriorityQueue::anchor() {} 52 53 ScheduleDAG::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 62 ScheduleDAG::~ScheduleDAG() = default; 63 64 void ScheduleDAG::clearDAG() { 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 75 LLVM_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 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) { 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 175 void 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 217 void 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 232 void 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 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 325 void 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) 341 LLVM_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 354 LLVM_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 363 LLVM_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 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 438 void 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 523 void 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 536 void 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 548 void 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 566 void ScheduleDAGTopologicalSort::RemovePred(SUnit *M, SUnit *N) { 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 704 bool 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 716 void ScheduleDAGTopologicalSort::AddSUnitWithoutPredecessors(const SUnit *SU) { 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 724 bool ScheduleDAGTopologicalSort::IsReachable(const SUnit *SU, 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 747 ScheduleDAGTopologicalSort:: 748 ScheduleDAGTopologicalSort(std::vector<SUnit> &sunits, SUnit *exitsu) 749 : SUnits(sunits), ExitSU(exitsu) {} 750 751 ScheduleHazardRecognizer::~ScheduleHazardRecognizer() = default; 752