1 //===--- ScheduleDAGSDNodes.cpp - Implement the ScheduleDAGSDNodes class --===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This implements the ScheduleDAG class, which is a base class used by
11 // scheduling implementation classes.
13 //===----------------------------------------------------------------------===//
15 #define DEBUG_TYPE "pre-RA-sched"
16 #include "ScheduleDAGSDNodes.h"
17 #include "llvm/CodeGen/SelectionDAG.h"
18 #include "llvm/Target/TargetMachine.h"
19 #include "llvm/Target/TargetInstrInfo.h"
20 #include "llvm/Target/TargetRegisterInfo.h"
21 #include "llvm/Target/TargetSubtarget.h"
22 #include "llvm/Support/Debug.h"
23 #include "llvm/Support/raw_ostream.h"
26 ScheduleDAGSDNodes::ScheduleDAGSDNodes(MachineFunction
&mf
)
30 /// Run - perform scheduling.
32 void ScheduleDAGSDNodes::Run(SelectionDAG
*dag
, MachineBasicBlock
*bb
,
33 MachineBasicBlock::iterator insertPos
) {
35 ScheduleDAG::Run(bb
, insertPos
);
38 SUnit
*ScheduleDAGSDNodes::Clone(SUnit
*Old
) {
39 SUnit
*SU
= NewSUnit(Old
->getNode());
40 SU
->OrigNode
= Old
->OrigNode
;
41 SU
->Latency
= Old
->Latency
;
42 SU
->isTwoAddress
= Old
->isTwoAddress
;
43 SU
->isCommutable
= Old
->isCommutable
;
44 SU
->hasPhysRegDefs
= Old
->hasPhysRegDefs
;
45 SU
->hasPhysRegClobbers
= Old
->hasPhysRegClobbers
;
50 /// CheckForPhysRegDependency - Check if the dependency between def and use of
51 /// a specified operand is a physical register dependency. If so, returns the
52 /// register and the cost of copying the register.
53 static void CheckForPhysRegDependency(SDNode
*Def
, SDNode
*User
, unsigned Op
,
54 const TargetRegisterInfo
*TRI
,
55 const TargetInstrInfo
*TII
,
56 unsigned &PhysReg
, int &Cost
) {
57 if (Op
!= 2 || User
->getOpcode() != ISD::CopyToReg
)
60 unsigned Reg
= cast
<RegisterSDNode
>(User
->getOperand(1))->getReg();
61 if (TargetRegisterInfo::isVirtualRegister(Reg
))
64 unsigned ResNo
= User
->getOperand(2).getResNo();
65 if (Def
->isMachineOpcode()) {
66 const TargetInstrDesc
&II
= TII
->get(Def
->getMachineOpcode());
67 if (ResNo
>= II
.getNumDefs() &&
68 II
.ImplicitDefs
[ResNo
- II
.getNumDefs()] == Reg
) {
70 const TargetRegisterClass
*RC
=
71 TRI
->getPhysicalRegisterRegClass(Reg
, Def
->getValueType(ResNo
));
72 Cost
= RC
->getCopyCost();
77 void ScheduleDAGSDNodes::BuildSchedUnits() {
78 // During scheduling, the NodeId field of SDNode is used to map SDNodes
79 // to their associated SUnits by holding SUnits table indices. A value
80 // of -1 means the SDNode does not yet have an associated SUnit.
81 unsigned NumNodes
= 0;
82 for (SelectionDAG::allnodes_iterator NI
= DAG
->allnodes_begin(),
83 E
= DAG
->allnodes_end(); NI
!= E
; ++NI
) {
88 // Reserve entries in the vector for each of the SUnits we are creating. This
89 // ensure that reallocation of the vector won't happen, so SUnit*'s won't get
91 // FIXME: Multiply by 2 because we may clone nodes during scheduling.
92 // This is a temporary workaround.
93 SUnits
.reserve(NumNodes
* 2);
95 // Check to see if the scheduler cares about latencies.
96 bool UnitLatencies
= ForceUnitLatencies();
98 for (SelectionDAG::allnodes_iterator NI
= DAG
->allnodes_begin(),
99 E
= DAG
->allnodes_end(); NI
!= E
; ++NI
) {
100 if (isPassiveNode(NI
)) // Leaf node, e.g. a TargetImmediate.
103 // If this node has already been processed, stop now.
104 if (NI
->getNodeId() != -1) continue;
106 SUnit
*NodeSUnit
= NewSUnit(NI
);
108 // See if anything is flagged to this node, if so, add them to flagged
109 // nodes. Nodes can have at most one flag input and one flag output. Flags
110 // are required to be the last operand and result of a node.
112 // Scan up to find flagged preds.
114 while (N
->getNumOperands() &&
115 N
->getOperand(N
->getNumOperands()-1).getValueType() == MVT::Flag
) {
116 N
= N
->getOperand(N
->getNumOperands()-1).getNode();
117 assert(N
->getNodeId() == -1 && "Node already inserted!");
118 N
->setNodeId(NodeSUnit
->NodeNum
);
121 // Scan down to find any flagged succs.
123 while (N
->getValueType(N
->getNumValues()-1) == MVT::Flag
) {
124 SDValue
FlagVal(N
, N
->getNumValues()-1);
126 // There are either zero or one users of the Flag result.
127 bool HasFlagUse
= false;
128 for (SDNode::use_iterator UI
= N
->use_begin(), E
= N
->use_end();
130 if (FlagVal
.isOperandOf(*UI
)) {
132 assert(N
->getNodeId() == -1 && "Node already inserted!");
133 N
->setNodeId(NodeSUnit
->NodeNum
);
137 if (!HasFlagUse
) break;
140 // If there are flag operands involved, N is now the bottom-most node
141 // of the sequence of nodes that are flagged together.
143 NodeSUnit
->setNode(N
);
144 assert(N
->getNodeId() == -1 && "Node already inserted!");
145 N
->setNodeId(NodeSUnit
->NodeNum
);
147 // Assign the Latency field of NodeSUnit using target-provided information.
149 NodeSUnit
->Latency
= 1;
151 ComputeLatency(NodeSUnit
);
155 void ScheduleDAGSDNodes::AddSchedEdges() {
156 const TargetSubtarget
&ST
= TM
.getSubtarget
<TargetSubtarget
>();
158 // Check to see if the scheduler cares about latencies.
159 bool UnitLatencies
= ForceUnitLatencies();
161 // Pass 2: add the preds, succs, etc.
162 for (unsigned su
= 0, e
= SUnits
.size(); su
!= e
; ++su
) {
163 SUnit
*SU
= &SUnits
[su
];
164 SDNode
*MainNode
= SU
->getNode();
166 if (MainNode
->isMachineOpcode()) {
167 unsigned Opc
= MainNode
->getMachineOpcode();
168 const TargetInstrDesc
&TID
= TII
->get(Opc
);
169 for (unsigned i
= 0; i
!= TID
.getNumOperands(); ++i
) {
170 if (TID
.getOperandConstraint(i
, TOI::TIED_TO
) != -1) {
171 SU
->isTwoAddress
= true;
175 if (TID
.isCommutable())
176 SU
->isCommutable
= true;
179 // Find all predecessors and successors of the group.
180 for (SDNode
*N
= SU
->getNode(); N
; N
= N
->getFlaggedNode()) {
181 if (N
->isMachineOpcode() &&
182 TII
->get(N
->getMachineOpcode()).getImplicitDefs()) {
183 SU
->hasPhysRegClobbers
= true;
184 unsigned NumUsed
= CountResults(N
);
185 while (NumUsed
!= 0 && !N
->hasAnyUseOfValue(NumUsed
- 1))
186 --NumUsed
; // Skip over unused values at the end.
187 if (NumUsed
> TII
->get(N
->getMachineOpcode()).getNumDefs())
188 SU
->hasPhysRegDefs
= true;
191 for (unsigned i
= 0, e
= N
->getNumOperands(); i
!= e
; ++i
) {
192 SDNode
*OpN
= N
->getOperand(i
).getNode();
193 if (isPassiveNode(OpN
)) continue; // Not scheduled.
194 SUnit
*OpSU
= &SUnits
[OpN
->getNodeId()];
195 assert(OpSU
&& "Node has no SUnit!");
196 if (OpSU
== SU
) continue; // In the same group.
198 EVT OpVT
= N
->getOperand(i
).getValueType();
199 assert(OpVT
!= MVT::Flag
&& "Flagged nodes should be in same sunit!");
200 bool isChain
= OpVT
== MVT::Other
;
202 unsigned PhysReg
= 0;
204 // Determine if this is a physical register dependency.
205 CheckForPhysRegDependency(OpN
, N
, i
, TRI
, TII
, PhysReg
, Cost
);
206 assert((PhysReg
== 0 || !isChain
) &&
207 "Chain dependence via physreg data?");
208 // FIXME: See ScheduleDAGSDNodes::EmitCopyFromReg. For now, scheduler
209 // emits a copy from the physical register to a virtual register unless
210 // it requires a cross class copy (cost < 0). That means we are only
211 // treating "expensive to copy" register dependency as physical register
212 // dependency. This may change in the future though.
216 const SDep
& dep
= SDep(OpSU
, isChain
? SDep::Order
: SDep::Data
,
217 OpSU
->Latency
, PhysReg
);
218 if (!isChain
&& !UnitLatencies
) {
219 ComputeOperandLatency(OpSU
, SU
, (SDep
&)dep
);
220 ST
.adjustSchedDependency(OpSU
, SU
, (SDep
&)dep
);
229 /// BuildSchedGraph - Build the SUnit graph from the selection dag that we
230 /// are input. This SUnit graph is similar to the SelectionDAG, but
231 /// excludes nodes that aren't interesting to scheduling, and represents
232 /// flagged together nodes with a single SUnit.
233 void ScheduleDAGSDNodes::BuildSchedGraph() {
234 // Populate the SUnits array.
236 // Compute all the scheduling dependencies between nodes.
240 void ScheduleDAGSDNodes::ComputeLatency(SUnit
*SU
) {
241 const InstrItineraryData
&InstrItins
= TM
.getInstrItineraryData();
243 // Compute the latency for the node. We use the sum of the latencies for
244 // all nodes flagged together into this SUnit.
246 bool SawMachineOpcode
= false;
247 for (SDNode
*N
= SU
->getNode(); N
; N
= N
->getFlaggedNode())
248 if (N
->isMachineOpcode()) {
249 SawMachineOpcode
= true;
250 SU
->Latency
+= InstrItins
.
251 getStageLatency(TII
->get(N
->getMachineOpcode()).getSchedClass());
255 /// CountResults - The results of target nodes have register or immediate
256 /// operands first, then an optional chain, and optional flag operands (which do
257 /// not go into the resulting MachineInstr).
258 unsigned ScheduleDAGSDNodes::CountResults(SDNode
*Node
) {
259 unsigned N
= Node
->getNumValues();
260 while (N
&& Node
->getValueType(N
- 1) == MVT::Flag
)
262 if (N
&& Node
->getValueType(N
- 1) == MVT::Other
)
263 --N
; // Skip over chain result.
267 /// CountOperands - The inputs to target nodes have any actual inputs first,
268 /// followed by special operands that describe memory references, then an
269 /// optional chain operand, then an optional flag operand. Compute the number
270 /// of actual operands that will go into the resulting MachineInstr.
271 unsigned ScheduleDAGSDNodes::CountOperands(SDNode
*Node
) {
272 unsigned N
= ComputeMemOperandsEnd(Node
);
273 while (N
&& isa
<MemOperandSDNode
>(Node
->getOperand(N
- 1).getNode()))
274 --N
; // Ignore MEMOPERAND nodes
278 /// ComputeMemOperandsEnd - Find the index one past the last MemOperandSDNode
280 unsigned ScheduleDAGSDNodes::ComputeMemOperandsEnd(SDNode
*Node
) {
281 unsigned N
= Node
->getNumOperands();
282 while (N
&& Node
->getOperand(N
- 1).getValueType() == MVT::Flag
)
284 if (N
&& Node
->getOperand(N
- 1).getValueType() == MVT::Other
)
285 --N
; // Ignore chain if it exists.
290 void ScheduleDAGSDNodes::dumpNode(const SUnit
*SU
) const {
291 if (!SU
->getNode()) {
292 errs() << "PHYS REG COPY\n";
296 SU
->getNode()->dump(DAG
);
298 SmallVector
<SDNode
*, 4> FlaggedNodes
;
299 for (SDNode
*N
= SU
->getNode()->getFlaggedNode(); N
; N
= N
->getFlaggedNode())
300 FlaggedNodes
.push_back(N
);
301 while (!FlaggedNodes
.empty()) {
303 FlaggedNodes
.back()->dump(DAG
);
305 FlaggedNodes
.pop_back();