1145519Sdarrenr//===----- SchedulePostRAList.cpp - list scheduler ------------------------===// 2145510Sdarrenr// 331183Speter// The LLVM Compiler Infrastructure 431183Speter// 5255332Scy// This file is distributed under the University of Illinois Open Source 631183Speter// License. See LICENSE.TXT for details. 7145510Sdarrenr// 831183Speter//===----------------------------------------------------------------------===// 9255332Scy// 1031183Speter// This implements a top-down list scheduler, using standard algorithms. 1131183Speter// The basic approach uses a priority queue of available nodes to schedule. 1231183Speter// One at a time, nodes are taken from the priority queue (thus in priority 1331183Speter// order), checked for legality to schedule, and emitted if legal. 1431183Speter// 1531183Speter// Nodes may not be legal to schedule either due to structural hazards (e.g. 1631183Speter// pipeline or resource constraints) or because an input to the instruction has 1731183Speter// not completed execution. 1831183Speter// 1931183Speter//===----------------------------------------------------------------------===// 20145510Sdarrenr 2131183Speter#define DEBUG_TYPE "post-RA-sched" 2231183Speter#include "llvm/CodeGen/Passes.h" 2331183Speter#include "AggressiveAntiDepBreaker.h" 2431183Speter#include "AntiDepBreaker.h" 2531183Speter#include "CriticalAntiDepBreaker.h" 2631183Speter#include "llvm/ADT/BitVector.h" 2731183Speter#include "llvm/ADT/Statistic.h" 2831183Speter#include "llvm/Analysis/AliasAnalysis.h" 2960841Sdarrenr#include "llvm/CodeGen/LatencyPriorityQueue.h" 3031183Speter#include "llvm/CodeGen/MachineDominators.h" 3131183Speter#include "llvm/CodeGen/MachineFrameInfo.h" 32369245Sgit2svn#include "llvm/CodeGen/MachineFunctionPass.h" 33369245Sgit2svn#include "llvm/CodeGen/MachineInstrBuilder.h" 34369245Sgit2svn#include "llvm/CodeGen/MachineLoopInfo.h" 35369245Sgit2svn#include "llvm/CodeGen/MachineRegisterInfo.h" 36369245Sgit2svn#include "llvm/CodeGen/RegisterClassInfo.h" 37369245Sgit2svn#include "llvm/CodeGen/ScheduleDAGInstrs.h" 38369245Sgit2svn#include "llvm/CodeGen/ScheduleHazardRecognizer.h" 39369245Sgit2svn#include "llvm/CodeGen/SchedulerRegistry.h" 4037074Speter#include "llvm/Support/CommandLine.h" 41145510Sdarrenr#include "llvm/Support/Debug.h" 4237074Speter#include "llvm/Support/ErrorHandling.h" 4337074Speter#include "llvm/Support/raw_ostream.h" 4437074Speter#include "llvm/Target/TargetInstrInfo.h" 4537074Speter#include "llvm/Target/TargetLowering.h" 4637074Speter#include "llvm/Target/TargetMachine.h" 47145510Sdarrenr#include "llvm/Target/TargetRegisterInfo.h" 4837074Speter#include "llvm/Target/TargetSubtargetInfo.h" 4937074Speterusing namespace llvm; 5037074Speter 5137074SpeterSTATISTIC(NumNoops, "Number of noops inserted"); 5237074SpeterSTATISTIC(NumStalls, "Number of pipeline stalls"); 5337074SpeterSTATISTIC(NumFixedAnti, "Number of fixed anti-dependencies"); 5437074Speter 5537074Speter// Post-RA scheduling is enabled with 5637074Speter// TargetSubtargetInfo.enablePostRAScheduler(). This flag can be used to 5737074Speter// override the target. 5837074Speterstatic cl::opt<bool> 5937074SpeterEnablePostRAScheduler("post-RA-scheduler", 6037074Speter cl::desc("Enable scheduling after register allocation"), 6137074Speter cl::init(false), cl::Hidden); 6237074Speterstatic cl::opt<std::string> 6337074SpeterEnableAntiDepBreaking("break-anti-dependencies", 6437074Speter cl::desc("Break post-RA scheduling anti-dependencies: " 6537074Speter "\"critical\", \"all\", or \"none\""), 6637074Speter cl::init("none"), cl::Hidden); 6737074Speter 6837074Speter// If DebugDiv > 0 then only schedule MBB with (ID % DebugDiv) == DebugMod 6937074Speterstatic cl::opt<int> 7037074SpeterDebugDiv("postra-sched-debugdiv", 7137074Speter cl::desc("Debug control MBBs that are scheduled"), 7237074Speter cl::init(0), cl::Hidden); 7337074Speterstatic cl::opt<int> 7437074SpeterDebugMod("postra-sched-debugmod", 7537074Speter cl::desc("Debug control MBBs that are scheduled"), 7637074Speter cl::init(0), cl::Hidden); 7737074Speter 7837074SpeterAntiDepBreaker::~AntiDepBreaker() { } 7937074Speter 8037074Speternamespace { 8137074Speter class PostRAScheduler : public MachineFunctionPass { 8237074Speter const TargetInstrInfo *TII; 8337074Speter RegisterClassInfo RegClassInfo; 8437074Speter 8537074Speter public: 8637074Speter static char ID; 8737074Speter PostRAScheduler() : MachineFunctionPass(ID) {} 8837074Speter 8937074Speter void getAnalysisUsage(AnalysisUsage &AU) const { 9037074Speter AU.setPreservesCFG(); 9137074Speter AU.addRequired<AliasAnalysis>(); 9237074Speter AU.addRequired<TargetPassConfig>(); 9337074Speter AU.addRequired<MachineDominatorTree>(); 9437074Speter AU.addPreserved<MachineDominatorTree>(); 9537074Speter AU.addRequired<MachineLoopInfo>(); 9637074Speter AU.addPreserved<MachineLoopInfo>(); 9737074Speter MachineFunctionPass::getAnalysisUsage(AU); 9837074Speter } 9937074Speter 10037074Speter bool runOnMachineFunction(MachineFunction &Fn); 10137074Speter }; 10237074Speter char PostRAScheduler::ID = 0; 10337074Speter 10437074Speter class SchedulePostRATDList : public ScheduleDAGInstrs { 10537074Speter /// AvailableQueue - The priority queue to use for the available SUnits. 10637074Speter /// 10737074Speter LatencyPriorityQueue AvailableQueue; 10837074Speter 10937074Speter /// PendingQueue - This contains all of the instructions whose operands have 11037074Speter /// been issued, but their results are not ready yet (due to the latency of 11137074Speter /// the operation). Once the operands becomes available, the instruction is 11237074Speter /// added to the AvailableQueue. 11337074Speter std::vector<SUnit*> PendingQueue; 11437074Speter 11537074Speter /// HazardRec - The hazard recognizer to use. 11637074Speter ScheduleHazardRecognizer *HazardRec; 11737074Speter 11837074Speter /// AntiDepBreak - Anti-dependence breaking object, or NULL if none 11937074Speter AntiDepBreaker *AntiDepBreak; 12037074Speter 12137074Speter /// AA - AliasAnalysis for making memory reference queries. 12237074Speter AliasAnalysis *AA; 12337074Speter 12437074Speter /// LiveRegs - true if the register is live. 12537074Speter BitVector LiveRegs; 12637074Speter 12737074Speter /// The schedule. Null SUnit*'s represent noop instructions. 12837074Speter std::vector<SUnit*> Sequence; 12937074Speter 13037074Speter /// The index in BB of RegionEnd. 13137074Speter /// 13237074Speter /// This is the instruction number from the top of the current block, not 13337074Speter /// the SlotIndex. It is only used by the AntiDepBreaker. 13437074Speter unsigned EndIndex; 13537074Speter 13637074Speter public: 13737074Speter SchedulePostRATDList( 13837074Speter MachineFunction &MF, MachineLoopInfo &MLI, MachineDominatorTree &MDT, 13937074Speter AliasAnalysis *AA, const RegisterClassInfo&, 14037074Speter TargetSubtargetInfo::AntiDepBreakMode AntiDepMode, 14137074Speter SmallVectorImpl<const TargetRegisterClass*> &CriticalPathRCs); 14237074Speter 14337074Speter ~SchedulePostRATDList(); 14437074Speter 14537074Speter /// startBlock - Initialize register live-range state for scheduling in 14637074Speter /// this block. 14737074Speter /// 14837074Speter void startBlock(MachineBasicBlock *BB); 14937074Speter 15037074Speter // Set the index of RegionEnd within the current BB. 15137074Speter void setEndIndex(unsigned EndIdx) { EndIndex = EndIdx; } 15237074Speter 15337074Speter /// Initialize the scheduler state for the next scheduling region. 15437074Speter virtual void enterRegion(MachineBasicBlock *bb, 15537074Speter MachineBasicBlock::iterator begin, 15637074Speter MachineBasicBlock::iterator end, 15737074Speter unsigned regioninstrs); 15837074Speter 15937074Speter /// Notify that the scheduler has finished scheduling the current region. 16037074Speter virtual void exitRegion(); 16137074Speter 16237074Speter /// Schedule - Schedule the instruction range using list scheduling. 16337074Speter /// 16431183Speter void schedule(); 16537074Speter 16631183Speter void EmitSchedule(); 16737074Speter 16831183Speter /// Observe - Update liveness information to account for the current 16931183Speter /// instruction, which will not be scheduled. 17031183Speter /// 17131183Speter void Observe(MachineInstr *MI, unsigned Count); 17231183Speter 17331183Speter /// finishBlock - Clean up register live-range state. 17431183Speter /// 17531183Speter void finishBlock(); 17637074Speter 17731183Speter /// FixupKills - Fix register kill flags that have been made 17831183Speter /// invalid due to scheduling 17931183Speter /// 18031183Speter void FixupKills(MachineBasicBlock *MBB); 18131183Speter 18231183Speter private: 18331183Speter void ReleaseSucc(SUnit *SU, SDep *SuccEdge); 18431183Speter void ReleaseSuccessors(SUnit *SU); 18531183Speter void ScheduleNodeTopDown(SUnit *SU, unsigned CurCycle); 18631183Speter void ListScheduleTopDown(); 18731183Speter void StartBlockForKills(MachineBasicBlock *BB); 18831183Speter 18931183Speter // ToggleKillFlag - Toggle a register operand kill flag. Other 19031183Speter // adjustments may be made to the instruction if necessary. Return 19131183Speter // true if the operand has been deleted, false if not. 19231183Speter bool ToggleKillFlag(MachineInstr *MI, MachineOperand &MO); 19331183Speter 194319175Scy void dumpSchedule() const; 195319175Scy }; 19660841Sdarrenr} 19731183Speter 19831183Speterchar &llvm::PostRASchedulerID = PostRAScheduler::ID; 19931183Speter 20031183SpeterINITIALIZE_PASS(PostRAScheduler, "post-RA-sched", 20131183Speter "Post RA top-down list latency scheduler", false, false) 20231183Speter 20360841SdarrenrSchedulePostRATDList::SchedulePostRATDList( 20431183Speter MachineFunction &MF, MachineLoopInfo &MLI, MachineDominatorTree &MDT, 20531183Speter AliasAnalysis *AA, const RegisterClassInfo &RCI, 20631183Speter TargetSubtargetInfo::AntiDepBreakMode AntiDepMode, 20731183Speter SmallVectorImpl<const TargetRegisterClass*> &CriticalPathRCs) 20831183Speter : ScheduleDAGInstrs(MF, MLI, MDT, /*IsPostRA=*/true), AA(AA), 20931183Speter LiveRegs(TRI->getNumRegs()), EndIndex(0) 21031183Speter{ 21131183Speter const TargetMachine &TM = MF.getTarget(); 21231183Speter const InstrItineraryData *InstrItins = TM.getInstrItineraryData(); 21331183Speter HazardRec = 21431183Speter TM.getInstrInfo()->CreateTargetPostRAHazardRecognizer(InstrItins, this); 21531183Speter 216145510Sdarrenr assert((AntiDepMode == TargetSubtargetInfo::ANTIDEP_NONE || 21731183Speter MRI.tracksLiveness()) && 21831183Speter "Live-ins must be accurate for anti-dependency breaking"); 21931183Speter AntiDepBreak = 22031183Speter ((AntiDepMode == TargetSubtargetInfo::ANTIDEP_ALL) ? 22131183Speter (AntiDepBreaker *)new AggressiveAntiDepBreaker(MF, RCI, CriticalPathRCs) : 22231183Speter ((AntiDepMode == TargetSubtargetInfo::ANTIDEP_CRITICAL) ? 22331183Speter (AntiDepBreaker *)new CriticalAntiDepBreaker(MF, RCI) : NULL)); 224145510Sdarrenr} 22537074Speter 22637074SpeterSchedulePostRATDList::~SchedulePostRATDList() { 22737074Speter delete HazardRec; 22831183Speter delete AntiDepBreak; 22931183Speter} 23031183Speter 23131183Speter/// Initialize state associated with the next scheduling region. 23237074Spetervoid SchedulePostRATDList::enterRegion(MachineBasicBlock *bb, 23337074Speter MachineBasicBlock::iterator begin, 23437074Speter MachineBasicBlock::iterator end, 235145510Sdarrenr unsigned regioninstrs) { 23637074Speter ScheduleDAGInstrs::enterRegion(bb, begin, end, regioninstrs); 23737074Speter Sequence.clear(); 23837074Speter} 23931183Speter 24031183Speter/// Print the schedule before exiting the region. 241145510Sdarrenrvoid SchedulePostRATDList::exitRegion() { 24231183Speter DEBUG({ 24331183Speter dbgs() << "*** Final schedule ***\n"; 24431183Speter dumpSchedule(); 24531183Speter dbgs() << '\n'; 24631183Speter }); 24731183Speter ScheduleDAGInstrs::exitRegion(); 24831183Speter} 24931183Speter 25031183Speter#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 25131183Speter/// dumpSchedule - dump the scheduled Sequence. 25231183Spetervoid SchedulePostRATDList::dumpSchedule() const { 25331183Speter for (unsigned i = 0, e = Sequence.size(); i != e; i++) { 25431183Speter if (SUnit *SU = Sequence[i]) 25531183Speter SU->dump(this); 25631183Speter else 25731183Speter dbgs() << "**** NOOP ****\n"; 25831183Speter } 25931183Speter} 26031183Speter#endif 26160841Sdarrenr 26260841Sdarrenrbool PostRAScheduler::runOnMachineFunction(MachineFunction &Fn) { 26331183Speter TII = Fn.getTarget().getInstrInfo(); 26431183Speter MachineLoopInfo &MLI = getAnalysis<MachineLoopInfo>(); 26560841Sdarrenr MachineDominatorTree &MDT = getAnalysis<MachineDominatorTree>(); 26631183Speter AliasAnalysis *AA = &getAnalysis<AliasAnalysis>(); 26760841Sdarrenr TargetPassConfig *PassConfig = &getAnalysis<TargetPassConfig>(); 26831183Speter 26960841Sdarrenr RegClassInfo.runOnMachineFunction(Fn); 27031183Speter 27131183Speter // Check for explicit enable/disable of post-ra scheduling. 27231183Speter TargetSubtargetInfo::AntiDepBreakMode AntiDepMode = 27360841Sdarrenr TargetSubtargetInfo::ANTIDEP_NONE; 27431183Speter SmallVector<const TargetRegisterClass*, 4> CriticalPathRCs; 27560841Sdarrenr if (EnablePostRAScheduler.getPosition() > 0) { 27631183Speter if (!EnablePostRAScheduler) 27731183Speter return false; 27831183Speter } else { 27960841Sdarrenr // Check that post-RA scheduling is enabled for this target. 28031183Speter // This may upgrade the AntiDepMode. 28131183Speter const TargetSubtargetInfo &ST = Fn.getTarget().getSubtarget<TargetSubtargetInfo>(); 28231183Speter if (!ST.enablePostRAScheduler(PassConfig->getOptLevel(), AntiDepMode, 28360841Sdarrenr CriticalPathRCs)) 28431183Speter return false; 28531183Speter } 28631183Speter 28760841Sdarrenr // Check for antidep breaking override... 28831183Speter if (EnableAntiDepBreaking.getPosition() > 0) { 28931183Speter AntiDepMode = (EnableAntiDepBreaking == "all") 29031183Speter ? TargetSubtargetInfo::ANTIDEP_ALL 29160841Sdarrenr : ((EnableAntiDepBreaking == "critical") 29231183Speter ? TargetSubtargetInfo::ANTIDEP_CRITICAL 29360841Sdarrenr : TargetSubtargetInfo::ANTIDEP_NONE); 29431183Speter } 29531183Speter 29631183Speter DEBUG(dbgs() << "PostRAScheduler\n"); 29760841Sdarrenr 29831183Speter SchedulePostRATDList Scheduler(Fn, MLI, MDT, AA, RegClassInfo, AntiDepMode, 29960841Sdarrenr CriticalPathRCs); 30031183Speter 30131183Speter // Loop over all of the basic blocks 30231183Speter for (MachineFunction::iterator MBB = Fn.begin(), MBBe = Fn.end(); 30331183Speter MBB != MBBe; ++MBB) { 30431183Speter#ifndef NDEBUG 30531183Speter // If DebugDiv > 0 then only schedule MBB with (ID % DebugDiv) == DebugMod 30631183Speter if (DebugDiv > 0) { 30731183Speter static int bbcnt = 0; 30831183Speter if (bbcnt++ % DebugDiv != DebugMod) 30953024Sguido continue; 31031183Speter dbgs() << "*** DEBUG scheduling " << Fn.getName() 31153024Sguido << ":BB#" << MBB->getNumber() << " ***\n"; 31253024Sguido } 31331183Speter#endif 31431183Speter 31531183Speter // Initialize register live-range state for scheduling in this block. 31631183Speter Scheduler.startBlock(MBB); 317130887Sdarrenr 318130887Sdarrenr // Schedule each sequence of instructions not interrupted by a label 31931183Speter // or anything else that effectively needs to shut down scheduling. 320 MachineBasicBlock::iterator Current = MBB->end(); 321 unsigned Count = MBB->size(), CurrentCount = Count; 322 for (MachineBasicBlock::iterator I = Current; I != MBB->begin(); ) { 323 MachineInstr *MI = llvm::prior(I); 324 --Count; 325 // Calls are not scheduling boundaries before register allocation, but 326 // post-ra we don't gain anything by scheduling across calls since we 327 // don't need to worry about register pressure. 328 if (MI->isCall() || TII->isSchedulingBoundary(MI, MBB, Fn)) { 329 Scheduler.enterRegion(MBB, I, Current, CurrentCount - Count); 330 Scheduler.setEndIndex(CurrentCount); 331 Scheduler.schedule(); 332 Scheduler.exitRegion(); 333 Scheduler.EmitSchedule(); 334 Current = MI; 335 CurrentCount = Count; 336 Scheduler.Observe(MI, CurrentCount); 337 } 338 I = MI; 339 if (MI->isBundle()) 340 Count -= MI->getBundleSize(); 341 } 342 assert(Count == 0 && "Instruction count mismatch!"); 343 assert((MBB->begin() == Current || CurrentCount != 0) && 344 "Instruction count mismatch!"); 345 Scheduler.enterRegion(MBB, MBB->begin(), Current, CurrentCount); 346 Scheduler.setEndIndex(CurrentCount); 347 Scheduler.schedule(); 348 Scheduler.exitRegion(); 349 Scheduler.EmitSchedule(); 350 351 // Clean up register live-range state. 352 Scheduler.finishBlock(); 353 354 // Update register kills 355 Scheduler.FixupKills(MBB); 356 } 357 358 return true; 359} 360 361/// StartBlock - Initialize register live-range state for scheduling in 362/// this block. 363/// 364void SchedulePostRATDList::startBlock(MachineBasicBlock *BB) { 365 // Call the superclass. 366 ScheduleDAGInstrs::startBlock(BB); 367 368 // Reset the hazard recognizer and anti-dep breaker. 369 HazardRec->Reset(); 370 if (AntiDepBreak != NULL) 371 AntiDepBreak->StartBlock(BB); 372} 373 374/// Schedule - Schedule the instruction range using list scheduling. 375/// 376void SchedulePostRATDList::schedule() { 377 // Build the scheduling graph. 378 buildSchedGraph(AA); 379 380 if (AntiDepBreak != NULL) { 381 unsigned Broken = 382 AntiDepBreak->BreakAntiDependencies(SUnits, RegionBegin, RegionEnd, 383 EndIndex, DbgValues); 384 385 if (Broken != 0) { 386 // We made changes. Update the dependency graph. 387 // Theoretically we could update the graph in place: 388 // When a live range is changed to use a different register, remove 389 // the def's anti-dependence *and* output-dependence edges due to 390 // that register, and add new anti-dependence and output-dependence 391 // edges based on the next live range of the register. 392 ScheduleDAG::clearDAG(); 393 buildSchedGraph(AA); 394 395 NumFixedAnti += Broken; 396 } 397 } 398 399 DEBUG(dbgs() << "********** List Scheduling **********\n"); 400 DEBUG(for (unsigned su = 0, e = SUnits.size(); su != e; ++su) 401 SUnits[su].dumpAll(this)); 402 403 AvailableQueue.initNodes(SUnits); 404 ListScheduleTopDown(); 405 AvailableQueue.releaseState(); 406} 407 408/// Observe - Update liveness information to account for the current 409/// instruction, which will not be scheduled. 410/// 411void SchedulePostRATDList::Observe(MachineInstr *MI, unsigned Count) { 412 if (AntiDepBreak != NULL) 413 AntiDepBreak->Observe(MI, Count, EndIndex); 414} 415 416/// FinishBlock - Clean up register live-range state. 417/// 418void SchedulePostRATDList::finishBlock() { 419 if (AntiDepBreak != NULL) 420 AntiDepBreak->FinishBlock(); 421 422 // Call the superclass. 423 ScheduleDAGInstrs::finishBlock(); 424} 425 426/// StartBlockForKills - Initialize register live-range state for updating kills 427/// 428void SchedulePostRATDList::StartBlockForKills(MachineBasicBlock *BB) { 429 // Start with no live registers. 430 LiveRegs.reset(); 431 432 // Examine the live-in regs of all successors. 433 for (MachineBasicBlock::succ_iterator SI = BB->succ_begin(), 434 SE = BB->succ_end(); SI != SE; ++SI) { 435 for (MachineBasicBlock::livein_iterator I = (*SI)->livein_begin(), 436 E = (*SI)->livein_end(); I != E; ++I) { 437 unsigned Reg = *I; 438 // Repeat, for reg and all subregs. 439 for (MCSubRegIterator SubRegs(Reg, TRI, /*IncludeSelf=*/true); 440 SubRegs.isValid(); ++SubRegs) 441 LiveRegs.set(*SubRegs); 442 } 443 } 444} 445 446bool SchedulePostRATDList::ToggleKillFlag(MachineInstr *MI, 447 MachineOperand &MO) { 448 // Setting kill flag... 449 if (!MO.isKill()) { 450 MO.setIsKill(true); 451 return false; 452 } 453 454 // If MO itself is live, clear the kill flag... 455 if (LiveRegs.test(MO.getReg())) { 456 MO.setIsKill(false); 457 return false; 458 } 459 460 // If any subreg of MO is live, then create an imp-def for that 461 // subreg and keep MO marked as killed. 462 MO.setIsKill(false); 463 bool AllDead = true; 464 const unsigned SuperReg = MO.getReg(); 465 MachineInstrBuilder MIB(MF, MI); 466 for (MCSubRegIterator SubRegs(SuperReg, TRI); SubRegs.isValid(); ++SubRegs) { 467 if (LiveRegs.test(*SubRegs)) { 468 MIB.addReg(*SubRegs, RegState::ImplicitDefine); 469 AllDead = false; 470 } 471 } 472 473 if(AllDead) 474 MO.setIsKill(true); 475 return false; 476} 477 478/// FixupKills - Fix the register kill flags, they may have been made 479/// incorrect by instruction reordering. 480/// 481void SchedulePostRATDList::FixupKills(MachineBasicBlock *MBB) { 482 DEBUG(dbgs() << "Fixup kills for BB#" << MBB->getNumber() << '\n'); 483 484 BitVector killedRegs(TRI->getNumRegs()); 485 486 StartBlockForKills(MBB); 487 488 // Examine block from end to start... 489 unsigned Count = MBB->size(); 490 for (MachineBasicBlock::iterator I = MBB->end(), E = MBB->begin(); 491 I != E; --Count) { 492 MachineInstr *MI = --I; 493 if (MI->isDebugValue()) 494 continue; 495 496 // Update liveness. Registers that are defed but not used in this 497 // instruction are now dead. Mark register and all subregs as they 498 // are completely defined. 499 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 500 MachineOperand &MO = MI->getOperand(i); 501 if (MO.isRegMask()) 502 LiveRegs.clearBitsNotInMask(MO.getRegMask()); 503 if (!MO.isReg()) continue; 504 unsigned Reg = MO.getReg(); 505 if (Reg == 0) continue; 506 if (!MO.isDef()) continue; 507 // Ignore two-addr defs. 508 if (MI->isRegTiedToUseOperand(i)) continue; 509 510 // Repeat for reg and all subregs. 511 for (MCSubRegIterator SubRegs(Reg, TRI, /*IncludeSelf=*/true); 512 SubRegs.isValid(); ++SubRegs) 513 LiveRegs.reset(*SubRegs); 514 } 515 516 // Examine all used registers and set/clear kill flag. When a 517 // register is used multiple times we only set the kill flag on 518 // the first use. Don't set kill flags on undef operands. 519 killedRegs.reset(); 520 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 521 MachineOperand &MO = MI->getOperand(i); 522 if (!MO.isReg() || !MO.isUse() || MO.isUndef()) continue; 523 unsigned Reg = MO.getReg(); 524 if ((Reg == 0) || MRI.isReserved(Reg)) continue; 525 526 bool kill = false; 527 if (!killedRegs.test(Reg)) { 528 kill = true; 529 // A register is not killed if any subregs are live... 530 for (MCSubRegIterator SubRegs(Reg, TRI); SubRegs.isValid(); ++SubRegs) { 531 if (LiveRegs.test(*SubRegs)) { 532 kill = false; 533 break; 534 } 535 } 536 537 // If subreg is not live, then register is killed if it became 538 // live in this instruction 539 if (kill) 540 kill = !LiveRegs.test(Reg); 541 } 542 543 if (MO.isKill() != kill) { 544 DEBUG(dbgs() << "Fixing " << MO << " in "); 545 // Warning: ToggleKillFlag may invalidate MO. 546 ToggleKillFlag(MI, MO); 547 DEBUG(MI->dump()); 548 } 549 550 killedRegs.set(Reg); 551 } 552 553 // Mark any used register (that is not using undef) and subregs as 554 // now live... 555 for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i) { 556 MachineOperand &MO = MI->getOperand(i); 557 if (!MO.isReg() || !MO.isUse() || MO.isUndef()) continue; 558 unsigned Reg = MO.getReg(); 559 if ((Reg == 0) || MRI.isReserved(Reg)) continue; 560 561 for (MCSubRegIterator SubRegs(Reg, TRI, /*IncludeSelf=*/true); 562 SubRegs.isValid(); ++SubRegs) 563 LiveRegs.set(*SubRegs); 564 } 565 } 566} 567 568//===----------------------------------------------------------------------===// 569// Top-Down Scheduling 570//===----------------------------------------------------------------------===// 571 572/// ReleaseSucc - Decrement the NumPredsLeft count of a successor. Add it to 573/// the PendingQueue if the count reaches zero. 574void SchedulePostRATDList::ReleaseSucc(SUnit *SU, SDep *SuccEdge) { 575 SUnit *SuccSU = SuccEdge->getSUnit(); 576 577 if (SuccEdge->isWeak()) { 578 --SuccSU->WeakPredsLeft; 579 return; 580 } 581#ifndef NDEBUG 582 if (SuccSU->NumPredsLeft == 0) { 583 dbgs() << "*** Scheduling failed! ***\n"; 584 SuccSU->dump(this); 585 dbgs() << " has been released too many times!\n"; 586 llvm_unreachable(0); 587 } 588#endif 589 --SuccSU->NumPredsLeft; 590 591 // Standard scheduler algorithms will recompute the depth of the successor 592 // here as such: 593 // SuccSU->setDepthToAtLeast(SU->getDepth() + SuccEdge->getLatency()); 594 // 595 // However, we lazily compute node depth instead. Note that 596 // ScheduleNodeTopDown has already updated the depth of this node which causes 597 // all descendents to be marked dirty. Setting the successor depth explicitly 598 // here would cause depth to be recomputed for all its ancestors. If the 599 // successor is not yet ready (because of a transitively redundant edge) then 600 // this causes depth computation to be quadratic in the size of the DAG. 601 602 // If all the node's predecessors are scheduled, this node is ready 603 // to be scheduled. Ignore the special ExitSU node. 604 if (SuccSU->NumPredsLeft == 0 && SuccSU != &ExitSU) 605 PendingQueue.push_back(SuccSU); 606} 607 608/// ReleaseSuccessors - Call ReleaseSucc on each of SU's successors. 609void SchedulePostRATDList::ReleaseSuccessors(SUnit *SU) { 610 for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); 611 I != E; ++I) { 612 ReleaseSucc(SU, &*I); 613 } 614} 615 616/// ScheduleNodeTopDown - Add the node to the schedule. Decrement the pending 617/// count of its successors. If a successor pending count is zero, add it to 618/// the Available queue. 619void SchedulePostRATDList::ScheduleNodeTopDown(SUnit *SU, unsigned CurCycle) { 620 DEBUG(dbgs() << "*** Scheduling [" << CurCycle << "]: "); 621 DEBUG(SU->dump(this)); 622 623 Sequence.push_back(SU); 624 assert(CurCycle >= SU->getDepth() && 625 "Node scheduled above its depth!"); 626 SU->setDepthToAtLeast(CurCycle); 627 628 ReleaseSuccessors(SU); 629 SU->isScheduled = true; 630 AvailableQueue.scheduledNode(SU); 631} 632 633/// ListScheduleTopDown - The main loop of list scheduling for top-down 634/// schedulers. 635void SchedulePostRATDList::ListScheduleTopDown() { 636 unsigned CurCycle = 0; 637 638 // We're scheduling top-down but we're visiting the regions in 639 // bottom-up order, so we don't know the hazards at the start of a 640 // region. So assume no hazards (this should usually be ok as most 641 // blocks are a single region). 642 HazardRec->Reset(); 643 644 // Release any successors of the special Entry node. 645 ReleaseSuccessors(&EntrySU); 646 647 // Add all leaves to Available queue. 648 for (unsigned i = 0, e = SUnits.size(); i != e; ++i) { 649 // It is available if it has no predecessors. 650 if (!SUnits[i].NumPredsLeft && !SUnits[i].isAvailable) { 651 AvailableQueue.push(&SUnits[i]); 652 SUnits[i].isAvailable = true; 653 } 654 } 655 656 // In any cycle where we can't schedule any instructions, we must 657 // stall or emit a noop, depending on the target. 658 bool CycleHasInsts = false; 659 660 // While Available queue is not empty, grab the node with the highest 661 // priority. If it is not ready put it back. Schedule the node. 662 std::vector<SUnit*> NotReady; 663 Sequence.reserve(SUnits.size()); 664 while (!AvailableQueue.empty() || !PendingQueue.empty()) { 665 // Check to see if any of the pending instructions are ready to issue. If 666 // so, add them to the available queue. 667 unsigned MinDepth = ~0u; 668 for (unsigned i = 0, e = PendingQueue.size(); i != e; ++i) { 669 if (PendingQueue[i]->getDepth() <= CurCycle) { 670 AvailableQueue.push(PendingQueue[i]); 671 PendingQueue[i]->isAvailable = true; 672 PendingQueue[i] = PendingQueue.back(); 673 PendingQueue.pop_back(); 674 --i; --e; 675 } else if (PendingQueue[i]->getDepth() < MinDepth) 676 MinDepth = PendingQueue[i]->getDepth(); 677 } 678 679 DEBUG(dbgs() << "\n*** Examining Available\n"; AvailableQueue.dump(this)); 680 681 SUnit *FoundSUnit = 0; 682 bool HasNoopHazards = false; 683 while (!AvailableQueue.empty()) { 684 SUnit *CurSUnit = AvailableQueue.pop(); 685 686 ScheduleHazardRecognizer::HazardType HT = 687 HazardRec->getHazardType(CurSUnit, 0/*no stalls*/); 688 if (HT == ScheduleHazardRecognizer::NoHazard) { 689 FoundSUnit = CurSUnit; 690 break; 691 } 692 693 // Remember if this is a noop hazard. 694 HasNoopHazards |= HT == ScheduleHazardRecognizer::NoopHazard; 695 696 NotReady.push_back(CurSUnit); 697 } 698 699 // Add the nodes that aren't ready back onto the available list. 700 if (!NotReady.empty()) { 701 AvailableQueue.push_all(NotReady); 702 NotReady.clear(); 703 } 704 705 // If we found a node to schedule... 706 if (FoundSUnit) { 707 // ... schedule the node... 708 ScheduleNodeTopDown(FoundSUnit, CurCycle); 709 HazardRec->EmitInstruction(FoundSUnit); 710 CycleHasInsts = true; 711 if (HazardRec->atIssueLimit()) { 712 DEBUG(dbgs() << "*** Max instructions per cycle " << CurCycle << '\n'); 713 HazardRec->AdvanceCycle(); 714 ++CurCycle; 715 CycleHasInsts = false; 716 } 717 } else { 718 if (CycleHasInsts) { 719 DEBUG(dbgs() << "*** Finished cycle " << CurCycle << '\n'); 720 HazardRec->AdvanceCycle(); 721 } else if (!HasNoopHazards) { 722 // Otherwise, we have a pipeline stall, but no other problem, 723 // just advance the current cycle and try again. 724 DEBUG(dbgs() << "*** Stall in cycle " << CurCycle << '\n'); 725 HazardRec->AdvanceCycle(); 726 ++NumStalls; 727 } else { 728 // Otherwise, we have no instructions to issue and we have instructions 729 // that will fault if we don't do this right. This is the case for 730 // processors without pipeline interlocks and other cases. 731 DEBUG(dbgs() << "*** Emitting noop in cycle " << CurCycle << '\n'); 732 HazardRec->EmitNoop(); 733 Sequence.push_back(0); // NULL here means noop 734 ++NumNoops; 735 } 736 737 ++CurCycle; 738 CycleHasInsts = false; 739 } 740 } 741 742#ifndef NDEBUG 743 unsigned ScheduledNodes = VerifyScheduledDAG(/*isBottomUp=*/false); 744 unsigned Noops = 0; 745 for (unsigned i = 0, e = Sequence.size(); i != e; ++i) 746 if (!Sequence[i]) 747 ++Noops; 748 assert(Sequence.size() - Noops == ScheduledNodes && 749 "The number of nodes scheduled doesn't match the expected number!"); 750#endif // NDEBUG 751} 752 753// EmitSchedule - Emit the machine code in scheduled order. 754void SchedulePostRATDList::EmitSchedule() { 755 RegionBegin = RegionEnd; 756 757 // If first instruction was a DBG_VALUE then put it back. 758 if (FirstDbgValue) 759 BB->splice(RegionEnd, BB, FirstDbgValue); 760 761 // Then re-insert them according to the given schedule. 762 for (unsigned i = 0, e = Sequence.size(); i != e; i++) { 763 if (SUnit *SU = Sequence[i]) 764 BB->splice(RegionEnd, BB, SU->getInstr()); 765 else 766 // Null SUnit* is a noop. 767 TII->insertNoop(*BB, RegionEnd); 768 769 // Update the Begin iterator, as the first instruction in the block 770 // may have been scheduled later. 771 if (i == 0) 772 RegionBegin = prior(RegionEnd); 773 } 774 775 // Reinsert any remaining debug_values. 776 for (std::vector<std::pair<MachineInstr *, MachineInstr *> >::iterator 777 DI = DbgValues.end(), DE = DbgValues.begin(); DI != DE; --DI) { 778 std::pair<MachineInstr *, MachineInstr *> P = *prior(DI); 779 MachineInstr *DbgValue = P.first; 780 MachineBasicBlock::iterator OrigPrivMI = P.second; 781 BB->splice(++OrigPrivMI, BB, DbgValue); 782 } 783 DbgValues.clear(); 784 FirstDbgValue = NULL; 785} 786