Bug Summary

File:llvm/lib/CodeGen/ScheduleDAG.cpp
Warning:line 647, column 3
Value stored to 'Found' is never read

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name ScheduleDAG.cpp -analyzer-store=region -analyzer-opt-analyze-nested-blocks -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=cplusplus -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -setup-static-analyzer -analyzer-config-compatibility-mode=true -mrelocation-model pic -pic-level 2 -mframe-pointer=none -fmath-errno -fno-rounding-math -mconstructor-aliases -munwind-tables -target-cpu x86-64 -tune-cpu generic -debugger-tuning=gdb -ffunction-sections -fdata-sections -fcoverage-compilation-dir=/build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/build-llvm/lib/CodeGen -resource-dir /usr/lib/llvm-14/lib/clang/14.0.0 -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/build-llvm/lib/CodeGen -I /build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/llvm/lib/CodeGen -I /build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/build-llvm/include -I /build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/llvm/include -D NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/x86_64-linux-gnu/c++/10 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10/backward -internal-isystem /usr/lib/llvm-14/lib/clang/14.0.0/include -internal-isystem /usr/local/include -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../x86_64-linux-gnu/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -O2 -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-maybe-uninitialized -Wno-class-memaccess -Wno-redundant-move -Wno-pessimizing-move -Wno-noexcept-type -Wno-comment -std=c++14 -fdeprecated-macro -fdebug-compilation-dir=/build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/build-llvm/lib/CodeGen -fdebug-prefix-map=/build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e=. -ferror-limit 19 -fvisibility-inlines-hidden -stack-protector 2 -fgnuc-version=4.2.1 -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -faddrsig -D__GCC_HAVE_DWARF2_CFI_ASM=1 -o /tmp/scan-build-2021-09-04-040900-46481-1 -x c++ /build/llvm-toolchain-snapshot-14~++20210903100615+fd66b44ec19e/llvm/lib/CodeGen/ScheduleDAG.cpp
1//===- ScheduleDAG.cpp - Implement the ScheduleDAG class ------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9/// \file Implements the ScheduleDAG class, which is a base class used by
10/// scheduling implementation classes.
11//
12//===----------------------------------------------------------------------===//
13
14#include "llvm/CodeGen/ScheduleDAG.h"
15#include "llvm/ADT/STLExtras.h"
16#include "llvm/ADT/SmallVector.h"
17#include "llvm/ADT/Statistic.h"
18#include "llvm/ADT/iterator_range.h"
19#include "llvm/CodeGen/MachineFunction.h"
20#include "llvm/CodeGen/ScheduleHazardRecognizer.h"
21#include "llvm/CodeGen/SelectionDAGNodes.h"
22#include "llvm/CodeGen/TargetInstrInfo.h"
23#include "llvm/CodeGen/TargetRegisterInfo.h"
24#include "llvm/CodeGen/TargetSubtargetInfo.h"
25#include "llvm/Config/llvm-config.h"
26#include "llvm/Support/CommandLine.h"
27#include "llvm/Support/Compiler.h"
28#include "llvm/Support/Debug.h"
29#include "llvm/Support/raw_ostream.h"
30#include <algorithm>
31#include <cassert>
32#include <iterator>
33#include <limits>
34#include <utility>
35#include <vector>
36
37using namespace llvm;
38
39#define DEBUG_TYPE"pre-RA-sched" "pre-RA-sched"
40
41STATISTIC(NumNewPredsAdded, "Number of times a single predecessor was added")static llvm::Statistic NumNewPredsAdded = {"pre-RA-sched", "NumNewPredsAdded"
, "Number of times a single predecessor was added"};
42STATISTIC(NumTopoInits,static llvm::Statistic NumTopoInits = {"pre-RA-sched", "NumTopoInits"
, "Number of times the topological order has been recomputed"
}
43 "Number of times the topological order has been recomputed")static llvm::Statistic NumTopoInits = {"pre-RA-sched", "NumTopoInits"
, "Number of times the topological order has been recomputed"
};
44
45#ifndef NDEBUG1
46static cl::opt<bool> StressSchedOpt(
47 "stress-sched", cl::Hidden, cl::init(false),
48 cl::desc("Stress test instruction scheduling"));
49#endif
50
51void SchedulingPriorityQueue::anchor() {}
52
53ScheduleDAG::ScheduleDAG(MachineFunction &mf)
54 : TM(mf.getTarget()), TII(mf.getSubtarget().getInstrInfo()),
55 TRI(mf.getSubtarget().getRegisterInfo()), MF(mf),
56 MRI(mf.getRegInfo()) {
57#ifndef NDEBUG1
58 StressSched = StressSchedOpt;
59#endif
60}
61
62ScheduleDAG::~ScheduleDAG() = default;
63
64void ScheduleDAG::clearDAG() {
65 SUnits.clear();
66 EntrySU = SUnit();
67 ExitSU = SUnit();
68}
69
70const MCInstrDesc *ScheduleDAG::getNodeDesc(const SDNode *Node) const {
71 if (!Node || !Node->isMachineOpcode()) return nullptr;
72 return &TII->get(Node->getMachineOpcode());
73}
74
75LLVM_DUMP_METHOD__attribute__((noinline)) __attribute__((__used__)) void SDep::dump(const TargetRegisterInfo *TRI) const {
76 switch (getKind()) {
77 case Data: dbgs() << "Data"; break;
78 case Anti: dbgs() << "Anti"; break;
79 case Output: dbgs() << "Out "; break;
80 case Order: dbgs() << "Ord "; break;
81 }
82
83 switch (getKind()) {
84 case Data:
85 dbgs() << " Latency=" << getLatency();
86 if (TRI && isAssignedRegDep())
87 dbgs() << " Reg=" << printReg(getReg(), TRI);
88 break;
89 case Anti:
90 case Output:
91 dbgs() << " Latency=" << getLatency();
92 break;
93 case Order:
94 dbgs() << " Latency=" << getLatency();
95 switch(Contents.OrdKind) {
96 case Barrier: dbgs() << " Barrier"; break;
97 case MayAliasMem:
98 case MustAliasMem: dbgs() << " Memory"; break;
99 case Artificial: dbgs() << " Artificial"; break;
100 case Weak: dbgs() << " Weak"; break;
101 case Cluster: dbgs() << " Cluster"; break;
102 }
103 break;
104 }
105}
106
107bool SUnit::addPred(const SDep &D, bool Required) {
108 // If this node already has this dependence, don't add a redundant one.
109 for (SDep &PredDep : Preds) {
110 // Zero-latency weak edges may be added purely for heuristic ordering. Don't
111 // add them if another kind of edge already exists.
112 if (!Required && PredDep.getSUnit() == D.getSUnit())
113 return false;
114 if (PredDep.overlaps(D)) {
115 // Extend the latency if needed. Equivalent to
116 // removePred(PredDep) + addPred(D).
117 if (PredDep.getLatency() < D.getLatency()) {
118 SUnit *PredSU = PredDep.getSUnit();
119 // Find the corresponding successor in N.
120 SDep ForwardD = PredDep;
121 ForwardD.setSUnit(this);
122 for (SDep &SuccDep : PredSU->Succs) {
123 if (SuccDep == ForwardD) {
124 SuccDep.setLatency(D.getLatency());
125 break;
126 }
127 }
128 PredDep.setLatency(D.getLatency());
129 }
130 return false;
131 }
132 }
133 // Now add a corresponding succ to N.
134 SDep P = D;
135 P.setSUnit(this);
136 SUnit *N = D.getSUnit();
137 // Update the bookkeeping.
138 if (D.getKind() == SDep::Data) {
139 assert(NumPreds < std::numeric_limits<unsigned>::max() &&(static_cast<void> (0))
140 "NumPreds will overflow!")(static_cast<void> (0));
141 assert(N->NumSuccs < std::numeric_limits<unsigned>::max() &&(static_cast<void> (0))
142 "NumSuccs will overflow!")(static_cast<void> (0));
143 ++NumPreds;
144 ++N->NumSuccs;
145 }
146 if (!N->isScheduled) {
147 if (D.isWeak()) {
148 ++WeakPredsLeft;
149 }
150 else {
151 assert(NumPredsLeft < std::numeric_limits<unsigned>::max() &&(static_cast<void> (0))
152 "NumPredsLeft will overflow!")(static_cast<void> (0));
153 ++NumPredsLeft;
154 }
155 }
156 if (!isScheduled) {
157 if (D.isWeak()) {
158 ++N->WeakSuccsLeft;
159 }
160 else {
161 assert(N->NumSuccsLeft < std::numeric_limits<unsigned>::max() &&(static_cast<void> (0))
162 "NumSuccsLeft will overflow!")(static_cast<void> (0));
163 ++N->NumSuccsLeft;
164 }
165 }
166 Preds.push_back(D);
167 N->Succs.push_back(P);
168 if (P.getLatency() != 0) {
169 this->setDepthDirty();
170 N->setHeightDirty();
171 }
172 return true;
173}
174
175void SUnit::removePred(const SDep &D) {
176 // Find the matching predecessor.
177 SmallVectorImpl<SDep>::iterator I = llvm::find(Preds, D);
178 if (I == Preds.end())
179 return;
180 // Find the corresponding successor in N.
181 SDep P = D;
182 P.setSUnit(this);
183 SUnit *N = D.getSUnit();
184 SmallVectorImpl<SDep>::iterator Succ = llvm::find(N->Succs, P);
185 assert(Succ != N->Succs.end() && "Mismatching preds / succs lists!")(static_cast<void> (0));
186 N->Succs.erase(Succ);
187 Preds.erase(I);
188 // Update the bookkeeping.
189 if (P.getKind() == SDep::Data) {
190 assert(NumPreds > 0 && "NumPreds will underflow!")(static_cast<void> (0));
191 assert(N->NumSuccs > 0 && "NumSuccs will underflow!")(static_cast<void> (0));
192 --NumPreds;
193 --N->NumSuccs;
194 }
195 if (!N->isScheduled) {
196 if (D.isWeak())
197 --WeakPredsLeft;
198 else {
199 assert(NumPredsLeft > 0 && "NumPredsLeft will underflow!")(static_cast<void> (0));
200 --NumPredsLeft;
201 }
202 }
203 if (!isScheduled) {
204 if (D.isWeak())
205 --N->WeakSuccsLeft;
206 else {
207 assert(N->NumSuccsLeft > 0 && "NumSuccsLeft will underflow!")(static_cast<void> (0));
208 --N->NumSuccsLeft;
209 }
210 }
211 if (P.getLatency() != 0) {
212 this->setDepthDirty();
213 N->setHeightDirty();
214 }
215}
216
217void SUnit::setDepthDirty() {
218 if (!isDepthCurrent) return;
219 SmallVector<SUnit*, 8> WorkList;
220 WorkList.push_back(this);
221 do {
222 SUnit *SU = WorkList.pop_back_val();
223 SU->isDepthCurrent = false;
224 for (SDep &SuccDep : SU->Succs) {
225 SUnit *SuccSU = SuccDep.getSUnit();
226 if (SuccSU->isDepthCurrent)
227 WorkList.push_back(SuccSU);
228 }
229 } while (!WorkList.empty());
230}
231
232void SUnit::setHeightDirty() {
233 if (!isHeightCurrent) return;
234 SmallVector<SUnit*, 8> WorkList;
235 WorkList.push_back(this);
236 do {
237 SUnit *SU = WorkList.pop_back_val();
238 SU->isHeightCurrent = false;
239 for (SDep &PredDep : SU->Preds) {
240 SUnit *PredSU = PredDep.getSUnit();
241 if (PredSU->isHeightCurrent)
242 WorkList.push_back(PredSU);
243 }
244 } while (!WorkList.empty());
245}
246
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(this);
267 do {
268 SUnit *Cur = WorkList.back();
269
270 bool Done = true;
271 unsigned MaxPredDepth = 0;
272 for (const SDep &PredDep : Cur->Preds) {
273 SUnit *PredSU = PredDep.getSUnit();
274 if (PredSU->isDepthCurrent)
275 MaxPredDepth = std::max(MaxPredDepth,
276 PredSU->Depth + PredDep.getLatency());
277 else {
278 Done = false;
279 WorkList.push_back(PredSU);
280 }
281 }
282
283 if (Done) {
284 WorkList.pop_back();
285 if (MaxPredDepth != Cur->Depth) {
286 Cur->setDepthDirty();
287 Cur->Depth = MaxPredDepth;
288 }
289 Cur->isDepthCurrent = true;
290 }
291 } while (!WorkList.empty());
292}
293
294/// Calculates the maximal path from the node to the entry.
295void SUnit::ComputeHeight() {
296 SmallVector<SUnit*, 8> WorkList;
297 WorkList.push_back(this);
298 do {
299 SUnit *Cur = WorkList.back();
300
301 bool Done = true;
302 unsigned MaxSuccHeight = 0;
303 for (const SDep &SuccDep : Cur->Succs) {
304 SUnit *SuccSU = SuccDep.getSUnit();
305 if (SuccSU->isHeightCurrent)
306 MaxSuccHeight = std::max(MaxSuccHeight,
307 SuccSU->Height + SuccDep.getLatency());
308 else {
309 Done = false;
310 WorkList.push_back(SuccSU);
311 }
312 }
313
314 if (Done) {
315 WorkList.pop_back();
316 if (MaxSuccHeight != Cur->Height) {
317 Cur->setHeightDirty();
318 Cur->Height = MaxSuccHeight;
319 }
320 Cur->isHeightCurrent = true;
321 }
322 } while (!WorkList.empty());
323}
324
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(BestI), E = Preds.end(); I != E;
332 ++I) {
333 if (I->getKind() == SDep::Data && I->getSUnit()->getDepth() > MaxDepth)
334 BestI = I;
335 }
336 if (BestI != Preds.begin())
337 std::swap(*Preds.begin(), *BestI);
338}
339
340#if !defined(NDEBUG1) || defined(LLVM_ENABLE_DUMP)
341LLVM_DUMP_METHOD__attribute__((noinline)) __attribute__((__used__)) void SUnit::dumpAttributes() const {
342 dbgs() << " # preds left : " << NumPredsLeft << "\n";
343 dbgs() << " # succs left : " << NumSuccsLeft << "\n";
344 if (WeakPredsLeft)
345 dbgs() << " # weak preds left : " << WeakPredsLeft << "\n";
346 if (WeakSuccsLeft)
347 dbgs() << " # weak succs left : " << WeakSuccsLeft << "\n";
348 dbgs() << " # rdefs left : " << NumRegDefsLeft << "\n";
349 dbgs() << " Latency : " << Latency << "\n";
350 dbgs() << " Depth : " << getDepth() << "\n";
351 dbgs() << " Height : " << getHeight() << "\n";
352}
353
354LLVM_DUMP_METHOD__attribute__((noinline)) __attribute__((__used__)) void ScheduleDAG::dumpNodeName(const SUnit &SU) const {
355 if (&SU == &EntrySU)
356 dbgs() << "EntrySU";
357 else if (&SU == &ExitSU)
358 dbgs() << "ExitSU";
359 else
360 dbgs() << "SU(" << SU.NodeNum << ")";
361}
362
363LLVM_DUMP_METHOD__attribute__((noinline)) __attribute__((__used__)) void ScheduleDAG::dumpNodeAll(const SUnit &SU) const {
364 dumpNode(SU);
365 SU.dumpAttributes();
366 if (SU.Preds.size() > 0) {
367 dbgs() << " Predecessors:\n";
368 for (const SDep &Dep : SU.Preds) {
369 dbgs() << " ";
370 dumpNodeName(*Dep.getSUnit());
371 dbgs() << ": ";
372 Dep.dump(TRI);
373 dbgs() << '\n';
374 }
375 }
376 if (SU.Succs.size() > 0) {
377 dbgs() << " Successors:\n";
378 for (const SDep &Dep : SU.Succs) {
379 dbgs() << " ";
380 dumpNodeName(*Dep.getSUnit());
381 dbgs() << ": ";
382 Dep.dump(TRI);
383 dbgs() << '\n';
384 }
385 }
386}
387#endif
388
389#ifndef NDEBUG1
390unsigned ScheduleDAG::VerifyScheduledDAG(bool isBottomUp) {
391 bool AnyNotSched = false;
392 unsigned DeadNodes = 0;
393 for (const SUnit &SUnit : SUnits) {
394 if (!SUnit.isScheduled) {
395 if (SUnit.NumPreds == 0 && SUnit.NumSuccs == 0) {
396 ++DeadNodes;
397 continue;
398 }
399 if (!AnyNotSched)
400 dbgs() << "*** Scheduling failed! ***\n";
401 dumpNode(SUnit);
402 dbgs() << "has not been scheduled!\n";
403 AnyNotSched = true;
404 }
405 if (SUnit.isScheduled &&
406 (isBottomUp ? SUnit.getHeight() : SUnit.getDepth()) >
407 unsigned(std::numeric_limits<int>::max())) {
408 if (!AnyNotSched)
409 dbgs() << "*** Scheduling failed! ***\n";
410 dumpNode(SUnit);
411 dbgs() << "has an unexpected "
412 << (isBottomUp ? "Height" : "Depth") << " value!\n";
413 AnyNotSched = true;
414 }
415 if (isBottomUp) {
416 if (SUnit.NumSuccsLeft != 0) {
417 if (!AnyNotSched)
418 dbgs() << "*** Scheduling failed! ***\n";
419 dumpNode(SUnit);
420 dbgs() << "has successors left!\n";
421 AnyNotSched = true;
422 }
423 } else {
424 if (SUnit.NumPredsLeft != 0) {
425 if (!AnyNotSched)
426 dbgs() << "*** Scheduling failed! ***\n";
427 dumpNode(SUnit);
428 dbgs() << "has predecessors left!\n";
429 AnyNotSched = true;
430 }
431 }
432 }
433 assert(!AnyNotSched)(static_cast<void> (0));
434 return SUnits.size() - DeadNodes;
435}
436#endif
437
438void ScheduleDAGTopologicalSort::InitDAGTopologicalSorting() {
439 // The idea of the algorithm is taken from
440 // "Online algorithms for managing the topological order of
441 // a directed acyclic graph" by David J. Pearce and Paul H.J. Kelly
442 // This is the MNR algorithm, which was first introduced by
443 // A. Marchetti-Spaccamela, U. Nanni and H. Rohnert in
444 // "Maintaining a topological order under edge insertions".
445 //
446 // Short description of the algorithm:
447 //
448 // Topological ordering, ord, of a DAG maps each node to a topological
449 // index so that for all edges X->Y it is the case that ord(X) < ord(Y).
450 //
451 // This means that if there is a path from the node X to the node Z,
452 // then ord(X) < ord(Z).
453 //
454 // This property can be used to check for reachability of nodes:
455 // if Z is reachable from X, then an insertion of the edge Z->X would
456 // create a cycle.
457 //
458 // The algorithm first computes a topological ordering for the DAG by
459 // initializing the Index2Node and Node2Index arrays and then tries to keep
460 // the ordering up-to-date after edge insertions by reordering the DAG.
461 //
462 // On insertion of the edge X->Y, the algorithm first marks by calling DFS
463 // the nodes reachable from Y, and then shifts them using Shift to lie
464 // immediately after X in Index2Node.
465
466 // Cancel pending updates, mark as valid.
467 Dirty = false;
468 Updates.clear();
469
470 unsigned DAGSize = SUnits.size();
471 std::vector<SUnit*> WorkList;
472 WorkList.reserve(DAGSize);
473
474 Index2Node.resize(DAGSize);
475 Node2Index.resize(DAGSize);
476
477 // Initialize the data structures.
478 if (ExitSU)
479 WorkList.push_back(ExitSU);
480 for (SUnit &SU : SUnits) {
481 int NodeNum = SU.NodeNum;
482 unsigned Degree = SU.Succs.size();
483 // Temporarily use the Node2Index array as scratch space for degree counts.
484 Node2Index[NodeNum] = Degree;
485
486 // Is it a node without dependencies?
487 if (Degree == 0) {
488 assert(SU.Succs.empty() && "SUnit should have no successors")(static_cast<void> (0));
489 // Collect leaf nodes.
490 WorkList.push_back(&SU);
491 }
492 }
493
494 int Id = DAGSize;
495 while (!WorkList.empty()) {
496 SUnit *SU = WorkList.back();
497 WorkList.pop_back();
498 if (SU->NodeNum < DAGSize)
499 Allocate(SU->NodeNum, --Id);
500 for (const SDep &PredDep : SU->Preds) {
501 SUnit *SU = PredDep.getSUnit();
502 if (SU->NodeNum < DAGSize && !--Node2Index[SU->NodeNum])
503 // If all dependencies of the node are processed already,
504 // then the node can be computed now.
505 WorkList.push_back(SU);
506 }
507 }
508
509 Visited.resize(DAGSize);
510 NumTopoInits++;
511
512#ifndef NDEBUG1
513 // Check correctness of the ordering
514 for (SUnit &SU : SUnits) {
515 for (const SDep &PD : SU.Preds) {
516 assert(Node2Index[SU.NodeNum] > Node2Index[PD.getSUnit()->NodeNum] &&(static_cast<void> (0))
517 "Wrong topological sorting")(static_cast<void> (0));
518 }
519 }
520#endif
521}
522
523void ScheduleDAGTopologicalSort::FixOrder() {
524 // Recompute from scratch after new nodes have been added.
525 if (Dirty) {
526 InitDAGTopologicalSorting();
527 return;
528 }
529
530 // Otherwise apply updates one-by-one.
531 for (auto &U : Updates)
532 AddPred(U.first, U.second);
533 Updates.clear();
534}
535
536void ScheduleDAGTopologicalSort::AddPredQueued(SUnit *Y, SUnit *X) {
537 // Recomputing the order from scratch is likely more efficient than applying
538 // updates one-by-one for too many updates. The current cut-off is arbitrarily
539 // chosen.
540 Dirty = Dirty || Updates.size() > 10;
541
542 if (Dirty)
543 return;
544
545 Updates.emplace_back(Y, X);
546}
547
548void ScheduleDAGTopologicalSort::AddPred(SUnit *Y, SUnit *X) {
549 int UpperBound, LowerBound;
550 LowerBound = Node2Index[Y->NodeNum];
551 UpperBound = Node2Index[X->NodeNum];
552 bool HasLoop = false;
553 // Is Ord(X) < Ord(Y) ?
554 if (LowerBound < UpperBound) {
555 // Update the topological order.
556 Visited.reset();
557 DFS(Y, UpperBound, HasLoop);
558 assert(!HasLoop && "Inserted edge creates a loop!")(static_cast<void> (0));
559 // Recompute topological indexes.
560 Shift(Visited, LowerBound, UpperBound);
561 }
562
563 NumNewPredsAdded++;
564}
565
566void ScheduleDAGTopologicalSort::RemovePred(SUnit *M, SUnit *N) {
567 // InitDAGTopologicalSorting();
568}
569
570void ScheduleDAGTopologicalSort::DFS(const SUnit *SU, int UpperBound,
571 bool &HasLoop) {
572 std::vector<const SUnit*> WorkList;
573 WorkList.reserve(SUnits.size());
574
575 WorkList.push_back(SU);
576 do {
577 SU = WorkList.back();
578 WorkList.pop_back();
579 Visited.set(SU->NodeNum);
580 for (const SDep &SuccDep
581 : make_range(SU->Succs.rbegin(), SU->Succs.rend())) {
582 unsigned s = SuccDep.getSUnit()->NodeNum;
583 // Edges to non-SUnits are allowed but ignored (e.g. ExitSU).
584 if (s >= Node2Index.size())
585 continue;
586 if (Node2Index[s] == UpperBound) {
587 HasLoop = true;
588 return;
589 }
590 // Visit successors if not already and in affected region.
591 if (!Visited.test(s) && Node2Index[s] < UpperBound) {
592 WorkList.push_back(SuccDep.getSUnit());
593 }
594 }
595 } while (!WorkList.empty());
596}
597
598std::vector<int> ScheduleDAGTopologicalSort::GetSubGraph(const SUnit &StartSU,
599 const SUnit &TargetSU,
600 bool &Success) {
601 std::vector<const SUnit*> WorkList;
602 int LowerBound = Node2Index[StartSU.NodeNum];
603 int UpperBound = Node2Index[TargetSU.NodeNum];
604 bool Found = false;
605 BitVector VisitedBack;
606 std::vector<int> Nodes;
607
608 if (LowerBound > UpperBound) {
609 Success = false;
610 return Nodes;
611 }
612
613 WorkList.reserve(SUnits.size());
614 Visited.reset();
615
616 // Starting from StartSU, visit all successors up
617 // to UpperBound.
618 WorkList.push_back(&StartSU);
619 do {
620 const SUnit *SU = WorkList.back();
621 WorkList.pop_back();
622 for (int I = SU->Succs.size()-1; I >= 0; --I) {
623 const SUnit *Succ = SU->Succs[I].getSUnit();
624 unsigned s = Succ->NodeNum;
625 // Edges to non-SUnits are allowed but ignored (e.g. ExitSU).
626 if (Succ->isBoundaryNode())
627 continue;
628 if (Node2Index[s] == UpperBound) {
629 Found = true;
630 continue;
631 }
632 // Visit successors if not already and in affected region.
633 if (!Visited.test(s) && Node2Index[s] < UpperBound) {
634 Visited.set(s);
635 WorkList.push_back(Succ);
636 }
637 }
638 } while (!WorkList.empty());
639
640 if (!Found) {
641 Success = false;
642 return Nodes;
643 }
644
645 WorkList.clear();
646 VisitedBack.resize(SUnits.size());
647 Found = false;
Value stored to 'Found' is never read
648
649 // Starting from TargetSU, visit all predecessors up
650 // to LowerBound. SUs that are visited by the two
651 // passes are added to Nodes.
652 WorkList.push_back(&TargetSU);
653 do {
654 const SUnit *SU = WorkList.back();
655 WorkList.pop_back();
656 for (int I = SU->Preds.size()-1; I >= 0; --I) {
657 const SUnit *Pred = SU->Preds[I].getSUnit();
658 unsigned s = Pred->NodeNum;
659 // Edges to non-SUnits are allowed but ignored (e.g. EntrySU).
660 if (Pred->isBoundaryNode())
661 continue;
662 if (Node2Index[s] == LowerBound) {
663 Found = true;
664 continue;
665 }
666 if (!VisitedBack.test(s) && Visited.test(s)) {
667 VisitedBack.set(s);
668 WorkList.push_back(Pred);
669 Nodes.push_back(s);
670 }
671 }
672 } while (!WorkList.empty());
673
674 assert(Found && "Error in SUnit Graph!")(static_cast<void> (0));
675 Success = true;
676 return Nodes;
677}
678
679void ScheduleDAGTopologicalSort::Shift(BitVector& Visited, int LowerBound,
680 int UpperBound) {
681 std::vector<int> L;
682 int shift = 0;
683 int i;
684
685 for (i = LowerBound; i <= UpperBound; ++i) {
686 // w is node at topological index i.
687 int w = Index2Node[i];
688 if (Visited.test(w)) {
689 // Unmark.
690 Visited.reset(w);
691 L.push_back(w);
692 shift = shift + 1;
693 } else {
694 Allocate(w, i - shift);
695 }
696 }
697
698 for (unsigned LI : L) {
699 Allocate(LI, i - shift);
700 i = i + 1;
701 }
702}
703
704bool ScheduleDAGTopologicalSort::WillCreateCycle(SUnit *TargetSU, SUnit *SU) {
705 FixOrder();
706 // Is SU reachable from TargetSU via successor edges?
707 if (IsReachable(SU, TargetSU))
708 return true;
709 for (const SDep &PredDep : TargetSU->Preds)
710 if (PredDep.isAssignedRegDep() &&
711 IsReachable(SU, PredDep.getSUnit()))
712 return true;
713 return false;
714}
715
716void ScheduleDAGTopologicalSort::AddSUnitWithoutPredecessors(const SUnit *SU) {
717 assert(SU->NodeNum == Index2Node.size() && "Node cannot be added at the end")(static_cast<void> (0));
718 assert(SU->NumPreds == 0 && "Can only add SU's with no predecessors")(static_cast<void> (0));
719 Node2Index.push_back(Index2Node.size());
720 Index2Node.push_back(SU->NodeNum);
721 Visited.resize(Node2Index.size());
722}
723
724bool ScheduleDAGTopologicalSort::IsReachable(const SUnit *SU,
725 const SUnit *TargetSU) {
726 FixOrder();
727 // If insertion of the edge SU->TargetSU would create a cycle
728 // then there is a path from TargetSU to SU.
729 int UpperBound, LowerBound;
730 LowerBound = Node2Index[TargetSU->NodeNum];
731 UpperBound = Node2Index[SU->NodeNum];
732 bool HasLoop = false;
733 // Is Ord(TargetSU) < Ord(SU) ?
734 if (LowerBound < UpperBound) {
735 Visited.reset();
736 // There may be a path from TargetSU to SU. Check for it.
737 DFS(TargetSU, UpperBound, HasLoop);
738 }
739 return HasLoop;
740}
741
742void ScheduleDAGTopologicalSort::Allocate(int n, int index) {
743 Node2Index[n] = index;
744 Index2Node[index] = n;
745}
746
747ScheduleDAGTopologicalSort::
748ScheduleDAGTopologicalSort(std::vector<SUnit> &sunits, SUnit *exitsu)
749 : SUnits(sunits), ExitSU(exitsu) {}
750
751ScheduleHazardRecognizer::~ScheduleHazardRecognizer() = default;