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/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 NDEBUG
45static cl::opt<bool> StressSchedOpt(
46 "stress-sched", cl::Hidden, cl::init(false),
47 cl::desc("Stress test instruction scheduling"));
48#endif
49
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 NDEBUG
57 StressSched = StressSchedOpt;
58#endif
59}
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(Opcode: 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(Reg: 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't
110 // add them if another kind of edge already exists.
111 if (!Required && PredDep.getSUnit() == D.getSUnit())
112 return false;
113 if (PredDep.overlaps(Other: D)) {
114 // Extend the latency if needed. Equivalent to
115 // 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(Elt: D);
169 N->Succs.push_back(Elt: 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(Range&: Preds, Val: 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(Range&: N->Succs, Val: 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(CI: Succ);
212 Preds.erase(CI: 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(Elt: 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(Elt: SuccSU);
228 }
229 } while (!WorkList.empty());
230}
231
232void SUnit::setHeightDirty() {
233 if (!isHeightCurrent) return;
234 SmallVector<SUnit*, 8> WorkList;
235 WorkList.push_back(Elt: 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(Elt: 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(Elt: 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(a: MaxPredDepth,
276 b: PredSU->Depth + PredDep.getLatency());
277 else {
278 Done = false;
279 WorkList.push_back(Elt: 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(Elt: 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(a: MaxSuccHeight,
307 b: SuccSU->Height + SuccDep.getLatency());
308 else {
309 Done = false;
310 WorkList.push_back(Elt: 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(x: 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(a&: *Preds.begin(), b&: *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 else
362 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#endif
393
394#ifndef NDEBUG
395unsigned 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#endif
442
443void ScheduleDAGTopologicalSort::InitDAGTopologicalSorting() {
444 // The idea of the algorithm is taken from
445 // "Online algorithms for managing the topological order of
446 // a directed acyclic graph" by David J. Pearce and Paul H.J. Kelly
447 // This is the MNR algorithm, which was first introduced by
448 // A. Marchetti-Spaccamela, U. Nanni and H. Rohnert in
449 // "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 topological
454 // 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 would
461 // create a cycle.
462 //
463 // The algorithm first computes a topological ordering for the DAG by
464 // initializing the Index2Node and Node2Index arrays and then tries to keep
465 // 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 DFS
468 // the nodes reachable from Y, and then shifts them using Shift to lie
469 // 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(n: DAGSize);
478
479 Index2Node.resize(new_size: DAGSize);
480 Node2Index.resize(new_size: DAGSize);
481
482 // Initialize the data structures.
483 if (ExitSU)
484 WorkList.push_back(x: 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(x: &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(n: SU->NodeNum, index: --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(x: SU);
511 }
512 }
513
514 Visited.resize(N: DAGSize);
515 NumTopoInits++;
516
517#ifndef NDEBUG
518 // Check correctness of the ordering
519 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#endif
526}
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(Y: U.first, X: 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 applying
543 // updates one-by-one for too many updates. The current cut-off is arbitrarily
544 // chosen.
545 Dirty = Dirty || Updates.size() > 10;
546
547 if (Dirty)
548 return;
549
550 Updates.emplace_back(Args&: Y, Args&: 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(SU: 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(n: SUnits.size());
579
580 WorkList.push_back(x: SU);
581 do {
582 SU = WorkList.back();
583 WorkList.pop_back();
584 Visited.set(SU->NodeNum);
585 for (const SDep &SuccDep : llvm::reverse(C: 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(Idx: s) && Node2Index[s] < UpperBound) {
596 WorkList.push_back(x: 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(n: SUnits.size());
618 Visited.reset();
619
620 // Starting from StartSU, visit all successors up
621 // to UpperBound.
622 WorkList.push_back(x: &StartSU);
623 do {
624 const SUnit *SU = WorkList.back();
625 WorkList.pop_back();
626 for (const SDep &SD : llvm::reverse(C: 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(Idx: s) && Node2Index[s] < UpperBound) {
638 Visited.set(s);
639 WorkList.push_back(x: 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(N: SUnits.size());
651 Found = false;
652
653 // Starting from TargetSU, visit all predecessors up
654 // to LowerBound. SUs that are visited by the two
655 // passes are added to Nodes.
656 WorkList.push_back(x: &TargetSU);
657 do {
658 const SUnit *SU = WorkList.back();
659 WorkList.pop_back();
660 for (const SDep &SD : llvm::reverse(C: 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(Idx: s) && Visited.test(Idx: s)) {
671 VisitedBack.set(s);
672 WorkList.push_back(x: Pred);
673 Nodes.push_back(x: 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(Idx: w)) {
693 // Unmark.
694 Visited.reset(Idx: w);
695 L.push_back(x: w);
696 shift = shift + 1;
697 } else {
698 Allocate(n: w, index: i - shift);
699 }
700 }
701
702 for (unsigned LI : L) {
703 Allocate(n: LI, index: 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, TargetSU: 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(x: Index2Node.size());
724 Index2Node.push_back(x: SU->NodeNum);
725 Visited.resize(N: 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 cycle
734 // 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(SU: 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