HexagonMachineScheduler.h revision c6a6660c6271d3309379ff439f66eb0e6ad48e3a 
1//===-- HexagonMachineScheduler.h - Custom Hexagon MI 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// Custom Hexagon MI scheduler.
11//
12//===----------------------------------------------------------------------===//
13
14#ifndef HEXAGONASMPRINTER_H
15#define HEXAGONASMPRINTER_H
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/RegisterPressure.h"
22#include "llvm/CodeGen/ResourcePriorityQueue.h"
23#include "llvm/CodeGen/ScheduleDAGInstrs.h"
24#include "llvm/CodeGen/ScheduleHazardRecognizer.h"
25#include "llvm/Analysis/AliasAnalysis.h"
26#include "llvm/Target/TargetInstrInfo.h"
27#include "llvm/Support/CommandLine.h"
28#include "llvm/Support/Debug.h"
29#include "llvm/Support/ErrorHandling.h"
30#include "llvm/Support/raw_ostream.h"
31#include "llvm/ADT/OwningPtr.h"
32#include "llvm/ADT/PriorityQueue.h"
33
34using namespace llvm;
35
36namespace llvm {
37//===----------------------------------------------------------------------===//
38// ConvergingVLIWScheduler - Implementation of the standard
39// MachineSchedStrategy.
40//===----------------------------------------------------------------------===//
41
42class VLIWResourceModel {
43  /// ResourcesModel - Represents VLIW state.
44  /// Not limited to VLIW targets per say, but assumes
45  /// definition of DFA by a target.
46  DFAPacketizer *ResourcesModel;
47
48  const InstrItineraryData *InstrItins;
49
50  /// Local packet/bundle model. Purely
51  /// internal to the MI schedulre at the time.
52  std::vector<SUnit*> Packet;
53
54  /// Total packets created.
55  unsigned TotalPackets;
56
57public:
58  VLIWResourceModel(MachineSchedContext *C, const InstrItineraryData *IID) :
59    InstrItins(IID), TotalPackets(0) {
60    const TargetMachine &TM = C->MF->getTarget();
61    ResourcesModel = TM.getInstrInfo()->CreateTargetScheduleState(&TM,NULL);
62
63    // This hard requirement could be relaxed,
64    // but for now do not let it proceed.
65    assert(ResourcesModel && "Unimplemented CreateTargetScheduleState.");
66
67    Packet.resize(InstrItins->SchedModel->IssueWidth);
68    Packet.clear();
69    ResourcesModel->clearResources();
70  }
71
72  VLIWResourceModel(const TargetMachine &TM) :
73    InstrItins(TM.getInstrItineraryData()), TotalPackets(0) {
74    ResourcesModel = TM.getInstrInfo()->CreateTargetScheduleState(&TM,NULL);
75
76    // This hard requirement could be relaxed,
77    // but for now do not let it proceed.
78    assert(ResourcesModel && "Unimplemented CreateTargetScheduleState.");
79
80    Packet.resize(InstrItins->SchedModel->IssueWidth);
81    Packet.clear();
82    ResourcesModel->clearResources();
83  }
84
85  ~VLIWResourceModel() {
86    delete ResourcesModel;
87  }
88
89  void resetPacketState() {
90    Packet.clear();
91  }
92
93  void resetDFA() {
94    ResourcesModel->clearResources();
95  }
96
97  void reset() {
98    Packet.clear();
99    ResourcesModel->clearResources();
100  }
101
102  bool isResourceAvailable(SUnit *SU);
103  bool reserveResources(SUnit *SU);
104  unsigned getTotalPackets() const { return TotalPackets; }
105};
106
107/// Extend the standard ScheduleDAGMI to provide more context and override the
108/// top-level schedule() driver.
109class VLIWMachineScheduler : public ScheduleDAGMI {
110public:
111  VLIWMachineScheduler(MachineSchedContext *C, MachineSchedStrategy *S):
112    ScheduleDAGMI(C, S) {}
113
114  /// Schedule - This is called back from ScheduleDAGInstrs::Run() when it's
115  /// time to do some work.
116  virtual void schedule();
117  /// Perform platform specific DAG postprocessing.
118  void postprocessDAG();
119};
120
121/// ConvergingVLIWScheduler shrinks the unscheduled zone using heuristics
122/// to balance the schedule.
123class ConvergingVLIWScheduler : public MachineSchedStrategy {
124
125  /// Store the state used by ConvergingVLIWScheduler heuristics, required
126  ///  for the lifetime of one invocation of pickNode().
127  struct SchedCandidate {
128    // The best SUnit candidate.
129    SUnit *SU;
130
131    // Register pressure values for the best candidate.
132    RegPressureDelta RPDelta;
133
134    // Best scheduling cost.
135    int SCost;
136
137    SchedCandidate(): SU(NULL), SCost(0) {}
138  };
139  /// Represent the type of SchedCandidate found within a single queue.
140  enum CandResult {
141    NoCand, NodeOrder, SingleExcess, SingleCritical, SingleMax, MultiPressure,
142    BestCost};
143
144  /// Each Scheduling boundary is associated with ready queues. It tracks the
145  /// current cycle in whichever direction at has moved, and maintains the state
146  /// of "hazards" and other interlocks at the current cycle.
147  struct SchedBoundary {
148    VLIWMachineScheduler *DAG;
149
150    ReadyQueue Available;
151    ReadyQueue Pending;
152    bool CheckPending;
153
154    ScheduleHazardRecognizer *HazardRec;
155    VLIWResourceModel *ResourceModel;
156
157    unsigned CurrCycle;
158    unsigned IssueCount;
159
160    /// MinReadyCycle - Cycle of the soonest available instruction.
161    unsigned MinReadyCycle;
162
163    // Remember the greatest min operand latency.
164    unsigned MaxMinLatency;
165
166    /// Pending queues extend the ready queues with the same ID and the
167    /// PendingFlag set.
168    SchedBoundary(unsigned ID, const Twine &Name):
169      DAG(0), Available(ID, Name+".A"),
170      Pending(ID << ConvergingVLIWScheduler::LogMaxQID, Name+".P"),
171      CheckPending(false), HazardRec(0), ResourceModel(0),
172      CurrCycle(0), IssueCount(0),
173      MinReadyCycle(UINT_MAX), MaxMinLatency(0) {}
174
175    ~SchedBoundary() {
176      delete ResourceModel;
177      delete HazardRec;
178    }
179
180    bool isTop() const {
181      return Available.getID() == ConvergingVLIWScheduler::TopQID;
182    }
183
184    bool checkHazard(SUnit *SU);
185
186    void releaseNode(SUnit *SU, unsigned ReadyCycle);
187
188    void bumpCycle();
189
190    void bumpNode(SUnit *SU);
191
192    void releasePending();
193
194    void removeReady(SUnit *SU);
195
196    SUnit *pickOnlyChoice();
197  };
198
199  VLIWMachineScheduler *DAG;
200  const TargetRegisterInfo *TRI;
201
202  // State of the top and bottom scheduled instruction boundaries.
203  SchedBoundary Top;
204  SchedBoundary Bot;
205
206public:
207  /// SUnit::NodeQueueId: 0 (none), 1 (top), 2 (bot), 3 (both)
208  enum {
209    TopQID = 1,
210    BotQID = 2,
211    LogMaxQID = 2
212  };
213
214  ConvergingVLIWScheduler():
215    DAG(0), TRI(0), Top(TopQID, "TopQ"), Bot(BotQID, "BotQ") {}
216
217  virtual void initialize(ScheduleDAGMI *dag);
218
219  virtual SUnit *pickNode(bool &IsTopNode);
220
221  virtual void schedNode(SUnit *SU, bool IsTopNode);
222
223  virtual void releaseTopNode(SUnit *SU);
224
225  virtual void releaseBottomNode(SUnit *SU);
226
227  unsigned ReportPackets() {
228    return Top.ResourceModel->getTotalPackets() +
229           Bot.ResourceModel->getTotalPackets();
230  }
231
232protected:
233  SUnit *pickNodeBidrectional(bool &IsTopNode);
234
235  int SchedulingCost(ReadyQueue &Q,
236                     SUnit *SU, SchedCandidate &Candidate,
237                     RegPressureDelta &Delta, bool verbose);
238
239  CandResult pickNodeFromQueue(ReadyQueue &Q,
240                               const RegPressureTracker &RPTracker,
241                               SchedCandidate &Candidate);
242#ifndef NDEBUG
243  void traceCandidate(const char *Label, const ReadyQueue &Q, SUnit *SU,
244                      PressureElement P = PressureElement());
245#endif
246};
247
248} // namespace
249
250
251#endif
252