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