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