1//==- MachineScheduler.h - MachineInstr Scheduling Pass ----------*- C++ -*-==//
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// This file provides a MachineSchedRegistry for registering alternative machine
11// schedulers. A Target may provide an alternative scheduler implementation by
12// implementing the following boilerplate:
13//
14// static ScheduleDAGInstrs *createCustomMachineSched(MachineSchedContext *C) {
15//  return new CustomMachineScheduler(C);
16// }
17// static MachineSchedRegistry
18// SchedCustomRegistry("custom", "Run my target's custom scheduler",
19//                     createCustomMachineSched);
20//
21// Inside <Target>PassConfig:
22//   enablePass(&MachineSchedulerID);
23//   MachineSchedRegistry::setDefault(createCustomMachineSched);
24//
25//===----------------------------------------------------------------------===//
26
27#ifndef MACHINESCHEDULER_H
28#define MACHINESCHEDULER_H
29
30#include "llvm/CodeGen/MachinePassRegistry.h"
31#include "llvm/CodeGen/RegisterPressure.h"
32#include "llvm/CodeGen/ScheduleDAGInstrs.h"
33#include "llvm/Target/TargetInstrInfo.h"
34
35namespace llvm {
36
37extern cl::opt<bool> ForceTopDown;
38extern cl::opt<bool> ForceBottomUp;
39
40class AliasAnalysis;
41class LiveIntervals;
42class MachineDominatorTree;
43class MachineLoopInfo;
44class RegisterClassInfo;
45class ScheduleDAGInstrs;
46
47/// MachineSchedContext provides enough context from the MachineScheduler pass
48/// for the target to instantiate a scheduler.
49struct MachineSchedContext {
50  MachineFunction *MF;
51  const MachineLoopInfo *MLI;
52  const MachineDominatorTree *MDT;
53  const TargetPassConfig *PassConfig;
54  AliasAnalysis *AA;
55  LiveIntervals *LIS;
56
57  RegisterClassInfo *RegClassInfo;
58
59  MachineSchedContext();
60  virtual ~MachineSchedContext();
61};
62
63/// MachineSchedRegistry provides a selection of available machine instruction
64/// schedulers.
65class MachineSchedRegistry : public MachinePassRegistryNode {
66public:
67  typedef ScheduleDAGInstrs *(*ScheduleDAGCtor)(MachineSchedContext *);
68
69  // RegisterPassParser requires a (misnamed) FunctionPassCtor type.
70  typedef ScheduleDAGCtor FunctionPassCtor;
71
72  static MachinePassRegistry Registry;
73
74  MachineSchedRegistry(const char *N, const char *D, ScheduleDAGCtor C)
75    : MachinePassRegistryNode(N, D, (MachinePassCtor)C) {
76    Registry.Add(this);
77  }
78  ~MachineSchedRegistry() { Registry.Remove(this); }
79
80  // Accessors.
81  //
82  MachineSchedRegistry *getNext() const {
83    return (MachineSchedRegistry *)MachinePassRegistryNode::getNext();
84  }
85  static MachineSchedRegistry *getList() {
86    return (MachineSchedRegistry *)Registry.getList();
87  }
88  static ScheduleDAGCtor getDefault() {
89    return (ScheduleDAGCtor)Registry.getDefault();
90  }
91  static void setDefault(ScheduleDAGCtor C) {
92    Registry.setDefault((MachinePassCtor)C);
93  }
94  static void setDefault(StringRef Name) {
95    Registry.setDefault(Name);
96  }
97  static void setListener(MachinePassRegistryListener *L) {
98    Registry.setListener(L);
99  }
100};
101
102class ScheduleDAGMI;
103
104/// MachineSchedStrategy - Interface to the scheduling algorithm used by
105/// ScheduleDAGMI.
106class MachineSchedStrategy {
107public:
108  virtual ~MachineSchedStrategy() {}
109
110  /// Initialize the strategy after building the DAG for a new region.
111  virtual void initialize(ScheduleDAGMI *DAG) = 0;
112
113  /// Notify this strategy that all roots have been released (including those
114  /// that depend on EntrySU or ExitSU).
115  virtual void registerRoots() {}
116
117  /// Pick the next node to schedule, or return NULL. Set IsTopNode to true to
118  /// schedule the node at the top of the unscheduled region. Otherwise it will
119  /// be scheduled at the bottom.
120  virtual SUnit *pickNode(bool &IsTopNode) = 0;
121
122  /// Notify MachineSchedStrategy that ScheduleDAGMI has scheduled an
123  /// instruction and updated scheduled/remaining flags in the DAG nodes.
124  virtual void schedNode(SUnit *SU, bool IsTopNode) = 0;
125
126  /// When all predecessor dependencies have been resolved, free this node for
127  /// top-down scheduling.
128  virtual void releaseTopNode(SUnit *SU) = 0;
129  /// When all successor dependencies have been resolved, free this node for
130  /// bottom-up scheduling.
131  virtual void releaseBottomNode(SUnit *SU) = 0;
132};
133
134/// ReadyQueue encapsulates vector of "ready" SUnits with basic convenience
135/// methods for pushing and removing nodes. ReadyQueue's are uniquely identified
136/// by an ID. SUnit::NodeQueueId is a mask of the ReadyQueues the SUnit is in.
137///
138/// This is a convenience class that may be used by implementations of
139/// MachineSchedStrategy.
140class ReadyQueue {
141  unsigned ID;
142  std::string Name;
143  std::vector<SUnit*> Queue;
144
145public:
146  ReadyQueue(unsigned id, const Twine &name): ID(id), Name(name.str()) {}
147
148  unsigned getID() const { return ID; }
149
150  StringRef getName() const { return Name; }
151
152  // SU is in this queue if it's NodeQueueID is a superset of this ID.
153  bool isInQueue(SUnit *SU) const { return (SU->NodeQueueId & ID); }
154
155  bool empty() const { return Queue.empty(); }
156
157  unsigned size() const { return Queue.size(); }
158
159  typedef std::vector<SUnit*>::iterator iterator;
160
161  iterator begin() { return Queue.begin(); }
162
163  iterator end() { return Queue.end(); }
164
165  iterator find(SUnit *SU) {
166    return std::find(Queue.begin(), Queue.end(), SU);
167  }
168
169  void push(SUnit *SU) {
170    Queue.push_back(SU);
171    SU->NodeQueueId |= ID;
172  }
173
174  void remove(iterator I) {
175    (*I)->NodeQueueId &= ~ID;
176    *I = Queue.back();
177    Queue.pop_back();
178  }
179
180#ifndef NDEBUG
181  void dump();
182#endif
183};
184
185/// Mutate the DAG as a postpass after normal DAG building.
186class ScheduleDAGMutation {
187public:
188  virtual ~ScheduleDAGMutation() {}
189
190  virtual void apply(ScheduleDAGMI *DAG) = 0;
191};
192
193/// ScheduleDAGMI is an implementation of ScheduleDAGInstrs that schedules
194/// machine instructions while updating LiveIntervals and tracking regpressure.
195class ScheduleDAGMI : public ScheduleDAGInstrs {
196protected:
197  AliasAnalysis *AA;
198  RegisterClassInfo *RegClassInfo;
199  MachineSchedStrategy *SchedImpl;
200
201  /// Ordered list of DAG postprocessing steps.
202  std::vector<ScheduleDAGMutation*> Mutations;
203
204  MachineBasicBlock::iterator LiveRegionEnd;
205
206  /// Register pressure in this region computed by buildSchedGraph.
207  IntervalPressure RegPressure;
208  RegPressureTracker RPTracker;
209
210  /// List of pressure sets that exceed the target's pressure limit before
211  /// scheduling, listed in increasing set ID order. Each pressure set is paired
212  /// with its max pressure in the currently scheduled regions.
213  std::vector<PressureElement> RegionCriticalPSets;
214
215  /// The top of the unscheduled zone.
216  MachineBasicBlock::iterator CurrentTop;
217  IntervalPressure TopPressure;
218  RegPressureTracker TopRPTracker;
219
220  /// The bottom of the unscheduled zone.
221  MachineBasicBlock::iterator CurrentBottom;
222  IntervalPressure BotPressure;
223  RegPressureTracker BotRPTracker;
224
225#ifndef NDEBUG
226  /// The number of instructions scheduled so far. Used to cut off the
227  /// scheduler at the point determined by misched-cutoff.
228  unsigned NumInstrsScheduled;
229#endif
230
231public:
232  ScheduleDAGMI(MachineSchedContext *C, MachineSchedStrategy *S):
233    ScheduleDAGInstrs(*C->MF, *C->MLI, *C->MDT, /*IsPostRA=*/false, C->LIS),
234    AA(C->AA), RegClassInfo(C->RegClassInfo), SchedImpl(S),
235    RPTracker(RegPressure), CurrentTop(), TopRPTracker(TopPressure),
236    CurrentBottom(), BotRPTracker(BotPressure) {
237#ifndef NDEBUG
238    NumInstrsScheduled = 0;
239#endif
240  }
241
242  virtual ~ScheduleDAGMI() {
243    delete SchedImpl;
244  }
245
246  /// Add a postprocessing step to the DAG builder.
247  /// Mutations are applied in the order that they are added after normal DAG
248  /// building and before MachineSchedStrategy initialization.
249  void addMutation(ScheduleDAGMutation *Mutation) {
250    Mutations.push_back(Mutation);
251  }
252
253  MachineBasicBlock::iterator top() const { return CurrentTop; }
254  MachineBasicBlock::iterator bottom() const { return CurrentBottom; }
255
256  /// Implement the ScheduleDAGInstrs interface for handling the next scheduling
257  /// region. This covers all instructions in a block, while schedule() may only
258  /// cover a subset.
259  void enterRegion(MachineBasicBlock *bb,
260                   MachineBasicBlock::iterator begin,
261                   MachineBasicBlock::iterator end,
262                   unsigned endcount);
263
264
265  /// Implement ScheduleDAGInstrs interface for scheduling a sequence of
266  /// reorderable instructions.
267  virtual void schedule();
268
269  /// Get current register pressure for the top scheduled instructions.
270  const IntervalPressure &getTopPressure() const { return TopPressure; }
271  const RegPressureTracker &getTopRPTracker() const { return TopRPTracker; }
272
273  /// Get current register pressure for the bottom scheduled instructions.
274  const IntervalPressure &getBotPressure() const { return BotPressure; }
275  const RegPressureTracker &getBotRPTracker() const { return BotRPTracker; }
276
277  /// Get register pressure for the entire scheduling region before scheduling.
278  const IntervalPressure &getRegPressure() const { return RegPressure; }
279
280  const std::vector<PressureElement> &getRegionCriticalPSets() const {
281    return RegionCriticalPSets;
282  }
283
284protected:
285  // Top-Level entry points for the schedule() driver...
286
287  /// Call ScheduleDAGInstrs::buildSchedGraph with register pressure tracking
288  /// enabled. This sets up three trackers. RPTracker will cover the entire DAG
289  /// region, TopTracker and BottomTracker will be initialized to the top and
290  /// bottom of the DAG region without covereing any unscheduled instruction.
291  void buildDAGWithRegPressure();
292
293  /// Apply each ScheduleDAGMutation step in order. This allows different
294  /// instances of ScheduleDAGMI to perform custom DAG postprocessing.
295  void postprocessDAG();
296
297  /// Identify DAG roots and setup scheduler queues.
298  void initQueues();
299
300  /// Move an instruction and update register pressure.
301  void scheduleMI(SUnit *SU, bool IsTopNode);
302
303  /// Update scheduler DAG and queues after scheduling an instruction.
304  void updateQueues(SUnit *SU, bool IsTopNode);
305
306  /// Reinsert debug_values recorded in ScheduleDAGInstrs::DbgValues.
307  void placeDebugValues();
308
309  // Lesser helpers...
310
311  void initRegPressure();
312
313  void updateScheduledPressure(std::vector<unsigned> NewMaxPressure);
314
315  void moveInstruction(MachineInstr *MI, MachineBasicBlock::iterator InsertPos);
316  bool checkSchedLimit();
317
318  void releaseRoots();
319
320  void releaseSucc(SUnit *SU, SDep *SuccEdge);
321  void releaseSuccessors(SUnit *SU);
322  void releasePred(SUnit *SU, SDep *PredEdge);
323  void releasePredecessors(SUnit *SU);
324};
325
326} // namespace llvm
327
328#endif
329