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();
28 TRI = TM.getRegisterInfo();
29 TLI = TM.getTargetLowering();
30 ConstPool = MF->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->getNode());
62 SU->OrigNode = Old->OrigNode;
63 SU->Latency = Old->Latency;
64 SU->isTwoAddress = Old->isTwoAddress;
65 SU->isCommutable = Old->isCommutable;
66 SU->hasPhysRegDefs = Old->hasPhysRegDefs;
71 /// BuildSchedUnits - Build SUnits from the selection dag that we are input.
72 /// This SUnit graph is similar to the SelectionDAG, but represents flagged
73 /// together nodes with a single SUnit.
74 void ScheduleDAG::BuildSchedUnits() {
75 // For post-regalloc scheduling, build the SUnits from the MachineInstrs
76 // in the MachineBasicBlock.
78 BuildSchedUnitsFromMBB();
82 // Reserve entries in the vector for each of the SUnits we are creating. This
83 // ensure that reallocation of the vector won't happen, so SUnit*'s won't get
85 SUnits.reserve(DAG->allnodes_size());
87 // During scheduling, the NodeId field of SDNode is used to map SDNodes
88 // to their associated SUnits by holding SUnits table indices. A value
89 // of -1 means the SDNode does not yet have an associated SUnit.
90 for (SelectionDAG::allnodes_iterator NI = DAG->allnodes_begin(),
91 E = DAG->allnodes_end(); NI != E; ++NI)
94 for (SelectionDAG::allnodes_iterator NI = DAG->allnodes_begin(),
95 E = DAG->allnodes_end(); NI != E; ++NI) {
96 if (isPassiveNode(NI)) // Leaf node, e.g. a TargetImmediate.
99 // If this node has already been processed, stop now.
100 if (NI->getNodeId() != -1) continue;
102 SUnit *NodeSUnit = NewSUnit(NI);
104 // See if anything is flagged to this node, if so, add them to flagged
105 // nodes. Nodes can have at most one flag input and one flag output. Flags
106 // are required the be the last operand and result of a node.
108 // Scan up to find flagged preds.
110 if (N->getNumOperands() &&
111 N->getOperand(N->getNumOperands()-1).getValueType() == MVT::Flag) {
113 N = N->getOperand(N->getNumOperands()-1).getNode();
114 assert(N->getNodeId() == -1 && "Node already inserted!");
115 N->setNodeId(NodeSUnit->NodeNum);
116 } while (N->getNumOperands() &&
117 N->getOperand(N->getNumOperands()-1).getValueType()== MVT::Flag);
120 // Scan down to find any flagged succs.
122 while (N->getValueType(N->getNumValues()-1) == MVT::Flag) {
123 SDValue FlagVal(N, N->getNumValues()-1);
125 // There are either zero or one users of the Flag result.
126 bool HasFlagUse = false;
127 for (SDNode::use_iterator UI = N->use_begin(), E = N->use_end();
129 if (FlagVal.isOperandOf(*UI)) {
131 assert(N->getNodeId() == -1 && "Node already inserted!");
132 N->setNodeId(NodeSUnit->NodeNum);
136 if (!HasFlagUse) break;
139 // If there are flag operands involved, N is now the bottom-most node
140 // of the sequence of nodes that are flagged together.
142 NodeSUnit->setNode(N);
143 assert(N->getNodeId() == -1 && "Node already inserted!");
144 N->setNodeId(NodeSUnit->NodeNum);
146 ComputeLatency(NodeSUnit);
149 // Pass 2: add the preds, succs, etc.
150 for (unsigned su = 0, e = SUnits.size(); su != e; ++su) {
151 SUnit *SU = &SUnits[su];
152 SDNode *MainNode = SU->getNode();
154 if (MainNode->isMachineOpcode()) {
155 unsigned Opc = MainNode->getMachineOpcode();
156 const TargetInstrDesc &TID = TII->get(Opc);
157 for (unsigned i = 0; i != TID.getNumOperands(); ++i) {
158 if (TID.getOperandConstraint(i, TOI::TIED_TO) != -1) {
159 SU->isTwoAddress = true;
163 if (TID.isCommutable())
164 SU->isCommutable = true;
167 // Find all predecessors and successors of the group.
168 for (SDNode *N = SU->getNode(); N; N = N->getFlaggedNode()) {
169 if (N->isMachineOpcode() &&
170 TII->get(N->getMachineOpcode()).getImplicitDefs() &&
171 CountResults(N) > TII->get(N->getMachineOpcode()).getNumDefs())
172 SU->hasPhysRegDefs = true;
174 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) {
175 SDNode *OpN = N->getOperand(i).getNode();
176 if (isPassiveNode(OpN)) continue; // Not scheduled.
177 SUnit *OpSU = &SUnits[OpN->getNodeId()];
178 assert(OpSU && "Node has no SUnit!");
179 if (OpSU == SU) continue; // In the same group.
181 MVT OpVT = N->getOperand(i).getValueType();
182 assert(OpVT != MVT::Flag && "Flagged nodes should be in same sunit!");
183 bool isChain = OpVT == MVT::Other;
185 unsigned PhysReg = 0;
187 // Determine if this is a physical register dependency.
188 CheckForPhysRegDependency(OpN, N, i, TRI, TII, PhysReg, Cost);
189 SU->addPred(OpSU, isChain, false, PhysReg, Cost);
195 void ScheduleDAG::BuildSchedUnitsFromMBB() {
197 SUnits.reserve(BB->size());
199 std::vector<SUnit *> PendingLoads;
200 SUnit *Terminator = 0;
202 SUnit *Defs[TargetRegisterInfo::FirstVirtualRegister] = {};
203 std::vector<SUnit *> Uses[TargetRegisterInfo::FirstVirtualRegister] = {};
204 int Cost = 1; // FIXME
206 for (MachineBasicBlock::iterator MII = BB->end(), MIE = BB->begin();
208 MachineInstr *MI = prior(MII);
209 SUnit *SU = NewSUnit(MI);
211 for (unsigned j = 0, n = MI->getNumOperands(); j != n; ++j) {
212 const MachineOperand &MO = MI->getOperand(j);
213 if (!MO.isReg()) continue;
214 unsigned Reg = MO.getReg();
215 if (Reg == 0) continue;
217 assert(TRI->isPhysicalRegister(Reg) && "Virtual register encountered!");
218 std::vector<SUnit *> &UseList = Uses[Reg];
219 SUnit *&Def = Defs[Reg];
220 // Optionally add output and anti dependences
221 if (Def && Def != SU)
222 Def->addPred(SU, /*isCtrl=*/true, /*isSpecial=*/false,
223 /*PhyReg=*/Reg, Cost);
224 for (const unsigned *Alias = TRI->getAliasSet(Reg); *Alias; ++Alias) {
225 SUnit *&Def = Defs[*Alias];
226 if (Def && Def != SU)
227 Def->addPred(SU, /*isCtrl=*/true, /*isSpecial=*/false,
228 /*PhyReg=*/*Alias, Cost);
232 // Add any data dependencies.
233 for (unsigned i = 0, e = UseList.size(); i != e; ++i)
234 if (UseList[i] != SU)
235 UseList[i]->addPred(SU, /*isCtrl=*/false, /*isSpecial=*/false,
236 /*PhysReg=*/Reg, Cost);
237 for (const unsigned *Alias = TRI->getAliasSet(Reg); *Alias; ++Alias) {
238 std::vector<SUnit *> &UseList = Uses[*Alias];
239 for (unsigned i = 0, e = UseList.size(); i != e; ++i)
240 if (UseList[i] != SU)
241 UseList[i]->addPred(SU, /*isCtrl=*/false, /*isSpecial=*/false,
242 /*PhysReg=*/*Alias, Cost);
248 UseList.push_back(SU);
253 if (!MI->isSafeToMove(TII, False)) {
255 Chain->addPred(SU, /*isCtrl=*/false, /*isSpecial=*/false);
256 for (unsigned k = 0, m = PendingLoads.size(); k != m; ++k)
257 PendingLoads[k]->addPred(SU, /*isCtrl=*/false, /*isSpecial=*/false);
258 PendingLoads.clear();
260 } else if (!MI->isSafeToMove(TII, True)) {
262 Chain->addPred(SU, /*isCtrl=*/false, /*isSpecial=*/false);
263 PendingLoads.push_back(SU);
265 if (Terminator && SU->Succs.empty())
266 Terminator->addPred(SU, /*isCtrl=*/false, /*isSpecial=*/false);
267 if (MI->getDesc().isTerminator())
272 void ScheduleDAG::ComputeLatency(SUnit *SU) {
273 const InstrItineraryData &InstrItins = TM.getInstrItineraryData();
275 // Compute the latency for the node. We use the sum of the latencies for
276 // all nodes flagged together into this SUnit.
277 if (InstrItins.isEmpty()) {
278 // No latency information.
284 for (SDNode *N = SU->getNode(); N; N = N->getFlaggedNode()) {
285 if (N->isMachineOpcode()) {
286 unsigned SchedClass = TII->get(N->getMachineOpcode()).getSchedClass();
287 const InstrStage *S = InstrItins.begin(SchedClass);
288 const InstrStage *E = InstrItins.end(SchedClass);
290 SU->Latency += S->Cycles;
295 /// CalculateDepths - compute depths using algorithms for the longest
297 void ScheduleDAG::CalculateDepths() {
298 unsigned DAGSize = SUnits.size();
299 std::vector<SUnit*> WorkList;
300 WorkList.reserve(DAGSize);
302 // Initialize the data structures
303 for (unsigned i = 0, e = DAGSize; i != e; ++i) {
304 SUnit *SU = &SUnits[i];
305 unsigned Degree = SU->Preds.size();
306 // Temporarily use the Depth field as scratch space for the degree count.
309 // Is it a node without dependencies?
311 assert(SU->Preds.empty() && "SUnit should have no predecessors");
312 // Collect leaf nodes
313 WorkList.push_back(SU);
317 // Process nodes in the topological order
318 while (!WorkList.empty()) {
319 SUnit *SU = WorkList.back();
321 unsigned SUDepth = 0;
323 // Use dynamic programming:
324 // When current node is being processed, all of its dependencies
325 // are already processed.
326 // So, just iterate over all predecessors and take the longest path
327 for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
329 unsigned PredDepth = I->Dep->Depth;
330 if (PredDepth+1 > SUDepth) {
331 SUDepth = PredDepth + 1;
337 // Update degrees of all nodes depending on current SUnit
338 for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
342 // If all dependencies of the node are processed already,
343 // then the longest path for the node can be computed now
344 WorkList.push_back(SU);
349 /// CalculateHeights - compute heights using algorithms for the longest
351 void ScheduleDAG::CalculateHeights() {
352 unsigned DAGSize = SUnits.size();
353 std::vector<SUnit*> WorkList;
354 WorkList.reserve(DAGSize);
356 // Initialize the data structures
357 for (unsigned i = 0, e = DAGSize; i != e; ++i) {
358 SUnit *SU = &SUnits[i];
359 unsigned Degree = SU->Succs.size();
360 // Temporarily use the Height field as scratch space for the degree count.
363 // Is it a node without dependencies?
365 assert(SU->Succs.empty() && "Something wrong");
366 assert(WorkList.empty() && "Should be empty");
367 // Collect leaf nodes
368 WorkList.push_back(SU);
372 // Process nodes in the topological order
373 while (!WorkList.empty()) {
374 SUnit *SU = WorkList.back();
376 unsigned SUHeight = 0;
378 // Use dynamic programming:
379 // When current node is being processed, all of its dependencies
380 // are already processed.
381 // So, just iterate over all successors and take the longest path
382 for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
384 unsigned SuccHeight = I->Dep->Height;
385 if (SuccHeight+1 > SUHeight) {
386 SUHeight = SuccHeight + 1;
390 SU->Height = SUHeight;
392 // Update degrees of all nodes depending on current SUnit
393 for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
397 // If all dependencies of the node are processed already,
398 // then the longest path for the node can be computed now
399 WorkList.push_back(SU);
404 /// CountResults - The results of target nodes have register or immediate
405 /// operands first, then an optional chain, and optional flag operands (which do
406 /// not go into the resulting MachineInstr).
407 unsigned ScheduleDAG::CountResults(SDNode *Node) {
408 unsigned N = Node->getNumValues();
409 while (N && Node->getValueType(N - 1) == MVT::Flag)
411 if (N && Node->getValueType(N - 1) == MVT::Other)
412 --N; // Skip over chain result.
416 /// CountOperands - The inputs to target nodes have any actual inputs first,
417 /// followed by special operands that describe memory references, then an
418 /// optional chain operand, then an optional flag operand. Compute the number
419 /// of actual operands that will go into the resulting MachineInstr.
420 unsigned ScheduleDAG::CountOperands(SDNode *Node) {
421 unsigned N = ComputeMemOperandsEnd(Node);
422 while (N && isa<MemOperandSDNode>(Node->getOperand(N - 1).getNode()))
423 --N; // Ignore MEMOPERAND nodes
427 /// ComputeMemOperandsEnd - Find the index one past the last MemOperandSDNode
429 unsigned ScheduleDAG::ComputeMemOperandsEnd(SDNode *Node) {
430 unsigned N = Node->getNumOperands();
431 while (N && Node->getOperand(N - 1).getValueType() == MVT::Flag)
433 if (N && Node->getOperand(N - 1).getValueType() == MVT::Other)
434 --N; // Ignore chain if it exists.
439 /// dump - dump the schedule.
440 void ScheduleDAG::dumpSchedule() const {
441 for (unsigned i = 0, e = Sequence.size(); i != e; i++) {
442 if (SUnit *SU = Sequence[i])
445 cerr << "**** NOOP ****\n";
450 /// Run - perform scheduling.
452 void ScheduleDAG::Run() {
455 DOUT << "*** Final schedule ***\n";
456 DEBUG(dumpSchedule());
460 /// SUnit - Scheduling unit. It's an wrapper around either a single SDNode or
461 /// a group of nodes flagged together.
462 void SUnit::dump(const ScheduleDAG *G) const {
463 cerr << "SU(" << NodeNum << "): ";
465 getNode()->dump(G->DAG);
467 cerr << "CROSS RC COPY ";
469 SmallVector<SDNode *, 4> FlaggedNodes;
470 for (SDNode *N = getNode()->getFlaggedNode(); N; N = N->getFlaggedNode())
471 FlaggedNodes.push_back(N);
472 while (!FlaggedNodes.empty()) {
474 FlaggedNodes.back()->dump(G->DAG);
476 FlaggedNodes.pop_back();
480 void SUnit::dumpAll(const ScheduleDAG *G) const {
483 cerr << " # preds left : " << NumPredsLeft << "\n";
484 cerr << " # succs left : " << NumSuccsLeft << "\n";
485 cerr << " Latency : " << Latency << "\n";
486 cerr << " Depth : " << Depth << "\n";
487 cerr << " Height : " << Height << "\n";
489 if (Preds.size() != 0) {
490 cerr << " Predecessors:\n";
491 for (SUnit::const_succ_iterator I = Preds.begin(), E = Preds.end();
497 cerr << I->Dep << " - SU(" << I->Dep->NodeNum << ")";
503 if (Succs.size() != 0) {
504 cerr << " Successors:\n";
505 for (SUnit::const_succ_iterator I = Succs.begin(), E = Succs.end();
511 cerr << I->Dep << " - SU(" << I->Dep->NodeNum << ")";