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