LLVM  16.0.0git
ScheduleDAG.h
Go to the documentation of this file.
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"
20 #include "llvm/ADT/SmallVector.h"
21 #include "llvm/ADT/iterator.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;
38 class MCInstrDesc;
39 struct MCSchedClassDesc;
40 class SDNode;
41 class SUnit;
42 class ScheduleDAG;
43 class TargetInstrInfo;
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.
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;
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 
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  SDNode *Node = nullptr; ///< Representative node.
247  MachineInstr *Instr = nullptr; ///< Alternatively, a MachineInstr.
248 
249  public:
250  SUnit *OrigNode = nullptr; ///< If not this, the node from which this node
251  /// was cloned. (SD scheduling only)
252 
254  nullptr; ///< nullptr or resolved SchedClass.
255 
256  SmallVector<SDep, 4> Preds; ///< All sunit predecessors.
257  SmallVector<SDep, 4> Succs; ///< All sunit successors.
258 
263 
264  unsigned NodeNum = BoundaryID; ///< Entry # of node in the node vector.
265  unsigned NodeQueueId = 0; ///< Queue id of node.
266  unsigned NumPreds = 0; ///< # of SDep::Data preds.
267  unsigned NumSuccs = 0; ///< # of SDep::Data sucss.
268  unsigned NumPredsLeft = 0; ///< # of preds not scheduled.
269  unsigned NumSuccsLeft = 0; ///< # of succs not scheduled.
270  unsigned WeakPredsLeft = 0; ///< # of weak preds not scheduled.
271  unsigned WeakSuccsLeft = 0; ///< # of weak succs not scheduled.
272  unsigned short NumRegDefsLeft = 0; ///< # of reg defs with no scheduled use.
273  unsigned short Latency = 0; ///< Node latency.
274  bool isVRegCycle : 1; ///< May use and def the same vreg.
275  bool isCall : 1; ///< Is a function call.
276  bool isCallOp : 1; ///< Is a function call operand.
277  bool isTwoAddress : 1; ///< Is a two-address instruction.
278  bool isCommutable : 1; ///< Is a commutable instruction.
279  bool hasPhysRegUses : 1; ///< Has physreg uses.
280  bool hasPhysRegDefs : 1; ///< Has physreg defs that are being used.
281  bool hasPhysRegClobbers : 1; ///< Has any physreg defs, used or not.
282  bool isPending : 1; ///< True once pending.
283  bool isAvailable : 1; ///< True once available.
284  bool isScheduled : 1; ///< True once scheduled.
285  bool isScheduleHigh : 1; ///< True if preferable to schedule high.
286  bool isScheduleLow : 1; ///< True if preferable to schedule low.
287  bool isCloned : 1; ///< True if this node has been cloned.
288  bool isUnbuffered : 1; ///< Uses an unbuffered resource.
289  bool hasReservedResource : 1; ///< Uses a reserved resource.
290  Sched::Preference SchedulingPref = Sched::None; ///< Scheduling preference.
291 
292  private:
293  bool isDepthCurrent : 1; ///< True if Depth is current.
294  bool isHeightCurrent : 1; ///< True if Height is current.
295  unsigned Depth = 0; ///< Node depth.
296  unsigned Height = 0; ///< Node height.
297 
298  public:
299  unsigned TopReadyCycle = 0; ///< Cycle relative to start when node is ready.
300  unsigned BotReadyCycle = 0; ///< Cycle relative to end when node is ready.
301 
303  nullptr; ///< Is a special copy node if != nullptr.
304  const TargetRegisterClass *CopySrcRC = nullptr;
305 
306  /// Constructs an SUnit for pre-regalloc scheduling to represent an
307  /// SDNode and any nodes flagged to it.
308  SUnit(SDNode *node, unsigned nodenum)
309  : Node(node), NodeNum(nodenum), isVRegCycle(false), isCall(false),
314  isUnbuffered(false), hasReservedResource(false), isDepthCurrent(false),
315  isHeightCurrent(false) {}
316 
317  /// Constructs an SUnit for post-regalloc scheduling to represent a
318  /// MachineInstr.
319  SUnit(MachineInstr *instr, unsigned nodenum)
320  : Instr(instr), NodeNum(nodenum), isVRegCycle(false), isCall(false),
325  isUnbuffered(false), hasReservedResource(false), isDepthCurrent(false),
326  isHeightCurrent(false) {}
327 
328  /// Constructs a placeholder SUnit.
335  isDepthCurrent(false), isHeightCurrent(false) {}
336 
337  /// Boundary nodes are placeholders for the boundary of the
338  /// scheduling region.
339  ///
340  /// BoundaryNodes can have DAG edges, including Data edges, but they do not
341  /// correspond to schedulable entities (e.g. instructions) and do not have a
342  /// valid ID. Consequently, always check for boundary nodes before accessing
343  /// an associative data structure keyed on node ID.
344  bool isBoundaryNode() const { return NodeNum == BoundaryID; }
345 
346  /// Assigns the representative SDNode for this SUnit. This may be used
347  /// during pre-regalloc scheduling.
348  void setNode(SDNode *N) {
349  assert(!Instr && "Setting SDNode of SUnit with MachineInstr!");
350  Node = N;
351  }
352 
353  /// Returns the representative SDNode for this SUnit. This may be used
354  /// during pre-regalloc scheduling.
355  SDNode *getNode() const {
356  assert(!Instr && "Reading SDNode of SUnit with MachineInstr!");
357  return Node;
358  }
359 
360  /// Returns true if this SUnit refers to a machine instruction as
361  /// opposed to an SDNode.
362  bool isInstr() const { return Instr; }
363 
364  /// Assigns the instruction for the SUnit. This may be used during
365  /// post-regalloc scheduling.
367  assert(!Node && "Setting MachineInstr of SUnit with SDNode!");
368  Instr = MI;
369  }
370 
371  /// Returns the representative MachineInstr for this SUnit. This may be used
372  /// during post-regalloc scheduling.
374  assert(!Node && "Reading MachineInstr of SUnit with SDNode!");
375  return Instr;
376  }
377 
378  /// Adds the specified edge as a pred of the current node if not already.
379  /// It also adds the current node as a successor of the specified node.
380  bool addPred(const SDep &D, bool Required = true);
381 
382  /// Adds a barrier edge to SU by calling addPred(), with latency 0
383  /// generally or latency 1 for a store followed by a load.
384  bool addPredBarrier(SUnit *SU) {
385  SDep Dep(SU, SDep::Barrier);
386  unsigned TrueMemOrderLatency =
387  ((SU->getInstr()->mayStore() && this->getInstr()->mayLoad()) ? 1 : 0);
388  Dep.setLatency(TrueMemOrderLatency);
389  return addPred(Dep);
390  }
391 
392  /// Removes the specified edge as a pred of the current node if it exists.
393  /// It also removes the current node as a successor of the specified node.
394  void removePred(const SDep &D);
395 
396  /// Returns the depth of this node, which is the length of the maximum path
397  /// up to any node which has no predecessors.
398  unsigned getDepth() const {
399  if (!isDepthCurrent)
400  const_cast<SUnit *>(this)->ComputeDepth();
401  return Depth;
402  }
403 
404  /// Returns the height of this node, which is the length of the
405  /// maximum path down to any node which has no successors.
406  unsigned getHeight() const {
407  if (!isHeightCurrent)
408  const_cast<SUnit *>(this)->ComputeHeight();
409  return Height;
410  }
411 
412  /// If NewDepth is greater than this node's depth value, sets it to
413  /// be the new depth value. This also recursively marks successor nodes
414  /// dirty.
415  void setDepthToAtLeast(unsigned NewDepth);
416 
417  /// If NewHeight is greater than this node's height value, set it to be
418  /// the new height value. This also recursively marks predecessor nodes
419  /// dirty.
420  void setHeightToAtLeast(unsigned NewHeight);
421 
422  /// Sets a flag in this node to indicate that its stored Depth value
423  /// will require recomputation the next time getDepth() is called.
424  void setDepthDirty();
425 
426  /// Sets a flag in this node to indicate that its stored Height value
427  /// will require recomputation the next time getHeight() is called.
428  void setHeightDirty();
429 
430  /// Tests if node N is a predecessor of this node.
431  bool isPred(const SUnit *N) const {
432  for (const SDep &Pred : Preds)
433  if (Pred.getSUnit() == N)
434  return true;
435  return false;
436  }
437 
438  /// Tests if node N is a successor of this node.
439  bool isSucc(const SUnit *N) const {
440  for (const SDep &Succ : Succs)
441  if (Succ.getSUnit() == N)
442  return true;
443  return false;
444  }
445 
446  bool isTopReady() const {
447  return NumPredsLeft == 0;
448  }
449  bool isBottomReady() const {
450  return NumSuccsLeft == 0;
451  }
452 
453  /// Orders this node's predecessor edges such that the critical path
454  /// edge occurs first.
455  void biasCriticalPath();
456 
457  void dumpAttributes() const;
458 
459  private:
460  void ComputeDepth();
461  void ComputeHeight();
462  };
463 
464  /// Returns true if the specified SDep is equivalent except for latency.
465  inline bool SDep::overlaps(const SDep &Other) const {
466  if (Dep != Other.Dep)
467  return false;
468  switch (Dep.getInt()) {
469  case Data:
470  case Anti:
471  case Output:
472  return Contents.Reg == Other.Contents.Reg;
473  case Order:
474  return Contents.OrdKind == Other.Contents.OrdKind;
475  }
476  llvm_unreachable("Invalid dependency kind!");
477  }
478 
479  //// Returns the SUnit to which this edge points.
480  inline SUnit *SDep::getSUnit() const { return Dep.getPointer(); }
481 
482  //// Assigns the SUnit to which this edge points.
483  inline void SDep::setSUnit(SUnit *SU) { Dep.setPointer(SU); }
484 
485  /// Returns an enum value representing the kind of the dependence.
486  inline SDep::Kind SDep::getKind() const { return Dep.getInt(); }
487 
488  //===--------------------------------------------------------------------===//
489 
490  /// This interface is used to plug different priorities computation
491  /// algorithms into the list scheduler. It implements the interface of a
492  /// standard priority queue, where nodes are inserted in arbitrary order and
493  /// returned in priority order. The computation of the priority and the
494  /// representation of the queue are totally up to the implementation to
495  /// decide.
497  virtual void anchor();
498 
499  unsigned CurCycle = 0;
500  bool HasReadyFilter;
501 
502  public:
503  SchedulingPriorityQueue(bool rf = false) : HasReadyFilter(rf) {}
504 
505  virtual ~SchedulingPriorityQueue() = default;
506 
507  virtual bool isBottomUp() const = 0;
508 
509  virtual void initNodes(std::vector<SUnit> &SUnits) = 0;
510  virtual void addNode(const SUnit *SU) = 0;
511  virtual void updateNode(const SUnit *SU) = 0;
512  virtual void releaseState() = 0;
513 
514  virtual bool empty() const = 0;
515 
516  bool hasReadyFilter() const { return HasReadyFilter; }
517 
518  virtual bool tracksRegPressure() const { return false; }
519 
520  virtual bool isReady(SUnit *) const {
521  assert(!HasReadyFilter && "The ready filter must override isReady()");
522  return true;
523  }
524 
525  virtual void push(SUnit *U) = 0;
526 
527  void push_all(const std::vector<SUnit *> &Nodes) {
528  for (SUnit *SU : Nodes)
529  push(SU);
530  }
531 
532  virtual SUnit *pop() = 0;
533 
534  virtual void remove(SUnit *SU) = 0;
535 
536  virtual void dump(ScheduleDAG *) const {}
537 
538  /// As each node is scheduled, this method is invoked. This allows the
539  /// priority function to adjust the priority of related unscheduled nodes,
540  /// for example.
541  virtual void scheduledNode(SUnit *) {}
542 
543  virtual void unscheduledNode(SUnit *) {}
544 
545  void setCurCycle(unsigned Cycle) {
546  CurCycle = Cycle;
547  }
548 
549  unsigned getCurCycle() const {
550  return CurCycle;
551  }
552  };
553 
554  class ScheduleDAG {
555  public:
556  const LLVMTargetMachine &TM; ///< Target processor
557  const TargetInstrInfo *TII; ///< Target instruction information
558  const TargetRegisterInfo *TRI; ///< Target processor register info
559  MachineFunction &MF; ///< Machine function
560  MachineRegisterInfo &MRI; ///< Virtual/real register map
561  std::vector<SUnit> SUnits; ///< The scheduling units.
562  SUnit EntrySU; ///< Special node for the region entry.
563  SUnit ExitSU; ///< Special node for the region exit.
564 
565 #ifdef NDEBUG
566  static const bool StressSched = false;
567 #else
569 #endif
570 
571  explicit ScheduleDAG(MachineFunction &mf);
572 
573  virtual ~ScheduleDAG();
574 
575  /// Clears the DAG state (between regions).
576  void clearDAG();
577 
578  /// Returns the MCInstrDesc of this SUnit.
579  /// Returns NULL for SDNodes without a machine opcode.
580  const MCInstrDesc *getInstrDesc(const SUnit *SU) const {
581  if (SU->isInstr()) return &SU->getInstr()->getDesc();
582  return getNodeDesc(SU->getNode());
583  }
584 
585  /// Pops up a GraphViz/gv window with the ScheduleDAG rendered using 'dot'.
586  virtual void viewGraph(const Twine &Name, const Twine &Title);
587  virtual void viewGraph();
588 
589  virtual void dumpNode(const SUnit &SU) const = 0;
590  virtual void dump() const = 0;
591  void dumpNodeName(const SUnit &SU) const;
592 
593  /// Returns a label for an SUnit node in a visualization of the ScheduleDAG.
594  virtual std::string getGraphNodeLabel(const SUnit *SU) const = 0;
595 
596  /// Returns a label for the region of code covered by the DAG.
597  virtual std::string getDAGName() const = 0;
598 
599  /// Adds custom features for a visualization of the ScheduleDAG.
601 
602 #ifndef NDEBUG
603  /// Verifies that all SUnits were scheduled and that their state is
604  /// consistent. Returns the number of scheduled SUnits.
605  unsigned VerifyScheduledDAG(bool isBottomUp);
606 #endif
607 
608  protected:
609  void dumpNodeAll(const SUnit &SU) const;
610 
611  private:
612  /// Returns the MCInstrDesc of this SDNode or NULL.
613  const MCInstrDesc *getNodeDesc(const SDNode *Node) const;
614  };
615 
617  SUnit *Node;
618  unsigned Operand;
619 
620  SUnitIterator(SUnit *N, unsigned Op) : Node(N), Operand(Op) {}
621 
622  public:
623  using iterator_category = std::forward_iterator_tag;
624  using value_type = SUnit;
625  using difference_type = std::ptrdiff_t;
626  using pointer = value_type *;
628 
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; }
672  return SUnitIterator::begin(N);
673  }
675  return SUnitIterator::end(N);
676  }
677  };
678 
679  template <> struct GraphTraits<ScheduleDAG*> : public GraphTraits<SUnit*> {
682  return nodes_iterator(G->SUnits.begin());
683  }
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  // Have any new nodes been added?
699  bool Dirty = false;
700 
701  // Outstanding added edges, that have not been applied to the ordering.
703 
704  /// Maps topological index to the node number.
705  std::vector<int> Index2Node;
706  /// Maps the node number to its topological index.
707  std::vector<int> Node2Index;
708  /// a set of nodes visited during a DFS traversal.
709  BitVector Visited;
710 
711  /// Makes a DFS traversal and mark all nodes affected by the edge insertion.
712  /// These nodes will later get new topological indexes by means of the Shift
713  /// method.
714  void DFS(const SUnit *SU, int UpperBound, bool& HasLoop);
715 
716  /// Reassigns topological indexes for the nodes in the DAG to
717  /// preserve the topological ordering.
718  void Shift(BitVector& Visited, int LowerBound, int UpperBound);
719 
720  /// Assigns the topological index to the node n.
721  void Allocate(int n, int index);
722 
723  /// Fix the ordering, by either recomputing from scratch or by applying
724  /// any outstanding updates. Uses a heuristic to estimate what will be
725  /// cheaper.
726  void FixOrder();
727 
728  public:
729  ScheduleDAGTopologicalSort(std::vector<SUnit> &SUnits, SUnit *ExitSU);
730 
731  /// Add a SUnit without predecessors to the end of the topological order. It
732  /// also must be the first new node added to the DAG.
733  void AddSUnitWithoutPredecessors(const SUnit *SU);
734 
735  /// Creates the initial topological ordering from the DAG to be scheduled.
737 
738  /// Returns an array of SUs that are both in the successor
739  /// subtree of StartSU and in the predecessor subtree of TargetSU.
740  /// StartSU and TargetSU are not in the array.
741  /// Success is false if TargetSU is not in the successor subtree of
742  /// StartSU, else it is true.
743  std::vector<int> GetSubGraph(const SUnit &StartSU, const SUnit &TargetSU,
744  bool &Success);
745 
746  /// Checks if \p SU is reachable from \p TargetSU.
747  bool IsReachable(const SUnit *SU, const SUnit *TargetSU);
748 
749  /// Returns true if addPred(TargetSU, SU) creates a cycle.
750  bool WillCreateCycle(SUnit *TargetSU, SUnit *SU);
751 
752  /// Updates the topological ordering to accommodate an edge to be
753  /// added from SUnit \p X to SUnit \p Y.
754  void AddPred(SUnit *Y, SUnit *X);
755 
756  /// Queues an update to the topological ordering to accommodate an edge to
757  /// be added from SUnit \p X to SUnit \p Y.
758  void AddPredQueued(SUnit *Y, SUnit *X);
759 
760  /// Updates the topological ordering to accommodate an an edge to be
761  /// removed from the specified node \p N from the predecessors of the
762  /// current node \p M.
763  void RemovePred(SUnit *M, SUnit *N);
764 
765  /// Mark the ordering as temporarily broken, after a new node has been
766  /// added.
767  void MarkDirty() { Dirty = true; }
768 
769  typedef std::vector<int>::iterator iterator;
770  typedef std::vector<int>::const_iterator const_iterator;
771  iterator begin() { return Index2Node.begin(); }
772  const_iterator begin() const { return Index2Node.begin(); }
773  iterator end() { return Index2Node.end(); }
774  const_iterator end() const { return Index2Node.end(); }
775 
776  typedef std::vector<int>::reverse_iterator reverse_iterator;
777  typedef std::vector<int>::const_reverse_iterator const_reverse_iterator;
778  reverse_iterator rbegin() { return Index2Node.rbegin(); }
779  const_reverse_iterator rbegin() const { return Index2Node.rbegin(); }
780  reverse_iterator rend() { return Index2Node.rend(); }
781  const_reverse_iterator rend() const { return Index2Node.rend(); }
782  };
783 
784 } // end namespace llvm
785 
786 #endif // LLVM_CODEGEN_SCHEDULEDAG_H
llvm::ScheduleDAG::MRI
MachineRegisterInfo & MRI
Virtual/real register map.
Definition: ScheduleDAG.h:560
llvm::SchedulingPriorityQueue::scheduledNode
virtual void scheduledNode(SUnit *)
As each node is scheduled, this method is invoked.
Definition: ScheduleDAG.h:541
llvm::ScheduleDAGTopologicalSort::RemovePred
void RemovePred(SUnit *M, SUnit *N)
Updates the topological ordering to accommodate an an edge to be removed from the specified node N fr...
Definition: ScheduleDAG.cpp:566
llvm::SUnit::dumpAttributes
void dumpAttributes() const
Definition: ScheduleDAG.cpp:341
MI
IRTranslator LLVM IR MI
Definition: IRTranslator.cpp:108
MachineInstr.h
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
llvm::ScheduleDAGTopologicalSort::WillCreateCycle
bool WillCreateCycle(SUnit *TargetSU, SUnit *SU)
Returns true if addPred(TargetSU, SU) creates a cycle.
Definition: ScheduleDAG.cpp:703
llvm::SDep::OrdKind
unsigned OrdKind
Additional information about Order dependencies.
Definition: ScheduleDAG.h:90
llvm::SUnit::isScheduleLow
bool isScheduleLow
True if preferable to schedule low.
Definition: ScheduleDAG.h:286
M
We currently emits eax Perhaps this is what we really should generate is Is imull three or four cycles eax eax The current instruction priority is based on pattern complexity The former is more complex because it folds a load so the latter will not be emitted Perhaps we should use AddedComplexity to give LEA32r a higher priority We should always try to match LEA first since the LEA matching code does some estimate to determine whether the match is profitable if we care more about code then imull is better It s two bytes shorter than movl leal On a Pentium M
Definition: README.txt:252
llvm::SUnit::NumPredsLeft
unsigned NumPredsLeft
Definition: ScheduleDAG.h:268
llvm::GraphWriter
Definition: ScheduleDAG.h:34
llvm::ScheduleDAGTopologicalSort::begin
iterator begin()
Definition: ScheduleDAG.h:771
llvm::SDep::MustAliasMem
@ MustAliasMem
Nonvolatile load/Store instructions that must alias.
Definition: ScheduleDAG.h:71
llvm::SUnitIterator::getSDep
const SDep & getSDep() const
Definition: ScheduleDAG.h:662
llvm::SDep::Artificial
@ Artificial
Arbitrary strong DAG edge (no real dependence).
Definition: ScheduleDAG.h:72
llvm::SDep::setReg
void setReg(unsigned Reg)
Assigns the associated register for this edge.
Definition: ScheduleDAG.h:228
llvm::SUnit::isAvailable
bool isAvailable
True once available.
Definition: ScheduleDAG.h:283
llvm::Latency
@ Latency
Definition: SIMachineScheduler.h:34
llvm::MachineRegisterInfo
MachineRegisterInfo - Keep track of information for virtual and physical registers,...
Definition: MachineRegisterInfo.h:50
llvm::SchedulingPriorityQueue::dump
virtual void dump(ScheduleDAG *) const
Definition: ScheduleDAG.h:536
llvm::MachineInstr::mayLoad
bool mayLoad(QueryType Type=AnyInBundle) const
Return true if this instruction could possibly read memory.
Definition: MachineInstr.h:1056
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1182
llvm::ScheduleDAGTopologicalSort::const_iterator
std::vector< int >::const_iterator const_iterator
Definition: ScheduleDAG.h:770
llvm::ScheduleDAGTopologicalSort::IsReachable
bool IsReachable(const SUnit *SU, const SUnit *TargetSU)
Checks if SU is reachable from TargetSU.
Definition: ScheduleDAG.cpp:723
llvm::ScheduleDAG::getGraphNodeLabel
virtual std::string getGraphNodeLabel(const SUnit *SU) const =0
Returns a label for an SUnit node in a visualization of the ScheduleDAG.
ErrorHandling.h
llvm::SUnit::const_pred_iterator
SmallVectorImpl< SDep >::const_iterator const_pred_iterator
Definition: ScheduleDAG.h:261
llvm::GraphTraits< SUnit * >
Definition: ScheduleDAG.h:667
llvm::GraphTraits< ScheduleDAG * >::nodes_iterator
pointer_iterator< std::vector< SUnit >::iterator > nodes_iterator
Definition: ScheduleDAG.h:680
llvm::SUnit::NumSuccsLeft
unsigned NumSuccsLeft
Definition: ScheduleDAG.h:269
llvm::SDep::Anti
@ Anti
A register anti-dependence (aka WAR).
Definition: ScheduleDAG.h:54
llvm::SUnit::isCommutable
bool isCommutable
Is a commutable instruction.
Definition: ScheduleDAG.h:278
llvm::SUnit::isCall
bool isCall
Is a function call.
Definition: ScheduleDAG.h:275
llvm::SDNode
Represents one node in the SelectionDAG.
Definition: SelectionDAGNodes.h:462
llvm::TargetRegisterInfo
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
Definition: TargetRegisterInfo.h:237
llvm::Depth
@ Depth
Definition: SIMachineScheduler.h:36
llvm::SDep::Kind
Kind
These are the different kinds of scheduling dependencies.
Definition: ScheduleDAG.h:52
llvm::MachineInstr::getDesc
const MCInstrDesc & getDesc() const
Returns the target instruction descriptor of this MachineInstr.
Definition: MachineInstr.h:513
llvm::SchedulingPriorityQueue::addNode
virtual void addNode(const SUnit *SU)=0
llvm::SchedulingPriorityQueue::tracksRegPressure
virtual bool tracksRegPressure() const
Definition: ScheduleDAG.h:518
llvm::GraphTraits< ScheduleDAG * >::nodes_end
static nodes_iterator nodes_end(ScheduleDAG *G)
Definition: ScheduleDAG.h:684
llvm::ScheduleDAGTopologicalSort::end
const_iterator end() const
Definition: ScheduleDAG.h:774
llvm::SUnit::Succs
SmallVector< SDep, 4 > Succs
All sunit successors.
Definition: ScheduleDAG.h:257
llvm::SUnitIterator::operator++
SUnitIterator operator++(int)
Definition: ScheduleDAG.h:643
llvm::SUnitIterator::operator*
pointer operator*() const
Definition: ScheduleDAG.h:634
llvm::SUnitIterator::getOperand
unsigned getOperand() const
Definition: ScheduleDAG.h:652
llvm::SDep::isNormalMemory
bool isNormalMemory() const
Tests if this is an Order dependence between two memory accesses where both sides of the dependence a...
Definition: ScheduleDAG.h:168
llvm::SUnit::getDepth
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:398
llvm::SchedulingPriorityQueue::isReady
virtual bool isReady(SUnit *) const
Definition: ScheduleDAG.h:520
llvm::ScheduleDAG::addCustomGraphFeatures
virtual void addCustomGraphFeatures(GraphWriter< ScheduleDAG * > &) const
Adds custom features for a visualization of the ScheduleDAG.
Definition: ScheduleDAG.h:600
llvm::SchedulingPriorityQueue::SchedulingPriorityQueue
SchedulingPriorityQueue(bool rf=false)
Definition: ScheduleDAG.h:503
llvm::SDep::setSUnit
void setSUnit(SUnit *SU)
Definition: ScheduleDAG.h:483
tmp
alloca< 16 x float >, align 16 %tmp2=alloca< 16 x float >, align 16 store< 16 x float > %A,< 16 x float > *%tmp %s=bitcast< 16 x float > *%tmp to i8 *%s2=bitcast< 16 x float > *%tmp2 to i8 *call void @llvm.memcpy.i64(i8 *%s, i8 *%s2, i64 64, i32 16) %R=load< 16 x float > *%tmp2 ret< 16 x float > %R } declare void @llvm.memcpy.i64(i8 *nocapture, i8 *nocapture, i64, i32) nounwind which compiles to:_foo:subl $140, %esp movaps %xmm3, 112(%esp) movaps %xmm2, 96(%esp) movaps %xmm1, 80(%esp) movaps %xmm0, 64(%esp) movl 60(%esp), %eax movl %eax, 124(%esp) movl 56(%esp), %eax movl %eax, 120(%esp) movl 52(%esp), %eax< many many more 32-bit copies > movaps(%esp), %xmm0 movaps 16(%esp), %xmm1 movaps 32(%esp), %xmm2 movaps 48(%esp), %xmm3 addl $140, %esp ret On Nehalem, it may even be cheaper to just use movups when unaligned than to fall back to lower-granularity chunks. Implement processor-specific optimizations for parity with GCC on these processors. GCC does two optimizations:1. ix86_pad_returns inserts a noop before ret instructions if immediately preceded by a conditional branch or is the target of a jump. 2. ix86_avoid_jump_misspredicts inserts noops in cases where a 16-byte block of code contains more than 3 branches. The first one is done for all AMDs, Core2, and "Generic" The second one is done for:Atom, Pentium Pro, all AMDs, Pentium 4, Nocona, Core 2, and "Generic" Testcase:int x(int a) { return(a &0xf0)> >4 tmp
Definition: README.txt:1347
llvm::ScheduleDAG::~ScheduleDAG
virtual ~ScheduleDAG()
TRI
unsigned const TargetRegisterInfo * TRI
Definition: MachineSink.cpp:1628
llvm::SUnit::isTopReady
bool isTopReady() const
Definition: ScheduleDAG.h:446
llvm::ScheduleDAGTopologicalSort::AddPredQueued
void AddPredQueued(SUnit *Y, SUnit *X)
Queues an update to the topological ordering to accommodate an edge to be added from SUnit X to SUnit...
Definition: ScheduleDAG.cpp:536
llvm::ScheduleDAG::ScheduleDAG
ScheduleDAG(MachineFunction &mf)
Definition: ScheduleDAG.cpp:53
llvm::SDep::isArtificial
bool isArtificial() const
Tests if this is an Order dependence that is marked as "artificial", meaning it isn't necessary for c...
Definition: ScheduleDAG.h:200
PointerIntPair.h
llvm::ScheduleDAGTopologicalSort::MarkDirty
void MarkDirty()
Mark the ordering as temporarily broken, after a new node has been added.
Definition: ScheduleDAG.h:767
llvm::ScheduleDAGTopologicalSort
This class can compute a topological ordering for SUnits and provides methods for dynamically updatin...
Definition: ScheduleDAG.h:693
llvm::SchedulingPriorityQueue::getCurCycle
unsigned getCurCycle() const
Definition: ScheduleDAG.h:549
llvm::SUnitIterator::isCtrlDep
bool isCtrlDep() const
Tests if this is not an SDep::Data dependence.
Definition: ScheduleDAG.h:656
TargetLowering.h
llvm::SUnit::isBoundaryNode
bool isBoundaryNode() const
Boundary nodes are placeholders for the boundary of the scheduling region.
Definition: ScheduleDAG.h:344
llvm::SUnit::BotReadyCycle
unsigned BotReadyCycle
Cycle relative to end when node is ready.
Definition: ScheduleDAG.h:300
llvm::SDep::Weak
@ Weak
Arbitrary weak DAG edge.
Definition: ScheduleDAG.h:73
llvm::SUnit::removePred
void removePred(const SDep &D)
Removes the specified edge as a pred of the current node if it exists.
Definition: ScheduleDAG.cpp:175
llvm::TargetInstrInfo
TargetInstrInfo - Interface to description of machine instruction set.
Definition: TargetInstrInfo.h:98
llvm::SDep::overlaps
bool overlaps(const SDep &Other) const
Returns true if the specified SDep is equivalent except for latency.
Definition: ScheduleDAG.h:465
llvm::SUnit::setDepthDirty
void setDepthDirty()
Sets a flag in this node to indicate that its stored Depth value will require recomputation the next ...
Definition: ScheduleDAG.cpp:217
llvm::SUnitIterator::difference_type
std::ptrdiff_t difference_type
Definition: ScheduleDAG.h:625
llvm::SUnitIterator::operator++
SUnitIterator & operator++()
Definition: ScheduleDAG.h:639
llvm::SUnit::isBottomReady
bool isBottomReady() const
Definition: ScheduleDAG.h:449
llvm::SUnit::isUnbuffered
bool isUnbuffered
Uses an unbuffered resource.
Definition: ScheduleDAG.h:288
llvm::GraphTraits< SUnit * >::getEntryNode
static NodeRef getEntryNode(SUnit *N)
Definition: ScheduleDAG.h:670
llvm::SUnitIterator::operator==
bool operator==(const SUnitIterator &x) const
Definition: ScheduleDAG.h:629
llvm::SUnit::isScheduleHigh
bool isScheduleHigh
True if preferable to schedule high.
Definition: ScheduleDAG.h:285
llvm::SUnit::setHeightToAtLeast
void setHeightToAtLeast(unsigned NewHeight)
If NewHeight is greater than this node's height value, set it to be the new height value.
Definition: ScheduleDAG.cpp:255
llvm::SUnit::Latency
unsigned short Latency
Node latency.
Definition: ScheduleDAG.h:273
llvm::cl::Required
@ Required
Definition: CommandLine.h:117
llvm::SUnit::setDepthToAtLeast
void setDepthToAtLeast(unsigned NewDepth)
If NewDepth is greater than this node's depth value, sets it to be the new depth value.
Definition: ScheduleDAG.cpp:247
llvm::SUnit::NodeNum
unsigned NodeNum
Entry # of node in the node vector.
Definition: ScheduleDAG.h:264
Y
static GCMetadataPrinterRegistry::Add< OcamlGCMetadataPrinter > Y("ocaml", "ocaml 3.10-compatible collector")
llvm::MCSchedClassDesc
Summarize the scheduling resources required for an instruction of a particular scheduling class.
Definition: MCSchedule.h:109
llvm::TargetRegisterClass
Definition: TargetRegisterInfo.h:46
false
Definition: StackSlotColoring.cpp:141
llvm::SUnit::NumPreds
unsigned NumPreds
Definition: ScheduleDAG.h:266
llvm::MCInstrDesc
Describe properties that are true of each instruction in the target description file.
Definition: MCInstrDesc.h:197
llvm::SchedulingPriorityQueue::empty
virtual bool empty() const =0
llvm::SUnit::setInstr
void setInstr(MachineInstr *MI)
Assigns the instruction for the SUnit.
Definition: ScheduleDAG.h:366
llvm::ScheduleDAGTopologicalSort::AddPred
void AddPred(SUnit *Y, SUnit *X)
Updates the topological ordering to accommodate an edge to be added from SUnit X to SUnit Y.
Definition: ScheduleDAG.cpp:548
llvm::GenericCycle
A possibly irreducible generalization of a Loop.
Definition: GenericCycleInfo.h:48
llvm::SUnitIterator::operator->
pointer operator->() const
Definition: ScheduleDAG.h:637
BitVector.h
llvm::SDep::Output
@ Output
A register output-dependence (aka WAW).
Definition: ScheduleDAG.h:55
llvm::SDep::Data
@ Data
Regular data dependence (aka true-dependence).
Definition: ScheduleDAG.h:53
llvm::ScheduleDAG::getInstrDesc
const MCInstrDesc * getInstrDesc(const SUnit *SU) const
Returns the MCInstrDesc of this SUnit.
Definition: ScheduleDAG.h:580
llvm::GraphTraits< SUnit * >::child_begin
static ChildIteratorType child_begin(NodeRef N)
Definition: ScheduleDAG.h:671
llvm::SUnit::isVRegCycle
bool isVRegCycle
May use and def the same vreg.
Definition: ScheduleDAG.h:274
llvm::BitVector
Definition: BitVector.h:75
llvm::ScheduleDAGTopologicalSort::const_reverse_iterator
std::vector< int >::const_reverse_iterator const_reverse_iterator
Definition: ScheduleDAG.h:777
llvm::SUnit::OrigNode
SUnit * OrigNode
If not this, the node from which this node was cloned.
Definition: ScheduleDAG.h:250
llvm::SUnit::hasPhysRegClobbers
bool hasPhysRegClobbers
Has any physreg defs, used or not.
Definition: ScheduleDAG.h:281
llvm::SUnit::isCallOp
bool isCallOp
Is a function call operand.
Definition: ScheduleDAG.h:276
X
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
llvm::ScheduleDAGTopologicalSort::reverse_iterator
std::vector< int >::reverse_iterator reverse_iterator
Definition: ScheduleDAG.h:776
llvm::ScheduleDAG::VerifyScheduledDAG
unsigned VerifyScheduledDAG(bool isBottomUp)
Verifies that all SUnits were scheduled and that their state is consistent.
Definition: ScheduleDAG.cpp:390
llvm::SDep::Order
@ Order
Any other ordering dependency.
Definition: ScheduleDAG.h:56
llvm::SUnit::getHeight
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:406
llvm::SchedulingPriorityQueue::push
virtual void push(SUnit *U)=0
llvm::SUnit::TopReadyCycle
unsigned TopReadyCycle
Cycle relative to start when node is ready.
Definition: ScheduleDAG.h:299
llvm::ScheduleDAGTopologicalSort::ScheduleDAGTopologicalSort
ScheduleDAGTopologicalSort(std::vector< SUnit > &SUnits, SUnit *ExitSU)
Definition: ScheduleDAG.cpp:747
llvm::ScheduleDAG::viewGraph
virtual void viewGraph()
Out-of-line implementation with no arguments is handy for gdb.
Definition: ScheduleDAGPrinter.cpp:90
G
const DataFlowGraph & G
Definition: RDFGraph.cpp:200
llvm::pointer_iterator
Definition: iterator.h:344
llvm::SUnit::isPred
bool isPred(const SUnit *N) const
Tests if node N is a predecessor of this node.
Definition: ScheduleDAG.h:431
llvm::SUnit::isPending
bool isPending
True once pending.
Definition: ScheduleDAG.h:282
llvm::SUnit::succ_iterator
SmallVectorImpl< SDep >::iterator succ_iterator
Definition: ScheduleDAG.h:260
llvm::SUnit::WeakSuccsLeft
unsigned WeakSuccsLeft
Definition: ScheduleDAG.h:271
llvm::SUnitIterator::end
static SUnitIterator end(SUnit *N)
Definition: ScheduleDAG.h:648
llvm::SUnit::CopyDstRC
const TargetRegisterClass * CopyDstRC
Is a special copy node if != nullptr.
Definition: ScheduleDAG.h:302
llvm::MachineInstr
Representation of each machine instruction.
Definition: MachineInstr.h:66
index
splat index
Definition: README_ALTIVEC.txt:181
llvm::SchedulingPriorityQueue::~SchedulingPriorityQueue
virtual ~SchedulingPriorityQueue()=default
D
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
llvm::SUnit::NumRegDefsLeft
unsigned short NumRegDefsLeft
Definition: ScheduleDAG.h:272
llvm::SchedulingPriorityQueue::isBottomUp
virtual bool isBottomUp() const =0
llvm::SUnit::setNode
void setNode(SDNode *N)
Assigns the representative SDNode for this SUnit.
Definition: ScheduleDAG.h:348
iterator.h
llvm::GraphTraits< ScheduleDAG * >::nodes_begin
static nodes_iterator nodes_begin(ScheduleDAG *G)
Definition: ScheduleDAG.h:681
llvm::SUnit::getInstr
MachineInstr * getInstr() const
Returns the representative MachineInstr for this SUnit.
Definition: ScheduleDAG.h:373
llvm::SDep::getReg
unsigned getReg() const
Returns the register associated with this edge.
Definition: ScheduleDAG.h:218
llvm::SUnit::isScheduled
bool isScheduled
True once scheduled.
Definition: ScheduleDAG.h:284
llvm::SchedulingPriorityQueue::hasReadyFilter
bool hasReadyFilter() const
Definition: ScheduleDAG.h:516
node
This currently compiles esp xmm0 movsd esp eax eax esp ret We should use not the dag combiner This is because dagcombine2 needs to be able to see through the X86ISD::Wrapper node
Definition: README-SSE.txt:406
llvm::SDep::MayAliasMem
@ MayAliasMem
Nonvolatile load/Store instructions that may alias.
Definition: ScheduleDAG.h:70
llvm::ScheduleDAGTopologicalSort::iterator
std::vector< int >::iterator iterator
Definition: ScheduleDAG.h:769
llvm::SUnit::SUnit
SUnit(MachineInstr *instr, unsigned nodenum)
Constructs an SUnit for post-regalloc scheduling to represent a MachineInstr.
Definition: ScheduleDAG.h:319
llvm::SUnit::hasPhysRegUses
bool hasPhysRegUses
Has physreg uses.
Definition: ScheduleDAG.h:279
llvm::Sched::None
@ None
Definition: TargetLowering.h:97
llvm::SUnit::biasCriticalPath
void biasCriticalPath()
Orders this node's predecessor edges such that the critical path edge occurs first.
Definition: ScheduleDAG.cpp:325
llvm::SmallVectorImpl::const_iterator
typename SuperClass::const_iterator const_iterator
Definition: SmallVector.h:565
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::SUnitIterator::begin
static SUnitIterator begin(SUnit *N)
Definition: ScheduleDAG.h:647
llvm::SUnit::CopySrcRC
const TargetRegisterClass * CopySrcRC
Definition: ScheduleDAG.h:304
llvm::ScheduleDAG::dumpNodeAll
void dumpNodeAll(const SUnit &SU) const
Definition: ScheduleDAG.cpp:363
llvm::SUnitIterator::operator!=
bool operator!=(const SUnitIterator &x) const
Definition: ScheduleDAG.h:632
llvm::SDep::operator==
bool operator==(const SDep &Other) const
Definition: ScheduleDAG.h:131
llvm::GraphTraits< SUnit * >::ChildIteratorType
SUnitIterator ChildIteratorType
Definition: ScheduleDAG.h:669
llvm::SUnit::const_succ_iterator
SmallVectorImpl< SDep >::const_iterator const_succ_iterator
Definition: ScheduleDAG.h:262
llvm::SDep::isCluster
bool isCluster() const
Tests if this is an Order dependence that is marked as "cluster", meaning it is artificial and wants ...
Definition: ScheduleDAG.h:206
llvm::SchedulingPriorityQueue::pop
virtual SUnit * pop()=0
llvm::MachineFunction
Definition: MachineFunction.h:257
llvm::SDep::operator!=
bool operator!=(const SDep &Other) const
Definition: ScheduleDAG.h:135
llvm::ScheduleDAG::StressSched
bool StressSched
Definition: ScheduleDAG.h:568
llvm::SUnit::SUnit
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:308
llvm::ScheduleDAG
Definition: ScheduleDAG.h:554
llvm::SUnitIterator::getNode
const SUnit * getNode() const
Definition: ScheduleDAG.h:653
llvm::ScheduleDAG::dumpNode
virtual void dumpNode(const SUnit &SU) const =0
llvm::ScheduleDAG::TRI
const TargetRegisterInfo * TRI
Target processor register info.
Definition: ScheduleDAG.h:558
llvm::ScheduleDAGTopologicalSort::rend
const_reverse_iterator rend() const
Definition: ScheduleDAG.h:781
llvm::SDep::getSUnit
SUnit * getSUnit() const
Definition: ScheduleDAG.h:480
llvm::SDep::OrderKind
OrderKind
Definition: ScheduleDAG.h:68
llvm::SUnitIterator::iterator_category
std::forward_iterator_tag iterator_category
Definition: ScheduleDAG.h:623
llvm::SUnit::SchedClass
const MCSchedClassDesc * SchedClass
nullptr or resolved SchedClass.
Definition: ScheduleDAG.h:253
llvm::ScheduleDAG::MF
MachineFunction & MF
Machine function.
Definition: ScheduleDAG.h:559
llvm_unreachable
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Definition: ErrorHandling.h:143
llvm::ScheduleDAGTopologicalSort::begin
const_iterator begin() const
Definition: ScheduleDAG.h:772
llvm::SDep::Barrier
@ Barrier
An unknown scheduling barrier.
Definition: ScheduleDAG.h:69
llvm::SDep::SDep
SDep(SUnit *S, OrderKind kind)
Definition: ScheduleDAG.h:123
S
add sub stmia L5 ldr r0 bl L_printf $stub Instead of a and a wouldn t it be better to do three moves *Return an aggregate type is even return S
Definition: README.txt:210
llvm::ScheduleDAG::EntrySU
SUnit EntrySU
Special node for the region entry.
Definition: ScheduleDAG.h:562
Node
Definition: ItaniumDemangle.h:155
llvm::SDep::isAssignedRegDep
bool isAssignedRegDep() const
Tests if this is a Data dependence that is associated with a register.
Definition: ScheduleDAG.h:211
llvm::SUnit::SchedulingPref
Sched::Preference SchedulingPref
Scheduling preference.
Definition: ScheduleDAG.h:290
llvm::ScheduleDAG::getDAGName
virtual std::string getDAGName() const =0
Returns a label for the region of code covered by the DAG.
llvm::SDep::Reg
unsigned Reg
For Data, Anti, and Output dependencies, the associated register.
Definition: ScheduleDAG.h:87
llvm::SDep
Scheduling dependency.
Definition: ScheduleDAG.h:49
llvm::SUnit::WeakPredsLeft
unsigned WeakPredsLeft
Definition: ScheduleDAG.h:270
llvm::Twine
Twine - A lightweight data structure for efficiently representing the concatenation of temporary valu...
Definition: Twine.h:81
llvm::ScheduleDAG::SUnits
std::vector< SUnit > SUnits
The scheduling units.
Definition: ScheduleDAG.h:561
llvm::SchedulingPriorityQueue::remove
virtual void remove(SUnit *SU)=0
llvm::SchedulingPriorityQueue::releaseState
virtual void releaseState()=0
llvm::ScheduleDAGTopologicalSort::rbegin
const_reverse_iterator rbegin() const
Definition: ScheduleDAG.h:779
llvm::GraphProgram::Name
Name
Definition: GraphWriter.h:50
llvm::SUnit::NumSuccs
unsigned NumSuccs
Definition: ScheduleDAG.h:267
llvm::GraphTraits< SUnit * >::NodeRef
SUnit * NodeRef
Definition: ScheduleDAG.h:668
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:348
llvm::SUnit::getNode
SDNode * getNode() const
Returns the representative SDNode for this SUnit.
Definition: ScheduleDAG.h:355
llvm::SUnit::setHeightDirty
void setHeightDirty()
Sets a flag in this node to indicate that its stored Height value will require recomputation the next...
Definition: ScheduleDAG.cpp:232
llvm::MachineInstr::mayStore
bool mayStore(QueryType Type=AnyInBundle) const
Return true if this instruction could possibly modify memory.
Definition: MachineInstr.h:1069
llvm::SDep::setLatency
void setLatency(unsigned Lat)
Sets the latency for this edge.
Definition: ScheduleDAG.h:147
llvm::ScheduleDAG::TII
const TargetInstrInfo * TII
Target instruction information.
Definition: ScheduleDAG.h:557
Success
#define Success
Definition: AArch64Disassembler.cpp:280
llvm::SDep::isWeak
bool isWeak() const
Tests if this a weak dependence.
Definition: ScheduleDAG.h:194
llvm::SchedulingPriorityQueue::setCurCycle
void setCurCycle(unsigned Cycle)
Definition: ScheduleDAG.h:545
x
TODO unsigned x
Definition: README.txt:10
llvm::ScheduleDAGTopologicalSort::InitDAGTopologicalSorting
void InitDAGTopologicalSorting()
Creates the initial topological ordering from the DAG to be scheduled.
Definition: ScheduleDAG.cpp:438
llvm::SUnit::addPred
bool addPred(const SDep &D, bool Required=true)
Adds the specified edge as a pred of the current node if not already.
Definition: ScheduleDAG.cpp:107
llvm::LLVMTargetMachine
This class describes a target machine that is implemented with the LLVM target-independent code gener...
Definition: TargetMachine.h:414
llvm::SUnit::hasPhysRegDefs
bool hasPhysRegDefs
Has physreg defs that are being used.
Definition: ScheduleDAG.h:280
llvm::SUnitIterator
Definition: ScheduleDAG.h:616
llvm::SUnit::isTwoAddress
bool isTwoAddress
Is a two-address instruction.
Definition: ScheduleDAG.h:277
llvm::SUnit::addPredBarrier
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:384
llvm::ScheduleDAGTopologicalSort::end
iterator end()
Definition: ScheduleDAG.h:773
llvm::SUnit::isCloned
bool isCloned
True if this node has been cloned.
Definition: ScheduleDAG.h:287
llvm::SDep::getKind
Kind getKind() const
Returns an enum value representing the kind of the dependence.
Definition: ScheduleDAG.h:486
llvm::ScheduleDAG::TM
const LLVMTargetMachine & TM
Target processor.
Definition: ScheduleDAG.h:556
llvm::SDep::isNormalMemoryOrBarrier
bool isNormalMemoryOrBarrier() const
Tests if this is could be any kind of memory dependence.
Definition: ScheduleDAG.h:179
llvm::SUnit::isSucc
bool isSucc(const SUnit *N) const
Tests if node N is a successor of this node.
Definition: ScheduleDAG.h:439
llvm::Cycle
CycleInfo::CycleT Cycle
Definition: CycleAnalysis.h:28
instr
@ instr
Definition: HWAddressSanitizer.cpp:192
llvm::SUnit::NodeQueueId
unsigned NodeQueueId
Queue id of node.
Definition: ScheduleDAG.h:265
llvm::PointerIntPair
PointerIntPair - This class implements a pair of a pointer and small integer.
Definition: PointerIntPair.h:46
llvm::SUnit::hasReservedResource
bool hasReservedResource
Uses a reserved resource.
Definition: ScheduleDAG.h:289
SmallVector.h
llvm::GraphTraits< SUnit * >::child_end
static ChildIteratorType child_end(NodeRef N)
Definition: ScheduleDAG.h:674
llvm::SUnit::isInstr
bool isInstr() const
Returns true if this SUnit refers to a machine instruction as opposed to an SDNode.
Definition: ScheduleDAG.h:362
llvm::SmallVectorImpl::iterator
typename SuperClass::iterator iterator
Definition: SmallVector.h:564
N
#define N
llvm::ScheduleDAG::dump
virtual void dump() const =0
llvm::ScheduleDAG::dumpNodeName
void dumpNodeName(const SUnit &SU) const
Definition: ScheduleDAG.cpp:354
llvm::SchedulingPriorityQueue::push_all
void push_all(const std::vector< SUnit * > &Nodes)
Definition: ScheduleDAG.h:527
llvm::SUnit::SUnit
SUnit()
Constructs a placeholder SUnit.
Definition: ScheduleDAG.h:329
llvm::SDep::Cluster
@ Cluster
Weak DAG edge linking a chain of clustered instrs.
Definition: ScheduleDAG.h:74
llvm::ScheduleDAGTopologicalSort::GetSubGraph
std::vector< int > GetSubGraph(const SUnit &StartSU, const SUnit &TargetSU, bool &Success)
Returns an array of SUs that are both in the successor subtree of StartSU and in the predecessor subt...
Definition: ScheduleDAG.cpp:597
llvm::SUnit::Preds
SmallVector< SDep, 4 > Preds
All sunit predecessors.
Definition: ScheduleDAG.h:256
llvm::SUnit
Scheduling unit. This is a node in the scheduling DAG.
Definition: ScheduleDAG.h:242
llvm::ScheduleDAGTopologicalSort::rbegin
reverse_iterator rbegin()
Definition: ScheduleDAG.h:778
llvm::SUnit::pred_iterator
SmallVectorImpl< SDep >::iterator pred_iterator
Definition: ScheduleDAG.h:259
llvm::SUnitIterator::isArtificialDep
bool isArtificialDep() const
Definition: ScheduleDAG.h:659
llvm::GraphTraits
Definition: GraphTraits.h:37
llvm::SchedulingPriorityQueue::unscheduledNode
virtual void unscheduledNode(SUnit *)
Definition: ScheduleDAG.h:543
llvm::Sched::Preference
Preference
Definition: TargetLowering.h:96
llvm::SchedulingPriorityQueue::updateNode
virtual void updateNode(const SUnit *SU)=0
llvm::SchedulingPriorityQueue
This interface is used to plug different priorities computation algorithms into the list scheduler.
Definition: ScheduleDAG.h:496
llvm::ScheduleDAGTopologicalSort::rend
reverse_iterator rend()
Definition: ScheduleDAG.h:780
llvm::SDep::dump
void dump(const TargetRegisterInfo *TRI=nullptr) const
Definition: ScheduleDAG.cpp:75
n
The same transformation can work with an even modulo with the addition of a and shrink the compare RHS by the same amount Unless the target supports that transformation probably isn t worthwhile The transformation can also easily be made to work with non zero equality for n
Definition: README.txt:685
llvm::SDep::isBarrier
bool isBarrier() const
Tests if this is an Order dependence that is marked as a barrier.
Definition: ScheduleDAG.h:174
llvm::SDep::SDep
SDep()
Constructs a null SDep.
Definition: ScheduleDAG.h:101
llvm::SDep::isCtrl
bool isCtrl() const
Shorthand for getKind() != SDep::Data.
Definition: ScheduleDAG.h:161
llvm::ScheduleDAG::clearDAG
void clearDAG()
Clears the DAG state (between regions).
Definition: ScheduleDAG.cpp:64
llvm::SchedulingPriorityQueue::initNodes
virtual void initNodes(std::vector< SUnit > &SUnits)=0
llvm::ScheduleDAG::ExitSU
SUnit ExitSU
Special node for the region exit.
Definition: ScheduleDAG.h:563
llvm::SDep::getLatency
unsigned getLatency() const
Returns the latency value for this edge, which roughly means the minimum number of cycles that must e...
Definition: ScheduleDAG.h:142
Other
Optional< std::vector< StOtherPiece > > Other
Definition: ELFYAML.cpp:1247
llvm::ScheduleDAGTopologicalSort::AddSUnitWithoutPredecessors
void AddSUnitWithoutPredecessors(const SUnit *SU)
Add a SUnit without predecessors to the end of the topological order.
Definition: ScheduleDAG.cpp:715
llvm::SDep::SDep
SDep(SUnit *S, Kind kind, unsigned Reg)
Constructs an SDep with the specified values.
Definition: ScheduleDAG.h:104
llvm::SDep::isMustAlias
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:186