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