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 // This file implements the ScheduleDAG class, which is used as the common
11 // base 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/CodeGen/MachineInstr.h"
24 #include "llvm/Target/TargetLowering.h"
29 class MachineConstantPool;
30 class MachineFunction;
31 class MachineRegisterInfo;
33 struct MCSchedClassDesc;
34 class TargetRegisterInfo;
37 class TargetInstrInfo;
40 class TargetRegisterClass;
41 template<class Graph> class GraphWriter;
43 /// SDep - Scheduling dependency. This represents one direction of an
44 /// edge in the scheduling DAG.
47 /// Kind - These are the different kinds of scheduling dependencies.
49 Data, ///< Regular data dependence (aka true-dependence).
50 Anti, ///< A register anti-dependedence (aka WAR).
51 Output, ///< A register output-dependence (aka WAW).
52 Order ///< Any other ordering dependency.
55 // Strong dependencies must be respected by the scheduler. Artificial
56 // dependencies may be removed only if they are redundant with another
59 // Weak dependencies may be violated by the scheduling strategy, but only if
60 // the strategy can prove it is correct to do so.
62 // Strong OrderKinds must occur before "Weak".
63 // Weak OrderKinds must occur after "Weak".
65 Barrier, ///< An unknown scheduling barrier.
66 MayAliasMem, ///< Nonvolatile load/Store instructions that may alias.
67 MustAliasMem, ///< Nonvolatile load/Store instructions that must alias.
68 Artificial, ///< Arbitrary strong DAG edge (no real dependence).
69 Weak, ///< Arbitrary weak DAG edge.
70 Cluster ///< Weak DAG edge linking a chain of clustered instrs.
74 /// Dep - A pointer to the depending/depended-on SUnit, and an enum
75 /// indicating the kind of the dependency.
76 PointerIntPair<SUnit *, 2, Kind> Dep;
78 /// Contents - A union discriminated by the dependence kind.
80 /// Reg - For Data, Anti, and Output dependencies, the associated
81 /// register. For Data dependencies that don't currently have a register
82 /// assigned, this is set to zero.
85 /// Order - Additional information about Order dependencies.
86 unsigned OrdKind; // enum OrderKind
89 /// Latency - The time associated with this edge. Often this is just
90 /// the value of the Latency field of the predecessor, however advanced
91 /// models may provide additional information about specific edges.
95 /// SDep - Construct a null SDep. This is only for use by container
96 /// classes which require default constructors. SUnits may not
97 /// have null SDep edges.
98 SDep() : Dep(0, Data) {}
100 /// SDep - Construct an SDep with the specified values.
101 SDep(SUnit *S, Kind kind, unsigned Reg)
102 : Dep(S, kind), Contents() {
105 llvm_unreachable("Reg given for non-register dependence!");
109 "SDep::Anti and SDep::Output must use a non-zero Reg!");
119 SDep(SUnit *S, OrderKind kind)
120 : Dep(S, Order), Contents(), Latency(0) {
121 Contents.OrdKind = kind;
124 /// Return true if the specified SDep is equivalent except for latency.
125 bool overlaps(const SDep &Other) const {
126 if (Dep != Other.Dep) return false;
127 switch (Dep.getInt()) {
131 return Contents.Reg == Other.Contents.Reg;
133 return Contents.OrdKind == Other.Contents.OrdKind;
135 llvm_unreachable("Invalid dependency kind!");
138 bool operator==(const SDep &Other) const {
139 return overlaps(Other) && Latency == Other.Latency;
142 bool operator!=(const SDep &Other) const {
143 return !operator==(Other);
146 /// getLatency - Return the latency value for this edge, which roughly
147 /// means the minimum number of cycles that must elapse between the
148 /// predecessor and the successor, given that they have this edge
150 unsigned getLatency() const {
154 /// setLatency - Set the latency for this edge.
155 void setLatency(unsigned Lat) {
159 //// getSUnit - Return the SUnit to which this edge points.
160 SUnit *getSUnit() const {
161 return Dep.getPointer();
164 //// setSUnit - Assign the SUnit to which this edge points.
165 void setSUnit(SUnit *SU) {
169 /// getKind - Return an enum value representing the kind of the dependence.
170 Kind getKind() const {
174 /// isCtrl - Shorthand for getKind() != SDep::Data.
175 bool isCtrl() const {
176 return getKind() != Data;
179 /// isNormalMemory - Test if this is an Order dependence between two
180 /// memory accesses where both sides of the dependence access memory
181 /// in non-volatile and fully modeled ways.
182 bool isNormalMemory() const {
183 return getKind() == Order && (Contents.OrdKind == MayAliasMem
184 || Contents.OrdKind == MustAliasMem);
187 /// isBarrier - Test if this is an Order dependence that is marked
189 bool isBarrier() const {
190 return getKind() == Order && Contents.OrdKind == Barrier;
193 /// isMustAlias - Test if this is an Order dependence that is marked
194 /// as "must alias", meaning that the SUnits at either end of the edge
195 /// have a memory dependence on a known memory location.
196 bool isMustAlias() const {
197 return getKind() == Order && Contents.OrdKind == MustAliasMem;
200 /// isWeak - Test if this a weak dependence. Weak dependencies are
201 /// considered DAG edges for height computation and other heuristics, but do
202 /// not force ordering. Breaking a weak edge may require the scheduler to
203 /// compensate, for example by inserting a copy.
204 bool isWeak() const {
205 return getKind() == Order && Contents.OrdKind >= Weak;
208 /// isArtificial - Test if this is an Order dependence that is marked
209 /// as "artificial", meaning it isn't necessary for correctness.
210 bool isArtificial() const {
211 return getKind() == Order && Contents.OrdKind == Artificial;
214 /// isCluster - Test if this is an Order dependence that is marked
215 /// as "cluster", meaning it is artificial and wants to be adjacent.
216 bool isCluster() const {
217 return getKind() == Order && Contents.OrdKind == Cluster;
220 /// isAssignedRegDep - Test if this is a Data dependence that is
221 /// associated with a register.
222 bool isAssignedRegDep() const {
223 return getKind() == Data && Contents.Reg != 0;
226 /// getReg - Return the register associated with this edge. This is
227 /// only valid on Data, Anti, and Output edges. On Data edges, this
228 /// value may be zero, meaning there is no associated register.
229 unsigned getReg() const {
230 assert((getKind() == Data || getKind() == Anti || getKind() == Output) &&
231 "getReg called on non-register dependence edge!");
235 /// setReg - Assign the associated register for this edge. This is
236 /// only valid on Data, Anti, and Output edges. On Anti and Output
237 /// edges, this value must not be zero. On Data edges, the value may
238 /// be zero, which would mean that no specific register is associated
240 void setReg(unsigned Reg) {
241 assert((getKind() == Data || getKind() == Anti || getKind() == Output) &&
242 "setReg called on non-register dependence edge!");
243 assert((getKind() != Anti || Reg != 0) &&
244 "SDep::Anti edge cannot use the zero register!");
245 assert((getKind() != Output || Reg != 0) &&
246 "SDep::Output edge cannot use the zero register!");
252 struct isPodLike<SDep> { static const bool value = true; };
254 /// SUnit - Scheduling unit. This is a node in the scheduling DAG.
257 enum : unsigned { BoundaryID = ~0u };
259 SDNode *Node; // Representative node.
260 MachineInstr *Instr; // Alternatively, a MachineInstr.
262 SUnit *OrigNode; // If not this, the node from which
263 // this node was cloned.
264 // (SD scheduling only)
266 const MCSchedClassDesc *SchedClass; // NULL or resolved SchedClass.
268 // Preds/Succs - The SUnits before/after us in the graph.
269 SmallVector<SDep, 4> Preds; // All sunit predecessors.
270 SmallVector<SDep, 4> Succs; // All sunit successors.
272 typedef SmallVectorImpl<SDep>::iterator pred_iterator;
273 typedef SmallVectorImpl<SDep>::iterator succ_iterator;
274 typedef SmallVectorImpl<SDep>::const_iterator const_pred_iterator;
275 typedef SmallVectorImpl<SDep>::const_iterator const_succ_iterator;
277 unsigned NodeNum; // Entry # of node in the node vector.
278 unsigned NodeQueueId; // Queue id of node.
279 unsigned NumPreds; // # of SDep::Data preds.
280 unsigned NumSuccs; // # of SDep::Data sucss.
281 unsigned NumPredsLeft; // # of preds not scheduled.
282 unsigned NumSuccsLeft; // # of succs not scheduled.
283 unsigned WeakPredsLeft; // # of weak preds not scheduled.
284 unsigned WeakSuccsLeft; // # of weak succs not scheduled.
285 unsigned short NumRegDefsLeft; // # of reg defs with no scheduled use.
286 unsigned short Latency; // Node latency.
287 bool isVRegCycle : 1; // May use and def the same vreg.
288 bool isCall : 1; // Is a function call.
289 bool isCallOp : 1; // Is a function call operand.
290 bool isTwoAddress : 1; // Is a two-address instruction.
291 bool isCommutable : 1; // Is a commutable instruction.
292 bool hasPhysRegUses : 1; // Has physreg uses.
293 bool hasPhysRegDefs : 1; // Has physreg defs that are being used.
294 bool hasPhysRegClobbers : 1; // Has any physreg defs, used or not.
295 bool isPending : 1; // True once pending.
296 bool isAvailable : 1; // True once available.
297 bool isScheduled : 1; // True once scheduled.
298 bool isScheduleHigh : 1; // True if preferable to schedule high.
299 bool isScheduleLow : 1; // True if preferable to schedule low.
300 bool isCloned : 1; // True if this node has been cloned.
301 bool isUnbuffered : 1; // Uses an unbuffered resource.
302 bool hasReservedResource : 1; // Uses a reserved resource.
303 Sched::Preference SchedulingPref; // Scheduling preference.
306 bool isDepthCurrent : 1; // True if Depth is current.
307 bool isHeightCurrent : 1; // True if Height is current.
308 unsigned Depth; // Node depth.
309 unsigned Height; // Node height.
311 unsigned TopReadyCycle; // Cycle relative to start when node is ready.
312 unsigned BotReadyCycle; // Cycle relative to end when node is ready.
314 const TargetRegisterClass *CopyDstRC; // Is a special copy node if not null.
315 const TargetRegisterClass *CopySrcRC;
317 /// SUnit - Construct an SUnit for pre-regalloc scheduling to represent
318 /// an SDNode and any nodes flagged to it.
319 SUnit(SDNode *node, unsigned nodenum)
320 : Node(node), Instr(0), OrigNode(0), SchedClass(0), NodeNum(nodenum),
321 NodeQueueId(0), NumPreds(0), NumSuccs(0), NumPredsLeft(0),
322 NumSuccsLeft(0), WeakPredsLeft(0), WeakSuccsLeft(0), NumRegDefsLeft(0),
323 Latency(0), isVRegCycle(false), isCall(false), isCallOp(false),
324 isTwoAddress(false), isCommutable(false), hasPhysRegUses(false),
325 hasPhysRegDefs(false), hasPhysRegClobbers(false), isPending(false),
326 isAvailable(false), isScheduled(false), isScheduleHigh(false),
327 isScheduleLow(false), isCloned(false), isUnbuffered(false),
328 hasReservedResource(false), SchedulingPref(Sched::None),
329 isDepthCurrent(false), isHeightCurrent(false), Depth(0), Height(0),
330 TopReadyCycle(0), BotReadyCycle(0), CopyDstRC(NULL), CopySrcRC(NULL) {}
332 /// SUnit - Construct an SUnit for post-regalloc scheduling to represent
334 SUnit(MachineInstr *instr, unsigned nodenum)
335 : Node(0), Instr(instr), OrigNode(0), SchedClass(0), NodeNum(nodenum),
336 NodeQueueId(0), NumPreds(0), NumSuccs(0), NumPredsLeft(0),
337 NumSuccsLeft(0), WeakPredsLeft(0), WeakSuccsLeft(0), NumRegDefsLeft(0),
338 Latency(0), isVRegCycle(false), isCall(false), isCallOp(false),
339 isTwoAddress(false), isCommutable(false), hasPhysRegUses(false),
340 hasPhysRegDefs(false), hasPhysRegClobbers(false), isPending(false),
341 isAvailable(false), isScheduled(false), isScheduleHigh(false),
342 isScheduleLow(false), isCloned(false), isUnbuffered(false),
343 hasReservedResource(false), SchedulingPref(Sched::None),
344 isDepthCurrent(false), isHeightCurrent(false), Depth(0), Height(0),
345 TopReadyCycle(0), BotReadyCycle(0), CopyDstRC(NULL), CopySrcRC(NULL) {}
347 /// SUnit - Construct a placeholder SUnit.
349 : Node(0), Instr(0), OrigNode(0), SchedClass(0), NodeNum(BoundaryID),
350 NodeQueueId(0), NumPreds(0), NumSuccs(0), NumPredsLeft(0),
351 NumSuccsLeft(0), WeakPredsLeft(0), WeakSuccsLeft(0), NumRegDefsLeft(0),
352 Latency(0), isVRegCycle(false), isCall(false), isCallOp(false),
353 isTwoAddress(false), isCommutable(false), hasPhysRegUses(false),
354 hasPhysRegDefs(false), hasPhysRegClobbers(false), isPending(false),
355 isAvailable(false), isScheduled(false), isScheduleHigh(false),
356 isScheduleLow(false), isCloned(false), isUnbuffered(false),
357 hasReservedResource(false), SchedulingPref(Sched::None),
358 isDepthCurrent(false), isHeightCurrent(false), Depth(0), Height(0),
359 TopReadyCycle(0), BotReadyCycle(0), CopyDstRC(NULL), CopySrcRC(NULL) {}
361 /// \brief Boundary nodes are placeholders for the boundary of the
362 /// scheduling region.
364 /// BoundaryNodes can have DAG edges, including Data edges, but they do not
365 /// correspond to schedulable entities (e.g. instructions) and do not have a
366 /// valid ID. Consequently, always check for boundary nodes before accessing
367 /// an assoicative data structure keyed on node ID.
368 bool isBoundaryNode() const { return NodeNum == BoundaryID; };
370 /// setNode - Assign the representative SDNode for this SUnit.
371 /// This may be used during pre-regalloc scheduling.
372 void setNode(SDNode *N) {
373 assert(!Instr && "Setting SDNode of SUnit with MachineInstr!");
377 /// getNode - Return the representative SDNode for this SUnit.
378 /// This may be used during pre-regalloc scheduling.
379 SDNode *getNode() const {
380 assert(!Instr && "Reading SDNode of SUnit with MachineInstr!");
384 /// isInstr - Return true if this SUnit refers to a machine instruction as
385 /// opposed to an SDNode.
386 bool isInstr() const { return Instr; }
388 /// setInstr - Assign the instruction for the SUnit.
389 /// This may be used during post-regalloc scheduling.
390 void setInstr(MachineInstr *MI) {
391 assert(!Node && "Setting MachineInstr of SUnit with SDNode!");
395 /// getInstr - Return the representative MachineInstr for this SUnit.
396 /// This may be used during post-regalloc scheduling.
397 MachineInstr *getInstr() const {
398 assert(!Node && "Reading MachineInstr of SUnit with SDNode!");
402 /// addPred - This adds the specified edge as a pred of the current node if
403 /// not already. It also adds the current node as a successor of the
405 bool addPred(const SDep &D, bool Required = true);
407 /// removePred - This removes the specified edge as a pred of the current
408 /// node if it exists. It also removes the current node as a successor of
409 /// the specified node.
410 void removePred(const SDep &D);
412 /// getDepth - Return the depth of this node, which is the length of the
413 /// maximum path up to any node which has no predecessors.
414 unsigned getDepth() const {
416 const_cast<SUnit *>(this)->ComputeDepth();
420 /// getHeight - Return the height of this node, which is the length of the
421 /// maximum path down to any node which has no successors.
422 unsigned getHeight() const {
423 if (!isHeightCurrent)
424 const_cast<SUnit *>(this)->ComputeHeight();
428 /// setDepthToAtLeast - If NewDepth is greater than this node's
429 /// depth value, set it to be the new depth value. This also
430 /// recursively marks successor nodes dirty.
431 void setDepthToAtLeast(unsigned NewDepth);
433 /// setDepthToAtLeast - If NewDepth is greater than this node's
434 /// depth value, set it to be the new height value. This also
435 /// recursively marks predecessor nodes dirty.
436 void setHeightToAtLeast(unsigned NewHeight);
438 /// setDepthDirty - Set a flag in this node to indicate that its
439 /// stored Depth value will require recomputation the next time
440 /// getDepth() is called.
441 void setDepthDirty();
443 /// setHeightDirty - Set a flag in this node to indicate that its
444 /// stored Height value will require recomputation the next time
445 /// getHeight() is called.
446 void setHeightDirty();
448 /// isPred - Test if node N is a predecessor of this node.
449 bool isPred(SUnit *N) {
450 for (unsigned i = 0, e = (unsigned)Preds.size(); i != e; ++i)
451 if (Preds[i].getSUnit() == N)
456 /// isSucc - Test if node N is a successor of this node.
457 bool isSucc(SUnit *N) {
458 for (unsigned i = 0, e = (unsigned)Succs.size(); i != e; ++i)
459 if (Succs[i].getSUnit() == N)
464 bool isTopReady() const {
465 return NumPredsLeft == 0;
467 bool isBottomReady() const {
468 return NumSuccsLeft == 0;
471 /// \brief Order this node's predecessor edges such that the critical path
472 /// edge occurs first.
473 void biasCriticalPath();
475 void dump(const ScheduleDAG *G) const;
476 void dumpAll(const ScheduleDAG *G) const;
477 void print(raw_ostream &O, const ScheduleDAG *G) const;
481 void ComputeHeight();
484 //===--------------------------------------------------------------------===//
485 /// SchedulingPriorityQueue - This interface is used to plug different
486 /// priorities computation algorithms into the list scheduler. It implements
487 /// the interface of a standard priority queue, where nodes are inserted in
488 /// arbitrary order and returned in priority order. The computation of the
489 /// priority and the representation of the queue are totally up to the
490 /// implementation to decide.
492 class SchedulingPriorityQueue {
493 virtual void anchor();
497 SchedulingPriorityQueue(bool rf = false):
498 CurCycle(0), HasReadyFilter(rf) {}
499 virtual ~SchedulingPriorityQueue() {}
501 virtual bool isBottomUp() const = 0;
503 virtual void initNodes(std::vector<SUnit> &SUnits) = 0;
504 virtual void addNode(const SUnit *SU) = 0;
505 virtual void updateNode(const SUnit *SU) = 0;
506 virtual void releaseState() = 0;
508 virtual bool empty() const = 0;
510 bool hasReadyFilter() const { return HasReadyFilter; }
512 virtual bool tracksRegPressure() const { return false; }
514 virtual bool isReady(SUnit *) const {
515 assert(!HasReadyFilter && "The ready filter must override isReady()");
518 virtual void push(SUnit *U) = 0;
520 void push_all(const std::vector<SUnit *> &Nodes) {
521 for (std::vector<SUnit *>::const_iterator I = Nodes.begin(),
522 E = Nodes.end(); I != E; ++I)
526 virtual SUnit *pop() = 0;
528 virtual void remove(SUnit *SU) = 0;
530 virtual void dump(ScheduleDAG *) const {}
532 /// scheduledNode - As each node is scheduled, this method is invoked. This
533 /// allows the priority function to adjust the priority of related
534 /// unscheduled nodes, for example.
536 virtual void scheduledNode(SUnit *) {}
538 virtual void unscheduledNode(SUnit *) {}
540 void setCurCycle(unsigned Cycle) {
544 unsigned getCurCycle() const {
551 const TargetMachine &TM; // Target processor
552 const TargetInstrInfo *TII; // Target instruction information
553 const TargetRegisterInfo *TRI; // Target processor register info
554 MachineFunction &MF; // Machine function
555 MachineRegisterInfo &MRI; // Virtual/real register map
556 std::vector<SUnit> SUnits; // The scheduling units.
557 SUnit EntrySU; // Special node for the region entry.
558 SUnit ExitSU; // Special node for the region exit.
561 static const bool StressSched = false;
566 explicit ScheduleDAG(MachineFunction &mf);
568 virtual ~ScheduleDAG();
570 /// clearDAG - clear the DAG state (between regions).
573 /// getInstrDesc - Return the MCInstrDesc of this SUnit.
574 /// Return NULL for SDNodes without a machine opcode.
575 const MCInstrDesc *getInstrDesc(const SUnit *SU) const {
576 if (SU->isInstr()) return &SU->getInstr()->getDesc();
577 return getNodeDesc(SU->getNode());
580 /// viewGraph - Pop up a GraphViz/gv window with the ScheduleDAG rendered
583 virtual void viewGraph(const Twine &Name, const Twine &Title);
584 virtual void viewGraph();
586 virtual void dumpNode(const SUnit *SU) const = 0;
588 /// getGraphNodeLabel - Return a label for an SUnit node in a visualization
589 /// of the ScheduleDAG.
590 virtual std::string getGraphNodeLabel(const SUnit *SU) const = 0;
592 /// getDAGLabel - Return a label for the region of code covered by the DAG.
593 virtual std::string getDAGName() const = 0;
595 /// addCustomGraphFeatures - Add custom features for a visualization of
597 virtual void addCustomGraphFeatures(GraphWriter<ScheduleDAG*> &) const {}
600 /// VerifyScheduledDAG - Verify that all SUnits were scheduled and that
601 /// their state is consistent. Return the number of scheduled SUnits.
602 unsigned VerifyScheduledDAG(bool isBottomUp);
606 // Return the MCInstrDesc of this SDNode or NULL.
607 const MCInstrDesc *getNodeDesc(const SDNode *Node) const;
610 class SUnitIterator : public std::iterator<std::forward_iterator_tag,
615 SUnitIterator(SUnit *N, unsigned Op) : Node(N), Operand(Op) {}
617 bool operator==(const SUnitIterator& x) const {
618 return Operand == x.Operand;
620 bool operator!=(const SUnitIterator& x) const { return !operator==(x); }
622 const SUnitIterator &operator=(const SUnitIterator &I) {
623 assert(I.Node==Node && "Cannot assign iterators to two different nodes!");
628 pointer operator*() const {
629 return Node->Preds[Operand].getSUnit();
631 pointer operator->() const { return operator*(); }
633 SUnitIterator& operator++() { // Preincrement
637 SUnitIterator operator++(int) { // Postincrement
638 SUnitIterator tmp = *this; ++*this; return tmp;
641 static SUnitIterator begin(SUnit *N) { return SUnitIterator(N, 0); }
642 static SUnitIterator end (SUnit *N) {
643 return SUnitIterator(N, (unsigned)N->Preds.size());
646 unsigned getOperand() const { return Operand; }
647 const SUnit *getNode() const { return Node; }
648 /// isCtrlDep - Test if this is not an SDep::Data dependence.
649 bool isCtrlDep() const {
650 return getSDep().isCtrl();
652 bool isArtificialDep() const {
653 return getSDep().isArtificial();
655 const SDep &getSDep() const {
656 return Node->Preds[Operand];
660 template <> struct GraphTraits<SUnit*> {
661 typedef SUnit NodeType;
662 typedef SUnitIterator ChildIteratorType;
663 static inline NodeType *getEntryNode(SUnit *N) { return N; }
664 static inline ChildIteratorType child_begin(NodeType *N) {
665 return SUnitIterator::begin(N);
667 static inline ChildIteratorType child_end(NodeType *N) {
668 return SUnitIterator::end(N);
672 template <> struct GraphTraits<ScheduleDAG*> : public GraphTraits<SUnit*> {
673 typedef std::vector<SUnit>::iterator nodes_iterator;
674 static nodes_iterator nodes_begin(ScheduleDAG *G) {
675 return G->SUnits.begin();
677 static nodes_iterator nodes_end(ScheduleDAG *G) {
678 return G->SUnits.end();
682 /// ScheduleDAGTopologicalSort is a class that computes a topological
683 /// ordering for SUnits and provides methods for dynamically updating
684 /// the ordering as new edges are added.
686 /// This allows a very fast implementation of IsReachable, for example.
688 class ScheduleDAGTopologicalSort {
689 /// SUnits - A reference to the ScheduleDAG's SUnits.
690 std::vector<SUnit> &SUnits;
693 /// Index2Node - Maps topological index to the node number.
694 std::vector<int> Index2Node;
695 /// Node2Index - Maps the node number to its topological index.
696 std::vector<int> Node2Index;
697 /// Visited - a set of nodes visited during a DFS traversal.
700 /// DFS - make a DFS traversal and mark all nodes affected by the
701 /// edge insertion. These nodes will later get new topological indexes
702 /// by means of the Shift method.
703 void DFS(const SUnit *SU, int UpperBound, bool& HasLoop);
705 /// Shift - reassign topological indexes for the nodes in the DAG
706 /// to preserve the topological ordering.
707 void Shift(BitVector& Visited, int LowerBound, int UpperBound);
709 /// Allocate - assign the topological index to the node n.
710 void Allocate(int n, int index);
713 ScheduleDAGTopologicalSort(std::vector<SUnit> &SUnits, SUnit *ExitSU);
715 /// InitDAGTopologicalSorting - create the initial topological
716 /// ordering from the DAG to be scheduled.
717 void InitDAGTopologicalSorting();
719 /// IsReachable - Checks if SU is reachable from TargetSU.
720 bool IsReachable(const SUnit *SU, const SUnit *TargetSU);
722 /// WillCreateCycle - Return true if addPred(TargetSU, SU) creates a cycle.
723 bool WillCreateCycle(SUnit *TargetSU, SUnit *SU);
725 /// AddPred - Updates the topological ordering to accommodate an edge
726 /// to be added from SUnit X to SUnit Y.
727 void AddPred(SUnit *Y, SUnit *X);
729 /// RemovePred - Updates the topological ordering to accommodate an
730 /// an edge to be removed from the specified node N from the predecessors
731 /// of the current node M.
732 void RemovePred(SUnit *M, SUnit *N);
734 typedef std::vector<int>::iterator iterator;
735 typedef std::vector<int>::const_iterator const_iterator;
736 iterator begin() { return Index2Node.begin(); }
737 const_iterator begin() const { return Index2Node.begin(); }
738 iterator end() { return Index2Node.end(); }
739 const_iterator end() const { return Index2Node.end(); }
741 typedef std::vector<int>::reverse_iterator reverse_iterator;
742 typedef std::vector<int>::const_reverse_iterator const_reverse_iterator;
743 reverse_iterator rbegin() { return Index2Node.rbegin(); }
744 const_reverse_iterator rbegin() const { return Index2Node.rbegin(); }
745 reverse_iterator rend() { return Index2Node.rend(); }
746 const_reverse_iterator rend() const { return Index2Node.rend(); }