1//===- MachineScheduler.cpp - Machine Instruction Scheduler ---------------===//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// MachineScheduler schedules machine instructions after phi elimination. It
11// preserves LiveIntervals so it can be invoked before register allocation.
12//
13//===----------------------------------------------------------------------===//
14
15#define DEBUG_TYPE "misched"
16
17#include "llvm/CodeGen/LiveIntervalAnalysis.h"
18#include "llvm/CodeGen/MachineScheduler.h"
19#include "llvm/CodeGen/Passes.h"
20#include "llvm/CodeGen/RegisterClassInfo.h"
21#include "llvm/CodeGen/ScheduleDAGILP.h"
22#include "llvm/CodeGen/ScheduleHazardRecognizer.h"
23#include "llvm/Analysis/AliasAnalysis.h"
24#include "llvm/Support/CommandLine.h"
25#include "llvm/Support/Debug.h"
26#include "llvm/Support/ErrorHandling.h"
27#include "llvm/Support/raw_ostream.h"
28#include "llvm/ADT/OwningPtr.h"
29#include "llvm/ADT/PriorityQueue.h"
30
31#include <queue>
32
33using namespace llvm;
34
35namespace llvm {
36cl::opt<bool> ForceTopDown("misched-topdown", cl::Hidden,
37                           cl::desc("Force top-down list scheduling"));
38cl::opt<bool> ForceBottomUp("misched-bottomup", cl::Hidden,
39                            cl::desc("Force bottom-up list scheduling"));
40}
41
42#ifndef NDEBUG
43static cl::opt<bool> ViewMISchedDAGs("view-misched-dags", cl::Hidden,
44  cl::desc("Pop up a window to show MISched dags after they are processed"));
45
46static cl::opt<unsigned> MISchedCutoff("misched-cutoff", cl::Hidden,
47  cl::desc("Stop scheduling after N instructions"), cl::init(~0U));
48#else
49static bool ViewMISchedDAGs = false;
50#endif // NDEBUG
51
52//===----------------------------------------------------------------------===//
53// Machine Instruction Scheduling Pass and Registry
54//===----------------------------------------------------------------------===//
55
56MachineSchedContext::MachineSchedContext():
57    MF(0), MLI(0), MDT(0), PassConfig(0), AA(0), LIS(0) {
58  RegClassInfo = new RegisterClassInfo();
59}
60
61MachineSchedContext::~MachineSchedContext() {
62  delete RegClassInfo;
63}
64
65namespace {
66/// MachineScheduler runs after coalescing and before register allocation.
67class MachineScheduler : public MachineSchedContext,
68                         public MachineFunctionPass {
69public:
70  MachineScheduler();
71
72  virtual void getAnalysisUsage(AnalysisUsage &AU) const;
73
74  virtual void releaseMemory() {}
75
76  virtual bool runOnMachineFunction(MachineFunction&);
77
78  virtual void print(raw_ostream &O, const Module* = 0) const;
79
80  static char ID; // Class identification, replacement for typeinfo
81};
82} // namespace
83
84char MachineScheduler::ID = 0;
85
86char &llvm::MachineSchedulerID = MachineScheduler::ID;
87
88INITIALIZE_PASS_BEGIN(MachineScheduler, "misched",
89                      "Machine Instruction Scheduler", false, false)
90INITIALIZE_AG_DEPENDENCY(AliasAnalysis)
91INITIALIZE_PASS_DEPENDENCY(SlotIndexes)
92INITIALIZE_PASS_DEPENDENCY(LiveIntervals)
93INITIALIZE_PASS_END(MachineScheduler, "misched",
94                    "Machine Instruction Scheduler", false, false)
95
96MachineScheduler::MachineScheduler()
97: MachineFunctionPass(ID) {
98  initializeMachineSchedulerPass(*PassRegistry::getPassRegistry());
99}
100
101void MachineScheduler::getAnalysisUsage(AnalysisUsage &AU) const {
102  AU.setPreservesCFG();
103  AU.addRequiredID(MachineDominatorsID);
104  AU.addRequired<MachineLoopInfo>();
105  AU.addRequired<AliasAnalysis>();
106  AU.addRequired<TargetPassConfig>();
107  AU.addRequired<SlotIndexes>();
108  AU.addPreserved<SlotIndexes>();
109  AU.addRequired<LiveIntervals>();
110  AU.addPreserved<LiveIntervals>();
111  MachineFunctionPass::getAnalysisUsage(AU);
112}
113
114MachinePassRegistry MachineSchedRegistry::Registry;
115
116/// A dummy default scheduler factory indicates whether the scheduler
117/// is overridden on the command line.
118static ScheduleDAGInstrs *useDefaultMachineSched(MachineSchedContext *C) {
119  return 0;
120}
121
122/// MachineSchedOpt allows command line selection of the scheduler.
123static cl::opt<MachineSchedRegistry::ScheduleDAGCtor, false,
124               RegisterPassParser<MachineSchedRegistry> >
125MachineSchedOpt("misched",
126                cl::init(&useDefaultMachineSched), cl::Hidden,
127                cl::desc("Machine instruction scheduler to use"));
128
129static MachineSchedRegistry
130DefaultSchedRegistry("default", "Use the target's default scheduler choice.",
131                     useDefaultMachineSched);
132
133/// Forward declare the standard machine scheduler. This will be used as the
134/// default scheduler if the target does not set a default.
135static ScheduleDAGInstrs *createConvergingSched(MachineSchedContext *C);
136
137
138/// Decrement this iterator until reaching the top or a non-debug instr.
139static MachineBasicBlock::iterator
140priorNonDebug(MachineBasicBlock::iterator I, MachineBasicBlock::iterator Beg) {
141  assert(I != Beg && "reached the top of the region, cannot decrement");
142  while (--I != Beg) {
143    if (!I->isDebugValue())
144      break;
145  }
146  return I;
147}
148
149/// If this iterator is a debug value, increment until reaching the End or a
150/// non-debug instruction.
151static MachineBasicBlock::iterator
152nextIfDebug(MachineBasicBlock::iterator I, MachineBasicBlock::iterator End) {
153  for(; I != End; ++I) {
154    if (!I->isDebugValue())
155      break;
156  }
157  return I;
158}
159
160/// Top-level MachineScheduler pass driver.
161///
162/// Visit blocks in function order. Divide each block into scheduling regions
163/// and visit them bottom-up. Visiting regions bottom-up is not required, but is
164/// consistent with the DAG builder, which traverses the interior of the
165/// scheduling regions bottom-up.
166///
167/// This design avoids exposing scheduling boundaries to the DAG builder,
168/// simplifying the DAG builder's support for "special" target instructions.
169/// At the same time the design allows target schedulers to operate across
170/// scheduling boundaries, for example to bundle the boudary instructions
171/// without reordering them. This creates complexity, because the target
172/// scheduler must update the RegionBegin and RegionEnd positions cached by
173/// ScheduleDAGInstrs whenever adding or removing instructions. A much simpler
174/// design would be to split blocks at scheduling boundaries, but LLVM has a
175/// general bias against block splitting purely for implementation simplicity.
176bool MachineScheduler::runOnMachineFunction(MachineFunction &mf) {
177  DEBUG(dbgs() << "Before MISsched:\n"; mf.print(dbgs()));
178
179  // Initialize the context of the pass.
180  MF = &mf;
181  MLI = &getAnalysis<MachineLoopInfo>();
182  MDT = &getAnalysis<MachineDominatorTree>();
183  PassConfig = &getAnalysis<TargetPassConfig>();
184  AA = &getAnalysis<AliasAnalysis>();
185
186  LIS = &getAnalysis<LiveIntervals>();
187  const TargetInstrInfo *TII = MF->getTarget().getInstrInfo();
188
189  RegClassInfo->runOnMachineFunction(*MF);
190
191  // Select the scheduler, or set the default.
192  MachineSchedRegistry::ScheduleDAGCtor Ctor = MachineSchedOpt;
193  if (Ctor == useDefaultMachineSched) {
194    // Get the default scheduler set by the target.
195    Ctor = MachineSchedRegistry::getDefault();
196    if (!Ctor) {
197      Ctor = createConvergingSched;
198      MachineSchedRegistry::setDefault(Ctor);
199    }
200  }
201  // Instantiate the selected scheduler.
202  OwningPtr<ScheduleDAGInstrs> Scheduler(Ctor(this));
203
204  // Visit all machine basic blocks.
205  //
206  // TODO: Visit blocks in global postorder or postorder within the bottom-up
207  // loop tree. Then we can optionally compute global RegPressure.
208  for (MachineFunction::iterator MBB = MF->begin(), MBBEnd = MF->end();
209       MBB != MBBEnd; ++MBB) {
210
211    Scheduler->startBlock(MBB);
212
213    // Break the block into scheduling regions [I, RegionEnd), and schedule each
214    // region as soon as it is discovered. RegionEnd points the scheduling
215    // boundary at the bottom of the region. The DAG does not include RegionEnd,
216    // but the region does (i.e. the next RegionEnd is above the previous
217    // RegionBegin). If the current block has no terminator then RegionEnd ==
218    // MBB->end() for the bottom region.
219    //
220    // The Scheduler may insert instructions during either schedule() or
221    // exitRegion(), even for empty regions. So the local iterators 'I' and
222    // 'RegionEnd' are invalid across these calls.
223    unsigned RemainingCount = MBB->size();
224    for(MachineBasicBlock::iterator RegionEnd = MBB->end();
225        RegionEnd != MBB->begin(); RegionEnd = Scheduler->begin()) {
226
227      // Avoid decrementing RegionEnd for blocks with no terminator.
228      if (RegionEnd != MBB->end()
229          || TII->isSchedulingBoundary(llvm::prior(RegionEnd), MBB, *MF)) {
230        --RegionEnd;
231        // Count the boundary instruction.
232        --RemainingCount;
233      }
234
235      // The next region starts above the previous region. Look backward in the
236      // instruction stream until we find the nearest boundary.
237      MachineBasicBlock::iterator I = RegionEnd;
238      for(;I != MBB->begin(); --I, --RemainingCount) {
239        if (TII->isSchedulingBoundary(llvm::prior(I), MBB, *MF))
240          break;
241      }
242      // Notify the scheduler of the region, even if we may skip scheduling
243      // it. Perhaps it still needs to be bundled.
244      Scheduler->enterRegion(MBB, I, RegionEnd, RemainingCount);
245
246      // Skip empty scheduling regions (0 or 1 schedulable instructions).
247      if (I == RegionEnd || I == llvm::prior(RegionEnd)) {
248        // Close the current region. Bundle the terminator if needed.
249        // This invalidates 'RegionEnd' and 'I'.
250        Scheduler->exitRegion();
251        continue;
252      }
253      DEBUG(dbgs() << "********** MI Scheduling **********\n");
254      DEBUG(dbgs() << MF->getName()
255            << ":BB#" << MBB->getNumber() << "\n  From: " << *I << "    To: ";
256            if (RegionEnd != MBB->end()) dbgs() << *RegionEnd;
257            else dbgs() << "End";
258            dbgs() << " Remaining: " << RemainingCount << "\n");
259
260      // Schedule a region: possibly reorder instructions.
261      // This invalidates 'RegionEnd' and 'I'.
262      Scheduler->schedule();
263
264      // Close the current region.
265      Scheduler->exitRegion();
266
267      // Scheduling has invalidated the current iterator 'I'. Ask the
268      // scheduler for the top of it's scheduled region.
269      RegionEnd = Scheduler->begin();
270    }
271    assert(RemainingCount == 0 && "Instruction count mismatch!");
272    Scheduler->finishBlock();
273  }
274  Scheduler->finalizeSchedule();
275  DEBUG(LIS->print(dbgs()));
276  return true;
277}
278
279void MachineScheduler::print(raw_ostream &O, const Module* m) const {
280  // unimplemented
281}
282
283#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
284void ReadyQueue::dump() {
285  dbgs() << Name << ": ";
286  for (unsigned i = 0, e = Queue.size(); i < e; ++i)
287    dbgs() << Queue[i]->NodeNum << " ";
288  dbgs() << "\n";
289}
290#endif
291
292//===----------------------------------------------------------------------===//
293// ScheduleDAGMI - Base class for MachineInstr scheduling with LiveIntervals
294// preservation.
295//===----------------------------------------------------------------------===//
296
297/// ReleaseSucc - Decrement the NumPredsLeft count of a successor. When
298/// NumPredsLeft reaches zero, release the successor node.
299///
300/// FIXME: Adjust SuccSU height based on MinLatency.
301void ScheduleDAGMI::releaseSucc(SUnit *SU, SDep *SuccEdge) {
302  SUnit *SuccSU = SuccEdge->getSUnit();
303
304#ifndef NDEBUG
305  if (SuccSU->NumPredsLeft == 0) {
306    dbgs() << "*** Scheduling failed! ***\n";
307    SuccSU->dump(this);
308    dbgs() << " has been released too many times!\n";
309    llvm_unreachable(0);
310  }
311#endif
312  --SuccSU->NumPredsLeft;
313  if (SuccSU->NumPredsLeft == 0 && SuccSU != &ExitSU)
314    SchedImpl->releaseTopNode(SuccSU);
315}
316
317/// releaseSuccessors - Call releaseSucc on each of SU's successors.
318void ScheduleDAGMI::releaseSuccessors(SUnit *SU) {
319  for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
320       I != E; ++I) {
321    releaseSucc(SU, &*I);
322  }
323}
324
325/// ReleasePred - Decrement the NumSuccsLeft count of a predecessor. When
326/// NumSuccsLeft reaches zero, release the predecessor node.
327///
328/// FIXME: Adjust PredSU height based on MinLatency.
329void ScheduleDAGMI::releasePred(SUnit *SU, SDep *PredEdge) {
330  SUnit *PredSU = PredEdge->getSUnit();
331
332#ifndef NDEBUG
333  if (PredSU->NumSuccsLeft == 0) {
334    dbgs() << "*** Scheduling failed! ***\n";
335    PredSU->dump(this);
336    dbgs() << " has been released too many times!\n";
337    llvm_unreachable(0);
338  }
339#endif
340  --PredSU->NumSuccsLeft;
341  if (PredSU->NumSuccsLeft == 0 && PredSU != &EntrySU)
342    SchedImpl->releaseBottomNode(PredSU);
343}
344
345/// releasePredecessors - Call releasePred on each of SU's predecessors.
346void ScheduleDAGMI::releasePredecessors(SUnit *SU) {
347  for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
348       I != E; ++I) {
349    releasePred(SU, &*I);
350  }
351}
352
353void ScheduleDAGMI::moveInstruction(MachineInstr *MI,
354                                    MachineBasicBlock::iterator InsertPos) {
355  // Advance RegionBegin if the first instruction moves down.
356  if (&*RegionBegin == MI)
357    ++RegionBegin;
358
359  // Update the instruction stream.
360  BB->splice(InsertPos, BB, MI);
361
362  // Update LiveIntervals
363  LIS->handleMove(MI);
364
365  // Recede RegionBegin if an instruction moves above the first.
366  if (RegionBegin == InsertPos)
367    RegionBegin = MI;
368}
369
370bool ScheduleDAGMI::checkSchedLimit() {
371#ifndef NDEBUG
372  if (NumInstrsScheduled == MISchedCutoff && MISchedCutoff != ~0U) {
373    CurrentTop = CurrentBottom;
374    return false;
375  }
376  ++NumInstrsScheduled;
377#endif
378  return true;
379}
380
381/// enterRegion - Called back from MachineScheduler::runOnMachineFunction after
382/// crossing a scheduling boundary. [begin, end) includes all instructions in
383/// the region, including the boundary itself and single-instruction regions
384/// that don't get scheduled.
385void ScheduleDAGMI::enterRegion(MachineBasicBlock *bb,
386                                MachineBasicBlock::iterator begin,
387                                MachineBasicBlock::iterator end,
388                                unsigned endcount)
389{
390  ScheduleDAGInstrs::enterRegion(bb, begin, end, endcount);
391
392  // For convenience remember the end of the liveness region.
393  LiveRegionEnd =
394    (RegionEnd == bb->end()) ? RegionEnd : llvm::next(RegionEnd);
395}
396
397// Setup the register pressure trackers for the top scheduled top and bottom
398// scheduled regions.
399void ScheduleDAGMI::initRegPressure() {
400  TopRPTracker.init(&MF, RegClassInfo, LIS, BB, RegionBegin);
401  BotRPTracker.init(&MF, RegClassInfo, LIS, BB, LiveRegionEnd);
402
403  // Close the RPTracker to finalize live ins.
404  RPTracker.closeRegion();
405
406  DEBUG(RPTracker.getPressure().dump(TRI));
407
408  // Initialize the live ins and live outs.
409  TopRPTracker.addLiveRegs(RPTracker.getPressure().LiveInRegs);
410  BotRPTracker.addLiveRegs(RPTracker.getPressure().LiveOutRegs);
411
412  // Close one end of the tracker so we can call
413  // getMaxUpward/DownwardPressureDelta before advancing across any
414  // instructions. This converts currently live regs into live ins/outs.
415  TopRPTracker.closeTop();
416  BotRPTracker.closeBottom();
417
418  // Account for liveness generated by the region boundary.
419  if (LiveRegionEnd != RegionEnd)
420    BotRPTracker.recede();
421
422  assert(BotRPTracker.getPos() == RegionEnd && "Can't find the region bottom");
423
424  // Cache the list of excess pressure sets in this region. This will also track
425  // the max pressure in the scheduled code for these sets.
426  RegionCriticalPSets.clear();
427  std::vector<unsigned> RegionPressure = RPTracker.getPressure().MaxSetPressure;
428  for (unsigned i = 0, e = RegionPressure.size(); i < e; ++i) {
429    unsigned Limit = TRI->getRegPressureSetLimit(i);
430    DEBUG(dbgs() << TRI->getRegPressureSetName(i)
431          << "Limit " << Limit
432          << " Actual " << RegionPressure[i] << "\n");
433    if (RegionPressure[i] > Limit)
434      RegionCriticalPSets.push_back(PressureElement(i, 0));
435  }
436  DEBUG(dbgs() << "Excess PSets: ";
437        for (unsigned i = 0, e = RegionCriticalPSets.size(); i != e; ++i)
438          dbgs() << TRI->getRegPressureSetName(
439            RegionCriticalPSets[i].PSetID) << " ";
440        dbgs() << "\n");
441}
442
443// FIXME: When the pressure tracker deals in pressure differences then we won't
444// iterate over all RegionCriticalPSets[i].
445void ScheduleDAGMI::
446updateScheduledPressure(std::vector<unsigned> NewMaxPressure) {
447  for (unsigned i = 0, e = RegionCriticalPSets.size(); i < e; ++i) {
448    unsigned ID = RegionCriticalPSets[i].PSetID;
449    int &MaxUnits = RegionCriticalPSets[i].UnitIncrease;
450    if ((int)NewMaxPressure[ID] > MaxUnits)
451      MaxUnits = NewMaxPressure[ID];
452  }
453}
454
455/// schedule - Called back from MachineScheduler::runOnMachineFunction
456/// after setting up the current scheduling region. [RegionBegin, RegionEnd)
457/// only includes instructions that have DAG nodes, not scheduling boundaries.
458///
459/// This is a skeletal driver, with all the functionality pushed into helpers,
460/// so that it can be easilly extended by experimental schedulers. Generally,
461/// implementing MachineSchedStrategy should be sufficient to implement a new
462/// scheduling algorithm. However, if a scheduler further subclasses
463/// ScheduleDAGMI then it will want to override this virtual method in order to
464/// update any specialized state.
465void ScheduleDAGMI::schedule() {
466  buildDAGWithRegPressure();
467
468  postprocessDAG();
469
470  DEBUG(for (unsigned su = 0, e = SUnits.size(); su != e; ++su)
471          SUnits[su].dumpAll(this));
472
473  if (ViewMISchedDAGs) viewGraph();
474
475  initQueues();
476
477  bool IsTopNode = false;
478  while (SUnit *SU = SchedImpl->pickNode(IsTopNode)) {
479    assert(!SU->isScheduled && "Node already scheduled");
480    if (!checkSchedLimit())
481      break;
482
483    scheduleMI(SU, IsTopNode);
484
485    updateQueues(SU, IsTopNode);
486  }
487  assert(CurrentTop == CurrentBottom && "Nonempty unscheduled zone.");
488
489  placeDebugValues();
490}
491
492/// Build the DAG and setup three register pressure trackers.
493void ScheduleDAGMI::buildDAGWithRegPressure() {
494  // Initialize the register pressure tracker used by buildSchedGraph.
495  RPTracker.init(&MF, RegClassInfo, LIS, BB, LiveRegionEnd);
496
497  // Account for liveness generate by the region boundary.
498  if (LiveRegionEnd != RegionEnd)
499    RPTracker.recede();
500
501  // Build the DAG, and compute current register pressure.
502  buildSchedGraph(AA, &RPTracker);
503  if (ViewMISchedDAGs) viewGraph();
504
505  // Initialize top/bottom trackers after computing region pressure.
506  initRegPressure();
507}
508
509/// Apply each ScheduleDAGMutation step in order.
510void ScheduleDAGMI::postprocessDAG() {
511  for (unsigned i = 0, e = Mutations.size(); i < e; ++i) {
512    Mutations[i]->apply(this);
513  }
514}
515
516// Release all DAG roots for scheduling.
517void ScheduleDAGMI::releaseRoots() {
518  SmallVector<SUnit*, 16> BotRoots;
519
520  for (std::vector<SUnit>::iterator
521         I = SUnits.begin(), E = SUnits.end(); I != E; ++I) {
522    // A SUnit is ready to top schedule if it has no predecessors.
523    if (I->Preds.empty())
524      SchedImpl->releaseTopNode(&(*I));
525    // A SUnit is ready to bottom schedule if it has no successors.
526    if (I->Succs.empty())
527      BotRoots.push_back(&(*I));
528  }
529  // Release bottom roots in reverse order so the higher priority nodes appear
530  // first. This is more natural and slightly more efficient.
531  for (SmallVectorImpl<SUnit*>::const_reverse_iterator
532         I = BotRoots.rbegin(), E = BotRoots.rend(); I != E; ++I)
533    SchedImpl->releaseBottomNode(*I);
534}
535
536/// Identify DAG roots and setup scheduler queues.
537void ScheduleDAGMI::initQueues() {
538
539  // Initialize the strategy before modifying the DAG.
540  SchedImpl->initialize(this);
541
542  // Release edges from the special Entry node or to the special Exit node.
543  releaseSuccessors(&EntrySU);
544  releasePredecessors(&ExitSU);
545
546  // Release all DAG roots for scheduling.
547  releaseRoots();
548
549  SchedImpl->registerRoots();
550
551  CurrentTop = nextIfDebug(RegionBegin, RegionEnd);
552  CurrentBottom = RegionEnd;
553}
554
555/// Move an instruction and update register pressure.
556void ScheduleDAGMI::scheduleMI(SUnit *SU, bool IsTopNode) {
557  // Move the instruction to its new location in the instruction stream.
558  MachineInstr *MI = SU->getInstr();
559
560  if (IsTopNode) {
561    assert(SU->isTopReady() && "node still has unscheduled dependencies");
562    if (&*CurrentTop == MI)
563      CurrentTop = nextIfDebug(++CurrentTop, CurrentBottom);
564    else {
565      moveInstruction(MI, CurrentTop);
566      TopRPTracker.setPos(MI);
567    }
568
569    // Update top scheduled pressure.
570    TopRPTracker.advance();
571    assert(TopRPTracker.getPos() == CurrentTop && "out of sync");
572    updateScheduledPressure(TopRPTracker.getPressure().MaxSetPressure);
573  }
574  else {
575    assert(SU->isBottomReady() && "node still has unscheduled dependencies");
576    MachineBasicBlock::iterator priorII =
577      priorNonDebug(CurrentBottom, CurrentTop);
578    if (&*priorII == MI)
579      CurrentBottom = priorII;
580    else {
581      if (&*CurrentTop == MI) {
582        CurrentTop = nextIfDebug(++CurrentTop, priorII);
583        TopRPTracker.setPos(CurrentTop);
584      }
585      moveInstruction(MI, CurrentBottom);
586      CurrentBottom = MI;
587    }
588    // Update bottom scheduled pressure.
589    BotRPTracker.recede();
590    assert(BotRPTracker.getPos() == CurrentBottom && "out of sync");
591    updateScheduledPressure(BotRPTracker.getPressure().MaxSetPressure);
592  }
593}
594
595/// Update scheduler queues after scheduling an instruction.
596void ScheduleDAGMI::updateQueues(SUnit *SU, bool IsTopNode) {
597  // Release dependent instructions for scheduling.
598  if (IsTopNode)
599    releaseSuccessors(SU);
600  else
601    releasePredecessors(SU);
602
603  SU->isScheduled = true;
604
605  // Notify the scheduling strategy after updating the DAG.
606  SchedImpl->schedNode(SU, IsTopNode);
607}
608
609/// Reinsert any remaining debug_values, just like the PostRA scheduler.
610void ScheduleDAGMI::placeDebugValues() {
611  // If first instruction was a DBG_VALUE then put it back.
612  if (FirstDbgValue) {
613    BB->splice(RegionBegin, BB, FirstDbgValue);
614    RegionBegin = FirstDbgValue;
615  }
616
617  for (std::vector<std::pair<MachineInstr *, MachineInstr *> >::iterator
618         DI = DbgValues.end(), DE = DbgValues.begin(); DI != DE; --DI) {
619    std::pair<MachineInstr *, MachineInstr *> P = *prior(DI);
620    MachineInstr *DbgValue = P.first;
621    MachineBasicBlock::iterator OrigPrevMI = P.second;
622    BB->splice(++OrigPrevMI, BB, DbgValue);
623    if (OrigPrevMI == llvm::prior(RegionEnd))
624      RegionEnd = DbgValue;
625  }
626  DbgValues.clear();
627  FirstDbgValue = NULL;
628}
629
630//===----------------------------------------------------------------------===//
631// ConvergingScheduler - Implementation of the standard MachineSchedStrategy.
632//===----------------------------------------------------------------------===//
633
634namespace {
635/// ConvergingScheduler shrinks the unscheduled zone using heuristics to balance
636/// the schedule.
637class ConvergingScheduler : public MachineSchedStrategy {
638
639  /// Store the state used by ConvergingScheduler heuristics, required for the
640  /// lifetime of one invocation of pickNode().
641  struct SchedCandidate {
642    // The best SUnit candidate.
643    SUnit *SU;
644
645    // Register pressure values for the best candidate.
646    RegPressureDelta RPDelta;
647
648    SchedCandidate(): SU(NULL) {}
649  };
650  /// Represent the type of SchedCandidate found within a single queue.
651  enum CandResult {
652    NoCand, NodeOrder, SingleExcess, SingleCritical, SingleMax, MultiPressure };
653
654  /// Each Scheduling boundary is associated with ready queues. It tracks the
655  /// current cycle in whichever direction at has moved, and maintains the state
656  /// of "hazards" and other interlocks at the current cycle.
657  struct SchedBoundary {
658    ScheduleDAGMI *DAG;
659    const TargetSchedModel *SchedModel;
660
661    ReadyQueue Available;
662    ReadyQueue Pending;
663    bool CheckPending;
664
665    ScheduleHazardRecognizer *HazardRec;
666
667    unsigned CurrCycle;
668    unsigned IssueCount;
669
670    /// MinReadyCycle - Cycle of the soonest available instruction.
671    unsigned MinReadyCycle;
672
673    // Remember the greatest min operand latency.
674    unsigned MaxMinLatency;
675
676    /// Pending queues extend the ready queues with the same ID and the
677    /// PendingFlag set.
678    SchedBoundary(unsigned ID, const Twine &Name):
679      DAG(0), SchedModel(0), Available(ID, Name+".A"),
680      Pending(ID << ConvergingScheduler::LogMaxQID, Name+".P"),
681      CheckPending(false), HazardRec(0), CurrCycle(0), IssueCount(0),
682      MinReadyCycle(UINT_MAX), MaxMinLatency(0) {}
683
684    ~SchedBoundary() { delete HazardRec; }
685
686    void init(ScheduleDAGMI *dag, const TargetSchedModel *smodel) {
687      DAG = dag;
688      SchedModel = smodel;
689    }
690
691    bool isTop() const {
692      return Available.getID() == ConvergingScheduler::TopQID;
693    }
694
695    bool checkHazard(SUnit *SU);
696
697    void releaseNode(SUnit *SU, unsigned ReadyCycle);
698
699    void bumpCycle();
700
701    void bumpNode(SUnit *SU);
702
703    void releasePending();
704
705    void removeReady(SUnit *SU);
706
707    SUnit *pickOnlyChoice();
708  };
709
710  ScheduleDAGMI *DAG;
711  const TargetSchedModel *SchedModel;
712  const TargetRegisterInfo *TRI;
713
714  // State of the top and bottom scheduled instruction boundaries.
715  SchedBoundary Top;
716  SchedBoundary Bot;
717
718public:
719  /// SUnit::NodeQueueId: 0 (none), 1 (top), 2 (bot), 3 (both)
720  enum {
721    TopQID = 1,
722    BotQID = 2,
723    LogMaxQID = 2
724  };
725
726  ConvergingScheduler():
727    DAG(0), SchedModel(0), TRI(0), Top(TopQID, "TopQ"), Bot(BotQID, "BotQ") {}
728
729  virtual void initialize(ScheduleDAGMI *dag);
730
731  virtual SUnit *pickNode(bool &IsTopNode);
732
733  virtual void schedNode(SUnit *SU, bool IsTopNode);
734
735  virtual void releaseTopNode(SUnit *SU);
736
737  virtual void releaseBottomNode(SUnit *SU);
738
739protected:
740  SUnit *pickNodeBidrectional(bool &IsTopNode);
741
742  CandResult pickNodeFromQueue(ReadyQueue &Q,
743                               const RegPressureTracker &RPTracker,
744                               SchedCandidate &Candidate);
745#ifndef NDEBUG
746  void traceCandidate(const char *Label, const ReadyQueue &Q, SUnit *SU,
747                      PressureElement P = PressureElement());
748#endif
749};
750} // namespace
751
752void ConvergingScheduler::initialize(ScheduleDAGMI *dag) {
753  DAG = dag;
754  SchedModel = DAG->getSchedModel();
755  TRI = DAG->TRI;
756  Top.init(DAG, SchedModel);
757  Bot.init(DAG, SchedModel);
758
759  // Initialize the HazardRecognizers. If itineraries don't exist, are empty, or
760  // are disabled, then these HazardRecs will be disabled.
761  const InstrItineraryData *Itin = SchedModel->getInstrItineraries();
762  const TargetMachine &TM = DAG->MF.getTarget();
763  Top.HazardRec = TM.getInstrInfo()->CreateTargetMIHazardRecognizer(Itin, DAG);
764  Bot.HazardRec = TM.getInstrInfo()->CreateTargetMIHazardRecognizer(Itin, DAG);
765
766  assert((!ForceTopDown || !ForceBottomUp) &&
767         "-misched-topdown incompatible with -misched-bottomup");
768}
769
770void ConvergingScheduler::releaseTopNode(SUnit *SU) {
771  if (SU->isScheduled)
772    return;
773
774  for (SUnit::succ_iterator I = SU->Preds.begin(), E = SU->Preds.end();
775       I != E; ++I) {
776    unsigned PredReadyCycle = I->getSUnit()->TopReadyCycle;
777    unsigned MinLatency = I->getMinLatency();
778#ifndef NDEBUG
779    Top.MaxMinLatency = std::max(MinLatency, Top.MaxMinLatency);
780#endif
781    if (SU->TopReadyCycle < PredReadyCycle + MinLatency)
782      SU->TopReadyCycle = PredReadyCycle + MinLatency;
783  }
784  Top.releaseNode(SU, SU->TopReadyCycle);
785}
786
787void ConvergingScheduler::releaseBottomNode(SUnit *SU) {
788  if (SU->isScheduled)
789    return;
790
791  assert(SU->getInstr() && "Scheduled SUnit must have instr");
792
793  for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
794       I != E; ++I) {
795    unsigned SuccReadyCycle = I->getSUnit()->BotReadyCycle;
796    unsigned MinLatency = I->getMinLatency();
797#ifndef NDEBUG
798    Bot.MaxMinLatency = std::max(MinLatency, Bot.MaxMinLatency);
799#endif
800    if (SU->BotReadyCycle < SuccReadyCycle + MinLatency)
801      SU->BotReadyCycle = SuccReadyCycle + MinLatency;
802  }
803  Bot.releaseNode(SU, SU->BotReadyCycle);
804}
805
806/// Does this SU have a hazard within the current instruction group.
807///
808/// The scheduler supports two modes of hazard recognition. The first is the
809/// ScheduleHazardRecognizer API. It is a fully general hazard recognizer that
810/// supports highly complicated in-order reservation tables
811/// (ScoreboardHazardRecognizer) and arbitraty target-specific logic.
812///
813/// The second is a streamlined mechanism that checks for hazards based on
814/// simple counters that the scheduler itself maintains. It explicitly checks
815/// for instruction dispatch limitations, including the number of micro-ops that
816/// can dispatch per cycle.
817///
818/// TODO: Also check whether the SU must start a new group.
819bool ConvergingScheduler::SchedBoundary::checkHazard(SUnit *SU) {
820  if (HazardRec->isEnabled())
821    return HazardRec->getHazardType(SU) != ScheduleHazardRecognizer::NoHazard;
822
823  unsigned uops = SchedModel->getNumMicroOps(SU->getInstr());
824  if (IssueCount + uops > SchedModel->getIssueWidth())
825    return true;
826
827  return false;
828}
829
830void ConvergingScheduler::SchedBoundary::releaseNode(SUnit *SU,
831                                                     unsigned ReadyCycle) {
832  if (ReadyCycle < MinReadyCycle)
833    MinReadyCycle = ReadyCycle;
834
835  // Check for interlocks first. For the purpose of other heuristics, an
836  // instruction that cannot issue appears as if it's not in the ReadyQueue.
837  if (ReadyCycle > CurrCycle || checkHazard(SU))
838    Pending.push(SU);
839  else
840    Available.push(SU);
841}
842
843/// Move the boundary of scheduled code by one cycle.
844void ConvergingScheduler::SchedBoundary::bumpCycle() {
845  unsigned Width = SchedModel->getIssueWidth();
846  IssueCount = (IssueCount <= Width) ? 0 : IssueCount - Width;
847
848  assert(MinReadyCycle < UINT_MAX && "MinReadyCycle uninitialized");
849  unsigned NextCycle = std::max(CurrCycle + 1, MinReadyCycle);
850
851  if (!HazardRec->isEnabled()) {
852    // Bypass HazardRec virtual calls.
853    CurrCycle = NextCycle;
854  }
855  else {
856    // Bypass getHazardType calls in case of long latency.
857    for (; CurrCycle != NextCycle; ++CurrCycle) {
858      if (isTop())
859        HazardRec->AdvanceCycle();
860      else
861        HazardRec->RecedeCycle();
862    }
863  }
864  CheckPending = true;
865
866  DEBUG(dbgs() << "*** " << Available.getName() << " cycle "
867        << CurrCycle << '\n');
868}
869
870/// Move the boundary of scheduled code by one SUnit.
871void ConvergingScheduler::SchedBoundary::bumpNode(SUnit *SU) {
872  // Update the reservation table.
873  if (HazardRec->isEnabled()) {
874    if (!isTop() && SU->isCall) {
875      // Calls are scheduled with their preceding instructions. For bottom-up
876      // scheduling, clear the pipeline state before emitting.
877      HazardRec->Reset();
878    }
879    HazardRec->EmitInstruction(SU);
880  }
881  // Check the instruction group dispatch limit.
882  // TODO: Check if this SU must end a dispatch group.
883  IssueCount += SchedModel->getNumMicroOps(SU->getInstr());
884  if (IssueCount >= SchedModel->getIssueWidth()) {
885    DEBUG(dbgs() << "*** Max instrs at cycle " << CurrCycle << '\n');
886    bumpCycle();
887  }
888}
889
890/// Release pending ready nodes in to the available queue. This makes them
891/// visible to heuristics.
892void ConvergingScheduler::SchedBoundary::releasePending() {
893  // If the available queue is empty, it is safe to reset MinReadyCycle.
894  if (Available.empty())
895    MinReadyCycle = UINT_MAX;
896
897  // Check to see if any of the pending instructions are ready to issue.  If
898  // so, add them to the available queue.
899  for (unsigned i = 0, e = Pending.size(); i != e; ++i) {
900    SUnit *SU = *(Pending.begin()+i);
901    unsigned ReadyCycle = isTop() ? SU->TopReadyCycle : SU->BotReadyCycle;
902
903    if (ReadyCycle < MinReadyCycle)
904      MinReadyCycle = ReadyCycle;
905
906    if (ReadyCycle > CurrCycle)
907      continue;
908
909    if (checkHazard(SU))
910      continue;
911
912    Available.push(SU);
913    Pending.remove(Pending.begin()+i);
914    --i; --e;
915  }
916  CheckPending = false;
917}
918
919/// Remove SU from the ready set for this boundary.
920void ConvergingScheduler::SchedBoundary::removeReady(SUnit *SU) {
921  if (Available.isInQueue(SU))
922    Available.remove(Available.find(SU));
923  else {
924    assert(Pending.isInQueue(SU) && "bad ready count");
925    Pending.remove(Pending.find(SU));
926  }
927}
928
929/// If this queue only has one ready candidate, return it. As a side effect,
930/// advance the cycle until at least one node is ready. If multiple instructions
931/// are ready, return NULL.
932SUnit *ConvergingScheduler::SchedBoundary::pickOnlyChoice() {
933  if (CheckPending)
934    releasePending();
935
936  for (unsigned i = 0; Available.empty(); ++i) {
937    assert(i <= (HazardRec->getMaxLookAhead() + MaxMinLatency) &&
938           "permanent hazard"); (void)i;
939    bumpCycle();
940    releasePending();
941  }
942  if (Available.size() == 1)
943    return *Available.begin();
944  return NULL;
945}
946
947#ifndef NDEBUG
948void ConvergingScheduler::traceCandidate(const char *Label, const ReadyQueue &Q,
949                                         SUnit *SU, PressureElement P) {
950  dbgs() << Label << " " << Q.getName() << " ";
951  if (P.isValid())
952    dbgs() << TRI->getRegPressureSetName(P.PSetID) << ":" << P.UnitIncrease
953           << " ";
954  else
955    dbgs() << "     ";
956  SU->dump(DAG);
957}
958#endif
959
960/// pickNodeFromQueue helper that returns true if the LHS reg pressure effect is
961/// more desirable than RHS from scheduling standpoint.
962static bool compareRPDelta(const RegPressureDelta &LHS,
963                           const RegPressureDelta &RHS) {
964  // Compare each component of pressure in decreasing order of importance
965  // without checking if any are valid. Invalid PressureElements are assumed to
966  // have UnitIncrease==0, so are neutral.
967
968  // Avoid increasing the max critical pressure in the scheduled region.
969  if (LHS.Excess.UnitIncrease != RHS.Excess.UnitIncrease)
970    return LHS.Excess.UnitIncrease < RHS.Excess.UnitIncrease;
971
972  // Avoid increasing the max critical pressure in the scheduled region.
973  if (LHS.CriticalMax.UnitIncrease != RHS.CriticalMax.UnitIncrease)
974    return LHS.CriticalMax.UnitIncrease < RHS.CriticalMax.UnitIncrease;
975
976  // Avoid increasing the max pressure of the entire region.
977  if (LHS.CurrentMax.UnitIncrease != RHS.CurrentMax.UnitIncrease)
978    return LHS.CurrentMax.UnitIncrease < RHS.CurrentMax.UnitIncrease;
979
980  return false;
981}
982
983/// Pick the best candidate from the top queue.
984///
985/// TODO: getMaxPressureDelta results can be mostly cached for each SUnit during
986/// DAG building. To adjust for the current scheduling location we need to
987/// maintain the number of vreg uses remaining to be top-scheduled.
988ConvergingScheduler::CandResult ConvergingScheduler::
989pickNodeFromQueue(ReadyQueue &Q, const RegPressureTracker &RPTracker,
990                  SchedCandidate &Candidate) {
991  DEBUG(Q.dump());
992
993  // getMaxPressureDelta temporarily modifies the tracker.
994  RegPressureTracker &TempTracker = const_cast<RegPressureTracker&>(RPTracker);
995
996  // BestSU remains NULL if no top candidates beat the best existing candidate.
997  CandResult FoundCandidate = NoCand;
998  for (ReadyQueue::iterator I = Q.begin(), E = Q.end(); I != E; ++I) {
999    RegPressureDelta RPDelta;
1000    TempTracker.getMaxPressureDelta((*I)->getInstr(), RPDelta,
1001                                    DAG->getRegionCriticalPSets(),
1002                                    DAG->getRegPressure().MaxSetPressure);
1003
1004    // Initialize the candidate if needed.
1005    if (!Candidate.SU) {
1006      Candidate.SU = *I;
1007      Candidate.RPDelta = RPDelta;
1008      FoundCandidate = NodeOrder;
1009      continue;
1010    }
1011    // Avoid exceeding the target's limit.
1012    if (RPDelta.Excess.UnitIncrease < Candidate.RPDelta.Excess.UnitIncrease) {
1013      DEBUG(traceCandidate("ECAND", Q, *I, RPDelta.Excess));
1014      Candidate.SU = *I;
1015      Candidate.RPDelta = RPDelta;
1016      FoundCandidate = SingleExcess;
1017      continue;
1018    }
1019    if (RPDelta.Excess.UnitIncrease > Candidate.RPDelta.Excess.UnitIncrease)
1020      continue;
1021    if (FoundCandidate == SingleExcess)
1022      FoundCandidate = MultiPressure;
1023
1024    // Avoid increasing the max critical pressure in the scheduled region.
1025    if (RPDelta.CriticalMax.UnitIncrease
1026        < Candidate.RPDelta.CriticalMax.UnitIncrease) {
1027      DEBUG(traceCandidate("PCAND", Q, *I, RPDelta.CriticalMax));
1028      Candidate.SU = *I;
1029      Candidate.RPDelta = RPDelta;
1030      FoundCandidate = SingleCritical;
1031      continue;
1032    }
1033    if (RPDelta.CriticalMax.UnitIncrease
1034        > Candidate.RPDelta.CriticalMax.UnitIncrease)
1035      continue;
1036    if (FoundCandidate == SingleCritical)
1037      FoundCandidate = MultiPressure;
1038
1039    // Avoid increasing the max pressure of the entire region.
1040    if (RPDelta.CurrentMax.UnitIncrease
1041        < Candidate.RPDelta.CurrentMax.UnitIncrease) {
1042      DEBUG(traceCandidate("MCAND", Q, *I, RPDelta.CurrentMax));
1043      Candidate.SU = *I;
1044      Candidate.RPDelta = RPDelta;
1045      FoundCandidate = SingleMax;
1046      continue;
1047    }
1048    if (RPDelta.CurrentMax.UnitIncrease
1049        > Candidate.RPDelta.CurrentMax.UnitIncrease)
1050      continue;
1051    if (FoundCandidate == SingleMax)
1052      FoundCandidate = MultiPressure;
1053
1054    // Fall through to original instruction order.
1055    // Only consider node order if Candidate was chosen from this Q.
1056    if (FoundCandidate == NoCand)
1057      continue;
1058
1059    if ((Q.getID() == TopQID && (*I)->NodeNum < Candidate.SU->NodeNum)
1060        || (Q.getID() == BotQID && (*I)->NodeNum > Candidate.SU->NodeNum)) {
1061      DEBUG(traceCandidate("NCAND", Q, *I));
1062      Candidate.SU = *I;
1063      Candidate.RPDelta = RPDelta;
1064      FoundCandidate = NodeOrder;
1065    }
1066  }
1067  return FoundCandidate;
1068}
1069
1070/// Pick the best candidate node from either the top or bottom queue.
1071SUnit *ConvergingScheduler::pickNodeBidrectional(bool &IsTopNode) {
1072  // Schedule as far as possible in the direction of no choice. This is most
1073  // efficient, but also provides the best heuristics for CriticalPSets.
1074  if (SUnit *SU = Bot.pickOnlyChoice()) {
1075    IsTopNode = false;
1076    return SU;
1077  }
1078  if (SUnit *SU = Top.pickOnlyChoice()) {
1079    IsTopNode = true;
1080    return SU;
1081  }
1082  SchedCandidate BotCand;
1083  // Prefer bottom scheduling when heuristics are silent.
1084  CandResult BotResult = pickNodeFromQueue(Bot.Available,
1085                                           DAG->getBotRPTracker(), BotCand);
1086  assert(BotResult != NoCand && "failed to find the first candidate");
1087
1088  // If either Q has a single candidate that provides the least increase in
1089  // Excess pressure, we can immediately schedule from that Q.
1090  //
1091  // RegionCriticalPSets summarizes the pressure within the scheduled region and
1092  // affects picking from either Q. If scheduling in one direction must
1093  // increase pressure for one of the excess PSets, then schedule in that
1094  // direction first to provide more freedom in the other direction.
1095  if (BotResult == SingleExcess || BotResult == SingleCritical) {
1096    IsTopNode = false;
1097    return BotCand.SU;
1098  }
1099  // Check if the top Q has a better candidate.
1100  SchedCandidate TopCand;
1101  CandResult TopResult = pickNodeFromQueue(Top.Available,
1102                                           DAG->getTopRPTracker(), TopCand);
1103  assert(TopResult != NoCand && "failed to find the first candidate");
1104
1105  if (TopResult == SingleExcess || TopResult == SingleCritical) {
1106    IsTopNode = true;
1107    return TopCand.SU;
1108  }
1109  // If either Q has a single candidate that minimizes pressure above the
1110  // original region's pressure pick it.
1111  if (BotResult == SingleMax) {
1112    IsTopNode = false;
1113    return BotCand.SU;
1114  }
1115  if (TopResult == SingleMax) {
1116    IsTopNode = true;
1117    return TopCand.SU;
1118  }
1119  // Check for a salient pressure difference and pick the best from either side.
1120  if (compareRPDelta(TopCand.RPDelta, BotCand.RPDelta)) {
1121    IsTopNode = true;
1122    return TopCand.SU;
1123  }
1124  // Otherwise prefer the bottom candidate in node order.
1125  IsTopNode = false;
1126  return BotCand.SU;
1127}
1128
1129/// Pick the best node to balance the schedule. Implements MachineSchedStrategy.
1130SUnit *ConvergingScheduler::pickNode(bool &IsTopNode) {
1131  if (DAG->top() == DAG->bottom()) {
1132    assert(Top.Available.empty() && Top.Pending.empty() &&
1133           Bot.Available.empty() && Bot.Pending.empty() && "ReadyQ garbage");
1134    return NULL;
1135  }
1136  SUnit *SU;
1137  do {
1138    if (ForceTopDown) {
1139      SU = Top.pickOnlyChoice();
1140      if (!SU) {
1141        SchedCandidate TopCand;
1142        CandResult TopResult =
1143          pickNodeFromQueue(Top.Available, DAG->getTopRPTracker(), TopCand);
1144        assert(TopResult != NoCand && "failed to find the first candidate");
1145        (void)TopResult;
1146        SU = TopCand.SU;
1147      }
1148      IsTopNode = true;
1149    }
1150    else if (ForceBottomUp) {
1151      SU = Bot.pickOnlyChoice();
1152      if (!SU) {
1153        SchedCandidate BotCand;
1154        CandResult BotResult =
1155          pickNodeFromQueue(Bot.Available, DAG->getBotRPTracker(), BotCand);
1156        assert(BotResult != NoCand && "failed to find the first candidate");
1157        (void)BotResult;
1158        SU = BotCand.SU;
1159      }
1160      IsTopNode = false;
1161    }
1162    else {
1163      SU = pickNodeBidrectional(IsTopNode);
1164    }
1165  } while (SU->isScheduled);
1166
1167  if (SU->isTopReady())
1168    Top.removeReady(SU);
1169  if (SU->isBottomReady())
1170    Bot.removeReady(SU);
1171
1172  DEBUG(dbgs() << "*** " << (IsTopNode ? "Top" : "Bottom")
1173        << " Scheduling Instruction in cycle "
1174        << (IsTopNode ? Top.CurrCycle : Bot.CurrCycle) << '\n';
1175        SU->dump(DAG));
1176  return SU;
1177}
1178
1179/// Update the scheduler's state after scheduling a node. This is the same node
1180/// that was just returned by pickNode(). However, ScheduleDAGMI needs to update
1181/// it's state based on the current cycle before MachineSchedStrategy does.
1182void ConvergingScheduler::schedNode(SUnit *SU, bool IsTopNode) {
1183  if (IsTopNode) {
1184    SU->TopReadyCycle = Top.CurrCycle;
1185    Top.bumpNode(SU);
1186  }
1187  else {
1188    SU->BotReadyCycle = Bot.CurrCycle;
1189    Bot.bumpNode(SU);
1190  }
1191}
1192
1193/// Create the standard converging machine scheduler. This will be used as the
1194/// default scheduler if the target does not set a default.
1195static ScheduleDAGInstrs *createConvergingSched(MachineSchedContext *C) {
1196  assert((!ForceTopDown || !ForceBottomUp) &&
1197         "-misched-topdown incompatible with -misched-bottomup");
1198  return new ScheduleDAGMI(C, new ConvergingScheduler());
1199}
1200static MachineSchedRegistry
1201ConvergingSchedRegistry("converge", "Standard converging scheduler.",
1202                        createConvergingSched);
1203
1204//===----------------------------------------------------------------------===//
1205// ILP Scheduler. Currently for experimental analysis of heuristics.
1206//===----------------------------------------------------------------------===//
1207
1208namespace {
1209/// \brief Order nodes by the ILP metric.
1210struct ILPOrder {
1211  ScheduleDAGILP *ILP;
1212  bool MaximizeILP;
1213
1214  ILPOrder(ScheduleDAGILP *ilp, bool MaxILP): ILP(ilp), MaximizeILP(MaxILP) {}
1215
1216  /// \brief Apply a less-than relation on node priority.
1217  bool operator()(const SUnit *A, const SUnit *B) const {
1218    // Return true if A comes after B in the Q.
1219    if (MaximizeILP)
1220      return ILP->getILP(A) < ILP->getILP(B);
1221    else
1222      return ILP->getILP(A) > ILP->getILP(B);
1223  }
1224};
1225
1226/// \brief Schedule based on the ILP metric.
1227class ILPScheduler : public MachineSchedStrategy {
1228  ScheduleDAGILP ILP;
1229  ILPOrder Cmp;
1230
1231  std::vector<SUnit*> ReadyQ;
1232public:
1233  ILPScheduler(bool MaximizeILP)
1234  : ILP(/*BottomUp=*/true), Cmp(&ILP, MaximizeILP) {}
1235
1236  virtual void initialize(ScheduleDAGMI *DAG) {
1237    ReadyQ.clear();
1238    ILP.resize(DAG->SUnits.size());
1239  }
1240
1241  virtual void registerRoots() {
1242    for (std::vector<SUnit*>::const_iterator
1243           I = ReadyQ.begin(), E = ReadyQ.end(); I != E; ++I) {
1244      ILP.computeILP(*I);
1245    }
1246  }
1247
1248  /// Implement MachineSchedStrategy interface.
1249  /// -----------------------------------------
1250
1251  virtual SUnit *pickNode(bool &IsTopNode) {
1252    if (ReadyQ.empty()) return NULL;
1253    pop_heap(ReadyQ.begin(), ReadyQ.end(), Cmp);
1254    SUnit *SU = ReadyQ.back();
1255    ReadyQ.pop_back();
1256    IsTopNode = false;
1257    DEBUG(dbgs() << "*** Scheduling " << *SU->getInstr()
1258          << " ILP: " << ILP.getILP(SU) << '\n');
1259    return SU;
1260  }
1261
1262  virtual void schedNode(SUnit *, bool) {}
1263
1264  virtual void releaseTopNode(SUnit *) { /*only called for top roots*/ }
1265
1266  virtual void releaseBottomNode(SUnit *SU) {
1267    ReadyQ.push_back(SU);
1268    std::push_heap(ReadyQ.begin(), ReadyQ.end(), Cmp);
1269  }
1270};
1271} // namespace
1272
1273static ScheduleDAGInstrs *createILPMaxScheduler(MachineSchedContext *C) {
1274  return new ScheduleDAGMI(C, new ILPScheduler(true));
1275}
1276static ScheduleDAGInstrs *createILPMinScheduler(MachineSchedContext *C) {
1277  return new ScheduleDAGMI(C, new ILPScheduler(false));
1278}
1279static MachineSchedRegistry ILPMaxRegistry(
1280  "ilpmax", "Schedule bottom-up for max ILP", createILPMaxScheduler);
1281static MachineSchedRegistry ILPMinRegistry(
1282  "ilpmin", "Schedule bottom-up for min ILP", createILPMinScheduler);
1283
1284//===----------------------------------------------------------------------===//
1285// Machine Instruction Shuffler for Correctness Testing
1286//===----------------------------------------------------------------------===//
1287
1288#ifndef NDEBUG
1289namespace {
1290/// Apply a less-than relation on the node order, which corresponds to the
1291/// instruction order prior to scheduling. IsReverse implements greater-than.
1292template<bool IsReverse>
1293struct SUnitOrder {
1294  bool operator()(SUnit *A, SUnit *B) const {
1295    if (IsReverse)
1296      return A->NodeNum > B->NodeNum;
1297    else
1298      return A->NodeNum < B->NodeNum;
1299  }
1300};
1301
1302/// Reorder instructions as much as possible.
1303class InstructionShuffler : public MachineSchedStrategy {
1304  bool IsAlternating;
1305  bool IsTopDown;
1306
1307  // Using a less-than relation (SUnitOrder<false>) for the TopQ priority
1308  // gives nodes with a higher number higher priority causing the latest
1309  // instructions to be scheduled first.
1310  PriorityQueue<SUnit*, std::vector<SUnit*>, SUnitOrder<false> >
1311    TopQ;
1312  // When scheduling bottom-up, use greater-than as the queue priority.
1313  PriorityQueue<SUnit*, std::vector<SUnit*>, SUnitOrder<true> >
1314    BottomQ;
1315public:
1316  InstructionShuffler(bool alternate, bool topdown)
1317    : IsAlternating(alternate), IsTopDown(topdown) {}
1318
1319  virtual void initialize(ScheduleDAGMI *) {
1320    TopQ.clear();
1321    BottomQ.clear();
1322  }
1323
1324  /// Implement MachineSchedStrategy interface.
1325  /// -----------------------------------------
1326
1327  virtual SUnit *pickNode(bool &IsTopNode) {
1328    SUnit *SU;
1329    if (IsTopDown) {
1330      do {
1331        if (TopQ.empty()) return NULL;
1332        SU = TopQ.top();
1333        TopQ.pop();
1334      } while (SU->isScheduled);
1335      IsTopNode = true;
1336    }
1337    else {
1338      do {
1339        if (BottomQ.empty()) return NULL;
1340        SU = BottomQ.top();
1341        BottomQ.pop();
1342      } while (SU->isScheduled);
1343      IsTopNode = false;
1344    }
1345    if (IsAlternating)
1346      IsTopDown = !IsTopDown;
1347    return SU;
1348  }
1349
1350  virtual void schedNode(SUnit *SU, bool IsTopNode) {}
1351
1352  virtual void releaseTopNode(SUnit *SU) {
1353    TopQ.push(SU);
1354  }
1355  virtual void releaseBottomNode(SUnit *SU) {
1356    BottomQ.push(SU);
1357  }
1358};
1359} // namespace
1360
1361static ScheduleDAGInstrs *createInstructionShuffler(MachineSchedContext *C) {
1362  bool Alternate = !ForceTopDown && !ForceBottomUp;
1363  bool TopDown = !ForceBottomUp;
1364  assert((TopDown || !ForceTopDown) &&
1365         "-misched-topdown incompatible with -misched-bottomup");
1366  return new ScheduleDAGMI(C, new InstructionShuffler(Alternate, TopDown));
1367}
1368static MachineSchedRegistry ShufflerRegistry(
1369  "shuffle", "Shuffle machine instructions alternating directions",
1370  createInstructionShuffler);
1371#endif // !NDEBUG
1372