MachineScheduler.cpp revision 28ebc89c413c042bf693d9ad6971f0fb5cca2f0f 
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 "RegisterClassInfo.h"
18#include "RegisterPressure.h"
19#include "llvm/CodeGen/LiveIntervalAnalysis.h"
20#include "llvm/CodeGen/MachineScheduler.h"
21#include "llvm/CodeGen/Passes.h"
22#include "llvm/CodeGen/ScheduleDAGInstrs.h"
23#include "llvm/Analysis/AliasAnalysis.h"
24#include "llvm/Target/TargetInstrInfo.h"
25#include "llvm/Support/CommandLine.h"
26#include "llvm/Support/Debug.h"
27#include "llvm/Support/ErrorHandling.h"
28#include "llvm/Support/raw_ostream.h"
29#include "llvm/ADT/OwningPtr.h"
30#include "llvm/ADT/PriorityQueue.h"
31
32#include <queue>
33
34using namespace llvm;
35
36static cl::opt<bool> ForceTopDown("misched-topdown", cl::Hidden,
37                                  cl::desc("Force top-down list scheduling"));
38static cl::opt<bool> ForceBottomUp("misched-bottomup", cl::Hidden,
39                                  cl::desc("Force bottom-up list scheduling"));
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  while(I != End) {
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  // Initialize the context of the pass.
177  MF = &mf;
178  MLI = &getAnalysis<MachineLoopInfo>();
179  MDT = &getAnalysis<MachineDominatorTree>();
180  PassConfig = &getAnalysis<TargetPassConfig>();
181  AA = &getAnalysis<AliasAnalysis>();
182
183  LIS = &getAnalysis<LiveIntervals>();
184  const TargetInstrInfo *TII = MF->getTarget().getInstrInfo();
185
186  RegClassInfo->runOnMachineFunction(*MF);
187
188  // Select the scheduler, or set the default.
189  MachineSchedRegistry::ScheduleDAGCtor Ctor = MachineSchedOpt;
190  if (Ctor == useDefaultMachineSched) {
191    // Get the default scheduler set by the target.
192    Ctor = MachineSchedRegistry::getDefault();
193    if (!Ctor) {
194      Ctor = createConvergingSched;
195      MachineSchedRegistry::setDefault(Ctor);
196    }
197  }
198  // Instantiate the selected scheduler.
199  OwningPtr<ScheduleDAGInstrs> Scheduler(Ctor(this));
200
201  // Visit all machine basic blocks.
202  //
203  // TODO: Visit blocks in global postorder or postorder within the bottom-up
204  // loop tree. Then we can optionally compute global RegPressure.
205  for (MachineFunction::iterator MBB = MF->begin(), MBBEnd = MF->end();
206       MBB != MBBEnd; ++MBB) {
207
208    Scheduler->startBlock(MBB);
209
210    // Break the block into scheduling regions [I, RegionEnd), and schedule each
211    // region as soon as it is discovered. RegionEnd points the the scheduling
212    // boundary at the bottom of the region. The DAG does not include RegionEnd,
213    // but the region does (i.e. the next RegionEnd is above the previous
214    // RegionBegin). If the current block has no terminator then RegionEnd ==
215    // MBB->end() for the bottom region.
216    //
217    // The Scheduler may insert instructions during either schedule() or
218    // exitRegion(), even for empty regions. So the local iterators 'I' and
219    // 'RegionEnd' are invalid across these calls.
220    unsigned RemainingCount = MBB->size();
221    for(MachineBasicBlock::iterator RegionEnd = MBB->end();
222        RegionEnd != MBB->begin(); RegionEnd = Scheduler->begin()) {
223
224      // Avoid decrementing RegionEnd for blocks with no terminator.
225      if (RegionEnd != MBB->end()
226          || TII->isSchedulingBoundary(llvm::prior(RegionEnd), MBB, *MF)) {
227        --RegionEnd;
228        // Count the boundary instruction.
229        --RemainingCount;
230      }
231
232      // The next region starts above the previous region. Look backward in the
233      // instruction stream until we find the nearest boundary.
234      MachineBasicBlock::iterator I = RegionEnd;
235      for(;I != MBB->begin(); --I, --RemainingCount) {
236        if (TII->isSchedulingBoundary(llvm::prior(I), MBB, *MF))
237          break;
238      }
239      // Notify the scheduler of the region, even if we may skip scheduling
240      // it. Perhaps it still needs to be bundled.
241      Scheduler->enterRegion(MBB, I, RegionEnd, RemainingCount);
242
243      // Skip empty scheduling regions (0 or 1 schedulable instructions).
244      if (I == RegionEnd || I == llvm::prior(RegionEnd)) {
245        // Close the current region. Bundle the terminator if needed.
246        // This invalidates 'RegionEnd' and 'I'.
247        Scheduler->exitRegion();
248        continue;
249      }
250      DEBUG(dbgs() << "MachineScheduling " << MF->getFunction()->getName()
251            << ":BB#" << MBB->getNumber() << "\n  From: " << *I << "    To: ";
252            if (RegionEnd != MBB->end()) dbgs() << *RegionEnd;
253            else dbgs() << "End";
254            dbgs() << " Remaining: " << RemainingCount << "\n");
255
256      // Schedule a region: possibly reorder instructions.
257      // This invalidates 'RegionEnd' and 'I'.
258      Scheduler->schedule();
259
260      // Close the current region.
261      Scheduler->exitRegion();
262
263      // Scheduling has invalidated the current iterator 'I'. Ask the
264      // scheduler for the top of it's scheduled region.
265      RegionEnd = Scheduler->begin();
266    }
267    assert(RemainingCount == 0 && "Instruction count mismatch!");
268    Scheduler->finishBlock();
269  }
270  Scheduler->finalizeSchedule();
271  DEBUG(LIS->print(dbgs()));
272  return true;
273}
274
275void MachineScheduler::print(raw_ostream &O, const Module* m) const {
276  // unimplemented
277}
278
279//===----------------------------------------------------------------------===//
280// MachineSchedStrategy - Interface to a machine scheduling algorithm.
281//===----------------------------------------------------------------------===//
282
283namespace {
284class ScheduleDAGMI;
285
286/// MachineSchedStrategy - Interface used by ScheduleDAGMI to drive the selected
287/// scheduling algorithm.
288///
289/// If this works well and targets wish to reuse ScheduleDAGMI, we may expose it
290/// in ScheduleDAGInstrs.h
291class MachineSchedStrategy {
292public:
293  virtual ~MachineSchedStrategy() {}
294
295  /// Initialize the strategy after building the DAG for a new region.
296  virtual void initialize(ScheduleDAGMI *DAG) = 0;
297
298  /// Pick the next node to schedule, or return NULL. Set IsTopNode to true to
299  /// schedule the node at the top of the unscheduled region. Otherwise it will
300  /// be scheduled at the bottom.
301  virtual SUnit *pickNode(bool &IsTopNode) = 0;
302
303  /// When all predecessor dependencies have been resolved, free this node for
304  /// top-down scheduling.
305  virtual void releaseTopNode(SUnit *SU) = 0;
306  /// When all successor dependencies have been resolved, free this node for
307  /// bottom-up scheduling.
308  virtual void releaseBottomNode(SUnit *SU) = 0;
309};
310} // namespace
311
312//===----------------------------------------------------------------------===//
313// ScheduleDAGMI - Base class for MachineInstr scheduling with LiveIntervals
314// preservation.
315//===----------------------------------------------------------------------===//
316
317namespace {
318/// ScheduleDAGMI is an implementation of ScheduleDAGInstrs that schedules
319/// machine instructions while updating LiveIntervals.
320class ScheduleDAGMI : public ScheduleDAGInstrs {
321  AliasAnalysis *AA;
322  RegisterClassInfo *RegClassInfo;
323  MachineSchedStrategy *SchedImpl;
324
325  MachineBasicBlock::iterator LiveRegionEnd;
326
327  // Register pressure in this region computed by buildSchedGraph.
328  IntervalPressure RegPressure;
329  RegPressureTracker RPTracker;
330
331  /// The top of the unscheduled zone.
332  MachineBasicBlock::iterator CurrentTop;
333  IntervalPressure TopPressure;
334  RegPressureTracker TopRPTracker;
335
336  /// The bottom of the unscheduled zone.
337  MachineBasicBlock::iterator CurrentBottom;
338  IntervalPressure BotPressure;
339  RegPressureTracker BotRPTracker;
340
341  /// The number of instructions scheduled so far. Used to cut off the
342  /// scheduler at the point determined by misched-cutoff.
343  unsigned NumInstrsScheduled;
344public:
345  ScheduleDAGMI(MachineSchedContext *C, MachineSchedStrategy *S):
346    ScheduleDAGInstrs(*C->MF, *C->MLI, *C->MDT, /*IsPostRA=*/false, C->LIS),
347    AA(C->AA), RegClassInfo(C->RegClassInfo), SchedImpl(S),
348    RPTracker(RegPressure), CurrentTop(), TopRPTracker(TopPressure),
349    CurrentBottom(), BotRPTracker(BotPressure), NumInstrsScheduled(0) {}
350
351  ~ScheduleDAGMI() {
352    delete SchedImpl;
353  }
354
355  MachineBasicBlock::iterator top() const { return CurrentTop; }
356  MachineBasicBlock::iterator bottom() const { return CurrentBottom; }
357
358  /// Implement the ScheduleDAGInstrs interface for handling the next scheduling
359  /// region. This covers all instructions in a block, while schedule() may only
360  /// cover a subset.
361  void enterRegion(MachineBasicBlock *bb,
362                   MachineBasicBlock::iterator begin,
363                   MachineBasicBlock::iterator end,
364                   unsigned endcount);
365
366  /// Implement ScheduleDAGInstrs interface for scheduling a sequence of
367  /// reorderable instructions.
368  void schedule();
369
370  /// Get current register pressure for the top scheduled instructions.
371  const IntervalPressure &getTopPressure() const { return TopPressure; }
372  const RegPressureTracker &getTopRPTracker() const { return TopRPTracker; }
373
374  /// Get current register pressure for the bottom scheduled instructions.
375  const IntervalPressure &getBotPressure() const { return BotPressure; }
376  const RegPressureTracker &getBotRPTracker() const { return BotRPTracker; }
377
378  /// Get register pressure for the entire scheduling region before scheduling.
379  const IntervalPressure &getRegPressure() const { return RegPressure; }
380
381protected:
382  void initRegPressure();
383
384  void moveInstruction(MachineInstr *MI, MachineBasicBlock::iterator InsertPos);
385  bool checkSchedLimit();
386
387  void releaseSucc(SUnit *SU, SDep *SuccEdge);
388  void releaseSuccessors(SUnit *SU);
389  void releasePred(SUnit *SU, SDep *PredEdge);
390  void releasePredecessors(SUnit *SU);
391
392  void placeDebugValues();
393};
394} // namespace
395
396/// ReleaseSucc - Decrement the NumPredsLeft count of a successor. When
397/// NumPredsLeft reaches zero, release the successor node.
398void ScheduleDAGMI::releaseSucc(SUnit *SU, SDep *SuccEdge) {
399  SUnit *SuccSU = SuccEdge->getSUnit();
400
401#ifndef NDEBUG
402  if (SuccSU->NumPredsLeft == 0) {
403    dbgs() << "*** Scheduling failed! ***\n";
404    SuccSU->dump(this);
405    dbgs() << " has been released too many times!\n";
406    llvm_unreachable(0);
407  }
408#endif
409  --SuccSU->NumPredsLeft;
410  if (SuccSU->NumPredsLeft == 0 && SuccSU != &ExitSU)
411    SchedImpl->releaseTopNode(SuccSU);
412}
413
414/// releaseSuccessors - Call releaseSucc on each of SU's successors.
415void ScheduleDAGMI::releaseSuccessors(SUnit *SU) {
416  for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
417       I != E; ++I) {
418    releaseSucc(SU, &*I);
419  }
420}
421
422/// ReleasePred - Decrement the NumSuccsLeft count of a predecessor. When
423/// NumSuccsLeft reaches zero, release the predecessor node.
424void ScheduleDAGMI::releasePred(SUnit *SU, SDep *PredEdge) {
425  SUnit *PredSU = PredEdge->getSUnit();
426
427#ifndef NDEBUG
428  if (PredSU->NumSuccsLeft == 0) {
429    dbgs() << "*** Scheduling failed! ***\n";
430    PredSU->dump(this);
431    dbgs() << " has been released too many times!\n";
432    llvm_unreachable(0);
433  }
434#endif
435  --PredSU->NumSuccsLeft;
436  if (PredSU->NumSuccsLeft == 0 && PredSU != &EntrySU)
437    SchedImpl->releaseBottomNode(PredSU);
438}
439
440/// releasePredecessors - Call releasePred on each of SU's predecessors.
441void ScheduleDAGMI::releasePredecessors(SUnit *SU) {
442  for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
443       I != E; ++I) {
444    releasePred(SU, &*I);
445  }
446}
447
448void ScheduleDAGMI::moveInstruction(MachineInstr *MI,
449                                    MachineBasicBlock::iterator InsertPos) {
450  // Fix RegionBegin if the first instruction moves down.
451  if (&*RegionBegin == MI)
452    RegionBegin = llvm::next(RegionBegin);
453  BB->splice(InsertPos, BB, MI);
454  LIS->handleMove(MI);
455  // Fix RegionBegin if another instruction moves above the first instruction.
456  if (RegionBegin == InsertPos)
457    RegionBegin = MI;
458  // Fix TopRPTracker if we move something above CurrentTop.
459  if (CurrentTop == InsertPos)
460    TopRPTracker.setPos(MI);
461}
462
463bool ScheduleDAGMI::checkSchedLimit() {
464#ifndef NDEBUG
465  if (NumInstrsScheduled == MISchedCutoff && MISchedCutoff != ~0U) {
466    CurrentTop = CurrentBottom;
467    return false;
468  }
469  ++NumInstrsScheduled;
470#endif
471  return true;
472}
473
474/// enterRegion - Called back from MachineScheduler::runOnMachineFunction after
475/// crossing a scheduling boundary. [begin, end) includes all instructions in
476/// the region, including the boundary itself and single-instruction regions
477/// that don't get scheduled.
478void ScheduleDAGMI::enterRegion(MachineBasicBlock *bb,
479                                MachineBasicBlock::iterator begin,
480                                MachineBasicBlock::iterator end,
481                                unsigned endcount)
482{
483  ScheduleDAGInstrs::enterRegion(bb, begin, end, endcount);
484
485  // For convenience remember the end of the liveness region.
486  LiveRegionEnd =
487    (RegionEnd == bb->end()) ? RegionEnd : llvm::next(RegionEnd);
488}
489
490// Setup the register pressure trackers for the top scheduled top and bottom
491// scheduled regions.
492void ScheduleDAGMI::initRegPressure() {
493  TopRPTracker.init(&MF, RegClassInfo, LIS, BB, RegionBegin);
494  BotRPTracker.init(&MF, RegClassInfo, LIS, BB, LiveRegionEnd);
495
496  // Close the RPTracker to finalize live ins.
497  RPTracker.closeRegion();
498
499  // Initialize the live ins and live outs.
500  TopRPTracker.addLiveRegs(RPTracker.getPressure().LiveInRegs);
501  BotRPTracker.addLiveRegs(RPTracker.getPressure().LiveOutRegs);
502
503  // Close one end of the tracker so we can call
504  // getMaxUpward/DownwardPressureDelta before advancing across any
505  // instructions. This converts currently live regs into live ins/outs.
506  TopRPTracker.closeTop();
507  BotRPTracker.closeBottom();
508
509  // Account for liveness generated by the region boundary.
510  if (LiveRegionEnd != RegionEnd)
511    BotRPTracker.recede();
512
513  assert(BotRPTracker.getPos() == RegionEnd && "Can't find the region bottom");
514}
515
516/// schedule - Called back from MachineScheduler::runOnMachineFunction
517/// after setting up the current scheduling region. [RegionBegin, RegionEnd)
518/// only includes instructions that have DAG nodes, not scheduling boundaries.
519void ScheduleDAGMI::schedule() {
520  // Initialize the register pressure tracker used by buildSchedGraph.
521  RPTracker.init(&MF, RegClassInfo, LIS, BB, LiveRegionEnd);
522
523  // Account for liveness generate by the region boundary.
524  if (LiveRegionEnd != RegionEnd)
525    RPTracker.recede();
526
527  // Build the DAG, and compute current register pressure.
528  buildSchedGraph(AA, &RPTracker);
529
530  // Initialize top/bottom trackers after computing region pressure.
531  initRegPressure();
532
533  DEBUG(dbgs() << "********** MI Scheduling **********\n");
534  DEBUG(for (unsigned su = 0, e = SUnits.size(); su != e; ++su)
535          SUnits[su].dumpAll(this));
536
537  if (ViewMISchedDAGs) viewGraph();
538
539  SchedImpl->initialize(this);
540
541  // Release edges from the special Entry node or to the special Exit node.
542  releaseSuccessors(&EntrySU);
543  releasePredecessors(&ExitSU);
544
545  // Release all DAG roots for scheduling.
546  for (std::vector<SUnit>::iterator I = SUnits.begin(), E = SUnits.end();
547       I != E; ++I) {
548    // A SUnit is ready to top schedule if it has no predecessors.
549    if (I->Preds.empty())
550      SchedImpl->releaseTopNode(&(*I));
551    // A SUnit is ready to bottom schedule if it has no successors.
552    if (I->Succs.empty())
553      SchedImpl->releaseBottomNode(&(*I));
554  }
555
556  CurrentTop = nextIfDebug(RegionBegin, RegionEnd);
557  CurrentBottom = RegionEnd;
558  bool IsTopNode = false;
559  while (SUnit *SU = SchedImpl->pickNode(IsTopNode)) {
560    DEBUG(dbgs() << "*** " << (IsTopNode ? "Top" : "Bottom")
561          << " Scheduling Instruction:\n"; SU->dump(this));
562    if (!checkSchedLimit())
563      break;
564
565    // Move the instruction to its new location in the instruction stream.
566    MachineInstr *MI = SU->getInstr();
567
568    if (IsTopNode) {
569      assert(SU->isTopReady() && "node still has unscheduled dependencies");
570      if (&*CurrentTop == MI)
571        CurrentTop = nextIfDebug(++CurrentTop, CurrentBottom);
572      else
573        moveInstruction(MI, CurrentTop);
574
575      // Update top scheduled pressure.
576      TopRPTracker.advance();
577      assert(TopRPTracker.getPos() == CurrentTop && "out of sync");
578
579      // Release dependent instructions for scheduling.
580      releaseSuccessors(SU);
581    }
582    else {
583      assert(SU->isBottomReady() && "node still has unscheduled dependencies");
584      MachineBasicBlock::iterator priorII =
585        priorNonDebug(CurrentBottom, CurrentTop);
586      if (&*priorII == MI)
587        CurrentBottom = priorII;
588      else {
589        if (&*CurrentTop == MI)
590          CurrentTop = nextIfDebug(++CurrentTop, CurrentBottom);
591        moveInstruction(MI, CurrentBottom);
592        CurrentBottom = MI;
593      }
594      // Update bottom scheduled pressure.
595      BotRPTracker.recede();
596      assert(BotRPTracker.getPos() == CurrentBottom && "out of sync");
597
598      // Release dependent instructions for scheduling.
599      releasePredecessors(SU);
600    }
601    SU->isScheduled = true;
602  }
603  assert(CurrentTop == CurrentBottom && "Nonempty unscheduled zone.");
604
605  placeDebugValues();
606}
607
608/// Reinsert any remaining debug_values, just like the PostRA scheduler.
609void ScheduleDAGMI::placeDebugValues() {
610  // If first instruction was a DBG_VALUE then put it back.
611  if (FirstDbgValue) {
612    BB->splice(RegionBegin, BB, FirstDbgValue);
613    RegionBegin = FirstDbgValue;
614  }
615
616  for (std::vector<std::pair<MachineInstr *, MachineInstr *> >::iterator
617         DI = DbgValues.end(), DE = DbgValues.begin(); DI != DE; --DI) {
618    std::pair<MachineInstr *, MachineInstr *> P = *prior(DI);
619    MachineInstr *DbgValue = P.first;
620    MachineBasicBlock::iterator OrigPrevMI = P.second;
621    BB->splice(++OrigPrevMI, BB, DbgValue);
622    if (OrigPrevMI == llvm::prior(RegionEnd))
623      RegionEnd = DbgValue;
624  }
625  DbgValues.clear();
626  FirstDbgValue = NULL;
627}
628
629//===----------------------------------------------------------------------===//
630// ConvergingScheduler - Implementation of the standard MachineSchedStrategy.
631//===----------------------------------------------------------------------===//
632
633namespace {
634/// Wrapper around a vector of SUnits with some basic convenience methods.
635struct ReadyQ {
636  typedef std::vector<SUnit*>::iterator iterator;
637
638  unsigned ID;
639  std::vector<SUnit*> Queue;
640
641  ReadyQ(unsigned id): ID(id) {}
642
643  bool isInQueue(SUnit *SU) const {
644    return SU->NodeQueueId & ID;
645  }
646
647  bool empty() const { return Queue.empty(); }
648
649  iterator begin() { return Queue.begin(); }
650
651  iterator end() { return Queue.end(); }
652
653  iterator find(SUnit *SU) {
654    return std::find(Queue.begin(), Queue.end(), SU);
655  }
656
657  void push(SUnit *SU) {
658    Queue.push_back(SU);
659    SU->NodeQueueId |= ID;
660  }
661
662  void remove(iterator I) {
663    (*I)->NodeQueueId &= ~ID;
664    *I = Queue.back();
665    Queue.pop_back();
666  }
667};
668
669/// ConvergingScheduler shrinks the unscheduled zone using heuristics to balance
670/// the schedule.
671class ConvergingScheduler : public MachineSchedStrategy {
672
673  /// Store the state used by ConvergingScheduler heuristics, required for the
674  /// lifetime of one invocation of pickNode().
675  struct SchedCandidate {
676    // The best SUnit candidate.
677    SUnit *SU;
678
679    // Register pressure values for the best candidate.
680    RegPressureDelta RPDelta;
681
682    SchedCandidate(): SU(NULL) {}
683  };
684
685  ScheduleDAGMI *DAG;
686  const TargetRegisterInfo *TRI;
687
688  ReadyQ TopQueue;
689  ReadyQ BotQueue;
690
691public:
692  /// SUnit::NodeQueueId = 0 (none), = 1 (top), = 2 (bottom), = 3 (both)
693  enum {
694    TopQID = 1,
695    BotQID = 2
696  };
697
698  ConvergingScheduler(): DAG(0), TRI(0), TopQueue(TopQID), BotQueue(BotQID) {}
699
700  static const char *getQName(unsigned ID) {
701    switch(ID) {
702    default: return "NoQ";
703    case TopQID: return "TopQ";
704    case BotQID: return "BotQ";
705    };
706  }
707
708  virtual void initialize(ScheduleDAGMI *dag) {
709    DAG = dag;
710    TRI = DAG->TRI;
711
712    assert((!ForceTopDown || !ForceBottomUp) &&
713           "-misched-topdown incompatible with -misched-bottomup");
714  }
715
716  virtual SUnit *pickNode(bool &IsTopNode);
717
718  virtual void releaseTopNode(SUnit *SU) {
719    if (!SU->isScheduled)
720      TopQueue.push(SU);
721  }
722  virtual void releaseBottomNode(SUnit *SU) {
723    if (!SU->isScheduled)
724      BotQueue.push(SU);
725  }
726protected:
727#ifndef NDEBUG
728  void traceCandidate(const char *Label, unsigned QID, SUnit *SU,
729                      int RPDiff, unsigned PSetID);
730#endif
731  bool pickNodeFromQueue(ReadyQ &Q, const RegPressureTracker &RPTracker,
732                         SchedCandidate &Candidate);
733};
734} // namespace
735
736#ifndef NDEBUG
737void ConvergingScheduler::
738traceCandidate(const char *Label, unsigned QID, SUnit *SU,
739               int RPDiff, unsigned PSetID) {
740  dbgs() << Label << getQName(QID) << " ";
741  if (RPDiff)
742    dbgs() << TRI->getRegPressureSetName(PSetID) << ":" << RPDiff << " ";
743  else
744    dbgs() << "     ";
745  SU->dump(DAG);
746}
747#endif
748
749/// Pick the best candidate from the top queue.
750///
751/// TODO: getMaxPressureDelta results can be mostly cached for each SUnit during
752/// DAG building. To adjust for the current scheduling location we need to
753/// maintain the number of vreg uses remaining to be top-scheduled.
754bool ConvergingScheduler::pickNodeFromQueue(ReadyQ &Q,
755                                            const RegPressureTracker &RPTracker,
756                                            SchedCandidate &Candidate) {
757  // getMaxPressureDelta temporarily modifies the tracker.
758  RegPressureTracker &TempTracker = const_cast<RegPressureTracker&>(RPTracker);
759
760  // BestSU remains NULL if no top candidates beat the best existing candidate.
761  bool FoundCandidate = false;
762  for (ReadyQ::iterator I = Q.begin(), E = Q.end(); I != E; ++I) {
763
764    RegPressureDelta RPDelta;
765    TempTracker.getMaxPressureDelta((*I)->getInstr(), RPDelta);
766
767    // Avoid exceeding the target's limit.
768    if (!Candidate.SU || RPDelta.ExcessUnits < Candidate.RPDelta.ExcessUnits) {
769      DEBUG(traceCandidate(Candidate.SU ? "PCAND" : "ACAND", Q.ID, *I,
770                           RPDelta.ExcessUnits, RPDelta.ExcessSetID));
771      Candidate.SU = *I;
772      Candidate.RPDelta = RPDelta;
773      FoundCandidate = true;
774      continue;
775    }
776    if (RPDelta.ExcessUnits > Candidate.RPDelta.ExcessUnits)
777      continue;
778
779    // Avoid increasing the max pressure.
780    if (RPDelta.MaxUnitIncrease < Candidate.RPDelta.MaxUnitIncrease) {
781      DEBUG(traceCandidate("MCAND", Q.ID, *I,
782                           RPDelta.ExcessUnits, RPDelta.ExcessSetID));
783      Candidate.SU = *I;
784      Candidate.RPDelta = RPDelta;
785      FoundCandidate = true;
786      continue;
787    }
788    if (RPDelta.MaxUnitIncrease > Candidate.RPDelta.MaxUnitIncrease)
789      continue;
790
791    // Fall through to original instruction order.
792    // Only consider node order if BestSU was chosen from this Q.
793    if (!FoundCandidate)
794      continue;
795
796    if ((Q.ID == TopQID && (*I)->NodeNum < Candidate.SU->NodeNum)
797        || (Q.ID == BotQID && (*I)->NodeNum > Candidate.SU->NodeNum)) {
798      DEBUG(traceCandidate("NCAND", Q.ID, *I, 0, 0));
799      Candidate.SU = *I;
800      Candidate.RPDelta = RPDelta;
801      FoundCandidate = true;
802    }
803  }
804  return FoundCandidate;
805}
806
807/// Pick the best node from either the top or bottom queue to balance the
808/// schedule.
809SUnit *ConvergingScheduler::pickNode(bool &IsTopNode) {
810  if (DAG->top() == DAG->bottom()) {
811    assert(TopQueue.empty() && BotQueue.empty() && "ReadyQ garbage");
812    return NULL;
813  }
814  // As an initial placeholder heuristic, schedule in the direction that has
815  // the fewest choices.
816  SUnit *SU;
817  if (ForceTopDown) {
818    SU = DAG->getSUnit(DAG->top());
819    IsTopNode = true;
820  }
821  else if (ForceBottomUp) {
822    SU = DAG->getSUnit(priorNonDebug(DAG->bottom(), DAG->top()));
823    IsTopNode = false;
824  }
825  else {
826    SchedCandidate Candidate;
827    // Prefer picking from the bottom.
828    pickNodeFromQueue(BotQueue, DAG->getBotRPTracker(), Candidate);
829    IsTopNode =
830      pickNodeFromQueue(TopQueue, DAG->getTopRPTracker(), Candidate);
831    SU = Candidate.SU;
832  }
833  if (SU->isTopReady()) {
834    assert(!TopQueue.empty() && "bad ready count");
835    TopQueue.remove(TopQueue.find(SU));
836  }
837  if (SU->isBottomReady()) {
838    assert(!BotQueue.empty() && "bad ready count");
839    BotQueue.remove(BotQueue.find(SU));
840  }
841  return SU;
842}
843
844/// Create the standard converging machine scheduler. This will be used as the
845/// default scheduler if the target does not set a default.
846static ScheduleDAGInstrs *createConvergingSched(MachineSchedContext *C) {
847  assert((!ForceTopDown || !ForceBottomUp) &&
848         "-misched-topdown incompatible with -misched-bottomup");
849  return new ScheduleDAGMI(C, new ConvergingScheduler());
850}
851static MachineSchedRegistry
852ConvergingSchedRegistry("converge", "Standard converging scheduler.",
853                        createConvergingSched);
854
855//===----------------------------------------------------------------------===//
856// Machine Instruction Shuffler for Correctness Testing
857//===----------------------------------------------------------------------===//
858
859#ifndef NDEBUG
860namespace {
861/// Apply a less-than relation on the node order, which corresponds to the
862/// instruction order prior to scheduling. IsReverse implements greater-than.
863template<bool IsReverse>
864struct SUnitOrder {
865  bool operator()(SUnit *A, SUnit *B) const {
866    if (IsReverse)
867      return A->NodeNum > B->NodeNum;
868    else
869      return A->NodeNum < B->NodeNum;
870  }
871};
872
873/// Reorder instructions as much as possible.
874class InstructionShuffler : public MachineSchedStrategy {
875  bool IsAlternating;
876  bool IsTopDown;
877
878  // Using a less-than relation (SUnitOrder<false>) for the TopQ priority
879  // gives nodes with a higher number higher priority causing the latest
880  // instructions to be scheduled first.
881  PriorityQueue<SUnit*, std::vector<SUnit*>, SUnitOrder<false> >
882    TopQ;
883  // When scheduling bottom-up, use greater-than as the queue priority.
884  PriorityQueue<SUnit*, std::vector<SUnit*>, SUnitOrder<true> >
885    BottomQ;
886public:
887  InstructionShuffler(bool alternate, bool topdown)
888    : IsAlternating(alternate), IsTopDown(topdown) {}
889
890  virtual void initialize(ScheduleDAGMI *) {
891    TopQ.clear();
892    BottomQ.clear();
893  }
894
895  /// Implement MachineSchedStrategy interface.
896  /// -----------------------------------------
897
898  virtual SUnit *pickNode(bool &IsTopNode) {
899    SUnit *SU;
900    if (IsTopDown) {
901      do {
902        if (TopQ.empty()) return NULL;
903        SU = TopQ.top();
904        TopQ.pop();
905      } while (SU->isScheduled);
906      IsTopNode = true;
907    }
908    else {
909      do {
910        if (BottomQ.empty()) return NULL;
911        SU = BottomQ.top();
912        BottomQ.pop();
913      } while (SU->isScheduled);
914      IsTopNode = false;
915    }
916    if (IsAlternating)
917      IsTopDown = !IsTopDown;
918    return SU;
919  }
920
921  virtual void releaseTopNode(SUnit *SU) {
922    TopQ.push(SU);
923  }
924  virtual void releaseBottomNode(SUnit *SU) {
925    BottomQ.push(SU);
926  }
927};
928} // namespace
929
930static ScheduleDAGInstrs *createInstructionShuffler(MachineSchedContext *C) {
931  bool Alternate = !ForceTopDown && !ForceBottomUp;
932  bool TopDown = !ForceBottomUp;
933  assert((TopDown || !ForceTopDown) &&
934         "-misched-topdown incompatible with -misched-bottomup");
935  return new ScheduleDAGMI(C, new InstructionShuffler(Alternate, TopDown));
936}
937static MachineSchedRegistry ShufflerRegistry(
938  "shuffle", "Shuffle machine instructions alternating directions",
939  createInstructionShuffler);
940#endif // !NDEBUG
941