MachineScheduler.cpp revision 2182977ff2cc8ff1259e3a2c3528651496d818d4
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/Passes.h" 25#include "llvm/CodeGen/RegisterClassInfo.h" 26#include "llvm/CodeGen/ScheduleDFS.h" 27#include "llvm/CodeGen/ScheduleHazardRecognizer.h" 28#include "llvm/Support/CommandLine.h" 29#include "llvm/Support/Debug.h" 30#include "llvm/Support/ErrorHandling.h" 31#include "llvm/Support/GraphWriter.h" 32#include "llvm/Support/raw_ostream.h" 33#include <queue> 34 35using namespace llvm; 36 37namespace llvm { 38cl::opt<bool> ForceTopDown("misched-topdown", cl::Hidden, 39 cl::desc("Force top-down list scheduling")); 40cl::opt<bool> ForceBottomUp("misched-bottomup", cl::Hidden, 41 cl::desc("Force bottom-up list scheduling")); 42} 43 44#ifndef NDEBUG 45static cl::opt<bool> ViewMISchedDAGs("view-misched-dags", cl::Hidden, 46 cl::desc("Pop up a window to show MISched dags after they are processed")); 47 48static cl::opt<unsigned> MISchedCutoff("misched-cutoff", cl::Hidden, 49 cl::desc("Stop scheduling after N instructions"), cl::init(~0U)); 50#else 51static bool ViewMISchedDAGs = false; 52#endif // NDEBUG 53 54// Experimental heuristics 55static cl::opt<bool> EnableLoadCluster("misched-cluster", cl::Hidden, 56 cl::desc("Enable load clustering."), cl::init(true)); 57 58// Experimental heuristics 59static cl::opt<bool> EnableMacroFusion("misched-fusion", cl::Hidden, 60 cl::desc("Enable scheduling for macro fusion."), cl::init(true)); 61 62static cl::opt<bool> VerifyScheduling("verify-misched", cl::Hidden, 63 cl::desc("Verify machine instrs before and after machine scheduling")); 64 65// DAG subtrees must have at least this many nodes. 66static const unsigned MinSubtreeSize = 8; 67 68//===----------------------------------------------------------------------===// 69// Machine Instruction Scheduling Pass and Registry 70//===----------------------------------------------------------------------===// 71 72MachineSchedContext::MachineSchedContext(): 73 MF(0), MLI(0), MDT(0), PassConfig(0), AA(0), LIS(0) { 74 RegClassInfo = new RegisterClassInfo(); 75} 76 77MachineSchedContext::~MachineSchedContext() { 78 delete RegClassInfo; 79} 80 81namespace { 82/// MachineScheduler runs after coalescing and before register allocation. 83class MachineScheduler : public MachineSchedContext, 84 public MachineFunctionPass { 85public: 86 MachineScheduler(); 87 88 virtual void getAnalysisUsage(AnalysisUsage &AU) const; 89 90 virtual void releaseMemory() {} 91 92 virtual bool runOnMachineFunction(MachineFunction&); 93 94 virtual void print(raw_ostream &O, const Module* = 0) const; 95 96 static char ID; // Class identification, replacement for typeinfo 97}; 98} // namespace 99 100char MachineScheduler::ID = 0; 101 102char &llvm::MachineSchedulerID = MachineScheduler::ID; 103 104INITIALIZE_PASS_BEGIN(MachineScheduler, "misched", 105 "Machine Instruction Scheduler", false, false) 106INITIALIZE_AG_DEPENDENCY(AliasAnalysis) 107INITIALIZE_PASS_DEPENDENCY(SlotIndexes) 108INITIALIZE_PASS_DEPENDENCY(LiveIntervals) 109INITIALIZE_PASS_END(MachineScheduler, "misched", 110 "Machine Instruction Scheduler", false, false) 111 112MachineScheduler::MachineScheduler() 113: MachineFunctionPass(ID) { 114 initializeMachineSchedulerPass(*PassRegistry::getPassRegistry()); 115} 116 117void MachineScheduler::getAnalysisUsage(AnalysisUsage &AU) const { 118 AU.setPreservesCFG(); 119 AU.addRequiredID(MachineDominatorsID); 120 AU.addRequired<MachineLoopInfo>(); 121 AU.addRequired<AliasAnalysis>(); 122 AU.addRequired<TargetPassConfig>(); 123 AU.addRequired<SlotIndexes>(); 124 AU.addPreserved<SlotIndexes>(); 125 AU.addRequired<LiveIntervals>(); 126 AU.addPreserved<LiveIntervals>(); 127 MachineFunctionPass::getAnalysisUsage(AU); 128} 129 130MachinePassRegistry MachineSchedRegistry::Registry; 131 132/// A dummy default scheduler factory indicates whether the scheduler 133/// is overridden on the command line. 134static ScheduleDAGInstrs *useDefaultMachineSched(MachineSchedContext *C) { 135 return 0; 136} 137 138/// MachineSchedOpt allows command line selection of the scheduler. 139static cl::opt<MachineSchedRegistry::ScheduleDAGCtor, false, 140 RegisterPassParser<MachineSchedRegistry> > 141MachineSchedOpt("misched", 142 cl::init(&useDefaultMachineSched), cl::Hidden, 143 cl::desc("Machine instruction scheduler to use")); 144 145static MachineSchedRegistry 146DefaultSchedRegistry("default", "Use the target's default scheduler choice.", 147 useDefaultMachineSched); 148 149/// Forward declare the standard machine scheduler. This will be used as the 150/// default scheduler if the target does not set a default. 151static ScheduleDAGInstrs *createConvergingSched(MachineSchedContext *C); 152 153 154/// Decrement this iterator until reaching the top or a non-debug instr. 155static MachineBasicBlock::iterator 156priorNonDebug(MachineBasicBlock::iterator I, MachineBasicBlock::iterator Beg) { 157 assert(I != Beg && "reached the top of the region, cannot decrement"); 158 while (--I != Beg) { 159 if (!I->isDebugValue()) 160 break; 161 } 162 return I; 163} 164 165/// If this iterator is a debug value, increment until reaching the End or a 166/// non-debug instruction. 167static MachineBasicBlock::iterator 168nextIfDebug(MachineBasicBlock::iterator I, MachineBasicBlock::iterator End) { 169 for(; I != End; ++I) { 170 if (!I->isDebugValue()) 171 break; 172 } 173 return I; 174} 175 176/// Top-level MachineScheduler pass driver. 177/// 178/// Visit blocks in function order. Divide each block into scheduling regions 179/// and visit them bottom-up. Visiting regions bottom-up is not required, but is 180/// consistent with the DAG builder, which traverses the interior of the 181/// scheduling regions bottom-up. 182/// 183/// This design avoids exposing scheduling boundaries to the DAG builder, 184/// simplifying the DAG builder's support for "special" target instructions. 185/// At the same time the design allows target schedulers to operate across 186/// scheduling boundaries, for example to bundle the boudary instructions 187/// without reordering them. This creates complexity, because the target 188/// scheduler must update the RegionBegin and RegionEnd positions cached by 189/// ScheduleDAGInstrs whenever adding or removing instructions. A much simpler 190/// design would be to split blocks at scheduling boundaries, but LLVM has a 191/// general bias against block splitting purely for implementation simplicity. 192bool MachineScheduler::runOnMachineFunction(MachineFunction &mf) { 193 DEBUG(dbgs() << "Before MISsched:\n"; mf.print(dbgs())); 194 195 // Initialize the context of the pass. 196 MF = &mf; 197 MLI = &getAnalysis<MachineLoopInfo>(); 198 MDT = &getAnalysis<MachineDominatorTree>(); 199 PassConfig = &getAnalysis<TargetPassConfig>(); 200 AA = &getAnalysis<AliasAnalysis>(); 201 202 LIS = &getAnalysis<LiveIntervals>(); 203 const TargetInstrInfo *TII = MF->getTarget().getInstrInfo(); 204 205 if (VerifyScheduling) { 206 DEBUG(LIS->print(dbgs())); 207 MF->verify(this, "Before machine scheduling."); 208 } 209 RegClassInfo->runOnMachineFunction(*MF); 210 211 // Select the scheduler, or set the default. 212 MachineSchedRegistry::ScheduleDAGCtor Ctor = MachineSchedOpt; 213 if (Ctor == useDefaultMachineSched) { 214 // Get the default scheduler set by the target. 215 Ctor = MachineSchedRegistry::getDefault(); 216 if (!Ctor) { 217 Ctor = createConvergingSched; 218 MachineSchedRegistry::setDefault(Ctor); 219 } 220 } 221 // Instantiate the selected scheduler. 222 OwningPtr<ScheduleDAGInstrs> Scheduler(Ctor(this)); 223 224 // Visit all machine basic blocks. 225 // 226 // TODO: Visit blocks in global postorder or postorder within the bottom-up 227 // loop tree. Then we can optionally compute global RegPressure. 228 for (MachineFunction::iterator MBB = MF->begin(), MBBEnd = MF->end(); 229 MBB != MBBEnd; ++MBB) { 230 231 Scheduler->startBlock(MBB); 232 233 // Break the block into scheduling regions [I, RegionEnd), and schedule each 234 // region as soon as it is discovered. RegionEnd points the scheduling 235 // boundary at the bottom of the region. The DAG does not include RegionEnd, 236 // but the region does (i.e. the next RegionEnd is above the previous 237 // RegionBegin). If the current block has no terminator then RegionEnd == 238 // MBB->end() for the bottom region. 239 // 240 // The Scheduler may insert instructions during either schedule() or 241 // exitRegion(), even for empty regions. So the local iterators 'I' and 242 // 'RegionEnd' are invalid across these calls. 243 unsigned RemainingInstrs = MBB->size(); 244 for(MachineBasicBlock::iterator RegionEnd = MBB->end(); 245 RegionEnd != MBB->begin(); RegionEnd = Scheduler->begin()) { 246 247 // Avoid decrementing RegionEnd for blocks with no terminator. 248 if (RegionEnd != MBB->end() 249 || TII->isSchedulingBoundary(llvm::prior(RegionEnd), MBB, *MF)) { 250 --RegionEnd; 251 // Count the boundary instruction. 252 --RemainingInstrs; 253 } 254 255 // The next region starts above the previous region. Look backward in the 256 // instruction stream until we find the nearest boundary. 257 MachineBasicBlock::iterator I = RegionEnd; 258 for(;I != MBB->begin(); --I, --RemainingInstrs) { 259 if (TII->isSchedulingBoundary(llvm::prior(I), MBB, *MF)) 260 break; 261 } 262 // Notify the scheduler of the region, even if we may skip scheduling 263 // it. Perhaps it still needs to be bundled. 264 Scheduler->enterRegion(MBB, I, RegionEnd, RemainingInstrs); 265 266 // Skip empty scheduling regions (0 or 1 schedulable instructions). 267 if (I == RegionEnd || I == llvm::prior(RegionEnd)) { 268 // Close the current region. Bundle the terminator if needed. 269 // This invalidates 'RegionEnd' and 'I'. 270 Scheduler->exitRegion(); 271 continue; 272 } 273 DEBUG(dbgs() << "********** MI Scheduling **********\n"); 274 DEBUG(dbgs() << MF->getName() 275 << ":BB#" << MBB->getNumber() << " " << MBB->getName() 276 << "\n From: " << *I << " To: "; 277 if (RegionEnd != MBB->end()) dbgs() << *RegionEnd; 278 else dbgs() << "End"; 279 dbgs() << " Remaining: " << RemainingInstrs << "\n"); 280 281 // Schedule a region: possibly reorder instructions. 282 // This invalidates 'RegionEnd' and 'I'. 283 Scheduler->schedule(); 284 285 // Close the current region. 286 Scheduler->exitRegion(); 287 288 // Scheduling has invalidated the current iterator 'I'. Ask the 289 // scheduler for the top of it's scheduled region. 290 RegionEnd = Scheduler->begin(); 291 } 292 assert(RemainingInstrs == 0 && "Instruction count mismatch!"); 293 Scheduler->finishBlock(); 294 } 295 Scheduler->finalizeSchedule(); 296 DEBUG(LIS->print(dbgs())); 297 if (VerifyScheduling) 298 MF->verify(this, "After machine scheduling."); 299 return true; 300} 301 302void MachineScheduler::print(raw_ostream &O, const Module* m) const { 303 // unimplemented 304} 305 306#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 307void ReadyQueue::dump() { 308 dbgs() << " " << Name << ": "; 309 for (unsigned i = 0, e = Queue.size(); i < e; ++i) 310 dbgs() << Queue[i]->NodeNum << " "; 311 dbgs() << "\n"; 312} 313#endif 314 315//===----------------------------------------------------------------------===// 316// ScheduleDAGMI - Base class for MachineInstr scheduling with LiveIntervals 317// preservation. 318//===----------------------------------------------------------------------===// 319 320ScheduleDAGMI::~ScheduleDAGMI() { 321 delete DFSResult; 322 DeleteContainerPointers(Mutations); 323 delete SchedImpl; 324} 325 326bool ScheduleDAGMI::addEdge(SUnit *SuccSU, const SDep &PredDep) { 327 if (SuccSU != &ExitSU) { 328 // Do not use WillCreateCycle, it assumes SD scheduling. 329 // If Pred is reachable from Succ, then the edge creates a cycle. 330 if (Topo.IsReachable(PredDep.getSUnit(), SuccSU)) 331 return false; 332 Topo.AddPred(SuccSU, PredDep.getSUnit()); 333 } 334 SuccSU->addPred(PredDep, /*Required=*/!PredDep.isArtificial()); 335 // Return true regardless of whether a new edge needed to be inserted. 336 return true; 337} 338 339/// ReleaseSucc - Decrement the NumPredsLeft count of a successor. When 340/// NumPredsLeft reaches zero, release the successor node. 341/// 342/// FIXME: Adjust SuccSU height based on MinLatency. 343void ScheduleDAGMI::releaseSucc(SUnit *SU, SDep *SuccEdge) { 344 SUnit *SuccSU = SuccEdge->getSUnit(); 345 346 if (SuccEdge->isWeak()) { 347 --SuccSU->WeakPredsLeft; 348 if (SuccEdge->isCluster()) 349 NextClusterSucc = SuccSU; 350 return; 351 } 352#ifndef NDEBUG 353 if (SuccSU->NumPredsLeft == 0) { 354 dbgs() << "*** Scheduling failed! ***\n"; 355 SuccSU->dump(this); 356 dbgs() << " has been released too many times!\n"; 357 llvm_unreachable(0); 358 } 359#endif 360 --SuccSU->NumPredsLeft; 361 if (SuccSU->NumPredsLeft == 0 && SuccSU != &ExitSU) 362 SchedImpl->releaseTopNode(SuccSU); 363} 364 365/// releaseSuccessors - Call releaseSucc on each of SU's successors. 366void ScheduleDAGMI::releaseSuccessors(SUnit *SU) { 367 for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); 368 I != E; ++I) { 369 releaseSucc(SU, &*I); 370 } 371} 372 373/// ReleasePred - Decrement the NumSuccsLeft count of a predecessor. When 374/// NumSuccsLeft reaches zero, release the predecessor node. 375/// 376/// FIXME: Adjust PredSU height based on MinLatency. 377void ScheduleDAGMI::releasePred(SUnit *SU, SDep *PredEdge) { 378 SUnit *PredSU = PredEdge->getSUnit(); 379 380 if (PredEdge->isWeak()) { 381 --PredSU->WeakSuccsLeft; 382 if (PredEdge->isCluster()) 383 NextClusterPred = PredSU; 384 return; 385 } 386#ifndef NDEBUG 387 if (PredSU->NumSuccsLeft == 0) { 388 dbgs() << "*** Scheduling failed! ***\n"; 389 PredSU->dump(this); 390 dbgs() << " has been released too many times!\n"; 391 llvm_unreachable(0); 392 } 393#endif 394 --PredSU->NumSuccsLeft; 395 if (PredSU->NumSuccsLeft == 0 && PredSU != &EntrySU) 396 SchedImpl->releaseBottomNode(PredSU); 397} 398 399/// releasePredecessors - Call releasePred on each of SU's predecessors. 400void ScheduleDAGMI::releasePredecessors(SUnit *SU) { 401 for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); 402 I != E; ++I) { 403 releasePred(SU, &*I); 404 } 405} 406 407void ScheduleDAGMI::moveInstruction(MachineInstr *MI, 408 MachineBasicBlock::iterator InsertPos) { 409 // Advance RegionBegin if the first instruction moves down. 410 if (&*RegionBegin == MI) 411 ++RegionBegin; 412 413 // Update the instruction stream. 414 BB->splice(InsertPos, BB, MI); 415 416 // Update LiveIntervals 417 LIS->handleMove(MI, /*UpdateFlags=*/true); 418 419 // Recede RegionBegin if an instruction moves above the first. 420 if (RegionBegin == InsertPos) 421 RegionBegin = MI; 422} 423 424bool ScheduleDAGMI::checkSchedLimit() { 425#ifndef NDEBUG 426 if (NumInstrsScheduled == MISchedCutoff && MISchedCutoff != ~0U) { 427 CurrentTop = CurrentBottom; 428 return false; 429 } 430 ++NumInstrsScheduled; 431#endif 432 return true; 433} 434 435/// enterRegion - Called back from MachineScheduler::runOnMachineFunction after 436/// crossing a scheduling boundary. [begin, end) includes all instructions in 437/// the region, including the boundary itself and single-instruction regions 438/// that don't get scheduled. 439void ScheduleDAGMI::enterRegion(MachineBasicBlock *bb, 440 MachineBasicBlock::iterator begin, 441 MachineBasicBlock::iterator end, 442 unsigned endcount) 443{ 444 ScheduleDAGInstrs::enterRegion(bb, begin, end, endcount); 445 446 // For convenience remember the end of the liveness region. 447 LiveRegionEnd = 448 (RegionEnd == bb->end()) ? RegionEnd : llvm::next(RegionEnd); 449} 450 451// Setup the register pressure trackers for the top scheduled top and bottom 452// scheduled regions. 453void ScheduleDAGMI::initRegPressure() { 454 TopRPTracker.init(&MF, RegClassInfo, LIS, BB, RegionBegin); 455 BotRPTracker.init(&MF, RegClassInfo, LIS, BB, LiveRegionEnd); 456 457 // Close the RPTracker to finalize live ins. 458 RPTracker.closeRegion(); 459 460 DEBUG(RPTracker.getPressure().dump(TRI)); 461 462 // Initialize the live ins and live outs. 463 TopRPTracker.addLiveRegs(RPTracker.getPressure().LiveInRegs); 464 BotRPTracker.addLiveRegs(RPTracker.getPressure().LiveOutRegs); 465 466 // Close one end of the tracker so we can call 467 // getMaxUpward/DownwardPressureDelta before advancing across any 468 // instructions. This converts currently live regs into live ins/outs. 469 TopRPTracker.closeTop(); 470 BotRPTracker.closeBottom(); 471 472 // Account for liveness generated by the region boundary. 473 if (LiveRegionEnd != RegionEnd) 474 BotRPTracker.recede(); 475 476 assert(BotRPTracker.getPos() == RegionEnd && "Can't find the region bottom"); 477 478 // Cache the list of excess pressure sets in this region. This will also track 479 // the max pressure in the scheduled code for these sets. 480 RegionCriticalPSets.clear(); 481 const std::vector<unsigned> &RegionPressure = 482 RPTracker.getPressure().MaxSetPressure; 483 for (unsigned i = 0, e = RegionPressure.size(); i < e; ++i) { 484 unsigned Limit = TRI->getRegPressureSetLimit(i); 485 DEBUG(dbgs() << TRI->getRegPressureSetName(i) 486 << "Limit " << Limit 487 << " Actual " << RegionPressure[i] << "\n"); 488 if (RegionPressure[i] > Limit) 489 RegionCriticalPSets.push_back(PressureElement(i, 0)); 490 } 491 DEBUG(dbgs() << "Excess PSets: "; 492 for (unsigned i = 0, e = RegionCriticalPSets.size(); i != e; ++i) 493 dbgs() << TRI->getRegPressureSetName( 494 RegionCriticalPSets[i].PSetID) << " "; 495 dbgs() << "\n"); 496} 497 498// FIXME: When the pressure tracker deals in pressure differences then we won't 499// iterate over all RegionCriticalPSets[i]. 500void ScheduleDAGMI:: 501updateScheduledPressure(const std::vector<unsigned> &NewMaxPressure) { 502 for (unsigned i = 0, e = RegionCriticalPSets.size(); i < e; ++i) { 503 unsigned ID = RegionCriticalPSets[i].PSetID; 504 int &MaxUnits = RegionCriticalPSets[i].UnitIncrease; 505 if ((int)NewMaxPressure[ID] > MaxUnits) 506 MaxUnits = NewMaxPressure[ID]; 507 } 508} 509 510/// schedule - Called back from MachineScheduler::runOnMachineFunction 511/// after setting up the current scheduling region. [RegionBegin, RegionEnd) 512/// only includes instructions that have DAG nodes, not scheduling boundaries. 513/// 514/// This is a skeletal driver, with all the functionality pushed into helpers, 515/// so that it can be easilly extended by experimental schedulers. Generally, 516/// implementing MachineSchedStrategy should be sufficient to implement a new 517/// scheduling algorithm. However, if a scheduler further subclasses 518/// ScheduleDAGMI then it will want to override this virtual method in order to 519/// update any specialized state. 520void ScheduleDAGMI::schedule() { 521 buildDAGWithRegPressure(); 522 523 Topo.InitDAGTopologicalSorting(); 524 525 postprocessDAG(); 526 527 SmallVector<SUnit*, 8> TopRoots, BotRoots; 528 findRootsAndBiasEdges(TopRoots, BotRoots); 529 530 // Initialize the strategy before modifying the DAG. 531 // This may initialize a DFSResult to be used for queue priority. 532 SchedImpl->initialize(this); 533 534 DEBUG(for (unsigned su = 0, e = SUnits.size(); su != e; ++su) 535 SUnits[su].dumpAll(this)); 536 if (ViewMISchedDAGs) viewGraph(); 537 538 // Initialize ready queues now that the DAG and priority data are finalized. 539 initQueues(TopRoots, BotRoots); 540 541 bool IsTopNode = false; 542 while (SUnit *SU = SchedImpl->pickNode(IsTopNode)) { 543 assert(!SU->isScheduled && "Node already scheduled"); 544 if (!checkSchedLimit()) 545 break; 546 547 scheduleMI(SU, IsTopNode); 548 549 updateQueues(SU, IsTopNode); 550 } 551 assert(CurrentTop == CurrentBottom && "Nonempty unscheduled zone."); 552 553 placeDebugValues(); 554 555 DEBUG({ 556 unsigned BBNum = begin()->getParent()->getNumber(); 557 dbgs() << "*** Final schedule for BB#" << BBNum << " ***\n"; 558 dumpSchedule(); 559 dbgs() << '\n'; 560 }); 561} 562 563/// Build the DAG and setup three register pressure trackers. 564void ScheduleDAGMI::buildDAGWithRegPressure() { 565 // Initialize the register pressure tracker used by buildSchedGraph. 566 RPTracker.init(&MF, RegClassInfo, LIS, BB, LiveRegionEnd); 567 568 // Account for liveness generate by the region boundary. 569 if (LiveRegionEnd != RegionEnd) 570 RPTracker.recede(); 571 572 // Build the DAG, and compute current register pressure. 573 buildSchedGraph(AA, &RPTracker); 574 575 // Initialize top/bottom trackers after computing region pressure. 576 initRegPressure(); 577} 578 579/// Apply each ScheduleDAGMutation step in order. 580void ScheduleDAGMI::postprocessDAG() { 581 for (unsigned i = 0, e = Mutations.size(); i < e; ++i) { 582 Mutations[i]->apply(this); 583 } 584} 585 586void ScheduleDAGMI::computeDFSResult() { 587 if (!DFSResult) 588 DFSResult = new SchedDFSResult(/*BottomU*/true, MinSubtreeSize); 589 DFSResult->clear(); 590 ScheduledTrees.clear(); 591 DFSResult->resize(SUnits.size()); 592 DFSResult->compute(SUnits); 593 ScheduledTrees.resize(DFSResult->getNumSubtrees()); 594} 595 596void ScheduleDAGMI::findRootsAndBiasEdges(SmallVectorImpl<SUnit*> &TopRoots, 597 SmallVectorImpl<SUnit*> &BotRoots) { 598 for (std::vector<SUnit>::iterator 599 I = SUnits.begin(), E = SUnits.end(); I != E; ++I) { 600 SUnit *SU = &(*I); 601 assert(!SU->isBoundaryNode() && "Boundary node should not be in SUnits"); 602 603 // Order predecessors so DFSResult follows the critical path. 604 SU->biasCriticalPath(); 605 606 // A SUnit is ready to top schedule if it has no predecessors. 607 if (!I->NumPredsLeft) 608 TopRoots.push_back(SU); 609 // A SUnit is ready to bottom schedule if it has no successors. 610 if (!I->NumSuccsLeft) 611 BotRoots.push_back(SU); 612 } 613 ExitSU.biasCriticalPath(); 614} 615 616/// Identify DAG roots and setup scheduler queues. 617void ScheduleDAGMI::initQueues(ArrayRef<SUnit*> TopRoots, 618 ArrayRef<SUnit*> BotRoots) { 619 NextClusterSucc = NULL; 620 NextClusterPred = NULL; 621 622 // Release all DAG roots for scheduling, not including EntrySU/ExitSU. 623 // 624 // Nodes with unreleased weak edges can still be roots. 625 // Release top roots in forward order. 626 for (SmallVectorImpl<SUnit*>::const_iterator 627 I = TopRoots.begin(), E = TopRoots.end(); I != E; ++I) { 628 SchedImpl->releaseTopNode(*I); 629 } 630 // Release bottom roots in reverse order so the higher priority nodes appear 631 // first. This is more natural and slightly more efficient. 632 for (SmallVectorImpl<SUnit*>::const_reverse_iterator 633 I = BotRoots.rbegin(), E = BotRoots.rend(); I != E; ++I) { 634 SchedImpl->releaseBottomNode(*I); 635 } 636 637 releaseSuccessors(&EntrySU); 638 releasePredecessors(&ExitSU); 639 640 SchedImpl->registerRoots(); 641 642 // Advance past initial DebugValues. 643 assert(TopRPTracker.getPos() == RegionBegin && "bad initial Top tracker"); 644 CurrentTop = nextIfDebug(RegionBegin, RegionEnd); 645 TopRPTracker.setPos(CurrentTop); 646 647 CurrentBottom = RegionEnd; 648} 649 650/// Move an instruction and update register pressure. 651void ScheduleDAGMI::scheduleMI(SUnit *SU, bool IsTopNode) { 652 // Move the instruction to its new location in the instruction stream. 653 MachineInstr *MI = SU->getInstr(); 654 655 if (IsTopNode) { 656 assert(SU->isTopReady() && "node still has unscheduled dependencies"); 657 if (&*CurrentTop == MI) 658 CurrentTop = nextIfDebug(++CurrentTop, CurrentBottom); 659 else { 660 moveInstruction(MI, CurrentTop); 661 TopRPTracker.setPos(MI); 662 } 663 664 // Update top scheduled pressure. 665 TopRPTracker.advance(); 666 assert(TopRPTracker.getPos() == CurrentTop && "out of sync"); 667 updateScheduledPressure(TopRPTracker.getPressure().MaxSetPressure); 668 } 669 else { 670 assert(SU->isBottomReady() && "node still has unscheduled dependencies"); 671 MachineBasicBlock::iterator priorII = 672 priorNonDebug(CurrentBottom, CurrentTop); 673 if (&*priorII == MI) 674 CurrentBottom = priorII; 675 else { 676 if (&*CurrentTop == MI) { 677 CurrentTop = nextIfDebug(++CurrentTop, priorII); 678 TopRPTracker.setPos(CurrentTop); 679 } 680 moveInstruction(MI, CurrentBottom); 681 CurrentBottom = MI; 682 } 683 // Update bottom scheduled pressure. 684 BotRPTracker.recede(); 685 assert(BotRPTracker.getPos() == CurrentBottom && "out of sync"); 686 updateScheduledPressure(BotRPTracker.getPressure().MaxSetPressure); 687 } 688} 689 690/// Update scheduler queues after scheduling an instruction. 691void ScheduleDAGMI::updateQueues(SUnit *SU, bool IsTopNode) { 692 // Release dependent instructions for scheduling. 693 if (IsTopNode) 694 releaseSuccessors(SU); 695 else 696 releasePredecessors(SU); 697 698 SU->isScheduled = true; 699 700 if (DFSResult) { 701 unsigned SubtreeID = DFSResult->getSubtreeID(SU); 702 if (!ScheduledTrees.test(SubtreeID)) { 703 ScheduledTrees.set(SubtreeID); 704 DFSResult->scheduleTree(SubtreeID); 705 SchedImpl->scheduleTree(SubtreeID); 706 } 707 } 708 709 // Notify the scheduling strategy after updating the DAG. 710 SchedImpl->schedNode(SU, IsTopNode); 711} 712 713/// Reinsert any remaining debug_values, just like the PostRA scheduler. 714void ScheduleDAGMI::placeDebugValues() { 715 // If first instruction was a DBG_VALUE then put it back. 716 if (FirstDbgValue) { 717 BB->splice(RegionBegin, BB, FirstDbgValue); 718 RegionBegin = FirstDbgValue; 719 } 720 721 for (std::vector<std::pair<MachineInstr *, MachineInstr *> >::iterator 722 DI = DbgValues.end(), DE = DbgValues.begin(); DI != DE; --DI) { 723 std::pair<MachineInstr *, MachineInstr *> P = *prior(DI); 724 MachineInstr *DbgValue = P.first; 725 MachineBasicBlock::iterator OrigPrevMI = P.second; 726 if (&*RegionBegin == DbgValue) 727 ++RegionBegin; 728 BB->splice(++OrigPrevMI, BB, DbgValue); 729 if (OrigPrevMI == llvm::prior(RegionEnd)) 730 RegionEnd = DbgValue; 731 } 732 DbgValues.clear(); 733 FirstDbgValue = NULL; 734} 735 736#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 737void ScheduleDAGMI::dumpSchedule() const { 738 for (MachineBasicBlock::iterator MI = begin(), ME = end(); MI != ME; ++MI) { 739 if (SUnit *SU = getSUnit(&(*MI))) 740 SU->dump(this); 741 else 742 dbgs() << "Missing SUnit\n"; 743 } 744} 745#endif 746 747//===----------------------------------------------------------------------===// 748// LoadClusterMutation - DAG post-processing to cluster loads. 749//===----------------------------------------------------------------------===// 750 751namespace { 752/// \brief Post-process the DAG to create cluster edges between neighboring 753/// loads. 754class LoadClusterMutation : public ScheduleDAGMutation { 755 struct LoadInfo { 756 SUnit *SU; 757 unsigned BaseReg; 758 unsigned Offset; 759 LoadInfo(SUnit *su, unsigned reg, unsigned ofs) 760 : SU(su), BaseReg(reg), Offset(ofs) {} 761 }; 762 static bool LoadInfoLess(const LoadClusterMutation::LoadInfo &LHS, 763 const LoadClusterMutation::LoadInfo &RHS); 764 765 const TargetInstrInfo *TII; 766 const TargetRegisterInfo *TRI; 767public: 768 LoadClusterMutation(const TargetInstrInfo *tii, 769 const TargetRegisterInfo *tri) 770 : TII(tii), TRI(tri) {} 771 772 virtual void apply(ScheduleDAGMI *DAG); 773protected: 774 void clusterNeighboringLoads(ArrayRef<SUnit*> Loads, ScheduleDAGMI *DAG); 775}; 776} // anonymous 777 778bool LoadClusterMutation::LoadInfoLess( 779 const LoadClusterMutation::LoadInfo &LHS, 780 const LoadClusterMutation::LoadInfo &RHS) { 781 if (LHS.BaseReg != RHS.BaseReg) 782 return LHS.BaseReg < RHS.BaseReg; 783 return LHS.Offset < RHS.Offset; 784} 785 786void LoadClusterMutation::clusterNeighboringLoads(ArrayRef<SUnit*> Loads, 787 ScheduleDAGMI *DAG) { 788 SmallVector<LoadClusterMutation::LoadInfo,32> LoadRecords; 789 for (unsigned Idx = 0, End = Loads.size(); Idx != End; ++Idx) { 790 SUnit *SU = Loads[Idx]; 791 unsigned BaseReg; 792 unsigned Offset; 793 if (TII->getLdStBaseRegImmOfs(SU->getInstr(), BaseReg, Offset, TRI)) 794 LoadRecords.push_back(LoadInfo(SU, BaseReg, Offset)); 795 } 796 if (LoadRecords.size() < 2) 797 return; 798 std::sort(LoadRecords.begin(), LoadRecords.end(), LoadInfoLess); 799 unsigned ClusterLength = 1; 800 for (unsigned Idx = 0, End = LoadRecords.size(); Idx < (End - 1); ++Idx) { 801 if (LoadRecords[Idx].BaseReg != LoadRecords[Idx+1].BaseReg) { 802 ClusterLength = 1; 803 continue; 804 } 805 806 SUnit *SUa = LoadRecords[Idx].SU; 807 SUnit *SUb = LoadRecords[Idx+1].SU; 808 if (TII->shouldClusterLoads(SUa->getInstr(), SUb->getInstr(), ClusterLength) 809 && DAG->addEdge(SUb, SDep(SUa, SDep::Cluster))) { 810 811 DEBUG(dbgs() << "Cluster loads SU(" << SUa->NodeNum << ") - SU(" 812 << SUb->NodeNum << ")\n"); 813 // Copy successor edges from SUa to SUb. Interleaving computation 814 // dependent on SUa can prevent load combining due to register reuse. 815 // Predecessor edges do not need to be copied from SUb to SUa since nearby 816 // loads should have effectively the same inputs. 817 for (SUnit::const_succ_iterator 818 SI = SUa->Succs.begin(), SE = SUa->Succs.end(); SI != SE; ++SI) { 819 if (SI->getSUnit() == SUb) 820 continue; 821 DEBUG(dbgs() << " Copy Succ SU(" << SI->getSUnit()->NodeNum << ")\n"); 822 DAG->addEdge(SI->getSUnit(), SDep(SUb, SDep::Artificial)); 823 } 824 ++ClusterLength; 825 } 826 else 827 ClusterLength = 1; 828 } 829} 830 831/// \brief Callback from DAG postProcessing to create cluster edges for loads. 832void LoadClusterMutation::apply(ScheduleDAGMI *DAG) { 833 // Map DAG NodeNum to store chain ID. 834 DenseMap<unsigned, unsigned> StoreChainIDs; 835 // Map each store chain to a set of dependent loads. 836 SmallVector<SmallVector<SUnit*,4>, 32> StoreChainDependents; 837 for (unsigned Idx = 0, End = DAG->SUnits.size(); Idx != End; ++Idx) { 838 SUnit *SU = &DAG->SUnits[Idx]; 839 if (!SU->getInstr()->mayLoad()) 840 continue; 841 unsigned ChainPredID = DAG->SUnits.size(); 842 for (SUnit::const_pred_iterator 843 PI = SU->Preds.begin(), PE = SU->Preds.end(); PI != PE; ++PI) { 844 if (PI->isCtrl()) { 845 ChainPredID = PI->getSUnit()->NodeNum; 846 break; 847 } 848 } 849 // Check if this chain-like pred has been seen 850 // before. ChainPredID==MaxNodeID for loads at the top of the schedule. 851 unsigned NumChains = StoreChainDependents.size(); 852 std::pair<DenseMap<unsigned, unsigned>::iterator, bool> Result = 853 StoreChainIDs.insert(std::make_pair(ChainPredID, NumChains)); 854 if (Result.second) 855 StoreChainDependents.resize(NumChains + 1); 856 StoreChainDependents[Result.first->second].push_back(SU); 857 } 858 // Iterate over the store chains. 859 for (unsigned Idx = 0, End = StoreChainDependents.size(); Idx != End; ++Idx) 860 clusterNeighboringLoads(StoreChainDependents[Idx], DAG); 861} 862 863//===----------------------------------------------------------------------===// 864// MacroFusion - DAG post-processing to encourage fusion of macro ops. 865//===----------------------------------------------------------------------===// 866 867namespace { 868/// \brief Post-process the DAG to create cluster edges between instructions 869/// that may be fused by the processor into a single operation. 870class MacroFusion : public ScheduleDAGMutation { 871 const TargetInstrInfo *TII; 872public: 873 MacroFusion(const TargetInstrInfo *tii): TII(tii) {} 874 875 virtual void apply(ScheduleDAGMI *DAG); 876}; 877} // anonymous 878 879/// \brief Callback from DAG postProcessing to create cluster edges to encourage 880/// fused operations. 881void MacroFusion::apply(ScheduleDAGMI *DAG) { 882 // For now, assume targets can only fuse with the branch. 883 MachineInstr *Branch = DAG->ExitSU.getInstr(); 884 if (!Branch) 885 return; 886 887 for (unsigned Idx = DAG->SUnits.size(); Idx > 0;) { 888 SUnit *SU = &DAG->SUnits[--Idx]; 889 if (!TII->shouldScheduleAdjacent(SU->getInstr(), Branch)) 890 continue; 891 892 // Create a single weak edge from SU to ExitSU. The only effect is to cause 893 // bottom-up scheduling to heavily prioritize the clustered SU. There is no 894 // need to copy predecessor edges from ExitSU to SU, since top-down 895 // scheduling cannot prioritize ExitSU anyway. To defer top-down scheduling 896 // of SU, we could create an artificial edge from the deepest root, but it 897 // hasn't been needed yet. 898 bool Success = DAG->addEdge(&DAG->ExitSU, SDep(SU, SDep::Cluster)); 899 (void)Success; 900 assert(Success && "No DAG nodes should be reachable from ExitSU"); 901 902 DEBUG(dbgs() << "Macro Fuse SU(" << SU->NodeNum << ")\n"); 903 break; 904 } 905} 906 907//===----------------------------------------------------------------------===// 908// ConvergingScheduler - Implementation of the standard MachineSchedStrategy. 909//===----------------------------------------------------------------------===// 910 911namespace { 912/// ConvergingScheduler shrinks the unscheduled zone using heuristics to balance 913/// the schedule. 914class ConvergingScheduler : public MachineSchedStrategy { 915public: 916 /// Represent the type of SchedCandidate found within a single queue. 917 /// pickNodeBidirectional depends on these listed by decreasing priority. 918 enum CandReason { 919 NoCand, SingleExcess, SingleCritical, Cluster, 920 ResourceReduce, ResourceDemand, BotHeightReduce, BotPathReduce, 921 TopDepthReduce, TopPathReduce, SingleMax, MultiPressure, NextDefUse, 922 NodeOrder}; 923 924#ifndef NDEBUG 925 static const char *getReasonStr(ConvergingScheduler::CandReason Reason); 926#endif 927 928 /// Policy for scheduling the next instruction in the candidate's zone. 929 struct CandPolicy { 930 bool ReduceLatency; 931 unsigned ReduceResIdx; 932 unsigned DemandResIdx; 933 934 CandPolicy(): ReduceLatency(false), ReduceResIdx(0), DemandResIdx(0) {} 935 }; 936 937 /// Status of an instruction's critical resource consumption. 938 struct SchedResourceDelta { 939 // Count critical resources in the scheduled region required by SU. 940 unsigned CritResources; 941 942 // Count critical resources from another region consumed by SU. 943 unsigned DemandedResources; 944 945 SchedResourceDelta(): CritResources(0), DemandedResources(0) {} 946 947 bool operator==(const SchedResourceDelta &RHS) const { 948 return CritResources == RHS.CritResources 949 && DemandedResources == RHS.DemandedResources; 950 } 951 bool operator!=(const SchedResourceDelta &RHS) const { 952 return !operator==(RHS); 953 } 954 }; 955 956 /// Store the state used by ConvergingScheduler heuristics, required for the 957 /// lifetime of one invocation of pickNode(). 958 struct SchedCandidate { 959 CandPolicy Policy; 960 961 // The best SUnit candidate. 962 SUnit *SU; 963 964 // The reason for this candidate. 965 CandReason Reason; 966 967 // Register pressure values for the best candidate. 968 RegPressureDelta RPDelta; 969 970 // Critical resource consumption of the best candidate. 971 SchedResourceDelta ResDelta; 972 973 SchedCandidate(const CandPolicy &policy) 974 : Policy(policy), SU(NULL), Reason(NoCand) {} 975 976 bool isValid() const { return SU; } 977 978 // Copy the status of another candidate without changing policy. 979 void setBest(SchedCandidate &Best) { 980 assert(Best.Reason != NoCand && "uninitialized Sched candidate"); 981 SU = Best.SU; 982 Reason = Best.Reason; 983 RPDelta = Best.RPDelta; 984 ResDelta = Best.ResDelta; 985 } 986 987 void initResourceDelta(const ScheduleDAGMI *DAG, 988 const TargetSchedModel *SchedModel); 989 }; 990 991 /// Summarize the unscheduled region. 992 struct SchedRemainder { 993 // Critical path through the DAG in expected latency. 994 unsigned CriticalPath; 995 996 // Unscheduled resources 997 SmallVector<unsigned, 16> RemainingCounts; 998 // Critical resource for the unscheduled zone. 999 unsigned CritResIdx; 1000 // Number of micro-ops left to schedule. 1001 unsigned RemainingMicroOps; 1002 1003 void reset() { 1004 CriticalPath = 0; 1005 RemainingCounts.clear(); 1006 CritResIdx = 0; 1007 RemainingMicroOps = 0; 1008 } 1009 1010 SchedRemainder() { reset(); } 1011 1012 void init(ScheduleDAGMI *DAG, const TargetSchedModel *SchedModel); 1013 1014 unsigned getMaxRemainingCount(const TargetSchedModel *SchedModel) const { 1015 if (!SchedModel->hasInstrSchedModel()) 1016 return 0; 1017 1018 return std::max( 1019 RemainingMicroOps * SchedModel->getMicroOpFactor(), 1020 RemainingCounts[CritResIdx]); 1021 } 1022 }; 1023 1024 /// Each Scheduling boundary is associated with ready queues. It tracks the 1025 /// current cycle in the direction of movement, and maintains the state 1026 /// of "hazards" and other interlocks at the current cycle. 1027 struct SchedBoundary { 1028 ScheduleDAGMI *DAG; 1029 const TargetSchedModel *SchedModel; 1030 SchedRemainder *Rem; 1031 1032 ReadyQueue Available; 1033 ReadyQueue Pending; 1034 bool CheckPending; 1035 1036 // For heuristics, keep a list of the nodes that immediately depend on the 1037 // most recently scheduled node. 1038 SmallPtrSet<const SUnit*, 8> NextSUs; 1039 1040 ScheduleHazardRecognizer *HazardRec; 1041 1042 unsigned CurrCycle; 1043 unsigned IssueCount; 1044 1045 /// MinReadyCycle - Cycle of the soonest available instruction. 1046 unsigned MinReadyCycle; 1047 1048 // The expected latency of the critical path in this scheduled zone. 1049 unsigned ExpectedLatency; 1050 1051 // Resources used in the scheduled zone beyond this boundary. 1052 SmallVector<unsigned, 16> ResourceCounts; 1053 1054 // Cache the critical resources ID in this scheduled zone. 1055 unsigned CritResIdx; 1056 1057 // Is the scheduled region resource limited vs. latency limited. 1058 bool IsResourceLimited; 1059 1060 unsigned ExpectedCount; 1061 1062#ifndef NDEBUG 1063 // Remember the greatest min operand latency. 1064 unsigned MaxMinLatency; 1065#endif 1066 1067 void reset() { 1068 // A new HazardRec is created for each DAG and owned by SchedBoundary. 1069 delete HazardRec; 1070 1071 Available.clear(); 1072 Pending.clear(); 1073 CheckPending = false; 1074 NextSUs.clear(); 1075 HazardRec = 0; 1076 CurrCycle = 0; 1077 IssueCount = 0; 1078 MinReadyCycle = UINT_MAX; 1079 ExpectedLatency = 0; 1080 ResourceCounts.resize(1); 1081 assert(!ResourceCounts[0] && "nonzero count for bad resource"); 1082 CritResIdx = 0; 1083 IsResourceLimited = false; 1084 ExpectedCount = 0; 1085#ifndef NDEBUG 1086 MaxMinLatency = 0; 1087#endif 1088 // Reserve a zero-count for invalid CritResIdx. 1089 ResourceCounts.resize(1); 1090 } 1091 1092 /// Pending queues extend the ready queues with the same ID and the 1093 /// PendingFlag set. 1094 SchedBoundary(unsigned ID, const Twine &Name): 1095 DAG(0), SchedModel(0), Rem(0), Available(ID, Name+".A"), 1096 Pending(ID << ConvergingScheduler::LogMaxQID, Name+".P"), 1097 HazardRec(0) { 1098 reset(); 1099 } 1100 1101 ~SchedBoundary() { delete HazardRec; } 1102 1103 void init(ScheduleDAGMI *dag, const TargetSchedModel *smodel, 1104 SchedRemainder *rem); 1105 1106 bool isTop() const { 1107 return Available.getID() == ConvergingScheduler::TopQID; 1108 } 1109 1110 unsigned getUnscheduledLatency(SUnit *SU) const { 1111 if (isTop()) 1112 return SU->getHeight(); 1113 return SU->getDepth() + SU->Latency; 1114 } 1115 1116 unsigned getCriticalCount() const { 1117 return ResourceCounts[CritResIdx]; 1118 } 1119 1120 bool checkHazard(SUnit *SU); 1121 1122 void setLatencyPolicy(CandPolicy &Policy); 1123 1124 void releaseNode(SUnit *SU, unsigned ReadyCycle); 1125 1126 void bumpCycle(); 1127 1128 void countResource(unsigned PIdx, unsigned Cycles); 1129 1130 void bumpNode(SUnit *SU); 1131 1132 void releasePending(); 1133 1134 void removeReady(SUnit *SU); 1135 1136 SUnit *pickOnlyChoice(); 1137 }; 1138 1139private: 1140 ScheduleDAGMI *DAG; 1141 const TargetSchedModel *SchedModel; 1142 const TargetRegisterInfo *TRI; 1143 1144 // State of the top and bottom scheduled instruction boundaries. 1145 SchedRemainder Rem; 1146 SchedBoundary Top; 1147 SchedBoundary Bot; 1148 1149public: 1150 /// SUnit::NodeQueueId: 0 (none), 1 (top), 2 (bot), 3 (both) 1151 enum { 1152 TopQID = 1, 1153 BotQID = 2, 1154 LogMaxQID = 2 1155 }; 1156 1157 ConvergingScheduler(): 1158 DAG(0), SchedModel(0), TRI(0), Top(TopQID, "TopQ"), Bot(BotQID, "BotQ") {} 1159 1160 virtual void initialize(ScheduleDAGMI *dag); 1161 1162 virtual SUnit *pickNode(bool &IsTopNode); 1163 1164 virtual void schedNode(SUnit *SU, bool IsTopNode); 1165 1166 virtual void releaseTopNode(SUnit *SU); 1167 1168 virtual void releaseBottomNode(SUnit *SU); 1169 1170 virtual void registerRoots(); 1171 1172protected: 1173 void balanceZones( 1174 ConvergingScheduler::SchedBoundary &CriticalZone, 1175 ConvergingScheduler::SchedCandidate &CriticalCand, 1176 ConvergingScheduler::SchedBoundary &OppositeZone, 1177 ConvergingScheduler::SchedCandidate &OppositeCand); 1178 1179 void checkResourceLimits(ConvergingScheduler::SchedCandidate &TopCand, 1180 ConvergingScheduler::SchedCandidate &BotCand); 1181 1182 void tryCandidate(SchedCandidate &Cand, 1183 SchedCandidate &TryCand, 1184 SchedBoundary &Zone, 1185 const RegPressureTracker &RPTracker, 1186 RegPressureTracker &TempTracker); 1187 1188 SUnit *pickNodeBidirectional(bool &IsTopNode); 1189 1190 void pickNodeFromQueue(SchedBoundary &Zone, 1191 const RegPressureTracker &RPTracker, 1192 SchedCandidate &Candidate); 1193 1194#ifndef NDEBUG 1195 void traceCandidate(const SchedCandidate &Cand); 1196#endif 1197}; 1198} // namespace 1199 1200void ConvergingScheduler::SchedRemainder:: 1201init(ScheduleDAGMI *DAG, const TargetSchedModel *SchedModel) { 1202 reset(); 1203 if (!SchedModel->hasInstrSchedModel()) 1204 return; 1205 RemainingCounts.resize(SchedModel->getNumProcResourceKinds()); 1206 for (std::vector<SUnit>::iterator 1207 I = DAG->SUnits.begin(), E = DAG->SUnits.end(); I != E; ++I) { 1208 const MCSchedClassDesc *SC = DAG->getSchedClass(&*I); 1209 RemainingMicroOps += SchedModel->getNumMicroOps(I->getInstr(), SC); 1210 for (TargetSchedModel::ProcResIter 1211 PI = SchedModel->getWriteProcResBegin(SC), 1212 PE = SchedModel->getWriteProcResEnd(SC); PI != PE; ++PI) { 1213 unsigned PIdx = PI->ProcResourceIdx; 1214 unsigned Factor = SchedModel->getResourceFactor(PIdx); 1215 RemainingCounts[PIdx] += (Factor * PI->Cycles); 1216 } 1217 } 1218 for (unsigned PIdx = 0, PEnd = SchedModel->getNumProcResourceKinds(); 1219 PIdx != PEnd; ++PIdx) { 1220 if ((int)(RemainingCounts[PIdx] - RemainingCounts[CritResIdx]) 1221 >= (int)SchedModel->getLatencyFactor()) { 1222 CritResIdx = PIdx; 1223 } 1224 } 1225} 1226 1227void ConvergingScheduler::SchedBoundary:: 1228init(ScheduleDAGMI *dag, const TargetSchedModel *smodel, SchedRemainder *rem) { 1229 reset(); 1230 DAG = dag; 1231 SchedModel = smodel; 1232 Rem = rem; 1233 if (SchedModel->hasInstrSchedModel()) 1234 ResourceCounts.resize(SchedModel->getNumProcResourceKinds()); 1235} 1236 1237void ConvergingScheduler::initialize(ScheduleDAGMI *dag) { 1238 DAG = dag; 1239 SchedModel = DAG->getSchedModel(); 1240 TRI = DAG->TRI; 1241 1242 Rem.init(DAG, SchedModel); 1243 Top.init(DAG, SchedModel, &Rem); 1244 Bot.init(DAG, SchedModel, &Rem); 1245 1246 // Initialize resource counts. 1247 1248 // Initialize the HazardRecognizers. If itineraries don't exist, are empty, or 1249 // are disabled, then these HazardRecs will be disabled. 1250 const InstrItineraryData *Itin = SchedModel->getInstrItineraries(); 1251 const TargetMachine &TM = DAG->MF.getTarget(); 1252 Top.HazardRec = TM.getInstrInfo()->CreateTargetMIHazardRecognizer(Itin, DAG); 1253 Bot.HazardRec = TM.getInstrInfo()->CreateTargetMIHazardRecognizer(Itin, DAG); 1254 1255 assert((!ForceTopDown || !ForceBottomUp) && 1256 "-misched-topdown incompatible with -misched-bottomup"); 1257} 1258 1259void ConvergingScheduler::releaseTopNode(SUnit *SU) { 1260 if (SU->isScheduled) 1261 return; 1262 1263 for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); 1264 I != E; ++I) { 1265 unsigned PredReadyCycle = I->getSUnit()->TopReadyCycle; 1266 unsigned MinLatency = I->getMinLatency(); 1267#ifndef NDEBUG 1268 Top.MaxMinLatency = std::max(MinLatency, Top.MaxMinLatency); 1269#endif 1270 if (SU->TopReadyCycle < PredReadyCycle + MinLatency) 1271 SU->TopReadyCycle = PredReadyCycle + MinLatency; 1272 } 1273 Top.releaseNode(SU, SU->TopReadyCycle); 1274} 1275 1276void ConvergingScheduler::releaseBottomNode(SUnit *SU) { 1277 if (SU->isScheduled) 1278 return; 1279 1280 assert(SU->getInstr() && "Scheduled SUnit must have instr"); 1281 1282 for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); 1283 I != E; ++I) { 1284 if (I->isWeak()) 1285 continue; 1286 unsigned SuccReadyCycle = I->getSUnit()->BotReadyCycle; 1287 unsigned MinLatency = I->getMinLatency(); 1288#ifndef NDEBUG 1289 Bot.MaxMinLatency = std::max(MinLatency, Bot.MaxMinLatency); 1290#endif 1291 if (SU->BotReadyCycle < SuccReadyCycle + MinLatency) 1292 SU->BotReadyCycle = SuccReadyCycle + MinLatency; 1293 } 1294 Bot.releaseNode(SU, SU->BotReadyCycle); 1295} 1296 1297void ConvergingScheduler::registerRoots() { 1298 Rem.CriticalPath = DAG->ExitSU.getDepth(); 1299 // Some roots may not feed into ExitSU. Check all of them in case. 1300 for (std::vector<SUnit*>::const_iterator 1301 I = Bot.Available.begin(), E = Bot.Available.end(); I != E; ++I) { 1302 if ((*I)->getDepth() > Rem.CriticalPath) 1303 Rem.CriticalPath = (*I)->getDepth(); 1304 } 1305 DEBUG(dbgs() << "Critical Path: " << Rem.CriticalPath << '\n'); 1306} 1307 1308/// Does this SU have a hazard within the current instruction group. 1309/// 1310/// The scheduler supports two modes of hazard recognition. The first is the 1311/// ScheduleHazardRecognizer API. It is a fully general hazard recognizer that 1312/// supports highly complicated in-order reservation tables 1313/// (ScoreboardHazardRecognizer) and arbitraty target-specific logic. 1314/// 1315/// The second is a streamlined mechanism that checks for hazards based on 1316/// simple counters that the scheduler itself maintains. It explicitly checks 1317/// for instruction dispatch limitations, including the number of micro-ops that 1318/// can dispatch per cycle. 1319/// 1320/// TODO: Also check whether the SU must start a new group. 1321bool ConvergingScheduler::SchedBoundary::checkHazard(SUnit *SU) { 1322 if (HazardRec->isEnabled()) 1323 return HazardRec->getHazardType(SU) != ScheduleHazardRecognizer::NoHazard; 1324 1325 unsigned uops = SchedModel->getNumMicroOps(SU->getInstr()); 1326 if ((IssueCount > 0) && (IssueCount + uops > SchedModel->getIssueWidth())) { 1327 DEBUG(dbgs() << " SU(" << SU->NodeNum << ") uops=" 1328 << SchedModel->getNumMicroOps(SU->getInstr()) << '\n'); 1329 return true; 1330 } 1331 return false; 1332} 1333 1334/// Compute the remaining latency to determine whether ILP should be increased. 1335void ConvergingScheduler::SchedBoundary::setLatencyPolicy(CandPolicy &Policy) { 1336 // FIXME: compile time. In all, we visit four queues here one we should only 1337 // need to visit the one that was last popped if we cache the result. 1338 unsigned RemLatency = 0; 1339 for (ReadyQueue::iterator I = Available.begin(), E = Available.end(); 1340 I != E; ++I) { 1341 unsigned L = getUnscheduledLatency(*I); 1342 if (L > RemLatency) 1343 RemLatency = L; 1344 } 1345 for (ReadyQueue::iterator I = Pending.begin(), E = Pending.end(); 1346 I != E; ++I) { 1347 unsigned L = getUnscheduledLatency(*I); 1348 if (L > RemLatency) 1349 RemLatency = L; 1350 } 1351 unsigned CriticalPathLimit = Rem->CriticalPath + SchedModel->getILPWindow(); 1352 if (RemLatency + ExpectedLatency >= CriticalPathLimit 1353 && RemLatency > Rem->getMaxRemainingCount(SchedModel)) { 1354 Policy.ReduceLatency = true; 1355 DEBUG(dbgs() << "Increase ILP: " << Available.getName() << '\n'); 1356 } 1357} 1358 1359void ConvergingScheduler::SchedBoundary::releaseNode(SUnit *SU, 1360 unsigned ReadyCycle) { 1361 1362 if (ReadyCycle < MinReadyCycle) 1363 MinReadyCycle = ReadyCycle; 1364 1365 // Check for interlocks first. For the purpose of other heuristics, an 1366 // instruction that cannot issue appears as if it's not in the ReadyQueue. 1367 if (ReadyCycle > CurrCycle || checkHazard(SU)) 1368 Pending.push(SU); 1369 else 1370 Available.push(SU); 1371 1372 // Record this node as an immediate dependent of the scheduled node. 1373 NextSUs.insert(SU); 1374} 1375 1376/// Move the boundary of scheduled code by one cycle. 1377void ConvergingScheduler::SchedBoundary::bumpCycle() { 1378 unsigned Width = SchedModel->getIssueWidth(); 1379 IssueCount = (IssueCount <= Width) ? 0 : IssueCount - Width; 1380 1381 unsigned NextCycle = CurrCycle + 1; 1382 assert(MinReadyCycle < UINT_MAX && "MinReadyCycle uninitialized"); 1383 if (MinReadyCycle > NextCycle) { 1384 IssueCount = 0; 1385 NextCycle = MinReadyCycle; 1386 } 1387 1388 if (!HazardRec->isEnabled()) { 1389 // Bypass HazardRec virtual calls. 1390 CurrCycle = NextCycle; 1391 } 1392 else { 1393 // Bypass getHazardType calls in case of long latency. 1394 for (; CurrCycle != NextCycle; ++CurrCycle) { 1395 if (isTop()) 1396 HazardRec->AdvanceCycle(); 1397 else 1398 HazardRec->RecedeCycle(); 1399 } 1400 } 1401 CheckPending = true; 1402 IsResourceLimited = getCriticalCount() > std::max(ExpectedLatency, CurrCycle); 1403 1404 DEBUG(dbgs() << " " << Available.getName() 1405 << " Cycle: " << CurrCycle << '\n'); 1406} 1407 1408/// Add the given processor resource to this scheduled zone. 1409void ConvergingScheduler::SchedBoundary::countResource(unsigned PIdx, 1410 unsigned Cycles) { 1411 unsigned Factor = SchedModel->getResourceFactor(PIdx); 1412 DEBUG(dbgs() << " " << SchedModel->getProcResource(PIdx)->Name 1413 << " +(" << Cycles << "x" << Factor 1414 << ") / " << SchedModel->getLatencyFactor() << '\n'); 1415 1416 unsigned Count = Factor * Cycles; 1417 ResourceCounts[PIdx] += Count; 1418 assert(Rem->RemainingCounts[PIdx] >= Count && "resource double counted"); 1419 Rem->RemainingCounts[PIdx] -= Count; 1420 1421 // Check if this resource exceeds the current critical resource by a full 1422 // cycle. If so, it becomes the critical resource. 1423 if ((int)(ResourceCounts[PIdx] - ResourceCounts[CritResIdx]) 1424 >= (int)SchedModel->getLatencyFactor()) { 1425 CritResIdx = PIdx; 1426 DEBUG(dbgs() << " *** Critical resource " 1427 << SchedModel->getProcResource(PIdx)->Name << " x" 1428 << ResourceCounts[PIdx] << '\n'); 1429 } 1430} 1431 1432/// Move the boundary of scheduled code by one SUnit. 1433void ConvergingScheduler::SchedBoundary::bumpNode(SUnit *SU) { 1434 // Update the reservation table. 1435 if (HazardRec->isEnabled()) { 1436 if (!isTop() && SU->isCall) { 1437 // Calls are scheduled with their preceding instructions. For bottom-up 1438 // scheduling, clear the pipeline state before emitting. 1439 HazardRec->Reset(); 1440 } 1441 HazardRec->EmitInstruction(SU); 1442 } 1443 // Update resource counts and critical resource. 1444 if (SchedModel->hasInstrSchedModel()) { 1445 const MCSchedClassDesc *SC = DAG->getSchedClass(SU); 1446 Rem->RemainingMicroOps -= SchedModel->getNumMicroOps(SU->getInstr(), SC); 1447 for (TargetSchedModel::ProcResIter 1448 PI = SchedModel->getWriteProcResBegin(SC), 1449 PE = SchedModel->getWriteProcResEnd(SC); PI != PE; ++PI) { 1450 countResource(PI->ProcResourceIdx, PI->Cycles); 1451 } 1452 } 1453 if (isTop()) { 1454 if (SU->getDepth() > ExpectedLatency) 1455 ExpectedLatency = SU->getDepth(); 1456 } 1457 else { 1458 if (SU->getHeight() > ExpectedLatency) 1459 ExpectedLatency = SU->getHeight(); 1460 } 1461 1462 IsResourceLimited = getCriticalCount() > std::max(ExpectedLatency, CurrCycle); 1463 1464 // Check the instruction group dispatch limit. 1465 // TODO: Check if this SU must end a dispatch group. 1466 IssueCount += SchedModel->getNumMicroOps(SU->getInstr()); 1467 1468 // checkHazard prevents scheduling multiple instructions per cycle that exceed 1469 // issue width. However, we commonly reach the maximum. In this case 1470 // opportunistically bump the cycle to avoid uselessly checking everything in 1471 // the readyQ. Furthermore, a single instruction may produce more than one 1472 // cycle's worth of micro-ops. 1473 if (IssueCount >= SchedModel->getIssueWidth()) { 1474 DEBUG(dbgs() << " *** Max instrs at cycle " << CurrCycle << '\n'); 1475 bumpCycle(); 1476 } 1477} 1478 1479/// Release pending ready nodes in to the available queue. This makes them 1480/// visible to heuristics. 1481void ConvergingScheduler::SchedBoundary::releasePending() { 1482 // If the available queue is empty, it is safe to reset MinReadyCycle. 1483 if (Available.empty()) 1484 MinReadyCycle = UINT_MAX; 1485 1486 // Check to see if any of the pending instructions are ready to issue. If 1487 // so, add them to the available queue. 1488 for (unsigned i = 0, e = Pending.size(); i != e; ++i) { 1489 SUnit *SU = *(Pending.begin()+i); 1490 unsigned ReadyCycle = isTop() ? SU->TopReadyCycle : SU->BotReadyCycle; 1491 1492 if (ReadyCycle < MinReadyCycle) 1493 MinReadyCycle = ReadyCycle; 1494 1495 if (ReadyCycle > CurrCycle) 1496 continue; 1497 1498 if (checkHazard(SU)) 1499 continue; 1500 1501 Available.push(SU); 1502 Pending.remove(Pending.begin()+i); 1503 --i; --e; 1504 } 1505 DEBUG(if (!Pending.empty()) Pending.dump()); 1506 CheckPending = false; 1507} 1508 1509/// Remove SU from the ready set for this boundary. 1510void ConvergingScheduler::SchedBoundary::removeReady(SUnit *SU) { 1511 if (Available.isInQueue(SU)) 1512 Available.remove(Available.find(SU)); 1513 else { 1514 assert(Pending.isInQueue(SU) && "bad ready count"); 1515 Pending.remove(Pending.find(SU)); 1516 } 1517} 1518 1519/// If this queue only has one ready candidate, return it. As a side effect, 1520/// defer any nodes that now hit a hazard, and advance the cycle until at least 1521/// one node is ready. If multiple instructions are ready, return NULL. 1522SUnit *ConvergingScheduler::SchedBoundary::pickOnlyChoice() { 1523 if (CheckPending) 1524 releasePending(); 1525 1526 if (IssueCount > 0) { 1527 // Defer any ready instrs that now have a hazard. 1528 for (ReadyQueue::iterator I = Available.begin(); I != Available.end();) { 1529 if (checkHazard(*I)) { 1530 Pending.push(*I); 1531 I = Available.remove(I); 1532 continue; 1533 } 1534 ++I; 1535 } 1536 } 1537 for (unsigned i = 0; Available.empty(); ++i) { 1538 assert(i <= (HazardRec->getMaxLookAhead() + MaxMinLatency) && 1539 "permanent hazard"); (void)i; 1540 bumpCycle(); 1541 releasePending(); 1542 } 1543 if (Available.size() == 1) 1544 return *Available.begin(); 1545 return NULL; 1546} 1547 1548/// Record the candidate policy for opposite zones with different critical 1549/// resources. 1550/// 1551/// If the CriticalZone is latency limited, don't force a policy for the 1552/// candidates here. Instead, setLatencyPolicy sets ReduceLatency if needed. 1553void ConvergingScheduler::balanceZones( 1554 ConvergingScheduler::SchedBoundary &CriticalZone, 1555 ConvergingScheduler::SchedCandidate &CriticalCand, 1556 ConvergingScheduler::SchedBoundary &OppositeZone, 1557 ConvergingScheduler::SchedCandidate &OppositeCand) { 1558 1559 if (!CriticalZone.IsResourceLimited) 1560 return; 1561 assert(SchedModel->hasInstrSchedModel() && "required schedmodel"); 1562 1563 SchedRemainder *Rem = CriticalZone.Rem; 1564 1565 // If the critical zone is overconsuming a resource relative to the 1566 // remainder, try to reduce it. 1567 unsigned RemainingCritCount = 1568 Rem->RemainingCounts[CriticalZone.CritResIdx]; 1569 if ((int)(Rem->getMaxRemainingCount(SchedModel) - RemainingCritCount) 1570 > (int)SchedModel->getLatencyFactor()) { 1571 CriticalCand.Policy.ReduceResIdx = CriticalZone.CritResIdx; 1572 DEBUG(dbgs() << "Balance " << CriticalZone.Available.getName() << " reduce " 1573 << SchedModel->getProcResource(CriticalZone.CritResIdx)->Name 1574 << '\n'); 1575 } 1576 // If the other zone is underconsuming a resource relative to the full zone, 1577 // try to increase it. 1578 unsigned OppositeCount = 1579 OppositeZone.ResourceCounts[CriticalZone.CritResIdx]; 1580 if ((int)(OppositeZone.ExpectedCount - OppositeCount) 1581 > (int)SchedModel->getLatencyFactor()) { 1582 OppositeCand.Policy.DemandResIdx = CriticalZone.CritResIdx; 1583 DEBUG(dbgs() << "Balance " << OppositeZone.Available.getName() << " demand " 1584 << SchedModel->getProcResource(OppositeZone.CritResIdx)->Name 1585 << '\n'); 1586 } 1587} 1588 1589/// Determine if the scheduled zones exceed resource limits or critical path and 1590/// set each candidate's ReduceHeight policy accordingly. 1591void ConvergingScheduler::checkResourceLimits( 1592 ConvergingScheduler::SchedCandidate &TopCand, 1593 ConvergingScheduler::SchedCandidate &BotCand) { 1594 1595 // Set ReduceLatency to true if needed. 1596 Bot.setLatencyPolicy(BotCand.Policy); 1597 Top.setLatencyPolicy(TopCand.Policy); 1598 1599 // Handle resource-limited regions. 1600 if (Top.IsResourceLimited && Bot.IsResourceLimited 1601 && Top.CritResIdx == Bot.CritResIdx) { 1602 // If the scheduled critical resource in both zones is no longer the 1603 // critical remaining resource, attempt to reduce resource height both ways. 1604 if (Top.CritResIdx != Rem.CritResIdx) { 1605 TopCand.Policy.ReduceResIdx = Top.CritResIdx; 1606 BotCand.Policy.ReduceResIdx = Bot.CritResIdx; 1607 DEBUG(dbgs() << "Reduce scheduled " 1608 << SchedModel->getProcResource(Top.CritResIdx)->Name << '\n'); 1609 } 1610 return; 1611 } 1612 // Handle latency-limited regions. 1613 if (!Top.IsResourceLimited && !Bot.IsResourceLimited) { 1614 // If the total scheduled expected latency exceeds the region's critical 1615 // path then reduce latency both ways. 1616 // 1617 // Just because a zone is not resource limited does not mean it is latency 1618 // limited. Unbuffered resource, such as max micro-ops may cause CurrCycle 1619 // to exceed expected latency. 1620 if ((Top.ExpectedLatency + Bot.ExpectedLatency >= Rem.CriticalPath) 1621 && (Rem.CriticalPath > Top.CurrCycle + Bot.CurrCycle)) { 1622 TopCand.Policy.ReduceLatency = true; 1623 BotCand.Policy.ReduceLatency = true; 1624 DEBUG(dbgs() << "Reduce scheduled latency " << Top.ExpectedLatency 1625 << " + " << Bot.ExpectedLatency << '\n'); 1626 } 1627 return; 1628 } 1629 // The critical resource is different in each zone, so request balancing. 1630 1631 // Compute the cost of each zone. 1632 Top.ExpectedCount = std::max(Top.ExpectedLatency, Top.CurrCycle); 1633 Top.ExpectedCount = std::max( 1634 Top.getCriticalCount(), 1635 Top.ExpectedCount * SchedModel->getLatencyFactor()); 1636 Bot.ExpectedCount = std::max(Bot.ExpectedLatency, Bot.CurrCycle); 1637 Bot.ExpectedCount = std::max( 1638 Bot.getCriticalCount(), 1639 Bot.ExpectedCount * SchedModel->getLatencyFactor()); 1640 1641 balanceZones(Top, TopCand, Bot, BotCand); 1642 balanceZones(Bot, BotCand, Top, TopCand); 1643} 1644 1645void ConvergingScheduler::SchedCandidate:: 1646initResourceDelta(const ScheduleDAGMI *DAG, 1647 const TargetSchedModel *SchedModel) { 1648 if (!Policy.ReduceResIdx && !Policy.DemandResIdx) 1649 return; 1650 1651 const MCSchedClassDesc *SC = DAG->getSchedClass(SU); 1652 for (TargetSchedModel::ProcResIter 1653 PI = SchedModel->getWriteProcResBegin(SC), 1654 PE = SchedModel->getWriteProcResEnd(SC); PI != PE; ++PI) { 1655 if (PI->ProcResourceIdx == Policy.ReduceResIdx) 1656 ResDelta.CritResources += PI->Cycles; 1657 if (PI->ProcResourceIdx == Policy.DemandResIdx) 1658 ResDelta.DemandedResources += PI->Cycles; 1659 } 1660} 1661 1662/// Return true if this heuristic determines order. 1663static bool tryLess(unsigned TryVal, unsigned CandVal, 1664 ConvergingScheduler::SchedCandidate &TryCand, 1665 ConvergingScheduler::SchedCandidate &Cand, 1666 ConvergingScheduler::CandReason Reason) { 1667 if (TryVal < CandVal) { 1668 TryCand.Reason = Reason; 1669 return true; 1670 } 1671 if (TryVal > CandVal) { 1672 if (Cand.Reason > Reason) 1673 Cand.Reason = Reason; 1674 return true; 1675 } 1676 return false; 1677} 1678 1679static bool tryGreater(unsigned TryVal, unsigned CandVal, 1680 ConvergingScheduler::SchedCandidate &TryCand, 1681 ConvergingScheduler::SchedCandidate &Cand, 1682 ConvergingScheduler::CandReason Reason) { 1683 if (TryVal > CandVal) { 1684 TryCand.Reason = Reason; 1685 return true; 1686 } 1687 if (TryVal < CandVal) { 1688 if (Cand.Reason > Reason) 1689 Cand.Reason = Reason; 1690 return true; 1691 } 1692 return false; 1693} 1694 1695static unsigned getWeakLeft(const SUnit *SU, bool isTop) { 1696 return (isTop) ? SU->WeakPredsLeft : SU->WeakSuccsLeft; 1697} 1698 1699/// Apply a set of heursitics to a new candidate. Heuristics are currently 1700/// hierarchical. This may be more efficient than a graduated cost model because 1701/// we don't need to evaluate all aspects of the model for each node in the 1702/// queue. But it's really done to make the heuristics easier to debug and 1703/// statistically analyze. 1704/// 1705/// \param Cand provides the policy and current best candidate. 1706/// \param TryCand refers to the next SUnit candidate, otherwise uninitialized. 1707/// \param Zone describes the scheduled zone that we are extending. 1708/// \param RPTracker describes reg pressure within the scheduled zone. 1709/// \param TempTracker is a scratch pressure tracker to reuse in queries. 1710void ConvergingScheduler::tryCandidate(SchedCandidate &Cand, 1711 SchedCandidate &TryCand, 1712 SchedBoundary &Zone, 1713 const RegPressureTracker &RPTracker, 1714 RegPressureTracker &TempTracker) { 1715 1716 // Always initialize TryCand's RPDelta. 1717 TempTracker.getMaxPressureDelta(TryCand.SU->getInstr(), TryCand.RPDelta, 1718 DAG->getRegionCriticalPSets(), 1719 DAG->getRegPressure().MaxSetPressure); 1720 1721 // Initialize the candidate if needed. 1722 if (!Cand.isValid()) { 1723 TryCand.Reason = NodeOrder; 1724 return; 1725 } 1726 // Avoid exceeding the target's limit. 1727 if (tryLess(TryCand.RPDelta.Excess.UnitIncrease, 1728 Cand.RPDelta.Excess.UnitIncrease, TryCand, Cand, SingleExcess)) 1729 return; 1730 if (Cand.Reason == SingleExcess) 1731 Cand.Reason = MultiPressure; 1732 1733 // Avoid increasing the max critical pressure in the scheduled region. 1734 if (tryLess(TryCand.RPDelta.CriticalMax.UnitIncrease, 1735 Cand.RPDelta.CriticalMax.UnitIncrease, 1736 TryCand, Cand, SingleCritical)) 1737 return; 1738 if (Cand.Reason == SingleCritical) 1739 Cand.Reason = MultiPressure; 1740 1741 // Keep clustered nodes together to encourage downstream peephole 1742 // optimizations which may reduce resource requirements. 1743 // 1744 // This is a best effort to set things up for a post-RA pass. Optimizations 1745 // like generating loads of multiple registers should ideally be done within 1746 // the scheduler pass by combining the loads during DAG postprocessing. 1747 const SUnit *NextClusterSU = 1748 Zone.isTop() ? DAG->getNextClusterSucc() : DAG->getNextClusterPred(); 1749 if (tryGreater(TryCand.SU == NextClusterSU, Cand.SU == NextClusterSU, 1750 TryCand, Cand, Cluster)) 1751 return; 1752 // Currently, weak edges are for clustering, so we hard-code that reason. 1753 // However, deferring the current TryCand will not change Cand's reason. 1754 CandReason OrigReason = Cand.Reason; 1755 if (tryLess(getWeakLeft(TryCand.SU, Zone.isTop()), 1756 getWeakLeft(Cand.SU, Zone.isTop()), 1757 TryCand, Cand, Cluster)) { 1758 Cand.Reason = OrigReason; 1759 return; 1760 } 1761 // Avoid critical resource consumption and balance the schedule. 1762 TryCand.initResourceDelta(DAG, SchedModel); 1763 if (tryLess(TryCand.ResDelta.CritResources, Cand.ResDelta.CritResources, 1764 TryCand, Cand, ResourceReduce)) 1765 return; 1766 if (tryGreater(TryCand.ResDelta.DemandedResources, 1767 Cand.ResDelta.DemandedResources, 1768 TryCand, Cand, ResourceDemand)) 1769 return; 1770 1771 // Avoid serializing long latency dependence chains. 1772 if (Cand.Policy.ReduceLatency) { 1773 if (Zone.isTop()) { 1774 if (Cand.SU->getDepth() * SchedModel->getLatencyFactor() 1775 > Zone.ExpectedCount) { 1776 if (tryLess(TryCand.SU->getDepth(), Cand.SU->getDepth(), 1777 TryCand, Cand, TopDepthReduce)) 1778 return; 1779 } 1780 if (tryGreater(TryCand.SU->getHeight(), Cand.SU->getHeight(), 1781 TryCand, Cand, TopPathReduce)) 1782 return; 1783 } 1784 else { 1785 if (Cand.SU->getHeight() * SchedModel->getLatencyFactor() 1786 > Zone.ExpectedCount) { 1787 if (tryLess(TryCand.SU->getHeight(), Cand.SU->getHeight(), 1788 TryCand, Cand, BotHeightReduce)) 1789 return; 1790 } 1791 if (tryGreater(TryCand.SU->getDepth(), Cand.SU->getDepth(), 1792 TryCand, Cand, BotPathReduce)) 1793 return; 1794 } 1795 } 1796 1797 // Avoid increasing the max pressure of the entire region. 1798 if (tryLess(TryCand.RPDelta.CurrentMax.UnitIncrease, 1799 Cand.RPDelta.CurrentMax.UnitIncrease, TryCand, Cand, SingleMax)) 1800 return; 1801 if (Cand.Reason == SingleMax) 1802 Cand.Reason = MultiPressure; 1803 1804 // Prefer immediate defs/users of the last scheduled instruction. This is a 1805 // nice pressure avoidance strategy that also conserves the processor's 1806 // register renaming resources and keeps the machine code readable. 1807 if (tryGreater(Zone.NextSUs.count(TryCand.SU), Zone.NextSUs.count(Cand.SU), 1808 TryCand, Cand, NextDefUse)) 1809 return; 1810 1811 // Fall through to original instruction order. 1812 if ((Zone.isTop() && TryCand.SU->NodeNum < Cand.SU->NodeNum) 1813 || (!Zone.isTop() && TryCand.SU->NodeNum > Cand.SU->NodeNum)) { 1814 TryCand.Reason = NodeOrder; 1815 } 1816} 1817 1818/// pickNodeFromQueue helper that returns true if the LHS reg pressure effect is 1819/// more desirable than RHS from scheduling standpoint. 1820static bool compareRPDelta(const RegPressureDelta &LHS, 1821 const RegPressureDelta &RHS) { 1822 // Compare each component of pressure in decreasing order of importance 1823 // without checking if any are valid. Invalid PressureElements are assumed to 1824 // have UnitIncrease==0, so are neutral. 1825 1826 // Avoid increasing the max critical pressure in the scheduled region. 1827 if (LHS.Excess.UnitIncrease != RHS.Excess.UnitIncrease) { 1828 DEBUG(dbgs() << "RP excess top - bot: " 1829 << (LHS.Excess.UnitIncrease - RHS.Excess.UnitIncrease) << '\n'); 1830 return LHS.Excess.UnitIncrease < RHS.Excess.UnitIncrease; 1831 } 1832 // Avoid increasing the max critical pressure in the scheduled region. 1833 if (LHS.CriticalMax.UnitIncrease != RHS.CriticalMax.UnitIncrease) { 1834 DEBUG(dbgs() << "RP critical top - bot: " 1835 << (LHS.CriticalMax.UnitIncrease - RHS.CriticalMax.UnitIncrease) 1836 << '\n'); 1837 return LHS.CriticalMax.UnitIncrease < RHS.CriticalMax.UnitIncrease; 1838 } 1839 // Avoid increasing the max pressure of the entire region. 1840 if (LHS.CurrentMax.UnitIncrease != RHS.CurrentMax.UnitIncrease) { 1841 DEBUG(dbgs() << "RP current top - bot: " 1842 << (LHS.CurrentMax.UnitIncrease - RHS.CurrentMax.UnitIncrease) 1843 << '\n'); 1844 return LHS.CurrentMax.UnitIncrease < RHS.CurrentMax.UnitIncrease; 1845 } 1846 return false; 1847} 1848 1849#ifndef NDEBUG 1850const char *ConvergingScheduler::getReasonStr( 1851 ConvergingScheduler::CandReason Reason) { 1852 switch (Reason) { 1853 case NoCand: return "NOCAND "; 1854 case SingleExcess: return "REG-EXCESS"; 1855 case SingleCritical: return "REG-CRIT "; 1856 case Cluster: return "CLUSTER "; 1857 case SingleMax: return "REG-MAX "; 1858 case MultiPressure: return "REG-MULTI "; 1859 case ResourceReduce: return "RES-REDUCE"; 1860 case ResourceDemand: return "RES-DEMAND"; 1861 case TopDepthReduce: return "TOP-DEPTH "; 1862 case TopPathReduce: return "TOP-PATH "; 1863 case BotHeightReduce:return "BOT-HEIGHT"; 1864 case BotPathReduce: return "BOT-PATH "; 1865 case NextDefUse: return "DEF-USE "; 1866 case NodeOrder: return "ORDER "; 1867 }; 1868 llvm_unreachable("Unknown reason!"); 1869} 1870 1871void ConvergingScheduler::traceCandidate(const SchedCandidate &Cand) { 1872 PressureElement P; 1873 unsigned ResIdx = 0; 1874 unsigned Latency = 0; 1875 switch (Cand.Reason) { 1876 default: 1877 break; 1878 case SingleExcess: 1879 P = Cand.RPDelta.Excess; 1880 break; 1881 case SingleCritical: 1882 P = Cand.RPDelta.CriticalMax; 1883 break; 1884 case SingleMax: 1885 P = Cand.RPDelta.CurrentMax; 1886 break; 1887 case ResourceReduce: 1888 ResIdx = Cand.Policy.ReduceResIdx; 1889 break; 1890 case ResourceDemand: 1891 ResIdx = Cand.Policy.DemandResIdx; 1892 break; 1893 case TopDepthReduce: 1894 Latency = Cand.SU->getDepth(); 1895 break; 1896 case TopPathReduce: 1897 Latency = Cand.SU->getHeight(); 1898 break; 1899 case BotHeightReduce: 1900 Latency = Cand.SU->getHeight(); 1901 break; 1902 case BotPathReduce: 1903 Latency = Cand.SU->getDepth(); 1904 break; 1905 } 1906 dbgs() << " SU(" << Cand.SU->NodeNum << ") " << getReasonStr(Cand.Reason); 1907 if (P.isValid()) 1908 dbgs() << " " << TRI->getRegPressureSetName(P.PSetID) 1909 << ":" << P.UnitIncrease << " "; 1910 else 1911 dbgs() << " "; 1912 if (ResIdx) 1913 dbgs() << " " << SchedModel->getProcResource(ResIdx)->Name << " "; 1914 else 1915 dbgs() << " "; 1916 if (Latency) 1917 dbgs() << " " << Latency << " cycles "; 1918 else 1919 dbgs() << " "; 1920 dbgs() << '\n'; 1921} 1922#endif 1923 1924/// Pick the best candidate from the top queue. 1925/// 1926/// TODO: getMaxPressureDelta results can be mostly cached for each SUnit during 1927/// DAG building. To adjust for the current scheduling location we need to 1928/// maintain the number of vreg uses remaining to be top-scheduled. 1929void ConvergingScheduler::pickNodeFromQueue(SchedBoundary &Zone, 1930 const RegPressureTracker &RPTracker, 1931 SchedCandidate &Cand) { 1932 ReadyQueue &Q = Zone.Available; 1933 1934 DEBUG(Q.dump()); 1935 1936 // getMaxPressureDelta temporarily modifies the tracker. 1937 RegPressureTracker &TempTracker = const_cast<RegPressureTracker&>(RPTracker); 1938 1939 for (ReadyQueue::iterator I = Q.begin(), E = Q.end(); I != E; ++I) { 1940 1941 SchedCandidate TryCand(Cand.Policy); 1942 TryCand.SU = *I; 1943 tryCandidate(Cand, TryCand, Zone, RPTracker, TempTracker); 1944 if (TryCand.Reason != NoCand) { 1945 // Initialize resource delta if needed in case future heuristics query it. 1946 if (TryCand.ResDelta == SchedResourceDelta()) 1947 TryCand.initResourceDelta(DAG, SchedModel); 1948 Cand.setBest(TryCand); 1949 DEBUG(traceCandidate(Cand)); 1950 } 1951 } 1952} 1953 1954static void tracePick(const ConvergingScheduler::SchedCandidate &Cand, 1955 bool IsTop) { 1956 DEBUG(dbgs() << "Pick " << (IsTop ? "Top" : "Bot") 1957 << " SU(" << Cand.SU->NodeNum << ") " 1958 << ConvergingScheduler::getReasonStr(Cand.Reason) << '\n'); 1959} 1960 1961/// Pick the best candidate node from either the top or bottom queue. 1962SUnit *ConvergingScheduler::pickNodeBidirectional(bool &IsTopNode) { 1963 // Schedule as far as possible in the direction of no choice. This is most 1964 // efficient, but also provides the best heuristics for CriticalPSets. 1965 if (SUnit *SU = Bot.pickOnlyChoice()) { 1966 IsTopNode = false; 1967 return SU; 1968 } 1969 if (SUnit *SU = Top.pickOnlyChoice()) { 1970 IsTopNode = true; 1971 return SU; 1972 } 1973 CandPolicy NoPolicy; 1974 SchedCandidate BotCand(NoPolicy); 1975 SchedCandidate TopCand(NoPolicy); 1976 checkResourceLimits(TopCand, BotCand); 1977 1978 // Prefer bottom scheduling when heuristics are silent. 1979 pickNodeFromQueue(Bot, DAG->getBotRPTracker(), BotCand); 1980 assert(BotCand.Reason != NoCand && "failed to find the first candidate"); 1981 1982 // If either Q has a single candidate that provides the least increase in 1983 // Excess pressure, we can immediately schedule from that Q. 1984 // 1985 // RegionCriticalPSets summarizes the pressure within the scheduled region and 1986 // affects picking from either Q. If scheduling in one direction must 1987 // increase pressure for one of the excess PSets, then schedule in that 1988 // direction first to provide more freedom in the other direction. 1989 if (BotCand.Reason == SingleExcess || BotCand.Reason == SingleCritical) { 1990 IsTopNode = false; 1991 tracePick(BotCand, IsTopNode); 1992 return BotCand.SU; 1993 } 1994 // Check if the top Q has a better candidate. 1995 pickNodeFromQueue(Top, DAG->getTopRPTracker(), TopCand); 1996 assert(TopCand.Reason != NoCand && "failed to find the first candidate"); 1997 1998 // If either Q has a single candidate that minimizes pressure above the 1999 // original region's pressure pick it. 2000 if (TopCand.Reason <= SingleMax || BotCand.Reason <= SingleMax) { 2001 if (TopCand.Reason < BotCand.Reason) { 2002 IsTopNode = true; 2003 tracePick(TopCand, IsTopNode); 2004 return TopCand.SU; 2005 } 2006 IsTopNode = false; 2007 tracePick(BotCand, IsTopNode); 2008 return BotCand.SU; 2009 } 2010 // Check for a salient pressure difference and pick the best from either side. 2011 if (compareRPDelta(TopCand.RPDelta, BotCand.RPDelta)) { 2012 IsTopNode = true; 2013 tracePick(TopCand, IsTopNode); 2014 return TopCand.SU; 2015 } 2016 // Otherwise prefer the bottom candidate, in node order if all else failed. 2017 if (TopCand.Reason < BotCand.Reason) { 2018 IsTopNode = true; 2019 tracePick(TopCand, IsTopNode); 2020 return TopCand.SU; 2021 } 2022 IsTopNode = false; 2023 tracePick(BotCand, IsTopNode); 2024 return BotCand.SU; 2025} 2026 2027/// Pick the best node to balance the schedule. Implements MachineSchedStrategy. 2028SUnit *ConvergingScheduler::pickNode(bool &IsTopNode) { 2029 if (DAG->top() == DAG->bottom()) { 2030 assert(Top.Available.empty() && Top.Pending.empty() && 2031 Bot.Available.empty() && Bot.Pending.empty() && "ReadyQ garbage"); 2032 return NULL; 2033 } 2034 SUnit *SU; 2035 do { 2036 if (ForceTopDown) { 2037 SU = Top.pickOnlyChoice(); 2038 if (!SU) { 2039 CandPolicy NoPolicy; 2040 SchedCandidate TopCand(NoPolicy); 2041 pickNodeFromQueue(Top, DAG->getTopRPTracker(), TopCand); 2042 assert(TopCand.Reason != NoCand && "failed to find the first candidate"); 2043 SU = TopCand.SU; 2044 } 2045 IsTopNode = true; 2046 } 2047 else if (ForceBottomUp) { 2048 SU = Bot.pickOnlyChoice(); 2049 if (!SU) { 2050 CandPolicy NoPolicy; 2051 SchedCandidate BotCand(NoPolicy); 2052 pickNodeFromQueue(Bot, DAG->getBotRPTracker(), BotCand); 2053 assert(BotCand.Reason != NoCand && "failed to find the first candidate"); 2054 SU = BotCand.SU; 2055 } 2056 IsTopNode = false; 2057 } 2058 else { 2059 SU = pickNodeBidirectional(IsTopNode); 2060 } 2061 } while (SU->isScheduled); 2062 2063 if (SU->isTopReady()) 2064 Top.removeReady(SU); 2065 if (SU->isBottomReady()) 2066 Bot.removeReady(SU); 2067 2068 DEBUG(dbgs() << "Scheduling " << *SU->getInstr()); 2069 return SU; 2070} 2071 2072/// Update the scheduler's state after scheduling a node. This is the same node 2073/// that was just returned by pickNode(). However, ScheduleDAGMI needs to update 2074/// it's state based on the current cycle before MachineSchedStrategy does. 2075void ConvergingScheduler::schedNode(SUnit *SU, bool IsTopNode) { 2076 if (IsTopNode) { 2077 SU->TopReadyCycle = Top.CurrCycle; 2078 Top.bumpNode(SU); 2079 } 2080 else { 2081 SU->BotReadyCycle = Bot.CurrCycle; 2082 Bot.bumpNode(SU); 2083 } 2084} 2085 2086/// Create the standard converging machine scheduler. This will be used as the 2087/// default scheduler if the target does not set a default. 2088static ScheduleDAGInstrs *createConvergingSched(MachineSchedContext *C) { 2089 assert((!ForceTopDown || !ForceBottomUp) && 2090 "-misched-topdown incompatible with -misched-bottomup"); 2091 ScheduleDAGMI *DAG = new ScheduleDAGMI(C, new ConvergingScheduler()); 2092 // Register DAG post-processors. 2093 if (EnableLoadCluster) 2094 DAG->addMutation(new LoadClusterMutation(DAG->TII, DAG->TRI)); 2095 if (EnableMacroFusion) 2096 DAG->addMutation(new MacroFusion(DAG->TII)); 2097 return DAG; 2098} 2099static MachineSchedRegistry 2100ConvergingSchedRegistry("converge", "Standard converging scheduler.", 2101 createConvergingSched); 2102 2103//===----------------------------------------------------------------------===// 2104// ILP Scheduler. Currently for experimental analysis of heuristics. 2105//===----------------------------------------------------------------------===// 2106 2107namespace { 2108/// \brief Order nodes by the ILP metric. 2109struct ILPOrder { 2110 const SchedDFSResult *DFSResult; 2111 const BitVector *ScheduledTrees; 2112 bool MaximizeILP; 2113 2114 ILPOrder(bool MaxILP): DFSResult(0), ScheduledTrees(0), MaximizeILP(MaxILP) {} 2115 2116 /// \brief Apply a less-than relation on node priority. 2117 /// 2118 /// (Return true if A comes after B in the Q.) 2119 bool operator()(const SUnit *A, const SUnit *B) const { 2120 unsigned SchedTreeA = DFSResult->getSubtreeID(A); 2121 unsigned SchedTreeB = DFSResult->getSubtreeID(B); 2122 if (SchedTreeA != SchedTreeB) { 2123 // Unscheduled trees have lower priority. 2124 if (ScheduledTrees->test(SchedTreeA) != ScheduledTrees->test(SchedTreeB)) 2125 return ScheduledTrees->test(SchedTreeB); 2126 2127 // Trees with shallower connections have have lower priority. 2128 if (DFSResult->getSubtreeLevel(SchedTreeA) 2129 != DFSResult->getSubtreeLevel(SchedTreeB)) { 2130 return DFSResult->getSubtreeLevel(SchedTreeA) 2131 < DFSResult->getSubtreeLevel(SchedTreeB); 2132 } 2133 } 2134 if (MaximizeILP) 2135 return DFSResult->getILP(A) < DFSResult->getILP(B); 2136 else 2137 return DFSResult->getILP(A) > DFSResult->getILP(B); 2138 } 2139}; 2140 2141/// \brief Schedule based on the ILP metric. 2142class ILPScheduler : public MachineSchedStrategy { 2143 /// In case all subtrees are eventually connected to a common root through 2144 /// data dependence (e.g. reduction), place an upper limit on their size. 2145 /// 2146 /// FIXME: A subtree limit is generally good, but in the situation commented 2147 /// above, where multiple similar subtrees feed a common root, we should 2148 /// only split at a point where the resulting subtrees will be balanced. 2149 /// (a motivating test case must be found). 2150 static const unsigned SubtreeLimit = 16; 2151 2152 ScheduleDAGMI *DAG; 2153 ILPOrder Cmp; 2154 2155 std::vector<SUnit*> ReadyQ; 2156public: 2157 ILPScheduler(bool MaximizeILP): DAG(0), Cmp(MaximizeILP) {} 2158 2159 virtual void initialize(ScheduleDAGMI *dag) { 2160 DAG = dag; 2161 DAG->computeDFSResult(); 2162 Cmp.DFSResult = DAG->getDFSResult(); 2163 Cmp.ScheduledTrees = &DAG->getScheduledTrees(); 2164 ReadyQ.clear(); 2165 } 2166 2167 virtual void registerRoots() { 2168 // Restore the heap in ReadyQ with the updated DFS results. 2169 std::make_heap(ReadyQ.begin(), ReadyQ.end(), Cmp); 2170 } 2171 2172 /// Implement MachineSchedStrategy interface. 2173 /// ----------------------------------------- 2174 2175 /// Callback to select the highest priority node from the ready Q. 2176 virtual SUnit *pickNode(bool &IsTopNode) { 2177 if (ReadyQ.empty()) return NULL; 2178 std::pop_heap(ReadyQ.begin(), ReadyQ.end(), Cmp); 2179 SUnit *SU = ReadyQ.back(); 2180 ReadyQ.pop_back(); 2181 IsTopNode = false; 2182 DEBUG(dbgs() << "*** Scheduling " << "SU(" << SU->NodeNum << "): " 2183 << *SU->getInstr() 2184 << " ILP: " << DAG->getDFSResult()->getILP(SU) 2185 << " Tree: " << DAG->getDFSResult()->getSubtreeID(SU) << " @" 2186 << DAG->getDFSResult()->getSubtreeLevel( 2187 DAG->getDFSResult()->getSubtreeID(SU)) << '\n'); 2188 return SU; 2189 } 2190 2191 /// \brief Scheduler callback to notify that a new subtree is scheduled. 2192 virtual void scheduleTree(unsigned SubtreeID) { 2193 std::make_heap(ReadyQ.begin(), ReadyQ.end(), Cmp); 2194 } 2195 2196 /// Callback after a node is scheduled. Mark a newly scheduled tree, notify 2197 /// DFSResults, and resort the priority Q. 2198 virtual void schedNode(SUnit *SU, bool IsTopNode) { 2199 assert(!IsTopNode && "SchedDFSResult needs bottom-up"); 2200 } 2201 2202 virtual void releaseTopNode(SUnit *) { /*only called for top roots*/ } 2203 2204 virtual void releaseBottomNode(SUnit *SU) { 2205 ReadyQ.push_back(SU); 2206 std::push_heap(ReadyQ.begin(), ReadyQ.end(), Cmp); 2207 } 2208}; 2209} // namespace 2210 2211static ScheduleDAGInstrs *createILPMaxScheduler(MachineSchedContext *C) { 2212 return new ScheduleDAGMI(C, new ILPScheduler(true)); 2213} 2214static ScheduleDAGInstrs *createILPMinScheduler(MachineSchedContext *C) { 2215 return new ScheduleDAGMI(C, new ILPScheduler(false)); 2216} 2217static MachineSchedRegistry ILPMaxRegistry( 2218 "ilpmax", "Schedule bottom-up for max ILP", createILPMaxScheduler); 2219static MachineSchedRegistry ILPMinRegistry( 2220 "ilpmin", "Schedule bottom-up for min ILP", createILPMinScheduler); 2221 2222//===----------------------------------------------------------------------===// 2223// Machine Instruction Shuffler for Correctness Testing 2224//===----------------------------------------------------------------------===// 2225 2226#ifndef NDEBUG 2227namespace { 2228/// Apply a less-than relation on the node order, which corresponds to the 2229/// instruction order prior to scheduling. IsReverse implements greater-than. 2230template<bool IsReverse> 2231struct SUnitOrder { 2232 bool operator()(SUnit *A, SUnit *B) const { 2233 if (IsReverse) 2234 return A->NodeNum > B->NodeNum; 2235 else 2236 return A->NodeNum < B->NodeNum; 2237 } 2238}; 2239 2240/// Reorder instructions as much as possible. 2241class InstructionShuffler : public MachineSchedStrategy { 2242 bool IsAlternating; 2243 bool IsTopDown; 2244 2245 // Using a less-than relation (SUnitOrder<false>) for the TopQ priority 2246 // gives nodes with a higher number higher priority causing the latest 2247 // instructions to be scheduled first. 2248 PriorityQueue<SUnit*, std::vector<SUnit*>, SUnitOrder<false> > 2249 TopQ; 2250 // When scheduling bottom-up, use greater-than as the queue priority. 2251 PriorityQueue<SUnit*, std::vector<SUnit*>, SUnitOrder<true> > 2252 BottomQ; 2253public: 2254 InstructionShuffler(bool alternate, bool topdown) 2255 : IsAlternating(alternate), IsTopDown(topdown) {} 2256 2257 virtual void initialize(ScheduleDAGMI *) { 2258 TopQ.clear(); 2259 BottomQ.clear(); 2260 } 2261 2262 /// Implement MachineSchedStrategy interface. 2263 /// ----------------------------------------- 2264 2265 virtual SUnit *pickNode(bool &IsTopNode) { 2266 SUnit *SU; 2267 if (IsTopDown) { 2268 do { 2269 if (TopQ.empty()) return NULL; 2270 SU = TopQ.top(); 2271 TopQ.pop(); 2272 } while (SU->isScheduled); 2273 IsTopNode = true; 2274 } 2275 else { 2276 do { 2277 if (BottomQ.empty()) return NULL; 2278 SU = BottomQ.top(); 2279 BottomQ.pop(); 2280 } while (SU->isScheduled); 2281 IsTopNode = false; 2282 } 2283 if (IsAlternating) 2284 IsTopDown = !IsTopDown; 2285 return SU; 2286 } 2287 2288 virtual void schedNode(SUnit *SU, bool IsTopNode) {} 2289 2290 virtual void releaseTopNode(SUnit *SU) { 2291 TopQ.push(SU); 2292 } 2293 virtual void releaseBottomNode(SUnit *SU) { 2294 BottomQ.push(SU); 2295 } 2296}; 2297} // namespace 2298 2299static ScheduleDAGInstrs *createInstructionShuffler(MachineSchedContext *C) { 2300 bool Alternate = !ForceTopDown && !ForceBottomUp; 2301 bool TopDown = !ForceBottomUp; 2302 assert((TopDown || !ForceTopDown) && 2303 "-misched-topdown incompatible with -misched-bottomup"); 2304 return new ScheduleDAGMI(C, new InstructionShuffler(Alternate, TopDown)); 2305} 2306static MachineSchedRegistry ShufflerRegistry( 2307 "shuffle", "Shuffle machine instructions alternating directions", 2308 createInstructionShuffler); 2309#endif // !NDEBUG 2310 2311//===----------------------------------------------------------------------===// 2312// GraphWriter support for ScheduleDAGMI. 2313//===----------------------------------------------------------------------===// 2314 2315#ifndef NDEBUG 2316namespace llvm { 2317 2318template<> struct GraphTraits< 2319 ScheduleDAGMI*> : public GraphTraits<ScheduleDAG*> {}; 2320 2321template<> 2322struct DOTGraphTraits<ScheduleDAGMI*> : public DefaultDOTGraphTraits { 2323 2324 DOTGraphTraits (bool isSimple=false) : DefaultDOTGraphTraits(isSimple) {} 2325 2326 static std::string getGraphName(const ScheduleDAG *G) { 2327 return G->MF.getName(); 2328 } 2329 2330 static bool renderGraphFromBottomUp() { 2331 return true; 2332 } 2333 2334 static bool isNodeHidden(const SUnit *Node) { 2335 return (Node->NumPreds > 10 || Node->NumSuccs > 10); 2336 } 2337 2338 static bool hasNodeAddressLabel(const SUnit *Node, 2339 const ScheduleDAG *Graph) { 2340 return false; 2341 } 2342 2343 /// If you want to override the dot attributes printed for a particular 2344 /// edge, override this method. 2345 static std::string getEdgeAttributes(const SUnit *Node, 2346 SUnitIterator EI, 2347 const ScheduleDAG *Graph) { 2348 if (EI.isArtificialDep()) 2349 return "color=cyan,style=dashed"; 2350 if (EI.isCtrlDep()) 2351 return "color=blue,style=dashed"; 2352 return ""; 2353 } 2354 2355 static std::string getNodeLabel(const SUnit *SU, const ScheduleDAG *G) { 2356 std::string Str; 2357 raw_string_ostream SS(Str); 2358 SS << "SU(" << SU->NodeNum << ')'; 2359 return SS.str(); 2360 } 2361 static std::string getNodeDescription(const SUnit *SU, const ScheduleDAG *G) { 2362 return G->getGraphNodeLabel(SU); 2363 } 2364 2365 static std::string getNodeAttributes(const SUnit *N, 2366 const ScheduleDAG *Graph) { 2367 std::string Str("shape=Mrecord"); 2368 const SchedDFSResult *DFS = 2369 static_cast<const ScheduleDAGMI*>(Graph)->getDFSResult(); 2370 if (DFS) { 2371 Str += ",style=filled,fillcolor=\"#"; 2372 Str += DOT::getColorString(DFS->getSubtreeID(N)); 2373 Str += '"'; 2374 } 2375 return Str; 2376 } 2377}; 2378} // namespace llvm 2379#endif // NDEBUG 2380 2381/// viewGraph - Pop up a ghostview window with the reachable parts of the DAG 2382/// rendered using 'dot'. 2383/// 2384void ScheduleDAGMI::viewGraph(const Twine &Name, const Twine &Title) { 2385#ifndef NDEBUG 2386 ViewGraph(this, Name, false, Title); 2387#else 2388 errs() << "ScheduleDAGMI::viewGraph is only available in debug builds on " 2389 << "systems with Graphviz or gv!\n"; 2390#endif // NDEBUG 2391} 2392 2393/// Out-of-line implementation with no arguments is handy for gdb. 2394void ScheduleDAGMI::viewGraph() { 2395 viewGraph(getDAGName(), "Scheduling-Units Graph for " + getDAGName()); 2396} 2397