xref: /freebsd/contrib/llvm-project/llvm/include/llvm/CodeGen/ScheduleDAG.h (revision b59017c5cad90d0f09a59e68c00457b7faf93e7c)
1 //===- llvm/CodeGen/ScheduleDAG.h - Common Base Class -----------*- C++ -*-===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 /// \file Implements the ScheduleDAG class, which is used as the common base
10 /// class for instruction schedulers. This encapsulates the scheduling DAG,
11 /// which is shared between SelectionDAG and MachineInstr scheduling.
12 //
13 //===----------------------------------------------------------------------===//
14 
15 #ifndef LLVM_CODEGEN_SCHEDULEDAG_H
16 #define LLVM_CODEGEN_SCHEDULEDAG_H
17 
18 #include "llvm/ADT/BitVector.h"
19 #include "llvm/ADT/PointerIntPair.h"
20 #include "llvm/ADT/SmallVector.h"
21 #include "llvm/ADT/iterator.h"
22 #include "llvm/CodeGen/MachineInstr.h"
23 #include "llvm/CodeGen/TargetLowering.h"
24 #include "llvm/Support/ErrorHandling.h"
25 #include <cassert>
26 #include <cstddef>
27 #include <iterator>
28 #include <string>
29 #include <vector>
30 
31 namespace llvm {
32 
33 template <class GraphType> struct GraphTraits;
34 template<class Graph> class GraphWriter;
35 class LLVMTargetMachine;
36 class MachineFunction;
37 class MachineRegisterInfo;
38 class MCInstrDesc;
39 struct MCSchedClassDesc;
40 class SDNode;
41 class SUnit;
42 class ScheduleDAG;
43 class TargetInstrInfo;
44 class TargetRegisterClass;
45 class TargetRegisterInfo;
46 
47   /// Scheduling dependency. This represents one direction of an edge in the
48   /// scheduling DAG.
49   class SDep {
50   public:
51     /// These are the different kinds of scheduling dependencies.
52     enum Kind {
53       Data,        ///< Regular data dependence (aka true-dependence).
54       Anti,        ///< A register anti-dependence (aka WAR).
55       Output,      ///< A register output-dependence (aka WAW).
56       Order        ///< Any other ordering dependency.
57     };
58 
59     // Strong dependencies must be respected by the scheduler. Artificial
60     // dependencies may be removed only if they are redundant with another
61     // strong dependence.
62     //
63     // Weak dependencies may be violated by the scheduling strategy, but only if
64     // the strategy can prove it is correct to do so.
65     //
66     // Strong OrderKinds must occur before "Weak".
67     // Weak OrderKinds must occur after "Weak".
68     enum OrderKind {
69       Barrier,      ///< An unknown scheduling barrier.
70       MayAliasMem,  ///< Nonvolatile load/Store instructions that may alias.
71       MustAliasMem, ///< Nonvolatile load/Store instructions that must alias.
72       Artificial,   ///< Arbitrary strong DAG edge (no real dependence).
73       Weak,         ///< Arbitrary weak DAG edge.
74       Cluster       ///< Weak DAG edge linking a chain of clustered instrs.
75     };
76 
77   private:
78     /// A pointer to the depending/depended-on SUnit, and an enum
79     /// indicating the kind of the dependency.
80     PointerIntPair<SUnit *, 2, Kind> Dep;
81 
82     /// A union discriminated by the dependence kind.
83     union {
84       /// For Data, Anti, and Output dependencies, the associated register. For
85       /// Data dependencies that don't currently have a register/ assigned, this
86       /// is set to zero.
87       unsigned Reg;
88 
89       /// Additional information about Order dependencies.
90       unsigned OrdKind; // enum OrderKind
91     } Contents;
92 
93     /// The time associated with this edge. Often this is just the value of the
94     /// Latency field of the predecessor, however advanced models may provide
95     /// additional information about specific edges.
96     unsigned Latency = 0u;
97 
98   public:
99     /// Constructs a null SDep. This is only for use by container classes which
100     /// require default constructors. SUnits may not/ have null SDep edges.
101     SDep() : Dep(nullptr, Data) {}
102 
103     /// Constructs an SDep with the specified values.
104     SDep(SUnit *S, Kind kind, unsigned Reg)
105       : Dep(S, kind), Contents() {
106       switch (kind) {
107       default:
108         llvm_unreachable("Reg given for non-register dependence!");
109       case Anti:
110       case Output:
111         assert(Reg != 0 &&
112                "SDep::Anti and SDep::Output must use a non-zero Reg!");
113         Contents.Reg = Reg;
114         Latency = 0;
115         break;
116       case Data:
117         Contents.Reg = Reg;
118         Latency = 1;
119         break;
120       }
121     }
122 
123     SDep(SUnit *S, OrderKind kind)
124       : Dep(S, Order), Contents(), Latency(0) {
125       Contents.OrdKind = kind;
126     }
127 
128     /// Returns true if the specified SDep is equivalent except for latency.
129     bool overlaps(const SDep &Other) const;
130 
131     bool operator==(const SDep &Other) const {
132       return overlaps(Other) && Latency == Other.Latency;
133     }
134 
135     bool operator!=(const SDep &Other) const {
136       return !operator==(Other);
137     }
138 
139     /// Returns the latency value for this edge, which roughly means the
140     /// minimum number of cycles that must elapse between the predecessor and
141     /// the successor, given that they have this edge between them.
142     unsigned getLatency() const {
143       return Latency;
144     }
145 
146     /// Sets the latency for this edge.
147     void setLatency(unsigned Lat) {
148       Latency = Lat;
149     }
150 
151     //// Returns the SUnit to which this edge points.
152     SUnit *getSUnit() const;
153 
154     //// Assigns the SUnit to which this edge points.
155     void setSUnit(SUnit *SU);
156 
157     /// Returns an enum value representing the kind of the dependence.
158     Kind getKind() const;
159 
160     /// Shorthand for getKind() != SDep::Data.
161     bool isCtrl() const {
162       return getKind() != Data;
163     }
164 
165     /// Tests if this is an Order dependence between two memory accesses
166     /// where both sides of the dependence access memory in non-volatile and
167     /// fully modeled ways.
168     bool isNormalMemory() const {
169       return getKind() == Order && (Contents.OrdKind == MayAliasMem
170                                     || Contents.OrdKind == MustAliasMem);
171     }
172 
173     /// Tests if this is an Order dependence that is marked as a barrier.
174     bool isBarrier() const {
175       return getKind() == Order && Contents.OrdKind == Barrier;
176     }
177 
178     /// Tests if this is could be any kind of memory dependence.
179     bool isNormalMemoryOrBarrier() const {
180       return (isNormalMemory() || isBarrier());
181     }
182 
183     /// Tests if this is an Order dependence that is marked as
184     /// "must alias", meaning that the SUnits at either end of the edge have a
185     /// memory dependence on a known memory location.
186     bool isMustAlias() const {
187       return getKind() == Order && Contents.OrdKind == MustAliasMem;
188     }
189 
190     /// Tests if this a weak dependence. Weak dependencies are considered DAG
191     /// edges for height computation and other heuristics, but do not force
192     /// ordering. Breaking a weak edge may require the scheduler to compensate,
193     /// for example by inserting a copy.
194     bool isWeak() const {
195       return getKind() == Order && Contents.OrdKind >= Weak;
196     }
197 
198     /// Tests if this is an Order dependence that is marked as
199     /// "artificial", meaning it isn't necessary for correctness.
200     bool isArtificial() const {
201       return getKind() == Order && Contents.OrdKind == Artificial;
202     }
203 
204     /// Tests if this is an Order dependence that is marked as "cluster",
205     /// meaning it is artificial and wants to be adjacent.
206     bool isCluster() const {
207       return getKind() == Order && Contents.OrdKind == Cluster;
208     }
209 
210     /// Tests if this is a Data dependence that is associated with a register.
211     bool isAssignedRegDep() const {
212       return getKind() == Data && Contents.Reg != 0;
213     }
214 
215     /// Returns the register associated with this edge. This is only valid on
216     /// Data, Anti, and Output edges. On Data edges, this value may be zero,
217     /// 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!");
221       return Contents.Reg;
222     }
223 
224     /// Assigns the associated register for this edge. This is only valid on
225     /// Data, Anti, and Output edges. On Anti and Output edges, this value must
226     /// not be zero. On Data edges, the value may be zero, which would mean that
227     /// no specific register is associated with this edge.
228     void setReg(unsigned Reg) {
229       assert((getKind() == Data || getKind() == Anti || getKind() == Output) &&
230              "setReg called on non-register dependence edge!");
231       assert((getKind() != Anti || Reg != 0) &&
232              "SDep::Anti edge cannot use the zero register!");
233       assert((getKind() != Output || Reg != 0) &&
234              "SDep::Output edge cannot use the zero register!");
235       Contents.Reg = Reg;
236     }
237 
238     void dump(const TargetRegisterInfo *TRI = nullptr) const;
239   };
240 
241   /// Scheduling unit. This is a node in the scheduling DAG.
242   class SUnit {
243   private:
244     enum : unsigned { BoundaryID = ~0u };
245 
246     union {
247       SDNode *Node;        ///< Representative node.
248       MachineInstr *Instr; ///< Alternatively, a MachineInstr.
249     };
250 
251   public:
252     SUnit *OrigNode = nullptr; ///< If not this, the node from which this node
253                                /// was cloned. (SD scheduling only)
254 
255     const MCSchedClassDesc *SchedClass =
256         nullptr; ///< nullptr or resolved SchedClass.
257 
258     const TargetRegisterClass *CopyDstRC =
259         nullptr; ///< Is a special copy node if != nullptr.
260     const TargetRegisterClass *CopySrcRC = nullptr;
261 
262     SmallVector<SDep, 4> Preds;  ///< All sunit predecessors.
263     SmallVector<SDep, 4> Succs;  ///< All sunit successors.
264 
265     typedef SmallVectorImpl<SDep>::iterator pred_iterator;
266     typedef SmallVectorImpl<SDep>::iterator succ_iterator;
267     typedef SmallVectorImpl<SDep>::const_iterator const_pred_iterator;
268     typedef SmallVectorImpl<SDep>::const_iterator const_succ_iterator;
269 
270     unsigned NodeNum = BoundaryID;     ///< Entry # of node in the node vector.
271     unsigned NodeQueueId = 0;          ///< Queue id of node.
272     unsigned NumPreds = 0;             ///< # of SDep::Data preds.
273     unsigned NumSuccs = 0;             ///< # of SDep::Data sucss.
274     unsigned NumPredsLeft = 0;         ///< # of preds not scheduled.
275     unsigned NumSuccsLeft = 0;         ///< # of succs not scheduled.
276     unsigned WeakPredsLeft = 0;        ///< # of weak preds not scheduled.
277     unsigned WeakSuccsLeft = 0;        ///< # of weak succs not scheduled.
278     unsigned TopReadyCycle = 0; ///< Cycle relative to start when node is ready.
279     unsigned BotReadyCycle = 0; ///< Cycle relative to end when node is ready.
280 
281   private:
282     unsigned Depth = 0;  ///< Node depth.
283     unsigned Height = 0; ///< Node height.
284 
285   public:
286     bool isVRegCycle      : 1;         ///< May use and def the same vreg.
287     bool isCall           : 1;         ///< Is a function call.
288     bool isCallOp         : 1;         ///< Is a function call operand.
289     bool isTwoAddress     : 1;         ///< Is a two-address instruction.
290     bool isCommutable     : 1;         ///< Is a commutable instruction.
291     bool hasPhysRegUses   : 1;         ///< Has physreg uses.
292     bool hasPhysRegDefs   : 1;         ///< Has physreg defs that are being used.
293     bool hasPhysRegClobbers : 1;       ///< Has any physreg defs, used or not.
294     bool isPending        : 1;         ///< True once pending.
295     bool isAvailable      : 1;         ///< True once available.
296     bool isScheduled      : 1;         ///< True once scheduled.
297     bool isScheduleHigh   : 1;         ///< True if preferable to schedule high.
298     bool isScheduleLow    : 1;         ///< True if preferable to schedule low.
299     bool isCloned         : 1;         ///< True if this node has been cloned.
300     bool isUnbuffered     : 1;         ///< Uses an unbuffered resource.
301     bool hasReservedResource : 1;      ///< Uses a reserved resource.
302     unsigned short NumRegDefsLeft = 0; ///< # of reg defs with no scheduled use.
303     unsigned short Latency = 0;        ///< Node latency.
304 
305   private:
306     bool isDepthCurrent   : 1;         ///< True if Depth is current.
307     bool isHeightCurrent  : 1;         ///< True if Height is current.
308     bool isNode : 1; ///< True if the representative is an SDNode
309     bool isInst : 1; ///< True if the representative is a MachineInstr
310 
311   public:
312     Sched::Preference SchedulingPref : 4; ///< Scheduling preference.
313     static_assert(Sched::Preference::Last <= (1 << 4),
314                   "not enough bits in bitfield");
315 
316     /// Constructs an SUnit for pre-regalloc scheduling to represent an
317     /// SDNode and any nodes flagged to it.
318     SUnit(SDNode *node, unsigned nodenum)
319         : Node(node), NodeNum(nodenum), isVRegCycle(false), isCall(false),
320           isCallOp(false), isTwoAddress(false), isCommutable(false),
321           hasPhysRegUses(false), hasPhysRegDefs(false),
322           hasPhysRegClobbers(false), isPending(false), isAvailable(false),
323           isScheduled(false), isScheduleHigh(false), isScheduleLow(false),
324           isCloned(false), isUnbuffered(false), hasReservedResource(false),
325           isDepthCurrent(false), isHeightCurrent(false), isNode(true),
326           isInst(false), SchedulingPref(Sched::None) {}
327 
328     /// Constructs an SUnit for post-regalloc scheduling to represent a
329     /// MachineInstr.
330     SUnit(MachineInstr *instr, unsigned nodenum)
331         : Instr(instr), NodeNum(nodenum), isVRegCycle(false), isCall(false),
332           isCallOp(false), isTwoAddress(false), isCommutable(false),
333           hasPhysRegUses(false), hasPhysRegDefs(false),
334           hasPhysRegClobbers(false), isPending(false), isAvailable(false),
335           isScheduled(false), isScheduleHigh(false), isScheduleLow(false),
336           isCloned(false), isUnbuffered(false), hasReservedResource(false),
337           isDepthCurrent(false), isHeightCurrent(false), isNode(false),
338           isInst(true), SchedulingPref(Sched::None) {}
339 
340     /// Constructs a placeholder SUnit.
341     SUnit()
342         : Node(nullptr), isVRegCycle(false), isCall(false), isCallOp(false),
343           isTwoAddress(false), isCommutable(false), hasPhysRegUses(false),
344           hasPhysRegDefs(false), hasPhysRegClobbers(false), isPending(false),
345           isAvailable(false), isScheduled(false), isScheduleHigh(false),
346           isScheduleLow(false), isCloned(false), isUnbuffered(false),
347           hasReservedResource(false), isDepthCurrent(false),
348           isHeightCurrent(false), isNode(false), isInst(false),
349           SchedulingPref(Sched::None) {}
350 
351     /// Boundary nodes are placeholders for the boundary of the
352     /// scheduling region.
353     ///
354     /// BoundaryNodes can have DAG edges, including Data edges, but they do not
355     /// correspond to schedulable entities (e.g. instructions) and do not have a
356     /// valid ID. Consequently, always check for boundary nodes before accessing
357     /// an associative data structure keyed on node ID.
358     bool isBoundaryNode() const { return NodeNum == BoundaryID; }
359 
360     /// Assigns the representative SDNode for this SUnit. This may be used
361     /// during pre-regalloc scheduling.
362     void setNode(SDNode *N) {
363       assert(!isInst && "Setting SDNode of SUnit with MachineInstr!");
364       Node = N;
365       isNode = true;
366     }
367 
368     /// Returns the representative SDNode for this SUnit. This may be used
369     /// during pre-regalloc scheduling.
370     SDNode *getNode() const {
371       assert(!isInst && (isNode || !Instr) &&
372              "Reading SDNode of SUnit without SDNode!");
373       return Node;
374     }
375 
376     /// Returns true if this SUnit refers to a machine instruction as
377     /// opposed to an SDNode.
378     bool isInstr() const { return isInst && Instr; }
379 
380     /// Assigns the instruction for the SUnit. This may be used during
381     /// post-regalloc scheduling.
382     void setInstr(MachineInstr *MI) {
383       assert(!isNode && "Setting MachineInstr of SUnit with SDNode!");
384       Instr = MI;
385       isInst = true;
386     }
387 
388     /// Returns the representative MachineInstr for this SUnit. This may be used
389     /// during post-regalloc scheduling.
390     MachineInstr *getInstr() const {
391       assert(!isNode && (isInst || !Node) &&
392              "Reading MachineInstr of SUnit without MachineInstr!");
393       return Instr;
394     }
395 
396     /// Adds the specified edge as a pred of the current node if not already.
397     /// It also adds the current node as a successor of the specified node.
398     bool addPred(const SDep &D, bool Required = true);
399 
400     /// Adds a barrier edge to SU by calling addPred(), with latency 0
401     /// generally or latency 1 for a store 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);
407       return addPred(Dep);
408     }
409 
410     /// Removes the specified edge as a pred of the current node if it exists.
411     /// It also removes the current node as a successor of the specified node.
412     void removePred(const SDep &D);
413 
414     /// Returns the depth of this node, which is the length of the maximum path
415     /// up to any node which has no predecessors.
416     unsigned getDepth() const {
417       if (!isDepthCurrent)
418         const_cast<SUnit *>(this)->ComputeDepth();
419       return Depth;
420     }
421 
422     /// Returns the height of this node, which is the length of the
423     /// maximum path down to any node which has no successors.
424     unsigned getHeight() const {
425       if (!isHeightCurrent)
426         const_cast<SUnit *>(this)->ComputeHeight();
427       return Height;
428     }
429 
430     /// If NewDepth is greater than this node's depth value, sets it to
431     /// be the new depth value. This also recursively marks successor nodes
432     /// dirty.
433     void setDepthToAtLeast(unsigned NewDepth);
434 
435     /// If NewHeight is greater than this node's height value, set it to be
436     /// the new height value. This also recursively marks predecessor nodes
437     /// dirty.
438     void setHeightToAtLeast(unsigned NewHeight);
439 
440     /// Sets a flag in this node to indicate that its stored Depth value
441     /// will require recomputation the next time getDepth() is called.
442     void setDepthDirty();
443 
444     /// Sets a flag in this node to indicate that its stored Height value
445     /// will require recomputation the next time getHeight() is called.
446     void setHeightDirty();
447 
448     /// Tests if node N is a predecessor of this node.
449     bool isPred(const SUnit *N) const {
450       for (const SDep &Pred : Preds)
451         if (Pred.getSUnit() == N)
452           return true;
453       return false;
454     }
455 
456     /// Tests if node N is a successor of this node.
457     bool isSucc(const SUnit *N) const {
458       for (const SDep &Succ : Succs)
459         if (Succ.getSUnit() == N)
460           return true;
461       return false;
462     }
463 
464     bool isTopReady() const {
465       return NumPredsLeft == 0;
466     }
467     bool isBottomReady() const {
468       return NumSuccsLeft == 0;
469     }
470 
471     /// Orders this node's predecessor edges such that the critical path
472     /// edge occurs first.
473     void biasCriticalPath();
474 
475     void dumpAttributes() const;
476 
477   private:
478     void ComputeDepth();
479     void ComputeHeight();
480   };
481 
482   /// Returns true if the specified SDep is equivalent except for latency.
483   inline bool SDep::overlaps(const SDep &Other) const {
484     if (Dep != Other.Dep)
485       return false;
486     switch (Dep.getInt()) {
487     case Data:
488     case Anti:
489     case Output:
490       return Contents.Reg == Other.Contents.Reg;
491     case Order:
492       return Contents.OrdKind == Other.Contents.OrdKind;
493     }
494     llvm_unreachable("Invalid dependency kind!");
495   }
496 
497   //// Returns the SUnit to which this edge points.
498   inline SUnit *SDep::getSUnit() const { return Dep.getPointer(); }
499 
500   //// Assigns the SUnit to which this edge points.
501   inline void SDep::setSUnit(SUnit *SU) { Dep.setPointer(SU); }
502 
503   /// Returns an enum value representing the kind of the dependence.
504   inline SDep::Kind SDep::getKind() const { return Dep.getInt(); }
505 
506   //===--------------------------------------------------------------------===//
507 
508   /// This interface is used to plug different priorities computation
509   /// algorithms into the list scheduler. It implements the interface of a
510   /// standard priority queue, where nodes are inserted in arbitrary order and
511   /// returned in priority order.  The computation of the priority and the
512   /// representation of the queue are totally up to the implementation to
513   /// decide.
514   class SchedulingPriorityQueue {
515     virtual void anchor();
516 
517     unsigned CurCycle = 0;
518     bool HasReadyFilter;
519 
520   public:
521     SchedulingPriorityQueue(bool rf = false) :  HasReadyFilter(rf) {}
522 
523     virtual ~SchedulingPriorityQueue() = default;
524 
525     virtual bool isBottomUp() const = 0;
526 
527     virtual void initNodes(std::vector<SUnit> &SUnits) = 0;
528     virtual void addNode(const SUnit *SU) = 0;
529     virtual void updateNode(const SUnit *SU) = 0;
530     virtual void releaseState() = 0;
531 
532     virtual bool empty() const = 0;
533 
534     bool hasReadyFilter() const { return HasReadyFilter; }
535 
536     virtual bool tracksRegPressure() const { return false; }
537 
538     virtual bool isReady(SUnit *) const {
539       assert(!HasReadyFilter && "The ready filter must override isReady()");
540       return true;
541     }
542 
543     virtual void push(SUnit *U) = 0;
544 
545     void push_all(const std::vector<SUnit *> &Nodes) {
546       for (SUnit *SU : Nodes)
547         push(SU);
548     }
549 
550     virtual SUnit *pop() = 0;
551 
552     virtual void remove(SUnit *SU) = 0;
553 
554     virtual void dump(ScheduleDAG *) const {}
555 
556     /// As each node is scheduled, this method is invoked.  This allows the
557     /// priority function to adjust the priority of related unscheduled nodes,
558     /// for example.
559     virtual void scheduledNode(SUnit *) {}
560 
561     virtual void unscheduledNode(SUnit *) {}
562 
563     void setCurCycle(unsigned Cycle) {
564       CurCycle = Cycle;
565     }
566 
567     unsigned getCurCycle() const {
568       return CurCycle;
569     }
570   };
571 
572   class ScheduleDAG {
573   public:
574     const LLVMTargetMachine &TM;        ///< Target processor
575     const TargetInstrInfo *TII;         ///< Target instruction information
576     const TargetRegisterInfo *TRI;      ///< Target processor register info
577     MachineFunction &MF;                ///< Machine function
578     MachineRegisterInfo &MRI;           ///< Virtual/real register map
579     std::vector<SUnit> SUnits;          ///< The scheduling units.
580     SUnit EntrySU;                      ///< Special node for the region entry.
581     SUnit ExitSU;                       ///< Special node for the region exit.
582 
583 #ifdef NDEBUG
584     static const bool StressSched = false;
585 #else
586     bool StressSched;
587 #endif
588 
589     // This class is designed to be passed by reference only. Copy constructor
590     // is declared as deleted here to make the derived classes have deleted
591     // implicit-declared copy constructor, which suppresses the warnings from
592     // static analyzer when the derived classes own resources that are freed in
593     // their destructors, but don't have user-written copy constructors (rule
594     // of three).
595     ScheduleDAG(const ScheduleDAG &) = delete;
596     ScheduleDAG &operator=(const ScheduleDAG &) = delete;
597 
598     explicit ScheduleDAG(MachineFunction &mf);
599 
600     virtual ~ScheduleDAG();
601 
602     /// Clears the DAG state (between regions).
603     void clearDAG();
604 
605     /// Returns the MCInstrDesc of this SUnit.
606     /// Returns NULL for SDNodes without a machine opcode.
607     const MCInstrDesc *getInstrDesc(const SUnit *SU) const {
608       if (SU->isInstr()) return &SU->getInstr()->getDesc();
609       return getNodeDesc(SU->getNode());
610     }
611 
612     /// Pops up a GraphViz/gv window with the ScheduleDAG rendered using 'dot'.
613     virtual void viewGraph(const Twine &Name, const Twine &Title);
614     virtual void viewGraph();
615 
616     virtual void dumpNode(const SUnit &SU) const = 0;
617     virtual void dump() const = 0;
618     void dumpNodeName(const SUnit &SU) const;
619 
620     /// Returns a label for an SUnit node in a visualization of the ScheduleDAG.
621     virtual std::string getGraphNodeLabel(const SUnit *SU) const = 0;
622 
623     /// Returns a label for the region of code covered by the DAG.
624     virtual std::string getDAGName() const = 0;
625 
626     /// Adds custom features for a visualization of the ScheduleDAG.
627     virtual void addCustomGraphFeatures(GraphWriter<ScheduleDAG*> &) const {}
628 
629 #ifndef NDEBUG
630     /// Verifies that all SUnits were scheduled and that their state is
631     /// consistent. Returns the number of scheduled SUnits.
632     unsigned VerifyScheduledDAG(bool isBottomUp);
633 #endif
634 
635   protected:
636     void dumpNodeAll(const SUnit &SU) const;
637 
638   private:
639     /// Returns the MCInstrDesc of this SDNode or NULL.
640     const MCInstrDesc *getNodeDesc(const SDNode *Node) const;
641   };
642 
643   class SUnitIterator {
644     SUnit *Node;
645     unsigned Operand;
646 
647     SUnitIterator(SUnit *N, unsigned Op) : Node(N), Operand(Op) {}
648 
649   public:
650     using iterator_category = std::forward_iterator_tag;
651     using value_type = SUnit;
652     using difference_type = std::ptrdiff_t;
653     using pointer = value_type *;
654     using reference = value_type &;
655 
656     bool operator==(const SUnitIterator& x) const {
657       return Operand == x.Operand;
658     }
659     bool operator!=(const SUnitIterator& x) const { return !operator==(x); }
660 
661     pointer operator*() const {
662       return Node->Preds[Operand].getSUnit();
663     }
664     pointer operator->() const { return operator*(); }
665 
666     SUnitIterator& operator++() {                // Preincrement
667       ++Operand;
668       return *this;
669     }
670     SUnitIterator operator++(int) { // Postincrement
671       SUnitIterator tmp = *this; ++*this; return tmp;
672     }
673 
674     static SUnitIterator begin(SUnit *N) { return SUnitIterator(N, 0); }
675     static SUnitIterator end  (SUnit *N) {
676       return SUnitIterator(N, (unsigned)N->Preds.size());
677     }
678 
679     unsigned getOperand() const { return Operand; }
680     const SUnit *getNode() const { return Node; }
681 
682     /// Tests if this is not an SDep::Data dependence.
683     bool isCtrlDep() const {
684       return getSDep().isCtrl();
685     }
686     bool isArtificialDep() const {
687       return getSDep().isArtificial();
688     }
689     const SDep &getSDep() const {
690       return Node->Preds[Operand];
691     }
692   };
693 
694   template <> struct GraphTraits<SUnit*> {
695     typedef SUnit *NodeRef;
696     typedef SUnitIterator ChildIteratorType;
697     static NodeRef getEntryNode(SUnit *N) { return N; }
698     static ChildIteratorType child_begin(NodeRef N) {
699       return SUnitIterator::begin(N);
700     }
701     static ChildIteratorType child_end(NodeRef N) {
702       return SUnitIterator::end(N);
703     }
704   };
705 
706   template <> struct GraphTraits<ScheduleDAG*> : public GraphTraits<SUnit*> {
707     typedef pointer_iterator<std::vector<SUnit>::iterator> nodes_iterator;
708     static nodes_iterator nodes_begin(ScheduleDAG *G) {
709       return nodes_iterator(G->SUnits.begin());
710     }
711     static nodes_iterator nodes_end(ScheduleDAG *G) {
712       return nodes_iterator(G->SUnits.end());
713     }
714   };
715 
716   /// This class can compute a topological ordering for SUnits and provides
717   /// methods for dynamically updating the ordering as new edges are added.
718   ///
719   /// This allows a very fast implementation of IsReachable, for example.
720   class ScheduleDAGTopologicalSort {
721     /// A reference to the ScheduleDAG's SUnits.
722     std::vector<SUnit> &SUnits;
723     SUnit *ExitSU;
724 
725     // Have any new nodes been added?
726     bool Dirty = false;
727 
728     // Outstanding added edges, that have not been applied to the ordering.
729     SmallVector<std::pair<SUnit *, SUnit *>, 16> Updates;
730 
731     /// Maps topological index to the node number.
732     std::vector<int> Index2Node;
733     /// Maps the node number to its topological index.
734     std::vector<int> Node2Index;
735     /// a set of nodes visited during a DFS traversal.
736     BitVector Visited;
737 
738     /// Makes a DFS traversal and mark all nodes affected by the edge insertion.
739     /// These nodes will later get new topological indexes by means of the Shift
740     /// method.
741     void DFS(const SUnit *SU, int UpperBound, bool& HasLoop);
742 
743     /// Reassigns topological indexes for the nodes in the DAG to
744     /// preserve the topological ordering.
745     void Shift(BitVector& Visited, int LowerBound, int UpperBound);
746 
747     /// Assigns the topological index to the node n.
748     void Allocate(int n, int index);
749 
750     /// Fix the ordering, by either recomputing from scratch or by applying
751     /// any outstanding updates. Uses a heuristic to estimate what will be
752     /// cheaper.
753     void FixOrder();
754 
755   public:
756     ScheduleDAGTopologicalSort(std::vector<SUnit> &SUnits, SUnit *ExitSU);
757 
758     /// Add a SUnit without predecessors to the end of the topological order. It
759     /// also must be the first new node added to the DAG.
760     void AddSUnitWithoutPredecessors(const SUnit *SU);
761 
762     /// Creates the initial topological ordering from the DAG to be scheduled.
763     void InitDAGTopologicalSorting();
764 
765     /// Returns an array of SUs that are both in the successor
766     /// subtree of StartSU and in the predecessor subtree of TargetSU.
767     /// StartSU and TargetSU are not in the array.
768     /// Success is false if TargetSU is not in the successor subtree of
769     /// StartSU, else it is true.
770     std::vector<int> GetSubGraph(const SUnit &StartSU, const SUnit &TargetSU,
771                                  bool &Success);
772 
773     /// Checks if \p SU is reachable from \p TargetSU.
774     bool IsReachable(const SUnit *SU, const SUnit *TargetSU);
775 
776     /// Returns true if addPred(TargetSU, SU) creates a cycle.
777     bool WillCreateCycle(SUnit *TargetSU, SUnit *SU);
778 
779     /// Updates the topological ordering to accommodate an edge to be
780     /// added from SUnit \p X to SUnit \p Y.
781     void AddPred(SUnit *Y, SUnit *X);
782 
783     /// Queues an update to the topological ordering to accommodate an edge to
784     /// be added from SUnit \p X to SUnit \p Y.
785     void AddPredQueued(SUnit *Y, SUnit *X);
786 
787     /// Updates the topological ordering to accommodate an edge to be
788     /// removed from the specified node \p N from the predecessors of the
789     /// current node \p M.
790     void RemovePred(SUnit *M, SUnit *N);
791 
792     /// Mark the ordering as temporarily broken, after a new node has been
793     /// added.
794     void MarkDirty() { Dirty = true; }
795 
796     typedef std::vector<int>::iterator iterator;
797     typedef std::vector<int>::const_iterator const_iterator;
798     iterator begin() { return Index2Node.begin(); }
799     const_iterator begin() const { return Index2Node.begin(); }
800     iterator end() { return Index2Node.end(); }
801     const_iterator end() const { return Index2Node.end(); }
802 
803     typedef std::vector<int>::reverse_iterator reverse_iterator;
804     typedef std::vector<int>::const_reverse_iterator const_reverse_iterator;
805     reverse_iterator rbegin() { return Index2Node.rbegin(); }
806     const_reverse_iterator rbegin() const { return Index2Node.rbegin(); }
807     reverse_iterator rend() { return Index2Node.rend(); }
808     const_reverse_iterator rend() const { return Index2Node.rend(); }
809   };
810 
811 } // end namespace llvm
812 
813 #endif // LLVM_CODEGEN_SCHEDULEDAG_H
814