1 //===----- ScheduleDAGFast.cpp - Fast poor list scheduler -----------------===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // This implements a fast scheduler. 10 // 11 //===----------------------------------------------------------------------===// 12 13 #include "InstrEmitter.h" 14 #include "SDNodeDbgValue.h" 15 #include "ScheduleDAGSDNodes.h" 16 #include "llvm/ADT/SmallSet.h" 17 #include "llvm/ADT/Statistic.h" 18 #include "llvm/CodeGen/SchedulerRegistry.h" 19 #include "llvm/CodeGen/SelectionDAGISel.h" 20 #include "llvm/CodeGen/TargetInstrInfo.h" 21 #include "llvm/CodeGen/TargetRegisterInfo.h" 22 #include "llvm/IR/InlineAsm.h" 23 #include "llvm/Support/Debug.h" 24 #include "llvm/Support/ErrorHandling.h" 25 #include "llvm/Support/raw_ostream.h" 26 using namespace llvm; 27 28 #define DEBUG_TYPE "pre-RA-sched" 29 30 STATISTIC(NumUnfolds, "Number of nodes unfolded"); 31 STATISTIC(NumDups, "Number of duplicated nodes"); 32 STATISTIC(NumPRCopies, "Number of physical copies"); 33 34 static RegisterScheduler 35 fastDAGScheduler("fast", "Fast suboptimal list scheduling", 36 createFastDAGScheduler); 37 static RegisterScheduler 38 linearizeDAGScheduler("linearize", "Linearize DAG, no scheduling", 39 createDAGLinearizer); 40 41 42 namespace { 43 /// FastPriorityQueue - A degenerate priority queue that considers 44 /// all nodes to have the same priority. 45 /// 46 struct FastPriorityQueue { 47 SmallVector<SUnit *, 16> Queue; 48 49 bool empty() const { return Queue.empty(); } 50 51 void push(SUnit *U) { 52 Queue.push_back(U); 53 } 54 55 SUnit *pop() { 56 if (empty()) return nullptr; 57 return Queue.pop_back_val(); 58 } 59 }; 60 61 //===----------------------------------------------------------------------===// 62 /// ScheduleDAGFast - The actual "fast" list scheduler implementation. 63 /// 64 class ScheduleDAGFast : public ScheduleDAGSDNodes { 65 private: 66 /// AvailableQueue - The priority queue to use for the available SUnits. 67 FastPriorityQueue AvailableQueue; 68 69 /// LiveRegDefs - A set of physical registers and their definition 70 /// that are "live". These nodes must be scheduled before any other nodes that 71 /// modifies the registers can be scheduled. 72 unsigned NumLiveRegs; 73 std::vector<SUnit*> LiveRegDefs; 74 std::vector<unsigned> LiveRegCycles; 75 76 public: 77 ScheduleDAGFast(MachineFunction &mf) 78 : ScheduleDAGSDNodes(mf) {} 79 80 void Schedule() override; 81 82 /// AddPred - adds a predecessor edge to SUnit SU. 83 /// This returns true if this is a new predecessor. 84 void AddPred(SUnit *SU, const SDep &D) { 85 SU->addPred(D); 86 } 87 88 /// RemovePred - removes a predecessor edge from SUnit SU. 89 /// This returns true if an edge was removed. 90 void RemovePred(SUnit *SU, const SDep &D) { 91 SU->removePred(D); 92 } 93 94 private: 95 void ReleasePred(SUnit *SU, SDep *PredEdge); 96 void ReleasePredecessors(SUnit *SU, unsigned CurCycle); 97 void ScheduleNodeBottomUp(SUnit*, unsigned); 98 SUnit *CopyAndMoveSuccessors(SUnit*); 99 void InsertCopiesAndMoveSuccs(SUnit*, unsigned, 100 const TargetRegisterClass*, 101 const TargetRegisterClass*, 102 SmallVectorImpl<SUnit*>&); 103 bool DelayForLiveRegsBottomUp(SUnit*, SmallVectorImpl<unsigned>&); 104 void ListScheduleBottomUp(); 105 106 /// forceUnitLatencies - The fast scheduler doesn't care about real latencies. 107 bool forceUnitLatencies() const override { return true; } 108 }; 109 } // end anonymous namespace 110 111 112 /// Schedule - Schedule the DAG using list scheduling. 113 void ScheduleDAGFast::Schedule() { 114 LLVM_DEBUG(dbgs() << "********** List Scheduling **********\n"); 115 116 NumLiveRegs = 0; 117 LiveRegDefs.resize(TRI->getNumRegs(), nullptr); 118 LiveRegCycles.resize(TRI->getNumRegs(), 0); 119 120 // Build the scheduling graph. 121 BuildSchedGraph(nullptr); 122 123 LLVM_DEBUG(dump()); 124 125 // Execute the actual scheduling loop. 126 ListScheduleBottomUp(); 127 } 128 129 //===----------------------------------------------------------------------===// 130 // Bottom-Up Scheduling 131 //===----------------------------------------------------------------------===// 132 133 /// ReleasePred - Decrement the NumSuccsLeft count of a predecessor. Add it to 134 /// the AvailableQueue if the count reaches zero. Also update its cycle bound. 135 void ScheduleDAGFast::ReleasePred(SUnit *SU, SDep *PredEdge) { 136 SUnit *PredSU = PredEdge->getSUnit(); 137 138 #ifndef NDEBUG 139 if (PredSU->NumSuccsLeft == 0) { 140 dbgs() << "*** Scheduling failed! ***\n"; 141 dumpNode(*PredSU); 142 dbgs() << " has been released too many times!\n"; 143 llvm_unreachable(nullptr); 144 } 145 #endif 146 --PredSU->NumSuccsLeft; 147 148 // If all the node's successors are scheduled, this node is ready 149 // to be scheduled. Ignore the special EntrySU node. 150 if (PredSU->NumSuccsLeft == 0 && PredSU != &EntrySU) { 151 PredSU->isAvailable = true; 152 AvailableQueue.push(PredSU); 153 } 154 } 155 156 void ScheduleDAGFast::ReleasePredecessors(SUnit *SU, unsigned CurCycle) { 157 // Bottom up: release predecessors 158 for (SDep &Pred : SU->Preds) { 159 ReleasePred(SU, &Pred); 160 if (Pred.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[Pred.getReg()]) { 166 ++NumLiveRegs; 167 LiveRegDefs[Pred.getReg()] = Pred.getSUnit(); 168 LiveRegCycles[Pred.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. 177 void ScheduleDAGFast::ScheduleNodeBottomUp(SUnit *SU, unsigned CurCycle) { 178 LLVM_DEBUG(dbgs() << "*** Scheduling [" << CurCycle << "]: "); 179 LLVM_DEBUG(dumpNode(*SU)); 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 (SDep &Succ : SU->Succs) { 189 if (Succ.isAssignedRegDep()) { 190 if (LiveRegCycles[Succ.getReg()] == Succ.getSUnit()->getHeight()) { 191 assert(NumLiveRegs > 0 && "NumLiveRegs is already zero!"); 192 assert(LiveRegDefs[Succ.getReg()] == SU && 193 "Physical register dependency violated?"); 194 --NumLiveRegs; 195 LiveRegDefs[Succ.getReg()] = nullptr; 196 LiveRegCycles[Succ.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. 206 SUnit *ScheduleDAGFast::CopyAndMoveSuccessors(SUnit *SU) { 207 if (SU->getNode()->getGluedNode()) 208 return nullptr; 209 210 SDNode *N = SU->getNode(); 211 if (!N) 212 return nullptr; 213 214 SUnit *NewSU; 215 bool TryUnfold = false; 216 for (unsigned i = 0, e = N->getNumValues(); i != e; ++i) { 217 MVT VT = N->getSimpleValueType(i); 218 if (VT == MVT::Glue) 219 return nullptr; 220 else if (VT == MVT::Other) 221 TryUnfold = true; 222 } 223 for (const SDValue &Op : N->op_values()) { 224 MVT VT = Op.getNode()->getSimpleValueType(Op.getResNo()); 225 if (VT == MVT::Glue) 226 return nullptr; 227 } 228 229 if (TryUnfold) { 230 SmallVector<SDNode*, 2> NewNodes; 231 if (!TII->unfoldMemoryOperand(*DAG, N, NewNodes)) 232 return nullptr; 233 234 LLVM_DEBUG(dbgs() << "Unfolding SU # " << SU->NodeNum << "\n"); 235 assert(NewNodes.size() == 2 && "Expected a load folding node!"); 236 237 N = NewNodes[1]; 238 SDNode *LoadNode = NewNodes[0]; 239 unsigned NumVals = N->getNumValues(); 240 unsigned OldNumVals = SU->getNode()->getNumValues(); 241 for (unsigned i = 0; i != NumVals; ++i) 242 DAG->ReplaceAllUsesOfValueWith(SDValue(SU->getNode(), i), SDValue(N, i)); 243 DAG->ReplaceAllUsesOfValueWith(SDValue(SU->getNode(), OldNumVals-1), 244 SDValue(LoadNode, 1)); 245 246 SUnit *NewSU = newSUnit(N); 247 assert(N->getNodeId() == -1 && "Node already inserted!"); 248 N->setNodeId(NewSU->NodeNum); 249 250 const MCInstrDesc &MCID = TII->get(N->getMachineOpcode()); 251 for (unsigned i = 0; i != MCID.getNumOperands(); ++i) { 252 if (MCID.getOperandConstraint(i, MCOI::TIED_TO) != -1) { 253 NewSU->isTwoAddress = true; 254 break; 255 } 256 } 257 if (MCID.isCommutable()) 258 NewSU->isCommutable = true; 259 260 // LoadNode may already exist. This can happen when there is another 261 // load from the same location and producing the same type of value 262 // but it has different alignment or volatileness. 263 bool isNewLoad = true; 264 SUnit *LoadSU; 265 if (LoadNode->getNodeId() != -1) { 266 LoadSU = &SUnits[LoadNode->getNodeId()]; 267 isNewLoad = false; 268 } else { 269 LoadSU = newSUnit(LoadNode); 270 LoadNode->setNodeId(LoadSU->NodeNum); 271 } 272 273 SDep ChainPred; 274 SmallVector<SDep, 4> ChainSuccs; 275 SmallVector<SDep, 4> LoadPreds; 276 SmallVector<SDep, 4> NodePreds; 277 SmallVector<SDep, 4> NodeSuccs; 278 for (SDep &Pred : SU->Preds) { 279 if (Pred.isCtrl()) 280 ChainPred = Pred; 281 else if (Pred.getSUnit()->getNode() && 282 Pred.getSUnit()->getNode()->isOperandOf(LoadNode)) 283 LoadPreds.push_back(Pred); 284 else 285 NodePreds.push_back(Pred); 286 } 287 for (SDep &Succ : SU->Succs) { 288 if (Succ.isCtrl()) 289 ChainSuccs.push_back(Succ); 290 else 291 NodeSuccs.push_back(Succ); 292 } 293 294 if (ChainPred.getSUnit()) { 295 RemovePred(SU, ChainPred); 296 if (isNewLoad) 297 AddPred(LoadSU, ChainPred); 298 } 299 for (unsigned i = 0, e = LoadPreds.size(); i != e; ++i) { 300 const SDep &Pred = LoadPreds[i]; 301 RemovePred(SU, Pred); 302 if (isNewLoad) { 303 AddPred(LoadSU, Pred); 304 } 305 } 306 for (unsigned i = 0, e = NodePreds.size(); i != e; ++i) { 307 const SDep &Pred = NodePreds[i]; 308 RemovePred(SU, Pred); 309 AddPred(NewSU, Pred); 310 } 311 for (unsigned i = 0, e = NodeSuccs.size(); i != e; ++i) { 312 SDep D = NodeSuccs[i]; 313 SUnit *SuccDep = D.getSUnit(); 314 D.setSUnit(SU); 315 RemovePred(SuccDep, D); 316 D.setSUnit(NewSU); 317 AddPred(SuccDep, D); 318 } 319 for (unsigned i = 0, e = ChainSuccs.size(); i != e; ++i) { 320 SDep D = ChainSuccs[i]; 321 SUnit *SuccDep = D.getSUnit(); 322 D.setSUnit(SU); 323 RemovePred(SuccDep, D); 324 if (isNewLoad) { 325 D.setSUnit(LoadSU); 326 AddPred(SuccDep, D); 327 } 328 } 329 if (isNewLoad) { 330 SDep D(LoadSU, SDep::Barrier); 331 D.setLatency(LoadSU->Latency); 332 AddPred(NewSU, D); 333 } 334 335 ++NumUnfolds; 336 337 if (NewSU->NumSuccsLeft == 0) { 338 NewSU->isAvailable = true; 339 return NewSU; 340 } 341 SU = NewSU; 342 } 343 344 LLVM_DEBUG(dbgs() << "Duplicating SU # " << SU->NodeNum << "\n"); 345 NewSU = Clone(SU); 346 347 // New SUnit has the exact same predecessors. 348 for (SDep &Pred : SU->Preds) 349 if (!Pred.isArtificial()) 350 AddPred(NewSU, Pred); 351 352 // Only copy scheduled successors. Cut them from old node's successor 353 // list and move them over. 354 SmallVector<std::pair<SUnit *, SDep>, 4> DelDeps; 355 for (SDep &Succ : SU->Succs) { 356 if (Succ.isArtificial()) 357 continue; 358 SUnit *SuccSU = Succ.getSUnit(); 359 if (SuccSU->isScheduled) { 360 SDep D = Succ; 361 D.setSUnit(NewSU); 362 AddPred(SuccSU, D); 363 D.setSUnit(SU); 364 DelDeps.push_back(std::make_pair(SuccSU, D)); 365 } 366 } 367 for (unsigned i = 0, e = DelDeps.size(); i != e; ++i) 368 RemovePred(DelDeps[i].first, DelDeps[i].second); 369 370 ++NumDups; 371 return NewSU; 372 } 373 374 /// InsertCopiesAndMoveSuccs - Insert register copies and move all 375 /// scheduled successors of the given SUnit to the last copy. 376 void ScheduleDAGFast::InsertCopiesAndMoveSuccs(SUnit *SU, unsigned Reg, 377 const TargetRegisterClass *DestRC, 378 const TargetRegisterClass *SrcRC, 379 SmallVectorImpl<SUnit*> &Copies) { 380 SUnit *CopyFromSU = newSUnit(static_cast<SDNode *>(nullptr)); 381 CopyFromSU->CopySrcRC = SrcRC; 382 CopyFromSU->CopyDstRC = DestRC; 383 384 SUnit *CopyToSU = newSUnit(static_cast<SDNode *>(nullptr)); 385 CopyToSU->CopySrcRC = DestRC; 386 CopyToSU->CopyDstRC = SrcRC; 387 388 // Only copy scheduled successors. Cut them from old node's successor 389 // list and move them over. 390 SmallVector<std::pair<SUnit *, SDep>, 4> DelDeps; 391 for (SDep &Succ : SU->Succs) { 392 if (Succ.isArtificial()) 393 continue; 394 SUnit *SuccSU = Succ.getSUnit(); 395 if (SuccSU->isScheduled) { 396 SDep D = Succ; 397 D.setSUnit(CopyToSU); 398 AddPred(SuccSU, D); 399 DelDeps.push_back(std::make_pair(SuccSU, Succ)); 400 } 401 } 402 for (unsigned i = 0, e = DelDeps.size(); i != e; ++i) { 403 RemovePred(DelDeps[i].first, DelDeps[i].second); 404 } 405 SDep FromDep(SU, SDep::Data, Reg); 406 FromDep.setLatency(SU->Latency); 407 AddPred(CopyFromSU, FromDep); 408 SDep ToDep(CopyFromSU, SDep::Data, 0); 409 ToDep.setLatency(CopyFromSU->Latency); 410 AddPred(CopyToSU, ToDep); 411 412 Copies.push_back(CopyFromSU); 413 Copies.push_back(CopyToSU); 414 415 ++NumPRCopies; 416 } 417 418 /// getPhysicalRegisterVT - Returns the ValueType of the physical register 419 /// definition of the specified node. 420 /// FIXME: Move to SelectionDAG? 421 static MVT getPhysicalRegisterVT(SDNode *N, unsigned Reg, 422 const TargetInstrInfo *TII) { 423 unsigned NumRes; 424 if (N->getOpcode() == ISD::CopyFromReg) { 425 // CopyFromReg has: "chain, Val, glue" so operand 1 gives the type. 426 NumRes = 1; 427 } else { 428 const MCInstrDesc &MCID = TII->get(N->getMachineOpcode()); 429 assert(MCID.ImplicitDefs && "Physical reg def must be in implicit def list!"); 430 NumRes = MCID.getNumDefs(); 431 for (const MCPhysReg *ImpDef = MCID.getImplicitDefs(); *ImpDef; ++ImpDef) { 432 if (Reg == *ImpDef) 433 break; 434 ++NumRes; 435 } 436 } 437 return N->getSimpleValueType(NumRes); 438 } 439 440 /// CheckForLiveRegDef - Return true and update live register vector if the 441 /// specified register def of the specified SUnit clobbers any "live" registers. 442 static bool CheckForLiveRegDef(SUnit *SU, unsigned Reg, 443 std::vector<SUnit *> &LiveRegDefs, 444 SmallSet<unsigned, 4> &RegAdded, 445 SmallVectorImpl<unsigned> &LRegs, 446 const TargetRegisterInfo *TRI, 447 const SDNode *Node = nullptr) { 448 bool Added = false; 449 for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI) { 450 // Check if Ref is live. 451 if (!LiveRegDefs[*AI]) 452 continue; 453 454 // Allow multiple uses of the same def. 455 if (LiveRegDefs[*AI] == SU) 456 continue; 457 458 // Allow multiple uses of same def 459 if (Node && LiveRegDefs[*AI]->getNode() == Node) 460 continue; 461 462 // Add Reg to the set of interfering live regs. 463 if (RegAdded.insert(*AI).second) { 464 LRegs.push_back(*AI); 465 Added = true; 466 } 467 } 468 return Added; 469 } 470 471 /// DelayForLiveRegsBottomUp - Returns true if it is necessary to delay 472 /// scheduling of the given node to satisfy live physical register dependencies. 473 /// If the specific node is the last one that's available to schedule, do 474 /// whatever is necessary (i.e. backtracking or cloning) to make it possible. 475 bool ScheduleDAGFast::DelayForLiveRegsBottomUp(SUnit *SU, 476 SmallVectorImpl<unsigned> &LRegs){ 477 if (NumLiveRegs == 0) 478 return false; 479 480 SmallSet<unsigned, 4> RegAdded; 481 // If this node would clobber any "live" register, then it's not ready. 482 for (SDep &Pred : SU->Preds) { 483 if (Pred.isAssignedRegDep()) { 484 CheckForLiveRegDef(Pred.getSUnit(), Pred.getReg(), LiveRegDefs, 485 RegAdded, LRegs, TRI); 486 } 487 } 488 489 for (SDNode *Node = SU->getNode(); Node; Node = Node->getGluedNode()) { 490 if (Node->getOpcode() == ISD::INLINEASM || 491 Node->getOpcode() == ISD::INLINEASM_BR) { 492 // Inline asm can clobber physical defs. 493 unsigned NumOps = Node->getNumOperands(); 494 if (Node->getOperand(NumOps-1).getValueType() == MVT::Glue) 495 --NumOps; // Ignore the glue operand. 496 497 for (unsigned i = InlineAsm::Op_FirstOperand; i != NumOps;) { 498 unsigned Flags = 499 cast<ConstantSDNode>(Node->getOperand(i))->getZExtValue(); 500 unsigned NumVals = InlineAsm::getNumOperandRegisters(Flags); 501 502 ++i; // Skip the ID value. 503 if (InlineAsm::isRegDefKind(Flags) || 504 InlineAsm::isRegDefEarlyClobberKind(Flags) || 505 InlineAsm::isClobberKind(Flags)) { 506 // Check for def of register or earlyclobber register. 507 for (; NumVals; --NumVals, ++i) { 508 unsigned Reg = cast<RegisterSDNode>(Node->getOperand(i))->getReg(); 509 if (Register::isPhysicalRegister(Reg)) 510 CheckForLiveRegDef(SU, Reg, LiveRegDefs, RegAdded, LRegs, TRI); 511 } 512 } else 513 i += NumVals; 514 } 515 continue; 516 } 517 518 if (Node->getOpcode() == ISD::CopyToReg) { 519 Register Reg = cast<RegisterSDNode>(Node->getOperand(1))->getReg(); 520 if (Reg.isPhysical()) { 521 SDNode *SrcNode = Node->getOperand(2).getNode(); 522 CheckForLiveRegDef(SU, Reg, LiveRegDefs, RegAdded, LRegs, TRI, SrcNode); 523 } 524 } 525 526 if (!Node->isMachineOpcode()) 527 continue; 528 const MCInstrDesc &MCID = TII->get(Node->getMachineOpcode()); 529 if (!MCID.ImplicitDefs) 530 continue; 531 for (const MCPhysReg *Reg = MCID.getImplicitDefs(); *Reg; ++Reg) { 532 CheckForLiveRegDef(SU, *Reg, LiveRegDefs, RegAdded, LRegs, TRI); 533 } 534 } 535 return !LRegs.empty(); 536 } 537 538 539 /// ListScheduleBottomUp - The main loop of list scheduling for bottom-up 540 /// schedulers. 541 void ScheduleDAGFast::ListScheduleBottomUp() { 542 unsigned CurCycle = 0; 543 544 // Release any predecessors of the special Exit node. 545 ReleasePredecessors(&ExitSU, CurCycle); 546 547 // Add root to Available queue. 548 if (!SUnits.empty()) { 549 SUnit *RootSU = &SUnits[DAG->getRoot().getNode()->getNodeId()]; 550 assert(RootSU->Succs.empty() && "Graph root shouldn't have successors!"); 551 RootSU->isAvailable = true; 552 AvailableQueue.push(RootSU); 553 } 554 555 // While Available queue is not empty, grab the node with the highest 556 // priority. If it is not ready put it back. Schedule the node. 557 SmallVector<SUnit*, 4> NotReady; 558 DenseMap<SUnit*, SmallVector<unsigned, 4> > LRegsMap; 559 Sequence.reserve(SUnits.size()); 560 while (!AvailableQueue.empty()) { 561 bool Delayed = false; 562 LRegsMap.clear(); 563 SUnit *CurSU = AvailableQueue.pop(); 564 while (CurSU) { 565 SmallVector<unsigned, 4> LRegs; 566 if (!DelayForLiveRegsBottomUp(CurSU, LRegs)) 567 break; 568 Delayed = true; 569 LRegsMap.insert(std::make_pair(CurSU, LRegs)); 570 571 CurSU->isPending = true; // This SU is not in AvailableQueue right now. 572 NotReady.push_back(CurSU); 573 CurSU = AvailableQueue.pop(); 574 } 575 576 // All candidates are delayed due to live physical reg dependencies. 577 // Try code duplication or inserting cross class copies 578 // to resolve it. 579 if (Delayed && !CurSU) { 580 if (!CurSU) { 581 // Try duplicating the nodes that produces these 582 // "expensive to copy" values to break the dependency. In case even 583 // that doesn't work, insert cross class copies. 584 SUnit *TrySU = NotReady[0]; 585 SmallVectorImpl<unsigned> &LRegs = LRegsMap[TrySU]; 586 assert(LRegs.size() == 1 && "Can't handle this yet!"); 587 unsigned Reg = LRegs[0]; 588 SUnit *LRDef = LiveRegDefs[Reg]; 589 MVT VT = getPhysicalRegisterVT(LRDef->getNode(), Reg, TII); 590 const TargetRegisterClass *RC = 591 TRI->getMinimalPhysRegClass(Reg, VT); 592 const TargetRegisterClass *DestRC = TRI->getCrossCopyRegClass(RC); 593 594 // If cross copy register class is the same as RC, then it must be 595 // possible copy the value directly. Do not try duplicate the def. 596 // If cross copy register class is not the same as RC, then it's 597 // possible to copy the value but it require cross register class copies 598 // and it is expensive. 599 // If cross copy register class is null, then it's not possible to copy 600 // the value at all. 601 SUnit *NewDef = nullptr; 602 if (DestRC != RC) { 603 NewDef = CopyAndMoveSuccessors(LRDef); 604 if (!DestRC && !NewDef) 605 report_fatal_error("Can't handle live physical " 606 "register dependency!"); 607 } 608 if (!NewDef) { 609 // Issue copies, these can be expensive cross register class copies. 610 SmallVector<SUnit*, 2> Copies; 611 InsertCopiesAndMoveSuccs(LRDef, Reg, DestRC, RC, Copies); 612 LLVM_DEBUG(dbgs() << "Adding an edge from SU # " << TrySU->NodeNum 613 << " to SU #" << Copies.front()->NodeNum << "\n"); 614 AddPred(TrySU, SDep(Copies.front(), SDep::Artificial)); 615 NewDef = Copies.back(); 616 } 617 618 LLVM_DEBUG(dbgs() << "Adding an edge from SU # " << NewDef->NodeNum 619 << " to SU #" << TrySU->NodeNum << "\n"); 620 LiveRegDefs[Reg] = NewDef; 621 AddPred(NewDef, SDep(TrySU, SDep::Artificial)); 622 TrySU->isAvailable = false; 623 CurSU = NewDef; 624 } 625 626 if (!CurSU) { 627 llvm_unreachable("Unable to resolve live physical register dependencies!"); 628 } 629 } 630 631 // Add the nodes that aren't ready back onto the available list. 632 for (unsigned i = 0, e = NotReady.size(); i != e; ++i) { 633 NotReady[i]->isPending = false; 634 // May no longer be available due to backtracking. 635 if (NotReady[i]->isAvailable) 636 AvailableQueue.push(NotReady[i]); 637 } 638 NotReady.clear(); 639 640 if (CurSU) 641 ScheduleNodeBottomUp(CurSU, CurCycle); 642 ++CurCycle; 643 } 644 645 // Reverse the order since it is bottom up. 646 std::reverse(Sequence.begin(), Sequence.end()); 647 648 #ifndef NDEBUG 649 VerifyScheduledSequence(/*isBottomUp=*/true); 650 #endif 651 } 652 653 654 namespace { 655 //===----------------------------------------------------------------------===// 656 // ScheduleDAGLinearize - No scheduling scheduler, it simply linearize the 657 // DAG in topological order. 658 // IMPORTANT: this may not work for targets with phyreg dependency. 659 // 660 class ScheduleDAGLinearize : public ScheduleDAGSDNodes { 661 public: 662 ScheduleDAGLinearize(MachineFunction &mf) : ScheduleDAGSDNodes(mf) {} 663 664 void Schedule() override; 665 666 MachineBasicBlock * 667 EmitSchedule(MachineBasicBlock::iterator &InsertPos) override; 668 669 private: 670 std::vector<SDNode*> Sequence; 671 DenseMap<SDNode*, SDNode*> GluedMap; // Cache glue to its user 672 673 void ScheduleNode(SDNode *N); 674 }; 675 } // end anonymous namespace 676 677 void ScheduleDAGLinearize::ScheduleNode(SDNode *N) { 678 if (N->getNodeId() != 0) 679 llvm_unreachable(nullptr); 680 681 if (!N->isMachineOpcode() && 682 (N->getOpcode() == ISD::EntryToken || isPassiveNode(N))) 683 // These nodes do not need to be translated into MIs. 684 return; 685 686 LLVM_DEBUG(dbgs() << "\n*** Scheduling: "); 687 LLVM_DEBUG(N->dump(DAG)); 688 Sequence.push_back(N); 689 690 unsigned NumOps = N->getNumOperands(); 691 if (unsigned NumLeft = NumOps) { 692 SDNode *GluedOpN = nullptr; 693 do { 694 const SDValue &Op = N->getOperand(NumLeft-1); 695 SDNode *OpN = Op.getNode(); 696 697 if (NumLeft == NumOps && Op.getValueType() == MVT::Glue) { 698 // Schedule glue operand right above N. 699 GluedOpN = OpN; 700 assert(OpN->getNodeId() != 0 && "Glue operand not ready?"); 701 OpN->setNodeId(0); 702 ScheduleNode(OpN); 703 continue; 704 } 705 706 if (OpN == GluedOpN) 707 // Glue operand is already scheduled. 708 continue; 709 710 DenseMap<SDNode*, SDNode*>::iterator DI = GluedMap.find(OpN); 711 if (DI != GluedMap.end() && DI->second != N) 712 // Users of glues are counted against the glued users. 713 OpN = DI->second; 714 715 unsigned Degree = OpN->getNodeId(); 716 assert(Degree > 0 && "Predecessor over-released!"); 717 OpN->setNodeId(--Degree); 718 if (Degree == 0) 719 ScheduleNode(OpN); 720 } while (--NumLeft); 721 } 722 } 723 724 /// findGluedUser - Find the representative use of a glue value by walking 725 /// the use chain. 726 static SDNode *findGluedUser(SDNode *N) { 727 while (SDNode *Glued = N->getGluedUser()) 728 N = Glued; 729 return N; 730 } 731 732 void ScheduleDAGLinearize::Schedule() { 733 LLVM_DEBUG(dbgs() << "********** DAG Linearization **********\n"); 734 735 SmallVector<SDNode*, 8> Glues; 736 unsigned DAGSize = 0; 737 for (SDNode &Node : DAG->allnodes()) { 738 SDNode *N = &Node; 739 740 // Use node id to record degree. 741 unsigned Degree = N->use_size(); 742 N->setNodeId(Degree); 743 unsigned NumVals = N->getNumValues(); 744 if (NumVals && N->getValueType(NumVals-1) == MVT::Glue && 745 N->hasAnyUseOfValue(NumVals-1)) { 746 SDNode *User = findGluedUser(N); 747 if (User) { 748 Glues.push_back(N); 749 GluedMap.insert(std::make_pair(N, User)); 750 } 751 } 752 753 if (N->isMachineOpcode() || 754 (N->getOpcode() != ISD::EntryToken && !isPassiveNode(N))) 755 ++DAGSize; 756 } 757 758 for (unsigned i = 0, e = Glues.size(); i != e; ++i) { 759 SDNode *Glue = Glues[i]; 760 SDNode *GUser = GluedMap[Glue]; 761 unsigned Degree = Glue->getNodeId(); 762 unsigned UDegree = GUser->getNodeId(); 763 764 // Glue user must be scheduled together with the glue operand. So other 765 // users of the glue operand must be treated as its users. 766 SDNode *ImmGUser = Glue->getGluedUser(); 767 for (const SDNode *U : Glue->uses()) 768 if (U == ImmGUser) 769 --Degree; 770 GUser->setNodeId(UDegree + Degree); 771 Glue->setNodeId(1); 772 } 773 774 Sequence.reserve(DAGSize); 775 ScheduleNode(DAG->getRoot().getNode()); 776 } 777 778 MachineBasicBlock* 779 ScheduleDAGLinearize::EmitSchedule(MachineBasicBlock::iterator &InsertPos) { 780 InstrEmitter Emitter(DAG->getTarget(), BB, InsertPos, 781 DAG->getUseInstrRefDebugInfo()); 782 DenseMap<SDValue, Register> VRBaseMap; 783 784 LLVM_DEBUG({ dbgs() << "\n*** Final schedule ***\n"; }); 785 786 unsigned NumNodes = Sequence.size(); 787 MachineBasicBlock *BB = Emitter.getBlock(); 788 for (unsigned i = 0; i != NumNodes; ++i) { 789 SDNode *N = Sequence[NumNodes-i-1]; 790 LLVM_DEBUG(N->dump(DAG)); 791 Emitter.EmitNode(N, false, false, VRBaseMap); 792 793 // Emit any debug values associated with the node. 794 if (N->getHasDebugValue()) { 795 MachineBasicBlock::iterator InsertPos = Emitter.getInsertPos(); 796 for (auto *DV : DAG->GetDbgValues(N)) { 797 if (!DV->isEmitted()) 798 if (auto *DbgMI = Emitter.EmitDbgValue(DV, VRBaseMap)) 799 BB->insert(InsertPos, DbgMI); 800 } 801 } 802 } 803 804 LLVM_DEBUG(dbgs() << '\n'); 805 806 InsertPos = Emitter.getInsertPos(); 807 return Emitter.getBlock(); 808 } 809 810 //===----------------------------------------------------------------------===// 811 // Public Constructor Functions 812 //===----------------------------------------------------------------------===// 813 814 llvm::ScheduleDAGSDNodes * 815 llvm::createFastDAGScheduler(SelectionDAGISel *IS, CodeGenOpt::Level) { 816 return new ScheduleDAGFast(*IS->MF); 817 } 818 819 llvm::ScheduleDAGSDNodes * 820 llvm::createDAGLinearizer(SelectionDAGISel *IS, CodeGenOpt::Level) { 821 return new ScheduleDAGLinearize(*IS->MF); 822 } 823