1 //===---- ScheduleDAG.cpp - Implement the ScheduleDAG 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 "llvm/CodeGen/ScheduleDAG.h"
17 #include "llvm/Target/TargetMachine.h"
18 #include "llvm/Target/TargetInstrInfo.h"
19 #include "llvm/Target/TargetRegisterInfo.h"
20 #include "llvm/Support/Debug.h"
23 ScheduleDAG::ScheduleDAG(SelectionDAG &dag, MachineBasicBlock *bb,
24 const TargetMachine &tm)
25 : DAG(dag), BB(bb), TM(tm), MRI(BB->getParent()->getRegInfo()) {
26 TII = TM.getInstrInfo();
27 MF = &DAG.getMachineFunction();
28 TRI = TM.getRegisterInfo();
29 TLI = &DAG.getTargetLoweringInfo();
30 ConstPool = BB->getParent()->getConstantPool();
33 /// CheckForPhysRegDependency - Check if the dependency between def and use of
34 /// a specified operand is a physical register dependency. If so, returns the
35 /// register and the cost of copying the register.
36 static void CheckForPhysRegDependency(SDNode *Def, SDNode *User, unsigned Op,
37 const TargetRegisterInfo *TRI,
38 const TargetInstrInfo *TII,
39 unsigned &PhysReg, int &Cost) {
40 if (Op != 2 || User->getOpcode() != ISD::CopyToReg)
43 unsigned Reg = cast<RegisterSDNode>(User->getOperand(1))->getReg();
44 if (TargetRegisterInfo::isVirtualRegister(Reg))
47 unsigned ResNo = User->getOperand(2).getResNo();
48 if (Def->isMachineOpcode()) {
49 const TargetInstrDesc &II = TII->get(Def->getMachineOpcode());
50 if (ResNo >= II.getNumDefs() &&
51 II.ImplicitDefs[ResNo - II.getNumDefs()] == Reg) {
53 const TargetRegisterClass *RC =
54 TRI->getPhysicalRegisterRegClass(Reg, Def->getValueType(ResNo));
55 Cost = RC->getCopyCost();
60 SUnit *ScheduleDAG::Clone(SUnit *Old) {
61 SUnit *SU = NewSUnit(Old->Node);
62 SU->OrigNode = Old->OrigNode;
63 SU->FlaggedNodes = Old->FlaggedNodes;
64 SU->Latency = Old->Latency;
65 SU->isTwoAddress = Old->isTwoAddress;
66 SU->isCommutable = Old->isCommutable;
67 SU->hasPhysRegDefs = Old->hasPhysRegDefs;
72 /// BuildSchedUnits - Build SUnits from the selection dag that we are input.
73 /// This SUnit graph is similar to the SelectionDAG, but represents flagged
74 /// together nodes with a single SUnit.
75 void ScheduleDAG::BuildSchedUnits() {
76 // Reserve entries in the vector for each of the SUnits we are creating. This
77 // ensure that reallocation of the vector won't happen, so SUnit*'s won't get
79 SUnits.reserve(DAG.allnodes_size());
81 // During scheduling, the NodeId field of SDNode is used to map SDNodes
82 // to their associated SUnits by holding SUnits table indices. A value
83 // of -1 means the SDNode does not yet have an associated SUnit.
84 for (SelectionDAG::allnodes_iterator NI = DAG.allnodes_begin(),
85 E = DAG.allnodes_end(); NI != E; ++NI)
88 for (SelectionDAG::allnodes_iterator NI = DAG.allnodes_begin(),
89 E = DAG.allnodes_end(); NI != E; ++NI) {
90 if (isPassiveNode(NI)) // Leaf node, e.g. a TargetImmediate.
93 // If this node has already been processed, stop now.
94 if (NI->getNodeId() != -1) continue;
96 SUnit *NodeSUnit = NewSUnit(NI);
98 // See if anything is flagged to this node, if so, add them to flagged
99 // nodes. Nodes can have at most one flag input and one flag output. Flags
100 // are required the be the last operand and result of a node.
102 // Scan up, adding flagged preds to FlaggedNodes.
104 if (N->getNumOperands() &&
105 N->getOperand(N->getNumOperands()-1).getValueType() == MVT::Flag) {
107 N = N->getOperand(N->getNumOperands()-1).getNode();
108 NodeSUnit->FlaggedNodes.push_back(N);
109 assert(N->getNodeId() == -1 && "Node already inserted!");
110 N->setNodeId(NodeSUnit->NodeNum);
111 } while (N->getNumOperands() &&
112 N->getOperand(N->getNumOperands()-1).getValueType()== MVT::Flag);
113 std::reverse(NodeSUnit->FlaggedNodes.begin(),
114 NodeSUnit->FlaggedNodes.end());
117 // Scan down, adding this node and any flagged succs to FlaggedNodes if they
118 // have a user of the flag operand.
120 while (N->getValueType(N->getNumValues()-1) == MVT::Flag) {
121 SDValue FlagVal(N, N->getNumValues()-1);
123 // There are either zero or one users of the Flag result.
124 bool HasFlagUse = false;
125 for (SDNode::use_iterator UI = N->use_begin(), E = N->use_end();
127 if (FlagVal.isOperandOf(*UI)) {
129 NodeSUnit->FlaggedNodes.push_back(N);
130 assert(N->getNodeId() == -1 && "Node already inserted!");
131 N->setNodeId(NodeSUnit->NodeNum);
135 if (!HasFlagUse) break;
138 // Now all flagged nodes are in FlaggedNodes and N is the bottom-most node.
141 assert(N->getNodeId() == -1 && "Node already inserted!");
142 N->setNodeId(NodeSUnit->NodeNum);
144 ComputeLatency(NodeSUnit);
147 // Pass 2: add the preds, succs, etc.
148 for (unsigned su = 0, e = SUnits.size(); su != e; ++su) {
149 SUnit *SU = &SUnits[su];
150 SDNode *MainNode = SU->Node;
152 if (MainNode->isMachineOpcode()) {
153 unsigned Opc = MainNode->getMachineOpcode();
154 const TargetInstrDesc &TID = TII->get(Opc);
155 for (unsigned i = 0; i != TID.getNumOperands(); ++i) {
156 if (TID.getOperandConstraint(i, TOI::TIED_TO) != -1) {
157 SU->isTwoAddress = true;
161 if (TID.isCommutable())
162 SU->isCommutable = true;
165 // Find all predecessors and successors of the group.
166 // Temporarily add N to make code simpler.
167 SU->FlaggedNodes.push_back(MainNode);
169 for (unsigned n = 0, e = SU->FlaggedNodes.size(); n != e; ++n) {
170 SDNode *N = SU->FlaggedNodes[n];
171 if (N->isMachineOpcode() &&
172 TII->get(N->getMachineOpcode()).getImplicitDefs() &&
173 CountResults(N) > TII->get(N->getMachineOpcode()).getNumDefs())
174 SU->hasPhysRegDefs = true;
176 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) {
177 SDNode *OpN = N->getOperand(i).getNode();
178 if (isPassiveNode(OpN)) continue; // Not scheduled.
179 SUnit *OpSU = &SUnits[OpN->getNodeId()];
180 assert(OpSU && "Node has no SUnit!");
181 if (OpSU == SU) continue; // In the same group.
183 MVT OpVT = N->getOperand(i).getValueType();
184 assert(OpVT != MVT::Flag && "Flagged nodes should be in same sunit!");
185 bool isChain = OpVT == MVT::Other;
187 unsigned PhysReg = 0;
189 // Determine if this is a physical register dependency.
190 CheckForPhysRegDependency(OpN, N, i, TRI, TII, PhysReg, Cost);
191 SU->addPred(OpSU, isChain, false, PhysReg, Cost);
195 // Remove MainNode from FlaggedNodes again.
196 SU->FlaggedNodes.pop_back();
200 void ScheduleDAG::ComputeLatency(SUnit *SU) {
201 const InstrItineraryData &InstrItins = TM.getInstrItineraryData();
203 // Compute the latency for the node. We use the sum of the latencies for
204 // all nodes flagged together into this SUnit.
205 if (InstrItins.isEmpty()) {
206 // No latency information.
212 if (SU->Node->isMachineOpcode()) {
213 unsigned SchedClass = TII->get(SU->Node->getMachineOpcode()).getSchedClass();
214 const InstrStage *S = InstrItins.begin(SchedClass);
215 const InstrStage *E = InstrItins.end(SchedClass);
217 SU->Latency += S->Cycles;
219 for (unsigned i = 0, e = SU->FlaggedNodes.size(); i != e; ++i) {
220 SDNode *FNode = SU->FlaggedNodes[i];
221 if (FNode->isMachineOpcode()) {
222 unsigned SchedClass = TII->get(FNode->getMachineOpcode()).getSchedClass();
223 const InstrStage *S = InstrItins.begin(SchedClass);
224 const InstrStage *E = InstrItins.end(SchedClass);
226 SU->Latency += S->Cycles;
231 /// CalculateDepths - compute depths using algorithms for the longest
233 void ScheduleDAG::CalculateDepths() {
234 unsigned DAGSize = SUnits.size();
235 std::vector<SUnit*> WorkList;
236 WorkList.reserve(DAGSize);
238 // Initialize the data structures
239 for (unsigned i = 0, e = DAGSize; i != e; ++i) {
240 SUnit *SU = &SUnits[i];
241 unsigned Degree = SU->Preds.size();
242 // Temporarily use the Depth field as scratch space for the degree count.
245 // Is it a node without dependencies?
247 assert(SU->Preds.empty() && "SUnit should have no predecessors");
248 // Collect leaf nodes
249 WorkList.push_back(SU);
253 // Process nodes in the topological order
254 while (!WorkList.empty()) {
255 SUnit *SU = WorkList.back();
257 unsigned SUDepth = 0;
259 // Use dynamic programming:
260 // When current node is being processed, all of its dependencies
261 // are already processed.
262 // So, just iterate over all predecessors and take the longest path
263 for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
265 unsigned PredDepth = I->Dep->Depth;
266 if (PredDepth+1 > SUDepth) {
267 SUDepth = PredDepth + 1;
273 // Update degrees of all nodes depending on current SUnit
274 for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
278 // If all dependencies of the node are processed already,
279 // then the longest path for the node can be computed now
280 WorkList.push_back(SU);
285 /// CalculateHeights - compute heights using algorithms for the longest
287 void ScheduleDAG::CalculateHeights() {
288 unsigned DAGSize = SUnits.size();
289 std::vector<SUnit*> WorkList;
290 WorkList.reserve(DAGSize);
292 // Initialize the data structures
293 for (unsigned i = 0, e = DAGSize; i != e; ++i) {
294 SUnit *SU = &SUnits[i];
295 unsigned Degree = SU->Succs.size();
296 // Temporarily use the Height field as scratch space for the degree count.
299 // Is it a node without dependencies?
301 assert(SU->Succs.empty() && "Something wrong");
302 assert(WorkList.empty() && "Should be empty");
303 // Collect leaf nodes
304 WorkList.push_back(SU);
308 // Process nodes in the topological order
309 while (!WorkList.empty()) {
310 SUnit *SU = WorkList.back();
312 unsigned SUHeight = 0;
314 // Use dynamic programming:
315 // When current node is being processed, all of its dependencies
316 // are already processed.
317 // So, just iterate over all successors and take the longest path
318 for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
320 unsigned SuccHeight = I->Dep->Height;
321 if (SuccHeight+1 > SUHeight) {
322 SUHeight = SuccHeight + 1;
326 SU->Height = SUHeight;
328 // Update degrees of all nodes depending on current SUnit
329 for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
333 // If all dependencies of the node are processed already,
334 // then the longest path for the node can be computed now
335 WorkList.push_back(SU);
340 /// CountResults - The results of target nodes have register or immediate
341 /// operands first, then an optional chain, and optional flag operands (which do
342 /// not go into the resulting MachineInstr).
343 unsigned ScheduleDAG::CountResults(SDNode *Node) {
344 unsigned N = Node->getNumValues();
345 while (N && Node->getValueType(N - 1) == MVT::Flag)
347 if (N && Node->getValueType(N - 1) == MVT::Other)
348 --N; // Skip over chain result.
352 /// CountOperands - The inputs to target nodes have any actual inputs first,
353 /// followed by special operands that describe memory references, then an
354 /// optional chain operand, then an optional flag operand. Compute the number
355 /// of actual operands that will go into the resulting MachineInstr.
356 unsigned ScheduleDAG::CountOperands(SDNode *Node) {
357 unsigned N = ComputeMemOperandsEnd(Node);
358 while (N && isa<MemOperandSDNode>(Node->getOperand(N - 1).getNode()))
359 --N; // Ignore MEMOPERAND nodes
363 /// ComputeMemOperandsEnd - Find the index one past the last MemOperandSDNode
365 unsigned ScheduleDAG::ComputeMemOperandsEnd(SDNode *Node) {
366 unsigned N = Node->getNumOperands();
367 while (N && Node->getOperand(N - 1).getValueType() == MVT::Flag)
369 if (N && Node->getOperand(N - 1).getValueType() == MVT::Other)
370 --N; // Ignore chain if it exists.
375 /// dump - dump the schedule.
376 void ScheduleDAG::dumpSchedule() const {
377 for (unsigned i = 0, e = Sequence.size(); i != e; i++) {
378 if (SUnit *SU = Sequence[i])
381 cerr << "**** NOOP ****\n";
386 /// Run - perform scheduling.
388 void ScheduleDAG::Run() {
391 DOUT << "*** Final schedule ***\n";
392 DEBUG(dumpSchedule());
396 /// SUnit - Scheduling unit. It's an wrapper around either a single SDNode or
397 /// a group of nodes flagged together.
398 void SUnit::dump(const SelectionDAG *G) const {
399 cerr << "SU(" << NodeNum << "): ";
403 cerr << "CROSS RC COPY ";
405 if (FlaggedNodes.size() != 0) {
406 for (unsigned i = 0, e = FlaggedNodes.size(); i != e; i++) {
408 FlaggedNodes[i]->dump(G);
414 void SUnit::dumpAll(const SelectionDAG *G) const {
417 cerr << " # preds left : " << NumPredsLeft << "\n";
418 cerr << " # succs left : " << NumSuccsLeft << "\n";
419 cerr << " Latency : " << Latency << "\n";
420 cerr << " Depth : " << Depth << "\n";
421 cerr << " Height : " << Height << "\n";
423 if (Preds.size() != 0) {
424 cerr << " Predecessors:\n";
425 for (SUnit::const_succ_iterator I = Preds.begin(), E = Preds.end();
431 cerr << I->Dep << " - SU(" << I->Dep->NodeNum << ")";
437 if (Succs.size() != 0) {
438 cerr << " Successors:\n";
439 for (SUnit::const_succ_iterator I = Succs.begin(), E = Succs.end();
445 cerr << I->Dep << " - SU(" << I->Dep->NodeNum << ")";