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/Analysis/AliasAnalysis.h"
24 #include "llvm/CodeGen/MachineInstr.h"
25 #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(nullptr, 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;
127 bool operator==(const SDep &Other) const {
128 return overlaps(Other) && Latency == Other.Latency;
131 bool operator!=(const SDep &Other) const {
132 return !operator==(Other);
135 /// getLatency - Return the latency value for this edge, which roughly
136 /// means the minimum number of cycles that must elapse between the
137 /// predecessor and the successor, given that they have this edge
139 unsigned getLatency() const {
143 /// setLatency - Set the latency for this edge.
144 void setLatency(unsigned Lat) {
148 //// getSUnit - Return the SUnit to which this edge points.
149 SUnit *getSUnit() const;
151 //// setSUnit - Assign the SUnit to which this edge points.
152 void setSUnit(SUnit *SU);
154 /// getKind - Return an enum value representing the kind of the dependence.
155 Kind getKind() const;
157 /// isCtrl - Shorthand for getKind() != SDep::Data.
158 bool isCtrl() const {
159 return getKind() != Data;
162 /// isNormalMemory - Test if this is an Order dependence between two
163 /// memory accesses where both sides of the dependence access memory
164 /// in non-volatile and fully modeled ways.
165 bool isNormalMemory() const {
166 return getKind() == Order && (Contents.OrdKind == MayAliasMem
167 || Contents.OrdKind == MustAliasMem);
170 /// isBarrier - Test if this is an Order dependence that is marked
172 bool isBarrier() const {
173 return getKind() == Order && Contents.OrdKind == Barrier;
176 /// isNormalMemoryOrBarrier - Test if this is could be any kind of memory
178 bool isNormalMemoryOrBarrier() const {
179 return (isNormalMemory() || isBarrier());
182 /// isMustAlias - Test if this is an Order dependence that is marked
183 /// as "must alias", meaning that the SUnits at either end of the edge
184 /// have a memory dependence on a known memory location.
185 bool isMustAlias() const {
186 return getKind() == Order && Contents.OrdKind == MustAliasMem;
189 /// isWeak - Test if this a weak dependence. Weak dependencies are
190 /// considered DAG edges for height computation and other heuristics, but do
191 /// not force ordering. Breaking a weak edge may require the scheduler to
192 /// compensate, for example by inserting a copy.
193 bool isWeak() const {
194 return getKind() == Order && Contents.OrdKind >= Weak;
197 /// isArtificial - Test if this is an Order dependence that is marked
198 /// as "artificial", meaning it isn't necessary for correctness.
199 bool isArtificial() const {
200 return getKind() == Order && Contents.OrdKind == Artificial;
203 /// isCluster - Test if this is an Order dependence that is marked
204 /// as "cluster", meaning it is artificial and wants to be adjacent.
205 bool isCluster() const {
206 return getKind() == Order && Contents.OrdKind == Cluster;
209 /// isAssignedRegDep - Test if this is a Data dependence that is
210 /// associated with a register.
211 bool isAssignedRegDep() const {
212 return getKind() == Data && Contents.Reg != 0;
215 /// getReg - Return the register associated with this edge. This is
216 /// only valid on Data, Anti, and Output edges. On Data edges, this
217 /// value may be zero, meaning there is no associated register.
218 unsigned getReg() const {
219 assert((getKind() == Data || getKind() == Anti || getKind() == Output) &&
220 "getReg called on non-register dependence edge!");
224 /// setReg - Assign the associated register for this edge. This is
225 /// only valid on Data, Anti, and Output edges. On Anti and Output
226 /// edges, this value must not be zero. On Data edges, the value may
227 /// be zero, which would mean that no specific register is associated
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 /// SUnit - Scheduling unit. This is a node in the scheduling DAG.
246 enum : unsigned { BoundaryID = ~0u };
248 SDNode *Node; // Representative node.
249 MachineInstr *Instr; // Alternatively, a MachineInstr.
251 SUnit *OrigNode; // If not this, the node from which
252 // this node was cloned.
253 // (SD scheduling only)
255 const MCSchedClassDesc *SchedClass; // NULL or resolved SchedClass.
257 // Preds/Succs - The SUnits before/after us in the graph.
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; // Entry # of node in the node vector.
267 unsigned NodeQueueId; // Queue id of node.
268 unsigned NumPreds; // # of SDep::Data preds.
269 unsigned NumSuccs; // # of SDep::Data sucss.
270 unsigned NumPredsLeft; // # of preds not scheduled.
271 unsigned NumSuccsLeft; // # of succs not scheduled.
272 unsigned WeakPredsLeft; // # of weak preds not scheduled.
273 unsigned WeakSuccsLeft; // # of weak succs not scheduled.
274 unsigned short NumRegDefsLeft; // # of reg defs with no scheduled use.
275 unsigned short Latency; // 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; // Scheduling preference.
295 bool isDepthCurrent : 1; // True if Depth is current.
296 bool isHeightCurrent : 1; // True if Height is current.
297 unsigned Depth; // Node depth.
298 unsigned Height; // Node height.
300 unsigned TopReadyCycle; // Cycle relative to start when node is ready.
301 unsigned BotReadyCycle; // Cycle relative to end when node is ready.
303 const TargetRegisterClass *CopyDstRC; // Is a special copy node if not null.
304 const TargetRegisterClass *CopySrcRC;
306 /// SUnit - Construct an SUnit for pre-regalloc scheduling to represent
307 /// an SDNode and any nodes flagged to it.
308 SUnit(SDNode *node, unsigned nodenum)
309 : Node(node), Instr(nullptr), OrigNode(nullptr), SchedClass(nullptr),
310 NodeNum(nodenum), NodeQueueId(0), NumPreds(0), NumSuccs(0),
311 NumPredsLeft(0), NumSuccsLeft(0), WeakPredsLeft(0), WeakSuccsLeft(0),
312 NumRegDefsLeft(0), Latency(0), isVRegCycle(false), isCall(false),
313 isCallOp(false), isTwoAddress(false), isCommutable(false),
314 hasPhysRegUses(false), hasPhysRegDefs(false), hasPhysRegClobbers(false),
315 isPending(false), isAvailable(false), isScheduled(false),
316 isScheduleHigh(false), isScheduleLow(false), isCloned(false),
317 isUnbuffered(false), hasReservedResource(false),
318 SchedulingPref(Sched::None), isDepthCurrent(false),
319 isHeightCurrent(false), Depth(0), Height(0), TopReadyCycle(0),
320 BotReadyCycle(0), CopyDstRC(nullptr), CopySrcRC(nullptr) {}
322 /// SUnit - Construct an SUnit for post-regalloc scheduling to represent
324 SUnit(MachineInstr *instr, unsigned nodenum)
325 : Node(nullptr), Instr(instr), OrigNode(nullptr), SchedClass(nullptr),
326 NodeNum(nodenum), NodeQueueId(0), NumPreds(0), NumSuccs(0),
327 NumPredsLeft(0), NumSuccsLeft(0), WeakPredsLeft(0), WeakSuccsLeft(0),
328 NumRegDefsLeft(0), Latency(0), isVRegCycle(false), isCall(false),
329 isCallOp(false), isTwoAddress(false), isCommutable(false),
330 hasPhysRegUses(false), hasPhysRegDefs(false), hasPhysRegClobbers(false),
331 isPending(false), isAvailable(false), isScheduled(false),
332 isScheduleHigh(false), isScheduleLow(false), isCloned(false),
333 isUnbuffered(false), hasReservedResource(false),
334 SchedulingPref(Sched::None), isDepthCurrent(false),
335 isHeightCurrent(false), Depth(0), Height(0), TopReadyCycle(0),
336 BotReadyCycle(0), CopyDstRC(nullptr), CopySrcRC(nullptr) {}
338 /// SUnit - Construct a placeholder SUnit.
340 : Node(nullptr), Instr(nullptr), OrigNode(nullptr), SchedClass(nullptr),
341 NodeNum(BoundaryID), NodeQueueId(0), NumPreds(0), NumSuccs(0),
342 NumPredsLeft(0), NumSuccsLeft(0), WeakPredsLeft(0), WeakSuccsLeft(0),
343 NumRegDefsLeft(0), Latency(0), isVRegCycle(false), isCall(false),
344 isCallOp(false), isTwoAddress(false), isCommutable(false),
345 hasPhysRegUses(false), hasPhysRegDefs(false), hasPhysRegClobbers(false),
346 isPending(false), isAvailable(false), isScheduled(false),
347 isScheduleHigh(false), isScheduleLow(false), isCloned(false),
348 isUnbuffered(false), hasReservedResource(false),
349 SchedulingPref(Sched::None), isDepthCurrent(false),
350 isHeightCurrent(false), Depth(0), Height(0), TopReadyCycle(0),
351 BotReadyCycle(0), CopyDstRC(nullptr), CopySrcRC(nullptr) {}
353 /// \brief Boundary nodes are placeholders for the boundary of the
354 /// scheduling region.
356 /// BoundaryNodes can have DAG edges, including Data edges, but they do not
357 /// correspond to schedulable entities (e.g. instructions) and do not have a
358 /// valid ID. Consequently, always check for boundary nodes before accessing
359 /// an assoicative data structure keyed on node ID.
360 bool isBoundaryNode() const { return NodeNum == BoundaryID; }
362 /// setNode - Assign the representative SDNode for this SUnit.
363 /// This may be used during pre-regalloc scheduling.
364 void setNode(SDNode *N) {
365 assert(!Instr && "Setting SDNode of SUnit with MachineInstr!");
369 /// getNode - Return the representative SDNode for this SUnit.
370 /// This may be used during pre-regalloc scheduling.
371 SDNode *getNode() const {
372 assert(!Instr && "Reading SDNode of SUnit with MachineInstr!");
376 /// isInstr - Return true if this SUnit refers to a machine instruction as
377 /// opposed to an SDNode.
378 bool isInstr() const { return Instr; }
380 /// setInstr - Assign the instruction for the SUnit.
381 /// This may be used during post-regalloc scheduling.
382 void setInstr(MachineInstr *MI) {
383 assert(!Node && "Setting MachineInstr of SUnit with SDNode!");
387 /// getInstr - Return the representative MachineInstr for this SUnit.
388 /// This may be used during post-regalloc scheduling.
389 MachineInstr *getInstr() const {
390 assert(!Node && "Reading MachineInstr of SUnit with SDNode!");
394 /// addPred - This adds the specified edge as a pred of the current node if
395 /// not already. It also adds the current node as a successor of the
397 bool addPred(const SDep &D, bool Required = true);
399 /// addPredBarrier - This adds a barrier edge to SU by calling
400 /// addPred(), with latency 0 generally or latency 1 for a store
401 /// followed by a load.
402 bool addPredBarrier(SUnit *SU) {
403 SDep Dep(SU, SDep::Barrier);
404 unsigned TrueMemOrderLatency =
405 ((SU->getInstr()->mayStore() && this->getInstr()->mayLoad()) ? 1 : 0);
406 Dep.setLatency(TrueMemOrderLatency);
410 /// removePred - This removes the specified edge as a pred of the current
411 /// node if it exists. It also removes the current node as a successor of
412 /// the specified node.
413 void removePred(const SDep &D);
415 /// getDepth - Return the depth of this node, which is the length of the
416 /// maximum path up to any node which has no predecessors.
417 unsigned getDepth() const {
419 const_cast<SUnit *>(this)->ComputeDepth();
423 /// getHeight - Return the height of this node, which is the length of the
424 /// maximum path down to any node which has no successors.
425 unsigned getHeight() const {
426 if (!isHeightCurrent)
427 const_cast<SUnit *>(this)->ComputeHeight();
431 /// setDepthToAtLeast - If NewDepth is greater than this node's
432 /// depth value, set it to be the new depth value. This also
433 /// recursively marks successor nodes dirty.
434 void setDepthToAtLeast(unsigned NewDepth);
436 /// setDepthToAtLeast - If NewDepth is greater than this node's
437 /// depth value, set it to be the new height value. This also
438 /// recursively marks predecessor nodes dirty.
439 void setHeightToAtLeast(unsigned NewHeight);
441 /// setDepthDirty - Set a flag in this node to indicate that its
442 /// stored Depth value will require recomputation the next time
443 /// getDepth() is called.
444 void setDepthDirty();
446 /// setHeightDirty - Set a flag in this node to indicate that its
447 /// stored Height value will require recomputation the next time
448 /// getHeight() is called.
449 void setHeightDirty();
451 /// isPred - Test if node N is a predecessor of this node.
452 bool isPred(SUnit *N) {
453 for (unsigned i = 0, e = (unsigned)Preds.size(); i != e; ++i)
454 if (Preds[i].getSUnit() == N)
459 /// isSucc - Test if node N is a successor of this node.
460 bool isSucc(SUnit *N) {
461 for (unsigned i = 0, e = (unsigned)Succs.size(); i != e; ++i)
462 if (Succs[i].getSUnit() == N)
467 bool isTopReady() const {
468 return NumPredsLeft == 0;
470 bool isBottomReady() const {
471 return NumSuccsLeft == 0;
474 /// \brief Order this node's predecessor edges such that the critical path
475 /// edge occurs first.
476 void biasCriticalPath();
478 void dump(const ScheduleDAG *G) const;
479 void dumpAll(const ScheduleDAG *G) const;
480 void print(raw_ostream &O, const ScheduleDAG *G) const;
484 void ComputeHeight();
487 /// Return true if the specified SDep is equivalent except for latency.
488 inline bool SDep::overlaps(const SDep &Other) const {
489 if (Dep != Other.Dep)
491 switch (Dep.getInt()) {
495 return Contents.Reg == Other.Contents.Reg;
497 return Contents.OrdKind == Other.Contents.OrdKind;
499 llvm_unreachable("Invalid dependency kind!");
502 //// getSUnit - Return the SUnit to which this edge points.
503 inline SUnit *SDep::getSUnit() const { return Dep.getPointer(); }
505 //// setSUnit - Assign the SUnit to which this edge points.
506 inline void SDep::setSUnit(SUnit *SU) { Dep.setPointer(SU); }
508 /// getKind - Return an enum value representing the kind of the dependence.
509 inline SDep::Kind SDep::getKind() const { return Dep.getInt(); }
511 //===--------------------------------------------------------------------===//
512 /// SchedulingPriorityQueue - This interface is used to plug different
513 /// priorities computation algorithms into the list scheduler. It implements
514 /// the interface of a standard priority queue, where nodes are inserted in
515 /// arbitrary order and returned in priority order. The computation of the
516 /// priority and the representation of the queue are totally up to the
517 /// implementation to decide.
519 class SchedulingPriorityQueue {
520 virtual void anchor();
524 SchedulingPriorityQueue(bool rf = false):
525 CurCycle(0), HasReadyFilter(rf) {}
526 virtual ~SchedulingPriorityQueue() {}
528 virtual bool isBottomUp() const = 0;
530 virtual void initNodes(std::vector<SUnit> &SUnits) = 0;
531 virtual void addNode(const SUnit *SU) = 0;
532 virtual void updateNode(const SUnit *SU) = 0;
533 virtual void releaseState() = 0;
535 virtual bool empty() const = 0;
537 bool hasReadyFilter() const { return HasReadyFilter; }
539 virtual bool tracksRegPressure() const { return false; }
541 virtual bool isReady(SUnit *) const {
542 assert(!HasReadyFilter && "The ready filter must override isReady()");
545 virtual void push(SUnit *U) = 0;
547 void push_all(const std::vector<SUnit *> &Nodes) {
548 for (std::vector<SUnit *>::const_iterator I = Nodes.begin(),
549 E = Nodes.end(); I != E; ++I)
553 virtual SUnit *pop() = 0;
555 virtual void remove(SUnit *SU) = 0;
557 virtual void dump(ScheduleDAG *) const {}
559 /// scheduledNode - As each node is scheduled, this method is invoked. This
560 /// allows the priority function to adjust the priority of related
561 /// unscheduled nodes, for example.
563 virtual void scheduledNode(SUnit *) {}
565 virtual void unscheduledNode(SUnit *) {}
567 void setCurCycle(unsigned Cycle) {
571 unsigned getCurCycle() const {
578 const TargetMachine &TM; // Target processor
579 const TargetInstrInfo *TII; // Target instruction information
580 const TargetRegisterInfo *TRI; // Target processor register info
581 MachineFunction &MF; // Machine function
582 MachineRegisterInfo &MRI; // Virtual/real register map
583 std::vector<SUnit> SUnits; // The scheduling units.
584 SUnit EntrySU; // Special node for the region entry.
585 SUnit ExitSU; // Special node for the region exit.
588 static const bool StressSched = false;
593 explicit ScheduleDAG(MachineFunction &mf);
595 virtual ~ScheduleDAG();
597 /// clearDAG - clear the DAG state (between regions).
600 /// getInstrDesc - Return the MCInstrDesc of this SUnit.
601 /// Return NULL for SDNodes without a machine opcode.
602 const MCInstrDesc *getInstrDesc(const SUnit *SU) const {
603 if (SU->isInstr()) return &SU->getInstr()->getDesc();
604 return getNodeDesc(SU->getNode());
607 /// viewGraph - Pop up a GraphViz/gv window with the ScheduleDAG rendered
610 virtual void viewGraph(const Twine &Name, const Twine &Title);
611 virtual void viewGraph();
613 virtual void dumpNode(const SUnit *SU) const = 0;
615 /// getGraphNodeLabel - Return a label for an SUnit node in a visualization
616 /// of the ScheduleDAG.
617 virtual std::string getGraphNodeLabel(const SUnit *SU) const = 0;
619 /// getDAGLabel - Return a label for the region of code covered by the DAG.
620 virtual std::string getDAGName() const = 0;
622 /// addCustomGraphFeatures - Add custom features for a visualization of
624 virtual void addCustomGraphFeatures(GraphWriter<ScheduleDAG*> &) const {}
627 /// VerifyScheduledDAG - Verify that all SUnits were scheduled and that
628 /// their state is consistent. Return the number of scheduled SUnits.
629 unsigned VerifyScheduledDAG(bool isBottomUp);
633 // Return the MCInstrDesc of this SDNode or NULL.
634 const MCInstrDesc *getNodeDesc(const SDNode *Node) const;
637 class SUnitIterator : public std::iterator<std::forward_iterator_tag,
642 SUnitIterator(SUnit *N, unsigned Op) : Node(N), Operand(Op) {}
644 bool operator==(const SUnitIterator& x) const {
645 return Operand == x.Operand;
647 bool operator!=(const SUnitIterator& x) const { return !operator==(x); }
649 pointer operator*() const {
650 return Node->Preds[Operand].getSUnit();
652 pointer operator->() const { return operator*(); }
654 SUnitIterator& operator++() { // Preincrement
658 SUnitIterator operator++(int) { // Postincrement
659 SUnitIterator tmp = *this; ++*this; return tmp;
662 static SUnitIterator begin(SUnit *N) { return SUnitIterator(N, 0); }
663 static SUnitIterator end (SUnit *N) {
664 return SUnitIterator(N, (unsigned)N->Preds.size());
667 unsigned getOperand() const { return Operand; }
668 const SUnit *getNode() const { return Node; }
669 /// isCtrlDep - Test if this is not an SDep::Data dependence.
670 bool isCtrlDep() const {
671 return getSDep().isCtrl();
673 bool isArtificialDep() const {
674 return getSDep().isArtificial();
676 const SDep &getSDep() const {
677 return Node->Preds[Operand];
681 template <> struct GraphTraits<SUnit*> {
682 typedef SUnit *NodeRef;
683 typedef SUnitIterator ChildIteratorType;
684 static NodeRef getEntryNode(SUnit *N) { return N; }
685 static ChildIteratorType child_begin(NodeRef N) {
686 return SUnitIterator::begin(N);
688 static ChildIteratorType child_end(NodeRef N) {
689 return SUnitIterator::end(N);
693 template <> struct GraphTraits<ScheduleDAG*> : public GraphTraits<SUnit*> {
694 typedef pointer_iterator<std::vector<SUnit>::iterator> nodes_iterator;
695 static nodes_iterator nodes_begin(ScheduleDAG *G) {
696 return nodes_iterator(G->SUnits.begin());
698 static nodes_iterator nodes_end(ScheduleDAG *G) {
699 return nodes_iterator(G->SUnits.end());
703 /// ScheduleDAGTopologicalSort is a class that computes a topological
704 /// ordering for SUnits and provides methods for dynamically updating
705 /// the ordering as new edges are added.
707 /// This allows a very fast implementation of IsReachable, for example.
709 class ScheduleDAGTopologicalSort {
710 /// SUnits - A reference to the ScheduleDAG's SUnits.
711 std::vector<SUnit> &SUnits;
714 /// Index2Node - Maps topological index to the node number.
715 std::vector<int> Index2Node;
716 /// Node2Index - Maps the node number to its topological index.
717 std::vector<int> Node2Index;
718 /// Visited - a set of nodes visited during a DFS traversal.
721 /// DFS - make a DFS traversal and mark all nodes affected by the
722 /// edge insertion. These nodes will later get new topological indexes
723 /// by means of the Shift method.
724 void DFS(const SUnit *SU, int UpperBound, bool& HasLoop);
726 /// Shift - reassign topological indexes for the nodes in the DAG
727 /// to preserve the topological ordering.
728 void Shift(BitVector& Visited, int LowerBound, int UpperBound);
730 /// Allocate - assign the topological index to the node n.
731 void Allocate(int n, int index);
734 ScheduleDAGTopologicalSort(std::vector<SUnit> &SUnits, SUnit *ExitSU);
736 /// InitDAGTopologicalSorting - create the initial topological
737 /// ordering from the DAG to be scheduled.
738 void InitDAGTopologicalSorting();
740 /// IsReachable - Checks if SU is reachable from TargetSU.
741 bool IsReachable(const SUnit *SU, const SUnit *TargetSU);
743 /// WillCreateCycle - Return true if addPred(TargetSU, SU) creates a cycle.
744 bool WillCreateCycle(SUnit *TargetSU, SUnit *SU);
746 /// AddPred - Updates the topological ordering to accommodate an edge
747 /// to be added from SUnit X to SUnit Y.
748 void AddPred(SUnit *Y, SUnit *X);
750 /// RemovePred - Updates the topological ordering to accommodate an
751 /// an edge to be removed from the specified node N from the predecessors
752 /// of the current node M.
753 void RemovePred(SUnit *M, SUnit *N);
755 typedef std::vector<int>::iterator iterator;
756 typedef std::vector<int>::const_iterator const_iterator;
757 iterator begin() { return Index2Node.begin(); }
758 const_iterator begin() const { return Index2Node.begin(); }
759 iterator end() { return Index2Node.end(); }
760 const_iterator end() const { return Index2Node.end(); }
762 typedef std::vector<int>::reverse_iterator reverse_iterator;
763 typedef std::vector<int>::const_reverse_iterator const_reverse_iterator;
764 reverse_iterator rbegin() { return Index2Node.rbegin(); }
765 const_reverse_iterator rbegin() const { return Index2Node.rbegin(); }
766 reverse_iterator rend() { return Index2Node.rend(); }
767 const_reverse_iterator rend() const { return Index2Node.rend(); }