MachineScheduler.cpp revision 3d6e70c857ded2605699f7de1b18269f4fb390bf
1//===- MachineScheduler.cpp - Machine Instruction 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// MachineScheduler schedules machine instructions after phi elimination. It 11// preserves LiveIntervals so it can be invoked before register allocation. 12// 13//===----------------------------------------------------------------------===// 14 15#define DEBUG_TYPE "misched" 16 17#include "llvm/CodeGen/MachineScheduler.h" 18#include "llvm/ADT/OwningPtr.h" 19#include "llvm/ADT/PriorityQueue.h" 20#include "llvm/Analysis/AliasAnalysis.h" 21#include "llvm/CodeGen/LiveIntervalAnalysis.h" 22#include "llvm/CodeGen/MachineDominators.h" 23#include "llvm/CodeGen/MachineLoopInfo.h" 24#include "llvm/CodeGen/MachineRegisterInfo.h" 25#include "llvm/CodeGen/Passes.h" 26#include "llvm/CodeGen/RegisterClassInfo.h" 27#include "llvm/CodeGen/ScheduleDFS.h" 28#include "llvm/CodeGen/ScheduleHazardRecognizer.h" 29#include "llvm/Support/CommandLine.h" 30#include "llvm/Support/Debug.h" 31#include "llvm/Support/ErrorHandling.h" 32#include "llvm/Support/GraphWriter.h" 33#include "llvm/Support/raw_ostream.h" 34#include "llvm/Target/TargetInstrInfo.h" 35#include <queue> 36 37using namespace llvm; 38 39namespace llvm { 40cl::opt<bool> ForceTopDown("misched-topdown", cl::Hidden, 41 cl::desc("Force top-down list scheduling")); 42cl::opt<bool> ForceBottomUp("misched-bottomup", cl::Hidden, 43 cl::desc("Force bottom-up list scheduling")); 44} 45 46#ifndef NDEBUG 47static cl::opt<bool> ViewMISchedDAGs("view-misched-dags", cl::Hidden, 48 cl::desc("Pop up a window to show MISched dags after they are processed")); 49 50static cl::opt<unsigned> MISchedCutoff("misched-cutoff", cl::Hidden, 51 cl::desc("Stop scheduling after N instructions"), cl::init(~0U)); 52#else 53static bool ViewMISchedDAGs = false; 54#endif // NDEBUG 55 56static cl::opt<bool> EnableRegPressure("misched-regpressure", cl::Hidden, 57 cl::desc("Enable register pressure scheduling."), cl::init(true)); 58 59static cl::opt<bool> EnableCyclicPath("misched-cyclicpath", cl::Hidden, 60 cl::desc("Enable cyclic critical path analysis."), cl::init(false)); 61 62static cl::opt<bool> EnableLoadCluster("misched-cluster", cl::Hidden, 63 cl::desc("Enable load clustering."), cl::init(true)); 64 65// Experimental heuristics 66static cl::opt<bool> EnableMacroFusion("misched-fusion", cl::Hidden, 67 cl::desc("Enable scheduling for macro fusion."), cl::init(true)); 68 69static cl::opt<bool> VerifyScheduling("verify-misched", cl::Hidden, 70 cl::desc("Verify machine instrs before and after machine scheduling")); 71 72// DAG subtrees must have at least this many nodes. 73static const unsigned MinSubtreeSize = 8; 74 75//===----------------------------------------------------------------------===// 76// Machine Instruction Scheduling Pass and Registry 77//===----------------------------------------------------------------------===// 78 79MachineSchedContext::MachineSchedContext(): 80 MF(0), MLI(0), MDT(0), PassConfig(0), AA(0), LIS(0) { 81 RegClassInfo = new RegisterClassInfo(); 82} 83 84MachineSchedContext::~MachineSchedContext() { 85 delete RegClassInfo; 86} 87 88namespace { 89/// MachineScheduler runs after coalescing and before register allocation. 90class MachineScheduler : public MachineSchedContext, 91 public MachineFunctionPass { 92public: 93 MachineScheduler(); 94 95 virtual void getAnalysisUsage(AnalysisUsage &AU) const; 96 97 virtual void releaseMemory() {} 98 99 virtual bool runOnMachineFunction(MachineFunction&); 100 101 virtual void print(raw_ostream &O, const Module* = 0) const; 102 103 static char ID; // Class identification, replacement for typeinfo 104}; 105} // namespace 106 107char MachineScheduler::ID = 0; 108 109char &llvm::MachineSchedulerID = MachineScheduler::ID; 110 111INITIALIZE_PASS_BEGIN(MachineScheduler, "misched", 112 "Machine Instruction Scheduler", false, false) 113INITIALIZE_AG_DEPENDENCY(AliasAnalysis) 114INITIALIZE_PASS_DEPENDENCY(SlotIndexes) 115INITIALIZE_PASS_DEPENDENCY(LiveIntervals) 116INITIALIZE_PASS_END(MachineScheduler, "misched", 117 "Machine Instruction Scheduler", false, false) 118 119MachineScheduler::MachineScheduler() 120: MachineFunctionPass(ID) { 121 initializeMachineSchedulerPass(*PassRegistry::getPassRegistry()); 122} 123 124void MachineScheduler::getAnalysisUsage(AnalysisUsage &AU) const { 125 AU.setPreservesCFG(); 126 AU.addRequiredID(MachineDominatorsID); 127 AU.addRequired<MachineLoopInfo>(); 128 AU.addRequired<AliasAnalysis>(); 129 AU.addRequired<TargetPassConfig>(); 130 AU.addRequired<SlotIndexes>(); 131 AU.addPreserved<SlotIndexes>(); 132 AU.addRequired<LiveIntervals>(); 133 AU.addPreserved<LiveIntervals>(); 134 MachineFunctionPass::getAnalysisUsage(AU); 135} 136 137MachinePassRegistry MachineSchedRegistry::Registry; 138 139/// A dummy default scheduler factory indicates whether the scheduler 140/// is overridden on the command line. 141static ScheduleDAGInstrs *useDefaultMachineSched(MachineSchedContext *C) { 142 return 0; 143} 144 145/// MachineSchedOpt allows command line selection of the scheduler. 146static cl::opt<MachineSchedRegistry::ScheduleDAGCtor, false, 147 RegisterPassParser<MachineSchedRegistry> > 148MachineSchedOpt("misched", 149 cl::init(&useDefaultMachineSched), cl::Hidden, 150 cl::desc("Machine instruction scheduler to use")); 151 152static MachineSchedRegistry 153DefaultSchedRegistry("default", "Use the target's default scheduler choice.", 154 useDefaultMachineSched); 155 156/// Forward declare the standard machine scheduler. This will be used as the 157/// default scheduler if the target does not set a default. 158static ScheduleDAGInstrs *createConvergingSched(MachineSchedContext *C); 159 160 161/// Decrement this iterator until reaching the top or a non-debug instr. 162static MachineBasicBlock::const_iterator 163priorNonDebug(MachineBasicBlock::const_iterator I, 164 MachineBasicBlock::const_iterator Beg) { 165 assert(I != Beg && "reached the top of the region, cannot decrement"); 166 while (--I != Beg) { 167 if (!I->isDebugValue()) 168 break; 169 } 170 return I; 171} 172 173/// Non-const version. 174static MachineBasicBlock::iterator 175priorNonDebug(MachineBasicBlock::iterator I, 176 MachineBasicBlock::const_iterator Beg) { 177 return const_cast<MachineInstr*>( 178 &*priorNonDebug(MachineBasicBlock::const_iterator(I), Beg)); 179} 180 181/// If this iterator is a debug value, increment until reaching the End or a 182/// non-debug instruction. 183static MachineBasicBlock::const_iterator 184nextIfDebug(MachineBasicBlock::const_iterator I, 185 MachineBasicBlock::const_iterator End) { 186 for(; I != End; ++I) { 187 if (!I->isDebugValue()) 188 break; 189 } 190 return I; 191} 192 193/// Non-const version. 194static MachineBasicBlock::iterator 195nextIfDebug(MachineBasicBlock::iterator I, 196 MachineBasicBlock::const_iterator End) { 197 // Cast the return value to nonconst MachineInstr, then cast to an 198 // instr_iterator, which does not check for null, finally return a 199 // bundle_iterator. 200 return MachineBasicBlock::instr_iterator( 201 const_cast<MachineInstr*>( 202 &*nextIfDebug(MachineBasicBlock::const_iterator(I), End))); 203} 204 205/// Top-level MachineScheduler pass driver. 206/// 207/// Visit blocks in function order. Divide each block into scheduling regions 208/// and visit them bottom-up. Visiting regions bottom-up is not required, but is 209/// consistent with the DAG builder, which traverses the interior of the 210/// scheduling regions bottom-up. 211/// 212/// This design avoids exposing scheduling boundaries to the DAG builder, 213/// simplifying the DAG builder's support for "special" target instructions. 214/// At the same time the design allows target schedulers to operate across 215/// scheduling boundaries, for example to bundle the boudary instructions 216/// without reordering them. This creates complexity, because the target 217/// scheduler must update the RegionBegin and RegionEnd positions cached by 218/// ScheduleDAGInstrs whenever adding or removing instructions. A much simpler 219/// design would be to split blocks at scheduling boundaries, but LLVM has a 220/// general bias against block splitting purely for implementation simplicity. 221bool MachineScheduler::runOnMachineFunction(MachineFunction &mf) { 222 DEBUG(dbgs() << "Before MISsched:\n"; mf.print(dbgs())); 223 224 // Initialize the context of the pass. 225 MF = &mf; 226 MLI = &getAnalysis<MachineLoopInfo>(); 227 MDT = &getAnalysis<MachineDominatorTree>(); 228 PassConfig = &getAnalysis<TargetPassConfig>(); 229 AA = &getAnalysis<AliasAnalysis>(); 230 231 LIS = &getAnalysis<LiveIntervals>(); 232 const TargetInstrInfo *TII = MF->getTarget().getInstrInfo(); 233 234 if (VerifyScheduling) { 235 DEBUG(LIS->dump()); 236 MF->verify(this, "Before machine scheduling."); 237 } 238 RegClassInfo->runOnMachineFunction(*MF); 239 240 // Select the scheduler, or set the default. 241 MachineSchedRegistry::ScheduleDAGCtor Ctor = MachineSchedOpt; 242 if (Ctor == useDefaultMachineSched) { 243 // Get the default scheduler set by the target. 244 Ctor = MachineSchedRegistry::getDefault(); 245 if (!Ctor) { 246 Ctor = createConvergingSched; 247 MachineSchedRegistry::setDefault(Ctor); 248 } 249 } 250 // Instantiate the selected scheduler. 251 OwningPtr<ScheduleDAGInstrs> Scheduler(Ctor(this)); 252 253 // Visit all machine basic blocks. 254 // 255 // TODO: Visit blocks in global postorder or postorder within the bottom-up 256 // loop tree. Then we can optionally compute global RegPressure. 257 for (MachineFunction::iterator MBB = MF->begin(), MBBEnd = MF->end(); 258 MBB != MBBEnd; ++MBB) { 259 260 Scheduler->startBlock(MBB); 261 262 // Break the block into scheduling regions [I, RegionEnd), and schedule each 263 // region as soon as it is discovered. RegionEnd points the scheduling 264 // boundary at the bottom of the region. The DAG does not include RegionEnd, 265 // but the region does (i.e. the next RegionEnd is above the previous 266 // RegionBegin). If the current block has no terminator then RegionEnd == 267 // MBB->end() for the bottom region. 268 // 269 // The Scheduler may insert instructions during either schedule() or 270 // exitRegion(), even for empty regions. So the local iterators 'I' and 271 // 'RegionEnd' are invalid across these calls. 272 unsigned RemainingInstrs = MBB->size(); 273 for(MachineBasicBlock::iterator RegionEnd = MBB->end(); 274 RegionEnd != MBB->begin(); RegionEnd = Scheduler->begin()) { 275 276 // Avoid decrementing RegionEnd for blocks with no terminator. 277 if (RegionEnd != MBB->end() 278 || TII->isSchedulingBoundary(llvm::prior(RegionEnd), MBB, *MF)) { 279 --RegionEnd; 280 // Count the boundary instruction. 281 --RemainingInstrs; 282 } 283 284 // The next region starts above the previous region. Look backward in the 285 // instruction stream until we find the nearest boundary. 286 unsigned NumRegionInstrs = 0; 287 MachineBasicBlock::iterator I = RegionEnd; 288 for(;I != MBB->begin(); --I, --RemainingInstrs, ++NumRegionInstrs) { 289 if (TII->isSchedulingBoundary(llvm::prior(I), MBB, *MF)) 290 break; 291 } 292 // Notify the scheduler of the region, even if we may skip scheduling 293 // it. Perhaps it still needs to be bundled. 294 Scheduler->enterRegion(MBB, I, RegionEnd, NumRegionInstrs); 295 296 // Skip empty scheduling regions (0 or 1 schedulable instructions). 297 if (I == RegionEnd || I == llvm::prior(RegionEnd)) { 298 // Close the current region. Bundle the terminator if needed. 299 // This invalidates 'RegionEnd' and 'I'. 300 Scheduler->exitRegion(); 301 continue; 302 } 303 DEBUG(dbgs() << "********** MI Scheduling **********\n"); 304 DEBUG(dbgs() << MF->getName() 305 << ":BB#" << MBB->getNumber() << " " << MBB->getName() 306 << "\n From: " << *I << " To: "; 307 if (RegionEnd != MBB->end()) dbgs() << *RegionEnd; 308 else dbgs() << "End"; 309 dbgs() << " RegionInstrs: " << NumRegionInstrs 310 << " Remaining: " << RemainingInstrs << "\n"); 311 312 // Schedule a region: possibly reorder instructions. 313 // This invalidates 'RegionEnd' and 'I'. 314 Scheduler->schedule(); 315 316 // Close the current region. 317 Scheduler->exitRegion(); 318 319 // Scheduling has invalidated the current iterator 'I'. Ask the 320 // scheduler for the top of it's scheduled region. 321 RegionEnd = Scheduler->begin(); 322 } 323 assert(RemainingInstrs == 0 && "Instruction count mismatch!"); 324 Scheduler->finishBlock(); 325 } 326 Scheduler->finalizeSchedule(); 327 DEBUG(LIS->dump()); 328 if (VerifyScheduling) 329 MF->verify(this, "After machine scheduling."); 330 return true; 331} 332 333void MachineScheduler::print(raw_ostream &O, const Module* m) const { 334 // unimplemented 335} 336 337#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 338void ReadyQueue::dump() { 339 dbgs() << Name << ": "; 340 for (unsigned i = 0, e = Queue.size(); i < e; ++i) 341 dbgs() << Queue[i]->NodeNum << " "; 342 dbgs() << "\n"; 343} 344#endif 345 346//===----------------------------------------------------------------------===// 347// ScheduleDAGMI - Base class for MachineInstr scheduling with LiveIntervals 348// preservation. 349//===----------------------------------------------------------------------===// 350 351ScheduleDAGMI::~ScheduleDAGMI() { 352 delete DFSResult; 353 DeleteContainerPointers(Mutations); 354 delete SchedImpl; 355} 356 357bool ScheduleDAGMI::canAddEdge(SUnit *SuccSU, SUnit *PredSU) { 358 return SuccSU == &ExitSU || !Topo.IsReachable(PredSU, SuccSU); 359} 360 361bool ScheduleDAGMI::addEdge(SUnit *SuccSU, const SDep &PredDep) { 362 if (SuccSU != &ExitSU) { 363 // Do not use WillCreateCycle, it assumes SD scheduling. 364 // If Pred is reachable from Succ, then the edge creates a cycle. 365 if (Topo.IsReachable(PredDep.getSUnit(), SuccSU)) 366 return false; 367 Topo.AddPred(SuccSU, PredDep.getSUnit()); 368 } 369 SuccSU->addPred(PredDep, /*Required=*/!PredDep.isArtificial()); 370 // Return true regardless of whether a new edge needed to be inserted. 371 return true; 372} 373 374/// ReleaseSucc - Decrement the NumPredsLeft count of a successor. When 375/// NumPredsLeft reaches zero, release the successor node. 376/// 377/// FIXME: Adjust SuccSU height based on MinLatency. 378void ScheduleDAGMI::releaseSucc(SUnit *SU, SDep *SuccEdge) { 379 SUnit *SuccSU = SuccEdge->getSUnit(); 380 381 if (SuccEdge->isWeak()) { 382 --SuccSU->WeakPredsLeft; 383 if (SuccEdge->isCluster()) 384 NextClusterSucc = SuccSU; 385 return; 386 } 387#ifndef NDEBUG 388 if (SuccSU->NumPredsLeft == 0) { 389 dbgs() << "*** Scheduling failed! ***\n"; 390 SuccSU->dump(this); 391 dbgs() << " has been released too many times!\n"; 392 llvm_unreachable(0); 393 } 394#endif 395 --SuccSU->NumPredsLeft; 396 if (SuccSU->NumPredsLeft == 0 && SuccSU != &ExitSU) 397 SchedImpl->releaseTopNode(SuccSU); 398} 399 400/// releaseSuccessors - Call releaseSucc on each of SU's successors. 401void ScheduleDAGMI::releaseSuccessors(SUnit *SU) { 402 for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); 403 I != E; ++I) { 404 releaseSucc(SU, &*I); 405 } 406} 407 408/// ReleasePred - Decrement the NumSuccsLeft count of a predecessor. When 409/// NumSuccsLeft reaches zero, release the predecessor node. 410/// 411/// FIXME: Adjust PredSU height based on MinLatency. 412void ScheduleDAGMI::releasePred(SUnit *SU, SDep *PredEdge) { 413 SUnit *PredSU = PredEdge->getSUnit(); 414 415 if (PredEdge->isWeak()) { 416 --PredSU->WeakSuccsLeft; 417 if (PredEdge->isCluster()) 418 NextClusterPred = PredSU; 419 return; 420 } 421#ifndef NDEBUG 422 if (PredSU->NumSuccsLeft == 0) { 423 dbgs() << "*** Scheduling failed! ***\n"; 424 PredSU->dump(this); 425 dbgs() << " has been released too many times!\n"; 426 llvm_unreachable(0); 427 } 428#endif 429 --PredSU->NumSuccsLeft; 430 if (PredSU->NumSuccsLeft == 0 && PredSU != &EntrySU) 431 SchedImpl->releaseBottomNode(PredSU); 432} 433 434/// releasePredecessors - Call releasePred on each of SU's predecessors. 435void ScheduleDAGMI::releasePredecessors(SUnit *SU) { 436 for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); 437 I != E; ++I) { 438 releasePred(SU, &*I); 439 } 440} 441 442/// This is normally called from the main scheduler loop but may also be invoked 443/// by the scheduling strategy to perform additional code motion. 444void ScheduleDAGMI::moveInstruction(MachineInstr *MI, 445 MachineBasicBlock::iterator InsertPos) { 446 // Advance RegionBegin if the first instruction moves down. 447 if (&*RegionBegin == MI) 448 ++RegionBegin; 449 450 // Update the instruction stream. 451 BB->splice(InsertPos, BB, MI); 452 453 // Update LiveIntervals 454 LIS->handleMove(MI, /*UpdateFlags=*/true); 455 456 // Recede RegionBegin if an instruction moves above the first. 457 if (RegionBegin == InsertPos) 458 RegionBegin = MI; 459} 460 461bool ScheduleDAGMI::checkSchedLimit() { 462#ifndef NDEBUG 463 if (NumInstrsScheduled == MISchedCutoff && MISchedCutoff != ~0U) { 464 CurrentTop = CurrentBottom; 465 return false; 466 } 467 ++NumInstrsScheduled; 468#endif 469 return true; 470} 471 472/// enterRegion - Called back from MachineScheduler::runOnMachineFunction after 473/// crossing a scheduling boundary. [begin, end) includes all instructions in 474/// the region, including the boundary itself and single-instruction regions 475/// that don't get scheduled. 476void ScheduleDAGMI::enterRegion(MachineBasicBlock *bb, 477 MachineBasicBlock::iterator begin, 478 MachineBasicBlock::iterator end, 479 unsigned regioninstrs) 480{ 481 ScheduleDAGInstrs::enterRegion(bb, begin, end, regioninstrs); 482 483 ShouldTrackPressure = 484 EnableRegPressure && SchedImpl->shouldTrackPressure(regioninstrs); 485 486 // For convenience remember the end of the liveness region. 487 LiveRegionEnd = 488 (RegionEnd == bb->end()) ? RegionEnd : llvm::next(RegionEnd); 489} 490 491// Setup the register pressure trackers for the top scheduled top and bottom 492// scheduled regions. 493void ScheduleDAGMI::initRegPressure() { 494 TopRPTracker.init(&MF, RegClassInfo, LIS, BB, RegionBegin); 495 BotRPTracker.init(&MF, RegClassInfo, LIS, BB, LiveRegionEnd); 496 497 // Close the RPTracker to finalize live ins. 498 RPTracker.closeRegion(); 499 500 DEBUG(RPTracker.dump()); 501 502 // Initialize the live ins and live outs. 503 TopRPTracker.addLiveRegs(RPTracker.getPressure().LiveInRegs); 504 BotRPTracker.addLiveRegs(RPTracker.getPressure().LiveOutRegs); 505 506 // Close one end of the tracker so we can call 507 // getMaxUpward/DownwardPressureDelta before advancing across any 508 // instructions. This converts currently live regs into live ins/outs. 509 TopRPTracker.closeTop(); 510 BotRPTracker.closeBottom(); 511 512 BotRPTracker.initLiveThru(RPTracker); 513 if (!BotRPTracker.getLiveThru().empty()) { 514 TopRPTracker.initLiveThru(BotRPTracker.getLiveThru()); 515 DEBUG(dbgs() << "Live Thru: "; 516 dumpRegSetPressure(BotRPTracker.getLiveThru(), TRI)); 517 }; 518 519 // For each live out vreg reduce the pressure change associated with other 520 // uses of the same vreg below the live-out reaching def. 521 updatePressureDiffs(RPTracker.getPressure().LiveOutRegs); 522 523 // Account for liveness generated by the region boundary. 524 if (LiveRegionEnd != RegionEnd) { 525 SmallVector<unsigned, 8> LiveUses; 526 BotRPTracker.recede(&LiveUses); 527 updatePressureDiffs(LiveUses); 528 } 529 530 assert(BotRPTracker.getPos() == RegionEnd && "Can't find the region bottom"); 531 532 // Cache the list of excess pressure sets in this region. This will also track 533 // the max pressure in the scheduled code for these sets. 534 RegionCriticalPSets.clear(); 535 const std::vector<unsigned> &RegionPressure = 536 RPTracker.getPressure().MaxSetPressure; 537 for (unsigned i = 0, e = RegionPressure.size(); i < e; ++i) { 538 unsigned Limit = RegClassInfo->getRegPressureSetLimit(i); 539 if (RegionPressure[i] > Limit) { 540 DEBUG(dbgs() << TRI->getRegPressureSetName(i) 541 << " Limit " << Limit 542 << " Actual " << RegionPressure[i] << "\n"); 543 RegionCriticalPSets.push_back(PressureChange(i)); 544 } 545 } 546 DEBUG(dbgs() << "Excess PSets: "; 547 for (unsigned i = 0, e = RegionCriticalPSets.size(); i != e; ++i) 548 dbgs() << TRI->getRegPressureSetName( 549 RegionCriticalPSets[i].getPSet()) << " "; 550 dbgs() << "\n"); 551} 552 553// FIXME: When the pressure tracker deals in pressure differences then we won't 554// iterate over all RegionCriticalPSets[i]. 555void ScheduleDAGMI:: 556updateScheduledPressure(const std::vector<unsigned> &NewMaxPressure) { 557 for (unsigned i = 0, e = RegionCriticalPSets.size(); i < e; ++i) { 558 unsigned ID = RegionCriticalPSets[i].getPSet(); 559 if ((int)NewMaxPressure[ID] > RegionCriticalPSets[i].getUnitInc() 560 && NewMaxPressure[ID] <= INT16_MAX) 561 RegionCriticalPSets[i].setUnitInc(NewMaxPressure[ID]); 562 } 563 DEBUG( 564 for (unsigned i = 0, e = NewMaxPressure.size(); i < e; ++i) { 565 unsigned Limit = RegClassInfo->getRegPressureSetLimit(i); 566 if (NewMaxPressure[i] > Limit ) { 567 dbgs() << " " << TRI->getRegPressureSetName(i) << ": " 568 << NewMaxPressure[i] << " > " << Limit << "\n"; 569 } 570 }); 571} 572 573/// Update the PressureDiff array for liveness after scheduling this 574/// instruction. 575void ScheduleDAGMI::updatePressureDiffs(ArrayRef<unsigned> LiveUses) { 576 for (unsigned LUIdx = 0, LUEnd = LiveUses.size(); LUIdx != LUEnd; ++LUIdx) { 577 /// FIXME: Currently assuming single-use physregs. 578 unsigned Reg = LiveUses[LUIdx]; 579 if (!TRI->isVirtualRegister(Reg)) 580 continue; 581 // This may be called before CurrentBottom has been initialized. However, 582 // BotRPTracker must have a valid position. We want the value live into the 583 // instruction or live out of the block, so ask for the previous 584 // instruction's live-out. 585 const LiveInterval &LI = LIS->getInterval(Reg); 586 VNInfo *VNI; 587 MachineBasicBlock::const_iterator I = 588 nextIfDebug(BotRPTracker.getPos(), BB->end()); 589 if (I == BB->end()) 590 VNI = LI.getVNInfoBefore(LIS->getMBBEndIdx(BB)); 591 else { 592 LiveRangeQuery LRQ(LI, LIS->getInstructionIndex(I)); 593 VNI = LRQ.valueIn(); 594 } 595 // RegisterPressureTracker guarantees that readsReg is true for LiveUses. 596 assert(VNI && "No live value at use."); 597 for (VReg2UseMap::iterator 598 UI = VRegUses.find(Reg); UI != VRegUses.end(); ++UI) { 599 SUnit *SU = UI->SU; 600 // If this use comes before the reaching def, it cannot be a last use, so 601 // descrease its pressure change. 602 if (!SU->isScheduled && SU != &ExitSU) { 603 LiveRangeQuery LRQ(LI, LIS->getInstructionIndex(SU->getInstr())); 604 if (LRQ.valueIn() == VNI) 605 getPressureDiff(SU).addPressureChange(Reg, true, &MRI); 606 } 607 } 608 } 609} 610 611/// schedule - Called back from MachineScheduler::runOnMachineFunction 612/// after setting up the current scheduling region. [RegionBegin, RegionEnd) 613/// only includes instructions that have DAG nodes, not scheduling boundaries. 614/// 615/// This is a skeletal driver, with all the functionality pushed into helpers, 616/// so that it can be easilly extended by experimental schedulers. Generally, 617/// implementing MachineSchedStrategy should be sufficient to implement a new 618/// scheduling algorithm. However, if a scheduler further subclasses 619/// ScheduleDAGMI then it will want to override this virtual method in order to 620/// update any specialized state. 621void ScheduleDAGMI::schedule() { 622 buildDAGWithRegPressure(); 623 624 Topo.InitDAGTopologicalSorting(); 625 626 postprocessDAG(); 627 628 SmallVector<SUnit*, 8> TopRoots, BotRoots; 629 findRootsAndBiasEdges(TopRoots, BotRoots); 630 631 // Initialize the strategy before modifying the DAG. 632 // This may initialize a DFSResult to be used for queue priority. 633 SchedImpl->initialize(this); 634 635 DEBUG(for (unsigned su = 0, e = SUnits.size(); su != e; ++su) 636 SUnits[su].dumpAll(this)); 637 if (ViewMISchedDAGs) viewGraph(); 638 639 // Initialize ready queues now that the DAG and priority data are finalized. 640 initQueues(TopRoots, BotRoots); 641 642 bool IsTopNode = false; 643 while (SUnit *SU = SchedImpl->pickNode(IsTopNode)) { 644 assert(!SU->isScheduled && "Node already scheduled"); 645 if (!checkSchedLimit()) 646 break; 647 648 scheduleMI(SU, IsTopNode); 649 650 updateQueues(SU, IsTopNode); 651 } 652 assert(CurrentTop == CurrentBottom && "Nonempty unscheduled zone."); 653 654 placeDebugValues(); 655 656 DEBUG({ 657 unsigned BBNum = begin()->getParent()->getNumber(); 658 dbgs() << "*** Final schedule for BB#" << BBNum << " ***\n"; 659 dumpSchedule(); 660 dbgs() << '\n'; 661 }); 662} 663 664/// Build the DAG and setup three register pressure trackers. 665void ScheduleDAGMI::buildDAGWithRegPressure() { 666 if (!ShouldTrackPressure) { 667 RPTracker.reset(); 668 RegionCriticalPSets.clear(); 669 buildSchedGraph(AA); 670 return; 671 } 672 673 // Initialize the register pressure tracker used by buildSchedGraph. 674 RPTracker.init(&MF, RegClassInfo, LIS, BB, LiveRegionEnd, 675 /*TrackUntiedDefs=*/true); 676 677 // Account for liveness generate by the region boundary. 678 if (LiveRegionEnd != RegionEnd) 679 RPTracker.recede(); 680 681 // Build the DAG, and compute current register pressure. 682 buildSchedGraph(AA, &RPTracker, &SUPressureDiffs); 683 684 // Initialize top/bottom trackers after computing region pressure. 685 initRegPressure(); 686} 687 688/// Apply each ScheduleDAGMutation step in order. 689void ScheduleDAGMI::postprocessDAG() { 690 for (unsigned i = 0, e = Mutations.size(); i < e; ++i) { 691 Mutations[i]->apply(this); 692 } 693} 694 695void ScheduleDAGMI::computeDFSResult() { 696 if (!DFSResult) 697 DFSResult = new SchedDFSResult(/*BottomU*/true, MinSubtreeSize); 698 DFSResult->clear(); 699 ScheduledTrees.clear(); 700 DFSResult->resize(SUnits.size()); 701 DFSResult->compute(SUnits); 702 ScheduledTrees.resize(DFSResult->getNumSubtrees()); 703} 704 705void ScheduleDAGMI::findRootsAndBiasEdges(SmallVectorImpl<SUnit*> &TopRoots, 706 SmallVectorImpl<SUnit*> &BotRoots) { 707 for (std::vector<SUnit>::iterator 708 I = SUnits.begin(), E = SUnits.end(); I != E; ++I) { 709 SUnit *SU = &(*I); 710 assert(!SU->isBoundaryNode() && "Boundary node should not be in SUnits"); 711 712 // Order predecessors so DFSResult follows the critical path. 713 SU->biasCriticalPath(); 714 715 // A SUnit is ready to top schedule if it has no predecessors. 716 if (!I->NumPredsLeft) 717 TopRoots.push_back(SU); 718 // A SUnit is ready to bottom schedule if it has no successors. 719 if (!I->NumSuccsLeft) 720 BotRoots.push_back(SU); 721 } 722 ExitSU.biasCriticalPath(); 723} 724 725/// Compute the max cyclic critical path through the DAG. The scheduling DAG 726/// only provides the critical path for single block loops. To handle loops that 727/// span blocks, we could use the vreg path latencies provided by 728/// MachineTraceMetrics instead. However, MachineTraceMetrics is not currently 729/// available for use in the scheduler. 730/// 731/// The cyclic path estimation identifies a def-use pair that crosses the back 732/// edge and considers the depth and height of the nodes. For example, consider 733/// the following instruction sequence where each instruction has unit latency 734/// and defines an epomymous virtual register: 735/// 736/// a->b(a,c)->c(b)->d(c)->exit 737/// 738/// The cyclic critical path is a two cycles: b->c->b 739/// The acyclic critical path is four cycles: a->b->c->d->exit 740/// LiveOutHeight = height(c) = len(c->d->exit) = 2 741/// LiveOutDepth = depth(c) + 1 = len(a->b->c) + 1 = 3 742/// LiveInHeight = height(b) + 1 = len(b->c->d->exit) + 1 = 4 743/// LiveInDepth = depth(b) = len(a->b) = 1 744/// 745/// LiveOutDepth - LiveInDepth = 3 - 1 = 2 746/// LiveInHeight - LiveOutHeight = 4 - 2 = 2 747/// CyclicCriticalPath = min(2, 2) = 2 748unsigned ScheduleDAGMI::computeCyclicCriticalPath() { 749 // This only applies to single block loop. 750 if (!BB->isSuccessor(BB)) 751 return 0; 752 753 unsigned MaxCyclicLatency = 0; 754 // Visit each live out vreg def to find def/use pairs that cross iterations. 755 ArrayRef<unsigned> LiveOuts = RPTracker.getPressure().LiveOutRegs; 756 for (ArrayRef<unsigned>::iterator RI = LiveOuts.begin(), RE = LiveOuts.end(); 757 RI != RE; ++RI) { 758 unsigned Reg = *RI; 759 if (!TRI->isVirtualRegister(Reg)) 760 continue; 761 const LiveInterval &LI = LIS->getInterval(Reg); 762 const VNInfo *DefVNI = LI.getVNInfoBefore(LIS->getMBBEndIdx(BB)); 763 if (!DefVNI) 764 continue; 765 766 MachineInstr *DefMI = LIS->getInstructionFromIndex(DefVNI->def); 767 const SUnit *DefSU = getSUnit(DefMI); 768 if (!DefSU) 769 continue; 770 771 unsigned LiveOutHeight = DefSU->getHeight(); 772 unsigned LiveOutDepth = DefSU->getDepth() + DefSU->Latency; 773 // Visit all local users of the vreg def. 774 for (VReg2UseMap::iterator 775 UI = VRegUses.find(Reg); UI != VRegUses.end(); ++UI) { 776 if (UI->SU == &ExitSU) 777 continue; 778 779 // Only consider uses of the phi. 780 LiveRangeQuery LRQ(LI, LIS->getInstructionIndex(UI->SU->getInstr())); 781 if (!LRQ.valueIn()->isPHIDef()) 782 continue; 783 784 // Assume that a path spanning two iterations is a cycle, which could 785 // overestimate in strange cases. This allows cyclic latency to be 786 // estimated as the minimum slack of the vreg's depth or height. 787 unsigned CyclicLatency = 0; 788 if (LiveOutDepth > UI->SU->getDepth()) 789 CyclicLatency = LiveOutDepth - UI->SU->getDepth(); 790 791 unsigned LiveInHeight = UI->SU->getHeight() + DefSU->Latency; 792 if (LiveInHeight > LiveOutHeight) { 793 if (LiveInHeight - LiveOutHeight < CyclicLatency) 794 CyclicLatency = LiveInHeight - LiveOutHeight; 795 } 796 else 797 CyclicLatency = 0; 798 799 DEBUG(dbgs() << "Cyclic Path: SU(" << DefSU->NodeNum << ") -> SU(" 800 << UI->SU->NodeNum << ") = " << CyclicLatency << "c\n"); 801 if (CyclicLatency > MaxCyclicLatency) 802 MaxCyclicLatency = CyclicLatency; 803 } 804 } 805 DEBUG(dbgs() << "Cyclic Critical Path: " << MaxCyclicLatency << "c\n"); 806 return MaxCyclicLatency; 807} 808 809/// Identify DAG roots and setup scheduler queues. 810void ScheduleDAGMI::initQueues(ArrayRef<SUnit*> TopRoots, 811 ArrayRef<SUnit*> BotRoots) { 812 NextClusterSucc = NULL; 813 NextClusterPred = NULL; 814 815 // Release all DAG roots for scheduling, not including EntrySU/ExitSU. 816 // 817 // Nodes with unreleased weak edges can still be roots. 818 // Release top roots in forward order. 819 for (SmallVectorImpl<SUnit*>::const_iterator 820 I = TopRoots.begin(), E = TopRoots.end(); I != E; ++I) { 821 SchedImpl->releaseTopNode(*I); 822 } 823 // Release bottom roots in reverse order so the higher priority nodes appear 824 // first. This is more natural and slightly more efficient. 825 for (SmallVectorImpl<SUnit*>::const_reverse_iterator 826 I = BotRoots.rbegin(), E = BotRoots.rend(); I != E; ++I) { 827 SchedImpl->releaseBottomNode(*I); 828 } 829 830 releaseSuccessors(&EntrySU); 831 releasePredecessors(&ExitSU); 832 833 SchedImpl->registerRoots(); 834 835 // Advance past initial DebugValues. 836 CurrentTop = nextIfDebug(RegionBegin, RegionEnd); 837 CurrentBottom = RegionEnd; 838 839 if (ShouldTrackPressure) { 840 assert(TopRPTracker.getPos() == RegionBegin && "bad initial Top tracker"); 841 TopRPTracker.setPos(CurrentTop); 842 } 843} 844 845/// Move an instruction and update register pressure. 846void ScheduleDAGMI::scheduleMI(SUnit *SU, bool IsTopNode) { 847 // Move the instruction to its new location in the instruction stream. 848 MachineInstr *MI = SU->getInstr(); 849 850 if (IsTopNode) { 851 assert(SU->isTopReady() && "node still has unscheduled dependencies"); 852 if (&*CurrentTop == MI) 853 CurrentTop = nextIfDebug(++CurrentTop, CurrentBottom); 854 else { 855 moveInstruction(MI, CurrentTop); 856 TopRPTracker.setPos(MI); 857 } 858 859 if (ShouldTrackPressure) { 860 // Update top scheduled pressure. 861 TopRPTracker.advance(); 862 assert(TopRPTracker.getPos() == CurrentTop && "out of sync"); 863 updateScheduledPressure(TopRPTracker.getPressure().MaxSetPressure); 864 } 865 } 866 else { 867 assert(SU->isBottomReady() && "node still has unscheduled dependencies"); 868 MachineBasicBlock::iterator priorII = 869 priorNonDebug(CurrentBottom, CurrentTop); 870 if (&*priorII == MI) 871 CurrentBottom = priorII; 872 else { 873 if (&*CurrentTop == MI) { 874 CurrentTop = nextIfDebug(++CurrentTop, priorII); 875 TopRPTracker.setPos(CurrentTop); 876 } 877 moveInstruction(MI, CurrentBottom); 878 CurrentBottom = MI; 879 } 880 if (ShouldTrackPressure) { 881 // Update bottom scheduled pressure. 882 SmallVector<unsigned, 8> LiveUses; 883 BotRPTracker.recede(&LiveUses); 884 assert(BotRPTracker.getPos() == CurrentBottom && "out of sync"); 885 updatePressureDiffs(LiveUses); 886 updateScheduledPressure(BotRPTracker.getPressure().MaxSetPressure); 887 } 888 } 889} 890 891/// Update scheduler queues after scheduling an instruction. 892void ScheduleDAGMI::updateQueues(SUnit *SU, bool IsTopNode) { 893 // Release dependent instructions for scheduling. 894 if (IsTopNode) 895 releaseSuccessors(SU); 896 else 897 releasePredecessors(SU); 898 899 SU->isScheduled = true; 900 901 if (DFSResult) { 902 unsigned SubtreeID = DFSResult->getSubtreeID(SU); 903 if (!ScheduledTrees.test(SubtreeID)) { 904 ScheduledTrees.set(SubtreeID); 905 DFSResult->scheduleTree(SubtreeID); 906 SchedImpl->scheduleTree(SubtreeID); 907 } 908 } 909 910 // Notify the scheduling strategy after updating the DAG. 911 SchedImpl->schedNode(SU, IsTopNode); 912} 913 914/// Reinsert any remaining debug_values, just like the PostRA scheduler. 915void ScheduleDAGMI::placeDebugValues() { 916 // If first instruction was a DBG_VALUE then put it back. 917 if (FirstDbgValue) { 918 BB->splice(RegionBegin, BB, FirstDbgValue); 919 RegionBegin = FirstDbgValue; 920 } 921 922 for (std::vector<std::pair<MachineInstr *, MachineInstr *> >::iterator 923 DI = DbgValues.end(), DE = DbgValues.begin(); DI != DE; --DI) { 924 std::pair<MachineInstr *, MachineInstr *> P = *prior(DI); 925 MachineInstr *DbgValue = P.first; 926 MachineBasicBlock::iterator OrigPrevMI = P.second; 927 if (&*RegionBegin == DbgValue) 928 ++RegionBegin; 929 BB->splice(++OrigPrevMI, BB, DbgValue); 930 if (OrigPrevMI == llvm::prior(RegionEnd)) 931 RegionEnd = DbgValue; 932 } 933 DbgValues.clear(); 934 FirstDbgValue = NULL; 935} 936 937#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 938void ScheduleDAGMI::dumpSchedule() const { 939 for (MachineBasicBlock::iterator MI = begin(), ME = end(); MI != ME; ++MI) { 940 if (SUnit *SU = getSUnit(&(*MI))) 941 SU->dump(this); 942 else 943 dbgs() << "Missing SUnit\n"; 944 } 945} 946#endif 947 948//===----------------------------------------------------------------------===// 949// LoadClusterMutation - DAG post-processing to cluster loads. 950//===----------------------------------------------------------------------===// 951 952namespace { 953/// \brief Post-process the DAG to create cluster edges between neighboring 954/// loads. 955class LoadClusterMutation : public ScheduleDAGMutation { 956 struct LoadInfo { 957 SUnit *SU; 958 unsigned BaseReg; 959 unsigned Offset; 960 LoadInfo(SUnit *su, unsigned reg, unsigned ofs) 961 : SU(su), BaseReg(reg), Offset(ofs) {} 962 }; 963 static bool LoadInfoLess(const LoadClusterMutation::LoadInfo &LHS, 964 const LoadClusterMutation::LoadInfo &RHS); 965 966 const TargetInstrInfo *TII; 967 const TargetRegisterInfo *TRI; 968public: 969 LoadClusterMutation(const TargetInstrInfo *tii, 970 const TargetRegisterInfo *tri) 971 : TII(tii), TRI(tri) {} 972 973 virtual void apply(ScheduleDAGMI *DAG); 974protected: 975 void clusterNeighboringLoads(ArrayRef<SUnit*> Loads, ScheduleDAGMI *DAG); 976}; 977} // anonymous 978 979bool LoadClusterMutation::LoadInfoLess( 980 const LoadClusterMutation::LoadInfo &LHS, 981 const LoadClusterMutation::LoadInfo &RHS) { 982 if (LHS.BaseReg != RHS.BaseReg) 983 return LHS.BaseReg < RHS.BaseReg; 984 return LHS.Offset < RHS.Offset; 985} 986 987void LoadClusterMutation::clusterNeighboringLoads(ArrayRef<SUnit*> Loads, 988 ScheduleDAGMI *DAG) { 989 SmallVector<LoadClusterMutation::LoadInfo,32> LoadRecords; 990 for (unsigned Idx = 0, End = Loads.size(); Idx != End; ++Idx) { 991 SUnit *SU = Loads[Idx]; 992 unsigned BaseReg; 993 unsigned Offset; 994 if (TII->getLdStBaseRegImmOfs(SU->getInstr(), BaseReg, Offset, TRI)) 995 LoadRecords.push_back(LoadInfo(SU, BaseReg, Offset)); 996 } 997 if (LoadRecords.size() < 2) 998 return; 999 std::sort(LoadRecords.begin(), LoadRecords.end(), LoadInfoLess); 1000 unsigned ClusterLength = 1; 1001 for (unsigned Idx = 0, End = LoadRecords.size(); Idx < (End - 1); ++Idx) { 1002 if (LoadRecords[Idx].BaseReg != LoadRecords[Idx+1].BaseReg) { 1003 ClusterLength = 1; 1004 continue; 1005 } 1006 1007 SUnit *SUa = LoadRecords[Idx].SU; 1008 SUnit *SUb = LoadRecords[Idx+1].SU; 1009 if (TII->shouldClusterLoads(SUa->getInstr(), SUb->getInstr(), ClusterLength) 1010 && DAG->addEdge(SUb, SDep(SUa, SDep::Cluster))) { 1011 1012 DEBUG(dbgs() << "Cluster loads SU(" << SUa->NodeNum << ") - SU(" 1013 << SUb->NodeNum << ")\n"); 1014 // Copy successor edges from SUa to SUb. Interleaving computation 1015 // dependent on SUa can prevent load combining due to register reuse. 1016 // Predecessor edges do not need to be copied from SUb to SUa since nearby 1017 // loads should have effectively the same inputs. 1018 for (SUnit::const_succ_iterator 1019 SI = SUa->Succs.begin(), SE = SUa->Succs.end(); SI != SE; ++SI) { 1020 if (SI->getSUnit() == SUb) 1021 continue; 1022 DEBUG(dbgs() << " Copy Succ SU(" << SI->getSUnit()->NodeNum << ")\n"); 1023 DAG->addEdge(SI->getSUnit(), SDep(SUb, SDep::Artificial)); 1024 } 1025 ++ClusterLength; 1026 } 1027 else 1028 ClusterLength = 1; 1029 } 1030} 1031 1032/// \brief Callback from DAG postProcessing to create cluster edges for loads. 1033void LoadClusterMutation::apply(ScheduleDAGMI *DAG) { 1034 // Map DAG NodeNum to store chain ID. 1035 DenseMap<unsigned, unsigned> StoreChainIDs; 1036 // Map each store chain to a set of dependent loads. 1037 SmallVector<SmallVector<SUnit*,4>, 32> StoreChainDependents; 1038 for (unsigned Idx = 0, End = DAG->SUnits.size(); Idx != End; ++Idx) { 1039 SUnit *SU = &DAG->SUnits[Idx]; 1040 if (!SU->getInstr()->mayLoad()) 1041 continue; 1042 unsigned ChainPredID = DAG->SUnits.size(); 1043 for (SUnit::const_pred_iterator 1044 PI = SU->Preds.begin(), PE = SU->Preds.end(); PI != PE; ++PI) { 1045 if (PI->isCtrl()) { 1046 ChainPredID = PI->getSUnit()->NodeNum; 1047 break; 1048 } 1049 } 1050 // Check if this chain-like pred has been seen 1051 // before. ChainPredID==MaxNodeID for loads at the top of the schedule. 1052 unsigned NumChains = StoreChainDependents.size(); 1053 std::pair<DenseMap<unsigned, unsigned>::iterator, bool> Result = 1054 StoreChainIDs.insert(std::make_pair(ChainPredID, NumChains)); 1055 if (Result.second) 1056 StoreChainDependents.resize(NumChains + 1); 1057 StoreChainDependents[Result.first->second].push_back(SU); 1058 } 1059 // Iterate over the store chains. 1060 for (unsigned Idx = 0, End = StoreChainDependents.size(); Idx != End; ++Idx) 1061 clusterNeighboringLoads(StoreChainDependents[Idx], DAG); 1062} 1063 1064//===----------------------------------------------------------------------===// 1065// MacroFusion - DAG post-processing to encourage fusion of macro ops. 1066//===----------------------------------------------------------------------===// 1067 1068namespace { 1069/// \brief Post-process the DAG to create cluster edges between instructions 1070/// that may be fused by the processor into a single operation. 1071class MacroFusion : public ScheduleDAGMutation { 1072 const TargetInstrInfo *TII; 1073public: 1074 MacroFusion(const TargetInstrInfo *tii): TII(tii) {} 1075 1076 virtual void apply(ScheduleDAGMI *DAG); 1077}; 1078} // anonymous 1079 1080/// \brief Callback from DAG postProcessing to create cluster edges to encourage 1081/// fused operations. 1082void MacroFusion::apply(ScheduleDAGMI *DAG) { 1083 // For now, assume targets can only fuse with the branch. 1084 MachineInstr *Branch = DAG->ExitSU.getInstr(); 1085 if (!Branch) 1086 return; 1087 1088 for (unsigned Idx = DAG->SUnits.size(); Idx > 0;) { 1089 SUnit *SU = &DAG->SUnits[--Idx]; 1090 if (!TII->shouldScheduleAdjacent(SU->getInstr(), Branch)) 1091 continue; 1092 1093 // Create a single weak edge from SU to ExitSU. The only effect is to cause 1094 // bottom-up scheduling to heavily prioritize the clustered SU. There is no 1095 // need to copy predecessor edges from ExitSU to SU, since top-down 1096 // scheduling cannot prioritize ExitSU anyway. To defer top-down scheduling 1097 // of SU, we could create an artificial edge from the deepest root, but it 1098 // hasn't been needed yet. 1099 bool Success = DAG->addEdge(&DAG->ExitSU, SDep(SU, SDep::Cluster)); 1100 (void)Success; 1101 assert(Success && "No DAG nodes should be reachable from ExitSU"); 1102 1103 DEBUG(dbgs() << "Macro Fuse SU(" << SU->NodeNum << ")\n"); 1104 break; 1105 } 1106} 1107 1108//===----------------------------------------------------------------------===// 1109// CopyConstrain - DAG post-processing to encourage copy elimination. 1110//===----------------------------------------------------------------------===// 1111 1112namespace { 1113/// \brief Post-process the DAG to create weak edges from all uses of a copy to 1114/// the one use that defines the copy's source vreg, most likely an induction 1115/// variable increment. 1116class CopyConstrain : public ScheduleDAGMutation { 1117 // Transient state. 1118 SlotIndex RegionBeginIdx; 1119 // RegionEndIdx is the slot index of the last non-debug instruction in the 1120 // scheduling region. So we may have RegionBeginIdx == RegionEndIdx. 1121 SlotIndex RegionEndIdx; 1122public: 1123 CopyConstrain(const TargetInstrInfo *, const TargetRegisterInfo *) {} 1124 1125 virtual void apply(ScheduleDAGMI *DAG); 1126 1127protected: 1128 void constrainLocalCopy(SUnit *CopySU, ScheduleDAGMI *DAG); 1129}; 1130} // anonymous 1131 1132/// constrainLocalCopy handles two possibilities: 1133/// 1) Local src: 1134/// I0: = dst 1135/// I1: src = ... 1136/// I2: = dst 1137/// I3: dst = src (copy) 1138/// (create pred->succ edges I0->I1, I2->I1) 1139/// 1140/// 2) Local copy: 1141/// I0: dst = src (copy) 1142/// I1: = dst 1143/// I2: src = ... 1144/// I3: = dst 1145/// (create pred->succ edges I1->I2, I3->I2) 1146/// 1147/// Although the MachineScheduler is currently constrained to single blocks, 1148/// this algorithm should handle extended blocks. An EBB is a set of 1149/// contiguously numbered blocks such that the previous block in the EBB is 1150/// always the single predecessor. 1151void CopyConstrain::constrainLocalCopy(SUnit *CopySU, ScheduleDAGMI *DAG) { 1152 LiveIntervals *LIS = DAG->getLIS(); 1153 MachineInstr *Copy = CopySU->getInstr(); 1154 1155 // Check for pure vreg copies. 1156 unsigned SrcReg = Copy->getOperand(1).getReg(); 1157 if (!TargetRegisterInfo::isVirtualRegister(SrcReg)) 1158 return; 1159 1160 unsigned DstReg = Copy->getOperand(0).getReg(); 1161 if (!TargetRegisterInfo::isVirtualRegister(DstReg)) 1162 return; 1163 1164 // Check if either the dest or source is local. If it's live across a back 1165 // edge, it's not local. Note that if both vregs are live across the back 1166 // edge, we cannot successfully contrain the copy without cyclic scheduling. 1167 unsigned LocalReg = DstReg; 1168 unsigned GlobalReg = SrcReg; 1169 LiveInterval *LocalLI = &LIS->getInterval(LocalReg); 1170 if (!LocalLI->isLocal(RegionBeginIdx, RegionEndIdx)) { 1171 LocalReg = SrcReg; 1172 GlobalReg = DstReg; 1173 LocalLI = &LIS->getInterval(LocalReg); 1174 if (!LocalLI->isLocal(RegionBeginIdx, RegionEndIdx)) 1175 return; 1176 } 1177 LiveInterval *GlobalLI = &LIS->getInterval(GlobalReg); 1178 1179 // Find the global segment after the start of the local LI. 1180 LiveInterval::iterator GlobalSegment = GlobalLI->find(LocalLI->beginIndex()); 1181 // If GlobalLI does not overlap LocalLI->start, then a copy directly feeds a 1182 // local live range. We could create edges from other global uses to the local 1183 // start, but the coalescer should have already eliminated these cases, so 1184 // don't bother dealing with it. 1185 if (GlobalSegment == GlobalLI->end()) 1186 return; 1187 1188 // If GlobalSegment is killed at the LocalLI->start, the call to find() 1189 // returned the next global segment. But if GlobalSegment overlaps with 1190 // LocalLI->start, then advance to the next segement. If a hole in GlobalLI 1191 // exists in LocalLI's vicinity, GlobalSegment will be the end of the hole. 1192 if (GlobalSegment->contains(LocalLI->beginIndex())) 1193 ++GlobalSegment; 1194 1195 if (GlobalSegment == GlobalLI->end()) 1196 return; 1197 1198 // Check if GlobalLI contains a hole in the vicinity of LocalLI. 1199 if (GlobalSegment != GlobalLI->begin()) { 1200 // Two address defs have no hole. 1201 if (SlotIndex::isSameInstr(llvm::prior(GlobalSegment)->end, 1202 GlobalSegment->start)) { 1203 return; 1204 } 1205 // If the prior global segment may be defined by the same two-address 1206 // instruction that also defines LocalLI, then can't make a hole here. 1207 if (SlotIndex::isSameInstr(llvm::prior(GlobalSegment)->start, 1208 LocalLI->beginIndex())) { 1209 return; 1210 } 1211 // If GlobalLI has a prior segment, it must be live into the EBB. Otherwise 1212 // it would be a disconnected component in the live range. 1213 assert(llvm::prior(GlobalSegment)->start < LocalLI->beginIndex() && 1214 "Disconnected LRG within the scheduling region."); 1215 } 1216 MachineInstr *GlobalDef = LIS->getInstructionFromIndex(GlobalSegment->start); 1217 if (!GlobalDef) 1218 return; 1219 1220 SUnit *GlobalSU = DAG->getSUnit(GlobalDef); 1221 if (!GlobalSU) 1222 return; 1223 1224 // GlobalDef is the bottom of the GlobalLI hole. Open the hole by 1225 // constraining the uses of the last local def to precede GlobalDef. 1226 SmallVector<SUnit*,8> LocalUses; 1227 const VNInfo *LastLocalVN = LocalLI->getVNInfoBefore(LocalLI->endIndex()); 1228 MachineInstr *LastLocalDef = LIS->getInstructionFromIndex(LastLocalVN->def); 1229 SUnit *LastLocalSU = DAG->getSUnit(LastLocalDef); 1230 for (SUnit::const_succ_iterator 1231 I = LastLocalSU->Succs.begin(), E = LastLocalSU->Succs.end(); 1232 I != E; ++I) { 1233 if (I->getKind() != SDep::Data || I->getReg() != LocalReg) 1234 continue; 1235 if (I->getSUnit() == GlobalSU) 1236 continue; 1237 if (!DAG->canAddEdge(GlobalSU, I->getSUnit())) 1238 return; 1239 LocalUses.push_back(I->getSUnit()); 1240 } 1241 // Open the top of the GlobalLI hole by constraining any earlier global uses 1242 // to precede the start of LocalLI. 1243 SmallVector<SUnit*,8> GlobalUses; 1244 MachineInstr *FirstLocalDef = 1245 LIS->getInstructionFromIndex(LocalLI->beginIndex()); 1246 SUnit *FirstLocalSU = DAG->getSUnit(FirstLocalDef); 1247 for (SUnit::const_pred_iterator 1248 I = GlobalSU->Preds.begin(), E = GlobalSU->Preds.end(); I != E; ++I) { 1249 if (I->getKind() != SDep::Anti || I->getReg() != GlobalReg) 1250 continue; 1251 if (I->getSUnit() == FirstLocalSU) 1252 continue; 1253 if (!DAG->canAddEdge(FirstLocalSU, I->getSUnit())) 1254 return; 1255 GlobalUses.push_back(I->getSUnit()); 1256 } 1257 DEBUG(dbgs() << "Constraining copy SU(" << CopySU->NodeNum << ")\n"); 1258 // Add the weak edges. 1259 for (SmallVectorImpl<SUnit*>::const_iterator 1260 I = LocalUses.begin(), E = LocalUses.end(); I != E; ++I) { 1261 DEBUG(dbgs() << " Local use SU(" << (*I)->NodeNum << ") -> SU(" 1262 << GlobalSU->NodeNum << ")\n"); 1263 DAG->addEdge(GlobalSU, SDep(*I, SDep::Weak)); 1264 } 1265 for (SmallVectorImpl<SUnit*>::const_iterator 1266 I = GlobalUses.begin(), E = GlobalUses.end(); I != E; ++I) { 1267 DEBUG(dbgs() << " Global use SU(" << (*I)->NodeNum << ") -> SU(" 1268 << FirstLocalSU->NodeNum << ")\n"); 1269 DAG->addEdge(FirstLocalSU, SDep(*I, SDep::Weak)); 1270 } 1271} 1272 1273/// \brief Callback from DAG postProcessing to create weak edges to encourage 1274/// copy elimination. 1275void CopyConstrain::apply(ScheduleDAGMI *DAG) { 1276 MachineBasicBlock::iterator FirstPos = nextIfDebug(DAG->begin(), DAG->end()); 1277 if (FirstPos == DAG->end()) 1278 return; 1279 RegionBeginIdx = DAG->getLIS()->getInstructionIndex(&*FirstPos); 1280 RegionEndIdx = DAG->getLIS()->getInstructionIndex( 1281 &*priorNonDebug(DAG->end(), DAG->begin())); 1282 1283 for (unsigned Idx = 0, End = DAG->SUnits.size(); Idx != End; ++Idx) { 1284 SUnit *SU = &DAG->SUnits[Idx]; 1285 if (!SU->getInstr()->isCopy()) 1286 continue; 1287 1288 constrainLocalCopy(SU, DAG); 1289 } 1290} 1291 1292//===----------------------------------------------------------------------===// 1293// ConvergingScheduler - Implementation of the generic MachineSchedStrategy. 1294//===----------------------------------------------------------------------===// 1295 1296namespace { 1297/// ConvergingScheduler shrinks the unscheduled zone using heuristics to balance 1298/// the schedule. 1299class ConvergingScheduler : public MachineSchedStrategy { 1300public: 1301 /// Represent the type of SchedCandidate found within a single queue. 1302 /// pickNodeBidirectional depends on these listed by decreasing priority. 1303 enum CandReason { 1304 NoCand, PhysRegCopy, RegExcess, RegCritical, Cluster, Weak, RegMax, 1305 ResourceReduce, ResourceDemand, BotHeightReduce, BotPathReduce, 1306 TopDepthReduce, TopPathReduce, NextDefUse, NodeOrder}; 1307 1308#ifndef NDEBUG 1309 static const char *getReasonStr(ConvergingScheduler::CandReason Reason); 1310#endif 1311 1312 /// Policy for scheduling the next instruction in the candidate's zone. 1313 struct CandPolicy { 1314 bool ReduceLatency; 1315 unsigned ReduceResIdx; 1316 unsigned DemandResIdx; 1317 1318 CandPolicy(): ReduceLatency(false), ReduceResIdx(0), DemandResIdx(0) {} 1319 }; 1320 1321 /// Status of an instruction's critical resource consumption. 1322 struct SchedResourceDelta { 1323 // Count critical resources in the scheduled region required by SU. 1324 unsigned CritResources; 1325 1326 // Count critical resources from another region consumed by SU. 1327 unsigned DemandedResources; 1328 1329 SchedResourceDelta(): CritResources(0), DemandedResources(0) {} 1330 1331 bool operator==(const SchedResourceDelta &RHS) const { 1332 return CritResources == RHS.CritResources 1333 && DemandedResources == RHS.DemandedResources; 1334 } 1335 bool operator!=(const SchedResourceDelta &RHS) const { 1336 return !operator==(RHS); 1337 } 1338 }; 1339 1340 /// Store the state used by ConvergingScheduler heuristics, required for the 1341 /// lifetime of one invocation of pickNode(). 1342 struct SchedCandidate { 1343 CandPolicy Policy; 1344 1345 // The best SUnit candidate. 1346 SUnit *SU; 1347 1348 // The reason for this candidate. 1349 CandReason Reason; 1350 1351 // Set of reasons that apply to multiple candidates. 1352 uint32_t RepeatReasonSet; 1353 1354 // Register pressure values for the best candidate. 1355 RegPressureDelta RPDelta; 1356 1357 // Critical resource consumption of the best candidate. 1358 SchedResourceDelta ResDelta; 1359 1360 SchedCandidate(const CandPolicy &policy) 1361 : Policy(policy), SU(NULL), Reason(NoCand), RepeatReasonSet(0) {} 1362 1363 bool isValid() const { return SU; } 1364 1365 // Copy the status of another candidate without changing policy. 1366 void setBest(SchedCandidate &Best) { 1367 assert(Best.Reason != NoCand && "uninitialized Sched candidate"); 1368 SU = Best.SU; 1369 Reason = Best.Reason; 1370 RPDelta = Best.RPDelta; 1371 ResDelta = Best.ResDelta; 1372 } 1373 1374 bool isRepeat(CandReason R) { return RepeatReasonSet & (1 << R); } 1375 void setRepeat(CandReason R) { RepeatReasonSet |= (1 << R); } 1376 1377 void initResourceDelta(const ScheduleDAGMI *DAG, 1378 const TargetSchedModel *SchedModel); 1379 }; 1380 1381 /// Summarize the unscheduled region. 1382 struct SchedRemainder { 1383 // Critical path through the DAG in expected latency. 1384 unsigned CriticalPath; 1385 unsigned CyclicCritPath; 1386 1387 // Scaled count of micro-ops left to schedule. 1388 unsigned RemIssueCount; 1389 1390 bool IsAcyclicLatencyLimited; 1391 1392 // Unscheduled resources 1393 SmallVector<unsigned, 16> RemainingCounts; 1394 1395 void reset() { 1396 CriticalPath = 0; 1397 CyclicCritPath = 0; 1398 RemIssueCount = 0; 1399 IsAcyclicLatencyLimited = false; 1400 RemainingCounts.clear(); 1401 } 1402 1403 SchedRemainder() { reset(); } 1404 1405 void init(ScheduleDAGMI *DAG, const TargetSchedModel *SchedModel); 1406 }; 1407 1408 /// Each Scheduling boundary is associated with ready queues. It tracks the 1409 /// current cycle in the direction of movement, and maintains the state 1410 /// of "hazards" and other interlocks at the current cycle. 1411 struct SchedBoundary { 1412 ScheduleDAGMI *DAG; 1413 const TargetSchedModel *SchedModel; 1414 SchedRemainder *Rem; 1415 1416 ReadyQueue Available; 1417 ReadyQueue Pending; 1418 bool CheckPending; 1419 1420 // For heuristics, keep a list of the nodes that immediately depend on the 1421 // most recently scheduled node. 1422 SmallPtrSet<const SUnit*, 8> NextSUs; 1423 1424 ScheduleHazardRecognizer *HazardRec; 1425 1426 /// Number of cycles it takes to issue the instructions scheduled in this 1427 /// zone. It is defined as: scheduled-micro-ops / issue-width + stalls. 1428 /// See getStalls(). 1429 unsigned CurrCycle; 1430 1431 /// Micro-ops issued in the current cycle 1432 unsigned CurrMOps; 1433 1434 /// MinReadyCycle - Cycle of the soonest available instruction. 1435 unsigned MinReadyCycle; 1436 1437 // The expected latency of the critical path in this scheduled zone. 1438 unsigned ExpectedLatency; 1439 1440 // The latency of dependence chains leading into this zone. 1441 // For each node scheduled bottom-up: DLat = max DLat, N.Depth. 1442 // For each cycle scheduled: DLat -= 1. 1443 unsigned DependentLatency; 1444 1445 /// Count the scheduled (issued) micro-ops that can be retired by 1446 /// time=CurrCycle assuming the first scheduled instr is retired at time=0. 1447 unsigned RetiredMOps; 1448 1449 // Count scheduled resources that have been executed. Resources are 1450 // considered executed if they become ready in the time that it takes to 1451 // saturate any resource including the one in question. Counts are scaled 1452 // for direct comparison with other resources. Counts can be compared with 1453 // MOps * getMicroOpFactor and Latency * getLatencyFactor. 1454 SmallVector<unsigned, 16> ExecutedResCounts; 1455 1456 /// Cache the max count for a single resource. 1457 unsigned MaxExecutedResCount; 1458 1459 // Cache the critical resources ID in this scheduled zone. 1460 unsigned ZoneCritResIdx; 1461 1462 // Is the scheduled region resource limited vs. latency limited. 1463 bool IsResourceLimited; 1464 1465#ifndef NDEBUG 1466 // Remember the greatest operand latency as an upper bound on the number of 1467 // times we should retry the pending queue because of a hazard. 1468 unsigned MaxObservedLatency; 1469#endif 1470 1471 void reset() { 1472 // A new HazardRec is created for each DAG and owned by SchedBoundary. 1473 // Destroying and reconstructing it is very expensive though. So keep 1474 // invalid, placeholder HazardRecs. 1475 if (HazardRec && HazardRec->isEnabled()) { 1476 delete HazardRec; 1477 HazardRec = 0; 1478 } 1479 Available.clear(); 1480 Pending.clear(); 1481 CheckPending = false; 1482 NextSUs.clear(); 1483 CurrCycle = 0; 1484 CurrMOps = 0; 1485 MinReadyCycle = UINT_MAX; 1486 ExpectedLatency = 0; 1487 DependentLatency = 0; 1488 RetiredMOps = 0; 1489 MaxExecutedResCount = 0; 1490 ZoneCritResIdx = 0; 1491 IsResourceLimited = false; 1492#ifndef NDEBUG 1493 MaxObservedLatency = 0; 1494#endif 1495 // Reserve a zero-count for invalid CritResIdx. 1496 ExecutedResCounts.resize(1); 1497 assert(!ExecutedResCounts[0] && "nonzero count for bad resource"); 1498 } 1499 1500 /// Pending queues extend the ready queues with the same ID and the 1501 /// PendingFlag set. 1502 SchedBoundary(unsigned ID, const Twine &Name): 1503 DAG(0), SchedModel(0), Rem(0), Available(ID, Name+".A"), 1504 Pending(ID << ConvergingScheduler::LogMaxQID, Name+".P"), 1505 HazardRec(0) { 1506 reset(); 1507 } 1508 1509 ~SchedBoundary() { delete HazardRec; } 1510 1511 void init(ScheduleDAGMI *dag, const TargetSchedModel *smodel, 1512 SchedRemainder *rem); 1513 1514 bool isTop() const { 1515 return Available.getID() == ConvergingScheduler::TopQID; 1516 } 1517 1518#ifndef NDEBUG 1519 const char *getResourceName(unsigned PIdx) { 1520 if (!PIdx) 1521 return "MOps"; 1522 return SchedModel->getProcResource(PIdx)->Name; 1523 } 1524#endif 1525 1526 /// Get the number of latency cycles "covered" by the scheduled 1527 /// instructions. This is the larger of the critical path within the zone 1528 /// and the number of cycles required to issue the instructions. 1529 unsigned getScheduledLatency() const { 1530 return std::max(ExpectedLatency, CurrCycle); 1531 } 1532 1533 unsigned getUnscheduledLatency(SUnit *SU) const { 1534 return isTop() ? SU->getHeight() : SU->getDepth(); 1535 } 1536 1537 unsigned getResourceCount(unsigned ResIdx) const { 1538 return ExecutedResCounts[ResIdx]; 1539 } 1540 1541 /// Get the scaled count of scheduled micro-ops and resources, including 1542 /// executed resources. 1543 unsigned getCriticalCount() const { 1544 if (!ZoneCritResIdx) 1545 return RetiredMOps * SchedModel->getMicroOpFactor(); 1546 return getResourceCount(ZoneCritResIdx); 1547 } 1548 1549 /// Get a scaled count for the minimum execution time of the scheduled 1550 /// micro-ops that are ready to execute by getExecutedCount. Notice the 1551 /// feedback loop. 1552 unsigned getExecutedCount() const { 1553 return std::max(CurrCycle * SchedModel->getLatencyFactor(), 1554 MaxExecutedResCount); 1555 } 1556 1557 bool checkHazard(SUnit *SU); 1558 1559 unsigned findMaxLatency(ArrayRef<SUnit*> ReadySUs); 1560 1561 unsigned getOtherResourceCount(unsigned &OtherCritIdx); 1562 1563 void setPolicy(CandPolicy &Policy, SchedBoundary &OtherZone); 1564 1565 void releaseNode(SUnit *SU, unsigned ReadyCycle); 1566 1567 void bumpCycle(unsigned NextCycle); 1568 1569 void incExecutedResources(unsigned PIdx, unsigned Count); 1570 1571 unsigned countResource(unsigned PIdx, unsigned Cycles, unsigned ReadyCycle); 1572 1573 void bumpNode(SUnit *SU); 1574 1575 void releasePending(); 1576 1577 void removeReady(SUnit *SU); 1578 1579 SUnit *pickOnlyChoice(); 1580 1581#ifndef NDEBUG 1582 void dumpScheduledState(); 1583#endif 1584 }; 1585 1586private: 1587 const MachineSchedContext *Context; 1588 ScheduleDAGMI *DAG; 1589 const TargetSchedModel *SchedModel; 1590 const TargetRegisterInfo *TRI; 1591 1592 // State of the top and bottom scheduled instruction boundaries. 1593 SchedRemainder Rem; 1594 SchedBoundary Top; 1595 SchedBoundary Bot; 1596 1597public: 1598 /// SUnit::NodeQueueId: 0 (none), 1 (top), 2 (bot), 3 (both) 1599 enum { 1600 TopQID = 1, 1601 BotQID = 2, 1602 LogMaxQID = 2 1603 }; 1604 1605 ConvergingScheduler(const MachineSchedContext *C): 1606 Context(C), DAG(0), SchedModel(0), TRI(0), 1607 Top(TopQID, "TopQ"), Bot(BotQID, "BotQ") {} 1608 1609 virtual bool shouldTrackPressure(unsigned NumRegionInstrs); 1610 1611 virtual void initialize(ScheduleDAGMI *dag); 1612 1613 virtual SUnit *pickNode(bool &IsTopNode); 1614 1615 virtual void schedNode(SUnit *SU, bool IsTopNode); 1616 1617 virtual void releaseTopNode(SUnit *SU); 1618 1619 virtual void releaseBottomNode(SUnit *SU); 1620 1621 virtual void registerRoots(); 1622 1623protected: 1624 void checkAcyclicLatency(); 1625 1626 void tryCandidate(SchedCandidate &Cand, 1627 SchedCandidate &TryCand, 1628 SchedBoundary &Zone, 1629 const RegPressureTracker &RPTracker, 1630 RegPressureTracker &TempTracker); 1631 1632 SUnit *pickNodeBidirectional(bool &IsTopNode); 1633 1634 void pickNodeFromQueue(SchedBoundary &Zone, 1635 const RegPressureTracker &RPTracker, 1636 SchedCandidate &Candidate); 1637 1638 void reschedulePhysRegCopies(SUnit *SU, bool isTop); 1639 1640#ifndef NDEBUG 1641 void traceCandidate(const SchedCandidate &Cand); 1642#endif 1643}; 1644} // namespace 1645 1646void ConvergingScheduler::SchedRemainder:: 1647init(ScheduleDAGMI *DAG, const TargetSchedModel *SchedModel) { 1648 reset(); 1649 if (!SchedModel->hasInstrSchedModel()) 1650 return; 1651 RemainingCounts.resize(SchedModel->getNumProcResourceKinds()); 1652 for (std::vector<SUnit>::iterator 1653 I = DAG->SUnits.begin(), E = DAG->SUnits.end(); I != E; ++I) { 1654 const MCSchedClassDesc *SC = DAG->getSchedClass(&*I); 1655 RemIssueCount += SchedModel->getNumMicroOps(I->getInstr(), SC) 1656 * SchedModel->getMicroOpFactor(); 1657 for (TargetSchedModel::ProcResIter 1658 PI = SchedModel->getWriteProcResBegin(SC), 1659 PE = SchedModel->getWriteProcResEnd(SC); PI != PE; ++PI) { 1660 unsigned PIdx = PI->ProcResourceIdx; 1661 unsigned Factor = SchedModel->getResourceFactor(PIdx); 1662 RemainingCounts[PIdx] += (Factor * PI->Cycles); 1663 } 1664 } 1665} 1666 1667void ConvergingScheduler::SchedBoundary:: 1668init(ScheduleDAGMI *dag, const TargetSchedModel *smodel, SchedRemainder *rem) { 1669 reset(); 1670 DAG = dag; 1671 SchedModel = smodel; 1672 Rem = rem; 1673 if (SchedModel->hasInstrSchedModel()) 1674 ExecutedResCounts.resize(SchedModel->getNumProcResourceKinds()); 1675} 1676 1677/// Avoid setting up the register pressure tracker for small regions to save 1678/// compile time. As a rough heuristic, only track pressure when the number 1679/// of schedulable instructions exceeds half the integer register file. 1680bool ConvergingScheduler::shouldTrackPressure(unsigned NumRegionInstrs) { 1681 unsigned NIntRegs = Context->RegClassInfo->getNumAllocatableRegs( 1682 Context->MF->getTarget().getTargetLowering()->getRegClassFor(MVT::i32)); 1683 1684 return NumRegionInstrs > (NIntRegs / 2); 1685} 1686 1687void ConvergingScheduler::initialize(ScheduleDAGMI *dag) { 1688 DAG = dag; 1689 SchedModel = DAG->getSchedModel(); 1690 TRI = DAG->TRI; 1691 1692 Rem.init(DAG, SchedModel); 1693 Top.init(DAG, SchedModel, &Rem); 1694 Bot.init(DAG, SchedModel, &Rem); 1695 1696 // Initialize resource counts. 1697 1698 // Initialize the HazardRecognizers. If itineraries don't exist, are empty, or 1699 // are disabled, then these HazardRecs will be disabled. 1700 const InstrItineraryData *Itin = SchedModel->getInstrItineraries(); 1701 const TargetMachine &TM = DAG->MF.getTarget(); 1702 if (!Top.HazardRec) { 1703 Top.HazardRec = 1704 TM.getInstrInfo()->CreateTargetMIHazardRecognizer(Itin, DAG); 1705 } 1706 if (!Bot.HazardRec) { 1707 Bot.HazardRec = 1708 TM.getInstrInfo()->CreateTargetMIHazardRecognizer(Itin, DAG); 1709 } 1710 assert((!ForceTopDown || !ForceBottomUp) && 1711 "-misched-topdown incompatible with -misched-bottomup"); 1712} 1713 1714void ConvergingScheduler::releaseTopNode(SUnit *SU) { 1715 if (SU->isScheduled) 1716 return; 1717 1718 for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); 1719 I != E; ++I) { 1720 if (I->isWeak()) 1721 continue; 1722 unsigned PredReadyCycle = I->getSUnit()->TopReadyCycle; 1723 unsigned Latency = I->getLatency(); 1724#ifndef NDEBUG 1725 Top.MaxObservedLatency = std::max(Latency, Top.MaxObservedLatency); 1726#endif 1727 if (SU->TopReadyCycle < PredReadyCycle + Latency) 1728 SU->TopReadyCycle = PredReadyCycle + Latency; 1729 } 1730 Top.releaseNode(SU, SU->TopReadyCycle); 1731} 1732 1733void ConvergingScheduler::releaseBottomNode(SUnit *SU) { 1734 if (SU->isScheduled) 1735 return; 1736 1737 assert(SU->getInstr() && "Scheduled SUnit must have instr"); 1738 1739 for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); 1740 I != E; ++I) { 1741 if (I->isWeak()) 1742 continue; 1743 unsigned SuccReadyCycle = I->getSUnit()->BotReadyCycle; 1744 unsigned Latency = I->getLatency(); 1745#ifndef NDEBUG 1746 Bot.MaxObservedLatency = std::max(Latency, Bot.MaxObservedLatency); 1747#endif 1748 if (SU->BotReadyCycle < SuccReadyCycle + Latency) 1749 SU->BotReadyCycle = SuccReadyCycle + Latency; 1750 } 1751 Bot.releaseNode(SU, SU->BotReadyCycle); 1752} 1753 1754/// Set IsAcyclicLatencyLimited if the acyclic path is longer than the cyclic 1755/// critical path by more cycles than it takes to drain the instruction buffer. 1756/// We estimate an upper bounds on in-flight instructions as: 1757/// 1758/// CyclesPerIteration = max( CyclicPath, Loop-Resource-Height ) 1759/// InFlightIterations = AcyclicPath / CyclesPerIteration 1760/// InFlightResources = InFlightIterations * LoopResources 1761/// 1762/// TODO: Check execution resources in addition to IssueCount. 1763void ConvergingScheduler::checkAcyclicLatency() { 1764 if (Rem.CyclicCritPath == 0 || Rem.CyclicCritPath >= Rem.CriticalPath) 1765 return; 1766 1767 // Scaled number of cycles per loop iteration. 1768 unsigned IterCount = 1769 std::max(Rem.CyclicCritPath * SchedModel->getLatencyFactor(), 1770 Rem.RemIssueCount); 1771 // Scaled acyclic critical path. 1772 unsigned AcyclicCount = Rem.CriticalPath * SchedModel->getLatencyFactor(); 1773 // InFlightCount = (AcyclicPath / IterCycles) * InstrPerLoop 1774 unsigned InFlightCount = 1775 (AcyclicCount * Rem.RemIssueCount + IterCount-1) / IterCount; 1776 unsigned BufferLimit = 1777 SchedModel->getMicroOpBufferSize() * SchedModel->getMicroOpFactor(); 1778 1779 Rem.IsAcyclicLatencyLimited = InFlightCount > BufferLimit; 1780 1781 DEBUG(dbgs() << "IssueCycles=" 1782 << Rem.RemIssueCount / SchedModel->getLatencyFactor() << "c " 1783 << "IterCycles=" << IterCount / SchedModel->getLatencyFactor() 1784 << "c NumIters=" << (AcyclicCount + IterCount-1) / IterCount 1785 << " InFlight=" << InFlightCount / SchedModel->getMicroOpFactor() 1786 << "m BufferLim=" << SchedModel->getMicroOpBufferSize() << "m\n"; 1787 if (Rem.IsAcyclicLatencyLimited) 1788 dbgs() << " ACYCLIC LATENCY LIMIT\n"); 1789} 1790 1791void ConvergingScheduler::registerRoots() { 1792 Rem.CriticalPath = DAG->ExitSU.getDepth(); 1793 1794 // Some roots may not feed into ExitSU. Check all of them in case. 1795 for (std::vector<SUnit*>::const_iterator 1796 I = Bot.Available.begin(), E = Bot.Available.end(); I != E; ++I) { 1797 if ((*I)->getDepth() > Rem.CriticalPath) 1798 Rem.CriticalPath = (*I)->getDepth(); 1799 } 1800 DEBUG(dbgs() << "Critical Path: " << Rem.CriticalPath << '\n'); 1801 1802 if (EnableCyclicPath) { 1803 Rem.CyclicCritPath = DAG->computeCyclicCriticalPath(); 1804 checkAcyclicLatency(); 1805 } 1806} 1807 1808/// Does this SU have a hazard within the current instruction group. 1809/// 1810/// The scheduler supports two modes of hazard recognition. The first is the 1811/// ScheduleHazardRecognizer API. It is a fully general hazard recognizer that 1812/// supports highly complicated in-order reservation tables 1813/// (ScoreboardHazardRecognizer) and arbitraty target-specific logic. 1814/// 1815/// The second is a streamlined mechanism that checks for hazards based on 1816/// simple counters that the scheduler itself maintains. It explicitly checks 1817/// for instruction dispatch limitations, including the number of micro-ops that 1818/// can dispatch per cycle. 1819/// 1820/// TODO: Also check whether the SU must start a new group. 1821bool ConvergingScheduler::SchedBoundary::checkHazard(SUnit *SU) { 1822 if (HazardRec->isEnabled()) 1823 return HazardRec->getHazardType(SU) != ScheduleHazardRecognizer::NoHazard; 1824 1825 unsigned uops = SchedModel->getNumMicroOps(SU->getInstr()); 1826 if ((CurrMOps > 0) && (CurrMOps + uops > SchedModel->getIssueWidth())) { 1827 DEBUG(dbgs() << " SU(" << SU->NodeNum << ") uops=" 1828 << SchedModel->getNumMicroOps(SU->getInstr()) << '\n'); 1829 return true; 1830 } 1831 return false; 1832} 1833 1834// Find the unscheduled node in ReadySUs with the highest latency. 1835unsigned ConvergingScheduler::SchedBoundary:: 1836findMaxLatency(ArrayRef<SUnit*> ReadySUs) { 1837 SUnit *LateSU = 0; 1838 unsigned RemLatency = 0; 1839 for (ArrayRef<SUnit*>::iterator I = ReadySUs.begin(), E = ReadySUs.end(); 1840 I != E; ++I) { 1841 unsigned L = getUnscheduledLatency(*I); 1842 if (L > RemLatency) { 1843 RemLatency = L; 1844 LateSU = *I; 1845 } 1846 } 1847 if (LateSU) { 1848 DEBUG(dbgs() << Available.getName() << " RemLatency SU(" 1849 << LateSU->NodeNum << ") " << RemLatency << "c\n"); 1850 } 1851 return RemLatency; 1852} 1853 1854// Count resources in this zone and the remaining unscheduled 1855// instruction. Return the max count, scaled. Set OtherCritIdx to the critical 1856// resource index, or zero if the zone is issue limited. 1857unsigned ConvergingScheduler::SchedBoundary:: 1858getOtherResourceCount(unsigned &OtherCritIdx) { 1859 OtherCritIdx = 0; 1860 if (!SchedModel->hasInstrSchedModel()) 1861 return 0; 1862 1863 unsigned OtherCritCount = Rem->RemIssueCount 1864 + (RetiredMOps * SchedModel->getMicroOpFactor()); 1865 DEBUG(dbgs() << " " << Available.getName() << " + Remain MOps: " 1866 << OtherCritCount / SchedModel->getMicroOpFactor() << '\n'); 1867 for (unsigned PIdx = 1, PEnd = SchedModel->getNumProcResourceKinds(); 1868 PIdx != PEnd; ++PIdx) { 1869 unsigned OtherCount = getResourceCount(PIdx) + Rem->RemainingCounts[PIdx]; 1870 if (OtherCount > OtherCritCount) { 1871 OtherCritCount = OtherCount; 1872 OtherCritIdx = PIdx; 1873 } 1874 } 1875 if (OtherCritIdx) { 1876 DEBUG(dbgs() << " " << Available.getName() << " + Remain CritRes: " 1877 << OtherCritCount / SchedModel->getResourceFactor(OtherCritIdx) 1878 << " " << getResourceName(OtherCritIdx) << "\n"); 1879 } 1880 return OtherCritCount; 1881} 1882 1883/// Set the CandPolicy for this zone given the current resources and latencies 1884/// inside and outside the zone. 1885void ConvergingScheduler::SchedBoundary::setPolicy(CandPolicy &Policy, 1886 SchedBoundary &OtherZone) { 1887 // Now that potential stalls have been considered, apply preemptive heuristics 1888 // based on the the total latency and resources inside and outside this 1889 // zone. 1890 1891 // Compute remaining latency. We need this both to determine whether the 1892 // overall schedule has become latency-limited and whether the instructions 1893 // outside this zone are resource or latency limited. 1894 // 1895 // The "dependent" latency is updated incrementally during scheduling as the 1896 // max height/depth of scheduled nodes minus the cycles since it was 1897 // scheduled: 1898 // DLat = max (N.depth - (CurrCycle - N.ReadyCycle) for N in Zone 1899 // 1900 // The "independent" latency is the max ready queue depth: 1901 // ILat = max N.depth for N in Available|Pending 1902 // 1903 // RemainingLatency is the greater of independent and dependent latency. 1904 unsigned RemLatency = DependentLatency; 1905 RemLatency = std::max(RemLatency, findMaxLatency(Available.elements())); 1906 RemLatency = std::max(RemLatency, findMaxLatency(Pending.elements())); 1907 1908 // Compute the critical resource outside the zone. 1909 unsigned OtherCritIdx; 1910 unsigned OtherCount = OtherZone.getOtherResourceCount(OtherCritIdx); 1911 1912 bool OtherResLimited = false; 1913 if (SchedModel->hasInstrSchedModel()) { 1914 unsigned LFactor = SchedModel->getLatencyFactor(); 1915 OtherResLimited = (int)(OtherCount - (RemLatency * LFactor)) > (int)LFactor; 1916 } 1917 if (!OtherResLimited && (RemLatency + CurrCycle > Rem->CriticalPath)) { 1918 Policy.ReduceLatency |= true; 1919 DEBUG(dbgs() << " " << Available.getName() << " RemainingLatency " 1920 << RemLatency << " + " << CurrCycle << "c > CritPath " 1921 << Rem->CriticalPath << "\n"); 1922 } 1923 // If the same resource is limiting inside and outside the zone, do nothing. 1924 if (ZoneCritResIdx == OtherCritIdx) 1925 return; 1926 1927 DEBUG( 1928 if (IsResourceLimited) { 1929 dbgs() << " " << Available.getName() << " ResourceLimited: " 1930 << getResourceName(ZoneCritResIdx) << "\n"; 1931 } 1932 if (OtherResLimited) 1933 dbgs() << " RemainingLimit: " << getResourceName(OtherCritIdx) << "\n"; 1934 if (!IsResourceLimited && !OtherResLimited) 1935 dbgs() << " Latency limited both directions.\n"); 1936 1937 if (IsResourceLimited && !Policy.ReduceResIdx) 1938 Policy.ReduceResIdx = ZoneCritResIdx; 1939 1940 if (OtherResLimited) 1941 Policy.DemandResIdx = OtherCritIdx; 1942} 1943 1944void ConvergingScheduler::SchedBoundary::releaseNode(SUnit *SU, 1945 unsigned ReadyCycle) { 1946 if (ReadyCycle < MinReadyCycle) 1947 MinReadyCycle = ReadyCycle; 1948 1949 // Check for interlocks first. For the purpose of other heuristics, an 1950 // instruction that cannot issue appears as if it's not in the ReadyQueue. 1951 bool IsBuffered = SchedModel->getMicroOpBufferSize() != 0; 1952 if ((!IsBuffered && ReadyCycle > CurrCycle) || checkHazard(SU)) 1953 Pending.push(SU); 1954 else 1955 Available.push(SU); 1956 1957 // Record this node as an immediate dependent of the scheduled node. 1958 NextSUs.insert(SU); 1959} 1960 1961/// Move the boundary of scheduled code by one cycle. 1962void ConvergingScheduler::SchedBoundary::bumpCycle(unsigned NextCycle) { 1963 if (SchedModel->getMicroOpBufferSize() == 0) { 1964 assert(MinReadyCycle < UINT_MAX && "MinReadyCycle uninitialized"); 1965 if (MinReadyCycle > NextCycle) 1966 NextCycle = MinReadyCycle; 1967 } 1968 // Update the current micro-ops, which will issue in the next cycle. 1969 unsigned DecMOps = SchedModel->getIssueWidth() * (NextCycle - CurrCycle); 1970 CurrMOps = (CurrMOps <= DecMOps) ? 0 : CurrMOps - DecMOps; 1971 1972 // Decrement DependentLatency based on the next cycle. 1973 if ((NextCycle - CurrCycle) > DependentLatency) 1974 DependentLatency = 0; 1975 else 1976 DependentLatency -= (NextCycle - CurrCycle); 1977 1978 if (!HazardRec->isEnabled()) { 1979 // Bypass HazardRec virtual calls. 1980 CurrCycle = NextCycle; 1981 } 1982 else { 1983 // Bypass getHazardType calls in case of long latency. 1984 for (; CurrCycle != NextCycle; ++CurrCycle) { 1985 if (isTop()) 1986 HazardRec->AdvanceCycle(); 1987 else 1988 HazardRec->RecedeCycle(); 1989 } 1990 } 1991 CheckPending = true; 1992 unsigned LFactor = SchedModel->getLatencyFactor(); 1993 IsResourceLimited = 1994 (int)(getCriticalCount() - (getScheduledLatency() * LFactor)) 1995 > (int)LFactor; 1996 1997 DEBUG(dbgs() << "Cycle: " << CurrCycle << ' ' << Available.getName() << '\n'); 1998} 1999 2000void ConvergingScheduler::SchedBoundary::incExecutedResources(unsigned PIdx, 2001 unsigned Count) { 2002 ExecutedResCounts[PIdx] += Count; 2003 if (ExecutedResCounts[PIdx] > MaxExecutedResCount) 2004 MaxExecutedResCount = ExecutedResCounts[PIdx]; 2005} 2006 2007/// Add the given processor resource to this scheduled zone. 2008/// 2009/// \param Cycles indicates the number of consecutive (non-pipelined) cycles 2010/// during which this resource is consumed. 2011/// 2012/// \return the next cycle at which the instruction may execute without 2013/// oversubscribing resources. 2014unsigned ConvergingScheduler::SchedBoundary:: 2015countResource(unsigned PIdx, unsigned Cycles, unsigned ReadyCycle) { 2016 unsigned Factor = SchedModel->getResourceFactor(PIdx); 2017 unsigned Count = Factor * Cycles; 2018 DEBUG(dbgs() << " " << getResourceName(PIdx) 2019 << " +" << Cycles << "x" << Factor << "u\n"); 2020 2021 // Update Executed resources counts. 2022 incExecutedResources(PIdx, Count); 2023 assert(Rem->RemainingCounts[PIdx] >= Count && "resource double counted"); 2024 Rem->RemainingCounts[PIdx] -= Count; 2025 2026 // Check if this resource exceeds the current critical resource. If so, it 2027 // becomes the critical resource. 2028 if (ZoneCritResIdx != PIdx && (getResourceCount(PIdx) > getCriticalCount())) { 2029 ZoneCritResIdx = PIdx; 2030 DEBUG(dbgs() << " *** Critical resource " 2031 << getResourceName(PIdx) << ": " 2032 << getResourceCount(PIdx) / SchedModel->getLatencyFactor() << "c\n"); 2033 } 2034 // TODO: We don't yet model reserved resources. It's not hard though. 2035 return CurrCycle; 2036} 2037 2038/// Move the boundary of scheduled code by one SUnit. 2039void ConvergingScheduler::SchedBoundary::bumpNode(SUnit *SU) { 2040 // Update the reservation table. 2041 if (HazardRec->isEnabled()) { 2042 if (!isTop() && SU->isCall) { 2043 // Calls are scheduled with their preceding instructions. For bottom-up 2044 // scheduling, clear the pipeline state before emitting. 2045 HazardRec->Reset(); 2046 } 2047 HazardRec->EmitInstruction(SU); 2048 } 2049 const MCSchedClassDesc *SC = DAG->getSchedClass(SU); 2050 unsigned IncMOps = SchedModel->getNumMicroOps(SU->getInstr()); 2051 CurrMOps += IncMOps; 2052 // checkHazard prevents scheduling multiple instructions per cycle that exceed 2053 // issue width. However, we commonly reach the maximum. In this case 2054 // opportunistically bump the cycle to avoid uselessly checking everything in 2055 // the readyQ. Furthermore, a single instruction may produce more than one 2056 // cycle's worth of micro-ops. 2057 // 2058 // TODO: Also check if this SU must end a dispatch group. 2059 unsigned NextCycle = CurrCycle; 2060 if (CurrMOps >= SchedModel->getIssueWidth()) { 2061 ++NextCycle; 2062 DEBUG(dbgs() << " *** Max MOps " << CurrMOps 2063 << " at cycle " << CurrCycle << '\n'); 2064 } 2065 unsigned ReadyCycle = (isTop() ? SU->TopReadyCycle : SU->BotReadyCycle); 2066 DEBUG(dbgs() << " Ready @" << ReadyCycle << "c\n"); 2067 2068 switch (SchedModel->getMicroOpBufferSize()) { 2069 case 0: 2070 assert(ReadyCycle <= CurrCycle && "Broken PendingQueue"); 2071 break; 2072 case 1: 2073 if (ReadyCycle > NextCycle) { 2074 NextCycle = ReadyCycle; 2075 DEBUG(dbgs() << " *** Stall until: " << ReadyCycle << "\n"); 2076 } 2077 break; 2078 default: 2079 // We don't currently model the OOO reorder buffer, so consider all 2080 // scheduled MOps to be "retired". 2081 break; 2082 } 2083 RetiredMOps += IncMOps; 2084 2085 // Update resource counts and critical resource. 2086 if (SchedModel->hasInstrSchedModel()) { 2087 unsigned DecRemIssue = IncMOps * SchedModel->getMicroOpFactor(); 2088 assert(Rem->RemIssueCount >= DecRemIssue && "MOps double counted"); 2089 Rem->RemIssueCount -= DecRemIssue; 2090 if (ZoneCritResIdx) { 2091 // Scale scheduled micro-ops for comparing with the critical resource. 2092 unsigned ScaledMOps = 2093 RetiredMOps * SchedModel->getMicroOpFactor(); 2094 2095 // If scaled micro-ops are now more than the previous critical resource by 2096 // a full cycle, then micro-ops issue becomes critical. 2097 if ((int)(ScaledMOps - getResourceCount(ZoneCritResIdx)) 2098 >= (int)SchedModel->getLatencyFactor()) { 2099 ZoneCritResIdx = 0; 2100 DEBUG(dbgs() << " *** Critical resource NumMicroOps: " 2101 << ScaledMOps / SchedModel->getLatencyFactor() << "c\n"); 2102 } 2103 } 2104 for (TargetSchedModel::ProcResIter 2105 PI = SchedModel->getWriteProcResBegin(SC), 2106 PE = SchedModel->getWriteProcResEnd(SC); PI != PE; ++PI) { 2107 unsigned RCycle = 2108 countResource(PI->ProcResourceIdx, PI->Cycles, ReadyCycle); 2109 if (RCycle > NextCycle) 2110 NextCycle = RCycle; 2111 } 2112 } 2113 // Update ExpectedLatency and DependentLatency. 2114 unsigned &TopLatency = isTop() ? ExpectedLatency : DependentLatency; 2115 unsigned &BotLatency = isTop() ? DependentLatency : ExpectedLatency; 2116 if (SU->getDepth() > TopLatency) { 2117 TopLatency = SU->getDepth(); 2118 DEBUG(dbgs() << " " << Available.getName() 2119 << " TopLatency SU(" << SU->NodeNum << ") " << TopLatency << "c\n"); 2120 } 2121 if (SU->getHeight() > BotLatency) { 2122 BotLatency = SU->getHeight(); 2123 DEBUG(dbgs() << " " << Available.getName() 2124 << " BotLatency SU(" << SU->NodeNum << ") " << BotLatency << "c\n"); 2125 } 2126 // If we stall for any reason, bump the cycle. 2127 if (NextCycle > CurrCycle) { 2128 bumpCycle(NextCycle); 2129 } 2130 else { 2131 // After updating ZoneCritResIdx and ExpectedLatency, check if we're 2132 // resource limited. If a stall occured, bumpCycle does this. 2133 unsigned LFactor = SchedModel->getLatencyFactor(); 2134 IsResourceLimited = 2135 (int)(getCriticalCount() - (getScheduledLatency() * LFactor)) 2136 > (int)LFactor; 2137 } 2138 DEBUG(dumpScheduledState()); 2139} 2140 2141/// Release pending ready nodes in to the available queue. This makes them 2142/// visible to heuristics. 2143void ConvergingScheduler::SchedBoundary::releasePending() { 2144 // If the available queue is empty, it is safe to reset MinReadyCycle. 2145 if (Available.empty()) 2146 MinReadyCycle = UINT_MAX; 2147 2148 // Check to see if any of the pending instructions are ready to issue. If 2149 // so, add them to the available queue. 2150 bool IsBuffered = SchedModel->getMicroOpBufferSize() != 0; 2151 for (unsigned i = 0, e = Pending.size(); i != e; ++i) { 2152 SUnit *SU = *(Pending.begin()+i); 2153 unsigned ReadyCycle = isTop() ? SU->TopReadyCycle : SU->BotReadyCycle; 2154 2155 if (ReadyCycle < MinReadyCycle) 2156 MinReadyCycle = ReadyCycle; 2157 2158 if (!IsBuffered && ReadyCycle > CurrCycle) 2159 continue; 2160 2161 if (checkHazard(SU)) 2162 continue; 2163 2164 Available.push(SU); 2165 Pending.remove(Pending.begin()+i); 2166 --i; --e; 2167 } 2168 DEBUG(if (!Pending.empty()) Pending.dump()); 2169 CheckPending = false; 2170} 2171 2172/// Remove SU from the ready set for this boundary. 2173void ConvergingScheduler::SchedBoundary::removeReady(SUnit *SU) { 2174 if (Available.isInQueue(SU)) 2175 Available.remove(Available.find(SU)); 2176 else { 2177 assert(Pending.isInQueue(SU) && "bad ready count"); 2178 Pending.remove(Pending.find(SU)); 2179 } 2180} 2181 2182/// If this queue only has one ready candidate, return it. As a side effect, 2183/// defer any nodes that now hit a hazard, and advance the cycle until at least 2184/// one node is ready. If multiple instructions are ready, return NULL. 2185SUnit *ConvergingScheduler::SchedBoundary::pickOnlyChoice() { 2186 if (CheckPending) 2187 releasePending(); 2188 2189 if (CurrMOps > 0) { 2190 // Defer any ready instrs that now have a hazard. 2191 for (ReadyQueue::iterator I = Available.begin(); I != Available.end();) { 2192 if (checkHazard(*I)) { 2193 Pending.push(*I); 2194 I = Available.remove(I); 2195 continue; 2196 } 2197 ++I; 2198 } 2199 } 2200 for (unsigned i = 0; Available.empty(); ++i) { 2201 assert(i <= (HazardRec->getMaxLookAhead() + MaxObservedLatency) && 2202 "permanent hazard"); (void)i; 2203 bumpCycle(CurrCycle + 1); 2204 releasePending(); 2205 } 2206 if (Available.size() == 1) 2207 return *Available.begin(); 2208 return NULL; 2209} 2210 2211#ifndef NDEBUG 2212// This is useful information to dump after bumpNode. 2213// Note that the Queue contents are more useful before pickNodeFromQueue. 2214void ConvergingScheduler::SchedBoundary::dumpScheduledState() { 2215 unsigned ResFactor; 2216 unsigned ResCount; 2217 if (ZoneCritResIdx) { 2218 ResFactor = SchedModel->getResourceFactor(ZoneCritResIdx); 2219 ResCount = getResourceCount(ZoneCritResIdx); 2220 } 2221 else { 2222 ResFactor = SchedModel->getMicroOpFactor(); 2223 ResCount = RetiredMOps * SchedModel->getMicroOpFactor(); 2224 } 2225 unsigned LFactor = SchedModel->getLatencyFactor(); 2226 dbgs() << Available.getName() << " @" << CurrCycle << "c\n" 2227 << " Retired: " << RetiredMOps; 2228 dbgs() << "\n Executed: " << getExecutedCount() / LFactor << "c"; 2229 dbgs() << "\n Critical: " << ResCount / LFactor << "c, " 2230 << ResCount / ResFactor << " " << getResourceName(ZoneCritResIdx) 2231 << "\n ExpectedLatency: " << ExpectedLatency << "c\n" 2232 << (IsResourceLimited ? " - Resource" : " - Latency") 2233 << " limited.\n"; 2234} 2235#endif 2236 2237void ConvergingScheduler::SchedCandidate:: 2238initResourceDelta(const ScheduleDAGMI *DAG, 2239 const TargetSchedModel *SchedModel) { 2240 if (!Policy.ReduceResIdx && !Policy.DemandResIdx) 2241 return; 2242 2243 const MCSchedClassDesc *SC = DAG->getSchedClass(SU); 2244 for (TargetSchedModel::ProcResIter 2245 PI = SchedModel->getWriteProcResBegin(SC), 2246 PE = SchedModel->getWriteProcResEnd(SC); PI != PE; ++PI) { 2247 if (PI->ProcResourceIdx == Policy.ReduceResIdx) 2248 ResDelta.CritResources += PI->Cycles; 2249 if (PI->ProcResourceIdx == Policy.DemandResIdx) 2250 ResDelta.DemandedResources += PI->Cycles; 2251 } 2252} 2253 2254 2255/// Return true if this heuristic determines order. 2256static bool tryLess(int TryVal, int CandVal, 2257 ConvergingScheduler::SchedCandidate &TryCand, 2258 ConvergingScheduler::SchedCandidate &Cand, 2259 ConvergingScheduler::CandReason Reason) { 2260 if (TryVal < CandVal) { 2261 TryCand.Reason = Reason; 2262 return true; 2263 } 2264 if (TryVal > CandVal) { 2265 if (Cand.Reason > Reason) 2266 Cand.Reason = Reason; 2267 return true; 2268 } 2269 Cand.setRepeat(Reason); 2270 return false; 2271} 2272 2273static bool tryGreater(int TryVal, int CandVal, 2274 ConvergingScheduler::SchedCandidate &TryCand, 2275 ConvergingScheduler::SchedCandidate &Cand, 2276 ConvergingScheduler::CandReason Reason) { 2277 if (TryVal > CandVal) { 2278 TryCand.Reason = Reason; 2279 return true; 2280 } 2281 if (TryVal < CandVal) { 2282 if (Cand.Reason > Reason) 2283 Cand.Reason = Reason; 2284 return true; 2285 } 2286 Cand.setRepeat(Reason); 2287 return false; 2288} 2289 2290static bool tryPressure(const PressureChange &TryP, 2291 const PressureChange &CandP, 2292 ConvergingScheduler::SchedCandidate &TryCand, 2293 ConvergingScheduler::SchedCandidate &Cand, 2294 ConvergingScheduler::CandReason Reason) { 2295 int TryRank = TryP.getPSetOrMax(); 2296 int CandRank = CandP.getPSetOrMax(); 2297 // If both candidates affect the same set, go with the smallest increase. 2298 if (TryRank == CandRank) { 2299 return tryLess(TryP.getUnitInc(), CandP.getUnitInc(), TryCand, Cand, 2300 Reason); 2301 } 2302 // If one candidate decreases and the other increases, go with it. 2303 // Invalid candidates have UnitInc==0. 2304 if (tryLess(TryP.getUnitInc() < 0, CandP.getUnitInc() < 0, TryCand, Cand, 2305 Reason)) { 2306 return true; 2307 } 2308 // If the candidates are decreasing pressure, reverse priority. 2309 if (TryP.getUnitInc() < 0) 2310 std::swap(TryRank, CandRank); 2311 return tryGreater(TryRank, CandRank, TryCand, Cand, Reason); 2312} 2313 2314static unsigned getWeakLeft(const SUnit *SU, bool isTop) { 2315 return (isTop) ? SU->WeakPredsLeft : SU->WeakSuccsLeft; 2316} 2317 2318/// Minimize physical register live ranges. Regalloc wants them adjacent to 2319/// their physreg def/use. 2320/// 2321/// FIXME: This is an unnecessary check on the critical path. Most are root/leaf 2322/// copies which can be prescheduled. The rest (e.g. x86 MUL) could be bundled 2323/// with the operation that produces or consumes the physreg. We'll do this when 2324/// regalloc has support for parallel copies. 2325static int biasPhysRegCopy(const SUnit *SU, bool isTop) { 2326 const MachineInstr *MI = SU->getInstr(); 2327 if (!MI->isCopy()) 2328 return 0; 2329 2330 unsigned ScheduledOper = isTop ? 1 : 0; 2331 unsigned UnscheduledOper = isTop ? 0 : 1; 2332 // If we have already scheduled the physreg produce/consumer, immediately 2333 // schedule the copy. 2334 if (TargetRegisterInfo::isPhysicalRegister( 2335 MI->getOperand(ScheduledOper).getReg())) 2336 return 1; 2337 // If the physreg is at the boundary, defer it. Otherwise schedule it 2338 // immediately to free the dependent. We can hoist the copy later. 2339 bool AtBoundary = isTop ? !SU->NumSuccsLeft : !SU->NumPredsLeft; 2340 if (TargetRegisterInfo::isPhysicalRegister( 2341 MI->getOperand(UnscheduledOper).getReg())) 2342 return AtBoundary ? -1 : 1; 2343 return 0; 2344} 2345 2346static bool tryLatency(ConvergingScheduler::SchedCandidate &TryCand, 2347 ConvergingScheduler::SchedCandidate &Cand, 2348 ConvergingScheduler::SchedBoundary &Zone) { 2349 if (Zone.isTop()) { 2350 if (Cand.SU->getDepth() > Zone.getScheduledLatency()) { 2351 if (tryLess(TryCand.SU->getDepth(), Cand.SU->getDepth(), 2352 TryCand, Cand, ConvergingScheduler::TopDepthReduce)) 2353 return true; 2354 } 2355 if (tryGreater(TryCand.SU->getHeight(), Cand.SU->getHeight(), 2356 TryCand, Cand, ConvergingScheduler::TopPathReduce)) 2357 return true; 2358 } 2359 else { 2360 if (Cand.SU->getHeight() > Zone.getScheduledLatency()) { 2361 if (tryLess(TryCand.SU->getHeight(), Cand.SU->getHeight(), 2362 TryCand, Cand, ConvergingScheduler::BotHeightReduce)) 2363 return true; 2364 } 2365 if (tryGreater(TryCand.SU->getDepth(), Cand.SU->getDepth(), 2366 TryCand, Cand, ConvergingScheduler::BotPathReduce)) 2367 return true; 2368 } 2369 return false; 2370} 2371 2372/// Apply a set of heursitics to a new candidate. Heuristics are currently 2373/// hierarchical. This may be more efficient than a graduated cost model because 2374/// we don't need to evaluate all aspects of the model for each node in the 2375/// queue. But it's really done to make the heuristics easier to debug and 2376/// statistically analyze. 2377/// 2378/// \param Cand provides the policy and current best candidate. 2379/// \param TryCand refers to the next SUnit candidate, otherwise uninitialized. 2380/// \param Zone describes the scheduled zone that we are extending. 2381/// \param RPTracker describes reg pressure within the scheduled zone. 2382/// \param TempTracker is a scratch pressure tracker to reuse in queries. 2383void ConvergingScheduler::tryCandidate(SchedCandidate &Cand, 2384 SchedCandidate &TryCand, 2385 SchedBoundary &Zone, 2386 const RegPressureTracker &RPTracker, 2387 RegPressureTracker &TempTracker) { 2388 2389 if (DAG->isTrackingPressure()) { 2390 // Always initialize TryCand's RPDelta. 2391 if (Zone.isTop()) { 2392 TempTracker.getMaxDownwardPressureDelta( 2393 TryCand.SU->getInstr(), 2394 TryCand.RPDelta, 2395 DAG->getRegionCriticalPSets(), 2396 DAG->getRegPressure().MaxSetPressure); 2397 } 2398 else { 2399 if (VerifyScheduling) { 2400 TempTracker.getMaxUpwardPressureDelta( 2401 TryCand.SU->getInstr(), 2402 &DAG->getPressureDiff(TryCand.SU), 2403 TryCand.RPDelta, 2404 DAG->getRegionCriticalPSets(), 2405 DAG->getRegPressure().MaxSetPressure); 2406 } 2407 else { 2408 RPTracker.getUpwardPressureDelta( 2409 TryCand.SU->getInstr(), 2410 DAG->getPressureDiff(TryCand.SU), 2411 TryCand.RPDelta, 2412 DAG->getRegionCriticalPSets(), 2413 DAG->getRegPressure().MaxSetPressure); 2414 } 2415 } 2416 } 2417 2418 // Initialize the candidate if needed. 2419 if (!Cand.isValid()) { 2420 TryCand.Reason = NodeOrder; 2421 return; 2422 } 2423 2424 if (tryGreater(biasPhysRegCopy(TryCand.SU, Zone.isTop()), 2425 biasPhysRegCopy(Cand.SU, Zone.isTop()), 2426 TryCand, Cand, PhysRegCopy)) 2427 return; 2428 2429 // Avoid exceeding the target's limit. If signed PSetID is negative, it is 2430 // invalid; convert it to INT_MAX to give it lowest priority. 2431 if (DAG->isTrackingPressure() && tryPressure(TryCand.RPDelta.Excess, 2432 Cand.RPDelta.Excess, 2433 TryCand, Cand, RegExcess)) 2434 return; 2435 2436 // For loops that are acyclic path limited, aggressively schedule for latency. 2437 if (Rem.IsAcyclicLatencyLimited && tryLatency(TryCand, Cand, Zone)) 2438 return; 2439 2440 // Avoid increasing the max critical pressure in the scheduled region. 2441 if (DAG->isTrackingPressure() && tryPressure(TryCand.RPDelta.CriticalMax, 2442 Cand.RPDelta.CriticalMax, 2443 TryCand, Cand, RegCritical)) 2444 return; 2445 2446 // Keep clustered nodes together to encourage downstream peephole 2447 // optimizations which may reduce resource requirements. 2448 // 2449 // This is a best effort to set things up for a post-RA pass. Optimizations 2450 // like generating loads of multiple registers should ideally be done within 2451 // the scheduler pass by combining the loads during DAG postprocessing. 2452 const SUnit *NextClusterSU = 2453 Zone.isTop() ? DAG->getNextClusterSucc() : DAG->getNextClusterPred(); 2454 if (tryGreater(TryCand.SU == NextClusterSU, Cand.SU == NextClusterSU, 2455 TryCand, Cand, Cluster)) 2456 return; 2457 2458 // Weak edges are for clustering and other constraints. 2459 if (tryLess(getWeakLeft(TryCand.SU, Zone.isTop()), 2460 getWeakLeft(Cand.SU, Zone.isTop()), 2461 TryCand, Cand, Weak)) { 2462 return; 2463 } 2464 // Avoid increasing the max pressure of the entire region. 2465 if (DAG->isTrackingPressure() && tryPressure(TryCand.RPDelta.CurrentMax, 2466 Cand.RPDelta.CurrentMax, 2467 TryCand, Cand, RegMax)) 2468 return; 2469 2470 // Avoid critical resource consumption and balance the schedule. 2471 TryCand.initResourceDelta(DAG, SchedModel); 2472 if (tryLess(TryCand.ResDelta.CritResources, Cand.ResDelta.CritResources, 2473 TryCand, Cand, ResourceReduce)) 2474 return; 2475 if (tryGreater(TryCand.ResDelta.DemandedResources, 2476 Cand.ResDelta.DemandedResources, 2477 TryCand, Cand, ResourceDemand)) 2478 return; 2479 2480 // Avoid serializing long latency dependence chains. 2481 // For acyclic path limited loops, latency was already checked above. 2482 if (Cand.Policy.ReduceLatency && !Rem.IsAcyclicLatencyLimited 2483 && tryLatency(TryCand, Cand, Zone)) { 2484 return; 2485 } 2486 2487 // Prefer immediate defs/users of the last scheduled instruction. This is a 2488 // local pressure avoidance strategy that also makes the machine code 2489 // readable. 2490 if (tryGreater(Zone.NextSUs.count(TryCand.SU), Zone.NextSUs.count(Cand.SU), 2491 TryCand, Cand, NextDefUse)) 2492 return; 2493 2494 // Fall through to original instruction order. 2495 if ((Zone.isTop() && TryCand.SU->NodeNum < Cand.SU->NodeNum) 2496 || (!Zone.isTop() && TryCand.SU->NodeNum > Cand.SU->NodeNum)) { 2497 TryCand.Reason = NodeOrder; 2498 } 2499} 2500 2501#ifndef NDEBUG 2502const char *ConvergingScheduler::getReasonStr( 2503 ConvergingScheduler::CandReason Reason) { 2504 switch (Reason) { 2505 case NoCand: return "NOCAND "; 2506 case PhysRegCopy: return "PREG-COPY"; 2507 case RegExcess: return "REG-EXCESS"; 2508 case RegCritical: return "REG-CRIT "; 2509 case Cluster: return "CLUSTER "; 2510 case Weak: return "WEAK "; 2511 case RegMax: return "REG-MAX "; 2512 case ResourceReduce: return "RES-REDUCE"; 2513 case ResourceDemand: return "RES-DEMAND"; 2514 case TopDepthReduce: return "TOP-DEPTH "; 2515 case TopPathReduce: return "TOP-PATH "; 2516 case BotHeightReduce:return "BOT-HEIGHT"; 2517 case BotPathReduce: return "BOT-PATH "; 2518 case NextDefUse: return "DEF-USE "; 2519 case NodeOrder: return "ORDER "; 2520 }; 2521 llvm_unreachable("Unknown reason!"); 2522} 2523 2524void ConvergingScheduler::traceCandidate(const SchedCandidate &Cand) { 2525 PressureChange P; 2526 unsigned ResIdx = 0; 2527 unsigned Latency = 0; 2528 switch (Cand.Reason) { 2529 default: 2530 break; 2531 case RegExcess: 2532 P = Cand.RPDelta.Excess; 2533 break; 2534 case RegCritical: 2535 P = Cand.RPDelta.CriticalMax; 2536 break; 2537 case RegMax: 2538 P = Cand.RPDelta.CurrentMax; 2539 break; 2540 case ResourceReduce: 2541 ResIdx = Cand.Policy.ReduceResIdx; 2542 break; 2543 case ResourceDemand: 2544 ResIdx = Cand.Policy.DemandResIdx; 2545 break; 2546 case TopDepthReduce: 2547 Latency = Cand.SU->getDepth(); 2548 break; 2549 case TopPathReduce: 2550 Latency = Cand.SU->getHeight(); 2551 break; 2552 case BotHeightReduce: 2553 Latency = Cand.SU->getHeight(); 2554 break; 2555 case BotPathReduce: 2556 Latency = Cand.SU->getDepth(); 2557 break; 2558 } 2559 dbgs() << " SU(" << Cand.SU->NodeNum << ") " << getReasonStr(Cand.Reason); 2560 if (P.isValid()) 2561 dbgs() << " " << TRI->getRegPressureSetName(P.getPSet()) 2562 << ":" << P.getUnitInc() << " "; 2563 else 2564 dbgs() << " "; 2565 if (ResIdx) 2566 dbgs() << " " << SchedModel->getProcResource(ResIdx)->Name << " "; 2567 else 2568 dbgs() << " "; 2569 if (Latency) 2570 dbgs() << " " << Latency << " cycles "; 2571 else 2572 dbgs() << " "; 2573 dbgs() << '\n'; 2574} 2575#endif 2576 2577/// Pick the best candidate from the top queue. 2578/// 2579/// TODO: getMaxPressureDelta results can be mostly cached for each SUnit during 2580/// DAG building. To adjust for the current scheduling location we need to 2581/// maintain the number of vreg uses remaining to be top-scheduled. 2582void ConvergingScheduler::pickNodeFromQueue(SchedBoundary &Zone, 2583 const RegPressureTracker &RPTracker, 2584 SchedCandidate &Cand) { 2585 ReadyQueue &Q = Zone.Available; 2586 2587 DEBUG(Q.dump()); 2588 2589 // getMaxPressureDelta temporarily modifies the tracker. 2590 RegPressureTracker &TempTracker = const_cast<RegPressureTracker&>(RPTracker); 2591 2592 for (ReadyQueue::iterator I = Q.begin(), E = Q.end(); I != E; ++I) { 2593 2594 SchedCandidate TryCand(Cand.Policy); 2595 TryCand.SU = *I; 2596 tryCandidate(Cand, TryCand, Zone, RPTracker, TempTracker); 2597 if (TryCand.Reason != NoCand) { 2598 // Initialize resource delta if needed in case future heuristics query it. 2599 if (TryCand.ResDelta == SchedResourceDelta()) 2600 TryCand.initResourceDelta(DAG, SchedModel); 2601 Cand.setBest(TryCand); 2602 DEBUG(traceCandidate(Cand)); 2603 } 2604 } 2605} 2606 2607static void tracePick(const ConvergingScheduler::SchedCandidate &Cand, 2608 bool IsTop) { 2609 DEBUG(dbgs() << "Pick " << (IsTop ? "Top " : "Bot ") 2610 << ConvergingScheduler::getReasonStr(Cand.Reason) << '\n'); 2611} 2612 2613/// Pick the best candidate node from either the top or bottom queue. 2614SUnit *ConvergingScheduler::pickNodeBidirectional(bool &IsTopNode) { 2615 // Schedule as far as possible in the direction of no choice. This is most 2616 // efficient, but also provides the best heuristics for CriticalPSets. 2617 if (SUnit *SU = Bot.pickOnlyChoice()) { 2618 IsTopNode = false; 2619 DEBUG(dbgs() << "Pick Bot NOCAND\n"); 2620 return SU; 2621 } 2622 if (SUnit *SU = Top.pickOnlyChoice()) { 2623 IsTopNode = true; 2624 DEBUG(dbgs() << "Pick Top NOCAND\n"); 2625 return SU; 2626 } 2627 CandPolicy NoPolicy; 2628 SchedCandidate BotCand(NoPolicy); 2629 SchedCandidate TopCand(NoPolicy); 2630 Bot.setPolicy(BotCand.Policy, Top); 2631 Top.setPolicy(TopCand.Policy, Bot); 2632 2633 // Prefer bottom scheduling when heuristics are silent. 2634 pickNodeFromQueue(Bot, DAG->getBotRPTracker(), BotCand); 2635 assert(BotCand.Reason != NoCand && "failed to find the first candidate"); 2636 2637 // If either Q has a single candidate that provides the least increase in 2638 // Excess pressure, we can immediately schedule from that Q. 2639 // 2640 // RegionCriticalPSets summarizes the pressure within the scheduled region and 2641 // affects picking from either Q. If scheduling in one direction must 2642 // increase pressure for one of the excess PSets, then schedule in that 2643 // direction first to provide more freedom in the other direction. 2644 if ((BotCand.Reason == RegExcess && !BotCand.isRepeat(RegExcess)) 2645 || (BotCand.Reason == RegCritical 2646 && !BotCand.isRepeat(RegCritical))) 2647 { 2648 IsTopNode = false; 2649 tracePick(BotCand, IsTopNode); 2650 return BotCand.SU; 2651 } 2652 // Check if the top Q has a better candidate. 2653 pickNodeFromQueue(Top, DAG->getTopRPTracker(), TopCand); 2654 assert(TopCand.Reason != NoCand && "failed to find the first candidate"); 2655 2656 // Choose the queue with the most important (lowest enum) reason. 2657 if (TopCand.Reason < BotCand.Reason) { 2658 IsTopNode = true; 2659 tracePick(TopCand, IsTopNode); 2660 return TopCand.SU; 2661 } 2662 // Otherwise prefer the bottom candidate, in node order if all else failed. 2663 IsTopNode = false; 2664 tracePick(BotCand, IsTopNode); 2665 return BotCand.SU; 2666} 2667 2668/// Pick the best node to balance the schedule. Implements MachineSchedStrategy. 2669SUnit *ConvergingScheduler::pickNode(bool &IsTopNode) { 2670 if (DAG->top() == DAG->bottom()) { 2671 assert(Top.Available.empty() && Top.Pending.empty() && 2672 Bot.Available.empty() && Bot.Pending.empty() && "ReadyQ garbage"); 2673 return NULL; 2674 } 2675 SUnit *SU; 2676 do { 2677 if (ForceTopDown) { 2678 SU = Top.pickOnlyChoice(); 2679 if (!SU) { 2680 CandPolicy NoPolicy; 2681 SchedCandidate TopCand(NoPolicy); 2682 pickNodeFromQueue(Top, DAG->getTopRPTracker(), TopCand); 2683 assert(TopCand.Reason != NoCand && "failed to find a candidate"); 2684 tracePick(TopCand, true); 2685 SU = TopCand.SU; 2686 } 2687 IsTopNode = true; 2688 } 2689 else if (ForceBottomUp) { 2690 SU = Bot.pickOnlyChoice(); 2691 if (!SU) { 2692 CandPolicy NoPolicy; 2693 SchedCandidate BotCand(NoPolicy); 2694 pickNodeFromQueue(Bot, DAG->getBotRPTracker(), BotCand); 2695 assert(BotCand.Reason != NoCand && "failed to find a candidate"); 2696 tracePick(BotCand, false); 2697 SU = BotCand.SU; 2698 } 2699 IsTopNode = false; 2700 } 2701 else { 2702 SU = pickNodeBidirectional(IsTopNode); 2703 } 2704 } while (SU->isScheduled); 2705 2706 if (SU->isTopReady()) 2707 Top.removeReady(SU); 2708 if (SU->isBottomReady()) 2709 Bot.removeReady(SU); 2710 2711 DEBUG(dbgs() << "Scheduling SU(" << SU->NodeNum << ") " << *SU->getInstr()); 2712 return SU; 2713} 2714 2715void ConvergingScheduler::reschedulePhysRegCopies(SUnit *SU, bool isTop) { 2716 2717 MachineBasicBlock::iterator InsertPos = SU->getInstr(); 2718 if (!isTop) 2719 ++InsertPos; 2720 SmallVectorImpl<SDep> &Deps = isTop ? SU->Preds : SU->Succs; 2721 2722 // Find already scheduled copies with a single physreg dependence and move 2723 // them just above the scheduled instruction. 2724 for (SmallVectorImpl<SDep>::iterator I = Deps.begin(), E = Deps.end(); 2725 I != E; ++I) { 2726 if (I->getKind() != SDep::Data || !TRI->isPhysicalRegister(I->getReg())) 2727 continue; 2728 SUnit *DepSU = I->getSUnit(); 2729 if (isTop ? DepSU->Succs.size() > 1 : DepSU->Preds.size() > 1) 2730 continue; 2731 MachineInstr *Copy = DepSU->getInstr(); 2732 if (!Copy->isCopy()) 2733 continue; 2734 DEBUG(dbgs() << " Rescheduling physreg copy "; 2735 I->getSUnit()->dump(DAG)); 2736 DAG->moveInstruction(Copy, InsertPos); 2737 } 2738} 2739 2740/// Update the scheduler's state after scheduling a node. This is the same node 2741/// that was just returned by pickNode(). However, ScheduleDAGMI needs to update 2742/// it's state based on the current cycle before MachineSchedStrategy does. 2743/// 2744/// FIXME: Eventually, we may bundle physreg copies rather than rescheduling 2745/// them here. See comments in biasPhysRegCopy. 2746void ConvergingScheduler::schedNode(SUnit *SU, bool IsTopNode) { 2747 if (IsTopNode) { 2748 SU->TopReadyCycle = std::max(SU->TopReadyCycle, Top.CurrCycle); 2749 Top.bumpNode(SU); 2750 if (SU->hasPhysRegUses) 2751 reschedulePhysRegCopies(SU, true); 2752 } 2753 else { 2754 SU->BotReadyCycle = std::max(SU->BotReadyCycle, Bot.CurrCycle); 2755 Bot.bumpNode(SU); 2756 if (SU->hasPhysRegDefs) 2757 reschedulePhysRegCopies(SU, false); 2758 } 2759} 2760 2761/// Create the standard converging machine scheduler. This will be used as the 2762/// default scheduler if the target does not set a default. 2763static ScheduleDAGInstrs *createConvergingSched(MachineSchedContext *C) { 2764 ScheduleDAGMI *DAG = new ScheduleDAGMI(C, new ConvergingScheduler(C)); 2765 // Register DAG post-processors. 2766 // 2767 // FIXME: extend the mutation API to allow earlier mutations to instantiate 2768 // data and pass it to later mutations. Have a single mutation that gathers 2769 // the interesting nodes in one pass. 2770 DAG->addMutation(new CopyConstrain(DAG->TII, DAG->TRI)); 2771 if (EnableLoadCluster && DAG->TII->enableClusterLoads()) 2772 DAG->addMutation(new LoadClusterMutation(DAG->TII, DAG->TRI)); 2773 if (EnableMacroFusion) 2774 DAG->addMutation(new MacroFusion(DAG->TII)); 2775 return DAG; 2776} 2777static MachineSchedRegistry 2778ConvergingSchedRegistry("converge", "Standard converging scheduler.", 2779 createConvergingSched); 2780 2781//===----------------------------------------------------------------------===// 2782// ILP Scheduler. Currently for experimental analysis of heuristics. 2783//===----------------------------------------------------------------------===// 2784 2785namespace { 2786/// \brief Order nodes by the ILP metric. 2787struct ILPOrder { 2788 const SchedDFSResult *DFSResult; 2789 const BitVector *ScheduledTrees; 2790 bool MaximizeILP; 2791 2792 ILPOrder(bool MaxILP): DFSResult(0), ScheduledTrees(0), MaximizeILP(MaxILP) {} 2793 2794 /// \brief Apply a less-than relation on node priority. 2795 /// 2796 /// (Return true if A comes after B in the Q.) 2797 bool operator()(const SUnit *A, const SUnit *B) const { 2798 unsigned SchedTreeA = DFSResult->getSubtreeID(A); 2799 unsigned SchedTreeB = DFSResult->getSubtreeID(B); 2800 if (SchedTreeA != SchedTreeB) { 2801 // Unscheduled trees have lower priority. 2802 if (ScheduledTrees->test(SchedTreeA) != ScheduledTrees->test(SchedTreeB)) 2803 return ScheduledTrees->test(SchedTreeB); 2804 2805 // Trees with shallower connections have have lower priority. 2806 if (DFSResult->getSubtreeLevel(SchedTreeA) 2807 != DFSResult->getSubtreeLevel(SchedTreeB)) { 2808 return DFSResult->getSubtreeLevel(SchedTreeA) 2809 < DFSResult->getSubtreeLevel(SchedTreeB); 2810 } 2811 } 2812 if (MaximizeILP) 2813 return DFSResult->getILP(A) < DFSResult->getILP(B); 2814 else 2815 return DFSResult->getILP(A) > DFSResult->getILP(B); 2816 } 2817}; 2818 2819/// \brief Schedule based on the ILP metric. 2820class ILPScheduler : public MachineSchedStrategy { 2821 ScheduleDAGMI *DAG; 2822 ILPOrder Cmp; 2823 2824 std::vector<SUnit*> ReadyQ; 2825public: 2826 ILPScheduler(bool MaximizeILP): DAG(0), Cmp(MaximizeILP) {} 2827 2828 virtual void initialize(ScheduleDAGMI *dag) { 2829 DAG = dag; 2830 DAG->computeDFSResult(); 2831 Cmp.DFSResult = DAG->getDFSResult(); 2832 Cmp.ScheduledTrees = &DAG->getScheduledTrees(); 2833 ReadyQ.clear(); 2834 } 2835 2836 virtual void registerRoots() { 2837 // Restore the heap in ReadyQ with the updated DFS results. 2838 std::make_heap(ReadyQ.begin(), ReadyQ.end(), Cmp); 2839 } 2840 2841 /// Implement MachineSchedStrategy interface. 2842 /// ----------------------------------------- 2843 2844 /// Callback to select the highest priority node from the ready Q. 2845 virtual SUnit *pickNode(bool &IsTopNode) { 2846 if (ReadyQ.empty()) return NULL; 2847 std::pop_heap(ReadyQ.begin(), ReadyQ.end(), Cmp); 2848 SUnit *SU = ReadyQ.back(); 2849 ReadyQ.pop_back(); 2850 IsTopNode = false; 2851 DEBUG(dbgs() << "Pick node " << "SU(" << SU->NodeNum << ") " 2852 << " ILP: " << DAG->getDFSResult()->getILP(SU) 2853 << " Tree: " << DAG->getDFSResult()->getSubtreeID(SU) << " @" 2854 << DAG->getDFSResult()->getSubtreeLevel( 2855 DAG->getDFSResult()->getSubtreeID(SU)) << '\n' 2856 << "Scheduling " << *SU->getInstr()); 2857 return SU; 2858 } 2859 2860 /// \brief Scheduler callback to notify that a new subtree is scheduled. 2861 virtual void scheduleTree(unsigned SubtreeID) { 2862 std::make_heap(ReadyQ.begin(), ReadyQ.end(), Cmp); 2863 } 2864 2865 /// Callback after a node is scheduled. Mark a newly scheduled tree, notify 2866 /// DFSResults, and resort the priority Q. 2867 virtual void schedNode(SUnit *SU, bool IsTopNode) { 2868 assert(!IsTopNode && "SchedDFSResult needs bottom-up"); 2869 } 2870 2871 virtual void releaseTopNode(SUnit *) { /*only called for top roots*/ } 2872 2873 virtual void releaseBottomNode(SUnit *SU) { 2874 ReadyQ.push_back(SU); 2875 std::push_heap(ReadyQ.begin(), ReadyQ.end(), Cmp); 2876 } 2877}; 2878} // namespace 2879 2880static ScheduleDAGInstrs *createILPMaxScheduler(MachineSchedContext *C) { 2881 return new ScheduleDAGMI(C, new ILPScheduler(true)); 2882} 2883static ScheduleDAGInstrs *createILPMinScheduler(MachineSchedContext *C) { 2884 return new ScheduleDAGMI(C, new ILPScheduler(false)); 2885} 2886static MachineSchedRegistry ILPMaxRegistry( 2887 "ilpmax", "Schedule bottom-up for max ILP", createILPMaxScheduler); 2888static MachineSchedRegistry ILPMinRegistry( 2889 "ilpmin", "Schedule bottom-up for min ILP", createILPMinScheduler); 2890 2891//===----------------------------------------------------------------------===// 2892// Machine Instruction Shuffler for Correctness Testing 2893//===----------------------------------------------------------------------===// 2894 2895#ifndef NDEBUG 2896namespace { 2897/// Apply a less-than relation on the node order, which corresponds to the 2898/// instruction order prior to scheduling. IsReverse implements greater-than. 2899template<bool IsReverse> 2900struct SUnitOrder { 2901 bool operator()(SUnit *A, SUnit *B) const { 2902 if (IsReverse) 2903 return A->NodeNum > B->NodeNum; 2904 else 2905 return A->NodeNum < B->NodeNum; 2906 } 2907}; 2908 2909/// Reorder instructions as much as possible. 2910class InstructionShuffler : public MachineSchedStrategy { 2911 bool IsAlternating; 2912 bool IsTopDown; 2913 2914 // Using a less-than relation (SUnitOrder<false>) for the TopQ priority 2915 // gives nodes with a higher number higher priority causing the latest 2916 // instructions to be scheduled first. 2917 PriorityQueue<SUnit*, std::vector<SUnit*>, SUnitOrder<false> > 2918 TopQ; 2919 // When scheduling bottom-up, use greater-than as the queue priority. 2920 PriorityQueue<SUnit*, std::vector<SUnit*>, SUnitOrder<true> > 2921 BottomQ; 2922public: 2923 InstructionShuffler(bool alternate, bool topdown) 2924 : IsAlternating(alternate), IsTopDown(topdown) {} 2925 2926 virtual void initialize(ScheduleDAGMI *) { 2927 TopQ.clear(); 2928 BottomQ.clear(); 2929 } 2930 2931 /// Implement MachineSchedStrategy interface. 2932 /// ----------------------------------------- 2933 2934 virtual SUnit *pickNode(bool &IsTopNode) { 2935 SUnit *SU; 2936 if (IsTopDown) { 2937 do { 2938 if (TopQ.empty()) return NULL; 2939 SU = TopQ.top(); 2940 TopQ.pop(); 2941 } while (SU->isScheduled); 2942 IsTopNode = true; 2943 } 2944 else { 2945 do { 2946 if (BottomQ.empty()) return NULL; 2947 SU = BottomQ.top(); 2948 BottomQ.pop(); 2949 } while (SU->isScheduled); 2950 IsTopNode = false; 2951 } 2952 if (IsAlternating) 2953 IsTopDown = !IsTopDown; 2954 return SU; 2955 } 2956 2957 virtual void schedNode(SUnit *SU, bool IsTopNode) {} 2958 2959 virtual void releaseTopNode(SUnit *SU) { 2960 TopQ.push(SU); 2961 } 2962 virtual void releaseBottomNode(SUnit *SU) { 2963 BottomQ.push(SU); 2964 } 2965}; 2966} // namespace 2967 2968static ScheduleDAGInstrs *createInstructionShuffler(MachineSchedContext *C) { 2969 bool Alternate = !ForceTopDown && !ForceBottomUp; 2970 bool TopDown = !ForceBottomUp; 2971 assert((TopDown || !ForceTopDown) && 2972 "-misched-topdown incompatible with -misched-bottomup"); 2973 return new ScheduleDAGMI(C, new InstructionShuffler(Alternate, TopDown)); 2974} 2975static MachineSchedRegistry ShufflerRegistry( 2976 "shuffle", "Shuffle machine instructions alternating directions", 2977 createInstructionShuffler); 2978#endif // !NDEBUG 2979 2980//===----------------------------------------------------------------------===// 2981// GraphWriter support for ScheduleDAGMI. 2982//===----------------------------------------------------------------------===// 2983 2984#ifndef NDEBUG 2985namespace llvm { 2986 2987template<> struct GraphTraits< 2988 ScheduleDAGMI*> : public GraphTraits<ScheduleDAG*> {}; 2989 2990template<> 2991struct DOTGraphTraits<ScheduleDAGMI*> : public DefaultDOTGraphTraits { 2992 2993 DOTGraphTraits (bool isSimple=false) : DefaultDOTGraphTraits(isSimple) {} 2994 2995 static std::string getGraphName(const ScheduleDAG *G) { 2996 return G->MF.getName(); 2997 } 2998 2999 static bool renderGraphFromBottomUp() { 3000 return true; 3001 } 3002 3003 static bool isNodeHidden(const SUnit *Node) { 3004 return (Node->Preds.size() > 10 || Node->Succs.size() > 10); 3005 } 3006 3007 static bool hasNodeAddressLabel(const SUnit *Node, 3008 const ScheduleDAG *Graph) { 3009 return false; 3010 } 3011 3012 /// If you want to override the dot attributes printed for a particular 3013 /// edge, override this method. 3014 static std::string getEdgeAttributes(const SUnit *Node, 3015 SUnitIterator EI, 3016 const ScheduleDAG *Graph) { 3017 if (EI.isArtificialDep()) 3018 return "color=cyan,style=dashed"; 3019 if (EI.isCtrlDep()) 3020 return "color=blue,style=dashed"; 3021 return ""; 3022 } 3023 3024 static std::string getNodeLabel(const SUnit *SU, const ScheduleDAG *G) { 3025 std::string Str; 3026 raw_string_ostream SS(Str); 3027 SS << "SU(" << SU->NodeNum << ')'; 3028 return SS.str(); 3029 } 3030 static std::string getNodeDescription(const SUnit *SU, const ScheduleDAG *G) { 3031 return G->getGraphNodeLabel(SU); 3032 } 3033 3034 static std::string getNodeAttributes(const SUnit *N, 3035 const ScheduleDAG *Graph) { 3036 std::string Str("shape=Mrecord"); 3037 const SchedDFSResult *DFS = 3038 static_cast<const ScheduleDAGMI*>(Graph)->getDFSResult(); 3039 if (DFS) { 3040 Str += ",style=filled,fillcolor=\"#"; 3041 Str += DOT::getColorString(DFS->getSubtreeID(N)); 3042 Str += '"'; 3043 } 3044 return Str; 3045 } 3046}; 3047} // namespace llvm 3048#endif // NDEBUG 3049 3050/// viewGraph - Pop up a ghostview window with the reachable parts of the DAG 3051/// rendered using 'dot'. 3052/// 3053void ScheduleDAGMI::viewGraph(const Twine &Name, const Twine &Title) { 3054#ifndef NDEBUG 3055 ViewGraph(this, Name, false, Title); 3056#else 3057 errs() << "ScheduleDAGMI::viewGraph is only available in debug builds on " 3058 << "systems with Graphviz or gv!\n"; 3059#endif // NDEBUG 3060} 3061 3062/// Out-of-line implementation with no arguments is handy for gdb. 3063void ScheduleDAGMI::viewGraph() { 3064 viewGraph(getDAGName(), "Scheduling-Units Graph for " + getDAGName()); 3065} 3066