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