MachineScheduler.cpp revision e9ef4ed13ba84ef27da831afa27b7955c8f09530 
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 "ScheduleDAGInstrs.h"
18#include "LiveDebugVariables.h"
19#include "llvm/CodeGen/LiveIntervalAnalysis.h"
20#include "llvm/CodeGen/MachinePassRegistry.h"
21#include "llvm/CodeGen/Passes.h"
22#include "llvm/Analysis/AliasAnalysis.h"
23#include "llvm/Target/TargetInstrInfo.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
30using namespace llvm;
31
32//===----------------------------------------------------------------------===//
33// Machine Instruction Scheduling Pass and Registry
34//===----------------------------------------------------------------------===//
35
36namespace {
37/// MachineSchedulerPass runs after coalescing and before register allocation.
38class MachineSchedulerPass : public MachineFunctionPass {
39public:
40  MachineFunction *MF;
41  const TargetInstrInfo *TII;
42  const MachineLoopInfo *MLI;
43  const MachineDominatorTree *MDT;
44
45  MachineSchedulerPass();
46
47  virtual void getAnalysisUsage(AnalysisUsage &AU) const;
48
49  virtual void releaseMemory() {}
50
51  virtual bool runOnMachineFunction(MachineFunction&);
52
53  virtual void print(raw_ostream &O, const Module* = 0) const;
54
55  static char ID; // Class identification, replacement for typeinfo
56};
57} // namespace
58
59char MachineSchedulerPass::ID = 0;
60
61char &llvm::MachineSchedulerPassID = MachineSchedulerPass::ID;
62
63INITIALIZE_PASS_BEGIN(MachineSchedulerPass, "misched",
64                      "Machine Instruction Scheduler", false, false)
65INITIALIZE_AG_DEPENDENCY(AliasAnalysis)
66INITIALIZE_PASS_DEPENDENCY(SlotIndexes)
67INITIALIZE_PASS_DEPENDENCY(LiveIntervals)
68INITIALIZE_PASS_DEPENDENCY(LiveDebugVariables)
69INITIALIZE_PASS_DEPENDENCY(StrongPHIElimination)
70INITIALIZE_PASS_DEPENDENCY(RegisterCoalescer)
71INITIALIZE_PASS_END(MachineSchedulerPass, "misched",
72                    "Machine Instruction Scheduler", false, false)
73
74MachineSchedulerPass::MachineSchedulerPass()
75: MachineFunctionPass(ID), MF(0), MLI(0), MDT(0) {
76  initializeMachineSchedulerPassPass(*PassRegistry::getPassRegistry());
77}
78
79void MachineSchedulerPass::getAnalysisUsage(AnalysisUsage &AU) const {
80  AU.setPreservesCFG();
81  AU.addRequiredID(MachineDominatorsID);
82  AU.addRequired<MachineLoopInfo>();
83  AU.addRequired<AliasAnalysis>();
84  AU.addPreserved<AliasAnalysis>();
85  AU.addRequired<SlotIndexes>();
86  AU.addPreserved<SlotIndexes>();
87  AU.addRequired<LiveIntervals>();
88  AU.addPreserved<LiveIntervals>();
89  AU.addRequired<LiveDebugVariables>();
90  AU.addPreserved<LiveDebugVariables>();
91  if (StrongPHIElim) {
92    AU.addRequiredID(StrongPHIEliminationID);
93    AU.addPreservedID(StrongPHIEliminationID);
94  }
95  AU.addRequiredID(RegisterCoalescerPassID);
96  AU.addPreservedID(RegisterCoalescerPassID);
97  MachineFunctionPass::getAnalysisUsage(AU);
98}
99
100namespace {
101/// MachineSchedRegistry provides a selection of available machine instruction
102/// schedulers.
103class MachineSchedRegistry : public MachinePassRegistryNode {
104public:
105  typedef ScheduleDAGInstrs *(*ScheduleDAGCtor)(MachineSchedulerPass *);
106
107  // RegisterPassParser requires a (misnamed) FunctionPassCtor type.
108  typedef ScheduleDAGCtor FunctionPassCtor;
109
110  static MachinePassRegistry Registry;
111
112  MachineSchedRegistry(const char *N, const char *D, ScheduleDAGCtor C)
113    : MachinePassRegistryNode(N, D, (MachinePassCtor)C) {
114    Registry.Add(this);
115  }
116  ~MachineSchedRegistry() { Registry.Remove(this); }
117
118  // Accessors.
119  //
120  MachineSchedRegistry *getNext() const {
121    return (MachineSchedRegistry *)MachinePassRegistryNode::getNext();
122  }
123  static MachineSchedRegistry *getList() {
124    return (MachineSchedRegistry *)Registry.getList();
125  }
126  static ScheduleDAGCtor getDefault() {
127    return (ScheduleDAGCtor)Registry.getDefault();
128  }
129  static void setDefault(ScheduleDAGCtor C) {
130    Registry.setDefault((MachinePassCtor)C);
131  }
132  static void setListener(MachinePassRegistryListener *L) {
133    Registry.setListener(L);
134  }
135};
136} // namespace
137
138MachinePassRegistry MachineSchedRegistry::Registry;
139
140static ScheduleDAGInstrs *createDefaultMachineSched(MachineSchedulerPass *P);
141
142/// MachineSchedOpt allows command line selection of the scheduler.
143static cl::opt<MachineSchedRegistry::ScheduleDAGCtor, false,
144               RegisterPassParser<MachineSchedRegistry> >
145MachineSchedOpt("misched",
146                cl::init(&createDefaultMachineSched), cl::Hidden,
147                cl::desc("Machine instruction scheduler to use"));
148
149//===----------------------------------------------------------------------===//
150// Machine Instruction Scheduling Implementation
151//===----------------------------------------------------------------------===//
152
153namespace {
154/// MachineScheduler is an implementation of ScheduleDAGInstrs that schedules
155/// machine instructions while updating LiveIntervals.
156class MachineScheduler : public ScheduleDAGInstrs {
157  MachineSchedulerPass *Pass;
158public:
159  MachineScheduler(MachineSchedulerPass *P):
160    ScheduleDAGInstrs(*P->MF, *P->MLI, *P->MDT), Pass(P) {}
161
162  /// Schedule - This is called back from ScheduleDAGInstrs::Run() when it's
163  /// time to do some work.
164  virtual void Schedule();
165};
166} // namespace
167
168static ScheduleDAGInstrs *createDefaultMachineSched(MachineSchedulerPass *P) {
169  return new MachineScheduler(P);
170}
171static MachineSchedRegistry
172SchedDefaultRegistry("default", "Activate the scheduler pass, "
173                     "but don't reorder instructions",
174                     createDefaultMachineSched);
175
176/// Schedule - This is called back from ScheduleDAGInstrs::Run() when it's
177/// time to do some work.
178void MachineScheduler::Schedule() {
179  BuildSchedGraph(&Pass->getAnalysis<AliasAnalysis>());
180
181  DEBUG(dbgs() << "********** MI Scheduling **********\n");
182  DEBUG(for (unsigned su = 0, e = SUnits.size(); su != e; ++su)
183          SUnits[su].dumpAll(this));
184
185  // TODO: Put interesting things here.
186}
187
188bool MachineSchedulerPass::runOnMachineFunction(MachineFunction &mf) {
189  // Initialize the context of the pass.
190  MF = &mf;
191  MLI = &getAnalysis<MachineLoopInfo>();
192  MDT = &getAnalysis<MachineDominatorTree>();
193  TII = MF->getTarget().getInstrInfo();
194
195  // Select the scheduler, or set the default.
196  MachineSchedRegistry::ScheduleDAGCtor Ctor =
197    MachineSchedRegistry::getDefault();
198  if (!Ctor) {
199    Ctor = MachineSchedOpt;
200    MachineSchedRegistry::setDefault(Ctor);
201  }
202  // Instantiate the selected scheduler.
203  OwningPtr<ScheduleDAGInstrs> Scheduler(Ctor(this));
204
205  // Visit all machine basic blocks.
206  for (MachineFunction::iterator MBB = MF->begin(), MBBEnd = MF->end();
207       MBB != MBBEnd; ++MBB) {
208
209    // Break the block into scheduling regions [I, RegionEnd), and schedule each
210    // region as soon as it is discovered.
211    unsigned RemainingCount = MBB->size();
212    for(MachineBasicBlock::iterator RegionEnd = MBB->end();
213        RegionEnd != MBB->begin();) {
214      // The next region starts above the previous region. Look backward in the
215      // instruction stream until we find the nearest boundary.
216      MachineBasicBlock::iterator I = RegionEnd;
217      for(;I != MBB->begin(); --I) {
218        if (TII->isSchedulingBoundary(llvm::prior(I), MBB, *MF))
219          break;
220      }
221      if (I == RegionEnd || I == llvm::prior(RegionEnd)) {
222        // Skip empty or single instruction scheduling regions.
223        RegionEnd = llvm::prior(RegionEnd);
224        continue;
225      }
226      DEBUG(dbgs() << "MachineScheduling " << MF->getFunction()->getName()
227            << ":BB#" << MBB->getNumber() << "\n  From: " << *I << " To: "
228            << *RegionEnd << " Remaining: " << RemainingCount << "\n");
229
230      // Inform ScheduleDAGInstrs of the region being scheduler. It calls back
231      // to our Schedule() method.
232      Scheduler->Run(MBB, I, RegionEnd, MBB->size());
233      RegionEnd = I;
234    }
235    assert(RemainingCount == 0 && "Instruction count mismatch!");
236  }
237  return true;
238}
239
240void MachineSchedulerPass::print(raw_ostream &O, const Module* m) const {
241  // unimplemented
242}
243
244//===----------------------------------------------------------------------===//
245// Machine Instruction Shuffler for Correctness Testing
246//===----------------------------------------------------------------------===//
247
248#ifndef NDEBUG
249namespace {
250/// Reorder instructions as much as possible.
251class InstructionShuffler : public ScheduleDAGInstrs {
252  MachineSchedulerPass *Pass;
253public:
254  InstructionShuffler(MachineSchedulerPass *P):
255    ScheduleDAGInstrs(*P->MF, *P->MLI, *P->MDT), Pass(P) {}
256
257  /// Schedule - This is called back from ScheduleDAGInstrs::Run() when it's
258  /// time to do some work.
259  virtual void Schedule() {
260    llvm_unreachable("unimplemented");
261  }
262};
263} // namespace
264
265static ScheduleDAGInstrs *createInstructionShuffler(MachineSchedulerPass *P) {
266  return new InstructionShuffler(P);
267}
268static MachineSchedRegistry ShufflerRegistry("shuffle",
269                                             "Shuffle machine instructions",
270                                             createInstructionShuffler);
271#endif // !NDEBUG
272