LLVM  8.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  /// 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  /// 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  /// 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  /// 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  /// 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  /// 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 
239  void dump(const TargetRegisterInfo *TRI = nullptr) const;
240  };
241 
242  template <>
243  struct isPodLike<SDep> { static const bool value = true; };
244 
245  /// Scheduling unit. This is a node in the scheduling DAG.
246  class SUnit {
247  private:
248  enum : unsigned { BoundaryID = ~0u };
249 
250  SDNode *Node = nullptr; ///< Representative node.
251  MachineInstr *Instr = nullptr; ///< Alternatively, a MachineInstr.
252 
253  public:
254  SUnit *OrigNode = nullptr; ///< If not this, the node from which this node
255  /// was cloned. (SD scheduling only)
256 
257  const MCSchedClassDesc *SchedClass =
258  nullptr; ///< nullptr or resolved SchedClass.
259 
260  SmallVector<SDep, 4> Preds; ///< All sunit predecessors.
261  SmallVector<SDep, 4> Succs; ///< All sunit successors.
262 
267 
268  unsigned NodeNum = BoundaryID; ///< Entry # of node in the node vector.
269  unsigned NodeQueueId = 0; ///< Queue id of node.
270  unsigned NumPreds = 0; ///< # of SDep::Data preds.
271  unsigned NumSuccs = 0; ///< # of SDep::Data sucss.
272  unsigned NumPredsLeft = 0; ///< # of preds not scheduled.
273  unsigned NumSuccsLeft = 0; ///< # of succs not scheduled.
274  unsigned WeakPredsLeft = 0; ///< # of weak preds not scheduled.
275  unsigned WeakSuccsLeft = 0; ///< # of weak succs not scheduled.
276  unsigned short NumRegDefsLeft = 0; ///< # of reg defs with no scheduled use.
277  unsigned short Latency = 0; ///< Node latency.
278  bool isVRegCycle : 1; ///< May use and def the same vreg.
279  bool isCall : 1; ///< Is a function call.
280  bool isCallOp : 1; ///< Is a function call operand.
281  bool isTwoAddress : 1; ///< Is a two-address instruction.
282  bool isCommutable : 1; ///< Is a commutable instruction.
283  bool hasPhysRegUses : 1; ///< Has physreg uses.
284  bool hasPhysRegDefs : 1; ///< Has physreg defs that are being used.
285  bool hasPhysRegClobbers : 1; ///< Has any physreg defs, used or not.
286  bool isPending : 1; ///< True once pending.
287  bool isAvailable : 1; ///< True once available.
288  bool isScheduled : 1; ///< True once scheduled.
289  bool isScheduleHigh : 1; ///< True if preferable to schedule high.
290  bool isScheduleLow : 1; ///< True if preferable to schedule low.
291  bool isCloned : 1; ///< True if this node has been cloned.
292  bool isUnbuffered : 1; ///< Uses an unbuffered resource.
293  bool hasReservedResource : 1; ///< Uses a reserved resource.
294  Sched::Preference SchedulingPref = Sched::None; ///< Scheduling preference.
295 
296  private:
297  bool isDepthCurrent : 1; ///< True if Depth is current.
298  bool isHeightCurrent : 1; ///< True if Height is current.
299  unsigned Depth = 0; ///< Node depth.
300  unsigned Height = 0; ///< Node height.
301 
302  public:
303  unsigned TopReadyCycle = 0; ///< Cycle relative to start when node is ready.
304  unsigned BotReadyCycle = 0; ///< Cycle relative to end when node is ready.
305 
306  const TargetRegisterClass *CopyDstRC =
307  nullptr; ///< Is a special copy node if != nullptr.
308  const TargetRegisterClass *CopySrcRC = nullptr;
309 
310  /// Constructs an SUnit for pre-regalloc scheduling to represent an
311  /// SDNode and any nodes flagged to it.
312  SUnit(SDNode *node, unsigned nodenum)
313  : Node(node), NodeNum(nodenum), isVRegCycle(false), isCall(false),
314  isCallOp(false), isTwoAddress(false), isCommutable(false),
315  hasPhysRegUses(false), hasPhysRegDefs(false), hasPhysRegClobbers(false),
316  isPending(false), isAvailable(false), isScheduled(false),
317  isScheduleHigh(false), isScheduleLow(false), isCloned(false),
318  isUnbuffered(false), hasReservedResource(false), isDepthCurrent(false),
319  isHeightCurrent(false) {}
320 
321  /// Constructs an SUnit for post-regalloc scheduling to represent a
322  /// MachineInstr.
323  SUnit(MachineInstr *instr, unsigned nodenum)
324  : Instr(instr), NodeNum(nodenum), isVRegCycle(false), isCall(false),
325  isCallOp(false), isTwoAddress(false), isCommutable(false),
326  hasPhysRegUses(false), hasPhysRegDefs(false), hasPhysRegClobbers(false),
327  isPending(false), isAvailable(false), isScheduled(false),
328  isScheduleHigh(false), isScheduleLow(false), isCloned(false),
329  isUnbuffered(false), hasReservedResource(false), isDepthCurrent(false),
330  isHeightCurrent(false) {}
331 
332  /// Constructs a placeholder SUnit.
334  : isVRegCycle(false), isCall(false), isCallOp(false), isTwoAddress(false),
335  isCommutable(false), hasPhysRegUses(false), hasPhysRegDefs(false),
336  hasPhysRegClobbers(false), isPending(false), isAvailable(false),
337  isScheduled(false), isScheduleHigh(false), isScheduleLow(false),
338  isCloned(false), isUnbuffered(false), hasReservedResource(false),
339  isDepthCurrent(false), isHeightCurrent(false) {}
340 
341  /// Boundary nodes are placeholders for the boundary of the
342  /// scheduling region.
343  ///
344  /// BoundaryNodes can have DAG edges, including Data edges, but they do not
345  /// correspond to schedulable entities (e.g. instructions) and do not have a
346  /// valid ID. Consequently, always check for boundary nodes before accessing
347  /// an associative data structure keyed on node ID.
348  bool isBoundaryNode() const { return NodeNum == BoundaryID; }
349 
350  /// Assigns the representative SDNode for this SUnit. This may be used
351  /// during pre-regalloc scheduling.
352  void setNode(SDNode *N) {
353  assert(!Instr && "Setting SDNode of SUnit with MachineInstr!");
354  Node = N;
355  }
356 
357  /// Returns the representative SDNode for this SUnit. This may be used
358  /// during pre-regalloc scheduling.
359  SDNode *getNode() const {
360  assert(!Instr && "Reading SDNode of SUnit with MachineInstr!");
361  return Node;
362  }
363 
364  /// Returns true if this SUnit refers to a machine instruction as
365  /// opposed to an SDNode.
366  bool isInstr() const { return Instr; }
367 
368  /// Assigns the instruction for the SUnit. This may be used during
369  /// post-regalloc scheduling.
371  assert(!Node && "Setting MachineInstr of SUnit with SDNode!");
372  Instr = MI;
373  }
374 
375  /// Returns the representative MachineInstr for this SUnit. This may be used
376  /// during post-regalloc scheduling.
378  assert(!Node && "Reading MachineInstr of SUnit with SDNode!");
379  return Instr;
380  }
381 
382  /// Adds the specified edge as a pred of the current node if not already.
383  /// It also adds the current node as a successor of the specified node.
384  bool addPred(const SDep &D, bool Required = true);
385 
386  /// Adds a barrier edge to SU by calling addPred(), with latency 0
387  /// generally or latency 1 for a store followed by a load.
388  bool addPredBarrier(SUnit *SU) {
389  SDep Dep(SU, SDep::Barrier);
390  unsigned TrueMemOrderLatency =
391  ((SU->getInstr()->mayStore() && this->getInstr()->mayLoad()) ? 1 : 0);
392  Dep.setLatency(TrueMemOrderLatency);
393  return addPred(Dep);
394  }
395 
396  /// Removes the specified edge as a pred of the current node if it exists.
397  /// It also removes the current node as a successor of the specified node.
398  void removePred(const SDep &D);
399 
400  /// Returns the depth of this node, which is the length of the maximum path
401  /// up to any node which has no predecessors.
402  unsigned getDepth() const {
403  if (!isDepthCurrent)
404  const_cast<SUnit *>(this)->ComputeDepth();
405  return Depth;
406  }
407 
408  /// Returns the height of this node, which is the length of the
409  /// maximum path down to any node which has no successors.
410  unsigned getHeight() const {
411  if (!isHeightCurrent)
412  const_cast<SUnit *>(this)->ComputeHeight();
413  return Height;
414  }
415 
416  /// If NewDepth is greater than this node's depth value, sets it to
417  /// be the new depth value. This also recursively marks successor nodes
418  /// dirty.
419  void setDepthToAtLeast(unsigned NewDepth);
420 
421  /// If NewDepth is greater than this node's depth value, set it to be
422  /// the new height value. This also recursively marks predecessor nodes
423  /// dirty.
424  void setHeightToAtLeast(unsigned NewHeight);
425 
426  /// Sets a flag in this node to indicate that its stored Depth value
427  /// will require recomputation the next time getDepth() is called.
428  void setDepthDirty();
429 
430  /// Sets a flag in this node to indicate that its stored Height value
431  /// will require recomputation the next time getHeight() is called.
432  void setHeightDirty();
433 
434  /// Tests if node N is a predecessor of this node.
435  bool isPred(const SUnit *N) const {
436  for (const SDep &Pred : Preds)
437  if (Pred.getSUnit() == N)
438  return true;
439  return false;
440  }
441 
442  /// Tests if node N is a successor of this node.
443  bool isSucc(const SUnit *N) const {
444  for (const SDep &Succ : Succs)
445  if (Succ.getSUnit() == N)
446  return true;
447  return false;
448  }
449 
450  bool isTopReady() const {
451  return NumPredsLeft == 0;
452  }
453  bool isBottomReady() const {
454  return NumSuccsLeft == 0;
455  }
456 
457  /// Orders this node's predecessor edges such that the critical path
458  /// edge occurs first.
459  void biasCriticalPath();
460 
461  void dumpAttributes() const;
462 
463  private:
464  void ComputeDepth();
465  void ComputeHeight();
466  };
467 
468  /// Returns true if the specified SDep is equivalent except for latency.
469  inline bool SDep::overlaps(const SDep &Other) const {
470  if (Dep != Other.Dep)
471  return false;
472  switch (Dep.getInt()) {
473  case Data:
474  case Anti:
475  case Output:
476  return Contents.Reg == Other.Contents.Reg;
477  case Order:
478  return Contents.OrdKind == Other.Contents.OrdKind;
479  }
480  llvm_unreachable("Invalid dependency kind!");
481  }
482 
483  //// Returns the SUnit to which this edge points.
484  inline SUnit *SDep::getSUnit() const { return Dep.getPointer(); }
485 
486  //// Assigns the SUnit to which this edge points.
487  inline void SDep::setSUnit(SUnit *SU) { Dep.setPointer(SU); }
488 
489  /// Returns an enum value representing the kind of the dependence.
490  inline SDep::Kind SDep::getKind() const { return Dep.getInt(); }
491 
492  //===--------------------------------------------------------------------===//
493 
494  /// This interface is used to plug different priorities computation
495  /// algorithms into the list scheduler. It implements the interface of a
496  /// standard priority queue, where nodes are inserted in arbitrary order and
497  /// returned in priority order. The computation of the priority and the
498  /// representation of the queue are totally up to the implementation to
499  /// decide.
501  virtual void anchor();
502 
503  unsigned CurCycle = 0;
504  bool HasReadyFilter;
505 
506  public:
507  SchedulingPriorityQueue(bool rf = false) : HasReadyFilter(rf) {}
508 
509  virtual ~SchedulingPriorityQueue() = default;
510 
511  virtual bool isBottomUp() const = 0;
512 
513  virtual void initNodes(std::vector<SUnit> &SUnits) = 0;
514  virtual void addNode(const SUnit *SU) = 0;
515  virtual void updateNode(const SUnit *SU) = 0;
516  virtual void releaseState() = 0;
517 
518  virtual bool empty() const = 0;
519 
520  bool hasReadyFilter() const { return HasReadyFilter; }
521 
522  virtual bool tracksRegPressure() const { return false; }
523 
524  virtual bool isReady(SUnit *) const {
525  assert(!HasReadyFilter && "The ready filter must override isReady()");
526  return true;
527  }
528 
529  virtual void push(SUnit *U) = 0;
530 
531  void push_all(const std::vector<SUnit *> &Nodes) {
532  for (std::vector<SUnit *>::const_iterator I = Nodes.begin(),
533  E = Nodes.end(); I != E; ++I)
534  push(*I);
535  }
536 
537  virtual SUnit *pop() = 0;
538 
539  virtual void remove(SUnit *SU) = 0;
540 
541  virtual void dump(ScheduleDAG *) const {}
542 
543  /// As each node is scheduled, this method is invoked. This allows the
544  /// priority function to adjust the priority of related unscheduled nodes,
545  /// for example.
546  virtual void scheduledNode(SUnit *) {}
547 
548  virtual void unscheduledNode(SUnit *) {}
549 
550  void setCurCycle(unsigned Cycle) {
551  CurCycle = Cycle;
552  }
553 
554  unsigned getCurCycle() const {
555  return CurCycle;
556  }
557  };
558 
559  class ScheduleDAG {
560  public:
561  const TargetMachine &TM; ///< Target processor
562  const TargetInstrInfo *TII; ///< Target instruction information
563  const TargetRegisterInfo *TRI; ///< Target processor register info
564  MachineFunction &MF; ///< Machine function
565  MachineRegisterInfo &MRI; ///< Virtual/real register map
566  std::vector<SUnit> SUnits; ///< The scheduling units.
567  SUnit EntrySU; ///< Special node for the region entry.
568  SUnit ExitSU; ///< Special node for the region exit.
569 
570 #ifdef NDEBUG
571  static const bool StressSched = false;
572 #else
574 #endif
575 
576  explicit ScheduleDAG(MachineFunction &mf);
577 
578  virtual ~ScheduleDAG();
579 
580  /// Clears the DAG state (between regions).
581  void clearDAG();
582 
583  /// Returns the MCInstrDesc of this SUnit.
584  /// Returns NULL for SDNodes without a machine opcode.
585  const MCInstrDesc *getInstrDesc(const SUnit *SU) const {
586  if (SU->isInstr()) return &SU->getInstr()->getDesc();
587  return getNodeDesc(SU->getNode());
588  }
589 
590  /// Pops up a GraphViz/gv window with the ScheduleDAG rendered using 'dot'.
591  virtual void viewGraph(const Twine &Name, const Twine &Title);
592  virtual void viewGraph();
593 
594  virtual void dumpNode(const SUnit &SU) const = 0;
595  virtual void dump() const = 0;
596  void dumpNodeName(const SUnit &SU) const;
597 
598  /// Returns a label for an SUnit node in a visualization of the ScheduleDAG.
599  virtual std::string getGraphNodeLabel(const SUnit *SU) const = 0;
600 
601  /// Returns a label for the region of code covered by the DAG.
602  virtual std::string getDAGName() const = 0;
603 
604  /// Adds custom features for a visualization of the ScheduleDAG.
606 
607 #ifndef NDEBUG
608  /// Verifies that all SUnits were scheduled and that their state is
609  /// consistent. Returns the number of scheduled SUnits.
610  unsigned VerifyScheduledDAG(bool isBottomUp);
611 #endif
612 
613  protected:
614  void dumpNodeAll(const SUnit &SU) const;
615 
616  private:
617  /// Returns the MCInstrDesc of this SDNode or NULL.
618  const MCInstrDesc *getNodeDesc(const SDNode *Node) const;
619  };
620 
621  class SUnitIterator : public std::iterator<std::forward_iterator_tag,
622  SUnit, ptrdiff_t> {
623  SUnit *Node;
624  unsigned Operand;
625 
626  SUnitIterator(SUnit *N, unsigned Op) : Node(N), Operand(Op) {}
627 
628  public:
629  bool operator==(const SUnitIterator& x) const {
630  return Operand == x.Operand;
631  }
632  bool operator!=(const SUnitIterator& x) const { return !operator==(x); }
633 
634  pointer operator*() const {
635  return Node->Preds[Operand].getSUnit();
636  }
637  pointer operator->() const { return operator*(); }
638 
639  SUnitIterator& operator++() { // Preincrement
640  ++Operand;
641  return *this;
642  }
643  SUnitIterator operator++(int) { // Postincrement
644  SUnitIterator tmp = *this; ++*this; return tmp;
645  }
646 
647  static SUnitIterator begin(SUnit *N) { return SUnitIterator(N, 0); }
648  static SUnitIterator end (SUnit *N) {
649  return SUnitIterator(N, (unsigned)N->Preds.size());
650  }
651 
652  unsigned getOperand() const { return Operand; }
653  const SUnit *getNode() const { return Node; }
654 
655  /// Tests if this is not an SDep::Data dependence.
656  bool isCtrlDep() const {
657  return getSDep().isCtrl();
658  }
659  bool isArtificialDep() const {
660  return getSDep().isArtificial();
661  }
662  const SDep &getSDep() const {
663  return Node->Preds[Operand];
664  }
665  };
666 
667  template <> struct GraphTraits<SUnit*> {
668  typedef SUnit *NodeRef;
670  static NodeRef getEntryNode(SUnit *N) { return N; }
671  static ChildIteratorType child_begin(NodeRef N) {
672  return SUnitIterator::begin(N);
673  }
674  static ChildIteratorType child_end(NodeRef N) {
675  return SUnitIterator::end(N);
676  }
677  };
678 
679  template <> struct GraphTraits<ScheduleDAG*> : public GraphTraits<SUnit*> {
681  static nodes_iterator nodes_begin(ScheduleDAG *G) {
682  return nodes_iterator(G->SUnits.begin());
683  }
684  static nodes_iterator nodes_end(ScheduleDAG *G) {
685  return nodes_iterator(G->SUnits.end());
686  }
687  };
688 
689  /// This class can compute a topological ordering for SUnits and provides
690  /// methods for dynamically updating the ordering as new edges are added.
691  ///
692  /// This allows a very fast implementation of IsReachable, for example.
694  /// A reference to the ScheduleDAG's SUnits.
695  std::vector<SUnit> &SUnits;
696  SUnit *ExitSU;
697 
698  /// Maps topological index to the node number.
699  std::vector<int> Index2Node;
700  /// Maps the node number to its topological index.
701  std::vector<int> Node2Index;
702  /// a set of nodes visited during a DFS traversal.
703  BitVector Visited;
704 
705  /// Makes a DFS traversal and mark all nodes affected by the edge insertion.
706  /// These nodes will later get new topological indexes by means of the Shift
707  /// method.
708  void DFS(const SUnit *SU, int UpperBound, bool& HasLoop);
709 
710  /// Reassigns topological indexes for the nodes in the DAG to
711  /// preserve the topological ordering.
712  void Shift(BitVector& Visited, int LowerBound, int UpperBound);
713 
714  /// Assigns the topological index to the node n.
715  void Allocate(int n, int index);
716 
717  public:
718  ScheduleDAGTopologicalSort(std::vector<SUnit> &SUnits, SUnit *ExitSU);
719 
720  /// Creates the initial topological ordering from the DAG to be scheduled.
721  void InitDAGTopologicalSorting();
722 
723  /// Returns an array of SUs that are both in the successor
724  /// subtree of StartSU and in the predecessor subtree of TargetSU.
725  /// StartSU and TargetSU are not in the array.
726  /// Success is false if TargetSU is not in the successor subtree of
727  /// StartSU, else it is true.
728  std::vector<int> GetSubGraph(const SUnit &StartSU, const SUnit &TargetSU,
729  bool &Success);
730 
731  /// Checks if \p SU is reachable from \p TargetSU.
732  bool IsReachable(const SUnit *SU, const SUnit *TargetSU);
733 
734  /// Returns true if addPred(TargetSU, SU) creates a cycle.
735  bool WillCreateCycle(SUnit *TargetSU, SUnit *SU);
736 
737  /// Updates the topological ordering to accommodate an edge to be
738  /// added from SUnit \p X to SUnit \p Y.
739  void AddPred(SUnit *Y, SUnit *X);
740 
741  /// Updates the topological ordering to accommodate an an edge to be
742  /// removed from the specified node \p N from the predecessors of the
743  /// current node \p M.
744  void RemovePred(SUnit *M, SUnit *N);
745 
746  typedef std::vector<int>::iterator iterator;
747  typedef std::vector<int>::const_iterator const_iterator;
748  iterator begin() { return Index2Node.begin(); }
749  const_iterator begin() const { return Index2Node.begin(); }
750  iterator end() { return Index2Node.end(); }
751  const_iterator end() const { return Index2Node.end(); }
752 
753  typedef std::vector<int>::reverse_iterator reverse_iterator;
754  typedef std::vector<int>::const_reverse_iterator const_reverse_iterator;
755  reverse_iterator rbegin() { return Index2Node.rbegin(); }
756  const_reverse_iterator rbegin() const { return Index2Node.rbegin(); }
757  reverse_iterator rend() { return Index2Node.rend(); }
758  const_reverse_iterator rend() const { return Index2Node.rend(); }
759  };
760 
761 } // end namespace llvm
762 
763 #endif // LLVM_CODEGEN_SCHEDULEDAG_H
static nodes_iterator nodes_begin(ScheduleDAG *G)
Definition: ScheduleDAG.h:681
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:754
unsigned getOperand() const
Definition: ScheduleDAG.h:652
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
std::vector< int >::reverse_iterator reverse_iterator
Definition: ScheduleDAG.h:753
typename SuperClass::const_iterator const_iterator
Definition: SmallVector.h:328
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:352
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:359
pointer operator*() const
Definition: ScheduleDAG.h:634
virtual bool tracksRegPressure() const
Definition: ScheduleDAG.h:522
bool isTwoAddress
Is a two-address instruction.
Definition: ScheduleDAG.h:281
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:402
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:487
std::vector< int >::iterator iterator
Definition: ScheduleDAG.h:746
unsigned const TargetRegisterInfo * TRI
unsigned getReg() const
Returns the register associated with this edge.
Definition: ScheduleDAG.h:219
const_reverse_iterator rend() const
Definition: ScheduleDAG.h:758
bool isBottomReady() const
Definition: ScheduleDAG.h:453
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:670
SmallVectorImpl< SDep >::iterator succ_iterator
Definition: ScheduleDAG.h:264
const_iterator begin() const
Definition: ScheduleDAG.h:749
virtual void dump(ScheduleDAG *) const
Definition: ScheduleDAG.h:541
SUnit()
Constructs a placeholder SUnit.
Definition: ScheduleDAG.h:333
unsigned getCurCycle() const
Definition: ScheduleDAG.h:554
SmallVector< SDep, 4 > Preds
All sunit predecessors.
Definition: ScheduleDAG.h:260
A register anti-dependence (aka WAR).
Definition: ScheduleDAG.h:55
MachineFunction & MF
Machine function.
Definition: ScheduleDAG.h:564
bool isScheduled
True once scheduled.
Definition: ScheduleDAG.h:288
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:500
amdgpu Simplify well known AMD library false Value Value const Twine & Name
SmallVectorImpl< SDep >::iterator pred_iterator
Definition: ScheduleDAG.h:263
virtual void unscheduledNode(SUnit *)
Definition: ScheduleDAG.h:548
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:370
SmallVectorImpl< SDep >::const_iterator const_pred_iterator
Definition: ScheduleDAG.h:265
void push_all(const std::vector< SUnit *> &Nodes)
Definition: ScheduleDAG.h:531
Regular data dependence (aka true-dependence).
Definition: ScheduleDAG.h:54
bool hasPhysRegUses
Has physreg uses.
Definition: ScheduleDAG.h:283
const MCInstrDesc * getInstrDesc(const SUnit *SU) const
Returns the MCInstrDesc of this SUnit.
Definition: ScheduleDAG.h:585
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:284
void setCurCycle(unsigned Cycle)
Definition: ScheduleDAG.h:550
ELFYAML::ELF_STO Other
Definition: ELFYAML.cpp:773
APInt operator*(APInt a, uint64_t RHS)
Definition: APInt.h:2085
SchedulingPriorityQueue(bool rf=false)
Definition: ScheduleDAG.h:507
bool operator==(const SUnitIterator &x) const
Definition: ScheduleDAG.h:629
const_reverse_iterator rbegin() const
Definition: ScheduleDAG.h:756
pointer operator->() const
Definition: ScheduleDAG.h:637
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:406
bool hasReservedResource
Uses a reserved resource.
Definition: ScheduleDAG.h:293
bool isPending
True once pending.
Definition: ScheduleDAG.h:286
bool isCtrl() const
Shorthand for getKind() != SDep::Data.
Definition: ScheduleDAG.h:162
bool isTopReady() const
Definition: ScheduleDAG.h:450
SUnit * getSUnit() const
Definition: ScheduleDAG.h:484
bool isBoundaryNode() const
Boundary nodes are placeholders for the boundary of the scheduling region.
Definition: ScheduleDAG.h:348
TargetInstrInfo - Interface to description of machine instruction set.
Scheduling dependency.
Definition: ScheduleDAG.h:50
bool isUnbuffered
Uses an unbuffered resource.
Definition: ScheduleDAG.h:292
bool isAvailable()
Definition: Compression.cpp:48
bool mayStore(QueryType Type=AnyInBundle) const
Return true if this instruction could possibly modify memory.
Definition: MachineInstr.h:820
bool isCall
Is a function call.
Definition: ScheduleDAG.h:279
MachineInstr * getInstr() const
Returns the representative MachineInstr for this SUnit.
Definition: ScheduleDAG.h:377
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:110
const SUnit * getNode() const
Definition: ScheduleDAG.h:653
static SUnitIterator begin(SUnit *N)
Definition: ScheduleDAG.h:647
bool isVRegCycle
May use and def the same vreg.
Definition: ScheduleDAG.h:278
static ChildIteratorType child_begin(NodeRef N)
Definition: ScheduleDAG.h:671
bool isCloned
True if this node has been cloned.
Definition: ScheduleDAG.h:291
bool operator!=(const SUnitIterator &x) const
Definition: ScheduleDAG.h:632
SUnitIterator operator++(int)
Definition: ScheduleDAG.h:643
Arbitrary weak DAG edge.
Definition: ScheduleDAG.h:74
const TargetMachine & TM
Target processor.
Definition: ScheduleDAG.h:561
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:648
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:680
void dump(const TargetRegisterInfo *TRI=nullptr) const
Definition: ScheduleDAG.cpp:71
SUnitIterator ChildIteratorType
Definition: ScheduleDAG.h:669
SUnitIterator & operator++()
Definition: ScheduleDAG.h:639
SDep(SUnit *S, OrderKind kind)
Definition: ScheduleDAG.h:124
const_iterator end() const
Definition: ScheduleDAG.h:751
An unknown scheduling barrier.
Definition: ScheduleDAG.h:70
bool isScheduleHigh
True if preferable to schedule high.
Definition: ScheduleDAG.h:289
bool isCommutable
Is a commutable instruction.
Definition: ScheduleDAG.h:282
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:605
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:847
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:388
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:747
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:546
typename SuperClass::iterator iterator
Definition: SmallVector.h:327
SmallVectorImpl< SDep >::const_iterator const_succ_iterator
Definition: ScheduleDAG.h:266
static void DFS(BasicBlock *Root, SetVector< BasicBlock *> &Set)
static ChildIteratorType child_end(NodeRef N)
Definition: ScheduleDAG.h:674
bool isCallOp
Is a function call operand.
Definition: ScheduleDAG.h:280
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:287
SUnit EntrySU
Special node for the region entry.
Definition: ScheduleDAG.h:567
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:410
Representation of each machine instruction.
Definition: MachineInstr.h:64
SUnit ExitSU
Special node for the region exit.
Definition: ScheduleDAG.h:568
const TargetRegisterInfo * TRI
Target processor register info.
Definition: ScheduleDAG.h:563
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:312
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:562
Kind getKind() const
Returns an enum value representing the kind of the dependence.
Definition: ScheduleDAG.h:490
bool isCtrlDep() const
Tests if this is not an SDep::Data dependence.
Definition: ScheduleDAG.h:656
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
const SDep & getSDep() const
Definition: ScheduleDAG.h:662
virtual bool isReady(SUnit *) const
Definition: ScheduleDAG.h:524
bool overlaps(const SDep &Other) const
Returns true if the specified SDep is equivalent except for latency.
Definition: ScheduleDAG.h:469
SUnit(MachineInstr *instr, unsigned nodenum)
Constructs an SUnit for post-regalloc scheduling to represent a MachineInstr.
Definition: ScheduleDAG.h:323
SmallVector< SDep, 4 > Succs
All sunit successors.
Definition: ScheduleDAG.h:261
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
Primary interface to the complete machine description for the target machine.
Definition: TargetMachine.h:59
IRTranslator LLVM IR MI
static nodes_iterator nodes_end(ScheduleDAG *G)
Definition: ScheduleDAG.h:684
bool isScheduleLow
True if preferable to schedule low.
Definition: ScheduleDAG.h:290
MachineRegisterInfo & MRI
Virtual/real register map.
Definition: ScheduleDAG.h:565
std::vector< SUnit > SUnits
The scheduling units.
Definition: ScheduleDAG.h:566
This class can compute a topological ordering for SUnits and provides methods for dynamically updatin...
Definition: ScheduleDAG.h:693
bool hasPhysRegClobbers
Has any physreg defs, used or not.
Definition: ScheduleDAG.h:285
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:366
bool isSucc(const SUnit *N) const
Tests if node N is a successor of this node.
Definition: ScheduleDAG.h:443
Scheduling unit. This is a node in the scheduling DAG.
Definition: ScheduleDAG.h:246
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:659
bool isPred(const SUnit *N) const
Tests if node N is a predecessor of this node.
Definition: ScheduleDAG.h:435