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/CodeGen/TargetLowering.h"
26 #include "llvm/Support/ErrorHandling.h"
35 template<class Graph> class GraphWriter;
36 class LLVMTargetMachine;
37 class MachineFunction;
38 class MachineRegisterInfo;
40 struct MCSchedClassDesc;
44 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 /// 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 /// 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 /// 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 /// 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 /// 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 /// 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 void dump(const TargetRegisterInfo *TRI = nullptr) const;
243 struct isPodLike<SDep> { static const bool value = true; };
245 /// Scheduling unit. This is a node in the scheduling DAG.
248 enum : unsigned { BoundaryID = ~0u };
250 SDNode *Node = nullptr; ///< Representative node.
251 MachineInstr *Instr = nullptr; ///< Alternatively, a MachineInstr.
254 SUnit *OrigNode = nullptr; ///< If not this, the node from which this node
255 /// was cloned. (SD scheduling only)
257 const MCSchedClassDesc *SchedClass =
258 nullptr; ///< nullptr or resolved SchedClass.
260 SmallVector<SDep, 4> Preds; ///< All sunit predecessors.
261 SmallVector<SDep, 4> Succs; ///< All sunit successors.
263 typedef SmallVectorImpl<SDep>::iterator pred_iterator;
264 typedef SmallVectorImpl<SDep>::iterator succ_iterator;
265 typedef SmallVectorImpl<SDep>::const_iterator const_pred_iterator;
266 typedef SmallVectorImpl<SDep>::const_iterator const_succ_iterator;
268 unsigned NodeNum = BoundaryID; ///< Entry # of node in the node vector.
269 unsigned NodeQueueId = 0; ///< Queue id of node.
270 unsigned NumPreds = 0; ///< # of SDep::Data preds.
271 unsigned NumSuccs = 0; ///< # of SDep::Data sucss.
272 unsigned NumPredsLeft = 0; ///< # of preds not scheduled.
273 unsigned NumSuccsLeft = 0; ///< # of succs not scheduled.
274 unsigned WeakPredsLeft = 0; ///< # of weak preds not scheduled.
275 unsigned WeakSuccsLeft = 0; ///< # of weak succs not scheduled.
276 unsigned short NumRegDefsLeft = 0; ///< # of reg defs with no scheduled use.
277 unsigned short Latency = 0; ///< Node latency.
278 bool isVRegCycle : 1; ///< May use and def the same vreg.
279 bool isCall : 1; ///< Is a function call.
280 bool isCallOp : 1; ///< Is a function call operand.
281 bool isTwoAddress : 1; ///< Is a two-address instruction.
282 bool isCommutable : 1; ///< Is a commutable instruction.
283 bool hasPhysRegUses : 1; ///< Has physreg uses.
284 bool hasPhysRegDefs : 1; ///< Has physreg defs that are being used.
285 bool hasPhysRegClobbers : 1; ///< Has any physreg defs, used or not.
286 bool isPending : 1; ///< True once pending.
287 bool isAvailable : 1; ///< True once available.
288 bool isScheduled : 1; ///< True once scheduled.
289 bool isScheduleHigh : 1; ///< True if preferable to schedule high.
290 bool isScheduleLow : 1; ///< True if preferable to schedule low.
291 bool isCloned : 1; ///< True if this node has been cloned.
292 bool isUnbuffered : 1; ///< Uses an unbuffered resource.
293 bool hasReservedResource : 1; ///< Uses a reserved resource.
294 Sched::Preference SchedulingPref = Sched::None; ///< Scheduling preference.
297 bool isDepthCurrent : 1; ///< True if Depth is current.
298 bool isHeightCurrent : 1; ///< True if Height is current.
299 unsigned Depth = 0; ///< Node depth.
300 unsigned Height = 0; ///< Node height.
303 unsigned TopReadyCycle = 0; ///< Cycle relative to start when node is ready.
304 unsigned BotReadyCycle = 0; ///< Cycle relative to end when node is ready.
306 const TargetRegisterClass *CopyDstRC =
307 nullptr; ///< Is a special copy node if != nullptr.
308 const TargetRegisterClass *CopySrcRC = nullptr;
310 /// Constructs an SUnit for pre-regalloc scheduling to represent an
311 /// SDNode and any nodes flagged to it.
312 SUnit(SDNode *node, unsigned nodenum)
313 : Node(node), NodeNum(nodenum), isVRegCycle(false), isCall(false),
314 isCallOp(false), isTwoAddress(false), isCommutable(false),
315 hasPhysRegUses(false), hasPhysRegDefs(false), hasPhysRegClobbers(false),
316 isPending(false), isAvailable(false), isScheduled(false),
317 isScheduleHigh(false), isScheduleLow(false), isCloned(false),
318 isUnbuffered(false), hasReservedResource(false), isDepthCurrent(false),
319 isHeightCurrent(false) {}
321 /// Constructs an SUnit for post-regalloc scheduling to represent a
323 SUnit(MachineInstr *instr, unsigned nodenum)
324 : Instr(instr), NodeNum(nodenum), isVRegCycle(false), isCall(false),
325 isCallOp(false), isTwoAddress(false), isCommutable(false),
326 hasPhysRegUses(false), hasPhysRegDefs(false), hasPhysRegClobbers(false),
327 isPending(false), isAvailable(false), isScheduled(false),
328 isScheduleHigh(false), isScheduleLow(false), isCloned(false),
329 isUnbuffered(false), hasReservedResource(false), isDepthCurrent(false),
330 isHeightCurrent(false) {}
332 /// Constructs a placeholder SUnit.
334 : isVRegCycle(false), isCall(false), isCallOp(false), isTwoAddress(false),
335 isCommutable(false), hasPhysRegUses(false), hasPhysRegDefs(false),
336 hasPhysRegClobbers(false), isPending(false), isAvailable(false),
337 isScheduled(false), isScheduleHigh(false), isScheduleLow(false),
338 isCloned(false), isUnbuffered(false), hasReservedResource(false),
339 isDepthCurrent(false), isHeightCurrent(false) {}
341 /// Boundary nodes are placeholders for the boundary of the
342 /// scheduling region.
344 /// BoundaryNodes can have DAG edges, including Data edges, but they do not
345 /// correspond to schedulable entities (e.g. instructions) and do not have a
346 /// valid ID. Consequently, always check for boundary nodes before accessing
347 /// an associative data structure keyed on node ID.
348 bool isBoundaryNode() const { return NodeNum == BoundaryID; }
350 /// Assigns the representative SDNode for this SUnit. This may be used
351 /// during pre-regalloc scheduling.
352 void setNode(SDNode *N) {
353 assert(!Instr && "Setting SDNode of SUnit with MachineInstr!");
357 /// Returns the representative SDNode for this SUnit. This may be used
358 /// during pre-regalloc scheduling.
359 SDNode *getNode() const {
360 assert(!Instr && "Reading SDNode of SUnit with MachineInstr!");
364 /// Returns true if this SUnit refers to a machine instruction as
365 /// opposed to an SDNode.
366 bool isInstr() const { return Instr; }
368 /// Assigns the instruction for the SUnit. This may be used during
369 /// post-regalloc scheduling.
370 void setInstr(MachineInstr *MI) {
371 assert(!Node && "Setting MachineInstr of SUnit with SDNode!");
375 /// Returns the representative MachineInstr for this SUnit. This may be used
376 /// during post-regalloc scheduling.
377 MachineInstr *getInstr() const {
378 assert(!Node && "Reading MachineInstr of SUnit with SDNode!");
382 /// Adds the specified edge as a pred of the current node if not already.
383 /// It also adds the current node as a successor of the specified node.
384 bool addPred(const SDep &D, bool Required = true);
386 /// Adds a barrier edge to SU by calling addPred(), with latency 0
387 /// generally or latency 1 for a store followed by a load.
388 bool addPredBarrier(SUnit *SU) {
389 SDep Dep(SU, SDep::Barrier);
390 unsigned TrueMemOrderLatency =
391 ((SU->getInstr()->mayStore() && this->getInstr()->mayLoad()) ? 1 : 0);
392 Dep.setLatency(TrueMemOrderLatency);
396 /// Removes the specified edge as a pred of the current node if it exists.
397 /// It also removes the current node as a successor of the specified node.
398 void removePred(const SDep &D);
400 /// Returns the depth of this node, which is the length of the maximum path
401 /// up to any node which has no predecessors.
402 unsigned getDepth() const {
404 const_cast<SUnit *>(this)->ComputeDepth();
408 /// Returns the height of this node, which is the length of the
409 /// maximum path down to any node which has no successors.
410 unsigned getHeight() const {
411 if (!isHeightCurrent)
412 const_cast<SUnit *>(this)->ComputeHeight();
416 /// If NewDepth is greater than this node's depth value, sets it to
417 /// be the new depth value. This also recursively marks successor nodes
419 void setDepthToAtLeast(unsigned NewDepth);
421 /// If NewDepth is greater than this node's depth value, set it to be
422 /// the new height value. This also recursively marks predecessor nodes
424 void setHeightToAtLeast(unsigned NewHeight);
426 /// Sets a flag in this node to indicate that its stored Depth value
427 /// will require recomputation the next time getDepth() is called.
428 void setDepthDirty();
430 /// Sets a flag in this node to indicate that its stored Height value
431 /// will require recomputation the next time getHeight() is called.
432 void setHeightDirty();
434 /// Tests if node N is a predecessor of this node.
435 bool isPred(const SUnit *N) const {
436 for (const SDep &Pred : Preds)
437 if (Pred.getSUnit() == N)
442 /// Tests if node N is a successor of this node.
443 bool isSucc(const SUnit *N) const {
444 for (const SDep &Succ : Succs)
445 if (Succ.getSUnit() == N)
450 bool isTopReady() const {
451 return NumPredsLeft == 0;
453 bool isBottomReady() const {
454 return NumSuccsLeft == 0;
457 /// Orders this node's predecessor edges such that the critical path
458 /// edge occurs first.
459 void biasCriticalPath();
461 void dumpAttributes() 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 /// 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 LLVMTargetMachine &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;
595 virtual void dump() const = 0;
596 void dumpNodeName(const SUnit &SU) const;
598 /// Returns a label for an SUnit node in a visualization of the ScheduleDAG.
599 virtual std::string getGraphNodeLabel(const SUnit *SU) const = 0;
601 /// Returns a label for the region of code covered by the DAG.
602 virtual std::string getDAGName() const = 0;
604 /// Adds custom features for a visualization of the ScheduleDAG.
605 virtual void addCustomGraphFeatures(GraphWriter<ScheduleDAG*> &) const {}
608 /// Verifies that all SUnits were scheduled and that their state is
609 /// consistent. Returns the number of scheduled SUnits.
610 unsigned VerifyScheduledDAG(bool isBottomUp);
614 void dumpNodeAll(const SUnit &SU) const;
617 /// Returns the MCInstrDesc of this SDNode or NULL.
618 const MCInstrDesc *getNodeDesc(const SDNode *Node) const;
621 class SUnitIterator : public std::iterator<std::forward_iterator_tag,
626 SUnitIterator(SUnit *N, unsigned Op) : Node(N), Operand(Op) {}
629 bool operator==(const SUnitIterator& x) const {
630 return Operand == x.Operand;
632 bool operator!=(const SUnitIterator& x) const { return !operator==(x); }
634 pointer operator*() const {
635 return Node->Preds[Operand].getSUnit();
637 pointer operator->() const { return operator*(); }
639 SUnitIterator& operator++() { // Preincrement
643 SUnitIterator operator++(int) { // Postincrement
644 SUnitIterator tmp = *this; ++*this; return tmp;
647 static SUnitIterator begin(SUnit *N) { return SUnitIterator(N, 0); }
648 static SUnitIterator end (SUnit *N) {
649 return SUnitIterator(N, (unsigned)N->Preds.size());
652 unsigned getOperand() const { return Operand; }
653 const SUnit *getNode() const { return Node; }
655 /// Tests if this is not an SDep::Data dependence.
656 bool isCtrlDep() const {
657 return getSDep().isCtrl();
659 bool isArtificialDep() const {
660 return getSDep().isArtificial();
662 const SDep &getSDep() const {
663 return Node->Preds[Operand];
667 template <> struct GraphTraits<SUnit*> {
668 typedef SUnit *NodeRef;
669 typedef SUnitIterator ChildIteratorType;
670 static NodeRef getEntryNode(SUnit *N) { return N; }
671 static ChildIteratorType child_begin(NodeRef N) {
672 return SUnitIterator::begin(N);
674 static ChildIteratorType child_end(NodeRef N) {
675 return SUnitIterator::end(N);
679 template <> struct GraphTraits<ScheduleDAG*> : public GraphTraits<SUnit*> {
680 typedef pointer_iterator<std::vector<SUnit>::iterator> nodes_iterator;
681 static nodes_iterator nodes_begin(ScheduleDAG *G) {
682 return nodes_iterator(G->SUnits.begin());
684 static nodes_iterator nodes_end(ScheduleDAG *G) {
685 return nodes_iterator(G->SUnits.end());
689 /// This class can compute a topological ordering for SUnits and provides
690 /// methods for dynamically updating the ordering as new edges are added.
692 /// This allows a very fast implementation of IsReachable, for example.
693 class ScheduleDAGTopologicalSort {
694 /// A reference to the ScheduleDAG's SUnits.
695 std::vector<SUnit> &SUnits;
698 /// Maps topological index to the node number.
699 std::vector<int> Index2Node;
700 /// Maps the node number to its topological index.
701 std::vector<int> Node2Index;
702 /// a set of nodes visited during a DFS traversal.
705 /// Makes a DFS traversal and mark all nodes affected by the edge insertion.
706 /// These nodes will later get new topological indexes by means of the Shift
708 void DFS(const SUnit *SU, int UpperBound, bool& HasLoop);
710 /// Reassigns topological indexes for the nodes in the DAG to
711 /// preserve the topological ordering.
712 void Shift(BitVector& Visited, int LowerBound, int UpperBound);
714 /// Assigns the topological index to the node n.
715 void Allocate(int n, int index);
718 ScheduleDAGTopologicalSort(std::vector<SUnit> &SUnits, SUnit *ExitSU);
720 /// Creates the initial topological ordering from the DAG to be scheduled.
721 void InitDAGTopologicalSorting();
723 /// Returns an array of SUs that are both in the successor
724 /// subtree of StartSU and in the predecessor subtree of TargetSU.
725 /// StartSU and TargetSU are not in the array.
726 /// Success is false if TargetSU is not in the successor subtree of
727 /// StartSU, else it is true.
728 std::vector<int> GetSubGraph(const SUnit &StartSU, const SUnit &TargetSU,
731 /// Checks if \p SU is reachable from \p TargetSU.
732 bool IsReachable(const SUnit *SU, const SUnit *TargetSU);
734 /// Returns true if addPred(TargetSU, SU) creates a cycle.
735 bool WillCreateCycle(SUnit *TargetSU, SUnit *SU);
737 /// Updates the topological ordering to accommodate an edge to be
738 /// added from SUnit \p X to SUnit \p Y.
739 void AddPred(SUnit *Y, SUnit *X);
741 /// Updates the topological ordering to accommodate an an edge to be
742 /// removed from the specified node \p N from the predecessors of the
743 /// current node \p M.
744 void RemovePred(SUnit *M, SUnit *N);
746 typedef std::vector<int>::iterator iterator;
747 typedef std::vector<int>::const_iterator const_iterator;
748 iterator begin() { return Index2Node.begin(); }
749 const_iterator begin() const { return Index2Node.begin(); }
750 iterator end() { return Index2Node.end(); }
751 const_iterator end() const { return Index2Node.end(); }
753 typedef std::vector<int>::reverse_iterator reverse_iterator;
754 typedef std::vector<int>::const_reverse_iterator const_reverse_iterator;
755 reverse_iterator rbegin() { return Index2Node.rbegin(); }
756 const_reverse_iterator rbegin() const { return Index2Node.rbegin(); }
757 reverse_iterator rend() { return Index2Node.rend(); }
758 const_reverse_iterator rend() const { return Index2Node.rend(); }
761 } // end namespace llvm
763 #endif // LLVM_CODEGEN_SCHEDULEDAG_H