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