LLVM  13.0.0git
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 AAResults;
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.
97  void BuildSchedGraph(AAResults *AA);
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  void dump() const override;
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*, Register> &VRBaseMap,
188  MachineBasicBlock::iterator InsertPos);
189  };
190 
191 } // end namespace llvm
192 
193 #endif // LLVM_LIB_CODEGEN_SELECTIONDAG_SCHEDULEDAGSDNODES_H
llvm::ScheduleDAGSDNodes::computeLatency
virtual void computeLatency(SUnit *SU)
computeLatency - Compute node latency.
Definition: ScheduleDAGSDNodes.cpp:612
ScheduleDAG.h
llvm
Definition: AllocatorList.h:23
llvm::tgtok::Def
@ Def
Definition: TGLexer.h:50
llvm::GraphWriter
Definition: ScheduleDAG.h:34
llvm::ScheduleDAGSDNodes
ScheduleDAGSDNodes - A ScheduleDAG for scheduling SDNode-based DAGs.
Definition: ScheduleDAGSDNodes.h:46
llvm::ScheduleDAGSDNodes::VerifyScheduledSequence
void VerifyScheduledSequence(bool isBottomUp)
VerifyScheduledSequence - Verify that all SUnits are scheduled and consistent with the Sequence of sc...
Definition: ScheduleDAGSDNodes.cpp:723
llvm::ScheduleDAGSDNodes::~ScheduleDAGSDNodes
~ScheduleDAGSDNodes() override=default
llvm::SDNode
Represents one node in the SelectionDAG.
Definition: SelectionDAGNodes.h:455
llvm::ScheduleDAGSDNodes::getCustomGraphFeatures
virtual void getCustomGraphFeatures(GraphWriter< ScheduleDAG * > &GW) const
Definition: SelectionDAGPrinter.cpp:309
MachineBasicBlock.h
llvm::ScheduleDAGSDNodes::newSUnit
SUnit * newSUnit(SDNode *N)
NewSUnit - Creates a new SUnit and return a ptr to it.
Definition: ScheduleDAGSDNodes.cpp:69
llvm::ScheduleDAGSDNodes::DAG
SelectionDAG * DAG
Definition: ScheduleDAGSDNodes.h:49
llvm::ScheduleDAGSDNodes::ScheduleDAGSDNodes
ScheduleDAGSDNodes(MachineFunction &mf)
Definition: ScheduleDAGSDNodes.cpp:49
MachineValueType.h
llvm::ScheduleDAGSDNodes::RegDefIter::RegDefIter
RegDefIter(const SUnit *SU, const ScheduleDAGSDNodes *SD)
Definition: ScheduleDAGSDNodes.cpp:579
bb
< i1 > br i1 label label bb bb
Definition: README.txt:978
llvm::SelectionDAG
This is used to represent a portion of an LLVM function in a low-level Data Dependence DAG representa...
Definition: SelectionDAG.h:216
SelectionDAGNodes.h
llvm::AAResults
Definition: AliasAnalysis.h:456
llvm::ScheduleDAGSDNodes::getDAGName
std::string getDAGName() const override
Return the basic block label.
Definition: ScheduleDAGSDNodes.cpp:1081
llvm::ScheduleDAGSDNodes::InstrItins
const InstrItineraryData * InstrItins
Definition: ScheduleDAGSDNodes.h:50
llvm::ScheduleDAGSDNodes::getGraphNodeLabel
std::string getGraphNodeLabel(const SUnit *SU) const override
Returns a label for an SUnit node in a visualization of the ScheduleDAG.
Definition: SelectionDAGPrinter.cpp:288
llvm::ISD::EntryToken
@ EntryToken
EntryToken - This is the marker used to indicate the start of a region.
Definition: ISDOpcodes.h:47
llvm::ScheduleDAGSDNodes::RegDefIter::GetValue
MVT GetValue() const
Definition: ScheduleDAGSDNodes.h:150
llvm::MachineBasicBlock
Definition: MachineBasicBlock.h:95
llvm::ScheduleDAGSDNodes::RegDefIter::Advance
void Advance()
Definition: ScheduleDAGSDNodes.cpp:587
llvm::ScheduleDAGSDNodes::computeOperandLatency
virtual void computeOperandLatency(SDNode *Def, SDNode *Use, unsigned OpIdx, SDep &dep) const
Definition: ScheduleDAGSDNodes.cpp:646
llvm::ScheduleDAGSDNodes::forceUnitLatencies
virtual bool forceUnitLatencies() const
ForceUnitLatencies - Return true if all scheduling edges should be given a latency value of one.
Definition: ScheduleDAGSDNodes.h:173
llvm::ScheduleDAGSDNodes::Clone
SUnit * Clone(SUnit *Old)
Clone - Creates a clone of the specified SUnit.
Definition: ScheduleDAGSDNodes.cpp:90
llvm::ScheduleDAGSDNodes::RegDefIter::GetIdx
unsigned GetIdx() const
Definition: ScheduleDAGSDNodes.h:159
llvm::DenseMap
Definition: DenseMap.h:714
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::ScheduleDAGSDNodes::EmitSchedule
virtual MachineBasicBlock * EmitSchedule(MachineBasicBlock::iterator &InsertPos)
EmitSchedule - Insert MachineInstrs into the MachineBasicBlock according to the order specified in Se...
Definition: ScheduleDAGSDNodes.cpp:850
llvm::ScheduleDAGSDNodes::Schedule
virtual void Schedule()=0
Schedule - Order nodes according to selected style, filling in the Sequence member.
llvm::MVT
Machine Value Type.
Definition: MachineValueType.h:30
llvm::ScheduleDAGSDNodes::Run
void Run(SelectionDAG *dag, MachineBasicBlock *bb)
Run - perform scheduling.
Definition: ScheduleDAGSDNodes.cpp:55
llvm::MachineFunction
Definition: MachineFunction.h:230
llvm::ScheduleDAG
Definition: ScheduleDAG.h:555
Node
Definition: ItaniumDemangle.h:114
llvm::PointerUnion< const Value *, const PseudoSourceValue * >
llvm::ScheduleDAGSDNodes::RegDefIter
RegDefIter - In place iteration over the values defined by an SUnit.
Definition: ScheduleDAGSDNodes.h:138
llvm::SDep
Scheduling dependency.
Definition: ScheduleDAG.h:49
llvm::ScheduleDAGSDNodes::dumpSchedule
void dumpSchedule() const
Definition: ScheduleDAGSDNodes.cpp:709
llvm::ScheduleDAGSDNodes::BB
MachineBasicBlock * BB
Definition: ScheduleDAGSDNodes.h:48
ISDOpcodes.h
Casting.h
llvm::ScheduleDAGSDNodes::dump
void dump() const override
Definition: ScheduleDAGSDNodes.cpp:697
llvm::ScheduleDAGSDNodes::dumpNode
void dumpNode(const SUnit &SU) const override
Definition: ScheduleDAGSDNodes.cpp:673
N
#define N
llvm::ScheduleDAGSDNodes::RegDefIter::GetNode
const SDNode * GetNode() const
Definition: ScheduleDAGSDNodes.h:155
llvm::SUnit
Scheduling unit. This is a node in the scheduling DAG.
Definition: ScheduleDAG.h:242
llvm::ScheduleDAGSDNodes::Sequence
std::vector< SUnit * > Sequence
The schedule. Null SUnit*'s represent noop instructions.
Definition: ScheduleDAGSDNodes.h:53
llvm::ScheduleDAGSDNodes::BuildSchedGraph
void BuildSchedGraph(AAResults *AA)
BuildSchedGraph - Build the SUnit graph from the selection dag that we are input.
Definition: ScheduleDAGSDNodes.cpp:535
llvm::ScheduleDAGSDNodes::InitNumRegDefsLeft
void InitNumRegDefsLeft(SUnit *SU)
InitNumRegDefsLeft - Determine the # of regs defined by this node.
Definition: ScheduleDAGSDNodes.cpp:604
llvm::MachineInstrBundleIterator< MachineInstr >
llvm::ScheduleDAGSDNodes::isPassiveNode
static bool isPassiveNode(SDNode *Node)
isPassiveNode - Return true if the node is a non-scheduled leaf.
Definition: ScheduleDAGSDNodes.h:65
llvm::InstrItineraryData
Itinerary data supplied by a subtarget to be used by a target.
Definition: MCInstrItineraries.h:109
llvm::ScheduleDAGSDNodes::RegDefIter::IsValid
bool IsValid() const
Definition: ScheduleDAGSDNodes.h:148
llvm::Use
A Use represents the edge between a Value definition and its users.
Definition: Use.h:44