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