ScheduleDAG.cpp revision b1bfe4e108453151c8b8dc01515eb3095385e054
1//===---- ScheduleDAG.cpp - Implement the ScheduleDAG class ---------------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This implements the ScheduleDAG class, which is a base class used by 11// scheduling implementation classes. 12// 13//===----------------------------------------------------------------------===// 14 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" 21#include <climits> 22using namespace llvm; 23 24ScheduleDAG::ScheduleDAG(SelectionDAG *dag, MachineBasicBlock *bb, 25 const TargetMachine &tm) 26 : DAG(dag), BB(bb), TM(tm), MRI(BB->getParent()->getRegInfo()) { 27 TII = TM.getInstrInfo(); 28 MF = BB->getParent(); 29 TRI = TM.getRegisterInfo(); 30 TLI = TM.getTargetLowering(); 31 ConstPool = MF->getConstantPool(); 32} 33 34ScheduleDAG::~ScheduleDAG() {} 35 36/// dump - dump the schedule. 37void ScheduleDAG::dumpSchedule() const { 38 for (unsigned i = 0, e = Sequence.size(); i != e; i++) { 39 if (SUnit *SU = Sequence[i]) 40 SU->dump(this); 41 else 42 cerr << "**** NOOP ****\n"; 43 } 44} 45 46 47/// Run - perform scheduling. 48/// 49void ScheduleDAG::Run() { 50 Schedule(); 51 52 DOUT << "*** Final schedule ***\n"; 53 DEBUG(dumpSchedule()); 54 DOUT << "\n"; 55} 56 57/// addPred - This adds the specified edge as a pred of the current node if 58/// not already. It also adds the current node as a successor of the 59/// specified node. 60void SUnit::addPred(const SDep &D) { 61 // If this node already has this depenence, don't add a redundant one. 62 for (unsigned i = 0, e = (unsigned)Preds.size(); i != e; ++i) 63 if (Preds[i] == D) 64 return; 65 // Now add a corresponding succ to N. 66 SDep P = D; 67 P.setSUnit(this); 68 SUnit *N = D.getSUnit(); 69 // Update the bookkeeping. 70 if (D.getKind() == SDep::Data) { 71 ++NumPreds; 72 ++N->NumSuccs; 73 } 74 if (!N->isScheduled) 75 ++NumPredsLeft; 76 if (!isScheduled) 77 ++N->NumSuccsLeft; 78 Preds.push_back(D); 79 N->Succs.push_back(P); 80 if (P.getLatency() != 0) { 81 this->setDepthDirty(); 82 N->setHeightDirty(); 83 } 84} 85 86/// removePred - This removes the specified edge as a pred of the current 87/// node if it exists. It also removes the current node as a successor of 88/// the specified node. 89void SUnit::removePred(const SDep &D) { 90 // Find the matching predecessor. 91 for (SmallVector<SDep, 4>::iterator I = Preds.begin(), E = Preds.end(); 92 I != E; ++I) 93 if (*I == D) { 94 bool FoundSucc = false; 95 // Find the corresponding successor in N. 96 SDep P = D; 97 P.setSUnit(this); 98 SUnit *N = D.getSUnit(); 99 for (SmallVector<SDep, 4>::iterator II = N->Succs.begin(), 100 EE = N->Succs.end(); II != EE; ++II) 101 if (*II == P) { 102 FoundSucc = true; 103 N->Succs.erase(II); 104 break; 105 } 106 assert(FoundSucc && "Mismatching preds / succs lists!"); 107 Preds.erase(I); 108 // Update the bookkeeping. 109 if (P.getKind() == SDep::Data) { 110 --NumPreds; 111 --N->NumSuccs; 112 } 113 if (!N->isScheduled) 114 --NumPredsLeft; 115 if (!isScheduled) 116 --N->NumSuccsLeft; 117 if (P.getLatency() != 0) { 118 this->setDepthDirty(); 119 N->setHeightDirty(); 120 } 121 return; 122 } 123} 124 125void SUnit::setDepthDirty() { 126 if (!isDepthCurrent) return; 127 SmallVector<SUnit*, 8> WorkList; 128 WorkList.push_back(this); 129 do { 130 SUnit *SU = WorkList.pop_back_val(); 131 SU->isDepthCurrent = false; 132 for (SUnit::const_succ_iterator I = SU->Succs.begin(), 133 E = SU->Succs.end(); I != E; ++I) { 134 SUnit *SuccSU = I->getSUnit(); 135 if (SuccSU->isDepthCurrent) 136 WorkList.push_back(SuccSU); 137 } 138 } while (!WorkList.empty()); 139} 140 141void SUnit::setHeightDirty() { 142 if (!isHeightCurrent) return; 143 SmallVector<SUnit*, 8> WorkList; 144 WorkList.push_back(this); 145 do { 146 SUnit *SU = WorkList.pop_back_val(); 147 SU->isHeightCurrent = false; 148 for (SUnit::const_pred_iterator I = SU->Preds.begin(), 149 E = SU->Preds.end(); I != E; ++I) { 150 SUnit *PredSU = I->getSUnit(); 151 if (PredSU->isHeightCurrent) 152 WorkList.push_back(PredSU); 153 } 154 } while (!WorkList.empty()); 155} 156 157/// setDepthToAtLeast - Update this node's successors to reflect the 158/// fact that this node's depth just increased. 159/// 160void SUnit::setDepthToAtLeast(unsigned NewDepth) { 161 if (NewDepth <= getDepth()) 162 return; 163 setDepthDirty(); 164 Depth = NewDepth; 165 isDepthCurrent = true; 166} 167 168/// setHeightToAtLeast - Update this node's predecessors to reflect the 169/// fact that this node's height just increased. 170/// 171void SUnit::setHeightToAtLeast(unsigned NewHeight) { 172 if (NewHeight <= getHeight()) 173 return; 174 setHeightDirty(); 175 Height = NewHeight; 176 isHeightCurrent = true; 177} 178 179/// ComputeDepth - Calculate the maximal path from the node to the exit. 180/// 181void SUnit::ComputeDepth() { 182 SmallVector<SUnit*, 8> WorkList; 183 WorkList.push_back(this); 184 do { 185 SUnit *Cur = WorkList.back(); 186 187 bool Done = true; 188 unsigned MaxPredDepth = 0; 189 for (SUnit::const_pred_iterator I = Cur->Preds.begin(), 190 E = Cur->Preds.end(); I != E; ++I) { 191 SUnit *PredSU = I->getSUnit(); 192 if (PredSU->isDepthCurrent) 193 MaxPredDepth = std::max(MaxPredDepth, 194 PredSU->Depth + I->getLatency()); 195 else { 196 Done = false; 197 WorkList.push_back(PredSU); 198 } 199 } 200 201 if (Done) { 202 WorkList.pop_back(); 203 if (MaxPredDepth != Cur->Depth) { 204 Cur->setDepthDirty(); 205 Cur->Depth = MaxPredDepth; 206 } 207 Cur->isDepthCurrent = true; 208 } 209 } while (!WorkList.empty()); 210} 211 212/// ComputeHeight - Calculate the maximal path from the node to the entry. 213/// 214void SUnit::ComputeHeight() { 215 SmallVector<SUnit*, 8> WorkList; 216 WorkList.push_back(this); 217 do { 218 SUnit *Cur = WorkList.back(); 219 220 bool Done = true; 221 unsigned MaxSuccHeight = 0; 222 for (SUnit::const_succ_iterator I = Cur->Succs.begin(), 223 E = Cur->Succs.end(); I != E; ++I) { 224 SUnit *SuccSU = I->getSUnit(); 225 if (SuccSU->isHeightCurrent) 226 MaxSuccHeight = std::max(MaxSuccHeight, 227 SuccSU->Height + I->getLatency()); 228 else { 229 Done = false; 230 WorkList.push_back(SuccSU); 231 } 232 } 233 234 if (Done) { 235 WorkList.pop_back(); 236 if (MaxSuccHeight != Cur->Height) { 237 Cur->setHeightDirty(); 238 Cur->Height = MaxSuccHeight; 239 } 240 Cur->isHeightCurrent = true; 241 } 242 } while (!WorkList.empty()); 243} 244 245/// SUnit - Scheduling unit. It's an wrapper around either a single SDNode or 246/// a group of nodes flagged together. 247void SUnit::dump(const ScheduleDAG *G) const { 248 cerr << "SU(" << NodeNum << "): "; 249 G->dumpNode(this); 250} 251 252void SUnit::dumpAll(const ScheduleDAG *G) const { 253 dump(G); 254 255 cerr << " # preds left : " << NumPredsLeft << "\n"; 256 cerr << " # succs left : " << NumSuccsLeft << "\n"; 257 cerr << " Latency : " << Latency << "\n"; 258 cerr << " Depth : " << Depth << "\n"; 259 cerr << " Height : " << Height << "\n"; 260 261 if (Preds.size() != 0) { 262 cerr << " Predecessors:\n"; 263 for (SUnit::const_succ_iterator I = Preds.begin(), E = Preds.end(); 264 I != E; ++I) { 265 cerr << " "; 266 switch (I->getKind()) { 267 case SDep::Data: cerr << "val "; break; 268 case SDep::Anti: cerr << "anti"; break; 269 case SDep::Output: cerr << "out "; break; 270 case SDep::Order: cerr << "ch "; break; 271 } 272 cerr << "#"; 273 cerr << I->getSUnit() << " - SU(" << I->getSUnit()->NodeNum << ")"; 274 if (I->isArtificial()) 275 cerr << " *"; 276 cerr << "\n"; 277 } 278 } 279 if (Succs.size() != 0) { 280 cerr << " Successors:\n"; 281 for (SUnit::const_succ_iterator I = Succs.begin(), E = Succs.end(); 282 I != E; ++I) { 283 cerr << " "; 284 switch (I->getKind()) { 285 case SDep::Data: cerr << "val "; break; 286 case SDep::Anti: cerr << "anti"; break; 287 case SDep::Output: cerr << "out "; break; 288 case SDep::Order: cerr << "ch "; break; 289 } 290 cerr << "#"; 291 cerr << I->getSUnit() << " - SU(" << I->getSUnit()->NodeNum << ")"; 292 if (I->isArtificial()) 293 cerr << " *"; 294 cerr << "\n"; 295 } 296 } 297 cerr << "\n"; 298} 299 300#ifndef NDEBUG 301/// VerifySchedule - Verify that all SUnits were scheduled and that 302/// their state is consistent. 303/// 304void ScheduleDAG::VerifySchedule(bool isBottomUp) { 305 bool AnyNotSched = false; 306 unsigned DeadNodes = 0; 307 unsigned Noops = 0; 308 for (unsigned i = 0, e = SUnits.size(); i != e; ++i) { 309 if (!SUnits[i].isScheduled) { 310 if (SUnits[i].NumPreds == 0 && SUnits[i].NumSuccs == 0) { 311 ++DeadNodes; 312 continue; 313 } 314 if (!AnyNotSched) 315 cerr << "*** Scheduling failed! ***\n"; 316 SUnits[i].dump(this); 317 cerr << "has not been scheduled!\n"; 318 AnyNotSched = true; 319 } 320 if (SUnits[i].isScheduled && 321 (isBottomUp ? SUnits[i].getHeight() : SUnits[i].getHeight()) > 322 unsigned(INT_MAX)) { 323 if (!AnyNotSched) 324 cerr << "*** Scheduling failed! ***\n"; 325 SUnits[i].dump(this); 326 cerr << "has an unexpected " 327 << (isBottomUp ? "Height" : "Depth") << " value!\n"; 328 AnyNotSched = true; 329 } 330 if (isBottomUp) { 331 if (SUnits[i].NumSuccsLeft != 0) { 332 if (!AnyNotSched) 333 cerr << "*** Scheduling failed! ***\n"; 334 SUnits[i].dump(this); 335 cerr << "has successors left!\n"; 336 AnyNotSched = true; 337 } 338 } else { 339 if (SUnits[i].NumPredsLeft != 0) { 340 if (!AnyNotSched) 341 cerr << "*** Scheduling failed! ***\n"; 342 SUnits[i].dump(this); 343 cerr << "has predecessors left!\n"; 344 AnyNotSched = true; 345 } 346 } 347 } 348 for (unsigned i = 0, e = Sequence.size(); i != e; ++i) 349 if (!Sequence[i]) 350 ++Noops; 351 assert(!AnyNotSched); 352 assert(Sequence.size() + DeadNodes - Noops == SUnits.size() && 353 "The number of nodes scheduled doesn't match the expected number!"); 354} 355#endif 356 357/// InitDAGTopologicalSorting - create the initial topological 358/// ordering from the DAG to be scheduled. 359/// 360/// The idea of the algorithm is taken from 361/// "Online algorithms for managing the topological order of 362/// a directed acyclic graph" by David J. Pearce and Paul H.J. Kelly 363/// This is the MNR algorithm, which was first introduced by 364/// A. Marchetti-Spaccamela, U. Nanni and H. Rohnert in 365/// "Maintaining a topological order under edge insertions". 366/// 367/// Short description of the algorithm: 368/// 369/// Topological ordering, ord, of a DAG maps each node to a topological 370/// index so that for all edges X->Y it is the case that ord(X) < ord(Y). 371/// 372/// This means that if there is a path from the node X to the node Z, 373/// then ord(X) < ord(Z). 374/// 375/// This property can be used to check for reachability of nodes: 376/// if Z is reachable from X, then an insertion of the edge Z->X would 377/// create a cycle. 378/// 379/// The algorithm first computes a topological ordering for the DAG by 380/// initializing the Index2Node and Node2Index arrays and then tries to keep 381/// the ordering up-to-date after edge insertions by reordering the DAG. 382/// 383/// On insertion of the edge X->Y, the algorithm first marks by calling DFS 384/// the nodes reachable from Y, and then shifts them using Shift to lie 385/// immediately after X in Index2Node. 386void ScheduleDAGTopologicalSort::InitDAGTopologicalSorting() { 387 unsigned DAGSize = SUnits.size(); 388 std::vector<SUnit*> WorkList; 389 WorkList.reserve(DAGSize); 390 391 Index2Node.resize(DAGSize); 392 Node2Index.resize(DAGSize); 393 394 // Initialize the data structures. 395 for (unsigned i = 0, e = DAGSize; i != e; ++i) { 396 SUnit *SU = &SUnits[i]; 397 int NodeNum = SU->NodeNum; 398 unsigned Degree = SU->Succs.size(); 399 // Temporarily use the Node2Index array as scratch space for degree counts. 400 Node2Index[NodeNum] = Degree; 401 402 // Is it a node without dependencies? 403 if (Degree == 0) { 404 assert(SU->Succs.empty() && "SUnit should have no successors"); 405 // Collect leaf nodes. 406 WorkList.push_back(SU); 407 } 408 } 409 410 int Id = DAGSize; 411 while (!WorkList.empty()) { 412 SUnit *SU = WorkList.back(); 413 WorkList.pop_back(); 414 Allocate(SU->NodeNum, --Id); 415 for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); 416 I != E; ++I) { 417 SUnit *SU = I->getSUnit(); 418 if (!--Node2Index[SU->NodeNum]) 419 // If all dependencies of the node are processed already, 420 // then the node can be computed now. 421 WorkList.push_back(SU); 422 } 423 } 424 425 Visited.resize(DAGSize); 426 427#ifndef NDEBUG 428 // Check correctness of the ordering 429 for (unsigned i = 0, e = DAGSize; i != e; ++i) { 430 SUnit *SU = &SUnits[i]; 431 for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); 432 I != E; ++I) { 433 assert(Node2Index[SU->NodeNum] > Node2Index[I->getSUnit()->NodeNum] && 434 "Wrong topological sorting"); 435 } 436 } 437#endif 438} 439 440/// AddPred - Updates the topological ordering to accomodate an edge 441/// to be added from SUnit X to SUnit Y. 442void ScheduleDAGTopologicalSort::AddPred(SUnit *Y, SUnit *X) { 443 int UpperBound, LowerBound; 444 LowerBound = Node2Index[Y->NodeNum]; 445 UpperBound = Node2Index[X->NodeNum]; 446 bool HasLoop = false; 447 // Is Ord(X) < Ord(Y) ? 448 if (LowerBound < UpperBound) { 449 // Update the topological order. 450 Visited.reset(); 451 DFS(Y, UpperBound, HasLoop); 452 assert(!HasLoop && "Inserted edge creates a loop!"); 453 // Recompute topological indexes. 454 Shift(Visited, LowerBound, UpperBound); 455 } 456} 457 458/// RemovePred - Updates the topological ordering to accomodate an 459/// an edge to be removed from the specified node N from the predecessors 460/// of the current node M. 461void ScheduleDAGTopologicalSort::RemovePred(SUnit *M, SUnit *N) { 462 // InitDAGTopologicalSorting(); 463} 464 465/// DFS - Make a DFS traversal to mark all nodes reachable from SU and mark 466/// all nodes affected by the edge insertion. These nodes will later get new 467/// topological indexes by means of the Shift method. 468void ScheduleDAGTopologicalSort::DFS(const SUnit *SU, int UpperBound, 469 bool& HasLoop) { 470 std::vector<const SUnit*> WorkList; 471 WorkList.reserve(SUnits.size()); 472 473 WorkList.push_back(SU); 474 do { 475 SU = WorkList.back(); 476 WorkList.pop_back(); 477 Visited.set(SU->NodeNum); 478 for (int I = SU->Succs.size()-1; I >= 0; --I) { 479 int s = SU->Succs[I].getSUnit()->NodeNum; 480 if (Node2Index[s] == UpperBound) { 481 HasLoop = true; 482 return; 483 } 484 // Visit successors if not already and in affected region. 485 if (!Visited.test(s) && Node2Index[s] < UpperBound) { 486 WorkList.push_back(SU->Succs[I].getSUnit()); 487 } 488 } 489 } while (!WorkList.empty()); 490} 491 492/// Shift - Renumber the nodes so that the topological ordering is 493/// preserved. 494void ScheduleDAGTopologicalSort::Shift(BitVector& Visited, int LowerBound, 495 int UpperBound) { 496 std::vector<int> L; 497 int shift = 0; 498 int i; 499 500 for (i = LowerBound; i <= UpperBound; ++i) { 501 // w is node at topological index i. 502 int w = Index2Node[i]; 503 if (Visited.test(w)) { 504 // Unmark. 505 Visited.reset(w); 506 L.push_back(w); 507 shift = shift + 1; 508 } else { 509 Allocate(w, i - shift); 510 } 511 } 512 513 for (unsigned j = 0; j < L.size(); ++j) { 514 Allocate(L[j], i - shift); 515 i = i + 1; 516 } 517} 518 519 520/// WillCreateCycle - Returns true if adding an edge from SU to TargetSU will 521/// create a cycle. 522bool ScheduleDAGTopologicalSort::WillCreateCycle(SUnit *SU, SUnit *TargetSU) { 523 if (IsReachable(TargetSU, SU)) 524 return true; 525 for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); 526 I != E; ++I) 527 if (I->isAssignedRegDep() && 528 IsReachable(TargetSU, I->getSUnit())) 529 return true; 530 return false; 531} 532 533/// IsReachable - Checks if SU is reachable from TargetSU. 534bool ScheduleDAGTopologicalSort::IsReachable(const SUnit *SU, 535 const SUnit *TargetSU) { 536 // If insertion of the edge SU->TargetSU would create a cycle 537 // then there is a path from TargetSU to SU. 538 int UpperBound, LowerBound; 539 LowerBound = Node2Index[TargetSU->NodeNum]; 540 UpperBound = Node2Index[SU->NodeNum]; 541 bool HasLoop = false; 542 // Is Ord(TargetSU) < Ord(SU) ? 543 if (LowerBound < UpperBound) { 544 Visited.reset(); 545 // There may be a path from TargetSU to SU. Check for it. 546 DFS(TargetSU, UpperBound, HasLoop); 547 } 548 return HasLoop; 549} 550 551/// Allocate - assign the topological index to the node n. 552void ScheduleDAGTopologicalSort::Allocate(int n, int index) { 553 Node2Index[n] = index; 554 Index2Node[index] = n; 555} 556 557ScheduleDAGTopologicalSort::ScheduleDAGTopologicalSort( 558 std::vector<SUnit> &sunits) 559 : SUnits(sunits) {} 560