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 entry.
264void SUnit::ComputeDepth() {
265 // Iterative post-order DFS along Preds. Pushing one pred at a time and
266 // finalizing on pop. A node on the stack cannot reappear as a pred of any
267 // descendant.
268 SmallVector<SUnit *, 8> WorkList;
269 WorkList.push_back(Elt: this);
270 do {
271 SUnit *Cur = WorkList.back();
272 bool Descended = false;
273 for (const SDep &PredDep : Cur->Preds) {
274 SUnit *PredSU = PredDep.getSUnit();
275 if (!PredSU->isDepthCurrent) {
276 WorkList.push_back(Elt: PredSU);
277 Descended = true;
278 break;
279 }
280 }
281 if (Descended)
282 continue;
283 WorkList.pop_back();
284 unsigned MaxPredDepth = 0;
285 for (const SDep &PredDep : Cur->Preds)
286 MaxPredDepth = std::max(a: MaxPredDepth,
287 b: PredDep.getSUnit()->Depth + PredDep.getLatency());
288 Cur->Depth = MaxPredDepth;
289 Cur->isDepthCurrent = true;
290 } while (!WorkList.empty());
291}
292
293/// Calculates the maximal path from the node to the exit.
294void SUnit::ComputeHeight() {
295 // See ComputeDepth; this is the mirror image walking Succs.
296 SmallVector<SUnit *, 8> WorkList;
297 WorkList.push_back(Elt: this);
298 do {
299 SUnit *Cur = WorkList.back();
300 bool Descended = false;
301 for (const SDep &SuccDep : Cur->Succs) {
302 SUnit *SuccSU = SuccDep.getSUnit();
303 if (!SuccSU->isHeightCurrent) {
304 WorkList.push_back(Elt: SuccSU);
305 Descended = true;
306 break;
307 }
308 }
309 if (Descended)
310 continue;
311 WorkList.pop_back();
312 unsigned MaxSuccHeight = 0;
313 for (const SDep &SuccDep : Cur->Succs)
314 MaxSuccHeight = std::max(a: MaxSuccHeight, b: SuccDep.getSUnit()->Height +
315 SuccDep.getLatency());
316 Cur->Height = MaxSuccHeight;
317 Cur->isHeightCurrent = true;
318 } while (!WorkList.empty());
319}
320
321void SUnit::biasCriticalPath() {
322 if (NumPreds < 2)
323 return;
324
325 SUnit::pred_iterator BestI = Preds.begin();
326 unsigned MaxDepth = BestI->getSUnit()->getDepth();
327 for (SUnit::pred_iterator I = std::next(x: BestI), E = Preds.end(); I != E;
328 ++I) {
329 if (I->getKind() == SDep::Data && I->getSUnit()->getDepth() > MaxDepth) {
330 MaxDepth = I->getSUnit()->getDepth();
331 BestI = I;
332 }
333 }
334 if (BestI != Preds.begin())
335 std::swap(a&: *Preds.begin(), b&: *BestI);
336}
337
338#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
339raw_ostream &llvm::operator<<(raw_ostream &OS, const SUnit &SU) {
340 assert(!SU.isBoundaryNode() &&
341 "use ScheduleDAG::dumpNodeName for boundary nodes");
342 return OS << "SU(" << SU.NodeNum << ")";
343}
344#endif
345
346#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
347LLVM_DUMP_METHOD void SUnit::dumpAttributes() const {
348 dbgs() << " # preds left : " << NumPredsLeft << "\n";
349 dbgs() << " # succs left : " << NumSuccsLeft << "\n";
350 if (WeakPredsLeft)
351 dbgs() << " # weak preds left : " << WeakPredsLeft << "\n";
352 if (WeakSuccsLeft)
353 dbgs() << " # weak succs left : " << WeakSuccsLeft << "\n";
354 dbgs() << " # rdefs left : " << NumRegDefsLeft << "\n";
355 dbgs() << " Latency : " << Latency << "\n";
356 dbgs() << " Depth : " << getDepth() << "\n";
357 dbgs() << " Height : " << getHeight() << "\n";
358}
359
360LLVM_DUMP_METHOD void ScheduleDAG::dumpNodeName(const SUnit &SU) const {
361 if (&SU == &EntrySU)
362 dbgs() << "EntrySU";
363 else if (&SU == &ExitSU)
364 dbgs() << "ExitSU";
365 else
366 dbgs() << SU;
367}
368
369LLVM_DUMP_METHOD void ScheduleDAG::dumpNodeAll(const SUnit &SU) const {
370 dumpNode(SU);
371 SU.dumpAttributes();
372 if (SU.isClustered())
373 dbgs() << " Parent Cluster Index: " << SU.ParentClusterIdx << '\n';
374
375 if (SU.Preds.size() > 0) {
376 dbgs() << " Predecessors:\n";
377 for (const SDep &Dep : SU.Preds) {
378 dbgs() << " ";
379 dumpNodeName(*Dep.getSUnit());
380 dbgs() << ": ";
381 Dep.dump(TRI);
382 dbgs() << '\n';
383 }
384 }
385 if (SU.Succs.size() > 0) {
386 dbgs() << " Successors:\n";
387 for (const SDep &Dep : SU.Succs) {
388 dbgs() << " ";
389 dumpNodeName(*Dep.getSUnit());
390 dbgs() << ": ";
391 Dep.dump(TRI);
392 dbgs() << '\n';
393 }
394 }
395}
396#endif
397
398#ifndef NDEBUG
399unsigned ScheduleDAG::VerifyScheduledDAG(bool isBottomUp) {
400 bool AnyNotSched = false;
401 unsigned DeadNodes = 0;
402 for (const SUnit &SUnit : SUnits) {
403 if (!SUnit.isScheduled) {
404 if (SUnit.NumPreds == 0 && SUnit.NumSuccs == 0) {
405 ++DeadNodes;
406 continue;
407 }
408 if (!AnyNotSched)
409 dbgs() << "*** Scheduling failed! ***\n";
410 dumpNode(SUnit);
411 dbgs() << "has not been scheduled!\n";
412 AnyNotSched = true;
413 }
414 if (SUnit.isScheduled &&
415 (isBottomUp ? SUnit.getHeight() : SUnit.getDepth()) >
416 unsigned(std::numeric_limits<int>::max())) {
417 if (!AnyNotSched)
418 dbgs() << "*** Scheduling failed! ***\n";
419 dumpNode(SUnit);
420 dbgs() << "has an unexpected "
421 << (isBottomUp ? "Height" : "Depth") << " value!\n";
422 AnyNotSched = true;
423 }
424 if (isBottomUp) {
425 if (SUnit.NumSuccsLeft != 0) {
426 if (!AnyNotSched)
427 dbgs() << "*** Scheduling failed! ***\n";
428 dumpNode(SUnit);
429 dbgs() << "has successors left!\n";
430 AnyNotSched = true;
431 }
432 } else {
433 if (SUnit.NumPredsLeft != 0) {
434 if (!AnyNotSched)
435 dbgs() << "*** Scheduling failed! ***\n";
436 dumpNode(SUnit);
437 dbgs() << "has predecessors left!\n";
438 AnyNotSched = true;
439 }
440 }
441 }
442 assert(!AnyNotSched);
443 return SUnits.size() - DeadNodes;
444}
445#endif
446
447void ScheduleDAGTopologicalSort::InitDAGTopologicalSorting() {
448 // The idea of the algorithm is taken from
449 // "Online algorithms for managing the topological order of
450 // a directed acyclic graph" by David J. Pearce and Paul H.J. Kelly
451 // This is the MNR algorithm, which was first introduced by
452 // A. Marchetti-Spaccamela, U. Nanni and H. Rohnert in
453 // "Maintaining a topological order under edge insertions".
454 //
455 // Short description of the algorithm:
456 //
457 // Topological ordering, ord, of a DAG maps each node to a topological
458 // index so that for all edges X->Y it is the case that ord(X) < ord(Y).
459 //
460 // This means that if there is a path from the node X to the node Z,
461 // then ord(X) < ord(Z).
462 //
463 // This property can be used to check for reachability of nodes:
464 // if Z is reachable from X, then an insertion of the edge Z->X would
465 // create a cycle.
466 //
467 // The algorithm first computes a topological ordering for the DAG by
468 // initializing the Index2Node and Node2Index arrays and then tries to keep
469 // the ordering up-to-date after edge insertions by reordering the DAG.
470 //
471 // On insertion of the edge X->Y, the algorithm first marks by calling DFS
472 // the nodes reachable from Y, and then shifts them using Shift to lie
473 // immediately after X in Index2Node.
474
475 // Cancel pending updates, mark as valid.
476 Dirty = false;
477 Updates.clear();
478 Reachable.clear();
479
480 unsigned DAGSize = SUnits.size();
481
482 Index2Node.resize(new_size: DAGSize);
483 Node2Index.resize(new_size: DAGSize);
484
485 WorkList.reserve(n: DAGSize);
486 WorkList.clear();
487
488 // Initialize the data structures.
489 if (ExitSU)
490 WorkList.push_back(x: ExitSU);
491 for (SUnit &SU : SUnits) {
492 int NodeNum = SU.NodeNum;
493 unsigned Degree = SU.Succs.size();
494 // Temporarily use the Node2Index array as scratch space for degree counts.
495 Node2Index[NodeNum] = Degree;
496
497 // Is it a node without dependencies?
498 if (Degree == 0) {
499 assert(SU.Succs.empty() && "SUnit should have no successors");
500 // Collect leaf nodes.
501 WorkList.push_back(x: &SU);
502 }
503 }
504
505 int Id = DAGSize;
506 while (!WorkList.empty()) {
507 const SUnit *SU = WorkList.back();
508 WorkList.pop_back();
509 if (SU->NodeNum < DAGSize)
510 Allocate(n: SU->NodeNum, index: --Id);
511 for (const SDep &PredDep : SU->Preds) {
512 SUnit *SU = PredDep.getSUnit();
513 if (SU->NodeNum < DAGSize && !--Node2Index[SU->NodeNum])
514 // If all dependencies of the node are processed already,
515 // then the node can be computed now.
516 WorkList.push_back(x: SU);
517 }
518 }
519
520 Visited.resize(N: DAGSize);
521 NumTopoInits++;
522
523#ifndef NDEBUG
524 // Check correctness of the ordering
525 for (SUnit &SU : SUnits) {
526 for (const SDep &PD : SU.Preds) {
527 assert(Node2Index[SU.NodeNum] > Node2Index[PD.getSUnit()->NodeNum] &&
528 "Wrong topological sorting");
529 }
530 }
531#endif
532}
533
534void ScheduleDAGTopologicalSort::FixOrder() {
535 // Recompute from scratch after new nodes have been added.
536 if (Dirty) {
537 InitDAGTopologicalSorting();
538 return;
539 }
540
541 // Otherwise apply updates one-by-one.
542 for (auto &U : Updates)
543 AddPred(Y: U.first, X: U.second);
544 Updates.clear();
545}
546
547void ScheduleDAGTopologicalSort::AddPredQueued(SUnit *Y, SUnit *X) {
548 // Recomputing the order from scratch is likely more efficient than applying
549 // updates one-by-one for too many updates. The current cut-off is arbitrarily
550 // chosen.
551 Dirty = Dirty || Updates.size() > 10;
552
553 if (Dirty)
554 return;
555
556 Updates.emplace_back(Args&: Y, Args&: X);
557}
558
559void ScheduleDAGTopologicalSort::AddPred(SUnit *Y, SUnit *X) {
560 int UpperBound, LowerBound;
561 LowerBound = Node2Index[Y->NodeNum];
562 UpperBound = Node2Index[X->NodeNum];
563 bool HasLoop = false;
564 // Is Ord(X) < Ord(Y) ?
565 if (LowerBound < UpperBound) {
566 // Update the topological order.
567 Visited.reset();
568 DFS(SU: Y, UpperBound, HasLoop);
569 assert(!HasLoop && "Inserted edge creates a loop!");
570 // Recompute topological indexes.
571 Shift(Visited, LowerBound, UpperBound);
572 }
573
574 NumNewPredsAdded++;
575 Reachable.clear();
576}
577
578void ScheduleDAGTopologicalSort::RemovePred(SUnit *M, SUnit *N) {
579 // InitDAGTopologicalSorting();
580}
581
582void ScheduleDAGTopologicalSort::DFS(const SUnit *SU, int UpperBound,
583 bool &HasLoop) {
584 WorkList.clear();
585
586 WorkList.push_back(x: SU);
587 do {
588 SU = WorkList.back();
589 WorkList.pop_back();
590 Visited.set(SU->NodeNum);
591 for (const SDep &SuccDep : llvm::reverse(C: SU->Succs)) {
592 unsigned s = SuccDep.getSUnit()->NodeNum;
593 // Edges to non-SUnits are allowed but ignored (e.g. ExitSU).
594 if (s >= Node2Index.size())
595 continue;
596 if (Node2Index[s] == UpperBound) {
597 HasLoop = true;
598 return;
599 }
600 // Visit successors if not already and in affected region.
601 if (!Visited.test(Idx: s) && Node2Index[s] < UpperBound) {
602 WorkList.push_back(x: SuccDep.getSUnit());
603 }
604 }
605 } while (!WorkList.empty());
606}
607
608std::vector<int> ScheduleDAGTopologicalSort::GetSubGraph(const SUnit &StartSU,
609 const SUnit &TargetSU,
610 bool &Success) {
611 int LowerBound = Node2Index[StartSU.NodeNum];
612 int UpperBound = Node2Index[TargetSU.NodeNum];
613 bool Found = false;
614 BitVector VisitedBack;
615 std::vector<int> Nodes;
616
617 if (LowerBound > UpperBound) {
618 Success = false;
619 return Nodes;
620 }
621
622 WorkList.clear();
623 Visited.reset();
624
625 // Starting from StartSU, visit all successors up
626 // to UpperBound.
627 WorkList.push_back(x: &StartSU);
628 do {
629 const SUnit *SU = WorkList.back();
630 WorkList.pop_back();
631 for (const SDep &SD : llvm::reverse(C: SU->Succs)) {
632 const SUnit *Succ = SD.getSUnit();
633 unsigned s = Succ->NodeNum;
634 // Edges to non-SUnits are allowed but ignored (e.g. ExitSU).
635 if (Succ->isBoundaryNode())
636 continue;
637 if (Node2Index[s] == UpperBound) {
638 Found = true;
639 continue;
640 }
641 // Visit successors if not already and in affected region.
642 if (!Visited.test(Idx: s) && Node2Index[s] < UpperBound) {
643 Visited.set(s);
644 WorkList.push_back(x: Succ);
645 }
646 }
647 } while (!WorkList.empty());
648
649 if (!Found) {
650 Success = false;
651 return Nodes;
652 }
653
654 WorkList.clear();
655 VisitedBack.resize(N: SUnits.size());
656 Found = false;
657
658 // Starting from TargetSU, visit all predecessors up
659 // to LowerBound. SUs that are visited by the two
660 // passes are added to Nodes.
661 WorkList.push_back(x: &TargetSU);
662 do {
663 const SUnit *SU = WorkList.back();
664 WorkList.pop_back();
665 for (const SDep &SD : llvm::reverse(C: SU->Preds)) {
666 const SUnit *Pred = SD.getSUnit();
667 unsigned s = Pred->NodeNum;
668 // Edges to non-SUnits are allowed but ignored (e.g. EntrySU).
669 if (Pred->isBoundaryNode())
670 continue;
671 if (Node2Index[s] == LowerBound) {
672 Found = true;
673 continue;
674 }
675 if (!VisitedBack.test(Idx: s) && Visited.test(Idx: s)) {
676 VisitedBack.set(s);
677 WorkList.push_back(x: Pred);
678 Nodes.push_back(x: s);
679 }
680 }
681 } while (!WorkList.empty());
682
683 assert(Found && "Error in SUnit Graph!");
684 Success = true;
685 return Nodes;
686}
687
688void ScheduleDAGTopologicalSort::Shift(BitVector& Visited, int LowerBound,
689 int UpperBound) {
690 std::vector<int> L;
691 int shift = 0;
692 int i;
693
694 for (i = LowerBound; i <= UpperBound; ++i) {
695 // w is node at topological index i.
696 int w = Index2Node[i];
697 if (Visited.test(Idx: w)) {
698 // Unmark.
699 Visited.reset(Idx: w);
700 L.push_back(x: w);
701 shift = shift + 1;
702 } else {
703 Allocate(n: w, index: i - shift);
704 }
705 }
706
707 for (unsigned LI : L) {
708 Allocate(n: LI, index: i - shift);
709 i = i + 1;
710 }
711}
712
713bool ScheduleDAGTopologicalSort::WillCreateCycle(SUnit *TargetSU, SUnit *SU) {
714 FixOrder();
715 // Is SU reachable from TargetSU via successor edges?
716 if (IsReachable(SU, TargetSU))
717 return true;
718 for (const SDep &PredDep : TargetSU->Preds)
719 if (PredDep.isAssignedRegDep() &&
720 IsReachable(SU, TargetSU: PredDep.getSUnit()))
721 return true;
722 return false;
723}
724
725void ScheduleDAGTopologicalSort::AddSUnitWithoutPredecessors(const SUnit *SU) {
726 assert(SU->NodeNum == Index2Node.size() && "Node cannot be added at the end");
727 assert(SU->NumPreds == 0 && "Can only add SU's with no predecessors");
728 Node2Index.push_back(x: Index2Node.size());
729 Index2Node.push_back(x: SU->NodeNum);
730 Visited.resize(N: Node2Index.size());
731}
732
733bool ScheduleDAGTopologicalSort::IsReachable(const SUnit *SU,
734 const SUnit *TargetSU) {
735 assert(TargetSU != nullptr && "Invalid target SUnit");
736 assert(SU != nullptr && "Invalid SUnit");
737 FixOrder();
738 // If insertion of the edge SU->TargetSU would create a cycle
739 // then there is a path from TargetSU to SU.
740 int UpperBound, LowerBound;
741 LowerBound = Node2Index[TargetSU->NodeNum];
742 UpperBound = Node2Index[SU->NodeNum];
743 bool HasLoop = false;
744 // Is Ord(TargetSU) < Ord(SU) ?
745 if (LowerBound < UpperBound) {
746 if (auto It = Reachable.find(Val: {TargetSU->NodeNum, SU->NodeNum});
747 It != Reachable.end()) {
748 return It->second;
749 }
750 Visited.reset();
751 // There may be a path from TargetSU to SU. Check for it.
752 DFS(SU: TargetSU, UpperBound, HasLoop);
753 // If there's no loop, cache the result. We only cache negative results,
754 // as positive results are not safe to cache; users call SU.removePred()
755 // without notifying us.
756 if (!HasLoop)
757 Reachable[{TargetSU->NodeNum, SU->NodeNum}] = false;
758 }
759 return HasLoop;
760}
761
762void ScheduleDAGTopologicalSort::Allocate(int n, int index) {
763 Node2Index[n] = index;
764 Index2Node[index] = n;
765}
766
767ScheduleDAGTopologicalSort::
768ScheduleDAGTopologicalSort(std::vector<SUnit> &sunits, SUnit *exitsu)
769 : SUnits(sunits), ExitSU(exitsu) {}
770
771ScheduleHazardRecognizer::~ScheduleHazardRecognizer() = default;
772