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