blob: b05d7263cdf62e0fbd371a09cc34c9df4062ffc4 [file] [log] [blame]
Andrew Trick5429a6b2012-05-17 22:37:09 +00001//===- MachineScheduler.cpp - Machine Instruction Scheduler ---------------===//
Andrew Trick96f678f2012-01-13 06:30:30 +00002//
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
Andrew Trick96f678f2012-01-13 06:30:30 +000017#include "llvm/CodeGen/LiveIntervalAnalysis.h"
Andrew Trickc174eaf2012-03-08 01:41:12 +000018#include "llvm/CodeGen/MachineScheduler.h"
Andrew Trick96f678f2012-01-13 06:30:30 +000019#include "llvm/CodeGen/Passes.h"
Andrew Trick15252602012-06-06 20:29:31 +000020#include "llvm/CodeGen/RegisterClassInfo.h"
Andrew Trick1e94e982012-10-15 18:02:27 +000021#include "llvm/CodeGen/ScheduleDAGILP.h"
Andrew Trick0a39d4e2012-05-24 22:11:09 +000022#include "llvm/CodeGen/ScheduleHazardRecognizer.h"
Andrew Trickb7e02892012-06-05 21:11:27 +000023#include "llvm/Analysis/AliasAnalysis.h"
Andrew Trick96f678f2012-01-13 06:30:30 +000024#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"
Andrew Trick17d35e52012-03-14 04:00:41 +000029#include "llvm/ADT/PriorityQueue.h"
Andrew Trick96f678f2012-01-13 06:30:30 +000030
Andrew Trickc6cf11b2012-01-17 06:55:07 +000031#include <queue>
32
Andrew Trick96f678f2012-01-13 06:30:30 +000033using namespace llvm;
34
Andrew Trick78e5efe2012-09-11 00:39:15 +000035namespace llvm {
36cl::opt<bool> ForceTopDown("misched-topdown", cl::Hidden,
37 cl::desc("Force top-down list scheduling"));
38cl::opt<bool> ForceBottomUp("misched-bottomup", cl::Hidden,
39 cl::desc("Force bottom-up list scheduling"));
40}
Andrew Trick17d35e52012-03-14 04:00:41 +000041
Andrew Trick0df7f882012-03-07 00:18:25 +000042#ifndef NDEBUG
43static cl::opt<bool> ViewMISchedDAGs("view-misched-dags", cl::Hidden,
44 cl::desc("Pop up a window to show MISched dags after they are processed"));
Lang Hames23f1cbb2012-03-19 18:38:38 +000045
46static cl::opt<unsigned> MISchedCutoff("misched-cutoff", cl::Hidden,
47 cl::desc("Stop scheduling after N instructions"), cl::init(~0U));
Andrew Trick0df7f882012-03-07 00:18:25 +000048#else
49static bool ViewMISchedDAGs = false;
50#endif // NDEBUG
51
Andrew Trick3b87f622012-11-07 07:05:09 +000052// Threshold to very roughly model an out-of-order processor's instruction
53// buffers. If the actual value of this threshold matters much in practice, then
54// it can be specified by the machine model. For now, it's an experimental
55// tuning knob to determine when and if it matters.
56static cl::opt<unsigned> ILPWindow("ilp-window", cl::Hidden,
57 cl::desc("Allow expected latency to exceed the critical path by N cycles "
58 "before attempting to balance ILP"),
59 cl::init(10U));
60
Andrew Trick9b5caaa2012-11-12 19:40:10 +000061// Experimental heuristics
62static cl::opt<bool> EnableLoadCluster("misched-cluster", cl::Hidden,
63 cl::desc("Enable load clustering."));
64
Andrew Trick6996fd02012-11-12 19:52:20 +000065// Experimental heuristics
66static cl::opt<bool> EnableMacroFusion("misched-fusion", cl::Hidden,
67 cl::desc("Enable scheduling for macro fusion."));
68
Andrew Trick5edf2f02012-01-14 02:17:06 +000069//===----------------------------------------------------------------------===//
70// Machine Instruction Scheduling Pass and Registry
71//===----------------------------------------------------------------------===//
72
Andrew Trick86b7e2a2012-04-24 20:36:19 +000073MachineSchedContext::MachineSchedContext():
74 MF(0), MLI(0), MDT(0), PassConfig(0), AA(0), LIS(0) {
75 RegClassInfo = new RegisterClassInfo();
76}
77
78MachineSchedContext::~MachineSchedContext() {
79 delete RegClassInfo;
80}
81
Andrew Trick96f678f2012-01-13 06:30:30 +000082namespace {
Andrew Trick42b7a712012-01-17 06:55:03 +000083/// MachineScheduler runs after coalescing and before register allocation.
Andrew Trickc174eaf2012-03-08 01:41:12 +000084class MachineScheduler : public MachineSchedContext,
85 public MachineFunctionPass {
Andrew Trick96f678f2012-01-13 06:30:30 +000086public:
Andrew Trick42b7a712012-01-17 06:55:03 +000087 MachineScheduler();
Andrew Trick96f678f2012-01-13 06:30:30 +000088
89 virtual void getAnalysisUsage(AnalysisUsage &AU) const;
90
91 virtual void releaseMemory() {}
92
93 virtual bool runOnMachineFunction(MachineFunction&);
94
95 virtual void print(raw_ostream &O, const Module* = 0) const;
96
97 static char ID; // Class identification, replacement for typeinfo
98};
99} // namespace
100
Andrew Trick42b7a712012-01-17 06:55:03 +0000101char MachineScheduler::ID = 0;
Andrew Trick96f678f2012-01-13 06:30:30 +0000102
Andrew Trick42b7a712012-01-17 06:55:03 +0000103char &llvm::MachineSchedulerID = MachineScheduler::ID;
Andrew Trick96f678f2012-01-13 06:30:30 +0000104
Andrew Trick42b7a712012-01-17 06:55:03 +0000105INITIALIZE_PASS_BEGIN(MachineScheduler, "misched",
Andrew Trick96f678f2012-01-13 06:30:30 +0000106 "Machine Instruction Scheduler", false, false)
107INITIALIZE_AG_DEPENDENCY(AliasAnalysis)
108INITIALIZE_PASS_DEPENDENCY(SlotIndexes)
109INITIALIZE_PASS_DEPENDENCY(LiveIntervals)
Andrew Trick42b7a712012-01-17 06:55:03 +0000110INITIALIZE_PASS_END(MachineScheduler, "misched",
Andrew Trick96f678f2012-01-13 06:30:30 +0000111 "Machine Instruction Scheduler", false, false)
112
Andrew Trick42b7a712012-01-17 06:55:03 +0000113MachineScheduler::MachineScheduler()
Andrew Trickc174eaf2012-03-08 01:41:12 +0000114: MachineFunctionPass(ID) {
Andrew Trick42b7a712012-01-17 06:55:03 +0000115 initializeMachineSchedulerPass(*PassRegistry::getPassRegistry());
Andrew Trick96f678f2012-01-13 06:30:30 +0000116}
117
Andrew Trick42b7a712012-01-17 06:55:03 +0000118void MachineScheduler::getAnalysisUsage(AnalysisUsage &AU) const {
Andrew Trick96f678f2012-01-13 06:30:30 +0000119 AU.setPreservesCFG();
120 AU.addRequiredID(MachineDominatorsID);
121 AU.addRequired<MachineLoopInfo>();
122 AU.addRequired<AliasAnalysis>();
Andrew Trickd04ec0c2012-03-09 00:52:20 +0000123 AU.addRequired<TargetPassConfig>();
Andrew Trick96f678f2012-01-13 06:30:30 +0000124 AU.addRequired<SlotIndexes>();
125 AU.addPreserved<SlotIndexes>();
126 AU.addRequired<LiveIntervals>();
127 AU.addPreserved<LiveIntervals>();
Andrew Trick96f678f2012-01-13 06:30:30 +0000128 MachineFunctionPass::getAnalysisUsage(AU);
129}
130
Andrew Trick96f678f2012-01-13 06:30:30 +0000131MachinePassRegistry MachineSchedRegistry::Registry;
132
Andrew Trickd04ec0c2012-03-09 00:52:20 +0000133/// A dummy default scheduler factory indicates whether the scheduler
134/// is overridden on the command line.
135static ScheduleDAGInstrs *useDefaultMachineSched(MachineSchedContext *C) {
136 return 0;
137}
Andrew Trick96f678f2012-01-13 06:30:30 +0000138
139/// MachineSchedOpt allows command line selection of the scheduler.
140static cl::opt<MachineSchedRegistry::ScheduleDAGCtor, false,
141 RegisterPassParser<MachineSchedRegistry> >
142MachineSchedOpt("misched",
Andrew Trickd04ec0c2012-03-09 00:52:20 +0000143 cl::init(&useDefaultMachineSched), cl::Hidden,
Andrew Trick96f678f2012-01-13 06:30:30 +0000144 cl::desc("Machine instruction scheduler to use"));
145
Andrew Trickd04ec0c2012-03-09 00:52:20 +0000146static MachineSchedRegistry
Andrew Trick17d35e52012-03-14 04:00:41 +0000147DefaultSchedRegistry("default", "Use the target's default scheduler choice.",
Andrew Trickd04ec0c2012-03-09 00:52:20 +0000148 useDefaultMachineSched);
149
Andrew Trick17d35e52012-03-14 04:00:41 +0000150/// Forward declare the standard machine scheduler. This will be used as the
Andrew Trickd04ec0c2012-03-09 00:52:20 +0000151/// default scheduler if the target does not set a default.
Andrew Trick17d35e52012-03-14 04:00:41 +0000152static ScheduleDAGInstrs *createConvergingSched(MachineSchedContext *C);
Andrew Trickd04ec0c2012-03-09 00:52:20 +0000153
Andrew Trickeb45ebb2012-04-24 18:04:34 +0000154
155/// Decrement this iterator until reaching the top or a non-debug instr.
156static MachineBasicBlock::iterator
157priorNonDebug(MachineBasicBlock::iterator I, MachineBasicBlock::iterator Beg) {
158 assert(I != Beg && "reached the top of the region, cannot decrement");
159 while (--I != Beg) {
160 if (!I->isDebugValue())
161 break;
162 }
163 return I;
164}
165
166/// If this iterator is a debug value, increment until reaching the End or a
167/// non-debug instruction.
168static MachineBasicBlock::iterator
169nextIfDebug(MachineBasicBlock::iterator I, MachineBasicBlock::iterator End) {
Andrew Trick811d92682012-05-17 18:35:03 +0000170 for(; I != End; ++I) {
Andrew Trickeb45ebb2012-04-24 18:04:34 +0000171 if (!I->isDebugValue())
172 break;
173 }
174 return I;
175}
176
Andrew Trickcb058d52012-03-14 04:00:38 +0000177/// Top-level MachineScheduler pass driver.
178///
179/// Visit blocks in function order. Divide each block into scheduling regions
Andrew Trick17d35e52012-03-14 04:00:41 +0000180/// and visit them bottom-up. Visiting regions bottom-up is not required, but is
181/// consistent with the DAG builder, which traverses the interior of the
182/// scheduling regions bottom-up.
Andrew Trickcb058d52012-03-14 04:00:38 +0000183///
184/// This design avoids exposing scheduling boundaries to the DAG builder,
Andrew Trick17d35e52012-03-14 04:00:41 +0000185/// simplifying the DAG builder's support for "special" target instructions.
186/// At the same time the design allows target schedulers to operate across
Andrew Trickcb058d52012-03-14 04:00:38 +0000187/// scheduling boundaries, for example to bundle the boudary instructions
188/// without reordering them. This creates complexity, because the target
189/// scheduler must update the RegionBegin and RegionEnd positions cached by
190/// ScheduleDAGInstrs whenever adding or removing instructions. A much simpler
191/// design would be to split blocks at scheduling boundaries, but LLVM has a
192/// general bias against block splitting purely for implementation simplicity.
Andrew Trick42b7a712012-01-17 06:55:03 +0000193bool MachineScheduler::runOnMachineFunction(MachineFunction &mf) {
Andrew Trick89c324b2012-05-10 21:06:21 +0000194 DEBUG(dbgs() << "Before MISsched:\n"; mf.print(dbgs()));
195
Andrew Trick96f678f2012-01-13 06:30:30 +0000196 // Initialize the context of the pass.
197 MF = &mf;
198 MLI = &getAnalysis<MachineLoopInfo>();
199 MDT = &getAnalysis<MachineDominatorTree>();
Andrew Trickd04ec0c2012-03-09 00:52:20 +0000200 PassConfig = &getAnalysis<TargetPassConfig>();
Andrew Trickc174eaf2012-03-08 01:41:12 +0000201 AA = &getAnalysis<AliasAnalysis>();
202
Lang Hames907cc8f2012-01-27 22:36:19 +0000203 LIS = &getAnalysis<LiveIntervals>();
Andrew Trickc174eaf2012-03-08 01:41:12 +0000204 const TargetInstrInfo *TII = MF->getTarget().getInstrInfo();
Andrew Trick96f678f2012-01-13 06:30:30 +0000205
Andrew Trick86b7e2a2012-04-24 20:36:19 +0000206 RegClassInfo->runOnMachineFunction(*MF);
Andrew Trick006e1ab2012-04-24 17:56:43 +0000207
Andrew Trick96f678f2012-01-13 06:30:30 +0000208 // Select the scheduler, or set the default.
Andrew Trickd04ec0c2012-03-09 00:52:20 +0000209 MachineSchedRegistry::ScheduleDAGCtor Ctor = MachineSchedOpt;
210 if (Ctor == useDefaultMachineSched) {
211 // Get the default scheduler set by the target.
212 Ctor = MachineSchedRegistry::getDefault();
213 if (!Ctor) {
Andrew Trick17d35e52012-03-14 04:00:41 +0000214 Ctor = createConvergingSched;
Andrew Trickd04ec0c2012-03-09 00:52:20 +0000215 MachineSchedRegistry::setDefault(Ctor);
216 }
Andrew Trick96f678f2012-01-13 06:30:30 +0000217 }
218 // Instantiate the selected scheduler.
219 OwningPtr<ScheduleDAGInstrs> Scheduler(Ctor(this));
220
221 // Visit all machine basic blocks.
Andrew Trick006e1ab2012-04-24 17:56:43 +0000222 //
223 // TODO: Visit blocks in global postorder or postorder within the bottom-up
224 // loop tree. Then we can optionally compute global RegPressure.
Andrew Trick96f678f2012-01-13 06:30:30 +0000225 for (MachineFunction::iterator MBB = MF->begin(), MBBEnd = MF->end();
226 MBB != MBBEnd; ++MBB) {
227
Andrew Trick1fabd9f2012-03-09 08:02:51 +0000228 Scheduler->startBlock(MBB);
229
Andrew Tricke9ef4ed2012-01-14 02:17:09 +0000230 // Break the block into scheduling regions [I, RegionEnd), and schedule each
Sylvestre Ledruc8e41c52012-07-23 08:51:15 +0000231 // region as soon as it is discovered. RegionEnd points the scheduling
Andrew Trickfe4d6df2012-03-09 22:34:56 +0000232 // boundary at the bottom of the region. The DAG does not include RegionEnd,
233 // but the region does (i.e. the next RegionEnd is above the previous
234 // RegionBegin). If the current block has no terminator then RegionEnd ==
235 // MBB->end() for the bottom region.
236 //
237 // The Scheduler may insert instructions during either schedule() or
238 // exitRegion(), even for empty regions. So the local iterators 'I' and
239 // 'RegionEnd' are invalid across these calls.
Andrew Trick22764532012-11-06 07:10:34 +0000240 unsigned RemainingInstrs = MBB->size();
Andrew Trick7799eb42012-03-09 03:46:39 +0000241 for(MachineBasicBlock::iterator RegionEnd = MBB->end();
Andrew Trickfe4d6df2012-03-09 22:34:56 +0000242 RegionEnd != MBB->begin(); RegionEnd = Scheduler->begin()) {
Andrew Trick006e1ab2012-04-24 17:56:43 +0000243
Andrew Trick1fabd9f2012-03-09 08:02:51 +0000244 // Avoid decrementing RegionEnd for blocks with no terminator.
245 if (RegionEnd != MBB->end()
246 || TII->isSchedulingBoundary(llvm::prior(RegionEnd), MBB, *MF)) {
247 --RegionEnd;
248 // Count the boundary instruction.
Andrew Trick22764532012-11-06 07:10:34 +0000249 --RemainingInstrs;
Andrew Trick1fabd9f2012-03-09 08:02:51 +0000250 }
251
Andrew Tricke9ef4ed2012-01-14 02:17:09 +0000252 // The next region starts above the previous region. Look backward in the
253 // instruction stream until we find the nearest boundary.
254 MachineBasicBlock::iterator I = RegionEnd;
Andrew Trick22764532012-11-06 07:10:34 +0000255 for(;I != MBB->begin(); --I, --RemainingInstrs) {
Andrew Tricke9ef4ed2012-01-14 02:17:09 +0000256 if (TII->isSchedulingBoundary(llvm::prior(I), MBB, *MF))
257 break;
258 }
Andrew Trick47c14452012-03-07 05:21:52 +0000259 // Notify the scheduler of the region, even if we may skip scheduling
260 // it. Perhaps it still needs to be bundled.
Andrew Trick22764532012-11-06 07:10:34 +0000261 Scheduler->enterRegion(MBB, I, RegionEnd, RemainingInstrs);
Andrew Trick47c14452012-03-07 05:21:52 +0000262
263 // Skip empty scheduling regions (0 or 1 schedulable instructions).
264 if (I == RegionEnd || I == llvm::prior(RegionEnd)) {
Andrew Trick47c14452012-03-07 05:21:52 +0000265 // Close the current region. Bundle the terminator if needed.
Andrew Trickfe4d6df2012-03-09 22:34:56 +0000266 // This invalidates 'RegionEnd' and 'I'.
Andrew Trick47c14452012-03-07 05:21:52 +0000267 Scheduler->exitRegion();
Andrew Trickc6cf11b2012-01-17 06:55:07 +0000268 continue;
Andrew Trick3c58ba82012-01-14 02:17:18 +0000269 }
Andrew Trickbb0a2422012-05-24 22:11:14 +0000270 DEBUG(dbgs() << "********** MI Scheduling **********\n");
Craig Topper96601ca2012-08-22 06:07:19 +0000271 DEBUG(dbgs() << MF->getName()
Andrew Trick291411c2012-02-08 02:17:21 +0000272 << ":BB#" << MBB->getNumber() << "\n From: " << *I << " To: ";
273 if (RegionEnd != MBB->end()) dbgs() << *RegionEnd;
274 else dbgs() << "End";
Andrew Trick22764532012-11-06 07:10:34 +0000275 dbgs() << " Remaining: " << RemainingInstrs << "\n");
Andrew Trickc6cf11b2012-01-17 06:55:07 +0000276
Andrew Trickd24da972012-03-09 03:46:42 +0000277 // Schedule a region: possibly reorder instructions.
Andrew Trickfe4d6df2012-03-09 22:34:56 +0000278 // This invalidates 'RegionEnd' and 'I'.
Andrew Trick953be892012-03-07 23:00:49 +0000279 Scheduler->schedule();
Andrew Trickd24da972012-03-09 03:46:42 +0000280
281 // Close the current region.
Andrew Trick47c14452012-03-07 05:21:52 +0000282 Scheduler->exitRegion();
283
284 // Scheduling has invalidated the current iterator 'I'. Ask the
285 // scheduler for the top of it's scheduled region.
286 RegionEnd = Scheduler->begin();
Andrew Tricke9ef4ed2012-01-14 02:17:09 +0000287 }
Andrew Trick22764532012-11-06 07:10:34 +0000288 assert(RemainingInstrs == 0 && "Instruction count mismatch!");
Andrew Trick953be892012-03-07 23:00:49 +0000289 Scheduler->finishBlock();
Andrew Trick96f678f2012-01-13 06:30:30 +0000290 }
Andrew Trick830da402012-04-01 07:24:23 +0000291 Scheduler->finalizeSchedule();
Andrew Trickaad37f12012-03-21 04:12:12 +0000292 DEBUG(LIS->print(dbgs()));
Andrew Trick96f678f2012-01-13 06:30:30 +0000293 return true;
294}
295
Andrew Trick42b7a712012-01-17 06:55:03 +0000296void MachineScheduler::print(raw_ostream &O, const Module* m) const {
Andrew Trick96f678f2012-01-13 06:30:30 +0000297 // unimplemented
298}
299
Manman Renb720be62012-09-11 22:23:19 +0000300#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
Andrew Trick78e5efe2012-09-11 00:39:15 +0000301void ReadyQueue::dump() {
302 dbgs() << Name << ": ";
303 for (unsigned i = 0, e = Queue.size(); i < e; ++i)
304 dbgs() << Queue[i]->NodeNum << " ";
305 dbgs() << "\n";
306}
307#endif
Andrew Trick17d35e52012-03-14 04:00:41 +0000308
309//===----------------------------------------------------------------------===//
310// ScheduleDAGMI - Base class for MachineInstr scheduling with LiveIntervals
311// preservation.
312//===----------------------------------------------------------------------===//
313
Andrew Trick9b5caaa2012-11-12 19:40:10 +0000314bool ScheduleDAGMI::addEdge(SUnit *SuccSU, const SDep &PredDep) {
Andrew Trick6996fd02012-11-12 19:52:20 +0000315 if (SuccSU != &ExitSU) {
316 // Do not use WillCreateCycle, it assumes SD scheduling.
317 // If Pred is reachable from Succ, then the edge creates a cycle.
318 if (Topo.IsReachable(PredDep.getSUnit(), SuccSU))
319 return false;
320 Topo.AddPred(SuccSU, PredDep.getSUnit());
321 }
Andrew Trick9b5caaa2012-11-12 19:40:10 +0000322 SuccSU->addPred(PredDep, /*Required=*/!PredDep.isArtificial());
323 // Return true regardless of whether a new edge needed to be inserted.
324 return true;
325}
326
Andrew Trickc174eaf2012-03-08 01:41:12 +0000327/// ReleaseSucc - Decrement the NumPredsLeft count of a successor. When
328/// NumPredsLeft reaches zero, release the successor node.
Andrew Trick0a39d4e2012-05-24 22:11:09 +0000329///
330/// FIXME: Adjust SuccSU height based on MinLatency.
Andrew Trick17d35e52012-03-14 04:00:41 +0000331void ScheduleDAGMI::releaseSucc(SUnit *SU, SDep *SuccEdge) {
Andrew Trickc174eaf2012-03-08 01:41:12 +0000332 SUnit *SuccSU = SuccEdge->getSUnit();
333
Andrew Trickae692f22012-11-12 19:28:57 +0000334 if (SuccEdge->isWeak()) {
335 --SuccSU->WeakPredsLeft;
Andrew Trick9b5caaa2012-11-12 19:40:10 +0000336 if (SuccEdge->isCluster())
337 NextClusterSucc = SuccSU;
Andrew Trickae692f22012-11-12 19:28:57 +0000338 return;
339 }
Andrew Trickc174eaf2012-03-08 01:41:12 +0000340#ifndef NDEBUG
341 if (SuccSU->NumPredsLeft == 0) {
342 dbgs() << "*** Scheduling failed! ***\n";
343 SuccSU->dump(this);
344 dbgs() << " has been released too many times!\n";
345 llvm_unreachable(0);
346 }
347#endif
348 --SuccSU->NumPredsLeft;
349 if (SuccSU->NumPredsLeft == 0 && SuccSU != &ExitSU)
Andrew Trick17d35e52012-03-14 04:00:41 +0000350 SchedImpl->releaseTopNode(SuccSU);
Andrew Trickc174eaf2012-03-08 01:41:12 +0000351}
352
353/// releaseSuccessors - Call releaseSucc on each of SU's successors.
Andrew Trick17d35e52012-03-14 04:00:41 +0000354void ScheduleDAGMI::releaseSuccessors(SUnit *SU) {
Andrew Trickc174eaf2012-03-08 01:41:12 +0000355 for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
356 I != E; ++I) {
357 releaseSucc(SU, &*I);
358 }
359}
360
Andrew Trick17d35e52012-03-14 04:00:41 +0000361/// ReleasePred - Decrement the NumSuccsLeft count of a predecessor. When
362/// NumSuccsLeft reaches zero, release the predecessor node.
Andrew Trick0a39d4e2012-05-24 22:11:09 +0000363///
364/// FIXME: Adjust PredSU height based on MinLatency.
Andrew Trick17d35e52012-03-14 04:00:41 +0000365void ScheduleDAGMI::releasePred(SUnit *SU, SDep *PredEdge) {
366 SUnit *PredSU = PredEdge->getSUnit();
367
Andrew Trickae692f22012-11-12 19:28:57 +0000368 if (PredEdge->isWeak()) {
369 --PredSU->WeakSuccsLeft;
Andrew Trick9b5caaa2012-11-12 19:40:10 +0000370 if (PredEdge->isCluster())
371 NextClusterPred = PredSU;
Andrew Trickae692f22012-11-12 19:28:57 +0000372 return;
373 }
Andrew Trick17d35e52012-03-14 04:00:41 +0000374#ifndef NDEBUG
375 if (PredSU->NumSuccsLeft == 0) {
376 dbgs() << "*** Scheduling failed! ***\n";
377 PredSU->dump(this);
378 dbgs() << " has been released too many times!\n";
379 llvm_unreachable(0);
380 }
381#endif
382 --PredSU->NumSuccsLeft;
383 if (PredSU->NumSuccsLeft == 0 && PredSU != &EntrySU)
384 SchedImpl->releaseBottomNode(PredSU);
385}
386
387/// releasePredecessors - Call releasePred on each of SU's predecessors.
388void ScheduleDAGMI::releasePredecessors(SUnit *SU) {
389 for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
390 I != E; ++I) {
391 releasePred(SU, &*I);
392 }
393}
394
395void ScheduleDAGMI::moveInstruction(MachineInstr *MI,
396 MachineBasicBlock::iterator InsertPos) {
Andrew Trick811d92682012-05-17 18:35:03 +0000397 // Advance RegionBegin if the first instruction moves down.
Andrew Trick1ce062f2012-03-21 04:12:10 +0000398 if (&*RegionBegin == MI)
Andrew Trick811d92682012-05-17 18:35:03 +0000399 ++RegionBegin;
400
401 // Update the instruction stream.
Andrew Trick17d35e52012-03-14 04:00:41 +0000402 BB->splice(InsertPos, BB, MI);
Andrew Trick811d92682012-05-17 18:35:03 +0000403
404 // Update LiveIntervals
Andrew Trick27c28ce2012-10-16 00:22:51 +0000405 LIS->handleMove(MI, /*UpdateFlags=*/true);
Andrew Trick811d92682012-05-17 18:35:03 +0000406
407 // Recede RegionBegin if an instruction moves above the first.
Andrew Trick17d35e52012-03-14 04:00:41 +0000408 if (RegionBegin == InsertPos)
409 RegionBegin = MI;
410}
411
Andrew Trick0b0d8992012-03-21 04:12:07 +0000412bool ScheduleDAGMI::checkSchedLimit() {
413#ifndef NDEBUG
414 if (NumInstrsScheduled == MISchedCutoff && MISchedCutoff != ~0U) {
415 CurrentTop = CurrentBottom;
416 return false;
417 }
418 ++NumInstrsScheduled;
419#endif
420 return true;
421}
422
Andrew Trick006e1ab2012-04-24 17:56:43 +0000423/// enterRegion - Called back from MachineScheduler::runOnMachineFunction after
424/// crossing a scheduling boundary. [begin, end) includes all instructions in
425/// the region, including the boundary itself and single-instruction regions
426/// that don't get scheduled.
427void ScheduleDAGMI::enterRegion(MachineBasicBlock *bb,
428 MachineBasicBlock::iterator begin,
429 MachineBasicBlock::iterator end,
430 unsigned endcount)
431{
432 ScheduleDAGInstrs::enterRegion(bb, begin, end, endcount);
Andrew Trick7f8ab782012-05-10 21:06:10 +0000433
434 // For convenience remember the end of the liveness region.
435 LiveRegionEnd =
436 (RegionEnd == bb->end()) ? RegionEnd : llvm::next(RegionEnd);
437}
438
439// Setup the register pressure trackers for the top scheduled top and bottom
440// scheduled regions.
441void ScheduleDAGMI::initRegPressure() {
442 TopRPTracker.init(&MF, RegClassInfo, LIS, BB, RegionBegin);
443 BotRPTracker.init(&MF, RegClassInfo, LIS, BB, LiveRegionEnd);
444
445 // Close the RPTracker to finalize live ins.
446 RPTracker.closeRegion();
447
Andrew Trickbb0a2422012-05-24 22:11:14 +0000448 DEBUG(RPTracker.getPressure().dump(TRI));
449
Andrew Trick7f8ab782012-05-10 21:06:10 +0000450 // Initialize the live ins and live outs.
451 TopRPTracker.addLiveRegs(RPTracker.getPressure().LiveInRegs);
452 BotRPTracker.addLiveRegs(RPTracker.getPressure().LiveOutRegs);
453
454 // Close one end of the tracker so we can call
455 // getMaxUpward/DownwardPressureDelta before advancing across any
456 // instructions. This converts currently live regs into live ins/outs.
457 TopRPTracker.closeTop();
458 BotRPTracker.closeBottom();
459
460 // Account for liveness generated by the region boundary.
461 if (LiveRegionEnd != RegionEnd)
462 BotRPTracker.recede();
463
464 assert(BotRPTracker.getPos() == RegionEnd && "Can't find the region bottom");
Andrew Trick73a0d8e2012-05-17 18:35:10 +0000465
466 // Cache the list of excess pressure sets in this region. This will also track
467 // the max pressure in the scheduled code for these sets.
468 RegionCriticalPSets.clear();
469 std::vector<unsigned> RegionPressure = RPTracker.getPressure().MaxSetPressure;
470 for (unsigned i = 0, e = RegionPressure.size(); i < e; ++i) {
471 unsigned Limit = TRI->getRegPressureSetLimit(i);
Andrew Trick78e5efe2012-09-11 00:39:15 +0000472 DEBUG(dbgs() << TRI->getRegPressureSetName(i)
473 << "Limit " << Limit
474 << " Actual " << RegionPressure[i] << "\n");
Andrew Trick73a0d8e2012-05-17 18:35:10 +0000475 if (RegionPressure[i] > Limit)
476 RegionCriticalPSets.push_back(PressureElement(i, 0));
477 }
478 DEBUG(dbgs() << "Excess PSets: ";
479 for (unsigned i = 0, e = RegionCriticalPSets.size(); i != e; ++i)
480 dbgs() << TRI->getRegPressureSetName(
481 RegionCriticalPSets[i].PSetID) << " ";
482 dbgs() << "\n");
483}
484
485// FIXME: When the pressure tracker deals in pressure differences then we won't
486// iterate over all RegionCriticalPSets[i].
487void ScheduleDAGMI::
488updateScheduledPressure(std::vector<unsigned> NewMaxPressure) {
489 for (unsigned i = 0, e = RegionCriticalPSets.size(); i < e; ++i) {
490 unsigned ID = RegionCriticalPSets[i].PSetID;
491 int &MaxUnits = RegionCriticalPSets[i].UnitIncrease;
492 if ((int)NewMaxPressure[ID] > MaxUnits)
493 MaxUnits = NewMaxPressure[ID];
494 }
Andrew Trick006e1ab2012-04-24 17:56:43 +0000495}
496
Andrew Trick17d35e52012-03-14 04:00:41 +0000497/// schedule - Called back from MachineScheduler::runOnMachineFunction
Andrew Trick006e1ab2012-04-24 17:56:43 +0000498/// after setting up the current scheduling region. [RegionBegin, RegionEnd)
499/// only includes instructions that have DAG nodes, not scheduling boundaries.
Andrew Trick78e5efe2012-09-11 00:39:15 +0000500///
501/// This is a skeletal driver, with all the functionality pushed into helpers,
502/// so that it can be easilly extended by experimental schedulers. Generally,
503/// implementing MachineSchedStrategy should be sufficient to implement a new
504/// scheduling algorithm. However, if a scheduler further subclasses
505/// ScheduleDAGMI then it will want to override this virtual method in order to
506/// update any specialized state.
Andrew Trick17d35e52012-03-14 04:00:41 +0000507void ScheduleDAGMI::schedule() {
Andrew Trick78e5efe2012-09-11 00:39:15 +0000508 buildDAGWithRegPressure();
509
Andrew Trick9b5caaa2012-11-12 19:40:10 +0000510 Topo.InitDAGTopologicalSorting();
511
Andrew Trickd039b382012-09-14 17:22:42 +0000512 postprocessDAG();
513
Andrew Trick78e5efe2012-09-11 00:39:15 +0000514 DEBUG(for (unsigned su = 0, e = SUnits.size(); su != e; ++su)
515 SUnits[su].dumpAll(this));
516
517 if (ViewMISchedDAGs) viewGraph();
518
519 initQueues();
520
521 bool IsTopNode = false;
522 while (SUnit *SU = SchedImpl->pickNode(IsTopNode)) {
Andrew Trick30c6ec22012-10-08 18:53:53 +0000523 assert(!SU->isScheduled && "Node already scheduled");
Andrew Trick78e5efe2012-09-11 00:39:15 +0000524 if (!checkSchedLimit())
525 break;
526
527 scheduleMI(SU, IsTopNode);
528
529 updateQueues(SU, IsTopNode);
530 }
531 assert(CurrentTop == CurrentBottom && "Nonempty unscheduled zone.");
532
533 placeDebugValues();
Andrew Trick3b87f622012-11-07 07:05:09 +0000534
535 DEBUG({
536 unsigned BBNum = top()->getParent()->getNumber();
537 dbgs() << "*** Final schedule for BB#" << BBNum << " ***\n";
538 dumpSchedule();
539 dbgs() << '\n';
540 });
Andrew Trick78e5efe2012-09-11 00:39:15 +0000541}
542
543/// Build the DAG and setup three register pressure trackers.
544void ScheduleDAGMI::buildDAGWithRegPressure() {
Andrew Trick7f8ab782012-05-10 21:06:10 +0000545 // Initialize the register pressure tracker used by buildSchedGraph.
546 RPTracker.init(&MF, RegClassInfo, LIS, BB, LiveRegionEnd);
Andrew Trick006e1ab2012-04-24 17:56:43 +0000547
Andrew Trick7f8ab782012-05-10 21:06:10 +0000548 // Account for liveness generate by the region boundary.
549 if (LiveRegionEnd != RegionEnd)
550 RPTracker.recede();
551
552 // Build the DAG, and compute current register pressure.
Andrew Trick006e1ab2012-04-24 17:56:43 +0000553 buildSchedGraph(AA, &RPTracker);
Andrew Trick78e5efe2012-09-11 00:39:15 +0000554 if (ViewMISchedDAGs) viewGraph();
Andrew Trickc174eaf2012-03-08 01:41:12 +0000555
Andrew Trick7f8ab782012-05-10 21:06:10 +0000556 // Initialize top/bottom trackers after computing region pressure.
557 initRegPressure();
Andrew Trick78e5efe2012-09-11 00:39:15 +0000558}
Andrew Trick7f8ab782012-05-10 21:06:10 +0000559
Andrew Trickd039b382012-09-14 17:22:42 +0000560/// Apply each ScheduleDAGMutation step in order.
561void ScheduleDAGMI::postprocessDAG() {
562 for (unsigned i = 0, e = Mutations.size(); i < e; ++i) {
563 Mutations[i]->apply(this);
564 }
565}
566
Andrew Trick1e94e982012-10-15 18:02:27 +0000567// Release all DAG roots for scheduling.
Andrew Trickae692f22012-11-12 19:28:57 +0000568//
569// Nodes with unreleased weak edges can still be roots.
Andrew Trick1e94e982012-10-15 18:02:27 +0000570void ScheduleDAGMI::releaseRoots() {
571 SmallVector<SUnit*, 16> BotRoots;
572
573 for (std::vector<SUnit>::iterator
574 I = SUnits.begin(), E = SUnits.end(); I != E; ++I) {
Andrew Trickae692f22012-11-12 19:28:57 +0000575 SUnit *SU = &(*I);
Andrew Trick1e94e982012-10-15 18:02:27 +0000576 // A SUnit is ready to top schedule if it has no predecessors.
Andrew Trickae692f22012-11-12 19:28:57 +0000577 if (!I->NumPredsLeft && SU != &EntrySU)
578 SchedImpl->releaseTopNode(SU);
Andrew Trick1e94e982012-10-15 18:02:27 +0000579 // A SUnit is ready to bottom schedule if it has no successors.
Andrew Trickae692f22012-11-12 19:28:57 +0000580 if (!I->NumSuccsLeft && SU != &ExitSU)
581 BotRoots.push_back(SU);
Andrew Trick1e94e982012-10-15 18:02:27 +0000582 }
583 // Release bottom roots in reverse order so the higher priority nodes appear
584 // first. This is more natural and slightly more efficient.
585 for (SmallVectorImpl<SUnit*>::const_reverse_iterator
586 I = BotRoots.rbegin(), E = BotRoots.rend(); I != E; ++I)
587 SchedImpl->releaseBottomNode(*I);
588}
589
Andrew Trick78e5efe2012-09-11 00:39:15 +0000590/// Identify DAG roots and setup scheduler queues.
591void ScheduleDAGMI::initQueues() {
Andrew Trick9b5caaa2012-11-12 19:40:10 +0000592 NextClusterSucc = NULL;
593 NextClusterPred = NULL;
Andrew Trick1e94e982012-10-15 18:02:27 +0000594
Andrew Trick78e5efe2012-09-11 00:39:15 +0000595 // Initialize the strategy before modifying the DAG.
Andrew Trick17d35e52012-03-14 04:00:41 +0000596 SchedImpl->initialize(this);
597
Andrew Trickae692f22012-11-12 19:28:57 +0000598 // Release all DAG roots for scheduling, not including EntrySU/ExitSU.
599 releaseRoots();
600
Andrew Trickc174eaf2012-03-08 01:41:12 +0000601 releaseSuccessors(&EntrySU);
Andrew Trick17d35e52012-03-14 04:00:41 +0000602 releasePredecessors(&ExitSU);
Andrew Trickc174eaf2012-03-08 01:41:12 +0000603
Andrew Trick1e94e982012-10-15 18:02:27 +0000604 SchedImpl->registerRoots();
605
Andrew Trickeb45ebb2012-04-24 18:04:34 +0000606 CurrentTop = nextIfDebug(RegionBegin, RegionEnd);
Andrew Trick17d35e52012-03-14 04:00:41 +0000607 CurrentBottom = RegionEnd;
Andrew Trick78e5efe2012-09-11 00:39:15 +0000608}
Andrew Trickc174eaf2012-03-08 01:41:12 +0000609
Andrew Trick78e5efe2012-09-11 00:39:15 +0000610/// Move an instruction and update register pressure.
611void ScheduleDAGMI::scheduleMI(SUnit *SU, bool IsTopNode) {
612 // Move the instruction to its new location in the instruction stream.
613 MachineInstr *MI = SU->getInstr();
Andrew Trickc174eaf2012-03-08 01:41:12 +0000614
Andrew Trick78e5efe2012-09-11 00:39:15 +0000615 if (IsTopNode) {
616 assert(SU->isTopReady() && "node still has unscheduled dependencies");
617 if (&*CurrentTop == MI)
618 CurrentTop = nextIfDebug(++CurrentTop, CurrentBottom);
Andrew Trick17d35e52012-03-14 04:00:41 +0000619 else {
Andrew Trick78e5efe2012-09-11 00:39:15 +0000620 moveInstruction(MI, CurrentTop);
621 TopRPTracker.setPos(MI);
Andrew Trick17d35e52012-03-14 04:00:41 +0000622 }
Andrew Trick000b2502012-04-24 18:04:37 +0000623
Andrew Trick78e5efe2012-09-11 00:39:15 +0000624 // Update top scheduled pressure.
625 TopRPTracker.advance();
626 assert(TopRPTracker.getPos() == CurrentTop && "out of sync");
627 updateScheduledPressure(TopRPTracker.getPressure().MaxSetPressure);
628 }
629 else {
630 assert(SU->isBottomReady() && "node still has unscheduled dependencies");
631 MachineBasicBlock::iterator priorII =
632 priorNonDebug(CurrentBottom, CurrentTop);
633 if (&*priorII == MI)
634 CurrentBottom = priorII;
635 else {
636 if (&*CurrentTop == MI) {
637 CurrentTop = nextIfDebug(++CurrentTop, priorII);
638 TopRPTracker.setPos(CurrentTop);
639 }
640 moveInstruction(MI, CurrentBottom);
641 CurrentBottom = MI;
642 }
643 // Update bottom scheduled pressure.
644 BotRPTracker.recede();
645 assert(BotRPTracker.getPos() == CurrentBottom && "out of sync");
646 updateScheduledPressure(BotRPTracker.getPressure().MaxSetPressure);
647 }
648}
649
650/// Update scheduler queues after scheduling an instruction.
651void ScheduleDAGMI::updateQueues(SUnit *SU, bool IsTopNode) {
652 // Release dependent instructions for scheduling.
653 if (IsTopNode)
654 releaseSuccessors(SU);
655 else
656 releasePredecessors(SU);
657
658 SU->isScheduled = true;
659
660 // Notify the scheduling strategy after updating the DAG.
661 SchedImpl->schedNode(SU, IsTopNode);
Andrew Trick000b2502012-04-24 18:04:37 +0000662}
663
664/// Reinsert any remaining debug_values, just like the PostRA scheduler.
665void ScheduleDAGMI::placeDebugValues() {
666 // If first instruction was a DBG_VALUE then put it back.
667 if (FirstDbgValue) {
668 BB->splice(RegionBegin, BB, FirstDbgValue);
669 RegionBegin = FirstDbgValue;
670 }
671
672 for (std::vector<std::pair<MachineInstr *, MachineInstr *> >::iterator
673 DI = DbgValues.end(), DE = DbgValues.begin(); DI != DE; --DI) {
674 std::pair<MachineInstr *, MachineInstr *> P = *prior(DI);
675 MachineInstr *DbgValue = P.first;
676 MachineBasicBlock::iterator OrigPrevMI = P.second;
677 BB->splice(++OrigPrevMI, BB, DbgValue);
678 if (OrigPrevMI == llvm::prior(RegionEnd))
679 RegionEnd = DbgValue;
680 }
681 DbgValues.clear();
682 FirstDbgValue = NULL;
Andrew Trickc174eaf2012-03-08 01:41:12 +0000683}
684
Andrew Trick3b87f622012-11-07 07:05:09 +0000685#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
686void ScheduleDAGMI::dumpSchedule() const {
687 for (MachineBasicBlock::iterator MI = begin(), ME = end(); MI != ME; ++MI) {
688 if (SUnit *SU = getSUnit(&(*MI)))
689 SU->dump(this);
690 else
691 dbgs() << "Missing SUnit\n";
692 }
693}
694#endif
695
Andrew Trick6996fd02012-11-12 19:52:20 +0000696//===----------------------------------------------------------------------===//
697// LoadClusterMutation - DAG post-processing to cluster loads.
698//===----------------------------------------------------------------------===//
699
Andrew Trick9b5caaa2012-11-12 19:40:10 +0000700namespace {
701/// \brief Post-process the DAG to create cluster edges between neighboring
702/// loads.
703class LoadClusterMutation : public ScheduleDAGMutation {
704 struct LoadInfo {
705 SUnit *SU;
706 unsigned BaseReg;
707 unsigned Offset;
708 LoadInfo(SUnit *su, unsigned reg, unsigned ofs)
709 : SU(su), BaseReg(reg), Offset(ofs) {}
710 };
711 static bool LoadInfoLess(const LoadClusterMutation::LoadInfo &LHS,
712 const LoadClusterMutation::LoadInfo &RHS);
713
714 const TargetInstrInfo *TII;
715 const TargetRegisterInfo *TRI;
716public:
717 LoadClusterMutation(const TargetInstrInfo *tii,
718 const TargetRegisterInfo *tri)
719 : TII(tii), TRI(tri) {}
720
721 virtual void apply(ScheduleDAGMI *DAG);
722protected:
723 void clusterNeighboringLoads(ArrayRef<SUnit*> Loads, ScheduleDAGMI *DAG);
724};
725} // anonymous
726
727bool LoadClusterMutation::LoadInfoLess(
728 const LoadClusterMutation::LoadInfo &LHS,
729 const LoadClusterMutation::LoadInfo &RHS) {
730 if (LHS.BaseReg != RHS.BaseReg)
731 return LHS.BaseReg < RHS.BaseReg;
732 return LHS.Offset < RHS.Offset;
733}
734
735void LoadClusterMutation::clusterNeighboringLoads(ArrayRef<SUnit*> Loads,
736 ScheduleDAGMI *DAG) {
737 SmallVector<LoadClusterMutation::LoadInfo,32> LoadRecords;
738 for (unsigned Idx = 0, End = Loads.size(); Idx != End; ++Idx) {
739 SUnit *SU = Loads[Idx];
740 unsigned BaseReg;
741 unsigned Offset;
742 if (TII->getLdStBaseRegImmOfs(SU->getInstr(), BaseReg, Offset, TRI))
743 LoadRecords.push_back(LoadInfo(SU, BaseReg, Offset));
744 }
745 if (LoadRecords.size() < 2)
746 return;
747 std::sort(LoadRecords.begin(), LoadRecords.end(), LoadInfoLess);
748 unsigned ClusterLength = 1;
749 for (unsigned Idx = 0, End = LoadRecords.size(); Idx < (End - 1); ++Idx) {
750 if (LoadRecords[Idx].BaseReg != LoadRecords[Idx+1].BaseReg) {
751 ClusterLength = 1;
752 continue;
753 }
754
755 SUnit *SUa = LoadRecords[Idx].SU;
756 SUnit *SUb = LoadRecords[Idx+1].SU;
757 if (TII->shouldScheduleLoadsNear(SUa->getInstr(), SUb->getInstr(),
758 ClusterLength)
759 && DAG->addEdge(SUb, SDep(SUa, SDep::Cluster))) {
760
761 DEBUG(dbgs() << "Cluster loads SU(" << SUa->NodeNum << ") - SU("
762 << SUb->NodeNum << ")\n");
763 // Copy successor edges from SUa to SUb. Interleaving computation
764 // dependent on SUa can prevent load combining due to register reuse.
765 // Predecessor edges do not need to be copied from SUb to SUa since nearby
766 // loads should have effectively the same inputs.
767 for (SUnit::const_succ_iterator
768 SI = SUa->Succs.begin(), SE = SUa->Succs.end(); SI != SE; ++SI) {
769 if (SI->getSUnit() == SUb)
770 continue;
771 DEBUG(dbgs() << " Copy Succ SU(" << SI->getSUnit()->NodeNum << ")\n");
772 DAG->addEdge(SI->getSUnit(), SDep(SUb, SDep::Artificial));
773 }
774 ++ClusterLength;
775 }
776 else
777 ClusterLength = 1;
778 }
779}
780
781/// \brief Callback from DAG postProcessing to create cluster edges for loads.
782void LoadClusterMutation::apply(ScheduleDAGMI *DAG) {
783 // Map DAG NodeNum to store chain ID.
784 DenseMap<unsigned, unsigned> StoreChainIDs;
785 // Map each store chain to a set of dependent loads.
786 SmallVector<SmallVector<SUnit*,4>, 32> StoreChainDependents;
787 for (unsigned Idx = 0, End = DAG->SUnits.size(); Idx != End; ++Idx) {
788 SUnit *SU = &DAG->SUnits[Idx];
789 if (!SU->getInstr()->mayLoad())
790 continue;
791 unsigned ChainPredID = DAG->SUnits.size();
792 for (SUnit::const_pred_iterator
793 PI = SU->Preds.begin(), PE = SU->Preds.end(); PI != PE; ++PI) {
794 if (PI->isCtrl()) {
795 ChainPredID = PI->getSUnit()->NodeNum;
796 break;
797 }
798 }
799 // Check if this chain-like pred has been seen
800 // before. ChainPredID==MaxNodeID for loads at the top of the schedule.
801 unsigned NumChains = StoreChainDependents.size();
802 std::pair<DenseMap<unsigned, unsigned>::iterator, bool> Result =
803 StoreChainIDs.insert(std::make_pair(ChainPredID, NumChains));
804 if (Result.second)
805 StoreChainDependents.resize(NumChains + 1);
806 StoreChainDependents[Result.first->second].push_back(SU);
807 }
808 // Iterate over the store chains.
809 for (unsigned Idx = 0, End = StoreChainDependents.size(); Idx != End; ++Idx)
810 clusterNeighboringLoads(StoreChainDependents[Idx], DAG);
811}
812
Andrew Trickc174eaf2012-03-08 01:41:12 +0000813//===----------------------------------------------------------------------===//
Andrew Trick6996fd02012-11-12 19:52:20 +0000814// MacroFusion - DAG post-processing to encourage fusion of macro ops.
815//===----------------------------------------------------------------------===//
816
817namespace {
818/// \brief Post-process the DAG to create cluster edges between instructions
819/// that may be fused by the processor into a single operation.
820class MacroFusion : public ScheduleDAGMutation {
821 const TargetInstrInfo *TII;
822public:
823 MacroFusion(const TargetInstrInfo *tii): TII(tii) {}
824
825 virtual void apply(ScheduleDAGMI *DAG);
826};
827} // anonymous
828
829/// \brief Callback from DAG postProcessing to create cluster edges to encourage
830/// fused operations.
831void MacroFusion::apply(ScheduleDAGMI *DAG) {
832 // For now, assume targets can only fuse with the branch.
833 MachineInstr *Branch = DAG->ExitSU.getInstr();
834 if (!Branch)
835 return;
836
837 for (unsigned Idx = DAG->SUnits.size(); Idx > 0;) {
838 SUnit *SU = &DAG->SUnits[--Idx];
839 if (!TII->shouldScheduleAdjacent(SU->getInstr(), Branch))
840 continue;
841
842 // Create a single weak edge from SU to ExitSU. The only effect is to cause
843 // bottom-up scheduling to heavily prioritize the clustered SU. There is no
844 // need to copy predecessor edges from ExitSU to SU, since top-down
845 // scheduling cannot prioritize ExitSU anyway. To defer top-down scheduling
846 // of SU, we could create an artificial edge from the deepest root, but it
847 // hasn't been needed yet.
848 bool Success = DAG->addEdge(&DAG->ExitSU, SDep(SU, SDep::Cluster));
849 (void)Success;
850 assert(Success && "No DAG nodes should be reachable from ExitSU");
851
852 DEBUG(dbgs() << "Macro Fuse SU(" << SU->NodeNum << ")\n");
853 break;
854 }
855}
856
857//===----------------------------------------------------------------------===//
Andrew Trick17d35e52012-03-14 04:00:41 +0000858// ConvergingScheduler - Implementation of the standard MachineSchedStrategy.
Andrew Trick42b7a712012-01-17 06:55:03 +0000859//===----------------------------------------------------------------------===//
860
861namespace {
Andrew Trick17d35e52012-03-14 04:00:41 +0000862/// ConvergingScheduler shrinks the unscheduled zone using heuristics to balance
863/// the schedule.
864class ConvergingScheduler : public MachineSchedStrategy {
Andrew Trick3b87f622012-11-07 07:05:09 +0000865public:
866 /// Represent the type of SchedCandidate found within a single queue.
867 /// pickNodeBidirectional depends on these listed by decreasing priority.
868 enum CandReason {
Andrew Trick9b5caaa2012-11-12 19:40:10 +0000869 NoCand, SingleExcess, SingleCritical, Cluster,
870 ResourceReduce, ResourceDemand, BotHeightReduce, BotPathReduce,
871 TopDepthReduce, TopPathReduce, SingleMax, MultiPressure, NextDefUse,
872 NodeOrder};
Andrew Trick3b87f622012-11-07 07:05:09 +0000873
874#ifndef NDEBUG
875 static const char *getReasonStr(ConvergingScheduler::CandReason Reason);
876#endif
877
878 /// Policy for scheduling the next instruction in the candidate's zone.
879 struct CandPolicy {
880 bool ReduceLatency;
881 unsigned ReduceResIdx;
882 unsigned DemandResIdx;
883
884 CandPolicy(): ReduceLatency(false), ReduceResIdx(0), DemandResIdx(0) {}
885 };
886
887 /// Status of an instruction's critical resource consumption.
888 struct SchedResourceDelta {
889 // Count critical resources in the scheduled region required by SU.
890 unsigned CritResources;
891
892 // Count critical resources from another region consumed by SU.
893 unsigned DemandedResources;
894
895 SchedResourceDelta(): CritResources(0), DemandedResources(0) {}
896
897 bool operator==(const SchedResourceDelta &RHS) const {
898 return CritResources == RHS.CritResources
899 && DemandedResources == RHS.DemandedResources;
900 }
901 bool operator!=(const SchedResourceDelta &RHS) const {
902 return !operator==(RHS);
903 }
904 };
Andrew Trick7196a8f2012-05-10 21:06:16 +0000905
906 /// Store the state used by ConvergingScheduler heuristics, required for the
907 /// lifetime of one invocation of pickNode().
908 struct SchedCandidate {
Andrew Trick3b87f622012-11-07 07:05:09 +0000909 CandPolicy Policy;
910
Andrew Trick7196a8f2012-05-10 21:06:16 +0000911 // The best SUnit candidate.
912 SUnit *SU;
913
Andrew Trick3b87f622012-11-07 07:05:09 +0000914 // The reason for this candidate.
915 CandReason Reason;
916
Andrew Trick7196a8f2012-05-10 21:06:16 +0000917 // Register pressure values for the best candidate.
918 RegPressureDelta RPDelta;
919
Andrew Trick3b87f622012-11-07 07:05:09 +0000920 // Critical resource consumption of the best candidate.
921 SchedResourceDelta ResDelta;
922
923 SchedCandidate(const CandPolicy &policy)
924 : Policy(policy), SU(NULL), Reason(NoCand) {}
925
926 bool isValid() const { return SU; }
927
928 // Copy the status of another candidate without changing policy.
929 void setBest(SchedCandidate &Best) {
930 assert(Best.Reason != NoCand && "uninitialized Sched candidate");
931 SU = Best.SU;
932 Reason = Best.Reason;
933 RPDelta = Best.RPDelta;
934 ResDelta = Best.ResDelta;
935 }
936
937 void initResourceDelta(const ScheduleDAGMI *DAG,
938 const TargetSchedModel *SchedModel);
Andrew Trick7196a8f2012-05-10 21:06:16 +0000939 };
Andrew Trick3b87f622012-11-07 07:05:09 +0000940
941 /// Summarize the unscheduled region.
942 struct SchedRemainder {
943 // Critical path through the DAG in expected latency.
944 unsigned CriticalPath;
945
946 // Unscheduled resources
947 SmallVector<unsigned, 16> RemainingCounts;
948 // Critical resource for the unscheduled zone.
949 unsigned CritResIdx;
950 // Number of micro-ops left to schedule.
951 unsigned RemainingMicroOps;
952 // Is the unscheduled zone resource limited.
953 bool IsResourceLimited;
954
955 unsigned MaxRemainingCount;
956
957 void reset() {
958 CriticalPath = 0;
959 RemainingCounts.clear();
960 CritResIdx = 0;
961 RemainingMicroOps = 0;
962 IsResourceLimited = false;
963 MaxRemainingCount = 0;
964 }
965
966 SchedRemainder() { reset(); }
967
968 void init(ScheduleDAGMI *DAG, const TargetSchedModel *SchedModel);
969 };
Andrew Trick7196a8f2012-05-10 21:06:16 +0000970
Andrew Trickf3234242012-05-24 22:11:12 +0000971 /// Each Scheduling boundary is associated with ready queues. It tracks the
Andrew Trick3b87f622012-11-07 07:05:09 +0000972 /// current cycle in the direction of movement, and maintains the state
Andrew Trickf3234242012-05-24 22:11:12 +0000973 /// of "hazards" and other interlocks at the current cycle.
Andrew Trick0a39d4e2012-05-24 22:11:09 +0000974 struct SchedBoundary {
Andrew Trick7f8c74c2012-06-29 03:23:22 +0000975 ScheduleDAGMI *DAG;
Andrew Trick412cd2f2012-10-10 05:43:09 +0000976 const TargetSchedModel *SchedModel;
Andrew Trick3b87f622012-11-07 07:05:09 +0000977 SchedRemainder *Rem;
Andrew Trick7f8c74c2012-06-29 03:23:22 +0000978
Andrew Trick0a39d4e2012-05-24 22:11:09 +0000979 ReadyQueue Available;
980 ReadyQueue Pending;
981 bool CheckPending;
982
Andrew Trick3b87f622012-11-07 07:05:09 +0000983 // For heuristics, keep a list of the nodes that immediately depend on the
984 // most recently scheduled node.
985 SmallPtrSet<const SUnit*, 8> NextSUs;
986
Andrew Trick0a39d4e2012-05-24 22:11:09 +0000987 ScheduleHazardRecognizer *HazardRec;
988
989 unsigned CurrCycle;
990 unsigned IssueCount;
991
992 /// MinReadyCycle - Cycle of the soonest available instruction.
993 unsigned MinReadyCycle;
994
Andrew Trick3b87f622012-11-07 07:05:09 +0000995 // The expected latency of the critical path in this scheduled zone.
996 unsigned ExpectedLatency;
997
998 // Resources used in the scheduled zone beyond this boundary.
999 SmallVector<unsigned, 16> ResourceCounts;
1000
1001 // Cache the critical resources ID in this scheduled zone.
1002 unsigned CritResIdx;
1003
1004 // Is the scheduled region resource limited vs. latency limited.
1005 bool IsResourceLimited;
1006
1007 unsigned ExpectedCount;
1008
1009 // Policy flag: attempt to find ILP until expected latency is covered.
1010 bool ShouldIncreaseILP;
1011
1012#ifndef NDEBUG
Andrew Trickb7e02892012-06-05 21:11:27 +00001013 // Remember the greatest min operand latency.
1014 unsigned MaxMinLatency;
Andrew Trick3b87f622012-11-07 07:05:09 +00001015#endif
1016
1017 void reset() {
1018 Available.clear();
1019 Pending.clear();
1020 CheckPending = false;
1021 NextSUs.clear();
1022 HazardRec = 0;
1023 CurrCycle = 0;
1024 IssueCount = 0;
1025 MinReadyCycle = UINT_MAX;
1026 ExpectedLatency = 0;
1027 ResourceCounts.resize(1);
1028 assert(!ResourceCounts[0] && "nonzero count for bad resource");
1029 CritResIdx = 0;
1030 IsResourceLimited = false;
1031 ExpectedCount = 0;
1032 ShouldIncreaseILP = false;
1033#ifndef NDEBUG
1034 MaxMinLatency = 0;
1035#endif
1036 // Reserve a zero-count for invalid CritResIdx.
1037 ResourceCounts.resize(1);
1038 }
Andrew Trickb7e02892012-06-05 21:11:27 +00001039
Andrew Trickf3234242012-05-24 22:11:12 +00001040 /// Pending queues extend the ready queues with the same ID and the
1041 /// PendingFlag set.
1042 SchedBoundary(unsigned ID, const Twine &Name):
Andrew Trick3b87f622012-11-07 07:05:09 +00001043 DAG(0), SchedModel(0), Rem(0), Available(ID, Name+".A"),
1044 Pending(ID << ConvergingScheduler::LogMaxQID, Name+".P") {
1045 reset();
1046 }
Andrew Trick0a39d4e2012-05-24 22:11:09 +00001047
1048 ~SchedBoundary() { delete HazardRec; }
1049
Andrew Trick3b87f622012-11-07 07:05:09 +00001050 void init(ScheduleDAGMI *dag, const TargetSchedModel *smodel,
1051 SchedRemainder *rem);
Andrew Trick412cd2f2012-10-10 05:43:09 +00001052
Andrew Trickf3234242012-05-24 22:11:12 +00001053 bool isTop() const {
1054 return Available.getID() == ConvergingScheduler::TopQID;
1055 }
Andrew Trick0a39d4e2012-05-24 22:11:09 +00001056
Andrew Trick3b87f622012-11-07 07:05:09 +00001057 unsigned getUnscheduledLatency(SUnit *SU) const {
1058 if (isTop())
1059 return SU->getHeight();
1060 return SU->getDepth();
1061 }
1062
1063 unsigned getCriticalCount() const {
1064 return ResourceCounts[CritResIdx];
1065 }
1066
Andrew Trick5559ffa2012-06-29 03:23:24 +00001067 bool checkHazard(SUnit *SU);
1068
Andrew Trick3b87f622012-11-07 07:05:09 +00001069 void checkILPPolicy();
1070
Andrew Trick0a39d4e2012-05-24 22:11:09 +00001071 void releaseNode(SUnit *SU, unsigned ReadyCycle);
1072
1073 void bumpCycle();
1074
Andrew Trick3b87f622012-11-07 07:05:09 +00001075 void countResource(unsigned PIdx, unsigned Cycles);
1076
Andrew Trick7f8c74c2012-06-29 03:23:22 +00001077 void bumpNode(SUnit *SU);
Andrew Trickb7e02892012-06-05 21:11:27 +00001078
Andrew Trick0a39d4e2012-05-24 22:11:09 +00001079 void releasePending();
1080
1081 void removeReady(SUnit *SU);
1082
1083 SUnit *pickOnlyChoice();
1084 };
1085
Andrew Trick3b87f622012-11-07 07:05:09 +00001086private:
Andrew Trick17d35e52012-03-14 04:00:41 +00001087 ScheduleDAGMI *DAG;
Andrew Trick412cd2f2012-10-10 05:43:09 +00001088 const TargetSchedModel *SchedModel;
Andrew Trick7196a8f2012-05-10 21:06:16 +00001089 const TargetRegisterInfo *TRI;
Andrew Trick42b7a712012-01-17 06:55:03 +00001090
Andrew Trick0a39d4e2012-05-24 22:11:09 +00001091 // State of the top and bottom scheduled instruction boundaries.
Andrew Trick3b87f622012-11-07 07:05:09 +00001092 SchedRemainder Rem;
Andrew Trick0a39d4e2012-05-24 22:11:09 +00001093 SchedBoundary Top;
1094 SchedBoundary Bot;
Andrew Trick17d35e52012-03-14 04:00:41 +00001095
1096public:
Andrew Trickf3234242012-05-24 22:11:12 +00001097 /// SUnit::NodeQueueId: 0 (none), 1 (top), 2 (bot), 3 (both)
Andrew Trick7196a8f2012-05-10 21:06:16 +00001098 enum {
1099 TopQID = 1,
Andrew Trickf3234242012-05-24 22:11:12 +00001100 BotQID = 2,
1101 LogMaxQID = 2
Andrew Trick7196a8f2012-05-10 21:06:16 +00001102 };
1103
Andrew Trickf3234242012-05-24 22:11:12 +00001104 ConvergingScheduler():
Andrew Trick412cd2f2012-10-10 05:43:09 +00001105 DAG(0), SchedModel(0), TRI(0), Top(TopQID, "TopQ"), Bot(BotQID, "BotQ") {}
Andrew Trickd38f87e2012-05-10 21:06:12 +00001106
Andrew Trick0a39d4e2012-05-24 22:11:09 +00001107 virtual void initialize(ScheduleDAGMI *dag);
Andrew Trick17d35e52012-03-14 04:00:41 +00001108
Andrew Trick7196a8f2012-05-10 21:06:16 +00001109 virtual SUnit *pickNode(bool &IsTopNode);
Andrew Trick17d35e52012-03-14 04:00:41 +00001110
Andrew Trick0a39d4e2012-05-24 22:11:09 +00001111 virtual void schedNode(SUnit *SU, bool IsTopNode);
1112
1113 virtual void releaseTopNode(SUnit *SU);
1114
1115 virtual void releaseBottomNode(SUnit *SU);
1116
Andrew Trick3b87f622012-11-07 07:05:09 +00001117 virtual void registerRoots();
Andrew Trick73a0d8e2012-05-17 18:35:10 +00001118
Andrew Trick3b87f622012-11-07 07:05:09 +00001119protected:
1120 void balanceZones(
1121 ConvergingScheduler::SchedBoundary &CriticalZone,
1122 ConvergingScheduler::SchedCandidate &CriticalCand,
1123 ConvergingScheduler::SchedBoundary &OppositeZone,
1124 ConvergingScheduler::SchedCandidate &OppositeCand);
1125
1126 void checkResourceLimits(ConvergingScheduler::SchedCandidate &TopCand,
1127 ConvergingScheduler::SchedCandidate &BotCand);
1128
1129 void tryCandidate(SchedCandidate &Cand,
1130 SchedCandidate &TryCand,
1131 SchedBoundary &Zone,
1132 const RegPressureTracker &RPTracker,
1133 RegPressureTracker &TempTracker);
1134
1135 SUnit *pickNodeBidirectional(bool &IsTopNode);
1136
1137 void pickNodeFromQueue(SchedBoundary &Zone,
1138 const RegPressureTracker &RPTracker,
1139 SchedCandidate &Candidate);
1140
Andrew Trick28ebc892012-05-10 21:06:19 +00001141#ifndef NDEBUG
Andrew Trick3b87f622012-11-07 07:05:09 +00001142 void traceCandidate(const SchedCandidate &Cand, const SchedBoundary &Zone);
Andrew Trick28ebc892012-05-10 21:06:19 +00001143#endif
Andrew Trick42b7a712012-01-17 06:55:03 +00001144};
1145} // namespace
1146
Andrew Trick3b87f622012-11-07 07:05:09 +00001147void ConvergingScheduler::SchedRemainder::
1148init(ScheduleDAGMI *DAG, const TargetSchedModel *SchedModel) {
1149 reset();
1150 if (!SchedModel->hasInstrSchedModel())
1151 return;
1152 RemainingCounts.resize(SchedModel->getNumProcResourceKinds());
1153 for (std::vector<SUnit>::iterator
1154 I = DAG->SUnits.begin(), E = DAG->SUnits.end(); I != E; ++I) {
1155 const MCSchedClassDesc *SC = DAG->getSchedClass(&*I);
1156 RemainingMicroOps += SchedModel->getNumMicroOps(I->getInstr(), SC);
1157 for (TargetSchedModel::ProcResIter
1158 PI = SchedModel->getWriteProcResBegin(SC),
1159 PE = SchedModel->getWriteProcResEnd(SC); PI != PE; ++PI) {
1160 unsigned PIdx = PI->ProcResourceIdx;
1161 unsigned Factor = SchedModel->getResourceFactor(PIdx);
1162 RemainingCounts[PIdx] += (Factor * PI->Cycles);
1163 }
1164 }
1165}
1166
1167void ConvergingScheduler::SchedBoundary::
1168init(ScheduleDAGMI *dag, const TargetSchedModel *smodel, SchedRemainder *rem) {
1169 reset();
1170 DAG = dag;
1171 SchedModel = smodel;
1172 Rem = rem;
1173 if (SchedModel->hasInstrSchedModel())
1174 ResourceCounts.resize(SchedModel->getNumProcResourceKinds());
1175}
1176
Andrew Trick0a39d4e2012-05-24 22:11:09 +00001177void ConvergingScheduler::initialize(ScheduleDAGMI *dag) {
1178 DAG = dag;
Andrew Trick412cd2f2012-10-10 05:43:09 +00001179 SchedModel = DAG->getSchedModel();
Andrew Trick0a39d4e2012-05-24 22:11:09 +00001180 TRI = DAG->TRI;
Andrew Trick3b87f622012-11-07 07:05:09 +00001181 Rem.init(DAG, SchedModel);
1182 Top.init(DAG, SchedModel, &Rem);
1183 Bot.init(DAG, SchedModel, &Rem);
1184
1185 // Initialize resource counts.
Andrew Trick0a39d4e2012-05-24 22:11:09 +00001186
Andrew Trick412cd2f2012-10-10 05:43:09 +00001187 // Initialize the HazardRecognizers. If itineraries don't exist, are empty, or
1188 // are disabled, then these HazardRecs will be disabled.
1189 const InstrItineraryData *Itin = SchedModel->getInstrItineraries();
Andrew Trick0a39d4e2012-05-24 22:11:09 +00001190 const TargetMachine &TM = DAG->MF.getTarget();
Andrew Trick0a39d4e2012-05-24 22:11:09 +00001191 Top.HazardRec = TM.getInstrInfo()->CreateTargetMIHazardRecognizer(Itin, DAG);
1192 Bot.HazardRec = TM.getInstrInfo()->CreateTargetMIHazardRecognizer(Itin, DAG);
1193
1194 assert((!ForceTopDown || !ForceBottomUp) &&
1195 "-misched-topdown incompatible with -misched-bottomup");
1196}
1197
1198void ConvergingScheduler::releaseTopNode(SUnit *SU) {
Andrew Trickb7e02892012-06-05 21:11:27 +00001199 if (SU->isScheduled)
1200 return;
1201
1202 for (SUnit::succ_iterator I = SU->Preds.begin(), E = SU->Preds.end();
1203 I != E; ++I) {
1204 unsigned PredReadyCycle = I->getSUnit()->TopReadyCycle;
Andrew Trickffd25262012-08-23 00:39:43 +00001205 unsigned MinLatency = I->getMinLatency();
Andrew Trickb7e02892012-06-05 21:11:27 +00001206#ifndef NDEBUG
Andrew Trickffd25262012-08-23 00:39:43 +00001207 Top.MaxMinLatency = std::max(MinLatency, Top.MaxMinLatency);
Andrew Trickb7e02892012-06-05 21:11:27 +00001208#endif
Andrew Trickffd25262012-08-23 00:39:43 +00001209 if (SU->TopReadyCycle < PredReadyCycle + MinLatency)
1210 SU->TopReadyCycle = PredReadyCycle + MinLatency;
Andrew Trickb7e02892012-06-05 21:11:27 +00001211 }
1212 Top.releaseNode(SU, SU->TopReadyCycle);
Andrew Trick0a39d4e2012-05-24 22:11:09 +00001213}
1214
1215void ConvergingScheduler::releaseBottomNode(SUnit *SU) {
Andrew Trickb7e02892012-06-05 21:11:27 +00001216 if (SU->isScheduled)
1217 return;
1218
1219 assert(SU->getInstr() && "Scheduled SUnit must have instr");
1220
1221 for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
1222 I != E; ++I) {
Andrew Trick9b5caaa2012-11-12 19:40:10 +00001223 if (I->isWeak())
1224 continue;
Andrew Trickb7e02892012-06-05 21:11:27 +00001225 unsigned SuccReadyCycle = I->getSUnit()->BotReadyCycle;
Andrew Trickffd25262012-08-23 00:39:43 +00001226 unsigned MinLatency = I->getMinLatency();
Andrew Trickb7e02892012-06-05 21:11:27 +00001227#ifndef NDEBUG
Andrew Trickffd25262012-08-23 00:39:43 +00001228 Bot.MaxMinLatency = std::max(MinLatency, Bot.MaxMinLatency);
Andrew Trickb7e02892012-06-05 21:11:27 +00001229#endif
Andrew Trickffd25262012-08-23 00:39:43 +00001230 if (SU->BotReadyCycle < SuccReadyCycle + MinLatency)
1231 SU->BotReadyCycle = SuccReadyCycle + MinLatency;
Andrew Trickb7e02892012-06-05 21:11:27 +00001232 }
1233 Bot.releaseNode(SU, SU->BotReadyCycle);
Andrew Trick0a39d4e2012-05-24 22:11:09 +00001234}
1235
Andrew Trick3b87f622012-11-07 07:05:09 +00001236void ConvergingScheduler::registerRoots() {
1237 Rem.CriticalPath = DAG->ExitSU.getDepth();
1238 // Some roots may not feed into ExitSU. Check all of them in case.
1239 for (std::vector<SUnit*>::const_iterator
1240 I = Bot.Available.begin(), E = Bot.Available.end(); I != E; ++I) {
1241 if ((*I)->getDepth() > Rem.CriticalPath)
1242 Rem.CriticalPath = (*I)->getDepth();
1243 }
1244 DEBUG(dbgs() << "Critical Path: " << Rem.CriticalPath << '\n');
1245}
1246
Andrew Trick5559ffa2012-06-29 03:23:24 +00001247/// Does this SU have a hazard within the current instruction group.
1248///
1249/// The scheduler supports two modes of hazard recognition. The first is the
1250/// ScheduleHazardRecognizer API. It is a fully general hazard recognizer that
1251/// supports highly complicated in-order reservation tables
1252/// (ScoreboardHazardRecognizer) and arbitraty target-specific logic.
1253///
1254/// The second is a streamlined mechanism that checks for hazards based on
1255/// simple counters that the scheduler itself maintains. It explicitly checks
1256/// for instruction dispatch limitations, including the number of micro-ops that
1257/// can dispatch per cycle.
1258///
1259/// TODO: Also check whether the SU must start a new group.
1260bool ConvergingScheduler::SchedBoundary::checkHazard(SUnit *SU) {
1261 if (HazardRec->isEnabled())
1262 return HazardRec->getHazardType(SU) != ScheduleHazardRecognizer::NoHazard;
1263
Andrew Trick412cd2f2012-10-10 05:43:09 +00001264 unsigned uops = SchedModel->getNumMicroOps(SU->getInstr());
Andrew Trick3b87f622012-11-07 07:05:09 +00001265 if ((IssueCount > 0) && (IssueCount + uops > SchedModel->getIssueWidth())) {
1266 DEBUG(dbgs() << " SU(" << SU->NodeNum << ") uops="
1267 << SchedModel->getNumMicroOps(SU->getInstr()) << '\n');
Andrew Trick5559ffa2012-06-29 03:23:24 +00001268 return true;
Andrew Trick3b87f622012-11-07 07:05:09 +00001269 }
Andrew Trick5559ffa2012-06-29 03:23:24 +00001270 return false;
1271}
1272
Andrew Trick3b87f622012-11-07 07:05:09 +00001273/// If expected latency is covered, disable ILP policy.
1274void ConvergingScheduler::SchedBoundary::checkILPPolicy() {
1275 if (ShouldIncreaseILP
1276 && (IsResourceLimited || ExpectedLatency <= CurrCycle)) {
1277 ShouldIncreaseILP = false;
1278 DEBUG(dbgs() << "Disable ILP: " << Available.getName() << '\n');
1279 }
1280}
1281
Andrew Trick0a39d4e2012-05-24 22:11:09 +00001282void ConvergingScheduler::SchedBoundary::releaseNode(SUnit *SU,
1283 unsigned ReadyCycle) {
Andrew Trick3b87f622012-11-07 07:05:09 +00001284
Andrew Trick0a39d4e2012-05-24 22:11:09 +00001285 if (ReadyCycle < MinReadyCycle)
1286 MinReadyCycle = ReadyCycle;
1287
1288 // Check for interlocks first. For the purpose of other heuristics, an
1289 // instruction that cannot issue appears as if it's not in the ReadyQueue.
Andrew Trick5559ffa2012-06-29 03:23:24 +00001290 if (ReadyCycle > CurrCycle || checkHazard(SU))
Andrew Trick0a39d4e2012-05-24 22:11:09 +00001291 Pending.push(SU);
1292 else
1293 Available.push(SU);
Andrew Trick3b87f622012-11-07 07:05:09 +00001294
1295 // Record this node as an immediate dependent of the scheduled node.
1296 NextSUs.insert(SU);
1297
1298 // If CriticalPath has been computed, then check if the unscheduled nodes
1299 // exceed the ILP window. Before registerRoots, CriticalPath==0.
1300 if (Rem->CriticalPath && (ExpectedLatency + getUnscheduledLatency(SU)
1301 > Rem->CriticalPath + ILPWindow)) {
1302 ShouldIncreaseILP = true;
1303 DEBUG(dbgs() << "Increase ILP: " << Available.getName() << " "
1304 << ExpectedLatency << " + " << getUnscheduledLatency(SU) << '\n');
1305 }
Andrew Trick0a39d4e2012-05-24 22:11:09 +00001306}
1307
1308/// Move the boundary of scheduled code by one cycle.
1309void ConvergingScheduler::SchedBoundary::bumpCycle() {
Andrew Trick412cd2f2012-10-10 05:43:09 +00001310 unsigned Width = SchedModel->getIssueWidth();
Andrew Trick7f8c74c2012-06-29 03:23:22 +00001311 IssueCount = (IssueCount <= Width) ? 0 : IssueCount - Width;
Andrew Trick0a39d4e2012-05-24 22:11:09 +00001312
Andrew Trick3b87f622012-11-07 07:05:09 +00001313 unsigned NextCycle = CurrCycle + 1;
Andrew Trick0a39d4e2012-05-24 22:11:09 +00001314 assert(MinReadyCycle < UINT_MAX && "MinReadyCycle uninitialized");
Andrew Trick3b87f622012-11-07 07:05:09 +00001315 if (MinReadyCycle > NextCycle) {
1316 IssueCount = 0;
1317 NextCycle = MinReadyCycle;
1318 }
Andrew Trick0a39d4e2012-05-24 22:11:09 +00001319
1320 if (!HazardRec->isEnabled()) {
Andrew Trickb7e02892012-06-05 21:11:27 +00001321 // Bypass HazardRec virtual calls.
Andrew Trick0a39d4e2012-05-24 22:11:09 +00001322 CurrCycle = NextCycle;
1323 }
1324 else {
Andrew Trickb7e02892012-06-05 21:11:27 +00001325 // Bypass getHazardType calls in case of long latency.
Andrew Trick0a39d4e2012-05-24 22:11:09 +00001326 for (; CurrCycle != NextCycle; ++CurrCycle) {
1327 if (isTop())
1328 HazardRec->AdvanceCycle();
1329 else
1330 HazardRec->RecedeCycle();
1331 }
1332 }
1333 CheckPending = true;
Andrew Trick3b87f622012-11-07 07:05:09 +00001334 IsResourceLimited = getCriticalCount() > std::max(ExpectedLatency, CurrCycle);
Andrew Trick0a39d4e2012-05-24 22:11:09 +00001335
Andrew Trick3b87f622012-11-07 07:05:09 +00001336 DEBUG(dbgs() << " *** " << Available.getName() << " cycle "
Andrew Trick0a39d4e2012-05-24 22:11:09 +00001337 << CurrCycle << '\n');
1338}
1339
Andrew Trick3b87f622012-11-07 07:05:09 +00001340/// Add the given processor resource to this scheduled zone.
1341void ConvergingScheduler::SchedBoundary::countResource(unsigned PIdx,
1342 unsigned Cycles) {
1343 unsigned Factor = SchedModel->getResourceFactor(PIdx);
1344 DEBUG(dbgs() << " " << SchedModel->getProcResource(PIdx)->Name
1345 << " +(" << Cycles << "x" << Factor
1346 << ") / " << SchedModel->getLatencyFactor() << '\n');
1347
1348 unsigned Count = Factor * Cycles;
1349 ResourceCounts[PIdx] += Count;
1350 assert(Rem->RemainingCounts[PIdx] >= Count && "resource double counted");
1351 Rem->RemainingCounts[PIdx] -= Count;
1352
1353 // Reset MaxRemainingCount for sanity.
1354 Rem->MaxRemainingCount = 0;
1355
1356 // Check if this resource exceeds the current critical resource by a full
1357 // cycle. If so, it becomes the critical resource.
1358 if ((int)(ResourceCounts[PIdx] - ResourceCounts[CritResIdx])
1359 >= (int)SchedModel->getLatencyFactor()) {
1360 CritResIdx = PIdx;
1361 DEBUG(dbgs() << " *** Critical resource "
1362 << SchedModel->getProcResource(PIdx)->Name << " x"
1363 << ResourceCounts[PIdx] << '\n');
1364 }
1365}
1366
Andrew Trickb7e02892012-06-05 21:11:27 +00001367/// Move the boundary of scheduled code by one SUnit.
Andrew Trick7f8c74c2012-06-29 03:23:22 +00001368void ConvergingScheduler::SchedBoundary::bumpNode(SUnit *SU) {
Andrew Trickb7e02892012-06-05 21:11:27 +00001369 // Update the reservation table.
1370 if (HazardRec->isEnabled()) {
1371 if (!isTop() && SU->isCall) {
1372 // Calls are scheduled with their preceding instructions. For bottom-up
1373 // scheduling, clear the pipeline state before emitting.
1374 HazardRec->Reset();
1375 }
1376 HazardRec->EmitInstruction(SU);
1377 }
Andrew Trick3b87f622012-11-07 07:05:09 +00001378 // Update resource counts and critical resource.
1379 if (SchedModel->hasInstrSchedModel()) {
1380 const MCSchedClassDesc *SC = DAG->getSchedClass(SU);
1381 Rem->RemainingMicroOps -= SchedModel->getNumMicroOps(SU->getInstr(), SC);
1382 for (TargetSchedModel::ProcResIter
1383 PI = SchedModel->getWriteProcResBegin(SC),
1384 PE = SchedModel->getWriteProcResEnd(SC); PI != PE; ++PI) {
1385 countResource(PI->ProcResourceIdx, PI->Cycles);
1386 }
1387 }
1388 if (isTop()) {
1389 if (SU->getDepth() > ExpectedLatency)
1390 ExpectedLatency = SU->getDepth();
1391 }
1392 else {
1393 if (SU->getHeight() > ExpectedLatency)
1394 ExpectedLatency = SU->getHeight();
1395 }
1396
1397 IsResourceLimited = getCriticalCount() > std::max(ExpectedLatency, CurrCycle);
1398
Andrew Trick5559ffa2012-06-29 03:23:24 +00001399 // Check the instruction group dispatch limit.
1400 // TODO: Check if this SU must end a dispatch group.
Andrew Trick412cd2f2012-10-10 05:43:09 +00001401 IssueCount += SchedModel->getNumMicroOps(SU->getInstr());
Andrew Trick3b87f622012-11-07 07:05:09 +00001402
1403 // checkHazard prevents scheduling multiple instructions per cycle that exceed
1404 // issue width. However, we commonly reach the maximum. In this case
1405 // opportunistically bump the cycle to avoid uselessly checking everything in
1406 // the readyQ. Furthermore, a single instruction may produce more than one
1407 // cycle's worth of micro-ops.
Andrew Trick412cd2f2012-10-10 05:43:09 +00001408 if (IssueCount >= SchedModel->getIssueWidth()) {
Andrew Trick3b87f622012-11-07 07:05:09 +00001409 DEBUG(dbgs() << " *** Max instrs at cycle " << CurrCycle << '\n');
Andrew Trickb7e02892012-06-05 21:11:27 +00001410 bumpCycle();
1411 }
1412}
1413
Andrew Trick0a39d4e2012-05-24 22:11:09 +00001414/// Release pending ready nodes in to the available queue. This makes them
1415/// visible to heuristics.
1416void ConvergingScheduler::SchedBoundary::releasePending() {
1417 // If the available queue is empty, it is safe to reset MinReadyCycle.
1418 if (Available.empty())
1419 MinReadyCycle = UINT_MAX;
1420
1421 // Check to see if any of the pending instructions are ready to issue. If
1422 // so, add them to the available queue.
1423 for (unsigned i = 0, e = Pending.size(); i != e; ++i) {
1424 SUnit *SU = *(Pending.begin()+i);
Andrew Trickb7e02892012-06-05 21:11:27 +00001425 unsigned ReadyCycle = isTop() ? SU->TopReadyCycle : SU->BotReadyCycle;
Andrew Trick0a39d4e2012-05-24 22:11:09 +00001426
1427 if (ReadyCycle < MinReadyCycle)
1428 MinReadyCycle = ReadyCycle;
1429
1430 if (ReadyCycle > CurrCycle)
1431 continue;
1432
Andrew Trick5559ffa2012-06-29 03:23:24 +00001433 if (checkHazard(SU))
Andrew Trick0a39d4e2012-05-24 22:11:09 +00001434 continue;
1435
1436 Available.push(SU);
1437 Pending.remove(Pending.begin()+i);
1438 --i; --e;
1439 }
Andrew Trick3b87f622012-11-07 07:05:09 +00001440 DEBUG(if (!Pending.empty()) Pending.dump());
Andrew Trick0a39d4e2012-05-24 22:11:09 +00001441 CheckPending = false;
1442}
1443
1444/// Remove SU from the ready set for this boundary.
1445void ConvergingScheduler::SchedBoundary::removeReady(SUnit *SU) {
1446 if (Available.isInQueue(SU))
1447 Available.remove(Available.find(SU));
1448 else {
1449 assert(Pending.isInQueue(SU) && "bad ready count");
1450 Pending.remove(Pending.find(SU));
1451 }
1452}
1453
1454/// If this queue only has one ready candidate, return it. As a side effect,
Andrew Trick3b87f622012-11-07 07:05:09 +00001455/// defer any nodes that now hit a hazard, and advance the cycle until at least
1456/// one node is ready. If multiple instructions are ready, return NULL.
Andrew Trick0a39d4e2012-05-24 22:11:09 +00001457SUnit *ConvergingScheduler::SchedBoundary::pickOnlyChoice() {
1458 if (CheckPending)
1459 releasePending();
1460
Andrew Trick3b87f622012-11-07 07:05:09 +00001461 if (IssueCount > 0) {
1462 // Defer any ready instrs that now have a hazard.
1463 for (ReadyQueue::iterator I = Available.begin(); I != Available.end();) {
1464 if (checkHazard(*I)) {
1465 Pending.push(*I);
1466 I = Available.remove(I);
1467 continue;
1468 }
1469 ++I;
1470 }
1471 }
Andrew Trick0a39d4e2012-05-24 22:11:09 +00001472 for (unsigned i = 0; Available.empty(); ++i) {
Andrew Trickb7e02892012-06-05 21:11:27 +00001473 assert(i <= (HazardRec->getMaxLookAhead() + MaxMinLatency) &&
1474 "permanent hazard"); (void)i;
Andrew Trick0a39d4e2012-05-24 22:11:09 +00001475 bumpCycle();
1476 releasePending();
1477 }
1478 if (Available.size() == 1)
1479 return *Available.begin();
1480 return NULL;
1481}
1482
Andrew Trick3b87f622012-11-07 07:05:09 +00001483/// Record the candidate policy for opposite zones with different critical
1484/// resources.
1485///
1486/// If the CriticalZone is latency limited, don't force a policy for the
1487/// candidates here. Instead, When releasing each candidate, releaseNode
1488/// compares the region's critical path to the candidate's height or depth and
1489/// the scheduled zone's expected latency then sets ShouldIncreaseILP.
1490void ConvergingScheduler::balanceZones(
1491 ConvergingScheduler::SchedBoundary &CriticalZone,
1492 ConvergingScheduler::SchedCandidate &CriticalCand,
1493 ConvergingScheduler::SchedBoundary &OppositeZone,
1494 ConvergingScheduler::SchedCandidate &OppositeCand) {
1495
1496 if (!CriticalZone.IsResourceLimited)
1497 return;
1498
1499 SchedRemainder *Rem = CriticalZone.Rem;
1500
1501 // If the critical zone is overconsuming a resource relative to the
1502 // remainder, try to reduce it.
1503 unsigned RemainingCritCount =
1504 Rem->RemainingCounts[CriticalZone.CritResIdx];
1505 if ((int)(Rem->MaxRemainingCount - RemainingCritCount)
1506 > (int)SchedModel->getLatencyFactor()) {
1507 CriticalCand.Policy.ReduceResIdx = CriticalZone.CritResIdx;
1508 DEBUG(dbgs() << "Balance " << CriticalZone.Available.getName() << " reduce "
1509 << SchedModel->getProcResource(CriticalZone.CritResIdx)->Name
1510 << '\n');
1511 }
1512 // If the other zone is underconsuming a resource relative to the full zone,
1513 // try to increase it.
1514 unsigned OppositeCount =
1515 OppositeZone.ResourceCounts[CriticalZone.CritResIdx];
1516 if ((int)(OppositeZone.ExpectedCount - OppositeCount)
1517 > (int)SchedModel->getLatencyFactor()) {
1518 OppositeCand.Policy.DemandResIdx = CriticalZone.CritResIdx;
1519 DEBUG(dbgs() << "Balance " << OppositeZone.Available.getName() << " demand "
1520 << SchedModel->getProcResource(OppositeZone.CritResIdx)->Name
1521 << '\n');
1522 }
Andrew Trick28ebc892012-05-10 21:06:19 +00001523}
Andrew Trick3b87f622012-11-07 07:05:09 +00001524
1525/// Determine if the scheduled zones exceed resource limits or critical path and
1526/// set each candidate's ReduceHeight policy accordingly.
1527void ConvergingScheduler::checkResourceLimits(
1528 ConvergingScheduler::SchedCandidate &TopCand,
1529 ConvergingScheduler::SchedCandidate &BotCand) {
1530
1531 Bot.checkILPPolicy();
1532 Top.checkILPPolicy();
1533 if (Bot.ShouldIncreaseILP)
1534 BotCand.Policy.ReduceLatency = true;
1535 if (Top.ShouldIncreaseILP)
1536 TopCand.Policy.ReduceLatency = true;
1537
1538 // Handle resource-limited regions.
1539 if (Top.IsResourceLimited && Bot.IsResourceLimited
1540 && Top.CritResIdx == Bot.CritResIdx) {
1541 // If the scheduled critical resource in both zones is no longer the
1542 // critical remaining resource, attempt to reduce resource height both ways.
1543 if (Top.CritResIdx != Rem.CritResIdx) {
1544 TopCand.Policy.ReduceResIdx = Top.CritResIdx;
1545 BotCand.Policy.ReduceResIdx = Bot.CritResIdx;
1546 DEBUG(dbgs() << "Reduce scheduled "
1547 << SchedModel->getProcResource(Top.CritResIdx)->Name << '\n');
1548 }
1549 return;
1550 }
1551 // Handle latency-limited regions.
1552 if (!Top.IsResourceLimited && !Bot.IsResourceLimited) {
1553 // If the total scheduled expected latency exceeds the region's critical
1554 // path then reduce latency both ways.
1555 //
1556 // Just because a zone is not resource limited does not mean it is latency
1557 // limited. Unbuffered resource, such as max micro-ops may cause CurrCycle
1558 // to exceed expected latency.
1559 if ((Top.ExpectedLatency + Bot.ExpectedLatency >= Rem.CriticalPath)
1560 && (Rem.CriticalPath > Top.CurrCycle + Bot.CurrCycle)) {
1561 TopCand.Policy.ReduceLatency = true;
1562 BotCand.Policy.ReduceLatency = true;
1563 DEBUG(dbgs() << "Reduce scheduled latency " << Top.ExpectedLatency
1564 << " + " << Bot.ExpectedLatency << '\n');
1565 }
1566 return;
1567 }
1568 // The critical resource is different in each zone, so request balancing.
1569
1570 // Compute the cost of each zone.
1571 Rem.MaxRemainingCount = std::max(
1572 Rem.RemainingMicroOps * SchedModel->getMicroOpFactor(),
1573 Rem.RemainingCounts[Rem.CritResIdx]);
1574 Top.ExpectedCount = std::max(Top.ExpectedLatency, Top.CurrCycle);
1575 Top.ExpectedCount = std::max(
1576 Top.getCriticalCount(),
1577 Top.ExpectedCount * SchedModel->getLatencyFactor());
1578 Bot.ExpectedCount = std::max(Bot.ExpectedLatency, Bot.CurrCycle);
1579 Bot.ExpectedCount = std::max(
1580 Bot.getCriticalCount(),
1581 Bot.ExpectedCount * SchedModel->getLatencyFactor());
1582
1583 balanceZones(Top, TopCand, Bot, BotCand);
1584 balanceZones(Bot, BotCand, Top, TopCand);
1585}
1586
1587void ConvergingScheduler::SchedCandidate::
1588initResourceDelta(const ScheduleDAGMI *DAG,
1589 const TargetSchedModel *SchedModel) {
1590 if (!Policy.ReduceResIdx && !Policy.DemandResIdx)
1591 return;
1592
1593 const MCSchedClassDesc *SC = DAG->getSchedClass(SU);
1594 for (TargetSchedModel::ProcResIter
1595 PI = SchedModel->getWriteProcResBegin(SC),
1596 PE = SchedModel->getWriteProcResEnd(SC); PI != PE; ++PI) {
1597 if (PI->ProcResourceIdx == Policy.ReduceResIdx)
1598 ResDelta.CritResources += PI->Cycles;
1599 if (PI->ProcResourceIdx == Policy.DemandResIdx)
1600 ResDelta.DemandedResources += PI->Cycles;
1601 }
1602}
1603
1604/// Return true if this heuristic determines order.
1605static bool tryLess(unsigned TryVal, unsigned CandVal,
1606 ConvergingScheduler::SchedCandidate &TryCand,
1607 ConvergingScheduler::SchedCandidate &Cand,
1608 ConvergingScheduler::CandReason Reason) {
1609 if (TryVal < CandVal) {
1610 TryCand.Reason = Reason;
1611 return true;
1612 }
1613 if (TryVal > CandVal) {
1614 if (Cand.Reason > Reason)
1615 Cand.Reason = Reason;
1616 return true;
1617 }
1618 return false;
1619}
Andrew Trick9b5caaa2012-11-12 19:40:10 +00001620
Andrew Trick3b87f622012-11-07 07:05:09 +00001621static bool tryGreater(unsigned TryVal, unsigned CandVal,
1622 ConvergingScheduler::SchedCandidate &TryCand,
1623 ConvergingScheduler::SchedCandidate &Cand,
1624 ConvergingScheduler::CandReason Reason) {
1625 if (TryVal > CandVal) {
1626 TryCand.Reason = Reason;
1627 return true;
1628 }
1629 if (TryVal < CandVal) {
1630 if (Cand.Reason > Reason)
1631 Cand.Reason = Reason;
1632 return true;
1633 }
1634 return false;
1635}
1636
Andrew Trick9b5caaa2012-11-12 19:40:10 +00001637static unsigned getWeakLeft(const SUnit *SU, bool isTop) {
1638 return (isTop) ? SU->WeakPredsLeft : SU->WeakSuccsLeft;
1639}
1640
Andrew Trick3b87f622012-11-07 07:05:09 +00001641/// Apply a set of heursitics to a new candidate. Heuristics are currently
1642/// hierarchical. This may be more efficient than a graduated cost model because
1643/// we don't need to evaluate all aspects of the model for each node in the
1644/// queue. But it's really done to make the heuristics easier to debug and
1645/// statistically analyze.
1646///
1647/// \param Cand provides the policy and current best candidate.
1648/// \param TryCand refers to the next SUnit candidate, otherwise uninitialized.
1649/// \param Zone describes the scheduled zone that we are extending.
1650/// \param RPTracker describes reg pressure within the scheduled zone.
1651/// \param TempTracker is a scratch pressure tracker to reuse in queries.
1652void ConvergingScheduler::tryCandidate(SchedCandidate &Cand,
1653 SchedCandidate &TryCand,
1654 SchedBoundary &Zone,
1655 const RegPressureTracker &RPTracker,
1656 RegPressureTracker &TempTracker) {
1657
1658 // Always initialize TryCand's RPDelta.
1659 TempTracker.getMaxPressureDelta(TryCand.SU->getInstr(), TryCand.RPDelta,
1660 DAG->getRegionCriticalPSets(),
1661 DAG->getRegPressure().MaxSetPressure);
1662
1663 // Initialize the candidate if needed.
1664 if (!Cand.isValid()) {
1665 TryCand.Reason = NodeOrder;
1666 return;
1667 }
1668 // Avoid exceeding the target's limit.
1669 if (tryLess(TryCand.RPDelta.Excess.UnitIncrease,
1670 Cand.RPDelta.Excess.UnitIncrease, TryCand, Cand, SingleExcess))
1671 return;
1672 if (Cand.Reason == SingleExcess)
1673 Cand.Reason = MultiPressure;
1674
1675 // Avoid increasing the max critical pressure in the scheduled region.
1676 if (tryLess(TryCand.RPDelta.CriticalMax.UnitIncrease,
1677 Cand.RPDelta.CriticalMax.UnitIncrease,
1678 TryCand, Cand, SingleCritical))
1679 return;
1680 if (Cand.Reason == SingleCritical)
1681 Cand.Reason = MultiPressure;
1682
Andrew Trick9b5caaa2012-11-12 19:40:10 +00001683 // Keep clustered nodes together to encourage downstream peephole
1684 // optimizations which may reduce resource requirements.
1685 //
1686 // This is a best effort to set things up for a post-RA pass. Optimizations
1687 // like generating loads of multiple registers should ideally be done within
1688 // the scheduler pass by combining the loads during DAG postprocessing.
1689 const SUnit *NextClusterSU =
1690 Zone.isTop() ? DAG->getNextClusterSucc() : DAG->getNextClusterPred();
1691 if (tryGreater(TryCand.SU == NextClusterSU, Cand.SU == NextClusterSU,
1692 TryCand, Cand, Cluster))
1693 return;
1694 // Currently, weak edges are for clustering, so we hard-code that reason.
1695 // However, deferring the current TryCand will not change Cand's reason.
1696 CandReason OrigReason = Cand.Reason;
1697 if (tryLess(getWeakLeft(TryCand.SU, Zone.isTop()),
1698 getWeakLeft(Cand.SU, Zone.isTop()),
1699 TryCand, Cand, Cluster)) {
1700 Cand.Reason = OrigReason;
1701 return;
1702 }
Andrew Trick3b87f622012-11-07 07:05:09 +00001703 // Avoid critical resource consumption and balance the schedule.
1704 TryCand.initResourceDelta(DAG, SchedModel);
1705 if (tryLess(TryCand.ResDelta.CritResources, Cand.ResDelta.CritResources,
1706 TryCand, Cand, ResourceReduce))
1707 return;
1708 if (tryGreater(TryCand.ResDelta.DemandedResources,
1709 Cand.ResDelta.DemandedResources,
1710 TryCand, Cand, ResourceDemand))
1711 return;
1712
1713 // Avoid serializing long latency dependence chains.
1714 if (Cand.Policy.ReduceLatency) {
1715 if (Zone.isTop()) {
1716 if (Cand.SU->getDepth() * SchedModel->getLatencyFactor()
1717 > Zone.ExpectedCount) {
1718 if (tryLess(TryCand.SU->getDepth(), Cand.SU->getDepth(),
1719 TryCand, Cand, TopDepthReduce))
1720 return;
1721 }
1722 if (tryGreater(TryCand.SU->getHeight(), Cand.SU->getHeight(),
1723 TryCand, Cand, TopPathReduce))
1724 return;
1725 }
1726 else {
1727 if (Cand.SU->getHeight() * SchedModel->getLatencyFactor()
1728 > Zone.ExpectedCount) {
1729 if (tryLess(TryCand.SU->getHeight(), Cand.SU->getHeight(),
1730 TryCand, Cand, BotHeightReduce))
1731 return;
1732 }
1733 if (tryGreater(TryCand.SU->getDepth(), Cand.SU->getDepth(),
1734 TryCand, Cand, BotPathReduce))
1735 return;
1736 }
1737 }
1738
1739 // Avoid increasing the max pressure of the entire region.
1740 if (tryLess(TryCand.RPDelta.CurrentMax.UnitIncrease,
1741 Cand.RPDelta.CurrentMax.UnitIncrease, TryCand, Cand, SingleMax))
1742 return;
1743 if (Cand.Reason == SingleMax)
1744 Cand.Reason = MultiPressure;
1745
1746 // Prefer immediate defs/users of the last scheduled instruction. This is a
1747 // nice pressure avoidance strategy that also conserves the processor's
1748 // register renaming resources and keeps the machine code readable.
Andrew Trick9b5caaa2012-11-12 19:40:10 +00001749 if (tryGreater(Zone.NextSUs.count(TryCand.SU), Zone.NextSUs.count(Cand.SU),
1750 TryCand, Cand, NextDefUse))
Andrew Trick3b87f622012-11-07 07:05:09 +00001751 return;
Andrew Trick9b5caaa2012-11-12 19:40:10 +00001752
Andrew Trick3b87f622012-11-07 07:05:09 +00001753 // Fall through to original instruction order.
1754 if ((Zone.isTop() && TryCand.SU->NodeNum < Cand.SU->NodeNum)
1755 || (!Zone.isTop() && TryCand.SU->NodeNum > Cand.SU->NodeNum)) {
1756 TryCand.Reason = NodeOrder;
1757 }
1758}
Andrew Trick28ebc892012-05-10 21:06:19 +00001759
Andrew Trick5429a6b2012-05-17 22:37:09 +00001760/// pickNodeFromQueue helper that returns true if the LHS reg pressure effect is
1761/// more desirable than RHS from scheduling standpoint.
Andrew Trick73a0d8e2012-05-17 18:35:10 +00001762static bool compareRPDelta(const RegPressureDelta &LHS,
1763 const RegPressureDelta &RHS) {
1764 // Compare each component of pressure in decreasing order of importance
1765 // without checking if any are valid. Invalid PressureElements are assumed to
1766 // have UnitIncrease==0, so are neutral.
Andrew Trickc8fe4ec2012-05-24 22:11:01 +00001767
1768 // Avoid increasing the max critical pressure in the scheduled region.
Andrew Trick3b87f622012-11-07 07:05:09 +00001769 if (LHS.Excess.UnitIncrease != RHS.Excess.UnitIncrease) {
1770 DEBUG(dbgs() << "RP excess top - bot: "
1771 << (LHS.Excess.UnitIncrease - RHS.Excess.UnitIncrease) << '\n');
Andrew Trick73a0d8e2012-05-17 18:35:10 +00001772 return LHS.Excess.UnitIncrease < RHS.Excess.UnitIncrease;
Andrew Trick3b87f622012-11-07 07:05:09 +00001773 }
Andrew Trickc8fe4ec2012-05-24 22:11:01 +00001774 // Avoid increasing the max critical pressure in the scheduled region.
Andrew Trick3b87f622012-11-07 07:05:09 +00001775 if (LHS.CriticalMax.UnitIncrease != RHS.CriticalMax.UnitIncrease) {
1776 DEBUG(dbgs() << "RP critical top - bot: "
1777 << (LHS.CriticalMax.UnitIncrease - RHS.CriticalMax.UnitIncrease)
1778 << '\n');
Andrew Trick73a0d8e2012-05-17 18:35:10 +00001779 return LHS.CriticalMax.UnitIncrease < RHS.CriticalMax.UnitIncrease;
Andrew Trick3b87f622012-11-07 07:05:09 +00001780 }
Andrew Trickc8fe4ec2012-05-24 22:11:01 +00001781 // Avoid increasing the max pressure of the entire region.
Andrew Trick3b87f622012-11-07 07:05:09 +00001782 if (LHS.CurrentMax.UnitIncrease != RHS.CurrentMax.UnitIncrease) {
1783 DEBUG(dbgs() << "RP current top - bot: "
1784 << (LHS.CurrentMax.UnitIncrease - RHS.CurrentMax.UnitIncrease)
1785 << '\n');
Andrew Trick73a0d8e2012-05-17 18:35:10 +00001786 return LHS.CurrentMax.UnitIncrease < RHS.CurrentMax.UnitIncrease;
Andrew Trick3b87f622012-11-07 07:05:09 +00001787 }
Andrew Trick73a0d8e2012-05-17 18:35:10 +00001788 return false;
1789}
1790
Andrew Trick3b87f622012-11-07 07:05:09 +00001791#ifndef NDEBUG
1792const char *ConvergingScheduler::getReasonStr(
1793 ConvergingScheduler::CandReason Reason) {
1794 switch (Reason) {
1795 case NoCand: return "NOCAND ";
1796 case SingleExcess: return "REG-EXCESS";
1797 case SingleCritical: return "REG-CRIT ";
Andrew Trick9b5caaa2012-11-12 19:40:10 +00001798 case Cluster: return "CLUSTER ";
Andrew Trick3b87f622012-11-07 07:05:09 +00001799 case SingleMax: return "REG-MAX ";
1800 case MultiPressure: return "REG-MULTI ";
1801 case ResourceReduce: return "RES-REDUCE";
1802 case ResourceDemand: return "RES-DEMAND";
1803 case TopDepthReduce: return "TOP-DEPTH ";
1804 case TopPathReduce: return "TOP-PATH ";
1805 case BotHeightReduce:return "BOT-HEIGHT";
1806 case BotPathReduce: return "BOT-PATH ";
1807 case NextDefUse: return "DEF-USE ";
1808 case NodeOrder: return "ORDER ";
1809 };
Benjamin Kramerb7546872012-11-09 15:45:22 +00001810 llvm_unreachable("Unknown reason!");
Andrew Trick3b87f622012-11-07 07:05:09 +00001811}
1812
1813void ConvergingScheduler::traceCandidate(const SchedCandidate &Cand,
1814 const SchedBoundary &Zone) {
1815 const char *Label = getReasonStr(Cand.Reason);
1816 PressureElement P;
1817 unsigned ResIdx = 0;
1818 unsigned Latency = 0;
1819 switch (Cand.Reason) {
1820 default:
1821 break;
1822 case SingleExcess:
1823 P = Cand.RPDelta.Excess;
1824 break;
1825 case SingleCritical:
1826 P = Cand.RPDelta.CriticalMax;
1827 break;
1828 case SingleMax:
1829 P = Cand.RPDelta.CurrentMax;
1830 break;
1831 case ResourceReduce:
1832 ResIdx = Cand.Policy.ReduceResIdx;
1833 break;
1834 case ResourceDemand:
1835 ResIdx = Cand.Policy.DemandResIdx;
1836 break;
1837 case TopDepthReduce:
1838 Latency = Cand.SU->getDepth();
1839 break;
1840 case TopPathReduce:
1841 Latency = Cand.SU->getHeight();
1842 break;
1843 case BotHeightReduce:
1844 Latency = Cand.SU->getHeight();
1845 break;
1846 case BotPathReduce:
1847 Latency = Cand.SU->getDepth();
1848 break;
1849 }
1850 dbgs() << Label << " " << Zone.Available.getName() << " ";
1851 if (P.isValid())
1852 dbgs() << TRI->getRegPressureSetName(P.PSetID) << ":" << P.UnitIncrease
1853 << " ";
1854 else
1855 dbgs() << " ";
1856 if (ResIdx)
1857 dbgs() << SchedModel->getProcResource(ResIdx)->Name << " ";
1858 else
1859 dbgs() << " ";
1860 if (Latency)
1861 dbgs() << Latency << " cycles ";
1862 else
1863 dbgs() << " ";
1864 Cand.SU->dump(DAG);
1865}
1866#endif
1867
Andrew Trick7196a8f2012-05-10 21:06:16 +00001868/// Pick the best candidate from the top queue.
1869///
1870/// TODO: getMaxPressureDelta results can be mostly cached for each SUnit during
1871/// DAG building. To adjust for the current scheduling location we need to
1872/// maintain the number of vreg uses remaining to be top-scheduled.
Andrew Trick3b87f622012-11-07 07:05:09 +00001873void ConvergingScheduler::pickNodeFromQueue(SchedBoundary &Zone,
1874 const RegPressureTracker &RPTracker,
1875 SchedCandidate &Cand) {
1876 ReadyQueue &Q = Zone.Available;
1877
Andrew Trickf3234242012-05-24 22:11:12 +00001878 DEBUG(Q.dump());
Andrew Trick73a0d8e2012-05-17 18:35:10 +00001879
Andrew Trick7196a8f2012-05-10 21:06:16 +00001880 // getMaxPressureDelta temporarily modifies the tracker.
1881 RegPressureTracker &TempTracker = const_cast<RegPressureTracker&>(RPTracker);
1882
Andrew Trick8c2d9212012-05-24 22:11:03 +00001883 for (ReadyQueue::iterator I = Q.begin(), E = Q.end(); I != E; ++I) {
Andrew Trick7196a8f2012-05-10 21:06:16 +00001884
Andrew Trick3b87f622012-11-07 07:05:09 +00001885 SchedCandidate TryCand(Cand.Policy);
1886 TryCand.SU = *I;
1887 tryCandidate(Cand, TryCand, Zone, RPTracker, TempTracker);
1888 if (TryCand.Reason != NoCand) {
1889 // Initialize resource delta if needed in case future heuristics query it.
1890 if (TryCand.ResDelta == SchedResourceDelta())
1891 TryCand.initResourceDelta(DAG, SchedModel);
1892 Cand.setBest(TryCand);
1893 DEBUG(traceCandidate(Cand, Zone));
Andrew Trick73a0d8e2012-05-17 18:35:10 +00001894 }
Andrew Trick3b87f622012-11-07 07:05:09 +00001895 TryCand.SU = *I;
Andrew Trick7196a8f2012-05-10 21:06:16 +00001896 }
Andrew Trick3b87f622012-11-07 07:05:09 +00001897}
1898
1899static void tracePick(const ConvergingScheduler::SchedCandidate &Cand,
1900 bool IsTop) {
1901 DEBUG(dbgs() << "Pick " << (IsTop ? "top" : "bot")
1902 << " SU(" << Cand.SU->NodeNum << ") "
1903 << ConvergingScheduler::getReasonStr(Cand.Reason) << '\n');
Andrew Trick7196a8f2012-05-10 21:06:16 +00001904}
1905
Andrew Trick73a0d8e2012-05-17 18:35:10 +00001906/// Pick the best candidate node from either the top or bottom queue.
Andrew Trick3b87f622012-11-07 07:05:09 +00001907SUnit *ConvergingScheduler::pickNodeBidirectional(bool &IsTopNode) {
Andrew Trick73a0d8e2012-05-17 18:35:10 +00001908 // Schedule as far as possible in the direction of no choice. This is most
1909 // efficient, but also provides the best heuristics for CriticalPSets.
Andrew Trick0a39d4e2012-05-24 22:11:09 +00001910 if (SUnit *SU = Bot.pickOnlyChoice()) {
Andrew Trick73a0d8e2012-05-17 18:35:10 +00001911 IsTopNode = false;
Andrew Trick0a39d4e2012-05-24 22:11:09 +00001912 return SU;
Andrew Trick73a0d8e2012-05-17 18:35:10 +00001913 }
Andrew Trick0a39d4e2012-05-24 22:11:09 +00001914 if (SUnit *SU = Top.pickOnlyChoice()) {
Andrew Trick73a0d8e2012-05-17 18:35:10 +00001915 IsTopNode = true;
Andrew Trick0a39d4e2012-05-24 22:11:09 +00001916 return SU;
Andrew Trick73a0d8e2012-05-17 18:35:10 +00001917 }
Andrew Trick3b87f622012-11-07 07:05:09 +00001918 CandPolicy NoPolicy;
1919 SchedCandidate BotCand(NoPolicy);
1920 SchedCandidate TopCand(NoPolicy);
1921 checkResourceLimits(TopCand, BotCand);
1922
Andrew Trick73a0d8e2012-05-17 18:35:10 +00001923 // Prefer bottom scheduling when heuristics are silent.
Andrew Trick3b87f622012-11-07 07:05:09 +00001924 pickNodeFromQueue(Bot, DAG->getBotRPTracker(), BotCand);
1925 assert(BotCand.Reason != NoCand && "failed to find the first candidate");
Andrew Trick73a0d8e2012-05-17 18:35:10 +00001926
1927 // If either Q has a single candidate that provides the least increase in
1928 // Excess pressure, we can immediately schedule from that Q.
1929 //
1930 // RegionCriticalPSets summarizes the pressure within the scheduled region and
1931 // affects picking from either Q. If scheduling in one direction must
1932 // increase pressure for one of the excess PSets, then schedule in that
1933 // direction first to provide more freedom in the other direction.
Andrew Trick3b87f622012-11-07 07:05:09 +00001934 if (BotCand.Reason == SingleExcess || BotCand.Reason == SingleCritical) {
Andrew Trick73a0d8e2012-05-17 18:35:10 +00001935 IsTopNode = false;
Andrew Trick3b87f622012-11-07 07:05:09 +00001936 tracePick(BotCand, IsTopNode);
Andrew Trick0a39d4e2012-05-24 22:11:09 +00001937 return BotCand.SU;
Andrew Trick73a0d8e2012-05-17 18:35:10 +00001938 }
1939 // Check if the top Q has a better candidate.
Andrew Trick3b87f622012-11-07 07:05:09 +00001940 pickNodeFromQueue(Top, DAG->getTopRPTracker(), TopCand);
1941 assert(TopCand.Reason != NoCand && "failed to find the first candidate");
Andrew Trick73a0d8e2012-05-17 18:35:10 +00001942
Andrew Trick73a0d8e2012-05-17 18:35:10 +00001943 // If either Q has a single candidate that minimizes pressure above the
1944 // original region's pressure pick it.
Andrew Trick3b87f622012-11-07 07:05:09 +00001945 if (TopCand.Reason <= SingleMax || BotCand.Reason <= SingleMax) {
1946 if (TopCand.Reason < BotCand.Reason) {
1947 IsTopNode = true;
1948 tracePick(TopCand, IsTopNode);
1949 return TopCand.SU;
1950 }
Andrew Trick73a0d8e2012-05-17 18:35:10 +00001951 IsTopNode = false;
Andrew Trick3b87f622012-11-07 07:05:09 +00001952 tracePick(BotCand, IsTopNode);
Andrew Trick0a39d4e2012-05-24 22:11:09 +00001953 return BotCand.SU;
Andrew Trick73a0d8e2012-05-17 18:35:10 +00001954 }
Andrew Trick73a0d8e2012-05-17 18:35:10 +00001955 // Check for a salient pressure difference and pick the best from either side.
Andrew Trick0a39d4e2012-05-24 22:11:09 +00001956 if (compareRPDelta(TopCand.RPDelta, BotCand.RPDelta)) {
Andrew Trick73a0d8e2012-05-17 18:35:10 +00001957 IsTopNode = true;
Andrew Trick3b87f622012-11-07 07:05:09 +00001958 tracePick(TopCand, IsTopNode);
Andrew Trick0a39d4e2012-05-24 22:11:09 +00001959 return TopCand.SU;
Andrew Trick73a0d8e2012-05-17 18:35:10 +00001960 }
Andrew Trick3b87f622012-11-07 07:05:09 +00001961 // Otherwise prefer the bottom candidate, in node order if all else failed.
1962 if (TopCand.Reason < BotCand.Reason) {
1963 IsTopNode = true;
1964 tracePick(TopCand, IsTopNode);
1965 return TopCand.SU;
1966 }
Andrew Trick73a0d8e2012-05-17 18:35:10 +00001967 IsTopNode = false;
Andrew Trick3b87f622012-11-07 07:05:09 +00001968 tracePick(BotCand, IsTopNode);
Andrew Trick0a39d4e2012-05-24 22:11:09 +00001969 return BotCand.SU;
Andrew Trick73a0d8e2012-05-17 18:35:10 +00001970}
1971
1972/// Pick the best node to balance the schedule. Implements MachineSchedStrategy.
Andrew Trick7196a8f2012-05-10 21:06:16 +00001973SUnit *ConvergingScheduler::pickNode(bool &IsTopNode) {
1974 if (DAG->top() == DAG->bottom()) {
Andrew Trick0a39d4e2012-05-24 22:11:09 +00001975 assert(Top.Available.empty() && Top.Pending.empty() &&
1976 Bot.Available.empty() && Bot.Pending.empty() && "ReadyQ garbage");
Andrew Trick7196a8f2012-05-10 21:06:16 +00001977 return NULL;
1978 }
Andrew Trick7196a8f2012-05-10 21:06:16 +00001979 SUnit *SU;
Andrew Trick30c6ec22012-10-08 18:53:53 +00001980 do {
1981 if (ForceTopDown) {
1982 SU = Top.pickOnlyChoice();
1983 if (!SU) {
Andrew Trick3b87f622012-11-07 07:05:09 +00001984 CandPolicy NoPolicy;
1985 SchedCandidate TopCand(NoPolicy);
1986 pickNodeFromQueue(Top, DAG->getTopRPTracker(), TopCand);
1987 assert(TopCand.Reason != NoCand && "failed to find the first candidate");
Andrew Trick30c6ec22012-10-08 18:53:53 +00001988 SU = TopCand.SU;
1989 }
1990 IsTopNode = true;
Andrew Trick8ddd9d52012-05-24 23:11:17 +00001991 }
Andrew Trick30c6ec22012-10-08 18:53:53 +00001992 else if (ForceBottomUp) {
1993 SU = Bot.pickOnlyChoice();
1994 if (!SU) {
Andrew Trick3b87f622012-11-07 07:05:09 +00001995 CandPolicy NoPolicy;
1996 SchedCandidate BotCand(NoPolicy);
1997 pickNodeFromQueue(Bot, DAG->getBotRPTracker(), BotCand);
1998 assert(BotCand.Reason != NoCand && "failed to find the first candidate");
Andrew Trick30c6ec22012-10-08 18:53:53 +00001999 SU = BotCand.SU;
2000 }
2001 IsTopNode = false;
Andrew Trick8ddd9d52012-05-24 23:11:17 +00002002 }
Andrew Trick30c6ec22012-10-08 18:53:53 +00002003 else {
Andrew Trick3b87f622012-11-07 07:05:09 +00002004 SU = pickNodeBidirectional(IsTopNode);
Andrew Trick30c6ec22012-10-08 18:53:53 +00002005 }
2006 } while (SU->isScheduled);
2007
Andrew Trick0a39d4e2012-05-24 22:11:09 +00002008 if (SU->isTopReady())
2009 Top.removeReady(SU);
2010 if (SU->isBottomReady())
2011 Bot.removeReady(SU);
Andrew Trickc7a098f2012-05-25 02:02:39 +00002012
2013 DEBUG(dbgs() << "*** " << (IsTopNode ? "Top" : "Bottom")
2014 << " Scheduling Instruction in cycle "
2015 << (IsTopNode ? Top.CurrCycle : Bot.CurrCycle) << '\n';
2016 SU->dump(DAG));
Andrew Trick7196a8f2012-05-10 21:06:16 +00002017 return SU;
2018}
2019
Andrew Trick0a39d4e2012-05-24 22:11:09 +00002020/// Update the scheduler's state after scheduling a node. This is the same node
2021/// that was just returned by pickNode(). However, ScheduleDAGMI needs to update
Andrew Trickb7e02892012-06-05 21:11:27 +00002022/// it's state based on the current cycle before MachineSchedStrategy does.
Andrew Trick0a39d4e2012-05-24 22:11:09 +00002023void ConvergingScheduler::schedNode(SUnit *SU, bool IsTopNode) {
Andrew Trickb7e02892012-06-05 21:11:27 +00002024 if (IsTopNode) {
2025 SU->TopReadyCycle = Top.CurrCycle;
Andrew Trick7f8c74c2012-06-29 03:23:22 +00002026 Top.bumpNode(SU);
Andrew Trick0a39d4e2012-05-24 22:11:09 +00002027 }
Andrew Trickb7e02892012-06-05 21:11:27 +00002028 else {
2029 SU->BotReadyCycle = Bot.CurrCycle;
Andrew Trick7f8c74c2012-06-29 03:23:22 +00002030 Bot.bumpNode(SU);
Andrew Trick0a39d4e2012-05-24 22:11:09 +00002031 }
2032}
2033
Andrew Trick17d35e52012-03-14 04:00:41 +00002034/// Create the standard converging machine scheduler. This will be used as the
2035/// default scheduler if the target does not set a default.
2036static ScheduleDAGInstrs *createConvergingSched(MachineSchedContext *C) {
Benjamin Kramer689e0b42012-03-14 11:26:37 +00002037 assert((!ForceTopDown || !ForceBottomUp) &&
Andrew Trick17d35e52012-03-14 04:00:41 +00002038 "-misched-topdown incompatible with -misched-bottomup");
Andrew Trick9b5caaa2012-11-12 19:40:10 +00002039 ScheduleDAGMI *DAG = new ScheduleDAGMI(C, new ConvergingScheduler());
2040 // Register DAG post-processors.
2041 if (EnableLoadCluster)
2042 DAG->addMutation(new LoadClusterMutation(DAG->TII, DAG->TRI));
Andrew Trick6996fd02012-11-12 19:52:20 +00002043 if (EnableMacroFusion)
2044 DAG->addMutation(new MacroFusion(DAG->TII));
Andrew Trick9b5caaa2012-11-12 19:40:10 +00002045 return DAG;
Andrew Trick42b7a712012-01-17 06:55:03 +00002046}
2047static MachineSchedRegistry
Andrew Trick17d35e52012-03-14 04:00:41 +00002048ConvergingSchedRegistry("converge", "Standard converging scheduler.",
2049 createConvergingSched);
Andrew Trick42b7a712012-01-17 06:55:03 +00002050
2051//===----------------------------------------------------------------------===//
Andrew Trick1e94e982012-10-15 18:02:27 +00002052// ILP Scheduler. Currently for experimental analysis of heuristics.
2053//===----------------------------------------------------------------------===//
2054
2055namespace {
2056/// \brief Order nodes by the ILP metric.
2057struct ILPOrder {
2058 ScheduleDAGILP *ILP;
2059 bool MaximizeILP;
2060
2061 ILPOrder(ScheduleDAGILP *ilp, bool MaxILP): ILP(ilp), MaximizeILP(MaxILP) {}
2062
2063 /// \brief Apply a less-than relation on node priority.
2064 bool operator()(const SUnit *A, const SUnit *B) const {
2065 // Return true if A comes after B in the Q.
2066 if (MaximizeILP)
2067 return ILP->getILP(A) < ILP->getILP(B);
2068 else
2069 return ILP->getILP(A) > ILP->getILP(B);
2070 }
2071};
2072
2073/// \brief Schedule based on the ILP metric.
2074class ILPScheduler : public MachineSchedStrategy {
2075 ScheduleDAGILP ILP;
2076 ILPOrder Cmp;
2077
2078 std::vector<SUnit*> ReadyQ;
2079public:
2080 ILPScheduler(bool MaximizeILP)
2081 : ILP(/*BottomUp=*/true), Cmp(&ILP, MaximizeILP) {}
2082
2083 virtual void initialize(ScheduleDAGMI *DAG) {
2084 ReadyQ.clear();
2085 ILP.resize(DAG->SUnits.size());
2086 }
2087
2088 virtual void registerRoots() {
2089 for (std::vector<SUnit*>::const_iterator
2090 I = ReadyQ.begin(), E = ReadyQ.end(); I != E; ++I) {
2091 ILP.computeILP(*I);
2092 }
2093 }
2094
2095 /// Implement MachineSchedStrategy interface.
2096 /// -----------------------------------------
2097
2098 virtual SUnit *pickNode(bool &IsTopNode) {
2099 if (ReadyQ.empty()) return NULL;
2100 pop_heap(ReadyQ.begin(), ReadyQ.end(), Cmp);
2101 SUnit *SU = ReadyQ.back();
2102 ReadyQ.pop_back();
2103 IsTopNode = false;
2104 DEBUG(dbgs() << "*** Scheduling " << *SU->getInstr()
2105 << " ILP: " << ILP.getILP(SU) << '\n');
2106 return SU;
2107 }
2108
2109 virtual void schedNode(SUnit *, bool) {}
2110
2111 virtual void releaseTopNode(SUnit *) { /*only called for top roots*/ }
2112
2113 virtual void releaseBottomNode(SUnit *SU) {
2114 ReadyQ.push_back(SU);
2115 std::push_heap(ReadyQ.begin(), ReadyQ.end(), Cmp);
2116 }
2117};
2118} // namespace
2119
2120static ScheduleDAGInstrs *createILPMaxScheduler(MachineSchedContext *C) {
2121 return new ScheduleDAGMI(C, new ILPScheduler(true));
2122}
2123static ScheduleDAGInstrs *createILPMinScheduler(MachineSchedContext *C) {
2124 return new ScheduleDAGMI(C, new ILPScheduler(false));
2125}
2126static MachineSchedRegistry ILPMaxRegistry(
2127 "ilpmax", "Schedule bottom-up for max ILP", createILPMaxScheduler);
2128static MachineSchedRegistry ILPMinRegistry(
2129 "ilpmin", "Schedule bottom-up for min ILP", createILPMinScheduler);
2130
2131//===----------------------------------------------------------------------===//
Andrew Trick5edf2f02012-01-14 02:17:06 +00002132// Machine Instruction Shuffler for Correctness Testing
2133//===----------------------------------------------------------------------===//
2134
Andrew Trick96f678f2012-01-13 06:30:30 +00002135#ifndef NDEBUG
2136namespace {
Andrew Trick17d35e52012-03-14 04:00:41 +00002137/// Apply a less-than relation on the node order, which corresponds to the
2138/// instruction order prior to scheduling. IsReverse implements greater-than.
2139template<bool IsReverse>
2140struct SUnitOrder {
Andrew Trickc6cf11b2012-01-17 06:55:07 +00002141 bool operator()(SUnit *A, SUnit *B) const {
Andrew Trick17d35e52012-03-14 04:00:41 +00002142 if (IsReverse)
2143 return A->NodeNum > B->NodeNum;
2144 else
2145 return A->NodeNum < B->NodeNum;
Andrew Trickc6cf11b2012-01-17 06:55:07 +00002146 }
2147};
2148
Andrew Trick96f678f2012-01-13 06:30:30 +00002149/// Reorder instructions as much as possible.
Andrew Trick17d35e52012-03-14 04:00:41 +00002150class InstructionShuffler : public MachineSchedStrategy {
2151 bool IsAlternating;
2152 bool IsTopDown;
2153
2154 // Using a less-than relation (SUnitOrder<false>) for the TopQ priority
2155 // gives nodes with a higher number higher priority causing the latest
2156 // instructions to be scheduled first.
2157 PriorityQueue<SUnit*, std::vector<SUnit*>, SUnitOrder<false> >
2158 TopQ;
2159 // When scheduling bottom-up, use greater-than as the queue priority.
2160 PriorityQueue<SUnit*, std::vector<SUnit*>, SUnitOrder<true> >
2161 BottomQ;
Andrew Trick96f678f2012-01-13 06:30:30 +00002162public:
Andrew Trick17d35e52012-03-14 04:00:41 +00002163 InstructionShuffler(bool alternate, bool topdown)
2164 : IsAlternating(alternate), IsTopDown(topdown) {}
Andrew Trick96f678f2012-01-13 06:30:30 +00002165
Andrew Trick17d35e52012-03-14 04:00:41 +00002166 virtual void initialize(ScheduleDAGMI *) {
2167 TopQ.clear();
2168 BottomQ.clear();
2169 }
Andrew Trickc6cf11b2012-01-17 06:55:07 +00002170
Andrew Trick17d35e52012-03-14 04:00:41 +00002171 /// Implement MachineSchedStrategy interface.
2172 /// -----------------------------------------
2173
2174 virtual SUnit *pickNode(bool &IsTopNode) {
2175 SUnit *SU;
2176 if (IsTopDown) {
2177 do {
2178 if (TopQ.empty()) return NULL;
2179 SU = TopQ.top();
2180 TopQ.pop();
2181 } while (SU->isScheduled);
2182 IsTopNode = true;
2183 }
2184 else {
2185 do {
2186 if (BottomQ.empty()) return NULL;
2187 SU = BottomQ.top();
2188 BottomQ.pop();
2189 } while (SU->isScheduled);
2190 IsTopNode = false;
2191 }
2192 if (IsAlternating)
2193 IsTopDown = !IsTopDown;
Andrew Trickc6cf11b2012-01-17 06:55:07 +00002194 return SU;
2195 }
2196
Andrew Trick0a39d4e2012-05-24 22:11:09 +00002197 virtual void schedNode(SUnit *SU, bool IsTopNode) {}
2198
Andrew Trick17d35e52012-03-14 04:00:41 +00002199 virtual void releaseTopNode(SUnit *SU) {
2200 TopQ.push(SU);
2201 }
2202 virtual void releaseBottomNode(SUnit *SU) {
2203 BottomQ.push(SU);
Andrew Trick96f678f2012-01-13 06:30:30 +00002204 }
2205};
2206} // namespace
2207
Andrew Trickc174eaf2012-03-08 01:41:12 +00002208static ScheduleDAGInstrs *createInstructionShuffler(MachineSchedContext *C) {
Andrew Trick17d35e52012-03-14 04:00:41 +00002209 bool Alternate = !ForceTopDown && !ForceBottomUp;
2210 bool TopDown = !ForceBottomUp;
Benjamin Kramer689e0b42012-03-14 11:26:37 +00002211 assert((TopDown || !ForceTopDown) &&
Andrew Trick17d35e52012-03-14 04:00:41 +00002212 "-misched-topdown incompatible with -misched-bottomup");
2213 return new ScheduleDAGMI(C, new InstructionShuffler(Alternate, TopDown));
Andrew Trick96f678f2012-01-13 06:30:30 +00002214}
Andrew Trick17d35e52012-03-14 04:00:41 +00002215static MachineSchedRegistry ShufflerRegistry(
2216 "shuffle", "Shuffle machine instructions alternating directions",
2217 createInstructionShuffler);
Andrew Trick96f678f2012-01-13 06:30:30 +00002218#endif // !NDEBUG