blob: c0a4f65d8862a98beb2d3ce19fd5804a1d4c6563 [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
Chandler Carruth6bda14b2017-06-06 11:49:48 +000015#include "llvm/CodeGen/MachineScheduler.h"
Eugene Zelenkodb56e5a2017-02-22 22:32:51 +000016#include "llvm/ADT/ArrayRef.h"
17#include "llvm/ADT/BitVector.h"
18#include "llvm/ADT/DenseMap.h"
Chandler Carruthed0881b2012-12-03 16:50:05 +000019#include "llvm/ADT/PriorityQueue.h"
Eugene Zelenkodb56e5a2017-02-22 22:32:51 +000020#include "llvm/ADT/STLExtras.h"
Chandler Carruth6bda14b2017-06-06 11:49:48 +000021#include "llvm/ADT/SmallVector.h"
22#include "llvm/ADT/iterator_range.h"
Chandler Carruthed0881b2012-12-03 16:50:05 +000023#include "llvm/Analysis/AliasAnalysis.h"
Eugene Zelenkodb56e5a2017-02-22 22:32:51 +000024#include "llvm/CodeGen/LiveInterval.h"
Matthias Braunf8422972017-12-13 02:51:04 +000025#include "llvm/CodeGen/LiveIntervals.h"
Eugene Zelenkodb56e5a2017-02-22 22:32:51 +000026#include "llvm/CodeGen/MachineBasicBlock.h"
Jakub Staszakdf17ddd2013-03-10 13:11:23 +000027#include "llvm/CodeGen/MachineDominators.h"
Eugene Zelenkodb56e5a2017-02-22 22:32:51 +000028#include "llvm/CodeGen/MachineFunction.h"
29#include "llvm/CodeGen/MachineFunctionPass.h"
30#include "llvm/CodeGen/MachineInstr.h"
Jakub Staszakdf17ddd2013-03-10 13:11:23 +000031#include "llvm/CodeGen/MachineLoopInfo.h"
Eugene Zelenkodb56e5a2017-02-22 22:32:51 +000032#include "llvm/CodeGen/MachineOperand.h"
33#include "llvm/CodeGen/MachinePassRegistry.h"
Andrew Trick736dd9a2013-06-21 18:32:58 +000034#include "llvm/CodeGen/MachineRegisterInfo.h"
Eugene Zelenkodb56e5a2017-02-22 22:32:51 +000035#include "llvm/CodeGen/MachineValueType.h"
Andrew Tricke77e84e2012-01-13 06:30:30 +000036#include "llvm/CodeGen/Passes.h"
Andrew Trick05ff4662012-06-06 20:29:31 +000037#include "llvm/CodeGen/RegisterClassInfo.h"
Chandler Carruth6bda14b2017-06-06 11:49:48 +000038#include "llvm/CodeGen/RegisterPressure.h"
Eugene Zelenkodb56e5a2017-02-22 22:32:51 +000039#include "llvm/CodeGen/ScheduleDAG.h"
40#include "llvm/CodeGen/ScheduleDAGInstrs.h"
41#include "llvm/CodeGen/ScheduleDAGMutation.h"
Andrew Trickcd1c2f92012-11-28 05:13:24 +000042#include "llvm/CodeGen/ScheduleDFS.h"
Andrew Trick61f1a272012-05-24 22:11:09 +000043#include "llvm/CodeGen/ScheduleHazardRecognizer.h"
Eugene Zelenkodb56e5a2017-02-22 22:32:51 +000044#include "llvm/CodeGen/SlotIndexes.h"
David Blaikie3f833ed2017-11-08 01:01:31 +000045#include "llvm/CodeGen/TargetInstrInfo.h"
David Blaikieb3bde2e2017-11-17 01:07:10 +000046#include "llvm/CodeGen/TargetLowering.h"
Matthias Braun31d19d42016-05-10 03:21:59 +000047#include "llvm/CodeGen/TargetPassConfig.h"
David Blaikieb3bde2e2017-11-17 01:07:10 +000048#include "llvm/CodeGen/TargetRegisterInfo.h"
Eugene Zelenkodb56e5a2017-02-22 22:32:51 +000049#include "llvm/CodeGen/TargetSchedule.h"
David Blaikieb3bde2e2017-11-17 01:07:10 +000050#include "llvm/CodeGen/TargetSubtargetInfo.h"
Eugene Zelenkodb56e5a2017-02-22 22:32:51 +000051#include "llvm/MC/LaneBitmask.h"
52#include "llvm/Pass.h"
Andrew Tricke77e84e2012-01-13 06:30:30 +000053#include "llvm/Support/CommandLine.h"
Eugene Zelenkodb56e5a2017-02-22 22:32:51 +000054#include "llvm/Support/Compiler.h"
Andrew Tricke77e84e2012-01-13 06:30:30 +000055#include "llvm/Support/Debug.h"
56#include "llvm/Support/ErrorHandling.h"
Andrew Trickea9fd952013-01-25 07:45:29 +000057#include "llvm/Support/GraphWriter.h"
Andrew Tricke77e84e2012-01-13 06:30:30 +000058#include "llvm/Support/raw_ostream.h"
Eugene Zelenkodb56e5a2017-02-22 22:32:51 +000059#include <algorithm>
60#include <cassert>
61#include <cstdint>
62#include <iterator>
63#include <limits>
64#include <memory>
65#include <string>
66#include <tuple>
67#include <utility>
68#include <vector>
Andrew Trick7ccdc5c2012-01-17 06:55:07 +000069
Andrew Tricke77e84e2012-01-13 06:30:30 +000070using namespace llvm;
71
Matthias Braun1527baa2017-05-25 21:26:32 +000072#define DEBUG_TYPE "machine-scheduler"
Chandler Carruth1b9dde02014-04-22 02:02:50 +000073
Andrew Trick7a8e1002012-09-11 00:39:15 +000074namespace llvm {
Eugene Zelenkodb56e5a2017-02-22 22:32:51 +000075
Andrew Trick7a8e1002012-09-11 00:39:15 +000076cl::opt<bool> ForceTopDown("misched-topdown", cl::Hidden,
77 cl::desc("Force top-down list scheduling"));
78cl::opt<bool> ForceBottomUp("misched-bottomup", cl::Hidden,
79 cl::desc("Force bottom-up list scheduling"));
Gerolf Hoflehnerb5220dc2014-08-07 21:49:44 +000080cl::opt<bool>
81DumpCriticalPathLength("misched-dcpl", cl::Hidden,
82 cl::desc("Print critical path length to stdout"));
Eugene Zelenkodb56e5a2017-02-22 22:32:51 +000083
84} // end namespace llvm
Andrew Trick8823dec2012-03-14 04:00:41 +000085
Andrew Tricka5f19562012-03-07 00:18:25 +000086#ifndef NDEBUG
87static cl::opt<bool> ViewMISchedDAGs("view-misched-dags", cl::Hidden,
88 cl::desc("Pop up a window to show MISched dags after they are processed"));
Lang Hamesdd98c492012-03-19 18:38:38 +000089
Matthias Braund78ee542015-09-17 21:09:59 +000090/// In some situations a few uninteresting nodes depend on nearly all other
91/// nodes in the graph, provide a cutoff to hide them.
92static cl::opt<unsigned> ViewMISchedCutoff("view-misched-cutoff", cl::Hidden,
93 cl::desc("Hide nodes with more predecessor/successor than cutoff"));
94
Lang Hamesdd98c492012-03-19 18:38:38 +000095static cl::opt<unsigned> MISchedCutoff("misched-cutoff", cl::Hidden,
96 cl::desc("Stop scheduling after N instructions"), cl::init(~0U));
Andrew Trick33e05d72013-12-28 21:57:02 +000097
98static cl::opt<std::string> SchedOnlyFunc("misched-only-func", cl::Hidden,
99 cl::desc("Only schedule this function"));
100static cl::opt<unsigned> SchedOnlyBlock("misched-only-block", cl::Hidden,
Francis Visoiu Mistrih25528d62017-12-04 17:18:51 +0000101 cl::desc("Only schedule this MBB#"));
Andrew Tricka5f19562012-03-07 00:18:25 +0000102#else
103static bool ViewMISchedDAGs = false;
104#endif // NDEBUG
105
Matthias Braun6493bc22016-04-22 19:09:17 +0000106/// Avoid quadratic complexity in unusually large basic blocks by limiting the
107/// size of the ready lists.
108static cl::opt<unsigned> ReadyListLimit("misched-limit", cl::Hidden,
109 cl::desc("Limit ready list to N instructions"), cl::init(256));
110
Andrew Trickb6e74712013-09-04 20:59:59 +0000111static cl::opt<bool> EnableRegPressure("misched-regpressure", cl::Hidden,
112 cl::desc("Enable register pressure scheduling."), cl::init(true));
113
Andrew Trickc01b0042013-08-23 17:48:43 +0000114static cl::opt<bool> EnableCyclicPath("misched-cyclicpath", cl::Hidden,
Andrew Trick6c88b352013-09-09 23:31:14 +0000115 cl::desc("Enable cyclic critical path analysis."), cl::init(true));
Andrew Trickc01b0042013-08-23 17:48:43 +0000116
Jun Bum Lim4c5bd582016-04-15 14:58:38 +0000117static cl::opt<bool> EnableMemOpCluster("misched-cluster", cl::Hidden,
118 cl::desc("Enable memop clustering."),
119 cl::init(true));
Andrew Tricka7714a02012-11-12 19:40:10 +0000120
Andrew Trick48f2a722013-03-08 05:40:34 +0000121static cl::opt<bool> VerifyScheduling("verify-misched", cl::Hidden,
122 cl::desc("Verify machine instrs before and after machine scheduling"));
123
Andrew Trick44f750a2013-01-25 04:01:04 +0000124// DAG subtrees must have at least this many nodes.
125static const unsigned MinSubtreeSize = 8;
126
Juergen Ributzkad12ccbd2013-11-19 00:57:56 +0000127// Pin the vtables to this file.
128void MachineSchedStrategy::anchor() {}
Eugene Zelenkodb56e5a2017-02-22 22:32:51 +0000129
Juergen Ributzkad12ccbd2013-11-19 00:57:56 +0000130void ScheduleDAGMutation::anchor() {}
131
Andrew Trick63440872012-01-14 02:17:06 +0000132//===----------------------------------------------------------------------===//
133// Machine Instruction Scheduling Pass and Registry
134//===----------------------------------------------------------------------===//
135
Eugene Zelenkodb56e5a2017-02-22 22:32:51 +0000136MachineSchedContext::MachineSchedContext() {
Andrew Trick4d4b5462012-04-24 20:36:19 +0000137 RegClassInfo = new RegisterClassInfo();
138}
139
140MachineSchedContext::~MachineSchedContext() {
141 delete RegClassInfo;
142}
143
Andrew Tricke77e84e2012-01-13 06:30:30 +0000144namespace {
Eugene Zelenkodb56e5a2017-02-22 22:32:51 +0000145
Andrew Trickd7f890e2013-12-28 21:56:47 +0000146/// Base class for a machine scheduler class that can run at any point.
147class MachineSchedulerBase : public MachineSchedContext,
148 public MachineFunctionPass {
149public:
150 MachineSchedulerBase(char &ID): MachineFunctionPass(ID) {}
151
Craig Topperc0196b12014-04-14 00:51:57 +0000152 void print(raw_ostream &O, const Module* = nullptr) const override;
Andrew Trickd7f890e2013-12-28 21:56:47 +0000153
154protected:
Matthias Braun93563e72015-11-03 01:53:29 +0000155 void scheduleRegions(ScheduleDAGInstrs &Scheduler, bool FixKillFlags);
Andrew Trickd7f890e2013-12-28 21:56:47 +0000156};
157
Andrew Tricke1c034f2012-01-17 06:55:03 +0000158/// MachineScheduler runs after coalescing and before register allocation.
Andrew Trickd7f890e2013-12-28 21:56:47 +0000159class MachineScheduler : public MachineSchedulerBase {
Andrew Tricke77e84e2012-01-13 06:30:30 +0000160public:
Andrew Tricke1c034f2012-01-17 06:55:03 +0000161 MachineScheduler();
Andrew Tricke77e84e2012-01-13 06:30:30 +0000162
Craig Topper4584cd52014-03-07 09:26:03 +0000163 void getAnalysisUsage(AnalysisUsage &AU) const override;
Andrew Tricke77e84e2012-01-13 06:30:30 +0000164
Craig Topper4584cd52014-03-07 09:26:03 +0000165 bool runOnMachineFunction(MachineFunction&) override;
Andrew Tricke77e84e2012-01-13 06:30:30 +0000166
Andrew Tricke77e84e2012-01-13 06:30:30 +0000167 static char ID; // Class identification, replacement for typeinfo
Andrew Trick978674b2013-09-20 05:14:41 +0000168
169protected:
170 ScheduleDAGInstrs *createMachineScheduler();
Andrew Tricke77e84e2012-01-13 06:30:30 +0000171};
Andrew Trick17080b92013-12-28 21:56:51 +0000172
173/// PostMachineScheduler runs after shortly before code emission.
174class PostMachineScheduler : public MachineSchedulerBase {
175public:
176 PostMachineScheduler();
177
Craig Topper4584cd52014-03-07 09:26:03 +0000178 void getAnalysisUsage(AnalysisUsage &AU) const override;
Andrew Trick17080b92013-12-28 21:56:51 +0000179
Craig Topper4584cd52014-03-07 09:26:03 +0000180 bool runOnMachineFunction(MachineFunction&) override;
Andrew Trick17080b92013-12-28 21:56:51 +0000181
182 static char ID; // Class identification, replacement for typeinfo
183
184protected:
185 ScheduleDAGInstrs *createPostMachineScheduler();
186};
Eugene Zelenkodb56e5a2017-02-22 22:32:51 +0000187
188} // end anonymous namespace
Andrew Tricke77e84e2012-01-13 06:30:30 +0000189
Andrew Tricke1c034f2012-01-17 06:55:03 +0000190char MachineScheduler::ID = 0;
Andrew Tricke77e84e2012-01-13 06:30:30 +0000191
Andrew Tricke1c034f2012-01-17 06:55:03 +0000192char &llvm::MachineSchedulerID = MachineScheduler::ID;
Andrew Tricke77e84e2012-01-13 06:30:30 +0000193
Matthias Braun1527baa2017-05-25 21:26:32 +0000194INITIALIZE_PASS_BEGIN(MachineScheduler, DEBUG_TYPE,
Andrew Tricke77e84e2012-01-13 06:30:30 +0000195 "Machine Instruction Scheduler", false, false)
Chandler Carruth7b560d42015-09-09 17:55:00 +0000196INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
Davide Italiano6a1209e2017-03-24 20:52:56 +0000197INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)
Andrew Tricke77e84e2012-01-13 06:30:30 +0000198INITIALIZE_PASS_DEPENDENCY(SlotIndexes)
199INITIALIZE_PASS_DEPENDENCY(LiveIntervals)
Matthias Braun1527baa2017-05-25 21:26:32 +0000200INITIALIZE_PASS_END(MachineScheduler, DEBUG_TYPE,
Andrew Tricke77e84e2012-01-13 06:30:30 +0000201 "Machine Instruction Scheduler", false, false)
202
Eugene Zelenko32a40562017-09-11 23:00:48 +0000203MachineScheduler::MachineScheduler() : MachineSchedulerBase(ID) {
Andrew Tricke1c034f2012-01-17 06:55:03 +0000204 initializeMachineSchedulerPass(*PassRegistry::getPassRegistry());
Andrew Tricke77e84e2012-01-13 06:30:30 +0000205}
206
Andrew Tricke1c034f2012-01-17 06:55:03 +0000207void MachineScheduler::getAnalysisUsage(AnalysisUsage &AU) const {
Andrew Tricke77e84e2012-01-13 06:30:30 +0000208 AU.setPreservesCFG();
209 AU.addRequiredID(MachineDominatorsID);
210 AU.addRequired<MachineLoopInfo>();
Chandler Carruth7b560d42015-09-09 17:55:00 +0000211 AU.addRequired<AAResultsWrapperPass>();
Andrew Trick45300682012-03-09 00:52:20 +0000212 AU.addRequired<TargetPassConfig>();
Andrew Tricke77e84e2012-01-13 06:30:30 +0000213 AU.addRequired<SlotIndexes>();
214 AU.addPreserved<SlotIndexes>();
215 AU.addRequired<LiveIntervals>();
216 AU.addPreserved<LiveIntervals>();
Andrew Tricke77e84e2012-01-13 06:30:30 +0000217 MachineFunctionPass::getAnalysisUsage(AU);
218}
219
Andrew Trick17080b92013-12-28 21:56:51 +0000220char PostMachineScheduler::ID = 0;
221
222char &llvm::PostMachineSchedulerID = PostMachineScheduler::ID;
223
224INITIALIZE_PASS(PostMachineScheduler, "postmisched",
Saleem Abdulrasool7230b372013-12-28 22:47:55 +0000225 "PostRA Machine Instruction Scheduler", false, false)
Andrew Trick17080b92013-12-28 21:56:51 +0000226
Eugene Zelenko32a40562017-09-11 23:00:48 +0000227PostMachineScheduler::PostMachineScheduler() : MachineSchedulerBase(ID) {
Andrew Trick17080b92013-12-28 21:56:51 +0000228 initializePostMachineSchedulerPass(*PassRegistry::getPassRegistry());
229}
230
231void PostMachineScheduler::getAnalysisUsage(AnalysisUsage &AU) const {
232 AU.setPreservesCFG();
233 AU.addRequiredID(MachineDominatorsID);
234 AU.addRequired<MachineLoopInfo>();
235 AU.addRequired<TargetPassConfig>();
236 MachineFunctionPass::getAnalysisUsage(AU);
237}
238
Andrew Tricke77e84e2012-01-13 06:30:30 +0000239MachinePassRegistry MachineSchedRegistry::Registry;
240
Andrew Trick45300682012-03-09 00:52:20 +0000241/// A dummy default scheduler factory indicates whether the scheduler
242/// is overridden on the command line.
243static ScheduleDAGInstrs *useDefaultMachineSched(MachineSchedContext *C) {
Craig Topperc0196b12014-04-14 00:51:57 +0000244 return nullptr;
Andrew Trick45300682012-03-09 00:52:20 +0000245}
Andrew Tricke77e84e2012-01-13 06:30:30 +0000246
247/// MachineSchedOpt allows command line selection of the scheduler.
248static cl::opt<MachineSchedRegistry::ScheduleDAGCtor, false,
Eugene Zelenkodb56e5a2017-02-22 22:32:51 +0000249 RegisterPassParser<MachineSchedRegistry>>
Andrew Tricke77e84e2012-01-13 06:30:30 +0000250MachineSchedOpt("misched",
Andrew Trick45300682012-03-09 00:52:20 +0000251 cl::init(&useDefaultMachineSched), cl::Hidden,
Andrew Tricke77e84e2012-01-13 06:30:30 +0000252 cl::desc("Machine instruction scheduler to use"));
253
Andrew Trick45300682012-03-09 00:52:20 +0000254static MachineSchedRegistry
Andrew Trick8823dec2012-03-14 04:00:41 +0000255DefaultSchedRegistry("default", "Use the target's default scheduler choice.",
Andrew Trick45300682012-03-09 00:52:20 +0000256 useDefaultMachineSched);
257
Eric Christopher5f141b02015-03-11 22:56:10 +0000258static cl::opt<bool> EnableMachineSched(
259 "enable-misched",
260 cl::desc("Enable the machine instruction scheduling pass."), cl::init(true),
261 cl::Hidden);
262
Chad Rosier816a1ab2016-01-20 23:08:32 +0000263static cl::opt<bool> EnablePostRAMachineSched(
264 "enable-post-misched",
265 cl::desc("Enable the post-ra machine instruction scheduling pass."),
266 cl::init(true), cl::Hidden);
267
Andrew Trickcc45a282012-04-24 18:04:34 +0000268/// Decrement this iterator until reaching the top or a non-debug instr.
Andrew Trick2bc74c22013-08-30 04:36:57 +0000269static MachineBasicBlock::const_iterator
270priorNonDebug(MachineBasicBlock::const_iterator I,
271 MachineBasicBlock::const_iterator Beg) {
Andrew Trickcc45a282012-04-24 18:04:34 +0000272 assert(I != Beg && "reached the top of the region, cannot decrement");
273 while (--I != Beg) {
274 if (!I->isDebugValue())
275 break;
276 }
277 return I;
278}
279
Andrew Trick2bc74c22013-08-30 04:36:57 +0000280/// Non-const version.
281static MachineBasicBlock::iterator
282priorNonDebug(MachineBasicBlock::iterator I,
283 MachineBasicBlock::const_iterator Beg) {
Duncan P. N. Exon Smithdcbce9c2016-08-16 23:34:07 +0000284 return priorNonDebug(MachineBasicBlock::const_iterator(I), Beg)
285 .getNonConstIterator();
Andrew Trick2bc74c22013-08-30 04:36:57 +0000286}
287
Andrew Trickcc45a282012-04-24 18:04:34 +0000288/// If this iterator is a debug value, increment until reaching the End or a
289/// non-debug instruction.
Andrew Trick2c4f8b72013-08-31 05:17:58 +0000290static MachineBasicBlock::const_iterator
291nextIfDebug(MachineBasicBlock::const_iterator I,
292 MachineBasicBlock::const_iterator End) {
Andrew Trick463b2f12012-05-17 18:35:03 +0000293 for(; I != End; ++I) {
Andrew Trickcc45a282012-04-24 18:04:34 +0000294 if (!I->isDebugValue())
295 break;
296 }
297 return I;
298}
299
Andrew Trick2c4f8b72013-08-31 05:17:58 +0000300/// Non-const version.
301static MachineBasicBlock::iterator
302nextIfDebug(MachineBasicBlock::iterator I,
303 MachineBasicBlock::const_iterator End) {
Duncan P. N. Exon Smithdcbce9c2016-08-16 23:34:07 +0000304 return nextIfDebug(MachineBasicBlock::const_iterator(I), End)
305 .getNonConstIterator();
Andrew Trick2c4f8b72013-08-31 05:17:58 +0000306}
307
Andrew Trickdc4c1ad2013-09-24 17:11:19 +0000308/// Instantiate a ScheduleDAGInstrs that will be owned by the caller.
Andrew Trick978674b2013-09-20 05:14:41 +0000309ScheduleDAGInstrs *MachineScheduler::createMachineScheduler() {
310 // Select the scheduler, or set the default.
311 MachineSchedRegistry::ScheduleDAGCtor Ctor = MachineSchedOpt;
312 if (Ctor != useDefaultMachineSched)
313 return Ctor(this);
314
315 // Get the default scheduler set by the target for this function.
316 ScheduleDAGInstrs *Scheduler = PassConfig->createMachineScheduler(this);
317 if (Scheduler)
318 return Scheduler;
319
320 // Default to GenericScheduler.
Andrew Trickd14d7c22013-12-28 21:56:57 +0000321 return createGenericSchedLive(this);
Andrew Trick978674b2013-09-20 05:14:41 +0000322}
323
Andrew Trick17080b92013-12-28 21:56:51 +0000324/// Instantiate a ScheduleDAGInstrs for PostRA scheduling that will be owned by
325/// the caller. We don't have a command line option to override the postRA
326/// scheduler. The Target must configure it.
327ScheduleDAGInstrs *PostMachineScheduler::createPostMachineScheduler() {
328 // Get the postRA scheduler set by the target for this function.
329 ScheduleDAGInstrs *Scheduler = PassConfig->createPostMachineScheduler(this);
330 if (Scheduler)
331 return Scheduler;
332
333 // Default to GenericScheduler.
Andrew Trickd14d7c22013-12-28 21:56:57 +0000334 return createGenericSchedPostRA(this);
Andrew Trick17080b92013-12-28 21:56:51 +0000335}
336
Andrew Trick72515be2012-03-14 04:00:38 +0000337/// Top-level MachineScheduler pass driver.
338///
339/// Visit blocks in function order. Divide each block into scheduling regions
Andrew Trick8823dec2012-03-14 04:00:41 +0000340/// and visit them bottom-up. Visiting regions bottom-up is not required, but is
341/// consistent with the DAG builder, which traverses the interior of the
342/// scheduling regions bottom-up.
Andrew Trick72515be2012-03-14 04:00:38 +0000343///
344/// This design avoids exposing scheduling boundaries to the DAG builder,
Andrew Trick8823dec2012-03-14 04:00:41 +0000345/// simplifying the DAG builder's support for "special" target instructions.
346/// At the same time the design allows target schedulers to operate across
Andrew Trick72515be2012-03-14 04:00:38 +0000347/// scheduling boundaries, for example to bundle the boudary instructions
348/// without reordering them. This creates complexity, because the target
349/// scheduler must update the RegionBegin and RegionEnd positions cached by
350/// ScheduleDAGInstrs whenever adding or removing instructions. A much simpler
351/// design would be to split blocks at scheduling boundaries, but LLVM has a
352/// general bias against block splitting purely for implementation simplicity.
Andrew Tricke1c034f2012-01-17 06:55:03 +0000353bool MachineScheduler::runOnMachineFunction(MachineFunction &mf) {
Matthias Braunf1caa282017-12-15 22:22:58 +0000354 if (skipFunction(mf.getFunction()))
Chad Rosier6338d7c2016-01-20 22:38:25 +0000355 return false;
356
Eric Christopher5f141b02015-03-11 22:56:10 +0000357 if (EnableMachineSched.getNumOccurrences()) {
358 if (!EnableMachineSched)
359 return false;
360 } else if (!mf.getSubtarget().enableMachineScheduler())
361 return false;
362
Matthias Braundc7580a2015-10-29 03:57:28 +0000363 DEBUG(dbgs() << "Before MISched:\n"; mf.print(dbgs()));
Andrew Trickc5d70082012-05-10 21:06:21 +0000364
Andrew Tricke77e84e2012-01-13 06:30:30 +0000365 // Initialize the context of the pass.
366 MF = &mf;
367 MLI = &getAnalysis<MachineLoopInfo>();
368 MDT = &getAnalysis<MachineDominatorTree>();
Andrew Trick45300682012-03-09 00:52:20 +0000369 PassConfig = &getAnalysis<TargetPassConfig>();
Chandler Carruth7b560d42015-09-09 17:55:00 +0000370 AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
Andrew Trick02a80da2012-03-08 01:41:12 +0000371
Lang Hamesad33d5a2012-01-27 22:36:19 +0000372 LIS = &getAnalysis<LiveIntervals>();
Andrew Tricke77e84e2012-01-13 06:30:30 +0000373
Andrew Trick48f2a722013-03-08 05:40:34 +0000374 if (VerifyScheduling) {
Andrew Trick97064962013-07-25 07:26:26 +0000375 DEBUG(LIS->dump());
Andrew Trick48f2a722013-03-08 05:40:34 +0000376 MF->verify(this, "Before machine scheduling.");
377 }
Andrew Trick4d4b5462012-04-24 20:36:19 +0000378 RegClassInfo->runOnMachineFunction(*MF);
Andrew Trick88639922012-04-24 17:56:43 +0000379
Andrew Trick978674b2013-09-20 05:14:41 +0000380 // Instantiate the selected scheduler for this target, function, and
381 // optimization level.
Ahmed Charles56440fd2014-03-06 05:51:42 +0000382 std::unique_ptr<ScheduleDAGInstrs> Scheduler(createMachineScheduler());
Matthias Braun93563e72015-11-03 01:53:29 +0000383 scheduleRegions(*Scheduler, false);
Andrew Trickd7f890e2013-12-28 21:56:47 +0000384
385 DEBUG(LIS->dump());
386 if (VerifyScheduling)
387 MF->verify(this, "After machine scheduling.");
388 return true;
389}
390
Andrew Trick17080b92013-12-28 21:56:51 +0000391bool PostMachineScheduler::runOnMachineFunction(MachineFunction &mf) {
Matthias Braunf1caa282017-12-15 22:22:58 +0000392 if (skipFunction(mf.getFunction()))
Paul Robinson7c99ec52014-03-31 17:43:35 +0000393 return false;
394
Chad Rosier816a1ab2016-01-20 23:08:32 +0000395 if (EnablePostRAMachineSched.getNumOccurrences()) {
396 if (!EnablePostRAMachineSched)
397 return false;
398 } else if (!mf.getSubtarget().enablePostRAScheduler()) {
Andrew Trick8d2ee372014-06-04 07:06:27 +0000399 DEBUG(dbgs() << "Subtarget disables post-MI-sched.\n");
400 return false;
401 }
Andrew Trick17080b92013-12-28 21:56:51 +0000402 DEBUG(dbgs() << "Before post-MI-sched:\n"; mf.print(dbgs()));
403
404 // Initialize the context of the pass.
405 MF = &mf;
Jonas Paulsson57a705d2017-08-17 08:33:44 +0000406 MLI = &getAnalysis<MachineLoopInfo>();
Andrew Trick17080b92013-12-28 21:56:51 +0000407 PassConfig = &getAnalysis<TargetPassConfig>();
408
409 if (VerifyScheduling)
410 MF->verify(this, "Before post machine scheduling.");
411
412 // Instantiate the selected scheduler for this target, function, and
413 // optimization level.
Ahmed Charles56440fd2014-03-06 05:51:42 +0000414 std::unique_ptr<ScheduleDAGInstrs> Scheduler(createPostMachineScheduler());
Matthias Braun93563e72015-11-03 01:53:29 +0000415 scheduleRegions(*Scheduler, true);
Andrew Trick17080b92013-12-28 21:56:51 +0000416
417 if (VerifyScheduling)
418 MF->verify(this, "After post machine scheduling.");
419 return true;
420}
421
Andrew Trickd14d7c22013-12-28 21:56:57 +0000422/// Return true of the given instruction should not be included in a scheduling
423/// region.
424///
425/// MachineScheduler does not currently support scheduling across calls. To
426/// handle calls, the DAG builder needs to be modified to create register
427/// anti/output dependencies on the registers clobbered by the call's regmask
428/// operand. In PreRA scheduling, the stack pointer adjustment already prevents
429/// scheduling across calls. In PostRA scheduling, we need the isCall to enforce
430/// the boundary, but there would be no benefit to postRA scheduling across
431/// calls this late anyway.
432static bool isSchedBoundary(MachineBasicBlock::iterator MI,
433 MachineBasicBlock *MBB,
434 MachineFunction *MF,
Matthias Braun93563e72015-11-03 01:53:29 +0000435 const TargetInstrInfo *TII) {
Duncan P. N. Exon Smith9cfc75c2016-06-30 00:01:54 +0000436 return MI->isCall() || TII->isSchedulingBoundary(*MI, MBB, *MF);
Andrew Trickd14d7c22013-12-28 21:56:57 +0000437}
438
Jonas Paulsson57a705d2017-08-17 08:33:44 +0000439/// A region of an MBB for scheduling.
Mikael Holmen4eb2a962017-09-13 14:07:47 +0000440namespace {
Jonas Paulsson57a705d2017-08-17 08:33:44 +0000441struct SchedRegion {
442 /// RegionBegin is the first instruction in the scheduling region, and
443 /// RegionEnd is either MBB->end() or the scheduling boundary after the
444 /// last instruction in the scheduling region. These iterators cannot refer
445 /// to instructions outside of the identified scheduling region because
446 /// those may be reordered before scheduling this region.
447 MachineBasicBlock::iterator RegionBegin;
448 MachineBasicBlock::iterator RegionEnd;
449 unsigned NumRegionInstrs;
Eugene Zelenko32a40562017-09-11 23:00:48 +0000450
Jonas Paulsson57a705d2017-08-17 08:33:44 +0000451 SchedRegion(MachineBasicBlock::iterator B, MachineBasicBlock::iterator E,
452 unsigned N) :
453 RegionBegin(B), RegionEnd(E), NumRegionInstrs(N) {}
454};
Mikael Holmen4eb2a962017-09-13 14:07:47 +0000455} // end anonymous namespace
Jonas Paulsson57a705d2017-08-17 08:33:44 +0000456
Eugene Zelenko32a40562017-09-11 23:00:48 +0000457using MBBRegionsVector = SmallVector<SchedRegion, 16>;
458
Jonas Paulsson57a705d2017-08-17 08:33:44 +0000459static void
460getSchedRegions(MachineBasicBlock *MBB,
461 MBBRegionsVector &Regions,
462 bool RegionsTopDown) {
463 MachineFunction *MF = MBB->getParent();
464 const TargetInstrInfo *TII = MF->getSubtarget().getInstrInfo();
465
466 MachineBasicBlock::iterator I = nullptr;
467 for(MachineBasicBlock::iterator RegionEnd = MBB->end();
468 RegionEnd != MBB->begin(); RegionEnd = I) {
469
470 // Avoid decrementing RegionEnd for blocks with no terminator.
471 if (RegionEnd != MBB->end() ||
472 isSchedBoundary(&*std::prev(RegionEnd), &*MBB, MF, TII)) {
473 --RegionEnd;
474 }
475
476 // The next region starts above the previous region. Look backward in the
477 // instruction stream until we find the nearest boundary.
478 unsigned NumRegionInstrs = 0;
479 I = RegionEnd;
480 for (;I != MBB->begin(); --I) {
481 MachineInstr &MI = *std::prev(I);
482 if (isSchedBoundary(&MI, &*MBB, MF, TII))
483 break;
484 if (!MI.isDebugValue())
485 // MBB::size() uses instr_iterator to count. Here we need a bundle to
486 // count as a single instruction.
487 ++NumRegionInstrs;
488 }
489
490 Regions.push_back(SchedRegion(I, RegionEnd, NumRegionInstrs));
491 }
492
493 if (RegionsTopDown)
494 std::reverse(Regions.begin(), Regions.end());
495}
496
Andrew Trickd7f890e2013-12-28 21:56:47 +0000497/// Main driver for both MachineScheduler and PostMachineScheduler.
Matthias Braun93563e72015-11-03 01:53:29 +0000498void MachineSchedulerBase::scheduleRegions(ScheduleDAGInstrs &Scheduler,
499 bool FixKillFlags) {
Andrew Tricke77e84e2012-01-13 06:30:30 +0000500 // Visit all machine basic blocks.
Andrew Trick88639922012-04-24 17:56:43 +0000501 //
502 // TODO: Visit blocks in global postorder or postorder within the bottom-up
503 // loop tree. Then we can optionally compute global RegPressure.
Andrew Tricke77e84e2012-01-13 06:30:30 +0000504 for (MachineFunction::iterator MBB = MF->begin(), MBBEnd = MF->end();
505 MBB != MBBEnd; ++MBB) {
506
Duncan P. N. Exon Smith5ec15682015-10-09 19:40:45 +0000507 Scheduler.startBlock(&*MBB);
Andrew Trickedfe2ec2012-03-09 08:02:51 +0000508
Andrew Trick33e05d72013-12-28 21:57:02 +0000509#ifndef NDEBUG
510 if (SchedOnlyFunc.getNumOccurrences() && SchedOnlyFunc != MF->getName())
511 continue;
512 if (SchedOnlyBlock.getNumOccurrences()
513 && (int)SchedOnlyBlock != MBB->getNumber())
514 continue;
515#endif
516
Jonas Paulsson57a705d2017-08-17 08:33:44 +0000517 // Break the block into scheduling regions [I, RegionEnd). RegionEnd
518 // points to the scheduling boundary at the bottom of the region. The DAG
519 // does not include RegionEnd, but the region does (i.e. the next
520 // RegionEnd is above the previous RegionBegin). If the current block has
521 // no terminator then RegionEnd == MBB->end() for the bottom region.
522 //
523 // All the regions of MBB are first found and stored in MBBRegions, which
524 // will be processed (MBB) top-down if initialized with true.
Andrew Trickaf1bee72012-03-09 22:34:56 +0000525 //
526 // The Scheduler may insert instructions during either schedule() or
527 // exitRegion(), even for empty regions. So the local iterators 'I' and
Jonas Paulsson57a705d2017-08-17 08:33:44 +0000528 // 'RegionEnd' are invalid across these calls. Instructions must not be
529 // added to other regions than the current one without updating MBBRegions.
Andrew Trick88639922012-04-24 17:56:43 +0000530
Jonas Paulsson57a705d2017-08-17 08:33:44 +0000531 MBBRegionsVector MBBRegions;
532 getSchedRegions(&*MBB, MBBRegions, Scheduler.doMBBSchedRegionsTopDown());
533 for (MBBRegionsVector::iterator R = MBBRegions.begin();
534 R != MBBRegions.end(); ++R) {
535 MachineBasicBlock::iterator I = R->RegionBegin;
536 MachineBasicBlock::iterator RegionEnd = R->RegionEnd;
537 unsigned NumRegionInstrs = R->NumRegionInstrs;
Andrew Trickedfe2ec2012-03-09 08:02:51 +0000538
Andrew Trick60cf03e2012-03-07 05:21:52 +0000539 // Notify the scheduler of the region, even if we may skip scheduling
540 // it. Perhaps it still needs to be bundled.
Duncan P. N. Exon Smith5ec15682015-10-09 19:40:45 +0000541 Scheduler.enterRegion(&*MBB, I, RegionEnd, NumRegionInstrs);
Andrew Trick60cf03e2012-03-07 05:21:52 +0000542
543 // Skip empty scheduling regions (0 or 1 schedulable instructions).
Benjamin Kramerb6d0bd42014-03-02 12:27:27 +0000544 if (I == RegionEnd || I == std::prev(RegionEnd)) {
Andrew Trick60cf03e2012-03-07 05:21:52 +0000545 // Close the current region. Bundle the terminator if needed.
Andrew Trickaf1bee72012-03-09 22:34:56 +0000546 // This invalidates 'RegionEnd' and 'I'.
Andrew Trickd7f890e2013-12-28 21:56:47 +0000547 Scheduler.exitRegion();
Andrew Trick7ccdc5c2012-01-17 06:55:07 +0000548 continue;
Andrew Trick59ac4fb2012-01-14 02:17:18 +0000549 }
Matthias Braun93563e72015-11-03 01:53:29 +0000550 DEBUG(dbgs() << "********** MI Scheduling **********\n");
Francis Visoiu Mistrih25528d62017-12-04 17:18:51 +0000551 DEBUG(dbgs() << MF->getName() << ":" << printMBBReference(*MBB) << " "
Francis Visoiu Mistrihd65438d2018-02-08 23:42:27 +0000552 << MBB->getName() << "\n From: " << *I << '\n'
553 << " To: ";
554 if (RegionEnd != MBB->end()) {
555 dbgs() << *RegionEnd << '\n';
556 } else {
557 dbgs() << "End";
558 }
Matthias Braun858d1df2016-05-20 19:46:13 +0000559 dbgs() << " RegionInstrs: " << NumRegionInstrs << '\n');
Gerolf Hoflehnerb5220dc2014-08-07 21:49:44 +0000560 if (DumpCriticalPathLength) {
561 errs() << MF->getName();
Francis Visoiu Mistrih25528d62017-12-04 17:18:51 +0000562 errs() << ":%bb. " << MBB->getNumber();
Gerolf Hoflehnerb5220dc2014-08-07 21:49:44 +0000563 errs() << " " << MBB->getName() << " \n";
564 }
Andrew Trick7ccdc5c2012-01-17 06:55:07 +0000565
Andrew Trick1c0ec452012-03-09 03:46:42 +0000566 // Schedule a region: possibly reorder instructions.
Jonas Paulsson57a705d2017-08-17 08:33:44 +0000567 // This invalidates the original region iterators.
Andrew Trickd7f890e2013-12-28 21:56:47 +0000568 Scheduler.schedule();
Andrew Trick1c0ec452012-03-09 03:46:42 +0000569
570 // Close the current region.
Andrew Trickd7f890e2013-12-28 21:56:47 +0000571 Scheduler.exitRegion();
Andrew Trick7e120f42012-01-14 02:17:09 +0000572 }
Andrew Trickd7f890e2013-12-28 21:56:47 +0000573 Scheduler.finishBlock();
Matthias Braun93563e72015-11-03 01:53:29 +0000574 // FIXME: Ideally, no further passes should rely on kill flags. However,
575 // thumb2 size reduction is currently an exception, so the PostMIScheduler
576 // needs to do this.
577 if (FixKillFlags)
Matthias Braun868bbd42017-05-27 02:50:50 +0000578 Scheduler.fixupKills(*MBB);
Andrew Tricke77e84e2012-01-13 06:30:30 +0000579 }
Andrew Trickd7f890e2013-12-28 21:56:47 +0000580 Scheduler.finalizeSchedule();
Andrew Tricke77e84e2012-01-13 06:30:30 +0000581}
582
Andrew Trickd7f890e2013-12-28 21:56:47 +0000583void MachineSchedulerBase::print(raw_ostream &O, const Module* m) const {
Andrew Tricke77e84e2012-01-13 06:30:30 +0000584 // unimplemented
585}
586
Aaron Ballman615eb472017-10-15 14:32:27 +0000587#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
Sam Clegg705f7982017-06-21 22:19:17 +0000588LLVM_DUMP_METHOD void ReadyQueue::dump() const {
James Y Knighte72b0db2015-09-18 18:52:20 +0000589 dbgs() << "Queue " << Name << ": ";
Javed Absare3a0cc22017-06-21 09:10:10 +0000590 for (const SUnit *SU : Queue)
591 dbgs() << SU->NodeNum << " ";
Andrew Trick7a8e1002012-09-11 00:39:15 +0000592 dbgs() << "\n";
593}
Matthias Braun8c209aa2017-01-28 02:02:38 +0000594#endif
Andrew Trick8823dec2012-03-14 04:00:41 +0000595
596//===----------------------------------------------------------------------===//
Andrew Trickd7f890e2013-12-28 21:56:47 +0000597// ScheduleDAGMI - Basic machine instruction scheduling. This is
598// independent of PreRA/PostRA scheduling and involves no extra book-keeping for
599// virtual registers.
600// ===----------------------------------------------------------------------===/
Andrew Trick8823dec2012-03-14 04:00:41 +0000601
David Blaikie422b93d2014-04-21 20:32:32 +0000602// Provide a vtable anchor.
Eugene Zelenkodb56e5a2017-02-22 22:32:51 +0000603ScheduleDAGMI::~ScheduleDAGMI() = default;
Andrew Trick44f750a2013-01-25 04:01:04 +0000604
Andrew Trick85a1d4c2013-04-24 15:54:43 +0000605bool ScheduleDAGMI::canAddEdge(SUnit *SuccSU, SUnit *PredSU) {
606 return SuccSU == &ExitSU || !Topo.IsReachable(PredSU, SuccSU);
607}
608
Andrew Tricka7714a02012-11-12 19:40:10 +0000609bool ScheduleDAGMI::addEdge(SUnit *SuccSU, const SDep &PredDep) {
Andrew Trick263280242012-11-12 19:52:20 +0000610 if (SuccSU != &ExitSU) {
611 // Do not use WillCreateCycle, it assumes SD scheduling.
612 // If Pred is reachable from Succ, then the edge creates a cycle.
613 if (Topo.IsReachable(PredDep.getSUnit(), SuccSU))
614 return false;
615 Topo.AddPred(SuccSU, PredDep.getSUnit());
616 }
Andrew Tricka7714a02012-11-12 19:40:10 +0000617 SuccSU->addPred(PredDep, /*Required=*/!PredDep.isArtificial());
618 // Return true regardless of whether a new edge needed to be inserted.
619 return true;
620}
621
Andrew Trick02a80da2012-03-08 01:41:12 +0000622/// ReleaseSucc - Decrement the NumPredsLeft count of a successor. When
623/// NumPredsLeft reaches zero, release the successor node.
Andrew Trick61f1a272012-05-24 22:11:09 +0000624///
625/// FIXME: Adjust SuccSU height based on MinLatency.
Andrew Trick8823dec2012-03-14 04:00:41 +0000626void ScheduleDAGMI::releaseSucc(SUnit *SU, SDep *SuccEdge) {
Andrew Trick02a80da2012-03-08 01:41:12 +0000627 SUnit *SuccSU = SuccEdge->getSUnit();
628
Andrew Trickf1ff84c2012-11-12 19:28:57 +0000629 if (SuccEdge->isWeak()) {
630 --SuccSU->WeakPredsLeft;
Andrew Tricka7714a02012-11-12 19:40:10 +0000631 if (SuccEdge->isCluster())
632 NextClusterSucc = SuccSU;
Andrew Trickf1ff84c2012-11-12 19:28:57 +0000633 return;
634 }
Andrew Trick02a80da2012-03-08 01:41:12 +0000635#ifndef NDEBUG
636 if (SuccSU->NumPredsLeft == 0) {
637 dbgs() << "*** Scheduling failed! ***\n";
638 SuccSU->dump(this);
639 dbgs() << " has been released too many times!\n";
Craig Topperc0196b12014-04-14 00:51:57 +0000640 llvm_unreachable(nullptr);
Andrew Trick02a80da2012-03-08 01:41:12 +0000641 }
642#endif
Andrew Trick7f1ebbe2014-06-07 01:48:43 +0000643 // SU->TopReadyCycle was set to CurrCycle when it was scheduled. However,
644 // CurrCycle may have advanced since then.
645 if (SuccSU->TopReadyCycle < SU->TopReadyCycle + SuccEdge->getLatency())
646 SuccSU->TopReadyCycle = SU->TopReadyCycle + SuccEdge->getLatency();
647
Andrew Trick02a80da2012-03-08 01:41:12 +0000648 --SuccSU->NumPredsLeft;
649 if (SuccSU->NumPredsLeft == 0 && SuccSU != &ExitSU)
Andrew Trick8823dec2012-03-14 04:00:41 +0000650 SchedImpl->releaseTopNode(SuccSU);
Andrew Trick02a80da2012-03-08 01:41:12 +0000651}
652
653/// releaseSuccessors - Call releaseSucc on each of SU's successors.
Andrew Trick8823dec2012-03-14 04:00:41 +0000654void ScheduleDAGMI::releaseSuccessors(SUnit *SU) {
Javed Absare3a0cc22017-06-21 09:10:10 +0000655 for (SDep &Succ : SU->Succs)
656 releaseSucc(SU, &Succ);
Andrew Trick02a80da2012-03-08 01:41:12 +0000657}
658
Andrew Trick8823dec2012-03-14 04:00:41 +0000659/// ReleasePred - Decrement the NumSuccsLeft count of a predecessor. When
660/// NumSuccsLeft reaches zero, release the predecessor node.
Andrew Trick61f1a272012-05-24 22:11:09 +0000661///
662/// FIXME: Adjust PredSU height based on MinLatency.
Andrew Trick8823dec2012-03-14 04:00:41 +0000663void ScheduleDAGMI::releasePred(SUnit *SU, SDep *PredEdge) {
664 SUnit *PredSU = PredEdge->getSUnit();
665
Andrew Trickf1ff84c2012-11-12 19:28:57 +0000666 if (PredEdge->isWeak()) {
667 --PredSU->WeakSuccsLeft;
Andrew Tricka7714a02012-11-12 19:40:10 +0000668 if (PredEdge->isCluster())
669 NextClusterPred = PredSU;
Andrew Trickf1ff84c2012-11-12 19:28:57 +0000670 return;
671 }
Andrew Trick8823dec2012-03-14 04:00:41 +0000672#ifndef NDEBUG
673 if (PredSU->NumSuccsLeft == 0) {
674 dbgs() << "*** Scheduling failed! ***\n";
675 PredSU->dump(this);
676 dbgs() << " has been released too many times!\n";
Craig Topperc0196b12014-04-14 00:51:57 +0000677 llvm_unreachable(nullptr);
Andrew Trick8823dec2012-03-14 04:00:41 +0000678 }
679#endif
Andrew Trick7f1ebbe2014-06-07 01:48:43 +0000680 // SU->BotReadyCycle was set to CurrCycle when it was scheduled. However,
681 // CurrCycle may have advanced since then.
682 if (PredSU->BotReadyCycle < SU->BotReadyCycle + PredEdge->getLatency())
683 PredSU->BotReadyCycle = SU->BotReadyCycle + PredEdge->getLatency();
684
Andrew Trick8823dec2012-03-14 04:00:41 +0000685 --PredSU->NumSuccsLeft;
686 if (PredSU->NumSuccsLeft == 0 && PredSU != &EntrySU)
687 SchedImpl->releaseBottomNode(PredSU);
688}
689
690/// releasePredecessors - Call releasePred on each of SU's predecessors.
691void ScheduleDAGMI::releasePredecessors(SUnit *SU) {
Javed Absare3a0cc22017-06-21 09:10:10 +0000692 for (SDep &Pred : SU->Preds)
693 releasePred(SU, &Pred);
Andrew Trick8823dec2012-03-14 04:00:41 +0000694}
695
Jonas Paulsson57a705d2017-08-17 08:33:44 +0000696void ScheduleDAGMI::startBlock(MachineBasicBlock *bb) {
697 ScheduleDAGInstrs::startBlock(bb);
698 SchedImpl->enterMBB(bb);
699}
700
701void ScheduleDAGMI::finishBlock() {
702 SchedImpl->leaveMBB();
703 ScheduleDAGInstrs::finishBlock();
704}
705
Andrew Trickd7f890e2013-12-28 21:56:47 +0000706/// enterRegion - Called back from MachineScheduler::runOnMachineFunction after
707/// crossing a scheduling boundary. [begin, end) includes all instructions in
708/// the region, including the boundary itself and single-instruction regions
709/// that don't get scheduled.
710void ScheduleDAGMI::enterRegion(MachineBasicBlock *bb,
711 MachineBasicBlock::iterator begin,
712 MachineBasicBlock::iterator end,
713 unsigned regioninstrs)
714{
715 ScheduleDAGInstrs::enterRegion(bb, begin, end, regioninstrs);
716
717 SchedImpl->initPolicy(begin, end, regioninstrs);
718}
719
Andrew Tricke833e1c2013-04-13 06:07:40 +0000720/// This is normally called from the main scheduler loop but may also be invoked
721/// by the scheduling strategy to perform additional code motion.
Andrew Trickd7f890e2013-12-28 21:56:47 +0000722void ScheduleDAGMI::moveInstruction(
723 MachineInstr *MI, MachineBasicBlock::iterator InsertPos) {
Andrew Trick463b2f12012-05-17 18:35:03 +0000724 // Advance RegionBegin if the first instruction moves down.
Andrew Trick54f7def2012-03-21 04:12:10 +0000725 if (&*RegionBegin == MI)
Andrew Trick463b2f12012-05-17 18:35:03 +0000726 ++RegionBegin;
727
728 // Update the instruction stream.
Andrew Trick8823dec2012-03-14 04:00:41 +0000729 BB->splice(InsertPos, BB, MI);
Andrew Trick463b2f12012-05-17 18:35:03 +0000730
731 // Update LiveIntervals
Andrew Trickd7f890e2013-12-28 21:56:47 +0000732 if (LIS)
Duncan P. N. Exon Smithbe8f8c42016-02-27 20:14:29 +0000733 LIS->handleMove(*MI, /*UpdateFlags=*/true);
Andrew Trick463b2f12012-05-17 18:35:03 +0000734
735 // Recede RegionBegin if an instruction moves above the first.
Andrew Trick8823dec2012-03-14 04:00:41 +0000736 if (RegionBegin == InsertPos)
737 RegionBegin = MI;
738}
739
Andrew Trickde670c02012-03-21 04:12:07 +0000740bool ScheduleDAGMI::checkSchedLimit() {
741#ifndef NDEBUG
742 if (NumInstrsScheduled == MISchedCutoff && MISchedCutoff != ~0U) {
743 CurrentTop = CurrentBottom;
744 return false;
745 }
746 ++NumInstrsScheduled;
747#endif
748 return true;
749}
750
Andrew Trickd7f890e2013-12-28 21:56:47 +0000751/// Per-region scheduling driver, called back from
752/// MachineScheduler::runOnMachineFunction. This is a simplified driver that
753/// does not consider liveness or register pressure. It is useful for PostRA
754/// scheduling and potentially other custom schedulers.
755void ScheduleDAGMI::schedule() {
James Y Knighte72b0db2015-09-18 18:52:20 +0000756 DEBUG(dbgs() << "ScheduleDAGMI::schedule starting\n");
757 DEBUG(SchedImpl->dumpPolicy());
758
Andrew Trickd7f890e2013-12-28 21:56:47 +0000759 // Build the DAG.
760 buildSchedGraph(AA);
761
762 Topo.InitDAGTopologicalSorting();
763
764 postprocessDAG();
765
766 SmallVector<SUnit*, 8> TopRoots, BotRoots;
767 findRootsAndBiasEdges(TopRoots, BotRoots);
768
769 // Initialize the strategy before modifying the DAG.
770 // This may initialize a DFSResult to be used for queue priority.
771 SchedImpl->initialize(this);
772
Matthias Braun69f1d122016-11-11 22:37:28 +0000773 DEBUG(
774 if (EntrySU.getInstr() != nullptr)
775 EntrySU.dumpAll(this);
Javed Absare3a0cc22017-06-21 09:10:10 +0000776 for (const SUnit &SU : SUnits)
777 SU.dumpAll(this);
Matthias Braun69f1d122016-11-11 22:37:28 +0000778 if (ExitSU.getInstr() != nullptr)
779 ExitSU.dumpAll(this);
780 );
Andrew Trickd7f890e2013-12-28 21:56:47 +0000781 if (ViewMISchedDAGs) viewGraph();
782
783 // Initialize ready queues now that the DAG and priority data are finalized.
784 initQueues(TopRoots, BotRoots);
785
786 bool IsTopNode = false;
James Y Knighte72b0db2015-09-18 18:52:20 +0000787 while (true) {
788 DEBUG(dbgs() << "** ScheduleDAGMI::schedule picking next node\n");
789 SUnit *SU = SchedImpl->pickNode(IsTopNode);
790 if (!SU) break;
791
Andrew Trickd7f890e2013-12-28 21:56:47 +0000792 assert(!SU->isScheduled && "Node already scheduled");
793 if (!checkSchedLimit())
794 break;
795
796 MachineInstr *MI = SU->getInstr();
797 if (IsTopNode) {
798 assert(SU->isTopReady() && "node still has unscheduled dependencies");
799 if (&*CurrentTop == MI)
800 CurrentTop = nextIfDebug(++CurrentTop, CurrentBottom);
801 else
802 moveInstruction(MI, CurrentTop);
Matthias Braunb550b762016-04-21 01:54:13 +0000803 } else {
Andrew Trickd7f890e2013-12-28 21:56:47 +0000804 assert(SU->isBottomReady() && "node still has unscheduled dependencies");
805 MachineBasicBlock::iterator priorII =
806 priorNonDebug(CurrentBottom, CurrentTop);
807 if (&*priorII == MI)
808 CurrentBottom = priorII;
809 else {
810 if (&*CurrentTop == MI)
811 CurrentTop = nextIfDebug(++CurrentTop, priorII);
812 moveInstruction(MI, CurrentBottom);
813 CurrentBottom = MI;
814 }
815 }
Andrew Trick7f1ebbe2014-06-07 01:48:43 +0000816 // Notify the scheduling strategy before updating the DAG.
Andrew Trick491e34a2014-06-12 22:36:28 +0000817 // This sets the scheduled node's ReadyCycle to CurrCycle. When updateQueues
Andrew Trick7f1ebbe2014-06-07 01:48:43 +0000818 // runs, it can then use the accurate ReadyCycle time to determine whether
819 // newly released nodes can move to the readyQ.
Andrew Trickd7f890e2013-12-28 21:56:47 +0000820 SchedImpl->schedNode(SU, IsTopNode);
Andrew Trick7f1ebbe2014-06-07 01:48:43 +0000821
822 updateQueues(SU, IsTopNode);
Andrew Trickd7f890e2013-12-28 21:56:47 +0000823 }
824 assert(CurrentTop == CurrentBottom && "Nonempty unscheduled zone.");
825
826 placeDebugValues();
827
828 DEBUG({
Francis Visoiu Mistrih25528d62017-12-04 17:18:51 +0000829 dbgs() << "*** Final schedule for "
830 << printMBBReference(*begin()->getParent()) << " ***\n";
831 dumpSchedule();
832 dbgs() << '\n';
833 });
Andrew Trickd7f890e2013-12-28 21:56:47 +0000834}
835
836/// Apply each ScheduleDAGMutation step in order.
837void ScheduleDAGMI::postprocessDAG() {
Javed Absare3a0cc22017-06-21 09:10:10 +0000838 for (auto &m : Mutations)
839 m->apply(this);
Andrew Trickd7f890e2013-12-28 21:56:47 +0000840}
841
842void ScheduleDAGMI::
843findRootsAndBiasEdges(SmallVectorImpl<SUnit*> &TopRoots,
844 SmallVectorImpl<SUnit*> &BotRoots) {
Javed Absare3a0cc22017-06-21 09:10:10 +0000845 for (SUnit &SU : SUnits) {
846 assert(!SU.isBoundaryNode() && "Boundary node should not be in SUnits");
Andrew Trickd7f890e2013-12-28 21:56:47 +0000847
848 // Order predecessors so DFSResult follows the critical path.
Javed Absare3a0cc22017-06-21 09:10:10 +0000849 SU.biasCriticalPath();
Andrew Trickd7f890e2013-12-28 21:56:47 +0000850
851 // A SUnit is ready to top schedule if it has no predecessors.
Javed Absare3a0cc22017-06-21 09:10:10 +0000852 if (!SU.NumPredsLeft)
853 TopRoots.push_back(&SU);
Andrew Trickd7f890e2013-12-28 21:56:47 +0000854 // A SUnit is ready to bottom schedule if it has no successors.
Javed Absare3a0cc22017-06-21 09:10:10 +0000855 if (!SU.NumSuccsLeft)
856 BotRoots.push_back(&SU);
Andrew Trickd7f890e2013-12-28 21:56:47 +0000857 }
858 ExitSU.biasCriticalPath();
859}
860
861/// Identify DAG roots and setup scheduler queues.
862void ScheduleDAGMI::initQueues(ArrayRef<SUnit*> TopRoots,
863 ArrayRef<SUnit*> BotRoots) {
Craig Topperc0196b12014-04-14 00:51:57 +0000864 NextClusterSucc = nullptr;
865 NextClusterPred = nullptr;
Andrew Trickd7f890e2013-12-28 21:56:47 +0000866
867 // Release all DAG roots for scheduling, not including EntrySU/ExitSU.
868 //
869 // Nodes with unreleased weak edges can still be roots.
870 // Release top roots in forward order.
Javed Absare3a0cc22017-06-21 09:10:10 +0000871 for (SUnit *SU : TopRoots)
872 SchedImpl->releaseTopNode(SU);
873
Andrew Trickd7f890e2013-12-28 21:56:47 +0000874 // Release bottom roots in reverse order so the higher priority nodes appear
875 // first. This is more natural and slightly more efficient.
876 for (SmallVectorImpl<SUnit*>::const_reverse_iterator
877 I = BotRoots.rbegin(), E = BotRoots.rend(); I != E; ++I) {
878 SchedImpl->releaseBottomNode(*I);
879 }
880
881 releaseSuccessors(&EntrySU);
882 releasePredecessors(&ExitSU);
883
884 SchedImpl->registerRoots();
885
886 // Advance past initial DebugValues.
887 CurrentTop = nextIfDebug(RegionBegin, RegionEnd);
888 CurrentBottom = RegionEnd;
889}
890
891/// Update scheduler queues after scheduling an instruction.
892void ScheduleDAGMI::updateQueues(SUnit *SU, bool IsTopNode) {
893 // Release dependent instructions for scheduling.
894 if (IsTopNode)
895 releaseSuccessors(SU);
896 else
897 releasePredecessors(SU);
898
899 SU->isScheduled = true;
900}
901
902/// Reinsert any remaining debug_values, just like the PostRA scheduler.
903void ScheduleDAGMI::placeDebugValues() {
904 // If first instruction was a DBG_VALUE then put it back.
905 if (FirstDbgValue) {
906 BB->splice(RegionBegin, BB, FirstDbgValue);
907 RegionBegin = FirstDbgValue;
908 }
909
Eugene Zelenkodb56e5a2017-02-22 22:32:51 +0000910 for (std::vector<std::pair<MachineInstr *, MachineInstr *>>::iterator
Andrew Trickd7f890e2013-12-28 21:56:47 +0000911 DI = DbgValues.end(), DE = DbgValues.begin(); DI != DE; --DI) {
Benjamin Kramerb6d0bd42014-03-02 12:27:27 +0000912 std::pair<MachineInstr *, MachineInstr *> P = *std::prev(DI);
Andrew Trickd7f890e2013-12-28 21:56:47 +0000913 MachineInstr *DbgValue = P.first;
914 MachineBasicBlock::iterator OrigPrevMI = P.second;
915 if (&*RegionBegin == DbgValue)
916 ++RegionBegin;
917 BB->splice(++OrigPrevMI, BB, DbgValue);
Benjamin Kramerb6d0bd42014-03-02 12:27:27 +0000918 if (OrigPrevMI == std::prev(RegionEnd))
Andrew Trickd7f890e2013-12-28 21:56:47 +0000919 RegionEnd = DbgValue;
920 }
921 DbgValues.clear();
Craig Topperc0196b12014-04-14 00:51:57 +0000922 FirstDbgValue = nullptr;
Andrew Trickd7f890e2013-12-28 21:56:47 +0000923}
924
Aaron Ballman615eb472017-10-15 14:32:27 +0000925#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
Matthias Braun8c209aa2017-01-28 02:02:38 +0000926LLVM_DUMP_METHOD void ScheduleDAGMI::dumpSchedule() const {
Andrew Trickd7f890e2013-12-28 21:56:47 +0000927 for (MachineBasicBlock::iterator MI = begin(), ME = end(); MI != ME; ++MI) {
928 if (SUnit *SU = getSUnit(&(*MI)))
929 SU->dump(this);
930 else
931 dbgs() << "Missing SUnit\n";
932 }
933}
934#endif
935
936//===----------------------------------------------------------------------===//
937// ScheduleDAGMILive - Base class for MachineInstr scheduling with LiveIntervals
938// preservation.
939//===----------------------------------------------------------------------===//
940
941ScheduleDAGMILive::~ScheduleDAGMILive() {
942 delete DFSResult;
943}
944
Matthias Braun40639882016-11-11 22:37:31 +0000945void ScheduleDAGMILive::collectVRegUses(SUnit &SU) {
946 const MachineInstr &MI = *SU.getInstr();
947 for (const MachineOperand &MO : MI.operands()) {
948 if (!MO.isReg())
949 continue;
950 if (!MO.readsReg())
951 continue;
952 if (TrackLaneMasks && !MO.isUse())
953 continue;
954
955 unsigned Reg = MO.getReg();
956 if (!TargetRegisterInfo::isVirtualRegister(Reg))
957 continue;
958
959 // Ignore re-defs.
960 if (TrackLaneMasks) {
961 bool FoundDef = false;
962 for (const MachineOperand &MO2 : MI.operands()) {
963 if (MO2.isReg() && MO2.isDef() && MO2.getReg() == Reg && !MO2.isDead()) {
964 FoundDef = true;
965 break;
966 }
967 }
968 if (FoundDef)
969 continue;
970 }
971
972 // Record this local VReg use.
973 VReg2SUnitMultiMap::iterator UI = VRegUses.find(Reg);
974 for (; UI != VRegUses.end(); ++UI) {
975 if (UI->SU == &SU)
976 break;
977 }
978 if (UI == VRegUses.end())
Krzysztof Parzyszek91b5cf82016-12-15 14:36:06 +0000979 VRegUses.insert(VReg2SUnit(Reg, LaneBitmask::getNone(), &SU));
Matthias Braun40639882016-11-11 22:37:31 +0000980 }
981}
982
Andrew Trick88639922012-04-24 17:56:43 +0000983/// enterRegion - Called back from MachineScheduler::runOnMachineFunction after
984/// crossing a scheduling boundary. [begin, end) includes all instructions in
985/// the region, including the boundary itself and single-instruction regions
986/// that don't get scheduled.
Andrew Trickd7f890e2013-12-28 21:56:47 +0000987void ScheduleDAGMILive::enterRegion(MachineBasicBlock *bb,
Andrew Trick88639922012-04-24 17:56:43 +0000988 MachineBasicBlock::iterator begin,
989 MachineBasicBlock::iterator end,
Andrew Tricka53e1012013-08-23 17:48:33 +0000990 unsigned regioninstrs)
Andrew Trick88639922012-04-24 17:56:43 +0000991{
Andrew Trickd7f890e2013-12-28 21:56:47 +0000992 // ScheduleDAGMI initializes SchedImpl's per-region policy.
993 ScheduleDAGMI::enterRegion(bb, begin, end, regioninstrs);
Andrew Trick4add42f2012-05-10 21:06:10 +0000994
995 // For convenience remember the end of the liveness region.
Benjamin Kramerb6d0bd42014-03-02 12:27:27 +0000996 LiveRegionEnd = (RegionEnd == bb->end()) ? RegionEnd : std::next(RegionEnd);
Andrew Trick75e411c2013-09-06 17:32:34 +0000997
Andrew Trickb248b4a2013-09-06 17:32:47 +0000998 SUPressureDiffs.clear();
999
Andrew Trick75e411c2013-09-06 17:32:34 +00001000 ShouldTrackPressure = SchedImpl->shouldTrackPressure();
Matthias Braund4f64092016-01-20 00:23:32 +00001001 ShouldTrackLaneMasks = SchedImpl->shouldTrackLaneMasks();
1002
Matthias Braunf9acaca2016-05-31 22:38:06 +00001003 assert((!ShouldTrackLaneMasks || ShouldTrackPressure) &&
1004 "ShouldTrackLaneMasks requires ShouldTrackPressure");
Andrew Trick4add42f2012-05-10 21:06:10 +00001005}
1006
1007// Setup the register pressure trackers for the top scheduled top and bottom
1008// scheduled regions.
Andrew Trickd7f890e2013-12-28 21:56:47 +00001009void ScheduleDAGMILive::initRegPressure() {
Matthias Braun40639882016-11-11 22:37:31 +00001010 VRegUses.clear();
1011 VRegUses.setUniverse(MRI.getNumVirtRegs());
1012 for (SUnit &SU : SUnits)
1013 collectVRegUses(SU);
1014
Matthias Braund4f64092016-01-20 00:23:32 +00001015 TopRPTracker.init(&MF, RegClassInfo, LIS, BB, RegionBegin,
1016 ShouldTrackLaneMasks, false);
1017 BotRPTracker.init(&MF, RegClassInfo, LIS, BB, LiveRegionEnd,
1018 ShouldTrackLaneMasks, false);
Andrew Trick4add42f2012-05-10 21:06:10 +00001019
1020 // Close the RPTracker to finalize live ins.
1021 RPTracker.closeRegion();
1022
Andrew Trick9c17eab2013-07-30 19:59:12 +00001023 DEBUG(RPTracker.dump());
Andrew Trick79d3eec2012-05-24 22:11:14 +00001024
Andrew Trick4add42f2012-05-10 21:06:10 +00001025 // Initialize the live ins and live outs.
Matthias Braun3e86de12015-09-17 21:12:24 +00001026 TopRPTracker.addLiveRegs(RPTracker.getPressure().LiveInRegs);
1027 BotRPTracker.addLiveRegs(RPTracker.getPressure().LiveOutRegs);
Andrew Trick4add42f2012-05-10 21:06:10 +00001028
1029 // Close one end of the tracker so we can call
1030 // getMaxUpward/DownwardPressureDelta before advancing across any
1031 // instructions. This converts currently live regs into live ins/outs.
1032 TopRPTracker.closeTop();
1033 BotRPTracker.closeBottom();
1034
Andrew Trick9c17eab2013-07-30 19:59:12 +00001035 BotRPTracker.initLiveThru(RPTracker);
1036 if (!BotRPTracker.getLiveThru().empty()) {
1037 TopRPTracker.initLiveThru(BotRPTracker.getLiveThru());
1038 DEBUG(dbgs() << "Live Thru: ";
1039 dumpRegSetPressure(BotRPTracker.getLiveThru(), TRI));
1040 };
1041
Andrew Trick2bc74c22013-08-30 04:36:57 +00001042 // For each live out vreg reduce the pressure change associated with other
1043 // uses of the same vreg below the live-out reaching def.
Matthias Braun3e86de12015-09-17 21:12:24 +00001044 updatePressureDiffs(RPTracker.getPressure().LiveOutRegs);
Andrew Trick2bc74c22013-08-30 04:36:57 +00001045
Andrew Trick4add42f2012-05-10 21:06:10 +00001046 // Account for liveness generated by the region boundary.
Andrew Trick2bc74c22013-08-30 04:36:57 +00001047 if (LiveRegionEnd != RegionEnd) {
Matthias Braun5d458612016-01-20 00:23:26 +00001048 SmallVector<RegisterMaskPair, 8> LiveUses;
Andrew Trick2bc74c22013-08-30 04:36:57 +00001049 BotRPTracker.recede(&LiveUses);
1050 updatePressureDiffs(LiveUses);
1051 }
Andrew Trick4add42f2012-05-10 21:06:10 +00001052
Matthias Braune6edd482015-11-13 22:30:31 +00001053 DEBUG(
1054 dbgs() << "Top Pressure:\n";
1055 dumpRegSetPressure(TopRPTracker.getRegSetPressureAtPos(), TRI);
1056 dbgs() << "Bottom Pressure:\n";
1057 dumpRegSetPressure(BotRPTracker.getRegSetPressureAtPos(), TRI);
1058 );
1059
Yaxun Liuc41e2f62017-12-15 03:56:57 +00001060 assert((BotRPTracker.getPos() == RegionEnd ||
1061 (RegionEnd->isDebugValue() &&
1062 BotRPTracker.getPos() == priorNonDebug(RegionEnd, RegionBegin))) &&
1063 "Can't find the region bottom");
Andrew Trick22025772012-05-17 18:35:10 +00001064
1065 // Cache the list of excess pressure sets in this region. This will also track
1066 // the max pressure in the scheduled code for these sets.
1067 RegionCriticalPSets.clear();
Jakub Staszakc641ada2013-01-25 21:44:27 +00001068 const std::vector<unsigned> &RegionPressure =
1069 RPTracker.getPressure().MaxSetPressure;
Andrew Trick22025772012-05-17 18:35:10 +00001070 for (unsigned i = 0, e = RegionPressure.size(); i < e; ++i) {
Andrew Trick736dd9a2013-06-21 18:32:58 +00001071 unsigned Limit = RegClassInfo->getRegPressureSetLimit(i);
Andrew Trickb55db582013-06-21 18:33:01 +00001072 if (RegionPressure[i] > Limit) {
1073 DEBUG(dbgs() << TRI->getRegPressureSetName(i)
1074 << " Limit " << Limit
1075 << " Actual " << RegionPressure[i] << "\n");
Andrew Trick1a831342013-08-30 03:49:48 +00001076 RegionCriticalPSets.push_back(PressureChange(i));
Andrew Trickb55db582013-06-21 18:33:01 +00001077 }
Andrew Trick22025772012-05-17 18:35:10 +00001078 }
1079 DEBUG(dbgs() << "Excess PSets: ";
Javed Absare3a0cc22017-06-21 09:10:10 +00001080 for (const PressureChange &RCPS : RegionCriticalPSets)
Andrew Trick22025772012-05-17 18:35:10 +00001081 dbgs() << TRI->getRegPressureSetName(
Javed Absare3a0cc22017-06-21 09:10:10 +00001082 RCPS.getPSet()) << " ";
Andrew Trick22025772012-05-17 18:35:10 +00001083 dbgs() << "\n");
1084}
1085
Andrew Trickd7f890e2013-12-28 21:56:47 +00001086void ScheduleDAGMILive::
Andrew Trickb248b4a2013-09-06 17:32:47 +00001087updateScheduledPressure(const SUnit *SU,
1088 const std::vector<unsigned> &NewMaxPressure) {
1089 const PressureDiff &PDiff = getPressureDiff(SU);
1090 unsigned CritIdx = 0, CritEnd = RegionCriticalPSets.size();
Javed Absare3a0cc22017-06-21 09:10:10 +00001091 for (const PressureChange &PC : PDiff) {
1092 if (!PC.isValid())
Andrew Trickb248b4a2013-09-06 17:32:47 +00001093 break;
Javed Absare3a0cc22017-06-21 09:10:10 +00001094 unsigned ID = PC.getPSet();
Andrew Trickb248b4a2013-09-06 17:32:47 +00001095 while (CritIdx != CritEnd && RegionCriticalPSets[CritIdx].getPSet() < ID)
1096 ++CritIdx;
1097 if (CritIdx != CritEnd && RegionCriticalPSets[CritIdx].getPSet() == ID) {
1098 if ((int)NewMaxPressure[ID] > RegionCriticalPSets[CritIdx].getUnitInc()
Simon Pilgrim858d8e62017-02-23 12:00:34 +00001099 && NewMaxPressure[ID] <= (unsigned)std::numeric_limits<int16_t>::max())
Andrew Trickb248b4a2013-09-06 17:32:47 +00001100 RegionCriticalPSets[CritIdx].setUnitInc(NewMaxPressure[ID]);
1101 }
1102 unsigned Limit = RegClassInfo->getRegPressureSetLimit(ID);
1103 if (NewMaxPressure[ID] >= Limit - 2) {
1104 DEBUG(dbgs() << " " << TRI->getRegPressureSetName(ID) << ": "
Andrew Trick569dc65a2015-05-17 23:40:31 +00001105 << NewMaxPressure[ID]
1106 << ((NewMaxPressure[ID] > Limit) ? " > " : " <= ") << Limit
1107 << "(+ " << BotRPTracker.getLiveThru()[ID] << " livethru)\n");
Andrew Trickb248b4a2013-09-06 17:32:47 +00001108 }
Andrew Trick22025772012-05-17 18:35:10 +00001109 }
Andrew Trick88639922012-04-24 17:56:43 +00001110}
1111
Andrew Trick2bc74c22013-08-30 04:36:57 +00001112/// Update the PressureDiff array for liveness after scheduling this
1113/// instruction.
Matthias Braun5d458612016-01-20 00:23:26 +00001114void ScheduleDAGMILive::updatePressureDiffs(
1115 ArrayRef<RegisterMaskPair> LiveUses) {
1116 for (const RegisterMaskPair &P : LiveUses) {
Matthias Braun5d458612016-01-20 00:23:26 +00001117 unsigned Reg = P.RegUnit;
Matthias Braund4f64092016-01-20 00:23:32 +00001118 /// FIXME: Currently assuming single-use physregs.
Andrew Trick2bc74c22013-08-30 04:36:57 +00001119 if (!TRI->isVirtualRegister(Reg))
1120 continue;
Andrew Trickffdbefb2013-09-06 17:32:39 +00001121
Matthias Braund4f64092016-01-20 00:23:32 +00001122 if (ShouldTrackLaneMasks) {
1123 // If the register has just become live then other uses won't change
1124 // this fact anymore => decrement pressure.
1125 // If the register has just become dead then other uses make it come
1126 // back to life => increment pressure.
Krzysztof Parzyszekea9f8ce2016-12-16 19:11:56 +00001127 bool Decrement = P.LaneMask.any();
Matthias Braund4f64092016-01-20 00:23:32 +00001128
1129 for (const VReg2SUnit &V2SU
1130 : make_range(VRegUses.find(Reg), VRegUses.end())) {
1131 SUnit &SU = *V2SU.SU;
1132 if (SU.isScheduled || &SU == &ExitSU)
1133 continue;
1134
1135 PressureDiff &PDiff = getPressureDiff(&SU);
Stanislav Mekhanoshin42259cf2017-02-24 21:56:16 +00001136 PDiff.addPressureChange(Reg, Decrement, &MRI);
Matthias Braund4f64092016-01-20 00:23:32 +00001137 DEBUG(
1138 dbgs() << " UpdateRegP: SU(" << SU.NodeNum << ") "
Francis Visoiu Mistrih9d419d32017-11-28 12:42:37 +00001139 << printReg(Reg, TRI) << ':' << PrintLaneMask(P.LaneMask)
Francis Visoiu Mistrihd65438d2018-02-08 23:42:27 +00001140 << ' ' << *SU.getInstr() << '\n';
Matthias Braund4f64092016-01-20 00:23:32 +00001141 dbgs() << " to ";
1142 PDiff.dump(*TRI);
1143 );
1144 }
1145 } else {
Krzysztof Parzyszekea9f8ce2016-12-16 19:11:56 +00001146 assert(P.LaneMask.any());
Francis Visoiu Mistrih9d419d32017-11-28 12:42:37 +00001147 DEBUG(dbgs() << " LiveReg: " << printVRegOrUnit(Reg, TRI) << "\n");
Matthias Braund4f64092016-01-20 00:23:32 +00001148 // This may be called before CurrentBottom has been initialized. However,
1149 // BotRPTracker must have a valid position. We want the value live into the
1150 // instruction or live out of the block, so ask for the previous
1151 // instruction's live-out.
1152 const LiveInterval &LI = LIS->getInterval(Reg);
1153 VNInfo *VNI;
1154 MachineBasicBlock::const_iterator I =
1155 nextIfDebug(BotRPTracker.getPos(), BB->end());
1156 if (I == BB->end())
1157 VNI = LI.getVNInfoBefore(LIS->getMBBEndIdx(BB));
1158 else {
Duncan P. N. Exon Smith3ac9cc62016-02-27 06:40:41 +00001159 LiveQueryResult LRQ = LI.Query(LIS->getInstructionIndex(*I));
Matthias Braund4f64092016-01-20 00:23:32 +00001160 VNI = LRQ.valueIn();
1161 }
1162 // RegisterPressureTracker guarantees that readsReg is true for LiveUses.
1163 assert(VNI && "No live value at use.");
1164 for (const VReg2SUnit &V2SU
1165 : make_range(VRegUses.find(Reg), VRegUses.end())) {
1166 SUnit *SU = V2SU.SU;
1167 // If this use comes before the reaching def, it cannot be a last use,
1168 // so decrease its pressure change.
1169 if (!SU->isScheduled && SU != &ExitSU) {
Duncan P. N. Exon Smith3ac9cc62016-02-27 06:40:41 +00001170 LiveQueryResult LRQ =
1171 LI.Query(LIS->getInstructionIndex(*SU->getInstr()));
Matthias Braund4f64092016-01-20 00:23:32 +00001172 if (LRQ.valueIn() == VNI) {
1173 PressureDiff &PDiff = getPressureDiff(SU);
Stanislav Mekhanoshin42259cf2017-02-24 21:56:16 +00001174 PDiff.addPressureChange(Reg, true, &MRI);
Matthias Braund4f64092016-01-20 00:23:32 +00001175 DEBUG(
1176 dbgs() << " UpdateRegP: SU(" << SU->NodeNum << ") "
Francis Visoiu Mistrihd65438d2018-02-08 23:42:27 +00001177 << *SU->getInstr() << '\n';
Matthias Braund4f64092016-01-20 00:23:32 +00001178 dbgs() << " to ";
1179 PDiff.dump(*TRI);
1180 );
1181 }
Matthias Braun9198c672015-11-06 20:59:02 +00001182 }
Andrew Trick2bc74c22013-08-30 04:36:57 +00001183 }
1184 }
1185 }
1186}
1187
Andrew Trick8823dec2012-03-14 04:00:41 +00001188/// schedule - Called back from MachineScheduler::runOnMachineFunction
Andrew Trick88639922012-04-24 17:56:43 +00001189/// after setting up the current scheduling region. [RegionBegin, RegionEnd)
1190/// only includes instructions that have DAG nodes, not scheduling boundaries.
Andrew Trick7a8e1002012-09-11 00:39:15 +00001191///
1192/// This is a skeletal driver, with all the functionality pushed into helpers,
Nick Lewycky06b0ea22015-08-18 22:41:58 +00001193/// so that it can be easily extended by experimental schedulers. Generally,
Andrew Trick7a8e1002012-09-11 00:39:15 +00001194/// implementing MachineSchedStrategy should be sufficient to implement a new
1195/// scheduling algorithm. However, if a scheduler further subclasses
Andrew Trickd7f890e2013-12-28 21:56:47 +00001196/// ScheduleDAGMILive then it will want to override this virtual method in order
1197/// to update any specialized state.
1198void ScheduleDAGMILive::schedule() {
James Y Knighte72b0db2015-09-18 18:52:20 +00001199 DEBUG(dbgs() << "ScheduleDAGMILive::schedule starting\n");
1200 DEBUG(SchedImpl->dumpPolicy());
Andrew Trick7a8e1002012-09-11 00:39:15 +00001201 buildDAGWithRegPressure();
1202
Andrew Tricka7714a02012-11-12 19:40:10 +00001203 Topo.InitDAGTopologicalSorting();
1204
Andrew Tricka2733e92012-09-14 17:22:42 +00001205 postprocessDAG();
1206
Andrew Tricke2c3f5c2013-01-25 06:33:57 +00001207 SmallVector<SUnit*, 8> TopRoots, BotRoots;
1208 findRootsAndBiasEdges(TopRoots, BotRoots);
1209
1210 // Initialize the strategy before modifying the DAG.
1211 // This may initialize a DFSResult to be used for queue priority.
1212 SchedImpl->initialize(this);
1213
Matthias Braun9198c672015-11-06 20:59:02 +00001214 DEBUG(
Matthias Braun69f1d122016-11-11 22:37:28 +00001215 if (EntrySU.getInstr() != nullptr)
1216 EntrySU.dumpAll(this);
Matthias Braun9198c672015-11-06 20:59:02 +00001217 for (const SUnit &SU : SUnits) {
1218 SU.dumpAll(this);
1219 if (ShouldTrackPressure) {
1220 dbgs() << " Pressure Diff : ";
1221 getPressureDiff(&SU).dump(*TRI);
1222 }
Javed Absar3d594372017-03-27 20:46:37 +00001223 dbgs() << " Single Issue : ";
1224 if (SchedModel.mustBeginGroup(SU.getInstr()) &&
1225 SchedModel.mustEndGroup(SU.getInstr()))
1226 dbgs() << "true;";
1227 else
1228 dbgs() << "false;";
Matthias Braun9198c672015-11-06 20:59:02 +00001229 dbgs() << '\n';
1230 }
Matthias Braun69f1d122016-11-11 22:37:28 +00001231 if (ExitSU.getInstr() != nullptr)
1232 ExitSU.dumpAll(this);
Matthias Braun9198c672015-11-06 20:59:02 +00001233 );
Andrew Tricke2c3f5c2013-01-25 06:33:57 +00001234 if (ViewMISchedDAGs) viewGraph();
Andrew Trick7a8e1002012-09-11 00:39:15 +00001235
Andrew Tricke2c3f5c2013-01-25 06:33:57 +00001236 // Initialize ready queues now that the DAG and priority data are finalized.
1237 initQueues(TopRoots, BotRoots);
Andrew Trick7a8e1002012-09-11 00:39:15 +00001238
1239 bool IsTopNode = false;
James Y Knighte72b0db2015-09-18 18:52:20 +00001240 while (true) {
1241 DEBUG(dbgs() << "** ScheduleDAGMILive::schedule picking next node\n");
1242 SUnit *SU = SchedImpl->pickNode(IsTopNode);
1243 if (!SU) break;
1244
Andrew Trick984d98b2012-10-08 18:53:53 +00001245 assert(!SU->isScheduled && "Node already scheduled");
Andrew Trick7a8e1002012-09-11 00:39:15 +00001246 if (!checkSchedLimit())
1247 break;
1248
1249 scheduleMI(SU, IsTopNode);
1250
Andrew Trickd7f890e2013-12-28 21:56:47 +00001251 if (DFSResult) {
1252 unsigned SubtreeID = DFSResult->getSubtreeID(SU);
1253 if (!ScheduledTrees.test(SubtreeID)) {
1254 ScheduledTrees.set(SubtreeID);
1255 DFSResult->scheduleTree(SubtreeID);
1256 SchedImpl->scheduleTree(SubtreeID);
1257 }
1258 }
1259
1260 // Notify the scheduling strategy after updating the DAG.
1261 SchedImpl->schedNode(SU, IsTopNode);
Andrew Trick43adfb32015-03-27 06:10:13 +00001262
1263 updateQueues(SU, IsTopNode);
Andrew Trick7a8e1002012-09-11 00:39:15 +00001264 }
1265 assert(CurrentTop == CurrentBottom && "Nonempty unscheduled zone.");
1266
1267 placeDebugValues();
Andrew Trick3ca33ac2012-11-07 07:05:09 +00001268
1269 DEBUG({
Francis Visoiu Mistrih25528d62017-12-04 17:18:51 +00001270 dbgs() << "*** Final schedule for "
1271 << printMBBReference(*begin()->getParent()) << " ***\n";
1272 dumpSchedule();
1273 dbgs() << '\n';
1274 });
Andrew Trick7a8e1002012-09-11 00:39:15 +00001275}
1276
1277/// Build the DAG and setup three register pressure trackers.
Andrew Trickd7f890e2013-12-28 21:56:47 +00001278void ScheduleDAGMILive::buildDAGWithRegPressure() {
Andrew Trickb6e74712013-09-04 20:59:59 +00001279 if (!ShouldTrackPressure) {
1280 RPTracker.reset();
1281 RegionCriticalPSets.clear();
1282 buildSchedGraph(AA);
1283 return;
1284 }
1285
Andrew Trick4add42f2012-05-10 21:06:10 +00001286 // Initialize the register pressure tracker used by buildSchedGraph.
Andrew Trick9c17eab2013-07-30 19:59:12 +00001287 RPTracker.init(&MF, RegClassInfo, LIS, BB, LiveRegionEnd,
Matthias Braund4f64092016-01-20 00:23:32 +00001288 ShouldTrackLaneMasks, /*TrackUntiedDefs=*/true);
Andrew Trick88639922012-04-24 17:56:43 +00001289
Andrew Trick4add42f2012-05-10 21:06:10 +00001290 // Account for liveness generate by the region boundary.
1291 if (LiveRegionEnd != RegionEnd)
1292 RPTracker.recede();
1293
1294 // Build the DAG, and compute current register pressure.
Matthias Braund4f64092016-01-20 00:23:32 +00001295 buildSchedGraph(AA, &RPTracker, &SUPressureDiffs, LIS, ShouldTrackLaneMasks);
Andrew Trick02a80da2012-03-08 01:41:12 +00001296
Andrew Trick4add42f2012-05-10 21:06:10 +00001297 // Initialize top/bottom trackers after computing region pressure.
1298 initRegPressure();
Andrew Trick7a8e1002012-09-11 00:39:15 +00001299}
Andrew Trick4add42f2012-05-10 21:06:10 +00001300
Andrew Trickd7f890e2013-12-28 21:56:47 +00001301void ScheduleDAGMILive::computeDFSResult() {
Andrew Trick44f750a2013-01-25 04:01:04 +00001302 if (!DFSResult)
1303 DFSResult = new SchedDFSResult(/*BottomU*/true, MinSubtreeSize);
1304 DFSResult->clear();
Andrew Trick44f750a2013-01-25 04:01:04 +00001305 ScheduledTrees.clear();
Andrew Tricke2c3f5c2013-01-25 06:33:57 +00001306 DFSResult->resize(SUnits.size());
1307 DFSResult->compute(SUnits);
Andrew Trick44f750a2013-01-25 04:01:04 +00001308 ScheduledTrees.resize(DFSResult->getNumSubtrees());
1309}
1310
Andrew Trick483f4192013-08-29 18:04:49 +00001311/// Compute the max cyclic critical path through the DAG. The scheduling DAG
1312/// only provides the critical path for single block loops. To handle loops that
1313/// span blocks, we could use the vreg path latencies provided by
1314/// MachineTraceMetrics instead. However, MachineTraceMetrics is not currently
1315/// available for use in the scheduler.
1316///
1317/// The cyclic path estimation identifies a def-use pair that crosses the back
Andrew Trickef80f502013-08-30 02:02:12 +00001318/// edge and considers the depth and height of the nodes. For example, consider
Andrew Trick483f4192013-08-29 18:04:49 +00001319/// the following instruction sequence where each instruction has unit latency
1320/// and defines an epomymous virtual register:
1321///
1322/// a->b(a,c)->c(b)->d(c)->exit
1323///
1324/// The cyclic critical path is a two cycles: b->c->b
1325/// The acyclic critical path is four cycles: a->b->c->d->exit
1326/// LiveOutHeight = height(c) = len(c->d->exit) = 2
1327/// LiveOutDepth = depth(c) + 1 = len(a->b->c) + 1 = 3
1328/// LiveInHeight = height(b) + 1 = len(b->c->d->exit) + 1 = 4
1329/// LiveInDepth = depth(b) = len(a->b) = 1
1330///
1331/// LiveOutDepth - LiveInDepth = 3 - 1 = 2
1332/// LiveInHeight - LiveOutHeight = 4 - 2 = 2
1333/// CyclicCriticalPath = min(2, 2) = 2
Andrew Trickd7f890e2013-12-28 21:56:47 +00001334///
1335/// This could be relevant to PostRA scheduling, but is currently implemented
1336/// assuming LiveIntervals.
1337unsigned ScheduleDAGMILive::computeCyclicCriticalPath() {
Andrew Trick483f4192013-08-29 18:04:49 +00001338 // This only applies to single block loop.
1339 if (!BB->isSuccessor(BB))
1340 return 0;
1341
1342 unsigned MaxCyclicLatency = 0;
1343 // Visit each live out vreg def to find def/use pairs that cross iterations.
Matthias Braun5d458612016-01-20 00:23:26 +00001344 for (const RegisterMaskPair &P : RPTracker.getPressure().LiveOutRegs) {
1345 unsigned Reg = P.RegUnit;
Andrew Trick483f4192013-08-29 18:04:49 +00001346 if (!TRI->isVirtualRegister(Reg))
1347 continue;
1348 const LiveInterval &LI = LIS->getInterval(Reg);
1349 const VNInfo *DefVNI = LI.getVNInfoBefore(LIS->getMBBEndIdx(BB));
1350 if (!DefVNI)
1351 continue;
1352
1353 MachineInstr *DefMI = LIS->getInstructionFromIndex(DefVNI->def);
1354 const SUnit *DefSU = getSUnit(DefMI);
1355 if (!DefSU)
1356 continue;
1357
1358 unsigned LiveOutHeight = DefSU->getHeight();
1359 unsigned LiveOutDepth = DefSU->getDepth() + DefSU->Latency;
1360 // Visit all local users of the vreg def.
Matthias Braunb0c437b2015-10-29 03:57:17 +00001361 for (const VReg2SUnit &V2SU
1362 : make_range(VRegUses.find(Reg), VRegUses.end())) {
1363 SUnit *SU = V2SU.SU;
1364 if (SU == &ExitSU)
Andrew Trick483f4192013-08-29 18:04:49 +00001365 continue;
1366
1367 // Only consider uses of the phi.
Duncan P. N. Exon Smith3ac9cc62016-02-27 06:40:41 +00001368 LiveQueryResult LRQ = LI.Query(LIS->getInstructionIndex(*SU->getInstr()));
Andrew Trick483f4192013-08-29 18:04:49 +00001369 if (!LRQ.valueIn()->isPHIDef())
1370 continue;
1371
1372 // Assume that a path spanning two iterations is a cycle, which could
1373 // overestimate in strange cases. This allows cyclic latency to be
1374 // estimated as the minimum slack of the vreg's depth or height.
1375 unsigned CyclicLatency = 0;
Matthias Braunb0c437b2015-10-29 03:57:17 +00001376 if (LiveOutDepth > SU->getDepth())
1377 CyclicLatency = LiveOutDepth - SU->getDepth();
Andrew Trick483f4192013-08-29 18:04:49 +00001378
Matthias Braunb0c437b2015-10-29 03:57:17 +00001379 unsigned LiveInHeight = SU->getHeight() + DefSU->Latency;
Andrew Trick483f4192013-08-29 18:04:49 +00001380 if (LiveInHeight > LiveOutHeight) {
1381 if (LiveInHeight - LiveOutHeight < CyclicLatency)
1382 CyclicLatency = LiveInHeight - LiveOutHeight;
Matthias Braunb550b762016-04-21 01:54:13 +00001383 } else
Andrew Trick483f4192013-08-29 18:04:49 +00001384 CyclicLatency = 0;
1385
1386 DEBUG(dbgs() << "Cyclic Path: SU(" << DefSU->NodeNum << ") -> SU("
Matthias Braunb0c437b2015-10-29 03:57:17 +00001387 << SU->NodeNum << ") = " << CyclicLatency << "c\n");
Andrew Trick483f4192013-08-29 18:04:49 +00001388 if (CyclicLatency > MaxCyclicLatency)
1389 MaxCyclicLatency = CyclicLatency;
1390 }
1391 }
1392 DEBUG(dbgs() << "Cyclic Critical Path: " << MaxCyclicLatency << "c\n");
1393 return MaxCyclicLatency;
1394}
1395
Krzysztof Parzyszek7ea9a522016-04-28 19:17:44 +00001396/// Release ExitSU predecessors and setup scheduler queues. Re-position
1397/// the Top RP tracker in case the region beginning has changed.
1398void ScheduleDAGMILive::initQueues(ArrayRef<SUnit*> TopRoots,
1399 ArrayRef<SUnit*> BotRoots) {
1400 ScheduleDAGMI::initQueues(TopRoots, BotRoots);
1401 if (ShouldTrackPressure) {
1402 assert(TopRPTracker.getPos() == RegionBegin && "bad initial Top tracker");
1403 TopRPTracker.setPos(CurrentTop);
1404 }
1405}
1406
Andrew Trick7a8e1002012-09-11 00:39:15 +00001407/// Move an instruction and update register pressure.
Andrew Trickd7f890e2013-12-28 21:56:47 +00001408void ScheduleDAGMILive::scheduleMI(SUnit *SU, bool IsTopNode) {
Andrew Trick7a8e1002012-09-11 00:39:15 +00001409 // Move the instruction to its new location in the instruction stream.
1410 MachineInstr *MI = SU->getInstr();
Andrew Trick02a80da2012-03-08 01:41:12 +00001411
Andrew Trick7a8e1002012-09-11 00:39:15 +00001412 if (IsTopNode) {
1413 assert(SU->isTopReady() && "node still has unscheduled dependencies");
1414 if (&*CurrentTop == MI)
1415 CurrentTop = nextIfDebug(++CurrentTop, CurrentBottom);
Andrew Trick8823dec2012-03-14 04:00:41 +00001416 else {
Andrew Trick7a8e1002012-09-11 00:39:15 +00001417 moveInstruction(MI, CurrentTop);
1418 TopRPTracker.setPos(MI);
Andrew Trick8823dec2012-03-14 04:00:41 +00001419 }
Andrew Trickc3ea0052012-04-24 18:04:37 +00001420
Andrew Trickb6e74712013-09-04 20:59:59 +00001421 if (ShouldTrackPressure) {
1422 // Update top scheduled pressure.
Matthias Braund4f64092016-01-20 00:23:32 +00001423 RegisterOperands RegOpers;
1424 RegOpers.collect(*MI, *TRI, MRI, ShouldTrackLaneMasks, false);
1425 if (ShouldTrackLaneMasks) {
1426 // Adjust liveness and add missing dead+read-undef flags.
Duncan P. N. Exon Smith3ac9cc62016-02-27 06:40:41 +00001427 SlotIndex SlotIdx = LIS->getInstructionIndex(*MI).getRegSlot();
Matthias Braund4f64092016-01-20 00:23:32 +00001428 RegOpers.adjustLaneLiveness(*LIS, MRI, SlotIdx, MI);
1429 } else {
1430 // Adjust for missing dead-def flags.
1431 RegOpers.detectDeadDefs(*MI, *LIS);
1432 }
1433
1434 TopRPTracker.advance(RegOpers);
Andrew Trickb6e74712013-09-04 20:59:59 +00001435 assert(TopRPTracker.getPos() == CurrentTop && "out of sync");
Matthias Braun9198c672015-11-06 20:59:02 +00001436 DEBUG(
1437 dbgs() << "Top Pressure:\n";
1438 dumpRegSetPressure(TopRPTracker.getRegSetPressureAtPos(), TRI);
1439 );
1440
Andrew Trickb248b4a2013-09-06 17:32:47 +00001441 updateScheduledPressure(SU, TopRPTracker.getPressure().MaxSetPressure);
Andrew Trickb6e74712013-09-04 20:59:59 +00001442 }
Matthias Braunb550b762016-04-21 01:54:13 +00001443 } else {
Andrew Trick7a8e1002012-09-11 00:39:15 +00001444 assert(SU->isBottomReady() && "node still has unscheduled dependencies");
1445 MachineBasicBlock::iterator priorII =
1446 priorNonDebug(CurrentBottom, CurrentTop);
1447 if (&*priorII == MI)
1448 CurrentBottom = priorII;
1449 else {
1450 if (&*CurrentTop == MI) {
1451 CurrentTop = nextIfDebug(++CurrentTop, priorII);
1452 TopRPTracker.setPos(CurrentTop);
1453 }
1454 moveInstruction(MI, CurrentBottom);
1455 CurrentBottom = MI;
Yaxun Liu8b7454a2018-01-23 16:04:53 +00001456 BotRPTracker.setPos(CurrentBottom);
Andrew Trick7a8e1002012-09-11 00:39:15 +00001457 }
Andrew Trickb6e74712013-09-04 20:59:59 +00001458 if (ShouldTrackPressure) {
Matthias Braund4f64092016-01-20 00:23:32 +00001459 RegisterOperands RegOpers;
1460 RegOpers.collect(*MI, *TRI, MRI, ShouldTrackLaneMasks, false);
1461 if (ShouldTrackLaneMasks) {
1462 // Adjust liveness and add missing dead+read-undef flags.
Duncan P. N. Exon Smith3ac9cc62016-02-27 06:40:41 +00001463 SlotIndex SlotIdx = LIS->getInstructionIndex(*MI).getRegSlot();
Matthias Braund4f64092016-01-20 00:23:32 +00001464 RegOpers.adjustLaneLiveness(*LIS, MRI, SlotIdx, MI);
1465 } else {
1466 // Adjust for missing dead-def flags.
1467 RegOpers.detectDeadDefs(*MI, *LIS);
1468 }
1469
Yaxun Liuc41e2f62017-12-15 03:56:57 +00001470 if (BotRPTracker.getPos() != CurrentBottom)
1471 BotRPTracker.recedeSkipDebugValues();
Matthias Braun5d458612016-01-20 00:23:26 +00001472 SmallVector<RegisterMaskPair, 8> LiveUses;
Matthias Braund4f64092016-01-20 00:23:32 +00001473 BotRPTracker.recede(RegOpers, &LiveUses);
Andrew Trickb6e74712013-09-04 20:59:59 +00001474 assert(BotRPTracker.getPos() == CurrentBottom && "out of sync");
Matthias Braun9198c672015-11-06 20:59:02 +00001475 DEBUG(
1476 dbgs() << "Bottom Pressure:\n";
1477 dumpRegSetPressure(BotRPTracker.getRegSetPressureAtPos(), TRI);
1478 );
1479
Andrew Trickb248b4a2013-09-06 17:32:47 +00001480 updateScheduledPressure(SU, BotRPTracker.getPressure().MaxSetPressure);
Andrew Trickb6e74712013-09-04 20:59:59 +00001481 updatePressureDiffs(LiveUses);
Andrew Trickb6e74712013-09-04 20:59:59 +00001482 }
Andrew Trick7a8e1002012-09-11 00:39:15 +00001483 }
1484}
1485
Andrew Trick263280242012-11-12 19:52:20 +00001486//===----------------------------------------------------------------------===//
Jun Bum Lim4c5bd582016-04-15 14:58:38 +00001487// BaseMemOpClusterMutation - DAG post-processing to cluster loads or stores.
Andrew Trick263280242012-11-12 19:52:20 +00001488//===----------------------------------------------------------------------===//
1489
Andrew Tricka7714a02012-11-12 19:40:10 +00001490namespace {
Eugene Zelenkodb56e5a2017-02-22 22:32:51 +00001491
Andrew Tricka7714a02012-11-12 19:40:10 +00001492/// \brief Post-process the DAG to create cluster edges between neighboring
Jun Bum Lim4c5bd582016-04-15 14:58:38 +00001493/// loads or between neighboring stores.
1494class BaseMemOpClusterMutation : public ScheduleDAGMutation {
1495 struct MemOpInfo {
Andrew Tricka7714a02012-11-12 19:40:10 +00001496 SUnit *SU;
1497 unsigned BaseReg;
Chad Rosierc27a18f2016-03-09 16:00:35 +00001498 int64_t Offset;
Eugene Zelenkodb56e5a2017-02-22 22:32:51 +00001499
Jun Bum Lim4c5bd582016-04-15 14:58:38 +00001500 MemOpInfo(SUnit *su, unsigned reg, int64_t ofs)
1501 : SU(su), BaseReg(reg), Offset(ofs) {}
Benjamin Kramerb0f74b22014-03-07 21:35:39 +00001502
Jun Bum Lim4c5bd582016-04-15 14:58:38 +00001503 bool operator<(const MemOpInfo&RHS) const {
Mandeep Singh Grange82678a2016-10-18 00:11:19 +00001504 return std::tie(BaseReg, Offset, SU->NodeNum) <
1505 std::tie(RHS.BaseReg, RHS.Offset, RHS.SU->NodeNum);
Benjamin Kramerb0f74b22014-03-07 21:35:39 +00001506 }
Andrew Tricka7714a02012-11-12 19:40:10 +00001507 };
Andrew Tricka7714a02012-11-12 19:40:10 +00001508
1509 const TargetInstrInfo *TII;
1510 const TargetRegisterInfo *TRI;
Jun Bum Lim4c5bd582016-04-15 14:58:38 +00001511 bool IsLoad;
1512
Andrew Tricka7714a02012-11-12 19:40:10 +00001513public:
Jun Bum Lim4c5bd582016-04-15 14:58:38 +00001514 BaseMemOpClusterMutation(const TargetInstrInfo *tii,
1515 const TargetRegisterInfo *tri, bool IsLoad)
1516 : TII(tii), TRI(tri), IsLoad(IsLoad) {}
Andrew Tricka7714a02012-11-12 19:40:10 +00001517
Krzysztof Parzyszek5c61d112016-03-05 15:45:23 +00001518 void apply(ScheduleDAGInstrs *DAGInstrs) override;
Jun Bum Lim4c5bd582016-04-15 14:58:38 +00001519
Andrew Tricka7714a02012-11-12 19:40:10 +00001520protected:
Jun Bum Lim4c5bd582016-04-15 14:58:38 +00001521 void clusterNeighboringMemOps(ArrayRef<SUnit *> MemOps, ScheduleDAGMI *DAG);
1522};
1523
1524class StoreClusterMutation : public BaseMemOpClusterMutation {
1525public:
1526 StoreClusterMutation(const TargetInstrInfo *tii,
1527 const TargetRegisterInfo *tri)
1528 : BaseMemOpClusterMutation(tii, tri, false) {}
1529};
1530
1531class LoadClusterMutation : public BaseMemOpClusterMutation {
1532public:
1533 LoadClusterMutation(const TargetInstrInfo *tii, const TargetRegisterInfo *tri)
1534 : BaseMemOpClusterMutation(tii, tri, true) {}
Andrew Tricka7714a02012-11-12 19:40:10 +00001535};
Eugene Zelenkodb56e5a2017-02-22 22:32:51 +00001536
1537} // end anonymous namespace
Andrew Tricka7714a02012-11-12 19:40:10 +00001538
Tom Stellard68726a52016-08-19 19:59:18 +00001539namespace llvm {
1540
1541std::unique_ptr<ScheduleDAGMutation>
1542createLoadClusterDAGMutation(const TargetInstrInfo *TII,
1543 const TargetRegisterInfo *TRI) {
Eugene Zelenkodb56e5a2017-02-22 22:32:51 +00001544 return EnableMemOpCluster ? llvm::make_unique<LoadClusterMutation>(TII, TRI)
Matthias Braun115efcd2016-11-28 20:11:54 +00001545 : nullptr;
Tom Stellard68726a52016-08-19 19:59:18 +00001546}
1547
1548std::unique_ptr<ScheduleDAGMutation>
1549createStoreClusterDAGMutation(const TargetInstrInfo *TII,
1550 const TargetRegisterInfo *TRI) {
Eugene Zelenkodb56e5a2017-02-22 22:32:51 +00001551 return EnableMemOpCluster ? llvm::make_unique<StoreClusterMutation>(TII, TRI)
Matthias Braun115efcd2016-11-28 20:11:54 +00001552 : nullptr;
Tom Stellard68726a52016-08-19 19:59:18 +00001553}
1554
Eugene Zelenkodb56e5a2017-02-22 22:32:51 +00001555} // end namespace llvm
Tom Stellard68726a52016-08-19 19:59:18 +00001556
Jun Bum Lim4c5bd582016-04-15 14:58:38 +00001557void BaseMemOpClusterMutation::clusterNeighboringMemOps(
1558 ArrayRef<SUnit *> MemOps, ScheduleDAGMI *DAG) {
1559 SmallVector<MemOpInfo, 32> MemOpRecords;
Javed Absare3a0cc22017-06-21 09:10:10 +00001560 for (SUnit *SU : MemOps) {
Andrew Tricka7714a02012-11-12 19:40:10 +00001561 unsigned BaseReg;
Chad Rosierc27a18f2016-03-09 16:00:35 +00001562 int64_t Offset;
Duncan P. N. Exon Smith9cfc75c2016-06-30 00:01:54 +00001563 if (TII->getMemOpBaseRegImmOfs(*SU->getInstr(), BaseReg, Offset, TRI))
Jun Bum Lim4c5bd582016-04-15 14:58:38 +00001564 MemOpRecords.push_back(MemOpInfo(SU, BaseReg, Offset));
Andrew Tricka7714a02012-11-12 19:40:10 +00001565 }
Jun Bum Lim4c5bd582016-04-15 14:58:38 +00001566 if (MemOpRecords.size() < 2)
Andrew Tricka7714a02012-11-12 19:40:10 +00001567 return;
Jun Bum Lim4c5bd582016-04-15 14:58:38 +00001568
1569 std::sort(MemOpRecords.begin(), MemOpRecords.end());
Andrew Tricka7714a02012-11-12 19:40:10 +00001570 unsigned ClusterLength = 1;
Jun Bum Lim4c5bd582016-04-15 14:58:38 +00001571 for (unsigned Idx = 0, End = MemOpRecords.size(); Idx < (End - 1); ++Idx) {
Jun Bum Lim4c5bd582016-04-15 14:58:38 +00001572 SUnit *SUa = MemOpRecords[Idx].SU;
1573 SUnit *SUb = MemOpRecords[Idx+1].SU;
Stanislav Mekhanoshin7fe9a5d2017-09-13 22:20:47 +00001574 if (TII->shouldClusterMemOps(*SUa->getInstr(), MemOpRecords[Idx].BaseReg,
1575 *SUb->getInstr(), MemOpRecords[Idx+1].BaseReg,
Duncan P. N. Exon Smith9cfc75c2016-06-30 00:01:54 +00001576 ClusterLength) &&
1577 DAG->addEdge(SUb, SDep(SUa, SDep::Cluster))) {
Jun Bum Lim4c5bd582016-04-15 14:58:38 +00001578 DEBUG(dbgs() << "Cluster ld/st SU(" << SUa->NodeNum << ") - SU("
Andrew Tricka7714a02012-11-12 19:40:10 +00001579 << SUb->NodeNum << ")\n");
1580 // Copy successor edges from SUa to SUb. Interleaving computation
1581 // dependent on SUa can prevent load combining due to register reuse.
1582 // Predecessor edges do not need to be copied from SUb to SUa since nearby
1583 // loads should have effectively the same inputs.
Javed Absare3a0cc22017-06-21 09:10:10 +00001584 for (const SDep &Succ : SUa->Succs) {
1585 if (Succ.getSUnit() == SUb)
Andrew Tricka7714a02012-11-12 19:40:10 +00001586 continue;
Javed Absare3a0cc22017-06-21 09:10:10 +00001587 DEBUG(dbgs() << " Copy Succ SU(" << Succ.getSUnit()->NodeNum << ")\n");
1588 DAG->addEdge(Succ.getSUnit(), SDep(SUb, SDep::Artificial));
Andrew Tricka7714a02012-11-12 19:40:10 +00001589 }
1590 ++ClusterLength;
Matthias Braunb550b762016-04-21 01:54:13 +00001591 } else
Andrew Tricka7714a02012-11-12 19:40:10 +00001592 ClusterLength = 1;
1593 }
1594}
1595
1596/// \brief Callback from DAG postProcessing to create cluster edges for loads.
Jun Bum Lim4c5bd582016-04-15 14:58:38 +00001597void BaseMemOpClusterMutation::apply(ScheduleDAGInstrs *DAGInstrs) {
Krzysztof Parzyszek5c61d112016-03-05 15:45:23 +00001598 ScheduleDAGMI *DAG = static_cast<ScheduleDAGMI*>(DAGInstrs);
1599
Andrew Tricka7714a02012-11-12 19:40:10 +00001600 // Map DAG NodeNum to store chain ID.
1601 DenseMap<unsigned, unsigned> StoreChainIDs;
Jun Bum Lim4c5bd582016-04-15 14:58:38 +00001602 // Map each store chain to a set of dependent MemOps.
Andrew Tricka7714a02012-11-12 19:40:10 +00001603 SmallVector<SmallVector<SUnit*,4>, 32> StoreChainDependents;
Javed Absare3a0cc22017-06-21 09:10:10 +00001604 for (SUnit &SU : DAG->SUnits) {
1605 if ((IsLoad && !SU.getInstr()->mayLoad()) ||
1606 (!IsLoad && !SU.getInstr()->mayStore()))
Andrew Tricka7714a02012-11-12 19:40:10 +00001607 continue;
Jun Bum Lim4c5bd582016-04-15 14:58:38 +00001608
Andrew Tricka7714a02012-11-12 19:40:10 +00001609 unsigned ChainPredID = DAG->SUnits.size();
Javed Absare3a0cc22017-06-21 09:10:10 +00001610 for (const SDep &Pred : SU.Preds) {
1611 if (Pred.isCtrl()) {
1612 ChainPredID = Pred.getSUnit()->NodeNum;
Andrew Tricka7714a02012-11-12 19:40:10 +00001613 break;
1614 }
1615 }
1616 // Check if this chain-like pred has been seen
Jun Bum Lim4c5bd582016-04-15 14:58:38 +00001617 // before. ChainPredID==MaxNodeID at the top of the schedule.
Andrew Tricka7714a02012-11-12 19:40:10 +00001618 unsigned NumChains = StoreChainDependents.size();
1619 std::pair<DenseMap<unsigned, unsigned>::iterator, bool> Result =
1620 StoreChainIDs.insert(std::make_pair(ChainPredID, NumChains));
1621 if (Result.second)
1622 StoreChainDependents.resize(NumChains + 1);
Javed Absare3a0cc22017-06-21 09:10:10 +00001623 StoreChainDependents[Result.first->second].push_back(&SU);
Andrew Tricka7714a02012-11-12 19:40:10 +00001624 }
Jun Bum Lim4c5bd582016-04-15 14:58:38 +00001625
Andrew Tricka7714a02012-11-12 19:40:10 +00001626 // Iterate over the store chains.
Javed Absare3a0cc22017-06-21 09:10:10 +00001627 for (auto &SCD : StoreChainDependents)
1628 clusterNeighboringMemOps(SCD, DAG);
Andrew Tricka7714a02012-11-12 19:40:10 +00001629}
1630
Andrew Trick02a80da2012-03-08 01:41:12 +00001631//===----------------------------------------------------------------------===//
Andrew Trick85a1d4c2013-04-24 15:54:43 +00001632// CopyConstrain - DAG post-processing to encourage copy elimination.
1633//===----------------------------------------------------------------------===//
1634
1635namespace {
Eugene Zelenkodb56e5a2017-02-22 22:32:51 +00001636
Andrew Trick85a1d4c2013-04-24 15:54:43 +00001637/// \brief Post-process the DAG to create weak edges from all uses of a copy to
1638/// the one use that defines the copy's source vreg, most likely an induction
1639/// variable increment.
1640class CopyConstrain : public ScheduleDAGMutation {
1641 // Transient state.
1642 SlotIndex RegionBeginIdx;
Eugene Zelenko32a40562017-09-11 23:00:48 +00001643
Andrew Trick2e875172013-04-24 23:19:56 +00001644 // RegionEndIdx is the slot index of the last non-debug instruction in the
1645 // scheduling region. So we may have RegionBeginIdx == RegionEndIdx.
Andrew Trick85a1d4c2013-04-24 15:54:43 +00001646 SlotIndex RegionEndIdx;
Eugene Zelenkodb56e5a2017-02-22 22:32:51 +00001647
Andrew Trick85a1d4c2013-04-24 15:54:43 +00001648public:
1649 CopyConstrain(const TargetInstrInfo *, const TargetRegisterInfo *) {}
1650
Krzysztof Parzyszek5c61d112016-03-05 15:45:23 +00001651 void apply(ScheduleDAGInstrs *DAGInstrs) override;
Andrew Trick85a1d4c2013-04-24 15:54:43 +00001652
1653protected:
Andrew Trickd7f890e2013-12-28 21:56:47 +00001654 void constrainLocalCopy(SUnit *CopySU, ScheduleDAGMILive *DAG);
Andrew Trick85a1d4c2013-04-24 15:54:43 +00001655};
Eugene Zelenkodb56e5a2017-02-22 22:32:51 +00001656
1657} // end anonymous namespace
Andrew Trick85a1d4c2013-04-24 15:54:43 +00001658
Tom Stellard68726a52016-08-19 19:59:18 +00001659namespace llvm {
1660
1661std::unique_ptr<ScheduleDAGMutation>
1662createCopyConstrainDAGMutation(const TargetInstrInfo *TII,
Eugene Zelenkodb56e5a2017-02-22 22:32:51 +00001663 const TargetRegisterInfo *TRI) {
1664 return llvm::make_unique<CopyConstrain>(TII, TRI);
Tom Stellard68726a52016-08-19 19:59:18 +00001665}
1666
Eugene Zelenkodb56e5a2017-02-22 22:32:51 +00001667} // end namespace llvm
Tom Stellard68726a52016-08-19 19:59:18 +00001668
Andrew Trick85a1d4c2013-04-24 15:54:43 +00001669/// constrainLocalCopy handles two possibilities:
1670/// 1) Local src:
1671/// I0: = dst
1672/// I1: src = ...
1673/// I2: = dst
1674/// I3: dst = src (copy)
1675/// (create pred->succ edges I0->I1, I2->I1)
1676///
1677/// 2) Local copy:
1678/// I0: dst = src (copy)
1679/// I1: = dst
1680/// I2: src = ...
1681/// I3: = dst
1682/// (create pred->succ edges I1->I2, I3->I2)
1683///
1684/// Although the MachineScheduler is currently constrained to single blocks,
1685/// this algorithm should handle extended blocks. An EBB is a set of
1686/// contiguously numbered blocks such that the previous block in the EBB is
1687/// always the single predecessor.
Andrew Trickd7f890e2013-12-28 21:56:47 +00001688void CopyConstrain::constrainLocalCopy(SUnit *CopySU, ScheduleDAGMILive *DAG) {
Andrew Trick85a1d4c2013-04-24 15:54:43 +00001689 LiveIntervals *LIS = DAG->getLIS();
1690 MachineInstr *Copy = CopySU->getInstr();
1691
1692 // Check for pure vreg copies.
Matthias Braun7511abd2016-04-04 21:23:46 +00001693 const MachineOperand &SrcOp = Copy->getOperand(1);
1694 unsigned SrcReg = SrcOp.getReg();
1695 if (!TargetRegisterInfo::isVirtualRegister(SrcReg) || !SrcOp.readsReg())
Andrew Trick85a1d4c2013-04-24 15:54:43 +00001696 return;
1697
Matthias Braun7511abd2016-04-04 21:23:46 +00001698 const MachineOperand &DstOp = Copy->getOperand(0);
1699 unsigned DstReg = DstOp.getReg();
1700 if (!TargetRegisterInfo::isVirtualRegister(DstReg) || DstOp.isDead())
Andrew Trick85a1d4c2013-04-24 15:54:43 +00001701 return;
1702
1703 // Check if either the dest or source is local. If it's live across a back
1704 // edge, it's not local. Note that if both vregs are live across the back
1705 // edge, we cannot successfully contrain the copy without cyclic scheduling.
Michael Kuperstein54c61ed2015-01-19 07:30:47 +00001706 // If both the copy's source and dest are local live intervals, then we
1707 // should treat the dest as the global for the purpose of adding
1708 // constraints. This adds edges from source's other uses to the copy.
1709 unsigned LocalReg = SrcReg;
1710 unsigned GlobalReg = DstReg;
Andrew Trick85a1d4c2013-04-24 15:54:43 +00001711 LiveInterval *LocalLI = &LIS->getInterval(LocalReg);
1712 if (!LocalLI->isLocal(RegionBeginIdx, RegionEndIdx)) {
Michael Kuperstein54c61ed2015-01-19 07:30:47 +00001713 LocalReg = DstReg;
1714 GlobalReg = SrcReg;
Andrew Trick85a1d4c2013-04-24 15:54:43 +00001715 LocalLI = &LIS->getInterval(LocalReg);
1716 if (!LocalLI->isLocal(RegionBeginIdx, RegionEndIdx))
1717 return;
1718 }
1719 LiveInterval *GlobalLI = &LIS->getInterval(GlobalReg);
1720
1721 // Find the global segment after the start of the local LI.
1722 LiveInterval::iterator GlobalSegment = GlobalLI->find(LocalLI->beginIndex());
1723 // If GlobalLI does not overlap LocalLI->start, then a copy directly feeds a
1724 // local live range. We could create edges from other global uses to the local
1725 // start, but the coalescer should have already eliminated these cases, so
1726 // don't bother dealing with it.
1727 if (GlobalSegment == GlobalLI->end())
1728 return;
1729
1730 // If GlobalSegment is killed at the LocalLI->start, the call to find()
1731 // returned the next global segment. But if GlobalSegment overlaps with
1732 // LocalLI->start, then advance to the next segement. If a hole in GlobalLI
1733 // exists in LocalLI's vicinity, GlobalSegment will be the end of the hole.
1734 if (GlobalSegment->contains(LocalLI->beginIndex()))
1735 ++GlobalSegment;
1736
1737 if (GlobalSegment == GlobalLI->end())
1738 return;
1739
1740 // Check if GlobalLI contains a hole in the vicinity of LocalLI.
1741 if (GlobalSegment != GlobalLI->begin()) {
1742 // Two address defs have no hole.
Benjamin Kramerb6d0bd42014-03-02 12:27:27 +00001743 if (SlotIndex::isSameInstr(std::prev(GlobalSegment)->end,
Andrew Trick85a1d4c2013-04-24 15:54:43 +00001744 GlobalSegment->start)) {
1745 return;
1746 }
Andrew Trickd9761772013-07-30 19:59:08 +00001747 // If the prior global segment may be defined by the same two-address
1748 // instruction that also defines LocalLI, then can't make a hole here.
Benjamin Kramerb6d0bd42014-03-02 12:27:27 +00001749 if (SlotIndex::isSameInstr(std::prev(GlobalSegment)->start,
Andrew Trickd9761772013-07-30 19:59:08 +00001750 LocalLI->beginIndex())) {
1751 return;
1752 }
Andrew Trick85a1d4c2013-04-24 15:54:43 +00001753 // If GlobalLI has a prior segment, it must be live into the EBB. Otherwise
1754 // it would be a disconnected component in the live range.
Benjamin Kramerb6d0bd42014-03-02 12:27:27 +00001755 assert(std::prev(GlobalSegment)->start < LocalLI->beginIndex() &&
Andrew Trick85a1d4c2013-04-24 15:54:43 +00001756 "Disconnected LRG within the scheduling region.");
1757 }
1758 MachineInstr *GlobalDef = LIS->getInstructionFromIndex(GlobalSegment->start);
1759 if (!GlobalDef)
1760 return;
1761
1762 SUnit *GlobalSU = DAG->getSUnit(GlobalDef);
1763 if (!GlobalSU)
1764 return;
1765
1766 // GlobalDef is the bottom of the GlobalLI hole. Open the hole by
1767 // constraining the uses of the last local def to precede GlobalDef.
1768 SmallVector<SUnit*,8> LocalUses;
1769 const VNInfo *LastLocalVN = LocalLI->getVNInfoBefore(LocalLI->endIndex());
1770 MachineInstr *LastLocalDef = LIS->getInstructionFromIndex(LastLocalVN->def);
1771 SUnit *LastLocalSU = DAG->getSUnit(LastLocalDef);
Javed Absare3a0cc22017-06-21 09:10:10 +00001772 for (const SDep &Succ : LastLocalSU->Succs) {
1773 if (Succ.getKind() != SDep::Data || Succ.getReg() != LocalReg)
Andrew Trick85a1d4c2013-04-24 15:54:43 +00001774 continue;
Javed Absare3a0cc22017-06-21 09:10:10 +00001775 if (Succ.getSUnit() == GlobalSU)
Andrew Trick85a1d4c2013-04-24 15:54:43 +00001776 continue;
Javed Absare3a0cc22017-06-21 09:10:10 +00001777 if (!DAG->canAddEdge(GlobalSU, Succ.getSUnit()))
Andrew Trick85a1d4c2013-04-24 15:54:43 +00001778 return;
Javed Absare3a0cc22017-06-21 09:10:10 +00001779 LocalUses.push_back(Succ.getSUnit());
Andrew Trick85a1d4c2013-04-24 15:54:43 +00001780 }
1781 // Open the top of the GlobalLI hole by constraining any earlier global uses
1782 // to precede the start of LocalLI.
1783 SmallVector<SUnit*,8> GlobalUses;
1784 MachineInstr *FirstLocalDef =
1785 LIS->getInstructionFromIndex(LocalLI->beginIndex());
1786 SUnit *FirstLocalSU = DAG->getSUnit(FirstLocalDef);
Javed Absare3a0cc22017-06-21 09:10:10 +00001787 for (const SDep &Pred : GlobalSU->Preds) {
1788 if (Pred.getKind() != SDep::Anti || Pred.getReg() != GlobalReg)
Andrew Trick85a1d4c2013-04-24 15:54:43 +00001789 continue;
Javed Absare3a0cc22017-06-21 09:10:10 +00001790 if (Pred.getSUnit() == FirstLocalSU)
Andrew Trick85a1d4c2013-04-24 15:54:43 +00001791 continue;
Javed Absare3a0cc22017-06-21 09:10:10 +00001792 if (!DAG->canAddEdge(FirstLocalSU, Pred.getSUnit()))
Andrew Trick85a1d4c2013-04-24 15:54:43 +00001793 return;
Javed Absare3a0cc22017-06-21 09:10:10 +00001794 GlobalUses.push_back(Pred.getSUnit());
Andrew Trick85a1d4c2013-04-24 15:54:43 +00001795 }
1796 DEBUG(dbgs() << "Constraining copy SU(" << CopySU->NodeNum << ")\n");
1797 // Add the weak edges.
1798 for (SmallVectorImpl<SUnit*>::const_iterator
1799 I = LocalUses.begin(), E = LocalUses.end(); I != E; ++I) {
1800 DEBUG(dbgs() << " Local use SU(" << (*I)->NodeNum << ") -> SU("
1801 << GlobalSU->NodeNum << ")\n");
1802 DAG->addEdge(GlobalSU, SDep(*I, SDep::Weak));
1803 }
1804 for (SmallVectorImpl<SUnit*>::const_iterator
1805 I = GlobalUses.begin(), E = GlobalUses.end(); I != E; ++I) {
1806 DEBUG(dbgs() << " Global use SU(" << (*I)->NodeNum << ") -> SU("
1807 << FirstLocalSU->NodeNum << ")\n");
1808 DAG->addEdge(FirstLocalSU, SDep(*I, SDep::Weak));
1809 }
1810}
1811
1812/// \brief Callback from DAG postProcessing to create weak edges to encourage
1813/// copy elimination.
Krzysztof Parzyszek5c61d112016-03-05 15:45:23 +00001814void CopyConstrain::apply(ScheduleDAGInstrs *DAGInstrs) {
1815 ScheduleDAGMI *DAG = static_cast<ScheduleDAGMI*>(DAGInstrs);
Andrew Trickd7f890e2013-12-28 21:56:47 +00001816 assert(DAG->hasVRegLiveness() && "Expect VRegs with LiveIntervals");
1817
Andrew Trick2e875172013-04-24 23:19:56 +00001818 MachineBasicBlock::iterator FirstPos = nextIfDebug(DAG->begin(), DAG->end());
1819 if (FirstPos == DAG->end())
1820 return;
Duncan P. N. Exon Smith3ac9cc62016-02-27 06:40:41 +00001821 RegionBeginIdx = DAG->getLIS()->getInstructionIndex(*FirstPos);
Andrew Trick85a1d4c2013-04-24 15:54:43 +00001822 RegionEndIdx = DAG->getLIS()->getInstructionIndex(
Duncan P. N. Exon Smith3ac9cc62016-02-27 06:40:41 +00001823 *priorNonDebug(DAG->end(), DAG->begin()));
Andrew Trick85a1d4c2013-04-24 15:54:43 +00001824
Javed Absare3a0cc22017-06-21 09:10:10 +00001825 for (SUnit &SU : DAG->SUnits) {
1826 if (!SU.getInstr()->isCopy())
Andrew Trick85a1d4c2013-04-24 15:54:43 +00001827 continue;
1828
Javed Absare3a0cc22017-06-21 09:10:10 +00001829 constrainLocalCopy(&SU, static_cast<ScheduleDAGMILive*>(DAG));
Andrew Trick85a1d4c2013-04-24 15:54:43 +00001830 }
1831}
1832
1833//===----------------------------------------------------------------------===//
Andrew Trickfc127d12013-12-07 05:59:44 +00001834// MachineSchedStrategy helpers used by GenericScheduler, GenericPostScheduler
1835// and possibly other custom schedulers.
Andrew Trickd14d7c22013-12-28 21:56:57 +00001836//===----------------------------------------------------------------------===//
Andrew Tricke1c034f2012-01-17 06:55:03 +00001837
Andrew Trick5a22df42013-12-05 17:56:02 +00001838static const unsigned InvalidCycle = ~0U;
1839
Andrew Trickfc127d12013-12-07 05:59:44 +00001840SchedBoundary::~SchedBoundary() { delete HazardRec; }
Andrew Trick3ca33ac2012-11-07 07:05:09 +00001841
Jonas Paulsson238c14b2017-10-25 08:23:33 +00001842/// Given a Count of resource usage and a Latency value, return true if a
1843/// SchedBoundary becomes resource limited.
1844static bool checkResourceLimit(unsigned LFactor, unsigned Count,
1845 unsigned Latency) {
1846 return (int)(Count - (Latency * LFactor)) > (int)LFactor;
1847}
1848
Andrew Trickfc127d12013-12-07 05:59:44 +00001849void SchedBoundary::reset() {
1850 // A new HazardRec is created for each DAG and owned by SchedBoundary.
1851 // Destroying and reconstructing it is very expensive though. So keep
1852 // invalid, placeholder HazardRecs.
1853 if (HazardRec && HazardRec->isEnabled()) {
1854 delete HazardRec;
Craig Topperc0196b12014-04-14 00:51:57 +00001855 HazardRec = nullptr;
Andrew Trickfc127d12013-12-07 05:59:44 +00001856 }
1857 Available.clear();
1858 Pending.clear();
1859 CheckPending = false;
Andrew Trickfc127d12013-12-07 05:59:44 +00001860 CurrCycle = 0;
1861 CurrMOps = 0;
Eugene Zelenkodb56e5a2017-02-22 22:32:51 +00001862 MinReadyCycle = std::numeric_limits<unsigned>::max();
Andrew Trickfc127d12013-12-07 05:59:44 +00001863 ExpectedLatency = 0;
1864 DependentLatency = 0;
1865 RetiredMOps = 0;
1866 MaxExecutedResCount = 0;
1867 ZoneCritResIdx = 0;
1868 IsResourceLimited = false;
1869 ReservedCycles.clear();
Andrew Trick3ca33ac2012-11-07 07:05:09 +00001870#ifndef NDEBUG
Andrew Trickd14d7c22013-12-28 21:56:57 +00001871 // Track the maximum number of stall cycles that could arise either from the
1872 // latency of a DAG edge or the number of cycles that a processor resource is
1873 // reserved (SchedBoundary::ReservedCycles).
Andrew Trick7f1ebbe2014-06-07 01:48:43 +00001874 MaxObservedStall = 0;
Andrew Trick3ca33ac2012-11-07 07:05:09 +00001875#endif
Andrew Trickfc127d12013-12-07 05:59:44 +00001876 // Reserve a zero-count for invalid CritResIdx.
1877 ExecutedResCounts.resize(1);
1878 assert(!ExecutedResCounts[0] && "nonzero count for bad resource");
1879}
Andrew Trick3ca33ac2012-11-07 07:05:09 +00001880
Andrew Trickfc127d12013-12-07 05:59:44 +00001881void SchedRemainder::
Andrew Trick3ca33ac2012-11-07 07:05:09 +00001882init(ScheduleDAGMI *DAG, const TargetSchedModel *SchedModel) {
1883 reset();
1884 if (!SchedModel->hasInstrSchedModel())
1885 return;
1886 RemainingCounts.resize(SchedModel->getNumProcResourceKinds());
Javed Absare3a0cc22017-06-21 09:10:10 +00001887 for (SUnit &SU : DAG->SUnits) {
1888 const MCSchedClassDesc *SC = DAG->getSchedClass(&SU);
1889 RemIssueCount += SchedModel->getNumMicroOps(SU.getInstr(), SC)
Andrew Trickf78e7fa2013-06-15 05:39:19 +00001890 * SchedModel->getMicroOpFactor();
Andrew Trick3ca33ac2012-11-07 07:05:09 +00001891 for (TargetSchedModel::ProcResIter
1892 PI = SchedModel->getWriteProcResBegin(SC),
1893 PE = SchedModel->getWriteProcResEnd(SC); PI != PE; ++PI) {
1894 unsigned PIdx = PI->ProcResourceIdx;
1895 unsigned Factor = SchedModel->getResourceFactor(PIdx);
1896 RemainingCounts[PIdx] += (Factor * PI->Cycles);
1897 }
1898 }
1899}
1900
Andrew Trickfc127d12013-12-07 05:59:44 +00001901void SchedBoundary::
Andrew Trick3ca33ac2012-11-07 07:05:09 +00001902init(ScheduleDAGMI *dag, const TargetSchedModel *smodel, SchedRemainder *rem) {
1903 reset();
1904 DAG = dag;
1905 SchedModel = smodel;
1906 Rem = rem;
Andrew Trick5a22df42013-12-05 17:56:02 +00001907 if (SchedModel->hasInstrSchedModel()) {
Andrew Trickf78e7fa2013-06-15 05:39:19 +00001908 ExecutedResCounts.resize(SchedModel->getNumProcResourceKinds());
Andrew Trick5a22df42013-12-05 17:56:02 +00001909 ReservedCycles.resize(SchedModel->getNumProcResourceKinds(), InvalidCycle);
1910 }
Andrew Trick3ca33ac2012-11-07 07:05:09 +00001911}
1912
Andrew Trick880e5732013-12-05 17:55:58 +00001913/// Compute the stall cycles based on this SUnit's ready time. Heuristics treat
1914/// these "soft stalls" differently than the hard stall cycles based on CPU
1915/// resources and computed by checkHazard(). A fully in-order model
1916/// (MicroOpBufferSize==0) will not make use of this since instructions are not
1917/// available for scheduling until they are ready. However, a weaker in-order
1918/// model may use this for heuristics. For example, if a processor has in-order
1919/// behavior when reading certain resources, this may come into play.
Andrew Trickfc127d12013-12-07 05:59:44 +00001920unsigned SchedBoundary::getLatencyStallCycles(SUnit *SU) {
Andrew Trick880e5732013-12-05 17:55:58 +00001921 if (!SU->isUnbuffered)
1922 return 0;
1923
1924 unsigned ReadyCycle = (isTop() ? SU->TopReadyCycle : SU->BotReadyCycle);
1925 if (ReadyCycle > CurrCycle)
1926 return ReadyCycle - CurrCycle;
1927 return 0;
1928}
1929
Andrew Trick5a22df42013-12-05 17:56:02 +00001930/// Compute the next cycle at which the given processor resource can be
1931/// scheduled.
Andrew Trickfc127d12013-12-07 05:59:44 +00001932unsigned SchedBoundary::
Andrew Trick5a22df42013-12-05 17:56:02 +00001933getNextResourceCycle(unsigned PIdx, unsigned Cycles) {
1934 unsigned NextUnreserved = ReservedCycles[PIdx];
1935 // If this resource has never been used, always return cycle zero.
1936 if (NextUnreserved == InvalidCycle)
1937 return 0;
1938 // For bottom-up scheduling add the cycles needed for the current operation.
1939 if (!isTop())
1940 NextUnreserved += Cycles;
1941 return NextUnreserved;
1942}
1943
Andrew Trick8c9e6722012-06-29 03:23:24 +00001944/// Does this SU have a hazard within the current instruction group.
1945///
1946/// The scheduler supports two modes of hazard recognition. The first is the
1947/// ScheduleHazardRecognizer API. It is a fully general hazard recognizer that
1948/// supports highly complicated in-order reservation tables
1949/// (ScoreboardHazardRecognizer) and arbitraty target-specific logic.
1950///
1951/// The second is a streamlined mechanism that checks for hazards based on
1952/// simple counters that the scheduler itself maintains. It explicitly checks
1953/// for instruction dispatch limitations, including the number of micro-ops that
1954/// can dispatch per cycle.
1955///
1956/// TODO: Also check whether the SU must start a new group.
Andrew Trickfc127d12013-12-07 05:59:44 +00001957bool SchedBoundary::checkHazard(SUnit *SU) {
Andrew Trickd14d7c22013-12-28 21:56:57 +00001958 if (HazardRec->isEnabled()
1959 && HazardRec->getHazardType(SU) != ScheduleHazardRecognizer::NoHazard) {
1960 return true;
1961 }
Javed Absar3d594372017-03-27 20:46:37 +00001962
Andrew Trickdd79f0f2012-10-10 05:43:09 +00001963 unsigned uops = SchedModel->getNumMicroOps(SU->getInstr());
Andrew Tricke2ff5752013-06-15 04:49:49 +00001964 if ((CurrMOps > 0) && (CurrMOps + uops > SchedModel->getIssueWidth())) {
Andrew Trick3ca33ac2012-11-07 07:05:09 +00001965 DEBUG(dbgs() << " SU(" << SU->NodeNum << ") uops="
1966 << SchedModel->getNumMicroOps(SU->getInstr()) << '\n');
Andrew Trick8c9e6722012-06-29 03:23:24 +00001967 return true;
Andrew Trick3ca33ac2012-11-07 07:05:09 +00001968 }
Javed Absar3d594372017-03-27 20:46:37 +00001969
1970 if (CurrMOps > 0 &&
1971 ((isTop() && SchedModel->mustBeginGroup(SU->getInstr())) ||
1972 (!isTop() && SchedModel->mustEndGroup(SU->getInstr())))) {
1973 DEBUG(dbgs() << " hazard: SU(" << SU->NodeNum << ") must "
1974 << (isTop()? "begin" : "end") << " group\n");
1975 return true;
1976 }
1977
Andrew Trick5a22df42013-12-05 17:56:02 +00001978 if (SchedModel->hasInstrSchedModel() && SU->hasReservedResource) {
1979 const MCSchedClassDesc *SC = DAG->getSchedClass(SU);
Javed Absare485b142017-10-03 09:35:04 +00001980 for (const MCWriteProcResEntry &PE :
1981 make_range(SchedModel->getWriteProcResBegin(SC),
1982 SchedModel->getWriteProcResEnd(SC))) {
1983 unsigned ResIdx = PE.ProcResourceIdx;
1984 unsigned Cycles = PE.Cycles;
1985 unsigned NRCycle = getNextResourceCycle(ResIdx, Cycles);
Andrew Trick56327222014-06-27 04:57:05 +00001986 if (NRCycle > CurrCycle) {
Andrew Trick040c0da2014-06-27 05:09:36 +00001987#ifndef NDEBUG
Javed Absare485b142017-10-03 09:35:04 +00001988 MaxObservedStall = std::max(Cycles, MaxObservedStall);
Andrew Trick040c0da2014-06-27 05:09:36 +00001989#endif
Andrew Trick56327222014-06-27 04:57:05 +00001990 DEBUG(dbgs() << " SU(" << SU->NodeNum << ") "
Javed Absare485b142017-10-03 09:35:04 +00001991 << SchedModel->getResourceName(ResIdx)
Andrew Trick56327222014-06-27 04:57:05 +00001992 << "=" << NRCycle << "c\n");
Andrew Trick5a22df42013-12-05 17:56:02 +00001993 return true;
Andrew Trick56327222014-06-27 04:57:05 +00001994 }
Andrew Trick5a22df42013-12-05 17:56:02 +00001995 }
1996 }
Andrew Trick8c9e6722012-06-29 03:23:24 +00001997 return false;
1998}
1999
Andrew Trickf78e7fa2013-06-15 05:39:19 +00002000// Find the unscheduled node in ReadySUs with the highest latency.
Andrew Trickfc127d12013-12-07 05:59:44 +00002001unsigned SchedBoundary::
Andrew Trickf78e7fa2013-06-15 05:39:19 +00002002findMaxLatency(ArrayRef<SUnit*> ReadySUs) {
Craig Topperc0196b12014-04-14 00:51:57 +00002003 SUnit *LateSU = nullptr;
Andrew Trickf78e7fa2013-06-15 05:39:19 +00002004 unsigned RemLatency = 0;
Javed Absare3a0cc22017-06-21 09:10:10 +00002005 for (SUnit *SU : ReadySUs) {
2006 unsigned L = getUnscheduledLatency(SU);
Andrew Trickf5b8ef22013-06-15 04:49:44 +00002007 if (L > RemLatency) {
Andrew Trickd6d5ad32012-12-18 20:52:56 +00002008 RemLatency = L;
Javed Absare3a0cc22017-06-21 09:10:10 +00002009 LateSU = SU;
Andrew Trickf5b8ef22013-06-15 04:49:44 +00002010 }
Andrew Trickd6d5ad32012-12-18 20:52:56 +00002011 }
Andrew Trickf78e7fa2013-06-15 05:39:19 +00002012 if (LateSU) {
2013 DEBUG(dbgs() << Available.getName() << " RemLatency SU("
2014 << LateSU->NodeNum << ") " << RemLatency << "c\n");
Andrew Trickd6d5ad32012-12-18 20:52:56 +00002015 }
Andrew Trickf78e7fa2013-06-15 05:39:19 +00002016 return RemLatency;
2017}
Andrew Trickf5b8ef22013-06-15 04:49:44 +00002018
Andrew Trickf78e7fa2013-06-15 05:39:19 +00002019// Count resources in this zone and the remaining unscheduled
2020// instruction. Return the max count, scaled. Set OtherCritIdx to the critical
2021// resource index, or zero if the zone is issue limited.
Andrew Trickfc127d12013-12-07 05:59:44 +00002022unsigned SchedBoundary::
Andrew Trickf78e7fa2013-06-15 05:39:19 +00002023getOtherResourceCount(unsigned &OtherCritIdx) {
Alexey Samsonov64c391d2013-07-19 08:55:18 +00002024 OtherCritIdx = 0;
Andrew Trickf78e7fa2013-06-15 05:39:19 +00002025 if (!SchedModel->hasInstrSchedModel())
2026 return 0;
2027
2028 unsigned OtherCritCount = Rem->RemIssueCount
2029 + (RetiredMOps * SchedModel->getMicroOpFactor());
2030 DEBUG(dbgs() << " " << Available.getName() << " + Remain MOps: "
2031 << OtherCritCount / SchedModel->getMicroOpFactor() << '\n');
Andrew Trickf78e7fa2013-06-15 05:39:19 +00002032 for (unsigned PIdx = 1, PEnd = SchedModel->getNumProcResourceKinds();
2033 PIdx != PEnd; ++PIdx) {
2034 unsigned OtherCount = getResourceCount(PIdx) + Rem->RemainingCounts[PIdx];
2035 if (OtherCount > OtherCritCount) {
2036 OtherCritCount = OtherCount;
2037 OtherCritIdx = PIdx;
2038 }
Andrew Trick3ca33ac2012-11-07 07:05:09 +00002039 }
Andrew Trickf78e7fa2013-06-15 05:39:19 +00002040 if (OtherCritIdx) {
2041 DEBUG(dbgs() << " " << Available.getName() << " + Remain CritRes: "
2042 << OtherCritCount / SchedModel->getResourceFactor(OtherCritIdx)
Andrew Trickfc127d12013-12-07 05:59:44 +00002043 << " " << SchedModel->getResourceName(OtherCritIdx) << "\n");
Andrew Trickf78e7fa2013-06-15 05:39:19 +00002044 }
2045 return OtherCritCount;
2046}
2047
Andrew Trickfc127d12013-12-07 05:59:44 +00002048void SchedBoundary::releaseNode(SUnit *SU, unsigned ReadyCycle) {
Andrew Trick7f1ebbe2014-06-07 01:48:43 +00002049 assert(SU->getInstr() && "Scheduled SUnit must have instr");
2050
2051#ifndef NDEBUG
Andrew Trick491e34a2014-06-12 22:36:28 +00002052 // ReadyCycle was been bumped up to the CurrCycle when this node was
2053 // scheduled, but CurrCycle may have been eagerly advanced immediately after
2054 // scheduling, so may now be greater than ReadyCycle.
2055 if (ReadyCycle > CurrCycle)
2056 MaxObservedStall = std::max(ReadyCycle - CurrCycle, MaxObservedStall);
Andrew Trick7f1ebbe2014-06-07 01:48:43 +00002057#endif
2058
Andrew Trick61f1a272012-05-24 22:11:09 +00002059 if (ReadyCycle < MinReadyCycle)
2060 MinReadyCycle = ReadyCycle;
2061
2062 // Check for interlocks first. For the purpose of other heuristics, an
2063 // instruction that cannot issue appears as if it's not in the ReadyQueue.
Andrew Trickf78e7fa2013-06-15 05:39:19 +00002064 bool IsBuffered = SchedModel->getMicroOpBufferSize() != 0;
Matthias Braun6493bc22016-04-22 19:09:17 +00002065 if ((!IsBuffered && ReadyCycle > CurrCycle) || checkHazard(SU) ||
2066 Available.size() >= ReadyListLimit)
Andrew Trick61f1a272012-05-24 22:11:09 +00002067 Pending.push(SU);
2068 else
2069 Available.push(SU);
2070}
2071
2072/// Move the boundary of scheduled code by one cycle.
Andrew Trickfc127d12013-12-07 05:59:44 +00002073void SchedBoundary::bumpCycle(unsigned NextCycle) {
Andrew Trickf78e7fa2013-06-15 05:39:19 +00002074 if (SchedModel->getMicroOpBufferSize() == 0) {
Eugene Zelenkodb56e5a2017-02-22 22:32:51 +00002075 assert(MinReadyCycle < std::numeric_limits<unsigned>::max() &&
2076 "MinReadyCycle uninitialized");
Andrew Trickf78e7fa2013-06-15 05:39:19 +00002077 if (MinReadyCycle > NextCycle)
2078 NextCycle = MinReadyCycle;
Andrew Trick3ca33ac2012-11-07 07:05:09 +00002079 }
Andrew Trickf78e7fa2013-06-15 05:39:19 +00002080 // Update the current micro-ops, which will issue in the next cycle.
2081 unsigned DecMOps = SchedModel->getIssueWidth() * (NextCycle - CurrCycle);
2082 CurrMOps = (CurrMOps <= DecMOps) ? 0 : CurrMOps - DecMOps;
2083
2084 // Decrement DependentLatency based on the next cycle.
Andrew Trickf5b8ef22013-06-15 04:49:44 +00002085 if ((NextCycle - CurrCycle) > DependentLatency)
2086 DependentLatency = 0;
2087 else
2088 DependentLatency -= (NextCycle - CurrCycle);
Andrew Trick61f1a272012-05-24 22:11:09 +00002089
2090 if (!HazardRec->isEnabled()) {
Andrew Trick45446062012-06-05 21:11:27 +00002091 // Bypass HazardRec virtual calls.
Andrew Trick61f1a272012-05-24 22:11:09 +00002092 CurrCycle = NextCycle;
Matthias Braunb550b762016-04-21 01:54:13 +00002093 } else {
Andrew Trick45446062012-06-05 21:11:27 +00002094 // Bypass getHazardType calls in case of long latency.
Andrew Trick61f1a272012-05-24 22:11:09 +00002095 for (; CurrCycle != NextCycle; ++CurrCycle) {
2096 if (isTop())
2097 HazardRec->AdvanceCycle();
2098 else
2099 HazardRec->RecedeCycle();
2100 }
2101 }
2102 CheckPending = true;
Andrew Trickf78e7fa2013-06-15 05:39:19 +00002103 IsResourceLimited =
Jonas Paulsson238c14b2017-10-25 08:23:33 +00002104 checkResourceLimit(SchedModel->getLatencyFactor(), getCriticalCount(),
2105 getScheduledLatency());
Andrew Trick61f1a272012-05-24 22:11:09 +00002106
Andrew Trickf78e7fa2013-06-15 05:39:19 +00002107 DEBUG(dbgs() << "Cycle: " << CurrCycle << ' ' << Available.getName() << '\n');
2108}
2109
Andrew Trickfc127d12013-12-07 05:59:44 +00002110void SchedBoundary::incExecutedResources(unsigned PIdx, unsigned Count) {
Andrew Trickf78e7fa2013-06-15 05:39:19 +00002111 ExecutedResCounts[PIdx] += Count;
2112 if (ExecutedResCounts[PIdx] > MaxExecutedResCount)
2113 MaxExecutedResCount = ExecutedResCounts[PIdx];
Andrew Trick61f1a272012-05-24 22:11:09 +00002114}
2115
Andrew Trick3ca33ac2012-11-07 07:05:09 +00002116/// Add the given processor resource to this scheduled zone.
Andrew Trickf78e7fa2013-06-15 05:39:19 +00002117///
2118/// \param Cycles indicates the number of consecutive (non-pipelined) cycles
2119/// during which this resource is consumed.
2120///
2121/// \return the next cycle at which the instruction may execute without
2122/// oversubscribing resources.
Andrew Trickfc127d12013-12-07 05:59:44 +00002123unsigned SchedBoundary::
Andrew Trick5a22df42013-12-05 17:56:02 +00002124countResource(unsigned PIdx, unsigned Cycles, unsigned NextCycle) {
Andrew Trick3ca33ac2012-11-07 07:05:09 +00002125 unsigned Factor = SchedModel->getResourceFactor(PIdx);
Andrew Trick3ca33ac2012-11-07 07:05:09 +00002126 unsigned Count = Factor * Cycles;
Andrew Trickfc127d12013-12-07 05:59:44 +00002127 DEBUG(dbgs() << " " << SchedModel->getResourceName(PIdx)
Andrew Trickf78e7fa2013-06-15 05:39:19 +00002128 << " +" << Cycles << "x" << Factor << "u\n");
2129
2130 // Update Executed resources counts.
2131 incExecutedResources(PIdx, Count);
Andrew Trick3ca33ac2012-11-07 07:05:09 +00002132 assert(Rem->RemainingCounts[PIdx] >= Count && "resource double counted");
2133 Rem->RemainingCounts[PIdx] -= Count;
2134
Andrew Trickb13ef172013-07-19 00:20:07 +00002135 // Check if this resource exceeds the current critical resource. If so, it
2136 // becomes the critical resource.
2137 if (ZoneCritResIdx != PIdx && (getResourceCount(PIdx) > getCriticalCount())) {
Andrew Trickf78e7fa2013-06-15 05:39:19 +00002138 ZoneCritResIdx = PIdx;
Andrew Trick3ca33ac2012-11-07 07:05:09 +00002139 DEBUG(dbgs() << " *** Critical resource "
Andrew Trickfc127d12013-12-07 05:59:44 +00002140 << SchedModel->getResourceName(PIdx) << ": "
Andrew Trickf78e7fa2013-06-15 05:39:19 +00002141 << getResourceCount(PIdx) / SchedModel->getLatencyFactor() << "c\n");
Andrew Trick3ca33ac2012-11-07 07:05:09 +00002142 }
Andrew Trick5a22df42013-12-05 17:56:02 +00002143 // For reserved resources, record the highest cycle using the resource.
2144 unsigned NextAvailable = getNextResourceCycle(PIdx, Cycles);
2145 if (NextAvailable > CurrCycle) {
2146 DEBUG(dbgs() << " Resource conflict: "
2147 << SchedModel->getProcResource(PIdx)->Name << " reserved until @"
2148 << NextAvailable << "\n");
2149 }
2150 return NextAvailable;
Andrew Trick3ca33ac2012-11-07 07:05:09 +00002151}
2152
Andrew Trick45446062012-06-05 21:11:27 +00002153/// Move the boundary of scheduled code by one SUnit.
Andrew Trickfc127d12013-12-07 05:59:44 +00002154void SchedBoundary::bumpNode(SUnit *SU) {
Andrew Trick45446062012-06-05 21:11:27 +00002155 // Update the reservation table.
2156 if (HazardRec->isEnabled()) {
2157 if (!isTop() && SU->isCall) {
2158 // Calls are scheduled with their preceding instructions. For bottom-up
2159 // scheduling, clear the pipeline state before emitting.
2160 HazardRec->Reset();
2161 }
2162 HazardRec->EmitInstruction(SU);
2163 }
Andrew Trick5a22df42013-12-05 17:56:02 +00002164 // checkHazard should prevent scheduling multiple instructions per cycle that
2165 // exceed the issue width.
Andrew Trickf78e7fa2013-06-15 05:39:19 +00002166 const MCSchedClassDesc *SC = DAG->getSchedClass(SU);
2167 unsigned IncMOps = SchedModel->getNumMicroOps(SU->getInstr());
Daniel Jasper0d92abd2013-12-06 08:58:22 +00002168 assert(
2169 (CurrMOps == 0 || (CurrMOps + IncMOps) <= SchedModel->getIssueWidth()) &&
Andrew Trickf7760a22013-12-06 17:19:20 +00002170 "Cannot schedule this instruction's MicroOps in the current cycle.");
Andrew Trick5a22df42013-12-05 17:56:02 +00002171
Andrew Trickf78e7fa2013-06-15 05:39:19 +00002172 unsigned ReadyCycle = (isTop() ? SU->TopReadyCycle : SU->BotReadyCycle);
2173 DEBUG(dbgs() << " Ready @" << ReadyCycle << "c\n");
2174
Andrew Trick5a22df42013-12-05 17:56:02 +00002175 unsigned NextCycle = CurrCycle;
Andrew Trickf78e7fa2013-06-15 05:39:19 +00002176 switch (SchedModel->getMicroOpBufferSize()) {
2177 case 0:
2178 assert(ReadyCycle <= CurrCycle && "Broken PendingQueue");
2179 break;
2180 case 1:
2181 if (ReadyCycle > NextCycle) {
2182 NextCycle = ReadyCycle;
2183 DEBUG(dbgs() << " *** Stall until: " << ReadyCycle << "\n");
2184 }
2185 break;
2186 default:
2187 // We don't currently model the OOO reorder buffer, so consider all
Andrew Trick880e5732013-12-05 17:55:58 +00002188 // scheduled MOps to be "retired". We do loosely model in-order resource
2189 // latency. If this instruction uses an in-order resource, account for any
2190 // likely stall cycles.
2191 if (SU->isUnbuffered && ReadyCycle > NextCycle)
2192 NextCycle = ReadyCycle;
Andrew Trickf78e7fa2013-06-15 05:39:19 +00002193 break;
2194 }
2195 RetiredMOps += IncMOps;
2196
2197 // Update resource counts and critical resource.
2198 if (SchedModel->hasInstrSchedModel()) {
2199 unsigned DecRemIssue = IncMOps * SchedModel->getMicroOpFactor();
2200 assert(Rem->RemIssueCount >= DecRemIssue && "MOps double counted");
2201 Rem->RemIssueCount -= DecRemIssue;
2202 if (ZoneCritResIdx) {
2203 // Scale scheduled micro-ops for comparing with the critical resource.
2204 unsigned ScaledMOps =
2205 RetiredMOps * SchedModel->getMicroOpFactor();
2206
2207 // If scaled micro-ops are now more than the previous critical resource by
2208 // a full cycle, then micro-ops issue becomes critical.
2209 if ((int)(ScaledMOps - getResourceCount(ZoneCritResIdx))
2210 >= (int)SchedModel->getLatencyFactor()) {
2211 ZoneCritResIdx = 0;
2212 DEBUG(dbgs() << " *** Critical resource NumMicroOps: "
2213 << ScaledMOps / SchedModel->getLatencyFactor() << "c\n");
2214 }
2215 }
2216 for (TargetSchedModel::ProcResIter
2217 PI = SchedModel->getWriteProcResBegin(SC),
2218 PE = SchedModel->getWriteProcResEnd(SC); PI != PE; ++PI) {
2219 unsigned RCycle =
Andrew Trick5a22df42013-12-05 17:56:02 +00002220 countResource(PI->ProcResourceIdx, PI->Cycles, NextCycle);
Andrew Trickf78e7fa2013-06-15 05:39:19 +00002221 if (RCycle > NextCycle)
2222 NextCycle = RCycle;
2223 }
Andrew Trick5a22df42013-12-05 17:56:02 +00002224 if (SU->hasReservedResource) {
2225 // For reserved resources, record the highest cycle using the resource.
2226 // For top-down scheduling, this is the cycle in which we schedule this
2227 // instruction plus the number of cycles the operations reserves the
2228 // resource. For bottom-up is it simply the instruction's cycle.
2229 for (TargetSchedModel::ProcResIter
2230 PI = SchedModel->getWriteProcResBegin(SC),
2231 PE = SchedModel->getWriteProcResEnd(SC); PI != PE; ++PI) {
2232 unsigned PIdx = PI->ProcResourceIdx;
Andrew Trickd14d7c22013-12-28 21:56:57 +00002233 if (SchedModel->getProcResource(PIdx)->BufferSize == 0) {
Chad Rosieraba845e2014-07-02 16:46:08 +00002234 if (isTop()) {
2235 ReservedCycles[PIdx] =
2236 std::max(getNextResourceCycle(PIdx, 0), NextCycle + PI->Cycles);
2237 }
2238 else
2239 ReservedCycles[PIdx] = NextCycle;
Andrew Trickd14d7c22013-12-28 21:56:57 +00002240 }
Andrew Trick5a22df42013-12-05 17:56:02 +00002241 }
2242 }
Andrew Trickf78e7fa2013-06-15 05:39:19 +00002243 }
2244 // Update ExpectedLatency and DependentLatency.
2245 unsigned &TopLatency = isTop() ? ExpectedLatency : DependentLatency;
2246 unsigned &BotLatency = isTop() ? DependentLatency : ExpectedLatency;
2247 if (SU->getDepth() > TopLatency) {
2248 TopLatency = SU->getDepth();
2249 DEBUG(dbgs() << " " << Available.getName()
2250 << " TopLatency SU(" << SU->NodeNum << ") " << TopLatency << "c\n");
2251 }
2252 if (SU->getHeight() > BotLatency) {
2253 BotLatency = SU->getHeight();
2254 DEBUG(dbgs() << " " << Available.getName()
2255 << " BotLatency SU(" << SU->NodeNum << ") " << BotLatency << "c\n");
2256 }
2257 // If we stall for any reason, bump the cycle.
Jonas Paulsson238c14b2017-10-25 08:23:33 +00002258 if (NextCycle > CurrCycle)
Andrew Trickf78e7fa2013-06-15 05:39:19 +00002259 bumpCycle(NextCycle);
Jonas Paulsson238c14b2017-10-25 08:23:33 +00002260 else
Andrew Trickf78e7fa2013-06-15 05:39:19 +00002261 // After updating ZoneCritResIdx and ExpectedLatency, check if we're
Alp Tokercb402912014-01-24 17:20:08 +00002262 // resource limited. If a stall occurred, bumpCycle does this.
Andrew Trickf78e7fa2013-06-15 05:39:19 +00002263 IsResourceLimited =
Jonas Paulsson238c14b2017-10-25 08:23:33 +00002264 checkResourceLimit(SchedModel->getLatencyFactor(), getCriticalCount(),
2265 getScheduledLatency());
2266
Andrew Trick5a22df42013-12-05 17:56:02 +00002267 // Update CurrMOps after calling bumpCycle to handle stalls, since bumpCycle
2268 // resets CurrMOps. Loop to handle instructions with more MOps than issue in
2269 // one cycle. Since we commonly reach the max MOps here, opportunistically
2270 // bump the cycle to avoid uselessly checking everything in the readyQ.
2271 CurrMOps += IncMOps;
Javed Absar3d594372017-03-27 20:46:37 +00002272
2273 // Bump the cycle count for issue group constraints.
2274 // This must be done after NextCycle has been adjust for all other stalls.
2275 // Calling bumpCycle(X) will reduce CurrMOps by one issue group and set
2276 // currCycle to X.
2277 if ((isTop() && SchedModel->mustEndGroup(SU->getInstr())) ||
2278 (!isTop() && SchedModel->mustBeginGroup(SU->getInstr()))) {
2279 DEBUG(dbgs() << " Bump cycle to "
2280 << (isTop() ? "end" : "begin") << " group\n");
2281 bumpCycle(++NextCycle);
2282 }
2283
Andrew Trick5a22df42013-12-05 17:56:02 +00002284 while (CurrMOps >= SchedModel->getIssueWidth()) {
Andrew Trick5a22df42013-12-05 17:56:02 +00002285 DEBUG(dbgs() << " *** Max MOps " << CurrMOps
2286 << " at cycle " << CurrCycle << '\n');
Andrew Trickd14d7c22013-12-28 21:56:57 +00002287 bumpCycle(++NextCycle);
Andrew Trick5a22df42013-12-05 17:56:02 +00002288 }
Andrew Trickf78e7fa2013-06-15 05:39:19 +00002289 DEBUG(dumpScheduledState());
Andrew Trick45446062012-06-05 21:11:27 +00002290}
2291
Andrew Trick61f1a272012-05-24 22:11:09 +00002292/// Release pending ready nodes in to the available queue. This makes them
2293/// visible to heuristics.
Andrew Trickfc127d12013-12-07 05:59:44 +00002294void SchedBoundary::releasePending() {
Andrew Trick61f1a272012-05-24 22:11:09 +00002295 // If the available queue is empty, it is safe to reset MinReadyCycle.
2296 if (Available.empty())
Eugene Zelenkodb56e5a2017-02-22 22:32:51 +00002297 MinReadyCycle = std::numeric_limits<unsigned>::max();
Andrew Trick61f1a272012-05-24 22:11:09 +00002298
2299 // Check to see if any of the pending instructions are ready to issue. If
2300 // so, add them to the available queue.
Andrew Trickf78e7fa2013-06-15 05:39:19 +00002301 bool IsBuffered = SchedModel->getMicroOpBufferSize() != 0;
Andrew Trick61f1a272012-05-24 22:11:09 +00002302 for (unsigned i = 0, e = Pending.size(); i != e; ++i) {
2303 SUnit *SU = *(Pending.begin()+i);
Andrew Trick45446062012-06-05 21:11:27 +00002304 unsigned ReadyCycle = isTop() ? SU->TopReadyCycle : SU->BotReadyCycle;
Andrew Trick61f1a272012-05-24 22:11:09 +00002305
2306 if (ReadyCycle < MinReadyCycle)
2307 MinReadyCycle = ReadyCycle;
2308
Andrew Trickf78e7fa2013-06-15 05:39:19 +00002309 if (!IsBuffered && ReadyCycle > CurrCycle)
Andrew Trick61f1a272012-05-24 22:11:09 +00002310 continue;
2311
Andrew Trick8c9e6722012-06-29 03:23:24 +00002312 if (checkHazard(SU))
Andrew Trick61f1a272012-05-24 22:11:09 +00002313 continue;
2314
Matthias Braun6493bc22016-04-22 19:09:17 +00002315 if (Available.size() >= ReadyListLimit)
2316 break;
2317
Andrew Trick61f1a272012-05-24 22:11:09 +00002318 Available.push(SU);
2319 Pending.remove(Pending.begin()+i);
2320 --i; --e;
2321 }
2322 CheckPending = false;
2323}
2324
2325/// Remove SU from the ready set for this boundary.
Andrew Trickfc127d12013-12-07 05:59:44 +00002326void SchedBoundary::removeReady(SUnit *SU) {
Andrew Trick61f1a272012-05-24 22:11:09 +00002327 if (Available.isInQueue(SU))
2328 Available.remove(Available.find(SU));
2329 else {
2330 assert(Pending.isInQueue(SU) && "bad ready count");
2331 Pending.remove(Pending.find(SU));
2332 }
2333}
2334
2335/// If this queue only has one ready candidate, return it. As a side effect,
Andrew Trick3ca33ac2012-11-07 07:05:09 +00002336/// defer any nodes that now hit a hazard, and advance the cycle until at least
2337/// one node is ready. If multiple instructions are ready, return NULL.
Andrew Trickfc127d12013-12-07 05:59:44 +00002338SUnit *SchedBoundary::pickOnlyChoice() {
Andrew Trick61f1a272012-05-24 22:11:09 +00002339 if (CheckPending)
2340 releasePending();
2341
Andrew Tricke2ff5752013-06-15 04:49:49 +00002342 if (CurrMOps > 0) {
Andrew Trick3ca33ac2012-11-07 07:05:09 +00002343 // Defer any ready instrs that now have a hazard.
2344 for (ReadyQueue::iterator I = Available.begin(); I != Available.end();) {
2345 if (checkHazard(*I)) {
2346 Pending.push(*I);
2347 I = Available.remove(I);
2348 continue;
2349 }
2350 ++I;
2351 }
2352 }
Andrew Trick61f1a272012-05-24 22:11:09 +00002353 for (unsigned i = 0; Available.empty(); ++i) {
Chad Rosieraba845e2014-07-02 16:46:08 +00002354// FIXME: Re-enable assert once PR20057 is resolved.
2355// assert(i <= (HazardRec->getMaxLookAhead() + MaxObservedStall) &&
2356// "permanent hazard");
2357 (void)i;
Andrew Trickf78e7fa2013-06-15 05:39:19 +00002358 bumpCycle(CurrCycle + 1);
Andrew Trick61f1a272012-05-24 22:11:09 +00002359 releasePending();
2360 }
Matthias Braund29d31e2016-06-23 21:27:38 +00002361
2362 DEBUG(Pending.dump());
2363 DEBUG(Available.dump());
2364
Andrew Trick61f1a272012-05-24 22:11:09 +00002365 if (Available.size() == 1)
2366 return *Available.begin();
Craig Topperc0196b12014-04-14 00:51:57 +00002367 return nullptr;
Andrew Trick61f1a272012-05-24 22:11:09 +00002368}
2369
Aaron Ballman615eb472017-10-15 14:32:27 +00002370#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
Andrew Trickf78e7fa2013-06-15 05:39:19 +00002371// This is useful information to dump after bumpNode.
2372// Note that the Queue contents are more useful before pickNodeFromQueue.
Sam Clegg705f7982017-06-21 22:19:17 +00002373LLVM_DUMP_METHOD void SchedBoundary::dumpScheduledState() const {
Andrew Trickf78e7fa2013-06-15 05:39:19 +00002374 unsigned ResFactor;
2375 unsigned ResCount;
2376 if (ZoneCritResIdx) {
2377 ResFactor = SchedModel->getResourceFactor(ZoneCritResIdx);
2378 ResCount = getResourceCount(ZoneCritResIdx);
Matthias Braunb550b762016-04-21 01:54:13 +00002379 } else {
Andrew Trickf78e7fa2013-06-15 05:39:19 +00002380 ResFactor = SchedModel->getMicroOpFactor();
Javed Absar1a77bcc2017-09-27 10:31:58 +00002381 ResCount = RetiredMOps * ResFactor;
Andrew Trick3ca33ac2012-11-07 07:05:09 +00002382 }
Andrew Trickf78e7fa2013-06-15 05:39:19 +00002383 unsigned LFactor = SchedModel->getLatencyFactor();
2384 dbgs() << Available.getName() << " @" << CurrCycle << "c\n"
2385 << " Retired: " << RetiredMOps;
2386 dbgs() << "\n Executed: " << getExecutedCount() / LFactor << "c";
2387 dbgs() << "\n Critical: " << ResCount / LFactor << "c, "
Andrew Trickfc127d12013-12-07 05:59:44 +00002388 << ResCount / ResFactor << " "
2389 << SchedModel->getResourceName(ZoneCritResIdx)
Andrew Trickf78e7fa2013-06-15 05:39:19 +00002390 << "\n ExpectedLatency: " << ExpectedLatency << "c\n"
2391 << (IsResourceLimited ? " - Resource" : " - Latency")
2392 << " limited.\n";
Andrew Trick3ca33ac2012-11-07 07:05:09 +00002393}
Andrew Trick8e8415f2013-06-15 05:46:47 +00002394#endif
Andrew Trick3ca33ac2012-11-07 07:05:09 +00002395
Andrew Trickfc127d12013-12-07 05:59:44 +00002396//===----------------------------------------------------------------------===//
Andrew Trickd14d7c22013-12-28 21:56:57 +00002397// GenericScheduler - Generic implementation of MachineSchedStrategy.
Andrew Trickfc127d12013-12-07 05:59:44 +00002398//===----------------------------------------------------------------------===//
2399
Andrew Trickd14d7c22013-12-28 21:56:57 +00002400void GenericSchedulerBase::SchedCandidate::
2401initResourceDelta(const ScheduleDAGMI *DAG,
2402 const TargetSchedModel *SchedModel) {
2403 if (!Policy.ReduceResIdx && !Policy.DemandResIdx)
2404 return;
2405
2406 const MCSchedClassDesc *SC = DAG->getSchedClass(SU);
2407 for (TargetSchedModel::ProcResIter
2408 PI = SchedModel->getWriteProcResBegin(SC),
2409 PE = SchedModel->getWriteProcResEnd(SC); PI != PE; ++PI) {
2410 if (PI->ProcResourceIdx == Policy.ReduceResIdx)
2411 ResDelta.CritResources += PI->Cycles;
2412 if (PI->ProcResourceIdx == Policy.DemandResIdx)
2413 ResDelta.DemandedResources += PI->Cycles;
2414 }
2415}
2416
2417/// Set the CandPolicy given a scheduling zone given the current resources and
2418/// latencies inside and outside the zone.
Matthias Braunb550b762016-04-21 01:54:13 +00002419void GenericSchedulerBase::setPolicy(CandPolicy &Policy, bool IsPostRA,
Andrew Trickd14d7c22013-12-28 21:56:57 +00002420 SchedBoundary &CurrZone,
2421 SchedBoundary *OtherZone) {
Eric Christopher572e03a2015-06-19 01:53:21 +00002422 // Apply preemptive heuristics based on the total latency and resources
Andrew Trickd14d7c22013-12-28 21:56:57 +00002423 // inside and outside this zone. Potential stalls should be considered before
2424 // following this policy.
2425
2426 // Compute remaining latency. We need this both to determine whether the
2427 // overall schedule has become latency-limited and whether the instructions
2428 // outside this zone are resource or latency limited.
2429 //
2430 // The "dependent" latency is updated incrementally during scheduling as the
2431 // max height/depth of scheduled nodes minus the cycles since it was
2432 // scheduled:
2433 // DLat = max (N.depth - (CurrCycle - N.ReadyCycle) for N in Zone
2434 //
2435 // The "independent" latency is the max ready queue depth:
2436 // ILat = max N.depth for N in Available|Pending
2437 //
2438 // RemainingLatency is the greater of independent and dependent latency.
2439 unsigned RemLatency = CurrZone.getDependentLatency();
2440 RemLatency = std::max(RemLatency,
2441 CurrZone.findMaxLatency(CurrZone.Available.elements()));
2442 RemLatency = std::max(RemLatency,
2443 CurrZone.findMaxLatency(CurrZone.Pending.elements()));
2444
2445 // Compute the critical resource outside the zone.
Andrew Trick7afe4812013-12-28 22:25:57 +00002446 unsigned OtherCritIdx = 0;
Andrew Trickd14d7c22013-12-28 21:56:57 +00002447 unsigned OtherCount =
2448 OtherZone ? OtherZone->getOtherResourceCount(OtherCritIdx) : 0;
2449
2450 bool OtherResLimited = false;
Jonas Paulsson238c14b2017-10-25 08:23:33 +00002451 if (SchedModel->hasInstrSchedModel())
2452 OtherResLimited = checkResourceLimit(SchedModel->getLatencyFactor(),
2453 OtherCount, RemLatency);
2454
Andrew Trickd14d7c22013-12-28 21:56:57 +00002455 // Schedule aggressively for latency in PostRA mode. We don't check for
2456 // acyclic latency during PostRA, and highly out-of-order processors will
2457 // skip PostRA scheduling.
2458 if (!OtherResLimited) {
2459 if (IsPostRA || (RemLatency + CurrZone.getCurrCycle() > Rem.CriticalPath)) {
2460 Policy.ReduceLatency |= true;
2461 DEBUG(dbgs() << " " << CurrZone.Available.getName()
2462 << " RemainingLatency " << RemLatency << " + "
2463 << CurrZone.getCurrCycle() << "c > CritPath "
2464 << Rem.CriticalPath << "\n");
2465 }
2466 }
2467 // If the same resource is limiting inside and outside the zone, do nothing.
2468 if (CurrZone.getZoneCritResIdx() == OtherCritIdx)
2469 return;
2470
2471 DEBUG(
2472 if (CurrZone.isResourceLimited()) {
2473 dbgs() << " " << CurrZone.Available.getName() << " ResourceLimited: "
2474 << SchedModel->getResourceName(CurrZone.getZoneCritResIdx())
2475 << "\n";
2476 }
2477 if (OtherResLimited)
2478 dbgs() << " RemainingLimit: "
2479 << SchedModel->getResourceName(OtherCritIdx) << "\n";
2480 if (!CurrZone.isResourceLimited() && !OtherResLimited)
2481 dbgs() << " Latency limited both directions.\n");
2482
2483 if (CurrZone.isResourceLimited() && !Policy.ReduceResIdx)
2484 Policy.ReduceResIdx = CurrZone.getZoneCritResIdx();
2485
2486 if (OtherResLimited)
2487 Policy.DemandResIdx = OtherCritIdx;
2488}
2489
2490#ifndef NDEBUG
2491const char *GenericSchedulerBase::getReasonStr(
2492 GenericSchedulerBase::CandReason Reason) {
2493 switch (Reason) {
2494 case NoCand: return "NOCAND ";
Matthias Braun49cb6e92016-05-27 22:14:26 +00002495 case Only1: return "ONLY1 ";
2496 case PhysRegCopy: return "PREG-COPY ";
Andrew Trickd14d7c22013-12-28 21:56:57 +00002497 case RegExcess: return "REG-EXCESS";
2498 case RegCritical: return "REG-CRIT ";
2499 case Stall: return "STALL ";
2500 case Cluster: return "CLUSTER ";
2501 case Weak: return "WEAK ";
2502 case RegMax: return "REG-MAX ";
2503 case ResourceReduce: return "RES-REDUCE";
2504 case ResourceDemand: return "RES-DEMAND";
2505 case TopDepthReduce: return "TOP-DEPTH ";
2506 case TopPathReduce: return "TOP-PATH ";
2507 case BotHeightReduce:return "BOT-HEIGHT";
2508 case BotPathReduce: return "BOT-PATH ";
2509 case NextDefUse: return "DEF-USE ";
2510 case NodeOrder: return "ORDER ";
2511 };
2512 llvm_unreachable("Unknown reason!");
2513}
2514
2515void GenericSchedulerBase::traceCandidate(const SchedCandidate &Cand) {
2516 PressureChange P;
2517 unsigned ResIdx = 0;
2518 unsigned Latency = 0;
2519 switch (Cand.Reason) {
2520 default:
2521 break;
2522 case RegExcess:
2523 P = Cand.RPDelta.Excess;
2524 break;
2525 case RegCritical:
2526 P = Cand.RPDelta.CriticalMax;
2527 break;
2528 case RegMax:
2529 P = Cand.RPDelta.CurrentMax;
2530 break;
2531 case ResourceReduce:
2532 ResIdx = Cand.Policy.ReduceResIdx;
2533 break;
2534 case ResourceDemand:
2535 ResIdx = Cand.Policy.DemandResIdx;
2536 break;
2537 case TopDepthReduce:
2538 Latency = Cand.SU->getDepth();
2539 break;
2540 case TopPathReduce:
2541 Latency = Cand.SU->getHeight();
2542 break;
2543 case BotHeightReduce:
2544 Latency = Cand.SU->getHeight();
2545 break;
2546 case BotPathReduce:
2547 Latency = Cand.SU->getDepth();
2548 break;
2549 }
James Y Knighte72b0db2015-09-18 18:52:20 +00002550 dbgs() << " Cand SU(" << Cand.SU->NodeNum << ") " << getReasonStr(Cand.Reason);
Andrew Trickd14d7c22013-12-28 21:56:57 +00002551 if (P.isValid())
2552 dbgs() << " " << TRI->getRegPressureSetName(P.getPSet())
2553 << ":" << P.getUnitInc() << " ";
2554 else
2555 dbgs() << " ";
2556 if (ResIdx)
2557 dbgs() << " " << SchedModel->getProcResource(ResIdx)->Name << " ";
2558 else
2559 dbgs() << " ";
2560 if (Latency)
2561 dbgs() << " " << Latency << " cycles ";
2562 else
2563 dbgs() << " ";
2564 dbgs() << '\n';
2565}
2566#endif
2567
2568/// Return true if this heuristic determines order.
2569static bool tryLess(int TryVal, int CandVal,
2570 GenericSchedulerBase::SchedCandidate &TryCand,
2571 GenericSchedulerBase::SchedCandidate &Cand,
2572 GenericSchedulerBase::CandReason Reason) {
2573 if (TryVal < CandVal) {
2574 TryCand.Reason = Reason;
2575 return true;
2576 }
2577 if (TryVal > CandVal) {
2578 if (Cand.Reason > Reason)
2579 Cand.Reason = Reason;
2580 return true;
2581 }
Andrew Trickd14d7c22013-12-28 21:56:57 +00002582 return false;
2583}
2584
2585static bool tryGreater(int TryVal, int CandVal,
2586 GenericSchedulerBase::SchedCandidate &TryCand,
2587 GenericSchedulerBase::SchedCandidate &Cand,
2588 GenericSchedulerBase::CandReason Reason) {
2589 if (TryVal > CandVal) {
2590 TryCand.Reason = Reason;
2591 return true;
2592 }
2593 if (TryVal < CandVal) {
2594 if (Cand.Reason > Reason)
2595 Cand.Reason = Reason;
2596 return true;
2597 }
Andrew Trickd14d7c22013-12-28 21:56:57 +00002598 return false;
2599}
2600
2601static bool tryLatency(GenericSchedulerBase::SchedCandidate &TryCand,
2602 GenericSchedulerBase::SchedCandidate &Cand,
2603 SchedBoundary &Zone) {
2604 if (Zone.isTop()) {
2605 if (Cand.SU->getDepth() > Zone.getScheduledLatency()) {
2606 if (tryLess(TryCand.SU->getDepth(), Cand.SU->getDepth(),
2607 TryCand, Cand, GenericSchedulerBase::TopDepthReduce))
2608 return true;
2609 }
2610 if (tryGreater(TryCand.SU->getHeight(), Cand.SU->getHeight(),
2611 TryCand, Cand, GenericSchedulerBase::TopPathReduce))
2612 return true;
Matthias Braunb550b762016-04-21 01:54:13 +00002613 } else {
Andrew Trickd14d7c22013-12-28 21:56:57 +00002614 if (Cand.SU->getHeight() > Zone.getScheduledLatency()) {
2615 if (tryLess(TryCand.SU->getHeight(), Cand.SU->getHeight(),
2616 TryCand, Cand, GenericSchedulerBase::BotHeightReduce))
2617 return true;
2618 }
2619 if (tryGreater(TryCand.SU->getDepth(), Cand.SU->getDepth(),
2620 TryCand, Cand, GenericSchedulerBase::BotPathReduce))
2621 return true;
2622 }
2623 return false;
2624}
2625
Matthias Braun49cb6e92016-05-27 22:14:26 +00002626static void tracePick(GenericSchedulerBase::CandReason Reason, bool IsTop) {
2627 DEBUG(dbgs() << "Pick " << (IsTop ? "Top " : "Bot ")
2628 << GenericSchedulerBase::getReasonStr(Reason) << '\n');
2629}
2630
Matthias Braun6ad3d052016-06-25 00:23:00 +00002631static void tracePick(const GenericSchedulerBase::SchedCandidate &Cand) {
2632 tracePick(Cand.Reason, Cand.AtTop);
Andrew Trickd14d7c22013-12-28 21:56:57 +00002633}
2634
Andrew Trickfc127d12013-12-07 05:59:44 +00002635void GenericScheduler::initialize(ScheduleDAGMI *dag) {
Andrew Trickd7f890e2013-12-28 21:56:47 +00002636 assert(dag->hasVRegLiveness() &&
2637 "(PreRA)GenericScheduler needs vreg liveness");
2638 DAG = static_cast<ScheduleDAGMILive*>(dag);
Andrew Trickfc127d12013-12-07 05:59:44 +00002639 SchedModel = DAG->getSchedModel();
2640 TRI = DAG->TRI;
2641
2642 Rem.init(DAG, SchedModel);
2643 Top.init(DAG, SchedModel, &Rem);
2644 Bot.init(DAG, SchedModel, &Rem);
2645
2646 // Initialize resource counts.
2647
2648 // Initialize the HazardRecognizers. If itineraries don't exist, are empty, or
2649 // are disabled, then these HazardRecs will be disabled.
2650 const InstrItineraryData *Itin = SchedModel->getInstrItineraries();
Andrew Trickfc127d12013-12-07 05:59:44 +00002651 if (!Top.HazardRec) {
2652 Top.HazardRec =
Eric Christopher99556d72014-10-14 06:56:25 +00002653 DAG->MF.getSubtarget().getInstrInfo()->CreateTargetMIHazardRecognizer(
Eric Christopherd9134482014-08-04 21:25:23 +00002654 Itin, DAG);
Andrew Trickfc127d12013-12-07 05:59:44 +00002655 }
2656 if (!Bot.HazardRec) {
2657 Bot.HazardRec =
Eric Christopher99556d72014-10-14 06:56:25 +00002658 DAG->MF.getSubtarget().getInstrInfo()->CreateTargetMIHazardRecognizer(
Eric Christopherd9134482014-08-04 21:25:23 +00002659 Itin, DAG);
Andrew Trickfc127d12013-12-07 05:59:44 +00002660 }
Matthias Brauncc676c42016-06-25 02:03:36 +00002661 TopCand.SU = nullptr;
2662 BotCand.SU = nullptr;
Andrew Trickfc127d12013-12-07 05:59:44 +00002663}
2664
2665/// Initialize the per-region scheduling policy.
2666void GenericScheduler::initPolicy(MachineBasicBlock::iterator Begin,
2667 MachineBasicBlock::iterator End,
2668 unsigned NumRegionInstrs) {
Justin Bognerfdf9bf42017-10-10 23:50:49 +00002669 const MachineFunction &MF = *Begin->getMF();
Eric Christopher99556d72014-10-14 06:56:25 +00002670 const TargetLowering *TLI = MF.getSubtarget().getTargetLowering();
Andrew Trickfc127d12013-12-07 05:59:44 +00002671
2672 // Avoid setting up the register pressure tracker for small regions to save
2673 // compile time. As a rough heuristic, only track pressure when the number of
2674 // schedulable instructions exceeds half the integer register file.
Andrew Trick350ff2c2014-01-21 21:27:37 +00002675 RegionPolicy.ShouldTrackPressure = true;
Andrew Trick46753512014-01-22 03:38:55 +00002676 for (unsigned VT = MVT::i32; VT > (unsigned)MVT::i1; --VT) {
2677 MVT::SimpleValueType LegalIntVT = (MVT::SimpleValueType)VT;
2678 if (TLI->isTypeLegal(LegalIntVT)) {
Andrew Trick350ff2c2014-01-21 21:27:37 +00002679 unsigned NIntRegs = Context->RegClassInfo->getNumAllocatableRegs(
Andrew Trick46753512014-01-22 03:38:55 +00002680 TLI->getRegClassFor(LegalIntVT));
Andrew Trick350ff2c2014-01-21 21:27:37 +00002681 RegionPolicy.ShouldTrackPressure = NumRegionInstrs > (NIntRegs / 2);
2682 }
2683 }
Andrew Trickfc127d12013-12-07 05:59:44 +00002684
2685 // For generic targets, we default to bottom-up, because it's simpler and more
2686 // compile-time optimizations have been implemented in that direction.
2687 RegionPolicy.OnlyBottomUp = true;
2688
2689 // Allow the subtarget to override default policy.
Duncan P. N. Exon Smith63298722016-07-01 00:23:27 +00002690 MF.getSubtarget().overrideSchedPolicy(RegionPolicy, NumRegionInstrs);
Andrew Trickfc127d12013-12-07 05:59:44 +00002691
2692 // After subtarget overrides, apply command line options.
2693 if (!EnableRegPressure)
2694 RegionPolicy.ShouldTrackPressure = false;
2695
2696 // Check -misched-topdown/bottomup can force or unforce scheduling direction.
2697 // e.g. -misched-bottomup=false allows scheduling in both directions.
2698 assert((!ForceTopDown || !ForceBottomUp) &&
2699 "-misched-topdown incompatible with -misched-bottomup");
2700 if (ForceBottomUp.getNumOccurrences() > 0) {
2701 RegionPolicy.OnlyBottomUp = ForceBottomUp;
2702 if (RegionPolicy.OnlyBottomUp)
2703 RegionPolicy.OnlyTopDown = false;
2704 }
2705 if (ForceTopDown.getNumOccurrences() > 0) {
2706 RegionPolicy.OnlyTopDown = ForceTopDown;
2707 if (RegionPolicy.OnlyTopDown)
2708 RegionPolicy.OnlyBottomUp = false;
2709 }
2710}
2711
Sam Clegg705f7982017-06-21 22:19:17 +00002712void GenericScheduler::dumpPolicy() const {
Matthias Braun8c209aa2017-01-28 02:02:38 +00002713 // Cannot completely remove virtual function even in release mode.
Aaron Ballman615eb472017-10-15 14:32:27 +00002714#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
James Y Knighte72b0db2015-09-18 18:52:20 +00002715 dbgs() << "GenericScheduler RegionPolicy: "
2716 << " ShouldTrackPressure=" << RegionPolicy.ShouldTrackPressure
2717 << " OnlyTopDown=" << RegionPolicy.OnlyTopDown
2718 << " OnlyBottomUp=" << RegionPolicy.OnlyBottomUp
2719 << "\n";
Matthias Braun8c209aa2017-01-28 02:02:38 +00002720#endif
James Y Knighte72b0db2015-09-18 18:52:20 +00002721}
2722
Andrew Trickfc127d12013-12-07 05:59:44 +00002723/// Set IsAcyclicLatencyLimited if the acyclic path is longer than the cyclic
2724/// critical path by more cycles than it takes to drain the instruction buffer.
2725/// We estimate an upper bounds on in-flight instructions as:
2726///
2727/// CyclesPerIteration = max( CyclicPath, Loop-Resource-Height )
2728/// InFlightIterations = AcyclicPath / CyclesPerIteration
2729/// InFlightResources = InFlightIterations * LoopResources
2730///
2731/// TODO: Check execution resources in addition to IssueCount.
2732void GenericScheduler::checkAcyclicLatency() {
2733 if (Rem.CyclicCritPath == 0 || Rem.CyclicCritPath >= Rem.CriticalPath)
2734 return;
2735
2736 // Scaled number of cycles per loop iteration.
2737 unsigned IterCount =
2738 std::max(Rem.CyclicCritPath * SchedModel->getLatencyFactor(),
2739 Rem.RemIssueCount);
2740 // Scaled acyclic critical path.
2741 unsigned AcyclicCount = Rem.CriticalPath * SchedModel->getLatencyFactor();
2742 // InFlightCount = (AcyclicPath / IterCycles) * InstrPerLoop
2743 unsigned InFlightCount =
2744 (AcyclicCount * Rem.RemIssueCount + IterCount-1) / IterCount;
2745 unsigned BufferLimit =
2746 SchedModel->getMicroOpBufferSize() * SchedModel->getMicroOpFactor();
2747
2748 Rem.IsAcyclicLatencyLimited = InFlightCount > BufferLimit;
2749
2750 DEBUG(dbgs() << "IssueCycles="
2751 << Rem.RemIssueCount / SchedModel->getLatencyFactor() << "c "
2752 << "IterCycles=" << IterCount / SchedModel->getLatencyFactor()
2753 << "c NumIters=" << (AcyclicCount + IterCount-1) / IterCount
2754 << " InFlight=" << InFlightCount / SchedModel->getMicroOpFactor()
2755 << "m BufferLim=" << SchedModel->getMicroOpBufferSize() << "m\n";
2756 if (Rem.IsAcyclicLatencyLimited)
2757 dbgs() << " ACYCLIC LATENCY LIMIT\n");
2758}
2759
2760void GenericScheduler::registerRoots() {
2761 Rem.CriticalPath = DAG->ExitSU.getDepth();
2762
2763 // Some roots may not feed into ExitSU. Check all of them in case.
Javed Absare3a0cc22017-06-21 09:10:10 +00002764 for (const SUnit *SU : Bot.Available) {
2765 if (SU->getDepth() > Rem.CriticalPath)
2766 Rem.CriticalPath = SU->getDepth();
Andrew Trickfc127d12013-12-07 05:59:44 +00002767 }
Gerolf Hoflehnerb5220dc2014-08-07 21:49:44 +00002768 DEBUG(dbgs() << "Critical Path(GS-RR ): " << Rem.CriticalPath << '\n');
2769 if (DumpCriticalPathLength) {
2770 errs() << "Critical Path(GS-RR ): " << Rem.CriticalPath << " \n";
2771 }
Andrew Trickfc127d12013-12-07 05:59:44 +00002772
Matthias Braun99551052017-04-12 18:09:05 +00002773 if (EnableCyclicPath && SchedModel->getMicroOpBufferSize() > 0) {
Andrew Trickfc127d12013-12-07 05:59:44 +00002774 Rem.CyclicCritPath = DAG->computeCyclicCriticalPath();
2775 checkAcyclicLatency();
2776 }
2777}
2778
Andrew Trick1a831342013-08-30 03:49:48 +00002779static bool tryPressure(const PressureChange &TryP,
2780 const PressureChange &CandP,
Andrew Trickd14d7c22013-12-28 21:56:57 +00002781 GenericSchedulerBase::SchedCandidate &TryCand,
2782 GenericSchedulerBase::SchedCandidate &Cand,
Tom Stellard5ce53062015-12-16 18:31:01 +00002783 GenericSchedulerBase::CandReason Reason,
2784 const TargetRegisterInfo *TRI,
2785 const MachineFunction &MF) {
Andrew Trickb1a45b62013-08-30 04:27:29 +00002786 // If one candidate decreases and the other increases, go with it.
2787 // Invalid candidates have UnitInc==0.
Hal Finkel7a87f8a2014-10-10 17:06:20 +00002788 if (tryGreater(TryP.getUnitInc() < 0, CandP.getUnitInc() < 0, TryCand, Cand,
2789 Reason)) {
Andrew Trickb1a45b62013-08-30 04:27:29 +00002790 return true;
2791 }
Matthias Braun6ad3d052016-06-25 00:23:00 +00002792 // Do not compare the magnitude of pressure changes between top and bottom
2793 // boundary.
2794 if (Cand.AtTop != TryCand.AtTop)
2795 return false;
2796
2797 // If both candidates affect the same set in the same boundary, go with the
2798 // smallest increase.
2799 unsigned TryPSet = TryP.getPSetOrMax();
2800 unsigned CandPSet = CandP.getPSetOrMax();
2801 if (TryPSet == CandPSet) {
2802 return tryLess(TryP.getUnitInc(), CandP.getUnitInc(), TryCand, Cand,
2803 Reason);
2804 }
Tom Stellard5ce53062015-12-16 18:31:01 +00002805
2806 int TryRank = TryP.isValid() ? TRI->getRegPressureSetScore(MF, TryPSet) :
2807 std::numeric_limits<int>::max();
2808
2809 int CandRank = CandP.isValid() ? TRI->getRegPressureSetScore(MF, CandPSet) :
2810 std::numeric_limits<int>::max();
2811
Andrew Trick401b6952013-07-25 07:26:35 +00002812 // If the candidates are decreasing pressure, reverse priority.
Andrew Trick1a831342013-08-30 03:49:48 +00002813 if (TryP.getUnitInc() < 0)
Andrew Trick401b6952013-07-25 07:26:35 +00002814 std::swap(TryRank, CandRank);
2815 return tryGreater(TryRank, CandRank, TryCand, Cand, Reason);
2816}
2817
Andrew Tricka7714a02012-11-12 19:40:10 +00002818static unsigned getWeakLeft(const SUnit *SU, bool isTop) {
2819 return (isTop) ? SU->WeakPredsLeft : SU->WeakSuccsLeft;
2820}
2821
Andrew Tricke833e1c2013-04-13 06:07:40 +00002822/// Minimize physical register live ranges. Regalloc wants them adjacent to
2823/// their physreg def/use.
2824///
2825/// FIXME: This is an unnecessary check on the critical path. Most are root/leaf
2826/// copies which can be prescheduled. The rest (e.g. x86 MUL) could be bundled
2827/// with the operation that produces or consumes the physreg. We'll do this when
2828/// regalloc has support for parallel copies.
2829static int biasPhysRegCopy(const SUnit *SU, bool isTop) {
2830 const MachineInstr *MI = SU->getInstr();
2831 if (!MI->isCopy())
2832 return 0;
2833
2834 unsigned ScheduledOper = isTop ? 1 : 0;
2835 unsigned UnscheduledOper = isTop ? 0 : 1;
2836 // If we have already scheduled the physreg produce/consumer, immediately
2837 // schedule the copy.
2838 if (TargetRegisterInfo::isPhysicalRegister(
2839 MI->getOperand(ScheduledOper).getReg()))
2840 return 1;
2841 // If the physreg is at the boundary, defer it. Otherwise schedule it
2842 // immediately to free the dependent. We can hoist the copy later.
2843 bool AtBoundary = isTop ? !SU->NumSuccsLeft : !SU->NumPredsLeft;
2844 if (TargetRegisterInfo::isPhysicalRegister(
2845 MI->getOperand(UnscheduledOper).getReg()))
2846 return AtBoundary ? -1 : 1;
2847 return 0;
2848}
2849
Matthias Braun4f573772016-04-22 19:10:15 +00002850void GenericScheduler::initCandidate(SchedCandidate &Cand, SUnit *SU,
2851 bool AtTop,
2852 const RegPressureTracker &RPTracker,
2853 RegPressureTracker &TempTracker) {
2854 Cand.SU = SU;
Matthias Braun6ad3d052016-06-25 00:23:00 +00002855 Cand.AtTop = AtTop;
Matthias Braun4f573772016-04-22 19:10:15 +00002856 if (DAG->isTrackingPressure()) {
2857 if (AtTop) {
2858 TempTracker.getMaxDownwardPressureDelta(
2859 Cand.SU->getInstr(),
2860 Cand.RPDelta,
2861 DAG->getRegionCriticalPSets(),
2862 DAG->getRegPressure().MaxSetPressure);
2863 } else {
2864 if (VerifyScheduling) {
2865 TempTracker.getMaxUpwardPressureDelta(
2866 Cand.SU->getInstr(),
2867 &DAG->getPressureDiff(Cand.SU),
2868 Cand.RPDelta,
2869 DAG->getRegionCriticalPSets(),
2870 DAG->getRegPressure().MaxSetPressure);
2871 } else {
2872 RPTracker.getUpwardPressureDelta(
2873 Cand.SU->getInstr(),
2874 DAG->getPressureDiff(Cand.SU),
2875 Cand.RPDelta,
2876 DAG->getRegionCriticalPSets(),
2877 DAG->getRegPressure().MaxSetPressure);
2878 }
2879 }
2880 }
2881 DEBUG(if (Cand.RPDelta.Excess.isValid())
2882 dbgs() << " Try SU(" << Cand.SU->NodeNum << ") "
2883 << TRI->getRegPressureSetName(Cand.RPDelta.Excess.getPSet())
2884 << ":" << Cand.RPDelta.Excess.getUnitInc() << "\n");
2885}
2886
Andrew Trick3ca33ac2012-11-07 07:05:09 +00002887/// Apply a set of heursitics to a new candidate. Heuristics are currently
2888/// hierarchical. This may be more efficient than a graduated cost model because
2889/// we don't need to evaluate all aspects of the model for each node in the
2890/// queue. But it's really done to make the heuristics easier to debug and
2891/// statistically analyze.
2892///
2893/// \param Cand provides the policy and current best candidate.
2894/// \param TryCand refers to the next SUnit candidate, otherwise uninitialized.
Matthias Braun6ad3d052016-06-25 00:23:00 +00002895/// \param Zone describes the scheduled zone that we are extending, or nullptr
2896// if Cand is from a different zone than TryCand.
Andrew Trick665d3ec2013-09-19 23:10:59 +00002897void GenericScheduler::tryCandidate(SchedCandidate &Cand,
Andrew Trickbb1247b2013-12-05 17:55:47 +00002898 SchedCandidate &TryCand,
Matthias Braun6ad3d052016-06-25 00:23:00 +00002899 SchedBoundary *Zone) {
Andrew Trick3ca33ac2012-11-07 07:05:09 +00002900 // Initialize the candidate if needed.
2901 if (!Cand.isValid()) {
2902 TryCand.Reason = NodeOrder;
2903 return;
2904 }
Andrew Tricke833e1c2013-04-13 06:07:40 +00002905
Matthias Braun6ad3d052016-06-25 00:23:00 +00002906 if (tryGreater(biasPhysRegCopy(TryCand.SU, TryCand.AtTop),
2907 biasPhysRegCopy(Cand.SU, Cand.AtTop),
Andrew Tricke833e1c2013-04-13 06:07:40 +00002908 TryCand, Cand, PhysRegCopy))
2909 return;
2910
Andrew Tricke02d5da2015-05-17 23:40:27 +00002911 // Avoid exceeding the target's limit.
Andrew Trick66c3dfb2013-09-04 21:00:11 +00002912 if (DAG->isTrackingPressure() && tryPressure(TryCand.RPDelta.Excess,
2913 Cand.RPDelta.Excess,
Tom Stellard5ce53062015-12-16 18:31:01 +00002914 TryCand, Cand, RegExcess, TRI,
2915 DAG->MF))
Andrew Trick3ca33ac2012-11-07 07:05:09 +00002916 return;
Andrew Trick3ca33ac2012-11-07 07:05:09 +00002917
2918 // Avoid increasing the max critical pressure in the scheduled region.
Andrew Trick66c3dfb2013-09-04 21:00:11 +00002919 if (DAG->isTrackingPressure() && tryPressure(TryCand.RPDelta.CriticalMax,
2920 Cand.RPDelta.CriticalMax,
Tom Stellard5ce53062015-12-16 18:31:01 +00002921 TryCand, Cand, RegCritical, TRI,
2922 DAG->MF))
Andrew Trick3ca33ac2012-11-07 07:05:09 +00002923 return;
Andrew Trick3ca33ac2012-11-07 07:05:09 +00002924
Matthias Braun6ad3d052016-06-25 00:23:00 +00002925 // We only compare a subset of features when comparing nodes between
2926 // Top and Bottom boundary. Some properties are simply incomparable, in many
2927 // other instances we should only override the other boundary if something
2928 // is a clear good pick on one boundary. Skip heuristics that are more
2929 // "tie-breaking" in nature.
2930 bool SameBoundary = Zone != nullptr;
2931 if (SameBoundary) {
2932 // For loops that are acyclic path limited, aggressively schedule for
Jonas Paulssonbaeb4022016-11-04 08:31:14 +00002933 // latency. Within an single cycle, whenever CurrMOps > 0, allow normal
2934 // heuristics to take precedence.
Matthias Braun6ad3d052016-06-25 00:23:00 +00002935 if (Rem.IsAcyclicLatencyLimited && !Zone->getCurrMOps() &&
2936 tryLatency(TryCand, Cand, *Zone))
2937 return;
Andrew Trickddffae92013-09-06 17:32:36 +00002938
Matthias Braun6ad3d052016-06-25 00:23:00 +00002939 // Prioritize instructions that read unbuffered resources by stall cycles.
2940 if (tryLess(Zone->getLatencyStallCycles(TryCand.SU),
2941 Zone->getLatencyStallCycles(Cand.SU), TryCand, Cand, Stall))
2942 return;
2943 }
Andrew Trick880e5732013-12-05 17:55:58 +00002944
Andrew Tricka7714a02012-11-12 19:40:10 +00002945 // Keep clustered nodes together to encourage downstream peephole
2946 // optimizations which may reduce resource requirements.
2947 //
2948 // This is a best effort to set things up for a post-RA pass. Optimizations
2949 // like generating loads of multiple registers should ideally be done within
2950 // the scheduler pass by combining the loads during DAG postprocessing.
Matthias Braun6ad3d052016-06-25 00:23:00 +00002951 const SUnit *CandNextClusterSU =
2952 Cand.AtTop ? DAG->getNextClusterSucc() : DAG->getNextClusterPred();
2953 const SUnit *TryCandNextClusterSU =
2954 TryCand.AtTop ? DAG->getNextClusterSucc() : DAG->getNextClusterPred();
2955 if (tryGreater(TryCand.SU == TryCandNextClusterSU,
2956 Cand.SU == CandNextClusterSU,
Andrew Tricka7714a02012-11-12 19:40:10 +00002957 TryCand, Cand, Cluster))
2958 return;
Andrew Trick85a1d4c2013-04-24 15:54:43 +00002959
Matthias Braun6ad3d052016-06-25 00:23:00 +00002960 if (SameBoundary) {
2961 // Weak edges are for clustering and other constraints.
2962 if (tryLess(getWeakLeft(TryCand.SU, TryCand.AtTop),
2963 getWeakLeft(Cand.SU, Cand.AtTop),
2964 TryCand, Cand, Weak))
2965 return;
Andrew Tricka7714a02012-11-12 19:40:10 +00002966 }
Matthias Braun6ad3d052016-06-25 00:23:00 +00002967
Andrew Trick71f08a32013-06-17 21:45:13 +00002968 // Avoid increasing the max pressure of the entire region.
Andrew Trick66c3dfb2013-09-04 21:00:11 +00002969 if (DAG->isTrackingPressure() && tryPressure(TryCand.RPDelta.CurrentMax,
2970 Cand.RPDelta.CurrentMax,
Tom Stellard5ce53062015-12-16 18:31:01 +00002971 TryCand, Cand, RegMax, TRI,
2972 DAG->MF))
Andrew Trick71f08a32013-06-17 21:45:13 +00002973 return;
2974
Matthias Braun6ad3d052016-06-25 00:23:00 +00002975 if (SameBoundary) {
2976 // Avoid critical resource consumption and balance the schedule.
2977 TryCand.initResourceDelta(DAG, SchedModel);
2978 if (tryLess(TryCand.ResDelta.CritResources, Cand.ResDelta.CritResources,
2979 TryCand, Cand, ResourceReduce))
2980 return;
2981 if (tryGreater(TryCand.ResDelta.DemandedResources,
2982 Cand.ResDelta.DemandedResources,
2983 TryCand, Cand, ResourceDemand))
2984 return;
Andrew Trick3ca33ac2012-11-07 07:05:09 +00002985
Matthias Braun6ad3d052016-06-25 00:23:00 +00002986 // Avoid serializing long latency dependence chains.
2987 // For acyclic path limited loops, latency was already checked above.
2988 if (!RegionPolicy.DisableLatencyHeuristic && TryCand.Policy.ReduceLatency &&
2989 !Rem.IsAcyclicLatencyLimited && tryLatency(TryCand, Cand, *Zone))
2990 return;
Andrew Trick3ca33ac2012-11-07 07:05:09 +00002991
Matthias Braun6ad3d052016-06-25 00:23:00 +00002992 // Fall through to original instruction order.
2993 if ((Zone->isTop() && TryCand.SU->NodeNum < Cand.SU->NodeNum)
2994 || (!Zone->isTop() && TryCand.SU->NodeNum > Cand.SU->NodeNum)) {
2995 TryCand.Reason = NodeOrder;
2996 }
Andrew Trick3ca33ac2012-11-07 07:05:09 +00002997 }
2998}
Andrew Trick419eae22012-05-10 21:06:19 +00002999
Andrew Trickc573cd92013-09-06 17:32:44 +00003000/// Pick the best candidate from the queue.
Andrew Trick7ee9de52012-05-10 21:06:16 +00003001///
3002/// TODO: getMaxPressureDelta results can be mostly cached for each SUnit during
3003/// DAG building. To adjust for the current scheduling location we need to
3004/// maintain the number of vreg uses remaining to be top-scheduled.
Andrew Trick665d3ec2013-09-19 23:10:59 +00003005void GenericScheduler::pickNodeFromQueue(SchedBoundary &Zone,
Matthias Braun6ad3d052016-06-25 00:23:00 +00003006 const CandPolicy &ZonePolicy,
Andrew Trickbb1247b2013-12-05 17:55:47 +00003007 const RegPressureTracker &RPTracker,
3008 SchedCandidate &Cand) {
Andrew Trick7ee9de52012-05-10 21:06:16 +00003009 // getMaxPressureDelta temporarily modifies the tracker.
3010 RegPressureTracker &TempTracker = const_cast<RegPressureTracker&>(RPTracker);
3011
Matthias Braund29d31e2016-06-23 21:27:38 +00003012 ReadyQueue &Q = Zone.Available;
Javed Absare3a0cc22017-06-21 09:10:10 +00003013 for (SUnit *SU : Q) {
Andrew Trick7ee9de52012-05-10 21:06:16 +00003014
Matthias Braun6ad3d052016-06-25 00:23:00 +00003015 SchedCandidate TryCand(ZonePolicy);
Javed Absare3a0cc22017-06-21 09:10:10 +00003016 initCandidate(TryCand, SU, Zone.isTop(), RPTracker, TempTracker);
Matthias Braun6ad3d052016-06-25 00:23:00 +00003017 // Pass SchedBoundary only when comparing nodes from the same boundary.
3018 SchedBoundary *ZoneArg = Cand.AtTop == TryCand.AtTop ? &Zone : nullptr;
3019 tryCandidate(Cand, TryCand, ZoneArg);
Andrew Trick3ca33ac2012-11-07 07:05:09 +00003020 if (TryCand.Reason != NoCand) {
3021 // Initialize resource delta if needed in case future heuristics query it.
3022 if (TryCand.ResDelta == SchedResourceDelta())
3023 TryCand.initResourceDelta(DAG, SchedModel);
3024 Cand.setBest(TryCand);
Andrew Trick419d4912013-04-05 00:31:29 +00003025 DEBUG(traceCandidate(Cand));
Andrew Trick22025772012-05-17 18:35:10 +00003026 }
Andrew Trick7ee9de52012-05-10 21:06:16 +00003027 }
Andrew Trick3ca33ac2012-11-07 07:05:09 +00003028}
3029
Andrew Trick22025772012-05-17 18:35:10 +00003030/// Pick the best candidate node from either the top or bottom queue.
Andrew Trick665d3ec2013-09-19 23:10:59 +00003031SUnit *GenericScheduler::pickNodeBidirectional(bool &IsTopNode) {
Andrew Trick22025772012-05-17 18:35:10 +00003032 // Schedule as far as possible in the direction of no choice. This is most
3033 // efficient, but also provides the best heuristics for CriticalPSets.
Andrew Trick61f1a272012-05-24 22:11:09 +00003034 if (SUnit *SU = Bot.pickOnlyChoice()) {
Andrew Trick22025772012-05-17 18:35:10 +00003035 IsTopNode = false;
Matthias Braun49cb6e92016-05-27 22:14:26 +00003036 tracePick(Only1, false);
Andrew Trick61f1a272012-05-24 22:11:09 +00003037 return SU;
Andrew Trick22025772012-05-17 18:35:10 +00003038 }
Andrew Trick61f1a272012-05-24 22:11:09 +00003039 if (SUnit *SU = Top.pickOnlyChoice()) {
Andrew Trick22025772012-05-17 18:35:10 +00003040 IsTopNode = true;
Matthias Braun49cb6e92016-05-27 22:14:26 +00003041 tracePick(Only1, true);
Andrew Trick61f1a272012-05-24 22:11:09 +00003042 return SU;
Andrew Trick22025772012-05-17 18:35:10 +00003043 }
Andrew Trickfc127d12013-12-07 05:59:44 +00003044 // Set the bottom-up policy based on the state of the current bottom zone and
3045 // the instructions outside the zone, including the top zone.
Matthias Braun6ad3d052016-06-25 00:23:00 +00003046 CandPolicy BotPolicy;
3047 setPolicy(BotPolicy, /*IsPostRA=*/false, Bot, &Top);
Andrew Trickfc127d12013-12-07 05:59:44 +00003048 // Set the top-down policy based on the state of the current top zone and
3049 // the instructions outside the zone, including the bottom zone.
Matthias Braun6ad3d052016-06-25 00:23:00 +00003050 CandPolicy TopPolicy;
3051 setPolicy(TopPolicy, /*IsPostRA=*/false, Top, &Bot);
Andrew Trick3ca33ac2012-11-07 07:05:09 +00003052
Matthias Brauncc676c42016-06-25 02:03:36 +00003053 // See if BotCand is still valid (because we previously scheduled from Top).
Matthias Braund29d31e2016-06-23 21:27:38 +00003054 DEBUG(dbgs() << "Picking from Bot:\n");
Matthias Brauncc676c42016-06-25 02:03:36 +00003055 if (!BotCand.isValid() || BotCand.SU->isScheduled ||
3056 BotCand.Policy != BotPolicy) {
3057 BotCand.reset(CandPolicy());
3058 pickNodeFromQueue(Bot, BotPolicy, DAG->getBotRPTracker(), BotCand);
3059 assert(BotCand.Reason != NoCand && "failed to find the first candidate");
3060 } else {
3061 DEBUG(traceCandidate(BotCand));
3062#ifndef NDEBUG
3063 if (VerifyScheduling) {
3064 SchedCandidate TCand;
3065 TCand.reset(CandPolicy());
3066 pickNodeFromQueue(Bot, BotPolicy, DAG->getBotRPTracker(), TCand);
3067 assert(TCand.SU == BotCand.SU &&
3068 "Last pick result should correspond to re-picking right now");
3069 }
3070#endif
3071 }
Andrew Trick22025772012-05-17 18:35:10 +00003072
Andrew Trick22025772012-05-17 18:35:10 +00003073 // Check if the top Q has a better candidate.
Matthias Braund29d31e2016-06-23 21:27:38 +00003074 DEBUG(dbgs() << "Picking from Top:\n");
Matthias Brauncc676c42016-06-25 02:03:36 +00003075 if (!TopCand.isValid() || TopCand.SU->isScheduled ||
3076 TopCand.Policy != TopPolicy) {
3077 TopCand.reset(CandPolicy());
3078 pickNodeFromQueue(Top, TopPolicy, DAG->getTopRPTracker(), TopCand);
3079 assert(TopCand.Reason != NoCand && "failed to find the first candidate");
3080 } else {
3081 DEBUG(traceCandidate(TopCand));
3082#ifndef NDEBUG
3083 if (VerifyScheduling) {
3084 SchedCandidate TCand;
3085 TCand.reset(CandPolicy());
3086 pickNodeFromQueue(Top, TopPolicy, DAG->getTopRPTracker(), TCand);
3087 assert(TCand.SU == TopCand.SU &&
3088 "Last pick result should correspond to re-picking right now");
3089 }
3090#endif
3091 }
3092
3093 // Pick best from BotCand and TopCand.
3094 assert(BotCand.isValid());
3095 assert(TopCand.isValid());
3096 SchedCandidate Cand = BotCand;
3097 TopCand.Reason = NoCand;
3098 tryCandidate(Cand, TopCand, nullptr);
3099 if (TopCand.Reason != NoCand) {
3100 Cand.setBest(TopCand);
3101 DEBUG(traceCandidate(Cand));
3102 }
Andrew Trick22025772012-05-17 18:35:10 +00003103
Matthias Braun6ad3d052016-06-25 00:23:00 +00003104 IsTopNode = Cand.AtTop;
3105 tracePick(Cand);
3106 return Cand.SU;
Andrew Trick22025772012-05-17 18:35:10 +00003107}
3108
3109/// Pick the best node to balance the schedule. Implements MachineSchedStrategy.
Andrew Trick665d3ec2013-09-19 23:10:59 +00003110SUnit *GenericScheduler::pickNode(bool &IsTopNode) {
Andrew Trick7ee9de52012-05-10 21:06:16 +00003111 if (DAG->top() == DAG->bottom()) {
Andrew Trick61f1a272012-05-24 22:11:09 +00003112 assert(Top.Available.empty() && Top.Pending.empty() &&
3113 Bot.Available.empty() && Bot.Pending.empty() && "ReadyQ garbage");
Craig Topperc0196b12014-04-14 00:51:57 +00003114 return nullptr;
Andrew Trick7ee9de52012-05-10 21:06:16 +00003115 }
Andrew Trick7ee9de52012-05-10 21:06:16 +00003116 SUnit *SU;
Andrew Trick984d98b2012-10-08 18:53:53 +00003117 do {
Andrew Trick75e411c2013-09-06 17:32:34 +00003118 if (RegionPolicy.OnlyTopDown) {
Andrew Trick984d98b2012-10-08 18:53:53 +00003119 SU = Top.pickOnlyChoice();
3120 if (!SU) {
Andrew Trick3ca33ac2012-11-07 07:05:09 +00003121 CandPolicy NoPolicy;
Matthias Brauncc676c42016-06-25 02:03:36 +00003122 TopCand.reset(NoPolicy);
Matthias Braun6ad3d052016-06-25 00:23:00 +00003123 pickNodeFromQueue(Top, NoPolicy, DAG->getTopRPTracker(), TopCand);
Andrew Trick1ab16d92013-09-04 21:00:13 +00003124 assert(TopCand.Reason != NoCand && "failed to find a candidate");
Matthias Braun6ad3d052016-06-25 00:23:00 +00003125 tracePick(TopCand);
Andrew Trick984d98b2012-10-08 18:53:53 +00003126 SU = TopCand.SU;
3127 }
3128 IsTopNode = true;
Matthias Braunb550b762016-04-21 01:54:13 +00003129 } else if (RegionPolicy.OnlyBottomUp) {
Andrew Trick984d98b2012-10-08 18:53:53 +00003130 SU = Bot.pickOnlyChoice();
3131 if (!SU) {
Andrew Trick3ca33ac2012-11-07 07:05:09 +00003132 CandPolicy NoPolicy;
Matthias Brauncc676c42016-06-25 02:03:36 +00003133 BotCand.reset(NoPolicy);
Matthias Braun6ad3d052016-06-25 00:23:00 +00003134 pickNodeFromQueue(Bot, NoPolicy, DAG->getBotRPTracker(), BotCand);
Andrew Trick1ab16d92013-09-04 21:00:13 +00003135 assert(BotCand.Reason != NoCand && "failed to find a candidate");
Matthias Braun6ad3d052016-06-25 00:23:00 +00003136 tracePick(BotCand);
Andrew Trick984d98b2012-10-08 18:53:53 +00003137 SU = BotCand.SU;
3138 }
3139 IsTopNode = false;
Matthias Braunb550b762016-04-21 01:54:13 +00003140 } else {
Andrew Trick3ca33ac2012-11-07 07:05:09 +00003141 SU = pickNodeBidirectional(IsTopNode);
Andrew Trick984d98b2012-10-08 18:53:53 +00003142 }
3143 } while (SU->isScheduled);
3144
Andrew Trick61f1a272012-05-24 22:11:09 +00003145 if (SU->isTopReady())
3146 Top.removeReady(SU);
3147 if (SU->isBottomReady())
3148 Bot.removeReady(SU);
Andrew Trick4e7f6a72012-05-25 02:02:39 +00003149
Andrew Trick1f0bb692013-04-13 06:07:49 +00003150 DEBUG(dbgs() << "Scheduling SU(" << SU->NodeNum << ") " << *SU->getInstr());
Andrew Trick7ee9de52012-05-10 21:06:16 +00003151 return SU;
3152}
3153
Andrew Trick665d3ec2013-09-19 23:10:59 +00003154void GenericScheduler::reschedulePhysRegCopies(SUnit *SU, bool isTop) {
Andrew Tricke833e1c2013-04-13 06:07:40 +00003155 MachineBasicBlock::iterator InsertPos = SU->getInstr();
3156 if (!isTop)
3157 ++InsertPos;
3158 SmallVectorImpl<SDep> &Deps = isTop ? SU->Preds : SU->Succs;
3159
3160 // Find already scheduled copies with a single physreg dependence and move
3161 // them just above the scheduled instruction.
Javed Absare3a0cc22017-06-21 09:10:10 +00003162 for (SDep &Dep : Deps) {
3163 if (Dep.getKind() != SDep::Data || !TRI->isPhysicalRegister(Dep.getReg()))
Andrew Tricke833e1c2013-04-13 06:07:40 +00003164 continue;
Javed Absare3a0cc22017-06-21 09:10:10 +00003165 SUnit *DepSU = Dep.getSUnit();
Andrew Tricke833e1c2013-04-13 06:07:40 +00003166 if (isTop ? DepSU->Succs.size() > 1 : DepSU->Preds.size() > 1)
3167 continue;
3168 MachineInstr *Copy = DepSU->getInstr();
3169 if (!Copy->isCopy())
3170 continue;
3171 DEBUG(dbgs() << " Rescheduling physreg copy ";
Javed Absare3a0cc22017-06-21 09:10:10 +00003172 Dep.getSUnit()->dump(DAG));
Andrew Tricke833e1c2013-04-13 06:07:40 +00003173 DAG->moveInstruction(Copy, InsertPos);
3174 }
3175}
3176
Andrew Trick61f1a272012-05-24 22:11:09 +00003177/// Update the scheduler's state after scheduling a node. This is the same node
Andrew Trickd14d7c22013-12-28 21:56:57 +00003178/// that was just returned by pickNode(). However, ScheduleDAGMILive needs to
3179/// update it's state based on the current cycle before MachineSchedStrategy
3180/// does.
Andrew Tricke833e1c2013-04-13 06:07:40 +00003181///
3182/// FIXME: Eventually, we may bundle physreg copies rather than rescheduling
3183/// them here. See comments in biasPhysRegCopy.
Andrew Trick665d3ec2013-09-19 23:10:59 +00003184void GenericScheduler::schedNode(SUnit *SU, bool IsTopNode) {
Andrew Trick45446062012-06-05 21:11:27 +00003185 if (IsTopNode) {
Andrew Trickfc127d12013-12-07 05:59:44 +00003186 SU->TopReadyCycle = std::max(SU->TopReadyCycle, Top.getCurrCycle());
Andrew Trickce27bb92012-06-29 03:23:22 +00003187 Top.bumpNode(SU);
Andrew Tricke833e1c2013-04-13 06:07:40 +00003188 if (SU->hasPhysRegUses)
3189 reschedulePhysRegCopies(SU, true);
Matthias Braunb550b762016-04-21 01:54:13 +00003190 } else {
Andrew Trickfc127d12013-12-07 05:59:44 +00003191 SU->BotReadyCycle = std::max(SU->BotReadyCycle, Bot.getCurrCycle());
Andrew Trickce27bb92012-06-29 03:23:22 +00003192 Bot.bumpNode(SU);
Andrew Tricke833e1c2013-04-13 06:07:40 +00003193 if (SU->hasPhysRegDefs)
3194 reschedulePhysRegCopies(SU, false);
Andrew Trick61f1a272012-05-24 22:11:09 +00003195 }
3196}
3197
Andrew Trick8823dec2012-03-14 04:00:41 +00003198/// Create the standard converging machine scheduler. This will be used as the
3199/// default scheduler if the target does not set a default.
Matthias Braun115efcd2016-11-28 20:11:54 +00003200ScheduleDAGMILive *llvm::createGenericSchedLive(MachineSchedContext *C) {
Eugene Zelenkodb56e5a2017-02-22 22:32:51 +00003201 ScheduleDAGMILive *DAG =
3202 new ScheduleDAGMILive(C, llvm::make_unique<GenericScheduler>(C));
Andrew Tricka7714a02012-11-12 19:40:10 +00003203 // Register DAG post-processors.
Andrew Trick85a1d4c2013-04-24 15:54:43 +00003204 //
3205 // FIXME: extend the mutation API to allow earlier mutations to instantiate
3206 // data and pass it to later mutations. Have a single mutation that gathers
3207 // the interesting nodes in one pass.
Tom Stellard68726a52016-08-19 19:59:18 +00003208 DAG->addMutation(createCopyConstrainDAGMutation(DAG->TII, DAG->TRI));
Andrew Tricka7714a02012-11-12 19:40:10 +00003209 return DAG;
Andrew Tricke1c034f2012-01-17 06:55:03 +00003210}
Andrew Trickd14d7c22013-12-28 21:56:57 +00003211
Matthias Braun115efcd2016-11-28 20:11:54 +00003212static ScheduleDAGInstrs *createConveringSched(MachineSchedContext *C) {
3213 return createGenericSchedLive(C);
3214}
3215
Andrew Tricke1c034f2012-01-17 06:55:03 +00003216static MachineSchedRegistry
Andrew Trick665d3ec2013-09-19 23:10:59 +00003217GenericSchedRegistry("converge", "Standard converging scheduler.",
Matthias Braun115efcd2016-11-28 20:11:54 +00003218 createConveringSched);
Andrew Trickd14d7c22013-12-28 21:56:57 +00003219
3220//===----------------------------------------------------------------------===//
3221// PostGenericScheduler - Generic PostRA implementation of MachineSchedStrategy.
3222//===----------------------------------------------------------------------===//
3223
Andrew Trick3ccf71d2014-06-04 07:06:18 +00003224void PostGenericScheduler::initialize(ScheduleDAGMI *Dag) {
3225 DAG = Dag;
3226 SchedModel = DAG->getSchedModel();
3227 TRI = DAG->TRI;
Andrew Trickd14d7c22013-12-28 21:56:57 +00003228
Andrew Trick3ccf71d2014-06-04 07:06:18 +00003229 Rem.init(DAG, SchedModel);
3230 Top.init(DAG, SchedModel, &Rem);
3231 BotRoots.clear();
Andrew Trickd14d7c22013-12-28 21:56:57 +00003232
Andrew Trick3ccf71d2014-06-04 07:06:18 +00003233 // Initialize the HazardRecognizers. If itineraries don't exist, are empty,
3234 // or are disabled, then these HazardRecs will be disabled.
3235 const InstrItineraryData *Itin = SchedModel->getInstrItineraries();
Andrew Trick3ccf71d2014-06-04 07:06:18 +00003236 if (!Top.HazardRec) {
3237 Top.HazardRec =
Eric Christopher99556d72014-10-14 06:56:25 +00003238 DAG->MF.getSubtarget().getInstrInfo()->CreateTargetMIHazardRecognizer(
Eric Christopherd9134482014-08-04 21:25:23 +00003239 Itin, DAG);
Andrew Trickd14d7c22013-12-28 21:56:57 +00003240 }
Andrew Trick3ccf71d2014-06-04 07:06:18 +00003241}
Andrew Trickd14d7c22013-12-28 21:56:57 +00003242
Andrew Trickd14d7c22013-12-28 21:56:57 +00003243void PostGenericScheduler::registerRoots() {
3244 Rem.CriticalPath = DAG->ExitSU.getDepth();
3245
3246 // Some roots may not feed into ExitSU. Check all of them in case.
Javed Absare3a0cc22017-06-21 09:10:10 +00003247 for (const SUnit *SU : BotRoots) {
3248 if (SU->getDepth() > Rem.CriticalPath)
3249 Rem.CriticalPath = SU->getDepth();
Andrew Trickd14d7c22013-12-28 21:56:57 +00003250 }
Gerolf Hoflehnerb5220dc2014-08-07 21:49:44 +00003251 DEBUG(dbgs() << "Critical Path: (PGS-RR) " << Rem.CriticalPath << '\n');
3252 if (DumpCriticalPathLength) {
3253 errs() << "Critical Path(PGS-RR ): " << Rem.CriticalPath << " \n";
3254 }
Andrew Trickd14d7c22013-12-28 21:56:57 +00003255}
3256
3257/// Apply a set of heursitics to a new candidate for PostRA scheduling.
3258///
3259/// \param Cand provides the policy and current best candidate.
3260/// \param TryCand refers to the next SUnit candidate, otherwise uninitialized.
3261void PostGenericScheduler::tryCandidate(SchedCandidate &Cand,
3262 SchedCandidate &TryCand) {
Andrew Trickd14d7c22013-12-28 21:56:57 +00003263 // Initialize the candidate if needed.
3264 if (!Cand.isValid()) {
3265 TryCand.Reason = NodeOrder;
3266 return;
3267 }
3268
3269 // Prioritize instructions that read unbuffered resources by stall cycles.
3270 if (tryLess(Top.getLatencyStallCycles(TryCand.SU),
3271 Top.getLatencyStallCycles(Cand.SU), TryCand, Cand, Stall))
3272 return;
3273
Florian Hahnabb42182017-05-23 09:33:34 +00003274 // Keep clustered nodes together.
3275 if (tryGreater(TryCand.SU == DAG->getNextClusterSucc(),
3276 Cand.SU == DAG->getNextClusterSucc(),
3277 TryCand, Cand, Cluster))
3278 return;
3279
Andrew Trickd14d7c22013-12-28 21:56:57 +00003280 // Avoid critical resource consumption and balance the schedule.
3281 if (tryLess(TryCand.ResDelta.CritResources, Cand.ResDelta.CritResources,
3282 TryCand, Cand, ResourceReduce))
3283 return;
3284 if (tryGreater(TryCand.ResDelta.DemandedResources,
3285 Cand.ResDelta.DemandedResources,
3286 TryCand, Cand, ResourceDemand))
3287 return;
3288
3289 // Avoid serializing long latency dependence chains.
3290 if (Cand.Policy.ReduceLatency && tryLatency(TryCand, Cand, Top)) {
3291 return;
3292 }
3293
3294 // Fall through to original instruction order.
3295 if (TryCand.SU->NodeNum < Cand.SU->NodeNum)
3296 TryCand.Reason = NodeOrder;
3297}
3298
3299void PostGenericScheduler::pickNodeFromQueue(SchedCandidate &Cand) {
3300 ReadyQueue &Q = Top.Available;
Javed Absare3a0cc22017-06-21 09:10:10 +00003301 for (SUnit *SU : Q) {
Andrew Trickd14d7c22013-12-28 21:56:57 +00003302 SchedCandidate TryCand(Cand.Policy);
Javed Absare3a0cc22017-06-21 09:10:10 +00003303 TryCand.SU = SU;
Matthias Braun6ad3d052016-06-25 00:23:00 +00003304 TryCand.AtTop = true;
Andrew Trickd14d7c22013-12-28 21:56:57 +00003305 TryCand.initResourceDelta(DAG, SchedModel);
3306 tryCandidate(Cand, TryCand);
3307 if (TryCand.Reason != NoCand) {
3308 Cand.setBest(TryCand);
3309 DEBUG(traceCandidate(Cand));
3310 }
3311 }
3312}
3313
3314/// Pick the next node to schedule.
3315SUnit *PostGenericScheduler::pickNode(bool &IsTopNode) {
3316 if (DAG->top() == DAG->bottom()) {
3317 assert(Top.Available.empty() && Top.Pending.empty() && "ReadyQ garbage");
Craig Topperc0196b12014-04-14 00:51:57 +00003318 return nullptr;
Andrew Trickd14d7c22013-12-28 21:56:57 +00003319 }
3320 SUnit *SU;
3321 do {
3322 SU = Top.pickOnlyChoice();
Matthias Braun49cb6e92016-05-27 22:14:26 +00003323 if (SU) {
3324 tracePick(Only1, true);
3325 } else {
Andrew Trickd14d7c22013-12-28 21:56:57 +00003326 CandPolicy NoPolicy;
3327 SchedCandidate TopCand(NoPolicy);
3328 // Set the top-down policy based on the state of the current top zone and
3329 // the instructions outside the zone, including the bottom zone.
Craig Topperc0196b12014-04-14 00:51:57 +00003330 setPolicy(TopCand.Policy, /*IsPostRA=*/true, Top, nullptr);
Andrew Trickd14d7c22013-12-28 21:56:57 +00003331 pickNodeFromQueue(TopCand);
3332 assert(TopCand.Reason != NoCand && "failed to find a candidate");
Matthias Braun6ad3d052016-06-25 00:23:00 +00003333 tracePick(TopCand);
Andrew Trickd14d7c22013-12-28 21:56:57 +00003334 SU = TopCand.SU;
3335 }
3336 } while (SU->isScheduled);
3337
3338 IsTopNode = true;
3339 Top.removeReady(SU);
3340
Francis Visoiu Mistrihd65438d2018-02-08 23:42:27 +00003341 DEBUG(dbgs() << "Scheduling SU(" << SU->NodeNum << ") " << *SU->getInstr()
3342 << '\n');
Andrew Trickd14d7c22013-12-28 21:56:57 +00003343 return SU;
3344}
3345
3346/// Called after ScheduleDAGMI has scheduled an instruction and updated
3347/// scheduled/remaining flags in the DAG nodes.
3348void PostGenericScheduler::schedNode(SUnit *SU, bool IsTopNode) {
3349 SU->TopReadyCycle = std::max(SU->TopReadyCycle, Top.getCurrCycle());
3350 Top.bumpNode(SU);
3351}
3352
Matthias Braun115efcd2016-11-28 20:11:54 +00003353ScheduleDAGMI *llvm::createGenericSchedPostRA(MachineSchedContext *C) {
Eugene Zelenkodb56e5a2017-02-22 22:32:51 +00003354 return new ScheduleDAGMI(C, llvm::make_unique<PostGenericScheduler>(C),
Jonas Paulsson28f29482016-11-09 09:59:27 +00003355 /*RemoveKillFlags=*/true);
Andrew Trickd14d7c22013-12-28 21:56:57 +00003356}
Andrew Tricke1c034f2012-01-17 06:55:03 +00003357
3358//===----------------------------------------------------------------------===//
Andrew Trick90f711d2012-10-15 18:02:27 +00003359// ILP Scheduler. Currently for experimental analysis of heuristics.
3360//===----------------------------------------------------------------------===//
3361
3362namespace {
Eugene Zelenkodb56e5a2017-02-22 22:32:51 +00003363
Andrew Trick90f711d2012-10-15 18:02:27 +00003364/// \brief Order nodes by the ILP metric.
3365struct ILPOrder {
Eugene Zelenkodb56e5a2017-02-22 22:32:51 +00003366 const SchedDFSResult *DFSResult = nullptr;
3367 const BitVector *ScheduledTrees = nullptr;
Andrew Trick90f711d2012-10-15 18:02:27 +00003368 bool MaximizeILP;
3369
Eugene Zelenkodb56e5a2017-02-22 22:32:51 +00003370 ILPOrder(bool MaxILP) : MaximizeILP(MaxILP) {}
Andrew Trick90f711d2012-10-15 18:02:27 +00003371
3372 /// \brief Apply a less-than relation on node priority.
Andrew Trick48d392e2012-11-28 05:13:28 +00003373 ///
3374 /// (Return true if A comes after B in the Q.)
Andrew Trick90f711d2012-10-15 18:02:27 +00003375 bool operator()(const SUnit *A, const SUnit *B) const {
Andrew Trick48d392e2012-11-28 05:13:28 +00003376 unsigned SchedTreeA = DFSResult->getSubtreeID(A);
3377 unsigned SchedTreeB = DFSResult->getSubtreeID(B);
3378 if (SchedTreeA != SchedTreeB) {
3379 // Unscheduled trees have lower priority.
3380 if (ScheduledTrees->test(SchedTreeA) != ScheduledTrees->test(SchedTreeB))
3381 return ScheduledTrees->test(SchedTreeB);
3382
3383 // Trees with shallower connections have have lower priority.
3384 if (DFSResult->getSubtreeLevel(SchedTreeA)
3385 != DFSResult->getSubtreeLevel(SchedTreeB)) {
3386 return DFSResult->getSubtreeLevel(SchedTreeA)
3387 < DFSResult->getSubtreeLevel(SchedTreeB);
3388 }
3389 }
Andrew Trick90f711d2012-10-15 18:02:27 +00003390 if (MaximizeILP)
Andrew Trick48d392e2012-11-28 05:13:28 +00003391 return DFSResult->getILP(A) < DFSResult->getILP(B);
Andrew Trick90f711d2012-10-15 18:02:27 +00003392 else
Andrew Trick48d392e2012-11-28 05:13:28 +00003393 return DFSResult->getILP(A) > DFSResult->getILP(B);
Andrew Trick90f711d2012-10-15 18:02:27 +00003394 }
3395};
3396
3397/// \brief Schedule based on the ILP metric.
3398class ILPScheduler : public MachineSchedStrategy {
Eugene Zelenkodb56e5a2017-02-22 22:32:51 +00003399 ScheduleDAGMILive *DAG = nullptr;
Andrew Trick90f711d2012-10-15 18:02:27 +00003400 ILPOrder Cmp;
3401
3402 std::vector<SUnit*> ReadyQ;
Eugene Zelenkodb56e5a2017-02-22 22:32:51 +00003403
Andrew Trick90f711d2012-10-15 18:02:27 +00003404public:
Eugene Zelenkodb56e5a2017-02-22 22:32:51 +00003405 ILPScheduler(bool MaximizeILP) : Cmp(MaximizeILP) {}
Andrew Trick90f711d2012-10-15 18:02:27 +00003406
Craig Topper4584cd52014-03-07 09:26:03 +00003407 void initialize(ScheduleDAGMI *dag) override {
Andrew Trickd7f890e2013-12-28 21:56:47 +00003408 assert(dag->hasVRegLiveness() && "ILPScheduler needs vreg liveness");
3409 DAG = static_cast<ScheduleDAGMILive*>(dag);
Andrew Tricke2c3f5c2013-01-25 06:33:57 +00003410 DAG->computeDFSResult();
Andrew Trick44f750a2013-01-25 04:01:04 +00003411 Cmp.DFSResult = DAG->getDFSResult();
3412 Cmp.ScheduledTrees = &DAG->getScheduledTrees();
Andrew Trick90f711d2012-10-15 18:02:27 +00003413 ReadyQ.clear();
Andrew Trick90f711d2012-10-15 18:02:27 +00003414 }
3415
Craig Topper4584cd52014-03-07 09:26:03 +00003416 void registerRoots() override {
Benjamin Krameraa598b32012-11-29 14:36:26 +00003417 // Restore the heap in ReadyQ with the updated DFS results.
3418 std::make_heap(ReadyQ.begin(), ReadyQ.end(), Cmp);
Andrew Trick90f711d2012-10-15 18:02:27 +00003419 }
3420
3421 /// Implement MachineSchedStrategy interface.
3422 /// -----------------------------------------
3423
Andrew Trick48d392e2012-11-28 05:13:28 +00003424 /// Callback to select the highest priority node from the ready Q.
Craig Topper4584cd52014-03-07 09:26:03 +00003425 SUnit *pickNode(bool &IsTopNode) override {
Craig Topperc0196b12014-04-14 00:51:57 +00003426 if (ReadyQ.empty()) return nullptr;
Matt Arsenault4ab769f2013-03-21 00:57:21 +00003427 std::pop_heap(ReadyQ.begin(), ReadyQ.end(), Cmp);
Andrew Trick90f711d2012-10-15 18:02:27 +00003428 SUnit *SU = ReadyQ.back();
3429 ReadyQ.pop_back();
3430 IsTopNode = false;
Andrew Trick1f0bb692013-04-13 06:07:49 +00003431 DEBUG(dbgs() << "Pick node " << "SU(" << SU->NodeNum << ") "
Andrew Trick44f750a2013-01-25 04:01:04 +00003432 << " ILP: " << DAG->getDFSResult()->getILP(SU)
3433 << " Tree: " << DAG->getDFSResult()->getSubtreeID(SU) << " @"
3434 << DAG->getDFSResult()->getSubtreeLevel(
Andrew Trick1f0bb692013-04-13 06:07:49 +00003435 DAG->getDFSResult()->getSubtreeID(SU)) << '\n'
3436 << "Scheduling " << *SU->getInstr());
Andrew Trick90f711d2012-10-15 18:02:27 +00003437 return SU;
3438 }
3439
Andrew Trick44f750a2013-01-25 04:01:04 +00003440 /// \brief Scheduler callback to notify that a new subtree is scheduled.
Craig Topper4584cd52014-03-07 09:26:03 +00003441 void scheduleTree(unsigned SubtreeID) override {
Andrew Trick44f750a2013-01-25 04:01:04 +00003442 std::make_heap(ReadyQ.begin(), ReadyQ.end(), Cmp);
3443 }
3444
Andrew Trick48d392e2012-11-28 05:13:28 +00003445 /// Callback after a node is scheduled. Mark a newly scheduled tree, notify
3446 /// DFSResults, and resort the priority Q.
Craig Topper4584cd52014-03-07 09:26:03 +00003447 void schedNode(SUnit *SU, bool IsTopNode) override {
Andrew Trick48d392e2012-11-28 05:13:28 +00003448 assert(!IsTopNode && "SchedDFSResult needs bottom-up");
Andrew Trick48d392e2012-11-28 05:13:28 +00003449 }
Andrew Trick90f711d2012-10-15 18:02:27 +00003450
Craig Topper4584cd52014-03-07 09:26:03 +00003451 void releaseTopNode(SUnit *) override { /*only called for top roots*/ }
Andrew Trick90f711d2012-10-15 18:02:27 +00003452
Craig Topper4584cd52014-03-07 09:26:03 +00003453 void releaseBottomNode(SUnit *SU) override {
Andrew Trick90f711d2012-10-15 18:02:27 +00003454 ReadyQ.push_back(SU);
3455 std::push_heap(ReadyQ.begin(), ReadyQ.end(), Cmp);
3456 }
3457};
Eugene Zelenkodb56e5a2017-02-22 22:32:51 +00003458
3459} // end anonymous namespace
Andrew Trick90f711d2012-10-15 18:02:27 +00003460
3461static ScheduleDAGInstrs *createILPMaxScheduler(MachineSchedContext *C) {
Eugene Zelenkodb56e5a2017-02-22 22:32:51 +00003462 return new ScheduleDAGMILive(C, llvm::make_unique<ILPScheduler>(true));
Andrew Trick90f711d2012-10-15 18:02:27 +00003463}
3464static ScheduleDAGInstrs *createILPMinScheduler(MachineSchedContext *C) {
Eugene Zelenkodb56e5a2017-02-22 22:32:51 +00003465 return new ScheduleDAGMILive(C, llvm::make_unique<ILPScheduler>(false));
Andrew Trick90f711d2012-10-15 18:02:27 +00003466}
Eugene Zelenkodb56e5a2017-02-22 22:32:51 +00003467
Andrew Trick90f711d2012-10-15 18:02:27 +00003468static MachineSchedRegistry ILPMaxRegistry(
3469 "ilpmax", "Schedule bottom-up for max ILP", createILPMaxScheduler);
3470static MachineSchedRegistry ILPMinRegistry(
3471 "ilpmin", "Schedule bottom-up for min ILP", createILPMinScheduler);
3472
3473//===----------------------------------------------------------------------===//
Andrew Trick63440872012-01-14 02:17:06 +00003474// Machine Instruction Shuffler for Correctness Testing
3475//===----------------------------------------------------------------------===//
3476
Andrew Tricke77e84e2012-01-13 06:30:30 +00003477#ifndef NDEBUG
3478namespace {
Eugene Zelenkodb56e5a2017-02-22 22:32:51 +00003479
Andrew Trick8823dec2012-03-14 04:00:41 +00003480/// Apply a less-than relation on the node order, which corresponds to the
3481/// instruction order prior to scheduling. IsReverse implements greater-than.
3482template<bool IsReverse>
3483struct SUnitOrder {
Andrew Trick7ccdc5c2012-01-17 06:55:07 +00003484 bool operator()(SUnit *A, SUnit *B) const {
Andrew Trick8823dec2012-03-14 04:00:41 +00003485 if (IsReverse)
3486 return A->NodeNum > B->NodeNum;
3487 else
3488 return A->NodeNum < B->NodeNum;
Andrew Trick7ccdc5c2012-01-17 06:55:07 +00003489 }
3490};
3491
Andrew Tricke77e84e2012-01-13 06:30:30 +00003492/// Reorder instructions as much as possible.
Andrew Trick8823dec2012-03-14 04:00:41 +00003493class InstructionShuffler : public MachineSchedStrategy {
3494 bool IsAlternating;
3495 bool IsTopDown;
3496
3497 // Using a less-than relation (SUnitOrder<false>) for the TopQ priority
3498 // gives nodes with a higher number higher priority causing the latest
3499 // instructions to be scheduled first.
Eugene Zelenkodb56e5a2017-02-22 22:32:51 +00003500 PriorityQueue<SUnit*, std::vector<SUnit*>, SUnitOrder<false>>
Andrew Trick8823dec2012-03-14 04:00:41 +00003501 TopQ;
Eugene Zelenko32a40562017-09-11 23:00:48 +00003502
Andrew Trick8823dec2012-03-14 04:00:41 +00003503 // When scheduling bottom-up, use greater-than as the queue priority.
Eugene Zelenkodb56e5a2017-02-22 22:32:51 +00003504 PriorityQueue<SUnit*, std::vector<SUnit*>, SUnitOrder<true>>
Andrew Trick8823dec2012-03-14 04:00:41 +00003505 BottomQ;
Eugene Zelenkodb56e5a2017-02-22 22:32:51 +00003506
Andrew Tricke77e84e2012-01-13 06:30:30 +00003507public:
Andrew Trick8823dec2012-03-14 04:00:41 +00003508 InstructionShuffler(bool alternate, bool topdown)
3509 : IsAlternating(alternate), IsTopDown(topdown) {}
Andrew Tricke77e84e2012-01-13 06:30:30 +00003510
Craig Topper9d74a5a2014-04-29 07:58:41 +00003511 void initialize(ScheduleDAGMI*) override {
Andrew Trick8823dec2012-03-14 04:00:41 +00003512 TopQ.clear();
3513 BottomQ.clear();
3514 }
Andrew Trick7ccdc5c2012-01-17 06:55:07 +00003515
Andrew Trick8823dec2012-03-14 04:00:41 +00003516 /// Implement MachineSchedStrategy interface.
3517 /// -----------------------------------------
3518
Craig Topper9d74a5a2014-04-29 07:58:41 +00003519 SUnit *pickNode(bool &IsTopNode) override {
Andrew Trick8823dec2012-03-14 04:00:41 +00003520 SUnit *SU;
3521 if (IsTopDown) {
3522 do {
Craig Topperc0196b12014-04-14 00:51:57 +00003523 if (TopQ.empty()) return nullptr;
Andrew Trick8823dec2012-03-14 04:00:41 +00003524 SU = TopQ.top();
3525 TopQ.pop();
3526 } while (SU->isScheduled);
3527 IsTopNode = true;
Matthias Braunb550b762016-04-21 01:54:13 +00003528 } else {
Andrew Trick8823dec2012-03-14 04:00:41 +00003529 do {
Craig Topperc0196b12014-04-14 00:51:57 +00003530 if (BottomQ.empty()) return nullptr;
Andrew Trick8823dec2012-03-14 04:00:41 +00003531 SU = BottomQ.top();
3532 BottomQ.pop();
3533 } while (SU->isScheduled);
3534 IsTopNode = false;
3535 }
3536 if (IsAlternating)
3537 IsTopDown = !IsTopDown;
Andrew Trick7ccdc5c2012-01-17 06:55:07 +00003538 return SU;
3539 }
3540
Craig Topper9d74a5a2014-04-29 07:58:41 +00003541 void schedNode(SUnit *SU, bool IsTopNode) override {}
Andrew Trick61f1a272012-05-24 22:11:09 +00003542
Craig Topper9d74a5a2014-04-29 07:58:41 +00003543 void releaseTopNode(SUnit *SU) override {
Andrew Trick8823dec2012-03-14 04:00:41 +00003544 TopQ.push(SU);
3545 }
Craig Topper9d74a5a2014-04-29 07:58:41 +00003546 void releaseBottomNode(SUnit *SU) override {
Andrew Trick8823dec2012-03-14 04:00:41 +00003547 BottomQ.push(SU);
Andrew Tricke77e84e2012-01-13 06:30:30 +00003548 }
3549};
Eugene Zelenkodb56e5a2017-02-22 22:32:51 +00003550
3551} // end anonymous namespace
Andrew Tricke77e84e2012-01-13 06:30:30 +00003552
Andrew Trick02a80da2012-03-08 01:41:12 +00003553static ScheduleDAGInstrs *createInstructionShuffler(MachineSchedContext *C) {
Andrew Trick8823dec2012-03-14 04:00:41 +00003554 bool Alternate = !ForceTopDown && !ForceBottomUp;
3555 bool TopDown = !ForceBottomUp;
Benjamin Kramer05e7a842012-03-14 11:26:37 +00003556 assert((TopDown || !ForceTopDown) &&
Andrew Trick8823dec2012-03-14 04:00:41 +00003557 "-misched-topdown incompatible with -misched-bottomup");
Eugene Zelenkodb56e5a2017-02-22 22:32:51 +00003558 return new ScheduleDAGMILive(
3559 C, llvm::make_unique<InstructionShuffler>(Alternate, TopDown));
Andrew Tricke77e84e2012-01-13 06:30:30 +00003560}
Eugene Zelenkodb56e5a2017-02-22 22:32:51 +00003561
Andrew Trick8823dec2012-03-14 04:00:41 +00003562static MachineSchedRegistry ShufflerRegistry(
3563 "shuffle", "Shuffle machine instructions alternating directions",
3564 createInstructionShuffler);
Andrew Tricke77e84e2012-01-13 06:30:30 +00003565#endif // !NDEBUG
Andrew Trickea9fd952013-01-25 07:45:29 +00003566
3567//===----------------------------------------------------------------------===//
Andrew Trickd7f890e2013-12-28 21:56:47 +00003568// GraphWriter support for ScheduleDAGMILive.
Andrew Trickea9fd952013-01-25 07:45:29 +00003569//===----------------------------------------------------------------------===//
3570
3571#ifndef NDEBUG
3572namespace llvm {
3573
3574template<> struct GraphTraits<
3575 ScheduleDAGMI*> : public GraphTraits<ScheduleDAG*> {};
3576
3577template<>
3578struct DOTGraphTraits<ScheduleDAGMI*> : public DefaultDOTGraphTraits {
Eugene Zelenkodb56e5a2017-02-22 22:32:51 +00003579 DOTGraphTraits(bool isSimple = false) : DefaultDOTGraphTraits(isSimple) {}
Andrew Trickea9fd952013-01-25 07:45:29 +00003580
3581 static std::string getGraphName(const ScheduleDAG *G) {
3582 return G->MF.getName();
3583 }
3584
3585 static bool renderGraphFromBottomUp() {
3586 return true;
3587 }
3588
3589 static bool isNodeHidden(const SUnit *Node) {
Matthias Braund78ee542015-09-17 21:09:59 +00003590 if (ViewMISchedCutoff == 0)
3591 return false;
3592 return (Node->Preds.size() > ViewMISchedCutoff
3593 || Node->Succs.size() > ViewMISchedCutoff);
Andrew Trickea9fd952013-01-25 07:45:29 +00003594 }
3595
Andrew Trickea9fd952013-01-25 07:45:29 +00003596 /// If you want to override the dot attributes printed for a particular
3597 /// edge, override this method.
3598 static std::string getEdgeAttributes(const SUnit *Node,
3599 SUnitIterator EI,
3600 const ScheduleDAG *Graph) {
3601 if (EI.isArtificialDep())
3602 return "color=cyan,style=dashed";
3603 if (EI.isCtrlDep())
3604 return "color=blue,style=dashed";
3605 return "";
3606 }
3607
3608 static std::string getNodeLabel(const SUnit *SU, const ScheduleDAG *G) {
Alp Tokere69170a2014-06-26 22:52:05 +00003609 std::string Str;
3610 raw_string_ostream SS(Str);
Andrew Trickd7f890e2013-12-28 21:56:47 +00003611 const ScheduleDAGMI *DAG = static_cast<const ScheduleDAGMI*>(G);
3612 const SchedDFSResult *DFS = DAG->hasVRegLiveness() ?
Craig Topperc0196b12014-04-14 00:51:57 +00003613 static_cast<const ScheduleDAGMILive*>(G)->getDFSResult() : nullptr;
Andrew Trick7609b7d2013-09-06 17:32:42 +00003614 SS << "SU:" << SU->NodeNum;
3615 if (DFS)
3616 SS << " I:" << DFS->getNumInstrs(SU);
Andrew Trickea9fd952013-01-25 07:45:29 +00003617 return SS.str();
3618 }
Eugene Zelenko32a40562017-09-11 23:00:48 +00003619
Andrew Trickea9fd952013-01-25 07:45:29 +00003620 static std::string getNodeDescription(const SUnit *SU, const ScheduleDAG *G) {
3621 return G->getGraphNodeLabel(SU);
3622 }
3623
Andrew Trickd7f890e2013-12-28 21:56:47 +00003624 static std::string getNodeAttributes(const SUnit *N, const ScheduleDAG *G) {
Andrew Trickea9fd952013-01-25 07:45:29 +00003625 std::string Str("shape=Mrecord");
Andrew Trickd7f890e2013-12-28 21:56:47 +00003626 const ScheduleDAGMI *DAG = static_cast<const ScheduleDAGMI*>(G);
3627 const SchedDFSResult *DFS = DAG->hasVRegLiveness() ?
Craig Topperc0196b12014-04-14 00:51:57 +00003628 static_cast<const ScheduleDAGMILive*>(G)->getDFSResult() : nullptr;
Andrew Trickea9fd952013-01-25 07:45:29 +00003629 if (DFS) {
3630 Str += ",style=filled,fillcolor=\"#";
3631 Str += DOT::getColorString(DFS->getSubtreeID(N));
3632 Str += '"';
3633 }
3634 return Str;
3635 }
3636};
Eugene Zelenkodb56e5a2017-02-22 22:32:51 +00003637
3638} // end namespace llvm
Andrew Trickea9fd952013-01-25 07:45:29 +00003639#endif // NDEBUG
3640
3641/// viewGraph - Pop up a ghostview window with the reachable parts of the DAG
3642/// rendered using 'dot'.
Andrew Trickea9fd952013-01-25 07:45:29 +00003643void ScheduleDAGMI::viewGraph(const Twine &Name, const Twine &Title) {
3644#ifndef NDEBUG
3645 ViewGraph(this, Name, false, Title);
3646#else
3647 errs() << "ScheduleDAGMI::viewGraph is only available in debug builds on "
3648 << "systems with Graphviz or gv!\n";
3649#endif // NDEBUG
3650}
3651
3652/// Out-of-line implementation with no arguments is handy for gdb.
3653void ScheduleDAGMI::viewGraph() {
3654 viewGraph(getDAGName(), "Scheduling-Units Graph for " + getDAGName());
3655}