1 //===- llvm/CodeGen/ScheduleDAG.h - Common Base Class -----------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 /// \file Implements the ScheduleDAG class, which is used as the common base
11 /// class for instruction schedulers. This encapsulates the scheduling DAG,
12 /// which is shared between SelectionDAG and MachineInstr scheduling.
14 //===----------------------------------------------------------------------===//
16 #ifndef LLVM_CODEGEN_SCHEDULEDAG_H
17 #define LLVM_CODEGEN_SCHEDULEDAG_H
19 #include "llvm/ADT/BitVector.h"
20 #include "llvm/ADT/GraphTraits.h"
21 #include "llvm/ADT/iterator.h"
22 #include "llvm/ADT/PointerIntPair.h"
23 #include "llvm/ADT/SmallVector.h"
24 #include "llvm/CodeGen/MachineInstr.h"
25 #include "llvm/Support/ErrorHandling.h"
26 #include "llvm/Target/TargetLowering.h"
35 template<class Graph> class GraphWriter;
36 class MachineFunction;
37 class MachineRegisterInfo;
39 struct MCSchedClassDesc;
43 class TargetInstrInfo;
45 class TargetRegisterClass;
46 class TargetRegisterInfo;
48 /// Scheduling dependency. This represents one direction of an edge in the
52 /// These are the different kinds of scheduling dependencies.
54 Data, ///< Regular data dependence (aka true-dependence).
55 Anti, ///< A register anti-dependence (aka WAR).
56 Output, ///< A register output-dependence (aka WAW).
57 Order ///< Any other ordering dependency.
60 // Strong dependencies must be respected by the scheduler. Artificial
61 // dependencies may be removed only if they are redundant with another
64 // Weak dependencies may be violated by the scheduling strategy, but only if
65 // the strategy can prove it is correct to do so.
67 // Strong OrderKinds must occur before "Weak".
68 // Weak OrderKinds must occur after "Weak".
70 Barrier, ///< An unknown scheduling barrier.
71 MayAliasMem, ///< Nonvolatile load/Store instructions that may alias.
72 MustAliasMem, ///< Nonvolatile load/Store instructions that must alias.
73 Artificial, ///< Arbitrary strong DAG edge (no real dependence).
74 Weak, ///< Arbitrary weak DAG edge.
75 Cluster ///< Weak DAG edge linking a chain of clustered instrs.
79 /// \brief A pointer to the depending/depended-on SUnit, and an enum
80 /// indicating the kind of the dependency.
81 PointerIntPair<SUnit *, 2, Kind> Dep;
83 /// A union discriminated by the dependence kind.
85 /// For Data, Anti, and Output dependencies, the associated register. For
86 /// Data dependencies that don't currently have a register/ assigned, this
90 /// Additional information about Order dependencies.
91 unsigned OrdKind; // enum OrderKind
94 /// The time associated with this edge. Often this is just the value of the
95 /// Latency field of the predecessor, however advanced models may provide
96 /// additional information about specific edges.
100 /// Constructs a null SDep. This is only for use by container classes which
101 /// require default constructors. SUnits may not/ have null SDep edges.
102 SDep() : Dep(nullptr, Data) {}
104 /// Constructs an SDep with the specified values.
105 SDep(SUnit *S, Kind kind, unsigned Reg)
106 : Dep(S, kind), Contents() {
109 llvm_unreachable("Reg given for non-register dependence!");
113 "SDep::Anti and SDep::Output must use a non-zero Reg!");
124 SDep(SUnit *S, OrderKind kind)
125 : Dep(S, Order), Contents(), Latency(0) {
126 Contents.OrdKind = kind;
129 /// Returns true if the specified SDep is equivalent except for latency.
130 bool overlaps(const SDep &Other) const;
132 bool operator==(const SDep &Other) const {
133 return overlaps(Other) && Latency == Other.Latency;
136 bool operator!=(const SDep &Other) const {
137 return !operator==(Other);
140 /// \brief Returns the latency value for this edge, which roughly means the
141 /// minimum number of cycles that must elapse between the predecessor and
142 /// the successor, given that they have this edge between them.
143 unsigned getLatency() const {
147 /// Sets the latency for this edge.
148 void setLatency(unsigned Lat) {
152 //// Returns the SUnit to which this edge points.
153 SUnit *getSUnit() const;
155 //// Assigns the SUnit to which this edge points.
156 void setSUnit(SUnit *SU);
158 /// Returns an enum value representing the kind of the dependence.
159 Kind getKind() const;
161 /// Shorthand for getKind() != SDep::Data.
162 bool isCtrl() const {
163 return getKind() != Data;
166 /// \brief Tests if this is an Order dependence between two memory accesses
167 /// where both sides of the dependence access memory in non-volatile and
168 /// fully modeled ways.
169 bool isNormalMemory() const {
170 return getKind() == Order && (Contents.OrdKind == MayAliasMem
171 || Contents.OrdKind == MustAliasMem);
174 /// Tests if this is an Order dependence that is marked as a barrier.
175 bool isBarrier() const {
176 return getKind() == Order && Contents.OrdKind == Barrier;
179 /// Tests if this is could be any kind of memory dependence.
180 bool isNormalMemoryOrBarrier() const {
181 return (isNormalMemory() || isBarrier());
184 /// \brief Tests if this is an Order dependence that is marked as
185 /// "must alias", meaning that the SUnits at either end of the edge have a
186 /// memory dependence on a known memory location.
187 bool isMustAlias() const {
188 return getKind() == Order && Contents.OrdKind == MustAliasMem;
191 /// Tests if this a weak dependence. Weak dependencies are considered DAG
192 /// edges for height computation and other heuristics, but do not force
193 /// ordering. Breaking a weak edge may require the scheduler to compensate,
194 /// for example by inserting a copy.
195 bool isWeak() const {
196 return getKind() == Order && Contents.OrdKind >= Weak;
199 /// \brief Tests if this is an Order dependence that is marked as
200 /// "artificial", meaning it isn't necessary for correctness.
201 bool isArtificial() const {
202 return getKind() == Order && Contents.OrdKind == Artificial;
205 /// \brief Tests if this is an Order dependence that is marked as "cluster",
206 /// meaning it is artificial and wants to be adjacent.
207 bool isCluster() const {
208 return getKind() == Order && Contents.OrdKind == Cluster;
211 /// Tests if this is a Data dependence that is associated with a register.
212 bool isAssignedRegDep() const {
213 return getKind() == Data && Contents.Reg != 0;
216 /// Returns the register associated with this edge. This is only valid on
217 /// Data, Anti, and Output edges. On Data edges, this value may be zero,
218 /// meaning there is no associated register.
219 unsigned getReg() const {
220 assert((getKind() == Data || getKind() == Anti || getKind() == Output) &&
221 "getReg called on non-register dependence edge!");
225 /// Assigns the associated register for this edge. This is only valid on
226 /// Data, Anti, and Output edges. On Anti and Output edges, this value must
227 /// not be zero. On Data edges, the value may be zero, which would mean that
228 /// no specific register is associated with this edge.
229 void setReg(unsigned Reg) {
230 assert((getKind() == Data || getKind() == Anti || getKind() == Output) &&
231 "setReg called on non-register dependence edge!");
232 assert((getKind() != Anti || Reg != 0) &&
233 "SDep::Anti edge cannot use the zero register!");
234 assert((getKind() != Output || Reg != 0) &&
235 "SDep::Output edge cannot use the zero register!");
241 struct isPodLike<SDep> { static const bool value = true; };
243 /// Scheduling unit. This is a node in the scheduling DAG.
246 enum : unsigned { BoundaryID = ~0u };
248 SDNode *Node = nullptr; ///< Representative node.
249 MachineInstr *Instr = nullptr; ///< Alternatively, a MachineInstr.
252 SUnit *OrigNode = nullptr; ///< If not this, the node from which this node
253 /// was cloned. (SD scheduling only)
255 const MCSchedClassDesc *SchedClass =
256 nullptr; ///< nullptr or resolved SchedClass.
258 SmallVector<SDep, 4> Preds; ///< All sunit predecessors.
259 SmallVector<SDep, 4> Succs; ///< All sunit successors.
261 typedef SmallVectorImpl<SDep>::iterator pred_iterator;
262 typedef SmallVectorImpl<SDep>::iterator succ_iterator;
263 typedef SmallVectorImpl<SDep>::const_iterator const_pred_iterator;
264 typedef SmallVectorImpl<SDep>::const_iterator const_succ_iterator;
266 unsigned NodeNum = BoundaryID; ///< Entry # of node in the node vector.
267 unsigned NodeQueueId = 0; ///< Queue id of node.
268 unsigned NumPreds = 0; ///< # of SDep::Data preds.
269 unsigned NumSuccs = 0; ///< # of SDep::Data sucss.
270 unsigned NumPredsLeft = 0; ///< # of preds not scheduled.
271 unsigned NumSuccsLeft = 0; ///< # of succs not scheduled.
272 unsigned WeakPredsLeft = 0; ///< # of weak preds not scheduled.
273 unsigned WeakSuccsLeft = 0; ///< # of weak succs not scheduled.
274 unsigned short NumRegDefsLeft = 0; ///< # of reg defs with no scheduled use.
275 unsigned short Latency = 0; ///< Node latency.
276 bool isVRegCycle : 1; ///< May use and def the same vreg.
277 bool isCall : 1; ///< Is a function call.
278 bool isCallOp : 1; ///< Is a function call operand.
279 bool isTwoAddress : 1; ///< Is a two-address instruction.
280 bool isCommutable : 1; ///< Is a commutable instruction.
281 bool hasPhysRegUses : 1; ///< Has physreg uses.
282 bool hasPhysRegDefs : 1; ///< Has physreg defs that are being used.
283 bool hasPhysRegClobbers : 1; ///< Has any physreg defs, used or not.
284 bool isPending : 1; ///< True once pending.
285 bool isAvailable : 1; ///< True once available.
286 bool isScheduled : 1; ///< True once scheduled.
287 bool isScheduleHigh : 1; ///< True if preferable to schedule high.
288 bool isScheduleLow : 1; ///< True if preferable to schedule low.
289 bool isCloned : 1; ///< True if this node has been cloned.
290 bool isUnbuffered : 1; ///< Uses an unbuffered resource.
291 bool hasReservedResource : 1; ///< Uses a reserved resource.
292 Sched::Preference SchedulingPref = Sched::None; ///< Scheduling preference.
295 bool isDepthCurrent : 1; ///< True if Depth is current.
296 bool isHeightCurrent : 1; ///< True if Height is current.
297 unsigned Depth = 0; ///< Node depth.
298 unsigned Height = 0; ///< Node height.
301 unsigned TopReadyCycle = 0; ///< Cycle relative to start when node is ready.
302 unsigned BotReadyCycle = 0; ///< Cycle relative to end when node is ready.
304 const TargetRegisterClass *CopyDstRC =
305 nullptr; ///< Is a special copy node if != nullptr.
306 const TargetRegisterClass *CopySrcRC = nullptr;
308 /// \brief Constructs an SUnit for pre-regalloc scheduling to represent an
309 /// SDNode and any nodes flagged to it.
310 SUnit(SDNode *node, unsigned nodenum)
311 : Node(node), NodeNum(nodenum), isVRegCycle(false), isCall(false),
312 isCallOp(false), isTwoAddress(false), isCommutable(false),
313 hasPhysRegUses(false), hasPhysRegDefs(false), hasPhysRegClobbers(false),
314 isPending(false), isAvailable(false), isScheduled(false),
315 isScheduleHigh(false), isScheduleLow(false), isCloned(false),
316 isUnbuffered(false), hasReservedResource(false), isDepthCurrent(false),
317 isHeightCurrent(false) {}
319 /// \brief Constructs an SUnit for post-regalloc scheduling to represent a
321 SUnit(MachineInstr *instr, unsigned nodenum)
322 : Instr(instr), NodeNum(nodenum), isVRegCycle(false), isCall(false),
323 isCallOp(false), isTwoAddress(false), isCommutable(false),
324 hasPhysRegUses(false), hasPhysRegDefs(false), hasPhysRegClobbers(false),
325 isPending(false), isAvailable(false), isScheduled(false),
326 isScheduleHigh(false), isScheduleLow(false), isCloned(false),
327 isUnbuffered(false), hasReservedResource(false), isDepthCurrent(false),
328 isHeightCurrent(false) {}
330 /// \brief Constructs a placeholder SUnit.
332 : isVRegCycle(false), isCall(false), isCallOp(false), isTwoAddress(false),
333 isCommutable(false), hasPhysRegUses(false), hasPhysRegDefs(false),
334 hasPhysRegClobbers(false), isPending(false), isAvailable(false),
335 isScheduled(false), isScheduleHigh(false), isScheduleLow(false),
336 isCloned(false), isUnbuffered(false), hasReservedResource(false),
337 isDepthCurrent(false), isHeightCurrent(false) {}
339 /// \brief Boundary nodes are placeholders for the boundary of the
340 /// scheduling region.
342 /// BoundaryNodes can have DAG edges, including Data edges, but they do not
343 /// correspond to schedulable entities (e.g. instructions) and do not have a
344 /// valid ID. Consequently, always check for boundary nodes before accessing
345 /// an associative data structure keyed on node ID.
346 bool isBoundaryNode() const { return NodeNum == BoundaryID; }
348 /// Assigns the representative SDNode for this SUnit. This may be used
349 /// during pre-regalloc scheduling.
350 void setNode(SDNode *N) {
351 assert(!Instr && "Setting SDNode of SUnit with MachineInstr!");
355 /// Returns the representative SDNode for this SUnit. This may be used
356 /// during pre-regalloc scheduling.
357 SDNode *getNode() const {
358 assert(!Instr && "Reading SDNode of SUnit with MachineInstr!");
362 /// \brief Returns true if this SUnit refers to a machine instruction as
363 /// opposed to an SDNode.
364 bool isInstr() const { return Instr; }
366 /// Assigns the instruction for the SUnit. This may be used during
367 /// post-regalloc scheduling.
368 void setInstr(MachineInstr *MI) {
369 assert(!Node && "Setting MachineInstr of SUnit with SDNode!");
373 /// Returns the representative MachineInstr for this SUnit. This may be used
374 /// during post-regalloc scheduling.
375 MachineInstr *getInstr() const {
376 assert(!Node && "Reading MachineInstr of SUnit with SDNode!");
380 /// Adds the specified edge as a pred of the current node if not already.
381 /// It also adds the current node as a successor of the specified node.
382 bool addPred(const SDep &D, bool Required = true);
384 /// \brief Adds a barrier edge to SU by calling addPred(), with latency 0
385 /// generally or latency 1 for a store followed by a load.
386 bool addPredBarrier(SUnit *SU) {
387 SDep Dep(SU, SDep::Barrier);
388 unsigned TrueMemOrderLatency =
389 ((SU->getInstr()->mayStore() && this->getInstr()->mayLoad()) ? 1 : 0);
390 Dep.setLatency(TrueMemOrderLatency);
394 /// Removes the specified edge as a pred of the current node if it exists.
395 /// It also removes the current node as a successor of the specified node.
396 void removePred(const SDep &D);
398 /// Returns the depth of this node, which is the length of the maximum path
399 /// up to any node which has no predecessors.
400 unsigned getDepth() const {
402 const_cast<SUnit *>(this)->ComputeDepth();
406 /// \brief Returns the height of this node, which is the length of the
407 /// maximum path down to any node which has no successors.
408 unsigned getHeight() const {
409 if (!isHeightCurrent)
410 const_cast<SUnit *>(this)->ComputeHeight();
414 /// \brief If NewDepth is greater than this node's depth value, sets it to
415 /// be the new depth value. This also recursively marks successor nodes
417 void setDepthToAtLeast(unsigned NewDepth);
419 /// \brief If NewDepth is greater than this node's depth value, set it to be
420 /// the new height value. This also recursively marks predecessor nodes
422 void setHeightToAtLeast(unsigned NewHeight);
424 /// \brief Sets a flag in this node to indicate that its stored Depth value
425 /// will require recomputation the next time getDepth() is called.
426 void setDepthDirty();
428 /// \brief Sets a flag in this node to indicate that its stored Height value
429 /// will require recomputation the next time getHeight() is called.
430 void setHeightDirty();
432 /// Tests if node N is a predecessor of this node.
433 bool isPred(const SUnit *N) const {
434 for (const SDep &Pred : Preds)
435 if (Pred.getSUnit() == N)
440 /// Tests if node N is a successor of this node.
441 bool isSucc(const SUnit *N) const {
442 for (const SDep &Succ : Succs)
443 if (Succ.getSUnit() == N)
448 bool isTopReady() const {
449 return NumPredsLeft == 0;
451 bool isBottomReady() const {
452 return NumSuccsLeft == 0;
455 /// \brief Orders this node's predecessor edges such that the critical path
456 /// edge occurs first.
457 void biasCriticalPath();
459 void dump(const ScheduleDAG *G) const;
460 void dumpAll(const ScheduleDAG *G) const;
461 void print(raw_ostream &O, const ScheduleDAG *G) const;
465 void ComputeHeight();
468 /// Returns true if the specified SDep is equivalent except for latency.
469 inline bool SDep::overlaps(const SDep &Other) const {
470 if (Dep != Other.Dep)
472 switch (Dep.getInt()) {
476 return Contents.Reg == Other.Contents.Reg;
478 return Contents.OrdKind == Other.Contents.OrdKind;
480 llvm_unreachable("Invalid dependency kind!");
483 //// Returns the SUnit to which this edge points.
484 inline SUnit *SDep::getSUnit() const { return Dep.getPointer(); }
486 //// Assigns the SUnit to which this edge points.
487 inline void SDep::setSUnit(SUnit *SU) { Dep.setPointer(SU); }
489 /// Returns an enum value representing the kind of the dependence.
490 inline SDep::Kind SDep::getKind() const { return Dep.getInt(); }
492 //===--------------------------------------------------------------------===//
494 /// \brief This interface is used to plug different priorities computation
495 /// algorithms into the list scheduler. It implements the interface of a
496 /// standard priority queue, where nodes are inserted in arbitrary order and
497 /// returned in priority order. The computation of the priority and the
498 /// representation of the queue are totally up to the implementation to
500 class SchedulingPriorityQueue {
501 virtual void anchor();
503 unsigned CurCycle = 0;
507 SchedulingPriorityQueue(bool rf = false) : HasReadyFilter(rf) {}
509 virtual ~SchedulingPriorityQueue() = default;
511 virtual bool isBottomUp() const = 0;
513 virtual void initNodes(std::vector<SUnit> &SUnits) = 0;
514 virtual void addNode(const SUnit *SU) = 0;
515 virtual void updateNode(const SUnit *SU) = 0;
516 virtual void releaseState() = 0;
518 virtual bool empty() const = 0;
520 bool hasReadyFilter() const { return HasReadyFilter; }
522 virtual bool tracksRegPressure() const { return false; }
524 virtual bool isReady(SUnit *) const {
525 assert(!HasReadyFilter && "The ready filter must override isReady()");
529 virtual void push(SUnit *U) = 0;
531 void push_all(const std::vector<SUnit *> &Nodes) {
532 for (std::vector<SUnit *>::const_iterator I = Nodes.begin(),
533 E = Nodes.end(); I != E; ++I)
537 virtual SUnit *pop() = 0;
539 virtual void remove(SUnit *SU) = 0;
541 virtual void dump(ScheduleDAG *) const {}
543 /// As each node is scheduled, this method is invoked. This allows the
544 /// priority function to adjust the priority of related unscheduled nodes,
546 virtual void scheduledNode(SUnit *) {}
548 virtual void unscheduledNode(SUnit *) {}
550 void setCurCycle(unsigned Cycle) {
554 unsigned getCurCycle() const {
561 const TargetMachine &TM; ///< Target processor
562 const TargetInstrInfo *TII; ///< Target instruction information
563 const TargetRegisterInfo *TRI; ///< Target processor register info
564 MachineFunction &MF; ///< Machine function
565 MachineRegisterInfo &MRI; ///< Virtual/real register map
566 std::vector<SUnit> SUnits; ///< The scheduling units.
567 SUnit EntrySU; ///< Special node for the region entry.
568 SUnit ExitSU; ///< Special node for the region exit.
571 static const bool StressSched = false;
576 explicit ScheduleDAG(MachineFunction &mf);
578 virtual ~ScheduleDAG();
580 /// Clears the DAG state (between regions).
583 /// Returns the MCInstrDesc of this SUnit.
584 /// Returns NULL for SDNodes without a machine opcode.
585 const MCInstrDesc *getInstrDesc(const SUnit *SU) const {
586 if (SU->isInstr()) return &SU->getInstr()->getDesc();
587 return getNodeDesc(SU->getNode());
590 /// Pops up a GraphViz/gv window with the ScheduleDAG rendered using 'dot'.
591 virtual void viewGraph(const Twine &Name, const Twine &Title);
592 virtual void viewGraph();
594 virtual void dumpNode(const SUnit *SU) const = 0;
596 /// Returns a label for an SUnit node in a visualization of the ScheduleDAG.
597 virtual std::string getGraphNodeLabel(const SUnit *SU) const = 0;
599 /// Returns a label for the region of code covered by the DAG.
600 virtual std::string getDAGName() const = 0;
602 /// Adds custom features for a visualization of the ScheduleDAG.
603 virtual void addCustomGraphFeatures(GraphWriter<ScheduleDAG*> &) const {}
606 /// \brief Verifies that all SUnits were scheduled and that their state is
607 /// consistent. Returns the number of scheduled SUnits.
608 unsigned VerifyScheduledDAG(bool isBottomUp);
612 /// Returns the MCInstrDesc of this SDNode or NULL.
613 const MCInstrDesc *getNodeDesc(const SDNode *Node) const;
616 class SUnitIterator : public std::iterator<std::forward_iterator_tag,
621 SUnitIterator(SUnit *N, unsigned Op) : Node(N), Operand(Op) {}
624 bool operator==(const SUnitIterator& x) const {
625 return Operand == x.Operand;
627 bool operator!=(const SUnitIterator& x) const { return !operator==(x); }
629 pointer operator*() const {
630 return Node->Preds[Operand].getSUnit();
632 pointer operator->() const { return operator*(); }
634 SUnitIterator& operator++() { // Preincrement
638 SUnitIterator operator++(int) { // Postincrement
639 SUnitIterator tmp = *this; ++*this; return tmp;
642 static SUnitIterator begin(SUnit *N) { return SUnitIterator(N, 0); }
643 static SUnitIterator end (SUnit *N) {
644 return SUnitIterator(N, (unsigned)N->Preds.size());
647 unsigned getOperand() const { return Operand; }
648 const SUnit *getNode() const { return Node; }
650 /// Tests if this is not an SDep::Data dependence.
651 bool isCtrlDep() const {
652 return getSDep().isCtrl();
654 bool isArtificialDep() const {
655 return getSDep().isArtificial();
657 const SDep &getSDep() const {
658 return Node->Preds[Operand];
662 template <> struct GraphTraits<SUnit*> {
663 typedef SUnit *NodeRef;
664 typedef SUnitIterator ChildIteratorType;
665 static NodeRef getEntryNode(SUnit *N) { return N; }
666 static ChildIteratorType child_begin(NodeRef N) {
667 return SUnitIterator::begin(N);
669 static ChildIteratorType child_end(NodeRef N) {
670 return SUnitIterator::end(N);
674 template <> struct GraphTraits<ScheduleDAG*> : public GraphTraits<SUnit*> {
675 typedef pointer_iterator<std::vector<SUnit>::iterator> nodes_iterator;
676 static nodes_iterator nodes_begin(ScheduleDAG *G) {
677 return nodes_iterator(G->SUnits.begin());
679 static nodes_iterator nodes_end(ScheduleDAG *G) {
680 return nodes_iterator(G->SUnits.end());
684 /// This class can compute a topological ordering for SUnits and provides
685 /// methods for dynamically updating the ordering as new edges are added.
687 /// This allows a very fast implementation of IsReachable, for example.
688 class ScheduleDAGTopologicalSort {
689 /// A reference to the ScheduleDAG's SUnits.
690 std::vector<SUnit> &SUnits;
693 /// Maps topological index to the node number.
694 std::vector<int> Index2Node;
695 /// Maps the node number to its topological index.
696 std::vector<int> Node2Index;
697 /// a set of nodes visited during a DFS traversal.
700 /// Makes a DFS traversal and mark all nodes affected by the edge insertion.
701 /// These nodes will later get new topological indexes by means of the Shift
703 void DFS(const SUnit *SU, int UpperBound, bool& HasLoop);
705 /// \brief Reassigns topological indexes for the nodes in the DAG to
706 /// preserve the topological ordering.
707 void Shift(BitVector& Visited, int LowerBound, int UpperBound);
709 /// Assigns the topological index to the node n.
710 void Allocate(int n, int index);
713 ScheduleDAGTopologicalSort(std::vector<SUnit> &SUnits, SUnit *ExitSU);
715 /// Creates the initial topological ordering from the DAG to be scheduled.
716 void InitDAGTopologicalSorting();
718 /// Returns an array of SUs that are both in the successor
719 /// subtree of StartSU and in the predecessor subtree of TargetSU.
720 /// StartSU and TargetSU are not in the array.
721 /// Success is false if TargetSU is not in the successor subtree of
722 /// StartSU, else it is true.
723 std::vector<int> GetSubGraph(const SUnit &StartSU, const SUnit &TargetSU,
726 /// Checks if \p SU is reachable from \p TargetSU.
727 bool IsReachable(const SUnit *SU, const SUnit *TargetSU);
729 /// Returns true if addPred(TargetSU, SU) creates a cycle.
730 bool WillCreateCycle(SUnit *TargetSU, SUnit *SU);
732 /// \brief Updates the topological ordering to accommodate an edge to be
733 /// added from SUnit \p X to SUnit \p Y.
734 void AddPred(SUnit *Y, SUnit *X);
736 /// \brief Updates the topological ordering to accommodate an an edge to be
737 /// removed from the specified node \p N from the predecessors of the
738 /// current node \p M.
739 void RemovePred(SUnit *M, SUnit *N);
741 typedef std::vector<int>::iterator iterator;
742 typedef std::vector<int>::const_iterator const_iterator;
743 iterator begin() { return Index2Node.begin(); }
744 const_iterator begin() const { return Index2Node.begin(); }
745 iterator end() { return Index2Node.end(); }
746 const_iterator end() const { return Index2Node.end(); }
748 typedef std::vector<int>::reverse_iterator reverse_iterator;
749 typedef std::vector<int>::const_reverse_iterator const_reverse_iterator;
750 reverse_iterator rbegin() { return Index2Node.rbegin(); }
751 const_reverse_iterator rbegin() const { return Index2Node.rbegin(); }
752 reverse_iterator rend() { return Index2Node.rend(); }
753 const_reverse_iterator rend() const { return Index2Node.rend(); }
756 } // end namespace llvm
758 #endif // LLVM_CODEGEN_SCHEDULEDAG_H