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