LLVM 17.0.0git
ScheduleDAG.h
Go to the documentation of this file.
1//===- llvm/CodeGen/ScheduleDAG.h - Common Base Class -----------*- C++ -*-===//
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 used as the common base
10/// class for instruction schedulers. This encapsulates the scheduling DAG,
11/// which is shared between SelectionDAG and MachineInstr scheduling.
12//
13//===----------------------------------------------------------------------===//
14
15#ifndef LLVM_CODEGEN_SCHEDULEDAG_H
16#define LLVM_CODEGEN_SCHEDULEDAG_H
17
18#include "llvm/ADT/BitVector.h"
21#include "llvm/ADT/iterator.h"
25#include <cassert>
26#include <cstddef>
27#include <iterator>
28#include <string>
29#include <vector>
30
31namespace llvm {
32
33template <class GraphType> struct GraphTraits;
34template<class Graph> class GraphWriter;
35class LLVMTargetMachine;
36class MachineFunction;
37class MachineRegisterInfo;
38class MCInstrDesc;
39struct MCSchedClassDesc;
40class SDNode;
41class SUnit;
42class ScheduleDAG;
43class TargetInstrInfo;
44class TargetRegisterClass;
45class TargetRegisterInfo;
46
47 /// Scheduling dependency. This represents one direction of an edge in the
48 /// scheduling DAG.
49 class SDep {
50 public:
51 /// These are the different kinds of scheduling dependencies.
52 enum Kind {
53 Data, ///< Regular data dependence (aka true-dependence).
54 Anti, ///< A register anti-dependence (aka WAR).
55 Output, ///< A register output-dependence (aka WAW).
56 Order ///< Any other ordering dependency.
57 };
58
59 // Strong dependencies must be respected by the scheduler. Artificial
60 // dependencies may be removed only if they are redundant with another
61 // strong dependence.
62 //
63 // Weak dependencies may be violated by the scheduling strategy, but only if
64 // the strategy can prove it is correct to do so.
65 //
66 // Strong OrderKinds must occur before "Weak".
67 // Weak OrderKinds must occur after "Weak".
68 enum OrderKind {
69 Barrier, ///< An unknown scheduling barrier.
70 MayAliasMem, ///< Nonvolatile load/Store instructions that may alias.
71 MustAliasMem, ///< Nonvolatile load/Store instructions that must alias.
72 Artificial, ///< Arbitrary strong DAG edge (no real dependence).
73 Weak, ///< Arbitrary weak DAG edge.
74 Cluster ///< Weak DAG edge linking a chain of clustered instrs.
75 };
76
77 private:
78 /// A pointer to the depending/depended-on SUnit, and an enum
79 /// indicating the kind of the dependency.
81
82 /// A union discriminated by the dependence kind.
83 union {
84 /// For Data, Anti, and Output dependencies, the associated register. For
85 /// Data dependencies that don't currently have a register/ assigned, this
86 /// is set to zero.
87 unsigned Reg;
88
89 /// Additional information about Order dependencies.
90 unsigned OrdKind; // enum OrderKind
91 } Contents;
92
93 /// The time associated with this edge. Often this is just the value of the
94 /// Latency field of the predecessor, however advanced models may provide
95 /// additional information about specific edges.
96 unsigned Latency = 0u;
97
98 public:
99 /// Constructs a null SDep. This is only for use by container classes which
100 /// require default constructors. SUnits may not/ have null SDep edges.
101 SDep() : Dep(nullptr, Data) {}
102
103 /// Constructs an SDep with the specified values.
104 SDep(SUnit *S, Kind kind, unsigned Reg)
105 : Dep(S, kind), Contents() {
106 switch (kind) {
107 default:
108 llvm_unreachable("Reg given for non-register dependence!");
109 case Anti:
110 case Output:
111 assert(Reg != 0 &&
112 "SDep::Anti and SDep::Output must use a non-zero Reg!");
113 Contents.Reg = Reg;
114 Latency = 0;
115 break;
116 case Data:
117 Contents.Reg = Reg;
118 Latency = 1;
119 break;
120 }
121 }
122
124 : Dep(S, Order), Contents(), Latency(0) {
125 Contents.OrdKind = kind;
126 }
127
128 /// Returns true if the specified SDep is equivalent except for latency.
129 bool overlaps(const SDep &Other) const;
130
131 bool operator==(const SDep &Other) const {
132 return overlaps(Other) && Latency == Other.Latency;
133 }
134
135 bool operator!=(const SDep &Other) const {
136 return !operator==(Other);
137 }
138
139 /// Returns the latency value for this edge, which roughly means the
140 /// minimum number of cycles that must elapse between the predecessor and
141 /// the successor, given that they have this edge between them.
142 unsigned getLatency() const {
143 return Latency;
144 }
145
146 /// Sets the latency for this edge.
147 void setLatency(unsigned Lat) {
148 Latency = Lat;
149 }
150
151 //// Returns the SUnit to which this edge points.
152 SUnit *getSUnit() const;
153
154 //// Assigns the SUnit to which this edge points.
155 void setSUnit(SUnit *SU);
156
157 /// Returns an enum value representing the kind of the dependence.
158 Kind getKind() const;
159
160 /// Shorthand for getKind() != SDep::Data.
161 bool isCtrl() const {
162 return getKind() != Data;
163 }
164
165 /// Tests if this is an Order dependence between two memory accesses
166 /// where both sides of the dependence access memory in non-volatile and
167 /// fully modeled ways.
168 bool isNormalMemory() const {
169 return getKind() == Order && (Contents.OrdKind == MayAliasMem
170 || Contents.OrdKind == MustAliasMem);
171 }
172
173 /// Tests if this is an Order dependence that is marked as a barrier.
174 bool isBarrier() const {
175 return getKind() == Order && Contents.OrdKind == Barrier;
176 }
177
178 /// Tests if this is could be any kind of memory dependence.
180 return (isNormalMemory() || isBarrier());
181 }
182
183 /// Tests if this is an Order dependence that is marked as
184 /// "must alias", meaning that the SUnits at either end of the edge have a
185 /// memory dependence on a known memory location.
186 bool isMustAlias() const {
187 return getKind() == Order && Contents.OrdKind == MustAliasMem;
188 }
189
190 /// Tests if this a weak dependence. Weak dependencies are considered DAG
191 /// edges for height computation and other heuristics, but do not force
192 /// ordering. Breaking a weak edge may require the scheduler to compensate,
193 /// for example by inserting a copy.
194 bool isWeak() const {
195 return getKind() == Order && Contents.OrdKind >= Weak;
196 }
197
198 /// Tests if this is an Order dependence that is marked as
199 /// "artificial", meaning it isn't necessary for correctness.
200 bool isArtificial() const {
201 return getKind() == Order && Contents.OrdKind == Artificial;
202 }
203
204 /// Tests if this is an Order dependence that is marked as "cluster",
205 /// meaning it is artificial and wants to be adjacent.
206 bool isCluster() const {
207 return getKind() == Order && Contents.OrdKind == Cluster;
208 }
209
210 /// Tests if this is a Data dependence that is associated with a register.
211 bool isAssignedRegDep() const {
212 return getKind() == Data && Contents.Reg != 0;
213 }
214
215 /// Returns the register associated with this edge. This is only valid on
216 /// Data, Anti, and Output edges. On Data edges, this value may be zero,
217 /// meaning there is no associated register.
218 unsigned getReg() const {
219 assert((getKind() == Data || getKind() == Anti || getKind() == Output) &&
220 "getReg called on non-register dependence edge!");
221 return Contents.Reg;
222 }
223
224 /// Assigns the associated register for this edge. This is only valid on
225 /// Data, Anti, and Output edges. On Anti and Output edges, this value must
226 /// not be zero. On Data edges, the value may be zero, which would mean that
227 /// no specific register is associated with this edge.
228 void setReg(unsigned Reg) {
229 assert((getKind() == Data || getKind() == Anti || getKind() == Output) &&
230 "setReg called on non-register dependence edge!");
231 assert((getKind() != Anti || Reg != 0) &&
232 "SDep::Anti edge cannot use the zero register!");
233 assert((getKind() != Output || Reg != 0) &&
234 "SDep::Output edge cannot use the zero register!");
235 Contents.Reg = Reg;
236 }
237
238 void dump(const TargetRegisterInfo *TRI = nullptr) const;
239 };
240
241 /// Scheduling unit. This is a node in the scheduling DAG.
242 class SUnit {
243 private:
244 enum : unsigned { BoundaryID = ~0u };
245
246 SDNode *Node = nullptr; ///< Representative node.
247 MachineInstr *Instr = nullptr; ///< Alternatively, a MachineInstr.
248
249 public:
250 SUnit *OrigNode = nullptr; ///< If not this, the node from which this node
251 /// was cloned. (SD scheduling only)
252
254 nullptr; ///< nullptr or resolved SchedClass.
255
256 SmallVector<SDep, 4> Preds; ///< All sunit predecessors.
257 SmallVector<SDep, 4> Succs; ///< All sunit successors.
258
263
264 unsigned NodeNum = BoundaryID; ///< Entry # of node in the node vector.
265 unsigned NodeQueueId = 0; ///< Queue id of node.
266 unsigned NumPreds = 0; ///< # of SDep::Data preds.
267 unsigned NumSuccs = 0; ///< # of SDep::Data sucss.
268 unsigned NumPredsLeft = 0; ///< # of preds not scheduled.
269 unsigned NumSuccsLeft = 0; ///< # of succs not scheduled.
270 unsigned WeakPredsLeft = 0; ///< # of weak preds not scheduled.
271 unsigned WeakSuccsLeft = 0; ///< # of weak succs not scheduled.
272 unsigned short NumRegDefsLeft = 0; ///< # of reg defs with no scheduled use.
273 unsigned short Latency = 0; ///< Node latency.
274 bool isVRegCycle : 1; ///< May use and def the same vreg.
275 bool isCall : 1; ///< Is a function call.
276 bool isCallOp : 1; ///< Is a function call operand.
277 bool isTwoAddress : 1; ///< Is a two-address instruction.
278 bool isCommutable : 1; ///< Is a commutable instruction.
279 bool hasPhysRegUses : 1; ///< Has physreg uses.
280 bool hasPhysRegDefs : 1; ///< Has physreg defs that are being used.
281 bool hasPhysRegClobbers : 1; ///< Has any physreg defs, used or not.
282 bool isPending : 1; ///< True once pending.
283 bool isAvailable : 1; ///< True once available.
284 bool isScheduled : 1; ///< True once scheduled.
285 bool isScheduleHigh : 1; ///< True if preferable to schedule high.
286 bool isScheduleLow : 1; ///< True if preferable to schedule low.
287 bool isCloned : 1; ///< True if this node has been cloned.
288 bool isUnbuffered : 1; ///< Uses an unbuffered resource.
289 bool hasReservedResource : 1; ///< Uses a reserved resource.
290 Sched::Preference SchedulingPref = Sched::None; ///< Scheduling preference.
291
292 private:
293 bool isDepthCurrent : 1; ///< True if Depth is current.
294 bool isHeightCurrent : 1; ///< True if Height is current.
295 unsigned Depth = 0; ///< Node depth.
296 unsigned Height = 0; ///< Node height.
297
298 public:
299 unsigned TopReadyCycle = 0; ///< Cycle relative to start when node is ready.
300 unsigned BotReadyCycle = 0; ///< Cycle relative to end when node is ready.
301
303 nullptr; ///< Is a special copy node if != nullptr.
305
306 /// Constructs an SUnit for pre-regalloc scheduling to represent an
307 /// SDNode and any nodes flagged to it.
308 SUnit(SDNode *node, unsigned nodenum)
309 : Node(node), NodeNum(nodenum), isVRegCycle(false), isCall(false),
315 isHeightCurrent(false) {}
316
317 /// Constructs an SUnit for post-regalloc scheduling to represent a
318 /// MachineInstr.
319 SUnit(MachineInstr *instr, unsigned nodenum)
320 : Instr(instr), NodeNum(nodenum), isVRegCycle(false), isCall(false),
326 isHeightCurrent(false) {}
327
328 /// Constructs a placeholder SUnit.
335 isDepthCurrent(false), isHeightCurrent(false) {}
336
337 /// Boundary nodes are placeholders for the boundary of the
338 /// scheduling region.
339 ///
340 /// BoundaryNodes can have DAG edges, including Data edges, but they do not
341 /// correspond to schedulable entities (e.g. instructions) and do not have a
342 /// valid ID. Consequently, always check for boundary nodes before accessing
343 /// an associative data structure keyed on node ID.
344 bool isBoundaryNode() const { return NodeNum == BoundaryID; }
345
346 /// Assigns the representative SDNode for this SUnit. This may be used
347 /// during pre-regalloc scheduling.
348 void setNode(SDNode *N) {
349 assert(!Instr && "Setting SDNode of SUnit with MachineInstr!");
350 Node = N;
351 }
352
353 /// Returns the representative SDNode for this SUnit. This may be used
354 /// during pre-regalloc scheduling.
355 SDNode *getNode() const {
356 assert(!Instr && "Reading SDNode of SUnit with MachineInstr!");
357 return Node;
358 }
359
360 /// Returns true if this SUnit refers to a machine instruction as
361 /// opposed to an SDNode.
362 bool isInstr() const { return Instr; }
363
364 /// Assigns the instruction for the SUnit. This may be used during
365 /// post-regalloc scheduling.
367 assert(!Node && "Setting MachineInstr of SUnit with SDNode!");
368 Instr = MI;
369 }
370
371 /// Returns the representative MachineInstr for this SUnit. This may be used
372 /// during post-regalloc scheduling.
374 assert(!Node && "Reading MachineInstr of SUnit with SDNode!");
375 return Instr;
376 }
377
378 /// Adds the specified edge as a pred of the current node if not already.
379 /// It also adds the current node as a successor of the specified node.
380 bool addPred(const SDep &D, bool Required = true);
381
382 /// Adds a barrier edge to SU by calling addPred(), with latency 0
383 /// generally or latency 1 for a store followed by a load.
385 SDep Dep(SU, SDep::Barrier);
386 unsigned TrueMemOrderLatency =
387 ((SU->getInstr()->mayStore() && this->getInstr()->mayLoad()) ? 1 : 0);
388 Dep.setLatency(TrueMemOrderLatency);
389 return addPred(Dep);
390 }
391
392 /// Removes the specified edge as a pred of the current node if it exists.
393 /// It also removes the current node as a successor of the specified node.
394 void removePred(const SDep &D);
395
396 /// Returns the depth of this node, which is the length of the maximum path
397 /// up to any node which has no predecessors.
398 unsigned getDepth() const {
399 if (!isDepthCurrent)
400 const_cast<SUnit *>(this)->ComputeDepth();
401 return Depth;
402 }
403
404 /// Returns the height of this node, which is the length of the
405 /// maximum path down to any node which has no successors.
406 unsigned getHeight() const {
407 if (!isHeightCurrent)
408 const_cast<SUnit *>(this)->ComputeHeight();
409 return Height;
410 }
411
412 /// If NewDepth is greater than this node's depth value, sets it to
413 /// be the new depth value. This also recursively marks successor nodes
414 /// dirty.
415 void setDepthToAtLeast(unsigned NewDepth);
416
417 /// If NewHeight is greater than this node's height value, set it to be
418 /// the new height value. This also recursively marks predecessor nodes
419 /// dirty.
420 void setHeightToAtLeast(unsigned NewHeight);
421
422 /// Sets a flag in this node to indicate that its stored Depth value
423 /// will require recomputation the next time getDepth() is called.
424 void setDepthDirty();
425
426 /// Sets a flag in this node to indicate that its stored Height value
427 /// will require recomputation the next time getHeight() is called.
428 void setHeightDirty();
429
430 /// Tests if node N is a predecessor of this node.
431 bool isPred(const SUnit *N) const {
432 for (const SDep &Pred : Preds)
433 if (Pred.getSUnit() == N)
434 return true;
435 return false;
436 }
437
438 /// Tests if node N is a successor of this node.
439 bool isSucc(const SUnit *N) const {
440 for (const SDep &Succ : Succs)
441 if (Succ.getSUnit() == N)
442 return true;
443 return false;
444 }
445
446 bool isTopReady() const {
447 return NumPredsLeft == 0;
448 }
449 bool isBottomReady() const {
450 return NumSuccsLeft == 0;
451 }
452
453 /// Orders this node's predecessor edges such that the critical path
454 /// edge occurs first.
455 void biasCriticalPath();
456
457 void dumpAttributes() const;
458
459 private:
460 void ComputeDepth();
461 void ComputeHeight();
462 };
463
464 /// Returns true if the specified SDep is equivalent except for latency.
465 inline bool SDep::overlaps(const SDep &Other) const {
466 if (Dep != Other.Dep)
467 return false;
468 switch (Dep.getInt()) {
469 case Data:
470 case Anti:
471 case Output:
472 return Contents.Reg == Other.Contents.Reg;
473 case Order:
474 return Contents.OrdKind == Other.Contents.OrdKind;
475 }
476 llvm_unreachable("Invalid dependency kind!");
477 }
478
479 //// Returns the SUnit to which this edge points.
480 inline SUnit *SDep::getSUnit() const { return Dep.getPointer(); }
481
482 //// Assigns the SUnit to which this edge points.
483 inline void SDep::setSUnit(SUnit *SU) { Dep.setPointer(SU); }
484
485 /// Returns an enum value representing the kind of the dependence.
486 inline SDep::Kind SDep::getKind() const { return Dep.getInt(); }
487
488 //===--------------------------------------------------------------------===//
489
490 /// This interface is used to plug different priorities computation
491 /// algorithms into the list scheduler. It implements the interface of a
492 /// standard priority queue, where nodes are inserted in arbitrary order and
493 /// returned in priority order. The computation of the priority and the
494 /// representation of the queue are totally up to the implementation to
495 /// decide.
497 virtual void anchor();
498
499 unsigned CurCycle = 0;
500 bool HasReadyFilter;
501
502 public:
503 SchedulingPriorityQueue(bool rf = false) : HasReadyFilter(rf) {}
504
505 virtual ~SchedulingPriorityQueue() = default;
506
507 virtual bool isBottomUp() const = 0;
508
509 virtual void initNodes(std::vector<SUnit> &SUnits) = 0;
510 virtual void addNode(const SUnit *SU) = 0;
511 virtual void updateNode(const SUnit *SU) = 0;
512 virtual void releaseState() = 0;
513
514 virtual bool empty() const = 0;
515
516 bool hasReadyFilter() const { return HasReadyFilter; }
517
518 virtual bool tracksRegPressure() const { return false; }
519
520 virtual bool isReady(SUnit *) const {
521 assert(!HasReadyFilter && "The ready filter must override isReady()");
522 return true;
523 }
524
525 virtual void push(SUnit *U) = 0;
526
527 void push_all(const std::vector<SUnit *> &Nodes) {
528 for (SUnit *SU : Nodes)
529 push(SU);
530 }
531
532 virtual SUnit *pop() = 0;
533
534 virtual void remove(SUnit *SU) = 0;
535
536 virtual void dump(ScheduleDAG *) const {}
537
538 /// As each node is scheduled, this method is invoked. This allows the
539 /// priority function to adjust the priority of related unscheduled nodes,
540 /// for example.
541 virtual void scheduledNode(SUnit *) {}
542
543 virtual void unscheduledNode(SUnit *) {}
544
545 void setCurCycle(unsigned Cycle) {
546 CurCycle = Cycle;
547 }
548
549 unsigned getCurCycle() const {
550 return CurCycle;
551 }
552 };
553
555 public:
556 const LLVMTargetMachine &TM; ///< Target processor
557 const TargetInstrInfo *TII; ///< Target instruction information
558 const TargetRegisterInfo *TRI; ///< Target processor register info
559 MachineFunction &MF; ///< Machine function
560 MachineRegisterInfo &MRI; ///< Virtual/real register map
561 std::vector<SUnit> SUnits; ///< The scheduling units.
562 SUnit EntrySU; ///< Special node for the region entry.
563 SUnit ExitSU; ///< Special node for the region exit.
564
565#ifdef NDEBUG
566 static const bool StressSched = false;
567#else
569#endif
570
571 // This class is designed to be passed by reference only. Copy constructor
572 // is declared as deleted here to make the derived classes have deleted
573 // implicit-declared copy constructor, which suppresses the warnings from
574 // static analyzer when the derived classes own resources that are freed in
575 // their destructors, but don't have user-written copy constructors (rule
576 // of three).
577 ScheduleDAG(const ScheduleDAG &) = delete;
579
580 explicit ScheduleDAG(MachineFunction &mf);
581
582 virtual ~ScheduleDAG();
583
584 /// Clears the DAG state (between regions).
585 void clearDAG();
586
587 /// Returns the MCInstrDesc of this SUnit.
588 /// Returns NULL for SDNodes without a machine opcode.
589 const MCInstrDesc *getInstrDesc(const SUnit *SU) const {
590 if (SU->isInstr()) return &SU->getInstr()->getDesc();
591 return getNodeDesc(SU->getNode());
592 }
593
594 /// Pops up a GraphViz/gv window with the ScheduleDAG rendered using 'dot'.
595 virtual void viewGraph(const Twine &Name, const Twine &Title);
596 virtual void viewGraph();
597
598 virtual void dumpNode(const SUnit &SU) const = 0;
599 virtual void dump() const = 0;
600 void dumpNodeName(const SUnit &SU) const;
601
602 /// Returns a label for an SUnit node in a visualization of the ScheduleDAG.
603 virtual std::string getGraphNodeLabel(const SUnit *SU) const = 0;
604
605 /// Returns a label for the region of code covered by the DAG.
606 virtual std::string getDAGName() const = 0;
607
608 /// Adds custom features for a visualization of the ScheduleDAG.
610
611#ifndef NDEBUG
612 /// Verifies that all SUnits were scheduled and that their state is
613 /// consistent. Returns the number of scheduled SUnits.
614 unsigned VerifyScheduledDAG(bool isBottomUp);
615#endif
616
617 protected:
618 void dumpNodeAll(const SUnit &SU) const;
619
620 private:
621 /// Returns the MCInstrDesc of this SDNode or NULL.
622 const MCInstrDesc *getNodeDesc(const SDNode *Node) const;
623 };
624
626 SUnit *Node;
627 unsigned Operand;
628
629 SUnitIterator(SUnit *N, unsigned Op) : Node(N), Operand(Op) {}
630
631 public:
632 using iterator_category = std::forward_iterator_tag;
634 using difference_type = std::ptrdiff_t;
637
638 bool operator==(const SUnitIterator& x) const {
639 return Operand == x.Operand;
640 }
641 bool operator!=(const SUnitIterator& x) const { return !operator==(x); }
642
644 return Node->Preds[Operand].getSUnit();
645 }
646 pointer operator->() const { return operator*(); }
647
648 SUnitIterator& operator++() { // Preincrement
649 ++Operand;
650 return *this;
651 }
652 SUnitIterator operator++(int) { // Postincrement
653 SUnitIterator tmp = *this; ++*this; return tmp;
654 }
655
656 static SUnitIterator begin(SUnit *N) { return SUnitIterator(N, 0); }
658 return SUnitIterator(N, (unsigned)N->Preds.size());
659 }
660
661 unsigned getOperand() const { return Operand; }
662 const SUnit *getNode() const { return Node; }
663
664 /// Tests if this is not an SDep::Data dependence.
665 bool isCtrlDep() const {
666 return getSDep().isCtrl();
667 }
668 bool isArtificialDep() const {
669 return getSDep().isArtificial();
670 }
671 const SDep &getSDep() const {
672 return Node->Preds[Operand];
673 }
674 };
675
676 template <> struct GraphTraits<SUnit*> {
677 typedef SUnit *NodeRef;
679 static NodeRef getEntryNode(SUnit *N) { return N; }
681 return SUnitIterator::begin(N);
682 }
684 return SUnitIterator::end(N);
685 }
686 };
687
688 template <> struct GraphTraits<ScheduleDAG*> : public GraphTraits<SUnit*> {
691 return nodes_iterator(G->SUnits.begin());
692 }
694 return nodes_iterator(G->SUnits.end());
695 }
696 };
697
698 /// This class can compute a topological ordering for SUnits and provides
699 /// methods for dynamically updating the ordering as new edges are added.
700 ///
701 /// This allows a very fast implementation of IsReachable, for example.
703 /// A reference to the ScheduleDAG's SUnits.
704 std::vector<SUnit> &SUnits;
705 SUnit *ExitSU;
706
707 // Have any new nodes been added?
708 bool Dirty = false;
709
710 // Outstanding added edges, that have not been applied to the ordering.
712
713 /// Maps topological index to the node number.
714 std::vector<int> Index2Node;
715 /// Maps the node number to its topological index.
716 std::vector<int> Node2Index;
717 /// a set of nodes visited during a DFS traversal.
718 BitVector Visited;
719
720 /// Makes a DFS traversal and mark all nodes affected by the edge insertion.
721 /// These nodes will later get new topological indexes by means of the Shift
722 /// method.
723 void DFS(const SUnit *SU, int UpperBound, bool& HasLoop);
724
725 /// Reassigns topological indexes for the nodes in the DAG to
726 /// preserve the topological ordering.
727 void Shift(BitVector& Visited, int LowerBound, int UpperBound);
728
729 /// Assigns the topological index to the node n.
730 void Allocate(int n, int index);
731
732 /// Fix the ordering, by either recomputing from scratch or by applying
733 /// any outstanding updates. Uses a heuristic to estimate what will be
734 /// cheaper.
735 void FixOrder();
736
737 public:
738 ScheduleDAGTopologicalSort(std::vector<SUnit> &SUnits, SUnit *ExitSU);
739
740 /// Add a SUnit without predecessors to the end of the topological order. It
741 /// also must be the first new node added to the DAG.
742 void AddSUnitWithoutPredecessors(const SUnit *SU);
743
744 /// Creates the initial topological ordering from the DAG to be scheduled.
746
747 /// Returns an array of SUs that are both in the successor
748 /// subtree of StartSU and in the predecessor subtree of TargetSU.
749 /// StartSU and TargetSU are not in the array.
750 /// Success is false if TargetSU is not in the successor subtree of
751 /// StartSU, else it is true.
752 std::vector<int> GetSubGraph(const SUnit &StartSU, const SUnit &TargetSU,
753 bool &Success);
754
755 /// Checks if \p SU is reachable from \p TargetSU.
756 bool IsReachable(const SUnit *SU, const SUnit *TargetSU);
757
758 /// Returns true if addPred(TargetSU, SU) creates a cycle.
759 bool WillCreateCycle(SUnit *TargetSU, SUnit *SU);
760
761 /// Updates the topological ordering to accommodate an edge to be
762 /// added from SUnit \p X to SUnit \p Y.
763 void AddPred(SUnit *Y, SUnit *X);
764
765 /// Queues an update to the topological ordering to accommodate an edge to
766 /// be added from SUnit \p X to SUnit \p Y.
767 void AddPredQueued(SUnit *Y, SUnit *X);
768
769 /// Updates the topological ordering to accommodate an an edge to be
770 /// removed from the specified node \p N from the predecessors of the
771 /// current node \p M.
772 void RemovePred(SUnit *M, SUnit *N);
773
774 /// Mark the ordering as temporarily broken, after a new node has been
775 /// added.
776 void MarkDirty() { Dirty = true; }
777
778 typedef std::vector<int>::iterator iterator;
779 typedef std::vector<int>::const_iterator const_iterator;
780 iterator begin() { return Index2Node.begin(); }
781 const_iterator begin() const { return Index2Node.begin(); }
782 iterator end() { return Index2Node.end(); }
783 const_iterator end() const { return Index2Node.end(); }
784
785 typedef std::vector<int>::reverse_iterator reverse_iterator;
786 typedef std::vector<int>::const_reverse_iterator const_reverse_iterator;
787 reverse_iterator rbegin() { return Index2Node.rbegin(); }
788 const_reverse_iterator rbegin() const { return Index2Node.rbegin(); }
789 reverse_iterator rend() { return Index2Node.rend(); }
790 const_reverse_iterator rend() const { return Index2Node.rend(); }
791 };
792
793} // end namespace llvm
794
795#endif // LLVM_CODEGEN_SCHEDULEDAG_H
#define Success
This file implements the BitVector class.
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
std::string Name
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
IRTranslator LLVM IR MI
#define G(x, y, z)
Definition: MD5.cpp:56
unsigned const TargetRegisterInfo * TRI
static GCMetadataPrinterRegistry::Add< OcamlGCMetadataPrinter > Y("ocaml", "ocaml 3.10-compatible collector")
This file defines the PointerIntPair class.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the SmallVector class.
This file describes how to lower LLVM code to machine code.
A possibly irreducible generalization of a Loop.
This class describes a target machine that is implemented with the LLVM target-independent code gener...
Describe properties that are true of each instruction in the target description file.
Definition: MCInstrDesc.h:198
Representation of each machine instruction.
Definition: MachineInstr.h:68
bool mayLoad(QueryType Type=AnyInBundle) const
Return true if this instruction could possibly read memory.
const MCInstrDesc & getDesc() const
Returns the target instruction descriptor of this MachineInstr.
Definition: MachineInstr.h:513
bool mayStore(QueryType Type=AnyInBundle) const
Return true if this instruction could possibly modify memory.
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
PointerIntPair - This class implements a pair of a pointer and small integer.
Represents one node in the SelectionDAG.
Scheduling dependency.
Definition: ScheduleDAG.h:49
SUnit * getSUnit() const
Definition: ScheduleDAG.h:480
bool overlaps(const SDep &Other) const
Returns true if the specified SDep is equivalent except for latency.
Definition: ScheduleDAG.h:465
Kind getKind() const
Returns an enum value representing the kind of the dependence.
Definition: ScheduleDAG.h:486
Kind
These are the different kinds of scheduling dependencies.
Definition: ScheduleDAG.h:52
@ Output
A register output-dependence (aka WAW).
Definition: ScheduleDAG.h:55
@ Order
Any other ordering dependency.
Definition: ScheduleDAG.h:56
@ Anti
A register anti-dependence (aka WAR).
Definition: ScheduleDAG.h:54
@ Data
Regular data dependence (aka true-dependence).
Definition: ScheduleDAG.h:53
void setLatency(unsigned Lat)
Sets the latency for this edge.
Definition: ScheduleDAG.h:147
bool isWeak() const
Tests if this a weak dependence.
Definition: ScheduleDAG.h:194
@ Cluster
Weak DAG edge linking a chain of clustered instrs.
Definition: ScheduleDAG.h:74
@ Barrier
An unknown scheduling barrier.
Definition: ScheduleDAG.h:69
@ Artificial
Arbitrary strong DAG edge (no real dependence).
Definition: ScheduleDAG.h:72
@ MayAliasMem
Nonvolatile load/Store instructions that may alias.
Definition: ScheduleDAG.h:70
@ Weak
Arbitrary weak DAG edge.
Definition: ScheduleDAG.h:73
@ MustAliasMem
Nonvolatile load/Store instructions that must alias.
Definition: ScheduleDAG.h:71
unsigned OrdKind
Additional information about Order dependencies.
Definition: ScheduleDAG.h:90
unsigned getLatency() const
Returns the latency value for this edge, which roughly means the minimum number of cycles that must e...
Definition: ScheduleDAG.h:142
bool isAssignedRegDep() const
Tests if this is a Data dependence that is associated with a register.
Definition: ScheduleDAG.h:211
bool isNormalMemory() const
Tests if this is an Order dependence between two memory accesses where both sides of the dependence a...
Definition: ScheduleDAG.h:168
bool isArtificial() const
Tests if this is an Order dependence that is marked as "artificial", meaning it isn't necessary for c...
Definition: ScheduleDAG.h:200
bool operator==(const SDep &Other) const
Definition: ScheduleDAG.h:131
bool isCtrl() const
Shorthand for getKind() != SDep::Data.
Definition: ScheduleDAG.h:161
unsigned getReg() const
Returns the register associated with this edge.
Definition: ScheduleDAG.h:218
SDep(SUnit *S, OrderKind kind)
Definition: ScheduleDAG.h:123
SDep()
Constructs a null SDep.
Definition: ScheduleDAG.h:101
bool operator!=(const SDep &Other) const
Definition: ScheduleDAG.h:135
void setSUnit(SUnit *SU)
Definition: ScheduleDAG.h:483
unsigned Reg
For Data, Anti, and Output dependencies, the associated register.
Definition: ScheduleDAG.h:87
bool isCluster() const
Tests if this is an Order dependence that is marked as "cluster", meaning it is artificial and wants ...
Definition: ScheduleDAG.h:206
void dump(const TargetRegisterInfo *TRI=nullptr) const
Definition: ScheduleDAG.cpp:75
void setReg(unsigned Reg)
Assigns the associated register for this edge.
Definition: ScheduleDAG.h:228
bool isBarrier() const
Tests if this is an Order dependence that is marked as a barrier.
Definition: ScheduleDAG.h:174
bool isNormalMemoryOrBarrier() const
Tests if this is could be any kind of memory dependence.
Definition: ScheduleDAG.h:179
SDep(SUnit *S, Kind kind, unsigned Reg)
Constructs an SDep with the specified values.
Definition: ScheduleDAG.h:104
bool isMustAlias() const
Tests if this is an Order dependence that is marked as "must alias", meaning that the SUnits at eithe...
Definition: ScheduleDAG.h:186
const SUnit * getNode() const
Definition: ScheduleDAG.h:662
std::forward_iterator_tag iterator_category
Definition: ScheduleDAG.h:632
unsigned getOperand() const
Definition: ScheduleDAG.h:661
static SUnitIterator end(SUnit *N)
Definition: ScheduleDAG.h:657
pointer operator*() const
Definition: ScheduleDAG.h:643
SUnitIterator operator++(int)
Definition: ScheduleDAG.h:652
static SUnitIterator begin(SUnit *N)
Definition: ScheduleDAG.h:656
SUnitIterator & operator++()
Definition: ScheduleDAG.h:648
pointer operator->() const
Definition: ScheduleDAG.h:646
bool operator==(const SUnitIterator &x) const
Definition: ScheduleDAG.h:638
const SDep & getSDep() const
Definition: ScheduleDAG.h:671
bool operator!=(const SUnitIterator &x) const
Definition: ScheduleDAG.h:641
bool isArtificialDep() const
Definition: ScheduleDAG.h:668
bool isCtrlDep() const
Tests if this is not an SDep::Data dependence.
Definition: ScheduleDAG.h:665
std::ptrdiff_t difference_type
Definition: ScheduleDAG.h:634
Scheduling unit. This is a node in the scheduling DAG.
Definition: ScheduleDAG.h:242
bool isCloned
True if this node has been cloned.
Definition: ScheduleDAG.h:287
bool isCall
Is a function call.
Definition: ScheduleDAG.h:275
void setHeightToAtLeast(unsigned NewHeight)
If NewHeight is greater than this node's height value, set it to be the new height value.
bool addPredBarrier(SUnit *SU)
Adds a barrier edge to SU by calling addPred(), with latency 0 generally or latency 1 for a store fol...
Definition: ScheduleDAG.h:384
unsigned NumSuccs
Definition: ScheduleDAG.h:267
void setNode(SDNode *N)
Assigns the representative SDNode for this SUnit.
Definition: ScheduleDAG.h:348
unsigned NumPreds
Definition: ScheduleDAG.h:266
unsigned NodeQueueId
Queue id of node.
Definition: ScheduleDAG.h:265
bool isInstr() const
Returns true if this SUnit refers to a machine instruction as opposed to an SDNode.
Definition: ScheduleDAG.h:362
unsigned TopReadyCycle
Cycle relative to start when node is ready.
Definition: ScheduleDAG.h:299
SmallVectorImpl< SDep >::const_iterator const_succ_iterator
Definition: ScheduleDAG.h:262
const MCSchedClassDesc * SchedClass
nullptr or resolved SchedClass.
Definition: ScheduleDAG.h:253
unsigned NodeNum
Entry # of node in the node vector.
Definition: ScheduleDAG.h:264
unsigned NumSuccsLeft
Definition: ScheduleDAG.h:269
bool hasPhysRegClobbers
Has any physreg defs, used or not.
Definition: ScheduleDAG.h:281
void biasCriticalPath()
Orders this node's predecessor edges such that the critical path edge occurs first.
bool isUnbuffered
Uses an unbuffered resource.
Definition: ScheduleDAG.h:288
bool isCallOp
Is a function call operand.
Definition: ScheduleDAG.h:276
const TargetRegisterClass * CopyDstRC
Is a special copy node if != nullptr.
Definition: ScheduleDAG.h:302
SUnit(MachineInstr *instr, unsigned nodenum)
Constructs an SUnit for post-regalloc scheduling to represent a MachineInstr.
Definition: ScheduleDAG.h:319
SmallVectorImpl< SDep >::const_iterator const_pred_iterator
Definition: ScheduleDAG.h:261
unsigned getHeight() const
Returns the height of this node, which is the length of the maximum path down to any node which has n...
Definition: ScheduleDAG.h:406
void setInstr(MachineInstr *MI)
Assigns the instruction for the SUnit.
Definition: ScheduleDAG.h:366
void setHeightDirty()
Sets a flag in this node to indicate that its stored Height value will require recomputation the next...
bool isSucc(const SUnit *N) const
Tests if node N is a successor of this node.
Definition: ScheduleDAG.h:439
void removePred(const SDep &D)
Removes the specified edge as a pred of the current node if it exists.
bool isPred(const SUnit *N) const
Tests if node N is a predecessor of this node.
Definition: ScheduleDAG.h:431
unsigned short Latency
Node latency.
Definition: ScheduleDAG.h:273
SmallVectorImpl< SDep >::iterator pred_iterator
Definition: ScheduleDAG.h:259
bool isBoundaryNode() const
Boundary nodes are placeholders for the boundary of the scheduling region.
Definition: ScheduleDAG.h:344
unsigned short NumRegDefsLeft
Definition: ScheduleDAG.h:272
bool isScheduleHigh
True if preferable to schedule high.
Definition: ScheduleDAG.h:285
bool isPending
True once pending.
Definition: ScheduleDAG.h:282
unsigned getDepth() const
Returns the depth of this node, which is the length of the maximum path up to any node which has no p...
Definition: ScheduleDAG.h:398
bool isScheduled
True once scheduled.
Definition: ScheduleDAG.h:284
bool isAvailable
True once available.
Definition: ScheduleDAG.h:283
unsigned NumPredsLeft
Definition: ScheduleDAG.h:268
bool isScheduleLow
True if preferable to schedule low.
Definition: ScheduleDAG.h:286
bool hasPhysRegDefs
Has physreg defs that are being used.
Definition: ScheduleDAG.h:280
unsigned BotReadyCycle
Cycle relative to end when node is ready.
Definition: ScheduleDAG.h:300
void dumpAttributes() const
SmallVector< SDep, 4 > Succs
All sunit successors.
Definition: ScheduleDAG.h:257
Sched::Preference SchedulingPref
Scheduling preference.
Definition: ScheduleDAG.h:290
SUnit(SDNode *node, unsigned nodenum)
Constructs an SUnit for pre-regalloc scheduling to represent an SDNode and any nodes flagged to it.
Definition: ScheduleDAG.h:308
bool hasReservedResource
Uses a reserved resource.
Definition: ScheduleDAG.h:289
unsigned WeakPredsLeft
Definition: ScheduleDAG.h:270
const TargetRegisterClass * CopySrcRC
Definition: ScheduleDAG.h:304
bool isBottomReady() const
Definition: ScheduleDAG.h:449
SDNode * getNode() const
Returns the representative SDNode for this SUnit.
Definition: ScheduleDAG.h:355
bool isTwoAddress
Is a two-address instruction.
Definition: ScheduleDAG.h:277
bool isCommutable
Is a commutable instruction.
Definition: ScheduleDAG.h:278
bool isVRegCycle
May use and def the same vreg.
Definition: ScheduleDAG.h:274
SUnit()
Constructs a placeholder SUnit.
Definition: ScheduleDAG.h:329
bool hasPhysRegUses
Has physreg uses.
Definition: ScheduleDAG.h:279
void setDepthDirty()
Sets a flag in this node to indicate that its stored Depth value will require recomputation the next ...
bool isTopReady() const
Definition: ScheduleDAG.h:446
SmallVector< SDep, 4 > Preds
All sunit predecessors.
Definition: ScheduleDAG.h:256
unsigned WeakSuccsLeft
Definition: ScheduleDAG.h:271
SmallVectorImpl< SDep >::iterator succ_iterator
Definition: ScheduleDAG.h:260
void setDepthToAtLeast(unsigned NewDepth)
If NewDepth is greater than this node's depth value, sets it to be the new depth value.
SUnit * OrigNode
If not this, the node from which this node was cloned.
Definition: ScheduleDAG.h:250
bool addPred(const SDep &D, bool Required=true)
Adds the specified edge as a pred of the current node if not already.
MachineInstr * getInstr() const
Returns the representative MachineInstr for this SUnit.
Definition: ScheduleDAG.h:373
This class can compute a topological ordering for SUnits and provides methods for dynamically updatin...
Definition: ScheduleDAG.h:702
void RemovePred(SUnit *M, SUnit *N)
Updates the topological ordering to accommodate an an edge to be removed from the specified node N fr...
bool WillCreateCycle(SUnit *TargetSU, SUnit *SU)
Returns true if addPred(TargetSU, SU) creates a cycle.
void MarkDirty()
Mark the ordering as temporarily broken, after a new node has been added.
Definition: ScheduleDAG.h:776
void AddSUnitWithoutPredecessors(const SUnit *SU)
Add a SUnit without predecessors to the end of the topological order.
const_reverse_iterator rbegin() const
Definition: ScheduleDAG.h:788
std::vector< int >::reverse_iterator reverse_iterator
Definition: ScheduleDAG.h:785
std::vector< int > GetSubGraph(const SUnit &StartSU, const SUnit &TargetSU, bool &Success)
Returns an array of SUs that are both in the successor subtree of StartSU and in the predecessor subt...
const_iterator end() const
Definition: ScheduleDAG.h:783
void InitDAGTopologicalSorting()
Creates the initial topological ordering from the DAG to be scheduled.
void AddPred(SUnit *Y, SUnit *X)
Updates the topological ordering to accommodate an edge to be added from SUnit X to SUnit Y.
std::vector< int >::const_iterator const_iterator
Definition: ScheduleDAG.h:779
std::vector< int >::iterator iterator
Definition: ScheduleDAG.h:778
const_reverse_iterator rend() const
Definition: ScheduleDAG.h:790
const_iterator begin() const
Definition: ScheduleDAG.h:781
bool IsReachable(const SUnit *SU, const SUnit *TargetSU)
Checks if SU is reachable from TargetSU.
void AddPredQueued(SUnit *Y, SUnit *X)
Queues an update to the topological ordering to accommodate an edge to be added from SUnit X to SUnit...
std::vector< int >::const_reverse_iterator const_reverse_iterator
Definition: ScheduleDAG.h:786
const MCInstrDesc * getInstrDesc(const SUnit *SU) const
Returns the MCInstrDesc of this SUnit.
Definition: ScheduleDAG.h:589
const LLVMTargetMachine & TM
Target processor.
Definition: ScheduleDAG.h:556
MachineRegisterInfo & MRI
Virtual/real register map.
Definition: ScheduleDAG.h:560
void clearDAG()
Clears the DAG state (between regions).
Definition: ScheduleDAG.cpp:64
virtual std::string getGraphNodeLabel(const SUnit *SU) const =0
Returns a label for an SUnit node in a visualization of the ScheduleDAG.
const TargetInstrInfo * TII
Target instruction information.
Definition: ScheduleDAG.h:557
virtual std::string getDAGName() const =0
Returns a label for the region of code covered by the DAG.
std::vector< SUnit > SUnits
The scheduling units.
Definition: ScheduleDAG.h:561
virtual ~ScheduleDAG()
const TargetRegisterInfo * TRI
Target processor register info.
Definition: ScheduleDAG.h:558
SUnit EntrySU
Special node for the region entry.
Definition: ScheduleDAG.h:562
MachineFunction & MF
Machine function.
Definition: ScheduleDAG.h:559
ScheduleDAG & operator=(const ScheduleDAG &)=delete
virtual void dump() const =0
virtual void viewGraph()
Out-of-line implementation with no arguments is handy for gdb.
ScheduleDAG(const ScheduleDAG &)=delete
void dumpNodeAll(const SUnit &SU) const
unsigned VerifyScheduledDAG(bool isBottomUp)
Verifies that all SUnits were scheduled and that their state is consistent.
virtual void addCustomGraphFeatures(GraphWriter< ScheduleDAG * > &) const
Adds custom features for a visualization of the ScheduleDAG.
Definition: ScheduleDAG.h:609
virtual void dumpNode(const SUnit &SU) const =0
void dumpNodeName(const SUnit &SU) const
SUnit ExitSU
Special node for the region exit.
Definition: ScheduleDAG.h:563
This interface is used to plug different priorities computation algorithms into the list scheduler.
Definition: ScheduleDAG.h:496
void setCurCycle(unsigned Cycle)
Definition: ScheduleDAG.h:545
SchedulingPriorityQueue(bool rf=false)
Definition: ScheduleDAG.h:503
virtual void remove(SUnit *SU)=0
virtual bool isBottomUp() const =0
virtual void releaseState()=0
virtual SUnit * pop()=0
virtual void scheduledNode(SUnit *)
As each node is scheduled, this method is invoked.
Definition: ScheduleDAG.h:541
virtual bool isReady(SUnit *) const
Definition: ScheduleDAG.h:520
virtual bool tracksRegPressure() const
Definition: ScheduleDAG.h:518
virtual void dump(ScheduleDAG *) const
Definition: ScheduleDAG.h:536
virtual void initNodes(std::vector< SUnit > &SUnits)=0
virtual ~SchedulingPriorityQueue()=default
virtual bool empty() const =0
virtual void unscheduledNode(SUnit *)
Definition: ScheduleDAG.h:543
void push_all(const std::vector< SUnit * > &Nodes)
Definition: ScheduleDAG.h:527
virtual void addNode(const SUnit *SU)=0
unsigned getCurCycle() const
Definition: ScheduleDAG.h:549
virtual void updateNode(const SUnit *SU)=0
virtual void push(SUnit *U)=0
typename SuperClass::const_iterator const_iterator
Definition: SmallVector.h:582
typename SuperClass::iterator iterator
Definition: SmallVector.h:581
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1200
TargetInstrInfo - Interface to description of machine instruction set.
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Definition: Twine.h:81
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
CycleInfo::CycleT Cycle
Definition: CycleAnalysis.h:28
#define N
SUnitIterator ChildIteratorType
Definition: ScheduleDAG.h:678
static ChildIteratorType child_begin(NodeRef N)
Definition: ScheduleDAG.h:680
static NodeRef getEntryNode(SUnit *N)
Definition: ScheduleDAG.h:679
static ChildIteratorType child_end(NodeRef N)
Definition: ScheduleDAG.h:683
static nodes_iterator nodes_begin(ScheduleDAG *G)
Definition: ScheduleDAG.h:690
static nodes_iterator nodes_end(ScheduleDAG *G)
Definition: ScheduleDAG.h:693
pointer_iterator< std::vector< SUnit >::iterator > nodes_iterator
Definition: ScheduleDAG.h:689
Summarize the scheduling resources required for an instruction of a particular scheduling class.
Definition: MCSchedule.h:114