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 "AntiDepBreaker.h" 23 #include "AggressiveAntiDepBreaker.h" 24 #include "CriticalAntiDepBreaker.h" 25 #include "llvm/CodeGen/Passes.h" 26 #include "llvm/CodeGen/LatencyPriorityQueue.h" 27 #include "llvm/CodeGen/SchedulerRegistry.h" 28 #include "llvm/CodeGen/MachineDominators.h" 29 #include "llvm/CodeGen/MachineFrameInfo.h" 30 #include "llvm/CodeGen/MachineFunctionPass.h" 31 #include "llvm/CodeGen/MachineLoopInfo.h" 32 #include "llvm/CodeGen/MachineRegisterInfo.h" 33 #include "llvm/CodeGen/RegisterClassInfo.h" 34 #include "llvm/CodeGen/ScheduleDAGInstrs.h" 35 #include "llvm/CodeGen/ScheduleHazardRecognizer.h" 36 #include "llvm/Analysis/AliasAnalysis.h" 37 #include "llvm/Target/TargetLowering.h" 38 #include "llvm/Target/TargetMachine.h" 39 #include "llvm/Target/TargetInstrInfo.h" 40 #include "llvm/Target/TargetRegisterInfo.h" 41 #include "llvm/Target/TargetSubtargetInfo.h" 42 #include "llvm/Support/CommandLine.h" 43 #include "llvm/Support/Debug.h" 44 #include "llvm/Support/ErrorHandling.h" 45 #include "llvm/Support/raw_ostream.h" 46 #include "llvm/ADT/BitVector.h" 47 #include "llvm/ADT/Statistic.h" 48 using namespace llvm; 49 50 STATISTIC(NumNoops, "Number of noops inserted"); 51 STATISTIC(NumStalls, "Number of pipeline stalls"); 52 STATISTIC(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. 57 static cl::opt<bool> 58 EnablePostRAScheduler("post-RA-scheduler", 59 cl::desc("Enable scheduling after register allocation"), 60 cl::init(false), cl::Hidden); 61 static cl::opt<std::string> 62 EnableAntiDepBreaking("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 68 static cl::opt<int> 69 DebugDiv("postra-sched-debugdiv", 70 cl::desc("Debug control MBBs that are scheduled"), 71 cl::init(0), cl::Hidden); 72 static cl::opt<int> 73 DebugMod("postra-sched-debugmod", 74 cl::desc("Debug control MBBs that are scheduled"), 75 cl::init(0), cl::Hidden); 76 77 AntiDepBreaker::~AntiDepBreaker() { } 78 79 namespace { 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 { 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); 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 /// Topo - A topological ordering for SUnits. 115 ScheduleDAGTopologicalSort Topo; 116 117 /// HazardRec - The hazard recognizer to use. 118 ScheduleHazardRecognizer *HazardRec; 119 120 /// AntiDepBreak - Anti-dependence breaking object, or NULL if none 121 AntiDepBreaker *AntiDepBreak; 122 123 /// AA - AliasAnalysis for making memory reference queries. 124 AliasAnalysis *AA; 125 126 /// LiveRegs - true if the register is live. 127 BitVector LiveRegs; 128 129 /// The schedule. Null SUnit*'s represent noop instructions. 130 std::vector<SUnit*> Sequence; 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); 145 146 /// Initialize the scheduler state for the next scheduling region. 147 virtual void enterRegion(MachineBasicBlock *bb, 148 MachineBasicBlock::iterator begin, 149 MachineBasicBlock::iterator end, 150 unsigned endcount); 151 152 /// Notify that the scheduler has finished scheduling the current region. 153 virtual void exitRegion(); 154 155 /// Schedule - Schedule the instruction range using list scheduling. 156 /// 157 void schedule(); 158 159 void EmitSchedule(); 160 161 /// Observe - Update liveness information to account for the current 162 /// instruction, which will not be scheduled. 163 /// 164 void Observe(MachineInstr *MI, unsigned Count); 165 166 /// finishBlock - Clean up register live-range state. 167 /// 168 void finishBlock(); 169 170 /// FixupKills - Fix register kill flags that have been made 171 /// invalid due to scheduling 172 /// 173 void FixupKills(MachineBasicBlock *MBB); 174 175 private: 176 void ReleaseSucc(SUnit *SU, SDep *SuccEdge); 177 void ReleaseSuccessors(SUnit *SU); 178 void ScheduleNodeTopDown(SUnit *SU, unsigned CurCycle); 179 void ListScheduleTopDown(); 180 void StartBlockForKills(MachineBasicBlock *BB); 181 182 // ToggleKillFlag - Toggle a register operand kill flag. Other 183 // adjustments may be made to the instruction if necessary. Return 184 // true if the operand has been deleted, false if not. 185 bool ToggleKillFlag(MachineInstr *MI, MachineOperand &MO); 186 187 void dumpSchedule() const; 188 }; 189 } 190 191 char &llvm::PostRASchedulerID = PostRAScheduler::ID; 192 193 INITIALIZE_PASS(PostRAScheduler, "post-RA-sched", 194 "Post RA top-down list latency scheduler", false, false) 195 196 SchedulePostRATDList::SchedulePostRATDList( 197 MachineFunction &MF, MachineLoopInfo &MLI, MachineDominatorTree &MDT, 198 AliasAnalysis *AA, const RegisterClassInfo &RCI, 199 TargetSubtargetInfo::AntiDepBreakMode AntiDepMode, 200 SmallVectorImpl<const TargetRegisterClass*> &CriticalPathRCs) 201 : ScheduleDAGInstrs(MF, MLI, MDT, /*IsPostRA=*/true), Topo(SUnits), AA(AA), 202 LiveRegs(TRI->getNumRegs()) 203 { 204 const TargetMachine &TM = MF.getTarget(); 205 const InstrItineraryData *InstrItins = TM.getInstrItineraryData(); 206 HazardRec = 207 TM.getInstrInfo()->CreateTargetPostRAHazardRecognizer(InstrItins, this); 208 209 assert((AntiDepMode == TargetSubtargetInfo::ANTIDEP_NONE || 210 MRI.tracksLiveness()) && 211 "Live-ins must be accurate for anti-dependency breaking"); 212 AntiDepBreak = 213 ((AntiDepMode == TargetSubtargetInfo::ANTIDEP_ALL) ? 214 (AntiDepBreaker *)new AggressiveAntiDepBreaker(MF, RCI, CriticalPathRCs) : 215 ((AntiDepMode == TargetSubtargetInfo::ANTIDEP_CRITICAL) ? 216 (AntiDepBreaker *)new CriticalAntiDepBreaker(MF, RCI) : NULL)); 217 } 218 219 SchedulePostRATDList::~SchedulePostRATDList() { 220 delete HazardRec; 221 delete AntiDepBreak; 222 } 223 224 /// Initialize state associated with the next scheduling region. 225 void SchedulePostRATDList::enterRegion(MachineBasicBlock *bb, 226 MachineBasicBlock::iterator begin, 227 MachineBasicBlock::iterator end, 228 unsigned endcount) { 229 ScheduleDAGInstrs::enterRegion(bb, begin, end, endcount); 230 Sequence.clear(); 231 } 232 233 /// Print the schedule before exiting the region. 234 void SchedulePostRATDList::exitRegion() { 235 DEBUG({ 236 dbgs() << "*** Final schedule ***\n"; 237 dumpSchedule(); 238 dbgs() << '\n'; 239 }); 240 ScheduleDAGInstrs::exitRegion(); 241 } 242 243 #ifndef NDEBUG 244 /// dumpSchedule - dump the scheduled Sequence. 245 void SchedulePostRATDList::dumpSchedule() const { 246 for (unsigned i = 0, e = Sequence.size(); i != e; i++) { 247 if (SUnit *SU = Sequence[i]) 248 SU->dump(this); 249 else 250 dbgs() << "**** NOOP ****\n"; 251 } 252 } 253 #endif 254 255 bool PostRAScheduler::runOnMachineFunction(MachineFunction &Fn) { 256 TII = Fn.getTarget().getInstrInfo(); 257 MachineLoopInfo &MLI = getAnalysis<MachineLoopInfo>(); 258 MachineDominatorTree &MDT = getAnalysis<MachineDominatorTree>(); 259 AliasAnalysis *AA = &getAnalysis<AliasAnalysis>(); 260 TargetPassConfig *PassConfig = &getAnalysis<TargetPassConfig>(); 261 262 RegClassInfo.runOnMachineFunction(Fn); 263 264 // Check for explicit enable/disable of post-ra scheduling. 265 TargetSubtargetInfo::AntiDepBreakMode AntiDepMode = 266 TargetSubtargetInfo::ANTIDEP_NONE; 267 SmallVector<const TargetRegisterClass*, 4> CriticalPathRCs; 268 if (EnablePostRAScheduler.getPosition() > 0) { 269 if (!EnablePostRAScheduler) 270 return false; 271 } else { 272 // Check that post-RA scheduling is enabled for this target. 273 // This may upgrade the AntiDepMode. 274 const TargetSubtargetInfo &ST = Fn.getTarget().getSubtarget<TargetSubtargetInfo>(); 275 if (!ST.enablePostRAScheduler(PassConfig->getOptLevel(), AntiDepMode, 276 CriticalPathRCs)) 277 return false; 278 } 279 280 // Check for antidep breaking override... 281 if (EnableAntiDepBreaking.getPosition() > 0) { 282 AntiDepMode = (EnableAntiDepBreaking == "all") 283 ? TargetSubtargetInfo::ANTIDEP_ALL 284 : ((EnableAntiDepBreaking == "critical") 285 ? TargetSubtargetInfo::ANTIDEP_CRITICAL 286 : TargetSubtargetInfo::ANTIDEP_NONE); 287 } 288 289 DEBUG(dbgs() << "PostRAScheduler\n"); 290 291 SchedulePostRATDList Scheduler(Fn, MLI, MDT, AA, RegClassInfo, AntiDepMode, 292 CriticalPathRCs); 293 294 // Loop over all of the basic blocks 295 for (MachineFunction::iterator MBB = Fn.begin(), MBBe = Fn.end(); 296 MBB != MBBe; ++MBB) { 297 #ifndef NDEBUG 298 // If DebugDiv > 0 then only schedule MBB with (ID % DebugDiv) == DebugMod 299 if (DebugDiv > 0) { 300 static int bbcnt = 0; 301 if (bbcnt++ % DebugDiv != DebugMod) 302 continue; 303 dbgs() << "*** DEBUG scheduling " << Fn.getName() 304 << ":BB#" << MBB->getNumber() << " ***\n"; 305 } 306 #endif 307 308 // Initialize register live-range state for scheduling in this block. 309 Scheduler.startBlock(MBB); 310 311 // Schedule each sequence of instructions not interrupted by a label 312 // or anything else that effectively needs to shut down scheduling. 313 MachineBasicBlock::iterator Current = MBB->end(); 314 unsigned Count = MBB->size(), CurrentCount = Count; 315 for (MachineBasicBlock::iterator I = Current; I != MBB->begin(); ) { 316 MachineInstr *MI = llvm::prior(I); 317 // Calls are not scheduling boundaries before register allocation, but 318 // post-ra we don't gain anything by scheduling across calls since we 319 // don't need to worry about register pressure. 320 if (MI->isCall() || TII->isSchedulingBoundary(MI, MBB, Fn)) { 321 Scheduler.enterRegion(MBB, I, Current, CurrentCount); 322 Scheduler.schedule(); 323 Scheduler.exitRegion(); 324 Scheduler.EmitSchedule(); 325 Current = MI; 326 CurrentCount = Count - 1; 327 Scheduler.Observe(MI, CurrentCount); 328 } 329 I = MI; 330 --Count; 331 if (MI->isBundle()) 332 Count -= MI->getBundleSize(); 333 } 334 assert(Count == 0 && "Instruction count mismatch!"); 335 assert((MBB->begin() == Current || CurrentCount != 0) && 336 "Instruction count mismatch!"); 337 Scheduler.enterRegion(MBB, MBB->begin(), Current, CurrentCount); 338 Scheduler.schedule(); 339 Scheduler.exitRegion(); 340 Scheduler.EmitSchedule(); 341 342 // Clean up register live-range state. 343 Scheduler.finishBlock(); 344 345 // Update register kills 346 Scheduler.FixupKills(MBB); 347 } 348 349 return true; 350 } 351 352 /// StartBlock - Initialize register live-range state for scheduling in 353 /// this block. 354 /// 355 void SchedulePostRATDList::startBlock(MachineBasicBlock *BB) { 356 // Call the superclass. 357 ScheduleDAGInstrs::startBlock(BB); 358 359 // Reset the hazard recognizer and anti-dep breaker. 360 HazardRec->Reset(); 361 if (AntiDepBreak != NULL) 362 AntiDepBreak->StartBlock(BB); 363 } 364 365 /// Schedule - Schedule the instruction range using list scheduling. 366 /// 367 void SchedulePostRATDList::schedule() { 368 // Build the scheduling graph. 369 buildSchedGraph(AA); 370 371 if (AntiDepBreak != NULL) { 372 unsigned Broken = 373 AntiDepBreak->BreakAntiDependencies(SUnits, RegionBegin, RegionEnd, 374 EndIndex, DbgValues); 375 376 if (Broken != 0) { 377 // We made changes. Update the dependency graph. 378 // Theoretically we could update the graph in place: 379 // When a live range is changed to use a different register, remove 380 // the def's anti-dependence *and* output-dependence edges due to 381 // that register, and add new anti-dependence and output-dependence 382 // edges based on the next live range of the register. 383 ScheduleDAG::clearDAG(); 384 buildSchedGraph(AA); 385 386 NumFixedAnti += Broken; 387 } 388 } 389 390 DEBUG(dbgs() << "********** List Scheduling **********\n"); 391 DEBUG(for (unsigned su = 0, e = SUnits.size(); su != e; ++su) 392 SUnits[su].dumpAll(this)); 393 394 AvailableQueue.initNodes(SUnits); 395 ListScheduleTopDown(); 396 AvailableQueue.releaseState(); 397 } 398 399 /// Observe - Update liveness information to account for the current 400 /// instruction, which will not be scheduled. 401 /// 402 void SchedulePostRATDList::Observe(MachineInstr *MI, unsigned Count) { 403 if (AntiDepBreak != NULL) 404 AntiDepBreak->Observe(MI, Count, EndIndex); 405 } 406 407 /// FinishBlock - Clean up register live-range state. 408 /// 409 void SchedulePostRATDList::finishBlock() { 410 if (AntiDepBreak != NULL) 411 AntiDepBreak->FinishBlock(); 412 413 // Call the superclass. 414 ScheduleDAGInstrs::finishBlock(); 415 } 416 417 /// StartBlockForKills - Initialize register live-range state for updating kills 418 /// 419 void SchedulePostRATDList::StartBlockForKills(MachineBasicBlock *BB) { 420 // Start with no live registers. 421 LiveRegs.reset(); 422 423 // Determine the live-out physregs for this block. 424 if (!BB->empty() && BB->back().isReturn()) { 425 // In a return block, examine the function live-out regs. 426 for (MachineRegisterInfo::liveout_iterator I = MRI.liveout_begin(), 427 E = MRI.liveout_end(); I != E; ++I) { 428 unsigned Reg = *I; 429 LiveRegs.set(Reg); 430 // Repeat, for all subregs. 431 for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs) 432 LiveRegs.set(*SubRegs); 433 } 434 } 435 else { 436 // In a non-return block, examine the live-in regs of all successors. 437 for (MachineBasicBlock::succ_iterator SI = BB->succ_begin(), 438 SE = BB->succ_end(); SI != SE; ++SI) { 439 for (MachineBasicBlock::livein_iterator I = (*SI)->livein_begin(), 440 E = (*SI)->livein_end(); I != E; ++I) { 441 unsigned Reg = *I; 442 LiveRegs.set(Reg); 443 // Repeat, for all subregs. 444 for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs) 445 LiveRegs.set(*SubRegs); 446 } 447 } 448 } 449 } 450 451 bool SchedulePostRATDList::ToggleKillFlag(MachineInstr *MI, 452 MachineOperand &MO) { 453 // Setting kill flag... 454 if (!MO.isKill()) { 455 MO.setIsKill(true); 456 return false; 457 } 458 459 // If MO itself is live, clear the kill flag... 460 if (LiveRegs.test(MO.getReg())) { 461 MO.setIsKill(false); 462 return false; 463 } 464 465 // If any subreg of MO is live, then create an imp-def for that 466 // subreg and keep MO marked as killed. 467 MO.setIsKill(false); 468 bool AllDead = true; 469 const unsigned SuperReg = MO.getReg(); 470 for (MCSubRegIterator SubRegs(SuperReg, TRI); SubRegs.isValid(); ++SubRegs) { 471 if (LiveRegs.test(*SubRegs)) { 472 MI->addOperand(MachineOperand::CreateReg(*SubRegs, 473 true /*IsDef*/, 474 true /*IsImp*/, 475 false /*IsKill*/, 476 false /*IsDead*/)); 477 AllDead = false; 478 } 479 } 480 481 if(AllDead) 482 MO.setIsKill(true); 483 return false; 484 } 485 486 /// FixupKills - Fix the register kill flags, they may have been made 487 /// incorrect by instruction reordering. 488 /// 489 void SchedulePostRATDList::FixupKills(MachineBasicBlock *MBB) { 490 DEBUG(dbgs() << "Fixup kills for BB#" << MBB->getNumber() << '\n'); 491 492 BitVector killedRegs(TRI->getNumRegs()); 493 BitVector ReservedRegs = TRI->getReservedRegs(MF); 494 495 StartBlockForKills(MBB); 496 497 // Examine block from end to start... 498 unsigned Count = MBB->size(); 499 for (MachineBasicBlock::iterator I = MBB->end(), E = MBB->begin(); 500 I != E; --Count) { 501 MachineInstr *MI = --I; 502 if (MI->isDebugValue()) 503 continue; 504 505 // Update liveness. Registers that are defed but not used in this 506 // instruction are now dead. Mark register and all subregs as they 507 // are completely defined. 508 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 509 MachineOperand &MO = MI->getOperand(i); 510 if (MO.isRegMask()) 511 LiveRegs.clearBitsNotInMask(MO.getRegMask()); 512 if (!MO.isReg()) continue; 513 unsigned Reg = MO.getReg(); 514 if (Reg == 0) continue; 515 if (!MO.isDef()) continue; 516 // Ignore two-addr defs. 517 if (MI->isRegTiedToUseOperand(i)) continue; 518 519 LiveRegs.reset(Reg); 520 521 // Repeat for all subregs. 522 for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs) 523 LiveRegs.reset(*SubRegs); 524 } 525 526 // Examine all used registers and set/clear kill flag. When a 527 // register is used multiple times we only set the kill flag on 528 // the first use. 529 killedRegs.reset(); 530 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 531 MachineOperand &MO = MI->getOperand(i); 532 if (!MO.isReg() || !MO.isUse()) continue; 533 unsigned Reg = MO.getReg(); 534 if ((Reg == 0) || ReservedRegs.test(Reg)) continue; 535 536 bool kill = false; 537 if (!killedRegs.test(Reg)) { 538 kill = true; 539 // A register is not killed if any subregs are live... 540 for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs) { 541 if (LiveRegs.test(*SubRegs)) { 542 kill = false; 543 break; 544 } 545 } 546 547 // If subreg is not live, then register is killed if it became 548 // live in this instruction 549 if (kill) 550 kill = !LiveRegs.test(Reg); 551 } 552 553 if (MO.isKill() != kill) { 554 DEBUG(dbgs() << "Fixing " << MO << " in "); 555 // Warning: ToggleKillFlag may invalidate MO. 556 ToggleKillFlag(MI, MO); 557 DEBUG(MI->dump()); 558 } 559 560 killedRegs.set(Reg); 561 } 562 563 // Mark any used register (that is not using undef) and subregs as 564 // now live... 565 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 566 MachineOperand &MO = MI->getOperand(i); 567 if (!MO.isReg() || !MO.isUse() || MO.isUndef()) continue; 568 unsigned Reg = MO.getReg(); 569 if ((Reg == 0) || ReservedRegs.test(Reg)) continue; 570 571 LiveRegs.set(Reg); 572 573 for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs) 574 LiveRegs.set(*SubRegs); 575 } 576 } 577 } 578 579 //===----------------------------------------------------------------------===// 580 // Top-Down Scheduling 581 //===----------------------------------------------------------------------===// 582 583 /// ReleaseSucc - Decrement the NumPredsLeft count of a successor. Add it to 584 /// the PendingQueue if the count reaches zero. Also update its cycle bound. 585 void SchedulePostRATDList::ReleaseSucc(SUnit *SU, SDep *SuccEdge) { 586 SUnit *SuccSU = SuccEdge->getSUnit(); 587 588 #ifndef NDEBUG 589 if (SuccSU->NumPredsLeft == 0) { 590 dbgs() << "*** Scheduling failed! ***\n"; 591 SuccSU->dump(this); 592 dbgs() << " has been released too many times!\n"; 593 llvm_unreachable(0); 594 } 595 #endif 596 --SuccSU->NumPredsLeft; 597 598 // Standard scheduler algorithms will recompute the depth of the successor 599 // here as such: 600 // SuccSU->setDepthToAtLeast(SU->getDepth() + SuccEdge->getLatency()); 601 // 602 // However, we lazily compute node depth instead. Note that 603 // ScheduleNodeTopDown has already updated the depth of this node which causes 604 // all descendents to be marked dirty. Setting the successor depth explicitly 605 // here would cause depth to be recomputed for all its ancestors. If the 606 // successor is not yet ready (because of a transitively redundant edge) then 607 // this causes depth computation to be quadratic in the size of the DAG. 608 609 // If all the node's predecessors are scheduled, this node is ready 610 // to be scheduled. Ignore the special ExitSU node. 611 if (SuccSU->NumPredsLeft == 0 && SuccSU != &ExitSU) 612 PendingQueue.push_back(SuccSU); 613 } 614 615 /// ReleaseSuccessors - Call ReleaseSucc on each of SU's successors. 616 void SchedulePostRATDList::ReleaseSuccessors(SUnit *SU) { 617 for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); 618 I != E; ++I) { 619 ReleaseSucc(SU, &*I); 620 } 621 } 622 623 /// ScheduleNodeTopDown - Add the node to the schedule. Decrement the pending 624 /// count of its successors. If a successor pending count is zero, add it to 625 /// the Available queue. 626 void SchedulePostRATDList::ScheduleNodeTopDown(SUnit *SU, unsigned CurCycle) { 627 DEBUG(dbgs() << "*** Scheduling [" << CurCycle << "]: "); 628 DEBUG(SU->dump(this)); 629 630 Sequence.push_back(SU); 631 assert(CurCycle >= SU->getDepth() && 632 "Node scheduled above its depth!"); 633 SU->setDepthToAtLeast(CurCycle); 634 635 ReleaseSuccessors(SU); 636 SU->isScheduled = true; 637 AvailableQueue.scheduledNode(SU); 638 } 639 640 /// ListScheduleTopDown - The main loop of list scheduling for top-down 641 /// schedulers. 642 void SchedulePostRATDList::ListScheduleTopDown() { 643 unsigned CurCycle = 0; 644 645 // We're scheduling top-down but we're visiting the regions in 646 // bottom-up order, so we don't know the hazards at the start of a 647 // region. So assume no hazards (this should usually be ok as most 648 // blocks are a single region). 649 HazardRec->Reset(); 650 651 // Release any successors of the special Entry node. 652 ReleaseSuccessors(&EntrySU); 653 654 // Add all leaves to Available queue. 655 for (unsigned i = 0, e = SUnits.size(); i != e; ++i) { 656 // It is available if it has no predecessors. 657 bool available = SUnits[i].Preds.empty(); 658 if (available) { 659 AvailableQueue.push(&SUnits[i]); 660 SUnits[i].isAvailable = true; 661 } 662 } 663 664 // In any cycle where we can't schedule any instructions, we must 665 // stall or emit a noop, depending on the target. 666 bool CycleHasInsts = false; 667 668 // While Available queue is not empty, grab the node with the highest 669 // priority. If it is not ready put it back. Schedule the node. 670 std::vector<SUnit*> NotReady; 671 Sequence.reserve(SUnits.size()); 672 while (!AvailableQueue.empty() || !PendingQueue.empty()) { 673 // Check to see if any of the pending instructions are ready to issue. If 674 // so, add them to the available queue. 675 unsigned MinDepth = ~0u; 676 for (unsigned i = 0, e = PendingQueue.size(); i != e; ++i) { 677 if (PendingQueue[i]->getDepth() <= CurCycle) { 678 AvailableQueue.push(PendingQueue[i]); 679 PendingQueue[i]->isAvailable = true; 680 PendingQueue[i] = PendingQueue.back(); 681 PendingQueue.pop_back(); 682 --i; --e; 683 } else if (PendingQueue[i]->getDepth() < MinDepth) 684 MinDepth = PendingQueue[i]->getDepth(); 685 } 686 687 DEBUG(dbgs() << "\n*** Examining Available\n"; AvailableQueue.dump(this)); 688 689 SUnit *FoundSUnit = 0; 690 bool HasNoopHazards = false; 691 while (!AvailableQueue.empty()) { 692 SUnit *CurSUnit = AvailableQueue.pop(); 693 694 ScheduleHazardRecognizer::HazardType HT = 695 HazardRec->getHazardType(CurSUnit, 0/*no stalls*/); 696 if (HT == ScheduleHazardRecognizer::NoHazard) { 697 FoundSUnit = CurSUnit; 698 break; 699 } 700 701 // Remember if this is a noop hazard. 702 HasNoopHazards |= HT == ScheduleHazardRecognizer::NoopHazard; 703 704 NotReady.push_back(CurSUnit); 705 } 706 707 // Add the nodes that aren't ready back onto the available list. 708 if (!NotReady.empty()) { 709 AvailableQueue.push_all(NotReady); 710 NotReady.clear(); 711 } 712 713 // If we found a node to schedule... 714 if (FoundSUnit) { 715 // ... schedule the node... 716 ScheduleNodeTopDown(FoundSUnit, CurCycle); 717 HazardRec->EmitInstruction(FoundSUnit); 718 CycleHasInsts = true; 719 if (HazardRec->atIssueLimit()) { 720 DEBUG(dbgs() << "*** Max instructions per cycle " << CurCycle << '\n'); 721 HazardRec->AdvanceCycle(); 722 ++CurCycle; 723 CycleHasInsts = false; 724 } 725 } else { 726 if (CycleHasInsts) { 727 DEBUG(dbgs() << "*** Finished cycle " << CurCycle << '\n'); 728 HazardRec->AdvanceCycle(); 729 } else if (!HasNoopHazards) { 730 // Otherwise, we have a pipeline stall, but no other problem, 731 // just advance the current cycle and try again. 732 DEBUG(dbgs() << "*** Stall in cycle " << CurCycle << '\n'); 733 HazardRec->AdvanceCycle(); 734 ++NumStalls; 735 } else { 736 // Otherwise, we have no instructions to issue and we have instructions 737 // that will fault if we don't do this right. This is the case for 738 // processors without pipeline interlocks and other cases. 739 DEBUG(dbgs() << "*** Emitting noop in cycle " << CurCycle << '\n'); 740 HazardRec->EmitNoop(); 741 Sequence.push_back(0); // NULL here means noop 742 ++NumNoops; 743 } 744 745 ++CurCycle; 746 CycleHasInsts = false; 747 } 748 } 749 750 #ifndef NDEBUG 751 unsigned ScheduledNodes = VerifyScheduledDAG(/*isBottomUp=*/false); 752 unsigned Noops = 0; 753 for (unsigned i = 0, e = Sequence.size(); i != e; ++i) 754 if (!Sequence[i]) 755 ++Noops; 756 assert(Sequence.size() - Noops == ScheduledNodes && 757 "The number of nodes scheduled doesn't match the expected number!"); 758 #endif // NDEBUG 759 } 760 761 // EmitSchedule - Emit the machine code in scheduled order. 762 void SchedulePostRATDList::EmitSchedule() { 763 RegionBegin = RegionEnd; 764 765 // If first instruction was a DBG_VALUE then put it back. 766 if (FirstDbgValue) 767 BB->splice(RegionEnd, BB, FirstDbgValue); 768 769 // Then re-insert them according to the given schedule. 770 for (unsigned i = 0, e = Sequence.size(); i != e; i++) { 771 if (SUnit *SU = Sequence[i]) 772 BB->splice(RegionEnd, BB, SU->getInstr()); 773 else 774 // Null SUnit* is a noop. 775 TII->insertNoop(*BB, RegionEnd); 776 777 // Update the Begin iterator, as the first instruction in the block 778 // may have been scheduled later. 779 if (i == 0) 780 RegionBegin = prior(RegionEnd); 781 } 782 783 // Reinsert any remaining debug_values. 784 for (std::vector<std::pair<MachineInstr *, MachineInstr *> >::iterator 785 DI = DbgValues.end(), DE = DbgValues.begin(); DI != DE; --DI) { 786 std::pair<MachineInstr *, MachineInstr *> P = *prior(DI); 787 MachineInstr *DbgValue = P.first; 788 MachineBasicBlock::iterator OrigPrivMI = P.second; 789 BB->splice(++OrigPrivMI, BB, DbgValue); 790 } 791 DbgValues.clear(); 792 FirstDbgValue = NULL; 793 } 794