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