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 ScheduleDAG::~ScheduleDAG() {}
35 /// CalculateDepths - compute depths using algorithms for the longest
37 void ScheduleDAG::CalculateDepths() {
38 unsigned DAGSize = SUnits.size();
39 std::vector<SUnit*> WorkList;
40 WorkList.reserve(DAGSize);
42 // Initialize the data structures
43 for (unsigned i = 0, e = DAGSize; i != e; ++i) {
44 SUnit *SU = &SUnits[i];
45 unsigned Degree = SU->Preds.size();
46 // Temporarily use the Depth field as scratch space for the degree count.
49 // Is it a node without dependencies?
51 assert(SU->Preds.empty() && "SUnit should have no predecessors");
53 WorkList.push_back(SU);
57 // Process nodes in the topological order
58 while (!WorkList.empty()) {
59 SUnit *SU = WorkList.back();
63 // Use dynamic programming:
64 // When current node is being processed, all of its dependencies
65 // are already processed.
66 // So, just iterate over all predecessors and take the longest path
67 for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
69 unsigned PredDepth = I->Dep->Depth;
70 if (PredDepth+1 > SUDepth) {
71 SUDepth = PredDepth + 1;
77 // Update degrees of all nodes depending on current SUnit
78 for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
82 // If all dependencies of the node are processed already,
83 // then the longest path for the node can be computed now
84 WorkList.push_back(SU);
89 /// CalculateHeights - compute heights using algorithms for the longest
91 void ScheduleDAG::CalculateHeights() {
92 unsigned DAGSize = SUnits.size();
93 std::vector<SUnit*> WorkList;
94 WorkList.reserve(DAGSize);
96 // Initialize the data structures
97 for (unsigned i = 0, e = DAGSize; i != e; ++i) {
98 SUnit *SU = &SUnits[i];
99 unsigned Degree = SU->Succs.size();
100 // Temporarily use the Height field as scratch space for the degree count.
103 // Is it a node without dependencies?
105 assert(SU->Succs.empty() && "Something wrong");
106 assert(WorkList.empty() && "Should be empty");
107 // Collect leaf nodes
108 WorkList.push_back(SU);
112 // Process nodes in the topological order
113 while (!WorkList.empty()) {
114 SUnit *SU = WorkList.back();
116 unsigned SUHeight = 0;
118 // Use dynamic programming:
119 // When current node is being processed, all of its dependencies
120 // are already processed.
121 // So, just iterate over all successors and take the longest path
122 for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
124 unsigned SuccHeight = I->Dep->Height;
125 if (SuccHeight+1 > SUHeight) {
126 SUHeight = SuccHeight + 1;
130 SU->Height = SUHeight;
132 // Update degrees of all nodes depending on current SUnit
133 for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
137 // If all dependencies of the node are processed already,
138 // then the longest path for the node can be computed now
139 WorkList.push_back(SU);
144 /// dump - dump the schedule.
145 void ScheduleDAG::dumpSchedule() const {
146 for (unsigned i = 0, e = Sequence.size(); i != e; i++) {
147 if (SUnit *SU = Sequence[i])
150 cerr << "**** NOOP ****\n";
155 /// Run - perform scheduling.
157 void ScheduleDAG::Run() {
160 DOUT << "*** Final schedule ***\n";
161 DEBUG(dumpSchedule());
165 /// SUnit - Scheduling unit. It's an wrapper around either a single SDNode or
166 /// a group of nodes flagged together.
167 void SUnit::dump(const ScheduleDAG *G) const {
168 cerr << "SU(" << NodeNum << "): ";
172 void SUnit::dumpAll(const ScheduleDAG *G) const {
175 cerr << " # preds left : " << NumPredsLeft << "\n";
176 cerr << " # succs left : " << NumSuccsLeft << "\n";
177 cerr << " Latency : " << Latency << "\n";
178 cerr << " Depth : " << Depth << "\n";
179 cerr << " Height : " << Height << "\n";
181 if (Preds.size() != 0) {
182 cerr << " Predecessors:\n";
183 for (SUnit::const_succ_iterator I = Preds.begin(), E = Preds.end();
189 cerr << I->Dep << " - SU(" << I->Dep->NodeNum << ")";
195 if (Succs.size() != 0) {
196 cerr << " Successors:\n";
197 for (SUnit::const_succ_iterator I = Succs.begin(), E = Succs.end();
203 cerr << I->Dep << " - SU(" << I->Dep->NodeNum << ")";
213 /// VerifySchedule - Verify that all SUnits were scheduled and that
214 /// their state is consistent.
216 void ScheduleDAG::VerifySchedule(bool isBottomUp) {
217 bool AnyNotSched = false;
218 unsigned DeadNodes = 0;
220 for (unsigned i = 0, e = SUnits.size(); i != e; ++i) {
221 if (!SUnits[i].isScheduled) {
222 if (SUnits[i].NumPreds == 0 && SUnits[i].NumSuccs == 0) {
227 cerr << "*** Scheduling failed! ***\n";
228 SUnits[i].dump(this);
229 cerr << "has not been scheduled!\n";
232 if (SUnits[i].isScheduled && SUnits[i].Cycle > (unsigned)INT_MAX) {
234 cerr << "*** Scheduling failed! ***\n";
235 SUnits[i].dump(this);
236 cerr << "has an unexpected Cycle value!\n";
240 if (SUnits[i].NumSuccsLeft != 0) {
242 cerr << "*** Scheduling failed! ***\n";
243 SUnits[i].dump(this);
244 cerr << "has successors left!\n";
248 if (SUnits[i].NumPredsLeft != 0) {
250 cerr << "*** Scheduling failed! ***\n";
251 SUnits[i].dump(this);
252 cerr << "has predecessors left!\n";
257 for (unsigned i = 0, e = Sequence.size(); i != e; ++i)
260 assert(!AnyNotSched);
261 assert(Sequence.size() + DeadNodes - Noops == SUnits.size() &&
262 "The number of nodes scheduled doesn't match the expected number!");