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/PointerIntPair.h"
22 #include "llvm/ADT/SmallVector.h"
23 #include "llvm/ADT/iterator.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!");
239 raw_ostream &print(raw_ostream &O,
240 const TargetRegisterInfo *TRI = nullptr) const;
244 struct isPodLike<SDep> { static const bool value = true; };
246 /// Scheduling unit. This is a node in the scheduling DAG.
249 enum : unsigned { BoundaryID = ~0u };
251 SDNode *Node = nullptr; ///< Representative node.
252 MachineInstr *Instr = nullptr; ///< Alternatively, a MachineInstr.
255 SUnit *OrigNode = nullptr; ///< If not this, the node from which this node
256 /// was cloned. (SD scheduling only)
258 const MCSchedClassDesc *SchedClass =
259 nullptr; ///< nullptr or resolved SchedClass.
261 SmallVector<SDep, 4> Preds; ///< All sunit predecessors.
262 SmallVector<SDep, 4> Succs; ///< All sunit successors.
264 typedef SmallVectorImpl<SDep>::iterator pred_iterator;
265 typedef SmallVectorImpl<SDep>::iterator succ_iterator;
266 typedef SmallVectorImpl<SDep>::const_iterator const_pred_iterator;
267 typedef SmallVectorImpl<SDep>::const_iterator const_succ_iterator;
269 unsigned NodeNum = BoundaryID; ///< Entry # of node in the node vector.
270 unsigned NodeQueueId = 0; ///< Queue id of node.
271 unsigned NumPreds = 0; ///< # of SDep::Data preds.
272 unsigned NumSuccs = 0; ///< # of SDep::Data sucss.
273 unsigned NumPredsLeft = 0; ///< # of preds not scheduled.
274 unsigned NumSuccsLeft = 0; ///< # of succs not scheduled.
275 unsigned WeakPredsLeft = 0; ///< # of weak preds not scheduled.
276 unsigned WeakSuccsLeft = 0; ///< # of weak succs not scheduled.
277 unsigned short NumRegDefsLeft = 0; ///< # of reg defs with no scheduled use.
278 unsigned short Latency = 0; ///< Node latency.
279 bool isVRegCycle : 1; ///< May use and def the same vreg.
280 bool isCall : 1; ///< Is a function call.
281 bool isCallOp : 1; ///< Is a function call operand.
282 bool isTwoAddress : 1; ///< Is a two-address instruction.
283 bool isCommutable : 1; ///< Is a commutable instruction.
284 bool hasPhysRegUses : 1; ///< Has physreg uses.
285 bool hasPhysRegDefs : 1; ///< Has physreg defs that are being used.
286 bool hasPhysRegClobbers : 1; ///< Has any physreg defs, used or not.
287 bool isPending : 1; ///< True once pending.
288 bool isAvailable : 1; ///< True once available.
289 bool isScheduled : 1; ///< True once scheduled.
290 bool isScheduleHigh : 1; ///< True if preferable to schedule high.
291 bool isScheduleLow : 1; ///< True if preferable to schedule low.
292 bool isCloned : 1; ///< True if this node has been cloned.
293 bool isUnbuffered : 1; ///< Uses an unbuffered resource.
294 bool hasReservedResource : 1; ///< Uses a reserved resource.
295 Sched::Preference SchedulingPref = Sched::None; ///< Scheduling preference.
298 bool isDepthCurrent : 1; ///< True if Depth is current.
299 bool isHeightCurrent : 1; ///< True if Height is current.
300 unsigned Depth = 0; ///< Node depth.
301 unsigned Height = 0; ///< Node height.
304 unsigned TopReadyCycle = 0; ///< Cycle relative to start when node is ready.
305 unsigned BotReadyCycle = 0; ///< Cycle relative to end when node is ready.
307 const TargetRegisterClass *CopyDstRC =
308 nullptr; ///< Is a special copy node if != nullptr.
309 const TargetRegisterClass *CopySrcRC = nullptr;
311 /// \brief Constructs an SUnit for pre-regalloc scheduling to represent an
312 /// SDNode and any nodes flagged to it.
313 SUnit(SDNode *node, unsigned nodenum)
314 : Node(node), NodeNum(nodenum), isVRegCycle(false), isCall(false),
315 isCallOp(false), isTwoAddress(false), isCommutable(false),
316 hasPhysRegUses(false), hasPhysRegDefs(false), hasPhysRegClobbers(false),
317 isPending(false), isAvailable(false), isScheduled(false),
318 isScheduleHigh(false), isScheduleLow(false), isCloned(false),
319 isUnbuffered(false), hasReservedResource(false), isDepthCurrent(false),
320 isHeightCurrent(false) {}
322 /// \brief Constructs an SUnit for post-regalloc scheduling to represent a
324 SUnit(MachineInstr *instr, unsigned nodenum)
325 : Instr(instr), NodeNum(nodenum), isVRegCycle(false), isCall(false),
326 isCallOp(false), isTwoAddress(false), isCommutable(false),
327 hasPhysRegUses(false), hasPhysRegDefs(false), hasPhysRegClobbers(false),
328 isPending(false), isAvailable(false), isScheduled(false),
329 isScheduleHigh(false), isScheduleLow(false), isCloned(false),
330 isUnbuffered(false), hasReservedResource(false), isDepthCurrent(false),
331 isHeightCurrent(false) {}
333 /// \brief Constructs a placeholder SUnit.
335 : isVRegCycle(false), isCall(false), isCallOp(false), isTwoAddress(false),
336 isCommutable(false), hasPhysRegUses(false), hasPhysRegDefs(false),
337 hasPhysRegClobbers(false), isPending(false), isAvailable(false),
338 isScheduled(false), isScheduleHigh(false), isScheduleLow(false),
339 isCloned(false), isUnbuffered(false), hasReservedResource(false),
340 isDepthCurrent(false), isHeightCurrent(false) {}
342 /// \brief Boundary nodes are placeholders for the boundary of the
343 /// scheduling region.
345 /// BoundaryNodes can have DAG edges, including Data edges, but they do not
346 /// correspond to schedulable entities (e.g. instructions) and do not have a
347 /// valid ID. Consequently, always check for boundary nodes before accessing
348 /// an associative data structure keyed on node ID.
349 bool isBoundaryNode() const { return NodeNum == BoundaryID; }
351 /// Assigns the representative SDNode for this SUnit. This may be used
352 /// during pre-regalloc scheduling.
353 void setNode(SDNode *N) {
354 assert(!Instr && "Setting SDNode of SUnit with MachineInstr!");
358 /// Returns the representative SDNode for this SUnit. This may be used
359 /// during pre-regalloc scheduling.
360 SDNode *getNode() const {
361 assert(!Instr && "Reading SDNode of SUnit with MachineInstr!");
365 /// \brief Returns true if this SUnit refers to a machine instruction as
366 /// opposed to an SDNode.
367 bool isInstr() const { return Instr; }
369 /// Assigns the instruction for the SUnit. This may be used during
370 /// post-regalloc scheduling.
371 void setInstr(MachineInstr *MI) {
372 assert(!Node && "Setting MachineInstr of SUnit with SDNode!");
376 /// Returns the representative MachineInstr for this SUnit. This may be used
377 /// during post-regalloc scheduling.
378 MachineInstr *getInstr() const {
379 assert(!Node && "Reading MachineInstr of SUnit with SDNode!");
383 /// Adds the specified edge as a pred of the current node if not already.
384 /// It also adds the current node as a successor of the specified node.
385 bool addPred(const SDep &D, bool Required = true);
387 /// \brief Adds a barrier edge to SU by calling addPred(), with latency 0
388 /// generally or latency 1 for a store followed by a load.
389 bool addPredBarrier(SUnit *SU) {
390 SDep Dep(SU, SDep::Barrier);
391 unsigned TrueMemOrderLatency =
392 ((SU->getInstr()->mayStore() && this->getInstr()->mayLoad()) ? 1 : 0);
393 Dep.setLatency(TrueMemOrderLatency);
397 /// Removes the specified edge as a pred of the current node if it exists.
398 /// It also removes the current node as a successor of the specified node.
399 void removePred(const SDep &D);
401 /// Returns the depth of this node, which is the length of the maximum path
402 /// up to any node which has no predecessors.
403 unsigned getDepth() const {
405 const_cast<SUnit *>(this)->ComputeDepth();
409 /// \brief Returns the height of this node, which is the length of the
410 /// maximum path down to any node which has no successors.
411 unsigned getHeight() const {
412 if (!isHeightCurrent)
413 const_cast<SUnit *>(this)->ComputeHeight();
417 /// \brief If NewDepth is greater than this node's depth value, sets it to
418 /// be the new depth value. This also recursively marks successor nodes
420 void setDepthToAtLeast(unsigned NewDepth);
422 /// \brief If NewDepth is greater than this node's depth value, set it to be
423 /// the new height value. This also recursively marks predecessor nodes
425 void setHeightToAtLeast(unsigned NewHeight);
427 /// \brief Sets a flag in this node to indicate that its stored Depth value
428 /// will require recomputation the next time getDepth() is called.
429 void setDepthDirty();
431 /// \brief Sets a flag in this node to indicate that its stored Height value
432 /// will require recomputation the next time getHeight() is called.
433 void setHeightDirty();
435 /// Tests if node N is a predecessor of this node.
436 bool isPred(const SUnit *N) const {
437 for (const SDep &Pred : Preds)
438 if (Pred.getSUnit() == N)
443 /// Tests if node N is a successor of this node.
444 bool isSucc(const SUnit *N) const {
445 for (const SDep &Succ : Succs)
446 if (Succ.getSUnit() == N)
451 bool isTopReady() const {
452 return NumPredsLeft == 0;
454 bool isBottomReady() const {
455 return NumSuccsLeft == 0;
458 /// \brief Orders this node's predecessor edges such that the critical path
459 /// edge occurs first.
460 void biasCriticalPath();
462 void dump(const ScheduleDAG *G) const;
463 void dumpAll(const ScheduleDAG *G) const;
464 raw_ostream &print(raw_ostream &O,
465 const SUnit *N = nullptr,
466 const SUnit *X = nullptr) const;
467 raw_ostream &print(raw_ostream &O, const ScheduleDAG *G) const;
471 void ComputeHeight();
474 /// Returns true if the specified SDep is equivalent except for latency.
475 inline bool SDep::overlaps(const SDep &Other) const {
476 if (Dep != Other.Dep)
478 switch (Dep.getInt()) {
482 return Contents.Reg == Other.Contents.Reg;
484 return Contents.OrdKind == Other.Contents.OrdKind;
486 llvm_unreachable("Invalid dependency kind!");
489 //// Returns the SUnit to which this edge points.
490 inline SUnit *SDep::getSUnit() const { return Dep.getPointer(); }
492 //// Assigns the SUnit to which this edge points.
493 inline void SDep::setSUnit(SUnit *SU) { Dep.setPointer(SU); }
495 /// Returns an enum value representing the kind of the dependence.
496 inline SDep::Kind SDep::getKind() const { return Dep.getInt(); }
498 //===--------------------------------------------------------------------===//
500 /// \brief This interface is used to plug different priorities computation
501 /// algorithms into the list scheduler. It implements the interface of a
502 /// standard priority queue, where nodes are inserted in arbitrary order and
503 /// returned in priority order. The computation of the priority and the
504 /// representation of the queue are totally up to the implementation to
506 class SchedulingPriorityQueue {
507 virtual void anchor();
509 unsigned CurCycle = 0;
513 SchedulingPriorityQueue(bool rf = false) : HasReadyFilter(rf) {}
515 virtual ~SchedulingPriorityQueue() = default;
517 virtual bool isBottomUp() const = 0;
519 virtual void initNodes(std::vector<SUnit> &SUnits) = 0;
520 virtual void addNode(const SUnit *SU) = 0;
521 virtual void updateNode(const SUnit *SU) = 0;
522 virtual void releaseState() = 0;
524 virtual bool empty() const = 0;
526 bool hasReadyFilter() const { return HasReadyFilter; }
528 virtual bool tracksRegPressure() const { return false; }
530 virtual bool isReady(SUnit *) const {
531 assert(!HasReadyFilter && "The ready filter must override isReady()");
535 virtual void push(SUnit *U) = 0;
537 void push_all(const std::vector<SUnit *> &Nodes) {
538 for (std::vector<SUnit *>::const_iterator I = Nodes.begin(),
539 E = Nodes.end(); I != E; ++I)
543 virtual SUnit *pop() = 0;
545 virtual void remove(SUnit *SU) = 0;
547 virtual void dump(ScheduleDAG *) const {}
549 /// As each node is scheduled, this method is invoked. This allows the
550 /// priority function to adjust the priority of related unscheduled nodes,
552 virtual void scheduledNode(SUnit *) {}
554 virtual void unscheduledNode(SUnit *) {}
556 void setCurCycle(unsigned Cycle) {
560 unsigned getCurCycle() const {
567 const TargetMachine &TM; ///< Target processor
568 const TargetInstrInfo *TII; ///< Target instruction information
569 const TargetRegisterInfo *TRI; ///< Target processor register info
570 MachineFunction &MF; ///< Machine function
571 MachineRegisterInfo &MRI; ///< Virtual/real register map
572 std::vector<SUnit> SUnits; ///< The scheduling units.
573 SUnit EntrySU; ///< Special node for the region entry.
574 SUnit ExitSU; ///< Special node for the region exit.
577 static const bool StressSched = false;
582 explicit ScheduleDAG(MachineFunction &mf);
584 virtual ~ScheduleDAG();
586 /// Clears the DAG state (between regions).
589 /// Returns the MCInstrDesc of this SUnit.
590 /// Returns NULL for SDNodes without a machine opcode.
591 const MCInstrDesc *getInstrDesc(const SUnit *SU) const {
592 if (SU->isInstr()) return &SU->getInstr()->getDesc();
593 return getNodeDesc(SU->getNode());
596 /// Pops up a GraphViz/gv window with the ScheduleDAG rendered using 'dot'.
597 virtual void viewGraph(const Twine &Name, const Twine &Title);
598 virtual void viewGraph();
600 virtual void dumpNode(const SUnit *SU) const = 0;
602 /// Returns a label for an SUnit node in a visualization of the ScheduleDAG.
603 virtual std::string getGraphNodeLabel(const SUnit *SU) const = 0;
605 /// Returns a label for the region of code covered by the DAG.
606 virtual std::string getDAGName() const = 0;
608 /// Adds custom features for a visualization of the ScheduleDAG.
609 virtual void addCustomGraphFeatures(GraphWriter<ScheduleDAG*> &) const {}
612 /// \brief Verifies that all SUnits were scheduled and that their state is
613 /// consistent. Returns the number of scheduled SUnits.
614 unsigned VerifyScheduledDAG(bool isBottomUp);
618 /// Returns the MCInstrDesc of this SDNode or NULL.
619 const MCInstrDesc *getNodeDesc(const SDNode *Node) const;
622 class SUnitIterator : public std::iterator<std::forward_iterator_tag,
627 SUnitIterator(SUnit *N, unsigned Op) : Node(N), Operand(Op) {}
630 bool operator==(const SUnitIterator& x) const {
631 return Operand == x.Operand;
633 bool operator!=(const SUnitIterator& x) const { return !operator==(x); }
635 pointer operator*() const {
636 return Node->Preds[Operand].getSUnit();
638 pointer operator->() const { return operator*(); }
640 SUnitIterator& operator++() { // Preincrement
644 SUnitIterator operator++(int) { // Postincrement
645 SUnitIterator tmp = *this; ++*this; return tmp;
648 static SUnitIterator begin(SUnit *N) { return SUnitIterator(N, 0); }
649 static SUnitIterator end (SUnit *N) {
650 return SUnitIterator(N, (unsigned)N->Preds.size());
653 unsigned getOperand() const { return Operand; }
654 const SUnit *getNode() const { return Node; }
656 /// Tests if this is not an SDep::Data dependence.
657 bool isCtrlDep() const {
658 return getSDep().isCtrl();
660 bool isArtificialDep() const {
661 return getSDep().isArtificial();
663 const SDep &getSDep() const {
664 return Node->Preds[Operand];
668 template <> struct GraphTraits<SUnit*> {
669 typedef SUnit *NodeRef;
670 typedef SUnitIterator ChildIteratorType;
671 static NodeRef getEntryNode(SUnit *N) { return N; }
672 static ChildIteratorType child_begin(NodeRef N) {
673 return SUnitIterator::begin(N);
675 static ChildIteratorType child_end(NodeRef N) {
676 return SUnitIterator::end(N);
680 template <> struct GraphTraits<ScheduleDAG*> : public GraphTraits<SUnit*> {
681 typedef pointer_iterator<std::vector<SUnit>::iterator> nodes_iterator;
682 static nodes_iterator nodes_begin(ScheduleDAG *G) {
683 return nodes_iterator(G->SUnits.begin());
685 static nodes_iterator nodes_end(ScheduleDAG *G) {
686 return nodes_iterator(G->SUnits.end());
690 /// This class can compute a topological ordering for SUnits and provides
691 /// methods for dynamically updating the ordering as new edges are added.
693 /// This allows a very fast implementation of IsReachable, for example.
694 class ScheduleDAGTopologicalSort {
695 /// A reference to the ScheduleDAG's SUnits.
696 std::vector<SUnit> &SUnits;
699 /// Maps topological index to the node number.
700 std::vector<int> Index2Node;
701 /// Maps the node number to its topological index.
702 std::vector<int> Node2Index;
703 /// a set of nodes visited during a DFS traversal.
706 /// Makes a DFS traversal and mark all nodes affected by the edge insertion.
707 /// These nodes will later get new topological indexes by means of the Shift
709 void DFS(const SUnit *SU, int UpperBound, bool& HasLoop);
711 /// \brief Reassigns topological indexes for the nodes in the DAG to
712 /// preserve the topological ordering.
713 void Shift(BitVector& Visited, int LowerBound, int UpperBound);
715 /// Assigns the topological index to the node n.
716 void Allocate(int n, int index);
719 ScheduleDAGTopologicalSort(std::vector<SUnit> &SUnits, SUnit *ExitSU);
721 /// Creates the initial topological ordering from the DAG to be scheduled.
722 void InitDAGTopologicalSorting();
724 /// Returns an array of SUs that are both in the successor
725 /// subtree of StartSU and in the predecessor subtree of TargetSU.
726 /// StartSU and TargetSU are not in the array.
727 /// Success is false if TargetSU is not in the successor subtree of
728 /// StartSU, else it is true.
729 std::vector<int> GetSubGraph(const SUnit &StartSU, const SUnit &TargetSU,
732 /// Checks if \p SU is reachable from \p TargetSU.
733 bool IsReachable(const SUnit *SU, const SUnit *TargetSU);
735 /// Returns true if addPred(TargetSU, SU) creates a cycle.
736 bool WillCreateCycle(SUnit *TargetSU, SUnit *SU);
738 /// \brief Updates the topological ordering to accommodate an edge to be
739 /// added from SUnit \p X to SUnit \p Y.
740 void AddPred(SUnit *Y, SUnit *X);
742 /// \brief Updates the topological ordering to accommodate an an edge to be
743 /// removed from the specified node \p N from the predecessors of the
744 /// current node \p M.
745 void RemovePred(SUnit *M, SUnit *N);
747 typedef std::vector<int>::iterator iterator;
748 typedef std::vector<int>::const_iterator const_iterator;
749 iterator begin() { return Index2Node.begin(); }
750 const_iterator begin() const { return Index2Node.begin(); }
751 iterator end() { return Index2Node.end(); }
752 const_iterator end() const { return Index2Node.end(); }
754 typedef std::vector<int>::reverse_iterator reverse_iterator;
755 typedef std::vector<int>::const_reverse_iterator const_reverse_iterator;
756 reverse_iterator rbegin() { return Index2Node.rbegin(); }
757 const_reverse_iterator rbegin() const { return Index2Node.rbegin(); }
758 reverse_iterator rend() { return Index2Node.rend(); }
759 const_reverse_iterator rend() const { return Index2Node.rend(); }
762 } // end namespace llvm
764 #endif // LLVM_CODEGEN_SCHEDULEDAG_H