Line data Source code
1 : //===- ScheduleDAG.cpp - Implement the ScheduleDAG class ------------------===//
2 : //
3 : // The LLVM Compiler Infrastructure
4 : //
5 : // This file is distributed under the University of Illinois Open Source
6 : // License. See LICENSE.TXT for details.
7 : //
8 : //===----------------------------------------------------------------------===//
9 : //
10 : /// \file Implements the ScheduleDAG class, which is a base class used by
11 : /// scheduling implementation classes.
12 : //
13 : //===----------------------------------------------------------------------===//
14 :
15 : #include "llvm/CodeGen/ScheduleDAG.h"
16 : #include "llvm/ADT/STLExtras.h"
17 : #include "llvm/ADT/SmallVector.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 : #ifndef NDEBUG
42 : static cl::opt<bool> StressSchedOpt(
43 : "stress-sched", cl::Hidden, cl::init(false),
44 : cl::desc("Stress test instruction scheduling"));
45 : #endif
46 :
47 0 : void SchedulingPriorityQueue::anchor() {}
48 :
49 1503384 : ScheduleDAG::ScheduleDAG(MachineFunction &mf)
50 3006768 : : TM(mf.getTarget()), TII(mf.getSubtarget().getInstrInfo()),
51 1503384 : TRI(mf.getSubtarget().getRegisterInfo()), MF(mf),
52 1503384 : MRI(mf.getRegInfo()) {
53 : #ifndef NDEBUG
54 : StressSched = StressSchedOpt;
55 : #endif
56 1503384 : }
57 :
58 : ScheduleDAG::~ScheduleDAG() = default;
59 :
60 2173475 : void ScheduleDAG::clearDAG() {
61 : SUnits.clear();
62 2173475 : EntrySU = SUnit();
63 2173475 : ExitSU = SUnit();
64 2173474 : }
65 :
66 341509 : const MCInstrDesc *ScheduleDAG::getNodeDesc(const SDNode *Node) const {
67 341509 : if (!Node || !Node->isMachineOpcode()) return nullptr;
68 665697 : return &TII->get(Node->getMachineOpcode());
69 : }
70 :
71 0 : LLVM_DUMP_METHOD void SDep::dump(const TargetRegisterInfo *TRI) const {
72 0 : switch (getKind()) {
73 0 : case Data: dbgs() << "Data"; break;
74 0 : case Anti: dbgs() << "Anti"; break;
75 0 : case Output: dbgs() << "Out "; break;
76 0 : case Order: dbgs() << "Ord "; break;
77 : }
78 :
79 0 : switch (getKind()) {
80 0 : case Data:
81 0 : dbgs() << " Latency=" << getLatency();
82 0 : if (TRI && isAssignedRegDep())
83 0 : dbgs() << " Reg=" << printReg(getReg(), TRI);
84 : break;
85 0 : case Anti:
86 : case Output:
87 0 : dbgs() << " Latency=" << getLatency();
88 : break;
89 0 : case Order:
90 0 : dbgs() << " Latency=" << getLatency();
91 0 : switch(Contents.OrdKind) {
92 0 : case Barrier: dbgs() << " Barrier"; break;
93 0 : case MayAliasMem:
94 0 : case MustAliasMem: dbgs() << " Memory"; break;
95 0 : case Artificial: dbgs() << " Artificial"; break;
96 0 : case Weak: dbgs() << " Weak"; break;
97 0 : case Cluster: dbgs() << " Cluster"; break;
98 : }
99 : break;
100 : }
101 0 : }
102 :
103 29998519 : bool SUnit::addPred(const SDep &D, bool Required) {
104 : // If this node already has this dependence, don't add a redundant one.
105 103319006 : for (SDep &PredDep : Preds) {
106 : // Zero-latency weak edges may be added purely for heuristic ordering. Don't
107 : // add them if another kind of edge already exists.
108 76259367 : if (!Required && PredDep.getSUnit() == D.getSUnit())
109 : return false;
110 3089744 : if (PredDep.overlaps(D)) {
111 : // Extend the latency if needed. Equivalent to
112 : // removePred(PredDep) + addPred(D).
113 2904102 : if (PredDep.getLatency() < D.getLatency()) {
114 : SUnit *PredSU = PredDep.getSUnit();
115 : // Find the corresponding successor in N.
116 1081 : SDep ForwardD = PredDep;
117 : ForwardD.setSUnit(this);
118 1928 : for (SDep &SuccDep : PredSU->Succs) {
119 1928 : if (SuccDep == ForwardD) {
120 : SuccDep.setLatency(D.getLatency());
121 : break;
122 : }
123 : }
124 1081 : PredDep.setLatency(D.getLatency());
125 : }
126 2904102 : return false;
127 : }
128 : }
129 : // Now add a corresponding succ to N.
130 27059639 : SDep P = D;
131 : P.setSUnit(this);
132 : SUnit *N = D.getSUnit();
133 : // Update the bookkeeping.
134 27059639 : if (D.getKind() == SDep::Data) {
135 : assert(NumPreds < std::numeric_limits<unsigned>::max() &&
136 : "NumPreds will overflow!");
137 : assert(N->NumSuccs < std::numeric_limits<unsigned>::max() &&
138 : "NumSuccs will overflow!");
139 11777559 : ++NumPreds;
140 11777559 : ++N->NumSuccs;
141 : }
142 27059639 : if (!N->isScheduled) {
143 : if (D.isWeak()) {
144 50376 : ++WeakPredsLeft;
145 : }
146 : else {
147 : assert(NumPredsLeft < std::numeric_limits<unsigned>::max() &&
148 : "NumPredsLeft will overflow!");
149 27009264 : ++NumPredsLeft;
150 : }
151 : }
152 27059639 : if (!isScheduled) {
153 : if (D.isWeak()) {
154 50376 : ++N->WeakSuccsLeft;
155 : }
156 : else {
157 : assert(N->NumSuccsLeft < std::numeric_limits<unsigned>::max() &&
158 : "NumSuccsLeft will overflow!");
159 27008455 : ++N->NumSuccsLeft;
160 : }
161 : }
162 27059639 : Preds.push_back(D);
163 27059640 : N->Succs.push_back(P);
164 27059640 : if (P.getLatency() != 0) {
165 22232924 : this->setDepthDirty();
166 22232924 : N->setHeightDirty();
167 : }
168 : return true;
169 : }
170 :
171 2260 : void SUnit::removePred(const SDep &D) {
172 : // Find the matching predecessor.
173 : SmallVectorImpl<SDep>::iterator I = llvm::find(Preds, D);
174 2260 : if (I == Preds.end())
175 115 : return;
176 : // Find the corresponding successor in N.
177 2145 : SDep P = D;
178 : P.setSUnit(this);
179 : SUnit *N = D.getSUnit();
180 : SmallVectorImpl<SDep>::iterator Succ = llvm::find(N->Succs, P);
181 : assert(Succ != N->Succs.end() && "Mismatching preds / succs lists!");
182 : N->Succs.erase(Succ);
183 : Preds.erase(I);
184 : // Update the bookkeeping.
185 2145 : if (P.getKind() == SDep::Data) {
186 : assert(NumPreds > 0 && "NumPreds will underflow!");
187 : assert(N->NumSuccs > 0 && "NumSuccs will underflow!");
188 921 : --NumPreds;
189 921 : --N->NumSuccs;
190 : }
191 2145 : if (!N->isScheduled) {
192 : if (D.isWeak())
193 0 : --WeakPredsLeft;
194 : else {
195 : assert(NumPredsLeft > 0 && "NumPredsLeft will underflow!");
196 2145 : --NumPredsLeft;
197 : }
198 : }
199 2145 : if (!isScheduled) {
200 : if (D.isWeak())
201 0 : --N->WeakSuccsLeft;
202 : else {
203 : assert(N->NumSuccsLeft > 0 && "NumSuccsLeft will underflow!");
204 1451 : --N->NumSuccsLeft;
205 : }
206 : }
207 2145 : if (P.getLatency() != 0) {
208 2005 : this->setDepthDirty();
209 2005 : N->setHeightDirty();
210 : }
211 : }
212 :
213 27156489 : void SUnit::setDepthDirty() {
214 27156489 : if (!isDepthCurrent) return;
215 : SmallVector<SUnit*, 8> WorkList;
216 140413 : WorkList.push_back(this);
217 : do {
218 : SUnit *SU = WorkList.pop_back_val();
219 142146 : SU->isDepthCurrent = false;
220 832974 : for (SDep &SuccDep : SU->Succs) {
221 690828 : SUnit *SuccSU = SuccDep.getSUnit();
222 690828 : if (SuccSU->isDepthCurrent)
223 1733 : WorkList.push_back(SuccSU);
224 : }
225 142146 : } while (!WorkList.empty());
226 : }
227 :
228 44826855 : void SUnit::setHeightDirty() {
229 44826855 : if (!isHeightCurrent) return;
230 : SmallVector<SUnit*, 8> WorkList;
231 5181769 : WorkList.push_back(this);
232 : do {
233 : SUnit *SU = WorkList.pop_back_val();
234 5310208 : SU->isHeightCurrent = false;
235 12413549 : for (SDep &PredDep : SU->Preds) {
236 7103341 : SUnit *PredSU = PredDep.getSUnit();
237 7103341 : if (PredSU->isHeightCurrent)
238 128439 : WorkList.push_back(PredSU);
239 : }
240 5310208 : } while (!WorkList.empty());
241 : }
242 :
243 900223 : void SUnit::setDepthToAtLeast(unsigned NewDepth) {
244 900223 : if (NewDepth <= getDepth())
245 : return;
246 140192 : setDepthDirty();
247 140192 : Depth = NewDepth;
248 140192 : isDepthCurrent = true;
249 : }
250 :
251 16552879 : void SUnit::setHeightToAtLeast(unsigned NewHeight) {
252 16552879 : if (NewHeight <= getHeight())
253 : return;
254 5172925 : setHeightDirty();
255 5172925 : Height = NewHeight;
256 5172925 : isHeightCurrent = true;
257 : }
258 :
259 : /// Calculates the maximal path from the node to the exit.
260 4156604 : void SUnit::ComputeDepth() {
261 : SmallVector<SUnit*, 8> WorkList;
262 4156604 : WorkList.push_back(this);
263 : do {
264 12330146 : SUnit *Cur = WorkList.back();
265 :
266 : bool Done = true;
267 12330146 : unsigned MaxPredDepth = 0;
268 28509233 : for (const SDep &PredDep : Cur->Preds) {
269 16179087 : SUnit *PredSU = PredDep.getSUnit();
270 16179087 : if (PredSU->isDepthCurrent)
271 11364467 : MaxPredDepth = std::max(MaxPredDepth,
272 17256915 : PredSU->Depth + PredDep.getLatency());
273 : else {
274 : Done = false;
275 4814620 : WorkList.push_back(PredSU);
276 : }
277 : }
278 :
279 12330146 : if (Done) {
280 : WorkList.pop_back();
281 8971224 : if (MaxPredDepth != Cur->Depth) {
282 4780277 : Cur->setDepthDirty();
283 4780277 : Cur->Depth = MaxPredDepth;
284 : }
285 8971224 : Cur->isDepthCurrent = true;
286 : }
287 12330146 : } while (!WorkList.empty());
288 4156604 : }
289 :
290 : /// Calculates the maximal path from the node to the entry.
291 18885517 : void SUnit::ComputeHeight() {
292 : SmallVector<SUnit*, 8> WorkList;
293 18885517 : WorkList.push_back(this);
294 : do {
295 22204838 : SUnit *Cur = WorkList.back();
296 :
297 : bool Done = true;
298 22204838 : unsigned MaxSuccHeight = 0;
299 57807074 : for (const SDep &SuccDep : Cur->Succs) {
300 35602236 : SUnit *SuccSU = SuccDep.getSUnit();
301 35602236 : if (SuccSU->isHeightCurrent)
302 33372816 : MaxSuccHeight = std::max(MaxSuccHeight,
303 55669053 : SuccSU->Height + SuccDep.getLatency());
304 : else {
305 : Done = false;
306 2229420 : WorkList.push_back(SuccSU);
307 : }
308 : }
309 :
310 22204838 : if (Done) {
311 : WorkList.pop_back();
312 21114938 : if (MaxSuccHeight != Cur->Height) {
313 17409070 : Cur->setHeightDirty();
314 17409070 : Cur->Height = MaxSuccHeight;
315 : }
316 21114938 : Cur->isHeightCurrent = true;
317 : }
318 22204838 : } while (!WorkList.empty());
319 18885517 : }
320 :
321 3139006 : void SUnit::biasCriticalPath() {
322 3139006 : if (NumPreds < 2)
323 : return;
324 :
325 : SUnit::pred_iterator BestI = Preds.begin();
326 : unsigned MaxDepth = BestI->getSUnit()->getDepth();
327 1445778 : for (SUnit::pred_iterator I = std::next(BestI), E = Preds.end(); I != E;
328 : ++I) {
329 1631143 : if (I->getKind() == SDep::Data && I->getSUnit()->getDepth() > MaxDepth)
330 : BestI = I;
331 : }
332 403542 : if (BestI != Preds.begin())
333 : std::swap(*Preds.begin(), *BestI);
334 : }
335 :
336 : #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
337 : LLVM_DUMP_METHOD void SUnit::dumpAttributes() const {
338 : dbgs() << " # preds left : " << NumPredsLeft << "\n";
339 : dbgs() << " # succs left : " << NumSuccsLeft << "\n";
340 : if (WeakPredsLeft)
341 : dbgs() << " # weak preds left : " << WeakPredsLeft << "\n";
342 : if (WeakSuccsLeft)
343 : dbgs() << " # weak succs left : " << WeakSuccsLeft << "\n";
344 : dbgs() << " # rdefs left : " << NumRegDefsLeft << "\n";
345 : dbgs() << " Latency : " << Latency << "\n";
346 : dbgs() << " Depth : " << getDepth() << "\n";
347 : dbgs() << " Height : " << getHeight() << "\n";
348 : }
349 :
350 : LLVM_DUMP_METHOD void ScheduleDAG::dumpNodeName(const SUnit &SU) const {
351 : if (&SU == &EntrySU)
352 : dbgs() << "EntrySU";
353 : else if (&SU == &ExitSU)
354 : dbgs() << "ExitSU";
355 : else
356 : dbgs() << "SU(" << SU.NodeNum << ")";
357 : }
358 :
359 : LLVM_DUMP_METHOD void ScheduleDAG::dumpNodeAll(const SUnit &SU) const {
360 : dumpNode(SU);
361 : SU.dumpAttributes();
362 : if (SU.Preds.size() > 0) {
363 : dbgs() << " Predecessors:\n";
364 : for (const SDep &Dep : SU.Preds) {
365 : dbgs() << " ";
366 : dumpNodeName(*Dep.getSUnit());
367 : dbgs() << ": ";
368 : Dep.dump(TRI);
369 : dbgs() << '\n';
370 : }
371 : }
372 : if (SU.Succs.size() > 0) {
373 : dbgs() << " Successors:\n";
374 : for (const SDep &Dep : SU.Succs) {
375 : dbgs() << " ";
376 : dumpNodeName(*Dep.getSUnit());
377 : dbgs() << ": ";
378 : Dep.dump(TRI);
379 : dbgs() << '\n';
380 : }
381 : }
382 : }
383 : #endif
384 :
385 : #ifndef NDEBUG
386 : unsigned ScheduleDAG::VerifyScheduledDAG(bool isBottomUp) {
387 : bool AnyNotSched = false;
388 : unsigned DeadNodes = 0;
389 : for (const SUnit &SUnit : SUnits) {
390 : if (!SUnit.isScheduled) {
391 : if (SUnit.NumPreds == 0 && SUnit.NumSuccs == 0) {
392 : ++DeadNodes;
393 : continue;
394 : }
395 : if (!AnyNotSched)
396 : dbgs() << "*** Scheduling failed! ***\n";
397 : dumpNode(SUnit);
398 : dbgs() << "has not been scheduled!\n";
399 : AnyNotSched = true;
400 : }
401 : if (SUnit.isScheduled &&
402 : (isBottomUp ? SUnit.getHeight() : SUnit.getDepth()) >
403 : unsigned(std::numeric_limits<int>::max())) {
404 : if (!AnyNotSched)
405 : dbgs() << "*** Scheduling failed! ***\n";
406 : dumpNode(SUnit);
407 : dbgs() << "has an unexpected "
408 : << (isBottomUp ? "Height" : "Depth") << " value!\n";
409 : AnyNotSched = true;
410 : }
411 : if (isBottomUp) {
412 : if (SUnit.NumSuccsLeft != 0) {
413 : if (!AnyNotSched)
414 : dbgs() << "*** Scheduling failed! ***\n";
415 : dumpNode(SUnit);
416 : dbgs() << "has successors left!\n";
417 : AnyNotSched = true;
418 : }
419 : } else {
420 : if (SUnit.NumPredsLeft != 0) {
421 : if (!AnyNotSched)
422 : dbgs() << "*** Scheduling failed! ***\n";
423 : dumpNode(SUnit);
424 : dbgs() << "has predecessors left!\n";
425 : AnyNotSched = true;
426 : }
427 : }
428 : }
429 : assert(!AnyNotSched);
430 : return SUnits.size() - DeadNodes;
431 : }
432 : #endif
433 :
434 1721911 : void ScheduleDAGTopologicalSort::InitDAGTopologicalSorting() {
435 : // The idea of the algorithm is taken from
436 : // "Online algorithms for managing the topological order of
437 : // a directed acyclic graph" by David J. Pearce and Paul H.J. Kelly
438 : // This is the MNR algorithm, which was first introduced by
439 : // A. Marchetti-Spaccamela, U. Nanni and H. Rohnert in
440 : // "Maintaining a topological order under edge insertions".
441 : //
442 : // Short description of the algorithm:
443 : //
444 : // Topological ordering, ord, of a DAG maps each node to a topological
445 : // index so that for all edges X->Y it is the case that ord(X) < ord(Y).
446 : //
447 : // This means that if there is a path from the node X to the node Z,
448 : // then ord(X) < ord(Z).
449 : //
450 : // This property can be used to check for reachability of nodes:
451 : // if Z is reachable from X, then an insertion of the edge Z->X would
452 : // create a cycle.
453 : //
454 : // The algorithm first computes a topological ordering for the DAG by
455 : // initializing the Index2Node and Node2Index arrays and then tries to keep
456 : // the ordering up-to-date after edge insertions by reordering the DAG.
457 : //
458 : // On insertion of the edge X->Y, the algorithm first marks by calling DFS
459 : // the nodes reachable from Y, and then shifts them using Shift to lie
460 : // immediately after X in Index2Node.
461 3443822 : unsigned DAGSize = SUnits.size();
462 : std::vector<SUnit*> WorkList;
463 1721911 : WorkList.reserve(DAGSize);
464 :
465 1721911 : Index2Node.resize(DAGSize);
466 1721912 : Node2Index.resize(DAGSize);
467 :
468 : // Initialize the data structures.
469 1721912 : if (ExitSU)
470 452260 : WorkList.push_back(ExitSU);
471 20878298 : for (SUnit &SU : SUnits) {
472 19156386 : int NodeNum = SU.NodeNum;
473 19156386 : unsigned Degree = SU.Succs.size();
474 : // Temporarily use the Node2Index array as scratch space for degree counts.
475 19156386 : Node2Index[NodeNum] = Degree;
476 :
477 : // Is it a node without dependencies?
478 19156386 : if (Degree == 0) {
479 : assert(SU.Succs.empty() && "SUnit should have no successors");
480 : // Collect leaf nodes.
481 1713730 : WorkList.push_back(&SU);
482 : }
483 : }
484 :
485 1721912 : int Id = DAGSize;
486 21330557 : while (!WorkList.empty()) {
487 19608646 : SUnit *SU = WorkList.back();
488 : WorkList.pop_back();
489 19608646 : if (SU->NodeNum < DAGSize)
490 19156386 : Allocate(SU->NodeNum, --Id);
491 44048051 : for (const SDep &PredDep : SU->Preds) {
492 24439406 : SUnit *SU = PredDep.getSUnit();
493 24439406 : if (SU->NodeNum < DAGSize && !--Node2Index[SU->NodeNum])
494 : // If all dependencies of the node are processed already,
495 : // then the node can be computed now.
496 17442656 : WorkList.push_back(SU);
497 : }
498 : }
499 :
500 1721911 : Visited.resize(DAGSize);
501 :
502 : #ifndef NDEBUG
503 : // Check correctness of the ordering
504 : for (SUnit &SU : SUnits) {
505 : for (const SDep &PD : SU.Preds) {
506 : assert(Node2Index[SU.NodeNum] > Node2Index[PD.getSUnit()->NodeNum] &&
507 : "Wrong topological sorting");
508 : }
509 : }
510 : #endif
511 1721912 : }
512 :
513 123734 : void ScheduleDAGTopologicalSort::AddPred(SUnit *Y, SUnit *X) {
514 : int UpperBound, LowerBound;
515 123734 : LowerBound = Node2Index[Y->NodeNum];
516 123734 : UpperBound = Node2Index[X->NodeNum];
517 123734 : bool HasLoop = false;
518 : // Is Ord(X) < Ord(Y) ?
519 123734 : if (LowerBound < UpperBound) {
520 : // Update the topological order.
521 : Visited.reset();
522 38433 : DFS(Y, UpperBound, HasLoop);
523 : assert(!HasLoop && "Inserted edge creates a loop!");
524 : // Recompute topological indexes.
525 38433 : Shift(Visited, LowerBound, UpperBound);
526 : }
527 123734 : }
528 :
529 1391 : void ScheduleDAGTopologicalSort::RemovePred(SUnit *M, SUnit *N) {
530 : // InitDAGTopologicalSorting();
531 1391 : }
532 :
533 95019 : void ScheduleDAGTopologicalSort::DFS(const SUnit *SU, int UpperBound,
534 : bool &HasLoop) {
535 : std::vector<const SUnit*> WorkList;
536 190038 : WorkList.reserve(SUnits.size());
537 :
538 95019 : WorkList.push_back(SU);
539 : do {
540 284833 : SU = WorkList.back();
541 : WorkList.pop_back();
542 284833 : Visited.set(SU->NodeNum);
543 : for (const SDep &SuccDep
544 912097 : : make_range(SU->Succs.rbegin(), SU->Succs.rend())) {
545 642484 : unsigned s = SuccDep.getSUnit()->NodeNum;
546 : // Edges to non-SUnits are allowed but ignored (e.g. ExitSU).
547 1284968 : if (s >= Node2Index.size())
548 : continue;
549 569781 : if (Node2Index[s] == UpperBound) {
550 15220 : HasLoop = true;
551 : return;
552 : }
553 : // Visit successors if not already and in affected region.
554 554561 : if (!Visited.test(s) && Node2Index[s] < UpperBound) {
555 256825 : WorkList.push_back(SuccDep.getSUnit());
556 : }
557 : }
558 269613 : } while (!WorkList.empty());
559 : }
560 :
561 0 : std::vector<int> ScheduleDAGTopologicalSort::GetSubGraph(const SUnit &StartSU,
562 : const SUnit &TargetSU,
563 : bool &Success) {
564 : std::vector<const SUnit*> WorkList;
565 0 : int LowerBound = Node2Index[StartSU.NodeNum];
566 0 : int UpperBound = Node2Index[TargetSU.NodeNum];
567 : bool Found = false;
568 : BitVector VisitedBack;
569 : std::vector<int> Nodes;
570 :
571 0 : if (LowerBound > UpperBound) {
572 0 : Success = false;
573 0 : return Nodes;
574 : }
575 :
576 0 : WorkList.reserve(SUnits.size());
577 : Visited.reset();
578 :
579 : // Starting from StartSU, visit all successors up
580 : // to UpperBound.
581 0 : WorkList.push_back(&StartSU);
582 : do {
583 0 : const SUnit *SU = WorkList.back();
584 : WorkList.pop_back();
585 0 : for (int I = SU->Succs.size()-1; I >= 0; --I) {
586 0 : const SUnit *Succ = SU->Succs[I].getSUnit();
587 0 : unsigned s = Succ->NodeNum;
588 : // Edges to non-SUnits are allowed but ignored (e.g. ExitSU).
589 0 : if (Succ->isBoundaryNode())
590 0 : continue;
591 0 : if (Node2Index[s] == UpperBound) {
592 : Found = true;
593 : continue;
594 : }
595 : // Visit successors if not already and in affected region.
596 0 : if (!Visited.test(s) && Node2Index[s] < UpperBound) {
597 : Visited.set(s);
598 0 : WorkList.push_back(Succ);
599 : }
600 : }
601 0 : } while (!WorkList.empty());
602 :
603 0 : if (!Found) {
604 0 : Success = false;
605 0 : return Nodes;
606 : }
607 :
608 : WorkList.clear();
609 0 : VisitedBack.resize(SUnits.size());
610 : Found = false;
611 :
612 : // Starting from TargetSU, visit all predecessors up
613 : // to LowerBound. SUs that are visited by the two
614 : // passes are added to Nodes.
615 0 : WorkList.push_back(&TargetSU);
616 : do {
617 0 : const SUnit *SU = WorkList.back();
618 : WorkList.pop_back();
619 0 : for (int I = SU->Preds.size()-1; I >= 0; --I) {
620 0 : const SUnit *Pred = SU->Preds[I].getSUnit();
621 0 : unsigned s = Pred->NodeNum;
622 : // Edges to non-SUnits are allowed but ignored (e.g. EntrySU).
623 0 : if (Pred->isBoundaryNode())
624 0 : continue;
625 0 : if (Node2Index[s] == LowerBound) {
626 : Found = true;
627 : continue;
628 : }
629 0 : if (!VisitedBack.test(s) && Visited.test(s)) {
630 : VisitedBack.set(s);
631 0 : WorkList.push_back(Pred);
632 0 : Nodes.push_back(s);
633 : }
634 : }
635 0 : } while (!WorkList.empty());
636 :
637 : assert(Found && "Error in SUnit Graph!");
638 0 : Success = true;
639 0 : return Nodes;
640 : }
641 :
642 38433 : void ScheduleDAGTopologicalSort::Shift(BitVector& Visited, int LowerBound,
643 : int UpperBound) {
644 : std::vector<int> L;
645 : int shift = 0;
646 : int i;
647 :
648 556975 : for (i = LowerBound; i <= UpperBound; ++i) {
649 : // w is node at topological index i.
650 518542 : int w = Index2Node[i];
651 1037084 : if (Visited.test(w)) {
652 : // Unmark.
653 : Visited.reset(w);
654 95457 : L.push_back(w);
655 95457 : shift = shift + 1;
656 : } else {
657 423085 : Allocate(w, i - shift);
658 : }
659 : }
660 :
661 133890 : for (unsigned LI : L) {
662 95457 : Allocate(LI, i - shift);
663 95457 : i = i + 1;
664 : }
665 38433 : }
666 :
667 3423 : bool ScheduleDAGTopologicalSort::WillCreateCycle(SUnit *TargetSU, SUnit *SU) {
668 : // Is SU reachable from TargetSU via successor edges?
669 3423 : if (IsReachable(SU, TargetSU))
670 : return true;
671 4613 : for (const SDep &PredDep : TargetSU->Preds)
672 983 : if (PredDep.isAssignedRegDep() &&
673 983 : IsReachable(SU, PredDep.getSUnit()))
674 : return true;
675 : return false;
676 : }
677 :
678 145503 : bool ScheduleDAGTopologicalSort::IsReachable(const SUnit *SU,
679 : const SUnit *TargetSU) {
680 : // If insertion of the edge SU->TargetSU would create a cycle
681 : // then there is a path from TargetSU to SU.
682 : int UpperBound, LowerBound;
683 145503 : LowerBound = Node2Index[TargetSU->NodeNum];
684 145503 : UpperBound = Node2Index[SU->NodeNum];
685 145503 : bool HasLoop = false;
686 : // Is Ord(TargetSU) < Ord(SU) ?
687 145503 : if (LowerBound < UpperBound) {
688 : Visited.reset();
689 : // There may be a path from TargetSU to SU. Check for it.
690 56586 : DFS(TargetSU, UpperBound, HasLoop);
691 : }
692 145503 : return HasLoop;
693 : }
694 :
695 19674928 : void ScheduleDAGTopologicalSort::Allocate(int n, int index) {
696 39349856 : Node2Index[n] = index;
697 39349856 : Index2Node[index] = n;
698 19674928 : }
699 :
700 1458721 : ScheduleDAGTopologicalSort::
701 1458721 : ScheduleDAGTopologicalSort(std::vector<SUnit> &sunits, SUnit *exitsu)
702 2917442 : : SUnits(sunits), ExitSU(exitsu) {}
703 :
704 : ScheduleHazardRecognizer::~ScheduleHazardRecognizer() = default;
|
