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