PostRASchedulerList.cpp revision 8295d4c96c8530acb7ae0098d813b53dc4fe0a89
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 "ExactHazardRecognizer.h" 26#include "SimpleHazardRecognizer.h" 27#include "ScheduleDAGInstrs.h" 28#include "llvm/CodeGen/Passes.h" 29#include "llvm/CodeGen/LatencyPriorityQueue.h" 30#include "llvm/CodeGen/SchedulerRegistry.h" 31#include "llvm/CodeGen/MachineDominators.h" 32#include "llvm/CodeGen/MachineFrameInfo.h" 33#include "llvm/CodeGen/MachineFunctionPass.h" 34#include "llvm/CodeGen/MachineLoopInfo.h" 35#include "llvm/CodeGen/MachineRegisterInfo.h" 36#include "llvm/CodeGen/ScheduleHazardRecognizer.h" 37#include "llvm/Analysis/AliasAnalysis.h" 38#include "llvm/Target/TargetLowering.h" 39#include "llvm/Target/TargetMachine.h" 40#include "llvm/Target/TargetInstrInfo.h" 41#include "llvm/Target/TargetRegisterInfo.h" 42#include "llvm/Target/TargetSubtarget.h" 43#include "llvm/Support/CommandLine.h" 44#include "llvm/Support/Debug.h" 45#include "llvm/Support/ErrorHandling.h" 46#include "llvm/Support/raw_ostream.h" 47#include "llvm/ADT/BitVector.h" 48#include "llvm/ADT/Statistic.h" 49#include <set> 50using namespace llvm; 51 52STATISTIC(NumNoops, "Number of noops inserted"); 53STATISTIC(NumStalls, "Number of pipeline stalls"); 54STATISTIC(NumFixedAnti, "Number of fixed anti-dependencies"); 55 56// Post-RA scheduling is enabled with 57// TargetSubtarget.enablePostRAScheduler(). This flag can be used to 58// override the target. 59static cl::opt<bool> 60EnablePostRAScheduler("post-RA-scheduler", 61 cl::desc("Enable scheduling after register allocation"), 62 cl::init(false), cl::Hidden); 63static cl::opt<std::string> 64EnableAntiDepBreaking("break-anti-dependencies", 65 cl::desc("Break post-RA scheduling anti-dependencies: " 66 "\"critical\", \"all\", or \"none\""), 67 cl::init("none"), cl::Hidden); 68static cl::opt<bool> 69EnablePostRAHazardAvoidance("avoid-hazards", 70 cl::desc("Enable exact hazard avoidance"), 71 cl::init(true), cl::Hidden); 72 73// If DebugDiv > 0 then only schedule MBB with (ID % DebugDiv) == DebugMod 74static cl::opt<int> 75DebugDiv("postra-sched-debugdiv", 76 cl::desc("Debug control MBBs that are scheduled"), 77 cl::init(0), cl::Hidden); 78static cl::opt<int> 79DebugMod("postra-sched-debugmod", 80 cl::desc("Debug control MBBs that are scheduled"), 81 cl::init(0), cl::Hidden); 82 83AntiDepBreaker::~AntiDepBreaker() { } 84 85namespace { 86 class PostRAScheduler : public MachineFunctionPass { 87 AliasAnalysis *AA; 88 CodeGenOpt::Level OptLevel; 89 90 public: 91 static char ID; 92 PostRAScheduler(CodeGenOpt::Level ol) : 93 MachineFunctionPass(&ID), OptLevel(ol) {} 94 95 void getAnalysisUsage(AnalysisUsage &AU) const { 96 AU.setPreservesCFG(); 97 AU.addRequired<AliasAnalysis>(); 98 AU.addRequired<MachineDominatorTree>(); 99 AU.addPreserved<MachineDominatorTree>(); 100 AU.addRequired<MachineLoopInfo>(); 101 AU.addPreserved<MachineLoopInfo>(); 102 MachineFunctionPass::getAnalysisUsage(AU); 103 } 104 105 const char *getPassName() const { 106 return "Post RA top-down list latency scheduler"; 107 } 108 109 bool runOnMachineFunction(MachineFunction &Fn); 110 }; 111 char PostRAScheduler::ID = 0; 112 113 class SchedulePostRATDList : public ScheduleDAGInstrs { 114 /// AvailableQueue - The priority queue to use for the available SUnits. 115 /// 116 LatencyPriorityQueue AvailableQueue; 117 118 /// PendingQueue - This contains all of the instructions whose operands have 119 /// been issued, but their results are not ready yet (due to the latency of 120 /// the operation). Once the operands becomes available, the instruction is 121 /// added to the AvailableQueue. 122 std::vector<SUnit*> PendingQueue; 123 124 /// Topo - A topological ordering for SUnits. 125 ScheduleDAGTopologicalSort Topo; 126 127 /// HazardRec - The hazard recognizer to use. 128 ScheduleHazardRecognizer *HazardRec; 129 130 /// AntiDepBreak - Anti-dependence breaking object, or NULL if none 131 AntiDepBreaker *AntiDepBreak; 132 133 /// AA - AliasAnalysis for making memory reference queries. 134 AliasAnalysis *AA; 135 136 /// KillIndices - The index of the most recent kill (proceding bottom-up), 137 /// or ~0u if the register is not live. 138 unsigned KillIndices[TargetRegisterInfo::FirstVirtualRegister]; 139 140 public: 141 SchedulePostRATDList(MachineFunction &MF, 142 const MachineLoopInfo &MLI, 143 const MachineDominatorTree &MDT, 144 ScheduleHazardRecognizer *HR, 145 AntiDepBreaker *ADB, 146 AliasAnalysis *aa) 147 : ScheduleDAGInstrs(MF, MLI, MDT), Topo(SUnits), 148 HazardRec(HR), AntiDepBreak(ADB), AA(aa) {} 149 150 ~SchedulePostRATDList() { 151 } 152 153 /// StartBlock - Initialize register live-range state for scheduling in 154 /// this block. 155 /// 156 void StartBlock(MachineBasicBlock *BB); 157 158 /// Schedule - Schedule the instruction range using list scheduling. 159 /// 160 void Schedule(); 161 162 /// Observe - Update liveness information to account for the current 163 /// instruction, which will not be scheduled. 164 /// 165 void Observe(MachineInstr *MI, unsigned Count); 166 167 /// FinishBlock - Clean up register live-range state. 168 /// 169 void FinishBlock(); 170 171 /// FixupKills - Fix register kill flags that have been made 172 /// invalid due to scheduling 173 /// 174 void FixupKills(MachineBasicBlock *MBB); 175 176 private: 177 void ReleaseSucc(SUnit *SU, SDep *SuccEdge); 178 void ReleaseSuccessors(SUnit *SU); 179 void ScheduleNodeTopDown(SUnit *SU, unsigned CurCycle); 180 void ListScheduleTopDown(); 181 void StartBlockForKills(MachineBasicBlock *BB); 182 183 // ToggleKillFlag - Toggle a register operand kill flag. Other 184 // adjustments may be made to the instruction if necessary. Return 185 // true if the operand has been deleted, false if not. 186 bool ToggleKillFlag(MachineInstr *MI, MachineOperand &MO); 187 }; 188} 189 190/// isSchedulingBoundary - Test if the given instruction should be 191/// considered a scheduling boundary. This primarily includes labels 192/// and terminators. 193/// 194static bool isSchedulingBoundary(const MachineInstr *MI, 195 const MachineFunction &MF) { 196 // Terminators and labels can't be scheduled around. 197 if (MI->getDesc().isTerminator() || MI->isLabel()) 198 return true; 199 200 // Don't attempt to schedule around any instruction that modifies 201 // a stack-oriented pointer, as it's unlikely to be profitable. This 202 // saves compile time, because it doesn't require every single 203 // stack slot reference to depend on the instruction that does the 204 // modification. 205 const TargetLowering &TLI = *MF.getTarget().getTargetLowering(); 206 if (MI->modifiesRegister(TLI.getStackPointerRegisterToSaveRestore())) 207 return true; 208 209 return false; 210} 211 212bool PostRAScheduler::runOnMachineFunction(MachineFunction &Fn) { 213 AA = &getAnalysis<AliasAnalysis>(); 214 215 // Check for explicit enable/disable of post-ra scheduling. 216 TargetSubtarget::AntiDepBreakMode AntiDepMode = TargetSubtarget::ANTIDEP_NONE; 217 SmallVector<TargetRegisterClass*, 4> CriticalPathRCs; 218 if (EnablePostRAScheduler.getPosition() > 0) { 219 if (!EnablePostRAScheduler) 220 return false; 221 } else { 222 // Check that post-RA scheduling is enabled for this target. 223 const TargetSubtarget &ST = Fn.getTarget().getSubtarget<TargetSubtarget>(); 224 if (!ST.enablePostRAScheduler(OptLevel, AntiDepMode, CriticalPathRCs)) 225 return false; 226 } 227 228 // Check for antidep breaking override... 229 if (EnableAntiDepBreaking.getPosition() > 0) { 230 AntiDepMode = (EnableAntiDepBreaking == "all") ? TargetSubtarget::ANTIDEP_ALL : 231 (EnableAntiDepBreaking == "critical") ? TargetSubtarget::ANTIDEP_CRITICAL : 232 TargetSubtarget::ANTIDEP_NONE; 233 } 234 235 DEBUG(dbgs() << "PostRAScheduler\n"); 236 237 const MachineLoopInfo &MLI = getAnalysis<MachineLoopInfo>(); 238 const MachineDominatorTree &MDT = getAnalysis<MachineDominatorTree>(); 239 const InstrItineraryData &InstrItins = Fn.getTarget().getInstrItineraryData(); 240 ScheduleHazardRecognizer *HR = EnablePostRAHazardAvoidance ? 241 (ScheduleHazardRecognizer *)new ExactHazardRecognizer(InstrItins) : 242 (ScheduleHazardRecognizer *)new SimpleHazardRecognizer(); 243 AntiDepBreaker *ADB = 244 ((AntiDepMode == TargetSubtarget::ANTIDEP_ALL) ? 245 (AntiDepBreaker *)new AggressiveAntiDepBreaker(Fn, CriticalPathRCs) : 246 ((AntiDepMode == TargetSubtarget::ANTIDEP_CRITICAL) ? 247 (AntiDepBreaker *)new CriticalAntiDepBreaker(Fn) : NULL)); 248 249 SchedulePostRATDList Scheduler(Fn, MLI, MDT, HR, ADB, AA); 250 251 // Loop over all of the basic blocks 252 for (MachineFunction::iterator MBB = Fn.begin(), MBBe = Fn.end(); 253 MBB != MBBe; ++MBB) { 254#ifndef NDEBUG 255 // If DebugDiv > 0 then only schedule MBB with (ID % DebugDiv) == DebugMod 256 if (DebugDiv > 0) { 257 static int bbcnt = 0; 258 if (bbcnt++ % DebugDiv != DebugMod) 259 continue; 260 dbgs() << "*** DEBUG scheduling " << Fn.getFunction()->getNameStr() << 261 ":BB#" << MBB->getNumber() << " ***\n"; 262 } 263#endif 264 265 // Initialize register live-range state for scheduling in this block. 266 Scheduler.StartBlock(MBB); 267 268 // FIXME: Temporary workaround for <rdar://problem/7759363>: The post-RA 269 // scheduler has some sort of problem with DebugValue instructions that 270 // causes an assertion in LeaksContext.h to fail occasionally. Just 271 // remove all those instructions for now. 272 for (MachineBasicBlock::iterator I = MBB->begin(), E = MBB->end(); 273 I != E; ) { 274 MachineInstr *MI = &*I++; 275 if (MI->isDebugValue()) 276 MI->eraseFromParent(); 277 } 278 279 // Schedule each sequence of instructions not interrupted by a label 280 // or anything else that effectively needs to shut down scheduling. 281 MachineBasicBlock::iterator Current = MBB->end(); 282 unsigned Count = MBB->size(), CurrentCount = Count; 283 for (MachineBasicBlock::iterator I = Current; I != MBB->begin(); ) { 284 MachineInstr *MI = prior(I); 285 if (isSchedulingBoundary(MI, Fn)) { 286 Scheduler.Run(MBB, I, Current, CurrentCount); 287 Scheduler.EmitSchedule(0); 288 Current = MI; 289 CurrentCount = Count - 1; 290 Scheduler.Observe(MI, CurrentCount); 291 } 292 I = MI; 293 --Count; 294 } 295 assert(Count == 0 && "Instruction count mismatch!"); 296 assert((MBB->begin() == Current || CurrentCount != 0) && 297 "Instruction count mismatch!"); 298 Scheduler.Run(MBB, MBB->begin(), Current, CurrentCount); 299 Scheduler.EmitSchedule(0); 300 301 // Clean up register live-range state. 302 Scheduler.FinishBlock(); 303 304 // Update register kills 305 Scheduler.FixupKills(MBB); 306 } 307 308 delete HR; 309 delete ADB; 310 311 return true; 312} 313 314/// StartBlock - Initialize register live-range state for scheduling in 315/// this block. 316/// 317void SchedulePostRATDList::StartBlock(MachineBasicBlock *BB) { 318 // Call the superclass. 319 ScheduleDAGInstrs::StartBlock(BB); 320 321 // Reset the hazard recognizer and anti-dep breaker. 322 HazardRec->Reset(); 323 if (AntiDepBreak != NULL) 324 AntiDepBreak->StartBlock(BB); 325} 326 327/// Schedule - Schedule the instruction range using list scheduling. 328/// 329void SchedulePostRATDList::Schedule() { 330 // Build the scheduling graph. 331 BuildSchedGraph(AA); 332 333 if (AntiDepBreak != NULL) { 334 unsigned Broken = 335 AntiDepBreak->BreakAntiDependencies(SUnits, Begin, InsertPos, 336 InsertPosIndex); 337 338 if (Broken != 0) { 339 // We made changes. Update the dependency graph. 340 // Theoretically we could update the graph in place: 341 // When a live range is changed to use a different register, remove 342 // the def's anti-dependence *and* output-dependence edges due to 343 // that register, and add new anti-dependence and output-dependence 344 // edges based on the next live range of the register. 345 SUnits.clear(); 346 Sequence.clear(); 347 EntrySU = SUnit(); 348 ExitSU = SUnit(); 349 BuildSchedGraph(AA); 350 351 NumFixedAnti += Broken; 352 } 353 } 354 355 DEBUG(dbgs() << "********** List Scheduling **********\n"); 356 DEBUG(for (unsigned su = 0, e = SUnits.size(); su != e; ++su) 357 SUnits[su].dumpAll(this)); 358 359 AvailableQueue.initNodes(SUnits); 360 ListScheduleTopDown(); 361 AvailableQueue.releaseState(); 362} 363 364/// Observe - Update liveness information to account for the current 365/// instruction, which will not be scheduled. 366/// 367void SchedulePostRATDList::Observe(MachineInstr *MI, unsigned Count) { 368 if (AntiDepBreak != NULL) 369 AntiDepBreak->Observe(MI, Count, InsertPosIndex); 370} 371 372/// FinishBlock - Clean up register live-range state. 373/// 374void SchedulePostRATDList::FinishBlock() { 375 if (AntiDepBreak != NULL) 376 AntiDepBreak->FinishBlock(); 377 378 // Call the superclass. 379 ScheduleDAGInstrs::FinishBlock(); 380} 381 382/// StartBlockForKills - Initialize register live-range state for updating kills 383/// 384void SchedulePostRATDList::StartBlockForKills(MachineBasicBlock *BB) { 385 // Initialize the indices to indicate that no registers are live. 386 for (unsigned i = 0; i < TRI->getNumRegs(); ++i) 387 KillIndices[i] = ~0u; 388 389 // Determine the live-out physregs for this block. 390 if (!BB->empty() && BB->back().getDesc().isReturn()) { 391 // In a return block, examine the function live-out regs. 392 for (MachineRegisterInfo::liveout_iterator I = MRI.liveout_begin(), 393 E = MRI.liveout_end(); I != E; ++I) { 394 unsigned Reg = *I; 395 KillIndices[Reg] = BB->size(); 396 // Repeat, for all subregs. 397 for (const unsigned *Subreg = TRI->getSubRegisters(Reg); 398 *Subreg; ++Subreg) { 399 KillIndices[*Subreg] = BB->size(); 400 } 401 } 402 } 403 else { 404 // In a non-return block, examine the live-in regs of all successors. 405 for (MachineBasicBlock::succ_iterator SI = BB->succ_begin(), 406 SE = BB->succ_end(); SI != SE; ++SI) { 407 for (MachineBasicBlock::livein_iterator I = (*SI)->livein_begin(), 408 E = (*SI)->livein_end(); I != E; ++I) { 409 unsigned Reg = *I; 410 KillIndices[Reg] = BB->size(); 411 // Repeat, for all subregs. 412 for (const unsigned *Subreg = TRI->getSubRegisters(Reg); 413 *Subreg; ++Subreg) { 414 KillIndices[*Subreg] = BB->size(); 415 } 416 } 417 } 418 } 419} 420 421bool SchedulePostRATDList::ToggleKillFlag(MachineInstr *MI, 422 MachineOperand &MO) { 423 // Setting kill flag... 424 if (!MO.isKill()) { 425 MO.setIsKill(true); 426 return false; 427 } 428 429 // If MO itself is live, clear the kill flag... 430 if (KillIndices[MO.getReg()] != ~0u) { 431 MO.setIsKill(false); 432 return false; 433 } 434 435 // If any subreg of MO is live, then create an imp-def for that 436 // subreg and keep MO marked as killed. 437 MO.setIsKill(false); 438 bool AllDead = true; 439 const unsigned SuperReg = MO.getReg(); 440 for (const unsigned *Subreg = TRI->getSubRegisters(SuperReg); 441 *Subreg; ++Subreg) { 442 if (KillIndices[*Subreg] != ~0u) { 443 MI->addOperand(MachineOperand::CreateReg(*Subreg, 444 true /*IsDef*/, 445 true /*IsImp*/, 446 false /*IsKill*/, 447 false /*IsDead*/)); 448 AllDead = false; 449 } 450 } 451 452 if(AllDead) 453 MO.setIsKill(true); 454 return false; 455} 456 457/// FixupKills - Fix the register kill flags, they may have been made 458/// incorrect by instruction reordering. 459/// 460void SchedulePostRATDList::FixupKills(MachineBasicBlock *MBB) { 461 DEBUG(dbgs() << "Fixup kills for BB#" << MBB->getNumber() << '\n'); 462 463 std::set<unsigned> killedRegs; 464 BitVector ReservedRegs = TRI->getReservedRegs(MF); 465 466 StartBlockForKills(MBB); 467 468 // Examine block from end to start... 469 unsigned Count = MBB->size(); 470 for (MachineBasicBlock::iterator I = MBB->end(), E = MBB->begin(); 471 I != E; --Count) { 472 MachineInstr *MI = --I; 473 if (MI->isDebugValue()) 474 continue; 475 476 // Update liveness. Registers that are defed but not used in this 477 // instruction are now dead. Mark register and all subregs as they 478 // are completely defined. 479 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 480 MachineOperand &MO = MI->getOperand(i); 481 if (!MO.isReg()) continue; 482 unsigned Reg = MO.getReg(); 483 if (Reg == 0) continue; 484 if (!MO.isDef()) continue; 485 // Ignore two-addr defs. 486 if (MI->isRegTiedToUseOperand(i)) continue; 487 488 KillIndices[Reg] = ~0u; 489 490 // Repeat for all subregs. 491 for (const unsigned *Subreg = TRI->getSubRegisters(Reg); 492 *Subreg; ++Subreg) { 493 KillIndices[*Subreg] = ~0u; 494 } 495 } 496 497 // Examine all used registers and set/clear kill flag. When a 498 // register is used multiple times we only set the kill flag on 499 // the first use. 500 killedRegs.clear(); 501 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 502 MachineOperand &MO = MI->getOperand(i); 503 if (!MO.isReg() || !MO.isUse()) continue; 504 unsigned Reg = MO.getReg(); 505 if ((Reg == 0) || ReservedRegs.test(Reg)) continue; 506 507 bool kill = false; 508 if (killedRegs.find(Reg) == killedRegs.end()) { 509 kill = true; 510 // A register is not killed if any subregs are live... 511 for (const unsigned *Subreg = TRI->getSubRegisters(Reg); 512 *Subreg; ++Subreg) { 513 if (KillIndices[*Subreg] != ~0u) { 514 kill = false; 515 break; 516 } 517 } 518 519 // If subreg is not live, then register is killed if it became 520 // live in this instruction 521 if (kill) 522 kill = (KillIndices[Reg] == ~0u); 523 } 524 525 if (MO.isKill() != kill) { 526 DEBUG(dbgs() << "Fixing " << MO << " in "); 527 // Warning: ToggleKillFlag may invalidate MO. 528 ToggleKillFlag(MI, MO); 529 DEBUG(MI->dump()); 530 } 531 532 killedRegs.insert(Reg); 533 } 534 535 // Mark any used register (that is not using undef) and subregs as 536 // now live... 537 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 538 MachineOperand &MO = MI->getOperand(i); 539 if (!MO.isReg() || !MO.isUse() || MO.isUndef()) continue; 540 unsigned Reg = MO.getReg(); 541 if ((Reg == 0) || ReservedRegs.test(Reg)) continue; 542 543 KillIndices[Reg] = Count; 544 545 for (const unsigned *Subreg = TRI->getSubRegisters(Reg); 546 *Subreg; ++Subreg) { 547 KillIndices[*Subreg] = Count; 548 } 549 } 550 } 551} 552 553//===----------------------------------------------------------------------===// 554// Top-Down Scheduling 555//===----------------------------------------------------------------------===// 556 557/// ReleaseSucc - Decrement the NumPredsLeft count of a successor. Add it to 558/// the PendingQueue if the count reaches zero. Also update its cycle bound. 559void SchedulePostRATDList::ReleaseSucc(SUnit *SU, SDep *SuccEdge) { 560 SUnit *SuccSU = SuccEdge->getSUnit(); 561 562#ifndef NDEBUG 563 if (SuccSU->NumPredsLeft == 0) { 564 dbgs() << "*** Scheduling failed! ***\n"; 565 SuccSU->dump(this); 566 dbgs() << " has been released too many times!\n"; 567 llvm_unreachable(0); 568 } 569#endif 570 --SuccSU->NumPredsLeft; 571 572 // Compute how many cycles it will be before this actually becomes 573 // available. This is the max of the start time of all predecessors plus 574 // their latencies. 575 SuccSU->setDepthToAtLeast(SU->getDepth() + SuccEdge->getLatency()); 576 577 // If all the node's predecessors are scheduled, this node is ready 578 // to be scheduled. Ignore the special ExitSU node. 579 if (SuccSU->NumPredsLeft == 0 && SuccSU != &ExitSU) 580 PendingQueue.push_back(SuccSU); 581} 582 583/// ReleaseSuccessors - Call ReleaseSucc on each of SU's successors. 584void SchedulePostRATDList::ReleaseSuccessors(SUnit *SU) { 585 for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); 586 I != E; ++I) { 587 ReleaseSucc(SU, &*I); 588 } 589} 590 591/// ScheduleNodeTopDown - Add the node to the schedule. Decrement the pending 592/// count of its successors. If a successor pending count is zero, add it to 593/// the Available queue. 594void SchedulePostRATDList::ScheduleNodeTopDown(SUnit *SU, unsigned CurCycle) { 595 DEBUG(dbgs() << "*** Scheduling [" << CurCycle << "]: "); 596 DEBUG(SU->dump(this)); 597 598 Sequence.push_back(SU); 599 assert(CurCycle >= SU->getDepth() && 600 "Node scheduled above its depth!"); 601 SU->setDepthToAtLeast(CurCycle); 602 603 ReleaseSuccessors(SU); 604 SU->isScheduled = true; 605 AvailableQueue.ScheduledNode(SU); 606} 607 608/// ListScheduleTopDown - The main loop of list scheduling for top-down 609/// schedulers. 610void SchedulePostRATDList::ListScheduleTopDown() { 611 unsigned CurCycle = 0; 612 613 // We're scheduling top-down but we're visiting the regions in 614 // bottom-up order, so we don't know the hazards at the start of a 615 // region. So assume no hazards (this should usually be ok as most 616 // blocks are a single region). 617 HazardRec->Reset(); 618 619 // Release any successors of the special Entry node. 620 ReleaseSuccessors(&EntrySU); 621 622 // Add all leaves to Available queue. 623 for (unsigned i = 0, e = SUnits.size(); i != e; ++i) { 624 // It is available if it has no predecessors. 625 bool available = SUnits[i].Preds.empty(); 626 if (available) { 627 AvailableQueue.push(&SUnits[i]); 628 SUnits[i].isAvailable = true; 629 } 630 } 631 632 // In any cycle where we can't schedule any instructions, we must 633 // stall or emit a noop, depending on the target. 634 bool CycleHasInsts = false; 635 636 // While Available queue is not empty, grab the node with the highest 637 // priority. If it is not ready put it back. Schedule the node. 638 std::vector<SUnit*> NotReady; 639 Sequence.reserve(SUnits.size()); 640 while (!AvailableQueue.empty() || !PendingQueue.empty()) { 641 // Check to see if any of the pending instructions are ready to issue. If 642 // so, add them to the available queue. 643 unsigned MinDepth = ~0u; 644 for (unsigned i = 0, e = PendingQueue.size(); i != e; ++i) { 645 if (PendingQueue[i]->getDepth() <= CurCycle) { 646 AvailableQueue.push(PendingQueue[i]); 647 PendingQueue[i]->isAvailable = true; 648 PendingQueue[i] = PendingQueue.back(); 649 PendingQueue.pop_back(); 650 --i; --e; 651 } else if (PendingQueue[i]->getDepth() < MinDepth) 652 MinDepth = PendingQueue[i]->getDepth(); 653 } 654 655 DEBUG(dbgs() << "\n*** Examining Available\n"; 656 LatencyPriorityQueue q = AvailableQueue; 657 while (!q.empty()) { 658 SUnit *su = q.pop(); 659 dbgs() << "Height " << su->getHeight() << ": "; 660 su->dump(this); 661 }); 662 663 SUnit *FoundSUnit = 0; 664 bool HasNoopHazards = false; 665 while (!AvailableQueue.empty()) { 666 SUnit *CurSUnit = AvailableQueue.pop(); 667 668 ScheduleHazardRecognizer::HazardType HT = 669 HazardRec->getHazardType(CurSUnit); 670 if (HT == ScheduleHazardRecognizer::NoHazard) { 671 FoundSUnit = CurSUnit; 672 break; 673 } 674 675 // Remember if this is a noop hazard. 676 HasNoopHazards |= HT == ScheduleHazardRecognizer::NoopHazard; 677 678 NotReady.push_back(CurSUnit); 679 } 680 681 // Add the nodes that aren't ready back onto the available list. 682 if (!NotReady.empty()) { 683 AvailableQueue.push_all(NotReady); 684 NotReady.clear(); 685 } 686 687 // If we found a node to schedule... 688 if (FoundSUnit) { 689 // ... schedule the node... 690 ScheduleNodeTopDown(FoundSUnit, CurCycle); 691 HazardRec->EmitInstruction(FoundSUnit); 692 CycleHasInsts = true; 693 694 // If we are using the target-specific hazards, then don't 695 // advance the cycle time just because we schedule a node. If 696 // the target allows it we can schedule multiple nodes in the 697 // same cycle. 698 if (!EnablePostRAHazardAvoidance) { 699 if (FoundSUnit->Latency) // Don't increment CurCycle for pseudo-ops! 700 ++CurCycle; 701 } 702 } else { 703 if (CycleHasInsts) { 704 DEBUG(dbgs() << "*** Finished cycle " << CurCycle << '\n'); 705 HazardRec->AdvanceCycle(); 706 } else if (!HasNoopHazards) { 707 // Otherwise, we have a pipeline stall, but no other problem, 708 // just advance the current cycle and try again. 709 DEBUG(dbgs() << "*** Stall in cycle " << CurCycle << '\n'); 710 HazardRec->AdvanceCycle(); 711 ++NumStalls; 712 } else { 713 // Otherwise, we have no instructions to issue and we have instructions 714 // that will fault if we don't do this right. This is the case for 715 // processors without pipeline interlocks and other cases. 716 DEBUG(dbgs() << "*** Emitting noop in cycle " << CurCycle << '\n'); 717 HazardRec->EmitNoop(); 718 Sequence.push_back(0); // NULL here means noop 719 ++NumNoops; 720 } 721 722 ++CurCycle; 723 CycleHasInsts = false; 724 } 725 } 726 727#ifndef NDEBUG 728 VerifySchedule(/*isBottomUp=*/false); 729#endif 730} 731 732//===----------------------------------------------------------------------===// 733// Public Constructor Functions 734//===----------------------------------------------------------------------===// 735 736FunctionPass *llvm::createPostRAScheduler(CodeGenOpt::Level OptLevel) { 737 return new PostRAScheduler(OptLevel); 738} 739