lib/CodeGen/MachineScheduler.cpp

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