ScheduleDAGFast.cpp revision 63a4c24616fafa2b86d6391308ffd93e012115e4
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 "InstrEmitter.h" 17#include "llvm/InlineAsm.h" 18#include "llvm/CodeGen/SchedulerRegistry.h" 19#include "llvm/CodeGen/SelectionDAGISel.h" 20#include "llvm/Target/TargetRegisterInfo.h" 21#include "llvm/DataLayout.h" 22#include "llvm/Target/TargetInstrInfo.h" 23#include "llvm/Support/Debug.h" 24#include "llvm/ADT/SmallSet.h" 25#include "llvm/ADT/Statistic.h" 26#include "llvm/ADT/STLExtras.h" 27#include "llvm/Support/ErrorHandling.h" 28#include "llvm/Support/raw_ostream.h" 29using namespace llvm; 30 31STATISTIC(NumUnfolds, "Number of nodes unfolded"); 32STATISTIC(NumDups, "Number of duplicated nodes"); 33STATISTIC(NumPRCopies, "Number of physical copies"); 34 35static RegisterScheduler 36 fastDAGScheduler("fast", "Fast suboptimal list scheduling", 37 createFastDAGScheduler); 38static RegisterScheduler 39 linearizeDAGScheduler("linearize", "Linearize DAG, no scheduling", 40 createDAGLinearizer); 41 42 43namespace { 44 /// FastPriorityQueue - A degenerate priority queue that considers 45 /// all nodes to have the same priority. 46 /// 47 struct FastPriorityQueue { 48 SmallVector<SUnit *, 16> Queue; 49 50 bool empty() const { return Queue.empty(); } 51 52 void push(SUnit *U) { 53 Queue.push_back(U); 54 } 55 56 SUnit *pop() { 57 if (empty()) return NULL; 58 SUnit *V = Queue.back(); 59 Queue.pop_back(); 60 return V; 61 } 62 }; 63 64//===----------------------------------------------------------------------===// 65/// ScheduleDAGFast - The actual "fast" list scheduler implementation. 66/// 67class ScheduleDAGFast : public ScheduleDAGSDNodes { 68private: 69 /// AvailableQueue - The priority queue to use for the available SUnits. 70 FastPriorityQueue AvailableQueue; 71 72 /// LiveRegDefs - A set of physical registers and their definition 73 /// that are "live". These nodes must be scheduled before any other nodes that 74 /// modifies the registers can be scheduled. 75 unsigned NumLiveRegs; 76 std::vector<SUnit*> LiveRegDefs; 77 std::vector<unsigned> LiveRegCycles; 78 79public: 80 ScheduleDAGFast(MachineFunction &mf) 81 : ScheduleDAGSDNodes(mf) {} 82 83 void Schedule(); 84 85 /// AddPred - adds a predecessor edge to SUnit SU. 86 /// This returns true if this is a new predecessor. 87 void AddPred(SUnit *SU, const SDep &D) { 88 SU->addPred(D); 89 } 90 91 /// RemovePred - removes a predecessor edge from SUnit SU. 92 /// This returns true if an edge was removed. 93 void RemovePred(SUnit *SU, const SDep &D) { 94 SU->removePred(D); 95 } 96 97private: 98 void ReleasePred(SUnit *SU, SDep *PredEdge); 99 void ReleasePredecessors(SUnit *SU, unsigned CurCycle); 100 void ScheduleNodeBottomUp(SUnit*, unsigned); 101 SUnit *CopyAndMoveSuccessors(SUnit*); 102 void InsertCopiesAndMoveSuccs(SUnit*, unsigned, 103 const TargetRegisterClass*, 104 const TargetRegisterClass*, 105 SmallVector<SUnit*, 2>&); 106 bool DelayForLiveRegsBottomUp(SUnit*, SmallVector<unsigned, 4>&); 107 void ListScheduleBottomUp(); 108 109 /// forceUnitLatencies - The fast scheduler doesn't care about real latencies. 110 bool forceUnitLatencies() const { return true; } 111}; 112} // end anonymous namespace 113 114 115/// Schedule - Schedule the DAG using list scheduling. 116void ScheduleDAGFast::Schedule() { 117 DEBUG(dbgs() << "********** List Scheduling **********\n"); 118 119 NumLiveRegs = 0; 120 LiveRegDefs.resize(TRI->getNumRegs(), NULL); 121 LiveRegCycles.resize(TRI->getNumRegs(), 0); 122 123 // Build the scheduling graph. 124 BuildSchedGraph(NULL); 125 126 DEBUG(for (unsigned su = 0, e = SUnits.size(); su != e; ++su) 127 SUnits[su].dumpAll(this)); 128 129 // Execute the actual scheduling loop. 130 ListScheduleBottomUp(); 131} 132 133//===----------------------------------------------------------------------===// 134// Bottom-Up Scheduling 135//===----------------------------------------------------------------------===// 136 137/// ReleasePred - Decrement the NumSuccsLeft count of a predecessor. Add it to 138/// the AvailableQueue if the count reaches zero. Also update its cycle bound. 139void ScheduleDAGFast::ReleasePred(SUnit *SU, SDep *PredEdge) { 140 SUnit *PredSU = PredEdge->getSUnit(); 141 142#ifndef NDEBUG 143 if (PredSU->NumSuccsLeft == 0) { 144 dbgs() << "*** Scheduling failed! ***\n"; 145 PredSU->dump(this); 146 dbgs() << " has been released too many times!\n"; 147 llvm_unreachable(0); 148 } 149#endif 150 --PredSU->NumSuccsLeft; 151 152 // If all the node's successors are scheduled, this node is ready 153 // to be scheduled. Ignore the special EntrySU node. 154 if (PredSU->NumSuccsLeft == 0 && PredSU != &EntrySU) { 155 PredSU->isAvailable = true; 156 AvailableQueue.push(PredSU); 157 } 158} 159 160void ScheduleDAGFast::ReleasePredecessors(SUnit *SU, unsigned CurCycle) { 161 // Bottom up: release predecessors 162 for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); 163 I != E; ++I) { 164 ReleasePred(SU, &*I); 165 if (I->isAssignedRegDep()) { 166 // This is a physical register dependency and it's impossible or 167 // expensive to copy the register. Make sure nothing that can 168 // clobber the register is scheduled between the predecessor and 169 // this node. 170 if (!LiveRegDefs[I->getReg()]) { 171 ++NumLiveRegs; 172 LiveRegDefs[I->getReg()] = I->getSUnit(); 173 LiveRegCycles[I->getReg()] = CurCycle; 174 } 175 } 176 } 177} 178 179/// ScheduleNodeBottomUp - Add the node to the schedule. Decrement the pending 180/// count of its predecessors. If a predecessor pending count is zero, add it to 181/// the Available queue. 182void ScheduleDAGFast::ScheduleNodeBottomUp(SUnit *SU, unsigned CurCycle) { 183 DEBUG(dbgs() << "*** Scheduling [" << CurCycle << "]: "); 184 DEBUG(SU->dump(this)); 185 186 assert(CurCycle >= SU->getHeight() && "Node scheduled below its height!"); 187 SU->setHeightToAtLeast(CurCycle); 188 Sequence.push_back(SU); 189 190 ReleasePredecessors(SU, CurCycle); 191 192 // Release all the implicit physical register defs that are live. 193 for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); 194 I != E; ++I) { 195 if (I->isAssignedRegDep()) { 196 if (LiveRegCycles[I->getReg()] == I->getSUnit()->getHeight()) { 197 assert(NumLiveRegs > 0 && "NumLiveRegs is already zero!"); 198 assert(LiveRegDefs[I->getReg()] == SU && 199 "Physical register dependency violated?"); 200 --NumLiveRegs; 201 LiveRegDefs[I->getReg()] = NULL; 202 LiveRegCycles[I->getReg()] = 0; 203 } 204 } 205 } 206 207 SU->isScheduled = true; 208} 209 210/// CopyAndMoveSuccessors - Clone the specified node and move its scheduled 211/// successors to the newly created node. 212SUnit *ScheduleDAGFast::CopyAndMoveSuccessors(SUnit *SU) { 213 if (SU->getNode()->getGluedNode()) 214 return NULL; 215 216 SDNode *N = SU->getNode(); 217 if (!N) 218 return NULL; 219 220 SUnit *NewSU; 221 bool TryUnfold = false; 222 for (unsigned i = 0, e = N->getNumValues(); i != e; ++i) { 223 EVT VT = N->getValueType(i); 224 if (VT == MVT::Glue) 225 return NULL; 226 else if (VT == MVT::Other) 227 TryUnfold = true; 228 } 229 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) { 230 const SDValue &Op = N->getOperand(i); 231 EVT VT = Op.getNode()->getValueType(Op.getResNo()); 232 if (VT == MVT::Glue) 233 return NULL; 234 } 235 236 if (TryUnfold) { 237 SmallVector<SDNode*, 2> NewNodes; 238 if (!TII->unfoldMemoryOperand(*DAG, N, NewNodes)) 239 return NULL; 240 241 DEBUG(dbgs() << "Unfolding SU # " << SU->NodeNum << "\n"); 242 assert(NewNodes.size() == 2 && "Expected a load folding node!"); 243 244 N = NewNodes[1]; 245 SDNode *LoadNode = NewNodes[0]; 246 unsigned NumVals = N->getNumValues(); 247 unsigned OldNumVals = SU->getNode()->getNumValues(); 248 for (unsigned i = 0; i != NumVals; ++i) 249 DAG->ReplaceAllUsesOfValueWith(SDValue(SU->getNode(), i), SDValue(N, i)); 250 DAG->ReplaceAllUsesOfValueWith(SDValue(SU->getNode(), OldNumVals-1), 251 SDValue(LoadNode, 1)); 252 253 SUnit *NewSU = newSUnit(N); 254 assert(N->getNodeId() == -1 && "Node already inserted!"); 255 N->setNodeId(NewSU->NodeNum); 256 257 const MCInstrDesc &MCID = TII->get(N->getMachineOpcode()); 258 for (unsigned i = 0; i != MCID.getNumOperands(); ++i) { 259 if (MCID.getOperandConstraint(i, MCOI::TIED_TO) != -1) { 260 NewSU->isTwoAddress = true; 261 break; 262 } 263 } 264 if (MCID.isCommutable()) 265 NewSU->isCommutable = true; 266 267 // LoadNode may already exist. This can happen when there is another 268 // load from the same location and producing the same type of value 269 // but it has different alignment or volatileness. 270 bool isNewLoad = true; 271 SUnit *LoadSU; 272 if (LoadNode->getNodeId() != -1) { 273 LoadSU = &SUnits[LoadNode->getNodeId()]; 274 isNewLoad = false; 275 } else { 276 LoadSU = newSUnit(LoadNode); 277 LoadNode->setNodeId(LoadSU->NodeNum); 278 } 279 280 SDep ChainPred; 281 SmallVector<SDep, 4> ChainSuccs; 282 SmallVector<SDep, 4> LoadPreds; 283 SmallVector<SDep, 4> NodePreds; 284 SmallVector<SDep, 4> NodeSuccs; 285 for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); 286 I != E; ++I) { 287 if (I->isCtrl()) 288 ChainPred = *I; 289 else if (I->getSUnit()->getNode() && 290 I->getSUnit()->getNode()->isOperandOf(LoadNode)) 291 LoadPreds.push_back(*I); 292 else 293 NodePreds.push_back(*I); 294 } 295 for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); 296 I != E; ++I) { 297 if (I->isCtrl()) 298 ChainSuccs.push_back(*I); 299 else 300 NodeSuccs.push_back(*I); 301 } 302 303 if (ChainPred.getSUnit()) { 304 RemovePred(SU, ChainPred); 305 if (isNewLoad) 306 AddPred(LoadSU, ChainPred); 307 } 308 for (unsigned i = 0, e = LoadPreds.size(); i != e; ++i) { 309 const SDep &Pred = LoadPreds[i]; 310 RemovePred(SU, Pred); 311 if (isNewLoad) { 312 AddPred(LoadSU, Pred); 313 } 314 } 315 for (unsigned i = 0, e = NodePreds.size(); i != e; ++i) { 316 const SDep &Pred = NodePreds[i]; 317 RemovePred(SU, Pred); 318 AddPred(NewSU, Pred); 319 } 320 for (unsigned i = 0, e = NodeSuccs.size(); i != e; ++i) { 321 SDep D = NodeSuccs[i]; 322 SUnit *SuccDep = D.getSUnit(); 323 D.setSUnit(SU); 324 RemovePred(SuccDep, D); 325 D.setSUnit(NewSU); 326 AddPred(SuccDep, D); 327 } 328 for (unsigned i = 0, e = ChainSuccs.size(); i != e; ++i) { 329 SDep D = ChainSuccs[i]; 330 SUnit *SuccDep = D.getSUnit(); 331 D.setSUnit(SU); 332 RemovePred(SuccDep, D); 333 if (isNewLoad) { 334 D.setSUnit(LoadSU); 335 AddPred(SuccDep, D); 336 } 337 } 338 if (isNewLoad) { 339 AddPred(NewSU, SDep(LoadSU, SDep::Order, LoadSU->Latency)); 340 } 341 342 ++NumUnfolds; 343 344 if (NewSU->NumSuccsLeft == 0) { 345 NewSU->isAvailable = true; 346 return NewSU; 347 } 348 SU = NewSU; 349 } 350 351 DEBUG(dbgs() << "Duplicating SU # " << SU->NodeNum << "\n"); 352 NewSU = Clone(SU); 353 354 // New SUnit has the exact same predecessors. 355 for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); 356 I != E; ++I) 357 if (!I->isArtificial()) 358 AddPred(NewSU, *I); 359 360 // Only copy scheduled successors. Cut them from old node's successor 361 // list and move them over. 362 SmallVector<std::pair<SUnit *, SDep>, 4> DelDeps; 363 for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); 364 I != E; ++I) { 365 if (I->isArtificial()) 366 continue; 367 SUnit *SuccSU = I->getSUnit(); 368 if (SuccSU->isScheduled) { 369 SDep D = *I; 370 D.setSUnit(NewSU); 371 AddPred(SuccSU, D); 372 D.setSUnit(SU); 373 DelDeps.push_back(std::make_pair(SuccSU, D)); 374 } 375 } 376 for (unsigned i = 0, e = DelDeps.size(); i != e; ++i) 377 RemovePred(DelDeps[i].first, DelDeps[i].second); 378 379 ++NumDups; 380 return NewSU; 381} 382 383/// InsertCopiesAndMoveSuccs - Insert register copies and move all 384/// scheduled successors of the given SUnit to the last copy. 385void ScheduleDAGFast::InsertCopiesAndMoveSuccs(SUnit *SU, unsigned Reg, 386 const TargetRegisterClass *DestRC, 387 const TargetRegisterClass *SrcRC, 388 SmallVector<SUnit*, 2> &Copies) { 389 SUnit *CopyFromSU = newSUnit(static_cast<SDNode *>(NULL)); 390 CopyFromSU->CopySrcRC = SrcRC; 391 CopyFromSU->CopyDstRC = DestRC; 392 393 SUnit *CopyToSU = newSUnit(static_cast<SDNode *>(NULL)); 394 CopyToSU->CopySrcRC = DestRC; 395 CopyToSU->CopyDstRC = SrcRC; 396 397 // Only copy scheduled successors. Cut them from old node's successor 398 // list and move them over. 399 SmallVector<std::pair<SUnit *, SDep>, 4> DelDeps; 400 for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); 401 I != E; ++I) { 402 if (I->isArtificial()) 403 continue; 404 SUnit *SuccSU = I->getSUnit(); 405 if (SuccSU->isScheduled) { 406 SDep D = *I; 407 D.setSUnit(CopyToSU); 408 AddPred(SuccSU, D); 409 DelDeps.push_back(std::make_pair(SuccSU, *I)); 410 } 411 } 412 for (unsigned i = 0, e = DelDeps.size(); i != e; ++i) { 413 RemovePred(DelDeps[i].first, DelDeps[i].second); 414 } 415 416 AddPred(CopyFromSU, SDep(SU, SDep::Data, SU->Latency, Reg)); 417 AddPred(CopyToSU, SDep(CopyFromSU, SDep::Data, CopyFromSU->Latency, 0)); 418 419 Copies.push_back(CopyFromSU); 420 Copies.push_back(CopyToSU); 421 422 ++NumPRCopies; 423} 424 425/// getPhysicalRegisterVT - Returns the ValueType of the physical register 426/// definition of the specified node. 427/// FIXME: Move to SelectionDAG? 428static EVT getPhysicalRegisterVT(SDNode *N, unsigned Reg, 429 const TargetInstrInfo *TII) { 430 const MCInstrDesc &MCID = TII->get(N->getMachineOpcode()); 431 assert(MCID.ImplicitDefs && "Physical reg def must be in implicit def list!"); 432 unsigned NumRes = MCID.getNumDefs(); 433 for (const uint16_t *ImpDef = MCID.getImplicitDefs(); *ImpDef; ++ImpDef) { 434 if (Reg == *ImpDef) 435 break; 436 ++NumRes; 437 } 438 return N->getValueType(NumRes); 439} 440 441/// CheckForLiveRegDef - Return true and update live register vector if the 442/// specified register def of the specified SUnit clobbers any "live" registers. 443static bool CheckForLiveRegDef(SUnit *SU, unsigned Reg, 444 std::vector<SUnit*> &LiveRegDefs, 445 SmallSet<unsigned, 4> &RegAdded, 446 SmallVector<unsigned, 4> &LRegs, 447 const TargetRegisterInfo *TRI) { 448 bool Added = false; 449 for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI) { 450 if (LiveRegDefs[*AI] && LiveRegDefs[*AI] != SU) { 451 if (RegAdded.insert(*AI)) { 452 LRegs.push_back(*AI); 453 Added = true; 454 } 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 uint16_t *Reg = MCID.getImplicitDefs(); *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 VerifyScheduledSequence(/*isBottomUp=*/true); 634#endif 635} 636 637 638namespace { 639//===----------------------------------------------------------------------===// 640// ScheduleDAGLinearize - No scheduling scheduler, it simply linearize the 641// DAG in topological order. 642// IMPORTANT: this may not work for targets with phyreg dependency. 643// 644class ScheduleDAGLinearize : public ScheduleDAGSDNodes { 645public: 646 ScheduleDAGLinearize(MachineFunction &mf) : ScheduleDAGSDNodes(mf) {} 647 648 void Schedule(); 649 650 MachineBasicBlock *EmitSchedule(MachineBasicBlock::iterator &InsertPos); 651 652private: 653 std::vector<SDNode*> Sequence; 654 DenseMap<SDNode*, SDNode*> GluedMap; // Cache glue to its user 655 656 void ScheduleNode(SDNode *N); 657}; 658} // end anonymous namespace 659 660void ScheduleDAGLinearize::ScheduleNode(SDNode *N) { 661 if (N->getNodeId() != 0) 662 llvm_unreachable(0); 663 664 if (!N->isMachineOpcode() && 665 (N->getOpcode() == ISD::EntryToken || isPassiveNode(N))) 666 // These nodes do not need to be translated into MIs. 667 return; 668 669 DEBUG(dbgs() << "\n*** Scheduling: "); 670 DEBUG(N->dump(DAG)); 671 Sequence.push_back(N); 672 673 unsigned NumOps = N->getNumOperands(); 674 if (unsigned NumLeft = NumOps) { 675 SDNode *GluedOpN = 0; 676 do { 677 const SDValue &Op = N->getOperand(NumLeft-1); 678 SDNode *OpN = Op.getNode(); 679 680 if (NumLeft == NumOps && Op.getValueType() == MVT::Glue) { 681 // Schedule glue operand right above N. 682 GluedOpN = OpN; 683 assert(OpN->getNodeId() != 0 && "Glue operand not ready?"); 684 OpN->setNodeId(0); 685 ScheduleNode(OpN); 686 continue; 687 } 688 689 if (OpN == GluedOpN) 690 // Glue operand is already scheduled. 691 continue; 692 693 DenseMap<SDNode*, SDNode*>::iterator DI = GluedMap.find(OpN); 694 if (DI != GluedMap.end() && DI->second != N) 695 // Users of glues are counted against the glued users. 696 OpN = DI->second; 697 698 unsigned Degree = OpN->getNodeId(); 699 assert(Degree > 0 && "Predecessor over-released!"); 700 OpN->setNodeId(--Degree); 701 if (Degree == 0) 702 ScheduleNode(OpN); 703 } while (--NumLeft); 704 } 705} 706 707/// findGluedUser - Find the representative use of a glue value by walking 708/// the use chain. 709static SDNode *findGluedUser(SDNode *N) { 710 while (SDNode *Glued = N->getGluedUser()) 711 N = Glued; 712 return N; 713} 714 715void ScheduleDAGLinearize::Schedule() { 716 DEBUG(dbgs() << "********** DAG Linearization **********\n"); 717 718 SmallVector<SDNode*, 8> Glues; 719 unsigned DAGSize = 0; 720 for (SelectionDAG::allnodes_iterator I = DAG->allnodes_begin(), 721 E = DAG->allnodes_end(); I != E; ++I) { 722 SDNode *N = I; 723 724 // Use node id to record degree. 725 unsigned Degree = N->use_size(); 726 N->setNodeId(Degree); 727 unsigned NumVals = N->getNumValues(); 728 if (NumVals && N->getValueType(NumVals-1) == MVT::Glue && 729 N->hasAnyUseOfValue(NumVals-1)) { 730 SDNode *User = findGluedUser(N); 731 if (User) { 732 Glues.push_back(N); 733 GluedMap.insert(std::make_pair(N, User)); 734 } 735 } 736 737 if (N->isMachineOpcode() || 738 (N->getOpcode() != ISD::EntryToken && !isPassiveNode(N))) 739 ++DAGSize; 740 } 741 742 for (unsigned i = 0, e = Glues.size(); i != e; ++i) { 743 SDNode *Glue = Glues[i]; 744 SDNode *GUser = GluedMap[Glue]; 745 unsigned Degree = Glue->getNodeId(); 746 unsigned UDegree = GUser->getNodeId(); 747 748 // Glue user must be scheduled together with the glue operand. So other 749 // users of the glue operand must be treated as its users. 750 SDNode *ImmGUser = Glue->getGluedUser(); 751 for (SDNode::use_iterator ui = Glue->use_begin(), ue = Glue->use_end(); 752 ui != ue; ++ui) 753 if (*ui == ImmGUser) 754 --Degree; 755 GUser->setNodeId(UDegree + Degree); 756 Glue->setNodeId(1); 757 } 758 759 Sequence.reserve(DAGSize); 760 ScheduleNode(DAG->getRoot().getNode()); 761} 762 763MachineBasicBlock* 764ScheduleDAGLinearize::EmitSchedule(MachineBasicBlock::iterator &InsertPos) { 765 InstrEmitter Emitter(BB, InsertPos); 766 DenseMap<SDValue, unsigned> VRBaseMap; 767 768 DEBUG({ 769 dbgs() << "\n*** Final schedule ***\n"; 770 }); 771 772 // FIXME: Handle dbg_values. 773 unsigned NumNodes = Sequence.size(); 774 for (unsigned i = 0; i != NumNodes; ++i) { 775 SDNode *N = Sequence[NumNodes-i-1]; 776 DEBUG(N->dump(DAG)); 777 Emitter.EmitNode(N, false, false, VRBaseMap); 778 } 779 780 DEBUG(dbgs() << '\n'); 781 782 InsertPos = Emitter.getInsertPos(); 783 return Emitter.getBlock(); 784} 785 786//===----------------------------------------------------------------------===// 787// Public Constructor Functions 788//===----------------------------------------------------------------------===// 789 790llvm::ScheduleDAGSDNodes * 791llvm::createFastDAGScheduler(SelectionDAGISel *IS, CodeGenOpt::Level) { 792 return new ScheduleDAGFast(*IS->MF); 793} 794 795llvm::ScheduleDAGSDNodes * 796llvm::createDAGLinearizer(SelectionDAGISel *IS, CodeGenOpt::Level) { 797 return new ScheduleDAGLinearize(*IS->MF); 798} 799