ScheduleDAGFast.cpp revision 9e64bbb322417c09f27afdf08e3946287c9df5aa
1//===----- ScheduleDAGFast.cpp - Fast poor list scheduler -----------------===// 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 a fast scheduler. 11// 12//===----------------------------------------------------------------------===// 13 14#define DEBUG_TYPE "pre-RA-sched" 15#include "ScheduleDAGSDNodes.h" 16#include "llvm/CodeGen/SchedulerRegistry.h" 17#include "llvm/CodeGen/SelectionDAGISel.h" 18#include "llvm/Target/TargetRegisterInfo.h" 19#include "llvm/Target/TargetData.h" 20#include "llvm/Target/TargetInstrInfo.h" 21#include "llvm/Support/Debug.h" 22#include "llvm/Support/Compiler.h" 23#include "llvm/ADT/SmallSet.h" 24#include "llvm/ADT/Statistic.h" 25#include "llvm/ADT/STLExtras.h" 26#include "llvm/Support/CommandLine.h" 27using namespace llvm; 28 29STATISTIC(NumUnfolds, "Number of nodes unfolded"); 30STATISTIC(NumDups, "Number of duplicated nodes"); 31STATISTIC(NumPRCopies, "Number of physical copies"); 32 33static RegisterScheduler 34 fastDAGScheduler("fast", "Fast suboptimal list scheduling", 35 createFastDAGScheduler); 36 37namespace { 38 /// FastPriorityQueue - A degenerate priority queue that considers 39 /// all nodes to have the same priority. 40 /// 41 struct VISIBILITY_HIDDEN FastPriorityQueue { 42 SmallVector<SUnit *, 16> Queue; 43 44 bool empty() const { return Queue.empty(); } 45 46 void push(SUnit *U) { 47 Queue.push_back(U); 48 } 49 50 SUnit *pop() { 51 if (empty()) return NULL; 52 SUnit *V = Queue.back(); 53 Queue.pop_back(); 54 return V; 55 } 56 }; 57 58//===----------------------------------------------------------------------===// 59/// ScheduleDAGFast - The actual "fast" list scheduler implementation. 60/// 61class VISIBILITY_HIDDEN ScheduleDAGFast : public ScheduleDAGSDNodes { 62private: 63 /// AvailableQueue - The priority queue to use for the available SUnits. 64 FastPriorityQueue AvailableQueue; 65 66 /// LiveRegDefs - A set of physical registers and their definition 67 /// that are "live". These nodes must be scheduled before any other nodes that 68 /// modifies the registers can be scheduled. 69 unsigned NumLiveRegs; 70 std::vector<SUnit*> LiveRegDefs; 71 std::vector<unsigned> LiveRegCycles; 72 73public: 74 ScheduleDAGFast(MachineFunction &mf) 75 : ScheduleDAGSDNodes(mf) {} 76 77 void Schedule(); 78 79 /// AddPred - adds a predecessor edge to SUnit SU. 80 /// This returns true if this is a new predecessor. 81 void AddPred(SUnit *SU, const SDep &D) { 82 SU->addPred(D); 83 } 84 85 /// RemovePred - removes a predecessor edge from SUnit SU. 86 /// This returns true if an edge was removed. 87 void RemovePred(SUnit *SU, const SDep &D) { 88 SU->removePred(D); 89 } 90 91private: 92 void ReleasePred(SUnit *SU, SDep *PredEdge); 93 void ReleasePredecessors(SUnit *SU, unsigned CurCycle); 94 void ScheduleNodeBottomUp(SUnit*, unsigned); 95 SUnit *CopyAndMoveSuccessors(SUnit*); 96 void InsertCopiesAndMoveSuccs(SUnit*, unsigned, 97 const TargetRegisterClass*, 98 const TargetRegisterClass*, 99 SmallVector<SUnit*, 2>&); 100 bool DelayForLiveRegsBottomUp(SUnit*, SmallVector<unsigned, 4>&); 101 void ListScheduleBottomUp(); 102 103 /// ForceUnitLatencies - The fast scheduler doesn't care about real latencies. 104 bool ForceUnitLatencies() const { return true; } 105}; 106} // end anonymous namespace 107 108 109/// Schedule - Schedule the DAG using list scheduling. 110void ScheduleDAGFast::Schedule() { 111 DOUT << "********** List Scheduling **********\n"; 112 113 NumLiveRegs = 0; 114 LiveRegDefs.resize(TRI->getNumRegs(), NULL); 115 LiveRegCycles.resize(TRI->getNumRegs(), 0); 116 117 // Build the scheduling graph. 118 BuildSchedGraph(); 119 120 DEBUG(for (unsigned su = 0, e = SUnits.size(); su != e; ++su) 121 SUnits[su].dumpAll(this)); 122 123 // Execute the actual scheduling loop. 124 ListScheduleBottomUp(); 125} 126 127//===----------------------------------------------------------------------===// 128// Bottom-Up Scheduling 129//===----------------------------------------------------------------------===// 130 131/// ReleasePred - Decrement the NumSuccsLeft count of a predecessor. Add it to 132/// the AvailableQueue if the count reaches zero. Also update its cycle bound. 133void ScheduleDAGFast::ReleasePred(SUnit *SU, SDep *PredEdge) { 134 SUnit *PredSU = PredEdge->getSUnit(); 135 --PredSU->NumSuccsLeft; 136 137#ifndef NDEBUG 138 if (PredSU->NumSuccsLeft < 0) { 139 cerr << "*** Scheduling failed! ***\n"; 140 PredSU->dump(this); 141 cerr << " has been released too many times!\n"; 142 assert(0); 143 } 144#endif 145 146 // If all the node's successors are scheduled, this node is ready 147 // to be scheduled. Ignore the special EntrySU node. 148 if (PredSU->NumSuccsLeft == 0 && PredSU != &EntrySU) { 149 PredSU->isAvailable = true; 150 AvailableQueue.push(PredSU); 151 } 152} 153 154void ScheduleDAGFast::ReleasePredecessors(SUnit *SU, unsigned CurCycle) { 155 // Bottom up: release predecessors 156 for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); 157 I != E; ++I) { 158 ReleasePred(SU, &*I); 159 if (I->isAssignedRegDep()) { 160 // This is a physical register dependency and it's impossible or 161 // expensive to copy the register. Make sure nothing that can 162 // clobber the register is scheduled between the predecessor and 163 // this node. 164 if (!LiveRegDefs[I->getReg()]) { 165 ++NumLiveRegs; 166 LiveRegDefs[I->getReg()] = I->getSUnit(); 167 LiveRegCycles[I->getReg()] = CurCycle; 168 } 169 } 170 } 171} 172 173/// ScheduleNodeBottomUp - Add the node to the schedule. Decrement the pending 174/// count of its predecessors. If a predecessor pending count is zero, add it to 175/// the Available queue. 176void ScheduleDAGFast::ScheduleNodeBottomUp(SUnit *SU, unsigned CurCycle) { 177 DOUT << "*** Scheduling [" << CurCycle << "]: "; 178 DEBUG(SU->dump(this)); 179 180 assert(CurCycle >= SU->getHeight() && "Node scheduled below its height!"); 181 SU->setHeightToAtLeast(CurCycle); 182 Sequence.push_back(SU); 183 184 ReleasePredecessors(SU, CurCycle); 185 186 // Release all the implicit physical register defs that are live. 187 for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); 188 I != E; ++I) { 189 if (I->isAssignedRegDep()) { 190 if (LiveRegCycles[I->getReg()] == I->getSUnit()->getHeight()) { 191 assert(NumLiveRegs > 0 && "NumLiveRegs is already zero!"); 192 assert(LiveRegDefs[I->getReg()] == SU && 193 "Physical register dependency violated?"); 194 --NumLiveRegs; 195 LiveRegDefs[I->getReg()] = NULL; 196 LiveRegCycles[I->getReg()] = 0; 197 } 198 } 199 } 200 201 SU->isScheduled = true; 202} 203 204/// CopyAndMoveSuccessors - Clone the specified node and move its scheduled 205/// successors to the newly created node. 206SUnit *ScheduleDAGFast::CopyAndMoveSuccessors(SUnit *SU) { 207 if (SU->getNode()->getFlaggedNode()) 208 return NULL; 209 210 SDNode *N = SU->getNode(); 211 if (!N) 212 return NULL; 213 214 SUnit *NewSU; 215 bool TryUnfold = false; 216 for (unsigned i = 0, e = N->getNumValues(); i != e; ++i) { 217 MVT VT = N->getValueType(i); 218 if (VT == MVT::Flag) 219 return NULL; 220 else if (VT == MVT::Other) 221 TryUnfold = true; 222 } 223 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) { 224 const SDValue &Op = N->getOperand(i); 225 MVT VT = Op.getNode()->getValueType(Op.getResNo()); 226 if (VT == MVT::Flag) 227 return NULL; 228 } 229 230 if (TryUnfold) { 231 SmallVector<SDNode*, 2> NewNodes; 232 if (!TII->unfoldMemoryOperand(*DAG, N, NewNodes)) 233 return NULL; 234 235 DOUT << "Unfolding SU # " << SU->NodeNum << "\n"; 236 assert(NewNodes.size() == 2 && "Expected a load folding node!"); 237 238 N = NewNodes[1]; 239 SDNode *LoadNode = NewNodes[0]; 240 unsigned NumVals = N->getNumValues(); 241 unsigned OldNumVals = SU->getNode()->getNumValues(); 242 for (unsigned i = 0; i != NumVals; ++i) 243 DAG->ReplaceAllUsesOfValueWith(SDValue(SU->getNode(), i), SDValue(N, i)); 244 DAG->ReplaceAllUsesOfValueWith(SDValue(SU->getNode(), OldNumVals-1), 245 SDValue(LoadNode, 1)); 246 247 SUnit *NewSU = NewSUnit(N); 248 assert(N->getNodeId() == -1 && "Node already inserted!"); 249 N->setNodeId(NewSU->NodeNum); 250 251 const TargetInstrDesc &TID = TII->get(N->getMachineOpcode()); 252 for (unsigned i = 0; i != TID.getNumOperands(); ++i) { 253 if (TID.getOperandConstraint(i, TOI::TIED_TO) != -1) { 254 NewSU->isTwoAddress = true; 255 break; 256 } 257 } 258 if (TID.isCommutable()) 259 NewSU->isCommutable = true; 260 261 // LoadNode may already exist. This can happen when there is another 262 // load from the same location and producing the same type of value 263 // but it has different alignment or volatileness. 264 bool isNewLoad = true; 265 SUnit *LoadSU; 266 if (LoadNode->getNodeId() != -1) { 267 LoadSU = &SUnits[LoadNode->getNodeId()]; 268 isNewLoad = false; 269 } else { 270 LoadSU = NewSUnit(LoadNode); 271 LoadNode->setNodeId(LoadSU->NodeNum); 272 } 273 274 SDep ChainPred; 275 SmallVector<SDep, 4> ChainSuccs; 276 SmallVector<SDep, 4> LoadPreds; 277 SmallVector<SDep, 4> NodePreds; 278 SmallVector<SDep, 4> NodeSuccs; 279 for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); 280 I != E; ++I) { 281 if (I->isCtrl()) 282 ChainPred = *I; 283 else if (I->getSUnit()->getNode() && 284 I->getSUnit()->getNode()->isOperandOf(LoadNode)) 285 LoadPreds.push_back(*I); 286 else 287 NodePreds.push_back(*I); 288 } 289 for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); 290 I != E; ++I) { 291 if (I->isCtrl()) 292 ChainSuccs.push_back(*I); 293 else 294 NodeSuccs.push_back(*I); 295 } 296 297 if (ChainPred.getSUnit()) { 298 RemovePred(SU, ChainPred); 299 if (isNewLoad) 300 AddPred(LoadSU, ChainPred); 301 } 302 for (unsigned i = 0, e = LoadPreds.size(); i != e; ++i) { 303 const SDep &Pred = LoadPreds[i]; 304 RemovePred(SU, Pred); 305 if (isNewLoad) { 306 AddPred(LoadSU, Pred); 307 } 308 } 309 for (unsigned i = 0, e = NodePreds.size(); i != e; ++i) { 310 const SDep &Pred = NodePreds[i]; 311 RemovePred(SU, Pred); 312 AddPred(NewSU, Pred); 313 } 314 for (unsigned i = 0, e = NodeSuccs.size(); i != e; ++i) { 315 SDep D = NodeSuccs[i]; 316 SUnit *SuccDep = D.getSUnit(); 317 D.setSUnit(SU); 318 RemovePred(SuccDep, D); 319 D.setSUnit(NewSU); 320 AddPred(SuccDep, D); 321 } 322 for (unsigned i = 0, e = ChainSuccs.size(); i != e; ++i) { 323 SDep D = ChainSuccs[i]; 324 SUnit *SuccDep = D.getSUnit(); 325 D.setSUnit(SU); 326 RemovePred(SuccDep, D); 327 if (isNewLoad) { 328 D.setSUnit(LoadSU); 329 AddPred(SuccDep, D); 330 } 331 } 332 if (isNewLoad) { 333 AddPred(NewSU, SDep(LoadSU, SDep::Order, LoadSU->Latency)); 334 } 335 336 ++NumUnfolds; 337 338 if (NewSU->NumSuccsLeft == 0) { 339 NewSU->isAvailable = true; 340 return NewSU; 341 } 342 SU = NewSU; 343 } 344 345 DOUT << "Duplicating SU # " << SU->NodeNum << "\n"; 346 NewSU = Clone(SU); 347 348 // New SUnit has the exact same predecessors. 349 for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); 350 I != E; ++I) 351 if (!I->isArtificial()) 352 AddPred(NewSU, *I); 353 354 // Only copy scheduled successors. Cut them from old node's successor 355 // list and move them over. 356 SmallVector<std::pair<SUnit *, SDep>, 4> DelDeps; 357 for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); 358 I != E; ++I) { 359 if (I->isArtificial()) 360 continue; 361 SUnit *SuccSU = I->getSUnit(); 362 if (SuccSU->isScheduled) { 363 SDep D = *I; 364 D.setSUnit(NewSU); 365 AddPred(SuccSU, D); 366 D.setSUnit(SU); 367 DelDeps.push_back(std::make_pair(SuccSU, D)); 368 } 369 } 370 for (unsigned i = 0, e = DelDeps.size(); i != e; ++i) 371 RemovePred(DelDeps[i].first, DelDeps[i].second); 372 373 ++NumDups; 374 return NewSU; 375} 376 377/// InsertCopiesAndMoveSuccs - Insert register copies and move all 378/// scheduled successors of the given SUnit to the last copy. 379void ScheduleDAGFast::InsertCopiesAndMoveSuccs(SUnit *SU, unsigned Reg, 380 const TargetRegisterClass *DestRC, 381 const TargetRegisterClass *SrcRC, 382 SmallVector<SUnit*, 2> &Copies) { 383 SUnit *CopyFromSU = NewSUnit(static_cast<SDNode *>(NULL)); 384 CopyFromSU->CopySrcRC = SrcRC; 385 CopyFromSU->CopyDstRC = DestRC; 386 387 SUnit *CopyToSU = NewSUnit(static_cast<SDNode *>(NULL)); 388 CopyToSU->CopySrcRC = DestRC; 389 CopyToSU->CopyDstRC = SrcRC; 390 391 // Only copy scheduled successors. Cut them from old node's successor 392 // list and move them over. 393 SmallVector<std::pair<SUnit *, SDep>, 4> DelDeps; 394 for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); 395 I != E; ++I) { 396 if (I->isArtificial()) 397 continue; 398 SUnit *SuccSU = I->getSUnit(); 399 if (SuccSU->isScheduled) { 400 SDep D = *I; 401 D.setSUnit(CopyToSU); 402 AddPred(SuccSU, D); 403 DelDeps.push_back(std::make_pair(SuccSU, *I)); 404 } 405 } 406 for (unsigned i = 0, e = DelDeps.size(); i != e; ++i) { 407 RemovePred(DelDeps[i].first, DelDeps[i].second); 408 } 409 410 AddPred(CopyFromSU, SDep(SU, SDep::Data, SU->Latency, Reg)); 411 AddPred(CopyToSU, SDep(CopyFromSU, SDep::Data, CopyFromSU->Latency, 0)); 412 413 Copies.push_back(CopyFromSU); 414 Copies.push_back(CopyToSU); 415 416 ++NumPRCopies; 417} 418 419/// getPhysicalRegisterVT - Returns the ValueType of the physical register 420/// definition of the specified node. 421/// FIXME: Move to SelectionDAG? 422static MVT getPhysicalRegisterVT(SDNode *N, unsigned Reg, 423 const TargetInstrInfo *TII) { 424 const TargetInstrDesc &TID = TII->get(N->getMachineOpcode()); 425 assert(TID.ImplicitDefs && "Physical reg def must be in implicit def list!"); 426 unsigned NumRes = TID.getNumDefs(); 427 for (const unsigned *ImpDef = TID.getImplicitDefs(); *ImpDef; ++ImpDef) { 428 if (Reg == *ImpDef) 429 break; 430 ++NumRes; 431 } 432 return N->getValueType(NumRes); 433} 434 435/// DelayForLiveRegsBottomUp - Returns true if it is necessary to delay 436/// scheduling of the given node to satisfy live physical register dependencies. 437/// If the specific node is the last one that's available to schedule, do 438/// whatever is necessary (i.e. backtracking or cloning) to make it possible. 439bool ScheduleDAGFast::DelayForLiveRegsBottomUp(SUnit *SU, 440 SmallVector<unsigned, 4> &LRegs){ 441 if (NumLiveRegs == 0) 442 return false; 443 444 SmallSet<unsigned, 4> RegAdded; 445 // If this node would clobber any "live" register, then it's not ready. 446 for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); 447 I != E; ++I) { 448 if (I->isAssignedRegDep()) { 449 unsigned Reg = I->getReg(); 450 if (LiveRegDefs[Reg] && LiveRegDefs[Reg] != I->getSUnit()) { 451 if (RegAdded.insert(Reg)) 452 LRegs.push_back(Reg); 453 } 454 for (const unsigned *Alias = TRI->getAliasSet(Reg); 455 *Alias; ++Alias) 456 if (LiveRegDefs[*Alias] && LiveRegDefs[*Alias] != I->getSUnit()) { 457 if (RegAdded.insert(*Alias)) 458 LRegs.push_back(*Alias); 459 } 460 } 461 } 462 463 for (SDNode *Node = SU->getNode(); Node; Node = Node->getFlaggedNode()) { 464 if (!Node->isMachineOpcode()) 465 continue; 466 const TargetInstrDesc &TID = TII->get(Node->getMachineOpcode()); 467 if (!TID.ImplicitDefs) 468 continue; 469 for (const unsigned *Reg = TID.ImplicitDefs; *Reg; ++Reg) { 470 if (LiveRegDefs[*Reg] && LiveRegDefs[*Reg] != SU) { 471 if (RegAdded.insert(*Reg)) 472 LRegs.push_back(*Reg); 473 } 474 for (const unsigned *Alias = TRI->getAliasSet(*Reg); 475 *Alias; ++Alias) 476 if (LiveRegDefs[*Alias] && LiveRegDefs[*Alias] != SU) { 477 if (RegAdded.insert(*Alias)) 478 LRegs.push_back(*Alias); 479 } 480 } 481 } 482 return !LRegs.empty(); 483} 484 485 486/// ListScheduleBottomUp - The main loop of list scheduling for bottom-up 487/// schedulers. 488void ScheduleDAGFast::ListScheduleBottomUp() { 489 unsigned CurCycle = 0; 490 491 // Release any predecessors of the special Exit node. 492 ReleasePredecessors(&ExitSU, CurCycle); 493 494 // Add root to Available queue. 495 if (!SUnits.empty()) { 496 SUnit *RootSU = &SUnits[DAG->getRoot().getNode()->getNodeId()]; 497 assert(RootSU->Succs.empty() && "Graph root shouldn't have successors!"); 498 RootSU->isAvailable = true; 499 AvailableQueue.push(RootSU); 500 } 501 502 // While Available queue is not empty, grab the node with the highest 503 // priority. If it is not ready put it back. Schedule the node. 504 SmallVector<SUnit*, 4> NotReady; 505 DenseMap<SUnit*, SmallVector<unsigned, 4> > LRegsMap; 506 Sequence.reserve(SUnits.size()); 507 while (!AvailableQueue.empty()) { 508 bool Delayed = false; 509 LRegsMap.clear(); 510 SUnit *CurSU = AvailableQueue.pop(); 511 while (CurSU) { 512 SmallVector<unsigned, 4> LRegs; 513 if (!DelayForLiveRegsBottomUp(CurSU, LRegs)) 514 break; 515 Delayed = true; 516 LRegsMap.insert(std::make_pair(CurSU, LRegs)); 517 518 CurSU->isPending = true; // This SU is not in AvailableQueue right now. 519 NotReady.push_back(CurSU); 520 CurSU = AvailableQueue.pop(); 521 } 522 523 // All candidates are delayed due to live physical reg dependencies. 524 // Try code duplication or inserting cross class copies 525 // to resolve it. 526 if (Delayed && !CurSU) { 527 if (!CurSU) { 528 // Try duplicating the nodes that produces these 529 // "expensive to copy" values to break the dependency. In case even 530 // that doesn't work, insert cross class copies. 531 SUnit *TrySU = NotReady[0]; 532 SmallVector<unsigned, 4> &LRegs = LRegsMap[TrySU]; 533 assert(LRegs.size() == 1 && "Can't handle this yet!"); 534 unsigned Reg = LRegs[0]; 535 SUnit *LRDef = LiveRegDefs[Reg]; 536 MVT VT = getPhysicalRegisterVT(LRDef->getNode(), Reg, TII); 537 const TargetRegisterClass *RC = 538 TRI->getPhysicalRegisterRegClass(Reg, VT); 539 const TargetRegisterClass *DestRC = TRI->getCrossCopyRegClass(RC); 540 541 // If cross copy register class is null, then it must be possible copy 542 // the value directly. Do not try duplicate the def. 543 SUnit *NewDef = 0; 544 if (DestRC) 545 NewDef = CopyAndMoveSuccessors(LRDef); 546 else 547 DestRC = RC; 548 if (!NewDef) { 549 // Issue copies, these can be expensive cross register class copies. 550 SmallVector<SUnit*, 2> Copies; 551 InsertCopiesAndMoveSuccs(LRDef, Reg, DestRC, RC, Copies); 552 DOUT << "Adding an edge from SU # " << TrySU->NodeNum 553 << " to SU #" << Copies.front()->NodeNum << "\n"; 554 AddPred(TrySU, SDep(Copies.front(), SDep::Order, /*Latency=*/1, 555 /*Reg=*/0, /*isNormalMemory=*/false, 556 /*isMustAlias=*/false, /*isArtificial=*/true)); 557 NewDef = Copies.back(); 558 } 559 560 DOUT << "Adding an edge from SU # " << NewDef->NodeNum 561 << " to SU #" << TrySU->NodeNum << "\n"; 562 LiveRegDefs[Reg] = NewDef; 563 AddPred(NewDef, SDep(TrySU, SDep::Order, /*Latency=*/1, 564 /*Reg=*/0, /*isNormalMemory=*/false, 565 /*isMustAlias=*/false, /*isArtificial=*/true)); 566 TrySU->isAvailable = false; 567 CurSU = NewDef; 568 } 569 570 if (!CurSU) { 571 assert(false && "Unable to resolve live physical register dependencies!"); 572 abort(); 573 } 574 } 575 576 // Add the nodes that aren't ready back onto the available list. 577 for (unsigned i = 0, e = NotReady.size(); i != e; ++i) { 578 NotReady[i]->isPending = false; 579 // May no longer be available due to backtracking. 580 if (NotReady[i]->isAvailable) 581 AvailableQueue.push(NotReady[i]); 582 } 583 NotReady.clear(); 584 585 if (CurSU) 586 ScheduleNodeBottomUp(CurSU, CurCycle); 587 ++CurCycle; 588 } 589 590 // Reverse the order if it is bottom up. 591 std::reverse(Sequence.begin(), Sequence.end()); 592 593 594#ifndef NDEBUG 595 // Verify that all SUnits were scheduled. 596 bool AnyNotSched = false; 597 unsigned DeadNodes = 0; 598 unsigned Noops = 0; 599 for (unsigned i = 0, e = SUnits.size(); i != e; ++i) { 600 if (!SUnits[i].isScheduled) { 601 if (SUnits[i].NumPreds == 0 && SUnits[i].NumSuccs == 0) { 602 ++DeadNodes; 603 continue; 604 } 605 if (!AnyNotSched) 606 cerr << "*** List scheduling failed! ***\n"; 607 SUnits[i].dump(this); 608 cerr << "has not been scheduled!\n"; 609 AnyNotSched = true; 610 } 611 if (SUnits[i].NumSuccsLeft != 0) { 612 if (!AnyNotSched) 613 cerr << "*** List scheduling failed! ***\n"; 614 SUnits[i].dump(this); 615 cerr << "has successors left!\n"; 616 AnyNotSched = true; 617 } 618 } 619 for (unsigned i = 0, e = Sequence.size(); i != e; ++i) 620 if (!Sequence[i]) 621 ++Noops; 622 assert(!AnyNotSched); 623 assert(Sequence.size() + DeadNodes - Noops == SUnits.size() && 624 "The number of nodes scheduled doesn't match the expected number!"); 625#endif 626} 627 628//===----------------------------------------------------------------------===// 629// Public Constructor Functions 630//===----------------------------------------------------------------------===// 631 632llvm::ScheduleDAG* llvm::createFastDAGScheduler(SelectionDAGISel *IS, bool) { 633 return new ScheduleDAGFast(*IS->MF); 634} 635