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