LLVM  9.0.0svn
ScheduleDAGSDNodes.h
Go to the documentation of this file.
1 //===---- ScheduleDAGSDNodes.h - SDNode Scheduling --------------*- 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 // This file implements the ScheduleDAGSDNodes class, which implements
10 // scheduling for an SDNode-based dependency graph.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #ifndef LLVM_LIB_CODEGEN_SELECTIONDAG_SCHEDULEDAGSDNODES_H
15 #define LLVM_LIB_CODEGEN_SELECTIONDAG_SCHEDULEDAGSDNODES_H
16 
21 #include "llvm/Support/Casting.h"
23 #include <cassert>
24 #include <string>
25 #include <vector>
26 
27 namespace llvm {
28 
29 class InstrItineraryData;
30 
31  /// ScheduleDAGSDNodes - A ScheduleDAG for scheduling SDNode-based DAGs.
32  ///
33  /// Edges between SUnits are initially based on edges in the SelectionDAG,
34  /// and additional edges can be added by the schedulers as heuristics.
35  /// SDNodes such as Constants, Registers, and a few others that are not
36  /// interesting to schedulers are not allocated SUnits.
37  ///
38  /// SDNodes with MVT::Glue operands are grouped along with the flagged
39  /// nodes into a single SUnit so that they are scheduled together.
40  ///
41  /// SDNode-based scheduling graphs do not use SDep::Anti or SDep::Output
42  /// edges. Physical register dependence information is not carried in
43  /// the DAG and must be handled explicitly by schedulers.
44  ///
46  public:
48  SelectionDAG *DAG; // DAG of the current basic block
50 
51  /// The schedule. Null SUnit*'s represent noop instructions.
52  std::vector<SUnit*> Sequence;
53 
54  explicit ScheduleDAGSDNodes(MachineFunction &mf);
55 
56  ~ScheduleDAGSDNodes() override = default;
57 
58  /// Run - perform scheduling.
59  ///
60  void Run(SelectionDAG *dag, MachineBasicBlock *bb);
61 
62  /// isPassiveNode - Return true if the node is a non-scheduled leaf.
63  ///
64  static bool isPassiveNode(SDNode *Node) {
65  if (isa<ConstantSDNode>(Node)) return true;
66  if (isa<ConstantFPSDNode>(Node)) return true;
67  if (isa<RegisterSDNode>(Node)) return true;
68  if (isa<RegisterMaskSDNode>(Node)) return true;
69  if (isa<GlobalAddressSDNode>(Node)) return true;
70  if (isa<BasicBlockSDNode>(Node)) return true;
71  if (isa<FrameIndexSDNode>(Node)) return true;
72  if (isa<ConstantPoolSDNode>(Node)) return true;
73  if (isa<TargetIndexSDNode>(Node)) return true;
74  if (isa<JumpTableSDNode>(Node)) return true;
75  if (isa<ExternalSymbolSDNode>(Node)) return true;
76  if (isa<MCSymbolSDNode>(Node)) return true;
77  if (isa<BlockAddressSDNode>(Node)) return true;
78  if (Node->getOpcode() == ISD::EntryToken ||
79  isa<MDNodeSDNode>(Node)) return true;
80  return false;
81  }
82 
83  /// NewSUnit - Creates a new SUnit and return a ptr to it.
84  ///
86 
87  /// Clone - Creates a clone of the specified SUnit. It does not copy the
88  /// predecessors / successors info nor the temporary scheduling states.
89  ///
90  SUnit *Clone(SUnit *Old);
91 
92  /// BuildSchedGraph - Build the SUnit graph from the selection dag that we
93  /// are input. This SUnit graph is similar to the SelectionDAG, but
94  /// excludes nodes that aren't interesting to scheduling, and represents
95  /// flagged together nodes with a single SUnit.
97 
98  /// InitNumRegDefsLeft - Determine the # of regs defined by this node.
99  ///
100  void InitNumRegDefsLeft(SUnit *SU);
101 
102  /// computeLatency - Compute node latency.
103  ///
104  virtual void computeLatency(SUnit *SU);
105 
106  virtual void computeOperandLatency(SDNode *Def, SDNode *Use,
107  unsigned OpIdx, SDep& dep) const;
108 
109  /// Schedule - Order nodes according to selected style, filling
110  /// in the Sequence member.
111  ///
112  virtual void Schedule() = 0;
113 
114  /// VerifyScheduledSequence - Verify that all SUnits are scheduled and
115  /// consistent with the Sequence of scheduled instructions.
116  void VerifyScheduledSequence(bool isBottomUp);
117 
118  /// EmitSchedule - Insert MachineInstrs into the MachineBasicBlock
119  /// according to the order specified in Sequence.
120  ///
121  virtual MachineBasicBlock*
123 
124  void dumpNode(const SUnit &SU) const override;
125  void dump() const override;
126  void dumpSchedule() const;
127 
128  std::string getGraphNodeLabel(const SUnit *SU) const override;
129 
130  std::string getDAGName() const override;
131 
132  virtual void getCustomGraphFeatures(GraphWriter<ScheduleDAG*> &GW) const;
133 
134  /// RegDefIter - In place iteration over the values defined by an
135  /// SUnit. This does not need copies of the iterator or any other STLisms.
136  /// The iterator creates itself, rather than being provided by the SchedDAG.
137  class RegDefIter {
138  const ScheduleDAGSDNodes *SchedDAG;
139  const SDNode *Node;
140  unsigned DefIdx;
141  unsigned NodeNumDefs;
142  MVT ValueType;
143 
144  public:
145  RegDefIter(const SUnit *SU, const ScheduleDAGSDNodes *SD);
146 
147  bool IsValid() const { return Node != nullptr; }
148 
149  MVT GetValue() const {
150  assert(IsValid() && "bad iterator");
151  return ValueType;
152  }
153 
154  const SDNode *GetNode() const {
155  return Node;
156  }
157 
158  unsigned GetIdx() const {
159  return DefIdx-1;
160  }
161 
162  void Advance();
163 
164  private:
165  void InitNodeNumDefs();
166  };
167 
168  protected:
169  /// ForceUnitLatencies - Return true if all scheduling edges should be given
170  /// a latency value of one. The default is to return false; schedulers may
171  /// override this as needed.
172  virtual bool forceUnitLatencies() const { return false; }
173 
174  private:
175  /// ClusterNeighboringLoads - Cluster loads from "near" addresses into
176  /// combined SUnits.
177  void ClusterNeighboringLoads(SDNode *Node);
178  /// ClusterNodes - Cluster certain nodes which should be scheduled together.
179  ///
180  void ClusterNodes();
181 
182  /// BuildSchedUnits, AddSchedEdges - Helper functions for BuildSchedGraph.
183  void BuildSchedUnits();
184  void AddSchedEdges();
185 
186  void EmitPhysRegCopy(SUnit *SU, DenseMap<SUnit*, unsigned> &VRBaseMap,
187  MachineBasicBlock::iterator InsertPos);
188  };
189 
190 } // end namespace llvm
191 
192 #endif // LLVM_LIB_CODEGEN_SELECTIONDAG_SCHEDULEDAGSDNODES_H
void dumpNode(const SUnit &SU) const override
unsigned getOpcode() const
Return the SelectionDAG opcode value for this node.
This class represents lattice values for constants.
Definition: AllocatorList.h:23
virtual void getCustomGraphFeatures(GraphWriter< ScheduleDAG *> &GW) const
EntryToken - This is the marker used to indicate the start of a region.
Definition: ISDOpcodes.h:44
void InitNumRegDefsLeft(SUnit *SU)
InitNumRegDefsLeft - Determine the # of regs defined by this node.
void dump() const override
A Use represents the edge between a Value definition and its users.
Definition: Use.h:55
ScheduleDAGSDNodes(MachineFunction &mf)
std::string getDAGName() const override
Return the basic block label.
Itinerary data supplied by a subtarget to be used by a target.
Scheduling dependency.
Definition: ScheduleDAG.h:49
ScheduleDAGSDNodes - A ScheduleDAG for scheduling SDNode-based DAGs.
std::vector< SUnit * > Sequence
The schedule. Null SUnit*&#39;s represent noop instructions.
SUnit * newSUnit(SDNode *N)
NewSUnit - Creates a new SUnit and return a ptr to it.
Machine Value Type.
virtual void computeOperandLatency(SDNode *Def, SDNode *Use, unsigned OpIdx, SDep &dep) const
const InstrItineraryData * InstrItins
virtual void computeLatency(SUnit *SU)
computeLatency - Compute node latency.
RegDefIter - In place iteration over the values defined by an SUnit.
~ScheduleDAGSDNodes() override=default
MachineBasicBlock * BB
This is used to represent a portion of an LLVM function in a low-level Data Dependence DAG representa...
Definition: SelectionDAG.h:221
SUnit * Clone(SUnit *Old)
Clone - Creates a clone of the specified SUnit.
Represents one node in the SelectionDAG.
virtual bool forceUnitLatencies() const
ForceUnitLatencies - Return true if all scheduling edges should be given a latency value of one...
std::string getGraphNodeLabel(const SUnit *SU) const override
Returns a label for an SUnit node in a visualization of the ScheduleDAG.
static bool isPassiveNode(SDNode *Node)
isPassiveNode - Return true if the node is a non-scheduled leaf.
RegDefIter(const SUnit *SU, const ScheduleDAGSDNodes *SD)
void BuildSchedGraph(AliasAnalysis *AA)
BuildSchedGraph - Build the SUnit graph from the selection dag that we are input. ...
#define N
void Run(SelectionDAG *dag, MachineBasicBlock *bb)
Run - perform scheduling.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
virtual MachineBasicBlock * EmitSchedule(MachineBasicBlock::iterator &InsertPos)
EmitSchedule - Insert MachineInstrs into the MachineBasicBlock according to the order specified in Se...
virtual void Schedule()=0
Schedule - Order nodes according to selected style, filling in the Sequence member.
Scheduling unit. This is a node in the scheduling DAG.
Definition: ScheduleDAG.h:242
void VerifyScheduledSequence(bool isBottomUp)
VerifyScheduledSequence - Verify that all SUnits are scheduled and consistent with the Sequence of sc...
A discriminated union of two or more pointer types, with the discriminator in the low bit of the poin...
Definition: PointerUnion.h:163