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