LLVM  14.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"
19 #include "llvm/ADT/GraphTraits.h"
21 #include "llvm/ADT/SmallVector.h"
22 #include "llvm/ADT/iterator.h"
26 #include <cassert>
27 #include <cstddef>
28 #include <iterator>
29 #include <string>
30 #include <vector>
31 
32 namespace llvm {
33 
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 (std::vector<SUnit *>::const_iterator I = Nodes.begin(),
529  E = Nodes.end(); I != E; ++I)
530  push(*I);
531  }
532 
533  virtual SUnit *pop() = 0;
534 
535  virtual void remove(SUnit *SU) = 0;
536 
537  virtual void dump(ScheduleDAG *) const {}
538 
539  /// As each node is scheduled, this method is invoked. This allows the
540  /// priority function to adjust the priority of related unscheduled nodes,
541  /// for example.
542  virtual void scheduledNode(SUnit *) {}
543 
544  virtual void unscheduledNode(SUnit *) {}
545 
546  void setCurCycle(unsigned Cycle) {
547  CurCycle = Cycle;
548  }
549 
550  unsigned getCurCycle() const {
551  return CurCycle;
552  }
553  };
554 
555  class ScheduleDAG {
556  public:
557  const LLVMTargetMachine &TM; ///< Target processor
558  const TargetInstrInfo *TII; ///< Target instruction information
559  const TargetRegisterInfo *TRI; ///< Target processor register info
560  MachineFunction &MF; ///< Machine function
561  MachineRegisterInfo &MRI; ///< Virtual/real register map
562  std::vector<SUnit> SUnits; ///< The scheduling units.
563  SUnit EntrySU; ///< Special node for the region entry.
564  SUnit ExitSU; ///< Special node for the region exit.
565 
566 #ifdef NDEBUG
567  static const bool StressSched = false;
568 #else
570 #endif
571 
572  explicit ScheduleDAG(MachineFunction &mf);
573 
574  virtual ~ScheduleDAG();
575 
576  /// Clears the DAG state (between regions).
577  void clearDAG();
578 
579  /// Returns the MCInstrDesc of this SUnit.
580  /// Returns NULL for SDNodes without a machine opcode.
581  const MCInstrDesc *getInstrDesc(const SUnit *SU) const {
582  if (SU->isInstr()) return &SU->getInstr()->getDesc();
583  return getNodeDesc(SU->getNode());
584  }
585 
586  /// Pops up a GraphViz/gv window with the ScheduleDAG rendered using 'dot'.
587  virtual void viewGraph(const Twine &Name, const Twine &Title);
588  virtual void viewGraph();
589 
590  virtual void dumpNode(const SUnit &SU) const = 0;
591  virtual void dump() const = 0;
592  void dumpNodeName(const SUnit &SU) const;
593 
594  /// Returns a label for an SUnit node in a visualization of the ScheduleDAG.
595  virtual std::string getGraphNodeLabel(const SUnit *SU) const = 0;
596 
597  /// Returns a label for the region of code covered by the DAG.
598  virtual std::string getDAGName() const = 0;
599 
600  /// Adds custom features for a visualization of the ScheduleDAG.
602 
603 #ifndef NDEBUG
604  /// Verifies that all SUnits were scheduled and that their state is
605  /// consistent. Returns the number of scheduled SUnits.
606  unsigned VerifyScheduledDAG(bool isBottomUp);
607 #endif
608 
609  protected:
610  void dumpNodeAll(const SUnit &SU) const;
611 
612  private:
613  /// Returns the MCInstrDesc of this SDNode or NULL.
614  const MCInstrDesc *getNodeDesc(const SDNode *Node) const;
615  };
616 
618  SUnit *Node;
619  unsigned Operand;
620 
621  SUnitIterator(SUnit *N, unsigned Op) : Node(N), Operand(Op) {}
622 
623  public:
624  using iterator_category = std::forward_iterator_tag;
625  using value_type = SUnit;
626  using difference_type = std::ptrdiff_t;
627  using pointer = value_type *;
629 
630  bool operator==(const SUnitIterator& x) const {
631  return Operand == x.Operand;
632  }
633  bool operator!=(const SUnitIterator& x) const { return !operator==(x); }
634 
635  pointer operator*() const {
636  return Node->Preds[Operand].getSUnit();
637  }
638  pointer operator->() const { return operator*(); }
639 
640  SUnitIterator& operator++() { // Preincrement
641  ++Operand;
642  return *this;
643  }
644  SUnitIterator operator++(int) { // Postincrement
645  SUnitIterator tmp = *this; ++*this; return tmp;
646  }
647 
648  static SUnitIterator begin(SUnit *N) { return SUnitIterator(N, 0); }
649  static SUnitIterator end (SUnit *N) {
650  return SUnitIterator(N, (unsigned)N->Preds.size());
651  }
652 
653  unsigned getOperand() const { return Operand; }
654  const SUnit *getNode() const { return Node; }
655 
656  /// Tests if this is not an SDep::Data dependence.
657  bool isCtrlDep() const {
658  return getSDep().isCtrl();
659  }
660  bool isArtificialDep() const {
661  return getSDep().isArtificial();
662  }
663  const SDep &getSDep() const {
664  return Node->Preds[Operand];
665  }
666  };
667 
668  template <> struct GraphTraits<SUnit*> {
669  typedef SUnit *NodeRef;
671  static NodeRef getEntryNode(SUnit *N) { return N; }
673  return SUnitIterator::begin(N);
674  }
676  return SUnitIterator::end(N);
677  }
678  };
679 
680  template <> struct GraphTraits<ScheduleDAG*> : public GraphTraits<SUnit*> {
683  return nodes_iterator(G->SUnits.begin());
684  }
686  return nodes_iterator(G->SUnits.end());
687  }
688  };
689 
690  /// This class can compute a topological ordering for SUnits and provides
691  /// methods for dynamically updating the ordering as new edges are added.
692  ///
693  /// This allows a very fast implementation of IsReachable, for example.
695  /// A reference to the ScheduleDAG's SUnits.
696  std::vector<SUnit> &SUnits;
697  SUnit *ExitSU;
698 
699  // Have any new nodes been added?
700  bool Dirty = false;
701 
702  // Outstanding added edges, that have not been applied to the ordering.
704 
705  /// Maps topological index to the node number.
706  std::vector<int> Index2Node;
707  /// Maps the node number to its topological index.
708  std::vector<int> Node2Index;
709  /// a set of nodes visited during a DFS traversal.
710  BitVector Visited;
711 
712  /// Makes a DFS traversal and mark all nodes affected by the edge insertion.
713  /// These nodes will later get new topological indexes by means of the Shift
714  /// method.
715  void DFS(const SUnit *SU, int UpperBound, bool& HasLoop);
716 
717  /// Reassigns topological indexes for the nodes in the DAG to
718  /// preserve the topological ordering.
719  void Shift(BitVector& Visited, int LowerBound, int UpperBound);
720 
721  /// Assigns the topological index to the node n.
722  void Allocate(int n, int index);
723 
724  /// Fix the ordering, by either recomputing from scratch or by applying
725  /// any outstanding updates. Uses a heuristic to estimate what will be
726  /// cheaper.
727  void FixOrder();
728 
729  public:
730  ScheduleDAGTopologicalSort(std::vector<SUnit> &SUnits, SUnit *ExitSU);
731 
732  /// Add a SUnit without predecessors to the end of the topological order. It
733  /// also must be the first new node added to the DAG.
734  void AddSUnitWithoutPredecessors(const SUnit *SU);
735 
736  /// Creates the initial topological ordering from the DAG to be scheduled.
738 
739  /// Returns an array of SUs that are both in the successor
740  /// subtree of StartSU and in the predecessor subtree of TargetSU.
741  /// StartSU and TargetSU are not in the array.
742  /// Success is false if TargetSU is not in the successor subtree of
743  /// StartSU, else it is true.
744  std::vector<int> GetSubGraph(const SUnit &StartSU, const SUnit &TargetSU,
745  bool &Success);
746 
747  /// Checks if \p SU is reachable from \p TargetSU.
748  bool IsReachable(const SUnit *SU, const SUnit *TargetSU);
749 
750  /// Returns true if addPred(TargetSU, SU) creates a cycle.
751  bool WillCreateCycle(SUnit *TargetSU, SUnit *SU);
752 
753  /// Updates the topological ordering to accommodate an edge to be
754  /// added from SUnit \p X to SUnit \p Y.
755  void AddPred(SUnit *Y, SUnit *X);
756 
757  /// Queues an update to the topological ordering to accommodate an edge to
758  /// be added from SUnit \p X to SUnit \p Y.
759  void AddPredQueued(SUnit *Y, SUnit *X);
760 
761  /// Updates the topological ordering to accommodate an an edge to be
762  /// removed from the specified node \p N from the predecessors of the
763  /// current node \p M.
764  void RemovePred(SUnit *M, SUnit *N);
765 
766  /// Mark the ordering as temporarily broken, after a new node has been
767  /// added.
768  void MarkDirty() { Dirty = true; }
769 
770  typedef std::vector<int>::iterator iterator;
771  typedef std::vector<int>::const_iterator const_iterator;
772  iterator begin() { return Index2Node.begin(); }
773  const_iterator begin() const { return Index2Node.begin(); }
774  iterator end() { return Index2Node.end(); }
775  const_iterator end() const { return Index2Node.end(); }
776 
777  typedef std::vector<int>::reverse_iterator reverse_iterator;
778  typedef std::vector<int>::const_reverse_iterator const_reverse_iterator;
779  reverse_iterator rbegin() { return Index2Node.rbegin(); }
780  const_reverse_iterator rbegin() const { return Index2Node.rbegin(); }
781  reverse_iterator rend() { return Index2Node.rend(); }
782  const_reverse_iterator rend() const { return Index2Node.rend(); }
783  };
784 
785 } // end namespace llvm
786 
787 #endif // LLVM_CODEGEN_SCHEDULEDAG_H
llvm::ScheduleDAG::MRI
MachineRegisterInfo & MRI
Virtual/real register map.
Definition: ScheduleDAG.h:561
llvm::SchedulingPriorityQueue::scheduledNode
virtual void scheduledNode(SUnit *)
As each node is scheduled, this method is invoked.
Definition: ScheduleDAG.h:542
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:105
MachineInstr.h
llvm
This file implements support for optimizing divisions by a constant.
Definition: AllocatorList.h:23
llvm::ScheduleDAGTopologicalSort::WillCreateCycle
bool WillCreateCycle(SUnit *TargetSU, SUnit *SU)
Returns true if addPred(TargetSU, SU) creates a cycle.
Definition: ScheduleDAG.cpp:704
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:772
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:663
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:52
llvm::SchedulingPriorityQueue::dump
virtual void dump(ScheduleDAG *) const
Definition: ScheduleDAG.h:537
llvm::MachineInstr::mayLoad
bool mayLoad(QueryType Type=AnyInBundle) const
Return true if this instruction could possibly read memory.
Definition: MachineInstr.h:1005
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1168
llvm::ScheduleDAGTopologicalSort::const_iterator
std::vector< int >::const_iterator const_iterator
Definition: ScheduleDAG.h:771
llvm::ScheduleDAGTopologicalSort::IsReachable
bool IsReachable(const SUnit *SU, const SUnit *TargetSU)
Checks if SU is reachable from TargetSU.
Definition: ScheduleDAG.cpp:724
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:668
llvm::GraphTraits< ScheduleDAG * >::nodes_iterator
pointer_iterator< std::vector< SUnit >::iterator > nodes_iterator
Definition: ScheduleDAG.h:681
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:455
llvm::TargetRegisterInfo
TargetRegisterInfo base class - We assume that the target defines a static array of TargetRegisterDes...
Definition: TargetRegisterInfo.h:233
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:486
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:685
llvm::ScheduleDAGTopologicalSort::end
const_iterator end() const
Definition: ScheduleDAG.h:775
llvm::SUnit::Succs
SmallVector< SDep, 4 > Succs
All sunit successors.
Definition: ScheduleDAG.h:257
llvm::SUnitIterator::operator++
SUnitIterator operator++(int)
Definition: ScheduleDAG.h:644
llvm::SUnitIterator::operator*
pointer operator*() const
Definition: ScheduleDAG.h:635
llvm::SUnitIterator::getOperand
unsigned getOperand() const
Definition: ScheduleDAG.h:653
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:601
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:1567
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
GraphTraits.h
llvm::ScheduleDAGTopologicalSort::MarkDirty
void MarkDirty()
Mark the ordering as temporarily broken, after a new node has been added.
Definition: ScheduleDAG.h:768
llvm::ScheduleDAGTopologicalSort
This class can compute a topological ordering for SUnits and provides methods for dynamically updatin...
Definition: ScheduleDAG.h:694
llvm::SchedulingPriorityQueue::getCurCycle
unsigned getCurCycle() const
Definition: ScheduleDAG.h:550
llvm::SUnitIterator::isCtrlDep
bool isCtrlDep() const
Tests if this is not an SDep::Data dependence.
Definition: ScheduleDAG.h:657
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:97
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:626
llvm::SUnitIterator::operator++
SUnitIterator & operator++()
Definition: ScheduleDAG.h:640
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:671
llvm::SUnitIterator::operator==
bool operator==(const SUnitIterator &x) const
Definition: ScheduleDAG.h:630
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
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:121
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:142
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:195
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::SUnitIterator::operator->
pointer operator->() const
Definition: ScheduleDAG.h:638
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:581
llvm::GraphTraits< SUnit * >::child_begin
static ChildIteratorType child_begin(NodeRef N)
Definition: ScheduleDAG.h:672
llvm::SUnit::isVRegCycle
bool isVRegCycle
May use and def the same vreg.
Definition: ScheduleDAG.h:274
llvm::BitVector
Definition: BitVector.h:74
llvm::ScheduleDAGTopologicalSort::const_reverse_iterator
std::vector< int >::const_reverse_iterator const_reverse_iterator
Definition: ScheduleDAG.h:778
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:777
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:748
llvm::ScheduleDAG::viewGraph
virtual void viewGraph()
Out-of-line implementation with no arguments is handy for gdb.
Definition: ScheduleDAGPrinter.cpp:95
G
const DataFlowGraph & G
Definition: RDFGraph.cpp:202
llvm::pointer_iterator
Definition: iterator.h:338
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:649
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:64
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
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::GraphTraits< ScheduleDAG * >::nodes_begin
static nodes_iterator nodes_begin(ScheduleDAG *G)
Definition: ScheduleDAG.h:682
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:770
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:99
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:563
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::SUnitIterator::begin
static SUnitIterator begin(SUnit *N)
Definition: ScheduleDAG.h:648
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:633
llvm::SDep::operator==
bool operator==(const SDep &Other) const
Definition: ScheduleDAG.h:131
llvm::GraphTraits< SUnit * >::ChildIteratorType
SUnitIterator ChildIteratorType
Definition: ScheduleDAG.h:670
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:234
llvm::SDep::operator!=
bool operator!=(const SDep &Other) const
Definition: ScheduleDAG.h:135
llvm::ScheduleDAG::StressSched
bool StressSched
Definition: ScheduleDAG.h:569
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:555
llvm::SUnitIterator::getNode
const SUnit * getNode() const
Definition: ScheduleDAG.h:654
llvm::ScheduleDAG::dumpNode
virtual void dumpNode(const SUnit &SU) const =0
llvm::ScheduleDAG::TRI
const TargetRegisterInfo * TRI
Target processor register info.
Definition: ScheduleDAG.h:559
llvm::ScheduleDAGTopologicalSort::rend
const_reverse_iterator rend() const
Definition: ScheduleDAG.h:782
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:624
llvm::SUnit::SchedClass
const MCSchedClassDesc * SchedClass
nullptr or resolved SchedClass.
Definition: ScheduleDAG.h:253
llvm::ScheduleDAG::MF
MachineFunction & MF
Machine function.
Definition: ScheduleDAG.h:560
llvm_unreachable
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Definition: ErrorHandling.h:134
llvm::ScheduleDAGTopologicalSort::begin
const_iterator begin() const
Definition: ScheduleDAG.h:773
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:563
Node
Definition: ItaniumDemangle.h:235
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:83
llvm::ScheduleDAG::SUnits
std::vector< SUnit > SUnits
The scheduling units.
Definition: ScheduleDAG.h:562
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:780
llvm::GraphProgram::Name
Name
Definition: GraphWriter.h:52
llvm::SUnit::NumSuccs
unsigned NumSuccs
Definition: ScheduleDAG.h:267
llvm::GraphTraits< SUnit * >::NodeRef
SUnit * NodeRef
Definition: ScheduleDAG.h:669
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:324
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:1018
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:558
Success
#define Success
Definition: AArch64Disassembler.cpp:260
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:546
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:393
llvm::SUnit::hasPhysRegDefs
bool hasPhysRegDefs
Has physreg defs that are being used.
Definition: ScheduleDAG.h:280
llvm::SUnitIterator
Definition: ScheduleDAG.h:617
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:774
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:557
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::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:45
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:675
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:562
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:598
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:779
llvm::SUnit::pred_iterator
SmallVectorImpl< SDep >::iterator pred_iterator
Definition: ScheduleDAG.h:259
llvm::SUnitIterator::isArtificialDep
bool isArtificialDep() const
Definition: ScheduleDAG.h:660
llvm::GraphTraits
Definition: GraphTraits.h:35
llvm::SchedulingPriorityQueue::unscheduledNode
virtual void unscheduledNode(SUnit *)
Definition: ScheduleDAG.h:544
llvm::Sched::Preference
Preference
Definition: TargetLowering.h:98
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:781
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:564
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:1184
llvm::ScheduleDAGTopologicalSort::AddSUnitWithoutPredecessors
void AddSUnitWithoutPredecessors(const SUnit *SU)
Add a SUnit without predecessors to the end of the topological order.
Definition: ScheduleDAG.cpp:716
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