blob: c9eefa15b23e9b95fbd9a1b6e03686b30877d820 [file] [log] [blame]
Andrew Trick6a50baa2012-05-17 22:37:09 +00001//===- MachineScheduler.cpp - Machine Instruction Scheduler ---------------===//
Andrew Tricke77e84e2012-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
Andrew Trick02a80da2012-03-08 01:41:12 +000015#include "llvm/CodeGen/MachineScheduler.h"
Chandler Carruthed0881b2012-12-03 16:50:05 +000016#include "llvm/ADT/PriorityQueue.h"
17#include "llvm/Analysis/AliasAnalysis.h"
18#include "llvm/CodeGen/LiveIntervalAnalysis.h"
Jakub Staszakdf17ddd2013-03-10 13:11:23 +000019#include "llvm/CodeGen/MachineDominators.h"
20#include "llvm/CodeGen/MachineLoopInfo.h"
Andrew Trick736dd9a2013-06-21 18:32:58 +000021#include "llvm/CodeGen/MachineRegisterInfo.h"
Andrew Tricke77e84e2012-01-13 06:30:30 +000022#include "llvm/CodeGen/Passes.h"
Andrew Trick05ff4662012-06-06 20:29:31 +000023#include "llvm/CodeGen/RegisterClassInfo.h"
Andrew Trickcd1c2f92012-11-28 05:13:24 +000024#include "llvm/CodeGen/ScheduleDFS.h"
Andrew Trick61f1a272012-05-24 22:11:09 +000025#include "llvm/CodeGen/ScheduleHazardRecognizer.h"
Andrew Tricke77e84e2012-01-13 06:30:30 +000026#include "llvm/Support/CommandLine.h"
27#include "llvm/Support/Debug.h"
28#include "llvm/Support/ErrorHandling.h"
Andrew Trickea9fd952013-01-25 07:45:29 +000029#include "llvm/Support/GraphWriter.h"
Andrew Tricke77e84e2012-01-13 06:30:30 +000030#include "llvm/Support/raw_ostream.h"
Jakub Staszak80df8b82013-06-14 00:00:13 +000031#include "llvm/Target/TargetInstrInfo.h"
Andrew Trick7ccdc5c2012-01-17 06:55:07 +000032#include <queue>
33
Andrew Tricke77e84e2012-01-13 06:30:30 +000034using namespace llvm;
35
Chandler Carruth1b9dde02014-04-22 02:02:50 +000036#define DEBUG_TYPE "misched"
37
Andrew Trick7a8e1002012-09-11 00:39:15 +000038namespace llvm {
39cl::opt<bool> ForceTopDown("misched-topdown", cl::Hidden,
40 cl::desc("Force top-down list scheduling"));
41cl::opt<bool> ForceBottomUp("misched-bottomup", cl::Hidden,
42 cl::desc("Force bottom-up list scheduling"));
43}
Andrew Trick8823dec2012-03-14 04:00:41 +000044
Andrew Tricka5f19562012-03-07 00:18:25 +000045#ifndef NDEBUG
46static cl::opt<bool> ViewMISchedDAGs("view-misched-dags", cl::Hidden,
47 cl::desc("Pop up a window to show MISched dags after they are processed"));
Lang Hamesdd98c492012-03-19 18:38:38 +000048
49static cl::opt<unsigned> MISchedCutoff("misched-cutoff", cl::Hidden,
50 cl::desc("Stop scheduling after N instructions"), cl::init(~0U));
Andrew Trick33e05d72013-12-28 21:57:02 +000051
52static cl::opt<std::string> SchedOnlyFunc("misched-only-func", cl::Hidden,
53 cl::desc("Only schedule this function"));
54static cl::opt<unsigned> SchedOnlyBlock("misched-only-block", cl::Hidden,
55 cl::desc("Only schedule this MBB#"));
Andrew Tricka5f19562012-03-07 00:18:25 +000056#else
57static bool ViewMISchedDAGs = false;
58#endif // NDEBUG
59
Andrew Trickb6e74712013-09-04 20:59:59 +000060static cl::opt<bool> EnableRegPressure("misched-regpressure", cl::Hidden,
61 cl::desc("Enable register pressure scheduling."), cl::init(true));
62
Andrew Trickc01b0042013-08-23 17:48:43 +000063static cl::opt<bool> EnableCyclicPath("misched-cyclicpath", cl::Hidden,
Andrew Trick6c88b352013-09-09 23:31:14 +000064 cl::desc("Enable cyclic critical path analysis."), cl::init(true));
Andrew Trickc01b0042013-08-23 17:48:43 +000065
Andrew Tricka7714a02012-11-12 19:40:10 +000066static cl::opt<bool> EnableLoadCluster("misched-cluster", cl::Hidden,
Andrew Trick108c88c2012-11-13 08:47:29 +000067 cl::desc("Enable load clustering."), cl::init(true));
Andrew Tricka7714a02012-11-12 19:40:10 +000068
Andrew Trick263280242012-11-12 19:52:20 +000069// Experimental heuristics
70static cl::opt<bool> EnableMacroFusion("misched-fusion", cl::Hidden,
Andrew Trick108c88c2012-11-13 08:47:29 +000071 cl::desc("Enable scheduling for macro fusion."), cl::init(true));
Andrew Trick263280242012-11-12 19:52:20 +000072
Andrew Trick48f2a722013-03-08 05:40:34 +000073static cl::opt<bool> VerifyScheduling("verify-misched", cl::Hidden,
74 cl::desc("Verify machine instrs before and after machine scheduling"));
75
Andrew Trick44f750a2013-01-25 04:01:04 +000076// DAG subtrees must have at least this many nodes.
77static const unsigned MinSubtreeSize = 8;
78
Juergen Ributzkad12ccbd2013-11-19 00:57:56 +000079// Pin the vtables to this file.
80void MachineSchedStrategy::anchor() {}
81void ScheduleDAGMutation::anchor() {}
82
Andrew Trick63440872012-01-14 02:17:06 +000083//===----------------------------------------------------------------------===//
84// Machine Instruction Scheduling Pass and Registry
85//===----------------------------------------------------------------------===//
86
Andrew Trick4d4b5462012-04-24 20:36:19 +000087MachineSchedContext::MachineSchedContext():
Craig Topperc0196b12014-04-14 00:51:57 +000088 MF(nullptr), MLI(nullptr), MDT(nullptr), PassConfig(nullptr), AA(nullptr), LIS(nullptr) {
Andrew Trick4d4b5462012-04-24 20:36:19 +000089 RegClassInfo = new RegisterClassInfo();
90}
91
92MachineSchedContext::~MachineSchedContext() {
93 delete RegClassInfo;
94}
95
Andrew Tricke77e84e2012-01-13 06:30:30 +000096namespace {
Andrew Trickd7f890e2013-12-28 21:56:47 +000097/// Base class for a machine scheduler class that can run at any point.
98class MachineSchedulerBase : public MachineSchedContext,
99 public MachineFunctionPass {
100public:
101 MachineSchedulerBase(char &ID): MachineFunctionPass(ID) {}
102
Craig Topperc0196b12014-04-14 00:51:57 +0000103 void print(raw_ostream &O, const Module* = nullptr) const override;
Andrew Trickd7f890e2013-12-28 21:56:47 +0000104
105protected:
106 void scheduleRegions(ScheduleDAGInstrs &Scheduler);
107};
108
Andrew Tricke1c034f2012-01-17 06:55:03 +0000109/// MachineScheduler runs after coalescing and before register allocation.
Andrew Trickd7f890e2013-12-28 21:56:47 +0000110class MachineScheduler : public MachineSchedulerBase {
Andrew Tricke77e84e2012-01-13 06:30:30 +0000111public:
Andrew Tricke1c034f2012-01-17 06:55:03 +0000112 MachineScheduler();
Andrew Tricke77e84e2012-01-13 06:30:30 +0000113
Craig Topper4584cd52014-03-07 09:26:03 +0000114 void getAnalysisUsage(AnalysisUsage &AU) const override;
Andrew Tricke77e84e2012-01-13 06:30:30 +0000115
Craig Topper4584cd52014-03-07 09:26:03 +0000116 bool runOnMachineFunction(MachineFunction&) override;
Andrew Tricke77e84e2012-01-13 06:30:30 +0000117
Andrew Tricke77e84e2012-01-13 06:30:30 +0000118 static char ID; // Class identification, replacement for typeinfo
Andrew Trick978674b2013-09-20 05:14:41 +0000119
120protected:
121 ScheduleDAGInstrs *createMachineScheduler();
Andrew Tricke77e84e2012-01-13 06:30:30 +0000122};
Andrew Trick17080b92013-12-28 21:56:51 +0000123
124/// PostMachineScheduler runs after shortly before code emission.
125class PostMachineScheduler : public MachineSchedulerBase {
126public:
127 PostMachineScheduler();
128
Craig Topper4584cd52014-03-07 09:26:03 +0000129 void getAnalysisUsage(AnalysisUsage &AU) const override;
Andrew Trick17080b92013-12-28 21:56:51 +0000130
Craig Topper4584cd52014-03-07 09:26:03 +0000131 bool runOnMachineFunction(MachineFunction&) override;
Andrew Trick17080b92013-12-28 21:56:51 +0000132
133 static char ID; // Class identification, replacement for typeinfo
134
135protected:
136 ScheduleDAGInstrs *createPostMachineScheduler();
137};
Andrew Tricke77e84e2012-01-13 06:30:30 +0000138} // namespace
139
Andrew Tricke1c034f2012-01-17 06:55:03 +0000140char MachineScheduler::ID = 0;
Andrew Tricke77e84e2012-01-13 06:30:30 +0000141
Andrew Tricke1c034f2012-01-17 06:55:03 +0000142char &llvm::MachineSchedulerID = MachineScheduler::ID;
Andrew Tricke77e84e2012-01-13 06:30:30 +0000143
Andrew Tricke1c034f2012-01-17 06:55:03 +0000144INITIALIZE_PASS_BEGIN(MachineScheduler, "misched",
Andrew Tricke77e84e2012-01-13 06:30:30 +0000145 "Machine Instruction Scheduler", false, false)
146INITIALIZE_AG_DEPENDENCY(AliasAnalysis)
147INITIALIZE_PASS_DEPENDENCY(SlotIndexes)
148INITIALIZE_PASS_DEPENDENCY(LiveIntervals)
Andrew Tricke1c034f2012-01-17 06:55:03 +0000149INITIALIZE_PASS_END(MachineScheduler, "misched",
Andrew Tricke77e84e2012-01-13 06:30:30 +0000150 "Machine Instruction Scheduler", false, false)
151
Andrew Tricke1c034f2012-01-17 06:55:03 +0000152MachineScheduler::MachineScheduler()
Andrew Trickd7f890e2013-12-28 21:56:47 +0000153: MachineSchedulerBase(ID) {
Andrew Tricke1c034f2012-01-17 06:55:03 +0000154 initializeMachineSchedulerPass(*PassRegistry::getPassRegistry());
Andrew Tricke77e84e2012-01-13 06:30:30 +0000155}
156
Andrew Tricke1c034f2012-01-17 06:55:03 +0000157void MachineScheduler::getAnalysisUsage(AnalysisUsage &AU) const {
Andrew Tricke77e84e2012-01-13 06:30:30 +0000158 AU.setPreservesCFG();
159 AU.addRequiredID(MachineDominatorsID);
160 AU.addRequired<MachineLoopInfo>();
161 AU.addRequired<AliasAnalysis>();
Andrew Trick45300682012-03-09 00:52:20 +0000162 AU.addRequired<TargetPassConfig>();
Andrew Tricke77e84e2012-01-13 06:30:30 +0000163 AU.addRequired<SlotIndexes>();
164 AU.addPreserved<SlotIndexes>();
165 AU.addRequired<LiveIntervals>();
166 AU.addPreserved<LiveIntervals>();
Andrew Tricke77e84e2012-01-13 06:30:30 +0000167 MachineFunctionPass::getAnalysisUsage(AU);
168}
169
Andrew Trick17080b92013-12-28 21:56:51 +0000170char PostMachineScheduler::ID = 0;
171
172char &llvm::PostMachineSchedulerID = PostMachineScheduler::ID;
173
174INITIALIZE_PASS(PostMachineScheduler, "postmisched",
Saleem Abdulrasool7230b372013-12-28 22:47:55 +0000175 "PostRA Machine Instruction Scheduler", false, false)
Andrew Trick17080b92013-12-28 21:56:51 +0000176
177PostMachineScheduler::PostMachineScheduler()
178: MachineSchedulerBase(ID) {
179 initializePostMachineSchedulerPass(*PassRegistry::getPassRegistry());
180}
181
182void PostMachineScheduler::getAnalysisUsage(AnalysisUsage &AU) const {
183 AU.setPreservesCFG();
184 AU.addRequiredID(MachineDominatorsID);
185 AU.addRequired<MachineLoopInfo>();
186 AU.addRequired<TargetPassConfig>();
187 MachineFunctionPass::getAnalysisUsage(AU);
188}
189
Andrew Tricke77e84e2012-01-13 06:30:30 +0000190MachinePassRegistry MachineSchedRegistry::Registry;
191
Andrew Trick45300682012-03-09 00:52:20 +0000192/// A dummy default scheduler factory indicates whether the scheduler
193/// is overridden on the command line.
194static ScheduleDAGInstrs *useDefaultMachineSched(MachineSchedContext *C) {
Craig Topperc0196b12014-04-14 00:51:57 +0000195 return nullptr;
Andrew Trick45300682012-03-09 00:52:20 +0000196}
Andrew Tricke77e84e2012-01-13 06:30:30 +0000197
198/// MachineSchedOpt allows command line selection of the scheduler.
199static cl::opt<MachineSchedRegistry::ScheduleDAGCtor, false,
200 RegisterPassParser<MachineSchedRegistry> >
201MachineSchedOpt("misched",
Andrew Trick45300682012-03-09 00:52:20 +0000202 cl::init(&useDefaultMachineSched), cl::Hidden,
Andrew Tricke77e84e2012-01-13 06:30:30 +0000203 cl::desc("Machine instruction scheduler to use"));
204
Andrew Trick45300682012-03-09 00:52:20 +0000205static MachineSchedRegistry
Andrew Trick8823dec2012-03-14 04:00:41 +0000206DefaultSchedRegistry("default", "Use the target's default scheduler choice.",
Andrew Trick45300682012-03-09 00:52:20 +0000207 useDefaultMachineSched);
208
Andrew Trick8823dec2012-03-14 04:00:41 +0000209/// Forward declare the standard machine scheduler. This will be used as the
Andrew Trick45300682012-03-09 00:52:20 +0000210/// default scheduler if the target does not set a default.
Andrew Trickd14d7c22013-12-28 21:56:57 +0000211static ScheduleDAGInstrs *createGenericSchedLive(MachineSchedContext *C);
212static ScheduleDAGInstrs *createGenericSchedPostRA(MachineSchedContext *C);
Andrew Trickcc45a282012-04-24 18:04:34 +0000213
214/// Decrement this iterator until reaching the top or a non-debug instr.
Andrew Trick2bc74c22013-08-30 04:36:57 +0000215static MachineBasicBlock::const_iterator
216priorNonDebug(MachineBasicBlock::const_iterator I,
217 MachineBasicBlock::const_iterator Beg) {
Andrew Trickcc45a282012-04-24 18:04:34 +0000218 assert(I != Beg && "reached the top of the region, cannot decrement");
219 while (--I != Beg) {
220 if (!I->isDebugValue())
221 break;
222 }
223 return I;
224}
225
Andrew Trick2bc74c22013-08-30 04:36:57 +0000226/// Non-const version.
227static MachineBasicBlock::iterator
228priorNonDebug(MachineBasicBlock::iterator I,
229 MachineBasicBlock::const_iterator Beg) {
230 return const_cast<MachineInstr*>(
231 &*priorNonDebug(MachineBasicBlock::const_iterator(I), Beg));
232}
233
Andrew Trickcc45a282012-04-24 18:04:34 +0000234/// If this iterator is a debug value, increment until reaching the End or a
235/// non-debug instruction.
Andrew Trick2c4f8b72013-08-31 05:17:58 +0000236static MachineBasicBlock::const_iterator
237nextIfDebug(MachineBasicBlock::const_iterator I,
238 MachineBasicBlock::const_iterator End) {
Andrew Trick463b2f12012-05-17 18:35:03 +0000239 for(; I != End; ++I) {
Andrew Trickcc45a282012-04-24 18:04:34 +0000240 if (!I->isDebugValue())
241 break;
242 }
243 return I;
244}
245
Andrew Trick2c4f8b72013-08-31 05:17:58 +0000246/// Non-const version.
247static MachineBasicBlock::iterator
248nextIfDebug(MachineBasicBlock::iterator I,
249 MachineBasicBlock::const_iterator End) {
250 // Cast the return value to nonconst MachineInstr, then cast to an
251 // instr_iterator, which does not check for null, finally return a
252 // bundle_iterator.
253 return MachineBasicBlock::instr_iterator(
254 const_cast<MachineInstr*>(
255 &*nextIfDebug(MachineBasicBlock::const_iterator(I), End)));
256}
257
Andrew Trickdc4c1ad2013-09-24 17:11:19 +0000258/// Instantiate a ScheduleDAGInstrs that will be owned by the caller.
Andrew Trick978674b2013-09-20 05:14:41 +0000259ScheduleDAGInstrs *MachineScheduler::createMachineScheduler() {
260 // Select the scheduler, or set the default.
261 MachineSchedRegistry::ScheduleDAGCtor Ctor = MachineSchedOpt;
262 if (Ctor != useDefaultMachineSched)
263 return Ctor(this);
264
265 // Get the default scheduler set by the target for this function.
266 ScheduleDAGInstrs *Scheduler = PassConfig->createMachineScheduler(this);
267 if (Scheduler)
268 return Scheduler;
269
270 // Default to GenericScheduler.
Andrew Trickd14d7c22013-12-28 21:56:57 +0000271 return createGenericSchedLive(this);
Andrew Trick978674b2013-09-20 05:14:41 +0000272}
273
Andrew Trick17080b92013-12-28 21:56:51 +0000274/// Instantiate a ScheduleDAGInstrs for PostRA scheduling that will be owned by
275/// the caller. We don't have a command line option to override the postRA
276/// scheduler. The Target must configure it.
277ScheduleDAGInstrs *PostMachineScheduler::createPostMachineScheduler() {
278 // Get the postRA scheduler set by the target for this function.
279 ScheduleDAGInstrs *Scheduler = PassConfig->createPostMachineScheduler(this);
280 if (Scheduler)
281 return Scheduler;
282
283 // Default to GenericScheduler.
Andrew Trickd14d7c22013-12-28 21:56:57 +0000284 return createGenericSchedPostRA(this);
Andrew Trick17080b92013-12-28 21:56:51 +0000285}
286
Andrew Trick72515be2012-03-14 04:00:38 +0000287/// Top-level MachineScheduler pass driver.
288///
289/// Visit blocks in function order. Divide each block into scheduling regions
Andrew Trick8823dec2012-03-14 04:00:41 +0000290/// and visit them bottom-up. Visiting regions bottom-up is not required, but is
291/// consistent with the DAG builder, which traverses the interior of the
292/// scheduling regions bottom-up.
Andrew Trick72515be2012-03-14 04:00:38 +0000293///
294/// This design avoids exposing scheduling boundaries to the DAG builder,
Andrew Trick8823dec2012-03-14 04:00:41 +0000295/// simplifying the DAG builder's support for "special" target instructions.
296/// At the same time the design allows target schedulers to operate across
Andrew Trick72515be2012-03-14 04:00:38 +0000297/// scheduling boundaries, for example to bundle the boudary instructions
298/// without reordering them. This creates complexity, because the target
299/// scheduler must update the RegionBegin and RegionEnd positions cached by
300/// ScheduleDAGInstrs whenever adding or removing instructions. A much simpler
301/// design would be to split blocks at scheduling boundaries, but LLVM has a
302/// general bias against block splitting purely for implementation simplicity.
Andrew Tricke1c034f2012-01-17 06:55:03 +0000303bool MachineScheduler::runOnMachineFunction(MachineFunction &mf) {
Andrew Trickc5d70082012-05-10 21:06:21 +0000304 DEBUG(dbgs() << "Before MISsched:\n"; mf.print(dbgs()));
305
Andrew Tricke77e84e2012-01-13 06:30:30 +0000306 // Initialize the context of the pass.
307 MF = &mf;
308 MLI = &getAnalysis<MachineLoopInfo>();
309 MDT = &getAnalysis<MachineDominatorTree>();
Andrew Trick45300682012-03-09 00:52:20 +0000310 PassConfig = &getAnalysis<TargetPassConfig>();
Andrew Trick02a80da2012-03-08 01:41:12 +0000311 AA = &getAnalysis<AliasAnalysis>();
312
Lang Hamesad33d5a2012-01-27 22:36:19 +0000313 LIS = &getAnalysis<LiveIntervals>();
Andrew Tricke77e84e2012-01-13 06:30:30 +0000314
Andrew Trick48f2a722013-03-08 05:40:34 +0000315 if (VerifyScheduling) {
Andrew Trick97064962013-07-25 07:26:26 +0000316 DEBUG(LIS->dump());
Andrew Trick48f2a722013-03-08 05:40:34 +0000317 MF->verify(this, "Before machine scheduling.");
318 }
Andrew Trick4d4b5462012-04-24 20:36:19 +0000319 RegClassInfo->runOnMachineFunction(*MF);
Andrew Trick88639922012-04-24 17:56:43 +0000320
Andrew Trick978674b2013-09-20 05:14:41 +0000321 // Instantiate the selected scheduler for this target, function, and
322 // optimization level.
Ahmed Charles56440fd2014-03-06 05:51:42 +0000323 std::unique_ptr<ScheduleDAGInstrs> Scheduler(createMachineScheduler());
Andrew Trickd7f890e2013-12-28 21:56:47 +0000324 scheduleRegions(*Scheduler);
325
326 DEBUG(LIS->dump());
327 if (VerifyScheduling)
328 MF->verify(this, "After machine scheduling.");
329 return true;
330}
331
Andrew Trick17080b92013-12-28 21:56:51 +0000332bool PostMachineScheduler::runOnMachineFunction(MachineFunction &mf) {
Paul Robinson7c99ec52014-03-31 17:43:35 +0000333 if (skipOptnoneFunction(*mf.getFunction()))
334 return false;
335
Andrew Trick8d2ee372014-06-04 07:06:27 +0000336 const TargetSubtargetInfo &ST =
337 mf.getTarget().getSubtarget<TargetSubtargetInfo>();
338 if (!ST.enablePostMachineScheduler()) {
339 DEBUG(dbgs() << "Subtarget disables post-MI-sched.\n");
340 return false;
341 }
Andrew Trick17080b92013-12-28 21:56:51 +0000342 DEBUG(dbgs() << "Before post-MI-sched:\n"; mf.print(dbgs()));
343
344 // Initialize the context of the pass.
345 MF = &mf;
346 PassConfig = &getAnalysis<TargetPassConfig>();
347
348 if (VerifyScheduling)
349 MF->verify(this, "Before post machine scheduling.");
350
351 // Instantiate the selected scheduler for this target, function, and
352 // optimization level.
Ahmed Charles56440fd2014-03-06 05:51:42 +0000353 std::unique_ptr<ScheduleDAGInstrs> Scheduler(createPostMachineScheduler());
Andrew Trick17080b92013-12-28 21:56:51 +0000354 scheduleRegions(*Scheduler);
355
356 if (VerifyScheduling)
357 MF->verify(this, "After post machine scheduling.");
358 return true;
359}
360
Andrew Trickd14d7c22013-12-28 21:56:57 +0000361/// Return true of the given instruction should not be included in a scheduling
362/// region.
363///
364/// MachineScheduler does not currently support scheduling across calls. To
365/// handle calls, the DAG builder needs to be modified to create register
366/// anti/output dependencies on the registers clobbered by the call's regmask
367/// operand. In PreRA scheduling, the stack pointer adjustment already prevents
368/// scheduling across calls. In PostRA scheduling, we need the isCall to enforce
369/// the boundary, but there would be no benefit to postRA scheduling across
370/// calls this late anyway.
371static bool isSchedBoundary(MachineBasicBlock::iterator MI,
372 MachineBasicBlock *MBB,
373 MachineFunction *MF,
374 const TargetInstrInfo *TII,
375 bool IsPostRA) {
376 return MI->isCall() || TII->isSchedulingBoundary(MI, MBB, *MF);
377}
378
Andrew Trickd7f890e2013-12-28 21:56:47 +0000379/// Main driver for both MachineScheduler and PostMachineScheduler.
380void MachineSchedulerBase::scheduleRegions(ScheduleDAGInstrs &Scheduler) {
Eric Christopherd9134482014-08-04 21:25:23 +0000381 const TargetInstrInfo *TII =
382 MF->getTarget().getSubtargetImpl()->getInstrInfo();
Andrew Trickd14d7c22013-12-28 21:56:57 +0000383 bool IsPostRA = Scheduler.isPostRA();
Andrew Tricke77e84e2012-01-13 06:30:30 +0000384
385 // Visit all machine basic blocks.
Andrew Trick88639922012-04-24 17:56:43 +0000386 //
387 // TODO: Visit blocks in global postorder or postorder within the bottom-up
388 // loop tree. Then we can optionally compute global RegPressure.
Andrew Tricke77e84e2012-01-13 06:30:30 +0000389 for (MachineFunction::iterator MBB = MF->begin(), MBBEnd = MF->end();
390 MBB != MBBEnd; ++MBB) {
391
Andrew Trickd7f890e2013-12-28 21:56:47 +0000392 Scheduler.startBlock(MBB);
Andrew Trickedfe2ec2012-03-09 08:02:51 +0000393
Andrew Trick33e05d72013-12-28 21:57:02 +0000394#ifndef NDEBUG
395 if (SchedOnlyFunc.getNumOccurrences() && SchedOnlyFunc != MF->getName())
396 continue;
397 if (SchedOnlyBlock.getNumOccurrences()
398 && (int)SchedOnlyBlock != MBB->getNumber())
399 continue;
400#endif
401
Andrew Trick7e120f42012-01-14 02:17:09 +0000402 // Break the block into scheduling regions [I, RegionEnd), and schedule each
Sylvestre Ledru35521e22012-07-23 08:51:15 +0000403 // region as soon as it is discovered. RegionEnd points the scheduling
Andrew Trickaf1bee72012-03-09 22:34:56 +0000404 // boundary at the bottom of the region. The DAG does not include RegionEnd,
405 // but the region does (i.e. the next RegionEnd is above the previous
406 // RegionBegin). If the current block has no terminator then RegionEnd ==
407 // MBB->end() for the bottom region.
408 //
409 // The Scheduler may insert instructions during either schedule() or
410 // exitRegion(), even for empty regions. So the local iterators 'I' and
411 // 'RegionEnd' are invalid across these calls.
Andrew Trickd14d7c22013-12-28 21:56:57 +0000412 //
413 // MBB::size() uses instr_iterator to count. Here we need a bundle to count
414 // as a single instruction.
415 unsigned RemainingInstrs = std::distance(MBB->begin(), MBB->end());
Andrew Tricka21daf72012-03-09 03:46:39 +0000416 for(MachineBasicBlock::iterator RegionEnd = MBB->end();
Andrew Trickd7f890e2013-12-28 21:56:47 +0000417 RegionEnd != MBB->begin(); RegionEnd = Scheduler.begin()) {
Andrew Trick88639922012-04-24 17:56:43 +0000418
Andrew Trickedfe2ec2012-03-09 08:02:51 +0000419 // Avoid decrementing RegionEnd for blocks with no terminator.
Benjamin Kramerb6d0bd42014-03-02 12:27:27 +0000420 if (RegionEnd != MBB->end() ||
421 isSchedBoundary(std::prev(RegionEnd), MBB, MF, TII, IsPostRA)) {
Andrew Trickedfe2ec2012-03-09 08:02:51 +0000422 --RegionEnd;
423 // Count the boundary instruction.
Andrew Trick4d1fa712012-11-06 07:10:34 +0000424 --RemainingInstrs;
Andrew Trickedfe2ec2012-03-09 08:02:51 +0000425 }
426
Andrew Trick7e120f42012-01-14 02:17:09 +0000427 // The next region starts above the previous region. Look backward in the
428 // instruction stream until we find the nearest boundary.
Andrew Tricka53e1012013-08-23 17:48:33 +0000429 unsigned NumRegionInstrs = 0;
Andrew Trick7e120f42012-01-14 02:17:09 +0000430 MachineBasicBlock::iterator I = RegionEnd;
Andrew Tricka53e1012013-08-23 17:48:33 +0000431 for(;I != MBB->begin(); --I, --RemainingInstrs, ++NumRegionInstrs) {
Benjamin Kramerb6d0bd42014-03-02 12:27:27 +0000432 if (isSchedBoundary(std::prev(I), MBB, MF, TII, IsPostRA))
Andrew Trick7e120f42012-01-14 02:17:09 +0000433 break;
434 }
Andrew Trick60cf03e2012-03-07 05:21:52 +0000435 // Notify the scheduler of the region, even if we may skip scheduling
436 // it. Perhaps it still needs to be bundled.
Andrew Trickd7f890e2013-12-28 21:56:47 +0000437 Scheduler.enterRegion(MBB, I, RegionEnd, NumRegionInstrs);
Andrew Trick60cf03e2012-03-07 05:21:52 +0000438
439 // Skip empty scheduling regions (0 or 1 schedulable instructions).
Benjamin Kramerb6d0bd42014-03-02 12:27:27 +0000440 if (I == RegionEnd || I == std::prev(RegionEnd)) {
Andrew Trick60cf03e2012-03-07 05:21:52 +0000441 // Close the current region. Bundle the terminator if needed.
Andrew Trickaf1bee72012-03-09 22:34:56 +0000442 // This invalidates 'RegionEnd' and 'I'.
Andrew Trickd7f890e2013-12-28 21:56:47 +0000443 Scheduler.exitRegion();
Andrew Trick7ccdc5c2012-01-17 06:55:07 +0000444 continue;
Andrew Trick59ac4fb2012-01-14 02:17:18 +0000445 }
Andrew Trickd14d7c22013-12-28 21:56:57 +0000446 DEBUG(dbgs() << "********** " << ((Scheduler.isPostRA()) ? "PostRA " : "")
447 << "MI Scheduling **********\n");
Craig Toppera538d832012-08-22 06:07:19 +0000448 DEBUG(dbgs() << MF->getName()
Andrew Trick54b2ce32013-01-25 07:45:31 +0000449 << ":BB#" << MBB->getNumber() << " " << MBB->getName()
450 << "\n From: " << *I << " To: ";
Andrew Tricke57583a2012-02-08 02:17:21 +0000451 if (RegionEnd != MBB->end()) dbgs() << *RegionEnd;
452 else dbgs() << "End";
Andrew Tricka53e1012013-08-23 17:48:33 +0000453 dbgs() << " RegionInstrs: " << NumRegionInstrs
454 << " Remaining: " << RemainingInstrs << "\n");
Andrew Trick7ccdc5c2012-01-17 06:55:07 +0000455
Andrew Trick1c0ec452012-03-09 03:46:42 +0000456 // Schedule a region: possibly reorder instructions.
Andrew Trickaf1bee72012-03-09 22:34:56 +0000457 // This invalidates 'RegionEnd' and 'I'.
Andrew Trickd7f890e2013-12-28 21:56:47 +0000458 Scheduler.schedule();
Andrew Trick1c0ec452012-03-09 03:46:42 +0000459
460 // Close the current region.
Andrew Trickd7f890e2013-12-28 21:56:47 +0000461 Scheduler.exitRegion();
Andrew Trick60cf03e2012-03-07 05:21:52 +0000462
463 // Scheduling has invalidated the current iterator 'I'. Ask the
464 // scheduler for the top of it's scheduled region.
Andrew Trickd7f890e2013-12-28 21:56:47 +0000465 RegionEnd = Scheduler.begin();
Andrew Trick7e120f42012-01-14 02:17:09 +0000466 }
Andrew Trick4d1fa712012-11-06 07:10:34 +0000467 assert(RemainingInstrs == 0 && "Instruction count mismatch!");
Andrew Trickd7f890e2013-12-28 21:56:47 +0000468 Scheduler.finishBlock();
Andrew Trickd14d7c22013-12-28 21:56:57 +0000469 if (Scheduler.isPostRA()) {
470 // FIXME: Ideally, no further passes should rely on kill flags. However,
471 // thumb2 size reduction is currently an exception.
472 Scheduler.fixupKills(MBB);
473 }
Andrew Tricke77e84e2012-01-13 06:30:30 +0000474 }
Andrew Trickd7f890e2013-12-28 21:56:47 +0000475 Scheduler.finalizeSchedule();
Andrew Tricke77e84e2012-01-13 06:30:30 +0000476}
477
Andrew Trickd7f890e2013-12-28 21:56:47 +0000478void MachineSchedulerBase::print(raw_ostream &O, const Module* m) const {
Andrew Tricke77e84e2012-01-13 06:30:30 +0000479 // unimplemented
480}
481
Alp Tokerd8d510a2014-07-01 21:19:13 +0000482LLVM_DUMP_METHOD
Andrew Trick7a8e1002012-09-11 00:39:15 +0000483void ReadyQueue::dump() {
Andrew Trickd40d0f22013-06-17 21:45:05 +0000484 dbgs() << Name << ": ";
Andrew Trick7a8e1002012-09-11 00:39:15 +0000485 for (unsigned i = 0, e = Queue.size(); i < e; ++i)
486 dbgs() << Queue[i]->NodeNum << " ";
487 dbgs() << "\n";
488}
Andrew Trick8823dec2012-03-14 04:00:41 +0000489
490//===----------------------------------------------------------------------===//
Andrew Trickd7f890e2013-12-28 21:56:47 +0000491// ScheduleDAGMI - Basic machine instruction scheduling. This is
492// independent of PreRA/PostRA scheduling and involves no extra book-keeping for
493// virtual registers.
494// ===----------------------------------------------------------------------===/
Andrew Trick8823dec2012-03-14 04:00:41 +0000495
David Blaikie422b93d2014-04-21 20:32:32 +0000496// Provide a vtable anchor.
Andrew Trick44f750a2013-01-25 04:01:04 +0000497ScheduleDAGMI::~ScheduleDAGMI() {
Andrew Trick44f750a2013-01-25 04:01:04 +0000498}
499
Andrew Trick85a1d4c2013-04-24 15:54:43 +0000500bool ScheduleDAGMI::canAddEdge(SUnit *SuccSU, SUnit *PredSU) {
501 return SuccSU == &ExitSU || !Topo.IsReachable(PredSU, SuccSU);
502}
503
Andrew Tricka7714a02012-11-12 19:40:10 +0000504bool ScheduleDAGMI::addEdge(SUnit *SuccSU, const SDep &PredDep) {
Andrew Trick263280242012-11-12 19:52:20 +0000505 if (SuccSU != &ExitSU) {
506 // Do not use WillCreateCycle, it assumes SD scheduling.
507 // If Pred is reachable from Succ, then the edge creates a cycle.
508 if (Topo.IsReachable(PredDep.getSUnit(), SuccSU))
509 return false;
510 Topo.AddPred(SuccSU, PredDep.getSUnit());
511 }
Andrew Tricka7714a02012-11-12 19:40:10 +0000512 SuccSU->addPred(PredDep, /*Required=*/!PredDep.isArtificial());
513 // Return true regardless of whether a new edge needed to be inserted.
514 return true;
515}
516
Andrew Trick02a80da2012-03-08 01:41:12 +0000517/// ReleaseSucc - Decrement the NumPredsLeft count of a successor. When
518/// NumPredsLeft reaches zero, release the successor node.
Andrew Trick61f1a272012-05-24 22:11:09 +0000519///
520/// FIXME: Adjust SuccSU height based on MinLatency.
Andrew Trick8823dec2012-03-14 04:00:41 +0000521void ScheduleDAGMI::releaseSucc(SUnit *SU, SDep *SuccEdge) {
Andrew Trick02a80da2012-03-08 01:41:12 +0000522 SUnit *SuccSU = SuccEdge->getSUnit();
523
Andrew Trickf1ff84c2012-11-12 19:28:57 +0000524 if (SuccEdge->isWeak()) {
525 --SuccSU->WeakPredsLeft;
Andrew Tricka7714a02012-11-12 19:40:10 +0000526 if (SuccEdge->isCluster())
527 NextClusterSucc = SuccSU;
Andrew Trickf1ff84c2012-11-12 19:28:57 +0000528 return;
529 }
Andrew Trick02a80da2012-03-08 01:41:12 +0000530#ifndef NDEBUG
531 if (SuccSU->NumPredsLeft == 0) {
532 dbgs() << "*** Scheduling failed! ***\n";
533 SuccSU->dump(this);
534 dbgs() << " has been released too many times!\n";
Craig Topperc0196b12014-04-14 00:51:57 +0000535 llvm_unreachable(nullptr);
Andrew Trick02a80da2012-03-08 01:41:12 +0000536 }
537#endif
Andrew Trick7f1ebbe2014-06-07 01:48:43 +0000538 // SU->TopReadyCycle was set to CurrCycle when it was scheduled. However,
539 // CurrCycle may have advanced since then.
540 if (SuccSU->TopReadyCycle < SU->TopReadyCycle + SuccEdge->getLatency())
541 SuccSU->TopReadyCycle = SU->TopReadyCycle + SuccEdge->getLatency();
542
Andrew Trick02a80da2012-03-08 01:41:12 +0000543 --SuccSU->NumPredsLeft;
544 if (SuccSU->NumPredsLeft == 0 && SuccSU != &ExitSU)
Andrew Trick8823dec2012-03-14 04:00:41 +0000545 SchedImpl->releaseTopNode(SuccSU);
Andrew Trick02a80da2012-03-08 01:41:12 +0000546}
547
548/// releaseSuccessors - Call releaseSucc on each of SU's successors.
Andrew Trick8823dec2012-03-14 04:00:41 +0000549void ScheduleDAGMI::releaseSuccessors(SUnit *SU) {
Andrew Trick02a80da2012-03-08 01:41:12 +0000550 for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
551 I != E; ++I) {
552 releaseSucc(SU, &*I);
553 }
554}
555
Andrew Trick8823dec2012-03-14 04:00:41 +0000556/// ReleasePred - Decrement the NumSuccsLeft count of a predecessor. When
557/// NumSuccsLeft reaches zero, release the predecessor node.
Andrew Trick61f1a272012-05-24 22:11:09 +0000558///
559/// FIXME: Adjust PredSU height based on MinLatency.
Andrew Trick8823dec2012-03-14 04:00:41 +0000560void ScheduleDAGMI::releasePred(SUnit *SU, SDep *PredEdge) {
561 SUnit *PredSU = PredEdge->getSUnit();
562
Andrew Trickf1ff84c2012-11-12 19:28:57 +0000563 if (PredEdge->isWeak()) {
564 --PredSU->WeakSuccsLeft;
Andrew Tricka7714a02012-11-12 19:40:10 +0000565 if (PredEdge->isCluster())
566 NextClusterPred = PredSU;
Andrew Trickf1ff84c2012-11-12 19:28:57 +0000567 return;
568 }
Andrew Trick8823dec2012-03-14 04:00:41 +0000569#ifndef NDEBUG
570 if (PredSU->NumSuccsLeft == 0) {
571 dbgs() << "*** Scheduling failed! ***\n";
572 PredSU->dump(this);
573 dbgs() << " has been released too many times!\n";
Craig Topperc0196b12014-04-14 00:51:57 +0000574 llvm_unreachable(nullptr);
Andrew Trick8823dec2012-03-14 04:00:41 +0000575 }
576#endif
Andrew Trick7f1ebbe2014-06-07 01:48:43 +0000577 // SU->BotReadyCycle was set to CurrCycle when it was scheduled. However,
578 // CurrCycle may have advanced since then.
579 if (PredSU->BotReadyCycle < SU->BotReadyCycle + PredEdge->getLatency())
580 PredSU->BotReadyCycle = SU->BotReadyCycle + PredEdge->getLatency();
581
Andrew Trick8823dec2012-03-14 04:00:41 +0000582 --PredSU->NumSuccsLeft;
583 if (PredSU->NumSuccsLeft == 0 && PredSU != &EntrySU)
584 SchedImpl->releaseBottomNode(PredSU);
585}
586
587/// releasePredecessors - Call releasePred on each of SU's predecessors.
588void ScheduleDAGMI::releasePredecessors(SUnit *SU) {
589 for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
590 I != E; ++I) {
591 releasePred(SU, &*I);
592 }
593}
594
Andrew Trickd7f890e2013-12-28 21:56:47 +0000595/// enterRegion - Called back from MachineScheduler::runOnMachineFunction after
596/// crossing a scheduling boundary. [begin, end) includes all instructions in
597/// the region, including the boundary itself and single-instruction regions
598/// that don't get scheduled.
599void ScheduleDAGMI::enterRegion(MachineBasicBlock *bb,
600 MachineBasicBlock::iterator begin,
601 MachineBasicBlock::iterator end,
602 unsigned regioninstrs)
603{
604 ScheduleDAGInstrs::enterRegion(bb, begin, end, regioninstrs);
605
606 SchedImpl->initPolicy(begin, end, regioninstrs);
607}
608
Andrew Tricke833e1c2013-04-13 06:07:40 +0000609/// This is normally called from the main scheduler loop but may also be invoked
610/// by the scheduling strategy to perform additional code motion.
Andrew Trickd7f890e2013-12-28 21:56:47 +0000611void ScheduleDAGMI::moveInstruction(
612 MachineInstr *MI, MachineBasicBlock::iterator InsertPos) {
Andrew Trick463b2f12012-05-17 18:35:03 +0000613 // Advance RegionBegin if the first instruction moves down.
Andrew Trick54f7def2012-03-21 04:12:10 +0000614 if (&*RegionBegin == MI)
Andrew Trick463b2f12012-05-17 18:35:03 +0000615 ++RegionBegin;
616
617 // Update the instruction stream.
Andrew Trick8823dec2012-03-14 04:00:41 +0000618 BB->splice(InsertPos, BB, MI);
Andrew Trick463b2f12012-05-17 18:35:03 +0000619
620 // Update LiveIntervals
Andrew Trickd7f890e2013-12-28 21:56:47 +0000621 if (LIS)
622 LIS->handleMove(MI, /*UpdateFlags=*/true);
Andrew Trick463b2f12012-05-17 18:35:03 +0000623
624 // Recede RegionBegin if an instruction moves above the first.
Andrew Trick8823dec2012-03-14 04:00:41 +0000625 if (RegionBegin == InsertPos)
626 RegionBegin = MI;
627}
628
Andrew Trickde670c02012-03-21 04:12:07 +0000629bool ScheduleDAGMI::checkSchedLimit() {
630#ifndef NDEBUG
631 if (NumInstrsScheduled == MISchedCutoff && MISchedCutoff != ~0U) {
632 CurrentTop = CurrentBottom;
633 return false;
634 }
635 ++NumInstrsScheduled;
636#endif
637 return true;
638}
639
Andrew Trickd7f890e2013-12-28 21:56:47 +0000640/// Per-region scheduling driver, called back from
641/// MachineScheduler::runOnMachineFunction. This is a simplified driver that
642/// does not consider liveness or register pressure. It is useful for PostRA
643/// scheduling and potentially other custom schedulers.
644void ScheduleDAGMI::schedule() {
645 // Build the DAG.
646 buildSchedGraph(AA);
647
648 Topo.InitDAGTopologicalSorting();
649
650 postprocessDAG();
651
652 SmallVector<SUnit*, 8> TopRoots, BotRoots;
653 findRootsAndBiasEdges(TopRoots, BotRoots);
654
655 // Initialize the strategy before modifying the DAG.
656 // This may initialize a DFSResult to be used for queue priority.
657 SchedImpl->initialize(this);
658
659 DEBUG(for (unsigned su = 0, e = SUnits.size(); su != e; ++su)
660 SUnits[su].dumpAll(this));
661 if (ViewMISchedDAGs) viewGraph();
662
663 // Initialize ready queues now that the DAG and priority data are finalized.
664 initQueues(TopRoots, BotRoots);
665
666 bool IsTopNode = false;
667 while (SUnit *SU = SchedImpl->pickNode(IsTopNode)) {
668 assert(!SU->isScheduled && "Node already scheduled");
669 if (!checkSchedLimit())
670 break;
671
672 MachineInstr *MI = SU->getInstr();
673 if (IsTopNode) {
674 assert(SU->isTopReady() && "node still has unscheduled dependencies");
675 if (&*CurrentTop == MI)
676 CurrentTop = nextIfDebug(++CurrentTop, CurrentBottom);
677 else
678 moveInstruction(MI, CurrentTop);
679 }
680 else {
681 assert(SU->isBottomReady() && "node still has unscheduled dependencies");
682 MachineBasicBlock::iterator priorII =
683 priorNonDebug(CurrentBottom, CurrentTop);
684 if (&*priorII == MI)
685 CurrentBottom = priorII;
686 else {
687 if (&*CurrentTop == MI)
688 CurrentTop = nextIfDebug(++CurrentTop, priorII);
689 moveInstruction(MI, CurrentBottom);
690 CurrentBottom = MI;
691 }
692 }
Andrew Trick7f1ebbe2014-06-07 01:48:43 +0000693 // Notify the scheduling strategy before updating the DAG.
Andrew Trick491e34a2014-06-12 22:36:28 +0000694 // This sets the scheduled node's ReadyCycle to CurrCycle. When updateQueues
Andrew Trick7f1ebbe2014-06-07 01:48:43 +0000695 // runs, it can then use the accurate ReadyCycle time to determine whether
696 // newly released nodes can move to the readyQ.
Andrew Trickd7f890e2013-12-28 21:56:47 +0000697 SchedImpl->schedNode(SU, IsTopNode);
Andrew Trick7f1ebbe2014-06-07 01:48:43 +0000698
699 updateQueues(SU, IsTopNode);
Andrew Trickd7f890e2013-12-28 21:56:47 +0000700 }
701 assert(CurrentTop == CurrentBottom && "Nonempty unscheduled zone.");
702
703 placeDebugValues();
704
705 DEBUG({
706 unsigned BBNum = begin()->getParent()->getNumber();
707 dbgs() << "*** Final schedule for BB#" << BBNum << " ***\n";
708 dumpSchedule();
709 dbgs() << '\n';
710 });
711}
712
713/// Apply each ScheduleDAGMutation step in order.
714void ScheduleDAGMI::postprocessDAG() {
715 for (unsigned i = 0, e = Mutations.size(); i < e; ++i) {
716 Mutations[i]->apply(this);
717 }
718}
719
720void ScheduleDAGMI::
721findRootsAndBiasEdges(SmallVectorImpl<SUnit*> &TopRoots,
722 SmallVectorImpl<SUnit*> &BotRoots) {
723 for (std::vector<SUnit>::iterator
724 I = SUnits.begin(), E = SUnits.end(); I != E; ++I) {
725 SUnit *SU = &(*I);
726 assert(!SU->isBoundaryNode() && "Boundary node should not be in SUnits");
727
728 // Order predecessors so DFSResult follows the critical path.
729 SU->biasCriticalPath();
730
731 // A SUnit is ready to top schedule if it has no predecessors.
732 if (!I->NumPredsLeft)
733 TopRoots.push_back(SU);
734 // A SUnit is ready to bottom schedule if it has no successors.
735 if (!I->NumSuccsLeft)
736 BotRoots.push_back(SU);
737 }
738 ExitSU.biasCriticalPath();
739}
740
741/// Identify DAG roots and setup scheduler queues.
742void ScheduleDAGMI::initQueues(ArrayRef<SUnit*> TopRoots,
743 ArrayRef<SUnit*> BotRoots) {
Craig Topperc0196b12014-04-14 00:51:57 +0000744 NextClusterSucc = nullptr;
745 NextClusterPred = nullptr;
Andrew Trickd7f890e2013-12-28 21:56:47 +0000746
747 // Release all DAG roots for scheduling, not including EntrySU/ExitSU.
748 //
749 // Nodes with unreleased weak edges can still be roots.
750 // Release top roots in forward order.
751 for (SmallVectorImpl<SUnit*>::const_iterator
752 I = TopRoots.begin(), E = TopRoots.end(); I != E; ++I) {
753 SchedImpl->releaseTopNode(*I);
754 }
755 // Release bottom roots in reverse order so the higher priority nodes appear
756 // first. This is more natural and slightly more efficient.
757 for (SmallVectorImpl<SUnit*>::const_reverse_iterator
758 I = BotRoots.rbegin(), E = BotRoots.rend(); I != E; ++I) {
759 SchedImpl->releaseBottomNode(*I);
760 }
761
762 releaseSuccessors(&EntrySU);
763 releasePredecessors(&ExitSU);
764
765 SchedImpl->registerRoots();
766
767 // Advance past initial DebugValues.
768 CurrentTop = nextIfDebug(RegionBegin, RegionEnd);
769 CurrentBottom = RegionEnd;
770}
771
772/// Update scheduler queues after scheduling an instruction.
773void ScheduleDAGMI::updateQueues(SUnit *SU, bool IsTopNode) {
774 // Release dependent instructions for scheduling.
775 if (IsTopNode)
776 releaseSuccessors(SU);
777 else
778 releasePredecessors(SU);
779
780 SU->isScheduled = true;
781}
782
783/// Reinsert any remaining debug_values, just like the PostRA scheduler.
784void ScheduleDAGMI::placeDebugValues() {
785 // If first instruction was a DBG_VALUE then put it back.
786 if (FirstDbgValue) {
787 BB->splice(RegionBegin, BB, FirstDbgValue);
788 RegionBegin = FirstDbgValue;
789 }
790
791 for (std::vector<std::pair<MachineInstr *, MachineInstr *> >::iterator
792 DI = DbgValues.end(), DE = DbgValues.begin(); DI != DE; --DI) {
Benjamin Kramerb6d0bd42014-03-02 12:27:27 +0000793 std::pair<MachineInstr *, MachineInstr *> P = *std::prev(DI);
Andrew Trickd7f890e2013-12-28 21:56:47 +0000794 MachineInstr *DbgValue = P.first;
795 MachineBasicBlock::iterator OrigPrevMI = P.second;
796 if (&*RegionBegin == DbgValue)
797 ++RegionBegin;
798 BB->splice(++OrigPrevMI, BB, DbgValue);
Benjamin Kramerb6d0bd42014-03-02 12:27:27 +0000799 if (OrigPrevMI == std::prev(RegionEnd))
Andrew Trickd7f890e2013-12-28 21:56:47 +0000800 RegionEnd = DbgValue;
801 }
802 DbgValues.clear();
Craig Topperc0196b12014-04-14 00:51:57 +0000803 FirstDbgValue = nullptr;
Andrew Trickd7f890e2013-12-28 21:56:47 +0000804}
805
806#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
807void ScheduleDAGMI::dumpSchedule() const {
808 for (MachineBasicBlock::iterator MI = begin(), ME = end(); MI != ME; ++MI) {
809 if (SUnit *SU = getSUnit(&(*MI)))
810 SU->dump(this);
811 else
812 dbgs() << "Missing SUnit\n";
813 }
814}
815#endif
816
817//===----------------------------------------------------------------------===//
818// ScheduleDAGMILive - Base class for MachineInstr scheduling with LiveIntervals
819// preservation.
820//===----------------------------------------------------------------------===//
821
822ScheduleDAGMILive::~ScheduleDAGMILive() {
823 delete DFSResult;
824}
825
Andrew Trick88639922012-04-24 17:56:43 +0000826/// enterRegion - Called back from MachineScheduler::runOnMachineFunction after
827/// crossing a scheduling boundary. [begin, end) includes all instructions in
828/// the region, including the boundary itself and single-instruction regions
829/// that don't get scheduled.
Andrew Trickd7f890e2013-12-28 21:56:47 +0000830void ScheduleDAGMILive::enterRegion(MachineBasicBlock *bb,
Andrew Trick88639922012-04-24 17:56:43 +0000831 MachineBasicBlock::iterator begin,
832 MachineBasicBlock::iterator end,
Andrew Tricka53e1012013-08-23 17:48:33 +0000833 unsigned regioninstrs)
Andrew Trick88639922012-04-24 17:56:43 +0000834{
Andrew Trickd7f890e2013-12-28 21:56:47 +0000835 // ScheduleDAGMI initializes SchedImpl's per-region policy.
836 ScheduleDAGMI::enterRegion(bb, begin, end, regioninstrs);
Andrew Trick4add42f2012-05-10 21:06:10 +0000837
838 // For convenience remember the end of the liveness region.
Benjamin Kramerb6d0bd42014-03-02 12:27:27 +0000839 LiveRegionEnd = (RegionEnd == bb->end()) ? RegionEnd : std::next(RegionEnd);
Andrew Trick75e411c2013-09-06 17:32:34 +0000840
Andrew Trickb248b4a2013-09-06 17:32:47 +0000841 SUPressureDiffs.clear();
842
Andrew Trick75e411c2013-09-06 17:32:34 +0000843 ShouldTrackPressure = SchedImpl->shouldTrackPressure();
Andrew Trick4add42f2012-05-10 21:06:10 +0000844}
845
846// Setup the register pressure trackers for the top scheduled top and bottom
847// scheduled regions.
Andrew Trickd7f890e2013-12-28 21:56:47 +0000848void ScheduleDAGMILive::initRegPressure() {
Andrew Trick4add42f2012-05-10 21:06:10 +0000849 TopRPTracker.init(&MF, RegClassInfo, LIS, BB, RegionBegin);
850 BotRPTracker.init(&MF, RegClassInfo, LIS, BB, LiveRegionEnd);
851
852 // Close the RPTracker to finalize live ins.
853 RPTracker.closeRegion();
854
Andrew Trick9c17eab2013-07-30 19:59:12 +0000855 DEBUG(RPTracker.dump());
Andrew Trick79d3eec2012-05-24 22:11:14 +0000856
Andrew Trick4add42f2012-05-10 21:06:10 +0000857 // Initialize the live ins and live outs.
858 TopRPTracker.addLiveRegs(RPTracker.getPressure().LiveInRegs);
859 BotRPTracker.addLiveRegs(RPTracker.getPressure().LiveOutRegs);
860
861 // Close one end of the tracker so we can call
862 // getMaxUpward/DownwardPressureDelta before advancing across any
863 // instructions. This converts currently live regs into live ins/outs.
864 TopRPTracker.closeTop();
865 BotRPTracker.closeBottom();
866
Andrew Trick9c17eab2013-07-30 19:59:12 +0000867 BotRPTracker.initLiveThru(RPTracker);
868 if (!BotRPTracker.getLiveThru().empty()) {
869 TopRPTracker.initLiveThru(BotRPTracker.getLiveThru());
870 DEBUG(dbgs() << "Live Thru: ";
871 dumpRegSetPressure(BotRPTracker.getLiveThru(), TRI));
872 };
873
Andrew Trick2bc74c22013-08-30 04:36:57 +0000874 // For each live out vreg reduce the pressure change associated with other
875 // uses of the same vreg below the live-out reaching def.
876 updatePressureDiffs(RPTracker.getPressure().LiveOutRegs);
877
Andrew Trick4add42f2012-05-10 21:06:10 +0000878 // Account for liveness generated by the region boundary.
Andrew Trick2bc74c22013-08-30 04:36:57 +0000879 if (LiveRegionEnd != RegionEnd) {
880 SmallVector<unsigned, 8> LiveUses;
881 BotRPTracker.recede(&LiveUses);
882 updatePressureDiffs(LiveUses);
883 }
Andrew Trick4add42f2012-05-10 21:06:10 +0000884
885 assert(BotRPTracker.getPos() == RegionEnd && "Can't find the region bottom");
Andrew Trick22025772012-05-17 18:35:10 +0000886
887 // Cache the list of excess pressure sets in this region. This will also track
888 // the max pressure in the scheduled code for these sets.
889 RegionCriticalPSets.clear();
Jakub Staszakc641ada2013-01-25 21:44:27 +0000890 const std::vector<unsigned> &RegionPressure =
891 RPTracker.getPressure().MaxSetPressure;
Andrew Trick22025772012-05-17 18:35:10 +0000892 for (unsigned i = 0, e = RegionPressure.size(); i < e; ++i) {
Andrew Trick736dd9a2013-06-21 18:32:58 +0000893 unsigned Limit = RegClassInfo->getRegPressureSetLimit(i);
Andrew Trickb55db582013-06-21 18:33:01 +0000894 if (RegionPressure[i] > Limit) {
895 DEBUG(dbgs() << TRI->getRegPressureSetName(i)
896 << " Limit " << Limit
897 << " Actual " << RegionPressure[i] << "\n");
Andrew Trick1a831342013-08-30 03:49:48 +0000898 RegionCriticalPSets.push_back(PressureChange(i));
Andrew Trickb55db582013-06-21 18:33:01 +0000899 }
Andrew Trick22025772012-05-17 18:35:10 +0000900 }
901 DEBUG(dbgs() << "Excess PSets: ";
902 for (unsigned i = 0, e = RegionCriticalPSets.size(); i != e; ++i)
903 dbgs() << TRI->getRegPressureSetName(
Andrew Trick1a831342013-08-30 03:49:48 +0000904 RegionCriticalPSets[i].getPSet()) << " ";
Andrew Trick22025772012-05-17 18:35:10 +0000905 dbgs() << "\n");
906}
907
Andrew Trickd7f890e2013-12-28 21:56:47 +0000908void ScheduleDAGMILive::
Andrew Trickb248b4a2013-09-06 17:32:47 +0000909updateScheduledPressure(const SUnit *SU,
910 const std::vector<unsigned> &NewMaxPressure) {
911 const PressureDiff &PDiff = getPressureDiff(SU);
912 unsigned CritIdx = 0, CritEnd = RegionCriticalPSets.size();
913 for (PressureDiff::const_iterator I = PDiff.begin(), E = PDiff.end();
914 I != E; ++I) {
915 if (!I->isValid())
916 break;
917 unsigned ID = I->getPSet();
918 while (CritIdx != CritEnd && RegionCriticalPSets[CritIdx].getPSet() < ID)
919 ++CritIdx;
920 if (CritIdx != CritEnd && RegionCriticalPSets[CritIdx].getPSet() == ID) {
921 if ((int)NewMaxPressure[ID] > RegionCriticalPSets[CritIdx].getUnitInc()
922 && NewMaxPressure[ID] <= INT16_MAX)
923 RegionCriticalPSets[CritIdx].setUnitInc(NewMaxPressure[ID]);
924 }
925 unsigned Limit = RegClassInfo->getRegPressureSetLimit(ID);
926 if (NewMaxPressure[ID] >= Limit - 2) {
927 DEBUG(dbgs() << " " << TRI->getRegPressureSetName(ID) << ": "
928 << NewMaxPressure[ID] << " > " << Limit << "(+ "
929 << BotRPTracker.getLiveThru()[ID] << " livethru)\n");
930 }
Andrew Trick22025772012-05-17 18:35:10 +0000931 }
Andrew Trick88639922012-04-24 17:56:43 +0000932}
933
Andrew Trick2bc74c22013-08-30 04:36:57 +0000934/// Update the PressureDiff array for liveness after scheduling this
935/// instruction.
Andrew Trickd7f890e2013-12-28 21:56:47 +0000936void ScheduleDAGMILive::updatePressureDiffs(ArrayRef<unsigned> LiveUses) {
Andrew Trick2bc74c22013-08-30 04:36:57 +0000937 for (unsigned LUIdx = 0, LUEnd = LiveUses.size(); LUIdx != LUEnd; ++LUIdx) {
938 /// FIXME: Currently assuming single-use physregs.
939 unsigned Reg = LiveUses[LUIdx];
Andrew Trickffdbefb2013-09-06 17:32:39 +0000940 DEBUG(dbgs() << " LiveReg: " << PrintVRegOrUnit(Reg, TRI) << "\n");
Andrew Trick2bc74c22013-08-30 04:36:57 +0000941 if (!TRI->isVirtualRegister(Reg))
942 continue;
Andrew Trickffdbefb2013-09-06 17:32:39 +0000943
Andrew Trick2bc74c22013-08-30 04:36:57 +0000944 // This may be called before CurrentBottom has been initialized. However,
945 // BotRPTracker must have a valid position. We want the value live into the
946 // instruction or live out of the block, so ask for the previous
947 // instruction's live-out.
948 const LiveInterval &LI = LIS->getInterval(Reg);
949 VNInfo *VNI;
Andrew Trick2c4f8b72013-08-31 05:17:58 +0000950 MachineBasicBlock::const_iterator I =
951 nextIfDebug(BotRPTracker.getPos(), BB->end());
952 if (I == BB->end())
Andrew Trick2bc74c22013-08-30 04:36:57 +0000953 VNI = LI.getVNInfoBefore(LIS->getMBBEndIdx(BB));
954 else {
Matthias Braun88dd0ab2013-10-10 21:28:52 +0000955 LiveQueryResult LRQ = LI.Query(LIS->getInstructionIndex(I));
Andrew Trick2bc74c22013-08-30 04:36:57 +0000956 VNI = LRQ.valueIn();
957 }
958 // RegisterPressureTracker guarantees that readsReg is true for LiveUses.
959 assert(VNI && "No live value at use.");
960 for (VReg2UseMap::iterator
961 UI = VRegUses.find(Reg); UI != VRegUses.end(); ++UI) {
962 SUnit *SU = UI->SU;
Andrew Trickffdbefb2013-09-06 17:32:39 +0000963 DEBUG(dbgs() << " UpdateRegP: SU(" << SU->NodeNum << ") "
964 << *SU->getInstr());
Andrew Trick2bc74c22013-08-30 04:36:57 +0000965 // If this use comes before the reaching def, it cannot be a last use, so
966 // descrease its pressure change.
967 if (!SU->isScheduled && SU != &ExitSU) {
Matthias Braun88dd0ab2013-10-10 21:28:52 +0000968 LiveQueryResult LRQ
969 = LI.Query(LIS->getInstructionIndex(SU->getInstr()));
Andrew Trick2bc74c22013-08-30 04:36:57 +0000970 if (LRQ.valueIn() == VNI)
971 getPressureDiff(SU).addPressureChange(Reg, true, &MRI);
972 }
973 }
974 }
975}
976
Andrew Trick8823dec2012-03-14 04:00:41 +0000977/// schedule - Called back from MachineScheduler::runOnMachineFunction
Andrew Trick88639922012-04-24 17:56:43 +0000978/// after setting up the current scheduling region. [RegionBegin, RegionEnd)
979/// only includes instructions that have DAG nodes, not scheduling boundaries.
Andrew Trick7a8e1002012-09-11 00:39:15 +0000980///
981/// This is a skeletal driver, with all the functionality pushed into helpers,
982/// so that it can be easilly extended by experimental schedulers. Generally,
983/// implementing MachineSchedStrategy should be sufficient to implement a new
984/// scheduling algorithm. However, if a scheduler further subclasses
Andrew Trickd7f890e2013-12-28 21:56:47 +0000985/// ScheduleDAGMILive then it will want to override this virtual method in order
986/// to update any specialized state.
987void ScheduleDAGMILive::schedule() {
Andrew Trick7a8e1002012-09-11 00:39:15 +0000988 buildDAGWithRegPressure();
989
Andrew Tricka7714a02012-11-12 19:40:10 +0000990 Topo.InitDAGTopologicalSorting();
991
Andrew Tricka2733e92012-09-14 17:22:42 +0000992 postprocessDAG();
993
Andrew Tricke2c3f5c2013-01-25 06:33:57 +0000994 SmallVector<SUnit*, 8> TopRoots, BotRoots;
995 findRootsAndBiasEdges(TopRoots, BotRoots);
996
997 // Initialize the strategy before modifying the DAG.
998 // This may initialize a DFSResult to be used for queue priority.
999 SchedImpl->initialize(this);
1000
Andrew Trick7a8e1002012-09-11 00:39:15 +00001001 DEBUG(for (unsigned su = 0, e = SUnits.size(); su != e; ++su)
1002 SUnits[su].dumpAll(this));
Andrew Tricke2c3f5c2013-01-25 06:33:57 +00001003 if (ViewMISchedDAGs) viewGraph();
Andrew Trick7a8e1002012-09-11 00:39:15 +00001004
Andrew Tricke2c3f5c2013-01-25 06:33:57 +00001005 // Initialize ready queues now that the DAG and priority data are finalized.
1006 initQueues(TopRoots, BotRoots);
Andrew Trick7a8e1002012-09-11 00:39:15 +00001007
Andrew Trickd7f890e2013-12-28 21:56:47 +00001008 if (ShouldTrackPressure) {
1009 assert(TopRPTracker.getPos() == RegionBegin && "bad initial Top tracker");
1010 TopRPTracker.setPos(CurrentTop);
1011 }
1012
Andrew Trick7a8e1002012-09-11 00:39:15 +00001013 bool IsTopNode = false;
1014 while (SUnit *SU = SchedImpl->pickNode(IsTopNode)) {
Andrew Trick984d98b2012-10-08 18:53:53 +00001015 assert(!SU->isScheduled && "Node already scheduled");
Andrew Trick7a8e1002012-09-11 00:39:15 +00001016 if (!checkSchedLimit())
1017 break;
1018
1019 scheduleMI(SU, IsTopNode);
1020
1021 updateQueues(SU, IsTopNode);
Andrew Trickd7f890e2013-12-28 21:56:47 +00001022
1023 if (DFSResult) {
1024 unsigned SubtreeID = DFSResult->getSubtreeID(SU);
1025 if (!ScheduledTrees.test(SubtreeID)) {
1026 ScheduledTrees.set(SubtreeID);
1027 DFSResult->scheduleTree(SubtreeID);
1028 SchedImpl->scheduleTree(SubtreeID);
1029 }
1030 }
1031
1032 // Notify the scheduling strategy after updating the DAG.
1033 SchedImpl->schedNode(SU, IsTopNode);
Andrew Trick7a8e1002012-09-11 00:39:15 +00001034 }
1035 assert(CurrentTop == CurrentBottom && "Nonempty unscheduled zone.");
1036
1037 placeDebugValues();
Andrew Trick3ca33ac2012-11-07 07:05:09 +00001038
1039 DEBUG({
Andrew Trickcf7e6972012-11-28 03:42:47 +00001040 unsigned BBNum = begin()->getParent()->getNumber();
Andrew Trick3ca33ac2012-11-07 07:05:09 +00001041 dbgs() << "*** Final schedule for BB#" << BBNum << " ***\n";
1042 dumpSchedule();
1043 dbgs() << '\n';
1044 });
Andrew Trick7a8e1002012-09-11 00:39:15 +00001045}
1046
1047/// Build the DAG and setup three register pressure trackers.
Andrew Trickd7f890e2013-12-28 21:56:47 +00001048void ScheduleDAGMILive::buildDAGWithRegPressure() {
Andrew Trickb6e74712013-09-04 20:59:59 +00001049 if (!ShouldTrackPressure) {
1050 RPTracker.reset();
1051 RegionCriticalPSets.clear();
1052 buildSchedGraph(AA);
1053 return;
1054 }
1055
Andrew Trick4add42f2012-05-10 21:06:10 +00001056 // Initialize the register pressure tracker used by buildSchedGraph.
Andrew Trick9c17eab2013-07-30 19:59:12 +00001057 RPTracker.init(&MF, RegClassInfo, LIS, BB, LiveRegionEnd,
1058 /*TrackUntiedDefs=*/true);
Andrew Trick88639922012-04-24 17:56:43 +00001059
Andrew Trick4add42f2012-05-10 21:06:10 +00001060 // Account for liveness generate by the region boundary.
1061 if (LiveRegionEnd != RegionEnd)
1062 RPTracker.recede();
1063
1064 // Build the DAG, and compute current register pressure.
Andrew Trick1a831342013-08-30 03:49:48 +00001065 buildSchedGraph(AA, &RPTracker, &SUPressureDiffs);
Andrew Trick02a80da2012-03-08 01:41:12 +00001066
Andrew Trick4add42f2012-05-10 21:06:10 +00001067 // Initialize top/bottom trackers after computing region pressure.
1068 initRegPressure();
Andrew Trick7a8e1002012-09-11 00:39:15 +00001069}
Andrew Trick4add42f2012-05-10 21:06:10 +00001070
Andrew Trickd7f890e2013-12-28 21:56:47 +00001071void ScheduleDAGMILive::computeDFSResult() {
Andrew Trick44f750a2013-01-25 04:01:04 +00001072 if (!DFSResult)
1073 DFSResult = new SchedDFSResult(/*BottomU*/true, MinSubtreeSize);
1074 DFSResult->clear();
Andrew Trick44f750a2013-01-25 04:01:04 +00001075 ScheduledTrees.clear();
Andrew Tricke2c3f5c2013-01-25 06:33:57 +00001076 DFSResult->resize(SUnits.size());
1077 DFSResult->compute(SUnits);
Andrew Trick44f750a2013-01-25 04:01:04 +00001078 ScheduledTrees.resize(DFSResult->getNumSubtrees());
1079}
1080
Andrew Trick483f4192013-08-29 18:04:49 +00001081/// Compute the max cyclic critical path through the DAG. The scheduling DAG
1082/// only provides the critical path for single block loops. To handle loops that
1083/// span blocks, we could use the vreg path latencies provided by
1084/// MachineTraceMetrics instead. However, MachineTraceMetrics is not currently
1085/// available for use in the scheduler.
1086///
1087/// The cyclic path estimation identifies a def-use pair that crosses the back
Andrew Trickef80f502013-08-30 02:02:12 +00001088/// edge and considers the depth and height of the nodes. For example, consider
Andrew Trick483f4192013-08-29 18:04:49 +00001089/// the following instruction sequence where each instruction has unit latency
1090/// and defines an epomymous virtual register:
1091///
1092/// a->b(a,c)->c(b)->d(c)->exit
1093///
1094/// The cyclic critical path is a two cycles: b->c->b
1095/// The acyclic critical path is four cycles: a->b->c->d->exit
1096/// LiveOutHeight = height(c) = len(c->d->exit) = 2
1097/// LiveOutDepth = depth(c) + 1 = len(a->b->c) + 1 = 3
1098/// LiveInHeight = height(b) + 1 = len(b->c->d->exit) + 1 = 4
1099/// LiveInDepth = depth(b) = len(a->b) = 1
1100///
1101/// LiveOutDepth - LiveInDepth = 3 - 1 = 2
1102/// LiveInHeight - LiveOutHeight = 4 - 2 = 2
1103/// CyclicCriticalPath = min(2, 2) = 2
Andrew Trickd7f890e2013-12-28 21:56:47 +00001104///
1105/// This could be relevant to PostRA scheduling, but is currently implemented
1106/// assuming LiveIntervals.
1107unsigned ScheduleDAGMILive::computeCyclicCriticalPath() {
Andrew Trick483f4192013-08-29 18:04:49 +00001108 // This only applies to single block loop.
1109 if (!BB->isSuccessor(BB))
1110 return 0;
1111
1112 unsigned MaxCyclicLatency = 0;
1113 // Visit each live out vreg def to find def/use pairs that cross iterations.
1114 ArrayRef<unsigned> LiveOuts = RPTracker.getPressure().LiveOutRegs;
1115 for (ArrayRef<unsigned>::iterator RI = LiveOuts.begin(), RE = LiveOuts.end();
1116 RI != RE; ++RI) {
1117 unsigned Reg = *RI;
1118 if (!TRI->isVirtualRegister(Reg))
1119 continue;
1120 const LiveInterval &LI = LIS->getInterval(Reg);
1121 const VNInfo *DefVNI = LI.getVNInfoBefore(LIS->getMBBEndIdx(BB));
1122 if (!DefVNI)
1123 continue;
1124
1125 MachineInstr *DefMI = LIS->getInstructionFromIndex(DefVNI->def);
1126 const SUnit *DefSU = getSUnit(DefMI);
1127 if (!DefSU)
1128 continue;
1129
1130 unsigned LiveOutHeight = DefSU->getHeight();
1131 unsigned LiveOutDepth = DefSU->getDepth() + DefSU->Latency;
1132 // Visit all local users of the vreg def.
1133 for (VReg2UseMap::iterator
1134 UI = VRegUses.find(Reg); UI != VRegUses.end(); ++UI) {
1135 if (UI->SU == &ExitSU)
1136 continue;
1137
1138 // Only consider uses of the phi.
Matthias Braun88dd0ab2013-10-10 21:28:52 +00001139 LiveQueryResult LRQ =
1140 LI.Query(LIS->getInstructionIndex(UI->SU->getInstr()));
Andrew Trick483f4192013-08-29 18:04:49 +00001141 if (!LRQ.valueIn()->isPHIDef())
1142 continue;
1143
1144 // Assume that a path spanning two iterations is a cycle, which could
1145 // overestimate in strange cases. This allows cyclic latency to be
1146 // estimated as the minimum slack of the vreg's depth or height.
1147 unsigned CyclicLatency = 0;
1148 if (LiveOutDepth > UI->SU->getDepth())
1149 CyclicLatency = LiveOutDepth - UI->SU->getDepth();
1150
1151 unsigned LiveInHeight = UI->SU->getHeight() + DefSU->Latency;
1152 if (LiveInHeight > LiveOutHeight) {
1153 if (LiveInHeight - LiveOutHeight < CyclicLatency)
1154 CyclicLatency = LiveInHeight - LiveOutHeight;
1155 }
1156 else
1157 CyclicLatency = 0;
1158
1159 DEBUG(dbgs() << "Cyclic Path: SU(" << DefSU->NodeNum << ") -> SU("
1160 << UI->SU->NodeNum << ") = " << CyclicLatency << "c\n");
1161 if (CyclicLatency > MaxCyclicLatency)
1162 MaxCyclicLatency = CyclicLatency;
1163 }
1164 }
1165 DEBUG(dbgs() << "Cyclic Critical Path: " << MaxCyclicLatency << "c\n");
1166 return MaxCyclicLatency;
1167}
1168
Andrew Trick7a8e1002012-09-11 00:39:15 +00001169/// Move an instruction and update register pressure.
Andrew Trickd7f890e2013-12-28 21:56:47 +00001170void ScheduleDAGMILive::scheduleMI(SUnit *SU, bool IsTopNode) {
Andrew Trick7a8e1002012-09-11 00:39:15 +00001171 // Move the instruction to its new location in the instruction stream.
1172 MachineInstr *MI = SU->getInstr();
Andrew Trick02a80da2012-03-08 01:41:12 +00001173
Andrew Trick7a8e1002012-09-11 00:39:15 +00001174 if (IsTopNode) {
1175 assert(SU->isTopReady() && "node still has unscheduled dependencies");
1176 if (&*CurrentTop == MI)
1177 CurrentTop = nextIfDebug(++CurrentTop, CurrentBottom);
Andrew Trick8823dec2012-03-14 04:00:41 +00001178 else {
Andrew Trick7a8e1002012-09-11 00:39:15 +00001179 moveInstruction(MI, CurrentTop);
1180 TopRPTracker.setPos(MI);
Andrew Trick8823dec2012-03-14 04:00:41 +00001181 }
Andrew Trickc3ea0052012-04-24 18:04:37 +00001182
Andrew Trickb6e74712013-09-04 20:59:59 +00001183 if (ShouldTrackPressure) {
1184 // Update top scheduled pressure.
1185 TopRPTracker.advance();
1186 assert(TopRPTracker.getPos() == CurrentTop && "out of sync");
Andrew Trickb248b4a2013-09-06 17:32:47 +00001187 updateScheduledPressure(SU, TopRPTracker.getPressure().MaxSetPressure);
Andrew Trickb6e74712013-09-04 20:59:59 +00001188 }
Andrew Trick7a8e1002012-09-11 00:39:15 +00001189 }
1190 else {
1191 assert(SU->isBottomReady() && "node still has unscheduled dependencies");
1192 MachineBasicBlock::iterator priorII =
1193 priorNonDebug(CurrentBottom, CurrentTop);
1194 if (&*priorII == MI)
1195 CurrentBottom = priorII;
1196 else {
1197 if (&*CurrentTop == MI) {
1198 CurrentTop = nextIfDebug(++CurrentTop, priorII);
1199 TopRPTracker.setPos(CurrentTop);
1200 }
1201 moveInstruction(MI, CurrentBottom);
1202 CurrentBottom = MI;
1203 }
Andrew Trickb6e74712013-09-04 20:59:59 +00001204 if (ShouldTrackPressure) {
1205 // Update bottom scheduled pressure.
1206 SmallVector<unsigned, 8> LiveUses;
1207 BotRPTracker.recede(&LiveUses);
1208 assert(BotRPTracker.getPos() == CurrentBottom && "out of sync");
Andrew Trickb248b4a2013-09-06 17:32:47 +00001209 updateScheduledPressure(SU, BotRPTracker.getPressure().MaxSetPressure);
Andrew Trickb6e74712013-09-04 20:59:59 +00001210 updatePressureDiffs(LiveUses);
Andrew Trickb6e74712013-09-04 20:59:59 +00001211 }
Andrew Trick7a8e1002012-09-11 00:39:15 +00001212 }
1213}
1214
Andrew Trick263280242012-11-12 19:52:20 +00001215//===----------------------------------------------------------------------===//
1216// LoadClusterMutation - DAG post-processing to cluster loads.
1217//===----------------------------------------------------------------------===//
1218
Andrew Tricka7714a02012-11-12 19:40:10 +00001219namespace {
1220/// \brief Post-process the DAG to create cluster edges between neighboring
1221/// loads.
1222class LoadClusterMutation : public ScheduleDAGMutation {
1223 struct LoadInfo {
1224 SUnit *SU;
1225 unsigned BaseReg;
1226 unsigned Offset;
1227 LoadInfo(SUnit *su, unsigned reg, unsigned ofs)
1228 : SU(su), BaseReg(reg), Offset(ofs) {}
Benjamin Kramerb0f74b22014-03-07 21:35:39 +00001229
1230 bool operator<(const LoadInfo &RHS) const {
1231 return std::tie(BaseReg, Offset) < std::tie(RHS.BaseReg, RHS.Offset);
1232 }
Andrew Tricka7714a02012-11-12 19:40:10 +00001233 };
Andrew Tricka7714a02012-11-12 19:40:10 +00001234
1235 const TargetInstrInfo *TII;
1236 const TargetRegisterInfo *TRI;
1237public:
1238 LoadClusterMutation(const TargetInstrInfo *tii,
1239 const TargetRegisterInfo *tri)
1240 : TII(tii), TRI(tri) {}
1241
Craig Topper4584cd52014-03-07 09:26:03 +00001242 void apply(ScheduleDAGMI *DAG) override;
Andrew Tricka7714a02012-11-12 19:40:10 +00001243protected:
1244 void clusterNeighboringLoads(ArrayRef<SUnit*> Loads, ScheduleDAGMI *DAG);
1245};
1246} // anonymous
1247
Andrew Tricka7714a02012-11-12 19:40:10 +00001248void LoadClusterMutation::clusterNeighboringLoads(ArrayRef<SUnit*> Loads,
1249 ScheduleDAGMI *DAG) {
1250 SmallVector<LoadClusterMutation::LoadInfo,32> LoadRecords;
1251 for (unsigned Idx = 0, End = Loads.size(); Idx != End; ++Idx) {
1252 SUnit *SU = Loads[Idx];
1253 unsigned BaseReg;
1254 unsigned Offset;
1255 if (TII->getLdStBaseRegImmOfs(SU->getInstr(), BaseReg, Offset, TRI))
1256 LoadRecords.push_back(LoadInfo(SU, BaseReg, Offset));
1257 }
1258 if (LoadRecords.size() < 2)
1259 return;
Benjamin Kramerb0f74b22014-03-07 21:35:39 +00001260 std::sort(LoadRecords.begin(), LoadRecords.end());
Andrew Tricka7714a02012-11-12 19:40:10 +00001261 unsigned ClusterLength = 1;
1262 for (unsigned Idx = 0, End = LoadRecords.size(); Idx < (End - 1); ++Idx) {
1263 if (LoadRecords[Idx].BaseReg != LoadRecords[Idx+1].BaseReg) {
1264 ClusterLength = 1;
1265 continue;
1266 }
1267
1268 SUnit *SUa = LoadRecords[Idx].SU;
1269 SUnit *SUb = LoadRecords[Idx+1].SU;
Andrew Trickec369d52012-11-12 21:28:10 +00001270 if (TII->shouldClusterLoads(SUa->getInstr(), SUb->getInstr(), ClusterLength)
Andrew Tricka7714a02012-11-12 19:40:10 +00001271 && DAG->addEdge(SUb, SDep(SUa, SDep::Cluster))) {
1272
1273 DEBUG(dbgs() << "Cluster loads SU(" << SUa->NodeNum << ") - SU("
1274 << SUb->NodeNum << ")\n");
1275 // Copy successor edges from SUa to SUb. Interleaving computation
1276 // dependent on SUa can prevent load combining due to register reuse.
1277 // Predecessor edges do not need to be copied from SUb to SUa since nearby
1278 // loads should have effectively the same inputs.
1279 for (SUnit::const_succ_iterator
1280 SI = SUa->Succs.begin(), SE = SUa->Succs.end(); SI != SE; ++SI) {
1281 if (SI->getSUnit() == SUb)
1282 continue;
1283 DEBUG(dbgs() << " Copy Succ SU(" << SI->getSUnit()->NodeNum << ")\n");
1284 DAG->addEdge(SI->getSUnit(), SDep(SUb, SDep::Artificial));
1285 }
1286 ++ClusterLength;
1287 }
1288 else
1289 ClusterLength = 1;
1290 }
1291}
1292
1293/// \brief Callback from DAG postProcessing to create cluster edges for loads.
1294void LoadClusterMutation::apply(ScheduleDAGMI *DAG) {
1295 // Map DAG NodeNum to store chain ID.
1296 DenseMap<unsigned, unsigned> StoreChainIDs;
1297 // Map each store chain to a set of dependent loads.
1298 SmallVector<SmallVector<SUnit*,4>, 32> StoreChainDependents;
1299 for (unsigned Idx = 0, End = DAG->SUnits.size(); Idx != End; ++Idx) {
1300 SUnit *SU = &DAG->SUnits[Idx];
1301 if (!SU->getInstr()->mayLoad())
1302 continue;
1303 unsigned ChainPredID = DAG->SUnits.size();
1304 for (SUnit::const_pred_iterator
1305 PI = SU->Preds.begin(), PE = SU->Preds.end(); PI != PE; ++PI) {
1306 if (PI->isCtrl()) {
1307 ChainPredID = PI->getSUnit()->NodeNum;
1308 break;
1309 }
1310 }
1311 // Check if this chain-like pred has been seen
1312 // before. ChainPredID==MaxNodeID for loads at the top of the schedule.
1313 unsigned NumChains = StoreChainDependents.size();
1314 std::pair<DenseMap<unsigned, unsigned>::iterator, bool> Result =
1315 StoreChainIDs.insert(std::make_pair(ChainPredID, NumChains));
1316 if (Result.second)
1317 StoreChainDependents.resize(NumChains + 1);
1318 StoreChainDependents[Result.first->second].push_back(SU);
1319 }
1320 // Iterate over the store chains.
1321 for (unsigned Idx = 0, End = StoreChainDependents.size(); Idx != End; ++Idx)
1322 clusterNeighboringLoads(StoreChainDependents[Idx], DAG);
1323}
1324
Andrew Trick02a80da2012-03-08 01:41:12 +00001325//===----------------------------------------------------------------------===//
Andrew Trick263280242012-11-12 19:52:20 +00001326// MacroFusion - DAG post-processing to encourage fusion of macro ops.
1327//===----------------------------------------------------------------------===//
1328
1329namespace {
1330/// \brief Post-process the DAG to create cluster edges between instructions
1331/// that may be fused by the processor into a single operation.
1332class MacroFusion : public ScheduleDAGMutation {
1333 const TargetInstrInfo *TII;
1334public:
1335 MacroFusion(const TargetInstrInfo *tii): TII(tii) {}
1336
Craig Topper4584cd52014-03-07 09:26:03 +00001337 void apply(ScheduleDAGMI *DAG) override;
Andrew Trick263280242012-11-12 19:52:20 +00001338};
1339} // anonymous
1340
1341/// \brief Callback from DAG postProcessing to create cluster edges to encourage
1342/// fused operations.
1343void MacroFusion::apply(ScheduleDAGMI *DAG) {
1344 // For now, assume targets can only fuse with the branch.
1345 MachineInstr *Branch = DAG->ExitSU.getInstr();
1346 if (!Branch)
1347 return;
1348
1349 for (unsigned Idx = DAG->SUnits.size(); Idx > 0;) {
1350 SUnit *SU = &DAG->SUnits[--Idx];
1351 if (!TII->shouldScheduleAdjacent(SU->getInstr(), Branch))
1352 continue;
1353
1354 // Create a single weak edge from SU to ExitSU. The only effect is to cause
1355 // bottom-up scheduling to heavily prioritize the clustered SU. There is no
1356 // need to copy predecessor edges from ExitSU to SU, since top-down
1357 // scheduling cannot prioritize ExitSU anyway. To defer top-down scheduling
1358 // of SU, we could create an artificial edge from the deepest root, but it
1359 // hasn't been needed yet.
1360 bool Success = DAG->addEdge(&DAG->ExitSU, SDep(SU, SDep::Cluster));
1361 (void)Success;
1362 assert(Success && "No DAG nodes should be reachable from ExitSU");
1363
1364 DEBUG(dbgs() << "Macro Fuse SU(" << SU->NodeNum << ")\n");
1365 break;
1366 }
1367}
1368
1369//===----------------------------------------------------------------------===//
Andrew Trick85a1d4c2013-04-24 15:54:43 +00001370// CopyConstrain - DAG post-processing to encourage copy elimination.
1371//===----------------------------------------------------------------------===//
1372
1373namespace {
1374/// \brief Post-process the DAG to create weak edges from all uses of a copy to
1375/// the one use that defines the copy's source vreg, most likely an induction
1376/// variable increment.
1377class CopyConstrain : public ScheduleDAGMutation {
1378 // Transient state.
1379 SlotIndex RegionBeginIdx;
Andrew Trick2e875172013-04-24 23:19:56 +00001380 // RegionEndIdx is the slot index of the last non-debug instruction in the
1381 // scheduling region. So we may have RegionBeginIdx == RegionEndIdx.
Andrew Trick85a1d4c2013-04-24 15:54:43 +00001382 SlotIndex RegionEndIdx;
1383public:
1384 CopyConstrain(const TargetInstrInfo *, const TargetRegisterInfo *) {}
1385
Craig Topper4584cd52014-03-07 09:26:03 +00001386 void apply(ScheduleDAGMI *DAG) override;
Andrew Trick85a1d4c2013-04-24 15:54:43 +00001387
1388protected:
Andrew Trickd7f890e2013-12-28 21:56:47 +00001389 void constrainLocalCopy(SUnit *CopySU, ScheduleDAGMILive *DAG);
Andrew Trick85a1d4c2013-04-24 15:54:43 +00001390};
1391} // anonymous
1392
1393/// constrainLocalCopy handles two possibilities:
1394/// 1) Local src:
1395/// I0: = dst
1396/// I1: src = ...
1397/// I2: = dst
1398/// I3: dst = src (copy)
1399/// (create pred->succ edges I0->I1, I2->I1)
1400///
1401/// 2) Local copy:
1402/// I0: dst = src (copy)
1403/// I1: = dst
1404/// I2: src = ...
1405/// I3: = dst
1406/// (create pred->succ edges I1->I2, I3->I2)
1407///
1408/// Although the MachineScheduler is currently constrained to single blocks,
1409/// this algorithm should handle extended blocks. An EBB is a set of
1410/// contiguously numbered blocks such that the previous block in the EBB is
1411/// always the single predecessor.
Andrew Trickd7f890e2013-12-28 21:56:47 +00001412void CopyConstrain::constrainLocalCopy(SUnit *CopySU, ScheduleDAGMILive *DAG) {
Andrew Trick85a1d4c2013-04-24 15:54:43 +00001413 LiveIntervals *LIS = DAG->getLIS();
1414 MachineInstr *Copy = CopySU->getInstr();
1415
1416 // Check for pure vreg copies.
1417 unsigned SrcReg = Copy->getOperand(1).getReg();
1418 if (!TargetRegisterInfo::isVirtualRegister(SrcReg))
1419 return;
1420
1421 unsigned DstReg = Copy->getOperand(0).getReg();
1422 if (!TargetRegisterInfo::isVirtualRegister(DstReg))
1423 return;
1424
1425 // Check if either the dest or source is local. If it's live across a back
1426 // edge, it's not local. Note that if both vregs are live across the back
1427 // edge, we cannot successfully contrain the copy without cyclic scheduling.
1428 unsigned LocalReg = DstReg;
1429 unsigned GlobalReg = SrcReg;
1430 LiveInterval *LocalLI = &LIS->getInterval(LocalReg);
1431 if (!LocalLI->isLocal(RegionBeginIdx, RegionEndIdx)) {
1432 LocalReg = SrcReg;
1433 GlobalReg = DstReg;
1434 LocalLI = &LIS->getInterval(LocalReg);
1435 if (!LocalLI->isLocal(RegionBeginIdx, RegionEndIdx))
1436 return;
1437 }
1438 LiveInterval *GlobalLI = &LIS->getInterval(GlobalReg);
1439
1440 // Find the global segment after the start of the local LI.
1441 LiveInterval::iterator GlobalSegment = GlobalLI->find(LocalLI->beginIndex());
1442 // If GlobalLI does not overlap LocalLI->start, then a copy directly feeds a
1443 // local live range. We could create edges from other global uses to the local
1444 // start, but the coalescer should have already eliminated these cases, so
1445 // don't bother dealing with it.
1446 if (GlobalSegment == GlobalLI->end())
1447 return;
1448
1449 // If GlobalSegment is killed at the LocalLI->start, the call to find()
1450 // returned the next global segment. But if GlobalSegment overlaps with
1451 // LocalLI->start, then advance to the next segement. If a hole in GlobalLI
1452 // exists in LocalLI's vicinity, GlobalSegment will be the end of the hole.
1453 if (GlobalSegment->contains(LocalLI->beginIndex()))
1454 ++GlobalSegment;
1455
1456 if (GlobalSegment == GlobalLI->end())
1457 return;
1458
1459 // Check if GlobalLI contains a hole in the vicinity of LocalLI.
1460 if (GlobalSegment != GlobalLI->begin()) {
1461 // Two address defs have no hole.
Benjamin Kramerb6d0bd42014-03-02 12:27:27 +00001462 if (SlotIndex::isSameInstr(std::prev(GlobalSegment)->end,
Andrew Trick85a1d4c2013-04-24 15:54:43 +00001463 GlobalSegment->start)) {
1464 return;
1465 }
Andrew Trickd9761772013-07-30 19:59:08 +00001466 // If the prior global segment may be defined by the same two-address
1467 // instruction that also defines LocalLI, then can't make a hole here.
Benjamin Kramerb6d0bd42014-03-02 12:27:27 +00001468 if (SlotIndex::isSameInstr(std::prev(GlobalSegment)->start,
Andrew Trickd9761772013-07-30 19:59:08 +00001469 LocalLI->beginIndex())) {
1470 return;
1471 }
Andrew Trick85a1d4c2013-04-24 15:54:43 +00001472 // If GlobalLI has a prior segment, it must be live into the EBB. Otherwise
1473 // it would be a disconnected component in the live range.
Benjamin Kramerb6d0bd42014-03-02 12:27:27 +00001474 assert(std::prev(GlobalSegment)->start < LocalLI->beginIndex() &&
Andrew Trick85a1d4c2013-04-24 15:54:43 +00001475 "Disconnected LRG within the scheduling region.");
1476 }
1477 MachineInstr *GlobalDef = LIS->getInstructionFromIndex(GlobalSegment->start);
1478 if (!GlobalDef)
1479 return;
1480
1481 SUnit *GlobalSU = DAG->getSUnit(GlobalDef);
1482 if (!GlobalSU)
1483 return;
1484
1485 // GlobalDef is the bottom of the GlobalLI hole. Open the hole by
1486 // constraining the uses of the last local def to precede GlobalDef.
1487 SmallVector<SUnit*,8> LocalUses;
1488 const VNInfo *LastLocalVN = LocalLI->getVNInfoBefore(LocalLI->endIndex());
1489 MachineInstr *LastLocalDef = LIS->getInstructionFromIndex(LastLocalVN->def);
1490 SUnit *LastLocalSU = DAG->getSUnit(LastLocalDef);
1491 for (SUnit::const_succ_iterator
1492 I = LastLocalSU->Succs.begin(), E = LastLocalSU->Succs.end();
1493 I != E; ++I) {
1494 if (I->getKind() != SDep::Data || I->getReg() != LocalReg)
1495 continue;
1496 if (I->getSUnit() == GlobalSU)
1497 continue;
1498 if (!DAG->canAddEdge(GlobalSU, I->getSUnit()))
1499 return;
1500 LocalUses.push_back(I->getSUnit());
1501 }
1502 // Open the top of the GlobalLI hole by constraining any earlier global uses
1503 // to precede the start of LocalLI.
1504 SmallVector<SUnit*,8> GlobalUses;
1505 MachineInstr *FirstLocalDef =
1506 LIS->getInstructionFromIndex(LocalLI->beginIndex());
1507 SUnit *FirstLocalSU = DAG->getSUnit(FirstLocalDef);
1508 for (SUnit::const_pred_iterator
1509 I = GlobalSU->Preds.begin(), E = GlobalSU->Preds.end(); I != E; ++I) {
1510 if (I->getKind() != SDep::Anti || I->getReg() != GlobalReg)
1511 continue;
1512 if (I->getSUnit() == FirstLocalSU)
1513 continue;
1514 if (!DAG->canAddEdge(FirstLocalSU, I->getSUnit()))
1515 return;
1516 GlobalUses.push_back(I->getSUnit());
1517 }
1518 DEBUG(dbgs() << "Constraining copy SU(" << CopySU->NodeNum << ")\n");
1519 // Add the weak edges.
1520 for (SmallVectorImpl<SUnit*>::const_iterator
1521 I = LocalUses.begin(), E = LocalUses.end(); I != E; ++I) {
1522 DEBUG(dbgs() << " Local use SU(" << (*I)->NodeNum << ") -> SU("
1523 << GlobalSU->NodeNum << ")\n");
1524 DAG->addEdge(GlobalSU, SDep(*I, SDep::Weak));
1525 }
1526 for (SmallVectorImpl<SUnit*>::const_iterator
1527 I = GlobalUses.begin(), E = GlobalUses.end(); I != E; ++I) {
1528 DEBUG(dbgs() << " Global use SU(" << (*I)->NodeNum << ") -> SU("
1529 << FirstLocalSU->NodeNum << ")\n");
1530 DAG->addEdge(FirstLocalSU, SDep(*I, SDep::Weak));
1531 }
1532}
1533
1534/// \brief Callback from DAG postProcessing to create weak edges to encourage
1535/// copy elimination.
1536void CopyConstrain::apply(ScheduleDAGMI *DAG) {
Andrew Trickd7f890e2013-12-28 21:56:47 +00001537 assert(DAG->hasVRegLiveness() && "Expect VRegs with LiveIntervals");
1538
Andrew Trick2e875172013-04-24 23:19:56 +00001539 MachineBasicBlock::iterator FirstPos = nextIfDebug(DAG->begin(), DAG->end());
1540 if (FirstPos == DAG->end())
1541 return;
1542 RegionBeginIdx = DAG->getLIS()->getInstructionIndex(&*FirstPos);
Andrew Trick85a1d4c2013-04-24 15:54:43 +00001543 RegionEndIdx = DAG->getLIS()->getInstructionIndex(
1544 &*priorNonDebug(DAG->end(), DAG->begin()));
1545
1546 for (unsigned Idx = 0, End = DAG->SUnits.size(); Idx != End; ++Idx) {
1547 SUnit *SU = &DAG->SUnits[Idx];
1548 if (!SU->getInstr()->isCopy())
1549 continue;
1550
Andrew Trickd7f890e2013-12-28 21:56:47 +00001551 constrainLocalCopy(SU, static_cast<ScheduleDAGMILive*>(DAG));
Andrew Trick85a1d4c2013-04-24 15:54:43 +00001552 }
1553}
1554
1555//===----------------------------------------------------------------------===//
Andrew Trickfc127d12013-12-07 05:59:44 +00001556// MachineSchedStrategy helpers used by GenericScheduler, GenericPostScheduler
1557// and possibly other custom schedulers.
Andrew Trickd14d7c22013-12-28 21:56:57 +00001558//===----------------------------------------------------------------------===//
Andrew Tricke1c034f2012-01-17 06:55:03 +00001559
Andrew Trick5a22df42013-12-05 17:56:02 +00001560static const unsigned InvalidCycle = ~0U;
1561
Andrew Trickfc127d12013-12-07 05:59:44 +00001562SchedBoundary::~SchedBoundary() { delete HazardRec; }
Andrew Trick3ca33ac2012-11-07 07:05:09 +00001563
Andrew Trickfc127d12013-12-07 05:59:44 +00001564void SchedBoundary::reset() {
1565 // A new HazardRec is created for each DAG and owned by SchedBoundary.
1566 // Destroying and reconstructing it is very expensive though. So keep
1567 // invalid, placeholder HazardRecs.
1568 if (HazardRec && HazardRec->isEnabled()) {
1569 delete HazardRec;
Craig Topperc0196b12014-04-14 00:51:57 +00001570 HazardRec = nullptr;
Andrew Trickfc127d12013-12-07 05:59:44 +00001571 }
1572 Available.clear();
1573 Pending.clear();
1574 CheckPending = false;
1575 NextSUs.clear();
1576 CurrCycle = 0;
1577 CurrMOps = 0;
1578 MinReadyCycle = UINT_MAX;
1579 ExpectedLatency = 0;
1580 DependentLatency = 0;
1581 RetiredMOps = 0;
1582 MaxExecutedResCount = 0;
1583 ZoneCritResIdx = 0;
1584 IsResourceLimited = false;
1585 ReservedCycles.clear();
Andrew Trick3ca33ac2012-11-07 07:05:09 +00001586#ifndef NDEBUG
Andrew Trickd14d7c22013-12-28 21:56:57 +00001587 // Track the maximum number of stall cycles that could arise either from the
1588 // latency of a DAG edge or the number of cycles that a processor resource is
1589 // reserved (SchedBoundary::ReservedCycles).
Andrew Trick7f1ebbe2014-06-07 01:48:43 +00001590 MaxObservedStall = 0;
Andrew Trick3ca33ac2012-11-07 07:05:09 +00001591#endif
Andrew Trickfc127d12013-12-07 05:59:44 +00001592 // Reserve a zero-count for invalid CritResIdx.
1593 ExecutedResCounts.resize(1);
1594 assert(!ExecutedResCounts[0] && "nonzero count for bad resource");
1595}
Andrew Trick3ca33ac2012-11-07 07:05:09 +00001596
Andrew Trickfc127d12013-12-07 05:59:44 +00001597void SchedRemainder::
Andrew Trick3ca33ac2012-11-07 07:05:09 +00001598init(ScheduleDAGMI *DAG, const TargetSchedModel *SchedModel) {
1599 reset();
1600 if (!SchedModel->hasInstrSchedModel())
1601 return;
1602 RemainingCounts.resize(SchedModel->getNumProcResourceKinds());
1603 for (std::vector<SUnit>::iterator
1604 I = DAG->SUnits.begin(), E = DAG->SUnits.end(); I != E; ++I) {
1605 const MCSchedClassDesc *SC = DAG->getSchedClass(&*I);
Andrew Trickf78e7fa2013-06-15 05:39:19 +00001606 RemIssueCount += SchedModel->getNumMicroOps(I->getInstr(), SC)
1607 * SchedModel->getMicroOpFactor();
Andrew Trick3ca33ac2012-11-07 07:05:09 +00001608 for (TargetSchedModel::ProcResIter
1609 PI = SchedModel->getWriteProcResBegin(SC),
1610 PE = SchedModel->getWriteProcResEnd(SC); PI != PE; ++PI) {
1611 unsigned PIdx = PI->ProcResourceIdx;
1612 unsigned Factor = SchedModel->getResourceFactor(PIdx);
1613 RemainingCounts[PIdx] += (Factor * PI->Cycles);
1614 }
1615 }
1616}
1617
Andrew Trickfc127d12013-12-07 05:59:44 +00001618void SchedBoundary::
Andrew Trick3ca33ac2012-11-07 07:05:09 +00001619init(ScheduleDAGMI *dag, const TargetSchedModel *smodel, SchedRemainder *rem) {
1620 reset();
1621 DAG = dag;
1622 SchedModel = smodel;
1623 Rem = rem;
Andrew Trick5a22df42013-12-05 17:56:02 +00001624 if (SchedModel->hasInstrSchedModel()) {
Andrew Trickf78e7fa2013-06-15 05:39:19 +00001625 ExecutedResCounts.resize(SchedModel->getNumProcResourceKinds());
Andrew Trick5a22df42013-12-05 17:56:02 +00001626 ReservedCycles.resize(SchedModel->getNumProcResourceKinds(), InvalidCycle);
1627 }
Andrew Trick3ca33ac2012-11-07 07:05:09 +00001628}
1629
Andrew Trick880e5732013-12-05 17:55:58 +00001630/// Compute the stall cycles based on this SUnit's ready time. Heuristics treat
1631/// these "soft stalls" differently than the hard stall cycles based on CPU
1632/// resources and computed by checkHazard(). A fully in-order model
1633/// (MicroOpBufferSize==0) will not make use of this since instructions are not
1634/// available for scheduling until they are ready. However, a weaker in-order
1635/// model may use this for heuristics. For example, if a processor has in-order
1636/// behavior when reading certain resources, this may come into play.
Andrew Trickfc127d12013-12-07 05:59:44 +00001637unsigned SchedBoundary::getLatencyStallCycles(SUnit *SU) {
Andrew Trick880e5732013-12-05 17:55:58 +00001638 if (!SU->isUnbuffered)
1639 return 0;
1640
1641 unsigned ReadyCycle = (isTop() ? SU->TopReadyCycle : SU->BotReadyCycle);
1642 if (ReadyCycle > CurrCycle)
1643 return ReadyCycle - CurrCycle;
1644 return 0;
1645}
1646
Andrew Trick5a22df42013-12-05 17:56:02 +00001647/// Compute the next cycle at which the given processor resource can be
1648/// scheduled.
Andrew Trickfc127d12013-12-07 05:59:44 +00001649unsigned SchedBoundary::
Andrew Trick5a22df42013-12-05 17:56:02 +00001650getNextResourceCycle(unsigned PIdx, unsigned Cycles) {
1651 unsigned NextUnreserved = ReservedCycles[PIdx];
1652 // If this resource has never been used, always return cycle zero.
1653 if (NextUnreserved == InvalidCycle)
1654 return 0;
1655 // For bottom-up scheduling add the cycles needed for the current operation.
1656 if (!isTop())
1657 NextUnreserved += Cycles;
1658 return NextUnreserved;
1659}
1660
Andrew Trick8c9e6722012-06-29 03:23:24 +00001661/// Does this SU have a hazard within the current instruction group.
1662///
1663/// The scheduler supports two modes of hazard recognition. The first is the
1664/// ScheduleHazardRecognizer API. It is a fully general hazard recognizer that
1665/// supports highly complicated in-order reservation tables
1666/// (ScoreboardHazardRecognizer) and arbitraty target-specific logic.
1667///
1668/// The second is a streamlined mechanism that checks for hazards based on
1669/// simple counters that the scheduler itself maintains. It explicitly checks
1670/// for instruction dispatch limitations, including the number of micro-ops that
1671/// can dispatch per cycle.
1672///
1673/// TODO: Also check whether the SU must start a new group.
Andrew Trickfc127d12013-12-07 05:59:44 +00001674bool SchedBoundary::checkHazard(SUnit *SU) {
Andrew Trickd14d7c22013-12-28 21:56:57 +00001675 if (HazardRec->isEnabled()
1676 && HazardRec->getHazardType(SU) != ScheduleHazardRecognizer::NoHazard) {
1677 return true;
1678 }
Andrew Trickdd79f0f2012-10-10 05:43:09 +00001679 unsigned uops = SchedModel->getNumMicroOps(SU->getInstr());
Andrew Tricke2ff5752013-06-15 04:49:49 +00001680 if ((CurrMOps > 0) && (CurrMOps + uops > SchedModel->getIssueWidth())) {
Andrew Trick3ca33ac2012-11-07 07:05:09 +00001681 DEBUG(dbgs() << " SU(" << SU->NodeNum << ") uops="
1682 << SchedModel->getNumMicroOps(SU->getInstr()) << '\n');
Andrew Trick8c9e6722012-06-29 03:23:24 +00001683 return true;
Andrew Trick3ca33ac2012-11-07 07:05:09 +00001684 }
Andrew Trick5a22df42013-12-05 17:56:02 +00001685 if (SchedModel->hasInstrSchedModel() && SU->hasReservedResource) {
1686 const MCSchedClassDesc *SC = DAG->getSchedClass(SU);
1687 for (TargetSchedModel::ProcResIter
1688 PI = SchedModel->getWriteProcResBegin(SC),
1689 PE = SchedModel->getWriteProcResEnd(SC); PI != PE; ++PI) {
Andrew Trick56327222014-06-27 04:57:05 +00001690 unsigned NRCycle = getNextResourceCycle(PI->ProcResourceIdx, PI->Cycles);
1691 if (NRCycle > CurrCycle) {
Andrew Trick040c0da2014-06-27 05:09:36 +00001692#ifndef NDEBUG
Chad Rosieraba845e2014-07-02 16:46:08 +00001693 MaxObservedStall = std::max(PI->Cycles, MaxObservedStall);
Andrew Trick040c0da2014-06-27 05:09:36 +00001694#endif
Andrew Trick56327222014-06-27 04:57:05 +00001695 DEBUG(dbgs() << " SU(" << SU->NodeNum << ") "
1696 << SchedModel->getResourceName(PI->ProcResourceIdx)
1697 << "=" << NRCycle << "c\n");
Andrew Trick5a22df42013-12-05 17:56:02 +00001698 return true;
Andrew Trick56327222014-06-27 04:57:05 +00001699 }
Andrew Trick5a22df42013-12-05 17:56:02 +00001700 }
1701 }
Andrew Trick8c9e6722012-06-29 03:23:24 +00001702 return false;
1703}
1704
Andrew Trickf78e7fa2013-06-15 05:39:19 +00001705// Find the unscheduled node in ReadySUs with the highest latency.
Andrew Trickfc127d12013-12-07 05:59:44 +00001706unsigned SchedBoundary::
Andrew Trickf78e7fa2013-06-15 05:39:19 +00001707findMaxLatency(ArrayRef<SUnit*> ReadySUs) {
Craig Topperc0196b12014-04-14 00:51:57 +00001708 SUnit *LateSU = nullptr;
Andrew Trickf78e7fa2013-06-15 05:39:19 +00001709 unsigned RemLatency = 0;
1710 for (ArrayRef<SUnit*>::iterator I = ReadySUs.begin(), E = ReadySUs.end();
Andrew Trickd6d5ad32012-12-18 20:52:56 +00001711 I != E; ++I) {
1712 unsigned L = getUnscheduledLatency(*I);
Andrew Trickf5b8ef22013-06-15 04:49:44 +00001713 if (L > RemLatency) {
Andrew Trickd6d5ad32012-12-18 20:52:56 +00001714 RemLatency = L;
Andrew Trickf78e7fa2013-06-15 05:39:19 +00001715 LateSU = *I;
Andrew Trickf5b8ef22013-06-15 04:49:44 +00001716 }
Andrew Trickd6d5ad32012-12-18 20:52:56 +00001717 }
Andrew Trickf78e7fa2013-06-15 05:39:19 +00001718 if (LateSU) {
1719 DEBUG(dbgs() << Available.getName() << " RemLatency SU("
1720 << LateSU->NodeNum << ") " << RemLatency << "c\n");
Andrew Trickd6d5ad32012-12-18 20:52:56 +00001721 }
Andrew Trickf78e7fa2013-06-15 05:39:19 +00001722 return RemLatency;
1723}
Andrew Trickf5b8ef22013-06-15 04:49:44 +00001724
Andrew Trickf78e7fa2013-06-15 05:39:19 +00001725// Count resources in this zone and the remaining unscheduled
1726// instruction. Return the max count, scaled. Set OtherCritIdx to the critical
1727// resource index, or zero if the zone is issue limited.
Andrew Trickfc127d12013-12-07 05:59:44 +00001728unsigned SchedBoundary::
Andrew Trickf78e7fa2013-06-15 05:39:19 +00001729getOtherResourceCount(unsigned &OtherCritIdx) {
Alexey Samsonov64c391d2013-07-19 08:55:18 +00001730 OtherCritIdx = 0;
Andrew Trickf78e7fa2013-06-15 05:39:19 +00001731 if (!SchedModel->hasInstrSchedModel())
1732 return 0;
1733
1734 unsigned OtherCritCount = Rem->RemIssueCount
1735 + (RetiredMOps * SchedModel->getMicroOpFactor());
1736 DEBUG(dbgs() << " " << Available.getName() << " + Remain MOps: "
1737 << OtherCritCount / SchedModel->getMicroOpFactor() << '\n');
Andrew Trickf78e7fa2013-06-15 05:39:19 +00001738 for (unsigned PIdx = 1, PEnd = SchedModel->getNumProcResourceKinds();
1739 PIdx != PEnd; ++PIdx) {
1740 unsigned OtherCount = getResourceCount(PIdx) + Rem->RemainingCounts[PIdx];
1741 if (OtherCount > OtherCritCount) {
1742 OtherCritCount = OtherCount;
1743 OtherCritIdx = PIdx;
1744 }
Andrew Trick3ca33ac2012-11-07 07:05:09 +00001745 }
Andrew Trickf78e7fa2013-06-15 05:39:19 +00001746 if (OtherCritIdx) {
1747 DEBUG(dbgs() << " " << Available.getName() << " + Remain CritRes: "
1748 << OtherCritCount / SchedModel->getResourceFactor(OtherCritIdx)
Andrew Trickfc127d12013-12-07 05:59:44 +00001749 << " " << SchedModel->getResourceName(OtherCritIdx) << "\n");
Andrew Trickf78e7fa2013-06-15 05:39:19 +00001750 }
1751 return OtherCritCount;
1752}
1753
Andrew Trickfc127d12013-12-07 05:59:44 +00001754void SchedBoundary::releaseNode(SUnit *SU, unsigned ReadyCycle) {
Andrew Trick7f1ebbe2014-06-07 01:48:43 +00001755 assert(SU->getInstr() && "Scheduled SUnit must have instr");
1756
1757#ifndef NDEBUG
Andrew Trick491e34a2014-06-12 22:36:28 +00001758 // ReadyCycle was been bumped up to the CurrCycle when this node was
1759 // scheduled, but CurrCycle may have been eagerly advanced immediately after
1760 // scheduling, so may now be greater than ReadyCycle.
1761 if (ReadyCycle > CurrCycle)
1762 MaxObservedStall = std::max(ReadyCycle - CurrCycle, MaxObservedStall);
Andrew Trick7f1ebbe2014-06-07 01:48:43 +00001763#endif
1764
Andrew Trick61f1a272012-05-24 22:11:09 +00001765 if (ReadyCycle < MinReadyCycle)
1766 MinReadyCycle = ReadyCycle;
1767
1768 // Check for interlocks first. For the purpose of other heuristics, an
1769 // instruction that cannot issue appears as if it's not in the ReadyQueue.
Andrew Trickf78e7fa2013-06-15 05:39:19 +00001770 bool IsBuffered = SchedModel->getMicroOpBufferSize() != 0;
1771 if ((!IsBuffered && ReadyCycle > CurrCycle) || checkHazard(SU))
Andrew Trick61f1a272012-05-24 22:11:09 +00001772 Pending.push(SU);
1773 else
1774 Available.push(SU);
Andrew Trick3ca33ac2012-11-07 07:05:09 +00001775
1776 // Record this node as an immediate dependent of the scheduled node.
1777 NextSUs.insert(SU);
Andrew Trick61f1a272012-05-24 22:11:09 +00001778}
1779
Andrew Trickfc127d12013-12-07 05:59:44 +00001780void SchedBoundary::releaseTopNode(SUnit *SU) {
1781 if (SU->isScheduled)
1782 return;
1783
Andrew Trickfc127d12013-12-07 05:59:44 +00001784 releaseNode(SU, SU->TopReadyCycle);
1785}
1786
1787void SchedBoundary::releaseBottomNode(SUnit *SU) {
1788 if (SU->isScheduled)
1789 return;
1790
Andrew Trickfc127d12013-12-07 05:59:44 +00001791 releaseNode(SU, SU->BotReadyCycle);
1792}
1793
Andrew Trick61f1a272012-05-24 22:11:09 +00001794/// Move the boundary of scheduled code by one cycle.
Andrew Trickfc127d12013-12-07 05:59:44 +00001795void SchedBoundary::bumpCycle(unsigned NextCycle) {
Andrew Trickf78e7fa2013-06-15 05:39:19 +00001796 if (SchedModel->getMicroOpBufferSize() == 0) {
1797 assert(MinReadyCycle < UINT_MAX && "MinReadyCycle uninitialized");
1798 if (MinReadyCycle > NextCycle)
1799 NextCycle = MinReadyCycle;
Andrew Trick3ca33ac2012-11-07 07:05:09 +00001800 }
Andrew Trickf78e7fa2013-06-15 05:39:19 +00001801 // Update the current micro-ops, which will issue in the next cycle.
1802 unsigned DecMOps = SchedModel->getIssueWidth() * (NextCycle - CurrCycle);
1803 CurrMOps = (CurrMOps <= DecMOps) ? 0 : CurrMOps - DecMOps;
1804
1805 // Decrement DependentLatency based on the next cycle.
Andrew Trickf5b8ef22013-06-15 04:49:44 +00001806 if ((NextCycle - CurrCycle) > DependentLatency)
1807 DependentLatency = 0;
1808 else
1809 DependentLatency -= (NextCycle - CurrCycle);
Andrew Trick61f1a272012-05-24 22:11:09 +00001810
1811 if (!HazardRec->isEnabled()) {
Andrew Trick45446062012-06-05 21:11:27 +00001812 // Bypass HazardRec virtual calls.
Andrew Trick61f1a272012-05-24 22:11:09 +00001813 CurrCycle = NextCycle;
1814 }
1815 else {
Andrew Trick45446062012-06-05 21:11:27 +00001816 // Bypass getHazardType calls in case of long latency.
Andrew Trick61f1a272012-05-24 22:11:09 +00001817 for (; CurrCycle != NextCycle; ++CurrCycle) {
1818 if (isTop())
1819 HazardRec->AdvanceCycle();
1820 else
1821 HazardRec->RecedeCycle();
1822 }
1823 }
1824 CheckPending = true;
Andrew Trickf78e7fa2013-06-15 05:39:19 +00001825 unsigned LFactor = SchedModel->getLatencyFactor();
1826 IsResourceLimited =
1827 (int)(getCriticalCount() - (getScheduledLatency() * LFactor))
1828 > (int)LFactor;
Andrew Trick61f1a272012-05-24 22:11:09 +00001829
Andrew Trickf78e7fa2013-06-15 05:39:19 +00001830 DEBUG(dbgs() << "Cycle: " << CurrCycle << ' ' << Available.getName() << '\n');
1831}
1832
Andrew Trickfc127d12013-12-07 05:59:44 +00001833void SchedBoundary::incExecutedResources(unsigned PIdx, unsigned Count) {
Andrew Trickf78e7fa2013-06-15 05:39:19 +00001834 ExecutedResCounts[PIdx] += Count;
1835 if (ExecutedResCounts[PIdx] > MaxExecutedResCount)
1836 MaxExecutedResCount = ExecutedResCounts[PIdx];
Andrew Trick61f1a272012-05-24 22:11:09 +00001837}
1838
Andrew Trick3ca33ac2012-11-07 07:05:09 +00001839/// Add the given processor resource to this scheduled zone.
Andrew Trickf78e7fa2013-06-15 05:39:19 +00001840///
1841/// \param Cycles indicates the number of consecutive (non-pipelined) cycles
1842/// during which this resource is consumed.
1843///
1844/// \return the next cycle at which the instruction may execute without
1845/// oversubscribing resources.
Andrew Trickfc127d12013-12-07 05:59:44 +00001846unsigned SchedBoundary::
Andrew Trick5a22df42013-12-05 17:56:02 +00001847countResource(unsigned PIdx, unsigned Cycles, unsigned NextCycle) {
Andrew Trick3ca33ac2012-11-07 07:05:09 +00001848 unsigned Factor = SchedModel->getResourceFactor(PIdx);
Andrew Trick3ca33ac2012-11-07 07:05:09 +00001849 unsigned Count = Factor * Cycles;
Andrew Trickfc127d12013-12-07 05:59:44 +00001850 DEBUG(dbgs() << " " << SchedModel->getResourceName(PIdx)
Andrew Trickf78e7fa2013-06-15 05:39:19 +00001851 << " +" << Cycles << "x" << Factor << "u\n");
1852
1853 // Update Executed resources counts.
1854 incExecutedResources(PIdx, Count);
Andrew Trick3ca33ac2012-11-07 07:05:09 +00001855 assert(Rem->RemainingCounts[PIdx] >= Count && "resource double counted");
1856 Rem->RemainingCounts[PIdx] -= Count;
1857
Andrew Trickb13ef172013-07-19 00:20:07 +00001858 // Check if this resource exceeds the current critical resource. If so, it
1859 // becomes the critical resource.
1860 if (ZoneCritResIdx != PIdx && (getResourceCount(PIdx) > getCriticalCount())) {
Andrew Trickf78e7fa2013-06-15 05:39:19 +00001861 ZoneCritResIdx = PIdx;
Andrew Trick3ca33ac2012-11-07 07:05:09 +00001862 DEBUG(dbgs() << " *** Critical resource "
Andrew Trickfc127d12013-12-07 05:59:44 +00001863 << SchedModel->getResourceName(PIdx) << ": "
Andrew Trickf78e7fa2013-06-15 05:39:19 +00001864 << getResourceCount(PIdx) / SchedModel->getLatencyFactor() << "c\n");
Andrew Trick3ca33ac2012-11-07 07:05:09 +00001865 }
Andrew Trick5a22df42013-12-05 17:56:02 +00001866 // For reserved resources, record the highest cycle using the resource.
1867 unsigned NextAvailable = getNextResourceCycle(PIdx, Cycles);
1868 if (NextAvailable > CurrCycle) {
1869 DEBUG(dbgs() << " Resource conflict: "
1870 << SchedModel->getProcResource(PIdx)->Name << " reserved until @"
1871 << NextAvailable << "\n");
1872 }
1873 return NextAvailable;
Andrew Trick3ca33ac2012-11-07 07:05:09 +00001874}
1875
Andrew Trick45446062012-06-05 21:11:27 +00001876/// Move the boundary of scheduled code by one SUnit.
Andrew Trickfc127d12013-12-07 05:59:44 +00001877void SchedBoundary::bumpNode(SUnit *SU) {
Andrew Trick45446062012-06-05 21:11:27 +00001878 // Update the reservation table.
1879 if (HazardRec->isEnabled()) {
1880 if (!isTop() && SU->isCall) {
1881 // Calls are scheduled with their preceding instructions. For bottom-up
1882 // scheduling, clear the pipeline state before emitting.
1883 HazardRec->Reset();
1884 }
1885 HazardRec->EmitInstruction(SU);
1886 }
Andrew Trick5a22df42013-12-05 17:56:02 +00001887 // checkHazard should prevent scheduling multiple instructions per cycle that
1888 // exceed the issue width.
Andrew Trickf78e7fa2013-06-15 05:39:19 +00001889 const MCSchedClassDesc *SC = DAG->getSchedClass(SU);
1890 unsigned IncMOps = SchedModel->getNumMicroOps(SU->getInstr());
Daniel Jasper0d92abd2013-12-06 08:58:22 +00001891 assert(
1892 (CurrMOps == 0 || (CurrMOps + IncMOps) <= SchedModel->getIssueWidth()) &&
Andrew Trickf7760a22013-12-06 17:19:20 +00001893 "Cannot schedule this instruction's MicroOps in the current cycle.");
Andrew Trick5a22df42013-12-05 17:56:02 +00001894
Andrew Trickf78e7fa2013-06-15 05:39:19 +00001895 unsigned ReadyCycle = (isTop() ? SU->TopReadyCycle : SU->BotReadyCycle);
1896 DEBUG(dbgs() << " Ready @" << ReadyCycle << "c\n");
1897
Andrew Trick5a22df42013-12-05 17:56:02 +00001898 unsigned NextCycle = CurrCycle;
Andrew Trickf78e7fa2013-06-15 05:39:19 +00001899 switch (SchedModel->getMicroOpBufferSize()) {
1900 case 0:
1901 assert(ReadyCycle <= CurrCycle && "Broken PendingQueue");
1902 break;
1903 case 1:
1904 if (ReadyCycle > NextCycle) {
1905 NextCycle = ReadyCycle;
1906 DEBUG(dbgs() << " *** Stall until: " << ReadyCycle << "\n");
1907 }
1908 break;
1909 default:
1910 // We don't currently model the OOO reorder buffer, so consider all
Andrew Trick880e5732013-12-05 17:55:58 +00001911 // scheduled MOps to be "retired". We do loosely model in-order resource
1912 // latency. If this instruction uses an in-order resource, account for any
1913 // likely stall cycles.
1914 if (SU->isUnbuffered && ReadyCycle > NextCycle)
1915 NextCycle = ReadyCycle;
Andrew Trickf78e7fa2013-06-15 05:39:19 +00001916 break;
1917 }
1918 RetiredMOps += IncMOps;
1919
1920 // Update resource counts and critical resource.
1921 if (SchedModel->hasInstrSchedModel()) {
1922 unsigned DecRemIssue = IncMOps * SchedModel->getMicroOpFactor();
1923 assert(Rem->RemIssueCount >= DecRemIssue && "MOps double counted");
1924 Rem->RemIssueCount -= DecRemIssue;
1925 if (ZoneCritResIdx) {
1926 // Scale scheduled micro-ops for comparing with the critical resource.
1927 unsigned ScaledMOps =
1928 RetiredMOps * SchedModel->getMicroOpFactor();
1929
1930 // If scaled micro-ops are now more than the previous critical resource by
1931 // a full cycle, then micro-ops issue becomes critical.
1932 if ((int)(ScaledMOps - getResourceCount(ZoneCritResIdx))
1933 >= (int)SchedModel->getLatencyFactor()) {
1934 ZoneCritResIdx = 0;
1935 DEBUG(dbgs() << " *** Critical resource NumMicroOps: "
1936 << ScaledMOps / SchedModel->getLatencyFactor() << "c\n");
1937 }
1938 }
1939 for (TargetSchedModel::ProcResIter
1940 PI = SchedModel->getWriteProcResBegin(SC),
1941 PE = SchedModel->getWriteProcResEnd(SC); PI != PE; ++PI) {
1942 unsigned RCycle =
Andrew Trick5a22df42013-12-05 17:56:02 +00001943 countResource(PI->ProcResourceIdx, PI->Cycles, NextCycle);
Andrew Trickf78e7fa2013-06-15 05:39:19 +00001944 if (RCycle > NextCycle)
1945 NextCycle = RCycle;
1946 }
Andrew Trick5a22df42013-12-05 17:56:02 +00001947 if (SU->hasReservedResource) {
1948 // For reserved resources, record the highest cycle using the resource.
1949 // For top-down scheduling, this is the cycle in which we schedule this
1950 // instruction plus the number of cycles the operations reserves the
1951 // resource. For bottom-up is it simply the instruction's cycle.
1952 for (TargetSchedModel::ProcResIter
1953 PI = SchedModel->getWriteProcResBegin(SC),
1954 PE = SchedModel->getWriteProcResEnd(SC); PI != PE; ++PI) {
1955 unsigned PIdx = PI->ProcResourceIdx;
Andrew Trickd14d7c22013-12-28 21:56:57 +00001956 if (SchedModel->getProcResource(PIdx)->BufferSize == 0) {
Chad Rosieraba845e2014-07-02 16:46:08 +00001957 if (isTop()) {
1958 ReservedCycles[PIdx] =
1959 std::max(getNextResourceCycle(PIdx, 0), NextCycle + PI->Cycles);
1960 }
1961 else
1962 ReservedCycles[PIdx] = NextCycle;
Andrew Trickd14d7c22013-12-28 21:56:57 +00001963 }
Andrew Trick5a22df42013-12-05 17:56:02 +00001964 }
1965 }
Andrew Trickf78e7fa2013-06-15 05:39:19 +00001966 }
1967 // Update ExpectedLatency and DependentLatency.
1968 unsigned &TopLatency = isTop() ? ExpectedLatency : DependentLatency;
1969 unsigned &BotLatency = isTop() ? DependentLatency : ExpectedLatency;
1970 if (SU->getDepth() > TopLatency) {
1971 TopLatency = SU->getDepth();
1972 DEBUG(dbgs() << " " << Available.getName()
1973 << " TopLatency SU(" << SU->NodeNum << ") " << TopLatency << "c\n");
1974 }
1975 if (SU->getHeight() > BotLatency) {
1976 BotLatency = SU->getHeight();
1977 DEBUG(dbgs() << " " << Available.getName()
1978 << " BotLatency SU(" << SU->NodeNum << ") " << BotLatency << "c\n");
1979 }
1980 // If we stall for any reason, bump the cycle.
1981 if (NextCycle > CurrCycle) {
1982 bumpCycle(NextCycle);
1983 }
1984 else {
1985 // After updating ZoneCritResIdx and ExpectedLatency, check if we're
Alp Tokercb402912014-01-24 17:20:08 +00001986 // resource limited. If a stall occurred, bumpCycle does this.
Andrew Trickf78e7fa2013-06-15 05:39:19 +00001987 unsigned LFactor = SchedModel->getLatencyFactor();
1988 IsResourceLimited =
1989 (int)(getCriticalCount() - (getScheduledLatency() * LFactor))
1990 > (int)LFactor;
1991 }
Andrew Trick5a22df42013-12-05 17:56:02 +00001992 // Update CurrMOps after calling bumpCycle to handle stalls, since bumpCycle
1993 // resets CurrMOps. Loop to handle instructions with more MOps than issue in
1994 // one cycle. Since we commonly reach the max MOps here, opportunistically
1995 // bump the cycle to avoid uselessly checking everything in the readyQ.
1996 CurrMOps += IncMOps;
1997 while (CurrMOps >= SchedModel->getIssueWidth()) {
Andrew Trick5a22df42013-12-05 17:56:02 +00001998 DEBUG(dbgs() << " *** Max MOps " << CurrMOps
1999 << " at cycle " << CurrCycle << '\n');
Andrew Trickd14d7c22013-12-28 21:56:57 +00002000 bumpCycle(++NextCycle);
Andrew Trick5a22df42013-12-05 17:56:02 +00002001 }
Andrew Trickf78e7fa2013-06-15 05:39:19 +00002002 DEBUG(dumpScheduledState());
Andrew Trick45446062012-06-05 21:11:27 +00002003}
2004
Andrew Trick61f1a272012-05-24 22:11:09 +00002005/// Release pending ready nodes in to the available queue. This makes them
2006/// visible to heuristics.
Andrew Trickfc127d12013-12-07 05:59:44 +00002007void SchedBoundary::releasePending() {
Andrew Trick61f1a272012-05-24 22:11:09 +00002008 // If the available queue is empty, it is safe to reset MinReadyCycle.
2009 if (Available.empty())
2010 MinReadyCycle = UINT_MAX;
2011
2012 // Check to see if any of the pending instructions are ready to issue. If
2013 // so, add them to the available queue.
Andrew Trickf78e7fa2013-06-15 05:39:19 +00002014 bool IsBuffered = SchedModel->getMicroOpBufferSize() != 0;
Andrew Trick61f1a272012-05-24 22:11:09 +00002015 for (unsigned i = 0, e = Pending.size(); i != e; ++i) {
2016 SUnit *SU = *(Pending.begin()+i);
Andrew Trick45446062012-06-05 21:11:27 +00002017 unsigned ReadyCycle = isTop() ? SU->TopReadyCycle : SU->BotReadyCycle;
Andrew Trick61f1a272012-05-24 22:11:09 +00002018
2019 if (ReadyCycle < MinReadyCycle)
2020 MinReadyCycle = ReadyCycle;
2021
Andrew Trickf78e7fa2013-06-15 05:39:19 +00002022 if (!IsBuffered && ReadyCycle > CurrCycle)
Andrew Trick61f1a272012-05-24 22:11:09 +00002023 continue;
2024
Andrew Trick8c9e6722012-06-29 03:23:24 +00002025 if (checkHazard(SU))
Andrew Trick61f1a272012-05-24 22:11:09 +00002026 continue;
2027
2028 Available.push(SU);
2029 Pending.remove(Pending.begin()+i);
2030 --i; --e;
2031 }
Andrew Trick3ca33ac2012-11-07 07:05:09 +00002032 DEBUG(if (!Pending.empty()) Pending.dump());
Andrew Trick61f1a272012-05-24 22:11:09 +00002033 CheckPending = false;
2034}
2035
2036/// Remove SU from the ready set for this boundary.
Andrew Trickfc127d12013-12-07 05:59:44 +00002037void SchedBoundary::removeReady(SUnit *SU) {
Andrew Trick61f1a272012-05-24 22:11:09 +00002038 if (Available.isInQueue(SU))
2039 Available.remove(Available.find(SU));
2040 else {
2041 assert(Pending.isInQueue(SU) && "bad ready count");
2042 Pending.remove(Pending.find(SU));
2043 }
2044}
2045
2046/// If this queue only has one ready candidate, return it. As a side effect,
Andrew Trick3ca33ac2012-11-07 07:05:09 +00002047/// defer any nodes that now hit a hazard, and advance the cycle until at least
2048/// one node is ready. If multiple instructions are ready, return NULL.
Andrew Trickfc127d12013-12-07 05:59:44 +00002049SUnit *SchedBoundary::pickOnlyChoice() {
Andrew Trick61f1a272012-05-24 22:11:09 +00002050 if (CheckPending)
2051 releasePending();
2052
Andrew Tricke2ff5752013-06-15 04:49:49 +00002053 if (CurrMOps > 0) {
Andrew Trick3ca33ac2012-11-07 07:05:09 +00002054 // Defer any ready instrs that now have a hazard.
2055 for (ReadyQueue::iterator I = Available.begin(); I != Available.end();) {
2056 if (checkHazard(*I)) {
2057 Pending.push(*I);
2058 I = Available.remove(I);
2059 continue;
2060 }
2061 ++I;
2062 }
2063 }
Andrew Trick61f1a272012-05-24 22:11:09 +00002064 for (unsigned i = 0; Available.empty(); ++i) {
Chad Rosieraba845e2014-07-02 16:46:08 +00002065// FIXME: Re-enable assert once PR20057 is resolved.
2066// assert(i <= (HazardRec->getMaxLookAhead() + MaxObservedStall) &&
2067// "permanent hazard");
2068 (void)i;
Andrew Trickf78e7fa2013-06-15 05:39:19 +00002069 bumpCycle(CurrCycle + 1);
Andrew Trick61f1a272012-05-24 22:11:09 +00002070 releasePending();
2071 }
2072 if (Available.size() == 1)
2073 return *Available.begin();
Craig Topperc0196b12014-04-14 00:51:57 +00002074 return nullptr;
Andrew Trick61f1a272012-05-24 22:11:09 +00002075}
2076
Andrew Trick8e8415f2013-06-15 05:46:47 +00002077#ifndef NDEBUG
Andrew Trickf78e7fa2013-06-15 05:39:19 +00002078// This is useful information to dump after bumpNode.
2079// Note that the Queue contents are more useful before pickNodeFromQueue.
Andrew Trickfc127d12013-12-07 05:59:44 +00002080void SchedBoundary::dumpScheduledState() {
Andrew Trickf78e7fa2013-06-15 05:39:19 +00002081 unsigned ResFactor;
2082 unsigned ResCount;
2083 if (ZoneCritResIdx) {
2084 ResFactor = SchedModel->getResourceFactor(ZoneCritResIdx);
2085 ResCount = getResourceCount(ZoneCritResIdx);
Andrew Trick3ca33ac2012-11-07 07:05:09 +00002086 }
Andrew Trickf78e7fa2013-06-15 05:39:19 +00002087 else {
2088 ResFactor = SchedModel->getMicroOpFactor();
2089 ResCount = RetiredMOps * SchedModel->getMicroOpFactor();
Andrew Trick3ca33ac2012-11-07 07:05:09 +00002090 }
Andrew Trickf78e7fa2013-06-15 05:39:19 +00002091 unsigned LFactor = SchedModel->getLatencyFactor();
2092 dbgs() << Available.getName() << " @" << CurrCycle << "c\n"
2093 << " Retired: " << RetiredMOps;
2094 dbgs() << "\n Executed: " << getExecutedCount() / LFactor << "c";
2095 dbgs() << "\n Critical: " << ResCount / LFactor << "c, "
Andrew Trickfc127d12013-12-07 05:59:44 +00002096 << ResCount / ResFactor << " "
2097 << SchedModel->getResourceName(ZoneCritResIdx)
Andrew Trickf78e7fa2013-06-15 05:39:19 +00002098 << "\n ExpectedLatency: " << ExpectedLatency << "c\n"
2099 << (IsResourceLimited ? " - Resource" : " - Latency")
2100 << " limited.\n";
Andrew Trick3ca33ac2012-11-07 07:05:09 +00002101}
Andrew Trick8e8415f2013-06-15 05:46:47 +00002102#endif
Andrew Trick3ca33ac2012-11-07 07:05:09 +00002103
Andrew Trickfc127d12013-12-07 05:59:44 +00002104//===----------------------------------------------------------------------===//
Andrew Trickd14d7c22013-12-28 21:56:57 +00002105// GenericScheduler - Generic implementation of MachineSchedStrategy.
Andrew Trickfc127d12013-12-07 05:59:44 +00002106//===----------------------------------------------------------------------===//
2107
Andrew Trickd14d7c22013-12-28 21:56:57 +00002108void GenericSchedulerBase::SchedCandidate::
2109initResourceDelta(const ScheduleDAGMI *DAG,
2110 const TargetSchedModel *SchedModel) {
2111 if (!Policy.ReduceResIdx && !Policy.DemandResIdx)
2112 return;
2113
2114 const MCSchedClassDesc *SC = DAG->getSchedClass(SU);
2115 for (TargetSchedModel::ProcResIter
2116 PI = SchedModel->getWriteProcResBegin(SC),
2117 PE = SchedModel->getWriteProcResEnd(SC); PI != PE; ++PI) {
2118 if (PI->ProcResourceIdx == Policy.ReduceResIdx)
2119 ResDelta.CritResources += PI->Cycles;
2120 if (PI->ProcResourceIdx == Policy.DemandResIdx)
2121 ResDelta.DemandedResources += PI->Cycles;
2122 }
2123}
2124
2125/// Set the CandPolicy given a scheduling zone given the current resources and
2126/// latencies inside and outside the zone.
2127void GenericSchedulerBase::setPolicy(CandPolicy &Policy,
2128 bool IsPostRA,
2129 SchedBoundary &CurrZone,
2130 SchedBoundary *OtherZone) {
2131 // Apply preemptive heuristics based on the the total latency and resources
2132 // inside and outside this zone. Potential stalls should be considered before
2133 // following this policy.
2134
2135 // Compute remaining latency. We need this both to determine whether the
2136 // overall schedule has become latency-limited and whether the instructions
2137 // outside this zone are resource or latency limited.
2138 //
2139 // The "dependent" latency is updated incrementally during scheduling as the
2140 // max height/depth of scheduled nodes minus the cycles since it was
2141 // scheduled:
2142 // DLat = max (N.depth - (CurrCycle - N.ReadyCycle) for N in Zone
2143 //
2144 // The "independent" latency is the max ready queue depth:
2145 // ILat = max N.depth for N in Available|Pending
2146 //
2147 // RemainingLatency is the greater of independent and dependent latency.
2148 unsigned RemLatency = CurrZone.getDependentLatency();
2149 RemLatency = std::max(RemLatency,
2150 CurrZone.findMaxLatency(CurrZone.Available.elements()));
2151 RemLatency = std::max(RemLatency,
2152 CurrZone.findMaxLatency(CurrZone.Pending.elements()));
2153
2154 // Compute the critical resource outside the zone.
Andrew Trick7afe4812013-12-28 22:25:57 +00002155 unsigned OtherCritIdx = 0;
Andrew Trickd14d7c22013-12-28 21:56:57 +00002156 unsigned OtherCount =
2157 OtherZone ? OtherZone->getOtherResourceCount(OtherCritIdx) : 0;
2158
2159 bool OtherResLimited = false;
2160 if (SchedModel->hasInstrSchedModel()) {
2161 unsigned LFactor = SchedModel->getLatencyFactor();
2162 OtherResLimited = (int)(OtherCount - (RemLatency * LFactor)) > (int)LFactor;
2163 }
2164 // Schedule aggressively for latency in PostRA mode. We don't check for
2165 // acyclic latency during PostRA, and highly out-of-order processors will
2166 // skip PostRA scheduling.
2167 if (!OtherResLimited) {
2168 if (IsPostRA || (RemLatency + CurrZone.getCurrCycle() > Rem.CriticalPath)) {
2169 Policy.ReduceLatency |= true;
2170 DEBUG(dbgs() << " " << CurrZone.Available.getName()
2171 << " RemainingLatency " << RemLatency << " + "
2172 << CurrZone.getCurrCycle() << "c > CritPath "
2173 << Rem.CriticalPath << "\n");
2174 }
2175 }
2176 // If the same resource is limiting inside and outside the zone, do nothing.
2177 if (CurrZone.getZoneCritResIdx() == OtherCritIdx)
2178 return;
2179
2180 DEBUG(
2181 if (CurrZone.isResourceLimited()) {
2182 dbgs() << " " << CurrZone.Available.getName() << " ResourceLimited: "
2183 << SchedModel->getResourceName(CurrZone.getZoneCritResIdx())
2184 << "\n";
2185 }
2186 if (OtherResLimited)
2187 dbgs() << " RemainingLimit: "
2188 << SchedModel->getResourceName(OtherCritIdx) << "\n";
2189 if (!CurrZone.isResourceLimited() && !OtherResLimited)
2190 dbgs() << " Latency limited both directions.\n");
2191
2192 if (CurrZone.isResourceLimited() && !Policy.ReduceResIdx)
2193 Policy.ReduceResIdx = CurrZone.getZoneCritResIdx();
2194
2195 if (OtherResLimited)
2196 Policy.DemandResIdx = OtherCritIdx;
2197}
2198
2199#ifndef NDEBUG
2200const char *GenericSchedulerBase::getReasonStr(
2201 GenericSchedulerBase::CandReason Reason) {
2202 switch (Reason) {
2203 case NoCand: return "NOCAND ";
2204 case PhysRegCopy: return "PREG-COPY";
2205 case RegExcess: return "REG-EXCESS";
2206 case RegCritical: return "REG-CRIT ";
2207 case Stall: return "STALL ";
2208 case Cluster: return "CLUSTER ";
2209 case Weak: return "WEAK ";
2210 case RegMax: return "REG-MAX ";
2211 case ResourceReduce: return "RES-REDUCE";
2212 case ResourceDemand: return "RES-DEMAND";
2213 case TopDepthReduce: return "TOP-DEPTH ";
2214 case TopPathReduce: return "TOP-PATH ";
2215 case BotHeightReduce:return "BOT-HEIGHT";
2216 case BotPathReduce: return "BOT-PATH ";
2217 case NextDefUse: return "DEF-USE ";
2218 case NodeOrder: return "ORDER ";
2219 };
2220 llvm_unreachable("Unknown reason!");
2221}
2222
2223void GenericSchedulerBase::traceCandidate(const SchedCandidate &Cand) {
2224 PressureChange P;
2225 unsigned ResIdx = 0;
2226 unsigned Latency = 0;
2227 switch (Cand.Reason) {
2228 default:
2229 break;
2230 case RegExcess:
2231 P = Cand.RPDelta.Excess;
2232 break;
2233 case RegCritical:
2234 P = Cand.RPDelta.CriticalMax;
2235 break;
2236 case RegMax:
2237 P = Cand.RPDelta.CurrentMax;
2238 break;
2239 case ResourceReduce:
2240 ResIdx = Cand.Policy.ReduceResIdx;
2241 break;
2242 case ResourceDemand:
2243 ResIdx = Cand.Policy.DemandResIdx;
2244 break;
2245 case TopDepthReduce:
2246 Latency = Cand.SU->getDepth();
2247 break;
2248 case TopPathReduce:
2249 Latency = Cand.SU->getHeight();
2250 break;
2251 case BotHeightReduce:
2252 Latency = Cand.SU->getHeight();
2253 break;
2254 case BotPathReduce:
2255 Latency = Cand.SU->getDepth();
2256 break;
2257 }
2258 dbgs() << " SU(" << Cand.SU->NodeNum << ") " << getReasonStr(Cand.Reason);
2259 if (P.isValid())
2260 dbgs() << " " << TRI->getRegPressureSetName(P.getPSet())
2261 << ":" << P.getUnitInc() << " ";
2262 else
2263 dbgs() << " ";
2264 if (ResIdx)
2265 dbgs() << " " << SchedModel->getProcResource(ResIdx)->Name << " ";
2266 else
2267 dbgs() << " ";
2268 if (Latency)
2269 dbgs() << " " << Latency << " cycles ";
2270 else
2271 dbgs() << " ";
2272 dbgs() << '\n';
2273}
2274#endif
2275
2276/// Return true if this heuristic determines order.
2277static bool tryLess(int TryVal, int CandVal,
2278 GenericSchedulerBase::SchedCandidate &TryCand,
2279 GenericSchedulerBase::SchedCandidate &Cand,
2280 GenericSchedulerBase::CandReason Reason) {
2281 if (TryVal < CandVal) {
2282 TryCand.Reason = Reason;
2283 return true;
2284 }
2285 if (TryVal > CandVal) {
2286 if (Cand.Reason > Reason)
2287 Cand.Reason = Reason;
2288 return true;
2289 }
2290 Cand.setRepeat(Reason);
2291 return false;
2292}
2293
2294static bool tryGreater(int TryVal, int CandVal,
2295 GenericSchedulerBase::SchedCandidate &TryCand,
2296 GenericSchedulerBase::SchedCandidate &Cand,
2297 GenericSchedulerBase::CandReason Reason) {
2298 if (TryVal > CandVal) {
2299 TryCand.Reason = Reason;
2300 return true;
2301 }
2302 if (TryVal < CandVal) {
2303 if (Cand.Reason > Reason)
2304 Cand.Reason = Reason;
2305 return true;
2306 }
2307 Cand.setRepeat(Reason);
2308 return false;
2309}
2310
2311static bool tryLatency(GenericSchedulerBase::SchedCandidate &TryCand,
2312 GenericSchedulerBase::SchedCandidate &Cand,
2313 SchedBoundary &Zone) {
2314 if (Zone.isTop()) {
2315 if (Cand.SU->getDepth() > Zone.getScheduledLatency()) {
2316 if (tryLess(TryCand.SU->getDepth(), Cand.SU->getDepth(),
2317 TryCand, Cand, GenericSchedulerBase::TopDepthReduce))
2318 return true;
2319 }
2320 if (tryGreater(TryCand.SU->getHeight(), Cand.SU->getHeight(),
2321 TryCand, Cand, GenericSchedulerBase::TopPathReduce))
2322 return true;
2323 }
2324 else {
2325 if (Cand.SU->getHeight() > Zone.getScheduledLatency()) {
2326 if (tryLess(TryCand.SU->getHeight(), Cand.SU->getHeight(),
2327 TryCand, Cand, GenericSchedulerBase::BotHeightReduce))
2328 return true;
2329 }
2330 if (tryGreater(TryCand.SU->getDepth(), Cand.SU->getDepth(),
2331 TryCand, Cand, GenericSchedulerBase::BotPathReduce))
2332 return true;
2333 }
2334 return false;
2335}
2336
2337static void tracePick(const GenericSchedulerBase::SchedCandidate &Cand,
2338 bool IsTop) {
2339 DEBUG(dbgs() << "Pick " << (IsTop ? "Top " : "Bot ")
2340 << GenericSchedulerBase::getReasonStr(Cand.Reason) << '\n');
2341}
2342
Andrew Trickfc127d12013-12-07 05:59:44 +00002343void GenericScheduler::initialize(ScheduleDAGMI *dag) {
Andrew Trickd7f890e2013-12-28 21:56:47 +00002344 assert(dag->hasVRegLiveness() &&
2345 "(PreRA)GenericScheduler needs vreg liveness");
2346 DAG = static_cast<ScheduleDAGMILive*>(dag);
Andrew Trickfc127d12013-12-07 05:59:44 +00002347 SchedModel = DAG->getSchedModel();
2348 TRI = DAG->TRI;
2349
2350 Rem.init(DAG, SchedModel);
2351 Top.init(DAG, SchedModel, &Rem);
2352 Bot.init(DAG, SchedModel, &Rem);
2353
2354 // Initialize resource counts.
2355
2356 // Initialize the HazardRecognizers. If itineraries don't exist, are empty, or
2357 // are disabled, then these HazardRecs will be disabled.
2358 const InstrItineraryData *Itin = SchedModel->getInstrItineraries();
2359 const TargetMachine &TM = DAG->MF.getTarget();
2360 if (!Top.HazardRec) {
2361 Top.HazardRec =
Eric Christopherd9134482014-08-04 21:25:23 +00002362 TM.getSubtargetImpl()->getInstrInfo()->CreateTargetMIHazardRecognizer(
2363 Itin, DAG);
Andrew Trickfc127d12013-12-07 05:59:44 +00002364 }
2365 if (!Bot.HazardRec) {
2366 Bot.HazardRec =
Eric Christopherd9134482014-08-04 21:25:23 +00002367 TM.getSubtargetImpl()->getInstrInfo()->CreateTargetMIHazardRecognizer(
2368 Itin, DAG);
Andrew Trickfc127d12013-12-07 05:59:44 +00002369 }
2370}
2371
2372/// Initialize the per-region scheduling policy.
2373void GenericScheduler::initPolicy(MachineBasicBlock::iterator Begin,
2374 MachineBasicBlock::iterator End,
2375 unsigned NumRegionInstrs) {
2376 const TargetMachine &TM = Context->MF->getTarget();
Eric Christopherd9134482014-08-04 21:25:23 +00002377 const TargetLowering *TLI = TM.getSubtargetImpl()->getTargetLowering();
Andrew Trickfc127d12013-12-07 05:59:44 +00002378
2379 // Avoid setting up the register pressure tracker for small regions to save
2380 // compile time. As a rough heuristic, only track pressure when the number of
2381 // schedulable instructions exceeds half the integer register file.
Andrew Trick350ff2c2014-01-21 21:27:37 +00002382 RegionPolicy.ShouldTrackPressure = true;
Andrew Trick46753512014-01-22 03:38:55 +00002383 for (unsigned VT = MVT::i32; VT > (unsigned)MVT::i1; --VT) {
2384 MVT::SimpleValueType LegalIntVT = (MVT::SimpleValueType)VT;
2385 if (TLI->isTypeLegal(LegalIntVT)) {
Andrew Trick350ff2c2014-01-21 21:27:37 +00002386 unsigned NIntRegs = Context->RegClassInfo->getNumAllocatableRegs(
Andrew Trick46753512014-01-22 03:38:55 +00002387 TLI->getRegClassFor(LegalIntVT));
Andrew Trick350ff2c2014-01-21 21:27:37 +00002388 RegionPolicy.ShouldTrackPressure = NumRegionInstrs > (NIntRegs / 2);
2389 }
2390 }
Andrew Trickfc127d12013-12-07 05:59:44 +00002391
2392 // For generic targets, we default to bottom-up, because it's simpler and more
2393 // compile-time optimizations have been implemented in that direction.
2394 RegionPolicy.OnlyBottomUp = true;
2395
2396 // Allow the subtarget to override default policy.
2397 const TargetSubtargetInfo &ST = TM.getSubtarget<TargetSubtargetInfo>();
2398 ST.overrideSchedPolicy(RegionPolicy, Begin, End, NumRegionInstrs);
2399
2400 // After subtarget overrides, apply command line options.
2401 if (!EnableRegPressure)
2402 RegionPolicy.ShouldTrackPressure = false;
2403
2404 // Check -misched-topdown/bottomup can force or unforce scheduling direction.
2405 // e.g. -misched-bottomup=false allows scheduling in both directions.
2406 assert((!ForceTopDown || !ForceBottomUp) &&
2407 "-misched-topdown incompatible with -misched-bottomup");
2408 if (ForceBottomUp.getNumOccurrences() > 0) {
2409 RegionPolicy.OnlyBottomUp = ForceBottomUp;
2410 if (RegionPolicy.OnlyBottomUp)
2411 RegionPolicy.OnlyTopDown = false;
2412 }
2413 if (ForceTopDown.getNumOccurrences() > 0) {
2414 RegionPolicy.OnlyTopDown = ForceTopDown;
2415 if (RegionPolicy.OnlyTopDown)
2416 RegionPolicy.OnlyBottomUp = false;
2417 }
2418}
2419
2420/// Set IsAcyclicLatencyLimited if the acyclic path is longer than the cyclic
2421/// critical path by more cycles than it takes to drain the instruction buffer.
2422/// We estimate an upper bounds on in-flight instructions as:
2423///
2424/// CyclesPerIteration = max( CyclicPath, Loop-Resource-Height )
2425/// InFlightIterations = AcyclicPath / CyclesPerIteration
2426/// InFlightResources = InFlightIterations * LoopResources
2427///
2428/// TODO: Check execution resources in addition to IssueCount.
2429void GenericScheduler::checkAcyclicLatency() {
2430 if (Rem.CyclicCritPath == 0 || Rem.CyclicCritPath >= Rem.CriticalPath)
2431 return;
2432
2433 // Scaled number of cycles per loop iteration.
2434 unsigned IterCount =
2435 std::max(Rem.CyclicCritPath * SchedModel->getLatencyFactor(),
2436 Rem.RemIssueCount);
2437 // Scaled acyclic critical path.
2438 unsigned AcyclicCount = Rem.CriticalPath * SchedModel->getLatencyFactor();
2439 // InFlightCount = (AcyclicPath / IterCycles) * InstrPerLoop
2440 unsigned InFlightCount =
2441 (AcyclicCount * Rem.RemIssueCount + IterCount-1) / IterCount;
2442 unsigned BufferLimit =
2443 SchedModel->getMicroOpBufferSize() * SchedModel->getMicroOpFactor();
2444
2445 Rem.IsAcyclicLatencyLimited = InFlightCount > BufferLimit;
2446
2447 DEBUG(dbgs() << "IssueCycles="
2448 << Rem.RemIssueCount / SchedModel->getLatencyFactor() << "c "
2449 << "IterCycles=" << IterCount / SchedModel->getLatencyFactor()
2450 << "c NumIters=" << (AcyclicCount + IterCount-1) / IterCount
2451 << " InFlight=" << InFlightCount / SchedModel->getMicroOpFactor()
2452 << "m BufferLim=" << SchedModel->getMicroOpBufferSize() << "m\n";
2453 if (Rem.IsAcyclicLatencyLimited)
2454 dbgs() << " ACYCLIC LATENCY LIMIT\n");
2455}
2456
2457void GenericScheduler::registerRoots() {
2458 Rem.CriticalPath = DAG->ExitSU.getDepth();
2459
2460 // Some roots may not feed into ExitSU. Check all of them in case.
2461 for (std::vector<SUnit*>::const_iterator
2462 I = Bot.Available.begin(), E = Bot.Available.end(); I != E; ++I) {
2463 if ((*I)->getDepth() > Rem.CriticalPath)
2464 Rem.CriticalPath = (*I)->getDepth();
2465 }
2466 DEBUG(dbgs() << "Critical Path: " << Rem.CriticalPath << '\n');
2467
2468 if (EnableCyclicPath) {
2469 Rem.CyclicCritPath = DAG->computeCyclicCriticalPath();
2470 checkAcyclicLatency();
2471 }
2472}
2473
Andrew Trick1a831342013-08-30 03:49:48 +00002474static bool tryPressure(const PressureChange &TryP,
2475 const PressureChange &CandP,
Andrew Trickd14d7c22013-12-28 21:56:57 +00002476 GenericSchedulerBase::SchedCandidate &TryCand,
2477 GenericSchedulerBase::SchedCandidate &Cand,
2478 GenericSchedulerBase::CandReason Reason) {
Andrew Trickb1a45b62013-08-30 04:27:29 +00002479 int TryRank = TryP.getPSetOrMax();
2480 int CandRank = CandP.getPSetOrMax();
2481 // If both candidates affect the same set, go with the smallest increase.
2482 if (TryRank == CandRank) {
2483 return tryLess(TryP.getUnitInc(), CandP.getUnitInc(), TryCand, Cand,
2484 Reason);
Andrew Trick401b6952013-07-25 07:26:35 +00002485 }
Andrew Trickb1a45b62013-08-30 04:27:29 +00002486 // If one candidate decreases and the other increases, go with it.
2487 // Invalid candidates have UnitInc==0.
2488 if (tryLess(TryP.getUnitInc() < 0, CandP.getUnitInc() < 0, TryCand, Cand,
2489 Reason)) {
2490 return true;
2491 }
Andrew Trick401b6952013-07-25 07:26:35 +00002492 // If the candidates are decreasing pressure, reverse priority.
Andrew Trick1a831342013-08-30 03:49:48 +00002493 if (TryP.getUnitInc() < 0)
Andrew Trick401b6952013-07-25 07:26:35 +00002494 std::swap(TryRank, CandRank);
2495 return tryGreater(TryRank, CandRank, TryCand, Cand, Reason);
2496}
2497
Andrew Tricka7714a02012-11-12 19:40:10 +00002498static unsigned getWeakLeft(const SUnit *SU, bool isTop) {
2499 return (isTop) ? SU->WeakPredsLeft : SU->WeakSuccsLeft;
2500}
2501
Andrew Tricke833e1c2013-04-13 06:07:40 +00002502/// Minimize physical register live ranges. Regalloc wants them adjacent to
2503/// their physreg def/use.
2504///
2505/// FIXME: This is an unnecessary check on the critical path. Most are root/leaf
2506/// copies which can be prescheduled. The rest (e.g. x86 MUL) could be bundled
2507/// with the operation that produces or consumes the physreg. We'll do this when
2508/// regalloc has support for parallel copies.
2509static int biasPhysRegCopy(const SUnit *SU, bool isTop) {
2510 const MachineInstr *MI = SU->getInstr();
2511 if (!MI->isCopy())
2512 return 0;
2513
2514 unsigned ScheduledOper = isTop ? 1 : 0;
2515 unsigned UnscheduledOper = isTop ? 0 : 1;
2516 // If we have already scheduled the physreg produce/consumer, immediately
2517 // schedule the copy.
2518 if (TargetRegisterInfo::isPhysicalRegister(
2519 MI->getOperand(ScheduledOper).getReg()))
2520 return 1;
2521 // If the physreg is at the boundary, defer it. Otherwise schedule it
2522 // immediately to free the dependent. We can hoist the copy later.
2523 bool AtBoundary = isTop ? !SU->NumSuccsLeft : !SU->NumPredsLeft;
2524 if (TargetRegisterInfo::isPhysicalRegister(
2525 MI->getOperand(UnscheduledOper).getReg()))
2526 return AtBoundary ? -1 : 1;
2527 return 0;
2528}
2529
Andrew Trick3ca33ac2012-11-07 07:05:09 +00002530/// Apply a set of heursitics to a new candidate. Heuristics are currently
2531/// hierarchical. This may be more efficient than a graduated cost model because
2532/// we don't need to evaluate all aspects of the model for each node in the
2533/// queue. But it's really done to make the heuristics easier to debug and
2534/// statistically analyze.
2535///
2536/// \param Cand provides the policy and current best candidate.
2537/// \param TryCand refers to the next SUnit candidate, otherwise uninitialized.
2538/// \param Zone describes the scheduled zone that we are extending.
2539/// \param RPTracker describes reg pressure within the scheduled zone.
2540/// \param TempTracker is a scratch pressure tracker to reuse in queries.
Andrew Trick665d3ec2013-09-19 23:10:59 +00002541void GenericScheduler::tryCandidate(SchedCandidate &Cand,
Andrew Trickbb1247b2013-12-05 17:55:47 +00002542 SchedCandidate &TryCand,
2543 SchedBoundary &Zone,
2544 const RegPressureTracker &RPTracker,
2545 RegPressureTracker &TempTracker) {
Andrew Trick3ca33ac2012-11-07 07:05:09 +00002546
Andrew Trick66c3dfb2013-09-04 21:00:11 +00002547 if (DAG->isTrackingPressure()) {
Andrew Trick310190e2013-09-04 21:00:02 +00002548 // Always initialize TryCand's RPDelta.
2549 if (Zone.isTop()) {
2550 TempTracker.getMaxDownwardPressureDelta(
Andrew Trick1a831342013-08-30 03:49:48 +00002551 TryCand.SU->getInstr(),
Andrew Trick1a831342013-08-30 03:49:48 +00002552 TryCand.RPDelta,
2553 DAG->getRegionCriticalPSets(),
2554 DAG->getRegPressure().MaxSetPressure);
2555 }
2556 else {
Andrew Trick310190e2013-09-04 21:00:02 +00002557 if (VerifyScheduling) {
2558 TempTracker.getMaxUpwardPressureDelta(
2559 TryCand.SU->getInstr(),
2560 &DAG->getPressureDiff(TryCand.SU),
2561 TryCand.RPDelta,
2562 DAG->getRegionCriticalPSets(),
2563 DAG->getRegPressure().MaxSetPressure);
2564 }
2565 else {
2566 RPTracker.getUpwardPressureDelta(
2567 TryCand.SU->getInstr(),
2568 DAG->getPressureDiff(TryCand.SU),
2569 TryCand.RPDelta,
2570 DAG->getRegionCriticalPSets(),
2571 DAG->getRegPressure().MaxSetPressure);
2572 }
Andrew Trick1a831342013-08-30 03:49:48 +00002573 }
2574 }
Andrew Trickc573cd92013-09-06 17:32:44 +00002575 DEBUG(if (TryCand.RPDelta.Excess.isValid())
2576 dbgs() << " SU(" << TryCand.SU->NodeNum << ") "
2577 << TRI->getRegPressureSetName(TryCand.RPDelta.Excess.getPSet())
2578 << ":" << TryCand.RPDelta.Excess.getUnitInc() << "\n");
Andrew Trick3ca33ac2012-11-07 07:05:09 +00002579
2580 // Initialize the candidate if needed.
2581 if (!Cand.isValid()) {
2582 TryCand.Reason = NodeOrder;
2583 return;
2584 }
Andrew Tricke833e1c2013-04-13 06:07:40 +00002585
2586 if (tryGreater(biasPhysRegCopy(TryCand.SU, Zone.isTop()),
2587 biasPhysRegCopy(Cand.SU, Zone.isTop()),
2588 TryCand, Cand, PhysRegCopy))
2589 return;
2590
Andrew Trick401b6952013-07-25 07:26:35 +00002591 // Avoid exceeding the target's limit. If signed PSetID is negative, it is
2592 // invalid; convert it to INT_MAX to give it lowest priority.
Andrew Trick66c3dfb2013-09-04 21:00:11 +00002593 if (DAG->isTrackingPressure() && tryPressure(TryCand.RPDelta.Excess,
2594 Cand.RPDelta.Excess,
2595 TryCand, Cand, RegExcess))
Andrew Trick3ca33ac2012-11-07 07:05:09 +00002596 return;
Andrew Trick3ca33ac2012-11-07 07:05:09 +00002597
2598 // Avoid increasing the max critical pressure in the scheduled region.
Andrew Trick66c3dfb2013-09-04 21:00:11 +00002599 if (DAG->isTrackingPressure() && tryPressure(TryCand.RPDelta.CriticalMax,
2600 Cand.RPDelta.CriticalMax,
2601 TryCand, Cand, RegCritical))
Andrew Trick3ca33ac2012-11-07 07:05:09 +00002602 return;
Andrew Trick3ca33ac2012-11-07 07:05:09 +00002603
Andrew Trickddffae92013-09-06 17:32:36 +00002604 // For loops that are acyclic path limited, aggressively schedule for latency.
Andrew Tricke1f7bf22013-09-09 22:28:08 +00002605 // This can result in very long dependence chains scheduled in sequence, so
2606 // once every cycle (when CurrMOps == 0), switch to normal heuristics.
Andrew Trickfc127d12013-12-07 05:59:44 +00002607 if (Rem.IsAcyclicLatencyLimited && !Zone.getCurrMOps()
Andrew Tricke1f7bf22013-09-09 22:28:08 +00002608 && tryLatency(TryCand, Cand, Zone))
Andrew Trickddffae92013-09-06 17:32:36 +00002609 return;
2610
Andrew Trick880e5732013-12-05 17:55:58 +00002611 // Prioritize instructions that read unbuffered resources by stall cycles.
2612 if (tryLess(Zone.getLatencyStallCycles(TryCand.SU),
2613 Zone.getLatencyStallCycles(Cand.SU), TryCand, Cand, Stall))
2614 return;
2615
Andrew Tricka7714a02012-11-12 19:40:10 +00002616 // Keep clustered nodes together to encourage downstream peephole
2617 // optimizations which may reduce resource requirements.
2618 //
2619 // This is a best effort to set things up for a post-RA pass. Optimizations
2620 // like generating loads of multiple registers should ideally be done within
2621 // the scheduler pass by combining the loads during DAG postprocessing.
2622 const SUnit *NextClusterSU =
2623 Zone.isTop() ? DAG->getNextClusterSucc() : DAG->getNextClusterPred();
2624 if (tryGreater(TryCand.SU == NextClusterSU, Cand.SU == NextClusterSU,
2625 TryCand, Cand, Cluster))
2626 return;
Andrew Trick85a1d4c2013-04-24 15:54:43 +00002627
2628 // Weak edges are for clustering and other constraints.
Andrew Tricka7714a02012-11-12 19:40:10 +00002629 if (tryLess(getWeakLeft(TryCand.SU, Zone.isTop()),
2630 getWeakLeft(Cand.SU, Zone.isTop()),
Andrew Trick85a1d4c2013-04-24 15:54:43 +00002631 TryCand, Cand, Weak)) {
Andrew Tricka7714a02012-11-12 19:40:10 +00002632 return;
2633 }
Andrew Trick71f08a32013-06-17 21:45:13 +00002634 // Avoid increasing the max pressure of the entire region.
Andrew Trick66c3dfb2013-09-04 21:00:11 +00002635 if (DAG->isTrackingPressure() && tryPressure(TryCand.RPDelta.CurrentMax,
2636 Cand.RPDelta.CurrentMax,
2637 TryCand, Cand, RegMax))
Andrew Trick71f08a32013-06-17 21:45:13 +00002638 return;
2639
Andrew Trick3ca33ac2012-11-07 07:05:09 +00002640 // Avoid critical resource consumption and balance the schedule.
2641 TryCand.initResourceDelta(DAG, SchedModel);
2642 if (tryLess(TryCand.ResDelta.CritResources, Cand.ResDelta.CritResources,
2643 TryCand, Cand, ResourceReduce))
2644 return;
2645 if (tryGreater(TryCand.ResDelta.DemandedResources,
2646 Cand.ResDelta.DemandedResources,
2647 TryCand, Cand, ResourceDemand))
2648 return;
2649
2650 // Avoid serializing long latency dependence chains.
Andrew Trickc01b0042013-08-23 17:48:43 +00002651 // For acyclic path limited loops, latency was already checked above.
2652 if (Cand.Policy.ReduceLatency && !Rem.IsAcyclicLatencyLimited
2653 && tryLatency(TryCand, Cand, Zone)) {
2654 return;
Andrew Trick3ca33ac2012-11-07 07:05:09 +00002655 }
2656
Andrew Trick3ca33ac2012-11-07 07:05:09 +00002657 // Prefer immediate defs/users of the last scheduled instruction. This is a
Andrew Trickf78e7fa2013-06-15 05:39:19 +00002658 // local pressure avoidance strategy that also makes the machine code
2659 // readable.
Andrew Trickfc127d12013-12-07 05:59:44 +00002660 if (tryGreater(Zone.isNextSU(TryCand.SU), Zone.isNextSU(Cand.SU),
Andrew Tricka7714a02012-11-12 19:40:10 +00002661 TryCand, Cand, NextDefUse))
Andrew Trick3ca33ac2012-11-07 07:05:09 +00002662 return;
Andrew Tricka7714a02012-11-12 19:40:10 +00002663
Andrew Trick3ca33ac2012-11-07 07:05:09 +00002664 // Fall through to original instruction order.
2665 if ((Zone.isTop() && TryCand.SU->NodeNum < Cand.SU->NodeNum)
2666 || (!Zone.isTop() && TryCand.SU->NodeNum > Cand.SU->NodeNum)) {
2667 TryCand.Reason = NodeOrder;
2668 }
2669}
Andrew Trick419eae22012-05-10 21:06:19 +00002670
Andrew Trickc573cd92013-09-06 17:32:44 +00002671/// Pick the best candidate from the queue.
Andrew Trick7ee9de52012-05-10 21:06:16 +00002672///
2673/// TODO: getMaxPressureDelta results can be mostly cached for each SUnit during
2674/// DAG building. To adjust for the current scheduling location we need to
2675/// maintain the number of vreg uses remaining to be top-scheduled.
Andrew Trick665d3ec2013-09-19 23:10:59 +00002676void GenericScheduler::pickNodeFromQueue(SchedBoundary &Zone,
Andrew Trickbb1247b2013-12-05 17:55:47 +00002677 const RegPressureTracker &RPTracker,
2678 SchedCandidate &Cand) {
Andrew Trick3ca33ac2012-11-07 07:05:09 +00002679 ReadyQueue &Q = Zone.Available;
2680
Andrew Tricka8ad5f72012-05-24 22:11:12 +00002681 DEBUG(Q.dump());
Andrew Trick22025772012-05-17 18:35:10 +00002682
Andrew Trick7ee9de52012-05-10 21:06:16 +00002683 // getMaxPressureDelta temporarily modifies the tracker.
2684 RegPressureTracker &TempTracker = const_cast<RegPressureTracker&>(RPTracker);
2685
Andrew Trickdd375dd2012-05-24 22:11:03 +00002686 for (ReadyQueue::iterator I = Q.begin(), E = Q.end(); I != E; ++I) {
Andrew Trick7ee9de52012-05-10 21:06:16 +00002687
Andrew Trick3ca33ac2012-11-07 07:05:09 +00002688 SchedCandidate TryCand(Cand.Policy);
2689 TryCand.SU = *I;
2690 tryCandidate(Cand, TryCand, Zone, RPTracker, TempTracker);
2691 if (TryCand.Reason != NoCand) {
2692 // Initialize resource delta if needed in case future heuristics query it.
2693 if (TryCand.ResDelta == SchedResourceDelta())
2694 TryCand.initResourceDelta(DAG, SchedModel);
2695 Cand.setBest(TryCand);
Andrew Trick419d4912013-04-05 00:31:29 +00002696 DEBUG(traceCandidate(Cand));
Andrew Trick22025772012-05-17 18:35:10 +00002697 }
Andrew Trick7ee9de52012-05-10 21:06:16 +00002698 }
Andrew Trick3ca33ac2012-11-07 07:05:09 +00002699}
2700
Andrew Trick22025772012-05-17 18:35:10 +00002701/// Pick the best candidate node from either the top or bottom queue.
Andrew Trick665d3ec2013-09-19 23:10:59 +00002702SUnit *GenericScheduler::pickNodeBidirectional(bool &IsTopNode) {
Andrew Trick22025772012-05-17 18:35:10 +00002703 // Schedule as far as possible in the direction of no choice. This is most
2704 // efficient, but also provides the best heuristics for CriticalPSets.
Andrew Trick61f1a272012-05-24 22:11:09 +00002705 if (SUnit *SU = Bot.pickOnlyChoice()) {
Andrew Trick22025772012-05-17 18:35:10 +00002706 IsTopNode = false;
Andrew Trickf78e7fa2013-06-15 05:39:19 +00002707 DEBUG(dbgs() << "Pick Bot NOCAND\n");
Andrew Trick61f1a272012-05-24 22:11:09 +00002708 return SU;
Andrew Trick22025772012-05-17 18:35:10 +00002709 }
Andrew Trick61f1a272012-05-24 22:11:09 +00002710 if (SUnit *SU = Top.pickOnlyChoice()) {
Andrew Trick22025772012-05-17 18:35:10 +00002711 IsTopNode = true;
Andrew Trickf78e7fa2013-06-15 05:39:19 +00002712 DEBUG(dbgs() << "Pick Top NOCAND\n");
Andrew Trick61f1a272012-05-24 22:11:09 +00002713 return SU;
Andrew Trick22025772012-05-17 18:35:10 +00002714 }
Andrew Trick3ca33ac2012-11-07 07:05:09 +00002715 CandPolicy NoPolicy;
2716 SchedCandidate BotCand(NoPolicy);
2717 SchedCandidate TopCand(NoPolicy);
Andrew Trickfc127d12013-12-07 05:59:44 +00002718 // Set the bottom-up policy based on the state of the current bottom zone and
2719 // the instructions outside the zone, including the top zone.
Andrew Trickd14d7c22013-12-28 21:56:57 +00002720 setPolicy(BotCand.Policy, /*IsPostRA=*/false, Bot, &Top);
Andrew Trickfc127d12013-12-07 05:59:44 +00002721 // Set the top-down policy based on the state of the current top zone and
2722 // the instructions outside the zone, including the bottom zone.
Andrew Trickd14d7c22013-12-28 21:56:57 +00002723 setPolicy(TopCand.Policy, /*IsPostRA=*/false, Top, &Bot);
Andrew Trick3ca33ac2012-11-07 07:05:09 +00002724
Andrew Trick22025772012-05-17 18:35:10 +00002725 // Prefer bottom scheduling when heuristics are silent.
Andrew Trick3ca33ac2012-11-07 07:05:09 +00002726 pickNodeFromQueue(Bot, DAG->getBotRPTracker(), BotCand);
2727 assert(BotCand.Reason != NoCand && "failed to find the first candidate");
Andrew Trick22025772012-05-17 18:35:10 +00002728
2729 // If either Q has a single candidate that provides the least increase in
2730 // Excess pressure, we can immediately schedule from that Q.
2731 //
2732 // RegionCriticalPSets summarizes the pressure within the scheduled region and
2733 // affects picking from either Q. If scheduling in one direction must
2734 // increase pressure for one of the excess PSets, then schedule in that
2735 // direction first to provide more freedom in the other direction.
Andrew Trickd40d0f22013-06-17 21:45:05 +00002736 if ((BotCand.Reason == RegExcess && !BotCand.isRepeat(RegExcess))
2737 || (BotCand.Reason == RegCritical
2738 && !BotCand.isRepeat(RegCritical)))
2739 {
Andrew Trick22025772012-05-17 18:35:10 +00002740 IsTopNode = false;
Andrew Trick3ca33ac2012-11-07 07:05:09 +00002741 tracePick(BotCand, IsTopNode);
Andrew Trick61f1a272012-05-24 22:11:09 +00002742 return BotCand.SU;
Andrew Trick22025772012-05-17 18:35:10 +00002743 }
2744 // Check if the top Q has a better candidate.
Andrew Trick3ca33ac2012-11-07 07:05:09 +00002745 pickNodeFromQueue(Top, DAG->getTopRPTracker(), TopCand);
2746 assert(TopCand.Reason != NoCand && "failed to find the first candidate");
Andrew Trick22025772012-05-17 18:35:10 +00002747
Andrew Trickd40d0f22013-06-17 21:45:05 +00002748 // Choose the queue with the most important (lowest enum) reason.
Andrew Trick3ca33ac2012-11-07 07:05:09 +00002749 if (TopCand.Reason < BotCand.Reason) {
2750 IsTopNode = true;
2751 tracePick(TopCand, IsTopNode);
2752 return TopCand.SU;
2753 }
Andrew Trickd40d0f22013-06-17 21:45:05 +00002754 // Otherwise prefer the bottom candidate, in node order if all else failed.
Andrew Trick22025772012-05-17 18:35:10 +00002755 IsTopNode = false;
Andrew Trick3ca33ac2012-11-07 07:05:09 +00002756 tracePick(BotCand, IsTopNode);
Andrew Trick61f1a272012-05-24 22:11:09 +00002757 return BotCand.SU;
Andrew Trick22025772012-05-17 18:35:10 +00002758}
2759
2760/// Pick the best node to balance the schedule. Implements MachineSchedStrategy.
Andrew Trick665d3ec2013-09-19 23:10:59 +00002761SUnit *GenericScheduler::pickNode(bool &IsTopNode) {
Andrew Trick7ee9de52012-05-10 21:06:16 +00002762 if (DAG->top() == DAG->bottom()) {
Andrew Trick61f1a272012-05-24 22:11:09 +00002763 assert(Top.Available.empty() && Top.Pending.empty() &&
2764 Bot.Available.empty() && Bot.Pending.empty() && "ReadyQ garbage");
Craig Topperc0196b12014-04-14 00:51:57 +00002765 return nullptr;
Andrew Trick7ee9de52012-05-10 21:06:16 +00002766 }
Andrew Trick7ee9de52012-05-10 21:06:16 +00002767 SUnit *SU;
Andrew Trick984d98b2012-10-08 18:53:53 +00002768 do {
Andrew Trick75e411c2013-09-06 17:32:34 +00002769 if (RegionPolicy.OnlyTopDown) {
Andrew Trick984d98b2012-10-08 18:53:53 +00002770 SU = Top.pickOnlyChoice();
2771 if (!SU) {
Andrew Trick3ca33ac2012-11-07 07:05:09 +00002772 CandPolicy NoPolicy;
2773 SchedCandidate TopCand(NoPolicy);
2774 pickNodeFromQueue(Top, DAG->getTopRPTracker(), TopCand);
Andrew Trick1ab16d92013-09-04 21:00:13 +00002775 assert(TopCand.Reason != NoCand && "failed to find a candidate");
Andrew Trickef54c592013-09-04 21:00:16 +00002776 tracePick(TopCand, true);
Andrew Trick984d98b2012-10-08 18:53:53 +00002777 SU = TopCand.SU;
2778 }
2779 IsTopNode = true;
Andrew Tricka306a8a2012-05-24 23:11:17 +00002780 }
Andrew Trick75e411c2013-09-06 17:32:34 +00002781 else if (RegionPolicy.OnlyBottomUp) {
Andrew Trick984d98b2012-10-08 18:53:53 +00002782 SU = Bot.pickOnlyChoice();
2783 if (!SU) {
Andrew Trick3ca33ac2012-11-07 07:05:09 +00002784 CandPolicy NoPolicy;
2785 SchedCandidate BotCand(NoPolicy);
2786 pickNodeFromQueue(Bot, DAG->getBotRPTracker(), BotCand);
Andrew Trick1ab16d92013-09-04 21:00:13 +00002787 assert(BotCand.Reason != NoCand && "failed to find a candidate");
Andrew Trickef54c592013-09-04 21:00:16 +00002788 tracePick(BotCand, false);
Andrew Trick984d98b2012-10-08 18:53:53 +00002789 SU = BotCand.SU;
2790 }
2791 IsTopNode = false;
Andrew Tricka306a8a2012-05-24 23:11:17 +00002792 }
Andrew Trick984d98b2012-10-08 18:53:53 +00002793 else {
Andrew Trick3ca33ac2012-11-07 07:05:09 +00002794 SU = pickNodeBidirectional(IsTopNode);
Andrew Trick984d98b2012-10-08 18:53:53 +00002795 }
2796 } while (SU->isScheduled);
2797
Andrew Trick61f1a272012-05-24 22:11:09 +00002798 if (SU->isTopReady())
2799 Top.removeReady(SU);
2800 if (SU->isBottomReady())
2801 Bot.removeReady(SU);
Andrew Trick4e7f6a72012-05-25 02:02:39 +00002802
Andrew Trick1f0bb692013-04-13 06:07:49 +00002803 DEBUG(dbgs() << "Scheduling SU(" << SU->NodeNum << ") " << *SU->getInstr());
Andrew Trick7ee9de52012-05-10 21:06:16 +00002804 return SU;
2805}
2806
Andrew Trick665d3ec2013-09-19 23:10:59 +00002807void GenericScheduler::reschedulePhysRegCopies(SUnit *SU, bool isTop) {
Andrew Tricke833e1c2013-04-13 06:07:40 +00002808
2809 MachineBasicBlock::iterator InsertPos = SU->getInstr();
2810 if (!isTop)
2811 ++InsertPos;
2812 SmallVectorImpl<SDep> &Deps = isTop ? SU->Preds : SU->Succs;
2813
2814 // Find already scheduled copies with a single physreg dependence and move
2815 // them just above the scheduled instruction.
2816 for (SmallVectorImpl<SDep>::iterator I = Deps.begin(), E = Deps.end();
2817 I != E; ++I) {
2818 if (I->getKind() != SDep::Data || !TRI->isPhysicalRegister(I->getReg()))
2819 continue;
2820 SUnit *DepSU = I->getSUnit();
2821 if (isTop ? DepSU->Succs.size() > 1 : DepSU->Preds.size() > 1)
2822 continue;
2823 MachineInstr *Copy = DepSU->getInstr();
2824 if (!Copy->isCopy())
2825 continue;
2826 DEBUG(dbgs() << " Rescheduling physreg copy ";
2827 I->getSUnit()->dump(DAG));
2828 DAG->moveInstruction(Copy, InsertPos);
2829 }
2830}
2831
Andrew Trick61f1a272012-05-24 22:11:09 +00002832/// Update the scheduler's state after scheduling a node. This is the same node
Andrew Trickd14d7c22013-12-28 21:56:57 +00002833/// that was just returned by pickNode(). However, ScheduleDAGMILive needs to
2834/// update it's state based on the current cycle before MachineSchedStrategy
2835/// does.
Andrew Tricke833e1c2013-04-13 06:07:40 +00002836///
2837/// FIXME: Eventually, we may bundle physreg copies rather than rescheduling
2838/// them here. See comments in biasPhysRegCopy.
Andrew Trick665d3ec2013-09-19 23:10:59 +00002839void GenericScheduler::schedNode(SUnit *SU, bool IsTopNode) {
Andrew Trick45446062012-06-05 21:11:27 +00002840 if (IsTopNode) {
Andrew Trickfc127d12013-12-07 05:59:44 +00002841 SU->TopReadyCycle = std::max(SU->TopReadyCycle, Top.getCurrCycle());
Andrew Trickce27bb92012-06-29 03:23:22 +00002842 Top.bumpNode(SU);
Andrew Tricke833e1c2013-04-13 06:07:40 +00002843 if (SU->hasPhysRegUses)
2844 reschedulePhysRegCopies(SU, true);
Andrew Trick61f1a272012-05-24 22:11:09 +00002845 }
Andrew Trick45446062012-06-05 21:11:27 +00002846 else {
Andrew Trickfc127d12013-12-07 05:59:44 +00002847 SU->BotReadyCycle = std::max(SU->BotReadyCycle, Bot.getCurrCycle());
Andrew Trickce27bb92012-06-29 03:23:22 +00002848 Bot.bumpNode(SU);
Andrew Tricke833e1c2013-04-13 06:07:40 +00002849 if (SU->hasPhysRegDefs)
2850 reschedulePhysRegCopies(SU, false);
Andrew Trick61f1a272012-05-24 22:11:09 +00002851 }
2852}
2853
Andrew Trick8823dec2012-03-14 04:00:41 +00002854/// Create the standard converging machine scheduler. This will be used as the
2855/// default scheduler if the target does not set a default.
Andrew Trickd14d7c22013-12-28 21:56:57 +00002856static ScheduleDAGInstrs *createGenericSchedLive(MachineSchedContext *C) {
David Blaikie422b93d2014-04-21 20:32:32 +00002857 ScheduleDAGMILive *DAG = new ScheduleDAGMILive(C, make_unique<GenericScheduler>(C));
Andrew Tricka7714a02012-11-12 19:40:10 +00002858 // Register DAG post-processors.
Andrew Trick85a1d4c2013-04-24 15:54:43 +00002859 //
2860 // FIXME: extend the mutation API to allow earlier mutations to instantiate
2861 // data and pass it to later mutations. Have a single mutation that gathers
2862 // the interesting nodes in one pass.
David Blaikie422b93d2014-04-21 20:32:32 +00002863 DAG->addMutation(make_unique<CopyConstrain>(DAG->TII, DAG->TRI));
Andrew Tricka6e87772013-09-04 21:00:08 +00002864 if (EnableLoadCluster && DAG->TII->enableClusterLoads())
David Blaikie422b93d2014-04-21 20:32:32 +00002865 DAG->addMutation(make_unique<LoadClusterMutation>(DAG->TII, DAG->TRI));
Andrew Trick263280242012-11-12 19:52:20 +00002866 if (EnableMacroFusion)
David Blaikie422b93d2014-04-21 20:32:32 +00002867 DAG->addMutation(make_unique<MacroFusion>(DAG->TII));
Andrew Tricka7714a02012-11-12 19:40:10 +00002868 return DAG;
Andrew Tricke1c034f2012-01-17 06:55:03 +00002869}
Andrew Trickd14d7c22013-12-28 21:56:57 +00002870
Andrew Tricke1c034f2012-01-17 06:55:03 +00002871static MachineSchedRegistry
Andrew Trick665d3ec2013-09-19 23:10:59 +00002872GenericSchedRegistry("converge", "Standard converging scheduler.",
Andrew Trickd14d7c22013-12-28 21:56:57 +00002873 createGenericSchedLive);
2874
2875//===----------------------------------------------------------------------===//
2876// PostGenericScheduler - Generic PostRA implementation of MachineSchedStrategy.
2877//===----------------------------------------------------------------------===//
2878
Andrew Trick3ccf71d2014-06-04 07:06:18 +00002879void PostGenericScheduler::initialize(ScheduleDAGMI *Dag) {
2880 DAG = Dag;
2881 SchedModel = DAG->getSchedModel();
2882 TRI = DAG->TRI;
Andrew Trickd14d7c22013-12-28 21:56:57 +00002883
Andrew Trick3ccf71d2014-06-04 07:06:18 +00002884 Rem.init(DAG, SchedModel);
2885 Top.init(DAG, SchedModel, &Rem);
2886 BotRoots.clear();
Andrew Trickd14d7c22013-12-28 21:56:57 +00002887
Andrew Trick3ccf71d2014-06-04 07:06:18 +00002888 // Initialize the HazardRecognizers. If itineraries don't exist, are empty,
2889 // or are disabled, then these HazardRecs will be disabled.
2890 const InstrItineraryData *Itin = SchedModel->getInstrItineraries();
2891 const TargetMachine &TM = DAG->MF.getTarget();
2892 if (!Top.HazardRec) {
2893 Top.HazardRec =
Eric Christopherd9134482014-08-04 21:25:23 +00002894 TM.getSubtargetImpl()->getInstrInfo()->CreateTargetMIHazardRecognizer(
2895 Itin, DAG);
Andrew Trickd14d7c22013-12-28 21:56:57 +00002896 }
Andrew Trick3ccf71d2014-06-04 07:06:18 +00002897}
Andrew Trickd14d7c22013-12-28 21:56:57 +00002898
Andrew Trickd14d7c22013-12-28 21:56:57 +00002899
2900void PostGenericScheduler::registerRoots() {
2901 Rem.CriticalPath = DAG->ExitSU.getDepth();
2902
2903 // Some roots may not feed into ExitSU. Check all of them in case.
2904 for (SmallVectorImpl<SUnit*>::const_iterator
2905 I = BotRoots.begin(), E = BotRoots.end(); I != E; ++I) {
2906 if ((*I)->getDepth() > Rem.CriticalPath)
2907 Rem.CriticalPath = (*I)->getDepth();
2908 }
2909 DEBUG(dbgs() << "Critical Path: " << Rem.CriticalPath << '\n');
2910}
2911
2912/// Apply a set of heursitics to a new candidate for PostRA scheduling.
2913///
2914/// \param Cand provides the policy and current best candidate.
2915/// \param TryCand refers to the next SUnit candidate, otherwise uninitialized.
2916void PostGenericScheduler::tryCandidate(SchedCandidate &Cand,
2917 SchedCandidate &TryCand) {
2918
2919 // Initialize the candidate if needed.
2920 if (!Cand.isValid()) {
2921 TryCand.Reason = NodeOrder;
2922 return;
2923 }
2924
2925 // Prioritize instructions that read unbuffered resources by stall cycles.
2926 if (tryLess(Top.getLatencyStallCycles(TryCand.SU),
2927 Top.getLatencyStallCycles(Cand.SU), TryCand, Cand, Stall))
2928 return;
2929
2930 // Avoid critical resource consumption and balance the schedule.
2931 if (tryLess(TryCand.ResDelta.CritResources, Cand.ResDelta.CritResources,
2932 TryCand, Cand, ResourceReduce))
2933 return;
2934 if (tryGreater(TryCand.ResDelta.DemandedResources,
2935 Cand.ResDelta.DemandedResources,
2936 TryCand, Cand, ResourceDemand))
2937 return;
2938
2939 // Avoid serializing long latency dependence chains.
2940 if (Cand.Policy.ReduceLatency && tryLatency(TryCand, Cand, Top)) {
2941 return;
2942 }
2943
2944 // Fall through to original instruction order.
2945 if (TryCand.SU->NodeNum < Cand.SU->NodeNum)
2946 TryCand.Reason = NodeOrder;
2947}
2948
2949void PostGenericScheduler::pickNodeFromQueue(SchedCandidate &Cand) {
2950 ReadyQueue &Q = Top.Available;
2951
2952 DEBUG(Q.dump());
2953
2954 for (ReadyQueue::iterator I = Q.begin(), E = Q.end(); I != E; ++I) {
2955 SchedCandidate TryCand(Cand.Policy);
2956 TryCand.SU = *I;
2957 TryCand.initResourceDelta(DAG, SchedModel);
2958 tryCandidate(Cand, TryCand);
2959 if (TryCand.Reason != NoCand) {
2960 Cand.setBest(TryCand);
2961 DEBUG(traceCandidate(Cand));
2962 }
2963 }
2964}
2965
2966/// Pick the next node to schedule.
2967SUnit *PostGenericScheduler::pickNode(bool &IsTopNode) {
2968 if (DAG->top() == DAG->bottom()) {
2969 assert(Top.Available.empty() && Top.Pending.empty() && "ReadyQ garbage");
Craig Topperc0196b12014-04-14 00:51:57 +00002970 return nullptr;
Andrew Trickd14d7c22013-12-28 21:56:57 +00002971 }
2972 SUnit *SU;
2973 do {
2974 SU = Top.pickOnlyChoice();
2975 if (!SU) {
2976 CandPolicy NoPolicy;
2977 SchedCandidate TopCand(NoPolicy);
2978 // Set the top-down policy based on the state of the current top zone and
2979 // the instructions outside the zone, including the bottom zone.
Craig Topperc0196b12014-04-14 00:51:57 +00002980 setPolicy(TopCand.Policy, /*IsPostRA=*/true, Top, nullptr);
Andrew Trickd14d7c22013-12-28 21:56:57 +00002981 pickNodeFromQueue(TopCand);
2982 assert(TopCand.Reason != NoCand && "failed to find a candidate");
2983 tracePick(TopCand, true);
2984 SU = TopCand.SU;
2985 }
2986 } while (SU->isScheduled);
2987
2988 IsTopNode = true;
2989 Top.removeReady(SU);
2990
2991 DEBUG(dbgs() << "Scheduling SU(" << SU->NodeNum << ") " << *SU->getInstr());
2992 return SU;
2993}
2994
2995/// Called after ScheduleDAGMI has scheduled an instruction and updated
2996/// scheduled/remaining flags in the DAG nodes.
2997void PostGenericScheduler::schedNode(SUnit *SU, bool IsTopNode) {
2998 SU->TopReadyCycle = std::max(SU->TopReadyCycle, Top.getCurrCycle());
2999 Top.bumpNode(SU);
3000}
3001
3002/// Create a generic scheduler with no vreg liveness or DAG mutation passes.
3003static ScheduleDAGInstrs *createGenericSchedPostRA(MachineSchedContext *C) {
David Blaikie422b93d2014-04-21 20:32:32 +00003004 return new ScheduleDAGMI(C, make_unique<PostGenericScheduler>(C), /*IsPostRA=*/true);
Andrew Trickd14d7c22013-12-28 21:56:57 +00003005}
Andrew Tricke1c034f2012-01-17 06:55:03 +00003006
3007//===----------------------------------------------------------------------===//
Andrew Trick90f711d2012-10-15 18:02:27 +00003008// ILP Scheduler. Currently for experimental analysis of heuristics.
3009//===----------------------------------------------------------------------===//
3010
3011namespace {
3012/// \brief Order nodes by the ILP metric.
3013struct ILPOrder {
Andrew Trick44f750a2013-01-25 04:01:04 +00003014 const SchedDFSResult *DFSResult;
3015 const BitVector *ScheduledTrees;
Andrew Trick90f711d2012-10-15 18:02:27 +00003016 bool MaximizeILP;
3017
Craig Topperc0196b12014-04-14 00:51:57 +00003018 ILPOrder(bool MaxILP)
3019 : DFSResult(nullptr), ScheduledTrees(nullptr), MaximizeILP(MaxILP) {}
Andrew Trick90f711d2012-10-15 18:02:27 +00003020
3021 /// \brief Apply a less-than relation on node priority.
Andrew Trick48d392e2012-11-28 05:13:28 +00003022 ///
3023 /// (Return true if A comes after B in the Q.)
Andrew Trick90f711d2012-10-15 18:02:27 +00003024 bool operator()(const SUnit *A, const SUnit *B) const {
Andrew Trick48d392e2012-11-28 05:13:28 +00003025 unsigned SchedTreeA = DFSResult->getSubtreeID(A);
3026 unsigned SchedTreeB = DFSResult->getSubtreeID(B);
3027 if (SchedTreeA != SchedTreeB) {
3028 // Unscheduled trees have lower priority.
3029 if (ScheduledTrees->test(SchedTreeA) != ScheduledTrees->test(SchedTreeB))
3030 return ScheduledTrees->test(SchedTreeB);
3031
3032 // Trees with shallower connections have have lower priority.
3033 if (DFSResult->getSubtreeLevel(SchedTreeA)
3034 != DFSResult->getSubtreeLevel(SchedTreeB)) {
3035 return DFSResult->getSubtreeLevel(SchedTreeA)
3036 < DFSResult->getSubtreeLevel(SchedTreeB);
3037 }
3038 }
Andrew Trick90f711d2012-10-15 18:02:27 +00003039 if (MaximizeILP)
Andrew Trick48d392e2012-11-28 05:13:28 +00003040 return DFSResult->getILP(A) < DFSResult->getILP(B);
Andrew Trick90f711d2012-10-15 18:02:27 +00003041 else
Andrew Trick48d392e2012-11-28 05:13:28 +00003042 return DFSResult->getILP(A) > DFSResult->getILP(B);
Andrew Trick90f711d2012-10-15 18:02:27 +00003043 }
3044};
3045
3046/// \brief Schedule based on the ILP metric.
3047class ILPScheduler : public MachineSchedStrategy {
Andrew Trickd7f890e2013-12-28 21:56:47 +00003048 ScheduleDAGMILive *DAG;
Andrew Trick90f711d2012-10-15 18:02:27 +00003049 ILPOrder Cmp;
3050
3051 std::vector<SUnit*> ReadyQ;
3052public:
Craig Topperc0196b12014-04-14 00:51:57 +00003053 ILPScheduler(bool MaximizeILP): DAG(nullptr), Cmp(MaximizeILP) {}
Andrew Trick90f711d2012-10-15 18:02:27 +00003054
Craig Topper4584cd52014-03-07 09:26:03 +00003055 void initialize(ScheduleDAGMI *dag) override {
Andrew Trickd7f890e2013-12-28 21:56:47 +00003056 assert(dag->hasVRegLiveness() && "ILPScheduler needs vreg liveness");
3057 DAG = static_cast<ScheduleDAGMILive*>(dag);
Andrew Tricke2c3f5c2013-01-25 06:33:57 +00003058 DAG->computeDFSResult();
Andrew Trick44f750a2013-01-25 04:01:04 +00003059 Cmp.DFSResult = DAG->getDFSResult();
3060 Cmp.ScheduledTrees = &DAG->getScheduledTrees();
Andrew Trick90f711d2012-10-15 18:02:27 +00003061 ReadyQ.clear();
Andrew Trick90f711d2012-10-15 18:02:27 +00003062 }
3063
Craig Topper4584cd52014-03-07 09:26:03 +00003064 void registerRoots() override {
Benjamin Krameraa598b32012-11-29 14:36:26 +00003065 // Restore the heap in ReadyQ with the updated DFS results.
3066 std::make_heap(ReadyQ.begin(), ReadyQ.end(), Cmp);
Andrew Trick90f711d2012-10-15 18:02:27 +00003067 }
3068
3069 /// Implement MachineSchedStrategy interface.
3070 /// -----------------------------------------
3071
Andrew Trick48d392e2012-11-28 05:13:28 +00003072 /// Callback to select the highest priority node from the ready Q.
Craig Topper4584cd52014-03-07 09:26:03 +00003073 SUnit *pickNode(bool &IsTopNode) override {
Craig Topperc0196b12014-04-14 00:51:57 +00003074 if (ReadyQ.empty()) return nullptr;
Matt Arsenault4ab769f2013-03-21 00:57:21 +00003075 std::pop_heap(ReadyQ.begin(), ReadyQ.end(), Cmp);
Andrew Trick90f711d2012-10-15 18:02:27 +00003076 SUnit *SU = ReadyQ.back();
3077 ReadyQ.pop_back();
3078 IsTopNode = false;
Andrew Trick1f0bb692013-04-13 06:07:49 +00003079 DEBUG(dbgs() << "Pick node " << "SU(" << SU->NodeNum << ") "
Andrew Trick44f750a2013-01-25 04:01:04 +00003080 << " ILP: " << DAG->getDFSResult()->getILP(SU)
3081 << " Tree: " << DAG->getDFSResult()->getSubtreeID(SU) << " @"
3082 << DAG->getDFSResult()->getSubtreeLevel(
Andrew Trick1f0bb692013-04-13 06:07:49 +00003083 DAG->getDFSResult()->getSubtreeID(SU)) << '\n'
3084 << "Scheduling " << *SU->getInstr());
Andrew Trick90f711d2012-10-15 18:02:27 +00003085 return SU;
3086 }
3087
Andrew Trick44f750a2013-01-25 04:01:04 +00003088 /// \brief Scheduler callback to notify that a new subtree is scheduled.
Craig Topper4584cd52014-03-07 09:26:03 +00003089 void scheduleTree(unsigned SubtreeID) override {
Andrew Trick44f750a2013-01-25 04:01:04 +00003090 std::make_heap(ReadyQ.begin(), ReadyQ.end(), Cmp);
3091 }
3092
Andrew Trick48d392e2012-11-28 05:13:28 +00003093 /// Callback after a node is scheduled. Mark a newly scheduled tree, notify
3094 /// DFSResults, and resort the priority Q.
Craig Topper4584cd52014-03-07 09:26:03 +00003095 void schedNode(SUnit *SU, bool IsTopNode) override {
Andrew Trick48d392e2012-11-28 05:13:28 +00003096 assert(!IsTopNode && "SchedDFSResult needs bottom-up");
Andrew Trick48d392e2012-11-28 05:13:28 +00003097 }
Andrew Trick90f711d2012-10-15 18:02:27 +00003098
Craig Topper4584cd52014-03-07 09:26:03 +00003099 void releaseTopNode(SUnit *) override { /*only called for top roots*/ }
Andrew Trick90f711d2012-10-15 18:02:27 +00003100
Craig Topper4584cd52014-03-07 09:26:03 +00003101 void releaseBottomNode(SUnit *SU) override {
Andrew Trick90f711d2012-10-15 18:02:27 +00003102 ReadyQ.push_back(SU);
3103 std::push_heap(ReadyQ.begin(), ReadyQ.end(), Cmp);
3104 }
3105};
3106} // namespace
3107
3108static ScheduleDAGInstrs *createILPMaxScheduler(MachineSchedContext *C) {
David Blaikie422b93d2014-04-21 20:32:32 +00003109 return new ScheduleDAGMILive(C, make_unique<ILPScheduler>(true));
Andrew Trick90f711d2012-10-15 18:02:27 +00003110}
3111static ScheduleDAGInstrs *createILPMinScheduler(MachineSchedContext *C) {
David Blaikie422b93d2014-04-21 20:32:32 +00003112 return new ScheduleDAGMILive(C, make_unique<ILPScheduler>(false));
Andrew Trick90f711d2012-10-15 18:02:27 +00003113}
3114static MachineSchedRegistry ILPMaxRegistry(
3115 "ilpmax", "Schedule bottom-up for max ILP", createILPMaxScheduler);
3116static MachineSchedRegistry ILPMinRegistry(
3117 "ilpmin", "Schedule bottom-up for min ILP", createILPMinScheduler);
3118
3119//===----------------------------------------------------------------------===//
Andrew Trick63440872012-01-14 02:17:06 +00003120// Machine Instruction Shuffler for Correctness Testing
3121//===----------------------------------------------------------------------===//
3122
Andrew Tricke77e84e2012-01-13 06:30:30 +00003123#ifndef NDEBUG
3124namespace {
Andrew Trick8823dec2012-03-14 04:00:41 +00003125/// Apply a less-than relation on the node order, which corresponds to the
3126/// instruction order prior to scheduling. IsReverse implements greater-than.
3127template<bool IsReverse>
3128struct SUnitOrder {
Andrew Trick7ccdc5c2012-01-17 06:55:07 +00003129 bool operator()(SUnit *A, SUnit *B) const {
Andrew Trick8823dec2012-03-14 04:00:41 +00003130 if (IsReverse)
3131 return A->NodeNum > B->NodeNum;
3132 else
3133 return A->NodeNum < B->NodeNum;
Andrew Trick7ccdc5c2012-01-17 06:55:07 +00003134 }
3135};
3136
Andrew Tricke77e84e2012-01-13 06:30:30 +00003137/// Reorder instructions as much as possible.
Andrew Trick8823dec2012-03-14 04:00:41 +00003138class InstructionShuffler : public MachineSchedStrategy {
3139 bool IsAlternating;
3140 bool IsTopDown;
3141
3142 // Using a less-than relation (SUnitOrder<false>) for the TopQ priority
3143 // gives nodes with a higher number higher priority causing the latest
3144 // instructions to be scheduled first.
3145 PriorityQueue<SUnit*, std::vector<SUnit*>, SUnitOrder<false> >
3146 TopQ;
3147 // When scheduling bottom-up, use greater-than as the queue priority.
3148 PriorityQueue<SUnit*, std::vector<SUnit*>, SUnitOrder<true> >
3149 BottomQ;
Andrew Tricke77e84e2012-01-13 06:30:30 +00003150public:
Andrew Trick8823dec2012-03-14 04:00:41 +00003151 InstructionShuffler(bool alternate, bool topdown)
3152 : IsAlternating(alternate), IsTopDown(topdown) {}
Andrew Tricke77e84e2012-01-13 06:30:30 +00003153
Craig Topper9d74a5a2014-04-29 07:58:41 +00003154 void initialize(ScheduleDAGMI*) override {
Andrew Trick8823dec2012-03-14 04:00:41 +00003155 TopQ.clear();
3156 BottomQ.clear();
3157 }
Andrew Trick7ccdc5c2012-01-17 06:55:07 +00003158
Andrew Trick8823dec2012-03-14 04:00:41 +00003159 /// Implement MachineSchedStrategy interface.
3160 /// -----------------------------------------
3161
Craig Topper9d74a5a2014-04-29 07:58:41 +00003162 SUnit *pickNode(bool &IsTopNode) override {
Andrew Trick8823dec2012-03-14 04:00:41 +00003163 SUnit *SU;
3164 if (IsTopDown) {
3165 do {
Craig Topperc0196b12014-04-14 00:51:57 +00003166 if (TopQ.empty()) return nullptr;
Andrew Trick8823dec2012-03-14 04:00:41 +00003167 SU = TopQ.top();
3168 TopQ.pop();
3169 } while (SU->isScheduled);
3170 IsTopNode = true;
3171 }
3172 else {
3173 do {
Craig Topperc0196b12014-04-14 00:51:57 +00003174 if (BottomQ.empty()) return nullptr;
Andrew Trick8823dec2012-03-14 04:00:41 +00003175 SU = BottomQ.top();
3176 BottomQ.pop();
3177 } while (SU->isScheduled);
3178 IsTopNode = false;
3179 }
3180 if (IsAlternating)
3181 IsTopDown = !IsTopDown;
Andrew Trick7ccdc5c2012-01-17 06:55:07 +00003182 return SU;
3183 }
3184
Craig Topper9d74a5a2014-04-29 07:58:41 +00003185 void schedNode(SUnit *SU, bool IsTopNode) override {}
Andrew Trick61f1a272012-05-24 22:11:09 +00003186
Craig Topper9d74a5a2014-04-29 07:58:41 +00003187 void releaseTopNode(SUnit *SU) override {
Andrew Trick8823dec2012-03-14 04:00:41 +00003188 TopQ.push(SU);
3189 }
Craig Topper9d74a5a2014-04-29 07:58:41 +00003190 void releaseBottomNode(SUnit *SU) override {
Andrew Trick8823dec2012-03-14 04:00:41 +00003191 BottomQ.push(SU);
Andrew Tricke77e84e2012-01-13 06:30:30 +00003192 }
3193};
3194} // namespace
3195
Andrew Trick02a80da2012-03-08 01:41:12 +00003196static ScheduleDAGInstrs *createInstructionShuffler(MachineSchedContext *C) {
Andrew Trick8823dec2012-03-14 04:00:41 +00003197 bool Alternate = !ForceTopDown && !ForceBottomUp;
3198 bool TopDown = !ForceBottomUp;
Benjamin Kramer05e7a842012-03-14 11:26:37 +00003199 assert((TopDown || !ForceTopDown) &&
Andrew Trick8823dec2012-03-14 04:00:41 +00003200 "-misched-topdown incompatible with -misched-bottomup");
David Blaikie422b93d2014-04-21 20:32:32 +00003201 return new ScheduleDAGMILive(C, make_unique<InstructionShuffler>(Alternate, TopDown));
Andrew Tricke77e84e2012-01-13 06:30:30 +00003202}
Andrew Trick8823dec2012-03-14 04:00:41 +00003203static MachineSchedRegistry ShufflerRegistry(
3204 "shuffle", "Shuffle machine instructions alternating directions",
3205 createInstructionShuffler);
Andrew Tricke77e84e2012-01-13 06:30:30 +00003206#endif // !NDEBUG
Andrew Trickea9fd952013-01-25 07:45:29 +00003207
3208//===----------------------------------------------------------------------===//
Andrew Trickd7f890e2013-12-28 21:56:47 +00003209// GraphWriter support for ScheduleDAGMILive.
Andrew Trickea9fd952013-01-25 07:45:29 +00003210//===----------------------------------------------------------------------===//
3211
3212#ifndef NDEBUG
3213namespace llvm {
3214
3215template<> struct GraphTraits<
3216 ScheduleDAGMI*> : public GraphTraits<ScheduleDAG*> {};
3217
3218template<>
3219struct DOTGraphTraits<ScheduleDAGMI*> : public DefaultDOTGraphTraits {
3220
3221 DOTGraphTraits (bool isSimple=false) : DefaultDOTGraphTraits(isSimple) {}
3222
3223 static std::string getGraphName(const ScheduleDAG *G) {
3224 return G->MF.getName();
3225 }
3226
3227 static bool renderGraphFromBottomUp() {
3228 return true;
3229 }
3230
3231 static bool isNodeHidden(const SUnit *Node) {
Andrew Trick856ecd92013-09-04 21:00:18 +00003232 return (Node->Preds.size() > 10 || Node->Succs.size() > 10);
Andrew Trickea9fd952013-01-25 07:45:29 +00003233 }
3234
3235 static bool hasNodeAddressLabel(const SUnit *Node,
3236 const ScheduleDAG *Graph) {
3237 return false;
3238 }
3239
3240 /// If you want to override the dot attributes printed for a particular
3241 /// edge, override this method.
3242 static std::string getEdgeAttributes(const SUnit *Node,
3243 SUnitIterator EI,
3244 const ScheduleDAG *Graph) {
3245 if (EI.isArtificialDep())
3246 return "color=cyan,style=dashed";
3247 if (EI.isCtrlDep())
3248 return "color=blue,style=dashed";
3249 return "";
3250 }
3251
3252 static std::string getNodeLabel(const SUnit *SU, const ScheduleDAG *G) {
Alp Tokere69170a2014-06-26 22:52:05 +00003253 std::string Str;
3254 raw_string_ostream SS(Str);
Andrew Trickd7f890e2013-12-28 21:56:47 +00003255 const ScheduleDAGMI *DAG = static_cast<const ScheduleDAGMI*>(G);
3256 const SchedDFSResult *DFS = DAG->hasVRegLiveness() ?
Craig Topperc0196b12014-04-14 00:51:57 +00003257 static_cast<const ScheduleDAGMILive*>(G)->getDFSResult() : nullptr;
Andrew Trick7609b7d2013-09-06 17:32:42 +00003258 SS << "SU:" << SU->NodeNum;
3259 if (DFS)
3260 SS << " I:" << DFS->getNumInstrs(SU);
Andrew Trickea9fd952013-01-25 07:45:29 +00003261 return SS.str();
3262 }
3263 static std::string getNodeDescription(const SUnit *SU, const ScheduleDAG *G) {
3264 return G->getGraphNodeLabel(SU);
3265 }
3266
Andrew Trickd7f890e2013-12-28 21:56:47 +00003267 static std::string getNodeAttributes(const SUnit *N, const ScheduleDAG *G) {
Andrew Trickea9fd952013-01-25 07:45:29 +00003268 std::string Str("shape=Mrecord");
Andrew Trickd7f890e2013-12-28 21:56:47 +00003269 const ScheduleDAGMI *DAG = static_cast<const ScheduleDAGMI*>(G);
3270 const SchedDFSResult *DFS = DAG->hasVRegLiveness() ?
Craig Topperc0196b12014-04-14 00:51:57 +00003271 static_cast<const ScheduleDAGMILive*>(G)->getDFSResult() : nullptr;
Andrew Trickea9fd952013-01-25 07:45:29 +00003272 if (DFS) {
3273 Str += ",style=filled,fillcolor=\"#";
3274 Str += DOT::getColorString(DFS->getSubtreeID(N));
3275 Str += '"';
3276 }
3277 return Str;
3278 }
3279};
3280} // namespace llvm
3281#endif // NDEBUG
3282
3283/// viewGraph - Pop up a ghostview window with the reachable parts of the DAG
3284/// rendered using 'dot'.
3285///
3286void ScheduleDAGMI::viewGraph(const Twine &Name, const Twine &Title) {
3287#ifndef NDEBUG
3288 ViewGraph(this, Name, false, Title);
3289#else
3290 errs() << "ScheduleDAGMI::viewGraph is only available in debug builds on "
3291 << "systems with Graphviz or gv!\n";
3292#endif // NDEBUG
3293}
3294
3295/// Out-of-line implementation with no arguments is handy for gdb.
3296void ScheduleDAGMI::viewGraph() {
3297 viewGraph(getDAGName(), "Scheduling-Units Graph for " + getDAGName());
3298}