1 //===----- SchedulePostRAList.cpp - 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 top-down list scheduler, using standard algorithms. 11 // The basic approach uses a priority queue of available nodes to schedule. 12 // One at a time, nodes are taken from the priority queue (thus in priority 13 // order), checked for legality to schedule, and emitted if legal. 14 // 15 // Nodes may not be legal to schedule either due to structural hazards (e.g. 16 // pipeline or resource constraints) or because an input to the instruction has 17 // not completed execution. 18 // 19 //===----------------------------------------------------------------------===// 20 21 #include "llvm/CodeGen/Passes.h" 22 #include "AggressiveAntiDepBreaker.h" 23 #include "AntiDepBreaker.h" 24 #include "CriticalAntiDepBreaker.h" 25 #include "llvm/ADT/BitVector.h" 26 #include "llvm/ADT/Statistic.h" 27 #include "llvm/Analysis/AliasAnalysis.h" 28 #include "llvm/CodeGen/LatencyPriorityQueue.h" 29 #include "llvm/CodeGen/MachineDominators.h" 30 #include "llvm/CodeGen/MachineFrameInfo.h" 31 #include "llvm/CodeGen/MachineFunctionPass.h" 32 #include "llvm/CodeGen/MachineLoopInfo.h" 33 #include "llvm/CodeGen/MachineRegisterInfo.h" 34 #include "llvm/CodeGen/RegisterClassInfo.h" 35 #include "llvm/CodeGen/ScheduleDAGInstrs.h" 36 #include "llvm/CodeGen/ScheduleHazardRecognizer.h" 37 #include "llvm/CodeGen/SchedulerRegistry.h" 38 #include "llvm/Support/CommandLine.h" 39 #include "llvm/Support/Debug.h" 40 #include "llvm/Support/ErrorHandling.h" 41 #include "llvm/Support/raw_ostream.h" 42 #include "llvm/Target/TargetInstrInfo.h" 43 #include "llvm/Target/TargetLowering.h" 44 #include "llvm/Target/TargetMachine.h" 45 #include "llvm/Target/TargetRegisterInfo.h" 46 #include "llvm/Target/TargetSubtargetInfo.h" 47 using namespace llvm; 48 49 #define DEBUG_TYPE "post-RA-sched" 50 51 STATISTIC(NumNoops, "Number of noops inserted"); 52 STATISTIC(NumStalls, "Number of pipeline stalls"); 53 STATISTIC(NumFixedAnti, "Number of fixed anti-dependencies"); 54 55 // Post-RA scheduling is enabled with 56 // TargetSubtargetInfo.enablePostRAScheduler(). This flag can be used to 57 // override the target. 58 static cl::opt<bool> 59 EnablePostRAScheduler("post-RA-scheduler", 60 cl::desc("Enable scheduling after register allocation"), 61 cl::init(false), cl::Hidden); 62 static cl::opt<std::string> 63 EnableAntiDepBreaking("break-anti-dependencies", 64 cl::desc("Break post-RA scheduling anti-dependencies: " 65 "\"critical\", \"all\", or \"none\""), 66 cl::init("none"), cl::Hidden); 67 68 // If DebugDiv > 0 then only schedule MBB with (ID % DebugDiv) == DebugMod 69 static cl::opt<int> 70 DebugDiv("postra-sched-debugdiv", 71 cl::desc("Debug control MBBs that are scheduled"), 72 cl::init(0), cl::Hidden); 73 static cl::opt<int> 74 DebugMod("postra-sched-debugmod", 75 cl::desc("Debug control MBBs that are scheduled"), 76 cl::init(0), cl::Hidden); 77 78 AntiDepBreaker::~AntiDepBreaker() { } 79 80 namespace { 81 class PostRAScheduler : public MachineFunctionPass { 82 const TargetInstrInfo *TII; 83 RegisterClassInfo RegClassInfo; 84 85 public: 86 static char ID; 87 PostRAScheduler() : MachineFunctionPass(ID) {} 88 89 void getAnalysisUsage(AnalysisUsage &AU) const override { 90 AU.setPreservesCFG(); 91 AU.addRequired<AliasAnalysis>(); 92 AU.addRequired<TargetPassConfig>(); 93 AU.addRequired<MachineDominatorTree>(); 94 AU.addPreserved<MachineDominatorTree>(); 95 AU.addRequired<MachineLoopInfo>(); 96 AU.addPreserved<MachineLoopInfo>(); 97 MachineFunctionPass::getAnalysisUsage(AU); 98 } 99 100 bool runOnMachineFunction(MachineFunction &Fn) override; 101 }; 102 char PostRAScheduler::ID = 0; 103 104 class SchedulePostRATDList : public ScheduleDAGInstrs { 105 /// AvailableQueue - The priority queue to use for the available SUnits. 106 /// 107 LatencyPriorityQueue AvailableQueue; 108 109 /// PendingQueue - This contains all of the instructions whose operands have 110 /// been issued, but their results are not ready yet (due to the latency of 111 /// the operation). Once the operands becomes available, the instruction is 112 /// added to the AvailableQueue. 113 std::vector<SUnit*> PendingQueue; 114 115 /// HazardRec - The hazard recognizer to use. 116 ScheduleHazardRecognizer *HazardRec; 117 118 /// AntiDepBreak - Anti-dependence breaking object, or NULL if none 119 AntiDepBreaker *AntiDepBreak; 120 121 /// AA - AliasAnalysis for making memory reference queries. 122 AliasAnalysis *AA; 123 124 /// The schedule. Null SUnit*'s represent noop instructions. 125 std::vector<SUnit*> Sequence; 126 127 /// The index in BB of RegionEnd. 128 /// 129 /// This is the instruction number from the top of the current block, not 130 /// the SlotIndex. It is only used by the AntiDepBreaker. 131 unsigned EndIndex; 132 133 public: 134 SchedulePostRATDList( 135 MachineFunction &MF, MachineLoopInfo &MLI, MachineDominatorTree &MDT, 136 AliasAnalysis *AA, const RegisterClassInfo&, 137 TargetSubtargetInfo::AntiDepBreakMode AntiDepMode, 138 SmallVectorImpl<const TargetRegisterClass*> &CriticalPathRCs); 139 140 ~SchedulePostRATDList(); 141 142 /// startBlock - Initialize register live-range state for scheduling in 143 /// this block. 144 /// 145 void startBlock(MachineBasicBlock *BB) override; 146 147 // Set the index of RegionEnd within the current BB. 148 void setEndIndex(unsigned EndIdx) { EndIndex = EndIdx; } 149 150 /// Initialize the scheduler state for the next scheduling region. 151 void enterRegion(MachineBasicBlock *bb, 152 MachineBasicBlock::iterator begin, 153 MachineBasicBlock::iterator end, 154 unsigned regioninstrs) override; 155 156 /// Notify that the scheduler has finished scheduling the current region. 157 void exitRegion() override; 158 159 /// Schedule - Schedule the instruction range using list scheduling. 160 /// 161 void schedule() override; 162 163 void EmitSchedule(); 164 165 /// Observe - Update liveness information to account for the current 166 /// instruction, which will not be scheduled. 167 /// 168 void Observe(MachineInstr *MI, unsigned Count); 169 170 /// finishBlock - Clean up register live-range state. 171 /// 172 void finishBlock() override; 173 174 private: 175 void ReleaseSucc(SUnit *SU, SDep *SuccEdge); 176 void ReleaseSuccessors(SUnit *SU); 177 void ScheduleNodeTopDown(SUnit *SU, unsigned CurCycle); 178 void ListScheduleTopDown(); 179 180 void dumpSchedule() const; 181 void emitNoop(unsigned CurCycle); 182 }; 183 } 184 185 char &llvm::PostRASchedulerID = PostRAScheduler::ID; 186 187 INITIALIZE_PASS(PostRAScheduler, "post-RA-sched", 188 "Post RA top-down list latency scheduler", false, false) 189 190 SchedulePostRATDList::SchedulePostRATDList( 191 MachineFunction &MF, MachineLoopInfo &MLI, MachineDominatorTree &MDT, 192 AliasAnalysis *AA, const RegisterClassInfo &RCI, 193 TargetSubtargetInfo::AntiDepBreakMode AntiDepMode, 194 SmallVectorImpl<const TargetRegisterClass*> &CriticalPathRCs) 195 : ScheduleDAGInstrs(MF, MLI, MDT, /*IsPostRA=*/true), AA(AA), EndIndex(0) { 196 197 const TargetMachine &TM = MF.getTarget(); 198 const InstrItineraryData *InstrItins = TM.getInstrItineraryData(); 199 HazardRec = 200 TM.getInstrInfo()->CreateTargetPostRAHazardRecognizer(InstrItins, this); 201 202 assert((AntiDepMode == TargetSubtargetInfo::ANTIDEP_NONE || 203 MRI.tracksLiveness()) && 204 "Live-ins must be accurate for anti-dependency breaking"); 205 AntiDepBreak = 206 ((AntiDepMode == TargetSubtargetInfo::ANTIDEP_ALL) ? 207 (AntiDepBreaker *)new AggressiveAntiDepBreaker(MF, RCI, CriticalPathRCs) : 208 ((AntiDepMode == TargetSubtargetInfo::ANTIDEP_CRITICAL) ? 209 (AntiDepBreaker *)new CriticalAntiDepBreaker(MF, RCI) : nullptr)); 210 } 211 212 SchedulePostRATDList::~SchedulePostRATDList() { 213 delete HazardRec; 214 delete AntiDepBreak; 215 } 216 217 /// Initialize state associated with the next scheduling region. 218 void SchedulePostRATDList::enterRegion(MachineBasicBlock *bb, 219 MachineBasicBlock::iterator begin, 220 MachineBasicBlock::iterator end, 221 unsigned regioninstrs) { 222 ScheduleDAGInstrs::enterRegion(bb, begin, end, regioninstrs); 223 Sequence.clear(); 224 } 225 226 /// Print the schedule before exiting the region. 227 void SchedulePostRATDList::exitRegion() { 228 DEBUG({ 229 dbgs() << "*** Final schedule ***\n"; 230 dumpSchedule(); 231 dbgs() << '\n'; 232 }); 233 ScheduleDAGInstrs::exitRegion(); 234 } 235 236 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 237 /// dumpSchedule - dump the scheduled Sequence. 238 void SchedulePostRATDList::dumpSchedule() const { 239 for (unsigned i = 0, e = Sequence.size(); i != e; i++) { 240 if (SUnit *SU = Sequence[i]) 241 SU->dump(this); 242 else 243 dbgs() << "**** NOOP ****\n"; 244 } 245 } 246 #endif 247 248 bool PostRAScheduler::runOnMachineFunction(MachineFunction &Fn) { 249 if (skipOptnoneFunction(*Fn.getFunction())) 250 return false; 251 252 TII = Fn.getTarget().getInstrInfo(); 253 MachineLoopInfo &MLI = getAnalysis<MachineLoopInfo>(); 254 MachineDominatorTree &MDT = getAnalysis<MachineDominatorTree>(); 255 AliasAnalysis *AA = &getAnalysis<AliasAnalysis>(); 256 TargetPassConfig *PassConfig = &getAnalysis<TargetPassConfig>(); 257 258 RegClassInfo.runOnMachineFunction(Fn); 259 260 // Check for explicit enable/disable of post-ra scheduling. 261 TargetSubtargetInfo::AntiDepBreakMode AntiDepMode = 262 TargetSubtargetInfo::ANTIDEP_NONE; 263 SmallVector<const TargetRegisterClass*, 4> CriticalPathRCs; 264 if (EnablePostRAScheduler.getPosition() > 0) { 265 if (!EnablePostRAScheduler) 266 return false; 267 } else { 268 // Check that post-RA scheduling is enabled for this target. 269 // This may upgrade the AntiDepMode. 270 const TargetSubtargetInfo &ST = Fn.getTarget().getSubtarget<TargetSubtargetInfo>(); 271 if (!ST.enablePostRAScheduler(PassConfig->getOptLevel(), AntiDepMode, 272 CriticalPathRCs)) 273 return false; 274 } 275 276 // Check for antidep breaking override... 277 if (EnableAntiDepBreaking.getPosition() > 0) { 278 AntiDepMode = (EnableAntiDepBreaking == "all") 279 ? TargetSubtargetInfo::ANTIDEP_ALL 280 : ((EnableAntiDepBreaking == "critical") 281 ? TargetSubtargetInfo::ANTIDEP_CRITICAL 282 : TargetSubtargetInfo::ANTIDEP_NONE); 283 } 284 285 DEBUG(dbgs() << "PostRAScheduler\n"); 286 287 SchedulePostRATDList Scheduler(Fn, MLI, MDT, AA, RegClassInfo, AntiDepMode, 288 CriticalPathRCs); 289 290 // Loop over all of the basic blocks 291 for (MachineFunction::iterator MBB = Fn.begin(), MBBe = Fn.end(); 292 MBB != MBBe; ++MBB) { 293 #ifndef NDEBUG 294 // If DebugDiv > 0 then only schedule MBB with (ID % DebugDiv) == DebugMod 295 if (DebugDiv > 0) { 296 static int bbcnt = 0; 297 if (bbcnt++ % DebugDiv != DebugMod) 298 continue; 299 dbgs() << "*** DEBUG scheduling " << Fn.getName() 300 << ":BB#" << MBB->getNumber() << " ***\n"; 301 } 302 #endif 303 304 // Initialize register live-range state for scheduling in this block. 305 Scheduler.startBlock(MBB); 306 307 // Schedule each sequence of instructions not interrupted by a label 308 // or anything else that effectively needs to shut down scheduling. 309 MachineBasicBlock::iterator Current = MBB->end(); 310 unsigned Count = MBB->size(), CurrentCount = Count; 311 for (MachineBasicBlock::iterator I = Current; I != MBB->begin(); ) { 312 MachineInstr *MI = std::prev(I); 313 --Count; 314 // Calls are not scheduling boundaries before register allocation, but 315 // post-ra we don't gain anything by scheduling across calls since we 316 // don't need to worry about register pressure. 317 if (MI->isCall() || TII->isSchedulingBoundary(MI, MBB, Fn)) { 318 Scheduler.enterRegion(MBB, I, Current, CurrentCount - Count); 319 Scheduler.setEndIndex(CurrentCount); 320 Scheduler.schedule(); 321 Scheduler.exitRegion(); 322 Scheduler.EmitSchedule(); 323 Current = MI; 324 CurrentCount = Count; 325 Scheduler.Observe(MI, CurrentCount); 326 } 327 I = MI; 328 if (MI->isBundle()) 329 Count -= MI->getBundleSize(); 330 } 331 assert(Count == 0 && "Instruction count mismatch!"); 332 assert((MBB->begin() == Current || CurrentCount != 0) && 333 "Instruction count mismatch!"); 334 Scheduler.enterRegion(MBB, MBB->begin(), Current, CurrentCount); 335 Scheduler.setEndIndex(CurrentCount); 336 Scheduler.schedule(); 337 Scheduler.exitRegion(); 338 Scheduler.EmitSchedule(); 339 340 // Clean up register live-range state. 341 Scheduler.finishBlock(); 342 343 // Update register kills 344 Scheduler.fixupKills(MBB); 345 } 346 347 return true; 348 } 349 350 /// StartBlock - Initialize register live-range state for scheduling in 351 /// this block. 352 /// 353 void SchedulePostRATDList::startBlock(MachineBasicBlock *BB) { 354 // Call the superclass. 355 ScheduleDAGInstrs::startBlock(BB); 356 357 // Reset the hazard recognizer and anti-dep breaker. 358 HazardRec->Reset(); 359 if (AntiDepBreak) 360 AntiDepBreak->StartBlock(BB); 361 } 362 363 /// Schedule - Schedule the instruction range using list scheduling. 364 /// 365 void SchedulePostRATDList::schedule() { 366 // Build the scheduling graph. 367 buildSchedGraph(AA); 368 369 if (AntiDepBreak) { 370 unsigned Broken = 371 AntiDepBreak->BreakAntiDependencies(SUnits, RegionBegin, RegionEnd, 372 EndIndex, DbgValues); 373 374 if (Broken != 0) { 375 // We made changes. Update the dependency graph. 376 // Theoretically we could update the graph in place: 377 // When a live range is changed to use a different register, remove 378 // the def's anti-dependence *and* output-dependence edges due to 379 // that register, and add new anti-dependence and output-dependence 380 // edges based on the next live range of the register. 381 ScheduleDAG::clearDAG(); 382 buildSchedGraph(AA); 383 384 NumFixedAnti += Broken; 385 } 386 } 387 388 DEBUG(dbgs() << "********** List Scheduling **********\n"); 389 DEBUG(for (unsigned su = 0, e = SUnits.size(); su != e; ++su) 390 SUnits[su].dumpAll(this)); 391 392 AvailableQueue.initNodes(SUnits); 393 ListScheduleTopDown(); 394 AvailableQueue.releaseState(); 395 } 396 397 /// Observe - Update liveness information to account for the current 398 /// instruction, which will not be scheduled. 399 /// 400 void SchedulePostRATDList::Observe(MachineInstr *MI, unsigned Count) { 401 if (AntiDepBreak) 402 AntiDepBreak->Observe(MI, Count, EndIndex); 403 } 404 405 /// FinishBlock - Clean up register live-range state. 406 /// 407 void SchedulePostRATDList::finishBlock() { 408 if (AntiDepBreak) 409 AntiDepBreak->FinishBlock(); 410 411 // Call the superclass. 412 ScheduleDAGInstrs::finishBlock(); 413 } 414 415 //===----------------------------------------------------------------------===// 416 // Top-Down Scheduling 417 //===----------------------------------------------------------------------===// 418 419 /// ReleaseSucc - Decrement the NumPredsLeft count of a successor. Add it to 420 /// the PendingQueue if the count reaches zero. 421 void SchedulePostRATDList::ReleaseSucc(SUnit *SU, SDep *SuccEdge) { 422 SUnit *SuccSU = SuccEdge->getSUnit(); 423 424 if (SuccEdge->isWeak()) { 425 --SuccSU->WeakPredsLeft; 426 return; 427 } 428 #ifndef NDEBUG 429 if (SuccSU->NumPredsLeft == 0) { 430 dbgs() << "*** Scheduling failed! ***\n"; 431 SuccSU->dump(this); 432 dbgs() << " has been released too many times!\n"; 433 llvm_unreachable(nullptr); 434 } 435 #endif 436 --SuccSU->NumPredsLeft; 437 438 // Standard scheduler algorithms will recompute the depth of the successor 439 // here as such: 440 // SuccSU->setDepthToAtLeast(SU->getDepth() + SuccEdge->getLatency()); 441 // 442 // However, we lazily compute node depth instead. Note that 443 // ScheduleNodeTopDown has already updated the depth of this node which causes 444 // all descendents to be marked dirty. Setting the successor depth explicitly 445 // here would cause depth to be recomputed for all its ancestors. If the 446 // successor is not yet ready (because of a transitively redundant edge) then 447 // this causes depth computation to be quadratic in the size of the DAG. 448 449 // If all the node's predecessors are scheduled, this node is ready 450 // to be scheduled. Ignore the special ExitSU node. 451 if (SuccSU->NumPredsLeft == 0 && SuccSU != &ExitSU) 452 PendingQueue.push_back(SuccSU); 453 } 454 455 /// ReleaseSuccessors - Call ReleaseSucc on each of SU's successors. 456 void SchedulePostRATDList::ReleaseSuccessors(SUnit *SU) { 457 for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); 458 I != E; ++I) { 459 ReleaseSucc(SU, &*I); 460 } 461 } 462 463 /// ScheduleNodeTopDown - Add the node to the schedule. Decrement the pending 464 /// count of its successors. If a successor pending count is zero, add it to 465 /// the Available queue. 466 void SchedulePostRATDList::ScheduleNodeTopDown(SUnit *SU, unsigned CurCycle) { 467 DEBUG(dbgs() << "*** Scheduling [" << CurCycle << "]: "); 468 DEBUG(SU->dump(this)); 469 470 Sequence.push_back(SU); 471 assert(CurCycle >= SU->getDepth() && 472 "Node scheduled above its depth!"); 473 SU->setDepthToAtLeast(CurCycle); 474 475 ReleaseSuccessors(SU); 476 SU->isScheduled = true; 477 AvailableQueue.scheduledNode(SU); 478 } 479 480 /// emitNoop - Add a noop to the current instruction sequence. 481 void SchedulePostRATDList::emitNoop(unsigned CurCycle) { 482 DEBUG(dbgs() << "*** Emitting noop in cycle " << CurCycle << '\n'); 483 HazardRec->EmitNoop(); 484 Sequence.push_back(nullptr); // NULL here means noop 485 ++NumNoops; 486 } 487 488 /// ListScheduleTopDown - The main loop of list scheduling for top-down 489 /// schedulers. 490 void SchedulePostRATDList::ListScheduleTopDown() { 491 unsigned CurCycle = 0; 492 493 // We're scheduling top-down but we're visiting the regions in 494 // bottom-up order, so we don't know the hazards at the start of a 495 // region. So assume no hazards (this should usually be ok as most 496 // blocks are a single region). 497 HazardRec->Reset(); 498 499 // Release any successors of the special Entry node. 500 ReleaseSuccessors(&EntrySU); 501 502 // Add all leaves to Available queue. 503 for (unsigned i = 0, e = SUnits.size(); i != e; ++i) { 504 // It is available if it has no predecessors. 505 if (!SUnits[i].NumPredsLeft && !SUnits[i].isAvailable) { 506 AvailableQueue.push(&SUnits[i]); 507 SUnits[i].isAvailable = true; 508 } 509 } 510 511 // In any cycle where we can't schedule any instructions, we must 512 // stall or emit a noop, depending on the target. 513 bool CycleHasInsts = false; 514 515 // While Available queue is not empty, grab the node with the highest 516 // priority. If it is not ready put it back. Schedule the node. 517 std::vector<SUnit*> NotReady; 518 Sequence.reserve(SUnits.size()); 519 while (!AvailableQueue.empty() || !PendingQueue.empty()) { 520 // Check to see if any of the pending instructions are ready to issue. If 521 // so, add them to the available queue. 522 unsigned MinDepth = ~0u; 523 for (unsigned i = 0, e = PendingQueue.size(); i != e; ++i) { 524 if (PendingQueue[i]->getDepth() <= CurCycle) { 525 AvailableQueue.push(PendingQueue[i]); 526 PendingQueue[i]->isAvailable = true; 527 PendingQueue[i] = PendingQueue.back(); 528 PendingQueue.pop_back(); 529 --i; --e; 530 } else if (PendingQueue[i]->getDepth() < MinDepth) 531 MinDepth = PendingQueue[i]->getDepth(); 532 } 533 534 DEBUG(dbgs() << "\n*** Examining Available\n"; AvailableQueue.dump(this)); 535 536 SUnit *FoundSUnit = nullptr, *NotPreferredSUnit = nullptr; 537 bool HasNoopHazards = false; 538 while (!AvailableQueue.empty()) { 539 SUnit *CurSUnit = AvailableQueue.pop(); 540 541 ScheduleHazardRecognizer::HazardType HT = 542 HazardRec->getHazardType(CurSUnit, 0/*no stalls*/); 543 if (HT == ScheduleHazardRecognizer::NoHazard) { 544 if (HazardRec->ShouldPreferAnother(CurSUnit)) { 545 if (!NotPreferredSUnit) { 546 // If this is the first non-preferred node for this cycle, then 547 // record it and continue searching for a preferred node. If this 548 // is not the first non-preferred node, then treat it as though 549 // there had been a hazard. 550 NotPreferredSUnit = CurSUnit; 551 continue; 552 } 553 } else { 554 FoundSUnit = CurSUnit; 555 break; 556 } 557 } 558 559 // Remember if this is a noop hazard. 560 HasNoopHazards |= HT == ScheduleHazardRecognizer::NoopHazard; 561 562 NotReady.push_back(CurSUnit); 563 } 564 565 // If we have a non-preferred node, push it back onto the available list. 566 // If we did not find a preferred node, then schedule this first 567 // non-preferred node. 568 if (NotPreferredSUnit) { 569 if (!FoundSUnit) { 570 DEBUG(dbgs() << "*** Will schedule a non-preferred instruction...\n"); 571 FoundSUnit = NotPreferredSUnit; 572 } else { 573 AvailableQueue.push(NotPreferredSUnit); 574 } 575 576 NotPreferredSUnit = nullptr; 577 } 578 579 // Add the nodes that aren't ready back onto the available list. 580 if (!NotReady.empty()) { 581 AvailableQueue.push_all(NotReady); 582 NotReady.clear(); 583 } 584 585 // If we found a node to schedule... 586 if (FoundSUnit) { 587 // If we need to emit noops prior to this instruction, then do so. 588 unsigned NumPreNoops = HazardRec->PreEmitNoops(FoundSUnit); 589 for (unsigned i = 0; i != NumPreNoops; ++i) 590 emitNoop(CurCycle); 591 592 // ... schedule the node... 593 ScheduleNodeTopDown(FoundSUnit, CurCycle); 594 HazardRec->EmitInstruction(FoundSUnit); 595 CycleHasInsts = true; 596 if (HazardRec->atIssueLimit()) { 597 DEBUG(dbgs() << "*** Max instructions per cycle " << CurCycle << '\n'); 598 HazardRec->AdvanceCycle(); 599 ++CurCycle; 600 CycleHasInsts = false; 601 } 602 } else { 603 if (CycleHasInsts) { 604 DEBUG(dbgs() << "*** Finished cycle " << CurCycle << '\n'); 605 HazardRec->AdvanceCycle(); 606 } else if (!HasNoopHazards) { 607 // Otherwise, we have a pipeline stall, but no other problem, 608 // just advance the current cycle and try again. 609 DEBUG(dbgs() << "*** Stall in cycle " << CurCycle << '\n'); 610 HazardRec->AdvanceCycle(); 611 ++NumStalls; 612 } else { 613 // Otherwise, we have no instructions to issue and we have instructions 614 // that will fault if we don't do this right. This is the case for 615 // processors without pipeline interlocks and other cases. 616 emitNoop(CurCycle); 617 } 618 619 ++CurCycle; 620 CycleHasInsts = false; 621 } 622 } 623 624 #ifndef NDEBUG 625 unsigned ScheduledNodes = VerifyScheduledDAG(/*isBottomUp=*/false); 626 unsigned Noops = 0; 627 for (unsigned i = 0, e = Sequence.size(); i != e; ++i) 628 if (!Sequence[i]) 629 ++Noops; 630 assert(Sequence.size() - Noops == ScheduledNodes && 631 "The number of nodes scheduled doesn't match the expected number!"); 632 #endif // NDEBUG 633 } 634 635 // EmitSchedule - Emit the machine code in scheduled order. 636 void SchedulePostRATDList::EmitSchedule() { 637 RegionBegin = RegionEnd; 638 639 // If first instruction was a DBG_VALUE then put it back. 640 if (FirstDbgValue) 641 BB->splice(RegionEnd, BB, FirstDbgValue); 642 643 // Then re-insert them according to the given schedule. 644 for (unsigned i = 0, e = Sequence.size(); i != e; i++) { 645 if (SUnit *SU = Sequence[i]) 646 BB->splice(RegionEnd, BB, SU->getInstr()); 647 else 648 // Null SUnit* is a noop. 649 TII->insertNoop(*BB, RegionEnd); 650 651 // Update the Begin iterator, as the first instruction in the block 652 // may have been scheduled later. 653 if (i == 0) 654 RegionBegin = std::prev(RegionEnd); 655 } 656 657 // Reinsert any remaining debug_values. 658 for (std::vector<std::pair<MachineInstr *, MachineInstr *> >::iterator 659 DI = DbgValues.end(), DE = DbgValues.begin(); DI != DE; --DI) { 660 std::pair<MachineInstr *, MachineInstr *> P = *std::prev(DI); 661 MachineInstr *DbgValue = P.first; 662 MachineBasicBlock::iterator OrigPrivMI = P.second; 663 BB->splice(++OrigPrivMI, BB, DbgValue); 664 } 665 DbgValues.clear(); 666 FirstDbgValue = nullptr; 667 } 668