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